1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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
&& !is_gimple_debug (stmt
))
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
);
328 /* Debug temps without a value are not useful. ??? If we could
329 easily locate the debug temp bind stmt for a use thereof,
330 would could refrain from marking all debug temps here, and
331 mark them only if they're used. */
332 if (gimple_debug_bind_has_value_p (stmt
)
333 || TREE_CODE (gimple_debug_bind_get_var (stmt
)) != DEBUG_EXPR_DECL
)
334 mark_stmt_necessary (stmt
, false);
338 gcc_assert (!simple_goto_p (stmt
));
339 mark_stmt_necessary (stmt
, true);
343 gcc_assert (EDGE_COUNT (gimple_bb (stmt
)->succs
) == 2);
348 mark_stmt_necessary (stmt
, true);
355 /* If the statement has volatile operands, it needs to be preserved.
356 Same for statements that can alter control flow in unpredictable
358 if (gimple_has_volatile_ops (stmt
) || is_ctrl_altering_stmt (stmt
))
360 mark_stmt_necessary (stmt
, true);
364 if (is_hidden_global_store (stmt
))
366 mark_stmt_necessary (stmt
, true);
374 /* Make corresponding control dependent edges necessary. We only
375 have to do this once for each basic block, so we clear the bitmap
378 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
)
381 unsigned edge_number
;
383 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
385 if (bb
== ENTRY_BLOCK_PTR
)
388 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
391 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
393 if (TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
395 SET_BIT (last_stmt_necessary
, cd_bb
->index
);
396 SET_BIT (bb_contains_live_stmts
, cd_bb
->index
);
398 stmt
= last_stmt (cd_bb
);
399 if (stmt
&& is_ctrl_stmt (stmt
))
400 mark_stmt_necessary (stmt
, true);
405 /* Find obviously necessary statements. These are things like most function
406 calls, and stores to file level variables.
408 If EL is NULL, control statements are conservatively marked as
409 necessary. Otherwise it contains the list of edges used by control
410 dependence analysis. */
413 find_obviously_necessary_stmts (struct edge_list
*el
)
416 gimple_stmt_iterator gsi
;
422 /* PHI nodes are never inherently necessary. */
423 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
425 phi
= gsi_stmt (gsi
);
426 gimple_set_plf (phi
, STMT_NECESSARY
, false);
429 /* Check all statements in the block. */
430 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
432 stmt
= gsi_stmt (gsi
);
433 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
434 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
438 /* Pure and const functions are finite and thus have no infinite loops in
440 if ((TREE_READONLY (current_function_decl
)
441 || DECL_PURE_P (current_function_decl
))
442 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
))
445 /* Prevent the empty possibly infinite loops from being removed. */
451 if (mark_irreducible_loops ())
455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
456 if ((e
->flags
& EDGE_DFS_BACK
)
457 && (e
->flags
& EDGE_IRREDUCIBLE_LOOP
))
460 fprintf (dump_file
, "Marking back edge of irreducible loop %i->%i\n",
461 e
->src
->index
, e
->dest
->index
);
462 mark_control_dependent_edges_necessary (e
->dest
, el
);
466 FOR_EACH_LOOP (li
, loop
, 0)
467 if (!finite_loop_p (loop
))
470 fprintf (dump_file
, "can not prove finiteness of loop %i\n", loop
->num
);
471 mark_control_dependent_edges_necessary (loop
->latch
, el
);
478 /* Return true if REF is based on an aliased base, otherwise false. */
481 ref_may_be_aliased (tree ref
)
483 while (handled_component_p (ref
))
484 ref
= TREE_OPERAND (ref
, 0);
485 return !(DECL_P (ref
)
486 && !may_be_aliased (ref
));
489 static bitmap visited
= NULL
;
490 static unsigned int longest_chain
= 0;
491 static unsigned int total_chain
= 0;
492 static unsigned int nr_walks
= 0;
493 static bool chain_ovfl
= false;
495 /* Worker for the walker that marks reaching definitions of REF,
496 which is based on a non-aliased decl, necessary. It returns
497 true whenever the defining statement of the current VDEF is
498 a kill for REF, as no dominating may-defs are necessary for REF
499 anymore. DATA points to the basic-block that contains the
500 stmt that refers to REF. */
503 mark_aliased_reaching_defs_necessary_1 (ao_ref
*ref
, tree vdef
, void *data
)
505 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
507 /* All stmts we visit are necessary. */
508 mark_operand_necessary (vdef
);
510 /* If the stmt lhs kills ref, then we can stop walking. */
511 if (gimple_has_lhs (def_stmt
)
512 && TREE_CODE (gimple_get_lhs (def_stmt
)) != SSA_NAME
)
514 tree base
, lhs
= gimple_get_lhs (def_stmt
);
515 HOST_WIDE_INT size
, offset
, max_size
;
517 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
518 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
519 so base == refd->base does not always hold. */
520 if (base
== ref
->base
)
522 /* For a must-alias check we need to be able to constrain
523 the accesses properly. */
524 if (size
!= -1 && size
== max_size
525 && ref
->max_size
!= -1)
527 if (offset
<= ref
->offset
528 && offset
+ size
>= ref
->offset
+ ref
->max_size
)
531 /* Or they need to be exactly the same. */
533 /* Make sure there is no induction variable involved
534 in the references (gcc.c-torture/execute/pr42142.c).
535 The simplest way is to check if the kill dominates
537 && dominated_by_p (CDI_DOMINATORS
, (basic_block
) data
,
538 gimple_bb (def_stmt
))
539 && operand_equal_p (ref
->ref
, lhs
, 0))
544 /* Otherwise keep walking. */
549 mark_aliased_reaching_defs_necessary (gimple stmt
, tree ref
)
553 gcc_assert (!chain_ovfl
);
554 ao_ref_init (&refd
, ref
);
555 chain
= walk_aliased_vdefs (&refd
, gimple_vuse (stmt
),
556 mark_aliased_reaching_defs_necessary_1
,
557 gimple_bb (stmt
), NULL
);
558 if (chain
> longest_chain
)
559 longest_chain
= chain
;
560 total_chain
+= chain
;
564 /* Worker for the walker that marks reaching definitions of REF, which
565 is not based on a non-aliased decl. For simplicity we need to end
566 up marking all may-defs necessary that are not based on a non-aliased
567 decl. The only job of this walker is to skip may-defs based on
568 a non-aliased decl. */
571 mark_all_reaching_defs_necessary_1 (ao_ref
*ref ATTRIBUTE_UNUSED
,
572 tree vdef
, void *data ATTRIBUTE_UNUSED
)
574 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
576 /* We have to skip already visited (and thus necessary) statements
577 to make the chaining work after we dropped back to simple mode. */
579 && TEST_BIT (processed
, SSA_NAME_VERSION (vdef
)))
581 gcc_assert (gimple_nop_p (def_stmt
)
582 || gimple_plf (def_stmt
, STMT_NECESSARY
));
586 /* We want to skip stores to non-aliased variables. */
588 && gimple_assign_single_p (def_stmt
))
590 tree lhs
= gimple_assign_lhs (def_stmt
);
591 if (!ref_may_be_aliased (lhs
))
595 mark_operand_necessary (vdef
);
601 mark_all_reaching_defs_necessary (gimple stmt
)
603 walk_aliased_vdefs (NULL
, gimple_vuse (stmt
),
604 mark_all_reaching_defs_necessary_1
, NULL
, &visited
);
607 /* Return true for PHI nodes with one or identical arguments
610 degenerate_phi_p (gimple phi
)
613 tree op
= gimple_phi_arg_def (phi
, 0);
614 for (i
= 1; i
< gimple_phi_num_args (phi
); i
++)
615 if (gimple_phi_arg_def (phi
, i
) != op
)
620 /* Propagate necessity using the operands of necessary statements.
621 Process the uses on each statement in the worklist, and add all
622 feeding statements which contribute to the calculation of this
623 value to the worklist.
625 In conservative mode, EL is NULL. */
628 propagate_necessity (struct edge_list
*el
)
631 bool aggressive
= (el
? true : false);
633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
634 fprintf (dump_file
, "\nProcessing worklist:\n");
636 while (VEC_length (gimple
, worklist
) > 0)
638 /* Take STMT from worklist. */
639 stmt
= VEC_pop (gimple
, worklist
);
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, "processing: ");
644 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
645 fprintf (dump_file
, "\n");
650 /* Mark the last statements of the basic blocks that the block
651 containing STMT is control dependent on, but only if we haven't
653 basic_block bb
= gimple_bb (stmt
);
654 if (bb
!= ENTRY_BLOCK_PTR
655 && ! TEST_BIT (visited_control_parents
, bb
->index
))
657 SET_BIT (visited_control_parents
, bb
->index
);
658 mark_control_dependent_edges_necessary (bb
, el
);
662 if (gimple_code (stmt
) == GIMPLE_PHI
663 /* We do not process virtual PHI nodes nor do we track their
665 && is_gimple_reg (gimple_phi_result (stmt
)))
667 /* PHI nodes are somewhat special in that each PHI alternative has
668 data and control dependencies. All the statements feeding the
669 PHI node's arguments are always necessary. In aggressive mode,
670 we also consider the control dependent edges leading to the
671 predecessor block associated with each PHI alternative as
675 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
677 tree arg
= PHI_ARG_DEF (stmt
, k
);
678 if (TREE_CODE (arg
) == SSA_NAME
)
679 mark_operand_necessary (arg
);
682 if (aggressive
&& !degenerate_phi_p (stmt
))
684 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
686 basic_block arg_bb
= gimple_phi_arg_edge (stmt
, k
)->src
;
687 if (arg_bb
!= ENTRY_BLOCK_PTR
688 && ! TEST_BIT (visited_control_parents
, arg_bb
->index
))
690 SET_BIT (visited_control_parents
, arg_bb
->index
);
691 mark_control_dependent_edges_necessary (arg_bb
, el
);
698 /* Propagate through the operands. Examine all the USE, VUSE and
699 VDEF operands in this statement. Mark all the statements
700 which feed this statement's uses as necessary. */
704 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
705 mark_operand_necessary (use
);
707 use
= gimple_vuse (stmt
);
711 /* If we dropped to simple mode make all immediately
712 reachable definitions necessary. */
715 mark_all_reaching_defs_necessary (stmt
);
719 /* For statements that may load from memory (have a VUSE) we
720 have to mark all reaching (may-)definitions as necessary.
721 We partition this task into two cases:
722 1) explicit loads based on decls that are not aliased
723 2) implicit loads (like calls) and explicit loads not
724 based on decls that are not aliased (like indirect
725 references or loads from globals)
726 For 1) we mark all reaching may-defs as necessary, stopping
727 at dominating kills. For 2) we want to mark all dominating
728 references necessary, but non-aliased ones which we handle
729 in 1). By keeping a global visited bitmap for references
730 we walk for 2) we avoid quadratic behavior for those. */
732 if (is_gimple_call (stmt
))
734 tree callee
= gimple_call_fndecl (stmt
);
737 /* Calls to functions that are merely acting as barriers
738 or that only store to memory do not make any previous
740 if (callee
!= NULL_TREE
741 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
742 && (DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET
743 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MALLOC
744 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_FREE
))
747 /* Calls implicitly load from memory, their arguments
748 in addition may explicitly perform memory loads. */
749 mark_all_reaching_defs_necessary (stmt
);
750 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
752 tree arg
= gimple_call_arg (stmt
, i
);
753 if (TREE_CODE (arg
) == SSA_NAME
754 || is_gimple_min_invariant (arg
))
756 if (!ref_may_be_aliased (arg
))
757 mark_aliased_reaching_defs_necessary (stmt
, arg
);
760 else if (gimple_assign_single_p (stmt
))
763 bool rhs_aliased
= false;
764 /* If this is a load mark things necessary. */
765 rhs
= gimple_assign_rhs1 (stmt
);
766 if (TREE_CODE (rhs
) != SSA_NAME
767 && !is_gimple_min_invariant (rhs
))
769 if (!ref_may_be_aliased (rhs
))
770 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
775 mark_all_reaching_defs_necessary (stmt
);
777 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
779 tree rhs
= gimple_return_retval (stmt
);
780 /* A return statement may perform a load. */
781 if (TREE_CODE (rhs
) != SSA_NAME
782 && !is_gimple_min_invariant (rhs
))
784 if (!ref_may_be_aliased (rhs
))
785 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
787 mark_all_reaching_defs_necessary (stmt
);
790 else if (gimple_code (stmt
) == GIMPLE_ASM
)
793 mark_all_reaching_defs_necessary (stmt
);
794 /* Inputs may perform loads. */
795 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
797 tree op
= TREE_VALUE (gimple_asm_input_op (stmt
, i
));
798 if (TREE_CODE (op
) != SSA_NAME
799 && !is_gimple_min_invariant (op
)
800 && !ref_may_be_aliased (op
))
801 mark_aliased_reaching_defs_necessary (stmt
, op
);
807 /* If we over-used our alias oracle budget drop to simple
808 mode. The cost metric allows quadratic behavior
809 (number of uses times number of may-defs queries) up to
810 a constant maximal number of queries and after that falls back to
811 super-linear complexity. */
812 if (/* Constant but quadratic for small functions. */
813 total_chain
> 128 * 128
814 /* Linear in the number of may-defs. */
815 && total_chain
> 32 * longest_chain
816 /* Linear in the number of uses. */
817 && total_chain
> nr_walks
* 32)
821 bitmap_clear (visited
);
827 /* Replace all uses of result of PHI by underlying variable and mark it
831 mark_virtual_phi_result_for_renaming (gimple phi
)
834 imm_use_iterator iter
;
837 tree result_ssa
, result_var
;
839 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
841 fprintf (dump_file
, "Marking result for renaming : ");
842 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
843 fprintf (dump_file
, "\n");
846 result_ssa
= gimple_phi_result (phi
);
847 result_var
= SSA_NAME_VAR (result_ssa
);
848 FOR_EACH_IMM_USE_STMT (stmt
, iter
, result_ssa
)
850 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
851 SET_USE (use_p
, result_var
);
856 mark_sym_for_renaming (result_var
);
859 /* Remove dead PHI nodes from block BB. */
862 remove_dead_phis (basic_block bb
)
864 bool something_changed
= false;
867 gimple_stmt_iterator gsi
;
868 phis
= phi_nodes (bb
);
870 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
);)
873 phi
= gsi_stmt (gsi
);
875 /* We do not track necessity of virtual PHI nodes. Instead do
876 very simple dead PHI removal here. */
877 if (!is_gimple_reg (gimple_phi_result (phi
)))
879 /* Virtual PHI nodes with one or identical arguments
881 if (degenerate_phi_p (phi
))
883 tree vdef
= gimple_phi_result (phi
);
884 tree vuse
= gimple_phi_arg_def (phi
, 0);
887 imm_use_iterator iter
;
889 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, vdef
)
890 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
891 SET_USE (use_p
, vuse
);
892 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef
)
893 && TREE_CODE (vuse
) == SSA_NAME
)
894 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse
) = 1;
897 gimple_set_plf (phi
, STMT_NECESSARY
, true);
900 if (!gimple_plf (phi
, STMT_NECESSARY
))
902 something_changed
= true;
903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
905 fprintf (dump_file
, "Deleting : ");
906 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
907 fprintf (dump_file
, "\n");
910 remove_phi_node (&gsi
, true);
911 stats
.removed_phis
++;
917 return something_changed
;
920 /* Find first live post dominator of BB. */
923 get_live_post_dom (basic_block bb
)
925 basic_block post_dom_bb
;
928 /* The post dominance info has to be up-to-date. */
929 gcc_assert (dom_info_state (CDI_POST_DOMINATORS
) == DOM_OK
);
931 /* Get the immediate post dominator of bb. */
932 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
933 /* And look for first live one. */
934 while (post_dom_bb
!= EXIT_BLOCK_PTR
935 && !TEST_BIT (bb_contains_live_stmts
, post_dom_bb
->index
))
936 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, post_dom_bb
);
941 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
944 forward_edge_to_pdom (edge e
, basic_block post_dom_bb
)
946 gimple_stmt_iterator gsi
;
950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
951 fprintf (dump_file
, "Redirecting edge %i->%i to %i\n", e
->src
->index
,
952 e
->dest
->index
, post_dom_bb
->index
);
954 e2
= redirect_edge_and_branch (e
, post_dom_bb
);
957 /* If edge was already around, no updating is neccesary. */
961 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb
)))
963 /* We are sure that for every live PHI we are seeing control dependent BB.
964 This means that we can look up the end of control dependent path leading
965 to the PHI itself. */
966 FOR_EACH_EDGE (e2
, ei
, post_dom_bb
->preds
)
967 if (e2
!= e
&& dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->src
))
969 for (gsi
= gsi_start_phis (post_dom_bb
); !gsi_end_p (gsi
);)
971 gimple phi
= gsi_stmt (gsi
);
973 source_location locus
;
975 /* Dead PHI do not imply control dependency. */
976 if (!gimple_plf (phi
, STMT_NECESSARY
)
977 && is_gimple_reg (gimple_phi_result (phi
)))
982 if (gimple_phi_arg_def (phi
, e
->dest_idx
))
988 /* We didn't find edge to update. This can happen for PHIs on virtuals
989 since there is no control dependency relation on them. We are lost
990 here and must force renaming of the symbol. */
991 if (!is_gimple_reg (gimple_phi_result (phi
)))
993 mark_virtual_phi_result_for_renaming (phi
);
994 remove_phi_node (&gsi
, true);
999 op
= gimple_phi_arg_def (phi
, e
->dest_idx
== 0 ? 1 : 0);
1000 locus
= gimple_phi_arg_location (phi
, e
->dest_idx
== 0 ? 1 : 0);
1004 op
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
1005 locus
= gimple_phi_arg_location (phi
, e2
->dest_idx
);
1007 add_phi_arg (phi
, op
, e
, locus
);
1008 gcc_assert (e2
|| degenerate_phi_p (phi
));
1015 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1016 containing I so that we don't have to look it up. */
1019 remove_dead_stmt (gimple_stmt_iterator
*i
, basic_block bb
)
1021 gimple stmt
= gsi_stmt (*i
);
1023 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1025 fprintf (dump_file
, "Deleting : ");
1026 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1027 fprintf (dump_file
, "\n");
1032 /* If we have determined that a conditional branch statement contributes
1033 nothing to the program, then we not only remove it, but we also change
1034 the flow graph so that the current block will simply fall-thru to its
1035 immediate post-dominator. The blocks we are circumventing will be
1036 removed by cleanup_tree_cfg if this change in the flow graph makes them
1038 if (is_ctrl_stmt (stmt
))
1040 basic_block post_dom_bb
;
1044 post_dom_bb
= get_live_post_dom (bb
);
1046 e
= find_edge (bb
, post_dom_bb
);
1048 /* If edge is already there, try to use it. This avoids need to update
1049 PHI nodes. Also watch for cases where post dominator does not exists
1050 or is exit block. These can happen for infinite loops as we create
1051 fake edges in the dominator tree. */
1054 else if (! post_dom_bb
|| post_dom_bb
== EXIT_BLOCK_PTR
)
1055 e
= EDGE_SUCC (bb
, 0);
1057 e
= forward_edge_to_pdom (EDGE_SUCC (bb
, 0), post_dom_bb
);
1059 e
->probability
= REG_BR_PROB_BASE
;
1060 e
->count
= bb
->count
;
1062 /* The edge is no longer associated with a conditional, so it does
1063 not have TRUE/FALSE flags. */
1064 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1066 /* The lone outgoing edge from BB will be a fallthru edge. */
1067 e
->flags
|= EDGE_FALLTHRU
;
1069 /* Remove the remaining outgoing edges. */
1070 for (ei
= ei_start (bb
->succs
); (e2
= ei_safe_edge (ei
)); )
1080 unlink_stmt_vdef (stmt
);
1081 gsi_remove (i
, true);
1082 release_defs (stmt
);
1085 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1086 contributes nothing to the program, and can be deleted. */
1089 eliminate_unnecessary_stmts (void)
1091 bool something_changed
= false;
1093 gimple_stmt_iterator gsi
, psi
;
1096 VEC (basic_block
, heap
) *h
;
1098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1099 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1101 clear_special_calls ();
1103 /* Walking basic blocks and statements in reverse order avoids
1104 releasing SSA names before any other DEFs that refer to them are
1105 released. This helps avoid loss of debug information, as we get
1106 a chance to propagate all RHSs of removed SSAs into debug uses,
1107 rather than only the latest ones. E.g., consider:
1113 If we were to release x_3 before a_5, when we reached a_5 and
1114 tried to substitute it into the debug stmt, we'd see x_3 there,
1115 but x_3's DEF, type, etc would have already been disconnected.
1116 By going backwards, the debug stmt first changes to:
1118 # DEBUG a => x_3 - b_4
1122 # DEBUG a => y_1 + z_2 - b_4
1125 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
1126 h
= get_all_dominated_blocks (CDI_DOMINATORS
, single_succ (ENTRY_BLOCK_PTR
));
1128 while (VEC_length (basic_block
, h
))
1130 bb
= VEC_pop (basic_block
, h
);
1132 /* Remove dead statements. */
1133 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi
= psi
)
1135 stmt
= gsi_stmt (gsi
);
1142 /* If GSI is not necessary then remove it. */
1143 if (!gimple_plf (stmt
, STMT_NECESSARY
))
1145 if (!is_gimple_debug (stmt
))
1146 something_changed
= true;
1147 remove_dead_stmt (&gsi
, bb
);
1149 else if (is_gimple_call (stmt
))
1151 call
= gimple_call_fndecl (stmt
);
1156 /* When LHS of var = call (); is dead, simplify it into
1157 call (); saving one operand. */
1158 name
= gimple_call_lhs (stmt
);
1159 if (name
&& TREE_CODE (name
) == SSA_NAME
1160 && !TEST_BIT (processed
, SSA_NAME_VERSION (name
)))
1162 something_changed
= true;
1163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1165 fprintf (dump_file
, "Deleting LHS of call: ");
1166 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1167 fprintf (dump_file
, "\n");
1170 gimple_call_set_lhs (stmt
, NULL_TREE
);
1171 maybe_clean_or_replace_eh_stmt (stmt
, stmt
);
1173 release_ssa_name (name
);
1175 notice_special_calls (stmt
);
1181 VEC_free (basic_block
, heap
, h
);
1183 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1184 rendered some PHI nodes unreachable while they are still in use.
1185 Mark them for renaming. */
1188 basic_block prev_bb
;
1190 find_unreachable_blocks ();
1192 /* Delete all unreachable basic blocks in reverse dominator order. */
1193 for (bb
= EXIT_BLOCK_PTR
->prev_bb
; bb
!= ENTRY_BLOCK_PTR
; bb
= prev_bb
)
1195 prev_bb
= bb
->prev_bb
;
1197 if (!TEST_BIT (bb_contains_live_stmts
, bb
->index
)
1198 || !(bb
->flags
& BB_REACHABLE
))
1200 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1201 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi
))))
1204 imm_use_iterator iter
;
1206 FOR_EACH_IMM_USE_STMT (stmt
, iter
, gimple_phi_result (gsi_stmt (gsi
)))
1208 if (!(gimple_bb (stmt
)->flags
& BB_REACHABLE
))
1210 if (gimple_code (stmt
) == GIMPLE_PHI
1211 || gimple_plf (stmt
, STMT_NECESSARY
))
1214 BREAK_FROM_IMM_USE_STMT (iter
);
1218 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi
));
1221 if (!(bb
->flags
& BB_REACHABLE
))
1223 /* Speed up the removal of blocks that don't
1224 dominate others. Walking backwards, this should
1225 be the common case. ??? Do we need to recompute
1226 dominators because of cfg_altered? */
1227 if (!MAY_HAVE_DEBUG_STMTS
1228 || !first_dom_son (CDI_DOMINATORS
, bb
))
1229 delete_basic_block (bb
);
1232 h
= get_all_dominated_blocks (CDI_DOMINATORS
, bb
);
1234 while (VEC_length (basic_block
, h
))
1236 bb
= VEC_pop (basic_block
, h
);
1237 prev_bb
= bb
->prev_bb
;
1238 /* Rearrangements to the CFG may have failed
1239 to update the dominators tree, so that
1240 formerly-dominated blocks are now
1241 otherwise reachable. */
1242 if (!!(bb
->flags
& BB_REACHABLE
))
1244 delete_basic_block (bb
);
1247 VEC_free (basic_block
, heap
, h
);
1255 /* Remove dead PHI nodes. */
1256 something_changed
|= remove_dead_phis (bb
);
1259 return something_changed
;
1263 /* Print out removed statement statistics. */
1270 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1271 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1272 stats
.removed
, stats
.total
, (int) percg
);
1274 if (stats
.total_phis
== 0)
1277 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1279 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1280 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1283 /* Initialization for this pass. Set up the used data structures. */
1286 tree_dce_init (bool aggressive
)
1288 memset ((void *) &stats
, 0, sizeof (stats
));
1294 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
1295 for (i
= 0; i
< last_basic_block
; ++i
)
1296 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
1298 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
1299 sbitmap_zero (last_stmt_necessary
);
1300 bb_contains_live_stmts
= sbitmap_alloc (last_basic_block
);
1301 sbitmap_zero (bb_contains_live_stmts
);
1304 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1305 sbitmap_zero (processed
);
1307 worklist
= VEC_alloc (gimple
, heap
, 64);
1308 cfg_altered
= false;
1311 /* Cleanup after this pass. */
1314 tree_dce_done (bool aggressive
)
1320 for (i
= 0; i
< last_basic_block
; ++i
)
1321 BITMAP_FREE (control_dependence_map
[i
]);
1322 free (control_dependence_map
);
1324 sbitmap_free (visited_control_parents
);
1325 sbitmap_free (last_stmt_necessary
);
1326 sbitmap_free (bb_contains_live_stmts
);
1327 bb_contains_live_stmts
= NULL
;
1330 sbitmap_free (processed
);
1332 VEC_free (gimple
, heap
, worklist
);
1335 /* Main routine to eliminate dead code.
1337 AGGRESSIVE controls the aggressiveness of the algorithm.
1338 In conservative mode, we ignore control dependence and simply declare
1339 all but the most trivially dead branches necessary. This mode is fast.
1340 In aggressive mode, control dependences are taken into account, which
1341 results in more dead code elimination, but at the cost of some time.
1343 FIXME: Aggressive mode before PRE doesn't work currently because
1344 the dominance info is not invalidated after DCE1. This is
1345 not an issue right now because we only run aggressive DCE
1346 as the last tree SSA pass, but keep this in mind when you
1347 start experimenting with pass ordering. */
1350 perform_tree_ssa_dce (bool aggressive
)
1352 struct edge_list
*el
= NULL
;
1353 bool something_changed
= 0;
1355 /* Preheaders are needed for SCEV to work.
1356 Simple lateches and recorded exits improve chances that loop will
1357 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1359 loop_optimizer_init (LOOPS_NORMAL
1360 | LOOPS_HAVE_RECORDED_EXITS
);
1362 tree_dce_init (aggressive
);
1366 /* Compute control dependence. */
1367 timevar_push (TV_CONTROL_DEPENDENCES
);
1368 calculate_dominance_info (CDI_POST_DOMINATORS
);
1369 el
= create_edge_list ();
1370 find_all_control_dependences (el
);
1371 timevar_pop (TV_CONTROL_DEPENDENCES
);
1373 visited_control_parents
= sbitmap_alloc (last_basic_block
);
1374 sbitmap_zero (visited_control_parents
);
1376 mark_dfs_back_edges ();
1379 find_obviously_necessary_stmts (el
);
1382 loop_optimizer_finalize ();
1388 visited
= BITMAP_ALLOC (NULL
);
1389 propagate_necessity (el
);
1390 BITMAP_FREE (visited
);
1392 something_changed
|= eliminate_unnecessary_stmts ();
1393 something_changed
|= cfg_altered
;
1395 /* We do not update postdominators, so free them unconditionally. */
1396 free_dominance_info (CDI_POST_DOMINATORS
);
1398 /* If we removed paths in the CFG, then we need to update
1399 dominators as well. I haven't investigated the possibility
1400 of incrementally updating dominators. */
1402 free_dominance_info (CDI_DOMINATORS
);
1404 statistics_counter_event (cfun
, "Statements deleted", stats
.removed
);
1405 statistics_counter_event (cfun
, "PHI nodes deleted", stats
.removed_phis
);
1407 /* Debugging dumps. */
1408 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1411 tree_dce_done (aggressive
);
1413 free_edge_list (el
);
1415 if (something_changed
)
1416 return (TODO_update_ssa
| TODO_cleanup_cfg
| TODO_ggc_collect
1417 | TODO_remove_unused_locals
);
1422 /* Pass entry points. */
1426 return perform_tree_ssa_dce (/*aggressive=*/false);
1430 tree_ssa_dce_loop (void)
1433 todo
= perform_tree_ssa_dce (/*aggressive=*/false);
1436 free_numbers_of_iterations_estimates ();
1443 tree_ssa_cd_dce (void)
1445 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1451 return flag_tree_dce
!= 0;
1454 struct gimple_opt_pass pass_dce
=
1459 gate_dce
, /* gate */
1460 tree_ssa_dce
, /* execute */
1463 0, /* static_pass_number */
1464 TV_TREE_DCE
, /* tv_id */
1465 PROP_cfg
| PROP_ssa
, /* properties_required */
1466 0, /* properties_provided */
1467 0, /* properties_destroyed */
1468 0, /* todo_flags_start */
1469 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1473 struct gimple_opt_pass pass_dce_loop
=
1477 "dceloop", /* name */
1478 gate_dce
, /* gate */
1479 tree_ssa_dce_loop
, /* execute */
1482 0, /* static_pass_number */
1483 TV_TREE_DCE
, /* tv_id */
1484 PROP_cfg
| PROP_ssa
, /* properties_required */
1485 0, /* properties_provided */
1486 0, /* properties_destroyed */
1487 0, /* todo_flags_start */
1488 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1492 struct gimple_opt_pass pass_cd_dce
=
1497 gate_dce
, /* gate */
1498 tree_ssa_cd_dce
, /* execute */
1501 0, /* static_pass_number */
1502 TV_TREE_CD_DCE
, /* tv_id */
1503 PROP_cfg
| PROP_ssa
, /* properties_required */
1504 0, /* properties_provided */
1505 0, /* properties_destroyed */
1506 0, /* todo_flags_start */
1507 TODO_dump_func
| TODO_verify_ssa
1508 | TODO_verify_flow
/* todo_flags_finish */