1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 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 COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
82 #include "tree-flow.h"
84 #include "diagnostic.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 /* Enumeration of all aggregate reductions we can do. */
93 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
94 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
95 SRA_MODE_INTRA }; /* late intraprocedural SRA */
97 /* Global variable describing which aggregate reduction we are performing at
99 static enum sra_mode sra_mode;
103 /* ACCESS represents each access to an aggregate variable (as a whole or a
104 part). It can also represent a group of accesses that refer to exactly the
105 same fragment of an aggregate (i.e. those that have exactly the same offset
106 and size). Such representatives for a single aggregate, once determined,
107 are linked in a linked list and have the group fields set.
109 Moreover, when doing intraprocedural SRA, a tree is built from those
110 representatives (by the means of first_child and next_sibling pointers), in
111 which all items in a subtree are "within" the root, i.e. their offset is
112 greater or equal to offset of the root and offset+size is smaller or equal
113 to offset+size of the root. Children of an access are sorted by offset.
115 Note that accesses to parts of vector and complex number types always
116 represented by an access to the whole complex number or a vector. It is a
117 duty of the modifying functions to replace them appropriately. */
121 /* Values returned by `get_ref_base_and_extent' for each component reference
122 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
123 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
124 HOST_WIDE_INT offset;
128 /* Expression. It is context dependent so do not use it to create new
129 expressions to access the original aggregate. See PR 42154 for a
135 /* The statement this access belongs to. */
138 /* Next group representative for this aggregate. */
139 struct access *next_grp;
141 /* Pointer to the group representative. Pointer to itself if the struct is
142 the representative. */
143 struct access *group_representative;
145 /* If this access has any children (in terms of the definition above), this
146 points to the first one. */
147 struct access *first_child;
149 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
150 described above. In IPA-SRA this is a pointer to the next access
151 belonging to the same group (having the same representative). */
152 struct access *next_sibling;
154 /* Pointers to the first and last element in the linked list of assign
156 struct assign_link *first_link, *last_link;
158 /* Pointer to the next access in the work queue. */
159 struct access *next_queued;
161 /* Replacement variable for this access "region." Never to be accessed
162 directly, always only by the means of get_access_replacement() and only
163 when grp_to_be_replaced flag is set. */
164 tree replacement_decl;
166 /* Is this particular access write access? */
169 /* Is this access currently in the work queue? */
170 unsigned grp_queued : 1;
172 /* Does this group contain a write access? This flag is propagated down the
174 unsigned grp_write : 1;
176 /* Does this group contain a read access? This flag is propagated down the
178 unsigned grp_read : 1;
180 /* Other passes of the analysis use this bit to make function
181 analyze_access_subtree create scalar replacements for this group if
183 unsigned grp_hint : 1;
185 /* Is the subtree rooted in this access fully covered by scalar
187 unsigned grp_covered : 1;
189 /* If set to true, this access and all below it in an access tree must not be
191 unsigned grp_unscalarizable_region : 1;
193 /* Whether data have been written to parts of the aggregate covered by this
194 access which is not to be scalarized. This flag is propagated up in the
196 unsigned grp_unscalarized_data : 1;
198 /* Does this access and/or group contain a write access through a
200 unsigned grp_partial_lhs : 1;
202 /* Set when a scalar replacement should be created for this variable. We do
203 the decision and creation at different places because create_tmp_var
204 cannot be called from within FOR_EACH_REFERENCED_VAR. */
205 unsigned grp_to_be_replaced : 1;
207 /* Is it possible that the group refers to data which might be (directly or
208 otherwise) modified? */
209 unsigned grp_maybe_modified : 1;
211 /* Set when this is a representative of a pointer to scalar (i.e. by
212 reference) parameter which we consider for turning into a plain scalar
213 (i.e. a by value parameter). */
214 unsigned grp_scalar_ptr : 1;
216 /* Set when we discover that this pointer is not safe to dereference in the
218 unsigned grp_not_necessarilly_dereferenced : 1;
221 typedef struct access *access_p;
223 DEF_VEC_P (access_p);
224 DEF_VEC_ALLOC_P (access_p, heap);
226 /* Alloc pool for allocating access structures. */
227 static alloc_pool access_pool;
229 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
230 are used to propagate subaccesses from rhs to lhs as long as they don't
231 conflict with what is already there. */
234 struct access *lacc, *racc;
235 struct assign_link *next;
238 /* Alloc pool for allocating assign link structures. */
239 static alloc_pool link_pool;
241 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
242 static struct pointer_map_t *base_access_vec;
244 /* Bitmap of candidates. */
245 static bitmap candidate_bitmap;
247 /* Obstack for creation of fancy names. */
248 static struct obstack name_obstack;
250 /* Head of a linked list of accesses that need to have its subaccesses
251 propagated to their assignment counterparts. */
252 static struct access *work_queue_head;
254 /* Number of parameters of the analyzed function when doing early ipa SRA. */
255 static int func_param_count;
257 /* scan_function sets the following to true if it encounters a call to
258 __builtin_apply_args. */
259 static bool encountered_apply_args;
261 /* Set by scan_function when it finds a recursive call. */
262 static bool encountered_recursive_call;
264 /* Set by scan_function when it finds a recursive call with less actual
265 arguments than formal parameters.. */
266 static bool encountered_unchangable_recursive_call;
268 /* This is a table in which for each basic block and parameter there is a
269 distance (offset + size) in that parameter which is dereferenced and
270 accessed in that BB. */
271 static HOST_WIDE_INT *bb_dereferences;
272 /* Bitmap of BBs that can cause the function to "stop" progressing by
273 returning, throwing externally, looping infinitely or calling a function
274 which might abort etc.. */
275 static bitmap final_bbs;
277 /* Representative of no accesses at all. */
278 static struct access no_accesses_representant;
280 /* Predicate to test the special value. */
283 no_accesses_p (struct access *access)
285 return access == &no_accesses_representant;
288 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
289 representative fields are dumped, otherwise those which only describe the
290 individual access are. */
294 /* Number of processed aggregates is readily available in
295 analyze_all_variable_accesses and so is not stored here. */
297 /* Number of created scalar replacements. */
300 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
304 /* Number of statements created by generate_subtree_copies. */
307 /* Number of statements created by load_assign_lhs_subreplacements. */
310 /* Number of times sra_modify_assign has deleted a statement. */
313 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
314 RHS reparately due to type conversions or nonexistent matching
316 int separate_lhs_rhs_handling;
318 /* Number of parameters that were removed because they were unused. */
319 int deleted_unused_parameters;
321 /* Number of scalars passed as parameters by reference that have been
322 converted to be passed by value. */
323 int scalar_by_ref_to_by_val;
325 /* Number of aggregate parameters that were replaced by one or more of their
327 int aggregate_params_reduced;
329 /* Numbber of components created when splitting aggregate parameters. */
330 int param_reductions_created;
334 dump_access (FILE *f, struct access *access, bool grp)
336 fprintf (f, "access { ");
337 fprintf (f, "base = (%d)'", DECL_UID (access->base));
338 print_generic_expr (f, access->base, 0);
339 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
340 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
341 fprintf (f, ", expr = ");
342 print_generic_expr (f, access->expr, 0);
343 fprintf (f, ", type = ");
344 print_generic_expr (f, access->type, 0);
346 fprintf (f, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
347 "grp_covered = %d, grp_unscalarizable_region = %d, "
348 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
349 "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
350 "grp_not_necessarilly_dereferenced = %d\n",
351 access->grp_write, access->grp_read, access->grp_hint,
352 access->grp_covered, access->grp_unscalarizable_region,
353 access->grp_unscalarized_data, access->grp_partial_lhs,
354 access->grp_to_be_replaced, access->grp_maybe_modified,
355 access->grp_not_necessarilly_dereferenced);
357 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
358 access->grp_partial_lhs);
361 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
364 dump_access_tree_1 (FILE *f, struct access *access, int level)
370 for (i = 0; i < level; i++)
371 fputs ("* ", dump_file);
373 dump_access (f, access, true);
375 if (access->first_child)
376 dump_access_tree_1 (f, access->first_child, level + 1);
378 access = access->next_sibling;
383 /* Dump all access trees for a variable, given the pointer to the first root in
387 dump_access_tree (FILE *f, struct access *access)
389 for (; access; access = access->next_grp)
390 dump_access_tree_1 (f, access, 0);
393 /* Return true iff ACC is non-NULL and has subaccesses. */
396 access_has_children_p (struct access *acc)
398 return acc && acc->first_child;
401 /* Return a vector of pointers to accesses for the variable given in BASE or
402 NULL if there is none. */
404 static VEC (access_p, heap) *
405 get_base_access_vector (tree base)
409 slot = pointer_map_contains (base_access_vec, base);
413 return *(VEC (access_p, heap) **) slot;
416 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
417 in ACCESS. Return NULL if it cannot be found. */
419 static struct access *
420 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
423 while (access && (access->offset != offset || access->size != size))
425 struct access *child = access->first_child;
427 while (child && (child->offset + child->size <= offset))
428 child = child->next_sibling;
435 /* Return the first group representative for DECL or NULL if none exists. */
437 static struct access *
438 get_first_repr_for_decl (tree base)
440 VEC (access_p, heap) *access_vec;
442 access_vec = get_base_access_vector (base);
446 return VEC_index (access_p, access_vec, 0);
449 /* Find an access representative for the variable BASE and given OFFSET and
450 SIZE. Requires that access trees have already been built. Return NULL if
451 it cannot be found. */
453 static struct access *
454 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
457 struct access *access;
459 access = get_first_repr_for_decl (base);
460 while (access && (access->offset + access->size <= offset))
461 access = access->next_grp;
465 return find_access_in_subtree (access, offset, size);
468 /* Add LINK to the linked list of assign links of RACC. */
470 add_link_to_rhs (struct access *racc, struct assign_link *link)
472 gcc_assert (link->racc == racc);
474 if (!racc->first_link)
476 gcc_assert (!racc->last_link);
477 racc->first_link = link;
480 racc->last_link->next = link;
482 racc->last_link = link;
486 /* Move all link structures in their linked list in OLD_RACC to the linked list
489 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
491 if (!old_racc->first_link)
493 gcc_assert (!old_racc->last_link);
497 if (new_racc->first_link)
499 gcc_assert (!new_racc->last_link->next);
500 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
502 new_racc->last_link->next = old_racc->first_link;
503 new_racc->last_link = old_racc->last_link;
507 gcc_assert (!new_racc->last_link);
509 new_racc->first_link = old_racc->first_link;
510 new_racc->last_link = old_racc->last_link;
512 old_racc->first_link = old_racc->last_link = NULL;
515 /* Add ACCESS to the work queue (which is actually a stack). */
518 add_access_to_work_queue (struct access *access)
520 if (!access->grp_queued)
522 gcc_assert (!access->next_queued);
523 access->next_queued = work_queue_head;
524 access->grp_queued = 1;
525 work_queue_head = access;
529 /* Pop an access from the work queue, and return it, assuming there is one. */
531 static struct access *
532 pop_access_from_work_queue (void)
534 struct access *access = work_queue_head;
536 work_queue_head = access->next_queued;
537 access->next_queued = NULL;
538 access->grp_queued = 0;
543 /* Allocate necessary structures. */
546 sra_initialize (void)
548 candidate_bitmap = BITMAP_ALLOC (NULL);
549 gcc_obstack_init (&name_obstack);
550 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
551 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
552 base_access_vec = pointer_map_create ();
553 memset (&sra_stats, 0, sizeof (sra_stats));
554 encountered_apply_args = false;
555 encountered_recursive_call = false;
556 encountered_unchangable_recursive_call = false;
559 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
562 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
563 void *data ATTRIBUTE_UNUSED)
565 VEC (access_p, heap) *access_vec;
566 access_vec = (VEC (access_p, heap) *) *value;
567 VEC_free (access_p, heap, access_vec);
572 /* Deallocate all general structures. */
575 sra_deinitialize (void)
577 BITMAP_FREE (candidate_bitmap);
578 free_alloc_pool (access_pool);
579 free_alloc_pool (link_pool);
580 obstack_free (&name_obstack, NULL);
582 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
583 pointer_map_destroy (base_access_vec);
586 /* Remove DECL from candidates for SRA and write REASON to the dump file if
589 disqualify_candidate (tree decl, const char *reason)
591 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
593 if (dump_file && (dump_flags & TDF_DETAILS))
595 fprintf (dump_file, "! Disqualifying ");
596 print_generic_expr (dump_file, decl, 0);
597 fprintf (dump_file, " - %s\n", reason);
601 /* Return true iff the type contains a field or an element which does not allow
605 type_internals_preclude_sra_p (tree type)
610 switch (TREE_CODE (type))
614 case QUAL_UNION_TYPE:
615 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
616 if (TREE_CODE (fld) == FIELD_DECL)
618 tree ft = TREE_TYPE (fld);
620 if (TREE_THIS_VOLATILE (fld)
621 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
622 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
623 || !host_integerp (DECL_SIZE (fld), 1))
626 if (AGGREGATE_TYPE_P (ft)
627 && type_internals_preclude_sra_p (ft))
634 et = TREE_TYPE (type);
636 if (AGGREGATE_TYPE_P (et))
637 return type_internals_preclude_sra_p (et);
646 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
647 base variable if it is. Return T if it is not an SSA_NAME. */
650 get_ssa_base_param (tree t)
652 if (TREE_CODE (t) == SSA_NAME)
654 if (SSA_NAME_IS_DEFAULT_DEF (t))
655 return SSA_NAME_VAR (t);
662 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
663 belongs to, unless the BB has already been marked as a potentially
667 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
669 basic_block bb = gimple_bb (stmt);
670 int idx, parm_index = 0;
673 if (bitmap_bit_p (final_bbs, bb->index))
676 for (parm = DECL_ARGUMENTS (current_function_decl);
677 parm && parm != base;
678 parm = TREE_CHAIN (parm))
681 gcc_assert (parm_index < func_param_count);
683 idx = bb->index * func_param_count + parm_index;
684 if (bb_dereferences[idx] < dist)
685 bb_dereferences[idx] = dist;
688 /* Create and insert access for EXPR. Return created access, or NULL if it is
691 static struct access *
692 create_access (tree expr, gimple stmt, bool write)
694 struct access *access;
696 VEC (access_p,heap) *vec;
697 HOST_WIDE_INT offset, size, max_size;
699 bool ptr, unscalarizable_region = false;
701 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
703 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
705 base = get_ssa_base_param (TREE_OPERAND (base, 0));
713 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
716 if (sra_mode == SRA_MODE_EARLY_IPA)
718 if (size < 0 || size != max_size)
720 disqualify_candidate (base, "Encountered a variable sized access.");
723 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
725 disqualify_candidate (base,
726 "Encountered an acces not aligned to a byte.");
731 mark_parm_dereference (base, offset + size, stmt);
735 if (size != max_size)
738 unscalarizable_region = true;
742 disqualify_candidate (base, "Encountered an unconstrained access.");
747 access = (struct access *) pool_alloc (access_pool);
748 memset (access, 0, sizeof (struct access));
751 access->offset = offset;
754 access->type = TREE_TYPE (expr);
755 access->write = write;
756 access->grp_unscalarizable_region = unscalarizable_region;
759 slot = pointer_map_contains (base_access_vec, base);
761 vec = (VEC (access_p, heap) *) *slot;
763 vec = VEC_alloc (access_p, heap, 32);
765 VEC_safe_push (access_p, heap, vec, access);
767 *((struct VEC (access_p,heap) **)
768 pointer_map_insert (base_access_vec, base)) = vec;
774 /* Search the given tree for a declaration by skipping handled components and
775 exclude it from the candidates. */
778 disqualify_base_of_expr (tree t, const char *reason)
780 while (handled_component_p (t))
781 t = TREE_OPERAND (t, 0);
783 if (sra_mode == SRA_MODE_EARLY_IPA)
785 if (INDIRECT_REF_P (t))
786 t = TREE_OPERAND (t, 0);
787 t = get_ssa_base_param (t);
791 disqualify_candidate (t, reason);
794 /* Scan expression EXPR and create access structures for all accesses to
795 candidates for scalarization. Return the created access or NULL if none is
798 static struct access *
799 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
801 struct access *ret = NULL;
802 tree expr = *expr_ptr;
805 if (TREE_CODE (expr) == BIT_FIELD_REF
806 || TREE_CODE (expr) == IMAGPART_EXPR
807 || TREE_CODE (expr) == REALPART_EXPR)
809 expr = TREE_OPERAND (expr, 0);
815 /* We need to dive through V_C_Es in order to get the size of its parameter
816 and not the result type. Ada produces such statements. We are also
817 capable of handling the topmost V_C_E but not any of those buried in other
818 handled components. */
819 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
820 expr = TREE_OPERAND (expr, 0);
822 if (contains_view_convert_expr_p (expr))
824 disqualify_base_of_expr (expr, "V_C_E under a different handled "
829 switch (TREE_CODE (expr))
832 if (sra_mode != SRA_MODE_EARLY_IPA)
840 case ARRAY_RANGE_REF:
841 ret = create_access (expr, stmt, write);
848 if (write && partial_ref && ret)
849 ret->grp_partial_lhs = 1;
854 /* Callback of scan_function. Scan expression EXPR and create access
855 structures for all accesses to candidates for scalarization. Return true if
856 any access has been inserted. */
859 build_access_from_expr (tree *expr_ptr,
860 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
861 void *data ATTRIBUTE_UNUSED)
863 return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
866 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
867 modes in which it matters, return true iff they have been disqualified. RHS
868 may be NULL, in that case ignore it. If we scalarize an aggregate in
869 intra-SRA we may need to add statements after each statement. This is not
870 possible if a statement unconditionally has to end the basic block. */
872 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
874 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
875 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
877 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
879 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
886 /* Result code for scan_assign callback for scan_function. */
887 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
888 SRA_SA_PROCESSED, /* stmt analyzed/changed */
889 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
892 /* Callback of scan_function. Scan expressions occuring in the statement
893 pointed to by STMT_EXPR, create access structures for all accesses to
894 candidates for scalarization and remove those candidates which occur in
895 statements or expressions that prevent them from being split apart. Return
896 true if any access has been inserted. */
898 static enum scan_assign_result
899 build_accesses_from_assign (gimple *stmt_ptr,
900 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
901 void *data ATTRIBUTE_UNUSED)
903 gimple stmt = *stmt_ptr;
904 tree *lhs_ptr, *rhs_ptr;
905 struct access *lacc, *racc;
907 if (!gimple_assign_single_p (stmt))
910 lhs_ptr = gimple_assign_lhs_ptr (stmt);
911 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
913 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
916 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
917 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
920 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
921 && !lacc->grp_unscalarizable_region
922 && !racc->grp_unscalarizable_region
923 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
924 /* FIXME: Turn the following line into an assert after PR 40058 is
926 && lacc->size == racc->size
927 && useless_type_conversion_p (lacc->type, racc->type))
929 struct assign_link *link;
931 link = (struct assign_link *) pool_alloc (link_pool);
932 memset (link, 0, sizeof (struct assign_link));
937 add_link_to_rhs (racc, link);
940 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
943 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
944 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
947 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
948 void *data ATTRIBUTE_UNUSED)
951 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
956 /* Return true iff callsite CALL has at least as many actual arguments as there
957 are formal parameters of the function currently processed by IPA-SRA. */
960 callsite_has_enough_arguments_p (gimple call)
962 return gimple_call_num_args (call) >= (unsigned) func_param_count;
965 /* Scan function and look for interesting statements. Return true if any has
966 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
967 called on all expressions within statements except assign statements and
968 those deemed entirely unsuitable for some reason (all operands in such
969 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
970 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
971 called on assign statements and those call statements which have a lhs, it
972 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
973 pass and thus no statement is being modified. DATA is a pointer passed to
974 all callbacks. If any single callback returns true, this function also
975 returns true, otherwise it returns false. */
978 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
979 enum scan_assign_result (*scan_assign) (gimple *,
980 gimple_stmt_iterator *,
982 bool (*handle_ssa_defs)(gimple, void *),
983 bool analysis_stage, void *data)
985 gimple_stmt_iterator gsi;
993 bool bb_changed = false;
996 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
997 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
999 gsi = gsi_start_bb (bb);
1000 while (!gsi_end_p (gsi))
1002 gimple stmt = gsi_stmt (gsi);
1003 enum scan_assign_result assign_result;
1004 bool any = false, deleted = false;
1006 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
1007 bitmap_set_bit (final_bbs, bb->index);
1008 switch (gimple_code (stmt))
1011 t = gimple_return_retval_ptr (stmt);
1012 if (*t != NULL_TREE)
1013 any |= scan_expr (t, &gsi, false, data);
1014 if (analysis_stage && final_bbs)
1015 bitmap_set_bit (final_bbs, bb->index);
1019 assign_result = scan_assign (&stmt, &gsi, data);
1020 any |= assign_result == SRA_SA_PROCESSED;
1021 deleted = assign_result == SRA_SA_REMOVED;
1022 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1023 any |= handle_ssa_defs (stmt, data);
1027 /* Operands must be processed before the lhs. */
1028 for (i = 0; i < gimple_call_num_args (stmt); i++)
1030 tree *argp = gimple_call_arg_ptr (stmt, i);
1031 any |= scan_expr (argp, &gsi, false, data);
1034 if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
1036 tree dest = gimple_call_fndecl (stmt);
1037 int flags = gimple_call_flags (stmt);
1041 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1042 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1043 encountered_apply_args = true;
1044 if (cgraph_get_node (dest)
1045 == cgraph_get_node (current_function_decl))
1047 encountered_recursive_call = true;
1048 if (!callsite_has_enough_arguments_p (stmt))
1049 encountered_unchangable_recursive_call = true;
1054 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1055 bitmap_set_bit (final_bbs, bb->index);
1058 if (gimple_call_lhs (stmt))
1060 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1062 || !disqualify_ops_if_throwing_stmt (stmt,
1065 any |= scan_expr (lhs_ptr, &gsi, true, data);
1066 if (handle_ssa_defs)
1067 any |= handle_ssa_defs (stmt, data);
1075 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1078 bitmap_set_bit (final_bbs, bb->index);
1080 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1082 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1083 any |= scan_expr (op, &gsi, false, data);
1085 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1087 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1088 any |= scan_expr (op, &gsi, true, data);
1100 if (!analysis_stage)
1104 maybe_clean_eh_stmt (stmt);
1115 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1116 gimple_purge_dead_eh_edges (bb);
1122 /* Helper of QSORT function. There are pointers to accesses in the array. An
1123 access is considered smaller than another if it has smaller offset or if the
1124 offsets are the same but is size is bigger. */
1127 compare_access_positions (const void *a, const void *b)
1129 const access_p *fp1 = (const access_p *) a;
1130 const access_p *fp2 = (const access_p *) b;
1131 const access_p f1 = *fp1;
1132 const access_p f2 = *fp2;
1134 if (f1->offset != f2->offset)
1135 return f1->offset < f2->offset ? -1 : 1;
1137 if (f1->size == f2->size)
1139 if (f1->type == f2->type)
1141 /* Put any non-aggregate type before any aggregate type. */
1142 else if (!is_gimple_reg_type (f1->type)
1143 && is_gimple_reg_type (f2->type))
1145 else if (is_gimple_reg_type (f1->type)
1146 && !is_gimple_reg_type (f2->type))
1148 /* Put any complex or vector type before any other scalar type. */
1149 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1150 && TREE_CODE (f1->type) != VECTOR_TYPE
1151 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1152 || TREE_CODE (f2->type) == VECTOR_TYPE))
1154 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1155 || TREE_CODE (f1->type) == VECTOR_TYPE)
1156 && TREE_CODE (f2->type) != COMPLEX_TYPE
1157 && TREE_CODE (f2->type) != VECTOR_TYPE)
1159 /* Put the integral type with the bigger precision first. */
1160 else if (INTEGRAL_TYPE_P (f1->type)
1161 && INTEGRAL_TYPE_P (f2->type))
1162 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1163 /* Put any integral type with non-full precision last. */
1164 else if (INTEGRAL_TYPE_P (f1->type)
1165 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1166 != TYPE_PRECISION (f1->type)))
1168 else if (INTEGRAL_TYPE_P (f2->type)
1169 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1170 != TYPE_PRECISION (f2->type)))
1172 /* Stabilize the sort. */
1173 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1176 /* We want the bigger accesses first, thus the opposite operator in the next
1178 return f1->size > f2->size ? -1 : 1;
1182 /* Append a name of the declaration to the name obstack. A helper function for
1186 make_fancy_decl_name (tree decl)
1190 tree name = DECL_NAME (decl);
1192 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1193 IDENTIFIER_LENGTH (name));
1196 sprintf (buffer, "D%u", DECL_UID (decl));
1197 obstack_grow (&name_obstack, buffer, strlen (buffer));
1201 /* Helper for make_fancy_name. */
1204 make_fancy_name_1 (tree expr)
1211 make_fancy_decl_name (expr);
1215 switch (TREE_CODE (expr))
1218 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1219 obstack_1grow (&name_obstack, '$');
1220 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1224 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1225 obstack_1grow (&name_obstack, '$');
1226 /* Arrays with only one element may not have a constant as their
1228 index = TREE_OPERAND (expr, 1);
1229 if (TREE_CODE (index) != INTEGER_CST)
1231 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1232 obstack_grow (&name_obstack, buffer, strlen (buffer));
1239 gcc_unreachable (); /* we treat these as scalars. */
1246 /* Create a human readable name for replacement variable of ACCESS. */
1249 make_fancy_name (tree expr)
1251 make_fancy_name_1 (expr);
1252 obstack_1grow (&name_obstack, '\0');
1253 return XOBFINISH (&name_obstack, char *);
1256 /* Helper function for build_ref_for_offset. */
1259 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1265 tree tr_size, index, minidx;
1266 HOST_WIDE_INT el_size;
1268 if (offset == 0 && exp_type
1269 && types_compatible_p (exp_type, type))
1272 switch (TREE_CODE (type))
1275 case QUAL_UNION_TYPE:
1277 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1279 HOST_WIDE_INT pos, size;
1280 tree expr, *expr_ptr;
1282 if (TREE_CODE (fld) != FIELD_DECL)
1285 pos = int_bit_position (fld);
1286 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1287 tr_size = DECL_SIZE (fld);
1288 if (!tr_size || !host_integerp (tr_size, 1))
1290 size = tree_low_cst (tr_size, 1);
1291 if (pos > offset || (pos + size) <= offset)
1296 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1302 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1303 offset - pos, exp_type))
1313 tr_size = TYPE_SIZE (TREE_TYPE (type));
1314 if (!tr_size || !host_integerp (tr_size, 1))
1316 el_size = tree_low_cst (tr_size, 1);
1318 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1319 if (TREE_CODE (minidx) != INTEGER_CST)
1323 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1324 if (!integer_zerop (minidx))
1325 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1326 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1327 NULL_TREE, NULL_TREE);
1329 offset = offset % el_size;
1330 type = TREE_TYPE (type);
1345 /* Construct an expression that would reference a part of aggregate *EXPR of
1346 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1347 function only determines whether it can build such a reference without
1348 actually doing it, otherwise, the tree it points to is unshared first and
1349 then used as a base for furhter sub-references.
1351 FIXME: Eventually this should be replaced with
1352 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1353 minor rewrite of fold_stmt.
1357 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1358 tree exp_type, bool allow_ptr)
1360 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1363 *expr = unshare_expr (*expr);
1365 if (allow_ptr && POINTER_TYPE_P (type))
1367 type = TREE_TYPE (type);
1369 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1372 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1375 /* Return true iff TYPE is stdarg va_list type. */
1378 is_va_list_type (tree type)
1380 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1383 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1384 those with type which is suitable for scalarization. */
1387 find_var_candidates (void)
1390 referenced_var_iterator rvi;
1393 FOR_EACH_REFERENCED_VAR (var, rvi)
1395 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1397 type = TREE_TYPE (var);
1399 if (!AGGREGATE_TYPE_P (type)
1400 || needs_to_live_in_memory (var)
1401 || TREE_THIS_VOLATILE (var)
1402 || !COMPLETE_TYPE_P (type)
1403 || !host_integerp (TYPE_SIZE (type), 1)
1404 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1405 || type_internals_preclude_sra_p (type)
1406 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1407 we also want to schedule it rather late. Thus we ignore it in
1409 || (sra_mode == SRA_MODE_EARLY_INTRA
1410 && is_va_list_type (type)))
1413 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1415 if (dump_file && (dump_flags & TDF_DETAILS))
1417 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1418 print_generic_expr (dump_file, var, 0);
1419 fprintf (dump_file, "\n");
1427 /* Sort all accesses for the given variable, check for partial overlaps and
1428 return NULL if there are any. If there are none, pick a representative for
1429 each combination of offset and size and create a linked list out of them.
1430 Return the pointer to the first representative and make sure it is the first
1431 one in the vector of accesses. */
1433 static struct access *
1434 sort_and_splice_var_accesses (tree var)
1436 int i, j, access_count;
1437 struct access *res, **prev_acc_ptr = &res;
1438 VEC (access_p, heap) *access_vec;
1440 HOST_WIDE_INT low = -1, high = 0;
1442 access_vec = get_base_access_vector (var);
1445 access_count = VEC_length (access_p, access_vec);
1447 /* Sort by <OFFSET, SIZE>. */
1448 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1449 compare_access_positions);
1452 while (i < access_count)
1454 struct access *access = VEC_index (access_p, access_vec, i);
1455 bool grp_write = access->write;
1456 bool grp_read = !access->write;
1457 bool multiple_reads = false;
1458 bool grp_partial_lhs = access->grp_partial_lhs;
1459 bool first_scalar = is_gimple_reg_type (access->type);
1460 bool unscalarizable_region = access->grp_unscalarizable_region;
1462 if (first || access->offset >= high)
1465 low = access->offset;
1466 high = access->offset + access->size;
1468 else if (access->offset > low && access->offset + access->size > high)
1471 gcc_assert (access->offset >= low
1472 && access->offset + access->size <= high);
1475 while (j < access_count)
1477 struct access *ac2 = VEC_index (access_p, access_vec, j);
1478 if (ac2->offset != access->offset || ac2->size != access->size)
1485 multiple_reads = true;
1489 grp_partial_lhs |= ac2->grp_partial_lhs;
1490 unscalarizable_region |= ac2->grp_unscalarizable_region;
1491 relink_to_new_repr (access, ac2);
1493 /* If there are both aggregate-type and scalar-type accesses with
1494 this combination of size and offset, the comparison function
1495 should have put the scalars first. */
1496 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1497 ac2->group_representative = access;
1503 access->group_representative = access;
1504 access->grp_write = grp_write;
1505 access->grp_read = grp_read;
1506 access->grp_hint = multiple_reads;
1507 access->grp_partial_lhs = grp_partial_lhs;
1508 access->grp_unscalarizable_region = unscalarizable_region;
1509 if (access->first_link)
1510 add_access_to_work_queue (access);
1512 *prev_acc_ptr = access;
1513 prev_acc_ptr = &access->next_grp;
1516 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1520 /* Create a variable for the given ACCESS which determines the type, name and a
1521 few other properties. Return the variable declaration and store it also to
1522 ACCESS->replacement. */
1525 create_access_replacement (struct access *access)
1529 repl = create_tmp_var (access->type, "SR");
1531 add_referenced_var (repl);
1532 mark_sym_for_renaming (repl);
1534 if (!access->grp_partial_lhs
1535 && (TREE_CODE (access->type) == COMPLEX_TYPE
1536 || TREE_CODE (access->type) == VECTOR_TYPE))
1537 DECL_GIMPLE_REG_P (repl) = 1;
1539 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1540 DECL_ARTIFICIAL (repl) = 1;
1542 if (DECL_NAME (access->base)
1543 && !DECL_IGNORED_P (access->base)
1544 && !DECL_ARTIFICIAL (access->base))
1546 char *pretty_name = make_fancy_name (access->expr);
1548 DECL_NAME (repl) = get_identifier (pretty_name);
1549 obstack_free (&name_obstack, pretty_name);
1551 SET_DECL_DEBUG_EXPR (repl, access->expr);
1552 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1553 DECL_IGNORED_P (repl) = 0;
1556 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1557 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1561 fprintf (dump_file, "Created a replacement for ");
1562 print_generic_expr (dump_file, access->base, 0);
1563 fprintf (dump_file, " offset: %u, size: %u: ",
1564 (unsigned) access->offset, (unsigned) access->size);
1565 print_generic_expr (dump_file, repl, 0);
1566 fprintf (dump_file, "\n");
1568 sra_stats.replacements++;
1573 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1576 get_access_replacement (struct access *access)
1578 gcc_assert (access->grp_to_be_replaced);
1580 if (!access->replacement_decl)
1581 access->replacement_decl = create_access_replacement (access);
1582 return access->replacement_decl;
1585 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1586 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1587 to it is not "within" the root. */
1590 build_access_subtree (struct access **access)
1592 struct access *root = *access, *last_child = NULL;
1593 HOST_WIDE_INT limit = root->offset + root->size;
1595 *access = (*access)->next_grp;
1596 while (*access && (*access)->offset + (*access)->size <= limit)
1599 root->first_child = *access;
1601 last_child->next_sibling = *access;
1602 last_child = *access;
1604 build_access_subtree (access);
1608 /* Build a tree of access representatives, ACCESS is the pointer to the first
1609 one, others are linked in a list by the next_grp field. Decide about scalar
1610 replacements on the way, return true iff any are to be created. */
1613 build_access_trees (struct access *access)
1617 struct access *root = access;
1619 build_access_subtree (&access);
1620 root->next_grp = access;
1624 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1628 expr_with_var_bounded_array_refs_p (tree expr)
1630 while (handled_component_p (expr))
1632 if (TREE_CODE (expr) == ARRAY_REF
1633 && !host_integerp (array_ref_low_bound (expr), 0))
1635 expr = TREE_OPERAND (expr, 0);
1640 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1641 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1642 all sorts of access flags appropriately along the way, notably always ser
1643 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1646 analyze_access_subtree (struct access *root, bool allow_replacements,
1647 bool mark_read, bool mark_write)
1649 struct access *child;
1650 HOST_WIDE_INT limit = root->offset + root->size;
1651 HOST_WIDE_INT covered_to = root->offset;
1652 bool scalar = is_gimple_reg_type (root->type);
1653 bool hole = false, sth_created = false;
1654 bool direct_read = root->grp_read;
1657 root->grp_read = true;
1658 else if (root->grp_read)
1662 root->grp_write = true;
1663 else if (root->grp_write)
1666 if (root->grp_unscalarizable_region)
1667 allow_replacements = false;
1669 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1670 allow_replacements = false;
1672 for (child = root->first_child; child; child = child->next_sibling)
1674 if (!hole && child->offset < covered_to)
1677 covered_to += child->size;
1679 sth_created |= analyze_access_subtree (child, allow_replacements,
1680 mark_read, mark_write);
1682 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1683 hole |= !child->grp_covered;
1686 if (allow_replacements && scalar && !root->first_child
1688 || (direct_read && root->grp_write))
1689 /* We must not ICE later on when trying to build an access to the
1690 original data within the aggregate even when it is impossible to do in
1691 a defined way like in the PR 42703 testcase. Therefore we check
1692 pre-emptively here that we will be able to do that. */
1693 && build_ref_for_offset (NULL, TREE_TYPE (root->base), root->offset,
1696 if (dump_file && (dump_flags & TDF_DETAILS))
1698 fprintf (dump_file, "Marking ");
1699 print_generic_expr (dump_file, root->base, 0);
1700 fprintf (dump_file, " offset: %u, size: %u: ",
1701 (unsigned) root->offset, (unsigned) root->size);
1702 fprintf (dump_file, " to be replaced.\n");
1705 root->grp_to_be_replaced = 1;
1709 else if (covered_to < limit)
1712 if (sth_created && !hole)
1714 root->grp_covered = 1;
1717 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1718 root->grp_unscalarized_data = 1; /* not covered and written to */
1724 /* Analyze all access trees linked by next_grp by the means of
1725 analyze_access_subtree. */
1727 analyze_access_trees (struct access *access)
1733 if (analyze_access_subtree (access, true, false, false))
1735 access = access->next_grp;
1741 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1742 SIZE would conflict with an already existing one. If exactly such a child
1743 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1746 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1747 HOST_WIDE_INT size, struct access **exact_match)
1749 struct access *child;
1751 for (child = lacc->first_child; child; child = child->next_sibling)
1753 if (child->offset == norm_offset && child->size == size)
1755 *exact_match = child;
1759 if (child->offset < norm_offset + size
1760 && child->offset + child->size > norm_offset)
1767 /* Create a new child access of PARENT, with all properties just like MODEL
1768 except for its offset and with its grp_write false and grp_read true.
1769 Return the new access or NULL if it cannot be created. Note that this access
1770 is created long after all splicing and sorting, it's not located in any
1771 access vector and is automatically a representative of its group. */
1773 static struct access *
1774 create_artificial_child_access (struct access *parent, struct access *model,
1775 HOST_WIDE_INT new_offset)
1777 struct access *access;
1778 struct access **child;
1779 tree expr = parent->base;;
1781 gcc_assert (!model->grp_unscalarizable_region);
1783 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1784 model->type, false))
1787 access = (struct access *) pool_alloc (access_pool);
1788 memset (access, 0, sizeof (struct access));
1789 access->base = parent->base;
1790 access->expr = expr;
1791 access->offset = new_offset;
1792 access->size = model->size;
1793 access->type = model->type;
1794 access->grp_write = true;
1795 access->grp_read = false;
1797 child = &parent->first_child;
1798 while (*child && (*child)->offset < new_offset)
1799 child = &(*child)->next_sibling;
1801 access->next_sibling = *child;
1808 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1809 true if any new subaccess was created. Additionally, if RACC is a scalar
1810 access but LACC is not, change the type of the latter, if possible. */
1813 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1815 struct access *rchild;
1816 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1819 if (is_gimple_reg_type (lacc->type)
1820 || lacc->grp_unscalarizable_region
1821 || racc->grp_unscalarizable_region)
1824 if (!lacc->first_child && !racc->first_child
1825 && is_gimple_reg_type (racc->type))
1827 tree t = lacc->base;
1829 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1833 lacc->type = racc->type;
1838 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1840 struct access *new_acc = NULL;
1841 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1843 if (rchild->grp_unscalarizable_region)
1846 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1851 rchild->grp_hint = 1;
1852 new_acc->grp_hint |= new_acc->grp_read;
1853 if (rchild->first_child)
1854 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1859 /* If a (part of) a union field is on the RHS of an assignment, it can
1860 have sub-accesses which do not make sense on the LHS (PR 40351).
1861 Check that this is not the case. */
1862 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1863 rchild->type, false))
1866 rchild->grp_hint = 1;
1867 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1871 if (racc->first_child)
1872 propagate_subaccesses_across_link (new_acc, rchild);
1879 /* Propagate all subaccesses across assignment links. */
1882 propagate_all_subaccesses (void)
1884 while (work_queue_head)
1886 struct access *racc = pop_access_from_work_queue ();
1887 struct assign_link *link;
1889 gcc_assert (racc->first_link);
1891 for (link = racc->first_link; link; link = link->next)
1893 struct access *lacc = link->lacc;
1895 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1897 lacc = lacc->group_representative;
1898 if (propagate_subaccesses_across_link (lacc, racc)
1899 && lacc->first_link)
1900 add_access_to_work_queue (lacc);
1905 /* Go through all accesses collected throughout the (intraprocedural) analysis
1906 stage, exclude overlapping ones, identify representatives and build trees
1907 out of them, making decisions about scalarization on the way. Return true
1908 iff there are any to-be-scalarized variables after this stage. */
1911 analyze_all_variable_accesses (void)
1914 bitmap tmp = BITMAP_ALLOC (NULL);
1918 bitmap_copy (tmp, candidate_bitmap);
1919 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1921 tree var = referenced_var (i);
1922 struct access *access;
1924 access = sort_and_splice_var_accesses (var);
1926 build_access_trees (access);
1928 disqualify_candidate (var,
1929 "No or inhibitingly overlapping accesses.");
1932 propagate_all_subaccesses ();
1934 bitmap_copy (tmp, candidate_bitmap);
1935 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1937 tree var = referenced_var (i);
1938 struct access *access = get_first_repr_for_decl (var);
1940 if (analyze_access_trees (access))
1943 if (dump_file && (dump_flags & TDF_DETAILS))
1945 fprintf (dump_file, "\nAccess trees for ");
1946 print_generic_expr (dump_file, var, 0);
1947 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1948 dump_access_tree (dump_file, access);
1949 fprintf (dump_file, "\n");
1953 disqualify_candidate (var, "No scalar replacements to be created.");
1960 statistics_counter_event (cfun, "Scalarized aggregates", res);
1967 /* Return true iff a reference statement into aggregate AGG can be built for
1968 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1969 or a child of its sibling. TOP_OFFSET is the offset from the processed
1970 access subtree that has to be subtracted from offset of each access. */
1973 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1974 HOST_WIDE_INT top_offset)
1978 if (access->grp_to_be_replaced
1979 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1980 access->offset - top_offset,
1981 access->type, false))
1984 if (access->first_child
1985 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1989 access = access->next_sibling;
1996 /* Generate statements copying scalar replacements of accesses within a subtree
1997 into or out of AGG. ACCESS is the first child of the root of the subtree to
1998 be processed. AGG is an aggregate type expression (can be a declaration but
1999 does not have to be, it can for example also be an indirect_ref).
2000 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2001 from offsets of individual accesses to get corresponding offsets for AGG.
2002 If CHUNK_SIZE is non-null, copy only replacements in the interval
2003 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2004 statement iterator used to place the new statements. WRITE should be true
2005 when the statements should write from AGG to the replacement and false if
2006 vice versa. if INSERT_AFTER is true, new statements will be added after the
2007 current statement in GSI, they will be added before the statement
2011 generate_subtree_copies (struct access *access, tree agg,
2012 HOST_WIDE_INT top_offset,
2013 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2014 gimple_stmt_iterator *gsi, bool write,
2021 if (chunk_size && access->offset >= start_offset + chunk_size)
2024 if (access->grp_to_be_replaced
2026 || access->offset + access->size > start_offset))
2028 tree repl = get_access_replacement (access);
2032 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2033 access->offset - top_offset,
2034 access->type, false);
2035 gcc_assert (ref_found);
2039 if (access->grp_partial_lhs)
2040 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2042 insert_after ? GSI_NEW_STMT
2044 stmt = gimple_build_assign (repl, expr);
2048 TREE_NO_WARNING (repl) = 1;
2049 if (access->grp_partial_lhs)
2050 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2052 insert_after ? GSI_NEW_STMT
2054 stmt = gimple_build_assign (expr, repl);
2058 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2060 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2062 sra_stats.subtree_copies++;
2065 if (access->first_child)
2066 generate_subtree_copies (access->first_child, agg, top_offset,
2067 start_offset, chunk_size, gsi,
2068 write, insert_after);
2070 access = access->next_sibling;
2075 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2076 the root of the subtree to be processed. GSI is the statement iterator used
2077 for inserting statements which are added after the current statement if
2078 INSERT_AFTER is true or before it otherwise. */
2081 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2085 struct access *child;
2087 if (access->grp_to_be_replaced)
2091 stmt = gimple_build_assign (get_access_replacement (access),
2092 fold_convert (access->type,
2093 integer_zero_node));
2095 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2097 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2101 for (child = access->first_child; child; child = child->next_sibling)
2102 init_subtree_with_zero (child, gsi, insert_after);
2105 /* Search for an access representative for the given expression EXPR and
2106 return it or NULL if it cannot be found. */
2108 static struct access *
2109 get_access_for_expr (tree expr)
2111 HOST_WIDE_INT offset, size, max_size;
2114 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2115 a different size than the size of its argument and we need the latter
2117 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2118 expr = TREE_OPERAND (expr, 0);
2120 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2121 if (max_size == -1 || !DECL_P (base))
2124 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2127 return get_var_base_offset_size_access (base, offset, max_size);
2130 /* Callback for scan_function. Replace the expression EXPR with a scalar
2131 replacement if there is one and generate other statements to do type
2132 conversion or subtree copying if necessary. GSI is used to place newly
2133 created statements, WRITE is true if the expression is being written to (it
2134 is on a LHS of a statement or output in an assembly statement). */
2137 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2138 void *data ATTRIBUTE_UNUSED)
2140 struct access *access;
2143 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2146 expr = &TREE_OPERAND (*expr, 0);
2151 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2152 expr = &TREE_OPERAND (*expr, 0);
2153 access = get_access_for_expr (*expr);
2156 type = TREE_TYPE (*expr);
2158 if (access->grp_to_be_replaced)
2160 tree repl = get_access_replacement (access);
2161 /* If we replace a non-register typed access simply use the original
2162 access expression to extract the scalar component afterwards.
2163 This happens if scalarizing a function return value or parameter
2164 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2165 gcc.c-torture/compile/20011217-1.c.
2167 We also want to use this when accessing a complex or vector which can
2168 be accessed as a different type too, potentially creating a need for
2169 type conversion (see PR42196) and when scalarized unions are involved
2170 in assembler statements (see PR42398). */
2171 if (!useless_type_conversion_p (type, access->type))
2173 tree ref = access->base;
2176 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2177 access->offset, access->type, false);
2184 if (access->grp_partial_lhs)
2185 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2186 false, GSI_NEW_STMT);
2187 stmt = gimple_build_assign (repl, ref);
2188 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2194 if (access->grp_partial_lhs)
2195 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2196 true, GSI_SAME_STMT);
2197 stmt = gimple_build_assign (ref, repl);
2198 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2206 if (access->first_child)
2208 HOST_WIDE_INT start_offset, chunk_size;
2210 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2211 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2213 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2214 start_offset = access->offset
2215 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2218 start_offset = chunk_size = 0;
2220 generate_subtree_copies (access->first_child, access->base, 0,
2221 start_offset, chunk_size, gsi, write, write);
2226 /* Where scalar replacements of the RHS have been written to when a replacement
2227 of a LHS of an assigments cannot be direclty loaded from a replacement of
2229 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2230 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2231 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2233 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2234 base aggregate if there are unscalarized data or directly to LHS
2237 static enum unscalarized_data_handling
2238 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2239 gimple_stmt_iterator *gsi)
2241 if (top_racc->grp_unscalarized_data)
2243 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2245 return SRA_UDH_RIGHT;
2249 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2250 0, 0, gsi, false, false);
2251 return SRA_UDH_LEFT;
2256 /* Try to generate statements to load all sub-replacements in an access
2257 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2258 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2259 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2260 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2261 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2262 the rhs top aggregate has already been refreshed by contents of its scalar
2263 reductions and is set to true if this function has to do it. */
2266 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2267 HOST_WIDE_INT left_offset,
2268 HOST_WIDE_INT right_offset,
2269 gimple_stmt_iterator *old_gsi,
2270 gimple_stmt_iterator *new_gsi,
2271 enum unscalarized_data_handling *refreshed,
2274 location_t loc = EXPR_LOCATION (lacc->expr);
2277 if (lacc->grp_to_be_replaced)
2279 struct access *racc;
2280 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2284 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2285 if (racc && racc->grp_to_be_replaced)
2287 rhs = get_access_replacement (racc);
2288 if (!useless_type_conversion_p (lacc->type, racc->type))
2289 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2293 /* No suitable access on the right hand side, need to load from
2294 the aggregate. See if we have to update it first... */
2295 if (*refreshed == SRA_UDH_NONE)
2296 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2299 if (*refreshed == SRA_UDH_LEFT)
2304 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2305 lacc->offset, lacc->type,
2307 gcc_assert (repl_found);
2313 rhs = top_racc->base;
2314 repl_found = build_ref_for_offset (&rhs,
2315 TREE_TYPE (top_racc->base),
2316 offset, lacc->type, false);
2317 gcc_assert (repl_found);
2321 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2322 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2324 sra_stats.subreplacements++;
2326 else if (*refreshed == SRA_UDH_NONE
2327 && lacc->grp_read && !lacc->grp_covered)
2328 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2331 if (lacc->first_child)
2332 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2333 left_offset, right_offset,
2334 old_gsi, new_gsi, refreshed, lhs);
2335 lacc = lacc->next_sibling;
2340 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2341 to the assignment and GSI is the statement iterator pointing at it. Returns
2342 the same values as sra_modify_assign. */
2344 static enum scan_assign_result
2345 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2347 tree lhs = gimple_assign_lhs (*stmt);
2350 acc = get_access_for_expr (lhs);
2354 if (VEC_length (constructor_elt,
2355 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2357 /* I have never seen this code path trigger but if it can happen the
2358 following should handle it gracefully. */
2359 if (access_has_children_p (acc))
2360 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2362 return SRA_SA_PROCESSED;
2365 if (acc->grp_covered)
2367 init_subtree_with_zero (acc, gsi, false);
2368 unlink_stmt_vdef (*stmt);
2369 gsi_remove (gsi, true);
2370 return SRA_SA_REMOVED;
2374 init_subtree_with_zero (acc, gsi, true);
2375 return SRA_SA_PROCESSED;
2380 /* Callback of scan_function to process assign statements. It examines both
2381 sides of the statement, replaces them with a scalare replacement if there is
2382 one and generating copying of replacements if scalarized aggregates have been
2383 used in the assignment. STMT is a pointer to the assign statement, GSI is
2384 used to hold generated statements for type conversions and subtree
2387 static enum scan_assign_result
2388 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2389 void *data ATTRIBUTE_UNUSED)
2391 struct access *lacc, *racc;
2393 bool modify_this_stmt = false;
2394 bool force_gimple_rhs = false;
2395 location_t loc = gimple_location (*stmt);
2397 if (!gimple_assign_single_p (*stmt))
2399 lhs = gimple_assign_lhs (*stmt);
2400 rhs = gimple_assign_rhs1 (*stmt);
2402 if (TREE_CODE (rhs) == CONSTRUCTOR)
2403 return sra_modify_constructor_assign (stmt, gsi);
2405 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2406 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2407 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2409 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2411 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2413 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2416 lacc = get_access_for_expr (lhs);
2417 racc = get_access_for_expr (rhs);
2421 if (lacc && lacc->grp_to_be_replaced)
2423 lhs = get_access_replacement (lacc);
2424 gimple_assign_set_lhs (*stmt, lhs);
2425 modify_this_stmt = true;
2426 if (lacc->grp_partial_lhs)
2427 force_gimple_rhs = true;
2431 if (racc && racc->grp_to_be_replaced)
2433 rhs = get_access_replacement (racc);
2434 modify_this_stmt = true;
2435 if (racc->grp_partial_lhs)
2436 force_gimple_rhs = true;
2440 if (modify_this_stmt)
2442 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2444 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2445 ??? This should move to fold_stmt which we simply should
2446 call after building a VIEW_CONVERT_EXPR here. */
2447 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2448 && !access_has_children_p (lacc))
2451 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2452 TREE_TYPE (rhs), false))
2455 gimple_assign_set_lhs (*stmt, expr);
2458 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2459 && !access_has_children_p (racc))
2462 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2463 TREE_TYPE (lhs), false))
2466 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2468 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2469 if (is_gimple_reg_type (TREE_TYPE (lhs))
2470 && TREE_CODE (lhs) != SSA_NAME)
2471 force_gimple_rhs = true;
2475 if (force_gimple_rhs)
2476 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2477 true, GSI_SAME_STMT);
2478 if (gimple_assign_rhs1 (*stmt) != rhs)
2480 gimple_assign_set_rhs_from_tree (gsi, rhs);
2481 gcc_assert (*stmt == gsi_stmt (*gsi));
2485 /* From this point on, the function deals with assignments in between
2486 aggregates when at least one has scalar reductions of some of its
2487 components. There are three possible scenarios: Both the LHS and RHS have
2488 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2490 In the first case, we would like to load the LHS components from RHS
2491 components whenever possible. If that is not possible, we would like to
2492 read it directly from the RHS (after updating it by storing in it its own
2493 components). If there are some necessary unscalarized data in the LHS,
2494 those will be loaded by the original assignment too. If neither of these
2495 cases happen, the original statement can be removed. Most of this is done
2496 by load_assign_lhs_subreplacements.
2498 In the second case, we would like to store all RHS scalarized components
2499 directly into LHS and if they cover the aggregate completely, remove the
2500 statement too. In the third case, we want the LHS components to be loaded
2501 directly from the RHS (DSE will remove the original statement if it
2504 This is a bit complex but manageable when types match and when unions do
2505 not cause confusion in a way that we cannot really load a component of LHS
2506 from the RHS or vice versa (the access representing this level can have
2507 subaccesses that are accessible only through a different union field at a
2508 higher level - different from the one used in the examined expression).
2511 Therefore, I specially handle a fourth case, happening when there is a
2512 specific type cast or it is impossible to locate a scalarized subaccess on
2513 the other side of the expression. If that happens, I simply "refresh" the
2514 RHS by storing in it is scalarized components leave the original statement
2515 there to do the copying and then load the scalar replacements of the LHS.
2516 This is what the first branch does. */
2518 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2519 || (access_has_children_p (racc)
2520 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2521 || (access_has_children_p (lacc)
2522 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2524 if (access_has_children_p (racc))
2525 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2527 if (access_has_children_p (lacc))
2528 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2530 sra_stats.separate_lhs_rhs_handling++;
2534 if (access_has_children_p (lacc) && access_has_children_p (racc))
2536 gimple_stmt_iterator orig_gsi = *gsi;
2537 enum unscalarized_data_handling refreshed;
2539 if (lacc->grp_read && !lacc->grp_covered)
2540 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2542 refreshed = SRA_UDH_NONE;
2544 load_assign_lhs_subreplacements (lacc->first_child, racc,
2545 lacc->offset, racc->offset,
2546 &orig_gsi, gsi, &refreshed, lhs);
2547 if (refreshed != SRA_UDH_RIGHT)
2549 if (*stmt == gsi_stmt (*gsi))
2552 unlink_stmt_vdef (*stmt);
2553 gsi_remove (&orig_gsi, true);
2554 sra_stats.deleted++;
2555 return SRA_SA_REMOVED;
2560 if (access_has_children_p (racc))
2562 if (!racc->grp_unscalarized_data
2563 /* Do not remove SSA name definitions (PR 42704). */
2564 && TREE_CODE (lhs) != SSA_NAME)
2566 generate_subtree_copies (racc->first_child, lhs,
2567 racc->offset, 0, 0, gsi,
2569 gcc_assert (*stmt == gsi_stmt (*gsi));
2570 unlink_stmt_vdef (*stmt);
2571 gsi_remove (gsi, true);
2572 sra_stats.deleted++;
2573 return SRA_SA_REMOVED;
2576 generate_subtree_copies (racc->first_child, lhs,
2577 racc->offset, 0, 0, gsi, false, true);
2579 else if (access_has_children_p (lacc))
2580 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2581 0, 0, gsi, true, true);
2584 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2587 /* Generate statements initializing scalar replacements of parts of function
2591 initialize_parameter_reductions (void)
2593 gimple_stmt_iterator gsi;
2594 gimple_seq seq = NULL;
2597 for (parm = DECL_ARGUMENTS (current_function_decl);
2599 parm = TREE_CHAIN (parm))
2601 VEC (access_p, heap) *access_vec;
2602 struct access *access;
2604 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2606 access_vec = get_base_access_vector (parm);
2612 seq = gimple_seq_alloc ();
2613 gsi = gsi_start (seq);
2616 for (access = VEC_index (access_p, access_vec, 0);
2618 access = access->next_grp)
2619 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2623 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2626 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2627 it reveals there are components of some aggregates to be scalarized, it runs
2628 the required transformations. */
2630 perform_intra_sra (void)
2635 if (!find_var_candidates ())
2638 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2642 if (!analyze_all_variable_accesses ())
2645 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2646 initialize_parameter_reductions ();
2648 statistics_counter_event (cfun, "Scalar replacements created",
2649 sra_stats.replacements);
2650 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2651 statistics_counter_event (cfun, "Subtree copy stmts",
2652 sra_stats.subtree_copies);
2653 statistics_counter_event (cfun, "Subreplacement stmts",
2654 sra_stats.subreplacements);
2655 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2656 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2657 sra_stats.separate_lhs_rhs_handling);
2659 ret = TODO_update_ssa;
2662 sra_deinitialize ();
2666 /* Perform early intraprocedural SRA. */
2668 early_intra_sra (void)
2670 sra_mode = SRA_MODE_EARLY_INTRA;
2671 return perform_intra_sra ();
2674 /* Perform "late" intraprocedural SRA. */
2676 late_intra_sra (void)
2678 sra_mode = SRA_MODE_INTRA;
2679 return perform_intra_sra ();
2684 gate_intra_sra (void)
2686 return flag_tree_sra != 0;
2690 struct gimple_opt_pass pass_sra_early =
2695 gate_intra_sra, /* gate */
2696 early_intra_sra, /* execute */
2699 0, /* static_pass_number */
2700 TV_TREE_SRA, /* tv_id */
2701 PROP_cfg | PROP_ssa, /* properties_required */
2702 0, /* properties_provided */
2703 0, /* properties_destroyed */
2704 0, /* todo_flags_start */
2708 | TODO_verify_ssa /* todo_flags_finish */
2712 struct gimple_opt_pass pass_sra =
2717 gate_intra_sra, /* gate */
2718 late_intra_sra, /* execute */
2721 0, /* static_pass_number */
2722 TV_TREE_SRA, /* tv_id */
2723 PROP_cfg | PROP_ssa, /* properties_required */
2724 0, /* properties_provided */
2725 0, /* properties_destroyed */
2726 TODO_update_address_taken, /* todo_flags_start */
2730 | TODO_verify_ssa /* todo_flags_finish */
2735 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2739 is_unused_scalar_param (tree parm)
2742 return (is_gimple_reg (parm)
2743 && (!(name = gimple_default_def (cfun, parm))
2744 || has_zero_uses (name)));
2747 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2748 examine whether there are any direct or otherwise infeasible ones. If so,
2749 return true, otherwise return false. PARM must be a gimple register with a
2750 non-NULL default definition. */
2753 ptr_parm_has_direct_uses (tree parm)
2755 imm_use_iterator ui;
2757 tree name = gimple_default_def (cfun, parm);
2760 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2762 if (gimple_assign_single_p (stmt))
2764 tree rhs = gimple_assign_rhs1 (stmt);
2767 else if (TREE_CODE (rhs) == ADDR_EXPR)
2771 rhs = TREE_OPERAND (rhs, 0);
2773 while (handled_component_p (rhs));
2774 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2778 else if (gimple_code (stmt) == GIMPLE_RETURN)
2780 tree t = gimple_return_retval (stmt);
2784 else if (is_gimple_call (stmt))
2787 for (i = 0; i < gimple_call_num_args (stmt); i++)
2789 tree arg = gimple_call_arg (stmt, i);
2797 else if (!is_gimple_debug (stmt))
2801 BREAK_FROM_IMM_USE_STMT (ui);
2807 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2808 them in candidate_bitmap. Note that these do not necessarily include
2809 parameter which are unused and thus can be removed. Return true iff any
2810 such candidate has been found. */
2813 find_param_candidates (void)
2819 for (parm = DECL_ARGUMENTS (current_function_decl);
2821 parm = TREE_CHAIN (parm))
2823 tree type = TREE_TYPE (parm);
2827 if (TREE_THIS_VOLATILE (parm)
2828 || TREE_ADDRESSABLE (parm)
2829 || is_va_list_type (type))
2832 if (is_unused_scalar_param (parm))
2838 if (POINTER_TYPE_P (type))
2840 type = TREE_TYPE (type);
2842 if (TREE_CODE (type) == FUNCTION_TYPE
2843 || TYPE_VOLATILE (type)
2844 || !is_gimple_reg (parm)
2845 || is_va_list_type (type)
2846 || ptr_parm_has_direct_uses (parm))
2849 else if (!AGGREGATE_TYPE_P (type))
2852 if (!COMPLETE_TYPE_P (type)
2853 || !host_integerp (TYPE_SIZE (type), 1)
2854 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2855 || (AGGREGATE_TYPE_P (type)
2856 && type_internals_preclude_sra_p (type)))
2859 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2861 if (dump_file && (dump_flags & TDF_DETAILS))
2863 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2864 print_generic_expr (dump_file, parm, 0);
2865 fprintf (dump_file, "\n");
2869 func_param_count = count;
2873 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2877 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2880 struct access *repr = (struct access *) data;
2882 repr->grp_maybe_modified = 1;
2886 /* Analyze what representatives (in linked lists accessible from
2887 REPRESENTATIVES) can be modified by side effects of statements in the
2888 current function. */
2891 analyze_modified_params (VEC (access_p, heap) *representatives)
2895 for (i = 0; i < func_param_count; i++)
2897 struct access *repr;
2899 for (repr = VEC_index (access_p, representatives, i);
2901 repr = repr->next_grp)
2903 struct access *access;
2907 if (no_accesses_p (repr))
2909 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
2910 || repr->grp_maybe_modified)
2913 ao_ref_init (&ar, repr->expr);
2914 visited = BITMAP_ALLOC (NULL);
2915 for (access = repr; access; access = access->next_sibling)
2917 /* All accesses are read ones, otherwise grp_maybe_modified would
2918 be trivially set. */
2919 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2920 mark_maybe_modified, repr, &visited);
2921 if (repr->grp_maybe_modified)
2924 BITMAP_FREE (visited);
2929 /* Propagate distances in bb_dereferences in the opposite direction than the
2930 control flow edges, in each step storing the maximum of the current value
2931 and the minimum of all successors. These steps are repeated until the table
2932 stabilizes. Note that BBs which might terminate the functions (according to
2933 final_bbs bitmap) never updated in this way. */
2936 propagate_dereference_distances (void)
2938 VEC (basic_block, heap) *queue;
2941 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2942 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2945 VEC_quick_push (basic_block, queue, bb);
2949 while (!VEC_empty (basic_block, queue))
2953 bool change = false;
2956 bb = VEC_pop (basic_block, queue);
2959 if (bitmap_bit_p (final_bbs, bb->index))
2962 for (i = 0; i < func_param_count; i++)
2964 int idx = bb->index * func_param_count + i;
2966 HOST_WIDE_INT inh = 0;
2968 FOR_EACH_EDGE (e, ei, bb->succs)
2970 int succ_idx = e->dest->index * func_param_count + i;
2972 if (e->src == EXIT_BLOCK_PTR)
2978 inh = bb_dereferences [succ_idx];
2980 else if (bb_dereferences [succ_idx] < inh)
2981 inh = bb_dereferences [succ_idx];
2984 if (!first && bb_dereferences[idx] < inh)
2986 bb_dereferences[idx] = inh;
2991 if (change && !bitmap_bit_p (final_bbs, bb->index))
2992 FOR_EACH_EDGE (e, ei, bb->preds)
2997 e->src->aux = e->src;
2998 VEC_quick_push (basic_block, queue, e->src);
3002 VEC_free (basic_block, heap, queue);
3005 /* Dump a dereferences TABLE with heading STR to file F. */
3008 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3012 fprintf (dump_file, str);
3013 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3015 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3016 if (bb != EXIT_BLOCK_PTR)
3019 for (i = 0; i < func_param_count; i++)
3021 int idx = bb->index * func_param_count + i;
3022 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3027 fprintf (dump_file, "\n");
3030 /* Determine what (parts of) parameters passed by reference that are not
3031 assigned to are not certainly dereferenced in this function and thus the
3032 dereferencing cannot be safely moved to the caller without potentially
3033 introducing a segfault. Mark such REPRESENTATIVES as
3034 grp_not_necessarilly_dereferenced.
3036 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3037 part is calculated rather than simple booleans are calculated for each
3038 pointer parameter to handle cases when only a fraction of the whole
3039 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3042 The maximum dereference distances for each pointer parameter and BB are
3043 already stored in bb_dereference. This routine simply propagates these
3044 values upwards by propagate_dereference_distances and then compares the
3045 distances of individual parameters in the ENTRY BB to the equivalent
3046 distances of each representative of a (fraction of a) parameter. */
3049 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3053 if (dump_file && (dump_flags & TDF_DETAILS))
3054 dump_dereferences_table (dump_file,
3055 "Dereference table before propagation:\n",
3058 propagate_dereference_distances ();
3060 if (dump_file && (dump_flags & TDF_DETAILS))
3061 dump_dereferences_table (dump_file,
3062 "Dereference table after propagation:\n",
3065 for (i = 0; i < func_param_count; i++)
3067 struct access *repr = VEC_index (access_p, representatives, i);
3068 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3070 if (!repr || no_accesses_p (repr))
3075 if ((repr->offset + repr->size) > bb_dereferences[idx])
3076 repr->grp_not_necessarilly_dereferenced = 1;
3077 repr = repr->next_grp;
3083 /* Return the representative access for the parameter declaration PARM if it is
3084 a scalar passed by reference which is not written to and the pointer value
3085 is not used directly. Thus, if it is legal to dereference it in the caller
3086 and we can rule out modifications through aliases, such parameter should be
3087 turned into one passed by value. Return NULL otherwise. */
3089 static struct access *
3090 unmodified_by_ref_scalar_representative (tree parm)
3092 int i, access_count;
3093 struct access *repr;
3094 VEC (access_p, heap) *access_vec;
3096 access_vec = get_base_access_vector (parm);
3097 gcc_assert (access_vec);
3098 repr = VEC_index (access_p, access_vec, 0);
3101 repr->group_representative = repr;
3103 access_count = VEC_length (access_p, access_vec);
3104 for (i = 1; i < access_count; i++)
3106 struct access *access = VEC_index (access_p, access_vec, i);
3109 access->group_representative = repr;
3110 access->next_sibling = repr->next_sibling;
3111 repr->next_sibling = access;
3115 repr->grp_scalar_ptr = 1;
3119 /* Return true iff this access precludes IPA-SRA of the parameter it is
3123 access_precludes_ipa_sra_p (struct access *access)
3125 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3126 is incompatible assign in a call statement (and possibly even in asm
3127 statements). This can be relaxed by using a new temporary but only for
3128 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3129 intraprocedural SRA we deal with this by keeping the old aggregate around,
3130 something we cannot do in IPA-SRA.) */
3132 && (is_gimple_call (access->stmt)
3133 || gimple_code (access->stmt) == GIMPLE_ASM))
3140 /* Sort collected accesses for parameter PARM, identify representatives for
3141 each accessed region and link them together. Return NULL if there are
3142 different but overlapping accesses, return the special ptr value meaning
3143 there are no accesses for this parameter if that is the case and return the
3144 first representative otherwise. Set *RO_GRP if there is a group of accesses
3145 with only read (i.e. no write) accesses. */
3147 static struct access *
3148 splice_param_accesses (tree parm, bool *ro_grp)
3150 int i, j, access_count, group_count;
3151 int agg_size, total_size = 0;
3152 struct access *access, *res, **prev_acc_ptr = &res;
3153 VEC (access_p, heap) *access_vec;
3155 access_vec = get_base_access_vector (parm);
3157 return &no_accesses_representant;
3158 access_count = VEC_length (access_p, access_vec);
3160 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3161 compare_access_positions);
3166 while (i < access_count)
3169 access = VEC_index (access_p, access_vec, i);
3170 modification = access->write;
3171 if (access_precludes_ipa_sra_p (access))
3174 /* Access is about to become group representative unless we find some
3175 nasty overlap which would preclude us from breaking this parameter
3179 while (j < access_count)
3181 struct access *ac2 = VEC_index (access_p, access_vec, j);
3182 if (ac2->offset != access->offset)
3184 /* All or nothing law for parameters. */
3185 if (access->offset + access->size > ac2->offset)
3190 else if (ac2->size != access->size)
3193 if (access_precludes_ipa_sra_p (ac2))
3196 modification |= ac2->write;
3197 ac2->group_representative = access;
3198 ac2->next_sibling = access->next_sibling;
3199 access->next_sibling = ac2;
3204 access->grp_maybe_modified = modification;
3207 *prev_acc_ptr = access;
3208 prev_acc_ptr = &access->next_grp;
3209 total_size += access->size;
3213 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3214 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3216 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3217 if (total_size >= agg_size)
3220 gcc_assert (group_count > 0);
3224 /* Decide whether parameters with representative accesses given by REPR should
3225 be reduced into components. */
3228 decide_one_param_reduction (struct access *repr)
3230 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3235 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3236 gcc_assert (cur_parm_size > 0);
3238 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3241 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3246 agg_size = cur_parm_size;
3252 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3253 print_generic_expr (dump_file, parm, 0);
3254 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3255 for (acc = repr; acc; acc = acc->next_grp)
3256 dump_access (dump_file, acc, true);
3260 new_param_count = 0;
3262 for (; repr; repr = repr->next_grp)
3264 gcc_assert (parm == repr->base);
3267 if (!by_ref || (!repr->grp_maybe_modified
3268 && !repr->grp_not_necessarilly_dereferenced))
3269 total_size += repr->size;
3271 total_size += cur_parm_size;
3274 gcc_assert (new_param_count > 0);
3276 if (optimize_function_for_size_p (cfun))
3277 parm_size_limit = cur_parm_size;
3279 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3282 if (total_size < agg_size
3283 && total_size <= parm_size_limit)
3286 fprintf (dump_file, " ....will be split into %i components\n",
3288 return new_param_count;
3294 /* The order of the following enums is important, we need to do extra work for
3295 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3296 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3297 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3299 /* Identify representatives of all accesses to all candidate parameters for
3300 IPA-SRA. Return result based on what representatives have been found. */
3302 static enum ipa_splicing_result
3303 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3305 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3307 struct access *repr;
3309 *representatives = VEC_alloc (access_p, heap, func_param_count);
3311 for (parm = DECL_ARGUMENTS (current_function_decl);
3313 parm = TREE_CHAIN (parm))
3315 if (is_unused_scalar_param (parm))
3317 VEC_quick_push (access_p, *representatives,
3318 &no_accesses_representant);
3319 if (result == NO_GOOD_ACCESS)
3320 result = UNUSED_PARAMS;
3322 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3323 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3324 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3326 repr = unmodified_by_ref_scalar_representative (parm);
3327 VEC_quick_push (access_p, *representatives, repr);
3329 result = UNMODIF_BY_REF_ACCESSES;
3331 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3333 bool ro_grp = false;
3334 repr = splice_param_accesses (parm, &ro_grp);
3335 VEC_quick_push (access_p, *representatives, repr);
3337 if (repr && !no_accesses_p (repr))
3339 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3342 result = UNMODIF_BY_REF_ACCESSES;
3343 else if (result < MODIF_BY_REF_ACCESSES)
3344 result = MODIF_BY_REF_ACCESSES;
3346 else if (result < BY_VAL_ACCESSES)
3347 result = BY_VAL_ACCESSES;
3349 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3350 result = UNUSED_PARAMS;
3353 VEC_quick_push (access_p, *representatives, NULL);
3356 if (result == NO_GOOD_ACCESS)
3358 VEC_free (access_p, heap, *representatives);
3359 *representatives = NULL;
3360 return NO_GOOD_ACCESS;
3366 /* Return the index of BASE in PARMS. Abort if it is not found. */
3369 get_param_index (tree base, VEC(tree, heap) *parms)
3373 len = VEC_length (tree, parms);
3374 for (i = 0; i < len; i++)
3375 if (VEC_index (tree, parms, i) == base)
3380 /* Convert the decisions made at the representative level into compact
3381 parameter adjustments. REPRESENTATIVES are pointers to first
3382 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3383 final number of adjustments. */
3385 static ipa_parm_adjustment_vec
3386 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3387 int adjustments_count)
3389 VEC (tree, heap) *parms;
3390 ipa_parm_adjustment_vec adjustments;
3394 gcc_assert (adjustments_count > 0);
3395 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3396 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3397 parm = DECL_ARGUMENTS (current_function_decl);
3398 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3400 struct access *repr = VEC_index (access_p, representatives, i);
3402 if (!repr || no_accesses_p (repr))
3404 struct ipa_parm_adjustment *adj;
3406 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3407 memset (adj, 0, sizeof (*adj));
3408 adj->base_index = get_param_index (parm, parms);
3411 adj->copy_param = 1;
3413 adj->remove_param = 1;
3417 struct ipa_parm_adjustment *adj;
3418 int index = get_param_index (parm, parms);
3420 for (; repr; repr = repr->next_grp)
3422 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3423 memset (adj, 0, sizeof (*adj));
3424 gcc_assert (repr->base == parm);
3425 adj->base_index = index;
3426 adj->base = repr->base;
3427 adj->type = repr->type;
3428 adj->offset = repr->offset;
3429 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3430 && (repr->grp_maybe_modified
3431 || repr->grp_not_necessarilly_dereferenced));
3436 VEC_free (tree, heap, parms);
3440 /* Analyze the collected accesses and produce a plan what to do with the
3441 parameters in the form of adjustments, NULL meaning nothing. */
3443 static ipa_parm_adjustment_vec
3444 analyze_all_param_acesses (void)
3446 enum ipa_splicing_result repr_state;
3447 bool proceed = false;
3448 int i, adjustments_count = 0;
3449 VEC (access_p, heap) *representatives;
3450 ipa_parm_adjustment_vec adjustments;
3452 repr_state = splice_all_param_accesses (&representatives);
3453 if (repr_state == NO_GOOD_ACCESS)
3456 /* If there are any parameters passed by reference which are not modified
3457 directly, we need to check whether they can be modified indirectly. */
3458 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3460 analyze_caller_dereference_legality (representatives);
3461 analyze_modified_params (representatives);
3464 for (i = 0; i < func_param_count; i++)
3466 struct access *repr = VEC_index (access_p, representatives, i);
3468 if (repr && !no_accesses_p (repr))
3470 if (repr->grp_scalar_ptr)
3472 adjustments_count++;
3473 if (repr->grp_not_necessarilly_dereferenced
3474 || repr->grp_maybe_modified)
3475 VEC_replace (access_p, representatives, i, NULL);
3479 sra_stats.scalar_by_ref_to_by_val++;
3484 int new_components = decide_one_param_reduction (repr);
3486 if (new_components == 0)
3488 VEC_replace (access_p, representatives, i, NULL);
3489 adjustments_count++;
3493 adjustments_count += new_components;
3494 sra_stats.aggregate_params_reduced++;
3495 sra_stats.param_reductions_created += new_components;
3502 if (no_accesses_p (repr))
3505 sra_stats.deleted_unused_parameters++;
3507 adjustments_count++;
3511 if (!proceed && dump_file)
3512 fprintf (dump_file, "NOT proceeding to change params.\n");
3515 adjustments = turn_representatives_into_adjustments (representatives,
3520 VEC_free (access_p, heap, representatives);
3524 /* If a parameter replacement identified by ADJ does not yet exist in the form
3525 of declaration, create it and record it, otherwise return the previously
3529 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3532 if (!adj->new_ssa_base)
3534 char *pretty_name = make_fancy_name (adj->base);
3536 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3537 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3538 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3539 DECL_GIMPLE_REG_P (repl) = 1;
3540 DECL_NAME (repl) = get_identifier (pretty_name);
3541 obstack_free (&name_obstack, pretty_name);
3544 add_referenced_var (repl);
3545 adj->new_ssa_base = repl;
3548 repl = adj->new_ssa_base;
3552 /* Find the first adjustment for a particular parameter BASE in a vector of
3553 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3556 static struct ipa_parm_adjustment *
3557 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3561 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3562 for (i = 0; i < len; i++)
3564 struct ipa_parm_adjustment *adj;
3566 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3567 if (!adj->copy_param && adj->base == base)
3574 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3575 parameter which is to be removed because its value is not used, replace the
3576 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3577 uses too and return true (update_stmt is then issued for the statement by
3578 the caller). DATA is a pointer to an adjustments vector. */
3581 replace_removed_params_ssa_names (gimple stmt, void *data)
3583 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3584 struct ipa_parm_adjustment *adj;
3585 tree lhs, decl, repl, name;
3587 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3588 if (gimple_code (stmt) == GIMPLE_PHI)
3589 lhs = gimple_phi_result (stmt);
3590 else if (is_gimple_assign (stmt))
3591 lhs = gimple_assign_lhs (stmt);
3592 else if (is_gimple_call (stmt))
3593 lhs = gimple_call_lhs (stmt);
3597 if (TREE_CODE (lhs) != SSA_NAME)
3599 decl = SSA_NAME_VAR (lhs);
3600 if (TREE_CODE (decl) != PARM_DECL)
3603 adj = get_adjustment_for_base (adjustments, decl);
3607 repl = get_replaced_param_substitute (adj);
3608 name = make_ssa_name (repl, stmt);
3612 fprintf (dump_file, "replacing an SSA name of a removed param ");
3613 print_generic_expr (dump_file, lhs, 0);
3614 fprintf (dump_file, " with ");
3615 print_generic_expr (dump_file, name, 0);
3616 fprintf (dump_file, "\n");
3619 if (is_gimple_assign (stmt))
3620 gimple_assign_set_lhs (stmt, name);
3621 else if (is_gimple_call (stmt))
3622 gimple_call_set_lhs (stmt, name);
3624 gimple_phi_set_result (stmt, name);
3626 replace_uses_by (lhs, name);
3630 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3631 expression *EXPR should be replaced by a reduction of a parameter, do so.
3632 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3633 whether the function should care about type incompatibility the current and
3634 new expressions. If it is true, the function will leave incompatibility
3635 issues to the caller.
3637 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3638 a write (LHS) expression. */
3641 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3642 bool dont_convert, void *data)
3644 ipa_parm_adjustment_vec adjustments;
3646 struct ipa_parm_adjustment *adj, *cand = NULL;
3647 HOST_WIDE_INT offset, size, max_size;
3650 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3651 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3653 if (TREE_CODE (*expr) == BIT_FIELD_REF
3654 || TREE_CODE (*expr) == IMAGPART_EXPR
3655 || TREE_CODE (*expr) == REALPART_EXPR)
3657 expr = &TREE_OPERAND (*expr, 0);
3658 dont_convert = false;
3661 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3662 if (!base || size == -1 || max_size == -1)
3665 if (INDIRECT_REF_P (base))
3666 base = TREE_OPERAND (base, 0);
3668 base = get_ssa_base_param (base);
3669 if (!base || TREE_CODE (base) != PARM_DECL)
3672 for (i = 0; i < len; i++)
3674 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3676 if (adj->base == base &&
3677 (adj->offset == offset || adj->remove_param))
3683 if (!cand || cand->copy_param || cand->remove_param)
3689 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3691 folded = gimple_fold_indirect_ref (src);
3696 src = cand->reduction;
3698 if (dump_file && (dump_flags & TDF_DETAILS))
3700 fprintf (dump_file, "About to replace expr ");
3701 print_generic_expr (dump_file, *expr, 0);
3702 fprintf (dump_file, " with ");
3703 print_generic_expr (dump_file, src, 0);
3704 fprintf (dump_file, "\n");
3708 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3710 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3718 /* Callback for scan_function to process assign statements. Performs
3719 essentially the same function like sra_ipa_modify_expr. */
3721 static enum scan_assign_result
3722 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3724 gimple stmt = *stmt_ptr;
3725 tree *lhs_p, *rhs_p;
3728 if (!gimple_assign_single_p (stmt))
3731 rhs_p = gimple_assign_rhs1_ptr (stmt);
3732 lhs_p = gimple_assign_lhs_ptr (stmt);
3734 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3735 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3738 tree new_rhs = NULL_TREE;
3740 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3742 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
3744 /* V_C_Es of constructors can cause trouble (PR 42714). */
3745 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
3746 *rhs_p = fold_convert (TREE_TYPE (*lhs_p), integer_zero_node);
3748 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
3751 new_rhs = fold_build1_loc (gimple_location (stmt),
3752 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
3755 else if (REFERENCE_CLASS_P (*rhs_p)
3756 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3757 && !is_gimple_reg (*lhs_p))
3758 /* This can happen when an assignment in between two single field
3759 structures is turned into an assignment in between two pointers to
3760 scalars (PR 42237). */
3765 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3766 true, GSI_SAME_STMT);
3768 gimple_assign_set_rhs_from_tree (gsi, tmp);
3771 return SRA_SA_PROCESSED;
3777 /* Call gimple_debug_bind_reset_value on all debug statements describing
3778 gimple register parameters that are being removed or replaced. */
3781 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3785 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3786 for (i = 0; i < len; i++)
3788 struct ipa_parm_adjustment *adj;
3789 imm_use_iterator ui;
3793 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3794 if (adj->copy_param || !is_gimple_reg (adj->base))
3796 name = gimple_default_def (cfun, adj->base);
3799 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3801 /* All other users must have been removed by scan_function. */
3802 gcc_assert (is_gimple_debug (stmt));
3803 gimple_debug_bind_reset_value (stmt);
3809 /* Return true iff all callers have at least as many actual arguments as there
3810 are formal parameters in the current function. */
3813 all_callers_have_enough_arguments_p (struct cgraph_node *node)
3815 struct cgraph_edge *cs;
3816 for (cs = node->callers; cs; cs = cs->next_caller)
3817 if (!callsite_has_enough_arguments_p (cs->call_stmt))
3824 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3827 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3829 tree old_cur_fndecl = current_function_decl;
3830 struct cgraph_edge *cs;
3831 basic_block this_block;
3832 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3834 for (cs = node->callers; cs; cs = cs->next_caller)
3836 current_function_decl = cs->caller->decl;
3837 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3840 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3841 cs->caller->uid, cs->callee->uid,
3842 cgraph_node_name (cs->caller),
3843 cgraph_node_name (cs->callee));
3845 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3850 for (cs = node->callers; cs; cs = cs->next_caller)
3851 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3853 compute_inline_parameters (cs->caller);
3854 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3856 BITMAP_FREE (recomputed_callers);
3858 current_function_decl = old_cur_fndecl;
3860 if (!encountered_recursive_call)
3863 FOR_EACH_BB (this_block)
3865 gimple_stmt_iterator gsi;
3867 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3869 gimple stmt = gsi_stmt (gsi);
3871 if (gimple_code (stmt) != GIMPLE_CALL)
3873 call_fndecl = gimple_call_fndecl (stmt);
3874 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
3877 fprintf (dump_file, "Adjusting recursive call");
3878 ipa_modify_call_arguments (NULL, stmt, adjustments);
3886 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3887 as given in ADJUSTMENTS. */
3890 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3892 struct cgraph_node *alias;
3893 for (alias = node->same_body; alias; alias = alias->next)
3894 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
3895 /* current_function_decl must be handled last, after same_body aliases,
3896 as following functions will use what it computed. */
3897 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3898 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3899 replace_removed_params_ssa_names, false, adjustments);
3900 sra_ipa_reset_debug_stmts (adjustments);
3901 convert_callers (node, adjustments);
3902 cgraph_make_node_local (node);
3906 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3907 attributes, return true otherwise. NODE is the cgraph node of the current
3911 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3913 if (!cgraph_node_can_be_local_p (node))
3916 fprintf (dump_file, "Function not local to this compilation unit.\n");
3920 if (DECL_VIRTUAL_P (current_function_decl))
3923 fprintf (dump_file, "Function is a virtual method.\n");
3927 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3928 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3931 fprintf (dump_file, "Function too big to be made truly local.\n");
3939 "Function has no callers in this compilation unit.\n");
3946 fprintf (dump_file, "Function uses stdarg. \n");
3953 /* Perform early interprocedural SRA. */
3956 ipa_early_sra (void)
3958 struct cgraph_node *node = cgraph_node (current_function_decl);
3959 ipa_parm_adjustment_vec adjustments;
3962 if (!ipa_sra_preliminary_function_checks (node))
3966 sra_mode = SRA_MODE_EARLY_IPA;
3968 if (!find_param_candidates ())
3971 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3975 if (!all_callers_have_enough_arguments_p (node))
3978 fprintf (dump_file, "There are callers with insufficient number of "
3983 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3985 * last_basic_block_for_function (cfun));
3986 final_bbs = BITMAP_ALLOC (NULL);
3988 scan_function (build_access_from_expr, build_accesses_from_assign,
3990 if (encountered_apply_args)
3993 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3997 if (encountered_unchangable_recursive_call)
4000 fprintf (dump_file, "Function calls itself with insufficient "
4001 "number of arguments.\n");
4005 adjustments = analyze_all_param_acesses ();
4009 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4011 modify_function (node, adjustments);
4012 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4013 ret = TODO_update_ssa;
4015 statistics_counter_event (cfun, "Unused parameters deleted",
4016 sra_stats.deleted_unused_parameters);
4017 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4018 sra_stats.scalar_by_ref_to_by_val);
4019 statistics_counter_event (cfun, "Aggregate parameters broken up",
4020 sra_stats.aggregate_params_reduced);
4021 statistics_counter_event (cfun, "Aggregate parameter components created",
4022 sra_stats.param_reductions_created);
4025 BITMAP_FREE (final_bbs);
4026 free (bb_dereferences);
4028 sra_deinitialize ();
4032 /* Return if early ipa sra shall be performed. */
4034 ipa_early_sra_gate (void)
4036 return flag_ipa_sra;
4039 struct gimple_opt_pass pass_early_ipa_sra =
4043 "eipa_sra", /* name */
4044 ipa_early_sra_gate, /* gate */
4045 ipa_early_sra, /* execute */
4048 0, /* static_pass_number */
4049 TV_IPA_SRA, /* tv_id */
4050 0, /* properties_required */
4051 0, /* properties_provided */
4052 0, /* properties_destroyed */
4053 0, /* todo_flags_start */
4054 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */