OSDN Git Service

PR middle-end/54017
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfgcleanup.c
1 /* CFG cleanup for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "output.h"
29 #include "diagnostic-core.h"
30 #include "flags.h"
31 #include "function.h"
32 #include "ggc.h"
33 #include "langhooks.h"
34 #include "tree-flow.h"
35 #include "timevar.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
38 #include "except.h"
39 #include "cfgloop.h"
40 #include "cfglayout.h"
41 #include "hashtab.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-scalar-evolution.h"
44
45 /* The set of blocks in that at least one of the following changes happened:
46    -- the statement at the end of the block was changed
47    -- the block was newly created
48    -- the set of the predecessors of the block changed
49    -- the set of the successors of the block changed
50    ??? Maybe we could track these changes separately, since they determine
51        what cleanups it makes sense to try on the block.  */
52 bitmap cfgcleanup_altered_bbs;
53
54 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
55
56 static bool
57 remove_fallthru_edge (VEC(edge,gc) *ev)
58 {
59   edge_iterator ei;
60   edge e;
61
62   FOR_EACH_EDGE (e, ei, ev)
63     if ((e->flags & EDGE_FALLTHRU) != 0)
64       {
65         remove_edge_and_dominated_blocks (e);
66         return true;
67       }
68   return false;
69 }
70
71
72 /* Disconnect an unreachable block in the control expression starting
73    at block BB.  */
74
75 static bool
76 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
77 {
78   edge taken_edge;
79   bool retval = false;
80   gimple stmt = gsi_stmt (gsi);
81   tree val;
82
83   if (!single_succ_p (bb))
84     {
85       edge e;
86       edge_iterator ei;
87       bool warned;
88       location_t loc;
89
90       fold_defer_overflow_warnings ();
91       loc = gimple_location (stmt);
92       switch (gimple_code (stmt))
93         {
94         case GIMPLE_COND:
95           {
96             tree lhs = gimple_cond_lhs (stmt);
97             tree rhs = gimple_cond_rhs (stmt);
98             /* For conditions try harder and lookup single-argument
99                PHI nodes.  Only do so from the same basic-block though
100                as other basic-blocks may be dead already.  */
101             if (TREE_CODE (lhs) == SSA_NAME
102                 && !name_registered_for_update_p (lhs))
103               {
104                 gimple def_stmt = SSA_NAME_DEF_STMT (lhs);
105                 if (gimple_code (def_stmt) == GIMPLE_PHI
106                     && gimple_phi_num_args (def_stmt) == 1
107                     && gimple_bb (def_stmt) == gimple_bb (stmt)
108                     && (TREE_CODE (PHI_ARG_DEF (def_stmt, 0)) != SSA_NAME
109                         || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt,
110                                                                        0))))
111                   lhs = PHI_ARG_DEF (def_stmt, 0);
112               }
113             if (TREE_CODE (rhs) == SSA_NAME
114                 && !name_registered_for_update_p (rhs))
115               {
116                 gimple def_stmt = SSA_NAME_DEF_STMT (rhs);
117                 if (gimple_code (def_stmt) == GIMPLE_PHI
118                     && gimple_phi_num_args (def_stmt) == 1
119                     && gimple_bb (def_stmt) == gimple_bb (stmt)
120                     && (TREE_CODE (PHI_ARG_DEF (def_stmt, 0)) != SSA_NAME
121                         || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt,
122                                                                        0))))
123                   rhs = PHI_ARG_DEF (def_stmt, 0);
124               }
125             val = fold_binary_loc (loc, gimple_cond_code (stmt),
126                                    boolean_type_node, lhs, rhs);
127             break;
128           }
129
130         case GIMPLE_SWITCH:
131           val = gimple_switch_index (stmt);
132           break;
133
134         default:
135           val = NULL_TREE;
136         }
137       taken_edge = find_taken_edge (bb, val);
138       if (!taken_edge)
139         {
140           fold_undefer_and_ignore_overflow_warnings ();
141           return false;
142         }
143
144       /* Remove all the edges except the one that is always executed.  */
145       warned = false;
146       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
147         {
148           if (e != taken_edge)
149             {
150               if (!warned)
151                 {
152                   fold_undefer_overflow_warnings
153                     (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
154                   warned = true;
155                 }
156
157               taken_edge->probability += e->probability;
158               taken_edge->count += e->count;
159               remove_edge_and_dominated_blocks (e);
160               retval = true;
161             }
162           else
163             ei_next (&ei);
164         }
165       if (!warned)
166         fold_undefer_and_ignore_overflow_warnings ();
167       if (taken_edge->probability > REG_BR_PROB_BASE)
168         taken_edge->probability = REG_BR_PROB_BASE;
169     }
170   else
171     taken_edge = single_succ_edge (bb);
172
173   bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
174   gsi_remove (&gsi, true);
175   taken_edge->flags = EDGE_FALLTHRU;
176
177   return retval;
178 }
179
180 /* Try to remove superfluous control structures in basic block BB.  Returns
181    true if anything changes.  */
182
183 static bool
184 cleanup_control_flow_bb (basic_block bb)
185 {
186   gimple_stmt_iterator gsi;
187   bool retval = false;
188   gimple stmt;
189
190   /* If the last statement of the block could throw and now cannot,
191      we need to prune cfg.  */
192   retval |= gimple_purge_dead_eh_edges (bb);
193
194   gsi = gsi_last_bb (bb);
195   if (gsi_end_p (gsi))
196     return retval;
197
198   stmt = gsi_stmt (gsi);
199
200   if (gimple_code (stmt) == GIMPLE_COND
201       || gimple_code (stmt) == GIMPLE_SWITCH)
202     retval |= cleanup_control_expr_graph (bb, gsi);
203   else if (gimple_code (stmt) == GIMPLE_GOTO
204            && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
205            && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
206                == LABEL_DECL))
207     {
208       /* If we had a computed goto which has a compile-time determinable
209          destination, then we can eliminate the goto.  */
210       edge e;
211       tree label;
212       edge_iterator ei;
213       basic_block target_block;
214
215       /* First look at all the outgoing edges.  Delete any outgoing
216          edges which do not go to the right block.  For the one
217          edge which goes to the right block, fix up its flags.  */
218       label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
219       target_block = label_to_block (label);
220       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
221         {
222           if (e->dest != target_block)
223             remove_edge_and_dominated_blocks (e);
224           else
225             {
226               /* Turn off the EDGE_ABNORMAL flag.  */
227               e->flags &= ~EDGE_ABNORMAL;
228
229               /* And set EDGE_FALLTHRU.  */
230               e->flags |= EDGE_FALLTHRU;
231               ei_next (&ei);
232             }
233         }
234
235       bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
236       bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
237
238       /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
239          relevant information we need.  */
240       gsi_remove (&gsi, true);
241       retval = true;
242     }
243
244   /* Check for indirect calls that have been turned into
245      noreturn calls.  */
246   else if (is_gimple_call (stmt)
247            && gimple_call_noreturn_p (stmt)
248            && remove_fallthru_edge (bb->succs))
249     retval = true;
250
251   return retval;
252 }
253
254 /* Return true if basic block BB does nothing except pass control
255    flow to another block and that we can safely insert a label at
256    the start of the successor block.
257
258    As a precondition, we require that BB be not equal to
259    ENTRY_BLOCK_PTR.  */
260
261 static bool
262 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
263 {
264   gimple_stmt_iterator gsi;
265   location_t locus;
266
267   /* BB must have a single outgoing edge.  */
268   if (single_succ_p (bb) != 1
269       /* If PHI_WANTED is false, BB must not have any PHI nodes.
270          Otherwise, BB must have PHI nodes.  */
271       || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
272       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
273       || single_succ (bb) == EXIT_BLOCK_PTR
274       /* Nor should this be an infinite loop.  */
275       || single_succ (bb) == bb
276       /* BB may not have an abnormal outgoing edge.  */
277       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
278     return false;
279
280   gcc_checking_assert (bb != ENTRY_BLOCK_PTR);
281
282   locus = single_succ_edge (bb)->goto_locus;
283
284   /* There should not be an edge coming from entry, or an EH edge.  */
285   {
286     edge_iterator ei;
287     edge e;
288
289     FOR_EACH_EDGE (e, ei, bb->preds)
290       if (e->src == ENTRY_BLOCK_PTR || (e->flags & EDGE_EH))
291         return false;
292       /* If goto_locus of any of the edges differs, prevent removing
293          the forwarder block for -O0.  */
294       else if (optimize == 0 && e->goto_locus != locus)
295         return false;
296   }
297
298   /* Now walk through the statements backward.  We can ignore labels,
299      anything else means this is not a forwarder block.  */
300   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
301     {
302       gimple stmt = gsi_stmt (gsi);
303
304       switch (gimple_code (stmt))
305         {
306         case GIMPLE_LABEL:
307           if (DECL_NONLOCAL (gimple_label_label (stmt)))
308             return false;
309           if (optimize == 0 && gimple_location (stmt) != locus)
310             return false;
311           break;
312
313           /* ??? For now, hope there's a corresponding debug
314              assignment at the destination.  */
315         case GIMPLE_DEBUG:
316           break;
317
318         default:
319           return false;
320         }
321     }
322
323   if (current_loops)
324     {
325       basic_block dest;
326       /* Protect loop latches, headers and preheaders.  */
327       if (bb->loop_father->header == bb)
328         return false;
329       dest = EDGE_SUCC (bb, 0)->dest;
330
331       if (dest->loop_father->header == dest)
332         return false;
333     }
334   return true;
335 }
336
337 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
338    those alternatives are equal in each of the PHI nodes, then return
339    true, else return false.  */
340
341 static bool
342 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
343 {
344   int n1 = e1->dest_idx;
345   int n2 = e2->dest_idx;
346   gimple_stmt_iterator gsi;
347
348   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
349     {
350       gimple phi = gsi_stmt (gsi);
351       tree val1 = gimple_phi_arg_def (phi, n1);
352       tree val2 = gimple_phi_arg_def (phi, n2);
353
354       gcc_assert (val1 != NULL_TREE);
355       gcc_assert (val2 != NULL_TREE);
356
357       if (!operand_equal_for_phi_arg_p (val1, val2))
358         return false;
359     }
360
361   return true;
362 }
363
364 /* Removes forwarder block BB.  Returns false if this failed.  */
365
366 static bool
367 remove_forwarder_block (basic_block bb)
368 {
369   edge succ = single_succ_edge (bb), e, s;
370   basic_block dest = succ->dest;
371   gimple label;
372   edge_iterator ei;
373   gimple_stmt_iterator gsi, gsi_to;
374   bool can_move_debug_stmts;
375
376   /* We check for infinite loops already in tree_forwarder_block_p.
377      However it may happen that the infinite loop is created
378      afterwards due to removal of forwarders.  */
379   if (dest == bb)
380     return false;
381
382   /* If the destination block consists of a nonlocal label or is a
383      EH landing pad, do not merge it.  */
384   label = first_stmt (dest);
385   if (label
386       && gimple_code (label) == GIMPLE_LABEL
387       && (DECL_NONLOCAL (gimple_label_label (label))
388           || EH_LANDING_PAD_NR (gimple_label_label (label)) != 0))
389     return false;
390
391   /* If there is an abnormal edge to basic block BB, but not into
392      dest, problems might occur during removal of the phi node at out
393      of ssa due to overlapping live ranges of registers.
394
395      If there is an abnormal edge in DEST, the problems would occur
396      anyway since cleanup_dead_labels would then merge the labels for
397      two different eh regions, and rest of exception handling code
398      does not like it.
399
400      So if there is an abnormal edge to BB, proceed only if there is
401      no abnormal edge to DEST and there are no phi nodes in DEST.  */
402   if (bb_has_abnormal_pred (bb)
403       && (bb_has_abnormal_pred (dest)
404           || !gimple_seq_empty_p (phi_nodes (dest))))
405     return false;
406
407   /* If there are phi nodes in DEST, and some of the blocks that are
408      predecessors of BB are also predecessors of DEST, check that the
409      phi node arguments match.  */
410   if (!gimple_seq_empty_p (phi_nodes (dest)))
411     {
412       FOR_EACH_EDGE (e, ei, bb->preds)
413         {
414           s = find_edge (e->src, dest);
415           if (!s)
416             continue;
417
418           if (!phi_alternatives_equal (dest, succ, s))
419             return false;
420         }
421     }
422
423   can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
424
425   /* Redirect the edges.  */
426   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
427     {
428       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
429
430       if (e->flags & EDGE_ABNORMAL)
431         {
432           /* If there is an abnormal edge, redirect it anyway, and
433              move the labels to the new block to make it legal.  */
434           s = redirect_edge_succ_nodup (e, dest);
435         }
436       else
437         s = redirect_edge_and_branch (e, dest);
438
439       if (s == e)
440         {
441           /* Create arguments for the phi nodes, since the edge was not
442              here before.  */
443           for (gsi = gsi_start_phis (dest);
444                !gsi_end_p (gsi);
445                gsi_next (&gsi))
446             {
447               gimple phi = gsi_stmt (gsi);
448               source_location l = gimple_phi_arg_location_from_edge (phi, succ);
449               add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s, l);
450             }
451         }
452     }
453
454   /* Move nonlocal labels and computed goto targets as well as user
455      defined labels and labels with an EH landing pad number to the
456      new block, so that the redirection of the abnormal edges works,
457      jump targets end up in a sane place and debug information for
458      labels is retained.  */
459   gsi_to = gsi_start_bb (dest);
460   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
461     {
462       tree decl;
463       label = gsi_stmt (gsi);
464       if (is_gimple_debug (label))
465         break;
466       decl = gimple_label_label (label);
467       if (EH_LANDING_PAD_NR (decl) != 0
468           || DECL_NONLOCAL (decl)
469           || FORCED_LABEL (decl)
470           || !DECL_ARTIFICIAL (decl))
471         {
472           gsi_remove (&gsi, false);
473           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
474         }
475       else
476         gsi_next (&gsi);
477     }
478
479   /* Move debug statements if the destination has a single predecessor.  */
480   if (can_move_debug_stmts)
481     {
482       gsi_to = gsi_after_labels (dest);
483       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
484         {
485           gimple debug = gsi_stmt (gsi);
486           if (!is_gimple_debug (debug))
487             break;
488           gsi_remove (&gsi, false);
489           gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
490         }
491     }
492
493   bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
494
495   /* Update the dominators.  */
496   if (dom_info_available_p (CDI_DOMINATORS))
497     {
498       basic_block dom, dombb, domdest;
499
500       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
501       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
502       if (domdest == bb)
503         {
504           /* Shortcut to avoid calling (relatively expensive)
505              nearest_common_dominator unless necessary.  */
506           dom = dombb;
507         }
508       else
509         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
510
511       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
512     }
513
514   /* And kill the forwarder block.  */
515   delete_basic_block (bb);
516
517   return true;
518 }
519
520 /* STMT is a call that has been discovered noreturn.  Fixup the CFG
521    and remove LHS.  Return true if something changed.  */
522
523 bool
524 fixup_noreturn_call (gimple stmt)
525 {
526   basic_block bb = gimple_bb (stmt);
527   bool changed = false;
528
529   if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
530     return false;
531
532   /* First split basic block if stmt is not last.  */
533   if (stmt != gsi_stmt (gsi_last_bb (bb)))
534     split_block (bb, stmt);
535
536   changed |= remove_fallthru_edge (bb->succs);
537
538   /* If there is LHS, remove it.  */
539   if (gimple_call_lhs (stmt))
540     {
541       tree op = gimple_call_lhs (stmt);
542       gimple_call_set_lhs (stmt, NULL_TREE);
543
544       /* We need to remove SSA name to avoid checking errors.
545          All uses are dominated by the noreturn and thus will
546          be removed afterwards.
547          We proactively remove affected non-PHI statements to avoid
548          fixup_cfg from trying to update them and crashing.  */
549       if (TREE_CODE (op) == SSA_NAME)
550         {
551           use_operand_p use_p;
552           imm_use_iterator iter;
553           gimple use_stmt;
554           bitmap_iterator bi;
555           unsigned int bb_index;
556
557           bitmap blocks = BITMAP_ALLOC (NULL);
558
559           FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
560             {
561               if (gimple_code (use_stmt) != GIMPLE_PHI)
562                 bitmap_set_bit (blocks, gimple_bb (use_stmt)->index);
563               else
564                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
565                   SET_USE (use_p, error_mark_node);
566             }
567           EXECUTE_IF_SET_IN_BITMAP (blocks, 0, bb_index, bi)
568             delete_basic_block (BASIC_BLOCK (bb_index));
569           BITMAP_FREE (blocks);
570           release_ssa_name (op);
571         }
572       update_stmt (stmt);
573       changed = true;
574     }
575   /* Similarly remove VDEF if there is any.  */
576   else if (gimple_vdef (stmt))
577     update_stmt (stmt);
578   return changed;
579 }
580
581
582 /* Split basic blocks on calls in the middle of a basic block that are now
583    known not to return, and remove the unreachable code.  */
584
585 static bool
586 split_bbs_on_noreturn_calls (void)
587 {
588   bool changed = false;
589   gimple stmt;
590   basic_block bb;
591
592   /* Detect cases where a mid-block call is now known not to return.  */
593   if (cfun->gimple_df)
594     while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
595       {
596         stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
597         bb = gimple_bb (stmt);
598         /* BB might be deleted at this point, so verify first
599            BB is present in the cfg.  */
600         if (bb == NULL
601             || bb->index < NUM_FIXED_BLOCKS
602             || bb->index >= last_basic_block
603             || BASIC_BLOCK (bb->index) != bb
604             || !gimple_call_noreturn_p (stmt))
605           continue;
606
607         changed |= fixup_noreturn_call (stmt);
608       }
609
610   return changed;
611 }
612
613 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
614    changes.  */
615
616 static bool
617 cleanup_tree_cfg_bb (basic_block bb)
618 {
619   bool retval = cleanup_control_flow_bb (bb);
620
621   if (tree_forwarder_block_p (bb, false)
622       && remove_forwarder_block (bb))
623     return true;
624
625   /* Merging the blocks may create new opportunities for folding
626      conditional branches (due to the elimination of single-valued PHI
627      nodes).  */
628   if (single_succ_p (bb)
629       && can_merge_blocks_p (bb, single_succ (bb)))
630     {
631       merge_blocks (bb, single_succ (bb));
632       return true;
633     }
634
635   return retval;
636 }
637
638 /* Iterate the cfg cleanups, while anything changes.  */
639
640 static bool
641 cleanup_tree_cfg_1 (void)
642 {
643   bool retval = false;
644   basic_block bb;
645   unsigned i, n;
646
647   retval |= split_bbs_on_noreturn_calls ();
648
649   /* Prepare the worklists of altered blocks.  */
650   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
651
652   /* During forwarder block cleanup, we may redirect edges out of
653      SWITCH_EXPRs, which can get expensive.  So we want to enable
654      recording of edge to CASE_LABEL_EXPR.  */
655   start_recording_case_labels ();
656
657   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB,
658      since the basic blocks may get removed.  */
659   n = last_basic_block;
660   for (i = NUM_FIXED_BLOCKS; i < n; i++)
661     {
662       bb = BASIC_BLOCK (i);
663       if (bb)
664         retval |= cleanup_tree_cfg_bb (bb);
665     }
666
667   /* Now process the altered blocks, as long as any are available.  */
668   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
669     {
670       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
671       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
672       if (i < NUM_FIXED_BLOCKS)
673         continue;
674
675       bb = BASIC_BLOCK (i);
676       if (!bb)
677         continue;
678
679       retval |= cleanup_tree_cfg_bb (bb);
680
681       /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
682          calls.  */
683       retval |= split_bbs_on_noreturn_calls ();
684     }
685
686   end_recording_case_labels ();
687   BITMAP_FREE (cfgcleanup_altered_bbs);
688   return retval;
689 }
690
691
692 /* Remove unreachable blocks and other miscellaneous clean up work.
693    Return true if the flowgraph was modified, false otherwise.  */
694
695 static bool
696 cleanup_tree_cfg_noloop (void)
697 {
698   bool changed;
699
700   timevar_push (TV_TREE_CLEANUP_CFG);
701
702   /* Iterate until there are no more cleanups left to do.  If any
703      iteration changed the flowgraph, set CHANGED to true.
704
705      If dominance information is available, there cannot be any unreachable
706      blocks.  */
707   if (!dom_info_available_p (CDI_DOMINATORS))
708     {
709       changed = delete_unreachable_blocks ();
710       calculate_dominance_info (CDI_DOMINATORS);
711     }
712   else
713     {
714 #ifdef ENABLE_CHECKING
715       verify_dominators (CDI_DOMINATORS);
716 #endif
717       changed = false;
718     }
719
720   changed |= cleanup_tree_cfg_1 ();
721
722   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
723   compact_blocks ();
724
725 #ifdef ENABLE_CHECKING
726   verify_flow_info ();
727 #endif
728
729   timevar_pop (TV_TREE_CLEANUP_CFG);
730
731   if (changed && current_loops)
732     loops_state_set (LOOPS_NEED_FIXUP);
733
734   return changed;
735 }
736
737 /* Repairs loop structures.  */
738
739 static void
740 repair_loop_structures (void)
741 {
742   bitmap changed_bbs;
743
744   timevar_push (TV_REPAIR_LOOPS);
745   changed_bbs = BITMAP_ALLOC (NULL);
746   fix_loop_structure (changed_bbs);
747
748   /* This usually does nothing.  But sometimes parts of cfg that originally
749      were inside a loop get out of it due to edge removal (since they
750      become unreachable by back edges from latch).  */
751   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
752     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
753
754   BITMAP_FREE (changed_bbs);
755
756 #ifdef ENABLE_CHECKING
757   verify_loop_structure ();
758 #endif
759   scev_reset ();
760
761   loops_state_clear (LOOPS_NEED_FIXUP);
762   timevar_pop (TV_REPAIR_LOOPS);
763 }
764
765 /* Cleanup cfg and repair loop structures.  */
766
767 bool
768 cleanup_tree_cfg (void)
769 {
770   bool changed = cleanup_tree_cfg_noloop ();
771
772   if (current_loops != NULL
773       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
774     repair_loop_structures ();
775
776   return changed;
777 }
778
779 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
780
781 static void
782 remove_forwarder_block_with_phi (basic_block bb)
783 {
784   edge succ = single_succ_edge (bb);
785   basic_block dest = succ->dest;
786   gimple label;
787   basic_block dombb, domdest, dom;
788
789   /* We check for infinite loops already in tree_forwarder_block_p.
790      However it may happen that the infinite loop is created
791      afterwards due to removal of forwarders.  */
792   if (dest == bb)
793     return;
794
795   /* If the destination block consists of a nonlocal label, do not
796      merge it.  */
797   label = first_stmt (dest);
798   if (label
799       && gimple_code (label) == GIMPLE_LABEL
800       && DECL_NONLOCAL (gimple_label_label (label)))
801     return;
802
803   /* Redirect each incoming edge to BB to DEST.  */
804   while (EDGE_COUNT (bb->preds) > 0)
805     {
806       edge e = EDGE_PRED (bb, 0), s;
807       gimple_stmt_iterator gsi;
808
809       s = find_edge (e->src, dest);
810       if (s)
811         {
812           /* We already have an edge S from E->src to DEST.  If S and
813              E->dest's sole successor edge have the same PHI arguments
814              at DEST, redirect S to DEST.  */
815           if (phi_alternatives_equal (dest, s, succ))
816             {
817               e = redirect_edge_and_branch (e, dest);
818               redirect_edge_var_map_clear (e);
819               continue;
820             }
821
822           /* PHI arguments are different.  Create a forwarder block by
823              splitting E so that we can merge PHI arguments on E to
824              DEST.  */
825           e = single_succ_edge (split_edge (e));
826         }
827
828       s = redirect_edge_and_branch (e, dest);
829
830       /* redirect_edge_and_branch must not create a new edge.  */
831       gcc_assert (s == e);
832
833       /* Add to the PHI nodes at DEST each PHI argument removed at the
834          destination of E.  */
835       for (gsi = gsi_start_phis (dest);
836            !gsi_end_p (gsi);
837            gsi_next (&gsi))
838         {
839           gimple phi = gsi_stmt (gsi);
840           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
841           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
842
843           if (TREE_CODE (def) == SSA_NAME)
844             {
845               edge_var_map_vector head;
846               edge_var_map *vm;
847               size_t i;
848
849               /* If DEF is one of the results of PHI nodes removed during
850                  redirection, replace it with the PHI argument that used
851                  to be on E.  */
852               head = redirect_edge_var_map_vector (e);
853               FOR_EACH_VEC_ELT (edge_var_map, head, i, vm)
854                 {
855                   tree old_arg = redirect_edge_var_map_result (vm);
856                   tree new_arg = redirect_edge_var_map_def (vm);
857
858                   if (def == old_arg)
859                     {
860                       def = new_arg;
861                       locus = redirect_edge_var_map_location (vm);
862                       break;
863                     }
864                 }
865             }
866
867           add_phi_arg (phi, def, s, locus);
868         }
869
870       redirect_edge_var_map_clear (e);
871     }
872
873   /* Update the dominators.  */
874   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
875   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
876   if (domdest == bb)
877     {
878       /* Shortcut to avoid calling (relatively expensive)
879          nearest_common_dominator unless necessary.  */
880       dom = dombb;
881     }
882   else
883     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
884
885   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
886
887   /* Remove BB since all of BB's incoming edges have been redirected
888      to DEST.  */
889   delete_basic_block (bb);
890 }
891
892 /* This pass merges PHI nodes if one feeds into another.  For example,
893    suppose we have the following:
894
895   goto <bb 9> (<L9>);
896
897 <L8>:;
898   tem_17 = foo ();
899
900   # tem_6 = PHI <tem_17(8), tem_23(7)>;
901 <L9>:;
902
903   # tem_3 = PHI <tem_6(9), tem_2(5)>;
904 <L10>:;
905
906   Then we merge the first PHI node into the second one like so:
907
908   goto <bb 9> (<L10>);
909
910 <L8>:;
911   tem_17 = foo ();
912
913   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
914 <L10>:;
915 */
916
917 static unsigned int
918 merge_phi_nodes (void)
919 {
920   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
921   basic_block *current = worklist;
922   basic_block bb;
923
924   calculate_dominance_info (CDI_DOMINATORS);
925
926   /* Find all PHI nodes that we may be able to merge.  */
927   FOR_EACH_BB (bb)
928     {
929       basic_block dest;
930
931       /* Look for a forwarder block with PHI nodes.  */
932       if (!tree_forwarder_block_p (bb, true))
933         continue;
934
935       dest = single_succ (bb);
936
937       /* We have to feed into another basic block with PHI
938          nodes.  */
939       if (gimple_seq_empty_p (phi_nodes (dest))
940           /* We don't want to deal with a basic block with
941              abnormal edges.  */
942           || bb_has_abnormal_pred (bb))
943         continue;
944
945       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
946         {
947           /* If BB does not dominate DEST, then the PHI nodes at
948              DEST must be the only users of the results of the PHI
949              nodes at BB.  */
950           *current++ = bb;
951         }
952       else
953         {
954           gimple_stmt_iterator gsi;
955           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
956
957           /* BB dominates DEST.  There may be many users of the PHI
958              nodes in BB.  However, there is still a trivial case we
959              can handle.  If the result of every PHI in BB is used
960              only by a PHI in DEST, then we can trivially merge the
961              PHI nodes from BB into DEST.  */
962           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
963                gsi_next (&gsi))
964             {
965               gimple phi = gsi_stmt (gsi);
966               tree result = gimple_phi_result (phi);
967               use_operand_p imm_use;
968               gimple use_stmt;
969
970               /* If the PHI's result is never used, then we can just
971                  ignore it.  */
972               if (has_zero_uses (result))
973                 continue;
974
975               /* Get the single use of the result of this PHI node.  */
976               if (!single_imm_use (result, &imm_use, &use_stmt)
977                   || gimple_code (use_stmt) != GIMPLE_PHI
978                   || gimple_bb (use_stmt) != dest
979                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
980                 break;
981             }
982
983           /* If the loop above iterated through all the PHI nodes
984              in BB, then we can merge the PHIs from BB into DEST.  */
985           if (gsi_end_p (gsi))
986             *current++ = bb;
987         }
988     }
989
990   /* Now let's drain WORKLIST.  */
991   while (current != worklist)
992     {
993       bb = *--current;
994       remove_forwarder_block_with_phi (bb);
995     }
996
997   free (worklist);
998   return 0;
999 }
1000
1001 static bool
1002 gate_merge_phi (void)
1003 {
1004   return 1;
1005 }
1006
1007 struct gimple_opt_pass pass_merge_phi =
1008 {
1009  {
1010   GIMPLE_PASS,
1011   "mergephi",                   /* name */
1012   gate_merge_phi,               /* gate */
1013   merge_phi_nodes,              /* execute */
1014   NULL,                         /* sub */
1015   NULL,                         /* next */
1016   0,                            /* static_pass_number */
1017   TV_TREE_MERGE_PHI,            /* tv_id */
1018   PROP_cfg | PROP_ssa,          /* properties_required */
1019   0,                            /* properties_provided */
1020   0,                            /* properties_destroyed */
1021   0,                            /* todo_flags_start */
1022   TODO_ggc_collect              /* todo_flags_finish */
1023   | TODO_verify_ssa
1024  }
1025 };