1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009 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 /* Does this group contain accesses to different types? (I.e. through a union
203 or a similar mechanism). */
204 unsigned grp_different_types : 1;
206 /* Set when a scalar replacement should be created for this variable. We do
207 the decision and creation at different places because create_tmp_var
208 cannot be called from within FOR_EACH_REFERENCED_VAR. */
209 unsigned grp_to_be_replaced : 1;
211 /* Is it possible that the group refers to data which might be (directly or
212 otherwise) modified? */
213 unsigned grp_maybe_modified : 1;
215 /* Set when this is a representative of a pointer to scalar (i.e. by
216 reference) parameter which we consider for turning into a plain scalar
217 (i.e. a by value parameter). */
218 unsigned grp_scalar_ptr : 1;
220 /* Set when we discover that this pointer is not safe to dereference in the
222 unsigned grp_not_necessarilly_dereferenced : 1;
225 typedef struct access *access_p;
227 DEF_VEC_P (access_p);
228 DEF_VEC_ALLOC_P (access_p, heap);
230 /* Alloc pool for allocating access structures. */
231 static alloc_pool access_pool;
233 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
234 are used to propagate subaccesses from rhs to lhs as long as they don't
235 conflict with what is already there. */
238 struct access *lacc, *racc;
239 struct assign_link *next;
242 /* Alloc pool for allocating assign link structures. */
243 static alloc_pool link_pool;
245 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
246 static struct pointer_map_t *base_access_vec;
248 /* Bitmap of candidates. */
249 static bitmap candidate_bitmap;
251 /* Obstack for creation of fancy names. */
252 static struct obstack name_obstack;
254 /* Head of a linked list of accesses that need to have its subaccesses
255 propagated to their assignment counterparts. */
256 static struct access *work_queue_head;
258 /* Number of parameters of the analyzed function when doing early ipa SRA. */
259 static int func_param_count;
261 /* scan_function sets the following to true if it encounters a call to
262 __builtin_apply_args. */
263 static bool encountered_apply_args;
265 /* This is a table in which for each basic block and parameter there is a
266 distance (offset + size) in that parameter which is dereferenced and
267 accessed in that BB. */
268 static HOST_WIDE_INT *bb_dereferences;
269 /* Bitmap of BBs that can cause the function to "stop" progressing by
270 returning, throwing externally, looping infinitely or calling a function
271 which might abort etc.. */
272 static bitmap final_bbs;
274 /* Representative of no accesses at all. */
275 static struct access no_accesses_representant;
277 /* Predicate to test the special value. */
280 no_accesses_p (struct access *access)
282 return access == &no_accesses_representant;
285 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
286 representative fields are dumped, otherwise those which only describe the
287 individual access are. */
291 /* Number of processed aggregates is readily available in
292 analyze_all_variable_accesses and so is not stored here. */
294 /* Number of created scalar replacements. */
297 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
301 /* Number of statements created by generate_subtree_copies. */
304 /* Number of statements created by load_assign_lhs_subreplacements. */
307 /* Number of times sra_modify_assign has deleted a statement. */
310 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
311 RHS reparately due to type conversions or nonexistent matching
313 int separate_lhs_rhs_handling;
315 /* Number of parameters that were removed because they were unused. */
316 int deleted_unused_parameters;
318 /* Number of scalars passed as parameters by reference that have been
319 converted to be passed by value. */
320 int scalar_by_ref_to_by_val;
322 /* Number of aggregate parameters that were replaced by one or more of their
324 int aggregate_params_reduced;
326 /* Numbber of components created when splitting aggregate parameters. */
327 int param_reductions_created;
331 dump_access (FILE *f, struct access *access, bool grp)
333 fprintf (f, "access { ");
334 fprintf (f, "base = (%d)'", DECL_UID (access->base));
335 print_generic_expr (f, access->base, 0);
336 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
337 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
338 fprintf (f, ", expr = ");
339 print_generic_expr (f, access->expr, 0);
340 fprintf (f, ", type = ");
341 print_generic_expr (f, access->type, 0);
343 fprintf (f, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
344 "grp_covered = %d, grp_unscalarizable_region = %d, "
345 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
346 "grp_different_types = %d, grp_to_be_replaced = %d, "
347 "grp_maybe_modified = %d, "
348 "grp_not_necessarilly_dereferenced = %d\n",
349 access->grp_write, access->grp_read, access->grp_hint,
350 access->grp_covered, access->grp_unscalarizable_region,
351 access->grp_unscalarized_data, access->grp_partial_lhs,
352 access->grp_different_types, access->grp_to_be_replaced,
353 access->grp_maybe_modified,
354 access->grp_not_necessarilly_dereferenced);
356 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
357 access->grp_partial_lhs);
360 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
363 dump_access_tree_1 (FILE *f, struct access *access, int level)
369 for (i = 0; i < level; i++)
370 fputs ("* ", dump_file);
372 dump_access (f, access, true);
374 if (access->first_child)
375 dump_access_tree_1 (f, access->first_child, level + 1);
377 access = access->next_sibling;
382 /* Dump all access trees for a variable, given the pointer to the first root in
386 dump_access_tree (FILE *f, struct access *access)
388 for (; access; access = access->next_grp)
389 dump_access_tree_1 (f, access, 0);
392 /* Return true iff ACC is non-NULL and has subaccesses. */
395 access_has_children_p (struct access *acc)
397 return acc && acc->first_child;
400 /* Return a vector of pointers to accesses for the variable given in BASE or
401 NULL if there is none. */
403 static VEC (access_p, heap) *
404 get_base_access_vector (tree base)
408 slot = pointer_map_contains (base_access_vec, base);
412 return *(VEC (access_p, heap) **) slot;
415 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
416 in ACCESS. Return NULL if it cannot be found. */
418 static struct access *
419 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
422 while (access && (access->offset != offset || access->size != size))
424 struct access *child = access->first_child;
426 while (child && (child->offset + child->size <= offset))
427 child = child->next_sibling;
434 /* Return the first group representative for DECL or NULL if none exists. */
436 static struct access *
437 get_first_repr_for_decl (tree base)
439 VEC (access_p, heap) *access_vec;
441 access_vec = get_base_access_vector (base);
445 return VEC_index (access_p, access_vec, 0);
448 /* Find an access representative for the variable BASE and given OFFSET and
449 SIZE. Requires that access trees have already been built. Return NULL if
450 it cannot be found. */
452 static struct access *
453 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
456 struct access *access;
458 access = get_first_repr_for_decl (base);
459 while (access && (access->offset + access->size <= offset))
460 access = access->next_grp;
464 return find_access_in_subtree (access, offset, size);
467 /* Add LINK to the linked list of assign links of RACC. */
469 add_link_to_rhs (struct access *racc, struct assign_link *link)
471 gcc_assert (link->racc == racc);
473 if (!racc->first_link)
475 gcc_assert (!racc->last_link);
476 racc->first_link = link;
479 racc->last_link->next = link;
481 racc->last_link = link;
485 /* Move all link structures in their linked list in OLD_RACC to the linked list
488 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
490 if (!old_racc->first_link)
492 gcc_assert (!old_racc->last_link);
496 if (new_racc->first_link)
498 gcc_assert (!new_racc->last_link->next);
499 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
501 new_racc->last_link->next = old_racc->first_link;
502 new_racc->last_link = old_racc->last_link;
506 gcc_assert (!new_racc->last_link);
508 new_racc->first_link = old_racc->first_link;
509 new_racc->last_link = old_racc->last_link;
511 old_racc->first_link = old_racc->last_link = NULL;
514 /* Add ACCESS to the work queue (which is actually a stack). */
517 add_access_to_work_queue (struct access *access)
519 if (!access->grp_queued)
521 gcc_assert (!access->next_queued);
522 access->next_queued = work_queue_head;
523 access->grp_queued = 1;
524 work_queue_head = access;
528 /* Pop an access from the work queue, and return it, assuming there is one. */
530 static struct access *
531 pop_access_from_work_queue (void)
533 struct access *access = work_queue_head;
535 work_queue_head = access->next_queued;
536 access->next_queued = NULL;
537 access->grp_queued = 0;
542 /* Allocate necessary structures. */
545 sra_initialize (void)
547 candidate_bitmap = BITMAP_ALLOC (NULL);
548 gcc_obstack_init (&name_obstack);
549 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
550 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
551 base_access_vec = pointer_map_create ();
552 memset (&sra_stats, 0, sizeof (sra_stats));
553 encountered_apply_args = false;
556 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
559 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
560 void *data ATTRIBUTE_UNUSED)
562 VEC (access_p, heap) *access_vec;
563 access_vec = (VEC (access_p, heap) *) *value;
564 VEC_free (access_p, heap, access_vec);
569 /* Deallocate all general structures. */
572 sra_deinitialize (void)
574 BITMAP_FREE (candidate_bitmap);
575 free_alloc_pool (access_pool);
576 free_alloc_pool (link_pool);
577 obstack_free (&name_obstack, NULL);
579 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
580 pointer_map_destroy (base_access_vec);
583 /* Remove DECL from candidates for SRA and write REASON to the dump file if
586 disqualify_candidate (tree decl, const char *reason)
588 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
590 if (dump_file && (dump_flags & TDF_DETAILS))
592 fprintf (dump_file, "! Disqualifying ");
593 print_generic_expr (dump_file, decl, 0);
594 fprintf (dump_file, " - %s\n", reason);
598 /* Return true iff the type contains a field or an element which does not allow
602 type_internals_preclude_sra_p (tree type)
607 switch (TREE_CODE (type))
611 case QUAL_UNION_TYPE:
612 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
613 if (TREE_CODE (fld) == FIELD_DECL)
615 tree ft = TREE_TYPE (fld);
617 if (TREE_THIS_VOLATILE (fld)
618 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
619 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
620 || !host_integerp (DECL_SIZE (fld), 1))
623 if (AGGREGATE_TYPE_P (ft)
624 && type_internals_preclude_sra_p (ft))
631 et = TREE_TYPE (type);
633 if (AGGREGATE_TYPE_P (et))
634 return type_internals_preclude_sra_p (et);
643 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
644 base variable if it is. Return T if it is not an SSA_NAME. */
647 get_ssa_base_param (tree t)
649 if (TREE_CODE (t) == SSA_NAME)
651 if (SSA_NAME_IS_DEFAULT_DEF (t))
652 return SSA_NAME_VAR (t);
659 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
660 belongs to, unless the BB has already been marked as a potentially
664 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
666 basic_block bb = gimple_bb (stmt);
667 int idx, parm_index = 0;
670 if (bitmap_bit_p (final_bbs, bb->index))
673 for (parm = DECL_ARGUMENTS (current_function_decl);
674 parm && parm != base;
675 parm = TREE_CHAIN (parm))
678 gcc_assert (parm_index < func_param_count);
680 idx = bb->index * func_param_count + parm_index;
681 if (bb_dereferences[idx] < dist)
682 bb_dereferences[idx] = dist;
685 /* Create and insert access for EXPR. Return created access, or NULL if it is
688 static struct access *
689 create_access (tree expr, gimple stmt, bool write)
691 struct access *access;
693 VEC (access_p,heap) *vec;
694 HOST_WIDE_INT offset, size, max_size;
696 bool ptr, unscalarizable_region = false;
698 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
700 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
702 base = get_ssa_base_param (TREE_OPERAND (base, 0));
710 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
713 if (sra_mode == SRA_MODE_EARLY_IPA)
715 if (size < 0 || size != max_size)
717 disqualify_candidate (base, "Encountered a variable sized access.");
720 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
722 disqualify_candidate (base,
723 "Encountered an acces not aligned to a byte.");
728 mark_parm_dereference (base, offset + size, stmt);
732 if (size != max_size)
735 unscalarizable_region = true;
739 disqualify_candidate (base, "Encountered an unconstrained access.");
744 access = (struct access *) pool_alloc (access_pool);
745 memset (access, 0, sizeof (struct access));
748 access->offset = offset;
751 access->type = TREE_TYPE (expr);
752 access->write = write;
753 access->grp_unscalarizable_region = unscalarizable_region;
756 slot = pointer_map_contains (base_access_vec, base);
758 vec = (VEC (access_p, heap) *) *slot;
760 vec = VEC_alloc (access_p, heap, 32);
762 VEC_safe_push (access_p, heap, vec, access);
764 *((struct VEC (access_p,heap) **)
765 pointer_map_insert (base_access_vec, base)) = vec;
771 /* Search the given tree for a declaration by skipping handled components and
772 exclude it from the candidates. */
775 disqualify_base_of_expr (tree t, const char *reason)
777 while (handled_component_p (t))
778 t = TREE_OPERAND (t, 0);
780 if (sra_mode == SRA_MODE_EARLY_IPA)
782 if (INDIRECT_REF_P (t))
783 t = TREE_OPERAND (t, 0);
784 t = get_ssa_base_param (t);
788 disqualify_candidate (t, reason);
791 /* Scan expression EXPR and create access structures for all accesses to
792 candidates for scalarization. Return the created access or NULL if none is
795 static struct access *
796 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
798 struct access *ret = NULL;
799 tree expr = *expr_ptr;
802 if (TREE_CODE (expr) == BIT_FIELD_REF
803 || TREE_CODE (expr) == IMAGPART_EXPR
804 || TREE_CODE (expr) == REALPART_EXPR)
806 expr = TREE_OPERAND (expr, 0);
812 /* We need to dive through V_C_Es in order to get the size of its parameter
813 and not the result type. Ada produces such statements. We are also
814 capable of handling the topmost V_C_E but not any of those buried in other
815 handled components. */
816 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
817 expr = TREE_OPERAND (expr, 0);
819 if (contains_view_convert_expr_p (expr))
821 disqualify_base_of_expr (expr, "V_C_E under a different handled "
826 switch (TREE_CODE (expr))
829 if (sra_mode != SRA_MODE_EARLY_IPA)
837 case ARRAY_RANGE_REF:
838 ret = create_access (expr, stmt, write);
845 if (write && partial_ref && ret)
846 ret->grp_partial_lhs = 1;
851 /* Callback of scan_function. Scan expression EXPR and create access
852 structures for all accesses to candidates for scalarization. Return true if
853 any access has been inserted. */
856 build_access_from_expr (tree *expr_ptr,
857 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
858 void *data ATTRIBUTE_UNUSED)
860 return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
863 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
864 modes in which it matters, return true iff they have been disqualified. RHS
865 may be NULL, in that case ignore it. If we scalarize an aggregate in
866 intra-SRA we may need to add statements after each statement. This is not
867 possible if a statement unconditionally has to end the basic block. */
869 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
871 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
872 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
874 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
876 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
883 /* Result code for scan_assign callback for scan_function. */
884 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
885 SRA_SA_PROCESSED, /* stmt analyzed/changed */
886 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
889 /* Callback of scan_function. Scan expressions occuring in the statement
890 pointed to by STMT_EXPR, create access structures for all accesses to
891 candidates for scalarization and remove those candidates which occur in
892 statements or expressions that prevent them from being split apart. Return
893 true if any access has been inserted. */
895 static enum scan_assign_result
896 build_accesses_from_assign (gimple *stmt_ptr,
897 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
898 void *data ATTRIBUTE_UNUSED)
900 gimple stmt = *stmt_ptr;
901 tree *lhs_ptr, *rhs_ptr;
902 struct access *lacc, *racc;
904 if (!gimple_assign_single_p (stmt))
907 lhs_ptr = gimple_assign_lhs_ptr (stmt);
908 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
910 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
913 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
914 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
917 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
918 && !lacc->grp_unscalarizable_region
919 && !racc->grp_unscalarizable_region
920 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
921 /* FIXME: Turn the following line into an assert after PR 40058 is
923 && lacc->size == racc->size
924 && useless_type_conversion_p (lacc->type, racc->type))
926 struct assign_link *link;
928 link = (struct assign_link *) pool_alloc (link_pool);
929 memset (link, 0, sizeof (struct assign_link));
934 add_link_to_rhs (racc, link);
937 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
940 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
941 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
944 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
945 void *data ATTRIBUTE_UNUSED)
948 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
954 /* Scan function and look for interesting statements. Return true if any has
955 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
956 called on all expressions within statements except assign statements and
957 those deemed entirely unsuitable for some reason (all operands in such
958 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
959 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
960 called on assign statements and those call statements which have a lhs, it
961 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
962 pass and thus no statement is being modified. DATA is a pointer passed to
963 all callbacks. If any single callback returns true, this function also
964 returns true, otherwise it returns false. */
967 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
968 enum scan_assign_result (*scan_assign) (gimple *,
969 gimple_stmt_iterator *,
971 bool (*handle_ssa_defs)(gimple, void *),
972 bool analysis_stage, void *data)
974 gimple_stmt_iterator gsi;
982 bool bb_changed = false;
985 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
986 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
988 gsi = gsi_start_bb (bb);
989 while (!gsi_end_p (gsi))
991 gimple stmt = gsi_stmt (gsi);
992 enum scan_assign_result assign_result;
993 bool any = false, deleted = false;
995 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
996 bitmap_set_bit (final_bbs, bb->index);
997 switch (gimple_code (stmt))
1000 t = gimple_return_retval_ptr (stmt);
1001 if (*t != NULL_TREE)
1002 any |= scan_expr (t, &gsi, false, data);
1003 if (analysis_stage && final_bbs)
1004 bitmap_set_bit (final_bbs, bb->index);
1008 assign_result = scan_assign (&stmt, &gsi, data);
1009 any |= assign_result == SRA_SA_PROCESSED;
1010 deleted = assign_result == SRA_SA_REMOVED;
1011 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1012 any |= handle_ssa_defs (stmt, data);
1016 /* Operands must be processed before the lhs. */
1017 for (i = 0; i < gimple_call_num_args (stmt); i++)
1019 tree *argp = gimple_call_arg_ptr (stmt, i);
1020 any |= scan_expr (argp, &gsi, false, data);
1025 tree dest = gimple_call_fndecl (stmt);
1026 int flags = gimple_call_flags (stmt);
1029 && DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1030 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1031 encountered_apply_args = true;
1034 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1035 bitmap_set_bit (final_bbs, bb->index);
1038 if (gimple_call_lhs (stmt))
1040 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1042 || !disqualify_ops_if_throwing_stmt (stmt,
1045 any |= scan_expr (lhs_ptr, &gsi, true, data);
1046 if (handle_ssa_defs)
1047 any |= handle_ssa_defs (stmt, data);
1055 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1058 bitmap_set_bit (final_bbs, bb->index);
1060 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1062 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1063 any |= scan_expr (op, &gsi, false, data);
1065 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1067 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1068 any |= scan_expr (op, &gsi, true, data);
1080 if (!analysis_stage)
1084 maybe_clean_eh_stmt (stmt);
1095 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1096 gimple_purge_dead_eh_edges (bb);
1102 /* Helper of QSORT function. There are pointers to accesses in the array. An
1103 access is considered smaller than another if it has smaller offset or if the
1104 offsets are the same but is size is bigger. */
1107 compare_access_positions (const void *a, const void *b)
1109 const access_p *fp1 = (const access_p *) a;
1110 const access_p *fp2 = (const access_p *) b;
1111 const access_p f1 = *fp1;
1112 const access_p f2 = *fp2;
1114 if (f1->offset != f2->offset)
1115 return f1->offset < f2->offset ? -1 : 1;
1117 if (f1->size == f2->size)
1119 /* Put any non-aggregate type before any aggregate type. */
1120 if (!is_gimple_reg_type (f1->type)
1121 && is_gimple_reg_type (f2->type))
1123 else if (is_gimple_reg_type (f1->type)
1124 && !is_gimple_reg_type (f2->type))
1126 /* Put any complex or vector type before any other scalar type. */
1127 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1128 && TREE_CODE (f1->type) != VECTOR_TYPE
1129 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1130 || TREE_CODE (f2->type) == VECTOR_TYPE))
1132 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1133 || TREE_CODE (f1->type) == VECTOR_TYPE)
1134 && TREE_CODE (f2->type) != COMPLEX_TYPE
1135 && TREE_CODE (f2->type) != VECTOR_TYPE)
1137 /* Put the integral type with the bigger precision first. */
1138 else if (INTEGRAL_TYPE_P (f1->type)
1139 && INTEGRAL_TYPE_P (f2->type))
1140 return TYPE_PRECISION (f1->type) > TYPE_PRECISION (f2->type) ? -1 : 1;
1141 /* Put any integral type with non-full precision last. */
1142 else if (INTEGRAL_TYPE_P (f1->type)
1143 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1144 != TYPE_PRECISION (f1->type)))
1146 else if (INTEGRAL_TYPE_P (f2->type)
1147 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1148 != TYPE_PRECISION (f2->type)))
1150 /* Stabilize the sort. */
1151 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1154 /* We want the bigger accesses first, thus the opposite operator in the next
1156 return f1->size > f2->size ? -1 : 1;
1160 /* Append a name of the declaration to the name obstack. A helper function for
1164 make_fancy_decl_name (tree decl)
1168 tree name = DECL_NAME (decl);
1170 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1171 IDENTIFIER_LENGTH (name));
1174 sprintf (buffer, "D%u", DECL_UID (decl));
1175 obstack_grow (&name_obstack, buffer, strlen (buffer));
1179 /* Helper for make_fancy_name. */
1182 make_fancy_name_1 (tree expr)
1189 make_fancy_decl_name (expr);
1193 switch (TREE_CODE (expr))
1196 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1197 obstack_1grow (&name_obstack, '$');
1198 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1202 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1203 obstack_1grow (&name_obstack, '$');
1204 /* Arrays with only one element may not have a constant as their
1206 index = TREE_OPERAND (expr, 1);
1207 if (TREE_CODE (index) != INTEGER_CST)
1209 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1210 obstack_grow (&name_obstack, buffer, strlen (buffer));
1217 gcc_unreachable (); /* we treat these as scalars. */
1224 /* Create a human readable name for replacement variable of ACCESS. */
1227 make_fancy_name (tree expr)
1229 make_fancy_name_1 (expr);
1230 obstack_1grow (&name_obstack, '\0');
1231 return XOBFINISH (&name_obstack, char *);
1234 /* Helper function for build_ref_for_offset. */
1237 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1243 tree tr_size, index, minidx;
1244 HOST_WIDE_INT el_size;
1246 if (offset == 0 && exp_type
1247 && types_compatible_p (exp_type, type))
1250 switch (TREE_CODE (type))
1253 case QUAL_UNION_TYPE:
1255 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1257 HOST_WIDE_INT pos, size;
1258 tree expr, *expr_ptr;
1260 if (TREE_CODE (fld) != FIELD_DECL)
1263 pos = int_bit_position (fld);
1264 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1265 tr_size = DECL_SIZE (fld);
1266 if (!tr_size || !host_integerp (tr_size, 1))
1268 size = tree_low_cst (tr_size, 1);
1269 if (pos > offset || (pos + size) <= offset)
1274 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1280 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1281 offset - pos, exp_type))
1291 tr_size = TYPE_SIZE (TREE_TYPE (type));
1292 if (!tr_size || !host_integerp (tr_size, 1))
1294 el_size = tree_low_cst (tr_size, 1);
1296 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1297 if (TREE_CODE (minidx) != INTEGER_CST)
1301 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1302 if (!integer_zerop (minidx))
1303 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1304 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1305 NULL_TREE, NULL_TREE);
1307 offset = offset % el_size;
1308 type = TREE_TYPE (type);
1323 /* Construct an expression that would reference a part of aggregate *EXPR of
1324 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1325 function only determines whether it can build such a reference without
1326 actually doing it, otherwise, the tree it points to is unshared first and
1327 then used as a base for furhter sub-references.
1329 FIXME: Eventually this should be replaced with
1330 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1331 minor rewrite of fold_stmt.
1335 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1336 tree exp_type, bool allow_ptr)
1338 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1341 *expr = unshare_expr (*expr);
1343 if (allow_ptr && POINTER_TYPE_P (type))
1345 type = TREE_TYPE (type);
1347 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1350 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1353 /* Return true iff TYPE is stdarg va_list type. */
1356 is_va_list_type (tree type)
1358 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1361 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1362 those with type which is suitable for scalarization. */
1365 find_var_candidates (void)
1368 referenced_var_iterator rvi;
1371 FOR_EACH_REFERENCED_VAR (var, rvi)
1373 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1375 type = TREE_TYPE (var);
1377 if (!AGGREGATE_TYPE_P (type)
1378 || needs_to_live_in_memory (var)
1379 || TREE_THIS_VOLATILE (var)
1380 || !COMPLETE_TYPE_P (type)
1381 || !host_integerp (TYPE_SIZE (type), 1)
1382 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1383 || type_internals_preclude_sra_p (type)
1384 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1385 we also want to schedule it rather late. Thus we ignore it in
1387 || (sra_mode == SRA_MODE_EARLY_INTRA
1388 && is_va_list_type (type)))
1391 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1393 if (dump_file && (dump_flags & TDF_DETAILS))
1395 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1396 print_generic_expr (dump_file, var, 0);
1397 fprintf (dump_file, "\n");
1405 /* Sort all accesses for the given variable, check for partial overlaps and
1406 return NULL if there are any. If there are none, pick a representative for
1407 each combination of offset and size and create a linked list out of them.
1408 Return the pointer to the first representative and make sure it is the first
1409 one in the vector of accesses. */
1411 static struct access *
1412 sort_and_splice_var_accesses (tree var)
1414 int i, j, access_count;
1415 struct access *res, **prev_acc_ptr = &res;
1416 VEC (access_p, heap) *access_vec;
1418 HOST_WIDE_INT low = -1, high = 0;
1420 access_vec = get_base_access_vector (var);
1423 access_count = VEC_length (access_p, access_vec);
1425 /* Sort by <OFFSET, SIZE>. */
1426 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1427 compare_access_positions);
1430 while (i < access_count)
1432 struct access *access = VEC_index (access_p, access_vec, i);
1433 bool grp_write = access->write;
1434 bool grp_read = !access->write;
1435 bool multiple_reads = false;
1436 bool grp_partial_lhs = access->grp_partial_lhs;
1437 bool grp_different_types = false;
1438 bool first_scalar = is_gimple_reg_type (access->type);
1439 bool unscalarizable_region = access->grp_unscalarizable_region;
1441 if (first || access->offset >= high)
1444 low = access->offset;
1445 high = access->offset + access->size;
1447 else if (access->offset > low && access->offset + access->size > high)
1450 gcc_assert (access->offset >= low
1451 && access->offset + access->size <= high);
1454 while (j < access_count)
1456 struct access *ac2 = VEC_index (access_p, access_vec, j);
1457 if (ac2->offset != access->offset || ac2->size != access->size)
1464 multiple_reads = true;
1468 grp_partial_lhs |= ac2->grp_partial_lhs;
1469 grp_different_types |= !types_compatible_p (access->type, ac2->type);
1470 unscalarizable_region |= ac2->grp_unscalarizable_region;
1471 relink_to_new_repr (access, ac2);
1473 /* If there are both aggregate-type and scalar-type accesses with
1474 this combination of size and offset, the comparison function
1475 should have put the scalars first. */
1476 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1477 ac2->group_representative = access;
1483 access->group_representative = access;
1484 access->grp_write = grp_write;
1485 access->grp_read = grp_read;
1486 access->grp_hint = multiple_reads;
1487 access->grp_partial_lhs = grp_partial_lhs;
1488 access->grp_different_types = grp_different_types;
1489 access->grp_unscalarizable_region = unscalarizable_region;
1490 if (access->first_link)
1491 add_access_to_work_queue (access);
1493 *prev_acc_ptr = access;
1494 prev_acc_ptr = &access->next_grp;
1497 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1501 /* Create a variable for the given ACCESS which determines the type, name and a
1502 few other properties. Return the variable declaration and store it also to
1503 ACCESS->replacement. */
1506 create_access_replacement (struct access *access)
1510 repl = create_tmp_var (access->type, "SR");
1512 add_referenced_var (repl);
1513 mark_sym_for_renaming (repl);
1515 if (!access->grp_partial_lhs
1516 && (TREE_CODE (access->type) == COMPLEX_TYPE
1517 || TREE_CODE (access->type) == VECTOR_TYPE))
1518 DECL_GIMPLE_REG_P (repl) = 1;
1520 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1521 DECL_ARTIFICIAL (repl) = 1;
1523 if (DECL_NAME (access->base)
1524 && !DECL_IGNORED_P (access->base)
1525 && !DECL_ARTIFICIAL (access->base))
1527 char *pretty_name = make_fancy_name (access->expr);
1529 DECL_NAME (repl) = get_identifier (pretty_name);
1530 obstack_free (&name_obstack, pretty_name);
1532 SET_DECL_DEBUG_EXPR (repl, access->expr);
1533 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1534 DECL_IGNORED_P (repl) = 0;
1537 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1538 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1542 fprintf (dump_file, "Created a replacement for ");
1543 print_generic_expr (dump_file, access->base, 0);
1544 fprintf (dump_file, " offset: %u, size: %u: ",
1545 (unsigned) access->offset, (unsigned) access->size);
1546 print_generic_expr (dump_file, repl, 0);
1547 fprintf (dump_file, "\n");
1549 sra_stats.replacements++;
1554 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1557 get_access_replacement (struct access *access)
1559 gcc_assert (access->grp_to_be_replaced);
1561 if (!access->replacement_decl)
1562 access->replacement_decl = create_access_replacement (access);
1563 return access->replacement_decl;
1566 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1567 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1568 to it is not "within" the root. */
1571 build_access_subtree (struct access **access)
1573 struct access *root = *access, *last_child = NULL;
1574 HOST_WIDE_INT limit = root->offset + root->size;
1576 *access = (*access)->next_grp;
1577 while (*access && (*access)->offset + (*access)->size <= limit)
1580 root->first_child = *access;
1582 last_child->next_sibling = *access;
1583 last_child = *access;
1585 build_access_subtree (access);
1589 /* Build a tree of access representatives, ACCESS is the pointer to the first
1590 one, others are linked in a list by the next_grp field. Decide about scalar
1591 replacements on the way, return true iff any are to be created. */
1594 build_access_trees (struct access *access)
1598 struct access *root = access;
1600 build_access_subtree (&access);
1601 root->next_grp = access;
1605 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1609 expr_with_var_bounded_array_refs_p (tree expr)
1611 while (handled_component_p (expr))
1613 if (TREE_CODE (expr) == ARRAY_REF
1614 && !host_integerp (array_ref_low_bound (expr), 0))
1616 expr = TREE_OPERAND (expr, 0);
1621 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1622 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1623 all sorts of access flags appropriately along the way, notably always ser
1624 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1627 analyze_access_subtree (struct access *root, bool allow_replacements,
1628 bool mark_read, bool mark_write)
1630 struct access *child;
1631 HOST_WIDE_INT limit = root->offset + root->size;
1632 HOST_WIDE_INT covered_to = root->offset;
1633 bool scalar = is_gimple_reg_type (root->type);
1634 bool hole = false, sth_created = false;
1635 bool direct_read = root->grp_read;
1638 root->grp_read = true;
1639 else if (root->grp_read)
1643 root->grp_write = true;
1644 else if (root->grp_write)
1647 if (root->grp_unscalarizable_region)
1648 allow_replacements = false;
1650 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1651 allow_replacements = false;
1653 for (child = root->first_child; child; child = child->next_sibling)
1655 if (!hole && child->offset < covered_to)
1658 covered_to += child->size;
1660 sth_created |= analyze_access_subtree (child, allow_replacements,
1661 mark_read, mark_write);
1663 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1664 hole |= !child->grp_covered;
1667 if (allow_replacements && scalar && !root->first_child
1669 || (direct_read && root->grp_write)))
1671 if (dump_file && (dump_flags & TDF_DETAILS))
1673 fprintf (dump_file, "Marking ");
1674 print_generic_expr (dump_file, root->base, 0);
1675 fprintf (dump_file, " offset: %u, size: %u: ",
1676 (unsigned) root->offset, (unsigned) root->size);
1677 fprintf (dump_file, " to be replaced.\n");
1680 root->grp_to_be_replaced = 1;
1684 else if (covered_to < limit)
1687 if (sth_created && !hole)
1689 root->grp_covered = 1;
1692 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1693 root->grp_unscalarized_data = 1; /* not covered and written to */
1699 /* Analyze all access trees linked by next_grp by the means of
1700 analyze_access_subtree. */
1702 analyze_access_trees (struct access *access)
1708 if (analyze_access_subtree (access, true, false, false))
1710 access = access->next_grp;
1716 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1717 SIZE would conflict with an already existing one. If exactly such a child
1718 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1721 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1722 HOST_WIDE_INT size, struct access **exact_match)
1724 struct access *child;
1726 for (child = lacc->first_child; child; child = child->next_sibling)
1728 if (child->offset == norm_offset && child->size == size)
1730 *exact_match = child;
1734 if (child->offset < norm_offset + size
1735 && child->offset + child->size > norm_offset)
1742 /* Create a new child access of PARENT, with all properties just like MODEL
1743 except for its offset and with its grp_write false and grp_read true.
1744 Return the new access or NULL if it cannot be created. Note that this access
1745 is created long after all splicing and sorting, it's not located in any
1746 access vector and is automatically a representative of its group. */
1748 static struct access *
1749 create_artificial_child_access (struct access *parent, struct access *model,
1750 HOST_WIDE_INT new_offset)
1752 struct access *access;
1753 struct access **child;
1754 tree expr = parent->base;;
1756 gcc_assert (!model->grp_unscalarizable_region);
1758 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1759 model->type, false))
1762 access = (struct access *) pool_alloc (access_pool);
1763 memset (access, 0, sizeof (struct access));
1764 access->base = parent->base;
1765 access->expr = expr;
1766 access->offset = new_offset;
1767 access->size = model->size;
1768 access->type = model->type;
1769 access->grp_write = true;
1770 access->grp_read = false;
1772 child = &parent->first_child;
1773 while (*child && (*child)->offset < new_offset)
1774 child = &(*child)->next_sibling;
1776 access->next_sibling = *child;
1783 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1784 true if any new subaccess was created. Additionally, if RACC is a scalar
1785 access but LACC is not, change the type of the latter, if possible. */
1788 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1790 struct access *rchild;
1791 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1794 if (is_gimple_reg_type (lacc->type)
1795 || lacc->grp_unscalarizable_region
1796 || racc->grp_unscalarizable_region)
1799 if (!lacc->first_child && !racc->first_child
1800 && is_gimple_reg_type (racc->type))
1802 tree t = lacc->base;
1804 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1808 lacc->type = racc->type;
1813 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1815 struct access *new_acc = NULL;
1816 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1818 if (rchild->grp_unscalarizable_region)
1821 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1826 rchild->grp_hint = 1;
1827 new_acc->grp_hint |= new_acc->grp_read;
1828 if (rchild->first_child)
1829 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1834 /* If a (part of) a union field is on the RHS of an assignment, it can
1835 have sub-accesses which do not make sense on the LHS (PR 40351).
1836 Check that this is not the case. */
1837 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1838 rchild->type, false))
1841 rchild->grp_hint = 1;
1842 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1846 if (racc->first_child)
1847 propagate_subaccesses_across_link (new_acc, rchild);
1854 /* Propagate all subaccesses across assignment links. */
1857 propagate_all_subaccesses (void)
1859 while (work_queue_head)
1861 struct access *racc = pop_access_from_work_queue ();
1862 struct assign_link *link;
1864 gcc_assert (racc->first_link);
1866 for (link = racc->first_link; link; link = link->next)
1868 struct access *lacc = link->lacc;
1870 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1872 lacc = lacc->group_representative;
1873 if (propagate_subaccesses_across_link (lacc, racc)
1874 && lacc->first_link)
1875 add_access_to_work_queue (lacc);
1880 /* Go through all accesses collected throughout the (intraprocedural) analysis
1881 stage, exclude overlapping ones, identify representatives and build trees
1882 out of them, making decisions about scalarization on the way. Return true
1883 iff there are any to-be-scalarized variables after this stage. */
1886 analyze_all_variable_accesses (void)
1889 referenced_var_iterator rvi;
1892 FOR_EACH_REFERENCED_VAR (var, rvi)
1893 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1895 struct access *access;
1897 access = sort_and_splice_var_accesses (var);
1899 build_access_trees (access);
1901 disqualify_candidate (var,
1902 "No or inhibitingly overlapping accesses.");
1905 propagate_all_subaccesses ();
1907 FOR_EACH_REFERENCED_VAR (var, rvi)
1908 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1910 struct access *access = get_first_repr_for_decl (var);
1912 if (analyze_access_trees (access))
1915 if (dump_file && (dump_flags & TDF_DETAILS))
1917 fprintf (dump_file, "\nAccess trees for ");
1918 print_generic_expr (dump_file, var, 0);
1919 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1920 dump_access_tree (dump_file, access);
1921 fprintf (dump_file, "\n");
1925 disqualify_candidate (var, "No scalar replacements to be created.");
1930 statistics_counter_event (cfun, "Scalarized aggregates", res);
1937 /* Return true iff a reference statement into aggregate AGG can be built for
1938 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1939 or a child of its sibling. TOP_OFFSET is the offset from the processed
1940 access subtree that has to be subtracted from offset of each access. */
1943 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1944 HOST_WIDE_INT top_offset)
1948 if (access->grp_to_be_replaced
1949 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1950 access->offset - top_offset,
1951 access->type, false))
1954 if (access->first_child
1955 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1959 access = access->next_sibling;
1966 /* Generate statements copying scalar replacements of accesses within a subtree
1967 into or out of AGG. ACCESS is the first child of the root of the subtree to
1968 be processed. AGG is an aggregate type expression (can be a declaration but
1969 does not have to be, it can for example also be an indirect_ref).
1970 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1971 from offsets of individual accesses to get corresponding offsets for AGG.
1972 If CHUNK_SIZE is non-null, copy only replacements in the interval
1973 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1974 statement iterator used to place the new statements. WRITE should be true
1975 when the statements should write from AGG to the replacement and false if
1976 vice versa. if INSERT_AFTER is true, new statements will be added after the
1977 current statement in GSI, they will be added before the statement
1981 generate_subtree_copies (struct access *access, tree agg,
1982 HOST_WIDE_INT top_offset,
1983 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1984 gimple_stmt_iterator *gsi, bool write,
1991 if (chunk_size && access->offset >= start_offset + chunk_size)
1994 if (access->grp_to_be_replaced
1996 || access->offset + access->size > start_offset))
1998 tree repl = get_access_replacement (access);
2002 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2003 access->offset - top_offset,
2004 access->type, false);
2005 gcc_assert (ref_found);
2009 if (access->grp_partial_lhs)
2010 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2012 insert_after ? GSI_NEW_STMT
2014 stmt = gimple_build_assign (repl, expr);
2018 TREE_NO_WARNING (repl) = 1;
2019 if (access->grp_partial_lhs)
2020 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2022 insert_after ? GSI_NEW_STMT
2024 stmt = gimple_build_assign (expr, repl);
2028 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2030 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2032 sra_stats.subtree_copies++;
2035 if (access->first_child)
2036 generate_subtree_copies (access->first_child, agg, top_offset,
2037 start_offset, chunk_size, gsi,
2038 write, insert_after);
2040 access = access->next_sibling;
2045 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2046 the root of the subtree to be processed. GSI is the statement iterator used
2047 for inserting statements which are added after the current statement if
2048 INSERT_AFTER is true or before it otherwise. */
2051 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2055 struct access *child;
2057 if (access->grp_to_be_replaced)
2061 stmt = gimple_build_assign (get_access_replacement (access),
2062 fold_convert (access->type,
2063 integer_zero_node));
2065 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2067 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2071 for (child = access->first_child; child; child = child->next_sibling)
2072 init_subtree_with_zero (child, gsi, insert_after);
2075 /* Search for an access representative for the given expression EXPR and
2076 return it or NULL if it cannot be found. */
2078 static struct access *
2079 get_access_for_expr (tree expr)
2081 HOST_WIDE_INT offset, size, max_size;
2084 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2085 a different size than the size of its argument and we need the latter
2087 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2088 expr = TREE_OPERAND (expr, 0);
2090 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2091 if (max_size == -1 || !DECL_P (base))
2094 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2097 return get_var_base_offset_size_access (base, offset, max_size);
2100 /* Callback for scan_function. Replace the expression EXPR with a scalar
2101 replacement if there is one and generate other statements to do type
2102 conversion or subtree copying if necessary. GSI is used to place newly
2103 created statements, WRITE is true if the expression is being written to (it
2104 is on a LHS of a statement or output in an assembly statement). */
2107 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2108 void *data ATTRIBUTE_UNUSED)
2110 struct access *access;
2113 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2116 expr = &TREE_OPERAND (*expr, 0);
2121 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2122 expr = &TREE_OPERAND (*expr, 0);
2123 access = get_access_for_expr (*expr);
2126 type = TREE_TYPE (*expr);
2128 if (access->grp_to_be_replaced)
2130 tree repl = get_access_replacement (access);
2131 /* If we replace a non-register typed access simply use the original
2132 access expression to extract the scalar component afterwards.
2133 This happens if scalarizing a function return value or parameter
2134 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2135 gcc.c-torture/compile/20011217-1.c.
2137 We also want to use this when accessing a complex or vector which can
2138 be accessed as a different type too, potentially creating a need for
2139 type conversion (see PR42196). */
2140 if (!is_gimple_reg_type (type)
2141 || (access->grp_different_types
2142 && (TREE_CODE (type) == COMPLEX_TYPE
2143 || TREE_CODE (type) == VECTOR_TYPE)))
2145 tree ref = access->base;
2148 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2149 access->offset, access->type, false);
2156 if (access->grp_partial_lhs)
2157 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2158 false, GSI_NEW_STMT);
2159 stmt = gimple_build_assign (repl, ref);
2160 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2166 if (access->grp_partial_lhs)
2167 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2168 true, GSI_SAME_STMT);
2169 stmt = gimple_build_assign (ref, repl);
2170 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2175 gcc_assert (useless_type_conversion_p (type, access->type));
2181 if (access->first_child)
2183 HOST_WIDE_INT start_offset, chunk_size;
2185 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2186 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2188 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2189 start_offset = access->offset
2190 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2193 start_offset = chunk_size = 0;
2195 generate_subtree_copies (access->first_child, access->base, 0,
2196 start_offset, chunk_size, gsi, write, write);
2201 /* Where scalar replacements of the RHS have been written to when a replacement
2202 of a LHS of an assigments cannot be direclty loaded from a replacement of
2204 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2205 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2206 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2208 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2209 base aggregate if there are unscalarized data or directly to LHS
2212 static enum unscalarized_data_handling
2213 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2214 gimple_stmt_iterator *gsi)
2216 if (top_racc->grp_unscalarized_data)
2218 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2220 return SRA_UDH_RIGHT;
2224 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2225 0, 0, gsi, false, false);
2226 return SRA_UDH_LEFT;
2231 /* Try to generate statements to load all sub-replacements in an access
2232 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2233 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2234 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2235 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2236 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2237 the rhs top aggregate has already been refreshed by contents of its scalar
2238 reductions and is set to true if this function has to do it. */
2241 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2242 HOST_WIDE_INT left_offset,
2243 HOST_WIDE_INT right_offset,
2244 gimple_stmt_iterator *old_gsi,
2245 gimple_stmt_iterator *new_gsi,
2246 enum unscalarized_data_handling *refreshed,
2249 location_t loc = EXPR_LOCATION (lacc->expr);
2252 if (lacc->grp_to_be_replaced)
2254 struct access *racc;
2255 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2259 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2260 if (racc && racc->grp_to_be_replaced)
2262 rhs = get_access_replacement (racc);
2263 if (!useless_type_conversion_p (lacc->type, racc->type))
2264 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2268 /* No suitable access on the right hand side, need to load from
2269 the aggregate. See if we have to update it first... */
2270 if (*refreshed == SRA_UDH_NONE)
2271 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2274 if (*refreshed == SRA_UDH_LEFT)
2279 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2280 lacc->offset, lacc->type,
2282 gcc_assert (repl_found);
2288 rhs = top_racc->base;
2289 repl_found = build_ref_for_offset (&rhs,
2290 TREE_TYPE (top_racc->base),
2291 offset, lacc->type, false);
2292 gcc_assert (repl_found);
2296 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2297 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2299 sra_stats.subreplacements++;
2301 else if (*refreshed == SRA_UDH_NONE
2302 && lacc->grp_read && !lacc->grp_covered)
2303 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2306 if (lacc->first_child)
2307 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2308 left_offset, right_offset,
2309 old_gsi, new_gsi, refreshed, lhs);
2310 lacc = lacc->next_sibling;
2315 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2316 to the assignment and GSI is the statement iterator pointing at it. Returns
2317 the same values as sra_modify_assign. */
2319 static enum scan_assign_result
2320 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2322 tree lhs = gimple_assign_lhs (*stmt);
2325 acc = get_access_for_expr (lhs);
2329 if (VEC_length (constructor_elt,
2330 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2332 /* I have never seen this code path trigger but if it can happen the
2333 following should handle it gracefully. */
2334 if (access_has_children_p (acc))
2335 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2337 return SRA_SA_PROCESSED;
2340 if (acc->grp_covered)
2342 init_subtree_with_zero (acc, gsi, false);
2343 unlink_stmt_vdef (*stmt);
2344 gsi_remove (gsi, true);
2345 return SRA_SA_REMOVED;
2349 init_subtree_with_zero (acc, gsi, true);
2350 return SRA_SA_PROCESSED;
2355 /* Callback of scan_function to process assign statements. It examines both
2356 sides of the statement, replaces them with a scalare replacement if there is
2357 one and generating copying of replacements if scalarized aggregates have been
2358 used in the assignment. STMT is a pointer to the assign statement, GSI is
2359 used to hold generated statements for type conversions and subtree
2362 static enum scan_assign_result
2363 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2364 void *data ATTRIBUTE_UNUSED)
2366 struct access *lacc, *racc;
2368 bool modify_this_stmt = false;
2369 bool force_gimple_rhs = false;
2370 location_t loc = gimple_location (*stmt);
2372 if (!gimple_assign_single_p (*stmt))
2374 lhs = gimple_assign_lhs (*stmt);
2375 rhs = gimple_assign_rhs1 (*stmt);
2377 if (TREE_CODE (rhs) == CONSTRUCTOR)
2378 return sra_modify_constructor_assign (stmt, gsi);
2380 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2381 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2382 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2384 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2386 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2388 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2391 lacc = get_access_for_expr (lhs);
2392 racc = get_access_for_expr (rhs);
2396 if (lacc && lacc->grp_to_be_replaced)
2398 lhs = get_access_replacement (lacc);
2399 gimple_assign_set_lhs (*stmt, lhs);
2400 modify_this_stmt = true;
2401 if (lacc->grp_partial_lhs)
2402 force_gimple_rhs = true;
2406 if (racc && racc->grp_to_be_replaced)
2408 rhs = get_access_replacement (racc);
2409 modify_this_stmt = true;
2410 if (racc->grp_partial_lhs)
2411 force_gimple_rhs = true;
2415 if (modify_this_stmt)
2417 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2419 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2420 ??? This should move to fold_stmt which we simply should
2421 call after building a VIEW_CONVERT_EXPR here. */
2422 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2423 && !access_has_children_p (lacc))
2426 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2427 TREE_TYPE (rhs), false))
2430 gimple_assign_set_lhs (*stmt, expr);
2433 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2434 && !access_has_children_p (racc))
2437 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2438 TREE_TYPE (lhs), false))
2441 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2443 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2444 if (is_gimple_reg_type (TREE_TYPE (lhs))
2445 && TREE_CODE (lhs) != SSA_NAME)
2446 force_gimple_rhs = true;
2450 if (force_gimple_rhs)
2451 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2452 true, GSI_SAME_STMT);
2453 if (gimple_assign_rhs1 (*stmt) != rhs)
2455 gimple_assign_set_rhs_from_tree (gsi, rhs);
2456 gcc_assert (*stmt == gsi_stmt (*gsi));
2460 /* From this point on, the function deals with assignments in between
2461 aggregates when at least one has scalar reductions of some of its
2462 components. There are three possible scenarios: Both the LHS and RHS have
2463 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2465 In the first case, we would like to load the LHS components from RHS
2466 components whenever possible. If that is not possible, we would like to
2467 read it directly from the RHS (after updating it by storing in it its own
2468 components). If there are some necessary unscalarized data in the LHS,
2469 those will be loaded by the original assignment too. If neither of these
2470 cases happen, the original statement can be removed. Most of this is done
2471 by load_assign_lhs_subreplacements.
2473 In the second case, we would like to store all RHS scalarized components
2474 directly into LHS and if they cover the aggregate completely, remove the
2475 statement too. In the third case, we want the LHS components to be loaded
2476 directly from the RHS (DSE will remove the original statement if it
2479 This is a bit complex but manageable when types match and when unions do
2480 not cause confusion in a way that we cannot really load a component of LHS
2481 from the RHS or vice versa (the access representing this level can have
2482 subaccesses that are accessible only through a different union field at a
2483 higher level - different from the one used in the examined expression).
2486 Therefore, I specially handle a fourth case, happening when there is a
2487 specific type cast or it is impossible to locate a scalarized subaccess on
2488 the other side of the expression. If that happens, I simply "refresh" the
2489 RHS by storing in it is scalarized components leave the original statement
2490 there to do the copying and then load the scalar replacements of the LHS.
2491 This is what the first branch does. */
2493 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2494 || (access_has_children_p (racc)
2495 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2496 || (access_has_children_p (lacc)
2497 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2499 if (access_has_children_p (racc))
2500 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2502 if (access_has_children_p (lacc))
2503 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2505 sra_stats.separate_lhs_rhs_handling++;
2509 if (access_has_children_p (lacc) && access_has_children_p (racc))
2511 gimple_stmt_iterator orig_gsi = *gsi;
2512 enum unscalarized_data_handling refreshed;
2514 if (lacc->grp_read && !lacc->grp_covered)
2515 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2517 refreshed = SRA_UDH_NONE;
2519 load_assign_lhs_subreplacements (lacc->first_child, racc,
2520 lacc->offset, racc->offset,
2521 &orig_gsi, gsi, &refreshed, lhs);
2522 if (refreshed != SRA_UDH_RIGHT)
2524 if (*stmt == gsi_stmt (*gsi))
2527 unlink_stmt_vdef (*stmt);
2528 gsi_remove (&orig_gsi, true);
2529 sra_stats.deleted++;
2530 return SRA_SA_REMOVED;
2535 if (access_has_children_p (racc))
2537 if (!racc->grp_unscalarized_data)
2539 generate_subtree_copies (racc->first_child, lhs,
2540 racc->offset, 0, 0, gsi,
2542 gcc_assert (*stmt == gsi_stmt (*gsi));
2543 unlink_stmt_vdef (*stmt);
2544 gsi_remove (gsi, true);
2545 sra_stats.deleted++;
2546 return SRA_SA_REMOVED;
2549 generate_subtree_copies (racc->first_child, lhs,
2550 racc->offset, 0, 0, gsi, false, true);
2552 else if (access_has_children_p (lacc))
2553 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2554 0, 0, gsi, true, true);
2557 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2560 /* Generate statements initializing scalar replacements of parts of function
2564 initialize_parameter_reductions (void)
2566 gimple_stmt_iterator gsi;
2567 gimple_seq seq = NULL;
2570 for (parm = DECL_ARGUMENTS (current_function_decl);
2572 parm = TREE_CHAIN (parm))
2574 VEC (access_p, heap) *access_vec;
2575 struct access *access;
2577 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2579 access_vec = get_base_access_vector (parm);
2585 seq = gimple_seq_alloc ();
2586 gsi = gsi_start (seq);
2589 for (access = VEC_index (access_p, access_vec, 0);
2591 access = access->next_grp)
2592 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2596 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2599 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2600 it reveals there are components of some aggregates to be scalarized, it runs
2601 the required transformations. */
2603 perform_intra_sra (void)
2608 if (!find_var_candidates ())
2611 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2615 if (!analyze_all_variable_accesses ())
2618 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2619 initialize_parameter_reductions ();
2621 statistics_counter_event (cfun, "Scalar replacements created",
2622 sra_stats.replacements);
2623 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2624 statistics_counter_event (cfun, "Subtree copy stmts",
2625 sra_stats.subtree_copies);
2626 statistics_counter_event (cfun, "Subreplacement stmts",
2627 sra_stats.subreplacements);
2628 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2629 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2630 sra_stats.separate_lhs_rhs_handling);
2632 ret = TODO_update_ssa;
2635 sra_deinitialize ();
2639 /* Perform early intraprocedural SRA. */
2641 early_intra_sra (void)
2643 sra_mode = SRA_MODE_EARLY_INTRA;
2644 return perform_intra_sra ();
2647 /* Perform "late" intraprocedural SRA. */
2649 late_intra_sra (void)
2651 sra_mode = SRA_MODE_INTRA;
2652 return perform_intra_sra ();
2657 gate_intra_sra (void)
2659 return flag_tree_sra != 0;
2663 struct gimple_opt_pass pass_sra_early =
2668 gate_intra_sra, /* gate */
2669 early_intra_sra, /* execute */
2672 0, /* static_pass_number */
2673 TV_TREE_SRA, /* tv_id */
2674 PROP_cfg | PROP_ssa, /* properties_required */
2675 0, /* properties_provided */
2676 0, /* properties_destroyed */
2677 0, /* todo_flags_start */
2681 | TODO_verify_ssa /* todo_flags_finish */
2685 struct gimple_opt_pass pass_sra =
2690 gate_intra_sra, /* gate */
2691 late_intra_sra, /* execute */
2694 0, /* static_pass_number */
2695 TV_TREE_SRA, /* tv_id */
2696 PROP_cfg | PROP_ssa, /* properties_required */
2697 0, /* properties_provided */
2698 0, /* properties_destroyed */
2699 TODO_update_address_taken, /* todo_flags_start */
2703 | TODO_verify_ssa /* todo_flags_finish */
2708 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2712 is_unused_scalar_param (tree parm)
2715 return (is_gimple_reg (parm)
2716 && (!(name = gimple_default_def (cfun, parm))
2717 || has_zero_uses (name)));
2720 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2721 examine whether there are any direct or otherwise infeasible ones. If so,
2722 return true, otherwise return false. PARM must be a gimple register with a
2723 non-NULL default definition. */
2726 ptr_parm_has_direct_uses (tree parm)
2728 imm_use_iterator ui;
2730 tree name = gimple_default_def (cfun, parm);
2733 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2735 if (gimple_assign_single_p (stmt))
2737 tree rhs = gimple_assign_rhs1 (stmt);
2740 else if (TREE_CODE (rhs) == ADDR_EXPR)
2744 rhs = TREE_OPERAND (rhs, 0);
2746 while (handled_component_p (rhs));
2747 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2751 else if (gimple_code (stmt) == GIMPLE_RETURN)
2753 tree t = gimple_return_retval (stmt);
2757 else if (is_gimple_call (stmt))
2760 for (i = 0; i < gimple_call_num_args (stmt); i++)
2762 tree arg = gimple_call_arg (stmt, i);
2770 else if (!is_gimple_debug (stmt))
2774 BREAK_FROM_IMM_USE_STMT (ui);
2780 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2781 them in candidate_bitmap. Note that these do not necessarily include
2782 parameter which are unused and thus can be removed. Return true iff any
2783 such candidate has been found. */
2786 find_param_candidates (void)
2792 for (parm = DECL_ARGUMENTS (current_function_decl);
2794 parm = TREE_CHAIN (parm))
2796 tree type = TREE_TYPE (parm);
2800 if (TREE_THIS_VOLATILE (parm)
2801 || TREE_ADDRESSABLE (parm)
2802 || is_va_list_type (type))
2805 if (is_unused_scalar_param (parm))
2811 if (POINTER_TYPE_P (type))
2813 type = TREE_TYPE (type);
2815 if (TREE_CODE (type) == FUNCTION_TYPE
2816 || TYPE_VOLATILE (type)
2817 || !is_gimple_reg (parm)
2818 || is_va_list_type (type)
2819 || ptr_parm_has_direct_uses (parm))
2822 else if (!AGGREGATE_TYPE_P (type))
2825 if (!COMPLETE_TYPE_P (type)
2826 || !host_integerp (TYPE_SIZE (type), 1)
2827 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2828 || (AGGREGATE_TYPE_P (type)
2829 && type_internals_preclude_sra_p (type)))
2832 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2834 if (dump_file && (dump_flags & TDF_DETAILS))
2836 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2837 print_generic_expr (dump_file, parm, 0);
2838 fprintf (dump_file, "\n");
2842 func_param_count = count;
2846 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2850 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2853 struct access *repr = (struct access *) data;
2855 repr->grp_maybe_modified = 1;
2859 /* Analyze what representatives (in linked lists accessible from
2860 REPRESENTATIVES) can be modified by side effects of statements in the
2861 current function. */
2864 analyze_modified_params (VEC (access_p, heap) *representatives)
2868 for (i = 0; i < func_param_count; i++)
2870 struct access *repr;
2872 for (repr = VEC_index (access_p, representatives, i);
2874 repr = repr->next_grp)
2876 struct access *access;
2880 if (no_accesses_p (repr))
2882 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
2883 || repr->grp_maybe_modified)
2886 ao_ref_init (&ar, repr->expr);
2887 visited = BITMAP_ALLOC (NULL);
2888 for (access = repr; access; access = access->next_sibling)
2890 /* All accesses are read ones, otherwise grp_maybe_modified would
2891 be trivially set. */
2892 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2893 mark_maybe_modified, repr, &visited);
2894 if (repr->grp_maybe_modified)
2897 BITMAP_FREE (visited);
2902 /* Propagate distances in bb_dereferences in the opposite direction than the
2903 control flow edges, in each step storing the maximum of the current value
2904 and the minimum of all successors. These steps are repeated until the table
2905 stabilizes. Note that BBs which might terminate the functions (according to
2906 final_bbs bitmap) never updated in this way. */
2909 propagate_dereference_distances (void)
2911 VEC (basic_block, heap) *queue;
2914 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2915 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2918 VEC_quick_push (basic_block, queue, bb);
2922 while (!VEC_empty (basic_block, queue))
2926 bool change = false;
2929 bb = VEC_pop (basic_block, queue);
2932 if (bitmap_bit_p (final_bbs, bb->index))
2935 for (i = 0; i < func_param_count; i++)
2937 int idx = bb->index * func_param_count + i;
2939 HOST_WIDE_INT inh = 0;
2941 FOR_EACH_EDGE (e, ei, bb->succs)
2943 int succ_idx = e->dest->index * func_param_count + i;
2945 if (e->src == EXIT_BLOCK_PTR)
2951 inh = bb_dereferences [succ_idx];
2953 else if (bb_dereferences [succ_idx] < inh)
2954 inh = bb_dereferences [succ_idx];
2957 if (!first && bb_dereferences[idx] < inh)
2959 bb_dereferences[idx] = inh;
2964 if (change && !bitmap_bit_p (final_bbs, bb->index))
2965 FOR_EACH_EDGE (e, ei, bb->preds)
2970 e->src->aux = e->src;
2971 VEC_quick_push (basic_block, queue, e->src);
2975 VEC_free (basic_block, heap, queue);
2978 /* Dump a dereferences TABLE with heading STR to file F. */
2981 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2985 fprintf (dump_file, str);
2986 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2988 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2989 if (bb != EXIT_BLOCK_PTR)
2992 for (i = 0; i < func_param_count; i++)
2994 int idx = bb->index * func_param_count + i;
2995 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3000 fprintf (dump_file, "\n");
3003 /* Determine what (parts of) parameters passed by reference that are not
3004 assigned to are not certainly dereferenced in this function and thus the
3005 dereferencing cannot be safely moved to the caller without potentially
3006 introducing a segfault. Mark such REPRESENTATIVES as
3007 grp_not_necessarilly_dereferenced.
3009 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3010 part is calculated rather than simple booleans are calculated for each
3011 pointer parameter to handle cases when only a fraction of the whole
3012 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3015 The maximum dereference distances for each pointer parameter and BB are
3016 already stored in bb_dereference. This routine simply propagates these
3017 values upwards by propagate_dereference_distances and then compares the
3018 distances of individual parameters in the ENTRY BB to the equivalent
3019 distances of each representative of a (fraction of a) parameter. */
3022 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3026 if (dump_file && (dump_flags & TDF_DETAILS))
3027 dump_dereferences_table (dump_file,
3028 "Dereference table before propagation:\n",
3031 propagate_dereference_distances ();
3033 if (dump_file && (dump_flags & TDF_DETAILS))
3034 dump_dereferences_table (dump_file,
3035 "Dereference table after propagation:\n",
3038 for (i = 0; i < func_param_count; i++)
3040 struct access *repr = VEC_index (access_p, representatives, i);
3041 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3043 if (!repr || no_accesses_p (repr))
3048 if ((repr->offset + repr->size) > bb_dereferences[idx])
3049 repr->grp_not_necessarilly_dereferenced = 1;
3050 repr = repr->next_grp;
3056 /* Return the representative access for the parameter declaration PARM if it is
3057 a scalar passed by reference which is not written to and the pointer value
3058 is not used directly. Thus, if it is legal to dereference it in the caller
3059 and we can rule out modifications through aliases, such parameter should be
3060 turned into one passed by value. Return NULL otherwise. */
3062 static struct access *
3063 unmodified_by_ref_scalar_representative (tree parm)
3065 int i, access_count;
3066 struct access *repr;
3067 VEC (access_p, heap) *access_vec;
3069 access_vec = get_base_access_vector (parm);
3070 gcc_assert (access_vec);
3071 repr = VEC_index (access_p, access_vec, 0);
3074 repr->group_representative = repr;
3076 access_count = VEC_length (access_p, access_vec);
3077 for (i = 1; i < access_count; i++)
3079 struct access *access = VEC_index (access_p, access_vec, i);
3082 access->group_representative = repr;
3083 access->next_sibling = repr->next_sibling;
3084 repr->next_sibling = access;
3088 repr->grp_scalar_ptr = 1;
3092 /* Return true iff this access precludes IPA-SRA of the parameter it is
3096 access_precludes_ipa_sra_p (struct access *access)
3098 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3099 is incompatible assign in a call statement (and possibly even in asm
3100 statements). This can be relaxed by using a new temporary but only for
3101 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3102 intraprocedural SRA we deal with this by keeping the old aggregate around,
3103 something we cannot do in IPA-SRA.) */
3105 && (is_gimple_call (access->stmt)
3106 || gimple_code (access->stmt) == GIMPLE_ASM))
3113 /* Sort collected accesses for parameter PARM, identify representatives for
3114 each accessed region and link them together. Return NULL if there are
3115 different but overlapping accesses, return the special ptr value meaning
3116 there are no accesses for this parameter if that is the case and return the
3117 first representative otherwise. Set *RO_GRP if there is a group of accesses
3118 with only read (i.e. no write) accesses. */
3120 static struct access *
3121 splice_param_accesses (tree parm, bool *ro_grp)
3123 int i, j, access_count, group_count;
3124 int agg_size, total_size = 0;
3125 struct access *access, *res, **prev_acc_ptr = &res;
3126 VEC (access_p, heap) *access_vec;
3128 access_vec = get_base_access_vector (parm);
3130 return &no_accesses_representant;
3131 access_count = VEC_length (access_p, access_vec);
3133 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3134 compare_access_positions);
3139 while (i < access_count)
3142 access = VEC_index (access_p, access_vec, i);
3143 modification = access->write;
3144 if (access_precludes_ipa_sra_p (access))
3147 /* Access is about to become group representative unless we find some
3148 nasty overlap which would preclude us from breaking this parameter
3152 while (j < access_count)
3154 struct access *ac2 = VEC_index (access_p, access_vec, j);
3155 if (ac2->offset != access->offset)
3157 /* All or nothing law for parameters. */
3158 if (access->offset + access->size > ac2->offset)
3163 else if (ac2->size != access->size)
3166 if (access_precludes_ipa_sra_p (ac2))
3169 modification |= ac2->write;
3170 ac2->group_representative = access;
3171 ac2->next_sibling = access->next_sibling;
3172 access->next_sibling = ac2;
3177 access->grp_maybe_modified = modification;
3180 *prev_acc_ptr = access;
3181 prev_acc_ptr = &access->next_grp;
3182 total_size += access->size;
3186 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3187 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3189 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3190 if (total_size >= agg_size)
3193 gcc_assert (group_count > 0);
3197 /* Decide whether parameters with representative accesses given by REPR should
3198 be reduced into components. */
3201 decide_one_param_reduction (struct access *repr)
3203 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3208 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3209 gcc_assert (cur_parm_size > 0);
3211 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3214 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3219 agg_size = cur_parm_size;
3225 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3226 print_generic_expr (dump_file, parm, 0);
3227 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3228 for (acc = repr; acc; acc = acc->next_grp)
3229 dump_access (dump_file, acc, true);
3233 new_param_count = 0;
3235 for (; repr; repr = repr->next_grp)
3237 gcc_assert (parm == repr->base);
3240 if (!by_ref || (!repr->grp_maybe_modified
3241 && !repr->grp_not_necessarilly_dereferenced))
3242 total_size += repr->size;
3244 total_size += cur_parm_size;
3247 gcc_assert (new_param_count > 0);
3249 if (optimize_function_for_size_p (cfun))
3250 parm_size_limit = cur_parm_size;
3252 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3255 if (total_size < agg_size
3256 && total_size <= parm_size_limit)
3259 fprintf (dump_file, " ....will be split into %i components\n",
3261 return new_param_count;
3267 /* The order of the following enums is important, we need to do extra work for
3268 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3269 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3270 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3272 /* Identify representatives of all accesses to all candidate parameters for
3273 IPA-SRA. Return result based on what representatives have been found. */
3275 static enum ipa_splicing_result
3276 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3278 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3280 struct access *repr;
3282 *representatives = VEC_alloc (access_p, heap, func_param_count);
3284 for (parm = DECL_ARGUMENTS (current_function_decl);
3286 parm = TREE_CHAIN (parm))
3288 if (is_unused_scalar_param (parm))
3290 VEC_quick_push (access_p, *representatives,
3291 &no_accesses_representant);
3292 if (result == NO_GOOD_ACCESS)
3293 result = UNUSED_PARAMS;
3295 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3296 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3297 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3299 repr = unmodified_by_ref_scalar_representative (parm);
3300 VEC_quick_push (access_p, *representatives, repr);
3302 result = UNMODIF_BY_REF_ACCESSES;
3304 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3306 bool ro_grp = false;
3307 repr = splice_param_accesses (parm, &ro_grp);
3308 VEC_quick_push (access_p, *representatives, repr);
3310 if (repr && !no_accesses_p (repr))
3312 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3315 result = UNMODIF_BY_REF_ACCESSES;
3316 else if (result < MODIF_BY_REF_ACCESSES)
3317 result = MODIF_BY_REF_ACCESSES;
3319 else if (result < BY_VAL_ACCESSES)
3320 result = BY_VAL_ACCESSES;
3322 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3323 result = UNUSED_PARAMS;
3326 VEC_quick_push (access_p, *representatives, NULL);
3329 if (result == NO_GOOD_ACCESS)
3331 VEC_free (access_p, heap, *representatives);
3332 *representatives = NULL;
3333 return NO_GOOD_ACCESS;
3339 /* Return the index of BASE in PARMS. Abort if it is not found. */
3342 get_param_index (tree base, VEC(tree, heap) *parms)
3346 len = VEC_length (tree, parms);
3347 for (i = 0; i < len; i++)
3348 if (VEC_index (tree, parms, i) == base)
3353 /* Convert the decisions made at the representative level into compact
3354 parameter adjustments. REPRESENTATIVES are pointers to first
3355 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3356 final number of adjustments. */
3358 static ipa_parm_adjustment_vec
3359 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3360 int adjustments_count)
3362 VEC (tree, heap) *parms;
3363 ipa_parm_adjustment_vec adjustments;
3367 gcc_assert (adjustments_count > 0);
3368 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3369 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3370 parm = DECL_ARGUMENTS (current_function_decl);
3371 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3373 struct access *repr = VEC_index (access_p, representatives, i);
3375 if (!repr || no_accesses_p (repr))
3377 struct ipa_parm_adjustment *adj;
3379 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3380 memset (adj, 0, sizeof (*adj));
3381 adj->base_index = get_param_index (parm, parms);
3384 adj->copy_param = 1;
3386 adj->remove_param = 1;
3390 struct ipa_parm_adjustment *adj;
3391 int index = get_param_index (parm, parms);
3393 for (; repr; repr = repr->next_grp)
3395 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3396 memset (adj, 0, sizeof (*adj));
3397 gcc_assert (repr->base == parm);
3398 adj->base_index = index;
3399 adj->base = repr->base;
3400 adj->type = repr->type;
3401 adj->offset = repr->offset;
3402 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3403 && (repr->grp_maybe_modified
3404 || repr->grp_not_necessarilly_dereferenced));
3409 VEC_free (tree, heap, parms);
3413 /* Analyze the collected accesses and produce a plan what to do with the
3414 parameters in the form of adjustments, NULL meaning nothing. */
3416 static ipa_parm_adjustment_vec
3417 analyze_all_param_acesses (void)
3419 enum ipa_splicing_result repr_state;
3420 bool proceed = false;
3421 int i, adjustments_count = 0;
3422 VEC (access_p, heap) *representatives;
3423 ipa_parm_adjustment_vec adjustments;
3425 repr_state = splice_all_param_accesses (&representatives);
3426 if (repr_state == NO_GOOD_ACCESS)
3429 /* If there are any parameters passed by reference which are not modified
3430 directly, we need to check whether they can be modified indirectly. */
3431 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3433 analyze_caller_dereference_legality (representatives);
3434 analyze_modified_params (representatives);
3437 for (i = 0; i < func_param_count; i++)
3439 struct access *repr = VEC_index (access_p, representatives, i);
3441 if (repr && !no_accesses_p (repr))
3443 if (repr->grp_scalar_ptr)
3445 adjustments_count++;
3446 if (repr->grp_not_necessarilly_dereferenced
3447 || repr->grp_maybe_modified)
3448 VEC_replace (access_p, representatives, i, NULL);
3452 sra_stats.scalar_by_ref_to_by_val++;
3457 int new_components = decide_one_param_reduction (repr);
3459 if (new_components == 0)
3461 VEC_replace (access_p, representatives, i, NULL);
3462 adjustments_count++;
3466 adjustments_count += new_components;
3467 sra_stats.aggregate_params_reduced++;
3468 sra_stats.param_reductions_created += new_components;
3475 if (no_accesses_p (repr))
3478 sra_stats.deleted_unused_parameters++;
3480 adjustments_count++;
3484 if (!proceed && dump_file)
3485 fprintf (dump_file, "NOT proceeding to change params.\n");
3488 adjustments = turn_representatives_into_adjustments (representatives,
3493 VEC_free (access_p, heap, representatives);
3497 /* If a parameter replacement identified by ADJ does not yet exist in the form
3498 of declaration, create it and record it, otherwise return the previously
3502 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3505 if (!adj->new_ssa_base)
3507 char *pretty_name = make_fancy_name (adj->base);
3509 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3510 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3511 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3512 DECL_GIMPLE_REG_P (repl) = 1;
3513 DECL_NAME (repl) = get_identifier (pretty_name);
3514 obstack_free (&name_obstack, pretty_name);
3517 add_referenced_var (repl);
3518 adj->new_ssa_base = repl;
3521 repl = adj->new_ssa_base;
3525 /* Find the first adjustment for a particular parameter BASE in a vector of
3526 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3529 static struct ipa_parm_adjustment *
3530 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3534 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3535 for (i = 0; i < len; i++)
3537 struct ipa_parm_adjustment *adj;
3539 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3540 if (!adj->copy_param && adj->base == base)
3547 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3548 parameter which is to be removed because its value is not used, replace the
3549 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3550 uses too and return true (update_stmt is then issued for the statement by
3551 the caller). DATA is a pointer to an adjustments vector. */
3554 replace_removed_params_ssa_names (gimple stmt, void *data)
3556 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3557 struct ipa_parm_adjustment *adj;
3558 tree lhs, decl, repl, name;
3560 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3561 if (gimple_code (stmt) == GIMPLE_PHI)
3562 lhs = gimple_phi_result (stmt);
3563 else if (is_gimple_assign (stmt))
3564 lhs = gimple_assign_lhs (stmt);
3565 else if (is_gimple_call (stmt))
3566 lhs = gimple_call_lhs (stmt);
3570 if (TREE_CODE (lhs) != SSA_NAME)
3572 decl = SSA_NAME_VAR (lhs);
3573 if (TREE_CODE (decl) != PARM_DECL)
3576 adj = get_adjustment_for_base (adjustments, decl);
3580 repl = get_replaced_param_substitute (adj);
3581 name = make_ssa_name (repl, stmt);
3585 fprintf (dump_file, "replacing an SSA name of a removed param ");
3586 print_generic_expr (dump_file, lhs, 0);
3587 fprintf (dump_file, " with ");
3588 print_generic_expr (dump_file, name, 0);
3589 fprintf (dump_file, "\n");
3592 if (is_gimple_assign (stmt))
3593 gimple_assign_set_lhs (stmt, name);
3594 else if (is_gimple_call (stmt))
3595 gimple_call_set_lhs (stmt, name);
3597 gimple_phi_set_result (stmt, name);
3599 replace_uses_by (lhs, name);
3603 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3604 expression *EXPR should be replaced by a reduction of a parameter, do so.
3605 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3606 whether the function should care about type incompatibility the current and
3607 new expressions. If it is true, the function will leave incompatibility
3608 issues to the caller.
3610 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3611 a write (LHS) expression. */
3614 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3615 bool dont_convert, void *data)
3617 ipa_parm_adjustment_vec adjustments;
3619 struct ipa_parm_adjustment *adj, *cand = NULL;
3620 HOST_WIDE_INT offset, size, max_size;
3623 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3624 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3626 if (TREE_CODE (*expr) == BIT_FIELD_REF
3627 || TREE_CODE (*expr) == IMAGPART_EXPR
3628 || TREE_CODE (*expr) == REALPART_EXPR)
3630 expr = &TREE_OPERAND (*expr, 0);
3631 dont_convert = false;
3634 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3635 if (!base || size == -1 || max_size == -1)
3638 if (INDIRECT_REF_P (base))
3639 base = TREE_OPERAND (base, 0);
3641 base = get_ssa_base_param (base);
3642 if (!base || TREE_CODE (base) != PARM_DECL)
3645 for (i = 0; i < len; i++)
3647 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3649 if (adj->base == base &&
3650 (adj->offset == offset || adj->remove_param))
3656 if (!cand || cand->copy_param || cand->remove_param)
3662 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3664 folded = gimple_fold_indirect_ref (src);
3669 src = cand->reduction;
3671 if (dump_file && (dump_flags & TDF_DETAILS))
3673 fprintf (dump_file, "About to replace expr ");
3674 print_generic_expr (dump_file, *expr, 0);
3675 fprintf (dump_file, " with ");
3676 print_generic_expr (dump_file, src, 0);
3677 fprintf (dump_file, "\n");
3681 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3683 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3691 /* Callback for scan_function to process assign statements. Performs
3692 essentially the same function like sra_ipa_modify_expr. */
3694 static enum scan_assign_result
3695 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3697 gimple stmt = *stmt_ptr;
3698 tree *lhs_p, *rhs_p;
3701 if (!gimple_assign_single_p (stmt))
3704 rhs_p = gimple_assign_rhs1_ptr (stmt);
3705 lhs_p = gimple_assign_lhs_ptr (stmt);
3707 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3708 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3711 tree new_rhs = NULL_TREE;
3713 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3714 new_rhs = fold_build1_loc (gimple_location (stmt), VIEW_CONVERT_EXPR,
3715 TREE_TYPE (*lhs_p), *rhs_p);
3716 else if (REFERENCE_CLASS_P (*rhs_p)
3717 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3718 && !is_gimple_reg (*lhs_p))
3719 /* This can happen when an assignment in between two single field
3720 structures is turned into an assignment in between two pointers to
3721 scalars (PR 42237). */
3726 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3727 true, GSI_SAME_STMT);
3729 gimple_assign_set_rhs_from_tree (gsi, tmp);
3732 return SRA_SA_PROCESSED;
3738 /* Call gimple_debug_bind_reset_value on all debug statements describing
3739 gimple register parameters that are being removed or replaced. */
3742 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3746 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3747 for (i = 0; i < len; i++)
3749 struct ipa_parm_adjustment *adj;
3750 imm_use_iterator ui;
3754 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3755 if (adj->copy_param || !is_gimple_reg (adj->base))
3757 name = gimple_default_def (cfun, adj->base);
3760 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3762 /* All other users must have been removed by scan_function. */
3763 gcc_assert (is_gimple_debug (stmt));
3764 gimple_debug_bind_reset_value (stmt);
3770 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3773 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3775 tree old_cur_fndecl = current_function_decl;
3776 struct cgraph_edge *cs;
3777 basic_block this_block;
3778 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3780 for (cs = node->callers; cs; cs = cs->next_caller)
3782 current_function_decl = cs->caller->decl;
3783 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3786 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3787 cs->caller->uid, cs->callee->uid,
3788 cgraph_node_name (cs->caller),
3789 cgraph_node_name (cs->callee));
3791 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3796 for (cs = node->callers; cs; cs = cs->next_caller)
3797 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3799 compute_inline_parameters (cs->caller);
3800 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3802 BITMAP_FREE (recomputed_callers);
3804 current_function_decl = old_cur_fndecl;
3805 FOR_EACH_BB (this_block)
3807 gimple_stmt_iterator gsi;
3809 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3811 gimple stmt = gsi_stmt (gsi);
3812 if (gimple_code (stmt) == GIMPLE_CALL
3813 && gimple_call_fndecl (stmt) == node->decl)
3816 fprintf (dump_file, "Adjusting recursive call");
3817 ipa_modify_call_arguments (NULL, stmt, adjustments);
3825 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3826 as given in ADJUSTMENTS. */
3829 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3831 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3832 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3833 replace_removed_params_ssa_names, false, adjustments);
3834 sra_ipa_reset_debug_stmts (adjustments);
3835 convert_callers (node, adjustments);
3836 cgraph_make_node_local (node);
3840 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3841 attributes, return true otherwise. NODE is the cgraph node of the current
3845 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3847 if (!cgraph_node_can_be_local_p (node))
3850 fprintf (dump_file, "Function not local to this compilation unit.\n");
3854 if (DECL_VIRTUAL_P (current_function_decl))
3857 fprintf (dump_file, "Function is a virtual method.\n");
3861 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3862 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3865 fprintf (dump_file, "Function too big to be made truly local.\n");
3873 "Function has no callers in this compilation unit.\n");
3880 fprintf (dump_file, "Function uses stdarg. \n");
3887 /* Perform early interprocedural SRA. */
3890 ipa_early_sra (void)
3892 struct cgraph_node *node = cgraph_node (current_function_decl);
3893 ipa_parm_adjustment_vec adjustments;
3896 if (!ipa_sra_preliminary_function_checks (node))
3900 sra_mode = SRA_MODE_EARLY_IPA;
3902 if (!find_param_candidates ())
3905 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3909 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3911 * last_basic_block_for_function (cfun));
3912 final_bbs = BITMAP_ALLOC (NULL);
3914 scan_function (build_access_from_expr, build_accesses_from_assign,
3916 if (encountered_apply_args)
3919 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3923 adjustments = analyze_all_param_acesses ();
3927 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3929 modify_function (node, adjustments);
3930 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3931 ret = TODO_update_ssa;
3933 statistics_counter_event (cfun, "Unused parameters deleted",
3934 sra_stats.deleted_unused_parameters);
3935 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3936 sra_stats.scalar_by_ref_to_by_val);
3937 statistics_counter_event (cfun, "Aggregate parameters broken up",
3938 sra_stats.aggregate_params_reduced);
3939 statistics_counter_event (cfun, "Aggregate parameter components created",
3940 sra_stats.param_reductions_created);
3943 BITMAP_FREE (final_bbs);
3944 free (bb_dereferences);
3946 sra_deinitialize ();
3950 /* Return if early ipa sra shall be performed. */
3952 ipa_early_sra_gate (void)
3954 return flag_ipa_sra;
3957 struct gimple_opt_pass pass_early_ipa_sra =
3961 "eipa_sra", /* name */
3962 ipa_early_sra_gate, /* gate */
3963 ipa_early_sra, /* execute */
3966 0, /* static_pass_number */
3967 TV_IPA_SRA, /* tv_id */
3968 0, /* properties_required */
3969 0, /* properties_provided */
3970 0, /* properties_destroyed */
3971 0, /* todo_flags_start */
3972 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */