gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Ben Elliston <bje@redhat.com>
   4    and Andrew MacLeod <amacleod@redhat.com>
   5    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by the
  11 Free Software Foundation; either version 2, or (at your option) any
  12 later version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT
  15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  22 02110-1301, USA.  */
  23
  24 /* Dead code elimination.
  25
  26    References:
  27
  28      Building an Optimizing Compiler,
  29      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
  30
  31      Advanced Compiler Design and Implementation,
  32      Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
  33
  34    Dead-code elimination is the removal of statements which have no
  35    impact on the program's output.  "Dead statements" have no impact
  36    on the program's output, while "necessary statements" may have
  37    impact on the output.
  38
  39    The algorithm consists of three phases:
  40    1. Marking as necessary all statements known to be necessary,
  41       e.g. most function calls, writing a value to memory, etc;
  42    2. Propagating necessary statements, e.g., the statements
  43       giving values to operands in necessary statements; and
  44    3. Removing dead statements.  */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "ggc.h"
  51
  52 /* These RTL headers are needed for basic-block.h.  */
  53 #include "rtl.h"
  54 #include "tm_p.h"
  55 #include "hard-reg-set.h"
  56 #include "obstack.h"
  57 #include "basic-block.h"
  58
  59 #include "tree.h"
  60 #include "diagnostic.h"
  61 #include "tree-flow.h"
  62 #include "tree-gimple.h"
  63 #include "tree-dump.h"
  64 #include "tree-pass.h"
  65 #include "timevar.h"
  66 #include "flags.h"
  67 \f
  68 static struct stmt_stats
  69 {
  70   int total;
  71   int total_phis;
  72   int removed;
  73   int removed_phis;
  74 } stats;
  75
  76 static VEC(tree,heap) *worklist;
  77
  78 /* Vector indicating an SSA name has already been processed and marked
  79    as necessary.  */
  80 static sbitmap processed;
  81
  82 /* Vector indicating that last_stmt if a basic block has already been
  83    marked as necessary.  */
  84 static sbitmap last_stmt_necessary;
  85
  86 /* Before we can determine whether a control branch is dead, we need to
  87    compute which blocks are control dependent on which edges.
  88
  89    We expect each block to be control dependent on very few edges so we
  90    use a bitmap for each block recording its edges.  An array holds the
  91    bitmap.  The Ith bit in the bitmap is set if that block is dependent
  92    on the Ith edge.  */
  93 static bitmap *control_dependence_map;
  94
  95 /* Vector indicating that a basic block has already had all the edges
  96    processed that it is control dependent on.  */
  97 static sbitmap visited_control_parents;
  98
  99 /* TRUE if this pass alters the CFG (by removing control statements).
 100    FALSE otherwise.
 101
 102    If this pass alters the CFG, then it will arrange for the dominators
 103    to be recomputed.  */
 104 static bool cfg_altered;
 105
 106 /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
 107    for which the block with index N is control dependent.  */
 108 #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)                    \
 109   {                                                                           \
 110     bitmap_iterator bi;                                                       \
 111                                                                               \
 112     EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, bi)  \
 113       {                                                                       \
 114         CODE;                                                                 \
 115       }                                                                       \
 116   }
 117
 118 /* Local function prototypes.  */
 119 static inline void set_control_dependence_map_bit (basic_block, int);
 120 static inline void clear_control_dependence_bitmap (basic_block);
 121 static void find_all_control_dependences (struct edge_list *);
 122 static void find_control_dependence (struct edge_list *, int);
 123 static inline basic_block find_pdom (basic_block);
 124
 125 static inline void mark_stmt_necessary (tree, bool);
 126 static inline void mark_operand_necessary (tree, bool);
 127
 128 static void mark_stmt_if_obviously_necessary (tree, bool);
 129 static void find_obviously_necessary_stmts (struct edge_list *);
 130
 131 static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
 132 static void propagate_necessity (struct edge_list *);
 133
 134 static void eliminate_unnecessary_stmts (void);
 135 static void remove_dead_phis (basic_block);
 136 static void remove_dead_stmt (block_stmt_iterator *, basic_block);
 137
 138 static void print_stats (void);
 139 static void tree_dce_init (bool);
 140 static void tree_dce_done (bool);
 141 \f
 142 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
 143 static inline void
 144 set_control_dependence_map_bit (basic_block bb, int edge_index)
 145 {
 146   if (bb == ENTRY_BLOCK_PTR)
 147     return;
 148   gcc_assert (bb != EXIT_BLOCK_PTR);
 149   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
 150 }
 151
 152 /* Clear all control dependences for block BB.  */
 153 static inline
 154 void clear_control_dependence_bitmap (basic_block bb)
 155 {
 156   bitmap_clear (control_dependence_map[bb->index]);
 157 }
 158
 159 /* Record all blocks' control dependences on all edges in the edge
 160    list EL, ala Morgan, Section 3.6.  */
 161
 162 static void
 163 find_all_control_dependences (struct edge_list *el)
 164 {
 165   int i;
 166
 167   for (i = 0; i < NUM_EDGES (el); ++i)
 168     find_control_dependence (el, i);
 169 }
 170
 171 /* Determine all blocks' control dependences on the given edge with edge_list
 172    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
 173
 174 static void
 175 find_control_dependence (struct edge_list *el, int edge_index)
 176 {
 177   basic_block current_block;
 178   basic_block ending_block;
 179
 180   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
 181
 182   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 183     ending_block = ENTRY_BLOCK_PTR->next_bb;
 184   else
 185     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
 186
 187   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 188        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 189        current_block = find_pdom (current_block))
 190     {
 191       edge e = INDEX_EDGE (el, edge_index);
 192
 193       /* For abnormal edges, we don't make current_block control
 194          dependent because instructions that throw are always necessary
 195          anyway.  */
 196       if (e->flags & EDGE_ABNORMAL)
 197         continue;
 198
 199       set_control_dependence_map_bit (current_block, edge_index);
 200     }
 201 }
 202
 203 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
 204    This function is necessary because some blocks have negative numbers.  */
 205
 206 static inline basic_block
 207 find_pdom (basic_block block)
 208 {
 209   gcc_assert (block != ENTRY_BLOCK_PTR);
 210
 211   if (block == EXIT_BLOCK_PTR)
 212     return EXIT_BLOCK_PTR;
 213   else
 214     {
 215       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
 216       if (! bb)
 217         return EXIT_BLOCK_PTR;
 218       return bb;
 219     }
 220 }
 221 \f
 222 #define NECESSARY(stmt)         stmt->common.asm_written_flag
 223
 224 /* If STMT is not already marked necessary, mark it, and add it to the
 225    worklist if ADD_TO_WORKLIST is true.  */
 226 static inline void
 227 mark_stmt_necessary (tree stmt, bool add_to_worklist)
 228 {
 229   gcc_assert (stmt);
 230   gcc_assert (!DECL_P (stmt));
 231
 232   if (NECESSARY (stmt))
 233     return;
 234
 235   if (dump_file && (dump_flags & TDF_DETAILS))
 236     {
 237       fprintf (dump_file, "Marking useful stmt: ");
 238       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 239       fprintf (dump_file, "\n");
 240     }
 241
 242   NECESSARY (stmt) = 1;
 243   if (add_to_worklist)
 244     VEC_safe_push (tree, heap, worklist, stmt);
 245 }
 246
 247 /* Mark the statement defining operand OP as necessary.  PHIONLY is true
 248    if we should only mark it necessary if it is a phi node.  */
 249
 250 static inline void
 251 mark_operand_necessary (tree op, bool phionly)
 252 {
 253   tree stmt;
 254   int ver;
 255
 256   gcc_assert (op);
 257
 258   ver = SSA_NAME_VERSION (op);
 259   if (TEST_BIT (processed, ver))
 260     return;
 261   SET_BIT (processed, ver);
 262
 263   stmt = SSA_NAME_DEF_STMT (op);
 264   gcc_assert (stmt);
 265
 266   if (NECESSARY (stmt)
 267       || IS_EMPTY_STMT (stmt)
 268       || (phionly && TREE_CODE (stmt) != PHI_NODE))
 269     return;
 270
 271   NECESSARY (stmt) = 1;
 272   VEC_safe_push (tree, heap, worklist, stmt);
 273 }
 274 \f
 275
 276 /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
 277    it can make other statements necessary.
 278
 279    If AGGRESSIVE is false, control statements are conservatively marked as
 280    necessary.  */
 281
 282 static void
 283 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 284 {
 285   stmt_ann_t ann;
 286   tree op, def;
 287   ssa_op_iter iter;
 288
 289   /* With non-call exceptions, we have to assume that all statements could
 290      throw.  If a statement may throw, it is inherently necessary.  */
 291   if (flag_non_call_exceptions
 292       && tree_could_throw_p (stmt))
 293     {
 294       mark_stmt_necessary (stmt, true);
 295       return;
 296     }
 297
 298   /* Statements that are implicitly live.  Most function calls, asm and return
 299      statements are required.  Labels and BIND_EXPR nodes are kept because
 300      they are control flow, and we have no way of knowing whether they can be
 301      removed.  DCE can eliminate all the other statements in a block, and CFG
 302      can then remove the block and labels.  */
 303   switch (TREE_CODE (stmt))
 304     {
 305     case BIND_EXPR:
 306     case LABEL_EXPR:
 307     case CASE_LABEL_EXPR:
 308       mark_stmt_necessary (stmt, false);
 309       return;
 310
 311     case ASM_EXPR:
 312     case RESX_EXPR:
 313     case RETURN_EXPR:
 314       mark_stmt_necessary (stmt, true);
 315       return;
 316
 317     case CALL_EXPR:
 318       /* Most, but not all function calls are required.  Function calls that
 319          produce no result and have no side effects (i.e. const pure
 320          functions) are unnecessary.  */
 321       if (TREE_SIDE_EFFECTS (stmt))
 322         mark_stmt_necessary (stmt, true);
 323       return;
 324
 325     case MODIFY_EXPR:
 326       op = get_call_expr_in (stmt);
 327       if (op && TREE_SIDE_EFFECTS (op))
 328         {
 329           mark_stmt_necessary (stmt, true);
 330           return;
 331         }
 332
 333       /* These values are mildly magic bits of the EH runtime.  We can't
 334          see the entire lifetime of these values until landing pads are
 335          generated.  */
 336       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR
 337           || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR)
 338         {
 339           mark_stmt_necessary (stmt, true);
 340           return;
 341         }
 342       break;
 343
 344     case GOTO_EXPR:
 345       gcc_assert (!simple_goto_p (stmt));
 346       mark_stmt_necessary (stmt, true);
 347       return;
 348
 349     case COND_EXPR:
 350       gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2);
 351       /* Fall through.  */
 352
 353     case SWITCH_EXPR:
 354       if (! aggressive)
 355         mark_stmt_necessary (stmt, true);
 356       break;
 357
 358     default:
 359       break;
 360     }
 361
 362   ann = stmt_ann (stmt);
 363
 364   /* If the statement has volatile operands, it needs to be preserved.
 365      Same for statements that can alter control flow in unpredictable
 366      ways.  */
 367   if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
 368     {
 369       mark_stmt_necessary (stmt, true);
 370       return;
 371     }
 372
 373   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
 374     {
 375       if (is_global_var (SSA_NAME_VAR (def)))
 376         {
 377           mark_stmt_necessary (stmt, true);
 378           return;
 379         }
 380     }
 381   if (is_hidden_global_store (stmt))
 382     {
 383       mark_stmt_necessary (stmt, true);
 384       return;
 385     }
 386
 387   return;
 388 }
 389 \f
 390 /* Find obviously necessary statements.  These are things like most function
 391    calls, and stores to file level variables.
 392
 393    If EL is NULL, control statements are conservatively marked as
 394    necessary.  Otherwise it contains the list of edges used by control
 395    dependence analysis.  */
 396
 397 static void
 398 find_obviously_necessary_stmts (struct edge_list *el)
 399 {
 400   basic_block bb;
 401   block_stmt_iterator i;
 402   edge e;
 403
 404   FOR_EACH_BB (bb)
 405     {
 406       tree phi;
 407
 408       /* Check any PHI nodes in the block.  */
 409       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 410         {
 411           NECESSARY (phi) = 0;
 412
 413           /* PHIs for virtual variables do not directly affect code
 414              generation and need not be considered inherently necessary
 415              regardless of the bits set in their decl.
 416
 417              Thus, we only need to mark PHIs for real variables which
 418              need their result preserved as being inherently necessary.  */
 419           if (is_gimple_reg (PHI_RESULT (phi))
 420               && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
 421             mark_stmt_necessary (phi, true);
 422         }
 423
 424       /* Check all statements in the block.  */
 425       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 426         {
 427           tree stmt = bsi_stmt (i);
 428           NECESSARY (stmt) = 0;
 429           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 430         }
 431     }
 432
 433   if (el)
 434     {
 435       /* Prevent the loops from being removed.  We must keep the infinite loops,
 436          and we currently do not have a means to recognize the finite ones.  */
 437       FOR_EACH_BB (bb)
 438         {
 439           edge_iterator ei;
 440           FOR_EACH_EDGE (e, ei, bb->succs)
 441             if (e->flags & EDGE_DFS_BACK)
 442               mark_control_dependent_edges_necessary (e->dest, el);
 443         }
 444     }
 445 }
 446 \f
 447 /* Make corresponding control dependent edges necessary.  We only
 448    have to do this once for each basic block, so we clear the bitmap
 449    after we're done.  */
 450 static void
 451 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 452 {
 453   unsigned edge_number;
 454
 455   gcc_assert (bb != EXIT_BLOCK_PTR);
 456
 457   if (bb == ENTRY_BLOCK_PTR)
 458     return;
 459
 460   EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
 461     {
 462       tree t;
 463       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 464
 465       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 466         continue;
 467       SET_BIT (last_stmt_necessary, cd_bb->index);
 468
 469       t = last_stmt (cd_bb);
 470       if (t && is_ctrl_stmt (t))
 471         mark_stmt_necessary (t, true);
 472     });
 473 }
 474 \f
 475 /* Propagate necessity using the operands of necessary statements.  Process
 476    the uses on each statement in the worklist, and add all feeding statements
 477    which contribute to the calculation of this value to the worklist.
 478
 479    In conservative mode, EL is NULL.  */
 480
 481 static void
 482 propagate_necessity (struct edge_list *el)
 483 {
 484   tree i;
 485   bool aggressive = (el ? true : false);
 486
 487   if (dump_file && (dump_flags & TDF_DETAILS))
 488     fprintf (dump_file, "\nProcessing worklist:\n");
 489
 490   while (VEC_length (tree, worklist) > 0)
 491     {
 492       /* Take `i' from worklist.  */
 493       i = VEC_pop (tree, worklist);
 494
 495       if (dump_file && (dump_flags & TDF_DETAILS))
 496         {
 497           fprintf (dump_file, "processing: ");
 498           print_generic_stmt (dump_file, i, TDF_SLIM);
 499           fprintf (dump_file, "\n");
 500         }
 501
 502       if (aggressive)
 503         {
 504           /* Mark the last statements of the basic blocks that the block
 505              containing `i' is control dependent on, but only if we haven't
 506              already done so.  */
 507           basic_block bb = bb_for_stmt (i);
 508           if (bb != ENTRY_BLOCK_PTR
 509               && ! TEST_BIT (visited_control_parents, bb->index))
 510             {
 511               SET_BIT (visited_control_parents, bb->index);
 512               mark_control_dependent_edges_necessary (bb, el);
 513             }
 514         }
 515
 516       if (TREE_CODE (i) == PHI_NODE)
 517         {
 518           /* PHI nodes are somewhat special in that each PHI alternative has
 519              data and control dependencies.  All the statements feeding the
 520              PHI node's arguments are always necessary.  In aggressive mode,
 521              we also consider the control dependent edges leading to the
 522              predecessor block associated with each PHI alternative as
 523              necessary.  */
 524           int k;
 525           for (k = 0; k < PHI_NUM_ARGS (i); k++)
 526             {
 527               tree arg = PHI_ARG_DEF (i, k);
 528               if (TREE_CODE (arg) == SSA_NAME)
 529                 mark_operand_necessary (arg, false);
 530             }
 531
 532           if (aggressive)
 533             {
 534               for (k = 0; k < PHI_NUM_ARGS (i); k++)
 535                 {
 536                   basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
 537                   if (arg_bb != ENTRY_BLOCK_PTR
 538                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 539                     {
 540                       SET_BIT (visited_control_parents, arg_bb->index);
 541                       mark_control_dependent_edges_necessary (arg_bb, el);
 542                     }
 543                 }
 544             }
 545         }
 546       else
 547         {
 548           /* Propagate through the operands.  Examine all the USE, VUSE and
 549              V_MAY_DEF operands in this statement.  Mark all the statements
 550              which feed this statement's uses as necessary.  */
 551           ssa_op_iter iter;
 552           tree use;
 553
 554           /* The operands of V_MAY_DEF expressions are also needed as they
 555              represent potential definitions that may reach this
 556              statement (V_MAY_DEF operands allow us to follow def-def
 557              links).  */
 558
 559           FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
 560             mark_operand_necessary (use, false);
 561         }
 562     }
 563 }
 564
 565
 566 /* Propagate necessity around virtual phi nodes used in kill operands.
 567    The reason this isn't done during propagate_necessity is because we don't
 568    want to keep phis around that are just there for must-defs, unless we
 569    absolutely have to.  After we've rewritten the reaching definitions to be
 570    correct in the previous part of the fixup routine, we can simply propagate
 571    around the information about which of these virtual phi nodes are really
 572    used, and set the NECESSARY flag accordingly.
 573    Note that we do the minimum here to ensure that we keep alive the phis that
 574    are actually used in the corrected SSA form.  In particular, some of these
 575    phis may now have all of the same operand, and will be deleted by some
 576    other pass.  */
 577
 578 static void
 579 mark_really_necessary_kill_operand_phis (void)
 580 {
 581   basic_block bb;
 582   int i;
 583
 584   /* Seed the worklist with the new virtual phi arguments and virtual
 585      uses */
 586   FOR_EACH_BB (bb)
 587     {
 588       block_stmt_iterator bsi;
 589       tree phi;
 590
 591       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 592         {
 593           if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi))
 594             {
 595               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 596                 mark_operand_necessary (PHI_ARG_DEF (phi, i), true);
 597             }
 598         }
 599
 600       for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 601         {
 602           tree stmt = bsi_stmt (bsi);
 603
 604           if (NECESSARY (stmt))
 605             {
 606               use_operand_p use_p;
 607               ssa_op_iter iter;
 608               FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
 609                                         SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
 610                 {
 611                   tree use = USE_FROM_PTR (use_p);
 612                   mark_operand_necessary (use, true);
 613                 }
 614             }
 615         }
 616     }
 617
 618   /* Mark all virtual phis still in use as necessary, and all of their
 619      arguments that are phis as necessary.  */
 620   while (VEC_length (tree, worklist) > 0)
 621     {
 622       tree use = VEC_pop (tree, worklist);
 623
 624       for (i = 0; i < PHI_NUM_ARGS (use); i++)
 625         mark_operand_necessary (PHI_ARG_DEF (use, i), true);
 626     }
 627 }
 628
 629
 630 \f
 631
 632 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 633    contributes nothing to the program, and can be deleted.  */
 634
 635 static void
 636 eliminate_unnecessary_stmts (void)
 637 {
 638   basic_block bb;
 639   block_stmt_iterator i;
 640
 641   if (dump_file && (dump_flags & TDF_DETAILS))
 642     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 643
 644   clear_special_calls ();
 645   FOR_EACH_BB (bb)
 646     {
 647       /* Remove dead PHI nodes.  */
 648       remove_dead_phis (bb);
 649     }
 650
 651   FOR_EACH_BB (bb)
 652     {
 653       /* Remove dead statements.  */
 654       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 655         {
 656          tree t = bsi_stmt (i);
 657
 658          stats.total++;
 659
 660          /* If `i' is not necessary then remove it.  */
 661          if (! NECESSARY (t))
 662            remove_dead_stmt (&i, bb);
 663          else
 664            {
 665              tree call = get_call_expr_in (t);
 666              if (call)
 667                notice_special_calls (call);
 668              bsi_next (&i);
 669            }
 670         }
 671     }
 672  }
 673 \f
 674 /* Remove dead PHI nodes from block BB.  */
 675
 676 static void
 677 remove_dead_phis (basic_block bb)
 678 {
 679   tree prev, phi;
 680
 681   prev = NULL_TREE;
 682   phi = phi_nodes (bb);
 683   while (phi)
 684     {
 685       stats.total_phis++;
 686
 687       if (! NECESSARY (phi))
 688         {
 689           tree next = PHI_CHAIN (phi);
 690
 691           if (dump_file && (dump_flags & TDF_DETAILS))
 692             {
 693               fprintf (dump_file, "Deleting : ");
 694               print_generic_stmt (dump_file, phi, TDF_SLIM);
 695               fprintf (dump_file, "\n");
 696             }
 697
 698           remove_phi_node (phi, prev);
 699           stats.removed_phis++;
 700           phi = next;
 701         }
 702       else
 703         {
 704           prev = phi;
 705           phi = PHI_CHAIN (phi);
 706         }
 707     }
 708 }
 709 \f
 710 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
 711    containing I so that we don't have to look it up.  */
 712
 713 static void
 714 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 715 {
 716   tree t = bsi_stmt (*i);
 717   def_operand_p def_p;
 718
 719   ssa_op_iter iter;
 720
 721   if (dump_file && (dump_flags & TDF_DETAILS))
 722     {
 723       fprintf (dump_file, "Deleting : ");
 724       print_generic_stmt (dump_file, t, TDF_SLIM);
 725       fprintf (dump_file, "\n");
 726     }
 727
 728   stats.removed++;
 729
 730   /* If we have determined that a conditional branch statement contributes
 731      nothing to the program, then we not only remove it, but we also change
 732      the flow graph so that the current block will simply fall-thru to its
 733      immediate post-dominator.  The blocks we are circumventing will be
 734      removed by cleaup_tree_cfg if this change in the flow graph makes them
 735      unreachable.  */
 736   if (is_ctrl_stmt (t))
 737     {
 738       basic_block post_dom_bb;
 739
 740       /* The post dominance info has to be up-to-date.  */
 741       gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
 742       /* Get the immediate post dominator of bb.  */
 743       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 744       /* Some blocks don't have an immediate post dominator.  This can happen
 745          for example with infinite loops.  Removing an infinite loop is an
 746          inappropriate transformation anyway...  */
 747       if (! post_dom_bb)
 748         {
 749           bsi_next (i);
 750           return;
 751         }
 752
 753       /* If the post dominator block has PHI nodes, we might be unable
 754          to compute the right PHI args for them.  Since the control
 755          statement is unnecessary, all edges can be regarded as
 756          equivalent, but we have to get rid of the condition, since it
 757          might reference a variable that was determined to be
 758          unnecessary and thus removed.  */
 759       if (phi_nodes (post_dom_bb))
 760         post_dom_bb = EDGE_SUCC (bb, 0)->dest;
 761       else
 762         {
 763           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 764           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 765           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 766         }
 767       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 768       EDGE_SUCC (bb, 0)->count = bb->count;
 769
 770       /* The edge is no longer associated with a conditional, so it does
 771          not have TRUE/FALSE flags.  */
 772       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 773
 774       /* If the edge reaches any block other than the exit, then it is a
 775          fallthru edge; if it reaches the exit, then it is not a fallthru
 776          edge.  */
 777       if (post_dom_bb != EXIT_BLOCK_PTR)
 778         EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 779       else
 780         EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
 781
 782       /* Remove the remaining the outgoing edges.  */
 783       while (!single_succ_p (bb))
 784         {
 785           /* FIXME.  When we remove the edge, we modify the CFG, which
 786              in turn modifies the dominator and post-dominator tree.
 787              Is it safe to postpone recomputing the dominator and
 788              post-dominator tree until the end of this pass given that
 789              the post-dominators are used above?  */
 790           cfg_altered = true;
 791           remove_edge (EDGE_SUCC (bb, 1));
 792         }
 793     }
 794
 795   FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS)
 796     {
 797       tree def = DEF_FROM_PTR (def_p);
 798       mark_sym_for_renaming (SSA_NAME_VAR (def));
 799     }
 800   bsi_remove (i);
 801   release_defs (t);
 802 }
 803 \f
 804 /* Print out removed statement statistics.  */
 805
 806 static void
 807 print_stats (void)
 808 {
 809   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 810     {
 811       float percg;
 812
 813       percg = ((float) stats.removed / (float) stats.total) * 100;
 814       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 815                stats.removed, stats.total, (int) percg);
 816
 817       if (stats.total_phis == 0)
 818         percg = 0;
 819       else
 820         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 821
 822       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 823                stats.removed_phis, stats.total_phis, (int) percg);
 824     }
 825 }
 826 \f
 827 /* Initialization for this pass.  Set up the used data structures.  */
 828
 829 static void
 830 tree_dce_init (bool aggressive)
 831 {
 832   memset ((void *) &stats, 0, sizeof (stats));
 833
 834   if (aggressive)
 835     {
 836       int i;
 837
 838       control_dependence_map
 839         = xmalloc (last_basic_block * sizeof (bitmap));
 840       for (i = 0; i < last_basic_block; ++i)
 841         control_dependence_map[i] = BITMAP_ALLOC (NULL);
 842
 843       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 844       sbitmap_zero (last_stmt_necessary);
 845     }
 846
 847   processed = sbitmap_alloc (num_ssa_names + 1);
 848   sbitmap_zero (processed);
 849
 850   worklist = VEC_alloc (tree, heap, 64);
 851   cfg_altered = false;
 852 }
 853
 854 /* Cleanup after this pass.  */
 855
 856 static void
 857 tree_dce_done (bool aggressive)
 858 {
 859   if (aggressive)
 860     {
 861       int i;
 862
 863       for (i = 0; i < last_basic_block; ++i)
 864         BITMAP_FREE (control_dependence_map[i]);
 865       free (control_dependence_map);
 866
 867       sbitmap_free (visited_control_parents);
 868       sbitmap_free (last_stmt_necessary);
 869     }
 870
 871   sbitmap_free (processed);
 872
 873   VEC_free (tree, heap, worklist);
 874 }
 875 \f
 876 /* Main routine to eliminate dead code.
 877
 878    AGGRESSIVE controls the aggressiveness of the algorithm.
 879    In conservative mode, we ignore control dependence and simply declare
 880    all but the most trivially dead branches necessary.  This mode is fast.
 881    In aggressive mode, control dependences are taken into account, which
 882    results in more dead code elimination, but at the cost of some time.
 883
 884    FIXME: Aggressive mode before PRE doesn't work currently because
 885           the dominance info is not invalidated after DCE1.  This is
 886           not an issue right now because we only run aggressive DCE
 887           as the last tree SSA pass, but keep this in mind when you
 888           start experimenting with pass ordering.  */
 889
 890 static void
 891 perform_tree_ssa_dce (bool aggressive)
 892 {
 893   struct edge_list *el = NULL;
 894
 895   tree_dce_init (aggressive);
 896
 897   if (aggressive)
 898     {
 899       /* Compute control dependence.  */
 900       timevar_push (TV_CONTROL_DEPENDENCES);
 901       calculate_dominance_info (CDI_POST_DOMINATORS);
 902       el = create_edge_list ();
 903       find_all_control_dependences (el);
 904       timevar_pop (TV_CONTROL_DEPENDENCES);
 905
 906       visited_control_parents = sbitmap_alloc (last_basic_block);
 907       sbitmap_zero (visited_control_parents);
 908
 909       mark_dfs_back_edges ();
 910     }
 911
 912   find_obviously_necessary_stmts (el);
 913
 914   propagate_necessity (el);
 915
 916   mark_really_necessary_kill_operand_phis ();
 917   eliminate_unnecessary_stmts ();
 918
 919   if (aggressive)
 920     free_dominance_info (CDI_POST_DOMINATORS);
 921
 922   /* If we removed paths in the CFG, then we need to update
 923      dominators as well.  I haven't investigated the possibility
 924      of incrementally updating dominators.  */
 925   if (cfg_altered)
 926     free_dominance_info (CDI_DOMINATORS);
 927
 928   /* Debugging dumps.  */
 929   if (dump_file)
 930     print_stats ();
 931
 932   tree_dce_done (aggressive);
 933
 934   free_edge_list (el);
 935 }
 936
 937 /* Pass entry points.  */
 938 static void
 939 tree_ssa_dce (void)
 940 {
 941   perform_tree_ssa_dce (/*aggressive=*/false);
 942 }
 943
 944 static void
 945 tree_ssa_cd_dce (void)
 946 {
 947   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 948 }
 949
 950 static bool
 951 gate_dce (void)
 952 {
 953   return flag_tree_dce != 0;
 954 }
 955
 956 struct tree_opt_pass pass_dce =
 957 {
 958   "dce",                                /* name */
 959   gate_dce,                             /* gate */
 960   tree_ssa_dce,                         /* execute */
 961   NULL,                                 /* sub */
 962   NULL,                                 /* next */
 963   0,                                    /* static_pass_number */
 964   TV_TREE_DCE,                          /* tv_id */
 965   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 966   0,                                    /* properties_provided */
 967   0,                                    /* properties_destroyed */
 968   0,                                    /* todo_flags_start */
 969   TODO_dump_func
 970     | TODO_update_ssa_no_phi
 971     | TODO_cleanup_cfg
 972     | TODO_ggc_collect
 973     | TODO_verify_ssa,                  /* todo_flags_finish */
 974   0                                     /* letter */
 975 };
 976
 977 struct tree_opt_pass pass_cd_dce =
 978 {
 979   "cddce",                              /* name */
 980   gate_dce,                             /* gate */
 981   tree_ssa_cd_dce,                      /* execute */
 982   NULL,                                 /* sub */
 983   NULL,                                 /* next */
 984   0,                                    /* static_pass_number */
 985   TV_TREE_CD_DCE,                       /* tv_id */
 986   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 987   0,                                    /* properties_provided */
 988   0,                                    /* properties_destroyed */
 989   0,                                    /* todo_flags_start */
 990   TODO_dump_func
 991     | TODO_update_ssa_no_phi
 992     | TODO_cleanup_cfg
 993     | TODO_ggc_collect
 994     | TODO_verify_ssa
 995     | TODO_verify_flow,                 /* todo_flags_finish */
 996   0                                     /* letter */
 997 };
 998