Branch data Line data Source code
1 : : /* Dead and redundant store elimination
2 : : Copyright (C) 2004-2024 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 : : #define INCLUDE_MEMORY
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "rtl.h"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "tree-pass.h"
29 : : #include "ssa.h"
30 : : #include "gimple-pretty-print.h"
31 : : #include "fold-const.h"
32 : : #include "gimple-iterator.h"
33 : : #include "tree-cfg.h"
34 : : #include "tree-dfa.h"
35 : : #include "tree-cfgcleanup.h"
36 : : #include "alias.h"
37 : : #include "tree-ssa-loop.h"
38 : : #include "tree-ssa-dse.h"
39 : : #include "builtins.h"
40 : : #include "gimple-fold.h"
41 : : #include "gimplify.h"
42 : : #include "tree-eh.h"
43 : : #include "cfganal.h"
44 : : #include "cgraph.h"
45 : : #include "ipa-modref-tree.h"
46 : : #include "ipa-modref.h"
47 : : #include "target.h"
48 : : #include "tree-ssa-loop-niter.h"
49 : : #include "cfgloop.h"
50 : : #include "tree-data-ref.h"
51 : : #include "internal-fn.h"
52 : : #include "tree-ssa.h"
53 : :
54 : : /* This file implements dead store elimination.
55 : :
56 : : A dead store is a store into a memory location which will later be
57 : : overwritten by another store without any intervening loads. In this
58 : : case the earlier store can be deleted or trimmed if the store
59 : : was partially dead.
60 : :
61 : : A redundant store is a store into a memory location which stores
62 : : the exact same value as a prior store to the same memory location.
63 : : While this can often be handled by dead store elimination, removing
64 : : the redundant store is often better than removing or trimming the
65 : : dead store.
66 : :
67 : : In our SSA + virtual operand world we use immediate uses of virtual
68 : : operands to detect these cases. If a store's virtual definition
69 : : is used precisely once by a later store to the same location which
70 : : post dominates the first store, then the first store is dead. If
71 : : the data stored is the same, then the second store is redundant.
72 : :
73 : : The single use of the store's virtual definition ensures that
74 : : there are no intervening aliased loads and the requirement that
75 : : the second load post dominate the first ensures that if the earlier
76 : : store executes, then the later stores will execute before the function
77 : : exits.
78 : :
79 : : It may help to think of this as first moving the earlier store to
80 : : the point immediately before the later store. Again, the single
81 : : use of the virtual definition and the post-dominance relationship
82 : : ensure that such movement would be safe. Clearly if there are
83 : : back to back stores, then the second is makes the first dead. If
84 : : the second store stores the same value, then the second store is
85 : : redundant.
86 : :
87 : : Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
88 : : may also help in understanding this code since it discusses the
89 : : relationship between dead store and redundant load elimination. In
90 : : fact, they are the same transformation applied to different views of
91 : : the CFG. */
92 : :
93 : : static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *);
94 : :
95 : : /* Bitmap of blocks that have had EH statements cleaned. We should
96 : : remove their dead edges eventually. */
97 : : static bitmap need_eh_cleanup;
98 : : static bitmap need_ab_cleanup;
99 : :
100 : : /* STMT is a statement that may write into memory. Analyze it and
101 : : initialize WRITE to describe how STMT affects memory. When
102 : : MAY_DEF_OK is true then the function initializes WRITE to what
103 : : the stmt may define.
104 : :
105 : : Return TRUE if the statement was analyzed, FALSE otherwise.
106 : :
107 : : It is always safe to return FALSE. But typically better optimziation
108 : : can be achieved by analyzing more statements. */
109 : :
110 : : static bool
111 : 208780816 : initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write, bool may_def_ok = false)
112 : : {
113 : : /* It's advantageous to handle certain mem* functions. */
114 : 208780816 : if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
115 : : {
116 : 4469789 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
117 : : {
118 : 963648 : case BUILT_IN_MEMCPY:
119 : 963648 : case BUILT_IN_MEMMOVE:
120 : 963648 : case BUILT_IN_MEMSET:
121 : 963648 : case BUILT_IN_MEMCPY_CHK:
122 : 963648 : case BUILT_IN_MEMMOVE_CHK:
123 : 963648 : case BUILT_IN_MEMSET_CHK:
124 : 963648 : case BUILT_IN_STRNCPY:
125 : 963648 : case BUILT_IN_STRNCPY_CHK:
126 : 963648 : {
127 : 963648 : tree size = gimple_call_arg (stmt, 2);
128 : 963648 : tree ptr = gimple_call_arg (stmt, 0);
129 : 963648 : ao_ref_init_from_ptr_and_size (write, ptr, size);
130 : 963648 : return true;
131 : : }
132 : :
133 : : /* A calloc call can never be dead, but it can make
134 : : subsequent stores redundant if they store 0 into
135 : : the same memory locations. */
136 : 2430 : case BUILT_IN_CALLOC:
137 : 2430 : {
138 : 2430 : tree nelem = gimple_call_arg (stmt, 0);
139 : 2430 : tree selem = gimple_call_arg (stmt, 1);
140 : 2430 : tree lhs;
141 : 2430 : if (TREE_CODE (nelem) == INTEGER_CST
142 : 1918 : && TREE_CODE (selem) == INTEGER_CST
143 : 4208 : && (lhs = gimple_call_lhs (stmt)) != NULL_TREE)
144 : : {
145 : 1775 : tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem),
146 : : nelem, selem);
147 : 1775 : ao_ref_init_from_ptr_and_size (write, lhs, size);
148 : 1775 : return true;
149 : : }
150 : : }
151 : :
152 : : default:
153 : : break;
154 : : }
155 : : }
156 : 204311027 : else if (is_gimple_call (stmt)
157 : 204311027 : && gimple_call_internal_p (stmt))
158 : : {
159 : 183486 : switch (gimple_call_internal_fn (stmt))
160 : : {
161 : 2232 : case IFN_LEN_STORE:
162 : 2232 : case IFN_MASK_STORE:
163 : 2232 : case IFN_MASK_LEN_STORE:
164 : 2232 : {
165 : 2232 : internal_fn ifn = gimple_call_internal_fn (stmt);
166 : 2232 : int stored_value_index = internal_fn_stored_value_index (ifn);
167 : 2232 : int len_index = internal_fn_len_index (ifn);
168 : 2232 : if (ifn == IFN_LEN_STORE)
169 : : {
170 : 0 : tree len = gimple_call_arg (stmt, len_index);
171 : 0 : tree bias = gimple_call_arg (stmt, len_index + 1);
172 : 0 : if (tree_fits_uhwi_p (len))
173 : : {
174 : 0 : ao_ref_init_from_ptr_and_size (write,
175 : : gimple_call_arg (stmt, 0),
176 : : int_const_binop (MINUS_EXPR,
177 : : len, bias));
178 : 0 : return true;
179 : : }
180 : : }
181 : : /* We cannot initialize a must-def ao_ref (in all cases) but we
182 : : can provide a may-def variant. */
183 : 2232 : if (may_def_ok)
184 : : {
185 : 2193 : ao_ref_init_from_ptr_and_size (
186 : : write, gimple_call_arg (stmt, 0),
187 : 2193 : TYPE_SIZE_UNIT (
188 : : TREE_TYPE (gimple_call_arg (stmt, stored_value_index))));
189 : 2193 : return true;
190 : : }
191 : : break;
192 : : }
193 : : default:;
194 : : }
195 : : }
196 : 207813200 : if (tree lhs = gimple_get_lhs (stmt))
197 : : {
198 : 194870872 : if (TREE_CODE (lhs) != SSA_NAME
199 : 194870872 : && (may_def_ok || !stmt_could_throw_p (cfun, stmt)))
200 : : {
201 : 180068549 : ao_ref_init (write, lhs);
202 : 180068549 : return true;
203 : : }
204 : : }
205 : : return false;
206 : : }
207 : :
208 : : /* Given REF from the alias oracle, return TRUE if it is a valid
209 : : kill memory reference for dead store elimination, false otherwise.
210 : :
211 : : In particular, the reference must have a known base, known maximum
212 : : size, start at a byte offset and have a size that is one or more
213 : : bytes. */
214 : :
215 : : static bool
216 : 150786726 : valid_ao_ref_kill_for_dse (ao_ref *ref)
217 : : {
218 : 150786726 : return (ao_ref_base (ref)
219 : 150786726 : && known_size_p (ref->max_size)
220 : 150560926 : && maybe_ne (ref->size, 0)
221 : 150557852 : && known_eq (ref->max_size, ref->size)
222 : 300871218 : && known_ge (ref->offset, 0));
223 : : }
224 : :
225 : : /* Given REF from the alias oracle, return TRUE if it is a valid
226 : : load or store memory reference for dead store elimination, false otherwise.
227 : :
228 : : Unlike for valid_ao_ref_kill_for_dse we can accept writes where max_size
229 : : is not same as size since we can handle conservatively the larger range. */
230 : :
231 : : static bool
232 : 35150694 : valid_ao_ref_for_dse (ao_ref *ref)
233 : : {
234 : 35150694 : return (ao_ref_base (ref)
235 : 35150694 : && known_size_p (ref->max_size)
236 : 69934909 : && known_ge (ref->offset, 0));
237 : : }
238 : :
239 : : /* Initialize OFFSET and SIZE to a range known to contain REF
240 : : where the boundaries are divisible by BITS_PER_UNIT (bit still in bits).
241 : : Return false if this is impossible. */
242 : :
243 : : static bool
244 : 96853308 : get_byte_aligned_range_containing_ref (ao_ref *ref, poly_int64 *offset,
245 : : HOST_WIDE_INT *size)
246 : : {
247 : 0 : if (!known_size_p (ref->max_size))
248 : : return false;
249 : 96853308 : *offset = aligned_lower_bound (ref->offset, BITS_PER_UNIT);
250 : 96853308 : poly_int64 end = aligned_upper_bound (ref->offset + ref->max_size,
251 : : BITS_PER_UNIT);
252 : 96853308 : return (end - *offset).is_constant (size);
253 : : }
254 : :
255 : : /* Initialize OFFSET and SIZE to a range known to be contained REF
256 : : where the boundaries are divisible by BITS_PER_UNIT (but still in bits).
257 : : Return false if this is impossible. */
258 : :
259 : : static bool
260 : 89622316 : get_byte_aligned_range_contained_in_ref (ao_ref *ref, poly_int64 *offset,
261 : : HOST_WIDE_INT *size)
262 : : {
263 : 89622316 : if (!known_size_p (ref->size)
264 : 89622316 : || !known_eq (ref->size, ref->max_size))
265 : : return false;
266 : 89622316 : *offset = aligned_upper_bound (ref->offset, BITS_PER_UNIT);
267 : 89622316 : poly_int64 end = aligned_lower_bound (ref->offset + ref->max_size,
268 : : BITS_PER_UNIT);
269 : : /* For bit accesses we can get -1 here, but also 0 sized kill is not
270 : : useful. */
271 : 89622316 : if (!known_gt (end, *offset))
272 : : return false;
273 : 89556502 : return (end - *offset).is_constant (size);
274 : : }
275 : :
276 : : /* Compute byte range (returned iN REF_OFFSET and RET_SIZE) for access COPY
277 : : inside REF. If KILL is true, then COPY represent a kill and the byte range
278 : : needs to be fully contained in bit range given by COPY. If KILL is false
279 : : then the byte range returned must contain the range of COPY. */
280 : :
281 : : static bool
282 : 93270719 : get_byte_range (ao_ref *copy, ao_ref *ref, bool kill,
283 : : HOST_WIDE_INT *ret_offset, HOST_WIDE_INT *ret_size)
284 : : {
285 : 93270719 : HOST_WIDE_INT copy_size, ref_size;
286 : 93270719 : poly_int64 copy_offset, ref_offset;
287 : 93270719 : HOST_WIDE_INT diff;
288 : :
289 : : /* First translate from bits to bytes, rounding to bigger or smaller ranges
290 : : as needed. Kills needs to be always rounded to smaller ranges while
291 : : uses and stores to larger ranges. */
292 : 93270719 : if (kill)
293 : : {
294 : 89622316 : if (!get_byte_aligned_range_contained_in_ref (copy, ©_offset,
295 : : ©_size))
296 : : return false;
297 : : }
298 : : else
299 : : {
300 : 89033247 : if (!get_byte_aligned_range_containing_ref (copy, ©_offset,
301 : : ©_size))
302 : : return false;
303 : : }
304 : :
305 : 93204905 : if (!get_byte_aligned_range_containing_ref (ref, &ref_offset, &ref_size)
306 : 93204905 : || !ordered_p (copy_offset, ref_offset))
307 : : return false;
308 : :
309 : : /* Switch sizes from bits to bytes so we do not need to care about
310 : : overflows. Offset calculation needs to stay in bits until we compute
311 : : the difference and can switch to HOST_WIDE_INT. */
312 : 93204905 : copy_size /= BITS_PER_UNIT;
313 : 93204905 : ref_size /= BITS_PER_UNIT;
314 : :
315 : : /* If COPY starts before REF, then reset the beginning of
316 : : COPY to match REF and decrease the size of COPY by the
317 : : number of bytes removed from COPY. */
318 : 93204905 : if (maybe_lt (copy_offset, ref_offset))
319 : : {
320 : 8250858 : if (!(ref_offset - copy_offset).is_constant (&diff)
321 : 8250858 : || copy_size < diff / BITS_PER_UNIT)
322 : : return false;
323 : 2451288 : copy_size -= diff / BITS_PER_UNIT;
324 : 2451288 : copy_offset = ref_offset;
325 : : }
326 : :
327 : 87405335 : if (!(copy_offset - ref_offset).is_constant (&diff)
328 : 87405335 : || ref_size <= diff / BITS_PER_UNIT)
329 : : return false;
330 : :
331 : : /* If COPY extends beyond REF, chop off its size appropriately. */
332 : 7885875 : HOST_WIDE_INT limit = ref_size - diff / BITS_PER_UNIT;
333 : :
334 : 7885875 : if (copy_size > limit)
335 : 1122932 : copy_size = limit;
336 : 7885875 : *ret_size = copy_size;
337 : 7885875 : if (!(copy_offset - ref_offset).is_constant (ret_offset))
338 : : return false;
339 : 7885875 : *ret_offset /= BITS_PER_UNIT;
340 : 7885875 : return true;
341 : : }
342 : :
343 : : /* Update LIVE_BYTES tracking REF for write to WRITE:
344 : : Verify we have the same base memory address, the write
345 : : has a known size and overlaps with REF. */
346 : : static void
347 : 150786726 : clear_live_bytes_for_ref (sbitmap live_bytes, ao_ref *ref, ao_ref *write)
348 : : {
349 : 150786726 : HOST_WIDE_INT start, size;
350 : :
351 : 150786726 : if (valid_ao_ref_kill_for_dse (write)
352 : 150084216 : && operand_equal_p (write->base, ref->base, OEP_ADDRESS_OF)
353 : 240409042 : && get_byte_range (write, ref, true, &start, &size))
354 : 4237472 : bitmap_clear_range (live_bytes, start, size);
355 : 150786726 : }
356 : :
357 : : /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base
358 : : address written by STMT must match the one found in REF, which must
359 : : have its base address previously initialized.
360 : :
361 : : This routine must be conservative. If we don't know the offset or
362 : : actual size written, assume nothing was written. */
363 : :
364 : : static void
365 : 162414907 : clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref)
366 : : {
367 : 162414907 : ao_ref write;
368 : :
369 : 162414907 : if (gcall *call = dyn_cast <gcall *> (stmt))
370 : : {
371 : 4505086 : bool interposed;
372 : 4505086 : modref_summary *summary = get_modref_function_summary (call, &interposed);
373 : :
374 : 4505086 : if (summary && !interposed)
375 : 406676 : for (auto kill : summary->kills)
376 : 47716 : if (kill.get_ao_ref (as_a <gcall *> (stmt), &write))
377 : 47692 : clear_live_bytes_for_ref (live_bytes, ref, &write);
378 : : }
379 : 162414907 : if (!initialize_ao_ref_for_dse (stmt, &write))
380 : 11675873 : return;
381 : :
382 : 150739034 : clear_live_bytes_for_ref (live_bytes, ref, &write);
383 : : }
384 : :
385 : : /* REF is a memory write. Extract relevant information from it and
386 : : initialize the LIVE_BYTES bitmap. If successful, return TRUE.
387 : : Otherwise return FALSE. */
388 : :
389 : : static bool
390 : 29128135 : setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes)
391 : : {
392 : 29128135 : HOST_WIDE_INT const_size;
393 : 29128135 : if (valid_ao_ref_for_dse (ref)
394 : 28776855 : && ((aligned_upper_bound (ref->offset + ref->max_size, BITS_PER_UNIT)
395 : 28776855 : - aligned_lower_bound (ref->offset,
396 : 28776855 : BITS_PER_UNIT)).is_constant (&const_size))
397 : 28776855 : && (const_size / BITS_PER_UNIT <= param_dse_max_object_size)
398 : 57529264 : && const_size > 1)
399 : : {
400 : 28400919 : bitmap_clear (live_bytes);
401 : 28400919 : bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT);
402 : 28400919 : return true;
403 : : }
404 : : return false;
405 : : }
406 : :
407 : : /* Compute the number of stored bytes that we can trim from the head and
408 : : tail of REF. LIVE is the bitmap of stores to REF that are still live.
409 : :
410 : : Store the number of bytes trimmed from the head and tail in TRIM_HEAD
411 : : and TRIM_TAIL respectively.
412 : :
413 : : STMT is the statement being trimmed and is used for debugging dump
414 : : output only. */
415 : :
416 : : static void
417 : 551076 : compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail,
418 : : gimple *stmt)
419 : : {
420 : 551076 : *trim_head = 0;
421 : 551076 : *trim_tail = 0;
422 : :
423 : : /* We use bitmaps biased such that ref->offset is contained in bit zero and
424 : : the bitmap extends through ref->max_size, so we know that in the original
425 : : bitmap bits 0 .. ref->max_size were true. But we need to check that this
426 : : covers the bytes of REF exactly. */
427 : 551076 : const unsigned int align = known_alignment (ref->offset);
428 : 551076 : if ((align > 0 && align < BITS_PER_UNIT)
429 : 551076 : || !known_eq (ref->size, ref->max_size))
430 : 0 : return;
431 : :
432 : : /* Now identify how much, if any of the tail we can chop off. */
433 : 551076 : HOST_WIDE_INT const_size;
434 : 551076 : int last_live = bitmap_last_set_bit (live);
435 : 551076 : if (ref->size.is_constant (&const_size))
436 : : {
437 : 551076 : 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 : 551076 : *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 : 551076 : if (*trim_tail
449 : 11666 : && TYPE_SIZE_UNIT (TREE_TYPE (ref->base))
450 : 11666 : && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST
451 : 562741 : && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)),
452 : : last_orig) <= 0)
453 : 61 : *trim_tail = 0;
454 : : }
455 : :
456 : : /* Identify how much, if any of the head we can chop off. */
457 : 551076 : int first_orig = 0;
458 : 551076 : int first_live = bitmap_first_set_bit (live);
459 : 551076 : *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 : 551076 : unsigned int align_bits;
464 : 551076 : unsigned HOST_WIDE_INT bitpos;
465 : 466357 : if ((*trim_head || *trim_tail)
466 : 91689 : && last_live - first_live >= 2
467 : 90888 : && ao_ref_alignment (ref, &align_bits, &bitpos)
468 : 76021 : && align_bits >= 32
469 : 75684 : && bitpos == 0
470 : 623526 : && align_bits % BITS_PER_UNIT == 0)
471 : : {
472 : 72450 : unsigned int align_units = align_bits / BITS_PER_UNIT;
473 : 72450 : if (align_units > 16)
474 : 487 : align_units = 16;
475 : 73363 : while ((first_live | (align_units - 1)) > (unsigned int)last_live)
476 : 913 : align_units >>= 1;
477 : :
478 : 72450 : if (*trim_head)
479 : : {
480 : 66736 : unsigned int pos = first_live & (align_units - 1);
481 : 71921 : for (unsigned int i = 1; i <= align_units; i <<= 1)
482 : : {
483 : 71921 : unsigned int mask = ~(i - 1);
484 : 71921 : unsigned int bytes = align_units - (pos & mask);
485 : 71921 : if (wi::popcount (bytes) <= 1)
486 : : {
487 : 66736 : *trim_head &= mask;
488 : 66736 : break;
489 : : }
490 : : }
491 : : }
492 : :
493 : 72450 : if (*trim_tail)
494 : : {
495 : 7395 : unsigned int pos = last_live & (align_units - 1);
496 : 7687 : for (unsigned int i = 1; i <= align_units; i <<= 1)
497 : : {
498 : 7687 : int mask = i - 1;
499 : 7687 : unsigned int bytes = (pos | mask) + 1;
500 : 7687 : if ((last_live | mask) > (last_live + *trim_tail))
501 : : break;
502 : 7687 : if (wi::popcount (bytes) <= 1)
503 : : {
504 : 7395 : unsigned int extra = (last_live | mask) - last_live;
505 : 7395 : *trim_tail -= extra;
506 : 7395 : break;
507 : : }
508 : : }
509 : : }
510 : : }
511 : :
512 : 551076 : if ((*trim_head || *trim_tail) && dump_file && (dump_flags & TDF_DETAILS))
513 : : {
514 : 15 : fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ",
515 : : *trim_head, *trim_tail);
516 : 15 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
517 : 15 : 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 : 5459 : maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt)
530 : : {
531 : 5459 : int trim_head, trim_tail;
532 : 5459 : 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 : 5459 : 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 : 5457 : 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 : 5459 : }
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 : :
572 : : static void
573 : 413074 : maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt)
574 : : {
575 : 413074 : tree ctor = gimple_assign_rhs1 (stmt);
576 : :
577 : : /* This is the only case we currently handle. It actually seems to
578 : : catch most cases of actual interest. */
579 : 413074 : gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0);
580 : :
581 : 413074 : int head_trim = 0;
582 : 413074 : int tail_trim = 0;
583 : 413074 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
584 : :
585 : : /* Now we want to replace the constructor initializer
586 : : with memset (object + head_trim, 0, size - head_trim - tail_trim). */
587 : 413074 : if (head_trim || tail_trim)
588 : : {
589 : : /* We want &lhs for the MEM_REF expression. */
590 : 87215 : tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt));
591 : :
592 : 87215 : if (! is_gimple_min_invariant (lhs_addr))
593 : 15106 : return;
594 : :
595 : : /* The number of bytes for the new constructor. */
596 : 72109 : poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT);
597 : 72109 : poly_int64 count = ref_bytes - head_trim - tail_trim;
598 : :
599 : : /* And the new type for the CONSTRUCTOR. Essentially it's just
600 : : a char array large enough to cover the non-trimmed parts of
601 : : the original CONSTRUCTOR. Note we want explicit bounds here
602 : : so that we know how many bytes to clear when expanding the
603 : : CONSTRUCTOR. */
604 : 72109 : tree type = build_array_type_nelts (char_type_node, count);
605 : :
606 : : /* Build a suitable alias type rather than using alias set zero
607 : : to avoid pessimizing. */
608 : 72109 : tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt));
609 : :
610 : : /* Build a MEM_REF representing the whole accessed area, starting
611 : : at the first byte not trimmed. */
612 : 72109 : tree exp = fold_build2 (MEM_REF, type, lhs_addr,
613 : : build_int_cst (alias_type, head_trim));
614 : :
615 : : /* Now update STMT with a new RHS and LHS. */
616 : 72109 : gimple_assign_set_lhs (stmt, exp);
617 : 72109 : gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL));
618 : : }
619 : : }
620 : :
621 : : /* STMT is a memcpy, memmove or memset. Decrement the number of bytes
622 : : copied/set by DECREMENT. */
623 : : static void
624 : 886 : decrement_count (gimple *stmt, int decrement)
625 : : {
626 : 886 : tree *countp = gimple_call_arg_ptr (stmt, 2);
627 : 886 : gcc_assert (TREE_CODE (*countp) == INTEGER_CST);
628 : 1772 : *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp)
629 : 886 : - decrement));
630 : 886 : }
631 : :
632 : : static void
633 : 640 : increment_start_addr (gimple *stmt, tree *where, int increment)
634 : : {
635 : 640 : if (tree lhs = gimple_call_lhs (stmt))
636 : 6 : if (where == gimple_call_arg_ptr (stmt, 0))
637 : : {
638 : 6 : gassign *newop = gimple_build_assign (lhs, unshare_expr (*where));
639 : 6 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
640 : 6 : gsi_insert_after (&gsi, newop, GSI_SAME_STMT);
641 : 6 : gimple_call_set_lhs (stmt, NULL_TREE);
642 : 6 : update_stmt (stmt);
643 : : }
644 : :
645 : 640 : if (TREE_CODE (*where) == SSA_NAME)
646 : : {
647 : 144 : tree tem = make_ssa_name (TREE_TYPE (*where));
648 : 144 : gassign *newop
649 : 144 : = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where,
650 : 144 : build_int_cst (sizetype, increment));
651 : 144 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
652 : 144 : gsi_insert_before (&gsi, newop, GSI_SAME_STMT);
653 : 144 : *where = tem;
654 : 144 : update_stmt (stmt);
655 : 144 : return;
656 : : }
657 : :
658 : 496 : *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node,
659 : : *where,
660 : : build_int_cst (ptr_type_node,
661 : : increment)));
662 : 496 : STRIP_USELESS_TYPE_CONVERSION (*where);
663 : : }
664 : :
665 : : /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
666 : : (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce
667 : : the amount of data it actually writes.
668 : :
669 : : Right now we only support trimming from the head or the tail of the
670 : : memory region. In theory we could split the mem* call, but it's
671 : : likely of marginal value. */
672 : :
673 : : static void
674 : 132543 : maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
675 : : {
676 : 132543 : int head_trim, tail_trim;
677 : 132543 : switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
678 : : {
679 : 4712 : case BUILT_IN_STRNCPY:
680 : 4712 : case BUILT_IN_STRNCPY_CHK:
681 : 4712 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
682 : 4712 : if (head_trim)
683 : : {
684 : : /* Head trimming of strncpy is only possible if we can
685 : : prove all bytes we would trim are non-zero (or we could
686 : : turn the strncpy into memset if there must be zero
687 : : among the head trimmed bytes). If we don't know anything
688 : : about those bytes, the presence or absence of '\0' bytes
689 : : in there will affect whether it acts for the non-trimmed
690 : : bytes as memset or memcpy/strncpy. */
691 : 68 : c_strlen_data lendata = { };
692 : 68 : int orig_head_trim = head_trim;
693 : 68 : tree srcstr = gimple_call_arg (stmt, 1);
694 : 68 : if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1)
695 : 68 : || !tree_fits_uhwi_p (lendata.minlen))
696 : 8 : head_trim = 0;
697 : 60 : else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim)
698 : : {
699 : 54 : head_trim = tree_to_uhwi (lendata.minlen);
700 : 54 : if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0)
701 : 0 : head_trim &= ~(UNITS_PER_WORD - 1);
702 : : }
703 : 68 : if (orig_head_trim != head_trim
704 : 62 : && dump_file
705 : 76 : && (dump_flags & TDF_DETAILS))
706 : 8 : fprintf (dump_file,
707 : : " Adjusting strncpy trimming to (head = %d,"
708 : : " tail = %d)\n", head_trim, tail_trim);
709 : : }
710 : 4712 : goto do_memcpy;
711 : :
712 : 92485 : case BUILT_IN_MEMCPY:
713 : 92485 : case BUILT_IN_MEMMOVE:
714 : 92485 : case BUILT_IN_MEMCPY_CHK:
715 : 92485 : case BUILT_IN_MEMMOVE_CHK:
716 : 92485 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
717 : :
718 : 97197 : do_memcpy:
719 : : /* Tail trimming is easy, we can just reduce the count. */
720 : 97197 : if (tail_trim)
721 : 254 : decrement_count (stmt, tail_trim);
722 : :
723 : : /* Head trimming requires adjusting all the arguments. */
724 : 97197 : if (head_trim)
725 : : {
726 : : /* For __*_chk need to adjust also the last argument. */
727 : 122 : if (gimple_call_num_args (stmt) == 4)
728 : : {
729 : 55 : tree size = gimple_call_arg (stmt, 3);
730 : 55 : if (!tree_fits_uhwi_p (size))
731 : : break;
732 : 7 : if (!integer_all_onesp (size))
733 : : {
734 : 7 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
735 : 7 : if (sz < (unsigned) head_trim)
736 : : break;
737 : 7 : tree arg = wide_int_to_tree (TREE_TYPE (size),
738 : 7 : sz - head_trim);
739 : 7 : gimple_call_set_arg (stmt, 3, arg);
740 : : }
741 : : }
742 : 74 : tree *dst = gimple_call_arg_ptr (stmt, 0);
743 : 74 : increment_start_addr (stmt, dst, head_trim);
744 : 74 : tree *src = gimple_call_arg_ptr (stmt, 1);
745 : 74 : increment_start_addr (stmt, src, head_trim);
746 : 74 : decrement_count (stmt, head_trim);
747 : : }
748 : : break;
749 : :
750 : 35346 : case BUILT_IN_MEMSET:
751 : 35346 : case BUILT_IN_MEMSET_CHK:
752 : 35346 : compute_trims (ref, live, &head_trim, &tail_trim, stmt);
753 : :
754 : : /* Tail trimming is easy, we can just reduce the count. */
755 : 35346 : if (tail_trim)
756 : 66 : decrement_count (stmt, tail_trim);
757 : :
758 : : /* Head trimming requires adjusting all the arguments. */
759 : 35346 : if (head_trim)
760 : : {
761 : : /* For __*_chk need to adjust also the last argument. */
762 : 492 : if (gimple_call_num_args (stmt) == 4)
763 : : {
764 : 7 : tree size = gimple_call_arg (stmt, 3);
765 : 7 : if (!tree_fits_uhwi_p (size))
766 : : break;
767 : 7 : if (!integer_all_onesp (size))
768 : : {
769 : 7 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
770 : 7 : if (sz < (unsigned) head_trim)
771 : : break;
772 : 7 : tree arg = wide_int_to_tree (TREE_TYPE (size),
773 : 7 : sz - head_trim);
774 : 7 : gimple_call_set_arg (stmt, 3, arg);
775 : : }
776 : : }
777 : 492 : tree *dst = gimple_call_arg_ptr (stmt, 0);
778 : 492 : increment_start_addr (stmt, dst, head_trim);
779 : 492 : decrement_count (stmt, head_trim);
780 : : }
781 : : break;
782 : :
783 : : default:
784 : : break;
785 : : }
786 : 132543 : }
787 : :
788 : : /* STMT is a memory write where one or more bytes written are dead stores.
789 : : REF is a representation of the memory written. LIVE is the bitmap of
790 : : stores to REF that are still live.
791 : :
792 : : Attempt to rewrite STMT so that it writes fewer memory locations. Right
793 : : now we only support trimming at the start or end of the memory region.
794 : : It's not clear how much there is to be gained by trimming from the middle
795 : : of the region. */
796 : :
797 : : static void
798 : 24616227 : maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt)
799 : : {
800 : 24616227 : if (is_gimple_assign (stmt)
801 : 24616227 : && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF)
802 : : {
803 : 23290707 : switch (gimple_assign_rhs_code (stmt))
804 : : {
805 : 413074 : case CONSTRUCTOR:
806 : 413074 : maybe_trim_constructor_store (ref, live, stmt);
807 : 413074 : break;
808 : 5459 : case COMPLEX_CST:
809 : 5459 : maybe_trim_complex_store (ref, live, stmt);
810 : 5459 : break;
811 : : default:
812 : : break;
813 : : }
814 : : }
815 : 24616227 : }
816 : :
817 : : /* Return TRUE if USE_REF reads bytes from LIVE where live is
818 : : derived from REF, a write reference.
819 : :
820 : : While this routine may modify USE_REF, it's passed by value, not
821 : : location. So callers do not see those modifications. */
822 : :
823 : : static bool
824 : 3648403 : live_bytes_read (ao_ref *use_ref, ao_ref *ref, sbitmap live)
825 : : {
826 : : /* We have already verified that USE_REF and REF hit the same object.
827 : : Now verify that there's actually an overlap between USE_REF and REF. */
828 : 3648403 : HOST_WIDE_INT start, size;
829 : 3648403 : if (get_byte_range (use_ref, ref, false, &start, &size))
830 : : {
831 : : /* If USE_REF covers all of REF, then it will hit one or more
832 : : live bytes. This avoids useless iteration over the bitmap
833 : : below. */
834 : 3648403 : if (start == 0 && known_eq (size * 8, ref->size))
835 : : return true;
836 : :
837 : : /* Now check if any of the remaining bits in use_ref are set in LIVE. */
838 : 995774 : return bitmap_bit_in_range_p (live, start, (start + size - 1));
839 : : }
840 : : return true;
841 : : }
842 : :
843 : : /* Callback for dse_classify_store calling for_each_index. Verify that
844 : : indices are invariant in the loop with backedge PHI in basic-block DATA. */
845 : :
846 : : static bool
847 : 1375679 : check_name (tree, tree *idx, void *data)
848 : : {
849 : 1375679 : basic_block phi_bb = (basic_block) data;
850 : 1375679 : if (TREE_CODE (*idx) == SSA_NAME
851 : 1236996 : && !SSA_NAME_IS_DEFAULT_DEF (*idx)
852 : 2551859 : && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)),
853 : : phi_bb))
854 : : return false;
855 : : return true;
856 : : }
857 : :
858 : : /* STMT stores the value 0 into one or more memory locations
859 : : (via memset, empty constructor, calloc call, etc).
860 : :
861 : : See if there is a subsequent store of the value 0 to one
862 : : or more of the same memory location(s). If so, the subsequent
863 : : store is redundant and can be removed.
864 : :
865 : : The subsequent stores could be via memset, empty constructors,
866 : : simple MEM stores, etc. */
867 : :
868 : : static void
869 : 3664951 : dse_optimize_redundant_stores (gimple *stmt)
870 : : {
871 : 3664951 : int cnt = 0;
872 : :
873 : : /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */
874 : 3664951 : alias_set_type earlier_set = 0;
875 : 3664951 : alias_set_type earlier_base_set = 0;
876 : 3664951 : if (is_gimple_assign (stmt))
877 : : {
878 : 3613356 : ao_ref lhs_ref;
879 : 3613356 : ao_ref_init (&lhs_ref, gimple_assign_lhs (stmt));
880 : 3613356 : earlier_set = ao_ref_alias_set (&lhs_ref);
881 : 3613356 : earlier_base_set = ao_ref_base_alias_set (&lhs_ref);
882 : : }
883 : :
884 : : /* We could do something fairly complex and look through PHIs
885 : : like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
886 : : the effort.
887 : :
888 : : Look at all the immediate uses of the VDEF (which are obviously
889 : : dominated by STMT). See if one or more stores 0 into the same
890 : : memory locations a STMT, if so remove the immediate use statements. */
891 : 3664951 : tree defvar = gimple_vdef (stmt);
892 : 3664951 : imm_use_iterator ui;
893 : 3664951 : gimple *use_stmt;
894 : 8164815 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
895 : : {
896 : : /* Limit stmt walking. */
897 : 4517795 : if (++cnt > param_dse_max_alias_queries_per_store)
898 : : break;
899 : :
900 : : /* If USE_STMT stores 0 into one or more of the same locations
901 : : as STMT and STMT would kill USE_STMT, then we can just remove
902 : : USE_STMT. */
903 : 4517795 : tree fndecl;
904 : 4517795 : if ((is_gimple_assign (use_stmt)
905 : 3151619 : && gimple_vdef (use_stmt)
906 : 2600313 : && (gimple_assign_single_p (use_stmt)
907 : 2600313 : && initializer_zerop (gimple_assign_rhs1 (use_stmt))))
908 : 6448970 : || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL)
909 : 131943 : && (fndecl = gimple_call_fndecl (use_stmt)) != NULL
910 : 131943 : && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
911 : 112908 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
912 : 19139 : && integer_zerop (gimple_call_arg (use_stmt, 1))))
913 : : {
914 : 1237104 : ao_ref write;
915 : :
916 : 1237104 : if (!initialize_ao_ref_for_dse (use_stmt, &write))
917 : : break;
918 : :
919 : 1219173 : if (valid_ao_ref_for_dse (&write)
920 : 1219173 : && stmt_kills_ref_p (stmt, &write))
921 : : {
922 : 5350 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
923 : 5350 : if (is_gimple_assign (use_stmt))
924 : : {
925 : 5300 : ao_ref lhs_ref;
926 : 5300 : ao_ref_init (&lhs_ref, gimple_assign_lhs (use_stmt));
927 : 5300 : if ((earlier_set == ao_ref_alias_set (&lhs_ref)
928 : 521 : || alias_set_subset_of (ao_ref_alias_set (&lhs_ref),
929 : : earlier_set))
930 : 5821 : && (earlier_base_set == ao_ref_base_alias_set (&lhs_ref)
931 : 993 : || alias_set_subset_of
932 : 993 : (ao_ref_base_alias_set (&lhs_ref),
933 : : earlier_base_set)))
934 : 5206 : delete_dead_or_redundant_assignment (&gsi, "redundant",
935 : : need_eh_cleanup,
936 : : need_ab_cleanup);
937 : : }
938 : 50 : else if (is_gimple_call (use_stmt))
939 : : {
940 : 50 : if ((earlier_set == 0
941 : 2 : || alias_set_subset_of (0, earlier_set))
942 : 51 : && (earlier_base_set == 0
943 : 1 : || alias_set_subset_of (0, earlier_base_set)))
944 : 49 : delete_dead_or_redundant_call (&gsi, "redundant");
945 : : }
946 : : else
947 : 0 : gcc_unreachable ();
948 : : }
949 : : }
950 : 3664951 : }
951 : 3664951 : }
952 : :
953 : : /* Return whether PHI contains ARG as an argument. */
954 : :
955 : : static bool
956 : 1483233 : contains_phi_arg (gphi *phi, tree arg)
957 : : {
958 : 12902638 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
959 : 11520569 : if (gimple_phi_arg_def (phi, i) == arg)
960 : : return true;
961 : : return false;
962 : : }
963 : :
964 : : /* Hash map of the memory use in a GIMPLE assignment to its
965 : : data reference. If NULL data-ref analysis isn't used. */
966 : : static hash_map<gimple *, data_reference_p> *dse_stmt_to_dr_map;
967 : :
968 : : /* A helper of dse_optimize_stmt.
969 : : Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
970 : : according to downstream uses and defs. Sets *BY_CLOBBER_P to true
971 : : if only clobber statements influenced the classification result.
972 : : Returns the classification. */
973 : :
974 : : dse_store_status
975 : 29146180 : dse_classify_store (ao_ref *ref, gimple *stmt,
976 : : bool byte_tracking_enabled, sbitmap live_bytes,
977 : : bool *by_clobber_p, tree stop_at_vuse)
978 : : {
979 : 29146180 : gimple *temp;
980 : 29146180 : int cnt = 0;
981 : 29146180 : auto_bitmap visited;
982 : 29146180 : std::unique_ptr<data_reference, void(*)(data_reference_p)>
983 : 29146180 : dra (nullptr, free_data_ref);
984 : :
985 : 29146180 : if (by_clobber_p)
986 : 28755037 : *by_clobber_p = true;
987 : :
988 : : /* Find the first dominated statement that clobbers (part of) the
989 : : memory stmt stores to with no intermediate statement that may use
990 : : part of the memory stmt stores. That is, find a store that may
991 : : prove stmt to be a dead store. */
992 : : temp = stmt;
993 : 359658508 : do
994 : : {
995 : 194402344 : gimple *use_stmt;
996 : 194402344 : imm_use_iterator ui;
997 : 194402344 : bool fail = false;
998 : 194402344 : tree defvar;
999 : :
1000 : 194402344 : if (gimple_code (temp) == GIMPLE_PHI)
1001 : : {
1002 : 6974415 : defvar = PHI_RESULT (temp);
1003 : 6974415 : bitmap_set_bit (visited, SSA_NAME_VERSION (defvar));
1004 : : }
1005 : : else
1006 : 374855858 : defvar = gimple_vdef (temp);
1007 : :
1008 : 194402344 : auto_vec<gimple *, 10> defs;
1009 : 194402344 : gphi *first_phi_def = NULL;
1010 : 194402344 : gphi *last_phi_def = NULL;
1011 : :
1012 : 194402344 : auto_vec<tree, 10> worklist;
1013 : 194402344 : worklist.quick_push (defvar);
1014 : :
1015 : 195611598 : do
1016 : : {
1017 : 195611598 : defvar = worklist.pop ();
1018 : : /* If we're instructed to stop walking at region boundary, do so. */
1019 : 195611598 : if (defvar == stop_at_vuse)
1020 : 15112 : return DSE_STORE_LIVE;
1021 : :
1022 : 393896005 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
1023 : : {
1024 : : /* Limit stmt walking. */
1025 : 223359440 : if (++cnt > param_dse_max_alias_queries_per_store)
1026 : : {
1027 : : fail = true;
1028 : : break;
1029 : : }
1030 : :
1031 : : /* In simple cases we can look through PHI nodes, but we
1032 : : have to be careful with loops and with memory references
1033 : : containing operands that are also operands of PHI nodes.
1034 : : See gcc.c-torture/execute/20051110-*.c. */
1035 : 223238345 : if (gimple_code (use_stmt) == GIMPLE_PHI)
1036 : : {
1037 : : /* Look through single-argument PHIs. */
1038 : 13832964 : if (gimple_phi_num_args (use_stmt) == 1)
1039 : 1731892 : worklist.safe_push (gimple_phi_result (use_stmt));
1040 : :
1041 : : /* If we already visited this PHI ignore it for further
1042 : : processing. */
1043 : 12101072 : else if (!bitmap_bit_p (visited,
1044 : 12101072 : SSA_NAME_VERSION
1045 : : (PHI_RESULT (use_stmt))))
1046 : : {
1047 : : /* If we visit this PHI by following a backedge then we
1048 : : have to make sure ref->ref only refers to SSA names
1049 : : that are invariant with respect to the loop
1050 : : represented by this PHI node. */
1051 : 11762337 : if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt),
1052 : 11762337 : gimple_bb (use_stmt))
1053 : 11762337 : && !for_each_index (ref->ref ? &ref->ref : &ref->base,
1054 : 1477775 : check_name, gimple_bb (use_stmt)))
1055 : 1131288 : return DSE_STORE_LIVE;
1056 : 10631049 : defs.safe_push (use_stmt);
1057 : 10631049 : if (!first_phi_def)
1058 : 9635963 : first_phi_def = as_a <gphi *> (use_stmt);
1059 : 10631049 : last_phi_def = as_a <gphi *> (use_stmt);
1060 : : }
1061 : : }
1062 : : /* If the statement is a use the store is not dead. */
1063 : 209405381 : else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
1064 : : {
1065 : 23818075 : if (dse_stmt_to_dr_map
1066 : 5296602 : && ref->ref
1067 : 29035815 : && is_gimple_assign (use_stmt))
1068 : : {
1069 : 1068628 : if (!dra)
1070 : 1064579 : dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
1071 : : false, false));
1072 : 1068628 : bool existed_p;
1073 : 1068628 : data_reference_p &drb
1074 : 1068628 : = dse_stmt_to_dr_map->get_or_insert (use_stmt,
1075 : : &existed_p);
1076 : 1068628 : if (!existed_p)
1077 : 678938 : drb = create_data_ref (NULL, NULL,
1078 : : gimple_assign_rhs1 (use_stmt),
1079 : : use_stmt, false, false);
1080 : 1068628 : if (!dr_may_alias_p (dra.get (), drb, NULL))
1081 : : {
1082 : 14484 : if (gimple_vdef (use_stmt))
1083 : 15 : defs.safe_push (use_stmt);
1084 : 7242 : continue;
1085 : : }
1086 : : }
1087 : :
1088 : : /* Handle common cases where we can easily build an ao_ref
1089 : : structure for USE_STMT and in doing so we find that the
1090 : : references hit non-live bytes and thus can be ignored.
1091 : :
1092 : : TODO: We can also use modref summary to handle calls. */
1093 : 23810833 : if (byte_tracking_enabled
1094 : 23810833 : && is_gimple_assign (use_stmt))
1095 : : {
1096 : 4803386 : ao_ref use_ref;
1097 : 4803386 : ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt));
1098 : 4803386 : if (valid_ao_ref_for_dse (&use_ref)
1099 : 4790322 : && operand_equal_p (use_ref.base, ref->base,
1100 : : OEP_ADDRESS_OF)
1101 : 8451789 : && !live_bytes_read (&use_ref, ref, live_bytes))
1102 : : {
1103 : : /* If this is a store, remember it as we possibly
1104 : : need to walk the defs uses. */
1105 : 6590 : if (gimple_vdef (use_stmt))
1106 : 864 : defs.safe_push (use_stmt);
1107 : 3295 : continue;
1108 : : }
1109 : : }
1110 : :
1111 : : fail = true;
1112 : : break;
1113 : : }
1114 : : /* We have visited ourselves already so ignore STMT for the
1115 : : purpose of chaining. */
1116 : 185587306 : else if (use_stmt == stmt)
1117 : : ;
1118 : : /* If this is a store, remember it as we possibly need to walk the
1119 : : defs uses. */
1120 : 569354719 : else if (gimple_vdef (use_stmt))
1121 : 166308876 : defs.safe_push (use_stmt);
1122 : 195596486 : }
1123 : : }
1124 : 388930396 : while (!fail && !worklist.is_empty ());
1125 : :
1126 : 193255944 : if (fail)
1127 : : {
1128 : : /* STMT might be partially dead and we may be able to reduce
1129 : : how many memory locations it stores into. */
1130 : 23928633 : if (byte_tracking_enabled && !gimple_clobber_p (stmt))
1131 : 22704357 : return DSE_STORE_MAYBE_PARTIAL_DEAD;
1132 : : return DSE_STORE_LIVE;
1133 : : }
1134 : :
1135 : : /* If we didn't find any definition this means the store is dead
1136 : : if it isn't a store to global reachable memory. In this case
1137 : : just pretend the stmt makes itself dead. Otherwise fail. */
1138 : 169327311 : if (defs.is_empty ())
1139 : : {
1140 : 299419 : if (ref_may_alias_global_p (ref, false))
1141 : : {
1142 : 33862 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (defvar));
1143 : : /* Assume that BUILT_IN_UNREACHABLE and BUILT_IN_UNREACHABLE_TRAP
1144 : : do not need to keep (global) memory side-effects live.
1145 : : We do not have virtual operands on BUILT_IN_UNREACHABLE
1146 : : but we can do poor mans reachability when the last
1147 : : definition we want to elide is in the block that ends
1148 : : in such a call. */
1149 : 33862 : if (EDGE_COUNT (def_bb->succs) == 0)
1150 : 48344 : if (gcall *last = dyn_cast <gcall *> (*gsi_last_bb (def_bb)))
1151 : 552 : if (gimple_call_builtin_p (last, BUILT_IN_UNREACHABLE)
1152 : 552 : || gimple_call_builtin_p (last,
1153 : : BUILT_IN_UNREACHABLE_TRAP))
1154 : : {
1155 : 372 : if (by_clobber_p)
1156 : 372 : *by_clobber_p = false;
1157 : 372 : return DSE_STORE_DEAD;
1158 : : }
1159 : 33490 : return DSE_STORE_LIVE;
1160 : : }
1161 : :
1162 : 265557 : if (by_clobber_p)
1163 : 264567 : *by_clobber_p = false;
1164 : 265557 : return DSE_STORE_DEAD;
1165 : : }
1166 : :
1167 : : /* Process defs and remove those we need not process further. */
1168 : 685105054 : for (unsigned i = 0; i < defs.length ();)
1169 : : {
1170 : 173534333 : gimple *def = defs[i];
1171 : 173534333 : gimple *use_stmt;
1172 : 173534333 : use_operand_p use_p;
1173 : 173534333 : tree vdef = (gimple_code (def) == GIMPLE_PHI
1174 : 182875897 : ? gimple_phi_result (def) : gimple_vdef (def));
1175 : 173534333 : gphi *phi_def;
1176 : : /* If the path to check starts with a kill we do not need to
1177 : : process it further.
1178 : : ??? With byte tracking we need only kill the bytes currently
1179 : : live. */
1180 : 173534333 : if (stmt_kills_ref_p (def, ref))
1181 : : {
1182 : 1366495 : if (by_clobber_p && !gimple_clobber_p (def))
1183 : 602947 : *by_clobber_p = false;
1184 : 1366495 : defs.unordered_remove (i);
1185 : : }
1186 : : /* If the path ends here we do not need to process it further.
1187 : : This for example happens with calls to noreturn functions. */
1188 : 172167838 : else if (has_zero_uses (vdef))
1189 : : {
1190 : : /* But if the store is to global memory it is definitely
1191 : : not dead. */
1192 : 827857 : if (ref_may_alias_global_p (ref, false))
1193 : 9698 : return DSE_STORE_LIVE;
1194 : 818159 : defs.unordered_remove (i);
1195 : : }
1196 : : /* In addition to kills we can remove defs whose only use
1197 : : is another def in defs. That can only ever be PHIs of which
1198 : : we track two for simplicity reasons, the first and last in
1199 : : {first,last}_phi_def (we fail for multiple PHIs anyways).
1200 : : We can also ignore defs that feed only into
1201 : : already visited PHIs. */
1202 : 171339981 : else if (single_imm_use (vdef, &use_p, &use_stmt)
1203 : 171339981 : && (use_stmt == first_phi_def
1204 : 155983943 : || use_stmt == last_phi_def
1205 : 155945945 : || (gimple_code (use_stmt) == GIMPLE_PHI
1206 : 4784954 : && bitmap_bit_p (visited,
1207 : 4784954 : SSA_NAME_VERSION
1208 : : (PHI_RESULT (use_stmt))))))
1209 : : {
1210 : 769270 : defs.unordered_remove (i);
1211 : 769270 : if (def == first_phi_def)
1212 : : first_phi_def = NULL;
1213 : 742222 : else if (def == last_phi_def)
1214 : 48337 : last_phi_def = NULL;
1215 : : }
1216 : : /* If def is a PHI and one of its arguments is another PHI node still
1217 : : in consideration we can defer processing it. */
1218 : 170570711 : else if ((phi_def = dyn_cast <gphi *> (def))
1219 : 9304052 : && ((last_phi_def
1220 : 9304052 : && phi_def != last_phi_def
1221 : 767794 : && contains_phi_arg (phi_def,
1222 : : gimple_phi_result (last_phi_def)))
1223 : 9252222 : || (first_phi_def
1224 : 9252222 : && phi_def != first_phi_def
1225 : 715439 : && contains_phi_arg
1226 : 715439 : (phi_def, gimple_phi_result (first_phi_def)))))
1227 : : {
1228 : 101164 : defs.unordered_remove (i);
1229 : 101164 : if (phi_def == first_phi_def)
1230 : : first_phi_def = NULL;
1231 : 55014 : else if (phi_def == last_phi_def)
1232 : 48337 : last_phi_def = NULL;
1233 : : }
1234 : : else
1235 : 170469547 : ++i;
1236 : : }
1237 : :
1238 : : /* If all defs kill the ref we are done. */
1239 : 169018194 : if (defs.is_empty ())
1240 : 1229011 : return DSE_STORE_DEAD;
1241 : : /* If more than one def survives fail. */
1242 : 167789183 : if (defs.length () > 1)
1243 : : {
1244 : : /* STMT might be partially dead and we may be able to reduce
1245 : : how many memory locations it stores into. */
1246 : 2208886 : if (byte_tracking_enabled && !gimple_clobber_p (stmt))
1247 : 2094812 : return DSE_STORE_MAYBE_PARTIAL_DEAD;
1248 : : return DSE_STORE_LIVE;
1249 : : }
1250 : 165580297 : temp = defs[0];
1251 : :
1252 : : /* Track partial kills. */
1253 : 165580297 : if (byte_tracking_enabled)
1254 : : {
1255 : 162414907 : clear_bytes_written_by (live_bytes, temp, ref);
1256 : 162414907 : if (bitmap_empty_p (live_bytes))
1257 : : {
1258 : 324133 : if (by_clobber_p && !gimple_clobber_p (temp))
1259 : 319470 : *by_clobber_p = false;
1260 : 324133 : return DSE_STORE_DEAD;
1261 : : }
1262 : : }
1263 : 194402344 : }
1264 : : /* Continue walking until there are no more live bytes. */
1265 : : while (1);
1266 : 29146180 : }
1267 : :
1268 : :
1269 : : /* Delete a dead call at GSI, which is mem* call of some kind. */
1270 : : static void
1271 : 5546 : delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type)
1272 : : {
1273 : 5546 : gimple *stmt = gsi_stmt (*gsi);
1274 : 5546 : if (dump_file && (dump_flags & TDF_DETAILS))
1275 : : {
1276 : 15 : fprintf (dump_file, " Deleted %s call: ", type);
1277 : 15 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1278 : 15 : fprintf (dump_file, "\n");
1279 : : }
1280 : :
1281 : 5546 : basic_block bb = gimple_bb (stmt);
1282 : 5546 : tree lhs = gimple_call_lhs (stmt);
1283 : 5546 : if (lhs)
1284 : : {
1285 : 791 : tree ptr = gimple_call_arg (stmt, 0);
1286 : 791 : gimple *new_stmt = gimple_build_assign (lhs, ptr);
1287 : 791 : unlink_stmt_vdef (stmt);
1288 : 791 : if (gsi_replace (gsi, new_stmt, true))
1289 : 2 : bitmap_set_bit (need_eh_cleanup, bb->index);
1290 : : }
1291 : : else
1292 : : {
1293 : : /* Then we need to fix the operand of the consuming stmt. */
1294 : 4755 : unlink_stmt_vdef (stmt);
1295 : :
1296 : : /* Remove the dead store. */
1297 : 4755 : if (gsi_remove (gsi, true))
1298 : 0 : bitmap_set_bit (need_eh_cleanup, bb->index);
1299 : 4755 : release_defs (stmt);
1300 : : }
1301 : 5546 : }
1302 : :
1303 : : /* Delete a dead store at GSI, which is a gimple assignment. */
1304 : :
1305 : : void
1306 : 1017287 : delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi,
1307 : : const char *type,
1308 : : bitmap need_eh_cleanup,
1309 : : bitmap need_ab_cleanup)
1310 : : {
1311 : 1017287 : gimple *stmt = gsi_stmt (*gsi);
1312 : 1017287 : if (dump_file && (dump_flags & TDF_DETAILS))
1313 : : {
1314 : 105 : fprintf (dump_file, " Deleted %s store: ", type);
1315 : 105 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1316 : 105 : fprintf (dump_file, "\n");
1317 : : }
1318 : :
1319 : : /* Then we need to fix the operand of the consuming stmt. */
1320 : 1017287 : unlink_stmt_vdef (stmt);
1321 : :
1322 : : /* Remove the dead store. */
1323 : 1017287 : basic_block bb = gimple_bb (stmt);
1324 : 1017287 : if (need_ab_cleanup && stmt_can_make_abnormal_goto (stmt))
1325 : 4 : bitmap_set_bit (need_ab_cleanup, bb->index);
1326 : 1017287 : if (gsi_remove (gsi, true) && need_eh_cleanup)
1327 : 84 : bitmap_set_bit (need_eh_cleanup, bb->index);
1328 : :
1329 : : /* And release any SSA_NAMEs set in this statement back to the
1330 : : SSA_NAME manager. */
1331 : 1017287 : release_defs (stmt);
1332 : 1017287 : }
1333 : :
1334 : : /* Try to prove, using modref summary, that all memory written to by a call is
1335 : : dead and remove it. Assume that if return value is written to memory
1336 : : it is already proved to be dead. */
1337 : :
1338 : : static bool
1339 : 16064065 : dse_optimize_call (gimple_stmt_iterator *gsi, sbitmap live_bytes)
1340 : : {
1341 : 31937299 : gcall *stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1342 : :
1343 : 15874342 : if (!stmt)
1344 : : return false;
1345 : :
1346 : 15874342 : tree callee = gimple_call_fndecl (stmt);
1347 : :
1348 : 15874342 : if (!callee)
1349 : : return false;
1350 : :
1351 : : /* Pure/const functions are optimized by normal DCE
1352 : : or handled as store above. */
1353 : 15210128 : int flags = gimple_call_flags (stmt);
1354 : 15210128 : if ((flags & (ECF_PURE|ECF_CONST|ECF_NOVOPS))
1355 : 107 : && !(flags & (ECF_LOOPING_CONST_OR_PURE)))
1356 : : return false;
1357 : :
1358 : 15210128 : cgraph_node *node = cgraph_node::get (callee);
1359 : 15210128 : if (!node)
1360 : : return false;
1361 : :
1362 : 15200826 : if (stmt_could_throw_p (cfun, stmt)
1363 : 15200826 : && !cfun->can_delete_dead_exceptions)
1364 : : return false;
1365 : :
1366 : : /* If return value is used the call is not dead. */
1367 : 10596065 : tree lhs = gimple_call_lhs (stmt);
1368 : 10596065 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
1369 : : {
1370 : 2152273 : imm_use_iterator ui;
1371 : 2152273 : gimple *use_stmt;
1372 : 2311890 : FOR_EACH_IMM_USE_STMT (use_stmt, ui, lhs)
1373 : 2249409 : if (!is_gimple_debug (use_stmt))
1374 : 2152273 : return false;
1375 : : }
1376 : :
1377 : : /* Verify that there are no side-effects except for return value
1378 : : and memory writes tracked by modref. */
1379 : 8506273 : modref_summary *summary = get_modref_function_summary (node);
1380 : 8506273 : if (!summary || !summary->try_dse)
1381 : : return false;
1382 : :
1383 : 53209 : bool by_clobber_p = false;
1384 : :
1385 : : /* Walk all memory writes and verify that they are dead. */
1386 : 160915 : for (auto base_node : summary->stores->bases)
1387 : 162206 : for (auto ref_node : base_node->refs)
1388 : 163937 : for (auto access_node : ref_node->accesses)
1389 : : {
1390 : 54158 : tree arg = access_node.get_call_arg (stmt);
1391 : :
1392 : 54158 : if (!arg || !POINTER_TYPE_P (TREE_TYPE (arg)))
1393 : 52101 : return false;
1394 : :
1395 : 54157 : if (integer_zerop (arg)
1396 : 54168 : && !targetm.addr_space.zero_address_valid
1397 : 11 : (TYPE_ADDR_SPACE (TREE_TYPE (arg))))
1398 : 11 : continue;
1399 : :
1400 : 54146 : ao_ref ref;
1401 : :
1402 : 54146 : if (!access_node.get_ao_ref (stmt, &ref))
1403 : : return false;
1404 : 54146 : ref.ref_alias_set = ref_node->ref;
1405 : 54146 : ref.base_alias_set = base_node->base;
1406 : :
1407 : 54146 : bool byte_tracking_enabled
1408 : 54146 : = setup_live_bytes_from_ref (&ref, live_bytes);
1409 : 54146 : enum dse_store_status store_status;
1410 : :
1411 : 54146 : store_status = dse_classify_store (&ref, stmt,
1412 : : byte_tracking_enabled,
1413 : : live_bytes, &by_clobber_p);
1414 : 54146 : if (store_status != DSE_STORE_DEAD)
1415 : : return false;
1416 : : }
1417 : 1108 : delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
1418 : : need_ab_cleanup);
1419 : 1108 : return true;
1420 : : }
1421 : :
1422 : : /* Attempt to eliminate dead stores in the statement referenced by BSI.
1423 : :
1424 : : A dead store is a store into a memory location which will later be
1425 : : overwritten by another store without any intervening loads. In this
1426 : : case the earlier store can be deleted.
1427 : :
1428 : : In our SSA + virtual operand world we use immediate uses of virtual
1429 : : operands to detect dead stores. If a store's virtual definition
1430 : : is used precisely once by a later store to the same location which
1431 : : post dominates the first store, then the first store is dead. */
1432 : :
1433 : : static void
1434 : 50407630 : dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes)
1435 : : {
1436 : 50407630 : gimple *stmt = gsi_stmt (*gsi);
1437 : :
1438 : : /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
1439 : 50407630 : if (gimple_has_volatile_ops (stmt)
1440 : 50407630 : && (!gimple_clobber_p (stmt)
1441 : 6215681 : || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
1442 : 49281939 : return;
1443 : :
1444 : 45128805 : ao_ref ref;
1445 : : /* If this is not a store we can still remove dead call using
1446 : : modref summary. Note we specifically allow ref to be initialized
1447 : : to a conservative may-def since we are looking for followup stores
1448 : : to kill all of it. */
1449 : 45128805 : if (!initialize_ao_ref_for_dse (stmt, &ref, true))
1450 : : {
1451 : 16050847 : dse_optimize_call (gsi, live_bytes);
1452 : 16050847 : return;
1453 : : }
1454 : :
1455 : : /* We know we have virtual definitions. We can handle assignments and
1456 : : some builtin calls. */
1457 : 29077958 : if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
1458 : : {
1459 : 374407 : tree fndecl = gimple_call_fndecl (stmt);
1460 : 374407 : switch (DECL_FUNCTION_CODE (fndecl))
1461 : : {
1462 : 373148 : case BUILT_IN_MEMCPY:
1463 : 373148 : case BUILT_IN_MEMMOVE:
1464 : 373148 : case BUILT_IN_STRNCPY:
1465 : 373148 : case BUILT_IN_MEMSET:
1466 : 373148 : case BUILT_IN_MEMCPY_CHK:
1467 : 373148 : case BUILT_IN_MEMMOVE_CHK:
1468 : 373148 : case BUILT_IN_STRNCPY_CHK:
1469 : 373148 : case BUILT_IN_MEMSET_CHK:
1470 : 373148 : {
1471 : : /* Occasionally calls with an explicit length of zero
1472 : : show up in the IL. It's pointless to do analysis
1473 : : on them, they're trivially dead. */
1474 : 373148 : tree size = gimple_call_arg (stmt, 2);
1475 : 373148 : if (integer_zerop (size))
1476 : : {
1477 : 50 : delete_dead_or_redundant_call (gsi, "dead");
1478 : 50 : return;
1479 : : }
1480 : :
1481 : : /* If this is a memset call that initializes an object
1482 : : to zero, it may be redundant with an earlier memset
1483 : : or empty CONSTRUCTOR of a larger object. */
1484 : 373098 : if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
1485 : 287429 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
1486 : 373430 : && integer_zerop (gimple_call_arg (stmt, 1)))
1487 : 50336 : dse_optimize_redundant_stores (stmt);
1488 : :
1489 : 373098 : enum dse_store_status store_status;
1490 : 373098 : bool byte_tracking_enabled
1491 : 373098 : = setup_live_bytes_from_ref (&ref, live_bytes);
1492 : 373098 : store_status = dse_classify_store (&ref, stmt,
1493 : : byte_tracking_enabled,
1494 : : live_bytes);
1495 : 373098 : if (store_status == DSE_STORE_LIVE)
1496 : : return;
1497 : :
1498 : 137990 : if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
1499 : : {
1500 : 132543 : maybe_trim_memstar_call (&ref, live_bytes, stmt);
1501 : 132543 : return;
1502 : : }
1503 : :
1504 : 5447 : if (store_status == DSE_STORE_DEAD)
1505 : 5447 : delete_dead_or_redundant_call (gsi, "dead");
1506 : 5447 : return;
1507 : : }
1508 : :
1509 : 1259 : case BUILT_IN_CALLOC:
1510 : : /* We already know the arguments are integer constants. */
1511 : 1259 : dse_optimize_redundant_stores (stmt);
1512 : 1259 : return;
1513 : :
1514 : : default:
1515 : : return;
1516 : : }
1517 : : }
1518 : 28703551 : else if (is_gimple_call (stmt)
1519 : 28703551 : && gimple_call_internal_p (stmt))
1520 : : {
1521 : 3422 : switch (gimple_call_internal_fn (stmt))
1522 : : {
1523 : 2193 : case IFN_LEN_STORE:
1524 : 2193 : case IFN_MASK_STORE:
1525 : 2193 : case IFN_MASK_LEN_STORE:
1526 : 2193 : {
1527 : 2193 : enum dse_store_status store_status;
1528 : 2193 : store_status = dse_classify_store (&ref, stmt, false, live_bytes);
1529 : 2193 : if (store_status == DSE_STORE_DEAD)
1530 : 0 : delete_dead_or_redundant_call (gsi, "dead");
1531 : 2193 : return;
1532 : : }
1533 : : default:;
1534 : : }
1535 : : }
1536 : :
1537 : 28701358 : bool by_clobber_p = false;
1538 : :
1539 : : /* Check if this statement stores zero to a memory location,
1540 : : and if there is a subsequent store of zero to the same
1541 : : memory location. If so, remove the subsequent store. */
1542 : 28701358 : if (gimple_assign_single_p (stmt)
1543 : 28701358 : && initializer_zerop (gimple_assign_rhs1 (stmt)))
1544 : 3613356 : dse_optimize_redundant_stores (stmt);
1545 : :
1546 : : /* Self-assignments are zombies. */
1547 : 28701358 : if (is_gimple_assign (stmt)
1548 : 56089570 : && operand_equal_p (gimple_assign_rhs1 (stmt),
1549 : 27388212 : gimple_assign_lhs (stmt), 0))
1550 : : ;
1551 : : else
1552 : : {
1553 : 28700891 : bool byte_tracking_enabled
1554 : 28700891 : = setup_live_bytes_from_ref (&ref, live_bytes);
1555 : 28700891 : enum dse_store_status store_status;
1556 : 28700891 : store_status = dse_classify_store (&ref, stmt,
1557 : : byte_tracking_enabled,
1558 : : live_bytes, &by_clobber_p);
1559 : 28700891 : if (store_status == DSE_STORE_LIVE)
1560 : : return;
1561 : :
1562 : 26427471 : if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
1563 : : {
1564 : 24616227 : maybe_trim_partially_dead_store (&ref, live_bytes, stmt);
1565 : 24616227 : return;
1566 : : }
1567 : : }
1568 : :
1569 : : /* Now we know that use_stmt kills the LHS of stmt. */
1570 : :
1571 : : /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
1572 : : another clobber stmt. */
1573 : 1811711 : if (gimple_clobber_p (stmt)
1574 : 1811711 : && !by_clobber_p)
1575 : : return;
1576 : :
1577 : 1128737 : if (is_gimple_call (stmt)
1578 : 1128737 : && (gimple_has_side_effects (stmt)
1579 : 483 : || (stmt_could_throw_p (fun, stmt)
1580 : 4 : && !fun->can_delete_dead_exceptions)))
1581 : : {
1582 : : /* See if we can remove complete call. */
1583 : 13218 : if (dse_optimize_call (gsi, live_bytes))
1584 : : return;
1585 : : /* Make sure we do not remove a return slot we cannot reconstruct
1586 : : later. */
1587 : 13204 : if (gimple_call_return_slot_opt_p (as_a <gcall *>(stmt))
1588 : 13204 : && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt)))
1589 : 6533 : || !poly_int_tree_p
1590 : 6533 : (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt))))))
1591 : : return;
1592 : 10172 : if (dump_file && (dump_flags & TDF_DETAILS))
1593 : : {
1594 : 1 : fprintf (dump_file, " Deleted dead store in call LHS: ");
1595 : 1 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1596 : 1 : fprintf (dump_file, "\n");
1597 : : }
1598 : 10172 : gimple_call_set_lhs (stmt, NULL_TREE);
1599 : 10172 : update_stmt (stmt);
1600 : : }
1601 : 1115519 : else if (!stmt_could_throw_p (fun, stmt)
1602 : 1115519 : || fun->can_delete_dead_exceptions)
1603 : 1010637 : delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
1604 : : need_ab_cleanup);
1605 : : }
1606 : :
1607 : : namespace {
1608 : :
1609 : : const pass_data pass_data_dse =
1610 : : {
1611 : : GIMPLE_PASS, /* type */
1612 : : "dse", /* name */
1613 : : OPTGROUP_NONE, /* optinfo_flags */
1614 : : TV_TREE_DSE, /* tv_id */
1615 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1616 : : 0, /* properties_provided */
1617 : : 0, /* properties_destroyed */
1618 : : 0, /* todo_flags_start */
1619 : : 0, /* todo_flags_finish */
1620 : : };
1621 : :
1622 : : class pass_dse : public gimple_opt_pass
1623 : : {
1624 : : public:
1625 : 1409570 : pass_dse (gcc::context *ctxt)
1626 : 2819140 : : gimple_opt_pass (pass_data_dse, ctxt), use_dr_analysis_p (false)
1627 : : {}
1628 : :
1629 : : /* opt_pass methods: */
1630 : 1127656 : opt_pass * clone () final override { return new pass_dse (m_ctxt); }
1631 : 281914 : void set_pass_param (unsigned n, bool param) final override
1632 : : {
1633 : 281914 : gcc_assert (n == 0);
1634 : 281914 : use_dr_analysis_p = param;
1635 : 281914 : }
1636 : 5199336 : bool gate (function *) final override { return flag_tree_dse != 0; }
1637 : : unsigned int execute (function *) final override;
1638 : :
1639 : : private:
1640 : : bool use_dr_analysis_p;
1641 : : }; // class pass_dse
1642 : :
1643 : : unsigned int
1644 : 5175120 : pass_dse::execute (function *fun)
1645 : : {
1646 : 5175120 : unsigned todo = 0;
1647 : 5175120 : bool released_def = false;
1648 : :
1649 : 5175120 : need_eh_cleanup = BITMAP_ALLOC (NULL);
1650 : 5175120 : need_ab_cleanup = BITMAP_ALLOC (NULL);
1651 : 5175120 : auto_sbitmap live_bytes (param_dse_max_object_size);
1652 : 5175120 : if (flag_expensive_optimizations && use_dr_analysis_p)
1653 : 909954 : dse_stmt_to_dr_map = new hash_map<gimple *, data_reference_p>;
1654 : :
1655 : 5175120 : renumber_gimple_stmt_uids (fun);
1656 : :
1657 : 5175120 : calculate_dominance_info (CDI_DOMINATORS);
1658 : :
1659 : : /* Dead store elimination is fundamentally a reverse program order walk. */
1660 : 5175120 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
1661 : 5175120 : int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
1662 : 47378985 : for (int i = n; i != 0; --i)
1663 : : {
1664 : 42203865 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);
1665 : 42203865 : gimple_stmt_iterator gsi;
1666 : :
1667 : 84407730 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1668 : : {
1669 : 278456107 : gimple *stmt = gsi_stmt (gsi);
1670 : :
1671 : 391412107 : if (gimple_vdef (stmt))
1672 : 50407630 : dse_optimize_stmt (fun, &gsi, live_bytes);
1673 : 456096954 : else if (def_operand_p
1674 : 228048477 : def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
1675 : : {
1676 : : /* When we remove dead stores make sure to also delete trivially
1677 : : dead SSA defs. */
1678 : 57036639 : if (has_zero_uses (DEF_FROM_PTR (def_p))
1679 : 1926964 : && !gimple_has_side_effects (stmt)
1680 : 1918428 : && !is_ctrl_altering_stmt (stmt)
1681 : 58952033 : && (!stmt_could_throw_p (fun, stmt)
1682 : 93863 : || fun->can_delete_dead_exceptions))
1683 : : {
1684 : 1821796 : if (dump_file && (dump_flags & TDF_DETAILS))
1685 : : {
1686 : 42 : fprintf (dump_file, " Deleted trivially dead stmt: ");
1687 : 42 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1688 : 42 : fprintf (dump_file, "\n");
1689 : : }
1690 : 1821796 : if (gsi_remove (&gsi, true) && need_eh_cleanup)
1691 : 22 : bitmap_set_bit (need_eh_cleanup, bb->index);
1692 : 1821796 : release_defs (stmt);
1693 : 1821796 : released_def = true;
1694 : : }
1695 : : }
1696 : 278456107 : if (gsi_end_p (gsi))
1697 : 418526 : gsi = gsi_last_bb (bb);
1698 : : else
1699 : 598906816 : gsi_prev (&gsi);
1700 : : }
1701 : 42203865 : bool removed_phi = false;
1702 : 59016359 : for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
1703 : : {
1704 : 16812494 : gphi *phi = si.phi ();
1705 : 16812494 : if (has_zero_uses (gimple_phi_result (phi)))
1706 : : {
1707 : 240244 : if (dump_file && (dump_flags & TDF_DETAILS))
1708 : : {
1709 : 0 : fprintf (dump_file, " Deleted trivially dead PHI: ");
1710 : 0 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
1711 : 0 : fprintf (dump_file, "\n");
1712 : : }
1713 : 240244 : remove_phi_node (&si, true);
1714 : 240244 : removed_phi = true;
1715 : 240244 : released_def = true;
1716 : : }
1717 : : else
1718 : 16572250 : gsi_next (&si);
1719 : : }
1720 : 42203865 : if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
1721 : : todo |= TODO_cleanup_cfg;
1722 : : }
1723 : 5175120 : free (rpo);
1724 : :
1725 : : /* Removal of stores may make some EH edges dead. Purge such edges from
1726 : : the CFG as needed. */
1727 : 5175120 : if (!bitmap_empty_p (need_eh_cleanup))
1728 : : {
1729 : 79 : gimple_purge_all_dead_eh_edges (need_eh_cleanup);
1730 : 79 : todo |= TODO_cleanup_cfg;
1731 : : }
1732 : 5175120 : if (!bitmap_empty_p (need_ab_cleanup))
1733 : : {
1734 : 4 : gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
1735 : 4 : todo |= TODO_cleanup_cfg;
1736 : : }
1737 : :
1738 : 5175120 : BITMAP_FREE (need_eh_cleanup);
1739 : 5175120 : BITMAP_FREE (need_ab_cleanup);
1740 : :
1741 : 5175120 : if (released_def)
1742 : 591495 : free_numbers_of_iterations_estimates (fun);
1743 : :
1744 : 5175120 : if (flag_expensive_optimizations && use_dr_analysis_p)
1745 : : {
1746 : 1588892 : for (auto i = dse_stmt_to_dr_map->begin ();
1747 : 2267830 : i != dse_stmt_to_dr_map->end (); ++i)
1748 : 678938 : free_data_ref ((*i).second);
1749 : 1819908 : delete dse_stmt_to_dr_map;
1750 : 909954 : dse_stmt_to_dr_map = NULL;
1751 : : }
1752 : :
1753 : 5175120 : return todo;
1754 : 5175120 : }
1755 : :
1756 : : } // anon namespace
1757 : :
1758 : : gimple_opt_pass *
1759 : 281914 : make_pass_dse (gcc::context *ctxt)
1760 : : {
1761 : 281914 : return new pass_dse (ctxt);
1762 : : }
|
