1 /* Dead and redundant store elimination
2 Copyright (C) 2004-2023 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/>. */
21 #define INCLUDE_MEMORY
23 #include "coretypes.h"
28 #include "tree-pass.h"
30 #include "gimple-pretty-print.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
35 #include "tree-cfgcleanup.h"
37 #include "tree-ssa-loop.h"
38 #include "tree-ssa-dse.h"
40 #include "gimple-fold.h"
45 #include "ipa-modref-tree.h"
46 #include "ipa-modref.h"
48 #include "tree-ssa-loop-niter.h"
50 #include "tree-data-ref.h"
51 #include "internal-fn.h"
53 /* This file implements dead store elimination.
55 A dead store is a store into a memory location which will later be
56 overwritten by another store without any intervening loads. In this
57 case the earlier store can be deleted or trimmed if the store
60 A redundant store is a store into a memory location which stores
61 the exact same value as a prior store to the same memory location.
62 While this can often be handled by dead store elimination, removing
63 the redundant store is often better than removing or trimming the
66 In our SSA + virtual operand world we use immediate uses of virtual
67 operands to detect these cases. If a store's virtual definition
68 is used precisely once by a later store to the same location which
69 post dominates the first store, then the first store is dead. If
70 the data stored is the same, then the second store is redundant.
72 The single use of the store's virtual definition ensures that
73 there are no intervening aliased loads and the requirement that
74 the second load post dominate the first ensures that if the earlier
75 store executes, then the later stores will execute before the function
78 It may help to think of this as first moving the earlier store to
79 the point immediately before the later store. Again, the single
80 use of the virtual definition and the post-dominance relationship
81 ensure that such movement would be safe. Clearly if there are
82 back to back stores, then the second is makes the first dead. If
83 the second store stores the same value, then the second store is
86 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
87 may also help in understanding this code since it discusses the
88 relationship between dead store and redundant load elimination. In
89 fact, they are the same transformation applied to different views of
92 static void delete_dead_or_redundant_call (gimple_stmt_iterator
*, const char *);
94 /* Bitmap of blocks that have had EH statements cleaned. We should
95 remove their dead edges eventually. */
96 static bitmap need_eh_cleanup
;
97 static bitmap need_ab_cleanup
;
99 /* STMT is a statement that may write into memory. Analyze it and
100 initialize WRITE to describe how STMT affects memory. When
101 MAY_DEF_OK is true then the function initializes WRITE to what
104 Return TRUE if the statement was analyzed, FALSE otherwise.
106 It is always safe to return FALSE. But typically better optimziation
107 can be achieved by analyzing more statements. */
110 initialize_ao_ref_for_dse (gimple
*stmt
, ao_ref
*write
, bool may_def_ok
= false)
112 /* It's advantageous to handle certain mem* functions. */
113 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
115 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
117 case BUILT_IN_MEMCPY
:
118 case BUILT_IN_MEMMOVE
:
119 case BUILT_IN_MEMSET
:
120 case BUILT_IN_MEMCPY_CHK
:
121 case BUILT_IN_MEMMOVE_CHK
:
122 case BUILT_IN_MEMSET_CHK
:
123 case BUILT_IN_STRNCPY
:
124 case BUILT_IN_STRNCPY_CHK
:
126 tree size
= gimple_call_arg (stmt
, 2);
127 tree ptr
= gimple_call_arg (stmt
, 0);
128 ao_ref_init_from_ptr_and_size (write
, ptr
, size
);
132 /* A calloc call can never be dead, but it can make
133 subsequent stores redundant if they store 0 into
134 the same memory locations. */
135 case BUILT_IN_CALLOC
:
137 tree nelem
= gimple_call_arg (stmt
, 0);
138 tree selem
= gimple_call_arg (stmt
, 1);
140 if (TREE_CODE (nelem
) == INTEGER_CST
141 && TREE_CODE (selem
) == INTEGER_CST
142 && (lhs
= gimple_call_lhs (stmt
)) != NULL_TREE
)
144 tree size
= fold_build2 (MULT_EXPR
, TREE_TYPE (nelem
),
146 ao_ref_init_from_ptr_and_size (write
, lhs
, size
);
155 else if (is_gimple_call (stmt
)
156 && gimple_call_internal_p (stmt
))
158 switch (gimple_call_internal_fn (stmt
))
162 case IFN_LEN_MASK_STORE
:
164 int stored_value_index
165 = internal_fn_stored_value_index (gimple_call_internal_fn (stmt
));
166 if (gimple_call_internal_fn (stmt
) == IFN_LEN_STORE
)
168 tree len
= gimple_call_arg (stmt
, 2);
169 tree bias
= gimple_call_arg (stmt
, 4);
170 if (tree_fits_uhwi_p (len
))
172 ao_ref_init_from_ptr_and_size (write
,
173 gimple_call_arg (stmt
, 0),
174 int_const_binop (MINUS_EXPR
,
179 /* We cannot initialize a must-def ao_ref (in all cases) but we
180 can provide a may-def variant. */
183 ao_ref_init_from_ptr_and_size (
184 write
, gimple_call_arg (stmt
, 0),
186 TREE_TYPE (gimple_call_arg (stmt
, stored_value_index
))));
194 if (tree lhs
= gimple_get_lhs (stmt
))
196 if (TREE_CODE (lhs
) != SSA_NAME
197 && (may_def_ok
|| !stmt_could_throw_p (cfun
, stmt
)))
199 ao_ref_init (write
, lhs
);
206 /* Given REF from the alias oracle, return TRUE if it is a valid
207 kill memory reference for dead store elimination, false otherwise.
209 In particular, the reference must have a known base, known maximum
210 size, start at a byte offset and have a size that is one or more
214 valid_ao_ref_kill_for_dse (ao_ref
*ref
)
216 return (ao_ref_base (ref
)
217 && known_size_p (ref
->max_size
)
218 && maybe_ne (ref
->size
, 0)
219 && known_eq (ref
->max_size
, ref
->size
)
220 && known_ge (ref
->offset
, 0));
223 /* Given REF from the alias oracle, return TRUE if it is a valid
224 load or store memory reference for dead store elimination, false otherwise.
226 Unlike for valid_ao_ref_kill_for_dse we can accept writes where max_size
227 is not same as size since we can handle conservatively the larger range. */
230 valid_ao_ref_for_dse (ao_ref
*ref
)
232 return (ao_ref_base (ref
)
233 && known_size_p (ref
->max_size
)
234 && known_ge (ref
->offset
, 0));
237 /* Initialize OFFSET and SIZE to a range known to contain REF
238 where the boundaries are divisible by BITS_PER_UNIT (bit still in bits).
239 Return false if this is impossible. */
242 get_byte_aligned_range_containing_ref (ao_ref
*ref
, poly_int64
*offset
,
245 if (!known_size_p (ref
->max_size
))
247 *offset
= aligned_lower_bound (ref
->offset
, BITS_PER_UNIT
);
248 poly_int64 end
= aligned_upper_bound (ref
->offset
+ ref
->max_size
,
250 return (end
- *offset
).is_constant (size
);
253 /* Initialize OFFSET and SIZE to a range known to be contained REF
254 where the boundaries are divisible by BITS_PER_UNIT (but still in bits).
255 Return false if this is impossible. */
258 get_byte_aligned_range_contained_in_ref (ao_ref
*ref
, poly_int64
*offset
,
261 if (!known_size_p (ref
->size
)
262 || !known_eq (ref
->size
, ref
->max_size
))
264 *offset
= aligned_upper_bound (ref
->offset
, BITS_PER_UNIT
);
265 poly_int64 end
= aligned_lower_bound (ref
->offset
+ ref
->max_size
,
267 /* For bit accesses we can get -1 here, but also 0 sized kill is not
269 if (!known_gt (end
, *offset
))
271 return (end
- *offset
).is_constant (size
);
274 /* Compute byte range (returned iN REF_OFFSET and RET_SIZE) for access COPY
275 inside REF. If KILL is true, then COPY represent a kill and the byte range
276 needs to be fully contained in bit range given by COPY. If KILL is false
277 then the byte range returned must contain the range of COPY. */
280 get_byte_range (ao_ref
*copy
, ao_ref
*ref
, bool kill
,
281 HOST_WIDE_INT
*ret_offset
, HOST_WIDE_INT
*ret_size
)
283 HOST_WIDE_INT copy_size
, ref_size
;
284 poly_int64 copy_offset
, ref_offset
;
287 /* First translate from bits to bytes, rounding to bigger or smaller ranges
288 as needed. Kills needs to be always rounded to smaller ranges while
289 uses and stores to larger ranges. */
292 if (!get_byte_aligned_range_contained_in_ref (copy
, ©_offset
,
298 if (!get_byte_aligned_range_containing_ref (copy
, ©_offset
,
303 if (!get_byte_aligned_range_containing_ref (ref
, &ref_offset
, &ref_size
)
304 || !ordered_p (copy_offset
, ref_offset
))
307 /* Switch sizes from bits to bytes so we do not need to care about
308 overflows. Offset calculation needs to stay in bits until we compute
309 the difference and can switch to HOST_WIDE_INT. */
310 copy_size
/= BITS_PER_UNIT
;
311 ref_size
/= BITS_PER_UNIT
;
313 /* If COPY starts before REF, then reset the beginning of
314 COPY to match REF and decrease the size of COPY by the
315 number of bytes removed from COPY. */
316 if (maybe_lt (copy_offset
, ref_offset
))
318 if (!(ref_offset
- copy_offset
).is_constant (&diff
)
319 || copy_size
< diff
/ BITS_PER_UNIT
)
321 copy_size
-= diff
/ BITS_PER_UNIT
;
322 copy_offset
= ref_offset
;
325 if (!(copy_offset
- ref_offset
).is_constant (&diff
)
326 || ref_size
<= diff
/ BITS_PER_UNIT
)
329 /* If COPY extends beyond REF, chop off its size appropriately. */
330 HOST_WIDE_INT limit
= ref_size
- diff
/ BITS_PER_UNIT
;
332 if (copy_size
> limit
)
334 *ret_size
= copy_size
;
335 if (!(copy_offset
- ref_offset
).is_constant (ret_offset
))
337 *ret_offset
/= BITS_PER_UNIT
;
341 /* Update LIVE_BYTES tracking REF for write to WRITE:
342 Verify we have the same base memory address, the write
343 has a known size and overlaps with REF. */
345 clear_live_bytes_for_ref (sbitmap live_bytes
, ao_ref
*ref
, ao_ref
*write
)
347 HOST_WIDE_INT start
, size
;
349 if (valid_ao_ref_kill_for_dse (write
)
350 && operand_equal_p (write
->base
, ref
->base
, OEP_ADDRESS_OF
)
351 && get_byte_range (write
, ref
, true, &start
, &size
))
352 bitmap_clear_range (live_bytes
, start
, size
);
355 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base
356 address written by STMT must match the one found in REF, which must
357 have its base address previously initialized.
359 This routine must be conservative. If we don't know the offset or
360 actual size written, assume nothing was written. */
363 clear_bytes_written_by (sbitmap live_bytes
, gimple
*stmt
, ao_ref
*ref
)
367 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
370 modref_summary
*summary
= get_modref_function_summary (call
, &interposed
);
372 if (summary
&& !interposed
)
373 for (auto kill
: summary
->kills
)
374 if (kill
.get_ao_ref (as_a
<gcall
*> (stmt
), &write
))
375 clear_live_bytes_for_ref (live_bytes
, ref
, &write
);
377 if (!initialize_ao_ref_for_dse (stmt
, &write
))
380 clear_live_bytes_for_ref (live_bytes
, ref
, &write
);
383 /* REF is a memory write. Extract relevant information from it and
384 initialize the LIVE_BYTES bitmap. If successful, return TRUE.
385 Otherwise return FALSE. */
388 setup_live_bytes_from_ref (ao_ref
*ref
, sbitmap live_bytes
)
390 HOST_WIDE_INT const_size
;
391 if (valid_ao_ref_for_dse (ref
)
392 && ((aligned_upper_bound (ref
->offset
+ ref
->max_size
, BITS_PER_UNIT
)
393 - aligned_lower_bound (ref
->offset
,
394 BITS_PER_UNIT
)).is_constant (&const_size
))
395 && (const_size
/ BITS_PER_UNIT
<= param_dse_max_object_size
)
398 bitmap_clear (live_bytes
);
399 bitmap_set_range (live_bytes
, 0, const_size
/ BITS_PER_UNIT
);
405 /* Compute the number of elements that we can trim from the head and
406 tail of ORIG resulting in a bitmap that is a superset of LIVE.
408 Store the number of elements trimmed from the head and tail in
409 TRIM_HEAD and TRIM_TAIL.
411 STMT is the statement being trimmed and is used for debugging dump
415 compute_trims (ao_ref
*ref
, sbitmap live
, int *trim_head
, int *trim_tail
,
418 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap
419 extends through ref->size. So we know that in the original bitmap
420 bits 0..ref->size were true. We don't actually need the bitmap, just
421 the REF to compute the trims. */
423 /* Now identify how much, if any of the tail we can chop off. */
424 HOST_WIDE_INT const_size
;
425 int last_live
= bitmap_last_set_bit (live
);
426 if (ref
->size
.is_constant (&const_size
))
428 int last_orig
= (const_size
/ BITS_PER_UNIT
) - 1;
429 /* We can leave inconvenient amounts on the tail as
430 residual handling in mem* and str* functions is usually
431 reasonably efficient. */
432 *trim_tail
= last_orig
- last_live
;
434 /* But don't trim away out of bounds accesses, as this defeats
437 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA
438 where TYPE_SIZE_UNIT is not a constant. */
440 && TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))
441 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))) == INTEGER_CST
442 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
)),
449 /* Identify how much, if any of the head we can chop off. */
451 int first_live
= bitmap_first_set_bit (live
);
452 *trim_head
= first_live
- first_orig
;
454 /* If REF is aligned, try to maintain this alignment if it reduces
455 the number of (power-of-two sized aligned) writes to memory. */
456 unsigned int align_bits
;
457 unsigned HOST_WIDE_INT bitpos
;
458 if ((*trim_head
|| *trim_tail
)
459 && last_live
- first_live
>= 2
460 && ao_ref_alignment (ref
, &align_bits
, &bitpos
)
463 && align_bits
% BITS_PER_UNIT
== 0)
465 unsigned int align_units
= align_bits
/ BITS_PER_UNIT
;
466 if (align_units
> 16)
468 while ((first_live
| (align_units
- 1)) > (unsigned int)last_live
)
473 unsigned int pos
= first_live
& (align_units
- 1);
474 for (unsigned int i
= 1; i
<= align_units
; i
<<= 1)
476 unsigned int mask
= ~(i
- 1);
477 unsigned int bytes
= align_units
- (pos
& mask
);
478 if (wi::popcount (bytes
) <= 1)
488 unsigned int pos
= last_live
& (align_units
- 1);
489 for (unsigned int i
= 1; i
<= align_units
; i
<<= 1)
492 unsigned int bytes
= (pos
| mask
) + 1;
493 if ((last_live
| mask
) > (last_live
+ *trim_tail
))
495 if (wi::popcount (bytes
) <= 1)
497 unsigned int extra
= (last_live
| mask
) - last_live
;
505 if ((*trim_head
|| *trim_tail
)
506 && dump_file
&& (dump_flags
& TDF_DETAILS
))
508 fprintf (dump_file
, " Trimming statement (head = %d, tail = %d): ",
509 *trim_head
, *trim_tail
);
510 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
511 fprintf (dump_file
, "\n");
515 /* STMT initializes an object from COMPLEX_CST where one or more of the
516 bytes written may be dead stores. REF is a representation of the
517 memory written. LIVE is the bitmap of stores that are actually live.
519 Attempt to rewrite STMT so that only the real or imaginary part of
520 the object is actually stored. */
523 maybe_trim_complex_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
525 int trim_head
, trim_tail
;
526 compute_trims (ref
, live
, &trim_head
, &trim_tail
, stmt
);
528 /* The amount of data trimmed from the head or tail must be at
529 least half the size of the object to ensure we're trimming
530 the entire real or imaginary half. By writing things this
531 way we avoid more O(n) bitmap operations. */
532 if (known_ge (trim_tail
* 2 * BITS_PER_UNIT
, ref
->size
))
534 /* TREE_REALPART is live */
535 tree x
= TREE_REALPART (gimple_assign_rhs1 (stmt
));
536 tree y
= gimple_assign_lhs (stmt
);
537 y
= build1 (REALPART_EXPR
, TREE_TYPE (x
), y
);
538 gimple_assign_set_lhs (stmt
, y
);
539 gimple_assign_set_rhs1 (stmt
, x
);
541 else if (known_ge (trim_head
* 2 * BITS_PER_UNIT
, ref
->size
))
543 /* TREE_IMAGPART is live */
544 tree x
= TREE_IMAGPART (gimple_assign_rhs1 (stmt
));
545 tree y
= gimple_assign_lhs (stmt
);
546 y
= build1 (IMAGPART_EXPR
, TREE_TYPE (x
), y
);
547 gimple_assign_set_lhs (stmt
, y
);
548 gimple_assign_set_rhs1 (stmt
, x
);
551 /* Other cases indicate parts of both the real and imag subobjects
552 are live. We do not try to optimize those cases. */
555 /* STMT initializes an object using a CONSTRUCTOR where one or more of the
556 bytes written are dead stores. ORIG is the bitmap of bytes stored by
557 STMT. LIVE is the bitmap of stores that are actually live.
559 Attempt to rewrite STMT so that only the real or imaginary part of
560 the object is actually stored.
562 The most common case for getting here is a CONSTRUCTOR with no elements
563 being used to zero initialize an object. We do not try to handle other
564 cases as those would force us to fully cover the object with the
565 CONSTRUCTOR node except for the components that are dead. */
568 maybe_trim_constructor_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
570 tree ctor
= gimple_assign_rhs1 (stmt
);
572 /* This is the only case we currently handle. It actually seems to
573 catch most cases of actual interest. */
574 gcc_assert (CONSTRUCTOR_NELTS (ctor
) == 0);
578 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
580 /* Now we want to replace the constructor initializer
581 with memset (object + head_trim, 0, size - head_trim - tail_trim). */
582 if (head_trim
|| tail_trim
)
584 /* We want &lhs for the MEM_REF expression. */
585 tree lhs_addr
= build_fold_addr_expr (gimple_assign_lhs (stmt
));
587 if (! is_gimple_min_invariant (lhs_addr
))
590 /* The number of bytes for the new constructor. */
591 poly_int64 ref_bytes
= exact_div (ref
->size
, BITS_PER_UNIT
);
592 poly_int64 count
= ref_bytes
- head_trim
- tail_trim
;
594 /* And the new type for the CONSTRUCTOR. Essentially it's just
595 a char array large enough to cover the non-trimmed parts of
596 the original CONSTRUCTOR. Note we want explicit bounds here
597 so that we know how many bytes to clear when expanding the
599 tree type
= build_array_type_nelts (char_type_node
, count
);
601 /* Build a suitable alias type rather than using alias set zero
602 to avoid pessimizing. */
603 tree alias_type
= reference_alias_ptr_type (gimple_assign_lhs (stmt
));
605 /* Build a MEM_REF representing the whole accessed area, starting
606 at the first byte not trimmed. */
607 tree exp
= fold_build2 (MEM_REF
, type
, lhs_addr
,
608 build_int_cst (alias_type
, head_trim
));
610 /* Now update STMT with a new RHS and LHS. */
611 gimple_assign_set_lhs (stmt
, exp
);
612 gimple_assign_set_rhs1 (stmt
, build_constructor (type
, NULL
));
616 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes
617 copied/set by DECREMENT. */
619 decrement_count (gimple
*stmt
, int decrement
)
621 tree
*countp
= gimple_call_arg_ptr (stmt
, 2);
622 gcc_assert (TREE_CODE (*countp
) == INTEGER_CST
);
623 *countp
= wide_int_to_tree (TREE_TYPE (*countp
), (TREE_INT_CST_LOW (*countp
)
628 increment_start_addr (gimple
*stmt
, tree
*where
, int increment
)
630 if (tree lhs
= gimple_call_lhs (stmt
))
631 if (where
== gimple_call_arg_ptr (stmt
, 0))
633 gassign
*newop
= gimple_build_assign (lhs
, unshare_expr (*where
));
634 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
635 gsi_insert_after (&gsi
, newop
, GSI_SAME_STMT
);
636 gimple_call_set_lhs (stmt
, NULL_TREE
);
640 if (TREE_CODE (*where
) == SSA_NAME
)
642 tree tem
= make_ssa_name (TREE_TYPE (*where
));
644 = gimple_build_assign (tem
, POINTER_PLUS_EXPR
, *where
,
645 build_int_cst (sizetype
, increment
));
646 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
647 gsi_insert_before (&gsi
, newop
, GSI_SAME_STMT
);
653 *where
= build_fold_addr_expr (fold_build2 (MEM_REF
, char_type_node
,
655 build_int_cst (ptr_type_node
,
659 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
660 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce
661 the amount of data it actually writes.
663 Right now we only support trimming from the head or the tail of the
664 memory region. In theory we could split the mem* call, but it's
665 likely of marginal value. */
668 maybe_trim_memstar_call (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
670 int head_trim
, tail_trim
;
671 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
673 case BUILT_IN_STRNCPY
:
674 case BUILT_IN_STRNCPY_CHK
:
675 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
678 /* Head trimming of strncpy is only possible if we can
679 prove all bytes we would trim are non-zero (or we could
680 turn the strncpy into memset if there must be zero
681 among the head trimmed bytes). If we don't know anything
682 about those bytes, the presence or absence of '\0' bytes
683 in there will affect whether it acts for the non-trimmed
684 bytes as memset or memcpy/strncpy. */
685 c_strlen_data lendata
= { };
686 int orig_head_trim
= head_trim
;
687 tree srcstr
= gimple_call_arg (stmt
, 1);
688 if (!get_range_strlen (srcstr
, &lendata
, /*eltsize=*/1)
689 || !tree_fits_uhwi_p (lendata
.minlen
))
691 else if (tree_to_uhwi (lendata
.minlen
) < (unsigned) head_trim
)
693 head_trim
= tree_to_uhwi (lendata
.minlen
);
694 if ((orig_head_trim
& (UNITS_PER_WORD
- 1)) == 0)
695 head_trim
&= ~(UNITS_PER_WORD
- 1);
697 if (orig_head_trim
!= head_trim
699 && (dump_flags
& TDF_DETAILS
))
701 " Adjusting strncpy trimming to (head = %d,"
702 " tail = %d)\n", head_trim
, tail_trim
);
706 case BUILT_IN_MEMCPY
:
707 case BUILT_IN_MEMMOVE
:
708 case BUILT_IN_MEMCPY_CHK
:
709 case BUILT_IN_MEMMOVE_CHK
:
710 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
713 /* Tail trimming is easy, we can just reduce the count. */
715 decrement_count (stmt
, tail_trim
);
717 /* Head trimming requires adjusting all the arguments. */
720 /* For __*_chk need to adjust also the last argument. */
721 if (gimple_call_num_args (stmt
) == 4)
723 tree size
= gimple_call_arg (stmt
, 3);
724 if (!tree_fits_uhwi_p (size
))
726 if (!integer_all_onesp (size
))
728 unsigned HOST_WIDE_INT sz
= tree_to_uhwi (size
);
729 if (sz
< (unsigned) head_trim
)
731 tree arg
= wide_int_to_tree (TREE_TYPE (size
),
733 gimple_call_set_arg (stmt
, 3, arg
);
736 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
737 increment_start_addr (stmt
, dst
, head_trim
);
738 tree
*src
= gimple_call_arg_ptr (stmt
, 1);
739 increment_start_addr (stmt
, src
, head_trim
);
740 decrement_count (stmt
, head_trim
);
744 case BUILT_IN_MEMSET
:
745 case BUILT_IN_MEMSET_CHK
:
746 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
748 /* Tail trimming is easy, we can just reduce the count. */
750 decrement_count (stmt
, tail_trim
);
752 /* Head trimming requires adjusting all the arguments. */
755 /* For __*_chk need to adjust also the last argument. */
756 if (gimple_call_num_args (stmt
) == 4)
758 tree size
= gimple_call_arg (stmt
, 3);
759 if (!tree_fits_uhwi_p (size
))
761 if (!integer_all_onesp (size
))
763 unsigned HOST_WIDE_INT sz
= tree_to_uhwi (size
);
764 if (sz
< (unsigned) head_trim
)
766 tree arg
= wide_int_to_tree (TREE_TYPE (size
),
768 gimple_call_set_arg (stmt
, 3, arg
);
771 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
772 increment_start_addr (stmt
, dst
, head_trim
);
773 decrement_count (stmt
, head_trim
);
782 /* STMT is a memory write where one or more bytes written are dead
783 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the
784 bitmap of stores that are actually live.
786 Attempt to rewrite STMT so that it writes fewer memory locations. Right
787 now we only support trimming at the start or end of the memory region.
788 It's not clear how much there is to be gained by trimming from the middle
792 maybe_trim_partially_dead_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
794 if (is_gimple_assign (stmt
)
795 && TREE_CODE (gimple_assign_lhs (stmt
)) != TARGET_MEM_REF
)
797 switch (gimple_assign_rhs_code (stmt
))
800 maybe_trim_constructor_store (ref
, live
, stmt
);
803 maybe_trim_complex_store (ref
, live
, stmt
);
811 /* Return TRUE if USE_REF reads bytes from LIVE where live is
812 derived from REF, a write reference.
814 While this routine may modify USE_REF, it's passed by value, not
815 location. So callers do not see those modifications. */
818 live_bytes_read (ao_ref
*use_ref
, ao_ref
*ref
, sbitmap live
)
820 /* We have already verified that USE_REF and REF hit the same object.
821 Now verify that there's actually an overlap between USE_REF and REF. */
822 HOST_WIDE_INT start
, size
;
823 if (get_byte_range (use_ref
, ref
, false, &start
, &size
))
825 /* If USE_REF covers all of REF, then it will hit one or more
826 live bytes. This avoids useless iteration over the bitmap
828 if (start
== 0 && known_eq (size
* 8, ref
->size
))
831 /* Now check if any of the remaining bits in use_ref are set in LIVE. */
832 return bitmap_bit_in_range_p (live
, start
, (start
+ size
- 1));
837 /* Callback for dse_classify_store calling for_each_index. Verify that
838 indices are invariant in the loop with backedge PHI in basic-block DATA. */
841 check_name (tree
, tree
*idx
, void *data
)
843 basic_block phi_bb
= (basic_block
) data
;
844 if (TREE_CODE (*idx
) == SSA_NAME
845 && !SSA_NAME_IS_DEFAULT_DEF (*idx
)
846 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (SSA_NAME_DEF_STMT (*idx
)),
852 /* STMT stores the value 0 into one or more memory locations
853 (via memset, empty constructor, calloc call, etc).
855 See if there is a subsequent store of the value 0 to one
856 or more of the same memory location(s). If so, the subsequent
857 store is redundant and can be removed.
859 The subsequent stores could be via memset, empty constructors,
860 simple MEM stores, etc. */
863 dse_optimize_redundant_stores (gimple
*stmt
)
867 /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */
868 alias_set_type earlier_set
= 0;
869 alias_set_type earlier_base_set
= 0;
870 if (is_gimple_assign (stmt
))
873 ao_ref_init (&lhs_ref
, gimple_assign_lhs (stmt
));
874 earlier_set
= ao_ref_alias_set (&lhs_ref
);
875 earlier_base_set
= ao_ref_base_alias_set (&lhs_ref
);
878 /* We could do something fairly complex and look through PHIs
879 like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
882 Look at all the immediate uses of the VDEF (which are obviously
883 dominated by STMT). See if one or more stores 0 into the same
884 memory locations a STMT, if so remove the immediate use statements. */
885 tree defvar
= gimple_vdef (stmt
);
888 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
890 /* Limit stmt walking. */
891 if (++cnt
> param_dse_max_alias_queries_per_store
)
894 /* If USE_STMT stores 0 into one or more of the same locations
895 as STMT and STMT would kill USE_STMT, then we can just remove
898 if ((is_gimple_assign (use_stmt
)
899 && gimple_vdef (use_stmt
)
900 && (gimple_assign_single_p (use_stmt
)
901 && initializer_zerop (gimple_assign_rhs1 (use_stmt
))))
902 || (gimple_call_builtin_p (use_stmt
, BUILT_IN_NORMAL
)
903 && (fndecl
= gimple_call_fndecl (use_stmt
)) != NULL
904 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
905 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
906 && integer_zerop (gimple_call_arg (use_stmt
, 1))))
910 if (!initialize_ao_ref_for_dse (use_stmt
, &write
))
913 if (valid_ao_ref_for_dse (&write
)
914 && stmt_kills_ref_p (stmt
, &write
))
916 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
917 if (is_gimple_assign (use_stmt
))
920 ao_ref_init (&lhs_ref
, gimple_assign_lhs (use_stmt
));
921 if ((earlier_set
== ao_ref_alias_set (&lhs_ref
)
922 || alias_set_subset_of (ao_ref_alias_set (&lhs_ref
),
924 && (earlier_base_set
== ao_ref_base_alias_set (&lhs_ref
)
925 || alias_set_subset_of
926 (ao_ref_base_alias_set (&lhs_ref
),
928 delete_dead_or_redundant_assignment (&gsi
, "redundant",
932 else if (is_gimple_call (use_stmt
))
934 if ((earlier_set
== 0
935 || alias_set_subset_of (0, earlier_set
))
936 && (earlier_base_set
== 0
937 || alias_set_subset_of (0, earlier_base_set
)))
938 delete_dead_or_redundant_call (&gsi
, "redundant");
947 /* Return whether PHI contains ARG as an argument. */
950 contains_phi_arg (gphi
*phi
, tree arg
)
952 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
953 if (gimple_phi_arg_def (phi
, i
) == arg
)
958 /* Hash map of the memory use in a GIMPLE assignment to its
959 data reference. If NULL data-ref analysis isn't used. */
960 static hash_map
<gimple
*, data_reference_p
> *dse_stmt_to_dr_map
;
962 /* A helper of dse_optimize_stmt.
963 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
964 according to downstream uses and defs. Sets *BY_CLOBBER_P to true
965 if only clobber statements influenced the classification result.
966 Returns the classification. */
969 dse_classify_store (ao_ref
*ref
, gimple
*stmt
,
970 bool byte_tracking_enabled
, sbitmap live_bytes
,
971 bool *by_clobber_p
, tree stop_at_vuse
)
976 std::unique_ptr
<data_reference
, void(*)(data_reference_p
)>
977 dra (nullptr, free_data_ref
);
980 *by_clobber_p
= true;
982 /* Find the first dominated statement that clobbers (part of) the
983 memory stmt stores to with no intermediate statement that may use
984 part of the memory stmt stores. That is, find a store that may
985 prove stmt to be a dead store. */
994 if (gimple_code (temp
) == GIMPLE_PHI
)
996 defvar
= PHI_RESULT (temp
);
997 bitmap_set_bit (visited
, SSA_NAME_VERSION (defvar
));
1000 defvar
= gimple_vdef (temp
);
1002 auto_vec
<gimple
*, 10> defs
;
1003 gphi
*first_phi_def
= NULL
;
1004 gphi
*last_phi_def
= NULL
;
1006 auto_vec
<tree
, 10> worklist
;
1007 worklist
.quick_push (defvar
);
1011 defvar
= worklist
.pop ();
1012 /* If we're instructed to stop walking at region boundary, do so. */
1013 if (defvar
== stop_at_vuse
)
1014 return DSE_STORE_LIVE
;
1016 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
1018 /* Limit stmt walking. */
1019 if (++cnt
> param_dse_max_alias_queries_per_store
)
1025 /* In simple cases we can look through PHI nodes, but we
1026 have to be careful with loops and with memory references
1027 containing operands that are also operands of PHI nodes.
1028 See gcc.c-torture/execute/20051110-*.c. */
1029 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1031 /* Look through single-argument PHIs. */
1032 if (gimple_phi_num_args (use_stmt
) == 1)
1033 worklist
.safe_push (gimple_phi_result (use_stmt
));
1035 /* If we already visited this PHI ignore it for further
1037 else if (!bitmap_bit_p (visited
,
1039 (PHI_RESULT (use_stmt
))))
1041 /* If we visit this PHI by following a backedge then we
1042 have to make sure ref->ref only refers to SSA names
1043 that are invariant with respect to the loop
1044 represented by this PHI node. */
1045 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (stmt
),
1046 gimple_bb (use_stmt
))
1047 && !for_each_index (ref
->ref
? &ref
->ref
: &ref
->base
,
1048 check_name
, gimple_bb (use_stmt
)))
1049 return DSE_STORE_LIVE
;
1050 defs
.safe_push (use_stmt
);
1052 first_phi_def
= as_a
<gphi
*> (use_stmt
);
1053 last_phi_def
= as_a
<gphi
*> (use_stmt
);
1056 /* If the statement is a use the store is not dead. */
1057 else if (ref_maybe_used_by_stmt_p (use_stmt
, ref
))
1059 if (dse_stmt_to_dr_map
1061 && is_gimple_assign (use_stmt
))
1064 dra
.reset (create_data_ref (NULL
, NULL
, ref
->ref
, stmt
,
1067 data_reference_p
&drb
1068 = dse_stmt_to_dr_map
->get_or_insert (use_stmt
,
1071 drb
= create_data_ref (NULL
, NULL
,
1072 gimple_assign_rhs1 (use_stmt
),
1073 use_stmt
, false, false);
1074 if (!dr_may_alias_p (dra
.get (), drb
, NULL
))
1076 if (gimple_vdef (use_stmt
))
1077 defs
.safe_push (use_stmt
);
1082 /* Handle common cases where we can easily build an ao_ref
1083 structure for USE_STMT and in doing so we find that the
1084 references hit non-live bytes and thus can be ignored.
1086 TODO: We can also use modref summary to handle calls. */
1087 if (byte_tracking_enabled
1088 && is_gimple_assign (use_stmt
))
1091 ao_ref_init (&use_ref
, gimple_assign_rhs1 (use_stmt
));
1092 if (valid_ao_ref_for_dse (&use_ref
)
1093 && operand_equal_p (use_ref
.base
, ref
->base
,
1095 && !live_bytes_read (&use_ref
, ref
, live_bytes
))
1097 /* If this is a store, remember it as we possibly
1098 need to walk the defs uses. */
1099 if (gimple_vdef (use_stmt
))
1100 defs
.safe_push (use_stmt
);
1108 /* We have visited ourselves already so ignore STMT for the
1109 purpose of chaining. */
1110 else if (use_stmt
== stmt
)
1112 /* If this is a store, remember it as we possibly need to walk the
1114 else if (gimple_vdef (use_stmt
))
1115 defs
.safe_push (use_stmt
);
1118 while (!fail
&& !worklist
.is_empty ());
1122 /* STMT might be partially dead and we may be able to reduce
1123 how many memory locations it stores into. */
1124 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
1125 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
1126 return DSE_STORE_LIVE
;
1129 /* If we didn't find any definition this means the store is dead
1130 if it isn't a store to global reachable memory. In this case
1131 just pretend the stmt makes itself dead. Otherwise fail. */
1132 if (defs
.is_empty ())
1134 if (ref_may_alias_global_p (ref
, false))
1136 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (defvar
));
1137 /* Assume that BUILT_IN_UNREACHABLE and BUILT_IN_UNREACHABLE_TRAP
1138 do not need to keep (global) memory side-effects live.
1139 We do not have virtual operands on BUILT_IN_UNREACHABLE
1140 but we can do poor mans reachability when the last
1141 definition we want to elide is in the block that ends
1143 if (EDGE_COUNT (def_bb
->succs
) == 0)
1144 if (gcall
*last
= dyn_cast
<gcall
*> (*gsi_last_bb (def_bb
)))
1145 if (gimple_call_builtin_p (last
, BUILT_IN_UNREACHABLE
)
1146 || gimple_call_builtin_p (last
,
1147 BUILT_IN_UNREACHABLE_TRAP
))
1150 *by_clobber_p
= false;
1151 return DSE_STORE_DEAD
;
1153 return DSE_STORE_LIVE
;
1157 *by_clobber_p
= false;
1158 return DSE_STORE_DEAD
;
1161 /* Process defs and remove those we need not process further. */
1162 for (unsigned i
= 0; i
< defs
.length ();)
1164 gimple
*def
= defs
[i
];
1166 use_operand_p use_p
;
1167 tree vdef
= (gimple_code (def
) == GIMPLE_PHI
1168 ? gimple_phi_result (def
) : gimple_vdef (def
));
1170 /* If the path to check starts with a kill we do not need to
1172 ??? With byte tracking we need only kill the bytes currently
1174 if (stmt_kills_ref_p (def
, ref
))
1176 if (by_clobber_p
&& !gimple_clobber_p (def
))
1177 *by_clobber_p
= false;
1178 defs
.unordered_remove (i
);
1180 /* If the path ends here we do not need to process it further.
1181 This for example happens with calls to noreturn functions. */
1182 else if (has_zero_uses (vdef
))
1184 /* But if the store is to global memory it is definitely
1186 if (ref_may_alias_global_p (ref
, false))
1187 return DSE_STORE_LIVE
;
1188 defs
.unordered_remove (i
);
1190 /* In addition to kills we can remove defs whose only use
1191 is another def in defs. That can only ever be PHIs of which
1192 we track two for simplicity reasons, the first and last in
1193 {first,last}_phi_def (we fail for multiple PHIs anyways).
1194 We can also ignore defs that feed only into
1195 already visited PHIs. */
1196 else if (single_imm_use (vdef
, &use_p
, &use_stmt
)
1197 && (use_stmt
== first_phi_def
1198 || use_stmt
== last_phi_def
1199 || (gimple_code (use_stmt
) == GIMPLE_PHI
1200 && bitmap_bit_p (visited
,
1202 (PHI_RESULT (use_stmt
))))))
1204 defs
.unordered_remove (i
);
1205 if (def
== first_phi_def
)
1206 first_phi_def
= NULL
;
1207 else if (def
== last_phi_def
)
1208 last_phi_def
= NULL
;
1210 /* If def is a PHI and one of its arguments is another PHI node still
1211 in consideration we can defer processing it. */
1212 else if ((phi_def
= dyn_cast
<gphi
*> (def
))
1214 && phi_def
!= last_phi_def
1215 && contains_phi_arg (phi_def
,
1216 gimple_phi_result (last_phi_def
)))
1218 && phi_def
!= first_phi_def
1220 (phi_def
, gimple_phi_result (first_phi_def
)))))
1222 defs
.unordered_remove (i
);
1223 if (phi_def
== first_phi_def
)
1224 first_phi_def
= NULL
;
1225 else if (phi_def
== last_phi_def
)
1226 last_phi_def
= NULL
;
1232 /* If all defs kill the ref we are done. */
1233 if (defs
.is_empty ())
1234 return DSE_STORE_DEAD
;
1235 /* If more than one def survives fail. */
1236 if (defs
.length () > 1)
1238 /* STMT might be partially dead and we may be able to reduce
1239 how many memory locations it stores into. */
1240 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
1241 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
1242 return DSE_STORE_LIVE
;
1246 /* Track partial kills. */
1247 if (byte_tracking_enabled
)
1249 clear_bytes_written_by (live_bytes
, temp
, ref
);
1250 if (bitmap_empty_p (live_bytes
))
1252 if (by_clobber_p
&& !gimple_clobber_p (temp
))
1253 *by_clobber_p
= false;
1254 return DSE_STORE_DEAD
;
1258 /* Continue walking until there are no more live bytes. */
1263 /* Delete a dead call at GSI, which is mem* call of some kind. */
1265 delete_dead_or_redundant_call (gimple_stmt_iterator
*gsi
, const char *type
)
1267 gimple
*stmt
= gsi_stmt (*gsi
);
1268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1270 fprintf (dump_file
, " Deleted %s call: ", type
);
1271 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1272 fprintf (dump_file
, "\n");
1275 basic_block bb
= gimple_bb (stmt
);
1276 tree lhs
= gimple_call_lhs (stmt
);
1279 tree ptr
= gimple_call_arg (stmt
, 0);
1280 gimple
*new_stmt
= gimple_build_assign (lhs
, ptr
);
1281 unlink_stmt_vdef (stmt
);
1282 if (gsi_replace (gsi
, new_stmt
, true))
1283 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1287 /* Then we need to fix the operand of the consuming stmt. */
1288 unlink_stmt_vdef (stmt
);
1290 /* Remove the dead store. */
1291 if (gsi_remove (gsi
, true))
1292 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1293 release_defs (stmt
);
1297 /* Delete a dead store at GSI, which is a gimple assignment. */
1300 delete_dead_or_redundant_assignment (gimple_stmt_iterator
*gsi
,
1302 bitmap need_eh_cleanup
,
1303 bitmap need_ab_cleanup
)
1305 gimple
*stmt
= gsi_stmt (*gsi
);
1306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1308 fprintf (dump_file
, " Deleted %s store: ", type
);
1309 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1310 fprintf (dump_file
, "\n");
1313 /* Then we need to fix the operand of the consuming stmt. */
1314 unlink_stmt_vdef (stmt
);
1316 /* Remove the dead store. */
1317 basic_block bb
= gimple_bb (stmt
);
1318 if (need_ab_cleanup
&& stmt_can_make_abnormal_goto (stmt
))
1319 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
1320 if (gsi_remove (gsi
, true) && need_eh_cleanup
)
1321 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1323 /* And release any SSA_NAMEs set in this statement back to the
1324 SSA_NAME manager. */
1325 release_defs (stmt
);
1328 /* Try to prove, using modref summary, that all memory written to by a call is
1329 dead and remove it. Assume that if return value is written to memory
1330 it is already proved to be dead. */
1333 dse_optimize_call (gimple_stmt_iterator
*gsi
, sbitmap live_bytes
)
1335 gcall
*stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1340 tree callee
= gimple_call_fndecl (stmt
);
1345 /* Pure/const functions are optimized by normal DCE
1346 or handled as store above. */
1347 int flags
= gimple_call_flags (stmt
);
1348 if ((flags
& (ECF_PURE
|ECF_CONST
|ECF_NOVOPS
))
1349 && !(flags
& (ECF_LOOPING_CONST_OR_PURE
)))
1352 cgraph_node
*node
= cgraph_node::get (callee
);
1356 if (stmt_could_throw_p (cfun
, stmt
)
1357 && !cfun
->can_delete_dead_exceptions
)
1360 /* If return value is used the call is not dead. */
1361 tree lhs
= gimple_call_lhs (stmt
);
1362 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1364 imm_use_iterator ui
;
1366 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, lhs
)
1367 if (!is_gimple_debug (use_stmt
))
1371 /* Verify that there are no side-effects except for return value
1372 and memory writes tracked by modref. */
1373 modref_summary
*summary
= get_modref_function_summary (node
);
1374 if (!summary
|| !summary
->try_dse
)
1377 bool by_clobber_p
= false;
1379 /* Walk all memory writes and verify that they are dead. */
1380 for (auto base_node
: summary
->stores
->bases
)
1381 for (auto ref_node
: base_node
->refs
)
1382 for (auto access_node
: ref_node
->accesses
)
1384 tree arg
= access_node
.get_call_arg (stmt
);
1386 if (!arg
|| !POINTER_TYPE_P (TREE_TYPE (arg
)))
1389 if (integer_zerop (arg
)
1390 && !targetm
.addr_space
.zero_address_valid
1391 (TYPE_ADDR_SPACE (TREE_TYPE (arg
))))
1396 if (!access_node
.get_ao_ref (stmt
, &ref
))
1398 ref
.ref_alias_set
= ref_node
->ref
;
1399 ref
.base_alias_set
= base_node
->base
;
1401 bool byte_tracking_enabled
1402 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1403 enum dse_store_status store_status
;
1405 store_status
= dse_classify_store (&ref
, stmt
,
1406 byte_tracking_enabled
,
1407 live_bytes
, &by_clobber_p
);
1408 if (store_status
!= DSE_STORE_DEAD
)
1411 delete_dead_or_redundant_assignment (gsi
, "dead", need_eh_cleanup
,
1416 /* Attempt to eliminate dead stores in the statement referenced by BSI.
1418 A dead store is a store into a memory location which will later be
1419 overwritten by another store without any intervening loads. In this
1420 case the earlier store can be deleted.
1422 In our SSA + virtual operand world we use immediate uses of virtual
1423 operands to detect dead stores. If a store's virtual definition
1424 is used precisely once by a later store to the same location which
1425 post dominates the first store, then the first store is dead. */
1428 dse_optimize_stmt (function
*fun
, gimple_stmt_iterator
*gsi
, sbitmap live_bytes
)
1430 gimple
*stmt
= gsi_stmt (*gsi
);
1432 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
1433 if (gimple_has_volatile_ops (stmt
)
1434 && (!gimple_clobber_p (stmt
)
1435 || TREE_CODE (gimple_assign_lhs (stmt
)) != MEM_REF
))
1439 /* If this is not a store we can still remove dead call using
1440 modref summary. Note we specifically allow ref to be initialized
1441 to a conservative may-def since we are looking for followup stores
1442 to kill all of it. */
1443 if (!initialize_ao_ref_for_dse (stmt
, &ref
, true))
1445 dse_optimize_call (gsi
, live_bytes
);
1449 /* We know we have virtual definitions. We can handle assignments and
1450 some builtin calls. */
1451 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1453 tree fndecl
= gimple_call_fndecl (stmt
);
1454 switch (DECL_FUNCTION_CODE (fndecl
))
1456 case BUILT_IN_MEMCPY
:
1457 case BUILT_IN_MEMMOVE
:
1458 case BUILT_IN_STRNCPY
:
1459 case BUILT_IN_MEMSET
:
1460 case BUILT_IN_MEMCPY_CHK
:
1461 case BUILT_IN_MEMMOVE_CHK
:
1462 case BUILT_IN_STRNCPY_CHK
:
1463 case BUILT_IN_MEMSET_CHK
:
1465 /* Occasionally calls with an explicit length of zero
1466 show up in the IL. It's pointless to do analysis
1467 on them, they're trivially dead. */
1468 tree size
= gimple_call_arg (stmt
, 2);
1469 if (integer_zerop (size
))
1471 delete_dead_or_redundant_call (gsi
, "dead");
1475 /* If this is a memset call that initializes an object
1476 to zero, it may be redundant with an earlier memset
1477 or empty CONSTRUCTOR of a larger object. */
1478 if ((DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
1479 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
1480 && integer_zerop (gimple_call_arg (stmt
, 1)))
1481 dse_optimize_redundant_stores (stmt
);
1483 enum dse_store_status store_status
;
1484 bool byte_tracking_enabled
1485 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1486 store_status
= dse_classify_store (&ref
, stmt
,
1487 byte_tracking_enabled
,
1489 if (store_status
== DSE_STORE_LIVE
)
1492 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1494 maybe_trim_memstar_call (&ref
, live_bytes
, stmt
);
1498 if (store_status
== DSE_STORE_DEAD
)
1499 delete_dead_or_redundant_call (gsi
, "dead");
1503 case BUILT_IN_CALLOC
:
1504 /* We already know the arguments are integer constants. */
1505 dse_optimize_redundant_stores (stmt
);
1512 else if (is_gimple_call (stmt
)
1513 && gimple_call_internal_p (stmt
))
1515 switch (gimple_call_internal_fn (stmt
))
1518 case IFN_MASK_STORE
:
1519 case IFN_LEN_MASK_STORE
:
1521 enum dse_store_status store_status
;
1522 store_status
= dse_classify_store (&ref
, stmt
, false, live_bytes
);
1523 if (store_status
== DSE_STORE_DEAD
)
1524 delete_dead_or_redundant_call (gsi
, "dead");
1531 bool by_clobber_p
= false;
1533 /* Check if this statement stores zero to a memory location,
1534 and if there is a subsequent store of zero to the same
1535 memory location. If so, remove the subsequent store. */
1536 if (gimple_assign_single_p (stmt
)
1537 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1538 dse_optimize_redundant_stores (stmt
);
1540 /* Self-assignments are zombies. */
1541 if (is_gimple_assign (stmt
)
1542 && operand_equal_p (gimple_assign_rhs1 (stmt
),
1543 gimple_assign_lhs (stmt
), 0))
1547 bool byte_tracking_enabled
1548 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1549 enum dse_store_status store_status
;
1550 store_status
= dse_classify_store (&ref
, stmt
,
1551 byte_tracking_enabled
,
1552 live_bytes
, &by_clobber_p
);
1553 if (store_status
== DSE_STORE_LIVE
)
1556 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1558 maybe_trim_partially_dead_store (&ref
, live_bytes
, stmt
);
1563 /* Now we know that use_stmt kills the LHS of stmt. */
1565 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
1566 another clobber stmt. */
1567 if (gimple_clobber_p (stmt
)
1571 if (is_gimple_call (stmt
)
1572 && (gimple_has_side_effects (stmt
)
1573 || (stmt_could_throw_p (fun
, stmt
)
1574 && !fun
->can_delete_dead_exceptions
)))
1576 /* See if we can remove complete call. */
1577 if (dse_optimize_call (gsi
, live_bytes
))
1579 /* Make sure we do not remove a return slot we cannot reconstruct
1581 if (gimple_call_return_slot_opt_p (as_a
<gcall
*>(stmt
))
1582 && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt
)))
1584 (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt
))))))
1586 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1588 fprintf (dump_file
, " Deleted dead store in call LHS: ");
1589 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1590 fprintf (dump_file
, "\n");
1592 gimple_call_set_lhs (stmt
, NULL_TREE
);
1595 else if (!stmt_could_throw_p (fun
, stmt
)
1596 || fun
->can_delete_dead_exceptions
)
1597 delete_dead_or_redundant_assignment (gsi
, "dead", need_eh_cleanup
,
1603 const pass_data pass_data_dse
=
1605 GIMPLE_PASS
, /* type */
1607 OPTGROUP_NONE
, /* optinfo_flags */
1608 TV_TREE_DSE
, /* tv_id */
1609 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1610 0, /* properties_provided */
1611 0, /* properties_destroyed */
1612 0, /* todo_flags_start */
1613 0, /* todo_flags_finish */
1616 class pass_dse
: public gimple_opt_pass
1619 pass_dse (gcc::context
*ctxt
)
1620 : gimple_opt_pass (pass_data_dse
, ctxt
), use_dr_analysis_p (false)
1623 /* opt_pass methods: */
1624 opt_pass
* clone () final override
{ return new pass_dse (m_ctxt
); }
1625 void set_pass_param (unsigned n
, bool param
) final override
1627 gcc_assert (n
== 0);
1628 use_dr_analysis_p
= param
;
1630 bool gate (function
*) final override
{ return flag_tree_dse
!= 0; }
1631 unsigned int execute (function
*) final override
;
1634 bool use_dr_analysis_p
;
1635 }; // class pass_dse
1638 pass_dse::execute (function
*fun
)
1641 bool released_def
= false;
1643 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
1644 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
1645 auto_sbitmap
live_bytes (param_dse_max_object_size
);
1646 if (flag_expensive_optimizations
&& use_dr_analysis_p
)
1647 dse_stmt_to_dr_map
= new hash_map
<gimple
*, data_reference_p
>;
1649 renumber_gimple_stmt_uids (fun
);
1651 calculate_dominance_info (CDI_DOMINATORS
);
1653 /* Dead store elimination is fundamentally a reverse program order walk. */
1654 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fun
) - NUM_FIXED_BLOCKS
);
1655 int n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
1656 for (int i
= n
; i
!= 0; --i
)
1658 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, rpo
[i
-1]);
1659 gimple_stmt_iterator gsi
;
1661 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
1663 gimple
*stmt
= gsi_stmt (gsi
);
1665 if (gimple_vdef (stmt
))
1666 dse_optimize_stmt (fun
, &gsi
, live_bytes
);
1667 else if (def_operand_p
1668 def_p
= single_ssa_def_operand (stmt
, SSA_OP_DEF
))
1670 /* When we remove dead stores make sure to also delete trivially
1672 if (has_zero_uses (DEF_FROM_PTR (def_p
))
1673 && !gimple_has_side_effects (stmt
)
1674 && !is_ctrl_altering_stmt (stmt
)
1675 && (!stmt_could_throw_p (fun
, stmt
)
1676 || fun
->can_delete_dead_exceptions
))
1678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1680 fprintf (dump_file
, " Deleted trivially dead stmt: ");
1681 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1682 fprintf (dump_file
, "\n");
1684 if (gsi_remove (&gsi
, true) && need_eh_cleanup
)
1685 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1686 release_defs (stmt
);
1687 released_def
= true;
1690 if (gsi_end_p (gsi
))
1691 gsi
= gsi_last_bb (bb
);
1695 bool removed_phi
= false;
1696 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);)
1698 gphi
*phi
= si
.phi ();
1699 if (has_zero_uses (gimple_phi_result (phi
)))
1701 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1703 fprintf (dump_file
, " Deleted trivially dead PHI: ");
1704 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
1705 fprintf (dump_file
, "\n");
1707 remove_phi_node (&si
, true);
1709 released_def
= true;
1714 if (removed_phi
&& gimple_seq_empty_p (phi_nodes (bb
)))
1715 todo
|= TODO_cleanup_cfg
;
1719 /* Removal of stores may make some EH edges dead. Purge such edges from
1720 the CFG as needed. */
1721 if (!bitmap_empty_p (need_eh_cleanup
))
1723 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
1724 todo
|= TODO_cleanup_cfg
;
1726 if (!bitmap_empty_p (need_ab_cleanup
))
1728 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
1729 todo
|= TODO_cleanup_cfg
;
1732 BITMAP_FREE (need_eh_cleanup
);
1733 BITMAP_FREE (need_ab_cleanup
);
1736 free_numbers_of_iterations_estimates (fun
);
1738 if (flag_expensive_optimizations
&& use_dr_analysis_p
)
1740 for (auto i
= dse_stmt_to_dr_map
->begin ();
1741 i
!= dse_stmt_to_dr_map
->end (); ++i
)
1742 free_data_ref ((*i
).second
);
1743 delete dse_stmt_to_dr_map
;
1744 dse_stmt_to_dr_map
= NULL
;
1753 make_pass_dse (gcc::context
*ctxt
)
1755 return new pass_dse (ctxt
);