* config/pa/linux-atomic.c (__kernel_cmpxchg): Reorder arguments to
[official-gcc.git] / gcc / tree-cfgcleanup.c
blob07e2d7465b005c21be42f25ac680667fac3b47aa
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2015 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 "alias.h"
25 #include "symtab.h"
26 #include "tree.h"
27 #include "fold-const.h"
28 #include "tm_p.h"
29 #include "predict.h"
30 #include "hard-reg-set.h"
31 #include "function.h"
32 #include "dominance.h"
33 #include "cfg.h"
34 #include "cfganal.h"
35 #include "cfgcleanup.h"
36 #include "basic-block.h"
37 #include "diagnostic-core.h"
38 #include "flags.h"
39 #include "langhooks.h"
40 #include "tree-ssa-alias.h"
41 #include "internal-fn.h"
42 #include "tree-eh.h"
43 #include "gimple-expr.h"
44 #include "gimple.h"
45 #include "gimplify.h"
46 #include "gimple-iterator.h"
47 #include "gimple-ssa.h"
48 #include "tree-cfg.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-ssa-loop-manip.h"
54 #include "rtl.h"
55 #include "insn-config.h"
56 #include "expmed.h"
57 #include "dojump.h"
58 #include "explow.h"
59 #include "calls.h"
60 #include "emit-rtl.h"
61 #include "varasm.h"
62 #include "stmt.h"
63 #include "expr.h"
64 #include "tree-dfa.h"
65 #include "tree-ssa.h"
66 #include "tree-pass.h"
67 #include "except.h"
68 #include "cfgloop.h"
69 #include "tree-ssa-propagate.h"
70 #include "tree-scalar-evolution.h"
72 /* The set of blocks in that at least one of the following changes happened:
73 -- the statement at the end of the block was changed
74 -- the block was newly created
75 -- the set of the predecessors of the block changed
76 -- the set of the successors of the block changed
77 ??? Maybe we could track these changes separately, since they determine
78 what cleanups it makes sense to try on the block. */
79 bitmap cfgcleanup_altered_bbs;
81 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
83 static bool
84 remove_fallthru_edge (vec<edge, va_gc> *ev)
86 edge_iterator ei;
87 edge e;
89 FOR_EACH_EDGE (e, ei, ev)
90 if ((e->flags & EDGE_FALLTHRU) != 0)
92 if (e->flags & EDGE_COMPLEX)
93 e->flags &= ~EDGE_FALLTHRU;
94 else
95 remove_edge_and_dominated_blocks (e);
96 return true;
98 return false;
102 /* Disconnect an unreachable block in the control expression starting
103 at block BB. */
105 static bool
106 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
108 edge taken_edge;
109 bool retval = false;
110 gimple stmt = gsi_stmt (gsi);
111 tree val;
113 if (!single_succ_p (bb))
115 edge e;
116 edge_iterator ei;
117 bool warned;
118 location_t loc;
120 fold_defer_overflow_warnings ();
121 loc = gimple_location (stmt);
122 switch (gimple_code (stmt))
124 case GIMPLE_COND:
125 val = fold_binary_loc (loc, gimple_cond_code (stmt),
126 boolean_type_node,
127 gimple_cond_lhs (stmt),
128 gimple_cond_rhs (stmt));
129 break;
131 case GIMPLE_SWITCH:
132 val = gimple_switch_index (as_a <gswitch *> (stmt));
133 break;
135 default:
136 val = NULL_TREE;
138 taken_edge = find_taken_edge (bb, val);
139 if (!taken_edge)
141 fold_undefer_and_ignore_overflow_warnings ();
142 return false;
145 /* Remove all the edges except the one that is always executed. */
146 warned = false;
147 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
149 if (e != taken_edge)
151 if (!warned)
153 fold_undefer_overflow_warnings
154 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
155 warned = true;
158 taken_edge->probability += e->probability;
159 taken_edge->count += e->count;
160 remove_edge_and_dominated_blocks (e);
161 retval = true;
163 else
164 ei_next (&ei);
166 if (!warned)
167 fold_undefer_and_ignore_overflow_warnings ();
168 if (taken_edge->probability > REG_BR_PROB_BASE)
169 taken_edge->probability = REG_BR_PROB_BASE;
171 else
172 taken_edge = single_succ_edge (bb);
174 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
175 gsi_remove (&gsi, true);
176 taken_edge->flags = EDGE_FALLTHRU;
178 return retval;
181 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
182 to updated gimple_call_flags. */
184 static void
185 cleanup_call_ctrl_altering_flag (gimple bb_end)
187 if (!is_gimple_call (bb_end)
188 || !gimple_call_ctrl_altering_p (bb_end))
189 return;
191 int flags = gimple_call_flags (bb_end);
192 if (((flags & (ECF_CONST | ECF_PURE))
193 && !(flags & ECF_LOOPING_CONST_OR_PURE))
194 || (flags & ECF_LEAF))
195 gimple_call_set_ctrl_altering (bb_end, false);
198 /* Try to remove superfluous control structures in basic block BB. Returns
199 true if anything changes. */
201 static bool
202 cleanup_control_flow_bb (basic_block bb)
204 gimple_stmt_iterator gsi;
205 bool retval = false;
206 gimple stmt;
208 /* If the last statement of the block could throw and now cannot,
209 we need to prune cfg. */
210 retval |= gimple_purge_dead_eh_edges (bb);
212 gsi = gsi_last_bb (bb);
213 if (gsi_end_p (gsi))
214 return retval;
216 stmt = gsi_stmt (gsi);
218 /* Try to cleanup ctrl altering flag for call which ends bb. */
219 cleanup_call_ctrl_altering_flag (stmt);
221 if (gimple_code (stmt) == GIMPLE_COND
222 || gimple_code (stmt) == GIMPLE_SWITCH)
223 retval |= cleanup_control_expr_graph (bb, gsi);
224 else if (gimple_code (stmt) == GIMPLE_GOTO
225 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
226 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
227 == LABEL_DECL))
229 /* If we had a computed goto which has a compile-time determinable
230 destination, then we can eliminate the goto. */
231 edge e;
232 tree label;
233 edge_iterator ei;
234 basic_block target_block;
236 /* First look at all the outgoing edges. Delete any outgoing
237 edges which do not go to the right block. For the one
238 edge which goes to the right block, fix up its flags. */
239 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
240 target_block = label_to_block (label);
241 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
243 if (e->dest != target_block)
244 remove_edge_and_dominated_blocks (e);
245 else
247 /* Turn off the EDGE_ABNORMAL flag. */
248 e->flags &= ~EDGE_ABNORMAL;
250 /* And set EDGE_FALLTHRU. */
251 e->flags |= EDGE_FALLTHRU;
252 ei_next (&ei);
256 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
257 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
259 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
260 relevant information we need. */
261 gsi_remove (&gsi, true);
262 retval = true;
265 /* Check for indirect calls that have been turned into
266 noreturn calls. */
267 else if (is_gimple_call (stmt)
268 && gimple_call_noreturn_p (stmt)
269 && remove_fallthru_edge (bb->succs))
270 retval = true;
272 return retval;
275 /* Return true if basic block BB does nothing except pass control
276 flow to another block and that we can safely insert a label at
277 the start of the successor block.
279 As a precondition, we require that BB be not equal to
280 the entry block. */
282 static bool
283 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
285 gimple_stmt_iterator gsi;
286 location_t locus;
288 /* BB must have a single outgoing edge. */
289 if (single_succ_p (bb) != 1
290 /* If PHI_WANTED is false, BB must not have any PHI nodes.
291 Otherwise, BB must have PHI nodes. */
292 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
293 /* BB may not be a predecessor of the exit block. */
294 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
295 /* Nor should this be an infinite loop. */
296 || single_succ (bb) == bb
297 /* BB may not have an abnormal outgoing edge. */
298 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
299 return false;
301 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
303 locus = single_succ_edge (bb)->goto_locus;
305 /* There should not be an edge coming from entry, or an EH edge. */
307 edge_iterator ei;
308 edge e;
310 FOR_EACH_EDGE (e, ei, bb->preds)
311 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
312 return false;
313 /* If goto_locus of any of the edges differs, prevent removing
314 the forwarder block for -O0. */
315 else if (optimize == 0 && e->goto_locus != locus)
316 return false;
319 /* Now walk through the statements backward. We can ignore labels,
320 anything else means this is not a forwarder block. */
321 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
323 gimple stmt = gsi_stmt (gsi);
325 switch (gimple_code (stmt))
327 case GIMPLE_LABEL:
328 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
329 return false;
330 if (optimize == 0 && gimple_location (stmt) != locus)
331 return false;
332 break;
334 /* ??? For now, hope there's a corresponding debug
335 assignment at the destination. */
336 case GIMPLE_DEBUG:
337 break;
339 default:
340 return false;
344 if (current_loops)
346 basic_block dest;
347 /* Protect loop headers. */
348 if (bb->loop_father->header == bb)
349 return false;
351 dest = EDGE_SUCC (bb, 0)->dest;
352 /* Protect loop preheaders and latches if requested. */
353 if (dest->loop_father->header == dest)
355 if (bb->loop_father == dest->loop_father)
357 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
358 return false;
359 /* If bb doesn't have a single predecessor we'd make this
360 loop have multiple latches. Don't do that if that
361 would in turn require disambiguating them. */
362 return (single_pred_p (bb)
363 || loops_state_satisfies_p
364 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
366 else if (bb->loop_father == loop_outer (dest->loop_father))
367 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
368 /* Always preserve other edges into loop headers that are
369 not simple latches or preheaders. */
370 return false;
374 return true;
377 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
378 those alternatives are equal in each of the PHI nodes, then return
379 true, else return false. */
381 static bool
382 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
384 int n1 = e1->dest_idx;
385 int n2 = e2->dest_idx;
386 gphi_iterator gsi;
388 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
390 gphi *phi = gsi.phi ();
391 tree val1 = gimple_phi_arg_def (phi, n1);
392 tree val2 = gimple_phi_arg_def (phi, n2);
394 gcc_assert (val1 != NULL_TREE);
395 gcc_assert (val2 != NULL_TREE);
397 if (!operand_equal_for_phi_arg_p (val1, val2))
398 return false;
401 return true;
404 /* Removes forwarder block BB. Returns false if this failed. */
406 static bool
407 remove_forwarder_block (basic_block bb)
409 edge succ = single_succ_edge (bb), e, s;
410 basic_block dest = succ->dest;
411 gimple label;
412 edge_iterator ei;
413 gimple_stmt_iterator gsi, gsi_to;
414 bool can_move_debug_stmts;
416 /* We check for infinite loops already in tree_forwarder_block_p.
417 However it may happen that the infinite loop is created
418 afterwards due to removal of forwarders. */
419 if (dest == bb)
420 return false;
422 /* If the destination block consists of a nonlocal label or is a
423 EH landing pad, do not merge it. */
424 label = first_stmt (dest);
425 if (label)
426 if (glabel *label_stmt = dyn_cast <glabel *> (label))
427 if (DECL_NONLOCAL (gimple_label_label (label_stmt))
428 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
429 return false;
431 /* If there is an abnormal edge to basic block BB, but not into
432 dest, problems might occur during removal of the phi node at out
433 of ssa due to overlapping live ranges of registers.
435 If there is an abnormal edge in DEST, the problems would occur
436 anyway since cleanup_dead_labels would then merge the labels for
437 two different eh regions, and rest of exception handling code
438 does not like it.
440 So if there is an abnormal edge to BB, proceed only if there is
441 no abnormal edge to DEST and there are no phi nodes in DEST. */
442 if (bb_has_abnormal_pred (bb)
443 && (bb_has_abnormal_pred (dest)
444 || !gimple_seq_empty_p (phi_nodes (dest))))
445 return false;
447 /* If there are phi nodes in DEST, and some of the blocks that are
448 predecessors of BB are also predecessors of DEST, check that the
449 phi node arguments match. */
450 if (!gimple_seq_empty_p (phi_nodes (dest)))
452 FOR_EACH_EDGE (e, ei, bb->preds)
454 s = find_edge (e->src, dest);
455 if (!s)
456 continue;
458 if (!phi_alternatives_equal (dest, succ, s))
459 return false;
463 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
465 basic_block pred = NULL;
466 if (single_pred_p (bb))
467 pred = single_pred (bb);
469 /* Redirect the edges. */
470 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
472 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
474 if (e->flags & EDGE_ABNORMAL)
476 /* If there is an abnormal edge, redirect it anyway, and
477 move the labels to the new block to make it legal. */
478 s = redirect_edge_succ_nodup (e, dest);
480 else
481 s = redirect_edge_and_branch (e, dest);
483 if (s == e)
485 /* Create arguments for the phi nodes, since the edge was not
486 here before. */
487 for (gphi_iterator psi = gsi_start_phis (dest);
488 !gsi_end_p (psi);
489 gsi_next (&psi))
491 gphi *phi = psi.phi ();
492 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
493 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
494 add_phi_arg (phi, unshare_expr (def), s, l);
499 /* Move nonlocal labels and computed goto targets as well as user
500 defined labels and labels with an EH landing pad number to the
501 new block, so that the redirection of the abnormal edges works,
502 jump targets end up in a sane place and debug information for
503 labels is retained. */
504 gsi_to = gsi_start_bb (dest);
505 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
507 tree decl;
508 label = gsi_stmt (gsi);
509 if (is_gimple_debug (label))
510 break;
511 decl = gimple_label_label (as_a <glabel *> (label));
512 if (EH_LANDING_PAD_NR (decl) != 0
513 || DECL_NONLOCAL (decl)
514 || FORCED_LABEL (decl)
515 || !DECL_ARTIFICIAL (decl))
517 gsi_remove (&gsi, false);
518 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
520 else
521 gsi_next (&gsi);
524 /* Move debug statements if the destination has a single predecessor. */
525 if (can_move_debug_stmts)
527 gsi_to = gsi_after_labels (dest);
528 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
530 gimple debug = gsi_stmt (gsi);
531 if (!is_gimple_debug (debug))
532 break;
533 gsi_remove (&gsi, false);
534 gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
538 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
540 /* Update the dominators. */
541 if (dom_info_available_p (CDI_DOMINATORS))
543 basic_block dom, dombb, domdest;
545 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
546 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
547 if (domdest == bb)
549 /* Shortcut to avoid calling (relatively expensive)
550 nearest_common_dominator unless necessary. */
551 dom = dombb;
553 else
554 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
556 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
559 /* Adjust latch infomation of BB's parent loop as otherwise
560 the cfg hook has a hard time not to kill the loop. */
561 if (current_loops && bb->loop_father->latch == bb)
562 bb->loop_father->latch = pred;
564 /* And kill the forwarder block. */
565 delete_basic_block (bb);
567 return true;
570 /* STMT is a call that has been discovered noreturn. Split the
571 block to prepare fixing up the CFG and remove LHS.
572 Return true if cleanup-cfg needs to run. */
574 bool
575 fixup_noreturn_call (gimple stmt)
577 basic_block bb = gimple_bb (stmt);
578 bool changed = false;
580 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
581 return false;
583 /* First split basic block if stmt is not last. */
584 if (stmt != gsi_stmt (gsi_last_bb (bb)))
586 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
588 /* Don't split if there are only debug stmts
589 after stmt, that can result in -fcompare-debug
590 failures. Remove the debug stmts instead,
591 they should be all unreachable anyway. */
592 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
593 for (gsi_next (&gsi); !gsi_end_p (gsi); )
594 gsi_remove (&gsi, true);
596 else
598 split_block (bb, stmt);
599 changed = true;
603 /* If there is an LHS, remove it, but only if its type has fixed size.
604 The LHS will need to be recreated during RTL expansion and creating
605 temporaries of variable-sized types is not supported. */
606 tree lhs = gimple_call_lhs (stmt);
607 if (lhs && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (lhs))) == INTEGER_CST)
609 gimple_call_set_lhs (stmt, NULL_TREE);
611 /* We need to fix up the SSA name to avoid checking errors. */
612 if (TREE_CODE (lhs) == SSA_NAME)
614 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
615 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
616 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
617 set_ssa_default_def (cfun, new_var, lhs);
620 update_stmt (stmt);
623 /* Mark the call as altering control flow. */
624 if (!gimple_call_ctrl_altering_p (stmt))
626 gimple_call_set_ctrl_altering (stmt, true);
627 changed = true;
630 return changed;
634 /* Tries to cleanup cfg in basic block BB. Returns true if anything
635 changes. */
637 static bool
638 cleanup_tree_cfg_bb (basic_block bb)
640 bool retval = cleanup_control_flow_bb (bb);
642 if (tree_forwarder_block_p (bb, false)
643 && remove_forwarder_block (bb))
644 return true;
646 /* Merging the blocks may create new opportunities for folding
647 conditional branches (due to the elimination of single-valued PHI
648 nodes). */
649 if (single_succ_p (bb)
650 && can_merge_blocks_p (bb, single_succ (bb)))
652 /* If there is a merge opportunity with the predecessor
653 do nothing now but wait until we process the predecessor.
654 This happens when we visit BBs in a non-optimal order and
655 avoids quadratic behavior with adjusting stmts BB pointer. */
656 if (single_pred_p (bb)
657 && can_merge_blocks_p (single_pred (bb), bb))
659 else
661 merge_blocks (bb, single_succ (bb));
662 return true;
666 return retval;
669 /* Iterate the cfg cleanups, while anything changes. */
671 static bool
672 cleanup_tree_cfg_1 (void)
674 bool retval = false;
675 basic_block bb;
676 unsigned i, n;
678 /* Prepare the worklists of altered blocks. */
679 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
681 /* During forwarder block cleanup, we may redirect edges out of
682 SWITCH_EXPRs, which can get expensive. So we want to enable
683 recording of edge to CASE_LABEL_EXPR. */
684 start_recording_case_labels ();
686 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
687 since the basic blocks may get removed. */
688 n = last_basic_block_for_fn (cfun);
689 for (i = NUM_FIXED_BLOCKS; i < n; i++)
691 bb = BASIC_BLOCK_FOR_FN (cfun, i);
692 if (bb)
693 retval |= cleanup_tree_cfg_bb (bb);
696 /* Now process the altered blocks, as long as any are available. */
697 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
699 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
700 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
701 if (i < NUM_FIXED_BLOCKS)
702 continue;
704 bb = BASIC_BLOCK_FOR_FN (cfun, i);
705 if (!bb)
706 continue;
708 retval |= cleanup_tree_cfg_bb (bb);
711 end_recording_case_labels ();
712 BITMAP_FREE (cfgcleanup_altered_bbs);
713 return retval;
717 /* Remove unreachable blocks and other miscellaneous clean up work.
718 Return true if the flowgraph was modified, false otherwise. */
720 static bool
721 cleanup_tree_cfg_noloop (void)
723 bool changed;
725 timevar_push (TV_TREE_CLEANUP_CFG);
727 /* Iterate until there are no more cleanups left to do. If any
728 iteration changed the flowgraph, set CHANGED to true.
730 If dominance information is available, there cannot be any unreachable
731 blocks. */
732 if (!dom_info_available_p (CDI_DOMINATORS))
734 changed = delete_unreachable_blocks ();
735 calculate_dominance_info (CDI_DOMINATORS);
737 else
739 #ifdef ENABLE_CHECKING
740 verify_dominators (CDI_DOMINATORS);
741 #endif
742 changed = false;
745 changed |= cleanup_tree_cfg_1 ();
747 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
748 compact_blocks ();
750 #ifdef ENABLE_CHECKING
751 verify_flow_info ();
752 #endif
754 timevar_pop (TV_TREE_CLEANUP_CFG);
756 if (changed && current_loops)
757 loops_state_set (LOOPS_NEED_FIXUP);
759 return changed;
762 /* Repairs loop structures. */
764 static void
765 repair_loop_structures (void)
767 bitmap changed_bbs;
768 unsigned n_new_loops;
770 calculate_dominance_info (CDI_DOMINATORS);
772 timevar_push (TV_REPAIR_LOOPS);
773 changed_bbs = BITMAP_ALLOC (NULL);
774 n_new_loops = fix_loop_structure (changed_bbs);
776 /* This usually does nothing. But sometimes parts of cfg that originally
777 were inside a loop get out of it due to edge removal (since they
778 become unreachable by back edges from latch). Also a former
779 irreducible loop can become reducible - in this case force a full
780 rewrite into loop-closed SSA form. */
781 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
782 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
783 TODO_update_ssa);
785 BITMAP_FREE (changed_bbs);
787 #ifdef ENABLE_CHECKING
788 verify_loop_structure ();
789 #endif
790 scev_reset ();
792 timevar_pop (TV_REPAIR_LOOPS);
795 /* Cleanup cfg and repair loop structures. */
797 bool
798 cleanup_tree_cfg (void)
800 bool changed = cleanup_tree_cfg_noloop ();
802 if (current_loops != NULL
803 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
804 repair_loop_structures ();
806 return changed;
809 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
810 Returns true if successful. */
812 static bool
813 remove_forwarder_block_with_phi (basic_block bb)
815 edge succ = single_succ_edge (bb);
816 basic_block dest = succ->dest;
817 gimple label;
818 basic_block dombb, domdest, dom;
820 /* We check for infinite loops already in tree_forwarder_block_p.
821 However it may happen that the infinite loop is created
822 afterwards due to removal of forwarders. */
823 if (dest == bb)
824 return false;
826 /* If the destination block consists of a nonlocal label, do not
827 merge it. */
828 label = first_stmt (dest);
829 if (label)
830 if (glabel *label_stmt = dyn_cast <glabel *> (label))
831 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
832 return false;
834 /* Record BB's single pred in case we need to update the father
835 loop's latch information later. */
836 basic_block pred = NULL;
837 if (single_pred_p (bb))
838 pred = single_pred (bb);
840 /* Redirect each incoming edge to BB to DEST. */
841 while (EDGE_COUNT (bb->preds) > 0)
843 edge e = EDGE_PRED (bb, 0), s;
844 gphi_iterator gsi;
846 s = find_edge (e->src, dest);
847 if (s)
849 /* We already have an edge S from E->src to DEST. If S and
850 E->dest's sole successor edge have the same PHI arguments
851 at DEST, redirect S to DEST. */
852 if (phi_alternatives_equal (dest, s, succ))
854 e = redirect_edge_and_branch (e, dest);
855 redirect_edge_var_map_clear (e);
856 continue;
859 /* PHI arguments are different. Create a forwarder block by
860 splitting E so that we can merge PHI arguments on E to
861 DEST. */
862 e = single_succ_edge (split_edge (e));
865 s = redirect_edge_and_branch (e, dest);
867 /* redirect_edge_and_branch must not create a new edge. */
868 gcc_assert (s == e);
870 /* Add to the PHI nodes at DEST each PHI argument removed at the
871 destination of E. */
872 for (gsi = gsi_start_phis (dest);
873 !gsi_end_p (gsi);
874 gsi_next (&gsi))
876 gphi *phi = gsi.phi ();
877 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
878 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
880 if (TREE_CODE (def) == SSA_NAME)
882 /* If DEF is one of the results of PHI nodes removed during
883 redirection, replace it with the PHI argument that used
884 to be on E. */
885 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
886 size_t length = head ? head->length () : 0;
887 for (size_t i = 0; i < length; i++)
889 edge_var_map *vm = &(*head)[i];
890 tree old_arg = redirect_edge_var_map_result (vm);
891 tree new_arg = redirect_edge_var_map_def (vm);
893 if (def == old_arg)
895 def = new_arg;
896 locus = redirect_edge_var_map_location (vm);
897 break;
902 add_phi_arg (phi, def, s, locus);
905 redirect_edge_var_map_clear (e);
908 /* Update the dominators. */
909 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
910 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
911 if (domdest == bb)
913 /* Shortcut to avoid calling (relatively expensive)
914 nearest_common_dominator unless necessary. */
915 dom = dombb;
917 else
918 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
920 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
922 /* Adjust latch infomation of BB's parent loop as otherwise
923 the cfg hook has a hard time not to kill the loop. */
924 if (current_loops && bb->loop_father->latch == bb)
925 bb->loop_father->latch = pred;
927 /* Remove BB since all of BB's incoming edges have been redirected
928 to DEST. */
929 delete_basic_block (bb);
931 return true;
934 /* This pass merges PHI nodes if one feeds into another. For example,
935 suppose we have the following:
937 goto <bb 9> (<L9>);
939 <L8>:;
940 tem_17 = foo ();
942 # tem_6 = PHI <tem_17(8), tem_23(7)>;
943 <L9>:;
945 # tem_3 = PHI <tem_6(9), tem_2(5)>;
946 <L10>:;
948 Then we merge the first PHI node into the second one like so:
950 goto <bb 9> (<L10>);
952 <L8>:;
953 tem_17 = foo ();
955 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
956 <L10>:;
959 namespace {
961 const pass_data pass_data_merge_phi =
963 GIMPLE_PASS, /* type */
964 "mergephi", /* name */
965 OPTGROUP_NONE, /* optinfo_flags */
966 TV_TREE_MERGE_PHI, /* tv_id */
967 ( PROP_cfg | PROP_ssa ), /* properties_required */
968 0, /* properties_provided */
969 0, /* properties_destroyed */
970 0, /* todo_flags_start */
971 0, /* todo_flags_finish */
974 class pass_merge_phi : public gimple_opt_pass
976 public:
977 pass_merge_phi (gcc::context *ctxt)
978 : gimple_opt_pass (pass_data_merge_phi, ctxt)
981 /* opt_pass methods: */
982 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
983 virtual unsigned int execute (function *);
985 }; // class pass_merge_phi
987 unsigned int
988 pass_merge_phi::execute (function *fun)
990 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
991 basic_block *current = worklist;
992 basic_block bb;
994 calculate_dominance_info (CDI_DOMINATORS);
996 /* Find all PHI nodes that we may be able to merge. */
997 FOR_EACH_BB_FN (bb, fun)
999 basic_block dest;
1001 /* Look for a forwarder block with PHI nodes. */
1002 if (!tree_forwarder_block_p (bb, true))
1003 continue;
1005 dest = single_succ (bb);
1007 /* We have to feed into another basic block with PHI
1008 nodes. */
1009 if (gimple_seq_empty_p (phi_nodes (dest))
1010 /* We don't want to deal with a basic block with
1011 abnormal edges. */
1012 || bb_has_abnormal_pred (bb))
1013 continue;
1015 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1017 /* If BB does not dominate DEST, then the PHI nodes at
1018 DEST must be the only users of the results of the PHI
1019 nodes at BB. */
1020 *current++ = bb;
1022 else
1024 gphi_iterator gsi;
1025 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1027 /* BB dominates DEST. There may be many users of the PHI
1028 nodes in BB. However, there is still a trivial case we
1029 can handle. If the result of every PHI in BB is used
1030 only by a PHI in DEST, then we can trivially merge the
1031 PHI nodes from BB into DEST. */
1032 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1033 gsi_next (&gsi))
1035 gphi *phi = gsi.phi ();
1036 tree result = gimple_phi_result (phi);
1037 use_operand_p imm_use;
1038 gimple use_stmt;
1040 /* If the PHI's result is never used, then we can just
1041 ignore it. */
1042 if (has_zero_uses (result))
1043 continue;
1045 /* Get the single use of the result of this PHI node. */
1046 if (!single_imm_use (result, &imm_use, &use_stmt)
1047 || gimple_code (use_stmt) != GIMPLE_PHI
1048 || gimple_bb (use_stmt) != dest
1049 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1050 break;
1053 /* If the loop above iterated through all the PHI nodes
1054 in BB, then we can merge the PHIs from BB into DEST. */
1055 if (gsi_end_p (gsi))
1056 *current++ = bb;
1060 /* Now let's drain WORKLIST. */
1061 bool changed = false;
1062 while (current != worklist)
1064 bb = *--current;
1065 changed |= remove_forwarder_block_with_phi (bb);
1067 free (worklist);
1069 /* Removing forwarder blocks can cause formerly irreducible loops
1070 to become reducible if we merged two entry blocks. */
1071 if (changed
1072 && current_loops)
1073 loops_state_set (LOOPS_NEED_FIXUP);
1075 return 0;
1078 } // anon namespace
1080 gimple_opt_pass *
1081 make_pass_merge_phi (gcc::context *ctxt)
1083 return new pass_merge_phi (ctxt);
1086 /* Pass: cleanup the CFG just before expanding trees to RTL.
1087 This is just a round of label cleanups and case node grouping
1088 because after the tree optimizers have run such cleanups may
1089 be necessary. */
1091 static unsigned int
1092 execute_cleanup_cfg_post_optimizing (void)
1094 unsigned int todo = execute_fixup_cfg ();
1095 if (cleanup_tree_cfg ())
1097 todo &= ~TODO_cleanup_cfg;
1098 todo |= TODO_update_ssa;
1100 maybe_remove_unreachable_handlers ();
1101 cleanup_dead_labels ();
1102 group_case_labels ();
1103 if ((flag_compare_debug_opt || flag_compare_debug)
1104 && flag_dump_final_insns)
1106 FILE *final_output = fopen (flag_dump_final_insns, "a");
1108 if (!final_output)
1110 error ("could not open final insn dump file %qs: %m",
1111 flag_dump_final_insns);
1112 flag_dump_final_insns = NULL;
1114 else
1116 int save_unnumbered = flag_dump_unnumbered;
1117 int save_noaddr = flag_dump_noaddr;
1119 flag_dump_noaddr = flag_dump_unnumbered = 1;
1120 fprintf (final_output, "\n");
1121 dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
1122 flag_dump_noaddr = save_noaddr;
1123 flag_dump_unnumbered = save_unnumbered;
1124 if (fclose (final_output))
1126 error ("could not close final insn dump file %qs: %m",
1127 flag_dump_final_insns);
1128 flag_dump_final_insns = NULL;
1132 return todo;
1135 namespace {
1137 const pass_data pass_data_cleanup_cfg_post_optimizing =
1139 GIMPLE_PASS, /* type */
1140 "optimized", /* name */
1141 OPTGROUP_NONE, /* optinfo_flags */
1142 TV_TREE_CLEANUP_CFG, /* tv_id */
1143 PROP_cfg, /* properties_required */
1144 0, /* properties_provided */
1145 0, /* properties_destroyed */
1146 0, /* todo_flags_start */
1147 TODO_remove_unused_locals, /* todo_flags_finish */
1150 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1152 public:
1153 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1154 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1157 /* opt_pass methods: */
1158 virtual unsigned int execute (function *)
1160 return execute_cleanup_cfg_post_optimizing ();
1163 }; // class pass_cleanup_cfg_post_optimizing
1165 } // anon namespace
1167 gimple_opt_pass *
1168 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1170 return new pass_cleanup_cfg_post_optimizing (ctxt);