gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Ben Elliston <bje@redhat.com>
   5    and Andrew MacLeod <amacleod@redhat.com>
   6    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it
  11 under the terms of the GNU General Public License as published by the
  12 Free Software Foundation; either version 3, or (at your option) any
  13 later version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT
  16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  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 "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
  70 static struct stmt_stats
  71 {
  72   int total;
  73   int total_phis;
  74   int removed;
  75   int removed_phis;
  76 } stats;
  77
  78 #define STMT_NECESSARY GF_PLF_1
  79
  80 static VEC(gimple,heap) *worklist;
  81
  82 /* Vector indicating an SSA name has already been processed and marked
  83    as necessary.  */
  84 static sbitmap processed;
  85
  86 /* Vector indicating that last_stmt if a basic block has already been
  87    marked as necessary.  */
  88 static sbitmap last_stmt_necessary;
  89
  90 /* Vector indicating that BB contains statements that are live.  */
  91 static sbitmap bb_contains_live_stmts;
  92
  93 /* Before we can determine whether a control branch is dead, we need to
  94    compute which blocks are control dependent on which edges.
  95
  96    We expect each block to be control dependent on very few edges so we
  97    use a bitmap for each block recording its edges.  An array holds the
  98    bitmap.  The Ith bit in the bitmap is set if that block is dependent
  99    on the Ith edge.  */
 100 static bitmap *control_dependence_map;
 101
 102 /* Vector indicating that a basic block has already had all the edges
 103    processed that it is control dependent on.  */
 104 static sbitmap visited_control_parents;
 105
 106 /* TRUE if this pass alters the CFG (by removing control statements).
 107    FALSE otherwise.
 108
 109    If this pass alters the CFG, then it will arrange for the dominators
 110    to be recomputed.  */
 111 static bool cfg_altered;
 112
 113 /* Execute code that follows the macro for each edge (given number
 114    EDGE_NUMBER within the CODE) for which the block with index N is
 115    control dependent.  */
 116 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)        \
 117   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,     \
 118                             (EDGE_NUMBER), (BI))
 119
 120
 121 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
 122 static inline void
 123 set_control_dependence_map_bit (basic_block bb, int edge_index)
 124 {
 125   if (bb == ENTRY_BLOCK_PTR)
 126     return;
 127   gcc_assert (bb != EXIT_BLOCK_PTR);
 128   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
 129 }
 130
 131 /* Clear all control dependences for block BB.  */
 132 static inline void
 133 clear_control_dependence_bitmap (basic_block bb)
 134 {
 135   bitmap_clear (control_dependence_map[bb->index]);
 136 }
 137
 138
 139 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
 140    This function is necessary because some blocks have negative numbers.  */
 141
 142 static inline basic_block
 143 find_pdom (basic_block block)
 144 {
 145   gcc_assert (block != ENTRY_BLOCK_PTR);
 146
 147   if (block == EXIT_BLOCK_PTR)
 148     return EXIT_BLOCK_PTR;
 149   else
 150     {
 151       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
 152       if (! bb)
 153         return EXIT_BLOCK_PTR;
 154       return bb;
 155     }
 156 }
 157
 158
 159 /* Determine all blocks' control dependences on the given edge with edge_list
 160    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
 161
 162 static void
 163 find_control_dependence (struct edge_list *el, int edge_index)
 164 {
 165   basic_block current_block;
 166   basic_block ending_block;
 167
 168   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
 169
 170   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 171     ending_block = single_succ (ENTRY_BLOCK_PTR);
 172   else
 173     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
 174
 175   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 176        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 177        current_block = find_pdom (current_block))
 178     {
 179       edge e = INDEX_EDGE (el, edge_index);
 180
 181       /* For abnormal edges, we don't make current_block control
 182          dependent because instructions that throw are always necessary
 183          anyway.  */
 184       if (e->flags & EDGE_ABNORMAL)
 185         continue;
 186
 187       set_control_dependence_map_bit (current_block, edge_index);
 188     }
 189 }
 190
 191
 192 /* Record all blocks' control dependences on all edges in the edge
 193    list EL, ala Morgan, Section 3.6.  */
 194
 195 static void
 196 find_all_control_dependences (struct edge_list *el)
 197 {
 198   int i;
 199
 200   for (i = 0; i < NUM_EDGES (el); ++i)
 201     find_control_dependence (el, i);
 202 }
 203
 204 /* If STMT is not already marked necessary, mark it, and add it to the
 205    worklist if ADD_TO_WORKLIST is true.  */
 206 static inline void
 207 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
 208 {
 209   gcc_assert (stmt);
 210
 211   if (gimple_plf (stmt, STMT_NECESSARY))
 212     return;
 213
 214   if (dump_file && (dump_flags & TDF_DETAILS))
 215     {
 216       fprintf (dump_file, "Marking useful stmt: ");
 217       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 218       fprintf (dump_file, "\n");
 219     }
 220
 221   gimple_set_plf (stmt, STMT_NECESSARY, true);
 222   if (add_to_worklist)
 223     VEC_safe_push (gimple, heap, worklist, stmt);
 224   if (bb_contains_live_stmts && !is_gimple_debug (stmt))
 225     SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
 226 }
 227
 228
 229 /* Mark the statement defining operand OP as necessary.  */
 230
 231 static inline void
 232 mark_operand_necessary (tree op)
 233 {
 234   gimple stmt;
 235   int ver;
 236
 237   gcc_assert (op);
 238
 239   ver = SSA_NAME_VERSION (op);
 240   if (TEST_BIT (processed, ver))
 241     {
 242       stmt = SSA_NAME_DEF_STMT (op);
 243       gcc_assert (gimple_nop_p (stmt)
 244                   || gimple_plf (stmt, STMT_NECESSARY));
 245       return;
 246     }
 247   SET_BIT (processed, ver);
 248
 249   stmt = SSA_NAME_DEF_STMT (op);
 250   gcc_assert (stmt);
 251
 252   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
 253     return;
 254
 255   if (dump_file && (dump_flags & TDF_DETAILS))
 256     {
 257       fprintf (dump_file, "marking necessary through ");
 258       print_generic_expr (dump_file, op, 0);
 259       fprintf (dump_file, " stmt ");
 260       print_gimple_stmt (dump_file, stmt, 0, 0);
 261     }
 262
 263   gimple_set_plf (stmt, STMT_NECESSARY, true);
 264   if (bb_contains_live_stmts)
 265     SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
 266   VEC_safe_push (gimple, heap, worklist, stmt);
 267 }
 268
 269
 270 /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
 271    it can make other statements necessary.
 272
 273    If AGGRESSIVE is false, control statements are conservatively marked as
 274    necessary.  */
 275
 276 static void
 277 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
 278 {
 279   tree lhs = NULL_TREE;
 280   /* With non-call exceptions, we have to assume that all statements could
 281      throw.  If a statement may throw, it is inherently necessary.  */
 282   if (flag_non_call_exceptions
 283       && stmt_could_throw_p (stmt))
 284     {
 285       mark_stmt_necessary (stmt, true);
 286       return;
 287     }
 288
 289   /* Statements that are implicitly live.  Most function calls, asm
 290      and return statements are required.  Labels and GIMPLE_BIND nodes
 291      are kept because they are control flow, and we have no way of
 292      knowing whether they can be removed.  DCE can eliminate all the
 293      other statements in a block, and CFG can then remove the block
 294      and labels.  */
 295   switch (gimple_code (stmt))
 296     {
 297     case GIMPLE_PREDICT:
 298     case GIMPLE_LABEL:
 299       mark_stmt_necessary (stmt, false);
 300       return;
 301
 302     case GIMPLE_ASM:
 303     case GIMPLE_RESX:
 304     case GIMPLE_RETURN:
 305       mark_stmt_necessary (stmt, true);
 306       return;
 307
 308     case GIMPLE_CALL:
 309       /* Most, but not all function calls are required.  Function calls that
 310          produce no result and have no side effects (i.e. const pure
 311          functions) are unnecessary.  */
 312       if (gimple_has_side_effects (stmt))
 313         {
 314           mark_stmt_necessary (stmt, true);
 315           return;
 316         }
 317       if (!gimple_call_lhs (stmt))
 318         return;
 319       lhs = gimple_call_lhs (stmt);
 320       /* Fall through */
 321
 322     case GIMPLE_ASSIGN:
 323       if (!lhs)
 324         lhs = gimple_assign_lhs (stmt);
 325       break;
 326
 327     case GIMPLE_DEBUG:
 328       mark_stmt_necessary (stmt, false);
 329       return;
 330
 331     case GIMPLE_GOTO:
 332       gcc_assert (!simple_goto_p (stmt));
 333       mark_stmt_necessary (stmt, true);
 334       return;
 335
 336     case GIMPLE_COND:
 337       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
 338       /* Fall through.  */
 339
 340     case GIMPLE_SWITCH:
 341       if (! aggressive)
 342         mark_stmt_necessary (stmt, true);
 343       break;
 344
 345     default:
 346       break;
 347     }
 348
 349   /* If the statement has volatile operands, it needs to be preserved.
 350      Same for statements that can alter control flow in unpredictable
 351      ways.  */
 352   if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
 353     {
 354       mark_stmt_necessary (stmt, true);
 355       return;
 356     }
 357
 358   if (is_hidden_global_store (stmt))
 359     {
 360       mark_stmt_necessary (stmt, true);
 361       return;
 362     }
 363
 364   return;
 365 }
 366
 367
 368 /* Make corresponding control dependent edges necessary.  We only
 369    have to do this once for each basic block, so we clear the bitmap
 370    after we're done.  */
 371 static void
 372 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 373 {
 374   bitmap_iterator bi;
 375   unsigned edge_number;
 376
 377   gcc_assert (bb != EXIT_BLOCK_PTR);
 378
 379   if (bb == ENTRY_BLOCK_PTR)
 380     return;
 381
 382   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 383     {
 384       gimple stmt;
 385       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 386
 387       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 388         continue;
 389       SET_BIT (last_stmt_necessary, cd_bb->index);
 390       SET_BIT (bb_contains_live_stmts, cd_bb->index);
 391
 392       stmt = last_stmt (cd_bb);
 393       if (stmt && is_ctrl_stmt (stmt))
 394         mark_stmt_necessary (stmt, true);
 395     }
 396 }
 397
 398
 399 /* Find obviously necessary statements.  These are things like most function
 400    calls, and stores to file level variables.
 401
 402    If EL is NULL, control statements are conservatively marked as
 403    necessary.  Otherwise it contains the list of edges used by control
 404    dependence analysis.  */
 405
 406 static void
 407 find_obviously_necessary_stmts (struct edge_list *el)
 408 {
 409   basic_block bb;
 410   gimple_stmt_iterator gsi;
 411   edge e;
 412   gimple phi, stmt;
 413
 414   FOR_EACH_BB (bb)
 415     {
 416       /* PHI nodes are never inherently necessary.  */
 417       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 418         {
 419           phi = gsi_stmt (gsi);
 420           gimple_set_plf (phi, STMT_NECESSARY, false);
 421         }
 422
 423       /* Check all statements in the block.  */
 424       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 425         {
 426           stmt = gsi_stmt (gsi);
 427           gimple_set_plf (stmt, STMT_NECESSARY, false);
 428           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 429         }
 430     }
 431
 432   /* Pure and const functions are finite and thus have no infinite loops in
 433      them.  */
 434   if ((TREE_READONLY (current_function_decl)
 435        || DECL_PURE_P (current_function_decl))
 436       && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
 437     return;
 438
 439   /* Prevent the empty possibly infinite loops from being removed.  */
 440   if (el)
 441     {
 442       loop_iterator li;
 443       struct loop *loop;
 444       scev_initialize ();
 445       if (mark_irreducible_loops ())
 446         FOR_EACH_BB (bb)
 447           {
 448             edge_iterator ei;
 449             FOR_EACH_EDGE (e, ei, bb->succs)
 450               if ((e->flags & EDGE_DFS_BACK)
 451                   && (e->flags & EDGE_IRREDUCIBLE_LOOP))
 452                 {
 453                   if (dump_file)
 454                     fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
 455                              e->src->index, e->dest->index);
 456                   mark_control_dependent_edges_necessary (e->dest, el);
 457                 }
 458           }
 459
 460       FOR_EACH_LOOP (li, loop, 0)
 461         if (!finite_loop_p (loop))
 462           {
 463             if (dump_file)
 464               fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
 465             mark_control_dependent_edges_necessary (loop->latch, el);
 466           }
 467       scev_finalize ();
 468     }
 469 }
 470
 471
 472 /* Return true if REF is based on an aliased base, otherwise false.  */
 473
 474 static bool
 475 ref_may_be_aliased (tree ref)
 476 {
 477   while (handled_component_p (ref))
 478     ref = TREE_OPERAND (ref, 0);
 479   return !(DECL_P (ref)
 480            && !may_be_aliased (ref));
 481 }
 482
 483 static bitmap visited = NULL;
 484 static unsigned int longest_chain = 0;
 485 static unsigned int total_chain = 0;
 486 static bool chain_ovfl = false;
 487
 488 /* Worker for the walker that marks reaching definitions of REF,
 489    which is based on a non-aliased decl, necessary.  It returns
 490    true whenever the defining statement of the current VDEF is
 491    a kill for REF, as no dominating may-defs are necessary for REF
 492    anymore.  DATA points to cached get_ref_base_and_extent data for REF.  */
 493
 494 static bool
 495 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
 496                                         void *data ATTRIBUTE_UNUSED)
 497 {
 498   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
 499
 500   /* All stmts we visit are necessary.  */
 501   mark_operand_necessary (vdef);
 502
 503   /* If the stmt lhs kills ref, then we can stop walking.  */
 504   if (gimple_has_lhs (def_stmt)
 505       && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
 506     {
 507       tree base, lhs = gimple_get_lhs (def_stmt);
 508       HOST_WIDE_INT size, offset, max_size;
 509       ao_ref_base (ref);
 510       base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
 511       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
 512          so base == refd->base does not always hold.  */
 513       if (base == ref->base)
 514         {
 515           /* For a must-alias check we need to be able to constrain
 516              the accesses properly.  */
 517           if (size != -1 && size == max_size
 518               && ref->max_size != -1)
 519             {
 520               if (offset <= ref->offset
 521                   && offset + size >= ref->offset + ref->max_size)
 522                 return true;
 523             }
 524           /* Or they need to be exactly the same.  */
 525           else if (ref->ref
 526                    && operand_equal_p (ref->ref, lhs, 0))
 527             return true;
 528         }
 529     }
 530
 531   /* Otherwise keep walking.  */
 532   return false;
 533 }
 534
 535 static void
 536 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
 537 {
 538   unsigned int chain;
 539   ao_ref refd;
 540   gcc_assert (!chain_ovfl);
 541   ao_ref_init (&refd, ref);
 542   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
 543                               mark_aliased_reaching_defs_necessary_1,
 544                               NULL, NULL);
 545   if (chain > longest_chain)
 546     longest_chain = chain;
 547   total_chain += chain;
 548 }
 549
 550 /* Worker for the walker that marks reaching definitions of REF, which
 551    is not based on a non-aliased decl.  For simplicity we need to end
 552    up marking all may-defs necessary that are not based on a non-aliased
 553    decl.  The only job of this walker is to skip may-defs based on
 554    a non-aliased decl.  */
 555
 556 static bool
 557 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
 558                                     tree vdef, void *data ATTRIBUTE_UNUSED)
 559 {
 560   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
 561
 562   /* We have to skip already visited (and thus necessary) statements
 563      to make the chaining work after we dropped back to simple mode.  */
 564   if (chain_ovfl
 565       && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
 566     {
 567       gcc_assert (gimple_nop_p (def_stmt)
 568                   || gimple_plf (def_stmt, STMT_NECESSARY));
 569       return false;
 570     }
 571
 572   /* We want to skip stores to non-aliased variables.  */
 573   if (!chain_ovfl
 574       && gimple_assign_single_p (def_stmt))
 575     {
 576       tree lhs = gimple_assign_lhs (def_stmt);
 577       if (!ref_may_be_aliased (lhs))
 578         return false;
 579     }
 580
 581   mark_operand_necessary (vdef);
 582
 583   return false;
 584 }
 585
 586 static void
 587 mark_all_reaching_defs_necessary (gimple stmt)
 588 {
 589   walk_aliased_vdefs (NULL, gimple_vuse (stmt),
 590                       mark_all_reaching_defs_necessary_1, NULL, &visited);
 591 }
 592
 593 /* Return true for PHI nodes with one or identical arguments
 594    can be removed.  */
 595 static bool
 596 degenerate_phi_p (gimple phi)
 597 {
 598   unsigned int i;
 599   tree op = gimple_phi_arg_def (phi, 0);
 600   for (i = 1; i < gimple_phi_num_args (phi); i++)
 601     if (gimple_phi_arg_def (phi, i) != op)
 602       return false;
 603   return true;
 604 }
 605
 606 /* Propagate necessity using the operands of necessary statements.
 607    Process the uses on each statement in the worklist, and add all
 608    feeding statements which contribute to the calculation of this
 609    value to the worklist.
 610
 611    In conservative mode, EL is NULL.  */
 612
 613 static void
 614 propagate_necessity (struct edge_list *el)
 615 {
 616   gimple stmt;
 617   bool aggressive = (el ? true : false);
 618
 619   if (dump_file && (dump_flags & TDF_DETAILS))
 620     fprintf (dump_file, "\nProcessing worklist:\n");
 621
 622   while (VEC_length (gimple, worklist) > 0)
 623     {
 624       /* Take STMT from worklist.  */
 625       stmt = VEC_pop (gimple, worklist);
 626
 627       if (dump_file && (dump_flags & TDF_DETAILS))
 628         {
 629           fprintf (dump_file, "processing: ");
 630           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 631           fprintf (dump_file, "\n");
 632         }
 633
 634       if (aggressive)
 635         {
 636           /* Mark the last statements of the basic blocks that the block
 637              containing STMT is control dependent on, but only if we haven't
 638              already done so.  */
 639           basic_block bb = gimple_bb (stmt);
 640           if (bb != ENTRY_BLOCK_PTR
 641               && ! TEST_BIT (visited_control_parents, bb->index))
 642             {
 643               SET_BIT (visited_control_parents, bb->index);
 644               mark_control_dependent_edges_necessary (bb, el);
 645             }
 646         }
 647
 648       if (gimple_code (stmt) == GIMPLE_PHI
 649           /* We do not process virtual PHI nodes nor do we track their
 650              necessity.  */
 651           && is_gimple_reg (gimple_phi_result (stmt)))
 652         {
 653           /* PHI nodes are somewhat special in that each PHI alternative has
 654              data and control dependencies.  All the statements feeding the
 655              PHI node's arguments are always necessary.  In aggressive mode,
 656              we also consider the control dependent edges leading to the
 657              predecessor block associated with each PHI alternative as
 658              necessary.  */
 659           size_t k;
 660
 661           for (k = 0; k < gimple_phi_num_args (stmt); k++)
 662             {
 663               tree arg = PHI_ARG_DEF (stmt, k);
 664               if (TREE_CODE (arg) == SSA_NAME)
 665                 mark_operand_necessary (arg);
 666             }
 667
 668           if (aggressive && !degenerate_phi_p (stmt))
 669             {
 670               for (k = 0; k < gimple_phi_num_args (stmt); k++)
 671                 {
 672                   basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
 673                   if (arg_bb != ENTRY_BLOCK_PTR
 674                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 675                     {
 676                       SET_BIT (visited_control_parents, arg_bb->index);
 677                       mark_control_dependent_edges_necessary (arg_bb, el);
 678                     }
 679                 }
 680             }
 681         }
 682       else
 683         {
 684           /* Propagate through the operands.  Examine all the USE, VUSE and
 685              VDEF operands in this statement.  Mark all the statements
 686              which feed this statement's uses as necessary.  */
 687           ssa_op_iter iter;
 688           tree use;
 689
 690           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 691             mark_operand_necessary (use);
 692
 693           use = gimple_vuse (stmt);
 694           if (!use)
 695             continue;
 696
 697           /* If we dropped to simple mode make all immediately
 698              reachable definitions necessary.  */
 699           if (chain_ovfl)
 700             {
 701               mark_all_reaching_defs_necessary (stmt);
 702               continue;
 703             }
 704
 705           /* For statements that may load from memory (have a VUSE) we
 706              have to mark all reaching (may-)definitions as necessary.
 707              We partition this task into two cases:
 708               1) explicit loads based on decls that are not aliased
 709               2) implicit loads (like calls) and explicit loads not
 710                  based on decls that are not aliased (like indirect
 711                  references or loads from globals)
 712              For 1) we mark all reaching may-defs as necessary, stopping
 713              at dominating kills.  For 2) we want to mark all dominating
 714              references necessary, but non-aliased ones which we handle
 715              in 1).  By keeping a global visited bitmap for references
 716              we walk for 2) we avoid quadratic behavior for those.  */
 717
 718           if (is_gimple_call (stmt))
 719             {
 720               tree callee = gimple_call_fndecl (stmt);
 721               unsigned i;
 722
 723               /* Calls to functions that are merely acting as barriers
 724                  or that only store to memory do not make any previous
 725                  stores necessary.  */
 726               if (callee != NULL_TREE
 727                   && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
 728                   && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
 729                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
 730                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
 731                 continue;
 732
 733               /* Calls implicitly load from memory, their arguments
 734                  in addition may explicitly perform memory loads.  */
 735               mark_all_reaching_defs_necessary (stmt);
 736               for (i = 0; i < gimple_call_num_args (stmt); ++i)
 737                 {
 738                   tree arg = gimple_call_arg (stmt, i);
 739                   if (TREE_CODE (arg) == SSA_NAME
 740                       || is_gimple_min_invariant (arg))
 741                     continue;
 742                   if (!ref_may_be_aliased (arg))
 743                     mark_aliased_reaching_defs_necessary (stmt, arg);
 744                 }
 745             }
 746           else if (gimple_assign_single_p (stmt))
 747             {
 748               tree rhs;
 749               bool rhs_aliased = false;
 750               /* If this is a load mark things necessary.  */
 751               rhs = gimple_assign_rhs1 (stmt);
 752               if (TREE_CODE (rhs) != SSA_NAME
 753                   && !is_gimple_min_invariant (rhs))
 754                 {
 755                   if (!ref_may_be_aliased (rhs))
 756                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 757                   else
 758                     rhs_aliased = true;
 759                 }
 760               if (rhs_aliased)
 761                 mark_all_reaching_defs_necessary (stmt);
 762             }
 763           else if (gimple_code (stmt) == GIMPLE_RETURN)
 764             {
 765               tree rhs = gimple_return_retval (stmt);
 766               /* A return statement may perform a load.  */
 767               if (TREE_CODE (rhs) != SSA_NAME
 768                   && !is_gimple_min_invariant (rhs))
 769                 {
 770                   if (!ref_may_be_aliased (rhs))
 771                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 772                   else
 773                     mark_all_reaching_defs_necessary (stmt);
 774                 }
 775             }
 776           else if (gimple_code (stmt) == GIMPLE_ASM)
 777             {
 778               unsigned i;
 779               mark_all_reaching_defs_necessary (stmt);
 780               /* Inputs may perform loads.  */
 781               for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
 782                 {
 783                   tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
 784                   if (TREE_CODE (op) != SSA_NAME
 785                       && !is_gimple_min_invariant (op)
 786                       && !ref_may_be_aliased (op))
 787                     mark_aliased_reaching_defs_necessary (stmt, op);
 788                 }
 789             }
 790           else
 791             gcc_unreachable ();
 792
 793           /* If we over-used our alias oracle budget drop to simple
 794              mode.  The cost metric allows quadratic behavior up to
 795              a constant maximal chain and after that falls back to
 796              super-linear complexity.  */
 797           if (longest_chain > 256
 798               && total_chain > 256 * longest_chain)
 799             {
 800               chain_ovfl = true;
 801               if (visited)
 802                 bitmap_clear (visited);
 803             }
 804         }
 805     }
 806 }
 807
 808 /* Replace all uses of result of PHI by underlying variable and mark it
 809    for renaming.  */
 810
 811 void
 812 mark_virtual_phi_result_for_renaming (gimple phi)
 813 {
 814   bool used = false;
 815   imm_use_iterator iter;
 816   use_operand_p use_p;
 817   gimple stmt;
 818   tree result_ssa, result_var;
 819
 820   if (dump_file && (dump_flags & TDF_DETAILS))
 821     {
 822       fprintf (dump_file, "Marking result for renaming : ");
 823       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 824       fprintf (dump_file, "\n");
 825     }
 826
 827   result_ssa = gimple_phi_result (phi);
 828   result_var = SSA_NAME_VAR (result_ssa);
 829   FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
 830     {
 831       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 832         SET_USE (use_p, result_var);
 833       update_stmt (stmt);
 834       used = true;
 835     }
 836   if (used)
 837     mark_sym_for_renaming (result_var);
 838 }
 839
 840 /* Remove dead PHI nodes from block BB.  */
 841
 842 static bool
 843 remove_dead_phis (basic_block bb)
 844 {
 845   bool something_changed = false;
 846   gimple_seq phis;
 847   gimple phi;
 848   gimple_stmt_iterator gsi;
 849   phis = phi_nodes (bb);
 850
 851   for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
 852     {
 853       stats.total_phis++;
 854       phi = gsi_stmt (gsi);
 855
 856       /* We do not track necessity of virtual PHI nodes.  Instead do
 857          very simple dead PHI removal here.  */
 858       if (!is_gimple_reg (gimple_phi_result (phi)))
 859         {
 860           /* Virtual PHI nodes with one or identical arguments
 861              can be removed.  */
 862           if (degenerate_phi_p (phi))
 863             {
 864               tree vdef = gimple_phi_result (phi);
 865               tree vuse = gimple_phi_arg_def (phi, 0);
 866
 867               use_operand_p use_p;
 868               imm_use_iterator iter;
 869               gimple use_stmt;
 870               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
 871                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 872                   SET_USE (use_p, vuse);
 873               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
 874                   && TREE_CODE (vuse) == SSA_NAME)
 875                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
 876             }
 877           else
 878             gimple_set_plf (phi, STMT_NECESSARY, true);
 879         }
 880
 881       if (!gimple_plf (phi, STMT_NECESSARY))
 882         {
 883           something_changed = true;
 884           if (dump_file && (dump_flags & TDF_DETAILS))
 885             {
 886               fprintf (dump_file, "Deleting : ");
 887               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 888               fprintf (dump_file, "\n");
 889             }
 890
 891           remove_phi_node (&gsi, true);
 892           stats.removed_phis++;
 893           continue;
 894         }
 895
 896       gsi_next (&gsi);
 897     }
 898   return something_changed;
 899 }
 900
 901 /* Find first live post dominator of BB.  */
 902
 903 static basic_block
 904 get_live_post_dom (basic_block bb)
 905 {
 906   basic_block post_dom_bb;
 907
 908
 909   /* The post dominance info has to be up-to-date.  */
 910   gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
 911
 912   /* Get the immediate post dominator of bb.  */
 913   post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 914   /* And look for first live one.  */
 915   while (post_dom_bb != EXIT_BLOCK_PTR
 916          && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
 917     post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
 918
 919   return post_dom_bb;
 920 }
 921
 922 /* Forward edge E to respective POST_DOM_BB and update PHIs.  */
 923
 924 static edge
 925 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
 926 {
 927   gimple_stmt_iterator gsi;
 928   edge e2 = NULL;
 929   edge_iterator ei;
 930
 931   if (dump_file && (dump_flags & TDF_DETAILS))
 932     fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
 933              e->dest->index, post_dom_bb->index);
 934
 935   e2 = redirect_edge_and_branch (e, post_dom_bb);
 936   cfg_altered = true;
 937
 938   /* If edge was already around, no updating is neccesary.  */
 939   if (e2 != e)
 940     return e2;
 941
 942   if (phi_nodes (post_dom_bb))
 943     {
 944       /* We are sure that for every live PHI we are seeing control dependent BB.
 945          This means that we can look up the end of control dependent path leading
 946          to the PHI itself.  */
 947       FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
 948         if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
 949           break;
 950       for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
 951         {
 952           gimple phi = gsi_stmt (gsi);
 953           tree op;
 954           source_location locus;
 955
 956           /* Dead PHI do not imply control dependency.  */
 957           if (!gimple_plf (phi, STMT_NECESSARY)
 958               && is_gimple_reg (gimple_phi_result (phi)))
 959             {
 960               gsi_next (&gsi);
 961               continue;
 962             }
 963           if (gimple_phi_arg_def (phi, e->dest_idx))
 964             {
 965               gsi_next (&gsi);
 966               continue;
 967             }
 968
 969           /* We didn't find edge to update.  This can happen for PHIs on virtuals
 970              since there is no control dependency relation on them.  We are lost
 971              here and must force renaming of the symbol.  */
 972           if (!is_gimple_reg (gimple_phi_result (phi)))
 973             {
 974               mark_virtual_phi_result_for_renaming (phi);
 975               remove_phi_node (&gsi, true);
 976               continue;
 977             }
 978           if (!e2)
 979             {
 980               op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
 981               locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0);
 982             }
 983           else
 984             {
 985               op = gimple_phi_arg_def (phi, e2->dest_idx);
 986               locus = gimple_phi_arg_location (phi, e2->dest_idx);
 987             }
 988           add_phi_arg (phi, op, e, locus);
 989           gcc_assert (e2 || degenerate_phi_p (phi));
 990           gsi_next (&gsi);
 991         }
 992     }
 993   return e;
 994 }
 995
 996 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 997    containing I so that we don't have to look it up.  */
 998
 999 static void
1000 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
1001 {
1002   gimple stmt = gsi_stmt (*i);
1003
1004   if (dump_file && (dump_flags & TDF_DETAILS))
1005     {
1006       fprintf (dump_file, "Deleting : ");
1007       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1008       fprintf (dump_file, "\n");
1009     }
1010
1011   stats.removed++;
1012
1013   /* If we have determined that a conditional branch statement contributes
1014      nothing to the program, then we not only remove it, but we also change
1015      the flow graph so that the current block will simply fall-thru to its
1016      immediate post-dominator.  The blocks we are circumventing will be
1017      removed by cleanup_tree_cfg if this change in the flow graph makes them
1018      unreachable.  */
1019   if (is_ctrl_stmt (stmt))
1020     {
1021       basic_block post_dom_bb;
1022       edge e, e2;
1023       edge_iterator ei;
1024
1025       post_dom_bb = get_live_post_dom (bb);
1026
1027       e = find_edge (bb, post_dom_bb);
1028
1029       /* If edge is already there, try to use it.  This avoids need to update
1030          PHI nodes.  Also watch for cases where post dominator does not exists
1031          or is exit block.  These can happen for infinite loops as we create
1032          fake edges in the dominator tree.  */
1033       if (e)
1034         ;
1035       else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
1036         e = EDGE_SUCC (bb, 0);
1037       else
1038         e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1039       gcc_assert (e);
1040       e->probability = REG_BR_PROB_BASE;
1041       e->count = bb->count;
1042
1043       /* The edge is no longer associated with a conditional, so it does
1044          not have TRUE/FALSE flags.  */
1045       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1046
1047       /* The lone outgoing edge from BB will be a fallthru edge.  */
1048       e->flags |= EDGE_FALLTHRU;
1049
1050       /* Remove the remaining outgoing edges.  */
1051       for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1052         if (e != e2)
1053           {
1054             cfg_altered = true;
1055             remove_edge (e2);
1056           }
1057         else
1058           ei_next (&ei);
1059     }
1060
1061   unlink_stmt_vdef (stmt);
1062   gsi_remove (i, true);
1063   release_defs (stmt);
1064 }
1065
1066 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1067    contributes nothing to the program, and can be deleted.  */
1068
1069 static bool
1070 eliminate_unnecessary_stmts (void)
1071 {
1072   bool something_changed = false;
1073   basic_block bb;
1074   gimple_stmt_iterator gsi;
1075   gimple stmt;
1076   tree call;
1077   VEC (basic_block, heap) *h;
1078
1079   if (dump_file && (dump_flags & TDF_DETAILS))
1080     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1081
1082   clear_special_calls ();
1083
1084   /* Walking basic blocks and statements in reverse order avoids
1085      releasing SSA names before any other DEFs that refer to them are
1086      released.  This helps avoid loss of debug information, as we get
1087      a chance to propagate all RHSs of removed SSAs into debug uses,
1088      rather than only the latest ones.  E.g., consider:
1089
1090      x_3 = y_1 + z_2;
1091      a_5 = x_3 - b_4;
1092      # DEBUG a => a_5
1093
1094      If we were to release x_3 before a_5, when we reached a_5 and
1095      tried to substitute it into the debug stmt, we'd see x_3 there,
1096      but x_3's DEF, type, etc would have already been disconnected.
1097      By going backwards, the debug stmt first changes to:
1098
1099      # DEBUG a => x_3 - b_4
1100
1101      and then to:
1102
1103      # DEBUG a => y_1 + z_2 - b_4
1104
1105      as desired.  */
1106   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1107   h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
1108
1109   while (VEC_length (basic_block, h))
1110     {
1111       bb = VEC_pop (basic_block, h);
1112
1113       /* Remove dead statements.  */
1114       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1115         {
1116           stmt = gsi_stmt (gsi);
1117
1118           stats.total++;
1119
1120           /* If GSI is not necessary then remove it.  */
1121           if (!gimple_plf (stmt, STMT_NECESSARY))
1122             {
1123               remove_dead_stmt (&gsi, bb);
1124               something_changed = true;
1125
1126               /* If stmt was the last stmt in the block, we want to
1127                  move gsi to the stmt that became the last stmt, but
1128                  gsi_prev would crash.  */
1129               if (gsi_end_p (gsi))
1130                 gsi = gsi_last_bb (bb);
1131               else
1132                 gsi_prev (&gsi);
1133             }
1134           else if (is_gimple_call (stmt))
1135             {
1136               call = gimple_call_fndecl (stmt);
1137               if (call)
1138                 {
1139                   tree name;
1140
1141                   /* When LHS of var = call (); is dead, simplify it into
1142                      call (); saving one operand.  */
1143                   name = gimple_call_lhs (stmt);
1144                   if (name && TREE_CODE (name) == SSA_NAME
1145                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1146                     {
1147                       something_changed = true;
1148                       if (dump_file && (dump_flags & TDF_DETAILS))
1149                         {
1150                           fprintf (dump_file, "Deleting LHS of call: ");
1151                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1152                           fprintf (dump_file, "\n");
1153                         }
1154
1155                       gimple_call_set_lhs (stmt, NULL_TREE);
1156                       maybe_clean_or_replace_eh_stmt (stmt, stmt);
1157                       update_stmt (stmt);
1158                       release_ssa_name (name);
1159                     }
1160                   notice_special_calls (stmt);
1161                 }
1162               gsi_prev (&gsi);
1163             }
1164           else
1165             gsi_prev (&gsi);
1166         }
1167     }
1168
1169   VEC_free (basic_block, heap, h);
1170
1171   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1172      rendered some PHI nodes unreachable while they are still in use.
1173      Mark them for renaming.  */
1174   if (cfg_altered)
1175     {
1176       basic_block prev_bb;
1177
1178       find_unreachable_blocks ();
1179
1180       /* Delete all unreachable basic blocks in reverse dominator order.  */
1181       for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
1182         {
1183           prev_bb = bb->prev_bb;
1184
1185           if (!TEST_BIT (bb_contains_live_stmts, bb->index)
1186               || !(bb->flags & BB_REACHABLE))
1187             {
1188               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1189                 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1190                   {
1191                     bool found = false;
1192                     imm_use_iterator iter;
1193
1194                     FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1195                       {
1196                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1197                           continue;
1198                         if (gimple_code (stmt) == GIMPLE_PHI
1199                             || gimple_plf (stmt, STMT_NECESSARY))
1200                           {
1201                             found = true;
1202                             BREAK_FROM_IMM_USE_STMT (iter);
1203                           }
1204                       }
1205                     if (found)
1206                       mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1207                   }
1208
1209               if (!(bb->flags & BB_REACHABLE))
1210                 {
1211                   /* Speed up the removal of blocks that don't
1212                      dominate others.  Walking backwards, this should
1213                      be the common case.  ??? Do we need to recompute
1214                      dominators because of cfg_altered?  */
1215                   if (!MAY_HAVE_DEBUG_STMTS
1216                       || !first_dom_son (CDI_DOMINATORS, bb))
1217                     delete_basic_block (bb);
1218                   else
1219                     {
1220                       h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1221
1222                       while (VEC_length (basic_block, h))
1223                         {
1224                           bb = VEC_pop (basic_block, h);
1225                           prev_bb = bb->prev_bb;
1226                           /* Rearrangements to the CFG may have failed
1227                              to update the dominators tree, so that
1228                              formerly-dominated blocks are now
1229                              otherwise reachable.  */
1230                           if (!!(bb->flags & BB_REACHABLE))
1231                             continue;
1232                           delete_basic_block (bb);
1233                         }
1234
1235                       VEC_free (basic_block, heap, h);
1236                     }
1237                 }
1238             }
1239         }
1240     }
1241   FOR_EACH_BB (bb)
1242     {
1243       /* Remove dead PHI nodes.  */
1244       something_changed |= remove_dead_phis (bb);
1245     }
1246
1247   return something_changed;
1248 }
1249
1250
1251 /* Print out removed statement statistics.  */
1252
1253 static void
1254 print_stats (void)
1255 {
1256   float percg;
1257
1258   percg = ((float) stats.removed / (float) stats.total) * 100;
1259   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1260            stats.removed, stats.total, (int) percg);
1261
1262   if (stats.total_phis == 0)
1263     percg = 0;
1264   else
1265     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1266
1267   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1268            stats.removed_phis, stats.total_phis, (int) percg);
1269 }
1270
1271 /* Initialization for this pass.  Set up the used data structures.  */
1272
1273 static void
1274 tree_dce_init (bool aggressive)
1275 {
1276   memset ((void *) &stats, 0, sizeof (stats));
1277
1278   if (aggressive)
1279     {
1280       int i;
1281
1282       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1283       for (i = 0; i < last_basic_block; ++i)
1284         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1285
1286       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1287       sbitmap_zero (last_stmt_necessary);
1288       bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1289       sbitmap_zero (bb_contains_live_stmts);
1290     }
1291
1292   processed = sbitmap_alloc (num_ssa_names + 1);
1293   sbitmap_zero (processed);
1294
1295   worklist = VEC_alloc (gimple, heap, 64);
1296   cfg_altered = false;
1297 }
1298
1299 /* Cleanup after this pass.  */
1300
1301 static void
1302 tree_dce_done (bool aggressive)
1303 {
1304   if (aggressive)
1305     {
1306       int i;
1307
1308       for (i = 0; i < last_basic_block; ++i)
1309         BITMAP_FREE (control_dependence_map[i]);
1310       free (control_dependence_map);
1311
1312       sbitmap_free (visited_control_parents);
1313       sbitmap_free (last_stmt_necessary);
1314       sbitmap_free (bb_contains_live_stmts);
1315       bb_contains_live_stmts = NULL;
1316     }
1317
1318   sbitmap_free (processed);
1319
1320   VEC_free (gimple, heap, worklist);
1321 }
1322
1323 /* Main routine to eliminate dead code.
1324
1325    AGGRESSIVE controls the aggressiveness of the algorithm.
1326    In conservative mode, we ignore control dependence and simply declare
1327    all but the most trivially dead branches necessary.  This mode is fast.
1328    In aggressive mode, control dependences are taken into account, which
1329    results in more dead code elimination, but at the cost of some time.
1330
1331    FIXME: Aggressive mode before PRE doesn't work currently because
1332           the dominance info is not invalidated after DCE1.  This is
1333           not an issue right now because we only run aggressive DCE
1334           as the last tree SSA pass, but keep this in mind when you
1335           start experimenting with pass ordering.  */
1336
1337 static unsigned int
1338 perform_tree_ssa_dce (bool aggressive)
1339 {
1340   struct edge_list *el = NULL;
1341   bool something_changed = 0;
1342
1343   /* Preheaders are needed for SCEV to work.
1344      Simple lateches and recorded exits improve chances that loop will
1345      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
1346   if (aggressive)
1347     loop_optimizer_init (LOOPS_NORMAL
1348                          | LOOPS_HAVE_RECORDED_EXITS);
1349
1350   tree_dce_init (aggressive);
1351
1352   if (aggressive)
1353     {
1354       /* Compute control dependence.  */
1355       timevar_push (TV_CONTROL_DEPENDENCES);
1356       calculate_dominance_info (CDI_POST_DOMINATORS);
1357       el = create_edge_list ();
1358       find_all_control_dependences (el);
1359       timevar_pop (TV_CONTROL_DEPENDENCES);
1360
1361       visited_control_parents = sbitmap_alloc (last_basic_block);
1362       sbitmap_zero (visited_control_parents);
1363
1364       mark_dfs_back_edges ();
1365     }
1366
1367   find_obviously_necessary_stmts (el);
1368
1369   if (aggressive)
1370     loop_optimizer_finalize ();
1371
1372   longest_chain = 0;
1373   total_chain = 0;
1374   chain_ovfl = false;
1375   propagate_necessity (el);
1376   BITMAP_FREE (visited);
1377
1378   something_changed |= eliminate_unnecessary_stmts ();
1379   something_changed |= cfg_altered;
1380
1381   /* We do not update postdominators, so free them unconditionally.  */
1382   free_dominance_info (CDI_POST_DOMINATORS);
1383
1384   /* If we removed paths in the CFG, then we need to update
1385      dominators as well.  I haven't investigated the possibility
1386      of incrementally updating dominators.  */
1387   if (cfg_altered)
1388     free_dominance_info (CDI_DOMINATORS);
1389
1390   statistics_counter_event (cfun, "Statements deleted", stats.removed);
1391   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1392
1393   /* Debugging dumps.  */
1394   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1395     print_stats ();
1396
1397   tree_dce_done (aggressive);
1398
1399   free_edge_list (el);
1400
1401   if (something_changed)
1402     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1403             | TODO_remove_unused_locals);
1404   else
1405     return 0;
1406 }
1407
1408 /* Pass entry points.  */
1409 static unsigned int
1410 tree_ssa_dce (void)
1411 {
1412   return perform_tree_ssa_dce (/*aggressive=*/false);
1413 }
1414
1415 static unsigned int
1416 tree_ssa_dce_loop (void)
1417 {
1418   unsigned int todo;
1419   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1420   if (todo)
1421     {
1422       free_numbers_of_iterations_estimates ();
1423       scev_reset ();
1424     }
1425   return todo;
1426 }
1427
1428 static unsigned int
1429 tree_ssa_cd_dce (void)
1430 {
1431   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1432 }
1433
1434 static bool
1435 gate_dce (void)
1436 {
1437   return flag_tree_dce != 0;
1438 }
1439
1440 struct gimple_opt_pass pass_dce =
1441 {
1442  {
1443   GIMPLE_PASS,
1444   "dce",                                /* name */
1445   gate_dce,                             /* gate */
1446   tree_ssa_dce,                         /* execute */
1447   NULL,                                 /* sub */
1448   NULL,                                 /* next */
1449   0,                                    /* static_pass_number */
1450   TV_TREE_DCE,                          /* tv_id */
1451   PROP_cfg | PROP_ssa,                  /* properties_required */
1452   0,                                    /* properties_provided */
1453   0,                                    /* properties_destroyed */
1454   0,                                    /* todo_flags_start */
1455   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1456  }
1457 };
1458
1459 struct gimple_opt_pass pass_dce_loop =
1460 {
1461  {
1462   GIMPLE_PASS,
1463   "dceloop",                            /* name */
1464   gate_dce,                             /* gate */
1465   tree_ssa_dce_loop,                    /* execute */
1466   NULL,                                 /* sub */
1467   NULL,                                 /* next */
1468   0,                                    /* static_pass_number */
1469   TV_TREE_DCE,                          /* tv_id */
1470   PROP_cfg | PROP_ssa,                  /* properties_required */
1471   0,                                    /* properties_provided */
1472   0,                                    /* properties_destroyed */
1473   0,                                    /* todo_flags_start */
1474   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1475  }
1476 };
1477
1478 struct gimple_opt_pass pass_cd_dce =
1479 {
1480  {
1481   GIMPLE_PASS,
1482   "cddce",                              /* name */
1483   gate_dce,                             /* gate */
1484   tree_ssa_cd_dce,                      /* execute */
1485   NULL,                                 /* sub */
1486   NULL,                                 /* next */
1487   0,                                    /* static_pass_number */
1488   TV_TREE_CD_DCE,                       /* tv_id */
1489   PROP_cfg | PROP_ssa,                  /* properties_required */
1490   0,                                    /* properties_provided */
1491   0,                                    /* properties_destroyed */
1492   0,                                    /* todo_flags_start */
1493   TODO_dump_func | TODO_verify_ssa
1494   | TODO_verify_flow                    /* todo_flags_finish */
1495  }
1496 };