bemain.c 25.6 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 "beirg.h"
74
#include "bestack.h"
75
#include "beemitter.h"
Sebastian Hack's avatar
Sebastian Hack committed
76

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

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

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

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

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

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

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

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

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

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

146
asm_constraint_flags_t asm_constraint_flags[256];
147

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

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

164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
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;
}

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

231
232
	initialize_isa();

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

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

	return flags;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

363
364
365
366
367
368
/**
 * 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
 */
369
370
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
371
{
Sebastian Hack's avatar
Sebastian Hack committed
372
	memset(env, 0, sizeof(*env));
373
	env->file_handle          = file_handle;
374
375
376
377
	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"));
378
	env->cup_name             = compilation_unit_name;
379
380

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

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

	return env;
386
387
}

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

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

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

422
423
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
424
425
	irg->be_data = birg;

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

	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;

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

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

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

452
	set_irg_phase_state(irg, phase_backend);
453
	be_info_init_irg(irg);
454

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

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

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

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

496
497
498
499
500
	initialize_isa();

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

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

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

522
523
524
	size_t        i;
	size_t        num_irgs;
	size_t        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
548
	num_irgs = get_irp_n_irgs();
	birgs    = ALLOCAN(be_irg_t, num_irgs + 1);
549

550
551
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
552
	/* First: initialize all birgs */
553
554
555
556
557
558
559
	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);
560
	}
561
	arch_env_handle_intrinsics(arch_env);
Michael Beck's avatar
Michael Beck committed
562

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

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

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

593
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
594
595
596
597
			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));
		}
598

599
		/* stop and reset timers */
600
		be_timer_push(T_OTHER);
601

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

613
		/* get a code generator for this graph. */
614
		arch_env->impl->init_graph(irg);
615
616

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

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

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

634
635
636
		/* 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) */
637
638
639
		edges_deactivate(irg);
		edges_activate(irg);

640
		dump(DUMP_PREPARED, irg, "before-code-selection");
641

642
		if (be_options.verify_option == BE_VERIFY_WARN) {
643
			be_check_dominance(irg);
644
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
645
646
647
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}

648
		/* perform codeselection */
649
		be_timer_push(T_CODEGEN);
650
651
		if (arch_env->impl->prepare_graph != NULL)
			arch_env->impl->prepare_graph(irg);
652
		be_timer_pop(T_CODEGEN);
Sebastian Hack's avatar
Sebastian Hack committed
653

654
		if (be_options.verify_option == BE_VERIFY_WARN) {
655
			be_check_dominance(irg);
656
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
657
658
659
			assert(be_check_dominance(irg) && "Dominance verification failed");
		}

660
661
		dump(DUMP_PREPARED, irg, "code-selection");

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

676
677

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

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

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

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

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

699
700
		/* add Keeps for should_be_different constrained nodes  */
		/* beware: needs schedule due to usage of be_ssa_constr */
701
		assure_constraints(irg);
702
		be_timer_pop(T_CONSTR);
703

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

706
		/* stuff needs to be done after scheduling but before register allocation */
707
		be_timer_push(T_RA_PREPARATION);
708
709
		if (arch_env->impl->before_ra != NULL)
			arch_env->impl->before_ra(irg);
710
		be_timer_pop(T_RA_PREPARATION);
711

Sebastian Hack's avatar
Sebastian Hack committed
712
		/* connect all stack modifying nodes together (see beabi.c) */
713
		be_timer_push(T_ABI);
714
		be_abi_fix_stack_nodes(irg);
715
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
716

717
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
718

Christian Würdig's avatar
Christian Würdig committed
719
		/* check schedule */
720
		be_timer_push(T_VERIFY);
721
		be_sched_verify(irg, be_options.verify_option);
722
		be_timer_pop(T_VERIFY);
Sebastian Hack's avatar
Sebastian Hack committed
723

724
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
725
			stat_ev_dbl("bemain_costs_before_ra",
726
					be_estimate_irg_costs(irg, birg->exec_freq));
Matthias Braun's avatar
Matthias Braun committed
727
728
729
			be_stat_ev("bemain_insns_before_ra", be_count_insns(irg));
			be_stat_ev("bemain_blocks_before_ra", be_count_blocks(irg));
		}
730

731
		/* Do register allocation */
732
		be_allocate_registers(irg);
733

734
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg, birg->exec_freq));
735

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

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

743
		dump(DUMP_FINAL, irg, "finish");
744

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

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

764
		}
765
		be_timer_pop(T_VERIFY);
766

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

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

775
776
777
778
779
		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
780

781
		restore_optimization_state(&state);
782

783
784
785
		be_timer_pop(T_OTHER);

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

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

812
	arch_env_end_codegeneration(arch_env);
813

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

	be_info_free();
818
819
}

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

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

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

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

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