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