bemain.c 25.5 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
 * @file
 * @brief       Main Backend driver.
 * @author      Sebastian Hack
 * @date        25.11.2004
25
 */
Michael Beck's avatar
Michael Beck committed
26
#include "config.h"
27

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

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

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

#include "irprog.h"
Sebastian Hack's avatar
Sebastian Hack committed
38
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
39
#include "irgraph.h"
Daniel Grund's avatar
Daniel Grund committed
40
#include "irdump.h"
Sebastian Hack's avatar
Sebastian Hack committed
41
42
#include "irdom_t.h"
#include "iredges_t.h"
43
#include "irloop_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
44
#include "irtools.h"
45
#include "irverify.h"
46
#include "irprintf.h"
Matthias Braun's avatar
Matthias Braun committed
47
#include "iroptimize.h"
Christian Würdig's avatar
Christian Würdig committed
48
#include "firmstat.h"
49
#include "execfreq.h"
50
#include "irprofile.h"
51
#include "irpass_t.h"
52
#include "ircons.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 */
90
	"",                                /* 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),
138

139
140
	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),
141
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
142
143
};

144
145
static be_module_list_entry_t *isa_ifs         = NULL;
static bool                    isa_initialized = false;
146

147
asm_constraint_flags_t asm_constraint_flags[256];
148

149
150
151
152
153
static void initialize_isa(void)
{
	if (isa_initialized)
		return;
	isa_if->init();
Matthias Braun's avatar
Matthias Braun committed
154
155
156
157
158
159
160
161
162
	isa_initialized = true;
}

static void finish_isa(void)
{
	if (isa_initialized) {
		isa_if->finish();
		isa_initialized = false;
	}
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
214
215
216
217
218
219
220
221
222
223
224
225
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;
}

226
asm_constraint_flags_t be_parse_asm_constraints(const char *constraint)
227
{
228
	asm_constraint_flags_t  flags = ASM_CONSTRAINT_FLAG_NONE;
229
230
231
	const char             *c;
	asm_constraint_flags_t  tflags;

232
233
	initialize_isa();

234
235
236
237
	for (c = constraint; *c != '\0'; ++c) {
		switch (*c) {
		case '#':
			/* 'comment' stuff */
238
			while (*c != 0 && *c != ',')
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
				++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 {
255
				flags |= isa_if->parse_asm_constraint(&c);
256
257
258
259
260
			}
			break;
		}
	}

261
	if ((
262
263
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_WRITE &&
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_NO_WRITE
264
	    ) || (
265
266
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_READ &&
	        flags & ASM_CONSTRAINT_FLAG_MODIFIER_NO_READ
267
	    )) {
268
269
		flags |= ASM_CONSTRAINT_FLAG_INVALID;
	}
270
271
272
273
274
	if (!(flags & (ASM_CONSTRAINT_FLAG_MODIFIER_READ     |
	               ASM_CONSTRAINT_FLAG_MODIFIER_WRITE    |
	               ASM_CONSTRAINT_FLAG_MODIFIER_NO_WRITE |
	               ASM_CONSTRAINT_FLAG_MODIFIER_NO_READ)
	    )) {
275
276
		flags |= ASM_CONSTRAINT_FLAG_MODIFIER_READ;
	}
277
278
279
280

	return flags;
}

281
int be_is_valid_clobber(const char *clobber)
282
{
283
284
	initialize_isa();

285
286
287
	/* 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)
288
		return 1;
289
290
	/* cc (condition code) is always valid */
	if (strcmp(clobber, "cc") == 0)
291
		return 1;
292

293
	return isa_if->is_valid_clobber(clobber);
294
295
}

296
297
void be_register_isa_if(const char *name, const arch_isa_if_t *isa)
{
298
	if (isa_if == NULL)
299
300
301
302
303
		isa_if = isa;

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

304
static void be_opt_register(void)
Sebastian Hack's avatar
Sebastian Hack committed
305
{
306
	lc_opt_entry_t *be_grp;
307
308
	static int run_once = 0;

309
	if (run_once)
310
		return;
311
	run_once = 1;
312

313
314
	be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_add_table(be_grp, be_main_options);
315
316
317

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

	be_init_modules();
320
}
Sebastian Hack's avatar
Sebastian Hack committed
321

322
/* Parse one argument. */
323
324
int be_parse_arg(const char *arg)
{
325
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
Michael Beck's avatar
Michael Beck committed
326
	if (strcmp(arg, "help") == 0 || (arg[0] == '?' && arg[1] == '\0')) {
327
		lc_opt_print_help_for_entry(be_grp, '-', stdout);
Michael Beck's avatar
Michael Beck committed
328
329
		return -1;
	}
330
	return lc_opt_from_single_arg(be_grp, NULL, arg, NULL);
331
332
}

Christian Würdig's avatar
Christian Würdig committed
333
/* Perform schedule verification if requested. */
334
static void be_sched_verify(ir_graph *irg, int verify_opt)
335
{
336
	if (verify_opt == BE_VERIFY_WARN) {
337
		be_verify_schedule(irg);
338
	} else if (verify_opt == BE_VERIFY_ASSERT) {
339
		assert(be_verify_schedule(irg) && "Schedule verification failed.");
Christian Würdig's avatar
Christian Würdig committed
340
341
342
	}
}

343
344
/* Initialize the Firm backend. Must be run first in init_firm()! */
void firm_be_init(void)
345
{
Sebastian Hack's avatar
Sebastian Hack committed
346
	be_opt_register();
347
	be_init_modules();
348
}
349

yb9976's avatar
yb9976 committed
350
351
352
/* Finalize the Firm backend. */
void firm_be_finish(void)
{
Matthias Braun's avatar
Matthias Braun committed
353
	finish_isa();
yb9976's avatar
yb9976 committed
354
355
356
	be_quit_modules();
}

357
358
359
/* Returns the backend parameter */
const backend_params *be_get_backend_param(void)
{
360
	initialize_isa();
361
	return isa_if->get_params();
362
363
}

364
365
366
367
368
369
/**
 * 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
 */
370
371
static be_main_env_t *be_init_env(be_main_env_t *env, FILE *file_handle,
                                  const char *compilation_unit_name)
Sebastian Hack's avatar
Sebastian Hack committed
372
{
Sebastian Hack's avatar
Sebastian Hack committed
373
	memset(env, 0, sizeof(*env));
374
	env->options              = &be_options;
375
	env->file_handle          = file_handle;
376
377
378
379
	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"));
380
	env->cup_name             = compilation_unit_name;
381
382

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

384
	memset(asm_constraint_flags, 0, sizeof(asm_constraint_flags));
385
	env->arch_env = arch_env_begin_codegeneration(isa_if, env);
Sebastian Hack's avatar
Sebastian Hack committed
386
387

	return env;
388
389
}

390
391
392
/**
 * Called when the be_main_env_t can be destroyed.
 */
Sebastian Hack's avatar
Sebastian Hack committed
393
static void be_done_env(be_main_env_t *env)
394
{
395
396
	pmap_destroy(env->ent_trampoline_map);
	pmap_destroy(env->ent_pic_symbol_map);
397
398
	free_type(env->pic_trampolines_type);
	free_type(env->pic_symbols_type);
Sebastian Hack's avatar
Sebastian Hack committed
399
}
Sebastian Hack's avatar
Sebastian Hack committed
400

401
402
403
404
405
406
407
408
409
/**
 * 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
 */
410
static void dump(int mask, ir_graph *irg, const char *suffix)
Sebastian Hack's avatar
Sebastian Hack committed
411
{
412
	if (be_options.dump_flags & mask)
413
		dump_ir_graph(irg, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
414
}
415

Michael Beck's avatar
Michael Beck committed
416
/**
417
 * Prepare a backend graph for code generation and initialize its irg
Michael Beck's avatar
Michael Beck committed
418
 */
419
static void initialize_birg(be_irg_t *birg, ir_graph *irg, be_main_env_t *env)
Sebastian Hack's avatar
Sebastian Hack committed
420
{
421
422
423
	/* don't duplicate locals in backend when dumping... */
	ir_remove_dump_flags(ir_dump_flag_consts_local);

424
425
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
426
427
	irg->be_data = birg;

428
429
430
	memset(birg, 0, sizeof(*birg));
	birg->irg = irg;
	birg->main_env = env;
431
	obstack_init(&birg->obst);
432
	birg->lv = be_liveness_new(irg);
433
434
435
436
437
438
439

	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;

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

Sebastian Hack's avatar
Sebastian Hack committed
444
	/* Remove critical edges */
445
	remove_critical_cf_edges_ex(irg, /*ignore_exception_edges=*/0);
Sebastian Hack's avatar
Sebastian Hack committed
446

447
448
449
450
	/* 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
451
	/* Ensure, that the ir_edges are computed. */
Sebastian Hack's avatar
Sebastian Hack committed
452
	edges_assure(irg);
Sebastian Hack's avatar
Sebastian Hack committed
453

454
	set_irg_phase_state(irg, phase_backend);
455
	be_info_init_irg(irg);
456

457
	dump(DUMP_INITIAL, irg, "prepared");
Sebastian Hack's avatar
Sebastian Hack committed
458
459
}

Matthias Braun's avatar
Matthias Braun committed
460
int be_timing;
461
462
463
464
465
466
467
468

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";
469
	case T_SPLIT:          return "split";
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
	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];
493

494
495
void be_lower_for_target(void)
{
Michael Beck's avatar
Michael Beck committed
496
	size_t i;
497

498
499
500
501
502
	initialize_isa();

	/* shouldn't lower program twice */
	assert(get_irp_phase_state() != phase_low);

503
504
	isa_if->lower_for_target();
	/* set the phase to low */
Michael Beck's avatar
Michael Beck committed
505
506
	for (i = get_irp_n_irgs(); i > 0;) {
		ir_graph *irg = get_irp_irg(--i);
507
508
509
510
511
		set_irg_phase_state(irg, phase_low);
	}
	set_irp_phase_state(phase_low);
}

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

Michael Beck's avatar
Michael Beck committed
524
	size_t        i, num_birgs;
525
526
527
528
	be_main_env_t env;
	char          prof_filename[256];
	be_irg_t      *birgs;
	arch_env_t    *arch_env;
529

Matthias Braun's avatar
Matthias Braun committed
530
531
	be_timing = (be_options.timing == BE_TIME_ON);

532
533
534
535
	/* perform target lowering if it didn't happen yet */
	if (get_irp_phase_state() != phase_low)
		be_lower_for_target();

Matthias Braun's avatar
Matthias Braun committed
536
	if (be_timing) {
537
538
539
		for (i = 0; i < T_LAST+1; ++i) {
			be_timers[i] = ir_timer_new();
		}
540
	}
541

542
	be_init_env(&env, file_handle, cup_name);
543

544
545
	arch_env = env.arch_env;

Christian Würdig's avatar
Christian Würdig committed
546
	/* we might need 1 birg more for instrumentation constructor */
547
	num_birgs = get_irp_n_irgs();
548
	birgs     = ALLOCAN(be_irg_t, num_birgs + 1);
549

550
551
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
552
	/* First: initialize all birgs */
553
	for (i = 0; i < num_birgs; ++i) {
554
		ir_graph *irg = get_irp_irg(i);
555
556
		initialize_birg(&birgs[i], irg, &env);
	}
557
	arch_env_handle_intrinsics(arch_env);
Michael Beck's avatar
Michael Beck committed
558

Christian Würdig's avatar
Christian Würdig committed
559
560
561
562
	/*
		Get the filename for the profiling data.
		Beware: '\0' is already included in sizeof(suffix)
	*/
563
564
565
566
567
568
569
570
571
572
	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);
		}
	}
573
	if (num_birgs > 0 && be_options.opt_profile_generate) {
574
575
		ir_graph *prof_init_irg
			= ir_profile_instrument(prof_filename);
576
577
		initialize_birg(&birgs[num_birgs], prof_init_irg, &env);
		num_birgs++;
578
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
579

580
	/* For all graphs */
581
	for (i = 0; i < num_birgs; ++i) {
582
		be_irg_t *birg = &birgs[i];
Christian Würdig's avatar
Christian Würdig committed
583
		ir_graph *irg  = birg->irg;
584
		optimization_state_t state;
Sebastian Hack's avatar
Sebastian Hack committed
585

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

589
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
590
591
592
593
			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));
		}
594

595
		/* stop and reset timers */
596
		be_timer_push(T_OTHER);
597

598
		/* Verify the initial graph */
599
		be_timer_push(T_VERIFY);
600
601
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
602
			be_check_dominance(irg);
603
604
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
605
606
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}
607
		be_timer_pop(T_VERIFY);
608

609
		/* get a code generator for this graph. */
610
		arch_env->impl->init_graph(irg);
611
612

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

Sebastian Hack's avatar
Sebastian Hack committed
616
		/* implement the ABI conventions. */
617
		if (!arch_env->custom_abi) {
618
619
620
			be_timer_push(T_ABI);
			be_abi_introduce(irg);
			be_timer_pop(T_ABI);
621
622
			dump(DUMP_ABI, irg, "abi");
		}
623

Andreas Zwinkau's avatar
Andreas Zwinkau committed
624
625
626
		/* We can't have Bad-blocks or critical edges in the backend.
		 * Before removing Bads, we remove unreachable code. */
		optimize_graph_df(irg);
627
		remove_critical_cf_edges(irg);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
628
		remove_bads(irg);
629

630
631
632
		/* 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) */
633
634
635
		edges_deactivate(irg);
		edges_activate(irg);

636
		dump(DUMP_PREPARED, irg, "before-code-selection");
637

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

644
		/* perform codeselection */
645
		be_timer_push(T_CODEGEN);
646
647
		if (arch_env->impl->prepare_graph != NULL)
			arch_env->impl->prepare_graph(irg);
648
		be_timer_pop(T_CODEGEN);
Sebastian Hack's avatar
Sebastian Hack committed
649

650
		if (be_options.verify_option == BE_VERIFY_WARN) {
651
			be_check_dominance(irg);
652
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
653
654
655
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}

656
657
		dump(DUMP_PREPARED, irg, "code-selection");

658
		be_timer_push(T_EXECFREQ);
659
660
661
		/**
		 * Create execution frequencies from profile data or estimate some
		 */
662
663
		if (ir_profile_has_data())
			birg->exec_freq = ir_create_execfreqs_from_profile(irg);
664
665
666
667
		else {
			/* TODO: edges are corrupt for EDGE_KIND_BLOCK after the local
			 * optimize graph phase merges blocks in the x86 backend */
			edges_deactivate(irg);
668
			birg->exec_freq = compute_execfreq(irg, 10);
669
		}
670
		be_timer_pop(T_EXECFREQ);
671

672
673

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

Christian Würdig's avatar
Christian Würdig committed
676
		/* schedule the irg */
677
		be_timer_push(T_SCHED);
678
		be_schedule_graph(irg);
679
		be_timer_pop(T_SCHED);
Sebastian Hack's avatar
Sebastian Hack committed
680

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

Christian Würdig's avatar
Christian Würdig committed
683
		/* check schedule */
684
		be_timer_push(T_VERIFY);
685
		be_sched_verify(irg, be_options.verify_option);
686
		be_timer_pop(T_VERIFY);
687

Christian Würdig's avatar
Christian Würdig committed
688
		/* introduce patterns to assure constraints */
689
		be_timer_push(T_CONSTR);
690
		/* we switch off optimizations here, because they might cause trouble */
691
		save_optimization_state(&state);
692
		set_optimize(0);
693
694
		set_opt_cse(0);

695
696
		/* add Keeps for should_be_different constrained nodes  */
		/* beware: needs schedule due to usage of be_ssa_constr */
697
		assure_constraints(irg);
698
		be_timer_pop(T_CONSTR);
699

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

702
		/* stuff needs to be done after scheduling but before register allocation */
703
		be_timer_push(T_RA_PREPARATION);
704
705
		if (arch_env->impl->before_ra != NULL)
			arch_env->impl->before_ra(irg);
706
		be_timer_pop(T_RA_PREPARATION);
707

Sebastian Hack's avatar
Sebastian Hack committed
708
		/* connect all stack modifying nodes together (see beabi.c) */
709
		be_timer_push(T_ABI);
710
		be_abi_fix_stack_nodes(irg);
711
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
712

713
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
714

Christian Würdig's avatar
Christian Würdig committed
715
		/* check schedule */
716
		be_timer_push(T_VERIFY);
717
		be_sched_verify(irg, be_options.verify_option);
718
		be_timer_pop(T_VERIFY);
Sebastian Hack's avatar
Sebastian Hack committed
719

720
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
721
			stat_ev_dbl("bemain_costs_before_ra",
722
					be_estimate_irg_costs(irg, birg->exec_freq));
Matthias Braun's avatar
Matthias Braun committed
723
724
725
			be_stat_ev("bemain_insns_before_ra", be_count_insns(irg));
			be_stat_ev("bemain_blocks_before_ra", be_count_blocks(irg));
		}
726

727
		/* Do register allocation */
728
		be_allocate_registers(irg);
729

730
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg, birg->exec_freq));
731

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

734
		be_timer_push(T_FINISH);
Matthias Braun's avatar
Matthias Braun committed
735
736
		if (arch_env->impl->finish_graph != NULL)
			arch_env->impl->finish_graph(irg);
737
		be_timer_pop(T_FINISH);
738

739
		dump(DUMP_FINAL, irg, "finish");
740

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

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

760
		}
761
		be_timer_pop(T_VERIFY);
762

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

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

771
772
773
774
775
		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
776

777
		restore_optimization_state(&state);
778

779
780
781
		be_timer_pop(T_OTHER);

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

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

808
	arch_env_end_codegeneration(arch_env);
809

810
	ir_profile_free();
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);