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
#include "obst.h"
21
#include "statev.h"
Sebastian Hack's avatar
Sebastian Hack committed
22
#include "irprog.h"
Sebastian Hack's avatar
Sebastian Hack committed
23
#include "irgopt.h"
Daniel Grund's avatar
Daniel Grund committed
24
#include "irdump.h"
Sebastian Hack's avatar
Sebastian Hack committed
25
26
#include "irdom_t.h"
#include "iredges_t.h"
27
#include "irloop_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
28
#include "irtools.h"
29
#include "irverify.h"
Matthias Braun's avatar
Matthias Braun committed
30
#include "iroptimize.h"
Christian Würdig's avatar
Christian Würdig committed
31
#include "firmstat.h"
32
#include "execfreq_t.h"
33
#include "irprofile.h"
34
#include "irpass_t.h"
35
#include "ircons.h"
Sebastian Hack's avatar
Sebastian Hack committed
36

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

61
62
#define NEW_ID(s) new_id_from_chars(s, sizeof(s) - 1)

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

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

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

Christian Würdig's avatar
Christian Würdig committed
96
/* verify options. */
97
98
99
100
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
101
	{ NULL,     0 }
Christian Würdig's avatar
Christian Würdig committed
102
};
103

Sebastian Hack's avatar
Sebastian Hack committed
104
static lc_opt_enum_mask_var_t dump_var = {
105
	&be_options.dump_flags, dump_items
106
107
};

108
109
static lc_opt_enum_int_var_t verify_var = {
	&be_options.verify_option, verify_items
Christian Würdig's avatar
Christian Würdig committed
110
111
};

Sebastian Hack's avatar
Sebastian Hack committed
112
static const lc_opt_table_entry_t be_main_options[] = {
113
114
115
	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),
116
	LC_OPT_ENT_ENUM_INT ("verify",     "verify the backend irg",                              &verify_var),
117
	LC_OPT_ENT_BOOL     ("time",       "get backend timing statistics",                       &be_options.timing),
118
119
	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),
120
	LC_OPT_ENT_BOOL     ("statev",     "dump statistic events",                               &be_options.statev),
121
	LC_OPT_ENT_STR      ("filtev",     "filter for stat events (regex if support is active",  &be_options.filtev),
122
	LC_OPT_ENT_BOOL     ("verboseasm", "enable verbose assembler output",                     &be_options.verbose_asm),
123

124
125
	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),
126
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
127
128
};

129
130
static be_module_list_entry_t *isa_ifs         = NULL;
static bool                    isa_initialized = false;
131

132
asm_constraint_flags_t asm_constraint_flags[256];
133

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

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

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

211
asm_constraint_flags_t be_parse_asm_constraints(const char *constraint)
212
{
213
	asm_constraint_flags_t  flags = ASM_CONSTRAINT_FLAG_NONE;
214
215
216
	const char             *c;
	asm_constraint_flags_t  tflags;

217
218
	initialize_isa();

219
220
221
222
	for (c = constraint; *c != '\0'; ++c) {
		switch (*c) {
		case '#':
			/* 'comment' stuff */
223
			while (*c != 0 && *c != ',')
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
				++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 {
240
				flags |= isa_if->parse_asm_constraint(&c);
241
242
243
244
245
			}
			break;
		}
	}

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

	return flags;
}

266
int be_is_valid_clobber(const char *clobber)
267
{
268
269
	initialize_isa();

270
271
272
	/* 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)
273
		return 1;
274
275
	/* cc (condition code) is always valid */
	if (strcmp(clobber, "cc") == 0)
276
		return 1;
277

278
	return isa_if->is_valid_clobber(clobber);
279
280
}

281
282
void be_register_isa_if(const char *name, const arch_isa_if_t *isa)
{
283
	if (isa_if == NULL)
284
285
286
287
288
		isa_if = isa;

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

289
static void be_opt_register(void)
Sebastian Hack's avatar
Sebastian Hack committed
290
{
291
	lc_opt_entry_t *be_grp;
292
293
	static int run_once = 0;

294
	if (run_once)
295
		return;
296
	run_once = 1;
297

298
299
	be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_add_table(be_grp, be_main_options);
300
301
302

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

	be_init_modules();
305
}
Sebastian Hack's avatar
Sebastian Hack committed
306

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

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

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

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

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

Manuel Mohr's avatar
Manuel Mohr committed
349
350
351
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
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;
}

379
380
381
382
383
384
/**
 * 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
 */
385
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
386
{
Sebastian Hack's avatar
Sebastian Hack committed
387
	memset(env, 0, sizeof(*env));
388
	env->ent_trampoline_map   = pmap_create();
389
	env->pic_trampolines_type = new_type_segment(NEW_ID("$PIC_TRAMPOLINE_TYPE"), tf_none);
390
	env->ent_pic_symbol_map   = pmap_create();
391
	env->pic_symbols_type     = new_type_segment(NEW_ID("$PIC_SYMBOLS_TYPE"), tf_none);
392
	env->cup_name             = compilation_unit_name;
393
	env->arch_env             = isa_if->begin_codegeneration();
394
395

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

397
	memset(asm_constraint_flags, 0, sizeof(asm_constraint_flags));
Sebastian Hack's avatar
Sebastian Hack committed
398
399

	return env;
400
401
}

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

413
414
415
416
417
418
419
420
421
/**
 * 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
 */
422
static void dump(int mask, ir_graph *irg, const char *suffix)
Sebastian Hack's avatar
Sebastian Hack committed
423
{
424
	if (be_options.dump_flags & mask)
425
		dump_ir_graph(irg, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
426
}
427

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

436
437
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
438
439
	irg->be_data = birg;

440
441
	memset(birg, 0, sizeof(*birg));
	birg->main_env = env;
442
	obstack_init(&birg->obst);
443
	birg->lv = be_liveness_new(irg);
444

445
446
	edges_deactivate(irg);
	edges_activate(irg);
447
448
449
450

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

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

Sebastian Hack's avatar
Sebastian Hack committed
455
	/* Remove critical edges */
456
	remove_critical_cf_edges_ex(irg, /*ignore_exception_edges=*/0);
Sebastian Hack's avatar
Sebastian Hack committed
457

458
459
460
461
	/* 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
462
	/* Ensure, that the ir_edges are computed. */
463
	assure_edges(irg);
Sebastian Hack's avatar
Sebastian Hack committed
464

465
	be_info_init_irg(irg);
466

467
	dump(DUMP_INITIAL, irg, "prepared");
Sebastian Hack's avatar
Sebastian Hack committed
468
469
}

Matthias Braun's avatar
Matthias Braun committed
470
int be_timing;
471
472
473
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

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];
501

502
503
void be_lower_for_target(void)
{
Michael Beck's avatar
Michael Beck committed
504
	size_t i;
505

506
507
	initialize_isa();

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

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

529
530
531
	size_t        i;
	size_t        num_irgs;
	size_t        num_birgs;
532
533
534
535
	be_main_env_t env;
	char          prof_filename[256];
	be_irg_t      *birgs;
	arch_env_t    *arch_env;
536

Matthias Braun's avatar
Matthias Braun committed
537
538
	be_timing = (be_options.timing == BE_TIME_ON);

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

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

549
550
551
552
	be_init_env(&env, cup_name);

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

554
555
	arch_env = env.arch_env;

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

560
561
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
562
	/* First: initialize all birgs */
563
564
565
566
567
568
569
	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);
570
	}
571
	arch_env_handle_intrinsics(arch_env);
Michael Beck's avatar
Michael Beck committed
572

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

580
	bool have_profile = false;
581
582
583
584
585
	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);
586
587
588
589
		} else {
			ir_create_execfreqs_from_profile();
			ir_profile_free();
			have_profile = true;
590
591
		}
	}
592

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

Matthias Braun's avatar
Matthias Braun committed
602
603
604
	for (be_timer_id_t t = T_FIRST; t < T_LAST+1; ++t) {
		ir_timer_init_parent(be_timers[t]);
	}
605
606
607
608
609
610
611
	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);
612
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
613

614
	/* For all graphs */
615
616
617
618
619
	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
620

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

624
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
625
626
627
			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
628
		}
629

630
		/* stop and reset timers */
631
		be_timer_push(T_OTHER);
632

633
		/* Verify the initial graph */
634
		be_timer_push(T_VERIFY);
635
636
637
638
		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");
639
		}
640
		be_timer_pop(T_VERIFY);
641

642
		/* get a code generator for this graph. */
643
644
		if (arch_env->impl->init_graph)
			arch_env->impl->init_graph(irg);
645
646

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

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

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

664
665
666
		/* 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) */
667
668
669
		edges_deactivate(irg);
		edges_activate(irg);

670
		dump(DUMP_PREPARED, irg, "before-code-selection");
671

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

678
679
		dump(DUMP_PREPARED, irg, "code-selection");

680
		/* disabled for now, fails for EmptyFor.c and XXEndless.c */
681
		/* be_live_chk_compare(irg); */
682

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

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

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

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

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

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

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

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

721
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
722

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

728
		if (stat_ev_enabled) {
729
			stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
Matthias Braun's avatar
Matthias Braun committed
730
731
			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
732
		}
733

734
		/* Do register allocation */
735
		be_allocate_registers(irg);
736

737
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
738

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

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

746
		dump(DUMP_FINAL, irg, "finish");
747

748
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
749
750
			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
751
752
		}

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

765
		}
766
		be_timer_pop(T_VERIFY);
767

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

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

776
		restore_optimization_state(&state);
777

778
779
780
		be_timer_pop(T_OTHER);

		if (be_timing) {
781
			be_timer_id_t t;
782
			if (stat_ev_enabled) {
783
				for (t = T_FIRST; t < T_LAST+1; ++t) {
784
785
786
787
788
					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
789
			} else {
790
791
				printf("==>> IRG %s <<==\n",
				       get_entity_name(get_irg_entity(irg)));
792
				for (t = T_FIRST; t < T_LAST+1; ++t) {
793
					double val = ir_timer_elapsed_usec(be_timers[t]) / 1000.0;
794
					printf("%-20s: %10.3f msec\n", get_timer_name(t), val);
795
				}
796
			}
797
			for (t = T_FIRST; t < T_LAST+1; ++t) {
798
799
800
				ir_timer_reset(be_timers[t]);
			}
		}
Michael Beck's avatar
BugFix:    
Michael Beck committed
801

802
		be_free_birg(irg);
Sebastian Hack's avatar
Sebastian Hack committed
803
		stat_ev_ctx_pop("bemain_irg");
804
	}
805

806
807
808
	be_gas_end_compilation_unit(&env);
	be_emit_exit();

809
	arch_env_end_codegeneration(arch_env);
810

Sebastian Hack's avatar
Sebastian Hack committed
811
	be_done_env(&env);
812
813

	be_info_free();
814
815
}

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

821
	if (be_options.timing == BE_TIME_ON) {
822
		t = ir_timer_new();
823

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

Matthias Braun's avatar
Matthias Braun committed
828
		ir_timer_reset_and_start(t);
829
	}
830

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

Sebastian Hack's avatar
Sebastian Hack committed
838
		be_options.statev = 1;
839
		stat_ev_begin(buf, be_options.filtev);