* sv.po: Update.
[official-gcc.git] / gcc / tree-cfgcleanup.c
blob46d0fa3ee0dd8f52f0185e98e8c0df2392a125bf
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2016 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 "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "cfghooks.h"
28 #include "tree-pass.h"
29 #include "ssa.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "cfganal.h"
33 #include "cfgcleanup.h"
34 #include "tree-eh.h"
35 #include "gimplify.h"
36 #include "gimple-iterator.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop-manip.h"
39 #include "tree-dfa.h"
40 #include "tree-ssa.h"
41 #include "cfgloop.h"
42 #include "tree-scalar-evolution.h"
43 #include "gimple-match.h"
44 #include "gimple-fold.h"
47 /* The set of blocks in that at least one of the following changes happened:
48 -- the statement at the end of the block was changed
49 -- the block was newly created
50 -- the set of the predecessors of the block changed
51 -- the set of the successors of the block changed
52 ??? Maybe we could track these changes separately, since they determine
53 what cleanups it makes sense to try on the block. */
54 bitmap cfgcleanup_altered_bbs;
56 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
58 static bool
59 remove_fallthru_edge (vec<edge, va_gc> *ev)
61 edge_iterator ei;
62 edge e;
64 FOR_EACH_EDGE (e, ei, ev)
65 if ((e->flags & EDGE_FALLTHRU) != 0)
67 if (e->flags & EDGE_COMPLEX)
68 e->flags &= ~EDGE_FALLTHRU;
69 else
70 remove_edge_and_dominated_blocks (e);
71 return true;
73 return false;
77 /* Disconnect an unreachable block in the control expression starting
78 at block BB. */
80 static bool
81 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi,
82 bool first_p)
84 edge taken_edge;
85 bool retval = false;
86 gimple *stmt = gsi_stmt (gsi);
88 if (!single_succ_p (bb))
90 edge e;
91 edge_iterator ei;
92 bool warned;
93 tree val = NULL_TREE;
95 fold_defer_overflow_warnings ();
96 switch (gimple_code (stmt))
98 case GIMPLE_COND:
99 /* During a first iteration on the CFG only remove trivially
100 dead edges but mark other conditions for re-evaluation. */
101 if (first_p)
103 val = const_binop (gimple_cond_code (stmt), boolean_type_node,
104 gimple_cond_lhs (stmt),
105 gimple_cond_rhs (stmt));
106 if (! val)
107 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
109 else
111 code_helper rcode;
112 tree ops[3] = {};
113 if (gimple_simplify (stmt, &rcode, ops, NULL, no_follow_ssa_edges,
114 no_follow_ssa_edges)
115 && rcode == INTEGER_CST)
116 val = ops[0];
118 break;
120 case GIMPLE_SWITCH:
121 val = gimple_switch_index (as_a <gswitch *> (stmt));
122 break;
124 default:
127 taken_edge = find_taken_edge (bb, val);
128 if (!taken_edge)
130 fold_undefer_and_ignore_overflow_warnings ();
131 return false;
134 /* Remove all the edges except the one that is always executed. */
135 warned = false;
136 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
138 if (e != taken_edge)
140 if (!warned)
142 fold_undefer_overflow_warnings
143 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
144 warned = true;
147 taken_edge->probability += e->probability;
148 taken_edge->count += e->count;
149 remove_edge_and_dominated_blocks (e);
150 retval = true;
152 else
153 ei_next (&ei);
155 if (!warned)
156 fold_undefer_and_ignore_overflow_warnings ();
157 if (taken_edge->probability > REG_BR_PROB_BASE)
158 taken_edge->probability = REG_BR_PROB_BASE;
160 else
161 taken_edge = single_succ_edge (bb);
163 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
164 gsi_remove (&gsi, true);
165 taken_edge->flags = EDGE_FALLTHRU;
167 return retval;
170 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
171 to updated gimple_call_flags. */
173 static void
174 cleanup_call_ctrl_altering_flag (gimple *bb_end)
176 if (!is_gimple_call (bb_end)
177 || !gimple_call_ctrl_altering_p (bb_end))
178 return;
180 int flags = gimple_call_flags (bb_end);
181 if (((flags & (ECF_CONST | ECF_PURE))
182 && !(flags & ECF_LOOPING_CONST_OR_PURE))
183 || (flags & ECF_LEAF))
184 gimple_call_set_ctrl_altering (bb_end, false);
187 /* Try to remove superfluous control structures in basic block BB. Returns
188 true if anything changes. */
190 static bool
191 cleanup_control_flow_bb (basic_block bb, bool first_p)
193 gimple_stmt_iterator gsi;
194 bool retval = false;
195 gimple *stmt;
197 /* If the last statement of the block could throw and now cannot,
198 we need to prune cfg. */
199 retval |= gimple_purge_dead_eh_edges (bb);
201 gsi = gsi_last_nondebug_bb (bb);
202 if (gsi_end_p (gsi))
203 return retval;
205 stmt = gsi_stmt (gsi);
207 /* Try to cleanup ctrl altering flag for call which ends bb. */
208 cleanup_call_ctrl_altering_flag (stmt);
210 if (gimple_code (stmt) == GIMPLE_COND
211 || gimple_code (stmt) == GIMPLE_SWITCH)
213 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
214 retval |= cleanup_control_expr_graph (bb, gsi, first_p);
216 else if (gimple_code (stmt) == GIMPLE_GOTO
217 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
218 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
219 == LABEL_DECL))
221 /* If we had a computed goto which has a compile-time determinable
222 destination, then we can eliminate the goto. */
223 edge e;
224 tree label;
225 edge_iterator ei;
226 basic_block target_block;
228 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
229 /* First look at all the outgoing edges. Delete any outgoing
230 edges which do not go to the right block. For the one
231 edge which goes to the right block, fix up its flags. */
232 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
233 target_block = label_to_block (label);
234 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
236 if (e->dest != target_block)
237 remove_edge_and_dominated_blocks (e);
238 else
240 /* Turn off the EDGE_ABNORMAL flag. */
241 e->flags &= ~EDGE_ABNORMAL;
243 /* And set EDGE_FALLTHRU. */
244 e->flags |= EDGE_FALLTHRU;
245 ei_next (&ei);
249 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
250 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
252 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
253 relevant information we need. */
254 gsi_remove (&gsi, true);
255 retval = true;
258 /* Check for indirect calls that have been turned into
259 noreturn calls. */
260 else if (is_gimple_call (stmt)
261 && gimple_call_noreturn_p (stmt))
263 /* If there are debug stmts after the noreturn call, remove them
264 now, they should be all unreachable anyway. */
265 for (gsi_next (&gsi); !gsi_end_p (gsi); )
266 gsi_remove (&gsi, true);
267 if (remove_fallthru_edge (bb->succs))
268 retval = true;
271 return retval;
274 /* Return true if basic block BB does nothing except pass control
275 flow to another block and that we can safely insert a label at
276 the start of the successor block.
278 As a precondition, we require that BB be not equal to
279 the entry block. */
281 static bool
282 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
284 gimple_stmt_iterator gsi;
285 location_t locus;
287 /* BB must have a single outgoing edge. */
288 if (single_succ_p (bb) != 1
289 /* If PHI_WANTED is false, BB must not have any PHI nodes.
290 Otherwise, BB must have PHI nodes. */
291 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
292 /* BB may not be a predecessor of the exit block. */
293 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
294 /* Nor should this be an infinite loop. */
295 || single_succ (bb) == bb
296 /* BB may not have an abnormal outgoing edge. */
297 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
298 return false;
300 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
302 locus = single_succ_edge (bb)->goto_locus;
304 /* There should not be an edge coming from entry, or an EH edge. */
306 edge_iterator ei;
307 edge e;
309 FOR_EACH_EDGE (e, ei, bb->preds)
310 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
311 return false;
312 /* If goto_locus of any of the edges differs, prevent removing
313 the forwarder block for -O0. */
314 else if (optimize == 0 && e->goto_locus != locus)
315 return false;
318 /* Now walk through the statements backward. We can ignore labels,
319 anything else means this is not a forwarder block. */
320 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
322 gimple *stmt = gsi_stmt (gsi);
324 switch (gimple_code (stmt))
326 case GIMPLE_LABEL:
327 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
328 return false;
329 if (optimize == 0 && gimple_location (stmt) != locus)
330 return false;
331 break;
333 /* ??? For now, hope there's a corresponding debug
334 assignment at the destination. */
335 case GIMPLE_DEBUG:
336 break;
338 default:
339 return false;
343 if (current_loops)
345 basic_block dest;
346 /* Protect loop headers. */
347 if (bb->loop_father->header == bb)
348 return false;
350 dest = EDGE_SUCC (bb, 0)->dest;
351 /* Protect loop preheaders and latches if requested. */
352 if (dest->loop_father->header == dest)
354 if (bb->loop_father == dest->loop_father)
356 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
357 return false;
358 /* If bb doesn't have a single predecessor we'd make this
359 loop have multiple latches. Don't do that if that
360 would in turn require disambiguating them. */
361 return (single_pred_p (bb)
362 || loops_state_satisfies_p
363 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
365 else if (bb->loop_father == loop_outer (dest->loop_father))
366 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
367 /* Always preserve other edges into loop headers that are
368 not simple latches or preheaders. */
369 return false;
373 return true;
376 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
377 those alternatives are equal in each of the PHI nodes, then return
378 true, else return false. */
380 static bool
381 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
383 int n1 = e1->dest_idx;
384 int n2 = e2->dest_idx;
385 gphi_iterator gsi;
387 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
389 gphi *phi = gsi.phi ();
390 tree val1 = gimple_phi_arg_def (phi, n1);
391 tree val2 = gimple_phi_arg_def (phi, n2);
393 gcc_assert (val1 != NULL_TREE);
394 gcc_assert (val2 != NULL_TREE);
396 if (!operand_equal_for_phi_arg_p (val1, val2))
397 return false;
400 return true;
403 /* Removes forwarder block BB. Returns false if this failed. */
405 static bool
406 remove_forwarder_block (basic_block bb)
408 edge succ = single_succ_edge (bb), e, s;
409 basic_block dest = succ->dest;
410 gimple *label;
411 edge_iterator ei;
412 gimple_stmt_iterator gsi, gsi_to;
413 bool can_move_debug_stmts;
415 /* We check for infinite loops already in tree_forwarder_block_p.
416 However it may happen that the infinite loop is created
417 afterwards due to removal of forwarders. */
418 if (dest == bb)
419 return false;
421 /* If the destination block consists of a nonlocal label or is a
422 EH landing pad, do not merge it. */
423 label = first_stmt (dest);
424 if (label)
425 if (glabel *label_stmt = dyn_cast <glabel *> (label))
426 if (DECL_NONLOCAL (gimple_label_label (label_stmt))
427 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
428 return false;
430 /* If there is an abnormal edge to basic block BB, but not into
431 dest, problems might occur during removal of the phi node at out
432 of ssa due to overlapping live ranges of registers.
434 If there is an abnormal edge in DEST, the problems would occur
435 anyway since cleanup_dead_labels would then merge the labels for
436 two different eh regions, and rest of exception handling code
437 does not like it.
439 So if there is an abnormal edge to BB, proceed only if there is
440 no abnormal edge to DEST and there are no phi nodes in DEST. */
441 if (bb_has_abnormal_pred (bb)
442 && (bb_has_abnormal_pred (dest)
443 || !gimple_seq_empty_p (phi_nodes (dest))))
444 return false;
446 /* If there are phi nodes in DEST, and some of the blocks that are
447 predecessors of BB are also predecessors of DEST, check that the
448 phi node arguments match. */
449 if (!gimple_seq_empty_p (phi_nodes (dest)))
451 FOR_EACH_EDGE (e, ei, bb->preds)
453 s = find_edge (e->src, dest);
454 if (!s)
455 continue;
457 if (!phi_alternatives_equal (dest, succ, s))
458 return false;
462 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
464 basic_block pred = NULL;
465 if (single_pred_p (bb))
466 pred = single_pred (bb);
468 /* Redirect the edges. */
469 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
471 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
473 if (e->flags & EDGE_ABNORMAL)
475 /* If there is an abnormal edge, redirect it anyway, and
476 move the labels to the new block to make it legal. */
477 s = redirect_edge_succ_nodup (e, dest);
479 else
480 s = redirect_edge_and_branch (e, dest);
482 if (s == e)
484 /* Create arguments for the phi nodes, since the edge was not
485 here before. */
486 for (gphi_iterator psi = gsi_start_phis (dest);
487 !gsi_end_p (psi);
488 gsi_next (&psi))
490 gphi *phi = psi.phi ();
491 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
492 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
493 add_phi_arg (phi, unshare_expr (def), s, l);
498 /* Move nonlocal labels and computed goto targets as well as user
499 defined labels and labels with an EH landing pad number to the
500 new block, so that the redirection of the abnormal edges works,
501 jump targets end up in a sane place and debug information for
502 labels is retained. */
503 gsi_to = gsi_start_bb (dest);
504 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
506 tree decl;
507 label = gsi_stmt (gsi);
508 if (is_gimple_debug (label))
509 break;
510 decl = gimple_label_label (as_a <glabel *> (label));
511 if (EH_LANDING_PAD_NR (decl) != 0
512 || DECL_NONLOCAL (decl)
513 || FORCED_LABEL (decl)
514 || !DECL_ARTIFICIAL (decl))
516 gsi_remove (&gsi, false);
517 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
519 else
520 gsi_next (&gsi);
523 /* Move debug statements if the destination has a single predecessor. */
524 if (can_move_debug_stmts)
526 gsi_to = gsi_after_labels (dest);
527 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
529 gimple *debug = gsi_stmt (gsi);
530 if (!is_gimple_debug (debug))
531 break;
532 gsi_remove (&gsi, false);
533 gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
537 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
539 /* Update the dominators. */
540 if (dom_info_available_p (CDI_DOMINATORS))
542 basic_block dom, dombb, domdest;
544 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
545 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
546 if (domdest == bb)
548 /* Shortcut to avoid calling (relatively expensive)
549 nearest_common_dominator unless necessary. */
550 dom = dombb;
552 else
553 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
555 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
558 /* Adjust latch infomation of BB's parent loop as otherwise
559 the cfg hook has a hard time not to kill the loop. */
560 if (current_loops && bb->loop_father->latch == bb)
561 bb->loop_father->latch = pred;
563 /* And kill the forwarder block. */
564 delete_basic_block (bb);
566 return true;
569 /* STMT is a call that has been discovered noreturn. Split the
570 block to prepare fixing up the CFG and remove LHS.
571 Return true if cleanup-cfg needs to run. */
573 bool
574 fixup_noreturn_call (gimple *stmt)
576 basic_block bb = gimple_bb (stmt);
577 bool changed = false;
579 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
580 return false;
582 /* First split basic block if stmt is not last. */
583 if (stmt != gsi_stmt (gsi_last_bb (bb)))
585 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
587 /* Don't split if there are only debug stmts
588 after stmt, that can result in -fcompare-debug
589 failures. Remove the debug stmts instead,
590 they should be all unreachable anyway. */
591 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
592 for (gsi_next (&gsi); !gsi_end_p (gsi); )
593 gsi_remove (&gsi, true);
595 else
597 split_block (bb, stmt);
598 changed = true;
602 /* If there is an LHS, remove it, but only if its type has fixed size.
603 The LHS will need to be recreated during RTL expansion and creating
604 temporaries of variable-sized types is not supported. Also don't
605 do this with TREE_ADDRESSABLE types, as assign_temp will abort. */
606 tree lhs = gimple_call_lhs (stmt);
607 if (lhs && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (lhs))) == INTEGER_CST
608 && !TREE_ADDRESSABLE (TREE_TYPE (lhs)))
610 gimple_call_set_lhs (stmt, NULL_TREE);
612 /* We need to fix up the SSA name to avoid checking errors. */
613 if (TREE_CODE (lhs) == SSA_NAME)
615 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
616 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
617 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
618 set_ssa_default_def (cfun, new_var, lhs);
621 update_stmt (stmt);
624 /* Mark the call as altering control flow. */
625 if (!gimple_call_ctrl_altering_p (stmt))
627 gimple_call_set_ctrl_altering (stmt, true);
628 changed = true;
631 return changed;
635 /* Tries to cleanup cfg in basic block BB. Returns true if anything
636 changes. */
638 static bool
639 cleanup_tree_cfg_bb (basic_block bb)
641 if (tree_forwarder_block_p (bb, false)
642 && remove_forwarder_block (bb))
643 return true;
645 /* Merging the blocks may create new opportunities for folding
646 conditional branches (due to the elimination of single-valued PHI
647 nodes). */
648 if (single_succ_p (bb)
649 && can_merge_blocks_p (bb, single_succ (bb)))
651 /* If there is a merge opportunity with the predecessor
652 do nothing now but wait until we process the predecessor.
653 This happens when we visit BBs in a non-optimal order and
654 avoids quadratic behavior with adjusting stmts BB pointer. */
655 if (single_pred_p (bb)
656 && can_merge_blocks_p (single_pred (bb), bb))
658 else
660 merge_blocks (bb, single_succ (bb));
661 return true;
665 return false;
668 /* Iterate the cfg cleanups, while anything changes. */
670 static bool
671 cleanup_tree_cfg_1 (void)
673 bool retval = false;
674 basic_block bb;
675 unsigned i, n;
677 /* Prepare the worklists of altered blocks. */
678 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
680 /* During forwarder block cleanup, we may redirect edges out of
681 SWITCH_EXPRs, which can get expensive. So we want to enable
682 recording of edge to CASE_LABEL_EXPR. */
683 start_recording_case_labels ();
685 /* We cannot use FOR_EACH_BB_FN for the BB iterations below
686 since the basic blocks may get removed. */
688 /* Start by iterating over all basic blocks looking for edge removal
689 opportunities. Do this first because incoming SSA form may be
690 invalid and we want to avoid performing SSA related tasks such
691 as propgating out a PHI node during BB merging in that state. */
692 n = last_basic_block_for_fn (cfun);
693 for (i = NUM_FIXED_BLOCKS; i < n; i++)
695 bb = BASIC_BLOCK_FOR_FN (cfun, i);
696 if (bb)
697 retval |= cleanup_control_flow_bb (bb, true);
700 /* After doing the above SSA form should be valid (or an update SSA
701 should be required). */
703 /* Continue by iterating over all basic blocks looking for BB merging
704 opportunities. */
705 n = last_basic_block_for_fn (cfun);
706 for (i = NUM_FIXED_BLOCKS; i < n; i++)
708 bb = BASIC_BLOCK_FOR_FN (cfun, i);
709 if (bb)
710 retval |= cleanup_tree_cfg_bb (bb);
713 /* Now process the altered blocks, as long as any are available. */
714 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
716 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
717 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
718 if (i < NUM_FIXED_BLOCKS)
719 continue;
721 bb = BASIC_BLOCK_FOR_FN (cfun, i);
722 if (!bb)
723 continue;
725 retval |= cleanup_control_flow_bb (bb, false);
726 retval |= cleanup_tree_cfg_bb (bb);
729 end_recording_case_labels ();
730 BITMAP_FREE (cfgcleanup_altered_bbs);
731 return retval;
735 /* Remove unreachable blocks and other miscellaneous clean up work.
736 Return true if the flowgraph was modified, false otherwise. */
738 static bool
739 cleanup_tree_cfg_noloop (void)
741 bool changed;
743 timevar_push (TV_TREE_CLEANUP_CFG);
745 /* Iterate until there are no more cleanups left to do. If any
746 iteration changed the flowgraph, set CHANGED to true.
748 If dominance information is available, there cannot be any unreachable
749 blocks. */
750 if (!dom_info_available_p (CDI_DOMINATORS))
752 changed = delete_unreachable_blocks ();
753 calculate_dominance_info (CDI_DOMINATORS);
755 else
757 checking_verify_dominators (CDI_DOMINATORS);
758 changed = false;
761 changed |= cleanup_tree_cfg_1 ();
763 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
764 compact_blocks ();
766 checking_verify_flow_info ();
768 timevar_pop (TV_TREE_CLEANUP_CFG);
770 if (changed && current_loops)
771 loops_state_set (LOOPS_NEED_FIXUP);
773 return changed;
776 /* Repairs loop structures. */
778 static void
779 repair_loop_structures (void)
781 bitmap changed_bbs;
782 unsigned n_new_loops;
784 calculate_dominance_info (CDI_DOMINATORS);
786 timevar_push (TV_REPAIR_LOOPS);
787 changed_bbs = BITMAP_ALLOC (NULL);
788 n_new_loops = fix_loop_structure (changed_bbs);
790 /* This usually does nothing. But sometimes parts of cfg that originally
791 were inside a loop get out of it due to edge removal (since they
792 become unreachable by back edges from latch). Also a former
793 irreducible loop can become reducible - in this case force a full
794 rewrite into loop-closed SSA form. */
795 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
796 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
797 TODO_update_ssa);
799 BITMAP_FREE (changed_bbs);
801 checking_verify_loop_structure ();
802 scev_reset ();
804 timevar_pop (TV_REPAIR_LOOPS);
807 /* Cleanup cfg and repair loop structures. */
809 bool
810 cleanup_tree_cfg (void)
812 bool changed = cleanup_tree_cfg_noloop ();
814 if (current_loops != NULL
815 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
816 repair_loop_structures ();
818 return changed;
821 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
822 Returns true if successful. */
824 static bool
825 remove_forwarder_block_with_phi (basic_block bb)
827 edge succ = single_succ_edge (bb);
828 basic_block dest = succ->dest;
829 gimple *label;
830 basic_block dombb, domdest, dom;
832 /* We check for infinite loops already in tree_forwarder_block_p.
833 However it may happen that the infinite loop is created
834 afterwards due to removal of forwarders. */
835 if (dest == bb)
836 return false;
838 /* If the destination block consists of a nonlocal label, do not
839 merge it. */
840 label = first_stmt (dest);
841 if (label)
842 if (glabel *label_stmt = dyn_cast <glabel *> (label))
843 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
844 return false;
846 /* Record BB's single pred in case we need to update the father
847 loop's latch information later. */
848 basic_block pred = NULL;
849 if (single_pred_p (bb))
850 pred = single_pred (bb);
852 /* Redirect each incoming edge to BB to DEST. */
853 while (EDGE_COUNT (bb->preds) > 0)
855 edge e = EDGE_PRED (bb, 0), s;
856 gphi_iterator gsi;
858 s = find_edge (e->src, dest);
859 if (s)
861 /* We already have an edge S from E->src to DEST. If S and
862 E->dest's sole successor edge have the same PHI arguments
863 at DEST, redirect S to DEST. */
864 if (phi_alternatives_equal (dest, s, succ))
866 e = redirect_edge_and_branch (e, dest);
867 redirect_edge_var_map_clear (e);
868 continue;
871 /* PHI arguments are different. Create a forwarder block by
872 splitting E so that we can merge PHI arguments on E to
873 DEST. */
874 e = single_succ_edge (split_edge (e));
877 s = redirect_edge_and_branch (e, dest);
879 /* redirect_edge_and_branch must not create a new edge. */
880 gcc_assert (s == e);
882 /* Add to the PHI nodes at DEST each PHI argument removed at the
883 destination of E. */
884 for (gsi = gsi_start_phis (dest);
885 !gsi_end_p (gsi);
886 gsi_next (&gsi))
888 gphi *phi = gsi.phi ();
889 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
890 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
892 if (TREE_CODE (def) == SSA_NAME)
894 /* If DEF is one of the results of PHI nodes removed during
895 redirection, replace it with the PHI argument that used
896 to be on E. */
897 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
898 size_t length = head ? head->length () : 0;
899 for (size_t i = 0; i < length; i++)
901 edge_var_map *vm = &(*head)[i];
902 tree old_arg = redirect_edge_var_map_result (vm);
903 tree new_arg = redirect_edge_var_map_def (vm);
905 if (def == old_arg)
907 def = new_arg;
908 locus = redirect_edge_var_map_location (vm);
909 break;
914 add_phi_arg (phi, def, s, locus);
917 redirect_edge_var_map_clear (e);
920 /* Update the dominators. */
921 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
922 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
923 if (domdest == bb)
925 /* Shortcut to avoid calling (relatively expensive)
926 nearest_common_dominator unless necessary. */
927 dom = dombb;
929 else
930 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
932 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
934 /* Adjust latch infomation of BB's parent loop as otherwise
935 the cfg hook has a hard time not to kill the loop. */
936 if (current_loops && bb->loop_father->latch == bb)
937 bb->loop_father->latch = pred;
939 /* Remove BB since all of BB's incoming edges have been redirected
940 to DEST. */
941 delete_basic_block (bb);
943 return true;
946 /* This pass merges PHI nodes if one feeds into another. For example,
947 suppose we have the following:
949 goto <bb 9> (<L9>);
951 <L8>:;
952 tem_17 = foo ();
954 # tem_6 = PHI <tem_17(8), tem_23(7)>;
955 <L9>:;
957 # tem_3 = PHI <tem_6(9), tem_2(5)>;
958 <L10>:;
960 Then we merge the first PHI node into the second one like so:
962 goto <bb 9> (<L10>);
964 <L8>:;
965 tem_17 = foo ();
967 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
968 <L10>:;
971 namespace {
973 const pass_data pass_data_merge_phi =
975 GIMPLE_PASS, /* type */
976 "mergephi", /* name */
977 OPTGROUP_NONE, /* optinfo_flags */
978 TV_TREE_MERGE_PHI, /* tv_id */
979 ( PROP_cfg | PROP_ssa ), /* properties_required */
980 0, /* properties_provided */
981 0, /* properties_destroyed */
982 0, /* todo_flags_start */
983 0, /* todo_flags_finish */
986 class pass_merge_phi : public gimple_opt_pass
988 public:
989 pass_merge_phi (gcc::context *ctxt)
990 : gimple_opt_pass (pass_data_merge_phi, ctxt)
993 /* opt_pass methods: */
994 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
995 virtual unsigned int execute (function *);
997 }; // class pass_merge_phi
999 unsigned int
1000 pass_merge_phi::execute (function *fun)
1002 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1003 basic_block *current = worklist;
1004 basic_block bb;
1006 calculate_dominance_info (CDI_DOMINATORS);
1008 /* Find all PHI nodes that we may be able to merge. */
1009 FOR_EACH_BB_FN (bb, fun)
1011 basic_block dest;
1013 /* Look for a forwarder block with PHI nodes. */
1014 if (!tree_forwarder_block_p (bb, true))
1015 continue;
1017 dest = single_succ (bb);
1019 /* We have to feed into another basic block with PHI
1020 nodes. */
1021 if (gimple_seq_empty_p (phi_nodes (dest))
1022 /* We don't want to deal with a basic block with
1023 abnormal edges. */
1024 || bb_has_abnormal_pred (bb))
1025 continue;
1027 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1029 /* If BB does not dominate DEST, then the PHI nodes at
1030 DEST must be the only users of the results of the PHI
1031 nodes at BB. */
1032 *current++ = bb;
1034 else
1036 gphi_iterator gsi;
1037 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1039 /* BB dominates DEST. There may be many users of the PHI
1040 nodes in BB. However, there is still a trivial case we
1041 can handle. If the result of every PHI in BB is used
1042 only by a PHI in DEST, then we can trivially merge the
1043 PHI nodes from BB into DEST. */
1044 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1045 gsi_next (&gsi))
1047 gphi *phi = gsi.phi ();
1048 tree result = gimple_phi_result (phi);
1049 use_operand_p imm_use;
1050 gimple *use_stmt;
1052 /* If the PHI's result is never used, then we can just
1053 ignore it. */
1054 if (has_zero_uses (result))
1055 continue;
1057 /* Get the single use of the result of this PHI node. */
1058 if (!single_imm_use (result, &imm_use, &use_stmt)
1059 || gimple_code (use_stmt) != GIMPLE_PHI
1060 || gimple_bb (use_stmt) != dest
1061 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1062 break;
1065 /* If the loop above iterated through all the PHI nodes
1066 in BB, then we can merge the PHIs from BB into DEST. */
1067 if (gsi_end_p (gsi))
1068 *current++ = bb;
1072 /* Now let's drain WORKLIST. */
1073 bool changed = false;
1074 while (current != worklist)
1076 bb = *--current;
1077 changed |= remove_forwarder_block_with_phi (bb);
1079 free (worklist);
1081 /* Removing forwarder blocks can cause formerly irreducible loops
1082 to become reducible if we merged two entry blocks. */
1083 if (changed
1084 && current_loops)
1085 loops_state_set (LOOPS_NEED_FIXUP);
1087 return 0;
1090 } // anon namespace
1092 gimple_opt_pass *
1093 make_pass_merge_phi (gcc::context *ctxt)
1095 return new pass_merge_phi (ctxt);
1098 /* Pass: cleanup the CFG just before expanding trees to RTL.
1099 This is just a round of label cleanups and case node grouping
1100 because after the tree optimizers have run such cleanups may
1101 be necessary. */
1103 static unsigned int
1104 execute_cleanup_cfg_post_optimizing (void)
1106 unsigned int todo = execute_fixup_cfg ();
1107 if (cleanup_tree_cfg ())
1109 todo &= ~TODO_cleanup_cfg;
1110 todo |= TODO_update_ssa;
1112 maybe_remove_unreachable_handlers ();
1113 cleanup_dead_labels ();
1114 group_case_labels ();
1115 if ((flag_compare_debug_opt || flag_compare_debug)
1116 && flag_dump_final_insns)
1118 FILE *final_output = fopen (flag_dump_final_insns, "a");
1120 if (!final_output)
1122 error ("could not open final insn dump file %qs: %m",
1123 flag_dump_final_insns);
1124 flag_dump_final_insns = NULL;
1126 else
1128 int save_unnumbered = flag_dump_unnumbered;
1129 int save_noaddr = flag_dump_noaddr;
1131 flag_dump_noaddr = flag_dump_unnumbered = 1;
1132 fprintf (final_output, "\n");
1133 dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
1134 flag_dump_noaddr = save_noaddr;
1135 flag_dump_unnumbered = save_unnumbered;
1136 if (fclose (final_output))
1138 error ("could not close final insn dump file %qs: %m",
1139 flag_dump_final_insns);
1140 flag_dump_final_insns = NULL;
1144 return todo;
1147 namespace {
1149 const pass_data pass_data_cleanup_cfg_post_optimizing =
1151 GIMPLE_PASS, /* type */
1152 "optimized", /* name */
1153 OPTGROUP_NONE, /* optinfo_flags */
1154 TV_TREE_CLEANUP_CFG, /* tv_id */
1155 PROP_cfg, /* properties_required */
1156 0, /* properties_provided */
1157 0, /* properties_destroyed */
1158 0, /* todo_flags_start */
1159 TODO_remove_unused_locals, /* todo_flags_finish */
1162 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1164 public:
1165 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1166 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1169 /* opt_pass methods: */
1170 virtual unsigned int execute (function *)
1172 return execute_cleanup_cfg_post_optimizing ();
1175 }; // class pass_cleanup_cfg_post_optimizing
1177 } // anon namespace
1179 gimple_opt_pass *
1180 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1182 return new pass_cleanup_cfg_post_optimizing (ctxt);