1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
82 #include "tree-flow.h"
84 #include "diagnostic.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 /* Enumeration of all aggregate reductions we can do. */
93 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
94 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
95 SRA_MODE_INTRA }; /* late intraprocedural SRA */
97 /* Global variable describing which aggregate reduction we are performing at
99 static enum sra_mode sra_mode;
103 /* ACCESS represents each access to an aggregate variable (as a whole or a
104 part). It can also represent a group of accesses that refer to exactly the
105 same fragment of an aggregate (i.e. those that have exactly the same offset
106 and size). Such representatives for a single aggregate, once determined,
107 are linked in a linked list and have the group fields set.
109 Moreover, when doing intraprocedural SRA, a tree is built from those
110 representatives (by the means of first_child and next_sibling pointers), in
111 which all items in a subtree are "within" the root, i.e. their offset is
112 greater or equal to offset of the root and offset+size is smaller or equal
113 to offset+size of the root. Children of an access are sorted by offset.
115 Note that accesses to parts of vector and complex number types always
116 represented by an access to the whole complex number or a vector. It is a
117 duty of the modifying functions to replace them appropriately. */
121 /* Values returned by `get_ref_base_and_extent' for each component reference
122 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
123 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
124 HOST_WIDE_INT offset;
128 /* Expression. It is context dependent so do not use it to create new
129 expressions to access the original aggregate. See PR 42154 for a
135 /* The statement this access belongs to. */
138 /* Next group representative for this aggregate. */
139 struct access *next_grp;
141 /* Pointer to the group representative. Pointer to itself if the struct is
142 the representative. */
143 struct access *group_representative;
145 /* If this access has any children (in terms of the definition above), this
146 points to the first one. */
147 struct access *first_child;
149 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
150 described above. In IPA-SRA this is a pointer to the next access
151 belonging to the same group (having the same representative). */
152 struct access *next_sibling;
154 /* Pointers to the first and last element in the linked list of assign
156 struct assign_link *first_link, *last_link;
158 /* Pointer to the next access in the work queue. */
159 struct access *next_queued;
161 /* Replacement variable for this access "region." Never to be accessed
162 directly, always only by the means of get_access_replacement() and only
163 when grp_to_be_replaced flag is set. */
164 tree replacement_decl;
166 /* Is this particular access write access? */
169 /* Is this access currently in the work queue? */
170 unsigned grp_queued : 1;
172 /* Does this group contain a write access? This flag is propagated down the
174 unsigned grp_write : 1;
176 /* Does this group contain a read access? This flag is propagated down the
178 unsigned grp_read : 1;
180 /* Other passes of the analysis use this bit to make function
181 analyze_access_subtree create scalar replacements for this group if
183 unsigned grp_hint : 1;
185 /* Is the subtree rooted in this access fully covered by scalar
187 unsigned grp_covered : 1;
189 /* If set to true, this access and all below it in an access tree must not be
191 unsigned grp_unscalarizable_region : 1;
193 /* Whether data have been written to parts of the aggregate covered by this
194 access which is not to be scalarized. This flag is propagated up in the
196 unsigned grp_unscalarized_data : 1;
198 /* Does this access and/or group contain a write access through a
200 unsigned grp_partial_lhs : 1;
202 /* Set when a scalar replacement should be created for this variable. We do
203 the decision and creation at different places because create_tmp_var
204 cannot be called from within FOR_EACH_REFERENCED_VAR. */
205 unsigned grp_to_be_replaced : 1;
207 /* Is it possible that the group refers to data which might be (directly or
208 otherwise) modified? */
209 unsigned grp_maybe_modified : 1;
211 /* Set when this is a representative of a pointer to scalar (i.e. by
212 reference) parameter which we consider for turning into a plain scalar
213 (i.e. a by value parameter). */
214 unsigned grp_scalar_ptr : 1;
216 /* Set when we discover that this pointer is not safe to dereference in the
218 unsigned grp_not_necessarilly_dereferenced : 1;
221 typedef struct access *access_p;
223 DEF_VEC_P (access_p);
224 DEF_VEC_ALLOC_P (access_p, heap);
226 /* Alloc pool for allocating access structures. */
227 static alloc_pool access_pool;
229 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
230 are used to propagate subaccesses from rhs to lhs as long as they don't
231 conflict with what is already there. */
234 struct access *lacc, *racc;
235 struct assign_link *next;
238 /* Alloc pool for allocating assign link structures. */
239 static alloc_pool link_pool;
241 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
242 static struct pointer_map_t *base_access_vec;
244 /* Bitmap of candidates. */
245 static bitmap candidate_bitmap;
247 /* Obstack for creation of fancy names. */
248 static struct obstack name_obstack;
250 /* Head of a linked list of accesses that need to have its subaccesses
251 propagated to their assignment counterparts. */
252 static struct access *work_queue_head;
254 /* Number of parameters of the analyzed function when doing early ipa SRA. */
255 static int func_param_count;
257 /* scan_function sets the following to true if it encounters a call to
258 __builtin_apply_args. */
259 static bool encountered_apply_args;
261 /* This is a table in which for each basic block and parameter there is a
262 distance (offset + size) in that parameter which is dereferenced and
263 accessed in that BB. */
264 static HOST_WIDE_INT *bb_dereferences;
265 /* Bitmap of BBs that can cause the function to "stop" progressing by
266 returning, throwing externally, looping infinitely or calling a function
267 which might abort etc.. */
268 static bitmap final_bbs;
270 /* Representative of no accesses at all. */
271 static struct access no_accesses_representant;
273 /* Predicate to test the special value. */
276 no_accesses_p (struct access *access)
278 return access == &no_accesses_representant;
281 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
282 representative fields are dumped, otherwise those which only describe the
283 individual access are. */
287 /* Number of processed aggregates is readily available in
288 analyze_all_variable_accesses and so is not stored here. */
290 /* Number of created scalar replacements. */
293 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
297 /* Number of statements created by generate_subtree_copies. */
300 /* Number of statements created by load_assign_lhs_subreplacements. */
303 /* Number of times sra_modify_assign has deleted a statement. */
306 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
307 RHS reparately due to type conversions or nonexistent matching
309 int separate_lhs_rhs_handling;
311 /* Number of parameters that were removed because they were unused. */
312 int deleted_unused_parameters;
314 /* Number of scalars passed as parameters by reference that have been
315 converted to be passed by value. */
316 int scalar_by_ref_to_by_val;
318 /* Number of aggregate parameters that were replaced by one or more of their
320 int aggregate_params_reduced;
322 /* Numbber of components created when splitting aggregate parameters. */
323 int param_reductions_created;
327 dump_access (FILE *f, struct access *access, bool grp)
329 fprintf (f, "access { ");
330 fprintf (f, "base = (%d)'", DECL_UID (access->base));
331 print_generic_expr (f, access->base, 0);
332 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
333 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
334 fprintf (f, ", expr = ");
335 print_generic_expr (f, access->expr, 0);
336 fprintf (f, ", type = ");
337 print_generic_expr (f, access->type, 0);
339 fprintf (f, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
340 "grp_covered = %d, grp_unscalarizable_region = %d, "
341 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
342 "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
343 "grp_not_necessarilly_dereferenced = %d\n",
344 access->grp_write, access->grp_read, access->grp_hint,
345 access->grp_covered, access->grp_unscalarizable_region,
346 access->grp_unscalarized_data, access->grp_partial_lhs,
347 access->grp_to_be_replaced, access->grp_maybe_modified,
348 access->grp_not_necessarilly_dereferenced);
350 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
351 access->grp_partial_lhs);
354 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
357 dump_access_tree_1 (FILE *f, struct access *access, int level)
363 for (i = 0; i < level; i++)
364 fputs ("* ", dump_file);
366 dump_access (f, access, true);
368 if (access->first_child)
369 dump_access_tree_1 (f, access->first_child, level + 1);
371 access = access->next_sibling;
376 /* Dump all access trees for a variable, given the pointer to the first root in
380 dump_access_tree (FILE *f, struct access *access)
382 for (; access; access = access->next_grp)
383 dump_access_tree_1 (f, access, 0);
386 /* Return true iff ACC is non-NULL and has subaccesses. */
389 access_has_children_p (struct access *acc)
391 return acc && acc->first_child;
394 /* Return a vector of pointers to accesses for the variable given in BASE or
395 NULL if there is none. */
397 static VEC (access_p, heap) *
398 get_base_access_vector (tree base)
402 slot = pointer_map_contains (base_access_vec, base);
406 return *(VEC (access_p, heap) **) slot;
409 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
410 in ACCESS. Return NULL if it cannot be found. */
412 static struct access *
413 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
416 while (access && (access->offset != offset || access->size != size))
418 struct access *child = access->first_child;
420 while (child && (child->offset + child->size <= offset))
421 child = child->next_sibling;
428 /* Return the first group representative for DECL or NULL if none exists. */
430 static struct access *
431 get_first_repr_for_decl (tree base)
433 VEC (access_p, heap) *access_vec;
435 access_vec = get_base_access_vector (base);
439 return VEC_index (access_p, access_vec, 0);
442 /* Find an access representative for the variable BASE and given OFFSET and
443 SIZE. Requires that access trees have already been built. Return NULL if
444 it cannot be found. */
446 static struct access *
447 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
450 struct access *access;
452 access = get_first_repr_for_decl (base);
453 while (access && (access->offset + access->size <= offset))
454 access = access->next_grp;
458 return find_access_in_subtree (access, offset, size);
461 /* Add LINK to the linked list of assign links of RACC. */
463 add_link_to_rhs (struct access *racc, struct assign_link *link)
465 gcc_assert (link->racc == racc);
467 if (!racc->first_link)
469 gcc_assert (!racc->last_link);
470 racc->first_link = link;
473 racc->last_link->next = link;
475 racc->last_link = link;
479 /* Move all link structures in their linked list in OLD_RACC to the linked list
482 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
484 if (!old_racc->first_link)
486 gcc_assert (!old_racc->last_link);
490 if (new_racc->first_link)
492 gcc_assert (!new_racc->last_link->next);
493 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
495 new_racc->last_link->next = old_racc->first_link;
496 new_racc->last_link = old_racc->last_link;
500 gcc_assert (!new_racc->last_link);
502 new_racc->first_link = old_racc->first_link;
503 new_racc->last_link = old_racc->last_link;
505 old_racc->first_link = old_racc->last_link = NULL;
508 /* Add ACCESS to the work queue (which is actually a stack). */
511 add_access_to_work_queue (struct access *access)
513 if (!access->grp_queued)
515 gcc_assert (!access->next_queued);
516 access->next_queued = work_queue_head;
517 access->grp_queued = 1;
518 work_queue_head = access;
522 /* Pop an access from the work queue, and return it, assuming there is one. */
524 static struct access *
525 pop_access_from_work_queue (void)
527 struct access *access = work_queue_head;
529 work_queue_head = access->next_queued;
530 access->next_queued = NULL;
531 access->grp_queued = 0;
536 /* Allocate necessary structures. */
539 sra_initialize (void)
541 candidate_bitmap = BITMAP_ALLOC (NULL);
542 gcc_obstack_init (&name_obstack);
543 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
544 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
545 base_access_vec = pointer_map_create ();
546 memset (&sra_stats, 0, sizeof (sra_stats));
547 encountered_apply_args = false;
550 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
553 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
554 void *data ATTRIBUTE_UNUSED)
556 VEC (access_p, heap) *access_vec;
557 access_vec = (VEC (access_p, heap) *) *value;
558 VEC_free (access_p, heap, access_vec);
563 /* Deallocate all general structures. */
566 sra_deinitialize (void)
568 BITMAP_FREE (candidate_bitmap);
569 free_alloc_pool (access_pool);
570 free_alloc_pool (link_pool);
571 obstack_free (&name_obstack, NULL);
573 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
574 pointer_map_destroy (base_access_vec);
577 /* Remove DECL from candidates for SRA and write REASON to the dump file if
580 disqualify_candidate (tree decl, const char *reason)
582 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
584 if (dump_file && (dump_flags & TDF_DETAILS))
586 fprintf (dump_file, "! Disqualifying ");
587 print_generic_expr (dump_file, decl, 0);
588 fprintf (dump_file, " - %s\n", reason);
592 /* Return true iff the type contains a field or an element which does not allow
596 type_internals_preclude_sra_p (tree type)
601 switch (TREE_CODE (type))
605 case QUAL_UNION_TYPE:
606 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
607 if (TREE_CODE (fld) == FIELD_DECL)
609 tree ft = TREE_TYPE (fld);
611 if (TREE_THIS_VOLATILE (fld)
612 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
613 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
614 || !host_integerp (DECL_SIZE (fld), 1))
617 if (AGGREGATE_TYPE_P (ft)
618 && type_internals_preclude_sra_p (ft))
625 et = TREE_TYPE (type);
627 if (AGGREGATE_TYPE_P (et))
628 return type_internals_preclude_sra_p (et);
637 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
638 base variable if it is. Return T if it is not an SSA_NAME. */
641 get_ssa_base_param (tree t)
643 if (TREE_CODE (t) == SSA_NAME)
645 if (SSA_NAME_IS_DEFAULT_DEF (t))
646 return SSA_NAME_VAR (t);
653 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
654 belongs to, unless the BB has already been marked as a potentially
658 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
660 basic_block bb = gimple_bb (stmt);
661 int idx, parm_index = 0;
664 if (bitmap_bit_p (final_bbs, bb->index))
667 for (parm = DECL_ARGUMENTS (current_function_decl);
668 parm && parm != base;
669 parm = TREE_CHAIN (parm))
672 gcc_assert (parm_index < func_param_count);
674 idx = bb->index * func_param_count + parm_index;
675 if (bb_dereferences[idx] < dist)
676 bb_dereferences[idx] = dist;
679 /* Create and insert access for EXPR. Return created access, or NULL if it is
682 static struct access *
683 create_access (tree expr, gimple stmt, bool write)
685 struct access *access;
687 VEC (access_p,heap) *vec;
688 HOST_WIDE_INT offset, size, max_size;
690 bool ptr, unscalarizable_region = false;
692 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
694 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
696 base = get_ssa_base_param (TREE_OPERAND (base, 0));
704 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
707 if (sra_mode == SRA_MODE_EARLY_IPA)
709 if (size < 0 || size != max_size)
711 disqualify_candidate (base, "Encountered a variable sized access.");
714 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
716 disqualify_candidate (base,
717 "Encountered an acces not aligned to a byte.");
722 mark_parm_dereference (base, offset + size, stmt);
726 if (size != max_size)
729 unscalarizable_region = true;
733 disqualify_candidate (base, "Encountered an unconstrained access.");
738 access = (struct access *) pool_alloc (access_pool);
739 memset (access, 0, sizeof (struct access));
742 access->offset = offset;
745 access->type = TREE_TYPE (expr);
746 access->write = write;
747 access->grp_unscalarizable_region = unscalarizable_region;
750 slot = pointer_map_contains (base_access_vec, base);
752 vec = (VEC (access_p, heap) *) *slot;
754 vec = VEC_alloc (access_p, heap, 32);
756 VEC_safe_push (access_p, heap, vec, access);
758 *((struct VEC (access_p,heap) **)
759 pointer_map_insert (base_access_vec, base)) = vec;
765 /* Search the given tree for a declaration by skipping handled components and
766 exclude it from the candidates. */
769 disqualify_base_of_expr (tree t, const char *reason)
771 while (handled_component_p (t))
772 t = TREE_OPERAND (t, 0);
774 if (sra_mode == SRA_MODE_EARLY_IPA)
776 if (INDIRECT_REF_P (t))
777 t = TREE_OPERAND (t, 0);
778 t = get_ssa_base_param (t);
782 disqualify_candidate (t, reason);
785 /* Scan expression EXPR and create access structures for all accesses to
786 candidates for scalarization. Return the created access or NULL if none is
789 static struct access *
790 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
792 struct access *ret = NULL;
793 tree expr = *expr_ptr;
796 if (TREE_CODE (expr) == BIT_FIELD_REF
797 || TREE_CODE (expr) == IMAGPART_EXPR
798 || TREE_CODE (expr) == REALPART_EXPR)
800 expr = TREE_OPERAND (expr, 0);
806 /* We need to dive through V_C_Es in order to get the size of its parameter
807 and not the result type. Ada produces such statements. We are also
808 capable of handling the topmost V_C_E but not any of those buried in other
809 handled components. */
810 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
811 expr = TREE_OPERAND (expr, 0);
813 if (contains_view_convert_expr_p (expr))
815 disqualify_base_of_expr (expr, "V_C_E under a different handled "
820 switch (TREE_CODE (expr))
823 if (sra_mode != SRA_MODE_EARLY_IPA)
831 case ARRAY_RANGE_REF:
832 ret = create_access (expr, stmt, write);
839 if (write && partial_ref && ret)
840 ret->grp_partial_lhs = 1;
845 /* Callback of scan_function. Scan expression EXPR and create access
846 structures for all accesses to candidates for scalarization. Return true if
847 any access has been inserted. */
850 build_access_from_expr (tree *expr_ptr,
851 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
852 void *data ATTRIBUTE_UNUSED)
854 return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
857 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
858 modes in which it matters, return true iff they have been disqualified. RHS
859 may be NULL, in that case ignore it. If we scalarize an aggregate in
860 intra-SRA we may need to add statements after each statement. This is not
861 possible if a statement unconditionally has to end the basic block. */
863 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
865 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
866 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
868 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
870 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
877 /* Result code for scan_assign callback for scan_function. */
878 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
879 SRA_SA_PROCESSED, /* stmt analyzed/changed */
880 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
883 /* Callback of scan_function. Scan expressions occuring in the statement
884 pointed to by STMT_EXPR, create access structures for all accesses to
885 candidates for scalarization and remove those candidates which occur in
886 statements or expressions that prevent them from being split apart. Return
887 true if any access has been inserted. */
889 static enum scan_assign_result
890 build_accesses_from_assign (gimple *stmt_ptr,
891 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
892 void *data ATTRIBUTE_UNUSED)
894 gimple stmt = *stmt_ptr;
895 tree *lhs_ptr, *rhs_ptr;
896 struct access *lacc, *racc;
898 if (!gimple_assign_single_p (stmt))
901 lhs_ptr = gimple_assign_lhs_ptr (stmt);
902 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
904 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
907 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
908 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
911 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
912 && !lacc->grp_unscalarizable_region
913 && !racc->grp_unscalarizable_region
914 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
915 /* FIXME: Turn the following line into an assert after PR 40058 is
917 && lacc->size == racc->size
918 && useless_type_conversion_p (lacc->type, racc->type))
920 struct assign_link *link;
922 link = (struct assign_link *) pool_alloc (link_pool);
923 memset (link, 0, sizeof (struct assign_link));
928 add_link_to_rhs (racc, link);
931 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
934 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
935 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
938 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
939 void *data ATTRIBUTE_UNUSED)
942 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
948 /* Scan function and look for interesting statements. Return true if any has
949 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
950 called on all expressions within statements except assign statements and
951 those deemed entirely unsuitable for some reason (all operands in such
952 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
953 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
954 called on assign statements and those call statements which have a lhs, it
955 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
956 pass and thus no statement is being modified. DATA is a pointer passed to
957 all callbacks. If any single callback returns true, this function also
958 returns true, otherwise it returns false. */
961 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
962 enum scan_assign_result (*scan_assign) (gimple *,
963 gimple_stmt_iterator *,
965 bool (*handle_ssa_defs)(gimple, void *),
966 bool analysis_stage, void *data)
968 gimple_stmt_iterator gsi;
976 bool bb_changed = false;
979 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
980 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
982 gsi = gsi_start_bb (bb);
983 while (!gsi_end_p (gsi))
985 gimple stmt = gsi_stmt (gsi);
986 enum scan_assign_result assign_result;
987 bool any = false, deleted = false;
989 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
990 bitmap_set_bit (final_bbs, bb->index);
991 switch (gimple_code (stmt))
994 t = gimple_return_retval_ptr (stmt);
996 any |= scan_expr (t, &gsi, false, data);
997 if (analysis_stage && final_bbs)
998 bitmap_set_bit (final_bbs, bb->index);
1002 assign_result = scan_assign (&stmt, &gsi, data);
1003 any |= assign_result == SRA_SA_PROCESSED;
1004 deleted = assign_result == SRA_SA_REMOVED;
1005 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1006 any |= handle_ssa_defs (stmt, data);
1010 /* Operands must be processed before the lhs. */
1011 for (i = 0; i < gimple_call_num_args (stmt); i++)
1013 tree *argp = gimple_call_arg_ptr (stmt, i);
1014 any |= scan_expr (argp, &gsi, false, data);
1019 tree dest = gimple_call_fndecl (stmt);
1020 int flags = gimple_call_flags (stmt);
1023 && DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1024 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1025 encountered_apply_args = true;
1028 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1029 bitmap_set_bit (final_bbs, bb->index);
1032 if (gimple_call_lhs (stmt))
1034 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1036 || !disqualify_ops_if_throwing_stmt (stmt,
1039 any |= scan_expr (lhs_ptr, &gsi, true, data);
1040 if (handle_ssa_defs)
1041 any |= handle_ssa_defs (stmt, data);
1049 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1052 bitmap_set_bit (final_bbs, bb->index);
1054 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1056 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1057 any |= scan_expr (op, &gsi, false, data);
1059 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1061 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1062 any |= scan_expr (op, &gsi, true, data);
1074 if (!analysis_stage)
1078 maybe_clean_eh_stmt (stmt);
1089 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1090 gimple_purge_dead_eh_edges (bb);
1096 /* Helper of QSORT function. There are pointers to accesses in the array. An
1097 access is considered smaller than another if it has smaller offset or if the
1098 offsets are the same but is size is bigger. */
1101 compare_access_positions (const void *a, const void *b)
1103 const access_p *fp1 = (const access_p *) a;
1104 const access_p *fp2 = (const access_p *) b;
1105 const access_p f1 = *fp1;
1106 const access_p f2 = *fp2;
1108 if (f1->offset != f2->offset)
1109 return f1->offset < f2->offset ? -1 : 1;
1111 if (f1->size == f2->size)
1113 /* Put any non-aggregate type before any aggregate type. */
1114 if (!is_gimple_reg_type (f1->type)
1115 && is_gimple_reg_type (f2->type))
1117 else if (is_gimple_reg_type (f1->type)
1118 && !is_gimple_reg_type (f2->type))
1120 /* Put any complex or vector type before any other scalar type. */
1121 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1122 && TREE_CODE (f1->type) != VECTOR_TYPE
1123 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1124 || TREE_CODE (f2->type) == VECTOR_TYPE))
1126 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1127 || TREE_CODE (f1->type) == VECTOR_TYPE)
1128 && TREE_CODE (f2->type) != COMPLEX_TYPE
1129 && TREE_CODE (f2->type) != VECTOR_TYPE)
1131 /* Put the integral type with the bigger precision first. */
1132 else if (INTEGRAL_TYPE_P (f1->type)
1133 && INTEGRAL_TYPE_P (f2->type))
1134 return TYPE_PRECISION (f1->type) > TYPE_PRECISION (f2->type) ? -1 : 1;
1135 /* Put any integral type with non-full precision last. */
1136 else if (INTEGRAL_TYPE_P (f1->type)
1137 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1138 != TYPE_PRECISION (f1->type)))
1140 else if (INTEGRAL_TYPE_P (f2->type)
1141 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1142 != TYPE_PRECISION (f2->type)))
1144 /* Stabilize the sort. */
1145 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1148 /* We want the bigger accesses first, thus the opposite operator in the next
1150 return f1->size > f2->size ? -1 : 1;
1154 /* Append a name of the declaration to the name obstack. A helper function for
1158 make_fancy_decl_name (tree decl)
1162 tree name = DECL_NAME (decl);
1164 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1165 IDENTIFIER_LENGTH (name));
1168 sprintf (buffer, "D%u", DECL_UID (decl));
1169 obstack_grow (&name_obstack, buffer, strlen (buffer));
1173 /* Helper for make_fancy_name. */
1176 make_fancy_name_1 (tree expr)
1183 make_fancy_decl_name (expr);
1187 switch (TREE_CODE (expr))
1190 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1191 obstack_1grow (&name_obstack, '$');
1192 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1196 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1197 obstack_1grow (&name_obstack, '$');
1198 /* Arrays with only one element may not have a constant as their
1200 index = TREE_OPERAND (expr, 1);
1201 if (TREE_CODE (index) != INTEGER_CST)
1203 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1204 obstack_grow (&name_obstack, buffer, strlen (buffer));
1211 gcc_unreachable (); /* we treat these as scalars. */
1218 /* Create a human readable name for replacement variable of ACCESS. */
1221 make_fancy_name (tree expr)
1223 make_fancy_name_1 (expr);
1224 obstack_1grow (&name_obstack, '\0');
1225 return XOBFINISH (&name_obstack, char *);
1228 /* Helper function for build_ref_for_offset. */
1231 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1237 tree tr_size, index, minidx;
1238 HOST_WIDE_INT el_size;
1240 if (offset == 0 && exp_type
1241 && types_compatible_p (exp_type, type))
1244 switch (TREE_CODE (type))
1247 case QUAL_UNION_TYPE:
1249 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1251 HOST_WIDE_INT pos, size;
1252 tree expr, *expr_ptr;
1254 if (TREE_CODE (fld) != FIELD_DECL)
1257 pos = int_bit_position (fld);
1258 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1259 tr_size = DECL_SIZE (fld);
1260 if (!tr_size || !host_integerp (tr_size, 1))
1262 size = tree_low_cst (tr_size, 1);
1263 if (pos > offset || (pos + size) <= offset)
1268 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1274 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1275 offset - pos, exp_type))
1285 tr_size = TYPE_SIZE (TREE_TYPE (type));
1286 if (!tr_size || !host_integerp (tr_size, 1))
1288 el_size = tree_low_cst (tr_size, 1);
1290 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1291 if (TREE_CODE (minidx) != INTEGER_CST)
1295 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1296 if (!integer_zerop (minidx))
1297 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1298 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1299 NULL_TREE, NULL_TREE);
1301 offset = offset % el_size;
1302 type = TREE_TYPE (type);
1317 /* Construct an expression that would reference a part of aggregate *EXPR of
1318 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1319 function only determines whether it can build such a reference without
1320 actually doing it, otherwise, the tree it points to is unshared first and
1321 then used as a base for furhter sub-references.
1323 FIXME: Eventually this should be replaced with
1324 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1325 minor rewrite of fold_stmt.
1329 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1330 tree exp_type, bool allow_ptr)
1332 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1335 *expr = unshare_expr (*expr);
1337 if (allow_ptr && POINTER_TYPE_P (type))
1339 type = TREE_TYPE (type);
1341 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1344 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1347 /* Return true iff TYPE is stdarg va_list type. */
1350 is_va_list_type (tree type)
1352 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1355 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1356 those with type which is suitable for scalarization. */
1359 find_var_candidates (void)
1362 referenced_var_iterator rvi;
1365 FOR_EACH_REFERENCED_VAR (var, rvi)
1367 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1369 type = TREE_TYPE (var);
1371 if (!AGGREGATE_TYPE_P (type)
1372 || needs_to_live_in_memory (var)
1373 || TREE_THIS_VOLATILE (var)
1374 || !COMPLETE_TYPE_P (type)
1375 || !host_integerp (TYPE_SIZE (type), 1)
1376 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1377 || type_internals_preclude_sra_p (type)
1378 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1379 we also want to schedule it rather late. Thus we ignore it in
1381 || (sra_mode == SRA_MODE_EARLY_INTRA
1382 && is_va_list_type (type)))
1385 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1387 if (dump_file && (dump_flags & TDF_DETAILS))
1389 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1390 print_generic_expr (dump_file, var, 0);
1391 fprintf (dump_file, "\n");
1399 /* Sort all accesses for the given variable, check for partial overlaps and
1400 return NULL if there are any. If there are none, pick a representative for
1401 each combination of offset and size and create a linked list out of them.
1402 Return the pointer to the first representative and make sure it is the first
1403 one in the vector of accesses. */
1405 static struct access *
1406 sort_and_splice_var_accesses (tree var)
1408 int i, j, access_count;
1409 struct access *res, **prev_acc_ptr = &res;
1410 VEC (access_p, heap) *access_vec;
1412 HOST_WIDE_INT low = -1, high = 0;
1414 access_vec = get_base_access_vector (var);
1417 access_count = VEC_length (access_p, access_vec);
1419 /* Sort by <OFFSET, SIZE>. */
1420 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1421 compare_access_positions);
1424 while (i < access_count)
1426 struct access *access = VEC_index (access_p, access_vec, i);
1427 bool grp_write = access->write;
1428 bool grp_read = !access->write;
1429 bool multiple_reads = false;
1430 bool grp_partial_lhs = access->grp_partial_lhs;
1431 bool first_scalar = is_gimple_reg_type (access->type);
1432 bool unscalarizable_region = access->grp_unscalarizable_region;
1434 if (first || access->offset >= high)
1437 low = access->offset;
1438 high = access->offset + access->size;
1440 else if (access->offset > low && access->offset + access->size > high)
1443 gcc_assert (access->offset >= low
1444 && access->offset + access->size <= high);
1447 while (j < access_count)
1449 struct access *ac2 = VEC_index (access_p, access_vec, j);
1450 if (ac2->offset != access->offset || ac2->size != access->size)
1457 multiple_reads = true;
1461 grp_partial_lhs |= ac2->grp_partial_lhs;
1462 unscalarizable_region |= ac2->grp_unscalarizable_region;
1463 relink_to_new_repr (access, ac2);
1465 /* If there are both aggregate-type and scalar-type accesses with
1466 this combination of size and offset, the comparison function
1467 should have put the scalars first. */
1468 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1469 ac2->group_representative = access;
1475 access->group_representative = access;
1476 access->grp_write = grp_write;
1477 access->grp_read = grp_read;
1478 access->grp_hint = multiple_reads;
1479 access->grp_partial_lhs = grp_partial_lhs;
1480 access->grp_unscalarizable_region = unscalarizable_region;
1481 if (access->first_link)
1482 add_access_to_work_queue (access);
1484 *prev_acc_ptr = access;
1485 prev_acc_ptr = &access->next_grp;
1488 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1492 /* Create a variable for the given ACCESS which determines the type, name and a
1493 few other properties. Return the variable declaration and store it also to
1494 ACCESS->replacement. */
1497 create_access_replacement (struct access *access)
1501 repl = create_tmp_var (access->type, "SR");
1503 add_referenced_var (repl);
1504 mark_sym_for_renaming (repl);
1506 if (!access->grp_partial_lhs
1507 && (TREE_CODE (access->type) == COMPLEX_TYPE
1508 || TREE_CODE (access->type) == VECTOR_TYPE))
1509 DECL_GIMPLE_REG_P (repl) = 1;
1511 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1512 DECL_ARTIFICIAL (repl) = 1;
1514 if (DECL_NAME (access->base)
1515 && !DECL_IGNORED_P (access->base)
1516 && !DECL_ARTIFICIAL (access->base))
1518 char *pretty_name = make_fancy_name (access->expr);
1520 DECL_NAME (repl) = get_identifier (pretty_name);
1521 obstack_free (&name_obstack, pretty_name);
1523 SET_DECL_DEBUG_EXPR (repl, access->expr);
1524 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1525 DECL_IGNORED_P (repl) = 0;
1528 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1529 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1533 fprintf (dump_file, "Created a replacement for ");
1534 print_generic_expr (dump_file, access->base, 0);
1535 fprintf (dump_file, " offset: %u, size: %u: ",
1536 (unsigned) access->offset, (unsigned) access->size);
1537 print_generic_expr (dump_file, repl, 0);
1538 fprintf (dump_file, "\n");
1540 sra_stats.replacements++;
1545 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1548 get_access_replacement (struct access *access)
1550 gcc_assert (access->grp_to_be_replaced);
1552 if (!access->replacement_decl)
1553 access->replacement_decl = create_access_replacement (access);
1554 return access->replacement_decl;
1557 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1558 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1559 to it is not "within" the root. */
1562 build_access_subtree (struct access **access)
1564 struct access *root = *access, *last_child = NULL;
1565 HOST_WIDE_INT limit = root->offset + root->size;
1567 *access = (*access)->next_grp;
1568 while (*access && (*access)->offset + (*access)->size <= limit)
1571 root->first_child = *access;
1573 last_child->next_sibling = *access;
1574 last_child = *access;
1576 build_access_subtree (access);
1580 /* Build a tree of access representatives, ACCESS is the pointer to the first
1581 one, others are linked in a list by the next_grp field. Decide about scalar
1582 replacements on the way, return true iff any are to be created. */
1585 build_access_trees (struct access *access)
1589 struct access *root = access;
1591 build_access_subtree (&access);
1592 root->next_grp = access;
1596 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1600 expr_with_var_bounded_array_refs_p (tree expr)
1602 while (handled_component_p (expr))
1604 if (TREE_CODE (expr) == ARRAY_REF
1605 && !host_integerp (array_ref_low_bound (expr), 0))
1607 expr = TREE_OPERAND (expr, 0);
1612 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1613 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1614 all sorts of access flags appropriately along the way, notably always ser
1615 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1618 analyze_access_subtree (struct access *root, bool allow_replacements,
1619 bool mark_read, bool mark_write)
1621 struct access *child;
1622 HOST_WIDE_INT limit = root->offset + root->size;
1623 HOST_WIDE_INT covered_to = root->offset;
1624 bool scalar = is_gimple_reg_type (root->type);
1625 bool hole = false, sth_created = false;
1626 bool direct_read = root->grp_read;
1629 root->grp_read = true;
1630 else if (root->grp_read)
1634 root->grp_write = true;
1635 else if (root->grp_write)
1638 if (root->grp_unscalarizable_region)
1639 allow_replacements = false;
1641 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1642 allow_replacements = false;
1644 for (child = root->first_child; child; child = child->next_sibling)
1646 if (!hole && child->offset < covered_to)
1649 covered_to += child->size;
1651 sth_created |= analyze_access_subtree (child, allow_replacements,
1652 mark_read, mark_write);
1654 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1655 hole |= !child->grp_covered;
1658 if (allow_replacements && scalar && !root->first_child
1660 || (direct_read && root->grp_write)))
1662 if (dump_file && (dump_flags & TDF_DETAILS))
1664 fprintf (dump_file, "Marking ");
1665 print_generic_expr (dump_file, root->base, 0);
1666 fprintf (dump_file, " offset: %u, size: %u: ",
1667 (unsigned) root->offset, (unsigned) root->size);
1668 fprintf (dump_file, " to be replaced.\n");
1671 root->grp_to_be_replaced = 1;
1675 else if (covered_to < limit)
1678 if (sth_created && !hole)
1680 root->grp_covered = 1;
1683 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1684 root->grp_unscalarized_data = 1; /* not covered and written to */
1690 /* Analyze all access trees linked by next_grp by the means of
1691 analyze_access_subtree. */
1693 analyze_access_trees (struct access *access)
1699 if (analyze_access_subtree (access, true, false, false))
1701 access = access->next_grp;
1707 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1708 SIZE would conflict with an already existing one. If exactly such a child
1709 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1712 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1713 HOST_WIDE_INT size, struct access **exact_match)
1715 struct access *child;
1717 for (child = lacc->first_child; child; child = child->next_sibling)
1719 if (child->offset == norm_offset && child->size == size)
1721 *exact_match = child;
1725 if (child->offset < norm_offset + size
1726 && child->offset + child->size > norm_offset)
1733 /* Create a new child access of PARENT, with all properties just like MODEL
1734 except for its offset and with its grp_write false and grp_read true.
1735 Return the new access or NULL if it cannot be created. Note that this access
1736 is created long after all splicing and sorting, it's not located in any
1737 access vector and is automatically a representative of its group. */
1739 static struct access *
1740 create_artificial_child_access (struct access *parent, struct access *model,
1741 HOST_WIDE_INT new_offset)
1743 struct access *access;
1744 struct access **child;
1745 tree expr = parent->base;;
1747 gcc_assert (!model->grp_unscalarizable_region);
1749 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1750 model->type, false))
1753 access = (struct access *) pool_alloc (access_pool);
1754 memset (access, 0, sizeof (struct access));
1755 access->base = parent->base;
1756 access->expr = expr;
1757 access->offset = new_offset;
1758 access->size = model->size;
1759 access->type = model->type;
1760 access->grp_write = true;
1761 access->grp_read = false;
1763 child = &parent->first_child;
1764 while (*child && (*child)->offset < new_offset)
1765 child = &(*child)->next_sibling;
1767 access->next_sibling = *child;
1774 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1775 true if any new subaccess was created. Additionally, if RACC is a scalar
1776 access but LACC is not, change the type of the latter, if possible. */
1779 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1781 struct access *rchild;
1782 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1785 if (is_gimple_reg_type (lacc->type)
1786 || lacc->grp_unscalarizable_region
1787 || racc->grp_unscalarizable_region)
1790 if (!lacc->first_child && !racc->first_child
1791 && is_gimple_reg_type (racc->type))
1793 tree t = lacc->base;
1795 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1799 lacc->type = racc->type;
1804 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1806 struct access *new_acc = NULL;
1807 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1809 if (rchild->grp_unscalarizable_region)
1812 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1817 rchild->grp_hint = 1;
1818 new_acc->grp_hint |= new_acc->grp_read;
1819 if (rchild->first_child)
1820 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1825 /* If a (part of) a union field is on the RHS of an assignment, it can
1826 have sub-accesses which do not make sense on the LHS (PR 40351).
1827 Check that this is not the case. */
1828 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1829 rchild->type, false))
1832 rchild->grp_hint = 1;
1833 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1837 if (racc->first_child)
1838 propagate_subaccesses_across_link (new_acc, rchild);
1845 /* Propagate all subaccesses across assignment links. */
1848 propagate_all_subaccesses (void)
1850 while (work_queue_head)
1852 struct access *racc = pop_access_from_work_queue ();
1853 struct assign_link *link;
1855 gcc_assert (racc->first_link);
1857 for (link = racc->first_link; link; link = link->next)
1859 struct access *lacc = link->lacc;
1861 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1863 lacc = lacc->group_representative;
1864 if (propagate_subaccesses_across_link (lacc, racc)
1865 && lacc->first_link)
1866 add_access_to_work_queue (lacc);
1871 /* Go through all accesses collected throughout the (intraprocedural) analysis
1872 stage, exclude overlapping ones, identify representatives and build trees
1873 out of them, making decisions about scalarization on the way. Return true
1874 iff there are any to-be-scalarized variables after this stage. */
1877 analyze_all_variable_accesses (void)
1880 bitmap tmp = BITMAP_ALLOC (NULL);
1884 bitmap_copy (tmp, candidate_bitmap);
1885 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1887 tree var = referenced_var (i);
1888 struct access *access;
1890 access = sort_and_splice_var_accesses (var);
1892 build_access_trees (access);
1894 disqualify_candidate (var,
1895 "No or inhibitingly overlapping accesses.");
1898 propagate_all_subaccesses ();
1900 bitmap_copy (tmp, candidate_bitmap);
1901 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1903 tree var = referenced_var (i);
1904 struct access *access = get_first_repr_for_decl (var);
1906 if (analyze_access_trees (access))
1909 if (dump_file && (dump_flags & TDF_DETAILS))
1911 fprintf (dump_file, "\nAccess trees for ");
1912 print_generic_expr (dump_file, var, 0);
1913 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1914 dump_access_tree (dump_file, access);
1915 fprintf (dump_file, "\n");
1919 disqualify_candidate (var, "No scalar replacements to be created.");
1926 statistics_counter_event (cfun, "Scalarized aggregates", res);
1933 /* Return true iff a reference statement into aggregate AGG can be built for
1934 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1935 or a child of its sibling. TOP_OFFSET is the offset from the processed
1936 access subtree that has to be subtracted from offset of each access. */
1939 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1940 HOST_WIDE_INT top_offset)
1944 if (access->grp_to_be_replaced
1945 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1946 access->offset - top_offset,
1947 access->type, false))
1950 if (access->first_child
1951 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1955 access = access->next_sibling;
1962 /* Generate statements copying scalar replacements of accesses within a subtree
1963 into or out of AGG. ACCESS is the first child of the root of the subtree to
1964 be processed. AGG is an aggregate type expression (can be a declaration but
1965 does not have to be, it can for example also be an indirect_ref).
1966 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1967 from offsets of individual accesses to get corresponding offsets for AGG.
1968 If CHUNK_SIZE is non-null, copy only replacements in the interval
1969 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1970 statement iterator used to place the new statements. WRITE should be true
1971 when the statements should write from AGG to the replacement and false if
1972 vice versa. if INSERT_AFTER is true, new statements will be added after the
1973 current statement in GSI, they will be added before the statement
1977 generate_subtree_copies (struct access *access, tree agg,
1978 HOST_WIDE_INT top_offset,
1979 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1980 gimple_stmt_iterator *gsi, bool write,
1987 if (chunk_size && access->offset >= start_offset + chunk_size)
1990 if (access->grp_to_be_replaced
1992 || access->offset + access->size > start_offset))
1994 tree repl = get_access_replacement (access);
1998 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1999 access->offset - top_offset,
2000 access->type, false);
2001 gcc_assert (ref_found);
2005 if (access->grp_partial_lhs)
2006 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2008 insert_after ? GSI_NEW_STMT
2010 stmt = gimple_build_assign (repl, expr);
2014 TREE_NO_WARNING (repl) = 1;
2015 if (access->grp_partial_lhs)
2016 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2018 insert_after ? GSI_NEW_STMT
2020 stmt = gimple_build_assign (expr, repl);
2024 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2026 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2028 sra_stats.subtree_copies++;
2031 if (access->first_child)
2032 generate_subtree_copies (access->first_child, agg, top_offset,
2033 start_offset, chunk_size, gsi,
2034 write, insert_after);
2036 access = access->next_sibling;
2041 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2042 the root of the subtree to be processed. GSI is the statement iterator used
2043 for inserting statements which are added after the current statement if
2044 INSERT_AFTER is true or before it otherwise. */
2047 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2051 struct access *child;
2053 if (access->grp_to_be_replaced)
2057 stmt = gimple_build_assign (get_access_replacement (access),
2058 fold_convert (access->type,
2059 integer_zero_node));
2061 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2063 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2067 for (child = access->first_child; child; child = child->next_sibling)
2068 init_subtree_with_zero (child, gsi, insert_after);
2071 /* Search for an access representative for the given expression EXPR and
2072 return it or NULL if it cannot be found. */
2074 static struct access *
2075 get_access_for_expr (tree expr)
2077 HOST_WIDE_INT offset, size, max_size;
2080 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2081 a different size than the size of its argument and we need the latter
2083 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2084 expr = TREE_OPERAND (expr, 0);
2086 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2087 if (max_size == -1 || !DECL_P (base))
2090 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2093 return get_var_base_offset_size_access (base, offset, max_size);
2096 /* Callback for scan_function. Replace the expression EXPR with a scalar
2097 replacement if there is one and generate other statements to do type
2098 conversion or subtree copying if necessary. GSI is used to place newly
2099 created statements, WRITE is true if the expression is being written to (it
2100 is on a LHS of a statement or output in an assembly statement). */
2103 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2104 void *data ATTRIBUTE_UNUSED)
2106 struct access *access;
2109 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2112 expr = &TREE_OPERAND (*expr, 0);
2117 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2118 expr = &TREE_OPERAND (*expr, 0);
2119 access = get_access_for_expr (*expr);
2122 type = TREE_TYPE (*expr);
2124 if (access->grp_to_be_replaced)
2126 tree repl = get_access_replacement (access);
2127 /* If we replace a non-register typed access simply use the original
2128 access expression to extract the scalar component afterwards.
2129 This happens if scalarizing a function return value or parameter
2130 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2131 gcc.c-torture/compile/20011217-1.c.
2133 We also want to use this when accessing a complex or vector which can
2134 be accessed as a different type too, potentially creating a need for
2135 type conversion (see PR42196) and when scalarized unions are involved
2136 in assembler statements (see PR42398). */
2137 if (!useless_type_conversion_p (type, access->type))
2139 tree ref = access->base;
2142 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2143 access->offset, access->type, false);
2150 if (access->grp_partial_lhs)
2151 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2152 false, GSI_NEW_STMT);
2153 stmt = gimple_build_assign (repl, ref);
2154 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2160 if (access->grp_partial_lhs)
2161 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2162 true, GSI_SAME_STMT);
2163 stmt = gimple_build_assign (ref, repl);
2164 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2172 if (access->first_child)
2174 HOST_WIDE_INT start_offset, chunk_size;
2176 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2177 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2179 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2180 start_offset = access->offset
2181 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2184 start_offset = chunk_size = 0;
2186 generate_subtree_copies (access->first_child, access->base, 0,
2187 start_offset, chunk_size, gsi, write, write);
2192 /* Where scalar replacements of the RHS have been written to when a replacement
2193 of a LHS of an assigments cannot be direclty loaded from a replacement of
2195 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2196 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2197 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2199 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2200 base aggregate if there are unscalarized data or directly to LHS
2203 static enum unscalarized_data_handling
2204 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2205 gimple_stmt_iterator *gsi)
2207 if (top_racc->grp_unscalarized_data)
2209 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2211 return SRA_UDH_RIGHT;
2215 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2216 0, 0, gsi, false, false);
2217 return SRA_UDH_LEFT;
2222 /* Try to generate statements to load all sub-replacements in an access
2223 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2224 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2225 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2226 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2227 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2228 the rhs top aggregate has already been refreshed by contents of its scalar
2229 reductions and is set to true if this function has to do it. */
2232 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2233 HOST_WIDE_INT left_offset,
2234 HOST_WIDE_INT right_offset,
2235 gimple_stmt_iterator *old_gsi,
2236 gimple_stmt_iterator *new_gsi,
2237 enum unscalarized_data_handling *refreshed,
2240 location_t loc = EXPR_LOCATION (lacc->expr);
2243 if (lacc->grp_to_be_replaced)
2245 struct access *racc;
2246 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2250 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2251 if (racc && racc->grp_to_be_replaced)
2253 rhs = get_access_replacement (racc);
2254 if (!useless_type_conversion_p (lacc->type, racc->type))
2255 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2259 /* No suitable access on the right hand side, need to load from
2260 the aggregate. See if we have to update it first... */
2261 if (*refreshed == SRA_UDH_NONE)
2262 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2265 if (*refreshed == SRA_UDH_LEFT)
2270 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2271 lacc->offset, lacc->type,
2273 gcc_assert (repl_found);
2279 rhs = top_racc->base;
2280 repl_found = build_ref_for_offset (&rhs,
2281 TREE_TYPE (top_racc->base),
2282 offset, lacc->type, false);
2283 gcc_assert (repl_found);
2287 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2288 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2290 sra_stats.subreplacements++;
2292 else if (*refreshed == SRA_UDH_NONE
2293 && lacc->grp_read && !lacc->grp_covered)
2294 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2297 if (lacc->first_child)
2298 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2299 left_offset, right_offset,
2300 old_gsi, new_gsi, refreshed, lhs);
2301 lacc = lacc->next_sibling;
2306 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2307 to the assignment and GSI is the statement iterator pointing at it. Returns
2308 the same values as sra_modify_assign. */
2310 static enum scan_assign_result
2311 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2313 tree lhs = gimple_assign_lhs (*stmt);
2316 acc = get_access_for_expr (lhs);
2320 if (VEC_length (constructor_elt,
2321 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2323 /* I have never seen this code path trigger but if it can happen the
2324 following should handle it gracefully. */
2325 if (access_has_children_p (acc))
2326 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2328 return SRA_SA_PROCESSED;
2331 if (acc->grp_covered)
2333 init_subtree_with_zero (acc, gsi, false);
2334 unlink_stmt_vdef (*stmt);
2335 gsi_remove (gsi, true);
2336 return SRA_SA_REMOVED;
2340 init_subtree_with_zero (acc, gsi, true);
2341 return SRA_SA_PROCESSED;
2346 /* Callback of scan_function to process assign statements. It examines both
2347 sides of the statement, replaces them with a scalare replacement if there is
2348 one and generating copying of replacements if scalarized aggregates have been
2349 used in the assignment. STMT is a pointer to the assign statement, GSI is
2350 used to hold generated statements for type conversions and subtree
2353 static enum scan_assign_result
2354 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2355 void *data ATTRIBUTE_UNUSED)
2357 struct access *lacc, *racc;
2359 bool modify_this_stmt = false;
2360 bool force_gimple_rhs = false;
2361 location_t loc = gimple_location (*stmt);
2363 if (!gimple_assign_single_p (*stmt))
2365 lhs = gimple_assign_lhs (*stmt);
2366 rhs = gimple_assign_rhs1 (*stmt);
2368 if (TREE_CODE (rhs) == CONSTRUCTOR)
2369 return sra_modify_constructor_assign (stmt, gsi);
2371 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2372 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2373 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2375 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2377 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2379 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2382 lacc = get_access_for_expr (lhs);
2383 racc = get_access_for_expr (rhs);
2387 if (lacc && lacc->grp_to_be_replaced)
2389 lhs = get_access_replacement (lacc);
2390 gimple_assign_set_lhs (*stmt, lhs);
2391 modify_this_stmt = true;
2392 if (lacc->grp_partial_lhs)
2393 force_gimple_rhs = true;
2397 if (racc && racc->grp_to_be_replaced)
2399 rhs = get_access_replacement (racc);
2400 modify_this_stmt = true;
2401 if (racc->grp_partial_lhs)
2402 force_gimple_rhs = true;
2406 if (modify_this_stmt)
2408 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2410 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2411 ??? This should move to fold_stmt which we simply should
2412 call after building a VIEW_CONVERT_EXPR here. */
2413 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2414 && !access_has_children_p (lacc))
2417 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2418 TREE_TYPE (rhs), false))
2421 gimple_assign_set_lhs (*stmt, expr);
2424 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2425 && !access_has_children_p (racc))
2428 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2429 TREE_TYPE (lhs), false))
2432 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2434 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2435 if (is_gimple_reg_type (TREE_TYPE (lhs))
2436 && TREE_CODE (lhs) != SSA_NAME)
2437 force_gimple_rhs = true;
2441 if (force_gimple_rhs)
2442 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2443 true, GSI_SAME_STMT);
2444 if (gimple_assign_rhs1 (*stmt) != rhs)
2446 gimple_assign_set_rhs_from_tree (gsi, rhs);
2447 gcc_assert (*stmt == gsi_stmt (*gsi));
2451 /* From this point on, the function deals with assignments in between
2452 aggregates when at least one has scalar reductions of some of its
2453 components. There are three possible scenarios: Both the LHS and RHS have
2454 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2456 In the first case, we would like to load the LHS components from RHS
2457 components whenever possible. If that is not possible, we would like to
2458 read it directly from the RHS (after updating it by storing in it its own
2459 components). If there are some necessary unscalarized data in the LHS,
2460 those will be loaded by the original assignment too. If neither of these
2461 cases happen, the original statement can be removed. Most of this is done
2462 by load_assign_lhs_subreplacements.
2464 In the second case, we would like to store all RHS scalarized components
2465 directly into LHS and if they cover the aggregate completely, remove the
2466 statement too. In the third case, we want the LHS components to be loaded
2467 directly from the RHS (DSE will remove the original statement if it
2470 This is a bit complex but manageable when types match and when unions do
2471 not cause confusion in a way that we cannot really load a component of LHS
2472 from the RHS or vice versa (the access representing this level can have
2473 subaccesses that are accessible only through a different union field at a
2474 higher level - different from the one used in the examined expression).
2477 Therefore, I specially handle a fourth case, happening when there is a
2478 specific type cast or it is impossible to locate a scalarized subaccess on
2479 the other side of the expression. If that happens, I simply "refresh" the
2480 RHS by storing in it is scalarized components leave the original statement
2481 there to do the copying and then load the scalar replacements of the LHS.
2482 This is what the first branch does. */
2484 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2485 || (access_has_children_p (racc)
2486 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2487 || (access_has_children_p (lacc)
2488 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2490 if (access_has_children_p (racc))
2491 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2493 if (access_has_children_p (lacc))
2494 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2496 sra_stats.separate_lhs_rhs_handling++;
2500 if (access_has_children_p (lacc) && access_has_children_p (racc))
2502 gimple_stmt_iterator orig_gsi = *gsi;
2503 enum unscalarized_data_handling refreshed;
2505 if (lacc->grp_read && !lacc->grp_covered)
2506 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2508 refreshed = SRA_UDH_NONE;
2510 load_assign_lhs_subreplacements (lacc->first_child, racc,
2511 lacc->offset, racc->offset,
2512 &orig_gsi, gsi, &refreshed, lhs);
2513 if (refreshed != SRA_UDH_RIGHT)
2515 if (*stmt == gsi_stmt (*gsi))
2518 unlink_stmt_vdef (*stmt);
2519 gsi_remove (&orig_gsi, true);
2520 sra_stats.deleted++;
2521 return SRA_SA_REMOVED;
2526 if (access_has_children_p (racc))
2528 if (!racc->grp_unscalarized_data)
2530 generate_subtree_copies (racc->first_child, lhs,
2531 racc->offset, 0, 0, gsi,
2533 gcc_assert (*stmt == gsi_stmt (*gsi));
2534 unlink_stmt_vdef (*stmt);
2535 gsi_remove (gsi, true);
2536 sra_stats.deleted++;
2537 return SRA_SA_REMOVED;
2540 generate_subtree_copies (racc->first_child, lhs,
2541 racc->offset, 0, 0, gsi, false, true);
2543 else if (access_has_children_p (lacc))
2544 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2545 0, 0, gsi, true, true);
2548 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2551 /* Generate statements initializing scalar replacements of parts of function
2555 initialize_parameter_reductions (void)
2557 gimple_stmt_iterator gsi;
2558 gimple_seq seq = NULL;
2561 for (parm = DECL_ARGUMENTS (current_function_decl);
2563 parm = TREE_CHAIN (parm))
2565 VEC (access_p, heap) *access_vec;
2566 struct access *access;
2568 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2570 access_vec = get_base_access_vector (parm);
2576 seq = gimple_seq_alloc ();
2577 gsi = gsi_start (seq);
2580 for (access = VEC_index (access_p, access_vec, 0);
2582 access = access->next_grp)
2583 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2587 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2590 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2591 it reveals there are components of some aggregates to be scalarized, it runs
2592 the required transformations. */
2594 perform_intra_sra (void)
2599 if (!find_var_candidates ())
2602 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2606 if (!analyze_all_variable_accesses ())
2609 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2610 initialize_parameter_reductions ();
2612 statistics_counter_event (cfun, "Scalar replacements created",
2613 sra_stats.replacements);
2614 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2615 statistics_counter_event (cfun, "Subtree copy stmts",
2616 sra_stats.subtree_copies);
2617 statistics_counter_event (cfun, "Subreplacement stmts",
2618 sra_stats.subreplacements);
2619 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2620 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2621 sra_stats.separate_lhs_rhs_handling);
2623 ret = TODO_update_ssa;
2626 sra_deinitialize ();
2630 /* Perform early intraprocedural SRA. */
2632 early_intra_sra (void)
2634 sra_mode = SRA_MODE_EARLY_INTRA;
2635 return perform_intra_sra ();
2638 /* Perform "late" intraprocedural SRA. */
2640 late_intra_sra (void)
2642 sra_mode = SRA_MODE_INTRA;
2643 return perform_intra_sra ();
2648 gate_intra_sra (void)
2650 return flag_tree_sra != 0;
2654 struct gimple_opt_pass pass_sra_early =
2659 gate_intra_sra, /* gate */
2660 early_intra_sra, /* execute */
2663 0, /* static_pass_number */
2664 TV_TREE_SRA, /* tv_id */
2665 PROP_cfg | PROP_ssa, /* properties_required */
2666 0, /* properties_provided */
2667 0, /* properties_destroyed */
2668 0, /* todo_flags_start */
2672 | TODO_verify_ssa /* todo_flags_finish */
2676 struct gimple_opt_pass pass_sra =
2681 gate_intra_sra, /* gate */
2682 late_intra_sra, /* execute */
2685 0, /* static_pass_number */
2686 TV_TREE_SRA, /* tv_id */
2687 PROP_cfg | PROP_ssa, /* properties_required */
2688 0, /* properties_provided */
2689 0, /* properties_destroyed */
2690 TODO_update_address_taken, /* todo_flags_start */
2694 | TODO_verify_ssa /* todo_flags_finish */
2699 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2703 is_unused_scalar_param (tree parm)
2706 return (is_gimple_reg (parm)
2707 && (!(name = gimple_default_def (cfun, parm))
2708 || has_zero_uses (name)));
2711 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2712 examine whether there are any direct or otherwise infeasible ones. If so,
2713 return true, otherwise return false. PARM must be a gimple register with a
2714 non-NULL default definition. */
2717 ptr_parm_has_direct_uses (tree parm)
2719 imm_use_iterator ui;
2721 tree name = gimple_default_def (cfun, parm);
2724 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2726 if (gimple_assign_single_p (stmt))
2728 tree rhs = gimple_assign_rhs1 (stmt);
2731 else if (TREE_CODE (rhs) == ADDR_EXPR)
2735 rhs = TREE_OPERAND (rhs, 0);
2737 while (handled_component_p (rhs));
2738 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2742 else if (gimple_code (stmt) == GIMPLE_RETURN)
2744 tree t = gimple_return_retval (stmt);
2748 else if (is_gimple_call (stmt))
2751 for (i = 0; i < gimple_call_num_args (stmt); i++)
2753 tree arg = gimple_call_arg (stmt, i);
2761 else if (!is_gimple_debug (stmt))
2765 BREAK_FROM_IMM_USE_STMT (ui);
2771 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2772 them in candidate_bitmap. Note that these do not necessarily include
2773 parameter which are unused and thus can be removed. Return true iff any
2774 such candidate has been found. */
2777 find_param_candidates (void)
2783 for (parm = DECL_ARGUMENTS (current_function_decl);
2785 parm = TREE_CHAIN (parm))
2787 tree type = TREE_TYPE (parm);
2791 if (TREE_THIS_VOLATILE (parm)
2792 || TREE_ADDRESSABLE (parm)
2793 || is_va_list_type (type))
2796 if (is_unused_scalar_param (parm))
2802 if (POINTER_TYPE_P (type))
2804 type = TREE_TYPE (type);
2806 if (TREE_CODE (type) == FUNCTION_TYPE
2807 || TYPE_VOLATILE (type)
2808 || !is_gimple_reg (parm)
2809 || is_va_list_type (type)
2810 || ptr_parm_has_direct_uses (parm))
2813 else if (!AGGREGATE_TYPE_P (type))
2816 if (!COMPLETE_TYPE_P (type)
2817 || !host_integerp (TYPE_SIZE (type), 1)
2818 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2819 || (AGGREGATE_TYPE_P (type)
2820 && type_internals_preclude_sra_p (type)))
2823 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2825 if (dump_file && (dump_flags & TDF_DETAILS))
2827 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2828 print_generic_expr (dump_file, parm, 0);
2829 fprintf (dump_file, "\n");
2833 func_param_count = count;
2837 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2841 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2844 struct access *repr = (struct access *) data;
2846 repr->grp_maybe_modified = 1;
2850 /* Analyze what representatives (in linked lists accessible from
2851 REPRESENTATIVES) can be modified by side effects of statements in the
2852 current function. */
2855 analyze_modified_params (VEC (access_p, heap) *representatives)
2859 for (i = 0; i < func_param_count; i++)
2861 struct access *repr;
2863 for (repr = VEC_index (access_p, representatives, i);
2865 repr = repr->next_grp)
2867 struct access *access;
2871 if (no_accesses_p (repr))
2873 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
2874 || repr->grp_maybe_modified)
2877 ao_ref_init (&ar, repr->expr);
2878 visited = BITMAP_ALLOC (NULL);
2879 for (access = repr; access; access = access->next_sibling)
2881 /* All accesses are read ones, otherwise grp_maybe_modified would
2882 be trivially set. */
2883 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2884 mark_maybe_modified, repr, &visited);
2885 if (repr->grp_maybe_modified)
2888 BITMAP_FREE (visited);
2893 /* Propagate distances in bb_dereferences in the opposite direction than the
2894 control flow edges, in each step storing the maximum of the current value
2895 and the minimum of all successors. These steps are repeated until the table
2896 stabilizes. Note that BBs which might terminate the functions (according to
2897 final_bbs bitmap) never updated in this way. */
2900 propagate_dereference_distances (void)
2902 VEC (basic_block, heap) *queue;
2905 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2906 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2909 VEC_quick_push (basic_block, queue, bb);
2913 while (!VEC_empty (basic_block, queue))
2917 bool change = false;
2920 bb = VEC_pop (basic_block, queue);
2923 if (bitmap_bit_p (final_bbs, bb->index))
2926 for (i = 0; i < func_param_count; i++)
2928 int idx = bb->index * func_param_count + i;
2930 HOST_WIDE_INT inh = 0;
2932 FOR_EACH_EDGE (e, ei, bb->succs)
2934 int succ_idx = e->dest->index * func_param_count + i;
2936 if (e->src == EXIT_BLOCK_PTR)
2942 inh = bb_dereferences [succ_idx];
2944 else if (bb_dereferences [succ_idx] < inh)
2945 inh = bb_dereferences [succ_idx];
2948 if (!first && bb_dereferences[idx] < inh)
2950 bb_dereferences[idx] = inh;
2955 if (change && !bitmap_bit_p (final_bbs, bb->index))
2956 FOR_EACH_EDGE (e, ei, bb->preds)
2961 e->src->aux = e->src;
2962 VEC_quick_push (basic_block, queue, e->src);
2966 VEC_free (basic_block, heap, queue);
2969 /* Dump a dereferences TABLE with heading STR to file F. */
2972 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2976 fprintf (dump_file, str);
2977 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2979 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2980 if (bb != EXIT_BLOCK_PTR)
2983 for (i = 0; i < func_param_count; i++)
2985 int idx = bb->index * func_param_count + i;
2986 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
2991 fprintf (dump_file, "\n");
2994 /* Determine what (parts of) parameters passed by reference that are not
2995 assigned to are not certainly dereferenced in this function and thus the
2996 dereferencing cannot be safely moved to the caller without potentially
2997 introducing a segfault. Mark such REPRESENTATIVES as
2998 grp_not_necessarilly_dereferenced.
3000 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3001 part is calculated rather than simple booleans are calculated for each
3002 pointer parameter to handle cases when only a fraction of the whole
3003 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3006 The maximum dereference distances for each pointer parameter and BB are
3007 already stored in bb_dereference. This routine simply propagates these
3008 values upwards by propagate_dereference_distances and then compares the
3009 distances of individual parameters in the ENTRY BB to the equivalent
3010 distances of each representative of a (fraction of a) parameter. */
3013 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3017 if (dump_file && (dump_flags & TDF_DETAILS))
3018 dump_dereferences_table (dump_file,
3019 "Dereference table before propagation:\n",
3022 propagate_dereference_distances ();
3024 if (dump_file && (dump_flags & TDF_DETAILS))
3025 dump_dereferences_table (dump_file,
3026 "Dereference table after propagation:\n",
3029 for (i = 0; i < func_param_count; i++)
3031 struct access *repr = VEC_index (access_p, representatives, i);
3032 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3034 if (!repr || no_accesses_p (repr))
3039 if ((repr->offset + repr->size) > bb_dereferences[idx])
3040 repr->grp_not_necessarilly_dereferenced = 1;
3041 repr = repr->next_grp;
3047 /* Return the representative access for the parameter declaration PARM if it is
3048 a scalar passed by reference which is not written to and the pointer value
3049 is not used directly. Thus, if it is legal to dereference it in the caller
3050 and we can rule out modifications through aliases, such parameter should be
3051 turned into one passed by value. Return NULL otherwise. */
3053 static struct access *
3054 unmodified_by_ref_scalar_representative (tree parm)
3056 int i, access_count;
3057 struct access *repr;
3058 VEC (access_p, heap) *access_vec;
3060 access_vec = get_base_access_vector (parm);
3061 gcc_assert (access_vec);
3062 repr = VEC_index (access_p, access_vec, 0);
3065 repr->group_representative = repr;
3067 access_count = VEC_length (access_p, access_vec);
3068 for (i = 1; i < access_count; i++)
3070 struct access *access = VEC_index (access_p, access_vec, i);
3073 access->group_representative = repr;
3074 access->next_sibling = repr->next_sibling;
3075 repr->next_sibling = access;
3079 repr->grp_scalar_ptr = 1;
3083 /* Return true iff this access precludes IPA-SRA of the parameter it is
3087 access_precludes_ipa_sra_p (struct access *access)
3089 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3090 is incompatible assign in a call statement (and possibly even in asm
3091 statements). This can be relaxed by using a new temporary but only for
3092 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3093 intraprocedural SRA we deal with this by keeping the old aggregate around,
3094 something we cannot do in IPA-SRA.) */
3096 && (is_gimple_call (access->stmt)
3097 || gimple_code (access->stmt) == GIMPLE_ASM))
3104 /* Sort collected accesses for parameter PARM, identify representatives for
3105 each accessed region and link them together. Return NULL if there are
3106 different but overlapping accesses, return the special ptr value meaning
3107 there are no accesses for this parameter if that is the case and return the
3108 first representative otherwise. Set *RO_GRP if there is a group of accesses
3109 with only read (i.e. no write) accesses. */
3111 static struct access *
3112 splice_param_accesses (tree parm, bool *ro_grp)
3114 int i, j, access_count, group_count;
3115 int agg_size, total_size = 0;
3116 struct access *access, *res, **prev_acc_ptr = &res;
3117 VEC (access_p, heap) *access_vec;
3119 access_vec = get_base_access_vector (parm);
3121 return &no_accesses_representant;
3122 access_count = VEC_length (access_p, access_vec);
3124 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3125 compare_access_positions);
3130 while (i < access_count)
3133 access = VEC_index (access_p, access_vec, i);
3134 modification = access->write;
3135 if (access_precludes_ipa_sra_p (access))
3138 /* Access is about to become group representative unless we find some
3139 nasty overlap which would preclude us from breaking this parameter
3143 while (j < access_count)
3145 struct access *ac2 = VEC_index (access_p, access_vec, j);
3146 if (ac2->offset != access->offset)
3148 /* All or nothing law for parameters. */
3149 if (access->offset + access->size > ac2->offset)
3154 else if (ac2->size != access->size)
3157 if (access_precludes_ipa_sra_p (ac2))
3160 modification |= ac2->write;
3161 ac2->group_representative = access;
3162 ac2->next_sibling = access->next_sibling;
3163 access->next_sibling = ac2;
3168 access->grp_maybe_modified = modification;
3171 *prev_acc_ptr = access;
3172 prev_acc_ptr = &access->next_grp;
3173 total_size += access->size;
3177 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3178 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3180 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3181 if (total_size >= agg_size)
3184 gcc_assert (group_count > 0);
3188 /* Decide whether parameters with representative accesses given by REPR should
3189 be reduced into components. */
3192 decide_one_param_reduction (struct access *repr)
3194 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3199 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3200 gcc_assert (cur_parm_size > 0);
3202 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3205 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3210 agg_size = cur_parm_size;
3216 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3217 print_generic_expr (dump_file, parm, 0);
3218 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3219 for (acc = repr; acc; acc = acc->next_grp)
3220 dump_access (dump_file, acc, true);
3224 new_param_count = 0;
3226 for (; repr; repr = repr->next_grp)
3228 gcc_assert (parm == repr->base);
3231 if (!by_ref || (!repr->grp_maybe_modified
3232 && !repr->grp_not_necessarilly_dereferenced))
3233 total_size += repr->size;
3235 total_size += cur_parm_size;
3238 gcc_assert (new_param_count > 0);
3240 if (optimize_function_for_size_p (cfun))
3241 parm_size_limit = cur_parm_size;
3243 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3246 if (total_size < agg_size
3247 && total_size <= parm_size_limit)
3250 fprintf (dump_file, " ....will be split into %i components\n",
3252 return new_param_count;
3258 /* The order of the following enums is important, we need to do extra work for
3259 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3260 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3261 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3263 /* Identify representatives of all accesses to all candidate parameters for
3264 IPA-SRA. Return result based on what representatives have been found. */
3266 static enum ipa_splicing_result
3267 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3269 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3271 struct access *repr;
3273 *representatives = VEC_alloc (access_p, heap, func_param_count);
3275 for (parm = DECL_ARGUMENTS (current_function_decl);
3277 parm = TREE_CHAIN (parm))
3279 if (is_unused_scalar_param (parm))
3281 VEC_quick_push (access_p, *representatives,
3282 &no_accesses_representant);
3283 if (result == NO_GOOD_ACCESS)
3284 result = UNUSED_PARAMS;
3286 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3287 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3288 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3290 repr = unmodified_by_ref_scalar_representative (parm);
3291 VEC_quick_push (access_p, *representatives, repr);
3293 result = UNMODIF_BY_REF_ACCESSES;
3295 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3297 bool ro_grp = false;
3298 repr = splice_param_accesses (parm, &ro_grp);
3299 VEC_quick_push (access_p, *representatives, repr);
3301 if (repr && !no_accesses_p (repr))
3303 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3306 result = UNMODIF_BY_REF_ACCESSES;
3307 else if (result < MODIF_BY_REF_ACCESSES)
3308 result = MODIF_BY_REF_ACCESSES;
3310 else if (result < BY_VAL_ACCESSES)
3311 result = BY_VAL_ACCESSES;
3313 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3314 result = UNUSED_PARAMS;
3317 VEC_quick_push (access_p, *representatives, NULL);
3320 if (result == NO_GOOD_ACCESS)
3322 VEC_free (access_p, heap, *representatives);
3323 *representatives = NULL;
3324 return NO_GOOD_ACCESS;
3330 /* Return the index of BASE in PARMS. Abort if it is not found. */
3333 get_param_index (tree base, VEC(tree, heap) *parms)
3337 len = VEC_length (tree, parms);
3338 for (i = 0; i < len; i++)
3339 if (VEC_index (tree, parms, i) == base)
3344 /* Convert the decisions made at the representative level into compact
3345 parameter adjustments. REPRESENTATIVES are pointers to first
3346 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3347 final number of adjustments. */
3349 static ipa_parm_adjustment_vec
3350 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3351 int adjustments_count)
3353 VEC (tree, heap) *parms;
3354 ipa_parm_adjustment_vec adjustments;
3358 gcc_assert (adjustments_count > 0);
3359 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3360 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3361 parm = DECL_ARGUMENTS (current_function_decl);
3362 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3364 struct access *repr = VEC_index (access_p, representatives, i);
3366 if (!repr || no_accesses_p (repr))
3368 struct ipa_parm_adjustment *adj;
3370 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3371 memset (adj, 0, sizeof (*adj));
3372 adj->base_index = get_param_index (parm, parms);
3375 adj->copy_param = 1;
3377 adj->remove_param = 1;
3381 struct ipa_parm_adjustment *adj;
3382 int index = get_param_index (parm, parms);
3384 for (; repr; repr = repr->next_grp)
3386 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3387 memset (adj, 0, sizeof (*adj));
3388 gcc_assert (repr->base == parm);
3389 adj->base_index = index;
3390 adj->base = repr->base;
3391 adj->type = repr->type;
3392 adj->offset = repr->offset;
3393 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3394 && (repr->grp_maybe_modified
3395 || repr->grp_not_necessarilly_dereferenced));
3400 VEC_free (tree, heap, parms);
3404 /* Analyze the collected accesses and produce a plan what to do with the
3405 parameters in the form of adjustments, NULL meaning nothing. */
3407 static ipa_parm_adjustment_vec
3408 analyze_all_param_acesses (void)
3410 enum ipa_splicing_result repr_state;
3411 bool proceed = false;
3412 int i, adjustments_count = 0;
3413 VEC (access_p, heap) *representatives;
3414 ipa_parm_adjustment_vec adjustments;
3416 repr_state = splice_all_param_accesses (&representatives);
3417 if (repr_state == NO_GOOD_ACCESS)
3420 /* If there are any parameters passed by reference which are not modified
3421 directly, we need to check whether they can be modified indirectly. */
3422 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3424 analyze_caller_dereference_legality (representatives);
3425 analyze_modified_params (representatives);
3428 for (i = 0; i < func_param_count; i++)
3430 struct access *repr = VEC_index (access_p, representatives, i);
3432 if (repr && !no_accesses_p (repr))
3434 if (repr->grp_scalar_ptr)
3436 adjustments_count++;
3437 if (repr->grp_not_necessarilly_dereferenced
3438 || repr->grp_maybe_modified)
3439 VEC_replace (access_p, representatives, i, NULL);
3443 sra_stats.scalar_by_ref_to_by_val++;
3448 int new_components = decide_one_param_reduction (repr);
3450 if (new_components == 0)
3452 VEC_replace (access_p, representatives, i, NULL);
3453 adjustments_count++;
3457 adjustments_count += new_components;
3458 sra_stats.aggregate_params_reduced++;
3459 sra_stats.param_reductions_created += new_components;
3466 if (no_accesses_p (repr))
3469 sra_stats.deleted_unused_parameters++;
3471 adjustments_count++;
3475 if (!proceed && dump_file)
3476 fprintf (dump_file, "NOT proceeding to change params.\n");
3479 adjustments = turn_representatives_into_adjustments (representatives,
3484 VEC_free (access_p, heap, representatives);
3488 /* If a parameter replacement identified by ADJ does not yet exist in the form
3489 of declaration, create it and record it, otherwise return the previously
3493 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3496 if (!adj->new_ssa_base)
3498 char *pretty_name = make_fancy_name (adj->base);
3500 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3501 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3502 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3503 DECL_GIMPLE_REG_P (repl) = 1;
3504 DECL_NAME (repl) = get_identifier (pretty_name);
3505 obstack_free (&name_obstack, pretty_name);
3508 add_referenced_var (repl);
3509 adj->new_ssa_base = repl;
3512 repl = adj->new_ssa_base;
3516 /* Find the first adjustment for a particular parameter BASE in a vector of
3517 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3520 static struct ipa_parm_adjustment *
3521 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3525 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3526 for (i = 0; i < len; i++)
3528 struct ipa_parm_adjustment *adj;
3530 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3531 if (!adj->copy_param && adj->base == base)
3538 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3539 parameter which is to be removed because its value is not used, replace the
3540 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3541 uses too and return true (update_stmt is then issued for the statement by
3542 the caller). DATA is a pointer to an adjustments vector. */
3545 replace_removed_params_ssa_names (gimple stmt, void *data)
3547 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3548 struct ipa_parm_adjustment *adj;
3549 tree lhs, decl, repl, name;
3551 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3552 if (gimple_code (stmt) == GIMPLE_PHI)
3553 lhs = gimple_phi_result (stmt);
3554 else if (is_gimple_assign (stmt))
3555 lhs = gimple_assign_lhs (stmt);
3556 else if (is_gimple_call (stmt))
3557 lhs = gimple_call_lhs (stmt);
3561 if (TREE_CODE (lhs) != SSA_NAME)
3563 decl = SSA_NAME_VAR (lhs);
3564 if (TREE_CODE (decl) != PARM_DECL)
3567 adj = get_adjustment_for_base (adjustments, decl);
3571 repl = get_replaced_param_substitute (adj);
3572 name = make_ssa_name (repl, stmt);
3576 fprintf (dump_file, "replacing an SSA name of a removed param ");
3577 print_generic_expr (dump_file, lhs, 0);
3578 fprintf (dump_file, " with ");
3579 print_generic_expr (dump_file, name, 0);
3580 fprintf (dump_file, "\n");
3583 if (is_gimple_assign (stmt))
3584 gimple_assign_set_lhs (stmt, name);
3585 else if (is_gimple_call (stmt))
3586 gimple_call_set_lhs (stmt, name);
3588 gimple_phi_set_result (stmt, name);
3590 replace_uses_by (lhs, name);
3594 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3595 expression *EXPR should be replaced by a reduction of a parameter, do so.
3596 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3597 whether the function should care about type incompatibility the current and
3598 new expressions. If it is true, the function will leave incompatibility
3599 issues to the caller.
3601 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3602 a write (LHS) expression. */
3605 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3606 bool dont_convert, void *data)
3608 ipa_parm_adjustment_vec adjustments;
3610 struct ipa_parm_adjustment *adj, *cand = NULL;
3611 HOST_WIDE_INT offset, size, max_size;
3614 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3615 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3617 if (TREE_CODE (*expr) == BIT_FIELD_REF
3618 || TREE_CODE (*expr) == IMAGPART_EXPR
3619 || TREE_CODE (*expr) == REALPART_EXPR)
3621 expr = &TREE_OPERAND (*expr, 0);
3622 dont_convert = false;
3625 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3626 if (!base || size == -1 || max_size == -1)
3629 if (INDIRECT_REF_P (base))
3630 base = TREE_OPERAND (base, 0);
3632 base = get_ssa_base_param (base);
3633 if (!base || TREE_CODE (base) != PARM_DECL)
3636 for (i = 0; i < len; i++)
3638 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3640 if (adj->base == base &&
3641 (adj->offset == offset || adj->remove_param))
3647 if (!cand || cand->copy_param || cand->remove_param)
3653 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3655 folded = gimple_fold_indirect_ref (src);
3660 src = cand->reduction;
3662 if (dump_file && (dump_flags & TDF_DETAILS))
3664 fprintf (dump_file, "About to replace expr ");
3665 print_generic_expr (dump_file, *expr, 0);
3666 fprintf (dump_file, " with ");
3667 print_generic_expr (dump_file, src, 0);
3668 fprintf (dump_file, "\n");
3672 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3674 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3682 /* Callback for scan_function to process assign statements. Performs
3683 essentially the same function like sra_ipa_modify_expr. */
3685 static enum scan_assign_result
3686 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3688 gimple stmt = *stmt_ptr;
3689 tree *lhs_p, *rhs_p;
3692 if (!gimple_assign_single_p (stmt))
3695 rhs_p = gimple_assign_rhs1_ptr (stmt);
3696 lhs_p = gimple_assign_lhs_ptr (stmt);
3698 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3699 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3702 tree new_rhs = NULL_TREE;
3704 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3705 new_rhs = fold_build1_loc (gimple_location (stmt), VIEW_CONVERT_EXPR,
3706 TREE_TYPE (*lhs_p), *rhs_p);
3707 else if (REFERENCE_CLASS_P (*rhs_p)
3708 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3709 && !is_gimple_reg (*lhs_p))
3710 /* This can happen when an assignment in between two single field
3711 structures is turned into an assignment in between two pointers to
3712 scalars (PR 42237). */
3717 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3718 true, GSI_SAME_STMT);
3720 gimple_assign_set_rhs_from_tree (gsi, tmp);
3723 return SRA_SA_PROCESSED;
3729 /* Call gimple_debug_bind_reset_value on all debug statements describing
3730 gimple register parameters that are being removed or replaced. */
3733 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3737 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3738 for (i = 0; i < len; i++)
3740 struct ipa_parm_adjustment *adj;
3741 imm_use_iterator ui;
3745 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3746 if (adj->copy_param || !is_gimple_reg (adj->base))
3748 name = gimple_default_def (cfun, adj->base);
3751 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3753 /* All other users must have been removed by scan_function. */
3754 gcc_assert (is_gimple_debug (stmt));
3755 gimple_debug_bind_reset_value (stmt);
3761 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3764 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3766 tree old_cur_fndecl = current_function_decl;
3767 struct cgraph_edge *cs;
3768 basic_block this_block;
3769 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3771 for (cs = node->callers; cs; cs = cs->next_caller)
3773 current_function_decl = cs->caller->decl;
3774 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3777 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3778 cs->caller->uid, cs->callee->uid,
3779 cgraph_node_name (cs->caller),
3780 cgraph_node_name (cs->callee));
3782 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3787 for (cs = node->callers; cs; cs = cs->next_caller)
3788 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3790 compute_inline_parameters (cs->caller);
3791 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3793 BITMAP_FREE (recomputed_callers);
3795 current_function_decl = old_cur_fndecl;
3796 FOR_EACH_BB (this_block)
3798 gimple_stmt_iterator gsi;
3800 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3802 gimple stmt = gsi_stmt (gsi);
3804 if (gimple_code (stmt) != GIMPLE_CALL)
3806 call_fndecl = gimple_call_fndecl (stmt);
3807 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
3810 fprintf (dump_file, "Adjusting recursive call");
3811 ipa_modify_call_arguments (NULL, stmt, adjustments);
3819 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3820 as given in ADJUSTMENTS. */
3823 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3825 struct cgraph_node *alias;
3826 for (alias = node->same_body; alias; alias = alias->next)
3827 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
3828 /* current_function_decl must be handled last, after same_body aliases,
3829 as following functions will use what it computed. */
3830 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3831 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3832 replace_removed_params_ssa_names, false, adjustments);
3833 sra_ipa_reset_debug_stmts (adjustments);
3834 convert_callers (node, adjustments);
3835 cgraph_make_node_local (node);
3839 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3840 attributes, return true otherwise. NODE is the cgraph node of the current
3844 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3846 if (!cgraph_node_can_be_local_p (node))
3849 fprintf (dump_file, "Function not local to this compilation unit.\n");
3853 if (DECL_VIRTUAL_P (current_function_decl))
3856 fprintf (dump_file, "Function is a virtual method.\n");
3860 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3861 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3864 fprintf (dump_file, "Function too big to be made truly local.\n");
3872 "Function has no callers in this compilation unit.\n");
3879 fprintf (dump_file, "Function uses stdarg. \n");
3886 /* Perform early interprocedural SRA. */
3889 ipa_early_sra (void)
3891 struct cgraph_node *node = cgraph_node (current_function_decl);
3892 ipa_parm_adjustment_vec adjustments;
3895 if (!ipa_sra_preliminary_function_checks (node))
3899 sra_mode = SRA_MODE_EARLY_IPA;
3901 if (!find_param_candidates ())
3904 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3908 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3910 * last_basic_block_for_function (cfun));
3911 final_bbs = BITMAP_ALLOC (NULL);
3913 scan_function (build_access_from_expr, build_accesses_from_assign,
3915 if (encountered_apply_args)
3918 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3922 adjustments = analyze_all_param_acesses ();
3926 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3928 modify_function (node, adjustments);
3929 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3930 ret = TODO_update_ssa;
3932 statistics_counter_event (cfun, "Unused parameters deleted",
3933 sra_stats.deleted_unused_parameters);
3934 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3935 sra_stats.scalar_by_ref_to_by_val);
3936 statistics_counter_event (cfun, "Aggregate parameters broken up",
3937 sra_stats.aggregate_params_reduced);
3938 statistics_counter_event (cfun, "Aggregate parameter components created",
3939 sra_stats.param_reductions_created);
3942 BITMAP_FREE (final_bbs);
3943 free (bb_dereferences);
3945 sra_deinitialize ();
3949 /* Return if early ipa sra shall be performed. */
3951 ipa_early_sra_gate (void)
3953 return flag_ipa_sra;
3956 struct gimple_opt_pass pass_early_ipa_sra =
3960 "eipa_sra", /* name */
3961 ipa_early_sra_gate, /* gate */
3962 ipa_early_sra, /* execute */
3965 0, /* static_pass_number */
3966 TV_IPA_SRA, /* tv_id */
3967 0, /* properties_required */
3968 0, /* properties_provided */
3969 0, /* properties_destroyed */
3970 0, /* todo_flags_start */
3971 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */