gcc/tree-ssa-dce.c

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