gcc/tree-ssa-dce.c

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