gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   3    Contributed by Ben Elliston <bje@redhat.com>
   4    and Andrew MacLeod <amacleod@redhat.com>
   5    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by the
  11 Free Software Foundation; either version 2, or (at your option) any
  12 later version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT
  15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  22 02110-1301, USA.  */
  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 "tree-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 \f
  70 static struct stmt_stats
  71 {
  72   int total;
  73   int total_phis;
  74   int removed;
  75   int removed_phis;
  76 } stats;
  77
  78 static VEC(tree,heap) *worklist;
  79
  80 /* Vector indicating an SSA name has already been processed and marked
  81    as necessary.  */
  82 static sbitmap processed;
  83
  84 /* Vector indicating that last_stmt if a basic block has already been
  85    marked as necessary.  */
  86 static sbitmap last_stmt_necessary;
  87
  88 /* Before we can determine whether a control branch is dead, we need to
  89    compute which blocks are control dependent on which edges.
  90
  91    We expect each block to be control dependent on very few edges so we
  92    use a bitmap for each block recording its edges.  An array holds the
  93    bitmap.  The Ith bit in the bitmap is set if that block is dependent
  94    on the Ith edge.  */
  95 static bitmap *control_dependence_map;
  96
  97 /* Vector indicating that a basic block has already had all the edges
  98    processed that it is control dependent on.  */
  99 static sbitmap visited_control_parents;
 100
 101 /* TRUE if this pass alters the CFG (by removing control statements).
 102    FALSE otherwise.
 103
 104    If this pass alters the CFG, then it will arrange for the dominators
 105    to be recomputed.  */
 106 static bool cfg_altered;
 107
 108 /* Execute code that follows the macro for each edge (given number
 109    EDGE_NUMBER within the CODE) for which the block with index N is
 110    control dependent.  */
 111 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)        \
 112   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,     \
 113                             (EDGE_NUMBER), (BI))
 114
 115
 116 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
 117 static inline void
 118 set_control_dependence_map_bit (basic_block bb, int edge_index)
 119 {
 120   if (bb == ENTRY_BLOCK_PTR)
 121     return;
 122   gcc_assert (bb != EXIT_BLOCK_PTR);
 123   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
 124 }
 125
 126 /* Clear all control dependences for block BB.  */
 127 static inline void
 128 clear_control_dependence_bitmap (basic_block bb)
 129 {
 130   bitmap_clear (control_dependence_map[bb->index]);
 131 }
 132
 133
 134 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
 135    This function is necessary because some blocks have negative numbers.  */
 136
 137 static inline basic_block
 138 find_pdom (basic_block block)
 139 {
 140   gcc_assert (block != ENTRY_BLOCK_PTR);
 141
 142   if (block == EXIT_BLOCK_PTR)
 143     return EXIT_BLOCK_PTR;
 144   else
 145     {
 146       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
 147       if (! bb)
 148         return EXIT_BLOCK_PTR;
 149       return bb;
 150     }
 151 }
 152
 153
 154 /* Determine all blocks' control dependences on the given edge with edge_list
 155    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
 156
 157 static void
 158 find_control_dependence (struct edge_list *el, int edge_index)
 159 {
 160   basic_block current_block;
 161   basic_block ending_block;
 162
 163   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
 164
 165   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 166     ending_block = single_succ (ENTRY_BLOCK_PTR);
 167   else
 168     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
 169
 170   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 171        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 172        current_block = find_pdom (current_block))
 173     {
 174       edge e = INDEX_EDGE (el, edge_index);
 175
 176       /* For abnormal edges, we don't make current_block control
 177          dependent because instructions that throw are always necessary
 178          anyway.  */
 179       if (e->flags & EDGE_ABNORMAL)
 180         continue;
 181
 182       set_control_dependence_map_bit (current_block, edge_index);
 183     }
 184 }
 185
 186
 187 /* Record all blocks' control dependences on all edges in the edge
 188    list EL, ala Morgan, Section 3.6.  */
 189
 190 static void
 191 find_all_control_dependences (struct edge_list *el)
 192 {
 193   int i;
 194
 195   for (i = 0; i < NUM_EDGES (el); ++i)
 196     find_control_dependence (el, i);
 197 }
 198
 199
 200 #define NECESSARY(stmt)         stmt->base.asm_written_flag
 201
 202 /* If STMT is not already marked necessary, mark it, and add it to the
 203    worklist if ADD_TO_WORKLIST is true.  */
 204 static inline void
 205 mark_stmt_necessary (tree stmt, bool add_to_worklist)
 206 {
 207   gcc_assert (stmt);
 208   gcc_assert (!DECL_P (stmt));
 209
 210   if (NECESSARY (stmt))
 211     return;
 212
 213   if (dump_file && (dump_flags & TDF_DETAILS))
 214     {
 215       fprintf (dump_file, "Marking useful stmt: ");
 216       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 217       fprintf (dump_file, "\n");
 218     }
 219
 220   NECESSARY (stmt) = 1;
 221   if (add_to_worklist)
 222     VEC_safe_push (tree, heap, worklist, stmt);
 223 }
 224
 225
 226 /* Mark the statement defining operand OP as necessary.  */
 227
 228 static inline void
 229 mark_operand_necessary (tree op)
 230 {
 231   tree stmt;
 232   int ver;
 233
 234   gcc_assert (op);
 235
 236   ver = SSA_NAME_VERSION (op);
 237   if (TEST_BIT (processed, ver))
 238     return;
 239   SET_BIT (processed, ver);
 240
 241   stmt = SSA_NAME_DEF_STMT (op);
 242   gcc_assert (stmt);
 243
 244   if (NECESSARY (stmt) || IS_EMPTY_STMT (stmt))
 245     return;
 246
 247   NECESSARY (stmt) = 1;
 248   VEC_safe_push (tree, heap, worklist, stmt);
 249 }
 250
 251
 252 /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
 253    it can make other statements necessary.
 254
 255    If AGGRESSIVE is false, control statements are conservatively marked as
 256    necessary.  */
 257
 258 static void
 259 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 260 {
 261   stmt_ann_t ann;
 262   tree op;
 263
 264   /* With non-call exceptions, we have to assume that all statements could
 265      throw.  If a statement may throw, it is inherently necessary.  */
 266   if (flag_non_call_exceptions
 267       && tree_could_throw_p (stmt))
 268     {
 269       mark_stmt_necessary (stmt, true);
 270       return;
 271     }
 272
 273   /* Statements that are implicitly live.  Most function calls, asm and return
 274      statements are required.  Labels and BIND_EXPR nodes are kept because
 275      they are control flow, and we have no way of knowing whether they can be
 276      removed.  DCE can eliminate all the other statements in a block, and CFG
 277      can then remove the block and labels.  */
 278   switch (TREE_CODE (stmt))
 279     {
 280     case BIND_EXPR:
 281     case LABEL_EXPR:
 282     case CASE_LABEL_EXPR:
 283       mark_stmt_necessary (stmt, false);
 284       return;
 285
 286     case ASM_EXPR:
 287     case RESX_EXPR:
 288     case RETURN_EXPR:
 289       mark_stmt_necessary (stmt, true);
 290       return;
 291
 292     case CALL_EXPR:
 293       /* Most, but not all function calls are required.  Function calls that
 294          produce no result and have no side effects (i.e. const pure
 295          functions) are unnecessary.  */
 296       if (TREE_SIDE_EFFECTS (stmt))
 297         mark_stmt_necessary (stmt, true);
 298       return;
 299
 300     case GIMPLE_MODIFY_STMT:
 301       op = get_call_expr_in (stmt);
 302       if (op && TREE_SIDE_EFFECTS (op))
 303         {
 304           mark_stmt_necessary (stmt, true);
 305           return;
 306         }
 307
 308       /* These values are mildly magic bits of the EH runtime.  We can't
 309          see the entire lifetime of these values until landing pads are
 310          generated.  */
 311       if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == EXC_PTR_EXPR
 312           || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == FILTER_EXPR)
 313         {
 314           mark_stmt_necessary (stmt, true);
 315           return;
 316         }
 317       break;
 318
 319     case GOTO_EXPR:
 320       gcc_assert (!simple_goto_p (stmt));
 321       mark_stmt_necessary (stmt, true);
 322       return;
 323
 324     case COND_EXPR:
 325       gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2);
 326       /* Fall through.  */
 327
 328     case SWITCH_EXPR:
 329       if (! aggressive)
 330         mark_stmt_necessary (stmt, true);
 331       break;
 332
 333     default:
 334       break;
 335     }
 336
 337   ann = stmt_ann (stmt);
 338
 339   /* If the statement has volatile operands, it needs to be preserved.
 340      Same for statements that can alter control flow in unpredictable
 341      ways.  */
 342   if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
 343     {
 344       mark_stmt_necessary (stmt, true);
 345       return;
 346     }
 347
 348   if (is_hidden_global_store (stmt))
 349     {
 350       mark_stmt_necessary (stmt, true);
 351       return;
 352     }
 353
 354   return;
 355 }
 356
 357
 358 /* Make corresponding control dependent edges necessary.  We only
 359    have to do this once for each basic block, so we clear the bitmap
 360    after we're done.  */
 361 static void
 362 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 363 {
 364   bitmap_iterator bi;
 365   unsigned edge_number;
 366
 367   gcc_assert (bb != EXIT_BLOCK_PTR);
 368
 369   if (bb == ENTRY_BLOCK_PTR)
 370     return;
 371
 372   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 373     {
 374       tree t;
 375       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 376
 377       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 378         continue;
 379       SET_BIT (last_stmt_necessary, cd_bb->index);
 380
 381       t = last_stmt (cd_bb);
 382       if (t && is_ctrl_stmt (t))
 383         mark_stmt_necessary (t, true);
 384     }
 385 }
 386
 387
 388 /* Find obviously necessary statements.  These are things like most function
 389    calls, and stores to file level variables.
 390
 391    If EL is NULL, control statements are conservatively marked as
 392    necessary.  Otherwise it contains the list of edges used by control
 393    dependence analysis.  */
 394
 395 static void
 396 find_obviously_necessary_stmts (struct edge_list *el)
 397 {
 398   basic_block bb;
 399   block_stmt_iterator i;
 400   edge e;
 401
 402   FOR_EACH_BB (bb)
 403     {
 404       tree phi;
 405
 406       /* PHI nodes are never inherently necessary.  */
 407       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 408         NECESSARY (phi) = 0;
 409
 410       /* Check all statements in the block.  */
 411       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 412         {
 413           tree stmt = bsi_stmt (i);
 414           NECESSARY (stmt) = 0;
 415           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 416         }
 417     }
 418
 419   if (el)
 420     {
 421       /* Prevent the loops from being removed.  We must keep the infinite loops,
 422          and we currently do not have a means to recognize the finite ones.  */
 423       FOR_EACH_BB (bb)
 424         {
 425           edge_iterator ei;
 426           FOR_EACH_EDGE (e, ei, bb->succs)
 427             if (e->flags & EDGE_DFS_BACK)
 428               mark_control_dependent_edges_necessary (e->dest, el);
 429         }
 430     }
 431 }
 432
 433
 434 /* Propagate necessity using the operands of necessary statements.
 435    Process the uses on each statement in the worklist, and add all
 436    feeding statements which contribute to the calculation of this
 437    value to the worklist.
 438
 439    In conservative mode, EL is NULL.  */
 440
 441 static void
 442 propagate_necessity (struct edge_list *el)
 443 {
 444   tree stmt;
 445   bool aggressive = (el ? true : false);
 446
 447   if (dump_file && (dump_flags & TDF_DETAILS))
 448     fprintf (dump_file, "\nProcessing worklist:\n");
 449
 450   while (VEC_length (tree, worklist) > 0)
 451     {
 452       /* Take STMT from worklist.  */
 453       stmt = VEC_pop (tree, worklist);
 454
 455       if (dump_file && (dump_flags & TDF_DETAILS))
 456         {
 457           fprintf (dump_file, "processing: ");
 458           print_generic_stmt (dump_file, stmt, TDF_SLIM);
 459           fprintf (dump_file, "\n");
 460         }
 461
 462       if (aggressive)
 463         {
 464           /* Mark the last statements of the basic blocks that the block
 465              containing STMT is control dependent on, but only if we haven't
 466              already done so.  */
 467           basic_block bb = bb_for_stmt (stmt);
 468           if (bb != ENTRY_BLOCK_PTR
 469               && ! TEST_BIT (visited_control_parents, bb->index))
 470             {
 471               SET_BIT (visited_control_parents, bb->index);
 472               mark_control_dependent_edges_necessary (bb, el);
 473             }
 474         }
 475
 476       if (TREE_CODE (stmt) == PHI_NODE)
 477         {
 478           /* PHI nodes are somewhat special in that each PHI alternative has
 479              data and control dependencies.  All the statements feeding the
 480              PHI node's arguments are always necessary.  In aggressive mode,
 481              we also consider the control dependent edges leading to the
 482              predecessor block associated with each PHI alternative as
 483              necessary.  */
 484           int k;
 485
 486           for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
 487             {
 488               tree arg = PHI_ARG_DEF (stmt, k);
 489               if (TREE_CODE (arg) == SSA_NAME)
 490                 mark_operand_necessary (arg);
 491             }
 492
 493           if (aggressive)
 494             {
 495               for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
 496                 {
 497                   basic_block arg_bb = PHI_ARG_EDGE (stmt, k)->src;
 498                   if (arg_bb != ENTRY_BLOCK_PTR
 499                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 500                     {
 501                       SET_BIT (visited_control_parents, arg_bb->index);
 502                       mark_control_dependent_edges_necessary (arg_bb, el);
 503                     }
 504                 }
 505             }
 506         }
 507       else
 508         {
 509           /* Propagate through the operands.  Examine all the USE, VUSE and
 510              VDEF operands in this statement.  Mark all the statements
 511              which feed this statement's uses as necessary.  The
 512              operands of VDEF expressions are also needed as they
 513              represent potential definitions that may reach this
 514              statement (VDEF operands allow us to follow def-def
 515              links).  */
 516           ssa_op_iter iter;
 517           tree use;
 518
 519           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
 520             mark_operand_necessary (use);
 521         }
 522     }
 523 }
 524
 525
 526 /* Remove dead PHI nodes from block BB.  */
 527
 528 static bool
 529 remove_dead_phis (basic_block bb)
 530 {
 531   tree prev, phi;
 532   bool something_changed = false;
 533
 534   prev = NULL_TREE;
 535   phi = phi_nodes (bb);
 536   while (phi)
 537     {
 538       stats.total_phis++;
 539
 540       if (! NECESSARY (phi))
 541         {
 542           tree next = PHI_CHAIN (phi);
 543
 544           something_changed = true;
 545           if (dump_file && (dump_flags & TDF_DETAILS))
 546             {
 547               fprintf (dump_file, "Deleting : ");
 548               print_generic_stmt (dump_file, phi, TDF_SLIM);
 549               fprintf (dump_file, "\n");
 550             }
 551
 552           remove_phi_node (phi, prev, true);
 553           stats.removed_phis++;
 554           phi = next;
 555         }
 556       else
 557         {
 558           prev = phi;
 559           phi = PHI_CHAIN (phi);
 560         }
 561     }
 562   return something_changed;
 563 }
 564
 565
 566 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 567    containing I so that we don't have to look it up.  */
 568
 569 static void
 570 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 571 {
 572   tree t = bsi_stmt (*i);
 573
 574   if (dump_file && (dump_flags & TDF_DETAILS))
 575     {
 576       fprintf (dump_file, "Deleting : ");
 577       print_generic_stmt (dump_file, t, TDF_SLIM);
 578       fprintf (dump_file, "\n");
 579     }
 580
 581   stats.removed++;
 582
 583   /* If we have determined that a conditional branch statement contributes
 584      nothing to the program, then we not only remove it, but we also change
 585      the flow graph so that the current block will simply fall-thru to its
 586      immediate post-dominator.  The blocks we are circumventing will be
 587      removed by cleanup_tree_cfg if this change in the flow graph makes them
 588      unreachable.  */
 589   if (is_ctrl_stmt (t))
 590     {
 591       basic_block post_dom_bb;
 592
 593       /* The post dominance info has to be up-to-date.  */
 594       gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
 595       /* Get the immediate post dominator of bb.  */
 596       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 597
 598       /* There are three particularly problematical cases.
 599
 600          1. Blocks that do not have an immediate post dominator.  This
 601             can happen with infinite loops.
 602
 603          2. Blocks that are only post dominated by the exit block.  These
 604             can also happen for infinite loops as we create fake edges
 605             in the dominator tree.
 606
 607          3. If the post dominator has PHI nodes we may be able to compute
 608             the right PHI args for them.
 609
 610          In each of these cases we must remove the control statement
 611          as it may reference SSA_NAMEs which are going to be removed and
 612          we remove all but one outgoing edge from the block.  */
 613       if (! post_dom_bb
 614           || post_dom_bb == EXIT_BLOCK_PTR
 615           || phi_nodes (post_dom_bb))
 616         ;
 617       else
 618         {
 619           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 620           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 621           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 622
 623           /* It is not sufficient to set cfg_altered below during edge
 624              removal, in case BB has two successors and one of them
 625              is POST_DOM_BB.  */
 626           cfg_altered = true;
 627         }
 628       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 629       EDGE_SUCC (bb, 0)->count = bb->count;
 630
 631       /* The edge is no longer associated with a conditional, so it does
 632          not have TRUE/FALSE flags.  */
 633       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 634
 635       /* The lone outgoing edge from BB will be a fallthru edge.  */
 636       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 637
 638       /* Remove the remaining the outgoing edges.  */
 639       while (!single_succ_p (bb))
 640         {
 641           /* FIXME.  When we remove the edge, we modify the CFG, which
 642              in turn modifies the dominator and post-dominator tree.
 643              Is it safe to postpone recomputing the dominator and
 644              post-dominator tree until the end of this pass given that
 645              the post-dominators are used above?  */
 646           cfg_altered = true;
 647           remove_edge (EDGE_SUCC (bb, 1));
 648         }
 649     }
 650
 651   bsi_remove (i, true);
 652   release_defs (t);
 653 }
 654
 655
 656 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 657    contributes nothing to the program, and can be deleted.  */
 658
 659 static bool
 660 eliminate_unnecessary_stmts (void)
 661 {
 662   bool something_changed = false;
 663   basic_block bb;
 664   block_stmt_iterator i;
 665
 666   if (dump_file && (dump_flags & TDF_DETAILS))
 667     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 668
 669   clear_special_calls ();
 670   FOR_EACH_BB (bb)
 671     {
 672       /* Remove dead PHI nodes.  */
 673       something_changed |= remove_dead_phis (bb);
 674     }
 675
 676   FOR_EACH_BB (bb)
 677     {
 678       /* Remove dead statements.  */
 679       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 680         {
 681           tree t = bsi_stmt (i);
 682
 683           stats.total++;
 684
 685           /* If `i' is not necessary then remove it.  */
 686           if (! NECESSARY (t))
 687             {
 688               remove_dead_stmt (&i, bb);
 689               something_changed = true;
 690             }
 691           else
 692             {
 693               tree call = get_call_expr_in (t);
 694               if (call)
 695                 {
 696                   tree name;
 697
 698                   /* When LHS of var = call (); is dead, simplify it into
 699                      call (); saving one operand.  */
 700                   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
 701                       && (TREE_CODE ((name = GIMPLE_STMT_OPERAND (t, 0)))
 702                           == SSA_NAME)
 703                       && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
 704                     {
 705                       tree oldlhs = GIMPLE_STMT_OPERAND (t, 0);
 706                       something_changed = true;
 707                       if (dump_file && (dump_flags & TDF_DETAILS))
 708                         {
 709                           fprintf (dump_file, "Deleting LHS of call: ");
 710                           print_generic_stmt (dump_file, t, TDF_SLIM);
 711                           fprintf (dump_file, "\n");
 712                         }
 713                       push_stmt_changes (bsi_stmt_ptr (i));
 714                       TREE_BLOCK (call) = TREE_BLOCK (t);
 715                       bsi_replace (&i, call, false);
 716                       maybe_clean_or_replace_eh_stmt (t, call);
 717                       mark_symbols_for_renaming (call);
 718                       pop_stmt_changes (bsi_stmt_ptr (i));
 719                       release_ssa_name (oldlhs);
 720                     }
 721                   notice_special_calls (call);
 722                 }
 723               bsi_next (&i);
 724             }
 725         }
 726     }
 727
 728   return something_changed;
 729 }
 730
 731
 732 /* Print out removed statement statistics.  */
 733
 734 static void
 735 print_stats (void)
 736 {
 737   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 738     {
 739       float percg;
 740
 741       percg = ((float) stats.removed / (float) stats.total) * 100;
 742       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 743                stats.removed, stats.total, (int) percg);
 744
 745       if (stats.total_phis == 0)
 746         percg = 0;
 747       else
 748         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 749
 750       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 751                stats.removed_phis, stats.total_phis, (int) percg);
 752     }
 753 }
 754 \f
 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 (tree, 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 (tree, heap, worklist);
 801 }
 802 \f
 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   /* Debugging dumps.  */
 857   if (dump_file)
 858     print_stats ();
 859
 860   tree_dce_done (aggressive);
 861
 862   free_edge_list (el);
 863
 864   if (something_changed)
 865     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
 866             | TODO_remove_unused_locals);
 867   else
 868     return 0;
 869 }
 870
 871 /* Pass entry points.  */
 872 static unsigned int
 873 tree_ssa_dce (void)
 874 {
 875   return perform_tree_ssa_dce (/*aggressive=*/false);
 876 }
 877
 878 static unsigned int
 879 tree_ssa_dce_loop (void)
 880 {
 881   unsigned int todo;
 882   todo = perform_tree_ssa_dce (/*aggressive=*/false);
 883   if (todo)
 884     {
 885       free_numbers_of_iterations_estimates ();
 886       scev_reset ();
 887     }
 888   return todo;
 889 }
 890
 891 static unsigned int
 892 tree_ssa_cd_dce (void)
 893 {
 894   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 895 }
 896
 897 static bool
 898 gate_dce (void)
 899 {
 900   return flag_tree_dce != 0;
 901 }
 902
 903 struct tree_opt_pass pass_dce =
 904 {
 905   "dce",                                /* name */
 906   gate_dce,                             /* gate */
 907   tree_ssa_dce,                         /* execute */
 908   NULL,                                 /* sub */
 909   NULL,                                 /* next */
 910   0,                                    /* static_pass_number */
 911   TV_TREE_DCE,                          /* tv_id */
 912   PROP_cfg | PROP_ssa,                  /* properties_required */
 913   0,                                    /* properties_provided */
 914   0,                                    /* properties_destroyed */
 915   0,                                    /* todo_flags_start */
 916   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 917   0                                     /* letter */
 918 };
 919
 920 struct tree_opt_pass pass_dce_loop =
 921 {
 922   "dceloop",                            /* name */
 923   gate_dce,                             /* gate */
 924   tree_ssa_dce_loop,                    /* execute */
 925   NULL,                                 /* sub */
 926   NULL,                                 /* next */
 927   0,                                    /* static_pass_number */
 928   TV_TREE_DCE,                          /* tv_id */
 929   PROP_cfg | PROP_ssa,                  /* properties_required */
 930   0,                                    /* properties_provided */
 931   0,                                    /* properties_destroyed */
 932   0,                                    /* todo_flags_start */
 933   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 934   0                                     /* letter */
 935 };
 936
 937 struct tree_opt_pass pass_cd_dce =
 938 {
 939   "cddce",                              /* name */
 940   gate_dce,                             /* gate */
 941   tree_ssa_cd_dce,                      /* execute */
 942   NULL,                                 /* sub */
 943   NULL,                                 /* next */
 944   0,                                    /* static_pass_number */
 945   TV_TREE_CD_DCE,                       /* tv_id */
 946   PROP_cfg | PROP_ssa,                  /* properties_required */
 947   0,                                    /* properties_provided */
 948   0,                                    /* properties_destroyed */
 949   0,                                    /* todo_flags_start */
 950   TODO_dump_func | TODO_verify_ssa
 951   | TODO_verify_flow,                   /* todo_flags_finish */
 952   0                                     /* letter */
 953 };