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