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