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     return;
 237   SET_BIT (processed, ver);
 238
 239   stmt = SSA_NAME_DEF_STMT (op);
 240   gcc_assert (stmt);
 241
 242   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
 243     return;
 244
 245   gimple_set_plf (stmt, STMT_NECESSARY, true);
 246   VEC_safe_push (gimple, heap, worklist, stmt);
 247 }
 248
 249
 250 /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
 251    it can make other statements necessary.
 252
 253    If AGGRESSIVE is false, control statements are conservatively marked as
 254    necessary.  */
 255
 256 static void
 257 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
 258 {
 259   tree lhs = NULL_TREE;
 260   /* With non-call exceptions, we have to assume that all statements could
 261      throw.  If a statement may throw, it is inherently necessary.  */
 262   if (flag_non_call_exceptions
 263       && stmt_could_throw_p (stmt))
 264     {
 265       mark_stmt_necessary (stmt, true);
 266       return;
 267     }
 268
 269   /* Statements that are implicitly live.  Most function calls, asm
 270      and return statements are required.  Labels and GIMPLE_BIND nodes
 271      are kept because they are control flow, and we have no way of
 272      knowing whether they can be removed.  DCE can eliminate all the
 273      other statements in a block, and CFG can then remove the block
 274      and labels.  */
 275   switch (gimple_code (stmt))
 276     {
 277     case GIMPLE_PREDICT:
 278     case GIMPLE_LABEL:
 279       mark_stmt_necessary (stmt, false);
 280       return;
 281
 282     case GIMPLE_ASM:
 283     case GIMPLE_RESX:
 284     case GIMPLE_RETURN:
 285     case GIMPLE_CHANGE_DYNAMIC_TYPE:
 286       mark_stmt_necessary (stmt, true);
 287       return;
 288
 289     case GIMPLE_CALL:
 290       /* Most, but not all function calls are required.  Function calls that
 291          produce no result and have no side effects (i.e. const pure
 292          functions) are unnecessary.  */
 293       if (gimple_has_side_effects (stmt))
 294         {
 295           mark_stmt_necessary (stmt, true);
 296           return;
 297         }
 298       if (!gimple_call_lhs (stmt))
 299         return;
 300       lhs = gimple_call_lhs (stmt);
 301       /* Fall through */
 302
 303     case GIMPLE_ASSIGN:
 304       if (!lhs)
 305         lhs = gimple_assign_lhs (stmt);
 306       /* These values are mildly magic bits of the EH runtime.  We can't
 307          see the entire lifetime of these values until landing pads are
 308          generated.  */
 309       if (TREE_CODE (lhs) == EXC_PTR_EXPR
 310           || TREE_CODE (lhs) == FILTER_EXPR)
 311         {
 312           mark_stmt_necessary (stmt, true);
 313           return;
 314         }
 315       break;
 316
 317     case GIMPLE_GOTO:
 318       gcc_assert (!simple_goto_p (stmt));
 319       mark_stmt_necessary (stmt, true);
 320       return;
 321
 322     case GIMPLE_COND:
 323       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
 324       /* Fall through.  */
 325
 326     case GIMPLE_SWITCH:
 327       if (! aggressive)
 328         mark_stmt_necessary (stmt, true);
 329       break;
 330
 331     default:
 332       break;
 333     }
 334
 335   /* If the statement has volatile operands, it needs to be preserved.
 336      Same for statements that can alter control flow in unpredictable
 337      ways.  */
 338   if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
 339     {
 340       mark_stmt_necessary (stmt, true);
 341       return;
 342     }
 343
 344   if (is_hidden_global_store (stmt))
 345     {
 346       mark_stmt_necessary (stmt, true);
 347       return;
 348     }
 349
 350   return;
 351 }
 352
 353
 354 /* Make corresponding control dependent edges necessary.  We only
 355    have to do this once for each basic block, so we clear the bitmap
 356    after we're done.  */
 357 static void
 358 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 359 {
 360   bitmap_iterator bi;
 361   unsigned edge_number;
 362
 363   gcc_assert (bb != EXIT_BLOCK_PTR);
 364
 365   if (bb == ENTRY_BLOCK_PTR)
 366     return;
 367
 368   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 369     {
 370       gimple stmt;
 371       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 372
 373       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 374         continue;
 375       SET_BIT (last_stmt_necessary, cd_bb->index);
 376
 377       stmt = last_stmt (cd_bb);
 378       if (stmt && is_ctrl_stmt (stmt))
 379         mark_stmt_necessary (stmt, true);
 380     }
 381 }
 382
 383
 384 /* Find obviously necessary statements.  These are things like most function
 385    calls, and stores to file level variables.
 386
 387    If EL is NULL, control statements are conservatively marked as
 388    necessary.  Otherwise it contains the list of edges used by control
 389    dependence analysis.  */
 390
 391 static void
 392 find_obviously_necessary_stmts (struct edge_list *el)
 393 {
 394   basic_block bb;
 395   gimple_stmt_iterator gsi;
 396   edge e;
 397   gimple phi, stmt;
 398
 399   FOR_EACH_BB (bb)
 400     {
 401       /* PHI nodes are never inherently necessary.  */
 402       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 403         {
 404           phi = gsi_stmt (gsi);
 405           gimple_set_plf (phi, STMT_NECESSARY, false);
 406         }
 407
 408       /* Check all statements in the block.  */
 409       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 410         {
 411           stmt = gsi_stmt (gsi);
 412           gimple_set_plf (stmt, STMT_NECESSARY, false);
 413           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 414         }
 415     }
 416
 417   if (el)
 418     {
 419       /* Prevent the loops from being removed.  We must keep the infinite loops,
 420          and we currently do not have a means to recognize the finite ones.  */
 421       FOR_EACH_BB (bb)
 422         {
 423           edge_iterator ei;
 424           FOR_EACH_EDGE (e, ei, bb->succs)
 425             if (e->flags & EDGE_DFS_BACK)
 426               mark_control_dependent_edges_necessary (e->dest, el);
 427         }
 428     }
 429 }
 430
 431
 432 /* Propagate necessity using the operands of necessary statements.
 433    Process the uses on each statement in the worklist, and add all
 434    feeding statements which contribute to the calculation of this
 435    value to the worklist.
 436
 437    In conservative mode, EL is NULL.  */
 438
 439 static void
 440 propagate_necessity (struct edge_list *el)
 441 {
 442   gimple stmt;
 443   bool aggressive = (el ? true : false);
 444
 445   if (dump_file && (dump_flags & TDF_DETAILS))
 446     fprintf (dump_file, "\nProcessing worklist:\n");
 447
 448   while (VEC_length (gimple, worklist) > 0)
 449     {
 450       /* Take STMT from worklist.  */
 451       stmt = VEC_pop (gimple, worklist);
 452
 453       if (dump_file && (dump_flags & TDF_DETAILS))
 454         {
 455           fprintf (dump_file, "processing: ");
 456           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 457           fprintf (dump_file, "\n");
 458         }
 459
 460       if (aggressive)
 461         {
 462           /* Mark the last statements of the basic blocks that the block
 463              containing STMT is control dependent on, but only if we haven't
 464              already done so.  */
 465           basic_block bb = gimple_bb (stmt);
 466           if (bb != ENTRY_BLOCK_PTR
 467               && ! TEST_BIT (visited_control_parents, bb->index))
 468             {
 469               SET_BIT (visited_control_parents, bb->index);
 470               mark_control_dependent_edges_necessary (bb, el);
 471             }
 472         }
 473
 474       if (gimple_code (stmt) == GIMPLE_PHI)
 475         {
 476           /* PHI nodes are somewhat special in that each PHI alternative has
 477              data and control dependencies.  All the statements feeding the
 478              PHI node's arguments are always necessary.  In aggressive mode,
 479              we also consider the control dependent edges leading to the
 480              predecessor block associated with each PHI alternative as
 481              necessary.  */
 482           size_t k;
 483
 484           for (k = 0; k < gimple_phi_num_args (stmt); k++)
 485             {
 486               tree arg = PHI_ARG_DEF (stmt, k);
 487               if (TREE_CODE (arg) == SSA_NAME)
 488                 mark_operand_necessary (arg);
 489             }
 490
 491           if (aggressive)
 492             {
 493               for (k = 0; k < gimple_phi_num_args (stmt); k++)
 494                 {
 495                   basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
 496                   if (arg_bb != ENTRY_BLOCK_PTR
 497                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 498                     {
 499                       SET_BIT (visited_control_parents, arg_bb->index);
 500                       mark_control_dependent_edges_necessary (arg_bb, el);
 501                     }
 502                 }
 503             }
 504         }
 505       else
 506         {
 507           /* Propagate through the operands.  Examine all the USE, VUSE and
 508              VDEF operands in this statement.  Mark all the statements
 509              which feed this statement's uses as necessary.  The
 510              operands of VDEF expressions are also needed as they
 511              represent potential definitions that may reach this
 512              statement (VDEF operands allow us to follow def-def
 513              links).  */
 514           ssa_op_iter iter;
 515           tree use;
 516
 517           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
 518             mark_operand_necessary (use);
 519         }
 520     }
 521 }
 522
 523
 524 /* Remove dead PHI nodes from block BB.  */
 525
 526 static bool
 527 remove_dead_phis (basic_block bb)
 528 {
 529   bool something_changed = false;
 530   gimple_seq phis;
 531   gimple phi;
 532   gimple_stmt_iterator gsi;
 533   phis = phi_nodes (bb);
 534
 535   for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
 536     {
 537       stats.total_phis++;
 538       phi = gsi_stmt (gsi);
 539
 540       if (!gimple_plf (phi, STMT_NECESSARY))
 541         {
 542           something_changed = true;
 543           if (dump_file && (dump_flags & TDF_DETAILS))
 544             {
 545               fprintf (dump_file, "Deleting : ");
 546               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 547               fprintf (dump_file, "\n");
 548             }
 549
 550           remove_phi_node (&gsi, true);
 551           stats.removed_phis++;
 552         }
 553       else
 554         {
 555           gsi_next (&gsi);
 556         }
 557     }
 558   return something_changed;
 559 }
 560
 561
 562 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 563    containing I so that we don't have to look it up.  */
 564
 565 static void
 566 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
 567 {
 568   gimple stmt = gsi_stmt (*i);
 569
 570   if (dump_file && (dump_flags & TDF_DETAILS))
 571     {
 572       fprintf (dump_file, "Deleting : ");
 573       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 574       fprintf (dump_file, "\n");
 575     }
 576
 577   stats.removed++;
 578
 579   /* If we have determined that a conditional branch statement contributes
 580      nothing to the program, then we not only remove it, but we also change
 581      the flow graph so that the current block will simply fall-thru to its
 582      immediate post-dominator.  The blocks we are circumventing will be
 583      removed by cleanup_tree_cfg if this change in the flow graph makes them
 584      unreachable.  */
 585   if (is_ctrl_stmt (stmt))
 586     {
 587       basic_block post_dom_bb;
 588
 589       /* The post dominance info has to be up-to-date.  */
 590       gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
 591       /* Get the immediate post dominator of bb.  */
 592       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 593
 594       /* There are three particularly problematical cases.
 595
 596          1. Blocks that do not have an immediate post dominator.  This
 597             can happen with infinite loops.
 598
 599          2. Blocks that are only post dominated by the exit block.  These
 600             can also happen for infinite loops as we create fake edges
 601             in the dominator tree.
 602
 603          3. If the post dominator has PHI nodes we may be able to compute
 604             the right PHI args for them.
 605
 606          In each of these cases we must remove the control statement
 607          as it may reference SSA_NAMEs which are going to be removed and
 608          we remove all but one outgoing edge from the block.  */
 609       if (! post_dom_bb
 610           || post_dom_bb == EXIT_BLOCK_PTR
 611           || phi_nodes (post_dom_bb))
 612         ;
 613       else
 614         {
 615           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 616           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 617           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 618
 619           /* It is not sufficient to set cfg_altered below during edge
 620              removal, in case BB has two successors and one of them
 621              is POST_DOM_BB.  */
 622           cfg_altered = true;
 623         }
 624       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 625       EDGE_SUCC (bb, 0)->count = bb->count;
 626
 627       /* The edge is no longer associated with a conditional, so it does
 628          not have TRUE/FALSE flags.  */
 629       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 630
 631       /* The lone outgoing edge from BB will be a fallthru edge.  */
 632       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 633
 634       /* Remove the remaining the outgoing edges.  */
 635       while (!single_succ_p (bb))
 636         {
 637           /* FIXME.  When we remove the edge, we modify the CFG, which
 638              in turn modifies the dominator and post-dominator tree.
 639              Is it safe to postpone recomputing the dominator and
 640              post-dominator tree until the end of this pass given that
 641              the post-dominators are used above?  */
 642           cfg_altered = true;
 643           remove_edge (EDGE_SUCC (bb, 1));
 644         }
 645     }
 646
 647   gsi_remove (i, true);
 648   release_defs (stmt);
 649 }
 650
 651
 652 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 653    contributes nothing to the program, and can be deleted.  */
 654
 655 static bool
 656 eliminate_unnecessary_stmts (void)
 657 {
 658   bool something_changed = false;
 659   basic_block bb;
 660   gimple_stmt_iterator gsi;
 661   gimple stmt;
 662   tree call;
 663
 664   if (dump_file && (dump_flags & TDF_DETAILS))
 665     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 666
 667   clear_special_calls ();
 668   FOR_EACH_BB (bb)
 669     {
 670       /* Remove dead PHI nodes.  */
 671       something_changed |= remove_dead_phis (bb);
 672     }
 673
 674   FOR_EACH_BB (bb)
 675     {
 676       /* Remove dead statements.  */
 677       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 678         {
 679           stmt = gsi_stmt (gsi);
 680
 681           stats.total++;
 682
 683           /* If GSI is not necessary then remove it.  */
 684           if (!gimple_plf (stmt, STMT_NECESSARY))
 685             {
 686               remove_dead_stmt (&gsi, bb);
 687               something_changed = true;
 688             }
 689           else if (is_gimple_call (stmt))
 690             {
 691               call = gimple_call_fndecl (stmt);
 692               if (call)
 693                 {
 694                   tree name;
 695                   gimple g;
 696
 697                   /* When LHS of var = call (); is dead, simplify it into
 698                      call (); saving one operand.  */
 699                   name = gimple_call_lhs (stmt);
 700                   if (name && TREE_CODE (name) == SSA_NAME
 701                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
 702                     {
 703                       something_changed = true;
 704                       if (dump_file && (dump_flags & TDF_DETAILS))
 705                         {
 706                           fprintf (dump_file, "Deleting LHS of call: ");
 707                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 708                           fprintf (dump_file, "\n");
 709                         }
 710
 711                       push_stmt_changes (gsi_stmt_ptr (&gsi));
 712                       g = gimple_copy (stmt);
 713                       gimple_call_set_lhs (g, NULL_TREE);
 714                       gsi_replace (&gsi, g, false);
 715                       maybe_clean_or_replace_eh_stmt (stmt, g);
 716                       mark_symbols_for_renaming (g);
 717                       pop_stmt_changes (gsi_stmt_ptr (&gsi));
 718                       release_ssa_name (name);
 719                     }
 720                   notice_special_calls (stmt);
 721                 }
 722               gsi_next (&gsi);
 723             }
 724           else
 725             {
 726               gsi_next (&gsi);
 727             }
 728         }
 729     }
 730
 731   return something_changed;
 732 }
 733
 734
 735 /* Print out removed statement statistics.  */
 736
 737 static void
 738 print_stats (void)
 739 {
 740   float percg;
 741
 742   percg = ((float) stats.removed / (float) stats.total) * 100;
 743   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 744            stats.removed, stats.total, (int) percg);
 745
 746   if (stats.total_phis == 0)
 747     percg = 0;
 748   else
 749     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 750
 751   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 752            stats.removed_phis, stats.total_phis, (int) percg);
 753 }
 754
 755 /* Initialization for this pass.  Set up the used data structures.  */
 756
 757 static void
 758 tree_dce_init (bool aggressive)
 759 {
 760   memset ((void *) &stats, 0, sizeof (stats));
 761
 762   if (aggressive)
 763     {
 764       int i;
 765
 766       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
 767       for (i = 0; i < last_basic_block; ++i)
 768         control_dependence_map[i] = BITMAP_ALLOC (NULL);
 769
 770       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 771       sbitmap_zero (last_stmt_necessary);
 772     }
 773
 774   processed = sbitmap_alloc (num_ssa_names + 1);
 775   sbitmap_zero (processed);
 776
 777   worklist = VEC_alloc (gimple, heap, 64);
 778   cfg_altered = false;
 779 }
 780
 781 /* Cleanup after this pass.  */
 782
 783 static void
 784 tree_dce_done (bool aggressive)
 785 {
 786   if (aggressive)
 787     {
 788       int i;
 789
 790       for (i = 0; i < last_basic_block; ++i)
 791         BITMAP_FREE (control_dependence_map[i]);
 792       free (control_dependence_map);
 793
 794       sbitmap_free (visited_control_parents);
 795       sbitmap_free (last_stmt_necessary);
 796     }
 797
 798   sbitmap_free (processed);
 799
 800   VEC_free (gimple, heap, worklist);
 801 }
 802
 803 /* Main routine to eliminate dead code.
 804
 805    AGGRESSIVE controls the aggressiveness of the algorithm.
 806    In conservative mode, we ignore control dependence and simply declare
 807    all but the most trivially dead branches necessary.  This mode is fast.
 808    In aggressive mode, control dependences are taken into account, which
 809    results in more dead code elimination, but at the cost of some time.
 810
 811    FIXME: Aggressive mode before PRE doesn't work currently because
 812           the dominance info is not invalidated after DCE1.  This is
 813           not an issue right now because we only run aggressive DCE
 814           as the last tree SSA pass, but keep this in mind when you
 815           start experimenting with pass ordering.  */
 816
 817 static unsigned int
 818 perform_tree_ssa_dce (bool aggressive)
 819 {
 820   struct edge_list *el = NULL;
 821   bool something_changed = 0;
 822
 823   tree_dce_init (aggressive);
 824
 825   if (aggressive)
 826     {
 827       /* Compute control dependence.  */
 828       timevar_push (TV_CONTROL_DEPENDENCES);
 829       calculate_dominance_info (CDI_POST_DOMINATORS);
 830       el = create_edge_list ();
 831       find_all_control_dependences (el);
 832       timevar_pop (TV_CONTROL_DEPENDENCES);
 833
 834       visited_control_parents = sbitmap_alloc (last_basic_block);
 835       sbitmap_zero (visited_control_parents);
 836
 837       mark_dfs_back_edges ();
 838     }
 839
 840   find_obviously_necessary_stmts (el);
 841
 842   propagate_necessity (el);
 843
 844   something_changed |= eliminate_unnecessary_stmts ();
 845   something_changed |= cfg_altered;
 846
 847   /* We do not update postdominators, so free them unconditionally.  */
 848   free_dominance_info (CDI_POST_DOMINATORS);
 849
 850   /* If we removed paths in the CFG, then we need to update
 851      dominators as well.  I haven't investigated the possibility
 852      of incrementally updating dominators.  */
 853   if (cfg_altered)
 854     free_dominance_info (CDI_DOMINATORS);
 855
 856   statistics_counter_event (cfun, "Statements deleted", stats.removed);
 857   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
 858
 859   /* Debugging dumps.  */
 860   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 861     print_stats ();
 862
 863   tree_dce_done (aggressive);
 864
 865   free_edge_list (el);
 866
 867   if (something_changed)
 868     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
 869             | TODO_remove_unused_locals);
 870   else
 871     return 0;
 872 }
 873
 874 /* Pass entry points.  */
 875 static unsigned int
 876 tree_ssa_dce (void)
 877 {
 878   return perform_tree_ssa_dce (/*aggressive=*/false);
 879 }
 880
 881 static unsigned int
 882 tree_ssa_dce_loop (void)
 883 {
 884   unsigned int todo;
 885   todo = perform_tree_ssa_dce (/*aggressive=*/false);
 886   if (todo)
 887     {
 888       free_numbers_of_iterations_estimates ();
 889       scev_reset ();
 890     }
 891   return todo;
 892 }
 893
 894 static unsigned int
 895 tree_ssa_cd_dce (void)
 896 {
 897   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 898 }
 899
 900 static bool
 901 gate_dce (void)
 902 {
 903   return flag_tree_dce != 0;
 904 }
 905
 906 struct gimple_opt_pass pass_dce =
 907 {
 908  {
 909   GIMPLE_PASS,
 910   "dce",                                /* name */
 911   gate_dce,                             /* gate */
 912   tree_ssa_dce,                         /* execute */
 913   NULL,                                 /* sub */
 914   NULL,                                 /* next */
 915   0,                                    /* static_pass_number */
 916   TV_TREE_DCE,                          /* tv_id */
 917   PROP_cfg | PROP_ssa,                  /* properties_required */
 918   0,                                    /* properties_provided */
 919   0,                                    /* properties_destroyed */
 920   0,                                    /* todo_flags_start */
 921   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
 922  }
 923 };
 924
 925 struct gimple_opt_pass pass_dce_loop =
 926 {
 927  {
 928   GIMPLE_PASS,
 929   "dceloop",                            /* name */
 930   gate_dce,                             /* gate */
 931   tree_ssa_dce_loop,                    /* execute */
 932   NULL,                                 /* sub */
 933   NULL,                                 /* next */
 934   0,                                    /* static_pass_number */
 935   TV_TREE_DCE,                          /* tv_id */
 936   PROP_cfg | PROP_ssa,                  /* properties_required */
 937   0,                                    /* properties_provided */
 938   0,                                    /* properties_destroyed */
 939   0,                                    /* todo_flags_start */
 940   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
 941  }
 942 };
 943
 944 struct gimple_opt_pass pass_cd_dce =
 945 {
 946  {
 947   GIMPLE_PASS,
 948   "cddce",                              /* name */
 949   gate_dce,                             /* gate */
 950   tree_ssa_cd_dce,                      /* execute */
 951   NULL,                                 /* sub */
 952   NULL,                                 /* next */
 953   0,                                    /* static_pass_number */
 954   TV_TREE_CD_DCE,                       /* tv_id */
 955   PROP_cfg | PROP_ssa,                  /* properties_required */
 956   0,                                    /* properties_provided */
 957   0,                                    /* properties_destroyed */
 958   0,                                    /* todo_flags_start */
 959   TODO_dump_func | TODO_verify_ssa
 960   | TODO_verify_flow                    /* todo_flags_finish */
 961  }
 962 };