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   tree op;
 294
 295   /* Statements that are implicitly live.  Most function calls, asm and return
 296      statements are required.  Labels and BIND_EXPR nodes are kept because
 297      they are control flow, and we have no way of knowing whether they can be
 298      removed.  DCE can eliminate all the other statements in a block, and CFG
 299      can then remove the block and labels.  */
 300   switch (TREE_CODE (stmt))
 301     {
 302     case BIND_EXPR:
 303     case LABEL_EXPR:
 304     case CASE_LABEL_EXPR:
 305       mark_stmt_necessary (stmt, false);
 306       return;
 307
 308     case ASM_EXPR:
 309     case RESX_EXPR:
 310     case RETURN_EXPR:
 311       mark_stmt_necessary (stmt, true);
 312       return;
 313
 314     case CALL_EXPR:
 315       /* Most, but not all function calls are required.  Function calls that
 316          produce no result and have no side effects (i.e. const pure
 317          functions) are unnecessary.  */
 318       if (TREE_SIDE_EFFECTS (stmt))
 319         mark_stmt_necessary (stmt, true);
 320       return;
 321
 322     case MODIFY_EXPR:
 323       op = get_call_expr_in (stmt);
 324       if (op && TREE_SIDE_EFFECTS (op))
 325         {
 326           mark_stmt_necessary (stmt, true);
 327           return;
 328         }
 329
 330       /* These values are mildly magic bits of the EH runtime.  We can't
 331          see the entire lifetime of these values until landing pads are
 332          generated.  */
 333       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR
 334           || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR)
 335         {
 336           mark_stmt_necessary (stmt, true);
 337           return;
 338         }
 339       break;
 340
 341     case GOTO_EXPR:
 342       if (! simple_goto_p (stmt))
 343         mark_stmt_necessary (stmt, true);
 344       return;
 345
 346     case COND_EXPR:
 347       if (GOTO_DESTINATION (COND_EXPR_THEN (stmt))
 348           == GOTO_DESTINATION (COND_EXPR_ELSE (stmt)))
 349         {
 350           /* A COND_EXPR is obviously dead if the target labels are the same.
 351              We cannot kill the statement at this point, so to prevent the
 352              statement from being marked necessary, we replace the condition
 353              with a constant.  The stmt is killed later on in cfg_cleanup.  */
 354           COND_EXPR_COND (stmt) = integer_zero_node;
 355           modify_stmt (stmt);
 356           return;
 357         }
 358       /* Fall through.  */
 359
 360     case SWITCH_EXPR:
 361       if (! aggressive)
 362         mark_stmt_necessary (stmt, true);
 363       break;
 364
 365     default:
 366       break;
 367     }
 368
 369   ann = stmt_ann (stmt);
 370   /* If the statement has volatile operands, it needs to be preserved.  Same
 371      for statements that can alter control flow in unpredictable ways.  */
 372   if (ann->has_volatile_ops
 373       || is_ctrl_altering_stmt (stmt))
 374     {
 375       mark_stmt_necessary (stmt, true);
 376       return;
 377     }
 378
 379   get_stmt_operands (stmt);
 380
 381   defs = DEF_OPS (ann);
 382   for (i = 0; i < NUM_DEFS (defs); i++)
 383     {
 384       tree def = DEF_OP (defs, i);
 385       if (need_to_preserve_store (def))
 386         {
 387           mark_stmt_necessary (stmt, true);
 388           return;
 389         }
 390     }
 391
 392   v_may_defs = V_MAY_DEF_OPS (ann);
 393   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 394     {
 395       tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
 396       if (need_to_preserve_store (v_may_def))
 397         {
 398           mark_stmt_necessary (stmt, true);
 399           return;
 400         }
 401     }
 402
 403   v_must_defs = V_MUST_DEF_OPS (ann);
 404   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 405     {
 406       tree v_must_def = V_MUST_DEF_OP (v_must_defs, i);
 407       if (need_to_preserve_store (v_must_def))
 408         {
 409           mark_stmt_necessary (stmt, true);
 410           return;
 411         }
 412     }
 413
 414   return;
 415 }
 416 \f
 417 /* Find obviously necessary statements.  These are things like most function
 418    calls, and stores to file level variables.
 419
 420    If EL is NULL, control statements are conservatively marked as
 421    necessary.  Otherwise it contains the list of edges used by control
 422    dependence analysis.  */
 423
 424 static void
 425 find_obviously_necessary_stmts (struct edge_list *el)
 426 {
 427   basic_block bb;
 428   block_stmt_iterator i;
 429   edge e;
 430
 431   FOR_EACH_BB (bb)
 432     {
 433       tree phi;
 434
 435       /* Check any PHI nodes in the block.  */
 436       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 437         {
 438           NECESSARY (phi) = 0;
 439
 440           /* PHIs for virtual variables do not directly affect code
 441              generation and need not be considered inherently necessary
 442              regardless of the bits set in their decl.
 443
 444              Thus, we only need to mark PHIs for real variables which
 445              need their result preserved as being inherently necessary.  */
 446           if (is_gimple_reg (PHI_RESULT (phi))
 447               && need_to_preserve_store (PHI_RESULT (phi)))
 448             mark_stmt_necessary (phi, true);
 449         }
 450
 451       /* Check all statements in the block.  */
 452       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 453         {
 454           tree stmt = bsi_stmt (i);
 455           NECESSARY (stmt) = 0;
 456           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 457         }
 458
 459       /* Mark this basic block as `not visited'.  A block will be marked
 460          visited when the edges that it is control dependent on have been
 461          marked.  */
 462       bb->flags &= ~BB_VISITED;
 463     }
 464
 465   if (el)
 466     {
 467       /* Prevent the loops from being removed.  We must keep the infinite loops,
 468          and we currently do not have a means to recognize the finite ones.  */
 469       FOR_EACH_BB (bb)
 470         {
 471           for (e = bb->succ; e; e = e->succ_next)
 472             if (e->flags & EDGE_DFS_BACK)
 473               mark_control_dependent_edges_necessary (e->dest, el);
 474         }
 475     }
 476 }
 477 \f
 478 /* Make corresponding control dependent edges necessary.  We only
 479    have to do this once for each basic block, so we clear the bitmap
 480    after we're done.  */
 481 static void
 482 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 483 {
 484   int edge_number;
 485
 486 #ifdef ENABLE_CHECKING
 487   if (bb == EXIT_BLOCK_PTR)
 488     abort ();
 489 #endif
 490
 491   if (bb == ENTRY_BLOCK_PTR)
 492     return;
 493
 494   EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
 495     {
 496       tree t;
 497       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 498
 499       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 500         continue;
 501       SET_BIT (last_stmt_necessary, cd_bb->index);
 502
 503       t = last_stmt (cd_bb);
 504       if (t && is_ctrl_stmt (t))
 505         mark_stmt_necessary (t, true);
 506     });
 507 }
 508 \f
 509 /* Propagate necessity using the operands of necessary statements.  Process
 510    the uses on each statement in the worklist, and add all feeding statements
 511    which contribute to the calculation of this value to the worklist.
 512
 513    In conservative mode, EL is NULL.  */
 514
 515 static void
 516 propagate_necessity (struct edge_list *el)
 517 {
 518   tree i;
 519   bool aggressive = (el ? true : false);
 520
 521   if (dump_file && (dump_flags & TDF_DETAILS))
 522     fprintf (dump_file, "\nProcessing worklist:\n");
 523
 524   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
 525     {
 526       /* Take `i' from worklist.  */
 527       i = VARRAY_TOP_TREE (worklist);
 528       VARRAY_POP (worklist);
 529
 530       if (dump_file && (dump_flags & TDF_DETAILS))
 531         {
 532           fprintf (dump_file, "processing: ");
 533           print_generic_stmt (dump_file, i, TDF_SLIM);
 534           fprintf (dump_file, "\n");
 535         }
 536
 537       if (aggressive)
 538         {
 539           /* Mark the last statements of the basic blocks that the block
 540              containing `i' is control dependent on, but only if we haven't
 541              already done so.  */
 542           basic_block bb = bb_for_stmt (i);
 543           if (! (bb->flags & BB_VISITED))
 544             {
 545               bb->flags |= BB_VISITED;
 546               mark_control_dependent_edges_necessary (bb, el);
 547             }
 548         }
 549
 550       if (TREE_CODE (i) == PHI_NODE)
 551         {
 552           /* PHI nodes are somewhat special in that each PHI alternative has
 553              data and control dependencies.  All the statements feeding the
 554              PHI node's arguments are always necessary.  In aggressive mode,
 555              we also consider the control dependent edges leading to the
 556              predecessor block associated with each PHI alternative as
 557              necessary.  */
 558           int k;
 559           for (k = 0; k < PHI_NUM_ARGS (i); k++)
 560             {
 561               tree arg = PHI_ARG_DEF (i, k);
 562               if (TREE_CODE (arg) == SSA_NAME)
 563                 mark_operand_necessary (arg);
 564             }
 565
 566           if (aggressive)
 567             {
 568               for (k = 0; k < PHI_NUM_ARGS (i); k++)
 569                 {
 570                   basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
 571                   if (! (arg_bb->flags & BB_VISITED))
 572                     {
 573                       arg_bb->flags |= BB_VISITED;
 574                       mark_control_dependent_edges_necessary (arg_bb, el);
 575                     }
 576                 }
 577             }
 578         }
 579       else
 580         {
 581           /* Propagate through the operands.  Examine all the USE, VUSE and
 582              V_MAY_DEF operands in this statement.  Mark all the statements
 583              which feed this statement's uses as necessary.  */
 584           vuse_optype vuses;
 585           v_may_def_optype v_may_defs;
 586           use_optype uses;
 587           stmt_ann_t ann;
 588           size_t k;
 589
 590           get_stmt_operands (i);
 591           ann = stmt_ann (i);
 592
 593           uses = USE_OPS (ann);
 594           for (k = 0; k < NUM_USES (uses); k++)
 595             mark_operand_necessary (USE_OP (uses, k));
 596
 597           vuses = VUSE_OPS (ann);
 598           for (k = 0; k < NUM_VUSES (vuses); k++)
 599             mark_operand_necessary (VUSE_OP (vuses, k));
 600
 601           /* The operands of V_MAY_DEF expressions are also needed as they
 602              represent potential definitions that may reach this
 603              statement (V_MAY_DEF operands allow us to follow def-def
 604              links).  */
 605           v_may_defs = V_MAY_DEF_OPS (ann);
 606           for (k = 0; k < NUM_V_MAY_DEFS (v_may_defs); k++)
 607             mark_operand_necessary (V_MAY_DEF_OP (v_may_defs, k));
 608         }
 609     }
 610 }
 611 \f
 612 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 613    contributes nothing to the program, and can be deleted.  */
 614
 615 static void
 616 eliminate_unnecessary_stmts (void)
 617 {
 618   basic_block bb;
 619   block_stmt_iterator i;
 620
 621   if (dump_file && (dump_flags & TDF_DETAILS))
 622     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 623
 624   clear_special_calls ();
 625   FOR_EACH_BB (bb)
 626     {
 627       /* Remove dead PHI nodes.  */
 628       remove_dead_phis (bb);
 629
 630       /* Remove dead statements.  */
 631       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 632         {
 633           tree t = bsi_stmt (i);
 634
 635           stats.total++;
 636
 637           /* If `i' is not necessary then remove it.  */
 638           if (! NECESSARY (t))
 639             remove_dead_stmt (&i, bb);
 640           else
 641             {
 642               tree call = get_call_expr_in (t);
 643               if (call)
 644                 notice_special_calls (call);
 645               bsi_next (&i);
 646             }
 647         }
 648     }
 649 }
 650 \f
 651 /* Remove dead PHI nodes from block BB.  */
 652
 653 static void
 654 remove_dead_phis (basic_block bb)
 655 {
 656   tree prev, phi;
 657
 658   prev = NULL_TREE;
 659   phi = phi_nodes (bb);
 660   while (phi)
 661     {
 662       stats.total_phis++;
 663
 664       if (! NECESSARY (phi))
 665         {
 666           tree next = PHI_CHAIN (phi);
 667
 668           if (dump_file && (dump_flags & TDF_DETAILS))
 669             {
 670               fprintf (dump_file, "Deleting : ");
 671               print_generic_stmt (dump_file, phi, TDF_SLIM);
 672               fprintf (dump_file, "\n");
 673             }
 674
 675           remove_phi_node (phi, prev, bb);
 676           stats.removed_phis++;
 677           phi = next;
 678         }
 679       else
 680         {
 681           prev = phi;
 682           phi = PHI_CHAIN (phi);
 683         }
 684     }
 685 }
 686 \f
 687 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
 688    containing I so that we don't have to look it up.  */
 689
 690 static void
 691 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 692 {
 693   tree t = bsi_stmt (*i);
 694
 695   if (dump_file && (dump_flags & TDF_DETAILS))
 696     {
 697       fprintf (dump_file, "Deleting : ");
 698       print_generic_stmt (dump_file, t, TDF_SLIM);
 699       fprintf (dump_file, "\n");
 700     }
 701
 702   stats.removed++;
 703
 704   /* If we have determined that a conditional branch statement contributes
 705      nothing to the program, then we not only remove it, but we also change
 706      the flow graph so that the current block will simply fall-thru to its
 707      immediate post-dominator.  The blocks we are circumventing will be
 708      removed by cleaup_cfg if this change in the flow graph makes them
 709      unreachable.  */
 710   if (is_ctrl_stmt (t))
 711     {
 712       basic_block post_dom_bb;
 713       edge e;
 714 #ifdef ENABLE_CHECKING
 715       /* The post dominance info has to be up-to-date.  */
 716       if (dom_computed[CDI_POST_DOMINATORS] != DOM_OK)
 717         abort ();
 718 #endif
 719       /* Get the immediate post dominator of bb.  */
 720       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 721       /* Some blocks don't have an immediate post dominator.  This can happen
 722          for example with infinite loops.  Removing an infinite loop is an
 723          inappropriate transformation anyway...  */
 724       if (! post_dom_bb)
 725         {
 726           bsi_next (i);
 727           return;
 728         }
 729
 730       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 731       redirect_edge_and_branch (bb->succ, post_dom_bb);
 732       PENDING_STMT (bb->succ) = NULL;
 733
 734       /* The edge is no longer associated with a conditional, so it does
 735          not have TRUE/FALSE flags.  */
 736       bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 737
 738       /* If the edge reaches any block other than the exit, then it is a
 739          fallthru edge; if it reaches the exit, then it is not a fallthru
 740          edge.  */
 741       if (post_dom_bb != EXIT_BLOCK_PTR)
 742         bb->succ->flags |= EDGE_FALLTHRU;
 743       else
 744         bb->succ->flags &= ~EDGE_FALLTHRU;
 745
 746       /* Remove the remaining the outgoing edges.  */
 747       for (e = bb->succ->succ_next; e != NULL;)
 748         {
 749           edge tmp = e;
 750           e = e->succ_next;
 751           remove_edge (tmp);
 752         }
 753     }
 754
 755   bsi_remove (i);
 756   release_defs (t);
 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 | PROP_alias,     /* 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 | PROP_alias,     /* 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