1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002-2015 Free Software Foundation, Inc.
3 Contributed by Ben Elliston <bje@redhat.com>
4 and Andrew MacLeod <amacleod@redhat.com>
5 Adapted to use control dependence by Steven Bosscher, SUSE Labs.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Dead code elimination.
27 Building an Optimizing Compiler,
28 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
30 Advanced Compiler Design and Implementation,
31 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
33 Dead-code elimination is the removal of statements which have no
34 impact on the program's output. "Dead statements" have no impact
35 on the program's output, while "necessary statements" may have
38 The algorithm consists of three phases:
39 1. Marking as necessary all statements known to be necessary,
40 e.g. most function calls, writing a value to memory, etc;
41 2. Propagating necessary statements, e.g., the statements
42 giving values to operands in necessary statements; and
43 3. Removing dead statements. */
47 #include "coretypes.h"
53 #include "fold-const.h"
55 #include "gimple-pretty-print.h"
57 #include "hard-reg-set.h"
59 #include "dominance.h"
62 #include "basic-block.h"
63 #include "tree-ssa-alias.h"
64 #include "internal-fn.h"
66 #include "gimple-expr.h"
70 #include "gimple-iterator.h"
71 #include "gimple-ssa.h"
73 #include "tree-phinodes.h"
74 #include "ssa-iterators.h"
75 #include "stringpool.h"
76 #include "tree-ssanames.h"
77 #include "tree-ssa-loop-niter.h"
78 #include "tree-into-ssa.h"
81 #include "insn-config.h"
90 #include "tree-pass.h"
92 #include "tree-scalar-evolution.h"
93 #include "tree-chkp.h"
94 #include "tree-ssa-propagate.h"
95 #include "gimple-fold.h"
97 static struct stmt_stats
105 #define STMT_NECESSARY GF_PLF_1
107 static vec
<gimple
> worklist
;
109 /* Vector indicating an SSA name has already been processed and marked
111 static sbitmap processed
;
113 /* Vector indicating that the last statement of a basic block has already
114 been marked as necessary. */
115 static sbitmap last_stmt_necessary
;
117 /* Vector indicating that BB contains statements that are live. */
118 static sbitmap bb_contains_live_stmts
;
120 /* Before we can determine whether a control branch is dead, we need to
121 compute which blocks are control dependent on which edges.
123 We expect each block to be control dependent on very few edges so we
124 use a bitmap for each block recording its edges. An array holds the
125 bitmap. The Ith bit in the bitmap is set if that block is dependent
127 static control_dependences
*cd
;
129 /* Vector indicating that a basic block has already had all the edges
130 processed that it is control dependent on. */
131 static sbitmap visited_control_parents
;
133 /* TRUE if this pass alters the CFG (by removing control statements).
136 If this pass alters the CFG, then it will arrange for the dominators
138 static bool cfg_altered
;
141 /* If STMT is not already marked necessary, mark it, and add it to the
142 worklist if ADD_TO_WORKLIST is true. */
145 mark_stmt_necessary (gimple stmt
, bool add_to_worklist
)
149 if (gimple_plf (stmt
, STMT_NECESSARY
))
152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
154 fprintf (dump_file
, "Marking useful stmt: ");
155 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
156 fprintf (dump_file
, "\n");
159 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
161 worklist
.safe_push (stmt
);
162 if (bb_contains_live_stmts
&& !is_gimple_debug (stmt
))
163 bitmap_set_bit (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
167 /* Mark the statement defining operand OP as necessary. */
170 mark_operand_necessary (tree op
)
177 ver
= SSA_NAME_VERSION (op
);
178 if (bitmap_bit_p (processed
, ver
))
180 stmt
= SSA_NAME_DEF_STMT (op
);
181 gcc_assert (gimple_nop_p (stmt
)
182 || gimple_plf (stmt
, STMT_NECESSARY
));
185 bitmap_set_bit (processed
, ver
);
187 stmt
= SSA_NAME_DEF_STMT (op
);
190 if (gimple_plf (stmt
, STMT_NECESSARY
) || gimple_nop_p (stmt
))
193 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
195 fprintf (dump_file
, "marking necessary through ");
196 print_generic_expr (dump_file
, op
, 0);
197 fprintf (dump_file
, " stmt ");
198 print_gimple_stmt (dump_file
, stmt
, 0, 0);
201 gimple_set_plf (stmt
, STMT_NECESSARY
, true);
202 if (bb_contains_live_stmts
)
203 bitmap_set_bit (bb_contains_live_stmts
, gimple_bb (stmt
)->index
);
204 worklist
.safe_push (stmt
);
208 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
209 it can make other statements necessary.
211 If AGGRESSIVE is false, control statements are conservatively marked as
215 mark_stmt_if_obviously_necessary (gimple stmt
, bool aggressive
)
217 /* With non-call exceptions, we have to assume that all statements could
218 throw. If a statement could throw, it can be deemed necessary. */
219 if (cfun
->can_throw_non_call_exceptions
220 && !cfun
->can_delete_dead_exceptions
221 && stmt_could_throw_p (stmt
))
223 mark_stmt_necessary (stmt
, true);
227 /* Statements that are implicitly live. Most function calls, asm
228 and return statements are required. Labels and GIMPLE_BIND nodes
229 are kept because they are control flow, and we have no way of
230 knowing whether they can be removed. DCE can eliminate all the
231 other statements in a block, and CFG can then remove the block
233 switch (gimple_code (stmt
))
237 mark_stmt_necessary (stmt
, false);
243 mark_stmt_necessary (stmt
, true);
248 tree callee
= gimple_call_fndecl (stmt
);
249 if (callee
!= NULL_TREE
250 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
251 switch (DECL_FUNCTION_CODE (callee
))
253 case BUILT_IN_MALLOC
:
254 case BUILT_IN_ALIGNED_ALLOC
:
255 case BUILT_IN_CALLOC
:
256 case BUILT_IN_ALLOCA
:
257 case BUILT_IN_ALLOCA_WITH_ALIGN
:
262 /* Most, but not all function calls are required. Function calls that
263 produce no result and have no side effects (i.e. const pure
264 functions) are unnecessary. */
265 if (gimple_has_side_effects (stmt
))
267 mark_stmt_necessary (stmt
, true);
270 if (!gimple_call_lhs (stmt
))
276 /* Debug temps without a value are not useful. ??? If we could
277 easily locate the debug temp bind stmt for a use thereof,
278 would could refrain from marking all debug temps here, and
279 mark them only if they're used. */
280 if (!gimple_debug_bind_p (stmt
)
281 || gimple_debug_bind_has_value_p (stmt
)
282 || TREE_CODE (gimple_debug_bind_get_var (stmt
)) != DEBUG_EXPR_DECL
)
283 mark_stmt_necessary (stmt
, false);
287 gcc_assert (!simple_goto_p (stmt
));
288 mark_stmt_necessary (stmt
, true);
292 gcc_assert (EDGE_COUNT (gimple_bb (stmt
)->succs
) == 2);
297 mark_stmt_necessary (stmt
, true);
301 if (gimple_clobber_p (stmt
))
309 /* If the statement has volatile operands, it needs to be preserved.
310 Same for statements that can alter control flow in unpredictable
312 if (gimple_has_volatile_ops (stmt
) || is_ctrl_altering_stmt (stmt
))
314 mark_stmt_necessary (stmt
, true);
318 if (stmt_may_clobber_global_p (stmt
))
320 mark_stmt_necessary (stmt
, true);
328 /* Mark the last statement of BB as necessary. */
331 mark_last_stmt_necessary (basic_block bb
)
333 gimple stmt
= last_stmt (bb
);
335 bitmap_set_bit (last_stmt_necessary
, bb
->index
);
336 bitmap_set_bit (bb_contains_live_stmts
, bb
->index
);
338 /* We actually mark the statement only if it is a control statement. */
339 if (stmt
&& is_ctrl_stmt (stmt
))
340 mark_stmt_necessary (stmt
, true);
344 /* Mark control dependent edges of BB as necessary. We have to do this only
345 once for each basic block so we set the appropriate bit after we're done.
347 When IGNORE_SELF is true, ignore BB in the list of control dependences. */
350 mark_control_dependent_edges_necessary (basic_block bb
, bool ignore_self
)
353 unsigned edge_number
;
354 bool skipped
= false;
356 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
358 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
361 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
364 basic_block cd_bb
= cd
->get_edge (edge_number
)->src
;
366 if (ignore_self
&& cd_bb
== bb
)
372 if (!bitmap_bit_p (last_stmt_necessary
, cd_bb
->index
))
373 mark_last_stmt_necessary (cd_bb
);
377 bitmap_set_bit (visited_control_parents
, bb
->index
);
381 /* Find obviously necessary statements. These are things like most function
382 calls, and stores to file level variables.
384 If EL is NULL, control statements are conservatively marked as
385 necessary. Otherwise it contains the list of edges used by control
386 dependence analysis. */
389 find_obviously_necessary_stmts (bool aggressive
)
392 gimple_stmt_iterator gsi
;
397 FOR_EACH_BB_FN (bb
, cfun
)
399 /* PHI nodes are never inherently necessary. */
400 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
402 phi
= gsi_stmt (gsi
);
403 gimple_set_plf (phi
, STMT_NECESSARY
, false);
406 /* Check all statements in the block. */
407 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
409 stmt
= gsi_stmt (gsi
);
410 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
411 mark_stmt_if_obviously_necessary (stmt
, aggressive
);
415 /* Pure and const functions are finite and thus have no infinite loops in
417 flags
= flags_from_decl_or_type (current_function_decl
);
418 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
421 /* Prevent the empty possibly infinite loops from being removed. */
426 if (mark_irreducible_loops ())
427 FOR_EACH_BB_FN (bb
, cfun
)
430 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
431 if ((e
->flags
& EDGE_DFS_BACK
)
432 && (e
->flags
& EDGE_IRREDUCIBLE_LOOP
))
435 fprintf (dump_file
, "Marking back edge of irreducible loop %i->%i\n",
436 e
->src
->index
, e
->dest
->index
);
437 mark_control_dependent_edges_necessary (e
->dest
, false);
441 FOR_EACH_LOOP (loop
, 0)
442 if (!finite_loop_p (loop
))
445 fprintf (dump_file
, "can not prove finiteness of loop %i\n", loop
->num
);
446 mark_control_dependent_edges_necessary (loop
->latch
, false);
453 /* Return true if REF is based on an aliased base, otherwise false. */
456 ref_may_be_aliased (tree ref
)
458 gcc_assert (TREE_CODE (ref
) != WITH_SIZE_EXPR
);
459 while (handled_component_p (ref
))
460 ref
= TREE_OPERAND (ref
, 0);
461 if (TREE_CODE (ref
) == MEM_REF
462 && TREE_CODE (TREE_OPERAND (ref
, 0)) == ADDR_EXPR
)
463 ref
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
464 return !(DECL_P (ref
)
465 && !may_be_aliased (ref
));
468 static bitmap visited
= NULL
;
469 static unsigned int longest_chain
= 0;
470 static unsigned int total_chain
= 0;
471 static unsigned int nr_walks
= 0;
472 static bool chain_ovfl
= false;
474 /* Worker for the walker that marks reaching definitions of REF,
475 which is based on a non-aliased decl, necessary. It returns
476 true whenever the defining statement of the current VDEF is
477 a kill for REF, as no dominating may-defs are necessary for REF
478 anymore. DATA points to the basic-block that contains the
479 stmt that refers to REF. */
482 mark_aliased_reaching_defs_necessary_1 (ao_ref
*ref
, tree vdef
, void *data
)
484 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
486 /* All stmts we visit are necessary. */
487 mark_operand_necessary (vdef
);
489 /* If the stmt lhs kills ref, then we can stop walking. */
490 if (gimple_has_lhs (def_stmt
)
491 && TREE_CODE (gimple_get_lhs (def_stmt
)) != SSA_NAME
492 /* The assignment is not necessarily carried out if it can throw
493 and we can catch it in the current function where we could inspect
495 ??? We only need to care about the RHS throwing. For aggregate
496 assignments or similar calls and non-call exceptions the LHS
497 might throw as well. */
498 && !stmt_can_throw_internal (def_stmt
))
500 tree base
, lhs
= gimple_get_lhs (def_stmt
);
501 HOST_WIDE_INT size
, offset
, max_size
;
505 = get_ref_base_and_extent (lhs
, &offset
, &size
, &max_size
, &reverse
);
506 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
507 so base == refd->base does not always hold. */
508 if (base
== ref
->base
)
510 /* For a must-alias check we need to be able to constrain
511 the accesses properly. */
512 if (size
!= -1 && size
== max_size
513 && ref
->max_size
!= -1)
515 if (offset
<= ref
->offset
516 && offset
+ size
>= ref
->offset
+ ref
->max_size
)
519 /* Or they need to be exactly the same. */
521 /* Make sure there is no induction variable involved
522 in the references (gcc.c-torture/execute/pr42142.c).
523 The simplest way is to check if the kill dominates
525 /* But when both are in the same block we cannot
526 easily tell whether we came from a backedge
527 unless we decide to compute stmt UIDs
529 && (basic_block
) data
!= gimple_bb (def_stmt
)
530 && dominated_by_p (CDI_DOMINATORS
, (basic_block
) data
,
531 gimple_bb (def_stmt
))
532 && operand_equal_p (ref
->ref
, lhs
, 0))
537 /* Otherwise keep walking. */
542 mark_aliased_reaching_defs_necessary (gimple stmt
, tree ref
)
546 gcc_assert (!chain_ovfl
);
547 ao_ref_init (&refd
, ref
);
548 chain
= walk_aliased_vdefs (&refd
, gimple_vuse (stmt
),
549 mark_aliased_reaching_defs_necessary_1
,
550 gimple_bb (stmt
), NULL
);
551 if (chain
> longest_chain
)
552 longest_chain
= chain
;
553 total_chain
+= chain
;
557 /* Worker for the walker that marks reaching definitions of REF, which
558 is not based on a non-aliased decl. For simplicity we need to end
559 up marking all may-defs necessary that are not based on a non-aliased
560 decl. The only job of this walker is to skip may-defs based on
561 a non-aliased decl. */
564 mark_all_reaching_defs_necessary_1 (ao_ref
*ref ATTRIBUTE_UNUSED
,
565 tree vdef
, void *data ATTRIBUTE_UNUSED
)
567 gimple def_stmt
= SSA_NAME_DEF_STMT (vdef
);
569 /* We have to skip already visited (and thus necessary) statements
570 to make the chaining work after we dropped back to simple mode. */
572 && bitmap_bit_p (processed
, SSA_NAME_VERSION (vdef
)))
574 gcc_assert (gimple_nop_p (def_stmt
)
575 || gimple_plf (def_stmt
, STMT_NECESSARY
));
579 /* We want to skip stores to non-aliased variables. */
581 && gimple_assign_single_p (def_stmt
))
583 tree lhs
= gimple_assign_lhs (def_stmt
);
584 if (!ref_may_be_aliased (lhs
))
588 /* We want to skip statments that do not constitute stores but have
589 a virtual definition. */
590 if (is_gimple_call (def_stmt
))
592 tree callee
= gimple_call_fndecl (def_stmt
);
593 if (callee
!= NULL_TREE
594 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
595 switch (DECL_FUNCTION_CODE (callee
))
597 case BUILT_IN_MALLOC
:
598 case BUILT_IN_ALIGNED_ALLOC
:
599 case BUILT_IN_CALLOC
:
600 case BUILT_IN_ALLOCA
:
601 case BUILT_IN_ALLOCA_WITH_ALIGN
:
609 mark_operand_necessary (vdef
);
615 mark_all_reaching_defs_necessary (gimple stmt
)
617 walk_aliased_vdefs (NULL
, gimple_vuse (stmt
),
618 mark_all_reaching_defs_necessary_1
, NULL
, &visited
);
621 /* Return true for PHI nodes with one or identical arguments
624 degenerate_phi_p (gimple phi
)
627 tree op
= gimple_phi_arg_def (phi
, 0);
628 for (i
= 1; i
< gimple_phi_num_args (phi
); i
++)
629 if (gimple_phi_arg_def (phi
, i
) != op
)
634 /* Propagate necessity using the operands of necessary statements.
635 Process the uses on each statement in the worklist, and add all
636 feeding statements which contribute to the calculation of this
637 value to the worklist.
639 In conservative mode, EL is NULL. */
642 propagate_necessity (bool aggressive
)
646 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
647 fprintf (dump_file
, "\nProcessing worklist:\n");
649 while (worklist
.length () > 0)
651 /* Take STMT from worklist. */
652 stmt
= worklist
.pop ();
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, "processing: ");
657 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
658 fprintf (dump_file
, "\n");
663 /* Mark the last statement of the basic blocks on which the block
664 containing STMT is control dependent, but only if we haven't
666 basic_block bb
= gimple_bb (stmt
);
667 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
668 && !bitmap_bit_p (visited_control_parents
, bb
->index
))
669 mark_control_dependent_edges_necessary (bb
, false);
672 if (gimple_code (stmt
) == GIMPLE_PHI
673 /* We do not process virtual PHI nodes nor do we track their
675 && !virtual_operand_p (gimple_phi_result (stmt
)))
677 /* PHI nodes are somewhat special in that each PHI alternative has
678 data and control dependencies. All the statements feeding the
679 PHI node's arguments are always necessary. In aggressive mode,
680 we also consider the control dependent edges leading to the
681 predecessor block associated with each PHI alternative as
683 gphi
*phi
= as_a
<gphi
*> (stmt
);
686 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
688 tree arg
= PHI_ARG_DEF (stmt
, k
);
689 if (TREE_CODE (arg
) == SSA_NAME
)
690 mark_operand_necessary (arg
);
693 /* For PHI operands it matters from where the control flow arrives
694 to the BB. Consider the following example:
704 We need to mark control dependence of the empty basic blocks, since they
705 contains computation of PHI operands.
707 Doing so is too restrictive in the case the predecestor block is in
713 for (i = 0; i<1000; ++i)
719 There is PHI for J in the BB containing return statement.
720 In this case the control dependence of predecestor block (that is
721 within the empty loop) also contains the block determining number
722 of iterations of the block that would prevent removing of empty
725 This scenario can be avoided by splitting critical edges.
726 To save the critical edge splitting pass we identify how the control
727 dependence would look like if the edge was split.
729 Consider the modified CFG created from current CFG by splitting
730 edge B->C. In the postdominance tree of modified CFG, C' is
731 always child of C. There are two cases how chlids of C' can look
736 In this case the only basic block C' is control dependent on is B.
738 2) C' has single child that is B
740 In this case control dependence of C' is same as control
741 dependence of B in original CFG except for block B itself.
742 (since C' postdominate B in modified CFG)
744 Now how to decide what case happens? There are two basic options:
746 a) C postdominate B. Then C immediately postdominate B and
747 case 2 happens iff there is no other way from B to C except
750 There is other way from B to C iff there is succesor of B that
751 is not postdominated by B. Testing this condition is somewhat
752 expensive, because we need to iterate all succesors of B.
753 We are safe to assume that this does not happen: we will mark B
754 as needed when processing the other path from B to C that is
755 conrol dependent on B and marking control dependencies of B
756 itself is harmless because they will be processed anyway after
757 processing control statement in B.
759 b) C does not postdominate B. Always case 1 happens since there is
760 path from C to exit that does not go through B and thus also C'. */
762 if (aggressive
&& !degenerate_phi_p (stmt
))
764 for (k
= 0; k
< gimple_phi_num_args (stmt
); k
++)
766 basic_block arg_bb
= gimple_phi_arg_edge (phi
, k
)->src
;
769 != get_immediate_dominator (CDI_POST_DOMINATORS
, arg_bb
))
771 if (!bitmap_bit_p (last_stmt_necessary
, arg_bb
->index
))
772 mark_last_stmt_necessary (arg_bb
);
774 else if (arg_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
775 && !bitmap_bit_p (visited_control_parents
,
777 mark_control_dependent_edges_necessary (arg_bb
, true);
783 /* Propagate through the operands. Examine all the USE, VUSE and
784 VDEF operands in this statement. Mark all the statements
785 which feed this statement's uses as necessary. */
789 /* If this is a call to free which is directly fed by an
790 allocation function do not mark that necessary through
791 processing the argument. */
792 if (gimple_call_builtin_p (stmt
, BUILT_IN_FREE
))
794 tree ptr
= gimple_call_arg (stmt
, 0);
797 /* If the pointer we free is defined by an allocation
798 function do not add the call to the worklist. */
799 if (TREE_CODE (ptr
) == SSA_NAME
800 && is_gimple_call (def_stmt
= SSA_NAME_DEF_STMT (ptr
))
801 && (def_callee
= gimple_call_fndecl (def_stmt
))
802 && DECL_BUILT_IN_CLASS (def_callee
) == BUILT_IN_NORMAL
803 && (DECL_FUNCTION_CODE (def_callee
) == BUILT_IN_ALIGNED_ALLOC
804 || DECL_FUNCTION_CODE (def_callee
) == BUILT_IN_MALLOC
805 || DECL_FUNCTION_CODE (def_callee
) == BUILT_IN_CALLOC
))
807 gimple bounds_def_stmt
;
810 /* For instrumented calls we should also check used
811 bounds are returned by the same allocation call. */
812 if (!gimple_call_with_bounds_p (stmt
)
813 || ((bounds
= gimple_call_arg (stmt
, 1))
814 && TREE_CODE (bounds
) == SSA_NAME
815 && (bounds_def_stmt
= SSA_NAME_DEF_STMT (bounds
))
816 && chkp_gimple_call_builtin_p (bounds_def_stmt
,
817 BUILT_IN_CHKP_BNDRET
)
818 && gimple_call_arg (bounds_def_stmt
, 0) == ptr
))
823 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
824 mark_operand_necessary (use
);
826 use
= gimple_vuse (stmt
);
830 /* If we dropped to simple mode make all immediately
831 reachable definitions necessary. */
834 mark_all_reaching_defs_necessary (stmt
);
838 /* For statements that may load from memory (have a VUSE) we
839 have to mark all reaching (may-)definitions as necessary.
840 We partition this task into two cases:
841 1) explicit loads based on decls that are not aliased
842 2) implicit loads (like calls) and explicit loads not
843 based on decls that are not aliased (like indirect
844 references or loads from globals)
845 For 1) we mark all reaching may-defs as necessary, stopping
846 at dominating kills. For 2) we want to mark all dominating
847 references necessary, but non-aliased ones which we handle
848 in 1). By keeping a global visited bitmap for references
849 we walk for 2) we avoid quadratic behavior for those. */
851 if (is_gimple_call (stmt
))
853 tree callee
= gimple_call_fndecl (stmt
);
856 /* Calls to functions that are merely acting as barriers
857 or that only store to memory do not make any previous
859 if (callee
!= NULL_TREE
860 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
861 && (DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET
862 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MEMSET_CHK
863 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_MALLOC
864 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_ALIGNED_ALLOC
865 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_CALLOC
866 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_FREE
867 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_VA_END
868 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_ALLOCA
869 || (DECL_FUNCTION_CODE (callee
)
870 == BUILT_IN_ALLOCA_WITH_ALIGN
)
871 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_STACK_SAVE
872 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_STACK_RESTORE
873 || DECL_FUNCTION_CODE (callee
) == BUILT_IN_ASSUME_ALIGNED
))
876 /* Calls implicitly load from memory, their arguments
877 in addition may explicitly perform memory loads. */
878 mark_all_reaching_defs_necessary (stmt
);
879 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
881 tree arg
= gimple_call_arg (stmt
, i
);
882 if (TREE_CODE (arg
) == SSA_NAME
883 || is_gimple_min_invariant (arg
))
885 if (TREE_CODE (arg
) == WITH_SIZE_EXPR
)
886 arg
= TREE_OPERAND (arg
, 0);
887 if (!ref_may_be_aliased (arg
))
888 mark_aliased_reaching_defs_necessary (stmt
, arg
);
891 else if (gimple_assign_single_p (stmt
))
894 /* If this is a load mark things necessary. */
895 rhs
= gimple_assign_rhs1 (stmt
);
896 if (TREE_CODE (rhs
) != SSA_NAME
897 && !is_gimple_min_invariant (rhs
)
898 && TREE_CODE (rhs
) != CONSTRUCTOR
)
900 if (!ref_may_be_aliased (rhs
))
901 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
903 mark_all_reaching_defs_necessary (stmt
);
906 else if (greturn
*return_stmt
= dyn_cast
<greturn
*> (stmt
))
908 tree rhs
= gimple_return_retval (return_stmt
);
909 /* A return statement may perform a load. */
911 && TREE_CODE (rhs
) != SSA_NAME
912 && !is_gimple_min_invariant (rhs
)
913 && TREE_CODE (rhs
) != CONSTRUCTOR
)
915 if (!ref_may_be_aliased (rhs
))
916 mark_aliased_reaching_defs_necessary (stmt
, rhs
);
918 mark_all_reaching_defs_necessary (stmt
);
921 else if (gasm
*asm_stmt
= dyn_cast
<gasm
*> (stmt
))
924 mark_all_reaching_defs_necessary (stmt
);
925 /* Inputs may perform loads. */
926 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); ++i
)
928 tree op
= TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
929 if (TREE_CODE (op
) != SSA_NAME
930 && !is_gimple_min_invariant (op
)
931 && TREE_CODE (op
) != CONSTRUCTOR
932 && !ref_may_be_aliased (op
))
933 mark_aliased_reaching_defs_necessary (stmt
, op
);
936 else if (gimple_code (stmt
) == GIMPLE_TRANSACTION
)
938 /* The beginning of a transaction is a memory barrier. */
939 /* ??? If we were really cool, we'd only be a barrier
940 for the memories touched within the transaction. */
941 mark_all_reaching_defs_necessary (stmt
);
946 /* If we over-used our alias oracle budget drop to simple
947 mode. The cost metric allows quadratic behavior
948 (number of uses times number of may-defs queries) up to
949 a constant maximal number of queries and after that falls back to
950 super-linear complexity. */
951 if (/* Constant but quadratic for small functions. */
952 total_chain
> 128 * 128
953 /* Linear in the number of may-defs. */
954 && total_chain
> 32 * longest_chain
955 /* Linear in the number of uses. */
956 && total_chain
> nr_walks
* 32)
960 bitmap_clear (visited
);
966 /* Remove dead PHI nodes from block BB. */
969 remove_dead_phis (basic_block bb
)
971 bool something_changed
= false;
975 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);)
980 /* We do not track necessity of virtual PHI nodes. Instead do
981 very simple dead PHI removal here. */
982 if (virtual_operand_p (gimple_phi_result (phi
)))
984 /* Virtual PHI nodes with one or identical arguments
986 if (degenerate_phi_p (phi
))
988 tree vdef
= gimple_phi_result (phi
);
989 tree vuse
= gimple_phi_arg_def (phi
, 0);
992 imm_use_iterator iter
;
994 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, vdef
)
995 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
996 SET_USE (use_p
, vuse
);
997 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef
)
998 && TREE_CODE (vuse
) == SSA_NAME
)
999 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse
) = 1;
1002 gimple_set_plf (phi
, STMT_NECESSARY
, true);
1005 if (!gimple_plf (phi
, STMT_NECESSARY
))
1007 something_changed
= true;
1008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1010 fprintf (dump_file
, "Deleting : ");
1011 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1012 fprintf (dump_file
, "\n");
1015 remove_phi_node (&gsi
, true);
1016 stats
.removed_phis
++;
1022 return something_changed
;
1025 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
1028 forward_edge_to_pdom (edge e
, basic_block post_dom_bb
)
1034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1035 fprintf (dump_file
, "Redirecting edge %i->%i to %i\n", e
->src
->index
,
1036 e
->dest
->index
, post_dom_bb
->index
);
1038 e2
= redirect_edge_and_branch (e
, post_dom_bb
);
1041 /* If edge was already around, no updating is necessary. */
1045 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb
)))
1047 /* We are sure that for every live PHI we are seeing control dependent BB.
1048 This means that we can pick any edge to duplicate PHI args from. */
1049 FOR_EACH_EDGE (e2
, ei
, post_dom_bb
->preds
)
1052 for (gsi
= gsi_start_phis (post_dom_bb
); !gsi_end_p (gsi
);)
1054 gphi
*phi
= gsi
.phi ();
1056 source_location locus
;
1058 /* PHIs for virtuals have no control dependency relation on them.
1059 We are lost here and must force renaming of the symbol. */
1060 if (virtual_operand_p (gimple_phi_result (phi
)))
1062 mark_virtual_phi_result_for_renaming (phi
);
1063 remove_phi_node (&gsi
, true);
1067 /* Dead PHI do not imply control dependency. */
1068 if (!gimple_plf (phi
, STMT_NECESSARY
))
1074 op
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
1075 locus
= gimple_phi_arg_location (phi
, e2
->dest_idx
);
1076 add_phi_arg (phi
, op
, e
, locus
);
1077 /* The resulting PHI if not dead can only be degenerate. */
1078 gcc_assert (degenerate_phi_p (phi
));
1085 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1086 containing I so that we don't have to look it up. */
1089 remove_dead_stmt (gimple_stmt_iterator
*i
, basic_block bb
)
1091 gimple stmt
= gsi_stmt (*i
);
1093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1095 fprintf (dump_file
, "Deleting : ");
1096 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1097 fprintf (dump_file
, "\n");
1102 /* If we have determined that a conditional branch statement contributes
1103 nothing to the program, then we not only remove it, but we also change
1104 the flow graph so that the current block will simply fall-thru to its
1105 immediate post-dominator. The blocks we are circumventing will be
1106 removed by cleanup_tree_cfg if this change in the flow graph makes them
1108 if (is_ctrl_stmt (stmt
))
1110 basic_block post_dom_bb
;
1114 post_dom_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
1116 e
= find_edge (bb
, post_dom_bb
);
1118 /* If edge is already there, try to use it. This avoids need to update
1119 PHI nodes. Also watch for cases where post dominator does not exists
1120 or is exit block. These can happen for infinite loops as we create
1121 fake edges in the dominator tree. */
1124 else if (! post_dom_bb
|| post_dom_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1125 e
= EDGE_SUCC (bb
, 0);
1127 e
= forward_edge_to_pdom (EDGE_SUCC (bb
, 0), post_dom_bb
);
1129 e
->probability
= REG_BR_PROB_BASE
;
1130 e
->count
= bb
->count
;
1132 /* The edge is no longer associated with a conditional, so it does
1133 not have TRUE/FALSE flags. */
1134 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
1136 /* The lone outgoing edge from BB will be a fallthru edge. */
1137 e
->flags
|= EDGE_FALLTHRU
;
1139 /* Remove the remaining outgoing edges. */
1140 for (ei
= ei_start (bb
->succs
); (e2
= ei_safe_edge (ei
)); )
1144 /* If we made a BB unconditionally exit a loop then this
1145 transform alters the set of BBs in the loop. Schedule
1147 if (loop_exit_edge_p (bb
->loop_father
, e
))
1148 loops_state_set (LOOPS_NEED_FIXUP
);
1155 /* If this is a store into a variable that is being optimized away,
1156 add a debug bind stmt if possible. */
1157 if (MAY_HAVE_DEBUG_STMTS
1158 && gimple_assign_single_p (stmt
)
1159 && is_gimple_val (gimple_assign_rhs1 (stmt
)))
1161 tree lhs
= gimple_assign_lhs (stmt
);
1162 if ((TREE_CODE (lhs
) == VAR_DECL
|| TREE_CODE (lhs
) == PARM_DECL
)
1163 && !DECL_IGNORED_P (lhs
)
1164 && is_gimple_reg_type (TREE_TYPE (lhs
))
1165 && !is_global_var (lhs
)
1166 && !DECL_HAS_VALUE_EXPR_P (lhs
))
1168 tree rhs
= gimple_assign_rhs1 (stmt
);
1170 = gimple_build_debug_bind (lhs
, unshare_expr (rhs
), stmt
);
1171 gsi_insert_after (i
, note
, GSI_SAME_STMT
);
1175 unlink_stmt_vdef (stmt
);
1176 gsi_remove (i
, true);
1177 release_defs (stmt
);
1180 /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any
1181 uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */
1184 find_non_realpart_uses (tree
*tp
, int *walk_subtrees
, void *data
)
1186 if (TYPE_P (*tp
) || TREE_CODE (*tp
) == REALPART_EXPR
)
1188 if (*tp
== (tree
) data
)
1193 /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
1194 but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
1195 into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
1199 maybe_optimize_arith_overflow (gimple_stmt_iterator
*gsi
,
1200 enum tree_code subcode
)
1202 gimple stmt
= gsi_stmt (*gsi
);
1203 tree lhs
= gimple_call_lhs (stmt
);
1205 if (lhs
== NULL
|| TREE_CODE (lhs
) != SSA_NAME
)
1208 imm_use_iterator imm_iter
;
1209 use_operand_p use_p
;
1210 bool has_debug_uses
= false;
1211 bool has_realpart_uses
= false;
1212 bool has_other_uses
= false;
1213 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1215 gimple use_stmt
= USE_STMT (use_p
);
1216 if (is_gimple_debug (use_stmt
))
1217 has_debug_uses
= true;
1218 else if (is_gimple_assign (use_stmt
)
1219 && gimple_assign_rhs_code (use_stmt
) == REALPART_EXPR
1220 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0) == lhs
)
1221 has_realpart_uses
= true;
1224 has_other_uses
= true;
1229 if (!has_realpart_uses
|| has_other_uses
)
1232 tree arg0
= gimple_call_arg (stmt
, 0);
1233 tree arg1
= gimple_call_arg (stmt
, 1);
1234 location_t loc
= gimple_location (stmt
);
1235 tree type
= TREE_TYPE (TREE_TYPE (lhs
));
1237 if (!TYPE_UNSIGNED (type
))
1238 utype
= build_nonstandard_integer_type (TYPE_PRECISION (type
), 1);
1239 tree result
= fold_build2_loc (loc
, subcode
, utype
,
1240 fold_convert_loc (loc
, utype
, arg0
),
1241 fold_convert_loc (loc
, utype
, arg1
));
1242 result
= fold_convert_loc (loc
, type
, result
);
1247 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, lhs
)
1249 if (!gimple_debug_bind_p (use_stmt
))
1251 tree v
= gimple_debug_bind_get_value (use_stmt
);
1252 if (walk_tree (&v
, find_non_realpart_uses
, lhs
, NULL
))
1254 gimple_debug_bind_reset_value (use_stmt
);
1255 update_stmt (use_stmt
);
1260 if (TREE_CODE (result
) == INTEGER_CST
&& TREE_OVERFLOW (result
))
1261 result
= drop_tree_overflow (result
);
1262 tree overflow
= build_zero_cst (type
);
1263 tree ctype
= build_complex_type (type
);
1264 if (TREE_CODE (result
) == INTEGER_CST
)
1265 result
= build_complex (ctype
, result
, overflow
);
1267 result
= build2_loc (gimple_location (stmt
), COMPLEX_EXPR
,
1268 ctype
, result
, overflow
);
1270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1272 fprintf (dump_file
, "Transforming call: ");
1273 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1274 fprintf (dump_file
, "because the overflow result is never used into: ");
1275 print_generic_stmt (dump_file
, result
, TDF_SLIM
);
1276 fprintf (dump_file
, "\n");
1279 if (!update_call_from_tree (gsi
, result
))
1280 gimplify_and_update_call_from_tree (gsi
, result
);
1283 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1284 contributes nothing to the program, and can be deleted. */
1287 eliminate_unnecessary_stmts (void)
1289 bool something_changed
= false;
1291 gimple_stmt_iterator gsi
, psi
;
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 fprintf (dump_file
, "\nEliminating unnecessary statements:\n");
1299 clear_special_calls ();
1301 /* Walking basic blocks and statements in reverse order avoids
1302 releasing SSA names before any other DEFs that refer to them are
1303 released. This helps avoid loss of debug information, as we get
1304 a chance to propagate all RHSs of removed SSAs into debug uses,
1305 rather than only the latest ones. E.g., consider:
1311 If we were to release x_3 before a_5, when we reached a_5 and
1312 tried to substitute it into the debug stmt, we'd see x_3 there,
1313 but x_3's DEF, type, etc would have already been disconnected.
1314 By going backwards, the debug stmt first changes to:
1316 # DEBUG a => x_3 - b_4
1320 # DEBUG a => y_1 + z_2 - b_4
1323 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
1324 h
= get_all_dominated_blocks (CDI_DOMINATORS
,
1325 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1331 /* Remove dead statements. */
1332 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi
= psi
)
1334 stmt
= gsi_stmt (gsi
);
1341 /* We can mark a call to free as not necessary if the
1342 defining statement of its argument is not necessary
1343 (and thus is getting removed). */
1344 if (gimple_plf (stmt
, STMT_NECESSARY
)
1345 && gimple_call_builtin_p (stmt
, BUILT_IN_FREE
))
1347 tree ptr
= gimple_call_arg (stmt
, 0);
1348 if (TREE_CODE (ptr
) == SSA_NAME
)
1350 gimple def_stmt
= SSA_NAME_DEF_STMT (ptr
);
1351 if (!gimple_nop_p (def_stmt
)
1352 && !gimple_plf (def_stmt
, STMT_NECESSARY
))
1353 gimple_set_plf (stmt
, STMT_NECESSARY
, false);
1355 /* We did not propagate necessity for free calls fed
1356 by allocation function to allow unnecessary
1357 alloc-free sequence elimination. For instrumented
1358 calls it also means we did not mark bounds producer
1359 as necessary and it is time to do it in case free
1360 call is not removed. */
1361 if (gimple_call_with_bounds_p (stmt
))
1363 gimple bounds_def_stmt
;
1364 tree bounds
= gimple_call_arg (stmt
, 1);
1365 gcc_assert (TREE_CODE (bounds
) == SSA_NAME
);
1366 bounds_def_stmt
= SSA_NAME_DEF_STMT (bounds
);
1368 && !gimple_plf (bounds_def_stmt
, STMT_NECESSARY
))
1369 gimple_set_plf (bounds_def_stmt
, STMT_NECESSARY
,
1370 gimple_plf (stmt
, STMT_NECESSARY
));
1374 /* If GSI is not necessary then remove it. */
1375 if (!gimple_plf (stmt
, STMT_NECESSARY
))
1377 /* Keep clobbers that we can keep live live. */
1378 if (gimple_clobber_p (stmt
))
1381 use_operand_p use_p
;
1383 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1385 tree name
= USE_FROM_PTR (use_p
);
1386 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
1387 && !bitmap_bit_p (processed
, SSA_NAME_VERSION (name
)))
1396 if (!is_gimple_debug (stmt
))
1397 something_changed
= true;
1398 remove_dead_stmt (&gsi
, bb
);
1400 else if (is_gimple_call (stmt
))
1402 tree name
= gimple_call_lhs (stmt
);
1404 notice_special_calls (as_a
<gcall
*> (stmt
));
1406 /* When LHS of var = call (); is dead, simplify it into
1407 call (); saving one operand. */
1409 && TREE_CODE (name
) == SSA_NAME
1410 && !bitmap_bit_p (processed
, SSA_NAME_VERSION (name
))
1411 /* Avoid doing so for allocation calls which we
1412 did not mark as necessary, it will confuse the
1413 special logic we apply to malloc/free pair removal. */
1414 && (!(call
= gimple_call_fndecl (stmt
))
1415 || DECL_BUILT_IN_CLASS (call
) != BUILT_IN_NORMAL
1416 || (DECL_FUNCTION_CODE (call
) != BUILT_IN_ALIGNED_ALLOC
1417 && DECL_FUNCTION_CODE (call
) != BUILT_IN_MALLOC
1418 && DECL_FUNCTION_CODE (call
) != BUILT_IN_CALLOC
1419 && DECL_FUNCTION_CODE (call
) != BUILT_IN_ALLOCA
1420 && (DECL_FUNCTION_CODE (call
)
1421 != BUILT_IN_ALLOCA_WITH_ALIGN
)))
1422 /* Avoid doing so for bndret calls for the same reason. */
1423 && !chkp_gimple_call_builtin_p (stmt
, BUILT_IN_CHKP_BNDRET
))
1425 something_changed
= true;
1426 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1428 fprintf (dump_file
, "Deleting LHS of call: ");
1429 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1430 fprintf (dump_file
, "\n");
1433 gimple_call_set_lhs (stmt
, NULL_TREE
);
1434 maybe_clean_or_replace_eh_stmt (stmt
, stmt
);
1436 release_ssa_name (name
);
1438 /* GOMP_SIMD_LANE without lhs is not needed. */
1439 if (gimple_call_internal_p (stmt
)
1440 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
)
1441 remove_dead_stmt (&gsi
, bb
);
1443 else if (gimple_call_internal_p (stmt
))
1444 switch (gimple_call_internal_fn (stmt
))
1446 case IFN_ADD_OVERFLOW
:
1447 maybe_optimize_arith_overflow (&gsi
, PLUS_EXPR
);
1449 case IFN_SUB_OVERFLOW
:
1450 maybe_optimize_arith_overflow (&gsi
, MINUS_EXPR
);
1452 case IFN_MUL_OVERFLOW
:
1453 maybe_optimize_arith_overflow (&gsi
, MULT_EXPR
);
1464 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1465 rendered some PHI nodes unreachable while they are still in use.
1466 Mark them for renaming. */
1469 basic_block prev_bb
;
1471 find_unreachable_blocks ();
1473 /* Delete all unreachable basic blocks in reverse dominator order. */
1474 for (bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
1475 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); bb
= prev_bb
)
1477 prev_bb
= bb
->prev_bb
;
1479 if (!bitmap_bit_p (bb_contains_live_stmts
, bb
->index
)
1480 || !(bb
->flags
& BB_REACHABLE
))
1482 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1484 if (virtual_operand_p (gimple_phi_result (gsi
.phi ())))
1487 imm_use_iterator iter
;
1489 FOR_EACH_IMM_USE_STMT (stmt
, iter
,
1490 gimple_phi_result (gsi
.phi ()))
1492 if (!(gimple_bb (stmt
)->flags
& BB_REACHABLE
))
1494 if (gimple_code (stmt
) == GIMPLE_PHI
1495 || gimple_plf (stmt
, STMT_NECESSARY
))
1498 BREAK_FROM_IMM_USE_STMT (iter
);
1502 mark_virtual_phi_result_for_renaming (gsi
.phi ());
1505 if (!(bb
->flags
& BB_REACHABLE
))
1507 /* Speed up the removal of blocks that don't
1508 dominate others. Walking backwards, this should
1509 be the common case. ??? Do we need to recompute
1510 dominators because of cfg_altered? */
1511 if (!MAY_HAVE_DEBUG_STMTS
1512 || !first_dom_son (CDI_DOMINATORS
, bb
))
1513 delete_basic_block (bb
);
1516 h
= get_all_dominated_blocks (CDI_DOMINATORS
, bb
);
1521 prev_bb
= bb
->prev_bb
;
1522 /* Rearrangements to the CFG may have failed
1523 to update the dominators tree, so that
1524 formerly-dominated blocks are now
1525 otherwise reachable. */
1526 if (!!(bb
->flags
& BB_REACHABLE
))
1528 delete_basic_block (bb
);
1537 FOR_EACH_BB_FN (bb
, cfun
)
1539 /* Remove dead PHI nodes. */
1540 something_changed
|= remove_dead_phis (bb
);
1543 return something_changed
;
1547 /* Print out removed statement statistics. */
1554 percg
= ((float) stats
.removed
/ (float) stats
.total
) * 100;
1555 fprintf (dump_file
, "Removed %d of %d statements (%d%%)\n",
1556 stats
.removed
, stats
.total
, (int) percg
);
1558 if (stats
.total_phis
== 0)
1561 percg
= ((float) stats
.removed_phis
/ (float) stats
.total_phis
) * 100;
1563 fprintf (dump_file
, "Removed %d of %d PHI nodes (%d%%)\n",
1564 stats
.removed_phis
, stats
.total_phis
, (int) percg
);
1567 /* Initialization for this pass. Set up the used data structures. */
1570 tree_dce_init (bool aggressive
)
1572 memset ((void *) &stats
, 0, sizeof (stats
));
1576 last_stmt_necessary
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1577 bitmap_clear (last_stmt_necessary
);
1578 bb_contains_live_stmts
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1579 bitmap_clear (bb_contains_live_stmts
);
1582 processed
= sbitmap_alloc (num_ssa_names
+ 1);
1583 bitmap_clear (processed
);
1585 worklist
.create (64);
1586 cfg_altered
= false;
1589 /* Cleanup after this pass. */
1592 tree_dce_done (bool aggressive
)
1597 sbitmap_free (visited_control_parents
);
1598 sbitmap_free (last_stmt_necessary
);
1599 sbitmap_free (bb_contains_live_stmts
);
1600 bb_contains_live_stmts
= NULL
;
1603 sbitmap_free (processed
);
1605 worklist
.release ();
1608 /* Main routine to eliminate dead code.
1610 AGGRESSIVE controls the aggressiveness of the algorithm.
1611 In conservative mode, we ignore control dependence and simply declare
1612 all but the most trivially dead branches necessary. This mode is fast.
1613 In aggressive mode, control dependences are taken into account, which
1614 results in more dead code elimination, but at the cost of some time.
1616 FIXME: Aggressive mode before PRE doesn't work currently because
1617 the dominance info is not invalidated after DCE1. This is
1618 not an issue right now because we only run aggressive DCE
1619 as the last tree SSA pass, but keep this in mind when you
1620 start experimenting with pass ordering. */
1623 perform_tree_ssa_dce (bool aggressive
)
1625 bool something_changed
= 0;
1627 calculate_dominance_info (CDI_DOMINATORS
);
1629 /* Preheaders are needed for SCEV to work.
1630 Simple lateches and recorded exits improve chances that loop will
1631 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1633 loop_optimizer_init (LOOPS_NORMAL
1634 | LOOPS_HAVE_RECORDED_EXITS
);
1636 tree_dce_init (aggressive
);
1640 /* Compute control dependence. */
1641 calculate_dominance_info (CDI_POST_DOMINATORS
);
1642 cd
= new control_dependences (create_edge_list ());
1644 visited_control_parents
=
1645 sbitmap_alloc (last_basic_block_for_fn (cfun
));
1646 bitmap_clear (visited_control_parents
);
1648 mark_dfs_back_edges ();
1651 find_obviously_necessary_stmts (aggressive
);
1654 loop_optimizer_finalize ();
1660 visited
= BITMAP_ALLOC (NULL
);
1661 propagate_necessity (aggressive
);
1662 BITMAP_FREE (visited
);
1664 something_changed
|= eliminate_unnecessary_stmts ();
1665 something_changed
|= cfg_altered
;
1667 /* We do not update postdominators, so free them unconditionally. */
1668 free_dominance_info (CDI_POST_DOMINATORS
);
1670 /* If we removed paths in the CFG, then we need to update
1671 dominators as well. I haven't investigated the possibility
1672 of incrementally updating dominators. */
1674 free_dominance_info (CDI_DOMINATORS
);
1676 statistics_counter_event (cfun
, "Statements deleted", stats
.removed
);
1677 statistics_counter_event (cfun
, "PHI nodes deleted", stats
.removed_phis
);
1679 /* Debugging dumps. */
1680 if (dump_file
&& (dump_flags
& (TDF_STATS
|TDF_DETAILS
)))
1683 tree_dce_done (aggressive
);
1685 if (something_changed
)
1687 free_numbers_of_iterations_estimates ();
1688 if (scev_initialized_p ())
1690 return TODO_update_ssa
| TODO_cleanup_cfg
;
1695 /* Pass entry points. */
1699 return perform_tree_ssa_dce (/*aggressive=*/false);
1703 tree_ssa_cd_dce (void)
1705 return perform_tree_ssa_dce (/*aggressive=*/optimize
>= 2);
1710 const pass_data pass_data_dce
=
1712 GIMPLE_PASS
, /* type */
1714 OPTGROUP_NONE
, /* optinfo_flags */
1715 TV_TREE_DCE
, /* tv_id */
1716 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1717 0, /* properties_provided */
1718 0, /* properties_destroyed */
1719 0, /* todo_flags_start */
1720 0, /* todo_flags_finish */
1723 class pass_dce
: public gimple_opt_pass
1726 pass_dce (gcc::context
*ctxt
)
1727 : gimple_opt_pass (pass_data_dce
, ctxt
)
1730 /* opt_pass methods: */
1731 opt_pass
* clone () { return new pass_dce (m_ctxt
); }
1732 virtual bool gate (function
*) { return flag_tree_dce
!= 0; }
1733 virtual unsigned int execute (function
*) { return tree_ssa_dce (); }
1735 }; // class pass_dce
1740 make_pass_dce (gcc::context
*ctxt
)
1742 return new pass_dce (ctxt
);
1747 const pass_data pass_data_cd_dce
=
1749 GIMPLE_PASS
, /* type */
1751 OPTGROUP_NONE
, /* optinfo_flags */
1752 TV_TREE_CD_DCE
, /* tv_id */
1753 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1754 0, /* properties_provided */
1755 0, /* properties_destroyed */
1756 0, /* todo_flags_start */
1757 0, /* todo_flags_finish */
1760 class pass_cd_dce
: public gimple_opt_pass
1763 pass_cd_dce (gcc::context
*ctxt
)
1764 : gimple_opt_pass (pass_data_cd_dce
, ctxt
)
1767 /* opt_pass methods: */
1768 opt_pass
* clone () { return new pass_cd_dce (m_ctxt
); }
1769 virtual bool gate (function
*) { return flag_tree_dce
!= 0; }
1770 virtual unsigned int execute (function
*) { return tree_ssa_cd_dce (); }
1772 }; // class pass_cd_dce
1777 make_pass_cd_dce (gcc::context
*ctxt
)
1779 return new pass_cd_dce (ctxt
);