bemain.c 25.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
 * @file
 * @brief       Main Backend driver.
 * @author      Sebastian Hack
 * @date        25.11.2004
 * @version     $Id$
26
 */
Michael Beck's avatar
Michael Beck committed
27
#include "config.h"
28

Sebastian Hack's avatar
Sebastian Hack committed
29
#include <stdarg.h>
30
#include <stdio.h>
31

Matthias Braun's avatar
Matthias Braun committed
32
33
#include "lc_opts.h"
#include "lc_opts_enum.h"
34

Sebastian Hack's avatar
Sebastian Hack committed
35
36
37
38
#include "obst.h"
#include "bitset.h"

#include "irprog.h"
Sebastian Hack's avatar
Sebastian Hack committed
39
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
40
#include "irgraph.h"
Daniel Grund's avatar
Daniel Grund committed
41
#include "irdump.h"
Sebastian Hack's avatar
Sebastian Hack committed
42
43
#include "irdom_t.h"
#include "iredges_t.h"
44
#include "irloop_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
45
#include "irtools.h"
46
#include "irverify.h"
47
#include "irprintf.h"
Matthias Braun's avatar
Matthias Braun committed
48
#include "iroptimize.h"
Christian Würdig's avatar
Christian Würdig committed
49
#include "firmstat.h"
50
#include "execfreq.h"
51
#include "irprofile.h"
52
#include "irpass_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
53

54
#include "bearch.h"
Sebastian Hack's avatar
Sebastian Hack committed
55
#include "be_t.h"
56
#include "bemodule.h"
57
#include "beutil.h"
58
#include "benode.h"
59
#include "beirgmod.h"
60
#include "besched.h"
61
62
#include "belistsched.h"
#include "belive_t.h"
63
64
65
#include "bera.h"
#include "bechordal_t.h"
#include "beifg.h"
Daniel Grund's avatar
Daniel Grund committed
66
#include "becopyopt.h"
67
#include "becopystat.h"
68
#include "bessadestr.h"
Sebastian Hack's avatar
Sebastian Hack committed
69
#include "beabi.h"
Christian Würdig's avatar
Christian Würdig committed
70
#include "belower.h"
71
#include "bestat.h"
72
#include "beverify.h"
73
#include "be_dbgout.h"
74
#include "beirg.h"
75
#include "bestack.h"
76
#include "beemitter.h"
Sebastian Hack's avatar
Sebastian Hack committed
77

78
79
#define NEW_ID(s) new_id_from_chars(s, sizeof(s) - 1)

Sebastian Hack's avatar
Sebastian Hack committed
80
/* options visible for anyone */
Sebastian Hack's avatar
Sebastian Hack committed
81
static be_options_t be_options = {
82
	DUMP_NONE,                         /* dump flags */
83
	BE_TIME_OFF,                       /* no timing */
84
85
	false,                             /* profile_generate */
	false,                             /* profile_use */
Michael Beck's avatar
Michael Beck committed
86
	0,                                 /* try to omit frame pointer */
87
	0,                                 /* create PIC code */
88
	BE_VERIFY_WARN,                    /* verification level: warn */
Sebastian Hack's avatar
Sebastian Hack committed
89
	"",                                /* ilp server */
Christian Würdig's avatar
Christian Würdig committed
90
	"cplex",                           /* ilp solver */
Sebastian Hack's avatar
Sebastian Hack committed
91
	0,                                 /* enable statistic event dumping */
92
	"",                                /* print stat events */
Sebastian Hack's avatar
Sebastian Hack committed
93
94
95
};

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

Sebastian Hack's avatar
Sebastian Hack committed
98
99
/* possible dumping options */
static const lc_opt_enum_mask_items_t dump_items[] = {
100
	{ "none",       DUMP_NONE },
Sebastian Hack's avatar
Sebastian Hack committed
101
	{ "initial",    DUMP_INITIAL },
102
	{ "abi",        DUMP_ABI    },
Sebastian Hack's avatar
Sebastian Hack committed
103
104
	{ "sched",      DUMP_SCHED  },
	{ "prepared",   DUMP_PREPARED },
105
	{ "regalloc",   DUMP_RA },
Sebastian Hack's avatar
Sebastian Hack committed
106
	{ "final",      DUMP_FINAL },
107
108
	{ "be",         DUMP_BE },
	{ "all",        2 * DUMP_BE - 1 },
Sebastian Hack's avatar
Sebastian Hack committed
109
110
111
	{ NULL,         0 }
};

Christian Würdig's avatar
Christian Würdig committed
112
/* verify options. */
113
114
115
116
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
117
	{ NULL,     0 }
Christian Würdig's avatar
Christian Würdig committed
118
};
119

Sebastian Hack's avatar
Sebastian Hack committed
120
static lc_opt_enum_mask_var_t dump_var = {
121
	&be_options.dump_flags, dump_items
122
123
};

124
125
static lc_opt_enum_int_var_t verify_var = {
	&be_options.verify_option, verify_items
Christian Würdig's avatar
Christian Würdig committed
126
127
};

Sebastian Hack's avatar
Sebastian Hack committed
128
static const lc_opt_table_entry_t be_main_options[] = {
129
130
131
	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),
132
	LC_OPT_ENT_ENUM_INT ("verify",     "verify the backend irg",                              &verify_var),
133
	LC_OPT_ENT_BOOL     ("time",       "get backend timing statistics",                       &be_options.timing),
134
135
	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),
136
	LC_OPT_ENT_BOOL     ("statev",     "dump statistic events",                               &be_options.statev),
137
	LC_OPT_ENT_STR      ("filtev",     "filter for stat events (regex if support is active",   be_options.filtev, sizeof(be_options.filtev)),
138

139
140
	LC_OPT_ENT_STR ("ilp.server", "the ilp server name", be_options.ilp_server, sizeof(be_options.ilp_server)),
	LC_OPT_ENT_STR ("ilp.solver", "the ilp solver name", be_options.ilp_solver, sizeof(be_options.ilp_solver)),
141
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
142
143
};

144
145
static be_module_list_entry_t *isa_ifs = NULL;

146

147
asm_constraint_flags_t asm_constraint_flags[256];
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

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

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

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

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

	return flags;
}

263
int be_is_valid_clobber(const char *clobber)
264
265
266
267
{
	/* 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)
268
		return 1;
269
270
	/* cc (condition code) is always valid */
	if (strcmp(clobber, "cc") == 0)
271
		return 1;
272

273
	return isa_if->is_valid_clobber(clobber);
274
275
}

276
277
void be_register_isa_if(const char *name, const arch_isa_if_t *isa)
{
278
	if (isa_if == NULL)
279
280
281
282
283
		isa_if = isa;

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

Sebastian Hack's avatar
Sebastian Hack committed
284
285
void be_opt_register(void)
{
286
	lc_opt_entry_t *be_grp;
287
288
	static int run_once = 0;

289
	if (run_once)
290
		return;
291
	run_once = 1;
292

293
294
	be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_add_table(be_grp, be_main_options);
295
296
297

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

	be_init_modules();
300
}
Sebastian Hack's avatar
Sebastian Hack committed
301

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

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

323
324
/* Initialize the Firm backend. Must be run first in init_firm()! */
void firm_be_init(void)
325
{
Sebastian Hack's avatar
Sebastian Hack committed
326
	be_opt_register();
327
	be_init_modules();
328
}
329

yb9976's avatar
yb9976 committed
330
331
332
333
334
335
/* Finalize the Firm backend. */
void firm_be_finish(void)
{
	be_quit_modules();
}

336
337
338
/* Returns the backend parameter */
const backend_params *be_get_backend_param(void)
{
339
	return isa_if->get_params();
340
341
}

342
343
344
345
346
347
/**
 * 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
 */
348
static be_main_env_t *be_init_env(be_main_env_t *env, FILE *file_handle)
Sebastian Hack's avatar
Sebastian Hack committed
349
{
Sebastian Hack's avatar
Sebastian Hack committed
350
	memset(env, 0, sizeof(*env));
351
352
353
354
355
	env->options              = &be_options;
	env->ent_trampoline_map   = pmap_create();
	env->pic_trampolines_type = new_type_class(NEW_ID("$PIC_TRAMPOLINE_TYPE"));
	env->ent_pic_symbol_map   = pmap_create();
	env->pic_symbols_type     = new_type_struct(NEW_ID("$PIC_SYMBOLS_TYPE"));
356
357
358
359

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

361
	memset(asm_constraint_flags, 0, sizeof(asm_constraint_flags));
362
	env->arch_env = arch_env_init(isa_if, file_handle, env);
Sebastian Hack's avatar
Sebastian Hack committed
363
364

	return env;
365
366
}

367
368
369
/**
 * Called when the be_main_env_t can be destroyed.
 */
Sebastian Hack's avatar
Sebastian Hack committed
370
static void be_done_env(be_main_env_t *env)
371
{
372
373
	pmap_destroy(env->ent_trampoline_map);
	pmap_destroy(env->ent_pic_symbol_map);
374
375
	free_type(env->pic_trampolines_type);
	free_type(env->pic_symbols_type);
Sebastian Hack's avatar
Sebastian Hack committed
376
}
Sebastian Hack's avatar
Sebastian Hack committed
377

378
379
380
381
382
383
384
385
386
/**
 * 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
 */
387
static void dump(int mask, ir_graph *irg, const char *suffix)
Sebastian Hack's avatar
Sebastian Hack committed
388
{
389
	if (be_options.dump_flags & mask)
390
		dump_ir_graph(irg, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
391
}
392

Michael Beck's avatar
Michael Beck committed
393
/**
394
 * Prepare a backend graph for code generation and initialize its irg
Michael Beck's avatar
Michael Beck committed
395
 */
396
static void initialize_birg(be_irg_t *birg, ir_graph *irg, be_main_env_t *env)
Sebastian Hack's avatar
Sebastian Hack committed
397
{
398
399
400
	/* don't duplicate locals in backend when dumping... */
	ir_remove_dump_flags(ir_dump_flag_consts_local);

401
402
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
403
404
	irg->be_data = birg;

405
406
407
	memset(birg, 0, sizeof(*birg));
	birg->irg = irg;
	birg->main_env = env;
408
	obstack_init(&birg->obst);
409
410
411
412
413
414
415

	edges_deactivate_kind(irg, EDGE_KIND_DEP);
	edges_activate_kind(irg, EDGE_KIND_DEP);

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

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

Sebastian Hack's avatar
Sebastian Hack committed
420
	/* Remove critical edges */
421
	remove_critical_cf_edges_ex(irg, /*ignore_exception_edges=*/0);
Sebastian Hack's avatar
Sebastian Hack committed
422

Sebastian Hack's avatar
Sebastian Hack committed
423
	/* Ensure, that the ir_edges are computed. */
Sebastian Hack's avatar
Sebastian Hack committed
424
	edges_assure(irg);
Sebastian Hack's avatar
Sebastian Hack committed
425

426
	set_irg_phase_state(irg, phase_backend);
427
	be_info_init_irg(irg);
428

429
	dump(DUMP_INITIAL, irg, "prepared");
Sebastian Hack's avatar
Sebastian Hack committed
430
431
}

Matthias Braun's avatar
Matthias Braun committed
432
int be_timing;
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

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_PROLOG:      return "ra_prolog";
	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];
464

465
466
void be_lower_for_target(void)
{
Michael Beck's avatar
Michael Beck committed
467
	size_t i;
468
469
470

	isa_if->lower_for_target();
	/* set the phase to low */
Michael Beck's avatar
Michael Beck committed
471
472
	for (i = get_irp_n_irgs(); i > 0;) {
		ir_graph *irg = get_irp_irg(--i);
473
474
475
476
477
		set_irg_phase_state(irg, phase_low);
	}
	set_irp_phase_state(phase_low);
}

478
479
480
481
482
483
484
485
486
487
488
static void emit_global_asms(void)
{
	size_t n = get_irp_n_asms();
	size_t i;
	for (i = 0; i < n; ++i) {
		be_emit_cstring("#APP\n");
		be_emit_ident(get_irp_asm(i));
		be_emit_cstring("\n#NO_APP\n");
	}
}

Michael Beck's avatar
Michael Beck committed
489
490
491
492
/**
 * The Firm backend main loop.
 * Do architecture specific lowering for all graphs
 * and call the architecture specific code generator.
493
494
 *
 * @param file_handle   the file handle the output will be written to
495
 * @param cup_name      name of the compilation unit
Michael Beck's avatar
Michael Beck committed
496
 */
497
static void be_main_loop(FILE *file_handle, const char *cup_name)
498
{
Adam Szalkowski's avatar
Adam Szalkowski committed
499
	static const char suffix[] = ".prof";
500

Michael Beck's avatar
Michael Beck committed
501
	size_t        i, num_birgs;
502
503
504
505
506
	be_main_env_t env;
	char          prof_filename[256];
	be_irg_t      *birgs;
	ir_graph      **irg_list, **backend_irg_list;
	arch_env_t    *arch_env;
507

Matthias Braun's avatar
Matthias Braun committed
508
509
510
	be_timing = (be_options.timing == BE_TIME_ON);

	if (be_timing) {
511
512
513
		for (i = 0; i < T_LAST+1; ++i) {
			be_timers[i] = ir_timer_new();
		}
514
	}
515

516
	be_init_env(&env, file_handle);
517
	env.cup_name = cup_name;
Sebastian Hack's avatar
Sebastian Hack committed
518

519
	be_dbg_open();
520
	be_dbg_unit_begin(cup_name);
521
	be_dbg_types();
522

523
524
	emit_global_asms();

525
526
	arch_env = env.arch_env;

527
528
	/* backend may provide an ordered list of irgs where code should be
	 * generated for */
Christian Würdig's avatar
Christian Würdig committed
529
	irg_list         = NEW_ARR_F(ir_graph *, 0);
530
	backend_irg_list = arch_env_get_backend_irg_list(arch_env, &irg_list);
531

Christian Würdig's avatar
Christian Würdig committed
532
	/* we might need 1 birg more for instrumentation constructor */
533
	num_birgs = backend_irg_list ? ARR_LEN(backend_irg_list) : get_irp_n_irgs();
534
	birgs     = ALLOCAN(be_irg_t, num_birgs + 1);
535

536
537
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
538
	/* First: initialize all birgs */
539
	for (i = 0; i < num_birgs; ++i) {
540
		ir_graph *irg = backend_irg_list ? backend_irg_list[i] : get_irp_irg(i);
541
542
		initialize_birg(&birgs[i], irg, &env);
	}
543
	arch_env_handle_intrinsics(arch_env);
Christian Würdig's avatar
Christian Würdig committed
544
	DEL_ARR_F(irg_list);
Michael Beck's avatar
Michael Beck committed
545

Christian Würdig's avatar
Christian Würdig committed
546
547
548
549
	/*
		Get the filename for the profiling data.
		Beware: '\0' is already included in sizeof(suffix)
	*/
550
551
552
553
554
555
556
557
558
559
560
561
562
	sprintf(prof_filename, "%.*s%s",
	        (int)(sizeof(prof_filename) - sizeof(suffix)), cup_name, suffix);

	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);
		}
	}
	if (be_options.opt_profile_generate) {
		ir_graph *prof_init_irg
			= ir_profile_instrument(prof_filename);
563
564
		initialize_birg(&birgs[num_birgs], prof_init_irg, &env);
		num_birgs++;
565
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
566

567
	/* For all graphs */
568
	for (i = 0; i < num_birgs; ++i) {
569
		be_irg_t *birg = &birgs[i];
Christian Würdig's avatar
Christian Würdig committed
570
		ir_graph *irg  = birg->irg;
571
		optimization_state_t state;
Sebastian Hack's avatar
Sebastian Hack committed
572

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

576
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
577
578
579
580
			stat_ev_ctx_push_fobj("bemain_irg", irg);
			be_stat_ev("bemain_insns_start", be_count_insns(irg));
			be_stat_ev("bemain_blocks_start", be_count_blocks(irg));
		}
581

582
		/* stop and reset timers */
583
		be_timer_push(T_OTHER);
584

585
		/* Verify the initial graph */
586
		be_timer_push(T_VERIFY);
587
588
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
589
			be_check_dominance(irg);
590
591
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
592
593
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}
594
		be_timer_pop(T_VERIFY);
595

596
		/* get a code generator for this graph. */
597
		arch_env->impl->init_graph(irg);
598
599

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

Sebastian Hack's avatar
Sebastian Hack committed
603
		/* implement the ABI conventions. */
604
		if (!arch_env->custom_abi) {
605
606
607
			be_timer_push(T_ABI);
			be_abi_introduce(irg);
			be_timer_pop(T_ABI);
608
609
			dump(DUMP_ABI, irg, "abi");
		}
610

Andreas Zwinkau's avatar
Andreas Zwinkau committed
611
612
613
		/* We can't have Bad-blocks or critical edges in the backend.
		 * Before removing Bads, we remove unreachable code. */
		optimize_graph_df(irg);
614
		remove_critical_cf_edges(irg);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
615
		remove_bads(irg);
616

617
618
619
		/* 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) */
620
621
622
		edges_deactivate(irg);
		edges_activate(irg);

623
		dump(DUMP_PREPARED, irg, "before-code-selection");
624

625
		if (be_options.verify_option == BE_VERIFY_WARN) {
626
			be_check_dominance(irg);
627
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
628
629
630
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}

631
		/* perform codeselection */
632
		be_timer_push(T_CODEGEN);
633
634
		if (arch_env->impl->prepare_graph != NULL)
			arch_env->impl->prepare_graph(irg);
635
		be_timer_pop(T_CODEGEN);
Sebastian Hack's avatar
Sebastian Hack committed
636

637
		if (be_options.verify_option == BE_VERIFY_WARN) {
638
			be_check_dominance(irg);
639
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
640
641
642
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}

643
644
		dump(DUMP_PREPARED, irg, "code-selection");

645
		be_timer_push(T_EXECFREQ);
646
647
648
		/**
		 * Create execution frequencies from profile data or estimate some
		 */
649
650
		if (ir_profile_has_data())
			birg->exec_freq = ir_create_execfreqs_from_profile(irg);
651
652
653
654
		else {
			/* TODO: edges are corrupt for EDGE_KIND_BLOCK after the local
			 * optimize graph phase merges blocks in the x86 backend */
			edges_deactivate(irg);
655
			birg->exec_freq = compute_execfreq(irg, 10);
656
		}
657
		be_timer_pop(T_EXECFREQ);
658

659
660

		/* disabled for now, fails for EmptyFor.c and XXEndless.c */
661
		/* be_live_chk_compare(irg); */
662

Christian Würdig's avatar
Christian Würdig committed
663
		/* schedule the irg */
664
		be_timer_push(T_SCHED);
665
		be_schedule_graph(irg);
666
		be_timer_pop(T_SCHED);
Sebastian Hack's avatar
Sebastian Hack committed
667

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

Christian Würdig's avatar
Christian Würdig committed
670
		/* check schedule */
671
		be_timer_push(T_VERIFY);
672
		be_sched_verify(irg, be_options.verify_option);
673
		be_timer_pop(T_VERIFY);
674

Christian Würdig's avatar
Christian Würdig committed
675
		/* introduce patterns to assure constraints */
676
		be_timer_push(T_CONSTR);
677
		/* we switch off optimizations here, because they might cause trouble */
678
		save_optimization_state(&state);
679
		set_optimize(0);
680
681
		set_opt_cse(0);

682
683
		/* add Keeps for should_be_different constrained nodes  */
		/* beware: needs schedule due to usage of be_ssa_constr */
684
		assure_constraints(irg);
685
		be_timer_pop(T_CONSTR);
686

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

689
		/* stuff needs to be done after scheduling but before register allocation */
690
		be_timer_push(T_RA_PREPARATION);
691
692
		if (arch_env->impl->before_ra != NULL)
			arch_env->impl->before_ra(irg);
693
		be_timer_pop(T_RA_PREPARATION);
694

Sebastian Hack's avatar
Sebastian Hack committed
695
		/* connect all stack modifying nodes together (see beabi.c) */
696
		be_timer_push(T_ABI);
697
		be_abi_fix_stack_nodes(irg);
698
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
699

700
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
701

Christian Würdig's avatar
Christian Würdig committed
702
		/* check schedule */
703
		be_timer_push(T_VERIFY);
704
		be_sched_verify(irg, be_options.verify_option);
705
		be_timer_pop(T_VERIFY);
Sebastian Hack's avatar
Sebastian Hack committed
706

707
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
708
			stat_ev_dbl("bemain_costs_before_ra",
709
					be_estimate_irg_costs(irg, birg->exec_freq));
Matthias Braun's avatar
Matthias Braun committed
710
711
712
			be_stat_ev("bemain_insns_before_ra", be_count_insns(irg));
			be_stat_ev("bemain_blocks_before_ra", be_count_blocks(irg));
		}
713

714
		/* Do register allocation */
715
		be_allocate_registers(irg);
716

717
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg, birg->exec_freq));
718

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

Christian Würdig's avatar
Christian Würdig committed
721
		/* let the code generator prepare the graph for emitter */
722
		be_timer_push(T_FINISH);
723
724
		if (arch_env->impl->after_ra != NULL)
			arch_env->impl->after_ra(irg);
725
		be_timer_pop(T_FINISH);
Sebastian Hack's avatar
Sebastian Hack committed
726

Christian Würdig's avatar
Christian Würdig committed
727
		/* fix stack offsets */
728
		be_timer_push(T_ABI);
729
		be_abi_fix_stack_nodes(irg);
730
		be_remove_dead_nodes_from_schedule(irg);
731
		be_abi_fix_stack_bias(irg);
732
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
733

734
		dump(DUMP_SCHED, irg, "fix_stack_after_ra");
Christian Würdig's avatar
Christian Würdig committed
735

736
		be_timer_push(T_FINISH);
737
738
		if (arch_env->impl->finish != NULL)
			arch_env->impl->finish(irg);
739
		be_timer_pop(T_FINISH);
740

741
		dump(DUMP_FINAL, irg, "finish");
742

743
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
744
745
746
747
			be_stat_ev("bemain_insns_finish", be_count_insns(irg));
			be_stat_ev("bemain_blocks_finish", be_count_blocks(irg));
		}

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

762
		}
763
		be_timer_pop(T_VERIFY);
764

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

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

773
774
775
776
777
		if (!arch_env->custom_abi) {
			be_timer_push(T_ABI);
			be_abi_free(irg);
			be_timer_pop(T_ABI);
		}
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
797
798
					double val = ir_timer_elapsed_usec(be_timers[t]) / 1000.0;
					printf("%-20s: %8.3lf msec\n", get_timer_name(t), val);
				}
799
			}
800
			for (t = T_FIRST; t < T_LAST+1; ++t) {
801
802
803
804
				ir_timer_stop(be_timers[t]);
				ir_timer_reset(be_timers[t]);
			}
		}
Michael Beck's avatar
BugFix:    
Michael Beck committed
805

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

810
811
	arch_env_done(arch_env);

812
	be_dbg_unit_end();
813
	be_dbg_close();
814

815
	ir_profile_free();
Sebastian Hack's avatar
Sebastian Hack committed
816
	be_done_env(&env);
817
818

	be_info_free();
819
820
}

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

826
	if (be_options.timing == BE_TIME_ON) {
827
		t = ir_timer_new();
828

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

Matthias Braun's avatar
Matthias Braun committed
833
		ir_timer_reset_and_start(t);
834
	}
835

Sebastian Hack's avatar
Sebastian Hack committed
836
	if (be_options.statev) {