Line data Source code
1 : /* Dead and redundant store elimination
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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)
9 : any later version.
10 :
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.
15 :
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/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "rtl.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "tree-pass.h"
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "fold-const.h"
31 : #include "gimple-iterator.h"
32 : #include "tree-cfg.h"
33 : #include "tree-dfa.h"
34 : #include "tree-cfgcleanup.h"
35 : #include "alias.h"
36 : #include "tree-ssa-loop.h"
37 : #include "tree-ssa-dse.h"
38 : #include "builtins.h"
39 : #include "gimple-fold.h"
40 : #include "tree-eh.h"
41 : #include "cfganal.h"
42 : #include "cgraph.h"
43 : #include "ipa-modref-tree.h"
44 : #include "ipa-modref.h"
45 : #include "target.h"
46 : #include "tree-ssa-loop-niter.h"
47 : #include "cfgloop.h"
48 : #include "tree-data-ref.h"
49 : #include "internal-fn.h"
50 : #include "tree-ssa.h"
51 :
52 : /* This file implements dead store elimination.
53 :
54 : A dead store is a store into a memory location which will later be
55 : overwritten by another store without any intervening loads. In this
56 : case the earlier store can be deleted or trimmed if the store
57 : was partially dead.
58 :
59 : A redundant store is a store into a memory location which stores
60 : the exact same value as a prior store to the same memory location.
61 : While this can often be handled by dead store elimination, removing
62 : the redundant store is often better than removing or trimming the
63 : dead store.
64 :
65 : In our SSA + virtual operand world we use immediate uses of virtual
66 : operands to detect these cases. If a store's virtual definition
67 : is used precisely once by a later store to the same location which
68 : post dominates the first store, then the first store is dead. If
69 : the data stored is the same, then the second store is redundant.
70 :
71 : The single use of the store's virtual definition ensures that
72 : there are no intervening aliased loads and the requirement that
73 : the second load post dominate the first ensures that if the earlier
74 : store executes, then the later stores will execute before the function
75 : exits.
76 :
77 : It may help to think of this as first moving the earlier store to
78 : the point immediately before the later store. Again, the single
79 : use of the virtual definition and the post-dominance relationship
80 : ensure that such movement would be safe. Clearly if there are
81 : back to back stores, then the second is makes the first dead. If
82 : the second store stores the same value, then the second store is
83 : redundant.
84 :
85 : Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
86 : may also help in understanding this code since it discusses the
87 : relationship between dead store and redundant load elimination. In
88 : fact, they are the same transformation applied to different views of
89 : the CFG. */
90 :
91 : static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *);
92 :
93 : /* Bitmap of blocks that have had EH statements cleaned. We should
94 : remove their dead edges eventually. */
95 : static bitmap need_eh_cleanup;
96 : static bitmap need_ab_cleanup;
97 :
98 : /* STMT is a statement that may write into memory. Analyze it and
99 : initialize WRITE to describe how STMT affects memory. When
100 : MAY_DEF_OK is true then the function initializes WRITE to what
101 : the stmt may define.
102 :
103 : Return TRUE if the statement was analyzed, FALSE otherwise.
104 :
105 : It is always safe to return FALSE. But typically better optimziation
106 : can be achieved by analyzing more statements. */
107 :
108 : static bool
109 236605623 : initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write, bool may_def_ok = false)
110 : {
111 : /* It's advantageous to handle certain mem* functions. */
112 236605623 : if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
113 : {
114 5427936 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
115 : {
116 1337344 : case BUILT_IN_MEMCPY:
117 1337344 : case BUILT_IN_MEMMOVE:
118 1337344 : case BUILT_IN_MEMSET:
119 1337344 : case BUILT_IN_MEMCPY_CHK:
120 1337344 : case BUILT_IN_MEMMOVE_CHK:
121 1337344 : case BUILT_IN_MEMSET_CHK:
122 1337344 : case BUILT_IN_STRNCPY:
123 1337344 : case BUILT_IN_STRNCPY_CHK:
124 1337344 : {
125 1337344 : tree size = gimple_call_arg (stmt, 2);
126 1337344 : tree ptr = gimple_call_arg (stmt, 0);
127 1337344 : ao_ref_init_from_ptr_and_size (write, ptr, size);
128 1337344 : return true;
129 : }
130 :
131 : /* A calloc call can never be dead, but it can make
132 : subsequent stores redundant if they store 0 into
133 : the same memory locations. */
134 3275 : case BUILT_IN_CALLOC:
135 3275 : {
136 3275 : tree nelem = gimple_call_arg (stmt, 0);
137 3275 : tree selem = gimple_call_arg (stmt, 1);
138 3275 : tree lhs;
139 3275 : if (TREE_CODE (nelem) == INTEGER_CST
140 2698 : && TREE_CODE (selem) == INTEGER_CST
141 5781 : && (lhs = gimple_call_lhs (stmt)) != NULL_TREE)
142 : {
143 2495 : tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem),
144 : nelem, selem);
145 2495 : ao_ref_init_from_ptr_and_size (write, lhs, size);
146 2495 : return true;
147 : }
148 : }
149 :
150 : default:
151 : break;
152 : }
153 : }
154 231177687 : else if (is_gimple_call (stmt)
155 231177687 : && gimple_call_internal_p (stmt))
156 : {
157 439816 : switch (gimple_call_internal_fn (stmt))
158 : {
159 1337 : case IFN_LEN_STORE:
160 1337 : case IFN_MASK_STORE:
161 1337 : case IFN_MASK_LEN_STORE:
162 1337 : {
163 1337 : internal_fn ifn = gimple_call_internal_fn (stmt);
164 1337 : int stored_value_index = internal_fn_stored_value_index (ifn);
165 1337 : int len_index = internal_fn_len_index (ifn);
166 1337 : if (ifn == IFN_LEN_STORE)
167 : {
168 0 : tree len = gimple_call_arg (stmt, len_index);
169 0 : tree bias = gimple_call_arg (stmt, len_index + 1);
170 0 : if (tree_fits_uhwi_p (len))
171 : {
172 0 : ao_ref_init_from_ptr_and_size (write,
173 : gimple_call_arg (stmt, 0),
174 : int_const_binop (MINUS_EXPR,
175 : len, bias));
176 0 : return true;
177 : }
178 : }
179 : /* We cannot initialize a must-def ao_ref (in all cases) but we
180 : can provide a may-def variant. */
181 1337 : if (may_def_ok)
182 : {
183 1299 : ao_ref_init_from_ptr_and_range (
184 : write, gimple_call_arg (stmt, 0), true, 0, -1,
185 1299 : tree_to_poly_int64 (TYPE_SIZE (
186 : TREE_TYPE (gimple_call_arg (stmt, stored_value_index)))));
187 1299 : return true;
188 : }
189 : break;
190 : }
191 : default:;
192 : }
193 : }
194 235264485 : if (tree lhs = gimple_get_lhs (stmt))
195 : {
196 221085664 : if (TREE_CODE (lhs) != SSA_NAME
197 221085664 : && (may_def_ok || !stmt_could_throw_p (cfun, stmt)))
198 : {
199 203776695 : ao_ref_init (write, lhs);
200 203776695 : return true;
201 : }
202 : }
203 : return false;
204 : }
205 :
206 : /* Given REF from the alias oracle, return TRUE if it is a valid
207 : kill memory reference for dead store elimination, false otherwise.
208 :
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
211 : bytes. */
212 :
213 : static bool
214 172324788 : valid_ao_ref_kill_for_dse (ao_ref *ref)
215 : {
216 172324788 : return (ao_ref_base (ref)
217 172324788 : && known_size_p (ref->max_size)
218 171991480 : && maybe_ne (ref->size, 0)
219 171973868 : && known_eq (ref->max_size, ref->size)
220 343792804 : && known_ge (ref->offset, 0));
221 : }
222 :
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.
225 :
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. */
228 :
229 : static bool
230 37923503 : valid_ao_ref_for_dse (ao_ref *ref)
231 : {
232 37923503 : return (ao_ref_base (ref)
233 37923503 : && known_size_p (ref->max_size)
234 75365604 : && known_ge (ref->offset, 0));
235 : }
236 :
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. */
240 :
241 : static bool
242 105791725 : get_byte_aligned_range_containing_ref (ao_ref *ref, poly_int64 *offset,
243 : HOST_WIDE_INT *size)
244 : {
245 0 : if (!known_size_p (ref->max_size))
246 : return false;
247 105791725 : *offset = aligned_lower_bound (ref->offset, BITS_PER_UNIT);
248 105791725 : poly_int64 end = aligned_upper_bound (ref->offset + ref->max_size,
249 : BITS_PER_UNIT);
250 105791725 : return (end - *offset).is_constant (size);
251 : }
252 :
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. */
256 :
257 : static bool
258 98717053 : get_byte_aligned_range_contained_in_ref (ao_ref *ref, poly_int64 *offset,
259 : HOST_WIDE_INT *size)
260 : {
261 98717053 : if (!known_size_p (ref->size)
262 98717053 : || !known_eq (ref->size, ref->max_size))
263 : return false;
264 98717053 : *offset = aligned_upper_bound (ref->offset, BITS_PER_UNIT);
265 98717053 : poly_int64 end = aligned_lower_bound (ref->offset + ref->max_size,
266 : BITS_PER_UNIT);
267 : /* For bit accesses we can get -1 here, but also 0 sized kill is not
268 : useful. */
269 98717053 : if (!known_gt (end, *offset))
270 : return false;
271 98581243 : return (end - *offset).is_constant (size);
272 : }
273 :
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. */
278 :
279 : static bool
280 102322294 : get_byte_range (ao_ref *copy, ao_ref *ref, bool kill,
281 : HOST_WIDE_INT *ret_offset, HOST_WIDE_INT *ret_size)
282 : {
283 102322294 : HOST_WIDE_INT copy_size, ref_size;
284 102322294 : poly_int64 copy_offset, ref_offset;
285 102322294 : HOST_WIDE_INT diff;
286 :
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. */
290 102322294 : if (kill)
291 : {
292 98717053 : if (!get_byte_aligned_range_contained_in_ref (copy, ©_offset,
293 : ©_size))
294 : return false;
295 : }
296 : else
297 : {
298 3605241 : if (!get_byte_aligned_range_containing_ref (copy, ©_offset,
299 : ©_size))
300 : return false;
301 : }
302 :
303 198293047 : if (!get_byte_aligned_range_containing_ref (ref, &ref_offset, &ref_size)
304 : || !ordered_p (copy_offset, ref_offset))
305 : return false;
306 :
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 102186484 : copy_size /= BITS_PER_UNIT;
311 102186484 : ref_size /= BITS_PER_UNIT;
312 :
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 102186484 : if (maybe_lt (copy_offset, ref_offset))
317 : {
318 9376600 : if (!(ref_offset - copy_offset).is_constant (&diff)
319 9376600 : || copy_size < diff / BITS_PER_UNIT)
320 : return false;
321 2720589 : copy_size -= diff / BITS_PER_UNIT;
322 2720589 : copy_offset = ref_offset;
323 : }
324 :
325 95530473 : if (!(copy_offset - ref_offset).is_constant (&diff)
326 95530473 : || ref_size <= diff / BITS_PER_UNIT)
327 : return false;
328 :
329 : /* If COPY extends beyond REF, chop off its size appropriately. */
330 6215731 : HOST_WIDE_INT limit = ref_size - diff / BITS_PER_UNIT;
331 :
332 6215731 : if (copy_size > limit)
333 1112233 : copy_size = limit;
334 6215731 : *ret_size = copy_size;
335 6215731 : if (!(copy_offset - ref_offset).is_constant (ret_offset))
336 : return false;
337 6215731 : *ret_offset /= BITS_PER_UNIT;
338 6215731 : return true;
339 : }
340 :
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. */
344 : static void
345 172324788 : clear_live_bytes_for_ref (sbitmap live_bytes, ao_ref *ref, ao_ref *write)
346 : {
347 172324788 : HOST_WIDE_INT start, size;
348 :
349 172324788 : if (valid_ao_ref_kill_for_dse (write)
350 171467760 : && operand_equal_p (write->base, ref->base, OEP_ADDRESS_OF)
351 271041841 : && get_byte_range (write, ref, true, &start, &size))
352 2610490 : bitmap_clear_range (live_bytes, start, size);
353 172324788 : }
354 :
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.
358 :
359 : This routine must be conservative. If we don't know the offset or
360 : actual size written, assume nothing was written. */
361 :
362 : static void
363 186428939 : clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref)
364 : {
365 186428939 : ao_ref write;
366 :
367 186428939 : if (gcall *call = dyn_cast <gcall *> (stmt))
368 : {
369 5624708 : bool interposed;
370 5624708 : modref_summary *summary = get_modref_function_summary (call, &interposed);
371 :
372 5624708 : if (summary && !interposed)
373 494742 : for (auto kill : summary->kills)
374 66659 : if (kill.get_ao_ref (as_a <gcall *> (stmt), &write))
375 66635 : clear_live_bytes_for_ref (live_bytes, ref, &write);
376 : }
377 186428939 : if (!initialize_ao_ref_for_dse (stmt, &write))
378 14170786 : return;
379 :
380 172258153 : clear_live_bytes_for_ref (live_bytes, ref, &write);
381 : }
382 :
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. */
386 :
387 : static bool
388 31488084 : setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes)
389 : {
390 31488084 : HOST_WIDE_INT const_size;
391 31488084 : if (valid_ao_ref_for_dse (ref)
392 31032981 : && ((aligned_upper_bound (ref->offset + ref->max_size, BITS_PER_UNIT)
393 31032981 : - aligned_lower_bound (ref->offset,
394 31032981 : BITS_PER_UNIT)).is_constant (&const_size))
395 31032981 : && (const_size / BITS_PER_UNIT <= param_dse_max_object_size)
396 62200647 : && const_size > 1)
397 : {
398 30712346 : bitmap_clear (live_bytes);
399 30712346 : bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT);
400 30712346 : return true;
401 : }
402 : return false;
403 : }
404 :
405 : /* Compute the number of stored bytes that we can trim from the head and
406 : tail of REF. LIVE is the bitmap of stores to REF that are still live.
407 :
408 : Store the number of bytes trimmed from the head and tail in TRIM_HEAD
409 : and TRIM_TAIL respectively.
410 :
411 : STMT is the statement being trimmed and is used for debugging dump
412 : output only. */
413 :
414 : static void
415 3463702 : compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail,
416 : gimple *stmt)
417 : {
418 3463702 : *trim_head = 0;
419 3463702 : *trim_tail = 0;
420 :
421 : /* We use bitmaps biased such that ref->offset is contained in bit zero and
422 : the bitmap extends through ref->max_size, so we know that in the original
423 : bitmap bits 0 .. ref->max_size were true. But we need to check that this
424 : covers the bytes of REF exactly. */
425 3463702 : const unsigned int offset_align = known_alignment (ref->offset);
426 3463702 : const unsigned int size_align = known_alignment (ref->size);
427 3463702 : if ((offset_align > 0 && offset_align < BITS_PER_UNIT)
428 3463413 : || (size_align > 0 && size_align < BITS_PER_UNIT)
429 6927115 : || !known_eq (ref->size, ref->max_size))
430 12374 : return;
431 :
432 : /* Now identify how much, if any of the tail we can chop off. */
433 3451328 : HOST_WIDE_INT const_size;
434 3451328 : int last_live = bitmap_last_set_bit (live);
435 3451328 : if (ref->size.is_constant (&const_size))
436 : {
437 3451328 : int last_orig = (const_size / BITS_PER_UNIT) - 1;
438 : /* We can leave inconvenient amounts on the tail as
439 : residual handling in mem* and str* functions is usually
440 : reasonably efficient. */
441 3451328 : *trim_tail = last_orig - last_live;
442 :
443 : /* But don't trim away out of bounds accesses, as this defeats
444 : proper warnings.
445 :
446 : We could have a type with no TYPE_SIZE_UNIT or we could have a VLA
447 : where TYPE_SIZE_UNIT is not a constant. */
448 3451328 : if (*trim_tail
449 9867 : && TYPE_SIZE_UNIT (TREE_TYPE (ref->base))
450 9867 : && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST
451 3461194 : && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)),
452 : last_orig) <= 0)
453 135 : *trim_tail = 0;
454 : }
455 :
456 : /* Identify how much, if any of the head we can chop off. */
457 3451328 : int first_orig = 0;
458 3451328 : int first_live = bitmap_first_set_bit (live);
459 3451328 : *trim_head = first_live - first_orig;
460 :
461 : /* If REF is aligned, try to maintain this alignment if it reduces
462 : the number of (power-of-two sized aligned) writes to memory. */
463 3451328 : unsigned int align_bits;
464 3451328 : unsigned HOST_WIDE_INT bitpos;
465 3361132 : if ((*trim_head || *trim_tail)
466 95635 : && last_live - first_live >= 2
467 94823 : && ao_ref_alignment (ref, &align_bits, &bitpos)
468 77309 : && align_bits >= 32
469 76959 : && bitpos == 0
470 3524441 : && align_bits % BITS_PER_UNIT == 0)
471 : {
472 73113 : unsigned int align_units = align_bits / BITS_PER_UNIT;
473 73113 : if (align_units > 16)
474 : align_units = 16;
475 75095 : while ((first_live | (align_units - 1)) > (unsigned int)last_live)
476 1982 : align_units >>= 1;
477 :
478 73113 : if (*trim_head)
479 : {
480 68808 : unsigned int pos = first_live & (align_units - 1);
481 76206 : for (unsigned int i = 1; i <= align_units; i <<= 1)
482 : {
483 76206 : unsigned int mask = ~(i - 1);
484 76206 : unsigned int bytes = align_units - (pos & mask);
485 76206 : if (wi::popcount (bytes) <= 1)
486 : {
487 68808 : *trim_head &= mask;
488 68808 : break;
489 : }
490 : }
491 : }
492 :
493 73113 : if (*trim_tail)
494 : {
495 6835 : unsigned int pos = last_live & (align_units - 1);
496 10128 : for (unsigned int i = 1; i <= align_units; i <<= 1)
497 : {
498 10128 : int mask = i - 1;
499 10128 : unsigned int bytes = (pos | mask) + 1;
500 10128 : if ((last_live | mask) > (last_live + *trim_tail))
501 : break;
502 10128 : if (wi::popcount (bytes) <= 1)
503 : {
504 6835 : unsigned int extra = (last_live | mask) - last_live;
505 6835 : *trim_tail -= extra;
506 6835 : break;
507 : }
508 : }
509 : }
510 : }
511 :
512 3451328 : if ((*trim_head || *trim_tail) && dump_file && (dump_flags & TDF_DETAILS))
513 : {
514 18 : fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ",
515 : *trim_head, *trim_tail);
516 18 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
517 18 : fprintf (dump_file, "\n");
518 : }
519 : }
520 :
521 : /* STMT initializes an object from COMPLEX_CST where one or more of the bytes
522 : written may be dead stores. REF is a representation of the memory written.
523 : LIVE is the bitmap of stores to REF that are still live.
524 :
525 : Attempt to rewrite STMT so that only the real or the imaginary part of the
526 : object is actually stored. */
527 :
528 : static void
529 5520 : maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt)
530 : {
531 5520 : int trim_head, trim_tail;
532 5520 : compute_trims (ref, live, &trim_head, &trim_tail, stmt);
533 :
534 : /* The amount of data trimmed from the head or tail must be at
535 : least half the size of the object to ensure we're trimming
536 : the entire real or imaginary half. By writing things this
537 : way we avoid more O(n) bitmap operations. */
538 5520 : if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size))
539 : {
540 : /* TREE_REALPART is live */
541 2 : tree x = TREE_REALPART (gimple_assign_rhs1 (stmt));
542 2 : tree y = gimple_assign_lhs (stmt);
543 2 : y = build1 (REALPART_EXPR, TREE_TYPE (x), y);
544 2 : gimple_assign_set_lhs (stmt, y);
545 2 : gimple_assign_set_rhs1 (stmt, x);
546 : }
547 5518 : else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size))
548 : {
549 : /* TREE_IMAGPART is live */
550 3 : tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt));
551 3 : tree y = gimple_assign_lhs (stmt);
552 3 : y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y);
553 3 : gimple_assign_set_lhs (stmt, y);
554 3 : gimple_assign_set_rhs1 (stmt, x);
555 : }
556 :
557 : /* Other cases indicate parts of both the real and imag subobjects
558 : are live. We do not try to optimize those cases. */
559 5520 : }
560 :
561 : /* STMT initializes an object using a CONSTRUCTOR where one or more of the
562 : bytes written are dead stores. REF is a representation of the memory
563 : written. LIVE is the bitmap of stores to REF that are still live.
564 :
565 : Attempt to rewrite STMT so that it writes fewer memory locations.
566 :
567 : The most common case for getting here is a CONSTRUCTOR with no elements
568 : being used to zero initialize an object. We do not try to handle other
569 : cases as those would force us to fully cover the object with the
570 : CONSTRUCTOR node except for the components that are dead.
571 : Also handles integer stores of 0 which can happen with memset/memcpy optimizations. */
572 :
573 : static void
574 3311898 : maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt, bool was_integer_cst)
575 : {
576 3311898 : tree ctor = gimple_assign_rhs1 (stmt);
577 :
578 : /* This is the only case we currently handle. It actually seems to
579 : catch most cases of actual interest. */
580 3790391 : gcc_assert (was_integer_cst ? integer_zerop (ctor) : CONSTRUCTOR_NELTS (ctor) == 0);
581 :
582 3311898 : int head_trim = 0;
583 3311898 : int tail_trim = 0;
584 3311898 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
585 :
586 : /* Now we want to replace the constructor initializer
587 : with memset (object + head_trim, 0, size - head_trim - tail_trim). */
588 3311898 : if (head_trim || tail_trim)
589 : {
590 : /* We want &lhs for the MEM_REF expression. */
591 89093 : tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt));
592 :
593 89093 : STRIP_USELESS_TYPE_CONVERSION (lhs_addr);
594 :
595 89093 : if (! is_gimple_min_invariant (lhs_addr))
596 17655 : return;
597 :
598 : /* The number of bytes for the new constructor. */
599 71438 : poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT);
600 71438 : poly_int64 count = ref_bytes - head_trim - tail_trim;
601 :
602 : /* And the new type for the CONSTRUCTOR. Essentially it's just
603 : a char array large enough to cover the non-trimmed parts of
604 : the original CONSTRUCTOR. Note we want explicit bounds here
605 : so that we know how many bytes to clear when expanding the
606 : CONSTRUCTOR. */
607 71438 : tree type = build_array_type_nelts (char_type_node, count);
608 :
609 : /* Build a suitable alias type rather than using alias set zero
610 : to avoid pessimizing. */
611 71438 : tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt));
612 :
613 : /* Build a MEM_REF representing the whole accessed area, starting
614 : at the first byte not trimmed. */
615 71438 : tree exp = fold_build2 (MEM_REF, type, lhs_addr,
616 : build_int_cst (alias_type, head_trim));
617 :
618 : /* Now update STMT with a new RHS and LHS. */
619 71438 : gimple_assign_set_lhs (stmt, exp);
620 71438 : gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL));
621 : }
622 : }
623 :
624 : /* STMT is a memcpy, memmove or memset. Decrement the number of bytes
625 : copied/set by DECREMENT. */
626 : static void
627 763 : decrement_count (gimple *stmt, int decrement)
628 : {
629 763 : tree *countp = gimple_call_arg_ptr (stmt, 2);
630 763 : gcc_assert (TREE_CODE (*countp) == INTEGER_CST);
631 1526 : *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp)
632 763 : - decrement));
633 763 : }
634 :
635 : static void
636 700 : increment_start_addr (gimple *stmt, tree *where, int increment)
637 : {
638 700 : if (tree lhs = gimple_call_lhs (stmt))
639 6 : if (where == gimple_call_arg_ptr (stmt, 0))
640 : {
641 6 : gassign *newop = gimple_build_assign (lhs, unshare_expr (*where));
642 6 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
643 6 : gsi_insert_after (&gsi, newop, GSI_SAME_STMT);
644 6 : gimple_call_set_lhs (stmt, NULL_TREE);
645 6 : update_stmt (stmt);
646 : }
647 :
648 700 : if (TREE_CODE (*where) == SSA_NAME)
649 : {
650 193 : tree tem = make_ssa_name (TREE_TYPE (*where));
651 193 : gassign *newop
652 193 : = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where,
653 193 : build_int_cst (sizetype, increment));
654 193 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
655 193 : gsi_insert_before (&gsi, newop, GSI_SAME_STMT);
656 193 : *where = tem;
657 193 : update_stmt (stmt);
658 193 : return;
659 : }
660 :
661 507 : *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node,
662 : *where,
663 : build_int_cst (ptr_type_node,
664 : increment)));
665 507 : STRIP_USELESS_TYPE_CONVERSION (*where);
666 : }
667 :
668 : /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
669 : (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce
670 : the amount of data it actually writes.
671 :
672 : Right now we only support trimming from the head or the tail of the
673 : memory region. In theory we could split the mem* call, but it's
674 : likely of marginal value. */
675 :
676 : static void
677 146284 : maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
678 : {
679 146284 : int head_trim, tail_trim;
680 146284 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
681 : {
682 4645 : case BUILT_IN_STRNCPY:
683 4645 : case BUILT_IN_STRNCPY_CHK:
684 4645 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
685 4645 : if (head_trim)
686 : {
687 : /* Head trimming of strncpy is only possible if we can
688 : prove all bytes we would trim are non-zero (or we could
689 : turn the strncpy into memset if there must be zero
690 : among the head trimmed bytes). If we don't know anything
691 : about those bytes, the presence or absence of '\0' bytes
692 : in there will affect whether it acts for the non-trimmed
693 : bytes as memset or memcpy/strncpy. */
694 74 : c_strlen_data lendata = { };
695 74 : int orig_head_trim = head_trim;
696 74 : tree srcstr = gimple_call_arg (stmt, 1);
697 74 : if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1)
698 74 : || !tree_fits_uhwi_p (lendata.minlen))
699 8 : head_trim = 0;
700 66 : else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim)
701 : {
702 60 : head_trim = tree_to_uhwi (lendata.minlen);
703 60 : if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0)
704 0 : head_trim &= ~(UNITS_PER_WORD - 1);
705 : }
706 74 : if (orig_head_trim != head_trim
707 68 : && dump_file
708 82 : && (dump_flags & TDF_DETAILS))
709 8 : fprintf (dump_file,
710 : " Adjusting strncpy trimming to (head = %d,"
711 : " tail = %d)\n", head_trim, tail_trim);
712 : }
713 4645 : goto do_memcpy;
714 :
715 103267 : case BUILT_IN_MEMCPY:
716 103267 : case BUILT_IN_MEMMOVE:
717 103267 : case BUILT_IN_MEMCPY_CHK:
718 103267 : case BUILT_IN_MEMMOVE_CHK:
719 103267 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
720 :
721 107912 : do_memcpy:
722 : /* Tail trimming is easy, we can just reduce the count. */
723 107912 : if (tail_trim)
724 73 : decrement_count (stmt, tail_trim);
725 :
726 : /* Head trimming requires adjusting all the arguments. */
727 107912 : if (head_trim)
728 : {
729 : /* For __*_chk need to adjust also the last argument. */
730 122 : if (gimple_call_num_args (stmt) == 4)
731 : {
732 49 : tree size = gimple_call_arg (stmt, 3);
733 49 : if (!tree_fits_uhwi_p (size))
734 : break;
735 7 : if (!integer_all_onesp (size))
736 : {
737 7 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
738 7 : if (sz < (unsigned) head_trim)
739 : break;
740 7 : tree arg = wide_int_to_tree (TREE_TYPE (size),
741 7 : sz - head_trim);
742 7 : gimple_call_set_arg (stmt, 3, arg);
743 : }
744 : }
745 80 : tree *dst = gimple_call_arg_ptr (stmt, 0);
746 80 : increment_start_addr (stmt, dst, head_trim);
747 80 : tree *src = gimple_call_arg_ptr (stmt, 1);
748 80 : increment_start_addr (stmt, src, head_trim);
749 80 : decrement_count (stmt, head_trim);
750 : }
751 : break;
752 :
753 38372 : case BUILT_IN_MEMSET:
754 38372 : case BUILT_IN_MEMSET_CHK:
755 38372 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
756 :
757 : /* Tail trimming is easy, we can just reduce the count. */
758 38372 : if (tail_trim)
759 70 : decrement_count (stmt, tail_trim);
760 :
761 : /* Head trimming requires adjusting all the arguments. */
762 38372 : if (head_trim)
763 : {
764 : /* For __*_chk need to adjust also the last argument. */
765 540 : if (gimple_call_num_args (stmt) == 4)
766 : {
767 7 : tree size = gimple_call_arg (stmt, 3);
768 7 : if (!tree_fits_uhwi_p (size))
769 : break;
770 7 : if (!integer_all_onesp (size))
771 : {
772 7 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
773 7 : if (sz < (unsigned) head_trim)
774 : break;
775 7 : tree arg = wide_int_to_tree (TREE_TYPE (size),
776 7 : sz - head_trim);
777 7 : gimple_call_set_arg (stmt, 3, arg);
778 : }
779 : }
780 540 : tree *dst = gimple_call_arg_ptr (stmt, 0);
781 540 : increment_start_addr (stmt, dst, head_trim);
782 540 : decrement_count (stmt, head_trim);
783 : }
784 : break;
785 :
786 : default:
787 : break;
788 : }
789 146284 : }
790 :
791 : /* STMT is a memory write where one or more bytes written are dead stores.
792 : REF is a representation of the memory written. LIVE is the bitmap of
793 : stores to REF that are still live.
794 :
795 : Attempt to rewrite STMT so that it writes fewer memory locations. Right
796 : now we only support trimming at the start or end of the memory region.
797 : It's not clear how much there is to be gained by trimming from the middle
798 : of the region. */
799 :
800 : static void
801 26200003 : maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt)
802 : {
803 26200003 : if (is_gimple_assign (stmt)
804 26200003 : && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF)
805 : {
806 24883235 : switch (gimple_assign_rhs_code (stmt))
807 : {
808 478493 : case CONSTRUCTOR:
809 478493 : maybe_trim_constructor_store (ref, live, stmt, false);
810 478493 : break;
811 5520 : case COMPLEX_CST:
812 5520 : maybe_trim_complex_store (ref, live, stmt);
813 5520 : break;
814 8807845 : case INTEGER_CST:
815 8807845 : if (integer_zerop (gimple_assign_rhs1 (stmt))
816 8807845 : && type_has_mode_precision_p (TREE_TYPE (gimple_assign_lhs (stmt))))
817 2833405 : maybe_trim_constructor_store (ref, live, stmt, true);
818 : break;
819 : default:
820 : break;
821 : }
822 : }
823 26200003 : }
824 :
825 : /* Return TRUE if USE_REF reads bytes from LIVE where live is
826 : derived from REF, a write reference.
827 :
828 : While this routine may modify USE_REF, it's passed by value, not
829 : location. So callers do not see those modifications. */
830 :
831 : static bool
832 3605241 : live_bytes_read (ao_ref *use_ref, ao_ref *ref, sbitmap live)
833 : {
834 : /* We have already verified that USE_REF and REF hit the same object.
835 : Now verify that there's actually an overlap between USE_REF and REF. */
836 3605241 : HOST_WIDE_INT start, size;
837 3605241 : if (get_byte_range (use_ref, ref, false, &start, &size))
838 : {
839 : /* If USE_REF covers all of REF, then it will hit one or more
840 : live bytes. This avoids useless iteration over the bitmap
841 : below. */
842 3605241 : if (start == 0 && known_eq (size * 8, ref->size))
843 : return true;
844 :
845 : /* Now check if any of the remaining bits in use_ref are set in LIVE. */
846 980109 : return bitmap_any_bit_in_range_p (live, start, (start + size - 1));
847 : }
848 : return true;
849 : }
850 :
851 : /* Callback for dse_classify_store calling for_each_index. Verify that
852 : indices are invariant in the loop with backedge PHI in basic-block DATA. */
853 :
854 : static bool
855 2656124 : check_name (tree, tree *idx, void *data)
856 : {
857 2656124 : basic_block phi_bb = (basic_block) data;
858 2656124 : if (TREE_CODE (*idx) == SSA_NAME
859 1776851 : && !SSA_NAME_IS_DEFAULT_DEF (*idx)
860 4304582 : && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)),
861 : phi_bb))
862 : return false;
863 : return true;
864 : }
865 :
866 : /* STMT stores the value 0 into one or more memory locations
867 : (via memset, empty constructor, calloc call, etc).
868 :
869 : See if there is a subsequent store of the value 0 to one
870 : or more of the same memory location(s). If so, the subsequent
871 : store is redundant and can be removed.
872 :
873 : The subsequent stores could be via memset, empty constructors,
874 : simple MEM stores, etc. */
875 :
876 : static void
877 4234102 : dse_optimize_redundant_stores (gimple *stmt)
878 : {
879 4234102 : int cnt = 0;
880 :
881 : /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */
882 4234102 : alias_set_type earlier_set = 0;
883 4234102 : alias_set_type earlier_base_set = 0;
884 4234102 : if (is_gimple_assign (stmt))
885 : {
886 4175922 : ao_ref lhs_ref;
887 4175922 : ao_ref_init (&lhs_ref, gimple_assign_lhs (stmt));
888 4175922 : earlier_set = ao_ref_alias_set (&lhs_ref);
889 4175922 : earlier_base_set = ao_ref_base_alias_set (&lhs_ref);
890 : }
891 :
892 : /* We could do something fairly complex and look through PHIs
893 : like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
894 : the effort.
895 :
896 : Look at all the immediate uses of the VDEF (which are obviously
897 : dominated by STMT). See if one or more stores 0 into the same
898 : memory locations a STMT, if so remove the immediate use statements. */
899 4234102 : tree defvar = gimple_vdef (stmt);
900 4234102 : imm_use_iterator ui;
901 4234102 : gimple *use_stmt;
902 13711807 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
903 : {
904 : /* Limit stmt walking. */
905 5264513 : if (++cnt > param_dse_max_alias_queries_per_store)
906 : break;
907 :
908 : /* If USE_STMT stores 0 into one or more of the same locations
909 : as STMT and STMT would kill USE_STMT, then we can just remove
910 : USE_STMT. */
911 5264513 : tree fndecl;
912 5264513 : if ((is_gimple_assign (use_stmt)
913 3716372 : && gimple_vdef (use_stmt)
914 3058663 : && (gimple_assign_single_p (use_stmt)
915 3058663 : && initializer_zerop (gimple_assign_rhs1 (use_stmt))))
916 7537741 : || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL)
917 160126 : && (fndecl = gimple_call_fndecl (use_stmt)) != NULL
918 160126 : && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
919 138991 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
920 21226 : && integer_zerop (gimple_call_arg (use_stmt, 1))))
921 : {
922 1461566 : ao_ref write;
923 :
924 1461566 : if (!initialize_ao_ref_for_dse (use_stmt, &write))
925 : break;
926 :
927 1440656 : if (valid_ao_ref_for_dse (&write)
928 1440656 : && stmt_kills_ref_p (stmt, &write))
929 : {
930 5411 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
931 5411 : if (is_gimple_assign (use_stmt))
932 : {
933 5361 : ao_ref lhs_ref;
934 5361 : ao_ref_init (&lhs_ref, gimple_assign_lhs (use_stmt));
935 5361 : if ((earlier_set == ao_ref_alias_set (&lhs_ref)
936 745 : || alias_set_subset_of (ao_ref_alias_set (&lhs_ref),
937 : earlier_set))
938 5521 : && (earlier_base_set == ao_ref_base_alias_set (&lhs_ref)
939 484 : || alias_set_subset_of
940 484 : (ao_ref_base_alias_set (&lhs_ref),
941 : earlier_base_set)))
942 4706 : delete_dead_or_redundant_assignment (&gsi, "redundant",
943 : need_eh_cleanup,
944 : need_ab_cleanup);
945 : }
946 50 : else if (is_gimple_call (use_stmt))
947 : {
948 50 : if ((earlier_set == 0
949 8 : || alias_set_subset_of (0, earlier_set))
950 50 : && (earlier_base_set == 0
951 0 : || alias_set_subset_of (0, earlier_base_set)))
952 42 : delete_dead_or_redundant_call (&gsi, "redundant");
953 : }
954 : else
955 0 : gcc_unreachable ();
956 : }
957 : }
958 4234102 : }
959 4234102 : }
960 :
961 : /* Return whether PHI contains ARG as an argument. */
962 :
963 : static bool
964 4247179 : contains_phi_arg (gphi *phi, tree arg)
965 : {
966 31715199 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
967 27718807 : if (gimple_phi_arg_def (phi, i) == arg)
968 : return true;
969 : return false;
970 : }
971 :
972 : /* Hash map of the memory use in a GIMPLE assignment to its
973 : data reference. If NULL data-ref analysis isn't used. */
974 : static hash_map<gimple *, data_reference_p> *dse_stmt_to_dr_map;
975 :
976 : /* A helper of dse_optimize_stmt.
977 : Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
978 : according to downstream uses and defs. Sets *BY_CLOBBER_P to true
979 : if only clobber statements influenced the classification result.
980 : Returns the classification. */
981 :
982 : static dse_store_status
983 41720654 : dse_classify_store (ao_ref *ref, gimple *stmt,
984 : bool byte_tracking_enabled, sbitmap live_bytes,
985 : bool *by_clobber_p, tree stop_at_vuse, int &cnt,
986 : bitmap visited)
987 : {
988 41720654 : gimple *temp;
989 41720654 : std::unique_ptr<data_reference, void(*)(data_reference_p)>
990 41720654 : dra (nullptr, free_data_ref);
991 :
992 41720654 : if (by_clobber_p)
993 41128038 : *by_clobber_p = true;
994 :
995 : /* Find the first dominated statement that clobbers (part of) the
996 : memory stmt stores to with no intermediate statement that may use
997 : part of the memory stmt stores. That is, find a store that may
998 : prove stmt to be a dead store. */
999 : temp = stmt;
1000 534920260 : do
1001 : {
1002 288320457 : gimple *use_stmt;
1003 288320457 : imm_use_iterator ui;
1004 288320457 : bool fail = false;
1005 288320457 : tree defvar;
1006 :
1007 288320457 : if (gimple_code (temp) == GIMPLE_PHI)
1008 : {
1009 19837801 : defvar = PHI_RESULT (temp);
1010 19837801 : bitmap_set_bit (visited, SSA_NAME_VERSION (defvar));
1011 : }
1012 : else
1013 536965312 : defvar = gimple_vdef (temp);
1014 :
1015 288320457 : auto_vec<gimple *, 10> defs;
1016 288320457 : gphi *first_phi_def = NULL;
1017 288320457 : gphi *last_phi_def = NULL;
1018 :
1019 288320457 : auto_vec<tree, 10> worklist;
1020 288320457 : worklist.quick_push (defvar);
1021 :
1022 292374515 : do
1023 : {
1024 292374515 : defvar = worklist.pop ();
1025 : /* If we're instructed to stop walking at region boundary, do so. */
1026 292374515 : if (defvar == stop_at_vuse)
1027 : return DSE_STORE_LIVE;
1028 :
1029 292354661 : use_operand_p usep;
1030 919071421 : FOR_EACH_IMM_USE_FAST (usep, ui, defvar)
1031 : {
1032 363445034 : use_stmt = USE_STMT (usep);
1033 :
1034 : /* Limit stmt walking. */
1035 363445034 : if (++cnt > param_dse_max_alias_queries_per_store)
1036 : {
1037 : fail = true;
1038 : break;
1039 : }
1040 :
1041 : /* In simple cases we can look through PHI nodes, but we
1042 : have to be careful with loops and with memory references
1043 : containing operands that are also operands of PHI nodes.
1044 : See gcc.c-torture/execute/20051110-*.c. */
1045 363166641 : if (gphi *phi = dyn_cast <gphi *> (use_stmt))
1046 : {
1047 : /* Look through single-argument PHIs. */
1048 40595364 : if (gimple_phi_num_args (phi) == 1)
1049 4745923 : worklist.safe_push (gimple_phi_result (phi));
1050 : else
1051 : {
1052 : /* If we visit this PHI by following a backedge then we
1053 : have to make sure ref->ref only refers to SSA names
1054 : that are invariant with respect to the loop
1055 : represented by this PHI node. We handle irreducible
1056 : regions by relying on backedge marking and identifying
1057 : the head of the (sub-)region. */
1058 35849441 : edge e = gimple_phi_arg_edge
1059 35849441 : (phi, PHI_ARG_INDEX_FROM_USE (usep));
1060 35849441 : if (e->flags & EDGE_DFS_BACK)
1061 : {
1062 3215427 : basic_block rgn_head
1063 3215427 : = nearest_common_dominator (CDI_DOMINATORS,
1064 : gimple_bb (phi),
1065 : e->src);
1066 3215427 : if (!for_each_index (ref->ref
1067 : ? &ref->ref : &ref->base,
1068 : check_name, rgn_head))
1069 1479187 : return DSE_STORE_LIVE;
1070 : }
1071 : /* If we already visited this PHI ignore it for further
1072 : processing. But note we have to check each incoming
1073 : edge above. */
1074 68740508 : if (!bitmap_bit_p (visited,
1075 34370254 : SSA_NAME_VERSION (PHI_RESULT (phi))))
1076 : {
1077 25552347 : defs.safe_push (phi);
1078 25552347 : if (!first_phi_def)
1079 21522848 : first_phi_def = phi;;
1080 : last_phi_def = phi;
1081 : }
1082 : }
1083 : }
1084 : /* If the statement is a use the store is not dead. */
1085 322571277 : else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
1086 : {
1087 27336725 : if (dse_stmt_to_dr_map
1088 5983728 : && ref->ref
1089 33214955 : && is_gimple_assign (use_stmt))
1090 : {
1091 1193554 : if (!dra)
1092 1188479 : dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
1093 : false, false));
1094 1193554 : bool existed_p;
1095 1193554 : data_reference_p &drb
1096 1193554 : = dse_stmt_to_dr_map->get_or_insert (use_stmt,
1097 : &existed_p);
1098 1193554 : if (!existed_p)
1099 726821 : drb = create_data_ref (NULL, NULL,
1100 : gimple_assign_rhs1 (use_stmt),
1101 : use_stmt, false, false);
1102 1193554 : if (!dr_may_alias_p (dra.get (), drb, NULL))
1103 : {
1104 18124 : if (gimple_vdef (use_stmt))
1105 18 : defs.safe_push (use_stmt);
1106 9062 : continue;
1107 : }
1108 : }
1109 :
1110 : /* Handle common cases where we can easily build an ao_ref
1111 : structure for USE_STMT and in doing so we find that the
1112 : references hit non-live bytes and thus can be ignored.
1113 :
1114 : TODO: We can also use modref summary to handle calls. */
1115 27327663 : if (byte_tracking_enabled
1116 27327663 : && is_gimple_assign (use_stmt))
1117 : {
1118 4994763 : ao_ref use_ref;
1119 4994763 : ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt));
1120 4994763 : if (valid_ao_ref_for_dse (&use_ref)
1121 4974387 : && operand_equal_p (use_ref.base, ref->base,
1122 : OEP_ADDRESS_OF)
1123 8600004 : && !live_bytes_read (&use_ref, ref, live_bytes))
1124 : {
1125 : /* If this is a store, remember it as we possibly
1126 : need to walk the defs uses. */
1127 4616 : if (gimple_vdef (use_stmt))
1128 424 : defs.safe_push (use_stmt);
1129 2308 : continue;
1130 : }
1131 : }
1132 :
1133 : fail = true;
1134 : break;
1135 : }
1136 : /* We have visited ourselves already so ignore STMT for the
1137 : purpose of chaining. */
1138 295234552 : else if (use_stmt == stmt)
1139 : ;
1140 : /* If this is a store, remember it as we possibly need to walk the
1141 : defs uses. */
1142 924654361 : else if (gimple_vdef (use_stmt))
1143 253475582 : defs.safe_push (use_stmt);
1144 1479187 : }
1145 : }
1146 581750948 : while (!fail && !worklist.is_empty ());
1147 :
1148 286821416 : if (fail)
1149 : {
1150 : /* STMT might be partially dead and we may be able to reduce
1151 : how many memory locations it stores into. */
1152 27603748 : if (byte_tracking_enabled && !gimple_clobber_p (stmt))
1153 24844075 : return DSE_STORE_MAYBE_PARTIAL_DEAD;
1154 : return DSE_STORE_LIVE;
1155 : }
1156 :
1157 : /* If we didn't find any definition this means the store is dead
1158 : if it isn't a store to global reachable memory. In this case
1159 : just pretend the stmt makes itself dead. Otherwise fail. */
1160 259217668 : if (defs.is_empty ())
1161 : {
1162 2655150 : if (ref_may_alias_global_p (ref, false))
1163 : {
1164 39886 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (defvar));
1165 : /* Assume that BUILT_IN_UNREACHABLE and BUILT_IN_UNREACHABLE_TRAP
1166 : do not need to keep (global) memory side-effects live.
1167 : We do not have virtual operands on BUILT_IN_UNREACHABLE
1168 : but we can do poor mans reachability when the last
1169 : definition we want to elide is in the block that ends
1170 : in such a call. */
1171 39886 : if (EDGE_COUNT (def_bb->succs) == 0)
1172 54548 : if (gcall *last = dyn_cast <gcall *> (*gsi_last_bb (def_bb)))
1173 632 : if (gimple_call_builtin_p (last, BUILT_IN_UNREACHABLE)
1174 632 : || gimple_call_builtin_p (last,
1175 : BUILT_IN_UNREACHABLE_TRAP))
1176 : {
1177 430 : if (by_clobber_p)
1178 430 : *by_clobber_p = false;
1179 430 : return DSE_STORE_DEAD;
1180 : }
1181 39456 : return DSE_STORE_LIVE;
1182 : }
1183 :
1184 2615264 : if (by_clobber_p)
1185 2611881 : *by_clobber_p = false;
1186 2615264 : return DSE_STORE_DEAD;
1187 : }
1188 :
1189 : /* Process defs and remove those we need not process further. */
1190 530301852 : for (unsigned i = 0; i < defs.length ();)
1191 : {
1192 273802989 : gimple *def = defs[i];
1193 273802989 : gimple *use_stmt;
1194 273802989 : use_operand_p use_p;
1195 273802989 : tree vdef = (gimple_code (def) == GIMPLE_PHI
1196 297289761 : ? gimple_phi_result (def) : gimple_vdef (def));
1197 273802989 : gphi *phi_def;
1198 : /* If the path to check starts with a kill we do not need to
1199 : process it further.
1200 : ??? With byte tracking we need only kill the bytes currently
1201 : live. */
1202 273802989 : if (stmt_kills_ref_p (def, ref))
1203 : {
1204 2497362 : if (by_clobber_p && !gimple_clobber_p (def))
1205 613533 : *by_clobber_p = false;
1206 2497362 : defs.unordered_remove (i);
1207 : }
1208 : /* If the path ends here we do not need to process it further.
1209 : This for example happens with calls to noreturn functions. */
1210 271305627 : else if (has_zero_uses (vdef))
1211 : {
1212 : /* But if the store is to global memory it is definitely
1213 : not dead. */
1214 2768020 : if (ref_may_alias_global_p (ref, false))
1215 63655 : return DSE_STORE_LIVE;
1216 2704365 : defs.unordered_remove (i);
1217 : }
1218 : /* In addition to kills we can remove defs whose only use
1219 : is another def in defs. That can only ever be PHIs of which
1220 : we track two for simplicity reasons, the first and last in
1221 : {first,last}_phi_def (we fail for multiple PHIs anyways).
1222 : We can also ignore defs that feed only into
1223 : already visited PHIs. */
1224 268537607 : else if (single_imm_use (vdef, &use_p, &use_stmt)
1225 268537607 : && (use_stmt == first_phi_def
1226 232363246 : || use_stmt == last_phi_def
1227 232243562 : || (gimple_code (use_stmt) == GIMPLE_PHI
1228 15018272 : && bitmap_bit_p (visited,
1229 15018272 : SSA_NAME_VERSION
1230 : (PHI_RESULT (use_stmt))))))
1231 : {
1232 6197124 : defs.unordered_remove (i);
1233 6197124 : if (def == first_phi_def)
1234 : first_phi_def = NULL;
1235 5538296 : else if (def == last_phi_def)
1236 240729 : last_phi_def = NULL;
1237 : }
1238 : /* If def is a PHI and one of its arguments is another PHI node still
1239 : in consideration we can defer processing it. */
1240 262340483 : else if ((phi_def = dyn_cast <gphi *> (def))
1241 22623704 : && ((last_phi_def
1242 22623704 : && phi_def != last_phi_def
1243 2246267 : && contains_phi_arg (phi_def,
1244 : gimple_phi_result (last_phi_def)))
1245 22495094 : || (first_phi_def
1246 22495094 : && phi_def != first_phi_def
1247 2000912 : && contains_phi_arg
1248 2000912 : (phi_def, gimple_phi_result (first_phi_def)))))
1249 : {
1250 250787 : defs.unordered_remove (i);
1251 250787 : if (phi_def == first_phi_def)
1252 : first_phi_def = NULL;
1253 174290 : else if (phi_def == last_phi_def)
1254 240729 : last_phi_def = NULL;
1255 : }
1256 : else
1257 262089696 : ++i;
1258 : }
1259 :
1260 : /* If all defs kill the ref we are done. */
1261 298219517 : if (defs.is_empty ())
1262 : return DSE_STORE_DEAD;
1263 : /* If more than one def survives we have to analyze multiple
1264 : paths. We can handle this by recursing, sharing 'visited'
1265 : to avoid redundant work and limiting it by shared 'cnt'.
1266 : For now do not bother with byte-tracking in this case. */
1267 256863164 : while (defs.length () > 1)
1268 : {
1269 10210386 : if (dse_classify_store (ref, defs.last (), false, NULL,
1270 : by_clobber_p, stop_at_vuse, cnt,
1271 : visited) != DSE_STORE_DEAD)
1272 : break;
1273 6336120 : byte_tracking_enabled = false;
1274 6336120 : defs.pop ();
1275 : }
1276 : /* If more than one def survives fail. */
1277 250527044 : if (defs.length () > 1)
1278 : {
1279 : /* STMT might be partially dead and we may be able to reduce
1280 : how many memory locations it stores into. */
1281 3874266 : if (byte_tracking_enabled && !gimple_clobber_p (stmt))
1282 1569372 : return DSE_STORE_MAYBE_PARTIAL_DEAD;
1283 : return DSE_STORE_LIVE;
1284 : }
1285 246652778 : temp = defs[0];
1286 :
1287 : /* Track partial kills. */
1288 246652778 : if (byte_tracking_enabled)
1289 : {
1290 186428939 : clear_bytes_written_by (live_bytes, temp, ref);
1291 186428939 : if (bitmap_empty_p (live_bytes))
1292 : {
1293 52975 : if (by_clobber_p && !gimple_clobber_p (temp))
1294 52813 : *by_clobber_p = false;
1295 52975 : return DSE_STORE_DEAD;
1296 : }
1297 : }
1298 288320457 : }
1299 : /* Continue walking until there are no more live bytes. */
1300 : while (1);
1301 41720654 : }
1302 :
1303 : dse_store_status
1304 31510268 : dse_classify_store (ao_ref *ref, gimple *stmt,
1305 : bool byte_tracking_enabled, sbitmap live_bytes,
1306 : bool *by_clobber_p, tree stop_at_vuse)
1307 : {
1308 31510268 : int cnt = 0;
1309 31510268 : auto_bitmap visited;
1310 31510268 : return dse_classify_store (ref, stmt, byte_tracking_enabled, live_bytes,
1311 31510268 : by_clobber_p, stop_at_vuse, cnt, visited);
1312 31510268 : }
1313 :
1314 :
1315 : /* Delete a dead call at GSI, which is mem* call of some kind. */
1316 : static void
1317 6739 : delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type)
1318 : {
1319 6739 : gimple *stmt = gsi_stmt (*gsi);
1320 6739 : if (dump_file && (dump_flags & TDF_DETAILS))
1321 : {
1322 18 : fprintf (dump_file, " Deleted %s call: ", type);
1323 18 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1324 18 : fprintf (dump_file, "\n");
1325 : }
1326 :
1327 6739 : basic_block bb = gimple_bb (stmt);
1328 6739 : tree lhs = gimple_call_lhs (stmt);
1329 6739 : if (lhs)
1330 : {
1331 1216 : tree ptr = gimple_call_arg (stmt, 0);
1332 1216 : gimple *new_stmt = gimple_build_assign (lhs, ptr);
1333 1216 : unlink_stmt_vdef (stmt);
1334 1216 : if (gsi_replace (gsi, new_stmt, true))
1335 390 : bitmap_set_bit (need_eh_cleanup, bb->index);
1336 : }
1337 : else
1338 : {
1339 : /* Then we need to fix the operand of the consuming stmt. */
1340 5523 : unlink_stmt_vdef (stmt);
1341 :
1342 : /* Remove the dead store. */
1343 5523 : if (gsi_remove (gsi, true))
1344 3 : bitmap_set_bit (need_eh_cleanup, bb->index);
1345 5523 : release_defs (stmt);
1346 : }
1347 6739 : }
1348 :
1349 : /* Delete a dead store at GSI, which is a gimple assignment. */
1350 :
1351 : void
1352 2161665 : delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi,
1353 : const char *type,
1354 : bitmap need_eh_cleanup,
1355 : bitmap need_ab_cleanup)
1356 : {
1357 2161665 : gimple *stmt = gsi_stmt (*gsi);
1358 2161665 : if (dump_file && (dump_flags & TDF_DETAILS))
1359 : {
1360 111 : fprintf (dump_file, " Deleted %s store: ", type);
1361 111 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1362 111 : fprintf (dump_file, "\n");
1363 : }
1364 :
1365 : /* Then we need to fix the operand of the consuming stmt. */
1366 2161665 : unlink_stmt_vdef (stmt);
1367 :
1368 : /* Remove the dead store. */
1369 2161665 : basic_block bb = gimple_bb (stmt);
1370 2161665 : if (need_ab_cleanup && stmt_can_make_abnormal_goto (stmt))
1371 4 : bitmap_set_bit (need_ab_cleanup, bb->index);
1372 2161665 : if (gsi_remove (gsi, true) && need_eh_cleanup)
1373 93 : bitmap_set_bit (need_eh_cleanup, bb->index);
1374 :
1375 : /* And release any SSA_NAMEs set in this statement back to the
1376 : SSA_NAME manager. */
1377 2161665 : release_defs (stmt);
1378 2161665 : }
1379 :
1380 : /* Try to prove, using modref summary, that all memory written to by a call is
1381 : dead and remove it. Assume that if return value is written to memory
1382 : it is already proved to be dead. */
1383 :
1384 : static bool
1385 17335145 : dse_optimize_call (gimple_stmt_iterator *gsi, sbitmap live_bytes)
1386 : {
1387 34480426 : gcall *stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1388 :
1389 17146643 : if (!stmt)
1390 : return false;
1391 :
1392 17146643 : tree callee = gimple_call_fndecl (stmt);
1393 :
1394 17146643 : if (!callee)
1395 : return false;
1396 :
1397 : /* Pure/const functions are optimized by normal DCE
1398 : or handled as store above. */
1399 16428604 : int flags = gimple_call_flags (stmt);
1400 16428604 : if ((flags & (ECF_PURE|ECF_CONST|ECF_NOVOPS))
1401 99 : && !(flags & (ECF_LOOPING_CONST_OR_PURE)))
1402 : return false;
1403 :
1404 16428602 : cgraph_node *node = cgraph_node::get (callee);
1405 16428602 : if (!node)
1406 : return false;
1407 :
1408 16418756 : if ((stmt_could_throw_p (cfun, stmt)
1409 7196438 : && !cfun->can_delete_dead_exceptions)
1410 18876692 : || ((gimple_call_flags (stmt) & ECF_NORETURN)
1411 2145982 : && gimple_call_ctrl_altering_p (stmt)))
1412 6884477 : return false;
1413 :
1414 : /* If return value is used the call is not dead. */
1415 9534279 : tree lhs = gimple_call_lhs (stmt);
1416 9534279 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
1417 : {
1418 2362839 : imm_use_iterator ui;
1419 2362839 : gimple *use_stmt;
1420 4917254 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, lhs)
1421 2506823 : if (!is_gimple_debug (use_stmt))
1422 2362839 : return false;
1423 : }
1424 :
1425 : /* Verify that there are no side-effects except for return value
1426 : and memory writes tracked by modref. */
1427 7219032 : modref_summary *summary = get_modref_function_summary (node);
1428 7219032 : if (!summary || !summary->try_dse)
1429 : return false;
1430 :
1431 71145 : bool by_clobber_p = false;
1432 :
1433 : /* Walk all memory writes and verify that they are dead. */
1434 215165 : for (auto base_node : summary->stores->bases)
1435 218112 : for (auto ref_node : base_node->refs)
1436 223358 : for (auto access_node : ref_node->accesses)
1437 : {
1438 73523 : tree arg = access_node.get_call_arg (stmt);
1439 :
1440 73523 : if (!arg || !POINTER_TYPE_P (TREE_TYPE (arg)))
1441 69783 : return false;
1442 :
1443 73522 : if (integer_zerop (arg)
1444 73534 : && !targetm.addr_space.zero_address_valid
1445 12 : (TYPE_ADDR_SPACE (TREE_TYPE (arg))))
1446 12 : continue;
1447 :
1448 73510 : ao_ref ref;
1449 :
1450 73510 : if (!access_node.get_ao_ref (stmt, &ref))
1451 : return false;
1452 73510 : ref.ref_alias_set = ref_node->ref;
1453 73510 : ref.base_alias_set = base_node->base;
1454 :
1455 73510 : bool byte_tracking_enabled
1456 73510 : = setup_live_bytes_from_ref (&ref, live_bytes);
1457 73510 : enum dse_store_status store_status;
1458 :
1459 73510 : store_status = dse_classify_store (&ref, stmt,
1460 : byte_tracking_enabled,
1461 : live_bytes, &by_clobber_p);
1462 73510 : if (store_status != DSE_STORE_DEAD)
1463 : return false;
1464 : }
1465 1362 : delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
1466 : need_ab_cleanup);
1467 1362 : return true;
1468 : }
1469 :
1470 : /* Attempt to eliminate dead stores in the statement referenced by BSI.
1471 :
1472 : A dead store is a store into a memory location which will later be
1473 : overwritten by another store without any intervening loads. In this
1474 : case the earlier store can be deleted.
1475 :
1476 : In our SSA + virtual operand world we use immediate uses of virtual
1477 : operands to detect dead stores. If a store's virtual definition
1478 : is used precisely once by a later store to the same location which
1479 : post dominates the first store, then the first store is dead. */
1480 :
1481 : static void
1482 55471214 : dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes)
1483 : {
1484 55471214 : gimple *stmt = gsi_stmt (*gsi);
1485 :
1486 : /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
1487 55471214 : if (gimple_has_volatile_ops (stmt)
1488 55471214 : && (!gimple_clobber_p (stmt)
1489 6539040 : || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
1490 53235563 : return;
1491 :
1492 48715118 : ao_ref ref;
1493 : /* If this is not a store we can still remove dead call using
1494 : modref summary. Note we specifically allow ref to be initialized
1495 : to a conservative may-def since we are looking for followup stores
1496 : to kill all of it. */
1497 48715118 : if (!initialize_ao_ref_for_dse (stmt, &ref, true))
1498 : {
1499 17296094 : dse_optimize_call (gsi, live_bytes);
1500 17296094 : return;
1501 : }
1502 :
1503 : /* We know we have virtual definitions. We can handle assignments and
1504 : some builtin calls. */
1505 31419024 : if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
1506 31419024 : && !gimple_call_ctrl_altering_p (stmt))
1507 : {
1508 464236 : tree fndecl = gimple_call_fndecl (stmt);
1509 464236 : switch (DECL_FUNCTION_CODE (fndecl))
1510 : {
1511 462546 : case BUILT_IN_MEMCPY:
1512 462546 : case BUILT_IN_MEMMOVE:
1513 462546 : case BUILT_IN_STRNCPY:
1514 462546 : case BUILT_IN_MEMSET:
1515 462546 : case BUILT_IN_MEMCPY_CHK:
1516 462546 : case BUILT_IN_MEMMOVE_CHK:
1517 462546 : case BUILT_IN_STRNCPY_CHK:
1518 462546 : case BUILT_IN_MEMSET_CHK:
1519 462546 : {
1520 : /* Occasionally calls with an explicit length of zero
1521 : show up in the IL. It's pointless to do analysis
1522 : on them, they're trivially dead. */
1523 462546 : tree size = gimple_call_arg (stmt, 2);
1524 462546 : if (integer_zerop (size))
1525 : {
1526 50 : delete_dead_or_redundant_call (gsi, "dead");
1527 50 : return;
1528 : }
1529 :
1530 : /* If this is a memset call that initializes an object
1531 : to zero, it may be redundant with an earlier memset
1532 : or empty CONSTRUCTOR of a larger object. */
1533 462496 : if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
1534 366109 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
1535 462799 : && integer_zerop (gimple_call_arg (stmt, 1)))
1536 56490 : dse_optimize_redundant_stores (stmt);
1537 :
1538 462496 : enum dse_store_status store_status;
1539 462496 : bool byte_tracking_enabled
1540 462496 : = setup_live_bytes_from_ref (&ref, live_bytes);
1541 462496 : store_status = dse_classify_store (&ref, stmt,
1542 : byte_tracking_enabled,
1543 : live_bytes);
1544 462496 : if (store_status == DSE_STORE_LIVE)
1545 : return;
1546 :
1547 152931 : if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
1548 : {
1549 146284 : maybe_trim_memstar_call (&ref, live_bytes, stmt);
1550 146284 : return;
1551 : }
1552 :
1553 6647 : if (store_status == DSE_STORE_DEAD)
1554 6647 : delete_dead_or_redundant_call (gsi, "dead");
1555 6647 : return;
1556 : }
1557 :
1558 1690 : case BUILT_IN_CALLOC:
1559 : /* We already know the arguments are integer constants. */
1560 1690 : dse_optimize_redundant_stores (stmt);
1561 1690 : return;
1562 :
1563 : default:
1564 : return;
1565 : }
1566 : }
1567 30954788 : else if (is_gimple_call (stmt)
1568 30954788 : && gimple_call_internal_p (stmt))
1569 : {
1570 116762 : switch (gimple_call_internal_fn (stmt))
1571 : {
1572 1299 : case IFN_LEN_STORE:
1573 1299 : case IFN_MASK_STORE:
1574 1299 : case IFN_MASK_LEN_STORE:
1575 1299 : {
1576 1299 : enum dse_store_status store_status;
1577 1299 : store_status = dse_classify_store (&ref, stmt, false, live_bytes);
1578 1299 : if (store_status == DSE_STORE_DEAD)
1579 0 : delete_dead_or_redundant_call (gsi, "dead");
1580 1299 : return;
1581 : }
1582 : default:;
1583 : }
1584 : }
1585 :
1586 30953489 : bool by_clobber_p = false;
1587 :
1588 : /* Check if this statement stores zero to a memory location,
1589 : and if there is a subsequent store of zero to the same
1590 : memory location. If so, remove the subsequent store. */
1591 30953489 : if (gimple_assign_single_p (stmt)
1592 30953489 : && initializer_zerop (gimple_assign_rhs1 (stmt)))
1593 4175922 : dse_optimize_redundant_stores (stmt);
1594 :
1595 : /* Self-assignments are zombies. */
1596 30953489 : if (is_gimple_assign (stmt)
1597 60485085 : && operand_equal_p (gimple_assign_rhs1 (stmt),
1598 29531596 : gimple_assign_lhs (stmt), 0))
1599 : ;
1600 : else
1601 : {
1602 30952078 : bool byte_tracking_enabled
1603 30952078 : = setup_live_bytes_from_ref (&ref, live_bytes);
1604 30952078 : enum dse_store_status store_status;
1605 30952078 : store_status = dse_classify_store (&ref, stmt,
1606 : byte_tracking_enabled,
1607 : live_bytes, &by_clobber_p);
1608 30952078 : if (store_status == DSE_STORE_LIVE)
1609 : return;
1610 :
1611 28493649 : if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
1612 : {
1613 26200003 : maybe_trim_partially_dead_store (&ref, live_bytes, stmt);
1614 26200003 : return;
1615 : }
1616 : }
1617 :
1618 : /* Now we know that use_stmt kills the LHS of stmt. */
1619 :
1620 : /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
1621 : another clobber stmt. */
1622 2295057 : if (gimple_clobber_p (stmt)
1623 2295057 : && !by_clobber_p)
1624 : return;
1625 :
1626 2244128 : if (is_gimple_call (stmt)
1627 2244128 : && (gimple_has_side_effects (stmt)
1628 44476 : || (stmt_could_throw_p (fun, stmt)
1629 5 : && !fun->can_delete_dead_exceptions)))
1630 : {
1631 : /* See if we can remove complete call. */
1632 39051 : if (dse_optimize_call (gsi, live_bytes))
1633 : return;
1634 : /* Make sure we do not remove a return slot we cannot reconstruct
1635 : later. */
1636 39033 : if (gimple_call_return_slot_opt_p (as_a <gcall *>(stmt))
1637 39033 : && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt)))
1638 14779 : || !poly_int_tree_p
1639 14779 : (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt))))))
1640 : return;
1641 30574 : if (dump_file && (dump_flags & TDF_DETAILS))
1642 : {
1643 1 : fprintf (dump_file, " Deleted dead store in call LHS: ");
1644 1 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1645 1 : fprintf (dump_file, "\n");
1646 : }
1647 30574 : gimple_call_set_lhs (stmt, NULL_TREE);
1648 30574 : update_stmt (stmt);
1649 : }
1650 2205077 : else if (!stmt_could_throw_p (fun, stmt)
1651 2205077 : || fun->can_delete_dead_exceptions)
1652 2155250 : delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
1653 : need_ab_cleanup);
1654 : }
1655 :
1656 : namespace {
1657 :
1658 : const pass_data pass_data_dse =
1659 : {
1660 : GIMPLE_PASS, /* type */
1661 : "dse", /* name */
1662 : OPTGROUP_NONE, /* optinfo_flags */
1663 : TV_TREE_DSE, /* tv_id */
1664 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1665 : 0, /* properties_provided */
1666 : 0, /* properties_destroyed */
1667 : 0, /* todo_flags_start */
1668 : 0, /* todo_flags_finish */
1669 : };
1670 :
1671 : class pass_dse : public gimple_opt_pass
1672 : {
1673 : public:
1674 1443835 : pass_dse (gcc::context *ctxt)
1675 2887670 : : gimple_opt_pass (pass_data_dse, ctxt), use_dr_analysis_p (false)
1676 : {}
1677 :
1678 : /* opt_pass methods: */
1679 1155068 : opt_pass * clone () final override { return new pass_dse (m_ctxt); }
1680 288767 : void set_pass_param (unsigned n, bool param) final override
1681 : {
1682 288767 : gcc_assert (n == 0);
1683 288767 : use_dr_analysis_p = param;
1684 288767 : }
1685 5600422 : bool gate (function *) final override { return flag_tree_dse != 0; }
1686 : unsigned int execute (function *) final override;
1687 :
1688 : private:
1689 : bool use_dr_analysis_p;
1690 : }; // class pass_dse
1691 :
1692 : unsigned int
1693 5575940 : pass_dse::execute (function *fun)
1694 : {
1695 5575940 : unsigned todo = 0;
1696 5575940 : bool released_def = false;
1697 :
1698 5575940 : need_eh_cleanup = BITMAP_ALLOC (NULL);
1699 5575940 : need_ab_cleanup = BITMAP_ALLOC (NULL);
1700 5575940 : auto_sbitmap live_bytes (param_dse_max_object_size);
1701 5575940 : if (flag_expensive_optimizations && use_dr_analysis_p)
1702 961521 : dse_stmt_to_dr_map = new hash_map<gimple *, data_reference_p>;
1703 :
1704 5575940 : renumber_gimple_stmt_uids (fun);
1705 :
1706 5575940 : calculate_dominance_info (CDI_DOMINATORS);
1707 :
1708 : /* Dead store elimination is fundamentally a reverse program order walk. */
1709 5575940 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
1710 5575940 : auto_bitmap exit_bbs;
1711 5575940 : bitmap_set_bit (exit_bbs, EXIT_BLOCK);
1712 5575940 : edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fun));
1713 5575940 : int n = rev_post_order_and_mark_dfs_back_seme (fun, entry,
1714 : exit_bbs, false, rpo, NULL);
1715 52680515 : for (int i = n; i != 0; --i)
1716 : {
1717 47104575 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);
1718 47104575 : gimple_stmt_iterator gsi;
1719 :
1720 94209150 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1721 : {
1722 339410540 : gimple *stmt = gsi_stmt (gsi);
1723 :
1724 464784482 : if (gimple_vdef (stmt))
1725 55471214 : dse_optimize_stmt (fun, &gsi, live_bytes);
1726 567878652 : else if (def_operand_p
1727 283939326 : def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
1728 : {
1729 : /* When we remove dead stores make sure to also delete trivially
1730 : dead SSA defs. */
1731 63777084 : if (has_zero_uses (DEF_FROM_PTR (def_p))
1732 2086562 : && !gimple_has_side_effects (stmt)
1733 2076558 : && !is_ctrl_altering_stmt (stmt)
1734 65851952 : && (!stmt_could_throw_p (fun, stmt)
1735 91471 : || fun->can_delete_dead_exceptions))
1736 : {
1737 1983516 : if (dump_file && (dump_flags & TDF_DETAILS))
1738 : {
1739 11 : fprintf (dump_file, " Deleted trivially dead stmt: ");
1740 11 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1741 11 : fprintf (dump_file, "\n");
1742 : }
1743 1983516 : if (gsi_remove (&gsi, true) && need_eh_cleanup)
1744 2 : bitmap_set_bit (need_eh_cleanup, bb->index);
1745 1983516 : release_defs (stmt);
1746 1983516 : released_def = true;
1747 : }
1748 : }
1749 339410540 : if (gsi_end_p (gsi))
1750 560868 : gsi = gsi_last_bb (bb);
1751 : else
1752 725645221 : gsi_prev (&gsi);
1753 : }
1754 47104575 : bool removed_phi = false;
1755 65941614 : for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
1756 : {
1757 18837039 : gphi *phi = si.phi ();
1758 18837039 : if (has_zero_uses (gimple_phi_result (phi)))
1759 : {
1760 214445 : if (dump_file && (dump_flags & TDF_DETAILS))
1761 : {
1762 0 : fprintf (dump_file, " Deleted trivially dead PHI: ");
1763 0 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
1764 0 : fprintf (dump_file, "\n");
1765 : }
1766 214445 : remove_phi_node (&si, true);
1767 214445 : removed_phi = true;
1768 214445 : released_def = true;
1769 : }
1770 : else
1771 18622594 : gsi_next (&si);
1772 : }
1773 47104575 : if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
1774 : todo |= TODO_cleanup_cfg;
1775 : }
1776 5575940 : free (rpo);
1777 :
1778 : /* Removal of stores may make some EH edges dead. Purge such edges from
1779 : the CFG as needed. */
1780 5575940 : if (!bitmap_empty_p (need_eh_cleanup))
1781 : {
1782 390 : gimple_purge_all_dead_eh_edges (need_eh_cleanup);
1783 390 : todo |= TODO_cleanup_cfg;
1784 : }
1785 5575940 : if (!bitmap_empty_p (need_ab_cleanup))
1786 : {
1787 4 : gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
1788 4 : todo |= TODO_cleanup_cfg;
1789 : }
1790 :
1791 5575940 : BITMAP_FREE (need_eh_cleanup);
1792 5575940 : BITMAP_FREE (need_ab_cleanup);
1793 :
1794 5575940 : if (released_def)
1795 599936 : free_numbers_of_iterations_estimates (fun);
1796 :
1797 5575940 : if (flag_expensive_optimizations && use_dr_analysis_p)
1798 : {
1799 1688342 : for (auto i = dse_stmt_to_dr_map->begin ();
1800 2415163 : i != dse_stmt_to_dr_map->end (); ++i)
1801 726821 : free_data_ref ((*i).second);
1802 1923042 : delete dse_stmt_to_dr_map;
1803 961521 : dse_stmt_to_dr_map = NULL;
1804 : }
1805 :
1806 5575940 : return todo;
1807 5575940 : }
1808 :
1809 : } // anon namespace
1810 :
1811 : gimple_opt_pass *
1812 288767 : make_pass_dse (gcc::context *ctxt)
1813 : {
1814 288767 : return new pass_dse (ctxt);
1815 : }
|
