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