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