2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Control flow optimizations.
23 * @author Goetz Lindenmaier, Michael Beck, Sebastian Hack
26 * Removes Bad control flow predecessors and empty blocks. A block is empty
27 * if it contains only a Jmp node. Blocks can only be removed if they are not
28 * needed for the semantics of Phi nodes. Further, we NEVER remove labeled
29 * blocks (even if we could move the label).
33 #include "iroptimize.h"
40 #include "irgraph_t.h"
54 #include "irbackedge_t.h"
59 #include "irphase_t.h"
61 #include "iropt_dbg.h"
63 /** An environment for merge_blocks and collect nodes. */
64 typedef struct merge_env {
65 bool changed; /**< Set if the graph was changed. */
66 bool phis_moved; /**< Set if Phi nodes were moved. */
69 /** set or reset the removable property of a block. */
70 static void set_Block_removable(ir_node *block, bool removable)
72 set_Block_mark(block, removable);
75 /** check if a block has the removable property set. */
76 static bool is_Block_removable(ir_node *block)
78 return get_Block_mark(block);
81 /** checks if a given Cond node is a switch Cond. */
82 static bool is_switch_Cond(ir_node *cond)
84 ir_node *sel = get_Cond_selector(cond);
85 return get_irn_mode(sel) != mode_b;
88 /** Walker: clear link fields and mark all blocks as removable. */
89 static void clear_link_and_mark_blocks_removable(ir_node *node, void *ctx)
92 set_irn_link(node, NULL);
94 set_Block_removable(node, true);
98 * Collects all Phi nodes in link list of Block.
99 * Marks all blocks "non_removable" if they contain a node other
100 * than Jmp (and Proj).
101 * Links all Proj nodes to their predecessors.
102 * Collects all switch-Conds in a list.
104 static void collect_nodes(ir_node *n, void *ctx)
106 ir_node ***switch_conds = (ir_node***)ctx;
109 /* Collect Phi nodes to compact ins along with block's ins. */
110 ir_node *block = get_nodes_block(n);
111 set_irn_link(n, get_irn_link(block));
112 set_irn_link(block, n);
113 } else if (is_Block(n)) {
114 if (has_Block_entity(n)) {
115 /* block with a jump label attached cannot be removed. */
116 set_Block_removable(n, false);
118 } else if (is_Bad(n) || is_Jmp(n)) {
122 /* Check for non-empty block. */
123 ir_node *block = get_nodes_block(n);
127 set_Block_removable(block, false);
130 /* link Proj nodes */
131 ir_node *pred = get_Proj_pred(n);
132 set_irn_link(n, get_irn_link(pred));
133 set_irn_link(pred, n);
134 } else if (is_Cond(n) && is_switch_Cond(n)) {
135 /* found a switch-Cond, collect */
136 ARR_APP1(ir_node*, *switch_conds, n);
141 /** Returns true if pred is predecessor of block b. */
142 static bool is_pred_of(ir_node *pred, ir_node *b)
146 for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
147 ir_node *b_pred = get_Block_cfgpred_block(b, i);
154 /** Test whether we can optimize away pred block pos of b.
156 * @param b A block node.
157 * @param pos The position of the predecessor block to judge about.
159 * @returns The number of predecessors
161 * The test is rather tricky.
163 * The situation is something like the following:
172 * b merges the control flow of an if-then-else. We may not remove
173 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
174 * node in b, even if both are empty. The destruction of this Phi
175 * requires that a copy is added before the merge. We have to
176 * keep one of the case blocks to place the copies in.
178 * To perform the test for pos, we must regard predecessors before pos
179 * as already removed.
181 static unsigned test_whether_dispensable(ir_node *b, int pos)
183 ir_node *pred = get_Block_cfgpred(b, pos);
184 ir_node *predb = get_nodes_block(pred);
186 if (is_Bad(pred) || !is_Block_removable(predb))
189 /* can't remove self-loops */
191 goto non_dispensable;
192 if (is_unknown_jump(pred))
193 goto non_dispensable;
195 /* Seems to be empty. At least we detected this in collect_nodes. */
196 if (get_irn_link(b) != NULL) {
197 int n_cfgpreds = get_Block_n_cfgpreds(b);
199 /* there are Phi nodes */
201 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
202 * Handle all pred blocks with preds < pos as if they were already
204 for (i = 0; i < pos; i++) {
205 ir_node *other_pred = get_Block_cfgpred(b, i);
206 ir_node *other_predb = get_nodes_block(other_pred);
207 if (is_Bad(other_pred))
209 if (is_Block_removable(other_predb)
210 && !Block_block_visited(other_predb)) {
212 for (j = get_Block_n_cfgpreds(other_predb) - 1; j >= 0; --j) {
213 ir_node *other_predpred
214 = get_Block_cfgpred_block(other_predb, j);
215 if (is_pred_of(other_predpred, predb))
216 goto non_dispensable;
218 } else if (is_pred_of(other_predb, predb)) {
219 goto non_dispensable;
222 for (i = pos+1; i < n_cfgpreds; i++) {
223 ir_node *other_predb = get_Block_cfgpred_block(b, i);
224 if (is_pred_of(other_predb, predb))
225 goto non_dispensable;
228 /* we will not dispense already visited blocks */
229 if (Block_block_visited(predb))
231 /* if we get here, the block is dispensable, count useful preds */
232 return get_irn_arity(predb);
235 set_Block_removable(predb, false);
240 * This method removes empty blocks. A block is empty if it only contains Phi
243 * We first adapt Phi nodes, then Block nodes, as we need the old ins
244 * of the Block to adapt the Phi nodes. We do this by computing new
245 * in arrays, and then replacing the old ones. So far we compute new in arrays
246 * for all nodes, not regarding whether there is a possibility for optimization.
248 * For each predecessor p of a Block b there are three cases:
249 * - The predecessor p is a Bad node: just skip it. The in array of b shrinks
251 * - The predecessor p is empty. Remove p. All predecessors of p are now
253 * - The predecessor p is a block containing useful code. Just keep p as is.
255 * For Phi nodes f we have to check the conditions at the Block of f.
256 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
258 * -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.
259 * In this case we proceed as for blocks. We remove pred_f. All
260 * predecessors of pred_f now are predecessors of f.
261 * -2b: The old predecessor of f is NOT in the block removed. It might be a Phi
262 * too. We have to replicate f for each predecessor of the removed block.
263 * Or, with other words, the removed predecessor block has exactly one
266 * Further there is a special case for self referencing blocks:
269 * then_b else_b then_b else_b
275 * | | | === optimized to ===> \ | | |
282 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
283 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
286 static void optimize_blocks(ir_node *b, void *ctx)
288 int i, j, k, n, max_preds, n_preds, p_preds = -1;
289 ir_node *pred, *phi, *next;
291 merge_env *env = (merge_env*)ctx;
293 if (get_Block_dom_depth(b) < 0) {
294 /* ignore unreachable blocks */
298 /* Count the number of predecessor if this block is merged with pred blocks
301 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
302 max_preds += test_whether_dispensable(b, i);
304 in = XMALLOCN(ir_node*, max_preds);
306 /*- Fix the Phi nodes of the current block -*/
307 for (phi = (ir_node*)get_irn_link(b); phi != NULL; phi = (ir_node*)next) {
309 next = (ir_node*)get_irn_link(phi);
311 /* Find the new predecessors for the Phi */
313 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
314 ir_graph *irg = get_irn_irg(b);
315 pred = get_Block_cfgpred_block(b, i);
318 /* case Phi 1: maintain Bads, as somebody else is responsible to remove them */
319 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
320 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
321 /* case Phi 2: It's an empty block and not yet visited. */
322 ir_node *phi_pred = get_Phi_pred(phi, i);
324 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
325 ir_node *pred_pred = get_Block_cfgpred(pred, j);
327 if (is_Bad(pred_pred)) {
328 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
332 if (get_nodes_block(phi_pred) == pred) {
334 assert(is_Phi(phi_pred)); /* Block is empty!! */
336 in[p_preds++] = get_Phi_pred(phi_pred, j);
339 in[p_preds++] = phi_pred;
344 in[p_preds++] = get_Phi_pred(phi, i);
347 assert(p_preds == max_preds);
351 exchange(phi, in[0]);
353 set_irn_in(phi, p_preds, in);
357 /*- This happens only if merge between loop backedge and single loop entry.
358 Moreover, it is only needed if predb is the direct dominator of b,
359 else there can be no uses of the Phi's in predb ... -*/
360 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
361 ir_node *pred = get_Block_cfgpred(b, k);
362 ir_node *predb = get_nodes_block(pred);
366 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
369 /* we found a predecessor block at position k that will be removed */
370 for (phi = (ir_node*)get_irn_link(predb); phi; phi = next_phi) {
372 next_phi = (ir_node*)get_irn_link(phi);
376 if (get_Block_idom(b) != predb) {
377 /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
378 ir_graph *irg = get_irn_irg(b);
379 ir_mode *mode = get_irn_mode(phi);
380 exchange(phi, new_r_Bad(irg, mode));
382 /* predb is the direct dominator of b. There might be uses of the Phi nodes from
383 predb in further block, so move this phi from the predecessor into the block b */
384 set_nodes_block(phi, b);
385 set_irn_link(phi, get_irn_link(b));
386 set_irn_link(b, phi);
387 env->phis_moved = true;
389 /* first, copy all 0..k-1 predecessors */
390 for (i = 0; i < k; i++) {
391 pred = get_Block_cfgpred_block(b, i);
394 ir_graph *irg = get_irn_irg(b);
395 ir_mode *mode = get_irn_mode(phi);
396 in[q_preds++] = new_r_Bad(irg, mode);
397 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
398 /* It's an empty block and not yet visited. */
399 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
400 if (! is_Bad(get_Block_cfgpred(pred, j))) {
403 ir_graph *irg = get_irn_irg(b);
404 ir_mode *mode = get_irn_mode(phi);
405 in[q_preds++] = new_r_Bad(irg, mode);
413 /* now we are at k, copy the phi predecessors */
414 pred = get_nodes_block(get_Block_cfgpred(b, k));
415 for (i = 0; i < get_Phi_n_preds(phi); i++) {
416 in[q_preds++] = get_Phi_pred(phi, i);
419 /* and now all the rest */
420 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
421 pred = get_Block_cfgpred_block(b, i);
424 ir_graph *irg = get_irn_irg(b);
425 ir_mode *mode = get_irn_mode(phi);
426 in[q_preds++] = new_r_Bad(irg, mode);
427 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
428 /* It's an empty block and not yet visited. */
429 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
430 if (! is_Bad(get_Block_cfgpred(pred, j))) {
433 ir_graph *irg = get_irn_irg(b);
434 ir_mode *mode = get_irn_mode(phi);
435 in[q_preds++] = new_r_Bad(irg, mode);
445 exchange(phi, in[0]);
447 set_irn_in(phi, q_preds, in);
450 assert(q_preds <= max_preds);
451 // assert(p_preds == q_preds && "Wrong Phi Fix");
457 /*- Fix the block -*/
459 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
460 ir_node *pred = get_Block_cfgpred(b, i);
461 ir_node *predb = get_nodes_block(pred);
462 ir_graph *irg = get_irn_irg(pred);
464 /* case 1: Bad predecessor */
466 in[n_preds++] = new_r_Bad(irg, mode_X);
469 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
470 /* case 2: It's an empty block and not yet visited. */
471 for (j = 0; j < get_Block_n_cfgpreds(predb); j++) {
472 ir_node *predpred = get_Block_cfgpred(predb, j);
474 if (is_Bad(predpred)) {
475 in[n_preds++] = new_r_Bad(irg, mode_X);
479 in[n_preds++] = predpred;
481 /* Remove block+jump as it might be kept alive. */
482 exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
483 exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
486 in[n_preds++] = pred;
489 assert(n_preds == max_preds);
491 set_irn_in(b, n_preds, in);
494 /* see if phi-fix was correct */
495 assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds));
500 * Optimize table-switch Conds.
502 * @param cond the switch-Cond
503 * @return true if the switch-Cond was optimized
505 static bool handle_switch_cond(ir_node *cond)
507 ir_node *sel = get_Cond_selector(cond);
508 ir_node *proj1 = (ir_node*)get_irn_link(cond);
509 ir_node *proj2 = (ir_node*)get_irn_link(proj1);
510 ir_node *blk = get_nodes_block(cond);
512 /* exactly 1 Proj on the Cond node: must be the defaultProj */
514 ir_node *jmp = new_r_Jmp(blk);
515 assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
516 /* convert it into a Jmp */
517 exchange(proj1, jmp);
521 /* handle Cond nodes with constant argument. In this case the localopt rules
522 * should have killed all obviously impossible cases.
523 * So the only case left to handle here is 1 defaultProj + 1 case
524 * (this one case should be the one taken) */
525 if (get_irn_link(proj2) == NULL) {
526 ir_tarval *tv = value_of(sel);
528 if (tv != tarval_bad) {
529 /* we have a constant switch */
530 long num = get_tarval_long(tv);
531 long def_num = get_Cond_default_proj(cond);
532 ir_graph *irg = get_irn_irg(cond);
533 ir_node *bad = new_r_Bad(irg, mode_X);
535 if (def_num == get_Proj_proj(proj1)) {
536 /* first one is the defProj */
537 if (num == get_Proj_proj(proj2)) {
538 ir_node *jmp = new_r_Jmp(blk);
539 exchange(proj2, jmp);
540 exchange(proj1, bad);
543 } else if (def_num == get_Proj_proj(proj2)) {
544 /* second one is the defProj */
545 if (num == get_Proj_proj(proj1)) {
546 ir_node *jmp = new_r_Jmp(blk);
547 exchange(proj1, jmp);
548 exchange(proj2, bad);
552 /* neither: strange, Cond was not optimized so far */
553 if (num == get_Proj_proj(proj1)) {
554 ir_node *jmp = new_r_Jmp(blk);
555 exchange(proj1, jmp);
556 exchange(proj2, bad);
558 } else if (num == get_Proj_proj(proj2)) {
559 ir_node *jmp = new_r_Jmp(blk);
560 exchange(proj2, jmp);
561 exchange(proj1, bad);
571 * Optimize boolean Conds, where true and false jump to the same block into a Jmp
572 * Block must contain no Phi nodes.
576 * projA projB => Jmp Bad
580 static bool optimize_pred_cond(ir_node *block, int i, int j)
582 ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
585 projA = get_Block_cfgpred(block, i);
586 if (!is_Proj(projA)) return false;
587 projB = get_Block_cfgpred(block, j);
588 if (!is_Proj(projB)) return false;
589 cond = get_Proj_pred(projA);
590 if (!is_Cond(cond)) return false;
592 if (cond != get_Proj_pred(projB)) return false;
593 if (is_switch_Cond(cond)) return false;
595 /* cond should actually be a Jmp */
596 pred_block = get_nodes_block(cond);
597 jmp = new_r_Jmp(pred_block);
598 bad = new_r_Bad(get_irn_irg(block), mode_X);
600 assert(projA != projB);
601 exchange(projA, jmp);
602 exchange(projB, bad);
606 typedef enum block_flags_t {
607 BF_HAS_OPERATIONS = 1 << 0,
608 BF_HAS_PHIS = 1 << 1,
609 BF_IS_UNKNOWN_JUMP_TARGET = 1 << 2,
612 static bool get_phase_flag(ir_phase *block_info, ir_node *block, int flag)
614 return PTR_TO_INT(phase_get_irn_data(block_info, block)) & flag;
617 static void set_phase_flag(ir_phase *block_info, ir_node *block,
620 int data = PTR_TO_INT(phase_get_irn_data(block_info, block));
622 phase_set_irn_data(block_info, block, INT_TO_PTR(data));
625 static void clear_phase_flag(ir_phase *block_info, ir_node *block)
627 phase_set_irn_data(block_info, block, NULL);
630 static bool has_operations(ir_phase *block_info, ir_node *block)
632 return get_phase_flag(block_info, block, BF_HAS_OPERATIONS);
635 static void set_has_operations(ir_phase *block_info, ir_node *block)
637 set_phase_flag(block_info, block, BF_HAS_OPERATIONS);
640 static bool has_phis(ir_phase *block_info, ir_node *block)
642 return get_phase_flag(block_info, block, BF_HAS_PHIS);
645 static void set_has_phis(ir_phase *block_info, ir_node *block)
647 set_phase_flag(block_info, block, BF_HAS_PHIS);
650 static bool is_unknown_jump_target(ir_phase *block_info, ir_node *block)
652 return get_phase_flag(block_info, block, BF_IS_UNKNOWN_JUMP_TARGET);
655 static void set_is_unknown_jump_target(ir_phase *block_info, ir_node *block)
657 set_phase_flag(block_info, block, BF_IS_UNKNOWN_JUMP_TARGET);
661 * Pre-Walker: fill block info information.
663 static void compute_block_info(ir_node *n, void *x)
665 ir_phase *block_info = (ir_phase *)x;
668 int i, max = get_Block_n_cfgpreds(n);
669 for (i=0; i<max; i++) {
670 ir_node *pred = get_Block_cfgpred(n,i);
671 if (is_unknown_jump(pred)) {
672 set_is_unknown_jump_target(block_info, n);
675 } else if (is_Phi(n)) {
676 ir_node *block = get_nodes_block(n);
677 set_has_phis(block_info, block);
678 } else if (is_Jmp(n) || is_Cond(n) || is_Proj(n)) {
681 ir_node *block = get_nodes_block(n);
682 set_has_operations(block_info, block);
686 static void clear_block_info(ir_node *block, void *x)
688 ir_phase *block_info = (ir_phase *)x;
689 clear_phase_flag(block_info, block);
692 typedef struct skip_env {
698 * Post-Block-walker: Optimize useless if's (boolean Cond nodes
699 * with same true/false target)
702 static void optimize_ifs(ir_node *block, void *x)
704 skip_env *env = (skip_env*)x;
706 int n_preds = get_Block_n_cfgpreds(block);
708 if (has_phis(env->phase, block))
711 /* optimize Cond predecessors (might produce Bad predecessors) */
712 for (i = 0; i < n_preds; ++i) {
713 for (j = i+1; j < n_preds; ++j) {
714 optimize_pred_cond(block, i, j);
720 * Pre-Block walker: remove empty blocks (only contain a Jmp)
721 * that are control flow predecessors of the current block.
723 static void remove_empty_blocks(ir_node *block, void *x)
725 skip_env *env = (skip_env*)x;
727 int n_preds = get_Block_n_cfgpreds(block);
729 for (i = 0; i < n_preds; ++i) {
730 ir_node *jmp, *jmp_block, *pred, *pred_block;
733 jmp = get_Block_cfgpred(block, i);
736 jmp_block = get_nodes_block(jmp);
737 if (jmp_block == block)
738 continue; /* this infinite loop cannot be optimized any further */
739 if (is_unknown_jump_target(env->phase, jmp_block))
740 continue; /* unknown jump target must not be optimized */
741 if (has_operations(env->phase,jmp_block))
742 continue; /* this block contains operations and cannot be skipped */
743 if (has_phis(env->phase,jmp_block))
744 continue; /* this block contains Phis and is not skipped */
745 if (Block_block_visited(jmp_block)) {
747 /* otherwise we could break the walker,
748 * if block was reached via KeepAlive edge -> jmp_block -> A ---> block,
749 * because the walker cannot handle Id nodes.
759 /* jmp_block is an empty block and can be optimized! */
761 n_jpreds = get_Block_n_cfgpreds(jmp_block);
763 * If the jmp block has only one predecessor this is straightforward.
764 * However, if there are more predecessors, we only handle this,
765 * if block has no Phis.
768 /* skip jmp block by rerouting its predecessor to block
776 pred = get_Block_cfgpred(jmp_block, 0);
779 /* cleanup: jmp_block might have a Keep edge! */
780 pred_block = get_nodes_block(pred);
781 exchange(jmp_block, pred_block);
783 } else if (! has_phis(env->phase, block)) {
784 /* all predecessors can skip the jmp block, so block gets some new predecessors
788 * jmp_block C => Bad C | |
792 ir_node **ins = NULL;
794 NEW_ARR_A(ir_node *, ins, n_preds+n_jpreds);
795 /* first copy the old predecessors, because the outer loop (i) still walks over them */
796 for (j = 0; j < n_preds; ++j) {
797 ins[j] = get_Block_cfgpred(block, j);
799 /* now append the new predecessors */
800 for (j = 0; j < n_jpreds; ++j) {
801 pred = get_Block_cfgpred(jmp_block, j);
802 ins[n_preds+j] = pred;
804 set_irn_in(block, n_preds+n_jpreds, ins);
805 /* convert the jmp_block to Bad */
806 ir_graph *irg = get_irn_irg(block);
807 exchange(jmp_block, new_r_Bad(irg, mode_BB));
808 exchange(jmp, new_r_Bad(irg, mode_X));
809 /* let the outer loop walk over the new predecessors as well */
812 // TODO What if jmp_block had a KeepAlive edge?
814 /* This would involve Phis ... */
820 * All cfg optimizations, which do not touch Phi nodes.
822 * Note that this might create critical edges.
824 static void cfgopt_ignoring_phis(ir_graph *irg)
826 ir_phase *block_info = new_phase(irg, NULL);
827 skip_env env = { true, block_info };
829 while (env.changed) {
830 irg_walk_graph(irg, compute_block_info, NULL, block_info);
833 /* Remove blocks, which only consist of a Jmp */
834 irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
836 /* Optimize Cond->Jmp, where then- and else-block are the same. */
837 irg_block_walk_graph(irg, NULL, optimize_ifs, &env);
840 set_irg_doms_inconsistent(irg);
841 /* clear block info, because it must be recomputed */
842 irg_block_walk_graph(irg, clear_block_info, NULL, block_info);
843 /* Removing blocks and Conds might enable more optimizations */
850 phase_free(block_info);
853 /* Optimizations of the control flow that also require changes of Phi nodes. */
854 void optimize_cf(ir_graph *irg)
858 ir_node *end = get_irg_end(irg);
863 env.phis_moved = false;
865 assert(get_irg_phase_state(irg) != phase_building);
867 /* if the graph is not pinned, we cannot determine empty blocks */
868 assert(get_irg_pinned(irg) != op_pin_state_floats &&
869 "Control flow optimization need a pinned graph");
871 edges_deactivate(irg);
873 /* First the "simple" optimizations, which do not touch Phis */
874 cfgopt_ignoring_phis(irg);
876 /* we use the mark flag to mark removable blocks */
877 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
879 /* The switch Cond optimization might expose unreachable code, so we loop */
882 ir_node **switch_conds = NULL;
883 bool changed = false;
888 * This pass collects all Phi nodes in a link list in the block
889 * nodes. Further it performs simple control flow optimizations.
890 * Finally it marks all blocks that do not contain useful
891 * computations, i.e., these blocks might be removed.
893 switch_conds = NEW_ARR_F(ir_node*, 0);
894 irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, &switch_conds);
896 /* handle all collected switch-Conds */
897 length = ARR_LEN(switch_conds);
898 for (i = 0; i < length; ++i) {
899 ir_node *cond = switch_conds[i];
900 changed |= handle_switch_cond(cond);
902 DEL_ARR_F(switch_conds);
907 set_irg_doms_inconsistent(irg);
908 set_irg_extblk_inconsistent(irg);
909 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
912 /* assert due to collect_nodes:
913 * 1. removable blocks are now marked as such
914 * 2. phi lists are up to date
917 /* Optimize the standard code.
918 * It walks only over block nodes and adapts these and the Phi nodes in these
919 * blocks, which it finds in a linked list computed before.
922 irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
924 new_end = optimize_in_place(end);
925 if (new_end != end) {
926 set_irg_end(irg, new_end);
929 remove_End_Bads_and_doublets(end);
931 ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
933 if (env.phis_moved) {
934 /* Bad: when we moved Phi's, we might produce dead Phi nodes
936 Some other phases cannot copy with this, so kill them.
938 n = get_End_n_keepalives(end);
940 NEW_ARR_A(ir_node *, in, n);
941 assure_irg_outs(irg);
943 for (i = j = 0; i < n; ++i) {
944 ir_node *ka = get_End_keepalive(end, i);
949 for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
950 ir_node *user = get_irn_out(ka, k);
952 if (user != ka && user != end) {
953 /* Is it a real user or just a self loop ? */
963 set_End_keepalives(end, j, in);
970 /* Handle graph state if was changed. */
971 set_irg_doms_inconsistent(irg);
972 set_irg_extblk_inconsistent(irg);
973 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
977 /* Creates an ir_graph pass for optimize_cf. */
978 ir_graph_pass_t *optimize_cf_pass(const char *name)
980 return def_graph_pass(name ? name : "optimize_cf", optimize_cf);