2013-08-14 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / tree-cfgcleanup.c
blob8917f855705dc43802000702185af8bf816d8c9a
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2013 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 "ggc.h"
31 #include "langhooks.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "except.h"
35 #include "cfgloop.h"
36 #include "hashtab.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-scalar-evolution.h"
40 /* The set of blocks in that at least one of the following changes happened:
41 -- the statement at the end of the block was changed
42 -- the block was newly created
43 -- the set of the predecessors of the block changed
44 -- the set of the successors of the block changed
45 ??? Maybe we could track these changes separately, since they determine
46 what cleanups it makes sense to try on the block. */
47 bitmap cfgcleanup_altered_bbs;
49 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
51 static bool
52 remove_fallthru_edge (vec<edge, va_gc> *ev)
54 edge_iterator ei;
55 edge e;
57 FOR_EACH_EDGE (e, ei, ev)
58 if ((e->flags & EDGE_FALLTHRU) != 0)
60 if (e->flags & EDGE_COMPLEX)
61 e->flags &= ~EDGE_FALLTHRU;
62 else
63 remove_edge_and_dominated_blocks (e);
64 return true;
66 return false;
70 /* Disconnect an unreachable block in the control expression starting
71 at block BB. */
73 static bool
74 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
76 edge taken_edge;
77 bool retval = false;
78 gimple stmt = gsi_stmt (gsi);
79 tree val;
81 if (!single_succ_p (bb))
83 edge e;
84 edge_iterator ei;
85 bool warned;
86 location_t loc;
88 fold_defer_overflow_warnings ();
89 loc = gimple_location (stmt);
90 switch (gimple_code (stmt))
92 case GIMPLE_COND:
93 val = fold_binary_loc (loc, gimple_cond_code (stmt),
94 boolean_type_node,
95 gimple_cond_lhs (stmt),
96 gimple_cond_rhs (stmt));
97 break;
99 case GIMPLE_SWITCH:
100 val = gimple_switch_index (stmt);
101 break;
103 default:
104 val = NULL_TREE;
106 taken_edge = find_taken_edge (bb, val);
107 if (!taken_edge)
109 fold_undefer_and_ignore_overflow_warnings ();
110 return false;
113 /* Remove all the edges except the one that is always executed. */
114 warned = false;
115 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
117 if (e != taken_edge)
119 if (!warned)
121 fold_undefer_overflow_warnings
122 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
123 warned = true;
126 taken_edge->probability += e->probability;
127 taken_edge->count += e->count;
128 remove_edge_and_dominated_blocks (e);
129 retval = true;
131 else
132 ei_next (&ei);
134 if (!warned)
135 fold_undefer_and_ignore_overflow_warnings ();
136 if (taken_edge->probability > REG_BR_PROB_BASE)
137 taken_edge->probability = REG_BR_PROB_BASE;
139 else
140 taken_edge = single_succ_edge (bb);
142 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
143 gsi_remove (&gsi, true);
144 taken_edge->flags = EDGE_FALLTHRU;
146 return retval;
149 /* Try to remove superfluous control structures in basic block BB. Returns
150 true if anything changes. */
152 static bool
153 cleanup_control_flow_bb (basic_block bb)
155 gimple_stmt_iterator gsi;
156 bool retval = false;
157 gimple stmt;
159 /* If the last statement of the block could throw and now cannot,
160 we need to prune cfg. */
161 retval |= gimple_purge_dead_eh_edges (bb);
163 gsi = gsi_last_bb (bb);
164 if (gsi_end_p (gsi))
165 return retval;
167 stmt = gsi_stmt (gsi);
169 if (gimple_code (stmt) == GIMPLE_COND
170 || gimple_code (stmt) == GIMPLE_SWITCH)
171 retval |= cleanup_control_expr_graph (bb, gsi);
172 else if (gimple_code (stmt) == GIMPLE_GOTO
173 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
174 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
175 == LABEL_DECL))
177 /* If we had a computed goto which has a compile-time determinable
178 destination, then we can eliminate the goto. */
179 edge e;
180 tree label;
181 edge_iterator ei;
182 basic_block target_block;
184 /* First look at all the outgoing edges. Delete any outgoing
185 edges which do not go to the right block. For the one
186 edge which goes to the right block, fix up its flags. */
187 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
188 target_block = label_to_block (label);
189 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
191 if (e->dest != target_block)
192 remove_edge_and_dominated_blocks (e);
193 else
195 /* Turn off the EDGE_ABNORMAL flag. */
196 e->flags &= ~EDGE_ABNORMAL;
198 /* And set EDGE_FALLTHRU. */
199 e->flags |= EDGE_FALLTHRU;
200 ei_next (&ei);
204 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
205 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
207 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
208 relevant information we need. */
209 gsi_remove (&gsi, true);
210 retval = true;
213 /* Check for indirect calls that have been turned into
214 noreturn calls. */
215 else if (is_gimple_call (stmt)
216 && gimple_call_noreturn_p (stmt)
217 && remove_fallthru_edge (bb->succs))
218 retval = true;
220 return retval;
223 /* Return true if basic block BB does nothing except pass control
224 flow to another block and that we can safely insert a label at
225 the start of the successor block.
227 As a precondition, we require that BB be not equal to
228 ENTRY_BLOCK_PTR. */
230 static bool
231 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
233 gimple_stmt_iterator gsi;
234 location_t locus;
236 /* BB must have a single outgoing edge. */
237 if (single_succ_p (bb) != 1
238 /* If PHI_WANTED is false, BB must not have any PHI nodes.
239 Otherwise, BB must have PHI nodes. */
240 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
241 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
242 || single_succ (bb) == EXIT_BLOCK_PTR
243 /* Nor should this be an infinite loop. */
244 || single_succ (bb) == bb
245 /* BB may not have an abnormal outgoing edge. */
246 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
247 return false;
249 gcc_checking_assert (bb != ENTRY_BLOCK_PTR);
251 locus = single_succ_edge (bb)->goto_locus;
253 /* There should not be an edge coming from entry, or an EH edge. */
255 edge_iterator ei;
256 edge e;
258 FOR_EACH_EDGE (e, ei, bb->preds)
259 if (e->src == ENTRY_BLOCK_PTR || (e->flags & EDGE_EH))
260 return false;
261 /* If goto_locus of any of the edges differs, prevent removing
262 the forwarder block for -O0. */
263 else if (optimize == 0 && e->goto_locus != locus)
264 return false;
267 /* Now walk through the statements backward. We can ignore labels,
268 anything else means this is not a forwarder block. */
269 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
271 gimple stmt = gsi_stmt (gsi);
273 switch (gimple_code (stmt))
275 case GIMPLE_LABEL:
276 if (DECL_NONLOCAL (gimple_label_label (stmt)))
277 return false;
278 if (optimize == 0 && gimple_location (stmt) != locus)
279 return false;
280 break;
282 /* ??? For now, hope there's a corresponding debug
283 assignment at the destination. */
284 case GIMPLE_DEBUG:
285 break;
287 default:
288 return false;
292 if (current_loops)
294 basic_block dest;
295 /* Protect loop latches, headers and preheaders. */
296 if (bb->loop_father->header == bb)
297 return false;
298 dest = EDGE_SUCC (bb, 0)->dest;
300 if (dest->loop_father->header == dest)
301 return false;
303 return true;
306 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
307 those alternatives are equal in each of the PHI nodes, then return
308 true, else return false. */
310 static bool
311 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
313 int n1 = e1->dest_idx;
314 int n2 = e2->dest_idx;
315 gimple_stmt_iterator gsi;
317 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
319 gimple phi = gsi_stmt (gsi);
320 tree val1 = gimple_phi_arg_def (phi, n1);
321 tree val2 = gimple_phi_arg_def (phi, n2);
323 gcc_assert (val1 != NULL_TREE);
324 gcc_assert (val2 != NULL_TREE);
326 if (!operand_equal_for_phi_arg_p (val1, val2))
327 return false;
330 return true;
333 /* Removes forwarder block BB. Returns false if this failed. */
335 static bool
336 remove_forwarder_block (basic_block bb)
338 edge succ = single_succ_edge (bb), e, s;
339 basic_block dest = succ->dest;
340 gimple label;
341 edge_iterator ei;
342 gimple_stmt_iterator gsi, gsi_to;
343 bool can_move_debug_stmts;
345 /* We check for infinite loops already in tree_forwarder_block_p.
346 However it may happen that the infinite loop is created
347 afterwards due to removal of forwarders. */
348 if (dest == bb)
349 return false;
351 /* If the destination block consists of a nonlocal label or is a
352 EH landing pad, do not merge it. */
353 label = first_stmt (dest);
354 if (label
355 && gimple_code (label) == GIMPLE_LABEL
356 && (DECL_NONLOCAL (gimple_label_label (label))
357 || EH_LANDING_PAD_NR (gimple_label_label (label)) != 0))
358 return false;
360 /* If there is an abnormal edge to basic block BB, but not into
361 dest, problems might occur during removal of the phi node at out
362 of ssa due to overlapping live ranges of registers.
364 If there is an abnormal edge in DEST, the problems would occur
365 anyway since cleanup_dead_labels would then merge the labels for
366 two different eh regions, and rest of exception handling code
367 does not like it.
369 So if there is an abnormal edge to BB, proceed only if there is
370 no abnormal edge to DEST and there are no phi nodes in DEST. */
371 if (bb_has_abnormal_pred (bb)
372 && (bb_has_abnormal_pred (dest)
373 || !gimple_seq_empty_p (phi_nodes (dest))))
374 return false;
376 /* If there are phi nodes in DEST, and some of the blocks that are
377 predecessors of BB are also predecessors of DEST, check that the
378 phi node arguments match. */
379 if (!gimple_seq_empty_p (phi_nodes (dest)))
381 FOR_EACH_EDGE (e, ei, bb->preds)
383 s = find_edge (e->src, dest);
384 if (!s)
385 continue;
387 if (!phi_alternatives_equal (dest, succ, s))
388 return false;
392 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
394 /* Redirect the edges. */
395 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
397 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
399 if (e->flags & EDGE_ABNORMAL)
401 /* If there is an abnormal edge, redirect it anyway, and
402 move the labels to the new block to make it legal. */
403 s = redirect_edge_succ_nodup (e, dest);
405 else
406 s = redirect_edge_and_branch (e, dest);
408 if (s == e)
410 /* Create arguments for the phi nodes, since the edge was not
411 here before. */
412 for (gsi = gsi_start_phis (dest);
413 !gsi_end_p (gsi);
414 gsi_next (&gsi))
416 gimple phi = gsi_stmt (gsi);
417 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
418 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
419 add_phi_arg (phi, unshare_expr (def), s, l);
424 /* Move nonlocal labels and computed goto targets as well as user
425 defined labels and labels with an EH landing pad number to the
426 new block, so that the redirection of the abnormal edges works,
427 jump targets end up in a sane place and debug information for
428 labels is retained. */
429 gsi_to = gsi_start_bb (dest);
430 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
432 tree decl;
433 label = gsi_stmt (gsi);
434 if (is_gimple_debug (label))
435 break;
436 decl = gimple_label_label (label);
437 if (EH_LANDING_PAD_NR (decl) != 0
438 || DECL_NONLOCAL (decl)
439 || FORCED_LABEL (decl)
440 || !DECL_ARTIFICIAL (decl))
442 gsi_remove (&gsi, false);
443 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
445 else
446 gsi_next (&gsi);
449 /* Move debug statements if the destination has a single predecessor. */
450 if (can_move_debug_stmts)
452 gsi_to = gsi_after_labels (dest);
453 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
455 gimple debug = gsi_stmt (gsi);
456 if (!is_gimple_debug (debug))
457 break;
458 gsi_remove (&gsi, false);
459 gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
463 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
465 /* Update the dominators. */
466 if (dom_info_available_p (CDI_DOMINATORS))
468 basic_block dom, dombb, domdest;
470 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
471 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
472 if (domdest == bb)
474 /* Shortcut to avoid calling (relatively expensive)
475 nearest_common_dominator unless necessary. */
476 dom = dombb;
478 else
479 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
481 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
484 /* And kill the forwarder block. */
485 delete_basic_block (bb);
487 return true;
490 /* STMT is a call that has been discovered noreturn. Fixup the CFG
491 and remove LHS. Return true if something changed. */
493 bool
494 fixup_noreturn_call (gimple stmt)
496 basic_block bb = gimple_bb (stmt);
497 bool changed = false;
499 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
500 return false;
502 /* First split basic block if stmt is not last. */
503 if (stmt != gsi_stmt (gsi_last_bb (bb)))
504 split_block (bb, stmt);
506 changed |= remove_fallthru_edge (bb->succs);
508 /* If there is LHS, remove it. */
509 if (gimple_call_lhs (stmt))
511 tree op = gimple_call_lhs (stmt);
512 gimple_call_set_lhs (stmt, NULL_TREE);
514 /* We need to remove SSA name to avoid checking errors.
515 All uses are dominated by the noreturn and thus will
516 be removed afterwards.
517 We proactively remove affected non-PHI statements to avoid
518 fixup_cfg from trying to update them and crashing. */
519 if (TREE_CODE (op) == SSA_NAME)
521 use_operand_p use_p;
522 imm_use_iterator iter;
523 gimple use_stmt;
524 bitmap_iterator bi;
525 unsigned int bb_index;
527 bitmap blocks = BITMAP_ALLOC (NULL);
529 FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
531 if (gimple_code (use_stmt) != GIMPLE_PHI)
532 bitmap_set_bit (blocks, gimple_bb (use_stmt)->index);
533 else
534 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
535 SET_USE (use_p, error_mark_node);
537 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, bb_index, bi)
538 delete_basic_block (BASIC_BLOCK (bb_index));
539 BITMAP_FREE (blocks);
540 release_ssa_name (op);
542 update_stmt (stmt);
543 changed = true;
545 /* Similarly remove VDEF if there is any. */
546 else if (gimple_vdef (stmt))
547 update_stmt (stmt);
548 return changed;
552 /* Split basic blocks on calls in the middle of a basic block that are now
553 known not to return, and remove the unreachable code. */
555 static bool
556 split_bbs_on_noreturn_calls (void)
558 bool changed = false;
559 gimple stmt;
560 basic_block bb;
562 /* Detect cases where a mid-block call is now known not to return. */
563 if (cfun->gimple_df)
564 while (vec_safe_length (MODIFIED_NORETURN_CALLS (cfun)))
566 stmt = MODIFIED_NORETURN_CALLS (cfun)->pop ();
567 bb = gimple_bb (stmt);
568 /* BB might be deleted at this point, so verify first
569 BB is present in the cfg. */
570 if (bb == NULL
571 || bb->index < NUM_FIXED_BLOCKS
572 || bb->index >= last_basic_block
573 || BASIC_BLOCK (bb->index) != bb
574 || !gimple_call_noreturn_p (stmt))
575 continue;
577 changed |= fixup_noreturn_call (stmt);
580 return changed;
583 /* Tries to cleanup cfg in basic block BB. Returns true if anything
584 changes. */
586 static bool
587 cleanup_tree_cfg_bb (basic_block bb)
589 bool retval = cleanup_control_flow_bb (bb);
591 if (tree_forwarder_block_p (bb, false)
592 && remove_forwarder_block (bb))
593 return true;
595 /* Merging the blocks may create new opportunities for folding
596 conditional branches (due to the elimination of single-valued PHI
597 nodes). */
598 if (single_succ_p (bb)
599 && can_merge_blocks_p (bb, single_succ (bb)))
601 merge_blocks (bb, single_succ (bb));
602 return true;
605 return retval;
608 /* Iterate the cfg cleanups, while anything changes. */
610 static bool
611 cleanup_tree_cfg_1 (void)
613 bool retval = false;
614 basic_block bb;
615 unsigned i, n;
617 retval |= split_bbs_on_noreturn_calls ();
619 /* Prepare the worklists of altered blocks. */
620 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
622 /* During forwarder block cleanup, we may redirect edges out of
623 SWITCH_EXPRs, which can get expensive. So we want to enable
624 recording of edge to CASE_LABEL_EXPR. */
625 start_recording_case_labels ();
627 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
628 since the basic blocks may get removed. */
629 n = last_basic_block;
630 for (i = NUM_FIXED_BLOCKS; i < n; i++)
632 bb = BASIC_BLOCK (i);
633 if (bb)
634 retval |= cleanup_tree_cfg_bb (bb);
637 /* Now process the altered blocks, as long as any are available. */
638 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
640 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
641 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
642 if (i < NUM_FIXED_BLOCKS)
643 continue;
645 bb = BASIC_BLOCK (i);
646 if (!bb)
647 continue;
649 retval |= cleanup_tree_cfg_bb (bb);
651 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
652 calls. */
653 retval |= split_bbs_on_noreturn_calls ();
656 end_recording_case_labels ();
657 BITMAP_FREE (cfgcleanup_altered_bbs);
658 return retval;
662 /* Remove unreachable blocks and other miscellaneous clean up work.
663 Return true if the flowgraph was modified, false otherwise. */
665 static bool
666 cleanup_tree_cfg_noloop (void)
668 bool changed;
670 timevar_push (TV_TREE_CLEANUP_CFG);
672 /* Iterate until there are no more cleanups left to do. If any
673 iteration changed the flowgraph, set CHANGED to true.
675 If dominance information is available, there cannot be any unreachable
676 blocks. */
677 if (!dom_info_available_p (CDI_DOMINATORS))
679 changed = delete_unreachable_blocks ();
680 calculate_dominance_info (CDI_DOMINATORS);
682 else
684 #ifdef ENABLE_CHECKING
685 verify_dominators (CDI_DOMINATORS);
686 #endif
687 changed = false;
690 changed |= cleanup_tree_cfg_1 ();
692 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
693 compact_blocks ();
695 #ifdef ENABLE_CHECKING
696 verify_flow_info ();
697 #endif
699 timevar_pop (TV_TREE_CLEANUP_CFG);
701 if (changed && current_loops)
702 loops_state_set (LOOPS_NEED_FIXUP);
704 return changed;
707 /* Repairs loop structures. */
709 static void
710 repair_loop_structures (void)
712 bitmap changed_bbs;
713 unsigned n_new_loops;
715 calculate_dominance_info (CDI_DOMINATORS);
717 timevar_push (TV_REPAIR_LOOPS);
718 changed_bbs = BITMAP_ALLOC (NULL);
719 n_new_loops = fix_loop_structure (changed_bbs);
721 /* This usually does nothing. But sometimes parts of cfg that originally
722 were inside a loop get out of it due to edge removal (since they
723 become unreachable by back edges from latch). Also a former
724 irreducible loop can become reducible - in this case force a full
725 rewrite into loop-closed SSA form. */
726 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
727 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
728 TODO_update_ssa);
730 BITMAP_FREE (changed_bbs);
732 #ifdef ENABLE_CHECKING
733 verify_loop_structure ();
734 #endif
735 scev_reset ();
737 timevar_pop (TV_REPAIR_LOOPS);
740 /* Cleanup cfg and repair loop structures. */
742 bool
743 cleanup_tree_cfg (void)
745 bool changed = cleanup_tree_cfg_noloop ();
747 if (current_loops != NULL
748 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
749 repair_loop_structures ();
751 return changed;
754 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
755 Returns true if successful. */
757 static bool
758 remove_forwarder_block_with_phi (basic_block bb)
760 edge succ = single_succ_edge (bb);
761 basic_block dest = succ->dest;
762 gimple label;
763 basic_block dombb, domdest, dom;
765 /* We check for infinite loops already in tree_forwarder_block_p.
766 However it may happen that the infinite loop is created
767 afterwards due to removal of forwarders. */
768 if (dest == bb)
769 return false;
771 /* If the destination block consists of a nonlocal label, do not
772 merge it. */
773 label = first_stmt (dest);
774 if (label
775 && gimple_code (label) == GIMPLE_LABEL
776 && DECL_NONLOCAL (gimple_label_label (label)))
777 return false;
779 /* Redirect each incoming edge to BB to DEST. */
780 while (EDGE_COUNT (bb->preds) > 0)
782 edge e = EDGE_PRED (bb, 0), s;
783 gimple_stmt_iterator gsi;
785 s = find_edge (e->src, dest);
786 if (s)
788 /* We already have an edge S from E->src to DEST. If S and
789 E->dest's sole successor edge have the same PHI arguments
790 at DEST, redirect S to DEST. */
791 if (phi_alternatives_equal (dest, s, succ))
793 e = redirect_edge_and_branch (e, dest);
794 redirect_edge_var_map_clear (e);
795 continue;
798 /* PHI arguments are different. Create a forwarder block by
799 splitting E so that we can merge PHI arguments on E to
800 DEST. */
801 e = single_succ_edge (split_edge (e));
804 s = redirect_edge_and_branch (e, dest);
806 /* redirect_edge_and_branch must not create a new edge. */
807 gcc_assert (s == e);
809 /* Add to the PHI nodes at DEST each PHI argument removed at the
810 destination of E. */
811 for (gsi = gsi_start_phis (dest);
812 !gsi_end_p (gsi);
813 gsi_next (&gsi))
815 gimple phi = gsi_stmt (gsi);
816 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
817 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
819 if (TREE_CODE (def) == SSA_NAME)
821 edge_var_map_vector *head;
822 edge_var_map *vm;
823 size_t i;
825 /* If DEF is one of the results of PHI nodes removed during
826 redirection, replace it with the PHI argument that used
827 to be on E. */
828 head = redirect_edge_var_map_vector (e);
829 FOR_EACH_VEC_SAFE_ELT (head, i, vm)
831 tree old_arg = redirect_edge_var_map_result (vm);
832 tree new_arg = redirect_edge_var_map_def (vm);
834 if (def == old_arg)
836 def = new_arg;
837 locus = redirect_edge_var_map_location (vm);
838 break;
843 add_phi_arg (phi, def, s, locus);
846 redirect_edge_var_map_clear (e);
849 /* Update the dominators. */
850 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
851 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
852 if (domdest == bb)
854 /* Shortcut to avoid calling (relatively expensive)
855 nearest_common_dominator unless necessary. */
856 dom = dombb;
858 else
859 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
861 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
863 /* Remove BB since all of BB's incoming edges have been redirected
864 to DEST. */
865 delete_basic_block (bb);
867 return true;
870 /* This pass merges PHI nodes if one feeds into another. For example,
871 suppose we have the following:
873 goto <bb 9> (<L9>);
875 <L8>:;
876 tem_17 = foo ();
878 # tem_6 = PHI <tem_17(8), tem_23(7)>;
879 <L9>:;
881 # tem_3 = PHI <tem_6(9), tem_2(5)>;
882 <L10>:;
884 Then we merge the first PHI node into the second one like so:
886 goto <bb 9> (<L10>);
888 <L8>:;
889 tem_17 = foo ();
891 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
892 <L10>:;
895 static unsigned int
896 merge_phi_nodes (void)
898 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
899 basic_block *current = worklist;
900 basic_block bb;
902 calculate_dominance_info (CDI_DOMINATORS);
904 /* Find all PHI nodes that we may be able to merge. */
905 FOR_EACH_BB (bb)
907 basic_block dest;
909 /* Look for a forwarder block with PHI nodes. */
910 if (!tree_forwarder_block_p (bb, true))
911 continue;
913 dest = single_succ (bb);
915 /* We have to feed into another basic block with PHI
916 nodes. */
917 if (gimple_seq_empty_p (phi_nodes (dest))
918 /* We don't want to deal with a basic block with
919 abnormal edges. */
920 || bb_has_abnormal_pred (bb))
921 continue;
923 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
925 /* If BB does not dominate DEST, then the PHI nodes at
926 DEST must be the only users of the results of the PHI
927 nodes at BB. */
928 *current++ = bb;
930 else
932 gimple_stmt_iterator gsi;
933 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
935 /* BB dominates DEST. There may be many users of the PHI
936 nodes in BB. However, there is still a trivial case we
937 can handle. If the result of every PHI in BB is used
938 only by a PHI in DEST, then we can trivially merge the
939 PHI nodes from BB into DEST. */
940 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
941 gsi_next (&gsi))
943 gimple phi = gsi_stmt (gsi);
944 tree result = gimple_phi_result (phi);
945 use_operand_p imm_use;
946 gimple use_stmt;
948 /* If the PHI's result is never used, then we can just
949 ignore it. */
950 if (has_zero_uses (result))
951 continue;
953 /* Get the single use of the result of this PHI node. */
954 if (!single_imm_use (result, &imm_use, &use_stmt)
955 || gimple_code (use_stmt) != GIMPLE_PHI
956 || gimple_bb (use_stmt) != dest
957 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
958 break;
961 /* If the loop above iterated through all the PHI nodes
962 in BB, then we can merge the PHIs from BB into DEST. */
963 if (gsi_end_p (gsi))
964 *current++ = bb;
968 /* Now let's drain WORKLIST. */
969 bool changed = false;
970 while (current != worklist)
972 bb = *--current;
973 changed |= remove_forwarder_block_with_phi (bb);
975 free (worklist);
977 /* Removing forwarder blocks can cause formerly irreducible loops
978 to become reducible if we merged two entry blocks. */
979 if (changed
980 && current_loops)
981 loops_state_set (LOOPS_NEED_FIXUP);
983 return 0;
986 static bool
987 gate_merge_phi (void)
989 return 1;
992 namespace {
994 const pass_data pass_data_merge_phi =
996 GIMPLE_PASS, /* type */
997 "mergephi", /* name */
998 OPTGROUP_NONE, /* optinfo_flags */
999 true, /* has_gate */
1000 true, /* has_execute */
1001 TV_TREE_MERGE_PHI, /* tv_id */
1002 ( PROP_cfg | PROP_ssa ), /* properties_required */
1003 0, /* properties_provided */
1004 0, /* properties_destroyed */
1005 0, /* todo_flags_start */
1006 TODO_verify_ssa, /* todo_flags_finish */
1009 class pass_merge_phi : public gimple_opt_pass
1011 public:
1012 pass_merge_phi(gcc::context *ctxt)
1013 : gimple_opt_pass(pass_data_merge_phi, ctxt)
1016 /* opt_pass methods: */
1017 opt_pass * clone () { return new pass_merge_phi (ctxt_); }
1018 bool gate () { return gate_merge_phi (); }
1019 unsigned int execute () { return merge_phi_nodes (); }
1021 }; // class pass_merge_phi
1023 } // anon namespace
1025 gimple_opt_pass *
1026 make_pass_merge_phi (gcc::context *ctxt)
1028 return new pass_merge_phi (ctxt);