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       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 832         SET_USE (use_p, SSA_NAME_VAR (gimple_phi_result (phi)));
 833       update_stmt (stmt);
 834       used = true;
 835     }
 836   if (used)
 837     mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi)));
 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
1067 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1068    contributes nothing to the program, and can be deleted.  */
1069
1070 static bool
1071 eliminate_unnecessary_stmts (void)
1072 {
1073   bool something_changed = false;
1074   basic_block bb;
1075   gimple_stmt_iterator gsi;
1076   gimple stmt;
1077   tree call;
1078
1079   if (dump_file && (dump_flags & TDF_DETAILS))
1080     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1081
1082   clear_special_calls ();
1083
1084   FOR_EACH_BB (bb)
1085     {
1086       /* Remove dead statements.  */
1087       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1088         {
1089           stmt = gsi_stmt (gsi);
1090
1091           stats.total++;
1092
1093           /* If GSI is not necessary then remove it.  */
1094           if (!gimple_plf (stmt, STMT_NECESSARY))
1095             {
1096               remove_dead_stmt (&gsi, bb);
1097               something_changed = true;
1098             }
1099           else if (is_gimple_call (stmt))
1100             {
1101               call = gimple_call_fndecl (stmt);
1102               if (call)
1103                 {
1104                   tree name;
1105
1106                   /* When LHS of var = call (); is dead, simplify it into
1107                      call (); saving one operand.  */
1108                   name = gimple_call_lhs (stmt);
1109                   if (name && TREE_CODE (name) == SSA_NAME
1110                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1111                     {
1112                       something_changed = true;
1113                       if (dump_file && (dump_flags & TDF_DETAILS))
1114                         {
1115                           fprintf (dump_file, "Deleting LHS of call: ");
1116                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1117                           fprintf (dump_file, "\n");
1118                         }
1119
1120                       gimple_call_set_lhs (stmt, NULL_TREE);
1121                       maybe_clean_or_replace_eh_stmt (stmt, stmt);
1122                       update_stmt (stmt);
1123                       release_ssa_name (name);
1124                     }
1125                   notice_special_calls (stmt);
1126                 }
1127               gsi_next (&gsi);
1128             }
1129           else
1130             {
1131               gsi_next (&gsi);
1132             }
1133         }
1134     }
1135   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1136      rendered some PHI nodes unreachable while they are still in use.
1137      Mark them for renaming.  */
1138   if (cfg_altered)
1139     {
1140       basic_block next_bb;
1141       find_unreachable_blocks ();
1142       for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
1143         {
1144           next_bb = bb->next_bb;
1145           if (!TEST_BIT (bb_contains_live_stmts, bb->index)
1146               || !(bb->flags & BB_REACHABLE))
1147             {
1148               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1149                 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1150                   {
1151                     bool found = false;
1152                     imm_use_iterator iter;
1153
1154                     FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1155                       {
1156                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1157                           continue;
1158                         if (gimple_code (stmt) == GIMPLE_PHI
1159                             || gimple_plf (stmt, STMT_NECESSARY))
1160                           {
1161                             found = true;
1162                             BREAK_FROM_IMM_USE_STMT (iter);
1163                           }
1164                       }
1165                     if (found)
1166                       mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1167                   }
1168               if (!(bb->flags & BB_REACHABLE))
1169                 delete_basic_block (bb);
1170             }
1171         }
1172     }
1173   FOR_EACH_BB (bb)
1174     {
1175       /* Remove dead PHI nodes.  */
1176       something_changed |= remove_dead_phis (bb);
1177     }
1178
1179   return something_changed;
1180 }
1181
1182
1183 /* Print out removed statement statistics.  */
1184
1185 static void
1186 print_stats (void)
1187 {
1188   float percg;
1189
1190   percg = ((float) stats.removed / (float) stats.total) * 100;
1191   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1192            stats.removed, stats.total, (int) percg);
1193
1194   if (stats.total_phis == 0)
1195     percg = 0;
1196   else
1197     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1198
1199   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1200            stats.removed_phis, stats.total_phis, (int) percg);
1201 }
1202
1203 /* Initialization for this pass.  Set up the used data structures.  */
1204
1205 static void
1206 tree_dce_init (bool aggressive)
1207 {
1208   memset ((void *) &stats, 0, sizeof (stats));
1209
1210   if (aggressive)
1211     {
1212       int i;
1213
1214       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1215       for (i = 0; i < last_basic_block; ++i)
1216         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1217
1218       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1219       sbitmap_zero (last_stmt_necessary);
1220       bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1221       sbitmap_zero (bb_contains_live_stmts);
1222     }
1223
1224   processed = sbitmap_alloc (num_ssa_names + 1);
1225   sbitmap_zero (processed);
1226
1227   worklist = VEC_alloc (gimple, heap, 64);
1228   cfg_altered = false;
1229 }
1230
1231 /* Cleanup after this pass.  */
1232
1233 static void
1234 tree_dce_done (bool aggressive)
1235 {
1236   if (aggressive)
1237     {
1238       int i;
1239
1240       for (i = 0; i < last_basic_block; ++i)
1241         BITMAP_FREE (control_dependence_map[i]);
1242       free (control_dependence_map);
1243
1244       sbitmap_free (visited_control_parents);
1245       sbitmap_free (last_stmt_necessary);
1246       sbitmap_free (bb_contains_live_stmts);
1247       bb_contains_live_stmts = NULL;
1248     }
1249
1250   sbitmap_free (processed);
1251
1252   VEC_free (gimple, heap, worklist);
1253 }
1254
1255 /* Main routine to eliminate dead code.
1256
1257    AGGRESSIVE controls the aggressiveness of the algorithm.
1258    In conservative mode, we ignore control dependence and simply declare
1259    all but the most trivially dead branches necessary.  This mode is fast.
1260    In aggressive mode, control dependences are taken into account, which
1261    results in more dead code elimination, but at the cost of some time.
1262
1263    FIXME: Aggressive mode before PRE doesn't work currently because
1264           the dominance info is not invalidated after DCE1.  This is
1265           not an issue right now because we only run aggressive DCE
1266           as the last tree SSA pass, but keep this in mind when you
1267           start experimenting with pass ordering.  */
1268
1269 static unsigned int
1270 perform_tree_ssa_dce (bool aggressive)
1271 {
1272   struct edge_list *el = NULL;
1273   bool something_changed = 0;
1274
1275   /* Preheaders are needed for SCEV to work.
1276      Simple lateches and recorded exits improve chances that loop will
1277      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
1278   if (aggressive)
1279     loop_optimizer_init (LOOPS_NORMAL
1280                          | LOOPS_HAVE_RECORDED_EXITS);
1281
1282   tree_dce_init (aggressive);
1283
1284   if (aggressive)
1285     {
1286       /* Compute control dependence.  */
1287       timevar_push (TV_CONTROL_DEPENDENCES);
1288       calculate_dominance_info (CDI_POST_DOMINATORS);
1289       el = create_edge_list ();
1290       find_all_control_dependences (el);
1291       timevar_pop (TV_CONTROL_DEPENDENCES);
1292
1293       visited_control_parents = sbitmap_alloc (last_basic_block);
1294       sbitmap_zero (visited_control_parents);
1295
1296       mark_dfs_back_edges ();
1297     }
1298
1299   find_obviously_necessary_stmts (el);
1300
1301   if (aggressive)
1302     loop_optimizer_finalize ();
1303
1304   longest_chain = 0;
1305   total_chain = 0;
1306   chain_ovfl = false;
1307   propagate_necessity (el);
1308   BITMAP_FREE (visited);
1309
1310   something_changed |= eliminate_unnecessary_stmts ();
1311   something_changed |= cfg_altered;
1312
1313   /* We do not update postdominators, so free them unconditionally.  */
1314   free_dominance_info (CDI_POST_DOMINATORS);
1315
1316   /* If we removed paths in the CFG, then we need to update
1317      dominators as well.  I haven't investigated the possibility
1318      of incrementally updating dominators.  */
1319   if (cfg_altered)
1320     free_dominance_info (CDI_DOMINATORS);
1321
1322   statistics_counter_event (cfun, "Statements deleted", stats.removed);
1323   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1324
1325   /* Debugging dumps.  */
1326   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1327     print_stats ();
1328
1329   tree_dce_done (aggressive);
1330
1331   free_edge_list (el);
1332
1333   if (something_changed)
1334     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1335             | TODO_remove_unused_locals);
1336   else
1337     return 0;
1338 }
1339
1340 /* Pass entry points.  */
1341 static unsigned int
1342 tree_ssa_dce (void)
1343 {
1344   return perform_tree_ssa_dce (/*aggressive=*/false);
1345 }
1346
1347 static unsigned int
1348 tree_ssa_dce_loop (void)
1349 {
1350   unsigned int todo;
1351   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1352   if (todo)
1353     {
1354       free_numbers_of_iterations_estimates ();
1355       scev_reset ();
1356     }
1357   return todo;
1358 }
1359
1360 static unsigned int
1361 tree_ssa_cd_dce (void)
1362 {
1363   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1364 }
1365
1366 static bool
1367 gate_dce (void)
1368 {
1369   return flag_tree_dce != 0;
1370 }
1371
1372 struct gimple_opt_pass pass_dce =
1373 {
1374  {
1375   GIMPLE_PASS,
1376   "dce",                                /* name */
1377   gate_dce,                             /* gate */
1378   tree_ssa_dce,                         /* execute */
1379   NULL,                                 /* sub */
1380   NULL,                                 /* next */
1381   0,                                    /* static_pass_number */
1382   TV_TREE_DCE,                          /* tv_id */
1383   PROP_cfg | PROP_ssa,                  /* properties_required */
1384   0,                                    /* properties_provided */
1385   0,                                    /* properties_destroyed */
1386   0,                                    /* todo_flags_start */
1387   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1388  }
1389 };
1390
1391 struct gimple_opt_pass pass_dce_loop =
1392 {
1393  {
1394   GIMPLE_PASS,
1395   "dceloop",                            /* name */
1396   gate_dce,                             /* gate */
1397   tree_ssa_dce_loop,                    /* execute */
1398   NULL,                                 /* sub */
1399   NULL,                                 /* next */
1400   0,                                    /* static_pass_number */
1401   TV_TREE_DCE,                          /* tv_id */
1402   PROP_cfg | PROP_ssa,                  /* properties_required */
1403   0,                                    /* properties_provided */
1404   0,                                    /* properties_destroyed */
1405   0,                                    /* todo_flags_start */
1406   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1407  }
1408 };
1409
1410 struct gimple_opt_pass pass_cd_dce =
1411 {
1412  {
1413   GIMPLE_PASS,
1414   "cddce",                              /* name */
1415   gate_dce,                             /* gate */
1416   tree_ssa_cd_dce,                      /* execute */
1417   NULL,                                 /* sub */
1418   NULL,                                 /* next */
1419   0,                                    /* static_pass_number */
1420   TV_TREE_CD_DCE,                       /* tv_id */
1421   PROP_cfg | PROP_ssa,                  /* properties_required */
1422   0,                                    /* properties_provided */
1423   0,                                    /* properties_destroyed */
1424   0,                                    /* todo_flags_start */
1425   TODO_dump_func | TODO_verify_ssa
1426   | TODO_verify_flow                    /* todo_flags_finish */
1427  }
1428 };