gcc/tree-cfgcleanup.c

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