gcc/tree-ssa-dce.c

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