1 /* Dead and redundant store elimination
2 Copyright (C) 2004-2022 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"
34 #include "tree-cfgcleanup.h"
36 #include "tree-ssa-loop.h"
37 #include "tree-ssa-dse.h"
39 #include "gimple-fold.h"
44 #include "ipa-modref-tree.h"
45 #include "ipa-modref.h"
47 /* This file implements dead store elimination.
49 A dead store is a store into a memory location which will later be
50 overwritten by another store without any intervening loads. In this
51 case the earlier store can be deleted or trimmed if the store
54 A redundant store is a store into a memory location which stores
55 the exact same value as a prior store to the same memory location.
56 While this can often be handled by dead store elimination, removing
57 the redundant store is often better than removing or trimming the
60 In our SSA + virtual operand world we use immediate uses of virtual
61 operands to detect these cases. If a store's virtual definition
62 is used precisely once by a later store to the same location which
63 post dominates the first store, then the first store is dead. If
64 the data stored is the same, then the second store is redundant.
66 The single use of the store's virtual definition ensures that
67 there are no intervening aliased loads and the requirement that
68 the second load post dominate the first ensures that if the earlier
69 store executes, then the later stores will execute before the function
72 It may help to think of this as first moving the earlier store to
73 the point immediately before the later store. Again, the single
74 use of the virtual definition and the post-dominance relationship
75 ensure that such movement would be safe. Clearly if there are
76 back to back stores, then the second is makes the first dead. If
77 the second store stores the same value, then the second store is
80 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
81 may also help in understanding this code since it discusses the
82 relationship between dead store and redundant load elimination. In
83 fact, they are the same transformation applied to different views of
86 static void delete_dead_or_redundant_call (gimple_stmt_iterator
*, const char *);
88 /* Bitmap of blocks that have had EH statements cleaned. We should
89 remove their dead edges eventually. */
90 static bitmap need_eh_cleanup
;
91 static bitmap need_ab_cleanup
;
93 /* STMT is a statement that may write into memory. Analyze it and
94 initialize WRITE to describe how STMT affects memory.
96 Return TRUE if the statement was analyzed, FALSE otherwise.
98 It is always safe to return FALSE. But typically better optimziation
99 can be achieved by analyzing more statements. */
102 initialize_ao_ref_for_dse (gimple
*stmt
, ao_ref
*write
)
104 /* It's advantageous to handle certain mem* functions. */
105 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
107 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
109 case BUILT_IN_MEMCPY
:
110 case BUILT_IN_MEMMOVE
:
111 case BUILT_IN_MEMSET
:
112 case BUILT_IN_MEMCPY_CHK
:
113 case BUILT_IN_MEMMOVE_CHK
:
114 case BUILT_IN_MEMSET_CHK
:
115 case BUILT_IN_STRNCPY
:
116 case BUILT_IN_STRNCPY_CHK
:
118 tree size
= gimple_call_arg (stmt
, 2);
119 tree ptr
= gimple_call_arg (stmt
, 0);
120 ao_ref_init_from_ptr_and_size (write
, ptr
, size
);
124 /* A calloc call can never be dead, but it can make
125 subsequent stores redundant if they store 0 into
126 the same memory locations. */
127 case BUILT_IN_CALLOC
:
129 tree nelem
= gimple_call_arg (stmt
, 0);
130 tree selem
= gimple_call_arg (stmt
, 1);
132 if (TREE_CODE (nelem
) == INTEGER_CST
133 && TREE_CODE (selem
) == INTEGER_CST
134 && (lhs
= gimple_call_lhs (stmt
)) != NULL_TREE
)
136 tree size
= fold_build2 (MULT_EXPR
, TREE_TYPE (nelem
),
138 ao_ref_init_from_ptr_and_size (write
, lhs
, size
);
147 else if (tree lhs
= gimple_get_lhs (stmt
))
149 if (TREE_CODE (lhs
) != SSA_NAME
)
151 ao_ref_init (write
, lhs
);
158 /* Given REF from the alias oracle, return TRUE if it is a valid
159 kill memory reference for dead store elimination, false otherwise.
161 In particular, the reference must have a known base, known maximum
162 size, start at a byte offset and have a size that is one or more
166 valid_ao_ref_kill_for_dse (ao_ref
*ref
)
168 return (ao_ref_base (ref
)
169 && known_size_p (ref
->max_size
)
170 && maybe_ne (ref
->size
, 0)
171 && known_eq (ref
->max_size
, ref
->size
)
172 && known_ge (ref
->offset
, 0));
175 /* Given REF from the alias oracle, return TRUE if it is a valid
176 load or store memory reference for dead store elimination, false otherwise.
178 Unlike for valid_ao_ref_kill_for_dse we can accept writes where max_size
179 is not same as size since we can handle conservatively the larger range. */
182 valid_ao_ref_for_dse (ao_ref
*ref
)
184 return (ao_ref_base (ref
)
185 && known_size_p (ref
->max_size
)
186 && known_ge (ref
->offset
, 0));
189 /* Initialize OFFSET and SIZE to a range known to contain REF
190 where the boundaries are divisible by BITS_PER_UNIT (bit still in bits).
191 Return false if this is impossible. */
194 get_byte_aligned_range_containing_ref (ao_ref
*ref
, poly_int64
*offset
,
197 if (!known_size_p (ref
->max_size
))
199 *offset
= aligned_lower_bound (ref
->offset
, BITS_PER_UNIT
);
200 poly_int64 end
= aligned_upper_bound (ref
->offset
+ ref
->max_size
,
202 return (end
- *offset
).is_constant (size
);
205 /* Initialize OFFSET and SIZE to a range known to be contained REF
206 where the boundaries are divisible by BITS_PER_UNIT (but still in bits).
207 Return false if this is impossible. */
210 get_byte_aligned_range_contained_in_ref (ao_ref
*ref
, poly_int64
*offset
,
213 if (!known_size_p (ref
->size
)
214 || !known_eq (ref
->size
, ref
->max_size
))
216 *offset
= aligned_upper_bound (ref
->offset
, BITS_PER_UNIT
);
217 poly_int64 end
= aligned_lower_bound (ref
->offset
+ ref
->max_size
,
219 /* For bit accesses we can get -1 here, but also 0 sized kill is not
221 if (!known_gt (end
, *offset
))
223 return (end
- *offset
).is_constant (size
);
226 /* Compute byte range (returned iN REF_OFFSET and RET_SIZE) for access COPY
227 inside REF. If KILL is true, then COPY represent a kill and the byte range
228 needs to be fully contained in bit range given by COPY. If KILL is false
229 then the byte range returned must contain the range of COPY. */
232 get_byte_range (ao_ref
*copy
, ao_ref
*ref
, bool kill
,
233 HOST_WIDE_INT
*ret_offset
, HOST_WIDE_INT
*ret_size
)
235 HOST_WIDE_INT copy_size
, ref_size
;
236 poly_int64 copy_offset
, ref_offset
;
239 /* First translate from bits to bytes, rounding to bigger or smaller ranges
240 as needed. Kills needs to be always rounded to smaller ranges while
241 uses and stores to larger ranges. */
244 if (!get_byte_aligned_range_contained_in_ref (copy
, ©_offset
,
250 if (!get_byte_aligned_range_containing_ref (copy
, ©_offset
,
255 if (!get_byte_aligned_range_containing_ref (ref
, &ref_offset
, &ref_size
)
256 || !ordered_p (copy_offset
, ref_offset
))
259 /* Switch sizes from bits to bytes so we do not need to care about
260 overflows. Offset calculation needs to stay in bits until we compute
261 the difference and can switch to HOST_WIDE_INT. */
262 copy_size
/= BITS_PER_UNIT
;
263 ref_size
/= BITS_PER_UNIT
;
265 /* If COPY starts before REF, then reset the beginning of
266 COPY to match REF and decrease the size of COPY by the
267 number of bytes removed from COPY. */
268 if (maybe_lt (copy_offset
, ref_offset
))
270 if (!(ref_offset
- copy_offset
).is_constant (&diff
)
271 || copy_size
< diff
/ BITS_PER_UNIT
)
273 copy_size
-= diff
/ BITS_PER_UNIT
;
274 copy_offset
= ref_offset
;
277 if (!(copy_offset
- ref_offset
).is_constant (&diff
)
278 || ref_size
<= diff
/ BITS_PER_UNIT
)
281 /* If COPY extends beyond REF, chop off its size appropriately. */
282 HOST_WIDE_INT limit
= ref_size
- diff
/ BITS_PER_UNIT
;
284 if (copy_size
> limit
)
286 *ret_size
= copy_size
;
287 if (!(copy_offset
- ref_offset
).is_constant (ret_offset
))
289 *ret_offset
/= BITS_PER_UNIT
;
293 /* Update LIVE_BYTES tracking REF for write to WRITE:
294 Verify we have the same base memory address, the write
295 has a known size and overlaps with REF. */
297 clear_live_bytes_for_ref (sbitmap live_bytes
, ao_ref
*ref
, ao_ref
*write
)
299 HOST_WIDE_INT start
, size
;
301 if (valid_ao_ref_kill_for_dse (write
)
302 && operand_equal_p (write
->base
, ref
->base
, OEP_ADDRESS_OF
)
303 && get_byte_range (write
, ref
, true, &start
, &size
))
304 bitmap_clear_range (live_bytes
, start
, size
);
307 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base
308 address written by STMT must match the one found in REF, which must
309 have its base address previously initialized.
311 This routine must be conservative. If we don't know the offset or
312 actual size written, assume nothing was written. */
315 clear_bytes_written_by (sbitmap live_bytes
, gimple
*stmt
, ao_ref
*ref
)
319 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
322 modref_summary
*summary
= get_modref_function_summary (call
, &interposed
);
324 if (summary
&& !interposed
)
325 for (auto kill
: summary
->kills
)
326 if (kill
.get_ao_ref (as_a
<gcall
*> (stmt
), &write
))
327 clear_live_bytes_for_ref (live_bytes
, ref
, &write
);
329 if (!initialize_ao_ref_for_dse (stmt
, &write
))
332 clear_live_bytes_for_ref (live_bytes
, ref
, &write
);
335 /* REF is a memory write. Extract relevant information from it and
336 initialize the LIVE_BYTES bitmap. If successful, return TRUE.
337 Otherwise return FALSE. */
340 setup_live_bytes_from_ref (ao_ref
*ref
, sbitmap live_bytes
)
342 HOST_WIDE_INT const_size
;
343 if (valid_ao_ref_for_dse (ref
)
344 && ((aligned_upper_bound (ref
->offset
+ ref
->max_size
, BITS_PER_UNIT
)
345 - aligned_lower_bound (ref
->offset
,
346 BITS_PER_UNIT
)).is_constant (&const_size
))
347 && (const_size
/ BITS_PER_UNIT
<= param_dse_max_object_size
)
350 bitmap_clear (live_bytes
);
351 bitmap_set_range (live_bytes
, 0, const_size
/ BITS_PER_UNIT
);
357 /* Compute the number of elements that we can trim from the head and
358 tail of ORIG resulting in a bitmap that is a superset of LIVE.
360 Store the number of elements trimmed from the head and tail in
361 TRIM_HEAD and TRIM_TAIL.
363 STMT is the statement being trimmed and is used for debugging dump
367 compute_trims (ao_ref
*ref
, sbitmap live
, int *trim_head
, int *trim_tail
,
370 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap
371 extends through ref->size. So we know that in the original bitmap
372 bits 0..ref->size were true. We don't actually need the bitmap, just
373 the REF to compute the trims. */
375 /* Now identify how much, if any of the tail we can chop off. */
376 HOST_WIDE_INT const_size
;
377 int last_live
= bitmap_last_set_bit (live
);
378 if (ref
->size
.is_constant (&const_size
))
380 int last_orig
= (const_size
/ BITS_PER_UNIT
) - 1;
381 /* We can leave inconvenient amounts on the tail as
382 residual handling in mem* and str* functions is usually
383 reasonably efficient. */
384 *trim_tail
= last_orig
- last_live
;
386 /* But don't trim away out of bounds accesses, as this defeats
389 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA
390 where TYPE_SIZE_UNIT is not a constant. */
392 && TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))
393 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
))) == INTEGER_CST
394 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref
->base
)),
401 /* Identify how much, if any of the head we can chop off. */
403 int first_live
= bitmap_first_set_bit (live
);
404 *trim_head
= first_live
- first_orig
;
406 /* If more than a word remains, then make sure to keep the
407 starting point at least word aligned. */
408 if (last_live
- first_live
> UNITS_PER_WORD
)
409 *trim_head
&= ~(UNITS_PER_WORD
- 1);
411 if ((*trim_head
|| *trim_tail
)
412 && dump_file
&& (dump_flags
& TDF_DETAILS
))
414 fprintf (dump_file
, " Trimming statement (head = %d, tail = %d): ",
415 *trim_head
, *trim_tail
);
416 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
417 fprintf (dump_file
, "\n");
421 /* STMT initializes an object from COMPLEX_CST where one or more of the
422 bytes written may be dead stores. REF is a representation of the
423 memory written. LIVE is the bitmap of stores that are actually live.
425 Attempt to rewrite STMT so that only the real or imaginary part of
426 the object is actually stored. */
429 maybe_trim_complex_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
431 int trim_head
, trim_tail
;
432 compute_trims (ref
, live
, &trim_head
, &trim_tail
, stmt
);
434 /* The amount of data trimmed from the head or tail must be at
435 least half the size of the object to ensure we're trimming
436 the entire real or imaginary half. By writing things this
437 way we avoid more O(n) bitmap operations. */
438 if (known_ge (trim_tail
* 2 * BITS_PER_UNIT
, ref
->size
))
440 /* TREE_REALPART is live */
441 tree x
= TREE_REALPART (gimple_assign_rhs1 (stmt
));
442 tree y
= gimple_assign_lhs (stmt
);
443 y
= build1 (REALPART_EXPR
, TREE_TYPE (x
), y
);
444 gimple_assign_set_lhs (stmt
, y
);
445 gimple_assign_set_rhs1 (stmt
, x
);
447 else if (known_ge (trim_head
* 2 * BITS_PER_UNIT
, ref
->size
))
449 /* TREE_IMAGPART is live */
450 tree x
= TREE_IMAGPART (gimple_assign_rhs1 (stmt
));
451 tree y
= gimple_assign_lhs (stmt
);
452 y
= build1 (IMAGPART_EXPR
, TREE_TYPE (x
), y
);
453 gimple_assign_set_lhs (stmt
, y
);
454 gimple_assign_set_rhs1 (stmt
, x
);
457 /* Other cases indicate parts of both the real and imag subobjects
458 are live. We do not try to optimize those cases. */
461 /* STMT initializes an object using a CONSTRUCTOR where one or more of the
462 bytes written are dead stores. ORIG is the bitmap of bytes stored by
463 STMT. LIVE is the bitmap of stores that are actually live.
465 Attempt to rewrite STMT so that only the real or imaginary part of
466 the object is actually stored.
468 The most common case for getting here is a CONSTRUCTOR with no elements
469 being used to zero initialize an object. We do not try to handle other
470 cases as those would force us to fully cover the object with the
471 CONSTRUCTOR node except for the components that are dead. */
474 maybe_trim_constructor_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
476 tree ctor
= gimple_assign_rhs1 (stmt
);
478 /* This is the only case we currently handle. It actually seems to
479 catch most cases of actual interest. */
480 gcc_assert (CONSTRUCTOR_NELTS (ctor
) == 0);
484 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
486 /* Now we want to replace the constructor initializer
487 with memset (object + head_trim, 0, size - head_trim - tail_trim). */
488 if (head_trim
|| tail_trim
)
490 /* We want &lhs for the MEM_REF expression. */
491 tree lhs_addr
= build_fold_addr_expr (gimple_assign_lhs (stmt
));
493 if (! is_gimple_min_invariant (lhs_addr
))
496 /* The number of bytes for the new constructor. */
497 poly_int64 ref_bytes
= exact_div (ref
->size
, BITS_PER_UNIT
);
498 poly_int64 count
= ref_bytes
- head_trim
- tail_trim
;
500 /* And the new type for the CONSTRUCTOR. Essentially it's just
501 a char array large enough to cover the non-trimmed parts of
502 the original CONSTRUCTOR. Note we want explicit bounds here
503 so that we know how many bytes to clear when expanding the
505 tree type
= build_array_type_nelts (char_type_node
, count
);
507 /* Build a suitable alias type rather than using alias set zero
508 to avoid pessimizing. */
509 tree alias_type
= reference_alias_ptr_type (gimple_assign_lhs (stmt
));
511 /* Build a MEM_REF representing the whole accessed area, starting
512 at the first byte not trimmed. */
513 tree exp
= fold_build2 (MEM_REF
, type
, lhs_addr
,
514 build_int_cst (alias_type
, head_trim
));
516 /* Now update STMT with a new RHS and LHS. */
517 gimple_assign_set_lhs (stmt
, exp
);
518 gimple_assign_set_rhs1 (stmt
, build_constructor (type
, NULL
));
522 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes
523 copied/set by DECREMENT. */
525 decrement_count (gimple
*stmt
, int decrement
)
527 tree
*countp
= gimple_call_arg_ptr (stmt
, 2);
528 gcc_assert (TREE_CODE (*countp
) == INTEGER_CST
);
529 *countp
= wide_int_to_tree (TREE_TYPE (*countp
), (TREE_INT_CST_LOW (*countp
)
534 increment_start_addr (gimple
*stmt
, tree
*where
, int increment
)
536 if (tree lhs
= gimple_call_lhs (stmt
))
537 if (where
== gimple_call_arg_ptr (stmt
, 0))
539 gassign
*newop
= gimple_build_assign (lhs
, unshare_expr (*where
));
540 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
541 gsi_insert_after (&gsi
, newop
, GSI_SAME_STMT
);
542 gimple_call_set_lhs (stmt
, NULL_TREE
);
546 if (TREE_CODE (*where
) == SSA_NAME
)
548 tree tem
= make_ssa_name (TREE_TYPE (*where
));
550 = gimple_build_assign (tem
, POINTER_PLUS_EXPR
, *where
,
551 build_int_cst (sizetype
, increment
));
552 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
553 gsi_insert_before (&gsi
, newop
, GSI_SAME_STMT
);
559 *where
= build_fold_addr_expr (fold_build2 (MEM_REF
, char_type_node
,
561 build_int_cst (ptr_type_node
,
565 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
566 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce
567 the amount of data it actually writes.
569 Right now we only support trimming from the head or the tail of the
570 memory region. In theory we could split the mem* call, but it's
571 likely of marginal value. */
574 maybe_trim_memstar_call (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
576 int head_trim
, tail_trim
;
577 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
579 case BUILT_IN_STRNCPY
:
580 case BUILT_IN_STRNCPY_CHK
:
581 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
584 /* Head trimming of strncpy is only possible if we can
585 prove all bytes we would trim are non-zero (or we could
586 turn the strncpy into memset if there must be zero
587 among the head trimmed bytes). If we don't know anything
588 about those bytes, the presence or absence of '\0' bytes
589 in there will affect whether it acts for the non-trimmed
590 bytes as memset or memcpy/strncpy. */
591 c_strlen_data lendata
= { };
592 int orig_head_trim
= head_trim
;
593 tree srcstr
= gimple_call_arg (stmt
, 1);
594 if (!get_range_strlen (srcstr
, &lendata
, /*eltsize=*/1)
595 || !tree_fits_uhwi_p (lendata
.minlen
))
597 else if (tree_to_uhwi (lendata
.minlen
) < (unsigned) head_trim
)
599 head_trim
= tree_to_uhwi (lendata
.minlen
);
600 if ((orig_head_trim
& (UNITS_PER_WORD
- 1)) == 0)
601 head_trim
&= ~(UNITS_PER_WORD
- 1);
603 if (orig_head_trim
!= head_trim
605 && (dump_flags
& TDF_DETAILS
))
607 " Adjusting strncpy trimming to (head = %d,"
608 " tail = %d)\n", head_trim
, tail_trim
);
612 case BUILT_IN_MEMCPY
:
613 case BUILT_IN_MEMMOVE
:
614 case BUILT_IN_MEMCPY_CHK
:
615 case BUILT_IN_MEMMOVE_CHK
:
616 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
619 /* Tail trimming is easy, we can just reduce the count. */
621 decrement_count (stmt
, tail_trim
);
623 /* Head trimming requires adjusting all the arguments. */
626 /* For __*_chk need to adjust also the last argument. */
627 if (gimple_call_num_args (stmt
) == 4)
629 tree size
= gimple_call_arg (stmt
, 3);
630 if (!tree_fits_uhwi_p (size
))
632 if (!integer_all_onesp (size
))
634 unsigned HOST_WIDE_INT sz
= tree_to_uhwi (size
);
635 if (sz
< (unsigned) head_trim
)
637 tree arg
= wide_int_to_tree (TREE_TYPE (size
),
639 gimple_call_set_arg (stmt
, 3, arg
);
642 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
643 increment_start_addr (stmt
, dst
, head_trim
);
644 tree
*src
= gimple_call_arg_ptr (stmt
, 1);
645 increment_start_addr (stmt
, src
, head_trim
);
646 decrement_count (stmt
, head_trim
);
650 case BUILT_IN_MEMSET
:
651 case BUILT_IN_MEMSET_CHK
:
652 compute_trims (ref
, live
, &head_trim
, &tail_trim
, stmt
);
654 /* Tail trimming is easy, we can just reduce the count. */
656 decrement_count (stmt
, tail_trim
);
658 /* Head trimming requires adjusting all the arguments. */
661 /* For __*_chk need to adjust also the last argument. */
662 if (gimple_call_num_args (stmt
) == 4)
664 tree size
= gimple_call_arg (stmt
, 3);
665 if (!tree_fits_uhwi_p (size
))
667 if (!integer_all_onesp (size
))
669 unsigned HOST_WIDE_INT sz
= tree_to_uhwi (size
);
670 if (sz
< (unsigned) head_trim
)
672 tree arg
= wide_int_to_tree (TREE_TYPE (size
),
674 gimple_call_set_arg (stmt
, 3, arg
);
677 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
678 increment_start_addr (stmt
, dst
, head_trim
);
679 decrement_count (stmt
, head_trim
);
688 /* STMT is a memory write where one or more bytes written are dead
689 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the
690 bitmap of stores that are actually live.
692 Attempt to rewrite STMT so that it writes fewer memory locations. Right
693 now we only support trimming at the start or end of the memory region.
694 It's not clear how much there is to be gained by trimming from the middle
698 maybe_trim_partially_dead_store (ao_ref
*ref
, sbitmap live
, gimple
*stmt
)
700 if (is_gimple_assign (stmt
)
701 && TREE_CODE (gimple_assign_lhs (stmt
)) != TARGET_MEM_REF
)
703 switch (gimple_assign_rhs_code (stmt
))
706 maybe_trim_constructor_store (ref
, live
, stmt
);
709 maybe_trim_complex_store (ref
, live
, stmt
);
717 /* Return TRUE if USE_REF reads bytes from LIVE where live is
718 derived from REF, a write reference.
720 While this routine may modify USE_REF, it's passed by value, not
721 location. So callers do not see those modifications. */
724 live_bytes_read (ao_ref
*use_ref
, ao_ref
*ref
, sbitmap live
)
726 /* We have already verified that USE_REF and REF hit the same object.
727 Now verify that there's actually an overlap between USE_REF and REF. */
728 HOST_WIDE_INT start
, size
;
729 if (get_byte_range (use_ref
, ref
, false, &start
, &size
))
731 /* If USE_REF covers all of REF, then it will hit one or more
732 live bytes. This avoids useless iteration over the bitmap
734 if (start
== 0 && known_eq (size
* 8, ref
->size
))
737 /* Now check if any of the remaining bits in use_ref are set in LIVE. */
738 return bitmap_bit_in_range_p (live
, start
, (start
+ size
- 1));
743 /* Callback for dse_classify_store calling for_each_index. Verify that
744 indices are invariant in the loop with backedge PHI in basic-block DATA. */
747 check_name (tree
, tree
*idx
, void *data
)
749 basic_block phi_bb
= (basic_block
) data
;
750 if (TREE_CODE (*idx
) == SSA_NAME
751 && !SSA_NAME_IS_DEFAULT_DEF (*idx
)
752 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (SSA_NAME_DEF_STMT (*idx
)),
758 /* STMT stores the value 0 into one or more memory locations
759 (via memset, empty constructor, calloc call, etc).
761 See if there is a subsequent store of the value 0 to one
762 or more of the same memory location(s). If so, the subsequent
763 store is redundant and can be removed.
765 The subsequent stores could be via memset, empty constructors,
766 simple MEM stores, etc. */
769 dse_optimize_redundant_stores (gimple
*stmt
)
773 /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */
774 alias_set_type earlier_set
= 0;
775 alias_set_type earlier_base_set
= 0;
776 if (is_gimple_assign (stmt
))
779 ao_ref_init (&lhs_ref
, gimple_assign_lhs (stmt
));
780 earlier_set
= ao_ref_alias_set (&lhs_ref
);
781 earlier_base_set
= ao_ref_base_alias_set (&lhs_ref
);
784 /* We could do something fairly complex and look through PHIs
785 like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
788 Look at all the immediate uses of the VDEF (which are obviously
789 dominated by STMT). See if one or more stores 0 into the same
790 memory locations a STMT, if so remove the immediate use statements. */
791 tree defvar
= gimple_vdef (stmt
);
794 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
796 /* Limit stmt walking. */
797 if (++cnt
> param_dse_max_alias_queries_per_store
)
800 /* If USE_STMT stores 0 into one or more of the same locations
801 as STMT and STMT would kill USE_STMT, then we can just remove
804 if ((is_gimple_assign (use_stmt
)
805 && gimple_vdef (use_stmt
)
806 && (gimple_assign_single_p (use_stmt
)
807 && initializer_zerop (gimple_assign_rhs1 (use_stmt
))))
808 || (gimple_call_builtin_p (use_stmt
, BUILT_IN_NORMAL
)
809 && (fndecl
= gimple_call_fndecl (use_stmt
)) != NULL
810 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
811 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
812 && integer_zerop (gimple_call_arg (use_stmt
, 1))))
816 if (!initialize_ao_ref_for_dse (use_stmt
, &write
))
819 if (valid_ao_ref_for_dse (&write
)
820 && stmt_kills_ref_p (stmt
, &write
))
822 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
823 if (is_gimple_assign (use_stmt
))
826 ao_ref_init (&lhs_ref
, gimple_assign_lhs (use_stmt
));
827 if ((earlier_set
== ao_ref_alias_set (&lhs_ref
)
828 || alias_set_subset_of (ao_ref_alias_set (&lhs_ref
),
830 && (earlier_base_set
== ao_ref_base_alias_set (&lhs_ref
)
831 || alias_set_subset_of
832 (ao_ref_base_alias_set (&lhs_ref
),
834 delete_dead_or_redundant_assignment (&gsi
, "redundant",
838 else if (is_gimple_call (use_stmt
))
840 if ((earlier_set
== 0
841 || alias_set_subset_of (0, earlier_set
))
842 && (earlier_base_set
== 0
843 || alias_set_subset_of (0, earlier_base_set
)))
844 delete_dead_or_redundant_call (&gsi
, "redundant");
853 /* A helper of dse_optimize_stmt.
854 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
855 according to downstream uses and defs. Sets *BY_CLOBBER_P to true
856 if only clobber statements influenced the classification result.
857 Returns the classification. */
860 dse_classify_store (ao_ref
*ref
, gimple
*stmt
,
861 bool byte_tracking_enabled
, sbitmap live_bytes
,
862 bool *by_clobber_p
, tree stop_at_vuse
)
869 *by_clobber_p
= true;
871 /* Find the first dominated statement that clobbers (part of) the
872 memory stmt stores to with no intermediate statement that may use
873 part of the memory stmt stores. That is, find a store that may
874 prove stmt to be a dead store. */
883 if (gimple_code (temp
) == GIMPLE_PHI
)
885 /* If we visit this PHI by following a backedge then we have to
886 make sure ref->ref only refers to SSA names that are invariant
887 with respect to the loop represented by this PHI node. */
888 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (stmt
),
890 && !for_each_index (ref
->ref
? &ref
->ref
: &ref
->base
,
891 check_name
, gimple_bb (temp
)))
892 return DSE_STORE_LIVE
;
893 defvar
= PHI_RESULT (temp
);
894 bitmap_set_bit (visited
, SSA_NAME_VERSION (defvar
));
897 defvar
= gimple_vdef (temp
);
899 /* If we're instructed to stop walking at region boundary, do so. */
900 if (defvar
== stop_at_vuse
)
901 return DSE_STORE_LIVE
;
903 auto_vec
<gimple
*, 10> defs
;
904 gimple
*first_phi_def
= NULL
;
905 gimple
*last_phi_def
= NULL
;
906 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
908 /* Limit stmt walking. */
909 if (++cnt
> param_dse_max_alias_queries_per_store
)
915 /* In simple cases we can look through PHI nodes, but we
916 have to be careful with loops and with memory references
917 containing operands that are also operands of PHI nodes.
918 See gcc.c-torture/execute/20051110-*.c. */
919 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
921 /* If we already visited this PHI ignore it for further
923 if (!bitmap_bit_p (visited
,
924 SSA_NAME_VERSION (PHI_RESULT (use_stmt
))))
926 defs
.safe_push (use_stmt
);
928 first_phi_def
= use_stmt
;
929 last_phi_def
= use_stmt
;
932 /* If the statement is a use the store is not dead. */
933 else if (ref_maybe_used_by_stmt_p (use_stmt
, ref
))
935 /* Handle common cases where we can easily build an ao_ref
936 structure for USE_STMT and in doing so we find that the
937 references hit non-live bytes and thus can be ignored.
939 TODO: We can also use modref summary to handle calls. */
940 if (byte_tracking_enabled
941 && is_gimple_assign (use_stmt
))
944 ao_ref_init (&use_ref
, gimple_assign_rhs1 (use_stmt
));
945 if (valid_ao_ref_for_dse (&use_ref
)
946 && operand_equal_p (use_ref
.base
, ref
->base
,
948 && !live_bytes_read (&use_ref
, ref
, live_bytes
))
950 /* If this is a store, remember it as we possibly
951 need to walk the defs uses. */
952 if (gimple_vdef (use_stmt
))
953 defs
.safe_push (use_stmt
);
961 /* We have visited ourselves already so ignore STMT for the
962 purpose of chaining. */
963 else if (use_stmt
== stmt
)
965 /* If this is a store, remember it as we possibly need to walk the
967 else if (gimple_vdef (use_stmt
))
968 defs
.safe_push (use_stmt
);
973 /* STMT might be partially dead and we may be able to reduce
974 how many memory locations it stores into. */
975 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
976 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
977 return DSE_STORE_LIVE
;
980 /* If we didn't find any definition this means the store is dead
981 if it isn't a store to global reachable memory. In this case
982 just pretend the stmt makes itself dead. Otherwise fail. */
983 if (defs
.is_empty ())
985 if (ref_may_alias_global_p (ref
))
986 return DSE_STORE_LIVE
;
989 *by_clobber_p
= false;
990 return DSE_STORE_DEAD
;
993 /* Process defs and remove those we need not process further. */
994 for (unsigned i
= 0; i
< defs
.length ();)
996 gimple
*def
= defs
[i
];
999 tree vdef
= (gimple_code (def
) == GIMPLE_PHI
1000 ? gimple_phi_result (def
) : gimple_vdef (def
));
1001 /* If the path to check starts with a kill we do not need to
1003 ??? With byte tracking we need only kill the bytes currently
1005 if (stmt_kills_ref_p (def
, ref
))
1007 if (by_clobber_p
&& !gimple_clobber_p (def
))
1008 *by_clobber_p
= false;
1009 defs
.unordered_remove (i
);
1011 /* If the path ends here we do not need to process it further.
1012 This for example happens with calls to noreturn functions. */
1013 else if (has_zero_uses (vdef
))
1015 /* But if the store is to global memory it is definitely
1017 if (ref_may_alias_global_p (ref
))
1018 return DSE_STORE_LIVE
;
1019 defs
.unordered_remove (i
);
1021 /* In addition to kills we can remove defs whose only use
1022 is another def in defs. That can only ever be PHIs of which
1023 we track two for simplicity reasons, the first and last in
1024 {first,last}_phi_def (we fail for multiple PHIs anyways).
1025 We can also ignore defs that feed only into
1026 already visited PHIs. */
1027 else if (single_imm_use (vdef
, &use_p
, &use_stmt
)
1028 && (use_stmt
== first_phi_def
1029 || use_stmt
== last_phi_def
1030 || (gimple_code (use_stmt
) == GIMPLE_PHI
1031 && bitmap_bit_p (visited
,
1033 (PHI_RESULT (use_stmt
))))))
1034 defs
.unordered_remove (i
);
1039 /* If all defs kill the ref we are done. */
1040 if (defs
.is_empty ())
1041 return DSE_STORE_DEAD
;
1042 /* If more than one def survives fail. */
1043 if (defs
.length () > 1)
1045 /* STMT might be partially dead and we may be able to reduce
1046 how many memory locations it stores into. */
1047 if (byte_tracking_enabled
&& !gimple_clobber_p (stmt
))
1048 return DSE_STORE_MAYBE_PARTIAL_DEAD
;
1049 return DSE_STORE_LIVE
;
1053 /* Track partial kills. */
1054 if (byte_tracking_enabled
)
1056 clear_bytes_written_by (live_bytes
, temp
, ref
);
1057 if (bitmap_empty_p (live_bytes
))
1059 if (by_clobber_p
&& !gimple_clobber_p (temp
))
1060 *by_clobber_p
= false;
1061 return DSE_STORE_DEAD
;
1065 /* Continue walking until there are no more live bytes. */
1070 /* Delete a dead call at GSI, which is mem* call of some kind. */
1072 delete_dead_or_redundant_call (gimple_stmt_iterator
*gsi
, const char *type
)
1074 gimple
*stmt
= gsi_stmt (*gsi
);
1075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1077 fprintf (dump_file
, " Deleted %s call: ", type
);
1078 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1079 fprintf (dump_file
, "\n");
1082 basic_block bb
= gimple_bb (stmt
);
1083 tree lhs
= gimple_call_lhs (stmt
);
1086 tree ptr
= gimple_call_arg (stmt
, 0);
1087 gimple
*new_stmt
= gimple_build_assign (lhs
, ptr
);
1088 unlink_stmt_vdef (stmt
);
1089 if (gsi_replace (gsi
, new_stmt
, true))
1090 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1094 /* Then we need to fix the operand of the consuming stmt. */
1095 unlink_stmt_vdef (stmt
);
1097 /* Remove the dead store. */
1098 if (gsi_remove (gsi
, true))
1099 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1100 release_defs (stmt
);
1104 /* Delete a dead store at GSI, which is a gimple assignment. */
1107 delete_dead_or_redundant_assignment (gimple_stmt_iterator
*gsi
,
1109 bitmap need_eh_cleanup
,
1110 bitmap need_ab_cleanup
)
1112 gimple
*stmt
= gsi_stmt (*gsi
);
1113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1115 fprintf (dump_file
, " Deleted %s store: ", type
);
1116 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1117 fprintf (dump_file
, "\n");
1120 /* Then we need to fix the operand of the consuming stmt. */
1121 unlink_stmt_vdef (stmt
);
1123 /* Remove the dead store. */
1124 basic_block bb
= gimple_bb (stmt
);
1125 if (need_ab_cleanup
&& stmt_can_make_abnormal_goto (stmt
))
1126 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
1127 if (gsi_remove (gsi
, true) && need_eh_cleanup
)
1128 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1130 /* And release any SSA_NAMEs set in this statement back to the
1131 SSA_NAME manager. */
1132 release_defs (stmt
);
1135 /* Try to prove, using modref summary, that all memory written to by a call is
1136 dead and remove it. Assume that if return value is written to memory
1137 it is already proved to be dead. */
1140 dse_optimize_call (gimple_stmt_iterator
*gsi
, sbitmap live_bytes
)
1142 gcall
*stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1147 tree callee
= gimple_call_fndecl (stmt
);
1152 /* Pure/const functions are optimized by normal DCE
1153 or handled as store above. */
1154 int flags
= gimple_call_flags (stmt
);
1155 if ((flags
& (ECF_PURE
|ECF_CONST
|ECF_NOVOPS
))
1156 && !(flags
& (ECF_LOOPING_CONST_OR_PURE
)))
1159 cgraph_node
*node
= cgraph_node::get (callee
);
1163 if (stmt_could_throw_p (cfun
, stmt
)
1164 && !cfun
->can_delete_dead_exceptions
)
1167 /* If return value is used the call is not dead. */
1168 tree lhs
= gimple_call_lhs (stmt
);
1169 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1171 imm_use_iterator ui
;
1173 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, lhs
)
1174 if (!is_gimple_debug (use_stmt
))
1178 /* Verify that there are no side-effects except for return value
1179 and memory writes tracked by modref. */
1180 modref_summary
*summary
= get_modref_function_summary (node
);
1181 if (!summary
|| !summary
->try_dse
)
1184 bool by_clobber_p
= false;
1186 /* Walk all memory writes and verify that they are dead. */
1187 for (auto base_node
: summary
->stores
->bases
)
1188 for (auto ref_node
: base_node
->refs
)
1189 for (auto access_node
: ref_node
->accesses
)
1191 tree arg
= access_node
.get_call_arg (stmt
);
1196 if (integer_zerop (arg
) && flag_delete_null_pointer_checks
)
1201 if (!access_node
.get_ao_ref (stmt
, &ref
))
1203 ref
.ref_alias_set
= ref_node
->ref
;
1204 ref
.base_alias_set
= base_node
->base
;
1206 bool byte_tracking_enabled
1207 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1208 enum dse_store_status store_status
;
1210 store_status
= dse_classify_store (&ref
, stmt
,
1211 byte_tracking_enabled
,
1212 live_bytes
, &by_clobber_p
);
1213 if (store_status
!= DSE_STORE_DEAD
)
1216 delete_dead_or_redundant_assignment (gsi
, "dead", need_eh_cleanup
,
1221 /* Attempt to eliminate dead stores in the statement referenced by BSI.
1223 A dead store is a store into a memory location which will later be
1224 overwritten by another store without any intervening loads. In this
1225 case the earlier store can be deleted.
1227 In our SSA + virtual operand world we use immediate uses of virtual
1228 operands to detect dead stores. If a store's virtual definition
1229 is used precisely once by a later store to the same location which
1230 post dominates the first store, then the first store is dead. */
1233 dse_optimize_stmt (function
*fun
, gimple_stmt_iterator
*gsi
, sbitmap live_bytes
)
1235 gimple
*stmt
= gsi_stmt (*gsi
);
1237 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
1238 if (gimple_has_volatile_ops (stmt
)
1239 && (!gimple_clobber_p (stmt
)
1240 || TREE_CODE (gimple_assign_lhs (stmt
)) != MEM_REF
))
1244 /* If this is not a store we can still remove dead call using
1246 if (!initialize_ao_ref_for_dse (stmt
, &ref
))
1248 dse_optimize_call (gsi
, live_bytes
);
1252 /* We know we have virtual definitions. We can handle assignments and
1253 some builtin calls. */
1254 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1256 tree fndecl
= gimple_call_fndecl (stmt
);
1257 switch (DECL_FUNCTION_CODE (fndecl
))
1259 case BUILT_IN_MEMCPY
:
1260 case BUILT_IN_MEMMOVE
:
1261 case BUILT_IN_STRNCPY
:
1262 case BUILT_IN_MEMSET
:
1263 case BUILT_IN_MEMCPY_CHK
:
1264 case BUILT_IN_MEMMOVE_CHK
:
1265 case BUILT_IN_STRNCPY_CHK
:
1266 case BUILT_IN_MEMSET_CHK
:
1268 /* Occasionally calls with an explicit length of zero
1269 show up in the IL. It's pointless to do analysis
1270 on them, they're trivially dead. */
1271 tree size
= gimple_call_arg (stmt
, 2);
1272 if (integer_zerop (size
))
1274 delete_dead_or_redundant_call (gsi
, "dead");
1278 /* If this is a memset call that initializes an object
1279 to zero, it may be redundant with an earlier memset
1280 or empty CONSTRUCTOR of a larger object. */
1281 if ((DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET
1282 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_MEMSET_CHK
)
1283 && integer_zerop (gimple_call_arg (stmt
, 1)))
1284 dse_optimize_redundant_stores (stmt
);
1286 enum dse_store_status store_status
;
1287 bool byte_tracking_enabled
1288 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1289 store_status
= dse_classify_store (&ref
, stmt
,
1290 byte_tracking_enabled
,
1292 if (store_status
== DSE_STORE_LIVE
)
1295 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1297 maybe_trim_memstar_call (&ref
, live_bytes
, stmt
);
1301 if (store_status
== DSE_STORE_DEAD
)
1302 delete_dead_or_redundant_call (gsi
, "dead");
1306 case BUILT_IN_CALLOC
:
1307 /* We already know the arguments are integer constants. */
1308 dse_optimize_redundant_stores (stmt
);
1316 bool by_clobber_p
= false;
1318 /* Check if this statement stores zero to a memory location,
1319 and if there is a subsequent store of zero to the same
1320 memory location. If so, remove the subsequent store. */
1321 if (gimple_assign_single_p (stmt
)
1322 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1323 dse_optimize_redundant_stores (stmt
);
1325 /* Self-assignments are zombies. */
1326 if (is_gimple_assign (stmt
)
1327 && operand_equal_p (gimple_assign_rhs1 (stmt
),
1328 gimple_assign_lhs (stmt
), 0))
1332 bool byte_tracking_enabled
1333 = setup_live_bytes_from_ref (&ref
, live_bytes
);
1334 enum dse_store_status store_status
;
1335 store_status
= dse_classify_store (&ref
, stmt
,
1336 byte_tracking_enabled
,
1337 live_bytes
, &by_clobber_p
);
1338 if (store_status
== DSE_STORE_LIVE
)
1341 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
1343 maybe_trim_partially_dead_store (&ref
, live_bytes
, stmt
);
1348 /* Now we know that use_stmt kills the LHS of stmt. */
1350 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
1351 another clobber stmt. */
1352 if (gimple_clobber_p (stmt
)
1356 if (is_gimple_call (stmt
)
1357 && (gimple_has_side_effects (stmt
)
1358 || (stmt_could_throw_p (fun
, stmt
)
1359 && !fun
->can_delete_dead_exceptions
)))
1361 /* See if we can remove complete call. */
1362 if (dse_optimize_call (gsi
, live_bytes
))
1364 /* Make sure we do not remove a return slot we cannot reconstruct
1366 if (gimple_call_return_slot_opt_p (as_a
<gcall
*>(stmt
))
1367 && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt
)))
1369 (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt
))))))
1371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1373 fprintf (dump_file
, " Deleted dead store in call LHS: ");
1374 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1375 fprintf (dump_file
, "\n");
1377 gimple_call_set_lhs (stmt
, NULL_TREE
);
1381 delete_dead_or_redundant_assignment (gsi
, "dead", need_eh_cleanup
,
1387 const pass_data pass_data_dse
=
1389 GIMPLE_PASS
, /* type */
1391 OPTGROUP_NONE
, /* optinfo_flags */
1392 TV_TREE_DSE
, /* tv_id */
1393 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1394 0, /* properties_provided */
1395 0, /* properties_destroyed */
1396 0, /* todo_flags_start */
1397 0, /* todo_flags_finish */
1400 class pass_dse
: public gimple_opt_pass
1403 pass_dse (gcc::context
*ctxt
)
1404 : gimple_opt_pass (pass_data_dse
, ctxt
)
1407 /* opt_pass methods: */
1408 opt_pass
* clone () { return new pass_dse (m_ctxt
); }
1409 virtual bool gate (function
*) { return flag_tree_dse
!= 0; }
1410 virtual unsigned int execute (function
*);
1412 }; // class pass_dse
1415 pass_dse::execute (function
*fun
)
1418 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
1419 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
1420 auto_sbitmap
live_bytes (param_dse_max_object_size
);
1422 renumber_gimple_stmt_uids (fun
);
1424 calculate_dominance_info (CDI_DOMINATORS
);
1426 /* Dead store elimination is fundamentally a reverse program order walk. */
1427 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fun
) - NUM_FIXED_BLOCKS
);
1428 int n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
1429 for (int i
= n
; i
!= 0; --i
)
1431 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, rpo
[i
-1]);
1432 gimple_stmt_iterator gsi
;
1434 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
1436 gimple
*stmt
= gsi_stmt (gsi
);
1438 if (gimple_vdef (stmt
))
1439 dse_optimize_stmt (fun
, &gsi
, live_bytes
);
1440 else if (def_operand_p
1441 def_p
= single_ssa_def_operand (stmt
, SSA_OP_DEF
))
1443 /* When we remove dead stores make sure to also delete trivially
1445 if (has_zero_uses (DEF_FROM_PTR (def_p
))
1446 && !gimple_has_side_effects (stmt
)
1447 && !is_ctrl_altering_stmt (stmt
)
1448 && (!stmt_could_throw_p (fun
, stmt
)
1449 || fun
->can_delete_dead_exceptions
))
1451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1453 fprintf (dump_file
, " Deleted trivially dead stmt: ");
1454 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
1455 fprintf (dump_file
, "\n");
1457 if (gsi_remove (&gsi
, true) && need_eh_cleanup
)
1458 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1459 release_defs (stmt
);
1462 if (gsi_end_p (gsi
))
1463 gsi
= gsi_last_bb (bb
);
1467 bool removed_phi
= false;
1468 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);)
1470 gphi
*phi
= si
.phi ();
1471 if (has_zero_uses (gimple_phi_result (phi
)))
1473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1475 fprintf (dump_file
, " Deleted trivially dead PHI: ");
1476 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
1477 fprintf (dump_file
, "\n");
1479 remove_phi_node (&si
, true);
1485 if (removed_phi
&& gimple_seq_empty_p (phi_nodes (bb
)))
1486 todo
|= TODO_cleanup_cfg
;
1490 /* Removal of stores may make some EH edges dead. Purge such edges from
1491 the CFG as needed. */
1492 if (!bitmap_empty_p (need_eh_cleanup
))
1494 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
1495 todo
|= TODO_cleanup_cfg
;
1497 if (!bitmap_empty_p (need_ab_cleanup
))
1499 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
1500 todo
|= TODO_cleanup_cfg
;
1503 BITMAP_FREE (need_eh_cleanup
);
1504 BITMAP_FREE (need_ab_cleanup
);
1512 make_pass_dse (gcc::context
*ctxt
)
1514 return new pass_dse (ctxt
);