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