bechordal_main.c 18.6 KB
Newer Older
Sebastian Hack's avatar
Sebastian Hack committed
1
2
3
4
/**
 * @file   bechordal_main.c
 * @date   29.11.2005
 * @author Sebastian Hack
Christian Würdig's avatar
Christian Würdig committed
5
 * @cvs-id $Id$
Sebastian Hack's avatar
Sebastian Hack committed
6
7
8
9
10
11
 *
 * Copyright (C) 2005 Universitaet Karlsruhe
 * Released under the GPL
 *
 * Driver for the chordal register allocator.
 */
Christian Würdig's avatar
Christian Würdig committed
12
13
14
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
Sebastian Hack's avatar
Sebastian Hack committed
15
16
17
18
19
20

#include "obst.h"
#include "pset.h"
#include "list.h"
#include "bitset.h"
#include "iterator.h"
21
#include "firm_config.h"
Sebastian Hack's avatar
Sebastian Hack committed
22
23
24
25

#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
26
#include <libcore/lc_timing.h>
Christian Würdig's avatar
Christian Würdig committed
27
#endif /* WITH_LIBCORE */
Sebastian Hack's avatar
Sebastian Hack committed
28
29
30
31
32

#include "irmode_t.h"
#include "irgraph_t.h"
#include "irprintf_t.h"
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
33
#include "ircons.h"
Sebastian Hack's avatar
Sebastian Hack committed
34
35
#include "irdump.h"
#include "irdom.h"
Christian Würdig's avatar
Christian Würdig committed
36
#include "ircons.h"
Sebastian Hack's avatar
Sebastian Hack committed
37
#include "irbitset.h"
38
39
#include "irnode.h"
#include "ircons.h"
Sebastian Hack's avatar
Sebastian Hack committed
40
41
#include "debug.h"
#include "xmalloc.h"
Sebastian Hack's avatar
Sebastian Hack committed
42
#include "execfreq.h"
Sebastian Hack's avatar
Sebastian Hack committed
43
44

#include "bechordal_t.h"
45
#include "beabi.h"
Sebastian Hack's avatar
Sebastian Hack committed
46
#include "bejavacoal.h"
Sebastian Hack's avatar
Sebastian Hack committed
47
48
49
50
51
52
#include "beutil.h"
#include "besched.h"
#include "benumb_t.h"
#include "besched_t.h"
#include "belive_t.h"
#include "bearch.h"
53
#include "beifg_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
54
#include "beifg_impl.h"
Christian Würdig's avatar
Christian Würdig committed
55
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
56
57

#include "bespillbelady.h"
58
#include "bespillmorgan.h"
Matthias Braun's avatar
Matthias Braun committed
59
#include "bespillslots.h"
60
61
#include "belower.h"

Christian Würdig's avatar
Christian Würdig committed
62
#ifdef WITH_ILP
63
#include "bespillremat.h"
Christian Würdig's avatar
Christian Würdig committed
64
65
#endif /* WITH_ILP */

66
#include "bejavacoal.h"
Daniel Grund's avatar
Daniel Grund committed
67
#include "becopystat.h"
Daniel Grund's avatar
Daniel Grund committed
68
#include "becopyopt.h"
Christian Würdig's avatar
Christian Würdig committed
69
#include "bessadestr.h"
70
#include "beverify.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
71
#include "bespillcost.h"
72
#include "benode_t.h"
Christian Würdig's avatar
Christian Würdig committed
73

Sebastian Hack's avatar
Sebastian Hack committed
74
void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
Sebastian Hack's avatar
Sebastian Hack committed
75
	const arch_env_t *arch_env = chordal_env->birg->main_env->arch_env;
Sebastian Hack's avatar
Sebastian Hack committed
76
77
78
79
	struct obstack ob;
	pmap_entry *pme;
	ir_node **nodes, *n1, *n2;
	int i, o;
80
	DEBUG_ONLY(firm_dbg_module_t *dbg = chordal_env->dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

	/* Collect all irns */
	obstack_init(&ob);
	pmap_foreach(chordal_env->border_heads, pme) {
		border_t *curr;
		struct list_head *head = pme->value;
		list_for_each_entry(border_t, curr, head, list)
			if (curr->is_def && curr->is_real)
				if (arch_get_irn_reg_class(arch_env, curr->irn, -1) == chordal_env->cls)
					obstack_ptr_grow(&ob, curr->irn);
	}
	obstack_ptr_grow(&ob, NULL);
	nodes = (ir_node **) obstack_finish(&ob);

	/* Check them */
	for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
		const arch_register_t *n1_reg, *n2_reg;

		n1_reg = arch_get_irn_register(arch_env, n1);
		if (!arch_reg_is_allocatable(arch_env, n1, -1, n1_reg)) {
101
			DBG((dbg, 0, "Register %s assigned to %+F is not allowed\n", n1_reg->name, n1));
Daniel Grund's avatar
:wq    
Daniel Grund committed
102
			assert(0 && "Register constraint does not hold");
Sebastian Hack's avatar
Sebastian Hack committed
103
104
105
		}
		for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) {
			n2_reg = arch_get_irn_register(arch_env, n2);
Sebastian Hack's avatar
Sebastian Hack committed
106
			if (values_interfere(chordal_env->lv, n1, n2) && n1_reg == n2_reg) {
107
				DBG((dbg, 0, "Values %+F and %+F interfere and have the same register assigned: %s\n", n1, n2, n1_reg->name));
Sebastian Hack's avatar
Sebastian Hack committed
108
109
110
111
112
113
114
115
116
117
118
119
				assert(0 && "Interfering values have the same color!");
			}
		}
	}
	obstack_free(&ob, NULL);
}

int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
{
	if(env->ifg)
		return be_ifg_connected(env->ifg, a, b);
	else
Sebastian Hack's avatar
Sebastian Hack committed
120
		return values_interfere(env->lv, a, b);
Sebastian Hack's avatar
Sebastian Hack committed
121
122
123
124
}


static be_ra_chordal_opts_t options = {
Sebastian Hack's avatar
Sebastian Hack committed
125
	BE_CH_DUMP_NONE,
126
	BE_CH_SPILL_BELADY,
127
	BE_CH_IFG_STD,
Christian Würdig's avatar
Christian Würdig committed
128
	BE_CH_LOWER_PERM_SWAP,
Christian Würdig's avatar
Christian Würdig committed
129
	BE_CH_VRFY_WARN,
Sebastian Hack's avatar
Sebastian Hack committed
130
131
};

132
133
134
135
136
137
138
139
140
static be_ra_timer_t ra_timer = {
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
Christian Würdig's avatar
Christian Würdig committed
141
142
	NULL,
	NULL,
143
	NULL,
144
145
};

Sebastian Hack's avatar
Sebastian Hack committed
146
147
#ifdef WITH_LIBCORE
static const lc_opt_enum_int_items_t spill_items[] = {
148
	{ "morgan", BE_CH_SPILL_MORGAN },
Sebastian Hack's avatar
Sebastian Hack committed
149
	{ "belady", BE_CH_SPILL_BELADY },
Christian Würdig's avatar
Christian Würdig committed
150
#ifdef WITH_ILP
Sebastian Hack's avatar
Sebastian Hack committed
151
	{ "remat",  BE_CH_SPILL_REMAT },
152
#endif /* WITH_ILP */
Sebastian Hack's avatar
Sebastian Hack committed
153
154
155
156
	{ NULL, 0 }
};

static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
157
158
159
160
161
162
163
	{ "std",     BE_CH_IFG_STD     },
	{ "fast",    BE_CH_IFG_FAST    },
	{ "clique",  BE_CH_IFG_CLIQUE  },
	{ "pointer", BE_CH_IFG_POINTER },
	{ "list",    BE_CH_IFG_LIST    },
	{ "check",   BE_CH_IFG_CHECK   },
	{ NULL,      0                 }
Sebastian Hack's avatar
Sebastian Hack committed
164
165
};

166
167
static const lc_opt_enum_int_items_t lower_perm_items[] = {
	{ "copy", BE_CH_LOWER_PERM_COPY },
168
169
170
171
172
	{ "swap", BE_CH_LOWER_PERM_SWAP },
	{ NULL, 0 }
};

static const lc_opt_enum_int_items_t lower_perm_stat_items[] = {
173
174
175
	{ NULL, 0 }
};

Sebastian Hack's avatar
Sebastian Hack committed
176
static const lc_opt_enum_int_items_t dump_items[] = {
Matthias Braun's avatar
Matthias Braun committed
177
178
179
180
181
182
183
184
185
186
187
	{ "spill",      BE_CH_DUMP_SPILL      },
	{ "live",       BE_CH_DUMP_LIVE       },
	{ "color",      BE_CH_DUMP_COLOR      },
	{ "copymin",    BE_CH_DUMP_COPYMIN    },
	{ "ssadestr",   BE_CH_DUMP_SSADESTR   },
	{ "tree",       BE_CH_DUMP_TREE_INTV  },
	{ "constr",     BE_CH_DUMP_CONSTR     },
	{ "lower",      BE_CH_DUMP_LOWER      },
	{ "spillslots", BE_CH_DUMP_SPILLSLOTS },
	{ "appel",      BE_CH_DUMP_APPEL      },
	{ "all",        BE_CH_DUMP_ALL        },
Christian Würdig's avatar
Christian Würdig committed
188
189
190
191
192
193
194
	{ NULL, 0 }
};

static const lc_opt_enum_int_items_t be_ch_vrfy_items[] = {
	{ "off",    BE_CH_VRFY_OFF    },
	{ "warn",   BE_CH_VRFY_WARN   },
	{ "assert", BE_CH_VRFY_ASSERT },
Sebastian Hack's avatar
Sebastian Hack committed
195
196
197
	{ NULL, 0 }
};

Sebastian Hack's avatar
Sebastian Hack committed
198
199
200
201
202
static lc_opt_enum_int_var_t spill_var = {
	&options.spill_method, spill_items
};

static lc_opt_enum_int_var_t ifg_flavor_var = {
203
	&options.ifg_flavor, ifg_flavor_items
Sebastian Hack's avatar
Sebastian Hack committed
204
205
};

206
static lc_opt_enum_int_var_t lower_perm_var = {
207
	&options.lower_perm_opt, lower_perm_items
208
209
};

Sebastian Hack's avatar
Sebastian Hack committed
210
211
212
213
static lc_opt_enum_int_var_t dump_var = {
	&options.dump_flags, dump_items
};

Christian Würdig's avatar
Christian Würdig committed
214
215
216
217
static lc_opt_enum_int_var_t be_ch_vrfy_var = {
	&options.vrfy_option, be_ch_vrfy_items
};

Sebastian Hack's avatar
Sebastian Hack committed
218
219
220
/** Enable extreme live range splitting. */
static int be_elr_split = 0;

Sebastian Hack's avatar
Sebastian Hack committed
221
222
223
/** Assumed loop iteration count for execution frequency estimation. */
static int be_loop_weight = 9;

224
static const lc_opt_table_entry_t be_chordal_options[] = {
225
	LC_OPT_ENT_ENUM_INT ("spill",	      "spill method (belady, morgan or remat)", &spill_var),
Sebastian Hack's avatar
Sebastian Hack committed
226
227
228
229
	LC_OPT_ENT_ENUM_PTR ("ifg",           "interference graph flavour (std, fast, clique, pointer, list, check)", &ifg_flavor_var),
	LC_OPT_ENT_ENUM_PTR ("perm",          "perm lowering options (copy or swap)", &lower_perm_var),
	LC_OPT_ENT_ENUM_MASK("dump",          "select dump phases", &dump_var),
	LC_OPT_ENT_ENUM_PTR ("vrfy",          "verify options (off, warn, assert)", &be_ch_vrfy_var),
Sebastian Hack's avatar
Sebastian Hack committed
230
	LC_OPT_ENT_BOOL     ("elrsplit",      "enable extreme live range splitting", &be_elr_split),
Sebastian Hack's avatar
Sebastian Hack committed
231
	LC_OPT_ENT_INT      ("loop_weight",   "assumed amount of loop iterations for guessing the execution frequency", &be_loop_weight),
232
233
234
	{ NULL }
};

Sebastian Hack's avatar
Sebastian Hack committed
235
236
static void be_ra_chordal_register_options(lc_opt_entry_t *grp)
{
237
238
239
240
241
242
243
244
245
	static int run_once = 0;
	lc_opt_entry_t *chordal_grp;

	if (! run_once) {
		run_once    = 1;
		chordal_grp = lc_opt_get_grp(grp, "chordal");

		lc_opt_add_table(chordal_grp, be_chordal_options);
	}
Sebastian Hack's avatar
Sebastian Hack committed
246
247

	co_register_options(chordal_grp);
248
	be_java_coal_register_options(chordal_grp);
Sebastian Hack's avatar
Sebastian Hack committed
249
}
Christian Würdig's avatar
Christian Würdig committed
250
#endif /* WITH_LIBCORE */
Sebastian Hack's avatar
Sebastian Hack committed
251

Sebastian Hack's avatar
Sebastian Hack committed
252
static void dump(unsigned mask, ir_graph *irg,
253
254
255
				 const arch_register_class_t *cls,
				 const char *suffix,
				 void (*dump_func)(ir_graph *, const char *))
Sebastian Hack's avatar
Sebastian Hack committed
256
{
Christian Würdig's avatar
Christian Würdig committed
257
258
	if((options.dump_flags & mask) == mask) {
		if (cls) {
259
260
			char buf[256];
			snprintf(buf, sizeof(buf), "-%s%s", cls->name, suffix);
Christian Würdig's avatar
Christian Würdig committed
261
			be_dump(irg, buf, dump_func);
262
263
		}
		else
Christian Würdig's avatar
Christian Würdig committed
264
			be_dump(irg, suffix, dump_func);
265
	}
Sebastian Hack's avatar
Sebastian Hack committed
266
267
}

268
269
270
271
272
273
274
275
276
277
278
279
static void put_ignore_colors(be_chordal_env_t *chordal_env)
{
	int n_colors = chordal_env->cls->n_regs;
	int i;

	bitset_clear_all(chordal_env->ignore_colors);
	be_abi_put_ignore_regs(chordal_env->birg->abi, chordal_env->cls, chordal_env->ignore_colors);
	for(i = 0; i < n_colors; ++i)
		if(arch_register_type_is(&chordal_env->cls->regs[i], ignore))
			bitset_set(chordal_env->ignore_colors, i);
}

Sebastian Hack's avatar
Sebastian Hack committed
280
281
282
283
FILE *be_chordal_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
{
	char buf[1024];

Sebastian Hack's avatar
Sebastian Hack committed
284
	ir_snprintf(buf, sizeof(buf), "%s%F_%s%s", prefix, env->irg, env->cls->name, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
285
286
287
	return fopen(buf, "wt");
}

288
289
290
291
void check_ifg_implementations(be_chordal_env_t *chordal_env)
{
	FILE *f;

Sebastian Hack's avatar
Sebastian Hack committed
292
	f = be_chordal_open(chordal_env, "std", ".log");
293
	chordal_env->ifg = be_ifg_std_new(chordal_env);
294
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
295
296
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
297
	f = be_chordal_open(chordal_env, "list", ".log");
298
	be_ifg_free(chordal_env->ifg);
299
	chordal_env->ifg = be_ifg_list_new(chordal_env);
300
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
301
302
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
303
	f = be_chordal_open(chordal_env, "clique", ".log");
304
	be_ifg_free(chordal_env->ifg);
305
	chordal_env->ifg = be_ifg_clique_new(chordal_env);
306
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
307
308
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
309
	f = be_chordal_open(chordal_env, "pointer", ".log");
310
	be_ifg_free(chordal_env->ifg);
311
	chordal_env->ifg = be_ifg_pointer_new(chordal_env);
312
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
313
	fclose(f);
314

315
316
317
	chordal_env->ifg = NULL;
};

Christian Würdig's avatar
Christian Würdig committed
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
/**
 * Checks for every reload if it's user can perform the load on itself.
 */
static void memory_operand_walker(ir_node *irn, void *env) {
	be_chordal_env_t *cenv = env;
	const arch_env_t *aenv = cenv->birg->main_env->arch_env;
	const ir_edge_t  *edge, *ne;
	ir_node          *block;

	if (! be_is_Reload(irn))
		return;

	block = get_nodes_block(irn);

	foreach_out_edge_safe(irn, edge, ne) {
		ir_node *src = get_edge_src_irn(edge);
		int     pos  = get_edge_src_pos(edge);

		if (! src)
			continue;

		if (get_nodes_block(src) == block && arch_possible_memory_operand(aenv, src, pos)) {
			DBG((cenv->dbg, LEVEL_3, "performing memory operand %+F at %+F\n", irn, src));
			arch_perform_memory_operand(aenv, src, irn, pos);
		}
	}

	/* kill the Reload */
	if (get_irn_n_edges(irn) == 0) {
		sched_remove(irn);
		set_irn_n(irn, 0, new_Bad());
		set_irn_n(irn, 1, new_Bad());
	}
}

/**
 * Starts a walk for memory operands if supported by the backend.
 */
static INLINE void check_for_memory_operands(be_chordal_env_t *chordal_env) {
	irg_walk_graph(chordal_env->irg, NULL, memory_operand_walker, chordal_env);
}

Christian Würdig's avatar
Christian Würdig committed
360
361
362
363
364
365
/**
 * Performs chordal register allocation for each register class on given irg.
 *
 * @param bi  Backend irg object
 * @return Structure containing timer for the single phases or NULL if no timing requested.
 */
366
static be_ra_timer_t *be_ra_chordal_main(const be_irg_t *bi)
Sebastian Hack's avatar
Sebastian Hack committed
367
{
368
369
370
371
	const be_main_env_t *main_env  = bi->main_env;
	const arch_isa_t    *isa       = arch_env_get_isa(main_env->arch_env);
	ir_graph            *irg       = bi->irg;
	be_options_t        *main_opts = main_env->options;
Sebastian Hack's avatar
Sebastian Hack committed
372
	int                  splitted  = 0;
373

Sebastian Hack's avatar
Sebastian Hack committed
374
375
376
	int j, m;
	be_chordal_env_t chordal_env;

377
	if (main_opts->timing == BE_TIME_ON) {
Christian Würdig's avatar
Christian Würdig committed
378
379
380
381
		ra_timer.t_prolog  = lc_timer_register("ra_prolog",   "regalloc prolog");
		ra_timer.t_epilog  = lc_timer_register("ra_epilog",   "regalloc epilog");
		ra_timer.t_live    = lc_timer_register("ra_liveness", "be liveness");
		ra_timer.t_spill   = lc_timer_register("ra_spill",    "spiller");
Matthias Braun's avatar
Matthias Braun committed
382
		ra_timer.t_spillslots = lc_timer_register("ra_spillslots",    "spillslots");
Christian Würdig's avatar
Christian Würdig committed
383
384
385
386
387
388
		ra_timer.t_color   = lc_timer_register("ra_color",    "graph coloring");
		ra_timer.t_ifg     = lc_timer_register("ra_ifg",      "interference graph");
		ra_timer.t_copymin = lc_timer_register("ra_copymin",  "copy minimization");
		ra_timer.t_ssa     = lc_timer_register("ra_ssadestr", "ssa destruction");
		ra_timer.t_verify  = lc_timer_register("ra_verify",   "graph verification");
		ra_timer.t_other   = lc_timer_register("ra_other",    "other time");
389
390
391
392
393

		LC_STOP_AND_RESET_TIMER(ra_timer.t_prolog);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_epilog);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_live);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_spill);
394
		LC_STOP_AND_RESET_TIMER(ra_timer.t_spillslots);
395
396
397
398
		LC_STOP_AND_RESET_TIMER(ra_timer.t_color);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_ifg);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_copymin);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_ssa);
Christian Würdig's avatar
Christian Würdig committed
399
400
		LC_STOP_AND_RESET_TIMER(ra_timer.t_verify);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_other);
401
402
	}

Christian Würdig's avatar
Christian Würdig committed
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
#define BE_TIMER_PUSH(timer)                                                        \
	if (main_opts->timing == BE_TIME_ON) {                                          \
		int res = lc_timer_push(timer);                                             \
		if (options.vrfy_option == BE_CH_VRFY_ASSERT)                               \
			assert(res && "Timer already on stack, cannot be pushed twice.");       \
		else if (options.vrfy_option == BE_CH_VRFY_WARN && ! res)                   \
			fprintf(stderr, "Timer %s already on stack, cannot be pushed twice.\n", \
				lc_timer_get_name(timer));                                          \
	}
#define BE_TIMER_POP(timer)                                                                    \
	if (main_opts->timing == BE_TIME_ON) {                                                     \
		lc_timer_t *tmp = lc_timer_pop();                                                      \
		if (options.vrfy_option == BE_CH_VRFY_ASSERT)                                          \
			assert(tmp == timer && "Attempt to pop wrong timer.");                             \
		else if (options.vrfy_option == BE_CH_VRFY_WARN && tmp != timer)                       \
			fprintf(stderr, "Attempt to pop wrong timer. %s is on stack, trying to pop %s.\n", \
				lc_timer_get_name(tmp), lc_timer_get_name(timer));                             \
		timer = tmp;                                                                           \
	}
422

Christian Würdig's avatar
Christian Würdig committed
423
424
	BE_TIMER_PUSH(ra_timer.t_other);
	BE_TIMER_PUSH(ra_timer.t_prolog);
425

Sebastian Hack's avatar
Sebastian Hack committed
426
427
	compute_doms(irg);

Sebastian Hack's avatar
Sebastian Hack committed
428
429
430
431
432
	chordal_env.opts      = &options;
	chordal_env.irg       = irg;
	chordal_env.birg      = bi;
	chordal_env.dom_front = be_compute_dominance_frontiers(irg);
	chordal_env.exec_freq = compute_execfreq(irg, be_loop_weight);
Sebastian Hack's avatar
Sebastian Hack committed
433
	chordal_env.lv        = be_liveness(irg);
434
	FIRM_DBG_REGISTER(chordal_env.dbg, "firm.be.chordal");
Sebastian Hack's avatar
Sebastian Hack committed
435
436
437

	obstack_init(&chordal_env.obst);

Christian Würdig's avatar
Christian Würdig committed
438
	BE_TIMER_POP(ra_timer.t_prolog);
439

Sebastian Hack's avatar
Sebastian Hack committed
440
	/* Perform the following for each register class. */
Christian Würdig's avatar
Christian Würdig committed
441
	for (j = 0, m = arch_isa_get_n_reg_class(isa); j < m; ++j) {
442
443
444
445
446
447
		chordal_env.cls           = arch_isa_get_reg_class(isa, j);
		chordal_env.border_heads  = pmap_create();
		chordal_env.ignore_colors = bitset_malloc(chordal_env.cls->n_regs);

		/* put all ignore registers into the ignore register set. */
		put_ignore_colors(&chordal_env);
Sebastian Hack's avatar
Sebastian Hack committed
448

Sebastian Hack's avatar
Sebastian Hack committed
449
450
		BE_TIMER_PUSH(ra_timer.t_live);
		be_liveness_recompute(chordal_env.lv);
Christian Würdig's avatar
Christian Würdig committed
451
		BE_TIMER_POP(ra_timer.t_live);
Sebastian Hack's avatar
Sebastian Hack committed
452
		dump(BE_CH_DUMP_LIVE, irg, chordal_env.cls, "-live", dump_ir_block_graph_sched);
Sebastian Hack's avatar
Sebastian Hack committed
453

Sebastian Hack's avatar
Sebastian Hack committed
454
455
456
		be_pre_spill_prepare_constr(&chordal_env);
		dump(BE_CH_DUMP_CONSTR, irg, chordal_env.cls, "-constr-pre", dump_ir_block_graph_sched);

Christian Würdig's avatar
Christian Würdig committed
457
		BE_TIMER_PUSH(ra_timer.t_spill);
458

Sebastian Hack's avatar
Sebastian Hack committed
459
460
		/* spilling */
		switch(options.spill_method) {
461
462
463
		case BE_CH_SPILL_MORGAN:
			be_spill_morgan(&chordal_env);
			break;
Sebastian Hack's avatar
Sebastian Hack committed
464
465
466
		case BE_CH_SPILL_BELADY:
			be_spill_belady(&chordal_env);
			break;
Michael Beck's avatar
Michael Beck committed
467
#ifdef WITH_ILP
Christian Würdig's avatar
Christian Würdig committed
468
469
470
		case BE_CH_SPILL_REMAT:
			be_spill_remat(&chordal_env);
			break;
Michael Beck's avatar
Michael Beck committed
471
#endif /* WITH_ILP */
Sebastian Hack's avatar
Sebastian Hack committed
472
473
474
475
		default:
			fprintf(stderr, "no valid spiller selected. falling back to belady\n");
			be_spill_belady(&chordal_env);
		}
Christian Würdig's avatar
Christian Würdig committed
476

Christian Würdig's avatar
Christian Würdig committed
477
		BE_TIMER_POP(ra_timer.t_spill);
Christian Würdig's avatar
Christian Würdig committed
478

Adam Szalkowski's avatar
Adam Szalkowski committed
479
480
481
482
483
484
		DBG((chordal_env.dbg, LEVEL_1, "spill costs for %+F in regclass %s: %g\n",
		      irg,
		      chordal_env.cls->name,
		      get_irg_spill_cost(&chordal_env))
		    );

485
		dump(BE_CH_DUMP_SPILL, irg, chordal_env.cls, "-spill", dump_ir_block_graph_sched);
Christian Würdig's avatar
Christian Würdig committed
486
		check_for_memory_operands(&chordal_env);
Sebastian Hack's avatar
Sebastian Hack committed
487
		be_abi_fix_stack_nodes(bi->abi, chordal_env.lv);
488

Christian Würdig's avatar
Christian Würdig committed
489
490
		BE_TIMER_PUSH(ra_timer.t_verify);

Christian Würdig's avatar
Christian Würdig committed
491
492
493
494
495
496
497
498
499
500
		/* verify schedule and register pressure */
		if (options.vrfy_option == BE_CH_VRFY_WARN) {
			be_verify_schedule(irg);
			be_verify_register_pressure(chordal_env.birg->main_env->arch_env, chordal_env.cls, irg);
		}
		else if (options.vrfy_option == BE_CH_VRFY_ASSERT) {
			assert(be_verify_schedule(irg) && "Schedule verification failed");
			assert(be_verify_register_pressure(chordal_env.birg->main_env->arch_env, chordal_env.cls, irg)
				&& "Register pressure verification failed");
		}
Christian Würdig's avatar
Christian Würdig committed
501
		BE_TIMER_POP(ra_timer.t_verify);
Sebastian Hack's avatar
Sebastian Hack committed
502

Christian Würdig's avatar
Christian Würdig committed
503
		if (be_elr_split && ! splitted) {
Sebastian Hack's avatar
Sebastian Hack committed
504
505
506
507
			extreme_liverange_splitting(&chordal_env);
			splitted = 1;
		}

508
509

		/* Color the graph. */
Sebastian Hack's avatar
Sebastian Hack committed
510
		BE_TIMER_PUSH(ra_timer.t_color);
Sebastian Hack's avatar
Sebastian Hack committed
511
		be_ra_chordal_color(&chordal_env);
Christian Würdig's avatar
Christian Würdig committed
512
		BE_TIMER_POP(ra_timer.t_color);
Christian Würdig's avatar
Christian Würdig committed
513

Sebastian Hack's avatar
Sebastian Hack committed
514
		dump(BE_CH_DUMP_CONSTR, irg, chordal_env.cls, "-color", dump_ir_block_graph_sched);
Sebastian Hack's avatar
Sebastian Hack committed
515

516
		/* Create the ifg with the selected flavor */
Sebastian Hack's avatar
Sebastian Hack committed
517
		BE_TIMER_PUSH(ra_timer.t_ifg);
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
		switch (options.ifg_flavor) {
			default:
				fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
			case BE_CH_IFG_STD:
			case BE_CH_IFG_FAST:
				chordal_env.ifg = be_ifg_std_new(&chordal_env);
				break;
			case BE_CH_IFG_CLIQUE:
				chordal_env.ifg = be_ifg_clique_new(&chordal_env);
				break;
			case BE_CH_IFG_POINTER:
				chordal_env.ifg = be_ifg_pointer_new(&chordal_env);
				break;
			case BE_CH_IFG_LIST:
				chordal_env.ifg = be_ifg_list_new(&chordal_env);
				break;
			case BE_CH_IFG_CHECK:
				check_ifg_implementations(&chordal_env);
				/* Build the interference graph. */
				chordal_env.ifg = be_ifg_std_new(&chordal_env);
				break;
		}
Christian Würdig's avatar
Christian Würdig committed
540
		BE_TIMER_POP(ra_timer.t_ifg);
Christian Würdig's avatar
Christian Würdig committed
541
542

		BE_TIMER_PUSH(ra_timer.t_verify);
543
544
545
		if (options.vrfy_option != BE_CH_VRFY_OFF)
			be_ra_chordal_check(&chordal_env);

Christian Würdig's avatar
Christian Würdig committed
546
		BE_TIMER_POP(ra_timer.t_verify);
547

Sebastian Hack's avatar
Sebastian Hack committed
548
		/* copy minimization */
Sebastian Hack's avatar
Sebastian Hack committed
549
		BE_TIMER_PUSH(ra_timer.t_copymin);
Sebastian Hack's avatar
Sebastian Hack committed
550
		co_driver(&chordal_env);
Christian Würdig's avatar
Christian Würdig committed
551
		BE_TIMER_POP(ra_timer.t_copymin);
552
		dump(BE_CH_DUMP_COPYMIN, irg, chordal_env.cls, "-copymin", dump_ir_block_graph_sched);
Christian Würdig's avatar
Christian Würdig committed
553
554
555

		BE_TIMER_PUSH(ra_timer.t_verify);

556
557
558
		if (options.vrfy_option != BE_CH_VRFY_OFF)
			be_ra_chordal_check(&chordal_env);

Christian Würdig's avatar
Christian Würdig committed
559
		BE_TIMER_POP(ra_timer.t_verify);
Christian Würdig's avatar
Christian Würdig committed
560
		BE_TIMER_PUSH(ra_timer.t_ssa);
Sebastian Hack's avatar
Sebastian Hack committed
561
562
563

		/* ssa destruction */
		be_ssa_destruction(&chordal_env);
Christian Würdig's avatar
Christian Würdig committed
564

Christian Würdig's avatar
Christian Würdig committed
565
		BE_TIMER_POP(ra_timer.t_ssa);
Christian Würdig's avatar
Christian Würdig committed
566

567
		dump(BE_CH_DUMP_SSADESTR, irg, chordal_env.cls, "-ssadestr", dump_ir_block_graph_sched);
Christian Würdig's avatar
Christian Würdig committed
568
569

		BE_TIMER_PUSH(ra_timer.t_verify);
570
571
572
573
		if (options.vrfy_option != BE_CH_VRFY_OFF) {
			be_ssa_destruction_check(&chordal_env);
			be_ra_chordal_check(&chordal_env);
		}
Christian Würdig's avatar
Christian Würdig committed
574
		BE_TIMER_POP(ra_timer.t_verify);
Sebastian Hack's avatar
Sebastian Hack committed
575
576

		be_ifg_free(chordal_env.ifg);
Sebastian Hack's avatar
Sebastian Hack committed
577
		pmap_destroy(chordal_env.border_heads);
578
		bitset_free(chordal_env.ignore_colors);
Sebastian Hack's avatar
Sebastian Hack committed
579
580
	}

581
582
	BE_TIMER_PUSH(ra_timer.t_spillslots);

Matthias Braun's avatar
Matthias Braun committed
583
	be_coalesce_spillslots(&chordal_env);
Matthias Braun's avatar
Matthias Braun committed
584
	dump(BE_CH_DUMP_SPILLSLOTS, irg, NULL, "-spillslots", dump_ir_block_graph_sched);
Matthias Braun's avatar
Matthias Braun committed
585

586
587
588
589
590
591
592
593
594
595
596
597
598
	BE_TIMER_POP(ra_timer.t_spillslots);

	BE_TIMER_PUSH(ra_timer.t_verify);

	/* verify spillslots */
	if (options.vrfy_option == BE_CH_VRFY_WARN) {
		be_verify_spillslots(irg);
	}
	else if (options.vrfy_option == BE_CH_VRFY_ASSERT) {
		assert(be_verify_spillslots(irg) && "Spillslot verification failed");
	}
	BE_TIMER_POP(ra_timer.t_verify);

Christian Würdig's avatar
Christian Würdig committed
599
	BE_TIMER_PUSH(ra_timer.t_epilog);
600

601
	dump(BE_CH_DUMP_LOWER, irg, NULL, "-spilloff", dump_ir_block_graph_sched);
602

603
	lower_nodes_after_ra(&chordal_env, options.lower_perm_opt & BE_CH_LOWER_PERM_COPY ? 1 : 0);
604
	dump(BE_CH_DUMP_LOWER, irg, NULL, "-belower-after-ra", dump_ir_block_graph_sched);
605

Sebastian Hack's avatar
Sebastian Hack committed
606
	obstack_free(&chordal_env.obst, NULL);
607
	be_free_dominance_frontiers(chordal_env.dom_front);
Sebastian Hack's avatar
Sebastian Hack committed
608
	be_liveness_free(chordal_env.lv);
Sebastian Hack's avatar
Sebastian Hack committed
609
	free_execfreq(chordal_env.exec_freq);
610

Christian Würdig's avatar
Christian Würdig committed
611
612
	BE_TIMER_POP(ra_timer.t_epilog);
	BE_TIMER_POP(ra_timer.t_other);
613

Christian Würdig's avatar
Christian Würdig committed
614
615
616
617
#undef BE_TIMER_PUSH
#undef BE_TIMER_POP

	return main_opts->timing == BE_TIME_ON ? &ra_timer : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
618
619
620
621
622
623
624
625
}

const be_ra_t be_ra_chordal_allocator = {
#ifdef WITH_LIBCORE
	be_ra_chordal_register_options,
#endif
	be_ra_chordal_main
};