gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
   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)
 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       /* These values are mildly magic bits of the EH runtime.  We can't
 326          see the entire lifetime of these values until landing pads are
 327          generated.  */
 328       if (TREE_CODE (lhs) == EXC_PTR_EXPR
 329           || TREE_CODE (lhs) == FILTER_EXPR)
 330         {
 331           mark_stmt_necessary (stmt, true);
 332           return;
 333         }
 334       break;
 335
 336     case GIMPLE_GOTO:
 337       gcc_assert (!simple_goto_p (stmt));
 338       mark_stmt_necessary (stmt, true);
 339       return;
 340
 341     case GIMPLE_COND:
 342       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
 343       /* Fall through.  */
 344
 345     case GIMPLE_SWITCH:
 346       if (! aggressive)
 347         mark_stmt_necessary (stmt, true);
 348       break;
 349
 350     default:
 351       break;
 352     }
 353
 354   /* If the statement has volatile operands, it needs to be preserved.
 355      Same for statements that can alter control flow in unpredictable
 356      ways.  */
 357   if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
 358     {
 359       mark_stmt_necessary (stmt, true);
 360       return;
 361     }
 362
 363   if (is_hidden_global_store (stmt))
 364     {
 365       mark_stmt_necessary (stmt, true);
 366       return;
 367     }
 368
 369   return;
 370 }
 371
 372
 373 /* Make corresponding control dependent edges necessary.  We only
 374    have to do this once for each basic block, so we clear the bitmap
 375    after we're done.  */
 376 static void
 377 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 378 {
 379   bitmap_iterator bi;
 380   unsigned edge_number;
 381
 382   gcc_assert (bb != EXIT_BLOCK_PTR);
 383
 384   if (bb == ENTRY_BLOCK_PTR)
 385     return;
 386
 387   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 388     {
 389       gimple stmt;
 390       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 391
 392       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 393         continue;
 394       SET_BIT (last_stmt_necessary, cd_bb->index);
 395       SET_BIT (bb_contains_live_stmts, cd_bb->index);
 396
 397       stmt = last_stmt (cd_bb);
 398       if (stmt && is_ctrl_stmt (stmt))
 399         mark_stmt_necessary (stmt, true);
 400     }
 401 }
 402
 403
 404 /* Find obviously necessary statements.  These are things like most function
 405    calls, and stores to file level variables.
 406
 407    If EL is NULL, control statements are conservatively marked as
 408    necessary.  Otherwise it contains the list of edges used by control
 409    dependence analysis.  */
 410
 411 static void
 412 find_obviously_necessary_stmts (struct edge_list *el)
 413 {
 414   basic_block bb;
 415   gimple_stmt_iterator gsi;
 416   edge e;
 417   gimple phi, stmt;
 418
 419   FOR_EACH_BB (bb)
 420     {
 421       /* PHI nodes are never inherently necessary.  */
 422       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 423         {
 424           phi = gsi_stmt (gsi);
 425           gimple_set_plf (phi, STMT_NECESSARY, false);
 426         }
 427
 428       /* Check all statements in the block.  */
 429       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 430         {
 431           stmt = gsi_stmt (gsi);
 432           gimple_set_plf (stmt, STMT_NECESSARY, false);
 433           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 434         }
 435     }
 436
 437   /* Pure and const functions are finite and thus have no infinite loops in
 438      them.  */
 439   if ((TREE_READONLY (current_function_decl)
 440        || DECL_PURE_P (current_function_decl))
 441       && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
 442     return;
 443
 444   /* Prevent the empty possibly infinite loops from being removed.  */
 445   if (el)
 446     {
 447       loop_iterator li;
 448       struct loop *loop;
 449       scev_initialize ();
 450       if (mark_irreducible_loops ())
 451         FOR_EACH_BB (bb)
 452           {
 453             edge_iterator ei;
 454             FOR_EACH_EDGE (e, ei, bb->succs)
 455               if ((e->flags & EDGE_DFS_BACK)
 456                   && (e->flags & EDGE_IRREDUCIBLE_LOOP))
 457                 {
 458                   if (dump_file)
 459                     fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
 460                              e->src->index, e->dest->index);
 461                   mark_control_dependent_edges_necessary (e->dest, el);
 462                 }
 463           }
 464
 465       FOR_EACH_LOOP (li, loop, 0)
 466         if (!finite_loop_p (loop))
 467           {
 468             if (dump_file)
 469               fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
 470             mark_control_dependent_edges_necessary (loop->latch, el);
 471           }
 472       scev_finalize ();
 473     }
 474 }
 475
 476
 477 /* Return true if REF is based on an aliased base, otherwise false.  */
 478
 479 static bool
 480 ref_may_be_aliased (tree ref)
 481 {
 482   while (handled_component_p (ref))
 483     ref = TREE_OPERAND (ref, 0);
 484   return !(DECL_P (ref)
 485            && !may_be_aliased (ref));
 486 }
 487
 488 static bitmap visited = NULL;
 489 static unsigned int longest_chain = 0;
 490 static unsigned int total_chain = 0;
 491 static bool chain_ovfl = false;
 492
 493 /* Worker for the walker that marks reaching definitions of REF,
 494    which is based on a non-aliased decl, necessary.  It returns
 495    true whenever the defining statement of the current VDEF is
 496    a kill for REF, as no dominating may-defs are necessary for REF
 497    anymore.  DATA points to cached get_ref_base_and_extent data for REF.  */
 498
 499 static bool
 500 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
 501                                         void *data ATTRIBUTE_UNUSED)
 502 {
 503   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
 504
 505   /* All stmts we visit are necessary.  */
 506   mark_operand_necessary (vdef);
 507
 508   /* If the stmt lhs kills ref, then we can stop walking.  */
 509   if (gimple_has_lhs (def_stmt)
 510       && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
 511     {
 512       tree base, lhs = gimple_get_lhs (def_stmt);
 513       HOST_WIDE_INT size, offset, max_size;
 514       ao_ref_base (ref);
 515       base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
 516       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
 517          so base == refd->base does not always hold.  */
 518       if (base == ref->base)
 519         {
 520           /* For a must-alias check we need to be able to constrain
 521              the accesses properly.  */
 522           if (size != -1 && size == max_size
 523               && ref->max_size != -1)
 524             {
 525               if (offset <= ref->offset
 526                   && offset + size >= ref->offset + ref->max_size)
 527                 return true;
 528             }
 529           /* Or they need to be exactly the same.  */
 530           else if (ref->ref
 531                    && operand_equal_p (ref->ref, lhs, 0))
 532             return true;
 533         }
 534     }
 535
 536   /* Otherwise keep walking.  */
 537   return false;
 538 }
 539
 540 static void
 541 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
 542 {
 543   unsigned int chain;
 544   ao_ref refd;
 545   gcc_assert (!chain_ovfl);
 546   ao_ref_init (&refd, ref);
 547   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
 548                               mark_aliased_reaching_defs_necessary_1,
 549                               NULL, NULL);
 550   if (chain > longest_chain)
 551     longest_chain = chain;
 552   total_chain += chain;
 553 }
 554
 555 /* Worker for the walker that marks reaching definitions of REF, which
 556    is not based on a non-aliased decl.  For simplicity we need to end
 557    up marking all may-defs necessary that are not based on a non-aliased
 558    decl.  The only job of this walker is to skip may-defs based on
 559    a non-aliased decl.  */
 560
 561 static bool
 562 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
 563                                     tree vdef, void *data ATTRIBUTE_UNUSED)
 564 {
 565   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
 566
 567   /* We have to skip already visited (and thus necessary) statements
 568      to make the chaining work after we dropped back to simple mode.  */
 569   if (chain_ovfl
 570       && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
 571     {
 572       gcc_assert (gimple_nop_p (def_stmt)
 573                   || gimple_plf (def_stmt, STMT_NECESSARY));
 574       return false;
 575     }
 576
 577   /* We want to skip stores to non-aliased variables.  */
 578   if (!chain_ovfl
 579       && gimple_assign_single_p (def_stmt))
 580     {
 581       tree lhs = gimple_assign_lhs (def_stmt);
 582       if (!ref_may_be_aliased (lhs))
 583         return false;
 584     }
 585
 586   mark_operand_necessary (vdef);
 587
 588   return false;
 589 }
 590
 591 static void
 592 mark_all_reaching_defs_necessary (gimple stmt)
 593 {
 594   walk_aliased_vdefs (NULL, gimple_vuse (stmt),
 595                       mark_all_reaching_defs_necessary_1, NULL, &visited);
 596 }
 597
 598 /* Return true for PHI nodes with one or identical arguments
 599    can be removed.  */
 600 static bool
 601 degenerate_phi_p (gimple phi)
 602 {
 603   unsigned int i;
 604   tree op = gimple_phi_arg_def (phi, 0);
 605   for (i = 1; i < gimple_phi_num_args (phi); i++)
 606     if (gimple_phi_arg_def (phi, i) != op)
 607       return false;
 608   return true;
 609 }
 610
 611 /* Propagate necessity using the operands of necessary statements.
 612    Process the uses on each statement in the worklist, and add all
 613    feeding statements which contribute to the calculation of this
 614    value to the worklist.
 615
 616    In conservative mode, EL is NULL.  */
 617
 618 static void
 619 propagate_necessity (struct edge_list *el)
 620 {
 621   gimple stmt;
 622   bool aggressive = (el ? true : false);
 623
 624   if (dump_file && (dump_flags & TDF_DETAILS))
 625     fprintf (dump_file, "\nProcessing worklist:\n");
 626
 627   while (VEC_length (gimple, worklist) > 0)
 628     {
 629       /* Take STMT from worklist.  */
 630       stmt = VEC_pop (gimple, worklist);
 631
 632       if (dump_file && (dump_flags & TDF_DETAILS))
 633         {
 634           fprintf (dump_file, "processing: ");
 635           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 636           fprintf (dump_file, "\n");
 637         }
 638
 639       if (aggressive)
 640         {
 641           /* Mark the last statements of the basic blocks that the block
 642              containing STMT is control dependent on, but only if we haven't
 643              already done so.  */
 644           basic_block bb = gimple_bb (stmt);
 645           if (bb != ENTRY_BLOCK_PTR
 646               && ! TEST_BIT (visited_control_parents, bb->index))
 647             {
 648               SET_BIT (visited_control_parents, bb->index);
 649               mark_control_dependent_edges_necessary (bb, el);
 650             }
 651         }
 652
 653       if (gimple_code (stmt) == GIMPLE_PHI
 654           /* We do not process virtual PHI nodes nor do we track their
 655              necessity.  */
 656           && is_gimple_reg (gimple_phi_result (stmt)))
 657         {
 658           /* PHI nodes are somewhat special in that each PHI alternative has
 659              data and control dependencies.  All the statements feeding the
 660              PHI node's arguments are always necessary.  In aggressive mode,
 661              we also consider the control dependent edges leading to the
 662              predecessor block associated with each PHI alternative as
 663              necessary.  */
 664           size_t k;
 665
 666           for (k = 0; k < gimple_phi_num_args (stmt); k++)
 667             {
 668               tree arg = PHI_ARG_DEF (stmt, k);
 669               if (TREE_CODE (arg) == SSA_NAME)
 670                 mark_operand_necessary (arg);
 671             }
 672
 673           if (aggressive && !degenerate_phi_p (stmt))
 674             {
 675               for (k = 0; k < gimple_phi_num_args (stmt); k++)
 676                 {
 677                   basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
 678                   if (arg_bb != ENTRY_BLOCK_PTR
 679                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 680                     {
 681                       SET_BIT (visited_control_parents, arg_bb->index);
 682                       mark_control_dependent_edges_necessary (arg_bb, el);
 683                     }
 684                 }
 685             }
 686         }
 687       else
 688         {
 689           /* Propagate through the operands.  Examine all the USE, VUSE and
 690              VDEF operands in this statement.  Mark all the statements
 691              which feed this statement's uses as necessary.  */
 692           ssa_op_iter iter;
 693           tree use;
 694
 695           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 696             mark_operand_necessary (use);
 697
 698           use = gimple_vuse (stmt);
 699           if (!use)
 700             continue;
 701
 702           /* If we dropped to simple mode make all immediately
 703              reachable definitions necessary.  */
 704           if (chain_ovfl)
 705             {
 706               mark_all_reaching_defs_necessary (stmt);
 707               continue;
 708             }
 709
 710           /* For statements that may load from memory (have a VUSE) we
 711              have to mark all reaching (may-)definitions as necessary.
 712              We partition this task into two cases:
 713               1) explicit loads based on decls that are not aliased
 714               2) implicit loads (like calls) and explicit loads not
 715                  based on decls that are not aliased (like indirect
 716                  references or loads from globals)
 717              For 1) we mark all reaching may-defs as necessary, stopping
 718              at dominating kills.  For 2) we want to mark all dominating
 719              references necessary, but non-aliased ones which we handle
 720              in 1).  By keeping a global visited bitmap for references
 721              we walk for 2) we avoid quadratic behavior for those.  */
 722
 723           if (is_gimple_call (stmt))
 724             {
 725               tree callee = gimple_call_fndecl (stmt);
 726               unsigned i;
 727
 728               /* Calls to functions that are merely acting as barriers
 729                  or that only store to memory do not make any previous
 730                  stores necessary.  */
 731               if (callee != NULL_TREE
 732                   && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
 733                   && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
 734                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
 735                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
 736                 continue;
 737
 738               /* Calls implicitly load from memory, their arguments
 739                  in addition may explicitly perform memory loads.  */
 740               mark_all_reaching_defs_necessary (stmt);
 741               for (i = 0; i < gimple_call_num_args (stmt); ++i)
 742                 {
 743                   tree arg = gimple_call_arg (stmt, i);
 744                   if (TREE_CODE (arg) == SSA_NAME
 745                       || is_gimple_min_invariant (arg))
 746                     continue;
 747                   if (!ref_may_be_aliased (arg))
 748                     mark_aliased_reaching_defs_necessary (stmt, arg);
 749                 }
 750             }
 751           else if (gimple_assign_single_p (stmt))
 752             {
 753               tree rhs;
 754               bool rhs_aliased = false;
 755               /* If this is a load mark things necessary.  */
 756               rhs = gimple_assign_rhs1 (stmt);
 757               if (TREE_CODE (rhs) != SSA_NAME
 758                   && !is_gimple_min_invariant (rhs))
 759                 {
 760                   if (!ref_may_be_aliased (rhs))
 761                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 762                   else
 763                     rhs_aliased = true;
 764                 }
 765               if (rhs_aliased)
 766                 mark_all_reaching_defs_necessary (stmt);
 767             }
 768           else if (gimple_code (stmt) == GIMPLE_RETURN)
 769             {
 770               tree rhs = gimple_return_retval (stmt);
 771               /* A return statement may perform a load.  */
 772               if (TREE_CODE (rhs) != SSA_NAME
 773                   && !is_gimple_min_invariant (rhs))
 774                 {
 775                   if (!ref_may_be_aliased (rhs))
 776                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 777                   else
 778                     mark_all_reaching_defs_necessary (stmt);
 779                 }
 780             }
 781           else if (gimple_code (stmt) == GIMPLE_ASM)
 782             {
 783               unsigned i;
 784               mark_all_reaching_defs_necessary (stmt);
 785               /* Inputs may perform loads.  */
 786               for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
 787                 {
 788                   tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
 789                   if (TREE_CODE (op) != SSA_NAME
 790                       && !is_gimple_min_invariant (op)
 791                       && !ref_may_be_aliased (op))
 792                     mark_aliased_reaching_defs_necessary (stmt, op);
 793                 }
 794             }
 795           else
 796             gcc_unreachable ();
 797
 798           /* If we over-used our alias oracle budget drop to simple
 799              mode.  The cost metric allows quadratic behavior up to
 800              a constant maximal chain and after that falls back to
 801              super-linear complexity.  */
 802           if (longest_chain > 256
 803               && total_chain > 256 * longest_chain)
 804             {
 805               chain_ovfl = true;
 806               if (visited)
 807                 bitmap_clear (visited);
 808             }
 809         }
 810     }
 811 }
 812
 813 /* Replace all uses of result of PHI by underlying variable and mark it
 814    for renaming.  */
 815
 816 static void
 817 mark_virtual_phi_result_for_renaming (gimple phi)
 818 {
 819   bool used = false;
 820   imm_use_iterator iter;
 821   use_operand_p use_p;
 822   gimple stmt;
 823   if (dump_file && (dump_flags & TDF_DETAILS))
 824     {
 825       fprintf (dump_file, "Marking result for renaming : ");
 826       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 827       fprintf (dump_file, "\n");
 828     }
 829   FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (phi))
 830     {
 831       if (gimple_code (stmt) != GIMPLE_PHI
 832           && !gimple_plf (stmt, STMT_NECESSARY))
 833         continue;
 834       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 835         SET_USE (use_p, SSA_NAME_VAR (gimple_phi_result (phi)));
 836       update_stmt (stmt);
 837       used = true;
 838     }
 839   if (used)
 840     mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi)));
 841 }
 842
 843 /* Remove dead PHI nodes from block BB.  */
 844
 845 static bool
 846 remove_dead_phis (basic_block bb)
 847 {
 848   bool something_changed = false;
 849   gimple_seq phis;
 850   gimple phi;
 851   gimple_stmt_iterator gsi;
 852   phis = phi_nodes (bb);
 853
 854   for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
 855     {
 856       stats.total_phis++;
 857       phi = gsi_stmt (gsi);
 858
 859       /* We do not track necessity of virtual PHI nodes.  Instead do
 860          very simple dead PHI removal here.  */
 861       if (!is_gimple_reg (gimple_phi_result (phi)))
 862         {
 863           /* Virtual PHI nodes with one or identical arguments
 864              can be removed.  */
 865           if (degenerate_phi_p (phi))
 866             {
 867               tree vdef = gimple_phi_result (phi);
 868               tree vuse = gimple_phi_arg_def (phi, 0);
 869
 870               use_operand_p use_p;
 871               imm_use_iterator iter;
 872               gimple use_stmt;
 873               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
 874                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 875                   SET_USE (use_p, vuse);
 876               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
 877                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
 878             }
 879           else
 880             gimple_set_plf (phi, STMT_NECESSARY, true);
 881         }
 882
 883       if (!gimple_plf (phi, STMT_NECESSARY))
 884         {
 885           something_changed = true;
 886           if (dump_file && (dump_flags & TDF_DETAILS))
 887             {
 888               fprintf (dump_file, "Deleting : ");
 889               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 890               fprintf (dump_file, "\n");
 891             }
 892
 893           remove_phi_node (&gsi, true);
 894           stats.removed_phis++;
 895           continue;
 896         }
 897
 898       gsi_next (&gsi);
 899     }
 900   return something_changed;
 901 }
 902
 903 /* Find first live post dominator of BB.  */
 904
 905 static basic_block
 906 get_live_post_dom (basic_block bb)
 907 {
 908   basic_block post_dom_bb;
 909
 910
 911   /* The post dominance info has to be up-to-date.  */
 912   gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
 913
 914   /* Get the immediate post dominator of bb.  */
 915   post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 916   /* And look for first live one.  */
 917   while (post_dom_bb != EXIT_BLOCK_PTR
 918          && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
 919     post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
 920
 921   return post_dom_bb;
 922 }
 923
 924 /* Forward edge E to respective POST_DOM_BB and update PHIs.  */
 925
 926 static edge
 927 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
 928 {
 929   gimple_stmt_iterator gsi;
 930   edge e2 = NULL;
 931   edge_iterator ei;
 932
 933   if (dump_file && (dump_flags & TDF_DETAILS))
 934     fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
 935              e->dest->index, post_dom_bb->index);
 936
 937   e2 = redirect_edge_and_branch (e, post_dom_bb);
 938   cfg_altered = true;
 939
 940   /* If edge was already around, no updating is neccesary.  */
 941   if (e2 != e)
 942     return e2;
 943
 944   if (phi_nodes (post_dom_bb))
 945     {
 946       /* We are sure that for every live PHI we are seeing control dependent BB.
 947          This means that we can look up the end of control dependent path leading
 948          to the PHI itself.  */
 949       FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
 950         if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
 951           break;
 952       for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
 953         {
 954           gimple phi = gsi_stmt (gsi);
 955           tree op;
 956
 957           /* Dead PHI do not imply control dependency.  */
 958           if (!gimple_plf (phi, STMT_NECESSARY)
 959               && is_gimple_reg (gimple_phi_result (phi)))
 960             {
 961               gsi_next (&gsi);
 962               continue;
 963             }
 964           if (gimple_phi_arg_def (phi, e->dest_idx))
 965             {
 966               gsi_next (&gsi);
 967               continue;
 968             }
 969
 970           /* We didn't find edge to update.  This can happen for PHIs on virtuals
 971              since there is no control dependency relation on them.  We are lost
 972              here and must force renaming of the symbol.  */
 973           if (!is_gimple_reg (gimple_phi_result (phi)))
 974             {
 975               mark_virtual_phi_result_for_renaming (phi);
 976               remove_phi_node (&gsi, true);
 977               continue;
 978             }
 979           if (!e2)
 980             op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
 981           else
 982             op = gimple_phi_arg_def (phi, e2->dest_idx);
 983           add_phi_arg (phi, op, e);
 984           gcc_assert (e2 || degenerate_phi_p (phi));
 985           gsi_next (&gsi);
 986         }
 987     }
 988   return e;
 989 }
 990
 991 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 992    containing I so that we don't have to look it up.  */
 993
 994 static void
 995 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
 996 {
 997   gimple stmt = gsi_stmt (*i);
 998
 999   if (dump_file && (dump_flags & TDF_DETAILS))
1000     {
1001       fprintf (dump_file, "Deleting : ");
1002       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1003       fprintf (dump_file, "\n");
1004     }
1005
1006   stats.removed++;
1007
1008   /* If we have determined that a conditional branch statement contributes
1009      nothing to the program, then we not only remove it, but we also change
1010      the flow graph so that the current block will simply fall-thru to its
1011      immediate post-dominator.  The blocks we are circumventing will be
1012      removed by cleanup_tree_cfg if this change in the flow graph makes them
1013      unreachable.  */
1014   if (is_ctrl_stmt (stmt))
1015     {
1016       basic_block post_dom_bb;
1017       edge e, e2;
1018       edge_iterator ei;
1019
1020       post_dom_bb = get_live_post_dom (bb);
1021
1022       e = find_edge (bb, post_dom_bb);
1023
1024       /* If edge is already there, try to use it.  This avoids need to update
1025          PHI nodes.  Also watch for cases where post dominator does not exists
1026          or is exit block.  These can happen for infinite loops as we create
1027          fake edges in the dominator tree.  */
1028       if (e)
1029         ;
1030       else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
1031         e = EDGE_SUCC (bb, 0);
1032       else
1033         e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1034       gcc_assert (e);
1035       e->probability = REG_BR_PROB_BASE;
1036       e->count = bb->count;
1037
1038       /* The edge is no longer associated with a conditional, so it does
1039          not have TRUE/FALSE flags.  */
1040       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1041
1042       /* The lone outgoing edge from BB will be a fallthru edge.  */
1043       e->flags |= EDGE_FALLTHRU;
1044
1045       /* Remove the remaining outgoing edges.  */
1046       for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1047         if (e != e2)
1048           {
1049             cfg_altered = true;
1050             remove_edge (e2);
1051           }
1052         else
1053           ei_next (&ei);
1054     }
1055
1056   unlink_stmt_vdef (stmt);
1057   gsi_remove (i, true);
1058   release_defs (stmt);
1059 }
1060
1061
1062 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1063    contributes nothing to the program, and can be deleted.  */
1064
1065 static bool
1066 eliminate_unnecessary_stmts (void)
1067 {
1068   bool something_changed = false;
1069   basic_block bb;
1070   gimple_stmt_iterator gsi;
1071   gimple stmt;
1072   tree call;
1073
1074   if (dump_file && (dump_flags & TDF_DETAILS))
1075     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1076
1077   clear_special_calls ();
1078
1079   FOR_EACH_BB (bb)
1080     {
1081       /* Remove dead statements.  */
1082       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1083         {
1084           stmt = gsi_stmt (gsi);
1085
1086           stats.total++;
1087
1088           /* If GSI is not necessary then remove it.  */
1089           if (!gimple_plf (stmt, STMT_NECESSARY))
1090             {
1091               remove_dead_stmt (&gsi, bb);
1092               something_changed = true;
1093             }
1094           else if (is_gimple_call (stmt))
1095             {
1096               call = gimple_call_fndecl (stmt);
1097               if (call)
1098                 {
1099                   tree name;
1100
1101                   /* When LHS of var = call (); is dead, simplify it into
1102                      call (); saving one operand.  */
1103                   name = gimple_call_lhs (stmt);
1104                   if (name && TREE_CODE (name) == SSA_NAME
1105                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1106                     {
1107                       something_changed = true;
1108                       if (dump_file && (dump_flags & TDF_DETAILS))
1109                         {
1110                           fprintf (dump_file, "Deleting LHS of call: ");
1111                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1112                           fprintf (dump_file, "\n");
1113                         }
1114
1115                       gimple_call_set_lhs (stmt, NULL_TREE);
1116                       maybe_clean_or_replace_eh_stmt (stmt, stmt);
1117                       update_stmt (stmt);
1118                       release_ssa_name (name);
1119                     }
1120                   notice_special_calls (stmt);
1121                 }
1122               gsi_next (&gsi);
1123             }
1124           else
1125             {
1126               gsi_next (&gsi);
1127             }
1128         }
1129     }
1130   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1131      rendered some PHI nodes unreachable while they are still in use.
1132      Mark them for renaming.  */
1133   if (cfg_altered)
1134     {
1135       basic_block next_bb;
1136       find_unreachable_blocks ();
1137       for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
1138         {
1139           next_bb = bb->next_bb;
1140           if (!(bb->flags & BB_REACHABLE))
1141             {
1142               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1143                 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1144                   {
1145                     bool found = false;
1146                     imm_use_iterator iter;
1147
1148                     FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1149                       {
1150                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1151                           continue;
1152                         if (gimple_code (stmt) == GIMPLE_PHI
1153                             || gimple_plf (stmt, STMT_NECESSARY))
1154                           {
1155                             found = true;
1156                             BREAK_FROM_IMM_USE_STMT (iter);
1157                           }
1158                       }
1159                     if (found)
1160                       mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1161                   }
1162               delete_basic_block (bb);
1163             }
1164         }
1165     }
1166   FOR_EACH_BB (bb)
1167     {
1168       /* Remove dead PHI nodes.  */
1169       something_changed |= remove_dead_phis (bb);
1170     }
1171
1172   return something_changed;
1173 }
1174
1175
1176 /* Print out removed statement statistics.  */
1177
1178 static void
1179 print_stats (void)
1180 {
1181   float percg;
1182
1183   percg = ((float) stats.removed / (float) stats.total) * 100;
1184   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1185            stats.removed, stats.total, (int) percg);
1186
1187   if (stats.total_phis == 0)
1188     percg = 0;
1189   else
1190     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1191
1192   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1193            stats.removed_phis, stats.total_phis, (int) percg);
1194 }
1195
1196 /* Initialization for this pass.  Set up the used data structures.  */
1197
1198 static void
1199 tree_dce_init (bool aggressive)
1200 {
1201   memset ((void *) &stats, 0, sizeof (stats));
1202
1203   if (aggressive)
1204     {
1205       int i;
1206
1207       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1208       for (i = 0; i < last_basic_block; ++i)
1209         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1210
1211       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1212       sbitmap_zero (last_stmt_necessary);
1213       bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1214       sbitmap_zero (bb_contains_live_stmts);
1215     }
1216
1217   processed = sbitmap_alloc (num_ssa_names + 1);
1218   sbitmap_zero (processed);
1219
1220   worklist = VEC_alloc (gimple, heap, 64);
1221   cfg_altered = false;
1222 }
1223
1224 /* Cleanup after this pass.  */
1225
1226 static void
1227 tree_dce_done (bool aggressive)
1228 {
1229   if (aggressive)
1230     {
1231       int i;
1232
1233       for (i = 0; i < last_basic_block; ++i)
1234         BITMAP_FREE (control_dependence_map[i]);
1235       free (control_dependence_map);
1236
1237       sbitmap_free (visited_control_parents);
1238       sbitmap_free (last_stmt_necessary);
1239       sbitmap_free (bb_contains_live_stmts);
1240       bb_contains_live_stmts = NULL;
1241     }
1242
1243   sbitmap_free (processed);
1244
1245   VEC_free (gimple, heap, worklist);
1246 }
1247
1248 /* Main routine to eliminate dead code.
1249
1250    AGGRESSIVE controls the aggressiveness of the algorithm.
1251    In conservative mode, we ignore control dependence and simply declare
1252    all but the most trivially dead branches necessary.  This mode is fast.
1253    In aggressive mode, control dependences are taken into account, which
1254    results in more dead code elimination, but at the cost of some time.
1255
1256    FIXME: Aggressive mode before PRE doesn't work currently because
1257           the dominance info is not invalidated after DCE1.  This is
1258           not an issue right now because we only run aggressive DCE
1259           as the last tree SSA pass, but keep this in mind when you
1260           start experimenting with pass ordering.  */
1261
1262 static unsigned int
1263 perform_tree_ssa_dce (bool aggressive)
1264 {
1265   struct edge_list *el = NULL;
1266   bool something_changed = 0;
1267
1268   /* Preheaders are needed for SCEV to work.
1269      Simple lateches and recorded exits improve chances that loop will
1270      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
1271   if (aggressive)
1272     loop_optimizer_init (LOOPS_NORMAL
1273                          | LOOPS_HAVE_RECORDED_EXITS);
1274
1275   tree_dce_init (aggressive);
1276
1277   if (aggressive)
1278     {
1279       /* Compute control dependence.  */
1280       timevar_push (TV_CONTROL_DEPENDENCES);
1281       calculate_dominance_info (CDI_POST_DOMINATORS);
1282       el = create_edge_list ();
1283       find_all_control_dependences (el);
1284       timevar_pop (TV_CONTROL_DEPENDENCES);
1285
1286       visited_control_parents = sbitmap_alloc (last_basic_block);
1287       sbitmap_zero (visited_control_parents);
1288
1289       mark_dfs_back_edges ();
1290     }
1291
1292   find_obviously_necessary_stmts (el);
1293
1294   if (aggressive)
1295     loop_optimizer_finalize ();
1296
1297   longest_chain = 0;
1298   total_chain = 0;
1299   chain_ovfl = false;
1300   propagate_necessity (el);
1301   BITMAP_FREE (visited);
1302
1303   something_changed |= eliminate_unnecessary_stmts ();
1304   something_changed |= cfg_altered;
1305
1306   /* We do not update postdominators, so free them unconditionally.  */
1307   free_dominance_info (CDI_POST_DOMINATORS);
1308
1309   /* If we removed paths in the CFG, then we need to update
1310      dominators as well.  I haven't investigated the possibility
1311      of incrementally updating dominators.  */
1312   if (cfg_altered)
1313     free_dominance_info (CDI_DOMINATORS);
1314
1315   statistics_counter_event (cfun, "Statements deleted", stats.removed);
1316   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1317
1318   /* Debugging dumps.  */
1319   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1320     print_stats ();
1321
1322   tree_dce_done (aggressive);
1323
1324   free_edge_list (el);
1325
1326   if (something_changed)
1327     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1328             | TODO_remove_unused_locals);
1329   else
1330     return 0;
1331 }
1332
1333 /* Pass entry points.  */
1334 static unsigned int
1335 tree_ssa_dce (void)
1336 {
1337   return perform_tree_ssa_dce (/*aggressive=*/false);
1338 }
1339
1340 static unsigned int
1341 tree_ssa_dce_loop (void)
1342 {
1343   unsigned int todo;
1344   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1345   if (todo)
1346     {
1347       free_numbers_of_iterations_estimates ();
1348       scev_reset ();
1349     }
1350   return todo;
1351 }
1352
1353 static unsigned int
1354 tree_ssa_cd_dce (void)
1355 {
1356   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1357 }
1358
1359 static bool
1360 gate_dce (void)
1361 {
1362   return flag_tree_dce != 0;
1363 }
1364
1365 struct gimple_opt_pass pass_dce =
1366 {
1367  {
1368   GIMPLE_PASS,
1369   "dce",                                /* name */
1370   gate_dce,                             /* gate */
1371   tree_ssa_dce,                         /* execute */
1372   NULL,                                 /* sub */
1373   NULL,                                 /* next */
1374   0,                                    /* static_pass_number */
1375   TV_TREE_DCE,                          /* tv_id */
1376   PROP_cfg | PROP_ssa,                  /* properties_required */
1377   0,                                    /* properties_provided */
1378   0,                                    /* properties_destroyed */
1379   0,                                    /* todo_flags_start */
1380   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1381  }
1382 };
1383
1384 struct gimple_opt_pass pass_dce_loop =
1385 {
1386  {
1387   GIMPLE_PASS,
1388   "dceloop",                            /* name */
1389   gate_dce,                             /* gate */
1390   tree_ssa_dce_loop,                    /* execute */
1391   NULL,                                 /* sub */
1392   NULL,                                 /* next */
1393   0,                                    /* static_pass_number */
1394   TV_TREE_DCE,                          /* tv_id */
1395   PROP_cfg | PROP_ssa,                  /* properties_required */
1396   0,                                    /* properties_provided */
1397   0,                                    /* properties_destroyed */
1398   0,                                    /* todo_flags_start */
1399   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1400  }
1401 };
1402
1403 struct gimple_opt_pass pass_cd_dce =
1404 {
1405  {
1406   GIMPLE_PASS,
1407   "cddce",                              /* name */
1408   gate_dce,                             /* gate */
1409   tree_ssa_cd_dce,                      /* execute */
1410   NULL,                                 /* sub */
1411   NULL,                                 /* next */
1412   0,                                    /* static_pass_number */
1413   TV_TREE_CD_DCE,                       /* tv_id */
1414   PROP_cfg | PROP_ssa,                  /* properties_required */
1415   0,                                    /* properties_provided */
1416   0,                                    /* properties_destroyed */
1417   0,                                    /* todo_flags_start */
1418   TODO_dump_func | TODO_verify_ssa
1419   | TODO_verify_flow                    /* todo_flags_finish */
1420  }
1421 };