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