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 (TREE_CODE (lhs) == INDIRECT_REF
 429                || TREE_CODE (lhs) == ALIGN_INDIRECT_REF
 430                || TREE_CODE (lhs) == MISALIGNED_INDIRECT_REF)
 431         {
 432           tree ptr = TREE_OPERAND (lhs, 0);
 433           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 434           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 435           tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 436
 437           /* If either the name tag or the type tag for PTR is a
 438              global variable, then the store is necessary.  */
 439           if ((nmt && is_global_var (nmt))
 440               || (tmt && is_global_var (tmt)))
 441             {
 442               mark_stmt_necessary (stmt, true);
 443               return;
 444             }
 445         }
 446       else
 447         gcc_unreachable ();
 448     }
 449
 450   return;
 451 }
 452 \f
 453 /* Find obviously necessary statements.  These are things like most function
 454    calls, and stores to file level variables.
 455
 456    If EL is NULL, control statements are conservatively marked as
 457    necessary.  Otherwise it contains the list of edges used by control
 458    dependence analysis.  */
 459
 460 static void
 461 find_obviously_necessary_stmts (struct edge_list *el)
 462 {
 463   basic_block bb;
 464   block_stmt_iterator i;
 465   edge e;
 466
 467   FOR_EACH_BB (bb)
 468     {
 469       tree phi;
 470
 471       /* Check any PHI nodes in the block.  */
 472       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 473         {
 474           NECESSARY (phi) = 0;
 475
 476           /* PHIs for virtual variables do not directly affect code
 477              generation and need not be considered inherently necessary
 478              regardless of the bits set in their decl.
 479
 480              Thus, we only need to mark PHIs for real variables which
 481              need their result preserved as being inherently necessary.  */
 482           if (is_gimple_reg (PHI_RESULT (phi))
 483               && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
 484             mark_stmt_necessary (phi, true);
 485         }
 486
 487       /* Check all statements in the block.  */
 488       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 489         {
 490           tree stmt = bsi_stmt (i);
 491           NECESSARY (stmt) = 0;
 492           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 493         }
 494
 495       /* Mark this basic block as `not visited'.  A block will be marked
 496          visited when the edges that it is control dependent on have been
 497          marked.  */
 498       bb->flags &= ~BB_VISITED;
 499     }
 500
 501   if (el)
 502     {
 503       /* Prevent the loops from being removed.  We must keep the infinite loops,
 504          and we currently do not have a means to recognize the finite ones.  */
 505       FOR_EACH_BB (bb)
 506         {
 507           for (e = bb->succ; e; e = e->succ_next)
 508             if (e->flags & EDGE_DFS_BACK)
 509               mark_control_dependent_edges_necessary (e->dest, el);
 510         }
 511     }
 512 }
 513 \f
 514 /* Make corresponding control dependent edges necessary.  We only
 515    have to do this once for each basic block, so we clear the bitmap
 516    after we're done.  */
 517 static void
 518 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 519 {
 520   int edge_number;
 521
 522   gcc_assert (bb != EXIT_BLOCK_PTR);
 523
 524   if (bb == ENTRY_BLOCK_PTR)
 525     return;
 526
 527   EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
 528     {
 529       tree t;
 530       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 531
 532       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 533         continue;
 534       SET_BIT (last_stmt_necessary, cd_bb->index);
 535
 536       t = last_stmt (cd_bb);
 537       if (t && is_ctrl_stmt (t))
 538         mark_stmt_necessary (t, true);
 539     });
 540 }
 541 \f
 542 /* Propagate necessity using the operands of necessary statements.  Process
 543    the uses on each statement in the worklist, and add all feeding statements
 544    which contribute to the calculation of this value to the worklist.
 545
 546    In conservative mode, EL is NULL.  */
 547
 548 static void
 549 propagate_necessity (struct edge_list *el)
 550 {
 551   tree i;
 552   bool aggressive = (el ? true : false);
 553
 554   if (dump_file && (dump_flags & TDF_DETAILS))
 555     fprintf (dump_file, "\nProcessing worklist:\n");
 556
 557   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
 558     {
 559       /* Take `i' from worklist.  */
 560       i = VARRAY_TOP_TREE (worklist);
 561       VARRAY_POP (worklist);
 562
 563       if (dump_file && (dump_flags & TDF_DETAILS))
 564         {
 565           fprintf (dump_file, "processing: ");
 566           print_generic_stmt (dump_file, i, TDF_SLIM);
 567           fprintf (dump_file, "\n");
 568         }
 569
 570       if (aggressive)
 571         {
 572           /* Mark the last statements of the basic blocks that the block
 573              containing `i' is control dependent on, but only if we haven't
 574              already done so.  */
 575           basic_block bb = bb_for_stmt (i);
 576           if (! (bb->flags & BB_VISITED))
 577             {
 578               bb->flags |= BB_VISITED;
 579               mark_control_dependent_edges_necessary (bb, el);
 580             }
 581         }
 582
 583       if (TREE_CODE (i) == PHI_NODE)
 584         {
 585           /* PHI nodes are somewhat special in that each PHI alternative has
 586              data and control dependencies.  All the statements feeding the
 587              PHI node's arguments are always necessary.  In aggressive mode,
 588              we also consider the control dependent edges leading to the
 589              predecessor block associated with each PHI alternative as
 590              necessary.  */
 591           int k;
 592           for (k = 0; k < PHI_NUM_ARGS (i); k++)
 593             {
 594               tree arg = PHI_ARG_DEF (i, k);
 595               if (TREE_CODE (arg) == SSA_NAME)
 596                 mark_operand_necessary (arg);
 597             }
 598
 599           if (aggressive)
 600             {
 601               for (k = 0; k < PHI_NUM_ARGS (i); k++)
 602                 {
 603                   basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
 604                   if (! (arg_bb->flags & BB_VISITED))
 605                     {
 606                       arg_bb->flags |= BB_VISITED;
 607                       mark_control_dependent_edges_necessary (arg_bb, el);
 608                     }
 609                 }
 610             }
 611         }
 612       else
 613         {
 614           /* Propagate through the operands.  Examine all the USE, VUSE and
 615              V_MAY_DEF operands in this statement.  Mark all the statements
 616              which feed this statement's uses as necessary.  */
 617           ssa_op_iter iter;
 618           tree use;
 619
 620           get_stmt_operands (i);
 621
 622           /* The operands of V_MAY_DEF expressions are also needed as they
 623              represent potential definitions that may reach this
 624              statement (V_MAY_DEF operands allow us to follow def-def
 625              links).  */
 626
 627           FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
 628             mark_operand_necessary (use);
 629         }
 630     }
 631 }
 632 \f
 633 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 634    contributes nothing to the program, and can be deleted.  */
 635
 636 static void
 637 eliminate_unnecessary_stmts (void)
 638 {
 639   basic_block bb;
 640   block_stmt_iterator i;
 641
 642   if (dump_file && (dump_flags & TDF_DETAILS))
 643     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 644
 645   clear_special_calls ();
 646   FOR_EACH_BB (bb)
 647     {
 648       /* Remove dead PHI nodes.  */
 649       remove_dead_phis (bb);
 650
 651       /* Remove dead statements.  */
 652       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 653         {
 654           tree t = bsi_stmt (i);
 655
 656           stats.total++;
 657
 658           /* If `i' is not necessary then remove it.  */
 659           if (! NECESSARY (t))
 660             remove_dead_stmt (&i, bb);
 661           else
 662             {
 663               tree call = get_call_expr_in (t);
 664               if (call)
 665                 notice_special_calls (call);
 666               bsi_next (&i);
 667             }
 668         }
 669     }
 670 }
 671 \f
 672 /* Remove dead PHI nodes from block BB.  */
 673
 674 static void
 675 remove_dead_phis (basic_block bb)
 676 {
 677   tree prev, phi;
 678
 679   prev = NULL_TREE;
 680   phi = phi_nodes (bb);
 681   while (phi)
 682     {
 683       stats.total_phis++;
 684
 685       if (! NECESSARY (phi))
 686         {
 687           tree next = PHI_CHAIN (phi);
 688
 689           if (dump_file && (dump_flags & TDF_DETAILS))
 690             {
 691               fprintf (dump_file, "Deleting : ");
 692               print_generic_stmt (dump_file, phi, TDF_SLIM);
 693               fprintf (dump_file, "\n");
 694             }
 695
 696           remove_phi_node (phi, prev, bb);
 697           stats.removed_phis++;
 698           phi = next;
 699         }
 700       else
 701         {
 702           prev = phi;
 703           phi = PHI_CHAIN (phi);
 704         }
 705     }
 706 }
 707 \f
 708 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
 709    containing I so that we don't have to look it up.  */
 710
 711 static void
 712 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 713 {
 714   tree t = bsi_stmt (*i);
 715
 716   if (dump_file && (dump_flags & TDF_DETAILS))
 717     {
 718       fprintf (dump_file, "Deleting : ");
 719       print_generic_stmt (dump_file, t, TDF_SLIM);
 720       fprintf (dump_file, "\n");
 721     }
 722
 723   stats.removed++;
 724
 725   /* If we have determined that a conditional branch statement contributes
 726      nothing to the program, then we not only remove it, but we also change
 727      the flow graph so that the current block will simply fall-thru to its
 728      immediate post-dominator.  The blocks we are circumventing will be
 729      removed by cleaup_cfg if this change in the flow graph makes them
 730      unreachable.  */
 731   if (is_ctrl_stmt (t))
 732     {
 733       basic_block post_dom_bb;
 734       edge e;
 735       /* The post dominance info has to be up-to-date.  */
 736       gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
 737       /* Get the immediate post dominator of bb.  */
 738       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 739       /* Some blocks don't have an immediate post dominator.  This can happen
 740          for example with infinite loops.  Removing an infinite loop is an
 741          inappropriate transformation anyway...  */
 742       if (! post_dom_bb)
 743         {
 744           bsi_next (i);
 745           return;
 746         }
 747
 748       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 749       redirect_edge_and_branch (bb->succ, post_dom_bb);
 750       PENDING_STMT (bb->succ) = NULL;
 751       bb->succ->probability = REG_BR_PROB_BASE;
 752       bb->succ->count = bb->count;
 753
 754       /* The edge is no longer associated with a conditional, so it does
 755          not have TRUE/FALSE flags.  */
 756       bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 757
 758       /* If the edge reaches any block other than the exit, then it is a
 759          fallthru edge; if it reaches the exit, then it is not a fallthru
 760          edge.  */
 761       if (post_dom_bb != EXIT_BLOCK_PTR)
 762         bb->succ->flags |= EDGE_FALLTHRU;
 763       else
 764         bb->succ->flags &= ~EDGE_FALLTHRU;
 765
 766       /* Remove the remaining the outgoing edges.  */
 767       for (e = bb->succ->succ_next; e != NULL;)
 768         {
 769           edge tmp = e;
 770           e = e->succ_next;
 771           remove_edge (tmp);
 772         }
 773     }
 774
 775   bsi_remove (i);
 776   release_defs (t);
 777 }
 778 \f
 779 /* Print out removed statement statistics.  */
 780
 781 static void
 782 print_stats (void)
 783 {
 784   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 785     {
 786       float percg;
 787
 788       percg = ((float) stats.removed / (float) stats.total) * 100;
 789       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 790                stats.removed, stats.total, (int) percg);
 791
 792       if (stats.total_phis == 0)
 793         percg = 0;
 794       else
 795         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 796
 797       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 798                stats.removed_phis, stats.total_phis, (int) percg);
 799     }
 800 }
 801 \f
 802 /* Initialization for this pass.  Set up the used data structures.  */
 803
 804 static void
 805 tree_dce_init (bool aggressive)
 806 {
 807   memset ((void *) &stats, 0, sizeof (stats));
 808
 809   if (aggressive)
 810     {
 811       int i;
 812
 813       control_dependence_map
 814         = xmalloc (last_basic_block * sizeof (bitmap));
 815       for (i = 0; i < last_basic_block; ++i)
 816         control_dependence_map[i] = BITMAP_XMALLOC ();
 817
 818       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 819       sbitmap_zero (last_stmt_necessary);
 820     }
 821
 822   processed = sbitmap_alloc (num_ssa_names + 1);
 823   sbitmap_zero (processed);
 824
 825   VARRAY_TREE_INIT (worklist, 64, "work list");
 826 }
 827
 828 /* Cleanup after this pass.  */
 829
 830 static void
 831 tree_dce_done (bool aggressive)
 832 {
 833   if (aggressive)
 834     {
 835       int i;
 836
 837       for (i = 0; i < last_basic_block; ++i)
 838         BITMAP_XFREE (control_dependence_map[i]);
 839       free (control_dependence_map);
 840
 841       sbitmap_free (last_stmt_necessary);
 842     }
 843
 844   sbitmap_free (processed);
 845 }
 846 \f
 847 /* Main routine to eliminate dead code.
 848
 849    AGGRESSIVE controls the aggressiveness of the algorithm.
 850    In conservative mode, we ignore control dependence and simply declare
 851    all but the most trivially dead branches necessary.  This mode is fast.
 852    In aggressive mode, control dependences are taken into account, which
 853    results in more dead code elimination, but at the cost of some time.
 854
 855    FIXME: Aggressive mode before PRE doesn't work currently because
 856           the dominance info is not invalidated after DCE1.  This is
 857           not an issue right now because we only run aggressive DCE
 858           as the last tree SSA pass, but keep this in mind when you
 859           start experimenting with pass ordering.  */
 860
 861 static void
 862 perform_tree_ssa_dce (bool aggressive)
 863 {
 864   struct edge_list *el = NULL;
 865
 866   tree_dce_init (aggressive);
 867
 868   if (aggressive)
 869     {
 870       /* Compute control dependence.  */
 871       timevar_push (TV_CONTROL_DEPENDENCES);
 872       calculate_dominance_info (CDI_POST_DOMINATORS);
 873       el = create_edge_list ();
 874       find_all_control_dependences (el);
 875       timevar_pop (TV_CONTROL_DEPENDENCES);
 876
 877       mark_dfs_back_edges ();
 878     }
 879
 880   find_obviously_necessary_stmts (el);
 881
 882   propagate_necessity (el);
 883
 884   eliminate_unnecessary_stmts ();
 885
 886   if (aggressive)
 887     free_dominance_info (CDI_POST_DOMINATORS);
 888
 889   cleanup_tree_cfg ();
 890
 891   /* Debugging dumps.  */
 892   if (dump_file)
 893     {
 894       dump_function_to_file (current_function_decl, dump_file, dump_flags);
 895       print_stats ();
 896     }
 897
 898   tree_dce_done (aggressive);
 899
 900   free_edge_list (el);
 901 }
 902
 903 /* Pass entry points.  */
 904 static void
 905 tree_ssa_dce (void)
 906 {
 907   perform_tree_ssa_dce (/*aggressive=*/false);
 908 }
 909
 910 static void
 911 tree_ssa_cd_dce (void)
 912 {
 913   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 914 }
 915
 916 static bool
 917 gate_dce (void)
 918 {
 919   return flag_tree_dce != 0;
 920 }
 921
 922 struct tree_opt_pass pass_dce =
 923 {
 924   "dce",                                /* name */
 925   gate_dce,                             /* gate */
 926   tree_ssa_dce,                         /* execute */
 927   NULL,                                 /* sub */
 928   NULL,                                 /* next */
 929   0,                                    /* static_pass_number */
 930   TV_TREE_DCE,                          /* tv_id */
 931   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 932   0,                                    /* properties_provided */
 933   0,                                    /* properties_destroyed */
 934   0,                                    /* todo_flags_start */
 935   TODO_ggc_collect | TODO_verify_ssa,   /* todo_flags_finish */
 936   0                                     /* letter */
 937 };
 938
 939 struct tree_opt_pass pass_cd_dce =
 940 {
 941   "cddce",                              /* name */
 942   gate_dce,                             /* gate */
 943   tree_ssa_cd_dce,                      /* execute */
 944   NULL,                                 /* sub */
 945   NULL,                                 /* next */
 946   0,                                    /* static_pass_number */
 947   TV_TREE_CD_DCE,                       /* tv_id */
 948   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 949   0,                                    /* properties_provided */
 950   0,                                    /* properties_destroyed */
 951   0,                                    /* todo_flags_start */
 952   TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
 953                                         /* todo_flags_finish */
 954   0                                     /* letter */
 955 };
 956