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