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"
50 #include "opt_manage.h"
55 #include "irbackedge_t.h"
60 #include "irnodehashmap.h"
63 #include "iropt_dbg.h"
65 /** An environment for merge_blocks and collect nodes. */
66 typedef struct merge_env {
67 bool changed; /**< Set if the graph was changed. */
68 bool phis_moved; /**< Set if Phi nodes were moved. */
71 /** set or reset the removable property of a block. */
72 static void set_Block_removable(ir_node *block, bool removable)
74 set_Block_mark(block, removable);
77 /** check if a block has the removable property set. */
78 static bool is_Block_removable(const ir_node *block)
80 return get_Block_mark(block);
83 /** checks if a given Cond node is a switch Cond. */
84 static bool is_switch_Cond(const ir_node *cond)
86 ir_node *sel = get_Cond_selector(cond);
87 return get_irn_mode(sel) != mode_b;
90 /** Walker: clear link fields and mark all blocks as removable. */
91 static void clear_link_and_mark_blocks_removable(ir_node *node, void *ctx)
94 set_irn_link(node, NULL);
96 set_Block_removable(node, true);
97 set_Block_phis(node, NULL);
98 } else if (is_Phi(node)) {
99 set_Phi_next(node, NULL);
104 * Collects all Phi nodes in link list of Block.
105 * Marks all blocks "non_removable" if they contain a node other
106 * than Jmp (and Proj).
107 * Links all Proj nodes to their predecessors.
108 * Collects all switch-Conds in a list.
110 static void collect_nodes(ir_node *n, void *ctx)
112 ir_node ***switch_conds = (ir_node***)ctx;
115 /* Collect Phi nodes to compact ins along with block's ins. */
116 ir_node *block = get_nodes_block(n);
117 add_Block_phi(block, n);
118 } else if (is_Block(n)) {
119 if (has_Block_entity(n)) {
120 /* block with a jump label attached cannot be removed. */
121 set_Block_removable(n, false);
123 } else if (is_Bad(n) || is_Jmp(n)) {
127 /* Check for non-empty block. */
128 ir_node *block = get_nodes_block(n);
130 set_Block_removable(block, false);
133 /* link Proj nodes */
134 ir_node *pred = get_Proj_pred(n);
135 set_irn_link(n, get_irn_link(pred));
136 set_irn_link(pred, n);
137 } else if (is_Cond(n) && is_switch_Cond(n)) {
138 /* found a switch-Cond, collect */
139 ARR_APP1(ir_node*, *switch_conds, n);
144 /** Returns true if pred is predecessor of block b. */
145 static bool is_pred_of(const ir_node *pred, const ir_node *b)
149 for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
150 ir_node *b_pred = get_Block_cfgpred_block(b, i);
157 /** Test whether we can optimize away pred block pos of b.
159 * @param b A block node.
160 * @param pos The position of the predecessor block to judge about.
162 * @returns The number of predecessors
164 * The test is rather tricky.
166 * The situation is something like the following:
175 * b merges the control flow of an if-then-else. We may not remove
176 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
177 * node in b, even if both are empty. The destruction of this Phi
178 * requires that a copy is added before the merge. We have to
179 * keep one of the case blocks to place the copies in.
181 * To perform the test for pos, we must regard predecessors before pos
182 * as already removed.
184 static unsigned test_whether_dispensable(const ir_node *b, int pos)
186 ir_node *pred = get_Block_cfgpred(b, pos);
187 ir_node *predb = get_nodes_block(pred);
189 if (is_Bad(pred) || !is_Block_removable(predb))
192 /* can't remove self-loops */
194 goto non_dispensable;
195 if (is_unknown_jump(pred))
196 goto non_dispensable;
198 /* Seems to be empty. At least we detected this in collect_nodes. */
199 if (get_Block_phis(b) != NULL) {
200 int n_cfgpreds = get_Block_n_cfgpreds(b);
202 /* there are Phi nodes */
204 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
205 * Handle all pred blocks with preds < pos as if they were already
207 for (i = 0; i < pos; i++) {
208 ir_node *other_pred = get_Block_cfgpred(b, i);
209 ir_node *other_predb = get_nodes_block(other_pred);
210 if (is_Bad(other_pred))
212 if (is_Block_removable(other_predb)
213 && !Block_block_visited(other_predb)) {
215 for (j = get_Block_n_cfgpreds(other_predb) - 1; j >= 0; --j) {
216 ir_node *other_predpred
217 = get_Block_cfgpred_block(other_predb, j);
218 if (is_pred_of(other_predpred, predb))
219 goto non_dispensable;
221 } else if (is_pred_of(other_predb, predb)) {
222 goto non_dispensable;
225 for (i = pos+1; i < n_cfgpreds; i++) {
226 ir_node *other_predb = get_Block_cfgpred_block(b, i);
227 if (is_pred_of(other_predb, predb))
228 goto non_dispensable;
231 /* we will not dispense already visited blocks */
232 if (Block_block_visited(predb))
234 /* if we get here, the block is dispensable, count useful preds */
235 return get_irn_arity(predb);
238 set_Block_removable(predb, false);
243 * This method removes empty blocks. A block is empty if it only contains Phi
246 * We first adapt Phi nodes, then Block nodes, as we need the old ins
247 * of the Block to adapt the Phi nodes. We do this by computing new
248 * in arrays, and then replacing the old ones. So far we compute new in arrays
249 * for all nodes, not regarding whether there is a possibility for optimization.
251 * For each predecessor p of a Block b there are three cases:
252 * - The predecessor p is a Bad node: just skip it. The in array of b shrinks
254 * - The predecessor p is empty. Remove p. All predecessors of p are now
256 * - The predecessor p is a block containing useful code. Just keep p as is.
258 * For Phi nodes f we have to check the conditions at the Block of f.
259 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
261 * -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.
262 * In this case we proceed as for blocks. We remove pred_f. All
263 * predecessors of pred_f now are predecessors of f.
264 * -2b: The old predecessor of f is NOT in the block removed. It might be a Phi
265 * too. We have to replicate f for each predecessor of the removed block.
266 * Or, with other words, the removed predecessor block has exactly one
269 * Further there is a special case for self referencing blocks:
272 * then_b else_b then_b else_b
278 * | | | === optimized to ===> \ | | |
285 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
286 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
289 static void optimize_blocks(ir_node *b, void *ctx)
291 int i, j, k, n, max_preds, n_preds, p_preds = -1;
295 merge_env *env = (merge_env*)ctx;
297 if (get_Block_dom_depth(b) < 0) {
298 /* ignore unreachable blocks */
302 /* Count the number of predecessor if this block is merged with pred blocks
305 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
306 max_preds += test_whether_dispensable(b, i);
308 in = XMALLOCN(ir_node*, max_preds);
310 /*- Fix the Phi nodes of the current block -*/
311 for (phi = get_Block_phis(b); phi != NULL; phi = next) {
312 next = get_Phi_next(phi);
314 /* Find the new predecessors for the Phi */
316 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
317 ir_graph *irg = get_irn_irg(b);
318 ir_node *predx = get_Block_cfgpred(b, i);
321 /* case Phi 1: maintain Bads, as somebody else is responsible to
324 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
328 pred = get_nodes_block(predx);
330 /* case Phi 2: It's an empty block and not yet visited. */
331 if (is_Block_removable(pred) && !Block_block_visited(pred)) {
332 ir_node *phi_pred = get_Phi_pred(phi, i);
334 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
335 ir_node *pred_pred = get_Block_cfgpred(pred, j);
337 if (is_Bad(pred_pred)) {
338 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
342 if (get_nodes_block(phi_pred) == pred) {
344 assert(is_Phi(phi_pred)); /* Block is empty!! */
346 in[p_preds++] = get_Phi_pred(phi_pred, j);
349 in[p_preds++] = phi_pred;
354 in[p_preds++] = get_Phi_pred(phi, i);
357 assert(p_preds == max_preds);
361 exchange(phi, in[0]);
363 set_irn_in(phi, p_preds, in);
368 /*- This happens only if merge between loop backedge and single loop entry.
369 Moreover, it is only needed if predb is the direct dominator of b,
370 else there can be no uses of the Phi's in predb ... -*/
371 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
372 ir_node *pred = get_Block_cfgpred(b, k);
373 ir_node *predb = get_nodes_block(pred);
377 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
380 /* we found a predecessor block at position k that will be removed */
381 for (phi = get_Block_phis(predb); phi != NULL; phi = next_phi) {
383 next_phi = get_Phi_next(phi);
385 if (get_Block_idom(b) != predb) {
386 /* predb is not the dominator. There can't be uses of
387 * pred's Phi nodes, kill them .*/
388 ir_graph *irg = get_irn_irg(b);
389 ir_mode *mode = get_irn_mode(phi);
390 exchange(phi, new_r_Bad(irg, mode));
392 /* predb is the direct dominator of b. There might be uses
393 * of the Phi nodes from predb in further block, so move
394 * this phi from the predecessor into the block b */
395 set_nodes_block(phi, b);
396 set_Phi_next(phi, get_Block_phis(b));
397 set_Block_phis(b, phi);
398 env->phis_moved = true;
400 /* first, copy all 0..k-1 predecessors */
401 for (i = 0; i < k; i++) {
402 ir_node *predx = get_Block_cfgpred(b, i);
406 ir_graph *irg = get_irn_irg(b);
407 ir_mode *mode = get_irn_mode(phi);
408 in[q_preds++] = new_r_Bad(irg, mode);
411 pred_block = get_nodes_block(predx);
412 if (is_Block_removable(pred_block)
413 && !Block_block_visited(pred_block)) {
414 int n_cfgpreds = get_Block_n_cfgpreds(pred_block);
415 /* It's an empty block and not yet visited. */
416 for (j = 0; j < n_cfgpreds; j++) {
417 if (!is_Bad(get_Block_cfgpred(pred_block, j))) {
420 ir_graph *irg = get_irn_irg(b);
421 ir_mode *mode = get_irn_mode(phi);
422 in[q_preds++] = new_r_Bad(irg, mode);
430 /* now we are at k, copy the phi predecessors */
431 pred = get_nodes_block(get_Block_cfgpred(b, k));
432 for (i = 0; i < get_Phi_n_preds(phi); i++) {
433 in[q_preds++] = get_Phi_pred(phi, i);
436 /* and now all the rest */
437 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
438 pred = get_Block_cfgpred_block(b, i);
441 ir_graph *irg = get_irn_irg(b);
442 ir_mode *mode = get_irn_mode(phi);
443 in[q_preds++] = new_r_Bad(irg, mode);
444 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
445 /* It's an empty block and not yet visited. */
446 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
447 if (! is_Bad(get_Block_cfgpred(pred, j))) {
450 ir_graph *irg = get_irn_irg(b);
451 ir_mode *mode = get_irn_mode(phi);
452 in[q_preds++] = new_r_Bad(irg, mode);
462 exchange(phi, in[0]);
464 set_irn_in(phi, q_preds, in);
467 assert(q_preds <= max_preds);
468 // assert(p_preds == q_preds && "Wrong Phi Fix");
474 /*- Fix the block -*/
476 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
477 ir_node *pred = get_Block_cfgpred(b, i);
478 ir_node *predb = get_nodes_block(pred);
479 ir_graph *irg = get_irn_irg(pred);
481 /* case 1: Bad predecessor */
483 in[n_preds++] = new_r_Bad(irg, mode_X);
486 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
487 /* case 2: It's an empty block and not yet visited. */
488 for (j = 0; j < get_Block_n_cfgpreds(predb); j++) {
489 ir_node *predpred = get_Block_cfgpred(predb, j);
491 if (is_Bad(predpred)) {
492 in[n_preds++] = new_r_Bad(irg, mode_X);
496 in[n_preds++] = predpred;
498 /* Remove block+jump as it might be kept alive. */
499 exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
500 exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
503 in[n_preds++] = pred;
506 assert(n_preds == max_preds);
508 set_irn_in(b, n_preds, in);
511 /* see if phi-fix was correct */
512 assert(get_Block_phis(b) == NULL || p_preds == -1 || (n_preds == p_preds));
517 * Optimize table-switch Conds.
519 * @param cond the switch-Cond
520 * @return true if the switch-Cond was optimized
522 static bool handle_switch_cond(ir_node *cond)
524 ir_node *sel = get_Cond_selector(cond);
525 ir_node *proj1 = (ir_node*)get_irn_link(cond);
526 ir_node *proj2 = (ir_node*)get_irn_link(proj1);
527 ir_node *blk = get_nodes_block(cond);
529 /* exactly 1 Proj on the Cond node: must be the defaultProj */
531 ir_node *jmp = new_r_Jmp(blk);
532 assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
533 /* convert it into a Jmp */
534 exchange(proj1, jmp);
538 /* handle Cond nodes with constant argument. In this case the localopt rules
539 * should have killed all obviously impossible cases.
540 * So the only case left to handle here is 1 defaultProj + 1 case
541 * (this one case should be the one taken) */
542 if (get_irn_link(proj2) == NULL) {
543 ir_tarval *tv = value_of(sel);
545 if (tv != tarval_bad) {
546 /* we have a constant switch */
547 long num = get_tarval_long(tv);
548 long def_num = get_Cond_default_proj(cond);
549 ir_graph *irg = get_irn_irg(cond);
550 ir_node *bad = new_r_Bad(irg, mode_X);
552 if (def_num == get_Proj_proj(proj1)) {
553 /* first one is the defProj */
554 if (num == get_Proj_proj(proj2)) {
555 ir_node *jmp = new_r_Jmp(blk);
556 exchange(proj2, jmp);
557 exchange(proj1, bad);
560 } else if (def_num == get_Proj_proj(proj2)) {
561 /* second one is the defProj */
562 if (num == get_Proj_proj(proj1)) {
563 ir_node *jmp = new_r_Jmp(blk);
564 exchange(proj1, jmp);
565 exchange(proj2, bad);
569 /* neither: strange, Cond was not optimized so far */
570 if (num == get_Proj_proj(proj1)) {
571 ir_node *jmp = new_r_Jmp(blk);
572 exchange(proj1, jmp);
573 exchange(proj2, bad);
575 } else if (num == get_Proj_proj(proj2)) {
576 ir_node *jmp = new_r_Jmp(blk);
577 exchange(proj2, jmp);
578 exchange(proj1, bad);
588 * Optimize boolean Conds, where true and false jump to the same block into a Jmp
589 * Block must contain no Phi nodes.
593 * projA projB => Jmp Bad
597 static bool optimize_pred_cond(ir_node *block, int i, int j)
599 ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
602 projA = get_Block_cfgpred(block, i);
603 if (!is_Proj(projA)) return false;
604 projB = get_Block_cfgpred(block, j);
605 if (!is_Proj(projB)) return false;
606 cond = get_Proj_pred(projA);
607 if (!is_Cond(cond)) return false;
609 if (cond != get_Proj_pred(projB)) return false;
610 if (is_switch_Cond(cond)) return false;
612 /* cond should actually be a Jmp */
613 pred_block = get_nodes_block(cond);
614 jmp = new_r_Jmp(pred_block);
615 bad = new_r_Bad(get_irn_irg(block), mode_X);
617 assert(projA != projB);
618 exchange(projA, jmp);
619 exchange(projB, bad);
623 typedef enum block_flags_t {
624 BF_HAS_OPERATIONS = 1 << 0,
625 BF_HAS_PHIS = 1 << 1,
626 BF_IS_UNKNOWN_JUMP_TARGET = 1 << 2,
629 static bool get_block_flag(const ir_nodehashmap_t *infos, const ir_node *block,
632 return PTR_TO_INT(ir_nodehashmap_get(infos, block)) & flag;
635 static void set_block_flag(ir_nodehashmap_t *infos, ir_node *block,
638 int data = PTR_TO_INT(ir_nodehashmap_get(infos, block));
640 ir_nodehashmap_insert(infos, block, INT_TO_PTR(data));
643 static void clear_block_flag(ir_nodehashmap_t *infos, const ir_node *block)
645 ir_nodehashmap_remove(infos, block);
648 static bool has_operations(ir_nodehashmap_t *infos, const ir_node *block)
650 return get_block_flag(infos, block, BF_HAS_OPERATIONS);
653 static void set_has_operations(ir_nodehashmap_t *infos, ir_node *block)
655 set_block_flag(infos, block, BF_HAS_OPERATIONS);
658 static bool has_phis(ir_nodehashmap_t *infos, const ir_node *block)
660 return get_block_flag(infos, block, BF_HAS_PHIS);
663 static void set_has_phis(ir_nodehashmap_t *infos, ir_node *block)
665 set_block_flag(infos, block, BF_HAS_PHIS);
668 static bool is_unknown_jump_target(ir_nodehashmap_t *infos, const ir_node *block)
670 return get_block_flag(infos, block, BF_IS_UNKNOWN_JUMP_TARGET);
673 static void set_is_unknown_jump_target(ir_nodehashmap_t *infos, ir_node *block)
675 set_block_flag(infos, block, BF_IS_UNKNOWN_JUMP_TARGET);
679 * Pre-Walker: fill block info information.
681 static void compute_block_info(ir_node *n, void *x)
683 ir_nodehashmap_t *infos = (ir_nodehashmap_t*)x;
686 int i, max = get_Block_n_cfgpreds(n);
687 for (i=0; i<max; i++) {
688 ir_node *pred = get_Block_cfgpred(n,i);
689 if (is_unknown_jump(pred)) {
690 set_is_unknown_jump_target(infos, n);
693 } else if (is_Phi(n)) {
694 ir_node *block = get_nodes_block(n);
695 set_has_phis(infos, block);
696 } else if (is_Jmp(n) || is_Cond(n) || is_Proj(n)) {
699 ir_node *block = get_nodes_block(n);
700 set_has_operations(infos, block);
704 static void clear_block_info(ir_node *block, void *x)
706 ir_nodehashmap_t *infos = (ir_nodehashmap_t*)x;
707 clear_block_flag(infos, block);
710 typedef struct skip_env {
712 ir_nodehashmap_t block_infos;
716 * Post-Block-walker: Optimize useless if's (boolean Cond nodes
717 * with same true/false target) away.
719 static void optimize_ifs(ir_node *block, void *x)
721 skip_env *env = (skip_env*)x;
723 int n_preds = get_Block_n_cfgpreds(block);
725 if (has_phis(&env->block_infos, block))
728 /* optimize Cond predecessors (might produce Bad predecessors) */
729 for (i = 0; i < n_preds; ++i) {
730 for (j = i+1; j < n_preds; ++j) {
731 optimize_pred_cond(block, i, j);
737 * Pre-Block walker: remove empty blocks (only contain a Jmp)
738 * that are control flow predecessors of the current block.
740 static void remove_empty_blocks(ir_node *block, void *x)
742 skip_env *env = (skip_env*)x;
744 int n_preds = get_Block_n_cfgpreds(block);
746 for (i = 0; i < n_preds; ++i) {
747 ir_node *jmp, *jmp_block, *pred, *pred_block;
750 jmp = get_Block_cfgpred(block, i);
753 jmp_block = get_nodes_block(jmp);
754 if (jmp_block == block)
755 continue; /* this infinite loop cannot be optimized any further */
756 if (is_unknown_jump_target(&env->block_infos, jmp_block))
757 continue; /* unknown jump target must not be optimized */
758 if (has_operations(&env->block_infos,jmp_block))
759 continue; /* this block contains operations and cannot be skipped */
760 if (has_phis(&env->block_infos,jmp_block))
761 continue; /* this block contains Phis and is not skipped */
762 if (Block_block_visited(jmp_block)) {
764 /* otherwise we could break the walker,
765 * if block was reached via
766 * KeepAlive edge -> jmp_block -> A ---> block,
767 * because the walker cannot handle Id nodes.
777 /* jmp_block is an empty block and can be optimized! */
779 n_jpreds = get_Block_n_cfgpreds(jmp_block);
781 * If the jmp block has only one predecessor this is straightforward.
782 * However, if there are more predecessors, we only handle this,
783 * if block has no Phis.
786 /* skip jmp block by rerouting its predecessor to block
794 pred = get_Block_cfgpred(jmp_block, 0);
797 /* cleanup: jmp_block might have a Keep edge! */
798 pred_block = get_nodes_block(pred);
799 exchange(jmp_block, pred_block);
801 } else if (! has_phis(&env->block_infos, block)) {
802 /* all predecessors can skip the jmp block, so block gets some new
807 * jmp_block C => Bad C | |
811 ir_node **ins = ALLOCAN(ir_node*, n_preds+n_jpreds);
813 /* first copy the old predecessors, because the outer loop (i)
814 * still walks over them */
815 for (j = 0; j < n_preds; ++j) {
816 ins[j] = get_Block_cfgpred(block, j);
818 /* now append the new predecessors */
819 for (j = 0; j < n_jpreds; ++j) {
820 pred = get_Block_cfgpred(jmp_block, j);
821 ins[n_preds+j] = pred;
823 set_irn_in(block, n_preds+n_jpreds, ins);
824 /* convert the jmp_block to Bad */
825 ir_graph *irg = get_irn_irg(block);
826 exchange(jmp_block, new_r_Bad(irg, mode_BB));
827 exchange(jmp, new_r_Bad(irg, mode_X));
828 /* let the outer loop walk over the new predecessors as well */
831 // TODO What if jmp_block had a KeepAlive edge?
833 /* This would involve Phis ... */
839 * All cfg optimizations, which do not touch Phi nodes.
841 * Note that this might create critical edges.
843 static void cfgopt_ignoring_phis(ir_graph *irg)
848 ir_nodehashmap_init(&env.block_infos);
850 while (env.changed) {
851 irg_walk_graph(irg, compute_block_info, NULL, &env.block_infos);
854 /* Remove blocks, which only consist of a Jmp */
855 irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
857 /* Optimize Cond->Jmp, where then- and else-block are the same. */
858 irg_block_walk_graph(irg, NULL, optimize_ifs, &env);
861 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
862 /* clear block info, because it must be recomputed */
863 irg_block_walk_graph(irg, clear_block_info, NULL, &env.block_infos);
864 /* Removing blocks and Conds might enable more optimizations */
871 ir_nodehashmap_destroy(&env.block_infos);
874 /* Optimizations of the control flow that also require changes of Phi nodes. */
875 static ir_graph_state_t do_cfopt(ir_graph *irg)
879 ir_node *end = get_irg_end(irg);
884 env.phis_moved = false;
886 assert(get_irg_phase_state(irg) != phase_building);
888 /* if the graph is not pinned, we cannot determine empty blocks */
889 assert(get_irg_pinned(irg) != op_pin_state_floats &&
890 "Control flow optimization need a pinned graph");
892 edges_deactivate(irg);
894 /* First the "simple" optimizations, which do not touch Phis */
895 cfgopt_ignoring_phis(irg);
897 /* we use the mark flag to mark removable blocks */
898 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK
899 | IR_RESOURCE_PHI_LIST);
901 /* The switch Cond optimization might expose unreachable code, so we loop */
904 ir_node **switch_conds = NULL;
905 bool changed = false;
910 * This pass collects all Phi nodes in a link list in the block
911 * nodes. Further it performs simple control flow optimizations.
912 * Finally it marks all blocks that do not contain useful
913 * computations, i.e., these blocks might be removed.
915 switch_conds = NEW_ARR_F(ir_node*, 0);
916 irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, &switch_conds);
918 /* handle all collected switch-Conds */
919 length = ARR_LEN(switch_conds);
920 for (i = 0; i < length; ++i) {
921 ir_node *cond = switch_conds[i];
922 changed |= handle_switch_cond(cond);
924 DEL_ARR_F(switch_conds);
929 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
930 | IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS
931 | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE);
934 /* assert due to collect_nodes:
935 * 1. removable blocks are now marked as such
936 * 2. phi lists are up to date
939 /* Optimize the standard code.
940 * It walks only over block nodes and adapts these and the Phi nodes in these
941 * blocks, which it finds in a linked list computed before.
944 irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
946 new_end = optimize_in_place(end);
947 if (new_end != end) {
948 set_irg_end(irg, new_end);
951 remove_End_Bads_and_doublets(end);
953 ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK
954 | IR_RESOURCE_PHI_LIST);
956 if (env.phis_moved) {
957 /* Bad: when we moved Phi's, we might produce dead Phi nodes
959 Some other phases cannot copy with this, so kill them.
961 n = get_End_n_keepalives(end);
963 NEW_ARR_A(ir_node *, in, n);
964 assure_irg_outs(irg);
966 for (i = j = 0; i < n; ++i) {
967 ir_node *ka = get_End_keepalive(end, i);
972 for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
973 ir_node *user = get_irn_out(ka, k);
975 if (user != ka && user != end) {
976 /* Is it a real user or just a self loop ? */
986 set_End_keepalives(end, j, in);
995 static optdesc_t opt_cf = {
997 IR_GRAPH_STATE_NO_UNREACHABLE_CODE,
1001 void optimize_cf(ir_graph *irg)
1003 perform_irg_optimization(irg, &opt_cf);
1006 /* Creates an ir_graph pass for optimize_cf. */
1007 ir_graph_pass_t *optimize_cf_pass(const char *name)
1009 return def_graph_pass(name ? name : "optimize_cf", optimize_cf);