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, 2007
5 Free Software Foundation, Inc.
6 Contributed by Diego Novillo <dnovillo@redhat.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 2, or (at your option) any
15 GCC is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
27 #include "coretypes.h"
32 /* These RTL headers are needed for basic-block.h. */
35 #include "hard-reg-set.h"
36 #include "basic-block.h"
37 #include "diagnostic.h"
38 #include "langhooks.h"
39 #include "tree-inline.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-dump.h"
43 #include "tree-pass.h"
49 /* expr.h is needed for MOVE_RATIO. */
54 /* This object of this pass is to replace a non-addressable aggregate with a
55 set of independent variables. Most of the time, all of these variables
56 will be scalars. But a secondary objective is to break up larger
57 aggregates into smaller aggregates. In the process we may find that some
58 bits of the larger aggregate can be deleted as unreferenced.
60 This substitution is done globally. More localized substitutions would
61 be the purvey of a load-store motion pass.
63 The optimization proceeds in phases:
65 (1) Identify variables that have types that are candidates for
68 (2) Scan the function looking for the ways these variables are used.
69 In particular we're interested in the number of times a variable
70 (or member) is needed as a complete unit, and the number of times
71 a variable (or member) is copied.
73 (3) Based on the usage profile, instantiate substitution variables.
75 (4) Scan the function making replacements.
79 /* The set of todo flags to return from tree_sra. */
80 static unsigned int todoflags;
82 /* The set of aggregate variables that are candidates for scalarization. */
83 static bitmap sra_candidates;
85 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
86 beginning of the function. */
87 static bitmap needs_copy_in;
89 /* Sets of bit pairs that cache type decomposition and instantiation. */
90 static bitmap sra_type_decomp_cache;
91 static bitmap sra_type_inst_cache;
93 /* One of these structures is created for each candidate aggregate and
94 each (accessed) member or group of members of such an aggregate. */
97 /* A tree of the elements. Used when we want to traverse everything. */
98 struct sra_elt *parent;
99 struct sra_elt *groups;
100 struct sra_elt *children;
101 struct sra_elt *sibling;
103 /* If this element is a root, then this is the VAR_DECL. If this is
104 a sub-element, this is some token used to identify the reference.
105 In the case of COMPONENT_REF, this is the FIELD_DECL. In the case
106 of an ARRAY_REF, this is the (constant) index. In the case of an
107 ARRAY_RANGE_REF, this is the (constant) RANGE_EXPR. In the case
108 of a complex number, this is a zero or one. */
111 /* The type of the element. */
114 /* A VAR_DECL, for any sub-element we've decided to replace. */
117 /* The number of times the element is referenced as a whole. I.e.
118 given "a.b.c", this would be incremented for C, but not for A or B. */
121 /* The number of times the element is copied to or from another
122 scalarizable element. */
123 unsigned int n_copies;
125 /* True if TYPE is scalar. */
128 /* True if this element is a group of members of its parent. */
131 /* True if we saw something about this element that prevents scalarization,
132 such as non-constant indexing. */
133 bool cannot_scalarize;
135 /* True if we've decided that structure-to-structure assignment
136 should happen via memcpy and not per-element. */
139 /* True if everything under this element has been marked TREE_NO_WARNING. */
142 /* A flag for use with/after random access traversals. */
146 #define IS_ELEMENT_FOR_GROUP(ELEMENT) (TREE_CODE (ELEMENT) == RANGE_EXPR)
148 #define FOR_EACH_ACTUAL_CHILD(CHILD, ELT) \
149 for ((CHILD) = (ELT)->is_group \
150 ? next_child_for_group (NULL, (ELT)) \
153 (CHILD) = (ELT)->is_group \
154 ? next_child_for_group ((CHILD), (ELT)) \
157 /* Helper function for above macro. Return next child in group. */
158 static struct sra_elt *
159 next_child_for_group (struct sra_elt *child, struct sra_elt *group)
161 gcc_assert (group->is_group);
163 /* Find the next child in the parent. */
165 child = child->sibling;
167 child = group->parent->children;
169 /* Skip siblings that do not belong to the group. */
172 tree g_elt = group->element;
173 if (TREE_CODE (g_elt) == RANGE_EXPR)
175 if (!tree_int_cst_lt (child->element, TREE_OPERAND (g_elt, 0))
176 && !tree_int_cst_lt (TREE_OPERAND (g_elt, 1), child->element))
182 child = child->sibling;
188 /* Random access to the child of a parent is performed by hashing.
189 This prevents quadratic behavior, and allows SRA to function
190 reasonably on larger records. */
191 static htab_t sra_map;
193 /* All structures are allocated out of the following obstack. */
194 static struct obstack sra_obstack;
196 /* Debugging functions. */
197 static void dump_sra_elt_name (FILE *, struct sra_elt *);
198 extern void debug_sra_elt_name (struct sra_elt *);
200 /* Forward declarations. */
201 static tree generate_element_ref (struct sra_elt *);
203 /* Return true if DECL is an SRA candidate. */
206 is_sra_candidate_decl (tree decl)
208 return DECL_P (decl) && bitmap_bit_p (sra_candidates, DECL_UID (decl));
211 /* Return true if TYPE is a scalar type. */
214 is_sra_scalar_type (tree type)
216 enum tree_code code = TREE_CODE (type);
217 return (code == INTEGER_TYPE || code == REAL_TYPE || code == VECTOR_TYPE
218 || code == ENUMERAL_TYPE || code == BOOLEAN_TYPE
219 || code == POINTER_TYPE || code == OFFSET_TYPE
220 || code == REFERENCE_TYPE);
223 /* Return true if TYPE can be decomposed into a set of independent variables.
225 Note that this doesn't imply that all elements of TYPE can be
226 instantiated, just that if we decide to break up the type into
227 separate pieces that it can be done. */
230 sra_type_can_be_decomposed_p (tree type)
232 unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
235 /* Avoid searching the same type twice. */
236 if (bitmap_bit_p (sra_type_decomp_cache, cache+0))
238 if (bitmap_bit_p (sra_type_decomp_cache, cache+1))
241 /* The type must have a definite nonzero size. */
242 if (TYPE_SIZE (type) == NULL || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
243 || integer_zerop (TYPE_SIZE (type)))
246 /* The type must be a non-union aggregate. */
247 switch (TREE_CODE (type))
251 bool saw_one_field = false;
253 for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
254 if (TREE_CODE (t) == FIELD_DECL)
256 /* Reject incorrectly represented bit fields. */
257 if (DECL_BIT_FIELD (t)
258 && (tree_low_cst (DECL_SIZE (t), 1)
259 != TYPE_PRECISION (TREE_TYPE (t))))
262 saw_one_field = true;
265 /* Record types must have at least one field. */
272 /* Array types must have a fixed lower and upper bound. */
273 t = TYPE_DOMAIN (type);
276 if (TYPE_MIN_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MIN_VALUE (t)))
278 if (TYPE_MAX_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MAX_VALUE (t)))
289 bitmap_set_bit (sra_type_decomp_cache, cache+0);
293 bitmap_set_bit (sra_type_decomp_cache, cache+1);
297 /* Return true if DECL can be decomposed into a set of independent
298 (though not necessarily scalar) variables. */
301 decl_can_be_decomposed_p (tree var)
303 /* Early out for scalars. */
304 if (is_sra_scalar_type (TREE_TYPE (var)))
307 /* The variable must not be aliased. */
308 if (!is_gimple_non_addressable (var))
310 if (dump_file && (dump_flags & TDF_DETAILS))
312 fprintf (dump_file, "Cannot scalarize variable ");
313 print_generic_expr (dump_file, var, dump_flags);
314 fprintf (dump_file, " because it must live in memory\n");
319 /* The variable must not be volatile. */
320 if (TREE_THIS_VOLATILE (var))
322 if (dump_file && (dump_flags & TDF_DETAILS))
324 fprintf (dump_file, "Cannot scalarize variable ");
325 print_generic_expr (dump_file, var, dump_flags);
326 fprintf (dump_file, " because it is declared volatile\n");
331 /* We must be able to decompose the variable's type. */
332 if (!sra_type_can_be_decomposed_p (TREE_TYPE (var)))
334 if (dump_file && (dump_flags & TDF_DETAILS))
336 fprintf (dump_file, "Cannot scalarize variable ");
337 print_generic_expr (dump_file, var, dump_flags);
338 fprintf (dump_file, " because its type cannot be decomposed\n");
346 /* Return true if TYPE can be *completely* decomposed into scalars. */
349 type_can_instantiate_all_elements (tree type)
351 if (is_sra_scalar_type (type))
353 if (!sra_type_can_be_decomposed_p (type))
356 switch (TREE_CODE (type))
360 unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
363 if (bitmap_bit_p (sra_type_inst_cache, cache+0))
365 if (bitmap_bit_p (sra_type_inst_cache, cache+1))
368 for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
369 if (TREE_CODE (f) == FIELD_DECL)
371 if (!type_can_instantiate_all_elements (TREE_TYPE (f)))
373 bitmap_set_bit (sra_type_inst_cache, cache+1);
378 bitmap_set_bit (sra_type_inst_cache, cache+0);
383 return type_can_instantiate_all_elements (TREE_TYPE (type));
393 /* Test whether ELT or some sub-element cannot be scalarized. */
396 can_completely_scalarize_p (struct sra_elt *elt)
400 if (elt->cannot_scalarize)
403 for (c = elt->children; c; c = c->sibling)
404 if (!can_completely_scalarize_p (c))
407 for (c = elt->groups; c; c = c->sibling)
408 if (!can_completely_scalarize_p (c))
415 /* A simplified tree hashing algorithm that only handles the types of
416 trees we expect to find in sra_elt->element. */
419 sra_hash_tree (tree t)
423 switch (TREE_CODE (t))
432 h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
436 h = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
437 h = iterative_hash_expr (TREE_OPERAND (t, 1), h);
441 /* We can have types that are compatible, but have different member
442 lists, so we can't hash fields by ID. Use offsets instead. */
443 h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0);
444 h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h);
454 /* Hash function for type SRA_PAIR. */
457 sra_elt_hash (const void *x)
459 const struct sra_elt *e = x;
460 const struct sra_elt *p;
463 h = sra_hash_tree (e->element);
465 /* Take into account everything back up the chain. Given that chain
466 lengths are rarely very long, this should be acceptable. If we
467 truly identify this as a performance problem, it should work to
468 hash the pointer value "e->parent". */
469 for (p = e->parent; p ; p = p->parent)
470 h = (h * 65521) ^ sra_hash_tree (p->element);
475 /* Equality function for type SRA_PAIR. */
478 sra_elt_eq (const void *x, const void *y)
480 const struct sra_elt *a = x;
481 const struct sra_elt *b = y;
484 if (a->parent != b->parent)
492 if (TREE_CODE (ae) != TREE_CODE (be))
495 switch (TREE_CODE (ae))
500 /* These are all pointer unique. */
504 /* Integers are not pointer unique, so compare their values. */
505 return tree_int_cst_equal (ae, be);
509 tree_int_cst_equal (TREE_OPERAND (ae, 0), TREE_OPERAND (be, 0))
510 && tree_int_cst_equal (TREE_OPERAND (ae, 1), TREE_OPERAND (be, 1));
513 /* Fields are unique within a record, but not between
514 compatible records. */
515 if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be))
517 return fields_compatible_p (ae, be);
524 /* Create or return the SRA_ELT structure for CHILD in PARENT. PARENT
525 may be null, in which case CHILD must be a DECL. */
527 static struct sra_elt *
528 lookup_element (struct sra_elt *parent, tree child, tree type,
529 enum insert_option insert)
531 struct sra_elt dummy;
532 struct sra_elt **slot;
536 dummy.parent = parent->is_group ? parent->parent : parent;
539 dummy.element = child;
541 slot = (struct sra_elt **) htab_find_slot (sra_map, &dummy, insert);
542 if (!slot && insert == NO_INSERT)
546 if (!elt && insert == INSERT)
548 *slot = elt = obstack_alloc (&sra_obstack, sizeof (*elt));
549 memset (elt, 0, sizeof (*elt));
551 elt->parent = parent;
552 elt->element = child;
554 elt->is_scalar = is_sra_scalar_type (type);
558 if (IS_ELEMENT_FOR_GROUP (elt->element))
560 elt->is_group = true;
561 elt->sibling = parent->groups;
562 parent->groups = elt;
566 elt->sibling = parent->children;
567 parent->children = elt;
571 /* If this is a parameter, then if we want to scalarize, we have
572 one copy from the true function parameter. Count it now. */
573 if (TREE_CODE (child) == PARM_DECL)
576 bitmap_set_bit (needs_copy_in, DECL_UID (child));
583 /* Create or return the SRA_ELT structure for EXPR if the expression
584 refers to a scalarizable variable. */
586 static struct sra_elt *
587 maybe_lookup_element_for_expr (tree expr)
592 switch (TREE_CODE (expr))
597 if (is_sra_candidate_decl (expr))
598 return lookup_element (NULL, expr, TREE_TYPE (expr), INSERT);
602 /* We can't scalarize variable array indices. */
603 if (in_array_bounds_p (expr))
604 child = TREE_OPERAND (expr, 1);
609 case ARRAY_RANGE_REF:
610 /* We can't scalarize variable array indices. */
611 if (range_in_array_bounds_p (expr))
613 tree domain = TYPE_DOMAIN (TREE_TYPE (expr));
614 child = build2 (RANGE_EXPR, integer_type_node,
615 TYPE_MIN_VALUE (domain), TYPE_MAX_VALUE (domain));
622 /* Don't look through unions. */
623 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) != RECORD_TYPE)
625 child = TREE_OPERAND (expr, 1);
629 child = integer_zero_node;
632 child = integer_one_node;
639 elt = maybe_lookup_element_for_expr (TREE_OPERAND (expr, 0));
641 return lookup_element (elt, child, TREE_TYPE (expr), INSERT);
646 /* Functions to walk just enough of the tree to see all scalarizable
647 references, and categorize them. */
649 /* A set of callbacks for phases 2 and 4. They'll be invoked for the
650 various kinds of references seen. In all cases, *BSI is an iterator
651 pointing to the statement being processed. */
654 /* Invoked when ELT is required as a unit. Note that ELT might refer to
655 a leaf node, in which case this is a simple scalar reference. *EXPR_P
656 points to the location of the expression. IS_OUTPUT is true if this
657 is a left-hand-side reference. USE_ALL is true if we saw something we
658 couldn't quite identify and had to force the use of the entire object. */
659 void (*use) (struct sra_elt *elt, tree *expr_p,
660 block_stmt_iterator *bsi, bool is_output, bool use_all);
662 /* Invoked when we have a copy between two scalarizable references. */
663 void (*copy) (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
664 block_stmt_iterator *bsi);
666 /* Invoked when ELT is initialized from a constant. VALUE may be NULL,
667 in which case it should be treated as an empty CONSTRUCTOR. */
668 void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
670 /* Invoked when we have a copy between one scalarizable reference ELT
671 and one non-scalarizable reference OTHER without side-effects.
672 IS_OUTPUT is true if ELT is on the left-hand side. */
673 void (*ldst) (struct sra_elt *elt, tree other,
674 block_stmt_iterator *bsi, bool is_output);
676 /* True during phase 2, false during phase 4. */
677 /* ??? This is a hack. */
681 #ifdef ENABLE_CHECKING
682 /* Invoked via walk_tree, if *TP contains a candidate decl, return it. */
685 sra_find_candidate_decl (tree *tp, int *walk_subtrees,
686 void *data ATTRIBUTE_UNUSED)
689 enum tree_code code = TREE_CODE (t);
691 if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
694 if (is_sra_candidate_decl (t))
704 /* Walk most expressions looking for a scalarizable aggregate.
705 If we find one, invoke FNS->USE. */
708 sra_walk_expr (tree *expr_p, block_stmt_iterator *bsi, bool is_output,
709 const struct sra_walk_fns *fns)
713 bool disable_scalarization = false;
714 bool use_all_p = false;
716 /* We're looking to collect a reference expression between EXPR and INNER,
717 such that INNER is a scalarizable decl and all other nodes through EXPR
718 are references that we can scalarize. If we come across something that
719 we can't scalarize, we reset EXPR. This has the effect of making it
720 appear that we're referring to the larger expression as a whole. */
723 switch (TREE_CODE (inner))
728 /* If there is a scalarizable decl at the bottom, then process it. */
729 if (is_sra_candidate_decl (inner))
731 struct sra_elt *elt = maybe_lookup_element_for_expr (expr);
732 if (disable_scalarization)
733 elt->cannot_scalarize = true;
735 fns->use (elt, expr_p, bsi, is_output, use_all_p);
740 /* Non-constant index means any member may be accessed. Prevent the
741 expression from being scalarized. If we were to treat this as a
742 reference to the whole array, we can wind up with a single dynamic
743 index reference inside a loop being overridden by several constant
744 index references during loop setup. It's possible that this could
745 be avoided by using dynamic usage counts based on BB trip counts
746 (based on loop analysis or profiling), but that hardly seems worth
748 /* ??? Hack. Figure out how to push this into the scan routines
749 without duplicating too much code. */
750 if (!in_array_bounds_p (inner))
752 disable_scalarization = true;
755 /* ??? Are we assured that non-constant bounds and stride will have
756 the same value everywhere? I don't think Fortran will... */
757 if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
759 inner = TREE_OPERAND (inner, 0);
762 case ARRAY_RANGE_REF:
763 if (!range_in_array_bounds_p (inner))
765 disable_scalarization = true;
768 /* ??? See above non-constant bounds and stride . */
769 if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
771 inner = TREE_OPERAND (inner, 0);
775 /* A reference to a union member constitutes a reference to the
777 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (inner, 0))) != RECORD_TYPE)
779 /* ??? See above re non-constant stride. */
780 if (TREE_OPERAND (inner, 2))
782 inner = TREE_OPERAND (inner, 0);
787 inner = TREE_OPERAND (inner, 0);
791 /* A bit field reference (access to *multiple* fields simultaneously)
792 is not currently scalarized. Consider this an access to the
793 complete outer element, to which walk_tree will bring us next. */
796 case VIEW_CONVERT_EXPR:
798 /* Similarly, a view/nop explicitly wants to look at an object in a
799 type other than the one we've scalarized. */
803 /* This is a transparent wrapper. The entire inner expression really
808 expr_p = &TREE_OPERAND (inner, 0);
809 inner = expr = *expr_p;
814 #ifdef ENABLE_CHECKING
815 /* Validate that we're not missing any references. */
816 gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL));
822 /* Walk a TREE_LIST of values looking for scalarizable aggregates.
823 If we find one, invoke FNS->USE. */
826 sra_walk_tree_list (tree list, block_stmt_iterator *bsi, bool is_output,
827 const struct sra_walk_fns *fns)
830 for (op = list; op ; op = TREE_CHAIN (op))
831 sra_walk_expr (&TREE_VALUE (op), bsi, is_output, fns);
834 /* Walk the arguments of a CALL_EXPR looking for scalarizable aggregates.
835 If we find one, invoke FNS->USE. */
838 sra_walk_call_expr (tree expr, block_stmt_iterator *bsi,
839 const struct sra_walk_fns *fns)
841 sra_walk_tree_list (TREE_OPERAND (expr, 1), bsi, false, fns);
844 /* Walk the inputs and outputs of an ASM_EXPR looking for scalarizable
845 aggregates. If we find one, invoke FNS->USE. */
848 sra_walk_asm_expr (tree expr, block_stmt_iterator *bsi,
849 const struct sra_walk_fns *fns)
851 sra_walk_tree_list (ASM_INPUTS (expr), bsi, false, fns);
852 sra_walk_tree_list (ASM_OUTPUTS (expr), bsi, true, fns);
855 /* Walk a MODIFY_EXPR and categorize the assignment appropriately. */
858 sra_walk_modify_expr (tree expr, block_stmt_iterator *bsi,
859 const struct sra_walk_fns *fns)
861 struct sra_elt *lhs_elt, *rhs_elt;
864 lhs = TREE_OPERAND (expr, 0);
865 rhs = TREE_OPERAND (expr, 1);
866 lhs_elt = maybe_lookup_element_for_expr (lhs);
867 rhs_elt = maybe_lookup_element_for_expr (rhs);
869 /* If both sides are scalarizable, this is a COPY operation. */
870 if (lhs_elt && rhs_elt)
872 fns->copy (lhs_elt, rhs_elt, bsi);
876 /* If the RHS is scalarizable, handle it. There are only two cases. */
879 if (!rhs_elt->is_scalar && !TREE_SIDE_EFFECTS (lhs))
880 fns->ldst (rhs_elt, lhs, bsi, false);
882 fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, false, false);
885 /* If it isn't scalarizable, there may be scalarizable variables within, so
886 check for a call or else walk the RHS to see if we need to do any
887 copy-in operations. We need to do it before the LHS is scalarized so
888 that the statements get inserted in the proper place, before any
889 copy-out operations. */
892 tree call = get_call_expr_in (rhs);
894 sra_walk_call_expr (call, bsi, fns);
896 sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns);
899 /* Likewise, handle the LHS being scalarizable. We have cases similar
900 to those above, but also want to handle RHS being constant. */
903 /* If this is an assignment from a constant, or constructor, then
904 we have access to all of the elements individually. Invoke INIT. */
905 if (TREE_CODE (rhs) == COMPLEX_EXPR
906 || TREE_CODE (rhs) == COMPLEX_CST
907 || TREE_CODE (rhs) == CONSTRUCTOR)
908 fns->init (lhs_elt, rhs, bsi);
910 /* If this is an assignment from read-only memory, treat this as if
911 we'd been passed the constructor directly. Invoke INIT. */
912 else if (TREE_CODE (rhs) == VAR_DECL
914 && TREE_READONLY (rhs)
915 && targetm.binds_local_p (rhs))
916 fns->init (lhs_elt, DECL_INITIAL (rhs), bsi);
918 /* If this is a copy from a non-scalarizable lvalue, invoke LDST.
919 The lvalue requirement prevents us from trying to directly scalarize
920 the result of a function call. Which would result in trying to call
921 the function multiple times, and other evil things. */
922 else if (!lhs_elt->is_scalar
923 && !TREE_SIDE_EFFECTS (rhs) && is_gimple_addressable (rhs))
924 fns->ldst (lhs_elt, rhs, bsi, true);
926 /* Otherwise we're being used in some context that requires the
927 aggregate to be seen as a whole. Invoke USE. */
929 fns->use (lhs_elt, &TREE_OPERAND (expr, 0), bsi, true, false);
932 /* Similarly to above, LHS_ELT being null only means that the LHS as a
933 whole is not a scalarizable reference. There may be occurrences of
934 scalarizable variables within, which implies a USE. */
936 sra_walk_expr (&TREE_OPERAND (expr, 0), bsi, true, fns);
939 /* Entry point to the walk functions. Search the entire function,
940 invoking the callbacks in FNS on each of the references to
941 scalarizable variables. */
944 sra_walk_function (const struct sra_walk_fns *fns)
947 block_stmt_iterator si, ni;
949 /* ??? Phase 4 could derive some benefit to walking the function in
950 dominator tree order. */
953 for (si = bsi_start (bb); !bsi_end_p (si); si = ni)
958 stmt = bsi_stmt (si);
959 ann = stmt_ann (stmt);
964 /* If the statement has no virtual operands, then it doesn't
965 make any structure references that we care about. */
966 if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE)))
969 switch (TREE_CODE (stmt))
972 /* If we have "return <retval>" then the return value is
973 already exposed for our pleasure. Walk it as a USE to
974 force all the components back in place for the return.
976 If we have an embedded assignment, then <retval> is of
977 a type that gets returned in registers in this ABI, and
978 we do not wish to extend their lifetimes. Treat this
979 as a USE of the variable on the RHS of this assignment. */
981 t = TREE_OPERAND (stmt, 0);
982 if (TREE_CODE (t) == MODIFY_EXPR)
983 sra_walk_expr (&TREE_OPERAND (t, 1), &si, false, fns);
985 sra_walk_expr (&TREE_OPERAND (stmt, 0), &si, false, fns);
989 sra_walk_modify_expr (stmt, &si, fns);
992 sra_walk_call_expr (stmt, &si, fns);
995 sra_walk_asm_expr (stmt, &si, fns);
1004 /* Phase One: Scan all referenced variables in the program looking for
1005 structures that could be decomposed. */
1008 find_candidates_for_sra (void)
1010 bool any_set = false;
1012 referenced_var_iterator rvi;
1014 FOR_EACH_REFERENCED_VAR (var, rvi)
1016 if (decl_can_be_decomposed_p (var))
1018 bitmap_set_bit (sra_candidates, DECL_UID (var));
1027 /* Phase Two: Scan all references to scalarizable variables. Count the
1028 number of times they are used or copied respectively. */
1030 /* Callbacks to fill in SRA_WALK_FNS. Everything but USE is
1031 considered a copy, because we can decompose the reference such that
1032 the sub-elements needn't be contiguous. */
1035 scan_use (struct sra_elt *elt, tree *expr_p ATTRIBUTE_UNUSED,
1036 block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
1037 bool is_output ATTRIBUTE_UNUSED, bool use_all ATTRIBUTE_UNUSED)
1043 scan_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
1044 block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
1046 lhs_elt->n_copies += 1;
1047 rhs_elt->n_copies += 1;
1051 scan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED,
1052 block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
1054 lhs_elt->n_copies += 1;
1058 scan_ldst (struct sra_elt *elt, tree other ATTRIBUTE_UNUSED,
1059 block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
1060 bool is_output ATTRIBUTE_UNUSED)
1065 /* Dump the values we collected during the scanning phase. */
1068 scan_dump (struct sra_elt *elt)
1072 dump_sra_elt_name (dump_file, elt);
1073 fprintf (dump_file, ": n_uses=%u n_copies=%u\n", elt->n_uses, elt->n_copies);
1075 for (c = elt->children; c ; c = c->sibling)
1078 for (c = elt->groups; c ; c = c->sibling)
1082 /* Entry point to phase 2. Scan the entire function, building up
1083 scalarization data structures, recording copies and uses. */
1086 scan_function (void)
1088 static const struct sra_walk_fns fns = {
1089 scan_use, scan_copy, scan_init, scan_ldst, true
1093 sra_walk_function (&fns);
1095 if (dump_file && (dump_flags & TDF_DETAILS))
1099 fputs ("\nScan results:\n", dump_file);
1100 EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1102 tree var = referenced_var (i);
1103 struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1107 fputc ('\n', dump_file);
1111 /* Phase Three: Make decisions about which variables to scalarize, if any.
1112 All elements to be scalarized have replacement variables made for them. */
1114 /* A subroutine of build_element_name. Recursively build the element
1115 name on the obstack. */
1118 build_element_name_1 (struct sra_elt *elt)
1125 build_element_name_1 (elt->parent);
1126 obstack_1grow (&sra_obstack, '$');
1128 if (TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
1130 if (elt->element == integer_zero_node)
1131 obstack_grow (&sra_obstack, "real", 4);
1133 obstack_grow (&sra_obstack, "imag", 4);
1139 if (TREE_CODE (t) == INTEGER_CST)
1141 /* ??? Eh. Don't bother doing double-wide printing. */
1142 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (t));
1143 obstack_grow (&sra_obstack, buffer, strlen (buffer));
1147 tree name = DECL_NAME (t);
1149 obstack_grow (&sra_obstack, IDENTIFIER_POINTER (name),
1150 IDENTIFIER_LENGTH (name));
1153 sprintf (buffer, "D%u", DECL_UID (t));
1154 obstack_grow (&sra_obstack, buffer, strlen (buffer));
1159 /* Construct a pretty variable name for an element's replacement variable.
1160 The name is built on the obstack. */
1163 build_element_name (struct sra_elt *elt)
1165 build_element_name_1 (elt);
1166 obstack_1grow (&sra_obstack, '\0');
1167 return XOBFINISH (&sra_obstack, char *);
1170 /* Instantiate an element as an independent variable. */
1173 instantiate_element (struct sra_elt *elt)
1175 struct sra_elt *base_elt;
1178 for (base_elt = elt; base_elt->parent; base_elt = base_elt->parent)
1180 base = base_elt->element;
1182 elt->replacement = var = make_rename_temp (elt->type, "SR");
1183 DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (base);
1184 DECL_ARTIFICIAL (var) = 1;
1186 if (TREE_THIS_VOLATILE (elt->type))
1188 TREE_THIS_VOLATILE (var) = 1;
1189 TREE_SIDE_EFFECTS (var) = 1;
1192 if (DECL_NAME (base) && !DECL_IGNORED_P (base))
1194 char *pretty_name = build_element_name (elt);
1195 DECL_NAME (var) = get_identifier (pretty_name);
1196 obstack_free (&sra_obstack, pretty_name);
1198 SET_DECL_DEBUG_EXPR (var, generate_element_ref (elt));
1199 DECL_DEBUG_EXPR_IS_FROM (var) = 1;
1201 DECL_IGNORED_P (var) = 0;
1202 TREE_NO_WARNING (var) = TREE_NO_WARNING (base);
1206 DECL_IGNORED_P (var) = 1;
1207 /* ??? We can't generate any warning that would be meaningful. */
1208 TREE_NO_WARNING (var) = 1;
1213 fputs (" ", dump_file);
1214 dump_sra_elt_name (dump_file, elt);
1215 fputs (" -> ", dump_file);
1216 print_generic_expr (dump_file, var, dump_flags);
1217 fputc ('\n', dump_file);
1221 /* Make one pass across an element tree deciding whether or not it's
1222 profitable to instantiate individual leaf scalars.
1224 PARENT_USES and PARENT_COPIES are the sum of the N_USES and N_COPIES
1225 fields all the way up the tree. */
1228 decide_instantiation_1 (struct sra_elt *elt, unsigned int parent_uses,
1229 unsigned int parent_copies)
1231 if (dump_file && !elt->parent)
1233 fputs ("Initial instantiation for ", dump_file);
1234 dump_sra_elt_name (dump_file, elt);
1235 fputc ('\n', dump_file);
1238 if (elt->cannot_scalarize)
1243 /* The decision is simple: instantiate if we're used more frequently
1244 than the parent needs to be seen as a complete unit. */
1245 if (elt->n_uses + elt->n_copies + parent_copies > parent_uses)
1246 instantiate_element (elt);
1250 struct sra_elt *c, *group;
1251 unsigned int this_uses = elt->n_uses + parent_uses;
1252 unsigned int this_copies = elt->n_copies + parent_copies;
1254 /* Consider groups of sub-elements as weighing in favour of
1255 instantiation whatever their size. */
1256 for (group = elt->groups; group ; group = group->sibling)
1257 FOR_EACH_ACTUAL_CHILD (c, group)
1259 c->n_uses += group->n_uses;
1260 c->n_copies += group->n_copies;
1263 for (c = elt->children; c ; c = c->sibling)
1264 decide_instantiation_1 (c, this_uses, this_copies);
1268 /* Compute the size and number of all instantiated elements below ELT.
1269 We will only care about this if the size of the complete structure
1270 fits in a HOST_WIDE_INT, so we don't have to worry about overflow. */
1273 sum_instantiated_sizes (struct sra_elt *elt, unsigned HOST_WIDE_INT *sizep)
1275 if (elt->replacement)
1277 *sizep += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt->type));
1283 unsigned int count = 0;
1285 for (c = elt->children; c ; c = c->sibling)
1286 count += sum_instantiated_sizes (c, sizep);
1292 /* Instantiate fields in ELT->TYPE that are not currently present as
1295 static void instantiate_missing_elements (struct sra_elt *elt);
1298 instantiate_missing_elements_1 (struct sra_elt *elt, tree child, tree type)
1300 struct sra_elt *sub = lookup_element (elt, child, type, INSERT);
1303 if (sub->replacement == NULL)
1304 instantiate_element (sub);
1307 instantiate_missing_elements (sub);
1311 instantiate_missing_elements (struct sra_elt *elt)
1313 tree type = elt->type;
1315 switch (TREE_CODE (type))
1320 for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
1321 if (TREE_CODE (f) == FIELD_DECL)
1323 tree field_type = TREE_TYPE (f);
1325 /* canonicalize_component_ref() unwidens some bit-field
1326 types (not marked as DECL_BIT_FIELD in C++), so we
1327 must do the same, lest we may introduce type
1329 if (INTEGRAL_TYPE_P (field_type)
1330 && DECL_MODE (f) != TYPE_MODE (field_type))
1331 field_type = TREE_TYPE (get_unwidened (build3 (COMPONENT_REF,
1337 instantiate_missing_elements_1 (elt, f, field_type);
1344 tree i, max, subtype;
1346 i = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1347 max = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1348 subtype = TREE_TYPE (type);
1352 instantiate_missing_elements_1 (elt, i, subtype);
1353 if (tree_int_cst_equal (i, max))
1355 i = int_const_binop (PLUS_EXPR, i, integer_one_node, true);
1362 type = TREE_TYPE (type);
1363 instantiate_missing_elements_1 (elt, integer_zero_node, type);
1364 instantiate_missing_elements_1 (elt, integer_one_node, type);
1372 /* Make one pass across an element tree deciding whether to perform block
1373 or element copies. If we decide on element copies, instantiate all
1374 elements. Return true if there are any instantiated sub-elements. */
1377 decide_block_copy (struct sra_elt *elt)
1382 /* We shouldn't be invoked on groups of sub-elements as they must
1383 behave like their parent as far as block copy is concerned. */
1384 gcc_assert (!elt->is_group);
1386 /* If scalarization is disabled, respect it. */
1387 if (elt->cannot_scalarize)
1389 elt->use_block_copy = 1;
1393 fputs ("Scalarization disabled for ", dump_file);
1394 dump_sra_elt_name (dump_file, elt);
1395 fputc ('\n', dump_file);
1398 /* Disable scalarization of sub-elements */
1399 for (c = elt->children; c; c = c->sibling)
1401 c->cannot_scalarize = 1;
1402 decide_block_copy (c);
1405 /* Groups behave like their parent. */
1406 for (c = elt->groups; c; c = c->sibling)
1408 c->cannot_scalarize = 1;
1409 c->use_block_copy = 1;
1415 /* Don't decide if we've no uses. */
1416 if (elt->n_uses == 0 && elt->n_copies == 0)
1419 else if (!elt->is_scalar)
1421 tree size_tree = TYPE_SIZE_UNIT (elt->type);
1422 bool use_block_copy = true;
1424 /* Tradeoffs for COMPLEX types pretty much always make it better
1425 to go ahead and split the components. */
1426 if (TREE_CODE (elt->type) == COMPLEX_TYPE)
1427 use_block_copy = false;
1429 /* Don't bother trying to figure out the rest if the structure is
1430 so large we can't do easy arithmetic. This also forces block
1431 copies for variable sized structures. */
1432 else if (host_integerp (size_tree, 1))
1434 unsigned HOST_WIDE_INT full_size, inst_size = 0;
1435 unsigned int max_size, max_count, inst_count, full_count;
1437 /* If the sra-max-structure-size parameter is 0, then the
1438 user has not overridden the parameter and we can choose a
1439 sensible default. */
1440 max_size = SRA_MAX_STRUCTURE_SIZE
1441 ? SRA_MAX_STRUCTURE_SIZE
1442 : MOVE_RATIO * UNITS_PER_WORD;
1443 max_count = SRA_MAX_STRUCTURE_COUNT
1444 ? SRA_MAX_STRUCTURE_COUNT
1447 full_size = tree_low_cst (size_tree, 1);
1448 full_count = count_type_elements (elt->type, false);
1449 inst_count = sum_instantiated_sizes (elt, &inst_size);
1451 /* ??? What to do here. If there are two fields, and we've only
1452 instantiated one, then instantiating the other is clearly a win.
1453 If there are a large number of fields then the size of the copy
1454 is much more of a factor. */
1456 /* If the structure is small, and we've made copies, go ahead
1457 and instantiate, hoping that the copies will go away. */
1458 if (full_size <= max_size
1459 && (full_count - inst_count) <= max_count
1460 && elt->n_copies > elt->n_uses)
1461 use_block_copy = false;
1462 else if (inst_count * 100 >= full_count * SRA_FIELD_STRUCTURE_RATIO
1463 && inst_size * 100 >= full_size * SRA_FIELD_STRUCTURE_RATIO)
1464 use_block_copy = false;
1466 /* In order to avoid block copy, we have to be able to instantiate
1467 all elements of the type. See if this is possible. */
1469 && (!can_completely_scalarize_p (elt)
1470 || !type_can_instantiate_all_elements (elt->type)))
1471 use_block_copy = true;
1474 elt->use_block_copy = use_block_copy;
1476 /* Groups behave like their parent. */
1477 for (c = elt->groups; c; c = c->sibling)
1478 c->use_block_copy = use_block_copy;
1482 fprintf (dump_file, "Using %s for ",
1483 use_block_copy ? "block-copy" : "element-copy");
1484 dump_sra_elt_name (dump_file, elt);
1485 fputc ('\n', dump_file);
1488 if (!use_block_copy)
1490 instantiate_missing_elements (elt);
1495 any_inst = elt->replacement != NULL;
1497 for (c = elt->children; c ; c = c->sibling)
1498 any_inst |= decide_block_copy (c);
1503 /* Entry point to phase 3. Instantiate scalar replacement variables. */
1506 decide_instantiations (void)
1510 bitmap_head done_head;
1513 /* We cannot clear bits from a bitmap we're iterating over,
1514 so save up all the bits to clear until the end. */
1515 bitmap_initialize (&done_head, &bitmap_default_obstack);
1516 cleared_any = false;
1518 EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1520 tree var = referenced_var (i);
1521 struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1524 decide_instantiation_1 (elt, 0, 0);
1525 if (!decide_block_copy (elt))
1530 bitmap_set_bit (&done_head, i);
1537 bitmap_and_compl_into (sra_candidates, &done_head);
1538 bitmap_and_compl_into (needs_copy_in, &done_head);
1540 bitmap_clear (&done_head);
1542 if (!bitmap_empty_p (sra_candidates))
1543 todoflags |= TODO_update_smt_usage;
1545 mark_set_for_renaming (sra_candidates);
1548 fputc ('\n', dump_file);
1552 /* Phase Four: Update the function to match the replacements created. */
1554 /* Mark all the variables in V_MAY_DEF or V_MUST_DEF operands for STMT for
1555 renaming. This becomes necessary when we modify all of a non-scalar. */
1558 mark_all_v_defs_1 (tree stmt)
1563 update_stmt_if_modified (stmt);
1565 FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_ALL_VIRTUALS)
1567 if (TREE_CODE (sym) == SSA_NAME)
1568 sym = SSA_NAME_VAR (sym);
1569 mark_sym_for_renaming (sym);
1574 /* Mark all the variables in virtual operands in all the statements in
1575 LIST for renaming. */
1578 mark_all_v_defs (tree list)
1580 if (TREE_CODE (list) != STATEMENT_LIST)
1581 mark_all_v_defs_1 (list);
1584 tree_stmt_iterator i;
1585 for (i = tsi_start (list); !tsi_end_p (i); tsi_next (&i))
1586 mark_all_v_defs_1 (tsi_stmt (i));
1590 /* Mark every replacement under ELT with TREE_NO_WARNING. */
1593 mark_no_warning (struct sra_elt *elt)
1595 if (!elt->all_no_warning)
1597 if (elt->replacement)
1598 TREE_NO_WARNING (elt->replacement) = 1;
1602 FOR_EACH_ACTUAL_CHILD (c, elt)
1603 mark_no_warning (c);
1605 elt->all_no_warning = true;
1609 /* Build a single level component reference to ELT rooted at BASE. */
1612 generate_one_element_ref (struct sra_elt *elt, tree base)
1614 switch (TREE_CODE (TREE_TYPE (base)))
1618 tree field = elt->element;
1620 /* Watch out for compatible records with differing field lists. */
1621 if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base)))
1622 field = find_compatible_field (TREE_TYPE (base), field);
1624 return build3 (COMPONENT_REF, elt->type, base, field, NULL);
1628 todoflags |= TODO_update_smt_usage;
1629 if (TREE_CODE (elt->element) == RANGE_EXPR)
1630 return build4 (ARRAY_RANGE_REF, elt->type, base,
1631 TREE_OPERAND (elt->element, 0), NULL, NULL);
1633 return build4 (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
1636 if (elt->element == integer_zero_node)
1637 return build1 (REALPART_EXPR, elt->type, base);
1639 return build1 (IMAGPART_EXPR, elt->type, base);
1646 /* Build a full component reference to ELT rooted at its native variable. */
1649 generate_element_ref (struct sra_elt *elt)
1652 return generate_one_element_ref (elt, generate_element_ref (elt->parent));
1654 return elt->element;
1658 sra_build_assignment (tree dst, tree src)
1660 /* We need TYPE_CANONICAL to compare the types of dst and src
1661 efficiently, but that's only introduced in GCC 4.3. */
1662 return build2 (MODIFY_EXPR, void_type_node, dst, src);
1665 /* Generate a set of assignment statements in *LIST_P to copy all
1666 instantiated elements under ELT to or from the equivalent structure
1667 rooted at EXPR. COPY_OUT controls the direction of the copy, with
1668 true meaning to copy out of EXPR into ELT. */
1671 generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
1677 if (!copy_out && TREE_CODE (expr) == SSA_NAME
1678 && TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
1682 c = lookup_element (elt, integer_zero_node, NULL, NO_INSERT);
1684 c = lookup_element (elt, integer_one_node, NULL, NO_INSERT);
1687 t = build2 (COMPLEX_EXPR, elt->type, r, i);
1688 t = sra_build_assignment (expr, t);
1689 SSA_NAME_DEF_STMT (expr) = t;
1690 append_to_statement_list (t, list_p);
1692 else if (elt->replacement)
1695 t = sra_build_assignment (elt->replacement, expr);
1697 t = sra_build_assignment (expr, elt->replacement);
1698 append_to_statement_list (t, list_p);
1702 FOR_EACH_ACTUAL_CHILD (c, elt)
1704 t = generate_one_element_ref (c, unshare_expr (expr));
1705 generate_copy_inout (c, copy_out, t, list_p);
1710 /* Generate a set of assignment statements in *LIST_P to copy all instantiated
1711 elements under SRC to their counterparts under DST. There must be a 1-1
1712 correspondence of instantiated elements. */
1715 generate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p)
1717 struct sra_elt *dc, *sc;
1719 FOR_EACH_ACTUAL_CHILD (dc, dst)
1721 sc = lookup_element (src, dc->element, NULL, NO_INSERT);
1723 generate_element_copy (dc, sc, list_p);
1726 if (dst->replacement)
1730 gcc_assert (src->replacement);
1732 t = sra_build_assignment (dst->replacement, src->replacement);
1733 append_to_statement_list (t, list_p);
1737 /* Generate a set of assignment statements in *LIST_P to zero all instantiated
1738 elements under ELT. In addition, do not assign to elements that have been
1739 marked VISITED but do reset the visited flag; this allows easy coordination
1740 with generate_element_init. */
1743 generate_element_zero (struct sra_elt *elt, tree *list_p)
1749 elt->visited = false;
1753 FOR_EACH_ACTUAL_CHILD (c, elt)
1754 generate_element_zero (c, list_p);
1756 if (elt->replacement)
1760 gcc_assert (elt->is_scalar);
1761 t = fold_convert (elt->type, integer_zero_node);
1763 t = sra_build_assignment (elt->replacement, t);
1764 append_to_statement_list (t, list_p);
1768 /* Generate an assignment VAR = INIT, where INIT may need gimplification.
1769 Add the result to *LIST_P. */
1772 generate_one_element_init (tree var, tree init, tree *list_p)
1774 /* The replacement can be almost arbitrarily complex. Gimplify. */
1775 tree stmt = sra_build_assignment (var, init);
1776 gimplify_and_add (stmt, list_p);
1779 /* Generate a set of assignment statements in *LIST_P to set all instantiated
1780 elements under ELT with the contents of the initializer INIT. In addition,
1781 mark all assigned elements VISITED; this allows easy coordination with
1782 generate_element_zero. Return false if we found a case we couldn't
1786 generate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p)
1789 enum tree_code init_code;
1790 struct sra_elt *sub;
1792 unsigned HOST_WIDE_INT idx;
1793 tree value, purpose;
1795 /* We can be passed DECL_INITIAL of a static variable. It might have a
1796 conversion, which we strip off here. */
1797 STRIP_USELESS_TYPE_CONVERSION (init);
1798 init_code = TREE_CODE (init);
1802 if (elt->replacement)
1804 generate_one_element_init (elt->replacement, init, list_p);
1805 elt->visited = true;
1814 FOR_EACH_ACTUAL_CHILD (sub, elt)
1816 if (sub->element == integer_zero_node)
1817 t = (init_code == COMPLEX_EXPR
1818 ? TREE_OPERAND (init, 0) : TREE_REALPART (init));
1820 t = (init_code == COMPLEX_EXPR
1821 ? TREE_OPERAND (init, 1) : TREE_IMAGPART (init));
1822 result &= generate_element_init_1 (sub, t, list_p);
1827 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, purpose, value)
1829 if (TREE_CODE (purpose) == RANGE_EXPR)
1831 tree lower = TREE_OPERAND (purpose, 0);
1832 tree upper = TREE_OPERAND (purpose, 1);
1836 sub = lookup_element (elt, lower, NULL, NO_INSERT);
1838 result &= generate_element_init_1 (sub, value, list_p);
1839 if (tree_int_cst_equal (lower, upper))
1841 lower = int_const_binop (PLUS_EXPR, lower,
1842 integer_one_node, true);
1847 sub = lookup_element (elt, purpose, NULL, NO_INSERT);
1849 result &= generate_element_init_1 (sub, value, list_p);
1855 elt->visited = true;
1862 /* A wrapper function for generate_element_init_1 that handles cleanup after
1866 generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
1870 push_gimplify_context ();
1871 ret = generate_element_init_1 (elt, init, list_p);
1872 pop_gimplify_context (NULL);
1874 /* The replacement can expose previously unreferenced variables. */
1877 tree_stmt_iterator i;
1879 for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i))
1880 find_new_referenced_vars (tsi_stmt_ptr (i));
1886 /* Insert STMT on all the outgoing edges out of BB. Note that if BB
1887 has more than one edge, STMT will be replicated for each edge. Also,
1888 abnormal edges will be ignored. */
1891 insert_edge_copies (tree stmt, basic_block bb)
1898 FOR_EACH_EDGE (e, ei, bb->succs)
1900 /* We don't need to insert copies on abnormal edges. The
1901 value of the scalar replacement is not guaranteed to
1902 be valid through an abnormal edge. */
1903 if (!(e->flags & EDGE_ABNORMAL))
1907 bsi_insert_on_edge (e, stmt);
1911 bsi_insert_on_edge (e, unsave_expr_now (stmt));
1916 /* Helper function to insert LIST before BSI, and set up line number info. */
1919 sra_insert_before (block_stmt_iterator *bsi, tree list)
1921 tree stmt = bsi_stmt (*bsi);
1923 if (EXPR_HAS_LOCATION (stmt))
1924 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1925 bsi_insert_before (bsi, list, BSI_SAME_STMT);
1928 /* Similarly, but insert after BSI. Handles insertion onto edges as well. */
1931 sra_insert_after (block_stmt_iterator *bsi, tree list)
1933 tree stmt = bsi_stmt (*bsi);
1935 if (EXPR_HAS_LOCATION (stmt))
1936 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1938 if (stmt_ends_bb_p (stmt))
1939 insert_edge_copies (list, bsi->bb);
1941 bsi_insert_after (bsi, list, BSI_SAME_STMT);
1944 /* Similarly, but replace the statement at BSI. */
1947 sra_replace (block_stmt_iterator *bsi, tree list)
1949 sra_insert_before (bsi, list);
1950 bsi_remove (bsi, false);
1951 if (bsi_end_p (*bsi))
1952 *bsi = bsi_last (bsi->bb);
1957 /* Scalarize a USE. To recap, this is either a simple reference to ELT,
1958 if elt is scalar, or some occurrence of ELT that requires a complete
1959 aggregate. IS_OUTPUT is true if ELT is being modified. */
1962 scalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi,
1963 bool is_output, bool use_all)
1965 tree list = NULL, stmt = bsi_stmt (*bsi);
1967 if (elt->replacement)
1969 /* If we have a replacement, then updating the reference is as
1970 simple as modifying the existing statement in place. */
1972 mark_all_v_defs (stmt);
1973 *expr_p = elt->replacement;
1978 /* Otherwise we need some copies. If ELT is being read, then we want
1979 to store all (modified) sub-elements back into the structure before
1980 the reference takes place. If ELT is being written, then we want to
1981 load the changed values back into our shadow variables. */
1982 /* ??? We don't check modified for reads, we just always write all of
1983 the values. We should be able to record the SSA number of the VOP
1984 for which the values were last read. If that number matches the
1985 SSA number of the VOP in the current statement, then we needn't
1986 emit an assignment. This would also eliminate double writes when
1987 a structure is passed as more than one argument to a function call.
1988 This optimization would be most effective if sra_walk_function
1989 processed the blocks in dominator order. */
1991 generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
1994 mark_all_v_defs (list);
1996 sra_insert_after (bsi, list);
1999 sra_insert_before (bsi, list);
2001 mark_no_warning (elt);
2006 /* Scalarize a COPY. To recap, this is an assignment statement between
2007 two scalarizable references, LHS_ELT and RHS_ELT. */
2010 scalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
2011 block_stmt_iterator *bsi)
2015 if (lhs_elt->replacement && rhs_elt->replacement)
2017 /* If we have two scalar operands, modify the existing statement. */
2018 stmt = bsi_stmt (*bsi);
2020 /* See the commentary in sra_walk_function concerning
2021 RETURN_EXPR, and why we should never see one here. */
2022 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
2024 TREE_OPERAND (stmt, 0) = lhs_elt->replacement;
2025 TREE_OPERAND (stmt, 1) = rhs_elt->replacement;
2028 else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
2030 /* If either side requires a block copy, then sync the RHS back
2031 to the original structure, leave the original assignment
2032 statement (which will perform the block copy), then load the
2033 LHS values out of its now-updated original structure. */
2034 /* ??? Could perform a modified pair-wise element copy. That
2035 would at least allow those elements that are instantiated in
2036 both structures to be optimized well. */
2039 generate_copy_inout (rhs_elt, false,
2040 generate_element_ref (rhs_elt), &list);
2043 mark_all_v_defs (list);
2044 sra_insert_before (bsi, list);
2048 generate_copy_inout (lhs_elt, true,
2049 generate_element_ref (lhs_elt), &list);
2052 mark_all_v_defs (list);
2053 sra_insert_after (bsi, list);
2058 /* Otherwise both sides must be fully instantiated. In which
2059 case perform pair-wise element assignments and replace the
2060 original block copy statement. */
2062 stmt = bsi_stmt (*bsi);
2063 mark_all_v_defs (stmt);
2066 generate_element_copy (lhs_elt, rhs_elt, &list);
2068 mark_all_v_defs (list);
2069 sra_replace (bsi, list);
2073 /* Scalarize an INIT. To recap, this is an assignment to a scalarizable
2074 reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
2075 COMPLEX_EXPR. If RHS is NULL, it should be treated as an empty
2079 scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
2084 /* Generate initialization statements for all members extant in the RHS. */
2087 /* Unshare the expression just in case this is from a decl's initial. */
2088 rhs = unshare_expr (rhs);
2089 result = generate_element_init (lhs_elt, rhs, &list);
2092 /* CONSTRUCTOR is defined such that any member not mentioned is assigned
2093 a zero value. Initialize the rest of the instantiated elements. */
2094 generate_element_zero (lhs_elt, &list);
2098 /* If we failed to convert the entire initializer, then we must
2099 leave the structure assignment in place and must load values
2100 from the structure into the slots for which we did not find
2101 constants. The easiest way to do this is to generate a complete
2102 copy-out, and then follow that with the constant assignments
2103 that we were able to build. DCE will clean things up. */
2105 generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
2107 append_to_statement_list (list, &list0);
2111 if (lhs_elt->use_block_copy || !result)
2113 /* Since LHS is not fully instantiated, we must leave the structure
2114 assignment in place. Treating this case differently from a USE
2115 exposes constants to later optimizations. */
2118 mark_all_v_defs (list);
2119 sra_insert_after (bsi, list);
2124 /* The LHS is fully instantiated. The list of initializations
2125 replaces the original structure assignment. */
2127 mark_all_v_defs (bsi_stmt (*bsi));
2128 mark_all_v_defs (list);
2129 sra_replace (bsi, list);
2133 /* A subroutine of scalarize_ldst called via walk_tree. Set TREE_NO_TRAP
2134 on all INDIRECT_REFs. */
2137 mark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2141 if (TREE_CODE (t) == INDIRECT_REF)
2143 TREE_THIS_NOTRAP (t) = 1;
2146 else if (IS_TYPE_OR_DECL_P (t))
2152 /* Scalarize a LDST. To recap, this is an assignment between one scalarizable
2153 reference ELT and one non-scalarizable reference OTHER. IS_OUTPUT is true
2154 if ELT is on the left-hand side. */
2157 scalarize_ldst (struct sra_elt *elt, tree other,
2158 block_stmt_iterator *bsi, bool is_output)
2160 /* Shouldn't have gotten called for a scalar. */
2161 gcc_assert (!elt->replacement);
2163 if (elt->use_block_copy)
2165 /* Since ELT is not fully instantiated, we have to leave the
2166 block copy in place. Treat this as a USE. */
2167 scalarize_use (elt, NULL, bsi, is_output, false);
2171 /* The interesting case is when ELT is fully instantiated. In this
2172 case we can have each element stored/loaded directly to/from the
2173 corresponding slot in OTHER. This avoids a block copy. */
2175 tree list = NULL, stmt = bsi_stmt (*bsi);
2177 mark_all_v_defs (stmt);
2178 generate_copy_inout (elt, is_output, other, &list);
2179 mark_all_v_defs (list);
2182 /* Preserve EH semantics. */
2183 if (stmt_ends_bb_p (stmt))
2185 tree_stmt_iterator tsi;
2188 /* Extract the first statement from LIST. */
2189 tsi = tsi_start (list);
2190 first = tsi_stmt (tsi);
2193 /* Replace the old statement with this new representative. */
2194 bsi_replace (bsi, first, true);
2196 if (!tsi_end_p (tsi))
2198 /* If any reference would trap, then they all would. And more
2199 to the point, the first would. Therefore none of the rest
2200 will trap since the first didn't. Indicate this by
2201 iterating over the remaining statements and set
2202 TREE_THIS_NOTRAP in all INDIRECT_REFs. */
2205 walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL);
2208 while (!tsi_end_p (tsi));
2210 insert_edge_copies (list, bsi->bb);
2214 sra_replace (bsi, list);
2218 /* Generate initializations for all scalarizable parameters. */
2221 scalarize_parms (void)
2227 EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi)
2229 tree var = referenced_var (i);
2230 struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
2231 generate_copy_inout (elt, true, var, &list);
2236 insert_edge_copies (list, ENTRY_BLOCK_PTR);
2237 mark_all_v_defs (list);
2241 /* Entry point to phase 4. Update the function to match replacements. */
2244 scalarize_function (void)
2246 static const struct sra_walk_fns fns = {
2247 scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false
2250 sra_walk_function (&fns);
2252 bsi_commit_edge_inserts ();
2256 /* Debug helper function. Print ELT in a nice human-readable format. */
2259 dump_sra_elt_name (FILE *f, struct sra_elt *elt)
2261 if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
2263 fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f);
2264 dump_sra_elt_name (f, elt->parent);
2269 dump_sra_elt_name (f, elt->parent);
2270 if (DECL_P (elt->element))
2272 if (TREE_CODE (elt->element) == FIELD_DECL)
2274 print_generic_expr (f, elt->element, dump_flags);
2276 else if (TREE_CODE (elt->element) == RANGE_EXPR)
2277 fprintf (f, "["HOST_WIDE_INT_PRINT_DEC".."HOST_WIDE_INT_PRINT_DEC"]",
2278 TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 0)),
2279 TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 1)));
2281 fprintf (f, "[" HOST_WIDE_INT_PRINT_DEC "]",
2282 TREE_INT_CST_LOW (elt->element));
2286 /* Likewise, but callable from the debugger. */
2289 debug_sra_elt_name (struct sra_elt *elt)
2291 dump_sra_elt_name (stderr, elt);
2292 fputc ('\n', stderr);
2296 sra_init_cache (void)
2298 if (sra_type_decomp_cache)
2301 sra_type_decomp_cache = BITMAP_ALLOC (NULL);
2302 sra_type_inst_cache = BITMAP_ALLOC (NULL);
2305 /* Main entry point. */
2310 /* Initialize local variables. */
2312 gcc_obstack_init (&sra_obstack);
2313 sra_candidates = BITMAP_ALLOC (NULL);
2314 needs_copy_in = BITMAP_ALLOC (NULL);
2316 sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, NULL);
2318 /* Scan. If we find anything, instantiate and scalarize. */
2319 if (find_candidates_for_sra ())
2322 decide_instantiations ();
2323 scalarize_function ();
2326 /* Free allocated memory. */
2327 htab_delete (sra_map);
2329 BITMAP_FREE (sra_candidates);
2330 BITMAP_FREE (needs_copy_in);
2331 BITMAP_FREE (sra_type_decomp_cache);
2332 BITMAP_FREE (sra_type_inst_cache);
2333 obstack_free (&sra_obstack, NULL);
2340 return flag_tree_sra != 0;
2343 struct tree_opt_pass pass_sra =
2346 gate_sra, /* gate */
2347 tree_sra, /* execute */
2350 0, /* static_pass_number */
2351 TV_TREE_SRA, /* tv_id */
2352 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2353 0, /* properties_provided */
2354 PROP_smt_usage, /* properties_destroyed */
2355 0, /* todo_flags_start */
2356 TODO_dump_func /* todo_flags_finish */
2358 | TODO_ggc_collect | TODO_verify_ssa,