gcc/tree-ssa-dce.c

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