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