ifconv.c 12.7 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
8
9
 * @brief   If conversion
 * @author  Christoph Mallon
10
 */
11
#include <assert.h>
12
13
#include <stdbool.h>

yb9976's avatar
yb9976 committed
14
#include "adt/pdeq.h"
yb9976's avatar
yb9976 committed
15
#include "be.h"
16
#include "cdep_t.h"
yb9976's avatar
yb9976 committed
17
#include "debug.h"
18
19
20
21
#include "ircons.h"
#include "irgmod.h"
#include "irgopt.h"
#include "irgwalk.h"
yb9976's avatar
yb9976 committed
22
23
#include "irnode_t.h"
#include "iroptimize.h"
24
25
#include "irtools.h"

26
27
28
29
/**
 * Environment for if-conversion.
 */
typedef struct walker_env {
30
31
	arch_allow_ifconv_func allow_ifconv;
	bool                   changed; /**< Set if the graph was changed. */
32
33
} walker_env;

34
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
35

Michael Beck's avatar
Michael Beck committed
36
37
/**
 * Returns non-zero if a Block can be emptied.
38
39
 *
 * @param block  the block
Michael Beck's avatar
Michael Beck committed
40
 */
41
42
static bool can_empty_block(ir_node *block)
{
43
	return get_Block_mark(block) == 0;
44
45
}

46
47
48
49
50
51
52
53
54
55
/**
 * Find the ProjX node leading from block dependency to block start.
 *
 * @param start       a block that is control depended on dependency
 * @param dependency  the block that decides whether start is executed
 *
 * @return a ProjX node that represent the decision control flow or
 *         NULL is start is not dependent at all or a block on the way
 *         cannot be emptied
 */
yb9976's avatar
yb9976 committed
56
static ir_node *walk_to_projx(ir_node *start, const ir_node *dependency)
57
58
{
	/* No need to find the conditional block if this block cannot be emptied and
59
	 * therefore not moved */
60
61
	if (!can_empty_block(start)) return NULL;

62
	foreach_irn_in(start, i, pred) {
yb9976's avatar
yb9976 committed
63
		ir_node *pred_block = get_nodes_block(skip_Proj(pred));
64

65
		if (pred_block == dependency) {
66
67
			if (is_Proj(pred)) {
				assert(get_irn_mode(pred) == mode_X);
68
				/* we found it */
69
70
				return pred;
			}
71
			/* Not a Proj? Should not happen. */
72
			return NULL;
73
74
		}

75
76
		if (is_Proj(pred)) {
			assert(get_irn_mode(pred) == mode_X);
77
			/* another Proj but not from the control block */
78
79
80
			return NULL;
		}

81
82
83
84
85
86
87
88
		if (is_cdep_on(pred_block, dependency)) {
			return walk_to_projx(pred_block, dependency);
		}
	}
	return NULL;
}


Michael Beck's avatar
Michael Beck committed
89
/**
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 * Recursively copies the DAG starting at node to the i-th predecessor
 * block of src_block
 * - if node isn't in the src_block, recursion ends and node is returned
 * - if node is a Phi in the src_block, the i-th predecessor of this Phi is
 *   returned and recursion ends
 * otherwise returns a copy of the passed node created in the i-th predecessor of
 * src_block.
 *
 * @param node       a root of a DAG
 * @param src_block  the block of the DAG
 * @param i          the position of the predecessor the DAG
 *                   is moved to
 *
 * @return  the root of the copied DAG
104
 */
yb9976's avatar
yb9976 committed
105
static ir_node *copy_to(ir_node *node, ir_node *src_block, int i)
106
{
107
108
109
110
111
112
113
114
	if (get_nodes_block(node) != src_block) {
		/* already outside src_block, do not copy */
		return node;
	}
	if (is_Phi(node)) {
		/* move through the Phi to the i-th predecessor */
		return get_irn_n(node, i);
	}
115

116
	/* else really need a copy */
yb9976's avatar
yb9976 committed
117
	ir_node *copy      = exact_copy(node);
yb9976's avatar
yb9976 committed
118
	ir_node *dst_block = get_Block_cfgpred_block(src_block, i);
119
120
	set_nodes_block(copy, dst_block);

Michael Beck's avatar
Michael Beck committed
121
122
	DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
		node, dst_block, copy));
123

124
	/* move recursively all predecessors */
125
126
127
128
	foreach_irn_in_r(node, j, pred) {
		ir_node *const copy_pred = copy_to(pred, src_block, i);
		set_irn_n(copy, j, copy_pred);
		DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, copy_pred));
129
130
131
132
133
	}
	return copy;
}


134
/**
135
136
137
138
139
140
141
 * Remove predecessors i and j (i < j) from a node and
 * add an additional predecessor new_pred.
 *
 * @param node      the node whose inputs are changed
 * @param i         the first index to remove
 * @param j         the second index to remove
 * @param new_pred  a node that is added as a new input to node
142
 */
yb9976's avatar
yb9976 committed
143
static void rewire(ir_node *node, int i, int j, ir_node *new_pred)
144
145
{
	int arity = get_irn_arity(node);
yb9976's avatar
yb9976 committed
146
	ir_node **ins = ALLOCAN(ir_node*, arity - 1);
147
148
	int k;

yb9976's avatar
yb9976 committed
149
	int l = 0;
150
151
152
	for (k = 0; k < i;     ++k) ins[l++] = get_irn_n(node, k);
	for (++k;   k < j;     ++k) ins[l++] = get_irn_n(node, k);
	for (++k;   k < arity; ++k) ins[l++] = get_irn_n(node, k);
153
154
155
156
157
158
	ins[l++] = new_pred;
	assert(l == arity - 1);
	set_irn_in(node, l, ins);
}


159
/**
Andreas Zwinkau's avatar
typo    
Andreas Zwinkau committed
160
 * Remove the j-th predecessor from the i-th predecessor of block and add it to block
161
 */
yb9976's avatar
yb9976 committed
162
static void split_block(ir_node *block, int i, int j)
163
{
yb9976's avatar
yb9976 committed
164
	ir_node  *pred_block = get_Block_cfgpred_block(block, i);
165
	int       arity      = get_Block_n_cfgpreds(block);
Christoph Mallon's avatar
Christoph Mallon committed
166
	ir_node **ins        = ALLOCAN(ir_node*, arity + 1);
167
168
169

	DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));

yb9976's avatar
yb9976 committed
170
	for (ir_node *phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
yb9976's avatar
yb9976 committed
171
		ir_node *copy = copy_to(get_irn_n(phi, i), pred_block, j);
172

yb9976's avatar
yb9976 committed
173
		int k;
174
175
176
		for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
		ins[k++] = copy;
		for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
Matthias Braun's avatar
Matthias Braun committed
177
178
		ins[k++] = get_irn_n(phi, i);
		set_irn_in(phi, k, ins);
179
180
	}

yb9976's avatar
yb9976 committed
181
	int k;
182
	for (k = 0; k < i; ++k) ins[k] = get_Block_cfgpred(block, k);
183
	ins[k++] = get_irn_n(pred_block, j);
184
185
	for (; k < arity; ++k) ins[k] = get_Block_cfgpred(block, k);
	ins[k++] = get_Block_cfgpred(block, i);
Matthias Braun's avatar
Matthias Braun committed
186
	set_irn_in(block, k, ins);
187

yb9976's avatar
yb9976 committed
188
189
	int       new_pred_arity = get_irn_arity(pred_block) - 1;
	ir_node **pred_ins       = ALLOCAN(ir_node*, new_pred_arity);
190

yb9976's avatar
yb9976 committed
191
	for (ir_node *next, *phi = get_Block_phis(pred_block); phi != NULL; phi = next) {
192
		next = get_Phi_next(phi);
Christoph Mallon's avatar
Christoph Mallon committed
193
194
195
		for (k = 0; k != j;              ++k) pred_ins[k] = get_irn_n(phi, k);
		for (;      k != new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
		if (k == 1) {
196
197
			if (get_irn_mode(phi) == mode_M)
				remove_keep_alive(phi);
198
			exchange(phi, pred_ins[0]);
Christoph Mallon's avatar
Christoph Mallon committed
199
200
		} else {
			set_irn_in(phi, k, pred_ins);
201
202
203
		}
	}

Christoph Mallon's avatar
Christoph Mallon committed
204
205
206
	for (k = 0; k != j;              ++k) pred_ins[k] = get_irn_n(pred_block, k);
	for (;      k != new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
	if (k == 1) {
207
		exchange(pred_block, get_nodes_block(pred_ins[0]));
Christoph Mallon's avatar
Christoph Mallon committed
208
209
	} else {
		set_irn_in(pred_block, k, pred_ins);
210
211
212
213
	}
}


yb9976's avatar
yb9976 committed
214
static void prepare_path(ir_node *block, int i, const ir_node *dependency)
215
{
yb9976's avatar
yb9976 committed
216
	ir_node *pred = get_Block_cfgpred_block(block, i);
217
218
219

	DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));

yb9976's avatar
yb9976 committed
220
221
222
223
224
225
	/* Optimize blocks with only one predecessor. */
	while (get_irn_arity(pred) == 1) {
		for (ir_node *next, *phi = get_Block_phis(pred); phi != NULL; phi = next) {
			next = get_Phi_next(phi);

			ir_node *operand = get_irn_n(phi, 0);
226
227
			if (get_irn_mode(phi) == mode_M)
				remove_keep_alive(phi);
yb9976's avatar
yb9976 committed
228
229
230
231
232
233
234
235
236
237
238
239
			exchange(phi, operand);
		}

		ir_node *pred_pred = get_Block_cfgpred(pred, 0);
		if (!is_Jmp(pred_pred))
			break;

		ir_node *pred_pred_block = get_nodes_block(pred_pred);
		exchange(pred, pred_pred_block);
		pred = pred_pred_block;
	}

yb9976's avatar
yb9976 committed
240
241
	int pred_arity = get_irn_arity(pred);
	for (int j = 0; j < pred_arity; ++j) {
yb9976's avatar
yb9976 committed
242
		ir_node *pred_pred = get_Block_cfgpred_block(pred, j);
243

244
		if (pred_pred != dependency && is_cdep_on(pred_pred, dependency)) {
245
246
247
248
249
250
251
			prepare_path(pred, j, dependency);
			split_block(block, i, j);
			break;
		}
	}
}

252
253
254
255
/**
 * Block walker: Search for diamonds and do the if conversion.
 */
static void if_conv_walker(ir_node *block, void *ctx)
256
{
257
	walker_env *env = (walker_env*)ctx;
258

yb9976's avatar
yb9976 committed
259
260
261
262
	/* We might have replaced this block already. */
	if (!is_Block(block))
		return;

Michael Beck's avatar
Michael Beck committed
263
	/* Bail out, if there are no Phis at all */
264
	if (get_Block_phis(block) == NULL) return;
265

yb9976's avatar
yb9976 committed
266
267
268
269
restart:;
	int arity = get_irn_arity(block);
	for (int i = 0; i < arity; ++i) {
		ir_node *pred0 = get_Block_cfgpred_block(block, i);
270
271
		if (pred0 == block) continue;

yb9976's avatar
yb9976 committed
272
273
		for (ir_cdep *cdep = find_cdep(pred0); cdep != NULL; cdep = get_cdep_next(cdep)) {
			const ir_node *dependency = get_cdep_node(cdep);
yb9976's avatar
yb9976 committed
274
			ir_node       *projx0     = walk_to_projx(pred0, dependency);
275

276
			if (projx0 == NULL) continue;
277

yb9976's avatar
yb9976 committed
278
			ir_node *cond = get_Proj_pred(projx0);
279
280
			if (! is_Cond(cond))
				continue;
281

yb9976's avatar
yb9976 committed
282
283
			for (int j = i + 1; j < arity; ++j) {
				ir_node *pred1 = get_Block_cfgpred_block(block, j);
284
				if (pred1 == block) continue;
285

286
				if (!is_cdep_on(pred1, dependency)) continue;
287

yb9976's avatar
yb9976 committed
288
				ir_node *projx1 = walk_to_projx(pred1, dependency);
289
290
291

				if (projx1 == NULL) continue;

yb9976's avatar
yb9976 committed
292
293
294
295
296
				ir_node *sel       = get_Cond_selector(cond);
				ir_node *phi       = get_Block_phis(block);
				bool     supported = true;
				bool     negated   = get_Proj_proj(projx0) == pn_Cond_false;
				for (ir_node *p = phi; p != NULL; p = get_Phi_next(p)) {
297
298
299
300
301
302
303
304
305
					ir_node *mux_false;
					ir_node *mux_true;
					if (negated) {
						mux_true  = get_Phi_pred(p, j);
						mux_false = get_Phi_pred(p, i);
					} else {
						mux_true  = get_Phi_pred(p, i);
						mux_false = get_Phi_pred(p, j);
					}
306
307
					if (mux_true == mux_false)
						continue;
308
309
310
					ir_mode *mode = get_irn_mode(mux_true);
					if (mode == mode_M
						|| !env->allow_ifconv(sel, mux_false, mux_true)) {
311
312
313
314
315
						supported = false;
						break;
					}
				}
				if (!supported)
316
					continue;
317

318
319
320
321
				DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
					cond, projx0, projx1
				));

322
				/* remove critical edges */
323
				env->changed = true;
324
325
326
327
				prepare_path(block, i, dependency);
				prepare_path(block, j, dependency);
				arity = get_irn_arity(block);

yb9976's avatar
yb9976 committed
328
329
				ir_node  *mux_block = get_nodes_block(cond);
				dbg_info *cond_dbg  = get_irn_dbg_info(cond);
330
				do { /* generate Mux nodes in mux_block for Phis in block */
yb9976's avatar
yb9976 committed
331
332
333
					ir_node *val_i = get_irn_n(phi, i);
					ir_node *val_j = get_irn_n(phi, j);
					ir_node *mux;
334
335

					if (val_i == val_j) {
336
337
						mux = val_i;
						DB((dbg, LEVEL_2,  "Generating no Mux, because both values are equal\n"));
338
339
						if (get_irn_mode(phi) == mode_M)
							remove_keep_alive(phi);
340
					} else {
341
						ir_node *t, *f;
342

343
344
345
346
						/* Something is very fishy if two predecessors of a PhiM point into
						 * one block, but not at the same memory node
						 */
						assert(get_irn_mode(phi) != mode_M);
347
						if (negated) {
348
349
							t = val_j;
							f = val_i;
350
351
352
						} else {
							t = val_i;
							f = val_j;
353
						}
354

355
						mux = new_rd_Mux(cond_dbg, mux_block, sel, f, t, get_irn_mode(phi));
356
						DB((dbg, LEVEL_2, "Generating %+F for %+F\n", mux, phi));
357
358
					}

yb9976's avatar
yb9976 committed
359
					ir_node *next_phi = get_Phi_next(phi);
360

361
					if (arity == 2) {
362
						exchange(phi, mux);
363
					} else {
364
						rewire(phi, i, j, mux);
365
					}
366
					phi = next_phi;
367
				} while (phi != NULL);
368

369
				/* move mux operands into mux_block */
yb9976's avatar
yb9976 committed
370
371
				exchange(get_Block_cfgpred_block(block, i), mux_block);
				exchange(get_Block_cfgpred_block(block, j), mux_block);
372

373
				if (arity == 2) {
374
					unsigned mark;
375
376
377
378
379
					DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, mux_block));
					mark =  get_Block_mark(mux_block) | get_Block_mark(block);
					/* mark both block just to be sure, should be enough to mark mux_block */
					set_Block_mark(mux_block, mark);
					exchange(block, mux_block);
380
381
					return;
				} else {
382
					rewire(block, i, j, new_r_Jmp(mux_block));
383
384
					goto restart;
				}
385
386
387
388
389
			}
		}
	}
}

Michael Beck's avatar
Michael Beck committed
390
/**
391
 * Block walker: clear block marks and Phi lists.
Michael Beck's avatar
Michael Beck committed
392
393
 */
static void init_block_link(ir_node *block, void *env)
394
{
395
	(void)env;
396
397
	set_Block_mark(block, 0);
	set_Block_phis(block, NULL);
398
399
400
}


Michael Beck's avatar
Michael Beck committed
401
/**
402
 * Daisy-chain all Phis in a block.
Michael Beck's avatar
Michael Beck committed
403
 * If a non-movable node is encountered set the has_pinned flag in its block.
404
 */
405
406
static void collect_phis(ir_node *node, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
407
408
	(void) env;

Michael Beck's avatar
Michael Beck committed
409
410
	if (is_Phi(node)) {
		ir_node *block = get_nodes_block(node);
411

412
		add_Block_phi(block, node);
413
	} else {
414
		if (!is_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
Michael Beck's avatar
Michael Beck committed
415
			/*
416
			 * Ignore control flow nodes (except Raise), these will be removed.
Michael Beck's avatar
Michael Beck committed
417
			 */
418
			if (!is_cfop(node) && !is_Raise(node)) {
Michael Beck's avatar
Michael Beck committed
419
420
421
				ir_node *block = get_nodes_block(node);

				DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
422
				set_Block_mark(block, 1);
Michael Beck's avatar
Michael Beck committed
423
			}
424
425
426
427
		}
	}
}

yb9976's avatar
yb9976 committed
428
429
430
431
432
static void fill_waitq(ir_node *node, void *env) {
	pdeq *waitq = (pdeq*)env;
	pdeq_putr(waitq, node);
}

433
void opt_if_conv_cb(ir_graph *irg, arch_allow_ifconv_func callback)
434
{
yb9976's avatar
yb9976 committed
435
436
	walker_env  env   = { .allow_ifconv = callback, .changed = false };
	pdeq       *waitq = new_pdeq();
Michael Beck's avatar
Michael Beck committed
437

438
439
440
441
442
443
	assure_irg_properties(irg,
		IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
		| IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
		| IR_GRAPH_PROPERTY_NO_BADS
		| IR_GRAPH_PROPERTY_ONE_RETURN);

Michael Beck's avatar
Michael Beck committed
444
445
446
	FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");

	DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
447
448
449

	compute_cdep(irg);

450
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
451

yb9976's avatar
yb9976 committed
452
	irg_block_walk_graph(irg, init_block_link, fill_waitq, waitq);
453
	irg_walk_graph(irg, collect_phis, NULL, NULL);
yb9976's avatar
yb9976 committed
454
455
456
457
458
459

	while (! pdeq_empty(waitq)) {
		ir_node *n = (ir_node *)pdeq_getl(waitq);
		if_conv_walker(n, &env);
	}
	del_pdeq(waitq);
460

461
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
462

463
464
465
	if (env.changed) {
		local_optimize_graph(irg);
	}
Michael Beck's avatar
Michael Beck committed
466

467
	free_cdep(irg);
468

469
470
471
	confirm_irg_properties(irg,
		IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
		| IR_GRAPH_PROPERTY_ONE_RETURN);
472
}
473
474
475
476
477
478
479

void opt_if_conv(ir_graph *irg)
{
	const backend_params *be_params = be_get_backend_param();
	/* get the parameters */
	opt_if_conv_cb(irg, be_params->allow_ifconv);
}