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.  Fixup the CFG
 583    and remove LHS.  Return true if something changed.  */
 584
 585 bool
 586 fixup_noreturn_call (gimple stmt)
 587 {
 588   basic_block bb = gimple_bb (stmt);
 589
 590   if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
 591     return false;
 592
 593   /* First split basic block if stmt is not last.  */
 594   if (stmt != gsi_stmt (gsi_last_bb (bb)))
 595     {
 596       if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
 597         {
 598           /* Don't split if there are only debug stmts
 599              after stmt, that can result in -fcompare-debug
 600              failures.  Remove the debug stmts instead,
 601              they should be all unreachable anyway.  */
 602           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 603           for (gsi_next (&gsi); !gsi_end_p (gsi); )
 604             gsi_remove (&gsi, true);
 605         }
 606       else
 607         split_block (bb, stmt);
 608     }
 609
 610   /* If there is an LHS, remove it.  */
 611   tree lhs = gimple_call_lhs (stmt);
 612   if (lhs)
 613     {
 614       gimple_call_set_lhs (stmt, NULL_TREE);
 615
 616       /* We need to fix up the SSA name to avoid checking errors.  */
 617       if (TREE_CODE (lhs) == SSA_NAME)
 618         {
 619           tree new_var = create_tmp_reg (TREE_TYPE (lhs));
 620           SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
 621           SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
 622           set_ssa_default_def (cfun, new_var, lhs);
 623         }
 624
 625       update_stmt (stmt);
 626     }
 627
 628   return remove_fallthru_edge (bb->succs);
 629 }
 630
 631
 632 /* Split basic blocks on calls in the middle of a basic block that are now
 633    known not to return, and remove the unreachable code.  */
 634
 635 static bool
 636 split_bb_on_noreturn_calls (basic_block bb)
 637 {
 638   bool changed = false;
 639   gimple_stmt_iterator gsi;
 640
 641   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 642     {
 643       gimple stmt = gsi_stmt (gsi);
 644
 645       if (!is_gimple_call (stmt))
 646         continue;
 647
 648       if (gimple_call_noreturn_p (stmt))
 649         changed |= fixup_noreturn_call (stmt);
 650     }
 651
 652   if (changed)
 653     bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
 654   return changed;
 655 }
 656
 657 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 658    changes.  */
 659
 660 static bool
 661 cleanup_tree_cfg_bb (basic_block bb)
 662 {
 663   bool retval = cleanup_control_flow_bb (bb);
 664
 665   if (tree_forwarder_block_p (bb, false)
 666       && remove_forwarder_block (bb))
 667     return true;
 668
 669   /* Merging the blocks may create new opportunities for folding
 670      conditional branches (due to the elimination of single-valued PHI
 671      nodes).  */
 672   if (single_succ_p (bb)
 673       && can_merge_blocks_p (bb, single_succ (bb)))
 674     {
 675       merge_blocks (bb, single_succ (bb));
 676       return true;
 677     }
 678
 679   return retval;
 680 }
 681
 682 /* Iterate the cfg cleanups, while anything changes.  */
 683
 684 static bool
 685 cleanup_tree_cfg_1 (void)
 686 {
 687   bool retval = false;
 688   basic_block bb;
 689   unsigned i, n;
 690
 691   /* Prepare the worklists of altered blocks.  */
 692   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 693
 694   /* During forwarder block cleanup, we may redirect edges out of
 695      SWITCH_EXPRs, which can get expensive.  So we want to enable
 696      recording of edge to CASE_LABEL_EXPR.  */
 697   start_recording_case_labels ();
 698
 699   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB_FN,
 700      since the basic blocks may get removed.  */
 701   n = last_basic_block_for_fn (cfun);
 702   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 703     {
 704       bb = BASIC_BLOCK_FOR_FN (cfun, i);
 705       if (bb)
 706         {
 707           retval |= cleanup_tree_cfg_bb (bb);
 708           retval |= split_bb_on_noreturn_calls (bb);
 709         }
 710     }
 711
 712   /* Now process the altered blocks, as long as any are available.  */
 713   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 714     {
 715       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 716       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 717       if (i < NUM_FIXED_BLOCKS)
 718         continue;
 719
 720       bb = BASIC_BLOCK_FOR_FN (cfun, i);
 721       if (!bb)
 722         continue;
 723
 724       retval |= cleanup_tree_cfg_bb (bb);
 725
 726       /* Rerun split_bb_on_noreturn_calls, in case we have altered any noreturn
 727          calls.  */
 728       retval |= split_bb_on_noreturn_calls (bb);
 729     }
 730
 731   end_recording_case_labels ();
 732   BITMAP_FREE (cfgcleanup_altered_bbs);
 733   return retval;
 734 }
 735
 736
 737 /* Remove unreachable blocks and other miscellaneous clean up work.
 738    Return true if the flowgraph was modified, false otherwise.  */
 739
 740 static bool
 741 cleanup_tree_cfg_noloop (void)
 742 {
 743   bool changed;
 744
 745   timevar_push (TV_TREE_CLEANUP_CFG);
 746
 747   /* Iterate until there are no more cleanups left to do.  If any
 748      iteration changed the flowgraph, set CHANGED to true.
 749
 750      If dominance information is available, there cannot be any unreachable
 751      blocks.  */
 752   if (!dom_info_available_p (CDI_DOMINATORS))
 753     {
 754       changed = delete_unreachable_blocks ();
 755       calculate_dominance_info (CDI_DOMINATORS);
 756     }
 757   else
 758     {
 759 #ifdef ENABLE_CHECKING
 760       verify_dominators (CDI_DOMINATORS);
 761 #endif
 762       changed = false;
 763     }
 764
 765   changed |= cleanup_tree_cfg_1 ();
 766
 767   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 768   compact_blocks ();
 769
 770 #ifdef ENABLE_CHECKING
 771   verify_flow_info ();
 772 #endif
 773
 774   timevar_pop (TV_TREE_CLEANUP_CFG);
 775
 776   if (changed && current_loops)
 777     loops_state_set (LOOPS_NEED_FIXUP);
 778
 779   return changed;
 780 }
 781
 782 /* Repairs loop structures.  */
 783
 784 static void
 785 repair_loop_structures (void)
 786 {
 787   bitmap changed_bbs;
 788   unsigned n_new_loops;
 789
 790   calculate_dominance_info (CDI_DOMINATORS);
 791
 792   timevar_push (TV_REPAIR_LOOPS);
 793   changed_bbs = BITMAP_ALLOC (NULL);
 794   n_new_loops = fix_loop_structure (changed_bbs);
 795
 796   /* This usually does nothing.  But sometimes parts of cfg that originally
 797      were inside a loop get out of it due to edge removal (since they
 798      become unreachable by back edges from latch).  Also a former
 799      irreducible loop can become reducible - in this case force a full
 800      rewrite into loop-closed SSA form.  */
 801   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 802     rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
 803                                   TODO_update_ssa);
 804
 805   BITMAP_FREE (changed_bbs);
 806
 807 #ifdef ENABLE_CHECKING
 808   verify_loop_structure ();
 809 #endif
 810   scev_reset ();
 811
 812   timevar_pop (TV_REPAIR_LOOPS);
 813 }
 814
 815 /* Cleanup cfg and repair loop structures.  */
 816
 817 bool
 818 cleanup_tree_cfg (void)
 819 {
 820   bool changed = cleanup_tree_cfg_noloop ();
 821
 822   if (current_loops != NULL
 823       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 824     repair_loop_structures ();
 825
 826   return changed;
 827 }
 828
 829 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
 830    Returns true if successful.  */
 831
 832 static bool
 833 remove_forwarder_block_with_phi (basic_block bb)
 834 {
 835   edge succ = single_succ_edge (bb);
 836   basic_block dest = succ->dest;
 837   gimple label;
 838   basic_block dombb, domdest, dom;
 839
 840   /* We check for infinite loops already in tree_forwarder_block_p.
 841      However it may happen that the infinite loop is created
 842      afterwards due to removal of forwarders.  */
 843   if (dest == bb)
 844     return false;
 845
 846   /* If the destination block consists of a nonlocal label, do not
 847      merge it.  */
 848   label = first_stmt (dest);
 849   if (label)
 850     if (glabel *label_stmt = dyn_cast <glabel *> (label))
 851       if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
 852         return false;
 853
 854   /* Record BB's single pred in case we need to update the father
 855      loop's latch information later.  */
 856   basic_block pred = NULL;
 857   if (single_pred_p (bb))
 858     pred = single_pred (bb);
 859
 860   /* Redirect each incoming edge to BB to DEST.  */
 861   while (EDGE_COUNT (bb->preds) > 0)
 862     {
 863       edge e = EDGE_PRED (bb, 0), s;
 864       gphi_iterator gsi;
 865
 866       s = find_edge (e->src, dest);
 867       if (s)
 868         {
 869           /* We already have an edge S from E->src to DEST.  If S and
 870              E->dest's sole successor edge have the same PHI arguments
 871              at DEST, redirect S to DEST.  */
 872           if (phi_alternatives_equal (dest, s, succ))
 873             {
 874               e = redirect_edge_and_branch (e, dest);
 875               redirect_edge_var_map_clear (e);
 876               continue;
 877             }
 878
 879           /* PHI arguments are different.  Create a forwarder block by
 880              splitting E so that we can merge PHI arguments on E to
 881              DEST.  */
 882           e = single_succ_edge (split_edge (e));
 883         }
 884
 885       s = redirect_edge_and_branch (e, dest);
 886
 887       /* redirect_edge_and_branch must not create a new edge.  */
 888       gcc_assert (s == e);
 889
 890       /* Add to the PHI nodes at DEST each PHI argument removed at the
 891          destination of E.  */
 892       for (gsi = gsi_start_phis (dest);
 893            !gsi_end_p (gsi);
 894            gsi_next (&gsi))
 895         {
 896           gphi *phi = gsi.phi ();
 897           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 898           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 899
 900           if (TREE_CODE (def) == SSA_NAME)
 901             {
 902               /* If DEF is one of the results of PHI nodes removed during
 903                  redirection, replace it with the PHI argument that used
 904                  to be on E.  */
 905               vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
 906               size_t length = head ? head->length () : 0;
 907               for (size_t i = 0; i < length; i++)
 908                 {
 909                   edge_var_map *vm = &(*head)[i];
 910                   tree old_arg = redirect_edge_var_map_result (vm);
 911                   tree new_arg = redirect_edge_var_map_def (vm);
 912
 913                   if (def == old_arg)
 914                     {
 915                       def = new_arg;
 916                       locus = redirect_edge_var_map_location (vm);
 917                       break;
 918                     }
 919                 }
 920             }
 921
 922           add_phi_arg (phi, def, s, locus);
 923         }
 924
 925       redirect_edge_var_map_clear (e);
 926     }
 927
 928   /* Update the dominators.  */
 929   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 930   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 931   if (domdest == bb)
 932     {
 933       /* Shortcut to avoid calling (relatively expensive)
 934          nearest_common_dominator unless necessary.  */
 935       dom = dombb;
 936     }
 937   else
 938     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 939
 940   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 941
 942   /* Adjust latch infomation of BB's parent loop as otherwise
 943      the cfg hook has a hard time not to kill the loop.  */
 944   if (current_loops && bb->loop_father->latch == bb)
 945     bb->loop_father->latch = pred;
 946
 947   /* Remove BB since all of BB's incoming edges have been redirected
 948      to DEST.  */
 949   delete_basic_block (bb);
 950
 951   return true;
 952 }
 953
 954 /* This pass merges PHI nodes if one feeds into another.  For example,
 955    suppose we have the following:
 956
 957   goto <bb 9> (<L9>);
 958
 959 <L8>:;
 960   tem_17 = foo ();
 961
 962   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 963 <L9>:;
 964
 965   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 966 <L10>:;
 967
 968   Then we merge the first PHI node into the second one like so:
 969
 970   goto <bb 9> (<L10>);
 971
 972 <L8>:;
 973   tem_17 = foo ();
 974
 975   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 976 <L10>:;
 977 */
 978
 979 namespace {
 980
 981 const pass_data pass_data_merge_phi =
 982 {
 983   GIMPLE_PASS, /* type */
 984   "mergephi", /* name */
 985   OPTGROUP_NONE, /* optinfo_flags */
 986   TV_TREE_MERGE_PHI, /* tv_id */
 987   ( PROP_cfg | PROP_ssa ), /* properties_required */
 988   0, /* properties_provided */
 989   0, /* properties_destroyed */
 990   0, /* todo_flags_start */
 991   0, /* todo_flags_finish */
 992 };
 993
 994 class pass_merge_phi : public gimple_opt_pass
 995 {
 996 public:
 997   pass_merge_phi (gcc::context *ctxt)
 998     : gimple_opt_pass (pass_data_merge_phi, ctxt)
 999   {}
1000
1001   /* opt_pass methods: */
1002   opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
1003   virtual unsigned int execute (function *);
1004
1005 }; // class pass_merge_phi
1006
1007 unsigned int
1008 pass_merge_phi::execute (function *fun)
1009 {
1010   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1011   basic_block *current = worklist;
1012   basic_block bb;
1013
1014   calculate_dominance_info (CDI_DOMINATORS);
1015
1016   /* Find all PHI nodes that we may be able to merge.  */
1017   FOR_EACH_BB_FN (bb, fun)
1018     {
1019       basic_block dest;
1020
1021       /* Look for a forwarder block with PHI nodes.  */
1022       if (!tree_forwarder_block_p (bb, true))
1023         continue;
1024
1025       dest = single_succ (bb);
1026
1027       /* We have to feed into another basic block with PHI
1028          nodes.  */
1029       if (gimple_seq_empty_p (phi_nodes (dest))
1030           /* We don't want to deal with a basic block with
1031              abnormal edges.  */
1032           || bb_has_abnormal_pred (bb))
1033         continue;
1034
1035       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1036         {
1037           /* If BB does not dominate DEST, then the PHI nodes at
1038              DEST must be the only users of the results of the PHI
1039              nodes at BB.  */
1040           *current++ = bb;
1041         }
1042       else
1043         {
1044           gphi_iterator gsi;
1045           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1046
1047           /* BB dominates DEST.  There may be many users of the PHI
1048              nodes in BB.  However, there is still a trivial case we
1049              can handle.  If the result of every PHI in BB is used
1050              only by a PHI in DEST, then we can trivially merge the
1051              PHI nodes from BB into DEST.  */
1052           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1053                gsi_next (&gsi))
1054             {
1055               gphi *phi = gsi.phi ();
1056               tree result = gimple_phi_result (phi);
1057               use_operand_p imm_use;
1058               gimple use_stmt;
1059
1060               /* If the PHI's result is never used, then we can just
1061                  ignore it.  */
1062               if (has_zero_uses (result))
1063                 continue;
1064
1065               /* Get the single use of the result of this PHI node.  */
1066               if (!single_imm_use (result, &imm_use, &use_stmt)
1067                   || gimple_code (use_stmt) != GIMPLE_PHI
1068                   || gimple_bb (use_stmt) != dest
1069                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1070                 break;
1071             }
1072
1073           /* If the loop above iterated through all the PHI nodes
1074              in BB, then we can merge the PHIs from BB into DEST.  */
1075           if (gsi_end_p (gsi))
1076             *current++ = bb;
1077         }
1078     }
1079
1080   /* Now let's drain WORKLIST.  */
1081   bool changed = false;
1082   while (current != worklist)
1083     {
1084       bb = *--current;
1085       changed |= remove_forwarder_block_with_phi (bb);
1086     }
1087   free (worklist);
1088
1089   /* Removing forwarder blocks can cause formerly irreducible loops
1090      to become reducible if we merged two entry blocks.  */
1091   if (changed
1092       && current_loops)
1093     loops_state_set (LOOPS_NEED_FIXUP);
1094
1095   return 0;
1096 }
1097
1098 } // anon namespace
1099
1100 gimple_opt_pass *
1101 make_pass_merge_phi (gcc::context *ctxt)
1102 {
1103   return new pass_merge_phi (ctxt);
1104 }
1105
1106 /* Pass: cleanup the CFG just before expanding trees to RTL.
1107    This is just a round of label cleanups and case node grouping
1108    because after the tree optimizers have run such cleanups may
1109    be necessary.  */
1110
1111 static unsigned int
1112 execute_cleanup_cfg_post_optimizing (void)
1113 {
1114   unsigned int todo = 0;
1115   if (cleanup_tree_cfg ())
1116     todo |= TODO_update_ssa;
1117   maybe_remove_unreachable_handlers ();
1118   cleanup_dead_labels ();
1119   group_case_labels ();
1120   if ((flag_compare_debug_opt || flag_compare_debug)
1121       && flag_dump_final_insns)
1122     {
1123       FILE *final_output = fopen (flag_dump_final_insns, "a");
1124
1125       if (!final_output)
1126         {
1127           error ("could not open final insn dump file %qs: %m",
1128                  flag_dump_final_insns);
1129           flag_dump_final_insns = NULL;
1130         }
1131       else
1132         {
1133           int save_unnumbered = flag_dump_unnumbered;
1134           int save_noaddr = flag_dump_noaddr;
1135
1136           flag_dump_noaddr = flag_dump_unnumbered = 1;
1137           fprintf (final_output, "\n");
1138           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
1139           flag_dump_noaddr = save_noaddr;
1140           flag_dump_unnumbered = save_unnumbered;
1141           if (fclose (final_output))
1142             {
1143               error ("could not close final insn dump file %qs: %m",
1144                      flag_dump_final_insns);
1145               flag_dump_final_insns = NULL;
1146             }
1147         }
1148     }
1149   return todo;
1150 }
1151
1152 namespace {
1153
1154 const pass_data pass_data_cleanup_cfg_post_optimizing =
1155 {
1156   GIMPLE_PASS, /* type */
1157   "optimized", /* name */
1158   OPTGROUP_NONE, /* optinfo_flags */
1159   TV_TREE_CLEANUP_CFG, /* tv_id */
1160   PROP_cfg, /* properties_required */
1161   0, /* properties_provided */
1162   0, /* properties_destroyed */
1163   0, /* todo_flags_start */
1164   TODO_remove_unused_locals, /* todo_flags_finish */
1165 };
1166
1167 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1168 {
1169 public:
1170   pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1171     : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1172   {}
1173
1174   /* opt_pass methods: */
1175   virtual unsigned int execute (function *)
1176     {
1177       return execute_cleanup_cfg_post_optimizing ();
1178     }
1179
1180 }; // class pass_cleanup_cfg_post_optimizing
1181
1182 } // anon namespace
1183
1184 gimple_opt_pass *
1185 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1186 {
1187   return new pass_cleanup_cfg_post_optimizing (ctxt);
1188 }
1189
1190