bessaconstr.c 15.5 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
7
/**
 * @file
Christian Würdig's avatar
Christian Würdig committed
8
 * @brief       SSA construction for a set of nodes
9
10
 * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig,
 *              Sebastian Buchwald
11
12
13
14
15
16
17
 * @date        04.05.2005
 *
 * The problem: Given a value and a set of "copies" that are known to
 * represent the same abstract value, rewire all usages of the original value
 * to their closest copy while introducing phis as necessary.
 *
 * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
18
 * and its copies. Link the copies ordered by dominance to the blocks.  Then
Michael Beck's avatar
Michael Beck committed
19
 * we search for each use all definitions in the current block, if none is
20
 * found, then we search one in the immediate dominator. If we are in a block
Michael Beck's avatar
Michael Beck committed
21
22
 * of the dominance frontier, create a phi and do the same search for all
 * phi arguments.
Christian Würdig's avatar
Christian Würdig committed
23
24
25
26
27
28
29
30
31
32
33
 *
 * A copy in this context means, that you want to introduce several new
 * abstract values (in Firm: nodes) for which you know, that they
 * represent the same concrete value. This is the case if you
 * - copy
 * - spill and reload
 * - re-materialize
 * a value.
 *
 * This function reroutes all uses of the original value to the copies in the
 * corresponding dominance subtrees and creates Phi functions where necessary.
34
 */
35
36
37
/* statev in this file is extensive, so only enable if needed */
#define DISABLE_STATEV

38
39
#include "bessaconstr.h"
#include "bemodule.h"
40
#include "besched.h"
Matthias Braun's avatar
Matthias Braun committed
41
#include "belive_t.h"
42
#include "beirg.h"
Matthias Braun's avatar
Matthias Braun committed
43
#include "be_t.h"
44
#include "benode.h"
45
46

#include "debug.h"
Matthias Braun's avatar
Matthias Braun committed
47
#include "panic.h"
48
49
50
51
#include "array.h"
#include "irdom.h"
#include "ircons.h"
#include "iredges_t.h"
52
#include "statev_t.h"
53
54
55

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

56
57
58
59
static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
                                        ir_node *block);

struct constr_info {
60
61
62
	bool is_definition     : 1;
	bool is_use            : 1;
	bool already_processed : 1;
63
64
65
66
67
68
69
	union {
		/* Since we only consider scheduled nodes,
		 * this points to the real definition (e.g. a Proj). */
		ir_node *definition;

		/* Last definition of a block. */
		ir_node *last_definition;
70
	} u;
71
72
73
74
75
76
77
};

typedef struct constr_info constr_info;

/**
 * @return Whether the block contains a definition.
 */
78
static bool has_definition(const ir_node *block)
79
80
81
82
{
	return irn_visited(block);
}

83
84
85
static constr_info *get_or_set_info(be_ssa_construction_env_t *env,
                                    const ir_node *node)
{
86
	constr_info *info = ir_nodemap_get(constr_info, &env->infos, node);
87
88
89
90
91
92
93
94
95
96
	if (info == NULL) {
		info = OALLOCZ(&env->obst, constr_info);
		ir_nodemap_insert(&env->infos, node, info);
	}
	return info;
}

static constr_info *get_info(const be_ssa_construction_env_t *env,
                             const ir_node *node)
{
97
	return ir_nodemap_get(constr_info, &env->infos, node);
98
99
}

100
101
102
103
104
/**
 * @return Whether the block contains a use.
 */
static inline bool has_use(be_ssa_construction_env_t *env, ir_node *block)
{
105
	constr_info *info = get_or_set_info(env, block);
106
107
108
109
110
111
	return info->is_use;
}

/**
 * @return Whether the node is a definition.
 */
112
static bool is_definition(be_ssa_construction_env_t *env, ir_node *node)
113
{
114
115
	constr_info *info = get_info(env, node);
	return info != NULL && info->is_definition;
116
117
118
119
120
121
122
123
}

/**
 * Introduces a definition at the corresponding block.
 */
static void introduce_definition(be_ssa_construction_env_t *env, ir_node *def)
{
	ir_node     *block      = get_nodes_block(def);
124
	constr_info *def_info   = get_or_set_info(env, def);
125
	ir_node     *skip       = skip_Proj(def);
126
127
	constr_info *skip_info  = get_or_set_info(env, skip);
	constr_info *block_info = get_or_set_info(env, block);
128
129
130
131
132
133

	DBG((dbg, LEVEL_2, "\tintroducing definition %+F in %+F\n", def, block));

	def_info->is_definition = true;

	skip_info->is_definition = true;
134
	skip_info->u.definition  = def;
135
136

	// Set the last definition if we only introduce one definition for the block
137
	if (has_definition(block)) {
138
		assert(!block_info->already_processed);
139
		block_info->u.last_definition = NULL;
140
	} else {
141
		mark_irn_visited(block);
142
		block_info->u.last_definition = def;
143
144
145
146
147
148
	}
}

static void introduce_use(be_ssa_construction_env_t *env, ir_node *use)
{
	ir_node     *block      = get_nodes_block(use);
149
150
	constr_info *info       = get_or_set_info(env, use);
	constr_info *block_info = get_or_set_info(env, block);
151
152
153
154
155
156
157
158
159

	DBG((dbg, LEVEL_2, "\tintroducing use %+F in %+F\n", use, block));

	info->is_use       = true;
	block_info->is_use = true;

	waitq_put(env->worklist, use);
}

160
161
162
163
164
/**
 * Calculates the iterated dominance frontier of a set of blocks. Marks the
 * blocks as visited. Sets the link fields of the blocks in the dominance
 * frontier to the block itself.
 */
165
static void mark_iterated_dominance_frontiers(
166
                                           const be_ssa_construction_env_t *env)
167
{
168
	stat_ev_cnt_decl(blocks);
169
	DBG((dbg, LEVEL_3, "Dominance Frontier:"));
170
	stat_ev_tim_push();
Michael Beck's avatar
Michael Beck committed
171
	while (!waitq_empty(env->worklist)) {
172
		int i;
173
		ir_node  *block    = (ir_node*)waitq_get(env->worklist);
Matthias Braun's avatar
Matthias Braun committed
174
		ir_node **domfront = ir_get_dominance_frontier(block);
175
176
177
178
		int domfront_len = ARR_LEN(domfront);

		for (i = 0; i < domfront_len; ++i) {
			ir_node *y = domfront[i];
179
180
181
182
			if (Block_block_visited(y))
				continue;

			if (!irn_visited(y)) {
183
				set_irn_link(y, NULL);
184
				waitq_put(env->worklist, y);
185
			}
186

187
188
			DBG((dbg, LEVEL_3, " %+F", y));
			mark_Block_block_visited(y);
189
			stat_ev_cnt_inc(blocks);
190
191
		}
	}
192
193
	stat_ev_tim_pop("bessaconstr_idf_time");
	stat_ev_cnt_done(blocks, "bessaconstr_idf_blocks");
194
195
196
	DBG((dbg, LEVEL_3, "\n"));
}

197
198
199
200
201
202
203
204
205
/**
 * Inserts a new phi at the given block.
 *
 * The constructed phi has only Dummy operands,
 * but can be used as definition for other nodes.
 *
 * @see fix_phi_arguments
 */
static ir_node *insert_dummy_phi(be_ssa_construction_env_t *env, ir_node *block)
206
207
{
	int i, n_preds = get_Block_n_cfgpreds(block);
208
	ir_graph *irg = get_Block_irg(block);
209
	ir_node **ins = ALLOCAN(ir_node*, n_preds);
210
	ir_node  *dummy;
211
	ir_node  *phi;
212

213
214
	DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));

215
216
	assert(n_preds > 1);

217
	dummy = new_r_Dummy(irg, env->mode);
218
	for (i = 0; i < n_preds; ++i) {
219
		ins[i] = dummy;
220
	}
221
	phi = be_new_Phi(block, n_preds, ins, env->mode, env->phi_req);
Matthias Braun's avatar
Matthias Braun committed
222
	sched_add_after(block, phi);
223
	ARR_APP1(ir_node*, env->new_phis, phi);
224
225

	DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
226
	introduce_definition(env, phi);
227

228
	waitq_put(env->worklist, phi);
229
230
231
232

	return phi;
}

233
234
235
/**
 * @return Last definition of the immediate dominator.
 */
236
static ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block)
237
238
{
	ir_node *dom = get_Block_idom(block);
Matthias Braun's avatar
Matthias Braun committed
239
	assert(dom != NULL);
240
	DBG((dbg, LEVEL_3, "\t...continue at idom %+F\n", dom));
Michael Beck's avatar
Michael Beck committed
241
	return search_def_end_of_block(env, dom);
242
243
}

244
245
246
247
248
249
250
251
252
253
static ir_node *get_def_from_preds(be_ssa_construction_env_t *const env, ir_node *const block)
{
	/* Create a phi if the block is in the dominance frontier. */
	if (Block_block_visited(block)) {
		return insert_dummy_phi(env, block);
	} else {
		return get_def_at_idom(env, block);
	}
}

254
255
256
257
258
259
/**
 * Fixes all operands of a use.
 *
 * If an operand of the use is a (original) definition,
 * it will be replaced by the given definition.
 */
260
static void set_operands(be_ssa_construction_env_t *env, ir_node *use, ir_node *def, constr_info *const use_info)
261
{
262
	foreach_irn_in(use, i, op) {
263
264
265
266
		if (is_definition(env, op)) {
			DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", use, i, def));
			set_irn_n(use, i, def);
		}
267
	}
268

269
	use_info->already_processed = true;
270
271
}

272
273
274
275
/**
 * Fixes all uses of the given block.
 */
static void process_block(be_ssa_construction_env_t *env, ir_node *block)
276
{
277
	ir_node     *def        = NULL;
278
	constr_info *block_info = get_or_set_info(env, block);
279

280
	assert(has_definition(block));
281
	assert(!block_info->already_processed && "Block already processed");
282

283
	DBG((dbg, LEVEL_3, "\tprocessing block  %+F\n", block));
284

285
	sched_foreach(block, node) {
286
287
288
289
290
		constr_info *const info = get_info(env, node);
		if (!info)
			continue;

		if (info->is_use && !is_Phi(node)) {
291
			DBG((dbg, LEVEL_3, "\t...found use %+F\n", node));
292

293
294
			if (def == NULL) {
				/* Create a phi if the block is in the dominance frontier. */
295
				def = get_def_from_preds(env, block);
296
			}
297

298
			set_operands(env, node, def, info);
299
300
		}

301
		if (info->is_definition) {
302
			def = info->u.definition;
303
304
			DBG((dbg, LEVEL_3, "\t...found definition %+F\n", def));
		}
305
306
	}

307
	block_info->already_processed = true;
308
	block_info->u.last_definition = def;
309
310
311
}

/**
312
 * @return Last definition of the given block.
313
 */
314
315
static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
                                        ir_node *block)
316
{
317
	constr_info *block_info      = get_or_set_info(env, block);
318
	ir_node     *last_definition = block_info->u.last_definition;
319
320
321
322

	if (last_definition != NULL)
		return last_definition;

323
	if (has_definition(block)) {
324
325
326
		if (has_use(env, block)) {
			if (!block_info->already_processed) {
				process_block(env, block);
327
			}
328
		} else {
329
330
			/* Search the last definition of the block. */
			sched_foreach_reverse(block, def) {
331
332
				constr_info const *const info = get_info(env, def);
				if (info && info->is_definition) {
333
334
					DBG((dbg, LEVEL_3, "\t...found definition %+F\n", info->u.definition));
					block_info->u.last_definition = info->u.definition;
335
336
337
					break;
				}
			}
338

339
			assert(block_info->u.last_definition && "No definition found");
340
341
		}

342
		return block_info->u.last_definition;
343
	} else {
344
		ir_node *const def = get_def_from_preds(env, block);
345
		block_info->u.last_definition = def;
346
		return def;
347
348
349
	}
}

350
351
352
/**
 * Fixes all operands of the given use.
 */
353
static void search_def_at_block(be_ssa_construction_env_t *const env, ir_node *const use, constr_info *const info)
354
355
{
	ir_node     *block      = get_nodes_block(use);
356
	constr_info *block_info = get_or_set_info(env, block);
357
358
359
360

	if (block_info->already_processed)
		return;

361
	if (has_definition(block)) {
362
363
		process_block(env, block);
	} else {
364
		ir_node *const def = get_def_from_preds(env, block);
365
		set_operands(env, use, def, info);
366
367
368
	}
}

369
void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg)
370
{
Matthias Braun's avatar
Matthias Braun committed
371
	stat_ev_ctx_push_fmt("bessaconstr", "%+F", irg);
372
	stat_ev_tim_push();
373

374
	stat_ev_dbl("bessaconstr_n_blocks", get_Block_dom_max_subtree_pre_num(get_irg_start_block(irg)));
375
376

	memset(env, 0, sizeof(env[0]));
377
378
379
380

	env->irg       = irg;
	env->new_phis  = NEW_ARR_F(ir_node*, 0);
	env->worklist  = new_waitq();
381
382
	ir_nodemap_init(&env->infos, irg);
	obstack_init(&env->obst);
383

Matthias Braun's avatar
Matthias Braun committed
384
385
386
	assure_irg_properties(env->irg,
	                      IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS);

387
388
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED
			| IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK);
389
390
391
392
393

	/* we use the visited flag to indicate blocks in the dominance frontier
	 * and blocks that already have the relevant value at the end calculated */
	inc_irg_visited(irg);
	/* We use the block visited flag to indicate blocks in the dominance
Michael Beck's avatar
Michael Beck committed
394
	 * frontier of some values (and this potentially needing phis) */
395
396
397
398
399
	inc_irg_block_visited(irg);
}

void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
{
400
	stat_ev_int("bessaconstr_phis", ARR_LEN(env->new_phis));
401
402
	obstack_free(&env->obst, NULL);
	ir_nodemap_destroy(&env->infos);
403
404
405
	del_waitq(env->worklist);
	DEL_ARR_F(env->new_phis);

406
407
	ir_free_resources(env->irg, IR_RESOURCE_IRN_VISITED
			| IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK);
408
409
410

	stat_ev_tim_pop("bessaconstr_total_time");
	stat_ev_ctx_pop("bessaconstr");
411
412
}

413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
static void determine_phi_req(be_ssa_construction_env_t *env, ir_node *value)
{
	const arch_register_req_t *req   = arch_get_irn_register_req(value);
	env->mode = get_irn_mode(value);
	if (req->width == 1) {
		env->phi_req = req->cls->class_req;
	} else {
		/* construct a new register req... */
		ir_graph            *irg     = get_irn_irg(value);
		struct obstack      *obst    = be_get_be_obst(irg);
		arch_register_req_t *new_req = OALLOCZ(obst, arch_register_req_t);
		new_req->cls   = req->cls;
		new_req->type  = req->type & arch_register_req_type_aligned;
		new_req->width = req->width;
		env->phi_req = new_req;
	}
}

431
432
433
434
435
436
437
void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
                                  ir_node *copy)
{
	ir_node *block;

	assert(env->iterated_domfront_calculated == 0);

438
	if (env->mode == NULL) {
439
		determine_phi_req(env, copy);
440
441
442
443
444
445
	} else {
		assert(env->mode == get_irn_mode(copy));
	}

	block = get_nodes_block(copy);

446
	if (!has_definition(block)) {
447
448
		waitq_put(env->worklist, block);
	}
449
	introduce_definition(env, copy);
450
451
452
453
454
455
456
457
458
}

void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
                                    ir_node **copies, size_t copies_len)
{
	size_t i;

	assert(env->iterated_domfront_calculated == 0);

459
	if (env->mode == NULL) {
460
		determine_phi_req(env, copies[0]);
461
462
	}

463
	for (i = 0; i < copies_len; ++i) {
464
		ir_node *copy  = copies[i];
465
466
467
		ir_node *block = get_nodes_block(copy);

		assert(env->mode == get_irn_mode(copy));
468
		if (!has_definition(block)) {
469
470
			waitq_put(env->worklist, block);
		}
471
		introduce_definition(env, copy);
472
473
474
475
476
477
478
479
	}
}

ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
{
	return env->new_phis;
}

480
481
482
483
484
/**
 * Fixes all arguments of a newly constructed phi.
 *
 * @see insert_dummy_phi
 */
485
static void fix_phi_arguments(be_ssa_construction_env_t *const env, ir_node *const phi, constr_info *const info)
486
487
488
{
	DBG((dbg, LEVEL_3, "\tfixing phi arguments  %+F\n", phi));

489
490
	ir_node *const block = get_nodes_block(phi);
	foreach_irn_in(phi, i, op) {
491
492
493
494
495
496
497
498
499
500
501
502
		if (is_definition(env, op) || is_Dummy(op)) {
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
			ir_node *pred_def   = search_def_end_of_block(env, pred_block);

			DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", phi, i, pred_def));
			set_irn_n(phi, i, pred_def);
		}
	}

	info->already_processed = true;
}

503
504
void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
                                         ir_node **nodes, size_t nodes_len)
505
{
506
	size_t i;
Michael Beck's avatar
Michael Beck committed
507
	stat_ev_cnt_decl(uses);
508

509
	be_timer_push(T_SSA_CONSTR);
Matthias Braun's avatar
Matthias Braun committed
510

511
	if (!env->iterated_domfront_calculated) {
512
		mark_iterated_dominance_frontiers(env);
513
514
515
		env->iterated_domfront_calculated = 1;
	}

516
517
518
519
	DBG((dbg, LEVEL_1, "\tfixing users array\n"));

	assert(waitq_empty(env->worklist));

520
	stat_ev_tim_push();
521

522
	for (i = 0; i < nodes_len; ++i) {
523
		ir_node *value = nodes[i];
524
525
		DBG((dbg, LEVEL_3, "\tfixing users of %+F\n", value));
		introduce_definition(env, value);
526

527
		foreach_out_edge_safe(value, edge) {
528
			ir_node *const use = get_edge_src_irn(edge);
529
			if (is_Anchor(use) || is_End(use))
530
				continue;
531

532
533
534
			introduce_use(env, use);
		}
	}
535

536
	assert(!waitq_empty(env->worklist));
537

538
539
	while (!waitq_empty(env->worklist)) {
		ir_node     *use  = (ir_node *)waitq_get(env->worklist);
540
		constr_info *info = get_info(env, use);
541

542
543
544
545
		if (info->already_processed)
			continue;

		if (is_Phi(use)) {
546
			fix_phi_arguments(env, use, info);
547
		} else {
548
			DBG((dbg, LEVEL_3, "\tsearching def for %+F at %+F\n", use, get_nodes_block(use)));
549
			search_def_at_block(env, use, info);
550
		}
551
552

		stat_ev_cnt_inc(uses);
553
	}
554

555
	be_timer_pop(T_SSA_CONSTR);
Matthias Braun's avatar
Matthias Braun committed
556

557
558
	stat_ev_tim_pop("bessaconstr_fix_time");
	stat_ev_cnt_done(uses, "bessaconstr_uses");
559
560
}

561
void be_ssa_construction_fix_users(be_ssa_construction_env_t *env, ir_node *value)
562
{
563
	be_ssa_construction_fix_users_array(env, &value, 1);
564
565
}

566

567
568
569
570
571
void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
                                              be_lv_t *lv)
{
	int i, n;

572
	be_timer_push(T_SSA_CONSTR);
Matthias Braun's avatar
Matthias Braun committed
573

574
	n = ARR_LEN(env->new_phis);
575
	for (i = 0; i < n; ++i) {
576
577
578
		ir_node *phi = env->new_phis[i];
		be_liveness_introduce(lv, phi);
	}
Matthias Braun's avatar
Matthias Braun committed
579

580
	be_timer_pop(T_SSA_CONSTR);
581
582
}

Matthias Braun's avatar
Matthias Braun committed
583
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr)
584
585
586
587
void be_init_ssaconstr(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");
}