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 && racc && !is_gimple_reg_type (racc->type))
1027 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1030 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1031 && !lacc->grp_unscalarizable_region
1032 && !racc->grp_unscalarizable_region
1033 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
1034 /* FIXME: Turn the following line into an assert after PR 40058 is
1036 && lacc->size == racc->size
1037 && useless_type_conversion_p (lacc->type, racc->type))
1039 struct assign_link *link;
1041 link = (struct assign_link *) pool_alloc (link_pool);
1042 memset (link, 0, sizeof (struct assign_link));
1047 add_link_to_rhs (racc, link);
1050 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
1053 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1054 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1057 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1058 void *data ATTRIBUTE_UNUSED)
1061 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1066 /* Return true iff callsite CALL has at least as many actual arguments as there
1067 are formal parameters of the function currently processed by IPA-SRA. */
1070 callsite_has_enough_arguments_p (gimple call)
1072 return gimple_call_num_args (call) >= (unsigned) func_param_count;
1075 /* Scan function and look for interesting statements. Return true if any has
1076 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
1077 called on all expressions within statements except assign statements and
1078 those deemed entirely unsuitable for some reason (all operands in such
1079 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
1080 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
1081 called on assign statements and those call statements which have a lhs, it
1082 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
1083 pass and thus no statement is being modified. DATA is a pointer passed to
1084 all callbacks. If any single callback returns true, this function also
1085 returns true, otherwise it returns false. */
1088 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
1089 enum scan_assign_result (*scan_assign) (gimple *,
1090 gimple_stmt_iterator *,
1092 bool (*handle_ssa_defs)(gimple, void *),
1093 bool analysis_stage, void *data)
1095 gimple_stmt_iterator gsi;
1103 bool bb_changed = false;
1105 if (handle_ssa_defs)
1106 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1107 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
1109 gsi = gsi_start_bb (bb);
1110 while (!gsi_end_p (gsi))
1112 gimple stmt = gsi_stmt (gsi);
1113 enum scan_assign_result assign_result;
1114 bool any = false, deleted = false;
1116 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
1117 bitmap_set_bit (final_bbs, bb->index);
1118 switch (gimple_code (stmt))
1121 t = gimple_return_retval_ptr (stmt);
1122 if (*t != NULL_TREE)
1123 any |= scan_expr (t, &gsi, false, data);
1124 if (analysis_stage && final_bbs)
1125 bitmap_set_bit (final_bbs, bb->index);
1129 assign_result = scan_assign (&stmt, &gsi, data);
1130 any |= assign_result == SRA_SA_PROCESSED;
1131 deleted = assign_result == SRA_SA_REMOVED;
1132 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1133 any |= handle_ssa_defs (stmt, data);
1137 /* Operands must be processed before the lhs. */
1138 for (i = 0; i < gimple_call_num_args (stmt); i++)
1140 tree *argp = gimple_call_arg_ptr (stmt, i);
1141 any |= scan_expr (argp, &gsi, false, data);
1144 if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
1146 tree dest = gimple_call_fndecl (stmt);
1147 int flags = gimple_call_flags (stmt);
1151 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1152 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1153 encountered_apply_args = true;
1154 if (cgraph_get_node (dest)
1155 == cgraph_get_node (current_function_decl))
1157 encountered_recursive_call = true;
1158 if (!callsite_has_enough_arguments_p (stmt))
1159 encountered_unchangable_recursive_call = true;
1164 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1165 bitmap_set_bit (final_bbs, bb->index);
1168 if (gimple_call_lhs (stmt))
1170 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1172 || !disqualify_ops_if_throwing_stmt (stmt,
1175 any |= scan_expr (lhs_ptr, &gsi, true, data);
1176 if (handle_ssa_defs)
1177 any |= handle_ssa_defs (stmt, data);
1185 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1188 bitmap_set_bit (final_bbs, bb->index);
1190 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1192 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1193 any |= scan_expr (op, &gsi, false, data);
1195 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1197 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1198 any |= scan_expr (op, &gsi, true, data);
1210 if (!analysis_stage)
1214 maybe_clean_eh_stmt (stmt);
1225 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1226 gimple_purge_dead_eh_edges (bb);
1232 /* Helper of QSORT function. There are pointers to accesses in the array. An
1233 access is considered smaller than another if it has smaller offset or if the
1234 offsets are the same but is size is bigger. */
1237 compare_access_positions (const void *a, const void *b)
1239 const access_p *fp1 = (const access_p *) a;
1240 const access_p *fp2 = (const access_p *) b;
1241 const access_p f1 = *fp1;
1242 const access_p f2 = *fp2;
1244 if (f1->offset != f2->offset)
1245 return f1->offset < f2->offset ? -1 : 1;
1247 if (f1->size == f2->size)
1249 if (f1->type == f2->type)
1251 /* Put any non-aggregate type before any aggregate type. */
1252 else if (!is_gimple_reg_type (f1->type)
1253 && is_gimple_reg_type (f2->type))
1255 else if (is_gimple_reg_type (f1->type)
1256 && !is_gimple_reg_type (f2->type))
1258 /* Put any complex or vector type before any other scalar type. */
1259 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1260 && TREE_CODE (f1->type) != VECTOR_TYPE
1261 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1262 || TREE_CODE (f2->type) == VECTOR_TYPE))
1264 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1265 || TREE_CODE (f1->type) == VECTOR_TYPE)
1266 && TREE_CODE (f2->type) != COMPLEX_TYPE
1267 && TREE_CODE (f2->type) != VECTOR_TYPE)
1269 /* Put the integral type with the bigger precision first. */
1270 else if (INTEGRAL_TYPE_P (f1->type)
1271 && INTEGRAL_TYPE_P (f2->type))
1272 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1273 /* Put any integral type with non-full precision last. */
1274 else if (INTEGRAL_TYPE_P (f1->type)
1275 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1276 != TYPE_PRECISION (f1->type)))
1278 else if (INTEGRAL_TYPE_P (f2->type)
1279 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1280 != TYPE_PRECISION (f2->type)))
1282 /* Stabilize the sort. */
1283 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1286 /* We want the bigger accesses first, thus the opposite operator in the next
1288 return f1->size > f2->size ? -1 : 1;
1292 /* Append a name of the declaration to the name obstack. A helper function for
1296 make_fancy_decl_name (tree decl)
1300 tree name = DECL_NAME (decl);
1302 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1303 IDENTIFIER_LENGTH (name));
1306 sprintf (buffer, "D%u", DECL_UID (decl));
1307 obstack_grow (&name_obstack, buffer, strlen (buffer));
1311 /* Helper for make_fancy_name. */
1314 make_fancy_name_1 (tree expr)
1321 make_fancy_decl_name (expr);
1325 switch (TREE_CODE (expr))
1328 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1329 obstack_1grow (&name_obstack, '$');
1330 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1334 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1335 obstack_1grow (&name_obstack, '$');
1336 /* Arrays with only one element may not have a constant as their
1338 index = TREE_OPERAND (expr, 1);
1339 if (TREE_CODE (index) != INTEGER_CST)
1341 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1342 obstack_grow (&name_obstack, buffer, strlen (buffer));
1349 gcc_unreachable (); /* we treat these as scalars. */
1356 /* Create a human readable name for replacement variable of ACCESS. */
1359 make_fancy_name (tree expr)
1361 make_fancy_name_1 (expr);
1362 obstack_1grow (&name_obstack, '\0');
1363 return XOBFINISH (&name_obstack, char *);
1366 /* Helper function for build_ref_for_offset. */
1369 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1375 tree tr_size, index, minidx;
1376 HOST_WIDE_INT el_size;
1378 if (offset == 0 && exp_type
1379 && types_compatible_p (exp_type, type))
1382 switch (TREE_CODE (type))
1385 case QUAL_UNION_TYPE:
1387 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1389 HOST_WIDE_INT pos, size;
1390 tree expr, *expr_ptr;
1392 if (TREE_CODE (fld) != FIELD_DECL)
1395 pos = int_bit_position (fld);
1396 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1397 tr_size = DECL_SIZE (fld);
1398 if (!tr_size || !host_integerp (tr_size, 1))
1400 size = tree_low_cst (tr_size, 1);
1406 else if (pos > offset || (pos + size) <= offset)
1411 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1417 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1418 offset - pos, exp_type))
1428 tr_size = TYPE_SIZE (TREE_TYPE (type));
1429 if (!tr_size || !host_integerp (tr_size, 1))
1431 el_size = tree_low_cst (tr_size, 1);
1433 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1434 if (TREE_CODE (minidx) != INTEGER_CST)
1438 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1439 if (!integer_zerop (minidx))
1440 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1441 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1442 NULL_TREE, NULL_TREE);
1444 offset = offset % el_size;
1445 type = TREE_TYPE (type);
1460 /* Construct an expression that would reference a part of aggregate *EXPR of
1461 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1462 function only determines whether it can build such a reference without
1463 actually doing it, otherwise, the tree it points to is unshared first and
1464 then used as a base for furhter sub-references.
1466 FIXME: Eventually this should be replaced with
1467 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1468 minor rewrite of fold_stmt.
1472 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1473 tree exp_type, bool allow_ptr)
1475 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1478 *expr = unshare_expr (*expr);
1480 if (allow_ptr && POINTER_TYPE_P (type))
1482 type = TREE_TYPE (type);
1484 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1487 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1490 /* Return true iff TYPE is stdarg va_list type. */
1493 is_va_list_type (tree type)
1495 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1498 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1499 those with type which is suitable for scalarization. */
1502 find_var_candidates (void)
1505 referenced_var_iterator rvi;
1508 FOR_EACH_REFERENCED_VAR (var, rvi)
1510 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1512 type = TREE_TYPE (var);
1514 if (!AGGREGATE_TYPE_P (type)
1515 || needs_to_live_in_memory (var)
1516 || TREE_THIS_VOLATILE (var)
1517 || !COMPLETE_TYPE_P (type)
1518 || !host_integerp (TYPE_SIZE (type), 1)
1519 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1520 || type_internals_preclude_sra_p (type)
1521 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1522 we also want to schedule it rather late. Thus we ignore it in
1524 || (sra_mode == SRA_MODE_EARLY_INTRA
1525 && is_va_list_type (type)))
1528 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1530 if (dump_file && (dump_flags & TDF_DETAILS))
1532 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1533 print_generic_expr (dump_file, var, 0);
1534 fprintf (dump_file, "\n");
1542 /* Sort all accesses for the given variable, check for partial overlaps and
1543 return NULL if there are any. If there are none, pick a representative for
1544 each combination of offset and size and create a linked list out of them.
1545 Return the pointer to the first representative and make sure it is the first
1546 one in the vector of accesses. */
1548 static struct access *
1549 sort_and_splice_var_accesses (tree var)
1551 int i, j, access_count;
1552 struct access *res, **prev_acc_ptr = &res;
1553 VEC (access_p, heap) *access_vec;
1555 HOST_WIDE_INT low = -1, high = 0;
1557 access_vec = get_base_access_vector (var);
1560 access_count = VEC_length (access_p, access_vec);
1562 /* Sort by <OFFSET, SIZE>. */
1563 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1564 compare_access_positions);
1567 while (i < access_count)
1569 struct access *access = VEC_index (access_p, access_vec, i);
1570 bool grp_write = access->write;
1571 bool grp_read = !access->write;
1572 bool multiple_reads = false;
1573 bool total_scalarization = access->total_scalarization;
1574 bool grp_partial_lhs = access->grp_partial_lhs;
1575 bool first_scalar = is_gimple_reg_type (access->type);
1576 bool unscalarizable_region = access->grp_unscalarizable_region;
1578 if (first || access->offset >= high)
1581 low = access->offset;
1582 high = access->offset + access->size;
1584 else if (access->offset > low && access->offset + access->size > high)
1587 gcc_assert (access->offset >= low
1588 && access->offset + access->size <= high);
1591 while (j < access_count)
1593 struct access *ac2 = VEC_index (access_p, access_vec, j);
1594 if (ac2->offset != access->offset || ac2->size != access->size)
1601 multiple_reads = true;
1605 grp_partial_lhs |= ac2->grp_partial_lhs;
1606 unscalarizable_region |= ac2->grp_unscalarizable_region;
1607 total_scalarization |= ac2->total_scalarization;
1608 relink_to_new_repr (access, ac2);
1610 /* If there are both aggregate-type and scalar-type accesses with
1611 this combination of size and offset, the comparison function
1612 should have put the scalars first. */
1613 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1614 ac2->group_representative = access;
1620 access->group_representative = access;
1621 access->grp_write = grp_write;
1622 access->grp_read = grp_read;
1623 access->grp_hint = multiple_reads || total_scalarization;
1624 access->grp_partial_lhs = grp_partial_lhs;
1625 access->grp_unscalarizable_region = unscalarizable_region;
1626 if (access->first_link)
1627 add_access_to_work_queue (access);
1629 *prev_acc_ptr = access;
1630 prev_acc_ptr = &access->next_grp;
1633 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1637 /* Create a variable for the given ACCESS which determines the type, name and a
1638 few other properties. Return the variable declaration and store it also to
1639 ACCESS->replacement. */
1642 create_access_replacement (struct access *access)
1646 repl = create_tmp_var (access->type, "SR");
1648 add_referenced_var (repl);
1649 mark_sym_for_renaming (repl);
1651 if (!access->grp_partial_lhs
1652 && (TREE_CODE (access->type) == COMPLEX_TYPE
1653 || TREE_CODE (access->type) == VECTOR_TYPE))
1654 DECL_GIMPLE_REG_P (repl) = 1;
1656 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1657 DECL_ARTIFICIAL (repl) = 1;
1659 if (DECL_NAME (access->base)
1660 && !DECL_IGNORED_P (access->base)
1661 && !DECL_ARTIFICIAL (access->base))
1663 char *pretty_name = make_fancy_name (access->expr);
1665 DECL_NAME (repl) = get_identifier (pretty_name);
1666 obstack_free (&name_obstack, pretty_name);
1668 SET_DECL_DEBUG_EXPR (repl, access->expr);
1669 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1670 DECL_IGNORED_P (repl) = 0;
1673 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1674 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1678 fprintf (dump_file, "Created a replacement for ");
1679 print_generic_expr (dump_file, access->base, 0);
1680 fprintf (dump_file, " offset: %u, size: %u: ",
1681 (unsigned) access->offset, (unsigned) access->size);
1682 print_generic_expr (dump_file, repl, 0);
1683 fprintf (dump_file, "\n");
1685 sra_stats.replacements++;
1690 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1693 get_access_replacement (struct access *access)
1695 gcc_assert (access->grp_to_be_replaced);
1697 if (!access->replacement_decl)
1698 access->replacement_decl = create_access_replacement (access);
1699 return access->replacement_decl;
1702 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1703 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1704 to it is not "within" the root. */
1707 build_access_subtree (struct access **access)
1709 struct access *root = *access, *last_child = NULL;
1710 HOST_WIDE_INT limit = root->offset + root->size;
1712 *access = (*access)->next_grp;
1713 while (*access && (*access)->offset + (*access)->size <= limit)
1716 root->first_child = *access;
1718 last_child->next_sibling = *access;
1719 last_child = *access;
1721 build_access_subtree (access);
1725 /* Build a tree of access representatives, ACCESS is the pointer to the first
1726 one, others are linked in a list by the next_grp field. Decide about scalar
1727 replacements on the way, return true iff any are to be created. */
1730 build_access_trees (struct access *access)
1734 struct access *root = access;
1736 build_access_subtree (&access);
1737 root->next_grp = access;
1741 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1745 expr_with_var_bounded_array_refs_p (tree expr)
1747 while (handled_component_p (expr))
1749 if (TREE_CODE (expr) == ARRAY_REF
1750 && !host_integerp (array_ref_low_bound (expr), 0))
1752 expr = TREE_OPERAND (expr, 0);
1757 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1758 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1759 all sorts of access flags appropriately along the way, notably always ser
1760 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1763 analyze_access_subtree (struct access *root, bool allow_replacements,
1764 bool mark_read, bool mark_write)
1766 struct access *child;
1767 HOST_WIDE_INT limit = root->offset + root->size;
1768 HOST_WIDE_INT covered_to = root->offset;
1769 bool scalar = is_gimple_reg_type (root->type);
1770 bool hole = false, sth_created = false;
1771 bool direct_read = root->grp_read;
1774 root->grp_read = true;
1775 else if (root->grp_read)
1779 root->grp_write = true;
1780 else if (root->grp_write)
1783 if (root->grp_unscalarizable_region)
1784 allow_replacements = false;
1786 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1787 allow_replacements = false;
1789 for (child = root->first_child; child; child = child->next_sibling)
1791 if (!hole && child->offset < covered_to)
1794 covered_to += child->size;
1796 sth_created |= analyze_access_subtree (child, allow_replacements,
1797 mark_read, mark_write);
1799 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1800 hole |= !child->grp_covered;
1803 if (allow_replacements && scalar && !root->first_child
1805 || (direct_read && root->grp_write))
1806 /* We must not ICE later on when trying to build an access to the
1807 original data within the aggregate even when it is impossible to do in
1808 a defined way like in the PR 42703 testcase. Therefore we check
1809 pre-emptively here that we will be able to do that. */
1810 && build_ref_for_offset (NULL, TREE_TYPE (root->base), root->offset,
1813 if (dump_file && (dump_flags & TDF_DETAILS))
1815 fprintf (dump_file, "Marking ");
1816 print_generic_expr (dump_file, root->base, 0);
1817 fprintf (dump_file, " offset: %u, size: %u: ",
1818 (unsigned) root->offset, (unsigned) root->size);
1819 fprintf (dump_file, " to be replaced.\n");
1822 root->grp_to_be_replaced = 1;
1826 else if (covered_to < limit)
1829 if (sth_created && !hole)
1831 root->grp_covered = 1;
1834 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1835 root->grp_unscalarized_data = 1; /* not covered and written to */
1841 /* Analyze all access trees linked by next_grp by the means of
1842 analyze_access_subtree. */
1844 analyze_access_trees (struct access *access)
1850 if (analyze_access_subtree (access, true, false, false))
1852 access = access->next_grp;
1858 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1859 SIZE would conflict with an already existing one. If exactly such a child
1860 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1863 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1864 HOST_WIDE_INT size, struct access **exact_match)
1866 struct access *child;
1868 for (child = lacc->first_child; child; child = child->next_sibling)
1870 if (child->offset == norm_offset && child->size == size)
1872 *exact_match = child;
1876 if (child->offset < norm_offset + size
1877 && child->offset + child->size > norm_offset)
1884 /* Create a new child access of PARENT, with all properties just like MODEL
1885 except for its offset and with its grp_write false and grp_read true.
1886 Return the new access or NULL if it cannot be created. Note that this access
1887 is created long after all splicing and sorting, it's not located in any
1888 access vector and is automatically a representative of its group. */
1890 static struct access *
1891 create_artificial_child_access (struct access *parent, struct access *model,
1892 HOST_WIDE_INT new_offset)
1894 struct access *access;
1895 struct access **child;
1896 tree expr = parent->base;;
1898 gcc_assert (!model->grp_unscalarizable_region);
1900 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1901 model->type, false))
1904 access = (struct access *) pool_alloc (access_pool);
1905 memset (access, 0, sizeof (struct access));
1906 access->base = parent->base;
1907 access->expr = expr;
1908 access->offset = new_offset;
1909 access->size = model->size;
1910 access->type = model->type;
1911 access->grp_write = true;
1912 access->grp_read = false;
1914 child = &parent->first_child;
1915 while (*child && (*child)->offset < new_offset)
1916 child = &(*child)->next_sibling;
1918 access->next_sibling = *child;
1925 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1926 true if any new subaccess was created. Additionally, if RACC is a scalar
1927 access but LACC is not, change the type of the latter, if possible. */
1930 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1932 struct access *rchild;
1933 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1936 if (is_gimple_reg_type (lacc->type)
1937 || lacc->grp_unscalarizable_region
1938 || racc->grp_unscalarizable_region)
1941 if (!lacc->first_child && !racc->first_child
1942 && is_gimple_reg_type (racc->type))
1944 tree t = lacc->base;
1946 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1950 lacc->type = racc->type;
1955 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1957 struct access *new_acc = NULL;
1958 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1960 if (rchild->grp_unscalarizable_region)
1963 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1968 rchild->grp_hint = 1;
1969 new_acc->grp_hint |= new_acc->grp_read;
1970 if (rchild->first_child)
1971 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1976 /* If a (part of) a union field is on the RHS of an assignment, it can
1977 have sub-accesses which do not make sense on the LHS (PR 40351).
1978 Check that this is not the case. */
1979 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1980 rchild->type, false))
1983 rchild->grp_hint = 1;
1984 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1988 if (racc->first_child)
1989 propagate_subaccesses_across_link (new_acc, rchild);
1996 /* Propagate all subaccesses across assignment links. */
1999 propagate_all_subaccesses (void)
2001 while (work_queue_head)
2003 struct access *racc = pop_access_from_work_queue ();
2004 struct assign_link *link;
2006 gcc_assert (racc->first_link);
2008 for (link = racc->first_link; link; link = link->next)
2010 struct access *lacc = link->lacc;
2012 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2014 lacc = lacc->group_representative;
2015 if (propagate_subaccesses_across_link (lacc, racc)
2016 && lacc->first_link)
2017 add_access_to_work_queue (lacc);
2022 /* Go through all accesses collected throughout the (intraprocedural) analysis
2023 stage, exclude overlapping ones, identify representatives and build trees
2024 out of them, making decisions about scalarization on the way. Return true
2025 iff there are any to-be-scalarized variables after this stage. */
2028 analyze_all_variable_accesses (void)
2031 bitmap tmp = BITMAP_ALLOC (NULL);
2033 unsigned i, max_total_scalarization_size;
2035 max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2036 * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2038 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2039 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2040 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2042 tree var = referenced_var (i);
2044 if (TREE_CODE (var) == VAR_DECL
2045 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2046 <= max_total_scalarization_size)
2047 && type_consists_of_records_p (TREE_TYPE (var)))
2049 completely_scalarize_record (var, var, 0);
2050 if (dump_file && (dump_flags & TDF_DETAILS))
2052 fprintf (dump_file, "Will attempt to totally scalarize ");
2053 print_generic_expr (dump_file, var, 0);
2054 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2059 bitmap_copy (tmp, candidate_bitmap);
2060 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2062 tree var = referenced_var (i);
2063 struct access *access;
2065 access = sort_and_splice_var_accesses (var);
2067 build_access_trees (access);
2069 disqualify_candidate (var,
2070 "No or inhibitingly overlapping accesses.");
2073 propagate_all_subaccesses ();
2075 bitmap_copy (tmp, candidate_bitmap);
2076 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2078 tree var = referenced_var (i);
2079 struct access *access = get_first_repr_for_decl (var);
2081 if (analyze_access_trees (access))
2084 if (dump_file && (dump_flags & TDF_DETAILS))
2086 fprintf (dump_file, "\nAccess trees for ");
2087 print_generic_expr (dump_file, var, 0);
2088 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2089 dump_access_tree (dump_file, access);
2090 fprintf (dump_file, "\n");
2094 disqualify_candidate (var, "No scalar replacements to be created.");
2101 statistics_counter_event (cfun, "Scalarized aggregates", res);
2108 /* Return true iff a reference statement into aggregate AGG can be built for
2109 every single to-be-replaced accesses that is a child of ACCESS, its sibling
2110 or a child of its sibling. TOP_OFFSET is the offset from the processed
2111 access subtree that has to be subtracted from offset of each access. */
2114 ref_expr_for_all_replacements_p (struct access *access, tree agg,
2115 HOST_WIDE_INT top_offset)
2119 if (access->grp_to_be_replaced
2120 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
2121 access->offset - top_offset,
2122 access->type, false))
2125 if (access->first_child
2126 && !ref_expr_for_all_replacements_p (access->first_child, agg,
2130 access = access->next_sibling;
2137 /* Generate statements copying scalar replacements of accesses within a subtree
2138 into or out of AGG. ACCESS is the first child of the root of the subtree to
2139 be processed. AGG is an aggregate type expression (can be a declaration but
2140 does not have to be, it can for example also be an indirect_ref).
2141 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2142 from offsets of individual accesses to get corresponding offsets for AGG.
2143 If CHUNK_SIZE is non-null, copy only replacements in the interval
2144 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2145 statement iterator used to place the new statements. WRITE should be true
2146 when the statements should write from AGG to the replacement and false if
2147 vice versa. if INSERT_AFTER is true, new statements will be added after the
2148 current statement in GSI, they will be added before the statement
2152 generate_subtree_copies (struct access *access, tree agg,
2153 HOST_WIDE_INT top_offset,
2154 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2155 gimple_stmt_iterator *gsi, bool write,
2162 if (chunk_size && access->offset >= start_offset + chunk_size)
2165 if (access->grp_to_be_replaced
2167 || access->offset + access->size > start_offset))
2169 tree repl = get_access_replacement (access);
2173 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2174 access->offset - top_offset,
2175 access->type, false);
2176 gcc_assert (ref_found);
2180 if (access->grp_partial_lhs)
2181 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2183 insert_after ? GSI_NEW_STMT
2185 stmt = gimple_build_assign (repl, expr);
2189 TREE_NO_WARNING (repl) = 1;
2190 if (access->grp_partial_lhs)
2191 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2193 insert_after ? GSI_NEW_STMT
2195 stmt = gimple_build_assign (expr, repl);
2199 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2201 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2203 sra_stats.subtree_copies++;
2206 if (access->first_child)
2207 generate_subtree_copies (access->first_child, agg, top_offset,
2208 start_offset, chunk_size, gsi,
2209 write, insert_after);
2211 access = access->next_sibling;
2216 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2217 the root of the subtree to be processed. GSI is the statement iterator used
2218 for inserting statements which are added after the current statement if
2219 INSERT_AFTER is true or before it otherwise. */
2222 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2226 struct access *child;
2228 if (access->grp_to_be_replaced)
2232 stmt = gimple_build_assign (get_access_replacement (access),
2233 fold_convert (access->type,
2234 integer_zero_node));
2236 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2238 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2242 for (child = access->first_child; child; child = child->next_sibling)
2243 init_subtree_with_zero (child, gsi, insert_after);
2246 /* Search for an access representative for the given expression EXPR and
2247 return it or NULL if it cannot be found. */
2249 static struct access *
2250 get_access_for_expr (tree expr)
2252 HOST_WIDE_INT offset, size, max_size;
2255 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2256 a different size than the size of its argument and we need the latter
2258 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2259 expr = TREE_OPERAND (expr, 0);
2261 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2262 if (max_size == -1 || !DECL_P (base))
2265 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2268 return get_var_base_offset_size_access (base, offset, max_size);
2271 /* Callback for scan_function. Replace the expression EXPR with a scalar
2272 replacement if there is one and generate other statements to do type
2273 conversion or subtree copying if necessary. GSI is used to place newly
2274 created statements, WRITE is true if the expression is being written to (it
2275 is on a LHS of a statement or output in an assembly statement). */
2278 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2279 void *data ATTRIBUTE_UNUSED)
2281 struct access *access;
2284 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2287 expr = &TREE_OPERAND (*expr, 0);
2292 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2293 expr = &TREE_OPERAND (*expr, 0);
2294 access = get_access_for_expr (*expr);
2297 type = TREE_TYPE (*expr);
2299 if (access->grp_to_be_replaced)
2301 tree repl = get_access_replacement (access);
2302 /* If we replace a non-register typed access simply use the original
2303 access expression to extract the scalar component afterwards.
2304 This happens if scalarizing a function return value or parameter
2305 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2306 gcc.c-torture/compile/20011217-1.c.
2308 We also want to use this when accessing a complex or vector which can
2309 be accessed as a different type too, potentially creating a need for
2310 type conversion (see PR42196) and when scalarized unions are involved
2311 in assembler statements (see PR42398). */
2312 if (!useless_type_conversion_p (type, access->type))
2314 tree ref = access->base;
2317 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2318 access->offset, access->type, false);
2325 if (access->grp_partial_lhs)
2326 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2327 false, GSI_NEW_STMT);
2328 stmt = gimple_build_assign (repl, ref);
2329 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2335 if (access->grp_partial_lhs)
2336 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2337 true, GSI_SAME_STMT);
2338 stmt = gimple_build_assign (ref, repl);
2339 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2347 if (access->first_child)
2349 HOST_WIDE_INT start_offset, chunk_size;
2351 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2352 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2354 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2355 start_offset = access->offset
2356 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2359 start_offset = chunk_size = 0;
2361 generate_subtree_copies (access->first_child, access->base, 0,
2362 start_offset, chunk_size, gsi, write, write);
2367 /* Where scalar replacements of the RHS have been written to when a replacement
2368 of a LHS of an assigments cannot be direclty loaded from a replacement of
2370 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2371 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2372 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2374 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2375 base aggregate if there are unscalarized data or directly to LHS
2378 static enum unscalarized_data_handling
2379 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2380 gimple_stmt_iterator *gsi)
2382 if (top_racc->grp_unscalarized_data)
2384 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2386 return SRA_UDH_RIGHT;
2390 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2391 0, 0, gsi, false, false);
2392 return SRA_UDH_LEFT;
2397 /* Try to generate statements to load all sub-replacements in an access
2398 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2399 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2400 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2401 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2402 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2403 the rhs top aggregate has already been refreshed by contents of its scalar
2404 reductions and is set to true if this function has to do it. */
2407 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2408 HOST_WIDE_INT left_offset,
2409 HOST_WIDE_INT right_offset,
2410 gimple_stmt_iterator *old_gsi,
2411 gimple_stmt_iterator *new_gsi,
2412 enum unscalarized_data_handling *refreshed,
2415 location_t loc = EXPR_LOCATION (lacc->expr);
2418 if (lacc->grp_to_be_replaced)
2420 struct access *racc;
2421 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2425 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2426 if (racc && racc->grp_to_be_replaced)
2428 rhs = get_access_replacement (racc);
2429 if (!useless_type_conversion_p (lacc->type, racc->type))
2430 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2434 /* No suitable access on the right hand side, need to load from
2435 the aggregate. See if we have to update it first... */
2436 if (*refreshed == SRA_UDH_NONE)
2437 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2440 if (*refreshed == SRA_UDH_LEFT)
2445 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2446 lacc->offset, lacc->type,
2448 gcc_assert (repl_found);
2454 rhs = top_racc->base;
2455 repl_found = build_ref_for_offset (&rhs,
2456 TREE_TYPE (top_racc->base),
2457 offset, lacc->type, false);
2458 gcc_assert (repl_found);
2462 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2463 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2465 sra_stats.subreplacements++;
2467 else if (*refreshed == SRA_UDH_NONE
2468 && lacc->grp_read && !lacc->grp_covered)
2469 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2472 if (lacc->first_child)
2473 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2474 left_offset, right_offset,
2475 old_gsi, new_gsi, refreshed, lhs);
2476 lacc = lacc->next_sibling;
2481 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2482 to the assignment and GSI is the statement iterator pointing at it. Returns
2483 the same values as sra_modify_assign. */
2485 static enum scan_assign_result
2486 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2488 tree lhs = gimple_assign_lhs (*stmt);
2491 acc = get_access_for_expr (lhs);
2495 if (VEC_length (constructor_elt,
2496 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2498 /* I have never seen this code path trigger but if it can happen the
2499 following should handle it gracefully. */
2500 if (access_has_children_p (acc))
2501 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2503 return SRA_SA_PROCESSED;
2506 if (acc->grp_covered)
2508 init_subtree_with_zero (acc, gsi, false);
2509 unlink_stmt_vdef (*stmt);
2510 gsi_remove (gsi, true);
2511 return SRA_SA_REMOVED;
2515 init_subtree_with_zero (acc, gsi, true);
2516 return SRA_SA_PROCESSED;
2521 /* Callback of scan_function to process assign statements. It examines both
2522 sides of the statement, replaces them with a scalare replacement if there is
2523 one and generating copying of replacements if scalarized aggregates have been
2524 used in the assignment. STMT is a pointer to the assign statement, GSI is
2525 used to hold generated statements for type conversions and subtree
2528 static enum scan_assign_result
2529 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2530 void *data ATTRIBUTE_UNUSED)
2532 struct access *lacc, *racc;
2534 bool modify_this_stmt = false;
2535 bool force_gimple_rhs = false;
2536 location_t loc = gimple_location (*stmt);
2537 gimple_stmt_iterator orig_gsi = *gsi;
2539 if (!gimple_assign_single_p (*stmt))
2541 lhs = gimple_assign_lhs (*stmt);
2542 rhs = gimple_assign_rhs1 (*stmt);
2544 if (TREE_CODE (rhs) == CONSTRUCTOR)
2545 return sra_modify_constructor_assign (stmt, gsi);
2547 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2548 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2549 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2551 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2553 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2555 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2558 lacc = get_access_for_expr (lhs);
2559 racc = get_access_for_expr (rhs);
2563 if (lacc && lacc->grp_to_be_replaced)
2565 lhs = get_access_replacement (lacc);
2566 gimple_assign_set_lhs (*stmt, lhs);
2567 modify_this_stmt = true;
2568 if (lacc->grp_partial_lhs)
2569 force_gimple_rhs = true;
2573 if (racc && racc->grp_to_be_replaced)
2575 rhs = get_access_replacement (racc);
2576 modify_this_stmt = true;
2577 if (racc->grp_partial_lhs)
2578 force_gimple_rhs = true;
2582 if (modify_this_stmt)
2584 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2586 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2587 ??? This should move to fold_stmt which we simply should
2588 call after building a VIEW_CONVERT_EXPR here. */
2589 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2590 && !access_has_children_p (lacc))
2593 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2594 TREE_TYPE (rhs), false))
2597 gimple_assign_set_lhs (*stmt, expr);
2600 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2601 && !access_has_children_p (racc))
2604 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2605 TREE_TYPE (lhs), false))
2608 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2610 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2611 if (is_gimple_reg_type (TREE_TYPE (lhs))
2612 && TREE_CODE (lhs) != SSA_NAME)
2613 force_gimple_rhs = true;
2618 /* From this point on, the function deals with assignments in between
2619 aggregates when at least one has scalar reductions of some of its
2620 components. There are three possible scenarios: Both the LHS and RHS have
2621 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2623 In the first case, we would like to load the LHS components from RHS
2624 components whenever possible. If that is not possible, we would like to
2625 read it directly from the RHS (after updating it by storing in it its own
2626 components). If there are some necessary unscalarized data in the LHS,
2627 those will be loaded by the original assignment too. If neither of these
2628 cases happen, the original statement can be removed. Most of this is done
2629 by load_assign_lhs_subreplacements.
2631 In the second case, we would like to store all RHS scalarized components
2632 directly into LHS and if they cover the aggregate completely, remove the
2633 statement too. In the third case, we want the LHS components to be loaded
2634 directly from the RHS (DSE will remove the original statement if it
2637 This is a bit complex but manageable when types match and when unions do
2638 not cause confusion in a way that we cannot really load a component of LHS
2639 from the RHS or vice versa (the access representing this level can have
2640 subaccesses that are accessible only through a different union field at a
2641 higher level - different from the one used in the examined expression).
2644 Therefore, I specially handle a fourth case, happening when there is a
2645 specific type cast or it is impossible to locate a scalarized subaccess on
2646 the other side of the expression. If that happens, I simply "refresh" the
2647 RHS by storing in it is scalarized components leave the original statement
2648 there to do the copying and then load the scalar replacements of the LHS.
2649 This is what the first branch does. */
2651 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2652 || (access_has_children_p (racc)
2653 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2654 || (access_has_children_p (lacc)
2655 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2657 if (access_has_children_p (racc))
2658 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2660 if (access_has_children_p (lacc))
2661 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2663 sra_stats.separate_lhs_rhs_handling++;
2667 if (access_has_children_p (lacc) && access_has_children_p (racc))
2669 gimple_stmt_iterator orig_gsi = *gsi;
2670 enum unscalarized_data_handling refreshed;
2672 if (lacc->grp_read && !lacc->grp_covered)
2673 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2675 refreshed = SRA_UDH_NONE;
2677 load_assign_lhs_subreplacements (lacc->first_child, racc,
2678 lacc->offset, racc->offset,
2679 &orig_gsi, gsi, &refreshed, lhs);
2680 if (refreshed != SRA_UDH_RIGHT)
2682 if (*stmt == gsi_stmt (*gsi))
2685 unlink_stmt_vdef (*stmt);
2686 gsi_remove (&orig_gsi, true);
2687 sra_stats.deleted++;
2688 return SRA_SA_REMOVED;
2693 if (access_has_children_p (racc))
2695 if (!racc->grp_unscalarized_data
2696 /* Do not remove SSA name definitions (PR 42704). */
2697 && TREE_CODE (lhs) != SSA_NAME)
2699 generate_subtree_copies (racc->first_child, lhs,
2700 racc->offset, 0, 0, gsi,
2702 gcc_assert (*stmt == gsi_stmt (*gsi));
2703 unlink_stmt_vdef (*stmt);
2704 gsi_remove (gsi, true);
2705 sra_stats.deleted++;
2706 return SRA_SA_REMOVED;
2709 generate_subtree_copies (racc->first_child, lhs,
2710 racc->offset, 0, 0, gsi, false, true);
2712 else if (access_has_children_p (lacc))
2713 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2714 0, 0, gsi, true, true);
2718 /* This gimplification must be done after generate_subtree_copies, lest we
2719 insert the subtree copies in the middle of the gimplified sequence. */
2720 if (force_gimple_rhs)
2721 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
2722 true, GSI_SAME_STMT);
2723 if (gimple_assign_rhs1 (*stmt) != rhs)
2725 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
2726 gcc_assert (*stmt == gsi_stmt (orig_gsi));
2729 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2732 /* Generate statements initializing scalar replacements of parts of function
2736 initialize_parameter_reductions (void)
2738 gimple_stmt_iterator gsi;
2739 gimple_seq seq = NULL;
2742 for (parm = DECL_ARGUMENTS (current_function_decl);
2744 parm = TREE_CHAIN (parm))
2746 VEC (access_p, heap) *access_vec;
2747 struct access *access;
2749 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2751 access_vec = get_base_access_vector (parm);
2757 seq = gimple_seq_alloc ();
2758 gsi = gsi_start (seq);
2761 for (access = VEC_index (access_p, access_vec, 0);
2763 access = access->next_grp)
2764 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2768 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2771 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2772 it reveals there are components of some aggregates to be scalarized, it runs
2773 the required transformations. */
2775 perform_intra_sra (void)
2780 if (!find_var_candidates ())
2783 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2787 if (!analyze_all_variable_accesses ())
2790 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2791 initialize_parameter_reductions ();
2793 statistics_counter_event (cfun, "Scalar replacements created",
2794 sra_stats.replacements);
2795 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2796 statistics_counter_event (cfun, "Subtree copy stmts",
2797 sra_stats.subtree_copies);
2798 statistics_counter_event (cfun, "Subreplacement stmts",
2799 sra_stats.subreplacements);
2800 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2801 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2802 sra_stats.separate_lhs_rhs_handling);
2804 ret = TODO_update_ssa;
2807 sra_deinitialize ();
2811 /* Perform early intraprocedural SRA. */
2813 early_intra_sra (void)
2815 sra_mode = SRA_MODE_EARLY_INTRA;
2816 return perform_intra_sra ();
2819 /* Perform "late" intraprocedural SRA. */
2821 late_intra_sra (void)
2823 sra_mode = SRA_MODE_INTRA;
2824 return perform_intra_sra ();
2829 gate_intra_sra (void)
2831 return flag_tree_sra != 0;
2835 struct gimple_opt_pass pass_sra_early =
2840 gate_intra_sra, /* gate */
2841 early_intra_sra, /* execute */
2844 0, /* static_pass_number */
2845 TV_TREE_SRA, /* tv_id */
2846 PROP_cfg | PROP_ssa, /* properties_required */
2847 0, /* properties_provided */
2848 0, /* properties_destroyed */
2849 0, /* todo_flags_start */
2853 | TODO_verify_ssa /* todo_flags_finish */
2857 struct gimple_opt_pass pass_sra =
2862 gate_intra_sra, /* gate */
2863 late_intra_sra, /* execute */
2866 0, /* static_pass_number */
2867 TV_TREE_SRA, /* tv_id */
2868 PROP_cfg | PROP_ssa, /* properties_required */
2869 0, /* properties_provided */
2870 0, /* properties_destroyed */
2871 TODO_update_address_taken, /* todo_flags_start */
2875 | TODO_verify_ssa /* todo_flags_finish */
2880 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2884 is_unused_scalar_param (tree parm)
2887 return (is_gimple_reg (parm)
2888 && (!(name = gimple_default_def (cfun, parm))
2889 || has_zero_uses (name)));
2892 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2893 examine whether there are any direct or otherwise infeasible ones. If so,
2894 return true, otherwise return false. PARM must be a gimple register with a
2895 non-NULL default definition. */
2898 ptr_parm_has_direct_uses (tree parm)
2900 imm_use_iterator ui;
2902 tree name = gimple_default_def (cfun, parm);
2905 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2907 if (gimple_assign_single_p (stmt))
2909 tree rhs = gimple_assign_rhs1 (stmt);
2912 else if (TREE_CODE (rhs) == ADDR_EXPR)
2916 rhs = TREE_OPERAND (rhs, 0);
2918 while (handled_component_p (rhs));
2919 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2923 else if (gimple_code (stmt) == GIMPLE_RETURN)
2925 tree t = gimple_return_retval (stmt);
2929 else if (is_gimple_call (stmt))
2932 for (i = 0; i < gimple_call_num_args (stmt); i++)
2934 tree arg = gimple_call_arg (stmt, i);
2942 else if (!is_gimple_debug (stmt))
2946 BREAK_FROM_IMM_USE_STMT (ui);
2952 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2953 them in candidate_bitmap. Note that these do not necessarily include
2954 parameter which are unused and thus can be removed. Return true iff any
2955 such candidate has been found. */
2958 find_param_candidates (void)
2964 for (parm = DECL_ARGUMENTS (current_function_decl);
2966 parm = TREE_CHAIN (parm))
2968 tree type = TREE_TYPE (parm);
2972 if (TREE_THIS_VOLATILE (parm)
2973 || TREE_ADDRESSABLE (parm)
2974 || is_va_list_type (type))
2977 if (is_unused_scalar_param (parm))
2983 if (POINTER_TYPE_P (type))
2985 type = TREE_TYPE (type);
2987 if (TREE_CODE (type) == FUNCTION_TYPE
2988 || TYPE_VOLATILE (type)
2989 || !is_gimple_reg (parm)
2990 || is_va_list_type (type)
2991 || ptr_parm_has_direct_uses (parm))
2994 else if (!AGGREGATE_TYPE_P (type))
2997 if (!COMPLETE_TYPE_P (type)
2998 || !host_integerp (TYPE_SIZE (type), 1)
2999 || tree_low_cst (TYPE_SIZE (type), 1) == 0
3000 || (AGGREGATE_TYPE_P (type)
3001 && type_internals_preclude_sra_p (type)))
3004 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3006 if (dump_file && (dump_flags & TDF_DETAILS))
3008 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3009 print_generic_expr (dump_file, parm, 0);
3010 fprintf (dump_file, "\n");
3014 func_param_count = count;
3018 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3022 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3025 struct access *repr = (struct access *) data;
3027 repr->grp_maybe_modified = 1;
3031 /* Analyze what representatives (in linked lists accessible from
3032 REPRESENTATIVES) can be modified by side effects of statements in the
3033 current function. */
3036 analyze_modified_params (VEC (access_p, heap) *representatives)
3040 for (i = 0; i < func_param_count; i++)
3042 struct access *repr;
3044 for (repr = VEC_index (access_p, representatives, i);
3046 repr = repr->next_grp)
3048 struct access *access;
3052 if (no_accesses_p (repr))
3054 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3055 || repr->grp_maybe_modified)
3058 ao_ref_init (&ar, repr->expr);
3059 visited = BITMAP_ALLOC (NULL);
3060 for (access = repr; access; access = access->next_sibling)
3062 /* All accesses are read ones, otherwise grp_maybe_modified would
3063 be trivially set. */
3064 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3065 mark_maybe_modified, repr, &visited);
3066 if (repr->grp_maybe_modified)
3069 BITMAP_FREE (visited);
3074 /* Propagate distances in bb_dereferences in the opposite direction than the
3075 control flow edges, in each step storing the maximum of the current value
3076 and the minimum of all successors. These steps are repeated until the table
3077 stabilizes. Note that BBs which might terminate the functions (according to
3078 final_bbs bitmap) never updated in this way. */
3081 propagate_dereference_distances (void)
3083 VEC (basic_block, heap) *queue;
3086 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3087 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3090 VEC_quick_push (basic_block, queue, bb);
3094 while (!VEC_empty (basic_block, queue))
3098 bool change = false;
3101 bb = VEC_pop (basic_block, queue);
3104 if (bitmap_bit_p (final_bbs, bb->index))
3107 for (i = 0; i < func_param_count; i++)
3109 int idx = bb->index * func_param_count + i;
3111 HOST_WIDE_INT inh = 0;
3113 FOR_EACH_EDGE (e, ei, bb->succs)
3115 int succ_idx = e->dest->index * func_param_count + i;
3117 if (e->src == EXIT_BLOCK_PTR)
3123 inh = bb_dereferences [succ_idx];
3125 else if (bb_dereferences [succ_idx] < inh)
3126 inh = bb_dereferences [succ_idx];
3129 if (!first && bb_dereferences[idx] < inh)
3131 bb_dereferences[idx] = inh;
3136 if (change && !bitmap_bit_p (final_bbs, bb->index))
3137 FOR_EACH_EDGE (e, ei, bb->preds)
3142 e->src->aux = e->src;
3143 VEC_quick_push (basic_block, queue, e->src);
3147 VEC_free (basic_block, heap, queue);
3150 /* Dump a dereferences TABLE with heading STR to file F. */
3153 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3157 fprintf (dump_file, str);
3158 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3160 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3161 if (bb != EXIT_BLOCK_PTR)
3164 for (i = 0; i < func_param_count; i++)
3166 int idx = bb->index * func_param_count + i;
3167 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3172 fprintf (dump_file, "\n");
3175 /* Determine what (parts of) parameters passed by reference that are not
3176 assigned to are not certainly dereferenced in this function and thus the
3177 dereferencing cannot be safely moved to the caller without potentially
3178 introducing a segfault. Mark such REPRESENTATIVES as
3179 grp_not_necessarilly_dereferenced.
3181 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3182 part is calculated rather than simple booleans are calculated for each
3183 pointer parameter to handle cases when only a fraction of the whole
3184 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3187 The maximum dereference distances for each pointer parameter and BB are
3188 already stored in bb_dereference. This routine simply propagates these
3189 values upwards by propagate_dereference_distances and then compares the
3190 distances of individual parameters in the ENTRY BB to the equivalent
3191 distances of each representative of a (fraction of a) parameter. */
3194 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3198 if (dump_file && (dump_flags & TDF_DETAILS))
3199 dump_dereferences_table (dump_file,
3200 "Dereference table before propagation:\n",
3203 propagate_dereference_distances ();
3205 if (dump_file && (dump_flags & TDF_DETAILS))
3206 dump_dereferences_table (dump_file,
3207 "Dereference table after propagation:\n",
3210 for (i = 0; i < func_param_count; i++)
3212 struct access *repr = VEC_index (access_p, representatives, i);
3213 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3215 if (!repr || no_accesses_p (repr))
3220 if ((repr->offset + repr->size) > bb_dereferences[idx])
3221 repr->grp_not_necessarilly_dereferenced = 1;
3222 repr = repr->next_grp;
3228 /* Return the representative access for the parameter declaration PARM if it is
3229 a scalar passed by reference which is not written to and the pointer value
3230 is not used directly. Thus, if it is legal to dereference it in the caller
3231 and we can rule out modifications through aliases, such parameter should be
3232 turned into one passed by value. Return NULL otherwise. */
3234 static struct access *
3235 unmodified_by_ref_scalar_representative (tree parm)
3237 int i, access_count;
3238 struct access *repr;
3239 VEC (access_p, heap) *access_vec;
3241 access_vec = get_base_access_vector (parm);
3242 gcc_assert (access_vec);
3243 repr = VEC_index (access_p, access_vec, 0);
3246 repr->group_representative = repr;
3248 access_count = VEC_length (access_p, access_vec);
3249 for (i = 1; i < access_count; i++)
3251 struct access *access = VEC_index (access_p, access_vec, i);
3254 access->group_representative = repr;
3255 access->next_sibling = repr->next_sibling;
3256 repr->next_sibling = access;
3260 repr->grp_scalar_ptr = 1;
3264 /* Return true iff this access precludes IPA-SRA of the parameter it is
3268 access_precludes_ipa_sra_p (struct access *access)
3270 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3271 is incompatible assign in a call statement (and possibly even in asm
3272 statements). This can be relaxed by using a new temporary but only for
3273 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3274 intraprocedural SRA we deal with this by keeping the old aggregate around,
3275 something we cannot do in IPA-SRA.) */
3277 && (is_gimple_call (access->stmt)
3278 || gimple_code (access->stmt) == GIMPLE_ASM))
3285 /* Sort collected accesses for parameter PARM, identify representatives for
3286 each accessed region and link them together. Return NULL if there are
3287 different but overlapping accesses, return the special ptr value meaning
3288 there are no accesses for this parameter if that is the case and return the
3289 first representative otherwise. Set *RO_GRP if there is a group of accesses
3290 with only read (i.e. no write) accesses. */
3292 static struct access *
3293 splice_param_accesses (tree parm, bool *ro_grp)
3295 int i, j, access_count, group_count;
3296 int agg_size, total_size = 0;
3297 struct access *access, *res, **prev_acc_ptr = &res;
3298 VEC (access_p, heap) *access_vec;
3300 access_vec = get_base_access_vector (parm);
3302 return &no_accesses_representant;
3303 access_count = VEC_length (access_p, access_vec);
3305 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3306 compare_access_positions);
3311 while (i < access_count)
3314 access = VEC_index (access_p, access_vec, i);
3315 modification = access->write;
3316 if (access_precludes_ipa_sra_p (access))
3319 /* Access is about to become group representative unless we find some
3320 nasty overlap which would preclude us from breaking this parameter
3324 while (j < access_count)
3326 struct access *ac2 = VEC_index (access_p, access_vec, j);
3327 if (ac2->offset != access->offset)
3329 /* All or nothing law for parameters. */
3330 if (access->offset + access->size > ac2->offset)
3335 else if (ac2->size != access->size)
3338 if (access_precludes_ipa_sra_p (ac2))
3341 modification |= ac2->write;
3342 ac2->group_representative = access;
3343 ac2->next_sibling = access->next_sibling;
3344 access->next_sibling = ac2;
3349 access->grp_maybe_modified = modification;
3352 *prev_acc_ptr = access;
3353 prev_acc_ptr = &access->next_grp;
3354 total_size += access->size;
3358 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3359 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3361 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3362 if (total_size >= agg_size)
3365 gcc_assert (group_count > 0);
3369 /* Decide whether parameters with representative accesses given by REPR should
3370 be reduced into components. */
3373 decide_one_param_reduction (struct access *repr)
3375 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3380 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3381 gcc_assert (cur_parm_size > 0);
3383 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3386 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3391 agg_size = cur_parm_size;
3397 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3398 print_generic_expr (dump_file, parm, 0);
3399 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3400 for (acc = repr; acc; acc = acc->next_grp)
3401 dump_access (dump_file, acc, true);
3405 new_param_count = 0;
3407 for (; repr; repr = repr->next_grp)
3409 gcc_assert (parm == repr->base);
3412 if (!by_ref || (!repr->grp_maybe_modified
3413 && !repr->grp_not_necessarilly_dereferenced))
3414 total_size += repr->size;
3416 total_size += cur_parm_size;
3419 gcc_assert (new_param_count > 0);
3421 if (optimize_function_for_size_p (cfun))
3422 parm_size_limit = cur_parm_size;
3424 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3427 if (total_size < agg_size
3428 && total_size <= parm_size_limit)
3431 fprintf (dump_file, " ....will be split into %i components\n",
3433 return new_param_count;
3439 /* The order of the following enums is important, we need to do extra work for
3440 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3441 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3442 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3444 /* Identify representatives of all accesses to all candidate parameters for
3445 IPA-SRA. Return result based on what representatives have been found. */
3447 static enum ipa_splicing_result
3448 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3450 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3452 struct access *repr;
3454 *representatives = VEC_alloc (access_p, heap, func_param_count);
3456 for (parm = DECL_ARGUMENTS (current_function_decl);
3458 parm = TREE_CHAIN (parm))
3460 if (is_unused_scalar_param (parm))
3462 VEC_quick_push (access_p, *representatives,
3463 &no_accesses_representant);
3464 if (result == NO_GOOD_ACCESS)
3465 result = UNUSED_PARAMS;
3467 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3468 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3469 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3471 repr = unmodified_by_ref_scalar_representative (parm);
3472 VEC_quick_push (access_p, *representatives, repr);
3474 result = UNMODIF_BY_REF_ACCESSES;
3476 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3478 bool ro_grp = false;
3479 repr = splice_param_accesses (parm, &ro_grp);
3480 VEC_quick_push (access_p, *representatives, repr);
3482 if (repr && !no_accesses_p (repr))
3484 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3487 result = UNMODIF_BY_REF_ACCESSES;
3488 else if (result < MODIF_BY_REF_ACCESSES)
3489 result = MODIF_BY_REF_ACCESSES;
3491 else if (result < BY_VAL_ACCESSES)
3492 result = BY_VAL_ACCESSES;
3494 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3495 result = UNUSED_PARAMS;
3498 VEC_quick_push (access_p, *representatives, NULL);
3501 if (result == NO_GOOD_ACCESS)
3503 VEC_free (access_p, heap, *representatives);
3504 *representatives = NULL;
3505 return NO_GOOD_ACCESS;
3511 /* Return the index of BASE in PARMS. Abort if it is not found. */
3514 get_param_index (tree base, VEC(tree, heap) *parms)
3518 len = VEC_length (tree, parms);
3519 for (i = 0; i < len; i++)
3520 if (VEC_index (tree, parms, i) == base)
3525 /* Convert the decisions made at the representative level into compact
3526 parameter adjustments. REPRESENTATIVES are pointers to first
3527 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3528 final number of adjustments. */
3530 static ipa_parm_adjustment_vec
3531 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3532 int adjustments_count)
3534 VEC (tree, heap) *parms;
3535 ipa_parm_adjustment_vec adjustments;
3539 gcc_assert (adjustments_count > 0);
3540 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3541 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3542 parm = DECL_ARGUMENTS (current_function_decl);
3543 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3545 struct access *repr = VEC_index (access_p, representatives, i);
3547 if (!repr || no_accesses_p (repr))
3549 struct ipa_parm_adjustment *adj;
3551 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3552 memset (adj, 0, sizeof (*adj));
3553 adj->base_index = get_param_index (parm, parms);
3556 adj->copy_param = 1;
3558 adj->remove_param = 1;
3562 struct ipa_parm_adjustment *adj;
3563 int index = get_param_index (parm, parms);
3565 for (; repr; repr = repr->next_grp)
3567 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3568 memset (adj, 0, sizeof (*adj));
3569 gcc_assert (repr->base == parm);
3570 adj->base_index = index;
3571 adj->base = repr->base;
3572 adj->type = repr->type;
3573 adj->offset = repr->offset;
3574 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3575 && (repr->grp_maybe_modified
3576 || repr->grp_not_necessarilly_dereferenced));
3581 VEC_free (tree, heap, parms);
3585 /* Analyze the collected accesses and produce a plan what to do with the
3586 parameters in the form of adjustments, NULL meaning nothing. */
3588 static ipa_parm_adjustment_vec
3589 analyze_all_param_acesses (void)
3591 enum ipa_splicing_result repr_state;
3592 bool proceed = false;
3593 int i, adjustments_count = 0;
3594 VEC (access_p, heap) *representatives;
3595 ipa_parm_adjustment_vec adjustments;
3597 repr_state = splice_all_param_accesses (&representatives);
3598 if (repr_state == NO_GOOD_ACCESS)
3601 /* If there are any parameters passed by reference which are not modified
3602 directly, we need to check whether they can be modified indirectly. */
3603 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3605 analyze_caller_dereference_legality (representatives);
3606 analyze_modified_params (representatives);
3609 for (i = 0; i < func_param_count; i++)
3611 struct access *repr = VEC_index (access_p, representatives, i);
3613 if (repr && !no_accesses_p (repr))
3615 if (repr->grp_scalar_ptr)
3617 adjustments_count++;
3618 if (repr->grp_not_necessarilly_dereferenced
3619 || repr->grp_maybe_modified)
3620 VEC_replace (access_p, representatives, i, NULL);
3624 sra_stats.scalar_by_ref_to_by_val++;
3629 int new_components = decide_one_param_reduction (repr);
3631 if (new_components == 0)
3633 VEC_replace (access_p, representatives, i, NULL);
3634 adjustments_count++;
3638 adjustments_count += new_components;
3639 sra_stats.aggregate_params_reduced++;
3640 sra_stats.param_reductions_created += new_components;
3647 if (no_accesses_p (repr))
3650 sra_stats.deleted_unused_parameters++;
3652 adjustments_count++;
3656 if (!proceed && dump_file)
3657 fprintf (dump_file, "NOT proceeding to change params.\n");
3660 adjustments = turn_representatives_into_adjustments (representatives,
3665 VEC_free (access_p, heap, representatives);
3669 /* If a parameter replacement identified by ADJ does not yet exist in the form
3670 of declaration, create it and record it, otherwise return the previously
3674 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3677 if (!adj->new_ssa_base)
3679 char *pretty_name = make_fancy_name (adj->base);
3681 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3682 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3683 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3684 DECL_GIMPLE_REG_P (repl) = 1;
3685 DECL_NAME (repl) = get_identifier (pretty_name);
3686 obstack_free (&name_obstack, pretty_name);
3689 add_referenced_var (repl);
3690 adj->new_ssa_base = repl;
3693 repl = adj->new_ssa_base;
3697 /* Find the first adjustment for a particular parameter BASE in a vector of
3698 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3701 static struct ipa_parm_adjustment *
3702 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3706 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3707 for (i = 0; i < len; i++)
3709 struct ipa_parm_adjustment *adj;
3711 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3712 if (!adj->copy_param && adj->base == base)
3719 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3720 parameter which is to be removed because its value is not used, replace the
3721 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3722 uses too and return true (update_stmt is then issued for the statement by
3723 the caller). DATA is a pointer to an adjustments vector. */
3726 replace_removed_params_ssa_names (gimple stmt, void *data)
3728 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3729 struct ipa_parm_adjustment *adj;
3730 tree lhs, decl, repl, name;
3732 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3733 if (gimple_code (stmt) == GIMPLE_PHI)
3734 lhs = gimple_phi_result (stmt);
3735 else if (is_gimple_assign (stmt))
3736 lhs = gimple_assign_lhs (stmt);
3737 else if (is_gimple_call (stmt))
3738 lhs = gimple_call_lhs (stmt);
3742 if (TREE_CODE (lhs) != SSA_NAME)
3744 decl = SSA_NAME_VAR (lhs);
3745 if (TREE_CODE (decl) != PARM_DECL)
3748 adj = get_adjustment_for_base (adjustments, decl);
3752 repl = get_replaced_param_substitute (adj);
3753 name = make_ssa_name (repl, stmt);
3757 fprintf (dump_file, "replacing an SSA name of a removed param ");
3758 print_generic_expr (dump_file, lhs, 0);
3759 fprintf (dump_file, " with ");
3760 print_generic_expr (dump_file, name, 0);
3761 fprintf (dump_file, "\n");
3764 if (is_gimple_assign (stmt))
3765 gimple_assign_set_lhs (stmt, name);
3766 else if (is_gimple_call (stmt))
3767 gimple_call_set_lhs (stmt, name);
3769 gimple_phi_set_result (stmt, name);
3771 replace_uses_by (lhs, name);
3775 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3776 expression *EXPR should be replaced by a reduction of a parameter, do so.
3777 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3778 whether the function should care about type incompatibility the current and
3779 new expressions. If it is true, the function will leave incompatibility
3780 issues to the caller.
3782 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3783 a write (LHS) expression. */
3786 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3787 bool dont_convert, void *data)
3789 ipa_parm_adjustment_vec adjustments;
3791 struct ipa_parm_adjustment *adj, *cand = NULL;
3792 HOST_WIDE_INT offset, size, max_size;
3795 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3796 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3798 if (TREE_CODE (*expr) == BIT_FIELD_REF
3799 || TREE_CODE (*expr) == IMAGPART_EXPR
3800 || TREE_CODE (*expr) == REALPART_EXPR)
3802 expr = &TREE_OPERAND (*expr, 0);
3803 dont_convert = false;
3806 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3807 if (!base || size == -1 || max_size == -1)
3810 if (INDIRECT_REF_P (base))
3811 base = TREE_OPERAND (base, 0);
3813 base = get_ssa_base_param (base);
3814 if (!base || TREE_CODE (base) != PARM_DECL)
3817 for (i = 0; i < len; i++)
3819 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3821 if (adj->base == base &&
3822 (adj->offset == offset || adj->remove_param))
3828 if (!cand || cand->copy_param || cand->remove_param)
3834 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3836 folded = gimple_fold_indirect_ref (src);
3841 src = cand->reduction;
3843 if (dump_file && (dump_flags & TDF_DETAILS))
3845 fprintf (dump_file, "About to replace expr ");
3846 print_generic_expr (dump_file, *expr, 0);
3847 fprintf (dump_file, " with ");
3848 print_generic_expr (dump_file, src, 0);
3849 fprintf (dump_file, "\n");
3853 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3855 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3863 /* Callback for scan_function to process assign statements. Performs
3864 essentially the same function like sra_ipa_modify_expr. */
3866 static enum scan_assign_result
3867 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3869 gimple stmt = *stmt_ptr;
3870 tree *lhs_p, *rhs_p;
3873 if (!gimple_assign_single_p (stmt))
3876 rhs_p = gimple_assign_rhs1_ptr (stmt);
3877 lhs_p = gimple_assign_lhs_ptr (stmt);
3879 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3880 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3883 tree new_rhs = NULL_TREE;
3885 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3887 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
3889 /* V_C_Es of constructors can cause trouble (PR 42714). */
3890 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
3891 *rhs_p = fold_convert (TREE_TYPE (*lhs_p), integer_zero_node);
3893 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
3896 new_rhs = fold_build1_loc (gimple_location (stmt),
3897 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
3900 else if (REFERENCE_CLASS_P (*rhs_p)
3901 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3902 && !is_gimple_reg (*lhs_p))
3903 /* This can happen when an assignment in between two single field
3904 structures is turned into an assignment in between two pointers to
3905 scalars (PR 42237). */
3910 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3911 true, GSI_SAME_STMT);
3913 gimple_assign_set_rhs_from_tree (gsi, tmp);
3916 return SRA_SA_PROCESSED;
3922 /* Call gimple_debug_bind_reset_value on all debug statements describing
3923 gimple register parameters that are being removed or replaced. */
3926 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3930 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3931 for (i = 0; i < len; i++)
3933 struct ipa_parm_adjustment *adj;
3934 imm_use_iterator ui;
3938 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3939 if (adj->copy_param || !is_gimple_reg (adj->base))
3941 name = gimple_default_def (cfun, adj->base);
3944 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3946 /* All other users must have been removed by scan_function. */
3947 gcc_assert (is_gimple_debug (stmt));
3948 gimple_debug_bind_reset_value (stmt);
3954 /* Return true iff all callers have at least as many actual arguments as there
3955 are formal parameters in the current function. */
3958 all_callers_have_enough_arguments_p (struct cgraph_node *node)
3960 struct cgraph_edge *cs;
3961 for (cs = node->callers; cs; cs = cs->next_caller)
3962 if (!callsite_has_enough_arguments_p (cs->call_stmt))
3969 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3972 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3974 tree old_cur_fndecl = current_function_decl;
3975 struct cgraph_edge *cs;
3976 basic_block this_block;
3977 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3979 for (cs = node->callers; cs; cs = cs->next_caller)
3981 current_function_decl = cs->caller->decl;
3982 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3985 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3986 cs->caller->uid, cs->callee->uid,
3987 cgraph_node_name (cs->caller),
3988 cgraph_node_name (cs->callee));
3990 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3995 for (cs = node->callers; cs; cs = cs->next_caller)
3996 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3998 compute_inline_parameters (cs->caller);
3999 bitmap_set_bit (recomputed_callers, cs->caller->uid);
4001 BITMAP_FREE (recomputed_callers);
4003 current_function_decl = old_cur_fndecl;
4005 if (!encountered_recursive_call)
4008 FOR_EACH_BB (this_block)
4010 gimple_stmt_iterator gsi;
4012 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4014 gimple stmt = gsi_stmt (gsi);
4016 if (gimple_code (stmt) != GIMPLE_CALL)
4018 call_fndecl = gimple_call_fndecl (stmt);
4019 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
4022 fprintf (dump_file, "Adjusting recursive call");
4023 ipa_modify_call_arguments (NULL, stmt, adjustments);
4031 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4032 as given in ADJUSTMENTS. */
4035 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4037 struct cgraph_node *alias;
4038 for (alias = node->same_body; alias; alias = alias->next)
4039 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
4040 /* current_function_decl must be handled last, after same_body aliases,
4041 as following functions will use what it computed. */
4042 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
4043 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
4044 replace_removed_params_ssa_names, false, adjustments);
4045 sra_ipa_reset_debug_stmts (adjustments);
4046 convert_callers (node, adjustments);
4047 cgraph_make_node_local (node);
4051 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4052 attributes, return true otherwise. NODE is the cgraph node of the current
4056 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4058 if (!cgraph_node_can_be_local_p (node))
4061 fprintf (dump_file, "Function not local to this compilation unit.\n");
4065 if (DECL_VIRTUAL_P (current_function_decl))
4068 fprintf (dump_file, "Function is a virtual method.\n");
4072 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
4073 && node->global.size >= MAX_INLINE_INSNS_AUTO)
4076 fprintf (dump_file, "Function too big to be made truly local.\n");
4084 "Function has no callers in this compilation unit.\n");
4091 fprintf (dump_file, "Function uses stdarg. \n");
4098 /* Perform early interprocedural SRA. */
4101 ipa_early_sra (void)
4103 struct cgraph_node *node = cgraph_node (current_function_decl);
4104 ipa_parm_adjustment_vec adjustments;
4107 if (!ipa_sra_preliminary_function_checks (node))
4111 sra_mode = SRA_MODE_EARLY_IPA;
4113 if (!find_param_candidates ())
4116 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
4120 if (!all_callers_have_enough_arguments_p (node))
4123 fprintf (dump_file, "There are callers with insufficient number of "
4128 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
4130 * last_basic_block_for_function (cfun));
4131 final_bbs = BITMAP_ALLOC (NULL);
4133 scan_function (build_access_from_expr, build_accesses_from_assign,
4135 if (encountered_apply_args)
4138 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4142 if (encountered_unchangable_recursive_call)
4145 fprintf (dump_file, "Function calls itself with insufficient "
4146 "number of arguments.\n");
4150 adjustments = analyze_all_param_acesses ();
4154 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4156 modify_function (node, adjustments);
4157 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4158 ret = TODO_update_ssa;
4160 statistics_counter_event (cfun, "Unused parameters deleted",
4161 sra_stats.deleted_unused_parameters);
4162 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4163 sra_stats.scalar_by_ref_to_by_val);
4164 statistics_counter_event (cfun, "Aggregate parameters broken up",
4165 sra_stats.aggregate_params_reduced);
4166 statistics_counter_event (cfun, "Aggregate parameter components created",
4167 sra_stats.param_reductions_created);
4170 BITMAP_FREE (final_bbs);
4171 free (bb_dereferences);
4173 sra_deinitialize ();
4177 /* Return if early ipa sra shall be performed. */
4179 ipa_early_sra_gate (void)
4181 return flag_ipa_sra;
4184 struct gimple_opt_pass pass_early_ipa_sra =
4188 "eipa_sra", /* name */
4189 ipa_early_sra_gate, /* gate */
4190 ipa_early_sra, /* execute */
4193 0, /* static_pass_number */
4194 TV_IPA_SRA, /* tv_id */
4195 0, /* properties_required */
4196 0, /* properties_provided */
4197 0, /* properties_destroyed */
4198 0, /* todo_flags_start */
4199 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */