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                       something_changed = true;
 706                       if (dump_file && (dump_flags & TDF_DETAILS))
 707                         {
 708                           fprintf (dump_file, "Deleting LHS of call: ");
 709                           print_generic_stmt (dump_file, t, TDF_SLIM);
 710                           fprintf (dump_file, "\n");
 711                         }
 712                       push_stmt_changes (bsi_stmt_ptr (i));
 713                       TREE_BLOCK (call) = TREE_BLOCK (t);
 714                       bsi_replace (&i, call, false);
 715                       maybe_clean_or_replace_eh_stmt (t, call);
 716                       mark_symbols_for_renaming (call);
 717                       pop_stmt_changes (bsi_stmt_ptr (i));
 718                     }
 719                   notice_special_calls (call);
 720                 }
 721               bsi_next (&i);
 722             }
 723         }
 724     }
 725
 726   return something_changed;
 727 }
 728
 729
 730 /* Print out removed statement statistics.  */
 731
 732 static void
 733 print_stats (void)
 734 {
 735   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 736     {
 737       float percg;
 738
 739       percg = ((float) stats.removed / (float) stats.total) * 100;
 740       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 741                stats.removed, stats.total, (int) percg);
 742
 743       if (stats.total_phis == 0)
 744         percg = 0;
 745       else
 746         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 747
 748       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 749                stats.removed_phis, stats.total_phis, (int) percg);
 750     }
 751 }
 752 \f
 753 /* Initialization for this pass.  Set up the used data structures.  */
 754
 755 static void
 756 tree_dce_init (bool aggressive)
 757 {
 758   memset ((void *) &stats, 0, sizeof (stats));
 759
 760   if (aggressive)
 761     {
 762       int i;
 763
 764       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
 765       for (i = 0; i < last_basic_block; ++i)
 766         control_dependence_map[i] = BITMAP_ALLOC (NULL);
 767
 768       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 769       sbitmap_zero (last_stmt_necessary);
 770     }
 771
 772   processed = sbitmap_alloc (num_ssa_names + 1);
 773   sbitmap_zero (processed);
 774
 775   worklist = VEC_alloc (tree, heap, 64);
 776   cfg_altered = false;
 777 }
 778
 779 /* Cleanup after this pass.  */
 780
 781 static void
 782 tree_dce_done (bool aggressive)
 783 {
 784   if (aggressive)
 785     {
 786       int i;
 787
 788       for (i = 0; i < last_basic_block; ++i)
 789         BITMAP_FREE (control_dependence_map[i]);
 790       free (control_dependence_map);
 791
 792       sbitmap_free (visited_control_parents);
 793       sbitmap_free (last_stmt_necessary);
 794     }
 795
 796   sbitmap_free (processed);
 797
 798   VEC_free (tree, heap, worklist);
 799 }
 800 \f
 801 /* Main routine to eliminate dead code.
 802
 803    AGGRESSIVE controls the aggressiveness of the algorithm.
 804    In conservative mode, we ignore control dependence and simply declare
 805    all but the most trivially dead branches necessary.  This mode is fast.
 806    In aggressive mode, control dependences are taken into account, which
 807    results in more dead code elimination, but at the cost of some time.
 808
 809    FIXME: Aggressive mode before PRE doesn't work currently because
 810           the dominance info is not invalidated after DCE1.  This is
 811           not an issue right now because we only run aggressive DCE
 812           as the last tree SSA pass, but keep this in mind when you
 813           start experimenting with pass ordering.  */
 814
 815 static unsigned int
 816 perform_tree_ssa_dce (bool aggressive)
 817 {
 818   struct edge_list *el = NULL;
 819   bool something_changed = 0;
 820
 821   tree_dce_init (aggressive);
 822
 823   if (aggressive)
 824     {
 825       /* Compute control dependence.  */
 826       timevar_push (TV_CONTROL_DEPENDENCES);
 827       calculate_dominance_info (CDI_POST_DOMINATORS);
 828       el = create_edge_list ();
 829       find_all_control_dependences (el);
 830       timevar_pop (TV_CONTROL_DEPENDENCES);
 831
 832       visited_control_parents = sbitmap_alloc (last_basic_block);
 833       sbitmap_zero (visited_control_parents);
 834
 835       mark_dfs_back_edges ();
 836     }
 837
 838   find_obviously_necessary_stmts (el);
 839
 840   propagate_necessity (el);
 841
 842   something_changed |= eliminate_unnecessary_stmts ();
 843   something_changed |= cfg_altered;
 844
 845   /* We do not update postdominators, so free them unconditionally.  */
 846   free_dominance_info (CDI_POST_DOMINATORS);
 847
 848   /* If we removed paths in the CFG, then we need to update
 849      dominators as well.  I haven't investigated the possibility
 850      of incrementally updating dominators.  */
 851   if (cfg_altered)
 852     free_dominance_info (CDI_DOMINATORS);
 853
 854   /* Debugging dumps.  */
 855   if (dump_file)
 856     print_stats ();
 857
 858   tree_dce_done (aggressive);
 859
 860   free_edge_list (el);
 861
 862   if (something_changed)
 863     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
 864             | TODO_remove_unused_locals);
 865   else
 866     return 0;
 867 }
 868
 869 /* Pass entry points.  */
 870 static unsigned int
 871 tree_ssa_dce (void)
 872 {
 873   return perform_tree_ssa_dce (/*aggressive=*/false);
 874 }
 875
 876 static unsigned int
 877 tree_ssa_dce_loop (void)
 878 {
 879   unsigned int todo;
 880   todo = perform_tree_ssa_dce (/*aggressive=*/false);
 881   if (todo)
 882     {
 883       free_numbers_of_iterations_estimates ();
 884       scev_reset ();
 885     }
 886   return todo;
 887 }
 888
 889 static unsigned int
 890 tree_ssa_cd_dce (void)
 891 {
 892   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 893 }
 894
 895 static bool
 896 gate_dce (void)
 897 {
 898   return flag_tree_dce != 0;
 899 }
 900
 901 struct tree_opt_pass pass_dce =
 902 {
 903   "dce",                                /* name */
 904   gate_dce,                             /* gate */
 905   tree_ssa_dce,                         /* execute */
 906   NULL,                                 /* sub */
 907   NULL,                                 /* next */
 908   0,                                    /* static_pass_number */
 909   TV_TREE_DCE,                          /* tv_id */
 910   PROP_cfg | PROP_ssa,                  /* properties_required */
 911   0,                                    /* properties_provided */
 912   0,                                    /* properties_destroyed */
 913   0,                                    /* todo_flags_start */
 914   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 915   0                                     /* letter */
 916 };
 917
 918 struct tree_opt_pass pass_dce_loop =
 919 {
 920   "dceloop",                            /* name */
 921   gate_dce,                             /* gate */
 922   tree_ssa_dce_loop,                    /* execute */
 923   NULL,                                 /* sub */
 924   NULL,                                 /* next */
 925   0,                                    /* static_pass_number */
 926   TV_TREE_DCE,                          /* tv_id */
 927   PROP_cfg | PROP_ssa,                  /* properties_required */
 928   0,                                    /* properties_provided */
 929   0,                                    /* properties_destroyed */
 930   0,                                    /* todo_flags_start */
 931   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 932   0                                     /* letter */
 933 };
 934
 935 struct tree_opt_pass pass_cd_dce =
 936 {
 937   "cddce",                              /* name */
 938   gate_dce,                             /* gate */
 939   tree_ssa_cd_dce,                      /* execute */
 940   NULL,                                 /* sub */
 941   NULL,                                 /* next */
 942   0,                                    /* static_pass_number */
 943   TV_TREE_CD_DCE,                       /* tv_id */
 944   PROP_cfg | PROP_ssa,                  /* properties_required */
 945   0,                                    /* properties_provided */
 946   0,                                    /* properties_destroyed */
 947   0,                                    /* todo_flags_start */
 948   TODO_dump_func | TODO_verify_ssa
 949   | TODO_verify_flow,                   /* todo_flags_finish */
 950   0                                     /* letter */
 951 };