1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
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 /* 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"
63 #include "tree-dump.h"
64 #include "tree-pass.h"
68 #include "tree-scalar-evolution.h"
70 static struct stmt_stats
78 #define STMT_NECESSARY GF_PLF_1
80 static VEC(gimple
,heap
) *worklist
;
82 /* Vector indicating an SSA name has already been processed and marked
84 static sbitmap processed
;
86 /* Vector indicating that last_stmt if a basic block has already been
87 marked as necessary. */
88 static sbitmap last_stmt_necessary
;
90 /* Vector indicating that BB contains statements that are live. */
91 static sbitmap bb_contains_live_stmts
;
93 /* Before we can determine whether a control branch is dead, we need to
94 compute which blocks are control dependent on which edges.
96 We expect each block to be control dependent on very few edges so we
97 use a bitmap for each block recording its edges. An array holds the
98 bitmap. The Ith bit in the bitmap is set if that block is dependent
100 static bitmap
*control_dependence_map
;
102 /* Vector indicating that a basic block has already had all the edges
103 processed that it is control dependent on. */
104 static sbitmap visited_control_parents
;
106 /* TRUE if this pass alters the CFG (by removing control statements).
109 If this pass alters the CFG, then it will arrange for the dominators
111 static bool cfg_altered
;
113 /* Execute code that follows the macro for each edge (given number
114 EDGE_NUMBER within the CODE) for which the block with index N is
115 control dependent. */
116 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
117 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
121 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
123 set_control_dependence_map_bit (basic_block bb
, int edge_index
)
125 if (bb
== ENTRY_BLOCK_PTR
)
127 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
128 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
131 /* Clear all control dependences for block BB. */
133 clear_control_dependence_bitmap (basic_block bb
)
135 bitmap_clear (control_dependence_map
[bb
->index
]);
139 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
140 This function is necessary because some blocks have negative numbers. */
142 static inline basic_block
143 find_pdom (basic_block block
)
145 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
147 if (block
== EXIT_BLOCK_PTR
)
148 return EXIT_BLOCK_PTR
;
151 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
153 return EXIT_BLOCK_PTR
;
159 /* Determine all blocks' control dependences on the given edge with edge_list
160 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
163 find_control_dependence (struct edge_list
*el
, int edge_index
)
165 basic_block current_block
;
166 basic_block ending_block
;
168 gcc_assert (INDEX_EDGE_PRED_BB (el
, edge_index
) != EXIT_BLOCK_PTR
);
170 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
171 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
173 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (el
, edge_index
));
175 for (current_block
= INDEX_EDGE_SUCC_BB (el
, edge_index
);
176 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
177 current_block
= find_pdom (current_block
))
179 edge e
= INDEX_EDGE (el
, edge_index
);
181 /* For abnormal edges, we don't make current_block control
182 dependent because instructions that throw are always necessary
184 if (e
->flags
& EDGE_ABNORMAL
)
187 set_control_dependence_map_bit (current_block
, edge_index
);
192 /* Record all blocks' control dependences on all edges in the edge
193 list EL, ala Morgan, Section 3.6. */
196 find_all_control_dependences (struct edge_list
*el
)
200 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
201 find_control_dependence (el
, i
);
204 /* If STMT is not already marked necessary, mark it, and add it to the
205 worklist if ADD_TO_WORKLIST is true. */
207 mark_stmt_necessary (gimple stmt
, bool add_to_worklist
)
211 if (gimple_plf (stmt
, STMT_NECESSARY
))
214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
216 fprintf (dump_file
, "Marking useful stmt: ");
217 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
218 fprintf (dump_file
, "\n");
221 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
223 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
224 if (bb_contains_live_stmts
)
225 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
229 /* Mark the statement defining operand OP as necessary. */
232 mark_operand_necessary (tree op
)
239 ver
= SSA_NAME_VERSION (op
);
240 if (TEST_BIT (processed
, ver
))
242 stmt
= SSA_NAME_DEF_STMT (op
);
243 gcc_assert (gimple_nop_p (stmt
)
244 || gimple_plf (stmt
, STMT_NECESSARY
));
247 SET_BIT (processed
, ver
);
249 stmt
= SSA_NAME_DEF_STMT (op
);
252 if (gimple_plf (stmt
, STMT_NECESSARY
) || gimple_nop_p (stmt
))
255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
257 fprintf (dump_file
, "marking necessary through ");
258 print_generic_expr (dump_file
, op
, 0);
259 fprintf (dump_file
, " stmt ");
260 print_gimple_stmt (dump_file
, stmt
, 0, 0);
263 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
264 if (bb_contains_live_stmts
)
265 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
266 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
270 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
271 it can make other statements necessary.
273 If AGGRESSIVE is false, control statements are conservatively marked as
277 mark_stmt_if_obviously_necessary (gimple stmt
, bool aggressive
)
279 tree lhs
= NULL_TREE
;
280 /* With non-call exceptions, we have to assume that all statements could
281 throw. If a statement may throw, it is inherently necessary. */
282 if (flag_non_call_exceptions
283 && stmt_could_throw_p (stmt
))
285 mark_stmt_necessary (stmt
, true);
289 /* Statements that are implicitly live. Most function calls, asm
290 and return statements are required. Labels and GIMPLE_BIND nodes
291 are kept because they are control flow, and we have no way of
292 knowing whether they can be removed. DCE can eliminate all the
293 other statements in a block, and CFG can then remove the block
295 switch (gimple_code (stmt
))
299 mark_stmt_necessary (stmt
, false);
305 mark_stmt_necessary (stmt
, true);
309 /* Most, but not all function calls are required. Function calls that
310 produce no result and have no side effects (i.e. const pure
311 functions) are unnecessary. */
312 if (gimple_has_side_effects (stmt
))
314 mark_stmt_necessary (stmt
, true);
317 if (!gimple_call_lhs (stmt
))
319 lhs
= gimple_call_lhs (stmt
);
324 lhs
= gimple_assign_lhs (stmt
);
325 /* These values are mildly magic bits of the EH runtime. We can't
326 see the entire lifetime of these values until landing pads are
328 if (TREE_CODE (lhs
) == EXC_PTR_EXPR
329 || TREE_CODE (lhs
) == FILTER_EXPR
)
331 mark_stmt_necessary (stmt
, true);
337 gcc_assert (!simple_goto_p (stmt
));
338 mark_stmt_necessary (stmt
, true);
342 gcc_assert (EDGE_COUNT (gimple_bb (stmt
)->succs
) == 2);
347 mark_stmt_necessary (stmt
, true);
354 /* If the statement has volatile operands, it needs to be preserved.
355 Same for statements that can alter control flow in unpredictable
357 if (gimple_has_volatile_ops (stmt
) || is_ctrl_altering_stmt (stmt
))
359 mark_stmt_necessary (stmt
, true);
363 if (is_hidden_global_store (stmt
))
365 mark_stmt_necessary (stmt
, true);
373 /* Make corresponding control dependent edges necessary. We only
374 have to do this once for each basic block, so we clear the bitmap
377 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
)
380 unsigned edge_number
;
382 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
384 if (bb
== ENTRY_BLOCK_PTR
)
387 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
390 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
392 if (TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
394 SET_BIT (last_stmt_necessary
, cd_bb
->index
);
395 SET_BIT (bb_contains_live_stmts
, cd_bb
->index
);
397 stmt
= last_stmt (cd_bb
);
398 if (stmt
&& is_ctrl_stmt (stmt
))
399 mark_stmt_necessary (stmt
, true);
404 /* Find obviously necessary statements. These are things like most function
405 calls, and stores to file level variables.
407 If EL is NULL, control statements are conservatively marked as
408 necessary. Otherwise it contains the list of edges used by control
409 dependence analysis. */
412 find_obviously_necessary_stmts (struct edge_list
*el
)
415 gimple_stmt_iterator gsi
;
421 /* PHI nodes are never inherently necessary. */
422 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
424 phi
= gsi_stmt (gsi
);
425 gimple_set_plf (phi
, STMT_NECESSARY
, false);
428 /* Check all statements in the block. */
429 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
431 stmt
= gsi_stmt (gsi
);
432 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
433 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
437 /* Pure and const functions are finite and thus have no infinite loops in
439 if ((TREE_READONLY (current_function_decl
)
440 || DECL_PURE_P (current_function_decl
))
441 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
))
444 /* Prevent the empty possibly infinite loops from being removed. */
450 if (mark_irreducible_loops ())
454 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
455 if ((e
->flags
& EDGE_DFS_BACK
)
456 && (e
->flags
& EDGE_IRREDUCIBLE_LOOP
))
459 fprintf (dump_file
, "Marking back edge of irreducible loop %i->%i\n",
460 e
->src
->index
, e
->dest
->index
);
461 mark_control_dependent_edges_necessary (e
->dest
, el
);
465 FOR_EACH_LOOP (li
, loop
, 0)
466 if (!finite_loop_p (loop
))
469 fprintf (dump_file
, "can not prove finiteness of loop %i\n", loop
->num
);
470 mark_control_dependent_edges_necessary (loop
->latch
, el
);
477 /* Return true if REF is based on an aliased base, otherwise false. */
480 ref_may_be_aliased (tree ref
)
482 while (handled_component_p (ref
))
483 ref
= TREE_OPERAND (ref
, 0);
484 return !(DECL_P (ref
)
485 && !may_be_aliased (ref
));
488 static bitmap visited
= NULL
;
489 static unsigned int longest_chain
= 0;
490 static unsigned int total_chain
= 0;
491 static bool chain_ovfl
= false;
493 /* Worker for the walker that marks reaching definitions of REF,
494 which is based on a non-aliased decl, necessary. It returns
495 true whenever the defining statement of the current VDEF is
496 a kill for REF, as no dominating may-defs are necessary for REF
497 anymore. DATA points to cached get_ref_base_and_extent data for REF. */
500 mark_aliased_reaching_defs_necessary_1 (ao_ref
*ref
, tree vdef
,
501 void *data ATTRIBUTE_UNUSED
)
503 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
505 /* All stmts we visit are necessary. */
506 mark_operand_necessary (vdef
);
508 /* If the stmt lhs kills ref, then we can stop walking. */
509 if (gimple_has_lhs (def_stmt
)
510 && TREE_CODE (gimple_get_lhs (def_stmt
)) != SSA_NAME
)
512 tree base
, lhs
= gimple_get_lhs (def_stmt
);
513 HOST_WIDE_INT size
, offset
, max_size
;
515 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
516 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
517 so base == refd->base does not always hold. */
518 if (base
== ref
->base
)
520 /* For a must-alias check we need to be able to constrain
521 the accesses properly. */
522 if (size
!= -1 && size
== max_size
523 && ref
->max_size
!= -1)
525 if (offset
<= ref
->offset
526 && offset
+ size
>= ref
->offset
+ ref
->max_size
)
529 /* Or they need to be exactly the same. */
531 && operand_equal_p (ref
->ref
, lhs
, 0))
536 /* Otherwise keep walking. */
541 mark_aliased_reaching_defs_necessary (gimple stmt
, tree ref
)
545 gcc_assert (!chain_ovfl
);
546 ao_ref_init (&refd
, ref
);
547 chain
= walk_aliased_vdefs (&refd
, gimple_vuse (stmt
),
548 mark_aliased_reaching_defs_necessary_1
,
550 if (chain
> longest_chain
)
551 longest_chain
= chain
;
552 total_chain
+= chain
;
555 /* Worker for the walker that marks reaching definitions of REF, which
556 is not based on a non-aliased decl. For simplicity we need to end
557 up marking all may-defs necessary that are not based on a non-aliased
558 decl. The only job of this walker is to skip may-defs based on
559 a non-aliased decl. */
562 mark_all_reaching_defs_necessary_1 (ao_ref
*ref ATTRIBUTE_UNUSED
,
563 tree vdef
, void *data ATTRIBUTE_UNUSED
)
565 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
567 /* We have to skip already visited (and thus necessary) statements
568 to make the chaining work after we dropped back to simple mode. */
570 && TEST_BIT (processed
, SSA_NAME_VERSION (vdef
)))
572 gcc_assert (gimple_nop_p (def_stmt
)
573 || gimple_plf (def_stmt
, STMT_NECESSARY
));
577 /* We want to skip stores to non-aliased variables. */
579 && gimple_assign_single_p (def_stmt
))
581 tree lhs
= gimple_assign_lhs (def_stmt
);
582 if (!ref_may_be_aliased (lhs
))
586 mark_operand_necessary (vdef
);
592 mark_all_reaching_defs_necessary (gimple stmt
)
594 walk_aliased_vdefs (NULL
, gimple_vuse (stmt
),
595 mark_all_reaching_defs_necessary_1
, NULL
, &visited
);
598 /* Return true for PHI nodes with one or identical arguments
601 degenerate_phi_p (gimple phi
)
604 tree op
= gimple_phi_arg_def (phi
, 0);
605 for (i
= 1; i
< gimple_phi_num_args (phi
); i
++)
606 if (gimple_phi_arg_def (phi
, i
) != op
)
611 /* Propagate necessity using the operands of necessary statements.
612 Process the uses on each statement in the worklist, and add all
613 feeding statements which contribute to the calculation of this
614 value to the worklist.
616 In conservative mode, EL is NULL. */
619 propagate_necessity (struct edge_list
*el
)
622 bool aggressive
= (el
? true : false);
624 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
625 fprintf (dump_file
, "\nProcessing worklist:\n");
627 while (VEC_length (gimple
, worklist
) > 0)
629 /* Take STMT from worklist. */
630 stmt
= VEC_pop (gimple
, worklist
);
632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
634 fprintf (dump_file
, "processing: ");
635 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
636 fprintf (dump_file
, "\n");
641 /* Mark the last statements of the basic blocks that the block
642 containing STMT is control dependent on, but only if we haven't
644 basic_block bb
= gimple_bb (stmt
);
645 if (bb
!= ENTRY_BLOCK_PTR
646 && ! TEST_BIT (visited_control_parents
, bb
->index
))
648 SET_BIT (visited_control_parents
, bb
->index
);
649 mark_control_dependent_edges_necessary (bb
, el
);
653 if (gimple_code (stmt
) == GIMPLE_PHI
654 /* We do not process virtual PHI nodes nor do we track their
656 && is_gimple_reg (gimple_phi_result (stmt
)))
658 /* PHI nodes are somewhat special in that each PHI alternative has
659 data and control dependencies. All the statements feeding the
660 PHI node's arguments are always necessary. In aggressive mode,
661 we also consider the control dependent edges leading to the
662 predecessor block associated with each PHI alternative as
666 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
668 tree arg
= PHI_ARG_DEF (stmt
, k
);
669 if (TREE_CODE (arg
) == SSA_NAME
)
670 mark_operand_necessary (arg
);
673 if (aggressive
&& !degenerate_phi_p (stmt
))
675 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
677 basic_block arg_bb
= gimple_phi_arg_edge (stmt
, k
)->src
;
678 if (arg_bb
!= ENTRY_BLOCK_PTR
679 && ! TEST_BIT (visited_control_parents
, arg_bb
->index
))
681 SET_BIT (visited_control_parents
, arg_bb
->index
);
682 mark_control_dependent_edges_necessary (arg_bb
, el
);
689 /* Propagate through the operands. Examine all the USE, VUSE and
690 VDEF operands in this statement. Mark all the statements
691 which feed this statement's uses as necessary. */
695 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
696 mark_operand_necessary (use
);
698 use
= gimple_vuse (stmt
);
702 /* If we dropped to simple mode make all immediately
703 reachable definitions necessary. */
706 mark_all_reaching_defs_necessary (stmt
);
710 /* For statements that may load from memory (have a VUSE) we
711 have to mark all reaching (may-)definitions as necessary.
712 We partition this task into two cases:
713 1) explicit loads based on decls that are not aliased
714 2) implicit loads (like calls) and explicit loads not
715 based on decls that are not aliased (like indirect
716 references or loads from globals)
717 For 1) we mark all reaching may-defs as necessary, stopping
718 at dominating kills. For 2) we want to mark all dominating
719 references necessary, but non-aliased ones which we handle
720 in 1). By keeping a global visited bitmap for references
721 we walk for 2) we avoid quadratic behavior for those. */
723 if (is_gimple_call (stmt
))
725 tree callee
= gimple_call_fndecl (stmt
);
728 /* Calls to functions that are merely acting as barriers
729 or that only store to memory do not make any previous
731 if (callee
!= NULL_TREE
732 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
733 && (DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET
734 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MALLOC
735 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_FREE
))
738 /* Calls implicitly load from memory, their arguments
739 in addition may explicitly perform memory loads. */
740 mark_all_reaching_defs_necessary (stmt
);
741 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
743 tree arg
= gimple_call_arg (stmt
, i
);
744 if (TREE_CODE (arg
) == SSA_NAME
745 || is_gimple_min_invariant (arg
))
747 if (!ref_may_be_aliased (arg
))
748 mark_aliased_reaching_defs_necessary (stmt
, arg
);
751 else if (gimple_assign_single_p (stmt
))
754 bool rhs_aliased
= false;
755 /* If this is a load mark things necessary. */
756 rhs
= gimple_assign_rhs1 (stmt
);
757 if (TREE_CODE (rhs
) != SSA_NAME
758 && !is_gimple_min_invariant (rhs
))
760 if (!ref_may_be_aliased (rhs
))
761 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
766 mark_all_reaching_defs_necessary (stmt
);
768 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
770 tree rhs
= gimple_return_retval (stmt
);
771 /* A return statement may perform a load. */
772 if (TREE_CODE (rhs
) != SSA_NAME
773 && !is_gimple_min_invariant (rhs
))
775 if (!ref_may_be_aliased (rhs
))
776 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
778 mark_all_reaching_defs_necessary (stmt
);
781 else if (gimple_code (stmt
) == GIMPLE_ASM
)
784 mark_all_reaching_defs_necessary (stmt
);
785 /* Inputs may perform loads. */
786 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
788 tree op
= TREE_VALUE (gimple_asm_input_op (stmt
, i
));
789 if (TREE_CODE (op
) != SSA_NAME
790 && !is_gimple_min_invariant (op
)
791 && !ref_may_be_aliased (op
))
792 mark_aliased_reaching_defs_necessary (stmt
, op
);
798 /* If we over-used our alias oracle budget drop to simple
799 mode. The cost metric allows quadratic behavior up to
800 a constant maximal chain and after that falls back to
801 super-linear complexity. */
802 if (longest_chain
> 256
803 && total_chain
> 256 * longest_chain
)
807 bitmap_clear (visited
);
813 /* Replace all uses of result of PHI by underlying variable and mark it
817 mark_virtual_phi_result_for_renaming (gimple phi
)
820 imm_use_iterator iter
;
823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
825 fprintf (dump_file
, "Marking result for renaming : ");
826 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
827 fprintf (dump_file
, "\n");
829 FOR_EACH_IMM_USE_STMT (stmt
, iter
, gimple_phi_result (phi
))
831 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
832 SET_USE (use_p
, SSA_NAME_VAR (gimple_phi_result (phi
)));
837 mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi
)));
840 /* Remove dead PHI nodes from block BB. */
843 remove_dead_phis (basic_block bb
)
845 bool something_changed
= false;
848 gimple_stmt_iterator gsi
;
849 phis
= phi_nodes (bb
);
851 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
);)
854 phi
= gsi_stmt (gsi
);
856 /* We do not track necessity of virtual PHI nodes. Instead do
857 very simple dead PHI removal here. */
858 if (!is_gimple_reg (gimple_phi_result (phi
)))
860 /* Virtual PHI nodes with one or identical arguments
862 if (degenerate_phi_p (phi
))
864 tree vdef
= gimple_phi_result (phi
);
865 tree vuse
= gimple_phi_arg_def (phi
, 0);
868 imm_use_iterator iter
;
870 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, vdef
)
871 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
872 SET_USE (use_p
, vuse
);
873 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef
)
874 && TREE_CODE (vuse
) == SSA_NAME
)
875 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse
) = 1;
878 gimple_set_plf (phi
, STMT_NECESSARY
, true);
881 if (!gimple_plf (phi
, STMT_NECESSARY
))
883 something_changed
= true;
884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
886 fprintf (dump_file
, "Deleting : ");
887 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
888 fprintf (dump_file
, "\n");
891 remove_phi_node (&gsi
, true);
892 stats
.removed_phis
++;
898 return something_changed
;
901 /* Find first live post dominator of BB. */
904 get_live_post_dom (basic_block bb
)
906 basic_block post_dom_bb
;
909 /* The post dominance info has to be up-to-date. */
910 gcc_assert (dom_info_state (CDI_POST_DOMINATORS
) == DOM_OK
);
912 /* Get the immediate post dominator of bb. */
913 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
914 /* And look for first live one. */
915 while (post_dom_bb
!= EXIT_BLOCK_PTR
916 && !TEST_BIT (bb_contains_live_stmts
, post_dom_bb
->index
))
917 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, post_dom_bb
);
922 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
925 forward_edge_to_pdom (edge e
, basic_block post_dom_bb
)
927 gimple_stmt_iterator gsi
;
931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
932 fprintf (dump_file
, "Redirecting edge %i->%i to %i\n", e
->src
->index
,
933 e
->dest
->index
, post_dom_bb
->index
);
935 e2
= redirect_edge_and_branch (e
, post_dom_bb
);
938 /* If edge was already around, no updating is neccesary. */
942 if (phi_nodes (post_dom_bb
))
944 /* We are sure that for every live PHI we are seeing control dependent BB.
945 This means that we can look up the end of control dependent path leading
946 to the PHI itself. */
947 FOR_EACH_EDGE (e2
, ei
, post_dom_bb
->preds
)
948 if (e2
!= e
&& dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->src
))
950 for (gsi
= gsi_start_phis (post_dom_bb
); !gsi_end_p (gsi
);)
952 gimple phi
= gsi_stmt (gsi
);
954 source_location locus
;
956 /* Dead PHI do not imply control dependency. */
957 if (!gimple_plf (phi
, STMT_NECESSARY
)
958 && is_gimple_reg (gimple_phi_result (phi
)))
963 if (gimple_phi_arg_def (phi
, e
->dest_idx
))
969 /* We didn't find edge to update. This can happen for PHIs on virtuals
970 since there is no control dependency relation on them. We are lost
971 here and must force renaming of the symbol. */
972 if (!is_gimple_reg (gimple_phi_result (phi
)))
974 mark_virtual_phi_result_for_renaming (phi
);
975 remove_phi_node (&gsi
, true);
980 op
= gimple_phi_arg_def (phi
, e
->dest_idx
== 0 ? 1 : 0);
981 locus
= gimple_phi_arg_location (phi
, e
->dest_idx
== 0 ? 1 : 0);
985 op
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
986 locus
= gimple_phi_arg_location (phi
, e2
->dest_idx
);
988 add_phi_arg (phi
, op
, e
, locus
);
989 gcc_assert (e2
|| degenerate_phi_p (phi
));
996 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
997 containing I so that we don't have to look it up. */
1000 remove_dead_stmt (gimple_stmt_iterator
*i
, basic_block bb
)
1002 gimple stmt
= gsi_stmt (*i
);
1004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1006 fprintf (dump_file
, "Deleting : ");
1007 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1008 fprintf (dump_file
, "\n");
1013 /* If we have determined that a conditional branch statement contributes
1014 nothing to the program, then we not only remove it, but we also change
1015 the flow graph so that the current block will simply fall-thru to its
1016 immediate post-dominator. The blocks we are circumventing will be
1017 removed by cleanup_tree_cfg if this change in the flow graph makes them
1019 if (is_ctrl_stmt (stmt
))
1021 basic_block post_dom_bb
;
1025 post_dom_bb
= get_live_post_dom (bb
);
1027 e
= find_edge (bb
, post_dom_bb
);
1029 /* If edge is already there, try to use it. This avoids need to update
1030 PHI nodes. Also watch for cases where post dominator does not exists
1031 or is exit block. These can happen for infinite loops as we create
1032 fake edges in the dominator tree. */
1035 else if (! post_dom_bb
|| post_dom_bb
== EXIT_BLOCK_PTR
)
1036 e
= EDGE_SUCC (bb
, 0);
1038 e
= forward_edge_to_pdom (EDGE_SUCC (bb
, 0), post_dom_bb
);
1040 e
->probability
= REG_BR_PROB_BASE
;
1041 e
->count
= bb
->count
;
1043 /* The edge is no longer associated with a conditional, so it does
1044 not have TRUE/FALSE flags. */
1045 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1047 /* The lone outgoing edge from BB will be a fallthru edge. */
1048 e
->flags
|= EDGE_FALLTHRU
;
1050 /* Remove the remaining outgoing edges. */
1051 for (ei
= ei_start (bb
->succs
); (e2
= ei_safe_edge (ei
)); )
1061 unlink_stmt_vdef (stmt
);
1062 gsi_remove (i
, true);
1063 release_defs (stmt
);
1067 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1068 contributes nothing to the program, and can be deleted. */
1071 eliminate_unnecessary_stmts (void)
1073 bool something_changed
= false;
1075 gimple_stmt_iterator gsi
;
1079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1080 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1082 clear_special_calls ();
1086 /* Remove dead statements. */
1087 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1089 stmt
= gsi_stmt (gsi
);
1093 /* If GSI is not necessary then remove it. */
1094 if (!gimple_plf (stmt
, STMT_NECESSARY
))
1096 remove_dead_stmt (&gsi
, bb
);
1097 something_changed
= true;
1099 else if (is_gimple_call (stmt
))
1101 call
= gimple_call_fndecl (stmt
);
1106 /* When LHS of var = call (); is dead, simplify it into
1107 call (); saving one operand. */
1108 name
= gimple_call_lhs (stmt
);
1109 if (name
&& TREE_CODE (name
) == SSA_NAME
1110 && !TEST_BIT (processed
, SSA_NAME_VERSION (name
)))
1112 something_changed
= true;
1113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1115 fprintf (dump_file
, "Deleting LHS of call: ");
1116 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1117 fprintf (dump_file
, "\n");
1120 gimple_call_set_lhs (stmt
, NULL_TREE
);
1121 maybe_clean_or_replace_eh_stmt (stmt
, stmt
);
1123 release_ssa_name (name
);
1125 notice_special_calls (stmt
);
1135 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1136 rendered some PHI nodes unreachable while they are still in use.
1137 Mark them for renaming. */
1140 basic_block next_bb
;
1141 find_unreachable_blocks ();
1142 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
!= EXIT_BLOCK_PTR
; bb
= next_bb
)
1144 next_bb
= bb
->next_bb
;
1145 if (!TEST_BIT (bb_contains_live_stmts
, bb
->index
)
1146 || !(bb
->flags
& BB_REACHABLE
))
1148 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1149 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi
))))
1152 imm_use_iterator iter
;
1154 FOR_EACH_IMM_USE_STMT (stmt
, iter
, gimple_phi_result (gsi_stmt (gsi
)))
1156 if (!(gimple_bb (stmt
)->flags
& BB_REACHABLE
))
1158 if (gimple_code (stmt
) == GIMPLE_PHI
1159 || gimple_plf (stmt
, STMT_NECESSARY
))
1162 BREAK_FROM_IMM_USE_STMT (iter
);
1166 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi
));
1168 if (!(bb
->flags
& BB_REACHABLE
))
1169 delete_basic_block (bb
);
1175 /* Remove dead PHI nodes. */
1176 something_changed
|= remove_dead_phis (bb
);
1179 return something_changed
;
1183 /* Print out removed statement statistics. */
1190 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1191 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1192 stats
.removed
, stats
.total
, (int) percg
);
1194 if (stats
.total_phis
== 0)
1197 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1199 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1200 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1203 /* Initialization for this pass. Set up the used data structures. */
1206 tree_dce_init (bool aggressive
)
1208 memset ((void *) &stats
, 0, sizeof (stats
));
1214 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
1215 for (i
= 0; i
< last_basic_block
; ++i
)
1216 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
1218 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
1219 sbitmap_zero (last_stmt_necessary
);
1220 bb_contains_live_stmts
= sbitmap_alloc (last_basic_block
);
1221 sbitmap_zero (bb_contains_live_stmts
);
1224 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1225 sbitmap_zero (processed
);
1227 worklist
= VEC_alloc (gimple
, heap
, 64);
1228 cfg_altered
= false;
1231 /* Cleanup after this pass. */
1234 tree_dce_done (bool aggressive
)
1240 for (i
= 0; i
< last_basic_block
; ++i
)
1241 BITMAP_FREE (control_dependence_map
[i
]);
1242 free (control_dependence_map
);
1244 sbitmap_free (visited_control_parents
);
1245 sbitmap_free (last_stmt_necessary
);
1246 sbitmap_free (bb_contains_live_stmts
);
1247 bb_contains_live_stmts
= NULL
;
1250 sbitmap_free (processed
);
1252 VEC_free (gimple
, heap
, worklist
);
1255 /* Main routine to eliminate dead code.
1257 AGGRESSIVE controls the aggressiveness of the algorithm.
1258 In conservative mode, we ignore control dependence and simply declare
1259 all but the most trivially dead branches necessary. This mode is fast.
1260 In aggressive mode, control dependences are taken into account, which
1261 results in more dead code elimination, but at the cost of some time.
1263 FIXME: Aggressive mode before PRE doesn't work currently because
1264 the dominance info is not invalidated after DCE1. This is
1265 not an issue right now because we only run aggressive DCE
1266 as the last tree SSA pass, but keep this in mind when you
1267 start experimenting with pass ordering. */
1270 perform_tree_ssa_dce (bool aggressive
)
1272 struct edge_list
*el
= NULL
;
1273 bool something_changed
= 0;
1275 /* Preheaders are needed for SCEV to work.
1276 Simple lateches and recorded exits improve chances that loop will
1277 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1279 loop_optimizer_init (LOOPS_NORMAL
1280 | LOOPS_HAVE_RECORDED_EXITS
);
1282 tree_dce_init (aggressive
);
1286 /* Compute control dependence. */
1287 timevar_push (TV_CONTROL_DEPENDENCES
);
1288 calculate_dominance_info (CDI_POST_DOMINATORS
);
1289 el
= create_edge_list ();
1290 find_all_control_dependences (el
);
1291 timevar_pop (TV_CONTROL_DEPENDENCES
);
1293 visited_control_parents
= sbitmap_alloc (last_basic_block
);
1294 sbitmap_zero (visited_control_parents
);
1296 mark_dfs_back_edges ();
1299 find_obviously_necessary_stmts (el
);
1302 loop_optimizer_finalize ();
1307 propagate_necessity (el
);
1308 BITMAP_FREE (visited
);
1310 something_changed
|= eliminate_unnecessary_stmts ();
1311 something_changed
|= cfg_altered
;
1313 /* We do not update postdominators, so free them unconditionally. */
1314 free_dominance_info (CDI_POST_DOMINATORS
);
1316 /* If we removed paths in the CFG, then we need to update
1317 dominators as well. I haven't investigated the possibility
1318 of incrementally updating dominators. */
1320 free_dominance_info (CDI_DOMINATORS
);
1322 statistics_counter_event (cfun
, "Statements deleted", stats
.removed
);
1323 statistics_counter_event (cfun
, "PHI nodes deleted", stats
.removed_phis
);
1325 /* Debugging dumps. */
1326 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1329 tree_dce_done (aggressive
);
1331 free_edge_list (el
);
1333 if (something_changed
)
1334 return (TODO_update_ssa
| TODO_cleanup_cfg
| TODO_ggc_collect
1335 | TODO_remove_unused_locals
);
1340 /* Pass entry points. */
1344 return perform_tree_ssa_dce (/*aggressive=*/false);
1348 tree_ssa_dce_loop (void)
1351 todo
= perform_tree_ssa_dce (/*aggressive=*/false);
1354 free_numbers_of_iterations_estimates ();
1361 tree_ssa_cd_dce (void)
1363 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1369 return flag_tree_dce
!= 0;
1372 struct gimple_opt_pass pass_dce
=
1377 gate_dce
, /* gate */
1378 tree_ssa_dce
, /* execute */
1381 0, /* static_pass_number */
1382 TV_TREE_DCE
, /* tv_id */
1383 PROP_cfg
| PROP_ssa
, /* properties_required */
1384 0, /* properties_provided */
1385 0, /* properties_destroyed */
1386 0, /* todo_flags_start */
1387 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1391 struct gimple_opt_pass pass_dce_loop
=
1395 "dceloop", /* name */
1396 gate_dce
, /* gate */
1397 tree_ssa_dce_loop
, /* execute */
1400 0, /* static_pass_number */
1401 TV_TREE_DCE
, /* tv_id */
1402 PROP_cfg
| PROP_ssa
, /* properties_required */
1403 0, /* properties_provided */
1404 0, /* properties_destroyed */
1405 0, /* todo_flags_start */
1406 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1410 struct gimple_opt_pass pass_cd_dce
=
1415 gate_dce
, /* gate */
1416 tree_ssa_cd_dce
, /* execute */
1419 0, /* static_pass_number */
1420 TV_TREE_CD_DCE
, /* tv_id */
1421 PROP_cfg
| PROP_ssa
, /* properties_required */
1422 0, /* properties_provided */
1423 0, /* properties_destroyed */
1424 0, /* todo_flags_start */
1425 TODO_dump_func
| TODO_verify_ssa
1426 | TODO_verify_flow
/* todo_flags_finish */