1 /* Dead store elimination
2 Copyright (C) 2004, 2005, 2006 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 2, 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 COPYING. If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
23 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "tree-dump.h"
40 /* This file implements dead store elimination.
42 A dead store is a store into a memory location which will later be
43 overwritten by another store without any intervening loads. In this
44 case the earlier store can be deleted.
46 In our SSA + virtual operand world we use immediate uses of virtual
47 operands to detect dead stores. If a store's virtual definition
48 is used precisely once by a later store to the same location which
49 post dominates the first store, then the first store is dead.
51 The single use of the store's virtual definition ensures that
52 there are no intervening aliased loads and the requirement that
53 the second load post dominate the first ensures that if the earlier
54 store executes, then the later stores will execute before the function
57 It may help to think of this as first moving the earlier store to
58 the point immediately before the later store. Again, the single
59 use of the virtual definition and the post-dominance relationship
60 ensure that such movement would be safe. Clearly if there are
61 back to back stores, then the second is redundant.
63 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
64 may also help in understanding this code since it discusses the
65 relationship between dead store and redundant load elimination. In
66 fact, they are the same transformation applied to different views of
70 /* Given an aggregate, this records the parts of it which have been
72 struct aggregate_vardecl_d
77 /* Some aggregates are too big for us to handle or never get stored
78 to as a whole. If this field is TRUE, we don't care about this
82 /* Number of parts in the whole. */
85 /* A bitmap of parts of the aggregate that have been set. If part N
86 of an aggregate has been stored to, bit N should be on. */
90 struct dse_global_data
92 /* This is the global bitmap for store statements.
94 Each statement has a unique ID. When we encounter a store statement
95 that we want to record, set the bit corresponding to the statement's
96 unique ID in this bitmap. */
99 /* A hash table containing the parts of an aggregate which have been
101 htab_t aggregate_vardecl
;
104 /* We allocate a bitmap-per-block for stores which are encountered
105 during the scan of that block. This allows us to restore the
106 global bitmap of stores when we finish processing a block. */
107 struct dse_block_local_data
112 /* Basic blocks of the potentially dead store and the following
113 store, for memory_address_same. */
114 struct address_walk_data
116 basic_block store1_bb
, store2_bb
;
119 static bool gate_dse (void);
120 static unsigned int tree_ssa_dse (void);
121 static void dse_initialize_block_local_data (struct dom_walk_data
*,
124 static void dse_optimize_stmt (struct dom_walk_data
*,
126 block_stmt_iterator
);
127 static void dse_record_phis (struct dom_walk_data
*, basic_block
);
128 static void dse_finalize_block (struct dom_walk_data
*, basic_block
);
129 static void record_voperand_set (bitmap
, bitmap
*, unsigned int);
130 static void dse_record_partial_aggregate_store (tree
, struct dse_global_data
*);
132 static unsigned max_stmt_uid
; /* Maximal uid of a statement. Uids to phi
133 nodes are assigned using the versions of
134 ssa names they define. */
136 /* Returns uid of statement STMT. */
139 get_stmt_uid (tree stmt
)
141 if (TREE_CODE (stmt
) == PHI_NODE
)
142 return SSA_NAME_VERSION (PHI_RESULT (stmt
)) + max_stmt_uid
;
144 return stmt_ann (stmt
)->uid
;
147 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */
150 record_voperand_set (bitmap global
, bitmap
*local
, unsigned int uid
)
152 /* Lazily allocate the bitmap. Note that we do not get a notification
153 when the block local data structures die, so we allocate the local
154 bitmap backed by the GC system. */
156 *local
= BITMAP_GGC_ALLOC ();
158 /* Set the bit in the local and global bitmaps. */
159 bitmap_set_bit (*local
, uid
);
160 bitmap_set_bit (global
, uid
);
163 /* Initialize block local data structures. */
166 dse_initialize_block_local_data (struct dom_walk_data
*walk_data
,
167 basic_block bb ATTRIBUTE_UNUSED
,
170 struct dse_block_local_data
*bd
171 = (struct dse_block_local_data
*)
172 VEC_last (void_p
, walk_data
->block_data_stack
);
174 /* If we are given a recycled block local data structure, ensure any
175 bitmap associated with the block is cleared. */
179 bitmap_clear (bd
->stores
);
183 /* Helper function for memory_address_same via walk_tree. Returns
184 non-NULL if it finds an SSA_NAME which is part of the address,
185 such that the definition of the SSA_NAME post-dominates the store
186 we want to delete but not the store that we believe makes it
187 redundant. This indicates that the address may change between
191 memory_ssa_name_same (tree
*expr_p
, int *walk_subtrees ATTRIBUTE_UNUSED
,
194 struct address_walk_data
*walk_data
= (struct address_walk_data
*) data
;
199 if (TREE_CODE (expr
) != SSA_NAME
)
202 /* If we've found a default definition, then there's no problem. Both
203 stores will post-dominate it. And def_bb will be NULL. */
204 if (SSA_NAME_IS_DEFAULT_DEF (expr
))
207 def_stmt
= SSA_NAME_DEF_STMT (expr
);
208 def_bb
= bb_for_stmt (def_stmt
);
210 /* DEF_STMT must dominate both stores. So if it is in the same
211 basic block as one, it does not post-dominate that store. */
212 if (walk_data
->store1_bb
!= def_bb
213 && dominated_by_p (CDI_POST_DOMINATORS
, walk_data
->store1_bb
, def_bb
))
215 if (walk_data
->store2_bb
== def_bb
216 || !dominated_by_p (CDI_POST_DOMINATORS
, walk_data
->store2_bb
,
218 /* Return non-NULL to stop the walk. */
225 /* Return TRUE if the destination memory address in STORE1 and STORE2
226 might be modified after STORE1, before control reaches STORE2. */
229 memory_address_same (tree store1
, tree store2
)
231 struct address_walk_data walk_data
;
233 walk_data
.store1_bb
= bb_for_stmt (store1
);
234 walk_data
.store2_bb
= bb_for_stmt (store2
);
236 return (walk_tree (&GIMPLE_STMT_OPERAND (store1
, 0), memory_ssa_name_same
,
241 /* Return the use stmt for the lhs of STMT following the virtual
242 def-use chains. Returns the MODIFY_EXPR stmt which lhs is equal to
243 the lhs of STMT or NULL_TREE if no such stmt can be found. */
245 get_use_of_stmt_lhs (tree stmt
,
246 use_operand_p
* first_use_p
,
247 use_operand_p
* use_p
, tree
* use_stmt
)
252 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
255 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
257 /* The stmt must have a single VDEF. */
258 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_VDEF
);
259 if (def_p
== NULL_DEF_OPERAND_P
)
262 if (!has_single_use (DEF_FROM_PTR (def_p
)))
264 /* Get the immediate use of the def. */
265 single_imm_use (DEF_FROM_PTR (def_p
), use_p
, use_stmt
);
266 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
268 if (TREE_CODE (*use_stmt
) != GIMPLE_MODIFY_STMT
)
273 /* Look at the use stmt and see if it's LHS matches
274 stmt's lhs SSA_NAME. */
275 def_p
= SINGLE_SSA_DEF_OPERAND (*use_stmt
, SSA_OP_VDEF
);
276 if (def_p
== NULL_DEF_OPERAND_P
)
279 usevar
= GIMPLE_STMT_OPERAND (*use_stmt
, 0);
280 if (operand_equal_p (usevar
, lhs
, 0))
283 if (!has_single_use (DEF_FROM_PTR (def_p
)))
285 single_imm_use (DEF_FROM_PTR (def_p
), use_p
, use_stmt
);
286 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
287 if (TREE_CODE (*use_stmt
) != GIMPLE_MODIFY_STMT
)
295 /* A helper of dse_optimize_stmt.
296 Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
297 use, and that one use is another VDEF clobbering the first one.
299 Return TRUE if the above conditions are met, otherwise FALSE. */
302 dse_possible_dead_store_p (tree stmt
,
303 use_operand_p
*first_use_p
,
304 use_operand_p
*use_p
,
306 struct dse_global_data
*dse_gd
,
307 struct dse_block_local_data
*bd
)
313 tree defvar
= NULL_TREE
, temp
;
314 tree prev_defvar
= NULL_TREE
;
315 stmt_ann_t ann
= stmt_ann (stmt
);
317 /* We want to verify that each virtual definition in STMT has
318 precisely one use and that all the virtual definitions are
319 used by the same single statement. When complete, we
320 want USE_STMT to refer to the one statement which uses
321 all of the virtual definitions from STMT. */
323 FOR_EACH_SSA_VDEF_OPERAND (var1
, vv
, stmt
, op_iter
)
325 defvar
= DEF_FROM_PTR (var1
);
327 /* If this virtual def does not have precisely one use, then
328 we will not be able to eliminate STMT. */
329 if (!has_single_use (defvar
))
335 /* Get the one and only immediate use of DEFVAR. */
336 single_imm_use (defvar
, use_p
, &temp
);
337 gcc_assert (*use_p
!= NULL_USE_OPERAND_P
);
338 *first_use_p
= *use_p
;
340 /* In the case of memory partitions, we may get:
342 # MPT.764_162 = VDEF <MPT.764_161(D)>
344 # MPT.764_167 = VDEF <MPT.764_162>
347 So we must make sure we're talking about the same LHS.
349 if (TREE_CODE (temp
) == GIMPLE_MODIFY_STMT
)
351 tree base1
= get_base_address (GIMPLE_STMT_OPERAND (stmt
, 0));
352 tree base2
= get_base_address (GIMPLE_STMT_OPERAND (temp
, 0));
354 while (base1
&& INDIRECT_REF_P (base1
))
355 base1
= TREE_OPERAND (base1
, 0);
356 while (base2
&& INDIRECT_REF_P (base2
))
357 base2
= TREE_OPERAND (base2
, 0);
366 /* If the immediate use of DEF_VAR is not the same as the
367 previously find immediate uses, then we will not be able
368 to eliminate STMT. */
369 if (*use_stmt
== NULL
)
372 prev_defvar
= defvar
;
374 else if (temp
!= *use_stmt
)
376 /* The immediate use and the previously found immediate use
377 must be the same, except... if they're uses of different
378 parts of the whole. */
379 if (TREE_CODE (defvar
) == SSA_NAME
380 && TREE_CODE (SSA_NAME_VAR (defvar
)) == STRUCT_FIELD_TAG
381 && TREE_CODE (prev_defvar
) == SSA_NAME
382 && TREE_CODE (SSA_NAME_VAR (prev_defvar
)) == STRUCT_FIELD_TAG
383 && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar
))
384 == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar
))))
396 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
397 dse_record_partial_aggregate_store (stmt
, dse_gd
);
401 /* Skip through any PHI nodes we have already seen if the PHI
402 represents the only use of this store.
404 Note this does not handle the case where the store has
405 multiple VDEFs which all reach a set of PHI nodes in the same block. */
406 while (*use_p
!= NULL_USE_OPERAND_P
407 && TREE_CODE (*use_stmt
) == PHI_NODE
408 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (*use_stmt
)))
410 /* A PHI node can both define and use the same SSA_NAME if
411 the PHI is at the top of a loop and the PHI_RESULT is
412 a loop invariant and copies have not been fully propagated.
414 The safe thing to do is exit assuming no optimization is
416 if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt
)) == *use_stmt
)
419 /* Skip past this PHI and loop again in case we had a PHI
421 single_imm_use (PHI_RESULT (*use_stmt
), use_p
, use_stmt
);
428 /* Given a DECL, return its AGGREGATE_VARDECL_D entry. If no entry is
429 found and INSERT is TRUE, add a new entry. */
431 static struct aggregate_vardecl_d
*
432 get_aggregate_vardecl (tree decl
, struct dse_global_data
*dse_gd
, bool insert
)
434 struct aggregate_vardecl_d av
, *av_p
;
438 slot
= htab_find_slot (dse_gd
->aggregate_vardecl
, &av
, insert
? INSERT
: NO_INSERT
);
441 /* Not found, and we don't want to insert. */
445 /* Create new entry. */
448 av_p
= XNEW (struct aggregate_vardecl_d
);
451 /* Record how many parts the whole has. */
452 if (TREE_CODE (TREE_TYPE (decl
)) == COMPLEX_TYPE
)
454 else if (TREE_CODE (TREE_TYPE (decl
)) == RECORD_TYPE
)
458 /* Count the number of fields. */
459 fields
= TYPE_FIELDS (TREE_TYPE (decl
));
464 fields
= TREE_CHAIN (fields
);
471 av_p
->parts_set
= sbitmap_alloc (HOST_BITS_PER_LONG
);
472 sbitmap_zero (av_p
->parts_set
);
476 av_p
= (struct aggregate_vardecl_d
*) *slot
;
482 /* If STMT is a partial store into an aggregate, record which part got set. */
485 dse_record_partial_aggregate_store (tree stmt
, struct dse_global_data
*dse_gd
)
489 struct aggregate_vardecl_d
*av_p
;
492 gcc_assert (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
494 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
495 code
= TREE_CODE (lhs
);
496 if (code
!= IMAGPART_EXPR
497 && code
!= REALPART_EXPR
498 && code
!= COMPONENT_REF
)
500 decl
= TREE_OPERAND (lhs
, 0);
501 /* Early bail on things like nested COMPONENT_REFs. */
502 if (TREE_CODE (decl
) != VAR_DECL
)
504 /* Early bail on unions. */
505 if (code
== COMPONENT_REF
506 && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs
, 0))) != RECORD_TYPE
)
509 av_p
= get_aggregate_vardecl (decl
, dse_gd
, /*insert=*/false);
510 /* Run away, this isn't an aggregate we care about. */
511 if (!av_p
|| av_p
->ignore
)
524 tree orig_field
, fields
;
525 tree record_type
= TREE_TYPE (TREE_OPERAND (lhs
, 0));
527 /* Get FIELD_DECL. */
528 orig_field
= TREE_OPERAND (lhs
, 1);
530 /* FIXME: Eeech, do this more efficiently. Perhaps
531 calculate bit/byte offsets. */
533 fields
= TYPE_FIELDS (record_type
);
537 if (fields
== orig_field
)
539 fields
= TREE_CHAIN (fields
);
541 gcc_assert (part
>= 0);
548 /* Record which part was set. */
549 SET_BIT (av_p
->parts_set
, part
);
553 /* Return TRUE if all parts in an AGGREGATE_VARDECL have been set. */
556 dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d
*av_p
)
559 sbitmap_iterator sbi
;
562 /* Count the number of partial stores (bits set). */
563 EXECUTE_IF_SET_IN_SBITMAP (av_p
->parts_set
, 0, i
, sbi
)
565 return ((unsigned) nbits_set
== av_p
->nparts
);
569 /* Return TRUE if STMT is a store into a whole aggregate whose parts we
570 have already seen and recorded. */
573 dse_partial_kill_p (tree stmt
, struct dse_global_data
*dse_gd
)
576 struct aggregate_vardecl_d
*av_p
;
578 /* Make sure this is a store into the whole. */
579 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
583 decl
= GIMPLE_STMT_OPERAND (stmt
, 0);
584 code
= TREE_CODE (TREE_TYPE (decl
));
586 if (code
!= COMPLEX_TYPE
&& code
!= RECORD_TYPE
)
589 if (TREE_CODE (decl
) != VAR_DECL
)
595 av_p
= get_aggregate_vardecl (decl
, dse_gd
, /*insert=*/false);
596 gcc_assert (av_p
!= NULL
);
598 return dse_whole_aggregate_clobbered_p (av_p
);
602 /* Attempt to eliminate dead stores in the statement referenced by BSI.
604 A dead store is a store into a memory location which will later be
605 overwritten by another store without any intervening loads. In this
606 case the earlier store can be deleted.
608 In our SSA + virtual operand world we use immediate uses of virtual
609 operands to detect dead stores. If a store's virtual definition
610 is used precisely once by a later store to the same location which
611 post dominates the first store, then the first store is dead. */
614 dse_optimize_stmt (struct dom_walk_data
*walk_data
,
615 basic_block bb ATTRIBUTE_UNUSED
,
616 block_stmt_iterator bsi
)
618 struct dse_block_local_data
*bd
619 = (struct dse_block_local_data
*)
620 VEC_last (void_p
, walk_data
->block_data_stack
);
621 struct dse_global_data
*dse_gd
622 = (struct dse_global_data
*) walk_data
->global_data
;
623 tree stmt
= bsi_stmt (bsi
);
624 stmt_ann_t ann
= stmt_ann (stmt
);
626 /* If this statement has no virtual defs, then there is nothing
628 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
))
631 /* We know we have virtual definitions. If this is a GIMPLE_MODIFY_STMT
632 that's not also a function call, then record it into our table. */
633 if (get_call_expr_in (stmt
))
636 if (ann
->has_volatile_ops
)
639 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
641 use_operand_p first_use_p
= NULL_USE_OPERAND_P
;
642 use_operand_p use_p
= NULL
;
645 if (!dse_possible_dead_store_p (stmt
, &first_use_p
, &use_p
, &use_stmt
,
649 /* If this is a partial store into an aggregate, record it. */
650 dse_record_partial_aggregate_store (stmt
, dse_gd
);
652 if (use_p
!= NULL_USE_OPERAND_P
653 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use_stmt
))
654 && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt
, 0),
655 GIMPLE_STMT_OPERAND (use_stmt
, 0), 0)
656 && !dse_partial_kill_p (stmt
, dse_gd
))
657 && memory_address_same (stmt
, use_stmt
))
659 /* If we have precisely one immediate use at this point, but
660 the stores are not to the same memory location then walk the
661 virtual def-use chain to get the stmt which stores to that same
663 if (get_use_of_stmt_lhs (stmt
, &first_use_p
, &use_p
, &use_stmt
) ==
666 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
671 /* If we have precisely one immediate use at this point and the
672 stores are to the same memory location or there is a chain of
673 virtual uses from stmt and the stmt which stores to that same
674 memory location, then we may have found redundant store. */
675 if (use_p
!= NULL_USE_OPERAND_P
676 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use_stmt
))
677 && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt
, 0),
678 GIMPLE_STMT_OPERAND (use_stmt
, 0), 0)
679 || dse_partial_kill_p (stmt
, dse_gd
))
680 && memory_address_same (stmt
, use_stmt
))
687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
689 fprintf (dump_file
, " Deleted dead store '");
690 print_generic_expr (dump_file
, bsi_stmt (bsi
), dump_flags
);
691 fprintf (dump_file
, "'\n");
694 /* Then we need to fix the operand of the consuming stmt. */
695 stmt_lhs
= USE_FROM_PTR (first_use_p
);
696 FOR_EACH_SSA_VDEF_OPERAND (var1
, vv
, stmt
, op_iter
)
700 single_imm_use (DEF_FROM_PTR (var1
), &use_p
, &temp
);
701 gcc_assert (VUSE_VECT_NUM_ELEM (*vv
) == 1);
702 usevar
= VUSE_ELEMENT_VAR (*vv
, 0);
703 SET_USE (use_p
, usevar
);
705 /* Make sure we propagate the ABNORMAL bit setting. */
706 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs
))
707 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar
) = 1;
710 /* Remove the dead store. */
711 bsi_remove (&bsi
, true);
713 /* And release any SSA_NAMEs set in this statement back to the
718 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
722 /* Record that we have seen the PHIs at the start of BB which correspond
723 to virtual operands. */
725 dse_record_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
727 struct dse_block_local_data
*bd
728 = (struct dse_block_local_data
*)
729 VEC_last (void_p
, walk_data
->block_data_stack
);
730 struct dse_global_data
*dse_gd
731 = (struct dse_global_data
*) walk_data
->global_data
;
734 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
735 if (!is_gimple_reg (PHI_RESULT (phi
)))
736 record_voperand_set (dse_gd
->stores
,
742 dse_finalize_block (struct dom_walk_data
*walk_data
,
743 basic_block bb ATTRIBUTE_UNUSED
)
745 struct dse_block_local_data
*bd
746 = (struct dse_block_local_data
*)
747 VEC_last (void_p
, walk_data
->block_data_stack
);
748 struct dse_global_data
*dse_gd
749 = (struct dse_global_data
*) walk_data
->global_data
;
750 bitmap stores
= dse_gd
->stores
;
754 /* Unwind the stores noted in this basic block. */
756 EXECUTE_IF_SET_IN_BITMAP (bd
->stores
, 0, i
, bi
)
758 bitmap_clear_bit (stores
, i
);
763 /* Hashing and equality functions for AGGREGATE_VARDECL. */
766 aggregate_vardecl_hash (const void *p
)
768 return htab_hash_pointer
769 ((const void *)((const struct aggregate_vardecl_d
*)p
)->decl
);
773 aggregate_vardecl_eq (const void *p1
, const void *p2
)
775 return ((const struct aggregate_vardecl_d
*)p1
)->decl
776 == ((const struct aggregate_vardecl_d
*)p2
)->decl
;
780 /* Free memory allocated by one entry in AGGREGATE_VARDECL. */
783 aggregate_vardecl_free (void *p
)
785 struct aggregate_vardecl_d
*entry
= (struct aggregate_vardecl_d
*) p
;
786 sbitmap_free (entry
->parts_set
);
791 /* Return true if STMT is a store into an entire aggregate. */
794 aggregate_whole_store_p (tree stmt
)
796 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
798 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
799 enum tree_code code
= TREE_CODE (TREE_TYPE (lhs
));
801 if (code
== COMPLEX_TYPE
|| code
== RECORD_TYPE
)
808 /* Main entry point. */
813 struct dom_walk_data walk_data
;
814 struct dse_global_data dse_gd
;
817 dse_gd
.aggregate_vardecl
=
818 htab_create (37, aggregate_vardecl_hash
,
819 aggregate_vardecl_eq
, aggregate_vardecl_free
);
824 block_stmt_iterator bsi
;
826 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
828 tree stmt
= bsi_stmt (bsi
);
830 /* Record aggregates which have been stored into as a whole. */
831 if (aggregate_whole_store_p (stmt
))
833 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
834 if (TREE_CODE (lhs
) == VAR_DECL
)
836 struct aggregate_vardecl_d
*av_p
;
838 av_p
= get_aggregate_vardecl (lhs
, &dse_gd
, /*insert=*/true);
839 av_p
->ignore
= false;
841 /* Ignore aggregates with too many parts. */
842 if (av_p
->nparts
> HOST_BITS_PER_LONG
)
847 /* Create a UID for each statement in the function.
848 Ordering of the UIDs is not important for this pass. */
849 stmt_ann (stmt
)->uid
= max_stmt_uid
++;
853 /* We might consider making this a property of each pass so that it
854 can be [re]computed on an as-needed basis. Particularly since
855 this pass could be seen as an extension of DCE which needs post
857 calculate_dominance_info (CDI_POST_DOMINATORS
);
859 /* Dead store elimination is fundamentally a walk of the post-dominator
860 tree and a backwards walk of statements within each block. */
861 walk_data
.walk_stmts_backward
= true;
862 walk_data
.dom_direction
= CDI_POST_DOMINATORS
;
863 walk_data
.initialize_block_local_data
= dse_initialize_block_local_data
;
864 walk_data
.before_dom_children_before_stmts
= NULL
;
865 walk_data
.before_dom_children_walk_stmts
= dse_optimize_stmt
;
866 walk_data
.before_dom_children_after_stmts
= dse_record_phis
;
867 walk_data
.after_dom_children_before_stmts
= NULL
;
868 walk_data
.after_dom_children_walk_stmts
= NULL
;
869 walk_data
.after_dom_children_after_stmts
= dse_finalize_block
;
870 walk_data
.interesting_blocks
= NULL
;
872 walk_data
.block_local_data_size
= sizeof (struct dse_block_local_data
);
874 /* This is the main hash table for the dead store elimination pass. */
875 dse_gd
.stores
= BITMAP_ALLOC (NULL
);
877 walk_data
.global_data
= &dse_gd
;
879 /* Initialize the dominator walker. */
880 init_walk_dominator_tree (&walk_data
);
882 /* Recursively walk the dominator tree. */
883 walk_dominator_tree (&walk_data
, EXIT_BLOCK_PTR
);
885 /* Finalize the dominator walker. */
886 fini_walk_dominator_tree (&walk_data
);
888 /* Release unneeded data. */
889 BITMAP_FREE (dse_gd
.stores
);
890 htab_delete (dse_gd
.aggregate_vardecl
);
892 /* For now, just wipe the post-dominator information. */
893 free_dominance_info (CDI_POST_DOMINATORS
);
900 return flag_tree_dse
!= 0;
903 struct tree_opt_pass pass_dse
= {
906 tree_ssa_dse
, /* execute */
909 0, /* static_pass_number */
910 TV_TREE_DSE
, /* tv_id */
913 | PROP_alias
, /* properties_required */
914 0, /* properties_provided */
915 0, /* properties_destroyed */
916 0, /* todo_flags_start */
919 | TODO_verify_ssa
, /* todo_flags_finish */