gcc/tree-ssa-dce.c

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