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