1 /* Dead store elimination
2 Copyright (C) 2004, 2005, 2006, 2007 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"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-dump.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 /* Given an aggregate, this records the parts of it which have been
71 struct aggregate_vardecl_d
76 /* Some aggregates are too big for us to handle or never get stored
77 to as a whole. If this field is TRUE, we don't care about this
81 /* Number of parts in the whole. */
84 /* A bitmap of parts of the aggregate that have been set. If part N
85 of an aggregate has been stored to, bit N should be on. */
89 struct dse_global_data
91 /* This is the global bitmap for store statements.
93 Each statement has a unique ID. When we encounter a store statement
94 that we want to record, set the bit corresponding to the statement's
95 unique ID in this bitmap. */
98 /* A hash table containing the parts of an aggregate which have been
100 htab_t aggregate_vardecl
;
103 /* We allocate a bitmap-per-block for stores which are encountered
104 during the scan of that block. This allows us to restore the
105 global bitmap of stores when we finish processing a block. */
106 struct dse_block_local_data
111 /* Basic blocks of the potentially dead store and the following
112 store, for memory_address_same. */
113 struct address_walk_data
115 basic_block store1_bb
, store2_bb
;
118 static bool gate_dse (void);
119 static unsigned int tree_ssa_dse (void);
120 static void dse_initialize_block_local_data (struct dom_walk_data
*,
123 static void dse_optimize_stmt (struct dom_walk_data
*,
125 block_stmt_iterator
);
126 static void dse_record_phis (struct dom_walk_data
*, basic_block
);
127 static void dse_finalize_block (struct dom_walk_data
*, basic_block
);
128 static void record_voperand_set (bitmap
, bitmap
*, unsigned int);
129 static void dse_record_partial_aggregate_store (tree
, struct dse_global_data
*);
131 static unsigned max_stmt_uid
; /* Maximal uid of a statement. Uids to phi
132 nodes are assigned using the versions of
133 ssa names they define. */
135 /* Returns uid of statement STMT. */
138 get_stmt_uid (tree stmt
)
140 if (TREE_CODE (stmt
) == PHI_NODE
)
141 return SSA_NAME_VERSION (PHI_RESULT (stmt
)) + max_stmt_uid
;
143 return stmt_ann (stmt
)->uid
;
146 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */
149 record_voperand_set (bitmap global
, bitmap
*local
, unsigned int uid
)
151 /* Lazily allocate the bitmap. Note that we do not get a notification
152 when the block local data structures die, so we allocate the local
153 bitmap backed by the GC system. */
155 *local
= BITMAP_GGC_ALLOC ();
157 /* Set the bit in the local and global bitmaps. */
158 bitmap_set_bit (*local
, uid
);
159 bitmap_set_bit (global
, uid
);
162 /* Initialize block local data structures. */
165 dse_initialize_block_local_data (struct dom_walk_data
*walk_data
,
166 basic_block bb ATTRIBUTE_UNUSED
,
169 struct dse_block_local_data
*bd
170 = (struct dse_block_local_data
*)
171 VEC_last (void_p
, walk_data
->block_data_stack
);
173 /* If we are given a recycled block local data structure, ensure any
174 bitmap associated with the block is cleared. */
178 bitmap_clear (bd
->stores
);
182 /* Helper function for memory_address_same via walk_tree. Returns
183 non-NULL if it finds an SSA_NAME which is part of the address,
184 such that the definition of the SSA_NAME post-dominates the store
185 we want to delete but not the store that we believe makes it
186 redundant. This indicates that the address may change between
190 memory_ssa_name_same (tree
*expr_p
, int *walk_subtrees ATTRIBUTE_UNUSED
,
193 struct address_walk_data
*walk_data
= (struct address_walk_data
*) data
;
198 if (TREE_CODE (expr
) != SSA_NAME
)
201 /* If we've found a default definition, then there's no problem. Both
202 stores will post-dominate it. And def_bb will be NULL. */
203 if (SSA_NAME_IS_DEFAULT_DEF (expr
))
206 def_stmt
= SSA_NAME_DEF_STMT (expr
);
207 def_bb
= bb_for_stmt (def_stmt
);
209 /* DEF_STMT must dominate both stores. So if it is in the same
210 basic block as one, it does not post-dominate that store. */
211 if (walk_data
->store1_bb
!= def_bb
212 && dominated_by_p (CDI_POST_DOMINATORS
, walk_data
->store1_bb
, def_bb
))
214 if (walk_data
->store2_bb
== def_bb
215 || !dominated_by_p (CDI_POST_DOMINATORS
, walk_data
->store2_bb
,
217 /* Return non-NULL to stop the walk. */
224 /* Return TRUE if the destination memory address in STORE1 and STORE2
225 might be modified after STORE1, before control reaches STORE2. */
228 memory_address_same (tree store1
, tree store2
)
230 struct address_walk_data walk_data
;
232 walk_data
.store1_bb
= bb_for_stmt (store1
);
233 walk_data
.store2_bb
= bb_for_stmt (store2
);
235 return (walk_tree (&GIMPLE_STMT_OPERAND (store1
, 0), memory_ssa_name_same
,
240 /* Return the use stmt for the lhs of STMT following the virtual
241 def-use chains. Returns the MODIFY_EXPR stmt which lhs is equal to
242 the lhs of STMT or NULL_TREE if no such stmt can be found. */
244 get_use_of_stmt_lhs (tree stmt
,
245 use_operand_p
* first_use_p
,
246 use_operand_p
* use_p
, tree
* use_stmt
)
251 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
254 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
256 /* The stmt must have a single VDEF. */
257 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_VDEF
);
258 if (def_p
== NULL_DEF_OPERAND_P
)
261 if (!has_single_use (DEF_FROM_PTR (def_p
)))
263 /* Get the immediate use of the def. */
264 single_imm_use (DEF_FROM_PTR (def_p
), use_p
, use_stmt
);
265 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
267 if (TREE_CODE (*use_stmt
) != GIMPLE_MODIFY_STMT
)
272 /* Look at the use stmt and see if it's LHS matches
273 stmt's lhs SSA_NAME. */
274 def_p
= SINGLE_SSA_DEF_OPERAND (*use_stmt
, SSA_OP_VDEF
);
275 if (def_p
== NULL_DEF_OPERAND_P
)
278 usevar
= GIMPLE_STMT_OPERAND (*use_stmt
, 0);
279 if (operand_equal_p (usevar
, lhs
, 0))
282 if (!has_single_use (DEF_FROM_PTR (def_p
)))
284 single_imm_use (DEF_FROM_PTR (def_p
), use_p
, use_stmt
);
285 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
286 if (TREE_CODE (*use_stmt
) != GIMPLE_MODIFY_STMT
)
294 /* A helper of dse_optimize_stmt.
295 Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
296 use, and that one use is another VDEF clobbering the first one.
298 Return TRUE if the above conditions are met, otherwise FALSE. */
301 dse_possible_dead_store_p (tree stmt
,
302 use_operand_p
*first_use_p
,
303 use_operand_p
*use_p
,
305 struct dse_global_data
*dse_gd
,
306 struct dse_block_local_data
*bd
)
312 tree defvar
= NULL_TREE
, temp
;
313 tree prev_defvar
= NULL_TREE
;
314 stmt_ann_t ann
= stmt_ann (stmt
);
316 /* We want to verify that each virtual definition in STMT has
317 precisely one use and that all the virtual definitions are
318 used by the same single statement. When complete, we
319 want USE_STMT to refer to the one statement which uses
320 all of the virtual definitions from STMT. */
322 FOR_EACH_SSA_VDEF_OPERAND (var1
, vv
, stmt
, op_iter
)
324 defvar
= DEF_FROM_PTR (var1
);
326 /* If this virtual def does not have precisely one use, then
327 we will not be able to eliminate STMT. */
328 if (!has_single_use (defvar
))
334 /* Get the one and only immediate use of DEFVAR. */
335 single_imm_use (defvar
, use_p
, &temp
);
336 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
337 *first_use_p
= *use_p
;
339 /* In the case of memory partitions, we may get:
341 # MPT.764_162 = VDEF <MPT.764_161(D)>
343 # MPT.764_167 = VDEF <MPT.764_162>
346 So we must make sure we're talking about the same LHS.
348 if (TREE_CODE (temp
) == GIMPLE_MODIFY_STMT
)
350 tree base1
= get_base_address (GIMPLE_STMT_OPERAND (stmt
, 0));
351 tree base2
= get_base_address (GIMPLE_STMT_OPERAND (temp
, 0));
353 while (base1
&& INDIRECT_REF_P (base1
))
354 base1
= TREE_OPERAND (base1
, 0);
355 while (base2
&& INDIRECT_REF_P (base2
))
356 base2
= TREE_OPERAND (base2
, 0);
365 /* If the immediate use of DEF_VAR is not the same as the
366 previously find immediate uses, then we will not be able
367 to eliminate STMT. */
368 if (*use_stmt
== NULL
)
371 prev_defvar
= defvar
;
373 else if (temp
!= *use_stmt
)
375 /* The immediate use and the previously found immediate use
376 must be the same, except... if they're uses of different
377 parts of the whole. */
378 if (TREE_CODE (defvar
) == SSA_NAME
379 && TREE_CODE (SSA_NAME_VAR (defvar
)) == STRUCT_FIELD_TAG
380 && TREE_CODE (prev_defvar
) == SSA_NAME
381 && TREE_CODE (SSA_NAME_VAR (prev_defvar
)) == STRUCT_FIELD_TAG
382 && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar
))
383 == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar
))))
395 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
396 dse_record_partial_aggregate_store (stmt
, dse_gd
);
400 /* Skip through any PHI nodes we have already seen if the PHI
401 represents the only use of this store.
403 Note this does not handle the case where the store has
404 multiple VDEFs which all reach a set of PHI nodes in the same block. */
405 while (*use_p
!= NULL_USE_OPERAND_P
406 && TREE_CODE (*use_stmt
) == PHI_NODE
407 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (*use_stmt
)))
409 /* A PHI node can both define and use the same SSA_NAME if
410 the PHI is at the top of a loop and the PHI_RESULT is
411 a loop invariant and copies have not been fully propagated.
413 The safe thing to do is exit assuming no optimization is
415 if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt
)) == *use_stmt
)
418 /* Skip past this PHI and loop again in case we had a PHI
420 single_imm_use (PHI_RESULT (*use_stmt
), use_p
, use_stmt
);
427 /* Given a DECL, return its AGGREGATE_VARDECL_D entry. If no entry is
428 found and INSERT is TRUE, add a new entry. */
430 static struct aggregate_vardecl_d
*
431 get_aggregate_vardecl (tree decl
, struct dse_global_data
*dse_gd
, bool insert
)
433 struct aggregate_vardecl_d av
, *av_p
;
437 slot
= htab_find_slot (dse_gd
->aggregate_vardecl
, &av
, insert
? INSERT
: NO_INSERT
);
440 /* Not found, and we don't want to insert. */
444 /* Create new entry. */
447 av_p
= XNEW (struct aggregate_vardecl_d
);
450 /* Record how many parts the whole has. */
451 if (TREE_CODE (TREE_TYPE (decl
)) == COMPLEX_TYPE
)
453 else if (TREE_CODE (TREE_TYPE (decl
)) == RECORD_TYPE
)
457 /* Count the number of fields. */
458 fields
= TYPE_FIELDS (TREE_TYPE (decl
));
463 fields
= TREE_CHAIN (fields
);
470 av_p
->parts_set
= sbitmap_alloc (HOST_BITS_PER_LONG
);
471 sbitmap_zero (av_p
->parts_set
);
475 av_p
= (struct aggregate_vardecl_d
*) *slot
;
481 /* If STMT is a partial store into an aggregate, record which part got set. */
484 dse_record_partial_aggregate_store (tree stmt
, struct dse_global_data
*dse_gd
)
488 struct aggregate_vardecl_d
*av_p
;
491 gcc_assert (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
493 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
494 code
= TREE_CODE (lhs
);
495 if (code
!= IMAGPART_EXPR
496 && code
!= REALPART_EXPR
497 && code
!= COMPONENT_REF
)
499 decl
= TREE_OPERAND (lhs
, 0);
500 /* Early bail on things like nested COMPONENT_REFs. */
501 if (TREE_CODE (decl
) != VAR_DECL
)
503 /* Early bail on unions. */
504 if (code
== COMPONENT_REF
505 && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs
, 0))) != RECORD_TYPE
)
508 av_p
= get_aggregate_vardecl (decl
, dse_gd
, /*insert=*/false);
509 /* Run away, this isn't an aggregate we care about. */
510 if (!av_p
|| av_p
->ignore
)
523 tree orig_field
, fields
;
524 tree record_type
= TREE_TYPE (TREE_OPERAND (lhs
, 0));
526 /* Get FIELD_DECL. */
527 orig_field
= TREE_OPERAND (lhs
, 1);
529 /* FIXME: Eeech, do this more efficiently. Perhaps
530 calculate bit/byte offsets. */
532 fields
= TYPE_FIELDS (record_type
);
536 if (fields
== orig_field
)
538 fields
= TREE_CHAIN (fields
);
540 gcc_assert (part
>= 0);
547 /* Record which part was set. */
548 SET_BIT (av_p
->parts_set
, part
);
552 /* Return TRUE if all parts in an AGGREGATE_VARDECL have been set. */
555 dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d
*av_p
)
558 sbitmap_iterator sbi
;
561 /* Count the number of partial stores (bits set). */
562 EXECUTE_IF_SET_IN_SBITMAP (av_p
->parts_set
, 0, i
, sbi
)
564 return ((unsigned) nbits_set
== av_p
->nparts
);
568 /* Return TRUE if STMT is a store into a whole aggregate whose parts we
569 have already seen and recorded. */
572 dse_partial_kill_p (tree stmt
, struct dse_global_data
*dse_gd
)
575 struct aggregate_vardecl_d
*av_p
;
577 /* Make sure this is a store into the whole. */
578 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
582 decl
= GIMPLE_STMT_OPERAND (stmt
, 0);
583 code
= TREE_CODE (TREE_TYPE (decl
));
585 if (code
!= COMPLEX_TYPE
&& code
!= RECORD_TYPE
)
588 if (TREE_CODE (decl
) != VAR_DECL
)
594 av_p
= get_aggregate_vardecl (decl
, dse_gd
, /*insert=*/false);
595 gcc_assert (av_p
!= NULL
);
597 return dse_whole_aggregate_clobbered_p (av_p
);
601 /* Attempt to eliminate dead stores in the statement referenced by BSI.
603 A dead store is a store into a memory location which will later be
604 overwritten by another store without any intervening loads. In this
605 case the earlier store can be deleted.
607 In our SSA + virtual operand world we use immediate uses of virtual
608 operands to detect dead stores. If a store's virtual definition
609 is used precisely once by a later store to the same location which
610 post dominates the first store, then the first store is dead. */
613 dse_optimize_stmt (struct dom_walk_data
*walk_data
,
614 basic_block bb ATTRIBUTE_UNUSED
,
615 block_stmt_iterator bsi
)
617 struct dse_block_local_data
*bd
618 = (struct dse_block_local_data
*)
619 VEC_last (void_p
, walk_data
->block_data_stack
);
620 struct dse_global_data
*dse_gd
621 = (struct dse_global_data
*) walk_data
->global_data
;
622 tree stmt
= bsi_stmt (bsi
);
623 stmt_ann_t ann
= stmt_ann (stmt
);
625 /* If this statement has no virtual defs, then there is nothing
627 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
))
630 /* We know we have virtual definitions. If this is a GIMPLE_MODIFY_STMT
631 that's not also a function call, then record it into our table. */
632 if (get_call_expr_in (stmt
))
635 if (ann
->has_volatile_ops
)
638 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
640 use_operand_p first_use_p
= NULL_USE_OPERAND_P
;
641 use_operand_p use_p
= NULL
;
644 if (!dse_possible_dead_store_p (stmt
, &first_use_p
, &use_p
, &use_stmt
,
648 /* If this is a partial store into an aggregate, record it. */
649 dse_record_partial_aggregate_store (stmt
, dse_gd
);
651 if (use_p
!= NULL_USE_OPERAND_P
652 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use_stmt
))
653 && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt
, 0),
654 GIMPLE_STMT_OPERAND (use_stmt
, 0), 0)
655 && !dse_partial_kill_p (stmt
, dse_gd
))
656 && memory_address_same (stmt
, use_stmt
))
658 /* If we have precisely one immediate use at this point, but
659 the stores are not to the same memory location then walk the
660 virtual def-use chain to get the stmt which stores to that same
662 if (get_use_of_stmt_lhs (stmt
, &first_use_p
, &use_p
, &use_stmt
) ==
665 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
670 /* If we have precisely one immediate use at this point and the
671 stores are to the same memory location or there is a chain of
672 virtual uses from stmt and the stmt which stores to that same
673 memory location, then we may have found redundant store. */
674 if (use_p
!= NULL_USE_OPERAND_P
675 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use_stmt
))
676 && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt
, 0),
677 GIMPLE_STMT_OPERAND (use_stmt
, 0), 0)
678 || dse_partial_kill_p (stmt
, dse_gd
))
679 && memory_address_same (stmt
, use_stmt
))
686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
688 fprintf (dump_file
, " Deleted dead store '");
689 print_generic_expr (dump_file
, bsi_stmt (bsi
), dump_flags
);
690 fprintf (dump_file
, "'\n");
693 /* Then we need to fix the operand of the consuming stmt. */
694 stmt_lhs
= USE_FROM_PTR (first_use_p
);
695 FOR_EACH_SSA_VDEF_OPERAND (var1
, vv
, stmt
, op_iter
)
699 single_imm_use (DEF_FROM_PTR (var1
), &use_p
, &temp
);
700 gcc_assert (VUSE_VECT_NUM_ELEM (*vv
) == 1);
701 usevar
= VUSE_ELEMENT_VAR (*vv
, 0);
702 SET_USE (use_p
, usevar
);
704 /* Make sure we propagate the ABNORMAL bit setting. */
705 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs
))
706 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar
) = 1;
709 /* Remove the dead store. */
710 bsi_remove (&bsi
, true);
712 /* And release any SSA_NAMEs set in this statement back to the
717 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
721 /* Record that we have seen the PHIs at the start of BB which correspond
722 to virtual operands. */
724 dse_record_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
726 struct dse_block_local_data
*bd
727 = (struct dse_block_local_data
*)
728 VEC_last (void_p
, walk_data
->block_data_stack
);
729 struct dse_global_data
*dse_gd
730 = (struct dse_global_data
*) walk_data
->global_data
;
733 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
734 if (!is_gimple_reg (PHI_RESULT (phi
)))
735 record_voperand_set (dse_gd
->stores
,
741 dse_finalize_block (struct dom_walk_data
*walk_data
,
742 basic_block bb ATTRIBUTE_UNUSED
)
744 struct dse_block_local_data
*bd
745 = (struct dse_block_local_data
*)
746 VEC_last (void_p
, walk_data
->block_data_stack
);
747 struct dse_global_data
*dse_gd
748 = (struct dse_global_data
*) walk_data
->global_data
;
749 bitmap stores
= dse_gd
->stores
;
753 /* Unwind the stores noted in this basic block. */
755 EXECUTE_IF_SET_IN_BITMAP (bd
->stores
, 0, i
, bi
)
757 bitmap_clear_bit (stores
, i
);
762 /* Hashing and equality functions for AGGREGATE_VARDECL. */
765 aggregate_vardecl_hash (const void *p
)
767 return htab_hash_pointer
768 ((const void *)((const struct aggregate_vardecl_d
*)p
)->decl
);
772 aggregate_vardecl_eq (const void *p1
, const void *p2
)
774 return ((const struct aggregate_vardecl_d
*)p1
)->decl
775 == ((const struct aggregate_vardecl_d
*)p2
)->decl
;
779 /* Free memory allocated by one entry in AGGREGATE_VARDECL. */
782 aggregate_vardecl_free (void *p
)
784 struct aggregate_vardecl_d
*entry
= (struct aggregate_vardecl_d
*) p
;
785 sbitmap_free (entry
->parts_set
);
790 /* Return true if STMT is a store into an entire aggregate. */
793 aggregate_whole_store_p (tree stmt
)
795 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
797 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
798 enum tree_code code
= TREE_CODE (TREE_TYPE (lhs
));
800 if (code
== COMPLEX_TYPE
|| code
== RECORD_TYPE
)
807 /* Main entry point. */
812 struct dom_walk_data walk_data
;
813 struct dse_global_data dse_gd
;
816 dse_gd
.aggregate_vardecl
=
817 htab_create (37, aggregate_vardecl_hash
,
818 aggregate_vardecl_eq
, aggregate_vardecl_free
);
823 block_stmt_iterator bsi
;
825 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
827 tree stmt
= bsi_stmt (bsi
);
829 /* Record aggregates which have been stored into as a whole. */
830 if (aggregate_whole_store_p (stmt
))
832 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
833 if (TREE_CODE (lhs
) == VAR_DECL
)
835 struct aggregate_vardecl_d
*av_p
;
837 av_p
= get_aggregate_vardecl (lhs
, &dse_gd
, /*insert=*/true);
838 av_p
->ignore
= false;
840 /* Ignore aggregates with too many parts. */
841 if (av_p
->nparts
> HOST_BITS_PER_LONG
)
846 /* Create a UID for each statement in the function.
847 Ordering of the UIDs is not important for this pass. */
848 stmt_ann (stmt
)->uid
= max_stmt_uid
++;
852 /* We might consider making this a property of each pass so that it
853 can be [re]computed on an as-needed basis. Particularly since
854 this pass could be seen as an extension of DCE which needs post
856 calculate_dominance_info (CDI_POST_DOMINATORS
);
858 /* Dead store elimination is fundamentally a walk of the post-dominator
859 tree and a backwards walk of statements within each block. */
860 walk_data
.walk_stmts_backward
= true;
861 walk_data
.dom_direction
= CDI_POST_DOMINATORS
;
862 walk_data
.initialize_block_local_data
= dse_initialize_block_local_data
;
863 walk_data
.before_dom_children_before_stmts
= NULL
;
864 walk_data
.before_dom_children_walk_stmts
= dse_optimize_stmt
;
865 walk_data
.before_dom_children_after_stmts
= dse_record_phis
;
866 walk_data
.after_dom_children_before_stmts
= NULL
;
867 walk_data
.after_dom_children_walk_stmts
= NULL
;
868 walk_data
.after_dom_children_after_stmts
= dse_finalize_block
;
869 walk_data
.interesting_blocks
= NULL
;
871 walk_data
.block_local_data_size
= sizeof (struct dse_block_local_data
);
873 /* This is the main hash table for the dead store elimination pass. */
874 dse_gd
.stores
= BITMAP_ALLOC (NULL
);
876 walk_data
.global_data
= &dse_gd
;
878 /* Initialize the dominator walker. */
879 init_walk_dominator_tree (&walk_data
);
881 /* Recursively walk the dominator tree. */
882 walk_dominator_tree (&walk_data
, EXIT_BLOCK_PTR
);
884 /* Finalize the dominator walker. */
885 fini_walk_dominator_tree (&walk_data
);
887 /* Release unneeded data. */
888 BITMAP_FREE (dse_gd
.stores
);
889 htab_delete (dse_gd
.aggregate_vardecl
);
891 /* For now, just wipe the post-dominator information. */
892 free_dominance_info (CDI_POST_DOMINATORS
);
899 return flag_tree_dse
!= 0;
902 struct tree_opt_pass pass_dse
= {
905 tree_ssa_dse
, /* execute */
908 0, /* static_pass_number */
909 TV_TREE_DSE
, /* tv_id */
912 | PROP_alias
, /* properties_required */
913 0, /* properties_provided */
914 0, /* properties_destroyed */
915 0, /* todo_flags_start */
918 | TODO_verify_ssa
, /* todo_flags_finish */