1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Ben Elliston <bje@redhat.com>
5 and Andrew MacLeod <amacleod@redhat.com>
6 Adapted to use control dependence by Steven Bosscher, SUSE Labs.
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 3, or (at your option) any
15 GCC is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
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 #include "tree-pretty-print.h"
53 #include "gimple-pretty-print.h"
54 #include "basic-block.h"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
62 #include "tree-scalar-evolution.h"
64 static struct stmt_stats
72 #define STMT_NECESSARY GF_PLF_1
74 static VEC(gimple
,heap
) *worklist
;
76 /* Vector indicating an SSA name has already been processed and marked
78 static sbitmap processed
;
80 /* Vector indicating that the last statement of a basic block has already
81 been marked as necessary. */
82 static sbitmap last_stmt_necessary
;
84 /* Vector indicating that BB contains statements that are live. */
85 static sbitmap bb_contains_live_stmts
;
87 /* Before we can determine whether a control branch is dead, we need to
88 compute which blocks are control dependent on which edges.
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
94 static bitmap
*control_dependence_map
;
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
;
100 /* TRUE if this pass alters the CFG (by removing control statements).
103 If this pass alters the CFG, then it will arrange for the dominators
105 static bool cfg_altered
;
107 /* Execute code that follows the macro for each edge (given number
108 EDGE_NUMBER within the CODE) for which the block with index N is
109 control dependent. */
110 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
111 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
115 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
117 set_control_dependence_map_bit (basic_block bb
, int edge_index
)
119 if (bb
== ENTRY_BLOCK_PTR
)
121 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
122 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
125 /* Clear all control dependences for block BB. */
127 clear_control_dependence_bitmap (basic_block bb
)
129 bitmap_clear (control_dependence_map
[bb
->index
]);
133 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
134 This function is necessary because some blocks have negative numbers. */
136 static inline basic_block
137 find_pdom (basic_block block
)
139 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
141 if (block
== EXIT_BLOCK_PTR
)
142 return EXIT_BLOCK_PTR
;
145 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
147 return EXIT_BLOCK_PTR
;
153 /* Determine all blocks' control dependences on the given edge with edge_list
154 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
157 find_control_dependence (struct edge_list
*el
, int edge_index
)
159 basic_block current_block
;
160 basic_block ending_block
;
162 gcc_assert (INDEX_EDGE_PRED_BB (el
, edge_index
) != EXIT_BLOCK_PTR
);
164 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
165 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
167 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (el
, edge_index
));
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
))
173 edge e
= INDEX_EDGE (el
, edge_index
);
175 /* For abnormal edges, we don't make current_block control
176 dependent because instructions that throw are always necessary
178 if (e
->flags
& EDGE_ABNORMAL
)
181 set_control_dependence_map_bit (current_block
, edge_index
);
186 /* Record all blocks' control dependences on all edges in the edge
187 list EL, ala Morgan, Section 3.6. */
190 find_all_control_dependences (struct edge_list
*el
)
194 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
195 find_control_dependence (el
, i
);
198 /* If STMT is not already marked necessary, mark it, and add it to the
199 worklist if ADD_TO_WORKLIST is true. */
202 mark_stmt_necessary (gimple stmt
, bool add_to_worklist
)
206 if (gimple_plf (stmt
, STMT_NECESSARY
))
209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
211 fprintf (dump_file
, "Marking useful stmt: ");
212 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
213 fprintf (dump_file
, "\n");
216 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
218 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
219 if (bb_contains_live_stmts
&& !is_gimple_debug (stmt
))
220 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
224 /* Mark the statement defining operand OP as necessary. */
227 mark_operand_necessary (tree op
)
234 ver
= SSA_NAME_VERSION (op
);
235 if (TEST_BIT (processed
, ver
))
237 stmt
= SSA_NAME_DEF_STMT (op
);
238 gcc_assert (gimple_nop_p (stmt
)
239 || gimple_plf (stmt
, STMT_NECESSARY
));
242 SET_BIT (processed
, ver
);
244 stmt
= SSA_NAME_DEF_STMT (op
);
247 if (gimple_plf (stmt
, STMT_NECESSARY
) || gimple_nop_p (stmt
))
250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
252 fprintf (dump_file
, "marking necessary through ");
253 print_generic_expr (dump_file
, op
, 0);
254 fprintf (dump_file
, " stmt ");
255 print_gimple_stmt (dump_file
, stmt
, 0, 0);
258 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
259 if (bb_contains_live_stmts
)
260 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
261 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
265 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
266 it can make other statements necessary.
268 If AGGRESSIVE is false, control statements are conservatively marked as
272 mark_stmt_if_obviously_necessary (gimple stmt
, bool aggressive
)
274 tree lhs
= NULL_TREE
;
276 /* With non-call exceptions, we have to assume that all statements could
277 throw. If a statement may throw, it is inherently necessary. */
278 if (cfun
->can_throw_non_call_exceptions
&& stmt_could_throw_p (stmt
))
280 mark_stmt_necessary (stmt
, true);
284 /* Statements that are implicitly live. Most function calls, asm
285 and return statements are required. Labels and GIMPLE_BIND nodes
286 are kept because they are control flow, and we have no way of
287 knowing whether they can be removed. DCE can eliminate all the
288 other statements in a block, and CFG can then remove the block
290 switch (gimple_code (stmt
))
294 mark_stmt_necessary (stmt
, false);
300 mark_stmt_necessary (stmt
, true);
304 /* Most, but not all function calls are required. Function calls that
305 produce no result and have no side effects (i.e. const pure
306 functions) are unnecessary. */
307 if (gimple_has_side_effects (stmt
))
309 mark_stmt_necessary (stmt
, true);
312 if (!gimple_call_lhs (stmt
))
314 lhs
= gimple_call_lhs (stmt
);
319 lhs
= gimple_assign_lhs (stmt
);
323 /* Debug temps without a value are not useful. ??? If we could
324 easily locate the debug temp bind stmt for a use thereof,
325 would could refrain from marking all debug temps here, and
326 mark them only if they're used. */
327 if (gimple_debug_bind_has_value_p (stmt
)
328 || TREE_CODE (gimple_debug_bind_get_var (stmt
)) != DEBUG_EXPR_DECL
)
329 mark_stmt_necessary (stmt
, false);
333 gcc_assert (!simple_goto_p (stmt
));
334 mark_stmt_necessary (stmt
, true);
338 gcc_assert (EDGE_COUNT (gimple_bb (stmt
)->succs
) == 2);
343 mark_stmt_necessary (stmt
, true);
350 /* If the statement has volatile operands, it needs to be preserved.
351 Same for statements that can alter control flow in unpredictable
353 if (gimple_has_volatile_ops (stmt
) || is_ctrl_altering_stmt (stmt
))
355 mark_stmt_necessary (stmt
, true);
359 if (is_hidden_global_store (stmt
))
361 mark_stmt_necessary (stmt
, true);
369 /* Mark the last statement of BB as necessary. */
372 mark_last_stmt_necessary (basic_block bb
)
374 gimple stmt
= last_stmt (bb
);
376 SET_BIT (last_stmt_necessary
, bb
->index
);
377 SET_BIT (bb_contains_live_stmts
, bb
->index
);
379 /* We actually mark the statement only if it is a control statement. */
380 if (stmt
&& is_ctrl_stmt (stmt
))
381 mark_stmt_necessary (stmt
, true);
385 /* Mark control dependent edges of BB as necessary. We have to do this only
386 once for each basic block so we set the appropriate bit after we're done.
388 When IGNORE_SELF is true, ignore BB in the list of control dependences. */
391 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
,
395 unsigned edge_number
;
396 bool skipped
= false;
398 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
400 if (bb
== ENTRY_BLOCK_PTR
)
403 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
405 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
407 if (ignore_self
&& cd_bb
== bb
)
413 if (!TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
414 mark_last_stmt_necessary (cd_bb
);
418 SET_BIT (visited_control_parents
, bb
->index
);
422 /* Find obviously necessary statements. These are things like most function
423 calls, and stores to file level variables.
425 If EL is NULL, control statements are conservatively marked as
426 necessary. Otherwise it contains the list of edges used by control
427 dependence analysis. */
430 find_obviously_necessary_stmts (struct edge_list
*el
)
433 gimple_stmt_iterator gsi
;
439 /* PHI nodes are never inherently necessary. */
440 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
442 phi
= gsi_stmt (gsi
);
443 gimple_set_plf (phi
, STMT_NECESSARY
, false);
446 /* Check all statements in the block. */
447 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
449 stmt
= gsi_stmt (gsi
);
450 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
451 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
455 /* Pure and const functions are finite and thus have no infinite loops in
457 if ((TREE_READONLY (current_function_decl
)
458 || DECL_PURE_P (current_function_decl
))
459 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
))
462 /* Prevent the empty possibly infinite loops from being removed. */
468 if (mark_irreducible_loops ())
472 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
473 if ((e
->flags
& EDGE_DFS_BACK
)
474 && (e
->flags
& EDGE_IRREDUCIBLE_LOOP
))
477 fprintf (dump_file
, "Marking back edge of irreducible loop %i->%i\n",
478 e
->src
->index
, e
->dest
->index
);
479 mark_control_dependent_edges_necessary (e
->dest
, el
, false);
483 FOR_EACH_LOOP (li
, loop
, 0)
484 if (!finite_loop_p (loop
))
487 fprintf (dump_file
, "can not prove finiteness of loop %i\n", loop
->num
);
488 mark_control_dependent_edges_necessary (loop
->latch
, el
, false);
495 /* Return true if REF is based on an aliased base, otherwise false. */
498 ref_may_be_aliased (tree ref
)
500 while (handled_component_p (ref
))
501 ref
= TREE_OPERAND (ref
, 0);
502 return !(DECL_P (ref
)
503 && !may_be_aliased (ref
));
506 static bitmap visited
= NULL
;
507 static unsigned int longest_chain
= 0;
508 static unsigned int total_chain
= 0;
509 static unsigned int nr_walks
= 0;
510 static bool chain_ovfl
= false;
512 /* Worker for the walker that marks reaching definitions of REF,
513 which is based on a non-aliased decl, necessary. It returns
514 true whenever the defining statement of the current VDEF is
515 a kill for REF, as no dominating may-defs are necessary for REF
516 anymore. DATA points to the basic-block that contains the
517 stmt that refers to REF. */
520 mark_aliased_reaching_defs_necessary_1 (ao_ref
*ref
, tree vdef
, void *data
)
522 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
524 /* All stmts we visit are necessary. */
525 mark_operand_necessary (vdef
);
527 /* If the stmt lhs kills ref, then we can stop walking. */
528 if (gimple_has_lhs (def_stmt
)
529 && TREE_CODE (gimple_get_lhs (def_stmt
)) != SSA_NAME
)
531 tree base
, lhs
= gimple_get_lhs (def_stmt
);
532 HOST_WIDE_INT size
, offset
, max_size
;
534 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
535 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
536 so base == refd->base does not always hold. */
537 if (base
== ref
->base
)
539 /* For a must-alias check we need to be able to constrain
540 the accesses properly. */
541 if (size
!= -1 && size
== max_size
542 && ref
->max_size
!= -1)
544 if (offset
<= ref
->offset
545 && offset
+ size
>= ref
->offset
+ ref
->max_size
)
548 /* Or they need to be exactly the same. */
550 /* Make sure there is no induction variable involved
551 in the references (gcc.c-torture/execute/pr42142.c).
552 The simplest way is to check if the kill dominates
554 && dominated_by_p (CDI_DOMINATORS
, (basic_block
) data
,
555 gimple_bb (def_stmt
))
556 && operand_equal_p (ref
->ref
, lhs
, 0))
561 /* Otherwise keep walking. */
566 mark_aliased_reaching_defs_necessary (gimple stmt
, tree ref
)
570 gcc_assert (!chain_ovfl
);
571 ao_ref_init (&refd
, ref
);
572 chain
= walk_aliased_vdefs (&refd
, gimple_vuse (stmt
),
573 mark_aliased_reaching_defs_necessary_1
,
574 gimple_bb (stmt
), NULL
);
575 if (chain
> longest_chain
)
576 longest_chain
= chain
;
577 total_chain
+= chain
;
581 /* Worker for the walker that marks reaching definitions of REF, which
582 is not based on a non-aliased decl. For simplicity we need to end
583 up marking all may-defs necessary that are not based on a non-aliased
584 decl. The only job of this walker is to skip may-defs based on
585 a non-aliased decl. */
588 mark_all_reaching_defs_necessary_1 (ao_ref
*ref ATTRIBUTE_UNUSED
,
589 tree vdef
, void *data ATTRIBUTE_UNUSED
)
591 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
593 /* We have to skip already visited (and thus necessary) statements
594 to make the chaining work after we dropped back to simple mode. */
596 && TEST_BIT (processed
, SSA_NAME_VERSION (vdef
)))
598 gcc_assert (gimple_nop_p (def_stmt
)
599 || gimple_plf (def_stmt
, STMT_NECESSARY
));
603 /* We want to skip stores to non-aliased variables. */
605 && gimple_assign_single_p (def_stmt
))
607 tree lhs
= gimple_assign_lhs (def_stmt
);
608 if (!ref_may_be_aliased (lhs
))
612 mark_operand_necessary (vdef
);
618 mark_all_reaching_defs_necessary (gimple stmt
)
620 walk_aliased_vdefs (NULL
, gimple_vuse (stmt
),
621 mark_all_reaching_defs_necessary_1
, NULL
, &visited
);
624 /* Return true for PHI nodes with one or identical arguments
627 degenerate_phi_p (gimple phi
)
630 tree op
= gimple_phi_arg_def (phi
, 0);
631 for (i
= 1; i
< gimple_phi_num_args (phi
); i
++)
632 if (gimple_phi_arg_def (phi
, i
) != op
)
637 /* Propagate necessity using the operands of necessary statements.
638 Process the uses on each statement in the worklist, and add all
639 feeding statements which contribute to the calculation of this
640 value to the worklist.
642 In conservative mode, EL is NULL. */
645 propagate_necessity (struct edge_list
*el
)
648 bool aggressive
= (el
? true : false);
650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
651 fprintf (dump_file
, "\nProcessing worklist:\n");
653 while (VEC_length (gimple
, worklist
) > 0)
655 /* Take STMT from worklist. */
656 stmt
= VEC_pop (gimple
, worklist
);
658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
660 fprintf (dump_file
, "processing: ");
661 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
662 fprintf (dump_file
, "\n");
667 /* Mark the last statement of the basic blocks on which the block
668 containing STMT is control dependent, but only if we haven't
670 basic_block bb
= gimple_bb (stmt
);
671 if (bb
!= ENTRY_BLOCK_PTR
672 && !TEST_BIT (visited_control_parents
, bb
->index
))
673 mark_control_dependent_edges_necessary (bb
, el
, false);
676 if (gimple_code (stmt
) == GIMPLE_PHI
677 /* We do not process virtual PHI nodes nor do we track their
679 && is_gimple_reg (gimple_phi_result (stmt
)))
681 /* PHI nodes are somewhat special in that each PHI alternative has
682 data and control dependencies. All the statements feeding the
683 PHI node's arguments are always necessary. In aggressive mode,
684 we also consider the control dependent edges leading to the
685 predecessor block associated with each PHI alternative as
689 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
691 tree arg
= PHI_ARG_DEF (stmt
, k
);
692 if (TREE_CODE (arg
) == SSA_NAME
)
693 mark_operand_necessary (arg
);
696 /* For PHI operands it matters from where the control flow arrives
697 to the BB. Consider the following example:
707 We need to mark control dependence of the empty basic blocks, since they
708 contains computation of PHI operands.
710 Doing so is too restrictive in the case the predecestor block is in
716 for (i = 0; i<1000; ++i)
722 There is PHI for J in the BB containing return statement.
723 In this case the control dependence of predecestor block (that is
724 within the empty loop) also contains the block determining number
725 of iterations of the block that would prevent removing of empty
728 This scenario can be avoided by splitting critical edges.
729 To save the critical edge splitting pass we identify how the control
730 dependence would look like if the edge was split.
732 Consider the modified CFG created from current CFG by splitting
733 edge B->C. In the postdominance tree of modified CFG, C' is
734 always child of C. There are two cases how chlids of C' can look
739 In this case the only basic block C' is control dependent on is B.
741 2) C' has single child that is B
743 In this case control dependence of C' is same as control
744 dependence of B in original CFG except for block B itself.
745 (since C' postdominate B in modified CFG)
747 Now how to decide what case happens? There are two basic options:
749 a) C postdominate B. Then C immediately postdominate B and
750 case 2 happens iff there is no other way from B to C except
753 There is other way from B to C iff there is succesor of B that
754 is not postdominated by B. Testing this condition is somewhat
755 expensive, because we need to iterate all succesors of B.
756 We are safe to assume that this does not happen: we will mark B
757 as needed when processing the other path from B to C that is
758 conrol dependent on B and marking control dependencies of B
759 itself is harmless because they will be processed anyway after
760 processing control statement in B.
762 b) C does not postdominate B. Always case 1 happens since there is
763 path from C to exit that does not go through B and thus also C'. */
765 if (aggressive
&& !degenerate_phi_p (stmt
))
767 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
769 basic_block arg_bb
= gimple_phi_arg_edge (stmt
, k
)->src
;
772 != get_immediate_dominator (CDI_POST_DOMINATORS
, arg_bb
))
774 if (!TEST_BIT (last_stmt_necessary
, arg_bb
->index
))
775 mark_last_stmt_necessary (arg_bb
);
777 else if (arg_bb
!= ENTRY_BLOCK_PTR
778 && !TEST_BIT (visited_control_parents
,
780 mark_control_dependent_edges_necessary (arg_bb
, el
, true);
786 /* Propagate through the operands. Examine all the USE, VUSE and
787 VDEF operands in this statement. Mark all the statements
788 which feed this statement's uses as necessary. */
792 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
793 mark_operand_necessary (use
);
795 use
= gimple_vuse (stmt
);
799 /* If we dropped to simple mode make all immediately
800 reachable definitions necessary. */
803 mark_all_reaching_defs_necessary (stmt
);
807 /* For statements that may load from memory (have a VUSE) we
808 have to mark all reaching (may-)definitions as necessary.
809 We partition this task into two cases:
810 1) explicit loads based on decls that are not aliased
811 2) implicit loads (like calls) and explicit loads not
812 based on decls that are not aliased (like indirect
813 references or loads from globals)
814 For 1) we mark all reaching may-defs as necessary, stopping
815 at dominating kills. For 2) we want to mark all dominating
816 references necessary, but non-aliased ones which we handle
817 in 1). By keeping a global visited bitmap for references
818 we walk for 2) we avoid quadratic behavior for those. */
820 if (is_gimple_call (stmt
))
822 tree callee
= gimple_call_fndecl (stmt
);
825 /* Calls to functions that are merely acting as barriers
826 or that only store to memory do not make any previous
828 if (callee
!= NULL_TREE
829 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
830 && (DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET
831 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MALLOC
832 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_FREE
))
835 /* Calls implicitly load from memory, their arguments
836 in addition may explicitly perform memory loads. */
837 mark_all_reaching_defs_necessary (stmt
);
838 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
840 tree arg
= gimple_call_arg (stmt
, i
);
841 if (TREE_CODE (arg
) == SSA_NAME
842 || is_gimple_min_invariant (arg
))
844 if (!ref_may_be_aliased (arg
))
845 mark_aliased_reaching_defs_necessary (stmt
, arg
);
848 else if (gimple_assign_single_p (stmt
))
851 bool rhs_aliased
= false;
852 /* If this is a load mark things necessary. */
853 rhs
= gimple_assign_rhs1 (stmt
);
854 if (TREE_CODE (rhs
) != SSA_NAME
855 && !is_gimple_min_invariant (rhs
))
857 if (!ref_may_be_aliased (rhs
))
858 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
863 mark_all_reaching_defs_necessary (stmt
);
865 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
867 tree rhs
= gimple_return_retval (stmt
);
868 /* A return statement may perform a load. */
869 if (TREE_CODE (rhs
) != SSA_NAME
870 && !is_gimple_min_invariant (rhs
))
872 if (!ref_may_be_aliased (rhs
))
873 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
875 mark_all_reaching_defs_necessary (stmt
);
878 else if (gimple_code (stmt
) == GIMPLE_ASM
)
881 mark_all_reaching_defs_necessary (stmt
);
882 /* Inputs may perform loads. */
883 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
885 tree op
= TREE_VALUE (gimple_asm_input_op (stmt
, i
));
886 if (TREE_CODE (op
) != SSA_NAME
887 && !is_gimple_min_invariant (op
)
888 && !ref_may_be_aliased (op
))
889 mark_aliased_reaching_defs_necessary (stmt
, op
);
895 /* If we over-used our alias oracle budget drop to simple
896 mode. The cost metric allows quadratic behavior
897 (number of uses times number of may-defs queries) up to
898 a constant maximal number of queries and after that falls back to
899 super-linear complexity. */
900 if (/* Constant but quadratic for small functions. */
901 total_chain
> 128 * 128
902 /* Linear in the number of may-defs. */
903 && total_chain
> 32 * longest_chain
904 /* Linear in the number of uses. */
905 && total_chain
> nr_walks
* 32)
909 bitmap_clear (visited
);
915 /* Replace all uses of result of PHI by underlying variable and mark it
919 mark_virtual_phi_result_for_renaming (gimple phi
)
922 imm_use_iterator iter
;
925 tree result_ssa
, result_var
;
927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
929 fprintf (dump_file
, "Marking result for renaming : ");
930 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
931 fprintf (dump_file
, "\n");
934 result_ssa
= gimple_phi_result (phi
);
935 result_var
= SSA_NAME_VAR (result_ssa
);
936 FOR_EACH_IMM_USE_STMT (stmt
, iter
, result_ssa
)
938 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
939 SET_USE (use_p
, result_var
);
944 mark_sym_for_renaming (result_var
);
947 /* Remove dead PHI nodes from block BB. */
950 remove_dead_phis (basic_block bb
)
952 bool something_changed
= false;
955 gimple_stmt_iterator gsi
;
956 phis
= phi_nodes (bb
);
958 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
);)
961 phi
= gsi_stmt (gsi
);
963 /* We do not track necessity of virtual PHI nodes. Instead do
964 very simple dead PHI removal here. */
965 if (!is_gimple_reg (gimple_phi_result (phi
)))
967 /* Virtual PHI nodes with one or identical arguments
969 if (degenerate_phi_p (phi
))
971 tree vdef
= gimple_phi_result (phi
);
972 tree vuse
= gimple_phi_arg_def (phi
, 0);
975 imm_use_iterator iter
;
977 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, vdef
)
978 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
979 SET_USE (use_p
, vuse
);
980 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef
)
981 && TREE_CODE (vuse
) == SSA_NAME
)
982 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse
) = 1;
985 gimple_set_plf (phi
, STMT_NECESSARY
, true);
988 if (!gimple_plf (phi
, STMT_NECESSARY
))
990 something_changed
= true;
991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
993 fprintf (dump_file
, "Deleting : ");
994 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
995 fprintf (dump_file
, "\n");
998 remove_phi_node (&gsi
, true);
999 stats
.removed_phis
++;
1005 return something_changed
;
1008 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
1011 forward_edge_to_pdom (edge e
, basic_block post_dom_bb
)
1013 gimple_stmt_iterator gsi
;
1017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1018 fprintf (dump_file
, "Redirecting edge %i->%i to %i\n", e
->src
->index
,
1019 e
->dest
->index
, post_dom_bb
->index
);
1021 e2
= redirect_edge_and_branch (e
, post_dom_bb
);
1024 /* If edge was already around, no updating is neccesary. */
1028 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb
)))
1030 /* We are sure that for every live PHI we are seeing control dependent BB.
1031 This means that we can pick any edge to duplicate PHI args from. */
1032 FOR_EACH_EDGE (e2
, ei
, post_dom_bb
->preds
)
1035 for (gsi
= gsi_start_phis (post_dom_bb
); !gsi_end_p (gsi
);)
1037 gimple phi
= gsi_stmt (gsi
);
1039 source_location locus
;
1041 /* PHIs for virtuals have no control dependency relation on them.
1042 We are lost here and must force renaming of the symbol. */
1043 if (!is_gimple_reg (gimple_phi_result (phi
)))
1045 mark_virtual_phi_result_for_renaming (phi
);
1046 remove_phi_node (&gsi
, true);
1050 /* Dead PHI do not imply control dependency. */
1051 if (!gimple_plf (phi
, STMT_NECESSARY
))
1057 op
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
1058 locus
= gimple_phi_arg_location (phi
, e2
->dest_idx
);
1059 add_phi_arg (phi
, op
, e
, locus
);
1060 /* The resulting PHI if not dead can only be degenerate. */
1061 gcc_assert (degenerate_phi_p (phi
));
1068 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1069 containing I so that we don't have to look it up. */
1072 remove_dead_stmt (gimple_stmt_iterator
*i
, basic_block bb
)
1074 gimple stmt
= gsi_stmt (*i
);
1076 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1078 fprintf (dump_file
, "Deleting : ");
1079 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1080 fprintf (dump_file
, "\n");
1085 /* If we have determined that a conditional branch statement contributes
1086 nothing to the program, then we not only remove it, but we also change
1087 the flow graph so that the current block will simply fall-thru to its
1088 immediate post-dominator. The blocks we are circumventing will be
1089 removed by cleanup_tree_cfg if this change in the flow graph makes them
1091 if (is_ctrl_stmt (stmt
))
1093 basic_block post_dom_bb
;
1097 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
1099 e
= find_edge (bb
, post_dom_bb
);
1101 /* If edge is already there, try to use it. This avoids need to update
1102 PHI nodes. Also watch for cases where post dominator does not exists
1103 or is exit block. These can happen for infinite loops as we create
1104 fake edges in the dominator tree. */
1107 else if (! post_dom_bb
|| post_dom_bb
== EXIT_BLOCK_PTR
)
1108 e
= EDGE_SUCC (bb
, 0);
1110 e
= forward_edge_to_pdom (EDGE_SUCC (bb
, 0), post_dom_bb
);
1112 e
->probability
= REG_BR_PROB_BASE
;
1113 e
->count
= bb
->count
;
1115 /* The edge is no longer associated with a conditional, so it does
1116 not have TRUE/FALSE flags. */
1117 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1119 /* The lone outgoing edge from BB will be a fallthru edge. */
1120 e
->flags
|= EDGE_FALLTHRU
;
1122 /* Remove the remaining outgoing edges. */
1123 for (ei
= ei_start (bb
->succs
); (e2
= ei_safe_edge (ei
)); )
1133 unlink_stmt_vdef (stmt
);
1134 gsi_remove (i
, true);
1135 release_defs (stmt
);
1138 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1139 contributes nothing to the program, and can be deleted. */
1142 eliminate_unnecessary_stmts (void)
1144 bool something_changed
= false;
1146 gimple_stmt_iterator gsi
, psi
;
1149 VEC (basic_block
, heap
) *h
;
1151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1152 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1154 clear_special_calls ();
1156 /* Walking basic blocks and statements in reverse order avoids
1157 releasing SSA names before any other DEFs that refer to them are
1158 released. This helps avoid loss of debug information, as we get
1159 a chance to propagate all RHSs of removed SSAs into debug uses,
1160 rather than only the latest ones. E.g., consider:
1166 If we were to release x_3 before a_5, when we reached a_5 and
1167 tried to substitute it into the debug stmt, we'd see x_3 there,
1168 but x_3's DEF, type, etc would have already been disconnected.
1169 By going backwards, the debug stmt first changes to:
1171 # DEBUG a => x_3 - b_4
1175 # DEBUG a => y_1 + z_2 - b_4
1178 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
1179 h
= get_all_dominated_blocks (CDI_DOMINATORS
, single_succ (ENTRY_BLOCK_PTR
));
1181 while (VEC_length (basic_block
, h
))
1183 bb
= VEC_pop (basic_block
, h
);
1185 /* Remove dead statements. */
1186 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi
= psi
)
1188 stmt
= gsi_stmt (gsi
);
1195 /* If GSI is not necessary then remove it. */
1196 if (!gimple_plf (stmt
, STMT_NECESSARY
))
1198 if (!is_gimple_debug (stmt
))
1199 something_changed
= true;
1200 remove_dead_stmt (&gsi
, bb
);
1202 else if (is_gimple_call (stmt
))
1204 call
= gimple_call_fndecl (stmt
);
1209 /* When LHS of var = call (); is dead, simplify it into
1210 call (); saving one operand. */
1211 name
= gimple_call_lhs (stmt
);
1212 if (name
&& TREE_CODE (name
) == SSA_NAME
1213 && !TEST_BIT (processed
, SSA_NAME_VERSION (name
)))
1215 something_changed
= true;
1216 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1218 fprintf (dump_file
, "Deleting LHS of call: ");
1219 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1220 fprintf (dump_file
, "\n");
1223 gimple_call_set_lhs (stmt
, NULL_TREE
);
1224 maybe_clean_or_replace_eh_stmt (stmt
, stmt
);
1226 release_ssa_name (name
);
1228 notice_special_calls (stmt
);
1234 VEC_free (basic_block
, heap
, h
);
1236 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1237 rendered some PHI nodes unreachable while they are still in use.
1238 Mark them for renaming. */
1241 basic_block prev_bb
;
1243 find_unreachable_blocks ();
1245 /* Delete all unreachable basic blocks in reverse dominator order. */
1246 for (bb
= EXIT_BLOCK_PTR
->prev_bb
; bb
!= ENTRY_BLOCK_PTR
; bb
= prev_bb
)
1248 prev_bb
= bb
->prev_bb
;
1250 if (!TEST_BIT (bb_contains_live_stmts
, bb
->index
)
1251 || !(bb
->flags
& BB_REACHABLE
))
1253 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1254 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi
))))
1257 imm_use_iterator iter
;
1259 FOR_EACH_IMM_USE_STMT (stmt
, iter
, gimple_phi_result (gsi_stmt (gsi
)))
1261 if (!(gimple_bb (stmt
)->flags
& BB_REACHABLE
))
1263 if (gimple_code (stmt
) == GIMPLE_PHI
1264 || gimple_plf (stmt
, STMT_NECESSARY
))
1267 BREAK_FROM_IMM_USE_STMT (iter
);
1271 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi
));
1274 if (!(bb
->flags
& BB_REACHABLE
))
1276 /* Speed up the removal of blocks that don't
1277 dominate others. Walking backwards, this should
1278 be the common case. ??? Do we need to recompute
1279 dominators because of cfg_altered? */
1280 if (!MAY_HAVE_DEBUG_STMTS
1281 || !first_dom_son (CDI_DOMINATORS
, bb
))
1282 delete_basic_block (bb
);
1285 h
= get_all_dominated_blocks (CDI_DOMINATORS
, bb
);
1287 while (VEC_length (basic_block
, h
))
1289 bb
= VEC_pop (basic_block
, h
);
1290 prev_bb
= bb
->prev_bb
;
1291 /* Rearrangements to the CFG may have failed
1292 to update the dominators tree, so that
1293 formerly-dominated blocks are now
1294 otherwise reachable. */
1295 if (!!(bb
->flags
& BB_REACHABLE
))
1297 delete_basic_block (bb
);
1300 VEC_free (basic_block
, heap
, h
);
1308 /* Remove dead PHI nodes. */
1309 something_changed
|= remove_dead_phis (bb
);
1312 return something_changed
;
1316 /* Print out removed statement statistics. */
1323 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1324 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1325 stats
.removed
, stats
.total
, (int) percg
);
1327 if (stats
.total_phis
== 0)
1330 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1332 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1333 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1336 /* Initialization for this pass. Set up the used data structures. */
1339 tree_dce_init (bool aggressive
)
1341 memset ((void *) &stats
, 0, sizeof (stats
));
1347 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
1348 for (i
= 0; i
< last_basic_block
; ++i
)
1349 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
1351 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
1352 sbitmap_zero (last_stmt_necessary
);
1353 bb_contains_live_stmts
= sbitmap_alloc (last_basic_block
);
1354 sbitmap_zero (bb_contains_live_stmts
);
1357 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1358 sbitmap_zero (processed
);
1360 worklist
= VEC_alloc (gimple
, heap
, 64);
1361 cfg_altered
= false;
1364 /* Cleanup after this pass. */
1367 tree_dce_done (bool aggressive
)
1373 for (i
= 0; i
< last_basic_block
; ++i
)
1374 BITMAP_FREE (control_dependence_map
[i
]);
1375 free (control_dependence_map
);
1377 sbitmap_free (visited_control_parents
);
1378 sbitmap_free (last_stmt_necessary
);
1379 sbitmap_free (bb_contains_live_stmts
);
1380 bb_contains_live_stmts
= NULL
;
1383 sbitmap_free (processed
);
1385 VEC_free (gimple
, heap
, worklist
);
1388 /* Main routine to eliminate dead code.
1390 AGGRESSIVE controls the aggressiveness of the algorithm.
1391 In conservative mode, we ignore control dependence and simply declare
1392 all but the most trivially dead branches necessary. This mode is fast.
1393 In aggressive mode, control dependences are taken into account, which
1394 results in more dead code elimination, but at the cost of some time.
1396 FIXME: Aggressive mode before PRE doesn't work currently because
1397 the dominance info is not invalidated after DCE1. This is
1398 not an issue right now because we only run aggressive DCE
1399 as the last tree SSA pass, but keep this in mind when you
1400 start experimenting with pass ordering. */
1403 perform_tree_ssa_dce (bool aggressive
)
1405 struct edge_list
*el
= NULL
;
1406 bool something_changed
= 0;
1408 /* Preheaders are needed for SCEV to work.
1409 Simple lateches and recorded exits improve chances that loop will
1410 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1412 loop_optimizer_init (LOOPS_NORMAL
1413 | LOOPS_HAVE_RECORDED_EXITS
);
1415 tree_dce_init (aggressive
);
1419 /* Compute control dependence. */
1420 timevar_push (TV_CONTROL_DEPENDENCES
);
1421 calculate_dominance_info (CDI_POST_DOMINATORS
);
1422 el
= create_edge_list ();
1423 find_all_control_dependences (el
);
1424 timevar_pop (TV_CONTROL_DEPENDENCES
);
1426 visited_control_parents
= sbitmap_alloc (last_basic_block
);
1427 sbitmap_zero (visited_control_parents
);
1429 mark_dfs_back_edges ();
1432 find_obviously_necessary_stmts (el
);
1435 loop_optimizer_finalize ();
1441 visited
= BITMAP_ALLOC (NULL
);
1442 propagate_necessity (el
);
1443 BITMAP_FREE (visited
);
1445 something_changed
|= eliminate_unnecessary_stmts ();
1446 something_changed
|= cfg_altered
;
1448 /* We do not update postdominators, so free them unconditionally. */
1449 free_dominance_info (CDI_POST_DOMINATORS
);
1451 /* If we removed paths in the CFG, then we need to update
1452 dominators as well. I haven't investigated the possibility
1453 of incrementally updating dominators. */
1455 free_dominance_info (CDI_DOMINATORS
);
1457 statistics_counter_event (cfun
, "Statements deleted", stats
.removed
);
1458 statistics_counter_event (cfun
, "PHI nodes deleted", stats
.removed_phis
);
1460 /* Debugging dumps. */
1461 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1464 tree_dce_done (aggressive
);
1466 free_edge_list (el
);
1468 if (something_changed
)
1469 return (TODO_update_ssa
| TODO_cleanup_cfg
| TODO_ggc_collect
1470 | TODO_remove_unused_locals
);
1475 /* Pass entry points. */
1479 return perform_tree_ssa_dce (/*aggressive=*/false);
1483 tree_ssa_dce_loop (void)
1486 todo
= perform_tree_ssa_dce (/*aggressive=*/false);
1489 free_numbers_of_iterations_estimates ();
1496 tree_ssa_cd_dce (void)
1498 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1504 return flag_tree_dce
!= 0;
1507 struct gimple_opt_pass pass_dce
=
1512 gate_dce
, /* gate */
1513 tree_ssa_dce
, /* execute */
1516 0, /* static_pass_number */
1517 TV_TREE_DCE
, /* tv_id */
1518 PROP_cfg
| PROP_ssa
, /* properties_required */
1519 0, /* properties_provided */
1520 0, /* properties_destroyed */
1521 0, /* todo_flags_start */
1522 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1526 struct gimple_opt_pass pass_dce_loop
=
1530 "dceloop", /* name */
1531 gate_dce
, /* gate */
1532 tree_ssa_dce_loop
, /* execute */
1535 0, /* static_pass_number */
1536 TV_TREE_DCE
, /* tv_id */
1537 PROP_cfg
| PROP_ssa
, /* properties_required */
1538 0, /* properties_provided */
1539 0, /* properties_destroyed */
1540 0, /* todo_flags_start */
1541 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1545 struct gimple_opt_pass pass_cd_dce
=
1550 gate_dce
, /* gate */
1551 tree_ssa_cd_dce
, /* execute */
1554 0, /* static_pass_number */
1555 TV_TREE_CD_DCE
, /* tv_id */
1556 PROP_cfg
| PROP_ssa
, /* properties_required */
1557 0, /* properties_provided */
1558 0, /* properties_destroyed */
1559 0, /* todo_flags_start */
1560 TODO_dump_func
| TODO_verify_ssa
1561 | TODO_verify_flow
/* todo_flags_finish */