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