gcc/tree-ssa-dce.c

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