condeval.c 16.1 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
35
36
#include "array.h"
#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
47
#include "tv.h"

48
49
//#define AVOID_PHIB

50
51
DEBUG_ONLY(static firm_dbg_module_t *dbg);

Christoph Mallon's avatar
Christoph Mallon committed
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 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);
65
66
	for (i = 0; i < n; i++)
		ins[i] = get_irn_n(node, i);
Christoph Mallon's avatar
Christoph Mallon committed
67
68
69
70
71
72
	ins[n] = x;
	set_irn_in(node, n + 1, ins);
}

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

79
80
81
	// This is needed because we create bads sometimes
	if(is_Bad(block))
		return new_Bad();
82
83
84
85
86
87
88

	// already processed this block?
	if(irn_visited(block)) {
		ir_node *value = (ir_node*) get_irn_link(block);
		return value;
	}

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

92
93
94
95
	// blocks with only 1 pred need no phi
	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
96
		ir_node *value      = search_def_and_create_phis(pred_block, mode);
97
98
99
100
101
102
103

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

	// create a new phi
Christoph Mallon's avatar
Christoph Mallon committed
104
	NEW_ARR_A(ir_node*, in, n_cfgpreds);
105
106
107
108
109
110
111
112
113
114
	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);

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

		set_irn_n(phi, i, pred_val);
	}

	return phi;
}

/**
124
125
126
 * 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.
127
 */
128
static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
Christoph Mallon's avatar
Christoph Mallon committed
129
{
130
131
132
	int i;
	ir_graph *irg;
	ir_mode *mode;
133
134
135
	const ir_edge_t *edge;
	const ir_edge_t *next;
	ir_node *value;
136

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

	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];
145
		ir_node *value_block = blocks[i];
146
147
148
149
150
151
152

		assert(get_irn_mode(value) == mode);

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

153
154
155
156
157
158
159
160
	// Only fix the users of the first, i.e. the original node
	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;
161

162
163
		// ignore keeps
		if(get_irn_op(user) == op_End)
164
			continue;
165

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

169
170
171
172
173
174
175
		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);
176
177
		}

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

186
187
188
189
190
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
191

192
193
194
195
	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
196
197
}

198
199
200
201
202
203
204
205
206
207
typedef struct condeval_env_t {
	ir_node       *true_block;
	pn_Cmp         pnc;
	ir_node       *cnst;
	tarval        *tv;
	unsigned long  visited_nr;

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

Matthias Braun's avatar
Matthias Braun committed
210
211
212
213
214
215
216
217
218
219
220
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
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);
		/* we might have to evaluate a phi-cascades */
		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;
}

251
252
static void copy_and_fix(const condeval_env_t *env, ir_node *block,
                         ir_node *copy_block, int j) {
253
254
255
256
257
258
	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;
259
260
261
262
263
264
265
		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;
		}
266
267

		/* ignore control flow */
268
		mode = get_irn_mode(node);
269
		if (mode == mode_X || is_Cond(node))
270
			continue;
271
#ifdef AVOID_PHIB
272
273
274
		/* we may not copy mode_b nodes, because this could produce phi with
		 * mode_bs which can't be handled in all backends. Instead we duplicate
		 * the node and move it to it's users */
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
		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;
		}
301
#endif
Christoph Mallon's avatar
Christoph Mallon committed
302

Matthias Braun's avatar
Matthias Braun committed
303
		copy = copy_and_fix_node(env, block, copy_block, j, node);
304
305
306
307
308
309
310
311
312
313

		/* we might hit values in blocks that have already been processed by a
		 * recursive find_phi_with_const call */
		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
314

315
316
317
318
319
	/* 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);
320
321
322
323
324
325
326
		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;
		}
327

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

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

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

346
347
348
349
/**
 * returns wether the cmp evaluates to true or false, or can't be evaluated!
 * 1: true, 0: false, -1: can't evaluate
 */
350
351
352
353
354
static int eval_cmp(pn_Cmp pnc, tarval *tv1, tarval *tv2) {
	pn_Cmp cmp_result = tarval_cmp(tv1, tv2);

	// does the compare evaluate to true?
	if(cmp_result == pn_Cmp_False)
355
		return -1;
356
357
358
359
360
361
	if((cmp_result & pnc) != cmp_result)
		return 0;

	return 1;
}

362
363
static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
{
364
365
366
367
368
369
370
371
	ir_node *block = get_nodes_block(jump);

	if(irn_visited(value))
		return NULL;
	mark_irn_visited(value);

	if(is_Const(value)) {
		tarval *tv_const = get_Const_tarval(env->cnst);
372
		tarval *tv       = get_Const_tarval(value);
373

374
		if(eval_cmp(env->pnc, tv, tv_const) <= 0) {
375
			return NULL;
376
		}
Christoph Mallon's avatar
Christoph Mallon committed
377
378
379

		DB((
			dbg, LEVEL_1,
380
381
			"> Found condition evaluation candidate %+F->%+F\n",
			env->true_block, block
Christoph Mallon's avatar
Christoph Mallon committed
382
383
		));

384
385
		// adjust true_block to point directly towards our jump
		add_pred(env->true_block, jump);
386

387
		split_critical_edge(env->true_block, 0);
388

389
390
		// we need a bigger visited nr when going back
		env->visited_nr++;
391

392
393
		return block;
	}
394

395
396
	if(is_Phi(value)) {
		int i, arity;
Christoph Mallon's avatar
Christoph Mallon committed
397

398
		/* the phi has to be in the same block as the jump */
399
		if(get_nodes_block(value) != block) {
400
			return NULL;
401
		}
402

403
404
405
406
		arity = get_irn_arity(value);
		for(i = 0; i < arity; ++i) {
			ir_node *copy_block;
			ir_node *phi_pred = get_Phi_pred(value, i);
407
			ir_node *cfgpred  = get_Block_cfgpred(block, i);
408

409
			copy_block = find_const(env, cfgpred, phi_pred);
410
			if(copy_block == NULL)
411
412
				continue;

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

416
417
			if(copy_block == get_nodes_block(cfgpred)) {
				env->cnst_pred = block;
418
				env->cnst_pos  = i;
419
			}
420

421
			/* return now as we can't process more possibilities in 1 run */
422
			return copy_block;
423
		}
Christoph Mallon's avatar
Christoph Mallon committed
424
	}
425

426
	return NULL;
Christoph Mallon's avatar
Christoph Mallon committed
427
428
}

429
430
static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
                               ir_node *value)
431
{
432
433
434
435
	ir_node *block = get_nodes_block(jump);

	if(irn_visited(value)) {
		return NULL;
436
	}
437
438
439
	mark_irn_visited(value);

	if(is_Const(value)) {
440
		tarval *tv = get_Const_tarval(value);
441
442
443
444
445
446
447
448
449
450
451
452
453
454

		if(tv != env->tv)
			return NULL;

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

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

		split_critical_edge(env->true_block, 0);
455

456
457
		// we need a bigger visited nr when going back
		env->visited_nr++;
458

459
		return block;
460
	}
461
462
	if(is_Phi(value)) {
		int i, arity;
463

464
465
466
		// the phi has to be in the same block as the jump
		if(get_nodes_block(value) != block)
			return NULL;
467

468
469
470
471
472
		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);
473

474
475
476
477
478
479
480
481
482
483
484
485
486
487
			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;
			}

			// return now as we can't process more possibilities in 1 run
			return copy_block;
Christoph Mallon's avatar
Christoph Mallon committed
488
		}
489
490
491
492
493
494
495
496
	}
	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;
497

498
499
500
		left  = get_Cmp_left(cmp);
		right = get_Cmp_right(cmp);
		pnc   = get_Proj_proj(value);
501

502
503
504
505
506
507
		/* 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;
508

509
510
			pnc        = get_inversed_pnc(pnc);
		}
511

512
		if(!is_Const(right))
513
			return 0;
514

515
516
517
		if(get_nodes_block(left) != block) {
			return 0;
		}
518

519
520
521
		/* negate condition when we're looking for the false block */
		if(env->tv == get_tarval_b_false()) {
			pnc = get_negated_pnc(pnc, get_irn_mode(right));
522
		}
523

524
525
526
527
528
		// (recursively) look if a pred of a phi is a constant
		env->pnc  = pnc;
		env->cnst = right;

		return find_const(env, jump, left);
529
	}
530

531
532
	return NULL;
}
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548

/**
 * 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)
{
549
	condeval_env_t env;
550
	int *changed = data;
551
	ir_node *selector;
552
553
	ir_node *projx;
	ir_node *cond;
554
	ir_node *copy_block;
555
	int      selector_evaluated;
556
557
558
	const ir_edge_t *edge, *next;
	ir_node* bad;
	size_t   cnst_pos;
559
560
561
562
563
564
565
566
567
568
569
570
571

	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;

572
573
574
	selector = get_Cond_selector(cond);
	// TODO handle switch Conds
	if (get_irn_mode(selector) != mode_b)
575
		return;
576

577
578
579
580
581
582
583
584
585
586
587
588
589
	/* handle cases that can be immediately evalutated */
	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);

				selector_evaluated = eval_cmp(pnc, tv_left, tv_right);
590
591
				if(selector_evaluated < 0)
					return;
592
593
594
595
596
597
598
599
600
601
602
603
604
			}
		}
	} else if(is_Const(selector)) {
		tarval *tv = get_Const_tarval(selector);
		if(tv == get_tarval_b_true()) {
			selector_evaluated = 1;
		} else {
			assert(tv == get_tarval_b_false());
			selector_evaluated = 0;
		}
	}

	env.cnst_pred = NULL;
605
606
	if (get_Proj_proj(projx) == pn_Cond_false) {
		env.tv = get_tarval_b_false();
607
608
		if(selector_evaluated >= 0)
			selector_evaluated = !selector_evaluated;
609
610
611
612
	} else {
		env.tv = get_tarval_b_true();
	}

613
614
615
616
617
618
619
620
621
622
623
624
625
	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;
	}

626
627
628
629
630
631
632
	// (recursively) look if a pred of a phi is a constant
	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)
633
634
		return;

635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
	/* we have to remove the edge towards the pred as the pred now
	 * jumps into the true_block. We also have to shorten phis
	 * in our block because of this */
	bad      = new_Bad();
	cnst_pos = env.cnst_pos;

	/* shorten phis */
	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;
653
654
655
656
}

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

659
660
661
662
	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
663
	remove_critical_cf_edges(irg);
664
	normalize_proj_nodes(irg);
665

Michael Beck's avatar
Michael Beck committed
666
	edges_assure(irg);
667
	set_using_irn_link(irg);
668
	set_using_irn_visited(irg);
669

Michael Beck's avatar
Michael Beck committed
670
	changed = 0;
671
	do {
Michael Beck's avatar
Michael Beck committed
672
673
674
675
676
677
678
		rerun = 0;
		irg_block_walk_graph(irg, cond_eval, NULL, &rerun);
		changed |= rerun;
	} while (rerun);

	if (changed) {
		/* control flow changed, some blocks may become dead */
679
		set_irg_outs_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
680
681
682
683
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
684

685
	clear_using_irn_visited(irg);
686
	clear_using_irn_link(irg);
687
}