contrib/gcc-5.0/gcc/tree-cfgcleanup.c

   1 /* CFG cleanup for trees.
   2    Copyright (C) 2001-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "hash-set.h"
  25 #include "machmode.h"
  26 #include "vec.h"
  27 #include "double-int.h"
  28 #include "input.h"
  29 #include "alias.h"
  30 #include "symtab.h"
  31 #include "wide-int.h"
  32 #include "inchash.h"
  33 #include "tree.h"
  34 #include "fold-const.h"
  35 #include "tm_p.h"
  36 #include "predict.h"
  37 #include "hard-reg-set.h"
  38 #include "function.h"
  39 #include "dominance.h"
  40 #include "cfg.h"
  41 #include "cfganal.h"
  42 #include "cfgcleanup.h"
  43 #include "basic-block.h"
  44 #include "diagnostic-core.h"
  45 #include "flags.h"
  46 #include "langhooks.h"
  47 #include "tree-ssa-alias.h"
  48 #include "internal-fn.h"
  49 #include "tree-eh.h"
  50 #include "gimple-expr.h"
  51 #include "is-a.h"
  52 #include "gimple.h"
  53 #include "gimplify.h"
  54 #include "gimple-iterator.h"
  55 #include "gimple-ssa.h"
  56 #include "tree-cfg.h"
  57 #include "tree-phinodes.h"
  58 #include "ssa-iterators.h"
  59 #include "stringpool.h"
  60 #include "tree-ssanames.h"
  61 #include "tree-ssa-loop-manip.h"
  62 #include "hashtab.h"
  63 #include "rtl.h"
  64 #include "statistics.h"
  65 #include "real.h"
  66 #include "fixed-value.h"
  67 #include "insn-config.h"
  68 #include "expmed.h"
  69 #include "dojump.h"
  70 #include "explow.h"
  71 #include "calls.h"
  72 #include "emit-rtl.h"
  73 #include "varasm.h"
  74 #include "stmt.h"
  75 #include "expr.h"
  76 #include "tree-dfa.h"
  77 #include "tree-ssa.h"
  78 #include "tree-pass.h"
  79 #include "except.h"
  80 #include "cfgloop.h"
  81 #include "tree-ssa-propagate.h"
  82 #include "tree-scalar-evolution.h"
  83
  84 /* The set of blocks in that at least one of the following changes happened:
  85    -- the statement at the end of the block was changed
  86    -- the block was newly created
  87    -- the set of the predecessors of the block changed
  88    -- the set of the successors of the block changed
  89    ??? Maybe we could track these changes separately, since they determine
  90        what cleanups it makes sense to try on the block.  */
  91 bitmap cfgcleanup_altered_bbs;
  92
  93 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
  94
  95 static bool
  96 remove_fallthru_edge (vec<edge, va_gc> *ev)
  97 {
  98   edge_iterator ei;
  99   edge e;
 100
 101   FOR_EACH_EDGE (e, ei, ev)
 102     if ((e->flags & EDGE_FALLTHRU) != 0)
 103       {
 104         if (e->flags & EDGE_COMPLEX)
 105           e->flags &= ~EDGE_FALLTHRU;
 106         else
 107           remove_edge_and_dominated_blocks (e);
 108         return true;
 109       }
 110   return false;
 111 }
 112
 113
 114 /* Disconnect an unreachable block in the control expression starting
 115    at block BB.  */
 116
 117 static bool
 118 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
 119 {
 120   edge taken_edge;
 121   bool retval = false;
 122   gimple stmt = gsi_stmt (gsi);
 123   tree val;
 124
 125   if (!single_succ_p (bb))
 126     {
 127       edge e;
 128       edge_iterator ei;
 129       bool warned;
 130       location_t loc;
 131
 132       fold_defer_overflow_warnings ();
 133       loc = gimple_location (stmt);
 134       switch (gimple_code (stmt))
 135         {
 136         case GIMPLE_COND:
 137           val = fold_binary_loc (loc, gimple_cond_code (stmt),
 138                                  boolean_type_node,
 139                                  gimple_cond_lhs (stmt),
 140                                  gimple_cond_rhs (stmt));
 141           break;
 142
 143         case GIMPLE_SWITCH:
 144           val = gimple_switch_index (as_a <gswitch *> (stmt));
 145           break;
 146
 147         default:
 148           val = NULL_TREE;
 149         }
 150       taken_edge = find_taken_edge (bb, val);
 151       if (!taken_edge)
 152         {
 153           fold_undefer_and_ignore_overflow_warnings ();
 154           return false;
 155         }
 156
 157       /* Remove all the edges except the one that is always executed.  */
 158       warned = false;
 159       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 160         {
 161           if (e != taken_edge)
 162             {
 163               if (!warned)
 164                 {
 165                   fold_undefer_overflow_warnings
 166                     (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
 167                   warned = true;
 168                 }
 169
 170               taken_edge->probability += e->probability;
 171               taken_edge->count += e->count;
 172               remove_edge_and_dominated_blocks (e);
 173               retval = true;
 174             }
 175           else
 176             ei_next (&ei);
 177         }
 178       if (!warned)
 179         fold_undefer_and_ignore_overflow_warnings ();
 180       if (taken_edge->probability > REG_BR_PROB_BASE)
 181         taken_edge->probability = REG_BR_PROB_BASE;
 182     }
 183   else
 184     taken_edge = single_succ_edge (bb);
 185
 186   bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
 187   gsi_remove (&gsi, true);
 188   taken_edge->flags = EDGE_FALLTHRU;
 189
 190   return retval;
 191 }
 192
 193 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
 194    to updated gimple_call_flags.  */
 195
 196 static void
 197 cleanup_call_ctrl_altering_flag (gimple bb_end)
 198 {
 199   if (!is_gimple_call (bb_end)
 200       || !gimple_call_ctrl_altering_p (bb_end))
 201     return;
 202
 203   int flags = gimple_call_flags (bb_end);
 204   if (((flags & (ECF_CONST | ECF_PURE))
 205        && !(flags & ECF_LOOPING_CONST_OR_PURE))
 206       || (flags & ECF_LEAF))
 207     gimple_call_set_ctrl_altering (bb_end, false);
 208 }
 209
 210 /* Try to remove superfluous control structures in basic block BB.  Returns
 211    true if anything changes.  */
 212
 213 static bool
 214 cleanup_control_flow_bb (basic_block bb)
 215 {
 216   gimple_stmt_iterator gsi;
 217   bool retval = false;
 218   gimple stmt;
 219
 220   /* If the last statement of the block could throw and now cannot,
 221      we need to prune cfg.  */
 222   retval |= gimple_purge_dead_eh_edges (bb);
 223
 224   gsi = gsi_last_bb (bb);
 225   if (gsi_end_p (gsi))
 226     return retval;
 227
 228   stmt = gsi_stmt (gsi);
 229
 230   /* Try to cleanup ctrl altering flag for call which ends bb.  */
 231   cleanup_call_ctrl_altering_flag (stmt);
 232
 233   if (gimple_code (stmt) == GIMPLE_COND
 234       || gimple_code (stmt) == GIMPLE_SWITCH)
 235     retval |= cleanup_control_expr_graph (bb, gsi);
 236   else if (gimple_code (stmt) == GIMPLE_GOTO
 237            && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
 238            && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
 239                == LABEL_DECL))
 240     {
 241       /* If we had a computed goto which has a compile-time determinable
 242          destination, then we can eliminate the goto.  */
 243       edge e;
 244       tree label;
 245       edge_iterator ei;
 246       basic_block target_block;
 247
 248       /* First look at all the outgoing edges.  Delete any outgoing
 249          edges which do not go to the right block.  For the one
 250          edge which goes to the right block, fix up its flags.  */
 251       label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
 252       target_block = label_to_block (label);
 253       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 254         {
 255           if (e->dest != target_block)
 256             remove_edge_and_dominated_blocks (e);
 257           else
 258             {
 259               /* Turn off the EDGE_ABNORMAL flag.  */
 260               e->flags &= ~EDGE_ABNORMAL;
 261
 262               /* And set EDGE_FALLTHRU.  */
 263               e->flags |= EDGE_FALLTHRU;
 264               ei_next (&ei);
 265             }
 266         }
 267
 268       bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
 269       bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
 270
 271       /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
 272          relevant information we need.  */
 273       gsi_remove (&gsi, true);
 274       retval = true;
 275     }
 276
 277   /* Check for indirect calls that have been turned into
 278      noreturn calls.  */
 279   else if (is_gimple_call (stmt)
 280            && gimple_call_noreturn_p (stmt)
 281            && remove_fallthru_edge (bb->succs))
 282     retval = true;
 283
 284   return retval;
 285 }
 286
 287 /* Return true if basic block BB does nothing except pass control
 288    flow to another block and that we can safely insert a label at
 289    the start of the successor block.
 290
 291    As a precondition, we require that BB be not equal to
 292    the entry block.  */
 293
 294 static bool
 295 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
 296 {
 297   gimple_stmt_iterator gsi;
 298   location_t locus;
 299
 300   /* BB must have a single outgoing edge.  */
 301   if (single_succ_p (bb) != 1
 302       /* If PHI_WANTED is false, BB must not have any PHI nodes.
 303          Otherwise, BB must have PHI nodes.  */
 304       || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
 305       /* BB may not be a predecessor of the exit block.  */
 306       || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
 307       /* Nor should this be an infinite loop.  */
 308       || single_succ (bb) == bb
 309       /* BB may not have an abnormal outgoing edge.  */
 310       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
 311     return false;
 312
 313   gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
 314
 315   locus = single_succ_edge (bb)->goto_locus;
 316
 317   /* There should not be an edge coming from entry, or an EH edge.  */
 318   {
 319     edge_iterator ei;
 320     edge e;
 321
 322     FOR_EACH_EDGE (e, ei, bb->preds)
 323       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
 324         return false;
 325       /* If goto_locus of any of the edges differs, prevent removing
 326          the forwarder block for -O0.  */
 327       else if (optimize == 0 && e->goto_locus != locus)
 328         return false;
 329   }
 330
 331   /* Now walk through the statements backward.  We can ignore labels,
 332      anything else means this is not a forwarder block.  */
 333   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 334     {
 335       gimple stmt = gsi_stmt (gsi);
 336
 337       switch (gimple_code (stmt))
 338         {
 339         case GIMPLE_LABEL:
 340           if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
 341             return false;
 342           if (optimize == 0 && gimple_location (stmt) != locus)
 343             return false;
 344           break;
 345
 346           /* ??? For now, hope there's a corresponding debug
 347              assignment at the destination.  */
 348         case GIMPLE_DEBUG:
 349           break;
 350
 351         default:
 352           return false;
 353         }
 354     }
 355
 356   if (current_loops)
 357     {
 358       basic_block dest;
 359       /* Protect loop headers.  */
 360       if (bb->loop_father->header == bb)
 361         return false;
 362
 363       dest = EDGE_SUCC (bb, 0)->dest;
 364       /* Protect loop preheaders and latches if requested.  */
 365       if (dest->loop_father->header == dest)
 366         {
 367           if (bb->loop_father == dest->loop_father)
 368             {
 369               if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
 370                 return false;
 371               /* If bb doesn't have a single predecessor we'd make this
 372                  loop have multiple latches.  Don't do that if that
 373                  would in turn require disambiguating them.  */
 374               return (single_pred_p (bb)
 375                       || loops_state_satisfies_p
 376                            (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
 377             }
 378           else if (bb->loop_father == loop_outer (dest->loop_father))
 379             return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
 380           /* Always preserve other edges into loop headers that are
 381              not simple latches or preheaders.  */
 382           return false;
 383         }
 384     }
 385
 386   return true;
 387 }
 388
 389 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
 390    those alternatives are equal in each of the PHI nodes, then return
 391    true, else return false.  */
 392
 393 static bool
 394 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 395 {
 396   int n1 = e1->dest_idx;
 397   int n2 = e2->dest_idx;
 398   gphi_iterator gsi;
 399
 400   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 401     {
 402       gphi *phi = gsi.phi ();
 403       tree val1 = gimple_phi_arg_def (phi, n1);
 404       tree val2 = gimple_phi_arg_def (phi, n2);
 405
 406       gcc_assert (val1 != NULL_TREE);
 407       gcc_assert (val2 != NULL_TREE);
 408
 409       if (!operand_equal_for_phi_arg_p (val1, val2))
 410         return false;
 411     }
 412
 413   return true;
 414 }
 415
 416 /* Removes forwarder block BB.  Returns false if this failed.  */
 417
 418 static bool
 419 remove_forwarder_block (basic_block bb)
 420 {
 421   edge succ = single_succ_edge (bb), e, s;
 422   basic_block dest = succ->dest;
 423   gimple label;
 424   edge_iterator ei;
 425   gimple_stmt_iterator gsi, gsi_to;
 426   bool can_move_debug_stmts;
 427
 428   /* We check for infinite loops already in tree_forwarder_block_p.
 429      However it may happen that the infinite loop is created
 430      afterwards due to removal of forwarders.  */
 431   if (dest == bb)
 432     return false;
 433
 434   /* If the destination block consists of a nonlocal label or is a
 435      EH landing pad, do not merge it.  */
 436   label = first_stmt (dest);
 437   if (label)
 438     if (glabel *label_stmt = dyn_cast <glabel *> (label))
 439       if (DECL_NONLOCAL (gimple_label_label (label_stmt))
 440           || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
 441         return false;
 442
 443   /* If there is an abnormal edge to basic block BB, but not into
 444      dest, problems might occur during removal of the phi node at out
 445      of ssa due to overlapping live ranges of registers.
 446
 447      If there is an abnormal edge in DEST, the problems would occur
 448      anyway since cleanup_dead_labels would then merge the labels for
 449      two different eh regions, and rest of exception handling code
 450      does not like it.
 451
 452      So if there is an abnormal edge to BB, proceed only if there is
 453      no abnormal edge to DEST and there are no phi nodes in DEST.  */
 454   if (bb_has_abnormal_pred (bb)
 455       && (bb_has_abnormal_pred (dest)
 456           || !gimple_seq_empty_p (phi_nodes (dest))))
 457     return false;
 458
 459   /* If there are phi nodes in DEST, and some of the blocks that are
 460      predecessors of BB are also predecessors of DEST, check that the
 461      phi node arguments match.  */
 462   if (!gimple_seq_empty_p (phi_nodes (dest)))
 463     {
 464       FOR_EACH_EDGE (e, ei, bb->preds)
 465         {
 466           s = find_edge (e->src, dest);
 467           if (!s)
 468             continue;
 469
 470           if (!phi_alternatives_equal (dest, succ, s))
 471             return false;
 472         }
 473     }
 474
 475   can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
 476
 477   basic_block pred = NULL;
 478   if (single_pred_p (bb))
 479     pred = single_pred (bb);
 480
 481   /* Redirect the edges.  */
 482   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 483     {
 484       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
 485
 486       if (e->flags & EDGE_ABNORMAL)
 487         {
 488           /* If there is an abnormal edge, redirect it anyway, and
 489              move the labels to the new block to make it legal.  */
 490           s = redirect_edge_succ_nodup (e, dest);
 491         }
 492       else
 493         s = redirect_edge_and_branch (e, dest);
 494
 495       if (s == e)
 496         {
 497           /* Create arguments for the phi nodes, since the edge was not
 498              here before.  */
 499           for (gphi_iterator psi = gsi_start_phis (dest);
 500                !gsi_end_p (psi);
 501                gsi_next (&psi))
 502             {
 503               gphi *phi = psi.phi ();
 504               source_location l = gimple_phi_arg_location_from_edge (phi, succ);
 505               tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 506               add_phi_arg (phi, unshare_expr (def), s, l);
 507             }
 508         }
 509     }
 510
 511   /* Move nonlocal labels and computed goto targets as well as user
 512      defined labels and labels with an EH landing pad number to the
 513      new block, so that the redirection of the abnormal edges works,
 514      jump targets end up in a sane place and debug information for
 515      labels is retained.  */
 516   gsi_to = gsi_start_bb (dest);
 517   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 518     {
 519       tree decl;
 520       label = gsi_stmt (gsi);
 521       if (is_gimple_debug (label))
 522         break;
 523       decl = gimple_label_label (as_a <glabel *> (label));
 524       if (EH_LANDING_PAD_NR (decl) != 0
 525           || DECL_NONLOCAL (decl)
 526           || FORCED_LABEL (decl)
 527           || !DECL_ARTIFICIAL (decl))
 528         {
 529           gsi_remove (&gsi, false);
 530           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 531         }
 532       else
 533         gsi_next (&gsi);
 534     }
 535
 536   /* Move debug statements if the destination has a single predecessor.  */
 537   if (can_move_debug_stmts)
 538     {
 539       gsi_to = gsi_after_labels (dest);
 540       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
 541         {
 542           gimple debug = gsi_stmt (gsi);
 543           if (!is_gimple_debug (debug))
 544             break;
 545           gsi_remove (&gsi, false);
 546           gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT);
 547         }
 548     }
 549
 550   bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
 551
 552   /* Update the dominators.  */
 553   if (dom_info_available_p (CDI_DOMINATORS))
 554     {
 555       basic_block dom, dombb, domdest;
 556
 557       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 558       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 559       if (domdest == bb)
 560         {
 561           /* Shortcut to avoid calling (relatively expensive)
 562              nearest_common_dominator unless necessary.  */
 563           dom = dombb;
 564         }
 565       else
 566         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 567
 568       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 569     }
 570
 571   /* Adjust latch infomation of BB's parent loop as otherwise
 572      the cfg hook has a hard time not to kill the loop.  */
 573   if (current_loops && bb->loop_father->latch == bb)
 574     bb->loop_father->latch = pred;
 575
 576   /* And kill the forwarder block.  */
 577   delete_basic_block (bb);
 578
 579   return true;
 580 }
 581
 582 /* STMT is a call that has been discovered noreturn.  Split the
 583    block to prepare fixing up the CFG and remove LHS.
 584    Return true if cleanup-cfg needs to run.  */
 585
 586 bool
 587 fixup_noreturn_call (gimple stmt)
 588 {
 589   basic_block bb = gimple_bb (stmt);
 590   bool changed = false;
 591
 592   if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
 593     return false;
 594
 595   /* First split basic block if stmt is not last.  */
 596   if (stmt != gsi_stmt (gsi_last_bb (bb)))
 597     {
 598       if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
 599         {
 600           /* Don't split if there are only debug stmts
 601              after stmt, that can result in -fcompare-debug
 602              failures.  Remove the debug stmts instead,
 603              they should be all unreachable anyway.  */
 604           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 605           for (gsi_next (&gsi); !gsi_end_p (gsi); )
 606             gsi_remove (&gsi, true);
 607         }
 608       else
 609         {
 610           split_block (bb, stmt);
 611           changed = true;
 612         }
 613     }
 614
 615   /* If there is an LHS, remove it.  */
 616   tree lhs = gimple_call_lhs (stmt);
 617   if (lhs)
 618     {
 619       gimple_call_set_lhs (stmt, NULL_TREE);
 620
 621       /* We need to fix up the SSA name to avoid checking errors.  */
 622       if (TREE_CODE (lhs) == SSA_NAME)
 623         {
 624           tree new_var = create_tmp_reg (TREE_TYPE (lhs));
 625           SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
 626           SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
 627           set_ssa_default_def (cfun, new_var, lhs);
 628         }
 629
 630       update_stmt (stmt);
 631     }
 632
 633   /* Mark the call as altering control flow.  */
 634   if (!gimple_call_ctrl_altering_p (stmt))
 635     {
 636       gimple_call_set_ctrl_altering (stmt, true);
 637       changed = true;
 638     }
 639
 640   return changed;
 641 }
 642
 643
 644 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 645    changes.  */
 646
 647 static bool
 648 cleanup_tree_cfg_bb (basic_block bb)
 649 {
 650   bool retval = cleanup_control_flow_bb (bb);
 651
 652   if (tree_forwarder_block_p (bb, false)
 653       && remove_forwarder_block (bb))
 654     return true;
 655
 656   /* Merging the blocks may create new opportunities for folding
 657      conditional branches (due to the elimination of single-valued PHI
 658      nodes).  */
 659   if (single_succ_p (bb)
 660       && can_merge_blocks_p (bb, single_succ (bb)))
 661     {
 662       /* If there is a merge opportunity with the predecessor
 663          do nothing now but wait until we process the predecessor.
 664          This happens when we visit BBs in a non-optimal order and
 665          avoids quadratic behavior with adjusting stmts BB pointer.  */
 666       if (single_pred_p (bb)
 667           && can_merge_blocks_p (single_pred (bb), bb))
 668         ;
 669       else
 670         {
 671           merge_blocks (bb, single_succ (bb));
 672           return true;
 673         }
 674     }
 675
 676   return retval;
 677 }
 678
 679 /* Iterate the cfg cleanups, while anything changes.  */
 680
 681 static bool
 682 cleanup_tree_cfg_1 (void)
 683 {
 684   bool retval = false;
 685   basic_block bb;
 686   unsigned i, n;
 687
 688   /* Prepare the worklists of altered blocks.  */
 689   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 690
 691   /* During forwarder block cleanup, we may redirect edges out of
 692      SWITCH_EXPRs, which can get expensive.  So we want to enable
 693      recording of edge to CASE_LABEL_EXPR.  */
 694   start_recording_case_labels ();
 695
 696   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB_FN,
 697      since the basic blocks may get removed.  */
 698   n = last_basic_block_for_fn (cfun);
 699   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 700     {
 701       bb = BASIC_BLOCK_FOR_FN (cfun, i);
 702       if (bb)
 703         retval |= cleanup_tree_cfg_bb (bb);
 704     }
 705
 706   /* Now process the altered blocks, as long as any are available.  */
 707   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 708     {
 709       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 710       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 711       if (i < NUM_FIXED_BLOCKS)
 712         continue;
 713
 714       bb = BASIC_BLOCK_FOR_FN (cfun, i);
 715       if (!bb)
 716         continue;
 717
 718       retval |= cleanup_tree_cfg_bb (bb);
 719     }
 720
 721   end_recording_case_labels ();
 722   BITMAP_FREE (cfgcleanup_altered_bbs);
 723   return retval;
 724 }
 725
 726
 727 /* Remove unreachable blocks and other miscellaneous clean up work.
 728    Return true if the flowgraph was modified, false otherwise.  */
 729
 730 static bool
 731 cleanup_tree_cfg_noloop (void)
 732 {
 733   bool changed;
 734
 735   timevar_push (TV_TREE_CLEANUP_CFG);
 736
 737   /* Iterate until there are no more cleanups left to do.  If any
 738      iteration changed the flowgraph, set CHANGED to true.
 739
 740      If dominance information is available, there cannot be any unreachable
 741      blocks.  */
 742   if (!dom_info_available_p (CDI_DOMINATORS))
 743     {
 744       changed = delete_unreachable_blocks ();
 745       calculate_dominance_info (CDI_DOMINATORS);
 746     }
 747   else
 748     {
 749 #ifdef ENABLE_CHECKING
 750       verify_dominators (CDI_DOMINATORS);
 751 #endif
 752       changed = false;
 753     }
 754
 755   changed |= cleanup_tree_cfg_1 ();
 756
 757   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 758   compact_blocks ();
 759
 760 #ifdef ENABLE_CHECKING
 761   verify_flow_info ();
 762 #endif
 763
 764   timevar_pop (TV_TREE_CLEANUP_CFG);
 765
 766   if (changed && current_loops)
 767     loops_state_set (LOOPS_NEED_FIXUP);
 768
 769   return changed;
 770 }
 771
 772 /* Repairs loop structures.  */
 773
 774 static void
 775 repair_loop_structures (void)
 776 {
 777   bitmap changed_bbs;
 778   unsigned n_new_loops;
 779
 780   calculate_dominance_info (CDI_DOMINATORS);
 781
 782   timevar_push (TV_REPAIR_LOOPS);
 783   changed_bbs = BITMAP_ALLOC (NULL);
 784   n_new_loops = fix_loop_structure (changed_bbs);
 785
 786   /* This usually does nothing.  But sometimes parts of cfg that originally
 787      were inside a loop get out of it due to edge removal (since they
 788      become unreachable by back edges from latch).  Also a former
 789      irreducible loop can become reducible - in this case force a full
 790      rewrite into loop-closed SSA form.  */
 791   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 792     rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
 793                                   TODO_update_ssa);
 794
 795   BITMAP_FREE (changed_bbs);
 796
 797 #ifdef ENABLE_CHECKING
 798   verify_loop_structure ();
 799 #endif
 800   scev_reset ();
 801
 802   timevar_pop (TV_REPAIR_LOOPS);
 803 }
 804
 805 /* Cleanup cfg and repair loop structures.  */
 806
 807 bool
 808 cleanup_tree_cfg (void)
 809 {
 810   bool changed = cleanup_tree_cfg_noloop ();
 811
 812   if (current_loops != NULL
 813       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 814     repair_loop_structures ();
 815
 816   return changed;
 817 }
 818
 819 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
 820    Returns true if successful.  */
 821
 822 static bool
 823 remove_forwarder_block_with_phi (basic_block bb)
 824 {
 825   edge succ = single_succ_edge (bb);
 826   basic_block dest = succ->dest;
 827   gimple label;
 828   basic_block dombb, domdest, dom;
 829
 830   /* We check for infinite loops already in tree_forwarder_block_p.
 831      However it may happen that the infinite loop is created
 832      afterwards due to removal of forwarders.  */
 833   if (dest == bb)
 834     return false;
 835
 836   /* If the destination block consists of a nonlocal label, do not
 837      merge it.  */
 838   label = first_stmt (dest);
 839   if (label)
 840     if (glabel *label_stmt = dyn_cast <glabel *> (label))
 841       if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
 842         return false;
 843
 844   /* Record BB's single pred in case we need to update the father
 845      loop's latch information later.  */
 846   basic_block pred = NULL;
 847   if (single_pred_p (bb))
 848     pred = single_pred (bb);
 849
 850   /* Redirect each incoming edge to BB to DEST.  */
 851   while (EDGE_COUNT (bb->preds) > 0)
 852     {
 853       edge e = EDGE_PRED (bb, 0), s;
 854       gphi_iterator gsi;
 855
 856       s = find_edge (e->src, dest);
 857       if (s)
 858         {
 859           /* We already have an edge S from E->src to DEST.  If S and
 860              E->dest's sole successor edge have the same PHI arguments
 861              at DEST, redirect S to DEST.  */
 862           if (phi_alternatives_equal (dest, s, succ))
 863             {
 864               e = redirect_edge_and_branch (e, dest);
 865               redirect_edge_var_map_clear (e);
 866               continue;
 867             }
 868
 869           /* PHI arguments are different.  Create a forwarder block by
 870              splitting E so that we can merge PHI arguments on E to
 871              DEST.  */
 872           e = single_succ_edge (split_edge (e));
 873         }
 874
 875       s = redirect_edge_and_branch (e, dest);
 876
 877       /* redirect_edge_and_branch must not create a new edge.  */
 878       gcc_assert (s == e);
 879
 880       /* Add to the PHI nodes at DEST each PHI argument removed at the
 881          destination of E.  */
 882       for (gsi = gsi_start_phis (dest);
 883            !gsi_end_p (gsi);
 884            gsi_next (&gsi))
 885         {
 886           gphi *phi = gsi.phi ();
 887           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 888           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 889
 890           if (TREE_CODE (def) == SSA_NAME)
 891             {
 892               /* If DEF is one of the results of PHI nodes removed during
 893                  redirection, replace it with the PHI argument that used
 894                  to be on E.  */
 895               vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
 896               size_t length = head ? head->length () : 0;
 897               for (size_t i = 0; i < length; i++)
 898                 {
 899                   edge_var_map *vm = &(*head)[i];
 900                   tree old_arg = redirect_edge_var_map_result (vm);
 901                   tree new_arg = redirect_edge_var_map_def (vm);
 902
 903                   if (def == old_arg)
 904                     {
 905                       def = new_arg;
 906                       locus = redirect_edge_var_map_location (vm);
 907                       break;
 908                     }
 909                 }
 910             }
 911
 912           add_phi_arg (phi, def, s, locus);
 913         }
 914
 915       redirect_edge_var_map_clear (e);
 916     }
 917
 918   /* Update the dominators.  */
 919   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 920   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 921   if (domdest == bb)
 922     {
 923       /* Shortcut to avoid calling (relatively expensive)
 924          nearest_common_dominator unless necessary.  */
 925       dom = dombb;
 926     }
 927   else
 928     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 929
 930   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 931
 932   /* Adjust latch infomation of BB's parent loop as otherwise
 933      the cfg hook has a hard time not to kill the loop.  */
 934   if (current_loops && bb->loop_father->latch == bb)
 935     bb->loop_father->latch = pred;
 936
 937   /* Remove BB since all of BB's incoming edges have been redirected
 938      to DEST.  */
 939   delete_basic_block (bb);
 940
 941   return true;
 942 }
 943
 944 /* This pass merges PHI nodes if one feeds into another.  For example,
 945    suppose we have the following:
 946
 947   goto <bb 9> (<L9>);
 948
 949 <L8>:;
 950   tem_17 = foo ();
 951
 952   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 953 <L9>:;
 954
 955   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 956 <L10>:;
 957
 958   Then we merge the first PHI node into the second one like so:
 959
 960   goto <bb 9> (<L10>);
 961
 962 <L8>:;
 963   tem_17 = foo ();
 964
 965   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 966 <L10>:;
 967 */
 968
 969 namespace {
 970
 971 const pass_data pass_data_merge_phi =
 972 {
 973   GIMPLE_PASS, /* type */
 974   "mergephi", /* name */
 975   OPTGROUP_NONE, /* optinfo_flags */
 976   TV_TREE_MERGE_PHI, /* tv_id */
 977   ( PROP_cfg | PROP_ssa ), /* properties_required */
 978   0, /* properties_provided */
 979   0, /* properties_destroyed */
 980   0, /* todo_flags_start */
 981   0, /* todo_flags_finish */
 982 };
 983
 984 class pass_merge_phi : public gimple_opt_pass
 985 {
 986 public:
 987   pass_merge_phi (gcc::context *ctxt)
 988     : gimple_opt_pass (pass_data_merge_phi, ctxt)
 989   {}
 990
 991   /* opt_pass methods: */
 992   opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
 993   virtual unsigned int execute (function *);
 994
 995 }; // class pass_merge_phi
 996
 997 unsigned int
 998 pass_merge_phi::execute (function *fun)
 999 {
1000   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1001   basic_block *current = worklist;
1002   basic_block bb;
1003
1004   calculate_dominance_info (CDI_DOMINATORS);
1005
1006   /* Find all PHI nodes that we may be able to merge.  */
1007   FOR_EACH_BB_FN (bb, fun)
1008     {
1009       basic_block dest;
1010
1011       /* Look for a forwarder block with PHI nodes.  */
1012       if (!tree_forwarder_block_p (bb, true))
1013         continue;
1014
1015       dest = single_succ (bb);
1016
1017       /* We have to feed into another basic block with PHI
1018          nodes.  */
1019       if (gimple_seq_empty_p (phi_nodes (dest))
1020           /* We don't want to deal with a basic block with
1021              abnormal edges.  */
1022           || bb_has_abnormal_pred (bb))
1023         continue;
1024
1025       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1026         {
1027           /* If BB does not dominate DEST, then the PHI nodes at
1028              DEST must be the only users of the results of the PHI
1029              nodes at BB.  */
1030           *current++ = bb;
1031         }
1032       else
1033         {
1034           gphi_iterator gsi;
1035           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1036
1037           /* BB dominates DEST.  There may be many users of the PHI
1038              nodes in BB.  However, there is still a trivial case we
1039              can handle.  If the result of every PHI in BB is used
1040              only by a PHI in DEST, then we can trivially merge the
1041              PHI nodes from BB into DEST.  */
1042           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1043                gsi_next (&gsi))
1044             {
1045               gphi *phi = gsi.phi ();
1046               tree result = gimple_phi_result (phi);
1047               use_operand_p imm_use;
1048               gimple use_stmt;
1049
1050               /* If the PHI's result is never used, then we can just
1051                  ignore it.  */
1052               if (has_zero_uses (result))
1053                 continue;
1054
1055               /* Get the single use of the result of this PHI node.  */
1056               if (!single_imm_use (result, &imm_use, &use_stmt)
1057                   || gimple_code (use_stmt) != GIMPLE_PHI
1058                   || gimple_bb (use_stmt) != dest
1059                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1060                 break;
1061             }
1062
1063           /* If the loop above iterated through all the PHI nodes
1064              in BB, then we can merge the PHIs from BB into DEST.  */
1065           if (gsi_end_p (gsi))
1066             *current++ = bb;
1067         }
1068     }
1069
1070   /* Now let's drain WORKLIST.  */
1071   bool changed = false;
1072   while (current != worklist)
1073     {
1074       bb = *--current;
1075       changed |= remove_forwarder_block_with_phi (bb);
1076     }
1077   free (worklist);
1078
1079   /* Removing forwarder blocks can cause formerly irreducible loops
1080      to become reducible if we merged two entry blocks.  */
1081   if (changed
1082       && current_loops)
1083     loops_state_set (LOOPS_NEED_FIXUP);
1084
1085   return 0;
1086 }
1087
1088 } // anon namespace
1089
1090 gimple_opt_pass *
1091 make_pass_merge_phi (gcc::context *ctxt)
1092 {
1093   return new pass_merge_phi (ctxt);
1094 }
1095
1096 /* Pass: cleanup the CFG just before expanding trees to RTL.
1097    This is just a round of label cleanups and case node grouping
1098    because after the tree optimizers have run such cleanups may
1099    be necessary.  */
1100
1101 static unsigned int
1102 execute_cleanup_cfg_post_optimizing (void)
1103 {
1104   unsigned int todo = execute_fixup_cfg ();
1105   if (cleanup_tree_cfg ())
1106     {
1107       todo &= ~TODO_cleanup_cfg;
1108       todo |= TODO_update_ssa;
1109     }
1110   maybe_remove_unreachable_handlers ();
1111   cleanup_dead_labels ();
1112   group_case_labels ();
1113   if ((flag_compare_debug_opt || flag_compare_debug)
1114       && flag_dump_final_insns)
1115     {
1116       FILE *final_output = fopen (flag_dump_final_insns, "a");
1117
1118       if (!final_output)
1119         {
1120           error ("could not open final insn dump file %qs: %m",
1121                  flag_dump_final_insns);
1122           flag_dump_final_insns = NULL;
1123         }
1124       else
1125         {
1126           int save_unnumbered = flag_dump_unnumbered;
1127           int save_noaddr = flag_dump_noaddr;
1128
1129           flag_dump_noaddr = flag_dump_unnumbered = 1;
1130           fprintf (final_output, "\n");
1131           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
1132           flag_dump_noaddr = save_noaddr;
1133           flag_dump_unnumbered = save_unnumbered;
1134           if (fclose (final_output))
1135             {
1136               error ("could not close final insn dump file %qs: %m",
1137                      flag_dump_final_insns);
1138               flag_dump_final_insns = NULL;
1139             }
1140         }
1141     }
1142   return todo;
1143 }
1144
1145 namespace {
1146
1147 const pass_data pass_data_cleanup_cfg_post_optimizing =
1148 {
1149   GIMPLE_PASS, /* type */
1150   "optimized", /* name */
1151   OPTGROUP_NONE, /* optinfo_flags */
1152   TV_TREE_CLEANUP_CFG, /* tv_id */
1153   PROP_cfg, /* properties_required */
1154   0, /* properties_provided */
1155   0, /* properties_destroyed */
1156   0, /* todo_flags_start */
1157   TODO_remove_unused_locals, /* todo_flags_finish */
1158 };
1159
1160 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1161 {
1162 public:
1163   pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1164     : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1165   {}
1166
1167   /* opt_pass methods: */
1168   virtual unsigned int execute (function *)
1169     {
1170       return execute_cleanup_cfg_post_optimizing ();
1171     }
1172
1173 }; // class pass_cleanup_cfg_post_optimizing
1174
1175 } // anon namespace
1176
1177 gimple_opt_pass *
1178 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1179 {
1180   return new pass_cleanup_cfg_post_optimizing (ctxt);
1181 }
1182
1183