bemain.c 25 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       Main Backend driver.
 * @author      Sebastian Hack
 * @date        25.11.2004
11
 */
Michael Beck's avatar
Michael Beck committed
12
#include "config.h"
13

Sebastian Hack's avatar
Sebastian Hack committed
14
#include <stdarg.h>
15
#include <stdio.h>
16

Matthias Braun's avatar
Matthias Braun committed
17
18
#include "lc_opts.h"
#include "lc_opts_enum.h"
19

Sebastian Hack's avatar
Sebastian Hack committed
20
21
#include "obst.h"
#include "bitset.h"
22
#include "statev.h"
Sebastian Hack's avatar
Sebastian Hack committed
23
#include "irprog.h"
Sebastian Hack's avatar
Sebastian Hack committed
24
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
25
#include "irgraph.h"
Daniel Grund's avatar
Daniel Grund committed
26
#include "irdump.h"
Sebastian Hack's avatar
Sebastian Hack committed
27
28
#include "irdom_t.h"
#include "iredges_t.h"
29
#include "irloop_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
30
#include "irtools.h"
31
#include "irverify.h"
32
#include "irprintf.h"
Matthias Braun's avatar
Matthias Braun committed
33
#include "iroptimize.h"
Christian Würdig's avatar
Christian Würdig committed
34
#include "firmstat.h"
35
#include "execfreq_t.h"
36
#include "irprofile.h"
37
#include "irpass_t.h"
38
#include "ircons.h"
Sebastian Hack's avatar
Sebastian Hack committed
39

40
#include "bearch.h"
Sebastian Hack's avatar
Sebastian Hack committed
41
#include "be_t.h"
42
#include "begnuas.h"
43
#include "bemodule.h"
44
#include "beutil.h"
45
#include "benode.h"
46
#include "beirgmod.h"
47
#include "besched.h"
48
49
#include "belistsched.h"
#include "belive_t.h"
50
51
52
#include "bera.h"
#include "bechordal_t.h"
#include "beifg.h"
Daniel Grund's avatar
Daniel Grund committed
53
#include "becopyopt.h"
54
#include "becopystat.h"
55
#include "bessadestr.h"
Sebastian Hack's avatar
Sebastian Hack committed
56
#include "beabi.h"
Christian Würdig's avatar
Christian Würdig committed
57
#include "belower.h"
58
#include "bestat.h"
59
#include "beverify.h"
60
#include "beirg.h"
61
#include "bestack.h"
62
#include "beemitter.h"
Sebastian Hack's avatar
Sebastian Hack committed
63

64
65
#define NEW_ID(s) new_id_from_chars(s, sizeof(s) - 1)

Sebastian Hack's avatar
Sebastian Hack committed
66
/* options visible for anyone */
67
be_options_t be_options = {
68
	DUMP_NONE,                         /* dump flags */
69
	BE_TIME_OFF,                       /* no timing */
70
71
	false,                             /* profile_generate */
	false,                             /* profile_use */
Michael Beck's avatar
Michael Beck committed
72
	0,                                 /* try to omit frame pointer */
73
	0,                                 /* create PIC code */
74
	BE_VERIFY_WARN,                    /* verification level: warn */
Sebastian Hack's avatar
Sebastian Hack committed
75
	"",                                /* ilp server */
76
	"",                                /* ilp solver */
Sebastian Hack's avatar
Sebastian Hack committed
77
	0,                                 /* enable statistic event dumping */
78
	"",                                /* print stat events */
79
	1,                                 /* verbose assembler output */
Sebastian Hack's avatar
Sebastian Hack committed
80
81
82
};

/* back end instruction set architecture to use */
83
static const arch_isa_if_t *isa_if = NULL;
Michael Beck's avatar
Michael Beck committed
84

Sebastian Hack's avatar
Sebastian Hack committed
85
86
/* possible dumping options */
static const lc_opt_enum_mask_items_t dump_items[] = {
87
	{ "none",       DUMP_NONE },
Sebastian Hack's avatar
Sebastian Hack committed
88
	{ "initial",    DUMP_INITIAL },
89
	{ "abi",        DUMP_ABI    },
Sebastian Hack's avatar
Sebastian Hack committed
90
91
	{ "sched",      DUMP_SCHED  },
	{ "prepared",   DUMP_PREPARED },
92
	{ "regalloc",   DUMP_RA },
Sebastian Hack's avatar
Sebastian Hack committed
93
	{ "final",      DUMP_FINAL },
94
95
	{ "be",         DUMP_BE },
	{ "all",        2 * DUMP_BE - 1 },
Sebastian Hack's avatar
Sebastian Hack committed
96
97
98
	{ NULL,         0 }
};

Christian Würdig's avatar
Christian Würdig committed
99
/* verify options. */
100
101
102
103
static const lc_opt_enum_int_items_t verify_items[] = {
	{ "off",    BE_VERIFY_OFF    },
	{ "warn",   BE_VERIFY_WARN   },
	{ "assert", BE_VERIFY_ASSERT },
Christian Würdig's avatar
Christian Würdig committed
104
	{ NULL,     0 }
Christian Würdig's avatar
Christian Würdig committed
105
};
106

Sebastian Hack's avatar
Sebastian Hack committed
107
static lc_opt_enum_mask_var_t dump_var = {
108
	&be_options.dump_flags, dump_items
109
110
};

111
112
static lc_opt_enum_int_var_t verify_var = {
	&be_options.verify_option, verify_items
Christian Würdig's avatar
Christian Würdig committed
113
114
};

Sebastian Hack's avatar
Sebastian Hack committed
115
static const lc_opt_table_entry_t be_main_options[] = {
116
117
118
	LC_OPT_ENT_ENUM_MASK("dump",       "dump irg on several occasions",                       &dump_var),
	LC_OPT_ENT_BOOL     ("omitfp",     "omit frame pointer",                                  &be_options.omit_fp),
	LC_OPT_ENT_BOOL     ("pic",        "create PIC code",                                     &be_options.pic),
119
	LC_OPT_ENT_ENUM_INT ("verify",     "verify the backend irg",                              &verify_var),
120
	LC_OPT_ENT_BOOL     ("time",       "get backend timing statistics",                       &be_options.timing),
121
122
	LC_OPT_ENT_BOOL     ("profilegenerate", "instrument the code for execution count profiling",   &be_options.opt_profile_generate),
	LC_OPT_ENT_BOOL     ("profileuse",      "use existing profile data",                           &be_options.opt_profile_use),
123
	LC_OPT_ENT_BOOL     ("statev",     "dump statistic events",                               &be_options.statev),
124
	LC_OPT_ENT_STR      ("filtev",     "filter for stat events (regex if support is active",  &be_options.filtev),
125
	LC_OPT_ENT_BOOL     ("verboseasm", "enable verbose assembler output",                     &be_options.verbose_asm),
126

127
128
	LC_OPT_ENT_STR("ilp.server", "the ilp server name", &be_options.ilp_server),
	LC_OPT_ENT_STR("ilp.solver", "the ilp solver name", &be_options.ilp_solver),
129
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
130
131
};

132
133
static be_module_list_entry_t *isa_ifs         = NULL;
static bool                    isa_initialized = false;
134

135
asm_constraint_flags_t asm_constraint_flags[256];
136

137
138
139
140
141
static void initialize_isa(void)
{
	if (isa_initialized)
		return;
	isa_if->init();
Matthias Braun's avatar
Matthias Braun committed
142
143
144
145
146
147
148
149
150
	isa_initialized = true;
}

static void finish_isa(void)
{
	if (isa_initialized) {
		isa_if->finish();
		isa_initialized = false;
	}
151
152
}

153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
void be_init_default_asm_constraint_flags(void)
{
	asm_constraint_flags['?'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['!'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['&'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT
		| ASM_CONSTRAINT_FLAG_MODIFIER_EARLYCLOBBER;
	asm_constraint_flags['%'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT
		| ASM_CONSTRAINT_FLAG_MODIFIER_COMMUTATIVE;
	asm_constraint_flags['!'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;

	asm_constraint_flags['='] = ASM_CONSTRAINT_FLAG_MODIFIER_WRITE
		| ASM_CONSTRAINT_FLAG_MODIFIER_NO_READ;
	asm_constraint_flags['+'] = ASM_CONSTRAINT_FLAG_MODIFIER_READ
		| ASM_CONSTRAINT_FLAG_MODIFIER_WRITE;

	asm_constraint_flags['i'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['s'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['E'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['F'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['G'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['H'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['I'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['J'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['K'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['L'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['M'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['N'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['O'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['P'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;

	asm_constraint_flags['m'] = ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP;
	asm_constraint_flags['o'] = ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP;
	asm_constraint_flags['V'] = ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP;
	asm_constraint_flags['<'] = ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP;
	asm_constraint_flags['>'] = ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP;

	asm_constraint_flags['p'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['0'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['1'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['2'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['3'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['4'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['5'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['6'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['7'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['8'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	asm_constraint_flags['9'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;

	asm_constraint_flags['X'] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER
		| ASM_CONSTRAINT_FLAG_SUPPORTS_MEMOP
		| ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;

	/* these should have been catched by the parsing code already */
	asm_constraint_flags['#']  = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['*']  = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags[' ']  = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['\t'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['\n'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
	asm_constraint_flags['\r'] = ASM_CONSTRAINT_FLAG_NO_SUPPORT;
}

214
asm_constraint_flags_t be_parse_asm_constraints(const char *constraint)
215
{
216
	asm_constraint_flags_t  flags = ASM_CONSTRAINT_FLAG_NONE;
217
218
219
	const char             *c;
	asm_constraint_flags_t  tflags;

220
221
	initialize_isa();

222
223
224
225
	for (c = constraint; *c != '\0'; ++c) {
		switch (*c) {
		case '#':
			/* 'comment' stuff */
226
			while (*c != 0 && *c != ',')
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
				++c;
			break;
		case '*':
			/* 'comment' character */
			++c;
			break;
		case ' ':
		case '\t':
		case '\n':
		case '\r':
			break;
		default:
			tflags = asm_constraint_flags[(int) *c];
			if (tflags != 0) {
				flags |= tflags;
			} else {
243
				flags |= isa_if->parse_asm_constraint(&c);
244
245
246
247
248
			}
			break;
		}
	}

249
	if ((
250
251
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_WRITE &&
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_NO_WRITE
252
	    ) || (
253
254
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_READ &&
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_NO_READ
255
	    )) {
256
257
		flags |= ASM_CONSTRAINT_FLAG_INVALID;
	}
258
259
260
261
262
	if (!(flags & (ASM_CONSTRAINT_FLAG_MODIFIER_READ     |
	               ASM_CONSTRAINT_FLAG_MODIFIER_WRITE    |
	               ASM_CONSTRAINT_FLAG_MODIFIER_NO_WRITE |
	               ASM_CONSTRAINT_FLAG_MODIFIER_NO_READ)
	    )) {
263
264
		flags |= ASM_CONSTRAINT_FLAG_MODIFIER_READ;
	}
265
266
267
268

	return flags;
}

269
int be_is_valid_clobber(const char *clobber)
270
{
271
272
	initialize_isa();

273
274
275
	/* memory is a valid clobber. (the frontend has to detect this case too,
	 * because it has to add memory edges to the asm) */
	if (strcmp(clobber, "memory") == 0)
276
		return 1;
277
278
	/* cc (condition code) is always valid */
	if (strcmp(clobber, "cc") == 0)
279
		return 1;
280

281
	return isa_if->is_valid_clobber(clobber);
282
283
}

284
285
void be_register_isa_if(const char *name, const arch_isa_if_t *isa)
{
286
	if (isa_if == NULL)
287
288
289
290
291
		isa_if = isa;

	be_add_module_to_list(&isa_ifs, name, (void*) isa);
}

292
static void be_opt_register(void)
Sebastian Hack's avatar
Sebastian Hack committed
293
{
294
	lc_opt_entry_t *be_grp;
295
296
	static int run_once = 0;

297
	if (run_once)
298
		return;
299
	run_once = 1;
300

301
302
	be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_add_table(be_grp, be_main_options);
303
304
305

	be_add_module_list_opt(be_grp, "isa", "the instruction set architecture",
	                       &isa_ifs, (void**) &isa_if);
306
307

	be_init_modules();
308
}
Sebastian Hack's avatar
Sebastian Hack committed
309

310
/* Parse one argument. */
311
312
int be_parse_arg(const char *arg)
{
313
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
Michael Beck's avatar
Michael Beck committed
314
	if (strcmp(arg, "help") == 0 || (arg[0] == '?' && arg[1] == '\0')) {
315
		lc_opt_print_help_for_entry(be_grp, '-', stdout);
Michael Beck's avatar
Michael Beck committed
316
317
		return -1;
	}
318
	return lc_opt_from_single_arg(be_grp, NULL, arg, NULL);
319
320
}

Christian Würdig's avatar
Christian Würdig committed
321
/* Perform schedule verification if requested. */
322
static void be_sched_verify(ir_graph *irg, int verify_opt)
323
{
324
	if (verify_opt == BE_VERIFY_WARN) {
325
		be_verify_schedule(irg);
326
	} else if (verify_opt == BE_VERIFY_ASSERT) {
327
		assert(be_verify_schedule(irg) && "Schedule verification failed.");
Christian Würdig's avatar
Christian Würdig committed
328
329
330
	}
}

331
332
/* Initialize the Firm backend. Must be run first in init_firm()! */
void firm_be_init(void)
333
{
Sebastian Hack's avatar
Sebastian Hack committed
334
	be_opt_register();
335
	be_init_modules();
336
}
337

yb9976's avatar
yb9976 committed
338
339
340
/* Finalize the Firm backend. */
void firm_be_finish(void)
{
Matthias Braun's avatar
Matthias Braun committed
341
	finish_isa();
yb9976's avatar
yb9976 committed
342
343
344
	be_quit_modules();
}

345
346
347
/* Returns the backend parameter */
const backend_params *be_get_backend_param(void)
{
348
	initialize_isa();
349
	return isa_if->get_params();
350
351
}

Manuel Mohr's avatar
Manuel Mohr committed
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
int be_is_big_endian(void)
{
	return be_get_backend_param()->byte_order_big_endian;
}

unsigned be_get_machine_size(void)
{
	return be_get_backend_param()->machine_size;
}

ir_mode *be_get_mode_float_arithmetic(void)
{
	return be_get_backend_param()->mode_float_arithmetic;
}

ir_type *be_get_type_long_long(void)
{
	return be_get_backend_param()->type_long_long;
}

ir_type *be_get_type_unsigned_long_long(void)
{
	return be_get_backend_param()->type_unsigned_long_long;
}

ir_type *be_get_type_long_double(void)
{
	return be_get_backend_param()->type_long_double;
}

382
383
384
385
386
387
/**
 * Initializes the main environment for the backend.
 *
 * @param env          an empty environment
 * @param file_handle  the file handle where the output will be written to
 */
388
static be_main_env_t *be_init_env(be_main_env_t *const env, char const *const compilation_unit_name)
Sebastian Hack's avatar
Sebastian Hack committed
389
{
Sebastian Hack's avatar
Sebastian Hack committed
390
	memset(env, 0, sizeof(*env));
391
	env->ent_trampoline_map   = pmap_create();
392
	env->pic_trampolines_type = new_type_segment(NEW_ID("$PIC_TRAMPOLINE_TYPE"), tf_none);
393
	env->ent_pic_symbol_map   = pmap_create();
394
	env->pic_symbols_type     = new_type_segment(NEW_ID("$PIC_SYMBOLS_TYPE"), tf_none);
395
	env->cup_name             = compilation_unit_name;
396
	env->arch_env             = isa_if->begin_codegeneration();
397
398

	set_class_final(env->pic_trampolines_type, 1);
Sebastian Hack's avatar
Sebastian Hack committed
399

400
	memset(asm_constraint_flags, 0, sizeof(asm_constraint_flags));
Sebastian Hack's avatar
Sebastian Hack committed
401
402

	return env;
403
404
}

405
406
407
/**
 * Called when the be_main_env_t can be destroyed.
 */
Sebastian Hack's avatar
Sebastian Hack committed
408
static void be_done_env(be_main_env_t *env)
409
{
410
411
	pmap_destroy(env->ent_trampoline_map);
	pmap_destroy(env->ent_pic_symbol_map);
412
413
	free_type(env->pic_trampolines_type);
	free_type(env->pic_symbols_type);
Sebastian Hack's avatar
Sebastian Hack committed
414
}
Sebastian Hack's avatar
Sebastian Hack committed
415

416
417
418
419
420
421
422
423
424
/**
 * A wrapper around a firm dumper. Dumps only, if
 * flags are enabled.
 *
 * @param mask    a bitmask containing the reason what will be dumped
 * @param irg     the IR graph to dump
 * @param suffix  the suffix for the dumper
 * @param dumper  the dumper to be called
 */
425
static void dump(int mask, ir_graph *irg, const char *suffix)
Sebastian Hack's avatar
Sebastian Hack committed
426
{
427
	if (be_options.dump_flags & mask)
428
		dump_ir_graph(irg, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
429
}
430

Michael Beck's avatar
Michael Beck committed
431
/**
432
 * Prepare a backend graph for code generation and initialize its irg
Michael Beck's avatar
Michael Beck committed
433
 */
434
static void initialize_birg(be_irg_t *birg, ir_graph *irg, be_main_env_t *env)
Sebastian Hack's avatar
Sebastian Hack committed
435
{
436
437
438
	/* don't duplicate locals in backend when dumping... */
	ir_remove_dump_flags(ir_dump_flag_consts_local);

439
440
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
441
442
	irg->be_data = birg;

443
444
	memset(birg, 0, sizeof(*birg));
	birg->main_env = env;
445
	obstack_init(&birg->obst);
446
	birg->lv = be_liveness_new(irg);
447

448
449
	edges_deactivate(irg);
	edges_activate(irg);
450
451
452
453

	/* set the current graph (this is important for several firm functions) */
	current_ir_graph = irg;

454
455
	/* we do this before critical edge split. As this produces less returns,
	   because sometimes (= 164.gzip) multiple returns are slower */
456
	normalize_n_returns(irg);
Sebastian Hack's avatar
Sebastian Hack committed
457

Sebastian Hack's avatar
Sebastian Hack committed
458
	/* Remove critical edges */
459
	remove_critical_cf_edges_ex(irg, /*ignore_exception_edges=*/0);
Sebastian Hack's avatar
Sebastian Hack committed
460

461
462
463
464
	/* For code generation all unreachable code and Bad nodes should be gone */
	remove_unreachable_code(irg);
	remove_bads(irg);

Sebastian Hack's avatar
Sebastian Hack committed
465
	/* Ensure, that the ir_edges are computed. */
466
	assure_edges(irg);
Sebastian Hack's avatar
Sebastian Hack committed
467

468
	be_info_init_irg(irg);
469

470
	dump(DUMP_INITIAL, irg, "prepared");
Sebastian Hack's avatar
Sebastian Hack committed
471
472
}

Matthias Braun's avatar
Matthias Braun committed
473
int be_timing;
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503

static const char *get_timer_name(be_timer_id_t id)
{
	switch (id) {
	case T_ABI:            return "abi";
	case T_CODEGEN:        return "codegen";
	case T_RA_PREPARATION: return "ra_preparation";
	case T_SCHED:          return "sched";
	case T_CONSTR:         return "constr";
	case T_FINISH:         return "finish";
	case T_EMIT:           return "emit";
	case T_VERIFY:         return "verify";
	case T_OTHER:          return "other";
	case T_HEIGHTS:        return "heights";
	case T_LIVE:           return "live";
	case T_EXECFREQ:       return "execfreq";
	case T_SSA_CONSTR:     return "ssa_constr";
	case T_RA_EPILOG:      return "ra_epilog";
	case T_RA_CONSTR:      return "ra_constr";
	case T_RA_SPILL:       return "ra_spill";
	case T_RA_SPILL_APPLY: return "ra_spill_apply";
	case T_RA_COLOR:       return "ra_color";
	case T_RA_IFG:         return "ra_ifg";
	case T_RA_COPYMIN:     return "ra_copymin";
	case T_RA_SSA:         return "ra_ssa";
	case T_RA_OTHER:       return "ra_other";
	}
	return "unknown";
}
ir_timer_t *be_timers[T_LAST+1];
504

505
506
void be_lower_for_target(void)
{
Michael Beck's avatar
Michael Beck committed
507
	size_t i;
508

509
510
	initialize_isa();

511
512
	isa_if->lower_for_target();
	/* set the phase to low */
Michael Beck's avatar
Michael Beck committed
513
514
	for (i = get_irp_n_irgs(); i > 0;) {
		ir_graph *irg = get_irp_irg(--i);
515
516
		assert(!irg_is_constrained(irg, IR_GRAPH_CONSTRAINT_TARGET_LOWERED));
		add_irg_constraints(irg, IR_GRAPH_CONSTRAINT_TARGET_LOWERED);
517
518
519
	}
}

Michael Beck's avatar
Michael Beck committed
520
521
522
523
/**
 * The Firm backend main loop.
 * Do architecture specific lowering for all graphs
 * and call the architecture specific code generator.
524
525
 *
 * @param file_handle   the file handle the output will be written to
526
 * @param cup_name      name of the compilation unit
Michael Beck's avatar
Michael Beck committed
527
 */
528
static void be_main_loop(FILE *file_handle, const char *cup_name)
529
{
Adam Szalkowski's avatar
Adam Szalkowski committed
530
	static const char suffix[] = ".prof";
531

532
533
534
	size_t        i;
	size_t        num_irgs;
	size_t        num_birgs;
535
536
537
538
	be_main_env_t env;
	char          prof_filename[256];
	be_irg_t      *birgs;
	arch_env_t    *arch_env;
539

Matthias Braun's avatar
Matthias Braun committed
540
541
	be_timing = (be_options.timing == BE_TIME_ON);

542
	/* perform target lowering if it didn't happen yet */
543
	if (get_irp_n_irgs() > 0 && !irg_is_constrained(get_irp_irg(0), IR_GRAPH_CONSTRAINT_TARGET_LOWERED))
544
545
		be_lower_for_target();

Matthias Braun's avatar
Matthias Braun committed
546
	if (be_timing) {
547
548
549
		for (i = 0; i < T_LAST+1; ++i) {
			be_timers[i] = ir_timer_new();
		}
550
	}
551

552
553
554
555
	be_init_env(&env, cup_name);

	be_emit_init(file_handle);
	be_gas_begin_compilation_unit(&env);
556

557
558
	arch_env = env.arch_env;

Christian Würdig's avatar
Christian Würdig committed
559
	/* we might need 1 birg more for instrumentation constructor */
560
561
	num_irgs = get_irp_n_irgs();
	birgs    = ALLOCAN(be_irg_t, num_irgs + 1);
562

563
564
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
565
	/* First: initialize all birgs */
566
567
568
569
570
571
572
	num_birgs = 0;
	for (i = 0; i < num_irgs; ++i) {
		ir_graph  *irg    = get_irp_irg(i);
		ir_entity *entity = get_irg_entity(irg);
		if (get_entity_linkage(entity) & IR_LINKAGE_NO_CODEGEN)
			continue;
		initialize_birg(&birgs[num_birgs++], irg, &env);
573
	}
574
	arch_env_handle_intrinsics(arch_env);
Michael Beck's avatar
Michael Beck committed
575

Christian Würdig's avatar
Christian Würdig committed
576
577
578
579
	/*
		Get the filename for the profiling data.
		Beware: '\0' is already included in sizeof(suffix)
	*/
580
581
582
	sprintf(prof_filename, "%.*s%s",
	        (int)(sizeof(prof_filename) - sizeof(suffix)), cup_name, suffix);

583
	bool have_profile = false;
584
585
586
587
588
	if (be_options.opt_profile_use) {
		bool res = ir_profile_read(prof_filename);
		if (!res) {
			fprintf(stderr, "Warning: Couldn't read profile data '%s'\n",
			        prof_filename);
589
590
591
592
		} else {
			ir_create_execfreqs_from_profile();
			ir_profile_free();
			have_profile = true;
593
594
		}
	}
595

596
	if (num_birgs > 0 && be_options.opt_profile_generate) {
597
		ir_graph *const prof_init_irg = ir_profile_instrument(prof_filename);
598
		assert(prof_init_irg->be_data == NULL);
599
600
		initialize_birg(&birgs[num_birgs], prof_init_irg, &env);
		num_birgs++;
601
602
603
604
		num_irgs++;
		assert(num_irgs == get_irp_n_irgs());
	}

Matthias Braun's avatar
Matthias Braun committed
605
606
607
	for (be_timer_id_t t = T_FIRST; t < T_LAST+1; ++t) {
		ir_timer_init_parent(be_timers[t]);
	}
608
609
610
611
612
613
614
	if (!have_profile) {
		be_timer_push(T_EXECFREQ);
		for (i = 0; i < num_irgs; ++i) {
			ir_graph *irg = get_irp_irg(i);
			ir_estimate_execfreq(irg);
		}
		be_timer_pop(T_EXECFREQ);
615
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
616

617
	/* For all graphs */
618
619
620
621
622
	for (i = 0; i < num_irgs; ++i) {
		ir_graph  *const irg    = get_irp_irg(i);
		ir_entity *const entity = get_irg_entity(irg);
		if (get_entity_linkage(entity) & IR_LINKAGE_NO_CODEGEN)
			continue;
Sebastian Hack's avatar
Sebastian Hack committed
623

624
625
626
		/* set the current graph (this is important for several firm functions) */
		current_ir_graph = irg;

627
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
628
629
630
			stat_ev_ctx_push_fmt("bemain_irg", "%+F", irg);
			stat_ev_ull("bemain_insns_start", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_start", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
631
		}
632

633
		/* stop and reset timers */
634
		be_timer_push(T_OTHER);
635

636
		/* Verify the initial graph */
637
		be_timer_push(T_VERIFY);
638
639
640
641
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
642
		}
643
		be_timer_pop(T_VERIFY);
644

645
		/* get a code generator for this graph. */
646
647
		if (arch_env->impl->init_graph)
			arch_env->impl->init_graph(irg);
648
649

		/* some transformations need to be done before abi introduce */
650
651
		if (arch_env->impl->before_abi != NULL)
			arch_env->impl->before_abi(irg);
652

Sebastian Hack's avatar
Sebastian Hack committed
653
		/* implement the ABI conventions. */
654
		if (!arch_env->custom_abi) {
655
656
657
			be_timer_push(T_ABI);
			be_abi_introduce(irg);
			be_timer_pop(T_ABI);
658
659
			dump(DUMP_ABI, irg, "abi");
		}
660

Andreas Zwinkau's avatar
Andreas Zwinkau committed
661
662
663
		/* We can't have Bad-blocks or critical edges in the backend.
		 * Before removing Bads, we remove unreachable code. */
		optimize_graph_df(irg);
664
		remove_critical_cf_edges(irg);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
665
		remove_bads(irg);
666

667
668
669
		/* We often have dead code reachable through out-edges here. So for
		 * now we rebuild edges (as we need correct user count for code
		 * selection) */
670
671
672
		edges_deactivate(irg);
		edges_activate(irg);

673
		dump(DUMP_PREPARED, irg, "before-code-selection");
674

675
		/* perform codeselection */
676
		be_timer_push(T_CODEGEN);
677
678
		if (arch_env->impl->prepare_graph != NULL)
			arch_env->impl->prepare_graph(irg);
679
		be_timer_pop(T_CODEGEN);
Sebastian Hack's avatar
Sebastian Hack committed
680

681
682
		dump(DUMP_PREPARED, irg, "code-selection");

683
		/* disabled for now, fails for EmptyFor.c and XXEndless.c */
684
		/* be_live_chk_compare(irg); */
685

Christian Würdig's avatar
Christian Würdig committed
686
		/* schedule the irg */
687
		be_timer_push(T_SCHED);
688
		be_schedule_graph(irg);
689
		be_timer_pop(T_SCHED);
Sebastian Hack's avatar
Sebastian Hack committed
690

691
		dump(DUMP_SCHED, irg, "sched");
Christian Würdig's avatar
Christian Würdig committed
692

Christian Würdig's avatar
Christian Würdig committed
693
		/* check schedule */
694
		be_timer_push(T_VERIFY);
695
		be_sched_verify(irg, be_options.verify_option);
696
		be_timer_pop(T_VERIFY);
697

Christian Würdig's avatar
Christian Würdig committed
698
		/* introduce patterns to assure constraints */
699
		be_timer_push(T_CONSTR);
700
		/* we switch off optimizations here, because they might cause trouble */
701
		optimization_state_t state;
702
		save_optimization_state(&state);
703
		set_optimize(0);
704
705
		set_opt_cse(0);

706
707
		/* add Keeps for should_be_different constrained nodes  */
		/* beware: needs schedule due to usage of be_ssa_constr */
708
		assure_constraints(irg);
709
		be_timer_pop(T_CONSTR);
710

711
		dump(DUMP_SCHED, irg, "assured");
Christian Würdig's avatar
Christian Würdig committed
712

713
		/* stuff needs to be done after scheduling but before register allocation */
714
		be_timer_push(T_RA_PREPARATION);
715
716
		if (arch_env->impl->before_ra != NULL)
			arch_env->impl->before_ra(irg);
717
		be_timer_pop(T_RA_PREPARATION);
718

Sebastian Hack's avatar
Sebastian Hack committed
719
		/* connect all stack modifying nodes together (see beabi.c) */
720
		be_timer_push(T_ABI);
721
		be_abi_fix_stack_nodes(irg);
722
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
723

724
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
725

Christian Würdig's avatar
Christian Würdig committed
726
		/* check schedule */
727
		be_timer_push(T_VERIFY);
728
		be_sched_verify(irg, be_options.verify_option);
729
		be_timer_pop(T_VERIFY);
Sebastian Hack's avatar
Sebastian Hack committed
730

731
		if (stat_ev_enabled) {
732
			stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
Matthias Braun's avatar
Matthias Braun committed
733
734
			stat_ev_ull("bemain_insns_before_ra", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_before_ra", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
735
		}
736

737
		/* Do register allocation */
738
		be_allocate_registers(irg);
739

740
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
741

742
		dump(DUMP_RA, irg, "ra");
Christian Würdig's avatar
Christian Würdig committed
743

744
		be_timer_push(T_FINISH);
Matthias Braun's avatar
Matthias Braun committed
745
746
		if (arch_env->impl->finish_graph != NULL)
			arch_env->impl->finish_graph(irg);
747
		be_timer_pop(T_FINISH);
748

749
		dump(DUMP_FINAL, irg, "finish");
750

751
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
752
753
			stat_ev_ull("bemain_insns_finish", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_finish", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
754
755
		}

756
		/* check schedule and register allocation */
757
		be_timer_push(T_VERIFY);
758
759
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
760
761
			be_verify_schedule(irg);
			be_verify_register_allocation(irg);
762
763
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
764
765
			assert(be_verify_schedule(irg) && "Schedule verification failed");
			assert(be_verify_register_allocation(irg)
766
			       && "register allocation verification failed");
767

768
		}
769
		be_timer_pop(T_VERIFY);
770

Christian Würdig's avatar
Christian Würdig committed
771
		/* emit assembler code */
772
		be_timer_push(T_EMIT);
773
774
		if (arch_env->impl->emit != NULL)
			arch_env->impl->emit(irg);
775
		be_timer_pop(T_EMIT);
Christian Würdig's avatar
Christian Würdig committed
776

777
		dump(DUMP_FINAL, irg, "end");
Christian Würdig's avatar
Christian Würdig committed
778

779
		restore_optimization_state(&state);
780

781
782
783
		be_timer_pop(T_OTHER);

		if (be_timing) {
784
			be_timer_id_t t;
785
			if (stat_ev_enabled) {
786
				for (t = T_FIRST; t < T_LAST+1; ++t) {
787
788
789
790
791
					char buf[128];
					snprintf(buf, sizeof(buf), "bemain_time_%s",
					         get_timer_name(t));
					stat_ev_dbl(buf, ir_timer_elapsed_usec(be_timers[i]));
				}
Matthias Braun's avatar
Matthias Braun committed
792
			} else {
793
794
				printf("==>> IRG %s <<==\n",
				       get_entity_name(get_irg_entity(irg)));
795
				for (t = T_FIRST; t < T_LAST+1; ++t) {
796
					double val = ir_timer_elapsed_usec(be_timers[t]) / 1000.0;
797
					printf("%-20s: %10.3f msec\n", get_timer_name(t), val);
798
				}
799
			}
800
			for (t = T_FIRST; t < T_LAST+1; ++t) {
801
802
803
				ir_timer_reset(be_timers[t]);
			}
		}
Michael Beck's avatar
BugFix:    
Michael Beck committed
804

805
		be_free_birg(irg);
Sebastian Hack's avatar
Sebastian Hack committed
806
		stat_ev_ctx_pop("bemain_irg");
807
	}
808

809
810
811
	be_gas_end_compilation_unit(&env);
	be_emit_exit();

812
	arch_env_end_codegeneration(arch_env);
813

Sebastian Hack's avatar
Sebastian Hack committed
814
	be_done_env(&env);
815
816

	be_info_free();
817
818
}

Michael Beck's avatar
Michael Beck committed
819
/* Main interface to the frontend. */
820
void be_main(FILE *file_handle, const char *cup_name)
821
{
Matthias Braun's avatar
Matthias Braun committed
822
	ir_timer_t *t = NULL;
823

824
	if (be_options.timing == BE_TIME_ON) {
825
		t = ir_timer_new();
826

Matthias Braun's avatar
Matthias Braun committed
827
		if (ir_timer_enter_high_priority()) {
828
829
830
			fprintf(stderr, "Warning: Could not enter high priority mode.\n");
		}

Matthias Braun's avatar
Matthias Braun committed
831
		ir_timer_reset_and_start(t);
832
	}
833

Sebastian Hack's avatar
Sebastian Hack committed
834
	if (be_options.statev) {
835
		const char *dot = strrchr(cup_name, '.');
Sebastian Hack's avatar
Sebastian Hack committed
836
		const char *pos = dot ? dot : cup_name + strlen(cup_name);
837
		char       *buf = ALLOCAN(char, pos - cup_name + 1);
Sebastian Hack's avatar
Sebastian Hack committed
838
		strncpy(buf, cup_name, pos - cup_name);
Sebastian Hack's avatar
Sebastian Hack committed
839
		buf[pos - cup_name] = '\0';
Sebastian Hack's avatar
Sebastian Hack committed
840