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