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