beilpsched.c 69.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
34
35
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

36
37
#include "firm_config.h"

Christian Würdig's avatar
Christian Würdig committed
38
39
40
41
#ifdef WITH_ILP

#include <math.h>

Christian Würdig's avatar
Christian Würdig committed
42
43
44
45
#ifndef _WIN32
#include <strings.h>
#endif /* _WIN32 */

46
47
48
49
#include "irnode_t.h"
#include "irgwalk.h"
#include "irbitset.h"
#include "irphase_t.h"
50
#include "height.h"
51
52
#include "iredges.h"
#include "pdeq.h"
53
#include "debug.h"
Christian Würdig's avatar
Christian Würdig committed
54
#include "irtools.h"
55
#include "irdump.h"
Matthias Braun's avatar
Matthias Braun committed
56
#include "irprintf.h"
57
#include "plist.h"
Christian Würdig's avatar
Christian Würdig committed
58
#include "irprintf.h"
Christian Würdig's avatar
Christian Würdig committed
59
60
61

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

63
64
65
66
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>

67
68
#include "be.h"
#include "benode_t.h"
69
#include "besched_t.h"
70
#include "beilpsched.h"
71
#include "beutil.h"
Christian Würdig's avatar
Christian Würdig committed
72
#include "bestat.h"
73
#include "beirg_t.h"
Christian Würdig's avatar
Christian Würdig committed
74
#include "benodesets.h"
75

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

82
83
84
85
86
typedef struct _unit_type_info_t {
	int                            n_units;
	const be_execution_unit_type_t *tp;
} unit_type_info_t;

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

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

Christian Würdig's avatar
Christian Würdig committed
105
/* attributes for a node */
106
typedef struct _ilpsched_node_attr_t {
Christian Würdig's avatar
Christian Würdig committed
107
108
	unsigned asap;                     /**< The ASAP scheduling control step */
	unsigned alap;                     /**< The ALAP scheduling control step */
109
	unsigned latency;                  /**< Latency of this node (needed for sorting) */
Christian Würdig's avatar
Christian Würdig committed
110
111
	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
112
113
114
	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 */
115
	waitq    *projkeeps;               /**< A List of Projs and Keeps belonging to this node */
116
117
118
	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
119
120
	bitset_t *transitive_block_nodes;  /**< Set of transitive block nodes (predecessors
											for ASAP, successors for ALAP */
121
	unsigned         n_unit_types;     /**< number of allowed execution unit types */
122
	unit_type_info_t *type_info;       /**< list of allowed execution unit types */
Christian Würdig's avatar
Christian Würdig committed
123
	ilp_var_types_t  ilp_vars;         /**< the different ILP variables */
124
125
} ilpsched_node_attr_t;

Christian Würdig's avatar
Christian Würdig committed
126
/* attributes for a block */
127
typedef struct _ilpsched_block_attr_t {
Christian Würdig's avatar
Christian Würdig committed
128
129
	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
130
	unsigned max_steps;             /**< Upper bound for block execution */
131
	plist_t  *root_nodes;           /**< A list of nodes having no user in current block */
Christian Würdig's avatar
Christian Würdig committed
132
	ir_node  *head_ilp_nodes;       /**< A linked list of nodes which will contribute to ILP */
133
	pset     *livein_nodes;         /**< A set of nodes which are live-in to this block */
134
135
136
137
138
139
140
} ilpsched_block_attr_t;

typedef union _ilpsched_attr_ {
	ilpsched_node_attr_t  node_attr;
	ilpsched_block_attr_t block_attr;
} ilpsched_attr_t;

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

147
/* The ILP scheduling environment */
148
typedef struct {
149
	ir_phase             ph;            /**< The phase */
150
151
152
153
154
155
156
157
158
	ir_graph             *irg;          /**< The current irg */
	heights_t            *height;       /**< The heights object of the irg */
	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 arch_isa_t     *isa;          /**< The ISA */
	const be_main_env_t  *main_env;
	const be_machine_t   *cpu;          /**< the current abstract machine */
	ilpsched_options_t   *opts;         /**< the ilp options for current irg */
159
160
	const be_irg_t       *birg;         /**< The birg object */
	be_options_t         *be_opts;      /**< backend options */
161
	const ilp_sched_selector_t *sel;    /**< The ILP sched selector provided by the backend */
162
163
164
	DEBUG_ONLY(firm_dbg_module_t *dbg);
} be_ilpsched_env_t;

165
/* convenience macros to handle phase irn data */
166
167
168
169
170
#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)

171
/* check if node is considered for ILP scheduling */
172
173
174
175
176
#define consider_for_sched(isa, irn) \
	(! (is_Block(irn)            ||  \
		is_normal_Proj(isa, irn) ||  \
		is_Phi(irn)              ||  \
		is_NoMem(irn)            ||  \
Christian Würdig's avatar
Christian Würdig committed
177
		is_Unknown(irn)          ||  \
178
		is_End(irn)                  \
179
180
181
		))

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

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

187
/* gives the corresponding ILP variable for given node, unit and time step */
Christian Würdig's avatar
Christian Würdig committed
188
189
190
#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
191
192
193
194
/* 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)

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

198
199
200
#define ilp_timer_push(t)         lc_timer_push((t))
#define ilp_timer_pop()           lc_timer_pop()
#define ilp_timer_elapsed_usec(t) lc_timer_elapsed_usec((t))
Christian Würdig's avatar
Christian Würdig committed
201

202
/* option variable */
Christian Würdig's avatar
Christian Würdig committed
203
static ilpsched_options_t ilp_opts = {
204
	1,     /* default is with register pressure constraints */
Christian Würdig's avatar
Christian Würdig committed
205
	300,   /* 300 sec per block time limit */
Christian Würdig's avatar
Christian Würdig committed
206
207
	""     /* no log file */
};
208

209
/* ILP options */
Christian Würdig's avatar
Christian Würdig committed
210
static const lc_opt_table_entry_t ilpsched_option_table[] = {
211
	LC_OPT_ENT_BOOL("regpress",  "Use register pressure constraints", &ilp_opts.regpress),
Christian Würdig's avatar
Christian Würdig committed
212
213
	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)),
214
	LC_OPT_LAST
Christian Würdig's avatar
Christian Würdig committed
215
};
216

217
218
219
220
221
222
/*
	We need this global variable as we compare nodes dependent on heights,
	but we cannot pass any information to the qsort compare function.
*/
static heights_t *glob_heights;

223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
/**
 * 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
 */
static INLINE int is_normal_Proj(const arch_isa_t *isa, const ir_node *irn) {
	return is_Proj(irn) && (arch_isa_get_allowed_execution_units(isa, irn) == NULL);
}

/**
 * Skips normal Projs.
 * @return predecessor if irn is a normal Proj, otherwise irn.
 */
static INLINE ir_node *skip_normal_Proj(const arch_isa_t *isa, ir_node *irn) {
	if (is_normal_Proj(isa, irn))
		return get_Proj_pred(irn);
	return irn;
}

241
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
242
243
244
245
246
247
	unsigned lat = be_ilp_sched_latency(sel, irn, env);
	if (lat == 0 && ! is_Proj(irn) && ! be_is_Keep(irn))
		lat = 1;
	return lat;
}

248
249
250
251
252
253
static int cmp_live_in_nodes(const void *a, const void *b) {
	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
254

255
256
257
258
259
260
261
262
263
/**
 * Compare scheduling time steps of two be_ilpsched_irn's.
 */
static int cmp_ilpsched_irn(const void *a, const void *b) {
	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);

264
265
266
267
268
269
270
271
	if (n1_a->sched_point == n2_a->sched_point) {
		ir_node *irn_a = n1->irn;
		ir_node *irn_b = n2->irn;

		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;
272
273
274
275
276
277

		/*
			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);
278
279
280
	}
	else
		return QSORT_CMP(n1_a->sched_point, n2_a->sched_point);
281
282
}

283
284
285
/**
 * In case there is no phase information for irn, initialize it.
 */
286
static void *init_ilpsched_irn(ir_phase *ph, ir_node *irn, void *old) {
287
288
289
	be_ilpsched_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));

	if (res == old) {
290
291
		/* if we have already some data: check for reinitialization */

Christian Würdig's avatar
Christian Würdig committed
292
		if (! is_Block(irn)) {
293
			ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
Christian Würdig's avatar
Christian Würdig committed
294
295
296
297
298
299

			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);

300
				/* we are called after the block indices have been build: create bitset */
Christian Würdig's avatar
Christian Würdig committed
301
302
303
304
305
				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);
306
307
				na->visit_idx    = 0;
				na->alap_changed = 1;
Christian Würdig's avatar
Christian Würdig committed
308
			}
309
310
311
312
313
314
		}
		return old;
	}

	res->irn = irn;

315
	/* set ilpsched irn attributes (either block or irn) */
316
317
318
319
	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
320
		ba->block_last_idx      = 0;
321
		ba->root_nodes          = plist_new();
Christian Würdig's avatar
Christian Würdig committed
322
		ba->head_ilp_nodes      = NULL;
323
		ba->livein_nodes        = new_pset(cmp_live_in_nodes, 16);
Christian Würdig's avatar
Christian Würdig committed
324
		ba->max_steps           = 0;
325
326
327
	}
	else {
		ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
Christian Würdig's avatar
Christian Würdig committed
328
		memset(na, 0, sizeof(*na));
329
330
331
332
333
	}

	return res;
}

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

343
	set_irn_link(irn, NULL);
344
	if (! consider_for_sched(env->arch_env->isa, irn))
Christian Würdig's avatar
Christian Würdig committed
345
346
347
348
349
350
351
352
353
354
		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++;
}

355
356
357
358
359
360
361
362
363
364
365
/********************************************************
 *                              __        _
 *                             / /       | |
 *   __ _ ___  __ _ _ __      / /    __ _| | __ _ _ __
 *  / _` / __|/ _` | '_ \    / /    / _` | |/ _` | '_ \
 * | (_| \__ \ (_| | |_) |  / /    | (_| | | (_| | |_) |
 *  \__,_|___/\__,_| .__/  /_/      \__,_|_|\__,_| .__/
 *                 | |                           | |
 *                 |_|                           |_|
 ********************************************************/

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

383
	if (! consider_for_sched(env->arch_env->isa, irn))
384
385
		return;

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

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

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

397
			if (is_normal_Proj(env->arch_env->isa, user)) {
Christian Würdig's avatar
Christian Würdig committed
398
				const ir_edge_t *user_edge;
399

Christian Würdig's avatar
Christian Würdig committed
400
401
				if (get_irn_mode(user) == mode_X)
					continue;
402

Christian Würdig's avatar
Christian Würdig committed
403
404
405
406
407
				/* 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);

408
						if (! is_Phi(real_user) && ! is_Block(real_user)) {
Christian Würdig's avatar
Christian Würdig committed
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
							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
429
430
						}
					}
431
				}
Christian Würdig's avatar
Christian Würdig committed
432
433
434
435
			}
			else if (is_Block(user)) {
				continue;
			}
436
			else if (! is_Phi(user)) {
Christian Würdig's avatar
Christian Würdig committed
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
				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
457
			}
458
459
460
			else if (get_nodes_block(user) != block) {
				n_consumer++;
			}
461
462
463
464
465
466
467
468
		}
	}

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

	/* 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);
485
486
}

487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
/**
 * Calculate the ASAP scheduling step for current irn.
 */
static void calculate_irn_asap(ir_node *irn, void *walk_env) {
	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 */
	if (! consider_for_sched(env->arch_env->isa, irn))
		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) {
		ir_node *pred = skip_normal_Proj(env->arch_env->isa, get_irn_in_or_dep(irn, i));

		/* 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;

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

	/* 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;
530
	ba->max_steps     += fixed_latency(env->sel, irn, env->block_env);
531
532
533
534
535
536
537
538
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
582
583
584
585
586
587
588
589
590
591
592
593
594
595

	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.
 */
static void calculate_block_alap(ir_node *block, void *walk_env) {
	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) {
				ir_node *pred = skip_normal_Proj(env->arch_env->isa, get_irn_in_or_dep(cur_irn, i));

				/* 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
596
					lat = fixed_latency(env->sel, pred, env->block_env);
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
629

					/* 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;
	}
}

/**
630
 * Free list of root nodes and the set of live-in nodes.
631
632
633
634
635
636
637
638
 */
static void clear_unwanted_data(ir_node *block, void *walk_env) {
	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
647
}

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

	if (! consider_for_sched(env->arch_env->isa, irn))
		return;

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

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

	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;

672
673
674
675
	/* 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
676

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

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

690
691
692
693
694
695
696
697
698
699
700
701
702
static INLINE void check_for_keeps(waitq *keeps, ir_node *block, ir_node *irn) {
	const ir_edge_t *edge;

	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);
		}
	}
}

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

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

Christian Würdig's avatar
Christian Würdig committed
721
	/* mode_M nodes are not scheduled */
722
723
724
	if (get_irn_mode(irn) == mode_M)
		return;

725
726
	if (! sched_is_scheduled(irn))
		notified_sched_add_before(env, block, irn, cycle);
727
728
729
730
731
732

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

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

			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))
750
			notified_sched_add_before(env, block, keep, cycle);
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
	}

	del_waitq(keeps);
}

/**
 * Schedule all nodes in the given block, according to the ILP solution.
 */
static void apply_solution(be_ilpsched_env_t *env, lpp_t *lpp, ir_node *block) {
	be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
	ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
	sched_info_t          *info       = get_irn_sched_info(block);
	be_ilpsched_irn_t     **sched_nodes;
	unsigned              i, l;
	ir_node               *cfop, *irn;
	const ir_edge_t       *edge;

	/* init block schedule list */
	INIT_LIST_HEAD(&info->list);
	info->scheduled = 1;

	/* 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
784
		/* check all nodes for their positive solution */
785
786
787
788
789
790
791
792
793
794
795
		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;

796
797
798
799
800
801
			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)) {
802
							DBG((env->dbg, LEVEL_3, "%+F has additional regpressure costs of %f\n", irn, cost));
803
804
805
806
807
808
809
							found = 1;
						}
					}
				}
			}

			found = 0;
Christian Würdig's avatar
Christian Würdig committed
810
			/* go over all variables of a node until the non-zero one is found */
811
812
			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
813
814
815
					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 :) */
816
817
818
					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
819
						DBG((env->dbg, LEVEL_2, "Schedpoint of %+F is %u at unit type %s\n",
820
821
822
823
824
825
826
							irn, t, na->type_info[tp_idx].tp->name));
						found = 1;
					}
				}
			}
		}

827
		glob_heights = env->height;
828
829
830
831
832
833
834
835
836
837
838
		/* 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:
839
				add_to_sched(env, block, irn, 0);
840
841
842
843
844
				break;
			case iro_Start:
			case iro_End:
			case iro_Proj:
			case iro_Bad:
Christian Würdig's avatar
Christian Würdig committed
845
			case iro_Unknown:
846
847
848
				break;
			default:
				if (is_cfop(irn)) {
Christian Würdig's avatar
Christian Würdig committed
849
					assert(cfop == NULL && "Highlander - there can be only one");
850
851
852
853
854
855
856
857
					cfop = irn;
				}
			break;
		}
	}

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

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

	DEL_ARR_F(sched_nodes);
}

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

Christian Würdig's avatar
Christian Würdig committed
880
/**
Christian Würdig's avatar
Christian Würdig committed
881
 * Check if node can be executed on given unit type.
Christian Würdig's avatar
Christian Würdig committed
882
 */
Christian Würdig's avatar
Christian Würdig committed
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
static INLINE int is_valid_unit_type_for_node(const be_execution_unit_type_t *tp, be_ilpsched_irn_t *node) {
	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 / (_| | |  | | (_| | |_) | |  __/\__ \
 *    \_/ \__,_|_|  |_|\__,_|_.__/|_|\___||___/
 *
 ************************************************/

905
906
907
908
909
910
911
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
948
949
950
951
952
953
954
955
956
957
958
959
960
961
static int be_ilpsched_set_type_info(be_ilpsched_env_t *env, ir_node *irn, struct obstack *obst) {
	const be_execution_unit_t ***execunits = arch_isa_get_allowed_execution_units(env->arch_env->isa, irn);
	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.
 */
static unsigned be_ilpsched_get_max_alap_user(be_ilpsched_env_t *env, ir_node *irn, ir_node *block) {
	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
962
963
964
965
966
967
/**
 * 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
 *
968
969
 * - 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
970
 *
971
972
 * - 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
973
 * ==>> These variables represent the register pressure
974
 *
Christian Würdig's avatar
Christian Würdig committed
975
976
 */
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
977
	char                  buf[1024];
Christian Würdig's avatar
Christian Würdig committed
978
979
	ir_node               *irn;
	unsigned              num_block_var, num_nodes;
980
	ilp_livein_node_t     *livein;
Christian Würdig's avatar
Christian Würdig committed
981
982
983
984
985
986
987
	ilpsched_block_attr_t *ba      = get_ilpsched_block_attr(block_node);
	unsigned              weigth_y = ba->n_interesting_nodes * ba->n_interesting_nodes;
	lc_timer_t            *t_var   = lc_timer_register("beilpsched_var", "create ilp variables");

	ilp_timer_push(t_var);
	num_block_var = num_nodes = 0;
	foreach_linked_irns(ba->head_ilp_nodes, irn) {
988
989
990
991
992
		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
993

994
995
996
		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
997
998
999
1000

		/* 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]));
For faster browsing, not all history is shown. View entire blame