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"
83 #include "tree-flow.h"
85 #include "diagnostic.h"
86 #include "statistics.h"
87 #include "tree-dump.h"
93 /* Enumeration of all aggregate reductions we can do. */
94 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
95 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
96 SRA_MODE_INTRA }; /* late intraprocedural SRA */
98 /* Global variable describing which aggregate reduction we are performing at
100 static enum sra_mode sra_mode;
104 /* ACCESS represents each access to an aggregate variable (as a whole or a
105 part). It can also represent a group of accesses that refer to exactly the
106 same fragment of an aggregate (i.e. those that have exactly the same offset
107 and size). Such representatives for a single aggregate, once determined,
108 are linked in a linked list and have the group fields set.
110 Moreover, when doing intraprocedural SRA, a tree is built from those
111 representatives (by the means of first_child and next_sibling pointers), in
112 which all items in a subtree are "within" the root, i.e. their offset is
113 greater or equal to offset of the root and offset+size is smaller or equal
114 to offset+size of the root. Children of an access are sorted by offset.
116 Note that accesses to parts of vector and complex number types always
117 represented by an access to the whole complex number or a vector. It is a
118 duty of the modifying functions to replace them appropriately. */
122 /* Values returned by `get_ref_base_and_extent' for each component reference
123 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
124 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
125 HOST_WIDE_INT offset;
129 /* Expression. It is context dependent so do not use it to create new
130 expressions to access the original aggregate. See PR 42154 for a
136 /* The statement this access belongs to. */
139 /* Next group representative for this aggregate. */
140 struct access *next_grp;
142 /* Pointer to the group representative. Pointer to itself if the struct is
143 the representative. */
144 struct access *group_representative;
146 /* If this access has any children (in terms of the definition above), this
147 points to the first one. */
148 struct access *first_child;
150 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
151 described above. In IPA-SRA this is a pointer to the next access
152 belonging to the same group (having the same representative). */
153 struct access *next_sibling;
155 /* Pointers to the first and last element in the linked list of assign
157 struct assign_link *first_link, *last_link;
159 /* Pointer to the next access in the work queue. */
160 struct access *next_queued;
162 /* Replacement variable for this access "region." Never to be accessed
163 directly, always only by the means of get_access_replacement() and only
164 when grp_to_be_replaced flag is set. */
165 tree replacement_decl;
167 /* Is this particular access write access? */
170 /* Is this access an artificial one created to scalarize some record
172 unsigned total_scalarization : 1;
174 /* Is this access currently in the work queue? */
175 unsigned grp_queued : 1;
177 /* Does this group contain a write access? This flag is propagated down the
179 unsigned grp_write : 1;
181 /* Does this group contain a read access? This flag is propagated down the
183 unsigned grp_read : 1;
185 /* Other passes of the analysis use this bit to make function
186 analyze_access_subtree create scalar replacements for this group if
188 unsigned grp_hint : 1;
190 /* Is the subtree rooted in this access fully covered by scalar
192 unsigned grp_covered : 1;
194 /* If set to true, this access and all below it in an access tree must not be
196 unsigned grp_unscalarizable_region : 1;
198 /* Whether data have been written to parts of the aggregate covered by this
199 access which is not to be scalarized. This flag is propagated up in the
201 unsigned grp_unscalarized_data : 1;
203 /* Does this access and/or group contain a write access through a
205 unsigned grp_partial_lhs : 1;
207 /* Set when a scalar replacement should be created for this variable. We do
208 the decision and creation at different places because create_tmp_var
209 cannot be called from within FOR_EACH_REFERENCED_VAR. */
210 unsigned grp_to_be_replaced : 1;
212 /* Is it possible that the group refers to data which might be (directly or
213 otherwise) modified? */
214 unsigned grp_maybe_modified : 1;
216 /* Set when this is a representative of a pointer to scalar (i.e. by
217 reference) parameter which we consider for turning into a plain scalar
218 (i.e. a by value parameter). */
219 unsigned grp_scalar_ptr : 1;
221 /* Set when we discover that this pointer is not safe to dereference in the
223 unsigned grp_not_necessarilly_dereferenced : 1;
226 typedef struct access *access_p;
228 DEF_VEC_P (access_p);
229 DEF_VEC_ALLOC_P (access_p, heap);
231 /* Alloc pool for allocating access structures. */
232 static alloc_pool access_pool;
234 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
235 are used to propagate subaccesses from rhs to lhs as long as they don't
236 conflict with what is already there. */
239 struct access *lacc, *racc;
240 struct assign_link *next;
243 /* Alloc pool for allocating assign link structures. */
244 static alloc_pool link_pool;
246 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
247 static struct pointer_map_t *base_access_vec;
249 /* Bitmap of candidates. */
250 static bitmap candidate_bitmap;
252 /* Bitmap of candidates which we should try to entirely scalarize away and
253 those which cannot be (because they are and need be used as a whole). */
254 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
256 /* Obstack for creation of fancy names. */
257 static struct obstack name_obstack;
259 /* Head of a linked list of accesses that need to have its subaccesses
260 propagated to their assignment counterparts. */
261 static struct access *work_queue_head;
263 /* Number of parameters of the analyzed function when doing early ipa SRA. */
264 static int func_param_count;
266 /* scan_function sets the following to true if it encounters a call to
267 __builtin_apply_args. */
268 static bool encountered_apply_args;
270 /* Set by scan_function when it finds a recursive call. */
271 static bool encountered_recursive_call;
273 /* Set by scan_function when it finds a recursive call with less actual
274 arguments than formal parameters.. */
275 static bool encountered_unchangable_recursive_call;
277 /* This is a table in which for each basic block and parameter there is a
278 distance (offset + size) in that parameter which is dereferenced and
279 accessed in that BB. */
280 static HOST_WIDE_INT *bb_dereferences;
281 /* Bitmap of BBs that can cause the function to "stop" progressing by
282 returning, throwing externally, looping infinitely or calling a function
283 which might abort etc.. */
284 static bitmap final_bbs;
286 /* Representative of no accesses at all. */
287 static struct access no_accesses_representant;
289 /* Predicate to test the special value. */
292 no_accesses_p (struct access *access)
294 return access == &no_accesses_representant;
297 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
298 representative fields are dumped, otherwise those which only describe the
299 individual access are. */
303 /* Number of processed aggregates is readily available in
304 analyze_all_variable_accesses and so is not stored here. */
306 /* Number of created scalar replacements. */
309 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
313 /* Number of statements created by generate_subtree_copies. */
316 /* Number of statements created by load_assign_lhs_subreplacements. */
319 /* Number of times sra_modify_assign has deleted a statement. */
322 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
323 RHS reparately due to type conversions or nonexistent matching
325 int separate_lhs_rhs_handling;
327 /* Number of parameters that were removed because they were unused. */
328 int deleted_unused_parameters;
330 /* Number of scalars passed as parameters by reference that have been
331 converted to be passed by value. */
332 int scalar_by_ref_to_by_val;
334 /* Number of aggregate parameters that were replaced by one or more of their
336 int aggregate_params_reduced;
338 /* Numbber of components created when splitting aggregate parameters. */
339 int param_reductions_created;
343 dump_access (FILE *f, struct access *access, bool grp)
345 fprintf (f, "access { ");
346 fprintf (f, "base = (%d)'", DECL_UID (access->base));
347 print_generic_expr (f, access->base, 0);
348 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
349 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
350 fprintf (f, ", expr = ");
351 print_generic_expr (f, access->expr, 0);
352 fprintf (f, ", type = ");
353 print_generic_expr (f, access->type, 0);
355 fprintf (f, ", grp_write = %d, total_scalarization = %d, "
356 "grp_read = %d, grp_hint = %d, "
357 "grp_covered = %d, grp_unscalarizable_region = %d, "
358 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
359 "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
360 "grp_not_necessarilly_dereferenced = %d\n",
361 access->grp_write, access->total_scalarization,
362 access->grp_read, access->grp_hint,
363 access->grp_covered, access->grp_unscalarizable_region,
364 access->grp_unscalarized_data, access->grp_partial_lhs,
365 access->grp_to_be_replaced, access->grp_maybe_modified,
366 access->grp_not_necessarilly_dereferenced);
368 fprintf (f, ", write = %d, total_scalarization = %d, "
369 "grp_partial_lhs = %d\n",
370 access->write, access->total_scalarization,
371 access->grp_partial_lhs);
374 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
377 dump_access_tree_1 (FILE *f, struct access *access, int level)
383 for (i = 0; i < level; i++)
384 fputs ("* ", dump_file);
386 dump_access (f, access, true);
388 if (access->first_child)
389 dump_access_tree_1 (f, access->first_child, level + 1);
391 access = access->next_sibling;
396 /* Dump all access trees for a variable, given the pointer to the first root in
400 dump_access_tree (FILE *f, struct access *access)
402 for (; access; access = access->next_grp)
403 dump_access_tree_1 (f, access, 0);
406 /* Return true iff ACC is non-NULL and has subaccesses. */
409 access_has_children_p (struct access *acc)
411 return acc && acc->first_child;
414 /* Return a vector of pointers to accesses for the variable given in BASE or
415 NULL if there is none. */
417 static VEC (access_p, heap) *
418 get_base_access_vector (tree base)
422 slot = pointer_map_contains (base_access_vec, base);
426 return *(VEC (access_p, heap) **) slot;
429 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
430 in ACCESS. Return NULL if it cannot be found. */
432 static struct access *
433 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
436 while (access && (access->offset != offset || access->size != size))
438 struct access *child = access->first_child;
440 while (child && (child->offset + child->size <= offset))
441 child = child->next_sibling;
448 /* Return the first group representative for DECL or NULL if none exists. */
450 static struct access *
451 get_first_repr_for_decl (tree base)
453 VEC (access_p, heap) *access_vec;
455 access_vec = get_base_access_vector (base);
459 return VEC_index (access_p, access_vec, 0);
462 /* Find an access representative for the variable BASE and given OFFSET and
463 SIZE. Requires that access trees have already been built. Return NULL if
464 it cannot be found. */
466 static struct access *
467 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
470 struct access *access;
472 access = get_first_repr_for_decl (base);
473 while (access && (access->offset + access->size <= offset))
474 access = access->next_grp;
478 return find_access_in_subtree (access, offset, size);
481 /* Add LINK to the linked list of assign links of RACC. */
483 add_link_to_rhs (struct access *racc, struct assign_link *link)
485 gcc_assert (link->racc == racc);
487 if (!racc->first_link)
489 gcc_assert (!racc->last_link);
490 racc->first_link = link;
493 racc->last_link->next = link;
495 racc->last_link = link;
499 /* Move all link structures in their linked list in OLD_RACC to the linked list
502 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
504 if (!old_racc->first_link)
506 gcc_assert (!old_racc->last_link);
510 if (new_racc->first_link)
512 gcc_assert (!new_racc->last_link->next);
513 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
515 new_racc->last_link->next = old_racc->first_link;
516 new_racc->last_link = old_racc->last_link;
520 gcc_assert (!new_racc->last_link);
522 new_racc->first_link = old_racc->first_link;
523 new_racc->last_link = old_racc->last_link;
525 old_racc->first_link = old_racc->last_link = NULL;
528 /* Add ACCESS to the work queue (which is actually a stack). */
531 add_access_to_work_queue (struct access *access)
533 if (!access->grp_queued)
535 gcc_assert (!access->next_queued);
536 access->next_queued = work_queue_head;
537 access->grp_queued = 1;
538 work_queue_head = access;
542 /* Pop an access from the work queue, and return it, assuming there is one. */
544 static struct access *
545 pop_access_from_work_queue (void)
547 struct access *access = work_queue_head;
549 work_queue_head = access->next_queued;
550 access->next_queued = NULL;
551 access->grp_queued = 0;
556 /* Allocate necessary structures. */
559 sra_initialize (void)
561 candidate_bitmap = BITMAP_ALLOC (NULL);
562 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
563 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
564 gcc_obstack_init (&name_obstack);
565 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
566 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
567 base_access_vec = pointer_map_create ();
568 memset (&sra_stats, 0, sizeof (sra_stats));
569 encountered_apply_args = false;
570 encountered_recursive_call = false;
571 encountered_unchangable_recursive_call = false;
574 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
577 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
578 void *data ATTRIBUTE_UNUSED)
580 VEC (access_p, heap) *access_vec;
581 access_vec = (VEC (access_p, heap) *) *value;
582 VEC_free (access_p, heap, access_vec);
587 /* Deallocate all general structures. */
590 sra_deinitialize (void)
592 BITMAP_FREE (candidate_bitmap);
593 BITMAP_FREE (should_scalarize_away_bitmap);
594 BITMAP_FREE (cannot_scalarize_away_bitmap);
595 free_alloc_pool (access_pool);
596 free_alloc_pool (link_pool);
597 obstack_free (&name_obstack, NULL);
599 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
600 pointer_map_destroy (base_access_vec);
603 /* Remove DECL from candidates for SRA and write REASON to the dump file if
606 disqualify_candidate (tree decl, const char *reason)
608 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
610 if (dump_file && (dump_flags & TDF_DETAILS))
612 fprintf (dump_file, "! Disqualifying ");
613 print_generic_expr (dump_file, decl, 0);
614 fprintf (dump_file, " - %s\n", reason);
618 /* Return true iff the type contains a field or an element which does not allow
622 type_internals_preclude_sra_p (tree type)
627 switch (TREE_CODE (type))
631 case QUAL_UNION_TYPE:
632 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
633 if (TREE_CODE (fld) == FIELD_DECL)
635 tree ft = TREE_TYPE (fld);
637 if (TREE_THIS_VOLATILE (fld)
638 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
639 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
640 || !host_integerp (DECL_SIZE (fld), 1))
643 if (AGGREGATE_TYPE_P (ft)
644 && type_internals_preclude_sra_p (ft))
651 et = TREE_TYPE (type);
653 if (AGGREGATE_TYPE_P (et))
654 return type_internals_preclude_sra_p (et);
663 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
664 base variable if it is. Return T if it is not an SSA_NAME. */
667 get_ssa_base_param (tree t)
669 if (TREE_CODE (t) == SSA_NAME)
671 if (SSA_NAME_IS_DEFAULT_DEF (t))
672 return SSA_NAME_VAR (t);
679 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
680 belongs to, unless the BB has already been marked as a potentially
684 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
686 basic_block bb = gimple_bb (stmt);
687 int idx, parm_index = 0;
690 if (bitmap_bit_p (final_bbs, bb->index))
693 for (parm = DECL_ARGUMENTS (current_function_decl);
694 parm && parm != base;
695 parm = TREE_CHAIN (parm))
698 gcc_assert (parm_index < func_param_count);
700 idx = bb->index * func_param_count + parm_index;
701 if (bb_dereferences[idx] < dist)
702 bb_dereferences[idx] = dist;
705 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
706 the three fields. Also add it to the vector of accesses corresponding to
707 the base. Finally, return the new access. */
709 static struct access *
710 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
712 VEC (access_p, heap) *vec;
713 struct access *access;
716 access = (struct access *) pool_alloc (access_pool);
717 memset (access, 0, sizeof (struct access));
719 access->offset = offset;
722 slot = pointer_map_contains (base_access_vec, base);
724 vec = (VEC (access_p, heap) *) *slot;
726 vec = VEC_alloc (access_p, heap, 32);
728 VEC_safe_push (access_p, heap, vec, access);
730 *((struct VEC (access_p,heap) **)
731 pointer_map_insert (base_access_vec, base)) = vec;
736 /* Create and insert access for EXPR. Return created access, or NULL if it is
739 static struct access *
740 create_access (tree expr, gimple stmt, bool write)
742 struct access *access;
743 HOST_WIDE_INT offset, size, max_size;
745 bool ptr, unscalarizable_region = false;
747 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
749 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
751 base = get_ssa_base_param (TREE_OPERAND (base, 0));
759 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
762 if (sra_mode == SRA_MODE_EARLY_IPA)
764 if (size < 0 || size != max_size)
766 disqualify_candidate (base, "Encountered a variable sized access.");
769 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
771 disqualify_candidate (base,
772 "Encountered an acces not aligned to a byte.");
777 mark_parm_dereference (base, offset + size, stmt);
781 if (size != max_size)
784 unscalarizable_region = true;
788 disqualify_candidate (base, "Encountered an unconstrained access.");
793 access = create_access_1 (base, offset, size);
795 access->type = TREE_TYPE (expr);
796 access->write = write;
797 access->grp_unscalarizable_region = unscalarizable_region;
804 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
805 register types or (recursively) records with only these two kinds of
809 type_consists_of_records_p (tree type)
813 if (TREE_CODE (type) != RECORD_TYPE)
816 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
817 if (TREE_CODE (fld) == FIELD_DECL)
819 tree ft = TREE_TYPE (fld);
821 if (!is_gimple_reg_type (ft)
822 && !type_consists_of_records_p (ft))
828 /* Create total_scalarization accesses for all scalar type fields in DECL that
829 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE
830 must be the top-most VAR_DECL representing the variable, OFFSET must be the
831 offset of DECL within BASE. */
834 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset)
836 tree fld, decl_type = TREE_TYPE (decl);
838 for (fld = TYPE_FIELDS (decl_type); fld; fld = TREE_CHAIN (fld))
839 if (TREE_CODE (fld) == FIELD_DECL)
841 HOST_WIDE_INT pos = offset + int_bit_position (fld);
842 tree ft = TREE_TYPE (fld);
844 if (is_gimple_reg_type (ft))
846 struct access *access;
851 size = tree_low_cst (DECL_SIZE (fld), 1);
853 ok = build_ref_for_offset (&expr, TREE_TYPE (base), pos,
857 access = create_access_1 (base, pos, size);
860 access->total_scalarization = 1;
861 /* Accesses for intraprocedural SRA can have their stmt NULL. */
864 completely_scalarize_record (base, fld, pos);
869 /* Search the given tree for a declaration by skipping handled components and
870 exclude it from the candidates. */
873 disqualify_base_of_expr (tree t, const char *reason)
875 while (handled_component_p (t))
876 t = TREE_OPERAND (t, 0);
878 if (sra_mode == SRA_MODE_EARLY_IPA)
880 if (INDIRECT_REF_P (t))
881 t = TREE_OPERAND (t, 0);
882 t = get_ssa_base_param (t);
886 disqualify_candidate (t, reason);
889 /* Scan expression EXPR and create access structures for all accesses to
890 candidates for scalarization. Return the created access or NULL if none is
893 static struct access *
894 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
896 struct access *ret = NULL;
897 tree expr = *expr_ptr;
900 if (TREE_CODE (expr) == BIT_FIELD_REF
901 || TREE_CODE (expr) == IMAGPART_EXPR
902 || TREE_CODE (expr) == REALPART_EXPR)
904 expr = TREE_OPERAND (expr, 0);
910 /* We need to dive through V_C_Es in order to get the size of its parameter
911 and not the result type. Ada produces such statements. We are also
912 capable of handling the topmost V_C_E but not any of those buried in other
913 handled components. */
914 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
915 expr = TREE_OPERAND (expr, 0);
917 if (contains_view_convert_expr_p (expr))
919 disqualify_base_of_expr (expr, "V_C_E under a different handled "
924 switch (TREE_CODE (expr))
927 if (sra_mode != SRA_MODE_EARLY_IPA)
935 case ARRAY_RANGE_REF:
936 ret = create_access (expr, stmt, write);
943 if (write && partial_ref && ret)
944 ret->grp_partial_lhs = 1;
949 /* Callback of scan_function. Scan expression EXPR and create access
950 structures for all accesses to candidates for scalarization. Return true if
951 any access has been inserted. */
954 build_access_from_expr (tree *expr_ptr,
955 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
956 void *data ATTRIBUTE_UNUSED)
958 struct access *access;
960 access = build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write);
963 /* This means the aggregate is accesses as a whole in a way other than an
964 assign statement and thus cannot be removed even if we had a scalar
965 replacement for everything. */
966 if (cannot_scalarize_away_bitmap)
967 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
973 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
974 modes in which it matters, return true iff they have been disqualified. RHS
975 may be NULL, in that case ignore it. If we scalarize an aggregate in
976 intra-SRA we may need to add statements after each statement. This is not
977 possible if a statement unconditionally has to end the basic block. */
979 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
981 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
982 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
984 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
986 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
993 /* Result code for scan_assign callback for scan_function. */
994 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
995 SRA_SA_PROCESSED, /* stmt analyzed/changed */
996 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
999 /* Callback of scan_function. Scan expressions occuring in the statement
1000 pointed to by STMT_EXPR, create access structures for all accesses to
1001 candidates for scalarization and remove those candidates which occur in
1002 statements or expressions that prevent them from being split apart. Return
1003 true if any access has been inserted. */
1005 static enum scan_assign_result
1006 build_accesses_from_assign (gimple *stmt_ptr,
1007 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
1008 void *data ATTRIBUTE_UNUSED)
1010 gimple stmt = *stmt_ptr;
1011 tree *lhs_ptr, *rhs_ptr;
1012 struct access *lacc, *racc;
1014 if (!gimple_assign_single_p (stmt))
1017 lhs_ptr = gimple_assign_lhs_ptr (stmt);
1018 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
1020 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
1023 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
1024 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
1026 if (should_scalarize_away_bitmap && !gimple_has_volatile_ops (stmt)
1027 && racc && !is_gimple_reg_type (racc->type))
1028 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1031 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1032 && !lacc->grp_unscalarizable_region
1033 && !racc->grp_unscalarizable_region
1034 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
1035 /* FIXME: Turn the following line into an assert after PR 40058 is
1037 && lacc->size == racc->size
1038 && useless_type_conversion_p (lacc->type, racc->type))
1040 struct assign_link *link;
1042 link = (struct assign_link *) pool_alloc (link_pool);
1043 memset (link, 0, sizeof (struct assign_link));
1048 add_link_to_rhs (racc, link);
1051 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
1054 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1055 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1058 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1059 void *data ATTRIBUTE_UNUSED)
1062 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1067 /* Return true iff callsite CALL has at least as many actual arguments as there
1068 are formal parameters of the function currently processed by IPA-SRA. */
1071 callsite_has_enough_arguments_p (gimple call)
1073 return gimple_call_num_args (call) >= (unsigned) func_param_count;
1076 /* Scan function and look for interesting statements. Return true if any has
1077 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
1078 called on all expressions within statements except assign statements and
1079 those deemed entirely unsuitable for some reason (all operands in such
1080 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
1081 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
1082 called on assign statements and those call statements which have a lhs, it
1083 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
1084 pass and thus no statement is being modified. DATA is a pointer passed to
1085 all callbacks. If any single callback returns true, this function also
1086 returns true, otherwise it returns false. */
1089 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
1090 enum scan_assign_result (*scan_assign) (gimple *,
1091 gimple_stmt_iterator *,
1093 bool (*handle_ssa_defs)(gimple, void *),
1094 bool analysis_stage, void *data)
1096 gimple_stmt_iterator gsi;
1104 bool bb_changed = false;
1106 if (handle_ssa_defs)
1107 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1108 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
1110 gsi = gsi_start_bb (bb);
1111 while (!gsi_end_p (gsi))
1113 gimple stmt = gsi_stmt (gsi);
1114 enum scan_assign_result assign_result;
1115 bool any = false, deleted = false;
1117 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
1118 bitmap_set_bit (final_bbs, bb->index);
1119 switch (gimple_code (stmt))
1122 t = gimple_return_retval_ptr (stmt);
1123 if (*t != NULL_TREE)
1124 any |= scan_expr (t, &gsi, false, data);
1125 if (analysis_stage && final_bbs)
1126 bitmap_set_bit (final_bbs, bb->index);
1130 assign_result = scan_assign (&stmt, &gsi, data);
1131 any |= assign_result == SRA_SA_PROCESSED;
1132 deleted = assign_result == SRA_SA_REMOVED;
1133 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1134 any |= handle_ssa_defs (stmt, data);
1138 /* Operands must be processed before the lhs. */
1139 for (i = 0; i < gimple_call_num_args (stmt); i++)
1141 tree *argp = gimple_call_arg_ptr (stmt, i);
1142 any |= scan_expr (argp, &gsi, false, data);
1145 if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
1147 tree dest = gimple_call_fndecl (stmt);
1148 int flags = gimple_call_flags (stmt);
1152 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1153 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1154 encountered_apply_args = true;
1155 if (cgraph_get_node (dest)
1156 == cgraph_get_node (current_function_decl))
1158 encountered_recursive_call = true;
1159 if (!callsite_has_enough_arguments_p (stmt))
1160 encountered_unchangable_recursive_call = true;
1165 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1166 bitmap_set_bit (final_bbs, bb->index);
1169 if (gimple_call_lhs (stmt))
1171 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1173 || !disqualify_ops_if_throwing_stmt (stmt,
1176 any |= scan_expr (lhs_ptr, &gsi, true, data);
1177 if (handle_ssa_defs)
1178 any |= handle_ssa_defs (stmt, data);
1186 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1189 bitmap_set_bit (final_bbs, bb->index);
1191 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1193 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1194 any |= scan_expr (op, &gsi, false, data);
1196 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1198 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1199 any |= scan_expr (op, &gsi, true, data);
1211 if (!analysis_stage)
1215 maybe_clean_eh_stmt (stmt);
1226 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1227 gimple_purge_dead_eh_edges (bb);
1233 /* Helper of QSORT function. There are pointers to accesses in the array. An
1234 access is considered smaller than another if it has smaller offset or if the
1235 offsets are the same but is size is bigger. */
1238 compare_access_positions (const void *a, const void *b)
1240 const access_p *fp1 = (const access_p *) a;
1241 const access_p *fp2 = (const access_p *) b;
1242 const access_p f1 = *fp1;
1243 const access_p f2 = *fp2;
1245 if (f1->offset != f2->offset)
1246 return f1->offset < f2->offset ? -1 : 1;
1248 if (f1->size == f2->size)
1250 if (f1->type == f2->type)
1252 /* Put any non-aggregate type before any aggregate type. */
1253 else if (!is_gimple_reg_type (f1->type)
1254 && is_gimple_reg_type (f2->type))
1256 else if (is_gimple_reg_type (f1->type)
1257 && !is_gimple_reg_type (f2->type))
1259 /* Put any complex or vector type before any other scalar type. */
1260 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1261 && TREE_CODE (f1->type) != VECTOR_TYPE
1262 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1263 || TREE_CODE (f2->type) == VECTOR_TYPE))
1265 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1266 || TREE_CODE (f1->type) == VECTOR_TYPE)
1267 && TREE_CODE (f2->type) != COMPLEX_TYPE
1268 && TREE_CODE (f2->type) != VECTOR_TYPE)
1270 /* Put the integral type with the bigger precision first. */
1271 else if (INTEGRAL_TYPE_P (f1->type)
1272 && INTEGRAL_TYPE_P (f2->type))
1273 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1274 /* Put any integral type with non-full precision last. */
1275 else if (INTEGRAL_TYPE_P (f1->type)
1276 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1277 != TYPE_PRECISION (f1->type)))
1279 else if (INTEGRAL_TYPE_P (f2->type)
1280 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1281 != TYPE_PRECISION (f2->type)))
1283 /* Stabilize the sort. */
1284 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1287 /* We want the bigger accesses first, thus the opposite operator in the next
1289 return f1->size > f2->size ? -1 : 1;
1293 /* Append a name of the declaration to the name obstack. A helper function for
1297 make_fancy_decl_name (tree decl)
1301 tree name = DECL_NAME (decl);
1303 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1304 IDENTIFIER_LENGTH (name));
1307 sprintf (buffer, "D%u", DECL_UID (decl));
1308 obstack_grow (&name_obstack, buffer, strlen (buffer));
1312 /* Helper for make_fancy_name. */
1315 make_fancy_name_1 (tree expr)
1322 make_fancy_decl_name (expr);
1326 switch (TREE_CODE (expr))
1329 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1330 obstack_1grow (&name_obstack, '$');
1331 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1335 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1336 obstack_1grow (&name_obstack, '$');
1337 /* Arrays with only one element may not have a constant as their
1339 index = TREE_OPERAND (expr, 1);
1340 if (TREE_CODE (index) != INTEGER_CST)
1342 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1343 obstack_grow (&name_obstack, buffer, strlen (buffer));
1350 gcc_unreachable (); /* we treat these as scalars. */
1357 /* Create a human readable name for replacement variable of ACCESS. */
1360 make_fancy_name (tree expr)
1362 make_fancy_name_1 (expr);
1363 obstack_1grow (&name_obstack, '\0');
1364 return XOBFINISH (&name_obstack, char *);
1367 /* Helper function for build_ref_for_offset. */
1370 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1376 tree tr_size, index, minidx;
1377 HOST_WIDE_INT el_size;
1379 if (offset == 0 && exp_type
1380 && types_compatible_p (exp_type, type))
1383 switch (TREE_CODE (type))
1386 case QUAL_UNION_TYPE:
1388 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1390 HOST_WIDE_INT pos, size;
1391 tree expr, *expr_ptr;
1393 if (TREE_CODE (fld) != FIELD_DECL)
1396 pos = int_bit_position (fld);
1397 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1398 tr_size = DECL_SIZE (fld);
1399 if (!tr_size || !host_integerp (tr_size, 1))
1401 size = tree_low_cst (tr_size, 1);
1407 else if (pos > offset || (pos + size) <= offset)
1412 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1418 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1419 offset - pos, exp_type))
1429 tr_size = TYPE_SIZE (TREE_TYPE (type));
1430 if (!tr_size || !host_integerp (tr_size, 1))
1432 el_size = tree_low_cst (tr_size, 1);
1434 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1435 if (TREE_CODE (minidx) != INTEGER_CST)
1439 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1440 if (!integer_zerop (minidx))
1441 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1442 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1443 NULL_TREE, NULL_TREE);
1445 offset = offset % el_size;
1446 type = TREE_TYPE (type);
1461 /* Construct an expression that would reference a part of aggregate *EXPR of
1462 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1463 function only determines whether it can build such a reference without
1464 actually doing it, otherwise, the tree it points to is unshared first and
1465 then used as a base for furhter sub-references.
1467 FIXME: Eventually this should be replaced with
1468 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1469 minor rewrite of fold_stmt.
1473 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1474 tree exp_type, bool allow_ptr)
1476 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1479 *expr = unshare_expr (*expr);
1481 if (allow_ptr && POINTER_TYPE_P (type))
1483 type = TREE_TYPE (type);
1485 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1488 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1491 /* Return true iff TYPE is stdarg va_list type. */
1494 is_va_list_type (tree type)
1496 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1499 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1500 those with type which is suitable for scalarization. */
1503 find_var_candidates (void)
1506 referenced_var_iterator rvi;
1509 FOR_EACH_REFERENCED_VAR (var, rvi)
1511 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1513 type = TREE_TYPE (var);
1515 if (!AGGREGATE_TYPE_P (type)
1516 || needs_to_live_in_memory (var)
1517 || TREE_THIS_VOLATILE (var)
1518 || !COMPLETE_TYPE_P (type)
1519 || !host_integerp (TYPE_SIZE (type), 1)
1520 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1521 || type_internals_preclude_sra_p (type)
1522 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1523 we also want to schedule it rather late. Thus we ignore it in
1525 || (sra_mode == SRA_MODE_EARLY_INTRA
1526 && is_va_list_type (type)))
1529 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1531 if (dump_file && (dump_flags & TDF_DETAILS))
1533 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1534 print_generic_expr (dump_file, var, 0);
1535 fprintf (dump_file, "\n");
1543 /* Sort all accesses for the given variable, check for partial overlaps and
1544 return NULL if there are any. If there are none, pick a representative for
1545 each combination of offset and size and create a linked list out of them.
1546 Return the pointer to the first representative and make sure it is the first
1547 one in the vector of accesses. */
1549 static struct access *
1550 sort_and_splice_var_accesses (tree var)
1552 int i, j, access_count;
1553 struct access *res, **prev_acc_ptr = &res;
1554 VEC (access_p, heap) *access_vec;
1556 HOST_WIDE_INT low = -1, high = 0;
1558 access_vec = get_base_access_vector (var);
1561 access_count = VEC_length (access_p, access_vec);
1563 /* Sort by <OFFSET, SIZE>. */
1564 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1565 compare_access_positions);
1568 while (i < access_count)
1570 struct access *access = VEC_index (access_p, access_vec, i);
1571 bool grp_write = access->write;
1572 bool grp_read = !access->write;
1573 bool multiple_reads = false;
1574 bool total_scalarization = access->total_scalarization;
1575 bool grp_partial_lhs = access->grp_partial_lhs;
1576 bool first_scalar = is_gimple_reg_type (access->type);
1577 bool unscalarizable_region = access->grp_unscalarizable_region;
1579 if (first || access->offset >= high)
1582 low = access->offset;
1583 high = access->offset + access->size;
1585 else if (access->offset > low && access->offset + access->size > high)
1588 gcc_assert (access->offset >= low
1589 && access->offset + access->size <= high);
1592 while (j < access_count)
1594 struct access *ac2 = VEC_index (access_p, access_vec, j);
1595 if (ac2->offset != access->offset || ac2->size != access->size)
1602 multiple_reads = true;
1606 grp_partial_lhs |= ac2->grp_partial_lhs;
1607 unscalarizable_region |= ac2->grp_unscalarizable_region;
1608 total_scalarization |= ac2->total_scalarization;
1609 relink_to_new_repr (access, ac2);
1611 /* If there are both aggregate-type and scalar-type accesses with
1612 this combination of size and offset, the comparison function
1613 should have put the scalars first. */
1614 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1615 ac2->group_representative = access;
1621 access->group_representative = access;
1622 access->grp_write = grp_write;
1623 access->grp_read = grp_read;
1624 access->grp_hint = multiple_reads || total_scalarization;
1625 access->grp_partial_lhs = grp_partial_lhs;
1626 access->grp_unscalarizable_region = unscalarizable_region;
1627 if (access->first_link)
1628 add_access_to_work_queue (access);
1630 *prev_acc_ptr = access;
1631 prev_acc_ptr = &access->next_grp;
1634 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1638 /* Create a variable for the given ACCESS which determines the type, name and a
1639 few other properties. Return the variable declaration and store it also to
1640 ACCESS->replacement. */
1643 create_access_replacement (struct access *access)
1647 repl = create_tmp_var (access->type, "SR");
1649 add_referenced_var (repl);
1650 mark_sym_for_renaming (repl);
1652 if (!access->grp_partial_lhs
1653 && (TREE_CODE (access->type) == COMPLEX_TYPE
1654 || TREE_CODE (access->type) == VECTOR_TYPE))
1655 DECL_GIMPLE_REG_P (repl) = 1;
1657 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1658 DECL_ARTIFICIAL (repl) = 1;
1660 if (DECL_NAME (access->base)
1661 && !DECL_IGNORED_P (access->base)
1662 && !DECL_ARTIFICIAL (access->base))
1664 char *pretty_name = make_fancy_name (access->expr);
1666 DECL_NAME (repl) = get_identifier (pretty_name);
1667 obstack_free (&name_obstack, pretty_name);
1669 SET_DECL_DEBUG_EXPR (repl, access->expr);
1670 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1671 DECL_IGNORED_P (repl) = 0;
1674 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1675 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1679 fprintf (dump_file, "Created a replacement for ");
1680 print_generic_expr (dump_file, access->base, 0);
1681 fprintf (dump_file, " offset: %u, size: %u: ",
1682 (unsigned) access->offset, (unsigned) access->size);
1683 print_generic_expr (dump_file, repl, 0);
1684 fprintf (dump_file, "\n");
1686 sra_stats.replacements++;
1691 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1694 get_access_replacement (struct access *access)
1696 gcc_assert (access->grp_to_be_replaced);
1698 if (!access->replacement_decl)
1699 access->replacement_decl = create_access_replacement (access);
1700 return access->replacement_decl;
1703 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1704 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1705 to it is not "within" the root. */
1708 build_access_subtree (struct access **access)
1710 struct access *root = *access, *last_child = NULL;
1711 HOST_WIDE_INT limit = root->offset + root->size;
1713 *access = (*access)->next_grp;
1714 while (*access && (*access)->offset + (*access)->size <= limit)
1717 root->first_child = *access;
1719 last_child->next_sibling = *access;
1720 last_child = *access;
1722 build_access_subtree (access);
1726 /* Build a tree of access representatives, ACCESS is the pointer to the first
1727 one, others are linked in a list by the next_grp field. Decide about scalar
1728 replacements on the way, return true iff any are to be created. */
1731 build_access_trees (struct access *access)
1735 struct access *root = access;
1737 build_access_subtree (&access);
1738 root->next_grp = access;
1742 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1746 expr_with_var_bounded_array_refs_p (tree expr)
1748 while (handled_component_p (expr))
1750 if (TREE_CODE (expr) == ARRAY_REF
1751 && !host_integerp (array_ref_low_bound (expr), 0))
1753 expr = TREE_OPERAND (expr, 0);
1758 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1759 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1760 all sorts of access flags appropriately along the way, notably always ser
1761 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1764 analyze_access_subtree (struct access *root, bool allow_replacements,
1765 bool mark_read, bool mark_write)
1767 struct access *child;
1768 HOST_WIDE_INT limit = root->offset + root->size;
1769 HOST_WIDE_INT covered_to = root->offset;
1770 bool scalar = is_gimple_reg_type (root->type);
1771 bool hole = false, sth_created = false;
1772 bool direct_read = root->grp_read;
1775 root->grp_read = true;
1776 else if (root->grp_read)
1780 root->grp_write = true;
1781 else if (root->grp_write)
1784 if (root->grp_unscalarizable_region)
1785 allow_replacements = false;
1787 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1788 allow_replacements = false;
1790 for (child = root->first_child; child; child = child->next_sibling)
1792 if (!hole && child->offset < covered_to)
1795 covered_to += child->size;
1797 sth_created |= analyze_access_subtree (child, allow_replacements,
1798 mark_read, mark_write);
1800 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1801 hole |= !child->grp_covered;
1804 if (allow_replacements && scalar && !root->first_child
1806 || (direct_read && root->grp_write))
1807 /* We must not ICE later on when trying to build an access to the
1808 original data within the aggregate even when it is impossible to do in
1809 a defined way like in the PR 42703 testcase. Therefore we check
1810 pre-emptively here that we will be able to do that. */
1811 && build_ref_for_offset (NULL, TREE_TYPE (root->base), root->offset,
1814 if (dump_file && (dump_flags & TDF_DETAILS))
1816 fprintf (dump_file, "Marking ");
1817 print_generic_expr (dump_file, root->base, 0);
1818 fprintf (dump_file, " offset: %u, size: %u: ",
1819 (unsigned) root->offset, (unsigned) root->size);
1820 fprintf (dump_file, " to be replaced.\n");
1823 root->grp_to_be_replaced = 1;
1827 else if (covered_to < limit)
1830 if (sth_created && !hole)
1832 root->grp_covered = 1;
1835 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1836 root->grp_unscalarized_data = 1; /* not covered and written to */
1842 /* Analyze all access trees linked by next_grp by the means of
1843 analyze_access_subtree. */
1845 analyze_access_trees (struct access *access)
1851 if (analyze_access_subtree (access, true, false, false))
1853 access = access->next_grp;
1859 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1860 SIZE would conflict with an already existing one. If exactly such a child
1861 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1864 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1865 HOST_WIDE_INT size, struct access **exact_match)
1867 struct access *child;
1869 for (child = lacc->first_child; child; child = child->next_sibling)
1871 if (child->offset == norm_offset && child->size == size)
1873 *exact_match = child;
1877 if (child->offset < norm_offset + size
1878 && child->offset + child->size > norm_offset)
1885 /* Create a new child access of PARENT, with all properties just like MODEL
1886 except for its offset and with its grp_write false and grp_read true.
1887 Return the new access or NULL if it cannot be created. Note that this access
1888 is created long after all splicing and sorting, it's not located in any
1889 access vector and is automatically a representative of its group. */
1891 static struct access *
1892 create_artificial_child_access (struct access *parent, struct access *model,
1893 HOST_WIDE_INT new_offset)
1895 struct access *access;
1896 struct access **child;
1897 tree expr = parent->base;;
1899 gcc_assert (!model->grp_unscalarizable_region);
1901 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1902 model->type, false))
1905 access = (struct access *) pool_alloc (access_pool);
1906 memset (access, 0, sizeof (struct access));
1907 access->base = parent->base;
1908 access->expr = expr;
1909 access->offset = new_offset;
1910 access->size = model->size;
1911 access->type = model->type;
1912 access->grp_write = true;
1913 access->grp_read = false;
1915 child = &parent->first_child;
1916 while (*child && (*child)->offset < new_offset)
1917 child = &(*child)->next_sibling;
1919 access->next_sibling = *child;
1926 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1927 true if any new subaccess was created. Additionally, if RACC is a scalar
1928 access but LACC is not, change the type of the latter, if possible. */
1931 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1933 struct access *rchild;
1934 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1937 if (is_gimple_reg_type (lacc->type)
1938 || lacc->grp_unscalarizable_region
1939 || racc->grp_unscalarizable_region)
1942 if (!lacc->first_child && !racc->first_child
1943 && is_gimple_reg_type (racc->type))
1945 tree t = lacc->base;
1947 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1951 lacc->type = racc->type;
1956 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1958 struct access *new_acc = NULL;
1959 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1961 if (rchild->grp_unscalarizable_region)
1964 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1969 rchild->grp_hint = 1;
1970 new_acc->grp_hint |= new_acc->grp_read;
1971 if (rchild->first_child)
1972 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1977 /* If a (part of) a union field is on the RHS of an assignment, it can
1978 have sub-accesses which do not make sense on the LHS (PR 40351).
1979 Check that this is not the case. */
1980 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1981 rchild->type, false))
1984 rchild->grp_hint = 1;
1985 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1989 if (racc->first_child)
1990 propagate_subaccesses_across_link (new_acc, rchild);
1997 /* Propagate all subaccesses across assignment links. */
2000 propagate_all_subaccesses (void)
2002 while (work_queue_head)
2004 struct access *racc = pop_access_from_work_queue ();
2005 struct assign_link *link;
2007 gcc_assert (racc->first_link);
2009 for (link = racc->first_link; link; link = link->next)
2011 struct access *lacc = link->lacc;
2013 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2015 lacc = lacc->group_representative;
2016 if (propagate_subaccesses_across_link (lacc, racc)
2017 && lacc->first_link)
2018 add_access_to_work_queue (lacc);
2023 /* Go through all accesses collected throughout the (intraprocedural) analysis
2024 stage, exclude overlapping ones, identify representatives and build trees
2025 out of them, making decisions about scalarization on the way. Return true
2026 iff there are any to-be-scalarized variables after this stage. */
2029 analyze_all_variable_accesses (void)
2032 bitmap tmp = BITMAP_ALLOC (NULL);
2034 unsigned i, max_total_scalarization_size;
2036 max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2037 * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2039 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2040 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2041 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2043 tree var = referenced_var (i);
2045 if (TREE_CODE (var) == VAR_DECL
2046 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2047 <= max_total_scalarization_size)
2048 && type_consists_of_records_p (TREE_TYPE (var)))
2050 completely_scalarize_record (var, var, 0);
2051 if (dump_file && (dump_flags & TDF_DETAILS))
2053 fprintf (dump_file, "Will attempt to totally scalarize ");
2054 print_generic_expr (dump_file, var, 0);
2055 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2060 bitmap_copy (tmp, candidate_bitmap);
2061 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2063 tree var = referenced_var (i);
2064 struct access *access;
2066 access = sort_and_splice_var_accesses (var);
2068 build_access_trees (access);
2070 disqualify_candidate (var,
2071 "No or inhibitingly overlapping accesses.");
2074 propagate_all_subaccesses ();
2076 bitmap_copy (tmp, candidate_bitmap);
2077 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2079 tree var = referenced_var (i);
2080 struct access *access = get_first_repr_for_decl (var);
2082 if (analyze_access_trees (access))
2085 if (dump_file && (dump_flags & TDF_DETAILS))
2087 fprintf (dump_file, "\nAccess trees for ");
2088 print_generic_expr (dump_file, var, 0);
2089 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2090 dump_access_tree (dump_file, access);
2091 fprintf (dump_file, "\n");
2095 disqualify_candidate (var, "No scalar replacements to be created.");
2102 statistics_counter_event (cfun, "Scalarized aggregates", res);
2109 /* Return true iff a reference statement into aggregate AGG can be built for
2110 every single to-be-replaced accesses that is a child of ACCESS, its sibling
2111 or a child of its sibling. TOP_OFFSET is the offset from the processed
2112 access subtree that has to be subtracted from offset of each access. */
2115 ref_expr_for_all_replacements_p (struct access *access, tree agg,
2116 HOST_WIDE_INT top_offset)
2120 if (access->grp_to_be_replaced
2121 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
2122 access->offset - top_offset,
2123 access->type, false))
2126 if (access->first_child
2127 && !ref_expr_for_all_replacements_p (access->first_child, agg,
2131 access = access->next_sibling;
2138 /* Generate statements copying scalar replacements of accesses within a subtree
2139 into or out of AGG. ACCESS is the first child of the root of the subtree to
2140 be processed. AGG is an aggregate type expression (can be a declaration but
2141 does not have to be, it can for example also be an indirect_ref).
2142 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2143 from offsets of individual accesses to get corresponding offsets for AGG.
2144 If CHUNK_SIZE is non-null, copy only replacements in the interval
2145 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2146 statement iterator used to place the new statements. WRITE should be true
2147 when the statements should write from AGG to the replacement and false if
2148 vice versa. if INSERT_AFTER is true, new statements will be added after the
2149 current statement in GSI, they will be added before the statement
2153 generate_subtree_copies (struct access *access, tree agg,
2154 HOST_WIDE_INT top_offset,
2155 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2156 gimple_stmt_iterator *gsi, bool write,
2163 if (chunk_size && access->offset >= start_offset + chunk_size)
2166 if (access->grp_to_be_replaced
2168 || access->offset + access->size > start_offset))
2170 tree repl = get_access_replacement (access);
2174 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2175 access->offset - top_offset,
2176 access->type, false);
2177 gcc_assert (ref_found);
2181 if (access->grp_partial_lhs)
2182 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2184 insert_after ? GSI_NEW_STMT
2186 stmt = gimple_build_assign (repl, expr);
2190 TREE_NO_WARNING (repl) = 1;
2191 if (access->grp_partial_lhs)
2192 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2194 insert_after ? GSI_NEW_STMT
2196 stmt = gimple_build_assign (expr, repl);
2200 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2202 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2204 sra_stats.subtree_copies++;
2207 if (access->first_child)
2208 generate_subtree_copies (access->first_child, agg, top_offset,
2209 start_offset, chunk_size, gsi,
2210 write, insert_after);
2212 access = access->next_sibling;
2217 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2218 the root of the subtree to be processed. GSI is the statement iterator used
2219 for inserting statements which are added after the current statement if
2220 INSERT_AFTER is true or before it otherwise. */
2223 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2227 struct access *child;
2229 if (access->grp_to_be_replaced)
2233 stmt = gimple_build_assign (get_access_replacement (access),
2234 fold_convert (access->type,
2235 integer_zero_node));
2237 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2239 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2243 for (child = access->first_child; child; child = child->next_sibling)
2244 init_subtree_with_zero (child, gsi, insert_after);
2247 /* Search for an access representative for the given expression EXPR and
2248 return it or NULL if it cannot be found. */
2250 static struct access *
2251 get_access_for_expr (tree expr)
2253 HOST_WIDE_INT offset, size, max_size;
2256 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2257 a different size than the size of its argument and we need the latter
2259 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2260 expr = TREE_OPERAND (expr, 0);
2262 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2263 if (max_size == -1 || !DECL_P (base))
2266 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2269 return get_var_base_offset_size_access (base, offset, max_size);
2272 /* Callback for scan_function. Replace the expression EXPR with a scalar
2273 replacement if there is one and generate other statements to do type
2274 conversion or subtree copying if necessary. GSI is used to place newly
2275 created statements, WRITE is true if the expression is being written to (it
2276 is on a LHS of a statement or output in an assembly statement). */
2279 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2280 void *data ATTRIBUTE_UNUSED)
2282 struct access *access;
2285 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2288 expr = &TREE_OPERAND (*expr, 0);
2293 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2294 expr = &TREE_OPERAND (*expr, 0);
2295 access = get_access_for_expr (*expr);
2298 type = TREE_TYPE (*expr);
2300 if (access->grp_to_be_replaced)
2302 tree repl = get_access_replacement (access);
2303 /* If we replace a non-register typed access simply use the original
2304 access expression to extract the scalar component afterwards.
2305 This happens if scalarizing a function return value or parameter
2306 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2307 gcc.c-torture/compile/20011217-1.c.
2309 We also want to use this when accessing a complex or vector which can
2310 be accessed as a different type too, potentially creating a need for
2311 type conversion (see PR42196) and when scalarized unions are involved
2312 in assembler statements (see PR42398). */
2313 if (!useless_type_conversion_p (type, access->type))
2315 tree ref = access->base;
2318 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2319 access->offset, access->type, false);
2326 if (access->grp_partial_lhs)
2327 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2328 false, GSI_NEW_STMT);
2329 stmt = gimple_build_assign (repl, ref);
2330 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2336 if (access->grp_partial_lhs)
2337 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2338 true, GSI_SAME_STMT);
2339 stmt = gimple_build_assign (ref, repl);
2340 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2348 if (access->first_child)
2350 HOST_WIDE_INT start_offset, chunk_size;
2352 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2353 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2355 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2356 start_offset = access->offset
2357 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2360 start_offset = chunk_size = 0;
2362 generate_subtree_copies (access->first_child, access->base, 0,
2363 start_offset, chunk_size, gsi, write, write);
2368 /* Where scalar replacements of the RHS have been written to when a replacement
2369 of a LHS of an assigments cannot be direclty loaded from a replacement of
2371 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2372 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2373 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2375 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2376 base aggregate if there are unscalarized data or directly to LHS
2379 static enum unscalarized_data_handling
2380 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2381 gimple_stmt_iterator *gsi)
2383 if (top_racc->grp_unscalarized_data)
2385 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2387 return SRA_UDH_RIGHT;
2391 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2392 0, 0, gsi, false, false);
2393 return SRA_UDH_LEFT;
2398 /* Try to generate statements to load all sub-replacements in an access
2399 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2400 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2401 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2402 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2403 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2404 the rhs top aggregate has already been refreshed by contents of its scalar
2405 reductions and is set to true if this function has to do it. */
2408 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2409 HOST_WIDE_INT left_offset,
2410 HOST_WIDE_INT right_offset,
2411 gimple_stmt_iterator *old_gsi,
2412 gimple_stmt_iterator *new_gsi,
2413 enum unscalarized_data_handling *refreshed,
2416 location_t loc = EXPR_LOCATION (lacc->expr);
2419 if (lacc->grp_to_be_replaced)
2421 struct access *racc;
2422 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2426 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2427 if (racc && racc->grp_to_be_replaced)
2429 rhs = get_access_replacement (racc);
2430 if (!useless_type_conversion_p (lacc->type, racc->type))
2431 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2435 /* No suitable access on the right hand side, need to load from
2436 the aggregate. See if we have to update it first... */
2437 if (*refreshed == SRA_UDH_NONE)
2438 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2441 if (*refreshed == SRA_UDH_LEFT)
2446 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2447 lacc->offset, lacc->type,
2449 gcc_assert (repl_found);
2455 rhs = top_racc->base;
2456 repl_found = build_ref_for_offset (&rhs,
2457 TREE_TYPE (top_racc->base),
2458 offset, lacc->type, false);
2459 gcc_assert (repl_found);
2463 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2464 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2466 sra_stats.subreplacements++;
2468 else if (*refreshed == SRA_UDH_NONE
2469 && lacc->grp_read && !lacc->grp_covered)
2470 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2473 if (lacc->first_child)
2474 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2475 left_offset, right_offset,
2476 old_gsi, new_gsi, refreshed, lhs);
2477 lacc = lacc->next_sibling;
2482 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2483 to the assignment and GSI is the statement iterator pointing at it. Returns
2484 the same values as sra_modify_assign. */
2486 static enum scan_assign_result
2487 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2489 tree lhs = gimple_assign_lhs (*stmt);
2492 acc = get_access_for_expr (lhs);
2496 if (VEC_length (constructor_elt,
2497 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2499 /* I have never seen this code path trigger but if it can happen the
2500 following should handle it gracefully. */
2501 if (access_has_children_p (acc))
2502 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2504 return SRA_SA_PROCESSED;
2507 if (acc->grp_covered)
2509 init_subtree_with_zero (acc, gsi, false);
2510 unlink_stmt_vdef (*stmt);
2511 gsi_remove (gsi, true);
2512 return SRA_SA_REMOVED;
2516 init_subtree_with_zero (acc, gsi, true);
2517 return SRA_SA_PROCESSED;
2522 /* Callback of scan_function to process assign statements. It examines both
2523 sides of the statement, replaces them with a scalare replacement if there is
2524 one and generating copying of replacements if scalarized aggregates have been
2525 used in the assignment. STMT is a pointer to the assign statement, GSI is
2526 used to hold generated statements for type conversions and subtree
2529 static enum scan_assign_result
2530 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2531 void *data ATTRIBUTE_UNUSED)
2533 struct access *lacc, *racc;
2535 bool modify_this_stmt = false;
2536 bool force_gimple_rhs = false;
2537 location_t loc = gimple_location (*stmt);
2538 gimple_stmt_iterator orig_gsi = *gsi;
2540 if (!gimple_assign_single_p (*stmt))
2542 lhs = gimple_assign_lhs (*stmt);
2543 rhs = gimple_assign_rhs1 (*stmt);
2545 if (TREE_CODE (rhs) == CONSTRUCTOR)
2546 return sra_modify_constructor_assign (stmt, gsi);
2548 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2549 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2550 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2552 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2554 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2556 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2559 lacc = get_access_for_expr (lhs);
2560 racc = get_access_for_expr (rhs);
2564 if (lacc && lacc->grp_to_be_replaced)
2566 lhs = get_access_replacement (lacc);
2567 gimple_assign_set_lhs (*stmt, lhs);
2568 modify_this_stmt = true;
2569 if (lacc->grp_partial_lhs)
2570 force_gimple_rhs = true;
2574 if (racc && racc->grp_to_be_replaced)
2576 rhs = get_access_replacement (racc);
2577 modify_this_stmt = true;
2578 if (racc->grp_partial_lhs)
2579 force_gimple_rhs = true;
2583 if (modify_this_stmt)
2585 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2587 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2588 ??? This should move to fold_stmt which we simply should
2589 call after building a VIEW_CONVERT_EXPR here. */
2590 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2591 && !access_has_children_p (lacc))
2594 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2595 TREE_TYPE (rhs), false))
2598 gimple_assign_set_lhs (*stmt, expr);
2601 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2602 && !access_has_children_p (racc))
2605 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2606 TREE_TYPE (lhs), false))
2609 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2611 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2612 if (is_gimple_reg_type (TREE_TYPE (lhs))
2613 && TREE_CODE (lhs) != SSA_NAME)
2614 force_gimple_rhs = true;
2619 /* From this point on, the function deals with assignments in between
2620 aggregates when at least one has scalar reductions of some of its
2621 components. There are three possible scenarios: Both the LHS and RHS have
2622 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2624 In the first case, we would like to load the LHS components from RHS
2625 components whenever possible. If that is not possible, we would like to
2626 read it directly from the RHS (after updating it by storing in it its own
2627 components). If there are some necessary unscalarized data in the LHS,
2628 those will be loaded by the original assignment too. If neither of these
2629 cases happen, the original statement can be removed. Most of this is done
2630 by load_assign_lhs_subreplacements.
2632 In the second case, we would like to store all RHS scalarized components
2633 directly into LHS and if they cover the aggregate completely, remove the
2634 statement too. In the third case, we want the LHS components to be loaded
2635 directly from the RHS (DSE will remove the original statement if it
2638 This is a bit complex but manageable when types match and when unions do
2639 not cause confusion in a way that we cannot really load a component of LHS
2640 from the RHS or vice versa (the access representing this level can have
2641 subaccesses that are accessible only through a different union field at a
2642 higher level - different from the one used in the examined expression).
2645 Therefore, I specially handle a fourth case, happening when there is a
2646 specific type cast or it is impossible to locate a scalarized subaccess on
2647 the other side of the expression. If that happens, I simply "refresh" the
2648 RHS by storing in it is scalarized components leave the original statement
2649 there to do the copying and then load the scalar replacements of the LHS.
2650 This is what the first branch does. */
2652 if (gimple_has_volatile_ops (*stmt)
2653 || contains_view_convert_expr_p (rhs)
2654 || contains_view_convert_expr_p (lhs)
2655 || (access_has_children_p (racc)
2656 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2657 || (access_has_children_p (lacc)
2658 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2660 if (access_has_children_p (racc))
2661 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2663 if (access_has_children_p (lacc))
2664 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2666 sra_stats.separate_lhs_rhs_handling++;
2670 if (access_has_children_p (lacc) && access_has_children_p (racc))
2672 gimple_stmt_iterator orig_gsi = *gsi;
2673 enum unscalarized_data_handling refreshed;
2675 if (lacc->grp_read && !lacc->grp_covered)
2676 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2678 refreshed = SRA_UDH_NONE;
2680 load_assign_lhs_subreplacements (lacc->first_child, racc,
2681 lacc->offset, racc->offset,
2682 &orig_gsi, gsi, &refreshed, lhs);
2683 if (refreshed != SRA_UDH_RIGHT)
2685 if (*stmt == gsi_stmt (*gsi))
2688 unlink_stmt_vdef (*stmt);
2689 gsi_remove (&orig_gsi, true);
2690 sra_stats.deleted++;
2691 return SRA_SA_REMOVED;
2696 if (access_has_children_p (racc))
2698 if (!racc->grp_unscalarized_data
2699 /* Do not remove SSA name definitions (PR 42704). */
2700 && TREE_CODE (lhs) != SSA_NAME)
2702 generate_subtree_copies (racc->first_child, lhs,
2703 racc->offset, 0, 0, gsi,
2705 gcc_assert (*stmt == gsi_stmt (*gsi));
2706 unlink_stmt_vdef (*stmt);
2707 gsi_remove (gsi, true);
2708 sra_stats.deleted++;
2709 return SRA_SA_REMOVED;
2712 generate_subtree_copies (racc->first_child, lhs,
2713 racc->offset, 0, 0, gsi, false, true);
2715 else if (access_has_children_p (lacc))
2716 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2717 0, 0, gsi, true, true);
2721 /* This gimplification must be done after generate_subtree_copies, lest we
2722 insert the subtree copies in the middle of the gimplified sequence. */
2723 if (force_gimple_rhs)
2724 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
2725 true, GSI_SAME_STMT);
2726 if (gimple_assign_rhs1 (*stmt) != rhs)
2728 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
2729 gcc_assert (*stmt == gsi_stmt (orig_gsi));
2732 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2735 /* Generate statements initializing scalar replacements of parts of function
2739 initialize_parameter_reductions (void)
2741 gimple_stmt_iterator gsi;
2742 gimple_seq seq = NULL;
2745 for (parm = DECL_ARGUMENTS (current_function_decl);
2747 parm = TREE_CHAIN (parm))
2749 VEC (access_p, heap) *access_vec;
2750 struct access *access;
2752 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2754 access_vec = get_base_access_vector (parm);
2760 seq = gimple_seq_alloc ();
2761 gsi = gsi_start (seq);
2764 for (access = VEC_index (access_p, access_vec, 0);
2766 access = access->next_grp)
2767 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2771 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2774 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2775 it reveals there are components of some aggregates to be scalarized, it runs
2776 the required transformations. */
2778 perform_intra_sra (void)
2783 if (!find_var_candidates ())
2786 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2790 if (!analyze_all_variable_accesses ())
2793 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2794 initialize_parameter_reductions ();
2796 statistics_counter_event (cfun, "Scalar replacements created",
2797 sra_stats.replacements);
2798 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2799 statistics_counter_event (cfun, "Subtree copy stmts",
2800 sra_stats.subtree_copies);
2801 statistics_counter_event (cfun, "Subreplacement stmts",
2802 sra_stats.subreplacements);
2803 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2804 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2805 sra_stats.separate_lhs_rhs_handling);
2807 ret = TODO_update_ssa;
2810 sra_deinitialize ();
2814 /* Perform early intraprocedural SRA. */
2816 early_intra_sra (void)
2818 sra_mode = SRA_MODE_EARLY_INTRA;
2819 return perform_intra_sra ();
2822 /* Perform "late" intraprocedural SRA. */
2824 late_intra_sra (void)
2826 sra_mode = SRA_MODE_INTRA;
2827 return perform_intra_sra ();
2832 gate_intra_sra (void)
2834 return flag_tree_sra != 0;
2838 struct gimple_opt_pass pass_sra_early =
2843 gate_intra_sra, /* gate */
2844 early_intra_sra, /* execute */
2847 0, /* static_pass_number */
2848 TV_TREE_SRA, /* tv_id */
2849 PROP_cfg | PROP_ssa, /* properties_required */
2850 0, /* properties_provided */
2851 0, /* properties_destroyed */
2852 0, /* todo_flags_start */
2856 | TODO_verify_ssa /* todo_flags_finish */
2860 struct gimple_opt_pass pass_sra =
2865 gate_intra_sra, /* gate */
2866 late_intra_sra, /* execute */
2869 0, /* static_pass_number */
2870 TV_TREE_SRA, /* tv_id */
2871 PROP_cfg | PROP_ssa, /* properties_required */
2872 0, /* properties_provided */
2873 0, /* properties_destroyed */
2874 TODO_update_address_taken, /* todo_flags_start */
2878 | TODO_verify_ssa /* todo_flags_finish */
2883 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2887 is_unused_scalar_param (tree parm)
2890 return (is_gimple_reg (parm)
2891 && (!(name = gimple_default_def (cfun, parm))
2892 || has_zero_uses (name)));
2895 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2896 examine whether there are any direct or otherwise infeasible ones. If so,
2897 return true, otherwise return false. PARM must be a gimple register with a
2898 non-NULL default definition. */
2901 ptr_parm_has_direct_uses (tree parm)
2903 imm_use_iterator ui;
2905 tree name = gimple_default_def (cfun, parm);
2908 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2911 use_operand_p use_p;
2913 if (is_gimple_debug (stmt))
2916 /* Valid uses include dereferences on the lhs and the rhs. */
2917 if (gimple_has_lhs (stmt))
2919 tree lhs = gimple_get_lhs (stmt);
2920 while (handled_component_p (lhs))
2921 lhs = TREE_OPERAND (lhs, 0);
2922 if (INDIRECT_REF_P (lhs)
2923 && TREE_OPERAND (lhs, 0) == name)
2926 if (gimple_assign_single_p (stmt))
2928 tree rhs = gimple_assign_rhs1 (stmt);
2929 while (handled_component_p (rhs))
2930 rhs = TREE_OPERAND (rhs, 0);
2931 if (INDIRECT_REF_P (rhs)
2932 && TREE_OPERAND (rhs, 0) == name)
2935 else if (is_gimple_call (stmt))
2938 for (i = 0; i < gimple_call_num_args (stmt); ++i)
2940 tree arg = gimple_call_arg (stmt, i);
2941 while (handled_component_p (arg))
2942 arg = TREE_OPERAND (arg, 0);
2943 if (INDIRECT_REF_P (arg)
2944 && TREE_OPERAND (arg, 0) == name)
2949 /* If the number of valid uses does not match the number of
2950 uses in this stmt there is an unhandled use. */
2951 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
2958 BREAK_FROM_IMM_USE_STMT (ui);
2964 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2965 them in candidate_bitmap. Note that these do not necessarily include
2966 parameter which are unused and thus can be removed. Return true iff any
2967 such candidate has been found. */
2970 find_param_candidates (void)
2976 for (parm = DECL_ARGUMENTS (current_function_decl);
2978 parm = TREE_CHAIN (parm))
2980 tree type = TREE_TYPE (parm);
2984 if (TREE_THIS_VOLATILE (parm)
2985 || TREE_ADDRESSABLE (parm)
2986 || is_va_list_type (type))
2989 if (is_unused_scalar_param (parm))
2995 if (POINTER_TYPE_P (type))
2997 type = TREE_TYPE (type);
2999 if (TREE_CODE (type) == FUNCTION_TYPE
3000 || TYPE_VOLATILE (type)
3001 || !is_gimple_reg (parm)
3002 || is_va_list_type (type)
3003 || ptr_parm_has_direct_uses (parm))
3006 else if (!AGGREGATE_TYPE_P (type))
3009 if (!COMPLETE_TYPE_P (type)
3010 || !host_integerp (TYPE_SIZE (type), 1)
3011 || tree_low_cst (TYPE_SIZE (type), 1) == 0
3012 || (AGGREGATE_TYPE_P (type)
3013 && type_internals_preclude_sra_p (type)))
3016 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3018 if (dump_file && (dump_flags & TDF_DETAILS))
3020 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3021 print_generic_expr (dump_file, parm, 0);
3022 fprintf (dump_file, "\n");
3026 func_param_count = count;
3030 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3034 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3037 struct access *repr = (struct access *) data;
3039 repr->grp_maybe_modified = 1;
3043 /* Analyze what representatives (in linked lists accessible from
3044 REPRESENTATIVES) can be modified by side effects of statements in the
3045 current function. */
3048 analyze_modified_params (VEC (access_p, heap) *representatives)
3052 for (i = 0; i < func_param_count; i++)
3054 struct access *repr;
3056 for (repr = VEC_index (access_p, representatives, i);
3058 repr = repr->next_grp)
3060 struct access *access;
3064 if (no_accesses_p (repr))
3066 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3067 || repr->grp_maybe_modified)
3070 ao_ref_init (&ar, repr->expr);
3071 visited = BITMAP_ALLOC (NULL);
3072 for (access = repr; access; access = access->next_sibling)
3074 /* All accesses are read ones, otherwise grp_maybe_modified would
3075 be trivially set. */
3076 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3077 mark_maybe_modified, repr, &visited);
3078 if (repr->grp_maybe_modified)
3081 BITMAP_FREE (visited);
3086 /* Propagate distances in bb_dereferences in the opposite direction than the
3087 control flow edges, in each step storing the maximum of the current value
3088 and the minimum of all successors. These steps are repeated until the table
3089 stabilizes. Note that BBs which might terminate the functions (according to
3090 final_bbs bitmap) never updated in this way. */
3093 propagate_dereference_distances (void)
3095 VEC (basic_block, heap) *queue;
3098 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3099 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3102 VEC_quick_push (basic_block, queue, bb);
3106 while (!VEC_empty (basic_block, queue))
3110 bool change = false;
3113 bb = VEC_pop (basic_block, queue);
3116 if (bitmap_bit_p (final_bbs, bb->index))
3119 for (i = 0; i < func_param_count; i++)
3121 int idx = bb->index * func_param_count + i;
3123 HOST_WIDE_INT inh = 0;
3125 FOR_EACH_EDGE (e, ei, bb->succs)
3127 int succ_idx = e->dest->index * func_param_count + i;
3129 if (e->src == EXIT_BLOCK_PTR)
3135 inh = bb_dereferences [succ_idx];
3137 else if (bb_dereferences [succ_idx] < inh)
3138 inh = bb_dereferences [succ_idx];
3141 if (!first && bb_dereferences[idx] < inh)
3143 bb_dereferences[idx] = inh;
3148 if (change && !bitmap_bit_p (final_bbs, bb->index))
3149 FOR_EACH_EDGE (e, ei, bb->preds)
3154 e->src->aux = e->src;
3155 VEC_quick_push (basic_block, queue, e->src);
3159 VEC_free (basic_block, heap, queue);
3162 /* Dump a dereferences TABLE with heading STR to file F. */
3165 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3169 fprintf (dump_file, str);
3170 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3172 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3173 if (bb != EXIT_BLOCK_PTR)
3176 for (i = 0; i < func_param_count; i++)
3178 int idx = bb->index * func_param_count + i;
3179 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3184 fprintf (dump_file, "\n");
3187 /* Determine what (parts of) parameters passed by reference that are not
3188 assigned to are not certainly dereferenced in this function and thus the
3189 dereferencing cannot be safely moved to the caller without potentially
3190 introducing a segfault. Mark such REPRESENTATIVES as
3191 grp_not_necessarilly_dereferenced.
3193 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3194 part is calculated rather than simple booleans are calculated for each
3195 pointer parameter to handle cases when only a fraction of the whole
3196 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3199 The maximum dereference distances for each pointer parameter and BB are
3200 already stored in bb_dereference. This routine simply propagates these
3201 values upwards by propagate_dereference_distances and then compares the
3202 distances of individual parameters in the ENTRY BB to the equivalent
3203 distances of each representative of a (fraction of a) parameter. */
3206 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3210 if (dump_file && (dump_flags & TDF_DETAILS))
3211 dump_dereferences_table (dump_file,
3212 "Dereference table before propagation:\n",
3215 propagate_dereference_distances ();
3217 if (dump_file && (dump_flags & TDF_DETAILS))
3218 dump_dereferences_table (dump_file,
3219 "Dereference table after propagation:\n",
3222 for (i = 0; i < func_param_count; i++)
3224 struct access *repr = VEC_index (access_p, representatives, i);
3225 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3227 if (!repr || no_accesses_p (repr))
3232 if ((repr->offset + repr->size) > bb_dereferences[idx])
3233 repr->grp_not_necessarilly_dereferenced = 1;
3234 repr = repr->next_grp;
3240 /* Return the representative access for the parameter declaration PARM if it is
3241 a scalar passed by reference which is not written to and the pointer value
3242 is not used directly. Thus, if it is legal to dereference it in the caller
3243 and we can rule out modifications through aliases, such parameter should be
3244 turned into one passed by value. Return NULL otherwise. */
3246 static struct access *
3247 unmodified_by_ref_scalar_representative (tree parm)
3249 int i, access_count;
3250 struct access *repr;
3251 VEC (access_p, heap) *access_vec;
3253 access_vec = get_base_access_vector (parm);
3254 gcc_assert (access_vec);
3255 repr = VEC_index (access_p, access_vec, 0);
3258 repr->group_representative = repr;
3260 access_count = VEC_length (access_p, access_vec);
3261 for (i = 1; i < access_count; i++)
3263 struct access *access = VEC_index (access_p, access_vec, i);
3266 access->group_representative = repr;
3267 access->next_sibling = repr->next_sibling;
3268 repr->next_sibling = access;
3272 repr->grp_scalar_ptr = 1;
3276 /* Return true iff this access precludes IPA-SRA of the parameter it is
3280 access_precludes_ipa_sra_p (struct access *access)
3282 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3283 is incompatible assign in a call statement (and possibly even in asm
3284 statements). This can be relaxed by using a new temporary but only for
3285 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3286 intraprocedural SRA we deal with this by keeping the old aggregate around,
3287 something we cannot do in IPA-SRA.) */
3289 && (is_gimple_call (access->stmt)
3290 || gimple_code (access->stmt) == GIMPLE_ASM))
3297 /* Sort collected accesses for parameter PARM, identify representatives for
3298 each accessed region and link them together. Return NULL if there are
3299 different but overlapping accesses, return the special ptr value meaning
3300 there are no accesses for this parameter if that is the case and return the
3301 first representative otherwise. Set *RO_GRP if there is a group of accesses
3302 with only read (i.e. no write) accesses. */
3304 static struct access *
3305 splice_param_accesses (tree parm, bool *ro_grp)
3307 int i, j, access_count, group_count;
3308 int agg_size, total_size = 0;
3309 struct access *access, *res, **prev_acc_ptr = &res;
3310 VEC (access_p, heap) *access_vec;
3312 access_vec = get_base_access_vector (parm);
3314 return &no_accesses_representant;
3315 access_count = VEC_length (access_p, access_vec);
3317 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3318 compare_access_positions);
3323 while (i < access_count)
3326 access = VEC_index (access_p, access_vec, i);
3327 modification = access->write;
3328 if (access_precludes_ipa_sra_p (access))
3331 /* Access is about to become group representative unless we find some
3332 nasty overlap which would preclude us from breaking this parameter
3336 while (j < access_count)
3338 struct access *ac2 = VEC_index (access_p, access_vec, j);
3339 if (ac2->offset != access->offset)
3341 /* All or nothing law for parameters. */
3342 if (access->offset + access->size > ac2->offset)
3347 else if (ac2->size != access->size)
3350 if (access_precludes_ipa_sra_p (ac2))
3353 modification |= ac2->write;
3354 ac2->group_representative = access;
3355 ac2->next_sibling = access->next_sibling;
3356 access->next_sibling = ac2;
3361 access->grp_maybe_modified = modification;
3364 *prev_acc_ptr = access;
3365 prev_acc_ptr = &access->next_grp;
3366 total_size += access->size;
3370 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3371 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3373 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3374 if (total_size >= agg_size)
3377 gcc_assert (group_count > 0);
3381 /* Decide whether parameters with representative accesses given by REPR should
3382 be reduced into components. */
3385 decide_one_param_reduction (struct access *repr)
3387 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3392 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3393 gcc_assert (cur_parm_size > 0);
3395 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3398 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3403 agg_size = cur_parm_size;
3409 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3410 print_generic_expr (dump_file, parm, 0);
3411 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3412 for (acc = repr; acc; acc = acc->next_grp)
3413 dump_access (dump_file, acc, true);
3417 new_param_count = 0;
3419 for (; repr; repr = repr->next_grp)
3421 gcc_assert (parm == repr->base);
3424 if (!by_ref || (!repr->grp_maybe_modified
3425 && !repr->grp_not_necessarilly_dereferenced))
3426 total_size += repr->size;
3428 total_size += cur_parm_size;
3431 gcc_assert (new_param_count > 0);
3433 if (optimize_function_for_size_p (cfun))
3434 parm_size_limit = cur_parm_size;
3436 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3439 if (total_size < agg_size
3440 && total_size <= parm_size_limit)
3443 fprintf (dump_file, " ....will be split into %i components\n",
3445 return new_param_count;
3451 /* The order of the following enums is important, we need to do extra work for
3452 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3453 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3454 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3456 /* Identify representatives of all accesses to all candidate parameters for
3457 IPA-SRA. Return result based on what representatives have been found. */
3459 static enum ipa_splicing_result
3460 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3462 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3464 struct access *repr;
3466 *representatives = VEC_alloc (access_p, heap, func_param_count);
3468 for (parm = DECL_ARGUMENTS (current_function_decl);
3470 parm = TREE_CHAIN (parm))
3472 if (is_unused_scalar_param (parm))
3474 VEC_quick_push (access_p, *representatives,
3475 &no_accesses_representant);
3476 if (result == NO_GOOD_ACCESS)
3477 result = UNUSED_PARAMS;
3479 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3480 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3481 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3483 repr = unmodified_by_ref_scalar_representative (parm);
3484 VEC_quick_push (access_p, *representatives, repr);
3486 result = UNMODIF_BY_REF_ACCESSES;
3488 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3490 bool ro_grp = false;
3491 repr = splice_param_accesses (parm, &ro_grp);
3492 VEC_quick_push (access_p, *representatives, repr);
3494 if (repr && !no_accesses_p (repr))
3496 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3499 result = UNMODIF_BY_REF_ACCESSES;
3500 else if (result < MODIF_BY_REF_ACCESSES)
3501 result = MODIF_BY_REF_ACCESSES;
3503 else if (result < BY_VAL_ACCESSES)
3504 result = BY_VAL_ACCESSES;
3506 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3507 result = UNUSED_PARAMS;
3510 VEC_quick_push (access_p, *representatives, NULL);
3513 if (result == NO_GOOD_ACCESS)
3515 VEC_free (access_p, heap, *representatives);
3516 *representatives = NULL;
3517 return NO_GOOD_ACCESS;
3523 /* Return the index of BASE in PARMS. Abort if it is not found. */
3526 get_param_index (tree base, VEC(tree, heap) *parms)
3530 len = VEC_length (tree, parms);
3531 for (i = 0; i < len; i++)
3532 if (VEC_index (tree, parms, i) == base)
3537 /* Convert the decisions made at the representative level into compact
3538 parameter adjustments. REPRESENTATIVES are pointers to first
3539 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3540 final number of adjustments. */
3542 static ipa_parm_adjustment_vec
3543 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3544 int adjustments_count)
3546 VEC (tree, heap) *parms;
3547 ipa_parm_adjustment_vec adjustments;
3551 gcc_assert (adjustments_count > 0);
3552 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3553 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3554 parm = DECL_ARGUMENTS (current_function_decl);
3555 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3557 struct access *repr = VEC_index (access_p, representatives, i);
3559 if (!repr || no_accesses_p (repr))
3561 struct ipa_parm_adjustment *adj;
3563 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3564 memset (adj, 0, sizeof (*adj));
3565 adj->base_index = get_param_index (parm, parms);
3568 adj->copy_param = 1;
3570 adj->remove_param = 1;
3574 struct ipa_parm_adjustment *adj;
3575 int index = get_param_index (parm, parms);
3577 for (; repr; repr = repr->next_grp)
3579 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3580 memset (adj, 0, sizeof (*adj));
3581 gcc_assert (repr->base == parm);
3582 adj->base_index = index;
3583 adj->base = repr->base;
3584 adj->type = repr->type;
3585 adj->offset = repr->offset;
3586 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3587 && (repr->grp_maybe_modified
3588 || repr->grp_not_necessarilly_dereferenced));
3593 VEC_free (tree, heap, parms);
3597 /* Analyze the collected accesses and produce a plan what to do with the
3598 parameters in the form of adjustments, NULL meaning nothing. */
3600 static ipa_parm_adjustment_vec
3601 analyze_all_param_acesses (void)
3603 enum ipa_splicing_result repr_state;
3604 bool proceed = false;
3605 int i, adjustments_count = 0;
3606 VEC (access_p, heap) *representatives;
3607 ipa_parm_adjustment_vec adjustments;
3609 repr_state = splice_all_param_accesses (&representatives);
3610 if (repr_state == NO_GOOD_ACCESS)
3613 /* If there are any parameters passed by reference which are not modified
3614 directly, we need to check whether they can be modified indirectly. */
3615 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3617 analyze_caller_dereference_legality (representatives);
3618 analyze_modified_params (representatives);
3621 for (i = 0; i < func_param_count; i++)
3623 struct access *repr = VEC_index (access_p, representatives, i);
3625 if (repr && !no_accesses_p (repr))
3627 if (repr->grp_scalar_ptr)
3629 adjustments_count++;
3630 if (repr->grp_not_necessarilly_dereferenced
3631 || repr->grp_maybe_modified)
3632 VEC_replace (access_p, representatives, i, NULL);
3636 sra_stats.scalar_by_ref_to_by_val++;
3641 int new_components = decide_one_param_reduction (repr);
3643 if (new_components == 0)
3645 VEC_replace (access_p, representatives, i, NULL);
3646 adjustments_count++;
3650 adjustments_count += new_components;
3651 sra_stats.aggregate_params_reduced++;
3652 sra_stats.param_reductions_created += new_components;
3659 if (no_accesses_p (repr))
3662 sra_stats.deleted_unused_parameters++;
3664 adjustments_count++;
3668 if (!proceed && dump_file)
3669 fprintf (dump_file, "NOT proceeding to change params.\n");
3672 adjustments = turn_representatives_into_adjustments (representatives,
3677 VEC_free (access_p, heap, representatives);
3681 /* If a parameter replacement identified by ADJ does not yet exist in the form
3682 of declaration, create it and record it, otherwise return the previously
3686 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3689 if (!adj->new_ssa_base)
3691 char *pretty_name = make_fancy_name (adj->base);
3693 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3694 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3695 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3696 DECL_GIMPLE_REG_P (repl) = 1;
3697 DECL_NAME (repl) = get_identifier (pretty_name);
3698 obstack_free (&name_obstack, pretty_name);
3701 add_referenced_var (repl);
3702 adj->new_ssa_base = repl;
3705 repl = adj->new_ssa_base;
3709 /* Find the first adjustment for a particular parameter BASE in a vector of
3710 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3713 static struct ipa_parm_adjustment *
3714 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3718 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3719 for (i = 0; i < len; i++)
3721 struct ipa_parm_adjustment *adj;
3723 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3724 if (!adj->copy_param && adj->base == base)
3731 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3732 parameter which is to be removed because its value is not used, replace the
3733 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3734 uses too and return true (update_stmt is then issued for the statement by
3735 the caller). DATA is a pointer to an adjustments vector. */
3738 replace_removed_params_ssa_names (gimple stmt, void *data)
3740 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3741 struct ipa_parm_adjustment *adj;
3742 tree lhs, decl, repl, name;
3744 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3745 if (gimple_code (stmt) == GIMPLE_PHI)
3746 lhs = gimple_phi_result (stmt);
3747 else if (is_gimple_assign (stmt))
3748 lhs = gimple_assign_lhs (stmt);
3749 else if (is_gimple_call (stmt))
3750 lhs = gimple_call_lhs (stmt);
3754 if (TREE_CODE (lhs) != SSA_NAME)
3756 decl = SSA_NAME_VAR (lhs);
3757 if (TREE_CODE (decl) != PARM_DECL)
3760 adj = get_adjustment_for_base (adjustments, decl);
3764 repl = get_replaced_param_substitute (adj);
3765 name = make_ssa_name (repl, stmt);
3769 fprintf (dump_file, "replacing an SSA name of a removed param ");
3770 print_generic_expr (dump_file, lhs, 0);
3771 fprintf (dump_file, " with ");
3772 print_generic_expr (dump_file, name, 0);
3773 fprintf (dump_file, "\n");
3776 if (is_gimple_assign (stmt))
3777 gimple_assign_set_lhs (stmt, name);
3778 else if (is_gimple_call (stmt))
3779 gimple_call_set_lhs (stmt, name);
3781 gimple_phi_set_result (stmt, name);
3783 replace_uses_by (lhs, name);
3787 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3788 expression *EXPR should be replaced by a reduction of a parameter, do so.
3789 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3790 whether the function should care about type incompatibility the current and
3791 new expressions. If it is true, the function will leave incompatibility
3792 issues to the caller.
3794 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3795 a write (LHS) expression. */
3798 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3799 bool dont_convert, void *data)
3801 ipa_parm_adjustment_vec adjustments;
3803 struct ipa_parm_adjustment *adj, *cand = NULL;
3804 HOST_WIDE_INT offset, size, max_size;
3807 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3808 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3810 if (TREE_CODE (*expr) == BIT_FIELD_REF
3811 || TREE_CODE (*expr) == IMAGPART_EXPR
3812 || TREE_CODE (*expr) == REALPART_EXPR)
3814 expr = &TREE_OPERAND (*expr, 0);
3815 dont_convert = false;
3818 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3819 if (!base || size == -1 || max_size == -1)
3822 if (INDIRECT_REF_P (base))
3823 base = TREE_OPERAND (base, 0);
3825 base = get_ssa_base_param (base);
3826 if (!base || TREE_CODE (base) != PARM_DECL)
3829 for (i = 0; i < len; i++)
3831 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3833 if (adj->base == base &&
3834 (adj->offset == offset || adj->remove_param))
3840 if (!cand || cand->copy_param || cand->remove_param)
3846 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3848 folded = gimple_fold_indirect_ref (src);
3853 src = cand->reduction;
3855 if (dump_file && (dump_flags & TDF_DETAILS))
3857 fprintf (dump_file, "About to replace expr ");
3858 print_generic_expr (dump_file, *expr, 0);
3859 fprintf (dump_file, " with ");
3860 print_generic_expr (dump_file, src, 0);
3861 fprintf (dump_file, "\n");
3865 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3867 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3875 /* Callback for scan_function to process assign statements. Performs
3876 essentially the same function like sra_ipa_modify_expr. */
3878 static enum scan_assign_result
3879 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3881 gimple stmt = *stmt_ptr;
3882 tree *lhs_p, *rhs_p;
3885 if (!gimple_assign_single_p (stmt))
3888 rhs_p = gimple_assign_rhs1_ptr (stmt);
3889 lhs_p = gimple_assign_lhs_ptr (stmt);
3891 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3892 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3895 tree new_rhs = NULL_TREE;
3897 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3899 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
3901 /* V_C_Es of constructors can cause trouble (PR 42714). */
3902 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
3903 *rhs_p = fold_convert (TREE_TYPE (*lhs_p), integer_zero_node);
3905 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
3908 new_rhs = fold_build1_loc (gimple_location (stmt),
3909 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
3912 else if (REFERENCE_CLASS_P (*rhs_p)
3913 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3914 && !is_gimple_reg (*lhs_p))
3915 /* This can happen when an assignment in between two single field
3916 structures is turned into an assignment in between two pointers to
3917 scalars (PR 42237). */
3922 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3923 true, GSI_SAME_STMT);
3925 gimple_assign_set_rhs_from_tree (gsi, tmp);
3928 return SRA_SA_PROCESSED;
3934 /* Call gimple_debug_bind_reset_value on all debug statements describing
3935 gimple register parameters that are being removed or replaced. */
3938 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3942 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3943 for (i = 0; i < len; i++)
3945 struct ipa_parm_adjustment *adj;
3946 imm_use_iterator ui;
3950 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3951 if (adj->copy_param || !is_gimple_reg (adj->base))
3953 name = gimple_default_def (cfun, adj->base);
3956 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3958 /* All other users must have been removed by scan_function. */
3959 gcc_assert (is_gimple_debug (stmt));
3960 gimple_debug_bind_reset_value (stmt);
3966 /* Return true iff all callers have at least as many actual arguments as there
3967 are formal parameters in the current function. */
3970 all_callers_have_enough_arguments_p (struct cgraph_node *node)
3972 struct cgraph_edge *cs;
3973 for (cs = node->callers; cs; cs = cs->next_caller)
3974 if (!callsite_has_enough_arguments_p (cs->call_stmt))
3981 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3984 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3986 tree old_cur_fndecl = current_function_decl;
3987 struct cgraph_edge *cs;
3988 basic_block this_block;
3989 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3991 for (cs = node->callers; cs; cs = cs->next_caller)
3993 current_function_decl = cs->caller->decl;
3994 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3997 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3998 cs->caller->uid, cs->callee->uid,
3999 cgraph_node_name (cs->caller),
4000 cgraph_node_name (cs->callee));
4002 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
4007 for (cs = node->callers; cs; cs = cs->next_caller)
4008 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
4010 compute_inline_parameters (cs->caller);
4011 bitmap_set_bit (recomputed_callers, cs->caller->uid);
4013 BITMAP_FREE (recomputed_callers);
4015 current_function_decl = old_cur_fndecl;
4017 if (!encountered_recursive_call)
4020 FOR_EACH_BB (this_block)
4022 gimple_stmt_iterator gsi;
4024 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4026 gimple stmt = gsi_stmt (gsi);
4028 if (gimple_code (stmt) != GIMPLE_CALL)
4030 call_fndecl = gimple_call_fndecl (stmt);
4031 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
4034 fprintf (dump_file, "Adjusting recursive call");
4035 ipa_modify_call_arguments (NULL, stmt, adjustments);
4043 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4044 as given in ADJUSTMENTS. */
4047 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4049 struct cgraph_node *alias;
4050 for (alias = node->same_body; alias; alias = alias->next)
4051 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
4052 /* current_function_decl must be handled last, after same_body aliases,
4053 as following functions will use what it computed. */
4054 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
4055 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
4056 replace_removed_params_ssa_names, false, adjustments);
4057 sra_ipa_reset_debug_stmts (adjustments);
4058 convert_callers (node, adjustments);
4059 cgraph_make_node_local (node);
4063 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4064 attributes, return true otherwise. NODE is the cgraph node of the current
4068 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4070 if (!cgraph_node_can_be_local_p (node))
4073 fprintf (dump_file, "Function not local to this compilation unit.\n");
4077 if (DECL_VIRTUAL_P (current_function_decl))
4080 fprintf (dump_file, "Function is a virtual method.\n");
4084 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
4085 && node->global.size >= MAX_INLINE_INSNS_AUTO)
4088 fprintf (dump_file, "Function too big to be made truly local.\n");
4096 "Function has no callers in this compilation unit.\n");
4103 fprintf (dump_file, "Function uses stdarg. \n");
4110 /* Perform early interprocedural SRA. */
4113 ipa_early_sra (void)
4115 struct cgraph_node *node = cgraph_node (current_function_decl);
4116 ipa_parm_adjustment_vec adjustments;
4119 if (!ipa_sra_preliminary_function_checks (node))
4123 sra_mode = SRA_MODE_EARLY_IPA;
4125 if (!find_param_candidates ())
4128 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
4132 if (!all_callers_have_enough_arguments_p (node))
4135 fprintf (dump_file, "There are callers with insufficient number of "
4140 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
4142 * last_basic_block_for_function (cfun));
4143 final_bbs = BITMAP_ALLOC (NULL);
4145 scan_function (build_access_from_expr, build_accesses_from_assign,
4147 if (encountered_apply_args)
4150 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4154 if (encountered_unchangable_recursive_call)
4157 fprintf (dump_file, "Function calls itself with insufficient "
4158 "number of arguments.\n");
4162 adjustments = analyze_all_param_acesses ();
4166 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4168 modify_function (node, adjustments);
4169 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4170 ret = TODO_update_ssa;
4172 statistics_counter_event (cfun, "Unused parameters deleted",
4173 sra_stats.deleted_unused_parameters);
4174 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4175 sra_stats.scalar_by_ref_to_by_val);
4176 statistics_counter_event (cfun, "Aggregate parameters broken up",
4177 sra_stats.aggregate_params_reduced);
4178 statistics_counter_event (cfun, "Aggregate parameter components created",
4179 sra_stats.param_reductions_created);
4182 BITMAP_FREE (final_bbs);
4183 free (bb_dereferences);
4185 sra_deinitialize ();
4189 /* Return if early ipa sra shall be performed. */
4191 ipa_early_sra_gate (void)
4193 return flag_ipa_sra;
4196 struct gimple_opt_pass pass_early_ipa_sra =
4200 "eipa_sra", /* name */
4201 ipa_early_sra_gate, /* gate */
4202 ipa_early_sra, /* execute */
4205 0, /* static_pass_number */
4206 TV_IPA_SRA, /* tv_id */
4207 0, /* properties_required */
4208 0, /* properties_provided */
4209 0, /* properties_destroyed */
4210 0, /* todo_flags_start */
4211 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */