condeval.c 15.6 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
332
333
334
335
336
337
338
339
340
341
342
343
		blocks[0] = block;
		vals[0] = node;
		blocks[1] = copy_block;
		vals[1] = get_irn_link(node);
		construct_ssa(blocks, vals, 2);
	}
}

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)
		return 0;
	if((cmp_result & pnc) != cmp_result)
		return 0;

	return 1;
}

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

356
		if(!eval_cmp(env->pnc, tv, tv_const)) {
357
			return NULL;
358
		}
Christoph Mallon's avatar
Christoph Mallon committed
359
360
361

		DB((
			dbg, LEVEL_1,
362
363
			"> Found condition evaluation candidate %+F->%+F\n",
			env->true_block, block
Christoph Mallon's avatar
Christoph Mallon committed
364
365
		));

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

369
		split_critical_edge(env->true_block, 0);
370

371
372
		// we need a bigger visited nr when going back
		env->visited_nr++;
373

374
375
		return block;
	}
376

377
378
	if(is_Phi(value)) {
		int i, arity;
Christoph Mallon's avatar
Christoph Mallon committed
379

380
		/* the phi has to be in the same block as the jump */
381
		if(get_nodes_block(value) != block) {
382
			return NULL;
383
		}
384

385
386
387
388
		arity = get_irn_arity(value);
		for(i = 0; i < arity; ++i) {
			ir_node *copy_block;
			ir_node *phi_pred = get_Phi_pred(value, i);
389
			ir_node *cfgpred  = get_Block_cfgpred(block, i);
390

391
			copy_block = find_const(env, cfgpred, phi_pred);
392
			if(copy_block == NULL)
393
394
				continue;

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

398
399
			if(copy_block == get_nodes_block(cfgpred)) {
				env->cnst_pred = block;
400
				env->cnst_pos  = i;
401
			}
402

403
			/* return now as we can't process more possibilities in 1 run */
404
			return copy_block;
405
		}
Christoph Mallon's avatar
Christoph Mallon committed
406
	}
407

408
	return NULL;
Christoph Mallon's avatar
Christoph Mallon committed
409
410
}

411
412
static ir_node *find_candidate(condeval_env_t *env, ir_node *jump,
                               ir_node *value)
413
{
414
415
416
417
	ir_node *block = get_nodes_block(jump);

	if(irn_visited(value)) {
		return NULL;
418
	}
419
420
421
	mark_irn_visited(value);

	if(is_Const(value)) {
422
		tarval *tv = get_Const_tarval(value);
423
424
425
426
427
428
429
430
431
432
433
434
435
436

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

438
439
		// we need a bigger visited nr when going back
		env->visited_nr++;
440

441
		return block;
442
	}
443
444
	if(is_Phi(value)) {
		int i, arity;
445

446
447
448
		// the phi has to be in the same block as the jump
		if(get_nodes_block(value) != block)
			return NULL;
449

450
451
452
453
454
		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);
455

456
457
458
459
460
461
462
463
464
465
466
467
468
469
			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
470
		}
471
472
473
474
475
476
477
478
	}
	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;
479

480
481
482
		left  = get_Cmp_left(cmp);
		right = get_Cmp_right(cmp);
		pnc   = get_Proj_proj(value);
483

484
485
486
487
488
489
		/* 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;
490

491
492
			pnc        = get_inversed_pnc(pnc);
		}
493

494
		if(!is_Const(right))
495
			return 0;
496

497
498
499
		if(get_nodes_block(left) != block) {
			return 0;
		}
500

501
502
503
		/* 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));
504
		}
505

506
507
508
509
510
		// (recursively) look if a pred of a phi is a constant
		env->pnc  = pnc;
		env->cnst = right;

		return find_const(env, jump, left);
511
	}
512

513
514
	return NULL;
}
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530

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

	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;

554
555
556
	selector = get_Cond_selector(cond);
	// TODO handle switch Conds
	if (get_irn_mode(selector) != mode_b)
557
		return;
558

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

593
594
595
596
597
598
599
600
601
602
603
604
605
	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;
	}

606
607
608
609
610
611
612
	// (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)
613
614
		return;

615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
	/* 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;
633
634
635
636
}

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

639
640
641
642
	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
643
	remove_critical_cf_edges(irg);
644
	normalize_proj_nodes(irg);
645

Michael Beck's avatar
Michael Beck committed
646
	edges_assure(irg);
647
648
649
	set_using_irn_link(irg);
	set_using_visited(irg);

Michael Beck's avatar
Michael Beck committed
650
	changed = 0;
651
	do {
Michael Beck's avatar
Michael Beck committed
652
653
654
655
656
657
658
		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 */
659
		set_irg_outs_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
660
661
662
663
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
664
665
666

	clear_using_visited(irg);
	clear_using_irn_link(irg);
667
}