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