2014-09-15 Andreas Krebbel <Andreas.Krebbel@de.ibm.com>
[official-gcc.git] / gcc / tree-cfgcleanup.c
bloba66ec6e75375a823f059f6d62d5b88ebf69fdfb3
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "tm_p.h"
26 #include "basic-block.h"
27 #include "diagnostic-core.h"
28 #include "flags.h"
29 #include "function.h"
30 #include "langhooks.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "tree-eh.h"
34 #include "gimple-expr.h"
35 #include "is-a.h"
36 #include "gimple.h"
37 #include "gimplify.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-cfg.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "expr.h"
47 #include "tree-dfa.h"
48 #include "tree-ssa.h"
49 #include "tree-pass.h"
50 #include "except.h"
51 #include "cfgloop.h"
52 #include "hashtab.h"
53 #include "tree-ssa-propagate.h"
54 #include "tree-scalar-evolution.h"
56 /* The set of blocks in that at least one of the following changes happened:
57 -- the statement at the end of the block was changed
58 -- the block was newly created
59 -- the set of the predecessors of the block changed
60 -- the set of the successors of the block changed
61 ??? Maybe we could track these changes separately, since they determine
62 what cleanups it makes sense to try on the block. */
63 bitmap cfgcleanup_altered_bbs;
65 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
67 static bool
68 remove_fallthru_edge (vec<edge, va_gc> *ev)
70 edge_iterator ei;
71 edge e;
73 FOR_EACH_EDGE (e, ei, ev)
74 if ((e->flags & EDGE_FALLTHRU) != 0)
76 if (e->flags & EDGE_COMPLEX)
77 e->flags &= ~EDGE_FALLTHRU;
78 else
79 remove_edge_and_dominated_blocks (e);
80 return true;
82 return false;
86 /* Disconnect an unreachable block in the control expression starting
87 at block BB. */
89 static bool
90 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
92 edge taken_edge;
93 bool retval = false;
94 gimple stmt = gsi_stmt (gsi);
95 tree val;
97 if (!single_succ_p (bb))
99 edge e;
100 edge_iterator ei;
101 bool warned;
102 location_t loc;
104 fold_defer_overflow_warnings ();
105 loc = gimple_location (stmt);
106 switch (gimple_code (stmt))
108 case GIMPLE_COND:
109 val = fold_binary_loc (loc, gimple_cond_code (stmt),
110 boolean_type_node,
111 gimple_cond_lhs (stmt),
112 gimple_cond_rhs (stmt));
113 break;
115 case GIMPLE_SWITCH:
116 val = gimple_switch_index (stmt);
117 break;
119 default:
120 val = NULL_TREE;
122 taken_edge = find_taken_edge (bb, val);
123 if (!taken_edge)
125 fold_undefer_and_ignore_overflow_warnings ();
126 return false;
129 /* Remove all the edges except the one that is always executed. */
130 warned = false;
131 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
133 if (e != taken_edge)
135 if (!warned)
137 fold_undefer_overflow_warnings
138 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
139 warned = true;
142 taken_edge->probability += e->probability;
143 taken_edge->count += e->count;
144 remove_edge_and_dominated_blocks (e);
145 retval = true;
147 else
148 ei_next (&ei);
150 if (!warned)
151 fold_undefer_and_ignore_overflow_warnings ();
152 if (taken_edge->probability > REG_BR_PROB_BASE)
153 taken_edge->probability = REG_BR_PROB_BASE;
155 else
156 taken_edge = single_succ_edge (bb);
158 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
159 gsi_remove (&gsi, true);
160 taken_edge->flags = EDGE_FALLTHRU;
162 return retval;
165 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
166 to updated gimple_call_flags. */
168 static void
169 cleanup_call_ctrl_altering_flag (gimple bb_end)
171 if (!is_gimple_call (bb_end)
172 || !gimple_call_ctrl_altering_p (bb_end))
173 return;
175 int flags = gimple_call_flags (bb_end);
176 if (((flags & (ECF_CONST | ECF_PURE))
177 && !(flags & ECF_LOOPING_CONST_OR_PURE))
178 || (flags & ECF_LEAF))
179 gimple_call_set_ctrl_altering (bb_end, false);
182 /* Try to remove superfluous control structures in basic block BB. Returns
183 true if anything changes. */
185 static bool
186 cleanup_control_flow_bb (basic_block bb)
188 gimple_stmt_iterator gsi;
189 bool retval = false;
190 gimple stmt;
192 /* If the last statement of the block could throw and now cannot,
193 we need to prune cfg. */
194 retval |= gimple_purge_dead_eh_edges (bb);
196 gsi = gsi_last_bb (bb);
197 if (gsi_end_p (gsi))
198 return retval;
200 stmt = gsi_stmt (gsi);
202 /* Try to cleanup ctrl altering flag for call which ends bb. */
203 cleanup_call_ctrl_altering_flag (stmt);
205 if (gimple_code (stmt) == GIMPLE_COND
206 || gimple_code (stmt) == GIMPLE_SWITCH)
207 retval |= cleanup_control_expr_graph (bb, gsi);
208 else if (gimple_code (stmt) == GIMPLE_GOTO
209 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
210 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
211 == LABEL_DECL))
213 /* If we had a computed goto which has a compile-time determinable
214 destination, then we can eliminate the goto. */
215 edge e;
216 tree label;
217 edge_iterator ei;
218 basic_block target_block;
220 /* First look at all the outgoing edges. Delete any outgoing
221 edges which do not go to the right block. For the one
222 edge which goes to the right block, fix up its flags. */
223 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
224 target_block = label_to_block (label);
225 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
227 if (e->dest != target_block)
228 remove_edge_and_dominated_blocks (e);
229 else
231 /* Turn off the EDGE_ABNORMAL flag. */
232 e->flags &= ~EDGE_ABNORMAL;
234 /* And set EDGE_FALLTHRU. */
235 e->flags |= EDGE_FALLTHRU;
236 ei_next (&ei);
240 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
241 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
243 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
244 relevant information we need. */
245 gsi_remove (&gsi, true);
246 retval = true;
249 /* Check for indirect calls that have been turned into
250 noreturn calls. */
251 else if (is_gimple_call (stmt)
252 && gimple_call_noreturn_p (stmt)
253 && remove_fallthru_edge (bb->succs))
254 retval = true;
256 return retval;
259 /* Return true if basic block BB does nothing except pass control
260 flow to another block and that we can safely insert a label at
261 the start of the successor block.
263 As a precondition, we require that BB be not equal to
264 the entry block. */
266 static bool
267 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
269 gimple_stmt_iterator gsi;
270 location_t locus;
272 /* BB must have a single outgoing edge. */
273 if (single_succ_p (bb) != 1
274 /* If PHI_WANTED is false, BB must not have any PHI nodes.
275 Otherwise, BB must have PHI nodes. */
276 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
277 /* BB may not be a predecessor of the exit block. */
278 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
279 /* Nor should this be an infinite loop. */
280 || single_succ (bb) == bb
281 /* BB may not have an abnormal outgoing edge. */
282 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
283 return false;
285 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
287 locus = single_succ_edge (bb)->goto_locus;
289 /* There should not be an edge coming from entry, or an EH edge. */
291 edge_iterator ei;
292 edge e;
294 FOR_EACH_EDGE (e, ei, bb->preds)
295 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
296 return false;
297 /* If goto_locus of any of the edges differs, prevent removing
298 the forwarder block for -O0. */
299 else if (optimize == 0 && e->goto_locus != locus)
300 return false;
303 /* Now walk through the statements backward. We can ignore labels,
304 anything else means this is not a forwarder block. */
305 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
307 gimple stmt = gsi_stmt (gsi);
309 switch (gimple_code (stmt))
311 case GIMPLE_LABEL:
312 if (DECL_NONLOCAL (gimple_label_label (stmt)))
313 return false;
314 if (optimize == 0 && gimple_location (stmt) != locus)
315 return false;
316 break;
318 /* ??? For now, hope there's a corresponding debug
319 assignment at the destination. */
320 case GIMPLE_DEBUG:
321 break;
323 default:
324 return false;
328 if (current_loops)
330 basic_block dest;
331 /* Protect loop headers. */
332 if (bb->loop_father->header == bb)
333 return false;
335 dest = EDGE_SUCC (bb, 0)->dest;
336 /* Protect loop preheaders and latches if requested. */
337 if (dest->loop_father->header == dest)
339 if (bb->loop_father == dest->loop_father)
341 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
342 return false;
343 /* If bb doesn't have a single predecessor we'd make this
344 loop have multiple latches. Don't do that if that
345 would in turn require disambiguating them. */
346 return (single_pred_p (bb)
347 || loops_state_satisfies_p
348 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
350 else if (bb->loop_father == loop_outer (dest->loop_father))
351 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
352 /* Always preserve other edges into loop headers that are
353 not simple latches or preheaders. */
354 return false;
358 return true;
361 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
362 those alternatives are equal in each of the PHI nodes, then return
363 true, else return false. */
365 static bool
366 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
368 int n1 = e1->dest_idx;
369 int n2 = e2->dest_idx;
370 gimple_stmt_iterator gsi;
372 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
374 gimple phi = gsi_stmt (gsi);
375 tree val1 = gimple_phi_arg_def (phi, n1);
376 tree val2 = gimple_phi_arg_def (phi, n2);
378 gcc_assert (val1 != NULL_TREE);
379 gcc_assert (val2 != NULL_TREE);
381 if (!operand_equal_for_phi_arg_p (val1, val2))
382 return false;
385 return true;
388 /* Removes forwarder block BB. Returns false if this failed. */
390 static bool
391 remove_forwarder_block (basic_block bb)
393 edge succ = single_succ_edge (bb), e, s;
394 basic_block dest = succ->dest;
395 gimple label;
396 edge_iterator ei;
397 gimple_stmt_iterator gsi, gsi_to;
398 bool can_move_debug_stmts;
400 /* We check for infinite loops already in tree_forwarder_block_p.
401 However it may happen that the infinite loop is created
402 afterwards due to removal of forwarders. */
403 if (dest == bb)
404 return false;
406 /* If the destination block consists of a nonlocal label or is a
407 EH landing pad, do not merge it. */
408 label = first_stmt (dest);
409 if (label
410 && gimple_code (label) == GIMPLE_LABEL
411 && (DECL_NONLOCAL (gimple_label_label (label))
412 || EH_LANDING_PAD_NR (gimple_label_label (label)) != 0))
413 return false;
415 /* If there is an abnormal edge to basic block BB, but not into
416 dest, problems might occur during removal of the phi node at out
417 of ssa due to overlapping live ranges of registers.
419 If there is an abnormal edge in DEST, the problems would occur
420 anyway since cleanup_dead_labels would then merge the labels for
421 two different eh regions, and rest of exception handling code
422 does not like it.
424 So if there is an abnormal edge to BB, proceed only if there is
425 no abnormal edge to DEST and there are no phi nodes in DEST. */
426 if (bb_has_abnormal_pred (bb)
427 && (bb_has_abnormal_pred (dest)
428 || !gimple_seq_empty_p (phi_nodes (dest))))
429 return false;
431 /* If there are phi nodes in DEST, and some of the blocks that are
432 predecessors of BB are also predecessors of DEST, check that the
433 phi node arguments match. */
434 if (!gimple_seq_empty_p (phi_nodes (dest)))
436 FOR_EACH_EDGE (e, ei, bb->preds)
438 s = find_edge (e->src, dest);
439 if (!s)
440 continue;
442 if (!phi_alternatives_equal (dest, succ, s))
443 return false;
447 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
449 basic_block pred = NULL;
450 if (single_pred_p (bb))
451 pred = single_pred (bb);
453 /* Redirect the edges. */
454 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
456 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
458 if (e->flags & EDGE_ABNORMAL)
460 /* If there is an abnormal edge, redirect it anyway, and
461 move the labels to the new block to make it legal. */
462 s = redirect_edge_succ_nodup (e, dest);
464 else
465 s = redirect_edge_and_branch (e, dest);
467 if (s == e)
469 /* Create arguments for the phi nodes, since the edge was not
470 here before. */
471 for (gsi = gsi_start_phis (dest);
472 !gsi_end_p (gsi);
473 gsi_next (&gsi))
475 gimple phi = gsi_stmt (gsi);
476 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
477 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
478 add_phi_arg (phi, unshare_expr (def), s, l);
483 /* Move nonlocal labels and computed goto targets as well as user
484 defined labels and labels with an EH landing pad number to the
485 new block, so that the redirection of the abnormal edges works,
486 jump targets end up in a sane place and debug information for
487 labels is retained. */
488 gsi_to = gsi_start_bb (dest);
489 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
491 tree decl;
492 label = gsi_stmt (gsi);
493 if (is_gimple_debug (label))
494 break;
495 decl = gimple_label_label (label);
496 if (EH_LANDING_PAD_NR (decl) != 0
497 || DECL_NONLOCAL (decl)
498 || FORCED_LABEL (decl)
499 || !DECL_ARTIFICIAL (decl))
501 gsi_remove (&gsi, false);
502 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
504 else
505 gsi_next (&gsi);
508 /* Move debug statements if the destination has a single predecessor. */
509 if (can_move_debug_stmts)
511 gsi_to = gsi_after_labels (dest);
512 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
514 gimple debug = gsi_stmt (gsi);
515 if (!is_gimple_debug (debug))
516 break;
517 gsi_remove (&gsi, false);
518 gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
522 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
524 /* Update the dominators. */
525 if (dom_info_available_p (CDI_DOMINATORS))
527 basic_block dom, dombb, domdest;
529 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
530 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
531 if (domdest == bb)
533 /* Shortcut to avoid calling (relatively expensive)
534 nearest_common_dominator unless necessary. */
535 dom = dombb;
537 else
538 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
540 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
543 /* Adjust latch infomation of BB's parent loop as otherwise
544 the cfg hook has a hard time not to kill the loop. */
545 if (current_loops && bb->loop_father->latch == bb)
546 bb->loop_father->latch = pred;
548 /* And kill the forwarder block. */
549 delete_basic_block (bb);
551 return true;
554 /* STMT is a call that has been discovered noreturn. Fixup the CFG
555 and remove LHS. Return true if something changed. */
557 bool
558 fixup_noreturn_call (gimple stmt)
560 basic_block bb = gimple_bb (stmt);
561 bool changed = false;
563 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
564 return false;
566 /* First split basic block if stmt is not last. */
567 if (stmt != gsi_stmt (gsi_last_bb (bb)))
568 split_block (bb, stmt);
570 changed |= remove_fallthru_edge (bb->succs);
572 /* If there is LHS, remove it. */
573 if (gimple_call_lhs (stmt))
575 tree op = gimple_call_lhs (stmt);
576 gimple_call_set_lhs (stmt, NULL_TREE);
578 /* We need to remove SSA name to avoid checking errors.
579 All uses are dominated by the noreturn and thus will
580 be removed afterwards.
581 We proactively remove affected non-PHI statements to avoid
582 fixup_cfg from trying to update them and crashing. */
583 if (TREE_CODE (op) == SSA_NAME)
585 use_operand_p use_p;
586 imm_use_iterator iter;
587 gimple use_stmt;
588 bitmap_iterator bi;
589 unsigned int bb_index;
591 bitmap blocks = BITMAP_ALLOC (NULL);
593 FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
595 if (gimple_code (use_stmt) != GIMPLE_PHI)
596 bitmap_set_bit (blocks, gimple_bb (use_stmt)->index);
597 else
598 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
599 SET_USE (use_p, error_mark_node);
601 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, bb_index, bi)
602 delete_basic_block (BASIC_BLOCK_FOR_FN (cfun, bb_index));
603 BITMAP_FREE (blocks);
604 release_ssa_name (op);
606 update_stmt (stmt);
607 changed = true;
609 return changed;
613 /* Split basic blocks on calls in the middle of a basic block that are now
614 known not to return, and remove the unreachable code. */
616 static bool
617 split_bb_on_noreturn_calls (basic_block bb)
619 bool changed = false;
620 gimple_stmt_iterator gsi;
622 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
624 gimple stmt = gsi_stmt (gsi);
626 if (!is_gimple_call (stmt))
627 continue;
629 if (gimple_call_noreturn_p (stmt))
630 changed |= fixup_noreturn_call (stmt);
633 if (changed)
634 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
635 return changed;
638 /* Tries to cleanup cfg in basic block BB. Returns true if anything
639 changes. */
641 static bool
642 cleanup_tree_cfg_bb (basic_block bb)
644 bool retval = cleanup_control_flow_bb (bb);
646 if (tree_forwarder_block_p (bb, false)
647 && remove_forwarder_block (bb))
648 return true;
650 /* Merging the blocks may create new opportunities for folding
651 conditional branches (due to the elimination of single-valued PHI
652 nodes). */
653 if (single_succ_p (bb)
654 && can_merge_blocks_p (bb, single_succ (bb)))
656 merge_blocks (bb, single_succ (bb));
657 return true;
660 return retval;
663 /* Iterate the cfg cleanups, while anything changes. */
665 static bool
666 cleanup_tree_cfg_1 (void)
668 bool retval = false;
669 basic_block bb;
670 unsigned i, n;
672 /* Prepare the worklists of altered blocks. */
673 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
675 /* During forwarder block cleanup, we may redirect edges out of
676 SWITCH_EXPRs, which can get expensive. So we want to enable
677 recording of edge to CASE_LABEL_EXPR. */
678 start_recording_case_labels ();
680 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
681 since the basic blocks may get removed. */
682 n = last_basic_block_for_fn (cfun);
683 for (i = NUM_FIXED_BLOCKS; i < n; i++)
685 bb = BASIC_BLOCK_FOR_FN (cfun, i);
686 if (bb)
688 retval |= cleanup_tree_cfg_bb (bb);
689 retval |= split_bb_on_noreturn_calls (bb);
693 /* Now process the altered blocks, as long as any are available. */
694 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
696 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
697 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
698 if (i < NUM_FIXED_BLOCKS)
699 continue;
701 bb = BASIC_BLOCK_FOR_FN (cfun, i);
702 if (!bb)
703 continue;
705 retval |= cleanup_tree_cfg_bb (bb);
707 /* Rerun split_bb_on_noreturn_calls, in case we have altered any noreturn
708 calls. */
709 retval |= split_bb_on_noreturn_calls (bb);
712 end_recording_case_labels ();
713 BITMAP_FREE (cfgcleanup_altered_bbs);
714 return retval;
718 /* Remove unreachable blocks and other miscellaneous clean up work.
719 Return true if the flowgraph was modified, false otherwise. */
721 static bool
722 cleanup_tree_cfg_noloop (void)
724 bool changed;
726 timevar_push (TV_TREE_CLEANUP_CFG);
728 /* Iterate until there are no more cleanups left to do. If any
729 iteration changed the flowgraph, set CHANGED to true.
731 If dominance information is available, there cannot be any unreachable
732 blocks. */
733 if (!dom_info_available_p (CDI_DOMINATORS))
735 changed = delete_unreachable_blocks ();
736 calculate_dominance_info (CDI_DOMINATORS);
738 else
740 #ifdef ENABLE_CHECKING
741 verify_dominators (CDI_DOMINATORS);
742 #endif
743 changed = false;
746 changed |= cleanup_tree_cfg_1 ();
748 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
749 compact_blocks ();
751 #ifdef ENABLE_CHECKING
752 verify_flow_info ();
753 #endif
755 timevar_pop (TV_TREE_CLEANUP_CFG);
757 if (changed && current_loops)
758 loops_state_set (LOOPS_NEED_FIXUP);
760 return changed;
763 /* Repairs loop structures. */
765 static void
766 repair_loop_structures (void)
768 bitmap changed_bbs;
769 unsigned n_new_loops;
771 calculate_dominance_info (CDI_DOMINATORS);
773 timevar_push (TV_REPAIR_LOOPS);
774 changed_bbs = BITMAP_ALLOC (NULL);
775 n_new_loops = fix_loop_structure (changed_bbs);
777 /* This usually does nothing. But sometimes parts of cfg that originally
778 were inside a loop get out of it due to edge removal (since they
779 become unreachable by back edges from latch). Also a former
780 irreducible loop can become reducible - in this case force a full
781 rewrite into loop-closed SSA form. */
782 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
783 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
784 TODO_update_ssa);
786 BITMAP_FREE (changed_bbs);
788 #ifdef ENABLE_CHECKING
789 verify_loop_structure ();
790 #endif
791 scev_reset ();
793 timevar_pop (TV_REPAIR_LOOPS);
796 /* Cleanup cfg and repair loop structures. */
798 bool
799 cleanup_tree_cfg (void)
801 bool changed = cleanup_tree_cfg_noloop ();
803 if (current_loops != NULL
804 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
805 repair_loop_structures ();
807 return changed;
810 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
811 Returns true if successful. */
813 static bool
814 remove_forwarder_block_with_phi (basic_block bb)
816 edge succ = single_succ_edge (bb);
817 basic_block dest = succ->dest;
818 gimple label;
819 basic_block dombb, domdest, dom;
821 /* We check for infinite loops already in tree_forwarder_block_p.
822 However it may happen that the infinite loop is created
823 afterwards due to removal of forwarders. */
824 if (dest == bb)
825 return false;
827 /* If the destination block consists of a nonlocal label, do not
828 merge it. */
829 label = first_stmt (dest);
830 if (label
831 && gimple_code (label) == GIMPLE_LABEL
832 && DECL_NONLOCAL (gimple_label_label (label)))
833 return false;
835 /* Record BB's single pred in case we need to update the father
836 loop's latch information later. */
837 basic_block pred = NULL;
838 if (single_pred_p (bb))
839 pred = single_pred (bb);
841 /* Redirect each incoming edge to BB to DEST. */
842 while (EDGE_COUNT (bb->preds) > 0)
844 edge e = EDGE_PRED (bb, 0), s;
845 gimple_stmt_iterator gsi;
847 s = find_edge (e->src, dest);
848 if (s)
850 /* We already have an edge S from E->src to DEST. If S and
851 E->dest's sole successor edge have the same PHI arguments
852 at DEST, redirect S to DEST. */
853 if (phi_alternatives_equal (dest, s, succ))
855 e = redirect_edge_and_branch (e, dest);
856 redirect_edge_var_map_clear (e);
857 continue;
860 /* PHI arguments are different. Create a forwarder block by
861 splitting E so that we can merge PHI arguments on E to
862 DEST. */
863 e = single_succ_edge (split_edge (e));
866 s = redirect_edge_and_branch (e, dest);
868 /* redirect_edge_and_branch must not create a new edge. */
869 gcc_assert (s == e);
871 /* Add to the PHI nodes at DEST each PHI argument removed at the
872 destination of E. */
873 for (gsi = gsi_start_phis (dest);
874 !gsi_end_p (gsi);
875 gsi_next (&gsi))
877 gimple phi = gsi_stmt (gsi);
878 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
879 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
881 if (TREE_CODE (def) == SSA_NAME)
883 /* If DEF is one of the results of PHI nodes removed during
884 redirection, replace it with the PHI argument that used
885 to be on E. */
886 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
887 size_t length = head ? head->length () : 0;
888 for (size_t i = 0; i < length; i++)
890 edge_var_map *vm = &(*head)[i];
891 tree old_arg = redirect_edge_var_map_result (vm);
892 tree new_arg = redirect_edge_var_map_def (vm);
894 if (def == old_arg)
896 def = new_arg;
897 locus = redirect_edge_var_map_location (vm);
898 break;
903 add_phi_arg (phi, def, s, locus);
906 redirect_edge_var_map_clear (e);
909 /* Update the dominators. */
910 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
911 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
912 if (domdest == bb)
914 /* Shortcut to avoid calling (relatively expensive)
915 nearest_common_dominator unless necessary. */
916 dom = dombb;
918 else
919 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
921 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
923 /* Adjust latch infomation of BB's parent loop as otherwise
924 the cfg hook has a hard time not to kill the loop. */
925 if (current_loops && bb->loop_father->latch == bb)
926 bb->loop_father->latch = pred;
928 /* Remove BB since all of BB's incoming edges have been redirected
929 to DEST. */
930 delete_basic_block (bb);
932 return true;
935 /* This pass merges PHI nodes if one feeds into another. For example,
936 suppose we have the following:
938 goto <bb 9> (<L9>);
940 <L8>:;
941 tem_17 = foo ();
943 # tem_6 = PHI <tem_17(8), tem_23(7)>;
944 <L9>:;
946 # tem_3 = PHI <tem_6(9), tem_2(5)>;
947 <L10>:;
949 Then we merge the first PHI node into the second one like so:
951 goto <bb 9> (<L10>);
953 <L8>:;
954 tem_17 = foo ();
956 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
957 <L10>:;
960 namespace {
962 const pass_data pass_data_merge_phi =
964 GIMPLE_PASS, /* type */
965 "mergephi", /* name */
966 OPTGROUP_NONE, /* optinfo_flags */
967 TV_TREE_MERGE_PHI, /* tv_id */
968 ( PROP_cfg | PROP_ssa ), /* properties_required */
969 0, /* properties_provided */
970 0, /* properties_destroyed */
971 0, /* todo_flags_start */
972 0, /* todo_flags_finish */
975 class pass_merge_phi : public gimple_opt_pass
977 public:
978 pass_merge_phi (gcc::context *ctxt)
979 : gimple_opt_pass (pass_data_merge_phi, ctxt)
982 /* opt_pass methods: */
983 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
984 virtual unsigned int execute (function *);
986 }; // class pass_merge_phi
988 unsigned int
989 pass_merge_phi::execute (function *fun)
991 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
992 basic_block *current = worklist;
993 basic_block bb;
995 calculate_dominance_info (CDI_DOMINATORS);
997 /* Find all PHI nodes that we may be able to merge. */
998 FOR_EACH_BB_FN (bb, fun)
1000 basic_block dest;
1002 /* Look for a forwarder block with PHI nodes. */
1003 if (!tree_forwarder_block_p (bb, true))
1004 continue;
1006 dest = single_succ (bb);
1008 /* We have to feed into another basic block with PHI
1009 nodes. */
1010 if (gimple_seq_empty_p (phi_nodes (dest))
1011 /* We don't want to deal with a basic block with
1012 abnormal edges. */
1013 || bb_has_abnormal_pred (bb))
1014 continue;
1016 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1018 /* If BB does not dominate DEST, then the PHI nodes at
1019 DEST must be the only users of the results of the PHI
1020 nodes at BB. */
1021 *current++ = bb;
1023 else
1025 gimple_stmt_iterator gsi;
1026 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1028 /* BB dominates DEST. There may be many users of the PHI
1029 nodes in BB. However, there is still a trivial case we
1030 can handle. If the result of every PHI in BB is used
1031 only by a PHI in DEST, then we can trivially merge the
1032 PHI nodes from BB into DEST. */
1033 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1034 gsi_next (&gsi))
1036 gimple phi = gsi_stmt (gsi);
1037 tree result = gimple_phi_result (phi);
1038 use_operand_p imm_use;
1039 gimple use_stmt;
1041 /* If the PHI's result is never used, then we can just
1042 ignore it. */
1043 if (has_zero_uses (result))
1044 continue;
1046 /* Get the single use of the result of this PHI node. */
1047 if (!single_imm_use (result, &imm_use, &use_stmt)
1048 || gimple_code (use_stmt) != GIMPLE_PHI
1049 || gimple_bb (use_stmt) != dest
1050 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1051 break;
1054 /* If the loop above iterated through all the PHI nodes
1055 in BB, then we can merge the PHIs from BB into DEST. */
1056 if (gsi_end_p (gsi))
1057 *current++ = bb;
1061 /* Now let's drain WORKLIST. */
1062 bool changed = false;
1063 while (current != worklist)
1065 bb = *--current;
1066 changed |= remove_forwarder_block_with_phi (bb);
1068 free (worklist);
1070 /* Removing forwarder blocks can cause formerly irreducible loops
1071 to become reducible if we merged two entry blocks. */
1072 if (changed
1073 && current_loops)
1074 loops_state_set (LOOPS_NEED_FIXUP);
1076 return 0;
1079 } // anon namespace
1081 gimple_opt_pass *
1082 make_pass_merge_phi (gcc::context *ctxt)
1084 return new pass_merge_phi (ctxt);
1087 /* Pass: cleanup the CFG just before expanding trees to RTL.
1088 This is just a round of label cleanups and case node grouping
1089 because after the tree optimizers have run such cleanups may
1090 be necessary. */
1092 static unsigned int
1093 execute_cleanup_cfg_post_optimizing (void)
1095 unsigned int todo = 0;
1096 if (cleanup_tree_cfg ())
1097 todo |= TODO_update_ssa;
1098 maybe_remove_unreachable_handlers ();
1099 cleanup_dead_labels ();
1100 group_case_labels ();
1101 if ((flag_compare_debug_opt || flag_compare_debug)
1102 && flag_dump_final_insns)
1104 FILE *final_output = fopen (flag_dump_final_insns, "a");
1106 if (!final_output)
1108 error ("could not open final insn dump file %qs: %m",
1109 flag_dump_final_insns);
1110 flag_dump_final_insns = NULL;
1112 else
1114 int save_unnumbered = flag_dump_unnumbered;
1115 int save_noaddr = flag_dump_noaddr;
1117 flag_dump_noaddr = flag_dump_unnumbered = 1;
1118 fprintf (final_output, "\n");
1119 dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
1120 flag_dump_noaddr = save_noaddr;
1121 flag_dump_unnumbered = save_unnumbered;
1122 if (fclose (final_output))
1124 error ("could not close final insn dump file %qs: %m",
1125 flag_dump_final_insns);
1126 flag_dump_final_insns = NULL;
1130 return todo;
1133 namespace {
1135 const pass_data pass_data_cleanup_cfg_post_optimizing =
1137 GIMPLE_PASS, /* type */
1138 "optimized", /* name */
1139 OPTGROUP_NONE, /* optinfo_flags */
1140 TV_TREE_CLEANUP_CFG, /* tv_id */
1141 PROP_cfg, /* properties_required */
1142 0, /* properties_provided */
1143 0, /* properties_destroyed */
1144 0, /* todo_flags_start */
1145 TODO_remove_unused_locals, /* todo_flags_finish */
1148 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1150 public:
1151 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1152 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1155 /* opt_pass methods: */
1156 virtual unsigned int execute (function *)
1158 return execute_cleanup_cfg_post_optimizing ();
1161 }; // class pass_cleanup_cfg_post_optimizing
1163 } // anon namespace
1165 gimple_opt_pass *
1166 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1168 return new pass_cleanup_cfg_post_optimizing (ctxt);