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_computed[CDI_DOMINATORS])
 613     {
 614       changed = delete_unreachable_blocks ();
 615       calculate_dominance_info (CDI_DOMINATORS);
 616     }
 617   else
 618     changed = false;
 619
 620   changed |= cleanup_tree_cfg_1 ();
 621
 622   gcc_assert (dom_computed[CDI_DOMINATORS]);
 623   compact_blocks ();
 624
 625 #ifdef ENABLE_CHECKING
 626   verify_flow_info ();
 627 #endif
 628
 629   timevar_pop (TV_TREE_CLEANUP_CFG);
 630
 631   return changed;
 632 }
 633
 634 /* Cleanup cfg and repair loop structures.  */
 635
 636 bool
 637 cleanup_tree_cfg_loop (void)
 638 {
 639   bool changed = cleanup_tree_cfg ();
 640
 641   if (changed && current_loops != NULL)
 642     {
 643       bitmap changed_bbs = BITMAP_ALLOC (NULL);
 644       fix_loop_structure (changed_bbs);
 645
 646       /* This usually does nothing.  But sometimes parts of cfg that originally
 647          were inside a loop get out of it due to edge removal (since they
 648          become unreachable by back edges from latch).  */
 649       if ((current_loops->state & LOOP_CLOSED_SSA) != 0)
 650         rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 651
 652       BITMAP_FREE (changed_bbs);
 653
 654 #ifdef ENABLE_CHECKING
 655       verify_loop_structure ();
 656 #endif
 657       scev_reset ();
 658     }
 659   return changed;
 660 }
 661
 662 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 663
 664 static void
 665 remove_forwarder_block_with_phi (basic_block bb)
 666 {
 667   edge succ = single_succ_edge (bb);
 668   basic_block dest = succ->dest;
 669   tree label;
 670   basic_block dombb, domdest, dom;
 671
 672   /* We check for infinite loops already in tree_forwarder_block_p.
 673      However it may happen that the infinite loop is created
 674      afterwards due to removal of forwarders.  */
 675   if (dest == bb)
 676     return;
 677
 678   /* If the destination block consists of a nonlocal label, do not
 679      merge it.  */
 680   label = first_stmt (dest);
 681   if (label
 682       && TREE_CODE (label) == LABEL_EXPR
 683       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
 684     return;
 685
 686   /* Redirect each incoming edge to BB to DEST.  */
 687   while (EDGE_COUNT (bb->preds) > 0)
 688     {
 689       edge e = EDGE_PRED (bb, 0), s;
 690       tree phi;
 691
 692       s = find_edge (e->src, dest);
 693       if (s)
 694         {
 695           /* We already have an edge S from E->src to DEST.  If S and
 696              E->dest's sole successor edge have the same PHI arguments
 697              at DEST, redirect S to DEST.  */
 698           if (phi_alternatives_equal (dest, s, succ))
 699             {
 700               e = redirect_edge_and_branch (e, dest);
 701               PENDING_STMT (e) = NULL_TREE;
 702               continue;
 703             }
 704
 705           /* PHI arguments are different.  Create a forwarder block by
 706              splitting E so that we can merge PHI arguments on E to
 707              DEST.  */
 708           e = single_succ_edge (split_edge (e));
 709         }
 710
 711       s = redirect_edge_and_branch (e, dest);
 712
 713       /* redirect_edge_and_branch must not create a new edge.  */
 714       gcc_assert (s == e);
 715
 716       /* Add to the PHI nodes at DEST each PHI argument removed at the
 717          destination of E.  */
 718       for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 719         {
 720           tree def = PHI_ARG_DEF (phi, succ->dest_idx);
 721
 722           if (TREE_CODE (def) == SSA_NAME)
 723             {
 724               tree var;
 725
 726               /* If DEF is one of the results of PHI nodes removed during
 727                  redirection, replace it with the PHI argument that used
 728                  to be on E.  */
 729               for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
 730                 {
 731                   tree old_arg = TREE_PURPOSE (var);
 732                   tree new_arg = TREE_VALUE (var);
 733
 734                   if (def == old_arg)
 735                     {
 736                       def = new_arg;
 737                       break;
 738                     }
 739                 }
 740             }
 741
 742           add_phi_arg (phi, def, s);
 743         }
 744
 745       PENDING_STMT (e) = NULL;
 746     }
 747
 748   /* Update the dominators.  */
 749   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 750   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 751   if (domdest == bb)
 752     {
 753       /* Shortcut to avoid calling (relatively expensive)
 754          nearest_common_dominator unless necessary.  */
 755       dom = dombb;
 756     }
 757   else
 758     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 759
 760   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 761
 762   /* Remove BB since all of BB's incoming edges have been redirected
 763      to DEST.  */
 764   delete_basic_block (bb);
 765 }
 766
 767 /* This pass merges PHI nodes if one feeds into another.  For example,
 768    suppose we have the following:
 769
 770   goto <bb 9> (<L9>);
 771
 772 <L8>:;
 773   tem_17 = foo ();
 774
 775   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 776 <L9>:;
 777
 778   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 779 <L10>:;
 780
 781   Then we merge the first PHI node into the second one like so:
 782
 783   goto <bb 9> (<L10>);
 784
 785 <L8>:;
 786   tem_17 = foo ();
 787
 788   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 789 <L10>:;
 790 */
 791
 792 static unsigned int
 793 merge_phi_nodes (void)
 794 {
 795   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 796   basic_block *current = worklist;
 797   basic_block bb;
 798
 799   calculate_dominance_info (CDI_DOMINATORS);
 800
 801   /* Find all PHI nodes that we may be able to merge.  */
 802   FOR_EACH_BB (bb)
 803     {
 804       basic_block dest;
 805
 806       /* Look for a forwarder block with PHI nodes.  */
 807       if (!tree_forwarder_block_p (bb, true))
 808         continue;
 809
 810       dest = single_succ (bb);
 811
 812       /* We have to feed into another basic block with PHI
 813          nodes.  */
 814       if (!phi_nodes (dest)
 815           /* We don't want to deal with a basic block with
 816              abnormal edges.  */
 817           || has_abnormal_incoming_edge_p (bb))
 818         continue;
 819
 820       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 821         {
 822           /* If BB does not dominate DEST, then the PHI nodes at
 823              DEST must be the only users of the results of the PHI
 824              nodes at BB.  */
 825           *current++ = bb;
 826         }
 827       else
 828         {
 829           tree phi;
 830           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 831
 832           /* BB dominates DEST.  There may be many users of the PHI
 833              nodes in BB.  However, there is still a trivial case we
 834              can handle.  If the result of every PHI in BB is used
 835              only by a PHI in DEST, then we can trivially merge the
 836              PHI nodes from BB into DEST.  */
 837           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 838             {
 839               tree result = PHI_RESULT (phi);
 840               use_operand_p imm_use;
 841               tree use_stmt;
 842
 843               /* If the PHI's result is never used, then we can just
 844                  ignore it.  */
 845               if (has_zero_uses (result))
 846                 continue;
 847
 848               /* Get the single use of the result of this PHI node.  */
 849               if (!single_imm_use (result, &imm_use, &use_stmt)
 850                   || TREE_CODE (use_stmt) != PHI_NODE
 851                   || bb_for_stmt (use_stmt) != dest
 852                   || PHI_ARG_DEF (use_stmt, dest_idx) != result)
 853                 break;
 854             }
 855
 856           /* If the loop above iterated through all the PHI nodes
 857              in BB, then we can merge the PHIs from BB into DEST.  */
 858           if (!phi)
 859             *current++ = bb;
 860         }
 861     }
 862
 863   /* Now let's drain WORKLIST.  */
 864   while (current != worklist)
 865     {
 866       bb = *--current;
 867       remove_forwarder_block_with_phi (bb);
 868     }
 869
 870   free (worklist);
 871   return 0;
 872 }
 873
 874 static bool
 875 gate_merge_phi (void)
 876 {
 877   return 1;
 878 }
 879
 880 struct tree_opt_pass pass_merge_phi = {
 881   "mergephi",                   /* name */
 882   gate_merge_phi,               /* gate */
 883   merge_phi_nodes,              /* execute */
 884   NULL,                         /* sub */
 885   NULL,                         /* next */
 886   0,                            /* static_pass_number */
 887   TV_TREE_MERGE_PHI,            /* tv_id */
 888   PROP_cfg | PROP_ssa,          /* properties_required */
 889   0,                            /* properties_provided */
 890   0,                            /* properties_destroyed */
 891   0,                            /* todo_flags_start */
 892   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 893   | TODO_verify_ssa,
 894   0                             /* letter */
 895 };