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               tree callee = gimple_call_fndecl (stmt);
 680               unsigned i;
 681
 682               /* Calls to functions that are merely acting as barriers
 683                  or that only store to memory do not make any previous
 684                  stores necessary.  */
 685               if (callee != NULL_TREE
 686                   && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
 687                   && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
 688                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
 689                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
 690                 continue;
 691
 692               /* Calls implicitly load from memory, their arguments
 693                  in addition may explicitly perform memory loads.  */
 694               mark_all_reaching_defs_necessary (stmt);
 695               for (i = 0; i < gimple_call_num_args (stmt); ++i)
 696                 {
 697                   tree arg = gimple_call_arg (stmt, i);
 698                   if (TREE_CODE (arg) == SSA_NAME
 699                       || is_gimple_min_invariant (arg))
 700                     continue;
 701                   if (!ref_may_be_aliased (arg))
 702                     mark_aliased_reaching_defs_necessary (stmt, arg);
 703                 }
 704             }
 705           else if (gimple_assign_single_p (stmt))
 706             {
 707               tree rhs;
 708               bool rhs_aliased = false;
 709               /* If this is a load mark things necessary.  */
 710               rhs = gimple_assign_rhs1 (stmt);
 711               if (TREE_CODE (rhs) != SSA_NAME
 712                   && !is_gimple_min_invariant (rhs))
 713                 {
 714                   if (!ref_may_be_aliased (rhs))
 715                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 716                   else
 717                     rhs_aliased = true;
 718                 }
 719               if (rhs_aliased)
 720                 mark_all_reaching_defs_necessary (stmt);
 721             }
 722           else if (gimple_code (stmt) == GIMPLE_RETURN)
 723             {
 724               tree rhs = gimple_return_retval (stmt);
 725               /* A return statement may perform a load.  */
 726               if (TREE_CODE (rhs) != SSA_NAME
 727                   && !is_gimple_min_invariant (rhs))
 728                 {
 729                   if (!ref_may_be_aliased (rhs))
 730                     mark_aliased_reaching_defs_necessary (stmt, rhs);
 731                   else
 732                     mark_all_reaching_defs_necessary (stmt);
 733                 }
 734             }
 735           else if (gimple_code (stmt) == GIMPLE_ASM)
 736             {
 737               unsigned i;
 738               mark_all_reaching_defs_necessary (stmt);
 739               /* Inputs may perform loads.  */
 740               for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
 741                 {
 742                   tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
 743                   if (TREE_CODE (op) != SSA_NAME
 744                       && !is_gimple_min_invariant (op)
 745                       && !ref_may_be_aliased (op))
 746                     mark_aliased_reaching_defs_necessary (stmt, op);
 747                 }
 748             }
 749           else
 750             gcc_unreachable ();
 751
 752           /* If we over-used our alias oracle budget drop to simple
 753              mode.  The cost metric allows quadratic behavior up to
 754              a constant maximal chain and after that falls back to
 755              super-linear complexity.  */
 756           if (longest_chain > 256
 757               && total_chain > 256 * longest_chain)
 758             {
 759               chain_ovfl = true;
 760               if (visited)
 761                 bitmap_clear (visited);
 762             }
 763         }
 764     }
 765 }
 766
 767
 768 /* Remove dead PHI nodes from block BB.  */
 769
 770 static bool
 771 remove_dead_phis (basic_block bb)
 772 {
 773   bool something_changed = false;
 774   gimple_seq phis;
 775   gimple phi;
 776   gimple_stmt_iterator gsi;
 777   phis = phi_nodes (bb);
 778
 779   for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
 780     {
 781       stats.total_phis++;
 782       phi = gsi_stmt (gsi);
 783
 784       /* We do not track necessity of virtual PHI nodes.  Instead do
 785          very simple dead PHI removal here.  */
 786       if (!is_gimple_reg (gimple_phi_result (phi)))
 787         {
 788           unsigned i;
 789           tree vuse;
 790
 791           /* Virtual PHI nodes with one or identical arguments
 792              can be removed.  */
 793           vuse = gimple_phi_arg_def (phi, 0);
 794           for (i = 1; i < gimple_phi_num_args (phi); ++i)
 795             {
 796               if (gimple_phi_arg_def (phi, i) != vuse)
 797                 {
 798                   vuse = NULL_TREE;
 799                   break;
 800                 }
 801             }
 802           if (vuse != NULL_TREE)
 803             {
 804               tree vdef = gimple_phi_result (phi);
 805               use_operand_p use_p;
 806               imm_use_iterator iter;
 807               gimple use_stmt;
 808               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
 809                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 810                   SET_USE (use_p, vuse);
 811               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
 812                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
 813             }
 814           else
 815             gimple_set_plf (phi, STMT_NECESSARY, true);
 816         }
 817
 818       if (!gimple_plf (phi, STMT_NECESSARY))
 819         {
 820           something_changed = true;
 821           if (dump_file && (dump_flags & TDF_DETAILS))
 822             {
 823               fprintf (dump_file, "Deleting : ");
 824               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 825               fprintf (dump_file, "\n");
 826             }
 827
 828           remove_phi_node (&gsi, true);
 829           stats.removed_phis++;
 830           continue;
 831         }
 832
 833       gsi_next (&gsi);
 834     }
 835   return something_changed;
 836 }
 837
 838
 839 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 840    containing I so that we don't have to look it up.  */
 841
 842 static void
 843 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
 844 {
 845   gimple stmt = gsi_stmt (*i);
 846
 847   if (dump_file && (dump_flags & TDF_DETAILS))
 848     {
 849       fprintf (dump_file, "Deleting : ");
 850       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 851       fprintf (dump_file, "\n");
 852     }
 853
 854   stats.removed++;
 855
 856   /* If we have determined that a conditional branch statement contributes
 857      nothing to the program, then we not only remove it, but we also change
 858      the flow graph so that the current block will simply fall-thru to its
 859      immediate post-dominator.  The blocks we are circumventing will be
 860      removed by cleanup_tree_cfg if this change in the flow graph makes them
 861      unreachable.  */
 862   if (is_ctrl_stmt (stmt))
 863     {
 864       basic_block post_dom_bb;
 865
 866       /* The post dominance info has to be up-to-date.  */
 867       gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
 868       /* Get the immediate post dominator of bb.  */
 869       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 870
 871       /* There are three particularly problematical cases.
 872
 873          1. Blocks that do not have an immediate post dominator.  This
 874             can happen with infinite loops.
 875
 876          2. Blocks that are only post dominated by the exit block.  These
 877             can also happen for infinite loops as we create fake edges
 878             in the dominator tree.
 879
 880          3. If the post dominator has PHI nodes we may be able to compute
 881             the right PHI args for them.
 882
 883          In each of these cases we must remove the control statement
 884          as it may reference SSA_NAMEs which are going to be removed and
 885          we remove all but one outgoing edge from the block.  */
 886       if (! post_dom_bb
 887           || post_dom_bb == EXIT_BLOCK_PTR
 888           || phi_nodes (post_dom_bb))
 889         ;
 890       else
 891         {
 892           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 893           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 894           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 895
 896           /* It is not sufficient to set cfg_altered below during edge
 897              removal, in case BB has two successors and one of them
 898              is POST_DOM_BB.  */
 899           cfg_altered = true;
 900         }
 901       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 902       EDGE_SUCC (bb, 0)->count = bb->count;
 903
 904       /* The edge is no longer associated with a conditional, so it does
 905          not have TRUE/FALSE flags.  */
 906       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 907
 908       /* The lone outgoing edge from BB will be a fallthru edge.  */
 909       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 910
 911       /* Remove the remaining the outgoing edges.  */
 912       while (!single_succ_p (bb))
 913         {
 914           /* FIXME.  When we remove the edge, we modify the CFG, which
 915              in turn modifies the dominator and post-dominator tree.
 916              Is it safe to postpone recomputing the dominator and
 917              post-dominator tree until the end of this pass given that
 918              the post-dominators are used above?  */
 919           cfg_altered = true;
 920           remove_edge (EDGE_SUCC (bb, 1));
 921         }
 922     }
 923
 924   unlink_stmt_vdef (stmt);
 925   gsi_remove (i, true);
 926   release_defs (stmt);
 927 }
 928
 929
 930 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 931    contributes nothing to the program, and can be deleted.  */
 932
 933 static bool
 934 eliminate_unnecessary_stmts (void)
 935 {
 936   bool something_changed = false;
 937   basic_block bb;
 938   gimple_stmt_iterator gsi;
 939   gimple stmt;
 940   tree call;
 941
 942   if (dump_file && (dump_flags & TDF_DETAILS))
 943     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 944
 945   clear_special_calls ();
 946
 947   FOR_EACH_BB (bb)
 948     {
 949       /* Remove dead statements.  */
 950       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 951         {
 952           stmt = gsi_stmt (gsi);
 953
 954           stats.total++;
 955
 956           /* If GSI is not necessary then remove it.  */
 957           if (!gimple_plf (stmt, STMT_NECESSARY))
 958             {
 959               remove_dead_stmt (&gsi, bb);
 960               something_changed = true;
 961             }
 962           else if (is_gimple_call (stmt))
 963             {
 964               call = gimple_call_fndecl (stmt);
 965               if (call)
 966                 {
 967                   tree name;
 968
 969                   /* When LHS of var = call (); is dead, simplify it into
 970                      call (); saving one operand.  */
 971                   name = gimple_call_lhs (stmt);
 972                   if (name && TREE_CODE (name) == SSA_NAME
 973                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
 974                     {
 975                       something_changed = true;
 976                       if (dump_file && (dump_flags & TDF_DETAILS))
 977                         {
 978                           fprintf (dump_file, "Deleting LHS of call: ");
 979                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 980                           fprintf (dump_file, "\n");
 981                         }
 982
 983                       gimple_call_set_lhs (stmt, NULL_TREE);
 984                       maybe_clean_or_replace_eh_stmt (stmt, stmt);
 985                       update_stmt (stmt);
 986                       release_ssa_name (name);
 987                     }
 988                   notice_special_calls (stmt);
 989                 }
 990               gsi_next (&gsi);
 991             }
 992           else
 993             {
 994               gsi_next (&gsi);
 995             }
 996         }
 997     }
 998
 999   FOR_EACH_BB (bb)
1000     {
1001       /* Remove dead PHI nodes.  */
1002       something_changed |= remove_dead_phis (bb);
1003     }
1004
1005   return something_changed;
1006 }
1007
1008
1009 /* Print out removed statement statistics.  */
1010
1011 static void
1012 print_stats (void)
1013 {
1014   float percg;
1015
1016   percg = ((float) stats.removed / (float) stats.total) * 100;
1017   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1018            stats.removed, stats.total, (int) percg);
1019
1020   if (stats.total_phis == 0)
1021     percg = 0;
1022   else
1023     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1024
1025   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1026            stats.removed_phis, stats.total_phis, (int) percg);
1027 }
1028
1029 /* Initialization for this pass.  Set up the used data structures.  */
1030
1031 static void
1032 tree_dce_init (bool aggressive)
1033 {
1034   memset ((void *) &stats, 0, sizeof (stats));
1035
1036   if (aggressive)
1037     {
1038       int i;
1039
1040       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1041       for (i = 0; i < last_basic_block; ++i)
1042         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1043
1044       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1045       sbitmap_zero (last_stmt_necessary);
1046     }
1047
1048   processed = sbitmap_alloc (num_ssa_names + 1);
1049   sbitmap_zero (processed);
1050
1051   worklist = VEC_alloc (gimple, heap, 64);
1052   cfg_altered = false;
1053 }
1054
1055 /* Cleanup after this pass.  */
1056
1057 static void
1058 tree_dce_done (bool aggressive)
1059 {
1060   if (aggressive)
1061     {
1062       int i;
1063
1064       for (i = 0; i < last_basic_block; ++i)
1065         BITMAP_FREE (control_dependence_map[i]);
1066       free (control_dependence_map);
1067
1068       sbitmap_free (visited_control_parents);
1069       sbitmap_free (last_stmt_necessary);
1070     }
1071
1072   sbitmap_free (processed);
1073
1074   VEC_free (gimple, heap, worklist);
1075 }
1076
1077 /* Main routine to eliminate dead code.
1078
1079    AGGRESSIVE controls the aggressiveness of the algorithm.
1080    In conservative mode, we ignore control dependence and simply declare
1081    all but the most trivially dead branches necessary.  This mode is fast.
1082    In aggressive mode, control dependences are taken into account, which
1083    results in more dead code elimination, but at the cost of some time.
1084
1085    FIXME: Aggressive mode before PRE doesn't work currently because
1086           the dominance info is not invalidated after DCE1.  This is
1087           not an issue right now because we only run aggressive DCE
1088           as the last tree SSA pass, but keep this in mind when you
1089           start experimenting with pass ordering.  */
1090
1091 static unsigned int
1092 perform_tree_ssa_dce (bool aggressive)
1093 {
1094   struct edge_list *el = NULL;
1095   bool something_changed = 0;
1096
1097   tree_dce_init (aggressive);
1098
1099   if (aggressive)
1100     {
1101       /* Compute control dependence.  */
1102       timevar_push (TV_CONTROL_DEPENDENCES);
1103       calculate_dominance_info (CDI_POST_DOMINATORS);
1104       el = create_edge_list ();
1105       find_all_control_dependences (el);
1106       timevar_pop (TV_CONTROL_DEPENDENCES);
1107
1108       visited_control_parents = sbitmap_alloc (last_basic_block);
1109       sbitmap_zero (visited_control_parents);
1110
1111       mark_dfs_back_edges ();
1112     }
1113
1114   find_obviously_necessary_stmts (el);
1115
1116   longest_chain = 0;
1117   total_chain = 0;
1118   chain_ovfl = false;
1119   propagate_necessity (el);
1120   BITMAP_FREE (visited);
1121
1122   something_changed |= eliminate_unnecessary_stmts ();
1123   something_changed |= cfg_altered;
1124
1125   /* We do not update postdominators, so free them unconditionally.  */
1126   free_dominance_info (CDI_POST_DOMINATORS);
1127
1128   /* If we removed paths in the CFG, then we need to update
1129      dominators as well.  I haven't investigated the possibility
1130      of incrementally updating dominators.  */
1131   if (cfg_altered)
1132     free_dominance_info (CDI_DOMINATORS);
1133
1134   statistics_counter_event (cfun, "Statements deleted", stats.removed);
1135   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1136
1137   /* Debugging dumps.  */
1138   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1139     print_stats ();
1140
1141   tree_dce_done (aggressive);
1142
1143   free_edge_list (el);
1144
1145   if (something_changed)
1146     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1147             | TODO_remove_unused_locals);
1148   else
1149     return 0;
1150 }
1151
1152 /* Pass entry points.  */
1153 static unsigned int
1154 tree_ssa_dce (void)
1155 {
1156   return perform_tree_ssa_dce (/*aggressive=*/false);
1157 }
1158
1159 static unsigned int
1160 tree_ssa_dce_loop (void)
1161 {
1162   unsigned int todo;
1163   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1164   if (todo)
1165     {
1166       free_numbers_of_iterations_estimates ();
1167       scev_reset ();
1168     }
1169   return todo;
1170 }
1171
1172 static unsigned int
1173 tree_ssa_cd_dce (void)
1174 {
1175   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1176 }
1177
1178 static bool
1179 gate_dce (void)
1180 {
1181   return flag_tree_dce != 0;
1182 }
1183
1184 struct gimple_opt_pass pass_dce =
1185 {
1186  {
1187   GIMPLE_PASS,
1188   "dce",                                /* name */
1189   gate_dce,                             /* gate */
1190   tree_ssa_dce,                         /* execute */
1191   NULL,                                 /* sub */
1192   NULL,                                 /* next */
1193   0,                                    /* static_pass_number */
1194   TV_TREE_DCE,                          /* tv_id */
1195   PROP_cfg | PROP_ssa,                  /* properties_required */
1196   0,                                    /* properties_provided */
1197   0,                                    /* properties_destroyed */
1198   0,                                    /* todo_flags_start */
1199   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1200  }
1201 };
1202
1203 struct gimple_opt_pass pass_dce_loop =
1204 {
1205  {
1206   GIMPLE_PASS,
1207   "dceloop",                            /* name */
1208   gate_dce,                             /* gate */
1209   tree_ssa_dce_loop,                    /* execute */
1210   NULL,                                 /* sub */
1211   NULL,                                 /* next */
1212   0,                                    /* static_pass_number */
1213   TV_TREE_DCE,                          /* tv_id */
1214   PROP_cfg | PROP_ssa,                  /* properties_required */
1215   0,                                    /* properties_provided */
1216   0,                                    /* properties_destroyed */
1217   0,                                    /* todo_flags_start */
1218   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1219  }
1220 };
1221
1222 struct gimple_opt_pass pass_cd_dce =
1223 {
1224  {
1225   GIMPLE_PASS,
1226   "cddce",                              /* name */
1227   gate_dce,                             /* gate */
1228   tree_ssa_cd_dce,                      /* execute */
1229   NULL,                                 /* sub */
1230   NULL,                                 /* next */
1231   0,                                    /* static_pass_number */
1232   TV_TREE_CD_DCE,                       /* tv_id */
1233   PROP_cfg | PROP_ssa,                  /* properties_required */
1234   0,                                    /* properties_provided */
1235   0,                                    /* properties_destroyed */
1236   0,                                    /* todo_flags_start */
1237   TODO_dump_func | TODO_verify_ssa
1238   | TODO_verify_flow                    /* todo_flags_finish */
1239  }
1240 };