gcc/tree-cfgcleanup.c

   1 /* CFG cleanup for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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   /* There should not be an edge coming from entry, or an EH edge.  */
 243   {
 244     edge_iterator ei;
 245     edge e;
 246
 247     FOR_EACH_EDGE (e, ei, bb->preds)
 248       if (e->src == ENTRY_BLOCK_PTR || (e->flags & EDGE_EH))
 249         return false;
 250   }
 251
 252   /* Now walk through the statements backward.  We can ignore labels,
 253      anything else means this is not a forwarder block.  */
 254   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 255     {
 256       gimple stmt = gsi_stmt (gsi);
 257
 258       switch (gimple_code (stmt))
 259         {
 260         case GIMPLE_LABEL:
 261           if (DECL_NONLOCAL (gimple_label_label (stmt)))
 262             return false;
 263           break;
 264
 265           /* ??? For now, hope there's a corresponding debug
 266              assignment at the destination.  */
 267         case GIMPLE_DEBUG:
 268           break;
 269
 270         default:
 271           return false;
 272         }
 273     }
 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   return true;
 287 }
 288
 289 /* Return true if BB has at least one abnormal incoming edge.  */
 290
 291 static inline bool
 292 has_abnormal_incoming_edge_p (basic_block bb)
 293 {
 294   edge e;
 295   edge_iterator ei;
 296
 297   FOR_EACH_EDGE (e, ei, bb->preds)
 298     if (e->flags & EDGE_ABNORMAL)
 299       return true;
 300
 301   return false;
 302 }
 303
 304 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
 305    those alternatives are equal in each of the PHI nodes, then return
 306    true, else return false.  */
 307
 308 static bool
 309 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 310 {
 311   int n1 = e1->dest_idx;
 312   int n2 = e2->dest_idx;
 313   gimple_stmt_iterator gsi;
 314
 315   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 316     {
 317       gimple phi = gsi_stmt (gsi);
 318       tree val1 = gimple_phi_arg_def (phi, n1);
 319       tree val2 = gimple_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.  */
 332
 333 static bool
 334 remove_forwarder_block (basic_block bb)
 335 {
 336   edge succ = single_succ_edge (bb), e, s;
 337   basic_block dest = succ->dest;
 338   gimple label;
 339   edge_iterator ei;
 340   gimple_stmt_iterator gsi, gsi_to;
 341
 342   /* We check for infinite loops already in tree_forwarder_block_p.
 343      However it may happen that the infinite loop is created
 344      afterwards due to removal of forwarders.  */
 345   if (dest == bb)
 346     return false;
 347
 348   /* If the destination block consists of a nonlocal label or is a
 349      EH landing pad, do not merge it.  */
 350   label = first_stmt (dest);
 351   if (label
 352       && gimple_code (label) == GIMPLE_LABEL
 353       && (DECL_NONLOCAL (gimple_label_label (label))
 354           || EH_LANDING_PAD_NR (gimple_label_label (label)) != 0))
 355     return false;
 356
 357   /* If there is an abnormal edge to basic block BB, but not into
 358      dest, problems might occur during removal of the phi node at out
 359      of ssa due to overlapping live ranges of registers.
 360
 361      If there is an abnormal edge in DEST, the problems would occur
 362      anyway since cleanup_dead_labels would then merge the labels for
 363      two different eh regions, and rest of exception handling code
 364      does not like it.
 365
 366      So if there is an abnormal edge to BB, proceed only if there is
 367      no abnormal edge to DEST and there are no phi nodes in DEST.  */
 368   if (has_abnormal_incoming_edge_p (bb)
 369       && (has_abnormal_incoming_edge_p (dest)
 370           || !gimple_seq_empty_p (phi_nodes (dest))))
 371     return false;
 372
 373   /* If there are phi nodes in DEST, and some of the blocks that are
 374      predecessors of BB are also predecessors of DEST, check that the
 375      phi node arguments match.  */
 376   if (!gimple_seq_empty_p (phi_nodes (dest)))
 377     {
 378       FOR_EACH_EDGE (e, ei, bb->preds)
 379         {
 380           s = find_edge (e->src, dest);
 381           if (!s)
 382             continue;
 383
 384           if (!phi_alternatives_equal (dest, succ, s))
 385             return false;
 386         }
 387     }
 388
 389   /* Redirect the edges.  */
 390   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 391     {
 392       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
 393
 394       if (e->flags & EDGE_ABNORMAL)
 395         {
 396           /* If there is an abnormal edge, redirect it anyway, and
 397              move the labels to the new block to make it legal.  */
 398           s = redirect_edge_succ_nodup (e, dest);
 399         }
 400       else
 401         s = redirect_edge_and_branch (e, dest);
 402
 403       if (s == e)
 404         {
 405           /* Create arguments for the phi nodes, since the edge was not
 406              here before.  */
 407           for (gsi = gsi_start_phis (dest);
 408                !gsi_end_p (gsi);
 409                gsi_next (&gsi))
 410             {
 411               gimple phi = gsi_stmt (gsi);
 412               source_location l = gimple_phi_arg_location_from_edge (phi, succ);
 413               add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s, l);
 414             }
 415         }
 416     }
 417
 418   /* Move nonlocal labels and computed goto targets as well as user
 419      defined labels and labels with an EH landing pad number to the
 420      new block, so that the redirection of the abnormal edges works,
 421      jump targets end up in a sane place and debug information for
 422      labels is retained.  */
 423   gsi_to = gsi_start_bb (dest);
 424   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 425     {
 426       tree decl;
 427       label = gsi_stmt (gsi);
 428       if (is_gimple_debug (label))
 429         break;
 430       decl = gimple_label_label (label);
 431       if (EH_LANDING_PAD_NR (decl) != 0
 432           || DECL_NONLOCAL (decl)
 433           || FORCED_LABEL (decl)
 434           || !DECL_ARTIFICIAL (decl))
 435         {
 436           gsi_remove (&gsi, false);
 437           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 438         }
 439       else
 440         gsi_next (&gsi);
 441     }
 442
 443   /* Move debug statements if the destination has just a single
 444      predecessor.  */
 445   if (single_pred_p (dest))
 446     {
 447       gsi_to = gsi_after_labels (dest);
 448       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
 449         {
 450           if (!is_gimple_debug (gsi_stmt (gsi)))
 451             break;
 452           gsi_remove (&gsi, false);
 453           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 454         }
 455     }
 456
 457   bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
 458
 459   /* Update the dominators.  */
 460   if (dom_info_available_p (CDI_DOMINATORS))
 461     {
 462       basic_block dom, dombb, domdest;
 463
 464       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 465       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 466       if (domdest == bb)
 467         {
 468           /* Shortcut to avoid calling (relatively expensive)
 469              nearest_common_dominator unless necessary.  */
 470           dom = dombb;
 471         }
 472       else
 473         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 474
 475       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 476     }
 477
 478   /* And kill the forwarder block.  */
 479   delete_basic_block (bb);
 480
 481   return true;
 482 }
 483
 484 /* Split basic blocks on calls in the middle of a basic block that are now
 485    known not to return, and remove the unreachable code.  */
 486
 487 static bool
 488 split_bbs_on_noreturn_calls (void)
 489 {
 490   bool changed = false;
 491   gimple stmt;
 492   basic_block bb;
 493
 494   /* Detect cases where a mid-block call is now known not to return.  */
 495   if (cfun->gimple_df)
 496     while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
 497       {
 498         stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
 499         bb = gimple_bb (stmt);
 500         /* BB might be deleted at this point, so verify first
 501            BB is present in the cfg.  */
 502         if (bb == NULL
 503             || bb->index < NUM_FIXED_BLOCKS
 504             || bb->index >= n_basic_blocks
 505             || BASIC_BLOCK (bb->index) != bb
 506             || last_stmt (bb) == stmt
 507             || !gimple_call_noreturn_p (stmt))
 508           continue;
 509
 510         changed = true;
 511         split_block (bb, stmt);
 512         remove_fallthru_edge (bb->succs);
 513       }
 514
 515   return changed;
 516 }
 517
 518 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it.  */
 519
 520 static bool
 521 cleanup_omp_return (basic_block bb)
 522 {
 523   gimple stmt = last_stmt (bb);
 524   basic_block control_bb;
 525
 526   if (stmt == NULL
 527       || gimple_code (stmt) != GIMPLE_OMP_RETURN
 528       || !single_pred_p (bb))
 529     return false;
 530
 531   control_bb = single_pred (bb);
 532   stmt = last_stmt (control_bb);
 533
 534   if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
 535     return false;
 536
 537   /* The block with the control statement normally has two entry edges -- one
 538      from entry, one from continue.  If continue is removed, return is
 539      unreachable, so we remove it here as well.  */
 540   if (EDGE_COUNT (control_bb->preds) == 2)
 541     return false;
 542
 543   gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
 544   remove_edge_and_dominated_blocks (single_pred_edge (bb));
 545   return true;
 546 }
 547
 548 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 549    changes.  */
 550
 551 static bool
 552 cleanup_tree_cfg_bb (basic_block bb)
 553 {
 554   bool retval = false;
 555
 556   if (cleanup_omp_return (bb))
 557     return true;
 558
 559   retval = cleanup_control_flow_bb (bb);
 560
 561   /* Forwarder blocks can carry line number information which is
 562      useful when debugging, so we only clean them up when
 563      optimizing.  */
 564   if (optimize > 0
 565       && tree_forwarder_block_p (bb, false)
 566       && remove_forwarder_block (bb))
 567     return true;
 568
 569   /* Merging the blocks may create new opportunities for folding
 570      conditional branches (due to the elimination of single-valued PHI
 571      nodes).  */
 572   if (single_succ_p (bb)
 573       && can_merge_blocks_p (bb, single_succ (bb)))
 574     {
 575       merge_blocks (bb, single_succ (bb));
 576       return true;
 577     }
 578
 579   return retval;
 580 }
 581
 582 /* Iterate the cfg cleanups, while anything changes.  */
 583
 584 static bool
 585 cleanup_tree_cfg_1 (void)
 586 {
 587   bool retval = false;
 588   basic_block bb;
 589   unsigned i, n;
 590
 591   retval |= split_bbs_on_noreturn_calls ();
 592
 593   /* Prepare the worklists of altered blocks.  */
 594   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 595
 596   /* During forwarder block cleanup, we may redirect edges out of
 597      SWITCH_EXPRs, which can get expensive.  So we want to enable
 598      recording of edge to CASE_LABEL_EXPR.  */
 599   start_recording_case_labels ();
 600
 601   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB,
 602      since the basic blocks may get removed.  */
 603   n = last_basic_block;
 604   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 605     {
 606       bb = BASIC_BLOCK (i);
 607       if (bb)
 608         retval |= cleanup_tree_cfg_bb (bb);
 609     }
 610
 611   /* Now process the altered blocks, as long as any are available.  */
 612   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 613     {
 614       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 615       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 616       if (i < NUM_FIXED_BLOCKS)
 617         continue;
 618
 619       bb = BASIC_BLOCK (i);
 620       if (!bb)
 621         continue;
 622
 623       retval |= cleanup_tree_cfg_bb (bb);
 624
 625       /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
 626          calls.  */
 627       retval |= split_bbs_on_noreturn_calls ();
 628     }
 629
 630   end_recording_case_labels ();
 631   BITMAP_FREE (cfgcleanup_altered_bbs);
 632   return retval;
 633 }
 634
 635
 636 /* Remove unreachable blocks and other miscellaneous clean up work.
 637    Return true if the flowgraph was modified, false otherwise.  */
 638
 639 static bool
 640 cleanup_tree_cfg_noloop (void)
 641 {
 642   bool changed;
 643
 644   timevar_push (TV_TREE_CLEANUP_CFG);
 645
 646   /* Iterate until there are no more cleanups left to do.  If any
 647      iteration changed the flowgraph, set CHANGED to true.
 648
 649      If dominance information is available, there cannot be any unreachable
 650      blocks.  */
 651   if (!dom_info_available_p (CDI_DOMINATORS))
 652     {
 653       changed = delete_unreachable_blocks ();
 654       calculate_dominance_info (CDI_DOMINATORS);
 655     }
 656   else
 657     {
 658 #ifdef ENABLE_CHECKING
 659       verify_dominators (CDI_DOMINATORS);
 660 #endif
 661       changed = false;
 662     }
 663
 664   changed |= cleanup_tree_cfg_1 ();
 665
 666   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 667   compact_blocks ();
 668
 669 #ifdef ENABLE_CHECKING
 670   verify_flow_info ();
 671 #endif
 672
 673   timevar_pop (TV_TREE_CLEANUP_CFG);
 674
 675   if (changed && current_loops)
 676     loops_state_set (LOOPS_NEED_FIXUP);
 677
 678   return changed;
 679 }
 680
 681 /* Repairs loop structures.  */
 682
 683 static void
 684 repair_loop_structures (void)
 685 {
 686   bitmap changed_bbs = BITMAP_ALLOC (NULL);
 687   fix_loop_structure (changed_bbs);
 688
 689   /* This usually does nothing.  But sometimes parts of cfg that originally
 690      were inside a loop get out of it due to edge removal (since they
 691      become unreachable by back edges from latch).  */
 692   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 693     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 694
 695   BITMAP_FREE (changed_bbs);
 696
 697 #ifdef ENABLE_CHECKING
 698   verify_loop_structure ();
 699 #endif
 700   scev_reset ();
 701
 702   loops_state_clear (LOOPS_NEED_FIXUP);
 703 }
 704
 705 /* Cleanup cfg and repair loop structures.  */
 706
 707 bool
 708 cleanup_tree_cfg (void)
 709 {
 710   bool changed = cleanup_tree_cfg_noloop ();
 711
 712   if (current_loops != NULL
 713       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 714     repair_loop_structures ();
 715
 716   return changed;
 717 }
 718
 719 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 720
 721 static void
 722 remove_forwarder_block_with_phi (basic_block bb)
 723 {
 724   edge succ = single_succ_edge (bb);
 725   basic_block dest = succ->dest;
 726   gimple label;
 727   basic_block dombb, domdest, dom;
 728
 729   /* We check for infinite loops already in tree_forwarder_block_p.
 730      However it may happen that the infinite loop is created
 731      afterwards due to removal of forwarders.  */
 732   if (dest == bb)
 733     return;
 734
 735   /* If the destination block consists of a nonlocal label, do not
 736      merge it.  */
 737   label = first_stmt (dest);
 738   if (label
 739       && gimple_code (label) == GIMPLE_LABEL
 740       && DECL_NONLOCAL (gimple_label_label (label)))
 741     return;
 742
 743   /* Redirect each incoming edge to BB to DEST.  */
 744   while (EDGE_COUNT (bb->preds) > 0)
 745     {
 746       edge e = EDGE_PRED (bb, 0), s;
 747       gimple_stmt_iterator gsi;
 748
 749       s = find_edge (e->src, dest);
 750       if (s)
 751         {
 752           /* We already have an edge S from E->src to DEST.  If S and
 753              E->dest's sole successor edge have the same PHI arguments
 754              at DEST, redirect S to DEST.  */
 755           if (phi_alternatives_equal (dest, s, succ))
 756             {
 757               e = redirect_edge_and_branch (e, dest);
 758               redirect_edge_var_map_clear (e);
 759               continue;
 760             }
 761
 762           /* PHI arguments are different.  Create a forwarder block by
 763              splitting E so that we can merge PHI arguments on E to
 764              DEST.  */
 765           e = single_succ_edge (split_edge (e));
 766         }
 767
 768       s = redirect_edge_and_branch (e, dest);
 769
 770       /* redirect_edge_and_branch must not create a new edge.  */
 771       gcc_assert (s == e);
 772
 773       /* Add to the PHI nodes at DEST each PHI argument removed at the
 774          destination of E.  */
 775       for (gsi = gsi_start_phis (dest);
 776            !gsi_end_p (gsi);
 777            gsi_next (&gsi))
 778         {
 779           gimple phi = gsi_stmt (gsi);
 780           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 781           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 782
 783           if (TREE_CODE (def) == SSA_NAME)
 784             {
 785               edge_var_map_vector head;
 786               edge_var_map *vm;
 787               size_t i;
 788
 789               /* If DEF is one of the results of PHI nodes removed during
 790                  redirection, replace it with the PHI argument that used
 791                  to be on E.  */
 792               head = redirect_edge_var_map_vector (e);
 793               for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
 794                 {
 795                   tree old_arg = redirect_edge_var_map_result (vm);
 796                   tree new_arg = redirect_edge_var_map_def (vm);
 797
 798                   if (def == old_arg)
 799                     {
 800                       def = new_arg;
 801                       locus = redirect_edge_var_map_location (vm);
 802                       break;
 803                     }
 804                 }
 805             }
 806
 807           add_phi_arg (phi, def, s, locus);
 808         }
 809
 810       redirect_edge_var_map_clear (e);
 811     }
 812
 813   /* Update the dominators.  */
 814   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 815   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 816   if (domdest == bb)
 817     {
 818       /* Shortcut to avoid calling (relatively expensive)
 819          nearest_common_dominator unless necessary.  */
 820       dom = dombb;
 821     }
 822   else
 823     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 824
 825   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 826
 827   /* Remove BB since all of BB's incoming edges have been redirected
 828      to DEST.  */
 829   delete_basic_block (bb);
 830 }
 831
 832 /* This pass merges PHI nodes if one feeds into another.  For example,
 833    suppose we have the following:
 834
 835   goto <bb 9> (<L9>);
 836
 837 <L8>:;
 838   tem_17 = foo ();
 839
 840   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 841 <L9>:;
 842
 843   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 844 <L10>:;
 845
 846   Then we merge the first PHI node into the second one like so:
 847
 848   goto <bb 9> (<L10>);
 849
 850 <L8>:;
 851   tem_17 = foo ();
 852
 853   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 854 <L10>:;
 855 */
 856
 857 static unsigned int
 858 merge_phi_nodes (void)
 859 {
 860   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 861   basic_block *current = worklist;
 862   basic_block bb;
 863
 864   calculate_dominance_info (CDI_DOMINATORS);
 865
 866   /* Find all PHI nodes that we may be able to merge.  */
 867   FOR_EACH_BB (bb)
 868     {
 869       basic_block dest;
 870
 871       /* Look for a forwarder block with PHI nodes.  */
 872       if (!tree_forwarder_block_p (bb, true))
 873         continue;
 874
 875       dest = single_succ (bb);
 876
 877       /* We have to feed into another basic block with PHI
 878          nodes.  */
 879       if (gimple_seq_empty_p (phi_nodes (dest))
 880           /* We don't want to deal with a basic block with
 881              abnormal edges.  */
 882           || has_abnormal_incoming_edge_p (bb))
 883         continue;
 884
 885       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 886         {
 887           /* If BB does not dominate DEST, then the PHI nodes at
 888              DEST must be the only users of the results of the PHI
 889              nodes at BB.  */
 890           *current++ = bb;
 891         }
 892       else
 893         {
 894           gimple_stmt_iterator gsi;
 895           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 896
 897           /* BB dominates DEST.  There may be many users of the PHI
 898              nodes in BB.  However, there is still a trivial case we
 899              can handle.  If the result of every PHI in BB is used
 900              only by a PHI in DEST, then we can trivially merge the
 901              PHI nodes from BB into DEST.  */
 902           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 903                gsi_next (&gsi))
 904             {
 905               gimple phi = gsi_stmt (gsi);
 906               tree result = gimple_phi_result (phi);
 907               use_operand_p imm_use;
 908               gimple use_stmt;
 909
 910               /* If the PHI's result is never used, then we can just
 911                  ignore it.  */
 912               if (has_zero_uses (result))
 913                 continue;
 914
 915               /* Get the single use of the result of this PHI node.  */
 916               if (!single_imm_use (result, &imm_use, &use_stmt)
 917                   || gimple_code (use_stmt) != GIMPLE_PHI
 918                   || gimple_bb (use_stmt) != dest
 919                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
 920                 break;
 921             }
 922
 923           /* If the loop above iterated through all the PHI nodes
 924              in BB, then we can merge the PHIs from BB into DEST.  */
 925           if (gsi_end_p (gsi))
 926             *current++ = bb;
 927         }
 928     }
 929
 930   /* Now let's drain WORKLIST.  */
 931   while (current != worklist)
 932     {
 933       bb = *--current;
 934       remove_forwarder_block_with_phi (bb);
 935     }
 936
 937   free (worklist);
 938   return 0;
 939 }
 940
 941 static bool
 942 gate_merge_phi (void)
 943 {
 944   return 1;
 945 }
 946
 947 struct gimple_opt_pass pass_merge_phi =
 948 {
 949  {
 950   GIMPLE_PASS,
 951   "mergephi",                   /* name */
 952   gate_merge_phi,               /* gate */
 953   merge_phi_nodes,              /* execute */
 954   NULL,                         /* sub */
 955   NULL,                         /* next */
 956   0,                            /* static_pass_number */
 957   TV_TREE_MERGE_PHI,            /* tv_id */
 958   PROP_cfg | PROP_ssa,          /* properties_required */
 959   0,                            /* properties_provided */
 960   0,                            /* properties_destroyed */
 961   0,                            /* todo_flags_start */
 962   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 963   | TODO_verify_ssa
 964  }
 965 };