gcc/tree-cfgcleanup.c

   1 /* CFG cleanup for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "toplev.h"
  32 #include "flags.h"
  33 #include "function.h"
  34 #include "expr.h"
  35 #include "ggc.h"
  36 #include "langhooks.h"
  37 #include "diagnostic.h"
  38 #include "tree-flow.h"
  39 #include "timevar.h"
  40 #include "tree-dump.h"
  41 #include "tree-pass.h"
  42 #include "toplev.h"
  43 #include "except.h"
  44 #include "cfgloop.h"
  45 #include "cfglayout.h"
  46 #include "hashtab.h"
  47 #include "tree-ssa-propagate.h"
  48 #include "tree-scalar-evolution.h"
  49
  50 /* The set of blocks in that at least one of the following changes happened:
  51    -- the statement at the end of the block was changed
  52    -- the block was newly created
  53    -- the set of the predecessors of the block changed
  54    -- the set of the successors of the block changed
  55    ??? Maybe we could track these changes separately, since they determine
  56        what cleanups it makes sense to try on the block.  */
  57 bitmap cfgcleanup_altered_bbs;
  58
  59 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
  60
  61 static bool
  62 remove_fallthru_edge (VEC(edge,gc) *ev)
  63 {
  64   edge_iterator ei;
  65   edge e;
  66
  67   FOR_EACH_EDGE (e, ei, ev)
  68     if ((e->flags & EDGE_FALLTHRU) != 0)
  69       {
  70         remove_edge_and_dominated_blocks (e);
  71         return true;
  72       }
  73   return false;
  74 }
  75
  76
  77 /* Disconnect an unreachable block in the control expression starting
  78    at block BB.  */
  79
  80 static bool
  81 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
  82 {
  83   edge taken_edge;
  84   bool retval = false;
  85   gimple stmt = gsi_stmt (gsi);
  86   tree val;
  87
  88   if (!single_succ_p (bb))
  89     {
  90       edge e;
  91       edge_iterator ei;
  92       bool warned;
  93
  94       fold_defer_overflow_warnings ();
  95       val = gimple_fold (stmt);
  96       taken_edge = find_taken_edge (bb, val);
  97       if (!taken_edge)
  98         {
  99           fold_undefer_and_ignore_overflow_warnings ();
 100           return false;
 101         }
 102
 103       /* Remove all the edges except the one that is always executed.  */
 104       warned = false;
 105       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 106         {
 107           if (e != taken_edge)
 108             {
 109               if (!warned)
 110                 {
 111                   fold_undefer_overflow_warnings
 112                     (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
 113                   warned = true;
 114                 }
 115
 116               taken_edge->probability += e->probability;
 117               taken_edge->count += e->count;
 118               remove_edge_and_dominated_blocks (e);
 119               retval = true;
 120             }
 121           else
 122             ei_next (&ei);
 123         }
 124       if (!warned)
 125         fold_undefer_and_ignore_overflow_warnings ();
 126       if (taken_edge->probability > REG_BR_PROB_BASE)
 127         taken_edge->probability = REG_BR_PROB_BASE;
 128     }
 129   else
 130     taken_edge = single_succ_edge (bb);
 131
 132   bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
 133   gsi_remove (&gsi, true);
 134   taken_edge->flags = EDGE_FALLTHRU;
 135
 136   return retval;
 137 }
 138
 139 /* Try to remove superfluous control structures in basic block BB.  Returns
 140    true if anything changes.  */
 141
 142 static bool
 143 cleanup_control_flow_bb (basic_block bb)
 144 {
 145   gimple_stmt_iterator gsi;
 146   bool retval = false;
 147   gimple stmt;
 148
 149   /* If the last statement of the block could throw and now cannot,
 150      we need to prune cfg.  */
 151   retval |= gimple_purge_dead_eh_edges (bb);
 152
 153   gsi = gsi_last_bb (bb);
 154   if (gsi_end_p (gsi))
 155     return retval;
 156
 157   stmt = gsi_stmt (gsi);
 158
 159   if (gimple_code (stmt) == GIMPLE_COND
 160       || gimple_code (stmt) == GIMPLE_SWITCH)
 161     retval |= cleanup_control_expr_graph (bb, gsi);
 162   else if (gimple_code (stmt) == GIMPLE_GOTO
 163            && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
 164            && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
 165                == LABEL_DECL))
 166     {
 167       /* If we had a computed goto which has a compile-time determinable
 168          destination, then we can eliminate the goto.  */
 169       edge e;
 170       tree label;
 171       edge_iterator ei;
 172       basic_block target_block;
 173
 174       /* First look at all the outgoing edges.  Delete any outgoing
 175          edges which do not go to the right block.  For the one
 176          edge which goes to the right block, fix up its flags.  */
 177       label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
 178       target_block = label_to_block (label);
 179       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 180         {
 181           if (e->dest != target_block)
 182             remove_edge_and_dominated_blocks (e);
 183           else
 184             {
 185               /* Turn off the EDGE_ABNORMAL flag.  */
 186               e->flags &= ~EDGE_ABNORMAL;
 187
 188               /* And set EDGE_FALLTHRU.  */
 189               e->flags |= EDGE_FALLTHRU;
 190               ei_next (&ei);
 191             }
 192         }
 193
 194       bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
 195       bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
 196
 197       /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
 198          relevant information we need.  */
 199       gsi_remove (&gsi, true);
 200       retval = true;
 201     }
 202
 203   /* Check for indirect calls that have been turned into
 204      noreturn calls.  */
 205   else if (is_gimple_call (stmt)
 206            && gimple_call_noreturn_p (stmt)
 207            && remove_fallthru_edge (bb->succs))
 208     retval = true;
 209
 210   return retval;
 211 }
 212
 213 /* Return true if basic block BB does nothing except pass control
 214    flow to another block and that we can safely insert a label at
 215    the start of the successor block.
 216
 217    As a precondition, we require that BB be not equal to
 218    ENTRY_BLOCK_PTR.  */
 219
 220 static bool
 221 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
 222 {
 223   gimple_stmt_iterator gsi;
 224
 225   /* BB must have a single outgoing edge.  */
 226   if (single_succ_p (bb) != 1
 227       /* If PHI_WANTED is false, BB must not have any PHI nodes.
 228          Otherwise, BB must have PHI nodes.  */
 229       || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
 230       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
 231       || single_succ (bb) == EXIT_BLOCK_PTR
 232       /* Nor should this be an infinite loop.  */
 233       || single_succ (bb) == bb
 234       /* BB may not have an abnormal outgoing edge.  */
 235       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
 236     return false;
 237
 238 #if ENABLE_CHECKING
 239   gcc_assert (bb != ENTRY_BLOCK_PTR);
 240 #endif
 241
 242   /* There should not be an edge coming from entry, or an EH edge.  */
 243   {
 244     edge_iterator ei;
 245     edge e;
 246
 247     FOR_EACH_EDGE (e, ei, bb->preds)
 248       if (e->src == ENTRY_BLOCK_PTR || (e->flags & EDGE_EH))
 249         return false;
 250   }
 251
 252   /* Now walk through the statements backward.  We can ignore labels,
 253      anything else means this is not a forwarder block.  */
 254   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 255     {
 256       gimple stmt = gsi_stmt (gsi);
 257
 258       switch (gimple_code (stmt))
 259         {
 260         case GIMPLE_LABEL:
 261           if (DECL_NONLOCAL (gimple_label_label (stmt)))
 262             return false;
 263           break;
 264
 265           /* ??? For now, hope there's a corresponding debug
 266              assignment at the destination.  */
 267         case GIMPLE_DEBUG:
 268           break;
 269
 270         default:
 271           return false;
 272         }
 273     }
 274
 275   if (current_loops)
 276     {
 277       basic_block dest;
 278       /* Protect loop latches, headers and preheaders.  */
 279       if (bb->loop_father->header == bb)
 280         return false;
 281       dest = EDGE_SUCC (bb, 0)->dest;
 282
 283       if (dest->loop_father->header == dest)
 284         return false;
 285     }
 286   return true;
 287 }
 288
 289 /* Return true if BB has at least one abnormal incoming edge.  */
 290
 291 static inline bool
 292 has_abnormal_incoming_edge_p (basic_block bb)
 293 {
 294   edge e;
 295   edge_iterator ei;
 296
 297   FOR_EACH_EDGE (e, ei, bb->preds)
 298     if (e->flags & EDGE_ABNORMAL)
 299       return true;
 300
 301   return false;
 302 }
 303
 304 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
 305    those alternatives are equal in each of the PHI nodes, then return
 306    true, else return false.  */
 307
 308 static bool
 309 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 310 {
 311   int n1 = e1->dest_idx;
 312   int n2 = e2->dest_idx;
 313   gimple_stmt_iterator gsi;
 314
 315   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 316     {
 317       gimple phi = gsi_stmt (gsi);
 318       tree val1 = gimple_phi_arg_def (phi, n1);
 319       tree val2 = gimple_phi_arg_def (phi, n2);
 320
 321       gcc_assert (val1 != NULL_TREE);
 322       gcc_assert (val2 != NULL_TREE);
 323
 324       if (!operand_equal_for_phi_arg_p (val1, val2))
 325         return false;
 326     }
 327
 328   return true;
 329 }
 330
 331 /* Removes forwarder block BB.  Returns false if this failed.  */
 332
 333 static bool
 334 remove_forwarder_block (basic_block bb)
 335 {
 336   edge succ = single_succ_edge (bb), e, s;
 337   basic_block dest = succ->dest;
 338   gimple label;
 339   edge_iterator ei;
 340   gimple_stmt_iterator gsi, gsi_to;
 341
 342   /* We check for infinite loops already in tree_forwarder_block_p.
 343      However it may happen that the infinite loop is created
 344      afterwards due to removal of forwarders.  */
 345   if (dest == bb)
 346     return false;
 347
 348   /* If the destination block consists of a nonlocal label, do not merge
 349      it.  */
 350   label = first_stmt (dest);
 351   if (label
 352       && gimple_code (label) == GIMPLE_LABEL
 353       && DECL_NONLOCAL (gimple_label_label (label)))
 354     return false;
 355
 356   /* If there is an abnormal edge to basic block BB, but not into
 357      dest, problems might occur during removal of the phi node at out
 358      of ssa due to overlapping live ranges of registers.
 359
 360      If there is an abnormal edge in DEST, the problems would occur
 361      anyway since cleanup_dead_labels would then merge the labels for
 362      two different eh regions, and rest of exception handling code
 363      does not like it.
 364
 365      So if there is an abnormal edge to BB, proceed only if there is
 366      no abnormal edge to DEST and there are no phi nodes in DEST.  */
 367   if (has_abnormal_incoming_edge_p (bb)
 368       && (has_abnormal_incoming_edge_p (dest)
 369           || !gimple_seq_empty_p (phi_nodes (dest))))
 370     return false;
 371
 372   /* If there are phi nodes in DEST, and some of the blocks that are
 373      predecessors of BB are also predecessors of DEST, check that the
 374      phi node arguments match.  */
 375   if (!gimple_seq_empty_p (phi_nodes (dest)))
 376     {
 377       FOR_EACH_EDGE (e, ei, bb->preds)
 378         {
 379           s = find_edge (e->src, dest);
 380           if (!s)
 381             continue;
 382
 383           if (!phi_alternatives_equal (dest, succ, s))
 384             return false;
 385         }
 386     }
 387
 388   /* Redirect the edges.  */
 389   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 390     {
 391       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
 392
 393       if (e->flags & EDGE_ABNORMAL)
 394         {
 395           /* If there is an abnormal edge, redirect it anyway, and
 396              move the labels to the new block to make it legal.  */
 397           s = redirect_edge_succ_nodup (e, dest);
 398         }
 399       else
 400         s = redirect_edge_and_branch (e, dest);
 401
 402       if (s == e)
 403         {
 404           /* Create arguments for the phi nodes, since the edge was not
 405              here before.  */
 406           for (gsi = gsi_start_phis (dest);
 407                !gsi_end_p (gsi);
 408                gsi_next (&gsi))
 409             {
 410               gimple phi = gsi_stmt (gsi);
 411               source_location l = gimple_phi_arg_location_from_edge (phi, succ);
 412               add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s, l);
 413             }
 414         }
 415     }
 416
 417   /* Move nonlocal labels and computed goto targets as well as user
 418      defined labels and labels with an EH landing pad number to the
 419      new block, so that the redirection of the abnormal edges works,
 420      jump targets end up in a sane place and debug information for
 421      labels is retained.  */
 422   gsi_to = gsi_start_bb (dest);
 423   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 424     {
 425       tree decl;
 426       label = gsi_stmt (gsi);
 427       if (is_gimple_debug (label))
 428         break;
 429       decl = gimple_label_label (label);
 430       if (EH_LANDING_PAD_NR (decl) != 0
 431           || DECL_NONLOCAL (decl)
 432           || FORCED_LABEL (decl)
 433           || !DECL_ARTIFICIAL (decl))
 434         {
 435           gsi_remove (&gsi, false);
 436           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 437         }
 438       else
 439         gsi_next (&gsi);
 440     }
 441
 442   /* Move debug statements if the destination has just a single
 443      predecessor.  */
 444   if (single_pred_p (dest))
 445     {
 446       gsi_to = gsi_after_labels (dest);
 447       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
 448         {
 449           if (!is_gimple_debug (gsi_stmt (gsi)))
 450             break;
 451           gsi_remove (&gsi, false);
 452           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 453         }
 454     }
 455
 456   bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
 457
 458   /* Update the dominators.  */
 459   if (dom_info_available_p (CDI_DOMINATORS))
 460     {
 461       basic_block dom, dombb, domdest;
 462
 463       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 464       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 465       if (domdest == bb)
 466         {
 467           /* Shortcut to avoid calling (relatively expensive)
 468              nearest_common_dominator unless necessary.  */
 469           dom = dombb;
 470         }
 471       else
 472         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 473
 474       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 475     }
 476
 477   /* And kill the forwarder block.  */
 478   delete_basic_block (bb);
 479
 480   return true;
 481 }
 482
 483 /* Split basic blocks on calls in the middle of a basic block that are now
 484    known not to return, and remove the unreachable code.  */
 485
 486 static bool
 487 split_bbs_on_noreturn_calls (void)
 488 {
 489   bool changed = false;
 490   gimple stmt;
 491   basic_block bb;
 492
 493   /* Detect cases where a mid-block call is now known not to return.  */
 494   if (cfun->gimple_df)
 495     while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
 496       {
 497         stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
 498         bb = gimple_bb (stmt);
 499         /* BB might be deleted at this point, so verify first
 500            BB is present in the cfg.  */
 501         if (bb == NULL
 502             || bb->index < NUM_FIXED_BLOCKS
 503             || bb->index >= n_basic_blocks
 504             || BASIC_BLOCK (bb->index) != bb
 505             || last_stmt (bb) == stmt
 506             || !gimple_call_noreturn_p (stmt))
 507           continue;
 508
 509         changed = true;
 510         split_block (bb, stmt);
 511         remove_fallthru_edge (bb->succs);
 512       }
 513
 514   return changed;
 515 }
 516
 517 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it.  */
 518
 519 static bool
 520 cleanup_omp_return (basic_block bb)
 521 {
 522   gimple stmt = last_stmt (bb);
 523   basic_block control_bb;
 524
 525   if (stmt == NULL
 526       || gimple_code (stmt) != GIMPLE_OMP_RETURN
 527       || !single_pred_p (bb))
 528     return false;
 529
 530   control_bb = single_pred (bb);
 531   stmt = last_stmt (control_bb);
 532
 533   if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
 534     return false;
 535
 536   /* The block with the control statement normally has two entry edges -- one
 537      from entry, one from continue.  If continue is removed, return is
 538      unreachable, so we remove it here as well.  */
 539   if (EDGE_COUNT (control_bb->preds) == 2)
 540     return false;
 541
 542   gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
 543   remove_edge_and_dominated_blocks (single_pred_edge (bb));
 544   return true;
 545 }
 546
 547 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 548    changes.  */
 549
 550 static bool
 551 cleanup_tree_cfg_bb (basic_block bb)
 552 {
 553   bool retval = false;
 554
 555   if (cleanup_omp_return (bb))
 556     return true;
 557
 558   retval = cleanup_control_flow_bb (bb);
 559
 560   /* Forwarder blocks can carry line number information which is
 561      useful when debugging, so we only clean them up when
 562      optimizing.  */
 563   if (optimize > 0
 564       && tree_forwarder_block_p (bb, false)
 565       && remove_forwarder_block (bb))
 566     return true;
 567
 568   /* Merging the blocks may create new opportunities for folding
 569      conditional branches (due to the elimination of single-valued PHI
 570      nodes).  */
 571   if (single_succ_p (bb)
 572       && can_merge_blocks_p (bb, single_succ (bb)))
 573     {
 574       merge_blocks (bb, single_succ (bb));
 575       return true;
 576     }
 577
 578   return retval;
 579 }
 580
 581 /* Iterate the cfg cleanups, while anything changes.  */
 582
 583 static bool
 584 cleanup_tree_cfg_1 (void)
 585 {
 586   bool retval = false;
 587   basic_block bb;
 588   unsigned i, n;
 589
 590   retval |= split_bbs_on_noreturn_calls ();
 591
 592   /* Prepare the worklists of altered blocks.  */
 593   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 594
 595   /* During forwarder block cleanup, we may redirect edges out of
 596      SWITCH_EXPRs, which can get expensive.  So we want to enable
 597      recording of edge to CASE_LABEL_EXPR.  */
 598   start_recording_case_labels ();
 599
 600   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB,
 601      since the basic blocks may get removed.  */
 602   n = last_basic_block;
 603   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 604     {
 605       bb = BASIC_BLOCK (i);
 606       if (bb)
 607         retval |= cleanup_tree_cfg_bb (bb);
 608     }
 609
 610   /* Now process the altered blocks, as long as any are available.  */
 611   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 612     {
 613       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 614       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 615       if (i < NUM_FIXED_BLOCKS)
 616         continue;
 617
 618       bb = BASIC_BLOCK (i);
 619       if (!bb)
 620         continue;
 621
 622       retval |= cleanup_tree_cfg_bb (bb);
 623
 624       /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
 625          calls.  */
 626       retval |= split_bbs_on_noreturn_calls ();
 627     }
 628
 629   end_recording_case_labels ();
 630   BITMAP_FREE (cfgcleanup_altered_bbs);
 631   return retval;
 632 }
 633
 634
 635 /* Remove unreachable blocks and other miscellaneous clean up work.
 636    Return true if the flowgraph was modified, false otherwise.  */
 637
 638 static bool
 639 cleanup_tree_cfg_noloop (void)
 640 {
 641   bool changed;
 642
 643   timevar_push (TV_TREE_CLEANUP_CFG);
 644
 645   /* Iterate until there are no more cleanups left to do.  If any
 646      iteration changed the flowgraph, set CHANGED to true.
 647
 648      If dominance information is available, there cannot be any unreachable
 649      blocks.  */
 650   if (!dom_info_available_p (CDI_DOMINATORS))
 651     {
 652       changed = delete_unreachable_blocks ();
 653       calculate_dominance_info (CDI_DOMINATORS);
 654     }
 655   else
 656     {
 657 #ifdef ENABLE_CHECKING
 658       verify_dominators (CDI_DOMINATORS);
 659 #endif
 660       changed = false;
 661     }
 662
 663   changed |= cleanup_tree_cfg_1 ();
 664
 665   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 666   compact_blocks ();
 667
 668 #ifdef ENABLE_CHECKING
 669   verify_flow_info ();
 670 #endif
 671
 672   timevar_pop (TV_TREE_CLEANUP_CFG);
 673
 674   if (changed && current_loops)
 675     loops_state_set (LOOPS_NEED_FIXUP);
 676
 677   return changed;
 678 }
 679
 680 /* Repairs loop structures.  */
 681
 682 static void
 683 repair_loop_structures (void)
 684 {
 685   bitmap changed_bbs = BITMAP_ALLOC (NULL);
 686   fix_loop_structure (changed_bbs);
 687
 688   /* This usually does nothing.  But sometimes parts of cfg that originally
 689      were inside a loop get out of it due to edge removal (since they
 690      become unreachable by back edges from latch).  */
 691   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 692     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 693
 694   BITMAP_FREE (changed_bbs);
 695
 696 #ifdef ENABLE_CHECKING
 697   verify_loop_structure ();
 698 #endif
 699   scev_reset ();
 700
 701   loops_state_clear (LOOPS_NEED_FIXUP);
 702 }
 703
 704 /* Cleanup cfg and repair loop structures.  */
 705
 706 bool
 707 cleanup_tree_cfg (void)
 708 {
 709   bool changed = cleanup_tree_cfg_noloop ();
 710
 711   if (current_loops != NULL
 712       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 713     repair_loop_structures ();
 714
 715   return changed;
 716 }
 717
 718 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 719
 720 static void
 721 remove_forwarder_block_with_phi (basic_block bb)
 722 {
 723   edge succ = single_succ_edge (bb);
 724   basic_block dest = succ->dest;
 725   gimple label;
 726   basic_block dombb, domdest, dom;
 727
 728   /* We check for infinite loops already in tree_forwarder_block_p.
 729      However it may happen that the infinite loop is created
 730      afterwards due to removal of forwarders.  */
 731   if (dest == bb)
 732     return;
 733
 734   /* If the destination block consists of a nonlocal label, do not
 735      merge it.  */
 736   label = first_stmt (dest);
 737   if (label
 738       && gimple_code (label) == GIMPLE_LABEL
 739       && DECL_NONLOCAL (gimple_label_label (label)))
 740     return;
 741
 742   /* Redirect each incoming edge to BB to DEST.  */
 743   while (EDGE_COUNT (bb->preds) > 0)
 744     {
 745       edge e = EDGE_PRED (bb, 0), s;
 746       gimple_stmt_iterator gsi;
 747
 748       s = find_edge (e->src, dest);
 749       if (s)
 750         {
 751           /* We already have an edge S from E->src to DEST.  If S and
 752              E->dest's sole successor edge have the same PHI arguments
 753              at DEST, redirect S to DEST.  */
 754           if (phi_alternatives_equal (dest, s, succ))
 755             {
 756               e = redirect_edge_and_branch (e, dest);
 757               redirect_edge_var_map_clear (e);
 758               continue;
 759             }
 760
 761           /* PHI arguments are different.  Create a forwarder block by
 762              splitting E so that we can merge PHI arguments on E to
 763              DEST.  */
 764           e = single_succ_edge (split_edge (e));
 765         }
 766
 767       s = redirect_edge_and_branch (e, dest);
 768
 769       /* redirect_edge_and_branch must not create a new edge.  */
 770       gcc_assert (s == e);
 771
 772       /* Add to the PHI nodes at DEST each PHI argument removed at the
 773          destination of E.  */
 774       for (gsi = gsi_start_phis (dest);
 775            !gsi_end_p (gsi);
 776            gsi_next (&gsi))
 777         {
 778           gimple phi = gsi_stmt (gsi);
 779           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 780           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 781
 782           if (TREE_CODE (def) == SSA_NAME)
 783             {
 784               edge_var_map_vector head;
 785               edge_var_map *vm;
 786               size_t i;
 787
 788               /* If DEF is one of the results of PHI nodes removed during
 789                  redirection, replace it with the PHI argument that used
 790                  to be on E.  */
 791               head = redirect_edge_var_map_vector (e);
 792               for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
 793                 {
 794                   tree old_arg = redirect_edge_var_map_result (vm);
 795                   tree new_arg = redirect_edge_var_map_def (vm);
 796
 797                   if (def == old_arg)
 798                     {
 799                       def = new_arg;
 800                       locus = redirect_edge_var_map_location (vm);
 801                       break;
 802                     }
 803                 }
 804             }
 805
 806           add_phi_arg (phi, def, s, locus);
 807         }
 808
 809       redirect_edge_var_map_clear (e);
 810     }
 811
 812   /* Update the dominators.  */
 813   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 814   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 815   if (domdest == bb)
 816     {
 817       /* Shortcut to avoid calling (relatively expensive)
 818          nearest_common_dominator unless necessary.  */
 819       dom = dombb;
 820     }
 821   else
 822     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 823
 824   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 825
 826   /* Remove BB since all of BB's incoming edges have been redirected
 827      to DEST.  */
 828   delete_basic_block (bb);
 829 }
 830
 831 /* This pass merges PHI nodes if one feeds into another.  For example,
 832    suppose we have the following:
 833
 834   goto <bb 9> (<L9>);
 835
 836 <L8>:;
 837   tem_17 = foo ();
 838
 839   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 840 <L9>:;
 841
 842   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 843 <L10>:;
 844
 845   Then we merge the first PHI node into the second one like so:
 846
 847   goto <bb 9> (<L10>);
 848
 849 <L8>:;
 850   tem_17 = foo ();
 851
 852   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 853 <L10>:;
 854 */
 855
 856 static unsigned int
 857 merge_phi_nodes (void)
 858 {
 859   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 860   basic_block *current = worklist;
 861   basic_block bb;
 862
 863   calculate_dominance_info (CDI_DOMINATORS);
 864
 865   /* Find all PHI nodes that we may be able to merge.  */
 866   FOR_EACH_BB (bb)
 867     {
 868       basic_block dest;
 869
 870       /* Look for a forwarder block with PHI nodes.  */
 871       if (!tree_forwarder_block_p (bb, true))
 872         continue;
 873
 874       dest = single_succ (bb);
 875
 876       /* We have to feed into another basic block with PHI
 877          nodes.  */
 878       if (gimple_seq_empty_p (phi_nodes (dest))
 879           /* We don't want to deal with a basic block with
 880              abnormal edges.  */
 881           || has_abnormal_incoming_edge_p (bb))
 882         continue;
 883
 884       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 885         {
 886           /* If BB does not dominate DEST, then the PHI nodes at
 887              DEST must be the only users of the results of the PHI
 888              nodes at BB.  */
 889           *current++ = bb;
 890         }
 891       else
 892         {
 893           gimple_stmt_iterator gsi;
 894           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 895
 896           /* BB dominates DEST.  There may be many users of the PHI
 897              nodes in BB.  However, there is still a trivial case we
 898              can handle.  If the result of every PHI in BB is used
 899              only by a PHI in DEST, then we can trivially merge the
 900              PHI nodes from BB into DEST.  */
 901           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 902                gsi_next (&gsi))
 903             {
 904               gimple phi = gsi_stmt (gsi);
 905               tree result = gimple_phi_result (phi);
 906               use_operand_p imm_use;
 907               gimple use_stmt;
 908
 909               /* If the PHI's result is never used, then we can just
 910                  ignore it.  */
 911               if (has_zero_uses (result))
 912                 continue;
 913
 914               /* Get the single use of the result of this PHI node.  */
 915               if (!single_imm_use (result, &imm_use, &use_stmt)
 916                   || gimple_code (use_stmt) != GIMPLE_PHI
 917                   || gimple_bb (use_stmt) != dest
 918                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
 919                 break;
 920             }
 921
 922           /* If the loop above iterated through all the PHI nodes
 923              in BB, then we can merge the PHIs from BB into DEST.  */
 924           if (gsi_end_p (gsi))
 925             *current++ = bb;
 926         }
 927     }
 928
 929   /* Now let's drain WORKLIST.  */
 930   while (current != worklist)
 931     {
 932       bb = *--current;
 933       remove_forwarder_block_with_phi (bb);
 934     }
 935
 936   free (worklist);
 937   return 0;
 938 }
 939
 940 static bool
 941 gate_merge_phi (void)
 942 {
 943   return 1;
 944 }
 945
 946 struct gimple_opt_pass pass_merge_phi =
 947 {
 948  {
 949   GIMPLE_PASS,
 950   "mergephi",                   /* name */
 951   gate_merge_phi,               /* gate */
 952   merge_phi_nodes,              /* execute */
 953   NULL,                         /* sub */
 954   NULL,                         /* next */
 955   0,                            /* static_pass_number */
 956   TV_TREE_MERGE_PHI,            /* tv_id */
 957   PROP_cfg | PROP_ssa,          /* properties_required */
 958   0,                            /* properties_provided */
 959   0,                            /* properties_destroyed */
 960   0,                            /* todo_flags_start */
 961   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 962   | TODO_verify_ssa
 963  }
 964 };