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