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       /* Remove dead statements.  */
 642       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
 643         {
 644          tree t = bsi_stmt (i);
 645
 646          stats.total++;
 647
 648          /* If `i' is not necessary then remove it.  */
 649          if (! NECESSARY (t))
 650            remove_dead_stmt (&i, bb);
 651          else
 652            {
 653              tree call = get_call_expr_in (t);
 654              if (call)
 655                notice_special_calls (call);
 656              bsi_next (&i);
 657            }
 658         }
 659     }
 660  }
 661 \f
 662 /* Remove dead PHI nodes from block BB.  */
 663
 664 static void
 665 remove_dead_phis (basic_block bb)
 666 {
 667   tree prev, phi;
 668
 669   prev = NULL_TREE;
 670   phi = phi_nodes (bb);
 671   while (phi)
 672     {
 673       stats.total_phis++;
 674
 675       if (! NECESSARY (phi))
 676         {
 677           tree next = PHI_CHAIN (phi);
 678
 679           if (dump_file && (dump_flags & TDF_DETAILS))
 680             {
 681               fprintf (dump_file, "Deleting : ");
 682               print_generic_stmt (dump_file, phi, TDF_SLIM);
 683               fprintf (dump_file, "\n");
 684             }
 685
 686           remove_phi_node (phi, prev);
 687           stats.removed_phis++;
 688           phi = next;
 689         }
 690       else
 691         {
 692           prev = phi;
 693           phi = PHI_CHAIN (phi);
 694         }
 695     }
 696 }
 697 \f
 698 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
 699    containing I so that we don't have to look it up.  */
 700
 701 static void
 702 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 703 {
 704   tree t = bsi_stmt (*i);
 705   def_operand_p def_p;
 706
 707   ssa_op_iter iter;
 708
 709   if (dump_file && (dump_flags & TDF_DETAILS))
 710     {
 711       fprintf (dump_file, "Deleting : ");
 712       print_generic_stmt (dump_file, t, TDF_SLIM);
 713       fprintf (dump_file, "\n");
 714     }
 715
 716   stats.removed++;
 717
 718   /* If we have determined that a conditional branch statement contributes
 719      nothing to the program, then we not only remove it, but we also change
 720      the flow graph so that the current block will simply fall-thru to its
 721      immediate post-dominator.  The blocks we are circumventing will be
 722      removed by cleaup_cfg if this change in the flow graph makes them
 723      unreachable.  */
 724   if (is_ctrl_stmt (t))
 725     {
 726       basic_block post_dom_bb;
 727       /* The post dominance info has to be up-to-date.  */
 728       gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
 729       /* Get the immediate post dominator of bb.  */
 730       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 731       /* Some blocks don't have an immediate post dominator.  This can happen
 732          for example with infinite loops.  Removing an infinite loop is an
 733          inappropriate transformation anyway...  */
 734       if (! post_dom_bb)
 735         {
 736           bsi_next (i);
 737           return;
 738         }
 739
 740       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
 741       redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
 742       PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
 743       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 744       EDGE_SUCC (bb, 0)->count = bb->count;
 745
 746       /* The edge is no longer associated with a conditional, so it does
 747          not have TRUE/FALSE flags.  */
 748       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 749
 750       /* If the edge reaches any block other than the exit, then it is a
 751          fallthru edge; if it reaches the exit, then it is not a fallthru
 752          edge.  */
 753       if (post_dom_bb != EXIT_BLOCK_PTR)
 754         EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 755       else
 756         EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
 757
 758       /* Remove the remaining the outgoing edges.  */
 759       while (!single_succ_p (bb))
 760         remove_edge (EDGE_SUCC (bb, 1));
 761     }
 762
 763   FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter,
 764                             SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS)
 765     {
 766       tree def = DEF_FROM_PTR (def_p);
 767       bitmap_set_bit (vars_to_rename,
 768                       var_ann (SSA_NAME_VAR (def))->uid);
 769     }
 770   bsi_remove (i);
 771   release_defs (t);
 772 }
 773 \f
 774 /* Print out removed statement statistics.  */
 775
 776 static void
 777 print_stats (void)
 778 {
 779   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
 780     {
 781       float percg;
 782
 783       percg = ((float) stats.removed / (float) stats.total) * 100;
 784       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
 785                stats.removed, stats.total, (int) percg);
 786
 787       if (stats.total_phis == 0)
 788         percg = 0;
 789       else
 790         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
 791
 792       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
 793                stats.removed_phis, stats.total_phis, (int) percg);
 794     }
 795 }
 796 \f
 797 /* Initialization for this pass.  Set up the used data structures.  */
 798
 799 static void
 800 tree_dce_init (bool aggressive)
 801 {
 802   memset ((void *) &stats, 0, sizeof (stats));
 803
 804   if (aggressive)
 805     {
 806       int i;
 807
 808       control_dependence_map
 809         = xmalloc (last_basic_block * sizeof (bitmap));
 810       for (i = 0; i < last_basic_block; ++i)
 811         control_dependence_map[i] = BITMAP_ALLOC (NULL);
 812
 813       last_stmt_necessary = sbitmap_alloc (last_basic_block);
 814       sbitmap_zero (last_stmt_necessary);
 815     }
 816
 817   processed = sbitmap_alloc (num_ssa_names + 1);
 818   sbitmap_zero (processed);
 819
 820   VARRAY_TREE_INIT (worklist, 64, "work list");
 821 }
 822
 823 /* Cleanup after this pass.  */
 824
 825 static void
 826 tree_dce_done (bool aggressive)
 827 {
 828   if (aggressive)
 829     {
 830       int i;
 831
 832       for (i = 0; i < last_basic_block; ++i)
 833         BITMAP_FREE (control_dependence_map[i]);
 834       free (control_dependence_map);
 835
 836       sbitmap_free (visited_control_parents);
 837       sbitmap_free (last_stmt_necessary);
 838     }
 839
 840   sbitmap_free (processed);
 841 }
 842 \f
 843 /* Main routine to eliminate dead code.
 844
 845    AGGRESSIVE controls the aggressiveness of the algorithm.
 846    In conservative mode, we ignore control dependence and simply declare
 847    all but the most trivially dead branches necessary.  This mode is fast.
 848    In aggressive mode, control dependences are taken into account, which
 849    results in more dead code elimination, but at the cost of some time.
 850
 851    FIXME: Aggressive mode before PRE doesn't work currently because
 852           the dominance info is not invalidated after DCE1.  This is
 853           not an issue right now because we only run aggressive DCE
 854           as the last tree SSA pass, but keep this in mind when you
 855           start experimenting with pass ordering.  */
 856
 857 static void
 858 perform_tree_ssa_dce (bool aggressive)
 859 {
 860   struct edge_list *el = NULL;
 861
 862   tree_dce_init (aggressive);
 863
 864   if (aggressive)
 865     {
 866       /* Compute control dependence.  */
 867       timevar_push (TV_CONTROL_DEPENDENCES);
 868       calculate_dominance_info (CDI_POST_DOMINATORS);
 869       el = create_edge_list ();
 870       find_all_control_dependences (el);
 871       timevar_pop (TV_CONTROL_DEPENDENCES);
 872
 873       visited_control_parents = sbitmap_alloc (last_basic_block);
 874       sbitmap_zero (visited_control_parents);
 875
 876       mark_dfs_back_edges ();
 877     }
 878
 879   find_obviously_necessary_stmts (el);
 880
 881   propagate_necessity (el);
 882
 883   mark_really_necessary_kill_operand_phis ();
 884   eliminate_unnecessary_stmts ();
 885
 886   if (aggressive)
 887     free_dominance_info (CDI_POST_DOMINATORS);
 888
 889   /* Debugging dumps.  */
 890   if (dump_file)
 891     print_stats ();
 892
 893   tree_dce_done (aggressive);
 894
 895   free_edge_list (el);
 896 }
 897
 898 /* Pass entry points.  */
 899 static void
 900 tree_ssa_dce (void)
 901 {
 902   perform_tree_ssa_dce (/*aggressive=*/false);
 903 }
 904
 905 static void
 906 tree_ssa_cd_dce (void)
 907 {
 908   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
 909 }
 910
 911 static bool
 912 gate_dce (void)
 913 {
 914   return flag_tree_dce != 0;
 915 }
 916
 917 struct tree_opt_pass pass_dce =
 918 {
 919   "dce",                                /* name */
 920   gate_dce,                             /* gate */
 921   tree_ssa_dce,                         /* execute */
 922   NULL,                                 /* sub */
 923   NULL,                                 /* next */
 924   0,                                    /* static_pass_number */
 925   TV_TREE_DCE,                          /* tv_id */
 926   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 927   0,                                    /* properties_provided */
 928   0,                                    /* properties_destroyed */
 929   0,                                    /* todo_flags_start */
 930   TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa,     /* todo_flags_finish */
 931   0                                     /* letter */
 932 };
 933
 934 struct tree_opt_pass pass_cd_dce =
 935 {
 936   "cddce",                              /* name */
 937   gate_dce,                             /* gate */
 938   tree_ssa_cd_dce,                      /* execute */
 939   NULL,                                 /* sub */
 940   NULL,                                 /* next */
 941   0,                                    /* static_pass_number */
 942   TV_TREE_CD_DCE,                       /* tv_id */
 943   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 944   0,                                    /* properties_provided */
 945   0,                                    /* properties_destroyed */
 946   0,                                    /* todo_flags_start */
 947   TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
 948                                         /* todo_flags_finish */
 949   0                                     /* letter */
 950 };
 951