contrib/gcc-4.4/gcc/tree-cfgcleanup.c

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