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);
1296 else if (pos > offset || (pos + size) <= offset)
1301 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1307 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1308 offset - pos, exp_type))
1318 tr_size = TYPE_SIZE (TREE_TYPE (type));
1319 if (!tr_size || !host_integerp (tr_size, 1))
1321 el_size = tree_low_cst (tr_size, 1);
1323 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1324 if (TREE_CODE (minidx) != INTEGER_CST)
1328 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1329 if (!integer_zerop (minidx))
1330 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1331 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1332 NULL_TREE, NULL_TREE);
1334 offset = offset % el_size;
1335 type = TREE_TYPE (type);
1350 /* Construct an expression that would reference a part of aggregate *EXPR of
1351 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1352 function only determines whether it can build such a reference without
1353 actually doing it, otherwise, the tree it points to is unshared first and
1354 then used as a base for furhter sub-references.
1356 FIXME: Eventually this should be replaced with
1357 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1358 minor rewrite of fold_stmt.
1362 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1363 tree exp_type, bool allow_ptr)
1365 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1368 *expr = unshare_expr (*expr);
1370 if (allow_ptr && POINTER_TYPE_P (type))
1372 type = TREE_TYPE (type);
1374 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1377 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1380 /* Return true iff TYPE is stdarg va_list type. */
1383 is_va_list_type (tree type)
1385 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1388 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1389 those with type which is suitable for scalarization. */
1392 find_var_candidates (void)
1395 referenced_var_iterator rvi;
1398 FOR_EACH_REFERENCED_VAR (var, rvi)
1400 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1402 type = TREE_TYPE (var);
1404 if (!AGGREGATE_TYPE_P (type)
1405 || needs_to_live_in_memory (var)
1406 || TREE_THIS_VOLATILE (var)
1407 || !COMPLETE_TYPE_P (type)
1408 || !host_integerp (TYPE_SIZE (type), 1)
1409 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1410 || type_internals_preclude_sra_p (type)
1411 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1412 we also want to schedule it rather late. Thus we ignore it in
1414 || (sra_mode == SRA_MODE_EARLY_INTRA
1415 && is_va_list_type (type)))
1418 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1420 if (dump_file && (dump_flags & TDF_DETAILS))
1422 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1423 print_generic_expr (dump_file, var, 0);
1424 fprintf (dump_file, "\n");
1432 /* Sort all accesses for the given variable, check for partial overlaps and
1433 return NULL if there are any. If there are none, pick a representative for
1434 each combination of offset and size and create a linked list out of them.
1435 Return the pointer to the first representative and make sure it is the first
1436 one in the vector of accesses. */
1438 static struct access *
1439 sort_and_splice_var_accesses (tree var)
1441 int i, j, access_count;
1442 struct access *res, **prev_acc_ptr = &res;
1443 VEC (access_p, heap) *access_vec;
1445 HOST_WIDE_INT low = -1, high = 0;
1447 access_vec = get_base_access_vector (var);
1450 access_count = VEC_length (access_p, access_vec);
1452 /* Sort by <OFFSET, SIZE>. */
1453 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1454 compare_access_positions);
1457 while (i < access_count)
1459 struct access *access = VEC_index (access_p, access_vec, i);
1460 bool grp_write = access->write;
1461 bool grp_read = !access->write;
1462 bool multiple_reads = false;
1463 bool grp_partial_lhs = access->grp_partial_lhs;
1464 bool first_scalar = is_gimple_reg_type (access->type);
1465 bool unscalarizable_region = access->grp_unscalarizable_region;
1467 if (first || access->offset >= high)
1470 low = access->offset;
1471 high = access->offset + access->size;
1473 else if (access->offset > low && access->offset + access->size > high)
1476 gcc_assert (access->offset >= low
1477 && access->offset + access->size <= high);
1480 while (j < access_count)
1482 struct access *ac2 = VEC_index (access_p, access_vec, j);
1483 if (ac2->offset != access->offset || ac2->size != access->size)
1490 multiple_reads = true;
1494 grp_partial_lhs |= ac2->grp_partial_lhs;
1495 unscalarizable_region |= ac2->grp_unscalarizable_region;
1496 relink_to_new_repr (access, ac2);
1498 /* If there are both aggregate-type and scalar-type accesses with
1499 this combination of size and offset, the comparison function
1500 should have put the scalars first. */
1501 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1502 ac2->group_representative = access;
1508 access->group_representative = access;
1509 access->grp_write = grp_write;
1510 access->grp_read = grp_read;
1511 access->grp_hint = multiple_reads;
1512 access->grp_partial_lhs = grp_partial_lhs;
1513 access->grp_unscalarizable_region = unscalarizable_region;
1514 if (access->first_link)
1515 add_access_to_work_queue (access);
1517 *prev_acc_ptr = access;
1518 prev_acc_ptr = &access->next_grp;
1521 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1525 /* Create a variable for the given ACCESS which determines the type, name and a
1526 few other properties. Return the variable declaration and store it also to
1527 ACCESS->replacement. */
1530 create_access_replacement (struct access *access)
1534 repl = create_tmp_var (access->type, "SR");
1536 add_referenced_var (repl);
1537 mark_sym_for_renaming (repl);
1539 if (!access->grp_partial_lhs
1540 && (TREE_CODE (access->type) == COMPLEX_TYPE
1541 || TREE_CODE (access->type) == VECTOR_TYPE))
1542 DECL_GIMPLE_REG_P (repl) = 1;
1544 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1545 DECL_ARTIFICIAL (repl) = 1;
1547 if (DECL_NAME (access->base)
1548 && !DECL_IGNORED_P (access->base)
1549 && !DECL_ARTIFICIAL (access->base))
1551 char *pretty_name = make_fancy_name (access->expr);
1553 DECL_NAME (repl) = get_identifier (pretty_name);
1554 obstack_free (&name_obstack, pretty_name);
1556 SET_DECL_DEBUG_EXPR (repl, access->expr);
1557 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1558 DECL_IGNORED_P (repl) = 0;
1561 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1562 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1566 fprintf (dump_file, "Created a replacement for ");
1567 print_generic_expr (dump_file, access->base, 0);
1568 fprintf (dump_file, " offset: %u, size: %u: ",
1569 (unsigned) access->offset, (unsigned) access->size);
1570 print_generic_expr (dump_file, repl, 0);
1571 fprintf (dump_file, "\n");
1573 sra_stats.replacements++;
1578 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1581 get_access_replacement (struct access *access)
1583 gcc_assert (access->grp_to_be_replaced);
1585 if (!access->replacement_decl)
1586 access->replacement_decl = create_access_replacement (access);
1587 return access->replacement_decl;
1590 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1591 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1592 to it is not "within" the root. */
1595 build_access_subtree (struct access **access)
1597 struct access *root = *access, *last_child = NULL;
1598 HOST_WIDE_INT limit = root->offset + root->size;
1600 *access = (*access)->next_grp;
1601 while (*access && (*access)->offset + (*access)->size <= limit)
1604 root->first_child = *access;
1606 last_child->next_sibling = *access;
1607 last_child = *access;
1609 build_access_subtree (access);
1613 /* Build a tree of access representatives, ACCESS is the pointer to the first
1614 one, others are linked in a list by the next_grp field. Decide about scalar
1615 replacements on the way, return true iff any are to be created. */
1618 build_access_trees (struct access *access)
1622 struct access *root = access;
1624 build_access_subtree (&access);
1625 root->next_grp = access;
1629 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1633 expr_with_var_bounded_array_refs_p (tree expr)
1635 while (handled_component_p (expr))
1637 if (TREE_CODE (expr) == ARRAY_REF
1638 && !host_integerp (array_ref_low_bound (expr), 0))
1640 expr = TREE_OPERAND (expr, 0);
1645 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1646 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1647 all sorts of access flags appropriately along the way, notably always ser
1648 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1651 analyze_access_subtree (struct access *root, bool allow_replacements,
1652 bool mark_read, bool mark_write)
1654 struct access *child;
1655 HOST_WIDE_INT limit = root->offset + root->size;
1656 HOST_WIDE_INT covered_to = root->offset;
1657 bool scalar = is_gimple_reg_type (root->type);
1658 bool hole = false, sth_created = false;
1659 bool direct_read = root->grp_read;
1662 root->grp_read = true;
1663 else if (root->grp_read)
1667 root->grp_write = true;
1668 else if (root->grp_write)
1671 if (root->grp_unscalarizable_region)
1672 allow_replacements = false;
1674 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1675 allow_replacements = false;
1677 for (child = root->first_child; child; child = child->next_sibling)
1679 if (!hole && child->offset < covered_to)
1682 covered_to += child->size;
1684 sth_created |= analyze_access_subtree (child, allow_replacements,
1685 mark_read, mark_write);
1687 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1688 hole |= !child->grp_covered;
1691 if (allow_replacements && scalar && !root->first_child
1693 || (direct_read && root->grp_write))
1694 /* We must not ICE later on when trying to build an access to the
1695 original data within the aggregate even when it is impossible to do in
1696 a defined way like in the PR 42703 testcase. Therefore we check
1697 pre-emptively here that we will be able to do that. */
1698 && build_ref_for_offset (NULL, TREE_TYPE (root->base), root->offset,
1701 if (dump_file && (dump_flags & TDF_DETAILS))
1703 fprintf (dump_file, "Marking ");
1704 print_generic_expr (dump_file, root->base, 0);
1705 fprintf (dump_file, " offset: %u, size: %u: ",
1706 (unsigned) root->offset, (unsigned) root->size);
1707 fprintf (dump_file, " to be replaced.\n");
1710 root->grp_to_be_replaced = 1;
1714 else if (covered_to < limit)
1717 if (sth_created && !hole)
1719 root->grp_covered = 1;
1722 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1723 root->grp_unscalarized_data = 1; /* not covered and written to */
1729 /* Analyze all access trees linked by next_grp by the means of
1730 analyze_access_subtree. */
1732 analyze_access_trees (struct access *access)
1738 if (analyze_access_subtree (access, true, false, false))
1740 access = access->next_grp;
1746 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1747 SIZE would conflict with an already existing one. If exactly such a child
1748 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1751 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1752 HOST_WIDE_INT size, struct access **exact_match)
1754 struct access *child;
1756 for (child = lacc->first_child; child; child = child->next_sibling)
1758 if (child->offset == norm_offset && child->size == size)
1760 *exact_match = child;
1764 if (child->offset < norm_offset + size
1765 && child->offset + child->size > norm_offset)
1772 /* Create a new child access of PARENT, with all properties just like MODEL
1773 except for its offset and with its grp_write false and grp_read true.
1774 Return the new access or NULL if it cannot be created. Note that this access
1775 is created long after all splicing and sorting, it's not located in any
1776 access vector and is automatically a representative of its group. */
1778 static struct access *
1779 create_artificial_child_access (struct access *parent, struct access *model,
1780 HOST_WIDE_INT new_offset)
1782 struct access *access;
1783 struct access **child;
1784 tree expr = parent->base;;
1786 gcc_assert (!model->grp_unscalarizable_region);
1788 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1789 model->type, false))
1792 access = (struct access *) pool_alloc (access_pool);
1793 memset (access, 0, sizeof (struct access));
1794 access->base = parent->base;
1795 access->expr = expr;
1796 access->offset = new_offset;
1797 access->size = model->size;
1798 access->type = model->type;
1799 access->grp_write = true;
1800 access->grp_read = false;
1802 child = &parent->first_child;
1803 while (*child && (*child)->offset < new_offset)
1804 child = &(*child)->next_sibling;
1806 access->next_sibling = *child;
1813 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1814 true if any new subaccess was created. Additionally, if RACC is a scalar
1815 access but LACC is not, change the type of the latter, if possible. */
1818 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1820 struct access *rchild;
1821 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1824 if (is_gimple_reg_type (lacc->type)
1825 || lacc->grp_unscalarizable_region
1826 || racc->grp_unscalarizable_region)
1829 if (!lacc->first_child && !racc->first_child
1830 && is_gimple_reg_type (racc->type))
1832 tree t = lacc->base;
1834 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1838 lacc->type = racc->type;
1843 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1845 struct access *new_acc = NULL;
1846 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1848 if (rchild->grp_unscalarizable_region)
1851 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1856 rchild->grp_hint = 1;
1857 new_acc->grp_hint |= new_acc->grp_read;
1858 if (rchild->first_child)
1859 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1864 /* If a (part of) a union field is on the RHS of an assignment, it can
1865 have sub-accesses which do not make sense on the LHS (PR 40351).
1866 Check that this is not the case. */
1867 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1868 rchild->type, false))
1871 rchild->grp_hint = 1;
1872 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1876 if (racc->first_child)
1877 propagate_subaccesses_across_link (new_acc, rchild);
1884 /* Propagate all subaccesses across assignment links. */
1887 propagate_all_subaccesses (void)
1889 while (work_queue_head)
1891 struct access *racc = pop_access_from_work_queue ();
1892 struct assign_link *link;
1894 gcc_assert (racc->first_link);
1896 for (link = racc->first_link; link; link = link->next)
1898 struct access *lacc = link->lacc;
1900 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1902 lacc = lacc->group_representative;
1903 if (propagate_subaccesses_across_link (lacc, racc)
1904 && lacc->first_link)
1905 add_access_to_work_queue (lacc);
1910 /* Go through all accesses collected throughout the (intraprocedural) analysis
1911 stage, exclude overlapping ones, identify representatives and build trees
1912 out of them, making decisions about scalarization on the way. Return true
1913 iff there are any to-be-scalarized variables after this stage. */
1916 analyze_all_variable_accesses (void)
1919 bitmap tmp = BITMAP_ALLOC (NULL);
1923 bitmap_copy (tmp, candidate_bitmap);
1924 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1926 tree var = referenced_var (i);
1927 struct access *access;
1929 access = sort_and_splice_var_accesses (var);
1931 build_access_trees (access);
1933 disqualify_candidate (var,
1934 "No or inhibitingly overlapping accesses.");
1937 propagate_all_subaccesses ();
1939 bitmap_copy (tmp, candidate_bitmap);
1940 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1942 tree var = referenced_var (i);
1943 struct access *access = get_first_repr_for_decl (var);
1945 if (analyze_access_trees (access))
1948 if (dump_file && (dump_flags & TDF_DETAILS))
1950 fprintf (dump_file, "\nAccess trees for ");
1951 print_generic_expr (dump_file, var, 0);
1952 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1953 dump_access_tree (dump_file, access);
1954 fprintf (dump_file, "\n");
1958 disqualify_candidate (var, "No scalar replacements to be created.");
1965 statistics_counter_event (cfun, "Scalarized aggregates", res);
1972 /* Return true iff a reference statement into aggregate AGG can be built for
1973 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1974 or a child of its sibling. TOP_OFFSET is the offset from the processed
1975 access subtree that has to be subtracted from offset of each access. */
1978 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1979 HOST_WIDE_INT top_offset)
1983 if (access->grp_to_be_replaced
1984 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1985 access->offset - top_offset,
1986 access->type, false))
1989 if (access->first_child
1990 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1994 access = access->next_sibling;
2001 /* Generate statements copying scalar replacements of accesses within a subtree
2002 into or out of AGG. ACCESS is the first child of the root of the subtree to
2003 be processed. AGG is an aggregate type expression (can be a declaration but
2004 does not have to be, it can for example also be an indirect_ref).
2005 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2006 from offsets of individual accesses to get corresponding offsets for AGG.
2007 If CHUNK_SIZE is non-null, copy only replacements in the interval
2008 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2009 statement iterator used to place the new statements. WRITE should be true
2010 when the statements should write from AGG to the replacement and false if
2011 vice versa. if INSERT_AFTER is true, new statements will be added after the
2012 current statement in GSI, they will be added before the statement
2016 generate_subtree_copies (struct access *access, tree agg,
2017 HOST_WIDE_INT top_offset,
2018 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2019 gimple_stmt_iterator *gsi, bool write,
2026 if (chunk_size && access->offset >= start_offset + chunk_size)
2029 if (access->grp_to_be_replaced
2031 || access->offset + access->size > start_offset))
2033 tree repl = get_access_replacement (access);
2037 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2038 access->offset - top_offset,
2039 access->type, false);
2040 gcc_assert (ref_found);
2044 if (access->grp_partial_lhs)
2045 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2047 insert_after ? GSI_NEW_STMT
2049 stmt = gimple_build_assign (repl, expr);
2053 TREE_NO_WARNING (repl) = 1;
2054 if (access->grp_partial_lhs)
2055 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2057 insert_after ? GSI_NEW_STMT
2059 stmt = gimple_build_assign (expr, repl);
2063 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2065 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2067 sra_stats.subtree_copies++;
2070 if (access->first_child)
2071 generate_subtree_copies (access->first_child, agg, top_offset,
2072 start_offset, chunk_size, gsi,
2073 write, insert_after);
2075 access = access->next_sibling;
2080 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2081 the root of the subtree to be processed. GSI is the statement iterator used
2082 for inserting statements which are added after the current statement if
2083 INSERT_AFTER is true or before it otherwise. */
2086 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2090 struct access *child;
2092 if (access->grp_to_be_replaced)
2096 stmt = gimple_build_assign (get_access_replacement (access),
2097 fold_convert (access->type,
2098 integer_zero_node));
2100 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2102 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2106 for (child = access->first_child; child; child = child->next_sibling)
2107 init_subtree_with_zero (child, gsi, insert_after);
2110 /* Search for an access representative for the given expression EXPR and
2111 return it or NULL if it cannot be found. */
2113 static struct access *
2114 get_access_for_expr (tree expr)
2116 HOST_WIDE_INT offset, size, max_size;
2119 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2120 a different size than the size of its argument and we need the latter
2122 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2123 expr = TREE_OPERAND (expr, 0);
2125 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2126 if (max_size == -1 || !DECL_P (base))
2129 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2132 return get_var_base_offset_size_access (base, offset, max_size);
2135 /* Callback for scan_function. Replace the expression EXPR with a scalar
2136 replacement if there is one and generate other statements to do type
2137 conversion or subtree copying if necessary. GSI is used to place newly
2138 created statements, WRITE is true if the expression is being written to (it
2139 is on a LHS of a statement or output in an assembly statement). */
2142 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2143 void *data ATTRIBUTE_UNUSED)
2145 struct access *access;
2148 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2151 expr = &TREE_OPERAND (*expr, 0);
2156 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2157 expr = &TREE_OPERAND (*expr, 0);
2158 access = get_access_for_expr (*expr);
2161 type = TREE_TYPE (*expr);
2163 if (access->grp_to_be_replaced)
2165 tree repl = get_access_replacement (access);
2166 /* If we replace a non-register typed access simply use the original
2167 access expression to extract the scalar component afterwards.
2168 This happens if scalarizing a function return value or parameter
2169 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2170 gcc.c-torture/compile/20011217-1.c.
2172 We also want to use this when accessing a complex or vector which can
2173 be accessed as a different type too, potentially creating a need for
2174 type conversion (see PR42196) and when scalarized unions are involved
2175 in assembler statements (see PR42398). */
2176 if (!useless_type_conversion_p (type, access->type))
2178 tree ref = access->base;
2181 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2182 access->offset, access->type, false);
2189 if (access->grp_partial_lhs)
2190 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2191 false, GSI_NEW_STMT);
2192 stmt = gimple_build_assign (repl, ref);
2193 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2199 if (access->grp_partial_lhs)
2200 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2201 true, GSI_SAME_STMT);
2202 stmt = gimple_build_assign (ref, repl);
2203 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2211 if (access->first_child)
2213 HOST_WIDE_INT start_offset, chunk_size;
2215 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2216 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2218 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2219 start_offset = access->offset
2220 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2223 start_offset = chunk_size = 0;
2225 generate_subtree_copies (access->first_child, access->base, 0,
2226 start_offset, chunk_size, gsi, write, write);
2231 /* Where scalar replacements of the RHS have been written to when a replacement
2232 of a LHS of an assigments cannot be direclty loaded from a replacement of
2234 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2235 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2236 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2238 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2239 base aggregate if there are unscalarized data or directly to LHS
2242 static enum unscalarized_data_handling
2243 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2244 gimple_stmt_iterator *gsi)
2246 if (top_racc->grp_unscalarized_data)
2248 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2250 return SRA_UDH_RIGHT;
2254 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2255 0, 0, gsi, false, false);
2256 return SRA_UDH_LEFT;
2261 /* Try to generate statements to load all sub-replacements in an access
2262 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2263 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2264 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2265 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2266 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2267 the rhs top aggregate has already been refreshed by contents of its scalar
2268 reductions and is set to true if this function has to do it. */
2271 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2272 HOST_WIDE_INT left_offset,
2273 HOST_WIDE_INT right_offset,
2274 gimple_stmt_iterator *old_gsi,
2275 gimple_stmt_iterator *new_gsi,
2276 enum unscalarized_data_handling *refreshed,
2279 location_t loc = EXPR_LOCATION (lacc->expr);
2282 if (lacc->grp_to_be_replaced)
2284 struct access *racc;
2285 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2289 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2290 if (racc && racc->grp_to_be_replaced)
2292 rhs = get_access_replacement (racc);
2293 if (!useless_type_conversion_p (lacc->type, racc->type))
2294 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2298 /* No suitable access on the right hand side, need to load from
2299 the aggregate. See if we have to update it first... */
2300 if (*refreshed == SRA_UDH_NONE)
2301 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2304 if (*refreshed == SRA_UDH_LEFT)
2309 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2310 lacc->offset, lacc->type,
2312 gcc_assert (repl_found);
2318 rhs = top_racc->base;
2319 repl_found = build_ref_for_offset (&rhs,
2320 TREE_TYPE (top_racc->base),
2321 offset, lacc->type, false);
2322 gcc_assert (repl_found);
2326 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2327 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2329 sra_stats.subreplacements++;
2331 else if (*refreshed == SRA_UDH_NONE
2332 && lacc->grp_read && !lacc->grp_covered)
2333 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2336 if (lacc->first_child)
2337 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2338 left_offset, right_offset,
2339 old_gsi, new_gsi, refreshed, lhs);
2340 lacc = lacc->next_sibling;
2345 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2346 to the assignment and GSI is the statement iterator pointing at it. Returns
2347 the same values as sra_modify_assign. */
2349 static enum scan_assign_result
2350 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2352 tree lhs = gimple_assign_lhs (*stmt);
2355 acc = get_access_for_expr (lhs);
2359 if (VEC_length (constructor_elt,
2360 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2362 /* I have never seen this code path trigger but if it can happen the
2363 following should handle it gracefully. */
2364 if (access_has_children_p (acc))
2365 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2367 return SRA_SA_PROCESSED;
2370 if (acc->grp_covered)
2372 init_subtree_with_zero (acc, gsi, false);
2373 unlink_stmt_vdef (*stmt);
2374 gsi_remove (gsi, true);
2375 return SRA_SA_REMOVED;
2379 init_subtree_with_zero (acc, gsi, true);
2380 return SRA_SA_PROCESSED;
2385 /* Callback of scan_function to process assign statements. It examines both
2386 sides of the statement, replaces them with a scalare replacement if there is
2387 one and generating copying of replacements if scalarized aggregates have been
2388 used in the assignment. STMT is a pointer to the assign statement, GSI is
2389 used to hold generated statements for type conversions and subtree
2392 static enum scan_assign_result
2393 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2394 void *data ATTRIBUTE_UNUSED)
2396 struct access *lacc, *racc;
2398 bool modify_this_stmt = false;
2399 bool force_gimple_rhs = false;
2400 location_t loc = gimple_location (*stmt);
2402 if (!gimple_assign_single_p (*stmt))
2404 lhs = gimple_assign_lhs (*stmt);
2405 rhs = gimple_assign_rhs1 (*stmt);
2407 if (TREE_CODE (rhs) == CONSTRUCTOR)
2408 return sra_modify_constructor_assign (stmt, gsi);
2410 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2411 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2412 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2414 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2416 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2418 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2421 lacc = get_access_for_expr (lhs);
2422 racc = get_access_for_expr (rhs);
2426 if (lacc && lacc->grp_to_be_replaced)
2428 lhs = get_access_replacement (lacc);
2429 gimple_assign_set_lhs (*stmt, lhs);
2430 modify_this_stmt = true;
2431 if (lacc->grp_partial_lhs)
2432 force_gimple_rhs = true;
2436 if (racc && racc->grp_to_be_replaced)
2438 rhs = get_access_replacement (racc);
2439 modify_this_stmt = true;
2440 if (racc->grp_partial_lhs)
2441 force_gimple_rhs = true;
2445 if (modify_this_stmt)
2447 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2449 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2450 ??? This should move to fold_stmt which we simply should
2451 call after building a VIEW_CONVERT_EXPR here. */
2452 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2453 && !access_has_children_p (lacc))
2456 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2457 TREE_TYPE (rhs), false))
2460 gimple_assign_set_lhs (*stmt, expr);
2463 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2464 && !access_has_children_p (racc))
2467 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2468 TREE_TYPE (lhs), false))
2471 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2473 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2474 if (is_gimple_reg_type (TREE_TYPE (lhs))
2475 && TREE_CODE (lhs) != SSA_NAME)
2476 force_gimple_rhs = true;
2480 if (force_gimple_rhs)
2481 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2482 true, GSI_SAME_STMT);
2483 if (gimple_assign_rhs1 (*stmt) != rhs)
2485 gimple_assign_set_rhs_from_tree (gsi, rhs);
2486 gcc_assert (*stmt == gsi_stmt (*gsi));
2490 /* From this point on, the function deals with assignments in between
2491 aggregates when at least one has scalar reductions of some of its
2492 components. There are three possible scenarios: Both the LHS and RHS have
2493 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2495 In the first case, we would like to load the LHS components from RHS
2496 components whenever possible. If that is not possible, we would like to
2497 read it directly from the RHS (after updating it by storing in it its own
2498 components). If there are some necessary unscalarized data in the LHS,
2499 those will be loaded by the original assignment too. If neither of these
2500 cases happen, the original statement can be removed. Most of this is done
2501 by load_assign_lhs_subreplacements.
2503 In the second case, we would like to store all RHS scalarized components
2504 directly into LHS and if they cover the aggregate completely, remove the
2505 statement too. In the third case, we want the LHS components to be loaded
2506 directly from the RHS (DSE will remove the original statement if it
2509 This is a bit complex but manageable when types match and when unions do
2510 not cause confusion in a way that we cannot really load a component of LHS
2511 from the RHS or vice versa (the access representing this level can have
2512 subaccesses that are accessible only through a different union field at a
2513 higher level - different from the one used in the examined expression).
2516 Therefore, I specially handle a fourth case, happening when there is a
2517 specific type cast or it is impossible to locate a scalarized subaccess on
2518 the other side of the expression. If that happens, I simply "refresh" the
2519 RHS by storing in it is scalarized components leave the original statement
2520 there to do the copying and then load the scalar replacements of the LHS.
2521 This is what the first branch does. */
2523 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2524 || (access_has_children_p (racc)
2525 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2526 || (access_has_children_p (lacc)
2527 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2529 if (access_has_children_p (racc))
2530 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2532 if (access_has_children_p (lacc))
2533 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2535 sra_stats.separate_lhs_rhs_handling++;
2539 if (access_has_children_p (lacc) && access_has_children_p (racc))
2541 gimple_stmt_iterator orig_gsi = *gsi;
2542 enum unscalarized_data_handling refreshed;
2544 if (lacc->grp_read && !lacc->grp_covered)
2545 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2547 refreshed = SRA_UDH_NONE;
2549 load_assign_lhs_subreplacements (lacc->first_child, racc,
2550 lacc->offset, racc->offset,
2551 &orig_gsi, gsi, &refreshed, lhs);
2552 if (refreshed != SRA_UDH_RIGHT)
2554 if (*stmt == gsi_stmt (*gsi))
2557 unlink_stmt_vdef (*stmt);
2558 gsi_remove (&orig_gsi, true);
2559 sra_stats.deleted++;
2560 return SRA_SA_REMOVED;
2565 if (access_has_children_p (racc))
2567 if (!racc->grp_unscalarized_data
2568 /* Do not remove SSA name definitions (PR 42704). */
2569 && TREE_CODE (lhs) != SSA_NAME)
2571 generate_subtree_copies (racc->first_child, lhs,
2572 racc->offset, 0, 0, gsi,
2574 gcc_assert (*stmt == gsi_stmt (*gsi));
2575 unlink_stmt_vdef (*stmt);
2576 gsi_remove (gsi, true);
2577 sra_stats.deleted++;
2578 return SRA_SA_REMOVED;
2581 generate_subtree_copies (racc->first_child, lhs,
2582 racc->offset, 0, 0, gsi, false, true);
2584 else if (access_has_children_p (lacc))
2585 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2586 0, 0, gsi, true, true);
2589 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2592 /* Generate statements initializing scalar replacements of parts of function
2596 initialize_parameter_reductions (void)
2598 gimple_stmt_iterator gsi;
2599 gimple_seq seq = NULL;
2602 for (parm = DECL_ARGUMENTS (current_function_decl);
2604 parm = TREE_CHAIN (parm))
2606 VEC (access_p, heap) *access_vec;
2607 struct access *access;
2609 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2611 access_vec = get_base_access_vector (parm);
2617 seq = gimple_seq_alloc ();
2618 gsi = gsi_start (seq);
2621 for (access = VEC_index (access_p, access_vec, 0);
2623 access = access->next_grp)
2624 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2628 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2631 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2632 it reveals there are components of some aggregates to be scalarized, it runs
2633 the required transformations. */
2635 perform_intra_sra (void)
2640 if (!find_var_candidates ())
2643 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2647 if (!analyze_all_variable_accesses ())
2650 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2651 initialize_parameter_reductions ();
2653 statistics_counter_event (cfun, "Scalar replacements created",
2654 sra_stats.replacements);
2655 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2656 statistics_counter_event (cfun, "Subtree copy stmts",
2657 sra_stats.subtree_copies);
2658 statistics_counter_event (cfun, "Subreplacement stmts",
2659 sra_stats.subreplacements);
2660 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2661 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2662 sra_stats.separate_lhs_rhs_handling);
2664 ret = TODO_update_ssa;
2667 sra_deinitialize ();
2671 /* Perform early intraprocedural SRA. */
2673 early_intra_sra (void)
2675 sra_mode = SRA_MODE_EARLY_INTRA;
2676 return perform_intra_sra ();
2679 /* Perform "late" intraprocedural SRA. */
2681 late_intra_sra (void)
2683 sra_mode = SRA_MODE_INTRA;
2684 return perform_intra_sra ();
2689 gate_intra_sra (void)
2691 return flag_tree_sra != 0;
2695 struct gimple_opt_pass pass_sra_early =
2700 gate_intra_sra, /* gate */
2701 early_intra_sra, /* execute */
2704 0, /* static_pass_number */
2705 TV_TREE_SRA, /* tv_id */
2706 PROP_cfg | PROP_ssa, /* properties_required */
2707 0, /* properties_provided */
2708 0, /* properties_destroyed */
2709 0, /* todo_flags_start */
2713 | TODO_verify_ssa /* todo_flags_finish */
2717 struct gimple_opt_pass pass_sra =
2722 gate_intra_sra, /* gate */
2723 late_intra_sra, /* execute */
2726 0, /* static_pass_number */
2727 TV_TREE_SRA, /* tv_id */
2728 PROP_cfg | PROP_ssa, /* properties_required */
2729 0, /* properties_provided */
2730 0, /* properties_destroyed */
2731 TODO_update_address_taken, /* todo_flags_start */
2735 | TODO_verify_ssa /* todo_flags_finish */
2740 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2744 is_unused_scalar_param (tree parm)
2747 return (is_gimple_reg (parm)
2748 && (!(name = gimple_default_def (cfun, parm))
2749 || has_zero_uses (name)));
2752 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2753 examine whether there are any direct or otherwise infeasible ones. If so,
2754 return true, otherwise return false. PARM must be a gimple register with a
2755 non-NULL default definition. */
2758 ptr_parm_has_direct_uses (tree parm)
2760 imm_use_iterator ui;
2762 tree name = gimple_default_def (cfun, parm);
2765 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2767 if (gimple_assign_single_p (stmt))
2769 tree rhs = gimple_assign_rhs1 (stmt);
2772 else if (TREE_CODE (rhs) == ADDR_EXPR)
2776 rhs = TREE_OPERAND (rhs, 0);
2778 while (handled_component_p (rhs));
2779 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2783 else if (gimple_code (stmt) == GIMPLE_RETURN)
2785 tree t = gimple_return_retval (stmt);
2789 else if (is_gimple_call (stmt))
2792 for (i = 0; i < gimple_call_num_args (stmt); i++)
2794 tree arg = gimple_call_arg (stmt, i);
2802 else if (!is_gimple_debug (stmt))
2806 BREAK_FROM_IMM_USE_STMT (ui);
2812 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2813 them in candidate_bitmap. Note that these do not necessarily include
2814 parameter which are unused and thus can be removed. Return true iff any
2815 such candidate has been found. */
2818 find_param_candidates (void)
2824 for (parm = DECL_ARGUMENTS (current_function_decl);
2826 parm = TREE_CHAIN (parm))
2828 tree type = TREE_TYPE (parm);
2832 if (TREE_THIS_VOLATILE (parm)
2833 || TREE_ADDRESSABLE (parm)
2834 || is_va_list_type (type))
2837 if (is_unused_scalar_param (parm))
2843 if (POINTER_TYPE_P (type))
2845 type = TREE_TYPE (type);
2847 if (TREE_CODE (type) == FUNCTION_TYPE
2848 || TYPE_VOLATILE (type)
2849 || !is_gimple_reg (parm)
2850 || is_va_list_type (type)
2851 || ptr_parm_has_direct_uses (parm))
2854 else if (!AGGREGATE_TYPE_P (type))
2857 if (!COMPLETE_TYPE_P (type)
2858 || !host_integerp (TYPE_SIZE (type), 1)
2859 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2860 || (AGGREGATE_TYPE_P (type)
2861 && type_internals_preclude_sra_p (type)))
2864 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2866 if (dump_file && (dump_flags & TDF_DETAILS))
2868 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2869 print_generic_expr (dump_file, parm, 0);
2870 fprintf (dump_file, "\n");
2874 func_param_count = count;
2878 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2882 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2885 struct access *repr = (struct access *) data;
2887 repr->grp_maybe_modified = 1;
2891 /* Analyze what representatives (in linked lists accessible from
2892 REPRESENTATIVES) can be modified by side effects of statements in the
2893 current function. */
2896 analyze_modified_params (VEC (access_p, heap) *representatives)
2900 for (i = 0; i < func_param_count; i++)
2902 struct access *repr;
2904 for (repr = VEC_index (access_p, representatives, i);
2906 repr = repr->next_grp)
2908 struct access *access;
2912 if (no_accesses_p (repr))
2914 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
2915 || repr->grp_maybe_modified)
2918 ao_ref_init (&ar, repr->expr);
2919 visited = BITMAP_ALLOC (NULL);
2920 for (access = repr; access; access = access->next_sibling)
2922 /* All accesses are read ones, otherwise grp_maybe_modified would
2923 be trivially set. */
2924 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2925 mark_maybe_modified, repr, &visited);
2926 if (repr->grp_maybe_modified)
2929 BITMAP_FREE (visited);
2934 /* Propagate distances in bb_dereferences in the opposite direction than the
2935 control flow edges, in each step storing the maximum of the current value
2936 and the minimum of all successors. These steps are repeated until the table
2937 stabilizes. Note that BBs which might terminate the functions (according to
2938 final_bbs bitmap) never updated in this way. */
2941 propagate_dereference_distances (void)
2943 VEC (basic_block, heap) *queue;
2946 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2947 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2950 VEC_quick_push (basic_block, queue, bb);
2954 while (!VEC_empty (basic_block, queue))
2958 bool change = false;
2961 bb = VEC_pop (basic_block, queue);
2964 if (bitmap_bit_p (final_bbs, bb->index))
2967 for (i = 0; i < func_param_count; i++)
2969 int idx = bb->index * func_param_count + i;
2971 HOST_WIDE_INT inh = 0;
2973 FOR_EACH_EDGE (e, ei, bb->succs)
2975 int succ_idx = e->dest->index * func_param_count + i;
2977 if (e->src == EXIT_BLOCK_PTR)
2983 inh = bb_dereferences [succ_idx];
2985 else if (bb_dereferences [succ_idx] < inh)
2986 inh = bb_dereferences [succ_idx];
2989 if (!first && bb_dereferences[idx] < inh)
2991 bb_dereferences[idx] = inh;
2996 if (change && !bitmap_bit_p (final_bbs, bb->index))
2997 FOR_EACH_EDGE (e, ei, bb->preds)
3002 e->src->aux = e->src;
3003 VEC_quick_push (basic_block, queue, e->src);
3007 VEC_free (basic_block, heap, queue);
3010 /* Dump a dereferences TABLE with heading STR to file F. */
3013 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3017 fprintf (dump_file, str);
3018 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3020 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3021 if (bb != EXIT_BLOCK_PTR)
3024 for (i = 0; i < func_param_count; i++)
3026 int idx = bb->index * func_param_count + i;
3027 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3032 fprintf (dump_file, "\n");
3035 /* Determine what (parts of) parameters passed by reference that are not
3036 assigned to are not certainly dereferenced in this function and thus the
3037 dereferencing cannot be safely moved to the caller without potentially
3038 introducing a segfault. Mark such REPRESENTATIVES as
3039 grp_not_necessarilly_dereferenced.
3041 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3042 part is calculated rather than simple booleans are calculated for each
3043 pointer parameter to handle cases when only a fraction of the whole
3044 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3047 The maximum dereference distances for each pointer parameter and BB are
3048 already stored in bb_dereference. This routine simply propagates these
3049 values upwards by propagate_dereference_distances and then compares the
3050 distances of individual parameters in the ENTRY BB to the equivalent
3051 distances of each representative of a (fraction of a) parameter. */
3054 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3058 if (dump_file && (dump_flags & TDF_DETAILS))
3059 dump_dereferences_table (dump_file,
3060 "Dereference table before propagation:\n",
3063 propagate_dereference_distances ();
3065 if (dump_file && (dump_flags & TDF_DETAILS))
3066 dump_dereferences_table (dump_file,
3067 "Dereference table after propagation:\n",
3070 for (i = 0; i < func_param_count; i++)
3072 struct access *repr = VEC_index (access_p, representatives, i);
3073 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3075 if (!repr || no_accesses_p (repr))
3080 if ((repr->offset + repr->size) > bb_dereferences[idx])
3081 repr->grp_not_necessarilly_dereferenced = 1;
3082 repr = repr->next_grp;
3088 /* Return the representative access for the parameter declaration PARM if it is
3089 a scalar passed by reference which is not written to and the pointer value
3090 is not used directly. Thus, if it is legal to dereference it in the caller
3091 and we can rule out modifications through aliases, such parameter should be
3092 turned into one passed by value. Return NULL otherwise. */
3094 static struct access *
3095 unmodified_by_ref_scalar_representative (tree parm)
3097 int i, access_count;
3098 struct access *repr;
3099 VEC (access_p, heap) *access_vec;
3101 access_vec = get_base_access_vector (parm);
3102 gcc_assert (access_vec);
3103 repr = VEC_index (access_p, access_vec, 0);
3106 repr->group_representative = repr;
3108 access_count = VEC_length (access_p, access_vec);
3109 for (i = 1; i < access_count; i++)
3111 struct access *access = VEC_index (access_p, access_vec, i);
3114 access->group_representative = repr;
3115 access->next_sibling = repr->next_sibling;
3116 repr->next_sibling = access;
3120 repr->grp_scalar_ptr = 1;
3124 /* Return true iff this access precludes IPA-SRA of the parameter it is
3128 access_precludes_ipa_sra_p (struct access *access)
3130 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3131 is incompatible assign in a call statement (and possibly even in asm
3132 statements). This can be relaxed by using a new temporary but only for
3133 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3134 intraprocedural SRA we deal with this by keeping the old aggregate around,
3135 something we cannot do in IPA-SRA.) */
3137 && (is_gimple_call (access->stmt)
3138 || gimple_code (access->stmt) == GIMPLE_ASM))
3145 /* Sort collected accesses for parameter PARM, identify representatives for
3146 each accessed region and link them together. Return NULL if there are
3147 different but overlapping accesses, return the special ptr value meaning
3148 there are no accesses for this parameter if that is the case and return the
3149 first representative otherwise. Set *RO_GRP if there is a group of accesses
3150 with only read (i.e. no write) accesses. */
3152 static struct access *
3153 splice_param_accesses (tree parm, bool *ro_grp)
3155 int i, j, access_count, group_count;
3156 int agg_size, total_size = 0;
3157 struct access *access, *res, **prev_acc_ptr = &res;
3158 VEC (access_p, heap) *access_vec;
3160 access_vec = get_base_access_vector (parm);
3162 return &no_accesses_representant;
3163 access_count = VEC_length (access_p, access_vec);
3165 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3166 compare_access_positions);
3171 while (i < access_count)
3174 access = VEC_index (access_p, access_vec, i);
3175 modification = access->write;
3176 if (access_precludes_ipa_sra_p (access))
3179 /* Access is about to become group representative unless we find some
3180 nasty overlap which would preclude us from breaking this parameter
3184 while (j < access_count)
3186 struct access *ac2 = VEC_index (access_p, access_vec, j);
3187 if (ac2->offset != access->offset)
3189 /* All or nothing law for parameters. */
3190 if (access->offset + access->size > ac2->offset)
3195 else if (ac2->size != access->size)
3198 if (access_precludes_ipa_sra_p (ac2))
3201 modification |= ac2->write;
3202 ac2->group_representative = access;
3203 ac2->next_sibling = access->next_sibling;
3204 access->next_sibling = ac2;
3209 access->grp_maybe_modified = modification;
3212 *prev_acc_ptr = access;
3213 prev_acc_ptr = &access->next_grp;
3214 total_size += access->size;
3218 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3219 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3221 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3222 if (total_size >= agg_size)
3225 gcc_assert (group_count > 0);
3229 /* Decide whether parameters with representative accesses given by REPR should
3230 be reduced into components. */
3233 decide_one_param_reduction (struct access *repr)
3235 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3240 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3241 gcc_assert (cur_parm_size > 0);
3243 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3246 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3251 agg_size = cur_parm_size;
3257 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3258 print_generic_expr (dump_file, parm, 0);
3259 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3260 for (acc = repr; acc; acc = acc->next_grp)
3261 dump_access (dump_file, acc, true);
3265 new_param_count = 0;
3267 for (; repr; repr = repr->next_grp)
3269 gcc_assert (parm == repr->base);
3272 if (!by_ref || (!repr->grp_maybe_modified
3273 && !repr->grp_not_necessarilly_dereferenced))
3274 total_size += repr->size;
3276 total_size += cur_parm_size;
3279 gcc_assert (new_param_count > 0);
3281 if (optimize_function_for_size_p (cfun))
3282 parm_size_limit = cur_parm_size;
3284 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3287 if (total_size < agg_size
3288 && total_size <= parm_size_limit)
3291 fprintf (dump_file, " ....will be split into %i components\n",
3293 return new_param_count;
3299 /* The order of the following enums is important, we need to do extra work for
3300 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3301 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3302 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3304 /* Identify representatives of all accesses to all candidate parameters for
3305 IPA-SRA. Return result based on what representatives have been found. */
3307 static enum ipa_splicing_result
3308 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3310 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3312 struct access *repr;
3314 *representatives = VEC_alloc (access_p, heap, func_param_count);
3316 for (parm = DECL_ARGUMENTS (current_function_decl);
3318 parm = TREE_CHAIN (parm))
3320 if (is_unused_scalar_param (parm))
3322 VEC_quick_push (access_p, *representatives,
3323 &no_accesses_representant);
3324 if (result == NO_GOOD_ACCESS)
3325 result = UNUSED_PARAMS;
3327 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3328 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3329 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3331 repr = unmodified_by_ref_scalar_representative (parm);
3332 VEC_quick_push (access_p, *representatives, repr);
3334 result = UNMODIF_BY_REF_ACCESSES;
3336 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3338 bool ro_grp = false;
3339 repr = splice_param_accesses (parm, &ro_grp);
3340 VEC_quick_push (access_p, *representatives, repr);
3342 if (repr && !no_accesses_p (repr))
3344 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3347 result = UNMODIF_BY_REF_ACCESSES;
3348 else if (result < MODIF_BY_REF_ACCESSES)
3349 result = MODIF_BY_REF_ACCESSES;
3351 else if (result < BY_VAL_ACCESSES)
3352 result = BY_VAL_ACCESSES;
3354 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3355 result = UNUSED_PARAMS;
3358 VEC_quick_push (access_p, *representatives, NULL);
3361 if (result == NO_GOOD_ACCESS)
3363 VEC_free (access_p, heap, *representatives);
3364 *representatives = NULL;
3365 return NO_GOOD_ACCESS;
3371 /* Return the index of BASE in PARMS. Abort if it is not found. */
3374 get_param_index (tree base, VEC(tree, heap) *parms)
3378 len = VEC_length (tree, parms);
3379 for (i = 0; i < len; i++)
3380 if (VEC_index (tree, parms, i) == base)
3385 /* Convert the decisions made at the representative level into compact
3386 parameter adjustments. REPRESENTATIVES are pointers to first
3387 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3388 final number of adjustments. */
3390 static ipa_parm_adjustment_vec
3391 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3392 int adjustments_count)
3394 VEC (tree, heap) *parms;
3395 ipa_parm_adjustment_vec adjustments;
3399 gcc_assert (adjustments_count > 0);
3400 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3401 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3402 parm = DECL_ARGUMENTS (current_function_decl);
3403 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3405 struct access *repr = VEC_index (access_p, representatives, i);
3407 if (!repr || no_accesses_p (repr))
3409 struct ipa_parm_adjustment *adj;
3411 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3412 memset (adj, 0, sizeof (*adj));
3413 adj->base_index = get_param_index (parm, parms);
3416 adj->copy_param = 1;
3418 adj->remove_param = 1;
3422 struct ipa_parm_adjustment *adj;
3423 int index = get_param_index (parm, parms);
3425 for (; repr; repr = repr->next_grp)
3427 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3428 memset (adj, 0, sizeof (*adj));
3429 gcc_assert (repr->base == parm);
3430 adj->base_index = index;
3431 adj->base = repr->base;
3432 adj->type = repr->type;
3433 adj->offset = repr->offset;
3434 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3435 && (repr->grp_maybe_modified
3436 || repr->grp_not_necessarilly_dereferenced));
3441 VEC_free (tree, heap, parms);
3445 /* Analyze the collected accesses and produce a plan what to do with the
3446 parameters in the form of adjustments, NULL meaning nothing. */
3448 static ipa_parm_adjustment_vec
3449 analyze_all_param_acesses (void)
3451 enum ipa_splicing_result repr_state;
3452 bool proceed = false;
3453 int i, adjustments_count = 0;
3454 VEC (access_p, heap) *representatives;
3455 ipa_parm_adjustment_vec adjustments;
3457 repr_state = splice_all_param_accesses (&representatives);
3458 if (repr_state == NO_GOOD_ACCESS)
3461 /* If there are any parameters passed by reference which are not modified
3462 directly, we need to check whether they can be modified indirectly. */
3463 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3465 analyze_caller_dereference_legality (representatives);
3466 analyze_modified_params (representatives);
3469 for (i = 0; i < func_param_count; i++)
3471 struct access *repr = VEC_index (access_p, representatives, i);
3473 if (repr && !no_accesses_p (repr))
3475 if (repr->grp_scalar_ptr)
3477 adjustments_count++;
3478 if (repr->grp_not_necessarilly_dereferenced
3479 || repr->grp_maybe_modified)
3480 VEC_replace (access_p, representatives, i, NULL);
3484 sra_stats.scalar_by_ref_to_by_val++;
3489 int new_components = decide_one_param_reduction (repr);
3491 if (new_components == 0)
3493 VEC_replace (access_p, representatives, i, NULL);
3494 adjustments_count++;
3498 adjustments_count += new_components;
3499 sra_stats.aggregate_params_reduced++;
3500 sra_stats.param_reductions_created += new_components;
3507 if (no_accesses_p (repr))
3510 sra_stats.deleted_unused_parameters++;
3512 adjustments_count++;
3516 if (!proceed && dump_file)
3517 fprintf (dump_file, "NOT proceeding to change params.\n");
3520 adjustments = turn_representatives_into_adjustments (representatives,
3525 VEC_free (access_p, heap, representatives);
3529 /* If a parameter replacement identified by ADJ does not yet exist in the form
3530 of declaration, create it and record it, otherwise return the previously
3534 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3537 if (!adj->new_ssa_base)
3539 char *pretty_name = make_fancy_name (adj->base);
3541 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3542 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3543 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3544 DECL_GIMPLE_REG_P (repl) = 1;
3545 DECL_NAME (repl) = get_identifier (pretty_name);
3546 obstack_free (&name_obstack, pretty_name);
3549 add_referenced_var (repl);
3550 adj->new_ssa_base = repl;
3553 repl = adj->new_ssa_base;
3557 /* Find the first adjustment for a particular parameter BASE in a vector of
3558 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3561 static struct ipa_parm_adjustment *
3562 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3566 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3567 for (i = 0; i < len; i++)
3569 struct ipa_parm_adjustment *adj;
3571 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3572 if (!adj->copy_param && adj->base == base)
3579 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3580 parameter which is to be removed because its value is not used, replace the
3581 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3582 uses too and return true (update_stmt is then issued for the statement by
3583 the caller). DATA is a pointer to an adjustments vector. */
3586 replace_removed_params_ssa_names (gimple stmt, void *data)
3588 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3589 struct ipa_parm_adjustment *adj;
3590 tree lhs, decl, repl, name;
3592 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3593 if (gimple_code (stmt) == GIMPLE_PHI)
3594 lhs = gimple_phi_result (stmt);
3595 else if (is_gimple_assign (stmt))
3596 lhs = gimple_assign_lhs (stmt);
3597 else if (is_gimple_call (stmt))
3598 lhs = gimple_call_lhs (stmt);
3602 if (TREE_CODE (lhs) != SSA_NAME)
3604 decl = SSA_NAME_VAR (lhs);
3605 if (TREE_CODE (decl) != PARM_DECL)
3608 adj = get_adjustment_for_base (adjustments, decl);
3612 repl = get_replaced_param_substitute (adj);
3613 name = make_ssa_name (repl, stmt);
3617 fprintf (dump_file, "replacing an SSA name of a removed param ");
3618 print_generic_expr (dump_file, lhs, 0);
3619 fprintf (dump_file, " with ");
3620 print_generic_expr (dump_file, name, 0);
3621 fprintf (dump_file, "\n");
3624 if (is_gimple_assign (stmt))
3625 gimple_assign_set_lhs (stmt, name);
3626 else if (is_gimple_call (stmt))
3627 gimple_call_set_lhs (stmt, name);
3629 gimple_phi_set_result (stmt, name);
3631 replace_uses_by (lhs, name);
3635 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3636 expression *EXPR should be replaced by a reduction of a parameter, do so.
3637 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3638 whether the function should care about type incompatibility the current and
3639 new expressions. If it is true, the function will leave incompatibility
3640 issues to the caller.
3642 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3643 a write (LHS) expression. */
3646 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3647 bool dont_convert, void *data)
3649 ipa_parm_adjustment_vec adjustments;
3651 struct ipa_parm_adjustment *adj, *cand = NULL;
3652 HOST_WIDE_INT offset, size, max_size;
3655 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3656 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3658 if (TREE_CODE (*expr) == BIT_FIELD_REF
3659 || TREE_CODE (*expr) == IMAGPART_EXPR
3660 || TREE_CODE (*expr) == REALPART_EXPR)
3662 expr = &TREE_OPERAND (*expr, 0);
3663 dont_convert = false;
3666 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3667 if (!base || size == -1 || max_size == -1)
3670 if (INDIRECT_REF_P (base))
3671 base = TREE_OPERAND (base, 0);
3673 base = get_ssa_base_param (base);
3674 if (!base || TREE_CODE (base) != PARM_DECL)
3677 for (i = 0; i < len; i++)
3679 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3681 if (adj->base == base &&
3682 (adj->offset == offset || adj->remove_param))
3688 if (!cand || cand->copy_param || cand->remove_param)
3694 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3696 folded = gimple_fold_indirect_ref (src);
3701 src = cand->reduction;
3703 if (dump_file && (dump_flags & TDF_DETAILS))
3705 fprintf (dump_file, "About to replace expr ");
3706 print_generic_expr (dump_file, *expr, 0);
3707 fprintf (dump_file, " with ");
3708 print_generic_expr (dump_file, src, 0);
3709 fprintf (dump_file, "\n");
3713 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3715 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3723 /* Callback for scan_function to process assign statements. Performs
3724 essentially the same function like sra_ipa_modify_expr. */
3726 static enum scan_assign_result
3727 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3729 gimple stmt = *stmt_ptr;
3730 tree *lhs_p, *rhs_p;
3733 if (!gimple_assign_single_p (stmt))
3736 rhs_p = gimple_assign_rhs1_ptr (stmt);
3737 lhs_p = gimple_assign_lhs_ptr (stmt);
3739 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3740 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3743 tree new_rhs = NULL_TREE;
3745 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3747 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
3749 /* V_C_Es of constructors can cause trouble (PR 42714). */
3750 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
3751 *rhs_p = fold_convert (TREE_TYPE (*lhs_p), integer_zero_node);
3753 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
3756 new_rhs = fold_build1_loc (gimple_location (stmt),
3757 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
3760 else if (REFERENCE_CLASS_P (*rhs_p)
3761 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3762 && !is_gimple_reg (*lhs_p))
3763 /* This can happen when an assignment in between two single field
3764 structures is turned into an assignment in between two pointers to
3765 scalars (PR 42237). */
3770 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3771 true, GSI_SAME_STMT);
3773 gimple_assign_set_rhs_from_tree (gsi, tmp);
3776 return SRA_SA_PROCESSED;
3782 /* Call gimple_debug_bind_reset_value on all debug statements describing
3783 gimple register parameters that are being removed or replaced. */
3786 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3790 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3791 for (i = 0; i < len; i++)
3793 struct ipa_parm_adjustment *adj;
3794 imm_use_iterator ui;
3798 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3799 if (adj->copy_param || !is_gimple_reg (adj->base))
3801 name = gimple_default_def (cfun, adj->base);
3804 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3806 /* All other users must have been removed by scan_function. */
3807 gcc_assert (is_gimple_debug (stmt));
3808 gimple_debug_bind_reset_value (stmt);
3814 /* Return true iff all callers have at least as many actual arguments as there
3815 are formal parameters in the current function. */
3818 all_callers_have_enough_arguments_p (struct cgraph_node *node)
3820 struct cgraph_edge *cs;
3821 for (cs = node->callers; cs; cs = cs->next_caller)
3822 if (!callsite_has_enough_arguments_p (cs->call_stmt))
3829 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3832 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3834 tree old_cur_fndecl = current_function_decl;
3835 struct cgraph_edge *cs;
3836 basic_block this_block;
3837 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3839 for (cs = node->callers; cs; cs = cs->next_caller)
3841 current_function_decl = cs->caller->decl;
3842 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3845 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3846 cs->caller->uid, cs->callee->uid,
3847 cgraph_node_name (cs->caller),
3848 cgraph_node_name (cs->callee));
3850 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3855 for (cs = node->callers; cs; cs = cs->next_caller)
3856 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3858 compute_inline_parameters (cs->caller);
3859 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3861 BITMAP_FREE (recomputed_callers);
3863 current_function_decl = old_cur_fndecl;
3865 if (!encountered_recursive_call)
3868 FOR_EACH_BB (this_block)
3870 gimple_stmt_iterator gsi;
3872 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3874 gimple stmt = gsi_stmt (gsi);
3876 if (gimple_code (stmt) != GIMPLE_CALL)
3878 call_fndecl = gimple_call_fndecl (stmt);
3879 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
3882 fprintf (dump_file, "Adjusting recursive call");
3883 ipa_modify_call_arguments (NULL, stmt, adjustments);
3891 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3892 as given in ADJUSTMENTS. */
3895 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3897 struct cgraph_node *alias;
3898 for (alias = node->same_body; alias; alias = alias->next)
3899 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
3900 /* current_function_decl must be handled last, after same_body aliases,
3901 as following functions will use what it computed. */
3902 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3903 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3904 replace_removed_params_ssa_names, false, adjustments);
3905 sra_ipa_reset_debug_stmts (adjustments);
3906 convert_callers (node, adjustments);
3907 cgraph_make_node_local (node);
3911 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3912 attributes, return true otherwise. NODE is the cgraph node of the current
3916 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3918 if (!cgraph_node_can_be_local_p (node))
3921 fprintf (dump_file, "Function not local to this compilation unit.\n");
3925 if (DECL_VIRTUAL_P (current_function_decl))
3928 fprintf (dump_file, "Function is a virtual method.\n");
3932 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3933 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3936 fprintf (dump_file, "Function too big to be made truly local.\n");
3944 "Function has no callers in this compilation unit.\n");
3951 fprintf (dump_file, "Function uses stdarg. \n");
3958 /* Perform early interprocedural SRA. */
3961 ipa_early_sra (void)
3963 struct cgraph_node *node = cgraph_node (current_function_decl);
3964 ipa_parm_adjustment_vec adjustments;
3967 if (!ipa_sra_preliminary_function_checks (node))
3971 sra_mode = SRA_MODE_EARLY_IPA;
3973 if (!find_param_candidates ())
3976 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3980 if (!all_callers_have_enough_arguments_p (node))
3983 fprintf (dump_file, "There are callers with insufficient number of "
3988 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3990 * last_basic_block_for_function (cfun));
3991 final_bbs = BITMAP_ALLOC (NULL);
3993 scan_function (build_access_from_expr, build_accesses_from_assign,
3995 if (encountered_apply_args)
3998 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4002 if (encountered_unchangable_recursive_call)
4005 fprintf (dump_file, "Function calls itself with insufficient "
4006 "number of arguments.\n");
4010 adjustments = analyze_all_param_acesses ();
4014 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4016 modify_function (node, adjustments);
4017 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4018 ret = TODO_update_ssa;
4020 statistics_counter_event (cfun, "Unused parameters deleted",
4021 sra_stats.deleted_unused_parameters);
4022 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4023 sra_stats.scalar_by_ref_to_by_val);
4024 statistics_counter_event (cfun, "Aggregate parameters broken up",
4025 sra_stats.aggregate_params_reduced);
4026 statistics_counter_event (cfun, "Aggregate parameter components created",
4027 sra_stats.param_reductions_created);
4030 BITMAP_FREE (final_bbs);
4031 free (bb_dereferences);
4033 sra_deinitialize ();
4037 /* Return if early ipa sra shall be performed. */
4039 ipa_early_sra_gate (void)
4041 return flag_ipa_sra;
4044 struct gimple_opt_pass pass_early_ipa_sra =
4048 "eipa_sra", /* name */
4049 ipa_early_sra_gate, /* gate */
4050 ipa_early_sra, /* execute */
4053 0, /* static_pass_number */
4054 TV_IPA_SRA, /* tv_id */
4055 0, /* properties_required */
4056 0, /* properties_provided */
4057 0, /* properties_destroyed */
4058 0, /* todo_flags_start */
4059 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */