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