gcc/tree-cfgcleanup.c

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