beilpsched.c 66.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
26
 * @file
 * @brief       ILP based instruction scheduling.
 * @author      Christian Wuerdig
 * @date        22.10.2006
 * @version     $Id$
 *
27
28
29
 * An ILP scheduler based on
 * "ILP-based Instruction Scheduling for IA-64"
 * by Daniel Kaestner and Sebastian Winkel
Christian Würdig's avatar
Christian Würdig committed
30
 * extended with register pressure constraints by Christian Wuerdig
31
32
33
 */
#include "config.h"

Christian Würdig's avatar
Christian Würdig committed
34
35
36
37
#ifdef WITH_ILP

#include <math.h>

Christian Würdig's avatar
Christian Würdig committed
38
39
40
41
#ifndef _WIN32
#include <strings.h>
#endif /* _WIN32 */

42
43
44
45
#include "irnode_t.h"
#include "irgwalk.h"
#include "irbitset.h"
#include "irphase_t.h"
46
#include "heights.h"
47
48
#include "iredges.h"
#include "pdeq.h"
49
#include "debug.h"
Christian Würdig's avatar
Christian Würdig committed
50
#include "irtools.h"
51
#include "irdump.h"
Matthias Braun's avatar
Matthias Braun committed
52
#include "irprintf.h"
53
#include "plist.h"
Christian Würdig's avatar
Christian Würdig committed
54
#include "irprintf.h"
Matthias Braun's avatar
Matthias Braun committed
55
#include "timing.h"
Christian Würdig's avatar
Christian Würdig committed
56
57
58

#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
59

Matthias Braun's avatar
Matthias Braun committed
60
61
#include "lc_opts.h"
#include "lc_opts_enum.h"
62

63
#include "be.h"
64
#include "benode.h"
65
#include "besched.h"
66
#include "beilpsched.h"
67
#include "beutil.h"
Christian Würdig's avatar
Christian Würdig committed
68
#include "bestat.h"
69
70
71
#include "beirg.h"
#include "bemachine.h"
#include "belistsched.h"
72
#include "bemodule.h"
73

74
typedef struct ilpsched_options_t {
75
	unsigned regpress;
Christian Würdig's avatar
Christian Würdig committed
76
77
78
79
	unsigned time_limit;
	char     log_file[1024];
} ilpsched_options_t;

80
typedef struct unit_type_info_t {
81
82
83
84
	int                            n_units;
	const be_execution_unit_type_t *tp;
} unit_type_info_t;

Christian Würdig's avatar
Christian Würdig committed
85
86
87
/**
 * holding the ILP variables of the different types
 */
88
typedef struct ilp_var_types_t {
Christian Würdig's avatar
Christian Würdig committed
89
	int *x;   /* x_{nt}^k variables */
90
	int *a;   /* a_{nt}^k variables */
Christian Würdig's avatar
Christian Würdig committed
91
92
93
	int *y;   /* y_{nt}^k variables */
} ilp_var_types_t;

94
95
96
/**
 * Holds alive variables for a node live-in to a block.
 */
97
typedef struct ilp_livein_node_t {
98
99
100
101
102
	ir_node  *irn;
	unsigned max_alive_steps;
	int      *a;
} ilp_livein_node_t;

Christian Würdig's avatar
Christian Würdig committed
103
/* attributes for a node */
104
typedef struct ilpsched_node_attr_t {
Christian Würdig's avatar
Christian Würdig committed
105
106
	unsigned asap;                     /**< The ASAP scheduling control step */
	unsigned alap;                     /**< The ALAP scheduling control step */
107
	unsigned latency;                  /**< Latency of this node (needed for sorting) */
Christian Würdig's avatar
Christian Würdig committed
108
109
	unsigned sched_point;              /**< the step in which the node is finally scheduled */
	unsigned visit_idx;                /**< Index of the node having visited this node last */
Christian Würdig's avatar
Christian Würdig committed
110
111
112
	unsigned consumer_idx;             /**< Index of the node having counted this node as consumer last */
	unsigned n_consumer;               /**< Number of consumers */
	ir_node  **block_consumer;         /**< List of consumer being in the same block */
113
	waitq    *projkeeps;               /**< A List of Projs and Keeps belonging to this node */
114
115
116
	unsigned block_idx     : 30;       /**< A unique per block index */
	unsigned alap_changed  : 1;        /**< the current ALAP has changed, revisit preds */
	unsigned is_dummy_node : 1;        /**< this node is assigned to DUMMY unit */
Christian Würdig's avatar
Christian Würdig committed
117
118
	bitset_t *transitive_block_nodes;  /**< Set of transitive block nodes (predecessors
											for ASAP, successors for ALAP */
119
	unsigned         n_unit_types;     /**< number of allowed execution unit types */
120
	unit_type_info_t *type_info;       /**< list of allowed execution unit types */
Christian Würdig's avatar
Christian Würdig committed
121
	ilp_var_types_t  ilp_vars;         /**< the different ILP variables */
122
123
} ilpsched_node_attr_t;

Christian Würdig's avatar
Christian Würdig committed
124
/* attributes for a block */
125
typedef struct ilpsched_block_attr_t {
Christian Würdig's avatar
Christian Würdig committed
126
127
	unsigned block_last_idx;        /**< The highest node index in block so far */
	unsigned n_interesting_nodes;   /**< The number of nodes interesting for scheduling */
Christian Würdig's avatar
Christian Würdig committed
128
	unsigned max_steps;             /**< Upper bound for block execution */
129
	plist_t  *root_nodes;           /**< A list of nodes having no user in current block */
Christian Würdig's avatar
Christian Würdig committed
130
	ir_node  *head_ilp_nodes;       /**< A linked list of nodes which will contribute to ILP */
131
	pset     *livein_nodes;         /**< A set of nodes which are live-in to this block */
132
133
} ilpsched_block_attr_t;

134
typedef union ilpsched_attr_ {
135
136
137
138
	ilpsched_node_attr_t  node_attr;
	ilpsched_block_attr_t block_attr;
} ilpsched_attr_t;

Christian Würdig's avatar
Christian Würdig committed
139
/* A irn for the phase and it's attributes (either node or block) */
140
typedef struct {
141
	const ir_node   *irn;
142
143
144
	ilpsched_attr_t attr;
} be_ilpsched_irn_t;

145
/* The ILP scheduling environment */
146
typedef struct {
147
	ir_phase             ph;            /**< The phase */
148
	ir_graph             *irg;          /**< The current irg */
149
	ir_heights_t         *height;       /**< The heights object of the irg */
150
151
152
153
154
155
	void                 *irg_env;      /**< An environment for the irg scheduling, provided by the backend */
	void                 *block_env;    /**< An environment for scheduling a block, provided by the backend */
	const arch_env_t     *arch_env;
	const be_machine_t   *cpu;          /**< the current abstract machine */
	ilpsched_options_t   *opts;         /**< the ilp options for current irg */
	const ilp_sched_selector_t *sel;    /**< The ILP sched selector provided by the backend */
156
157
158
	DEBUG_ONLY(firm_dbg_module_t *dbg);
} be_ilpsched_env_t;

159
/* convenience macros to handle phase irn data */
160
161
162
163
164
#define get_ilpsched_irn(ilpsched_env, irn) (phase_get_or_set_irn_data(&(ilpsched_env)->ph, (irn)))
#define is_ilpsched_block(node)             (is_Block((node)->irn))
#define get_ilpsched_block_attr(block)      (&(block)->attr.block_attr)
#define get_ilpsched_node_attr(node)        (&(node)->attr.node_attr)

165
/* check if node is considered for ILP scheduling */
166
#define consider_for_sched(env, irn) \
167
	(! (is_Block(irn)            ||  \
168
		is_normal_Proj(env, irn) ||  \
169
170
		is_Phi(irn)              ||  \
		is_NoMem(irn)            ||  \
Christian Würdig's avatar
Christian Würdig committed
171
		is_Unknown(irn)          ||  \
172
		is_End(irn)                  \
173
174
175
		))

/* gives the valid scheduling time step interval for a node */
Christian Würdig's avatar
Christian Würdig committed
176
177
#define VALID_SCHED_INTERVAL(na) ((na)->alap - (na)->asap + 1)

Christian Würdig's avatar
Christian Würdig committed
178
179
180
/* gives the valid interval where a node can die */
#define VALID_KILL_INTERVAL(ba, na) ((ba)->max_steps - (na)->asap + 1)

181
/* gives the corresponding ILP variable for given node, unit and time step */
Christian Würdig's avatar
Christian Würdig committed
182
183
184
#define ILPVAR_IDX(na, unit, control_step) \
	((unit) * VALID_SCHED_INTERVAL((na)) + (control_step) - (na)->asap + 1)

Christian Würdig's avatar
Christian Würdig committed
185
186
187
188
/* gives the corresponding dead nodes ILP variable for given node, unit and time step */
#define ILPVAR_IDX_DEAD(ba, na, unit, control_step) \
	((unit) * VALID_KILL_INTERVAL((ba), (na)) + (control_step) - (na)->asap + 1)

189
/* check if a double value is within an epsilon environment of 0 */
Christian Würdig's avatar
Christian Würdig committed
190
191
#define LPP_VALUE_IS_0(dbl) (fabs((dbl)) <= 1e-10)

192
/* option variable */
Christian Würdig's avatar
Christian Würdig committed
193
static ilpsched_options_t ilp_opts = {
194
	1,     /* default is with register pressure constraints */
Christian Würdig's avatar
Christian Würdig committed
195
	300,   /* 300 sec per block time limit */
Christian Würdig's avatar
Christian Würdig committed
196
197
	""     /* no log file */
};
198

199
/* ILP options */
Christian Würdig's avatar
Christian Würdig committed
200
static const lc_opt_table_entry_t ilpsched_option_table[] = {
201
	LC_OPT_ENT_BOOL("regpress",  "Use register pressure constraints", &ilp_opts.regpress),
Christian Würdig's avatar
Christian Würdig committed
202
203
	LC_OPT_ENT_INT("time_limit", "ILP time limit per block", &ilp_opts.time_limit),
	LC_OPT_ENT_STR("lpp_log",    "LPP logfile (stderr and stdout are supported)", ilp_opts.log_file, sizeof(ilp_opts.log_file)),
204
	LC_OPT_LAST
Christian Würdig's avatar
Christian Würdig committed
205
};
206

207
208
209
210
/*
	We need this global variable as we compare nodes dependent on heights,
	but we cannot pass any information to the qsort compare function.
*/
211
static ir_heights_t *glob_heights;
212

213
214
215
216
/**
 * Check if irn is a Proj, which has no execution units assigned.
 * @return 1 if irn is a Proj having no execution units assigned, 0 otherwise
 */
217
218
static inline int is_normal_Proj(const arch_env_t *env, const ir_node *irn)
{
219
	return is_Proj(irn) && (arch_env_get_allowed_execution_units(env, irn) == NULL);
220
221
222
223
224
225
}

/**
 * Skips normal Projs.
 * @return predecessor if irn is a normal Proj, otherwise irn.
 */
226
227
static inline ir_node *skip_normal_Proj(const arch_env_t *env, ir_node *irn)
{
228
	if (is_normal_Proj(env, irn))
229
230
231
232
		return get_Proj_pred(irn);
	return irn;
}

233
234
static inline int fixed_latency(const ilp_sched_selector_t *sel, ir_node *irn, void *env)
{
Christian Würdig's avatar
Christian Würdig committed
235
236
237
238
239
240
	unsigned lat = be_ilp_sched_latency(sel, irn, env);
	if (lat == 0 && ! is_Proj(irn) && ! be_is_Keep(irn))
		lat = 1;
	return lat;
}

241
242
static int cmp_live_in_nodes(const void *a, const void *b)
{
243
244
245
246
247
	const ilp_livein_node_t *n1 = a;
	const ilp_livein_node_t *n2 = b;

	return n1->irn != n2->irn;
}
Christian Würdig's avatar
Christian Würdig committed
248

249
250
251
/**
 * Compare scheduling time steps of two be_ilpsched_irn's.
 */
252
253
static int cmp_ilpsched_irn(const void *a, const void *b)
{
254
255
256
257
258
	be_ilpsched_irn_t    *n1   = *(be_ilpsched_irn_t **)a;
	be_ilpsched_irn_t    *n2   = *(be_ilpsched_irn_t **)b;
	ilpsched_node_attr_t *n1_a = get_ilpsched_node_attr(n1);
	ilpsched_node_attr_t *n2_a = get_ilpsched_node_attr(n2);

259
	if (n1_a->sched_point == n2_a->sched_point) {
260
261
		const ir_node *irn_a = n1->irn;
		const ir_node *irn_b = n2->irn;
262
263
264
265
266

		if (heights_reachable_in_block(glob_heights, irn_a, irn_b))
			return 1;
		if (heights_reachable_in_block(glob_heights, irn_b, irn_a))
			return -1;
267
268
269
270
271
272

		/*
			Ok, timestep is equal and the nodes are parallel,
			so check latency and schedule high latency first.
		*/
		return QSORT_CMP(n2_a->latency, n1_a->latency);
273
274
275
	}
	else
		return QSORT_CMP(n1_a->sched_point, n2_a->sched_point);
276
277
}

278
static void *reinit_ilpsched_irn(ir_phase *ph, const ir_node *irn, void *old)
279
{
280
	be_ilpsched_irn_t *res = old;
281

282
283
284
	/* if we have already some data: check for reinitialization */
	if (! is_Block(irn)) {
		ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
Christian Würdig's avatar
Christian Würdig committed
285

286
287
288
289
		if (! na->transitive_block_nodes) {
			ir_node               *block      = get_nodes_block(irn);
			be_ilpsched_irn_t     *block_node = phase_get_or_set_irn_data(ph, block);
			ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
Christian Würdig's avatar
Christian Würdig committed
290

291
292
293
294
295
296
297
			/* we are called after the block indices have been build: create bitset */
			na->transitive_block_nodes = bitset_obstack_alloc(phase_obst(ph), ba->block_last_idx);
		} else {
			/* we are called from reinit block data: clear the bitset */
			bitset_clear_all(na->transitive_block_nodes);
			na->visit_idx    = 0;
			na->alap_changed = 1;
298
299
		}
	}
300
301
	return res;
}
302

303
304
305
306
307
308
/**
 * In case there is no phase information for irn, initialize it.
 */
static void *init_ilpsched_irn(ir_phase *phase, const ir_node *irn)
{
	be_ilpsched_irn_t *res = phase_alloc(phase, sizeof(res[0]));
309
310
	res->irn = irn;

311
	/* set ilpsched irn attributes (either block or irn) */
312
313
314
315
	if (is_Block(irn)) {
		ilpsched_block_attr_t *ba = get_ilpsched_block_attr(res);

		ba->n_interesting_nodes = 0;
Christian Würdig's avatar
Christian Würdig committed
316
		ba->block_last_idx      = 0;
317
		ba->root_nodes          = plist_new();
Christian Würdig's avatar
Christian Würdig committed
318
		ba->head_ilp_nodes      = NULL;
319
		ba->livein_nodes        = new_pset(cmp_live_in_nodes, 16);
Christian Würdig's avatar
Christian Würdig committed
320
		ba->max_steps           = 0;
321
	} else {
322
		ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
Christian Würdig's avatar
Christian Würdig committed
323
		memset(na, 0, sizeof(*na));
324
325
326
327
328
	}

	return res;
}

Christian Würdig's avatar
Christian Würdig committed
329
330
331
/**
 * Assign a per block unique number to each node.
 */
332
333
static void build_block_idx(ir_node *irn, void *walk_env)
{
Christian Würdig's avatar
Christian Würdig committed
334
335
336
337
338
	be_ilpsched_env_t     *env = walk_env;
	be_ilpsched_irn_t     *node, *block_node;
	ilpsched_node_attr_t  *na;
	ilpsched_block_attr_t *ba;

339
	set_irn_link(irn, NULL);
340
	if (! consider_for_sched(env->arch_env, irn))
Christian Würdig's avatar
Christian Würdig committed
341
342
343
344
345
346
347
348
349
350
		return;

	node       = get_ilpsched_irn(env, irn);
	na         = get_ilpsched_node_attr(node);
	block_node = get_ilpsched_irn(env, get_nodes_block(irn));
	ba         = get_ilpsched_block_attr(block_node);

	na->block_idx = ba->block_last_idx++;
}

351
352
353
354
355
356
357
358
359
360
361
/********************************************************
 *                              __        _
 *                             / /       | |
 *   __ _ ___  __ _ _ __      / /    __ _| | __ _ _ __
 *  / _` / __|/ _` | '_ \    / /    / _` | |/ _` | '_ \
 * | (_| \__ \ (_| | |_) |  / /    | (_| | | (_| | |_) |
 *  \__,_|___/\__,_| .__/  /_/      \__,_|_|\__,_| .__/
 *                 | |                           | |
 *                 |_|                           |_|
 ********************************************************/

362
363
364
/**
 * Add all nodes having no user in current block to last_nodes list.
 */
365
366
static void collect_alap_root_nodes(ir_node *irn, void *walk_env)
{
367
368
	ir_node               *block;
	const ir_edge_t       *edge;
Christian Würdig's avatar
Christian Würdig committed
369
	be_ilpsched_irn_t     *block_node, *node;
370
	ilpsched_block_attr_t *ba;
Christian Würdig's avatar
Christian Würdig committed
371
372
	ilpsched_node_attr_t  *na;
	int                   i, j;
Christian Würdig's avatar
Christian Würdig committed
373
	be_ilpsched_env_t     *env           = walk_env;
374
	int                   has_block_user = 0;
Christian Würdig's avatar
Christian Würdig committed
375
	unsigned              n_consumer     = 0;
Christian Würdig's avatar
Christian Würdig committed
376
	ir_edge_kind_t        ekind[2]       = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
Christian Würdig's avatar
Christian Würdig committed
377
	ir_node               **consumer;
378
	unsigned              idx;
379

380
	if (! consider_for_sched(env->arch_env, irn))
381
382
		return;

Christian Würdig's avatar
Christian Würdig committed
383
384
385
	block    = get_nodes_block(irn);
    idx      = get_irn_idx(irn);
	consumer = NEW_ARR_F(ir_node *, 0);
386

Christian Würdig's avatar
Christian Würdig committed
387
	DBG((env->dbg, LEVEL_3, "%+F (%+F) is interesting, examining ... ", irn, block));
388

Christian Würdig's avatar
Christian Würdig committed
389
390
	/* check data and dependency out edges */
	for (i = 0; i < 2 && ! has_block_user; ++i) {
Christian Würdig's avatar
Christian Würdig committed
391
392
		foreach_out_edge_kind(irn, edge, ekind[i]) {
			ir_node *user = get_edge_src_irn(edge);
393

394
			if (is_normal_Proj(env->arch_env, user)) {
Christian Würdig's avatar
Christian Würdig committed
395
				const ir_edge_t *user_edge;
396

Christian Würdig's avatar
Christian Würdig committed
397
398
				if (get_irn_mode(user) == mode_X)
					continue;
399

Christian Würdig's avatar
Christian Würdig committed
400
401
402
403
404
				/* The ABI ensures, that there will be no ProjT nodes in the graph. */
				for (j = 0; j < 2; ++j) {
					foreach_out_edge_kind(user, user_edge, ekind[j]) {
						ir_node *real_user = get_edge_src_irn(user_edge);

405
						if (! is_Phi(real_user) && ! is_Block(real_user)) {
Christian Würdig's avatar
Christian Würdig committed
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
							be_ilpsched_irn_t    *node = get_ilpsched_irn(env, real_user);
							ilpsched_node_attr_t *ua   = get_ilpsched_node_attr(node);

							/* skip already visited nodes */
							if (ua->consumer_idx == idx)
								continue;

							/* check if node has user in this block and collect the user if it's a data user */
							if (get_nodes_block(real_user) == block) {
								if (i == 0 && j == 0)
									ARR_APP1(ir_node *, consumer, real_user);
								has_block_user = 1;
							}

							/* only count data consumer */
							if (i == 0)
								n_consumer++;

							/* mark user as visited by this node */
							ua->consumer_idx = idx;
Christian Würdig's avatar
Christian Würdig committed
426
427
						}
					}
428
				}
Christian Würdig's avatar
Christian Würdig committed
429
430
431
432
			}
			else if (is_Block(user)) {
				continue;
			}
433
			else if (! is_Phi(user)) {
Christian Würdig's avatar
Christian Würdig committed
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
				be_ilpsched_irn_t    *node = get_ilpsched_irn(env, user);
				ilpsched_node_attr_t *ua   = get_ilpsched_node_attr(node);

				/* skip already visited nodes */
				if (ua->consumer_idx == idx)
					continue;

				/* check if node has user in this block and collect the user if it's a data user */
				if (get_nodes_block(user) == block) {
					if (i == 0)
						ARR_APP1(ir_node *, consumer, user);
					has_block_user = 1;
				}

				/* only count data consumer */
				if (i == 0)
					n_consumer++;

				/* mark user visited by this node */
				ua->consumer_idx = idx;
Christian Würdig's avatar
Christian Würdig committed
454
			}
455
456
457
			else if (get_nodes_block(user) != block) {
				n_consumer++;
			}
458
459
460
461
462
463
464
465
		}
	}

	block_node = get_ilpsched_irn(env, block);
	ba         = get_ilpsched_block_attr(block_node);

	ba->n_interesting_nodes++;

Christian Würdig's avatar
Christian Würdig committed
466
	/* current irn has no user inside this block, add to queue */
467
	if (! has_block_user) {
Christian Würdig's avatar
Christian Würdig committed
468
		DB((env->dbg, LEVEL_3, "root node\n"));
469
		plist_insert_back(ba->root_nodes, irn);
Christian Würdig's avatar
Christian Würdig committed
470
471
472
	}
	else {
		DB((env->dbg, LEVEL_3, "normal node\n"));
473
	}
Christian Würdig's avatar
Christian Würdig committed
474
475
476
477
478
479
480
481

	/* record number of all consumer and the consumer within the same block */
	node = get_ilpsched_irn(env, irn);
	na   = get_ilpsched_node_attr(node);
	na->n_consumer     = n_consumer;
	na->block_consumer = NEW_ARR_D(ir_node *, phase_obst(&env->ph), ARR_LEN(consumer));
	memcpy(na->block_consumer, consumer, ARR_LEN(consumer) * sizeof(na->block_consumer[0]));
	DEL_ARR_F(consumer);
482
483
}

484
485
486
/**
 * Calculate the ASAP scheduling step for current irn.
 */
487
488
static void calculate_irn_asap(ir_node *irn, void *walk_env)
{
489
490
491
492
493
494
495
496
	be_ilpsched_env_t     *env = walk_env;
	int                   i;
	ir_node               *block;
	be_ilpsched_irn_t     *node, *block_node;
	ilpsched_node_attr_t  *na;
	ilpsched_block_attr_t *ba;

	/* These nodes are handled separate */
497
	if (! consider_for_sched(env->arch_env, irn))
498
499
500
501
502
503
504
505
506
507
		return;

	DBG((env->dbg, LEVEL_2, "Calculating ASAP of node %+F ... ", irn));

	block    = get_nodes_block(irn);
	node     = get_ilpsched_irn(env, irn);
	na       = get_ilpsched_node_attr(node);
	na->asap = 1;

	for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
508
		ir_node *pred = skip_normal_Proj(env->arch_env, get_irn_in_or_dep(irn, i));
509
510
511
512
513
514
515

		/* check for greatest distance to top */
		if (! is_Phi(pred) && ! is_NoMem(pred) && get_nodes_block(pred) == block) {
			be_ilpsched_irn_t    *pred_node = get_ilpsched_irn(env, pred);
			ilpsched_node_attr_t *pna       = get_ilpsched_node_attr(pred_node);
			unsigned             lat;

516
517
518
			lat         = fixed_latency(env->sel, pred, env->block_env);
			na->latency = lat;
			na->asap    = MAX(na->asap, pna->asap + lat);
519
520
521
522
523
524
525
526
527
		}
	}

	/* add node to ILP node list and update max_steps */
	block_node = get_ilpsched_irn(env, block);
	ba         = get_ilpsched_block_attr(block_node);

	set_irn_link(irn, ba->head_ilp_nodes);
	ba->head_ilp_nodes = irn;
528
	ba->max_steps     += fixed_latency(env->sel, irn, env->block_env);
529
530
531
532
533
534
535
536

	DB((env->dbg, LEVEL_2, "%u\n", na->asap));
}

/**
 * Calculate the ALAP scheduling step of all irns in current block.
 * Depends on max_steps being calculated.
 */
537
538
static void calculate_block_alap(ir_node *block, void *walk_env)
{
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
	be_ilpsched_env_t     *env        = walk_env;
	be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
	ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
	waitq                 *cur_queue  = new_waitq();
	plist_element_t       *el;

	assert(is_Block(block));

	DBG((env->dbg, LEVEL_2, "Calculating ALAP for nodes in %+F (%u nodes, %u max steps)\n",
		block, ba->n_interesting_nodes, ba->max_steps));

	/* TODO: Might be faster to use out edges and call phase_reinit_single_irn_data */
	//phase_reinit_block_irn_data(&env->ph, block);

	/* init start queue */
	foreach_plist(ba->root_nodes, el) {
		waitq_put(cur_queue, plist_element_get_value(el));
	}

	/* repeat until all nodes are processed */
	while (! waitq_empty(cur_queue)) {
		waitq *next_queue = new_waitq();

		/* process all nodes in current step */
		while (! waitq_empty(cur_queue)) {
			ir_node              *cur_irn = waitq_get(cur_queue);
			be_ilpsched_irn_t    *node    = get_ilpsched_irn(env, cur_irn);
			ilpsched_node_attr_t *na      = get_ilpsched_node_attr(node);
			int                  i;

			/* cur_node has no alap set -> it's a root node, set to max alap */
			if (na->alap == 0) {
				na->alap = ba->max_steps;
				DBG((env->dbg, LEVEL_2, "setting ALAP of node %+F to %u, handling preds:\n",
					cur_irn, na->alap));
			}
			else {
				DBG((env->dbg, LEVEL_2, "ALAP of node %+F is %u, handling preds:\n",
					cur_irn, na->alap));
			}

			/* set the alap's of all predecessors */
			for (i = get_irn_ins_or_deps(cur_irn) - 1; i >= 0; --i) {
582
				ir_node *pred = skip_normal_Proj(env->arch_env, get_irn_in_or_dep(cur_irn, i));
583
584
585
586
587
588
589
590
591
592
593
594

				/* check for greatest distance to bottom */
				if (! is_Phi(pred) && ! is_NoMem(pred) && get_nodes_block(pred) == block) {
					be_ilpsched_irn_t    *pred_node = get_ilpsched_irn(env, pred);
					ilpsched_node_attr_t *pna       = get_ilpsched_node_attr(pred_node);
					unsigned             lat;

					/* mark the predecessor as visited by current irn */
					if (pna->visit_idx == get_irn_idx(cur_irn) && ! na->alap_changed)
						continue;
					pna->visit_idx = get_irn_idx(cur_irn);

Christian Würdig's avatar
Christian Würdig committed
595
					lat = fixed_latency(env->sel, pred, env->block_env);
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628

					/* set ALAP of current pred */
					if (pna->alap == 0) {
						/* current ALAP is 0: node has not yet been visited */
						pna->alap_changed = 1;
						pna->alap         = na->alap - lat;
					}
					else if (pna->alap > na->alap - lat) {
						/* we found a longer path to root node: change ALAP */
						pna->alap         = na->alap - lat;
						pna->alap_changed = 1;
					}
					else {
						/* current ALAP is best found so far: keep it */
						pna->alap_changed = 0;
					}

					DBG((env->dbg, LEVEL_2, "\tsetting ALAP of node %+F to %u\n", pred, pna->alap));

					/* enqueue node for next iteration */
					if (get_irn_ins_or_deps(pred) > 0)
						waitq_put(next_queue, pred);
				}
			}
		}

		/* prepare for next iteration */
		del_waitq(cur_queue);
		cur_queue = next_queue;
	}
}

/**
629
 * Free list of root nodes and the set of live-in nodes.
630
 */
631
632
static void clear_unwanted_data(ir_node *block, void *walk_env)
{
633
634
635
636
637
638
	be_ilpsched_env_t     *env        = walk_env;
	be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
	ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);

	plist_free(ba->root_nodes);
	ba->root_nodes = NULL;
639
640
	del_pset(ba->livein_nodes);
	ba->livein_nodes = NULL;
641
642
643
644
645
646
}

/**
 * Refine the {ASAP(n), ALAP(n)} interval for the nodes.
 * Set the ASAP/ALAP times of Projs and Keeps to their ancestor ones.
 */
647
648
static void refine_asap_alap_times(ir_node *irn, void *walk_env)
{
649
650
	be_ilpsched_env_t    *env  = walk_env;
	ir_node              *pred = irn;
651
652
653
	be_ilpsched_irn_t    *node, *pred_node;
	ilpsched_node_attr_t *na, *pna;

654
	if (! consider_for_sched(env->arch_env, irn))
655
656
657
658
659
660
661
		return;

	if (! is_Proj(irn) && ! be_is_Keep(irn))
		return;

	/* go to the ancestor */
	if (be_is_Keep(irn))
662
663
		pred = get_irn_n(irn, 0);
	pred = skip_Proj(pred);
664
665
666
667
668
669
670
671
672

	node      = get_ilpsched_irn(env, irn);
	pred_node = get_ilpsched_irn(env, pred);
	na        = get_ilpsched_node_attr(node);
	pna       = get_ilpsched_node_attr(pred_node);

	na->asap = pna->asap;
	na->alap = pna->alap;

673
674
675
676
	/* record all Projs and Keeps for this node */
	if (! pna->projkeeps)
		pna->projkeeps = new_waitq();
	waitq_put(pna->projkeeps, irn);
Christian Würdig's avatar
Christian Würdig committed
677

678
	DBG((env->dbg, LEVEL_2, "fixing ASAP/ALAP of %+F to %u/%u\n", irn, na->asap, na->alap));
679
680
}

Christian Würdig's avatar
Christian Würdig committed
681
682
683
684
685
686
687
/*******************************************
 *           _              _       _
 *          | |            | |     | |
 *  ___  ___| |__   ___  __| |_   _| | ___
 * / __|/ __| '_ \ / _ \/ _` | | | | |/ _ \
 * \__ \ (__| | | |  __/ (_| | |_| | |  __/
 * |___/\___|_| |_|\___|\__,_|\__,_|_|\___|
688
 *
Christian Würdig's avatar
Christian Würdig committed
689
 *******************************************/
Christian Würdig's avatar
Christian Würdig committed
690

691
692
static inline void check_for_keeps(waitq *keeps, const ir_node *block, const ir_node *irn)
{
693
	const ir_edge_t *edge;
Matthias Braun's avatar
Matthias Braun committed
694
        (void) block;
695
696
697
698
699
700
701
702
703
704
705

	foreach_out_edge(irn, edge) {
		ir_node *user = get_edge_src_irn(edge);

		if (be_is_Keep(user)) {
			assert(get_nodes_block(user) == block && "Keep must not be in different block.");
			waitq_put(keeps, user);
		}
	}
}

706
707
708
/**
 * Inserts @p irn before @p before into schedule and notifies backend.
 */
709
static inline void notified_sched_add_before(be_ilpsched_env_t *env,
710
	const ir_node *before, const ir_node *irn, unsigned cycle)
711
712
{
	be_ilp_sched_node_scheduled(env->sel, irn, cycle, env->block_env);
713
	sched_add_before((ir_node*) before, (ir_node*) irn);
714
715
}

716
717
718
719
/**
 * Adds a node, it's Projs (in case of mode_T nodes) and
 * it's Keeps to schedule.
 */
720
721
static void add_to_sched(be_ilpsched_env_t *env, const ir_node *block, const ir_node *irn, unsigned cycle)
{
722
723
724
	const ir_edge_t *edge;
	waitq           *keeps = new_waitq();

Christian Würdig's avatar
Christian Würdig committed
725
	/* mode_M nodes are not scheduled */
726
727
728
	if (get_irn_mode(irn) == mode_M)
		return;

729
730
	if (! sched_is_scheduled(irn))
		notified_sched_add_before(env, block, irn, cycle);
731
732
733
734
735
736

	/* add Projs */
	if (get_irn_mode(irn) == mode_T) {
		foreach_out_edge(irn, edge) {
			ir_node *user = get_edge_src_irn(edge);

737
738
739
			if ((to_appear_in_schedule(user) || get_irn_mode(user) == mode_b) &&
				get_irn_n_edges(user) > 0)
			{
740
				notified_sched_add_before(env, block, user, cycle);
741
			}
742
743
744
745
746
747
748
749
750
751
752
753

			check_for_keeps(keeps, block, user);
		}
	}
	else {
		check_for_keeps(keeps, block, irn);
	}

	/* add Keeps */
	while (! waitq_empty(keeps)) {
		ir_node *keep = waitq_get(keeps);
		if (! sched_is_scheduled(keep))
754
			notified_sched_add_before(env, block, keep, cycle);
755
756
757
758
759
760
761
762
	}

	del_waitq(keeps);
}

/**
 * Schedule all nodes in the given block, according to the ILP solution.
 */
763
764
static void apply_solution(be_ilpsched_env_t *env, lpp_t *lpp, ir_node *block)
{
765
766
767
768
769
770
771
772
	be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
	ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
	be_ilpsched_irn_t     **sched_nodes;
	unsigned              i, l;
	ir_node               *cfop, *irn;
	const ir_edge_t       *edge;

	/* init block schedule list */
773
	sched_init_block(block);
774
775
776
777
778
779
780
781
782
783
784
785
786

	/* collect nodes and their scheduling time step */
	sched_nodes = NEW_ARR_F(be_ilpsched_irn_t *, 0);
	if (ba->n_interesting_nodes == 0) {
		/* ignore */
	}
	else if (ba->n_interesting_nodes == 1) {
		be_ilpsched_irn_t *node = get_ilpsched_irn(env, ba->head_ilp_nodes);

		/* add the single node */
		ARR_APP1(be_ilpsched_irn_t *, sched_nodes, node);
	}
	else {
Christian Würdig's avatar
Christian Würdig committed
787
		/* check all nodes for their positive solution */
788
789
790
791
792
793
794
795
796
797
798
		foreach_linked_irns(ba->head_ilp_nodes, irn) {
			be_ilpsched_irn_t    *node;
			ilpsched_node_attr_t *na;
			int                  tp_idx, found;
			unsigned             cur_var, t;

			node    = get_ilpsched_irn(env, irn);
			na      = get_ilpsched_node_attr(node);
			cur_var = 0;
			found   = 0;

799
800
801
802
803
804
			if (! na->is_dummy_node) {
				for (tp_idx = na->n_unit_types - 1; ! found && tp_idx >= 0; --tp_idx) {
					for (t = na->asap - 1; ! found && t <= na->alap - 1; ++t) {
						double cost = lpp_get_var_sol(lpp, na->ilp_vars.y[cur_var]);

						if (! LPP_VALUE_IS_0(cost)) {
805
							DBG((env->dbg, LEVEL_3, "%+F has additional regpressure costs of %f\n", irn, cost));
806
807
808
809
810
811
812
							found = 1;
						}
					}
				}
			}

			found = 0;
Christian Würdig's avatar
Christian Würdig committed
813
			/* go over all variables of a node until the non-zero one is found */
814
815
			for (tp_idx = na->n_unit_types - 1; ! found && tp_idx >= 0; --tp_idx) {
				for (t = na->asap - 1; ! found && t <= na->alap - 1; ++t) {
Christian Würdig's avatar
Christian Würdig committed
816
817
818
					double val = lpp_get_var_sol(lpp, na->ilp_vars.x[cur_var++]);

					/* check, if variable is set to one (it's not zero then :) */
819
820
821
					if (! LPP_VALUE_IS_0(val)) {
						na->sched_point = t;
						ARR_APP1(be_ilpsched_irn_t *, sched_nodes, node);
Christian Würdig's avatar
Christian Würdig committed
822
						DBG((env->dbg, LEVEL_2, "Schedpoint of %+F is %u at unit type %s\n",
823
824
825
826
827
828
829
							irn, t, na->type_info[tp_idx].tp->name));
						found = 1;
					}
				}
			}
		}

830
		glob_heights = env->height;
831
832
833
834
835
836
837
838
839
840
841
		/* sort nodes ascending by scheduling time step */
		qsort(sched_nodes, ARR_LEN(sched_nodes), sizeof(sched_nodes[0]), cmp_ilpsched_irn);
	}

	/* make all Phis ready and remember the single cf op */
	cfop = NULL;
	foreach_out_edge(block, edge) {
		irn = get_edge_src_irn(edge);

		switch (get_irn_opcode(irn)) {
			case iro_Phi:
842
				add_to_sched(env, block, irn, 0);
843
				break;
844
			case beo_Start:
845
846
847
			case iro_End:
			case iro_Proj:
			case iro_Bad:
Christian Würdig's avatar
Christian Würdig committed
848
			case iro_Unknown:
849
850
851
				break;
			default:
				if (is_cfop(irn)) {
Christian Würdig's avatar
Christian Würdig committed
852
					assert(cfop == NULL && "Highlander - there can be only one");
853
854
855
856
857
858
859
860
					cfop = irn;
				}
			break;
		}
	}

	/* add all nodes from list */
	for (i = 0, l = ARR_LEN(sched_nodes); i < l; ++i) {
861
		ilpsched_node_attr_t *na = get_ilpsched_node_attr(sched_nodes[i]);
Christian Würdig's avatar
Christian Würdig committed
862
863
		if (sched_nodes[i]->irn != cfop)
			add_to_sched(env, block, sched_nodes[i]->irn, na->sched_point);
864
865
866
867
	}

	/* schedule control flow node if not already done */
	if (cfop && ! sched_is_scheduled(cfop))
868
		add_to_sched(env, block, cfop, 0);
869
870
871
872

	DEL_ARR_F(sched_nodes);
}

Christian Würdig's avatar
Christian Würdig committed
873
874
875
876
877
878
879
880
881
882
/***************************************************************
 *   _____ _      _____     _____           _   _
 *  |_   _| |    |  __ \   / ____|         | | (_)
 *    | | | |    | |__) | | (___   ___  ___| |_ _  ___  _ __
 *    | | | |    |  ___/   \___ \ / _ \/ __| __| |/ _ \| '_ \
 *   _| |_| |____| |       ____) |  __/ (__| |_| | (_) | | | |
 *  |_____|______|_|      |_____/ \___|\___|\__|_|\___/|_| |_|
 *
 ***************************************************************/

Christian Würdig's avatar
Christian Würdig committed
883
/**
Christian Würdig's avatar
Christian Würdig committed
884
 * Check if node can be executed on given unit type.
Christian Würdig's avatar
Christian Würdig committed
885
 */
886
887
static inline int is_valid_unit_type_for_node(const be_execution_unit_type_t *tp, be_ilpsched_irn_t *node)
{
Christian Würdig's avatar
Christian Würdig committed
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
	int                  i;
	ilpsched_node_attr_t *na = get_ilpsched_node_attr(node);

	for (i = na->n_unit_types - 1; i >= 0; --i) {
		if (na->type_info[i].tp == tp)
			return i;
	}

	return -1;
}

/************************************************
 *                   _       _     _
 *                  (_)     | |   | |
 *  __   ____ _ _ __ _  __ _| |__ | | ___  ___
 *  \ \ / / _` | '__| |/ _` | '_ \| |/ _ \/ __|
 *   \ V / (_| | |  | | (_| | |_) | |  __/\__ \
 *    \_/ \__,_|_|  |_|\__,_|_.__/|_|\___||___/
 *
 ************************************************/

909
910
static int be_ilpsched_set_type_info(be_ilpsched_env_t *env, ir_node *irn, struct obstack *obst)
{
911
	const be_execution_unit_t ***execunits = arch_env_get_allowed_execution_units(env->arch_env, irn);
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
	unsigned                  n_unit_types = 0;
	be_ilpsched_irn_t         *node;
	ilpsched_node_attr_t      *na;
	unsigned                  unit_idx, tp_idx;

	/* count number of available unit types for this node */
	for (n_unit_types = 0; execunits[n_unit_types]; ++n_unit_types)
		/* just count */ ;

	node = get_ilpsched_irn(env, irn);
	na   = get_ilpsched_node_attr(node);

	if (! na->type_info) {
		na->n_unit_types = n_unit_types;
		na->type_info    = NEW_ARR_D(unit_type_info_t, obst, n_unit_types);

		/* fill the type info array */
		for (tp_idx = 0; tp_idx < n_unit_types; ++tp_idx) {
			for (unit_idx = 0; execunits[tp_idx][unit_idx]; ++unit_idx) {
				/* beware: we also count number of available units here */
				if (be_machine_is_dummy_unit(execunits[tp_idx][unit_idx]))
					na->is_dummy_node = 1;
			}

			na->type_info[tp_idx].tp      = execunits[tp_idx][0]->tp;
			na->type_info[tp_idx].n_units = unit_idx;
		}
	}

	return n_unit_types;
}

/**
 * Returns the largest alap time of a user of @p irn.
 * The user must be in block @p block.
 */
948
949
static unsigned be_ilpsched_get_max_alap_user(be_ilpsched_env_t *env, const ir_node *irn, const ir_node *block)
{
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
	const ir_edge_t *edge;
	unsigned        max_alap = 0;

	foreach_out_edge(irn, edge) {
		ir_node *user = get_edge_src_irn(edge);

		if (get_nodes_block(user) == block) {
			be_ilpsched_irn_t    *node = get_ilpsched_irn(env, user);
			ilpsched_node_attr_t *na   = get_ilpsched_node_attr(node);

			max_alap = MAX(max_alap, na->alap);
		}
	}

	assert(max_alap > 0);
	return max_alap;
}

Christian Würdig's avatar
Christian Würdig committed
968
969
970
971
972
973
/**
 * Create the following variables:
 * - x_{nt}^k    binary     weigthed with: t
 *      node n is scheduled at time step t to unit type k
 * ==>> These variables represent the schedule
 *
974
975
 * - a_{nt}^k    binary     weighted with num_nodes
 *      node n is alive at time step t on unit type k
Christian Würdig's avatar
Christian Würdig committed
976
 *
977
978
 * - y_{nt}^k    continuous  weighted with: num_nodes^2
 *      register pressure over limit for unit type k
Christian Würdig's avatar
Christian Würdig committed
979
 * ==>> These variables represent the register pressure
980
 *
Christian Würdig's avatar
Christian Würdig committed
981
 */
982
983
static void create_variables(be_ilpsched_env_t *env, lpp_t *lpp, be_ilpsched_irn_t *block_node, struct obstack *var_obst)
{
Christian Würdig's avatar
Christian Würdig committed
984
	char                  buf[1024];
Christian Würdig's avatar
Christian Würdig committed
985
986
	ir_node               *irn;
	unsigned              num_block_var, num_nodes;
987
	ilp_livein_node_t     *livein;
Christian Würdig's avatar
Christian Würdig committed
988
989
990
	ilpsched_block_attr_t *ba      = get_ilpsched_block_attr(block_node);
	unsigned              weigth_y = ba->n_interesting_nodes * ba->n_interesting_nodes;

991
992
	stat_ev_tim_push();

Christian Würdig's avatar
Christian Würdig committed
993
994
	num_block_var = num_nodes = 0;
	foreach_linked_irns(ba->head_ilp_nodes, irn) {
995
996
997
998
999
		be_ilpsched_irn_t    *node;
		ilpsched_node_attr_t *na;
		unsigned             n_unit_types, tp_idx, n_var, cur_unit;
		unsigned             cur_var_ad, cur_var_x, cur_var_y, num_ad;
		int                  i;
Christian Würdig's avatar
Christian Würdig committed
1000

1001
1002
1003
		node         = get_ilpsched_irn(env, irn);
		na           = get_ilpsched_node_attr(node);
		n_unit_types = be_ilpsched_set_type_info(env, irn, var_obst);
Christian Würdig's avatar
Christian Würdig committed
1004
1005
1006
1007
1008

		/* allocate space for ilp variables */
		na->ilp_vars.x = NEW_ARR_D(int, var_obst, n_unit_types * VALID_SCHED_INTERVAL(na));
		memset(na->ilp_vars.x, -1, ARR_LEN(na->ilp_vars.x) * sizeof(na->ilp_vars.x[0]));

1009
1010
1011
1012
1013
		/* we need these variables only for "real" nodes */
		if (! na->is_dummy_node) {
			na->ilp_vars.y = NEW_ARR_D(int, var_obst, n_unit_types * VALID_SCHED_INTERVAL(na));
			memset(na->ilp_vars.y, -1, ARR_LEN(na->ilp_vars.y) * sizeof(na->ilp_vars.y[0]));

1014
1015
1016
			num_ad         = ba->max_steps - na->asap + 1;
			na->ilp_vars.a = NEW_ARR_D(int, var_obst, n_unit_types * num_ad);
			memset(na->ilp_vars.a, -1, ARR_LEN(na->ilp_vars.a) * sizeof(na->ilp_vars.a[0]));
1017
		}
Christian Würdig's avatar
Christian Würdig committed
1018
1019
1020
1021

		DBG((env->dbg, LEVEL_3, "\thandling %+F (asap %u, alap %u, unit types %u):\n",
			irn, na->asap, na->alap, na->n_unit_types));

1022
		cur_var_x = cur_var_ad = cur_var_y = cur_unit = n_var = 0;
Christian Würdig's avatar
Christian Würdig committed
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
		/* create variables */
		for (tp_idx = 0; tp_idx < n_unit_types; ++tp_idx) {
			unsigned t;

			for (t = na->asap - 1; t <= na->alap - 1; ++t) {
				/* x_{nt}^k variables */
				snprintf(buf, sizeof(buf), "x_n%u_%s_%u",
					get_irn_idx(irn), na->type_info[tp_idx].tp->name, t);
				na->ilp_vars.x[cur_var_x++] = lpp_add_var(lpp, buf, lpp_binary, (double)(t + 1));
				DBG((env->dbg, LEVEL_4, "\t\tcreated ILP variable %s\n", buf));
1033
1034
1035
				/* variable counter */
				n_var++;
				num_block_var++;
Christian Würdig's avatar
Christian Würdig committed
1036

1037
1038
1039
1040
				if (! na->is_dummy_node) {
					/* y_{nt}^k variables */
					snprintf(buf, sizeof(buf), "y_n%u_%s_%u",
						get_irn_idx(irn), na->type_info[tp_idx].tp->name, t);
1041
					na->ilp_vars.y[cur_var_y++] = lpp_add_var(lpp, buf, lpp_continous, (double)(weigth_y));
1042
					DBG((env->dbg, LEVEL_4, "\t\tcreated ILP variable %s\n", buf));
Christian Würdig's avatar
Christian Würdig committed
1043

1044
1045
1046
1047
					/* variable counter */
					n_var++;
					num_block_var++;
				}
Christian Würdig's avatar
Christian Würdig committed
1048
1049
1050
			}

			/* a node can die at any step t: asap(n) <= t <= U */
1051
1052
			if (! na->is_dummy_node) {
				for (t = na->asap - 1; t <= ba->max_steps; ++t) {
1053

1054
1055
1056
1057
					/* a_{nt}^k variables */
					snprintf(buf, sizeof(buf), "a_n%u_%s_%u",
						get_irn_idx(irn), na->type_info[tp_idx].tp->name, t);
					na->ilp_vars.a[cur_var_ad++] = lpp_add_var(lpp, buf, lpp_binary, (double)(ba->n_interesting_nodes));
1058
1059
1060
1061
1062
1063
					DBG((env->dbg, LEVEL_4, "\t\tcreated ILP variable %s\n", buf));

					/* variable counter */
					n_var++;
					num_block_var++;
				}
Christian Würdig's avatar
Christian Würdig committed
1064
			}
1065
1066
1067
1068
1069

			/* collect live-in nodes */
			for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
				ir_node *pred = get_irn_n(irn, i);

1070
				if (get_nodes_block(pred) != block_node->irn && consider_for_sched(env->arch_env, pred)) {
1071
1072
					be_ilpsched_set_type_info(env, pred, var_obst);
					if (! na->is_dummy_node) {
1073
						ilp_livein_node_t *entry = OALLOC(var_obst, ilp_livein_node_t);
1074
1075
1076
1077
1078
1079
						entry->irn = pred;
						entry->a   = NULL;
						pset_insert(ba->livein_nodes, entry, (unsigned)get_irn_idx(pred));
					}
				}
			}
Christian Würdig's avatar
Christian Würdig committed
1080
1081
1082
1083
1084
		}

		DB((env->dbg, LEVEL_3, "%u variables created\n", n_var));
		num_nodes++;
	}
1085
1086
1087
1088
1089

	/* create alive variables a_{nt}^k for live-ins */
	foreach_pset(ba->livein_nodes, livein) {
		be_ilpsched_irn_t    *node;
		ilpsched_node_attr_t *na;
1090
		unsigned             tp_idx, var_idx;
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
		ir_node              *irn;

		irn  = livein->irn;
		node = get_ilpsched_irn(env, irn);
		na   = get_ilpsched_node_attr(node);

		livein->max_alive_steps = be_ilpsched_get_max_alap_user(env, irn, block_node->irn);

		livein->a = NEW_ARR_D(int, var_obst, na->n_unit_types * livein->max_alive_steps);
		var_idx   = 0;

		/* create variables */
		for (tp_idx = 0; tp_idx < na->n_unit_types; ++tp_idx) {
			unsigned t;

			for (t = 0; t < livein->max_alive_steps; ++t) {
				/* a_{nt}^k variables */
				snprintf(buf, sizeof(buf), "al_n%u_%s_%u",
					get_irn_idx(irn), na->type_info[tp_idx].tp->name, t);
				livein->a[var_idx++] = lpp_add_var(lpp, buf, lpp_binary, (double)(ba->n_interesting_nodes));
				DBG((env->dbg, LEVEL_4, "\t\tcreated ILP variable %s\n", buf));
				num_block_var++;
			}
		}
	}

1117
	stat_ev_tim_pop("beilpsched_var");
Christian Würdig's avatar
Christian Würdig committed
1118
}
1119

Christian Würdig's avatar
Christian Würdig committed
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
/*******************************************************
 *                      _             _       _
 *                     | |           (_)     | |
 *   ___ ___  _ __  ___| |_ _ __ __ _ _ _ __ | |_ ___
 *  / __/ _ \| '_ \/ __| __| '__/ _` | | '_ \| __/ __|
 * | (_| (_) | | | \__ \ |_| | | (_| | | | | | |_\__ \
 *  \___\___/|_| |_|___/\__|_|  \__,_|_|_| |_|\__|___/
 *
 *******************************************************/

1130
1131
1132
1133
/**
 * Collect all operands and nodes @p irn depends on.
 * If there is a Proj within the dependencies, all other Projs of the parent node are added as well.
 */
1134
1135
static void sta_collect_in_deps(ir_node *irn, ir_nodeset_t *deps)
{
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
	int i;

	for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
		ir_node *p = get_irn_in_or_dep(irn, i);

		if (is_Proj(p)) {
			const ir_edge_t *edge;

			p = get_Proj_pred(p);
			foreach_out_edge(p, edge) {
				ir_node *src = get_edge_src_irn(edge);
1147
				ir_nodeset_insert(deps, src);
1148
1149
1150
			}
		}
		else {
1151
			ir_nodeset_insert(deps, p);
1152
1153
1154
1155
		}
	}
}

Christian Würdig's avatar
Christian Würdig committed
1156
1157
1158
1159
1160
1161
1162
1163
1164
/**
 * Create following ILP constraints:
 * - the assignment constraints:
 *     assure each node is executed once by exactly one (allowed) execution unit
 * - the dead node assignment constraints:
 *     assure a node can only die at most once
 * - the precedence constraints:
 *     assure that no data dependencies are violated
 */
1165
1166
static void create_assignment_and_precedence_constraints(be_ilpsched_env_t *env, lpp_t *lpp, be_ilpsched_irn_t *block_node)
{
Christian Würdig's avatar
Christian Würdig committed
1167
1168
1169
1170
1171
	unsigned              num_cst_assign, num_cst_prec, num_cst_dead;
	char                  buf[1024];
	ir_node               *irn;
	ilpsched_block_attr_t *ba            = get_ilpsched_block_attr(block_node);
	bitset_t              *bs_block_irns = bitset_alloca(ba->block_last_idx);
Christian Würdig's avatar
Christian Würdig committed
1172

Christian Würdig's avatar
Christian Würdig committed
1173
1174
	num_cst_assign = num_cst_prec = num_cst_dead = 0;
	foreach_linked_irns(ba->head_ilp_nodes, irn) {
Christian Würdig's avatar
Christian Würdig committed
1175
		int                  cst, tp_idx;
Christian Würdig's avatar
Christian Würdig committed
1176
1177
1178
		unsigned             cur_var;
		be_ilpsched_irn_t    *node;
		ilpsched_node_attr_t *na;
1179
		ir_node              *pred;
1180
1181
1182
1183
		ir_nodeset_t          deps;
		ir_nodeset_iterator_t iter;

		ir_nodeset_init(&deps);
Christian Würdig's avatar
Christian Würdig committed
1184
1185
1186
1187
1188
1189

		node    = get_ilpsched_irn(env, irn);
		na      = get_ilpsched_node_attr(node);
		cur_var = 0;

		/* the assignment constraint */
1190
		stat_ev_tim_push();
Christian Würdig's avatar
Christian Würdig committed
1191
1192
1193
1194
1195
1196
		snprintf(buf, sizeof(buf), "assignment_cst_n%u", get_irn_idx(irn));
		cst = lpp_add_cst_uniq(lpp, buf, lpp_equal, 1.0);
		DBG((env->dbg, LEVEL_2, "added constraint %s\n", buf));
		num_cst_assign++;

		lpp_set_factor_fast_bulk(lpp, cst, na->ilp_vars.x, ARR_LEN(na->ilp_vars.x), 1.0);
1197
		stat_ev_tim_pop("beilpsched_cst_assign");