condeval.c 15.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
		ir_mode *mode = get_irn_mode(node);
260
261

		/* ignore control flow */
262
		if (mode == mode_X || is_Cond(node))
263
			continue;
264
#ifdef AVOID_PHIB
265
266
267
		/* 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 */
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
		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;
		}
294
#endif
Christoph Mallon's avatar
Christoph Mallon committed
295

Matthias Braun's avatar
Matthias Braun committed
296
		copy = copy_and_fix_node(env, block, copy_block, j, node);
297
298
299
300
301
302
303
304
305
306

		/* 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
307

308
309
310
311
312
	/* 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);
313
		ir_mode *mode = get_irn_mode(node);
314

315
		if (mode == mode_X || is_Cond(node))
316
			continue;
317
#ifdef AVOID_PHIB
318
		if (mode == mode_b)
319
			continue;
320
#endif
321

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

324
325
326
327
328
329
330
331
		blocks[0] = block;
		vals[0] = node;
		blocks[1] = copy_block;
		vals[1] = get_irn_link(node);
		construct_ssa(blocks, vals, 2);
	}
}

332
333
334
335
/**
 * returns wether the cmp evaluates to true or false, or can't be evaluated!
 * 1: true, 0: false, -1: can't evaluate
 */
336
337
338
339
340
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)
341
		return -1;
342
343
344
345
346
347
	if((cmp_result & pnc) != cmp_result)
		return 0;

	return 1;
}

348
349
static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value)
{
350
351
352
353
354
355
356
357
	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);
358
		tarval *tv       = get_Const_tarval(value);
359

360
		if(eval_cmp(env->pnc, tv, tv_const) <= 0) {
361
			return NULL;
362
		}
Christoph Mallon's avatar
Christoph Mallon committed
363
364
365

		DB((
			dbg, LEVEL_1,
366
367
			"> Found condition evaluation candidate %+F->%+F\n",
			env->true_block, block
Christoph Mallon's avatar
Christoph Mallon committed
368
369
		));

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

373
		split_critical_edge(env->true_block, 0);
374

375
376
		// we need a bigger visited nr when going back
		env->visited_nr++;
377

378
379
		return block;
	}
380

381
382
	if(is_Phi(value)) {
		int i, arity;
Christoph Mallon's avatar
Christoph Mallon committed
383

384
		/* the phi has to be in the same block as the jump */
385
		if(get_nodes_block(value) != block) {
386
			return NULL;
387
		}
388

389
390
391
392
		arity = get_irn_arity(value);
		for(i = 0; i < arity; ++i) {
			ir_node *copy_block;
			ir_node *phi_pred = get_Phi_pred(value, i);
393
			ir_node *cfgpred  = get_Block_cfgpred(block, i);
394

395
			copy_block = find_const(env, cfgpred, phi_pred);
396
			if(copy_block == NULL)
397
398
				continue;

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

402
403
			if(copy_block == get_nodes_block(cfgpred)) {
				env->cnst_pred = block;
404
				env->cnst_pos  = i;
405
			}
406

407
			/* return now as we can't process more possibilities in 1 run */
408
			return copy_block;
409
		}
Christoph Mallon's avatar
Christoph Mallon committed
410
	}
411

412
	return NULL;
Christoph Mallon's avatar
Christoph Mallon committed
413
414
}

415
416
static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
                               ir_node *value)
417
{
418
419
420
421
	ir_node *block = get_nodes_block(jump);

	if(irn_visited(value)) {
		return NULL;
422
	}
423
424
425
	mark_irn_visited(value);

	if(is_Const(value)) {
426
		tarval *tv = get_Const_tarval(value);
427
428
429
430
431
432
433
434
435
436
437
438
439
440

		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);
441

442
443
		// we need a bigger visited nr when going back
		env->visited_nr++;
444

445
		return block;
446
	}
447
448
	if(is_Phi(value)) {
		int i, arity;
449

450
451
452
		// the phi has to be in the same block as the jump
		if(get_nodes_block(value) != block)
			return NULL;
453

454
455
456
457
458
		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);
459

460
461
462
463
464
465
466
467
468
469
470
471
472
473
			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
474
		}
475
476
477
478
479
480
481
482
	}
	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;
483

484
485
486
		left  = get_Cmp_left(cmp);
		right = get_Cmp_right(cmp);
		pnc   = get_Proj_proj(value);
487

488
489
490
491
492
493
		/* 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;
494

495
496
			pnc        = get_inversed_pnc(pnc);
		}
497

498
		if(!is_Const(right))
499
			return 0;
500

501
502
503
		if(get_nodes_block(left) != block) {
			return 0;
		}
504

505
506
507
		/* 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));
508
		}
509

510
511
512
513
514
		// (recursively) look if a pred of a phi is a constant
		env->pnc  = pnc;
		env->cnst = right;

		return find_const(env, jump, left);
515
	}
516

517
518
	return NULL;
}
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534

/**
 * 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)
{
535
	condeval_env_t env;
536
	int *changed = data;
537
	ir_node *selector;
538
539
	ir_node *projx;
	ir_node *cond;
540
	ir_node *copy_block;
541
	int      selector_evaluated;
542
543
544
	const ir_edge_t *edge, *next;
	ir_node* bad;
	size_t   cnst_pos;
545
546
547
548
549
550
551
552
553
554
555
556
557

	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;

558
559
560
	selector = get_Cond_selector(cond);
	// TODO handle switch Conds
	if (get_irn_mode(selector) != mode_b)
561
		return;
562

563
564
565
566
567
568
569
570
571
572
573
574
575
	/* 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);
576
577
				if(selector_evaluated < 0)
					return;
578
579
580
581
582
583
584
585
586
587
588
589
590
			}
		}
	} 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;
591
592
	if (get_Proj_proj(projx) == pn_Cond_false) {
		env.tv = get_tarval_b_false();
593
594
		if(selector_evaluated >= 0)
			selector_evaluated = !selector_evaluated;
595
596
597
598
	} else {
		env.tv = get_tarval_b_true();
	}

599
600
601
602
603
604
605
606
607
608
609
610
611
	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;
	}

612
613
614
615
616
617
618
	// (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)
619
620
		return;

621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
	/* 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;
639
640
641
642
}

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

645
646
647
648
	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
649
	remove_critical_cf_edges(irg);
650
	normalize_proj_nodes(irg);
651

Michael Beck's avatar
Michael Beck committed
652
	edges_assure(irg);
653
654
655
	set_using_irn_link(irg);
	set_using_visited(irg);

Michael Beck's avatar
Michael Beck committed
656
	changed = 0;
657
	do {
Michael Beck's avatar
Michael Beck committed
658
659
660
661
662
663
664
		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 */
665
		set_irg_outs_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
666
667
668
669
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
670
671
672

	clear_using_visited(irg);
	clear_using_irn_link(irg);
673
}