gcc/tree-cfgcleanup.c

   1 /* CFG cleanup for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  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 "errors.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 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
  51
  52 static bool
  53 remove_fallthru_edge (VEC(edge,gc) *ev)
  54 {
  55   edge_iterator ei;
  56   edge e;
  57
  58   FOR_EACH_EDGE (e, ei, ev)
  59     if ((e->flags & EDGE_FALLTHRU) != 0)
  60       {
  61         remove_edge (e);
  62         return true;
  63       }
  64   return false;
  65 }
  66
  67 /* Disconnect an unreachable block in the control expression starting
  68    at block BB.  */
  69
  70 static bool
  71 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
  72 {
  73   edge taken_edge;
  74   bool retval = false;
  75   tree expr = bsi_stmt (bsi), val;
  76
  77   if (!single_succ_p (bb))
  78     {
  79       edge e;
  80       edge_iterator ei;
  81
  82       switch (TREE_CODE (expr))
  83         {
  84         case COND_EXPR:
  85           val = fold (COND_EXPR_COND (expr));
  86           break;
  87
  88         case SWITCH_EXPR:
  89           val = fold (SWITCH_COND (expr));
  90           if (TREE_CODE (val) != INTEGER_CST)
  91             return false;
  92           break;
  93
  94         default:
  95           gcc_unreachable ();
  96         }
  97
  98       taken_edge = find_taken_edge (bb, val);
  99       if (!taken_edge)
 100         return false;
 101
 102       /* Remove all the edges except the one that is always executed.  */
 103       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 104         {
 105           if (e != taken_edge)
 106             {
 107               taken_edge->probability += e->probability;
 108               taken_edge->count += e->count;
 109               remove_edge (e);
 110               retval = true;
 111             }
 112           else
 113             ei_next (&ei);
 114         }
 115       if (taken_edge->probability > REG_BR_PROB_BASE)
 116         taken_edge->probability = REG_BR_PROB_BASE;
 117     }
 118   else
 119     taken_edge = single_succ_edge (bb);
 120
 121   bsi_remove (&bsi, true);
 122   taken_edge->flags = EDGE_FALLTHRU;
 123
 124   /* We removed some paths from the cfg.  */
 125   free_dominance_info (CDI_DOMINATORS);
 126
 127   return retval;
 128 }
 129
 130 /* Try to remove superfluous control structures.  */
 131
 132 static bool
 133 cleanup_control_flow (void)
 134 {
 135   basic_block bb;
 136   block_stmt_iterator bsi;
 137   bool retval = false;
 138   tree stmt;
 139
 140   /* Detect cases where a mid-block call is now known not to return.  */
 141   if (cfun->gimple_df)
 142     while (VEC_length (tree, MODIFIED_NORETURN_CALLS (cfun)))
 143       {
 144         stmt = VEC_pop (tree, MODIFIED_NORETURN_CALLS (cfun));
 145         bb = bb_for_stmt (stmt);
 146         if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt))
 147           split_block (bb, stmt);
 148       }
 149
 150   FOR_EACH_BB (bb)
 151     {
 152       bsi = bsi_last (bb);
 153
 154       /* If the last statement of the block could throw and now cannot,
 155          we need to prune cfg.  */
 156       retval |= tree_purge_dead_eh_edges (bb);
 157
 158       if (bsi_end_p (bsi))
 159         continue;
 160
 161       stmt = bsi_stmt (bsi);
 162
 163       if (TREE_CODE (stmt) == COND_EXPR
 164           || TREE_CODE (stmt) == SWITCH_EXPR)
 165         retval |= cleanup_control_expr_graph (bb, bsi);
 166       /* If we had a computed goto which has a compile-time determinable
 167          destination, then we can eliminate the goto.  */
 168       else if (TREE_CODE (stmt) == GOTO_EXPR
 169                && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR
 170                && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0))
 171                    == LABEL_DECL))
 172         {
 173           edge e;
 174           tree label;
 175           edge_iterator ei;
 176           basic_block target_block;
 177           bool removed_edge = false;
 178
 179           /* First look at all the outgoing edges.  Delete any outgoing
 180              edges which do not go to the right block.  For the one
 181              edge which goes to the right block, fix up its flags.  */
 182           label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0);
 183           target_block = label_to_block (label);
 184           for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 185             {
 186               if (e->dest != target_block)
 187                 {
 188                   removed_edge = true;
 189                   remove_edge (e);
 190                 }
 191               else
 192                 {
 193                   /* Turn off the EDGE_ABNORMAL flag.  */
 194                   e->flags &= ~EDGE_ABNORMAL;
 195
 196                   /* And set EDGE_FALLTHRU.  */
 197                   e->flags |= EDGE_FALLTHRU;
 198                   ei_next (&ei);
 199                 }
 200             }
 201
 202           /* If we removed one or more edges, then we will need to fix the
 203              dominators.  It may be possible to incrementally update them.  */
 204           if (removed_edge)
 205             free_dominance_info (CDI_DOMINATORS);
 206
 207           /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
 208              relevant information we need.  */
 209           bsi_remove (&bsi, true);
 210           retval = true;
 211         }
 212
 213       /* Check for indirect calls that have been turned into
 214          noreturn calls.  */
 215       else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
 216         {
 217           free_dominance_info (CDI_DOMINATORS);
 218           retval = true;
 219         }
 220     }
 221   return retval;
 222 }
 223
 224 /* Return true if basic block BB does nothing except pass control
 225    flow to another block and that we can safely insert a label at
 226    the start of the successor block.
 227
 228    As a precondition, we require that BB be not equal to
 229    ENTRY_BLOCK_PTR.  */
 230
 231 static bool
 232 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
 233 {
 234   block_stmt_iterator bsi;
 235   edge_iterator ei;
 236   edge e, succ;
 237   basic_block dest;
 238
 239   /* BB must have a single outgoing edge.  */
 240   if (single_succ_p (bb) != 1
 241       /* If PHI_WANTED is false, BB must not have any PHI nodes.
 242          Otherwise, BB must have PHI nodes.  */
 243       || (phi_nodes (bb) != NULL_TREE) != phi_wanted
 244       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
 245       || single_succ (bb) == EXIT_BLOCK_PTR
 246       /* Nor should this be an infinite loop.  */
 247       || single_succ (bb) == bb
 248       /* BB may not have an abnormal outgoing edge.  */
 249       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
 250     return false;
 251
 252 #if ENABLE_CHECKING
 253   gcc_assert (bb != ENTRY_BLOCK_PTR);
 254 #endif
 255
 256   /* Now walk through the statements backward.  We can ignore labels,
 257      anything else means this is not a forwarder block.  */
 258   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 259     {
 260       tree stmt = bsi_stmt (bsi);
 261
 262       switch (TREE_CODE (stmt))
 263         {
 264         case LABEL_EXPR:
 265           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
 266             return false;
 267           break;
 268
 269         default:
 270           return false;
 271         }
 272     }
 273
 274   if (find_edge (ENTRY_BLOCK_PTR, bb))
 275     return false;
 276
 277   if (current_loops)
 278     {
 279       basic_block dest;
 280       /* Protect loop latches, headers and preheaders.  */
 281       if (bb->loop_father->header == bb)
 282         return false;
 283       dest = EDGE_SUCC (bb, 0)->dest;
 284
 285       if (dest->loop_father->header == dest)
 286         return false;
 287     }
 288
 289   /* If we have an EH edge leaving this block, make sure that the
 290      destination of this block has only one predecessor.  This ensures
 291      that we don't get into the situation where we try to remove two
 292      forwarders that go to the same basic block but are handlers for
 293      different EH regions.  */
 294   succ = single_succ_edge (bb);
 295   dest = succ->dest;
 296   FOR_EACH_EDGE (e, ei, bb->preds)
 297     {
 298       if (e->flags & EDGE_EH)
 299         {
 300           if (!single_pred_p (dest))
 301             return false;
 302         }
 303     }
 304
 305   return true;
 306 }
 307
 308 /* Return true if BB has at least one abnormal incoming edge.  */
 309
 310 static inline bool
 311 has_abnormal_incoming_edge_p (basic_block bb)
 312 {
 313   edge e;
 314   edge_iterator ei;
 315
 316   FOR_EACH_EDGE (e, ei, bb->preds)
 317     if (e->flags & EDGE_ABNORMAL)
 318       return true;
 319
 320   return false;
 321 }
 322
 323 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
 324    those alternatives are equal in each of the PHI nodes, then return
 325    true, else return false.  */
 326
 327 static bool
 328 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 329 {
 330   int n1 = e1->dest_idx;
 331   int n2 = e2->dest_idx;
 332   tree phi;
 333
 334   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 335     {
 336       tree val1 = PHI_ARG_DEF (phi, n1);
 337       tree val2 = PHI_ARG_DEF (phi, n2);
 338
 339       gcc_assert (val1 != NULL_TREE);
 340       gcc_assert (val2 != NULL_TREE);
 341
 342       if (!operand_equal_for_phi_arg_p (val1, val2))
 343         return false;
 344     }
 345
 346   return true;
 347 }
 348
 349 /* Removes forwarder block BB.  Returns false if this failed.  If a new
 350    forwarder block is created due to redirection of edges, it is
 351    stored to worklist.  */
 352
 353 static bool
 354 remove_forwarder_block (basic_block bb, basic_block **worklist)
 355 {
 356   edge succ = single_succ_edge (bb), e, s;
 357   basic_block dest = succ->dest;
 358   tree label;
 359   tree phi;
 360   edge_iterator ei;
 361   block_stmt_iterator bsi, bsi_to;
 362   bool seen_abnormal_edge = false;
 363
 364   /* We check for infinite loops already in tree_forwarder_block_p.
 365      However it may happen that the infinite loop is created
 366      afterwards due to removal of forwarders.  */
 367   if (dest == bb)
 368     return false;
 369
 370   /* If the destination block consists of a nonlocal label, do not merge
 371      it.  */
 372   label = first_stmt (dest);
 373   if (label
 374       && TREE_CODE (label) == LABEL_EXPR
 375       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
 376     return false;
 377
 378   /* If there is an abnormal edge to basic block BB, but not into
 379      dest, problems might occur during removal of the phi node at out
 380      of ssa due to overlapping live ranges of registers.
 381
 382      If there is an abnormal edge in DEST, the problems would occur
 383      anyway since cleanup_dead_labels would then merge the labels for
 384      two different eh regions, and rest of exception handling code
 385      does not like it.
 386
 387      So if there is an abnormal edge to BB, proceed only if there is
 388      no abnormal edge to DEST and there are no phi nodes in DEST.  */
 389   if (has_abnormal_incoming_edge_p (bb))
 390     {
 391       seen_abnormal_edge = true;
 392
 393       if (has_abnormal_incoming_edge_p (dest)
 394           || phi_nodes (dest) != NULL_TREE)
 395         return false;
 396     }
 397
 398   /* If there are phi nodes in DEST, and some of the blocks that are
 399      predecessors of BB are also predecessors of DEST, check that the
 400      phi node arguments match.  */
 401   if (phi_nodes (dest))
 402     {
 403       FOR_EACH_EDGE (e, ei, bb->preds)
 404         {
 405           s = find_edge (e->src, dest);
 406           if (!s)
 407             continue;
 408
 409           if (!phi_alternatives_equal (dest, succ, s))
 410             return false;
 411         }
 412     }
 413
 414   /* Redirect the edges.  */
 415   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 416     {
 417       if (e->flags & EDGE_ABNORMAL)
 418         {
 419           /* If there is an abnormal edge, redirect it anyway, and
 420              move the labels to the new block to make it legal.  */
 421           s = redirect_edge_succ_nodup (e, dest);
 422         }
 423       else
 424         s = redirect_edge_and_branch (e, dest);
 425
 426       if (s == e)
 427         {
 428           /* Create arguments for the phi nodes, since the edge was not
 429              here before.  */
 430           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 431             add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
 432         }
 433       else
 434         {
 435           /* The source basic block might become a forwarder.  We know
 436              that it was not a forwarder before, since it used to have
 437              at least two outgoing edges, so we may just add it to
 438              worklist.  */
 439           if (tree_forwarder_block_p (s->src, false))
 440             *(*worklist)++ = s->src;
 441         }
 442     }
 443
 444   if (seen_abnormal_edge)
 445     {
 446       /* Move the labels to the new block, so that the redirection of
 447          the abnormal edges works.  */
 448
 449       bsi_to = bsi_start (dest);
 450       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 451         {
 452           label = bsi_stmt (bsi);
 453           gcc_assert (TREE_CODE (label) == LABEL_EXPR);
 454           bsi_remove (&bsi, false);
 455           bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
 456         }
 457     }
 458
 459   /* Update the dominators.  */
 460   if (dom_info_available_p (CDI_DOMINATORS))
 461     {
 462       basic_block dom, dombb, domdest;
 463
 464       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 465       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 466       if (domdest == bb)
 467         {
 468           /* Shortcut to avoid calling (relatively expensive)
 469              nearest_common_dominator unless necessary.  */
 470           dom = dombb;
 471         }
 472       else
 473         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 474
 475       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 476     }
 477
 478   /* And kill the forwarder block.  */
 479   delete_basic_block (bb);
 480
 481   return true;
 482 }
 483
 484 /* Removes forwarder blocks.  */
 485
 486 static bool
 487 cleanup_forwarder_blocks (void)
 488 {
 489   basic_block bb;
 490   bool changed = false;
 491   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 492   basic_block *current = worklist;
 493
 494   FOR_EACH_BB (bb)
 495     {
 496       if (tree_forwarder_block_p (bb, false))
 497         *current++ = bb;
 498     }
 499
 500   while (current != worklist)
 501     {
 502       bb = *--current;
 503       changed |= remove_forwarder_block (bb, &current);
 504     }
 505
 506   free (worklist);
 507   return changed;
 508 }
 509
 510 /* Do one round of CFG cleanup.  */
 511
 512 static bool
 513 cleanup_tree_cfg_1 (void)
 514 {
 515   bool retval;
 516
 517   retval = cleanup_control_flow ();
 518   retval |= delete_unreachable_blocks ();
 519
 520   /* Forwarder blocks can carry line number information which is
 521      useful when debugging, so we only clean them up when
 522      optimizing.  */
 523
 524   if (optimize > 0)
 525     {
 526       /* cleanup_forwarder_blocks can redirect edges out of
 527          SWITCH_EXPRs, which can get expensive.  So we want to enable
 528          recording of edge to CASE_LABEL_EXPR mappings around the call
 529          to cleanup_forwarder_blocks.  */
 530       start_recording_case_labels ();
 531       retval |= cleanup_forwarder_blocks ();
 532       end_recording_case_labels ();
 533     }
 534
 535   /* Merging the blocks may create new opportunities for folding
 536      conditional branches (due to the elimination of single-valued PHI
 537      nodes).  */
 538   retval |= merge_seq_blocks ();
 539
 540   return retval;
 541 }
 542
 543
 544 /* Remove unreachable blocks and other miscellaneous clean up work.
 545    Return true if the flowgraph was modified, false otherwise.  */
 546
 547 bool
 548 cleanup_tree_cfg (void)
 549 {
 550   bool retval, changed;
 551
 552   timevar_push (TV_TREE_CLEANUP_CFG);
 553
 554   /* Iterate until there are no more cleanups left to do.  If any
 555      iteration changed the flowgraph, set CHANGED to true.  */
 556   changed = false;
 557   do
 558     {
 559       retval = cleanup_tree_cfg_1 ();
 560       changed |= retval;
 561     }
 562   while (retval);
 563
 564   compact_blocks ();
 565
 566 #ifdef ENABLE_CHECKING
 567   verify_flow_info ();
 568 #endif
 569
 570   timevar_pop (TV_TREE_CLEANUP_CFG);
 571
 572   return changed;
 573 }
 574
 575 /* Cleanup cfg and repair loop structures.  */
 576
 577 bool
 578 cleanup_tree_cfg_loop (void)
 579 {
 580   bool changed = cleanup_tree_cfg ();
 581
 582   if (changed)
 583     {
 584       bitmap changed_bbs = BITMAP_ALLOC (NULL);
 585       calculate_dominance_info (CDI_DOMINATORS);
 586       fix_loop_structure (changed_bbs);
 587
 588       /* This usually does nothing.  But sometimes parts of cfg that originally
 589          were inside a loop get out of it due to edge removal (since they
 590          become unreachable by back edges from latch).  */
 591       rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 592
 593       BITMAP_FREE (changed_bbs);
 594
 595 #ifdef ENABLE_CHECKING
 596       verify_loop_structure ();
 597 #endif
 598       scev_reset ();
 599     }
 600   return changed;
 601 }
 602
 603 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
 604
 605 static void
 606 remove_forwarder_block_with_phi (basic_block bb)
 607 {
 608   edge succ = single_succ_edge (bb);
 609   basic_block dest = succ->dest;
 610   tree label;
 611   basic_block dombb, domdest, dom;
 612
 613   /* We check for infinite loops already in tree_forwarder_block_p.
 614      However it may happen that the infinite loop is created
 615      afterwards due to removal of forwarders.  */
 616   if (dest == bb)
 617     return;
 618
 619   /* If the destination block consists of a nonlocal label, do not
 620      merge it.  */
 621   label = first_stmt (dest);
 622   if (label
 623       && TREE_CODE (label) == LABEL_EXPR
 624       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
 625     return;
 626
 627   /* Redirect each incoming edge to BB to DEST.  */
 628   while (EDGE_COUNT (bb->preds) > 0)
 629     {
 630       edge e = EDGE_PRED (bb, 0), s;
 631       tree phi;
 632
 633       s = find_edge (e->src, dest);
 634       if (s)
 635         {
 636           /* We already have an edge S from E->src to DEST.  If S and
 637              E->dest's sole successor edge have the same PHI arguments
 638              at DEST, redirect S to DEST.  */
 639           if (phi_alternatives_equal (dest, s, succ))
 640             {
 641               e = redirect_edge_and_branch (e, dest);
 642               PENDING_STMT (e) = NULL_TREE;
 643               continue;
 644             }
 645
 646           /* PHI arguments are different.  Create a forwarder block by
 647              splitting E so that we can merge PHI arguments on E to
 648              DEST.  */
 649           e = single_succ_edge (split_edge (e));
 650         }
 651
 652       s = redirect_edge_and_branch (e, dest);
 653
 654       /* redirect_edge_and_branch must not create a new edge.  */
 655       gcc_assert (s == e);
 656
 657       /* Add to the PHI nodes at DEST each PHI argument removed at the
 658          destination of E.  */
 659       for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 660         {
 661           tree def = PHI_ARG_DEF (phi, succ->dest_idx);
 662
 663           if (TREE_CODE (def) == SSA_NAME)
 664             {
 665               tree var;
 666
 667               /* If DEF is one of the results of PHI nodes removed during
 668                  redirection, replace it with the PHI argument that used
 669                  to be on E.  */
 670               for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
 671                 {
 672                   tree old_arg = TREE_PURPOSE (var);
 673                   tree new_arg = TREE_VALUE (var);
 674
 675                   if (def == old_arg)
 676                     {
 677                       def = new_arg;
 678                       break;
 679                     }
 680                 }
 681             }
 682
 683           add_phi_arg (phi, def, s);
 684         }
 685
 686       PENDING_STMT (e) = NULL;
 687     }
 688
 689   /* Update the dominators.  */
 690   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
 691   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
 692   if (domdest == bb)
 693     {
 694       /* Shortcut to avoid calling (relatively expensive)
 695          nearest_common_dominator unless necessary.  */
 696       dom = dombb;
 697     }
 698   else
 699     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
 700
 701   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 702
 703   /* Remove BB since all of BB's incoming edges have been redirected
 704      to DEST.  */
 705   delete_basic_block (bb);
 706 }
 707
 708 /* This pass merges PHI nodes if one feeds into another.  For example,
 709    suppose we have the following:
 710
 711   goto <bb 9> (<L9>);
 712
 713 <L8>:;
 714   tem_17 = foo ();
 715
 716   # tem_6 = PHI <tem_17(8), tem_23(7)>;
 717 <L9>:;
 718
 719   # tem_3 = PHI <tem_6(9), tem_2(5)>;
 720 <L10>:;
 721
 722   Then we merge the first PHI node into the second one like so:
 723
 724   goto <bb 9> (<L10>);
 725
 726 <L8>:;
 727   tem_17 = foo ();
 728
 729   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
 730 <L10>:;
 731 */
 732
 733 static unsigned int
 734 merge_phi_nodes (void)
 735 {
 736   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
 737   basic_block *current = worklist;
 738   basic_block bb;
 739
 740   calculate_dominance_info (CDI_DOMINATORS);
 741
 742   /* Find all PHI nodes that we may be able to merge.  */
 743   FOR_EACH_BB (bb)
 744     {
 745       basic_block dest;
 746
 747       /* Look for a forwarder block with PHI nodes.  */
 748       if (!tree_forwarder_block_p (bb, true))
 749         continue;
 750
 751       dest = single_succ (bb);
 752
 753       /* We have to feed into another basic block with PHI
 754          nodes.  */
 755       if (!phi_nodes (dest)
 756           /* We don't want to deal with a basic block with
 757              abnormal edges.  */
 758           || has_abnormal_incoming_edge_p (bb))
 759         continue;
 760
 761       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
 762         {
 763           /* If BB does not dominate DEST, then the PHI nodes at
 764              DEST must be the only users of the results of the PHI
 765              nodes at BB.  */
 766           *current++ = bb;
 767         }
 768       else
 769         {
 770           tree phi;
 771           unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
 772
 773           /* BB dominates DEST.  There may be many users of the PHI
 774              nodes in BB.  However, there is still a trivial case we
 775              can handle.  If the result of every PHI in BB is used
 776              only by a PHI in DEST, then we can trivially merge the
 777              PHI nodes from BB into DEST.  */
 778           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 779             {
 780               tree result = PHI_RESULT (phi);
 781               use_operand_p imm_use;
 782               tree use_stmt;
 783
 784               /* If the PHI's result is never used, then we can just
 785                  ignore it.  */
 786               if (has_zero_uses (result))
 787                 continue;
 788
 789               /* Get the single use of the result of this PHI node.  */
 790               if (!single_imm_use (result, &imm_use, &use_stmt)
 791                   || TREE_CODE (use_stmt) != PHI_NODE
 792                   || bb_for_stmt (use_stmt) != dest
 793                   || PHI_ARG_DEF (use_stmt, dest_idx) != result)
 794                 break;
 795             }
 796
 797           /* If the loop above iterated through all the PHI nodes
 798              in BB, then we can merge the PHIs from BB into DEST.  */
 799           if (!phi)
 800             *current++ = bb;
 801         }
 802     }
 803
 804   /* Now let's drain WORKLIST.  */
 805   while (current != worklist)
 806     {
 807       bb = *--current;
 808       remove_forwarder_block_with_phi (bb);
 809     }
 810
 811   free (worklist);
 812   return 0;
 813 }
 814
 815 static bool
 816 gate_merge_phi (void)
 817 {
 818   return 1;
 819 }
 820
 821 struct tree_opt_pass pass_merge_phi = {
 822   "mergephi",                   /* name */
 823   gate_merge_phi,               /* gate */
 824   merge_phi_nodes,              /* execute */
 825   NULL,                         /* sub */
 826   NULL,                         /* next */
 827   0,                            /* static_pass_number */
 828   TV_TREE_MERGE_PHI,            /* tv_id */
 829   PROP_cfg | PROP_ssa,          /* properties_required */
 830   0,                            /* properties_provided */
 831   0,                            /* properties_destroyed */
 832   0,                            /* todo_flags_start */
 833   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 834   | TODO_verify_ssa,
 835   0                             /* letter */
 836 };