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