1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006 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.
7 This file is part of GCC.
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
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
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, 51 Franklin Street, Fifth Floor, Boston, MA
24 /* Dead code elimination.
28 Building an Optimizing Compiler,
29 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
31 Advanced Compiler Design and Implementation,
32 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
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
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. */
48 #include "coretypes.h"
52 /* These RTL headers are needed for basic-block.h. */
55 #include "hard-reg-set.h"
57 #include "basic-block.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"
68 #include "tree-scalar-evolution.h"
70 static struct stmt_stats
78 static VEC(tree
,heap
) *worklist
;
80 /* Vector indicating an SSA name has already been processed and marked
82 static sbitmap processed
;
84 /* Vector indicating that last_stmt if a basic block has already been
85 marked as necessary. */
86 static sbitmap last_stmt_necessary
;
88 /* Before we can determine whether a control branch is dead, we need to
89 compute which blocks are control dependent on which edges.
91 We expect each block to be control dependent on very few edges so we
92 use a bitmap for each block recording its edges. An array holds the
93 bitmap. The Ith bit in the bitmap is set if that block is dependent
95 static bitmap
*control_dependence_map
;
97 /* Vector indicating that a basic block has already had all the edges
98 processed that it is control dependent on. */
99 static sbitmap visited_control_parents
;
101 /* TRUE if this pass alters the CFG (by removing control statements).
104 If this pass alters the CFG, then it will arrange for the dominators
106 static bool cfg_altered
;
108 /* Execute code that follows the macro for each edge (given number
109 EDGE_NUMBER within the CODE) for which the block with index N is
110 control dependent. */
111 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
112 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
116 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
118 set_control_dependence_map_bit (basic_block bb
, int edge_index
)
120 if (bb
== ENTRY_BLOCK_PTR
)
122 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
123 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
126 /* Clear all control dependences for block BB. */
128 clear_control_dependence_bitmap (basic_block bb
)
130 bitmap_clear (control_dependence_map
[bb
->index
]);
134 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
135 This function is necessary because some blocks have negative numbers. */
137 static inline basic_block
138 find_pdom (basic_block block
)
140 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
142 if (block
== EXIT_BLOCK_PTR
)
143 return EXIT_BLOCK_PTR
;
146 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
148 return EXIT_BLOCK_PTR
;
154 /* Determine all blocks' control dependences on the given edge with edge_list
155 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
158 find_control_dependence (struct edge_list
*el
, int edge_index
)
160 basic_block current_block
;
161 basic_block ending_block
;
163 gcc_assert (INDEX_EDGE_PRED_BB (el
, edge_index
) != EXIT_BLOCK_PTR
);
165 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
166 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
168 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (el
, edge_index
));
170 for (current_block
= INDEX_EDGE_SUCC_BB (el
, edge_index
);
171 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
172 current_block
= find_pdom (current_block
))
174 edge e
= INDEX_EDGE (el
, edge_index
);
176 /* For abnormal edges, we don't make current_block control
177 dependent because instructions that throw are always necessary
179 if (e
->flags
& EDGE_ABNORMAL
)
182 set_control_dependence_map_bit (current_block
, edge_index
);
187 /* Record all blocks' control dependences on all edges in the edge
188 list EL, ala Morgan, Section 3.6. */
191 find_all_control_dependences (struct edge_list
*el
)
195 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
196 find_control_dependence (el
, i
);
200 #define NECESSARY(stmt) stmt->base.asm_written_flag
202 /* If STMT is not already marked necessary, mark it, and add it to the
203 worklist if ADD_TO_WORKLIST is true. */
205 mark_stmt_necessary (tree stmt
, bool add_to_worklist
)
208 gcc_assert (!DECL_P (stmt
));
210 if (NECESSARY (stmt
))
213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
215 fprintf (dump_file
, "Marking useful stmt: ");
216 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
217 fprintf (dump_file
, "\n");
220 NECESSARY (stmt
) = 1;
222 VEC_safe_push (tree
, heap
, worklist
, stmt
);
226 /* Mark the statement defining operand OP as necessary. */
229 mark_operand_necessary (tree op
)
236 ver
= SSA_NAME_VERSION (op
);
237 if (TEST_BIT (processed
, ver
))
239 SET_BIT (processed
, ver
);
241 stmt
= SSA_NAME_DEF_STMT (op
);
244 if (NECESSARY (stmt
) || IS_EMPTY_STMT (stmt
))
247 NECESSARY (stmt
) = 1;
248 VEC_safe_push (tree
, heap
, worklist
, stmt
);
252 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
253 it can make other statements necessary.
255 If AGGRESSIVE is false, control statements are conservatively marked as
259 mark_stmt_if_obviously_necessary (tree stmt
, bool aggressive
)
264 /* With non-call exceptions, we have to assume that all statements could
265 throw. If a statement may throw, it is inherently necessary. */
266 if (flag_non_call_exceptions
267 && tree_could_throw_p (stmt
))
269 mark_stmt_necessary (stmt
, true);
273 /* Statements that are implicitly live. Most function calls, asm and return
274 statements are required. Labels and BIND_EXPR nodes are kept because
275 they are control flow, and we have no way of knowing whether they can be
276 removed. DCE can eliminate all the other statements in a block, and CFG
277 can then remove the block and labels. */
278 switch (TREE_CODE (stmt
))
282 case CASE_LABEL_EXPR
:
283 mark_stmt_necessary (stmt
, false);
289 mark_stmt_necessary (stmt
, true);
293 /* Most, but not all function calls are required. Function calls that
294 produce no result and have no side effects (i.e. const pure
295 functions) are unnecessary. */
296 if (TREE_SIDE_EFFECTS (stmt
))
297 mark_stmt_necessary (stmt
, true);
300 case GIMPLE_MODIFY_STMT
:
301 op
= get_call_expr_in (stmt
);
302 if (op
&& TREE_SIDE_EFFECTS (op
))
304 mark_stmt_necessary (stmt
, true);
308 /* These values are mildly magic bits of the EH runtime. We can't
309 see the entire lifetime of these values until landing pads are
311 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == EXC_PTR_EXPR
312 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == FILTER_EXPR
)
314 mark_stmt_necessary (stmt
, true);
320 gcc_assert (!simple_goto_p (stmt
));
321 mark_stmt_necessary (stmt
, true);
325 gcc_assert (EDGE_COUNT (bb_for_stmt (stmt
)->succs
) == 2);
330 mark_stmt_necessary (stmt
, true);
337 ann
= stmt_ann (stmt
);
339 /* If the statement has volatile operands, it needs to be preserved.
340 Same for statements that can alter control flow in unpredictable
342 if (ann
->has_volatile_ops
|| is_ctrl_altering_stmt (stmt
))
344 mark_stmt_necessary (stmt
, true);
348 if (is_hidden_global_store (stmt
))
350 mark_stmt_necessary (stmt
, true);
358 /* Make corresponding control dependent edges necessary. We only
359 have to do this once for each basic block, so we clear the bitmap
362 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
)
365 unsigned edge_number
;
367 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
369 if (bb
== ENTRY_BLOCK_PTR
)
372 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
375 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
377 if (TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
379 SET_BIT (last_stmt_necessary
, cd_bb
->index
);
381 t
= last_stmt (cd_bb
);
382 if (t
&& is_ctrl_stmt (t
))
383 mark_stmt_necessary (t
, true);
388 /* Find obviously necessary statements. These are things like most function
389 calls, and stores to file level variables.
391 If EL is NULL, control statements are conservatively marked as
392 necessary. Otherwise it contains the list of edges used by control
393 dependence analysis. */
396 find_obviously_necessary_stmts (struct edge_list
*el
)
399 block_stmt_iterator i
;
406 /* PHI nodes are never inherently necessary. */
407 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
410 /* Check all statements in the block. */
411 for (i
= bsi_start (bb
); ! bsi_end_p (i
); bsi_next (&i
))
413 tree stmt
= bsi_stmt (i
);
414 NECESSARY (stmt
) = 0;
415 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
421 /* Prevent the loops from being removed. We must keep the infinite loops,
422 and we currently do not have a means to recognize the finite ones. */
426 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
427 if (e
->flags
& EDGE_DFS_BACK
)
428 mark_control_dependent_edges_necessary (e
->dest
, el
);
434 /* Propagate necessity using the operands of necessary statements.
435 Process the uses on each statement in the worklist, and add all
436 feeding statements which contribute to the calculation of this
437 value to the worklist.
439 In conservative mode, EL is NULL. */
442 propagate_necessity (struct edge_list
*el
)
445 bool aggressive
= (el
? true : false);
447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
448 fprintf (dump_file
, "\nProcessing worklist:\n");
450 while (VEC_length (tree
, worklist
) > 0)
452 /* Take STMT from worklist. */
453 stmt
= VEC_pop (tree
, worklist
);
455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
457 fprintf (dump_file
, "processing: ");
458 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
459 fprintf (dump_file
, "\n");
464 /* Mark the last statements of the basic blocks that the block
465 containing STMT is control dependent on, but only if we haven't
467 basic_block bb
= bb_for_stmt (stmt
);
468 if (bb
!= ENTRY_BLOCK_PTR
469 && ! TEST_BIT (visited_control_parents
, bb
->index
))
471 SET_BIT (visited_control_parents
, bb
->index
);
472 mark_control_dependent_edges_necessary (bb
, el
);
476 if (TREE_CODE (stmt
) == PHI_NODE
)
478 /* PHI nodes are somewhat special in that each PHI alternative has
479 data and control dependencies. All the statements feeding the
480 PHI node's arguments are always necessary. In aggressive mode,
481 we also consider the control dependent edges leading to the
482 predecessor block associated with each PHI alternative as
486 for (k
= 0; k
< PHI_NUM_ARGS (stmt
); k
++)
488 tree arg
= PHI_ARG_DEF (stmt
, k
);
489 if (TREE_CODE (arg
) == SSA_NAME
)
490 mark_operand_necessary (arg
);
495 for (k
= 0; k
< PHI_NUM_ARGS (stmt
); k
++)
497 basic_block arg_bb
= PHI_ARG_EDGE (stmt
, k
)->src
;
498 if (arg_bb
!= ENTRY_BLOCK_PTR
499 && ! TEST_BIT (visited_control_parents
, arg_bb
->index
))
501 SET_BIT (visited_control_parents
, arg_bb
->index
);
502 mark_control_dependent_edges_necessary (arg_bb
, el
);
509 /* Propagate through the operands. Examine all the USE, VUSE and
510 VDEF operands in this statement. Mark all the statements
511 which feed this statement's uses as necessary. The
512 operands of VDEF expressions are also needed as they
513 represent potential definitions that may reach this
514 statement (VDEF operands allow us to follow def-def
519 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_ALL_USES
)
520 mark_operand_necessary (use
);
526 /* Remove dead PHI nodes from block BB. */
529 remove_dead_phis (basic_block bb
)
534 phi
= phi_nodes (bb
);
539 if (! NECESSARY (phi
))
541 tree next
= PHI_CHAIN (phi
);
543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
545 fprintf (dump_file
, "Deleting : ");
546 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
547 fprintf (dump_file
, "\n");
550 remove_phi_node (phi
, prev
, true);
551 stats
.removed_phis
++;
557 phi
= PHI_CHAIN (phi
);
563 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
564 containing I so that we don't have to look it up. */
567 remove_dead_stmt (block_stmt_iterator
*i
, basic_block bb
)
569 tree t
= bsi_stmt (*i
);
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "Deleting : ");
574 print_generic_stmt (dump_file
, t
, TDF_SLIM
);
575 fprintf (dump_file
, "\n");
580 /* If we have determined that a conditional branch statement contributes
581 nothing to the program, then we not only remove it, but we also change
582 the flow graph so that the current block will simply fall-thru to its
583 immediate post-dominator. The blocks we are circumventing will be
584 removed by cleanup_tree_cfg if this change in the flow graph makes them
586 if (is_ctrl_stmt (t
))
588 basic_block post_dom_bb
;
590 /* The post dominance info has to be up-to-date. */
591 gcc_assert (dom_computed
[CDI_POST_DOMINATORS
] == DOM_OK
);
592 /* Get the immediate post dominator of bb. */
593 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
595 /* There are three particularly problematical cases.
597 1. Blocks that do not have an immediate post dominator. This
598 can happen with infinite loops.
600 2. Blocks that are only post dominated by the exit block. These
601 can also happen for infinite loops as we create fake edges
602 in the dominator tree.
604 3. If the post dominator has PHI nodes we may be able to compute
605 the right PHI args for them.
608 In each of these cases we must remove the control statement
609 as it may reference SSA_NAMEs which are going to be removed and
610 we remove all but one outgoing edge from the block. */
612 || post_dom_bb
== EXIT_BLOCK_PTR
613 || phi_nodes (post_dom_bb
))
617 /* Redirect the first edge out of BB to reach POST_DOM_BB. */
618 redirect_edge_and_branch (EDGE_SUCC (bb
, 0), post_dom_bb
);
619 PENDING_STMT (EDGE_SUCC (bb
, 0)) = NULL
;
621 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
622 EDGE_SUCC (bb
, 0)->count
= bb
->count
;
624 /* The edge is no longer associated with a conditional, so it does
625 not have TRUE/FALSE flags. */
626 EDGE_SUCC (bb
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
628 /* The lone outgoing edge from BB will be a fallthru edge. */
629 EDGE_SUCC (bb
, 0)->flags
|= EDGE_FALLTHRU
;
631 /* Remove the remaining the outgoing edges. */
632 while (!single_succ_p (bb
))
634 /* FIXME. When we remove the edge, we modify the CFG, which
635 in turn modifies the dominator and post-dominator tree.
636 Is it safe to postpone recomputing the dominator and
637 post-dominator tree until the end of this pass given that
638 the post-dominators are used above? */
640 remove_edge (EDGE_SUCC (bb
, 1));
644 bsi_remove (i
, true);
649 /* Eliminate unnecessary statements. Any instruction not marked as necessary
650 contributes nothing to the program, and can be deleted. */
653 eliminate_unnecessary_stmts (void)
656 block_stmt_iterator i
;
658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
659 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
661 clear_special_calls ();
664 /* Remove dead PHI nodes. */
665 remove_dead_phis (bb
);
670 /* Remove dead statements. */
671 for (i
= bsi_start (bb
); ! bsi_end_p (i
) ; )
673 tree t
= bsi_stmt (i
);
677 /* If `i' is not necessary then remove it. */
679 remove_dead_stmt (&i
, bb
);
682 tree call
= get_call_expr_in (t
);
684 notice_special_calls (call
);
692 /* Print out removed statement statistics. */
697 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
701 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
702 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
703 stats
.removed
, stats
.total
, (int) percg
);
705 if (stats
.total_phis
== 0)
708 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
710 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
711 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
715 /* Initialization for this pass. Set up the used data structures. */
718 tree_dce_init (bool aggressive
)
720 memset ((void *) &stats
, 0, sizeof (stats
));
726 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
727 for (i
= 0; i
< last_basic_block
; ++i
)
728 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
730 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
731 sbitmap_zero (last_stmt_necessary
);
734 processed
= sbitmap_alloc (num_ssa_names
+ 1);
735 sbitmap_zero (processed
);
737 worklist
= VEC_alloc (tree
, heap
, 64);
741 /* Cleanup after this pass. */
744 tree_dce_done (bool aggressive
)
750 for (i
= 0; i
< last_basic_block
; ++i
)
751 BITMAP_FREE (control_dependence_map
[i
]);
752 free (control_dependence_map
);
754 sbitmap_free (visited_control_parents
);
755 sbitmap_free (last_stmt_necessary
);
758 sbitmap_free (processed
);
760 VEC_free (tree
, heap
, worklist
);
763 /* Main routine to eliminate dead code.
765 AGGRESSIVE controls the aggressiveness of the algorithm.
766 In conservative mode, we ignore control dependence and simply declare
767 all but the most trivially dead branches necessary. This mode is fast.
768 In aggressive mode, control dependences are taken into account, which
769 results in more dead code elimination, but at the cost of some time.
771 FIXME: Aggressive mode before PRE doesn't work currently because
772 the dominance info is not invalidated after DCE1. This is
773 not an issue right now because we only run aggressive DCE
774 as the last tree SSA pass, but keep this in mind when you
775 start experimenting with pass ordering. */
778 perform_tree_ssa_dce (bool aggressive
)
780 struct edge_list
*el
= NULL
;
782 tree_dce_init (aggressive
);
786 /* Compute control dependence. */
787 timevar_push (TV_CONTROL_DEPENDENCES
);
788 calculate_dominance_info (CDI_POST_DOMINATORS
);
789 el
= create_edge_list ();
790 find_all_control_dependences (el
);
791 timevar_pop (TV_CONTROL_DEPENDENCES
);
793 visited_control_parents
= sbitmap_alloc (last_basic_block
);
794 sbitmap_zero (visited_control_parents
);
796 mark_dfs_back_edges ();
799 find_obviously_necessary_stmts (el
);
801 propagate_necessity (el
);
803 eliminate_unnecessary_stmts ();
806 free_dominance_info (CDI_POST_DOMINATORS
);
808 /* If we removed paths in the CFG, then we need to update
809 dominators as well. I haven't investigated the possibility
810 of incrementally updating dominators. */
812 free_dominance_info (CDI_DOMINATORS
);
814 /* Debugging dumps. */
818 tree_dce_done (aggressive
);
823 /* Pass entry points. */
827 perform_tree_ssa_dce (/*aggressive=*/false);
832 tree_ssa_dce_loop (void)
834 perform_tree_ssa_dce (/*aggressive=*/false);
835 free_numbers_of_iterations_estimates ();
841 tree_ssa_cd_dce (void)
843 perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
850 return flag_tree_dce
!= 0;
853 struct tree_opt_pass pass_dce
=
857 tree_ssa_dce
, /* execute */
860 0, /* static_pass_number */
861 TV_TREE_DCE
, /* tv_id */
862 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
863 0, /* properties_provided */
864 0, /* properties_destroyed */
865 0, /* todo_flags_start */
871 | TODO_remove_unused_locals
, /* todo_flags_finish */
875 struct tree_opt_pass pass_dce_loop
=
877 "dceloop", /* name */
879 tree_ssa_dce_loop
, /* execute */
882 0, /* static_pass_number */
883 TV_TREE_DCE
, /* tv_id */
884 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
885 0, /* properties_provided */
886 0, /* properties_destroyed */
887 0, /* todo_flags_start */
891 | TODO_verify_ssa
, /* todo_flags_finish */
895 struct tree_opt_pass pass_cd_dce
=
899 tree_ssa_cd_dce
, /* execute */
902 0, /* static_pass_number */
903 TV_TREE_CD_DCE
, /* tv_id */
904 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
905 0, /* properties_provided */
906 0, /* properties_destroyed */
907 0, /* todo_flags_start */
913 | TODO_verify_flow
, /* todo_flags_finish */