gcc/tree-ssa-dce.c

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