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