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