cfopt.c 20.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
/**
 * @file
 * @brief   Control flow optimizations.
 * @author  Goetz Lindenmaier, Michael Beck, Sebastian Hack
 * @version $Id$
25
26
27
28
29
 *
 * Removes Bad control flow predecessors and empty blocks.  A block is empty
 * if it contains only a Jmp node. Blocks can only be removed if they are not
 * needed for the semantics of Phi nodes. Further, we NEVER remove labeled
 * blocks (even if we could move the label).
Michael Beck's avatar
Michael Beck committed
30
 */
Matthias Braun's avatar
Matthias Braun committed
31
#include "config.h"
Michael Beck's avatar
Michael Beck committed
32

33
34
#include "iroptimize.h"

Michael Beck's avatar
Michael Beck committed
35
#include <assert.h>
36
#include <stdbool.h>
Michael Beck's avatar
Michael Beck committed
37

Michael Beck's avatar
Michael Beck committed
38
#include "xmalloc.h"
Michael Beck's avatar
Michael Beck committed
39
40
41
42
43
44
45
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irprog_t.h"

#include "ircons.h"
#include "iropt_t.h"
#include "irgwalk.h"
Michael Beck's avatar
Michael Beck committed
46
#include "irgmod.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
47
#include "irdump.h"
48
#include "irverify.h"
Matthias Braun's avatar
Matthias Braun committed
49
#include "iredges.h"
Michael Beck's avatar
Michael Beck committed
50

51
#include "array_t.h"
Michael Beck's avatar
Michael Beck committed
52
53
54
55
56
57

#include "irouts.h"
#include "irbackedge_t.h"

#include "irflag_t.h"
#include "firmstat.h"
58
#include "irpass.h"
Michael Beck's avatar
Michael Beck committed
59

Michael Beck's avatar
Michael Beck committed
60
#include "iropt_dbg.h"
Michael Beck's avatar
Michael Beck committed
61

Michael Beck's avatar
Michael Beck committed
62
/** An environment for merge_blocks and collect nodes. */
63
typedef struct merge_env {
64
65
66
	bool      changed;      /**< Set if the graph was changed. */
	bool      phis_moved;   /**< Set if Phi nodes were moved. */
	ir_node **switch_conds; /**< Helper list for all found Switch Conds. */
Michael Beck's avatar
Michael Beck committed
67
68
} merge_env;

69
static void set_Block_removable(ir_node *block, bool removable)
70
{
71
	set_Block_mark(block, removable);
Michael Beck's avatar
Michael Beck committed
72
73
}

74
static bool is_Block_removable(ir_node *block)
75
{
76
77
	return get_Block_mark(block);
}
78

79
80
81
82
static void clear_link(ir_node *node, void *ctx)
{
	(void) ctx;
	set_irn_link(node, NULL);
83
84
	if (is_Block(node))
		set_Block_removable(node, true);
85
86
}

Michael Beck's avatar
Michael Beck committed
87
88
/**
 * Collects all Phi nodes in link list of Block.
89
 * Marks all blocks "non_removable" if they contain a node other
90
 * than Jmp (and Proj).
91
 * Links all Proj nodes to their predecessors.
92
 * Collects all switch-Conds in a list.
Michael Beck's avatar
Michael Beck committed
93
 */
94
95
static void collect_nodes(ir_node *n, void *ctx)
{
96
97
98
99
100
101
102
103
	merge_env *env = (merge_env*)ctx;

	if (is_Phi(n)) {
		/* Collect Phi nodes to compact ins along with block's ins. */
		ir_node *block = get_nodes_block(n);
		set_irn_link(n, get_irn_link(block));
		set_irn_link(block, n);
	} else if (is_Block(n)) {
104
105
		if (has_Block_entity(n))
			set_Block_removable(n, false);
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
		return;
	} else if (!is_Jmp(n)) {  /* Check for non-empty block. */
		ir_node *block = get_nodes_block(n);
		set_Block_removable(block, false);

		if (is_Proj(n)) {
			/* link Proj nodes */
			ir_node *pred = get_Proj_pred(n);
			set_irn_link(n, get_irn_link(pred));
			set_irn_link(pred, n);
		} else if (is_Cond(n)) {
			ir_node *sel = get_Cond_selector(n);
			if (get_irn_mode(sel) != mode_b) {
				/* found a switch-Cond, collect */
				ARR_APP1(ir_node*, env->switch_conds, n);
121
122
123
			}
		}
	}
Michael Beck's avatar
Michael Beck committed
124
125
126
}

/** Returns true if pred is predecessor of block. */
127
static bool is_pred_of(ir_node *pred, ir_node *b)
128
{
129
	int i;
130

131
	for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
132
		ir_node *b_pred = get_Block_cfgpred_block(b, i);
133
		if (b_pred == pred)
134
			return true;
135
	}
136
	return false;
Michael Beck's avatar
Michael Beck committed
137
138
}

Michael Beck's avatar
Michael Beck committed
139
/** Test whether we can optimize away pred block pos of b.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
140
141
142
143
144
145
146
147
148
 *
 *  @param  b    A block node.
 *  @param  pos  The position of the predecessor block to judge about.
 *
 *  @returns     The number of predecessors
 *
 *  The test is rather tricky.
 *
 *  The situation is something like the following:
Michael Beck's avatar
Michael Beck committed
149
 *  @verbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
150
151
152
153
154
 *                 if-block
 *                  /   \
 *              then-b  else-b
 *                  \   /
 *                    b
Michael Beck's avatar
Michael Beck committed
155
 *  @endverbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
156
 *
Michael Beck's avatar
Michael Beck committed
157
158
159
160
161
 *  b merges the control flow of an if-then-else.  We may not remove
 *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 *  node in b, even if both are empty.  The destruction of this Phi
 *  requires that a copy is added before the merge.  We have to
 *  keep one of the case blocks to place the copies in.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
162
 *
Michael Beck's avatar
Michael Beck committed
163
164
 *  To perform the test for pos, we must regard predecessors before pos
 *  as already removed.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
165
 **/
166
static unsigned test_whether_dispensable(ir_node *b, int pos)
167
{
168
169
	ir_node *pred  = get_Block_cfgpred(b, pos);
	ir_node *predb = get_nodes_block(pred);
170

Andreas Zwinkau's avatar
Andreas Zwinkau committed
171
	if (is_Bad(pred) || !is_Block_removable(predb))
172
		return 1;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
173

174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
	/* can't remove self-loops */
	if (predb == b)
		goto non_dispensable;
	if (is_unknown_jump(pred))
		goto non_dispensable;

	/* Seems to be empty. At least we detected this in collect_nodes. */
	if (get_irn_link(b) != NULL) {
		int n_cfgpreds = get_Block_n_cfgpreds(b);
		int i;
		/* there are Phi nodes */

		/* b's pred blocks and pred's pred blocks must be pairwise disjunct.
		 * Handle all pred blocks with preds < pos as if they were already
		 * removed. */
		for (i = 0; i < pos; i++) {
			ir_node *other_pred  = get_Block_cfgpred(b, i);
			ir_node *other_predb = get_nodes_block(other_pred);
			if (is_Bad(other_pred))
				continue;
			if (is_Block_removable(other_predb)
			    && !Block_block_visited(other_predb)) {
				int j;
				for (j = get_Block_n_cfgpreds(other_predb) - 1; j >= 0; --j) {
					ir_node *other_predpred
						= get_Block_cfgpred_block(other_predb, j);
					if (is_pred_of(other_predpred, predb))
201
202
						goto non_dispensable;
				}
203
204
			} else if (is_pred_of(other_predb, predb)) {
				goto non_dispensable;
205
			}
206
207
208
209
210
		}
		for (i = pos+1; i < n_cfgpreds; i++) {
			ir_node *other_predb = get_Block_cfgpred_block(b, i);
			if (is_pred_of(other_predb, predb))
				goto non_dispensable;
211
212
		}
	}
213
214
215
216
	/* we will not dispense already visited blocks */
	if (Block_block_visited(predb))
		return 1;
	/* if we get here, the block is dispensable, count useful preds */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
217
	return get_irn_arity(predb);
Michael Beck's avatar
BugFix:    
Michael Beck committed
218
219

non_dispensable:
220
	set_Block_removable(predb, false);
221
	return 1;
Michael Beck's avatar
Michael Beck committed
222
223
}

224
/**
Michael Beck's avatar
Michael Beck committed
225
 * This method removed Bad cf predecessors from Blocks and Phis, and removes
Götz Lindenmaier's avatar
Götz Lindenmaier committed
226
227
228
229
230
231
232
233
 * empty blocks.  A block is empty if it only contains Phi and Jmp nodes.
 *
 * We first adapt Phi nodes, then Block nodes, as we need the old ins
 * of the Block to adapt the Phi nodes.  We do this by computing new
 * in arrays, and then replacing the old ones.  So far we compute new in arrays
 * for all nodes, not regarding whether there is a possibility for optimization.
 *
 * For each predecessor p of a Block b there are three cases:
234
235
236
237
238
 *  - The predecessor p is a Bad node: just skip it. The in array of b shrinks
 *    by one.
 *  - The predecessor p is empty. Remove p. All predecessors of p are now
 *    predecessors of b.
 *  - The predecessor p is a block containing useful code. Just keep p as is.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
239
240
241
242
 *
 * For Phi nodes f we have to check the conditions at the Block of f.
 * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 * cases:
243
244
245
246
247
248
249
 *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.
 *       In this case we proceed as for blocks. We remove pred_f.  All
 *       predecessors of pred_f now are predecessors of f.
 *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi
 *       too. We have to replicate f for each predecessor of the removed block.
 *       Or, with other words, the removed predecessor block has exactly one
 *       predecessor.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
250
251
 *
 * Further there is a special case for self referencing blocks:
Michael Beck's avatar
Michael Beck committed
252
 * @verbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
253
254
 *
 *    then_b     else_b                              then_b  else_b
255
256
257
 *       \      /                                      \      /
 *        \    /                                        |    /
 *        pred_b                                        |   /
Michael Beck's avatar
BugFix:    
Michael Beck committed
258
 *         |   ____                                     |  /  ____
259
 *         |  |    |                                    |  | |    |
Götz Lindenmaier's avatar
Götz Lindenmaier committed
260
 *         |  |    |       === optimized to ===>        \  | |    |
261
262
263
264
 *        loop_b   |                                     loop_b   |
 *         |  |    |                                      |  |    |
 *         |  |____|                                      |  |____|
 *         |                                              |
Michael Beck's avatar
Michael Beck committed
265
 * @endverbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
266
267
268
269
270
 *
 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 * backedge.
 */
271
272
static void optimize_blocks(ir_node *b, void *ctx)
{
273
	int i, j, k, n, max_preds, n_preds, p_preds = -1;
274
	ir_node *pred, *phi, *next;
275
	ir_node **in;
276
	merge_env *env = (merge_env*)ctx;
277
278
279
280
281
282
283

	/* Count the number of predecessor if this block is merged with pred blocks
	   that are empty. */
	max_preds = 0;
	for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
		max_preds += test_whether_dispensable(b, i);
	}
284
	in = XMALLOCN(ir_node*, max_preds);
285
286

	/*- Fix the Phi nodes of the current block -*/
287
	for (phi = (ir_node*)get_irn_link(b); phi != NULL; phi = (ir_node*)next) {
288
		assert(is_Phi(phi));
289
		next = (ir_node*)get_irn_link(phi);
290
291
292
293

		/* Find the new predecessors for the Phi */
		p_preds = 0;
		for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
294
			ir_graph *irg = get_irn_irg(b);
295
296
			pred = get_Block_cfgpred_block(b, i);

297
			if (is_Bad(pred)) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
298
				/* case Phi 1: maintain Bads, as somebody else is responsible to remove them */
299
				in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
300
			} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
301
302
303
304
				/* case Phi 2: It's an empty block and not yet visited. */
				ir_node *phi_pred = get_Phi_pred(phi, i);

				for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
305
					ir_node *pred_pred = get_Block_cfgpred(pred, j);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
306
307

					if (is_Bad(pred_pred)) {
308
						in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
309
						continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
310
					}
311

312
313
314
315
316
317
318
319
					if (get_nodes_block(phi_pred) == pred) {
						/* case Phi 2a: */
						assert(is_Phi(phi_pred));  /* Block is empty!! */

						in[p_preds++] = get_Phi_pred(phi_pred, j);
					} else {
						/* case Phi 2b: */
						in[p_preds++] = phi_pred;
320
321
322
323
324
325
326
					}
				}
			} else {
				/* case Phi 3: */
				in[p_preds++] = get_Phi_pred(phi, i);
			}
		}
327
		assert(p_preds == max_preds);
328
329
330
331
332
333

		/* Fix the node */
		if (p_preds == 1)
			exchange(phi, in[0]);
		else
			set_irn_in(phi, p_preds, in);
334
		env->changed = true;
335
336
337
	}

	/*- This happens only if merge between loop backedge and single loop entry.
338
339
	    Moreover, it is only needed if predb is the direct dominator of b,
	    else there can be no uses of the Phi's in predb ... -*/
340
	for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
341
342
343
		ir_node *pred  = get_Block_cfgpred(b, k);
		ir_node *predb = get_nodes_block(pred);
		if (is_Bad(pred))
344
345
			continue;

346
		if (is_Block_removable(predb) && !Block_block_visited(predb)) {
Michael Beck's avatar
Michael Beck committed
347
348
			ir_node *next_phi;

349
			/* we found a predecessor block at position k that will be removed */
350
			for (phi = (ir_node*)get_irn_link(predb); phi; phi = next_phi) {
Michael Beck's avatar
Michael Beck committed
351
				int q_preds = 0;
352
				next_phi = (ir_node*)get_irn_link(phi);
Michael Beck's avatar
Michael Beck committed
353
354
355

				assert(is_Phi(phi));

Michael Beck's avatar
BugFix:    
Michael Beck committed
356
357
				if (get_Block_idom(b) != predb) {
					/* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
Matthias Braun's avatar
Matthias Braun committed
358
359
360
					ir_graph *irg  = get_irn_irg(b);
					ir_mode  *mode = get_irn_mode(phi);
					exchange(phi, new_r_Bad(irg, mode));
Michael Beck's avatar
Michael Beck committed
361
				} else {
Michael Beck's avatar
BugFix:    
Michael Beck committed
362
363
					/* predb is the direct dominator of b. There might be uses of the Phi nodes from
					   predb in further block, so move this phi from the predecessor into the block b */
Michael Beck's avatar
Michael Beck committed
364
365
366
					set_nodes_block(phi, b);
					set_irn_link(phi, get_irn_link(b));
					set_irn_link(b, phi);
367
					env->phis_moved = true;
Michael Beck's avatar
Michael Beck committed
368
369
370
371
372

					/* first, copy all 0..k-1 predecessors */
					for (i = 0; i < k; i++) {
						pred = get_Block_cfgpred_block(b, i);

373
						if (is_Bad(pred)) {
Michael Beck's avatar
Michael Beck committed
374
							/* Do nothing */
375
						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
Michael Beck's avatar
Michael Beck committed
376
377
378
379
380
381
382
							/* It's an empty block and not yet visited. */
							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
								if (! is_Bad(get_Block_cfgpred(pred, j)))
									in[q_preds++] = phi;
							}
						} else {
							in[q_preds++] = phi;
383
384
385
						}
					}

Michael Beck's avatar
Michael Beck committed
386
387
388
389
390
391
					/* now we are at k, copy the phi predecessors */
					pred = get_nodes_block(get_Block_cfgpred(b, k));
					for (i = 0; i < get_Phi_n_preds(phi); i++) {
						if (! is_Bad(get_Block_cfgpred(pred, i)))
							in[q_preds++] = get_Phi_pred(phi, i);
					}
392

Michael Beck's avatar
Michael Beck committed
393
394
					/* and now all the rest */
					for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
395
						pred = get_Block_cfgpred_block(b, i);
Michael Beck's avatar
Michael Beck committed
396

397
						if (is_Bad(pred)) {
Michael Beck's avatar
Michael Beck committed
398
							/* Do nothing */
399
						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
Michael Beck's avatar
Michael Beck committed
400
401
402
403
404
405
406
							/* It's an empty block and not yet visited. */
							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
								if (! is_Bad(get_Block_cfgpred(pred, j)))
									in[q_preds++] = phi;
							}
						} else {
							in[q_preds++] = phi;
407
408
409
						}
					}

Michael Beck's avatar
Michael Beck committed
410
411
412
413
414
					/* Fix the node */
					if (q_preds == 1)
						exchange(phi, in[0]);
					else
						set_irn_in(phi, q_preds, in);
415
					env->changed = true;
416

Michael Beck's avatar
Michael Beck committed
417
418
419
					assert(q_preds <= max_preds);
					// assert(p_preds == q_preds && "Wrong Phi Fix");
				}
420
421
422
423
424
425
426
			}
		}
	}

	/*- Fix the block -*/
	n_preds = 0;
	for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
427
428
		ir_node *pred  = get_Block_cfgpred(b, i);
		ir_node *predb = get_nodes_block(pred);
429
		ir_graph *irg  = get_irn_irg(pred);
430

431
		/* case 1: Do nothing */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
432
		if (is_Bad(pred)) {
433
			in[n_preds++] = new_r_Bad(irg, mode_X);
434
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
435
		}
436
		if (is_Block_removable(predb) && !Block_block_visited(predb)) {
437
			/* case 2: It's an empty block and not yet visited. */
438
439
440
			for (j = 0; j < get_Block_n_cfgpreds(predb); j++) {
				ir_node *predpred = get_Block_cfgpred(predb, j);

Andreas Zwinkau's avatar
Andreas Zwinkau committed
441
				if (is_Bad(predpred)) {
442
					in[n_preds++] = new_r_Bad(irg, mode_X);
443
					continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
444
445
				}

446
				in[n_preds++] = predpred;
447
			}
448
			/* Remove block+jump as it might be kept alive. */
Matthias Braun's avatar
Matthias Braun committed
449
450
			exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
			exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
451
452
		} else {
			/* case 3: */
453
			in[n_preds++] = pred;
454
455
		}
	}
456
	assert(n_preds == max_preds);
457
458

	set_irn_in(b, n_preds, in);
459
	env->changed = true;
460

461
462
	/* see if phi-fix was correct */
	assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds));
463
	xfree(in);
Michael Beck's avatar
Michael Beck committed
464
465
}

466
/**
Michael Beck's avatar
Michael Beck committed
467
 * Block walker: optimize all blocks using the default optimizations.
468
 * This removes Blocks with only a Jmp predecessor.
469
 */
470
471
static void remove_simple_blocks(ir_node *block, void *ctx)
{
472
473
	merge_env *env = (merge_env*)ctx;
	ir_node   *new_blk = equivalent_node(block);
Michael Beck's avatar
Michael Beck committed
474
475

	if (new_blk != block) {
476
		exchange(block, new_blk);
477
		env->changed = true;
Michael Beck's avatar
Michael Beck committed
478
	}
479
480
481
}

/**
482
 * Optimize table-switch Conds.
483
484
 *
 * @param cond the switch-Cond
485
 * @return true if the switch-Cond was optimized
486
 */
487
static bool handle_switch_cond(ir_node *cond)
488
{
489
	ir_node *sel   = get_Cond_selector(cond);
490
491
	ir_node *proj1 = (ir_node*)get_irn_link(cond);
	ir_node *proj2 = (ir_node*)get_irn_link(proj1);
492
	ir_node *blk   = get_nodes_block(cond);
493

494
	/* exactly 1 Proj on the Cond node: must be the defaultProj */
495
	if (proj2 == NULL) {
496
		ir_node *jmp = new_r_Jmp(blk);
497
		assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
498
499
		/* convert it into a Jmp */
		exchange(proj1, jmp);
500
501
502
503
504
505
506
507
		return true;
	}

	/* handle Cond nodes with constant argument. In this case the localopt rules
	 * should have killed all obviously impossible cases.
	 * So the only case left to handle here is 1 defaultProj + 1case
	 * (this one case should be the one taken) */
	if (get_irn_link(proj2) == NULL) {
Matthias Braun's avatar
Matthias Braun committed
508
		ir_tarval *tv = value_of(sel);
509
510
511

		if (tv != tarval_bad) {
			/* we have a constant switch */
512
513
514
			long      num     = get_tarval_long(tv);
			long      def_num = get_Cond_default_proj(cond);
			ir_graph *irg     = get_irn_irg(cond);
Matthias Braun's avatar
Matthias Braun committed
515
			ir_node  *bad     = new_r_Bad(irg, mode_X);
516
517
518
519

			if (def_num == get_Proj_proj(proj1)) {
				/* first one is the defProj */
				if (num == get_Proj_proj(proj2)) {
520
					ir_node *jmp = new_r_Jmp(blk);
521
					exchange(proj2, jmp);
522
523
					exchange(proj1, bad);
					return true;
524
525
526
527
				}
			} else if (def_num == get_Proj_proj(proj2)) {
				/* second one is the defProj */
				if (num == get_Proj_proj(proj1)) {
528
					ir_node *jmp = new_r_Jmp(blk);
529
					exchange(proj1, jmp);
530
531
					exchange(proj2, bad);
					return true;
532
533
534
535
				}
			} else {
				/* neither: strange, Cond was not optimized so far */
				if (num == get_Proj_proj(proj1)) {
536
					ir_node *jmp = new_r_Jmp(blk);
537
					exchange(proj1, jmp);
538
539
					exchange(proj2, bad);
					return true;
540
				} else if (num == get_Proj_proj(proj2)) {
541
					ir_node *jmp = new_r_Jmp(blk);
542
					exchange(proj2, jmp);
543
544
					exchange(proj1, bad);
					return true;
545
546
547
548
				}
			}
		}
	}
549
	return false;
550
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
551

552
/* Optimizations of the control flow that also require changes of Phi nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
553
554
555
556
557
558
559
560
561
 *
 * This optimization performs two passes over the graph.
 *
 * The first pass collects all Phi nodes in a link list in the block
 * nodes.  Further it performs simple control flow optimizations.
 * Finally it marks all blocks that do not contain useful
 * computations, i.e., these blocks might be removed.
 *
 * The second pass performs the optimizations intended by this algorithm.
562
563
 * It walks only over block nodes and adapts these and the Phi nodes in these
 * blocks, which it finds in a linked list computed by the first pass.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
564
 *
565
 * We use the mark flag to mark removable blocks in the first phase.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
566
 */
567
568
void optimize_cf(ir_graph *irg)
{
569
	int i, j, n;
570
	ir_node **in = NULL;
571
572
	ir_node *end = get_irg_end(irg);
	ir_node *new_end;
Michael Beck's avatar
Michael Beck committed
573
	merge_env env;
574
575
576
577
578
579
580

	assert(get_irg_phase_state(irg) != phase_building);

	/* if the graph is not pinned, we cannot determine empty blocks */
	assert(get_irg_pinned(irg) != op_pin_state_floats &&
	       "Control flow optimization need a pinned graph");

581
582
	/* FIXME: control flow opt destroys block edges. So edges are deactivated
	 * here. Fix the edges! */
583
584
	edges_deactivate(irg);

585
	/* we use the mark flag to mark removable blocks */
586
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
587
restart:
588
589
	env.changed    = false;
	env.phis_moved = false;
590

591
	assure_doms(irg);
592

593
594
	env.switch_conds = NEW_ARR_F(ir_node*, 0);
	irg_walk(end, clear_link, collect_nodes, &env);
595

596
597
598
599
600
601
602
	/* handle all collected switch-Conds */
	n = ARR_LEN(env.switch_conds);
	for (i = 0; i < n; ++i) {
		ir_node *cond = env.switch_conds[i];
		env.changed |= handle_switch_cond(cond);
	}
	DEL_ARR_F(env.switch_conds);
Matthias Braun's avatar
Matthias Braun committed
603

604
605
606
607
608
609
	if (env.changed) {
		/* Handle graph state if was changed. */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
610
		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
611
612
613

		/* The Cond optimization might generate unreachable code, so restart if
		   it happens. */
614
		goto restart;
615
616
617
	}

	/* Optimize the standard code. */
618
	assure_doms(irg);
619
	irg_block_walk_graph(irg, optimize_blocks, remove_simple_blocks, &env);
Michael Beck's avatar
Michael Beck committed
620

621
622
623
624
	new_end = optimize_in_place(end);
	if (new_end != end) {
		set_irg_end(irg, new_end);
		end = new_end;
625
	}
626
627
	remove_End_Bads_and_doublets(end);

628
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
Matthias Braun's avatar
Matthias Braun committed
629

630
631
632
633
634
635
636
	if (env.phis_moved) {
		/* Bad: when we moved Phi's, we might produce dead Phi nodes
		   that are kept-alive.
		   Some other phases cannot copy with this, so will them.
		 */
		n = get_End_n_keepalives(end);
		if (n > 0) {
637
			NEW_ARR_A(ir_node *, in, n);
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
			if (env.changed) {
				/* Handle graph state if was changed. */
				set_irg_outs_inconsistent(irg);
			}
			assure_irg_outs(irg);

			for (i = j = 0; i < n; ++i) {
				ir_node *ka = get_End_keepalive(end, i);

				if (is_Phi(ka)) {
					int k;

					for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
						ir_node *user = get_irn_out(ka, k);

						if (user != ka && user != end) {
							/* Is it a real user or just a self loop ? */
							break;
						}
					}
					if (k >= 0)
						in[j++] = ka;
				} else
					in[j++] = ka;
			}
			if (j != n) {
				set_End_keepalives(end, j, in);
665
				env.changed = true;
666
667
668
669
			}
		}
	}

Michael Beck's avatar
Michael Beck committed
670
671
672
673
674
675
	if (env.changed) {
		/* Handle graph state if was changed. */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
676
		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
Michael Beck's avatar
Michael Beck committed
677
	}
Michael Beck's avatar
Michael Beck committed
678
}
679
680

/* Creates an ir_graph pass for optimize_cf. */
681
ir_graph_pass_t *optimize_cf_pass(const char *name)
682
{
683
	return def_graph_pass(name ? name : "optimize_cf", optimize_cf);
684
}