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 void
 529 remove_dead_phis (basic_block bb)
 530 {
 531   tree prev, phi;
 532
 533   prev = NULL_TREE;
 534   phi = phi_nodes (bb);
 535   while (phi)
 536     {
 537       stats.total_phis++;
 538
 539       if (! NECESSARY (phi))
 540         {
 541           tree next = PHI_CHAIN (phi);
 542
 543           if (dump_file && (dump_flags & TDF_DETAILS))
 544             {
 545               fprintf (dump_file, "Deleting : ");
 546               print_generic_stmt (dump_file, phi, TDF_SLIM);
 547               fprintf (dump_file, "\n");
 548             }
 549
 550           remove_phi_node (phi, prev, true);
 551           stats.removed_phis++;
 552           phi = next;
 553         }
 554       else
 555         {
 556           prev = phi;
 557           phi = PHI_CHAIN (phi);
 558         }
 559     }
 560 }
 561
 562
 563 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
 564    containing I so that we don't have to look it up.  */
 565
 566 static void
 567 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 568 {
 569   tree t = bsi_stmt (*i);
 570
 571   if (dump_file && (dump_flags & TDF_DETAILS))
 572     {
 573       fprintf (dump_file, "Deleting : ");
 574       print_generic_stmt (dump_file, t, TDF_SLIM);
 575       fprintf (dump_file, "\n");
 576     }
 577
 578   stats.removed++;
 579
 580   /* If we have determined that a conditional branch statement contributes
 581      nothing to the program, then we not only remove it, but we also change
 582      the flow graph so that the current block will simply fall-thru to its
 583      immediate post-dominator.  The blocks we are circumventing will be
 584      removed by cleanup_tree_cfg if this change in the flow graph makes them
 585      unreachable.  */
 586   if (is_ctrl_stmt (t))
 587     {
 588       basic_block post_dom_bb;
 589
 590       /* The post dominance info has to be up-to-date.  */
 591       gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
 592       /* Get the immediate post dominator of bb.  */
 593       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 594
 595       /* There are three particularly problematical cases.
 596
 597          1. Blocks that do not have an immediate post dominator.  This
 598             can happen with infinite loops.
 599
 600          2. Blocks that are only post dominated by the exit block.  These
 601             can also happen for infinite loops as we create fake edges
 602             in the dominator tree.
 603
 604          3. If the post dominator has PHI nodes we may be able to compute
 605             the right PHI args for them.
 606
 607
 608          In each of these cases we must remove the control statement
 609          as it may reference SSA_NAMEs which are going to be removed and
 610          we remove all but one outgoing edge from the block.  */
 611       if (! post_dom_bb
 612           || post_dom_bb == EXIT_BLOCK_PTR
 613           || phi_nodes (post_dom_bb))
 614         ;
 615       else
 616         {
 617           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 618           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 619           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 620         }
 621       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 622       EDGE_SUCC (bb, 0)->count = bb->count;
 623
 624       /* The edge is no longer associated with a conditional, so it does
 625          not have TRUE/FALSE flags.  */
 626       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 627
 628       /* The lone outgoing edge from BB will be a fallthru edge.  */
 629       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 630
 631       /* Remove the remaining the outgoing edges.  */
 632       while (!single_succ_p (bb))
 633         {
 634           /* FIXME.  When we remove the edge, we modify the CFG, which
 635              in turn modifies the dominator and post-dominator tree.
 636              Is it safe to postpone recomputing the dominator and
 637              post-dominator tree until the end of this pass given that
 638              the post-dominators are used above?  */
 639           cfg_altered = true;
 640           remove_edge (EDGE_SUCC (bb, 1));
 641         }
 642     }
 643
 644   bsi_remove (i, true);
 645   release_defs (t);
 646 }
 647
 648
 649 /* Eliminate unnecessary statements. Any instruction not marked as necessary
 650    contributes nothing to the program, and can be deleted.  */
 651
 652 static void
 653 eliminate_unnecessary_stmts (void)
 654 {
 655   basic_block bb;
 656   block_stmt_iterator i;
 657
 658   if (dump_file && (dump_flags & TDF_DETAILS))
 659     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 660
 661   clear_special_calls ();
 662   FOR_EACH_BB (bb)
 663     {
 664       /* Remove dead PHI nodes.  */
 665       remove_dead_phis (bb);
 666     }
 667
 668   FOR_EACH_BB (bb)
 669     {
 670       /* Remove dead statements.  */
 671       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 672         {
 673           tree t = bsi_stmt (i);
 674
 675           stats.total++;
 676
 677           /* If `i' is not necessary then remove it.  */
 678           if (! NECESSARY (t))
 679             remove_dead_stmt (&i, bb);
 680           else
 681             {
 682               tree call = get_call_expr_in (t);
 683               if (call)
 684                 notice_special_calls (call);
 685               bsi_next (&i);
 686             }
 687         }
 688     }
 689 }
 690
 691
 692 /* Print out removed statement statistics.  */
 693
 694 static void
 695 print_stats (void)
 696 {
 697   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 698     {
 699       float percg;
 700
 701       percg = ((float) stats.removed / (float) stats.total) * 100;
 702       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 703                stats.removed, stats.total, (int) percg);
 704
 705       if (stats.total_phis == 0)
 706         percg = 0;
 707       else
 708         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 709
 710       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 711                stats.removed_phis, stats.total_phis, (int) percg);
 712     }
 713 }
 714 \f
 715 /* Initialization for this pass.  Set up the used data structures.  */
 716
 717 static void
 718 tree_dce_init (bool aggressive)
 719 {
 720   memset ((void *) &stats, 0, sizeof (stats));
 721
 722   if (aggressive)
 723     {
 724       int i;
 725
 726       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
 727       for (i = 0; i < last_basic_block; ++i)
 728         control_dependence_map[i] = BITMAP_ALLOC (NULL);
 729
 730       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 731       sbitmap_zero (last_stmt_necessary);
 732     }
 733
 734   processed = sbitmap_alloc (num_ssa_names + 1);
 735   sbitmap_zero (processed);
 736
 737   worklist = VEC_alloc (tree, heap, 64);
 738   cfg_altered = false;
 739 }
 740
 741 /* Cleanup after this pass.  */
 742
 743 static void
 744 tree_dce_done (bool aggressive)
 745 {
 746   if (aggressive)
 747     {
 748       int i;
 749
 750       for (i = 0; i < last_basic_block; ++i)
 751         BITMAP_FREE (control_dependence_map[i]);
 752       free (control_dependence_map);
 753
 754       sbitmap_free (visited_control_parents);
 755       sbitmap_free (last_stmt_necessary);
 756     }
 757
 758   sbitmap_free (processed);
 759
 760   VEC_free (tree, heap, worklist);
 761 }
 762 \f
 763 /* Main routine to eliminate dead code.
 764
 765    AGGRESSIVE controls the aggressiveness of the algorithm.
 766    In conservative mode, we ignore control dependence and simply declare
 767    all but the most trivially dead branches necessary.  This mode is fast.
 768    In aggressive mode, control dependences are taken into account, which
 769    results in more dead code elimination, but at the cost of some time.
 770
 771    FIXME: Aggressive mode before PRE doesn't work currently because
 772           the dominance info is not invalidated after DCE1.  This is
 773           not an issue right now because we only run aggressive DCE
 774           as the last tree SSA pass, but keep this in mind when you
 775           start experimenting with pass ordering.  */
 776
 777 static void
 778 perform_tree_ssa_dce (bool aggressive)
 779 {
 780   struct edge_list *el = NULL;
 781
 782   tree_dce_init (aggressive);
 783
 784   if (aggressive)
 785     {
 786       /* Compute control dependence.  */
 787       timevar_push (TV_CONTROL_DEPENDENCES);
 788       calculate_dominance_info (CDI_POST_DOMINATORS);
 789       el = create_edge_list ();
 790       find_all_control_dependences (el);
 791       timevar_pop (TV_CONTROL_DEPENDENCES);
 792
 793       visited_control_parents = sbitmap_alloc (last_basic_block);
 794       sbitmap_zero (visited_control_parents);
 795
 796       mark_dfs_back_edges ();
 797     }
 798
 799   find_obviously_necessary_stmts (el);
 800
 801   propagate_necessity (el);
 802
 803   eliminate_unnecessary_stmts ();
 804
 805   if (aggressive)
 806     free_dominance_info (CDI_POST_DOMINATORS);
 807
 808   /* If we removed paths in the CFG, then we need to update
 809      dominators as well.  I haven't investigated the possibility
 810      of incrementally updating dominators.  */
 811   if (cfg_altered)
 812     free_dominance_info (CDI_DOMINATORS);
 813
 814   /* Debugging dumps.  */
 815   if (dump_file)
 816     print_stats ();
 817
 818   tree_dce_done (aggressive);
 819
 820   free_edge_list (el);
 821 }
 822
 823 /* Pass entry points.  */
 824 static unsigned int
 825 tree_ssa_dce (void)
 826 {
 827   perform_tree_ssa_dce (/*aggressive=*/false);
 828   return 0;
 829 }
 830
 831 static unsigned int
 832 tree_ssa_dce_loop (void)
 833 {
 834   perform_tree_ssa_dce (/*aggressive=*/false);
 835   free_numbers_of_iterations_estimates ();
 836   scev_reset ();
 837   return 0;
 838 }
 839
 840 static unsigned int
 841 tree_ssa_cd_dce (void)
 842 {
 843   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 844   return 0;
 845 }
 846
 847 static bool
 848 gate_dce (void)
 849 {
 850   return flag_tree_dce != 0;
 851 }
 852
 853 struct tree_opt_pass pass_dce =
 854 {
 855   "dce",                                /* name */
 856   gate_dce,                             /* gate */
 857   tree_ssa_dce,                         /* execute */
 858   NULL,                                 /* sub */
 859   NULL,                                 /* next */
 860   0,                                    /* static_pass_number */
 861   TV_TREE_DCE,                          /* tv_id */
 862   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 863   0,                                    /* properties_provided */
 864   0,                                    /* properties_destroyed */
 865   0,                                    /* todo_flags_start */
 866   TODO_dump_func
 867     | TODO_update_ssa
 868     | TODO_cleanup_cfg
 869     | TODO_ggc_collect
 870     | TODO_verify_ssa
 871     | TODO_remove_unused_locals,        /* todo_flags_finish */
 872   0                                     /* letter */
 873 };
 874
 875 struct tree_opt_pass pass_dce_loop =
 876 {
 877   "dceloop",                            /* name */
 878   gate_dce,                             /* gate */
 879   tree_ssa_dce_loop,                    /* execute */
 880   NULL,                                 /* sub */
 881   NULL,                                 /* next */
 882   0,                                    /* static_pass_number */
 883   TV_TREE_DCE,                          /* tv_id */
 884   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 885   0,                                    /* properties_provided */
 886   0,                                    /* properties_destroyed */
 887   0,                                    /* todo_flags_start */
 888   TODO_dump_func
 889     | TODO_update_ssa
 890     | TODO_cleanup_cfg
 891     | TODO_verify_ssa,                  /* todo_flags_finish */
 892   0                                     /* letter */
 893 };
 894
 895 struct tree_opt_pass pass_cd_dce =
 896 {
 897   "cddce",                              /* name */
 898   gate_dce,                             /* gate */
 899   tree_ssa_cd_dce,                      /* execute */
 900   NULL,                                 /* sub */
 901   NULL,                                 /* next */
 902   0,                                    /* static_pass_number */
 903   TV_TREE_CD_DCE,                       /* tv_id */
 904   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 905   0,                                    /* properties_provided */
 906   0,                                    /* properties_destroyed */
 907   0,                                    /* todo_flags_start */
 908   TODO_dump_func
 909     | TODO_update_ssa
 910     | TODO_cleanup_cfg
 911     | TODO_ggc_collect
 912     | TODO_verify_ssa
 913     | TODO_verify_flow,                 /* todo_flags_finish */
 914   0                                     /* letter */
 915 };