]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Dead store elimination |
aad93da1 | 2 | Copyright (C) 2004-2017 Free Software Foundation, Inc. |
4ee9c684 | 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 | |
8c4c00c1 | 8 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 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 | |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
9ef16211 | 23 | #include "backend.h" |
7c29e30e | 24 | #include "rtl.h" |
4ee9c684 | 25 | #include "tree.h" |
9ef16211 | 26 | #include "gimple.h" |
7c29e30e | 27 | #include "tree-pass.h" |
9ef16211 | 28 | #include "ssa.h" |
7c29e30e | 29 | #include "gimple-pretty-print.h" |
b20a8bb4 | 30 | #include "fold-const.h" |
dcf1a1ec | 31 | #include "gimple-iterator.h" |
073c1fd5 | 32 | #include "tree-cfg.h" |
073c1fd5 | 33 | #include "tree-dfa.h" |
4ee9c684 | 34 | #include "domwalk.h" |
424a4a92 | 35 | #include "tree-cfgcleanup.h" |
64123137 | 36 | #include "params.h" |
56ce87e3 | 37 | #include "alias.h" |
4ee9c684 | 38 | |
39 | /* This file implements dead store elimination. | |
40 | ||
41 | A dead store is a store into a memory location which will later be | |
42 | overwritten by another store without any intervening loads. In this | |
43 | case the earlier store can be deleted. | |
44 | ||
45 | In our SSA + virtual operand world we use immediate uses of virtual | |
46 | operands to detect dead stores. If a store's virtual definition | |
47 | is used precisely once by a later store to the same location which | |
48e1416a | 48 | post dominates the first store, then the first store is dead. |
4ee9c684 | 49 | |
50 | The single use of the store's virtual definition ensures that | |
51 | there are no intervening aliased loads and the requirement that | |
52 | the second load post dominate the first ensures that if the earlier | |
53 | store executes, then the later stores will execute before the function | |
54 | exits. | |
55 | ||
56 | It may help to think of this as first moving the earlier store to | |
57 | the point immediately before the later store. Again, the single | |
2c763ed4 | 58 | use of the virtual definition and the post-dominance relationship |
48e1416a | 59 | ensure that such movement would be safe. Clearly if there are |
4ee9c684 | 60 | back to back stores, then the second is redundant. |
61 | ||
62 | Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
63 | may also help in understanding this code since it discusses the | |
64 | relationship between dead store and redundant load elimination. In | |
65 | fact, they are the same transformation applied to different views of | |
66 | the CFG. */ | |
75a70cf9 | 67 | |
4ee9c684 | 68 | |
d02c8339 | 69 | /* Bitmap of blocks that have had EH statements cleaned. We should |
70 | remove their dead edges eventually. */ | |
71 | static bitmap need_eh_cleanup; | |
72 | ||
64123137 | 73 | /* Return value from dse_classify_store */ |
74 | enum dse_store_status | |
75 | { | |
76 | DSE_STORE_LIVE, | |
77 | DSE_STORE_MAYBE_PARTIAL_DEAD, | |
78 | DSE_STORE_DEAD | |
79 | }; | |
80 | ||
81 | /* STMT is a statement that may write into memory. Analyze it and | |
82 | initialize WRITE to describe how STMT affects memory. | |
83 | ||
84 | Return TRUE if the the statement was analyzed, FALSE otherwise. | |
85 | ||
86 | It is always safe to return FALSE. But typically better optimziation | |
87 | can be achieved by analyzing more statements. */ | |
88 | ||
89 | static bool | |
90 | initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) | |
91 | { | |
92 | /* It's advantageous to handle certain mem* functions. */ | |
93 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
94 | { | |
95 | switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
96 | { | |
97 | case BUILT_IN_MEMCPY: | |
98 | case BUILT_IN_MEMMOVE: | |
99 | case BUILT_IN_MEMSET: | |
100 | { | |
101 | tree size = NULL_TREE; | |
102 | if (gimple_call_num_args (stmt) == 3) | |
103 | size = gimple_call_arg (stmt, 2); | |
104 | tree ptr = gimple_call_arg (stmt, 0); | |
105 | ao_ref_init_from_ptr_and_size (write, ptr, size); | |
106 | return true; | |
107 | } | |
108 | default: | |
109 | break; | |
110 | } | |
111 | } | |
112 | else if (is_gimple_assign (stmt)) | |
113 | { | |
114 | ao_ref_init (write, gimple_assign_lhs (stmt)); | |
115 | return true; | |
116 | } | |
117 | return false; | |
118 | } | |
119 | ||
120 | /* Given REF from the the alias oracle, return TRUE if it is a valid | |
121 | memory reference for dead store elimination, false otherwise. | |
122 | ||
123 | In particular, the reference must have a known base, known maximum | |
124 | size, start at a byte offset and have a size that is one or more | |
125 | bytes. */ | |
126 | ||
127 | static bool | |
128 | valid_ao_ref_for_dse (ao_ref *ref) | |
129 | { | |
130 | return (ao_ref_base (ref) | |
131 | && ref->max_size != -1 | |
b37570be | 132 | && ref->size != 0 |
133 | && ref->max_size == ref->size | |
64123137 | 134 | && (ref->offset % BITS_PER_UNIT) == 0 |
135 | && (ref->size % BITS_PER_UNIT) == 0 | |
136 | && (ref->size != -1)); | |
137 | } | |
138 | ||
139 | /* Normalize COPY (an ao_ref) relative to REF. Essentially when we are | |
140 | done COPY will only refer bytes found within REF. | |
141 | ||
142 | We have already verified that COPY intersects at least one | |
143 | byte with REF. */ | |
144 | ||
145 | static void | |
146 | normalize_ref (ao_ref *copy, ao_ref *ref) | |
147 | { | |
148 | /* If COPY starts before REF, then reset the beginning of | |
149 | COPY to match REF and decrease the size of COPY by the | |
150 | number of bytes removed from COPY. */ | |
151 | if (copy->offset < ref->offset) | |
152 | { | |
153 | copy->size -= (ref->offset - copy->offset); | |
154 | copy->offset = ref->offset; | |
155 | } | |
156 | ||
157 | /* If COPY extends beyond REF, chop off its size appropriately. */ | |
158 | if (copy->offset + copy->size > ref->offset + ref->size) | |
159 | copy->size -= (copy->offset + copy->size - (ref->offset + ref->size)); | |
160 | } | |
161 | ||
162 | /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base | |
163 | address written by STMT must match the one found in REF, which must | |
164 | have its base address previously initialized. | |
165 | ||
166 | This routine must be conservative. If we don't know the offset or | |
167 | actual size written, assume nothing was written. */ | |
168 | ||
169 | static void | |
170 | clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) | |
171 | { | |
172 | ao_ref write; | |
173 | if (!initialize_ao_ref_for_dse (stmt, &write)) | |
174 | return; | |
175 | ||
176 | /* Verify we have the same base memory address, the write | |
177 | has a known size and overlaps with REF. */ | |
178 | if (valid_ao_ref_for_dse (&write) | |
b87372d9 | 179 | && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) |
64123137 | 180 | && write.size == write.max_size |
181 | && ((write.offset < ref->offset | |
182 | && write.offset + write.size > ref->offset) | |
183 | || (write.offset >= ref->offset | |
184 | && write.offset < ref->offset + ref->size))) | |
185 | { | |
186 | normalize_ref (&write, ref); | |
187 | bitmap_clear_range (live_bytes, | |
188 | (write.offset - ref->offset) / BITS_PER_UNIT, | |
189 | write.size / BITS_PER_UNIT); | |
190 | } | |
191 | } | |
192 | ||
193 | /* REF is a memory write. Extract relevant information from it and | |
194 | initialize the LIVE_BYTES bitmap. If successful, return TRUE. | |
195 | Otherwise return FALSE. */ | |
196 | ||
197 | static bool | |
198 | setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | |
199 | { | |
200 | if (valid_ao_ref_for_dse (ref) | |
201 | && (ref->size / BITS_PER_UNIT | |
202 | <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) | |
203 | { | |
204 | bitmap_clear (live_bytes); | |
205 | bitmap_set_range (live_bytes, 0, ref->size / BITS_PER_UNIT); | |
206 | return true; | |
207 | } | |
208 | return false; | |
209 | } | |
210 | ||
211 | /* Compute the number of elements that we can trim from the head and | |
212 | tail of ORIG resulting in a bitmap that is a superset of LIVE. | |
213 | ||
214 | Store the number of elements trimmed from the head and tail in | |
f4826e25 | 215 | TRIM_HEAD and TRIM_TAIL. |
216 | ||
217 | STMT is the statement being trimmed and is used for debugging dump | |
218 | output only. */ | |
64123137 | 219 | |
220 | static void | |
f4826e25 | 221 | compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
222 | gimple *stmt) | |
64123137 | 223 | { |
224 | /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap | |
225 | extends through ref->size. So we know that in the original bitmap | |
226 | bits 0..ref->size were true. We don't actually need the bitmap, just | |
227 | the REF to compute the trims. */ | |
228 | ||
229 | /* Now identify how much, if any of the tail we can chop off. */ | |
64123137 | 230 | int last_orig = (ref->size / BITS_PER_UNIT) - 1; |
231 | int last_live = bitmap_last_set_bit (live); | |
232 | *trim_tail = (last_orig - last_live) & ~0x1; | |
233 | ||
234 | /* Identify how much, if any of the head we can chop off. */ | |
235 | int first_orig = 0; | |
236 | int first_live = bitmap_first_set_bit (live); | |
237 | *trim_head = (first_live - first_orig) & ~0x1; | |
f4826e25 | 238 | |
239 | if ((*trim_head || *trim_tail) | |
240 | && dump_file && (dump_flags & TDF_DETAILS)) | |
241 | { | |
242 | fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", | |
243 | *trim_head, *trim_tail); | |
1ffa4346 | 244 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
f4826e25 | 245 | fprintf (dump_file, "\n"); |
246 | } | |
64123137 | 247 | } |
248 | ||
249 | /* STMT initializes an object from COMPLEX_CST where one or more of the | |
250 | bytes written may be dead stores. REF is a representation of the | |
251 | memory written. LIVE is the bitmap of stores that are actually live. | |
252 | ||
253 | Attempt to rewrite STMT so that only the real or imaginary part of | |
254 | the object is actually stored. */ | |
255 | ||
256 | static void | |
257 | maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
258 | { | |
259 | int trim_head, trim_tail; | |
f4826e25 | 260 | compute_trims (ref, live, &trim_head, &trim_tail, stmt); |
64123137 | 261 | |
262 | /* The amount of data trimmed from the head or tail must be at | |
263 | least half the size of the object to ensure we're trimming | |
264 | the entire real or imaginary half. By writing things this | |
265 | way we avoid more O(n) bitmap operations. */ | |
266 | if (trim_tail * 2 >= ref->size / BITS_PER_UNIT) | |
267 | { | |
268 | /* TREE_REALPART is live */ | |
269 | tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | |
270 | tree y = gimple_assign_lhs (stmt); | |
271 | y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | |
272 | gimple_assign_set_lhs (stmt, y); | |
273 | gimple_assign_set_rhs1 (stmt, x); | |
274 | } | |
275 | else if (trim_head * 2 >= ref->size / BITS_PER_UNIT) | |
276 | { | |
277 | /* TREE_IMAGPART is live */ | |
278 | tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | |
279 | tree y = gimple_assign_lhs (stmt); | |
280 | y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | |
281 | gimple_assign_set_lhs (stmt, y); | |
282 | gimple_assign_set_rhs1 (stmt, x); | |
283 | } | |
284 | ||
285 | /* Other cases indicate parts of both the real and imag subobjects | |
286 | are live. We do not try to optimize those cases. */ | |
287 | } | |
288 | ||
56ce87e3 | 289 | /* STMT initializes an object using a CONSTRUCTOR where one or more of the |
290 | bytes written are dead stores. ORIG is the bitmap of bytes stored by | |
291 | STMT. LIVE is the bitmap of stores that are actually live. | |
292 | ||
293 | Attempt to rewrite STMT so that only the real or imaginary part of | |
294 | the object is actually stored. | |
295 | ||
296 | The most common case for getting here is a CONSTRUCTOR with no elements | |
297 | being used to zero initialize an object. We do not try to handle other | |
298 | cases as those would force us to fully cover the object with the | |
299 | CONSTRUCTOR node except for the components that are dead. */ | |
300 | ||
301 | static void | |
302 | maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
303 | { | |
304 | tree ctor = gimple_assign_rhs1 (stmt); | |
305 | ||
306 | /* This is the only case we currently handle. It actually seems to | |
307 | catch most cases of actual interest. */ | |
308 | gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); | |
309 | ||
310 | int head_trim = 0; | |
311 | int tail_trim = 0; | |
f4826e25 | 312 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
56ce87e3 | 313 | |
314 | /* Now we want to replace the constructor initializer | |
315 | with memset (object + head_trim, 0, size - head_trim - tail_trim). */ | |
316 | if (head_trim || tail_trim) | |
317 | { | |
318 | /* We want &lhs for the MEM_REF expression. */ | |
319 | tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); | |
320 | ||
321 | if (! is_gimple_min_invariant (lhs_addr)) | |
322 | return; | |
323 | ||
324 | /* The number of bytes for the new constructor. */ | |
325 | int count = (ref->size / BITS_PER_UNIT) - head_trim - tail_trim; | |
326 | ||
327 | /* And the new type for the CONSTRUCTOR. Essentially it's just | |
328 | a char array large enough to cover the non-trimmed parts of | |
329 | the original CONSTRUCTOR. Note we want explicit bounds here | |
330 | so that we know how many bytes to clear when expanding the | |
331 | CONSTRUCTOR. */ | |
332 | tree type = build_array_type_nelts (char_type_node, count); | |
333 | ||
334 | /* Build a suitable alias type rather than using alias set zero | |
335 | to avoid pessimizing. */ | |
336 | tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); | |
337 | ||
338 | /* Build a MEM_REF representing the whole accessed area, starting | |
339 | at the first byte not trimmed. */ | |
340 | tree exp = fold_build2 (MEM_REF, type, lhs_addr, | |
341 | build_int_cst (alias_type, head_trim)); | |
342 | ||
343 | /* Now update STMT with a new RHS and LHS. */ | |
344 | gimple_assign_set_lhs (stmt, exp); | |
345 | gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); | |
346 | } | |
347 | } | |
348 | ||
339f327d | 349 | /* STMT is a memcpy, memmove or memset. Decrement the number of bytes |
350 | copied/set by DECREMENT. */ | |
351 | static void | |
352 | decrement_count (gimple *stmt, int decrement) | |
353 | { | |
354 | tree *countp = gimple_call_arg_ptr (stmt, 2); | |
355 | gcc_assert (TREE_CODE (*countp) == INTEGER_CST); | |
356 | *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) | |
357 | - decrement)); | |
358 | ||
359 | } | |
360 | ||
361 | static void | |
362 | increment_start_addr (gimple *stmt, tree *where, int increment) | |
363 | { | |
364 | if (TREE_CODE (*where) == SSA_NAME) | |
365 | { | |
366 | tree tem = make_ssa_name (TREE_TYPE (*where)); | |
367 | gassign *newop | |
368 | = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, | |
369 | build_int_cst (sizetype, increment)); | |
370 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
371 | gsi_insert_before (&gsi, newop, GSI_SAME_STMT); | |
372 | *where = tem; | |
373 | update_stmt (gsi_stmt (gsi)); | |
374 | return; | |
375 | } | |
376 | ||
377 | *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, | |
378 | *where, | |
379 | build_int_cst (ptr_type_node, | |
380 | increment))); | |
381 | } | |
382 | ||
383 | /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead | |
384 | (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce | |
385 | the amount of data it actually writes. | |
386 | ||
387 | Right now we only support trimming from the head or the tail of the | |
388 | memory region. In theory we could split the mem* call, but it's | |
389 | likely of marginal value. */ | |
390 | ||
391 | static void | |
392 | maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) | |
393 | { | |
394 | switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
395 | { | |
396 | case BUILT_IN_MEMCPY: | |
397 | case BUILT_IN_MEMMOVE: | |
398 | { | |
399 | int head_trim, tail_trim; | |
f4826e25 | 400 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
339f327d | 401 | |
402 | /* Tail trimming is easy, we can just reduce the count. */ | |
403 | if (tail_trim) | |
404 | decrement_count (stmt, tail_trim); | |
405 | ||
406 | /* Head trimming requires adjusting all the arguments. */ | |
407 | if (head_trim) | |
408 | { | |
409 | tree *dst = gimple_call_arg_ptr (stmt, 0); | |
410 | increment_start_addr (stmt, dst, head_trim); | |
411 | tree *src = gimple_call_arg_ptr (stmt, 1); | |
412 | increment_start_addr (stmt, src, head_trim); | |
413 | decrement_count (stmt, head_trim); | |
414 | } | |
415 | break; | |
416 | } | |
417 | ||
418 | case BUILT_IN_MEMSET: | |
419 | { | |
420 | int head_trim, tail_trim; | |
f4826e25 | 421 | compute_trims (ref, live, &head_trim, &tail_trim, stmt); |
339f327d | 422 | |
423 | /* Tail trimming is easy, we can just reduce the count. */ | |
424 | if (tail_trim) | |
425 | decrement_count (stmt, tail_trim); | |
426 | ||
427 | /* Head trimming requires adjusting all the arguments. */ | |
428 | if (head_trim) | |
429 | { | |
430 | tree *dst = gimple_call_arg_ptr (stmt, 0); | |
431 | increment_start_addr (stmt, dst, head_trim); | |
432 | decrement_count (stmt, head_trim); | |
433 | } | |
434 | break; | |
435 | } | |
436 | ||
437 | default: | |
438 | break; | |
439 | } | |
440 | } | |
441 | ||
64123137 | 442 | /* STMT is a memory write where one or more bytes written are dead |
443 | stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the | |
444 | bitmap of stores that are actually live. | |
445 | ||
446 | Attempt to rewrite STMT so that it writes fewer memory locations. Right | |
447 | now we only support trimming at the start or end of the memory region. | |
448 | It's not clear how much there is to be gained by trimming from the middle | |
449 | of the region. */ | |
450 | ||
451 | static void | |
452 | maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
453 | { | |
1bcbd566 | 454 | if (is_gimple_assign (stmt) |
455 | && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) | |
64123137 | 456 | { |
457 | switch (gimple_assign_rhs_code (stmt)) | |
458 | { | |
56ce87e3 | 459 | case CONSTRUCTOR: |
460 | maybe_trim_constructor_store (ref, live, stmt); | |
461 | break; | |
64123137 | 462 | case COMPLEX_CST: |
463 | maybe_trim_complex_store (ref, live, stmt); | |
464 | break; | |
465 | default: | |
466 | break; | |
467 | } | |
468 | } | |
469 | } | |
4ee9c684 | 470 | |
4fb5e5ca | 471 | /* A helper of dse_optimize_stmt. |
258bd648 | 472 | Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate |
473 | statement *USE_STMT that may prove STMT to be dead. | |
4fb5e5ca | 474 | Return TRUE if the above conditions are met, otherwise FALSE. */ |
475 | ||
64123137 | 476 | static dse_store_status |
477 | dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, | |
478 | bool byte_tracking_enabled, sbitmap live_bytes) | |
4fb5e5ca | 479 | { |
42acab1c | 480 | gimple *temp; |
dd277d48 | 481 | unsigned cnt = 0; |
4fb5e5ca | 482 | |
4fb5e5ca | 483 | *use_stmt = NULL; |
4fb5e5ca | 484 | |
dd277d48 | 485 | /* Find the first dominated statement that clobbers (part of) the |
486 | memory stmt stores to with no intermediate statement that may use | |
487 | part of the memory stmt stores. That is, find a store that may | |
488 | prove stmt to be a dead store. */ | |
489 | temp = stmt; | |
490 | do | |
491 | { | |
42acab1c | 492 | gimple *use_stmt, *defvar_def; |
dd277d48 | 493 | imm_use_iterator ui; |
494 | bool fail = false; | |
495 | tree defvar; | |
496 | ||
497 | /* Limit stmt walking to be linear in the number of possibly | |
498 | dead stores. */ | |
499 | if (++cnt > 256) | |
64123137 | 500 | return DSE_STORE_LIVE; |
4fb5e5ca | 501 | |
75a70cf9 | 502 | if (gimple_code (temp) == GIMPLE_PHI) |
dd277d48 | 503 | defvar = PHI_RESULT (temp); |
504 | else | |
505 | defvar = gimple_vdef (temp); | |
48089971 | 506 | defvar_def = temp; |
dd277d48 | 507 | temp = NULL; |
508 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) | |
77ad2905 | 509 | { |
dd277d48 | 510 | cnt++; |
161fe168 | 511 | |
43e2b34d | 512 | /* If we ever reach our DSE candidate stmt again fail. We |
513 | cannot handle dead stores in loops. */ | |
514 | if (use_stmt == stmt) | |
515 | { | |
516 | fail = true; | |
517 | BREAK_FROM_IMM_USE_STMT (ui); | |
518 | } | |
dd277d48 | 519 | /* In simple cases we can look through PHI nodes, but we |
520 | have to be careful with loops and with memory references | |
521 | containing operands that are also operands of PHI nodes. | |
522 | See gcc.c-torture/execute/20051110-*.c. */ | |
43e2b34d | 523 | else if (gimple_code (use_stmt) == GIMPLE_PHI) |
dd277d48 | 524 | { |
525 | if (temp | |
43e2b34d | 526 | /* Make sure we are not in a loop latch block. */ |
527 | || gimple_bb (stmt) == gimple_bb (use_stmt) | |
dd277d48 | 528 | || dominated_by_p (CDI_DOMINATORS, |
43e2b34d | 529 | gimple_bb (stmt), gimple_bb (use_stmt)) |
530 | /* We can look through PHIs to regions post-dominating | |
531 | the DSE candidate stmt. */ | |
532 | || !dominated_by_p (CDI_POST_DOMINATORS, | |
533 | gimple_bb (stmt), gimple_bb (use_stmt))) | |
dd277d48 | 534 | { |
535 | fail = true; | |
536 | BREAK_FROM_IMM_USE_STMT (ui); | |
537 | } | |
64123137 | 538 | /* Do not consider the PHI as use if it dominates the |
48089971 | 539 | stmt defining the virtual operand we are processing, |
540 | we have processed it already in this case. */ | |
541 | if (gimple_bb (defvar_def) != gimple_bb (use_stmt) | |
542 | && !dominated_by_p (CDI_DOMINATORS, | |
543 | gimple_bb (defvar_def), | |
544 | gimple_bb (use_stmt))) | |
545 | temp = use_stmt; | |
dd277d48 | 546 | } |
547 | /* If the statement is a use the store is not dead. */ | |
258bd648 | 548 | else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
161fe168 | 549 | { |
550 | fail = true; | |
dd277d48 | 551 | BREAK_FROM_IMM_USE_STMT (ui); |
552 | } | |
553 | /* If this is a store, remember it or bail out if we have | |
554 | multiple ones (the will be in different CFG parts then). */ | |
555 | else if (gimple_vdef (use_stmt)) | |
556 | { | |
557 | if (temp) | |
558 | { | |
559 | fail = true; | |
560 | BREAK_FROM_IMM_USE_STMT (ui); | |
561 | } | |
562 | temp = use_stmt; | |
161fe168 | 563 | } |
564 | } | |
565 | ||
dd277d48 | 566 | if (fail) |
64123137 | 567 | { |
568 | /* STMT might be partially dead and we may be able to reduce | |
569 | how many memory locations it stores into. */ | |
570 | if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
571 | return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
572 | return DSE_STORE_LIVE; | |
573 | } | |
dd277d48 | 574 | |
575 | /* If we didn't find any definition this means the store is dead | |
576 | if it isn't a store to global reachable memory. In this case | |
577 | just pretend the stmt makes itself dead. Otherwise fail. */ | |
578 | if (!temp) | |
4fb5e5ca | 579 | { |
258bd648 | 580 | if (ref_may_alias_global_p (ref)) |
64123137 | 581 | return DSE_STORE_LIVE; |
dd277d48 | 582 | |
583 | temp = stmt; | |
789aa951 | 584 | break; |
4fb5e5ca | 585 | } |
64123137 | 586 | |
587 | if (byte_tracking_enabled && temp) | |
588 | clear_bytes_written_by (live_bytes, temp, ref); | |
4fb5e5ca | 589 | } |
64123137 | 590 | /* Continue walking until we reach a full kill as a single statement |
591 | or there are no more live bytes. */ | |
592 | while (!stmt_kills_ref_p (temp, ref) | |
593 | && !(byte_tracking_enabled && bitmap_empty_p (live_bytes))); | |
4fb5e5ca | 594 | |
dd277d48 | 595 | *use_stmt = temp; |
64123137 | 596 | return DSE_STORE_DEAD; |
597 | } | |
598 | ||
599 | ||
600 | class dse_dom_walker : public dom_walker | |
601 | { | |
602 | public: | |
603 | dse_dom_walker (cdi_direction direction) | |
07a7b947 | 604 | : dom_walker (direction), |
605 | m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)), | |
606 | m_byte_tracking_enabled (false) {} | |
64123137 | 607 | |
608 | virtual edge before_dom_children (basic_block); | |
609 | ||
610 | private: | |
07a7b947 | 611 | auto_sbitmap m_live_bytes; |
64123137 | 612 | bool m_byte_tracking_enabled; |
613 | void dse_optimize_stmt (gimple_stmt_iterator *); | |
614 | }; | |
615 | ||
a0b1e585 | 616 | /* Delete a dead call at GSI, which is mem* call of some kind. */ |
64123137 | 617 | static void |
ec40332f | 618 | delete_dead_call (gimple_stmt_iterator *gsi) |
64123137 | 619 | { |
ec40332f | 620 | gimple *stmt = gsi_stmt (*gsi); |
64123137 | 621 | if (dump_file && (dump_flags & TDF_DETAILS)) |
622 | { | |
623 | fprintf (dump_file, " Deleted dead call: "); | |
1ffa4346 | 624 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
64123137 | 625 | fprintf (dump_file, "\n"); |
626 | } | |
627 | ||
628 | tree lhs = gimple_call_lhs (stmt); | |
64123137 | 629 | if (lhs) |
630 | { | |
631 | tree ptr = gimple_call_arg (stmt, 0); | |
632 | gimple *new_stmt = gimple_build_assign (lhs, ptr); | |
633 | unlink_stmt_vdef (stmt); | |
ec40332f | 634 | if (gsi_replace (gsi, new_stmt, true)) |
64123137 | 635 | bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); |
636 | } | |
637 | else | |
638 | { | |
639 | /* Then we need to fix the operand of the consuming stmt. */ | |
640 | unlink_stmt_vdef (stmt); | |
641 | ||
642 | /* Remove the dead store. */ | |
ec40332f | 643 | if (gsi_remove (gsi, true)) |
64123137 | 644 | bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); |
645 | release_defs (stmt); | |
646 | } | |
4fb5e5ca | 647 | } |
648 | ||
a0b1e585 | 649 | /* Delete a dead store at GSI, which is a gimple assignment. */ |
64123137 | 650 | |
651 | static void | |
ec40332f | 652 | delete_dead_assignment (gimple_stmt_iterator *gsi) |
64123137 | 653 | { |
ec40332f | 654 | gimple *stmt = gsi_stmt (*gsi); |
64123137 | 655 | if (dump_file && (dump_flags & TDF_DETAILS)) |
656 | { | |
657 | fprintf (dump_file, " Deleted dead store: "); | |
1ffa4346 | 658 | print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
64123137 | 659 | fprintf (dump_file, "\n"); |
660 | } | |
661 | ||
662 | /* Then we need to fix the operand of the consuming stmt. */ | |
663 | unlink_stmt_vdef (stmt); | |
664 | ||
665 | /* Remove the dead store. */ | |
64123137 | 666 | basic_block bb = gimple_bb (stmt); |
ec40332f | 667 | if (gsi_remove (gsi, true)) |
64123137 | 668 | bitmap_set_bit (need_eh_cleanup, bb->index); |
669 | ||
670 | /* And release any SSA_NAMEs set in this statement back to the | |
671 | SSA_NAME manager. */ | |
672 | release_defs (stmt); | |
673 | } | |
4fb5e5ca | 674 | |
4ee9c684 | 675 | /* Attempt to eliminate dead stores in the statement referenced by BSI. |
676 | ||
677 | A dead store is a store into a memory location which will later be | |
678 | overwritten by another store without any intervening loads. In this | |
679 | case the earlier store can be deleted. | |
680 | ||
681 | In our SSA + virtual operand world we use immediate uses of virtual | |
682 | operands to detect dead stores. If a store's virtual definition | |
683 | is used precisely once by a later store to the same location which | |
684 | post dominates the first store, then the first store is dead. */ | |
685 | ||
64123137 | 686 | void |
687 | dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) | |
4ee9c684 | 688 | { |
42acab1c | 689 | gimple *stmt = gsi_stmt (*gsi); |
4ee9c684 | 690 | |
e920115e | 691 | /* If this statement has no virtual defs, then there is nothing |
4ee9c684 | 692 | to do. */ |
dd277d48 | 693 | if (!gimple_vdef (stmt)) |
4ee9c684 | 694 | return; |
695 | ||
9f559b20 | 696 | /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
697 | if (gimple_has_volatile_ops (stmt) | |
698 | && (!gimple_clobber_p (stmt) | |
699 | || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
52c2a307 | 700 | return; |
701 | ||
64123137 | 702 | ao_ref ref; |
703 | if (!initialize_ao_ref_for_dse (stmt, &ref)) | |
704 | return; | |
705 | ||
258bd648 | 706 | /* We know we have virtual definitions. We can handle assignments and |
707 | some builtin calls. */ | |
708 | if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
709 | { | |
710 | switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
711 | { | |
712 | case BUILT_IN_MEMCPY: | |
713 | case BUILT_IN_MEMMOVE: | |
714 | case BUILT_IN_MEMSET: | |
715 | { | |
b37570be | 716 | /* Occasionally calls with an explicit length of zero |
717 | show up in the IL. It's pointless to do analysis | |
718 | on them, they're trivially dead. */ | |
719 | tree size = gimple_call_arg (stmt, 2); | |
720 | if (integer_zerop (size)) | |
721 | { | |
722 | delete_dead_call (gsi); | |
723 | return; | |
724 | } | |
725 | ||
42acab1c | 726 | gimple *use_stmt; |
64123137 | 727 | enum dse_store_status store_status; |
728 | m_byte_tracking_enabled | |
729 | = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
730 | store_status = dse_classify_store (&ref, stmt, &use_stmt, | |
731 | m_byte_tracking_enabled, | |
732 | m_live_bytes); | |
733 | if (store_status == DSE_STORE_LIVE) | |
258bd648 | 734 | return; |
735 | ||
64123137 | 736 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
258bd648 | 737 | { |
339f327d | 738 | maybe_trim_memstar_call (&ref, m_live_bytes, stmt); |
64123137 | 739 | return; |
258bd648 | 740 | } |
258bd648 | 741 | |
64123137 | 742 | if (store_status == DSE_STORE_DEAD) |
ec40332f | 743 | delete_dead_call (gsi); |
64123137 | 744 | return; |
258bd648 | 745 | } |
64123137 | 746 | |
258bd648 | 747 | default: |
748 | return; | |
749 | } | |
750 | } | |
751 | ||
75a70cf9 | 752 | if (is_gimple_assign (stmt)) |
4ee9c684 | 753 | { |
42acab1c | 754 | gimple *use_stmt; |
4ee9c684 | 755 | |
258bd648 | 756 | /* Self-assignments are zombies. */ |
757 | if (operand_equal_p (gimple_assign_rhs1 (stmt), | |
758 | gimple_assign_lhs (stmt), 0)) | |
759 | use_stmt = stmt; | |
760 | else | |
761 | { | |
64123137 | 762 | m_byte_tracking_enabled |
763 | = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
764 | enum dse_store_status store_status; | |
765 | store_status = dse_classify_store (&ref, stmt, &use_stmt, | |
766 | m_byte_tracking_enabled, | |
767 | m_live_bytes); | |
768 | if (store_status == DSE_STORE_LIVE) | |
258bd648 | 769 | return; |
64123137 | 770 | |
771 | if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) | |
772 | { | |
773 | maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); | |
774 | return; | |
775 | } | |
258bd648 | 776 | } |
2bf1fefd | 777 | |
88114c9f | 778 | /* Now we know that use_stmt kills the LHS of stmt. */ |
779 | ||
9f559b20 | 780 | /* But only remove *this_2(D) ={v} {CLOBBER} if killed by |
781 | another clobber stmt. */ | |
782 | if (gimple_clobber_p (stmt) | |
783 | && !gimple_clobber_p (use_stmt)) | |
784 | return; | |
785 | ||
ec40332f | 786 | delete_dead_assignment (gsi); |
4ee9c684 | 787 | } |
788 | } | |
789 | ||
96752458 | 790 | edge |
54c91640 | 791 | dse_dom_walker::before_dom_children (basic_block bb) |
4ee9c684 | 792 | { |
75a70cf9 | 793 | gimple_stmt_iterator gsi; |
4ee9c684 | 794 | |
3222e348 | 795 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
796 | { | |
797 | dse_optimize_stmt (&gsi); | |
798 | if (gsi_end_p (gsi)) | |
799 | gsi = gsi_last_bb (bb); | |
800 | else | |
801 | gsi_prev (&gsi); | |
802 | } | |
96752458 | 803 | return NULL; |
4ee9c684 | 804 | } |
805 | ||
7620bc82 | 806 | namespace { |
807 | ||
808 | const pass_data pass_data_dse = | |
65b0537f | 809 | { |
810 | GIMPLE_PASS, /* type */ | |
811 | "dse", /* name */ | |
812 | OPTGROUP_NONE, /* optinfo_flags */ | |
65b0537f | 813 | TV_TREE_DSE, /* tv_id */ |
814 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
815 | 0, /* properties_provided */ | |
816 | 0, /* properties_destroyed */ | |
817 | 0, /* todo_flags_start */ | |
8b88439e | 818 | 0, /* todo_flags_finish */ |
65b0537f | 819 | }; |
820 | ||
7620bc82 | 821 | class pass_dse : public gimple_opt_pass |
65b0537f | 822 | { |
823 | public: | |
824 | pass_dse (gcc::context *ctxt) | |
825 | : gimple_opt_pass (pass_data_dse, ctxt) | |
826 | {} | |
827 | ||
828 | /* opt_pass methods: */ | |
829 | opt_pass * clone () { return new pass_dse (m_ctxt); } | |
830 | virtual bool gate (function *) { return flag_tree_dse != 0; } | |
831 | virtual unsigned int execute (function *); | |
832 | ||
833 | }; // class pass_dse | |
4fb5e5ca | 834 | |
65b0537f | 835 | unsigned int |
836 | pass_dse::execute (function *fun) | |
4ee9c684 | 837 | { |
d02c8339 | 838 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
839 | ||
ec415c45 | 840 | renumber_gimple_stmt_uids (); |
4ee9c684 | 841 | |
842 | /* We might consider making this a property of each pass so that it | |
843 | can be [re]computed on an as-needed basis. Particularly since | |
844 | this pass could be seen as an extension of DCE which needs post | |
845 | dominators. */ | |
846 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
dd277d48 | 847 | calculate_dominance_info (CDI_DOMINATORS); |
4ee9c684 | 848 | |
4ee9c684 | 849 | /* Dead store elimination is fundamentally a walk of the post-dominator |
850 | tree and a backwards walk of statements within each block. */ | |
65b0537f | 851 | dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); |
4ee9c684 | 852 | |
d02c8339 | 853 | /* Removal of stores may make some EH edges dead. Purge such edges from |
854 | the CFG as needed. */ | |
855 | if (!bitmap_empty_p (need_eh_cleanup)) | |
856 | { | |
857 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
858 | cleanup_tree_cfg (); | |
859 | } | |
860 | ||
861 | BITMAP_FREE (need_eh_cleanup); | |
64123137 | 862 | |
4ee9c684 | 863 | /* For now, just wipe the post-dominator information. */ |
864 | free_dominance_info (CDI_POST_DOMINATORS); | |
2a1990e9 | 865 | return 0; |
4ee9c684 | 866 | } |
867 | ||
7620bc82 | 868 | } // anon namespace |
869 | ||
cbe8bda8 | 870 | gimple_opt_pass * |
871 | make_pass_dse (gcc::context *ctxt) | |
872 | { | |
873 | return new pass_dse (ctxt); | |
874 | } |