gcc/tree-cfgcleanup.c

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