gcc/tree-cfgcleanup.c

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