gcc/tree-ssa-dce.c

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