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