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_t.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 */
92
	1,                                 /* verbose assembler output */
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
	LC_OPT_ENT_BOOL     ("verboseasm", "enable verbose assembler output",                     &be_options.verbose_asm),
139

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

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

148
asm_constraint_flags_t asm_constraint_flags[256];
149

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

static void finish_isa(void)
{
	if (isa_initialized) {
		isa_if->finish();
		isa_initialized = false;
	}
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
226
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;
}

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

233
234
	initialize_isa();

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

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

	return flags;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Manuel Mohr's avatar
Manuel Mohr committed
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
int be_is_big_endian(void)
{
	return be_get_backend_param()->byte_order_big_endian;
}

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

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

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

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

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

395
396
397
398
399
400
/**
 * 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
 */
401
402
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
403
{
Sebastian Hack's avatar
Sebastian Hack committed
404
	memset(env, 0, sizeof(*env));
405
	env->file_handle          = file_handle;
406
407
408
409
	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"));
410
	env->cup_name             = compilation_unit_name;
411
412

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

414
	memset(asm_constraint_flags, 0, sizeof(asm_constraint_flags));
415
	env->arch_env = arch_env_begin_codegeneration(isa_if, env);
Sebastian Hack's avatar
Sebastian Hack committed
416
417

	return env;
418
419
}

420
421
422
/**
 * Called when the be_main_env_t can be destroyed.
 */
Sebastian Hack's avatar
Sebastian Hack committed
423
static void be_done_env(be_main_env_t *env)
424
{
425
426
	pmap_destroy(env->ent_trampoline_map);
	pmap_destroy(env->ent_pic_symbol_map);
427
428
	free_type(env->pic_trampolines_type);
	free_type(env->pic_symbols_type);
Sebastian Hack's avatar
Sebastian Hack committed
429
}
Sebastian Hack's avatar
Sebastian Hack committed
430

431
432
433
434
435
436
437
438
439
/**
 * 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
 */
440
static void dump(int mask, ir_graph *irg, const char *suffix)
Sebastian Hack's avatar
Sebastian Hack committed
441
{
442
	if (be_options.dump_flags & mask)
443
		dump_ir_graph(irg, suffix);
Sebastian Hack's avatar
Sebastian Hack committed
444
}
445

Michael Beck's avatar
Michael Beck committed
446
/**
447
 * Prepare a backend graph for code generation and initialize its irg
Michael Beck's avatar
Michael Beck committed
448
 */
449
static void initialize_birg(be_irg_t *birg, ir_graph *irg, be_main_env_t *env)
Sebastian Hack's avatar
Sebastian Hack committed
450
{
451
452
453
	/* don't duplicate locals in backend when dumping... */
	ir_remove_dump_flags(ir_dump_flag_consts_local);

454
455
	dump(DUMP_INITIAL, irg, "begin");

yb9976's avatar
yb9976 committed
456
457
	irg->be_data = birg;

458
459
	memset(birg, 0, sizeof(*birg));
	birg->main_env = env;
460
	obstack_init(&birg->obst);
461
	birg->lv = be_liveness_new(irg);
462

463
464
	edges_deactivate(irg);
	edges_activate(irg);
465
466
467
468

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

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

Sebastian Hack's avatar
Sebastian Hack committed
473
	/* Remove critical edges */
474
	remove_critical_cf_edges_ex(irg, /*ignore_exception_edges=*/0);
Sebastian Hack's avatar
Sebastian Hack committed
475

476
477
478
479
	/* 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
480
	/* Ensure, that the ir_edges are computed. */
481
	assure_edges(irg);
Sebastian Hack's avatar
Sebastian Hack committed
482

483
	add_irg_constraints(irg, IR_GRAPH_CONSTRAINT_BACKEND);
484
	be_info_init_irg(irg);
485

486
	dump(DUMP_INITIAL, irg, "prepared");
Sebastian Hack's avatar
Sebastian Hack committed
487
488
}

Matthias Braun's avatar
Matthias Braun committed
489
int be_timing;
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519

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

521
522
void be_lower_for_target(void)
{
Michael Beck's avatar
Michael Beck committed
523
	size_t i;
524

525
526
	initialize_isa();

527
528
	isa_if->lower_for_target();
	/* set the phase to low */
Michael Beck's avatar
Michael Beck committed
529
530
	for (i = get_irp_n_irgs(); i > 0;) {
		ir_graph *irg = get_irp_irg(--i);
531
532
		assert(!irg_is_constrained(irg, IR_GRAPH_CONSTRAINT_TARGET_LOWERED));
		add_irg_constraints(irg, IR_GRAPH_CONSTRAINT_TARGET_LOWERED);
533
534
535
	}
}

Michael Beck's avatar
Michael Beck committed
536
537
538
539
/**
 * The Firm backend main loop.
 * Do architecture specific lowering for all graphs
 * and call the architecture specific code generator.
540
541
 *
 * @param file_handle   the file handle the output will be written to
542
 * @param cup_name      name of the compilation unit
Michael Beck's avatar
Michael Beck committed
543
 */
544
static void be_main_loop(FILE *file_handle, const char *cup_name)
545
{
Adam Szalkowski's avatar
Adam Szalkowski committed
546
	static const char suffix[] = ".prof";
547

548
549
550
	size_t        i;
	size_t        num_irgs;
	size_t        num_birgs;
551
552
553
554
	be_main_env_t env;
	char          prof_filename[256];
	be_irg_t      *birgs;
	arch_env_t    *arch_env;
555

Matthias Braun's avatar
Matthias Braun committed
556
557
	be_timing = (be_options.timing == BE_TIME_ON);

558
	/* perform target lowering if it didn't happen yet */
559
	if (get_irp_n_irgs() > 0 && !irg_is_constrained(get_irp_irg(0), IR_GRAPH_CONSTRAINT_TARGET_LOWERED))
560
561
		be_lower_for_target();

Matthias Braun's avatar
Matthias Braun committed
562
	if (be_timing) {
563
564
565
		for (i = 0; i < T_LAST+1; ++i) {
			be_timers[i] = ir_timer_new();
		}
566
	}
567

568
	be_init_env(&env, file_handle, cup_name);
569

570
571
	arch_env = env.arch_env;

Christian Würdig's avatar
Christian Würdig committed
572
	/* we might need 1 birg more for instrumentation constructor */
573
574
	num_irgs = get_irp_n_irgs();
	birgs    = ALLOCAN(be_irg_t, num_irgs + 1);
575

576
577
	be_info_init();

Christian Würdig's avatar
Christian Würdig committed
578
	/* First: initialize all birgs */
579
580
581
582
583
584
585
	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);
586
	}
587
	arch_env_handle_intrinsics(arch_env);
Michael Beck's avatar
Michael Beck committed
588

Christian Würdig's avatar
Christian Würdig committed
589
590
591
592
	/*
		Get the filename for the profiling data.
		Beware: '\0' is already included in sizeof(suffix)
	*/
593
594
595
	sprintf(prof_filename, "%.*s%s",
	        (int)(sizeof(prof_filename) - sizeof(suffix)), cup_name, suffix);

596
	bool have_profile = false;
597
598
599
600
601
	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);
602
603
604
605
		} else {
			ir_create_execfreqs_from_profile();
			ir_profile_free();
			have_profile = true;
606
607
		}
	}
608

609
	if (num_birgs > 0 && be_options.opt_profile_generate) {
610
		ir_graph *const prof_init_irg = ir_profile_instrument(prof_filename);
611
		assert(prof_init_irg->be_data == NULL);
612
613
		initialize_birg(&birgs[num_birgs], prof_init_irg, &env);
		num_birgs++;
614
615
616
617
		num_irgs++;
		assert(num_irgs == get_irp_n_irgs());
	}

Matthias Braun's avatar
Matthias Braun committed
618
619
620
	for (be_timer_id_t t = T_FIRST; t < T_LAST+1; ++t) {
		ir_timer_init_parent(be_timers[t]);
	}
621
622
623
624
625
626
627
	if (!have_profile) {
		be_timer_push(T_EXECFREQ);
		for (i = 0; i < num_irgs; ++i) {
			ir_graph *irg = get_irp_irg(i);
			ir_estimate_execfreq(irg);
		}
		be_timer_pop(T_EXECFREQ);
628
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
629

630
	/* For all graphs */
631
632
633
634
635
	for (i = 0; i < num_irgs; ++i) {
		ir_graph  *const irg    = get_irp_irg(i);
		ir_entity *const entity = get_irg_entity(irg);
		if (get_entity_linkage(entity) & IR_LINKAGE_NO_CODEGEN)
			continue;
Sebastian Hack's avatar
Sebastian Hack committed
636

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

640
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
641
642
643
			stat_ev_ctx_push_fmt("bemain_irg", "%+F", irg);
			stat_ev_ull("bemain_insns_start", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_start", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
644
		}
645

646
		/* stop and reset timers */
647
		be_timer_push(T_OTHER);
648

649
		/* Verify the initial graph */
650
		be_timer_push(T_VERIFY);
651
652
653
654
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
655
		}
656
		be_timer_pop(T_VERIFY);
657

658
		/* get a code generator for this graph. */
659
660
		if (arch_env->impl->init_graph)
			arch_env->impl->init_graph(irg);
661
662

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

Sebastian Hack's avatar
Sebastian Hack committed
666
		/* implement the ABI conventions. */
667
		if (!arch_env->custom_abi) {
668
669
670
			be_timer_push(T_ABI);
			be_abi_introduce(irg);
			be_timer_pop(T_ABI);
671
672
			dump(DUMP_ABI, irg, "abi");
		}
673

Andreas Zwinkau's avatar
Andreas Zwinkau committed
674
675
676
		/* We can't have Bad-blocks or critical edges in the backend.
		 * Before removing Bads, we remove unreachable code. */
		optimize_graph_df(irg);
677
		remove_critical_cf_edges(irg);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
678
		remove_bads(irg);
679

680
681
682
		/* 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) */
683
684
685
		edges_deactivate(irg);
		edges_activate(irg);

686
		dump(DUMP_PREPARED, irg, "before-code-selection");
687

688
		/* perform codeselection */
689
		be_timer_push(T_CODEGEN);
690
691
		if (arch_env->impl->prepare_graph != NULL)
			arch_env->impl->prepare_graph(irg);
692
		be_timer_pop(T_CODEGEN);
Sebastian Hack's avatar
Sebastian Hack committed
693

694
695
		dump(DUMP_PREPARED, irg, "code-selection");

696
		/* disabled for now, fails for EmptyFor.c and XXEndless.c */
697
		/* be_live_chk_compare(irg); */
698

Christian Würdig's avatar
Christian Würdig committed
699
		/* schedule the irg */
700
		be_timer_push(T_SCHED);
701
		be_schedule_graph(irg);
702
		be_timer_pop(T_SCHED);
Sebastian Hack's avatar
Sebastian Hack committed
703

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

Christian Würdig's avatar
Christian Würdig committed
706
		/* check schedule */
707
		be_timer_push(T_VERIFY);
708
		be_sched_verify(irg, be_options.verify_option);
709
		be_timer_pop(T_VERIFY);
710

Christian Würdig's avatar
Christian Würdig committed
711
		/* introduce patterns to assure constraints */
712
		be_timer_push(T_CONSTR);
713
		/* we switch off optimizations here, because they might cause trouble */
714
		optimization_state_t state;
715
		save_optimization_state(&state);
716
		set_optimize(0);
717
718
		set_opt_cse(0);

719
720
		/* add Keeps for should_be_different constrained nodes  */
		/* beware: needs schedule due to usage of be_ssa_constr */
721
		assure_constraints(irg);
722
		be_timer_pop(T_CONSTR);
723

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

726
		/* stuff needs to be done after scheduling but before register allocation */
727
		be_timer_push(T_RA_PREPARATION);
728
729
		if (arch_env->impl->before_ra != NULL)
			arch_env->impl->before_ra(irg);
730
		be_timer_pop(T_RA_PREPARATION);
731

Sebastian Hack's avatar
Sebastian Hack committed
732
		/* connect all stack modifying nodes together (see beabi.c) */
733
		be_timer_push(T_ABI);
734
		be_abi_fix_stack_nodes(irg);
735
		be_timer_pop(T_ABI);
Christian Würdig's avatar
Christian Würdig committed
736

737
		dump(DUMP_SCHED, irg, "fix_stack");
Sebastian Hack's avatar
Sebastian Hack committed
738

Christian Würdig's avatar
Christian Würdig committed
739
		/* check schedule */
740
		be_timer_push(T_VERIFY);
741
		be_sched_verify(irg, be_options.verify_option);
742
		be_timer_pop(T_VERIFY);
Sebastian Hack's avatar
Sebastian Hack committed
743

744
		if (stat_ev_enabled) {
745
			stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
Matthias Braun's avatar
Matthias Braun committed
746
747
			stat_ev_ull("bemain_insns_before_ra", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_before_ra", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
748
		}
749

750
		/* Do register allocation */
751
		be_allocate_registers(irg);
752

753
		stat_ev_dbl("bemain_costs_before_ra", be_estimate_irg_costs(irg));
754

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

757
		be_timer_push(T_FINISH);
Matthias Braun's avatar
Matthias Braun committed
758
759
		if (arch_env->impl->finish_graph != NULL)
			arch_env->impl->finish_graph(irg);
760
		be_timer_pop(T_FINISH);
761

762
		dump(DUMP_FINAL, irg, "finish");
763

764
		if (stat_ev_enabled) {
Matthias Braun's avatar
Matthias Braun committed
765
766
			stat_ev_ull("bemain_insns_finish", be_count_insns(irg));
			stat_ev_ull("bemain_blocks_finish", be_count_blocks(irg));
Matthias Braun's avatar
Matthias Braun committed
767
768
		}

769
		/* check schedule and register allocation */
770
		be_timer_push(T_VERIFY);
771
772
		if (be_options.verify_option == BE_VERIFY_WARN) {
			irg_verify(irg, VERIFY_ENFORCE_SSA);
773
774
			be_verify_schedule(irg);
			be_verify_register_allocation(irg);
775
776
		} else if (be_options.verify_option == BE_VERIFY_ASSERT) {
			assert(irg_verify(irg, VERIFY_ENFORCE_SSA) && "irg verification failed");
777
778
			assert(be_verify_schedule(irg) && "Schedule verification failed");
			assert(be_verify_register_allocation(irg)
779
			       && "register allocation verification failed");
780

781
		}
782
		be_timer_pop(T_VERIFY);
783

Christian Würdig's avatar
Christian Würdig committed
784
		/* emit assembler code */
785
		be_timer_push(T_EMIT);
786
787
		if (arch_env->impl->emit != NULL)
			arch_env->impl->emit(irg);
788
		be_timer_pop(T_EMIT);
Christian Würdig's avatar
Christian Würdig committed
789

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

792
		restore_optimization_state(&state);
793

794
795
796
		be_timer_pop(T_OTHER);

		if (be_timing) {
797
			be_timer_id_t t;
798
			if (stat_ev_enabled) {
799
				for (t = T_FIRST; t < T_LAST+1; ++t) {
800
801
802
803
804
					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
805
			} else {
806
807
				printf("==>> IRG %s <<==\n",
				       get_entity_name(get_irg_entity(irg)));
808
				for (t = T_FIRST; t < T_LAST+1; ++t) {
809
					double val = ir_timer_elapsed_usec(be_timers[t]) / 1000.0;
810
					printf("%-20s: %10.3f msec\n", get_timer_name(t), val);
811
				}
812
			}
813
			for (t = T_FIRST; t < T_LAST+1; ++t) {
814
815
816
				ir_timer_reset(be_timers[t]);
			}
		}
Michael Beck's avatar
BugFix:    
Michael Beck committed
817

818
		be_free_birg(irg);
Sebastian Hack's avatar
Sebastian Hack committed
819
		stat_ev_ctx_pop("bemain_irg");
820
	}
821

822
	arch_env_end_codegeneration(arch_env);
823

Sebastian Hack's avatar
Sebastian Hack committed
824
	be_done_env(&env);
825
826

	be_info_free();
827
828
}

Michael Beck's avatar
Michael Beck committed
829
/* Main interface to the frontend. */
830
void be_main(FILE *file_handle, const char *cup_name)
831
{
Matthias Braun's avatar
Matthias Braun committed
832
	ir_timer_t *t = NULL;
833

834
	if (be_options.timing == BE_TIME_ON) {
835
		t = ir_timer_new();
836

Matthias Braun's avatar
Matthias Braun committed
837
		if (ir_timer_enter_high_priority()) {
838
839
840
			fprintf(stderr, "Warning: Could not enter high priority mode.\n");
		}

Matthias Braun's avatar
Matthias Braun committed
841
		ir_timer_reset_and_start(t);
842
	}
843

Sebastian Hack's avatar
Sebastian Hack committed
844
	if (be_options.statev) {
845
		const char *dot = strrchr(cup_name, '.');
Sebastian Hack's avatar
Sebastian Hack committed
846
		const char *pos = dot ? dot : cup_name + strlen(cup_name);
847
		char       *buf = ALLOCAN(char, pos - cup_name + 1);
Sebastian Hack's avatar
Sebastian Hack committed
848
		strncpy(buf, cup_name, pos - cup_name);
Sebastian Hack's avatar
Sebastian Hack committed
849
		buf[pos - cup_name] = '\0';
Sebastian Hack's avatar
Sebastian Hack committed
850

Sebastian Hack's avatar
Sebastian Hack committed
851
		be_options.statev = 1;
852
		stat_ev_begin(buf, be_options.filtev);
853
		stat_ev_ctx_push_str("bemain_compilation_unit", cup_name);