gcc/tree-cfgcleanup.c

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