condeval.c 17.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
24
25
/**
 * @file
 * @brief   Partial condition evaluation
 * @date    10. Sep. 2006
 * @author  Christoph Mallon, Matthias Braun
 * @version $Id$
26
 */
27
28
29
30
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

31
32
#include "iroptimize.h"

33
#include <assert.h>
34
#include "array_t.h"
35
36
#include "debug.h"
#include "ircons.h"
Christoph Mallon's avatar
Christoph Mallon committed
37
38
#include "irgmod.h"
#include "irgopt.h"
39
40
#include "irgwalk.h"
#include "irnode.h"
41
#include "irnode_t.h"
42
#include "iredges.h"
43
#include "iredges_t.h"
44
#include "irtools.h"
45
#include "irgraph.h"
46
#include "tv.h"
47
#include "opt_confirms.h"
48

49
#undef AVOID_PHIB
50

51
52
DEBUG_ONLY(static firm_dbg_module_t *dbg);

Christoph Mallon's avatar
Christoph Mallon committed
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Add the new predecessor x to node node, which is either a Block or a Phi
 */
static void add_pred(ir_node* node, ir_node* x)
{
	ir_node** ins;
	int n;
	int i;

	assert(is_Block(node) || is_Phi(node));

	n = get_irn_arity(node);
	NEW_ARR_A(ir_node*, ins, n + 1);
66
67
	for (i = 0; i < n; i++)
		ins[i] = get_irn_n(node, i);
Christoph Mallon's avatar
Christoph Mallon committed
68
69
70
71
72
73
	ins[n] = x;
	set_irn_in(node, n + 1, ins);
}

static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
{
74
75
76
77
78
79
	int i;
	int n_cfgpreds;
	ir_graph *irg;
	ir_node *phi;
	ir_node **in;

80
	/* This is needed because we create bads sometimes */
81
82
	if(is_Bad(block))
		return new_Bad();
83

84
	/* already processed this block? */
85
86
87
88
89
	if(irn_visited(block)) {
		ir_node *value = (ir_node*) get_irn_link(block);
		return value;
	}

Matthias Braun's avatar
Matthias Braun committed
90
91
92
	irg = get_irn_irg(block);
	assert(block != get_irg_start_block(irg));

Christoph Mallon's avatar
Christoph Mallon committed
93
	/* a Block with only 1 predecessor needs no Phi */
94
95
96
	n_cfgpreds = get_Block_n_cfgpreds(block);
	if(n_cfgpreds == 1) {
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
Matthias Braun's avatar
Matthias Braun committed
97
		ir_node *value      = search_def_and_create_phis(pred_block, mode);
98
99
100
101
102
103

		set_irn_link(block, value);
		mark_irn_visited(block);
		return value;
	}

104
	/* create a new Phi */
Christoph Mallon's avatar
Christoph Mallon committed
105
	NEW_ARR_A(ir_node*, in, n_cfgpreds);
106
107
108
109
110
111
112
	for(i = 0; i < n_cfgpreds; ++i)
		in[i] = new_Unknown(mode);

	phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
	set_irn_link(block, phi);
	mark_irn_visited(block);

113
	/* set Phi predecessors */
114
115
	for(i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred_block = get_Block_cfgpred_block(block, i);
Christoph Mallon's avatar
Christoph Mallon committed
116
		ir_node *pred_val = search_def_and_create_phis(pred_block, mode);
117
118
119
120
121
122
123
124

		set_irn_n(phi, i, pred_val);
	}

	return phi;
}

/**
125
126
127
 * Given a set of values this function constructs SSA-form for the users of the
 * first value (the users are determined through the out-edges of the value).
 * Uses the irn_visited flags. Works without using the dominance tree.
128
 */
129
static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
Christoph Mallon's avatar
Christoph Mallon committed
130
{
131
132
133
	int i;
	ir_graph *irg;
	ir_mode *mode;
134
135
136
	const ir_edge_t *edge;
	const ir_edge_t *next;
	ir_node *value;
137

Matthias Braun's avatar
Matthias Braun committed
138
	assert(n_vals == 2);
139
140
141
142
143
144
145

	irg = get_irn_irg(vals[0]);
	inc_irg_visited(irg);

	mode = get_irn_mode(vals[0]);
	for(i = 0; i < n_vals; ++i) {
		ir_node *value = vals[i];
146
		ir_node *value_block = blocks[i];
147

Matthias Braun's avatar
Matthias Braun committed
148
		assert(get_irn_mode(value) == mode || is_Bad(value));
149
150
151
152
153

		set_irn_link(value_block, value);
		mark_irn_visited(value_block);
	}

154
	/* Only fix the users of the first, i.e. the original node */
155
156
157
158
159
160
161
	value = vals[0];

	foreach_out_edge_safe(value, edge, next) {
		ir_node *user = get_edge_src_irn(edge);
		int j = get_edge_src_pos(edge);
		ir_node *user_block = get_nodes_block(user);
		ir_node *newval;
162

163
164
		/* ignore keeps */
		if (is_End(user))
165
			continue;
166

Matthias Braun's avatar
Matthias Braun committed
167
168
169
		if (user_block == blocks[1])
			continue;

170
171
172
173
174
175
176
		DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));

		if(is_Phi(user)) {
			ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
			newval = search_def_and_create_phis(pred_block, mode);
		} else {
			newval = search_def_and_create_phis(user_block, mode);
177
178
		}

179
		/* don't fix newly created Phis from the SSA construction */
180
181
182
		if (newval != user) {
			DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
			set_irn_n(user, j, newval);
183
184
185
186
		}
	}
}

187
188
189
190
191
static void split_critical_edge(ir_node *block, int pos) {
	ir_graph *irg = get_irn_irg(block);
	ir_node *in[1];
	ir_node *new_block;
	ir_node *new_jmp;
Christoph Mallon's avatar
Christoph Mallon committed
192

193
194
195
196
	in[0] = get_Block_cfgpred(block, pos);
	new_block = new_r_Block(irg, 1, in);
	new_jmp = new_r_Jmp(irg, new_block);
	set_Block_cfgpred(block, pos, new_jmp);
Christoph Mallon's avatar
Christoph Mallon committed
197
198
}

199
200
typedef struct condeval_env_t {
	ir_node       *true_block;
201
	ir_node       *cmp;        /**< The Compare node that might be partial evaluated */
202
	pn_Cmp         pnc;        /**< The Compare mode of the Compare node. */
203
204
	ir_node       *cnst;
	tarval        *tv;
205
	ir_visited_t   visited_nr;
206
207
208
209

	ir_node       *cnst_pred;   /**< the block before the constant */
	int            cnst_pos;    /**< the pos to the constant block (needed to
	                                  kill that edge later) */
210
} condeval_env_t;
Christoph Mallon's avatar
Christoph Mallon committed
211

Matthias Braun's avatar
Matthias Braun committed
212
213
214
215
216
217
218
219
static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block,
                                  ir_node *copy_block, int j, ir_node *node) {
	int      i, arity;
	ir_node *copy;

	/* we can evaluate Phis right now, all other nodes get copied */
	if (is_Phi(node)) {
		copy = get_Phi_pred(node, j);
220
		/* we might have to evaluate a Phi-cascade */
Matthias Braun's avatar
Matthias Braun committed
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
		if(get_irn_visited(copy) >= env->visited_nr) {
			copy = get_irn_link(copy);
		}
	} else {
		copy = exact_copy(node);
		set_nodes_block(copy, copy_block);

		assert(get_irn_mode(copy) != mode_X);

		arity = get_irn_arity(copy);
		for(i = 0; i < arity; ++i) {
			ir_node *pred     = get_irn_n(copy, i);
			ir_node *new_pred;

			if(get_nodes_block(pred) != block)
				continue;

			if(get_irn_visited(pred) >= env->visited_nr) {
				new_pred = get_irn_link(pred);
			} else {
				new_pred = copy_and_fix_node(env, block, copy_block, j, pred);
			}
			set_irn_n(copy, i, new_pred);
		}
	}

	set_irn_link(node, copy);
	set_irn_visited(node, env->visited_nr);

	return copy;
}

253
254
static void copy_and_fix(const condeval_env_t *env, ir_node *block,
                         ir_node *copy_block, int j) {
255
256
257
258
259
260
	const ir_edge_t *edge;

	/* Look at all nodes in the cond_block and copy them into pred */
	foreach_out_edge(block, edge) {
		ir_node *node = get_edge_src_irn(edge);
		ir_node *copy;
261
262
263
264
265
266
267
		ir_mode *mode;

		if (is_Block(node)) {
			/* Block->Block edge, should be the MacroBlock edge */
			assert(get_Block_MacroBlock(node) == block && "Block->Block edge found");
			continue;
		}
268
269

		/* ignore control flow */
270
		mode = get_irn_mode(node);
271
		if (mode == mode_X || is_Cond(node))
272
			continue;
273
#ifdef AVOID_PHIB
274
		/* we may not copy mode_b nodes, because this could produce Phi with
275
		 * mode_bs which can't be handled in all backends. Instead we duplicate
Christoph Mallon's avatar
Christoph Mallon committed
276
		 * the node and move it to its users */
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
		if (mode == mode_b) {
			const ir_edge_t *edge, *next;
			ir_node *pred;
			int      pn;

			assert(is_Proj(node));

			pred = get_Proj_pred(node);
			pn   = get_Proj_proj(node);

			foreach_out_edge_safe(node, edge, next) {
				ir_node *cmp_copy;
				ir_node *user       = get_edge_src_irn(edge);
				int pos             = get_edge_src_pos(edge);
				ir_node *user_block = get_nodes_block(user);

				if(user_block == block)
					continue;

				cmp_copy = exact_copy(pred);
				set_nodes_block(cmp_copy, user_block);
				copy = new_r_Proj(current_ir_graph, user_block, cmp_copy, mode_b, pn);
				set_irn_n(user, pos, copy);
			}
			continue;
		}
303
#endif
Christoph Mallon's avatar
Christoph Mallon committed
304

Matthias Braun's avatar
Matthias Braun committed
305
		copy = copy_and_fix_node(env, block, copy_block, j, node);
306
307

		/* we might hit values in blocks that have already been processed by a
308
		 * recursive find_phi_with_const() call */
309
310
311
312
313
314
315
		assert(get_irn_visited(copy) <= env->visited_nr);
		if(get_irn_visited(copy) >= env->visited_nr) {
			ir_node *prev_copy = get_irn_link(copy);
			if(prev_copy != NULL)
				set_irn_link(node, prev_copy);
		}
	}
Christoph Mallon's avatar
Christoph Mallon committed
316

317
318
319
320
321
	/* fix data-flow (and reconstruct SSA if needed) */
	foreach_out_edge(block, edge) {
		ir_node *vals[2];
		ir_node *blocks[2];
		ir_node *node = get_edge_src_irn(edge);
322
323
324
325
326
327
328
		ir_mode *mode;

		if (is_Block(node)) {
			/* Block->Block edge, should be the MacroBlock edge */
			assert(get_Block_MacroBlock(node) == block && "Block->Block edge found");
			continue;
		}
329

330
		mode = get_irn_mode(node);
331
		if (mode == mode_X || is_Cond(node))
332
			continue;
333
#ifdef AVOID_PHIB
334
		if (mode == mode_b)
335
			continue;
336
#endif
337

338
339
		DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node));

340
341
342
343
344
345
346
347
		blocks[0] = block;
		vals[0] = node;
		blocks[1] = copy_block;
		vals[1] = get_irn_link(node);
		construct_ssa(blocks, vals, 2);
	}
}

348
/**
Michael Beck's avatar
Michael Beck committed
349
 * returns whether the cmp evaluates to true or false, or can't be evaluated!
350
 * 1: true, 0: false, -1: can't evaluate
351
352
353
354
 *
 * @param pnc       the compare mode of the Compare
 * @param tv_left   the left tarval
 * @param tv_right  the right tarval
355
 */
356
357
static int eval_cmp_tv(pn_Cmp pnc, tarval *tv_left, tarval *tv_right) {
	pn_Cmp cmp_result = tarval_cmp(tv_left, tv_right);
358

359
360
	/* does the compare evaluate to true? */
	if (cmp_result == pn_Cmp_False)
361
		return -1;
362
	if ((cmp_result & pnc) != cmp_result)
363
364
365
366
367
		return 0;

	return 1;
}

368
/**
369
370
371
372
373
 * returns whether the cmp evaluates to true or false, or can't be evaluated!
 * 1: true, 0: false, -1: can't evaluate
 *
 * @param env      the environment
 * @param cand     the candidate node, either a Const or a Confirm
374
 */
375
376
377
378
379
380
381
382
383
384
385
386
static int eval_cmp(condeval_env_t *env, ir_node *cand) {
	if (is_Const(cand)) {
		tarval *tv_cand   = get_Const_tarval(cand);
		tarval *tv_cmp    = get_Const_tarval(env->cnst);

		return eval_cmp_tv(env->pnc, tv_cand, tv_cmp);
	} else { /* a Confirm */
		tarval *res = computed_value_Cmp_Confirm(env->cmp, cand, env->cnst, env->pnc);

		if (res == tarval_bad)
			return -1;
		return res == tarval_b_true;
387
	}
388
389
390
391
392
393
394
395
}

/**
 * Check for Const or Confirm with Const.
 */
static int is_Const_or_Confirm(const ir_node *node) {
	if (is_Confirm(node))
		node = get_Confirm_bound(node);
396
397
398
399
	return is_Const(node);
}

/**
400
 * get the tarval of a Const or Confirm with
401
402
403
 */
static tarval *get_Const_or_Confirm_tarval(const ir_node *node) {
	if (is_Confirm(node)) {
404
		if (get_Confirm_bound(node))
405
406
407
408
409
			node = get_Confirm_bound(node);
	}
	return get_Const_tarval(node);
}

410
static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_node *value)
411
{
412
413
	ir_node *block = get_nodes_block(jump);

414
	if (irn_visited(value))
415
416
417
		return NULL;
	mark_irn_visited(value);

418
419
	if (is_Const_or_Confirm(value)) {
		if (eval_cmp(env, value) <= 0) {
420
			return NULL;
421
		}
Christoph Mallon's avatar
Christoph Mallon committed
422
423
424

		DB((
			dbg, LEVEL_1,
425
426
			"> Found condition evaluation candidate %+F->%+F\n",
			env->true_block, block
Christoph Mallon's avatar
Christoph Mallon committed
427
428
		));

429
		/* adjust true_block to point directly towards our jump */
430
		add_pred(env->true_block, jump);
431

432
		split_critical_edge(env->true_block, 0);
433

434
		/* we need a bigger visited nr when going back */
435
		env->visited_nr++;
436

437
438
		return block;
	}
439

440
441
	if(is_Phi(value)) {
		int i, arity;
Christoph Mallon's avatar
Christoph Mallon committed
442

443
		/* the Phi has to be in the same Block as the Jmp */
444
		if(get_nodes_block(value) != block) {
445
			return NULL;
446
		}
447

448
449
450
451
		arity = get_irn_arity(value);
		for(i = 0; i < arity; ++i) {
			ir_node *copy_block;
			ir_node *phi_pred = get_Phi_pred(value, i);
452
			ir_node *cfgpred  = get_Block_cfgpred(block, i);
453

454
			copy_block = find_const_or_confirm(env, cfgpred, phi_pred);
455
			if(copy_block == NULL)
456
457
				continue;

458
			/* copy duplicated nodes in copy_block and fix SSA */
459
			copy_and_fix(env, block, copy_block, i);
460

461
462
			if(copy_block == get_nodes_block(cfgpred)) {
				env->cnst_pred = block;
463
				env->cnst_pos  = i;
464
			}
465

466
			/* return now as we can't process more possibilities in 1 run */
467
			return copy_block;
468
		}
Christoph Mallon's avatar
Christoph Mallon committed
469
	}
470

471
	return NULL;
Christoph Mallon's avatar
Christoph Mallon committed
472
473
}

474
475
static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
                               ir_node *value)
476
{
477
478
479
480
	ir_node *block = get_nodes_block(jump);

	if(irn_visited(value)) {
		return NULL;
481
	}
482
483
	mark_irn_visited(value);

484
	if (is_Const_or_Confirm(value)) {
485
		tarval *tv = get_Const_or_Confirm_tarval(value);
486

487
		if (tv != env->tv)
488
489
490
491
492
493
494
495
			return NULL;

		DB((
			dbg, LEVEL_1,
			"> Found condition evaluation candidate %+F->%+F\n",
			env->true_block, block
		));

496
		/* adjust true_block to point directly towards our jump */
497
498
499
		add_pred(env->true_block, jump);

		split_critical_edge(env->true_block, 0);
500

501
		/* we need a bigger visited nr when going back */
502
		env->visited_nr++;
503

504
		return block;
505
	}
506
507
	if(is_Phi(value)) {
		int i, arity;
508

509
		/* the Phi has to be in the same Block as the Jmp */
510
511
		if(get_nodes_block(value) != block)
			return NULL;
512

513
514
515
516
517
		arity = get_irn_arity(value);
		for(i = 0; i < arity; ++i) {
			ir_node *copy_block;
			ir_node *phi_pred = get_Phi_pred(value, i);
			ir_node *cfgpred  = get_Block_cfgpred(block, i);
518

519
520
521
522
523
524
525
526
527
528
529
530
			copy_block = find_candidate(env, cfgpred, phi_pred);
			if(copy_block == NULL)
				continue;

			/* copy duplicated nodes in copy_block and fix SSA */
			copy_and_fix(env, block, copy_block, i);

			if(copy_block == get_nodes_block(cfgpred)) {
				env->cnst_pred = block;
				env->cnst_pos  = i;
			}

531
			/* return now as we can't process more possibilities in 1 run */
532
			return copy_block;
Christoph Mallon's avatar
Christoph Mallon committed
533
		}
534
535
536
537
538
539
540
541
	}
	if(is_Proj(value)) {
		ir_node *left;
		ir_node *right;
		int      pnc;
		ir_node *cmp = get_Proj_pred(value);
		if(!is_Cmp(cmp))
			return NULL;
542

543
544
545
		left  = get_Cmp_left(cmp);
		right = get_Cmp_right(cmp);
		pnc   = get_Proj_proj(value);
546

547
548
549
550
551
552
		/* we assume that the constant is on the right side, swap left/right
		 * if needed */
		if(is_Const(left)) {
			ir_node *t = left;
			left       = right;
			right      = t;
553

554
555
			pnc        = get_inversed_pnc(pnc);
		}
556

557
		if(!is_Const(right))
558
			return 0;
559

560
561
562
		if(get_nodes_block(left) != block) {
			return 0;
		}
563

564
		/* negate condition when we're looking for the false block */
565
		if(env->tv == tarval_b_false) {
566
			pnc = get_negated_pnc(pnc, get_irn_mode(right));
567
		}
568

569
		/* (recursively) look if a pred of a Phi is a constant or a Confirm */
570
		env->cmp  = cmp;
571
572
573
		env->pnc  = pnc;
		env->cnst = right;

574
		return find_const_or_confirm(env, jump, left);
575
	}
576

577
578
	return NULL;
}
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594

/**
 * Block-walker: searches for the following construct
 *
 *  Const or Phi with constants
 *           |
 *          Cmp
 *           |
 *         Cond
 *          /
 *       ProjX
 *        /
 *     Block
 */
static void cond_eval(ir_node* block, void* data)
{
595
	condeval_env_t env;
596
	int *changed = data;
597
	ir_node *selector;
598
599
	ir_node *projx;
	ir_node *cond;
600
	ir_node *copy_block;
601
	int      selector_evaluated;
602
603
604
	const ir_edge_t *edge, *next;
	ir_node* bad;
	size_t   cnst_pos;
605
606
607
608
609
610
611
612
613
614
615
616
617

	if(get_Block_n_cfgpreds(block) != 1)
		return;

	projx = get_Block_cfgpred(block, 0);
	if (!is_Proj(projx))
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
	if (!is_Cond(cond))
		return;

618
	selector = get_Cond_selector(cond);
619
	/* TODO handle switch Conds */
620
	if (get_irn_mode(selector) != mode_b)
621
		return;
622

Michael Beck's avatar
Michael Beck committed
623
	/* handle cases that can be immediately evaluated */
624
625
626
627
628
629
630
631
632
633
634
	selector_evaluated = -1;
	if(is_Proj(selector)) {
		ir_node *cmp = get_Proj_pred(selector);
		if(is_Cmp(cmp)) {
			ir_node *left  = get_Cmp_left(cmp);
			ir_node *right = get_Cmp_right(cmp);
			if(is_Const(left) && is_Const(right)) {
				int     pnc      = get_Proj_proj(selector);
				tarval *tv_left  = get_Const_tarval(left);
				tarval *tv_right = get_Const_tarval(right);

635
				selector_evaluated = eval_cmp_tv(pnc, tv_left, tv_right);
636
637
				if(selector_evaluated < 0)
					return;
638
639
			}
		}
640
	} else if (is_Const_or_Confirm(selector)) {
641
		tarval *tv = get_Const_or_Confirm_tarval(selector);
642
		if(tv == tarval_b_true) {
643
644
			selector_evaluated = 1;
		} else {
645
			assert(tv == tarval_b_false);
646
647
648
649
650
			selector_evaluated = 0;
		}
	}

	env.cnst_pred = NULL;
651
	if (get_Proj_proj(projx) == pn_Cond_false) {
652
		env.tv = tarval_b_false;
653
654
		if(selector_evaluated >= 0)
			selector_evaluated = !selector_evaluated;
655
	} else {
656
		env.tv = tarval_b_true;
657
658
	}

659
660
661
662
663
664
665
666
667
668
669
670
671
	if(selector_evaluated == 0) {
		bad = new_Bad();
		exchange(projx, bad);
		*changed = 1;
		return;
	} else if(selector_evaluated == 1) {
		dbg_info *dbgi = get_irn_dbg_info(selector);
		ir_node  *jmp  = new_rd_Jmp(dbgi, current_ir_graph, get_nodes_block(projx));
		exchange(projx, jmp);
		*changed = 1;
		return;
	}

672
	/* (recursively) look if a pred of a Phi is a constant or a Confirm */
673
674
675
676
677
678
	env.true_block = block;
	inc_irg_visited(current_ir_graph);
	env.visited_nr = get_irg_visited(current_ir_graph);

	copy_block = find_candidate(&env, projx, selector);
	if (copy_block == NULL)
679
680
		return;

681
	/* we have to remove the edge towards the pred as the pred now
682
	 * jumps into the true_block. We also have to shorten Phis
683
684
685
686
	 * in our block because of this */
	bad      = new_Bad();
	cnst_pos = env.cnst_pos;

687
	/* shorten Phis */
688
689
690
691
692
693
694
695
696
697
698
	foreach_out_edge_safe(env.cnst_pred, edge, next) {
		ir_node *node = get_edge_src_irn(edge);

		if(is_Phi(node))
			set_Phi_pred(node, cnst_pos, bad);
	}

	set_Block_cfgpred(env.cnst_pred, cnst_pos, bad);

	/* the graph is changed now */
	*changed = 1;
699
700
701
702
}

void opt_cond_eval(ir_graph* irg)
{
Michael Beck's avatar
Michael Beck committed
703
	int changed, rerun;
704

705
706
707
708
	FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");

	DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));

Christoph Mallon's avatar
Christoph Mallon committed
709
	remove_critical_cf_edges(irg);
710
	normalize_proj_nodes(irg);
711

Michael Beck's avatar
Michael Beck committed
712
	edges_assure(irg);
713
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
714

Michael Beck's avatar
Michael Beck committed
715
	changed = 0;
716
	do {
Michael Beck's avatar
Michael Beck committed
717
718
719
720
721
		rerun = 0;
		irg_block_walk_graph(irg, cond_eval, NULL, &rerun);
		changed |= rerun;
	} while (rerun);

722
	ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
723

Michael Beck's avatar
Michael Beck committed
724
725
	if (changed) {
		/* control flow changed, some blocks may become dead */
726
		set_irg_outs_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
727
728
729
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
730
731
732
733

		/* Dead code might be created. Optimize it away as it is dangerous
		 * to call optimize_df() an dead code. */
		optimize_cf(irg);
Michael Beck's avatar
Michael Beck committed
734
	}
735
}