bechordal_main.c 22.9 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
 *
Michael Beck's avatar
Michael Beck committed
7
 * Copyright (C) 2005-2006 Universitaet Karlsruhe
Sebastian Hack's avatar
Sebastian Hack committed
8
9
10
11
 * 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
#include <time.h>

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

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

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

#include "bechordal_t.h"
48
#include "beabi.h"
Sebastian Hack's avatar
Sebastian Hack committed
49
#include "bejavacoal.h"
Sebastian Hack's avatar
Sebastian Hack committed
50
51
52
53
54
55
#include "beutil.h"
#include "besched.h"
#include "benumb_t.h"
#include "besched_t.h"
#include "belive_t.h"
#include "bearch.h"
56
#include "beifg_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
57
#include "beifg_impl.h"
Christian Würdig's avatar
Christian Würdig committed
58
#include "benode_t.h"
59
#include "bestatevent.h"
60
#include "bestat.h"
Sebastian Hack's avatar
Sebastian Hack committed
61
62

#include "bespillbelady.h"
63
#include "bespillmorgan.h"
Matthias Braun's avatar
Matthias Braun committed
64
#include "bespillslots.h"
65
#include "bespilloptions.h"
66
67
#include "belower.h"

Christian Würdig's avatar
Christian Würdig committed
68
#ifdef WITH_ILP
69
#include "bespillremat.h"
Christian Würdig's avatar
Christian Würdig committed
70
71
#endif /* WITH_ILP */

72
#include "bejavacoal.h"
Daniel Grund's avatar
Daniel Grund committed
73
#include "becopystat.h"
Daniel Grund's avatar
Daniel Grund committed
74
#include "becopyopt.h"
Christian Würdig's avatar
Christian Würdig committed
75
#include "bessadestr.h"
76
#include "beverify.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
77
#include "bespillcost.h"
78
#include "benode_t.h"
Christian Würdig's avatar
Christian Würdig committed
79

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

	/* 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)) {
108
			DBG((dbg, 0, "Register %s assigned to %+F is not allowed\n", n1_reg->name, n1));
Daniel Grund's avatar
:wq    
Daniel Grund committed
109
			assert(0 && "Register constraint does not hold");
Sebastian Hack's avatar
Sebastian Hack committed
110
111
112
		}
		for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) {
			n2_reg = arch_get_irn_register(arch_env, n2);
113
			if (values_interfere(lv, n1, n2) && n1_reg == n2_reg) {
114
				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
115
116
117
118
119
120
121
122
123
124
125
126
				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
127
		return values_interfere(env->birg->lv, a, b);
Sebastian Hack's avatar
Sebastian Hack committed
128
129
130
131
}


static be_ra_chordal_opts_t options = {
Sebastian Hack's avatar
Sebastian Hack committed
132
	BE_CH_DUMP_NONE,
133
	BE_CH_SPILL_BELADY,
134
	BE_CH_IFG_STD,
Christian Würdig's avatar
Christian Würdig committed
135
	BE_CH_LOWER_PERM_SWAP,
Christian Würdig's avatar
Christian Würdig committed
136
	BE_CH_VRFY_WARN,
Sebastian Hack's avatar
Sebastian Hack committed
137
138
};

139
140
141
/** Enable extreme live range splitting. */
static int be_elr_split = 0;

Matthias Braun's avatar
Matthias Braun committed
142
#ifdef WITH_LIBCORE
143
144
145
/** Assumed loop iteration count for execution frequency estimation. */
static int be_loop_weight = 9;

146
147
148
149
150
151
152
153
154
static be_ra_timer_t ra_timer = {
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
Christian Würdig's avatar
Christian Würdig committed
155
156
	NULL,
	NULL,
157
	NULL,
158
159
};

Sebastian Hack's avatar
Sebastian Hack committed
160
static const lc_opt_enum_int_items_t spill_items[] = {
161
	{ "morgan", BE_CH_SPILL_MORGAN },
Sebastian Hack's avatar
Sebastian Hack committed
162
	{ "belady", BE_CH_SPILL_BELADY },
Christian Würdig's avatar
Christian Würdig committed
163
#ifdef WITH_ILP
Sebastian Hack's avatar
Sebastian Hack committed
164
	{ "remat",  BE_CH_SPILL_REMAT },
165
#endif /* WITH_ILP */
Sebastian Hack's avatar
Sebastian Hack committed
166
167
168
169
	{ NULL, 0 }
};

static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
170
171
172
173
174
175
176
	{ "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
177
178
};

179
180
static const lc_opt_enum_int_items_t lower_perm_items[] = {
	{ "copy", BE_CH_LOWER_PERM_COPY },
181
182
183
184
185
	{ "swap", BE_CH_LOWER_PERM_SWAP },
	{ NULL, 0 }
};

static const lc_opt_enum_int_items_t lower_perm_stat_items[] = {
186
187
188
	{ NULL, 0 }
};

Sebastian Hack's avatar
Sebastian Hack committed
189
static const lc_opt_enum_int_items_t dump_items[] = {
Matthias Braun's avatar
Matthias Braun committed
190
191
192
193
194
195
196
197
198
199
200
	{ "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
201
202
203
204
205
206
207
	{ 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
208
209
210
	{ NULL, 0 }
};

Sebastian Hack's avatar
Sebastian Hack committed
211
212
213
214
215
static lc_opt_enum_int_var_t spill_var = {
	&options.spill_method, spill_items
};

static lc_opt_enum_int_var_t ifg_flavor_var = {
216
	&options.ifg_flavor, ifg_flavor_items
Sebastian Hack's avatar
Sebastian Hack committed
217
218
};

219
static lc_opt_enum_int_var_t lower_perm_var = {
220
	&options.lower_perm_opt, lower_perm_items
221
222
};

Sebastian Hack's avatar
Sebastian Hack committed
223
224
225
226
static lc_opt_enum_int_var_t dump_var = {
	&options.dump_flags, dump_items
};

Christian Würdig's avatar
Christian Würdig committed
227
228
229
230
static lc_opt_enum_int_var_t be_ch_vrfy_var = {
	&options.vrfy_option, be_ch_vrfy_items
};

231
static const lc_opt_table_entry_t be_chordal_options[] = {
232
233
234
	LC_OPT_ENT_ENUM_INT ("spill",	      "spill method", &spill_var),
	LC_OPT_ENT_ENUM_PTR ("ifg",           "interference graph flavour", &ifg_flavor_var),
	LC_OPT_ENT_ENUM_PTR ("perm",          "perm lowering options", &lower_perm_var),
Sebastian Hack's avatar
Sebastian Hack committed
235
	LC_OPT_ENT_ENUM_MASK("dump",          "select dump phases", &dump_var),
236
	LC_OPT_ENT_ENUM_PTR ("vrfy",          "verify options", &be_ch_vrfy_var),
Sebastian Hack's avatar
Sebastian Hack committed
237
	LC_OPT_ENT_BOOL     ("elrsplit",      "enable extreme live range splitting", &be_elr_split),
Sebastian Hack's avatar
Sebastian Hack committed
238
	LC_OPT_ENT_INT      ("loop_weight",   "assumed amount of loop iterations for guessing the execution frequency", &be_loop_weight),
239
240
241
	{ NULL }
};

Sebastian Hack's avatar
Sebastian Hack committed
242
243
244
extern void be_spill_remat_register_options(lc_opt_entry_t *ent);


Sebastian Hack's avatar
Sebastian Hack committed
245
246
static void be_ra_chordal_register_options(lc_opt_entry_t *grp)
{
247
248
249
250
251
252
253
254
	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
255

Matthias Braun's avatar
Matthias Braun committed
256
		co_register_options(chordal_grp);
257
#ifdef WITH_JVM
Matthias Braun's avatar
Matthias Braun committed
258
		be_java_coal_register_options(chordal_grp);
259
#endif
260
#ifdef WITH_ILP
Matthias Braun's avatar
Matthias Braun committed
261
		be_spill_remat_register_options(chordal_grp);
262
#endif
263
		be_spill_register_options(chordal_grp);
Matthias Braun's avatar
Matthias Braun committed
264
	}
Sebastian Hack's avatar
Sebastian Hack committed
265
}
Christian Würdig's avatar
Christian Würdig committed
266
#endif /* WITH_LIBCORE */
Sebastian Hack's avatar
Sebastian Hack committed
267

Sebastian Hack's avatar
Sebastian Hack committed
268
static void dump(unsigned mask, ir_graph *irg,
269
270
271
				 const arch_register_class_t *cls,
				 const char *suffix,
				 void (*dump_func)(ir_graph *, const char *))
Sebastian Hack's avatar
Sebastian Hack committed
272
{
Christian Würdig's avatar
Christian Würdig committed
273
274
	if((options.dump_flags & mask) == mask) {
		if (cls) {
275
276
			char buf[256];
			snprintf(buf, sizeof(buf), "-%s%s", cls->name, suffix);
Christian Würdig's avatar
Christian Würdig committed
277
			be_dump(irg, buf, dump_func);
278
279
		}
		else
Christian Würdig's avatar
Christian Würdig committed
280
			be_dump(irg, suffix, dump_func);
281
	}
Sebastian Hack's avatar
Sebastian Hack committed
282
283
}

284
285
286
287
288
289
290
291
292
293
294
295
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
296
297
298
299
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
300
	ir_snprintf(buf, sizeof(buf), "%s%F_%s%s", prefix, env->irg, env->cls->name, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
301
302
303
	return fopen(buf, "wt");
}

304
305
306
307
void check_ifg_implementations(be_chordal_env_t *chordal_env)
{
	FILE *f;

Sebastian Hack's avatar
Sebastian Hack committed
308
	f = be_chordal_open(chordal_env, "std", ".log");
309
	chordal_env->ifg = be_ifg_std_new(chordal_env);
310
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
311
312
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
313
	f = be_chordal_open(chordal_env, "list", ".log");
314
	be_ifg_free(chordal_env->ifg);
315
	chordal_env->ifg = be_ifg_list_new(chordal_env);
316
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
317
318
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
319
	f = be_chordal_open(chordal_env, "clique", ".log");
320
	be_ifg_free(chordal_env->ifg);
321
	chordal_env->ifg = be_ifg_clique_new(chordal_env);
322
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
323
324
	fclose(f);

Sebastian Hack's avatar
Sebastian Hack committed
325
	f = be_chordal_open(chordal_env, "pointer", ".log");
326
	be_ifg_free(chordal_env->ifg);
327
	chordal_env->ifg = be_ifg_pointer_new(chordal_env);
328
	be_ifg_check_sorted_to_file(chordal_env->ifg, f);
329
	fclose(f);
330

331
332
333
	chordal_env->ifg = NULL;
};

Christian Würdig's avatar
Christian Würdig committed
334
335
336
337
338
339
340
341
/**
 * 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;
342
	ir_node          *spill;
Christian Würdig's avatar
Christian Würdig committed
343
344
345
346

	if (! be_is_Reload(irn))
		return;

347
348
349
	/* always use addressmode, it's good for x86 */
#if 0
	/* only use memory operands, if the reload is only used by 1 node */
350
351
	if(get_irn_n_edges(irn) > 1)
		return;
352
#endif
353
354

	spill = be_get_Reload_mem(irn);
Christian Würdig's avatar
Christian Würdig committed
355
356
357
358
359
360
	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);

361
		assert(src && "outedges broken!");
Christian Würdig's avatar
Christian Würdig committed
362
363
364

		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));
365
			//arch_perform_memory_operand(aenv, src, spill, pos);
Christian Würdig's avatar
Christian Würdig committed
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
		}
	}

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

384
385
386
387
388
389
/**
 * Sorry for doing stats again...
 */
typedef struct _node_stat_t {
	unsigned int n_phis;      /**< Phis of the current register class. */
	unsigned int n_mem_phis;  /**< Memory Phis (Phis with spill operands). */
Sebastian Hack's avatar
Sebastian Hack committed
390
391
	unsigned int n_copies;    /**< Copies */
	unsigned int n_perms;     /**< Perms */
392
	unsigned int n_spills;    /**< Spill nodes */
Sebastian Hack's avatar
Sebastian Hack committed
393
	unsigned int n_reloads;   /**< Reloads */
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
} node_stat_t;

struct node_stat_walker {
	node_stat_t *stat;
	const be_chordal_env_t *cenv;
	bitset_t *mem_phis;
};

static void node_stat_walker(ir_node *irn, void *data)
{
	struct node_stat_walker *env = data;
	const arch_env_t *aenv       = env->cenv->birg->main_env->arch_env;

	if(arch_irn_consider_in_reg_alloc(aenv, env->cenv->cls, irn)) {

		/* if the node is a normal phi */
		if(is_Phi(irn))
			env->stat->n_phis++;

		else if(arch_irn_classify(aenv, irn) & arch_irn_class_spill)
			++env->stat->n_spills;

		else if(arch_irn_classify(aenv, irn) & arch_irn_class_reload)
			++env->stat->n_reloads;

Sebastian Hack's avatar
Sebastian Hack committed
419
420
421
422
423
		else if(arch_irn_classify(aenv, irn) & arch_irn_class_copy)
			++env->stat->n_copies;

		else if(arch_irn_classify(aenv, irn) & arch_irn_class_perm)
			++env->stat->n_perms;
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
	}

	/* a mem phi is a PhiM with a mem phi operand or a Spill operand */
	else if(is_Phi(irn) && get_irn_mode(irn) == mode_M) {
		int i;

		for(i = get_irn_arity(irn) - 1; i >= 0; --i) {
			ir_node *op = get_irn_n(irn, i);

			if((is_Phi(op) && bitset_contains_irn(env->mem_phis, op)) || (arch_irn_classify(aenv, op) & arch_irn_class_spill)) {
				bitset_add_irn(env->mem_phis, irn);
				env->stat->n_mem_phis++;
				break;
			}
		}
	}
}

static void node_stats(const be_chordal_env_t *cenv, node_stat_t *stat)
{
	struct node_stat_walker env;

	memset(stat, 0, sizeof(stat[0]));
	env.cenv     = cenv;
	env.mem_phis = bitset_irg_malloc(cenv->irg);
	env.stat     = stat;
	irg_walk_graph(cenv->irg, NULL, node_stat_walker, &env);
	bitset_free(env.mem_phis);
}

static void insn_count_walker(ir_node *irn, void *data)
{
	int *cnt = data;

	switch(get_irn_opcode(irn)) {
	case iro_Proj:
	case iro_Phi:
	case iro_Start:
	case iro_End:
		break;
	default:
		(*cnt)++;
	}
}

static unsigned int count_insns(ir_graph *irg)
{
	int cnt = 0;
	irg_walk_graph(irg, insn_count_walker, NULL, &cnt);
	return cnt;
}

476
#ifdef WITH_LIBCORE
Christian Würdig's avatar
Christian Würdig committed
477
/**
478
 * Initialize all timers.
Christian Würdig's avatar
Christian Würdig committed
479
 */
480
static void be_init_timer(be_options_t *main_opts)
Sebastian Hack's avatar
Sebastian Hack committed
481
{
482
	if (main_opts->timing == BE_TIME_ON) {
483
484
485
486
487
488
489
490
491
492
493
		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");
		ra_timer.t_spillslots = lc_timer_register("ra_spillslots", "spillslots");
		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");
494
495
496
497
498

		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);
499
		LC_STOP_AND_RESET_TIMER(ra_timer.t_spillslots);
500
501
502
503
		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
504
505
		LC_STOP_AND_RESET_TIMER(ra_timer.t_verify);
		LC_STOP_AND_RESET_TIMER(ra_timer.t_other);
506
	}
507
}
508

509
510
511
512
513
514
515
516
517
518
519
#define BE_TIMER_INIT(main_opts)	be_init_timer(main_opts)

#define BE_TIMER_PUSH(timer)                                                            \
	if (main_opts->timing == BE_TIME_ON) {                                              \
		if (! lc_timer_push(timer)) {                                                   \
			if (options.vrfy_option == BE_CH_VRFY_ASSERT)                               \
				assert(!"Timer already on stack, cannot be pushed twice.");             \
			else if (options.vrfy_option == BE_CH_VRFY_WARN)                            \
				fprintf(stderr, "Timer %s already on stack, cannot be pushed twice.\n", \
					lc_timer_get_name(timer));                                          \
		}                                                                               \
Christian Würdig's avatar
Christian Würdig committed
520
521
522
523
524
525
526
527
528
529
530
	}
#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;                                                                           \
	}
531
#else
532

533
534
535
536
537
538
539
540
541
#define BE_TIMER_INIT(main_opts)
#define BE_TIMER_PUSH(timer)
#define BE_TIMER_POP(timer)

#endif /* WITH_LIBCORE */

/**
 * Performs chordal register allocation for each register class on given irg.
 *
542
 * @param birg  Backend irg object
543
544
 * @return Structure containing timer for the single phases or NULL if no timing requested.
 */
545
static be_ra_timer_t *be_ra_chordal_main(be_irg_t *birg)
546
{
547
	const be_main_env_t *main_env  = birg->main_env;
548
	const arch_isa_t    *isa       = arch_env_get_isa(main_env->arch_env);
549
	ir_graph            *irg       = birg->irg;
550
	be_options_t        *main_opts = main_env->options;
Matthias Braun's avatar
Matthias Braun committed
551
	int                  splitted = 0;
552

553
	int j, m;
554
555
556
	be_chordal_env_t chordal_env;

	BE_TIMER_INIT(main_opts);
Christian Würdig's avatar
Christian Würdig committed
557
558
	BE_TIMER_PUSH(ra_timer.t_other);
	BE_TIMER_PUSH(ra_timer.t_prolog);
559

560
561
	be_assure_dom_front(birg);
	be_assure_liveness(birg);
Sebastian Hack's avatar
Sebastian Hack committed
562

Sebastian Hack's avatar
Sebastian Hack committed
563
564
	chordal_env.opts      = &options;
	chordal_env.irg       = irg;
565
	chordal_env.birg      = birg;
566
	FIRM_DBG_REGISTER(chordal_env.dbg, "firm.be.chordal");
Sebastian Hack's avatar
Sebastian Hack committed
567
568
569

	obstack_init(&chordal_env.obst);

Christian Würdig's avatar
Christian Würdig committed
570
	BE_TIMER_POP(ra_timer.t_prolog);
571

572
573
	be_stat_ev("insns_before", count_insns(irg));

Sebastian Hack's avatar
Sebastian Hack committed
574
	/* Perform the following for each register class. */
Christian Würdig's avatar
Christian Würdig committed
575
	for (j = 0, m = arch_isa_get_n_reg_class(isa); j < m; ++j) {
576
		node_stat_t node_stat;
577
		double spillcosts = 0;
578

579
580
581
582
		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);

Matthias Braun's avatar
Matthias Braun committed
583
#ifdef FIRM_STATISTICS
584
		if(be_stat_ev_is_active()) {
585
			be_stat_tags[STAT_TAG_CLS] = chordal_env.cls->name;
586
			be_stat_ev_push(be_stat_tags, STAT_TAG_LAST, be_stat_file);
Adam Szalkowski's avatar
Adam Szalkowski committed
587

588
589
590
591
			/* perform some node statistics. */
			node_stats(&chordal_env, &node_stat);
			be_stat_ev("phis_before_spill", node_stat.n_phis);
		}
Matthias Braun's avatar
Matthias Braun committed
592
#endif
593

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

Sebastian Hack's avatar
Sebastian Hack committed
597
598
599
		be_pre_spill_prepare_constr(&chordal_env);
		dump(BE_CH_DUMP_CONSTR, irg, chordal_env.cls, "-constr-pre", dump_ir_block_graph_sched);

600
		if(be_stat_ev_is_active()) {
601
			spillcosts = be_estimate_irg_costs(irg, main_env->arch_env, birg->exec_freq);
602
603
		}

Christian Würdig's avatar
Christian Würdig committed
604
		BE_TIMER_PUSH(ra_timer.t_spill);
605

Sebastian Hack's avatar
Sebastian Hack committed
606
607
		/* spilling */
		switch(options.spill_method) {
608
609
610
		case BE_CH_SPILL_MORGAN:
			be_spill_morgan(&chordal_env);
			break;
Sebastian Hack's avatar
Sebastian Hack committed
611
612
613
		case BE_CH_SPILL_BELADY:
			be_spill_belady(&chordal_env);
			break;
Michael Beck's avatar
Michael Beck committed
614
#ifdef WITH_ILP
Christian Würdig's avatar
Christian Würdig committed
615
616
617
		case BE_CH_SPILL_REMAT:
			be_spill_remat(&chordal_env);
			break;
Michael Beck's avatar
Michael Beck committed
618
#endif /* WITH_ILP */
Sebastian Hack's avatar
Sebastian Hack committed
619
620
621
622
		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
623

Christian Würdig's avatar
Christian Würdig committed
624
		BE_TIMER_POP(ra_timer.t_spill);
Christian Würdig's avatar
Christian Würdig committed
625

626
		if(be_stat_ev_is_active()) {
627
			spillcosts = be_estimate_irg_costs(irg, main_env->arch_env, birg->exec_freq) - spillcosts;
628
629
			be_stat_ev_l("spillcosts", (long) spillcosts);

630
631
632
633
634
635
636
637
			node_stats(&chordal_env, &node_stat);
			be_stat_ev("phis_after_spill", node_stat.n_phis);
			be_stat_ev("mem_phis", node_stat.n_mem_phis);
			be_stat_ev("reloads", node_stat.n_reloads);
			be_stat_ev("spills", node_stat.n_spills);
		}

		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)));
Adam Szalkowski's avatar
Adam Szalkowski committed
638

639
		dump(BE_CH_DUMP_SPILL, irg, chordal_env.cls, "-spill", dump_ir_block_graph_sched);
640

641
642
		check_for_memory_operands(&chordal_env);

643
		be_abi_fix_stack_nodes(birg->abi, birg->lv);
644

Christian Würdig's avatar
Christian Würdig committed
645
646
		BE_TIMER_PUSH(ra_timer.t_verify);

Christian Würdig's avatar
Christian Würdig committed
647
648
649
		/* verify schedule and register pressure */
		if (options.vrfy_option == BE_CH_VRFY_WARN) {
			be_verify_schedule(irg);
Sebastian Hack's avatar
Sebastian Hack committed
650
			be_verify_register_pressure(chordal_env.birg, chordal_env.cls, irg);
Christian Würdig's avatar
Christian Würdig committed
651
652
653
		}
		else if (options.vrfy_option == BE_CH_VRFY_ASSERT) {
			assert(be_verify_schedule(irg) && "Schedule verification failed");
Sebastian Hack's avatar
Sebastian Hack committed
654
			assert(be_verify_register_pressure(chordal_env.birg, chordal_env.cls, irg)
Christian Würdig's avatar
Christian Würdig committed
655
656
				&& "Register pressure verification failed");
		}
Christian Würdig's avatar
Christian Würdig committed
657
		BE_TIMER_POP(ra_timer.t_verify);
Sebastian Hack's avatar
Sebastian Hack committed
658

Christian Würdig's avatar
Christian Würdig committed
659
		if (be_elr_split && ! splitted) {
Sebastian Hack's avatar
Sebastian Hack committed
660
661
662
663
			extreme_liverange_splitting(&chordal_env);
			splitted = 1;
		}

664
665

		/* Color the graph. */
Sebastian Hack's avatar
Sebastian Hack committed
666
		BE_TIMER_PUSH(ra_timer.t_color);
Sebastian Hack's avatar
Sebastian Hack committed
667
		be_ra_chordal_color(&chordal_env);
Christian Würdig's avatar
Christian Würdig committed
668
		BE_TIMER_POP(ra_timer.t_color);
Christian Würdig's avatar
Christian Würdig committed
669

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

672
		/* Create the ifg with the selected flavor */
Sebastian Hack's avatar
Sebastian Hack committed
673
		BE_TIMER_PUSH(ra_timer.t_ifg);
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
		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
696
		BE_TIMER_POP(ra_timer.t_ifg);
Christian Würdig's avatar
Christian Würdig committed
697

698
		if(be_stat_ev_is_active()) {
699
			be_ifg_stat_t stat;
Sebastian Hack's avatar
Sebastian Hack committed
700
			be_ifg_stat(&chordal_env, &stat);
701
702
			be_stat_ev("ifg_nodes", stat.n_nodes);
			be_stat_ev("ifg_edges", stat.n_edges);
Sebastian Hack's avatar
Sebastian Hack committed
703
			be_stat_ev("ifg_comps", stat.n_comps);
704
705
		}

Christian Würdig's avatar
Christian Würdig committed
706
		BE_TIMER_PUSH(ra_timer.t_verify);
707
708
709
		if (options.vrfy_option != BE_CH_VRFY_OFF) {
			//be_ra_chordal_check(&chordal_env);
		}
710

Christian Würdig's avatar
Christian Würdig committed
711
		BE_TIMER_POP(ra_timer.t_verify);
712

713
		if(be_stat_ev_is_active()) {
Sebastian Hack's avatar
Sebastian Hack committed
714
715
716
717
718
			node_stats(&chordal_env, &node_stat);
			be_stat_ev("perms_before_coal", node_stat.n_perms);
			be_stat_ev("copies_before_coal", node_stat.n_copies);
		}

Sebastian Hack's avatar
Sebastian Hack committed
719
		/* copy minimization */
Sebastian Hack's avatar
Sebastian Hack committed
720
		BE_TIMER_PUSH(ra_timer.t_copymin);
Sebastian Hack's avatar
Sebastian Hack committed
721
		co_driver(&chordal_env);
Christian Würdig's avatar
Christian Würdig committed
722
		BE_TIMER_POP(ra_timer.t_copymin);
Sebastian Hack's avatar
Sebastian Hack committed
723

724
		dump(BE_CH_DUMP_COPYMIN, irg, chordal_env.cls, "-copymin", dump_ir_block_graph_sched);
Christian Würdig's avatar
Christian Würdig committed
725
726
727

		BE_TIMER_PUSH(ra_timer.t_verify);

728
729
730
		if (options.vrfy_option != BE_CH_VRFY_OFF) {
			//be_ra_chordal_check(&chordal_env);
		}
731

Christian Würdig's avatar
Christian Würdig committed
732
		BE_TIMER_POP(ra_timer.t_verify);
Christian Würdig's avatar
Christian Würdig committed
733
		BE_TIMER_PUSH(ra_timer.t_ssa);
Sebastian Hack's avatar
Sebastian Hack committed
734
735
736

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

Christian Würdig's avatar
Christian Würdig committed
738
		BE_TIMER_POP(ra_timer.t_ssa);
Christian Würdig's avatar
Christian Würdig committed
739

740
		dump(BE_CH_DUMP_SSADESTR, irg, chordal_env.cls, "-ssadestr", dump_ir_block_graph_sched);
Christian Würdig's avatar
Christian Würdig committed
741
742

		BE_TIMER_PUSH(ra_timer.t_verify);
743
744
		if (options.vrfy_option != BE_CH_VRFY_OFF) {
			be_ssa_destruction_check(&chordal_env);
745
			//be_ra_chordal_check(&chordal_env);
746
		}
Christian Würdig's avatar
Christian Würdig committed
747
		BE_TIMER_POP(ra_timer.t_verify);
Sebastian Hack's avatar
Sebastian Hack committed
748
749

		be_ifg_free(chordal_env.ifg);
Sebastian Hack's avatar
Sebastian Hack committed
750
		pmap_destroy(chordal_env.border_heads);
751
		bitset_free(chordal_env.ignore_colors);
752

753
		if(be_stat_ev_is_active()) {
Sebastian Hack's avatar
Sebastian Hack committed
754
755
756
757
758
			node_stats(&chordal_env, &node_stat);
			be_stat_ev("perms_after_coal", node_stat.n_perms);
			be_stat_ev("copies_after_coal", node_stat.n_copies);
		}

759
		be_stat_ev_pop();
Sebastian Hack's avatar
Sebastian Hack committed
760
761
	}

762
763
	BE_TIMER_PUSH(ra_timer.t_spillslots);

764
	be_coalesce_spillslots(&chordal_env);
Matthias Braun's avatar
Matthias Braun committed
765
	dump(BE_CH_DUMP_SPILLSLOTS, irg, NULL, "-spillslots", dump_ir_block_graph_sched);
Matthias Braun's avatar
Matthias Braun committed
766

767
768
769
770
771
772
	BE_TIMER_POP(ra_timer.t_spillslots);

	BE_TIMER_PUSH(ra_timer.t_verify);

	/* verify spillslots */
	if (options.vrfy_option == BE_CH_VRFY_WARN) {
773
		be_verify_spillslots(main_env->arch_env, irg);
774
775
	}
	else if (options.vrfy_option == BE_CH_VRFY_ASSERT) {
776
		assert(be_verify_spillslots(main_env->arch_env, irg) && "Spillslot verification failed");
777
778
779
	}
	BE_TIMER_POP(ra_timer.t_verify);

Christian Würdig's avatar
Christian Würdig committed
780
	BE_TIMER_PUSH(ra_timer.t_epilog);
781

782
	dump(BE_CH_DUMP_LOWER, irg, NULL, "-spilloff", dump_ir_block_graph_sched);
783

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

Sebastian Hack's avatar
Sebastian Hack committed
787
	obstack_free(&chordal_env.obst, NULL);
788

Christian Würdig's avatar
Christian Würdig committed
789
790
	BE_TIMER_POP(ra_timer.t_epilog);
	BE_TIMER_POP(ra_timer.t_other);
791

792
793
	be_stat_ev("insns_after", count_insns(irg));

794
#ifdef WITH_LIBCORE
Christian Würdig's avatar
Christian Würdig committed
795
	return main_opts->timing == BE_TIME_ON ? &ra_timer : NULL;
796
797
#endif /* WITH_LIBCORE */
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
798
799
800
801
802
}

const be_ra_t be_ra_chordal_allocator = {
#ifdef WITH_LIBCORE
	be_ra_chordal_register_options,
803
#else
Christian Würdig's avatar
Christian Würdig committed
804
	NULL,
805
#endif
Christian Würdig's avatar
Christian Würdig committed
806
	be_ra_chordal_main,
Sebastian Hack's avatar
Sebastian Hack committed
807
};