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 | 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 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) |
115 | { |
116 | switch (DECL_FUNCTION_CODE (decl: gimple_call_fndecl (gs: stmt))) |
117 | { |
118 | case BUILT_IN_MEMCPY: |
119 | case BUILT_IN_MEMMOVE: |
120 | case BUILT_IN_MEMSET: |
121 | case BUILT_IN_MEMCPY_CHK: |
122 | case BUILT_IN_MEMMOVE_CHK: |
123 | case BUILT_IN_MEMSET_CHK: |
124 | case BUILT_IN_STRNCPY: |
125 | case BUILT_IN_STRNCPY_CHK: |
126 | { |
127 | tree size = gimple_call_arg (gs: stmt, index: 2); |
128 | tree ptr = gimple_call_arg (gs: stmt, index: 0); |
129 | ao_ref_init_from_ptr_and_size (write, ptr, size); |
130 | 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 | case BUILT_IN_CALLOC: |
137 | { |
138 | tree nelem = gimple_call_arg (gs: stmt, index: 0); |
139 | tree selem = gimple_call_arg (gs: stmt, index: 1); |
140 | tree lhs; |
141 | if (TREE_CODE (nelem) == INTEGER_CST |
142 | && TREE_CODE (selem) == INTEGER_CST |
143 | && (lhs = gimple_call_lhs (gs: stmt)) != NULL_TREE) |
144 | { |
145 | tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem), |
146 | nelem, selem); |
147 | ao_ref_init_from_ptr_and_size (write, lhs, size); |
148 | return true; |
149 | } |
150 | } |
151 | |
152 | default: |
153 | break; |
154 | } |
155 | } |
156 | else if (is_gimple_call (gs: stmt) |
157 | && gimple_call_internal_p (gs: stmt)) |
158 | { |
159 | switch (gimple_call_internal_fn (gs: stmt)) |
160 | { |
161 | case IFN_LEN_STORE: |
162 | case IFN_MASK_STORE: |
163 | case IFN_MASK_LEN_STORE: |
164 | { |
165 | internal_fn ifn = gimple_call_internal_fn (gs: stmt); |
166 | int stored_value_index = internal_fn_stored_value_index (ifn); |
167 | int len_index = internal_fn_len_index (ifn); |
168 | if (ifn == IFN_LEN_STORE) |
169 | { |
170 | tree len = gimple_call_arg (gs: stmt, index: len_index); |
171 | tree bias = gimple_call_arg (gs: stmt, index: len_index + 1); |
172 | if (tree_fits_uhwi_p (len)) |
173 | { |
174 | ao_ref_init_from_ptr_and_size (write, |
175 | gimple_call_arg (gs: stmt, index: 0), |
176 | int_const_binop (MINUS_EXPR, |
177 | len, bias)); |
178 | 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 | if (may_def_ok) |
184 | { |
185 | ao_ref_init_from_ptr_and_size ( |
186 | write, gimple_call_arg (gs: stmt, index: 0), |
187 | TYPE_SIZE_UNIT ( |
188 | TREE_TYPE (gimple_call_arg (stmt, stored_value_index)))); |
189 | return true; |
190 | } |
191 | break; |
192 | } |
193 | default:; |
194 | } |
195 | } |
196 | if (tree lhs = gimple_get_lhs (stmt)) |
197 | { |
198 | if (TREE_CODE (lhs) != SSA_NAME |
199 | && (may_def_ok || !stmt_could_throw_p (cfun, stmt))) |
200 | { |
201 | ao_ref_init (write, lhs); |
202 | 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 | valid_ao_ref_kill_for_dse (ao_ref *ref) |
217 | { |
218 | return (ao_ref_base (ref) |
219 | && known_size_p (a: ref->max_size) |
220 | && maybe_ne (a: ref->size, b: 0) |
221 | && known_eq (ref->max_size, ref->size) |
222 | && 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 | valid_ao_ref_for_dse (ao_ref *ref) |
233 | { |
234 | return (ao_ref_base (ref) |
235 | && known_size_p (a: ref->max_size) |
236 | && 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 | get_byte_aligned_range_containing_ref (ao_ref *ref, poly_int64 *offset, |
245 | HOST_WIDE_INT *size) |
246 | { |
247 | if (!known_size_p (a: ref->max_size)) |
248 | return false; |
249 | *offset = aligned_lower_bound (value: ref->offset, BITS_PER_UNIT); |
250 | poly_int64 end = aligned_upper_bound (value: ref->offset + ref->max_size, |
251 | BITS_PER_UNIT); |
252 | return (end - *offset).is_constant (const_value: 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 | get_byte_aligned_range_contained_in_ref (ao_ref *ref, poly_int64 *offset, |
261 | HOST_WIDE_INT *size) |
262 | { |
263 | if (!known_size_p (a: ref->size) |
264 | || !known_eq (ref->size, ref->max_size)) |
265 | return false; |
266 | *offset = aligned_upper_bound (value: ref->offset, BITS_PER_UNIT); |
267 | poly_int64 end = aligned_lower_bound (value: 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 | if (!known_gt (end, *offset)) |
272 | return false; |
273 | return (end - *offset).is_constant (const_value: 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 | get_byte_range (ao_ref *copy, ao_ref *ref, bool kill, |
283 | HOST_WIDE_INT *ret_offset, HOST_WIDE_INT *ret_size) |
284 | { |
285 | HOST_WIDE_INT copy_size, ref_size; |
286 | poly_int64 copy_offset, ref_offset; |
287 | 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 | if (kill) |
293 | { |
294 | if (!get_byte_aligned_range_contained_in_ref (ref: copy, offset: ©_offset, |
295 | size: ©_size)) |
296 | return false; |
297 | } |
298 | else |
299 | { |
300 | if (!get_byte_aligned_range_containing_ref (ref: copy, offset: ©_offset, |
301 | size: ©_size)) |
302 | return false; |
303 | } |
304 | |
305 | if (!get_byte_aligned_range_containing_ref (ref, offset: &ref_offset, size: &ref_size) |
306 | || !ordered_p (a: copy_offset, b: 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 | copy_size /= BITS_PER_UNIT; |
313 | 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 | if (maybe_lt (a: copy_offset, b: ref_offset)) |
319 | { |
320 | if (!(ref_offset - copy_offset).is_constant (const_value: &diff) |
321 | || copy_size < diff / BITS_PER_UNIT) |
322 | return false; |
323 | copy_size -= diff / BITS_PER_UNIT; |
324 | copy_offset = ref_offset; |
325 | } |
326 | |
327 | if (!(copy_offset - ref_offset).is_constant (const_value: &diff) |
328 | || ref_size <= diff / BITS_PER_UNIT) |
329 | return false; |
330 | |
331 | /* If COPY extends beyond REF, chop off its size appropriately. */ |
332 | HOST_WIDE_INT limit = ref_size - diff / BITS_PER_UNIT; |
333 | |
334 | if (copy_size > limit) |
335 | copy_size = limit; |
336 | *ret_size = copy_size; |
337 | if (!(copy_offset - ref_offset).is_constant (const_value: ret_offset)) |
338 | return false; |
339 | *ret_offset /= BITS_PER_UNIT; |
340 | 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 | clear_live_bytes_for_ref (sbitmap live_bytes, ao_ref *ref, ao_ref *write) |
348 | { |
349 | HOST_WIDE_INT start, size; |
350 | |
351 | if (valid_ao_ref_kill_for_dse (ref: write) |
352 | && operand_equal_p (write->base, ref->base, flags: OEP_ADDRESS_OF) |
353 | && get_byte_range (copy: write, ref, kill: true, ret_offset: &start, ret_size: &size)) |
354 | bitmap_clear_range (live_bytes, start, size); |
355 | } |
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 | clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) |
366 | { |
367 | ao_ref write; |
368 | |
369 | if (gcall *call = dyn_cast <gcall *> (p: stmt)) |
370 | { |
371 | bool interposed; |
372 | modref_summary *summary = get_modref_function_summary (call, interposed: &interposed); |
373 | |
374 | if (summary && !interposed) |
375 | for (auto kill : summary->kills) |
376 | if (kill.get_ao_ref (stmt: as_a <gcall *> (p: stmt), ref: &write)) |
377 | clear_live_bytes_for_ref (live_bytes, ref, write: &write); |
378 | } |
379 | if (!initialize_ao_ref_for_dse (stmt, write: &write)) |
380 | return; |
381 | |
382 | clear_live_bytes_for_ref (live_bytes, ref, write: &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 | setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) |
391 | { |
392 | HOST_WIDE_INT const_size; |
393 | if (valid_ao_ref_for_dse (ref) |
394 | && ((aligned_upper_bound (value: ref->offset + ref->max_size, BITS_PER_UNIT) |
395 | - aligned_lower_bound (value: ref->offset, |
396 | BITS_PER_UNIT)).is_constant (const_value: &const_size)) |
397 | && (const_size / BITS_PER_UNIT <= param_dse_max_object_size) |
398 | && const_size > 1) |
399 | { |
400 | bitmap_clear (live_bytes); |
401 | bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); |
402 | 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 | compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
418 | gimple *stmt) |
419 | { |
420 | *trim_head = 0; |
421 | *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 | const unsigned int align = known_alignment (a: ref->offset); |
428 | if ((align > 0 && align < BITS_PER_UNIT) |
429 | || !known_eq (ref->size, ref->max_size)) |
430 | return; |
431 | |
432 | /* Now identify how much, if any of the tail we can chop off. */ |
433 | HOST_WIDE_INT const_size; |
434 | int last_live = bitmap_last_set_bit (live); |
435 | if (ref->size.is_constant (const_value: &const_size)) |
436 | { |
437 | 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 | *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 | if (*trim_tail |
449 | && TYPE_SIZE_UNIT (TREE_TYPE (ref->base)) |
450 | && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST |
451 | && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)), |
452 | last_orig) <= 0) |
453 | *trim_tail = 0; |
454 | } |
455 | |
456 | /* Identify how much, if any of the head we can chop off. */ |
457 | int first_orig = 0; |
458 | int first_live = bitmap_first_set_bit (live); |
459 | *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 | unsigned int align_bits; |
464 | unsigned HOST_WIDE_INT bitpos; |
465 | if ((*trim_head || *trim_tail) |
466 | && last_live - first_live >= 2 |
467 | && ao_ref_alignment (ref, &align_bits, &bitpos) |
468 | && align_bits >= 32 |
469 | && bitpos == 0 |
470 | && align_bits % BITS_PER_UNIT == 0) |
471 | { |
472 | unsigned int align_units = align_bits / BITS_PER_UNIT; |
473 | if (align_units > 16) |
474 | align_units = 16; |
475 | while ((first_live | (align_units - 1)) > (unsigned int)last_live) |
476 | align_units >>= 1; |
477 | |
478 | if (*trim_head) |
479 | { |
480 | unsigned int pos = first_live & (align_units - 1); |
481 | for (unsigned int i = 1; i <= align_units; i <<= 1) |
482 | { |
483 | unsigned int mask = ~(i - 1); |
484 | unsigned int bytes = align_units - (pos & mask); |
485 | if (wi::popcount (bytes) <= 1) |
486 | { |
487 | *trim_head &= mask; |
488 | break; |
489 | } |
490 | } |
491 | } |
492 | |
493 | if (*trim_tail) |
494 | { |
495 | unsigned int pos = last_live & (align_units - 1); |
496 | for (unsigned int i = 1; i <= align_units; i <<= 1) |
497 | { |
498 | int mask = i - 1; |
499 | unsigned int bytes = (pos | mask) + 1; |
500 | if ((last_live | mask) > (last_live + *trim_tail)) |
501 | break; |
502 | if (wi::popcount (bytes) <= 1) |
503 | { |
504 | unsigned int = (last_live | mask) - last_live; |
505 | *trim_tail -= extra; |
506 | break; |
507 | } |
508 | } |
509 | } |
510 | } |
511 | |
512 | if ((*trim_head || *trim_tail) && dump_file && (dump_flags & TDF_DETAILS)) |
513 | { |
514 | fprintf (stream: dump_file, format: " Trimming statement (head = %d, tail = %d): " , |
515 | *trim_head, *trim_tail); |
516 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
517 | fprintf (stream: dump_file, format: "\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 | maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) |
530 | { |
531 | int trim_head, trim_tail; |
532 | compute_trims (ref, live, trim_head: &trim_head, trim_tail: &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 | if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) |
539 | { |
540 | /* TREE_REALPART is live */ |
541 | tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); |
542 | tree y = gimple_assign_lhs (gs: stmt); |
543 | y = build1 (REALPART_EXPR, TREE_TYPE (x), y); |
544 | gimple_assign_set_lhs (gs: stmt, lhs: y); |
545 | gimple_assign_set_rhs1 (gs: stmt, rhs: x); |
546 | } |
547 | else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) |
548 | { |
549 | /* TREE_IMAGPART is live */ |
550 | tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); |
551 | tree y = gimple_assign_lhs (gs: stmt); |
552 | y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); |
553 | gimple_assign_set_lhs (gs: stmt, lhs: y); |
554 | gimple_assign_set_rhs1 (gs: stmt, rhs: 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 | } |
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 | maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) |
574 | { |
575 | tree ctor = gimple_assign_rhs1 (gs: stmt); |
576 | |
577 | /* This is the only case we currently handle. It actually seems to |
578 | catch most cases of actual interest. */ |
579 | gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); |
580 | |
581 | int head_trim = 0; |
582 | int tail_trim = 0; |
583 | compute_trims (ref, live, trim_head: &head_trim, trim_tail: &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 | if (head_trim || tail_trim) |
588 | { |
589 | /* We want &lhs for the MEM_REF expression. */ |
590 | tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); |
591 | |
592 | if (! is_gimple_min_invariant (lhs_addr)) |
593 | return; |
594 | |
595 | /* The number of bytes for the new constructor. */ |
596 | poly_int64 ref_bytes = exact_div (a: ref->size, BITS_PER_UNIT); |
597 | 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 | 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 | tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (gs: stmt)); |
609 | |
610 | /* Build a MEM_REF representing the whole accessed area, starting |
611 | at the first byte not trimmed. */ |
612 | 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 | gimple_assign_set_lhs (gs: stmt, lhs: exp); |
617 | gimple_assign_set_rhs1 (gs: stmt, rhs: 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 | decrement_count (gimple *stmt, int decrement) |
625 | { |
626 | tree *countp = gimple_call_arg_ptr (gs: stmt, index: 2); |
627 | gcc_assert (TREE_CODE (*countp) == INTEGER_CST); |
628 | *countp = wide_int_to_tree (TREE_TYPE (*countp), cst: (TREE_INT_CST_LOW (*countp) |
629 | - decrement)); |
630 | } |
631 | |
632 | static void |
633 | increment_start_addr (gimple *stmt, tree *where, int increment) |
634 | { |
635 | if (tree lhs = gimple_call_lhs (gs: stmt)) |
636 | if (where == gimple_call_arg_ptr (gs: stmt, index: 0)) |
637 | { |
638 | gassign *newop = gimple_build_assign (lhs, unshare_expr (*where)); |
639 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); |
640 | gsi_insert_after (&gsi, newop, GSI_SAME_STMT); |
641 | gimple_call_set_lhs (gs: stmt, NULL_TREE); |
642 | update_stmt (s: stmt); |
643 | } |
644 | |
645 | if (TREE_CODE (*where) == SSA_NAME) |
646 | { |
647 | tree tem = make_ssa_name (TREE_TYPE (*where)); |
648 | gassign *newop |
649 | = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, |
650 | build_int_cst (sizetype, increment)); |
651 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); |
652 | gsi_insert_before (&gsi, newop, GSI_SAME_STMT); |
653 | *where = tem; |
654 | update_stmt (s: stmt); |
655 | return; |
656 | } |
657 | |
658 | *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, |
659 | *where, |
660 | build_int_cst (ptr_type_node, |
661 | increment))); |
662 | 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 | maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) |
675 | { |
676 | int head_trim, tail_trim; |
677 | switch (DECL_FUNCTION_CODE (decl: gimple_call_fndecl (gs: stmt))) |
678 | { |
679 | case BUILT_IN_STRNCPY: |
680 | case BUILT_IN_STRNCPY_CHK: |
681 | compute_trims (ref, live, trim_head: &head_trim, trim_tail: &tail_trim, stmt); |
682 | 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 | c_strlen_data lendata = { }; |
692 | int orig_head_trim = head_trim; |
693 | tree srcstr = gimple_call_arg (gs: stmt, index: 1); |
694 | if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1) |
695 | || !tree_fits_uhwi_p (lendata.minlen)) |
696 | head_trim = 0; |
697 | else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim) |
698 | { |
699 | head_trim = tree_to_uhwi (lendata.minlen); |
700 | if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0) |
701 | head_trim &= ~(UNITS_PER_WORD - 1); |
702 | } |
703 | if (orig_head_trim != head_trim |
704 | && dump_file |
705 | && (dump_flags & TDF_DETAILS)) |
706 | fprintf (stream: dump_file, |
707 | format: " Adjusting strncpy trimming to (head = %d," |
708 | " tail = %d)\n" , head_trim, tail_trim); |
709 | } |
710 | goto do_memcpy; |
711 | |
712 | case BUILT_IN_MEMCPY: |
713 | case BUILT_IN_MEMMOVE: |
714 | case BUILT_IN_MEMCPY_CHK: |
715 | case BUILT_IN_MEMMOVE_CHK: |
716 | compute_trims (ref, live, trim_head: &head_trim, trim_tail: &tail_trim, stmt); |
717 | |
718 | do_memcpy: |
719 | /* Tail trimming is easy, we can just reduce the count. */ |
720 | if (tail_trim) |
721 | decrement_count (stmt, decrement: tail_trim); |
722 | |
723 | /* Head trimming requires adjusting all the arguments. */ |
724 | if (head_trim) |
725 | { |
726 | /* For __*_chk need to adjust also the last argument. */ |
727 | if (gimple_call_num_args (gs: stmt) == 4) |
728 | { |
729 | tree size = gimple_call_arg (gs: stmt, index: 3); |
730 | if (!tree_fits_uhwi_p (size)) |
731 | break; |
732 | if (!integer_all_onesp (size)) |
733 | { |
734 | unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); |
735 | if (sz < (unsigned) head_trim) |
736 | break; |
737 | tree arg = wide_int_to_tree (TREE_TYPE (size), |
738 | cst: sz - head_trim); |
739 | gimple_call_set_arg (gs: stmt, index: 3, arg); |
740 | } |
741 | } |
742 | tree *dst = gimple_call_arg_ptr (gs: stmt, index: 0); |
743 | increment_start_addr (stmt, where: dst, increment: head_trim); |
744 | tree *src = gimple_call_arg_ptr (gs: stmt, index: 1); |
745 | increment_start_addr (stmt, where: src, increment: head_trim); |
746 | decrement_count (stmt, decrement: head_trim); |
747 | } |
748 | break; |
749 | |
750 | case BUILT_IN_MEMSET: |
751 | case BUILT_IN_MEMSET_CHK: |
752 | compute_trims (ref, live, trim_head: &head_trim, trim_tail: &tail_trim, stmt); |
753 | |
754 | /* Tail trimming is easy, we can just reduce the count. */ |
755 | if (tail_trim) |
756 | decrement_count (stmt, decrement: tail_trim); |
757 | |
758 | /* Head trimming requires adjusting all the arguments. */ |
759 | if (head_trim) |
760 | { |
761 | /* For __*_chk need to adjust also the last argument. */ |
762 | if (gimple_call_num_args (gs: stmt) == 4) |
763 | { |
764 | tree size = gimple_call_arg (gs: stmt, index: 3); |
765 | if (!tree_fits_uhwi_p (size)) |
766 | break; |
767 | if (!integer_all_onesp (size)) |
768 | { |
769 | unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); |
770 | if (sz < (unsigned) head_trim) |
771 | break; |
772 | tree arg = wide_int_to_tree (TREE_TYPE (size), |
773 | cst: sz - head_trim); |
774 | gimple_call_set_arg (gs: stmt, index: 3, arg); |
775 | } |
776 | } |
777 | tree *dst = gimple_call_arg_ptr (gs: stmt, index: 0); |
778 | increment_start_addr (stmt, where: dst, increment: head_trim); |
779 | decrement_count (stmt, decrement: head_trim); |
780 | } |
781 | break; |
782 | |
783 | default: |
784 | break; |
785 | } |
786 | } |
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 | maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) |
799 | { |
800 | if (is_gimple_assign (gs: stmt) |
801 | && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) |
802 | { |
803 | switch (gimple_assign_rhs_code (gs: stmt)) |
804 | { |
805 | case CONSTRUCTOR: |
806 | maybe_trim_constructor_store (ref, live, stmt); |
807 | break; |
808 | case COMPLEX_CST: |
809 | maybe_trim_complex_store (ref, live, stmt); |
810 | break; |
811 | default: |
812 | break; |
813 | } |
814 | } |
815 | } |
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 | 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 | HOST_WIDE_INT start, size; |
829 | if (get_byte_range (copy: use_ref, ref, kill: false, ret_offset: &start, ret_size: &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 | 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 | 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 | check_name (tree, tree *idx, void *data) |
848 | { |
849 | basic_block phi_bb = (basic_block) data; |
850 | if (TREE_CODE (*idx) == SSA_NAME |
851 | && !SSA_NAME_IS_DEFAULT_DEF (*idx) |
852 | && 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 | dse_optimize_redundant_stores (gimple *stmt) |
870 | { |
871 | int cnt = 0; |
872 | |
873 | /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */ |
874 | alias_set_type earlier_set = 0; |
875 | alias_set_type earlier_base_set = 0; |
876 | if (is_gimple_assign (gs: stmt)) |
877 | { |
878 | ao_ref lhs_ref; |
879 | ao_ref_init (&lhs_ref, gimple_assign_lhs (gs: stmt)); |
880 | earlier_set = ao_ref_alias_set (&lhs_ref); |
881 | 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 | tree defvar = gimple_vdef (g: stmt); |
892 | imm_use_iterator ui; |
893 | gimple *use_stmt; |
894 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
895 | { |
896 | /* Limit stmt walking. */ |
897 | 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 | tree fndecl; |
904 | if ((is_gimple_assign (gs: use_stmt) |
905 | && gimple_vdef (g: use_stmt) |
906 | && (gimple_assign_single_p (gs: use_stmt) |
907 | && initializer_zerop (gimple_assign_rhs1 (gs: use_stmt)))) |
908 | || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL) |
909 | && (fndecl = gimple_call_fndecl (gs: use_stmt)) != NULL |
910 | && (DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_MEMSET |
911 | || DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_MEMSET_CHK) |
912 | && integer_zerop (gimple_call_arg (gs: use_stmt, index: 1)))) |
913 | { |
914 | ao_ref write; |
915 | |
916 | if (!initialize_ao_ref_for_dse (stmt: use_stmt, write: &write)) |
917 | break; |
918 | |
919 | if (valid_ao_ref_for_dse (ref: &write) |
920 | && stmt_kills_ref_p (stmt, &write)) |
921 | { |
922 | gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); |
923 | if (is_gimple_assign (gs: use_stmt)) |
924 | { |
925 | ao_ref lhs_ref; |
926 | ao_ref_init (&lhs_ref, gimple_assign_lhs (gs: use_stmt)); |
927 | if ((earlier_set == ao_ref_alias_set (&lhs_ref) |
928 | || alias_set_subset_of (ao_ref_alias_set (&lhs_ref), |
929 | earlier_set)) |
930 | && (earlier_base_set == ao_ref_base_alias_set (&lhs_ref) |
931 | || alias_set_subset_of |
932 | (ao_ref_base_alias_set (&lhs_ref), |
933 | earlier_base_set))) |
934 | delete_dead_or_redundant_assignment (&gsi, "redundant" , |
935 | need_eh_cleanup, |
936 | need_ab_cleanup); |
937 | } |
938 | else if (is_gimple_call (gs: use_stmt)) |
939 | { |
940 | if ((earlier_set == 0 |
941 | || alias_set_subset_of (0, earlier_set)) |
942 | && (earlier_base_set == 0 |
943 | || alias_set_subset_of (0, earlier_base_set))) |
944 | delete_dead_or_redundant_call (&gsi, "redundant" ); |
945 | } |
946 | else |
947 | gcc_unreachable (); |
948 | } |
949 | } |
950 | } |
951 | } |
952 | |
953 | /* Return whether PHI contains ARG as an argument. */ |
954 | |
955 | static bool |
956 | contains_phi_arg (gphi *phi, tree arg) |
957 | { |
958 | for (unsigned i = 0; i < gimple_phi_num_args (gs: phi); ++i) |
959 | if (gimple_phi_arg_def (gs: phi, index: 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 | 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 | gimple *temp; |
980 | int cnt = 0; |
981 | auto_bitmap visited; |
982 | std::unique_ptr<data_reference, void(*)(data_reference_p)> |
983 | dra (nullptr, free_data_ref); |
984 | |
985 | if (by_clobber_p) |
986 | *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 | do |
994 | { |
995 | gimple *use_stmt; |
996 | imm_use_iterator ui; |
997 | bool fail = false; |
998 | tree defvar; |
999 | |
1000 | if (gimple_code (g: temp) == GIMPLE_PHI) |
1001 | { |
1002 | defvar = PHI_RESULT (temp); |
1003 | bitmap_set_bit (visited, SSA_NAME_VERSION (defvar)); |
1004 | } |
1005 | else |
1006 | defvar = gimple_vdef (g: temp); |
1007 | |
1008 | auto_vec<gimple *, 10> defs; |
1009 | gphi *first_phi_def = NULL; |
1010 | gphi *last_phi_def = NULL; |
1011 | |
1012 | auto_vec<tree, 10> worklist; |
1013 | worklist.quick_push (obj: defvar); |
1014 | |
1015 | do |
1016 | { |
1017 | defvar = worklist.pop (); |
1018 | /* If we're instructed to stop walking at region boundary, do so. */ |
1019 | if (defvar == stop_at_vuse) |
1020 | return DSE_STORE_LIVE; |
1021 | |
1022 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
1023 | { |
1024 | /* Limit stmt walking. */ |
1025 | 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 | if (gimple_code (g: use_stmt) == GIMPLE_PHI) |
1036 | { |
1037 | /* Look through single-argument PHIs. */ |
1038 | if (gimple_phi_num_args (gs: use_stmt) == 1) |
1039 | worklist.safe_push (obj: gimple_phi_result (gs: use_stmt)); |
1040 | |
1041 | /* If we already visited this PHI ignore it for further |
1042 | processing. */ |
1043 | else if (!bitmap_bit_p (visited, |
1044 | 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 | if (dominated_by_p (CDI_DOMINATORS, gimple_bb (g: stmt), |
1052 | gimple_bb (g: use_stmt)) |
1053 | && !for_each_index (ref->ref ? &ref->ref : &ref->base, |
1054 | check_name, gimple_bb (g: use_stmt))) |
1055 | return DSE_STORE_LIVE; |
1056 | defs.safe_push (obj: use_stmt); |
1057 | if (!first_phi_def) |
1058 | first_phi_def = as_a <gphi *> (p: use_stmt); |
1059 | last_phi_def = as_a <gphi *> (p: use_stmt); |
1060 | } |
1061 | } |
1062 | /* If the statement is a use the store is not dead. */ |
1063 | else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
1064 | { |
1065 | if (dse_stmt_to_dr_map |
1066 | && ref->ref |
1067 | && is_gimple_assign (gs: use_stmt)) |
1068 | { |
1069 | if (!dra) |
1070 | dra.reset (p: create_data_ref (NULL, NULL, ref->ref, stmt, |
1071 | false, false)); |
1072 | bool existed_p; |
1073 | data_reference_p &drb |
1074 | = dse_stmt_to_dr_map->get_or_insert (k: use_stmt, |
1075 | existed: &existed_p); |
1076 | if (!existed_p) |
1077 | drb = create_data_ref (NULL, NULL, |
1078 | gimple_assign_rhs1 (gs: use_stmt), |
1079 | use_stmt, false, false); |
1080 | if (!dr_may_alias_p (dra.get (), drb, NULL)) |
1081 | { |
1082 | if (gimple_vdef (g: use_stmt)) |
1083 | defs.safe_push (obj: use_stmt); |
1084 | 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 | if (byte_tracking_enabled |
1094 | && is_gimple_assign (gs: use_stmt)) |
1095 | { |
1096 | ao_ref use_ref; |
1097 | ao_ref_init (&use_ref, gimple_assign_rhs1 (gs: use_stmt)); |
1098 | if (valid_ao_ref_for_dse (ref: &use_ref) |
1099 | && operand_equal_p (use_ref.base, ref->base, |
1100 | flags: OEP_ADDRESS_OF) |
1101 | && !live_bytes_read (use_ref: &use_ref, ref, live: live_bytes)) |
1102 | { |
1103 | /* If this is a store, remember it as we possibly |
1104 | need to walk the defs uses. */ |
1105 | if (gimple_vdef (g: use_stmt)) |
1106 | defs.safe_push (obj: use_stmt); |
1107 | 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 | 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 | else if (gimple_vdef (g: use_stmt)) |
1121 | defs.safe_push (obj: use_stmt); |
1122 | } |
1123 | } |
1124 | while (!fail && !worklist.is_empty ()); |
1125 | |
1126 | 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 | if (byte_tracking_enabled && !gimple_clobber_p (s: stmt)) |
1131 | 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 | if (defs.is_empty ()) |
1139 | { |
1140 | if (ref_may_alias_global_p (ref, false)) |
1141 | { |
1142 | 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 | if (EDGE_COUNT (def_bb->succs) == 0) |
1150 | if (gcall *last = dyn_cast <gcall *> (p: *gsi_last_bb (bb: def_bb))) |
1151 | if (gimple_call_builtin_p (last, BUILT_IN_UNREACHABLE) |
1152 | || gimple_call_builtin_p (last, |
1153 | BUILT_IN_UNREACHABLE_TRAP)) |
1154 | { |
1155 | if (by_clobber_p) |
1156 | *by_clobber_p = false; |
1157 | return DSE_STORE_DEAD; |
1158 | } |
1159 | return DSE_STORE_LIVE; |
1160 | } |
1161 | |
1162 | if (by_clobber_p) |
1163 | *by_clobber_p = false; |
1164 | return DSE_STORE_DEAD; |
1165 | } |
1166 | |
1167 | /* Process defs and remove those we need not process further. */ |
1168 | for (unsigned i = 0; i < defs.length ();) |
1169 | { |
1170 | gimple *def = defs[i]; |
1171 | gimple *use_stmt; |
1172 | use_operand_p use_p; |
1173 | tree vdef = (gimple_code (g: def) == GIMPLE_PHI |
1174 | ? gimple_phi_result (gs: def) : gimple_vdef (g: def)); |
1175 | 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 | if (stmt_kills_ref_p (def, ref)) |
1181 | { |
1182 | if (by_clobber_p && !gimple_clobber_p (s: def)) |
1183 | *by_clobber_p = false; |
1184 | defs.unordered_remove (ix: 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 | else if (has_zero_uses (var: vdef)) |
1189 | { |
1190 | /* But if the store is to global memory it is definitely |
1191 | not dead. */ |
1192 | if (ref_may_alias_global_p (ref, false)) |
1193 | return DSE_STORE_LIVE; |
1194 | defs.unordered_remove (ix: 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 | else if (single_imm_use (var: vdef, use_p: &use_p, stmt: &use_stmt) |
1203 | && (use_stmt == first_phi_def |
1204 | || use_stmt == last_phi_def |
1205 | || (gimple_code (g: use_stmt) == GIMPLE_PHI |
1206 | && bitmap_bit_p (visited, |
1207 | SSA_NAME_VERSION |
1208 | (PHI_RESULT (use_stmt)))))) |
1209 | { |
1210 | defs.unordered_remove (ix: i); |
1211 | if (def == first_phi_def) |
1212 | first_phi_def = NULL; |
1213 | else if (def == last_phi_def) |
1214 | 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 | else if ((phi_def = dyn_cast <gphi *> (p: def)) |
1219 | && ((last_phi_def |
1220 | && phi_def != last_phi_def |
1221 | && contains_phi_arg (phi: phi_def, |
1222 | arg: gimple_phi_result (gs: last_phi_def))) |
1223 | || (first_phi_def |
1224 | && phi_def != first_phi_def |
1225 | && contains_phi_arg |
1226 | (phi: phi_def, arg: gimple_phi_result (gs: first_phi_def))))) |
1227 | { |
1228 | defs.unordered_remove (ix: i); |
1229 | if (phi_def == first_phi_def) |
1230 | first_phi_def = NULL; |
1231 | else if (phi_def == last_phi_def) |
1232 | last_phi_def = NULL; |
1233 | } |
1234 | else |
1235 | ++i; |
1236 | } |
1237 | |
1238 | /* If all defs kill the ref we are done. */ |
1239 | if (defs.is_empty ()) |
1240 | return DSE_STORE_DEAD; |
1241 | /* If more than one def survives fail. */ |
1242 | 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 | if (byte_tracking_enabled && !gimple_clobber_p (s: stmt)) |
1247 | return DSE_STORE_MAYBE_PARTIAL_DEAD; |
1248 | return DSE_STORE_LIVE; |
1249 | } |
1250 | temp = defs[0]; |
1251 | |
1252 | /* Track partial kills. */ |
1253 | if (byte_tracking_enabled) |
1254 | { |
1255 | clear_bytes_written_by (live_bytes, stmt: temp, ref); |
1256 | if (bitmap_empty_p (live_bytes)) |
1257 | { |
1258 | if (by_clobber_p && !gimple_clobber_p (s: temp)) |
1259 | *by_clobber_p = false; |
1260 | return DSE_STORE_DEAD; |
1261 | } |
1262 | } |
1263 | } |
1264 | /* Continue walking until there are no more live bytes. */ |
1265 | while (1); |
1266 | } |
1267 | |
1268 | |
1269 | /* Delete a dead call at GSI, which is mem* call of some kind. */ |
1270 | static void |
1271 | delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type) |
1272 | { |
1273 | gimple *stmt = gsi_stmt (i: *gsi); |
1274 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1275 | { |
1276 | fprintf (stream: dump_file, format: " Deleted %s call: " , type); |
1277 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
1278 | fprintf (stream: dump_file, format: "\n" ); |
1279 | } |
1280 | |
1281 | basic_block bb = gimple_bb (g: stmt); |
1282 | tree lhs = gimple_call_lhs (gs: stmt); |
1283 | if (lhs) |
1284 | { |
1285 | tree ptr = gimple_call_arg (gs: stmt, index: 0); |
1286 | gimple *new_stmt = gimple_build_assign (lhs, ptr); |
1287 | unlink_stmt_vdef (stmt); |
1288 | if (gsi_replace (gsi, new_stmt, true)) |
1289 | 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 | unlink_stmt_vdef (stmt); |
1295 | |
1296 | /* Remove the dead store. */ |
1297 | if (gsi_remove (gsi, true)) |
1298 | bitmap_set_bit (need_eh_cleanup, bb->index); |
1299 | release_defs (stmt); |
1300 | } |
1301 | } |
1302 | |
1303 | /* Delete a dead store at GSI, which is a gimple assignment. */ |
1304 | |
1305 | void |
1306 | 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 | gimple *stmt = gsi_stmt (i: *gsi); |
1312 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1313 | { |
1314 | fprintf (stream: dump_file, format: " Deleted %s store: " , type); |
1315 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
1316 | fprintf (stream: dump_file, format: "\n" ); |
1317 | } |
1318 | |
1319 | /* Then we need to fix the operand of the consuming stmt. */ |
1320 | unlink_stmt_vdef (stmt); |
1321 | |
1322 | /* Remove the dead store. */ |
1323 | basic_block bb = gimple_bb (g: stmt); |
1324 | if (need_ab_cleanup && stmt_can_make_abnormal_goto (stmt)) |
1325 | bitmap_set_bit (need_ab_cleanup, bb->index); |
1326 | if (gsi_remove (gsi, true) && need_eh_cleanup) |
1327 | 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 | release_defs (stmt); |
1332 | } |
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 | dse_optimize_call (gimple_stmt_iterator *gsi, sbitmap live_bytes) |
1340 | { |
1341 | gcall *stmt = dyn_cast <gcall *> (p: gsi_stmt (i: *gsi)); |
1342 | |
1343 | if (!stmt) |
1344 | return false; |
1345 | |
1346 | tree callee = gimple_call_fndecl (gs: stmt); |
1347 | |
1348 | if (!callee) |
1349 | return false; |
1350 | |
1351 | /* Pure/const functions are optimized by normal DCE |
1352 | or handled as store above. */ |
1353 | int flags = gimple_call_flags (stmt); |
1354 | if ((flags & (ECF_PURE|ECF_CONST|ECF_NOVOPS)) |
1355 | && !(flags & (ECF_LOOPING_CONST_OR_PURE))) |
1356 | return false; |
1357 | |
1358 | cgraph_node *node = cgraph_node::get (decl: callee); |
1359 | if (!node) |
1360 | return false; |
1361 | |
1362 | if (stmt_could_throw_p (cfun, stmt) |
1363 | && !cfun->can_delete_dead_exceptions) |
1364 | return false; |
1365 | |
1366 | /* If return value is used the call is not dead. */ |
1367 | tree lhs = gimple_call_lhs (gs: stmt); |
1368 | if (lhs && TREE_CODE (lhs) == SSA_NAME) |
1369 | { |
1370 | imm_use_iterator ui; |
1371 | gimple *use_stmt; |
1372 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, lhs) |
1373 | if (!is_gimple_debug (gs: use_stmt)) |
1374 | return false; |
1375 | } |
1376 | |
1377 | /* Verify that there are no side-effects except for return value |
1378 | and memory writes tracked by modref. */ |
1379 | modref_summary *summary = get_modref_function_summary (func: node); |
1380 | if (!summary || !summary->try_dse) |
1381 | return false; |
1382 | |
1383 | bool by_clobber_p = false; |
1384 | |
1385 | /* Walk all memory writes and verify that they are dead. */ |
1386 | for (auto base_node : summary->stores->bases) |
1387 | for (auto ref_node : base_node->refs) |
1388 | for (auto access_node : ref_node->accesses) |
1389 | { |
1390 | tree arg = access_node.get_call_arg (stmt); |
1391 | |
1392 | if (!arg || !POINTER_TYPE_P (TREE_TYPE (arg))) |
1393 | return false; |
1394 | |
1395 | if (integer_zerop (arg) |
1396 | && !targetm.addr_space.zero_address_valid |
1397 | (TYPE_ADDR_SPACE (TREE_TYPE (arg)))) |
1398 | continue; |
1399 | |
1400 | ao_ref ref; |
1401 | |
1402 | if (!access_node.get_ao_ref (stmt, ref: &ref)) |
1403 | return false; |
1404 | ref.ref_alias_set = ref_node->ref; |
1405 | ref.base_alias_set = base_node->base; |
1406 | |
1407 | bool byte_tracking_enabled |
1408 | = setup_live_bytes_from_ref (ref: &ref, live_bytes); |
1409 | enum dse_store_status store_status; |
1410 | |
1411 | store_status = dse_classify_store (ref: &ref, stmt, |
1412 | byte_tracking_enabled, |
1413 | live_bytes, by_clobber_p: &by_clobber_p); |
1414 | if (store_status != DSE_STORE_DEAD) |
1415 | return false; |
1416 | } |
1417 | delete_dead_or_redundant_assignment (gsi, type: "dead" , need_eh_cleanup, |
1418 | need_ab_cleanup); |
1419 | 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 | dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes) |
1435 | { |
1436 | gimple *stmt = gsi_stmt (i: *gsi); |
1437 | |
1438 | /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
1439 | if (gimple_has_volatile_ops (stmt) |
1440 | && (!gimple_clobber_p (s: stmt) |
1441 | || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) |
1442 | return; |
1443 | |
1444 | 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 | if (!initialize_ao_ref_for_dse (stmt, write: &ref, may_def_ok: true)) |
1450 | { |
1451 | dse_optimize_call (gsi, live_bytes); |
1452 | return; |
1453 | } |
1454 | |
1455 | /* We know we have virtual definitions. We can handle assignments and |
1456 | some builtin calls. */ |
1457 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) |
1458 | { |
1459 | tree fndecl = gimple_call_fndecl (gs: stmt); |
1460 | switch (DECL_FUNCTION_CODE (decl: fndecl)) |
1461 | { |
1462 | case BUILT_IN_MEMCPY: |
1463 | case BUILT_IN_MEMMOVE: |
1464 | case BUILT_IN_STRNCPY: |
1465 | case BUILT_IN_MEMSET: |
1466 | case BUILT_IN_MEMCPY_CHK: |
1467 | case BUILT_IN_MEMMOVE_CHK: |
1468 | case BUILT_IN_STRNCPY_CHK: |
1469 | case BUILT_IN_MEMSET_CHK: |
1470 | { |
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 | tree size = gimple_call_arg (gs: stmt, index: 2); |
1475 | if (integer_zerop (size)) |
1476 | { |
1477 | delete_dead_or_redundant_call (gsi, type: "dead" ); |
1478 | 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 | if ((DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_MEMSET |
1485 | || DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_MEMSET_CHK) |
1486 | && integer_zerop (gimple_call_arg (gs: stmt, index: 1))) |
1487 | dse_optimize_redundant_stores (stmt); |
1488 | |
1489 | enum dse_store_status store_status; |
1490 | bool byte_tracking_enabled |
1491 | = setup_live_bytes_from_ref (ref: &ref, live_bytes); |
1492 | store_status = dse_classify_store (ref: &ref, stmt, |
1493 | byte_tracking_enabled, |
1494 | live_bytes); |
1495 | if (store_status == DSE_STORE_LIVE) |
1496 | return; |
1497 | |
1498 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
1499 | { |
1500 | maybe_trim_memstar_call (ref: &ref, live: live_bytes, stmt); |
1501 | return; |
1502 | } |
1503 | |
1504 | if (store_status == DSE_STORE_DEAD) |
1505 | delete_dead_or_redundant_call (gsi, type: "dead" ); |
1506 | return; |
1507 | } |
1508 | |
1509 | case BUILT_IN_CALLOC: |
1510 | /* We already know the arguments are integer constants. */ |
1511 | dse_optimize_redundant_stores (stmt); |
1512 | return; |
1513 | |
1514 | default: |
1515 | return; |
1516 | } |
1517 | } |
1518 | else if (is_gimple_call (gs: stmt) |
1519 | && gimple_call_internal_p (gs: stmt)) |
1520 | { |
1521 | switch (gimple_call_internal_fn (gs: stmt)) |
1522 | { |
1523 | case IFN_LEN_STORE: |
1524 | case IFN_MASK_STORE: |
1525 | case IFN_MASK_LEN_STORE: |
1526 | { |
1527 | enum dse_store_status store_status; |
1528 | store_status = dse_classify_store (ref: &ref, stmt, byte_tracking_enabled: false, live_bytes); |
1529 | if (store_status == DSE_STORE_DEAD) |
1530 | delete_dead_or_redundant_call (gsi, type: "dead" ); |
1531 | return; |
1532 | } |
1533 | default:; |
1534 | } |
1535 | } |
1536 | |
1537 | 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 | if (gimple_assign_single_p (gs: stmt) |
1543 | && initializer_zerop (gimple_assign_rhs1 (gs: stmt))) |
1544 | dse_optimize_redundant_stores (stmt); |
1545 | |
1546 | /* Self-assignments are zombies. */ |
1547 | if (is_gimple_assign (gs: stmt) |
1548 | && operand_equal_p (gimple_assign_rhs1 (gs: stmt), |
1549 | gimple_assign_lhs (gs: stmt), flags: 0)) |
1550 | ; |
1551 | else |
1552 | { |
1553 | bool byte_tracking_enabled |
1554 | = setup_live_bytes_from_ref (ref: &ref, live_bytes); |
1555 | enum dse_store_status store_status; |
1556 | store_status = dse_classify_store (ref: &ref, stmt, |
1557 | byte_tracking_enabled, |
1558 | live_bytes, by_clobber_p: &by_clobber_p); |
1559 | if (store_status == DSE_STORE_LIVE) |
1560 | return; |
1561 | |
1562 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
1563 | { |
1564 | maybe_trim_partially_dead_store (ref: &ref, live: live_bytes, stmt); |
1565 | 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 | if (gimple_clobber_p (s: stmt) |
1574 | && !by_clobber_p) |
1575 | return; |
1576 | |
1577 | if (is_gimple_call (gs: stmt) |
1578 | && (gimple_has_side_effects (stmt) |
1579 | || (stmt_could_throw_p (fun, stmt) |
1580 | && !fun->can_delete_dead_exceptions))) |
1581 | { |
1582 | /* See if we can remove complete call. */ |
1583 | 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 | if (gimple_call_return_slot_opt_p (s: as_a <gcall *>(p: stmt)) |
1588 | && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt))) |
1589 | || !poly_int_tree_p |
1590 | (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt)))))) |
1591 | return; |
1592 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1593 | { |
1594 | fprintf (stream: dump_file, format: " Deleted dead store in call LHS: " ); |
1595 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
1596 | fprintf (stream: dump_file, format: "\n" ); |
1597 | } |
1598 | gimple_call_set_lhs (gs: stmt, NULL_TREE); |
1599 | update_stmt (s: stmt); |
1600 | } |
1601 | else if (!stmt_could_throw_p (fun, stmt) |
1602 | || fun->can_delete_dead_exceptions) |
1603 | delete_dead_or_redundant_assignment (gsi, type: "dead" , need_eh_cleanup, |
1604 | need_ab_cleanup); |
1605 | } |
1606 | |
1607 | namespace { |
1608 | |
1609 | const pass_data pass_data_dse = |
1610 | { |
1611 | .type: GIMPLE_PASS, /* type */ |
1612 | .name: "dse" , /* name */ |
1613 | .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */ |
1614 | .tv_id: TV_TREE_DSE, /* tv_id */ |
1615 | .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */ |
1616 | .properties_provided: 0, /* properties_provided */ |
1617 | .properties_destroyed: 0, /* properties_destroyed */ |
1618 | .todo_flags_start: 0, /* todo_flags_start */ |
1619 | .todo_flags_finish: 0, /* todo_flags_finish */ |
1620 | }; |
1621 | |
1622 | class pass_dse : public gimple_opt_pass |
1623 | { |
1624 | public: |
1625 | pass_dse (gcc::context *ctxt) |
1626 | : gimple_opt_pass (pass_data_dse, ctxt), use_dr_analysis_p (false) |
1627 | {} |
1628 | |
1629 | /* opt_pass methods: */ |
1630 | opt_pass * clone () final override { return new pass_dse (m_ctxt); } |
1631 | void set_pass_param (unsigned n, bool param) final override |
1632 | { |
1633 | gcc_assert (n == 0); |
1634 | use_dr_analysis_p = param; |
1635 | } |
1636 | 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 | pass_dse::execute (function *fun) |
1645 | { |
1646 | unsigned todo = 0; |
1647 | bool released_def = false; |
1648 | |
1649 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
1650 | need_ab_cleanup = BITMAP_ALLOC (NULL); |
1651 | auto_sbitmap live_bytes (param_dse_max_object_size); |
1652 | if (flag_expensive_optimizations && use_dr_analysis_p) |
1653 | dse_stmt_to_dr_map = new hash_map<gimple *, data_reference_p>; |
1654 | |
1655 | renumber_gimple_stmt_uids (fun); |
1656 | |
1657 | calculate_dominance_info (CDI_DOMINATORS); |
1658 | |
1659 | /* Dead store elimination is fundamentally a reverse program order walk. */ |
1660 | int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS); |
1661 | int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false); |
1662 | for (int i = n; i != 0; --i) |
1663 | { |
1664 | basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]); |
1665 | gimple_stmt_iterator gsi; |
1666 | |
1667 | for (gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi);) |
1668 | { |
1669 | gimple *stmt = gsi_stmt (i: gsi); |
1670 | |
1671 | if (gimple_vdef (g: stmt)) |
1672 | dse_optimize_stmt (fun, gsi: &gsi, live_bytes); |
1673 | else if (def_operand_p |
1674 | 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 | if (has_zero_uses (DEF_FROM_PTR (def_p)) |
1679 | && !gimple_has_side_effects (stmt) |
1680 | && !is_ctrl_altering_stmt (stmt) |
1681 | && (!stmt_could_throw_p (fun, stmt) |
1682 | || fun->can_delete_dead_exceptions)) |
1683 | { |
1684 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1685 | { |
1686 | fprintf (stream: dump_file, format: " Deleted trivially dead stmt: " ); |
1687 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
1688 | fprintf (stream: dump_file, format: "\n" ); |
1689 | } |
1690 | if (gsi_remove (&gsi, true) && need_eh_cleanup) |
1691 | bitmap_set_bit (need_eh_cleanup, bb->index); |
1692 | release_defs (stmt); |
1693 | released_def = true; |
1694 | } |
1695 | } |
1696 | if (gsi_end_p (i: gsi)) |
1697 | gsi = gsi_last_bb (bb); |
1698 | else |
1699 | gsi_prev (i: &gsi); |
1700 | } |
1701 | bool removed_phi = false; |
1702 | for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (i: si);) |
1703 | { |
1704 | gphi *phi = si.phi (); |
1705 | if (has_zero_uses (var: gimple_phi_result (gs: phi))) |
1706 | { |
1707 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1708 | { |
1709 | fprintf (stream: dump_file, format: " Deleted trivially dead PHI: " ); |
1710 | print_gimple_stmt (dump_file, phi, 0, dump_flags); |
1711 | fprintf (stream: dump_file, format: "\n" ); |
1712 | } |
1713 | remove_phi_node (&si, true); |
1714 | removed_phi = true; |
1715 | released_def = true; |
1716 | } |
1717 | else |
1718 | gsi_next (i: &si); |
1719 | } |
1720 | if (removed_phi && gimple_seq_empty_p (s: phi_nodes (bb))) |
1721 | todo |= TODO_cleanup_cfg; |
1722 | } |
1723 | free (ptr: rpo); |
1724 | |
1725 | /* Removal of stores may make some EH edges dead. Purge such edges from |
1726 | the CFG as needed. */ |
1727 | if (!bitmap_empty_p (map: need_eh_cleanup)) |
1728 | { |
1729 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
1730 | todo |= TODO_cleanup_cfg; |
1731 | } |
1732 | if (!bitmap_empty_p (map: need_ab_cleanup)) |
1733 | { |
1734 | gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); |
1735 | todo |= TODO_cleanup_cfg; |
1736 | } |
1737 | |
1738 | BITMAP_FREE (need_eh_cleanup); |
1739 | BITMAP_FREE (need_ab_cleanup); |
1740 | |
1741 | if (released_def) |
1742 | free_numbers_of_iterations_estimates (fun); |
1743 | |
1744 | if (flag_expensive_optimizations && use_dr_analysis_p) |
1745 | { |
1746 | for (auto i = dse_stmt_to_dr_map->begin (); |
1747 | i != dse_stmt_to_dr_map->end (); ++i) |
1748 | free_data_ref ((*i).second); |
1749 | delete dse_stmt_to_dr_map; |
1750 | dse_stmt_to_dr_map = NULL; |
1751 | } |
1752 | |
1753 | return todo; |
1754 | } |
1755 | |
1756 | } // anon namespace |
1757 | |
1758 | gimple_opt_pass * |
1759 | make_pass_dse (gcc::context *ctxt) |
1760 | { |
1761 | return new pass_dse (ctxt); |
1762 | } |
1763 | |