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 /* STMT is a call that has been discovered noreturn.  Fixup the CFG
 542    and remove LHS.  Return true if something changed.  */
 543
 544 bool
 545 fixup_noreturn_call (gimple stmt)
 546 {
 547   basic_block bb = gimple_bb (stmt);
 548   bool changed = false;
 549
 550   if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
 551     return false;
 552
 553   /* First split basic block if stmt is not last.  */
 554   if (stmt != gsi_stmt (gsi_last_bb (bb)))
 555     split_block (bb, stmt);
 556
 557   changed |= remove_fallthru_edge (bb->succs);
 558
 559   /* If there is LHS, remove it.  */
 560   if (gimple_call_lhs (stmt))
 561     {
 562       tree op = gimple_call_lhs (stmt);
 563       gimple_call_set_lhs (stmt, NULL_TREE);
 564       /* We need to remove SSA name to avoid checking.
 565          All uses are dominated by the noreturn and thus will
 566          be removed afterwards.  */
 567       if (TREE_CODE (op) == SSA_NAME)
 568         {
 569           use_operand_p use_p;
 570           imm_use_iterator iter;
 571           gimple use_stmt;
 572
 573           FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
 574             FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 575               SET_USE (use_p, error_mark_node);
 576         }
 577       update_stmt (stmt);
 578       changed = true;
 579     }
 580   return changed;
 581 }
 582
 583
 584 /* Split basic blocks on calls in the middle of a basic block that are now
 585    known not to return, and remove the unreachable code.  */
 586
 587 static bool
 588 split_bbs_on_noreturn_calls (void)
 589 {
 590   bool changed = false;
 591   gimple stmt;
 592   basic_block bb;
 593
 594   /* Detect cases where a mid-block call is now known not to return.  */
 595   if (cfun->gimple_df)
 596     while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
 597       {
 598         stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
 599         bb = gimple_bb (stmt);
 600         /* BB might be deleted at this point, so verify first
 601            BB is present in the cfg.  */
 602         if (bb == NULL
 603             || bb->index < NUM_FIXED_BLOCKS
 604             || bb->index >= n_basic_blocks
 605             || BASIC_BLOCK (bb->index) != bb
 606             || !gimple_call_noreturn_p (stmt))
 607           continue;
 608
 609         changed |= fixup_noreturn_call (stmt);
 610       }
 611
 612   return changed;
 613 }
 614
 615 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it.  */
 616
 617 static bool
 618 cleanup_omp_return (basic_block bb)
 619 {
 620   gimple stmt = last_stmt (bb);
 621   basic_block control_bb;
 622
 623   if (stmt == NULL
 624       || gimple_code (stmt) != GIMPLE_OMP_RETURN
 625       || !single_pred_p (bb))
 626     return false;
 627
 628   control_bb = single_pred (bb);
 629   stmt = last_stmt (control_bb);
 630
 631   if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
 632     return false;
 633
 634   /* The block with the control statement normally has two entry edges -- one
 635      from entry, one from continue.  If continue is removed, return is
 636      unreachable, so we remove it here as well.  */
 637   if (EDGE_COUNT (control_bb->preds) == 2)
 638     return false;
 639
 640   gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
 641   remove_edge_and_dominated_blocks (single_pred_edge (bb));
 642   return true;
 643 }
 644
 645 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 646    changes.  */
 647
 648 static bool
 649 cleanup_tree_cfg_bb (basic_block bb)
 650 {
 651   bool retval = false;
 652
 653   if (cleanup_omp_return (bb))
 654     return true;
 655
 656   retval = cleanup_control_flow_bb (bb);
 657
 658   if (tree_forwarder_block_p (bb, false)
 659       && remove_forwarder_block (bb))
 660     return true;
 661
 662   /* Merging the blocks may create new opportunities for folding
 663      conditional branches (due to the elimination of single-valued PHI
 664      nodes).  */
 665   if (single_succ_p (bb)
 666       && can_merge_blocks_p (bb, single_succ (bb)))
 667     {
 668       merge_blocks (bb, single_succ (bb));
 669       return true;
 670     }
 671
 672   return retval;
 673 }
 674
 675 /* Iterate the cfg cleanups, while anything changes.  */
 676
 677 static bool
 678 cleanup_tree_cfg_1 (void)
 679 {
 680   bool retval = false;
 681   basic_block bb;
 682   unsigned i, n;
 683
 684   retval |= split_bbs_on_noreturn_calls ();
 685
 686   /* Prepare the worklists of altered blocks.  */
 687   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 688
 689   /* During forwarder block cleanup, we may redirect edges out of
 690      SWITCH_EXPRs, which can get expensive.  So we want to enable
 691      recording of edge to CASE_LABEL_EXPR.  */
 692   start_recording_case_labels ();
 693
 694   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB,
 695      since the basic blocks may get removed.  */
 696   n = last_basic_block;
 697   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 698     {
 699       bb = BASIC_BLOCK (i);
 700       if (bb)
 701         retval |= cleanup_tree_cfg_bb (bb);
 702     }
 703
 704   /* Now process the altered blocks, as long as any are available.  */
 705   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 706     {
 707       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 708       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 709       if (i < NUM_FIXED_BLOCKS)
 710         continue;
 711
 712       bb = BASIC_BLOCK (i);
 713       if (!bb)
 714         continue;
 715
 716       retval |= cleanup_tree_cfg_bb (bb);
 717
 718       /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
 719          calls.  */
 720       retval |= split_bbs_on_noreturn_calls ();
 721     }
 722
 723   end_recording_case_labels ();
 724   BITMAP_FREE (cfgcleanup_altered_bbs);
 725   return retval;
 726 }
 727
 728
 729 /* Remove unreachable blocks and other miscellaneous clean up work.
 730    Return true if the flowgraph was modified, false otherwise.  */
 731
 732 static bool
 733 cleanup_tree_cfg_noloop (void)
 734 {
 735   bool changed;
 736
 737   timevar_push (TV_TREE_CLEANUP_CFG);
 738
 739   /* Iterate until there are no more cleanups left to do.  If any
 740      iteration changed the flowgraph, set CHANGED to true.
 741
 742      If dominance information is available, there cannot be any unreachable
 743      blocks.  */
 744   if (!dom_info_available_p (CDI_DOMINATORS))
 745     {
 746       changed = delete_unreachable_blocks ();
 747       calculate_dominance_info (CDI_DOMINATORS);
 748     }
 749   else
 750     {
 751 #ifdef ENABLE_CHECKING
 752       verify_dominators (CDI_DOMINATORS);
 753 #endif
 754       changed = false;
 755     }
 756
 757   changed |= cleanup_tree_cfg_1 ();
 758
 759   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 760   compact_blocks ();
 761
 762 #ifdef ENABLE_CHECKING
 763   verify_flow_info ();
 764 #endif
 765
 766   timevar_pop (TV_TREE_CLEANUP_CFG);
 767
 768   if (changed && current_loops)
 769     loops_state_set (LOOPS_NEED_FIXUP);
 770
 771   return changed;
 772 }
 773
 774 /* Repairs loop structures.  */
 775
 776 static void
 777 repair_loop_structures (void)
 778 {
 779   bitmap changed_bbs = BITMAP_ALLOC (NULL);
 780   fix_loop_structure (changed_bbs);
 781
 782   /* This usually does nothing.  But sometimes parts of cfg that originally
 783      were inside a loop get out of it due to edge removal (since they
 784      become unreachable by back edges from latch).  */
 785   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 786     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 787
 788   BITMAP_FREE (changed_bbs);
 789
 790 #ifdef ENABLE_CHECKING
 791   verify_loop_structure ();
 792 #endif
 793   scev_reset ();
 794
 795   loops_state_clear (LOOPS_NEED_FIXUP);
 796 }
 797
 798 /* Cleanup cfg and repair loop structures.  */
 799
 800 bool
 801 cleanup_tree_cfg (void)
 802 {
 803   bool changed = cleanup_tree_cfg_noloop ();
 804
 805   if (current_loops != NULL
 806       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 807     repair_loop_structures ();
 808
 809   return changed;
 810 }
 811
 812 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 813
 814 static void
 815 remove_forwarder_block_with_phi (basic_block bb)
 816 {
 817   edge succ = single_succ_edge (bb);
 818   basic_block dest = succ->dest;
 819   gimple label;
 820   basic_block dombb, domdest, dom;
 821
 822   /* We check for infinite loops already in tree_forwarder_block_p.
 823      However it may happen that the infinite loop is created
 824      afterwards due to removal of forwarders.  */
 825   if (dest == bb)
 826     return;
 827
 828   /* If the destination block consists of a nonlocal label, do not
 829      merge it.  */
 830   label = first_stmt (dest);
 831   if (label
 832       && gimple_code (label) == GIMPLE_LABEL
 833       && DECL_NONLOCAL (gimple_label_label (label)))
 834     return;
 835
 836   /* Redirect each incoming edge to BB to DEST.  */
 837   while (EDGE_COUNT (bb->preds) > 0)
 838     {
 839       edge e = EDGE_PRED (bb, 0), s;
 840       gimple_stmt_iterator gsi;
 841
 842       s = find_edge (e->src, dest);
 843       if (s)
 844         {
 845           /* We already have an edge S from E->src to DEST.  If S and
 846              E->dest's sole successor edge have the same PHI arguments
 847              at DEST, redirect S to DEST.  */
 848           if (phi_alternatives_equal (dest, s, succ))
 849             {
 850               e = redirect_edge_and_branch (e, dest);
 851               redirect_edge_var_map_clear (e);
 852               continue;
 853             }
 854
 855           /* PHI arguments are different.  Create a forwarder block by
 856              splitting E so that we can merge PHI arguments on E to
 857              DEST.  */
 858           e = single_succ_edge (split_edge (e));
 859         }
 860
 861       s = redirect_edge_and_branch (e, dest);
 862
 863       /* redirect_edge_and_branch must not create a new edge.  */
 864       gcc_assert (s == e);
 865
 866       /* Add to the PHI nodes at DEST each PHI argument removed at the
 867          destination of E.  */
 868       for (gsi = gsi_start_phis (dest);
 869            !gsi_end_p (gsi);
 870            gsi_next (&gsi))
 871         {
 872           gimple phi = gsi_stmt (gsi);
 873           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 874           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 875
 876           if (TREE_CODE (def) == SSA_NAME)
 877             {
 878               edge_var_map_vector head;
 879               edge_var_map *vm;
 880               size_t i;
 881
 882               /* If DEF is one of the results of PHI nodes removed during
 883                  redirection, replace it with the PHI argument that used
 884                  to be on E.  */
 885               head = redirect_edge_var_map_vector (e);
 886               for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
 887                 {
 888                   tree old_arg = redirect_edge_var_map_result (vm);
 889                   tree new_arg = redirect_edge_var_map_def (vm);
 890
 891                   if (def == old_arg)
 892                     {
 893                       def = new_arg;
 894                       locus = redirect_edge_var_map_location (vm);
 895                       break;
 896                     }
 897                 }
 898             }
 899
 900           add_phi_arg (phi, def, s, locus);
 901         }
 902
 903       redirect_edge_var_map_clear (e);
 904     }
 905
 906   /* Update the dominators.  */
 907   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 908   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 909   if (domdest == bb)
 910     {
 911       /* Shortcut to avoid calling (relatively expensive)
 912          nearest_common_dominator unless necessary.  */
 913       dom = dombb;
 914     }
 915   else
 916     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 917
 918   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 919
 920   /* Remove BB since all of BB's incoming edges have been redirected
 921      to DEST.  */
 922   delete_basic_block (bb);
 923 }
 924
 925 /* This pass merges PHI nodes if one feeds into another.  For example,
 926    suppose we have the following:
 927
 928   goto <bb 9> (<L9>);
 929
 930 <L8>:;
 931   tem_17 = foo ();
 932
 933   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 934 <L9>:;
 935
 936   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 937 <L10>:;
 938
 939   Then we merge the first PHI node into the second one like so:
 940
 941   goto <bb 9> (<L10>);
 942
 943 <L8>:;
 944   tem_17 = foo ();
 945
 946   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 947 <L10>:;
 948 */
 949
 950 static unsigned int
 951 merge_phi_nodes (void)
 952 {
 953   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 954   basic_block *current = worklist;
 955   basic_block bb;
 956
 957   calculate_dominance_info (CDI_DOMINATORS);
 958
 959   /* Find all PHI nodes that we may be able to merge.  */
 960   FOR_EACH_BB (bb)
 961     {
 962       basic_block dest;
 963
 964       /* Look for a forwarder block with PHI nodes.  */
 965       if (!tree_forwarder_block_p (bb, true))
 966         continue;
 967
 968       dest = single_succ (bb);
 969
 970       /* We have to feed into another basic block with PHI
 971          nodes.  */
 972       if (gimple_seq_empty_p (phi_nodes (dest))
 973           /* We don't want to deal with a basic block with
 974              abnormal edges.  */
 975           || has_abnormal_incoming_edge_p (bb))
 976         continue;
 977
 978       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 979         {
 980           /* If BB does not dominate DEST, then the PHI nodes at
 981              DEST must be the only users of the results of the PHI
 982              nodes at BB.  */
 983           *current++ = bb;
 984         }
 985       else
 986         {
 987           gimple_stmt_iterator gsi;
 988           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 989
 990           /* BB dominates DEST.  There may be many users of the PHI
 991              nodes in BB.  However, there is still a trivial case we
 992              can handle.  If the result of every PHI in BB is used
 993              only by a PHI in DEST, then we can trivially merge the
 994              PHI nodes from BB into DEST.  */
 995           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 996                gsi_next (&gsi))
 997             {
 998               gimple phi = gsi_stmt (gsi);
 999               tree result = gimple_phi_result (phi);
1000               use_operand_p imm_use;
1001               gimple use_stmt;
1002
1003               /* If the PHI's result is never used, then we can just
1004                  ignore it.  */
1005               if (has_zero_uses (result))
1006                 continue;
1007
1008               /* Get the single use of the result of this PHI node.  */
1009               if (!single_imm_use (result, &imm_use, &use_stmt)
1010                   || gimple_code (use_stmt) != GIMPLE_PHI
1011                   || gimple_bb (use_stmt) != dest
1012                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1013                 break;
1014             }
1015
1016           /* If the loop above iterated through all the PHI nodes
1017              in BB, then we can merge the PHIs from BB into DEST.  */
1018           if (gsi_end_p (gsi))
1019             *current++ = bb;
1020         }
1021     }
1022
1023   /* Now let's drain WORKLIST.  */
1024   while (current != worklist)
1025     {
1026       bb = *--current;
1027       remove_forwarder_block_with_phi (bb);
1028     }
1029
1030   free (worklist);
1031   return 0;
1032 }
1033
1034 static bool
1035 gate_merge_phi (void)
1036 {
1037   return 1;
1038 }
1039
1040 struct gimple_opt_pass pass_merge_phi =
1041 {
1042  {
1043   GIMPLE_PASS,
1044   "mergephi",                   /* name */
1045   gate_merge_phi,               /* gate */
1046   merge_phi_nodes,              /* execute */
1047   NULL,                         /* sub */
1048   NULL,                         /* next */
1049   0,                            /* static_pass_number */
1050   TV_TREE_MERGE_PHI,            /* tv_id */
1051   PROP_cfg | PROP_ssa,          /* properties_required */
1052   0,                            /* properties_provided */
1053   0,                            /* properties_destroyed */
1054   0,                            /* todo_flags_start */
1055   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
1056   | TODO_verify_ssa
1057  }
1058 };