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