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