1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Ben Elliston <bje@redhat.com>
5 and Andrew MacLeod <amacleod@redhat.com>
6 Adapted to use control dependence by Steven Bosscher, SUSE Labs.
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 3, or (at your option) any
15 GCC is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Dead code elimination.
28 Building an Optimizing Compiler,
29 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
31 Advanced Compiler Design and Implementation,
32 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
34 Dead-code elimination is the removal of statements which have no
35 impact on the program's output. "Dead statements" have no impact
36 on the program's output, while "necessary statements" may have
39 The algorithm consists of three phases:
40 1. Marking as necessary all statements known to be necessary,
41 e.g. most function calls, writing a value to memory, etc;
42 2. Propagating necessary statements, e.g., the statements
43 giving values to operands in necessary statements; and
44 3. Removing dead statements. */
48 #include "coretypes.h"
52 #include "gimple-pretty-print.h"
53 #include "basic-block.h"
54 #include "tree-flow.h"
56 #include "tree-pass.h"
59 #include "tree-scalar-evolution.h"
61 static struct stmt_stats
69 #define STMT_NECESSARY GF_PLF_1
71 static VEC(gimple
,heap
) *worklist
;
73 /* Vector indicating an SSA name has already been processed and marked
75 static sbitmap processed
;
77 /* Vector indicating that the last statement of a basic block has already
78 been marked as necessary. */
79 static sbitmap last_stmt_necessary
;
81 /* Vector indicating that BB contains statements that are live. */
82 static sbitmap bb_contains_live_stmts
;
84 /* Before we can determine whether a control branch is dead, we need to
85 compute which blocks are control dependent on which edges.
87 We expect each block to be control dependent on very few edges so we
88 use a bitmap for each block recording its edges. An array holds the
89 bitmap. The Ith bit in the bitmap is set if that block is dependent
91 static bitmap
*control_dependence_map
;
93 /* Vector indicating that a basic block has already had all the edges
94 processed that it is control dependent on. */
95 static sbitmap visited_control_parents
;
97 /* TRUE if this pass alters the CFG (by removing control statements).
100 If this pass alters the CFG, then it will arrange for the dominators
102 static bool cfg_altered
;
104 /* Execute code that follows the macro for each edge (given number
105 EDGE_NUMBER within the CODE) for which the block with index N is
106 control dependent. */
107 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
108 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
112 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
114 set_control_dependence_map_bit (basic_block bb
, int edge_index
)
116 if (bb
== ENTRY_BLOCK_PTR
)
118 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
119 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
122 /* Clear all control dependences for block BB. */
124 clear_control_dependence_bitmap (basic_block bb
)
126 bitmap_clear (control_dependence_map
[bb
->index
]);
130 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
131 This function is necessary because some blocks have negative numbers. */
133 static inline basic_block
134 find_pdom (basic_block block
)
136 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
138 if (block
== EXIT_BLOCK_PTR
)
139 return EXIT_BLOCK_PTR
;
142 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
144 return EXIT_BLOCK_PTR
;
150 /* Determine all blocks' control dependences on the given edge with edge_list
151 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
154 find_control_dependence (struct edge_list
*el
, int edge_index
)
156 basic_block current_block
;
157 basic_block ending_block
;
159 gcc_assert (INDEX_EDGE_PRED_BB (el
, edge_index
) != EXIT_BLOCK_PTR
);
161 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
162 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
164 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (el
, edge_index
));
166 for (current_block
= INDEX_EDGE_SUCC_BB (el
, edge_index
);
167 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
168 current_block
= find_pdom (current_block
))
170 edge e
= INDEX_EDGE (el
, edge_index
);
172 /* For abnormal edges, we don't make current_block control
173 dependent because instructions that throw are always necessary
175 if (e
->flags
& EDGE_ABNORMAL
)
178 set_control_dependence_map_bit (current_block
, edge_index
);
183 /* Record all blocks' control dependences on all edges in the edge
184 list EL, ala Morgan, Section 3.6. */
187 find_all_control_dependences (struct edge_list
*el
)
191 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
192 find_control_dependence (el
, i
);
195 /* If STMT is not already marked necessary, mark it, and add it to the
196 worklist if ADD_TO_WORKLIST is true. */
199 mark_stmt_necessary (gimple stmt
, bool add_to_worklist
)
203 if (gimple_plf (stmt
, STMT_NECESSARY
))
206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
208 fprintf (dump_file
, "Marking useful stmt: ");
209 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
210 fprintf (dump_file
, "\n");
213 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
215 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
216 if (bb_contains_live_stmts
&& !is_gimple_debug (stmt
))
217 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
221 /* Mark the statement defining operand OP as necessary. */
224 mark_operand_necessary (tree op
)
231 ver
= SSA_NAME_VERSION (op
);
232 if (TEST_BIT (processed
, ver
))
234 stmt
= SSA_NAME_DEF_STMT (op
);
235 gcc_assert (gimple_nop_p (stmt
)
236 || gimple_plf (stmt
, STMT_NECESSARY
));
239 SET_BIT (processed
, ver
);
241 stmt
= SSA_NAME_DEF_STMT (op
);
244 if (gimple_plf (stmt
, STMT_NECESSARY
) || gimple_nop_p (stmt
))
247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
249 fprintf (dump_file
, "marking necessary through ");
250 print_generic_expr (dump_file
, op
, 0);
251 fprintf (dump_file
, " stmt ");
252 print_gimple_stmt (dump_file
, stmt
, 0, 0);
255 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
256 if (bb_contains_live_stmts
)
257 SET_BIT (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
258 VEC_safe_push (gimple
, heap
, worklist
, stmt
);
262 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
263 it can make other statements necessary.
265 If AGGRESSIVE is false, control statements are conservatively marked as
269 mark_stmt_if_obviously_necessary (gimple stmt
, bool aggressive
)
271 /* With non-call exceptions, we have to assume that all statements could
272 throw. If a statement could throw, it can be deemed necessary. */
273 if (cfun
->can_throw_non_call_exceptions
274 && !cfun
->can_delete_dead_exceptions
275 && stmt_could_throw_p (stmt
))
277 mark_stmt_necessary (stmt
, true);
281 /* Statements that are implicitly live. Most function calls, asm
282 and return statements are required. Labels and GIMPLE_BIND nodes
283 are kept because they are control flow, and we have no way of
284 knowing whether they can be removed. DCE can eliminate all the
285 other statements in a block, and CFG can then remove the block
287 switch (gimple_code (stmt
))
291 mark_stmt_necessary (stmt
, false);
297 mark_stmt_necessary (stmt
, true);
302 tree callee
= gimple_call_fndecl (stmt
);
303 if (callee
!= NULL_TREE
304 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
305 switch (DECL_FUNCTION_CODE (callee
))
307 case BUILT_IN_MALLOC
:
308 case BUILT_IN_CALLOC
:
309 case BUILT_IN_ALLOCA
:
310 case BUILT_IN_ALLOCA_WITH_ALIGN
:
315 /* Most, but not all function calls are required. Function calls that
316 produce no result and have no side effects (i.e. const pure
317 functions) are unnecessary. */
318 if (gimple_has_side_effects (stmt
))
320 mark_stmt_necessary (stmt
, true);
323 if (!gimple_call_lhs (stmt
))
329 /* Debug temps without a value are not useful. ??? If we could
330 easily locate the debug temp bind stmt for a use thereof,
331 would could refrain from marking all debug temps here, and
332 mark them only if they're used. */
333 if (!gimple_debug_bind_p (stmt
)
334 || gimple_debug_bind_has_value_p (stmt
)
335 || TREE_CODE (gimple_debug_bind_get_var (stmt
)) != DEBUG_EXPR_DECL
)
336 mark_stmt_necessary (stmt
, false);
340 gcc_assert (!simple_goto_p (stmt
));
341 mark_stmt_necessary (stmt
, true);
345 gcc_assert (EDGE_COUNT (gimple_bb (stmt
)->succs
) == 2);
350 mark_stmt_necessary (stmt
, true);
354 if (TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
355 && TREE_CLOBBER_P (gimple_assign_rhs1 (stmt
)))
363 /* If the statement has volatile operands, it needs to be preserved.
364 Same for statements that can alter control flow in unpredictable
366 if (gimple_has_volatile_ops (stmt
) || is_ctrl_altering_stmt (stmt
))
368 mark_stmt_necessary (stmt
, true);
372 if (stmt_may_clobber_global_p (stmt
))
374 mark_stmt_necessary (stmt
, true);
382 /* Mark the last statement of BB as necessary. */
385 mark_last_stmt_necessary (basic_block bb
)
387 gimple stmt
= last_stmt (bb
);
389 SET_BIT (last_stmt_necessary
, bb
->index
);
390 SET_BIT (bb_contains_live_stmts
, bb
->index
);
392 /* We actually mark the statement only if it is a control statement. */
393 if (stmt
&& is_ctrl_stmt (stmt
))
394 mark_stmt_necessary (stmt
, true);
398 /* Mark control dependent edges of BB as necessary. We have to do this only
399 once for each basic block so we set the appropriate bit after we're done.
401 When IGNORE_SELF is true, ignore BB in the list of control dependences. */
404 mark_control_dependent_edges_necessary (basic_block bb
, struct edge_list
*el
,
408 unsigned edge_number
;
409 bool skipped
= false;
411 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
413 if (bb
== ENTRY_BLOCK_PTR
)
416 EXECUTE_IF_CONTROL_DEPENDENT (bi
, bb
->index
, edge_number
)
418 basic_block cd_bb
= INDEX_EDGE_PRED_BB (el
, edge_number
);
420 if (ignore_self
&& cd_bb
== bb
)
426 if (!TEST_BIT (last_stmt_necessary
, cd_bb
->index
))
427 mark_last_stmt_necessary (cd_bb
);
431 SET_BIT (visited_control_parents
, bb
->index
);
435 /* Find obviously necessary statements. These are things like most function
436 calls, and stores to file level variables.
438 If EL is NULL, control statements are conservatively marked as
439 necessary. Otherwise it contains the list of edges used by control
440 dependence analysis. */
443 find_obviously_necessary_stmts (struct edge_list
*el
)
446 gimple_stmt_iterator gsi
;
453 /* PHI nodes are never inherently necessary. */
454 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
456 phi
= gsi_stmt (gsi
);
457 gimple_set_plf (phi
, STMT_NECESSARY
, false);
460 /* Check all statements in the block. */
461 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
463 stmt
= gsi_stmt (gsi
);
464 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
465 mark_stmt_if_obviously_necessary (stmt
, el
!= NULL
);
469 /* Pure and const functions are finite and thus have no infinite loops in
471 flags
= flags_from_decl_or_type (current_function_decl
);
472 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
475 /* Prevent the empty possibly infinite loops from being removed. */
481 if (mark_irreducible_loops ())
485 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
486 if ((e
->flags
& EDGE_DFS_BACK
)
487 && (e
->flags
& EDGE_IRREDUCIBLE_LOOP
))
490 fprintf (dump_file
, "Marking back edge of irreducible loop %i->%i\n",
491 e
->src
->index
, e
->dest
->index
);
492 mark_control_dependent_edges_necessary (e
->dest
, el
, false);
496 FOR_EACH_LOOP (li
, loop
, 0)
497 if (!finite_loop_p (loop
))
500 fprintf (dump_file
, "can not prove finiteness of loop %i\n", loop
->num
);
501 mark_control_dependent_edges_necessary (loop
->latch
, el
, false);
508 /* Return true if REF is based on an aliased base, otherwise false. */
511 ref_may_be_aliased (tree ref
)
513 gcc_assert (TREE_CODE (ref
) != WITH_SIZE_EXPR
);
514 while (handled_component_p (ref
))
515 ref
= TREE_OPERAND (ref
, 0);
516 if (TREE_CODE (ref
) == MEM_REF
517 && TREE_CODE (TREE_OPERAND (ref
, 0)) == ADDR_EXPR
)
518 ref
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
519 return !(DECL_P (ref
)
520 && !may_be_aliased (ref
));
523 static bitmap visited
= NULL
;
524 static unsigned int longest_chain
= 0;
525 static unsigned int total_chain
= 0;
526 static unsigned int nr_walks
= 0;
527 static bool chain_ovfl
= false;
529 /* Worker for the walker that marks reaching definitions of REF,
530 which is based on a non-aliased decl, necessary. It returns
531 true whenever the defining statement of the current VDEF is
532 a kill for REF, as no dominating may-defs are necessary for REF
533 anymore. DATA points to the basic-block that contains the
534 stmt that refers to REF. */
537 mark_aliased_reaching_defs_necessary_1 (ao_ref
*ref
, tree vdef
, void *data
)
539 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
541 /* All stmts we visit are necessary. */
542 mark_operand_necessary (vdef
);
544 /* If the stmt lhs kills ref, then we can stop walking. */
545 if (gimple_has_lhs (def_stmt
)
546 && TREE_CODE (gimple_get_lhs (def_stmt
)) != SSA_NAME
547 /* The assignment is not necessarily carried out if it can throw
548 and we can catch it in the current function where we could inspect
550 ??? We only need to care about the RHS throwing. For aggregate
551 assignments or similar calls and non-call exceptions the LHS
552 might throw as well. */
553 && !stmt_can_throw_internal (def_stmt
))
555 tree base
, lhs
= gimple_get_lhs (def_stmt
);
556 HOST_WIDE_INT size
, offset
, max_size
;
558 base
= get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
);
559 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
560 so base == refd->base does not always hold. */
561 if (base
== ref
->base
)
563 /* For a must-alias check we need to be able to constrain
564 the accesses properly. */
565 if (size
!= -1 && size
== max_size
566 && ref
->max_size
!= -1)
568 if (offset
<= ref
->offset
569 && offset
+ size
>= ref
->offset
+ ref
->max_size
)
572 /* Or they need to be exactly the same. */
574 /* Make sure there is no induction variable involved
575 in the references (gcc.c-torture/execute/pr42142.c).
576 The simplest way is to check if the kill dominates
578 && dominated_by_p (CDI_DOMINATORS
, (basic_block
) data
,
579 gimple_bb (def_stmt
))
580 && operand_equal_p (ref
->ref
, lhs
, 0))
585 /* Otherwise keep walking. */
590 mark_aliased_reaching_defs_necessary (gimple stmt
, tree ref
)
594 gcc_assert (!chain_ovfl
);
595 ao_ref_init (&refd
, ref
);
596 chain
= walk_aliased_vdefs (&refd
, gimple_vuse (stmt
),
597 mark_aliased_reaching_defs_necessary_1
,
598 gimple_bb (stmt
), NULL
);
599 if (chain
> longest_chain
)
600 longest_chain
= chain
;
601 total_chain
+= chain
;
605 /* Worker for the walker that marks reaching definitions of REF, which
606 is not based on a non-aliased decl. For simplicity we need to end
607 up marking all may-defs necessary that are not based on a non-aliased
608 decl. The only job of this walker is to skip may-defs based on
609 a non-aliased decl. */
612 mark_all_reaching_defs_necessary_1 (ao_ref
*ref ATTRIBUTE_UNUSED
,
613 tree vdef
, void *data ATTRIBUTE_UNUSED
)
615 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
617 /* We have to skip already visited (and thus necessary) statements
618 to make the chaining work after we dropped back to simple mode. */
620 && TEST_BIT (processed
, SSA_NAME_VERSION (vdef
)))
622 gcc_assert (gimple_nop_p (def_stmt
)
623 || gimple_plf (def_stmt
, STMT_NECESSARY
));
627 /* We want to skip stores to non-aliased variables. */
629 && gimple_assign_single_p (def_stmt
))
631 tree lhs
= gimple_assign_lhs (def_stmt
);
632 if (!ref_may_be_aliased (lhs
))
636 /* We want to skip statments that do not constitute stores but have
637 a virtual definition. */
638 if (is_gimple_call (def_stmt
))
640 tree callee
= gimple_call_fndecl (def_stmt
);
641 if (callee
!= NULL_TREE
642 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
643 switch (DECL_FUNCTION_CODE (callee
))
645 case BUILT_IN_MALLOC
:
646 case BUILT_IN_CALLOC
:
647 case BUILT_IN_ALLOCA
:
648 case BUILT_IN_ALLOCA_WITH_ALIGN
:
656 mark_operand_necessary (vdef
);
662 mark_all_reaching_defs_necessary (gimple stmt
)
664 walk_aliased_vdefs (NULL
, gimple_vuse (stmt
),
665 mark_all_reaching_defs_necessary_1
, NULL
, &visited
);
668 /* Return true for PHI nodes with one or identical arguments
671 degenerate_phi_p (gimple phi
)
674 tree op
= gimple_phi_arg_def (phi
, 0);
675 for (i
= 1; i
< gimple_phi_num_args (phi
); i
++)
676 if (gimple_phi_arg_def (phi
, i
) != op
)
681 /* Propagate necessity using the operands of necessary statements.
682 Process the uses on each statement in the worklist, and add all
683 feeding statements which contribute to the calculation of this
684 value to the worklist.
686 In conservative mode, EL is NULL. */
689 propagate_necessity (struct edge_list
*el
)
692 bool aggressive
= (el
? true : false);
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
695 fprintf (dump_file
, "\nProcessing worklist:\n");
697 while (VEC_length (gimple
, worklist
) > 0)
699 /* Take STMT from worklist. */
700 stmt
= VEC_pop (gimple
, worklist
);
702 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
704 fprintf (dump_file
, "processing: ");
705 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
706 fprintf (dump_file
, "\n");
711 /* Mark the last statement of the basic blocks on which the block
712 containing STMT is control dependent, but only if we haven't
714 basic_block bb
= gimple_bb (stmt
);
715 if (bb
!= ENTRY_BLOCK_PTR
716 && !TEST_BIT (visited_control_parents
, bb
->index
))
717 mark_control_dependent_edges_necessary (bb
, el
, false);
720 if (gimple_code (stmt
) == GIMPLE_PHI
721 /* We do not process virtual PHI nodes nor do we track their
723 && !virtual_operand_p (gimple_phi_result (stmt
)))
725 /* PHI nodes are somewhat special in that each PHI alternative has
726 data and control dependencies. All the statements feeding the
727 PHI node's arguments are always necessary. In aggressive mode,
728 we also consider the control dependent edges leading to the
729 predecessor block associated with each PHI alternative as
733 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
735 tree arg
= PHI_ARG_DEF (stmt
, k
);
736 if (TREE_CODE (arg
) == SSA_NAME
)
737 mark_operand_necessary (arg
);
740 /* For PHI operands it matters from where the control flow arrives
741 to the BB. Consider the following example:
751 We need to mark control dependence of the empty basic blocks, since they
752 contains computation of PHI operands.
754 Doing so is too restrictive in the case the predecestor block is in
760 for (i = 0; i<1000; ++i)
766 There is PHI for J in the BB containing return statement.
767 In this case the control dependence of predecestor block (that is
768 within the empty loop) also contains the block determining number
769 of iterations of the block that would prevent removing of empty
772 This scenario can be avoided by splitting critical edges.
773 To save the critical edge splitting pass we identify how the control
774 dependence would look like if the edge was split.
776 Consider the modified CFG created from current CFG by splitting
777 edge B->C. In the postdominance tree of modified CFG, C' is
778 always child of C. There are two cases how chlids of C' can look
783 In this case the only basic block C' is control dependent on is B.
785 2) C' has single child that is B
787 In this case control dependence of C' is same as control
788 dependence of B in original CFG except for block B itself.
789 (since C' postdominate B in modified CFG)
791 Now how to decide what case happens? There are two basic options:
793 a) C postdominate B. Then C immediately postdominate B and
794 case 2 happens iff there is no other way from B to C except
797 There is other way from B to C iff there is succesor of B that
798 is not postdominated by B. Testing this condition is somewhat
799 expensive, because we need to iterate all succesors of B.
800 We are safe to assume that this does not happen: we will mark B
801 as needed when processing the other path from B to C that is
802 conrol dependent on B and marking control dependencies of B
803 itself is harmless because they will be processed anyway after
804 processing control statement in B.
806 b) C does not postdominate B. Always case 1 happens since there is
807 path from C to exit that does not go through B and thus also C'. */
809 if (aggressive
&& !degenerate_phi_p (stmt
))
811 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
813 basic_block arg_bb
= gimple_phi_arg_edge (stmt
, k
)->src
;
816 != get_immediate_dominator (CDI_POST_DOMINATORS
, arg_bb
))
818 if (!TEST_BIT (last_stmt_necessary
, arg_bb
->index
))
819 mark_last_stmt_necessary (arg_bb
);
821 else if (arg_bb
!= ENTRY_BLOCK_PTR
822 && !TEST_BIT (visited_control_parents
,
824 mark_control_dependent_edges_necessary (arg_bb
, el
, true);
830 /* Propagate through the operands. Examine all the USE, VUSE and
831 VDEF operands in this statement. Mark all the statements
832 which feed this statement's uses as necessary. */
836 /* If this is a call to free which is directly fed by an
837 allocation function do not mark that necessary through
838 processing the argument. */
839 if (gimple_call_builtin_p (stmt
, BUILT_IN_FREE
))
841 tree ptr
= gimple_call_arg (stmt
, 0);
844 /* If the pointer we free is defined by an allocation
845 function do not add the call to the worklist. */
846 if (TREE_CODE (ptr
) == SSA_NAME
847 && is_gimple_call (def_stmt
= SSA_NAME_DEF_STMT (ptr
))
848 && (def_callee
= gimple_call_fndecl (def_stmt
))
849 && DECL_BUILT_IN_CLASS (def_callee
) == BUILT_IN_NORMAL
850 && (DECL_FUNCTION_CODE (def_callee
) == BUILT_IN_MALLOC
851 || DECL_FUNCTION_CODE (def_callee
) == BUILT_IN_CALLOC
))
855 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
856 mark_operand_necessary (use
);
858 use
= gimple_vuse (stmt
);
862 /* If we dropped to simple mode make all immediately
863 reachable definitions necessary. */
866 mark_all_reaching_defs_necessary (stmt
);
870 /* For statements that may load from memory (have a VUSE) we
871 have to mark all reaching (may-)definitions as necessary.
872 We partition this task into two cases:
873 1) explicit loads based on decls that are not aliased
874 2) implicit loads (like calls) and explicit loads not
875 based on decls that are not aliased (like indirect
876 references or loads from globals)
877 For 1) we mark all reaching may-defs as necessary, stopping
878 at dominating kills. For 2) we want to mark all dominating
879 references necessary, but non-aliased ones which we handle
880 in 1). By keeping a global visited bitmap for references
881 we walk for 2) we avoid quadratic behavior for those. */
883 if (is_gimple_call (stmt
))
885 tree callee
= gimple_call_fndecl (stmt
);
888 /* Calls to functions that are merely acting as barriers
889 or that only store to memory do not make any previous
891 if (callee
!= NULL_TREE
892 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
893 && (DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET
894 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET_CHK
895 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MALLOC
896 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_CALLOC
897 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_FREE
898 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_VA_END
899 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_ALLOCA
900 || (DECL_FUNCTION_CODE (callee
)
901 == BUILT_IN_ALLOCA_WITH_ALIGN
)
902 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_STACK_SAVE
903 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_STACK_RESTORE
904 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_ASSUME_ALIGNED
))
907 /* Calls implicitly load from memory, their arguments
908 in addition may explicitly perform memory loads. */
909 mark_all_reaching_defs_necessary (stmt
);
910 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
912 tree arg
= gimple_call_arg (stmt
, i
);
913 if (TREE_CODE (arg
) == SSA_NAME
914 || is_gimple_min_invariant (arg
))
916 if (TREE_CODE (arg
) == WITH_SIZE_EXPR
)
917 arg
= TREE_OPERAND (arg
, 0);
918 if (!ref_may_be_aliased (arg
))
919 mark_aliased_reaching_defs_necessary (stmt
, arg
);
922 else if (gimple_assign_single_p (stmt
))
925 /* If this is a load mark things necessary. */
926 rhs
= gimple_assign_rhs1 (stmt
);
927 if (TREE_CODE (rhs
) != SSA_NAME
928 && !is_gimple_min_invariant (rhs
)
929 && TREE_CODE (rhs
) != CONSTRUCTOR
)
931 if (!ref_may_be_aliased (rhs
))
932 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
934 mark_all_reaching_defs_necessary (stmt
);
937 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
939 tree rhs
= gimple_return_retval (stmt
);
940 /* A return statement may perform a load. */
942 && TREE_CODE (rhs
) != SSA_NAME
943 && !is_gimple_min_invariant (rhs
)
944 && TREE_CODE (rhs
) != CONSTRUCTOR
)
946 if (!ref_may_be_aliased (rhs
))
947 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
949 mark_all_reaching_defs_necessary (stmt
);
952 else if (gimple_code (stmt
) == GIMPLE_ASM
)
955 mark_all_reaching_defs_necessary (stmt
);
956 /* Inputs may perform loads. */
957 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
959 tree op
= TREE_VALUE (gimple_asm_input_op (stmt
, i
));
960 if (TREE_CODE (op
) != SSA_NAME
961 && !is_gimple_min_invariant (op
)
962 && TREE_CODE (op
) != CONSTRUCTOR
963 && !ref_may_be_aliased (op
))
964 mark_aliased_reaching_defs_necessary (stmt
, op
);
967 else if (gimple_code (stmt
) == GIMPLE_TRANSACTION
)
969 /* The beginning of a transaction is a memory barrier. */
970 /* ??? If we were really cool, we'd only be a barrier
971 for the memories touched within the transaction. */
972 mark_all_reaching_defs_necessary (stmt
);
977 /* If we over-used our alias oracle budget drop to simple
978 mode. The cost metric allows quadratic behavior
979 (number of uses times number of may-defs queries) up to
980 a constant maximal number of queries and after that falls back to
981 super-linear complexity. */
982 if (/* Constant but quadratic for small functions. */
983 total_chain
> 128 * 128
984 /* Linear in the number of may-defs. */
985 && total_chain
> 32 * longest_chain
986 /* Linear in the number of uses. */
987 && total_chain
> nr_walks
* 32)
991 bitmap_clear (visited
);
997 /* Replace all uses of NAME by underlying variable and mark it
998 for renaming. This assumes the defining statement of NAME is
999 going to be removed. */
1002 mark_virtual_operand_for_renaming (tree name
)
1004 tree name_var
= SSA_NAME_VAR (name
);
1006 imm_use_iterator iter
;
1007 use_operand_p use_p
;
1010 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
1011 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1013 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
1014 SET_USE (use_p
, name_var
);
1018 mark_virtual_operands_for_renaming (cfun
);
1021 /* Replace all uses of the virtual PHI result by its underlying variable
1022 and mark it for renaming. This assumes the PHI node is going to be
1026 mark_virtual_phi_result_for_renaming (gimple phi
)
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "Marking result for renaming : ");
1031 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1032 fprintf (dump_file
, "\n");
1035 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
1039 /* Remove dead PHI nodes from block BB. */
1042 remove_dead_phis (basic_block bb
)
1044 bool something_changed
= false;
1046 gimple_stmt_iterator gsi
;
1048 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);)
1051 phi
= gsi_stmt (gsi
);
1053 /* We do not track necessity of virtual PHI nodes. Instead do
1054 very simple dead PHI removal here. */
1055 if (virtual_operand_p (gimple_phi_result (phi
)))
1057 /* Virtual PHI nodes with one or identical arguments
1059 if (degenerate_phi_p (phi
))
1061 tree vdef
= gimple_phi_result (phi
);
1062 tree vuse
= gimple_phi_arg_def (phi
, 0);
1064 use_operand_p use_p
;
1065 imm_use_iterator iter
;
1067 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, vdef
)
1068 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
1069 SET_USE (use_p
, vuse
);
1070 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef
)
1071 && TREE_CODE (vuse
) == SSA_NAME
)
1072 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse
) = 1;
1075 gimple_set_plf (phi
, STMT_NECESSARY
, true);
1078 if (!gimple_plf (phi
, STMT_NECESSARY
))
1080 something_changed
= true;
1081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1083 fprintf (dump_file
, "Deleting : ");
1084 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1085 fprintf (dump_file
, "\n");
1088 remove_phi_node (&gsi
, true);
1089 stats
.removed_phis
++;
1095 return something_changed
;
1098 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
1101 forward_edge_to_pdom (edge e
, basic_block post_dom_bb
)
1103 gimple_stmt_iterator gsi
;
1107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1108 fprintf (dump_file
, "Redirecting edge %i->%i to %i\n", e
->src
->index
,
1109 e
->dest
->index
, post_dom_bb
->index
);
1111 e2
= redirect_edge_and_branch (e
, post_dom_bb
);
1114 /* If edge was already around, no updating is neccesary. */
1118 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb
)))
1120 /* We are sure that for every live PHI we are seeing control dependent BB.
1121 This means that we can pick any edge to duplicate PHI args from. */
1122 FOR_EACH_EDGE (e2
, ei
, post_dom_bb
->preds
)
1125 for (gsi
= gsi_start_phis (post_dom_bb
); !gsi_end_p (gsi
);)
1127 gimple phi
= gsi_stmt (gsi
);
1129 source_location locus
;
1131 /* PHIs for virtuals have no control dependency relation on them.
1132 We are lost here and must force renaming of the symbol. */
1133 if (virtual_operand_p (gimple_phi_result (phi
)))
1135 mark_virtual_phi_result_for_renaming (phi
);
1136 remove_phi_node (&gsi
, true);
1140 /* Dead PHI do not imply control dependency. */
1141 if (!gimple_plf (phi
, STMT_NECESSARY
))
1147 op
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
1148 locus
= gimple_phi_arg_location (phi
, e2
->dest_idx
);
1149 add_phi_arg (phi
, op
, e
, locus
);
1150 /* The resulting PHI if not dead can only be degenerate. */
1151 gcc_assert (degenerate_phi_p (phi
));
1158 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1159 containing I so that we don't have to look it up. */
1162 remove_dead_stmt (gimple_stmt_iterator
*i
, basic_block bb
)
1164 gimple stmt
= gsi_stmt (*i
);
1166 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1168 fprintf (dump_file
, "Deleting : ");
1169 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1170 fprintf (dump_file
, "\n");
1175 /* If we have determined that a conditional branch statement contributes
1176 nothing to the program, then we not only remove it, but we also change
1177 the flow graph so that the current block will simply fall-thru to its
1178 immediate post-dominator. The blocks we are circumventing will be
1179 removed by cleanup_tree_cfg if this change in the flow graph makes them
1181 if (is_ctrl_stmt (stmt
))
1183 basic_block post_dom_bb
;
1187 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
1189 e
= find_edge (bb
, post_dom_bb
);
1191 /* If edge is already there, try to use it. This avoids need to update
1192 PHI nodes. Also watch for cases where post dominator does not exists
1193 or is exit block. These can happen for infinite loops as we create
1194 fake edges in the dominator tree. */
1197 else if (! post_dom_bb
|| post_dom_bb
== EXIT_BLOCK_PTR
)
1198 e
= EDGE_SUCC (bb
, 0);
1200 e
= forward_edge_to_pdom (EDGE_SUCC (bb
, 0), post_dom_bb
);
1202 e
->probability
= REG_BR_PROB_BASE
;
1203 e
->count
= bb
->count
;
1205 /* The edge is no longer associated with a conditional, so it does
1206 not have TRUE/FALSE flags. */
1207 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1209 /* The lone outgoing edge from BB will be a fallthru edge. */
1210 e
->flags
|= EDGE_FALLTHRU
;
1212 /* Remove the remaining outgoing edges. */
1213 for (ei
= ei_start (bb
->succs
); (e2
= ei_safe_edge (ei
)); )
1223 /* If this is a store into a variable that is being optimized away,
1224 add a debug bind stmt if possible. */
1225 if (MAY_HAVE_DEBUG_STMTS
1226 && gimple_assign_single_p (stmt
)
1227 && is_gimple_val (gimple_assign_rhs1 (stmt
)))
1229 tree lhs
= gimple_assign_lhs (stmt
);
1230 if ((TREE_CODE (lhs
) == VAR_DECL
|| TREE_CODE (lhs
) == PARM_DECL
)
1231 && !DECL_IGNORED_P (lhs
)
1232 && is_gimple_reg_type (TREE_TYPE (lhs
))
1233 && !is_global_var (lhs
)
1234 && !DECL_HAS_VALUE_EXPR_P (lhs
))
1236 tree rhs
= gimple_assign_rhs1 (stmt
);
1238 = gimple_build_debug_bind (lhs
, unshare_expr (rhs
), stmt
);
1239 gsi_insert_after (i
, note
, GSI_SAME_STMT
);
1243 unlink_stmt_vdef (stmt
);
1244 gsi_remove (i
, true);
1245 release_defs (stmt
);
1248 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1249 contributes nothing to the program, and can be deleted. */
1252 eliminate_unnecessary_stmts (void)
1254 bool something_changed
= false;
1256 gimple_stmt_iterator gsi
, psi
;
1259 VEC (basic_block
, heap
) *h
;
1261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1262 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1264 clear_special_calls ();
1266 /* Walking basic blocks and statements in reverse order avoids
1267 releasing SSA names before any other DEFs that refer to them are
1268 released. This helps avoid loss of debug information, as we get
1269 a chance to propagate all RHSs of removed SSAs into debug uses,
1270 rather than only the latest ones. E.g., consider:
1276 If we were to release x_3 before a_5, when we reached a_5 and
1277 tried to substitute it into the debug stmt, we'd see x_3 there,
1278 but x_3's DEF, type, etc would have already been disconnected.
1279 By going backwards, the debug stmt first changes to:
1281 # DEBUG a => x_3 - b_4
1285 # DEBUG a => y_1 + z_2 - b_4
1288 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
1289 h
= get_all_dominated_blocks (CDI_DOMINATORS
, single_succ (ENTRY_BLOCK_PTR
));
1291 while (VEC_length (basic_block
, h
))
1293 bb
= VEC_pop (basic_block
, h
);
1295 /* Remove dead statements. */
1296 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi
= psi
)
1298 stmt
= gsi_stmt (gsi
);
1305 /* We can mark a call to free as not necessary if the
1306 defining statement of its argument is an allocation
1307 function and that is not necessary itself. */
1308 if (gimple_call_builtin_p (stmt
, BUILT_IN_FREE
))
1310 tree ptr
= gimple_call_arg (stmt
, 0);
1313 if (TREE_CODE (ptr
) != SSA_NAME
)
1315 def_stmt
= SSA_NAME_DEF_STMT (ptr
);
1316 if (!is_gimple_call (def_stmt
)
1317 || gimple_plf (def_stmt
, STMT_NECESSARY
))
1319 callee2
= gimple_call_fndecl (def_stmt
);
1320 if (callee2
== NULL_TREE
1321 || DECL_BUILT_IN_CLASS (callee2
) != BUILT_IN_NORMAL
1322 || (DECL_FUNCTION_CODE (callee2
) != BUILT_IN_MALLOC
1323 && DECL_FUNCTION_CODE (callee2
) != BUILT_IN_CALLOC
))
1325 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
1328 /* If GSI is not necessary then remove it. */
1329 if (!gimple_plf (stmt
, STMT_NECESSARY
))
1331 if (!is_gimple_debug (stmt
))
1332 something_changed
= true;
1333 remove_dead_stmt (&gsi
, bb
);
1335 else if (is_gimple_call (stmt
))
1337 tree name
= gimple_call_lhs (stmt
);
1339 notice_special_calls (stmt
);
1341 /* When LHS of var = call (); is dead, simplify it into
1342 call (); saving one operand. */
1344 && TREE_CODE (name
) == SSA_NAME
1345 && !TEST_BIT (processed
, SSA_NAME_VERSION (name
))
1346 /* Avoid doing so for allocation calls which we
1347 did not mark as necessary, it will confuse the
1348 special logic we apply to malloc/free pair removal. */
1349 && (!(call
= gimple_call_fndecl (stmt
))
1350 || DECL_BUILT_IN_CLASS (call
) != BUILT_IN_NORMAL
1351 || (DECL_FUNCTION_CODE (call
) != BUILT_IN_MALLOC
1352 && DECL_FUNCTION_CODE (call
) != BUILT_IN_CALLOC
1353 && DECL_FUNCTION_CODE (call
) != BUILT_IN_ALLOCA
1354 && (DECL_FUNCTION_CODE (call
)
1355 != BUILT_IN_ALLOCA_WITH_ALIGN
))))
1357 something_changed
= true;
1358 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1360 fprintf (dump_file
, "Deleting LHS of call: ");
1361 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1362 fprintf (dump_file
, "\n");
1365 gimple_call_set_lhs (stmt
, NULL_TREE
);
1366 maybe_clean_or_replace_eh_stmt (stmt
, stmt
);
1368 release_ssa_name (name
);
1374 VEC_free (basic_block
, heap
, h
);
1376 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1377 rendered some PHI nodes unreachable while they are still in use.
1378 Mark them for renaming. */
1381 basic_block prev_bb
;
1383 find_unreachable_blocks ();
1385 /* Delete all unreachable basic blocks in reverse dominator order. */
1386 for (bb
= EXIT_BLOCK_PTR
->prev_bb
; bb
!= ENTRY_BLOCK_PTR
; bb
= prev_bb
)
1388 prev_bb
= bb
->prev_bb
;
1390 if (!TEST_BIT (bb_contains_live_stmts
, bb
->index
)
1391 || !(bb
->flags
& BB_REACHABLE
))
1393 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1394 if (virtual_operand_p (gimple_phi_result (gsi_stmt (gsi
))))
1397 imm_use_iterator iter
;
1399 FOR_EACH_IMM_USE_STMT (stmt
, iter
, gimple_phi_result (gsi_stmt (gsi
)))
1401 if (!(gimple_bb (stmt
)->flags
& BB_REACHABLE
))
1403 if (gimple_code (stmt
) == GIMPLE_PHI
1404 || gimple_plf (stmt
, STMT_NECESSARY
))
1407 BREAK_FROM_IMM_USE_STMT (iter
);
1411 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi
));
1414 if (!(bb
->flags
& BB_REACHABLE
))
1416 /* Speed up the removal of blocks that don't
1417 dominate others. Walking backwards, this should
1418 be the common case. ??? Do we need to recompute
1419 dominators because of cfg_altered? */
1420 if (!MAY_HAVE_DEBUG_STMTS
1421 || !first_dom_son (CDI_DOMINATORS
, bb
))
1422 delete_basic_block (bb
);
1425 h
= get_all_dominated_blocks (CDI_DOMINATORS
, bb
);
1427 while (VEC_length (basic_block
, h
))
1429 bb
= VEC_pop (basic_block
, h
);
1430 prev_bb
= bb
->prev_bb
;
1431 /* Rearrangements to the CFG may have failed
1432 to update the dominators tree, so that
1433 formerly-dominated blocks are now
1434 otherwise reachable. */
1435 if (!!(bb
->flags
& BB_REACHABLE
))
1437 delete_basic_block (bb
);
1440 VEC_free (basic_block
, heap
, h
);
1448 /* Remove dead PHI nodes. */
1449 something_changed
|= remove_dead_phis (bb
);
1452 return something_changed
;
1456 /* Print out removed statement statistics. */
1463 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1464 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1465 stats
.removed
, stats
.total
, (int) percg
);
1467 if (stats
.total_phis
== 0)
1470 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1472 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1473 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1476 /* Initialization for this pass. Set up the used data structures. */
1479 tree_dce_init (bool aggressive
)
1481 memset ((void *) &stats
, 0, sizeof (stats
));
1487 control_dependence_map
= XNEWVEC (bitmap
, last_basic_block
);
1488 for (i
= 0; i
< last_basic_block
; ++i
)
1489 control_dependence_map
[i
] = BITMAP_ALLOC (NULL
);
1491 last_stmt_necessary
= sbitmap_alloc (last_basic_block
);
1492 bitmap_clear (last_stmt_necessary
);
1493 bb_contains_live_stmts
= sbitmap_alloc (last_basic_block
);
1494 bitmap_clear (bb_contains_live_stmts
);
1497 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1498 bitmap_clear (processed
);
1500 worklist
= VEC_alloc (gimple
, heap
, 64);
1501 cfg_altered
= false;
1504 /* Cleanup after this pass. */
1507 tree_dce_done (bool aggressive
)
1513 for (i
= 0; i
< last_basic_block
; ++i
)
1514 BITMAP_FREE (control_dependence_map
[i
]);
1515 free (control_dependence_map
);
1517 sbitmap_free (visited_control_parents
);
1518 sbitmap_free (last_stmt_necessary
);
1519 sbitmap_free (bb_contains_live_stmts
);
1520 bb_contains_live_stmts
= NULL
;
1523 sbitmap_free (processed
);
1525 VEC_free (gimple
, heap
, worklist
);
1528 /* Main routine to eliminate dead code.
1530 AGGRESSIVE controls the aggressiveness of the algorithm.
1531 In conservative mode, we ignore control dependence and simply declare
1532 all but the most trivially dead branches necessary. This mode is fast.
1533 In aggressive mode, control dependences are taken into account, which
1534 results in more dead code elimination, but at the cost of some time.
1536 FIXME: Aggressive mode before PRE doesn't work currently because
1537 the dominance info is not invalidated after DCE1. This is
1538 not an issue right now because we only run aggressive DCE
1539 as the last tree SSA pass, but keep this in mind when you
1540 start experimenting with pass ordering. */
1543 perform_tree_ssa_dce (bool aggressive
)
1545 struct edge_list
*el
= NULL
;
1546 bool something_changed
= 0;
1548 calculate_dominance_info (CDI_DOMINATORS
);
1550 /* Preheaders are needed for SCEV to work.
1551 Simple lateches and recorded exits improve chances that loop will
1552 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1554 loop_optimizer_init (LOOPS_NORMAL
1555 | LOOPS_HAVE_RECORDED_EXITS
);
1557 tree_dce_init (aggressive
);
1561 /* Compute control dependence. */
1562 timevar_push (TV_CONTROL_DEPENDENCES
);
1563 calculate_dominance_info (CDI_POST_DOMINATORS
);
1564 el
= create_edge_list ();
1565 find_all_control_dependences (el
);
1566 timevar_pop (TV_CONTROL_DEPENDENCES
);
1568 visited_control_parents
= sbitmap_alloc (last_basic_block
);
1569 bitmap_clear (visited_control_parents
);
1571 mark_dfs_back_edges ();
1574 find_obviously_necessary_stmts (el
);
1577 loop_optimizer_finalize ();
1583 visited
= BITMAP_ALLOC (NULL
);
1584 propagate_necessity (el
);
1585 BITMAP_FREE (visited
);
1587 something_changed
|= eliminate_unnecessary_stmts ();
1588 something_changed
|= cfg_altered
;
1590 /* We do not update postdominators, so free them unconditionally. */
1591 free_dominance_info (CDI_POST_DOMINATORS
);
1593 /* If we removed paths in the CFG, then we need to update
1594 dominators as well. I haven't investigated the possibility
1595 of incrementally updating dominators. */
1597 free_dominance_info (CDI_DOMINATORS
);
1599 statistics_counter_event (cfun
, "Statements deleted", stats
.removed
);
1600 statistics_counter_event (cfun
, "PHI nodes deleted", stats
.removed_phis
);
1602 /* Debugging dumps. */
1603 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1606 tree_dce_done (aggressive
);
1608 free_edge_list (el
);
1610 if (something_changed
)
1611 return (TODO_update_ssa
| TODO_cleanup_cfg
| TODO_ggc_collect
1612 | TODO_remove_unused_locals
);
1617 /* Pass entry points. */
1621 return perform_tree_ssa_dce (/*aggressive=*/false);
1625 tree_ssa_dce_loop (void)
1628 todo
= perform_tree_ssa_dce (/*aggressive=*/false);
1631 free_numbers_of_iterations_estimates ();
1638 tree_ssa_cd_dce (void)
1640 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1646 return flag_tree_dce
!= 0;
1649 struct gimple_opt_pass pass_dce
=
1654 gate_dce
, /* gate */
1655 tree_ssa_dce
, /* execute */
1658 0, /* static_pass_number */
1659 TV_TREE_DCE
, /* tv_id */
1660 PROP_cfg
| PROP_ssa
, /* properties_required */
1661 0, /* properties_provided */
1662 0, /* properties_destroyed */
1663 0, /* todo_flags_start */
1664 TODO_verify_ssa
/* todo_flags_finish */
1668 struct gimple_opt_pass pass_dce_loop
=
1672 "dceloop", /* name */
1673 gate_dce
, /* gate */
1674 tree_ssa_dce_loop
, /* execute */
1677 0, /* static_pass_number */
1678 TV_TREE_DCE
, /* tv_id */
1679 PROP_cfg
| PROP_ssa
, /* properties_required */
1680 0, /* properties_provided */
1681 0, /* properties_destroyed */
1682 0, /* todo_flags_start */
1683 TODO_verify_ssa
/* todo_flags_finish */
1687 struct gimple_opt_pass pass_cd_dce
=
1692 gate_dce
, /* gate */
1693 tree_ssa_cd_dce
, /* execute */
1696 0, /* static_pass_number */
1697 TV_TREE_CD_DCE
, /* tv_id */
1698 PROP_cfg
| PROP_ssa
, /* properties_required */
1699 0, /* properties_provided */
1700 0, /* properties_destroyed */
1701 0, /* todo_flags_start */
1703 | TODO_verify_flow
/* todo_flags_finish */