gcc/tree-cfgcleanup.c

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