re PR c++/79790 ([C++17] ICE class template argument deduction failed)
[official-gcc.git] / gcc / tree-ssa-dse.c
blob70c8b073359a75ff9ec7e5c7f32b21c96310bb59
1 /* Dead store elimination
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
39 /* This file implements dead store elimination.
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.
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.
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.
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.
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. */
69 /* Bitmap of blocks that have had EH statements cleaned. We should
70 remove their dead edges eventually. */
71 static bitmap need_eh_cleanup;
73 /* Return value from dse_classify_store */
74 enum dse_store_status
76 DSE_STORE_LIVE,
77 DSE_STORE_MAYBE_PARTIAL_DEAD,
78 DSE_STORE_DEAD
81 /* STMT is a statement that may write into memory. Analyze it and
82 initialize WRITE to describe how STMT affects memory.
84 Return TRUE if the the statement was analyzed, FALSE otherwise.
86 It is always safe to return FALSE. But typically better optimziation
87 can be achieved by analyzing more statements. */
89 static bool
90 initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
92 /* It's advantageous to handle certain mem* functions. */
93 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
95 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
97 case BUILT_IN_MEMCPY:
98 case BUILT_IN_MEMMOVE:
99 case BUILT_IN_MEMSET:
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;
108 default:
109 break;
112 else if (is_gimple_assign (stmt))
114 ao_ref_init (write, gimple_assign_lhs (stmt));
115 return true;
117 return false;
120 /* Given REF from the the alias oracle, return TRUE if it is a valid
121 memory reference for dead store elimination, false otherwise.
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. */
127 static bool
128 valid_ao_ref_for_dse (ao_ref *ref)
130 return (ao_ref_base (ref)
131 && ref->max_size != -1
132 && ref->size != 0
133 && ref->max_size == ref->size
134 && (ref->offset % BITS_PER_UNIT) == 0
135 && (ref->size % BITS_PER_UNIT) == 0
136 && (ref->size != -1));
139 /* Normalize COPY (an ao_ref) relative to REF. Essentially when we are
140 done COPY will only refer bytes found within REF.
142 We have already verified that COPY intersects at least one
143 byte with REF. */
145 static void
146 normalize_ref (ao_ref *copy, ao_ref *ref)
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)
153 copy->size -= (ref->offset - copy->offset);
154 copy->offset = ref->offset;
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));
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.
166 This routine must be conservative. If we don't know the offset or
167 actual size written, assume nothing was written. */
169 static void
170 clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref)
172 ao_ref write;
173 if (!initialize_ao_ref_for_dse (stmt, &write))
174 return;
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)
179 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF)
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)))
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);
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. */
197 static bool
198 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes)
200 if (valid_ao_ref_for_dse (ref)
201 && (ref->size / BITS_PER_UNIT
202 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)))
204 bitmap_clear (live_bytes);
205 bitmap_set_range (live_bytes, 0, ref->size / BITS_PER_UNIT);
206 return true;
208 return false;
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.
214 Store the number of elements trimmed from the head and tail in
215 TRIM_HEAD and TRIM_TAIL.
217 STMT is the statement being trimmed and is used for debugging dump
218 output only. */
220 static void
221 compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail,
222 gimple *stmt)
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. */
229 /* Now identify how much, if any of the tail we can chop off. */
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;
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;
239 if ((*trim_head || *trim_tail)
240 && dump_file && (dump_flags & TDF_DETAILS))
242 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ",
243 *trim_head, *trim_tail);
244 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
245 fprintf (dump_file, "\n");
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.
253 Attempt to rewrite STMT so that only the real or imaginary part of
254 the object is actually stored. */
256 static void
257 maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt)
259 int trim_head, trim_tail;
260 compute_trims (ref, live, &trim_head, &trim_tail, stmt);
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)
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);
275 else if (trim_head * 2 >= ref->size / BITS_PER_UNIT)
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);
285 /* Other cases indicate parts of both the real and imag subobjects
286 are live. We do not try to optimize those cases. */
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.
293 Attempt to rewrite STMT so that only the real or imaginary part of
294 the object is actually stored.
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. */
301 static void
302 maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt)
304 tree ctor = gimple_assign_rhs1 (stmt);
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);
310 int head_trim = 0;
311 int tail_trim = 0;
312 compute_trims (ref, live, &head_trim, &tail_trim, stmt);
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)
318 /* We want &lhs for the MEM_REF expression. */
319 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt));
321 if (! is_gimple_min_invariant (lhs_addr))
322 return;
324 /* The number of bytes for the new constructor. */
325 int count = (ref->size / BITS_PER_UNIT) - head_trim - tail_trim;
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);
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));
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));
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));
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)
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));
361 static void
362 increment_start_addr (gimple *stmt, tree *where, int increment)
364 if (TREE_CODE (*where) == SSA_NAME)
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;
377 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node,
378 *where,
379 build_int_cst (ptr_type_node,
380 increment)));
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.
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. */
391 static void
392 maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
394 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
396 case BUILT_IN_MEMCPY:
397 case BUILT_IN_MEMMOVE:
399 int head_trim, tail_trim;
400 compute_trims (ref, live, &head_trim, &tail_trim, stmt);
402 /* Tail trimming is easy, we can just reduce the count. */
403 if (tail_trim)
404 decrement_count (stmt, tail_trim);
406 /* Head trimming requires adjusting all the arguments. */
407 if (head_trim)
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);
415 break;
418 case BUILT_IN_MEMSET:
420 int head_trim, tail_trim;
421 compute_trims (ref, live, &head_trim, &tail_trim, stmt);
423 /* Tail trimming is easy, we can just reduce the count. */
424 if (tail_trim)
425 decrement_count (stmt, tail_trim);
427 /* Head trimming requires adjusting all the arguments. */
428 if (head_trim)
430 tree *dst = gimple_call_arg_ptr (stmt, 0);
431 increment_start_addr (stmt, dst, head_trim);
432 decrement_count (stmt, head_trim);
434 break;
437 default:
438 break;
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.
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. */
451 static void
452 maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt)
454 if (is_gimple_assign (stmt)
455 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF)
457 switch (gimple_assign_rhs_code (stmt))
459 case CONSTRUCTOR:
460 maybe_trim_constructor_store (ref, live, stmt);
461 break;
462 case COMPLEX_CST:
463 maybe_trim_complex_store (ref, live, stmt);
464 break;
465 default:
466 break;
471 /* A helper of dse_optimize_stmt.
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.
474 Return TRUE if the above conditions are met, otherwise FALSE. */
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)
480 gimple *temp;
481 unsigned cnt = 0;
483 *use_stmt = NULL;
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;
492 gimple *use_stmt, *defvar_def;
493 imm_use_iterator ui;
494 bool fail = false;
495 tree defvar;
497 /* Limit stmt walking to be linear in the number of possibly
498 dead stores. */
499 if (++cnt > 256)
500 return DSE_STORE_LIVE;
502 if (gimple_code (temp) == GIMPLE_PHI)
503 defvar = PHI_RESULT (temp);
504 else
505 defvar = gimple_vdef (temp);
506 defvar_def = temp;
507 temp = NULL;
508 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
510 cnt++;
512 /* If we ever reach our DSE candidate stmt again fail. We
513 cannot handle dead stores in loops. */
514 if (use_stmt == stmt)
516 fail = true;
517 BREAK_FROM_IMM_USE_STMT (ui);
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. */
523 else if (gimple_code (use_stmt) == GIMPLE_PHI)
525 if (temp
526 /* Make sure we are not in a loop latch block. */
527 || gimple_bb (stmt) == gimple_bb (use_stmt)
528 || dominated_by_p (CDI_DOMINATORS,
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)))
535 fail = true;
536 BREAK_FROM_IMM_USE_STMT (ui);
538 /* Do not consider the PHI as use if it dominates the
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;
547 /* If the statement is a use the store is not dead. */
548 else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
550 fail = true;
551 BREAK_FROM_IMM_USE_STMT (ui);
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))
557 if (temp)
559 fail = true;
560 BREAK_FROM_IMM_USE_STMT (ui);
562 temp = use_stmt;
566 if (fail)
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;
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)
580 if (ref_may_alias_global_p (ref))
581 return DSE_STORE_LIVE;
583 temp = stmt;
584 break;
587 if (byte_tracking_enabled && temp)
588 clear_bytes_written_by (live_bytes, temp, ref);
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)));
595 *use_stmt = temp;
596 return DSE_STORE_DEAD;
600 class dse_dom_walker : public dom_walker
602 public:
603 dse_dom_walker (cdi_direction direction)
604 : dom_walker (direction),
605 m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)),
606 m_byte_tracking_enabled (false) {}
608 virtual edge before_dom_children (basic_block);
610 private:
611 auto_sbitmap m_live_bytes;
612 bool m_byte_tracking_enabled;
613 void dse_optimize_stmt (gimple_stmt_iterator *);
616 /* Delete a dead call at GSI, which is mem* call of some kind. */
617 static void
618 delete_dead_call (gimple_stmt_iterator *gsi)
620 gimple *stmt = gsi_stmt (*gsi);
621 if (dump_file && (dump_flags & TDF_DETAILS))
623 fprintf (dump_file, " Deleted dead call: ");
624 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
625 fprintf (dump_file, "\n");
628 tree lhs = gimple_call_lhs (stmt);
629 if (lhs)
631 tree ptr = gimple_call_arg (stmt, 0);
632 gimple *new_stmt = gimple_build_assign (lhs, ptr);
633 unlink_stmt_vdef (stmt);
634 if (gsi_replace (gsi, new_stmt, true))
635 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
637 else
639 /* Then we need to fix the operand of the consuming stmt. */
640 unlink_stmt_vdef (stmt);
642 /* Remove the dead store. */
643 if (gsi_remove (gsi, true))
644 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
645 release_defs (stmt);
649 /* Delete a dead store at GSI, which is a gimple assignment. */
651 static void
652 delete_dead_assignment (gimple_stmt_iterator *gsi)
654 gimple *stmt = gsi_stmt (*gsi);
655 if (dump_file && (dump_flags & TDF_DETAILS))
657 fprintf (dump_file, " Deleted dead store: ");
658 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
659 fprintf (dump_file, "\n");
662 /* Then we need to fix the operand of the consuming stmt. */
663 unlink_stmt_vdef (stmt);
665 /* Remove the dead store. */
666 basic_block bb = gimple_bb (stmt);
667 if (gsi_remove (gsi, true))
668 bitmap_set_bit (need_eh_cleanup, bb->index);
670 /* And release any SSA_NAMEs set in this statement back to the
671 SSA_NAME manager. */
672 release_defs (stmt);
675 /* Attempt to eliminate dead stores in the statement referenced by BSI.
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.
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. */
686 void
687 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
689 gimple *stmt = gsi_stmt (*gsi);
691 /* If this statement has no virtual defs, then there is nothing
692 to do. */
693 if (!gimple_vdef (stmt))
694 return;
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))
700 return;
702 ao_ref ref;
703 if (!initialize_ao_ref_for_dse (stmt, &ref))
704 return;
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))
710 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
712 case BUILT_IN_MEMCPY:
713 case BUILT_IN_MEMMOVE:
714 case BUILT_IN_MEMSET:
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))
722 delete_dead_call (gsi);
723 return;
726 gimple *use_stmt;
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)
734 return;
736 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
738 maybe_trim_memstar_call (&ref, m_live_bytes, stmt);
739 return;
742 if (store_status == DSE_STORE_DEAD)
743 delete_dead_call (gsi);
744 return;
747 default:
748 return;
752 if (is_gimple_assign (stmt))
754 gimple *use_stmt;
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
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)
769 return;
771 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
773 maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt);
774 return;
778 /* Now we know that use_stmt kills the LHS of stmt. */
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;
786 delete_dead_assignment (gsi);
790 edge
791 dse_dom_walker::before_dom_children (basic_block bb)
793 gimple_stmt_iterator gsi;
795 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
797 dse_optimize_stmt (&gsi);
798 if (gsi_end_p (gsi))
799 gsi = gsi_last_bb (bb);
800 else
801 gsi_prev (&gsi);
803 return NULL;
806 namespace {
808 const pass_data pass_data_dse =
810 GIMPLE_PASS, /* type */
811 "dse", /* name */
812 OPTGROUP_NONE, /* optinfo_flags */
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 */
818 0, /* todo_flags_finish */
821 class pass_dse : public gimple_opt_pass
823 public:
824 pass_dse (gcc::context *ctxt)
825 : gimple_opt_pass (pass_data_dse, ctxt)
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 *);
833 }; // class pass_dse
835 unsigned int
836 pass_dse::execute (function *fun)
838 need_eh_cleanup = BITMAP_ALLOC (NULL);
840 renumber_gimple_stmt_uids ();
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);
847 calculate_dominance_info (CDI_DOMINATORS);
849 /* Dead store elimination is fundamentally a walk of the post-dominator
850 tree and a backwards walk of statements within each block. */
851 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
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))
857 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
858 cleanup_tree_cfg ();
861 BITMAP_FREE (need_eh_cleanup);
863 /* For now, just wipe the post-dominator information. */
864 free_dominance_info (CDI_POST_DOMINATORS);
865 return 0;
868 } // anon namespace
870 gimple_opt_pass *
871 make_pass_dse (gcc::context *ctxt)
873 return new pass_dse (ctxt);