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)
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/>. */
22 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
31 #include "gimple-iterator.h"
35 #include "tree-cfgcleanup.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
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
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 */
77 DSE_STORE_MAYBE_PARTIAL_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. */
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
)))
98 case BUILT_IN_MEMMOVE
:
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
);
112 else if (is_gimple_assign (stmt
))
114 ao_ref_init (write
, gimple_assign_lhs (stmt
));
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
128 valid_ao_ref_for_dse (ao_ref
*ref
)
130 return (ao_ref_base (ref
)
131 && ref
->max_size
!= -1
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
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. */
170 clear_bytes_written_by (sbitmap live_bytes
, gimple
*stmt
, ao_ref
*ref
)
173 if (!initialize_ao_ref_for_dse (stmt
, &write
))
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. */
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
);
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
221 compute_trims (ao_ref
*ref
, sbitmap live
, int *trim_head
, int *trim_tail
,
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. */
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. */
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. */
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);
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
))
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
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. */
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
)
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
));
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
);
373 update_stmt (gsi_stmt (gsi
));
377 *where
= build_fold_addr_expr (fold_build2 (MEM_REF
, char_type_node
,
379 build_int_cst (ptr_type_node
,
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. */
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. */
404 decrement_count (stmt
, tail_trim
);
406 /* Head trimming requires adjusting all the arguments. */
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
);
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. */
425 decrement_count (stmt
, tail_trim
);
427 /* Head trimming requires adjusting all the arguments. */
430 tree
*dst
= gimple_call_arg_ptr (stmt
, 0);
431 increment_start_addr (stmt
, dst
, head_trim
);
432 decrement_count (stmt
, head_trim
);
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
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
))
460 maybe_trim_constructor_store (ref
, live
, stmt
);
463 maybe_trim_complex_store (ref
, live
, stmt
);
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
)
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. */
492 gimple
*use_stmt
, *defvar_def
;
497 /* Limit stmt walking to be linear in the number of possibly
500 return DSE_STORE_LIVE
;
502 if (gimple_code (temp
) == GIMPLE_PHI
)
503 defvar
= PHI_RESULT (temp
);
505 defvar
= gimple_vdef (temp
);
508 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, defvar
)
512 /* If we ever reach our DSE candidate stmt again fail. We
513 cannot handle dead stores in loops. */
514 if (use_stmt
== stmt
)
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
)
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
)))
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
)))
547 /* If the statement is a use the store is not dead. */
548 else if (ref_maybe_used_by_stmt_p (use_stmt
, ref
))
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
))
560 BREAK_FROM_IMM_USE_STMT (ui
);
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. */
580 if (ref_may_alias_global_p (ref
))
581 return DSE_STORE_LIVE
;
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
)));
596 return DSE_STORE_DEAD
;
600 class dse_dom_walker
: public dom_walker
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
);
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. */
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
);
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
);
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
);
649 /* Delete a dead store at GSI, which is a gimple assignment. */
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
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. */
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
693 if (!gimple_vdef (stmt
))
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
))
703 if (!initialize_ao_ref_for_dse (stmt
, &ref
))
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
);
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
,
733 if (store_status
== DSE_STORE_LIVE
)
736 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
738 maybe_trim_memstar_call (&ref
, m_live_bytes
, stmt
);
742 if (store_status
== DSE_STORE_DEAD
)
743 delete_dead_call (gsi
);
752 if (is_gimple_assign (stmt
))
756 /* Self-assignments are zombies. */
757 if (operand_equal_p (gimple_assign_rhs1 (stmt
),
758 gimple_assign_lhs (stmt
), 0))
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
,
768 if (store_status
== DSE_STORE_LIVE
)
771 if (store_status
== DSE_STORE_MAYBE_PARTIAL_DEAD
)
773 maybe_trim_partially_dead_store (&ref
, m_live_bytes
, stmt
);
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
))
786 delete_dead_assignment (gsi
);
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
);
799 gsi
= gsi_last_bb (bb
);
808 const pass_data pass_data_dse
=
810 GIMPLE_PASS
, /* type */
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
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
*);
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
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
);
861 BITMAP_FREE (need_eh_cleanup
);
863 /* For now, just wipe the post-dominator information. */
864 free_dominance_info (CDI_POST_DOMINATORS
);
871 make_pass_dse (gcc::context
*ctxt
)
873 return new pass_dse (ctxt
);