gcc/tree-cfgcleanup.c

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