1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
5 Contributed by Diego Novillo <dnovillo@redhat.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
31 /* These RTL headers are needed for basic-block.h. */
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
36 #include "diagnostic.h"
37 #include "langhooks.h"
38 #include "tree-inline.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
48 /* expr.h is needed for MOVE_RATIO. */
53 /* This object of this pass is to replace a non-addressable aggregate with a
54 set of independent variables. Most of the time, all of these variables
55 will be scalars. But a secondary objective is to break up larger
56 aggregates into smaller aggregates. In the process we may find that some
57 bits of the larger aggregate can be deleted as unreferenced.
59 This substitution is done globally. More localized substitutions would
60 be the purvey of a load-store motion pass.
62 The optimization proceeds in phases:
64 (1) Identify variables that have types that are candidates for
67 (2) Scan the function looking for the ways these variables are used.
68 In particular we're interested in the number of times a variable
69 (or member) is needed as a complete unit, and the number of times
70 a variable (or member) is copied.
72 (3) Based on the usage profile, instantiate substitution variables.
74 (4) Scan the function making replacements.
78 /* The set of todo flags to return from tree_sra. */
79 static unsigned int todoflags
;
81 /* The set of aggregate variables that are candidates for scalarization. */
82 static bitmap sra_candidates
;
84 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
85 beginning of the function. */
86 static bitmap needs_copy_in
;
88 /* Sets of bit pairs that cache type decomposition and instantiation. */
89 static bitmap sra_type_decomp_cache
;
90 static bitmap sra_type_inst_cache
;
92 /* One of these structures is created for each candidate aggregate and
93 each (accessed) member or group of members of such an aggregate. */
96 /* A tree of the elements. Used when we want to traverse everything. */
97 struct sra_elt
*parent
;
98 struct sra_elt
*groups
;
99 struct sra_elt
*children
;
100 struct sra_elt
*sibling
;
102 /* If this element is a root, then this is the VAR_DECL. If this is
103 a sub-element, this is some token used to identify the reference.
104 In the case of COMPONENT_REF, this is the FIELD_DECL. In the case
105 of an ARRAY_REF, this is the (constant) index. In the case of an
106 ARRAY_RANGE_REF, this is the (constant) RANGE_EXPR. In the case
107 of a complex number, this is a zero or one. */
110 /* The type of the element. */
113 /* A VAR_DECL, for any sub-element we've decided to replace. */
116 /* The number of times the element is referenced as a whole. I.e.
117 given "a.b.c", this would be incremented for C, but not for A or B. */
120 /* The number of times the element is copied to or from another
121 scalarizable element. */
122 unsigned int n_copies
;
124 /* True if TYPE is scalar. */
127 /* True if this element is a group of members of its parent. */
130 /* True if we saw something about this element that prevents scalarization,
131 such as non-constant indexing. */
132 bool cannot_scalarize
;
134 /* True if we've decided that structure-to-structure assignment
135 should happen via memcpy and not per-element. */
138 /* True if everything under this element has been marked TREE_NO_WARNING. */
141 /* A flag for use with/after random access traversals. */
144 /* True if there is BIT_FIELD_REF on the lhs with a vector. */
148 #define IS_ELEMENT_FOR_GROUP(ELEMENT) (TREE_CODE (ELEMENT) == RANGE_EXPR)
150 #define FOR_EACH_ACTUAL_CHILD(CHILD, ELT) \
151 for ((CHILD) = (ELT)->is_group \
152 ? next_child_for_group (NULL, (ELT)) \
155 (CHILD) = (ELT)->is_group \
156 ? next_child_for_group ((CHILD), (ELT)) \
159 /* Helper function for above macro. Return next child in group. */
160 static struct sra_elt
*
161 next_child_for_group (struct sra_elt
*child
, struct sra_elt
*group
)
163 gcc_assert (group
->is_group
);
165 /* Find the next child in the parent. */
167 child
= child
->sibling
;
169 child
= group
->parent
->children
;
171 /* Skip siblings that do not belong to the group. */
174 tree g_elt
= group
->element
;
175 if (TREE_CODE (g_elt
) == RANGE_EXPR
)
177 if (!tree_int_cst_lt (child
->element
, TREE_OPERAND (g_elt
, 0))
178 && !tree_int_cst_lt (TREE_OPERAND (g_elt
, 1), child
->element
))
184 child
= child
->sibling
;
190 /* Random access to the child of a parent is performed by hashing.
191 This prevents quadratic behavior, and allows SRA to function
192 reasonably on larger records. */
193 static htab_t sra_map
;
195 /* All structures are allocated out of the following obstack. */
196 static struct obstack sra_obstack
;
198 /* Debugging functions. */
199 static void dump_sra_elt_name (FILE *, struct sra_elt
*);
200 extern void debug_sra_elt_name (struct sra_elt
*);
202 /* Forward declarations. */
203 static tree
generate_element_ref (struct sra_elt
*);
205 /* Return true if DECL is an SRA candidate. */
208 is_sra_candidate_decl (tree decl
)
210 return DECL_P (decl
) && bitmap_bit_p (sra_candidates
, DECL_UID (decl
));
213 /* Return true if TYPE is a scalar type. */
216 is_sra_scalar_type (tree type
)
218 enum tree_code code
= TREE_CODE (type
);
219 return (code
== INTEGER_TYPE
|| code
== REAL_TYPE
|| code
== VECTOR_TYPE
220 || code
== ENUMERAL_TYPE
|| code
== BOOLEAN_TYPE
221 || code
== POINTER_TYPE
|| code
== OFFSET_TYPE
222 || code
== REFERENCE_TYPE
);
225 /* Return true if TYPE can be decomposed into a set of independent variables.
227 Note that this doesn't imply that all elements of TYPE can be
228 instantiated, just that if we decide to break up the type into
229 separate pieces that it can be done. */
232 sra_type_can_be_decomposed_p (tree type
)
234 unsigned int cache
= TYPE_UID (TYPE_MAIN_VARIANT (type
)) * 2;
237 /* Avoid searching the same type twice. */
238 if (bitmap_bit_p (sra_type_decomp_cache
, cache
+0))
240 if (bitmap_bit_p (sra_type_decomp_cache
, cache
+1))
243 /* The type must have a definite nonzero size. */
244 if (TYPE_SIZE (type
) == NULL
|| TREE_CODE (TYPE_SIZE (type
)) != INTEGER_CST
245 || integer_zerop (TYPE_SIZE (type
)))
248 /* The type must be a non-union aggregate. */
249 switch (TREE_CODE (type
))
253 bool saw_one_field
= false;
255 for (t
= TYPE_FIELDS (type
); t
; t
= TREE_CHAIN (t
))
256 if (TREE_CODE (t
) == FIELD_DECL
)
258 /* Reject incorrectly represented bit fields. */
259 if (DECL_BIT_FIELD (t
)
260 && (tree_low_cst (DECL_SIZE (t
), 1)
261 != TYPE_PRECISION (TREE_TYPE (t
))))
264 saw_one_field
= true;
267 /* Record types must have at least one field. */
274 /* Array types must have a fixed lower and upper bound. */
275 t
= TYPE_DOMAIN (type
);
278 if (TYPE_MIN_VALUE (t
) == NULL
|| !TREE_CONSTANT (TYPE_MIN_VALUE (t
)))
280 if (TYPE_MAX_VALUE (t
) == NULL
|| !TREE_CONSTANT (TYPE_MAX_VALUE (t
)))
291 bitmap_set_bit (sra_type_decomp_cache
, cache
+0);
295 bitmap_set_bit (sra_type_decomp_cache
, cache
+1);
299 /* Return true if DECL can be decomposed into a set of independent
300 (though not necessarily scalar) variables. */
303 decl_can_be_decomposed_p (tree var
)
305 /* Early out for scalars. */
306 if (is_sra_scalar_type (TREE_TYPE (var
)))
309 /* The variable must not be aliased. */
310 if (!is_gimple_non_addressable (var
))
312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
314 fprintf (dump_file
, "Cannot scalarize variable ");
315 print_generic_expr (dump_file
, var
, dump_flags
);
316 fprintf (dump_file
, " because it must live in memory\n");
321 /* The variable must not be volatile. */
322 if (TREE_THIS_VOLATILE (var
))
324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
326 fprintf (dump_file
, "Cannot scalarize variable ");
327 print_generic_expr (dump_file
, var
, dump_flags
);
328 fprintf (dump_file
, " because it is declared volatile\n");
333 /* We must be able to decompose the variable's type. */
334 if (!sra_type_can_be_decomposed_p (TREE_TYPE (var
)))
336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
338 fprintf (dump_file
, "Cannot scalarize variable ");
339 print_generic_expr (dump_file
, var
, dump_flags
);
340 fprintf (dump_file
, " because its type cannot be decomposed\n");
348 /* Return true if TYPE can be *completely* decomposed into scalars. */
351 type_can_instantiate_all_elements (tree type
)
353 if (is_sra_scalar_type (type
))
355 if (!sra_type_can_be_decomposed_p (type
))
358 switch (TREE_CODE (type
))
362 unsigned int cache
= TYPE_UID (TYPE_MAIN_VARIANT (type
)) * 2;
365 if (bitmap_bit_p (sra_type_inst_cache
, cache
+0))
367 if (bitmap_bit_p (sra_type_inst_cache
, cache
+1))
370 for (f
= TYPE_FIELDS (type
); f
; f
= TREE_CHAIN (f
))
371 if (TREE_CODE (f
) == FIELD_DECL
)
373 if (!type_can_instantiate_all_elements (TREE_TYPE (f
)))
375 bitmap_set_bit (sra_type_inst_cache
, cache
+1);
380 bitmap_set_bit (sra_type_inst_cache
, cache
+0);
385 return type_can_instantiate_all_elements (TREE_TYPE (type
));
395 /* Test whether ELT or some sub-element cannot be scalarized. */
398 can_completely_scalarize_p (struct sra_elt
*elt
)
402 if (elt
->cannot_scalarize
)
405 for (c
= elt
->children
; c
; c
= c
->sibling
)
406 if (!can_completely_scalarize_p (c
))
409 for (c
= elt
->groups
; c
; c
= c
->sibling
)
410 if (!can_completely_scalarize_p (c
))
417 /* A simplified tree hashing algorithm that only handles the types of
418 trees we expect to find in sra_elt->element. */
421 sra_hash_tree (tree t
)
425 switch (TREE_CODE (t
))
434 h
= TREE_INT_CST_LOW (t
) ^ TREE_INT_CST_HIGH (t
);
438 h
= iterative_hash_expr (TREE_OPERAND (t
, 0), 0);
439 h
= iterative_hash_expr (TREE_OPERAND (t
, 1), h
);
443 /* We can have types that are compatible, but have different member
444 lists, so we can't hash fields by ID. Use offsets instead. */
445 h
= iterative_hash_expr (DECL_FIELD_OFFSET (t
), 0);
446 h
= iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t
), h
);
456 /* Hash function for type SRA_PAIR. */
459 sra_elt_hash (const void *x
)
461 const struct sra_elt
*e
= x
;
462 const struct sra_elt
*p
;
465 h
= sra_hash_tree (e
->element
);
467 /* Take into account everything back up the chain. Given that chain
468 lengths are rarely very long, this should be acceptable. If we
469 truly identify this as a performance problem, it should work to
470 hash the pointer value "e->parent". */
471 for (p
= e
->parent
; p
; p
= p
->parent
)
472 h
= (h
* 65521) ^ sra_hash_tree (p
->element
);
477 /* Equality function for type SRA_PAIR. */
480 sra_elt_eq (const void *x
, const void *y
)
482 const struct sra_elt
*a
= x
;
483 const struct sra_elt
*b
= y
;
486 if (a
->parent
!= b
->parent
)
494 if (TREE_CODE (ae
) != TREE_CODE (be
))
497 switch (TREE_CODE (ae
))
502 /* These are all pointer unique. */
506 /* Integers are not pointer unique, so compare their values. */
507 return tree_int_cst_equal (ae
, be
);
511 tree_int_cst_equal (TREE_OPERAND (ae
, 0), TREE_OPERAND (be
, 0))
512 && tree_int_cst_equal (TREE_OPERAND (ae
, 1), TREE_OPERAND (be
, 1));
515 /* Fields are unique within a record, but not between
516 compatible records. */
517 if (DECL_FIELD_CONTEXT (ae
) == DECL_FIELD_CONTEXT (be
))
519 return fields_compatible_p (ae
, be
);
526 /* Create or return the SRA_ELT structure for CHILD in PARENT. PARENT
527 may be null, in which case CHILD must be a DECL. */
529 static struct sra_elt
*
530 lookup_element (struct sra_elt
*parent
, tree child
, tree type
,
531 enum insert_option insert
)
533 struct sra_elt dummy
;
534 struct sra_elt
**slot
;
538 dummy
.parent
= parent
->is_group
? parent
->parent
: parent
;
541 dummy
.element
= child
;
543 slot
= (struct sra_elt
**) htab_find_slot (sra_map
, &dummy
, insert
);
544 if (!slot
&& insert
== NO_INSERT
)
548 if (!elt
&& insert
== INSERT
)
550 *slot
= elt
= obstack_alloc (&sra_obstack
, sizeof (*elt
));
551 memset (elt
, 0, sizeof (*elt
));
553 elt
->parent
= parent
;
554 elt
->element
= child
;
556 elt
->is_scalar
= is_sra_scalar_type (type
);
560 if (IS_ELEMENT_FOR_GROUP (elt
->element
))
562 elt
->is_group
= true;
563 elt
->sibling
= parent
->groups
;
564 parent
->groups
= elt
;
568 elt
->sibling
= parent
->children
;
569 parent
->children
= elt
;
573 /* If this is a parameter, then if we want to scalarize, we have
574 one copy from the true function parameter. Count it now. */
575 if (TREE_CODE (child
) == PARM_DECL
)
578 bitmap_set_bit (needs_copy_in
, DECL_UID (child
));
585 /* Create or return the SRA_ELT structure for EXPR if the expression
586 refers to a scalarizable variable. */
588 static struct sra_elt
*
589 maybe_lookup_element_for_expr (tree expr
)
594 switch (TREE_CODE (expr
))
599 if (is_sra_candidate_decl (expr
))
600 return lookup_element (NULL
, expr
, TREE_TYPE (expr
), INSERT
);
604 /* We can't scalarize variable array indices. */
605 if (in_array_bounds_p (expr
))
606 child
= TREE_OPERAND (expr
, 1);
611 case ARRAY_RANGE_REF
:
612 /* We can't scalarize variable array indices. */
613 if (range_in_array_bounds_p (expr
))
615 tree domain
= TYPE_DOMAIN (TREE_TYPE (expr
));
616 child
= build2 (RANGE_EXPR
, integer_type_node
,
617 TYPE_MIN_VALUE (domain
), TYPE_MAX_VALUE (domain
));
624 /* Don't look through unions. */
625 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr
, 0))) != RECORD_TYPE
)
627 child
= TREE_OPERAND (expr
, 1);
631 child
= integer_zero_node
;
634 child
= integer_one_node
;
641 elt
= maybe_lookup_element_for_expr (TREE_OPERAND (expr
, 0));
643 return lookup_element (elt
, child
, TREE_TYPE (expr
), INSERT
);
648 /* Functions to walk just enough of the tree to see all scalarizable
649 references, and categorize them. */
651 /* A set of callbacks for phases 2 and 4. They'll be invoked for the
652 various kinds of references seen. In all cases, *BSI is an iterator
653 pointing to the statement being processed. */
656 /* Invoked when ELT is required as a unit. Note that ELT might refer to
657 a leaf node, in which case this is a simple scalar reference. *EXPR_P
658 points to the location of the expression. IS_OUTPUT is true if this
659 is a left-hand-side reference. USE_ALL is true if we saw something we
660 couldn't quite identify and had to force the use of the entire object. */
661 void (*use
) (struct sra_elt
*elt
, tree
*expr_p
,
662 block_stmt_iterator
*bsi
, bool is_output
, bool use_all
);
664 /* Invoked when we have a copy between two scalarizable references. */
665 void (*copy
) (struct sra_elt
*lhs_elt
, struct sra_elt
*rhs_elt
,
666 block_stmt_iterator
*bsi
);
668 /* Invoked when ELT is initialized from a constant. VALUE may be NULL,
669 in which case it should be treated as an empty CONSTRUCTOR. */
670 void (*init
) (struct sra_elt
*elt
, tree value
, block_stmt_iterator
*bsi
);
672 /* Invoked when we have a copy between one scalarizable reference ELT
673 and one non-scalarizable reference OTHER. IS_OUTPUT is true if ELT
674 is on the left-hand side. */
675 void (*ldst
) (struct sra_elt
*elt
, tree other
,
676 block_stmt_iterator
*bsi
, bool is_output
);
678 /* True during phase 2, false during phase 4. */
679 /* ??? This is a hack. */
683 #ifdef ENABLE_CHECKING
684 /* Invoked via walk_tree, if *TP contains a candidate decl, return it. */
687 sra_find_candidate_decl (tree
*tp
, int *walk_subtrees
,
688 void *data ATTRIBUTE_UNUSED
)
691 enum tree_code code
= TREE_CODE (t
);
693 if (code
== VAR_DECL
|| code
== PARM_DECL
|| code
== RESULT_DECL
)
696 if (is_sra_candidate_decl (t
))
706 /* Walk most expressions looking for a scalarizable aggregate.
707 If we find one, invoke FNS->USE. */
710 sra_walk_expr (tree
*expr_p
, block_stmt_iterator
*bsi
, bool is_output
,
711 const struct sra_walk_fns
*fns
)
715 bool disable_scalarization
= false;
716 bool use_all_p
= false;
718 /* We're looking to collect a reference expression between EXPR and INNER,
719 such that INNER is a scalarizable decl and all other nodes through EXPR
720 are references that we can scalarize. If we come across something that
721 we can't scalarize, we reset EXPR. This has the effect of making it
722 appear that we're referring to the larger expression as a whole. */
725 switch (TREE_CODE (inner
))
730 /* If there is a scalarizable decl at the bottom, then process it. */
731 if (is_sra_candidate_decl (inner
))
733 struct sra_elt
*elt
= maybe_lookup_element_for_expr (expr
);
734 if (disable_scalarization
)
735 elt
->cannot_scalarize
= true;
737 fns
->use (elt
, expr_p
, bsi
, is_output
, use_all_p
);
742 /* Non-constant index means any member may be accessed. Prevent the
743 expression from being scalarized. If we were to treat this as a
744 reference to the whole array, we can wind up with a single dynamic
745 index reference inside a loop being overridden by several constant
746 index references during loop setup. It's possible that this could
747 be avoided by using dynamic usage counts based on BB trip counts
748 (based on loop analysis or profiling), but that hardly seems worth
750 /* ??? Hack. Figure out how to push this into the scan routines
751 without duplicating too much code. */
752 if (!in_array_bounds_p (inner
))
754 disable_scalarization
= true;
757 /* ??? Are we assured that non-constant bounds and stride will have
758 the same value everywhere? I don't think Fortran will... */
759 if (TREE_OPERAND (inner
, 2) || TREE_OPERAND (inner
, 3))
761 inner
= TREE_OPERAND (inner
, 0);
764 case ARRAY_RANGE_REF
:
765 if (!range_in_array_bounds_p (inner
))
767 disable_scalarization
= true;
770 /* ??? See above non-constant bounds and stride . */
771 if (TREE_OPERAND (inner
, 2) || TREE_OPERAND (inner
, 3))
773 inner
= TREE_OPERAND (inner
, 0);
777 /* A reference to a union member constitutes a reference to the
779 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (inner
, 0))) != RECORD_TYPE
)
781 /* ??? See above re non-constant stride. */
782 if (TREE_OPERAND (inner
, 2))
784 inner
= TREE_OPERAND (inner
, 0);
789 inner
= TREE_OPERAND (inner
, 0);
793 /* A bit field reference to a specific vector is scalarized but for
794 ones for inputs need to be marked as used on the left hand size so
795 when we scalarize it, we can mark that variable as non renamable. */
796 if (is_output
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (inner
, 0))) == VECTOR_TYPE
)
798 struct sra_elt
*elt
= maybe_lookup_element_for_expr (TREE_OPERAND (inner
, 0));
799 elt
->is_vector_lhs
= true;
801 /* A bit field reference (access to *multiple* fields simultaneously)
802 is not currently scalarized. Consider this an access to the
803 complete outer element, to which walk_tree will bring us next. */
807 case VIEW_CONVERT_EXPR
:
809 /* Similarly, a view/nop explicitly wants to look at an object in a
810 type other than the one we've scalarized. */
814 /* This is a transparent wrapper. The entire inner expression really
819 expr_p
= &TREE_OPERAND (inner
, 0);
820 inner
= expr
= *expr_p
;
825 #ifdef ENABLE_CHECKING
826 /* Validate that we're not missing any references. */
827 gcc_assert (!walk_tree (&inner
, sra_find_candidate_decl
, NULL
, NULL
));
833 /* Walk a TREE_LIST of values looking for scalarizable aggregates.
834 If we find one, invoke FNS->USE. */
837 sra_walk_tree_list (tree list
, block_stmt_iterator
*bsi
, bool is_output
,
838 const struct sra_walk_fns
*fns
)
841 for (op
= list
; op
; op
= TREE_CHAIN (op
))
842 sra_walk_expr (&TREE_VALUE (op
), bsi
, is_output
, fns
);
845 /* Walk the arguments of a CALL_EXPR looking for scalarizable aggregates.
846 If we find one, invoke FNS->USE. */
849 sra_walk_call_expr (tree expr
, block_stmt_iterator
*bsi
,
850 const struct sra_walk_fns
*fns
)
852 sra_walk_tree_list (TREE_OPERAND (expr
, 1), bsi
, false, fns
);
855 /* Walk the inputs and outputs of an ASM_EXPR looking for scalarizable
856 aggregates. If we find one, invoke FNS->USE. */
859 sra_walk_asm_expr (tree expr
, block_stmt_iterator
*bsi
,
860 const struct sra_walk_fns
*fns
)
862 sra_walk_tree_list (ASM_INPUTS (expr
), bsi
, false, fns
);
863 sra_walk_tree_list (ASM_OUTPUTS (expr
), bsi
, true, fns
);
866 /* Walk a GIMPLE_MODIFY_STMT and categorize the assignment appropriately. */
869 sra_walk_gimple_modify_stmt (tree expr
, block_stmt_iterator
*bsi
,
870 const struct sra_walk_fns
*fns
)
872 struct sra_elt
*lhs_elt
, *rhs_elt
;
875 lhs
= GIMPLE_STMT_OPERAND (expr
, 0);
876 rhs
= GIMPLE_STMT_OPERAND (expr
, 1);
877 lhs_elt
= maybe_lookup_element_for_expr (lhs
);
878 rhs_elt
= maybe_lookup_element_for_expr (rhs
);
880 /* If both sides are scalarizable, this is a COPY operation. */
881 if (lhs_elt
&& rhs_elt
)
883 fns
->copy (lhs_elt
, rhs_elt
, bsi
);
887 /* If the RHS is scalarizable, handle it. There are only two cases. */
890 if (!rhs_elt
->is_scalar
)
891 fns
->ldst (rhs_elt
, lhs
, bsi
, false);
893 fns
->use (rhs_elt
, &GIMPLE_STMT_OPERAND (expr
, 1), bsi
, false, false);
896 /* If it isn't scalarizable, there may be scalarizable variables within, so
897 check for a call or else walk the RHS to see if we need to do any
898 copy-in operations. We need to do it before the LHS is scalarized so
899 that the statements get inserted in the proper place, before any
900 copy-out operations. */
903 tree call
= get_call_expr_in (rhs
);
905 sra_walk_call_expr (call
, bsi
, fns
);
907 sra_walk_expr (&GIMPLE_STMT_OPERAND (expr
, 1), bsi
, false, fns
);
910 /* Likewise, handle the LHS being scalarizable. We have cases similar
911 to those above, but also want to handle RHS being constant. */
914 /* If this is an assignment from a constant, or constructor, then
915 we have access to all of the elements individually. Invoke INIT. */
916 if (TREE_CODE (rhs
) == COMPLEX_EXPR
917 || TREE_CODE (rhs
) == COMPLEX_CST
918 || TREE_CODE (rhs
) == CONSTRUCTOR
)
919 fns
->init (lhs_elt
, rhs
, bsi
);
921 /* If this is an assignment from read-only memory, treat this as if
922 we'd been passed the constructor directly. Invoke INIT. */
923 else if (TREE_CODE (rhs
) == VAR_DECL
925 && TREE_READONLY (rhs
)
926 && targetm
.binds_local_p (rhs
))
927 fns
->init (lhs_elt
, DECL_INITIAL (rhs
), bsi
);
929 /* If this is a copy from a non-scalarizable lvalue, invoke LDST.
930 The lvalue requirement prevents us from trying to directly scalarize
931 the result of a function call. Which would result in trying to call
932 the function multiple times, and other evil things. */
933 else if (!lhs_elt
->is_scalar
&& is_gimple_addressable (rhs
))
934 fns
->ldst (lhs_elt
, rhs
, bsi
, true);
936 /* Otherwise we're being used in some context that requires the
937 aggregate to be seen as a whole. Invoke USE. */
939 fns
->use (lhs_elt
, &GIMPLE_STMT_OPERAND (expr
, 0), bsi
, true, false);
942 /* Similarly to above, LHS_ELT being null only means that the LHS as a
943 whole is not a scalarizable reference. There may be occurrences of
944 scalarizable variables within, which implies a USE. */
946 sra_walk_expr (&GIMPLE_STMT_OPERAND (expr
, 0), bsi
, true, fns
);
949 /* Entry point to the walk functions. Search the entire function,
950 invoking the callbacks in FNS on each of the references to
951 scalarizable variables. */
954 sra_walk_function (const struct sra_walk_fns
*fns
)
957 block_stmt_iterator si
, ni
;
959 /* ??? Phase 4 could derive some benefit to walking the function in
960 dominator tree order. */
963 for (si
= bsi_start (bb
); !bsi_end_p (si
); si
= ni
)
968 stmt
= bsi_stmt (si
);
969 ann
= stmt_ann (stmt
);
974 /* If the statement has no virtual operands, then it doesn't
975 make any structure references that we care about. */
976 if (gimple_aliases_computed_p (cfun
)
977 && ZERO_SSA_OPERANDS (stmt
, (SSA_OP_VIRTUAL_DEFS
| SSA_OP_VUSE
)))
980 switch (TREE_CODE (stmt
))
983 /* If we have "return <retval>" then the return value is
984 already exposed for our pleasure. Walk it as a USE to
985 force all the components back in place for the return.
987 If we have an embedded assignment, then <retval> is of
988 a type that gets returned in registers in this ABI, and
989 we do not wish to extend their lifetimes. Treat this
990 as a USE of the variable on the RHS of this assignment. */
992 t
= TREE_OPERAND (stmt
, 0);
995 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
996 sra_walk_expr (&GIMPLE_STMT_OPERAND (t
, 1), &si
, false, fns
);
998 sra_walk_expr (&TREE_OPERAND (stmt
, 0), &si
, false, fns
);
1001 case GIMPLE_MODIFY_STMT
:
1002 sra_walk_gimple_modify_stmt (stmt
, &si
, fns
);
1005 sra_walk_call_expr (stmt
, &si
, fns
);
1008 sra_walk_asm_expr (stmt
, &si
, fns
);
1017 /* Phase One: Scan all referenced variables in the program looking for
1018 structures that could be decomposed. */
1021 find_candidates_for_sra (void)
1023 bool any_set
= false;
1025 referenced_var_iterator rvi
;
1027 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1029 if (decl_can_be_decomposed_p (var
))
1031 bitmap_set_bit (sra_candidates
, DECL_UID (var
));
1040 /* Phase Two: Scan all references to scalarizable variables. Count the
1041 number of times they are used or copied respectively. */
1043 /* Callbacks to fill in SRA_WALK_FNS. Everything but USE is
1044 considered a copy, because we can decompose the reference such that
1045 the sub-elements needn't be contiguous. */
1048 scan_use (struct sra_elt
*elt
, tree
*expr_p ATTRIBUTE_UNUSED
,
1049 block_stmt_iterator
*bsi ATTRIBUTE_UNUSED
,
1050 bool is_output ATTRIBUTE_UNUSED
, bool use_all ATTRIBUTE_UNUSED
)
1056 scan_copy (struct sra_elt
*lhs_elt
, struct sra_elt
*rhs_elt
,
1057 block_stmt_iterator
*bsi ATTRIBUTE_UNUSED
)
1059 lhs_elt
->n_copies
+= 1;
1060 rhs_elt
->n_copies
+= 1;
1064 scan_init (struct sra_elt
*lhs_elt
, tree rhs ATTRIBUTE_UNUSED
,
1065 block_stmt_iterator
*bsi ATTRIBUTE_UNUSED
)
1067 lhs_elt
->n_copies
+= 1;
1071 scan_ldst (struct sra_elt
*elt
, tree other ATTRIBUTE_UNUSED
,
1072 block_stmt_iterator
*bsi ATTRIBUTE_UNUSED
,
1073 bool is_output ATTRIBUTE_UNUSED
)
1078 /* Dump the values we collected during the scanning phase. */
1081 scan_dump (struct sra_elt
*elt
)
1085 dump_sra_elt_name (dump_file
, elt
);
1086 fprintf (dump_file
, ": n_uses=%u n_copies=%u\n", elt
->n_uses
, elt
->n_copies
);
1088 for (c
= elt
->children
; c
; c
= c
->sibling
)
1091 for (c
= elt
->groups
; c
; c
= c
->sibling
)
1095 /* Entry point to phase 2. Scan the entire function, building up
1096 scalarization data structures, recording copies and uses. */
1099 scan_function (void)
1101 static const struct sra_walk_fns fns
= {
1102 scan_use
, scan_copy
, scan_init
, scan_ldst
, true
1106 sra_walk_function (&fns
);
1108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1112 fputs ("\nScan results:\n", dump_file
);
1113 EXECUTE_IF_SET_IN_BITMAP (sra_candidates
, 0, i
, bi
)
1115 tree var
= referenced_var (i
);
1116 struct sra_elt
*elt
= lookup_element (NULL
, var
, NULL
, NO_INSERT
);
1120 fputc ('\n', dump_file
);
1124 /* Phase Three: Make decisions about which variables to scalarize, if any.
1125 All elements to be scalarized have replacement variables made for them. */
1127 /* A subroutine of build_element_name. Recursively build the element
1128 name on the obstack. */
1131 build_element_name_1 (struct sra_elt
*elt
)
1138 build_element_name_1 (elt
->parent
);
1139 obstack_1grow (&sra_obstack
, '$');
1141 if (TREE_CODE (elt
->parent
->type
) == COMPLEX_TYPE
)
1143 if (elt
->element
== integer_zero_node
)
1144 obstack_grow (&sra_obstack
, "real", 4);
1146 obstack_grow (&sra_obstack
, "imag", 4);
1152 if (TREE_CODE (t
) == INTEGER_CST
)
1154 /* ??? Eh. Don't bother doing double-wide printing. */
1155 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (t
));
1156 obstack_grow (&sra_obstack
, buffer
, strlen (buffer
));
1160 tree name
= DECL_NAME (t
);
1162 obstack_grow (&sra_obstack
, IDENTIFIER_POINTER (name
),
1163 IDENTIFIER_LENGTH (name
));
1166 sprintf (buffer
, "D%u", DECL_UID (t
));
1167 obstack_grow (&sra_obstack
, buffer
, strlen (buffer
));
1172 /* Construct a pretty variable name for an element's replacement variable.
1173 The name is built on the obstack. */
1176 build_element_name (struct sra_elt
*elt
)
1178 build_element_name_1 (elt
);
1179 obstack_1grow (&sra_obstack
, '\0');
1180 return XOBFINISH (&sra_obstack
, char *);
1183 /* Instantiate an element as an independent variable. */
1186 instantiate_element (struct sra_elt
*elt
)
1188 struct sra_elt
*base_elt
;
1191 for (base_elt
= elt
; base_elt
->parent
; base_elt
= base_elt
->parent
)
1193 base
= base_elt
->element
;
1195 elt
->replacement
= var
= make_rename_temp (elt
->type
, "SR");
1197 /* For vectors, if used on the left hand side with BIT_FIELD_REF,
1198 they are not a gimple register. */
1199 if (TREE_CODE (TREE_TYPE (var
)) == VECTOR_TYPE
&& elt
->is_vector_lhs
)
1200 DECL_GIMPLE_REG_P (var
) = 0;
1202 DECL_SOURCE_LOCATION (var
) = DECL_SOURCE_LOCATION (base
);
1203 DECL_ARTIFICIAL (var
) = 1;
1205 if (TREE_THIS_VOLATILE (elt
->type
))
1207 TREE_THIS_VOLATILE (var
) = 1;
1208 TREE_SIDE_EFFECTS (var
) = 1;
1211 if (DECL_NAME (base
) && !DECL_IGNORED_P (base
))
1213 char *pretty_name
= build_element_name (elt
);
1214 DECL_NAME (var
) = get_identifier (pretty_name
);
1215 obstack_free (&sra_obstack
, pretty_name
);
1217 SET_DECL_DEBUG_EXPR (var
, generate_element_ref (elt
));
1218 DECL_DEBUG_EXPR_IS_FROM (var
) = 1;
1220 DECL_IGNORED_P (var
) = 0;
1221 TREE_NO_WARNING (var
) = TREE_NO_WARNING (base
);
1225 DECL_IGNORED_P (var
) = 1;
1226 /* ??? We can't generate any warning that would be meaningful. */
1227 TREE_NO_WARNING (var
) = 1;
1232 fputs (" ", dump_file
);
1233 dump_sra_elt_name (dump_file
, elt
);
1234 fputs (" -> ", dump_file
);
1235 print_generic_expr (dump_file
, var
, dump_flags
);
1236 fputc ('\n', dump_file
);
1240 /* Make one pass across an element tree deciding whether or not it's
1241 profitable to instantiate individual leaf scalars.
1243 PARENT_USES and PARENT_COPIES are the sum of the N_USES and N_COPIES
1244 fields all the way up the tree. */
1247 decide_instantiation_1 (struct sra_elt
*elt
, unsigned int parent_uses
,
1248 unsigned int parent_copies
)
1250 if (dump_file
&& !elt
->parent
)
1252 fputs ("Initial instantiation for ", dump_file
);
1253 dump_sra_elt_name (dump_file
, elt
);
1254 fputc ('\n', dump_file
);
1257 if (elt
->cannot_scalarize
)
1262 /* The decision is simple: instantiate if we're used more frequently
1263 than the parent needs to be seen as a complete unit. */
1264 if (elt
->n_uses
+ elt
->n_copies
+ parent_copies
> parent_uses
)
1265 instantiate_element (elt
);
1269 struct sra_elt
*c
, *group
;
1270 unsigned int this_uses
= elt
->n_uses
+ parent_uses
;
1271 unsigned int this_copies
= elt
->n_copies
+ parent_copies
;
1273 /* Consider groups of sub-elements as weighing in favour of
1274 instantiation whatever their size. */
1275 for (group
= elt
->groups
; group
; group
= group
->sibling
)
1276 FOR_EACH_ACTUAL_CHILD (c
, group
)
1278 c
->n_uses
+= group
->n_uses
;
1279 c
->n_copies
+= group
->n_copies
;
1282 for (c
= elt
->children
; c
; c
= c
->sibling
)
1283 decide_instantiation_1 (c
, this_uses
, this_copies
);
1287 /* Compute the size and number of all instantiated elements below ELT.
1288 We will only care about this if the size of the complete structure
1289 fits in a HOST_WIDE_INT, so we don't have to worry about overflow. */
1292 sum_instantiated_sizes (struct sra_elt
*elt
, unsigned HOST_WIDE_INT
*sizep
)
1294 if (elt
->replacement
)
1296 *sizep
+= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt
->type
));
1302 unsigned int count
= 0;
1304 for (c
= elt
->children
; c
; c
= c
->sibling
)
1305 count
+= sum_instantiated_sizes (c
, sizep
);
1311 /* Instantiate fields in ELT->TYPE that are not currently present as
1314 static void instantiate_missing_elements (struct sra_elt
*elt
);
1317 instantiate_missing_elements_1 (struct sra_elt
*elt
, tree child
, tree type
)
1319 struct sra_elt
*sub
= lookup_element (elt
, child
, type
, INSERT
);
1322 if (sub
->replacement
== NULL
)
1323 instantiate_element (sub
);
1326 instantiate_missing_elements (sub
);
1330 instantiate_missing_elements (struct sra_elt
*elt
)
1332 tree type
= elt
->type
;
1334 switch (TREE_CODE (type
))
1339 for (f
= TYPE_FIELDS (type
); f
; f
= TREE_CHAIN (f
))
1340 if (TREE_CODE (f
) == FIELD_DECL
)
1341 instantiate_missing_elements_1 (elt
, f
, TREE_TYPE (f
));
1347 tree i
, max
, subtype
;
1349 i
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1350 max
= TYPE_MAX_VALUE (TYPE_DOMAIN (type
));
1351 subtype
= TREE_TYPE (type
);
1355 instantiate_missing_elements_1 (elt
, i
, subtype
);
1356 if (tree_int_cst_equal (i
, max
))
1358 i
= int_const_binop (PLUS_EXPR
, i
, integer_one_node
, true);
1365 type
= TREE_TYPE (type
);
1366 instantiate_missing_elements_1 (elt
, integer_zero_node
, type
);
1367 instantiate_missing_elements_1 (elt
, integer_one_node
, type
);
1375 /* Return true if there is only one non aggregate field in the record, TYPE.
1376 Return false otherwise. */
1379 single_scalar_field_in_record_p (tree type
)
1383 if (TREE_CODE (type
) != RECORD_TYPE
)
1386 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
1387 if (TREE_CODE (field
) == FIELD_DECL
)
1391 if (num_fields
== 2)
1394 if (AGGREGATE_TYPE_P (TREE_TYPE (field
)))
1401 /* Make one pass across an element tree deciding whether to perform block
1402 or element copies. If we decide on element copies, instantiate all
1403 elements. Return true if there are any instantiated sub-elements. */
1406 decide_block_copy (struct sra_elt
*elt
)
1411 /* We shouldn't be invoked on groups of sub-elements as they must
1412 behave like their parent as far as block copy is concerned. */
1413 gcc_assert (!elt
->is_group
);
1415 /* If scalarization is disabled, respect it. */
1416 if (elt
->cannot_scalarize
)
1418 elt
->use_block_copy
= 1;
1422 fputs ("Scalarization disabled for ", dump_file
);
1423 dump_sra_elt_name (dump_file
, elt
);
1424 fputc ('\n', dump_file
);
1427 /* Disable scalarization of sub-elements */
1428 for (c
= elt
->children
; c
; c
= c
->sibling
)
1430 c
->cannot_scalarize
= 1;
1431 decide_block_copy (c
);
1434 /* Groups behave like their parent. */
1435 for (c
= elt
->groups
; c
; c
= c
->sibling
)
1437 c
->cannot_scalarize
= 1;
1438 c
->use_block_copy
= 1;
1444 /* Don't decide if we've no uses. */
1445 if (elt
->n_uses
== 0 && elt
->n_copies
== 0)
1448 else if (!elt
->is_scalar
)
1450 tree size_tree
= TYPE_SIZE_UNIT (elt
->type
);
1451 bool use_block_copy
= true;
1453 /* Tradeoffs for COMPLEX types pretty much always make it better
1454 to go ahead and split the components. */
1455 if (TREE_CODE (elt
->type
) == COMPLEX_TYPE
)
1456 use_block_copy
= false;
1458 /* Don't bother trying to figure out the rest if the structure is
1459 so large we can't do easy arithmetic. This also forces block
1460 copies for variable sized structures. */
1461 else if (host_integerp (size_tree
, 1))
1463 unsigned HOST_WIDE_INT full_size
, inst_size
= 0;
1464 unsigned int max_size
, max_count
, inst_count
, full_count
;
1466 /* If the sra-max-structure-size parameter is 0, then the
1467 user has not overridden the parameter and we can choose a
1468 sensible default. */
1469 max_size
= SRA_MAX_STRUCTURE_SIZE
1470 ? SRA_MAX_STRUCTURE_SIZE
1471 : MOVE_RATIO
* UNITS_PER_WORD
;
1472 max_count
= SRA_MAX_STRUCTURE_COUNT
1473 ? SRA_MAX_STRUCTURE_COUNT
1476 full_size
= tree_low_cst (size_tree
, 1);
1477 full_count
= count_type_elements (elt
->type
, false);
1478 inst_count
= sum_instantiated_sizes (elt
, &inst_size
);
1480 /* If there is only one scalar field in the record, don't block copy. */
1481 if (single_scalar_field_in_record_p (elt
->type
))
1482 use_block_copy
= false;
1484 /* ??? What to do here. If there are two fields, and we've only
1485 instantiated one, then instantiating the other is clearly a win.
1486 If there are a large number of fields then the size of the copy
1487 is much more of a factor. */
1489 /* If the structure is small, and we've made copies, go ahead
1490 and instantiate, hoping that the copies will go away. */
1491 if (full_size
<= max_size
1492 && (full_count
- inst_count
) <= max_count
1493 && elt
->n_copies
> elt
->n_uses
)
1494 use_block_copy
= false;
1495 else if (inst_count
* 100 >= full_count
* SRA_FIELD_STRUCTURE_RATIO
1496 && inst_size
* 100 >= full_size
* SRA_FIELD_STRUCTURE_RATIO
)
1497 use_block_copy
= false;
1499 /* In order to avoid block copy, we have to be able to instantiate
1500 all elements of the type. See if this is possible. */
1502 && (!can_completely_scalarize_p (elt
)
1503 || !type_can_instantiate_all_elements (elt
->type
)))
1504 use_block_copy
= true;
1507 elt
->use_block_copy
= use_block_copy
;
1509 /* Groups behave like their parent. */
1510 for (c
= elt
->groups
; c
; c
= c
->sibling
)
1511 c
->use_block_copy
= use_block_copy
;
1515 fprintf (dump_file
, "Using %s for ",
1516 use_block_copy
? "block-copy" : "element-copy");
1517 dump_sra_elt_name (dump_file
, elt
);
1518 fputc ('\n', dump_file
);
1521 if (!use_block_copy
)
1523 instantiate_missing_elements (elt
);
1528 any_inst
= elt
->replacement
!= NULL
;
1530 for (c
= elt
->children
; c
; c
= c
->sibling
)
1531 any_inst
|= decide_block_copy (c
);
1536 /* Entry point to phase 3. Instantiate scalar replacement variables. */
1539 decide_instantiations (void)
1543 bitmap_head done_head
;
1546 /* We cannot clear bits from a bitmap we're iterating over,
1547 so save up all the bits to clear until the end. */
1548 bitmap_initialize (&done_head
, &bitmap_default_obstack
);
1549 cleared_any
= false;
1551 EXECUTE_IF_SET_IN_BITMAP (sra_candidates
, 0, i
, bi
)
1553 tree var
= referenced_var (i
);
1554 struct sra_elt
*elt
= lookup_element (NULL
, var
, NULL
, NO_INSERT
);
1557 decide_instantiation_1 (elt
, 0, 0);
1558 if (!decide_block_copy (elt
))
1563 bitmap_set_bit (&done_head
, i
);
1570 bitmap_and_compl_into (sra_candidates
, &done_head
);
1571 bitmap_and_compl_into (needs_copy_in
, &done_head
);
1573 bitmap_clear (&done_head
);
1575 if (!bitmap_empty_p (sra_candidates
))
1576 todoflags
|= TODO_update_smt_usage
;
1578 mark_set_for_renaming (sra_candidates
);
1581 fputc ('\n', dump_file
);
1585 /* Phase Four: Update the function to match the replacements created. */
1587 /* Mark all the variables in VDEF/VUSE operators for STMT for
1588 renaming. This becomes necessary when we modify all of a
1592 mark_all_v_defs_1 (tree stmt
)
1597 update_stmt_if_modified (stmt
);
1599 FOR_EACH_SSA_TREE_OPERAND (sym
, stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1601 if (TREE_CODE (sym
) == SSA_NAME
)
1602 sym
= SSA_NAME_VAR (sym
);
1603 mark_sym_for_renaming (sym
);
1608 /* Mark all the variables in virtual operands in all the statements in
1609 LIST for renaming. */
1612 mark_all_v_defs (tree list
)
1614 if (TREE_CODE (list
) != STATEMENT_LIST
)
1615 mark_all_v_defs_1 (list
);
1618 tree_stmt_iterator i
;
1619 for (i
= tsi_start (list
); !tsi_end_p (i
); tsi_next (&i
))
1620 mark_all_v_defs_1 (tsi_stmt (i
));
1625 /* Mark every replacement under ELT with TREE_NO_WARNING. */
1628 mark_no_warning (struct sra_elt
*elt
)
1630 if (!elt
->all_no_warning
)
1632 if (elt
->replacement
)
1633 TREE_NO_WARNING (elt
->replacement
) = 1;
1637 FOR_EACH_ACTUAL_CHILD (c
, elt
)
1638 mark_no_warning (c
);
1640 elt
->all_no_warning
= true;
1644 /* Build a single level component reference to ELT rooted at BASE. */
1647 generate_one_element_ref (struct sra_elt
*elt
, tree base
)
1649 switch (TREE_CODE (TREE_TYPE (base
)))
1653 tree field
= elt
->element
;
1655 /* Watch out for compatible records with differing field lists. */
1656 if (DECL_FIELD_CONTEXT (field
) != TYPE_MAIN_VARIANT (TREE_TYPE (base
)))
1657 field
= find_compatible_field (TREE_TYPE (base
), field
);
1659 return build3 (COMPONENT_REF
, elt
->type
, base
, field
, NULL
);
1663 todoflags
|= TODO_update_smt_usage
;
1664 if (TREE_CODE (elt
->element
) == RANGE_EXPR
)
1665 return build4 (ARRAY_RANGE_REF
, elt
->type
, base
,
1666 TREE_OPERAND (elt
->element
, 0), NULL
, NULL
);
1668 return build4 (ARRAY_REF
, elt
->type
, base
, elt
->element
, NULL
, NULL
);
1671 if (elt
->element
== integer_zero_node
)
1672 return build1 (REALPART_EXPR
, elt
->type
, base
);
1674 return build1 (IMAGPART_EXPR
, elt
->type
, base
);
1681 /* Build a full component reference to ELT rooted at its native variable. */
1684 generate_element_ref (struct sra_elt
*elt
)
1687 return generate_one_element_ref (elt
, generate_element_ref (elt
->parent
));
1689 return elt
->element
;
1692 /* Generate a set of assignment statements in *LIST_P to copy all
1693 instantiated elements under ELT to or from the equivalent structure
1694 rooted at EXPR. COPY_OUT controls the direction of the copy, with
1695 true meaning to copy out of EXPR into ELT. */
1698 generate_copy_inout (struct sra_elt
*elt
, bool copy_out
, tree expr
,
1704 if (!copy_out
&& TREE_CODE (expr
) == SSA_NAME
1705 && TREE_CODE (TREE_TYPE (expr
)) == COMPLEX_TYPE
)
1709 c
= lookup_element (elt
, integer_zero_node
, NULL
, NO_INSERT
);
1711 c
= lookup_element (elt
, integer_one_node
, NULL
, NO_INSERT
);
1714 t
= build2 (COMPLEX_EXPR
, elt
->type
, r
, i
);
1715 t
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, expr
, t
);
1716 SSA_NAME_DEF_STMT (expr
) = t
;
1717 append_to_statement_list (t
, list_p
);
1719 else if (elt
->replacement
)
1722 t
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, elt
->replacement
, expr
);
1724 t
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, expr
, elt
->replacement
);
1725 append_to_statement_list (t
, list_p
);
1729 FOR_EACH_ACTUAL_CHILD (c
, elt
)
1731 t
= generate_one_element_ref (c
, unshare_expr (expr
));
1732 generate_copy_inout (c
, copy_out
, t
, list_p
);
1737 /* Generate a set of assignment statements in *LIST_P to copy all instantiated
1738 elements under SRC to their counterparts under DST. There must be a 1-1
1739 correspondence of instantiated elements. */
1742 generate_element_copy (struct sra_elt
*dst
, struct sra_elt
*src
, tree
*list_p
)
1744 struct sra_elt
*dc
, *sc
;
1746 FOR_EACH_ACTUAL_CHILD (dc
, dst
)
1748 sc
= lookup_element (src
, dc
->element
, NULL
, NO_INSERT
);
1750 generate_element_copy (dc
, sc
, list_p
);
1753 if (dst
->replacement
)
1757 gcc_assert (src
->replacement
);
1759 t
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, dst
->replacement
,
1761 append_to_statement_list (t
, list_p
);
1765 /* Generate a set of assignment statements in *LIST_P to zero all instantiated
1766 elements under ELT. In addition, do not assign to elements that have been
1767 marked VISITED but do reset the visited flag; this allows easy coordination
1768 with generate_element_init. */
1771 generate_element_zero (struct sra_elt
*elt
, tree
*list_p
)
1777 elt
->visited
= false;
1781 FOR_EACH_ACTUAL_CHILD (c
, elt
)
1782 generate_element_zero (c
, list_p
);
1784 if (elt
->replacement
)
1788 gcc_assert (elt
->is_scalar
);
1789 t
= fold_convert (elt
->type
, integer_zero_node
);
1791 t
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, elt
->replacement
, t
);
1792 append_to_statement_list (t
, list_p
);
1796 /* Generate an assignment VAR = INIT, where INIT may need gimplification.
1797 Add the result to *LIST_P. */
1800 generate_one_element_init (tree var
, tree init
, tree
*list_p
)
1802 /* The replacement can be almost arbitrarily complex. Gimplify. */
1803 tree stmt
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, var
, init
);
1804 gimplify_and_add (stmt
, list_p
);
1807 /* Generate a set of assignment statements in *LIST_P to set all instantiated
1808 elements under ELT with the contents of the initializer INIT. In addition,
1809 mark all assigned elements VISITED; this allows easy coordination with
1810 generate_element_zero. Return false if we found a case we couldn't
1814 generate_element_init_1 (struct sra_elt
*elt
, tree init
, tree
*list_p
)
1817 enum tree_code init_code
;
1818 struct sra_elt
*sub
;
1820 unsigned HOST_WIDE_INT idx
;
1821 tree value
, purpose
;
1823 /* We can be passed DECL_INITIAL of a static variable. It might have a
1824 conversion, which we strip off here. */
1825 STRIP_USELESS_TYPE_CONVERSION (init
);
1826 init_code
= TREE_CODE (init
);
1830 if (elt
->replacement
)
1832 generate_one_element_init (elt
->replacement
, init
, list_p
);
1833 elt
->visited
= true;
1842 FOR_EACH_ACTUAL_CHILD (sub
, elt
)
1844 if (sub
->element
== integer_zero_node
)
1845 t
= (init_code
== COMPLEX_EXPR
1846 ? TREE_OPERAND (init
, 0) : TREE_REALPART (init
));
1848 t
= (init_code
== COMPLEX_EXPR
1849 ? TREE_OPERAND (init
, 1) : TREE_IMAGPART (init
));
1850 result
&= generate_element_init_1 (sub
, t
, list_p
);
1855 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init
), idx
, purpose
, value
)
1857 if (TREE_CODE (purpose
) == RANGE_EXPR
)
1859 tree lower
= TREE_OPERAND (purpose
, 0);
1860 tree upper
= TREE_OPERAND (purpose
, 1);
1864 sub
= lookup_element (elt
, lower
, NULL
, NO_INSERT
);
1866 result
&= generate_element_init_1 (sub
, value
, list_p
);
1867 if (tree_int_cst_equal (lower
, upper
))
1869 lower
= int_const_binop (PLUS_EXPR
, lower
,
1870 integer_one_node
, true);
1875 sub
= lookup_element (elt
, purpose
, NULL
, NO_INSERT
);
1877 result
&= generate_element_init_1 (sub
, value
, list_p
);
1883 elt
->visited
= true;
1890 /* A wrapper function for generate_element_init_1 that handles cleanup after
1894 generate_element_init (struct sra_elt
*elt
, tree init
, tree
*list_p
)
1898 push_gimplify_context ();
1899 ret
= generate_element_init_1 (elt
, init
, list_p
);
1900 pop_gimplify_context (NULL
);
1902 /* The replacement can expose previously unreferenced variables. */
1905 tree_stmt_iterator i
;
1907 for (i
= tsi_start (*list_p
); !tsi_end_p (i
); tsi_next (&i
))
1908 find_new_referenced_vars (tsi_stmt_ptr (i
));
1914 /* Insert STMT on all the outgoing edges out of BB. Note that if BB
1915 has more than one edge, STMT will be replicated for each edge. Also,
1916 abnormal edges will be ignored. */
1919 insert_edge_copies (tree stmt
, basic_block bb
)
1926 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1928 /* We don't need to insert copies on abnormal edges. The
1929 value of the scalar replacement is not guaranteed to
1930 be valid through an abnormal edge. */
1931 if (!(e
->flags
& EDGE_ABNORMAL
))
1935 bsi_insert_on_edge (e
, stmt
);
1939 bsi_insert_on_edge (e
, unsave_expr_now (stmt
));
1944 /* Helper function to insert LIST before BSI, and set up line number info. */
1947 sra_insert_before (block_stmt_iterator
*bsi
, tree list
)
1949 tree stmt
= bsi_stmt (*bsi
);
1951 if (EXPR_HAS_LOCATION (stmt
))
1952 annotate_all_with_locus (&list
, EXPR_LOCATION (stmt
));
1953 bsi_insert_before (bsi
, list
, BSI_SAME_STMT
);
1956 /* Similarly, but insert after BSI. Handles insertion onto edges as well. */
1959 sra_insert_after (block_stmt_iterator
*bsi
, tree list
)
1961 tree stmt
= bsi_stmt (*bsi
);
1963 if (EXPR_HAS_LOCATION (stmt
))
1964 annotate_all_with_locus (&list
, EXPR_LOCATION (stmt
));
1966 if (stmt_ends_bb_p (stmt
))
1967 insert_edge_copies (list
, bsi
->bb
);
1969 bsi_insert_after (bsi
, list
, BSI_SAME_STMT
);
1972 /* Similarly, but replace the statement at BSI. */
1975 sra_replace (block_stmt_iterator
*bsi
, tree list
)
1977 sra_insert_before (bsi
, list
);
1978 bsi_remove (bsi
, false);
1979 if (bsi_end_p (*bsi
))
1980 *bsi
= bsi_last (bsi
->bb
);
1985 /* Scalarize a USE. To recap, this is either a simple reference to ELT,
1986 if elt is scalar, or some occurrence of ELT that requires a complete
1987 aggregate. IS_OUTPUT is true if ELT is being modified. */
1990 scalarize_use (struct sra_elt
*elt
, tree
*expr_p
, block_stmt_iterator
*bsi
,
1991 bool is_output
, bool use_all
)
1993 tree list
= NULL
, stmt
= bsi_stmt (*bsi
);
1995 if (elt
->replacement
)
1997 /* If we have a replacement, then updating the reference is as
1998 simple as modifying the existing statement in place. */
2000 mark_all_v_defs (stmt
);
2001 *expr_p
= elt
->replacement
;
2006 /* Otherwise we need some copies. If ELT is being read, then we want
2007 to store all (modified) sub-elements back into the structure before
2008 the reference takes place. If ELT is being written, then we want to
2009 load the changed values back into our shadow variables. */
2010 /* ??? We don't check modified for reads, we just always write all of
2011 the values. We should be able to record the SSA number of the VOP
2012 for which the values were last read. If that number matches the
2013 SSA number of the VOP in the current statement, then we needn't
2014 emit an assignment. This would also eliminate double writes when
2015 a structure is passed as more than one argument to a function call.
2016 This optimization would be most effective if sra_walk_function
2017 processed the blocks in dominator order. */
2019 generate_copy_inout (elt
, is_output
, generate_element_ref (elt
), &list
);
2022 mark_all_v_defs (list
);
2024 sra_insert_after (bsi
, list
);
2027 sra_insert_before (bsi
, list
);
2029 mark_no_warning (elt
);
2034 /* Scalarize a COPY. To recap, this is an assignment statement between
2035 two scalarizable references, LHS_ELT and RHS_ELT. */
2038 scalarize_copy (struct sra_elt
*lhs_elt
, struct sra_elt
*rhs_elt
,
2039 block_stmt_iterator
*bsi
)
2043 if (lhs_elt
->replacement
&& rhs_elt
->replacement
)
2045 /* If we have two scalar operands, modify the existing statement. */
2046 stmt
= bsi_stmt (*bsi
);
2048 /* See the commentary in sra_walk_function concerning
2049 RETURN_EXPR, and why we should never see one here. */
2050 gcc_assert (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
2052 GIMPLE_STMT_OPERAND (stmt
, 0) = lhs_elt
->replacement
;
2053 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs_elt
->replacement
;
2056 else if (lhs_elt
->use_block_copy
|| rhs_elt
->use_block_copy
)
2058 /* If either side requires a block copy, then sync the RHS back
2059 to the original structure, leave the original assignment
2060 statement (which will perform the block copy), then load the
2061 LHS values out of its now-updated original structure. */
2062 /* ??? Could perform a modified pair-wise element copy. That
2063 would at least allow those elements that are instantiated in
2064 both structures to be optimized well. */
2067 generate_copy_inout (rhs_elt
, false,
2068 generate_element_ref (rhs_elt
), &list
);
2071 mark_all_v_defs (list
);
2072 sra_insert_before (bsi
, list
);
2076 generate_copy_inout (lhs_elt
, true,
2077 generate_element_ref (lhs_elt
), &list
);
2080 mark_all_v_defs (list
);
2081 sra_insert_after (bsi
, list
);
2086 /* Otherwise both sides must be fully instantiated. In which
2087 case perform pair-wise element assignments and replace the
2088 original block copy statement. */
2090 stmt
= bsi_stmt (*bsi
);
2091 mark_all_v_defs (stmt
);
2094 generate_element_copy (lhs_elt
, rhs_elt
, &list
);
2096 mark_all_v_defs (list
);
2097 sra_replace (bsi
, list
);
2101 /* Scalarize an INIT. To recap, this is an assignment to a scalarizable
2102 reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
2103 COMPLEX_EXPR. If RHS is NULL, it should be treated as an empty
2107 scalarize_init (struct sra_elt
*lhs_elt
, tree rhs
, block_stmt_iterator
*bsi
)
2112 /* Generate initialization statements for all members extant in the RHS. */
2115 /* Unshare the expression just in case this is from a decl's initial. */
2116 rhs
= unshare_expr (rhs
);
2117 result
= generate_element_init (lhs_elt
, rhs
, &list
);
2120 /* CONSTRUCTOR is defined such that any member not mentioned is assigned
2121 a zero value. Initialize the rest of the instantiated elements. */
2122 generate_element_zero (lhs_elt
, &list
);
2126 /* If we failed to convert the entire initializer, then we must
2127 leave the structure assignment in place and must load values
2128 from the structure into the slots for which we did not find
2129 constants. The easiest way to do this is to generate a complete
2130 copy-out, and then follow that with the constant assignments
2131 that we were able to build. DCE will clean things up. */
2133 generate_copy_inout (lhs_elt
, true, generate_element_ref (lhs_elt
),
2135 append_to_statement_list (list
, &list0
);
2139 if (lhs_elt
->use_block_copy
|| !result
)
2141 /* Since LHS is not fully instantiated, we must leave the structure
2142 assignment in place. Treating this case differently from a USE
2143 exposes constants to later optimizations. */
2146 mark_all_v_defs (list
);
2147 sra_insert_after (bsi
, list
);
2152 /* The LHS is fully instantiated. The list of initializations
2153 replaces the original structure assignment. */
2155 mark_all_v_defs (bsi_stmt (*bsi
));
2156 mark_all_v_defs (list
);
2157 sra_replace (bsi
, list
);
2161 /* A subroutine of scalarize_ldst called via walk_tree. Set TREE_NO_TRAP
2162 on all INDIRECT_REFs. */
2165 mark_notrap (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
2169 if (TREE_CODE (t
) == INDIRECT_REF
)
2171 TREE_THIS_NOTRAP (t
) = 1;
2174 else if (IS_TYPE_OR_DECL_P (t
))
2180 /* Scalarize a LDST. To recap, this is an assignment between one scalarizable
2181 reference ELT and one non-scalarizable reference OTHER. IS_OUTPUT is true
2182 if ELT is on the left-hand side. */
2185 scalarize_ldst (struct sra_elt
*elt
, tree other
,
2186 block_stmt_iterator
*bsi
, bool is_output
)
2188 /* Shouldn't have gotten called for a scalar. */
2189 gcc_assert (!elt
->replacement
);
2191 if (elt
->use_block_copy
)
2193 /* Since ELT is not fully instantiated, we have to leave the
2194 block copy in place. Treat this as a USE. */
2195 scalarize_use (elt
, NULL
, bsi
, is_output
, false);
2199 /* The interesting case is when ELT is fully instantiated. In this
2200 case we can have each element stored/loaded directly to/from the
2201 corresponding slot in OTHER. This avoids a block copy. */
2203 tree list
= NULL
, stmt
= bsi_stmt (*bsi
);
2205 mark_all_v_defs (stmt
);
2206 generate_copy_inout (elt
, is_output
, other
, &list
);
2207 mark_all_v_defs (list
);
2210 /* Preserve EH semantics. */
2211 if (stmt_ends_bb_p (stmt
))
2213 tree_stmt_iterator tsi
;
2216 /* Extract the first statement from LIST. */
2217 tsi
= tsi_start (list
);
2218 first
= tsi_stmt (tsi
);
2221 /* Replace the old statement with this new representative. */
2222 bsi_replace (bsi
, first
, true);
2224 if (!tsi_end_p (tsi
))
2226 /* If any reference would trap, then they all would. And more
2227 to the point, the first would. Therefore none of the rest
2228 will trap since the first didn't. Indicate this by
2229 iterating over the remaining statements and set
2230 TREE_THIS_NOTRAP in all INDIRECT_REFs. */
2233 walk_tree (tsi_stmt_ptr (tsi
), mark_notrap
, NULL
, NULL
);
2236 while (!tsi_end_p (tsi
));
2238 insert_edge_copies (list
, bsi
->bb
);
2242 sra_replace (bsi
, list
);
2246 /* Generate initializations for all scalarizable parameters. */
2249 scalarize_parms (void)
2255 EXECUTE_IF_SET_IN_BITMAP (needs_copy_in
, 0, i
, bi
)
2257 tree var
= referenced_var (i
);
2258 struct sra_elt
*elt
= lookup_element (NULL
, var
, NULL
, NO_INSERT
);
2259 generate_copy_inout (elt
, true, var
, &list
);
2264 insert_edge_copies (list
, ENTRY_BLOCK_PTR
);
2265 mark_all_v_defs (list
);
2269 /* Entry point to phase 4. Update the function to match replacements. */
2272 scalarize_function (void)
2274 static const struct sra_walk_fns fns
= {
2275 scalarize_use
, scalarize_copy
, scalarize_init
, scalarize_ldst
, false
2278 sra_walk_function (&fns
);
2280 bsi_commit_edge_inserts ();
2284 /* Debug helper function. Print ELT in a nice human-readable format. */
2287 dump_sra_elt_name (FILE *f
, struct sra_elt
*elt
)
2289 if (elt
->parent
&& TREE_CODE (elt
->parent
->type
) == COMPLEX_TYPE
)
2291 fputs (elt
->element
== integer_zero_node
? "__real__ " : "__imag__ ", f
);
2292 dump_sra_elt_name (f
, elt
->parent
);
2297 dump_sra_elt_name (f
, elt
->parent
);
2298 if (DECL_P (elt
->element
))
2300 if (TREE_CODE (elt
->element
) == FIELD_DECL
)
2302 print_generic_expr (f
, elt
->element
, dump_flags
);
2304 else if (TREE_CODE (elt
->element
) == RANGE_EXPR
)
2305 fprintf (f
, "["HOST_WIDE_INT_PRINT_DEC
".."HOST_WIDE_INT_PRINT_DEC
"]",
2306 TREE_INT_CST_LOW (TREE_OPERAND (elt
->element
, 0)),
2307 TREE_INT_CST_LOW (TREE_OPERAND (elt
->element
, 1)));
2309 fprintf (f
, "[" HOST_WIDE_INT_PRINT_DEC
"]",
2310 TREE_INT_CST_LOW (elt
->element
));
2314 /* Likewise, but callable from the debugger. */
2317 debug_sra_elt_name (struct sra_elt
*elt
)
2319 dump_sra_elt_name (stderr
, elt
);
2320 fputc ('\n', stderr
);
2324 sra_init_cache (void)
2326 if (sra_type_decomp_cache
)
2329 sra_type_decomp_cache
= BITMAP_ALLOC (NULL
);
2330 sra_type_inst_cache
= BITMAP_ALLOC (NULL
);
2333 /* Main entry point. */
2338 /* Initialize local variables. */
2340 gcc_obstack_init (&sra_obstack
);
2341 sra_candidates
= BITMAP_ALLOC (NULL
);
2342 needs_copy_in
= BITMAP_ALLOC (NULL
);
2344 sra_map
= htab_create (101, sra_elt_hash
, sra_elt_eq
, NULL
);
2346 /* Scan. If we find anything, instantiate and scalarize. */
2347 if (find_candidates_for_sra ())
2350 decide_instantiations ();
2351 scalarize_function ();
2354 /* Free allocated memory. */
2355 htab_delete (sra_map
);
2357 BITMAP_FREE (sra_candidates
);
2358 BITMAP_FREE (needs_copy_in
);
2359 BITMAP_FREE (sra_type_decomp_cache
);
2360 BITMAP_FREE (sra_type_inst_cache
);
2361 obstack_free (&sra_obstack
, NULL
);
2368 return flag_tree_sra
!= 0;
2371 struct tree_opt_pass pass_sra
=
2374 gate_sra
, /* gate */
2375 tree_sra
, /* execute */
2378 0, /* static_pass_number */
2379 TV_TREE_SRA
, /* tv_id */
2380 PROP_cfg
| PROP_ssa
, /* properties_required */
2381 0, /* properties_provided */
2382 0, /* properties_destroyed */
2383 0, /* todo_flags_start */
2387 | TODO_verify_ssa
, /* todo_flags_finish */