gcc/tree-cfgcleanup.c

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