cfopt.c 25.2 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"
Andreas Zwinkau's avatar
Andreas Zwinkau committed
59
#include "irphase_t.h"
Michael Beck's avatar
Michael Beck committed
60

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

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

unknown's avatar
unknown committed
69
/** set or reset the removable property of a block. */
70
static void set_Block_removable(ir_node *block, bool removable)
71
{
72
	set_Block_mark(block, removable);
Michael Beck's avatar
Michael Beck committed
73
74
}

unknown's avatar
unknown committed
75
/** check if a block has the removable property set. */
76
static bool is_Block_removable(ir_node *block)
77
{
78
79
	return get_Block_mark(block);
}
80

unknown's avatar
unknown committed
81
/** checks if a given Cond node is a switch Cond. */
82
83
84
85
86
static bool is_switch_Cond(ir_node *cond) {
	ir_node *sel = get_Cond_selector(cond);
	return get_irn_mode(sel) != mode_b;
}

unknown's avatar
unknown committed
87
88
/** Walker: clear link fields and mark all blocks as removable. */
static void clear_link_and_mark_blocks_removable(ir_node *node, void *ctx)
89
90
91
{
	(void) ctx;
	set_irn_link(node, NULL);
92
93
	if (is_Block(node))
		set_Block_removable(node, true);
94
95
}

Michael Beck's avatar
Michael Beck committed
96
97
/**
 * Collects all Phi nodes in link list of Block.
98
 * Marks all blocks "non_removable" if they contain a node other
99
 * than Jmp (and Proj).
100
 * Links all Proj nodes to their predecessors.
101
 * Collects all switch-Conds in a list.
Michael Beck's avatar
Michael Beck committed
102
 */
103
104
static void collect_nodes(ir_node *n, void *ctx)
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
105
	ir_node ***switch_conds = (ir_node***)ctx;
106
107
108
109
110
111
112

	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)) {
unknown's avatar
unknown committed
113
114
		if (has_Block_entity(n)) {
			/* block with a jump label attached cannot be removed. */
115
			set_Block_removable(n, false);
unknown's avatar
unknown committed
116
		}
117
118
119
120
121
122
123
124
125
126
		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);
127
128
		} else if (is_Cond(n) && is_switch_Cond(n)) {
			/* found a switch-Cond, collect */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
129
			ARR_APP1(ir_node*, *switch_conds, n);
130
131
		}
	}
Michael Beck's avatar
Michael Beck committed
132
133
}

unknown's avatar
unknown committed
134
/** Returns true if pred is predecessor of block b. */
135
static bool is_pred_of(ir_node *pred, ir_node *b)
136
{
137
	int i;
138

139
	for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
140
		ir_node *b_pred = get_Block_cfgpred_block(b, i);
141
		if (b_pred == pred)
142
			return true;
143
	}
144
	return false;
Michael Beck's avatar
Michael Beck committed
145
146
}

Michael Beck's avatar
Michael Beck committed
147
/** Test whether we can optimize away pred block pos of b.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
148
149
150
151
152
153
154
155
156
 *
 *  @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
157
 *  @verbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
158
159
160
161
162
 *                 if-block
 *                  /   \
 *              then-b  else-b
 *                  \   /
 *                    b
Michael Beck's avatar
Michael Beck committed
163
 *  @endverbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
164
 *
Michael Beck's avatar
Michael Beck committed
165
166
167
168
169
 *  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
170
 *
Michael Beck's avatar
Michael Beck committed
171
172
 *  To perform the test for pos, we must regard predecessors before pos
 *  as already removed.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
173
 **/
174
static unsigned test_whether_dispensable(ir_node *b, int pos)
175
{
176
177
	ir_node *pred  = get_Block_cfgpred(b, pos);
	ir_node *predb = get_nodes_block(pred);
178

Andreas Zwinkau's avatar
Andreas Zwinkau committed
179
	if (is_Bad(pred) || !is_Block_removable(predb))
180
		return 1;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
181

182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
	/* 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))
209
210
						goto non_dispensable;
				}
211
212
			} else if (is_pred_of(other_predb, predb)) {
				goto non_dispensable;
213
			}
214
215
216
217
218
		}
		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;
219
220
		}
	}
221
222
223
224
	/* 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
225
	return get_irn_arity(predb);
Michael Beck's avatar
BugFix:    
Michael Beck committed
226
227

non_dispensable:
228
	set_Block_removable(predb, false);
229
	return 1;
Michael Beck's avatar
Michael Beck committed
230
231
}

232
/**
Andreas Zwinkau's avatar
Andreas Zwinkau committed
233
234
 * This method removes empty blocks.  A block is empty if it only contains Phi
 * and Jmp nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
235
236
237
238
239
240
241
 *
 * 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:
242
243
244
245
246
 *  - 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
247
248
249
250
 *
 * 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:
251
252
253
254
255
256
257
 *  -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
258
259
 *
 * Further there is a special case for self referencing blocks:
Michael Beck's avatar
Michael Beck committed
260
 * @verbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
261
262
 *
 *    then_b     else_b                              then_b  else_b
263
264
265
 *       \      /                                      \      /
 *        \    /                                        |    /
 *        pred_b                                        |   /
Michael Beck's avatar
BugFix:    
Michael Beck committed
266
 *         |   ____                                     |  /  ____
267
 *         |  |    |                                    |  | |    |
Götz Lindenmaier's avatar
Götz Lindenmaier committed
268
 *         |  |    |       === optimized to ===>        \  | |    |
269
270
271
272
 *        loop_b   |                                     loop_b   |
 *         |  |    |                                      |  |    |
 *         |  |____|                                      |  |____|
 *         |                                              |
Michael Beck's avatar
Michael Beck committed
273
 * @endverbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
274
275
276
277
278
 *
 * 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.
 */
279
280
static void optimize_blocks(ir_node *b, void *ctx)
{
281
	int i, j, k, n, max_preds, n_preds, p_preds = -1;
282
	ir_node *pred, *phi, *next;
283
	ir_node **in;
284
	merge_env *env = (merge_env*)ctx;
285
286
287
288
289
290
291

	/* 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);
	}
292
	in = XMALLOCN(ir_node*, max_preds);
293
294

	/*- Fix the Phi nodes of the current block -*/
295
	for (phi = (ir_node*)get_irn_link(b); phi != NULL; phi = (ir_node*)next) {
296
		assert(is_Phi(phi));
297
		next = (ir_node*)get_irn_link(phi);
298
299
300
301

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

305
			if (is_Bad(pred)) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
306
				/* case Phi 1: maintain Bads, as somebody else is responsible to remove them */
307
				in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
308
			} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
309
310
311
312
				/* 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++) {
313
					ir_node *pred_pred = get_Block_cfgpred(pred, j);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
314
315

					if (is_Bad(pred_pred)) {
316
						in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
317
						continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
318
					}
319

320
321
322
323
324
325
326
327
					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;
328
329
330
331
332
333
334
					}
				}
			} else {
				/* case Phi 3: */
				in[p_preds++] = get_Phi_pred(phi, i);
			}
		}
335
		assert(p_preds == max_preds);
336
337
338
339
340
341

		/* Fix the node */
		if (p_preds == 1)
			exchange(phi, in[0]);
		else
			set_irn_in(phi, p_preds, in);
342
		env->changed = true;
343
344
345
	}

	/*- This happens only if merge between loop backedge and single loop entry.
346
347
	    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 ... -*/
348
	for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
349
350
351
		ir_node *pred  = get_Block_cfgpred(b, k);
		ir_node *predb = get_nodes_block(pred);
		if (is_Bad(pred))
352
353
			continue;

354
		if (is_Block_removable(predb) && !Block_block_visited(predb)) {
Michael Beck's avatar
Michael Beck committed
355
356
			ir_node *next_phi;

357
			/* we found a predecessor block at position k that will be removed */
358
			for (phi = (ir_node*)get_irn_link(predb); phi; phi = next_phi) {
Michael Beck's avatar
Michael Beck committed
359
				int q_preds = 0;
360
				next_phi = (ir_node*)get_irn_link(phi);
Michael Beck's avatar
Michael Beck committed
361
362
363

				assert(is_Phi(phi));

Michael Beck's avatar
BugFix:    
Michael Beck committed
364
365
				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
366
367
368
					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
369
				} else {
Michael Beck's avatar
BugFix:    
Michael Beck committed
370
371
					/* 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
372
373
374
					set_nodes_block(phi, b);
					set_irn_link(phi, get_irn_link(b));
					set_irn_link(b, phi);
375
					env->phis_moved = true;
Michael Beck's avatar
Michael Beck committed
376
377
378
379
380

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

381
						if (is_Bad(pred)) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
382
383
384
							ir_graph *irg  = get_irn_irg(b);
							ir_mode  *mode = get_irn_mode(phi);
							in[q_preds++] = new_r_Bad(irg, mode);
385
						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
Michael Beck's avatar
Michael Beck committed
386
387
							/* It's an empty block and not yet visited. */
							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
388
								if (! is_Bad(get_Block_cfgpred(pred, j))) {
Michael Beck's avatar
Michael Beck committed
389
									in[q_preds++] = phi;
390
391
392
393
394
								} else {
									ir_graph *irg  = get_irn_irg(b);
									ir_mode  *mode = get_irn_mode(phi);
									in[q_preds++] = new_r_Bad(irg, mode);
								}
Michael Beck's avatar
Michael Beck committed
395
396
397
							}
						} else {
							in[q_preds++] = phi;
398
399
400
						}
					}

Michael Beck's avatar
Michael Beck committed
401
402
403
					/* 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++) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
404
						in[q_preds++] = get_Phi_pred(phi, i);
Michael Beck's avatar
Michael Beck committed
405
					}
406

Michael Beck's avatar
Michael Beck committed
407
408
					/* and now all the rest */
					for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
409
						pred = get_Block_cfgpred_block(b, i);
Michael Beck's avatar
Michael Beck committed
410

411
						if (is_Bad(pred)) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
412
413
414
							ir_graph *irg  = get_irn_irg(b);
							ir_mode  *mode = get_irn_mode(phi);
							in[q_preds++] = new_r_Bad(irg, mode);
415
						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
Michael Beck's avatar
Michael Beck committed
416
417
							/* It's an empty block and not yet visited. */
							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
418
								if (! is_Bad(get_Block_cfgpred(pred, j))) {
Michael Beck's avatar
Michael Beck committed
419
									in[q_preds++] = phi;
420
421
422
423
424
								} else {
									ir_graph *irg  = get_irn_irg(b);
									ir_mode  *mode = get_irn_mode(phi);
									in[q_preds++] = new_r_Bad(irg, mode);
								}
Michael Beck's avatar
Michael Beck committed
425
426
427
							}
						} else {
							in[q_preds++] = phi;
428
429
430
						}
					}

Michael Beck's avatar
Michael Beck committed
431
432
433
434
435
					/* Fix the node */
					if (q_preds == 1)
						exchange(phi, in[0]);
					else
						set_irn_in(phi, q_preds, in);
436
					env->changed = true;
437

Michael Beck's avatar
Michael Beck committed
438
439
440
					assert(q_preds <= max_preds);
					// assert(p_preds == q_preds && "Wrong Phi Fix");
				}
441
442
443
444
445
446
447
			}
		}
	}

	/*- Fix the block -*/
	n_preds = 0;
	for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
448
449
		ir_node *pred  = get_Block_cfgpred(b, i);
		ir_node *predb = get_nodes_block(pred);
450
		ir_graph *irg  = get_irn_irg(pred);
451

Andreas Zwinkau's avatar
Andreas Zwinkau committed
452
		/* case 1: Bad predecessor */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
453
		if (is_Bad(pred)) {
454
			in[n_preds++] = new_r_Bad(irg, mode_X);
455
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
456
		}
457
		if (is_Block_removable(predb) && !Block_block_visited(predb)) {
458
			/* case 2: It's an empty block and not yet visited. */
459
460
461
			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
462
				if (is_Bad(predpred)) {
463
					in[n_preds++] = new_r_Bad(irg, mode_X);
464
					continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
465
466
				}

467
				in[n_preds++] = predpred;
468
			}
469
			/* Remove block+jump as it might be kept alive. */
Matthias Braun's avatar
Matthias Braun committed
470
471
			exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
			exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
472
473
		} else {
			/* case 3: */
474
			in[n_preds++] = pred;
475
476
		}
	}
477
	assert(n_preds == max_preds);
478
479

	set_irn_in(b, n_preds, in);
480
	env->changed = true;
481

482
483
	/* see if phi-fix was correct */
	assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds));
484
	xfree(in);
Michael Beck's avatar
Michael Beck committed
485
486
}

487
/**
488
 * Optimize table-switch Conds.
489
490
 *
 * @param cond the switch-Cond
491
 * @return true if the switch-Cond was optimized
492
 */
493
static bool handle_switch_cond(ir_node *cond)
494
{
495
	ir_node *sel   = get_Cond_selector(cond);
496
497
	ir_node *proj1 = (ir_node*)get_irn_link(cond);
	ir_node *proj2 = (ir_node*)get_irn_link(proj1);
498
	ir_node *blk   = get_nodes_block(cond);
499

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

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

		if (tv != tarval_bad) {
			/* we have a constant switch */
518
519
520
			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
521
			ir_node  *bad     = new_r_Bad(irg, mode_X);
522
523
524
525

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

Andreas Zwinkau's avatar
Andreas Zwinkau committed
558
/**
unknown's avatar
unknown committed
559
560
 * Optimize boolean Conds, where true and false jump to the same block into a Jmp
 * Block must contain no Phi nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
561
 *
Andreas Zwinkau's avatar
Andreas Zwinkau committed
562
563
564
565
566
 *        Cond
 *       /    \
 *  projA      projB   =>   Jmp     Bad
 *       \    /                \   /
 *       block                 block
Götz Lindenmaier's avatar
Götz Lindenmaier committed
567
 */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
static bool optimize_pred_cond(ir_node *block, int i, int j)
{
	ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
	assert(i != j);

	projA = get_Block_cfgpred(block, i);
	if (!is_Proj(projA)) return false;
	projB = get_Block_cfgpred(block, j);
	if (!is_Proj(projB)) return false;
	cond  = get_Proj_pred(projA);
	if (!is_Cond(cond))  return false;

	if (cond != get_Proj_pred(projB)) return false;
	if (is_switch_Cond(cond)) return false;

	/* cond should actually be a Jmp */
	pred_block = get_nodes_block(cond);
	jmp = new_r_Jmp(pred_block);
	bad = new_r_Bad(get_irn_irg(block), mode_X);

	assert(projA != projB);
	exchange(projA, jmp);
	exchange(projB, bad);
	return true;
}

unknown's avatar
unknown committed
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
typedef enum block_flags_t {
	BF_HAS_OPERATIONS         = 1 << 0,
	BF_HAS_PHIS               = 1 << 1,
	BF_IS_UNKNOWN_JUMP_TARGET = 1 << 2,
} block_flags_t;

static bool get_phase_flag(ir_phase *block_info, ir_node *block, int flag) {
	return ((int)phase_get_irn_data(block_info, block)) & flag;
}
static void set_phase_flag(ir_phase *block_info, ir_node *block, int flag) {
	int data = (int)phase_get_irn_data(block_info, block);
	data |= flag;
	phase_set_irn_data(block_info, block, (void*)data);
}

static bool has_operations(ir_phase *block_info, ir_node *block) {
	return get_phase_flag(block_info, block, BF_HAS_OPERATIONS);
}
static void set_has_operations(ir_phase *block_info, ir_node *block) {
	set_phase_flag(block_info, block, BF_HAS_OPERATIONS);
}

static bool has_phis(ir_phase *block_info, ir_node *block) {
	return get_phase_flag(block_info, block, BF_HAS_PHIS);
}
static void set_has_phis(ir_phase *block_info, ir_node *block) {
	set_phase_flag(block_info, block, BF_HAS_PHIS);
}

static bool is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
	return get_phase_flag(block_info, block, BF_IS_UNKNOWN_JUMP_TARGET);
}
static void set_is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
	set_phase_flag(block_info, block, BF_IS_UNKNOWN_JUMP_TARGET);
}

/**
 * Walker: fill block info information.
 */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
static void compute_block_info(ir_node *n, void *x)
{
	ir_phase *block_info = (ir_phase *)x;

	if (is_Block(n)) {
		int i, max = get_Block_n_cfgpreds(n);
		for (i=0; i<max; i++) {
			ir_node *pred = get_Block_cfgpred(n,i);
			if (is_unknown_jump(pred)) {
				set_is_unknown_jump_target(block_info, n);
			}
		}
	} else if (is_Phi(n)) {
		ir_node *block = get_nodes_block(n);
		set_has_phis(block_info, block);
	} else if (is_Jmp(n) || is_Cond(n) || is_Cmp(n) || is_Proj(n)) {
		/* ignore */
	} else {
		ir_node *block = get_nodes_block(n);
		set_has_operations(block_info, block);
	}
}

typedef struct skip_env {
	bool changed;
	ir_phase *phase;
} skip_env;

unknown's avatar
unknown committed
661
662
663
664
665
666
/**
 * Post-Block-walker: Optimize useless if's (boolean Cond nodes
 * with same true/false target)
 * away.
 */
static void optimize_ifs(ir_node *block, void *x)
Andreas Zwinkau's avatar
Andreas Zwinkau committed
667
668
669
{
	skip_env *env = (skip_env*)x;
	int i, j;
unknown's avatar
unknown committed
670
	int n_preds = get_Block_n_cfgpreds(block);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
671

unknown's avatar
unknown committed
672
673
	if (has_phis(env->phase, block))
		return;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
674
675

	/* optimize Cond predecessors (might produce Bad predecessors) */
unknown's avatar
unknown committed
676
677
678
	for (i = 0; i < n_preds; ++i) {
		for (j = i+1; j < n_preds; ++j) {
			optimize_pred_cond(block, i, j);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
679
680
681
682
		}
	}
}

unknown's avatar
unknown committed
683
/**
Andreas Zwinkau's avatar
Andreas Zwinkau committed
684
 * Pre-Block walker: remove empty blocks that are
unknown's avatar
unknown committed
685
686
687
 * predecessors of the current block.
 */
static void remove_empty_blocks(ir_node *block, void *x)
Andreas Zwinkau's avatar
Andreas Zwinkau committed
688
689
690
{
	skip_env *env = (skip_env*)x;
	int i;
unknown's avatar
unknown committed
691
	int n_preds = get_Block_n_cfgpreds(block);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
692
693
694
695

	for (i = 0; i < n_preds; ++i) {
		ir_node *jmp, *jmp_block, *pred, *pred_block;

unknown's avatar
unknown committed
696
697
698
		jmp = get_Block_cfgpred(block, i);
		if (!is_Jmp(jmp))
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
699
		jmp_block = get_nodes_block(jmp);
unknown's avatar
unknown committed
700
701
702
703
		if (is_unknown_jump_target(env->phase, jmp_block))
			continue;
		if (has_operations(env->phase,jmp_block))
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
704
705
		/* jmp_block is an empty block! */

unknown's avatar
unknown committed
706
707
		if (get_Block_n_cfgpreds(jmp_block) != 1)
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
708
709
710
711
712
713
714
715
716
717
718
		pred = get_Block_cfgpred(jmp_block, 0);
		exchange(jmp, pred);
		env->changed = true;

		/* cleanup: jmp_block might have a Keep edge! */
		pred_block = get_nodes_block(pred);
		exchange(jmp_block, pred_block);
	}
}

/*
unknown's avatar
unknown committed
719
720
 * Some cfg optimizations, which do not touch Phi nodes
 */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
721
722
723
724
725
726
static void cfgopt_ignoring_phis(ir_graph *irg) {
	ir_phase *block_info = new_phase(irg, NULL);
	skip_env env = { false, block_info };

	irg_walk_graph(irg, compute_block_info, NULL, block_info);

unknown's avatar
unknown committed
727
	for (;;) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
728
729
		env.changed = false;

unknown's avatar
unknown committed
730
731
		/* useless if optimization: will not touch empty blocks */
		irg_block_walk_graph(irg, NULL, optimize_ifs, &env);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
732
733

		/* Remove empty blocks */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
734
		irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
735
736
737
738
739
740
741
742
743
744
745
746
747
		if (env.changed) {
			set_irg_doms_inconsistent(irg);
			/* Removing blocks might enable more Cond optimizations */
			continue;
		} else {
			break;
		}
	}

	phase_free(block_info);
}

/* Optimizations of the control flow that also require changes of Phi nodes.  */
748
749
void optimize_cf(ir_graph *irg)
{
750
	int i, j, n;
751
	ir_node **in = NULL;
752
753
	ir_node *end = get_irg_end(irg);
	ir_node *new_end;
Michael Beck's avatar
Michael Beck committed
754
	merge_env env;
755

unknown's avatar
unknown committed
756
757
758
	env.changed    = false;
	env.phis_moved = false;

759
760
761
762
763
764
	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");

765
766
	/* FIXME: control flow opt destroys block edges. So edges are deactivated
	 * here. Fix the edges! */
767
768
	edges_deactivate(irg);

Andreas Zwinkau's avatar
Andreas Zwinkau committed
769
770
	cfgopt_ignoring_phis(irg);

771
	/* we use the mark flag to mark removable blocks */
772
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
773

Andreas Zwinkau's avatar
Andreas Zwinkau committed
774
	/* The switch Cond optimization might expose unreachable code, so we loop */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
775
776
	for (;;) {
		int length;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
777
		ir_node **switch_conds = NULL;
unknown's avatar
unknown committed
778
		bool changed = false;
779

Andreas Zwinkau's avatar
Andreas Zwinkau committed
780
		assure_doms(irg);
781

Andreas Zwinkau's avatar
Andreas Zwinkau committed
782
783
784
785
786
787
		/*
		 * This 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.
		 */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
788
		switch_conds = NEW_ARR_F(ir_node*, 0);
unknown's avatar
unknown committed
789
		irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, &switch_conds);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
790
791

		/* handle all collected switch-Conds */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
792
		length = ARR_LEN(switch_conds);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
793
		for (i = 0; i < length; ++i) {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
794
			ir_node *cond = switch_conds[i];
unknown's avatar
unknown committed
795
			changed |= handle_switch_cond(cond);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
796
		}
Andreas Zwinkau's avatar
Andreas Zwinkau committed
797
		DEL_ARR_F(switch_conds);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
798

unknown's avatar
unknown committed
799
800
		if (!changed)
			break;
Matthias Braun's avatar
Matthias Braun committed
801

unknown's avatar
unknown committed
802
		set_irg_outs_inconsistent(irg);
803
804
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
805
		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
806
807
	}

Andreas Zwinkau's avatar
Andreas Zwinkau committed
808
809
810
811
812
	/* assert due to collect_nodes:
	 * 1. removable blocks are now marked as such
	 * 2. phi lists are up to date
	 */

Andreas Zwinkau's avatar
Andreas Zwinkau committed
813
814
815
816
	/* Optimize the standard code.
	 * It walks only over block nodes and adapts these and the Phi nodes in these
	 * blocks, which it finds in a linked list computed before.
	 * */
817
	assure_doms(irg);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
818
	irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
Michael Beck's avatar
Michael Beck committed
819

820
821
822
823
	new_end = optimize_in_place(end);
	if (new_end != end) {
		set_irg_end(irg, new_end);
		end = new_end;
824
	}
825
826
	remove_End_Bads_and_doublets(end);

827
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
Matthias Braun's avatar
Matthias Braun committed
828

829
830
831
	if (env.phis_moved) {
		/* Bad: when we moved Phi's, we might produce dead Phi nodes
		   that are kept-alive.
unknown's avatar
unknown committed
832
		   Some other phases cannot copy with this, so kill them.
833
834
835
		 */
		n = get_End_n_keepalives(end);
		if (n > 0) {
836
			NEW_ARR_A(ir_node *, in, n);
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
			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);
860
				env.changed = true;
861
862
863
864
			}
		}
	}

Michael Beck's avatar
Michael Beck committed
865
866
	if (env.changed) {
		/* Handle graph state if was changed. */
unknown's avatar
unknown committed
867
		set_irg_outs_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
868
869
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
870
		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
Michael Beck's avatar
Michael Beck committed
871
	}
Michael Beck's avatar
Michael Beck committed
872
}
873
874

/* Creates an ir_graph pass for optimize_cf. */
875
ir_graph_pass_t *optimize_cf_pass(const char *name)
876
{
877
	return def_graph_pass(name ? name : "optimize_cf", optimize_cf);
878
}