1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
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"
51 #include "diagnostic.h"
53 /* These RTL headers are needed for basic-block.h. */
56 #include "hard-reg-set.h"
58 #include "basic-block.h"
61 #include "diagnostic.h"
62 #include "tree-flow.h"
63 #include "tree-gimple.h"
64 #include "tree-dump.h"
65 #include "tree-pass.h"
69 #include "tree-scalar-evolution.h"
71 static struct stmt_stats
80 static VEC (tree
, heap
) *worklist
;
81 static VEC (tree
, heap
) *cond_dead_built_in_calls
;
83 /* Vector indicating an SSA name has already been processed and marked
85 static sbitmap processed
;
87 /* Vector indicating that last_stmt if a basic block has already been
88 marked as necessary. */
89 static sbitmap last_stmt_necessary
;
91 /* Before we can determine whether a control branch is dead, we need to
92 compute which blocks are control dependent on which edges.
94 We expect each block to be control dependent on very few edges so we
95 use a bitmap for each block recording its edges. An array holds the
96 bitmap. The Ith bit in the bitmap is set if that block is dependent
98 static bitmap
*control_dependence_map
;
100 /* Vector indicating that a basic block has already had all the edges
101 processed that it is control dependent on. */
102 static sbitmap visited_control_parents
;
104 /* TRUE if this pass alters the CFG (by removing control statements).
107 If this pass alters the CFG, then it will arrange for the dominators
109 static bool cfg_altered
;
111 /* Execute code that follows the macro for each edge (given number
112 EDGE_NUMBER within the CODE) for which the block with index N is
113 control dependent. */
114 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
115 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
119 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
121 set_control_dependence_map_bit (basic_block bb
, int edge_index
)
123 if (bb
== ENTRY_BLOCK_PTR
)
125 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
126 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
129 /* Clear all control dependences for block BB. */
131 clear_control_dependence_bitmap (basic_block bb
)
133 bitmap_clear (control_dependence_map
[bb
->index
]);
137 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
138 This function is necessary because some blocks have negative numbers. */
140 static inline basic_block
141 find_pdom (basic_block block
)
143 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
145 if (block
== EXIT_BLOCK_PTR
)
146 return EXIT_BLOCK_PTR
;
149 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
151 return EXIT_BLOCK_PTR
;
157 /* Determine all blocks' control dependences on the given edge with edge_list
158 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
161 find_control_dependence (struct edge_list
*el
, int edge_index
)
163 basic_block current_block
;
164 basic_block ending_block
;
166 gcc_assert (INDEX_EDGE_PRED_BB (el
, edge_index
) != EXIT_BLOCK_PTR
);
168 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
169 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
171 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (el
, edge_index
));
173 for (current_block
= INDEX_EDGE_SUCC_BB (el
, edge_index
);
174 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
175 current_block
= find_pdom (current_block
))
177 edge e
= INDEX_EDGE (el
, edge_index
);
179 /* For abnormal edges, we don't make current_block control
180 dependent because instructions that throw are always necessary
182 if (e
->flags
& EDGE_ABNORMAL
)
185 set_control_dependence_map_bit (current_block
, edge_index
);
190 /* Record all blocks' control dependences on all edges in the edge
191 list EL, ala Morgan, Section 3.6. */
194 find_all_control_dependences (struct edge_list
*el
)
198 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
199 find_control_dependence (el
, i
);
203 #define NECESSARY(stmt) stmt->base.asm_written_flag
205 /* Conditional dead call elimination
207 Some builtin functions can set errno on error conditions, but they
208 are otherwise pure. If the result of a call to such a function is
209 not used, the compiler can still not eliminate the call without
210 powerful interprocedural analysis to prove that the errno is not
211 checked. However, if the conditions under which the error occurs
212 are known, compiler can conditionally dead code eliminate the calls
213 by shrink-wrapping the semi-dead calls into the error condition:
217 if (error_cond(args))
220 ( An actual simple exampl is :
221 log (x); // Mostly dead call
225 With this change, call to log(x) is effectively eliminated, as
226 in majority of the cases, log won't be called with x out of
227 range. The branch is totally predicatible, so the branch cost
228 is low. Such optimization improves the performance of
229 an important application in a big search company by 20% )
231 Note that library functions are not supposed to clear errno to zero without
234 In this implementation, only 'pow' and 'log' are handled. ('sin' and 'cos'
235 seem to be wrongly handled by gcc -- they are treated as not touching errno
236 which is not correct.)
238 The condition wrapping the builtin call is conservatively set to avoid too
239 aggressive (wrong) shrink wrapping. The optimization is called conditional
240 dead call elimination because the call is eliminated under the condition
241 that the input arguments would not lead to domain or range error (for
242 instance when x <= 0 for a log(x) call), however the chances that the error
243 condition is hit is very low (those builtin calls which are conditionally
244 dead are usually part of the C++ abstraction penalty exposed after
249 check_pow (tree pow_call
)
252 enum tree_code bc
, ec
;
254 gcc_assert (TREE_CODE (pow_call
) == CALL_EXPR
);
255 if (call_expr_nargs (pow_call
) != 2)
258 base
= CALL_EXPR_ARG (pow_call
, 0);
259 expn
= CALL_EXPR_ARG (pow_call
, 1);
261 bc
= TREE_CODE (base
);
262 ec
= TREE_CODE (expn
);
264 gcc_assert (TREE_CODE_CLASS (bc
) != tcc_constant
266 gcc_assert (TREE_CODE_CLASS (ec
) != tcc_constant
269 /* Folding candidates are not interesting. */
270 if (ec
== REAL_CST
&& bc
== REAL_CST
)
275 /* Only handle a fixed range of constant. */
277 REAL_VALUE_TYPE bcv
= TREE_REAL_CST (base
);
278 if (REAL_VALUES_EQUAL (bcv
, dconst1
))
280 if (REAL_VALUES_LESS (bcv
, dconst1
))
282 real_from_integer (&mv
, VOIDmode
,256,0,1);
283 if (REAL_VALUES_LESS (mv
, bcv
))
287 else if (bc
== SSA_NAME
)
289 tree def
, nm
, rhs
, rhs0
, var
, typ
;
292 def
= SSA_NAME_DEF_STMT (base
);
293 if (TREE_CODE (def
) != GIMPLE_MODIFY_STMT
)
296 nm
= GIMPLE_STMT_OPERAND (def
,0);
297 gcc_assert (TREE_CODE (nm
) == SSA_NAME
);
301 rhs
= GIMPLE_STMT_OPERAND (def
,1);
303 if (TREE_CODE (rhs
) != FLOAT_EXPR
)
305 rhs0
= TREE_OPERAND (rhs
,0);
307 if (TREE_CODE (rhs0
) != SSA_NAME
)
310 var
= SSA_NAME_VAR (rhs0
);
311 if (TREE_CODE (var
) != VAR_DECL
&&
312 TREE_CODE (var
) != PARM_DECL
)
315 typ
= TREE_TYPE (var
);
316 if (TREE_CODE (typ
) != INTEGER_TYPE
)
318 sz
= int_size_in_bytes (typ
);
319 if (sz
== -1 || sz
> INT_TYPE_SIZE
)
329 check_log (tree log_call
)
332 gcc_assert (TREE_CODE (log_call
) == CALL_EXPR
);
333 if (call_expr_nargs (log_call
) != 1)
336 arg_typ
= TREE_TYPE (CALL_EXPR_ARG (log_call
, 0));
337 if (!is_gimple_reg_type (arg_typ
))
343 /* A helper function to determine if a builtin function
344 call is a candidate for conditional DCE. */
347 is_unnecessary_except_errno_call (tree call
)
350 bool is_unnecessary_except_errno
= false;
351 enum built_in_function fnc
;
353 if (!flag_tree_builtin_dce
)
357 gcc_assert (!DECL_P (call
));
358 gcc_assert (TREE_CODE (call
) == CALL_EXPR
);
360 fn
= get_callee_fndecl (call
);
361 if (!fn
|| !DECL_BUILT_IN (fn
))
364 fnc
= DECL_FUNCTION_CODE (fn
);
367 CASE_FLT_FN (BUILT_IN_POW
):
368 if (check_pow (call
))
369 is_unnecessary_except_errno
= true;
372 CASE_FLT_FN (BUILT_IN_LOG
):
373 if (check_log (call
))
374 is_unnecessary_except_errno
= true;
377 is_unnecessary_except_errno
= false;
381 if (!is_unnecessary_except_errno
)
384 return is_unnecessary_except_errno
;
388 /* If STMT is not already marked necessary, mark it, and add it to the
389 worklist if ADD_TO_WORKLIST is true. */
391 mark_stmt_necessary (tree stmt
, bool add_to_worklist
)
394 gcc_assert (!DECL_P (stmt
));
396 if (NECESSARY (stmt
))
399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
401 fprintf (dump_file
, "Marking useful stmt: ");
402 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
403 fprintf (dump_file
, "\n");
406 NECESSARY (stmt
) = 1;
408 VEC_safe_push (tree
, heap
, worklist
, stmt
);
412 /* Mark the statement defining operand OP as necessary. */
415 mark_operand_necessary (tree op
)
422 ver
= SSA_NAME_VERSION (op
);
423 if (TEST_BIT (processed
, ver
))
425 SET_BIT (processed
, ver
);
427 stmt
= SSA_NAME_DEF_STMT (op
);
430 if (NECESSARY (stmt
) || IS_EMPTY_STMT (stmt
))
433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
435 fprintf (dump_file
, " Marked as necessary: ");
436 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
437 fprintf (dump_file
, "\n");
440 NECESSARY (stmt
) = 1;
441 VEC_safe_push (tree
, heap
, worklist
, stmt
);
445 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
446 it can make other statements necessary.
448 If AGGRESSIVE is false, control statements are conservatively marked as
452 mark_stmt_if_obviously_necessary (tree stmt
, bool aggressive
)
457 /* With non-call exceptions, we have to assume that all statements could
458 throw. If a statement may throw, it is inherently necessary. */
459 if (flag_non_call_exceptions
460 && tree_could_throw_p (stmt
))
462 mark_stmt_necessary (stmt
, true);
466 /* Statements that are implicitly live. Most function calls, asm and return
467 statements are required. Labels and BIND_EXPR nodes are kept because
468 they are control flow, and we have no way of knowing whether they can be
469 removed. DCE can eliminate all the other statements in a block, and CFG
470 can then remove the block and labels. */
471 switch (TREE_CODE (stmt
))
475 case CASE_LABEL_EXPR
:
476 mark_stmt_necessary (stmt
, false);
482 case CHANGE_DYNAMIC_TYPE_EXPR
:
483 mark_stmt_necessary (stmt
, true);
487 /* Most, but not all function calls are required. Function calls that
488 produce no result and have no side effects (i.e. const pure
489 functions) are unnecessary. */
490 if (TREE_SIDE_EFFECTS (stmt
))
491 mark_stmt_necessary (stmt
, true);
495 case GIMPLE_MODIFY_STMT
:
496 op
= get_call_expr_in (stmt
);
497 if (op
&& TREE_SIDE_EFFECTS (op
))
499 mark_stmt_necessary (stmt
, true);
503 /* These values are mildly magic bits of the EH runtime. We can't
504 see the entire lifetime of these values until landing pads are
506 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == EXC_PTR_EXPR
507 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == FILTER_EXPR
)
509 mark_stmt_necessary (stmt
, true);
515 gcc_assert (!simple_goto_p (stmt
));
516 mark_stmt_necessary (stmt
, true);
520 gcc_assert (EDGE_COUNT (bb_for_stmt (stmt
)->succs
) == 2);
525 mark_stmt_necessary (stmt
, true);
532 ann
= stmt_ann (stmt
);
534 /* If the statement has volatile operands, it needs to be preserved.
535 Same for statements that can alter control flow in unpredictable
537 if (ann
->has_volatile_ops
|| is_ctrl_altering_stmt (stmt
))
539 mark_stmt_necessary (stmt
, true);
543 if (is_hidden_global_store (stmt
))
545 mark_stmt_necessary (stmt
, true);
553 /* Make corresponding control dependent edges necessary. We only
554 have to do this once for each basic block, so we clear the bitmap
557 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
)
560 unsigned edge_number
;
562 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
564 if (bb
== ENTRY_BLOCK_PTR
)
567 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
570 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
572 if (TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
574 SET_BIT (last_stmt_necessary
, cd_bb
->index
);
576 t
= last_stmt (cd_bb
);
577 if (t
&& is_ctrl_stmt (t
))
578 mark_stmt_necessary (t
, true);
583 /* Find obviously necessary statements. These are things like most function
584 calls, and stores to file level variables.
586 If EL is NULL, control statements are conservatively marked as
587 necessary. Otherwise it contains the list of edges used by control
588 dependence analysis. */
591 find_obviously_necessary_stmts (struct edge_list
*el
)
594 block_stmt_iterator i
;
601 /* PHI nodes are never inherently necessary. */
602 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
605 /* Check all statements in the block. */
606 for (i
= bsi_start (bb
); ! bsi_end_p (i
); bsi_next (&i
))
608 tree stmt
= bsi_stmt (i
);
609 NECESSARY (stmt
) = 0;
610 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
616 /* Prevent the loops from being removed. We must keep the infinite loops,
617 and we currently do not have a means to recognize the finite ones. */
621 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
622 if (e
->flags
& EDGE_DFS_BACK
)
623 mark_control_dependent_edges_necessary (e
->dest
, el
);
629 /* Propagate necessity using the operands of necessary statements.
630 Process the uses on each statement in the worklist, and add all
631 feeding statements which contribute to the calculation of this
632 value to the worklist.
634 In conservative mode, EL is NULL. */
637 propagate_necessity (struct edge_list
*el
)
640 bool aggressive
= (el
? true : false);
642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, "\nProcessing worklist:\n");
645 while (VEC_length (tree
, worklist
) > 0)
647 /* Take STMT from worklist. */
648 stmt
= VEC_pop (tree
, worklist
);
650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
652 fprintf (dump_file
, "processing: ");
653 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
654 fprintf (dump_file
, "\n");
659 /* Mark the last statements of the basic blocks that the block
660 containing STMT is control dependent on, but only if we haven't
662 basic_block bb
= bb_for_stmt (stmt
);
663 if (bb
!= ENTRY_BLOCK_PTR
664 && ! TEST_BIT (visited_control_parents
, bb
->index
))
666 SET_BIT (visited_control_parents
, bb
->index
);
667 mark_control_dependent_edges_necessary (bb
, el
);
671 if (TREE_CODE (stmt
) == PHI_NODE
)
673 /* PHI nodes are somewhat special in that each PHI alternative has
674 data and control dependencies. All the statements feeding the
675 PHI node's arguments are always necessary. In aggressive mode,
676 we also consider the control dependent edges leading to the
677 predecessor block associated with each PHI alternative as
681 for (k
= 0; k
< PHI_NUM_ARGS (stmt
); k
++)
683 tree arg
= PHI_ARG_DEF (stmt
, k
);
684 if (TREE_CODE (arg
) == SSA_NAME
)
685 mark_operand_necessary (arg
);
690 for (k
= 0; k
< PHI_NUM_ARGS (stmt
); k
++)
692 basic_block arg_bb
= PHI_ARG_EDGE (stmt
, k
)->src
;
693 if (arg_bb
!= ENTRY_BLOCK_PTR
694 && ! TEST_BIT (visited_control_parents
, arg_bb
->index
))
696 SET_BIT (visited_control_parents
, arg_bb
->index
);
697 mark_control_dependent_edges_necessary (arg_bb
, el
);
704 /* Propagate through the operands. Examine all the USE, VUSE and
705 VDEF operands in this statement. Mark all the statements
706 which feed this statement's uses as necessary. The
707 operands of VDEF expressions are also needed as they
708 represent potential definitions that may reach this
709 statement (VDEF operands allow us to follow def-def
714 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_ALL_USES
)
715 mark_operand_necessary (use
);
720 /* Method to generate conditional statements for guarding condionally
721 dead calls to pow. One or more statements can be generated for
722 each logical condition. Statement groups of different conditions
723 are separated by a NULL tree. */
725 gen_conditions_for_pow (tree pow_call
, enum built_in_function fnc
,
726 VEC (tree
, heap
)* conds
, unsigned * nconds
)
729 enum tree_code bc
, ec
;
730 gcc_assert (TREE_CODE (pow_call
) == CALL_EXPR
);
731 gcc_assert (call_expr_nargs (pow_call
) == 2);
732 gcc_assert (fnc
== BUILT_IN_POW
);
736 base
= CALL_EXPR_ARG (pow_call
, 0);
737 expn
= CALL_EXPR_ARG (pow_call
, 1);
739 bc
= TREE_CODE (base
);
740 ec
= TREE_CODE (expn
);
742 gcc_assert (TREE_CODE_CLASS (bc
) != tcc_constant
||
744 gcc_assert (TREE_CODE_CLASS (ec
) != tcc_constant
||
749 tree float_typ
, max_exp_real_cst
;
750 tree temp
, tempn
, tempc
, tempcn
, stmt1
, stmt2
, stmt3
;
753 /* See candidate selection in check_pow.
754 Since the candidates have a given range
755 of base values, the guard code generated
756 for such calls: pow(const,y) are simple:
759 max_y can be computed separately for each
760 const base, but in this implemetation, we
761 choose to compute it using the max base
762 in the allowed range. */
764 REAL_VALUE_TYPE bcv
= TREE_REAL_CST (base
);
765 gcc_assert (!REAL_VALUES_EQUAL (bcv
, dconst1
));
766 gcc_assert (!REAL_VALUES_LESS (bcv
, dconst1
));
767 real_from_integer (&mv
, VOIDmode
,256,0,1),
768 gcc_assert (!REAL_VALUES_LESS (mv
, bcv
));
769 float_typ
= TREE_TYPE (expn
);
771 max_exp_real_cst
= build_real (float_typ
, mv
);
772 temp
= create_tmp_var (float_typ
, "DCE_COND");
773 stmt1
= build_gimple_modify_stmt (temp
, expn
);
774 tempn
= make_ssa_name (temp
, stmt1
);
775 GIMPLE_STMT_OPERAND (stmt1
, 0) = tempn
;
777 tempc
= create_tmp_var (boolean_type_node
, "DCE_COND_TEST");
778 stmt2
= build_gimple_modify_stmt (tempc
,
781 tempn
, max_exp_real_cst
));
782 tempcn
= make_ssa_name (tempc
, stmt2
);
783 GIMPLE_STMT_OPERAND (stmt2
, 0) = tempcn
;
785 stmt3
= build3 (COND_EXPR
, void_type_node
,
786 tempcn
, NULL_TREE
, NULL_TREE
);
787 VEC_safe_push (tree
, heap
, conds
, stmt1
);
788 VEC_safe_push (tree
, heap
, conds
, stmt2
);
789 VEC_safe_push (tree
, heap
, conds
, stmt3
);
793 else if (bc
== SSA_NAME
)
795 tree def
, nm
, rhs
, rhs0
, var
, int_typ
, float_typ
;
796 tree max_exp_cst
, max_exp_real_cst
;
797 tree temp1
, temp1n
, temp2
, temp2n
, temp2c
, temp2cn
;
798 tree cst0
, stmt1
, stmt2
, stmt3
;
801 /* Generate error condition code for pow calls with
802 non constant base value. The candidates selected
803 have their base argument value converted from
804 integer (see check_pow) value (1,2,4 bytes), and
805 the max exp value is computed based on the size
806 of the integer type. The code below first does
807 sanity check and then does code generation. */
809 def
= SSA_NAME_DEF_STMT (base
);
810 gcc_assert (TREE_CODE (def
) == GIMPLE_MODIFY_STMT
);
812 nm
= GIMPLE_STMT_OPERAND (def
,0);
813 gcc_assert (TREE_CODE (nm
) == SSA_NAME
);
814 gcc_assert (nm
== base
);
816 rhs
= GIMPLE_STMT_OPERAND (def
,1);
818 gcc_assert (TREE_CODE (rhs
) == FLOAT_EXPR
);
819 rhs0
= TREE_OPERAND (rhs
,0);
820 gcc_assert (TREE_CODE (rhs0
) == SSA_NAME
);
822 var
= SSA_NAME_VAR (rhs0
);
823 gcc_assert (TREE_CODE (var
) == VAR_DECL
824 || TREE_CODE (var
) == PARM_DECL
);
826 int_typ
= TREE_TYPE (var
);
827 gcc_assert (TREE_CODE (int_typ
) == INTEGER_TYPE
);
829 sz
= int_size_in_bytes (int_typ
);
830 gcc_assert (sz
> 0 && sz
<= INT_TYPE_SIZE
) ;
833 float_typ
= TREE_TYPE (SSA_NAME_VAR (expn
));
840 gcc_assert (sz
== 4);
843 max_exp_cst
= build_int_cst (integer_type_node
, max_exp
);
844 max_exp_real_cst
= build_real_from_int_cst (float_typ
, max_exp_cst
);
846 /* For pow ((dobule)x,y), generate the following conditions:
853 if (temp2 > max_exp_real_cst) */
855 temp2
= create_tmp_var (float_typ
, "DCE_COND2");
856 stmt1
= build_gimple_modify_stmt (temp2
, expn
);
857 temp2n
= make_ssa_name (temp2
, stmt1
);
858 GIMPLE_STMT_OPERAND (stmt1
,0) = temp2n
;
860 temp2c
= create_tmp_var (boolean_type_node
, "DCE_COND2_TEST");
861 stmt2
= build_gimple_modify_stmt (temp2c
,
864 temp2n
, max_exp_real_cst
));
865 temp2cn
= make_ssa_name (temp2c
, stmt2
);
866 GIMPLE_STMT_OPERAND (stmt2
, 0) = temp2cn
;
868 stmt3
= build3 (COND_EXPR
, void_type_node
,
869 temp2cn
, NULL_TREE
, NULL_TREE
);
870 VEC_safe_push (tree
, heap
, conds
, stmt1
);
871 VEC_safe_push (tree
, heap
, conds
, stmt2
);
872 VEC_safe_push (tree
, heap
, conds
, stmt3
);
876 VEC_safe_push (tree
, heap
, conds
, NULL
);
878 temp1
= create_tmp_var (int_typ
, "DCE_COND1");
879 cst0
= build_int_cst (int_typ
, 0);
880 stmt1
= build_gimple_modify_stmt (temp1
, rhs0
);
881 temp1n
= make_ssa_name (temp1
, stmt1
);
882 GIMPLE_STMT_OPERAND (stmt1
,0) = temp1n
;
883 stmt2
= build3 (COND_EXPR
, void_type_node
,
884 build2 (LE_EXPR
, boolean_type_node
, temp1n
, cst0
),
885 NULL_TREE
, NULL_TREE
);
887 VEC_safe_push (tree
, heap
, conds
, stmt1
);
888 VEC_safe_push (tree
, heap
, conds
, stmt2
);
896 /* The method to generate error condition guard code for log(x)
899 gen_conditions_for_log (tree call
, enum built_in_function fnc
,
900 VEC (tree
, heap
)* conds
, unsigned * nconds
)
902 tree arg
, cst0
, temp
, tempn
, tempc
, tempcn
, stmt1
, stmt2
, stmt3
;
903 gcc_assert (TREE_CODE (call
) == CALL_EXPR
);
904 gcc_assert (fnc
== BUILT_IN_LOG
|| fnc
== BUILT_IN_LOGF
|| fnc
== BUILT_IN_LOGL
);
914 arg
= CALL_EXPR_ARG (call
, 0);
915 cst0
= build_real (TREE_TYPE (arg
), dconst0
);
916 temp
= create_tmp_var (TREE_TYPE (arg
), "DCE_COND");
917 stmt1
= build_gimple_modify_stmt (temp
, arg
);
918 tempn
= make_ssa_name (temp
, stmt1
);
919 GIMPLE_STMT_OPERAND (stmt1
,0) = tempn
;
921 tempc
= create_tmp_var (boolean_type_node
, "DCE_COND_TEST");
922 stmt2
= build_gimple_modify_stmt (tempc
,
926 tempcn
= make_ssa_name (tempc
, stmt2
);
927 GIMPLE_STMT_OPERAND (stmt2
, 0) = tempcn
;
929 stmt3
= build3 (COND_EXPR
, void_type_node
, tempcn
,
930 NULL_TREE
, NULL_TREE
);
932 VEC_safe_push (tree
, heap
, conds
, stmt1
);
933 VEC_safe_push (tree
, heap
, conds
, stmt2
);
934 VEC_safe_push (tree
, heap
, conds
, stmt3
);
940 /* The method to generate shrink wrap conditions for partially
941 a dead builtin call whose return value is not used anywhere,
942 but has to be kept live due to potential error condition.
944 BI_CALL: the builtin call
945 CONDS : the vector of statements for condition code
946 NCODES : the pointer to the number of logical conditions,
947 which may be different from the length of CONDS
948 vector. Statements belonging to different logical
949 condition are separated by NULL tree in the vector
953 gen_shrink_wrap_conditions (tree bi_call
, VEC (tree
, heap
)* conds
, unsigned int * nconds
)
956 enum built_in_function fnc
;
957 gcc_assert (nconds
&& conds
);
958 gcc_assert (VEC_length(tree
, conds
) == 0);
959 gcc_assert (TREE_CODE (bi_call
) == GIMPLE_MODIFY_STMT
||
960 TREE_CODE (bi_call
) == CALL_EXPR
);
963 if (TREE_CODE (call
) == GIMPLE_MODIFY_STMT
)
964 call
= get_call_expr_in (bi_call
);
966 fn
= get_callee_fndecl (call
);
967 gcc_assert (fn
&& DECL_BUILT_IN (fn
));
968 fnc
= DECL_FUNCTION_CODE (fn
);
973 /*CASE_FLT_FN(BUILT_IN_POW)*/
975 gen_conditions_for_pow (call
, fnc
, conds
, nconds
);
977 /*CASE_FLT_FN(BUILT_IN_LOG):*/
981 gen_conditions_for_log (call
, fnc
, conds
, nconds
);
988 gcc_assert (*nconds
);
993 #define ERR_PROB 0.01
995 /* The method to shrink wrap a partially dead builtin call
996 whose return value is not used anywhere, but has to be kept
997 live due to potential error condition. */
999 shrink_wrap_one_built_in_call (tree bi_call
)
1001 block_stmt_iterator bi_call_bsi
, join_tgt_bsi
;
1002 basic_block bi_call_bb
, join_tgt_bb
, guard_bb
, guard_bb0
;
1003 edge join_tgt_in_edge_from_call
, join_tgt_in_edge_fall_thru
;
1004 tree join_tgt_label_decl
, join_tgt_label
;
1005 edge bi_call_in_edge0
, guard_bb_in_edge
;
1006 VEC (tree
, heap
) *conds
;
1007 unsigned tn_cond_stmts
, nconds
;
1009 tree cond_expr
= NULL
;
1010 tree cond_expr_start
;
1011 tree bi_call_label_decl
;
1014 conds
= VEC_alloc (tree
, heap
, 10);
1015 gen_shrink_wrap_conditions (bi_call
, conds
, &nconds
);
1017 gcc_assert (nconds
> 0);
1018 /* Make sure no reallocation happens. */
1019 gcc_assert (VEC_length (tree
, conds
) <= 10);
1020 gcc_assert (VEC_length (tree
, conds
) >= nconds
);
1021 bi_call_bb
= bb_for_stmt (bi_call
);
1023 /* Now find the join target bb -- split
1024 bi_call_bb if needed */
1025 bi_call_bsi
= bsi_for_stmt (bi_call
);
1027 gcc_assert (!bsi_end_p (bi_call_bsi
));
1028 join_tgt_in_edge_from_call
= split_block (bi_call_bb
, bi_call
);
1029 bi_call_bsi
= bsi_for_stmt (bi_call
);
1031 join_tgt_bb
= join_tgt_in_edge_from_call
->dest
;
1032 join_tgt_label_decl
= create_artificial_label ();
1033 join_tgt_label
= build1 (LABEL_EXPR
, void_type_node
, join_tgt_label_decl
);
1034 join_tgt_bsi
= bsi_start (join_tgt_bb
);
1035 bsi_insert_before (&join_tgt_bsi
, join_tgt_label
, BSI_SAME_STMT
);
1037 /* Now it is time to insert the first condtional expression
1038 into bi_call_bb and split this bb so that bi_call is
1040 tn_cond_stmts
= VEC_length (tree
, conds
);
1042 cond_expr_start
= VEC_index (tree
, conds
,0);
1043 for (ci
= 0; ci
< tn_cond_stmts
; ci
++)
1045 tree c
= VEC_index (tree
, conds
, ci
);
1046 gcc_assert ( c
|| ci
!= 0 );
1048 bsi_insert_before (&bi_call_bsi
, c
, BSI_SAME_STMT
);
1053 gcc_assert (cond_expr
&& TREE_CODE (cond_expr
) == COND_EXPR
);
1056 bi_call_label_decl
= create_artificial_label ();
1057 bi_call_label
= build1 (LABEL_EXPR
, void_type_node
, bi_call_label_decl
);
1058 bsi_insert_before (&bi_call_bsi
, bi_call_label
, BSI_SAME_STMT
);
1060 bi_call_in_edge0
= split_block (bi_call_bb
, cond_expr
);
1061 bi_call_in_edge0
->flags
&= ~EDGE_FALLTHRU
;
1062 bi_call_in_edge0
->flags
|= EDGE_TRUE_VALUE
;
1063 guard_bb0
= bi_call_bb
;
1064 bi_call_bb
= bi_call_in_edge0
->dest
;
1065 join_tgt_in_edge_fall_thru
= make_edge (guard_bb0
, join_tgt_bb
, EDGE_FALSE_VALUE
);
1067 bi_call_in_edge0
->probability
= REG_BR_PROB_BASE
*ERR_PROB
;
1068 join_tgt_in_edge_fall_thru
->probability
=
1069 REG_BR_PROB_BASE
- bi_call_in_edge0
->probability
;
1071 /* code generation for the rest of the conditions */
1072 guard_bb
= guard_bb0
;
1073 for (; nconds
> 0; )
1076 edge bi_call_in_edge
;
1077 block_stmt_iterator guard_bsi
= bsi_for_stmt (cond_expr_start
);
1079 cond_expr_start
= VEC_index (tree
, conds
, ci0
);
1080 for (; ci
< tn_cond_stmts
; ci
++)
1082 tree c
= VEC_index (tree
, conds
, ci
);
1083 gcc_assert ( c
|| ci
!= ci0
);
1086 bsi_insert_before (&guard_bsi
, c
, BSI_SAME_STMT
);
1091 gcc_assert (cond_expr
&& TREE_CODE (cond_expr
) == COND_EXPR
);
1092 guard_bb_in_edge
= split_block (guard_bb
, cond_expr
);
1093 guard_bb_in_edge
->flags
&= ~EDGE_FALLTHRU
;
1094 guard_bb_in_edge
->flags
|= EDGE_FALSE_VALUE
;
1096 bi_call_in_edge
= make_edge (guard_bb
, bi_call_bb
, EDGE_TRUE_VALUE
);
1098 bi_call_in_edge
->probability
= REG_BR_PROB_BASE
*ERR_PROB
;
1099 guard_bb_in_edge
->probability
=
1100 REG_BR_PROB_BASE
- bi_call_in_edge
->probability
;
1104 VEC_free (tree
, heap
, conds
);
1105 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1108 loc
= EXPR_LOCATION (bi_call
);
1110 "%Hfunction call is shrink-wrapped into error conditions.",
1115 /* The top level method for conditional dead code shrink
1116 wrapping transformation. */
1119 shrink_wrap_conditional_dead_built_in_calls (void)
1122 unsigned n
= VEC_length (tree
, cond_dead_built_in_calls
);
1123 if (n
== 0) return false;
1127 tree bi_call
= VEC_index (tree
, cond_dead_built_in_calls
, i
);
1128 shrink_wrap_one_built_in_call (bi_call
);
1136 /* Remove dead PHI nodes from block BB. */
1139 remove_dead_phis (basic_block bb
)
1142 bool something_changed
= false;
1145 phi
= phi_nodes (bb
);
1150 if (! NECESSARY (phi
))
1152 tree next
= PHI_CHAIN (phi
);
1154 something_changed
= true;
1155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1157 fprintf (dump_file
, "Deleting : ");
1158 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1159 fprintf (dump_file
, "\n");
1162 remove_phi_node (phi
, prev
, true);
1163 stats
.removed_phis
++;
1169 phi
= PHI_CHAIN (phi
);
1172 return something_changed
;
1176 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1177 containing I so that we don't have to look it up. */
1180 remove_dead_stmt (block_stmt_iterator
*i
, basic_block bb
)
1182 tree t
= bsi_stmt (*i
);
1184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1186 fprintf (dump_file
, "Deleting : ");
1187 print_generic_stmt (dump_file
, t
, TDF_SLIM
);
1188 fprintf (dump_file
, "\n");
1193 /* If we have determined that a conditional branch statement contributes
1194 nothing to the program, then we not only remove it, but we also change
1195 the flow graph so that the current block will simply fall-thru to its
1196 immediate post-dominator. The blocks we are circumventing will be
1197 removed by cleanup_tree_cfg if this change in the flow graph makes them
1199 if (is_ctrl_stmt (t
))
1201 basic_block post_dom_bb
;
1203 /* The post dominance info has to be up-to-date. */
1204 gcc_assert (dom_info_state (CDI_POST_DOMINATORS
) == DOM_OK
);
1205 /* Get the immediate post dominator of bb. */
1206 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
1208 /* There are three particularly problematical cases.
1210 1. Blocks that do not have an immediate post dominator. This
1211 can happen with infinite loops.
1213 2. Blocks that are only post dominated by the exit block. These
1214 can also happen for infinite loops as we create fake edges
1215 in the dominator tree.
1217 3. If the post dominator has PHI nodes we may be able to compute
1218 the right PHI args for them.
1220 In each of these cases we must remove the control statement
1221 as it may reference SSA_NAMEs which are going to be removed and
1222 we remove all but one outgoing edge from the block. */
1224 || post_dom_bb
== EXIT_BLOCK_PTR
1225 || phi_nodes (post_dom_bb
))
1229 /* Redirect the first edge out of BB to reach POST_DOM_BB. */
1230 redirect_edge_and_branch (EDGE_SUCC (bb
, 0), post_dom_bb
);
1231 PENDING_STMT (EDGE_SUCC (bb
, 0)) = NULL
;
1233 /* It is not sufficient to set cfg_altered below during edge
1234 removal, in case BB has two successors and one of them
1238 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
1239 EDGE_SUCC (bb
, 0)->count
= bb
->count
;
1241 /* The edge is no longer associated with a conditional, so it does
1242 not have TRUE/FALSE flags. */
1243 EDGE_SUCC (bb
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1245 /* The lone outgoing edge from BB will be a fallthru edge. */
1246 EDGE_SUCC (bb
, 0)->flags
|= EDGE_FALLTHRU
;
1248 /* Remove the remaining the outgoing edges. */
1249 while (!single_succ_p (bb
))
1251 /* FIXME. When we remove the edge, we modify the CFG, which
1252 in turn modifies the dominator and post-dominator tree.
1253 Is it safe to postpone recomputing the dominator and
1254 post-dominator tree until the end of this pass given that
1255 the post-dominators are used above? */
1257 remove_edge (EDGE_SUCC (bb
, 1));
1261 bsi_remove (i
, true);
1266 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1267 contributes nothing to the program, and can be deleted. */
1270 eliminate_unnecessary_stmts (void)
1272 bool something_changed
= false;
1274 block_stmt_iterator i
;
1276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1277 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1279 clear_special_calls ();
1282 /* Remove dead PHI nodes. */
1283 something_changed
|= remove_dead_phis (bb
);
1288 /* Remove dead statements. */
1289 for (i
= bsi_start (bb
); ! bsi_end_p (i
) ; )
1291 tree t
= bsi_stmt (i
);
1295 /* If `i' is not necessary then remove it. */
1296 if (! NECESSARY (t
))
1298 remove_dead_stmt (&i
, bb
);
1299 something_changed
= true;
1303 tree call
= get_call_expr_in (t
);
1308 /* When LHS of var = call (); is dead, simplify it into
1309 call (); saving one operand. */
1310 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
1311 && (TREE_CODE ((name
= GIMPLE_STMT_OPERAND (t
, 0)))
1313 && !TEST_BIT (processed
, SSA_NAME_VERSION (name
)))
1315 tree oldlhs
= GIMPLE_STMT_OPERAND (t
, 0);
1316 something_changed
= true;
1317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1319 fprintf (dump_file
, "Deleting LHS of call: ");
1320 print_generic_stmt (dump_file
, t
, TDF_SLIM
);
1321 fprintf (dump_file
, "\n");
1324 if (is_unnecessary_except_errno_call (call
))
1326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1328 fprintf (dump_file
, "Found conditional dead call: ");
1329 print_generic_stmt (dump_file
, t
, TDF_SLIM
);
1330 fprintf (dump_file
, "\n");
1332 VEC_safe_push (tree
, heap
, cond_dead_built_in_calls
, call
);
1335 push_stmt_changes (bsi_stmt_ptr (i
));
1336 TREE_BLOCK (call
) = TREE_BLOCK (t
);
1337 bsi_replace (&i
, call
, false);
1338 maybe_clean_or_replace_eh_stmt (t
, call
);
1339 mark_symbols_for_renaming (call
);
1340 pop_stmt_changes (bsi_stmt_ptr (i
));
1341 release_ssa_name (oldlhs
);
1345 notice_special_calls (call
);
1352 something_changed
|=
1353 shrink_wrap_conditional_dead_built_in_calls ();
1355 return something_changed
;
1359 /* Print out removed statement statistics. */
1364 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1368 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1369 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1370 stats
.removed
, stats
.total
, (int) percg
);
1372 if (stats
.total_phis
== 0)
1375 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1377 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1378 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1382 /* Initialization for this pass. Set up the used data structures. */
1385 tree_dce_init (bool aggressive
)
1387 memset ((void *) &stats
, 0, sizeof (stats
));
1393 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
1394 for (i
= 0; i
< last_basic_block
; ++i
)
1395 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
1397 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
1398 sbitmap_zero (last_stmt_necessary
);
1401 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1402 sbitmap_zero (processed
);
1404 worklist
= VEC_alloc (tree
, heap
, 64);
1405 cond_dead_built_in_calls
= VEC_alloc (tree
, heap
,64);
1406 cfg_altered
= false;
1410 /* Cleanup after this pass. */
1413 tree_dce_done (bool aggressive
)
1419 for (i
= 0; i
< last_basic_block
; ++i
)
1420 BITMAP_FREE (control_dependence_map
[i
]);
1421 free (control_dependence_map
);
1423 sbitmap_free (visited_control_parents
);
1424 sbitmap_free (last_stmt_necessary
);
1427 sbitmap_free (processed
);
1429 VEC_free (tree
, heap
, worklist
);
1430 VEC_free (tree
, heap
, cond_dead_built_in_calls
);
1434 /* Main routine to eliminate dead code.
1436 AGGRESSIVE controls the aggressiveness of the algorithm.
1437 In conservative mode, we ignore control dependence and simply declare
1438 all but the most trivially dead branches necessary. This mode is fast.
1439 In aggressive mode, control dependences are taken into account, which
1440 results in more dead code elimination, but at the cost of some time.
1442 FIXME: Aggressive mode before PRE doesn't work currently because
1443 the dominance info is not invalidated after DCE1. This is
1444 not an issue right now because we only run aggressive DCE
1445 as the last tree SSA pass, but keep this in mind when you
1446 start experimenting with pass ordering. */
1449 perform_tree_ssa_dce (bool aggressive
)
1451 struct edge_list
*el
= NULL
;
1452 bool something_changed
= 0;
1454 tree_dce_init (aggressive
);
1458 /* Compute control dependence. */
1459 timevar_push (TV_CONTROL_DEPENDENCES
);
1460 calculate_dominance_info (CDI_POST_DOMINATORS
);
1461 el
= create_edge_list ();
1462 find_all_control_dependences (el
);
1463 timevar_pop (TV_CONTROL_DEPENDENCES
);
1465 visited_control_parents
= sbitmap_alloc (last_basic_block
);
1466 sbitmap_zero (visited_control_parents
);
1468 mark_dfs_back_edges ();
1471 find_obviously_necessary_stmts (el
);
1473 propagate_necessity (el
);
1475 something_changed
|= eliminate_unnecessary_stmts ();
1476 something_changed
|= cfg_altered
;
1478 /* We do not update postdominators, so free them unconditionally. */
1479 free_dominance_info (CDI_POST_DOMINATORS
);
1481 /* If we removed paths in the CFG, then we need to update
1482 dominators as well. I haven't investigated the possibility
1483 of incrementally updating dominators. */
1485 free_dominance_info (CDI_DOMINATORS
);
1487 /* Debugging dumps. */
1491 tree_dce_done (aggressive
);
1493 free_edge_list (el
);
1495 if (something_changed
)
1496 return (TODO_update_ssa
| TODO_cleanup_cfg
| TODO_ggc_collect
1497 | TODO_remove_unused_locals
);
1502 /* Pass entry points. */
1506 return perform_tree_ssa_dce (/*aggressive=*/false);
1510 tree_ssa_dce_loop (void)
1513 todo
= perform_tree_ssa_dce (/*aggressive=*/false);
1516 free_numbers_of_iterations_estimates ();
1523 tree_ssa_cd_dce (void)
1525 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1531 return flag_tree_dce
!= 0;
1534 struct gimple_opt_pass pass_dce
=
1539 gate_dce
, /* gate */
1540 tree_ssa_dce
, /* execute */
1543 0, /* static_pass_number */
1544 TV_TREE_DCE
, /* tv_id */
1545 PROP_cfg
| PROP_ssa
, /* properties_required */
1546 0, /* properties_provided */
1547 0, /* properties_destroyed */
1548 0, /* todo_flags_start */
1549 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1553 struct gimple_opt_pass pass_dce_loop
=
1557 "dceloop", /* name */
1558 gate_dce
, /* gate */
1559 tree_ssa_dce_loop
, /* execute */
1562 0, /* static_pass_number */
1563 TV_TREE_DCE
, /* tv_id */
1564 PROP_cfg
| PROP_ssa
, /* properties_required */
1565 0, /* properties_provided */
1566 0, /* properties_destroyed */
1567 0, /* todo_flags_start */
1568 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
1572 struct gimple_opt_pass pass_cd_dce
=
1577 gate_dce
, /* gate */
1578 tree_ssa_cd_dce
, /* execute */
1581 0, /* static_pass_number */
1582 TV_TREE_CD_DCE
, /* tv_id */
1583 PROP_cfg
| PROP_ssa
, /* properties_required */
1584 0, /* properties_provided */
1585 0, /* properties_destroyed */
1586 0, /* todo_flags_start */
1587 TODO_dump_func
| TODO_verify_ssa
1588 | TODO_verify_flow
/* todo_flags_finish */