gcc/tree-cfgcleanup.c

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