1 /* Dead and redundant store elimination
2 Copyright (C) 2004-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
31 #include "gimple-iterator.h"
35 #include "tree-cfgcleanup.h"
38 #include "tree-ssa-loop.h"
40 /* This file implements dead store elimination.
42 A dead store is a store into a memory location which will later be
43 overwritten by another store without any intervening loads. In this
44 case the earlier store can be deleted or trimmed if the store
47 A redundant store is a store into a memory location which stores
48 the exact same value as a prior store to the same memory location.
49 While this can often be handled by dead store elimination, removing
50 the redundant store is often better than removing or trimming the
53 In our SSA + virtual operand world we use immediate uses of virtual
54 operands to detect these cases. If a store's virtual definition
55 is used precisely once by a later store to the same location which
56 post dominates the first store, then the first store is dead. If
57 the data stored is the same, then the second store is redundant.
59 The single use of the store's virtual definition ensures that
60 there are no intervening aliased loads and the requirement that
61 the second load post dominate the first ensures that if the earlier
62 store executes, then the later stores will execute before the function
65 It may help to think of this as first moving the earlier store to
66 the point immediately before the later store. Again, the single
67 use of the virtual definition and the post-dominance relationship
68 ensure that such movement would be safe. Clearly if there are
69 back to back stores, then the second is makes the first dead. If
70 the second store stores the same value, then the second store is
73 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
74 may also help in understanding this code since it discusses the
75 relationship between dead store and redundant load elimination. In
76 fact, they are the same transformation applied to different views of
79 static void delete_dead_or_redundant_assignment (gimple_stmt_iterator
*, const char *);
80 static void delete_dead_or_redundant_call (gimple_stmt_iterator
*, const char *);
82 /* Bitmap of blocks that have had EH statements cleaned. We should
83 remove their dead edges eventually. */
84 static bitmap need_eh_cleanup
;
86 /* Return value from dse_classify_store */
90 DSE_STORE_MAYBE_PARTIAL_DEAD
,
94 /* STMT is a statement that may write into memory. Analyze it and
95 initialize WRITE to describe how STMT affects memory.
97 Return TRUE if the the statement was analyzed, FALSE otherwise.
99 It is always safe to return FALSE. But typically better optimziation
100 can be achieved by analyzing more statements. */
103 initialize_ao_ref_for_dse (gimple
*stmt
, ao_ref
*write
)
105 /* It's advantageous to handle certain mem* functions. */
106 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
108 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
110 case BUILT_IN_MEMCPY
:
111 case BUILT_IN_MEMMOVE
:
112 case BUILT_IN_MEMSET
:
113 case BUILT_IN_MEMCPY_CHK
:
114 case BUILT_IN_MEMMOVE_CHK
:
115 case BUILT_IN_MEMSET_CHK
:
117 tree size
= NULL_TREE
;
118 if (gimple_call_num_args (stmt
) == 3)
119 size
= gimple_call_arg (stmt
, 2);
120 tree ptr
= gimple_call_arg (stmt
, 0);
121 ao_ref_init_from_ptr_and_size (write
, ptr
, size
);
125 /* A calloc call can never be dead, but it can make
126 subsequent stores redundant if they store 0 into
127 the same memory locations. */
128 case BUILT_IN_CALLOC
:
130 tree nelem
= gimple_call_arg (stmt
, 0);
131 tree selem
= gimple_call_arg (stmt
, 1);
132 if (TREE_CODE (nelem
) == INTEGER_CST
133 && TREE_CODE (selem
) == INTEGER_CST
)
135 tree lhs
= gimple_call_lhs (stmt
);
136 tree size
= fold_build2 (MULT_EXPR
, TREE_TYPE (nelem
),
138 ao_ref_init_from_ptr_and_size (write
, lhs
, size
);
147 else if (is_gimple_assign (stmt
))
149 ao_ref_init (write
, gimple_assign_lhs (stmt
));
155 /* Given REF from the the alias oracle, return TRUE if it is a valid
156 memory reference for dead store elimination, false otherwise.
158 In particular, the reference must have a known base, known maximum
159 size, start at a byte offset and have a size that is one or more
163 valid_ao_ref_for_dse (ao_ref
*ref
)
165 return (ao_ref_base (ref
)
166 && known_size_p (ref
->max_size
)
167 && maybe_ne (ref
->size
, 0)
168 && known_eq (ref
->max_size
, ref
->size
)
169 && known_ge (ref
->offset
, 0)
170 && multiple_p (ref
->offset
, BITS_PER_UNIT
)
171 && multiple_p (ref
->size
, BITS_PER_UNIT
));
174 /* Try to normalize COPY (an ao_ref) relative to REF. Essentially when we are
175 done COPY will only refer bytes found within REF. Return true if COPY
176 is known to intersect at least one byte of REF. */
179 normalize_ref (ao_ref
*copy
, ao_ref
*ref
)
181 if (!ordered_p (copy
->offset
, ref
->offset
))
184 /* If COPY starts before REF, then reset the beginning of
185 COPY to match REF and decrease the size of COPY by the
186 number of bytes removed from COPY. */
187 if (maybe_lt (copy
->offset
, ref
->offset
))
189 poly_int64 diff
= ref
->offset
- copy
->offset
;
190 if (maybe_le (copy
->size
, diff
))
193 copy
->offset
= ref
->offset
;
196 poly_int64 diff
= copy
->offset
- ref
->offset
;
197 if (maybe_le (ref
->size
, diff
))
200 /* If COPY extends beyond REF, chop off its size appropriately. */
201 poly_int64 limit
= ref
->size
- diff
;
202 if (!ordered_p (limit
, copy
->size
))
205 if (maybe_gt (copy
->size
, limit
))
210 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base
211 address written by STMT must match the one found in REF, which must
212 have its base address previously initialized.
214 This routine must be conservative. If we don't know the offset or
215 actual size written, assume nothing was written. */
218 clear_bytes_written_by (sbitmap live_bytes
, gimple
*stmt
, ao_ref
*ref
)
221 if (!initialize_ao_ref_for_dse (stmt
, &write
))
224 /* Verify we have the same base memory address, the write
225 has a known size and overlaps with REF. */
226 HOST_WIDE_INT start
, size
;
227 if (valid_ao_ref_for_dse (&write
)
228 && operand_equal_p (write
.base
, ref
->base
, OEP_ADDRESS_OF
)
229 && known_eq (write
.size
, write
.max_size
)
230 && normalize_ref (&write
, ref
)
231 && (write
.offset
- ref
->offset
).is_constant (&start
)
232 && write
.size
.is_constant (&size
))
233 bitmap_clear_range (live_bytes
, start
/ BITS_PER_UNIT
,
234 size
/ BITS_PER_UNIT
);
237 /* REF is a memory write. Extract relevant information from it and
238 initialize the LIVE_BYTES bitmap. If successful, return TRUE.
239 Otherwise return FALSE. */
242 setup_live_bytes_from_ref (ao_ref
*ref
, sbitmap live_bytes
)
244 HOST_WIDE_INT const_size
;
245 if (valid_ao_ref_for_dse (ref
)
246 && ref
->size
.is_constant (&const_size
)
247 && (const_size
/ BITS_PER_UNIT
248 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE
)))
250 bitmap_clear (live_bytes
);
251 bitmap_set_range (live_bytes
, 0, const_size
/ BITS_PER_UNIT
);
257 /* Compute the number of elements that we can trim from the head and
258 tail of ORIG resulting in a bitmap that is a superset of LIVE.
260 Store the number of elements trimmed from the head and tail in
261 TRIM_HEAD and TRIM_TAIL.
263 STMT is the statement being trimmed and is used for debugging dump
267 compute_trims (ao_ref
*ref
, sbitmap live
, int *trim_head
, int *trim_tail
,
270 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap
271 extends through ref->size. So we know that in the original bitmap
272 bits 0..ref->size were true. We don't actually need the bitmap, just
273 the REF to compute the trims. */
275 /* Now identify how much, if any of the tail we can chop off. */
276 HOST_WIDE_INT const_size
;
277 int last_live
= bitmap_last_set_bit (live
);
278 if (ref
->size
.is_constant (&const_size
))
280 int last_orig
= (const_size
/ BITS_PER_UNIT
) - 1;
281 /* We can leave inconvenient amounts on the tail as
282 residual handling in mem* and str* functions is usually
283 reasonably efficient. */
284 *trim_tail
= last_orig
- last_live
;
286 /* But don't trim away out of bounds accesses, as this defeats
289 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA
290 where TYPE_SIZE_UNIT is not a constant. */
292 && TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))
293 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))) == INTEGER_CST
294 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
)),
301 /* Identify how much, if any of the head we can chop off. */
303 int first_live
= bitmap_first_set_bit (live
);
304 *trim_head
= first_live
- first_orig
;
306 /* If more than a word remains, then make sure to keep the
307 starting point at least word aligned. */
308 if (last_live
- first_live
> UNITS_PER_WORD
)
309 *trim_head
&= ~(UNITS_PER_WORD
- 1);
311 if ((*trim_head
|| *trim_tail
)
312 && dump_file
&& (dump_flags
& TDF_DETAILS
))
314 fprintf (dump_file
, " Trimming statement (head = %d, tail = %d): ",
315 *trim_head
, *trim_tail
);
316 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
317 fprintf (dump_file
, "\n");
321 /* STMT initializes an object from COMPLEX_CST where one or more of the
322 bytes written may be dead stores. REF is a representation of the
323 memory written. LIVE is the bitmap of stores that are actually live.
325 Attempt to rewrite STMT so that only the real or imaginary part of
326 the object is actually stored. */
329 maybe_trim_complex_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
331 int trim_head
, trim_tail
;
332 compute_trims (ref
, live
, &trim_head
, &trim_tail
, stmt
);
334 /* The amount of data trimmed from the head or tail must be at
335 least half the size of the object to ensure we're trimming
336 the entire real or imaginary half. By writing things this
337 way we avoid more O(n) bitmap operations. */
338 if (known_ge (trim_tail
* 2 * BITS_PER_UNIT
, ref
->size
))
340 /* TREE_REALPART is live */
341 tree x
= TREE_REALPART (gimple_assign_rhs1 (stmt
));
342 tree y
= gimple_assign_lhs (stmt
);
343 y
= build1 (REALPART_EXPR
, TREE_TYPE (x
), y
);
344 gimple_assign_set_lhs (stmt
, y
);
345 gimple_assign_set_rhs1 (stmt
, x
);
347 else if (known_ge (trim_head
* 2 * BITS_PER_UNIT
, ref
->size
))
349 /* TREE_IMAGPART is live */
350 tree x
= TREE_IMAGPART (gimple_assign_rhs1 (stmt
));
351 tree y
= gimple_assign_lhs (stmt
);
352 y
= build1 (IMAGPART_EXPR
, TREE_TYPE (x
), y
);
353 gimple_assign_set_lhs (stmt
, y
);
354 gimple_assign_set_rhs1 (stmt
, x
);
357 /* Other cases indicate parts of both the real and imag subobjects
358 are live. We do not try to optimize those cases. */
361 /* STMT initializes an object using a CONSTRUCTOR where one or more of the
362 bytes written are dead stores. ORIG is the bitmap of bytes stored by
363 STMT. LIVE is the bitmap of stores that are actually live.
365 Attempt to rewrite STMT so that only the real or imaginary part of
366 the object is actually stored.
368 The most common case for getting here is a CONSTRUCTOR with no elements
369 being used to zero initialize an object. We do not try to handle other
370 cases as those would force us to fully cover the object with the
371 CONSTRUCTOR node except for the components that are dead. */
374 maybe_trim_constructor_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
376 tree ctor
= gimple_assign_rhs1 (stmt
);
378 /* This is the only case we currently handle. It actually seems to
379 catch most cases of actual interest. */
380 gcc_assert (CONSTRUCTOR_NELTS (ctor
) == 0);
384 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
386 /* Now we want to replace the constructor initializer
387 with memset (object + head_trim, 0, size - head_trim - tail_trim). */
388 if (head_trim
|| tail_trim
)
390 /* We want &lhs for the MEM_REF expression. */
391 tree lhs_addr
= build_fold_addr_expr (gimple_assign_lhs (stmt
));
393 if (! is_gimple_min_invariant (lhs_addr
))
396 /* The number of bytes for the new constructor. */
397 poly_int64 ref_bytes
= exact_div (ref
->size
, BITS_PER_UNIT
);
398 poly_int64 count
= ref_bytes
- head_trim
- tail_trim
;
400 /* And the new type for the CONSTRUCTOR. Essentially it's just
401 a char array large enough to cover the non-trimmed parts of
402 the original CONSTRUCTOR. Note we want explicit bounds here
403 so that we know how many bytes to clear when expanding the
405 tree type
= build_array_type_nelts (char_type_node
, count
);
407 /* Build a suitable alias type rather than using alias set zero
408 to avoid pessimizing. */
409 tree alias_type
= reference_alias_ptr_type (gimple_assign_lhs (stmt
));
411 /* Build a MEM_REF representing the whole accessed area, starting
412 at the first byte not trimmed. */
413 tree exp
= fold_build2 (MEM_REF
, type
, lhs_addr
,
414 build_int_cst (alias_type
, head_trim
));
416 /* Now update STMT with a new RHS and LHS. */
417 gimple_assign_set_lhs (stmt
, exp
);
418 gimple_assign_set_rhs1 (stmt
, build_constructor (type
, NULL
));
422 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes
423 copied/set by DECREMENT. */
425 decrement_count (gimple
*stmt
, int decrement
)
427 tree
*countp
= gimple_call_arg_ptr (stmt
, 2);
428 gcc_assert (TREE_CODE (*countp
) == INTEGER_CST
);
429 *countp
= wide_int_to_tree (TREE_TYPE (*countp
), (TREE_INT_CST_LOW (*countp
)
435 increment_start_addr (gimple
*stmt
, tree
*where
, int increment
)
437 if (TREE_CODE (*where
) == SSA_NAME
)
439 tree tem
= make_ssa_name (TREE_TYPE (*where
));
441 = gimple_build_assign (tem
, POINTER_PLUS_EXPR
, *where
,
442 build_int_cst (sizetype
, increment
));
443 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
444 gsi_insert_before (&gsi
, newop
, GSI_SAME_STMT
);
446 update_stmt (gsi_stmt (gsi
));
450 *where
= build_fold_addr_expr (fold_build2 (MEM_REF
, char_type_node
,
452 build_int_cst (ptr_type_node
,
456 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
457 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce
458 the amount of data it actually writes.
460 Right now we only support trimming from the head or the tail of the
461 memory region. In theory we could split the mem* call, but it's
462 likely of marginal value. */
465 maybe_trim_memstar_call (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
467 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
469 case BUILT_IN_MEMCPY
:
470 case BUILT_IN_MEMMOVE
:
471 case BUILT_IN_MEMCPY_CHK
:
472 case BUILT_IN_MEMMOVE_CHK
:
474 int head_trim
, tail_trim
;
475 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
477 /* Tail trimming is easy, we can just reduce the count. */
479 decrement_count (stmt
, tail_trim
);
481 /* Head trimming requires adjusting all the arguments. */
484 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
485 increment_start_addr (stmt
, dst
, head_trim
);
486 tree
*src
= gimple_call_arg_ptr (stmt
, 1);
487 increment_start_addr (stmt
, src
, head_trim
);
488 decrement_count (stmt
, head_trim
);
493 case BUILT_IN_MEMSET
:
494 case BUILT_IN_MEMSET_CHK
:
496 int head_trim
, tail_trim
;
497 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
499 /* Tail trimming is easy, we can just reduce the count. */
501 decrement_count (stmt
, tail_trim
);
503 /* Head trimming requires adjusting all the arguments. */
506 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
507 increment_start_addr (stmt
, dst
, head_trim
);
508 decrement_count (stmt
, head_trim
);
518 /* STMT is a memory write where one or more bytes written are dead
519 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the
520 bitmap of stores that are actually live.
522 Attempt to rewrite STMT so that it writes fewer memory locations. Right
523 now we only support trimming at the start or end of the memory region.
524 It's not clear how much there is to be gained by trimming from the middle
528 maybe_trim_partially_dead_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
530 if (is_gimple_assign (stmt
)
531 && TREE_CODE (gimple_assign_lhs (stmt
)) != TARGET_MEM_REF
)
533 switch (gimple_assign_rhs_code (stmt
))
536 maybe_trim_constructor_store (ref
, live
, stmt
);
539 maybe_trim_complex_store (ref
, live
, stmt
);
547 /* Return TRUE if USE_REF reads bytes from LIVE where live is
548 derived from REF, a write reference.
550 While this routine may modify USE_REF, it's passed by value, not
551 location. So callers do not see those modifications. */
554 live_bytes_read (ao_ref use_ref
, ao_ref
*ref
, sbitmap live
)
556 /* We have already verified that USE_REF and REF hit the same object.
557 Now verify that there's actually an overlap between USE_REF and REF. */
558 HOST_WIDE_INT start
, size
;
559 if (normalize_ref (&use_ref
, ref
)
560 && (use_ref
.offset
- ref
->offset
).is_constant (&start
)
561 && use_ref
.size
.is_constant (&size
))
563 /* If USE_REF covers all of REF, then it will hit one or more
564 live bytes. This avoids useless iteration over the bitmap
566 if (start
== 0 && known_eq (size
, ref
->size
))
569 /* Now check if any of the remaining bits in use_ref are set in LIVE. */
570 return bitmap_bit_in_range_p (live
, start
/ BITS_PER_UNIT
,
571 (start
+ size
- 1) / BITS_PER_UNIT
);
576 /* Callback for dse_classify_store calling for_each_index. Verify that
577 indices are invariant in the loop with backedge PHI in basic-block DATA. */
580 check_name (tree
, tree
*idx
, void *data
)
582 basic_block phi_bb
= (basic_block
) data
;
583 if (TREE_CODE (*idx
) == SSA_NAME
584 && !SSA_NAME_IS_DEFAULT_DEF (*idx
)
585 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (SSA_NAME_DEF_STMT (*idx
)),
591 /* STMT stores the value 0 into one or more memory locations
592 (via memset, empty constructor, calloc call, etc).
594 See if there is a subsequent store of the value 0 to one
595 or more of the same memory location(s). If so, the subsequent
596 store is redundant and can be removed.
598 The subsequent stores could be via memset, empty constructors,
599 simple MEM stores, etc. */
602 dse_optimize_redundant_stores (gimple
*stmt
)
606 /* We could do something fairly complex and look through PHIs
607 like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
610 Look at all the immediate uses of the VDEF (which are obviously
611 dominated by STMT). See if one or more stores 0 into the same
612 memory locations a STMT, if so remove the immediate use statements. */
613 tree defvar
= gimple_vdef (stmt
);
616 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
618 /* Limit stmt walking. */
619 if (++cnt
> PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE
))
620 BREAK_FROM_IMM_USE_STMT (ui
);
622 /* If USE_STMT stores 0 into one or more of the same locations
623 as STMT and STMT would kill USE_STMT, then we can just remove
626 if ((is_gimple_assign (use_stmt
)
627 && gimple_vdef (use_stmt
)
628 && ((gimple_assign_rhs_code (use_stmt
) == CONSTRUCTOR
629 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (use_stmt
)) == 0
630 && !gimple_clobber_p (stmt
))
631 || (gimple_assign_rhs_code (use_stmt
) == INTEGER_CST
632 && integer_zerop (gimple_assign_rhs1 (use_stmt
)))))
633 || (gimple_call_builtin_p (use_stmt
, BUILT_IN_NORMAL
)
634 && (fndecl
= gimple_call_fndecl (use_stmt
)) != NULL
635 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
636 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
637 && integer_zerop (gimple_call_arg (use_stmt
, 1))))
641 if (!initialize_ao_ref_for_dse (use_stmt
, &write
))
642 BREAK_FROM_IMM_USE_STMT (ui
)
644 if (valid_ao_ref_for_dse (&write
)
645 && stmt_kills_ref_p (stmt
, &write
))
647 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
648 if (is_gimple_assign (use_stmt
))
649 delete_dead_or_redundant_assignment (&gsi
, "redundant");
650 else if (is_gimple_call (use_stmt
))
651 delete_dead_or_redundant_call (&gsi
, "redundant");
659 /* A helper of dse_optimize_stmt.
660 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
661 according to downstream uses and defs. Sets *BY_CLOBBER_P to true
662 if only clobber statements influenced the classification result.
663 Returns the classification. */
665 static dse_store_status
666 dse_classify_store (ao_ref
*ref
, gimple
*stmt
,
667 bool byte_tracking_enabled
, sbitmap live_bytes
,
668 bool *by_clobber_p
= NULL
)
675 *by_clobber_p
= true;
677 /* Find the first dominated statement that clobbers (part of) the
678 memory stmt stores to with no intermediate statement that may use
679 part of the memory stmt stores. That is, find a store that may
680 prove stmt to be a dead store. */
689 if (gimple_code (temp
) == GIMPLE_PHI
)
691 /* If we visit this PHI by following a backedge then we have to
692 make sure ref->ref only refers to SSA names that are invariant
693 with respect to the loop represented by this PHI node. */
694 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (stmt
),
696 && !for_each_index (ref
->ref
? &ref
->ref
: &ref
->base
,
697 check_name
, gimple_bb (temp
)))
698 return DSE_STORE_LIVE
;
699 defvar
= PHI_RESULT (temp
);
700 bitmap_set_bit (visited
, SSA_NAME_VERSION (defvar
));
703 defvar
= gimple_vdef (temp
);
704 auto_vec
<gimple
*, 10> defs
;
705 gimple
*phi_def
= NULL
;
706 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
708 /* Limit stmt walking. */
709 if (++cnt
> PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE
))
712 BREAK_FROM_IMM_USE_STMT (ui
);
715 /* We have visited ourselves already so ignore STMT for the
716 purpose of chaining. */
717 if (use_stmt
== stmt
)
719 /* In simple cases we can look through PHI nodes, but we
720 have to be careful with loops and with memory references
721 containing operands that are also operands of PHI nodes.
722 See gcc.c-torture/execute/20051110-*.c. */
723 else if (gimple_code (use_stmt
) == GIMPLE_PHI
)
725 /* If we already visited this PHI ignore it for further
727 if (!bitmap_bit_p (visited
,
728 SSA_NAME_VERSION (PHI_RESULT (use_stmt
))))
730 defs
.safe_push (use_stmt
);
734 /* If the statement is a use the store is not dead. */
735 else if (ref_maybe_used_by_stmt_p (use_stmt
, ref
))
737 /* Handle common cases where we can easily build an ao_ref
738 structure for USE_STMT and in doing so we find that the
739 references hit non-live bytes and thus can be ignored. */
740 if (byte_tracking_enabled
741 && is_gimple_assign (use_stmt
))
744 ao_ref_init (&use_ref
, gimple_assign_rhs1 (use_stmt
));
745 if (valid_ao_ref_for_dse (&use_ref
)
746 && use_ref
.base
== ref
->base
747 && known_eq (use_ref
.size
, use_ref
.max_size
)
748 && !live_bytes_read (use_ref
, ref
, live_bytes
))
750 /* If this is a store, remember it as we possibly
751 need to walk the defs uses. */
752 if (gimple_vdef (use_stmt
))
753 defs
.safe_push (use_stmt
);
759 BREAK_FROM_IMM_USE_STMT (ui
);
761 /* If this is a store, remember it as we possibly need to walk the
763 else if (gimple_vdef (use_stmt
))
764 defs
.safe_push (use_stmt
);
769 /* STMT might be partially dead and we may be able to reduce
770 how many memory locations it stores into. */
771 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
772 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
773 return DSE_STORE_LIVE
;
776 /* If we didn't find any definition this means the store is dead
777 if it isn't a store to global reachable memory. In this case
778 just pretend the stmt makes itself dead. Otherwise fail. */
779 if (defs
.is_empty ())
781 if (ref_may_alias_global_p (ref
))
782 return DSE_STORE_LIVE
;
785 *by_clobber_p
= false;
786 return DSE_STORE_DEAD
;
789 /* Process defs and remove those we need not process further. */
790 for (unsigned i
= 0; i
< defs
.length ();)
792 gimple
*def
= defs
[i
];
795 /* If the path to check starts with a kill we do not need to
797 ??? With byte tracking we need only kill the bytes currently
799 if (stmt_kills_ref_p (def
, ref
))
801 if (by_clobber_p
&& !gimple_clobber_p (def
))
802 *by_clobber_p
= false;
803 defs
.unordered_remove (i
);
805 /* In addition to kills we can remove defs whose only use
806 is another def in defs. That can only ever be PHIs of which
807 we track a single for simplicity reasons (we fail for multiple
808 PHIs anyways). We can also ignore defs that feed only into
809 already visited PHIs. */
810 else if (gimple_code (def
) != GIMPLE_PHI
811 && single_imm_use (gimple_vdef (def
), &use_p
, &use_stmt
)
812 && (use_stmt
== phi_def
813 || (gimple_code (use_stmt
) == GIMPLE_PHI
814 && bitmap_bit_p (visited
,
816 (PHI_RESULT (use_stmt
))))))
817 defs
.unordered_remove (i
);
822 /* If all defs kill the ref we are done. */
823 if (defs
.is_empty ())
824 return DSE_STORE_DEAD
;
825 /* If more than one def survives fail. */
826 if (defs
.length () > 1)
828 /* STMT might be partially dead and we may be able to reduce
829 how many memory locations it stores into. */
830 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
831 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
832 return DSE_STORE_LIVE
;
836 /* Track partial kills. */
837 if (byte_tracking_enabled
)
839 clear_bytes_written_by (live_bytes
, temp
, ref
);
840 if (bitmap_empty_p (live_bytes
))
842 if (by_clobber_p
&& !gimple_clobber_p (temp
))
843 *by_clobber_p
= false;
844 return DSE_STORE_DEAD
;
848 /* Continue walking until there are no more live bytes. */
853 class dse_dom_walker
: public dom_walker
856 dse_dom_walker (cdi_direction direction
)
857 : dom_walker (direction
),
858 m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE
)),
859 m_byte_tracking_enabled (false) {}
861 virtual edge
before_dom_children (basic_block
);
864 auto_sbitmap m_live_bytes
;
865 bool m_byte_tracking_enabled
;
866 void dse_optimize_stmt (gimple_stmt_iterator
*);
869 /* Delete a dead call at GSI, which is mem* call of some kind. */
871 delete_dead_or_redundant_call (gimple_stmt_iterator
*gsi
, const char *type
)
873 gimple
*stmt
= gsi_stmt (*gsi
);
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, " Deleted %s call: ", type
);
877 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
878 fprintf (dump_file
, "\n");
881 tree lhs
= gimple_call_lhs (stmt
);
884 tree ptr
= gimple_call_arg (stmt
, 0);
885 gimple
*new_stmt
= gimple_build_assign (lhs
, ptr
);
886 unlink_stmt_vdef (stmt
);
887 if (gsi_replace (gsi
, new_stmt
, true))
888 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
892 /* Then we need to fix the operand of the consuming stmt. */
893 unlink_stmt_vdef (stmt
);
895 /* Remove the dead store. */
896 if (gsi_remove (gsi
, true))
897 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
902 /* Delete a dead store at GSI, which is a gimple assignment. */
905 delete_dead_or_redundant_assignment (gimple_stmt_iterator
*gsi
, const char *type
)
907 gimple
*stmt
= gsi_stmt (*gsi
);
908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
910 fprintf (dump_file
, " Deleted %s store: ", type
);
911 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
912 fprintf (dump_file
, "\n");
915 /* Then we need to fix the operand of the consuming stmt. */
916 unlink_stmt_vdef (stmt
);
918 /* Remove the dead store. */
919 basic_block bb
= gimple_bb (stmt
);
920 if (gsi_remove (gsi
, true))
921 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
923 /* And release any SSA_NAMEs set in this statement back to the
928 /* Attempt to eliminate dead stores in the statement referenced by BSI.
930 A dead store is a store into a memory location which will later be
931 overwritten by another store without any intervening loads. In this
932 case the earlier store can be deleted.
934 In our SSA + virtual operand world we use immediate uses of virtual
935 operands to detect dead stores. If a store's virtual definition
936 is used precisely once by a later store to the same location which
937 post dominates the first store, then the first store is dead. */
940 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator
*gsi
)
942 gimple
*stmt
= gsi_stmt (*gsi
);
944 /* If this statement has no virtual defs, then there is nothing
946 if (!gimple_vdef (stmt
))
949 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
950 if (gimple_has_volatile_ops (stmt
)
951 && (!gimple_clobber_p (stmt
)
952 || TREE_CODE (gimple_assign_lhs (stmt
)) != MEM_REF
))
956 if (!initialize_ao_ref_for_dse (stmt
, &ref
))
959 /* We know we have virtual definitions. We can handle assignments and
960 some builtin calls. */
961 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
963 tree fndecl
= gimple_call_fndecl (stmt
);
964 switch (DECL_FUNCTION_CODE (fndecl
))
966 case BUILT_IN_MEMCPY
:
967 case BUILT_IN_MEMMOVE
:
968 case BUILT_IN_MEMSET
:
969 case BUILT_IN_MEMCPY_CHK
:
970 case BUILT_IN_MEMMOVE_CHK
:
971 case BUILT_IN_MEMSET_CHK
:
973 /* Occasionally calls with an explicit length of zero
974 show up in the IL. It's pointless to do analysis
975 on them, they're trivially dead. */
976 tree size
= gimple_call_arg (stmt
, 2);
977 if (integer_zerop (size
))
979 delete_dead_or_redundant_call (gsi
, "dead");
983 /* If this is a memset call that initializes an object
984 to zero, it may be redundant with an earlier memset
985 or empty CONSTRUCTOR of a larger object. */
986 if ((DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
987 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
988 && integer_zerop (gimple_call_arg (stmt
, 1)))
989 dse_optimize_redundant_stores (stmt
);
991 enum dse_store_status store_status
;
992 m_byte_tracking_enabled
993 = setup_live_bytes_from_ref (&ref
, m_live_bytes
);
994 store_status
= dse_classify_store (&ref
, stmt
,
995 m_byte_tracking_enabled
,
997 if (store_status
== DSE_STORE_LIVE
)
1000 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1002 maybe_trim_memstar_call (&ref
, m_live_bytes
, stmt
);
1006 if (store_status
== DSE_STORE_DEAD
)
1007 delete_dead_or_redundant_call (gsi
, "dead");
1011 case BUILT_IN_CALLOC
:
1012 /* We already know the arguments are integer constants. */
1013 dse_optimize_redundant_stores (stmt
);
1020 if (is_gimple_assign (stmt
))
1022 bool by_clobber_p
= false;
1024 /* First see if this store is a CONSTRUCTOR and if there
1025 are subsequent CONSTRUCTOR stores which are totally
1026 subsumed by this statement. If so remove the subsequent
1029 This will tend to make fewer calls into memset with longer
1031 if (gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
1032 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
)) == 0
1033 && !gimple_clobber_p (stmt
))
1034 dse_optimize_redundant_stores (stmt
);
1036 /* Self-assignments are zombies. */
1037 if (operand_equal_p (gimple_assign_rhs1 (stmt
),
1038 gimple_assign_lhs (stmt
), 0))
1042 m_byte_tracking_enabled
1043 = setup_live_bytes_from_ref (&ref
, m_live_bytes
);
1044 enum dse_store_status store_status
;
1045 store_status
= dse_classify_store (&ref
, stmt
,
1046 m_byte_tracking_enabled
,
1047 m_live_bytes
, &by_clobber_p
);
1048 if (store_status
== DSE_STORE_LIVE
)
1051 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1053 maybe_trim_partially_dead_store (&ref
, m_live_bytes
, stmt
);
1058 /* Now we know that use_stmt kills the LHS of stmt. */
1060 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
1061 another clobber stmt. */
1062 if (gimple_clobber_p (stmt
)
1066 delete_dead_or_redundant_assignment (gsi
, "dead");
1071 dse_dom_walker::before_dom_children (basic_block bb
)
1073 gimple_stmt_iterator gsi
;
1075 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
1077 dse_optimize_stmt (&gsi
);
1078 if (gsi_end_p (gsi
))
1079 gsi
= gsi_last_bb (bb
);
1088 const pass_data pass_data_dse
=
1090 GIMPLE_PASS
, /* type */
1092 OPTGROUP_NONE
, /* optinfo_flags */
1093 TV_TREE_DSE
, /* tv_id */
1094 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1095 0, /* properties_provided */
1096 0, /* properties_destroyed */
1097 0, /* todo_flags_start */
1098 0, /* todo_flags_finish */
1101 class pass_dse
: public gimple_opt_pass
1104 pass_dse (gcc::context
*ctxt
)
1105 : gimple_opt_pass (pass_data_dse
, ctxt
)
1108 /* opt_pass methods: */
1109 opt_pass
* clone () { return new pass_dse (m_ctxt
); }
1110 virtual bool gate (function
*) { return flag_tree_dse
!= 0; }
1111 virtual unsigned int execute (function
*);
1113 }; // class pass_dse
1116 pass_dse::execute (function
*fun
)
1118 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
1120 renumber_gimple_stmt_uids ();
1122 /* We might consider making this a property of each pass so that it
1123 can be [re]computed on an as-needed basis. Particularly since
1124 this pass could be seen as an extension of DCE which needs post
1126 calculate_dominance_info (CDI_POST_DOMINATORS
);
1127 calculate_dominance_info (CDI_DOMINATORS
);
1129 /* Dead store elimination is fundamentally a walk of the post-dominator
1130 tree and a backwards walk of statements within each block. */
1131 dse_dom_walker (CDI_POST_DOMINATORS
).walk (fun
->cfg
->x_exit_block_ptr
);
1133 /* Removal of stores may make some EH edges dead. Purge such edges from
1134 the CFG as needed. */
1135 if (!bitmap_empty_p (need_eh_cleanup
))
1137 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
1138 cleanup_tree_cfg ();
1141 BITMAP_FREE (need_eh_cleanup
);
1143 /* For now, just wipe the post-dominator information. */
1144 free_dominance_info (CDI_POST_DOMINATORS
);
1151 make_pass_dse (gcc::context
*ctxt
)
1153 return new pass_dse (ctxt
);