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, 2011 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
82 #include "tree-flow.h"
84 #include "tree-pretty-print.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 #include "tree-inline.h"
93 #include "gimple-pretty-print.h"
94 #include "ipa-inline.h"
96 /* Enumeration of all aggregate reductions we can do. */
97 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
98 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
99 SRA_MODE_INTRA }; /* late intraprocedural SRA */
101 /* Global variable describing which aggregate reduction we are performing at
103 static enum sra_mode sra_mode;
107 /* ACCESS represents each access to an aggregate variable (as a whole or a
108 part). It can also represent a group of accesses that refer to exactly the
109 same fragment of an aggregate (i.e. those that have exactly the same offset
110 and size). Such representatives for a single aggregate, once determined,
111 are linked in a linked list and have the group fields set.
113 Moreover, when doing intraprocedural SRA, a tree is built from those
114 representatives (by the means of first_child and next_sibling pointers), in
115 which all items in a subtree are "within" the root, i.e. their offset is
116 greater or equal to offset of the root and offset+size is smaller or equal
117 to offset+size of the root. Children of an access are sorted by offset.
119 Note that accesses to parts of vector and complex number types always
120 represented by an access to the whole complex number or a vector. It is a
121 duty of the modifying functions to replace them appropriately. */
125 /* Values returned by `get_ref_base_and_extent' for each component reference
126 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
127 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
128 HOST_WIDE_INT offset;
132 /* Expression. It is context dependent so do not use it to create new
133 expressions to access the original aggregate. See PR 42154 for a
139 /* The statement this access belongs to. */
142 /* Next group representative for this aggregate. */
143 struct access *next_grp;
145 /* Pointer to the group representative. Pointer to itself if the struct is
146 the representative. */
147 struct access *group_representative;
149 /* If this access has any children (in terms of the definition above), this
150 points to the first one. */
151 struct access *first_child;
153 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
154 described above. In IPA-SRA this is a pointer to the next access
155 belonging to the same group (having the same representative). */
156 struct access *next_sibling;
158 /* Pointers to the first and last element in the linked list of assign
160 struct assign_link *first_link, *last_link;
162 /* Pointer to the next access in the work queue. */
163 struct access *next_queued;
165 /* Replacement variable for this access "region." Never to be accessed
166 directly, always only by the means of get_access_replacement() and only
167 when grp_to_be_replaced flag is set. */
168 tree replacement_decl;
170 /* Is this particular access write access? */
173 /* Is this access an artificial one created to scalarize some record
175 unsigned total_scalarization : 1;
177 /* Is this access an access to a non-addressable field? */
178 unsigned non_addressable : 1;
180 /* Is this access currently in the work queue? */
181 unsigned grp_queued : 1;
183 /* Does this group contain a write access? This flag is propagated down the
185 unsigned grp_write : 1;
187 /* Does this group contain a read access? This flag is propagated down the
189 unsigned grp_read : 1;
191 /* Does this group contain a read access that comes from an assignment
192 statement? This flag is propagated down the access tree. */
193 unsigned grp_assignment_read : 1;
195 /* Does this group contain a write access that comes from an assignment
196 statement? This flag is propagated down the access tree. */
197 unsigned grp_assignment_write : 1;
199 /* Does this group contain a read access through a scalar type? This flag is
200 not propagated in the access tree in any direction. */
201 unsigned grp_scalar_read : 1;
203 /* Does this group contain a write access through a scalar type? This flag
204 is not propagated in the access tree in any direction. */
205 unsigned grp_scalar_write : 1;
207 /* Other passes of the analysis use this bit to make function
208 analyze_access_subtree create scalar replacements for this group if
210 unsigned grp_hint : 1;
212 /* Is the subtree rooted in this access fully covered by scalar
214 unsigned grp_covered : 1;
216 /* If set to true, this access and all below it in an access tree must not be
218 unsigned grp_unscalarizable_region : 1;
220 /* Whether data have been written to parts of the aggregate covered by this
221 access which is not to be scalarized. This flag is propagated up in the
223 unsigned grp_unscalarized_data : 1;
225 /* Does this access and/or group contain a write access through a
227 unsigned grp_partial_lhs : 1;
229 /* Set when a scalar replacement should be created for this variable. We do
230 the decision and creation at different places because create_tmp_var
231 cannot be called from within FOR_EACH_REFERENCED_VAR. */
232 unsigned grp_to_be_replaced : 1;
234 /* Should TREE_NO_WARNING of a replacement be set? */
235 unsigned grp_no_warning : 1;
237 /* Is it possible that the group refers to data which might be (directly or
238 otherwise) modified? */
239 unsigned grp_maybe_modified : 1;
241 /* Set when this is a representative of a pointer to scalar (i.e. by
242 reference) parameter which we consider for turning into a plain scalar
243 (i.e. a by value parameter). */
244 unsigned grp_scalar_ptr : 1;
246 /* Set when we discover that this pointer is not safe to dereference in the
248 unsigned grp_not_necessarilly_dereferenced : 1;
251 typedef struct access *access_p;
253 DEF_VEC_P (access_p);
254 DEF_VEC_ALLOC_P (access_p, heap);
256 /* Alloc pool for allocating access structures. */
257 static alloc_pool access_pool;
259 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
260 are used to propagate subaccesses from rhs to lhs as long as they don't
261 conflict with what is already there. */
264 struct access *lacc, *racc;
265 struct assign_link *next;
268 /* Alloc pool for allocating assign link structures. */
269 static alloc_pool link_pool;
271 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
272 static struct pointer_map_t *base_access_vec;
274 /* Bitmap of candidates. */
275 static bitmap candidate_bitmap;
277 /* Bitmap of candidates which we should try to entirely scalarize away and
278 those which cannot be (because they are and need be used as a whole). */
279 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
281 /* Obstack for creation of fancy names. */
282 static struct obstack name_obstack;
284 /* Head of a linked list of accesses that need to have its subaccesses
285 propagated to their assignment counterparts. */
286 static struct access *work_queue_head;
288 /* Number of parameters of the analyzed function when doing early ipa SRA. */
289 static int func_param_count;
291 /* scan_function sets the following to true if it encounters a call to
292 __builtin_apply_args. */
293 static bool encountered_apply_args;
295 /* Set by scan_function when it finds a recursive call. */
296 static bool encountered_recursive_call;
298 /* Set by scan_function when it finds a recursive call with less actual
299 arguments than formal parameters.. */
300 static bool encountered_unchangable_recursive_call;
302 /* This is a table in which for each basic block and parameter there is a
303 distance (offset + size) in that parameter which is dereferenced and
304 accessed in that BB. */
305 static HOST_WIDE_INT *bb_dereferences;
306 /* Bitmap of BBs that can cause the function to "stop" progressing by
307 returning, throwing externally, looping infinitely or calling a function
308 which might abort etc.. */
309 static bitmap final_bbs;
311 /* Representative of no accesses at all. */
312 static struct access no_accesses_representant;
314 /* Predicate to test the special value. */
317 no_accesses_p (struct access *access)
319 return access == &no_accesses_representant;
322 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
323 representative fields are dumped, otherwise those which only describe the
324 individual access are. */
328 /* Number of processed aggregates is readily available in
329 analyze_all_variable_accesses and so is not stored here. */
331 /* Number of created scalar replacements. */
334 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
338 /* Number of statements created by generate_subtree_copies. */
341 /* Number of statements created by load_assign_lhs_subreplacements. */
344 /* Number of times sra_modify_assign has deleted a statement. */
347 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
348 RHS reparately due to type conversions or nonexistent matching
350 int separate_lhs_rhs_handling;
352 /* Number of parameters that were removed because they were unused. */
353 int deleted_unused_parameters;
355 /* Number of scalars passed as parameters by reference that have been
356 converted to be passed by value. */
357 int scalar_by_ref_to_by_val;
359 /* Number of aggregate parameters that were replaced by one or more of their
361 int aggregate_params_reduced;
363 /* Numbber of components created when splitting aggregate parameters. */
364 int param_reductions_created;
368 dump_access (FILE *f, struct access *access, bool grp)
370 fprintf (f, "access { ");
371 fprintf (f, "base = (%d)'", DECL_UID (access->base));
372 print_generic_expr (f, access->base, 0);
373 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
374 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
375 fprintf (f, ", expr = ");
376 print_generic_expr (f, access->expr, 0);
377 fprintf (f, ", type = ");
378 print_generic_expr (f, access->type, 0);
380 fprintf (f, ", total_scalarization = %d, grp_read = %d, grp_write = %d, "
381 "grp_assignment_read = %d, grp_assignment_write = %d, "
382 "grp_scalar_read = %d, grp_scalar_write = %d, "
383 "grp_hint = %d, grp_covered = %d, "
384 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
385 "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
386 "grp_maybe_modified = %d, "
387 "grp_not_necessarilly_dereferenced = %d\n",
388 access->total_scalarization, access->grp_read, access->grp_write,
389 access->grp_assignment_read, access->grp_assignment_write,
390 access->grp_scalar_read, access->grp_scalar_write,
391 access->grp_hint, access->grp_covered,
392 access->grp_unscalarizable_region, access->grp_unscalarized_data,
393 access->grp_partial_lhs, access->grp_to_be_replaced,
394 access->grp_maybe_modified,
395 access->grp_not_necessarilly_dereferenced);
397 fprintf (f, ", write = %d, total_scalarization = %d, "
398 "grp_partial_lhs = %d\n",
399 access->write, access->total_scalarization,
400 access->grp_partial_lhs);
403 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
406 dump_access_tree_1 (FILE *f, struct access *access, int level)
412 for (i = 0; i < level; i++)
413 fputs ("* ", dump_file);
415 dump_access (f, access, true);
417 if (access->first_child)
418 dump_access_tree_1 (f, access->first_child, level + 1);
420 access = access->next_sibling;
425 /* Dump all access trees for a variable, given the pointer to the first root in
429 dump_access_tree (FILE *f, struct access *access)
431 for (; access; access = access->next_grp)
432 dump_access_tree_1 (f, access, 0);
435 /* Return true iff ACC is non-NULL and has subaccesses. */
438 access_has_children_p (struct access *acc)
440 return acc && acc->first_child;
443 /* Return a vector of pointers to accesses for the variable given in BASE or
444 NULL if there is none. */
446 static VEC (access_p, heap) *
447 get_base_access_vector (tree base)
451 slot = pointer_map_contains (base_access_vec, base);
455 return *(VEC (access_p, heap) **) slot;
458 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
459 in ACCESS. Return NULL if it cannot be found. */
461 static struct access *
462 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
465 while (access && (access->offset != offset || access->size != size))
467 struct access *child = access->first_child;
469 while (child && (child->offset + child->size <= offset))
470 child = child->next_sibling;
477 /* Return the first group representative for DECL or NULL if none exists. */
479 static struct access *
480 get_first_repr_for_decl (tree base)
482 VEC (access_p, heap) *access_vec;
484 access_vec = get_base_access_vector (base);
488 return VEC_index (access_p, access_vec, 0);
491 /* Find an access representative for the variable BASE and given OFFSET and
492 SIZE. Requires that access trees have already been built. Return NULL if
493 it cannot be found. */
495 static struct access *
496 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
499 struct access *access;
501 access = get_first_repr_for_decl (base);
502 while (access && (access->offset + access->size <= offset))
503 access = access->next_grp;
507 return find_access_in_subtree (access, offset, size);
510 /* Add LINK to the linked list of assign links of RACC. */
512 add_link_to_rhs (struct access *racc, struct assign_link *link)
514 gcc_assert (link->racc == racc);
516 if (!racc->first_link)
518 gcc_assert (!racc->last_link);
519 racc->first_link = link;
522 racc->last_link->next = link;
524 racc->last_link = link;
528 /* Move all link structures in their linked list in OLD_RACC to the linked list
531 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
533 if (!old_racc->first_link)
535 gcc_assert (!old_racc->last_link);
539 if (new_racc->first_link)
541 gcc_assert (!new_racc->last_link->next);
542 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
544 new_racc->last_link->next = old_racc->first_link;
545 new_racc->last_link = old_racc->last_link;
549 gcc_assert (!new_racc->last_link);
551 new_racc->first_link = old_racc->first_link;
552 new_racc->last_link = old_racc->last_link;
554 old_racc->first_link = old_racc->last_link = NULL;
557 /* Add ACCESS to the work queue (which is actually a stack). */
560 add_access_to_work_queue (struct access *access)
562 if (!access->grp_queued)
564 gcc_assert (!access->next_queued);
565 access->next_queued = work_queue_head;
566 access->grp_queued = 1;
567 work_queue_head = access;
571 /* Pop an access from the work queue, and return it, assuming there is one. */
573 static struct access *
574 pop_access_from_work_queue (void)
576 struct access *access = work_queue_head;
578 work_queue_head = access->next_queued;
579 access->next_queued = NULL;
580 access->grp_queued = 0;
585 /* Allocate necessary structures. */
588 sra_initialize (void)
590 candidate_bitmap = BITMAP_ALLOC (NULL);
591 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
592 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
593 gcc_obstack_init (&name_obstack);
594 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
595 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
596 base_access_vec = pointer_map_create ();
597 memset (&sra_stats, 0, sizeof (sra_stats));
598 encountered_apply_args = false;
599 encountered_recursive_call = false;
600 encountered_unchangable_recursive_call = false;
603 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
606 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
607 void *data ATTRIBUTE_UNUSED)
609 VEC (access_p, heap) *access_vec;
610 access_vec = (VEC (access_p, heap) *) *value;
611 VEC_free (access_p, heap, access_vec);
616 /* Deallocate all general structures. */
619 sra_deinitialize (void)
621 BITMAP_FREE (candidate_bitmap);
622 BITMAP_FREE (should_scalarize_away_bitmap);
623 BITMAP_FREE (cannot_scalarize_away_bitmap);
624 free_alloc_pool (access_pool);
625 free_alloc_pool (link_pool);
626 obstack_free (&name_obstack, NULL);
628 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
629 pointer_map_destroy (base_access_vec);
632 /* Remove DECL from candidates for SRA and write REASON to the dump file if
635 disqualify_candidate (tree decl, const char *reason)
637 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
639 if (dump_file && (dump_flags & TDF_DETAILS))
641 fprintf (dump_file, "! Disqualifying ");
642 print_generic_expr (dump_file, decl, 0);
643 fprintf (dump_file, " - %s\n", reason);
647 /* Return true iff the type contains a field or an element which does not allow
651 type_internals_preclude_sra_p (tree type, const char **msg)
656 switch (TREE_CODE (type))
660 case QUAL_UNION_TYPE:
661 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
662 if (TREE_CODE (fld) == FIELD_DECL)
664 tree ft = TREE_TYPE (fld);
666 if (TREE_THIS_VOLATILE (fld))
668 *msg = "volatile structure field";
671 if (!DECL_FIELD_OFFSET (fld))
673 *msg = "no structure field offset";
676 if (!DECL_SIZE (fld))
678 *msg = "zero structure field size";
681 if (!host_integerp (DECL_FIELD_OFFSET (fld), 1))
683 *msg = "structure field offset not fixed";
686 if (!host_integerp (DECL_SIZE (fld), 1))
688 *msg = "structure field size not fixed";
691 if (AGGREGATE_TYPE_P (ft)
692 && int_bit_position (fld) % BITS_PER_UNIT != 0)
694 *msg = "structure field is bit field";
698 if (AGGREGATE_TYPE_P (ft) && type_internals_preclude_sra_p (ft, msg))
705 et = TREE_TYPE (type);
707 if (TYPE_VOLATILE (et))
709 *msg = "element type is volatile";
713 if (AGGREGATE_TYPE_P (et) && type_internals_preclude_sra_p (et, msg))
723 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
724 base variable if it is. Return T if it is not an SSA_NAME. */
727 get_ssa_base_param (tree t)
729 if (TREE_CODE (t) == SSA_NAME)
731 if (SSA_NAME_IS_DEFAULT_DEF (t))
732 return SSA_NAME_VAR (t);
739 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
740 belongs to, unless the BB has already been marked as a potentially
744 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
746 basic_block bb = gimple_bb (stmt);
747 int idx, parm_index = 0;
750 if (bitmap_bit_p (final_bbs, bb->index))
753 for (parm = DECL_ARGUMENTS (current_function_decl);
754 parm && parm != base;
755 parm = DECL_CHAIN (parm))
758 gcc_assert (parm_index < func_param_count);
760 idx = bb->index * func_param_count + parm_index;
761 if (bb_dereferences[idx] < dist)
762 bb_dereferences[idx] = dist;
765 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
766 the three fields. Also add it to the vector of accesses corresponding to
767 the base. Finally, return the new access. */
769 static struct access *
770 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
772 VEC (access_p, heap) *vec;
773 struct access *access;
776 access = (struct access *) pool_alloc (access_pool);
777 memset (access, 0, sizeof (struct access));
779 access->offset = offset;
782 slot = pointer_map_contains (base_access_vec, base);
784 vec = (VEC (access_p, heap) *) *slot;
786 vec = VEC_alloc (access_p, heap, 32);
788 VEC_safe_push (access_p, heap, vec, access);
790 *((struct VEC (access_p,heap) **)
791 pointer_map_insert (base_access_vec, base)) = vec;
796 /* Create and insert access for EXPR. Return created access, or NULL if it is
799 static struct access *
800 create_access (tree expr, gimple stmt, bool write)
802 struct access *access;
803 HOST_WIDE_INT offset, size, max_size;
805 bool ptr, unscalarizable_region = false;
807 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
809 if (sra_mode == SRA_MODE_EARLY_IPA
810 && TREE_CODE (base) == MEM_REF)
812 base = get_ssa_base_param (TREE_OPERAND (base, 0));
820 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
823 if (sra_mode == SRA_MODE_EARLY_IPA)
825 if (size < 0 || size != max_size)
827 disqualify_candidate (base, "Encountered a variable sized access.");
830 if (TREE_CODE (expr) == COMPONENT_REF
831 && DECL_BIT_FIELD (TREE_OPERAND (expr, 1)))
833 disqualify_candidate (base, "Encountered a bit-field access.");
836 gcc_checking_assert ((offset % BITS_PER_UNIT) == 0);
839 mark_parm_dereference (base, offset + size, stmt);
843 if (size != max_size)
846 unscalarizable_region = true;
850 disqualify_candidate (base, "Encountered an unconstrained access.");
855 access = create_access_1 (base, offset, size);
857 access->type = TREE_TYPE (expr);
858 access->write = write;
859 access->grp_unscalarizable_region = unscalarizable_region;
862 if (TREE_CODE (expr) == COMPONENT_REF
863 && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1)))
864 access->non_addressable = 1;
870 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
871 register types or (recursively) records with only these two kinds of fields.
872 It also returns false if any of these records contains a bit-field. */
875 type_consists_of_records_p (tree type)
879 if (TREE_CODE (type) != RECORD_TYPE)
882 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
883 if (TREE_CODE (fld) == FIELD_DECL)
885 tree ft = TREE_TYPE (fld);
887 if (DECL_BIT_FIELD (fld))
890 if (!is_gimple_reg_type (ft)
891 && !type_consists_of_records_p (ft))
898 /* Create total_scalarization accesses for all scalar type fields in DECL that
899 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE
900 must be the top-most VAR_DECL representing the variable, OFFSET must be the
901 offset of DECL within BASE. REF must be the memory reference expression for
905 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset,
908 tree fld, decl_type = TREE_TYPE (decl);
910 for (fld = TYPE_FIELDS (decl_type); fld; fld = DECL_CHAIN (fld))
911 if (TREE_CODE (fld) == FIELD_DECL)
913 HOST_WIDE_INT pos = offset + int_bit_position (fld);
914 tree ft = TREE_TYPE (fld);
915 tree nref = build3 (COMPONENT_REF, TREE_TYPE (fld), ref, fld,
918 if (is_gimple_reg_type (ft))
920 struct access *access;
923 size = tree_low_cst (DECL_SIZE (fld), 1);
924 access = create_access_1 (base, pos, size);
927 access->total_scalarization = 1;
928 /* Accesses for intraprocedural SRA can have their stmt NULL. */
931 completely_scalarize_record (base, fld, pos, nref);
936 /* Search the given tree for a declaration by skipping handled components and
937 exclude it from the candidates. */
940 disqualify_base_of_expr (tree t, const char *reason)
942 t = get_base_address (t);
943 if (sra_mode == SRA_MODE_EARLY_IPA
944 && TREE_CODE (t) == MEM_REF)
945 t = get_ssa_base_param (TREE_OPERAND (t, 0));
948 disqualify_candidate (t, reason);
951 /* Scan expression EXPR and create access structures for all accesses to
952 candidates for scalarization. Return the created access or NULL if none is
955 static struct access *
956 build_access_from_expr_1 (tree expr, gimple stmt, bool write)
958 struct access *ret = NULL;
961 if (TREE_CODE (expr) == BIT_FIELD_REF
962 || TREE_CODE (expr) == IMAGPART_EXPR
963 || TREE_CODE (expr) == REALPART_EXPR)
965 expr = TREE_OPERAND (expr, 0);
971 /* We need to dive through V_C_Es in order to get the size of its parameter
972 and not the result type. Ada produces such statements. We are also
973 capable of handling the topmost V_C_E but not any of those buried in other
974 handled components. */
975 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
976 expr = TREE_OPERAND (expr, 0);
978 if (contains_view_convert_expr_p (expr))
980 disqualify_base_of_expr (expr, "V_C_E under a different handled "
985 switch (TREE_CODE (expr))
988 if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR
989 && sra_mode != SRA_MODE_EARLY_IPA)
997 case ARRAY_RANGE_REF:
998 ret = create_access (expr, stmt, write);
1005 if (write && partial_ref && ret)
1006 ret->grp_partial_lhs = 1;
1011 /* Scan expression EXPR and create access structures for all accesses to
1012 candidates for scalarization. Return true if any access has been inserted.
1013 STMT must be the statement from which the expression is taken, WRITE must be
1014 true if the expression is a store and false otherwise. */
1017 build_access_from_expr (tree expr, gimple stmt, bool write)
1019 struct access *access;
1021 access = build_access_from_expr_1 (expr, stmt, write);
1024 /* This means the aggregate is accesses as a whole in a way other than an
1025 assign statement and thus cannot be removed even if we had a scalar
1026 replacement for everything. */
1027 if (cannot_scalarize_away_bitmap)
1028 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1034 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
1035 modes in which it matters, return true iff they have been disqualified. RHS
1036 may be NULL, in that case ignore it. If we scalarize an aggregate in
1037 intra-SRA we may need to add statements after each statement. This is not
1038 possible if a statement unconditionally has to end the basic block. */
1040 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
1042 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1043 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
1045 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1047 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1053 /* Scan expressions occuring in STMT, create access structures for all accesses
1054 to candidates for scalarization and remove those candidates which occur in
1055 statements or expressions that prevent them from being split apart. Return
1056 true if any access has been inserted. */
1059 build_accesses_from_assign (gimple stmt)
1062 struct access *lacc, *racc;
1064 if (!gimple_assign_single_p (stmt))
1067 lhs = gimple_assign_lhs (stmt);
1068 rhs = gimple_assign_rhs1 (stmt);
1070 if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
1073 racc = build_access_from_expr_1 (rhs, stmt, false);
1074 lacc = build_access_from_expr_1 (lhs, stmt, true);
1077 lacc->grp_assignment_write = 1;
1081 racc->grp_assignment_read = 1;
1082 if (should_scalarize_away_bitmap && !gimple_has_volatile_ops (stmt)
1083 && !is_gimple_reg_type (racc->type))
1084 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1088 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1089 && !lacc->grp_unscalarizable_region
1090 && !racc->grp_unscalarizable_region
1091 && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1092 /* FIXME: Turn the following line into an assert after PR 40058 is
1094 && lacc->size == racc->size
1095 && useless_type_conversion_p (lacc->type, racc->type))
1097 struct assign_link *link;
1099 link = (struct assign_link *) pool_alloc (link_pool);
1100 memset (link, 0, sizeof (struct assign_link));
1105 add_link_to_rhs (racc, link);
1108 return lacc || racc;
1111 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1112 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1115 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1116 void *data ATTRIBUTE_UNUSED)
1118 op = get_base_address (op);
1121 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1126 /* Return true iff callsite CALL has at least as many actual arguments as there
1127 are formal parameters of the function currently processed by IPA-SRA. */
1130 callsite_has_enough_arguments_p (gimple call)
1132 return gimple_call_num_args (call) >= (unsigned) func_param_count;
1135 /* Scan function and look for interesting expressions and create access
1136 structures for them. Return true iff any access is created. */
1139 scan_function (void)
1146 gimple_stmt_iterator gsi;
1147 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1149 gimple stmt = gsi_stmt (gsi);
1153 if (final_bbs && stmt_can_throw_external (stmt))
1154 bitmap_set_bit (final_bbs, bb->index);
1155 switch (gimple_code (stmt))
1158 t = gimple_return_retval (stmt);
1160 ret |= build_access_from_expr (t, stmt, false);
1162 bitmap_set_bit (final_bbs, bb->index);
1166 ret |= build_accesses_from_assign (stmt);
1170 for (i = 0; i < gimple_call_num_args (stmt); i++)
1171 ret |= build_access_from_expr (gimple_call_arg (stmt, i),
1174 if (sra_mode == SRA_MODE_EARLY_IPA)
1176 tree dest = gimple_call_fndecl (stmt);
1177 int flags = gimple_call_flags (stmt);
1181 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1182 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1183 encountered_apply_args = true;
1184 if (cgraph_get_node (dest)
1185 == cgraph_get_node (current_function_decl))
1187 encountered_recursive_call = true;
1188 if (!callsite_has_enough_arguments_p (stmt))
1189 encountered_unchangable_recursive_call = true;
1194 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1195 bitmap_set_bit (final_bbs, bb->index);
1198 t = gimple_call_lhs (stmt);
1199 if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
1200 ret |= build_access_from_expr (t, stmt, true);
1204 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1207 bitmap_set_bit (final_bbs, bb->index);
1209 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1211 t = TREE_VALUE (gimple_asm_input_op (stmt, i));
1212 ret |= build_access_from_expr (t, stmt, false);
1214 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1216 t = TREE_VALUE (gimple_asm_output_op (stmt, i));
1217 ret |= build_access_from_expr (t, stmt, true);
1230 /* Helper of QSORT function. There are pointers to accesses in the array. An
1231 access is considered smaller than another if it has smaller offset or if the
1232 offsets are the same but is size is bigger. */
1235 compare_access_positions (const void *a, const void *b)
1237 const access_p *fp1 = (const access_p *) a;
1238 const access_p *fp2 = (const access_p *) b;
1239 const access_p f1 = *fp1;
1240 const access_p f2 = *fp2;
1242 if (f1->offset != f2->offset)
1243 return f1->offset < f2->offset ? -1 : 1;
1245 if (f1->size == f2->size)
1247 if (f1->type == f2->type)
1249 /* Put any non-aggregate type before any aggregate type. */
1250 else if (!is_gimple_reg_type (f1->type)
1251 && is_gimple_reg_type (f2->type))
1253 else if (is_gimple_reg_type (f1->type)
1254 && !is_gimple_reg_type (f2->type))
1256 /* Put any complex or vector type before any other scalar type. */
1257 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1258 && TREE_CODE (f1->type) != VECTOR_TYPE
1259 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1260 || TREE_CODE (f2->type) == VECTOR_TYPE))
1262 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1263 || TREE_CODE (f1->type) == VECTOR_TYPE)
1264 && TREE_CODE (f2->type) != COMPLEX_TYPE
1265 && TREE_CODE (f2->type) != VECTOR_TYPE)
1267 /* Put the integral type with the bigger precision first. */
1268 else if (INTEGRAL_TYPE_P (f1->type)
1269 && INTEGRAL_TYPE_P (f2->type))
1270 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1271 /* Put any integral type with non-full precision last. */
1272 else if (INTEGRAL_TYPE_P (f1->type)
1273 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1274 != TYPE_PRECISION (f1->type)))
1276 else if (INTEGRAL_TYPE_P (f2->type)
1277 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1278 != TYPE_PRECISION (f2->type)))
1280 /* Stabilize the sort. */
1281 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1284 /* We want the bigger accesses first, thus the opposite operator in the next
1286 return f1->size > f2->size ? -1 : 1;
1290 /* Append a name of the declaration to the name obstack. A helper function for
1294 make_fancy_decl_name (tree decl)
1298 tree name = DECL_NAME (decl);
1300 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1301 IDENTIFIER_LENGTH (name));
1304 sprintf (buffer, "D%u", DECL_UID (decl));
1305 obstack_grow (&name_obstack, buffer, strlen (buffer));
1309 /* Helper for make_fancy_name. */
1312 make_fancy_name_1 (tree expr)
1319 make_fancy_decl_name (expr);
1323 switch (TREE_CODE (expr))
1326 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1327 obstack_1grow (&name_obstack, '$');
1328 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1332 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1333 obstack_1grow (&name_obstack, '$');
1334 /* Arrays with only one element may not have a constant as their
1336 index = TREE_OPERAND (expr, 1);
1337 if (TREE_CODE (index) != INTEGER_CST)
1339 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1340 obstack_grow (&name_obstack, buffer, strlen (buffer));
1344 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1348 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1349 if (!integer_zerop (TREE_OPERAND (expr, 1)))
1351 obstack_1grow (&name_obstack, '$');
1352 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1353 TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1354 obstack_grow (&name_obstack, buffer, strlen (buffer));
1361 gcc_unreachable (); /* we treat these as scalars. */
1368 /* Create a human readable name for replacement variable of ACCESS. */
1371 make_fancy_name (tree expr)
1373 make_fancy_name_1 (expr);
1374 obstack_1grow (&name_obstack, '\0');
1375 return XOBFINISH (&name_obstack, char *);
1378 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1379 EXP_TYPE at the given OFFSET. If BASE is something for which
1380 get_addr_base_and_unit_offset returns NULL, gsi must be non-NULL and is used
1381 to insert new statements either before or below the current one as specified
1382 by INSERT_AFTER. This function is not capable of handling bitfields. */
1385 build_ref_for_offset (location_t loc, tree base, HOST_WIDE_INT offset,
1386 tree exp_type, gimple_stmt_iterator *gsi,
1389 tree prev_base = base;
1391 HOST_WIDE_INT base_offset;
1393 gcc_checking_assert (offset % BITS_PER_UNIT == 0);
1395 base = get_addr_base_and_unit_offset (base, &base_offset);
1397 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1398 offset such as array[var_index]. */
1404 gcc_checking_assert (gsi);
1405 tmp = create_tmp_reg (build_pointer_type (TREE_TYPE (prev_base)), NULL);
1406 add_referenced_var (tmp);
1407 tmp = make_ssa_name (tmp, NULL);
1408 addr = build_fold_addr_expr (unshare_expr (prev_base));
1409 STRIP_USELESS_TYPE_CONVERSION (addr);
1410 stmt = gimple_build_assign (tmp, addr);
1411 gimple_set_location (stmt, loc);
1412 SSA_NAME_DEF_STMT (tmp) = stmt;
1414 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1416 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1419 off = build_int_cst (reference_alias_ptr_type (prev_base),
1420 offset / BITS_PER_UNIT);
1423 else if (TREE_CODE (base) == MEM_REF)
1425 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1426 base_offset + offset / BITS_PER_UNIT);
1427 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1428 base = unshare_expr (TREE_OPERAND (base, 0));
1432 off = build_int_cst (reference_alias_ptr_type (base),
1433 base_offset + offset / BITS_PER_UNIT);
1434 base = build_fold_addr_expr (unshare_expr (base));
1437 return fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1440 /* Construct a memory reference to a part of an aggregate BASE at the given
1441 OFFSET and of the same type as MODEL. In case this is a reference to a
1442 component, the function will replicate the last COMPONENT_REF of model's
1443 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1444 build_ref_for_offset. */
1447 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1448 struct access *model, gimple_stmt_iterator *gsi,
1451 if (TREE_CODE (model->expr) == COMPONENT_REF)
1453 tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
1454 tree cr_offset = component_ref_field_offset (model->expr);
1456 gcc_assert (cr_offset && host_integerp (cr_offset, 1));
1457 offset -= TREE_INT_CST_LOW (cr_offset) * BITS_PER_UNIT;
1458 offset -= TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fld));
1459 exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
1460 t = build_ref_for_offset (loc, base, offset, exp_type, gsi, insert_after);
1461 return fold_build3_loc (loc, COMPONENT_REF, model->type, t, fld,
1462 TREE_OPERAND (model->expr, 2));
1465 return build_ref_for_offset (loc, base, offset, model->type,
1469 /* Construct a memory reference consisting of component_refs and array_refs to
1470 a part of an aggregate *RES (which is of type TYPE). The requested part
1471 should have type EXP_TYPE at be the given OFFSET. This function might not
1472 succeed, it returns true when it does and only then *RES points to something
1473 meaningful. This function should be used only to build expressions that we
1474 might need to present to user (e.g. in warnings). In all other situations,
1475 build_ref_for_model or build_ref_for_offset should be used instead. */
1478 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
1484 tree tr_size, index, minidx;
1485 HOST_WIDE_INT el_size;
1487 if (offset == 0 && exp_type
1488 && types_compatible_p (exp_type, type))
1491 switch (TREE_CODE (type))
1494 case QUAL_UNION_TYPE:
1496 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1498 HOST_WIDE_INT pos, size;
1499 tree expr, *expr_ptr;
1501 if (TREE_CODE (fld) != FIELD_DECL)
1504 pos = int_bit_position (fld);
1505 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1506 tr_size = DECL_SIZE (fld);
1507 if (!tr_size || !host_integerp (tr_size, 1))
1509 size = tree_low_cst (tr_size, 1);
1515 else if (pos > offset || (pos + size) <= offset)
1518 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1521 if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
1522 offset - pos, exp_type))
1531 tr_size = TYPE_SIZE (TREE_TYPE (type));
1532 if (!tr_size || !host_integerp (tr_size, 1))
1534 el_size = tree_low_cst (tr_size, 1);
1536 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1537 if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
1539 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1540 if (!integer_zerop (minidx))
1541 index = int_const_binop (PLUS_EXPR, index, minidx);
1542 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1543 NULL_TREE, NULL_TREE);
1544 offset = offset % el_size;
1545 type = TREE_TYPE (type);
1560 /* Return true iff TYPE is stdarg va_list type. */
1563 is_va_list_type (tree type)
1565 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1568 /* Print message to dump file why a variable was rejected. */
1571 reject (tree var, const char *msg)
1573 if (dump_file && (dump_flags & TDF_DETAILS))
1575 fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
1576 print_generic_expr (dump_file, var, 0);
1577 fprintf (dump_file, "\n");
1581 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1582 those with type which is suitable for scalarization. */
1585 find_var_candidates (void)
1588 referenced_var_iterator rvi;
1592 FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
1594 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1596 type = TREE_TYPE (var);
1598 if (!AGGREGATE_TYPE_P (type))
1600 reject (var, "not aggregate");
1603 if (needs_to_live_in_memory (var))
1605 reject (var, "needs to live in memory");
1608 if (TREE_THIS_VOLATILE (var))
1610 reject (var, "is volatile");
1613 if (!COMPLETE_TYPE_P (type))
1615 reject (var, "has incomplete type");
1618 if (!host_integerp (TYPE_SIZE (type), 1))
1620 reject (var, "type size not fixed");
1623 if (tree_low_cst (TYPE_SIZE (type), 1) == 0)
1625 reject (var, "type size is zero");
1628 if (type_internals_preclude_sra_p (type, &msg))
1633 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1634 we also want to schedule it rather late. Thus we ignore it in
1636 (sra_mode == SRA_MODE_EARLY_INTRA
1637 && is_va_list_type (type)))
1639 reject (var, "is va_list");
1643 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1645 if (dump_file && (dump_flags & TDF_DETAILS))
1647 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1648 print_generic_expr (dump_file, var, 0);
1649 fprintf (dump_file, "\n");
1657 /* Sort all accesses for the given variable, check for partial overlaps and
1658 return NULL if there are any. If there are none, pick a representative for
1659 each combination of offset and size and create a linked list out of them.
1660 Return the pointer to the first representative and make sure it is the first
1661 one in the vector of accesses. */
1663 static struct access *
1664 sort_and_splice_var_accesses (tree var)
1666 int i, j, access_count;
1667 struct access *res, **prev_acc_ptr = &res;
1668 VEC (access_p, heap) *access_vec;
1670 HOST_WIDE_INT low = -1, high = 0;
1672 access_vec = get_base_access_vector (var);
1675 access_count = VEC_length (access_p, access_vec);
1677 /* Sort by <OFFSET, SIZE>. */
1678 VEC_qsort (access_p, access_vec, compare_access_positions);
1681 while (i < access_count)
1683 struct access *access = VEC_index (access_p, access_vec, i);
1684 bool grp_write = access->write;
1685 bool grp_read = !access->write;
1686 bool grp_scalar_write = access->write
1687 && is_gimple_reg_type (access->type);
1688 bool grp_scalar_read = !access->write
1689 && is_gimple_reg_type (access->type);
1690 bool grp_assignment_read = access->grp_assignment_read;
1691 bool grp_assignment_write = access->grp_assignment_write;
1692 bool multiple_scalar_reads = false;
1693 bool total_scalarization = access->total_scalarization;
1694 bool grp_partial_lhs = access->grp_partial_lhs;
1695 bool first_scalar = is_gimple_reg_type (access->type);
1696 bool unscalarizable_region = access->grp_unscalarizable_region;
1698 if (first || access->offset >= high)
1701 low = access->offset;
1702 high = access->offset + access->size;
1704 else if (access->offset > low && access->offset + access->size > high)
1707 gcc_assert (access->offset >= low
1708 && access->offset + access->size <= high);
1711 while (j < access_count)
1713 struct access *ac2 = VEC_index (access_p, access_vec, j);
1714 if (ac2->offset != access->offset || ac2->size != access->size)
1719 grp_scalar_write = (grp_scalar_write
1720 || is_gimple_reg_type (ac2->type));
1725 if (is_gimple_reg_type (ac2->type))
1727 if (grp_scalar_read)
1728 multiple_scalar_reads = true;
1730 grp_scalar_read = true;
1733 grp_assignment_read |= ac2->grp_assignment_read;
1734 grp_assignment_write |= ac2->grp_assignment_write;
1735 grp_partial_lhs |= ac2->grp_partial_lhs;
1736 unscalarizable_region |= ac2->grp_unscalarizable_region;
1737 total_scalarization |= ac2->total_scalarization;
1738 relink_to_new_repr (access, ac2);
1740 /* If there are both aggregate-type and scalar-type accesses with
1741 this combination of size and offset, the comparison function
1742 should have put the scalars first. */
1743 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1744 ac2->group_representative = access;
1750 access->group_representative = access;
1751 access->grp_write = grp_write;
1752 access->grp_read = grp_read;
1753 access->grp_scalar_read = grp_scalar_read;
1754 access->grp_scalar_write = grp_scalar_write;
1755 access->grp_assignment_read = grp_assignment_read;
1756 access->grp_assignment_write = grp_assignment_write;
1757 access->grp_hint = multiple_scalar_reads || total_scalarization;
1758 access->grp_partial_lhs = grp_partial_lhs;
1759 access->grp_unscalarizable_region = unscalarizable_region;
1760 if (access->first_link)
1761 add_access_to_work_queue (access);
1763 *prev_acc_ptr = access;
1764 prev_acc_ptr = &access->next_grp;
1767 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1771 /* Create a variable for the given ACCESS which determines the type, name and a
1772 few other properties. Return the variable declaration and store it also to
1773 ACCESS->replacement. */
1776 create_access_replacement (struct access *access, bool rename)
1780 repl = create_tmp_var (access->type, "SR");
1782 add_referenced_var (repl);
1784 mark_sym_for_renaming (repl);
1786 if (!access->grp_partial_lhs
1787 && (TREE_CODE (access->type) == COMPLEX_TYPE
1788 || TREE_CODE (access->type) == VECTOR_TYPE))
1789 DECL_GIMPLE_REG_P (repl) = 1;
1791 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1792 DECL_ARTIFICIAL (repl) = 1;
1793 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1795 if (DECL_NAME (access->base)
1796 && !DECL_IGNORED_P (access->base)
1797 && !DECL_ARTIFICIAL (access->base))
1799 char *pretty_name = make_fancy_name (access->expr);
1800 tree debug_expr = unshare_expr (access->expr), d;
1802 DECL_NAME (repl) = get_identifier (pretty_name);
1803 obstack_free (&name_obstack, pretty_name);
1805 /* Get rid of any SSA_NAMEs embedded in debug_expr,
1806 as DECL_DEBUG_EXPR isn't considered when looking for still
1807 used SSA_NAMEs and thus they could be freed. All debug info
1808 generation cares is whether something is constant or variable
1809 and that get_ref_base_and_extent works properly on the
1811 for (d = debug_expr; handled_component_p (d); d = TREE_OPERAND (d, 0))
1812 switch (TREE_CODE (d))
1815 case ARRAY_RANGE_REF:
1816 if (TREE_OPERAND (d, 1)
1817 && TREE_CODE (TREE_OPERAND (d, 1)) == SSA_NAME)
1818 TREE_OPERAND (d, 1) = SSA_NAME_VAR (TREE_OPERAND (d, 1));
1819 if (TREE_OPERAND (d, 3)
1820 && TREE_CODE (TREE_OPERAND (d, 3)) == SSA_NAME)
1821 TREE_OPERAND (d, 3) = SSA_NAME_VAR (TREE_OPERAND (d, 3));
1824 if (TREE_OPERAND (d, 2)
1825 && TREE_CODE (TREE_OPERAND (d, 2)) == SSA_NAME)
1826 TREE_OPERAND (d, 2) = SSA_NAME_VAR (TREE_OPERAND (d, 2));
1831 SET_DECL_DEBUG_EXPR (repl, debug_expr);
1832 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1833 if (access->grp_no_warning)
1834 TREE_NO_WARNING (repl) = 1;
1836 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1839 TREE_NO_WARNING (repl) = 1;
1843 fprintf (dump_file, "Created a replacement for ");
1844 print_generic_expr (dump_file, access->base, 0);
1845 fprintf (dump_file, " offset: %u, size: %u: ",
1846 (unsigned) access->offset, (unsigned) access->size);
1847 print_generic_expr (dump_file, repl, 0);
1848 fprintf (dump_file, "\n");
1850 sra_stats.replacements++;
1855 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1858 get_access_replacement (struct access *access)
1860 gcc_assert (access->grp_to_be_replaced);
1862 if (!access->replacement_decl)
1863 access->replacement_decl = create_access_replacement (access, true);
1864 return access->replacement_decl;
1867 /* Return ACCESS scalar replacement, create it if it does not exist yet but do
1868 not mark it for renaming. */
1871 get_unrenamed_access_replacement (struct access *access)
1873 gcc_assert (!access->grp_to_be_replaced);
1875 if (!access->replacement_decl)
1876 access->replacement_decl = create_access_replacement (access, false);
1877 return access->replacement_decl;
1881 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1882 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1883 to it is not "within" the root. Return false iff some accesses partially
1887 build_access_subtree (struct access **access)
1889 struct access *root = *access, *last_child = NULL;
1890 HOST_WIDE_INT limit = root->offset + root->size;
1892 *access = (*access)->next_grp;
1893 while (*access && (*access)->offset + (*access)->size <= limit)
1896 root->first_child = *access;
1898 last_child->next_sibling = *access;
1899 last_child = *access;
1901 if (!build_access_subtree (access))
1905 if (*access && (*access)->offset < limit)
1911 /* Build a tree of access representatives, ACCESS is the pointer to the first
1912 one, others are linked in a list by the next_grp field. Return false iff
1913 some accesses partially overlap. */
1916 build_access_trees (struct access *access)
1920 struct access *root = access;
1922 if (!build_access_subtree (&access))
1924 root->next_grp = access;
1929 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1933 expr_with_var_bounded_array_refs_p (tree expr)
1935 while (handled_component_p (expr))
1937 if (TREE_CODE (expr) == ARRAY_REF
1938 && !host_integerp (array_ref_low_bound (expr), 0))
1940 expr = TREE_OPERAND (expr, 0);
1945 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1946 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all
1947 sorts of access flags appropriately along the way, notably always set
1948 grp_read and grp_assign_read according to MARK_READ and grp_write when
1951 Creating a replacement for a scalar access is considered beneficial if its
1952 grp_hint is set (this means we are either attempting total scalarization or
1953 there is more than one direct read access) or according to the following
1956 Access written to through a scalar type (once or more times)
1958 | Written to in an assignment statement
1960 | | Access read as scalar _once_
1962 | | | Read in an assignment statement
1964 | | | | Scalarize Comment
1965 -----------------------------------------------------------------------------
1966 0 0 0 0 No access for the scalar
1967 0 0 0 1 No access for the scalar
1968 0 0 1 0 No Single read - won't help
1969 0 0 1 1 No The same case
1970 0 1 0 0 No access for the scalar
1971 0 1 0 1 No access for the scalar
1972 0 1 1 0 Yes s = *g; return s.i;
1973 0 1 1 1 Yes The same case as above
1974 1 0 0 0 No Won't help
1975 1 0 0 1 Yes s.i = 1; *g = s;
1976 1 0 1 0 Yes s.i = 5; g = s.i;
1977 1 0 1 1 Yes The same case as above
1978 1 1 0 0 No Won't help.
1979 1 1 0 1 Yes s.i = 1; *g = s;
1980 1 1 1 0 Yes s = *g; return s.i;
1981 1 1 1 1 Yes Any of the above yeses */
1984 analyze_access_subtree (struct access *root, struct access *parent,
1985 bool allow_replacements)
1987 struct access *child;
1988 HOST_WIDE_INT limit = root->offset + root->size;
1989 HOST_WIDE_INT covered_to = root->offset;
1990 bool scalar = is_gimple_reg_type (root->type);
1991 bool hole = false, sth_created = false;
1995 if (parent->grp_read)
1997 if (parent->grp_assignment_read)
1998 root->grp_assignment_read = 1;
1999 if (parent->grp_write)
2000 root->grp_write = 1;
2001 if (parent->grp_assignment_write)
2002 root->grp_assignment_write = 1;
2005 if (root->grp_unscalarizable_region)
2006 allow_replacements = false;
2008 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2009 allow_replacements = false;
2011 for (child = root->first_child; child; child = child->next_sibling)
2013 if (!hole && child->offset < covered_to)
2016 covered_to += child->size;
2018 sth_created |= analyze_access_subtree (child, root,
2019 allow_replacements && !scalar);
2021 root->grp_unscalarized_data |= child->grp_unscalarized_data;
2022 hole |= !child->grp_covered;
2025 if (allow_replacements && scalar && !root->first_child
2027 || ((root->grp_scalar_read || root->grp_assignment_read)
2028 && (root->grp_scalar_write || root->grp_assignment_write))))
2030 if (dump_file && (dump_flags & TDF_DETAILS))
2032 fprintf (dump_file, "Marking ");
2033 print_generic_expr (dump_file, root->base, 0);
2034 fprintf (dump_file, " offset: %u, size: %u: ",
2035 (unsigned) root->offset, (unsigned) root->size);
2036 fprintf (dump_file, " to be replaced.\n");
2039 root->grp_to_be_replaced = 1;
2043 else if (covered_to < limit)
2046 if (sth_created && !hole)
2048 root->grp_covered = 1;
2051 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
2052 root->grp_unscalarized_data = 1; /* not covered and written to */
2058 /* Analyze all access trees linked by next_grp by the means of
2059 analyze_access_subtree. */
2061 analyze_access_trees (struct access *access)
2067 if (analyze_access_subtree (access, NULL, true))
2069 access = access->next_grp;
2075 /* Return true iff a potential new child of LACC at offset OFFSET and with size
2076 SIZE would conflict with an already existing one. If exactly such a child
2077 already exists in LACC, store a pointer to it in EXACT_MATCH. */
2080 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
2081 HOST_WIDE_INT size, struct access **exact_match)
2083 struct access *child;
2085 for (child = lacc->first_child; child; child = child->next_sibling)
2087 if (child->offset == norm_offset && child->size == size)
2089 *exact_match = child;
2093 if (child->offset < norm_offset + size
2094 && child->offset + child->size > norm_offset)
2101 /* Create a new child access of PARENT, with all properties just like MODEL
2102 except for its offset and with its grp_write false and grp_read true.
2103 Return the new access or NULL if it cannot be created. Note that this access
2104 is created long after all splicing and sorting, it's not located in any
2105 access vector and is automatically a representative of its group. */
2107 static struct access *
2108 create_artificial_child_access (struct access *parent, struct access *model,
2109 HOST_WIDE_INT new_offset)
2111 struct access *access;
2112 struct access **child;
2113 tree expr = parent->base;
2115 gcc_assert (!model->grp_unscalarizable_region);
2117 access = (struct access *) pool_alloc (access_pool);
2118 memset (access, 0, sizeof (struct access));
2119 if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
2122 access->grp_no_warning = true;
2123 expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
2124 new_offset, model, NULL, false);
2127 access->base = parent->base;
2128 access->expr = expr;
2129 access->offset = new_offset;
2130 access->size = model->size;
2131 access->type = model->type;
2132 access->grp_write = true;
2133 access->grp_read = false;
2135 child = &parent->first_child;
2136 while (*child && (*child)->offset < new_offset)
2137 child = &(*child)->next_sibling;
2139 access->next_sibling = *child;
2146 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
2147 true if any new subaccess was created. Additionally, if RACC is a scalar
2148 access but LACC is not, change the type of the latter, if possible. */
2151 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
2153 struct access *rchild;
2154 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
2157 if (is_gimple_reg_type (lacc->type)
2158 || lacc->grp_unscalarizable_region
2159 || racc->grp_unscalarizable_region)
2162 if (!lacc->first_child && !racc->first_child
2163 && is_gimple_reg_type (racc->type))
2165 tree t = lacc->base;
2167 lacc->type = racc->type;
2168 if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t), lacc->offset,
2173 lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
2174 lacc->base, lacc->offset,
2176 lacc->grp_no_warning = true;
2181 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
2183 struct access *new_acc = NULL;
2184 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
2186 if (rchild->grp_unscalarizable_region)
2189 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
2194 rchild->grp_hint = 1;
2195 new_acc->grp_hint |= new_acc->grp_read;
2196 if (rchild->first_child)
2197 ret |= propagate_subaccesses_across_link (new_acc, rchild);
2202 rchild->grp_hint = 1;
2203 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
2207 if (racc->first_child)
2208 propagate_subaccesses_across_link (new_acc, rchild);
2215 /* Propagate all subaccesses across assignment links. */
2218 propagate_all_subaccesses (void)
2220 while (work_queue_head)
2222 struct access *racc = pop_access_from_work_queue ();
2223 struct assign_link *link;
2225 gcc_assert (racc->first_link);
2227 for (link = racc->first_link; link; link = link->next)
2229 struct access *lacc = link->lacc;
2231 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2233 lacc = lacc->group_representative;
2234 if (propagate_subaccesses_across_link (lacc, racc)
2235 && lacc->first_link)
2236 add_access_to_work_queue (lacc);
2241 /* Go through all accesses collected throughout the (intraprocedural) analysis
2242 stage, exclude overlapping ones, identify representatives and build trees
2243 out of them, making decisions about scalarization on the way. Return true
2244 iff there are any to-be-scalarized variables after this stage. */
2247 analyze_all_variable_accesses (void)
2250 bitmap tmp = BITMAP_ALLOC (NULL);
2252 unsigned i, max_total_scalarization_size;
2254 max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2255 * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2257 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2258 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2259 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2261 tree var = referenced_var (i);
2263 if (TREE_CODE (var) == VAR_DECL
2264 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2265 <= max_total_scalarization_size)
2266 && type_consists_of_records_p (TREE_TYPE (var)))
2268 completely_scalarize_record (var, var, 0, var);
2269 if (dump_file && (dump_flags & TDF_DETAILS))
2271 fprintf (dump_file, "Will attempt to totally scalarize ");
2272 print_generic_expr (dump_file, var, 0);
2273 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2278 bitmap_copy (tmp, candidate_bitmap);
2279 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2281 tree var = referenced_var (i);
2282 struct access *access;
2284 access = sort_and_splice_var_accesses (var);
2285 if (!access || !build_access_trees (access))
2286 disqualify_candidate (var,
2287 "No or inhibitingly overlapping accesses.");
2290 propagate_all_subaccesses ();
2292 bitmap_copy (tmp, candidate_bitmap);
2293 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2295 tree var = referenced_var (i);
2296 struct access *access = get_first_repr_for_decl (var);
2298 if (analyze_access_trees (access))
2301 if (dump_file && (dump_flags & TDF_DETAILS))
2303 fprintf (dump_file, "\nAccess trees for ");
2304 print_generic_expr (dump_file, var, 0);
2305 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2306 dump_access_tree (dump_file, access);
2307 fprintf (dump_file, "\n");
2311 disqualify_candidate (var, "No scalar replacements to be created.");
2318 statistics_counter_event (cfun, "Scalarized aggregates", res);
2325 /* Generate statements copying scalar replacements of accesses within a subtree
2326 into or out of AGG. ACCESS, all its children, siblings and their children
2327 are to be processed. AGG is an aggregate type expression (can be a
2328 declaration but does not have to be, it can for example also be a mem_ref or
2329 a series of handled components). TOP_OFFSET is the offset of the processed
2330 subtree which has to be subtracted from offsets of individual accesses to
2331 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
2332 replacements in the interval <start_offset, start_offset + chunk_size>,
2333 otherwise copy all. GSI is a statement iterator used to place the new
2334 statements. WRITE should be true when the statements should write from AGG
2335 to the replacement and false if vice versa. if INSERT_AFTER is true, new
2336 statements will be added after the current statement in GSI, they will be
2337 added before the statement otherwise. */
2340 generate_subtree_copies (struct access *access, tree agg,
2341 HOST_WIDE_INT top_offset,
2342 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2343 gimple_stmt_iterator *gsi, bool write,
2344 bool insert_after, location_t loc)
2348 if (chunk_size && access->offset >= start_offset + chunk_size)
2351 if (access->grp_to_be_replaced
2353 || access->offset + access->size > start_offset))
2355 tree expr, repl = get_access_replacement (access);
2358 expr = build_ref_for_model (loc, agg, access->offset - top_offset,
2359 access, gsi, insert_after);
2363 if (access->grp_partial_lhs)
2364 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2366 insert_after ? GSI_NEW_STMT
2368 stmt = gimple_build_assign (repl, expr);
2372 TREE_NO_WARNING (repl) = 1;
2373 if (access->grp_partial_lhs)
2374 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2376 insert_after ? GSI_NEW_STMT
2378 stmt = gimple_build_assign (expr, repl);
2380 gimple_set_location (stmt, loc);
2383 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2385 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2387 sra_stats.subtree_copies++;
2390 if (access->first_child)
2391 generate_subtree_copies (access->first_child, agg, top_offset,
2392 start_offset, chunk_size, gsi,
2393 write, insert_after, loc);
2395 access = access->next_sibling;
2400 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2401 the root of the subtree to be processed. GSI is the statement iterator used
2402 for inserting statements which are added after the current statement if
2403 INSERT_AFTER is true or before it otherwise. */
2406 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2407 bool insert_after, location_t loc)
2410 struct access *child;
2412 if (access->grp_to_be_replaced)
2416 stmt = gimple_build_assign (get_access_replacement (access),
2417 build_zero_cst (access->type));
2419 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2421 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2423 gimple_set_location (stmt, loc);
2426 for (child = access->first_child; child; child = child->next_sibling)
2427 init_subtree_with_zero (child, gsi, insert_after, loc);
2430 /* Search for an access representative for the given expression EXPR and
2431 return it or NULL if it cannot be found. */
2433 static struct access *
2434 get_access_for_expr (tree expr)
2436 HOST_WIDE_INT offset, size, max_size;
2439 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2440 a different size than the size of its argument and we need the latter
2442 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2443 expr = TREE_OPERAND (expr, 0);
2445 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2446 if (max_size == -1 || !DECL_P (base))
2449 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2452 return get_var_base_offset_size_access (base, offset, max_size);
2455 /* Replace the expression EXPR with a scalar replacement if there is one and
2456 generate other statements to do type conversion or subtree copying if
2457 necessary. GSI is used to place newly created statements, WRITE is true if
2458 the expression is being written to (it is on a LHS of a statement or output
2459 in an assembly statement). */
2462 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
2465 struct access *access;
2468 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2471 expr = &TREE_OPERAND (*expr, 0);
2476 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2477 expr = &TREE_OPERAND (*expr, 0);
2478 access = get_access_for_expr (*expr);
2481 type = TREE_TYPE (*expr);
2483 loc = gimple_location (gsi_stmt (*gsi));
2484 if (access->grp_to_be_replaced)
2486 tree repl = get_access_replacement (access);
2487 /* If we replace a non-register typed access simply use the original
2488 access expression to extract the scalar component afterwards.
2489 This happens if scalarizing a function return value or parameter
2490 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2491 gcc.c-torture/compile/20011217-1.c.
2493 We also want to use this when accessing a complex or vector which can
2494 be accessed as a different type too, potentially creating a need for
2495 type conversion (see PR42196) and when scalarized unions are involved
2496 in assembler statements (see PR42398). */
2497 if (!useless_type_conversion_p (type, access->type))
2501 ref = build_ref_for_model (loc, access->base, access->offset, access,
2508 if (access->grp_partial_lhs)
2509 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2510 false, GSI_NEW_STMT);
2511 stmt = gimple_build_assign (repl, ref);
2512 gimple_set_location (stmt, loc);
2513 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2519 if (access->grp_partial_lhs)
2520 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2521 true, GSI_SAME_STMT);
2522 stmt = gimple_build_assign (ref, repl);
2523 gimple_set_location (stmt, loc);
2524 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2532 if (access->first_child)
2534 HOST_WIDE_INT start_offset, chunk_size;
2536 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2537 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2539 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2540 start_offset = access->offset
2541 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2544 start_offset = chunk_size = 0;
2546 generate_subtree_copies (access->first_child, access->base, 0,
2547 start_offset, chunk_size, gsi, write, write,
2553 /* Where scalar replacements of the RHS have been written to when a replacement
2554 of a LHS of an assigments cannot be direclty loaded from a replacement of
2556 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2557 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2558 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2560 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2561 base aggregate if there are unscalarized data or directly to LHS of the
2562 statement that is pointed to by GSI otherwise. */
2564 static enum unscalarized_data_handling
2565 handle_unscalarized_data_in_subtree (struct access *top_racc,
2566 gimple_stmt_iterator *gsi)
2568 if (top_racc->grp_unscalarized_data)
2570 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2572 gimple_location (gsi_stmt (*gsi)));
2573 return SRA_UDH_RIGHT;
2577 tree lhs = gimple_assign_lhs (gsi_stmt (*gsi));
2578 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2579 0, 0, gsi, false, false,
2580 gimple_location (gsi_stmt (*gsi)));
2581 return SRA_UDH_LEFT;
2586 /* Try to generate statements to load all sub-replacements in an access subtree
2587 formed by children of LACC from scalar replacements in the TOP_RACC subtree.
2588 If that is not possible, refresh the TOP_RACC base aggregate and load the
2589 accesses from it. LEFT_OFFSET is the offset of the left whole subtree being
2590 copied. NEW_GSI is stmt iterator used for statement insertions after the
2591 original assignment, OLD_GSI is used to insert statements before the
2592 assignment. *REFRESHED keeps the information whether we have needed to
2593 refresh replacements of the LHS and from which side of the assignments this
2597 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2598 HOST_WIDE_INT left_offset,
2599 gimple_stmt_iterator *old_gsi,
2600 gimple_stmt_iterator *new_gsi,
2601 enum unscalarized_data_handling *refreshed)
2603 location_t loc = gimple_location (gsi_stmt (*old_gsi));
2604 for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
2606 if (lacc->grp_to_be_replaced)
2608 struct access *racc;
2609 HOST_WIDE_INT offset = lacc->offset - left_offset + top_racc->offset;
2613 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2614 if (racc && racc->grp_to_be_replaced)
2616 rhs = get_access_replacement (racc);
2617 if (!useless_type_conversion_p (lacc->type, racc->type))
2618 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2622 /* No suitable access on the right hand side, need to load from
2623 the aggregate. See if we have to update it first... */
2624 if (*refreshed == SRA_UDH_NONE)
2625 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2628 if (*refreshed == SRA_UDH_LEFT)
2629 rhs = build_ref_for_model (loc, lacc->base, lacc->offset, lacc,
2632 rhs = build_ref_for_model (loc, top_racc->base, offset, lacc,
2636 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2637 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2638 gimple_set_location (stmt, loc);
2640 sra_stats.subreplacements++;
2642 else if (*refreshed == SRA_UDH_NONE
2643 && lacc->grp_read && !lacc->grp_covered)
2644 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2647 if (lacc->first_child)
2648 load_assign_lhs_subreplacements (lacc, top_racc, left_offset,
2649 old_gsi, new_gsi, refreshed);
2653 /* Result code for SRA assignment modification. */
2654 enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
2655 SRA_AM_MODIFIED, /* stmt changed but not
2657 SRA_AM_REMOVED }; /* stmt eliminated */
2659 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2660 to the assignment and GSI is the statement iterator pointing at it. Returns
2661 the same values as sra_modify_assign. */
2663 static enum assignment_mod_result
2664 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2666 tree lhs = gimple_assign_lhs (*stmt);
2670 acc = get_access_for_expr (lhs);
2674 loc = gimple_location (*stmt);
2675 if (VEC_length (constructor_elt,
2676 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2678 /* I have never seen this code path trigger but if it can happen the
2679 following should handle it gracefully. */
2680 if (access_has_children_p (acc))
2681 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2683 return SRA_AM_MODIFIED;
2686 if (acc->grp_covered)
2688 init_subtree_with_zero (acc, gsi, false, loc);
2689 unlink_stmt_vdef (*stmt);
2690 gsi_remove (gsi, true);
2691 return SRA_AM_REMOVED;
2695 init_subtree_with_zero (acc, gsi, true, loc);
2696 return SRA_AM_MODIFIED;
2700 /* Create and return a new suitable default definition SSA_NAME for RACC which
2701 is an access describing an uninitialized part of an aggregate that is being
2705 get_repl_default_def_ssa_name (struct access *racc)
2709 decl = get_unrenamed_access_replacement (racc);
2711 repl = gimple_default_def (cfun, decl);
2714 repl = make_ssa_name (decl, gimple_build_nop ());
2715 set_default_def (decl, repl);
2721 /* Return true if REF has a COMPONENT_REF with a bit-field field declaration
2725 contains_bitfld_comp_ref_p (const_tree ref)
2727 while (handled_component_p (ref))
2729 if (TREE_CODE (ref) == COMPONENT_REF
2730 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
2732 ref = TREE_OPERAND (ref, 0);
2738 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
2739 bit-field field declaration somewhere in it. */
2742 contains_vce_or_bfcref_p (const_tree ref)
2744 while (handled_component_p (ref))
2746 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
2747 || (TREE_CODE (ref) == COMPONENT_REF
2748 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
2750 ref = TREE_OPERAND (ref, 0);
2756 /* Examine both sides of the assignment statement pointed to by STMT, replace
2757 them with a scalare replacement if there is one and generate copying of
2758 replacements if scalarized aggregates have been used in the assignment. GSI
2759 is used to hold generated statements for type conversions and subtree
2762 static enum assignment_mod_result
2763 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2765 struct access *lacc, *racc;
2767 bool modify_this_stmt = false;
2768 bool force_gimple_rhs = false;
2770 gimple_stmt_iterator orig_gsi = *gsi;
2772 if (!gimple_assign_single_p (*stmt))
2774 lhs = gimple_assign_lhs (*stmt);
2775 rhs = gimple_assign_rhs1 (*stmt);
2777 if (TREE_CODE (rhs) == CONSTRUCTOR)
2778 return sra_modify_constructor_assign (stmt, gsi);
2780 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2781 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2782 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2784 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2786 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2788 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2791 lacc = get_access_for_expr (lhs);
2792 racc = get_access_for_expr (rhs);
2796 loc = gimple_location (*stmt);
2797 if (lacc && lacc->grp_to_be_replaced)
2799 lhs = get_access_replacement (lacc);
2800 gimple_assign_set_lhs (*stmt, lhs);
2801 modify_this_stmt = true;
2802 if (lacc->grp_partial_lhs)
2803 force_gimple_rhs = true;
2807 if (racc && racc->grp_to_be_replaced)
2809 rhs = get_access_replacement (racc);
2810 modify_this_stmt = true;
2811 if (racc->grp_partial_lhs)
2812 force_gimple_rhs = true;
2816 if (modify_this_stmt)
2818 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2820 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2821 ??? This should move to fold_stmt which we simply should
2822 call after building a VIEW_CONVERT_EXPR here. */
2823 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2824 && !contains_bitfld_comp_ref_p (lhs)
2825 && !access_has_children_p (lacc))
2827 lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
2828 gimple_assign_set_lhs (*stmt, lhs);
2830 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2831 && !contains_vce_or_bfcref_p (rhs)
2832 && !access_has_children_p (racc))
2833 rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
2835 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2837 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
2839 if (is_gimple_reg_type (TREE_TYPE (lhs))
2840 && TREE_CODE (lhs) != SSA_NAME)
2841 force_gimple_rhs = true;
2846 /* From this point on, the function deals with assignments in between
2847 aggregates when at least one has scalar reductions of some of its
2848 components. There are three possible scenarios: Both the LHS and RHS have
2849 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2851 In the first case, we would like to load the LHS components from RHS
2852 components whenever possible. If that is not possible, we would like to
2853 read it directly from the RHS (after updating it by storing in it its own
2854 components). If there are some necessary unscalarized data in the LHS,
2855 those will be loaded by the original assignment too. If neither of these
2856 cases happen, the original statement can be removed. Most of this is done
2857 by load_assign_lhs_subreplacements.
2859 In the second case, we would like to store all RHS scalarized components
2860 directly into LHS and if they cover the aggregate completely, remove the
2861 statement too. In the third case, we want the LHS components to be loaded
2862 directly from the RHS (DSE will remove the original statement if it
2865 This is a bit complex but manageable when types match and when unions do
2866 not cause confusion in a way that we cannot really load a component of LHS
2867 from the RHS or vice versa (the access representing this level can have
2868 subaccesses that are accessible only through a different union field at a
2869 higher level - different from the one used in the examined expression).
2872 Therefore, I specially handle a fourth case, happening when there is a
2873 specific type cast or it is impossible to locate a scalarized subaccess on
2874 the other side of the expression. If that happens, I simply "refresh" the
2875 RHS by storing in it is scalarized components leave the original statement
2876 there to do the copying and then load the scalar replacements of the LHS.
2877 This is what the first branch does. */
2879 if (modify_this_stmt
2880 || gimple_has_volatile_ops (*stmt)
2881 || contains_vce_or_bfcref_p (rhs)
2882 || contains_vce_or_bfcref_p (lhs))
2884 if (access_has_children_p (racc))
2885 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2886 gsi, false, false, loc);
2887 if (access_has_children_p (lacc))
2888 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2889 gsi, true, true, loc);
2890 sra_stats.separate_lhs_rhs_handling++;
2894 if (access_has_children_p (lacc) && access_has_children_p (racc))
2896 gimple_stmt_iterator orig_gsi = *gsi;
2897 enum unscalarized_data_handling refreshed;
2899 if (lacc->grp_read && !lacc->grp_covered)
2900 refreshed = handle_unscalarized_data_in_subtree (racc, gsi);
2902 refreshed = SRA_UDH_NONE;
2904 load_assign_lhs_subreplacements (lacc, racc, lacc->offset,
2905 &orig_gsi, gsi, &refreshed);
2906 if (refreshed != SRA_UDH_RIGHT)
2909 unlink_stmt_vdef (*stmt);
2910 gsi_remove (&orig_gsi, true);
2911 sra_stats.deleted++;
2912 return SRA_AM_REMOVED;
2919 if (!racc->grp_to_be_replaced && !racc->grp_unscalarized_data)
2923 fprintf (dump_file, "Removing load: ");
2924 print_gimple_stmt (dump_file, *stmt, 0, 0);
2927 if (TREE_CODE (lhs) == SSA_NAME)
2929 rhs = get_repl_default_def_ssa_name (racc);
2930 if (!useless_type_conversion_p (TREE_TYPE (lhs),
2932 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
2933 TREE_TYPE (lhs), rhs);
2937 if (racc->first_child)
2938 generate_subtree_copies (racc->first_child, lhs,
2939 racc->offset, 0, 0, gsi,
2942 gcc_assert (*stmt == gsi_stmt (*gsi));
2943 unlink_stmt_vdef (*stmt);
2944 gsi_remove (gsi, true);
2945 sra_stats.deleted++;
2946 return SRA_AM_REMOVED;
2949 else if (racc->first_child)
2950 generate_subtree_copies (racc->first_child, lhs, racc->offset,
2951 0, 0, gsi, false, true, loc);
2953 if (access_has_children_p (lacc))
2954 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2955 0, 0, gsi, true, true, loc);
2959 /* This gimplification must be done after generate_subtree_copies, lest we
2960 insert the subtree copies in the middle of the gimplified sequence. */
2961 if (force_gimple_rhs)
2962 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
2963 true, GSI_SAME_STMT);
2964 if (gimple_assign_rhs1 (*stmt) != rhs)
2966 modify_this_stmt = true;
2967 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
2968 gcc_assert (*stmt == gsi_stmt (orig_gsi));
2971 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2974 /* Traverse the function body and all modifications as decided in
2975 analyze_all_variable_accesses. Return true iff the CFG has been
2979 sra_modify_function_body (void)
2981 bool cfg_changed = false;
2986 gimple_stmt_iterator gsi = gsi_start_bb (bb);
2987 while (!gsi_end_p (gsi))
2989 gimple stmt = gsi_stmt (gsi);
2990 enum assignment_mod_result assign_result;
2991 bool modified = false, deleted = false;
2995 switch (gimple_code (stmt))
2998 t = gimple_return_retval_ptr (stmt);
2999 if (*t != NULL_TREE)
3000 modified |= sra_modify_expr (t, &gsi, false);
3004 assign_result = sra_modify_assign (&stmt, &gsi);
3005 modified |= assign_result == SRA_AM_MODIFIED;
3006 deleted = assign_result == SRA_AM_REMOVED;
3010 /* Operands must be processed before the lhs. */
3011 for (i = 0; i < gimple_call_num_args (stmt); i++)
3013 t = gimple_call_arg_ptr (stmt, i);
3014 modified |= sra_modify_expr (t, &gsi, false);
3017 if (gimple_call_lhs (stmt))
3019 t = gimple_call_lhs_ptr (stmt);
3020 modified |= sra_modify_expr (t, &gsi, true);
3025 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
3027 t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
3028 modified |= sra_modify_expr (t, &gsi, false);
3030 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
3032 t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
3033 modified |= sra_modify_expr (t, &gsi, true);
3044 if (maybe_clean_eh_stmt (stmt)
3045 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
3056 /* Generate statements initializing scalar replacements of parts of function
3060 initialize_parameter_reductions (void)
3062 gimple_stmt_iterator gsi;
3063 gimple_seq seq = NULL;
3066 for (parm = DECL_ARGUMENTS (current_function_decl);
3068 parm = DECL_CHAIN (parm))
3070 VEC (access_p, heap) *access_vec;
3071 struct access *access;
3073 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3075 access_vec = get_base_access_vector (parm);
3081 seq = gimple_seq_alloc ();
3082 gsi = gsi_start (seq);
3085 for (access = VEC_index (access_p, access_vec, 0);
3087 access = access->next_grp)
3088 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3089 EXPR_LOCATION (parm));
3093 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
3096 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
3097 it reveals there are components of some aggregates to be scalarized, it runs
3098 the required transformations. */
3100 perform_intra_sra (void)
3105 if (!find_var_candidates ())
3108 if (!scan_function ())
3111 if (!analyze_all_variable_accesses ())
3114 if (sra_modify_function_body ())
3115 ret = TODO_update_ssa | TODO_cleanup_cfg;
3117 ret = TODO_update_ssa;
3118 initialize_parameter_reductions ();
3120 statistics_counter_event (cfun, "Scalar replacements created",
3121 sra_stats.replacements);
3122 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3123 statistics_counter_event (cfun, "Subtree copy stmts",
3124 sra_stats.subtree_copies);
3125 statistics_counter_event (cfun, "Subreplacement stmts",
3126 sra_stats.subreplacements);
3127 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3128 statistics_counter_event (cfun, "Separate LHS and RHS handling",
3129 sra_stats.separate_lhs_rhs_handling);
3132 sra_deinitialize ();
3136 /* Perform early intraprocedural SRA. */
3138 early_intra_sra (void)
3140 sra_mode = SRA_MODE_EARLY_INTRA;
3141 return perform_intra_sra ();
3144 /* Perform "late" intraprocedural SRA. */
3146 late_intra_sra (void)
3148 sra_mode = SRA_MODE_INTRA;
3149 return perform_intra_sra ();
3154 gate_intra_sra (void)
3156 return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3160 struct gimple_opt_pass pass_sra_early =
3165 gate_intra_sra, /* gate */
3166 early_intra_sra, /* execute */
3169 0, /* static_pass_number */
3170 TV_TREE_SRA, /* tv_id */
3171 PROP_cfg | PROP_ssa, /* properties_required */
3172 0, /* properties_provided */
3173 0, /* properties_destroyed */
3174 0, /* todo_flags_start */
3177 | TODO_verify_ssa /* todo_flags_finish */
3181 struct gimple_opt_pass pass_sra =
3186 gate_intra_sra, /* gate */
3187 late_intra_sra, /* execute */
3190 0, /* static_pass_number */
3191 TV_TREE_SRA, /* tv_id */
3192 PROP_cfg | PROP_ssa, /* properties_required */
3193 0, /* properties_provided */
3194 0, /* properties_destroyed */
3195 TODO_update_address_taken, /* todo_flags_start */
3198 | TODO_verify_ssa /* todo_flags_finish */
3203 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3207 is_unused_scalar_param (tree parm)
3210 return (is_gimple_reg (parm)
3211 && (!(name = gimple_default_def (cfun, parm))
3212 || has_zero_uses (name)));
3215 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3216 examine whether there are any direct or otherwise infeasible ones. If so,
3217 return true, otherwise return false. PARM must be a gimple register with a
3218 non-NULL default definition. */
3221 ptr_parm_has_direct_uses (tree parm)
3223 imm_use_iterator ui;
3225 tree name = gimple_default_def (cfun, parm);
3228 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3231 use_operand_p use_p;
3233 if (is_gimple_debug (stmt))
3236 /* Valid uses include dereferences on the lhs and the rhs. */
3237 if (gimple_has_lhs (stmt))
3239 tree lhs = gimple_get_lhs (stmt);
3240 while (handled_component_p (lhs))
3241 lhs = TREE_OPERAND (lhs, 0);
3242 if (TREE_CODE (lhs) == MEM_REF
3243 && TREE_OPERAND (lhs, 0) == name
3244 && integer_zerop (TREE_OPERAND (lhs, 1))
3245 && types_compatible_p (TREE_TYPE (lhs),
3246 TREE_TYPE (TREE_TYPE (name))))
3249 if (gimple_assign_single_p (stmt))
3251 tree rhs = gimple_assign_rhs1 (stmt);
3252 while (handled_component_p (rhs))
3253 rhs = TREE_OPERAND (rhs, 0);
3254 if (TREE_CODE (rhs) == MEM_REF
3255 && TREE_OPERAND (rhs, 0) == name
3256 && integer_zerop (TREE_OPERAND (rhs, 1))
3257 && types_compatible_p (TREE_TYPE (rhs),
3258 TREE_TYPE (TREE_TYPE (name))))
3261 else if (is_gimple_call (stmt))
3264 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3266 tree arg = gimple_call_arg (stmt, i);
3267 while (handled_component_p (arg))
3268 arg = TREE_OPERAND (arg, 0);
3269 if (TREE_CODE (arg) == MEM_REF
3270 && TREE_OPERAND (arg, 0) == name
3271 && integer_zerop (TREE_OPERAND (arg, 1))
3272 && types_compatible_p (TREE_TYPE (arg),
3273 TREE_TYPE (TREE_TYPE (name))))
3278 /* If the number of valid uses does not match the number of
3279 uses in this stmt there is an unhandled use. */
3280 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
3287 BREAK_FROM_IMM_USE_STMT (ui);
3293 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3294 them in candidate_bitmap. Note that these do not necessarily include
3295 parameter which are unused and thus can be removed. Return true iff any
3296 such candidate has been found. */
3299 find_param_candidates (void)
3306 for (parm = DECL_ARGUMENTS (current_function_decl);
3308 parm = DECL_CHAIN (parm))
3310 tree type = TREE_TYPE (parm);
3314 if (TREE_THIS_VOLATILE (parm)
3315 || TREE_ADDRESSABLE (parm)
3316 || (!is_gimple_reg_type (type) && is_va_list_type (type)))
3319 if (is_unused_scalar_param (parm))
3325 if (POINTER_TYPE_P (type))
3327 type = TREE_TYPE (type);
3329 if (TREE_CODE (type) == FUNCTION_TYPE
3330 || TYPE_VOLATILE (type)
3331 || (TREE_CODE (type) == ARRAY_TYPE
3332 && TYPE_NONALIASED_COMPONENT (type))
3333 || !is_gimple_reg (parm)
3334 || is_va_list_type (type)
3335 || ptr_parm_has_direct_uses (parm))
3338 else if (!AGGREGATE_TYPE_P (type))
3341 if (!COMPLETE_TYPE_P (type)
3342 || !host_integerp (TYPE_SIZE (type), 1)
3343 || tree_low_cst (TYPE_SIZE (type), 1) == 0
3344 || (AGGREGATE_TYPE_P (type)
3345 && type_internals_preclude_sra_p (type, &msg)))
3348 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3350 if (dump_file && (dump_flags & TDF_DETAILS))
3352 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3353 print_generic_expr (dump_file, parm, 0);
3354 fprintf (dump_file, "\n");
3358 func_param_count = count;
3362 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3366 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3369 struct access *repr = (struct access *) data;
3371 repr->grp_maybe_modified = 1;
3375 /* Analyze what representatives (in linked lists accessible from
3376 REPRESENTATIVES) can be modified by side effects of statements in the
3377 current function. */
3380 analyze_modified_params (VEC (access_p, heap) *representatives)
3384 for (i = 0; i < func_param_count; i++)
3386 struct access *repr;
3388 for (repr = VEC_index (access_p, representatives, i);
3390 repr = repr->next_grp)
3392 struct access *access;
3396 if (no_accesses_p (repr))
3398 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3399 || repr->grp_maybe_modified)
3402 ao_ref_init (&ar, repr->expr);
3403 visited = BITMAP_ALLOC (NULL);
3404 for (access = repr; access; access = access->next_sibling)
3406 /* All accesses are read ones, otherwise grp_maybe_modified would
3407 be trivially set. */
3408 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3409 mark_maybe_modified, repr, &visited);
3410 if (repr->grp_maybe_modified)
3413 BITMAP_FREE (visited);
3418 /* Propagate distances in bb_dereferences in the opposite direction than the
3419 control flow edges, in each step storing the maximum of the current value
3420 and the minimum of all successors. These steps are repeated until the table
3421 stabilizes. Note that BBs which might terminate the functions (according to
3422 final_bbs bitmap) never updated in this way. */
3425 propagate_dereference_distances (void)
3427 VEC (basic_block, heap) *queue;
3430 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3431 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3434 VEC_quick_push (basic_block, queue, bb);
3438 while (!VEC_empty (basic_block, queue))
3442 bool change = false;
3445 bb = VEC_pop (basic_block, queue);
3448 if (bitmap_bit_p (final_bbs, bb->index))
3451 for (i = 0; i < func_param_count; i++)
3453 int idx = bb->index * func_param_count + i;
3455 HOST_WIDE_INT inh = 0;
3457 FOR_EACH_EDGE (e, ei, bb->succs)
3459 int succ_idx = e->dest->index * func_param_count + i;
3461 if (e->src == EXIT_BLOCK_PTR)
3467 inh = bb_dereferences [succ_idx];
3469 else if (bb_dereferences [succ_idx] < inh)
3470 inh = bb_dereferences [succ_idx];
3473 if (!first && bb_dereferences[idx] < inh)
3475 bb_dereferences[idx] = inh;
3480 if (change && !bitmap_bit_p (final_bbs, bb->index))
3481 FOR_EACH_EDGE (e, ei, bb->preds)
3486 e->src->aux = e->src;
3487 VEC_quick_push (basic_block, queue, e->src);
3491 VEC_free (basic_block, heap, queue);
3494 /* Dump a dereferences TABLE with heading STR to file F. */
3497 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3501 fprintf (dump_file, str);
3502 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3504 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3505 if (bb != EXIT_BLOCK_PTR)
3508 for (i = 0; i < func_param_count; i++)
3510 int idx = bb->index * func_param_count + i;
3511 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3516 fprintf (dump_file, "\n");
3519 /* Determine what (parts of) parameters passed by reference that are not
3520 assigned to are not certainly dereferenced in this function and thus the
3521 dereferencing cannot be safely moved to the caller without potentially
3522 introducing a segfault. Mark such REPRESENTATIVES as
3523 grp_not_necessarilly_dereferenced.
3525 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3526 part is calculated rather than simple booleans are calculated for each
3527 pointer parameter to handle cases when only a fraction of the whole
3528 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3531 The maximum dereference distances for each pointer parameter and BB are
3532 already stored in bb_dereference. This routine simply propagates these
3533 values upwards by propagate_dereference_distances and then compares the
3534 distances of individual parameters in the ENTRY BB to the equivalent
3535 distances of each representative of a (fraction of a) parameter. */
3538 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3542 if (dump_file && (dump_flags & TDF_DETAILS))
3543 dump_dereferences_table (dump_file,
3544 "Dereference table before propagation:\n",
3547 propagate_dereference_distances ();
3549 if (dump_file && (dump_flags & TDF_DETAILS))
3550 dump_dereferences_table (dump_file,
3551 "Dereference table after propagation:\n",
3554 for (i = 0; i < func_param_count; i++)
3556 struct access *repr = VEC_index (access_p, representatives, i);
3557 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3559 if (!repr || no_accesses_p (repr))
3564 if ((repr->offset + repr->size) > bb_dereferences[idx])
3565 repr->grp_not_necessarilly_dereferenced = 1;
3566 repr = repr->next_grp;
3572 /* Return the representative access for the parameter declaration PARM if it is
3573 a scalar passed by reference which is not written to and the pointer value
3574 is not used directly. Thus, if it is legal to dereference it in the caller
3575 and we can rule out modifications through aliases, such parameter should be
3576 turned into one passed by value. Return NULL otherwise. */
3578 static struct access *
3579 unmodified_by_ref_scalar_representative (tree parm)
3581 int i, access_count;
3582 struct access *repr;
3583 VEC (access_p, heap) *access_vec;
3585 access_vec = get_base_access_vector (parm);
3586 gcc_assert (access_vec);
3587 repr = VEC_index (access_p, access_vec, 0);
3590 repr->group_representative = repr;
3592 access_count = VEC_length (access_p, access_vec);
3593 for (i = 1; i < access_count; i++)
3595 struct access *access = VEC_index (access_p, access_vec, i);
3598 access->group_representative = repr;
3599 access->next_sibling = repr->next_sibling;
3600 repr->next_sibling = access;
3604 repr->grp_scalar_ptr = 1;
3608 /* Return true iff this access precludes IPA-SRA of the parameter it is
3612 access_precludes_ipa_sra_p (struct access *access)
3614 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3615 is incompatible assign in a call statement (and possibly even in asm
3616 statements). This can be relaxed by using a new temporary but only for
3617 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3618 intraprocedural SRA we deal with this by keeping the old aggregate around,
3619 something we cannot do in IPA-SRA.) */
3621 && (is_gimple_call (access->stmt)
3622 || gimple_code (access->stmt) == GIMPLE_ASM))
3629 /* Sort collected accesses for parameter PARM, identify representatives for
3630 each accessed region and link them together. Return NULL if there are
3631 different but overlapping accesses, return the special ptr value meaning
3632 there are no accesses for this parameter if that is the case and return the
3633 first representative otherwise. Set *RO_GRP if there is a group of accesses
3634 with only read (i.e. no write) accesses. */
3636 static struct access *
3637 splice_param_accesses (tree parm, bool *ro_grp)
3639 int i, j, access_count, group_count;
3640 int agg_size, total_size = 0;
3641 struct access *access, *res, **prev_acc_ptr = &res;
3642 VEC (access_p, heap) *access_vec;
3644 access_vec = get_base_access_vector (parm);
3646 return &no_accesses_representant;
3647 access_count = VEC_length (access_p, access_vec);
3649 VEC_qsort (access_p, access_vec, compare_access_positions);
3654 while (i < access_count)
3658 access = VEC_index (access_p, access_vec, i);
3659 modification = access->write;
3660 if (access_precludes_ipa_sra_p (access))
3662 a1_alias_type = reference_alias_ptr_type (access->expr);
3664 /* Access is about to become group representative unless we find some
3665 nasty overlap which would preclude us from breaking this parameter
3669 while (j < access_count)
3671 struct access *ac2 = VEC_index (access_p, access_vec, j);
3672 if (ac2->offset != access->offset)
3674 /* All or nothing law for parameters. */
3675 if (access->offset + access->size > ac2->offset)
3680 else if (ac2->size != access->size)
3683 if (access_precludes_ipa_sra_p (ac2)
3684 || (ac2->type != access->type
3685 && (TREE_ADDRESSABLE (ac2->type)
3686 || TREE_ADDRESSABLE (access->type)))
3687 || (reference_alias_ptr_type (ac2->expr) != a1_alias_type))
3690 modification |= ac2->write;
3691 ac2->group_representative = access;
3692 ac2->next_sibling = access->next_sibling;
3693 access->next_sibling = ac2;
3698 access->grp_maybe_modified = modification;
3701 *prev_acc_ptr = access;
3702 prev_acc_ptr = &access->next_grp;
3703 total_size += access->size;
3707 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3708 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3710 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3711 if (total_size >= agg_size)
3714 gcc_assert (group_count > 0);
3718 /* Decide whether parameters with representative accesses given by REPR should
3719 be reduced into components. */
3722 decide_one_param_reduction (struct access *repr)
3724 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3729 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3730 gcc_assert (cur_parm_size > 0);
3732 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3735 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3740 agg_size = cur_parm_size;
3746 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3747 print_generic_expr (dump_file, parm, 0);
3748 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3749 for (acc = repr; acc; acc = acc->next_grp)
3750 dump_access (dump_file, acc, true);
3754 new_param_count = 0;
3756 for (; repr; repr = repr->next_grp)
3758 gcc_assert (parm == repr->base);
3760 /* Taking the address of a non-addressable field is verboten. */
3761 if (by_ref && repr->non_addressable)
3764 if (!by_ref || (!repr->grp_maybe_modified
3765 && !repr->grp_not_necessarilly_dereferenced))
3766 total_size += repr->size;
3768 total_size += cur_parm_size;
3773 gcc_assert (new_param_count > 0);
3775 if (optimize_function_for_size_p (cfun))
3776 parm_size_limit = cur_parm_size;
3778 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3781 if (total_size < agg_size
3782 && total_size <= parm_size_limit)
3785 fprintf (dump_file, " ....will be split into %i components\n",
3787 return new_param_count;
3793 /* The order of the following enums is important, we need to do extra work for
3794 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3795 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3796 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3798 /* Identify representatives of all accesses to all candidate parameters for
3799 IPA-SRA. Return result based on what representatives have been found. */
3801 static enum ipa_splicing_result
3802 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3804 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3806 struct access *repr;
3808 *representatives = VEC_alloc (access_p, heap, func_param_count);
3810 for (parm = DECL_ARGUMENTS (current_function_decl);
3812 parm = DECL_CHAIN (parm))
3814 if (is_unused_scalar_param (parm))
3816 VEC_quick_push (access_p, *representatives,
3817 &no_accesses_representant);
3818 if (result == NO_GOOD_ACCESS)
3819 result = UNUSED_PARAMS;
3821 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3822 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3823 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3825 repr = unmodified_by_ref_scalar_representative (parm);
3826 VEC_quick_push (access_p, *representatives, repr);
3828 result = UNMODIF_BY_REF_ACCESSES;
3830 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3832 bool ro_grp = false;
3833 repr = splice_param_accesses (parm, &ro_grp);
3834 VEC_quick_push (access_p, *representatives, repr);
3836 if (repr && !no_accesses_p (repr))
3838 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3841 result = UNMODIF_BY_REF_ACCESSES;
3842 else if (result < MODIF_BY_REF_ACCESSES)
3843 result = MODIF_BY_REF_ACCESSES;
3845 else if (result < BY_VAL_ACCESSES)
3846 result = BY_VAL_ACCESSES;
3848 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3849 result = UNUSED_PARAMS;
3852 VEC_quick_push (access_p, *representatives, NULL);
3855 if (result == NO_GOOD_ACCESS)
3857 VEC_free (access_p, heap, *representatives);
3858 *representatives = NULL;
3859 return NO_GOOD_ACCESS;
3865 /* Return the index of BASE in PARMS. Abort if it is not found. */
3868 get_param_index (tree base, VEC(tree, heap) *parms)
3872 len = VEC_length (tree, parms);
3873 for (i = 0; i < len; i++)
3874 if (VEC_index (tree, parms, i) == base)
3879 /* Convert the decisions made at the representative level into compact
3880 parameter adjustments. REPRESENTATIVES are pointers to first
3881 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3882 final number of adjustments. */
3884 static ipa_parm_adjustment_vec
3885 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3886 int adjustments_count)
3888 VEC (tree, heap) *parms;
3889 ipa_parm_adjustment_vec adjustments;
3893 gcc_assert (adjustments_count > 0);
3894 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3895 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3896 parm = DECL_ARGUMENTS (current_function_decl);
3897 for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm))
3899 struct access *repr = VEC_index (access_p, representatives, i);
3901 if (!repr || no_accesses_p (repr))
3903 struct ipa_parm_adjustment *adj;
3905 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3906 memset (adj, 0, sizeof (*adj));
3907 adj->base_index = get_param_index (parm, parms);
3910 adj->copy_param = 1;
3912 adj->remove_param = 1;
3916 struct ipa_parm_adjustment *adj;
3917 int index = get_param_index (parm, parms);
3919 for (; repr; repr = repr->next_grp)
3921 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3922 memset (adj, 0, sizeof (*adj));
3923 gcc_assert (repr->base == parm);
3924 adj->base_index = index;
3925 adj->base = repr->base;
3926 adj->type = repr->type;
3927 adj->alias_ptr_type = reference_alias_ptr_type (repr->expr);
3928 adj->offset = repr->offset;
3929 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3930 && (repr->grp_maybe_modified
3931 || repr->grp_not_necessarilly_dereferenced));
3936 VEC_free (tree, heap, parms);
3940 /* Analyze the collected accesses and produce a plan what to do with the
3941 parameters in the form of adjustments, NULL meaning nothing. */
3943 static ipa_parm_adjustment_vec
3944 analyze_all_param_acesses (void)
3946 enum ipa_splicing_result repr_state;
3947 bool proceed = false;
3948 int i, adjustments_count = 0;
3949 VEC (access_p, heap) *representatives;
3950 ipa_parm_adjustment_vec adjustments;
3952 repr_state = splice_all_param_accesses (&representatives);
3953 if (repr_state == NO_GOOD_ACCESS)
3956 /* If there are any parameters passed by reference which are not modified
3957 directly, we need to check whether they can be modified indirectly. */
3958 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3960 analyze_caller_dereference_legality (representatives);
3961 analyze_modified_params (representatives);
3964 for (i = 0; i < func_param_count; i++)
3966 struct access *repr = VEC_index (access_p, representatives, i);
3968 if (repr && !no_accesses_p (repr))
3970 if (repr->grp_scalar_ptr)
3972 adjustments_count++;
3973 if (repr->grp_not_necessarilly_dereferenced
3974 || repr->grp_maybe_modified)
3975 VEC_replace (access_p, representatives, i, NULL);
3979 sra_stats.scalar_by_ref_to_by_val++;
3984 int new_components = decide_one_param_reduction (repr);
3986 if (new_components == 0)
3988 VEC_replace (access_p, representatives, i, NULL);
3989 adjustments_count++;
3993 adjustments_count += new_components;
3994 sra_stats.aggregate_params_reduced++;
3995 sra_stats.param_reductions_created += new_components;
4002 if (no_accesses_p (repr))
4005 sra_stats.deleted_unused_parameters++;
4007 adjustments_count++;
4011 if (!proceed && dump_file)
4012 fprintf (dump_file, "NOT proceeding to change params.\n");
4015 adjustments = turn_representatives_into_adjustments (representatives,
4020 VEC_free (access_p, heap, representatives);
4024 /* If a parameter replacement identified by ADJ does not yet exist in the form
4025 of declaration, create it and record it, otherwise return the previously
4029 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
4032 if (!adj->new_ssa_base)
4034 char *pretty_name = make_fancy_name (adj->base);
4036 repl = create_tmp_reg (TREE_TYPE (adj->base), "ISR");
4037 DECL_NAME (repl) = get_identifier (pretty_name);
4038 obstack_free (&name_obstack, pretty_name);
4041 add_referenced_var (repl);
4042 adj->new_ssa_base = repl;
4045 repl = adj->new_ssa_base;
4049 /* Find the first adjustment for a particular parameter BASE in a vector of
4050 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
4053 static struct ipa_parm_adjustment *
4054 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
4058 len = VEC_length (ipa_parm_adjustment_t, adjustments);
4059 for (i = 0; i < len; i++)
4061 struct ipa_parm_adjustment *adj;
4063 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
4064 if (!adj->copy_param && adj->base == base)
4071 /* If the statement STMT defines an SSA_NAME of a parameter which is to be
4072 removed because its value is not used, replace the SSA_NAME with a one
4073 relating to a created VAR_DECL together all of its uses and return true.
4074 ADJUSTMENTS is a pointer to an adjustments vector. */
4077 replace_removed_params_ssa_names (gimple stmt,
4078 ipa_parm_adjustment_vec adjustments)
4080 struct ipa_parm_adjustment *adj;
4081 tree lhs, decl, repl, name;
4083 if (gimple_code (stmt) == GIMPLE_PHI)
4084 lhs = gimple_phi_result (stmt);
4085 else if (is_gimple_assign (stmt))
4086 lhs = gimple_assign_lhs (stmt);
4087 else if (is_gimple_call (stmt))
4088 lhs = gimple_call_lhs (stmt);
4092 if (TREE_CODE (lhs) != SSA_NAME)
4094 decl = SSA_NAME_VAR (lhs);
4095 if (TREE_CODE (decl) != PARM_DECL)
4098 adj = get_adjustment_for_base (adjustments, decl);
4102 repl = get_replaced_param_substitute (adj);
4103 name = make_ssa_name (repl, stmt);
4107 fprintf (dump_file, "replacing an SSA name of a removed param ");
4108 print_generic_expr (dump_file, lhs, 0);
4109 fprintf (dump_file, " with ");
4110 print_generic_expr (dump_file, name, 0);
4111 fprintf (dump_file, "\n");
4114 if (is_gimple_assign (stmt))
4115 gimple_assign_set_lhs (stmt, name);
4116 else if (is_gimple_call (stmt))
4117 gimple_call_set_lhs (stmt, name);
4119 gimple_phi_set_result (stmt, name);
4121 replace_uses_by (lhs, name);
4122 release_ssa_name (lhs);
4126 /* If the expression *EXPR should be replaced by a reduction of a parameter, do
4127 so. ADJUSTMENTS is a pointer to a vector of adjustments. CONVERT
4128 specifies whether the function should care about type incompatibility the
4129 current and new expressions. If it is false, the function will leave
4130 incompatibility issues to the caller. Return true iff the expression
4134 sra_ipa_modify_expr (tree *expr, bool convert,
4135 ipa_parm_adjustment_vec adjustments)
4138 struct ipa_parm_adjustment *adj, *cand = NULL;
4139 HOST_WIDE_INT offset, size, max_size;
4142 len = VEC_length (ipa_parm_adjustment_t, adjustments);
4144 if (TREE_CODE (*expr) == BIT_FIELD_REF
4145 || TREE_CODE (*expr) == IMAGPART_EXPR
4146 || TREE_CODE (*expr) == REALPART_EXPR)
4148 expr = &TREE_OPERAND (*expr, 0);
4152 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
4153 if (!base || size == -1 || max_size == -1)
4156 if (TREE_CODE (base) == MEM_REF)
4158 offset += mem_ref_offset (base).low * BITS_PER_UNIT;
4159 base = TREE_OPERAND (base, 0);
4162 base = get_ssa_base_param (base);
4163 if (!base || TREE_CODE (base) != PARM_DECL)
4166 for (i = 0; i < len; i++)
4168 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
4170 if (adj->base == base &&
4171 (adj->offset == offset || adj->remove_param))
4177 if (!cand || cand->copy_param || cand->remove_param)
4181 src = build_simple_mem_ref (cand->reduction);
4183 src = cand->reduction;
4185 if (dump_file && (dump_flags & TDF_DETAILS))
4187 fprintf (dump_file, "About to replace expr ");
4188 print_generic_expr (dump_file, *expr, 0);
4189 fprintf (dump_file, " with ");
4190 print_generic_expr (dump_file, src, 0);
4191 fprintf (dump_file, "\n");
4194 if (convert && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
4196 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
4204 /* If the statement pointed to by STMT_PTR contains any expressions that need
4205 to replaced with a different one as noted by ADJUSTMENTS, do so. Handle any
4206 potential type incompatibilities (GSI is used to accommodate conversion
4207 statements and must point to the statement). Return true iff the statement
4211 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi,
4212 ipa_parm_adjustment_vec adjustments)
4214 gimple stmt = *stmt_ptr;
4215 tree *lhs_p, *rhs_p;
4218 if (!gimple_assign_single_p (stmt))
4221 rhs_p = gimple_assign_rhs1_ptr (stmt);
4222 lhs_p = gimple_assign_lhs_ptr (stmt);
4224 any = sra_ipa_modify_expr (rhs_p, false, adjustments);
4225 any |= sra_ipa_modify_expr (lhs_p, false, adjustments);
4228 tree new_rhs = NULL_TREE;
4230 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
4232 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
4234 /* V_C_Es of constructors can cause trouble (PR 42714). */
4235 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
4236 *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
4238 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
4241 new_rhs = fold_build1_loc (gimple_location (stmt),
4242 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
4245 else if (REFERENCE_CLASS_P (*rhs_p)
4246 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
4247 && !is_gimple_reg (*lhs_p))
4248 /* This can happen when an assignment in between two single field
4249 structures is turned into an assignment in between two pointers to
4250 scalars (PR 42237). */
4255 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
4256 true, GSI_SAME_STMT);
4258 gimple_assign_set_rhs_from_tree (gsi, tmp);
4267 /* Traverse the function body and all modifications as described in
4268 ADJUSTMENTS. Return true iff the CFG has been changed. */
4271 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments)
4273 bool cfg_changed = false;
4278 gimple_stmt_iterator gsi;
4280 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4281 replace_removed_params_ssa_names (gsi_stmt (gsi), adjustments);
4283 gsi = gsi_start_bb (bb);
4284 while (!gsi_end_p (gsi))
4286 gimple stmt = gsi_stmt (gsi);
4287 bool modified = false;
4291 switch (gimple_code (stmt))
4294 t = gimple_return_retval_ptr (stmt);
4295 if (*t != NULL_TREE)
4296 modified |= sra_ipa_modify_expr (t, true, adjustments);
4300 modified |= sra_ipa_modify_assign (&stmt, &gsi, adjustments);
4301 modified |= replace_removed_params_ssa_names (stmt, adjustments);
4305 /* Operands must be processed before the lhs. */
4306 for (i = 0; i < gimple_call_num_args (stmt); i++)
4308 t = gimple_call_arg_ptr (stmt, i);
4309 modified |= sra_ipa_modify_expr (t, true, adjustments);
4312 if (gimple_call_lhs (stmt))
4314 t = gimple_call_lhs_ptr (stmt);
4315 modified |= sra_ipa_modify_expr (t, false, adjustments);
4316 modified |= replace_removed_params_ssa_names (stmt,
4322 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
4324 t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
4325 modified |= sra_ipa_modify_expr (t, true, adjustments);
4327 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
4329 t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
4330 modified |= sra_ipa_modify_expr (t, false, adjustments);
4341 if (maybe_clean_eh_stmt (stmt)
4342 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
4352 /* Call gimple_debug_bind_reset_value on all debug statements describing
4353 gimple register parameters that are being removed or replaced. */
4356 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
4359 gimple_stmt_iterator *gsip = NULL, gsi;
4361 if (MAY_HAVE_DEBUG_STMTS && single_succ_p (ENTRY_BLOCK_PTR))
4363 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
4366 len = VEC_length (ipa_parm_adjustment_t, adjustments);
4367 for (i = 0; i < len; i++)
4369 struct ipa_parm_adjustment *adj;
4370 imm_use_iterator ui;
4371 gimple stmt, def_temp;
4372 tree name, vexpr, copy = NULL_TREE;
4373 use_operand_p use_p;
4375 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
4376 if (adj->copy_param || !is_gimple_reg (adj->base))
4378 name = gimple_default_def (cfun, adj->base);
4381 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
4383 /* All other users must have been removed by
4384 ipa_sra_modify_function_body. */
4385 gcc_assert (is_gimple_debug (stmt));
4386 if (vexpr == NULL && gsip != NULL)
4388 gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
4389 vexpr = make_node (DEBUG_EXPR_DECL);
4390 def_temp = gimple_build_debug_source_bind (vexpr, adj->base,
4392 DECL_ARTIFICIAL (vexpr) = 1;
4393 TREE_TYPE (vexpr) = TREE_TYPE (name);
4394 DECL_MODE (vexpr) = DECL_MODE (adj->base);
4395 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
4399 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
4400 SET_USE (use_p, vexpr);
4403 gimple_debug_bind_reset_value (stmt);
4406 /* Create a VAR_DECL for debug info purposes. */
4407 if (!DECL_IGNORED_P (adj->base))
4409 copy = build_decl (DECL_SOURCE_LOCATION (current_function_decl),
4410 VAR_DECL, DECL_NAME (adj->base),
4411 TREE_TYPE (adj->base));
4412 if (DECL_PT_UID_SET_P (adj->base))
4413 SET_DECL_PT_UID (copy, DECL_PT_UID (adj->base));
4414 TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (adj->base);
4415 TREE_READONLY (copy) = TREE_READONLY (adj->base);
4416 TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (adj->base);
4417 DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (adj->base);
4418 DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (adj->base);
4419 DECL_IGNORED_P (copy) = DECL_IGNORED_P (adj->base);
4420 DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (adj->base);
4421 DECL_SEEN_IN_BIND_EXPR_P (copy) = 1;
4422 SET_DECL_RTL (copy, 0);
4423 TREE_USED (copy) = 1;
4424 DECL_CONTEXT (copy) = current_function_decl;
4425 add_referenced_var (copy);
4426 add_local_decl (cfun, copy);
4428 BLOCK_VARS (DECL_INITIAL (current_function_decl));
4429 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = copy;
4431 if (gsip != NULL && copy && target_for_debug_bind (adj->base))
4433 gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
4435 def_temp = gimple_build_debug_bind (copy, vexpr, NULL);
4437 def_temp = gimple_build_debug_source_bind (copy, adj->base,
4439 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
4444 /* Return false iff all callers have at least as many actual arguments as there
4445 are formal parameters in the current function. */
4448 not_all_callers_have_enough_arguments_p (struct cgraph_node *node,
4449 void *data ATTRIBUTE_UNUSED)
4451 struct cgraph_edge *cs;
4452 for (cs = node->callers; cs; cs = cs->next_caller)
4453 if (!callsite_has_enough_arguments_p (cs->call_stmt))
4459 /* Convert all callers of NODE. */
4462 convert_callers_for_node (struct cgraph_node *node,
4465 ipa_parm_adjustment_vec adjustments = (ipa_parm_adjustment_vec)data;
4466 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
4467 struct cgraph_edge *cs;
4469 for (cs = node->callers; cs; cs = cs->next_caller)
4471 current_function_decl = cs->caller->decl;
4472 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
4475 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
4476 cs->caller->uid, cs->callee->uid,
4477 cgraph_node_name (cs->caller),
4478 cgraph_node_name (cs->callee));
4480 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
4485 for (cs = node->callers; cs; cs = cs->next_caller)
4486 if (bitmap_set_bit (recomputed_callers, cs->caller->uid)
4487 && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (cs->caller->decl)))
4488 compute_inline_parameters (cs->caller, true);
4489 BITMAP_FREE (recomputed_callers);
4494 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
4497 convert_callers (struct cgraph_node *node, tree old_decl,
4498 ipa_parm_adjustment_vec adjustments)
4500 tree old_cur_fndecl = current_function_decl;
4501 basic_block this_block;
4503 cgraph_for_node_and_aliases (node, convert_callers_for_node,
4504 adjustments, false);
4506 current_function_decl = old_cur_fndecl;
4508 if (!encountered_recursive_call)
4511 FOR_EACH_BB (this_block)
4513 gimple_stmt_iterator gsi;
4515 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4517 gimple stmt = gsi_stmt (gsi);
4519 if (gimple_code (stmt) != GIMPLE_CALL)
4521 call_fndecl = gimple_call_fndecl (stmt);
4522 if (call_fndecl == old_decl)
4525 fprintf (dump_file, "Adjusting recursive call");
4526 gimple_call_set_fndecl (stmt, node->decl);
4527 ipa_modify_call_arguments (NULL, stmt, adjustments);
4535 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4536 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */
4539 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4541 struct cgraph_node *new_node;
4543 VEC (cgraph_edge_p, heap) * redirect_callers = collect_callers_of_node (node);
4545 rebuild_cgraph_edges ();
4547 current_function_decl = NULL_TREE;
4549 new_node = cgraph_function_versioning (node, redirect_callers, NULL, NULL,
4550 NULL, NULL, "isra");
4551 current_function_decl = new_node->decl;
4552 push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
4554 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
4555 cfg_changed = ipa_sra_modify_function_body (adjustments);
4556 sra_ipa_reset_debug_stmts (adjustments);
4557 convert_callers (new_node, node->decl, adjustments);
4558 cgraph_make_node_local (new_node);
4562 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4563 attributes, return true otherwise. NODE is the cgraph node of the current
4567 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4569 if (!cgraph_node_can_be_local_p (node))
4572 fprintf (dump_file, "Function not local to this compilation unit.\n");
4576 if (!node->local.can_change_signature)
4579 fprintf (dump_file, "Function can not change signature.\n");
4583 if (!tree_versionable_function_p (node->decl))
4586 fprintf (dump_file, "Function is not versionable.\n");
4590 if (DECL_VIRTUAL_P (current_function_decl))
4593 fprintf (dump_file, "Function is a virtual method.\n");
4597 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
4598 && inline_summary(node)->size >= MAX_INLINE_INSNS_AUTO)
4601 fprintf (dump_file, "Function too big to be made truly local.\n");
4609 "Function has no callers in this compilation unit.\n");
4616 fprintf (dump_file, "Function uses stdarg. \n");
4620 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
4626 /* Perform early interprocedural SRA. */
4629 ipa_early_sra (void)
4631 struct cgraph_node *node = cgraph_get_node (current_function_decl);
4632 ipa_parm_adjustment_vec adjustments;
4635 if (!ipa_sra_preliminary_function_checks (node))
4639 sra_mode = SRA_MODE_EARLY_IPA;
4641 if (!find_param_candidates ())
4644 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
4648 if (cgraph_for_node_and_aliases (node, not_all_callers_have_enough_arguments_p,
4652 fprintf (dump_file, "There are callers with insufficient number of "
4657 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
4659 * last_basic_block_for_function (cfun));
4660 final_bbs = BITMAP_ALLOC (NULL);
4663 if (encountered_apply_args)
4666 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4670 if (encountered_unchangable_recursive_call)
4673 fprintf (dump_file, "Function calls itself with insufficient "
4674 "number of arguments.\n");
4678 adjustments = analyze_all_param_acesses ();
4682 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4684 if (modify_function (node, adjustments))
4685 ret = TODO_update_ssa | TODO_cleanup_cfg;
4687 ret = TODO_update_ssa;
4688 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4690 statistics_counter_event (cfun, "Unused parameters deleted",
4691 sra_stats.deleted_unused_parameters);
4692 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4693 sra_stats.scalar_by_ref_to_by_val);
4694 statistics_counter_event (cfun, "Aggregate parameters broken up",
4695 sra_stats.aggregate_params_reduced);
4696 statistics_counter_event (cfun, "Aggregate parameter components created",
4697 sra_stats.param_reductions_created);
4700 BITMAP_FREE (final_bbs);
4701 free (bb_dereferences);
4703 sra_deinitialize ();
4707 /* Return if early ipa sra shall be performed. */
4709 ipa_early_sra_gate (void)
4711 return flag_ipa_sra && dbg_cnt (eipa_sra);
4714 struct gimple_opt_pass pass_early_ipa_sra =
4718 "eipa_sra", /* name */
4719 ipa_early_sra_gate, /* gate */
4720 ipa_early_sra, /* execute */
4723 0, /* static_pass_number */
4724 TV_IPA_SRA, /* tv_id */
4725 0, /* properties_required */
4726 0, /* properties_provided */
4727 0, /* properties_destroyed */
4728 0, /* todo_flags_start */
4729 TODO_dump_cgraph /* todo_flags_finish */