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   bool seen_abnormal_edge = false;
 342
 343   /* We check for infinite loops already in tree_forwarder_block_p.
 344      However it may happen that the infinite loop is created
 345      afterwards due to removal of forwarders.  */
 346   if (dest == bb)
 347     return false;
 348
 349   /* If the destination block consists of a nonlocal label, do not merge
 350      it.  */
 351   label = first_stmt (dest);
 352   if (label
 353       && gimple_code (label) == GIMPLE_LABEL
 354       && DECL_NONLOCAL (gimple_label_label (label)))
 355     return false;
 356
 357   /* If there is an abnormal edge to basic block BB, but not into
 358      dest, problems might occur during removal of the phi node at out
 359      of ssa due to overlapping live ranges of registers.
 360
 361      If there is an abnormal edge in DEST, the problems would occur
 362      anyway since cleanup_dead_labels would then merge the labels for
 363      two different eh regions, and rest of exception handling code
 364      does not like it.
 365
 366      So if there is an abnormal edge to BB, proceed only if there is
 367      no abnormal edge to DEST and there are no phi nodes in DEST.  */
 368   if (has_abnormal_incoming_edge_p (bb))
 369     {
 370       seen_abnormal_edge = true;
 371
 372       if (has_abnormal_incoming_edge_p (dest)
 373           || !gimple_seq_empty_p (phi_nodes (dest)))
 374         return false;
 375     }
 376
 377   /* If there are phi nodes in DEST, and some of the blocks that are
 378      predecessors of BB are also predecessors of DEST, check that the
 379      phi node arguments match.  */
 380   if (!gimple_seq_empty_p (phi_nodes (dest)))
 381     {
 382       FOR_EACH_EDGE (e, ei, bb->preds)
 383         {
 384           s = find_edge (e->src, dest);
 385           if (!s)
 386             continue;
 387
 388           if (!phi_alternatives_equal (dest, succ, s))
 389             return false;
 390         }
 391     }
 392
 393   /* Redirect the edges.  */
 394   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 395     {
 396       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
 397
 398       if (e->flags & EDGE_ABNORMAL)
 399         {
 400           /* If there is an abnormal edge, redirect it anyway, and
 401              move the labels to the new block to make it legal.  */
 402           s = redirect_edge_succ_nodup (e, dest);
 403         }
 404       else
 405         s = redirect_edge_and_branch (e, dest);
 406
 407       if (s == e)
 408         {
 409           /* Create arguments for the phi nodes, since the edge was not
 410              here before.  */
 411           for (gsi = gsi_start_phis (dest);
 412                !gsi_end_p (gsi);
 413                gsi_next (&gsi))
 414             {
 415               gimple phi = gsi_stmt (gsi);
 416               source_location l = gimple_phi_arg_location_from_edge (phi, succ);
 417               add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s, l);
 418             }
 419         }
 420     }
 421
 422   if (seen_abnormal_edge)
 423     {
 424       /* Move the labels to the new block, so that the redirection of
 425          the abnormal edges works.  */
 426       gsi_to = gsi_start_bb (dest);
 427       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 428         {
 429           label = gsi_stmt (gsi);
 430           gcc_assert (gimple_code (label) == GIMPLE_LABEL
 431                       || is_gimple_debug (label));
 432           gsi_remove (&gsi, false);
 433           gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
 434         }
 435     }
 436
 437   bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
 438
 439   /* Update the dominators.  */
 440   if (dom_info_available_p (CDI_DOMINATORS))
 441     {
 442       basic_block dom, dombb, domdest;
 443
 444       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 445       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 446       if (domdest == bb)
 447         {
 448           /* Shortcut to avoid calling (relatively expensive)
 449              nearest_common_dominator unless necessary.  */
 450           dom = dombb;
 451         }
 452       else
 453         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 454
 455       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 456     }
 457
 458   /* And kill the forwarder block.  */
 459   delete_basic_block (bb);
 460
 461   return true;
 462 }
 463
 464 /* Split basic blocks on calls in the middle of a basic block that are now
 465    known not to return, and remove the unreachable code.  */
 466
 467 static bool
 468 split_bbs_on_noreturn_calls (void)
 469 {
 470   bool changed = false;
 471   gimple stmt;
 472   basic_block bb;
 473
 474   /* Detect cases where a mid-block call is now known not to return.  */
 475   if (cfun->gimple_df)
 476     while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
 477       {
 478         stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
 479         bb = gimple_bb (stmt);
 480         /* BB might be deleted at this point, so verify first
 481            BB is present in the cfg.  */
 482         if (bb == NULL
 483             || bb->index < NUM_FIXED_BLOCKS
 484             || bb->index >= n_basic_blocks
 485             || BASIC_BLOCK (bb->index) != bb
 486             || last_stmt (bb) == stmt
 487             || !gimple_call_noreturn_p (stmt))
 488           continue;
 489
 490         changed = true;
 491         split_block (bb, stmt);
 492         remove_fallthru_edge (bb->succs);
 493       }
 494
 495   return changed;
 496 }
 497
 498 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it.  */
 499
 500 static bool
 501 cleanup_omp_return (basic_block bb)
 502 {
 503   gimple stmt = last_stmt (bb);
 504   basic_block control_bb;
 505
 506   if (stmt == NULL
 507       || gimple_code (stmt) != GIMPLE_OMP_RETURN
 508       || !single_pred_p (bb))
 509     return false;
 510
 511   control_bb = single_pred (bb);
 512   stmt = last_stmt (control_bb);
 513
 514   if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
 515     return false;
 516
 517   /* The block with the control statement normally has two entry edges -- one
 518      from entry, one from continue.  If continue is removed, return is
 519      unreachable, so we remove it here as well.  */
 520   if (EDGE_COUNT (control_bb->preds) == 2)
 521     return false;
 522
 523   gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
 524   remove_edge_and_dominated_blocks (single_pred_edge (bb));
 525   return true;
 526 }
 527
 528 /* Tries to cleanup cfg in basic block BB.  Returns true if anything
 529    changes.  */
 530
 531 static bool
 532 cleanup_tree_cfg_bb (basic_block bb)
 533 {
 534   bool retval = false;
 535
 536   if (cleanup_omp_return (bb))
 537     return true;
 538
 539   retval = cleanup_control_flow_bb (bb);
 540
 541   /* Forwarder blocks can carry line number information which is
 542      useful when debugging, so we only clean them up when
 543      optimizing.  */
 544   if (optimize > 0
 545       && tree_forwarder_block_p (bb, false)
 546       && remove_forwarder_block (bb))
 547     return true;
 548
 549   /* Merging the blocks may create new opportunities for folding
 550      conditional branches (due to the elimination of single-valued PHI
 551      nodes).  */
 552   if (single_succ_p (bb)
 553       && can_merge_blocks_p (bb, single_succ (bb)))
 554     {
 555       merge_blocks (bb, single_succ (bb));
 556       return true;
 557     }
 558
 559   return retval;
 560 }
 561
 562 /* Iterate the cfg cleanups, while anything changes.  */
 563
 564 static bool
 565 cleanup_tree_cfg_1 (void)
 566 {
 567   bool retval = false;
 568   basic_block bb;
 569   unsigned i, n;
 570
 571   retval |= split_bbs_on_noreturn_calls ();
 572
 573   /* Prepare the worklists of altered blocks.  */
 574   cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
 575
 576   /* During forwarder block cleanup, we may redirect edges out of
 577      SWITCH_EXPRs, which can get expensive.  So we want to enable
 578      recording of edge to CASE_LABEL_EXPR.  */
 579   start_recording_case_labels ();
 580
 581   /* Start by iterating over all basic blocks.  We cannot use FOR_EACH_BB,
 582      since the basic blocks may get removed.  */
 583   n = last_basic_block;
 584   for (i = NUM_FIXED_BLOCKS; i < n; i++)
 585     {
 586       bb = BASIC_BLOCK (i);
 587       if (bb)
 588         retval |= cleanup_tree_cfg_bb (bb);
 589     }
 590
 591   /* Now process the altered blocks, as long as any are available.  */
 592   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
 593     {
 594       i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
 595       bitmap_clear_bit (cfgcleanup_altered_bbs, i);
 596       if (i < NUM_FIXED_BLOCKS)
 597         continue;
 598
 599       bb = BASIC_BLOCK (i);
 600       if (!bb)
 601         continue;
 602
 603       retval |= cleanup_tree_cfg_bb (bb);
 604
 605       /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
 606          calls.  */
 607       retval |= split_bbs_on_noreturn_calls ();
 608     }
 609
 610   end_recording_case_labels ();
 611   BITMAP_FREE (cfgcleanup_altered_bbs);
 612   return retval;
 613 }
 614
 615
 616 /* Remove unreachable blocks and other miscellaneous clean up work.
 617    Return true if the flowgraph was modified, false otherwise.  */
 618
 619 static bool
 620 cleanup_tree_cfg_noloop (void)
 621 {
 622   bool changed;
 623
 624   timevar_push (TV_TREE_CLEANUP_CFG);
 625
 626   /* Iterate until there are no more cleanups left to do.  If any
 627      iteration changed the flowgraph, set CHANGED to true.
 628
 629      If dominance information is available, there cannot be any unreachable
 630      blocks.  */
 631   if (!dom_info_available_p (CDI_DOMINATORS))
 632     {
 633       changed = delete_unreachable_blocks ();
 634       calculate_dominance_info (CDI_DOMINATORS);
 635     }
 636   else
 637     {
 638 #ifdef ENABLE_CHECKING
 639       verify_dominators (CDI_DOMINATORS);
 640 #endif
 641       changed = false;
 642     }
 643
 644   changed |= cleanup_tree_cfg_1 ();
 645
 646   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
 647   compact_blocks ();
 648
 649 #ifdef ENABLE_CHECKING
 650   verify_flow_info ();
 651 #endif
 652
 653   timevar_pop (TV_TREE_CLEANUP_CFG);
 654
 655   if (changed && current_loops)
 656     loops_state_set (LOOPS_NEED_FIXUP);
 657
 658   return changed;
 659 }
 660
 661 /* Repairs loop structures.  */
 662
 663 static void
 664 repair_loop_structures (void)
 665 {
 666   bitmap changed_bbs = BITMAP_ALLOC (NULL);
 667   fix_loop_structure (changed_bbs);
 668
 669   /* This usually does nothing.  But sometimes parts of cfg that originally
 670      were inside a loop get out of it due to edge removal (since they
 671      become unreachable by back edges from latch).  */
 672   if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
 673     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 674
 675   BITMAP_FREE (changed_bbs);
 676
 677 #ifdef ENABLE_CHECKING
 678   verify_loop_structure ();
 679 #endif
 680   scev_reset ();
 681
 682   loops_state_clear (LOOPS_NEED_FIXUP);
 683 }
 684
 685 /* Cleanup cfg and repair loop structures.  */
 686
 687 bool
 688 cleanup_tree_cfg (void)
 689 {
 690   bool changed = cleanup_tree_cfg_noloop ();
 691
 692   if (current_loops != NULL
 693       && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 694     repair_loop_structures ();
 695
 696   return changed;
 697 }
 698
 699 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 700
 701 static void
 702 remove_forwarder_block_with_phi (basic_block bb)
 703 {
 704   edge succ = single_succ_edge (bb);
 705   basic_block dest = succ->dest;
 706   gimple label;
 707   basic_block dombb, domdest, dom;
 708
 709   /* We check for infinite loops already in tree_forwarder_block_p.
 710      However it may happen that the infinite loop is created
 711      afterwards due to removal of forwarders.  */
 712   if (dest == bb)
 713     return;
 714
 715   /* If the destination block consists of a nonlocal label, do not
 716      merge it.  */
 717   label = first_stmt (dest);
 718   if (label
 719       && gimple_code (label) == GIMPLE_LABEL
 720       && DECL_NONLOCAL (gimple_label_label (label)))
 721     return;
 722
 723   /* Redirect each incoming edge to BB to DEST.  */
 724   while (EDGE_COUNT (bb->preds) > 0)
 725     {
 726       edge e = EDGE_PRED (bb, 0), s;
 727       gimple_stmt_iterator gsi;
 728
 729       s = find_edge (e->src, dest);
 730       if (s)
 731         {
 732           /* We already have an edge S from E->src to DEST.  If S and
 733              E->dest's sole successor edge have the same PHI arguments
 734              at DEST, redirect S to DEST.  */
 735           if (phi_alternatives_equal (dest, s, succ))
 736             {
 737               e = redirect_edge_and_branch (e, dest);
 738               redirect_edge_var_map_clear (e);
 739               continue;
 740             }
 741
 742           /* PHI arguments are different.  Create a forwarder block by
 743              splitting E so that we can merge PHI arguments on E to
 744              DEST.  */
 745           e = single_succ_edge (split_edge (e));
 746         }
 747
 748       s = redirect_edge_and_branch (e, dest);
 749
 750       /* redirect_edge_and_branch must not create a new edge.  */
 751       gcc_assert (s == e);
 752
 753       /* Add to the PHI nodes at DEST each PHI argument removed at the
 754          destination of E.  */
 755       for (gsi = gsi_start_phis (dest);
 756            !gsi_end_p (gsi);
 757            gsi_next (&gsi))
 758         {
 759           gimple phi = gsi_stmt (gsi);
 760           tree def = gimple_phi_arg_def (phi, succ->dest_idx);
 761           source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
 762
 763           if (TREE_CODE (def) == SSA_NAME)
 764             {
 765               edge_var_map_vector head;
 766               edge_var_map *vm;
 767               size_t i;
 768
 769               /* If DEF is one of the results of PHI nodes removed during
 770                  redirection, replace it with the PHI argument that used
 771                  to be on E.  */
 772               head = redirect_edge_var_map_vector (e);
 773               for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
 774                 {
 775                   tree old_arg = redirect_edge_var_map_result (vm);
 776                   tree new_arg = redirect_edge_var_map_def (vm);
 777
 778                   if (def == old_arg)
 779                     {
 780                       def = new_arg;
 781                       locus = redirect_edge_var_map_location (vm);
 782                       break;
 783                     }
 784                 }
 785             }
 786
 787           add_phi_arg (phi, def, s, locus);
 788         }
 789
 790       redirect_edge_var_map_clear (e);
 791     }
 792
 793   /* Update the dominators.  */
 794   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 795   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 796   if (domdest == bb)
 797     {
 798       /* Shortcut to avoid calling (relatively expensive)
 799          nearest_common_dominator unless necessary.  */
 800       dom = dombb;
 801     }
 802   else
 803     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 804
 805   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 806
 807   /* Remove BB since all of BB's incoming edges have been redirected
 808      to DEST.  */
 809   delete_basic_block (bb);
 810 }
 811
 812 /* This pass merges PHI nodes if one feeds into another.  For example,
 813    suppose we have the following:
 814
 815   goto <bb 9> (<L9>);
 816
 817 <L8>:;
 818   tem_17 = foo ();
 819
 820   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 821 <L9>:;
 822
 823   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 824 <L10>:;
 825
 826   Then we merge the first PHI node into the second one like so:
 827
 828   goto <bb 9> (<L10>);
 829
 830 <L8>:;
 831   tem_17 = foo ();
 832
 833   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 834 <L10>:;
 835 */
 836
 837 static unsigned int
 838 merge_phi_nodes (void)
 839 {
 840   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 841   basic_block *current = worklist;
 842   basic_block bb;
 843
 844   calculate_dominance_info (CDI_DOMINATORS);
 845
 846   /* Find all PHI nodes that we may be able to merge.  */
 847   FOR_EACH_BB (bb)
 848     {
 849       basic_block dest;
 850
 851       /* Look for a forwarder block with PHI nodes.  */
 852       if (!tree_forwarder_block_p (bb, true))
 853         continue;
 854
 855       dest = single_succ (bb);
 856
 857       /* We have to feed into another basic block with PHI
 858          nodes.  */
 859       if (!phi_nodes (dest)
 860           /* We don't want to deal with a basic block with
 861              abnormal edges.  */
 862           || has_abnormal_incoming_edge_p (bb))
 863         continue;
 864
 865       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 866         {
 867           /* If BB does not dominate DEST, then the PHI nodes at
 868              DEST must be the only users of the results of the PHI
 869              nodes at BB.  */
 870           *current++ = bb;
 871         }
 872       else
 873         {
 874           gimple_stmt_iterator gsi;
 875           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 876
 877           /* BB dominates DEST.  There may be many users of the PHI
 878              nodes in BB.  However, there is still a trivial case we
 879              can handle.  If the result of every PHI in BB is used
 880              only by a PHI in DEST, then we can trivially merge the
 881              PHI nodes from BB into DEST.  */
 882           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 883                gsi_next (&gsi))
 884             {
 885               gimple phi = gsi_stmt (gsi);
 886               tree result = gimple_phi_result (phi);
 887               use_operand_p imm_use;
 888               gimple use_stmt;
 889
 890               /* If the PHI's result is never used, then we can just
 891                  ignore it.  */
 892               if (has_zero_uses (result))
 893                 continue;
 894
 895               /* Get the single use of the result of this PHI node.  */
 896               if (!single_imm_use (result, &imm_use, &use_stmt)
 897                   || gimple_code (use_stmt) != GIMPLE_PHI
 898                   || gimple_bb (use_stmt) != dest
 899                   || gimple_phi_arg_def (use_stmt, dest_idx) != result)
 900                 break;
 901             }
 902
 903           /* If the loop above iterated through all the PHI nodes
 904              in BB, then we can merge the PHIs from BB into DEST.  */
 905           if (gsi_end_p (gsi))
 906             *current++ = bb;
 907         }
 908     }
 909
 910   /* Now let's drain WORKLIST.  */
 911   while (current != worklist)
 912     {
 913       bb = *--current;
 914       remove_forwarder_block_with_phi (bb);
 915     }
 916
 917   free (worklist);
 918   return 0;
 919 }
 920
 921 static bool
 922 gate_merge_phi (void)
 923 {
 924   return 1;
 925 }
 926
 927 struct gimple_opt_pass pass_merge_phi =
 928 {
 929  {
 930   GIMPLE_PASS,
 931   "mergephi",                   /* name */
 932   gate_merge_phi,               /* gate */
 933   merge_phi_nodes,              /* execute */
 934   NULL,                         /* sub */
 935   NULL,                         /* next */
 936   0,                            /* static_pass_number */
 937   TV_TREE_MERGE_PHI,            /* tv_id */
 938   PROP_cfg | PROP_ssa,          /* properties_required */
 939   0,                            /* properties_provided */
 940   0,                            /* properties_destroyed */
 941   0,                            /* todo_flags_start */
 942   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 943   | TODO_verify_ssa
 944  }
 945 };