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   unsigned n_new_loops;
 711
 712   calculate_dominance_info (CDI_DOMINATORS);
 713
 714   timevar_push (TV_REPAIR_LOOPS);
 715   changed_bbs = BITMAP_ALLOC (NULL);
 716   n_new_loops = fix_loop_structure (changed_bbs);
 717
 718   /* This usually does nothing.  But sometimes parts of cfg that originally
 719      were inside a loop get out of it due to edge removal (since they
 720      become unreachable by back edges from latch).  Also a former
 721      irreducible loop can become reducible - in this case force a full
 722      rewrite into loop-closed SSA form.  */
 723   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 724     rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
 725                                   TODO_update_ssa);
 726
 727   BITMAP_FREE (changed_bbs);
 728
 729 #ifdef ENABLE_CHECKING
 730   verify_loop_structure ();
 731 #endif
 732   scev_reset ();
 733
 734   timevar_pop (TV_REPAIR_LOOPS);
 735 }
 736
 737 /* Cleanup cfg and repair loop structures.  */
 738
 739 bool
 740 cleanup_tree_cfg (void)
 741 {
 742   bool changed = cleanup_tree_cfg_noloop ();
 743
 744   if (current_loops != NULL
 745       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 746     repair_loop_structures ();
 747
 748   return changed;
 749 }
 750
 751 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 752
 753 static void
 754 remove_forwarder_block_with_phi (basic_block bb)
 755 {
 756   edge succ = single_succ_edge (bb);
 757   basic_block dest = succ->dest;
 758   gimple label;
 759   basic_block dombb, domdest, dom;
 760
 761   /* We check for infinite loops already in tree_forwarder_block_p.
 762      However it may happen that the infinite loop is created
 763      afterwards due to removal of forwarders.  */
 764   if (dest == bb)
 765     return;
 766
 767   /* If the destination block consists of a nonlocal label, do not
 768      merge it.  */
 769   label = first_stmt (dest);
 770   if (label
 771       && gimple_code (label) == GIMPLE_LABEL
 772       && DECL_NONLOCAL (gimple_label_label (label)))
 773     return;
 774
 775   /* Redirect each incoming edge to BB to DEST.  */
 776   while (EDGE_COUNT (bb->preds) > 0)
 777     {
 778       edge e = EDGE_PRED (bb, 0), s;
 779       gimple_stmt_iterator gsi;
 780
 781       s = find_edge (e->src, dest);
 782       if (s)
 783         {
 784           /* We already have an edge S from E->src to DEST.  If S and
 785              E->dest's sole successor edge have the same PHI arguments
 786              at DEST, redirect S to DEST.  */
 787           if (phi_alternatives_equal (dest, s, succ))
 788             {
 789               e = redirect_edge_and_branch (e, dest);
 790               redirect_edge_var_map_clear (e);
 791               continue;
 792             }
 793
 794           /* PHI arguments are different.  Create a forwarder block by
 795              splitting E so that we can merge PHI arguments on E to
 796              DEST.  */
 797           e = single_succ_edge (split_edge (e));
 798         }
 799
 800       s = redirect_edge_and_branch (e, dest);
 801
 802       /* redirect_edge_and_branch must not create a new edge.  */
 803       gcc_assert (s == e);
 804
 805       /* Add to the PHI nodes at DEST each PHI argument removed at the
 806          destination of E.  */
 807       for (gsi = gsi_start_phis (dest);
 808            !gsi_end_p (gsi);
 809            gsi_next (&gsi))
 810         {
 811           gimple phi = gsi_stmt (gsi);
 812           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 813           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 814
 815           if (TREE_CODE (def) == SSA_NAME)
 816             {
 817               edge_var_map_vector *head;
 818               edge_var_map *vm;
 819               size_t i;
 820
 821               /* If DEF is one of the results of PHI nodes removed during
 822                  redirection, replace it with the PHI argument that used
 823                  to be on E.  */
 824               head = redirect_edge_var_map_vector (e);
 825               FOR_EACH_VEC_SAFE_ELT (head, i, vm)
 826                 {
 827                   tree old_arg = redirect_edge_var_map_result (vm);
 828                   tree new_arg = redirect_edge_var_map_def (vm);
 829
 830                   if (def == old_arg)
 831                     {
 832                       def = new_arg;
 833                       locus = redirect_edge_var_map_location (vm);
 834                       break;
 835                     }
 836                 }
 837             }
 838
 839           add_phi_arg (phi, def, s, locus);
 840         }
 841
 842       redirect_edge_var_map_clear (e);
 843     }
 844
 845   /* Update the dominators.  */
 846   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 847   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 848   if (domdest == bb)
 849     {
 850       /* Shortcut to avoid calling (relatively expensive)
 851          nearest_common_dominator unless necessary.  */
 852       dom = dombb;
 853     }
 854   else
 855     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 856
 857   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 858
 859   /* Remove BB since all of BB's incoming edges have been redirected
 860      to DEST.  */
 861   delete_basic_block (bb);
 862 }
 863
 864 /* This pass merges PHI nodes if one feeds into another.  For example,
 865    suppose we have the following:
 866
 867   goto <bb 9> (<L9>);
 868
 869 <L8>:;
 870   tem_17 = foo ();
 871
 872   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 873 <L9>:;
 874
 875   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 876 <L10>:;
 877
 878   Then we merge the first PHI node into the second one like so:
 879
 880   goto <bb 9> (<L10>);
 881
 882 <L8>:;
 883   tem_17 = foo ();
 884
 885   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 886 <L10>:;
 887 */
 888
 889 static unsigned int
 890 merge_phi_nodes (void)
 891 {
 892   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 893   basic_block *current = worklist;
 894   basic_block bb;
 895
 896   calculate_dominance_info (CDI_DOMINATORS);
 897
 898   /* Find all PHI nodes that we may be able to merge.  */
 899   FOR_EACH_BB (bb)
 900     {
 901       basic_block dest;
 902
 903       /* Look for a forwarder block with PHI nodes.  */
 904       if (!tree_forwarder_block_p (bb, true))
 905         continue;
 906
 907       dest = single_succ (bb);
 908
 909       /* We have to feed into another basic block with PHI
 910          nodes.  */
 911       if (gimple_seq_empty_p (phi_nodes (dest))
 912           /* We don't want to deal with a basic block with
 913              abnormal edges.  */
 914           || bb_has_abnormal_pred (bb))
 915         continue;
 916
 917       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 918         {
 919           /* If BB does not dominate DEST, then the PHI nodes at
 920              DEST must be the only users of the results of the PHI
 921              nodes at BB.  */
 922           *current++ = bb;
 923         }
 924       else
 925         {
 926           gimple_stmt_iterator gsi;
 927           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 928
 929           /* BB dominates DEST.  There may be many users of the PHI
 930              nodes in BB.  However, there is still a trivial case we
 931              can handle.  If the result of every PHI in BB is used
 932              only by a PHI in DEST, then we can trivially merge the
 933              PHI nodes from BB into DEST.  */
 934           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 935                gsi_next (&gsi))
 936             {
 937               gimple phi = gsi_stmt (gsi);
 938               tree result = gimple_phi_result (phi);
 939               use_operand_p imm_use;
 940               gimple use_stmt;
 941
 942               /* If the PHI's result is never used, then we can just
 943                  ignore it.  */
 944               if (has_zero_uses (result))
 945                 continue;
 946
 947               /* Get the single use of the result of this PHI node.  */
 948               if (!single_imm_use (result, &imm_use, &use_stmt)
 949                   || gimple_code (use_stmt) != GIMPLE_PHI
 950                   || gimple_bb (use_stmt) != dest
 951                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
 952                 break;
 953             }
 954
 955           /* If the loop above iterated through all the PHI nodes
 956              in BB, then we can merge the PHIs from BB into DEST.  */
 957           if (gsi_end_p (gsi))
 958             *current++ = bb;
 959         }
 960     }
 961
 962   /* Now let's drain WORKLIST.  */
 963   while (current != worklist)
 964     {
 965       bb = *--current;
 966       remove_forwarder_block_with_phi (bb);
 967     }
 968
 969   free (worklist);
 970   return 0;
 971 }
 972
 973 static bool
 974 gate_merge_phi (void)
 975 {
 976   return 1;
 977 }
 978
 979 struct gimple_opt_pass pass_merge_phi =
 980 {
 981  {
 982   GIMPLE_PASS,
 983   "mergephi",                   /* name */
 984   OPTGROUP_NONE,                /* optinfo_flags */
 985   gate_merge_phi,               /* gate */
 986   merge_phi_nodes,              /* execute */
 987   NULL,                         /* sub */
 988   NULL,                         /* next */
 989   0,                            /* static_pass_number */
 990   TV_TREE_MERGE_PHI,            /* tv_id */
 991   PROP_cfg | PROP_ssa,          /* properties_required */
 992   0,                            /* properties_provided */
 993   0,                            /* properties_destroyed */
 994   0,                            /* todo_flags_start */
 995   TODO_ggc_collect              /* todo_flags_finish */
 996   | TODO_verify_ssa
 997  }
 998 };