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