cfopt.c 17.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2014 Karlsruhe Institute of Technology
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
/**
 * @file
 * @brief   Control flow optimizations.
9
 * @author  Goetz Lindenmaier, Michael Beck, Sebastian Hack, Matthias Braun
10
 *
11
12
 * Removes Bad control flow predecessors, merges blocks with jumps and
 * transforms pointless conditional jumps into undonciditonal ones.
Michael Beck's avatar
Michael Beck committed
13
 */
14
15
#include "iroptimize.h"

Michael Beck's avatar
Michael Beck committed
16
#include <assert.h>
17
#include <stdbool.h>
Michael Beck's avatar
Michael Beck committed
18

Matthias Braun's avatar
Matthias Braun committed
19
20
21
22
23
#include "irgmod.h"
#include "irgraph_t.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "irverify.h"
24
#include "panic.h"
25
#include "util.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "xmalloc.h"
Michael Beck's avatar
Michael Beck committed
27

28
29
30
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

/** Set or reset the removable property of a block. */
31
static void set_Block_removable(ir_node *block, bool removable)
32
{
33
	set_Block_mark(block, removable);
Michael Beck's avatar
Michael Beck committed
34
35
}

36
/** Check if a block has the removable property set. */
Matthias Braun's avatar
Matthias Braun committed
37
static bool is_Block_removable(const ir_node *block)
38
{
39
40
	return get_Block_mark(block);
}
41

unknown's avatar
unknown committed
42
43
/** Walker: clear link fields and mark all blocks as removable. */
static void clear_link_and_mark_blocks_removable(ir_node *node, void *ctx)
44
{
Matthias Braun's avatar
Matthias Braun committed
45
	(void)ctx;
Matthias Braun's avatar
Matthias Braun committed
46
	if (is_Block(node)) {
47
		set_Block_removable(node, true);
Matthias Braun's avatar
Matthias Braun committed
48
		set_Block_phis(node, NULL);
49
50
	} else if (is_Switch(node)) {
		set_irn_link(node, INT_TO_PTR(0));
Matthias Braun's avatar
Matthias Braun committed
51
52
53
	} else if (is_Phi(node)) {
		set_Phi_next(node, NULL);
	}
54
55
}

Michael Beck's avatar
Michael Beck committed
56
57
/**
 * Collects all Phi nodes in link list of Block.
58
 * Marks all blocks "non_removable" if they contain a node other
59
 * than Jmp (and Proj).
60
 * Links all Proj nodes to their predecessors.
61
 * Collects all switch-Conds in a list.
Michael Beck's avatar
Michael Beck committed
62
 */
63
64
static void collect_nodes(ir_node *n, void *ctx)
{
Matthias Braun's avatar
Matthias Braun committed
65
	(void)ctx;
66
67
	if (is_Phi(n)) {
		ir_node *block = get_nodes_block(n);
Matthias Braun's avatar
Matthias Braun committed
68
		add_Block_phi(block, n);
69
70
71
		return;
	}
	if (is_Block(n)) {
72
73
74
		/* do not merge blocks with Jump labels for now (we cannot currently
		 * have multiple labels on a block) */
		if (get_Block_entity(n) != NULL)
75
			set_Block_removable(n, false);
76
		return;
77
	}
78
79
80
81
82
83
84
85
	/* these nodes are fine and still allow us to potentially remove the
	 * block (Switch will be decided based on its ProjX nodes) */
	if (is_Bad(n) || is_Jmp(n) || is_Switch(n))
		return;
	if (is_Proj(n)) {
		ir_node *pred = get_Proj_pred(n);
		if (is_Switch(pred)) {
			/* Switch with just default Proj is fine too */
86
			if (get_Proj_num(n) == pn_Switch_default)
87
88
89
90
91
92
93
94
				return;
			/* mark switch as having a non-default Proj */
			set_irn_link(pred, INT_TO_PTR(1));
		}
	}
	/* Any other node leads to the block not being removable. */
	ir_node *block = get_nodes_block(n);
	set_Block_removable(block, false);
Michael Beck's avatar
Michael Beck committed
95
96
}

97
/**
98
99
100
101
 * Before setting new block predecessors check if there are pairs of
 * predecessors from the same Cond node. If there are and all Phi inputs
 * are equivalent, then the Cond has no noticable effect and can be replaced
 * with a simple Jmp.
102
 */
103
104
static unsigned optimize_pointless_forks(ir_node *block, unsigned n_cfgpreds,
                                         ir_node **cfgpreds)
105
{
106
107
108
109
110
111
112
113
114
115
116
	ir_node **new_cfgpreds = NULL;
	if (cfgpreds == NULL) {
		cfgpreds     = get_Block_cfgpred_arr(block);
		new_cfgpreds = NULL;
	} else {
		new_cfgpreds = cfgpreds;
	}

	unsigned new_n_cfgpreds = n_cfgpreds;
	for (unsigned i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred0 = cfgpreds[i];
117
		if (new_cfgpreds != NULL && new_cfgpreds[i] == NULL)
118
			continue;
119
120
121
122
		if (!is_Proj(pred0))
			continue;
		ir_node *cfop = get_Proj_pred(pred0);
		if (!is_Cond(cfop) && !is_Switch(cfop))
123
124
125
126
			continue;

		for (unsigned j = i+1; j < n_cfgpreds; ++j) {
			ir_node *pred1 = cfgpreds[j];
127
128
129
			if (new_cfgpreds != NULL && new_cfgpreds[j] == NULL)
				continue;
			if (!is_Proj(pred1))
130
				continue;
131
			if (get_Proj_pred(pred1) != cfop)
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
				continue;
			/* Both variants jump into the same block, check if all
			 * Phi nodes have the same inputs */
			bool phis_ok = true;
			for (ir_node *phi = get_Block_phis(block); phi != NULL;
			     phi = get_Phi_next(phi)) {
				ir_node *phi_pred0 = get_Phi_pred(phi, i);
				ir_node *phi_pred1 = get_Phi_pred(phi, j);
				if (phi_pred0 != phi_pred1) {
					phis_ok = false;
					break;
				}
			}
			if (!phis_ok)
				continue;

			if (new_cfgpreds == NULL) {
				new_cfgpreds = XMALLOCN(ir_node*, n_cfgpreds);
Christoph Mallon's avatar
Christoph Mallon committed
150
				MEMCPY(new_cfgpreds, cfgpreds, n_cfgpreds);
151
			}
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
			if (is_Cond(cfop)) {
				/* replace Cond with Jmp */
				ir_node *predb1 = get_nodes_block(pred1);
				ir_node *jmp    = new_r_Jmp(predb1);

				new_cfgpreds[i] = jmp;
				new_cfgpreds[j] = NULL;
				--new_n_cfgpreds;
				DB((dbg, LEVEL_1, "Pointless fork %+F to %+F => replace %+F with %+F\n",
					predb1, block, cfop, jmp));
				break;
			} else {
				/* merge Switch table->Proj mapping entries */
				assert(is_Switch(cfop));

167
168
				unsigned pn0 = get_Proj_num(pred0);
				unsigned pn1 = get_Proj_num(pred1);
169
170
171
				/* we merge into pn0, make sure we always merge into the default
				 * case and switch if necessary */
				if (pn1 == pn_Switch_default) {
172
					unsigned t = pn0;
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
					pn0 = pn1;
					pn1 = t;
					ir_node *tp = pred0;
					pred0 = pred1;
					pred1 = tp;
					new_cfgpreds[i] = pred0;
				}
				/* remove 2nd ProjX */
				new_cfgpreds[j] = NULL;
				--new_n_cfgpreds;

				ir_switch_table *table = get_Switch_table(cfop);
				for (size_t i = 0, n = ir_switch_table_get_n_entries(table);
				     i < n; ++i) {
					if (ir_switch_table_get_pn(table, i) == pn1) {
						ir_tarval *min = ir_switch_table_get_min(table, i);
						ir_tarval *max = ir_switch_table_get_max(table, i);
						ir_switch_table_set(table, i, min, max, pn0);
					}
				}
				DB((dbg, LEVEL_1,
194
				    "Merge switch %+F table entry for %+F, %+F (pn %u into %u)\n",
195
196
				    cfop, pred1, pred0, pn1, pn0));
			}
197
198
199
200
201
202
203
204
205
206
207
208
209
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
		}
	}

	if (new_n_cfgpreds != n_cfgpreds) {
		ir_node **in = XMALLOCN(ir_node*, new_n_cfgpreds);
		for (ir_node *phi = get_Block_phis(block); phi != NULL;
		     phi = get_Phi_next(phi)) {
			unsigned new_n_phi_preds = 0;
			for (unsigned i = 0; i < n_cfgpreds; ++i) {
				if (new_cfgpreds[i] == NULL)
					continue;
				ir_node *pred = get_Phi_pred(phi, i);
				in[new_n_phi_preds++] = pred;
			}
			assert(new_n_phi_preds == new_n_cfgpreds);
			set_irn_in(phi, new_n_phi_preds, in);
		}
		unsigned n = 0;
		for (unsigned i = 0; i < n_cfgpreds; ++i) {
			ir_node *pred = new_cfgpreds[i];
			if (pred == NULL)
				continue;
			new_cfgpreds[n++] = pred;
		}
		assert(n == new_n_cfgpreds);
	}
	if (new_cfgpreds != cfgpreds && new_cfgpreds != NULL)
		set_irn_in(block, new_n_cfgpreds, new_cfgpreds);
	return new_n_cfgpreds;
}

static void exchange_phi(ir_node *old, ir_node *new)
{
	if (get_Phi_loop(old)) {
		remove_keep_alive(old);
		set_Phi_loop(old, false);
	}
	exchange(old, new);
}

237
238
239
240
241
242
243
244
245
246
247
248
249
#ifndef NDEBUG
static bool is_default_switch(const ir_node *node)
{
	ir_switch_table *table = get_Switch_table(node);
	for (size_t i = 0, n_entries = ir_switch_table_get_n_entries(table);
	     i < n_entries; ++i) {
		if (ir_switch_table_get_pn(table, i) != pn_Switch_default)
			return false;
	}
	return true;
}
#endif

250
251
/** Merge the single predecessor of @p block at position @p pred_pos.
 * The predecessor has to end with a Jmp for this to be legal. */
252
static bool try_merge_blocks(ir_node *block, unsigned pred_pos)
253
{
254
255
256
257
258
259
260
261
262
263
264
265
266
	if (get_Block_entity(block) != NULL)
		return false;
	ir_node *pred = get_Block_cfgpred(block, pred_pos);
	if (is_Proj(pred)) {
		ir_node *cfop = get_Proj_pred(pred);
		/* is it a switch with just a default Proj? */
		if (!is_Switch(cfop) || get_irn_link(cfop) != INT_TO_PTR(0))
			return false;
		assert(is_default_switch(cfop));
	} else if (!is_Jmp(pred)) {
		return false;
	}

267
268
269
270
271
272
273
274
275
276
277
278
279
280
	/* We can simply remove the Phi nodes and replace them by their single
	 * real input. */
	for (ir_node *phi = get_Block_phis(block), *next_phi; phi != NULL;
	     phi = next_phi) {
		next_phi = get_Phi_next(phi);
		ir_node *val = get_Phi_pred(phi, pred_pos);
		exchange_phi(phi, val);
	}
	ir_node *pred_block = get_Block_cfgpred_block(block, pred_pos);
	DB((dbg, LEVEL_1, "Replace block %+F with %+F\n", block, pred_block));
	if (!is_Block_removable(block))
		set_Block_removable(pred_block, false);
	assert(get_Block_entity(block) == NULL);
	exchange(block, pred_block);
281
	return true;
282
283
}

284
/**
285
 * Merge empty predecessor blocks with block and remove Bad block inputs.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
286
287
 *
 * For each predecessor p of a Block b there are three cases:
288
289
290
291
292
 *  - 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
293
 *
294
 * The most complicated case we handle looks like this:
Michael Beck's avatar
Michael Beck committed
295
 * @verbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
296
 *    then_b     else_b                              then_b  else_b
297
298
299
 *       \      /                                      \      /
 *        \    /                                        |    /
 *        pred_b                                        |   /
Michael Beck's avatar
BugFix:    
Michael Beck committed
300
 *         |   ____                                     |  /  ____
301
 *         |  |    |                                    |  | |    |
Götz Lindenmaier's avatar
Götz Lindenmaier committed
302
 *         |  |    |       === optimized to ===>        \  | |    |
303
304
305
306
 *        loop_b   |                                     loop_b   |
 *         |  |    |                                      |  |    |
 *         |  |____|                                      |  |____|
 *         |                                              |
Michael Beck's avatar
Michael Beck committed
307
 * @endverbatim
Götz Lindenmaier's avatar
Götz Lindenmaier committed
308
 *
309
310
311
312
313
314
 * We have to adapt the Phi nodes in the loop_b and pred_b blocks. Note that
 * for the additional new inputs of the Phi nodes in pred_b we use the Phi node
 * itself (self-loop). This is because pred_b either does not dominate loop_b
 * and the Phi node isn't used except for Phis inside loop_b which are changed
 * anyway. The only case where pred_b dominated loop_b is in case of a loop
 * header then using self-loops for the additional Phi inputs is correct.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
315
 */
316
static void merge_empty_predecessors(ir_node *block, unsigned new_n_cfgpreds)
317
{
318
319
	unsigned  n_cfgpreds = get_Block_n_cfgpreds(block);
	ir_node **in         = XMALLOCN(ir_node*, new_n_cfgpreds);
320

321
322
	/* Fix the Phi nodes of the current block */
	for (ir_node *phi = get_Block_phis(block), *next; phi != NULL; phi = next) {
Matthias Braun's avatar
Matthias Braun committed
323
		next = get_Phi_next(phi);
324
325

		/* Find the new predecessors for the Phi */
326
327
328
329
		unsigned new_n_phi_preds = 0;
		for (unsigned i = 0; i < n_cfgpreds; ++i) {
			ir_node *pred = get_Block_cfgpred(block, i);
			if (is_Bad(pred))
Matthias Braun's avatar
Matthias Braun committed
330
331
				continue;

332
333
334
335
336
337
			/* case1: keep the predecessor */
			ir_node *predb = get_nodes_block(pred);
			if (predb == block || !is_Block_removable(predb)) {
				in[new_n_phi_preds++] = get_Phi_pred(phi, i);
				continue;
			}
338

339
340
341
342
343
344
345
			/* case2: merge with empty predecessor block */
			ir_node *phi_pred = get_Phi_pred(phi, i);
			for (unsigned j = 0, n_pred_cfgpreds = get_Block_n_cfgpreds(predb);
			     j < n_pred_cfgpreds; ++j) {
				ir_node *pred_pred = get_Block_cfgpred(predb, j);
				if (is_Bad(pred_pred))
					continue;
346

347
348
349
350
				ir_node *new_val = phi_pred;
				if (get_nodes_block(phi_pred) == predb) {
					assert(is_Phi(phi_pred));
					new_val = get_Phi_pred(phi_pred, j);
351
				}
352
				in[new_n_phi_preds++] = new_val;
353
354
			}
		}
355
		assert(new_n_phi_preds == new_n_cfgpreds);
356
357

		/* Fix the node */
358
359
		if (new_n_phi_preds == 1) {
			exchange_phi(phi, in[0]);
Matthias Braun's avatar
Matthias Braun committed
360
		} else {
361
			set_irn_in(phi, new_n_phi_preds, in);
Matthias Braun's avatar
Matthias Braun committed
362
		}
363
	}
364
365
366
367
368
369
370
371
	/* all phis have been removed if we only have 1 pred => clear phi list */
	if (new_n_cfgpreds == 1)
		set_Block_phis(block, NULL);

	/* Fix Phi nodes of predecessor blocks which we merge. This is necessary
	 * when we merge between loop backedge and single loop entry. */
	for (unsigned i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred = get_Block_cfgpred(block, i);
372
		if (is_Bad(pred))
373
			continue;
374
375
376
		ir_node *predb = get_nodes_block(pred);
		if (predb == block || !is_Block_removable(predb))
			continue;
377

378
379
380
381
		/* Adapt Phis of predecessor block */
		for (ir_node *phi = get_Block_phis(predb), *next_phi; phi != NULL;
			 phi = next_phi) {
			next_phi = get_Phi_next(phi);
382

383
384
385
386
387
388
389
390
391
392
			unsigned new_n_phi_preds = 0;
			for (unsigned j = 0; j < n_cfgpreds; ++j) {
				ir_node *pred2 = get_Block_cfgpred(block, j);
				if (is_Bad(pred2))
					continue;
				ir_node *predb2 = get_nodes_block(pred2);
				if (predb2 == block || !is_Block_removable(predb2)) {
					in[new_n_phi_preds++] = phi;
					continue;
				}
393

394
395
396
397
398
399
400
401
402
403
404
				for (unsigned k = 0,
				     n_predb2_cfgpreds = get_Block_n_cfgpreds(predb2);
				     k < n_predb2_cfgpreds; ++k) {
				    ir_node *predpred = get_Block_cfgpred(predb2, k);
				    if (is_Bad(predpred))
						continue;
					ir_node *new_phi_pred;
					if (j == i) {
						new_phi_pred = get_Phi_pred(phi, k);
					} else {
						new_phi_pred = phi;
405
					}
406
407
408
409
					in[new_n_phi_preds++] = new_phi_pred;
				}
			}
			assert(new_n_phi_preds == new_n_cfgpreds);
410

411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
			/* kill Phi if only 1 input left else update preds and move */
			if (new_n_phi_preds == 1) {
				exchange_phi(phi, in[0]);
			} else {
				set_irn_in(phi, new_n_phi_preds, in);
				/* move Phi from predecessor into block and update Phi list */
				set_nodes_block(phi, block);
				set_Phi_next(phi, get_Block_phis(block));
				set_Block_phis(block, phi);

				/* We have two possibilties here:
				 *  1) predb does not dominate block -> the Phi is unused
				 *     -> it doesn't matter what we do
				 *  2) predb dominates block -> we merge into a loop which must
				 *     already contain another PhiM[Loop] so no need to create
				 *     a 2nd one.
				 */
				if (get_Phi_loop(phi)) {
					remove_keep_alive(phi);
					set_Phi_loop(phi, false);
Michael Beck's avatar
Michael Beck committed
431
				}
432
433
			}
		}
434
435
436
		/* all phis are removed if we only have 1 pred => clear phi list */
		if (new_n_cfgpreds == 1)
			set_Block_phis(block, NULL);
437
438
	}

439
440
441
442
443
444
445
	/* Calculate new block inputs */
	unsigned n = 0;
	for (unsigned i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred = get_Block_cfgpred(block, i);
		if (is_Bad(pred))
			continue;
		ir_node *predb = get_nodes_block(pred);
446

447
448
449
		/* case1: keep predecessor */
		if (predb == block || !is_Block_removable(predb)) {
			in[n++] = pred;
450
			continue;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
451
		}
452
453
454
455
456
457
458
459
		DB((dbg, LEVEL_1, "Merge block %+F into %+F\n", predb, block));
		/* case2: merge predecessor */
		for (unsigned j = 0, n_pred_cfgpreds = get_Block_n_cfgpreds(predb);
			 j < n_pred_cfgpreds; ++j) {
			ir_node *predpred = get_Block_cfgpred(predb, j);
			if (is_Bad(predpred))
				continue;
			in[n++] = predpred;
460
		}
461
462
		/* Merge blocks to preserve keep alive edges. */
		exchange(predb, block);
463
	}
464
	assert(n == new_n_cfgpreds);
465

466
	n = optimize_pointless_forks(block, n, in);
467

468
469
	DB((dbg, LEVEL_1, "Set new inputs for %+F\n", block));
	set_irn_in(block, n, in);
470
	free(in);
Michael Beck's avatar
Michael Beck committed
471
472
}

Andreas Zwinkau's avatar
Andreas Zwinkau committed
473
/**
474
 * Optimize control flow leading into a basic block.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
475
 */
476
static bool optimize_block(ir_node *block, bool *changed)
Andreas Zwinkau's avatar
Andreas Zwinkau committed
477
{
478
	if (irn_visited_else_mark(block))
Matthias Braun's avatar
Matthias Braun committed
479
		return false;
480

481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
again:;
	/* Count the number of predecessor if this block is merged with pred blocks
	   that are empty. */
	unsigned n_cfgpreds      = get_Block_n_cfgpreds(block);
	unsigned real_preds      = 0;
	/** number of inputs when removing Bads and merging empty predecessors */
	unsigned new_n_cfgpreds  = 0;
	unsigned single_pred_pos = (unsigned)-1;
	bool     can_opt         = false;
	for (unsigned i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred = get_Block_cfgpred(block, i);
		if (is_Bad(pred)) {
			can_opt = true;
			continue;
		}
unknown's avatar
unknown committed
496

497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
		/* make sure predecessor is optimized */
		ir_node *predb = get_nodes_block(pred);
		bool bail_out = optimize_block(predb, changed);
		/* bail out if recursion changed our current block (may happen in
		 * endless loops only reachable by keep-alive edges) */
		if (bail_out || is_Id(block) || is_Id(predb))
			return false;

		++real_preds;
		single_pred_pos = i;
		if (predb != block && is_Block_removable(predb)) {
			can_opt = true;
			for (int j = 0, n_pred_cfgpreds = get_Block_n_cfgpreds(predb);
			     j < n_pred_cfgpreds; ++j) {
			    ir_node *predpred = get_Block_cfgpred(predb, j);
			    if (is_Bad(predpred))
					continue;
				++new_n_cfgpreds;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
515
			}
516
517
		} else {
			++new_n_cfgpreds;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
518
		}
Matthias Braun's avatar
Matthias Braun committed
519
520
	}

521
522
	/* If we only have a single predecessor which jumps into this block,
	 * then we can simply merge the blocks even if they are not empty. */
523
524
525
	if (real_preds == 1 && try_merge_blocks(block, single_pred_pos)) {
		*changed = true;
		return true;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
526
527
	}

528
529
530
531
532
533
534
	if (!can_opt) {
		/* attempt conditional->unconditional jump optimization */
		unsigned new_n_cfgpreds
			= optimize_pointless_forks(block, n_cfgpreds, NULL);
		if (new_n_cfgpreds != n_cfgpreds) {
			*changed = true;
			goto again;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
535
		}
536
		return false;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
537
538
	}

539
540
541
	merge_empty_predecessors(block, new_n_cfgpreds);
	*changed = true;
	return false;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
542
543
}

544
void optimize_cf(ir_graph *irg)
545
{
546
547
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
	                         | IR_GRAPH_PROPERTY_ONE_RETURN);
548
549
550
	/* we have some hacky is_Id() checks here so exchange must not use Deleted
	 * nodes because out edges are active. */
	edges_deactivate(irg);
551
552
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST
	                        | IR_RESOURCE_IRN_LINK);
unknown's avatar
unknown committed
553

554
555
	FIRM_DBG_REGISTER(dbg, "firm.opt.controlflow");
	DB((dbg, LEVEL_1, "===> Performing control flow opt on %+F\n", irg));
556

557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
	ir_node *end            = get_irg_end(irg);
	ir_node *end_block      = get_irg_end_block(irg);
	bool     global_changed = false;
	bool     changed;
	do {
		/* Analysis: Create basic block phi lists and marks blocks which only
		 * contain Jmp and Phi nodes. */
		irg_walk_graph(irg, clear_link_and_mark_blocks_removable, collect_nodes,
		               NULL);

		/* Transformation. Calls recursive opt function starting from end block
		 * and blocks which are kept alive. */
		changed = false;
		ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
		inc_irg_visited(irg);
		optimize_block(end_block, &changed);
		foreach_irn_in(end, i, kept) {
			if (is_Block(kept))
				optimize_block(kept, &changed);
		}
		ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
		global_changed |= changed;
	} while(changed);
580

581
	remove_End_Bads_and_doublets(end);
Matthias Braun's avatar
Matthias Braun committed
582

583
584
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST
	                     | IR_RESOURCE_IRN_LINK);
585
586
	confirm_irg_properties(irg, global_changed ? IR_GRAPH_PROPERTIES_NONE
	                                           : IR_GRAPH_PROPERTIES_ALL);
Michael Beck's avatar
Michael Beck committed
587
}