gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
  22 02111-1307, 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 "errors.h"
  51 #include "ggc.h"
  52
  53 /* These RTL headers are needed for basic-block.h.  */
  54 #include "rtl.h"
  55 #include "tm_p.h"
  56 #include "hard-reg-set.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 varray_type 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 bitmap *control_dependence_map;
  94
  95 /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
  96    for which the block with index N is control dependent.  */
  97 #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)                    \
  98   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, CODE)
  99
 100 /* Local function prototypes.  */
 101 static inline void set_control_dependence_map_bit (basic_block, int);
 102 static inline void clear_control_dependence_bitmap (basic_block);
 103 static void find_all_control_dependences (struct edge_list *);
 104 static void find_control_dependence (struct edge_list *, int);
 105 static inline basic_block find_pdom (basic_block);
 106
 107 static inline void mark_stmt_necessary (tree, bool);
 108 static inline void mark_operand_necessary (tree);
 109
 110 static bool need_to_preserve_store (tree);
 111 static void mark_stmt_if_obviously_necessary (tree, bool);
 112 static void find_obviously_necessary_stmts (struct edge_list *);
 113
 114 static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
 115 static void propagate_necessity (struct edge_list *);
 116
 117 static void eliminate_unnecessary_stmts (void);
 118 static void remove_dead_phis (basic_block);
 119 static void remove_dead_stmt (block_stmt_iterator *, basic_block);
 120
 121 static void print_stats (void);
 122 static void tree_dce_init (bool);
 123 static void tree_dce_done (bool);
 124 \f
 125 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
 126 static inline void
 127 set_control_dependence_map_bit (basic_block bb, int edge_index)
 128 {
 129   if (bb == ENTRY_BLOCK_PTR)
 130     return;
 131   if (bb == EXIT_BLOCK_PTR)
 132     abort ();
 133   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
 134 }
 135
 136 /* Clear all control dependences for block BB.  */
 137 static inline
 138 void clear_control_dependence_bitmap (basic_block bb)
 139 {
 140   bitmap_clear (control_dependence_map[bb->index]);
 141 }
 142
 143 /* Record all blocks' control dependences on all edges in the edge
 144    list EL, ala Morgan, Section 3.6.  */
 145
 146 static void
 147 find_all_control_dependences (struct edge_list *el)
 148 {
 149   int i;
 150
 151   for (i = 0; i < NUM_EDGES (el); ++i)
 152     find_control_dependence (el, i);
 153 }
 154
 155 /* Determine all blocks' control dependences on the given edge with edge_list
 156    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
 157
 158 static void
 159 find_control_dependence (struct edge_list *el, int edge_index)
 160 {
 161   basic_block current_block;
 162   basic_block ending_block;
 163
 164 #ifdef ENABLE_CHECKING
 165   if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
 166     abort ();
 167 #endif
 168
 169   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 170     ending_block = ENTRY_BLOCK_PTR->next_bb;
 171   else
 172     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
 173
 174   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 175        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 176        current_block = find_pdom (current_block))
 177     {
 178       edge e = INDEX_EDGE (el, edge_index);
 179
 180       /* For abnormal edges, we don't make current_block control
 181          dependent because instructions that throw are always necessary
 182          anyway.  */
 183       if (e->flags & EDGE_ABNORMAL)
 184         continue;
 185
 186       set_control_dependence_map_bit (current_block, edge_index);
 187     }
 188 }
 189
 190 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
 191    This function is necessary because some blocks have negative numbers.  */
 192
 193 static inline basic_block
 194 find_pdom (basic_block block)
 195 {
 196   if (block == ENTRY_BLOCK_PTR)
 197     abort ();
 198   else if (block == EXIT_BLOCK_PTR)
 199     return EXIT_BLOCK_PTR;
 200   else
 201     {
 202       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
 203       if (! bb)
 204         return EXIT_BLOCK_PTR;
 205       return bb;
 206     }
 207 }
 208 \f
 209 #define NECESSARY(stmt)         stmt->common.asm_written_flag
 210
 211 /* If STMT is not already marked necessary, mark it, and add it to the
 212    worklist if ADD_TO_WORKLIST is true.  */
 213 static inline void
 214 mark_stmt_necessary (tree stmt, bool add_to_worklist)
 215 {
 216 #ifdef ENABLE_CHECKING
 217   if (stmt == NULL
 218       || stmt == error_mark_node
 219       || (stmt && DECL_P (stmt)))
 220     abort ();
 221 #endif
 222
 223   if (NECESSARY (stmt))
 224     return;
 225
 226   if (dump_file && (dump_flags & TDF_DETAILS))
 227     {
 228       fprintf (dump_file, "Marking useful stmt: ");
 229       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 230       fprintf (dump_file, "\n");
 231     }
 232
 233   NECESSARY (stmt) = 1;
 234   if (add_to_worklist)
 235     VARRAY_PUSH_TREE (worklist, stmt);
 236 }
 237
 238 /* Mark the statement defining operand OP as necessary.  */
 239
 240 static inline void
 241 mark_operand_necessary (tree op)
 242 {
 243   tree stmt;
 244   int ver;
 245
 246 #ifdef ENABLE_CHECKING
 247   if (op == NULL)
 248     abort ();
 249 #endif
 250
 251   ver = SSA_NAME_VERSION (op);
 252   if (TEST_BIT (processed, ver))
 253     return;
 254   SET_BIT (processed, ver);
 255
 256   stmt = SSA_NAME_DEF_STMT (op);
 257 #ifdef ENABLE_CHECKING
 258   if (stmt == NULL)
 259     abort ();
 260 #endif
 261
 262   if (NECESSARY (stmt)
 263       || IS_EMPTY_STMT (stmt))
 264     return;
 265
 266   NECESSARY (stmt) = 1;
 267   VARRAY_PUSH_TREE (worklist, stmt);
 268 }
 269 \f
 270 /* Return true if a store to a variable needs to be preserved.  */
 271
 272 static inline bool
 273 need_to_preserve_store (tree ssa_name)
 274 {
 275   return (needs_to_live_in_memory (SSA_NAME_VAR (ssa_name)));
 276 }
 277 \f
 278
 279 /* Mark STMT as necessary if it is obviously is.  Add it to the worklist if
 280    it can make other statements necessary.
 281
 282    If AGGRESSIVE is false, control statements are conservatively marked as
 283    necessary.  */
 284
 285 static void
 286 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 287 {
 288   def_optype defs;
 289   v_may_def_optype v_may_defs;
 290   v_must_def_optype v_must_defs;
 291   stmt_ann_t ann;
 292   size_t i;
 293
 294   /* Statements that are implicitly live.  Most function calls, asm and return
 295      statements are required.  Labels and BIND_EXPR nodes are kept because
 296      they are control flow, and we have no way of knowing whether they can be
 297      removed.  DCE can eliminate all the other statements in a block, and CFG
 298      can then remove the block and labels.  */
 299   switch (TREE_CODE (stmt))
 300     {
 301     case BIND_EXPR:
 302     case LABEL_EXPR:
 303     case CASE_LABEL_EXPR:
 304       mark_stmt_necessary (stmt, false);
 305       return;
 306
 307     case ASM_EXPR:
 308     case RESX_EXPR:
 309     case RETURN_EXPR:
 310       mark_stmt_necessary (stmt, true);
 311       return;
 312
 313     case CALL_EXPR:
 314       /* Most, but not all function calls are required.  Function calls that
 315          produce no result and have no side effects (i.e. const pure
 316          functions) are unnecessary.  */
 317       if (TREE_SIDE_EFFECTS (stmt))
 318         mark_stmt_necessary (stmt, true);
 319       return;
 320
 321     case MODIFY_EXPR:
 322       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR
 323           && TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
 324         {
 325           mark_stmt_necessary (stmt, true);
 326           return;
 327         }
 328
 329       /* These values are mildly magic bits of the EH runtime.  We can't
 330          see the entire lifetime of these values until landing pads are
 331          generated.  */
 332       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR
 333           || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR)
 334         {
 335           mark_stmt_necessary (stmt, true);
 336           return;
 337         }
 338       break;
 339
 340     case GOTO_EXPR:
 341       if (! simple_goto_p (stmt))
 342         mark_stmt_necessary (stmt, true);
 343       return;
 344
 345     case COND_EXPR:
 346       if (GOTO_DESTINATION (COND_EXPR_THEN (stmt))
 347           == GOTO_DESTINATION (COND_EXPR_ELSE (stmt)))
 348         {
 349           /* A COND_EXPR is obviously dead if the target labels are the same.
 350              We cannot kill the statement at this point, so to prevent the
 351              statement from being marked necessary, we replace the condition
 352              with a constant.  The stmt is killed later on in cfg_cleanup.  */
 353           COND_EXPR_COND (stmt) = integer_zero_node;
 354           modify_stmt (stmt);
 355           return;
 356         }
 357       /* Fall through.  */
 358
 359     case SWITCH_EXPR:
 360       if (! aggressive)
 361         mark_stmt_necessary (stmt, true);
 362       break;
 363
 364     default:
 365       break;
 366     }
 367
 368   ann = stmt_ann (stmt);
 369   /* If the statement has volatile operands, it needs to be preserved.  Same
 370      for statements that can alter control flow in unpredictable ways.  */
 371   if (ann->has_volatile_ops
 372       || is_ctrl_altering_stmt (stmt))
 373     {
 374       mark_stmt_necessary (stmt, true);
 375       return;
 376     }
 377
 378   get_stmt_operands (stmt);
 379
 380   defs = DEF_OPS (ann);
 381   for (i = 0; i < NUM_DEFS (defs); i++)
 382     {
 383       tree def = DEF_OP (defs, i);
 384       if (need_to_preserve_store (def))
 385         {
 386           mark_stmt_necessary (stmt, true);
 387           return;
 388         }
 389     }
 390
 391   v_may_defs = V_MAY_DEF_OPS (ann);
 392   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 393     {
 394       tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
 395       if (need_to_preserve_store (v_may_def))
 396         {
 397           mark_stmt_necessary (stmt, true);
 398           return;
 399         }
 400     }
 401
 402   v_must_defs = V_MUST_DEF_OPS (ann);
 403   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 404     {
 405       tree v_must_def = V_MUST_DEF_OP (v_must_defs, i);
 406       if (need_to_preserve_store (v_must_def))
 407         {
 408           mark_stmt_necessary (stmt, true);
 409           return;
 410         }
 411     }
 412
 413   return;
 414 }
 415 \f
 416 /* Find obviously necessary statements.  These are things like most function
 417    calls, and stores to file level variables.
 418
 419    If EL is NULL, control statements are conservatively marked as
 420    necessary.  Otherwise it contains the list of edges used by control
 421    dependence analysis.  */
 422
 423 static void
 424 find_obviously_necessary_stmts (struct edge_list *el)
 425 {
 426   basic_block bb;
 427   block_stmt_iterator i;
 428   edge e;
 429
 430   FOR_EACH_BB (bb)
 431     {
 432       tree phi;
 433
 434       /* Check any PHI nodes in the block.  */
 435       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 436         {
 437           NECESSARY (phi) = 0;
 438
 439           /* PHIs for virtual variables do not directly affect code
 440              generation and need not be considered inherently necessary
 441              regardless of the bits set in their decl.
 442
 443              Thus, we only need to mark PHIs for real variables which
 444              need their result preserved as being inherently necessary.  */
 445           if (is_gimple_reg (PHI_RESULT (phi))
 446               && need_to_preserve_store (PHI_RESULT (phi)))
 447             mark_stmt_necessary (phi, true);
 448         }
 449
 450       /* Check all statements in the block.  */
 451       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 452         {
 453           tree stmt = bsi_stmt (i);
 454           NECESSARY (stmt) = 0;
 455           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 456         }
 457
 458       /* Mark this basic block as `not visited'.  A block will be marked
 459          visited when the edges that it is control dependent on have been
 460          marked.  */
 461       bb->flags &= ~BB_VISITED;
 462     }
 463
 464   if (el)
 465     {
 466       /* Prevent the loops from being removed.  We must keep the infinite loops,
 467          and we currently do not have a means to recognize the finite ones.  */
 468       FOR_EACH_BB (bb)
 469         {
 470           for (e = bb->succ; e; e = e->succ_next)
 471             if (e->flags & EDGE_DFS_BACK)
 472               mark_control_dependent_edges_necessary (e->dest, el);
 473         }
 474     }
 475 }
 476 \f
 477 /* Make corresponding control dependent edges necessary.  We only
 478    have to do this once for each basic block, so we clear the bitmap
 479    after we're done.  */
 480 static void
 481 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 482 {
 483   int edge_number;
 484
 485 #ifdef ENABLE_CHECKING
 486   if (bb == EXIT_BLOCK_PTR)
 487     abort ();
 488 #endif
 489
 490   if (bb == ENTRY_BLOCK_PTR)
 491     return;
 492
 493   EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
 494     {
 495       tree t;
 496       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 497
 498       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 499         continue;
 500       SET_BIT (last_stmt_necessary, cd_bb->index);
 501
 502       t = last_stmt (cd_bb);
 503       if (is_ctrl_stmt (t))
 504         mark_stmt_necessary (t, true);
 505     });
 506 }
 507 \f
 508 /* Propagate necessity using the operands of necessary statements.  Process
 509    the uses on each statement in the worklist, and add all feeding statements
 510    which contribute to the calculation of this value to the worklist.
 511
 512    In conservative mode, EL is NULL.  */
 513
 514 static void
 515 propagate_necessity (struct edge_list *el)
 516 {
 517   tree i;
 518   bool aggressive = (el ? true : false);
 519
 520   if (dump_file && (dump_flags & TDF_DETAILS))
 521     fprintf (dump_file, "\nProcessing worklist:\n");
 522
 523   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
 524     {
 525       /* Take `i' from worklist.  */
 526       i = VARRAY_TOP_TREE (worklist);
 527       VARRAY_POP (worklist);
 528
 529       if (dump_file && (dump_flags & TDF_DETAILS))
 530         {
 531           fprintf (dump_file, "processing: ");
 532           print_generic_stmt (dump_file, i, TDF_SLIM);
 533           fprintf (dump_file, "\n");
 534         }
 535
 536       if (aggressive)
 537         {
 538           /* Mark the last statements of the basic blocks that the block
 539              containing `i' is control dependent on, but only if we haven't
 540              already done so.  */
 541           basic_block bb = bb_for_stmt (i);
 542           if (! (bb->flags & BB_VISITED))
 543             {
 544               bb->flags |= BB_VISITED;
 545               mark_control_dependent_edges_necessary (bb, el);
 546             }
 547         }
 548
 549       if (TREE_CODE (i) == PHI_NODE)
 550         {
 551           /* PHI nodes are somewhat special in that each PHI alternative has
 552              data and control dependencies.  All the statements feeding the
 553              PHI node's arguments are always necessary.  In aggressive mode,
 554              we also consider the control dependent edges leading to the
 555              predecessor block associated with each PHI alternative as
 556              necessary.  */
 557           int k;
 558           for (k = 0; k < PHI_NUM_ARGS (i); k++)
 559             {
 560               tree arg = PHI_ARG_DEF (i, k);
 561               if (TREE_CODE (arg) == SSA_NAME)
 562                 mark_operand_necessary (arg);
 563             }
 564
 565           if (aggressive)
 566             {
 567               for (k = 0; k < PHI_NUM_ARGS (i); k++)
 568                 {
 569                   basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
 570                   if (! (arg_bb->flags & BB_VISITED))
 571                     {
 572                       arg_bb->flags |= BB_VISITED;
 573                       mark_control_dependent_edges_necessary (arg_bb, el);
 574                     }
 575                 }
 576             }
 577         }
 578       else
 579         {
 580           /* Propagate through the operands.  Examine all the USE, VUSE and
 581              V_MAY_DEF operands in this statement.  Mark all the statements
 582              which feed this statement's uses as necessary.  */
 583           vuse_optype vuses;
 584           v_may_def_optype v_may_defs;
 585           use_optype uses;
 586           stmt_ann_t ann;
 587           size_t k;
 588
 589           get_stmt_operands (i);
 590           ann = stmt_ann (i);
 591
 592           uses = USE_OPS (ann);
 593           for (k = 0; k < NUM_USES (uses); k++)
 594             mark_operand_necessary (USE_OP (uses, k));
 595
 596           vuses = VUSE_OPS (ann);
 597           for (k = 0; k < NUM_VUSES (vuses); k++)
 598             mark_operand_necessary (VUSE_OP (vuses, k));
 599
 600           /* The operands of V_MAY_DEF expressions are also needed as they
 601              represent potential definitions that may reach this
 602              statement (V_MAY_DEF operands allow us to follow def-def
 603              links).  */
 604           v_may_defs = V_MAY_DEF_OPS (ann);
 605           for (k = 0; k < NUM_V_MAY_DEFS (v_may_defs); k++)
 606             mark_operand_necessary (V_MAY_DEF_OP (v_may_defs, k));
 607         }
 608     }
 609 }
 610 \f
 611 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 612    contributes nothing to the program, and can be deleted.  */
 613
 614 static void
 615 eliminate_unnecessary_stmts (void)
 616 {
 617   basic_block bb;
 618   block_stmt_iterator i;
 619
 620   if (dump_file && (dump_flags & TDF_DETAILS))
 621     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 622
 623   clear_special_calls ();
 624   FOR_EACH_BB (bb)
 625     {
 626       /* Remove dead PHI nodes.  */
 627       remove_dead_phis (bb);
 628
 629       /* Remove dead statements.  */
 630       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 631         {
 632           tree t = bsi_stmt (i);
 633
 634           stats.total++;
 635
 636           /* If `i' is not necessary then remove it.  */
 637           if (! NECESSARY (t))
 638             remove_dead_stmt (&i, bb);
 639           else
 640             {
 641               if (TREE_CODE (t) == CALL_EXPR)
 642                 notice_special_calls (t);
 643               else if (TREE_CODE (t) == MODIFY_EXPR
 644                        && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
 645                 notice_special_calls (TREE_OPERAND (t, 1));
 646               bsi_next (&i);
 647             }
 648         }
 649     }
 650 }
 651 \f
 652 /* Remove dead PHI nodes from block BB.  */
 653
 654 static void
 655 remove_dead_phis (basic_block bb)
 656 {
 657   tree prev, phi;
 658
 659   prev = NULL_TREE;
 660   phi = phi_nodes (bb);
 661   while (phi)
 662     {
 663       stats.total_phis++;
 664
 665       if (! NECESSARY (phi))
 666         {
 667           tree next = TREE_CHAIN (phi);
 668
 669           if (dump_file && (dump_flags & TDF_DETAILS))
 670             {
 671               fprintf (dump_file, "Deleting : ");
 672               print_generic_stmt (dump_file, phi, TDF_SLIM);
 673               fprintf (dump_file, "\n");
 674             }
 675
 676           remove_phi_node (phi, prev, bb);
 677           stats.removed_phis++;
 678           phi = next;
 679         }
 680       else
 681         {
 682           prev = phi;
 683           phi = TREE_CHAIN (phi);
 684         }
 685     }
 686 }
 687 \f
 688 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
 689    containing I so that we don't have to look it up.  */
 690
 691 static void
 692 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 693 {
 694   tree t = bsi_stmt (*i);
 695
 696   if (dump_file && (dump_flags & TDF_DETAILS))
 697     {
 698       fprintf (dump_file, "Deleting : ");
 699       print_generic_stmt (dump_file, t, TDF_SLIM);
 700       fprintf (dump_file, "\n");
 701     }
 702
 703   stats.removed++;
 704
 705   /* If we have determined that a conditional branch statement contributes
 706      nothing to the program, then we not only remove it, but we also change
 707      the flow graph so that the current block will simply fall-thru to its
 708      immediate post-dominator.  The blocks we are circumventing will be
 709      removed by cleaup_cfg if this change in the flow graph makes them
 710      unreachable.  */
 711   if (is_ctrl_stmt (t))
 712     {
 713       basic_block post_dom_bb;
 714       edge e;
 715 #ifdef ENABLE_CHECKING
 716       /* The post dominance info has to be up-to-date.  */
 717       if (dom_computed[CDI_POST_DOMINATORS] != DOM_OK)
 718         abort ();
 719 #endif
 720       /* Get the immediate post dominator of bb.  */
 721       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 722       /* Some blocks don't have an immediate post dominator.  This can happen
 723          for example with infinite loops.  Removing an infinite loop is an
 724          inappropriate transformation anyway...  */
 725       if (! post_dom_bb)
 726         {
 727           bsi_next (i);
 728           return;
 729         }
 730
 731       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 732       redirect_edge_and_branch (bb->succ, post_dom_bb);
 733       PENDING_STMT (bb->succ) = NULL;
 734
 735       /* The edge is no longer associated with a conditional, so it does
 736          not have TRUE/FALSE flags.  */
 737       bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 738
 739       /* If the edge reaches any block other than the exit, then it is a
 740          fallthru edge; if it reaches the exit, then it is not a fallthru
 741          edge.  */
 742       if (post_dom_bb != EXIT_BLOCK_PTR)
 743         bb->succ->flags |= EDGE_FALLTHRU;
 744       else
 745         bb->succ->flags &= ~EDGE_FALLTHRU;
 746
 747       /* Remove the remaining the outgoing edges.  */
 748       for (e = bb->succ->succ_next; e != NULL;)
 749         {
 750           edge tmp = e;
 751           e = e->succ_next;
 752           remove_edge (tmp);
 753         }
 754     }
 755
 756   bsi_remove (i);
 757 }
 758 \f
 759 /* Print out removed statement statistics.  */
 760
 761 static void
 762 print_stats (void)
 763 {
 764   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 765     {
 766       float percg;
 767
 768       percg = ((float) stats.removed / (float) stats.total) * 100;
 769       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 770                stats.removed, stats.total, (int) percg);
 771
 772       if (stats.total_phis == 0)
 773         percg = 0;
 774       else
 775         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 776
 777       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 778                stats.removed_phis, stats.total_phis, (int) percg);
 779     }
 780 }
 781 \f
 782 /* Initialization for this pass.  Set up the used data structures.  */
 783
 784 static void
 785 tree_dce_init (bool aggressive)
 786 {
 787   memset ((void *) &stats, 0, sizeof (stats));
 788
 789   if (aggressive)
 790     {
 791       int i;
 792
 793       control_dependence_map
 794         = xmalloc (last_basic_block * sizeof (bitmap));
 795       for (i = 0; i < last_basic_block; ++i)
 796         control_dependence_map[i] = BITMAP_XMALLOC ();
 797
 798       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 799       sbitmap_zero (last_stmt_necessary);
 800     }
 801
 802   processed = sbitmap_alloc (num_ssa_names + 1);
 803   sbitmap_zero (processed);
 804
 805   VARRAY_TREE_INIT (worklist, 64, "work list");
 806 }
 807
 808 /* Cleanup after this pass.  */
 809
 810 static void
 811 tree_dce_done (bool aggressive)
 812 {
 813   if (aggressive)
 814     {
 815       int i;
 816
 817       for (i = 0; i < last_basic_block; ++i)
 818         BITMAP_XFREE (control_dependence_map[i]);
 819       free (control_dependence_map);
 820
 821       sbitmap_free (last_stmt_necessary);
 822     }
 823
 824   sbitmap_free (processed);
 825 }
 826 \f
 827 /* Main routine to eliminate dead code.
 828
 829    AGGRESSIVE controls the aggressiveness of the algorithm.
 830    In conservative mode, we ignore control dependence and simply declare
 831    all but the most trivially dead branches necessary.  This mode is fast.
 832    In aggressive mode, control dependences are taken into account, which
 833    results in more dead code elimination, but at the cost of some time.
 834
 835    FIXME: Aggressive mode before PRE doesn't work currently because
 836           the dominance info is not invalidated after DCE1.  This is
 837           not an issue right now because we only run aggressive DCE
 838           as the last tree SSA pass, but keep this in mind when you
 839           start experimenting with pass ordering.  */
 840
 841 static void
 842 perform_tree_ssa_dce (bool aggressive)
 843 {
 844   struct edge_list *el = NULL;
 845
 846   tree_dce_init (aggressive);
 847
 848   if (aggressive)
 849     {
 850       /* Compute control dependence.  */
 851       timevar_push (TV_CONTROL_DEPENDENCES);
 852       calculate_dominance_info (CDI_POST_DOMINATORS);
 853       el = create_edge_list ();
 854       find_all_control_dependences (el);
 855       timevar_pop (TV_CONTROL_DEPENDENCES);
 856
 857       mark_dfs_back_edges ();
 858     }
 859
 860   find_obviously_necessary_stmts (el);
 861
 862   propagate_necessity (el);
 863
 864   eliminate_unnecessary_stmts ();
 865
 866   if (aggressive)
 867     free_dominance_info (CDI_POST_DOMINATORS);
 868
 869   cleanup_tree_cfg ();
 870
 871   /* Debugging dumps.  */
 872   if (dump_file)
 873     {
 874       dump_function_to_file (current_function_decl, dump_file, dump_flags);
 875       print_stats ();
 876     }
 877
 878   tree_dce_done (aggressive);
 879
 880   free_edge_list (el);
 881 }
 882
 883 /* Pass entry points.  */
 884 static void
 885 tree_ssa_dce (void)
 886 {
 887   perform_tree_ssa_dce (/*aggressive=*/false);
 888 }
 889
 890 static void
 891 tree_ssa_cd_dce (void)
 892 {
 893   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 894 }
 895
 896 static bool
 897 gate_dce (void)
 898 {
 899   return flag_tree_dce != 0;
 900 }
 901
 902 struct tree_opt_pass pass_dce =
 903 {
 904   "dce",                                /* name */
 905   gate_dce,                             /* gate */
 906   tree_ssa_dce,                         /* execute */
 907   NULL,                                 /* sub */
 908   NULL,                                 /* next */
 909   0,                                    /* static_pass_number */
 910   TV_TREE_DCE,                          /* tv_id */
 911   PROP_cfg | PROP_ssa,                  /* properties_required */
 912   0,                                    /* properties_provided */
 913   0,                                    /* properties_destroyed */
 914   0,                                    /* todo_flags_start */
 915   TODO_ggc_collect | TODO_verify_ssa    /* todo_flags_finish */
 916 };
 917
 918 struct tree_opt_pass pass_cd_dce =
 919 {
 920   "cddce",                              /* name */
 921   gate_dce,                             /* gate */
 922   tree_ssa_cd_dce,                      /* execute */
 923   NULL,                                 /* sub */
 924   NULL,                                 /* next */
 925   0,                                    /* static_pass_number */
 926   TV_TREE_CD_DCE,                       /* tv_id */
 927   PROP_cfg | PROP_ssa,                  /* properties_required */
 928   0,                                    /* properties_provided */
 929   0,                                    /* properties_destroyed */
 930   0,                                    /* todo_flags_start */
 931   TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow
 932                                         /* todo_flags_finish */
 933 };
 934