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 if (f1->type == f2->type)
1115 /* Put any non-aggregate type before any aggregate type. */
1116 else if (!is_gimple_reg_type (f1->type)
1117 && is_gimple_reg_type (f2->type))
1119 else if (is_gimple_reg_type (f1->type)
1120 && !is_gimple_reg_type (f2->type))
1122 /* Put any complex or vector type before any other scalar type. */
1123 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1124 && TREE_CODE (f1->type) != VECTOR_TYPE
1125 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1126 || TREE_CODE (f2->type) == VECTOR_TYPE))
1128 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1129 || TREE_CODE (f1->type) == VECTOR_TYPE)
1130 && TREE_CODE (f2->type) != COMPLEX_TYPE
1131 && TREE_CODE (f2->type) != VECTOR_TYPE)
1133 /* Put the integral type with the bigger precision first. */
1134 else if (INTEGRAL_TYPE_P (f1->type)
1135 && INTEGRAL_TYPE_P (f2->type))
1136 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1137 /* Put any integral type with non-full precision last. */
1138 else if (INTEGRAL_TYPE_P (f1->type)
1139 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1140 != TYPE_PRECISION (f1->type)))
1142 else if (INTEGRAL_TYPE_P (f2->type)
1143 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1144 != TYPE_PRECISION (f2->type)))
1146 /* Stabilize the sort. */
1147 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1150 /* We want the bigger accesses first, thus the opposite operator in the next
1152 return f1->size > f2->size ? -1 : 1;
1156 /* Append a name of the declaration to the name obstack. A helper function for
1160 make_fancy_decl_name (tree decl)
1164 tree name = DECL_NAME (decl);
1166 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1167 IDENTIFIER_LENGTH (name));
1170 sprintf (buffer, "D%u", DECL_UID (decl));
1171 obstack_grow (&name_obstack, buffer, strlen (buffer));
1175 /* Helper for make_fancy_name. */
1178 make_fancy_name_1 (tree expr)
1185 make_fancy_decl_name (expr);
1189 switch (TREE_CODE (expr))
1192 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1193 obstack_1grow (&name_obstack, '$');
1194 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1198 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1199 obstack_1grow (&name_obstack, '$');
1200 /* Arrays with only one element may not have a constant as their
1202 index = TREE_OPERAND (expr, 1);
1203 if (TREE_CODE (index) != INTEGER_CST)
1205 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1206 obstack_grow (&name_obstack, buffer, strlen (buffer));
1213 gcc_unreachable (); /* we treat these as scalars. */
1220 /* Create a human readable name for replacement variable of ACCESS. */
1223 make_fancy_name (tree expr)
1225 make_fancy_name_1 (expr);
1226 obstack_1grow (&name_obstack, '\0');
1227 return XOBFINISH (&name_obstack, char *);
1230 /* Helper function for build_ref_for_offset. */
1233 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1239 tree tr_size, index, minidx;
1240 HOST_WIDE_INT el_size;
1242 if (offset == 0 && exp_type
1243 && types_compatible_p (exp_type, type))
1246 switch (TREE_CODE (type))
1249 case QUAL_UNION_TYPE:
1251 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1253 HOST_WIDE_INT pos, size;
1254 tree expr, *expr_ptr;
1256 if (TREE_CODE (fld) != FIELD_DECL)
1259 pos = int_bit_position (fld);
1260 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1261 tr_size = DECL_SIZE (fld);
1262 if (!tr_size || !host_integerp (tr_size, 1))
1264 size = tree_low_cst (tr_size, 1);
1265 if (pos > offset || (pos + size) <= offset)
1270 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1276 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1277 offset - pos, exp_type))
1287 tr_size = TYPE_SIZE (TREE_TYPE (type));
1288 if (!tr_size || !host_integerp (tr_size, 1))
1290 el_size = tree_low_cst (tr_size, 1);
1292 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1293 if (TREE_CODE (minidx) != INTEGER_CST)
1297 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1298 if (!integer_zerop (minidx))
1299 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1300 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1301 NULL_TREE, NULL_TREE);
1303 offset = offset % el_size;
1304 type = TREE_TYPE (type);
1319 /* Construct an expression that would reference a part of aggregate *EXPR of
1320 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1321 function only determines whether it can build such a reference without
1322 actually doing it, otherwise, the tree it points to is unshared first and
1323 then used as a base for furhter sub-references.
1325 FIXME: Eventually this should be replaced with
1326 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1327 minor rewrite of fold_stmt.
1331 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1332 tree exp_type, bool allow_ptr)
1334 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1337 *expr = unshare_expr (*expr);
1339 if (allow_ptr && POINTER_TYPE_P (type))
1341 type = TREE_TYPE (type);
1343 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1346 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1349 /* Return true iff TYPE is stdarg va_list type. */
1352 is_va_list_type (tree type)
1354 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1357 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1358 those with type which is suitable for scalarization. */
1361 find_var_candidates (void)
1364 referenced_var_iterator rvi;
1367 FOR_EACH_REFERENCED_VAR (var, rvi)
1369 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1371 type = TREE_TYPE (var);
1373 if (!AGGREGATE_TYPE_P (type)
1374 || needs_to_live_in_memory (var)
1375 || TREE_THIS_VOLATILE (var)
1376 || !COMPLETE_TYPE_P (type)
1377 || !host_integerp (TYPE_SIZE (type), 1)
1378 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1379 || type_internals_preclude_sra_p (type)
1380 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1381 we also want to schedule it rather late. Thus we ignore it in
1383 || (sra_mode == SRA_MODE_EARLY_INTRA
1384 && is_va_list_type (type)))
1387 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1389 if (dump_file && (dump_flags & TDF_DETAILS))
1391 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1392 print_generic_expr (dump_file, var, 0);
1393 fprintf (dump_file, "\n");
1401 /* Sort all accesses for the given variable, check for partial overlaps and
1402 return NULL if there are any. If there are none, pick a representative for
1403 each combination of offset and size and create a linked list out of them.
1404 Return the pointer to the first representative and make sure it is the first
1405 one in the vector of accesses. */
1407 static struct access *
1408 sort_and_splice_var_accesses (tree var)
1410 int i, j, access_count;
1411 struct access *res, **prev_acc_ptr = &res;
1412 VEC (access_p, heap) *access_vec;
1414 HOST_WIDE_INT low = -1, high = 0;
1416 access_vec = get_base_access_vector (var);
1419 access_count = VEC_length (access_p, access_vec);
1421 /* Sort by <OFFSET, SIZE>. */
1422 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1423 compare_access_positions);
1426 while (i < access_count)
1428 struct access *access = VEC_index (access_p, access_vec, i);
1429 bool grp_write = access->write;
1430 bool grp_read = !access->write;
1431 bool multiple_reads = false;
1432 bool grp_partial_lhs = access->grp_partial_lhs;
1433 bool first_scalar = is_gimple_reg_type (access->type);
1434 bool unscalarizable_region = access->grp_unscalarizable_region;
1436 if (first || access->offset >= high)
1439 low = access->offset;
1440 high = access->offset + access->size;
1442 else if (access->offset > low && access->offset + access->size > high)
1445 gcc_assert (access->offset >= low
1446 && access->offset + access->size <= high);
1449 while (j < access_count)
1451 struct access *ac2 = VEC_index (access_p, access_vec, j);
1452 if (ac2->offset != access->offset || ac2->size != access->size)
1459 multiple_reads = true;
1463 grp_partial_lhs |= ac2->grp_partial_lhs;
1464 unscalarizable_region |= ac2->grp_unscalarizable_region;
1465 relink_to_new_repr (access, ac2);
1467 /* If there are both aggregate-type and scalar-type accesses with
1468 this combination of size and offset, the comparison function
1469 should have put the scalars first. */
1470 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1471 ac2->group_representative = access;
1477 access->group_representative = access;
1478 access->grp_write = grp_write;
1479 access->grp_read = grp_read;
1480 access->grp_hint = multiple_reads;
1481 access->grp_partial_lhs = grp_partial_lhs;
1482 access->grp_unscalarizable_region = unscalarizable_region;
1483 if (access->first_link)
1484 add_access_to_work_queue (access);
1486 *prev_acc_ptr = access;
1487 prev_acc_ptr = &access->next_grp;
1490 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1494 /* Create a variable for the given ACCESS which determines the type, name and a
1495 few other properties. Return the variable declaration and store it also to
1496 ACCESS->replacement. */
1499 create_access_replacement (struct access *access)
1503 repl = create_tmp_var (access->type, "SR");
1505 add_referenced_var (repl);
1506 mark_sym_for_renaming (repl);
1508 if (!access->grp_partial_lhs
1509 && (TREE_CODE (access->type) == COMPLEX_TYPE
1510 || TREE_CODE (access->type) == VECTOR_TYPE))
1511 DECL_GIMPLE_REG_P (repl) = 1;
1513 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1514 DECL_ARTIFICIAL (repl) = 1;
1516 if (DECL_NAME (access->base)
1517 && !DECL_IGNORED_P (access->base)
1518 && !DECL_ARTIFICIAL (access->base))
1520 char *pretty_name = make_fancy_name (access->expr);
1522 DECL_NAME (repl) = get_identifier (pretty_name);
1523 obstack_free (&name_obstack, pretty_name);
1525 SET_DECL_DEBUG_EXPR (repl, access->expr);
1526 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1527 DECL_IGNORED_P (repl) = 0;
1530 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1531 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1535 fprintf (dump_file, "Created a replacement for ");
1536 print_generic_expr (dump_file, access->base, 0);
1537 fprintf (dump_file, " offset: %u, size: %u: ",
1538 (unsigned) access->offset, (unsigned) access->size);
1539 print_generic_expr (dump_file, repl, 0);
1540 fprintf (dump_file, "\n");
1542 sra_stats.replacements++;
1547 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1550 get_access_replacement (struct access *access)
1552 gcc_assert (access->grp_to_be_replaced);
1554 if (!access->replacement_decl)
1555 access->replacement_decl = create_access_replacement (access);
1556 return access->replacement_decl;
1559 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1560 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1561 to it is not "within" the root. */
1564 build_access_subtree (struct access **access)
1566 struct access *root = *access, *last_child = NULL;
1567 HOST_WIDE_INT limit = root->offset + root->size;
1569 *access = (*access)->next_grp;
1570 while (*access && (*access)->offset + (*access)->size <= limit)
1573 root->first_child = *access;
1575 last_child->next_sibling = *access;
1576 last_child = *access;
1578 build_access_subtree (access);
1582 /* Build a tree of access representatives, ACCESS is the pointer to the first
1583 one, others are linked in a list by the next_grp field. Decide about scalar
1584 replacements on the way, return true iff any are to be created. */
1587 build_access_trees (struct access *access)
1591 struct access *root = access;
1593 build_access_subtree (&access);
1594 root->next_grp = access;
1598 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1602 expr_with_var_bounded_array_refs_p (tree expr)
1604 while (handled_component_p (expr))
1606 if (TREE_CODE (expr) == ARRAY_REF
1607 && !host_integerp (array_ref_low_bound (expr), 0))
1609 expr = TREE_OPERAND (expr, 0);
1614 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1615 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1616 all sorts of access flags appropriately along the way, notably always ser
1617 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1620 analyze_access_subtree (struct access *root, bool allow_replacements,
1621 bool mark_read, bool mark_write)
1623 struct access *child;
1624 HOST_WIDE_INT limit = root->offset + root->size;
1625 HOST_WIDE_INT covered_to = root->offset;
1626 bool scalar = is_gimple_reg_type (root->type);
1627 bool hole = false, sth_created = false;
1628 bool direct_read = root->grp_read;
1631 root->grp_read = true;
1632 else if (root->grp_read)
1636 root->grp_write = true;
1637 else if (root->grp_write)
1640 if (root->grp_unscalarizable_region)
1641 allow_replacements = false;
1643 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1644 allow_replacements = false;
1646 for (child = root->first_child; child; child = child->next_sibling)
1648 if (!hole && child->offset < covered_to)
1651 covered_to += child->size;
1653 sth_created |= analyze_access_subtree (child, allow_replacements,
1654 mark_read, mark_write);
1656 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1657 hole |= !child->grp_covered;
1660 if (allow_replacements && scalar && !root->first_child
1662 || (direct_read && root->grp_write)))
1664 if (dump_file && (dump_flags & TDF_DETAILS))
1666 fprintf (dump_file, "Marking ");
1667 print_generic_expr (dump_file, root->base, 0);
1668 fprintf (dump_file, " offset: %u, size: %u: ",
1669 (unsigned) root->offset, (unsigned) root->size);
1670 fprintf (dump_file, " to be replaced.\n");
1673 root->grp_to_be_replaced = 1;
1677 else if (covered_to < limit)
1680 if (sth_created && !hole)
1682 root->grp_covered = 1;
1685 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1686 root->grp_unscalarized_data = 1; /* not covered and written to */
1692 /* Analyze all access trees linked by next_grp by the means of
1693 analyze_access_subtree. */
1695 analyze_access_trees (struct access *access)
1701 if (analyze_access_subtree (access, true, false, false))
1703 access = access->next_grp;
1709 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1710 SIZE would conflict with an already existing one. If exactly such a child
1711 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1714 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1715 HOST_WIDE_INT size, struct access **exact_match)
1717 struct access *child;
1719 for (child = lacc->first_child; child; child = child->next_sibling)
1721 if (child->offset == norm_offset && child->size == size)
1723 *exact_match = child;
1727 if (child->offset < norm_offset + size
1728 && child->offset + child->size > norm_offset)
1735 /* Create a new child access of PARENT, with all properties just like MODEL
1736 except for its offset and with its grp_write false and grp_read true.
1737 Return the new access or NULL if it cannot be created. Note that this access
1738 is created long after all splicing and sorting, it's not located in any
1739 access vector and is automatically a representative of its group. */
1741 static struct access *
1742 create_artificial_child_access (struct access *parent, struct access *model,
1743 HOST_WIDE_INT new_offset)
1745 struct access *access;
1746 struct access **child;
1747 tree expr = parent->base;;
1749 gcc_assert (!model->grp_unscalarizable_region);
1751 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1752 model->type, false))
1755 access = (struct access *) pool_alloc (access_pool);
1756 memset (access, 0, sizeof (struct access));
1757 access->base = parent->base;
1758 access->expr = expr;
1759 access->offset = new_offset;
1760 access->size = model->size;
1761 access->type = model->type;
1762 access->grp_write = true;
1763 access->grp_read = false;
1765 child = &parent->first_child;
1766 while (*child && (*child)->offset < new_offset)
1767 child = &(*child)->next_sibling;
1769 access->next_sibling = *child;
1776 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1777 true if any new subaccess was created. Additionally, if RACC is a scalar
1778 access but LACC is not, change the type of the latter, if possible. */
1781 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1783 struct access *rchild;
1784 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1787 if (is_gimple_reg_type (lacc->type)
1788 || lacc->grp_unscalarizable_region
1789 || racc->grp_unscalarizable_region)
1792 if (!lacc->first_child && !racc->first_child
1793 && is_gimple_reg_type (racc->type))
1795 tree t = lacc->base;
1797 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1801 lacc->type = racc->type;
1806 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1808 struct access *new_acc = NULL;
1809 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1811 if (rchild->grp_unscalarizable_region)
1814 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1819 rchild->grp_hint = 1;
1820 new_acc->grp_hint |= new_acc->grp_read;
1821 if (rchild->first_child)
1822 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1827 /* If a (part of) a union field is on the RHS of an assignment, it can
1828 have sub-accesses which do not make sense on the LHS (PR 40351).
1829 Check that this is not the case. */
1830 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1831 rchild->type, false))
1834 rchild->grp_hint = 1;
1835 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1839 if (racc->first_child)
1840 propagate_subaccesses_across_link (new_acc, rchild);
1847 /* Propagate all subaccesses across assignment links. */
1850 propagate_all_subaccesses (void)
1852 while (work_queue_head)
1854 struct access *racc = pop_access_from_work_queue ();
1855 struct assign_link *link;
1857 gcc_assert (racc->first_link);
1859 for (link = racc->first_link; link; link = link->next)
1861 struct access *lacc = link->lacc;
1863 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1865 lacc = lacc->group_representative;
1866 if (propagate_subaccesses_across_link (lacc, racc)
1867 && lacc->first_link)
1868 add_access_to_work_queue (lacc);
1873 /* Go through all accesses collected throughout the (intraprocedural) analysis
1874 stage, exclude overlapping ones, identify representatives and build trees
1875 out of them, making decisions about scalarization on the way. Return true
1876 iff there are any to-be-scalarized variables after this stage. */
1879 analyze_all_variable_accesses (void)
1882 bitmap tmp = BITMAP_ALLOC (NULL);
1886 bitmap_copy (tmp, candidate_bitmap);
1887 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1889 tree var = referenced_var (i);
1890 struct access *access;
1892 access = sort_and_splice_var_accesses (var);
1894 build_access_trees (access);
1896 disqualify_candidate (var,
1897 "No or inhibitingly overlapping accesses.");
1900 propagate_all_subaccesses ();
1902 bitmap_copy (tmp, candidate_bitmap);
1903 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1905 tree var = referenced_var (i);
1906 struct access *access = get_first_repr_for_decl (var);
1908 if (analyze_access_trees (access))
1911 if (dump_file && (dump_flags & TDF_DETAILS))
1913 fprintf (dump_file, "\nAccess trees for ");
1914 print_generic_expr (dump_file, var, 0);
1915 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1916 dump_access_tree (dump_file, access);
1917 fprintf (dump_file, "\n");
1921 disqualify_candidate (var, "No scalar replacements to be created.");
1928 statistics_counter_event (cfun, "Scalarized aggregates", res);
1935 /* Return true iff a reference statement into aggregate AGG can be built for
1936 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1937 or a child of its sibling. TOP_OFFSET is the offset from the processed
1938 access subtree that has to be subtracted from offset of each access. */
1941 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1942 HOST_WIDE_INT top_offset)
1946 if (access->grp_to_be_replaced
1947 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1948 access->offset - top_offset,
1949 access->type, false))
1952 if (access->first_child
1953 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1957 access = access->next_sibling;
1964 /* Generate statements copying scalar replacements of accesses within a subtree
1965 into or out of AGG. ACCESS is the first child of the root of the subtree to
1966 be processed. AGG is an aggregate type expression (can be a declaration but
1967 does not have to be, it can for example also be an indirect_ref).
1968 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1969 from offsets of individual accesses to get corresponding offsets for AGG.
1970 If CHUNK_SIZE is non-null, copy only replacements in the interval
1971 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1972 statement iterator used to place the new statements. WRITE should be true
1973 when the statements should write from AGG to the replacement and false if
1974 vice versa. if INSERT_AFTER is true, new statements will be added after the
1975 current statement in GSI, they will be added before the statement
1979 generate_subtree_copies (struct access *access, tree agg,
1980 HOST_WIDE_INT top_offset,
1981 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1982 gimple_stmt_iterator *gsi, bool write,
1989 if (chunk_size && access->offset >= start_offset + chunk_size)
1992 if (access->grp_to_be_replaced
1994 || access->offset + access->size > start_offset))
1996 tree repl = get_access_replacement (access);
2000 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2001 access->offset - top_offset,
2002 access->type, false);
2003 gcc_assert (ref_found);
2007 if (access->grp_partial_lhs)
2008 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2010 insert_after ? GSI_NEW_STMT
2012 stmt = gimple_build_assign (repl, expr);
2016 TREE_NO_WARNING (repl) = 1;
2017 if (access->grp_partial_lhs)
2018 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2020 insert_after ? GSI_NEW_STMT
2022 stmt = gimple_build_assign (expr, repl);
2026 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2028 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2030 sra_stats.subtree_copies++;
2033 if (access->first_child)
2034 generate_subtree_copies (access->first_child, agg, top_offset,
2035 start_offset, chunk_size, gsi,
2036 write, insert_after);
2038 access = access->next_sibling;
2043 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2044 the root of the subtree to be processed. GSI is the statement iterator used
2045 for inserting statements which are added after the current statement if
2046 INSERT_AFTER is true or before it otherwise. */
2049 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2053 struct access *child;
2055 if (access->grp_to_be_replaced)
2059 stmt = gimple_build_assign (get_access_replacement (access),
2060 fold_convert (access->type,
2061 integer_zero_node));
2063 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2065 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2069 for (child = access->first_child; child; child = child->next_sibling)
2070 init_subtree_with_zero (child, gsi, insert_after);
2073 /* Search for an access representative for the given expression EXPR and
2074 return it or NULL if it cannot be found. */
2076 static struct access *
2077 get_access_for_expr (tree expr)
2079 HOST_WIDE_INT offset, size, max_size;
2082 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2083 a different size than the size of its argument and we need the latter
2085 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2086 expr = TREE_OPERAND (expr, 0);
2088 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2089 if (max_size == -1 || !DECL_P (base))
2092 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2095 return get_var_base_offset_size_access (base, offset, max_size);
2098 /* Callback for scan_function. Replace the expression EXPR with a scalar
2099 replacement if there is one and generate other statements to do type
2100 conversion or subtree copying if necessary. GSI is used to place newly
2101 created statements, WRITE is true if the expression is being written to (it
2102 is on a LHS of a statement or output in an assembly statement). */
2105 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2106 void *data ATTRIBUTE_UNUSED)
2108 struct access *access;
2111 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2114 expr = &TREE_OPERAND (*expr, 0);
2119 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2120 expr = &TREE_OPERAND (*expr, 0);
2121 access = get_access_for_expr (*expr);
2124 type = TREE_TYPE (*expr);
2126 if (access->grp_to_be_replaced)
2128 tree repl = get_access_replacement (access);
2129 /* If we replace a non-register typed access simply use the original
2130 access expression to extract the scalar component afterwards.
2131 This happens if scalarizing a function return value or parameter
2132 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2133 gcc.c-torture/compile/20011217-1.c.
2135 We also want to use this when accessing a complex or vector which can
2136 be accessed as a different type too, potentially creating a need for
2137 type conversion (see PR42196) and when scalarized unions are involved
2138 in assembler statements (see PR42398). */
2139 if (!useless_type_conversion_p (type, access->type))
2141 tree ref = access->base;
2144 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2145 access->offset, access->type, false);
2152 if (access->grp_partial_lhs)
2153 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2154 false, GSI_NEW_STMT);
2155 stmt = gimple_build_assign (repl, ref);
2156 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2162 if (access->grp_partial_lhs)
2163 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2164 true, GSI_SAME_STMT);
2165 stmt = gimple_build_assign (ref, repl);
2166 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2174 if (access->first_child)
2176 HOST_WIDE_INT start_offset, chunk_size;
2178 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2179 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2181 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2182 start_offset = access->offset
2183 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2186 start_offset = chunk_size = 0;
2188 generate_subtree_copies (access->first_child, access->base, 0,
2189 start_offset, chunk_size, gsi, write, write);
2194 /* Where scalar replacements of the RHS have been written to when a replacement
2195 of a LHS of an assigments cannot be direclty loaded from a replacement of
2197 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2198 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2199 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2201 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2202 base aggregate if there are unscalarized data or directly to LHS
2205 static enum unscalarized_data_handling
2206 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2207 gimple_stmt_iterator *gsi)
2209 if (top_racc->grp_unscalarized_data)
2211 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2213 return SRA_UDH_RIGHT;
2217 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2218 0, 0, gsi, false, false);
2219 return SRA_UDH_LEFT;
2224 /* Try to generate statements to load all sub-replacements in an access
2225 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2226 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2227 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2228 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2229 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2230 the rhs top aggregate has already been refreshed by contents of its scalar
2231 reductions and is set to true if this function has to do it. */
2234 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2235 HOST_WIDE_INT left_offset,
2236 HOST_WIDE_INT right_offset,
2237 gimple_stmt_iterator *old_gsi,
2238 gimple_stmt_iterator *new_gsi,
2239 enum unscalarized_data_handling *refreshed,
2242 location_t loc = EXPR_LOCATION (lacc->expr);
2245 if (lacc->grp_to_be_replaced)
2247 struct access *racc;
2248 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2252 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2253 if (racc && racc->grp_to_be_replaced)
2255 rhs = get_access_replacement (racc);
2256 if (!useless_type_conversion_p (lacc->type, racc->type))
2257 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2261 /* No suitable access on the right hand side, need to load from
2262 the aggregate. See if we have to update it first... */
2263 if (*refreshed == SRA_UDH_NONE)
2264 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2267 if (*refreshed == SRA_UDH_LEFT)
2272 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2273 lacc->offset, lacc->type,
2275 gcc_assert (repl_found);
2281 rhs = top_racc->base;
2282 repl_found = build_ref_for_offset (&rhs,
2283 TREE_TYPE (top_racc->base),
2284 offset, lacc->type, false);
2285 gcc_assert (repl_found);
2289 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2290 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2292 sra_stats.subreplacements++;
2294 else if (*refreshed == SRA_UDH_NONE
2295 && lacc->grp_read && !lacc->grp_covered)
2296 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2299 if (lacc->first_child)
2300 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2301 left_offset, right_offset,
2302 old_gsi, new_gsi, refreshed, lhs);
2303 lacc = lacc->next_sibling;
2308 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2309 to the assignment and GSI is the statement iterator pointing at it. Returns
2310 the same values as sra_modify_assign. */
2312 static enum scan_assign_result
2313 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2315 tree lhs = gimple_assign_lhs (*stmt);
2318 acc = get_access_for_expr (lhs);
2322 if (VEC_length (constructor_elt,
2323 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2325 /* I have never seen this code path trigger but if it can happen the
2326 following should handle it gracefully. */
2327 if (access_has_children_p (acc))
2328 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2330 return SRA_SA_PROCESSED;
2333 if (acc->grp_covered)
2335 init_subtree_with_zero (acc, gsi, false);
2336 unlink_stmt_vdef (*stmt);
2337 gsi_remove (gsi, true);
2338 return SRA_SA_REMOVED;
2342 init_subtree_with_zero (acc, gsi, true);
2343 return SRA_SA_PROCESSED;
2348 /* Callback of scan_function to process assign statements. It examines both
2349 sides of the statement, replaces them with a scalare replacement if there is
2350 one and generating copying of replacements if scalarized aggregates have been
2351 used in the assignment. STMT is a pointer to the assign statement, GSI is
2352 used to hold generated statements for type conversions and subtree
2355 static enum scan_assign_result
2356 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2357 void *data ATTRIBUTE_UNUSED)
2359 struct access *lacc, *racc;
2361 bool modify_this_stmt = false;
2362 bool force_gimple_rhs = false;
2363 location_t loc = gimple_location (*stmt);
2365 if (!gimple_assign_single_p (*stmt))
2367 lhs = gimple_assign_lhs (*stmt);
2368 rhs = gimple_assign_rhs1 (*stmt);
2370 if (TREE_CODE (rhs) == CONSTRUCTOR)
2371 return sra_modify_constructor_assign (stmt, gsi);
2373 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2374 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2375 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2377 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2379 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2381 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2384 lacc = get_access_for_expr (lhs);
2385 racc = get_access_for_expr (rhs);
2389 if (lacc && lacc->grp_to_be_replaced)
2391 lhs = get_access_replacement (lacc);
2392 gimple_assign_set_lhs (*stmt, lhs);
2393 modify_this_stmt = true;
2394 if (lacc->grp_partial_lhs)
2395 force_gimple_rhs = true;
2399 if (racc && racc->grp_to_be_replaced)
2401 rhs = get_access_replacement (racc);
2402 modify_this_stmt = true;
2403 if (racc->grp_partial_lhs)
2404 force_gimple_rhs = true;
2408 if (modify_this_stmt)
2410 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2412 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2413 ??? This should move to fold_stmt which we simply should
2414 call after building a VIEW_CONVERT_EXPR here. */
2415 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2416 && !access_has_children_p (lacc))
2419 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2420 TREE_TYPE (rhs), false))
2423 gimple_assign_set_lhs (*stmt, expr);
2426 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2427 && !access_has_children_p (racc))
2430 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2431 TREE_TYPE (lhs), false))
2434 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2436 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2437 if (is_gimple_reg_type (TREE_TYPE (lhs))
2438 && TREE_CODE (lhs) != SSA_NAME)
2439 force_gimple_rhs = true;
2443 if (force_gimple_rhs)
2444 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2445 true, GSI_SAME_STMT);
2446 if (gimple_assign_rhs1 (*stmt) != rhs)
2448 gimple_assign_set_rhs_from_tree (gsi, rhs);
2449 gcc_assert (*stmt == gsi_stmt (*gsi));
2453 /* From this point on, the function deals with assignments in between
2454 aggregates when at least one has scalar reductions of some of its
2455 components. There are three possible scenarios: Both the LHS and RHS have
2456 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2458 In the first case, we would like to load the LHS components from RHS
2459 components whenever possible. If that is not possible, we would like to
2460 read it directly from the RHS (after updating it by storing in it its own
2461 components). If there are some necessary unscalarized data in the LHS,
2462 those will be loaded by the original assignment too. If neither of these
2463 cases happen, the original statement can be removed. Most of this is done
2464 by load_assign_lhs_subreplacements.
2466 In the second case, we would like to store all RHS scalarized components
2467 directly into LHS and if they cover the aggregate completely, remove the
2468 statement too. In the third case, we want the LHS components to be loaded
2469 directly from the RHS (DSE will remove the original statement if it
2472 This is a bit complex but manageable when types match and when unions do
2473 not cause confusion in a way that we cannot really load a component of LHS
2474 from the RHS or vice versa (the access representing this level can have
2475 subaccesses that are accessible only through a different union field at a
2476 higher level - different from the one used in the examined expression).
2479 Therefore, I specially handle a fourth case, happening when there is a
2480 specific type cast or it is impossible to locate a scalarized subaccess on
2481 the other side of the expression. If that happens, I simply "refresh" the
2482 RHS by storing in it is scalarized components leave the original statement
2483 there to do the copying and then load the scalar replacements of the LHS.
2484 This is what the first branch does. */
2486 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2487 || (access_has_children_p (racc)
2488 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2489 || (access_has_children_p (lacc)
2490 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2492 if (access_has_children_p (racc))
2493 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2495 if (access_has_children_p (lacc))
2496 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2498 sra_stats.separate_lhs_rhs_handling++;
2502 if (access_has_children_p (lacc) && access_has_children_p (racc))
2504 gimple_stmt_iterator orig_gsi = *gsi;
2505 enum unscalarized_data_handling refreshed;
2507 if (lacc->grp_read && !lacc->grp_covered)
2508 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2510 refreshed = SRA_UDH_NONE;
2512 load_assign_lhs_subreplacements (lacc->first_child, racc,
2513 lacc->offset, racc->offset,
2514 &orig_gsi, gsi, &refreshed, lhs);
2515 if (refreshed != SRA_UDH_RIGHT)
2517 if (*stmt == gsi_stmt (*gsi))
2520 unlink_stmt_vdef (*stmt);
2521 gsi_remove (&orig_gsi, true);
2522 sra_stats.deleted++;
2523 return SRA_SA_REMOVED;
2528 if (access_has_children_p (racc))
2530 if (!racc->grp_unscalarized_data)
2532 generate_subtree_copies (racc->first_child, lhs,
2533 racc->offset, 0, 0, gsi,
2535 gcc_assert (*stmt == gsi_stmt (*gsi));
2536 unlink_stmt_vdef (*stmt);
2537 gsi_remove (gsi, true);
2538 sra_stats.deleted++;
2539 return SRA_SA_REMOVED;
2542 generate_subtree_copies (racc->first_child, lhs,
2543 racc->offset, 0, 0, gsi, false, true);
2545 else if (access_has_children_p (lacc))
2546 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2547 0, 0, gsi, true, true);
2550 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2553 /* Generate statements initializing scalar replacements of parts of function
2557 initialize_parameter_reductions (void)
2559 gimple_stmt_iterator gsi;
2560 gimple_seq seq = NULL;
2563 for (parm = DECL_ARGUMENTS (current_function_decl);
2565 parm = TREE_CHAIN (parm))
2567 VEC (access_p, heap) *access_vec;
2568 struct access *access;
2570 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2572 access_vec = get_base_access_vector (parm);
2578 seq = gimple_seq_alloc ();
2579 gsi = gsi_start (seq);
2582 for (access = VEC_index (access_p, access_vec, 0);
2584 access = access->next_grp)
2585 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2589 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2592 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2593 it reveals there are components of some aggregates to be scalarized, it runs
2594 the required transformations. */
2596 perform_intra_sra (void)
2601 if (!find_var_candidates ())
2604 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2608 if (!analyze_all_variable_accesses ())
2611 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2612 initialize_parameter_reductions ();
2614 statistics_counter_event (cfun, "Scalar replacements created",
2615 sra_stats.replacements);
2616 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2617 statistics_counter_event (cfun, "Subtree copy stmts",
2618 sra_stats.subtree_copies);
2619 statistics_counter_event (cfun, "Subreplacement stmts",
2620 sra_stats.subreplacements);
2621 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2622 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2623 sra_stats.separate_lhs_rhs_handling);
2625 ret = TODO_update_ssa;
2628 sra_deinitialize ();
2632 /* Perform early intraprocedural SRA. */
2634 early_intra_sra (void)
2636 sra_mode = SRA_MODE_EARLY_INTRA;
2637 return perform_intra_sra ();
2640 /* Perform "late" intraprocedural SRA. */
2642 late_intra_sra (void)
2644 sra_mode = SRA_MODE_INTRA;
2645 return perform_intra_sra ();
2650 gate_intra_sra (void)
2652 return flag_tree_sra != 0;
2656 struct gimple_opt_pass pass_sra_early =
2661 gate_intra_sra, /* gate */
2662 early_intra_sra, /* execute */
2665 0, /* static_pass_number */
2666 TV_TREE_SRA, /* tv_id */
2667 PROP_cfg | PROP_ssa, /* properties_required */
2668 0, /* properties_provided */
2669 0, /* properties_destroyed */
2670 0, /* todo_flags_start */
2674 | TODO_verify_ssa /* todo_flags_finish */
2678 struct gimple_opt_pass pass_sra =
2683 gate_intra_sra, /* gate */
2684 late_intra_sra, /* execute */
2687 0, /* static_pass_number */
2688 TV_TREE_SRA, /* tv_id */
2689 PROP_cfg | PROP_ssa, /* properties_required */
2690 0, /* properties_provided */
2691 0, /* properties_destroyed */
2692 TODO_update_address_taken, /* todo_flags_start */
2696 | TODO_verify_ssa /* todo_flags_finish */
2701 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2705 is_unused_scalar_param (tree parm)
2708 return (is_gimple_reg (parm)
2709 && (!(name = gimple_default_def (cfun, parm))
2710 || has_zero_uses (name)));
2713 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2714 examine whether there are any direct or otherwise infeasible ones. If so,
2715 return true, otherwise return false. PARM must be a gimple register with a
2716 non-NULL default definition. */
2719 ptr_parm_has_direct_uses (tree parm)
2721 imm_use_iterator ui;
2723 tree name = gimple_default_def (cfun, parm);
2726 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2728 if (gimple_assign_single_p (stmt))
2730 tree rhs = gimple_assign_rhs1 (stmt);
2733 else if (TREE_CODE (rhs) == ADDR_EXPR)
2737 rhs = TREE_OPERAND (rhs, 0);
2739 while (handled_component_p (rhs));
2740 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2744 else if (gimple_code (stmt) == GIMPLE_RETURN)
2746 tree t = gimple_return_retval (stmt);
2750 else if (is_gimple_call (stmt))
2753 for (i = 0; i < gimple_call_num_args (stmt); i++)
2755 tree arg = gimple_call_arg (stmt, i);
2763 else if (!is_gimple_debug (stmt))
2767 BREAK_FROM_IMM_USE_STMT (ui);
2773 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2774 them in candidate_bitmap. Note that these do not necessarily include
2775 parameter which are unused and thus can be removed. Return true iff any
2776 such candidate has been found. */
2779 find_param_candidates (void)
2785 for (parm = DECL_ARGUMENTS (current_function_decl);
2787 parm = TREE_CHAIN (parm))
2789 tree type = TREE_TYPE (parm);
2793 if (TREE_THIS_VOLATILE (parm)
2794 || TREE_ADDRESSABLE (parm)
2795 || is_va_list_type (type))
2798 if (is_unused_scalar_param (parm))
2804 if (POINTER_TYPE_P (type))
2806 type = TREE_TYPE (type);
2808 if (TREE_CODE (type) == FUNCTION_TYPE
2809 || TYPE_VOLATILE (type)
2810 || !is_gimple_reg (parm)
2811 || is_va_list_type (type)
2812 || ptr_parm_has_direct_uses (parm))
2815 else if (!AGGREGATE_TYPE_P (type))
2818 if (!COMPLETE_TYPE_P (type)
2819 || !host_integerp (TYPE_SIZE (type), 1)
2820 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2821 || (AGGREGATE_TYPE_P (type)
2822 && type_internals_preclude_sra_p (type)))
2825 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2827 if (dump_file && (dump_flags & TDF_DETAILS))
2829 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2830 print_generic_expr (dump_file, parm, 0);
2831 fprintf (dump_file, "\n");
2835 func_param_count = count;
2839 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2843 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2846 struct access *repr = (struct access *) data;
2848 repr->grp_maybe_modified = 1;
2852 /* Analyze what representatives (in linked lists accessible from
2853 REPRESENTATIVES) can be modified by side effects of statements in the
2854 current function. */
2857 analyze_modified_params (VEC (access_p, heap) *representatives)
2861 for (i = 0; i < func_param_count; i++)
2863 struct access *repr;
2865 for (repr = VEC_index (access_p, representatives, i);
2867 repr = repr->next_grp)
2869 struct access *access;
2873 if (no_accesses_p (repr))
2875 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
2876 || repr->grp_maybe_modified)
2879 ao_ref_init (&ar, repr->expr);
2880 visited = BITMAP_ALLOC (NULL);
2881 for (access = repr; access; access = access->next_sibling)
2883 /* All accesses are read ones, otherwise grp_maybe_modified would
2884 be trivially set. */
2885 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2886 mark_maybe_modified, repr, &visited);
2887 if (repr->grp_maybe_modified)
2890 BITMAP_FREE (visited);
2895 /* Propagate distances in bb_dereferences in the opposite direction than the
2896 control flow edges, in each step storing the maximum of the current value
2897 and the minimum of all successors. These steps are repeated until the table
2898 stabilizes. Note that BBs which might terminate the functions (according to
2899 final_bbs bitmap) never updated in this way. */
2902 propagate_dereference_distances (void)
2904 VEC (basic_block, heap) *queue;
2907 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2908 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2911 VEC_quick_push (basic_block, queue, bb);
2915 while (!VEC_empty (basic_block, queue))
2919 bool change = false;
2922 bb = VEC_pop (basic_block, queue);
2925 if (bitmap_bit_p (final_bbs, bb->index))
2928 for (i = 0; i < func_param_count; i++)
2930 int idx = bb->index * func_param_count + i;
2932 HOST_WIDE_INT inh = 0;
2934 FOR_EACH_EDGE (e, ei, bb->succs)
2936 int succ_idx = e->dest->index * func_param_count + i;
2938 if (e->src == EXIT_BLOCK_PTR)
2944 inh = bb_dereferences [succ_idx];
2946 else if (bb_dereferences [succ_idx] < inh)
2947 inh = bb_dereferences [succ_idx];
2950 if (!first && bb_dereferences[idx] < inh)
2952 bb_dereferences[idx] = inh;
2957 if (change && !bitmap_bit_p (final_bbs, bb->index))
2958 FOR_EACH_EDGE (e, ei, bb->preds)
2963 e->src->aux = e->src;
2964 VEC_quick_push (basic_block, queue, e->src);
2968 VEC_free (basic_block, heap, queue);
2971 /* Dump a dereferences TABLE with heading STR to file F. */
2974 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2978 fprintf (dump_file, str);
2979 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2981 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2982 if (bb != EXIT_BLOCK_PTR)
2985 for (i = 0; i < func_param_count; i++)
2987 int idx = bb->index * func_param_count + i;
2988 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
2993 fprintf (dump_file, "\n");
2996 /* Determine what (parts of) parameters passed by reference that are not
2997 assigned to are not certainly dereferenced in this function and thus the
2998 dereferencing cannot be safely moved to the caller without potentially
2999 introducing a segfault. Mark such REPRESENTATIVES as
3000 grp_not_necessarilly_dereferenced.
3002 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3003 part is calculated rather than simple booleans are calculated for each
3004 pointer parameter to handle cases when only a fraction of the whole
3005 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3008 The maximum dereference distances for each pointer parameter and BB are
3009 already stored in bb_dereference. This routine simply propagates these
3010 values upwards by propagate_dereference_distances and then compares the
3011 distances of individual parameters in the ENTRY BB to the equivalent
3012 distances of each representative of a (fraction of a) parameter. */
3015 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3019 if (dump_file && (dump_flags & TDF_DETAILS))
3020 dump_dereferences_table (dump_file,
3021 "Dereference table before propagation:\n",
3024 propagate_dereference_distances ();
3026 if (dump_file && (dump_flags & TDF_DETAILS))
3027 dump_dereferences_table (dump_file,
3028 "Dereference table after propagation:\n",
3031 for (i = 0; i < func_param_count; i++)
3033 struct access *repr = VEC_index (access_p, representatives, i);
3034 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3036 if (!repr || no_accesses_p (repr))
3041 if ((repr->offset + repr->size) > bb_dereferences[idx])
3042 repr->grp_not_necessarilly_dereferenced = 1;
3043 repr = repr->next_grp;
3049 /* Return the representative access for the parameter declaration PARM if it is
3050 a scalar passed by reference which is not written to and the pointer value
3051 is not used directly. Thus, if it is legal to dereference it in the caller
3052 and we can rule out modifications through aliases, such parameter should be
3053 turned into one passed by value. Return NULL otherwise. */
3055 static struct access *
3056 unmodified_by_ref_scalar_representative (tree parm)
3058 int i, access_count;
3059 struct access *repr;
3060 VEC (access_p, heap) *access_vec;
3062 access_vec = get_base_access_vector (parm);
3063 gcc_assert (access_vec);
3064 repr = VEC_index (access_p, access_vec, 0);
3067 repr->group_representative = repr;
3069 access_count = VEC_length (access_p, access_vec);
3070 for (i = 1; i < access_count; i++)
3072 struct access *access = VEC_index (access_p, access_vec, i);
3075 access->group_representative = repr;
3076 access->next_sibling = repr->next_sibling;
3077 repr->next_sibling = access;
3081 repr->grp_scalar_ptr = 1;
3085 /* Return true iff this access precludes IPA-SRA of the parameter it is
3089 access_precludes_ipa_sra_p (struct access *access)
3091 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3092 is incompatible assign in a call statement (and possibly even in asm
3093 statements). This can be relaxed by using a new temporary but only for
3094 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3095 intraprocedural SRA we deal with this by keeping the old aggregate around,
3096 something we cannot do in IPA-SRA.) */
3098 && (is_gimple_call (access->stmt)
3099 || gimple_code (access->stmt) == GIMPLE_ASM))
3106 /* Sort collected accesses for parameter PARM, identify representatives for
3107 each accessed region and link them together. Return NULL if there are
3108 different but overlapping accesses, return the special ptr value meaning
3109 there are no accesses for this parameter if that is the case and return the
3110 first representative otherwise. Set *RO_GRP if there is a group of accesses
3111 with only read (i.e. no write) accesses. */
3113 static struct access *
3114 splice_param_accesses (tree parm, bool *ro_grp)
3116 int i, j, access_count, group_count;
3117 int agg_size, total_size = 0;
3118 struct access *access, *res, **prev_acc_ptr = &res;
3119 VEC (access_p, heap) *access_vec;
3121 access_vec = get_base_access_vector (parm);
3123 return &no_accesses_representant;
3124 access_count = VEC_length (access_p, access_vec);
3126 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3127 compare_access_positions);
3132 while (i < access_count)
3135 access = VEC_index (access_p, access_vec, i);
3136 modification = access->write;
3137 if (access_precludes_ipa_sra_p (access))
3140 /* Access is about to become group representative unless we find some
3141 nasty overlap which would preclude us from breaking this parameter
3145 while (j < access_count)
3147 struct access *ac2 = VEC_index (access_p, access_vec, j);
3148 if (ac2->offset != access->offset)
3150 /* All or nothing law for parameters. */
3151 if (access->offset + access->size > ac2->offset)
3156 else if (ac2->size != access->size)
3159 if (access_precludes_ipa_sra_p (ac2))
3162 modification |= ac2->write;
3163 ac2->group_representative = access;
3164 ac2->next_sibling = access->next_sibling;
3165 access->next_sibling = ac2;
3170 access->grp_maybe_modified = modification;
3173 *prev_acc_ptr = access;
3174 prev_acc_ptr = &access->next_grp;
3175 total_size += access->size;
3179 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3180 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3182 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3183 if (total_size >= agg_size)
3186 gcc_assert (group_count > 0);
3190 /* Decide whether parameters with representative accesses given by REPR should
3191 be reduced into components. */
3194 decide_one_param_reduction (struct access *repr)
3196 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3201 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3202 gcc_assert (cur_parm_size > 0);
3204 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3207 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3212 agg_size = cur_parm_size;
3218 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3219 print_generic_expr (dump_file, parm, 0);
3220 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3221 for (acc = repr; acc; acc = acc->next_grp)
3222 dump_access (dump_file, acc, true);
3226 new_param_count = 0;
3228 for (; repr; repr = repr->next_grp)
3230 gcc_assert (parm == repr->base);
3233 if (!by_ref || (!repr->grp_maybe_modified
3234 && !repr->grp_not_necessarilly_dereferenced))
3235 total_size += repr->size;
3237 total_size += cur_parm_size;
3240 gcc_assert (new_param_count > 0);
3242 if (optimize_function_for_size_p (cfun))
3243 parm_size_limit = cur_parm_size;
3245 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3248 if (total_size < agg_size
3249 && total_size <= parm_size_limit)
3252 fprintf (dump_file, " ....will be split into %i components\n",
3254 return new_param_count;
3260 /* The order of the following enums is important, we need to do extra work for
3261 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3262 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3263 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3265 /* Identify representatives of all accesses to all candidate parameters for
3266 IPA-SRA. Return result based on what representatives have been found. */
3268 static enum ipa_splicing_result
3269 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3271 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3273 struct access *repr;
3275 *representatives = VEC_alloc (access_p, heap, func_param_count);
3277 for (parm = DECL_ARGUMENTS (current_function_decl);
3279 parm = TREE_CHAIN (parm))
3281 if (is_unused_scalar_param (parm))
3283 VEC_quick_push (access_p, *representatives,
3284 &no_accesses_representant);
3285 if (result == NO_GOOD_ACCESS)
3286 result = UNUSED_PARAMS;
3288 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3289 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3290 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3292 repr = unmodified_by_ref_scalar_representative (parm);
3293 VEC_quick_push (access_p, *representatives, repr);
3295 result = UNMODIF_BY_REF_ACCESSES;
3297 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3299 bool ro_grp = false;
3300 repr = splice_param_accesses (parm, &ro_grp);
3301 VEC_quick_push (access_p, *representatives, repr);
3303 if (repr && !no_accesses_p (repr))
3305 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3308 result = UNMODIF_BY_REF_ACCESSES;
3309 else if (result < MODIF_BY_REF_ACCESSES)
3310 result = MODIF_BY_REF_ACCESSES;
3312 else if (result < BY_VAL_ACCESSES)
3313 result = BY_VAL_ACCESSES;
3315 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3316 result = UNUSED_PARAMS;
3319 VEC_quick_push (access_p, *representatives, NULL);
3322 if (result == NO_GOOD_ACCESS)
3324 VEC_free (access_p, heap, *representatives);
3325 *representatives = NULL;
3326 return NO_GOOD_ACCESS;
3332 /* Return the index of BASE in PARMS. Abort if it is not found. */
3335 get_param_index (tree base, VEC(tree, heap) *parms)
3339 len = VEC_length (tree, parms);
3340 for (i = 0; i < len; i++)
3341 if (VEC_index (tree, parms, i) == base)
3346 /* Convert the decisions made at the representative level into compact
3347 parameter adjustments. REPRESENTATIVES are pointers to first
3348 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3349 final number of adjustments. */
3351 static ipa_parm_adjustment_vec
3352 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3353 int adjustments_count)
3355 VEC (tree, heap) *parms;
3356 ipa_parm_adjustment_vec adjustments;
3360 gcc_assert (adjustments_count > 0);
3361 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3362 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3363 parm = DECL_ARGUMENTS (current_function_decl);
3364 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3366 struct access *repr = VEC_index (access_p, representatives, i);
3368 if (!repr || no_accesses_p (repr))
3370 struct ipa_parm_adjustment *adj;
3372 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3373 memset (adj, 0, sizeof (*adj));
3374 adj->base_index = get_param_index (parm, parms);
3377 adj->copy_param = 1;
3379 adj->remove_param = 1;
3383 struct ipa_parm_adjustment *adj;
3384 int index = get_param_index (parm, parms);
3386 for (; repr; repr = repr->next_grp)
3388 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3389 memset (adj, 0, sizeof (*adj));
3390 gcc_assert (repr->base == parm);
3391 adj->base_index = index;
3392 adj->base = repr->base;
3393 adj->type = repr->type;
3394 adj->offset = repr->offset;
3395 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3396 && (repr->grp_maybe_modified
3397 || repr->grp_not_necessarilly_dereferenced));
3402 VEC_free (tree, heap, parms);
3406 /* Analyze the collected accesses and produce a plan what to do with the
3407 parameters in the form of adjustments, NULL meaning nothing. */
3409 static ipa_parm_adjustment_vec
3410 analyze_all_param_acesses (void)
3412 enum ipa_splicing_result repr_state;
3413 bool proceed = false;
3414 int i, adjustments_count = 0;
3415 VEC (access_p, heap) *representatives;
3416 ipa_parm_adjustment_vec adjustments;
3418 repr_state = splice_all_param_accesses (&representatives);
3419 if (repr_state == NO_GOOD_ACCESS)
3422 /* If there are any parameters passed by reference which are not modified
3423 directly, we need to check whether they can be modified indirectly. */
3424 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3426 analyze_caller_dereference_legality (representatives);
3427 analyze_modified_params (representatives);
3430 for (i = 0; i < func_param_count; i++)
3432 struct access *repr = VEC_index (access_p, representatives, i);
3434 if (repr && !no_accesses_p (repr))
3436 if (repr->grp_scalar_ptr)
3438 adjustments_count++;
3439 if (repr->grp_not_necessarilly_dereferenced
3440 || repr->grp_maybe_modified)
3441 VEC_replace (access_p, representatives, i, NULL);
3445 sra_stats.scalar_by_ref_to_by_val++;
3450 int new_components = decide_one_param_reduction (repr);
3452 if (new_components == 0)
3454 VEC_replace (access_p, representatives, i, NULL);
3455 adjustments_count++;
3459 adjustments_count += new_components;
3460 sra_stats.aggregate_params_reduced++;
3461 sra_stats.param_reductions_created += new_components;
3468 if (no_accesses_p (repr))
3471 sra_stats.deleted_unused_parameters++;
3473 adjustments_count++;
3477 if (!proceed && dump_file)
3478 fprintf (dump_file, "NOT proceeding to change params.\n");
3481 adjustments = turn_representatives_into_adjustments (representatives,
3486 VEC_free (access_p, heap, representatives);
3490 /* If a parameter replacement identified by ADJ does not yet exist in the form
3491 of declaration, create it and record it, otherwise return the previously
3495 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3498 if (!adj->new_ssa_base)
3500 char *pretty_name = make_fancy_name (adj->base);
3502 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3503 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3504 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3505 DECL_GIMPLE_REG_P (repl) = 1;
3506 DECL_NAME (repl) = get_identifier (pretty_name);
3507 obstack_free (&name_obstack, pretty_name);
3510 add_referenced_var (repl);
3511 adj->new_ssa_base = repl;
3514 repl = adj->new_ssa_base;
3518 /* Find the first adjustment for a particular parameter BASE in a vector of
3519 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3522 static struct ipa_parm_adjustment *
3523 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3527 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3528 for (i = 0; i < len; i++)
3530 struct ipa_parm_adjustment *adj;
3532 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3533 if (!adj->copy_param && adj->base == base)
3540 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3541 parameter which is to be removed because its value is not used, replace the
3542 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3543 uses too and return true (update_stmt is then issued for the statement by
3544 the caller). DATA is a pointer to an adjustments vector. */
3547 replace_removed_params_ssa_names (gimple stmt, void *data)
3549 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3550 struct ipa_parm_adjustment *adj;
3551 tree lhs, decl, repl, name;
3553 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3554 if (gimple_code (stmt) == GIMPLE_PHI)
3555 lhs = gimple_phi_result (stmt);
3556 else if (is_gimple_assign (stmt))
3557 lhs = gimple_assign_lhs (stmt);
3558 else if (is_gimple_call (stmt))
3559 lhs = gimple_call_lhs (stmt);
3563 if (TREE_CODE (lhs) != SSA_NAME)
3565 decl = SSA_NAME_VAR (lhs);
3566 if (TREE_CODE (decl) != PARM_DECL)
3569 adj = get_adjustment_for_base (adjustments, decl);
3573 repl = get_replaced_param_substitute (adj);
3574 name = make_ssa_name (repl, stmt);
3578 fprintf (dump_file, "replacing an SSA name of a removed param ");
3579 print_generic_expr (dump_file, lhs, 0);
3580 fprintf (dump_file, " with ");
3581 print_generic_expr (dump_file, name, 0);
3582 fprintf (dump_file, "\n");
3585 if (is_gimple_assign (stmt))
3586 gimple_assign_set_lhs (stmt, name);
3587 else if (is_gimple_call (stmt))
3588 gimple_call_set_lhs (stmt, name);
3590 gimple_phi_set_result (stmt, name);
3592 replace_uses_by (lhs, name);
3596 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3597 expression *EXPR should be replaced by a reduction of a parameter, do so.
3598 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3599 whether the function should care about type incompatibility the current and
3600 new expressions. If it is true, the function will leave incompatibility
3601 issues to the caller.
3603 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3604 a write (LHS) expression. */
3607 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3608 bool dont_convert, void *data)
3610 ipa_parm_adjustment_vec adjustments;
3612 struct ipa_parm_adjustment *adj, *cand = NULL;
3613 HOST_WIDE_INT offset, size, max_size;
3616 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3617 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3619 if (TREE_CODE (*expr) == BIT_FIELD_REF
3620 || TREE_CODE (*expr) == IMAGPART_EXPR
3621 || TREE_CODE (*expr) == REALPART_EXPR)
3623 expr = &TREE_OPERAND (*expr, 0);
3624 dont_convert = false;
3627 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3628 if (!base || size == -1 || max_size == -1)
3631 if (INDIRECT_REF_P (base))
3632 base = TREE_OPERAND (base, 0);
3634 base = get_ssa_base_param (base);
3635 if (!base || TREE_CODE (base) != PARM_DECL)
3638 for (i = 0; i < len; i++)
3640 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3642 if (adj->base == base &&
3643 (adj->offset == offset || adj->remove_param))
3649 if (!cand || cand->copy_param || cand->remove_param)
3655 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3657 folded = gimple_fold_indirect_ref (src);
3662 src = cand->reduction;
3664 if (dump_file && (dump_flags & TDF_DETAILS))
3666 fprintf (dump_file, "About to replace expr ");
3667 print_generic_expr (dump_file, *expr, 0);
3668 fprintf (dump_file, " with ");
3669 print_generic_expr (dump_file, src, 0);
3670 fprintf (dump_file, "\n");
3674 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3676 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3684 /* Callback for scan_function to process assign statements. Performs
3685 essentially the same function like sra_ipa_modify_expr. */
3687 static enum scan_assign_result
3688 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3690 gimple stmt = *stmt_ptr;
3691 tree *lhs_p, *rhs_p;
3694 if (!gimple_assign_single_p (stmt))
3697 rhs_p = gimple_assign_rhs1_ptr (stmt);
3698 lhs_p = gimple_assign_lhs_ptr (stmt);
3700 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3701 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3704 tree new_rhs = NULL_TREE;
3706 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3707 new_rhs = fold_build1_loc (gimple_location (stmt), VIEW_CONVERT_EXPR,
3708 TREE_TYPE (*lhs_p), *rhs_p);
3709 else if (REFERENCE_CLASS_P (*rhs_p)
3710 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3711 && !is_gimple_reg (*lhs_p))
3712 /* This can happen when an assignment in between two single field
3713 structures is turned into an assignment in between two pointers to
3714 scalars (PR 42237). */
3719 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3720 true, GSI_SAME_STMT);
3722 gimple_assign_set_rhs_from_tree (gsi, tmp);
3725 return SRA_SA_PROCESSED;
3731 /* Call gimple_debug_bind_reset_value on all debug statements describing
3732 gimple register parameters that are being removed or replaced. */
3735 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3739 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3740 for (i = 0; i < len; i++)
3742 struct ipa_parm_adjustment *adj;
3743 imm_use_iterator ui;
3747 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3748 if (adj->copy_param || !is_gimple_reg (adj->base))
3750 name = gimple_default_def (cfun, adj->base);
3753 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3755 /* All other users must have been removed by scan_function. */
3756 gcc_assert (is_gimple_debug (stmt));
3757 gimple_debug_bind_reset_value (stmt);
3763 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3766 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3768 tree old_cur_fndecl = current_function_decl;
3769 struct cgraph_edge *cs;
3770 basic_block this_block;
3771 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3773 for (cs = node->callers; cs; cs = cs->next_caller)
3775 current_function_decl = cs->caller->decl;
3776 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3779 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3780 cs->caller->uid, cs->callee->uid,
3781 cgraph_node_name (cs->caller),
3782 cgraph_node_name (cs->callee));
3784 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3789 for (cs = node->callers; cs; cs = cs->next_caller)
3790 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3792 compute_inline_parameters (cs->caller);
3793 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3795 BITMAP_FREE (recomputed_callers);
3797 current_function_decl = old_cur_fndecl;
3798 FOR_EACH_BB (this_block)
3800 gimple_stmt_iterator gsi;
3802 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3804 gimple stmt = gsi_stmt (gsi);
3806 if (gimple_code (stmt) != GIMPLE_CALL)
3808 call_fndecl = gimple_call_fndecl (stmt);
3809 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
3812 fprintf (dump_file, "Adjusting recursive call");
3813 ipa_modify_call_arguments (NULL, stmt, adjustments);
3821 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3822 as given in ADJUSTMENTS. */
3825 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3827 struct cgraph_node *alias;
3828 for (alias = node->same_body; alias; alias = alias->next)
3829 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
3830 /* current_function_decl must be handled last, after same_body aliases,
3831 as following functions will use what it computed. */
3832 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3833 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3834 replace_removed_params_ssa_names, false, adjustments);
3835 sra_ipa_reset_debug_stmts (adjustments);
3836 convert_callers (node, adjustments);
3837 cgraph_make_node_local (node);
3841 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3842 attributes, return true otherwise. NODE is the cgraph node of the current
3846 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3848 if (!cgraph_node_can_be_local_p (node))
3851 fprintf (dump_file, "Function not local to this compilation unit.\n");
3855 if (DECL_VIRTUAL_P (current_function_decl))
3858 fprintf (dump_file, "Function is a virtual method.\n");
3862 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3863 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3866 fprintf (dump_file, "Function too big to be made truly local.\n");
3874 "Function has no callers in this compilation unit.\n");
3881 fprintf (dump_file, "Function uses stdarg. \n");
3888 /* Perform early interprocedural SRA. */
3891 ipa_early_sra (void)
3893 struct cgraph_node *node = cgraph_node (current_function_decl);
3894 ipa_parm_adjustment_vec adjustments;
3897 if (!ipa_sra_preliminary_function_checks (node))
3901 sra_mode = SRA_MODE_EARLY_IPA;
3903 if (!find_param_candidates ())
3906 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3910 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3912 * last_basic_block_for_function (cfun));
3913 final_bbs = BITMAP_ALLOC (NULL);
3915 scan_function (build_access_from_expr, build_accesses_from_assign,
3917 if (encountered_apply_args)
3920 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3924 adjustments = analyze_all_param_acesses ();
3928 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3930 modify_function (node, adjustments);
3931 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3932 ret = TODO_update_ssa;
3934 statistics_counter_event (cfun, "Unused parameters deleted",
3935 sra_stats.deleted_unused_parameters);
3936 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3937 sra_stats.scalar_by_ref_to_by_val);
3938 statistics_counter_event (cfun, "Aggregate parameters broken up",
3939 sra_stats.aggregate_params_reduced);
3940 statistics_counter_event (cfun, "Aggregate parameter components created",
3941 sra_stats.param_reductions_created);
3944 BITMAP_FREE (final_bbs);
3945 free (bb_dereferences);
3947 sra_deinitialize ();
3951 /* Return if early ipa sra shall be performed. */
3953 ipa_early_sra_gate (void)
3955 return flag_ipa_sra;
3958 struct gimple_opt_pass pass_early_ipa_sra =
3962 "eipa_sra", /* name */
3963 ipa_early_sra_gate, /* gate */
3964 ipa_early_sra, /* execute */
3967 0, /* static_pass_number */
3968 TV_IPA_SRA, /* tv_id */
3969 0, /* properties_required */
3970 0, /* properties_provided */
3971 0, /* properties_destroyed */
3972 0, /* todo_flags_start */
3973 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */