]>
Commit | Line | Data |
---|---|---|
3fe0ddc8 | 1 | /* Dead and redundant store elimination |
a5544970 | 2 | Copyright (C) 2004-2019 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
957060b5 | 24 | #include "rtl.h" |
6de9cd9a | 25 | #include "tree.h" |
c7131fb2 | 26 | #include "gimple.h" |
957060b5 | 27 | #include "tree-pass.h" |
c7131fb2 | 28 | #include "ssa.h" |
957060b5 | 29 | #include "gimple-pretty-print.h" |
40e23961 | 30 | #include "fold-const.h" |
5be5c238 | 31 | #include "gimple-iterator.h" |
442b4905 | 32 | #include "tree-cfg.h" |
442b4905 | 33 | #include "tree-dfa.h" |
6de9cd9a | 34 | #include "domwalk.h" |
4484a35a | 35 | #include "tree-cfgcleanup.h" |
d155c6fe | 36 | #include "params.h" |
9e59e99a | 37 | #include "alias.h" |
311eb816 | 38 | #include "tree-ssa-loop.h" |
6de9cd9a DN |
39 | |
40 | /* This file implements dead store elimination. | |
41 | ||
42 | A dead store is a store into a memory location which will later be | |
43 | overwritten by another store without any intervening loads. In this | |
3fe0ddc8 JL |
44 | case the earlier store can be deleted or trimmed if the store |
45 | was partially dead. | |
46 | ||
47 | A redundant store is a store into a memory location which stores | |
48 | the exact same value as a prior store to the same memory location. | |
49 | While this can often be handled by dead store elimination, removing | |
50 | the redundant store is often better than removing or trimming the | |
51 | dead store. | |
6de9cd9a DN |
52 | |
53 | In our SSA + virtual operand world we use immediate uses of virtual | |
3fe0ddc8 | 54 | operands to detect these cases. If a store's virtual definition |
6de9cd9a | 55 | is used precisely once by a later store to the same location which |
3fe0ddc8 JL |
56 | post dominates the first store, then the first store is dead. If |
57 | the data stored is the same, then the second store is redundant. | |
6de9cd9a DN |
58 | |
59 | The single use of the store's virtual definition ensures that | |
60 | there are no intervening aliased loads and the requirement that | |
61 | the second load post dominate the first ensures that if the earlier | |
62 | store executes, then the later stores will execute before the function | |
63 | exits. | |
64 | ||
65 | It may help to think of this as first moving the earlier store to | |
66 | the point immediately before the later store. Again, the single | |
61ada8ae | 67 | use of the virtual definition and the post-dominance relationship |
b8698a0f | 68 | ensure that such movement would be safe. Clearly if there are |
3fe0ddc8 JL |
69 | back to back stores, then the second is makes the first dead. If |
70 | the second store stores the same value, then the second store is | |
71 | redundant. | |
6de9cd9a DN |
72 | |
73 | Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
74 | may also help in understanding this code since it discusses the | |
75 | relationship between dead store and redundant load elimination. In | |
76 | fact, they are the same transformation applied to different views of | |
77 | the CFG. */ | |
726a989a | 78 | |
08c1638d JL |
79 | static void delete_dead_or_redundant_assignment (gimple_stmt_iterator *, const char *); |
80 | static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *); | |
6de9cd9a | 81 | |
caaf13d3 JL |
82 | /* Bitmap of blocks that have had EH statements cleaned. We should |
83 | remove their dead edges eventually. */ | |
84 | static bitmap need_eh_cleanup; | |
85 | ||
d155c6fe JL |
86 | /* Return value from dse_classify_store */ |
87 | enum dse_store_status | |
88 | { | |
89 | DSE_STORE_LIVE, | |
90 | DSE_STORE_MAYBE_PARTIAL_DEAD, | |
91 | DSE_STORE_DEAD | |
92 | }; | |
93 | ||
94 | /* STMT is a statement that may write into memory. Analyze it and | |
95 | initialize WRITE to describe how STMT affects memory. | |
96 | ||
97 | Return TRUE if the the statement was analyzed, FALSE otherwise. | |
98 | ||
99 | It is always safe to return FALSE. But typically better optimziation | |
100 | can be achieved by analyzing more statements. */ | |
101 | ||
102 | static bool | |
103 | initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) | |
104 | { | |
105 | /* It's advantageous to handle certain mem* functions. */ | |
106 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
107 | { | |
108 | switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
109 | { | |
caffb6e5 JL |
110 | case BUILT_IN_MEMCPY: |
111 | case BUILT_IN_MEMMOVE: | |
112 | case BUILT_IN_MEMSET: | |
113 | case BUILT_IN_MEMCPY_CHK: | |
114 | case BUILT_IN_MEMMOVE_CHK: | |
115 | case BUILT_IN_MEMSET_CHK: | |
192ece9e JL |
116 | case BUILT_IN_STRNCPY: |
117 | case BUILT_IN_STRNCPY_CHK: | |
caffb6e5 | 118 | { |
192ece9e | 119 | tree size = gimple_call_arg (stmt, 2); |
caffb6e5 JL |
120 | tree ptr = gimple_call_arg (stmt, 0); |
121 | ao_ref_init_from_ptr_and_size (write, ptr, size); | |
122 | return true; | |
123 | } | |
3fe0ddc8 | 124 | |
caffb6e5 JL |
125 | /* A calloc call can never be dead, but it can make |
126 | subsequent stores redundant if they store 0 into | |
127 | the same memory locations. */ | |
128 | case BUILT_IN_CALLOC: | |
129 | { | |
130 | tree nelem = gimple_call_arg (stmt, 0); | |
131 | tree selem = gimple_call_arg (stmt, 1); | |
132 | tree lhs; | |
133 | if (TREE_CODE (nelem) == INTEGER_CST | |
134 | && TREE_CODE (selem) == INTEGER_CST | |
135 | && (lhs = gimple_call_lhs (stmt)) != NULL_TREE) | |
136 | { | |
137 | tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem), | |
138 | nelem, selem); | |
139 | ao_ref_init_from_ptr_and_size (write, lhs, size); | |
140 | return true; | |
141 | } | |
142 | } | |
3fe0ddc8 | 143 | |
caffb6e5 JL |
144 | default: |
145 | break; | |
d155c6fe JL |
146 | } |
147 | } | |
148 | else if (is_gimple_assign (stmt)) | |
149 | { | |
150 | ao_ref_init (write, gimple_assign_lhs (stmt)); | |
151 | return true; | |
152 | } | |
153 | return false; | |
154 | } | |
155 | ||
156 | /* Given REF from the the alias oracle, return TRUE if it is a valid | |
157 | memory reference for dead store elimination, false otherwise. | |
158 | ||
159 | In particular, the reference must have a known base, known maximum | |
160 | size, start at a byte offset and have a size that is one or more | |
161 | bytes. */ | |
162 | ||
163 | static bool | |
164 | valid_ao_ref_for_dse (ao_ref *ref) | |
165 | { | |
166 | return (ao_ref_base (ref) | |
b9c25734 RS |
167 | && known_size_p (ref->max_size) |
168 | && maybe_ne (ref->size, 0) | |
169 | && known_eq (ref->max_size, ref->size) | |
170 | && known_ge (ref->offset, 0) | |
171 | && multiple_p (ref->offset, BITS_PER_UNIT) | |
172 | && multiple_p (ref->size, BITS_PER_UNIT)); | |
d155c6fe JL |
173 | } |
174 | ||
4a110e34 RS |
175 | /* Try to normalize COPY (an ao_ref) relative to REF. Essentially when we are |
176 | done COPY will only refer bytes found within REF. Return true if COPY | |
177 | is known to intersect at least one byte of REF. */ | |
d155c6fe | 178 | |
4a110e34 | 179 | static bool |
d155c6fe JL |
180 | normalize_ref (ao_ref *copy, ao_ref *ref) |
181 | { | |
b9c25734 RS |
182 | if (!ordered_p (copy->offset, ref->offset)) |
183 | return false; | |
184 | ||
d155c6fe JL |
185 | /* If COPY starts before REF, then reset the beginning of |
186 | COPY to match REF and decrease the size of COPY by the | |
187 | number of bytes removed from COPY. */ | |
b9c25734 | 188 | if (maybe_lt (copy->offset, ref->offset)) |
d155c6fe | 189 | { |
b9c25734 RS |
190 | poly_int64 diff = ref->offset - copy->offset; |
191 | if (maybe_le (copy->size, diff)) | |
4a110e34 RS |
192 | return false; |
193 | copy->size -= diff; | |
d155c6fe JL |
194 | copy->offset = ref->offset; |
195 | } | |
196 | ||
b9c25734 RS |
197 | poly_int64 diff = copy->offset - ref->offset; |
198 | if (maybe_le (ref->size, diff)) | |
4a110e34 RS |
199 | return false; |
200 | ||
d155c6fe | 201 | /* If COPY extends beyond REF, chop off its size appropriately. */ |
b9c25734 RS |
202 | poly_int64 limit = ref->size - diff; |
203 | if (!ordered_p (limit, copy->size)) | |
204 | return false; | |
205 | ||
206 | if (maybe_gt (copy->size, limit)) | |
4a110e34 RS |
207 | copy->size = limit; |
208 | return true; | |
d155c6fe JL |
209 | } |
210 | ||
211 | /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base | |
212 | address written by STMT must match the one found in REF, which must | |
213 | have its base address previously initialized. | |
214 | ||
215 | This routine must be conservative. If we don't know the offset or | |
216 | actual size written, assume nothing was written. */ | |
217 | ||
218 | static void | |
219 | clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) | |
220 | { | |
221 | ao_ref write; | |
222 | if (!initialize_ao_ref_for_dse (stmt, &write)) | |
223 | return; | |
224 | ||
225 | /* Verify we have the same base memory address, the write | |
226 | has a known size and overlaps with REF. */ | |
b9c25734 | 227 | HOST_WIDE_INT start, size; |
d155c6fe | 228 | if (valid_ao_ref_for_dse (&write) |
06b909b0 | 229 | && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) |
b9c25734 RS |
230 | && known_eq (write.size, write.max_size) |
231 | && normalize_ref (&write, ref) | |
232 | && (write.offset - ref->offset).is_constant (&start) | |
233 | && write.size.is_constant (&size)) | |
234 | bitmap_clear_range (live_bytes, start / BITS_PER_UNIT, | |
235 | size / BITS_PER_UNIT); | |
d155c6fe JL |
236 | } |
237 | ||
238 | /* REF is a memory write. Extract relevant information from it and | |
239 | initialize the LIVE_BYTES bitmap. If successful, return TRUE. | |
240 | Otherwise return FALSE. */ | |
241 | ||
242 | static bool | |
243 | setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | |
244 | { | |
b9c25734 | 245 | HOST_WIDE_INT const_size; |
d155c6fe | 246 | if (valid_ao_ref_for_dse (ref) |
b9c25734 RS |
247 | && ref->size.is_constant (&const_size) |
248 | && (const_size / BITS_PER_UNIT | |
d155c6fe JL |
249 | <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) |
250 | { | |
251 | bitmap_clear (live_bytes); | |
b9c25734 | 252 | bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); |
d155c6fe JL |
253 | return true; |
254 | } | |
255 | return false; | |
256 | } | |
257 | ||
258 | /* Compute the number of elements that we can trim from the head and | |
259 | tail of ORIG resulting in a bitmap that is a superset of LIVE. | |
260 | ||
261 | Store the number of elements trimmed from the head and tail in | |
a59afbe2 JL |
262 | TRIM_HEAD and TRIM_TAIL. |
263 | ||
264 | STMT is the statement being trimmed and is used for debugging dump | |
265 | output only. */ | |
d155c6fe JL |
266 | |
267 | static void | |
a59afbe2 JL |
268 | compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
269 | gimple *stmt) | |
d155c6fe JL |
270 | { |
271 | /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap | |
272 | extends through ref->size. So we know that in the original bitmap | |
273 | bits 0..ref->size were true. We don't actually need the bitmap, just | |
274 | the REF to compute the trims. */ | |
275 | ||
276 | /* Now identify how much, if any of the tail we can chop off. */ | |
b9c25734 | 277 | HOST_WIDE_INT const_size; |
99e87c0e | 278 | int last_live = bitmap_last_set_bit (live); |
b9c25734 RS |
279 | if (ref->size.is_constant (&const_size)) |
280 | { | |
281 | int last_orig = (const_size / BITS_PER_UNIT) - 1; | |
99e87c0e JL |
282 | /* We can leave inconvenient amounts on the tail as |
283 | residual handling in mem* and str* functions is usually | |
284 | reasonably efficient. */ | |
285 | *trim_tail = last_orig - last_live; | |
36d2d101 BE |
286 | |
287 | /* But don't trim away out of bounds accesses, as this defeats | |
a1ae0cbd JL |
288 | proper warnings. |
289 | ||
290 | We could have a type with no TYPE_SIZE_UNIT or we could have a VLA | |
291 | where TYPE_SIZE_UNIT is not a constant. */ | |
36d2d101 | 292 | if (*trim_tail |
6a2a6928 | 293 | && TYPE_SIZE_UNIT (TREE_TYPE (ref->base)) |
a1ae0cbd | 294 | && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST |
36d2d101 BE |
295 | && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)), |
296 | last_orig) <= 0) | |
297 | *trim_tail = 0; | |
b9c25734 RS |
298 | } |
299 | else | |
300 | *trim_tail = 0; | |
d155c6fe JL |
301 | |
302 | /* Identify how much, if any of the head we can chop off. */ | |
303 | int first_orig = 0; | |
304 | int first_live = bitmap_first_set_bit (live); | |
99e87c0e JL |
305 | *trim_head = first_live - first_orig; |
306 | ||
307 | /* If more than a word remains, then make sure to keep the | |
308 | starting point at least word aligned. */ | |
309 | if (last_live - first_live > UNITS_PER_WORD) | |
efae2f50 | 310 | *trim_head &= ~(UNITS_PER_WORD - 1); |
a59afbe2 JL |
311 | |
312 | if ((*trim_head || *trim_tail) | |
313 | && dump_file && (dump_flags & TDF_DETAILS)) | |
314 | { | |
315 | fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", | |
316 | *trim_head, *trim_tail); | |
ef6cb4c7 | 317 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
a59afbe2 JL |
318 | fprintf (dump_file, "\n"); |
319 | } | |
d155c6fe JL |
320 | } |
321 | ||
322 | /* STMT initializes an object from COMPLEX_CST where one or more of the | |
323 | bytes written may be dead stores. REF is a representation of the | |
324 | memory written. LIVE is the bitmap of stores that are actually live. | |
325 | ||
326 | Attempt to rewrite STMT so that only the real or imaginary part of | |
327 | the object is actually stored. */ | |
328 | ||
329 | static void | |
330 | maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
331 | { | |
332 | int trim_head, trim_tail; | |
a59afbe2 | 333 | compute_trims (ref, live, &trim_head, &trim_tail, stmt); |
d155c6fe JL |
334 | |
335 | /* The amount of data trimmed from the head or tail must be at | |
336 | least half the size of the object to ensure we're trimming | |
337 | the entire real or imaginary half. By writing things this | |
338 | way we avoid more O(n) bitmap operations. */ | |
b9c25734 | 339 | if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) |
d155c6fe JL |
340 | { |
341 | /* TREE_REALPART is live */ | |
342 | tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | |
343 | tree y = gimple_assign_lhs (stmt); | |
344 | y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | |
345 | gimple_assign_set_lhs (stmt, y); | |
346 | gimple_assign_set_rhs1 (stmt, x); | |
347 | } | |
b9c25734 | 348 | else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) |
d155c6fe JL |
349 | { |
350 | /* TREE_IMAGPART is live */ | |
351 | tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | |
352 | tree y = gimple_assign_lhs (stmt); | |
353 | y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | |
354 | gimple_assign_set_lhs (stmt, y); | |
355 | gimple_assign_set_rhs1 (stmt, x); | |
356 | } | |
357 | ||
358 | /* Other cases indicate parts of both the real and imag subobjects | |
359 | are live. We do not try to optimize those cases. */ | |
360 | } | |
361 | ||
9e59e99a JL |
362 | /* STMT initializes an object using a CONSTRUCTOR where one or more of the |
363 | bytes written are dead stores. ORIG is the bitmap of bytes stored by | |
364 | STMT. LIVE is the bitmap of stores that are actually live. | |
365 | ||
366 | Attempt to rewrite STMT so that only the real or imaginary part of | |
367 | the object is actually stored. | |
368 | ||
369 | The most common case for getting here is a CONSTRUCTOR with no elements | |
370 | being used to zero initialize an object. We do not try to handle other | |
371 | cases as those would force us to fully cover the object with the | |
372 | CONSTRUCTOR node except for the components that are dead. */ | |
373 | ||
374 | static void | |
375 | maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
376 | { | |
377 | tree ctor = gimple_assign_rhs1 (stmt); | |
378 | ||
379 | /* This is the only case we currently handle. It actually seems to | |
380 | catch most cases of actual interest. */ | |
381 | gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); | |
382 | ||
383 | int head_trim = 0; | |
384 | int tail_trim = 0; | |
a59afbe2 | 385 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
9e59e99a JL |
386 | |
387 | /* Now we want to replace the constructor initializer | |
388 | with memset (object + head_trim, 0, size - head_trim - tail_trim). */ | |
389 | if (head_trim || tail_trim) | |
390 | { | |
391 | /* We want &lhs for the MEM_REF expression. */ | |
392 | tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); | |
393 | ||
394 | if (! is_gimple_min_invariant (lhs_addr)) | |
395 | return; | |
396 | ||
397 | /* The number of bytes for the new constructor. */ | |
b9c25734 RS |
398 | poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT); |
399 | poly_int64 count = ref_bytes - head_trim - tail_trim; | |
9e59e99a JL |
400 | |
401 | /* And the new type for the CONSTRUCTOR. Essentially it's just | |
402 | a char array large enough to cover the non-trimmed parts of | |
403 | the original CONSTRUCTOR. Note we want explicit bounds here | |
404 | so that we know how many bytes to clear when expanding the | |
405 | CONSTRUCTOR. */ | |
406 | tree type = build_array_type_nelts (char_type_node, count); | |
407 | ||
408 | /* Build a suitable alias type rather than using alias set zero | |
409 | to avoid pessimizing. */ | |
410 | tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); | |
411 | ||
412 | /* Build a MEM_REF representing the whole accessed area, starting | |
413 | at the first byte not trimmed. */ | |
414 | tree exp = fold_build2 (MEM_REF, type, lhs_addr, | |
415 | build_int_cst (alias_type, head_trim)); | |
416 | ||
417 | /* Now update STMT with a new RHS and LHS. */ | |
418 | gimple_assign_set_lhs (stmt, exp); | |
419 | gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); | |
420 | } | |
421 | } | |
422 | ||
7c9560a5 JL |
423 | /* STMT is a memcpy, memmove or memset. Decrement the number of bytes |
424 | copied/set by DECREMENT. */ | |
425 | static void | |
426 | decrement_count (gimple *stmt, int decrement) | |
427 | { | |
428 | tree *countp = gimple_call_arg_ptr (stmt, 2); | |
429 | gcc_assert (TREE_CODE (*countp) == INTEGER_CST); | |
430 | *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) | |
431 | - decrement)); | |
432 | ||
433 | } | |
434 | ||
435 | static void | |
436 | increment_start_addr (gimple *stmt, tree *where, int increment) | |
437 | { | |
438 | if (TREE_CODE (*where) == SSA_NAME) | |
439 | { | |
440 | tree tem = make_ssa_name (TREE_TYPE (*where)); | |
441 | gassign *newop | |
442 | = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, | |
443 | build_int_cst (sizetype, increment)); | |
444 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
445 | gsi_insert_before (&gsi, newop, GSI_SAME_STMT); | |
446 | *where = tem; | |
447 | update_stmt (gsi_stmt (gsi)); | |
448 | return; | |
449 | } | |
450 | ||
451 | *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, | |
452 | *where, | |
453 | build_int_cst (ptr_type_node, | |
454 | increment))); | |
455 | } | |
456 | ||
457 | /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead | |
458 | (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce | |
459 | the amount of data it actually writes. | |
460 | ||
461 | Right now we only support trimming from the head or the tail of the | |
462 | memory region. In theory we could split the mem* call, but it's | |
463 | likely of marginal value. */ | |
464 | ||
465 | static void | |
466 | maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) | |
467 | { | |
468 | switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
469 | { | |
470 | case BUILT_IN_MEMCPY: | |
471 | case BUILT_IN_MEMMOVE: | |
192ece9e | 472 | case BUILT_IN_STRNCPY: |
4a61cf9c JL |
473 | case BUILT_IN_MEMCPY_CHK: |
474 | case BUILT_IN_MEMMOVE_CHK: | |
192ece9e | 475 | case BUILT_IN_STRNCPY_CHK: |
7c9560a5 JL |
476 | { |
477 | int head_trim, tail_trim; | |
a59afbe2 | 478 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
7c9560a5 JL |
479 | |
480 | /* Tail trimming is easy, we can just reduce the count. */ | |
481 | if (tail_trim) | |
482 | decrement_count (stmt, tail_trim); | |
483 | ||
484 | /* Head trimming requires adjusting all the arguments. */ | |
485 | if (head_trim) | |
486 | { | |
487 | tree *dst = gimple_call_arg_ptr (stmt, 0); | |
488 | increment_start_addr (stmt, dst, head_trim); | |
489 | tree *src = gimple_call_arg_ptr (stmt, 1); | |
490 | increment_start_addr (stmt, src, head_trim); | |
491 | decrement_count (stmt, head_trim); | |
492 | } | |
493 | break; | |
494 | } | |
495 | ||
496 | case BUILT_IN_MEMSET: | |
4a61cf9c | 497 | case BUILT_IN_MEMSET_CHK: |
7c9560a5 JL |
498 | { |
499 | int head_trim, tail_trim; | |
a59afbe2 | 500 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
7c9560a5 JL |
501 | |
502 | /* Tail trimming is easy, we can just reduce the count. */ | |
503 | if (tail_trim) | |
504 | decrement_count (stmt, tail_trim); | |
505 | ||
506 | /* Head trimming requires adjusting all the arguments. */ | |
507 | if (head_trim) | |
508 | { | |
509 | tree *dst = gimple_call_arg_ptr (stmt, 0); | |
510 | increment_start_addr (stmt, dst, head_trim); | |
511 | decrement_count (stmt, head_trim); | |
512 | } | |
513 | break; | |
514 | } | |
515 | ||
516 | default: | |
517 | break; | |
518 | } | |
519 | } | |
520 | ||
d155c6fe JL |
521 | /* STMT is a memory write where one or more bytes written are dead |
522 | stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the | |
523 | bitmap of stores that are actually live. | |
524 | ||
525 | Attempt to rewrite STMT so that it writes fewer memory locations. Right | |
526 | now we only support trimming at the start or end of the memory region. | |
527 | It's not clear how much there is to be gained by trimming from the middle | |
528 | of the region. */ | |
529 | ||
530 | static void | |
531 | maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
532 | { | |
940c9a7c RB |
533 | if (is_gimple_assign (stmt) |
534 | && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) | |
d155c6fe JL |
535 | { |
536 | switch (gimple_assign_rhs_code (stmt)) | |
537 | { | |
9e59e99a JL |
538 | case CONSTRUCTOR: |
539 | maybe_trim_constructor_store (ref, live, stmt); | |
540 | break; | |
d155c6fe JL |
541 | case COMPLEX_CST: |
542 | maybe_trim_complex_store (ref, live, stmt); | |
543 | break; | |
544 | default: | |
545 | break; | |
546 | } | |
547 | } | |
548 | } | |
6de9cd9a | 549 | |
e9d297a1 JL |
550 | /* Return TRUE if USE_REF reads bytes from LIVE where live is |
551 | derived from REF, a write reference. | |
552 | ||
553 | While this routine may modify USE_REF, it's passed by value, not | |
554 | location. So callers do not see those modifications. */ | |
555 | ||
556 | static bool | |
557 | live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) | |
558 | { | |
559 | /* We have already verified that USE_REF and REF hit the same object. | |
560 | Now verify that there's actually an overlap between USE_REF and REF. */ | |
b9c25734 RS |
561 | HOST_WIDE_INT start, size; |
562 | if (normalize_ref (&use_ref, ref) | |
563 | && (use_ref.offset - ref->offset).is_constant (&start) | |
564 | && use_ref.size.is_constant (&size)) | |
e9d297a1 | 565 | { |
e9d297a1 JL |
566 | /* If USE_REF covers all of REF, then it will hit one or more |
567 | live bytes. This avoids useless iteration over the bitmap | |
568 | below. */ | |
b9c25734 | 569 | if (start == 0 && known_eq (size, ref->size)) |
e9d297a1 JL |
570 | return true; |
571 | ||
572 | /* Now check if any of the remaining bits in use_ref are set in LIVE. */ | |
4a110e34 RS |
573 | return bitmap_bit_in_range_p (live, start / BITS_PER_UNIT, |
574 | (start + size - 1) / BITS_PER_UNIT); | |
e9d297a1 JL |
575 | } |
576 | return true; | |
577 | } | |
578 | ||
311eb816 RB |
579 | /* Callback for dse_classify_store calling for_each_index. Verify that |
580 | indices are invariant in the loop with backedge PHI in basic-block DATA. */ | |
581 | ||
582 | static bool | |
583 | check_name (tree, tree *idx, void *data) | |
584 | { | |
585 | basic_block phi_bb = (basic_block) data; | |
586 | if (TREE_CODE (*idx) == SSA_NAME | |
587 | && !SSA_NAME_IS_DEFAULT_DEF (*idx) | |
588 | && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)), | |
589 | phi_bb)) | |
590 | return false; | |
591 | return true; | |
592 | } | |
593 | ||
3fe0ddc8 JL |
594 | /* STMT stores the value 0 into one or more memory locations |
595 | (via memset, empty constructor, calloc call, etc). | |
596 | ||
597 | See if there is a subsequent store of the value 0 to one | |
598 | or more of the same memory location(s). If so, the subsequent | |
599 | store is redundant and can be removed. | |
600 | ||
601 | The subsequent stores could be via memset, empty constructors, | |
602 | simple MEM stores, etc. */ | |
603 | ||
604 | static void | |
605 | dse_optimize_redundant_stores (gimple *stmt) | |
606 | { | |
607 | int cnt = 0; | |
608 | ||
609 | /* We could do something fairly complex and look through PHIs | |
610 | like DSE_CLASSIFY_STORE, but it doesn't seem to be worth | |
611 | the effort. | |
612 | ||
613 | Look at all the immediate uses of the VDEF (which are obviously | |
614 | dominated by STMT). See if one or more stores 0 into the same | |
615 | memory locations a STMT, if so remove the immediate use statements. */ | |
616 | tree defvar = gimple_vdef (stmt); | |
617 | imm_use_iterator ui; | |
618 | gimple *use_stmt; | |
619 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) | |
620 | { | |
621 | /* Limit stmt walking. */ | |
622 | if (++cnt > PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE)) | |
623 | BREAK_FROM_IMM_USE_STMT (ui); | |
624 | ||
625 | /* If USE_STMT stores 0 into one or more of the same locations | |
626 | as STMT and STMT would kill USE_STMT, then we can just remove | |
627 | USE_STMT. */ | |
628 | tree fndecl; | |
629 | if ((is_gimple_assign (use_stmt) | |
630 | && gimple_vdef (use_stmt) | |
631 | && ((gimple_assign_rhs_code (use_stmt) == CONSTRUCTOR | |
632 | && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (use_stmt)) == 0 | |
633 | && !gimple_clobber_p (stmt)) | |
634 | || (gimple_assign_rhs_code (use_stmt) == INTEGER_CST | |
635 | && integer_zerop (gimple_assign_rhs1 (use_stmt))))) | |
636 | || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL) | |
637 | && (fndecl = gimple_call_fndecl (use_stmt)) != NULL | |
638 | && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET | |
639 | || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) | |
640 | && integer_zerop (gimple_call_arg (use_stmt, 1)))) | |
641 | { | |
642 | ao_ref write; | |
643 | ||
644 | if (!initialize_ao_ref_for_dse (use_stmt, &write)) | |
645 | BREAK_FROM_IMM_USE_STMT (ui) | |
646 | ||
647 | if (valid_ao_ref_for_dse (&write) | |
648 | && stmt_kills_ref_p (stmt, &write)) | |
649 | { | |
650 | gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
651 | if (is_gimple_assign (use_stmt)) | |
652 | delete_dead_or_redundant_assignment (&gsi, "redundant"); | |
653 | else if (is_gimple_call (use_stmt)) | |
654 | delete_dead_or_redundant_call (&gsi, "redundant"); | |
655 | else | |
656 | gcc_unreachable (); | |
657 | } | |
658 | } | |
659 | } | |
660 | } | |
661 | ||
38635499 | 662 | /* A helper of dse_optimize_stmt. |
afe3cc73 RB |
663 | Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it |
664 | according to downstream uses and defs. Sets *BY_CLOBBER_P to true | |
665 | if only clobber statements influenced the classification result. | |
666 | Returns the classification. */ | |
38635499 | 667 | |
d155c6fe | 668 | static dse_store_status |
afe3cc73 RB |
669 | dse_classify_store (ao_ref *ref, gimple *stmt, |
670 | bool byte_tracking_enabled, sbitmap live_bytes, | |
671 | bool *by_clobber_p = NULL) | |
38635499 | 672 | { |
355fe088 | 673 | gimple *temp; |
311eb816 RB |
674 | int cnt = 0; |
675 | auto_bitmap visited; | |
38635499 | 676 | |
afe3cc73 RB |
677 | if (by_clobber_p) |
678 | *by_clobber_p = true; | |
38635499 | 679 | |
5006671f RG |
680 | /* Find the first dominated statement that clobbers (part of) the |
681 | memory stmt stores to with no intermediate statement that may use | |
682 | part of the memory stmt stores. That is, find a store that may | |
683 | prove stmt to be a dead store. */ | |
684 | temp = stmt; | |
685 | do | |
686 | { | |
311eb816 | 687 | gimple *use_stmt; |
5006671f RG |
688 | imm_use_iterator ui; |
689 | bool fail = false; | |
690 | tree defvar; | |
691 | ||
726a989a | 692 | if (gimple_code (temp) == GIMPLE_PHI) |
311eb816 RB |
693 | { |
694 | /* If we visit this PHI by following a backedge then we have to | |
695 | make sure ref->ref only refers to SSA names that are invariant | |
696 | with respect to the loop represented by this PHI node. */ | |
697 | if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), | |
698 | gimple_bb (temp)) | |
699 | && !for_each_index (ref->ref ? &ref->ref : &ref->base, | |
700 | check_name, gimple_bb (temp))) | |
701 | return DSE_STORE_LIVE; | |
702 | defvar = PHI_RESULT (temp); | |
703 | bitmap_set_bit (visited, SSA_NAME_VERSION (defvar)); | |
704 | } | |
5006671f RG |
705 | else |
706 | defvar = gimple_vdef (temp); | |
afe3cc73 | 707 | auto_vec<gimple *, 10> defs; |
773d0331 | 708 | gimple *phi_def = NULL; |
5006671f | 709 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
f403a4a2 | 710 | { |
311eb816 RB |
711 | /* Limit stmt walking. */ |
712 | if (++cnt > PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE)) | |
cc788fcc RG |
713 | { |
714 | fail = true; | |
715 | BREAK_FROM_IMM_USE_STMT (ui); | |
716 | } | |
311eb816 RB |
717 | |
718 | /* We have visited ourselves already so ignore STMT for the | |
719 | purpose of chaining. */ | |
720 | if (use_stmt == stmt) | |
721 | ; | |
5006671f RG |
722 | /* In simple cases we can look through PHI nodes, but we |
723 | have to be careful with loops and with memory references | |
724 | containing operands that are also operands of PHI nodes. | |
725 | See gcc.c-torture/execute/20051110-*.c. */ | |
cc788fcc | 726 | else if (gimple_code (use_stmt) == GIMPLE_PHI) |
5006671f | 727 | { |
311eb816 RB |
728 | /* If we already visited this PHI ignore it for further |
729 | processing. */ | |
730 | if (!bitmap_bit_p (visited, | |
731 | SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) | |
773d0331 RB |
732 | { |
733 | defs.safe_push (use_stmt); | |
734 | phi_def = use_stmt; | |
735 | } | |
5006671f RG |
736 | } |
737 | /* If the statement is a use the store is not dead. */ | |
8cb65b37 | 738 | else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
0f84b066 | 739 | { |
f240a230 | 740 | /* Handle common cases where we can easily build an ao_ref |
e9d297a1 JL |
741 | structure for USE_STMT and in doing so we find that the |
742 | references hit non-live bytes and thus can be ignored. */ | |
afe3cc73 | 743 | if (byte_tracking_enabled |
311eb816 | 744 | && is_gimple_assign (use_stmt)) |
e9d297a1 | 745 | { |
311eb816 RB |
746 | ao_ref use_ref; |
747 | ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); | |
748 | if (valid_ao_ref_for_dse (&use_ref) | |
749 | && use_ref.base == ref->base | |
750 | && known_eq (use_ref.size, use_ref.max_size) | |
751 | && !live_bytes_read (use_ref, ref, live_bytes)) | |
e9d297a1 | 752 | { |
311eb816 RB |
753 | /* If this is a store, remember it as we possibly |
754 | need to walk the defs uses. */ | |
755 | if (gimple_vdef (use_stmt)) | |
756 | defs.safe_push (use_stmt); | |
757 | continue; | |
e9d297a1 JL |
758 | } |
759 | } | |
760 | ||
0f84b066 | 761 | fail = true; |
5006671f RG |
762 | BREAK_FROM_IMM_USE_STMT (ui); |
763 | } | |
afe3cc73 RB |
764 | /* If this is a store, remember it as we possibly need to walk the |
765 | defs uses. */ | |
5006671f | 766 | else if (gimple_vdef (use_stmt)) |
afe3cc73 | 767 | defs.safe_push (use_stmt); |
0f84b066 AH |
768 | } |
769 | ||
5006671f | 770 | if (fail) |
d155c6fe JL |
771 | { |
772 | /* STMT might be partially dead and we may be able to reduce | |
773 | how many memory locations it stores into. */ | |
774 | if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
775 | return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
776 | return DSE_STORE_LIVE; | |
777 | } | |
5006671f RG |
778 | |
779 | /* If we didn't find any definition this means the store is dead | |
780 | if it isn't a store to global reachable memory. In this case | |
781 | just pretend the stmt makes itself dead. Otherwise fail. */ | |
afe3cc73 | 782 | if (defs.is_empty ()) |
38635499 | 783 | { |
8cb65b37 | 784 | if (ref_may_alias_global_p (ref)) |
d155c6fe | 785 | return DSE_STORE_LIVE; |
5006671f | 786 | |
afe3cc73 RB |
787 | if (by_clobber_p) |
788 | *by_clobber_p = false; | |
789 | return DSE_STORE_DEAD; | |
38635499 | 790 | } |
d155c6fe | 791 | |
773d0331 | 792 | /* Process defs and remove those we need not process further. */ |
f1bcb061 | 793 | for (unsigned i = 0; i < defs.length ();) |
773d0331 RB |
794 | { |
795 | gimple *def = defs[i]; | |
796 | gimple *use_stmt; | |
797 | use_operand_p use_p; | |
798 | /* If the path to check starts with a kill we do not need to | |
799 | process it further. | |
800 | ??? With byte tracking we need only kill the bytes currently | |
801 | live. */ | |
802 | if (stmt_kills_ref_p (def, ref)) | |
803 | { | |
804 | if (by_clobber_p && !gimple_clobber_p (def)) | |
805 | *by_clobber_p = false; | |
806 | defs.unordered_remove (i); | |
807 | } | |
808 | /* In addition to kills we can remove defs whose only use | |
809 | is another def in defs. That can only ever be PHIs of which | |
810 | we track a single for simplicity reasons (we fail for multiple | |
f1bcb061 RB |
811 | PHIs anyways). We can also ignore defs that feed only into |
812 | already visited PHIs. */ | |
773d0331 RB |
813 | else if (gimple_code (def) != GIMPLE_PHI |
814 | && single_imm_use (gimple_vdef (def), &use_p, &use_stmt) | |
f1bcb061 RB |
815 | && (use_stmt == phi_def |
816 | || (gimple_code (use_stmt) == GIMPLE_PHI | |
817 | && bitmap_bit_p (visited, | |
818 | SSA_NAME_VERSION | |
819 | (PHI_RESULT (use_stmt)))))) | |
afe3cc73 | 820 | defs.unordered_remove (i); |
f1bcb061 RB |
821 | else |
822 | ++i; | |
773d0331 | 823 | } |
afe3cc73 RB |
824 | |
825 | /* If all defs kill the ref we are done. */ | |
826 | if (defs.is_empty ()) | |
827 | return DSE_STORE_DEAD; | |
828 | /* If more than one def survives fail. */ | |
829 | if (defs.length () > 1) | |
830 | { | |
831 | /* STMT might be partially dead and we may be able to reduce | |
832 | how many memory locations it stores into. */ | |
833 | if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
834 | return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
835 | return DSE_STORE_LIVE; | |
836 | } | |
837 | temp = defs[0]; | |
38635499 | 838 | |
afe3cc73 RB |
839 | /* Track partial kills. */ |
840 | if (byte_tracking_enabled) | |
841 | { | |
842 | clear_bytes_written_by (live_bytes, temp, ref); | |
843 | if (bitmap_empty_p (live_bytes)) | |
844 | { | |
845 | if (by_clobber_p && !gimple_clobber_p (temp)) | |
846 | *by_clobber_p = false; | |
847 | return DSE_STORE_DEAD; | |
848 | } | |
849 | } | |
850 | } | |
851 | /* Continue walking until there are no more live bytes. */ | |
852 | while (1); | |
d155c6fe JL |
853 | } |
854 | ||
855 | ||
856 | class dse_dom_walker : public dom_walker | |
857 | { | |
858 | public: | |
859 | dse_dom_walker (cdi_direction direction) | |
0236bb04 TS |
860 | : dom_walker (direction), |
861 | m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)), | |
862 | m_byte_tracking_enabled (false) {} | |
d155c6fe JL |
863 | |
864 | virtual edge before_dom_children (basic_block); | |
865 | ||
866 | private: | |
0236bb04 | 867 | auto_sbitmap m_live_bytes; |
d155c6fe JL |
868 | bool m_byte_tracking_enabled; |
869 | void dse_optimize_stmt (gimple_stmt_iterator *); | |
870 | }; | |
871 | ||
39b6ee24 | 872 | /* Delete a dead call at GSI, which is mem* call of some kind. */ |
d155c6fe | 873 | static void |
08c1638d | 874 | delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type) |
d155c6fe | 875 | { |
1a15be68 | 876 | gimple *stmt = gsi_stmt (*gsi); |
d155c6fe JL |
877 | if (dump_file && (dump_flags & TDF_DETAILS)) |
878 | { | |
3fe0ddc8 | 879 | fprintf (dump_file, " Deleted %s call: ", type); |
ef6cb4c7 | 880 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
d155c6fe JL |
881 | fprintf (dump_file, "\n"); |
882 | } | |
883 | ||
884 | tree lhs = gimple_call_lhs (stmt); | |
d155c6fe JL |
885 | if (lhs) |
886 | { | |
887 | tree ptr = gimple_call_arg (stmt, 0); | |
888 | gimple *new_stmt = gimple_build_assign (lhs, ptr); | |
889 | unlink_stmt_vdef (stmt); | |
1a15be68 | 890 | if (gsi_replace (gsi, new_stmt, true)) |
d155c6fe JL |
891 | bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); |
892 | } | |
893 | else | |
894 | { | |
895 | /* Then we need to fix the operand of the consuming stmt. */ | |
896 | unlink_stmt_vdef (stmt); | |
897 | ||
898 | /* Remove the dead store. */ | |
1a15be68 | 899 | if (gsi_remove (gsi, true)) |
d155c6fe JL |
900 | bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); |
901 | release_defs (stmt); | |
902 | } | |
38635499 DN |
903 | } |
904 | ||
39b6ee24 | 905 | /* Delete a dead store at GSI, which is a gimple assignment. */ |
d155c6fe JL |
906 | |
907 | static void | |
08c1638d | 908 | delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi, const char *type) |
d155c6fe | 909 | { |
1a15be68 | 910 | gimple *stmt = gsi_stmt (*gsi); |
d155c6fe JL |
911 | if (dump_file && (dump_flags & TDF_DETAILS)) |
912 | { | |
3fe0ddc8 | 913 | fprintf (dump_file, " Deleted %s store: ", type); |
ef6cb4c7 | 914 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
d155c6fe JL |
915 | fprintf (dump_file, "\n"); |
916 | } | |
917 | ||
918 | /* Then we need to fix the operand of the consuming stmt. */ | |
919 | unlink_stmt_vdef (stmt); | |
920 | ||
921 | /* Remove the dead store. */ | |
d155c6fe | 922 | basic_block bb = gimple_bb (stmt); |
1a15be68 | 923 | if (gsi_remove (gsi, true)) |
d155c6fe JL |
924 | bitmap_set_bit (need_eh_cleanup, bb->index); |
925 | ||
926 | /* And release any SSA_NAMEs set in this statement back to the | |
927 | SSA_NAME manager. */ | |
928 | release_defs (stmt); | |
929 | } | |
38635499 | 930 | |
6de9cd9a DN |
931 | /* Attempt to eliminate dead stores in the statement referenced by BSI. |
932 | ||
933 | A dead store is a store into a memory location which will later be | |
934 | overwritten by another store without any intervening loads. In this | |
935 | case the earlier store can be deleted. | |
936 | ||
937 | In our SSA + virtual operand world we use immediate uses of virtual | |
938 | operands to detect dead stores. If a store's virtual definition | |
939 | is used precisely once by a later store to the same location which | |
940 | post dominates the first store, then the first store is dead. */ | |
941 | ||
d155c6fe JL |
942 | void |
943 | dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) | |
6de9cd9a | 944 | { |
355fe088 | 945 | gimple *stmt = gsi_stmt (*gsi); |
6de9cd9a | 946 | |
773168c7 | 947 | /* If this statement has no virtual defs, then there is nothing |
6de9cd9a | 948 | to do. */ |
5006671f | 949 | if (!gimple_vdef (stmt)) |
6de9cd9a DN |
950 | return; |
951 | ||
5d751b0c JJ |
952 | /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
953 | if (gimple_has_volatile_ops (stmt) | |
954 | && (!gimple_clobber_p (stmt) | |
955 | || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
e79b60a7 DN |
956 | return; |
957 | ||
d155c6fe JL |
958 | ao_ref ref; |
959 | if (!initialize_ao_ref_for_dse (stmt, &ref)) | |
960 | return; | |
961 | ||
8cb65b37 MG |
962 | /* We know we have virtual definitions. We can handle assignments and |
963 | some builtin calls. */ | |
964 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
965 | { | |
3fe0ddc8 JL |
966 | tree fndecl = gimple_call_fndecl (stmt); |
967 | switch (DECL_FUNCTION_CODE (fndecl)) | |
8cb65b37 | 968 | { |
caffb6e5 JL |
969 | case BUILT_IN_MEMCPY: |
970 | case BUILT_IN_MEMMOVE: | |
192ece9e | 971 | case BUILT_IN_STRNCPY: |
caffb6e5 JL |
972 | case BUILT_IN_MEMSET: |
973 | case BUILT_IN_MEMCPY_CHK: | |
974 | case BUILT_IN_MEMMOVE_CHK: | |
192ece9e | 975 | case BUILT_IN_STRNCPY_CHK: |
caffb6e5 JL |
976 | case BUILT_IN_MEMSET_CHK: |
977 | { | |
978 | /* Occasionally calls with an explicit length of zero | |
979 | show up in the IL. It's pointless to do analysis | |
980 | on them, they're trivially dead. */ | |
981 | tree size = gimple_call_arg (stmt, 2); | |
982 | if (integer_zerop (size)) | |
983 | { | |
3fe0ddc8 | 984 | delete_dead_or_redundant_call (gsi, "dead"); |
caffb6e5 JL |
985 | return; |
986 | } | |
987 | ||
988 | /* If this is a memset call that initializes an object | |
989 | to zero, it may be redundant with an earlier memset | |
990 | or empty CONSTRUCTOR of a larger object. */ | |
991 | if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET | |
992 | || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) | |
993 | && integer_zerop (gimple_call_arg (stmt, 1))) | |
994 | dse_optimize_redundant_stores (stmt); | |
995 | ||
996 | enum dse_store_status store_status; | |
997 | m_byte_tracking_enabled | |
998 | = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
999 | store_status = dse_classify_store (&ref, stmt, | |
1000 | m_byte_tracking_enabled, | |
1001 | m_live_bytes); | |
1002 | if (store_status == DSE_STORE_LIVE) | |
d155c6fe | 1003 | return; |
d155c6fe | 1004 | |
caffb6e5 JL |
1005 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
1006 | { | |
1007 | maybe_trim_memstar_call (&ref, m_live_bytes, stmt); | |
1008 | return; | |
1009 | } | |
3fe0ddc8 | 1010 | |
caffb6e5 JL |
1011 | if (store_status == DSE_STORE_DEAD) |
1012 | delete_dead_or_redundant_call (gsi, "dead"); | |
8cb65b37 | 1013 | return; |
caffb6e5 JL |
1014 | } |
1015 | ||
1016 | case BUILT_IN_CALLOC: | |
1017 | /* We already know the arguments are integer constants. */ | |
1018 | dse_optimize_redundant_stores (stmt); | |
1019 | return; | |
1020 | ||
1021 | default: | |
1022 | return; | |
8cb65b37 MG |
1023 | } |
1024 | } | |
1025 | ||
726a989a | 1026 | if (is_gimple_assign (stmt)) |
6de9cd9a | 1027 | { |
afe3cc73 | 1028 | bool by_clobber_p = false; |
6de9cd9a | 1029 | |
3fe0ddc8 JL |
1030 | /* First see if this store is a CONSTRUCTOR and if there |
1031 | are subsequent CONSTRUCTOR stores which are totally | |
1032 | subsumed by this statement. If so remove the subsequent | |
1033 | CONSTRUCTOR store. | |
1034 | ||
1035 | This will tend to make fewer calls into memset with longer | |
1036 | arguments. */ | |
1037 | if (gimple_assign_rhs_code (stmt) == CONSTRUCTOR | |
1038 | && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) == 0 | |
1039 | && !gimple_clobber_p (stmt)) | |
1040 | dse_optimize_redundant_stores (stmt); | |
1041 | ||
8cb65b37 MG |
1042 | /* Self-assignments are zombies. */ |
1043 | if (operand_equal_p (gimple_assign_rhs1 (stmt), | |
1044 | gimple_assign_lhs (stmt), 0)) | |
afe3cc73 | 1045 | ; |
8cb65b37 MG |
1046 | else |
1047 | { | |
d155c6fe JL |
1048 | m_byte_tracking_enabled |
1049 | = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
1050 | enum dse_store_status store_status; | |
afe3cc73 | 1051 | store_status = dse_classify_store (&ref, stmt, |
d155c6fe | 1052 | m_byte_tracking_enabled, |
afe3cc73 | 1053 | m_live_bytes, &by_clobber_p); |
d155c6fe | 1054 | if (store_status == DSE_STORE_LIVE) |
8cb65b37 | 1055 | return; |
d155c6fe JL |
1056 | |
1057 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) | |
1058 | { | |
1059 | maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); | |
1060 | return; | |
1061 | } | |
8cb65b37 | 1062 | } |
8a8b05f4 | 1063 | |
0ea48022 RB |
1064 | /* Now we know that use_stmt kills the LHS of stmt. */ |
1065 | ||
5d751b0c JJ |
1066 | /* But only remove *this_2(D) ={v} {CLOBBER} if killed by |
1067 | another clobber stmt. */ | |
1068 | if (gimple_clobber_p (stmt) | |
afe3cc73 | 1069 | && !by_clobber_p) |
5d751b0c JJ |
1070 | return; |
1071 | ||
3fe0ddc8 | 1072 | delete_dead_or_redundant_assignment (gsi, "dead"); |
6de9cd9a DN |
1073 | } |
1074 | } | |
1075 | ||
3daacdcd | 1076 | edge |
4d9192b5 | 1077 | dse_dom_walker::before_dom_children (basic_block bb) |
6de9cd9a | 1078 | { |
726a989a | 1079 | gimple_stmt_iterator gsi; |
6de9cd9a | 1080 | |
0285a18e MM |
1081 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
1082 | { | |
1083 | dse_optimize_stmt (&gsi); | |
1084 | if (gsi_end_p (gsi)) | |
1085 | gsi = gsi_last_bb (bb); | |
1086 | else | |
1087 | gsi_prev (&gsi); | |
1088 | } | |
3daacdcd | 1089 | return NULL; |
6de9cd9a DN |
1090 | } |
1091 | ||
17795822 TS |
1092 | namespace { |
1093 | ||
1094 | const pass_data pass_data_dse = | |
be55bfe6 TS |
1095 | { |
1096 | GIMPLE_PASS, /* type */ | |
1097 | "dse", /* name */ | |
1098 | OPTGROUP_NONE, /* optinfo_flags */ | |
be55bfe6 TS |
1099 | TV_TREE_DSE, /* tv_id */ |
1100 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
1101 | 0, /* properties_provided */ | |
1102 | 0, /* properties_destroyed */ | |
1103 | 0, /* todo_flags_start */ | |
3bea341f | 1104 | 0, /* todo_flags_finish */ |
be55bfe6 TS |
1105 | }; |
1106 | ||
17795822 | 1107 | class pass_dse : public gimple_opt_pass |
be55bfe6 TS |
1108 | { |
1109 | public: | |
1110 | pass_dse (gcc::context *ctxt) | |
1111 | : gimple_opt_pass (pass_data_dse, ctxt) | |
1112 | {} | |
1113 | ||
1114 | /* opt_pass methods: */ | |
1115 | opt_pass * clone () { return new pass_dse (m_ctxt); } | |
1116 | virtual bool gate (function *) { return flag_tree_dse != 0; } | |
1117 | virtual unsigned int execute (function *); | |
1118 | ||
1119 | }; // class pass_dse | |
38635499 | 1120 | |
be55bfe6 TS |
1121 | unsigned int |
1122 | pass_dse::execute (function *fun) | |
6de9cd9a | 1123 | { |
caaf13d3 JL |
1124 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
1125 | ||
908ff6a3 | 1126 | renumber_gimple_stmt_uids (); |
6de9cd9a DN |
1127 | |
1128 | /* We might consider making this a property of each pass so that it | |
1129 | can be [re]computed on an as-needed basis. Particularly since | |
1130 | this pass could be seen as an extension of DCE which needs post | |
1131 | dominators. */ | |
1132 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
5006671f | 1133 | calculate_dominance_info (CDI_DOMINATORS); |
6de9cd9a | 1134 | |
6de9cd9a DN |
1135 | /* Dead store elimination is fundamentally a walk of the post-dominator |
1136 | tree and a backwards walk of statements within each block. */ | |
be55bfe6 | 1137 | dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); |
6de9cd9a | 1138 | |
caaf13d3 JL |
1139 | /* Removal of stores may make some EH edges dead. Purge such edges from |
1140 | the CFG as needed. */ | |
1141 | if (!bitmap_empty_p (need_eh_cleanup)) | |
1142 | { | |
1143 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
1144 | cleanup_tree_cfg (); | |
1145 | } | |
1146 | ||
1147 | BITMAP_FREE (need_eh_cleanup); | |
d155c6fe | 1148 | |
6de9cd9a DN |
1149 | /* For now, just wipe the post-dominator information. */ |
1150 | free_dominance_info (CDI_POST_DOMINATORS); | |
c2924966 | 1151 | return 0; |
6de9cd9a DN |
1152 | } |
1153 | ||
17795822 TS |
1154 | } // anon namespace |
1155 | ||
27a4cd48 DM |
1156 | gimple_opt_pass * |
1157 | make_pass_dse (gcc::context *ctxt) | |
1158 | { | |
1159 | return new pass_dse (ctxt); | |
1160 | } |