1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
82 #include "tree-flow.h"
84 #include "tree-pretty-print.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 #include "tree-inline.h"
93 #include "gimple-pretty-print.h"
95 /* Enumeration of all aggregate reductions we can do. */
96 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
97 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
98 SRA_MODE_INTRA }; /* late intraprocedural SRA */
100 /* Global variable describing which aggregate reduction we are performing at
102 static enum sra_mode sra_mode;
106 /* ACCESS represents each access to an aggregate variable (as a whole or a
107 part). It can also represent a group of accesses that refer to exactly the
108 same fragment of an aggregate (i.e. those that have exactly the same offset
109 and size). Such representatives for a single aggregate, once determined,
110 are linked in a linked list and have the group fields set.
112 Moreover, when doing intraprocedural SRA, a tree is built from those
113 representatives (by the means of first_child and next_sibling pointers), in
114 which all items in a subtree are "within" the root, i.e. their offset is
115 greater or equal to offset of the root and offset+size is smaller or equal
116 to offset+size of the root. Children of an access are sorted by offset.
118 Note that accesses to parts of vector and complex number types always
119 represented by an access to the whole complex number or a vector. It is a
120 duty of the modifying functions to replace them appropriately. */
124 /* Values returned by `get_ref_base_and_extent' for each component reference
125 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
126 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
127 HOST_WIDE_INT offset;
131 /* Expression. It is context dependent so do not use it to create new
132 expressions to access the original aggregate. See PR 42154 for a
138 /* The statement this access belongs to. */
141 /* Next group representative for this aggregate. */
142 struct access *next_grp;
144 /* Pointer to the group representative. Pointer to itself if the struct is
145 the representative. */
146 struct access *group_representative;
148 /* If this access has any children (in terms of the definition above), this
149 points to the first one. */
150 struct access *first_child;
152 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
153 described above. In IPA-SRA this is a pointer to the next access
154 belonging to the same group (having the same representative). */
155 struct access *next_sibling;
157 /* Pointers to the first and last element in the linked list of assign
159 struct assign_link *first_link, *last_link;
161 /* Pointer to the next access in the work queue. */
162 struct access *next_queued;
164 /* Replacement variable for this access "region." Never to be accessed
165 directly, always only by the means of get_access_replacement() and only
166 when grp_to_be_replaced flag is set. */
167 tree replacement_decl;
169 /* Is this particular access write access? */
172 /* Is this access an artificial one created to scalarize some record
174 unsigned total_scalarization : 1;
176 /* Is this access an access to a non-addressable field? */
177 unsigned non_addressable : 1;
179 /* Is this access currently in the work queue? */
180 unsigned grp_queued : 1;
182 /* Does this group contain a write access? This flag is propagated down the
184 unsigned grp_write : 1;
186 /* Does this group contain a read access? This flag is propagated down the
188 unsigned grp_read : 1;
190 /* Does this group contain a read access that comes from an assignment
191 statement? This flag is propagated down the access tree. */
192 unsigned grp_assignment_read : 1;
194 /* Does this group contain a write access that comes from an assignment
195 statement? This flag is propagated down the access tree. */
196 unsigned grp_assignment_write : 1;
198 /* Other passes of the analysis use this bit to make function
199 analyze_access_subtree create scalar replacements for this group if
201 unsigned grp_hint : 1;
203 /* Is the subtree rooted in this access fully covered by scalar
205 unsigned grp_covered : 1;
207 /* If set to true, this access and all below it in an access tree must not be
209 unsigned grp_unscalarizable_region : 1;
211 /* Whether data have been written to parts of the aggregate covered by this
212 access which is not to be scalarized. This flag is propagated up in the
214 unsigned grp_unscalarized_data : 1;
216 /* Does this access and/or group contain a write access through a
218 unsigned grp_partial_lhs : 1;
220 /* Set when a scalar replacement should be created for this variable. We do
221 the decision and creation at different places because create_tmp_var
222 cannot be called from within FOR_EACH_REFERENCED_VAR. */
223 unsigned grp_to_be_replaced : 1;
225 /* Should TREE_NO_WARNING of a replacement be set? */
226 unsigned grp_no_warning : 1;
228 /* Is it possible that the group refers to data which might be (directly or
229 otherwise) modified? */
230 unsigned grp_maybe_modified : 1;
232 /* Set when this is a representative of a pointer to scalar (i.e. by
233 reference) parameter which we consider for turning into a plain scalar
234 (i.e. a by value parameter). */
235 unsigned grp_scalar_ptr : 1;
237 /* Set when we discover that this pointer is not safe to dereference in the
239 unsigned grp_not_necessarilly_dereferenced : 1;
242 typedef struct access *access_p;
244 DEF_VEC_P (access_p);
245 DEF_VEC_ALLOC_P (access_p, heap);
247 /* Alloc pool for allocating access structures. */
248 static alloc_pool access_pool;
250 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
251 are used to propagate subaccesses from rhs to lhs as long as they don't
252 conflict with what is already there. */
255 struct access *lacc, *racc;
256 struct assign_link *next;
259 /* Alloc pool for allocating assign link structures. */
260 static alloc_pool link_pool;
262 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
263 static struct pointer_map_t *base_access_vec;
265 /* Bitmap of candidates. */
266 static bitmap candidate_bitmap;
268 /* Bitmap of candidates which we should try to entirely scalarize away and
269 those which cannot be (because they are and need be used as a whole). */
270 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
272 /* Obstack for creation of fancy names. */
273 static struct obstack name_obstack;
275 /* Head of a linked list of accesses that need to have its subaccesses
276 propagated to their assignment counterparts. */
277 static struct access *work_queue_head;
279 /* Number of parameters of the analyzed function when doing early ipa SRA. */
280 static int func_param_count;
282 /* scan_function sets the following to true if it encounters a call to
283 __builtin_apply_args. */
284 static bool encountered_apply_args;
286 /* Set by scan_function when it finds a recursive call. */
287 static bool encountered_recursive_call;
289 /* Set by scan_function when it finds a recursive call with less actual
290 arguments than formal parameters.. */
291 static bool encountered_unchangable_recursive_call;
293 /* This is a table in which for each basic block and parameter there is a
294 distance (offset + size) in that parameter which is dereferenced and
295 accessed in that BB. */
296 static HOST_WIDE_INT *bb_dereferences;
297 /* Bitmap of BBs that can cause the function to "stop" progressing by
298 returning, throwing externally, looping infinitely or calling a function
299 which might abort etc.. */
300 static bitmap final_bbs;
302 /* Representative of no accesses at all. */
303 static struct access no_accesses_representant;
305 /* Predicate to test the special value. */
308 no_accesses_p (struct access *access)
310 return access == &no_accesses_representant;
313 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
314 representative fields are dumped, otherwise those which only describe the
315 individual access are. */
319 /* Number of processed aggregates is readily available in
320 analyze_all_variable_accesses and so is not stored here. */
322 /* Number of created scalar replacements. */
325 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
329 /* Number of statements created by generate_subtree_copies. */
332 /* Number of statements created by load_assign_lhs_subreplacements. */
335 /* Number of times sra_modify_assign has deleted a statement. */
338 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
339 RHS reparately due to type conversions or nonexistent matching
341 int separate_lhs_rhs_handling;
343 /* Number of parameters that were removed because they were unused. */
344 int deleted_unused_parameters;
346 /* Number of scalars passed as parameters by reference that have been
347 converted to be passed by value. */
348 int scalar_by_ref_to_by_val;
350 /* Number of aggregate parameters that were replaced by one or more of their
352 int aggregate_params_reduced;
354 /* Numbber of components created when splitting aggregate parameters. */
355 int param_reductions_created;
359 dump_access (FILE *f, struct access *access, bool grp)
361 fprintf (f, "access { ");
362 fprintf (f, "base = (%d)'", DECL_UID (access->base));
363 print_generic_expr (f, access->base, 0);
364 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
365 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
366 fprintf (f, ", expr = ");
367 print_generic_expr (f, access->expr, 0);
368 fprintf (f, ", type = ");
369 print_generic_expr (f, access->type, 0);
371 fprintf (f, ", grp_write = %d, total_scalarization = %d, "
372 "grp_read = %d, grp_hint = %d, grp_assignment_read = %d,"
373 "grp_assignment_write = %d, grp_covered = %d, "
374 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
375 "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
376 "grp_maybe_modified = %d, "
377 "grp_not_necessarilly_dereferenced = %d\n",
378 access->grp_write, access->total_scalarization,
379 access->grp_read, access->grp_hint, access->grp_assignment_read,
380 access->grp_assignment_write, access->grp_covered,
381 access->grp_unscalarizable_region, access->grp_unscalarized_data,
382 access->grp_partial_lhs, access->grp_to_be_replaced,
383 access->grp_maybe_modified,
384 access->grp_not_necessarilly_dereferenced);
386 fprintf (f, ", write = %d, total_scalarization = %d, "
387 "grp_partial_lhs = %d\n",
388 access->write, access->total_scalarization,
389 access->grp_partial_lhs);
392 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
395 dump_access_tree_1 (FILE *f, struct access *access, int level)
401 for (i = 0; i < level; i++)
402 fputs ("* ", dump_file);
404 dump_access (f, access, true);
406 if (access->first_child)
407 dump_access_tree_1 (f, access->first_child, level + 1);
409 access = access->next_sibling;
414 /* Dump all access trees for a variable, given the pointer to the first root in
418 dump_access_tree (FILE *f, struct access *access)
420 for (; access; access = access->next_grp)
421 dump_access_tree_1 (f, access, 0);
424 /* Return true iff ACC is non-NULL and has subaccesses. */
427 access_has_children_p (struct access *acc)
429 return acc && acc->first_child;
432 /* Return a vector of pointers to accesses for the variable given in BASE or
433 NULL if there is none. */
435 static VEC (access_p, heap) *
436 get_base_access_vector (tree base)
440 slot = pointer_map_contains (base_access_vec, base);
444 return *(VEC (access_p, heap) **) slot;
447 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
448 in ACCESS. Return NULL if it cannot be found. */
450 static struct access *
451 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
454 while (access && (access->offset != offset || access->size != size))
456 struct access *child = access->first_child;
458 while (child && (child->offset + child->size <= offset))
459 child = child->next_sibling;
466 /* Return the first group representative for DECL or NULL if none exists. */
468 static struct access *
469 get_first_repr_for_decl (tree base)
471 VEC (access_p, heap) *access_vec;
473 access_vec = get_base_access_vector (base);
477 return VEC_index (access_p, access_vec, 0);
480 /* Find an access representative for the variable BASE and given OFFSET and
481 SIZE. Requires that access trees have already been built. Return NULL if
482 it cannot be found. */
484 static struct access *
485 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
488 struct access *access;
490 access = get_first_repr_for_decl (base);
491 while (access && (access->offset + access->size <= offset))
492 access = access->next_grp;
496 return find_access_in_subtree (access, offset, size);
499 /* Add LINK to the linked list of assign links of RACC. */
501 add_link_to_rhs (struct access *racc, struct assign_link *link)
503 gcc_assert (link->racc == racc);
505 if (!racc->first_link)
507 gcc_assert (!racc->last_link);
508 racc->first_link = link;
511 racc->last_link->next = link;
513 racc->last_link = link;
517 /* Move all link structures in their linked list in OLD_RACC to the linked list
520 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
522 if (!old_racc->first_link)
524 gcc_assert (!old_racc->last_link);
528 if (new_racc->first_link)
530 gcc_assert (!new_racc->last_link->next);
531 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
533 new_racc->last_link->next = old_racc->first_link;
534 new_racc->last_link = old_racc->last_link;
538 gcc_assert (!new_racc->last_link);
540 new_racc->first_link = old_racc->first_link;
541 new_racc->last_link = old_racc->last_link;
543 old_racc->first_link = old_racc->last_link = NULL;
546 /* Add ACCESS to the work queue (which is actually a stack). */
549 add_access_to_work_queue (struct access *access)
551 if (!access->grp_queued)
553 gcc_assert (!access->next_queued);
554 access->next_queued = work_queue_head;
555 access->grp_queued = 1;
556 work_queue_head = access;
560 /* Pop an access from the work queue, and return it, assuming there is one. */
562 static struct access *
563 pop_access_from_work_queue (void)
565 struct access *access = work_queue_head;
567 work_queue_head = access->next_queued;
568 access->next_queued = NULL;
569 access->grp_queued = 0;
574 /* Allocate necessary structures. */
577 sra_initialize (void)
579 candidate_bitmap = BITMAP_ALLOC (NULL);
580 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
581 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
582 gcc_obstack_init (&name_obstack);
583 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
584 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
585 base_access_vec = pointer_map_create ();
586 memset (&sra_stats, 0, sizeof (sra_stats));
587 encountered_apply_args = false;
588 encountered_recursive_call = false;
589 encountered_unchangable_recursive_call = false;
592 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
595 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
596 void *data ATTRIBUTE_UNUSED)
598 VEC (access_p, heap) *access_vec;
599 access_vec = (VEC (access_p, heap) *) *value;
600 VEC_free (access_p, heap, access_vec);
605 /* Deallocate all general structures. */
608 sra_deinitialize (void)
610 BITMAP_FREE (candidate_bitmap);
611 BITMAP_FREE (should_scalarize_away_bitmap);
612 BITMAP_FREE (cannot_scalarize_away_bitmap);
613 free_alloc_pool (access_pool);
614 free_alloc_pool (link_pool);
615 obstack_free (&name_obstack, NULL);
617 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
618 pointer_map_destroy (base_access_vec);
621 /* Remove DECL from candidates for SRA and write REASON to the dump file if
624 disqualify_candidate (tree decl, const char *reason)
626 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
628 if (dump_file && (dump_flags & TDF_DETAILS))
630 fprintf (dump_file, "! Disqualifying ");
631 print_generic_expr (dump_file, decl, 0);
632 fprintf (dump_file, " - %s\n", reason);
636 /* Return true iff the type contains a field or an element which does not allow
640 type_internals_preclude_sra_p (tree type)
645 switch (TREE_CODE (type))
649 case QUAL_UNION_TYPE:
650 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
651 if (TREE_CODE (fld) == FIELD_DECL)
653 tree ft = TREE_TYPE (fld);
655 if (TREE_THIS_VOLATILE (fld)
656 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
657 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
658 || !host_integerp (DECL_SIZE (fld), 1)
659 || (AGGREGATE_TYPE_P (ft)
660 && int_bit_position (fld) % BITS_PER_UNIT != 0))
663 if (AGGREGATE_TYPE_P (ft)
664 && type_internals_preclude_sra_p (ft))
671 et = TREE_TYPE (type);
673 if (AGGREGATE_TYPE_P (et))
674 return type_internals_preclude_sra_p (et);
683 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
684 base variable if it is. Return T if it is not an SSA_NAME. */
687 get_ssa_base_param (tree t)
689 if (TREE_CODE (t) == SSA_NAME)
691 if (SSA_NAME_IS_DEFAULT_DEF (t))
692 return SSA_NAME_VAR (t);
699 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
700 belongs to, unless the BB has already been marked as a potentially
704 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
706 basic_block bb = gimple_bb (stmt);
707 int idx, parm_index = 0;
710 if (bitmap_bit_p (final_bbs, bb->index))
713 for (parm = DECL_ARGUMENTS (current_function_decl);
714 parm && parm != base;
715 parm = DECL_CHAIN (parm))
718 gcc_assert (parm_index < func_param_count);
720 idx = bb->index * func_param_count + parm_index;
721 if (bb_dereferences[idx] < dist)
722 bb_dereferences[idx] = dist;
725 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
726 the three fields. Also add it to the vector of accesses corresponding to
727 the base. Finally, return the new access. */
729 static struct access *
730 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
732 VEC (access_p, heap) *vec;
733 struct access *access;
736 access = (struct access *) pool_alloc (access_pool);
737 memset (access, 0, sizeof (struct access));
739 access->offset = offset;
742 slot = pointer_map_contains (base_access_vec, base);
744 vec = (VEC (access_p, heap) *) *slot;
746 vec = VEC_alloc (access_p, heap, 32);
748 VEC_safe_push (access_p, heap, vec, access);
750 *((struct VEC (access_p,heap) **)
751 pointer_map_insert (base_access_vec, base)) = vec;
756 /* Create and insert access for EXPR. Return created access, or NULL if it is
759 static struct access *
760 create_access (tree expr, gimple stmt, bool write)
762 struct access *access;
763 HOST_WIDE_INT offset, size, max_size;
765 bool ptr, unscalarizable_region = false;
767 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
769 if (sra_mode == SRA_MODE_EARLY_IPA
770 && TREE_CODE (base) == MEM_REF)
772 base = get_ssa_base_param (TREE_OPERAND (base, 0));
780 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
783 if (sra_mode == SRA_MODE_EARLY_IPA)
785 if (size < 0 || size != max_size)
787 disqualify_candidate (base, "Encountered a variable sized access.");
790 if (TREE_CODE (expr) == COMPONENT_REF
791 && DECL_BIT_FIELD (TREE_OPERAND (expr, 1)))
793 disqualify_candidate (base, "Encountered a bit-field access.");
796 gcc_checking_assert ((offset % BITS_PER_UNIT) == 0);
799 mark_parm_dereference (base, offset + size, stmt);
803 if (size != max_size)
806 unscalarizable_region = true;
810 disqualify_candidate (base, "Encountered an unconstrained access.");
815 access = create_access_1 (base, offset, size);
817 access->type = TREE_TYPE (expr);
818 access->write = write;
819 access->grp_unscalarizable_region = unscalarizable_region;
822 if (TREE_CODE (expr) == COMPONENT_REF
823 && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1)))
824 access->non_addressable = 1;
830 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
831 register types or (recursively) records with only these two kinds of fields.
832 It also returns false if any of these records contains a bit-field. */
835 type_consists_of_records_p (tree type)
839 if (TREE_CODE (type) != RECORD_TYPE)
842 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
843 if (TREE_CODE (fld) == FIELD_DECL)
845 tree ft = TREE_TYPE (fld);
847 if (DECL_BIT_FIELD (fld))
850 if (!is_gimple_reg_type (ft)
851 && !type_consists_of_records_p (ft))
858 /* Create total_scalarization accesses for all scalar type fields in DECL that
859 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE
860 must be the top-most VAR_DECL representing the variable, OFFSET must be the
861 offset of DECL within BASE. REF must be the memory reference expression for
865 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset,
868 tree fld, decl_type = TREE_TYPE (decl);
870 for (fld = TYPE_FIELDS (decl_type); fld; fld = DECL_CHAIN (fld))
871 if (TREE_CODE (fld) == FIELD_DECL)
873 HOST_WIDE_INT pos = offset + int_bit_position (fld);
874 tree ft = TREE_TYPE (fld);
875 tree nref = build3 (COMPONENT_REF, TREE_TYPE (fld), ref, fld,
878 if (is_gimple_reg_type (ft))
880 struct access *access;
883 size = tree_low_cst (DECL_SIZE (fld), 1);
884 access = create_access_1 (base, pos, size);
887 access->total_scalarization = 1;
888 /* Accesses for intraprocedural SRA can have their stmt NULL. */
891 completely_scalarize_record (base, fld, pos, nref);
896 /* Search the given tree for a declaration by skipping handled components and
897 exclude it from the candidates. */
900 disqualify_base_of_expr (tree t, const char *reason)
902 t = get_base_address (t);
903 if (sra_mode == SRA_MODE_EARLY_IPA
904 && TREE_CODE (t) == MEM_REF)
905 t = get_ssa_base_param (TREE_OPERAND (t, 0));
908 disqualify_candidate (t, reason);
911 /* Scan expression EXPR and create access structures for all accesses to
912 candidates for scalarization. Return the created access or NULL if none is
915 static struct access *
916 build_access_from_expr_1 (tree expr, gimple stmt, bool write)
918 struct access *ret = NULL;
921 if (TREE_CODE (expr) == BIT_FIELD_REF
922 || TREE_CODE (expr) == IMAGPART_EXPR
923 || TREE_CODE (expr) == REALPART_EXPR)
925 expr = TREE_OPERAND (expr, 0);
931 /* We need to dive through V_C_Es in order to get the size of its parameter
932 and not the result type. Ada produces such statements. We are also
933 capable of handling the topmost V_C_E but not any of those buried in other
934 handled components. */
935 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
936 expr = TREE_OPERAND (expr, 0);
938 if (contains_view_convert_expr_p (expr))
940 disqualify_base_of_expr (expr, "V_C_E under a different handled "
945 switch (TREE_CODE (expr))
948 if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR
949 && sra_mode != SRA_MODE_EARLY_IPA)
957 case ARRAY_RANGE_REF:
958 ret = create_access (expr, stmt, write);
965 if (write && partial_ref && ret)
966 ret->grp_partial_lhs = 1;
971 /* Scan expression EXPR and create access structures for all accesses to
972 candidates for scalarization. Return true if any access has been inserted.
973 STMT must be the statement from which the expression is taken, WRITE must be
974 true if the expression is a store and false otherwise. */
977 build_access_from_expr (tree expr, gimple stmt, bool write)
979 struct access *access;
981 access = build_access_from_expr_1 (expr, stmt, write);
984 /* This means the aggregate is accesses as a whole in a way other than an
985 assign statement and thus cannot be removed even if we had a scalar
986 replacement for everything. */
987 if (cannot_scalarize_away_bitmap)
988 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
994 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
995 modes in which it matters, return true iff they have been disqualified. RHS
996 may be NULL, in that case ignore it. If we scalarize an aggregate in
997 intra-SRA we may need to add statements after each statement. This is not
998 possible if a statement unconditionally has to end the basic block. */
1000 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
1002 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1003 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
1005 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1007 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1013 /* Scan expressions occuring in STMT, create access structures for all accesses
1014 to candidates for scalarization and remove those candidates which occur in
1015 statements or expressions that prevent them from being split apart. Return
1016 true if any access has been inserted. */
1019 build_accesses_from_assign (gimple stmt)
1022 struct access *lacc, *racc;
1024 if (!gimple_assign_single_p (stmt))
1027 lhs = gimple_assign_lhs (stmt);
1028 rhs = gimple_assign_rhs1 (stmt);
1030 if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
1033 racc = build_access_from_expr_1 (rhs, stmt, false);
1034 lacc = build_access_from_expr_1 (lhs, stmt, true);
1037 lacc->grp_assignment_write = 1;
1041 racc->grp_assignment_read = 1;
1042 if (should_scalarize_away_bitmap && !gimple_has_volatile_ops (stmt)
1043 && !is_gimple_reg_type (racc->type))
1044 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1048 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1049 && !lacc->grp_unscalarizable_region
1050 && !racc->grp_unscalarizable_region
1051 && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1052 /* FIXME: Turn the following line into an assert after PR 40058 is
1054 && lacc->size == racc->size
1055 && useless_type_conversion_p (lacc->type, racc->type))
1057 struct assign_link *link;
1059 link = (struct assign_link *) pool_alloc (link_pool);
1060 memset (link, 0, sizeof (struct assign_link));
1065 add_link_to_rhs (racc, link);
1068 return lacc || racc;
1071 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1072 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1075 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1076 void *data ATTRIBUTE_UNUSED)
1078 op = get_base_address (op);
1081 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1086 /* Return true iff callsite CALL has at least as many actual arguments as there
1087 are formal parameters of the function currently processed by IPA-SRA. */
1090 callsite_has_enough_arguments_p (gimple call)
1092 return gimple_call_num_args (call) >= (unsigned) func_param_count;
1095 /* Scan function and look for interesting expressions and create access
1096 structures for them. Return true iff any access is created. */
1099 scan_function (void)
1106 gimple_stmt_iterator gsi;
1107 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1109 gimple stmt = gsi_stmt (gsi);
1113 if (final_bbs && stmt_can_throw_external (stmt))
1114 bitmap_set_bit (final_bbs, bb->index);
1115 switch (gimple_code (stmt))
1118 t = gimple_return_retval (stmt);
1120 ret |= build_access_from_expr (t, stmt, false);
1122 bitmap_set_bit (final_bbs, bb->index);
1126 ret |= build_accesses_from_assign (stmt);
1130 for (i = 0; i < gimple_call_num_args (stmt); i++)
1131 ret |= build_access_from_expr (gimple_call_arg (stmt, i),
1134 if (sra_mode == SRA_MODE_EARLY_IPA)
1136 tree dest = gimple_call_fndecl (stmt);
1137 int flags = gimple_call_flags (stmt);
1141 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1142 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1143 encountered_apply_args = true;
1144 if (cgraph_get_node (dest)
1145 == cgraph_get_node (current_function_decl))
1147 encountered_recursive_call = true;
1148 if (!callsite_has_enough_arguments_p (stmt))
1149 encountered_unchangable_recursive_call = true;
1154 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1155 bitmap_set_bit (final_bbs, bb->index);
1158 t = gimple_call_lhs (stmt);
1159 if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
1160 ret |= build_access_from_expr (t, stmt, true);
1164 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1167 bitmap_set_bit (final_bbs, bb->index);
1169 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1171 t = TREE_VALUE (gimple_asm_input_op (stmt, i));
1172 ret |= build_access_from_expr (t, stmt, false);
1174 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1176 t = TREE_VALUE (gimple_asm_output_op (stmt, i));
1177 ret |= build_access_from_expr (t, stmt, true);
1190 /* Helper of QSORT function. There are pointers to accesses in the array. An
1191 access is considered smaller than another if it has smaller offset or if the
1192 offsets are the same but is size is bigger. */
1195 compare_access_positions (const void *a, const void *b)
1197 const access_p *fp1 = (const access_p *) a;
1198 const access_p *fp2 = (const access_p *) b;
1199 const access_p f1 = *fp1;
1200 const access_p f2 = *fp2;
1202 if (f1->offset != f2->offset)
1203 return f1->offset < f2->offset ? -1 : 1;
1205 if (f1->size == f2->size)
1207 if (f1->type == f2->type)
1209 /* Put any non-aggregate type before any aggregate type. */
1210 else if (!is_gimple_reg_type (f1->type)
1211 && is_gimple_reg_type (f2->type))
1213 else if (is_gimple_reg_type (f1->type)
1214 && !is_gimple_reg_type (f2->type))
1216 /* Put any complex or vector type before any other scalar type. */
1217 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1218 && TREE_CODE (f1->type) != VECTOR_TYPE
1219 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1220 || TREE_CODE (f2->type) == VECTOR_TYPE))
1222 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1223 || TREE_CODE (f1->type) == VECTOR_TYPE)
1224 && TREE_CODE (f2->type) != COMPLEX_TYPE
1225 && TREE_CODE (f2->type) != VECTOR_TYPE)
1227 /* Put the integral type with the bigger precision first. */
1228 else if (INTEGRAL_TYPE_P (f1->type)
1229 && INTEGRAL_TYPE_P (f2->type))
1230 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1231 /* Put any integral type with non-full precision last. */
1232 else if (INTEGRAL_TYPE_P (f1->type)
1233 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1234 != TYPE_PRECISION (f1->type)))
1236 else if (INTEGRAL_TYPE_P (f2->type)
1237 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1238 != TYPE_PRECISION (f2->type)))
1240 /* Stabilize the sort. */
1241 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1244 /* We want the bigger accesses first, thus the opposite operator in the next
1246 return f1->size > f2->size ? -1 : 1;
1250 /* Append a name of the declaration to the name obstack. A helper function for
1254 make_fancy_decl_name (tree decl)
1258 tree name = DECL_NAME (decl);
1260 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1261 IDENTIFIER_LENGTH (name));
1264 sprintf (buffer, "D%u", DECL_UID (decl));
1265 obstack_grow (&name_obstack, buffer, strlen (buffer));
1269 /* Helper for make_fancy_name. */
1272 make_fancy_name_1 (tree expr)
1279 make_fancy_decl_name (expr);
1283 switch (TREE_CODE (expr))
1286 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1287 obstack_1grow (&name_obstack, '$');
1288 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1292 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1293 obstack_1grow (&name_obstack, '$');
1294 /* Arrays with only one element may not have a constant as their
1296 index = TREE_OPERAND (expr, 1);
1297 if (TREE_CODE (index) != INTEGER_CST)
1299 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1300 obstack_grow (&name_obstack, buffer, strlen (buffer));
1304 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1308 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1309 if (!integer_zerop (TREE_OPERAND (expr, 1)))
1311 obstack_1grow (&name_obstack, '$');
1312 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1313 TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1314 obstack_grow (&name_obstack, buffer, strlen (buffer));
1321 gcc_unreachable (); /* we treat these as scalars. */
1328 /* Create a human readable name for replacement variable of ACCESS. */
1331 make_fancy_name (tree expr)
1333 make_fancy_name_1 (expr);
1334 obstack_1grow (&name_obstack, '\0');
1335 return XOBFINISH (&name_obstack, char *);
1338 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1339 EXP_TYPE at the given OFFSET. If BASE is something for which
1340 get_addr_base_and_unit_offset returns NULL, gsi must be non-NULL and is used
1341 to insert new statements either before or below the current one as specified
1342 by INSERT_AFTER. This function is not capable of handling bitfields. */
1345 build_ref_for_offset (location_t loc, tree base, HOST_WIDE_INT offset,
1346 tree exp_type, gimple_stmt_iterator *gsi,
1349 tree prev_base = base;
1351 HOST_WIDE_INT base_offset;
1353 gcc_checking_assert (offset % BITS_PER_UNIT == 0);
1355 base = get_addr_base_and_unit_offset (base, &base_offset);
1357 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1358 offset such as array[var_index]. */
1364 gcc_checking_assert (gsi);
1365 tmp = create_tmp_reg (build_pointer_type (TREE_TYPE (prev_base)), NULL);
1366 add_referenced_var (tmp);
1367 tmp = make_ssa_name (tmp, NULL);
1368 addr = build_fold_addr_expr (unshare_expr (prev_base));
1369 stmt = gimple_build_assign (tmp, addr);
1370 gimple_set_location (stmt, loc);
1371 SSA_NAME_DEF_STMT (tmp) = stmt;
1373 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1375 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1378 off = build_int_cst (reference_alias_ptr_type (prev_base),
1379 offset / BITS_PER_UNIT);
1382 else if (TREE_CODE (base) == MEM_REF)
1384 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1385 base_offset + offset / BITS_PER_UNIT);
1386 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off, 0);
1387 base = unshare_expr (TREE_OPERAND (base, 0));
1391 off = build_int_cst (reference_alias_ptr_type (base),
1392 base_offset + offset / BITS_PER_UNIT);
1393 base = build_fold_addr_expr (unshare_expr (base));
1396 return fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1399 /* Construct a memory reference to a part of an aggregate BASE at the given
1400 OFFSET and of the same type as MODEL. In case this is a reference to a
1401 component, the function will replicate the last COMPONENT_REF of model's
1402 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1403 build_ref_for_offset. */
1406 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1407 struct access *model, gimple_stmt_iterator *gsi,
1410 if (TREE_CODE (model->expr) == COMPONENT_REF)
1413 offset -= int_bit_position (TREE_OPERAND (model->expr, 1));
1414 exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
1415 t = build_ref_for_offset (loc, base, offset, exp_type, gsi, insert_after);
1416 return fold_build3_loc (loc, COMPONENT_REF, model->type, t,
1417 TREE_OPERAND (model->expr, 1), NULL_TREE);
1420 return build_ref_for_offset (loc, base, offset, model->type,
1424 /* Construct a memory reference consisting of component_refs and array_refs to
1425 a part of an aggregate *RES (which is of type TYPE). The requested part
1426 should have type EXP_TYPE at be the given OFFSET. This function might not
1427 succeed, it returns true when it does and only then *RES points to something
1428 meaningful. This function should be used only to build expressions that we
1429 might need to present to user (e.g. in warnings). In all other situations,
1430 build_ref_for_model or build_ref_for_offset should be used instead. */
1433 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
1439 tree tr_size, index, minidx;
1440 HOST_WIDE_INT el_size;
1442 if (offset == 0 && exp_type
1443 && types_compatible_p (exp_type, type))
1446 switch (TREE_CODE (type))
1449 case QUAL_UNION_TYPE:
1451 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1453 HOST_WIDE_INT pos, size;
1454 tree expr, *expr_ptr;
1456 if (TREE_CODE (fld) != FIELD_DECL)
1459 pos = int_bit_position (fld);
1460 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1461 tr_size = DECL_SIZE (fld);
1462 if (!tr_size || !host_integerp (tr_size, 1))
1464 size = tree_low_cst (tr_size, 1);
1470 else if (pos > offset || (pos + size) <= offset)
1473 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1476 if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
1477 offset - pos, exp_type))
1486 tr_size = TYPE_SIZE (TREE_TYPE (type));
1487 if (!tr_size || !host_integerp (tr_size, 1))
1489 el_size = tree_low_cst (tr_size, 1);
1491 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1492 if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
1494 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1495 if (!integer_zerop (minidx))
1496 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1497 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1498 NULL_TREE, NULL_TREE);
1499 offset = offset % el_size;
1500 type = TREE_TYPE (type);
1515 /* Return true iff TYPE is stdarg va_list type. */
1518 is_va_list_type (tree type)
1520 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1523 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1524 those with type which is suitable for scalarization. */
1527 find_var_candidates (void)
1530 referenced_var_iterator rvi;
1533 FOR_EACH_REFERENCED_VAR (var, rvi)
1535 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1537 type = TREE_TYPE (var);
1539 if (!AGGREGATE_TYPE_P (type)
1540 || needs_to_live_in_memory (var)
1541 || TREE_THIS_VOLATILE (var)
1542 || !COMPLETE_TYPE_P (type)
1543 || !host_integerp (TYPE_SIZE (type), 1)
1544 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1545 || type_internals_preclude_sra_p (type)
1546 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1547 we also want to schedule it rather late. Thus we ignore it in
1549 || (sra_mode == SRA_MODE_EARLY_INTRA
1550 && is_va_list_type (type)))
1553 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1555 if (dump_file && (dump_flags & TDF_DETAILS))
1557 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1558 print_generic_expr (dump_file, var, 0);
1559 fprintf (dump_file, "\n");
1567 /* Sort all accesses for the given variable, check for partial overlaps and
1568 return NULL if there are any. If there are none, pick a representative for
1569 each combination of offset and size and create a linked list out of them.
1570 Return the pointer to the first representative and make sure it is the first
1571 one in the vector of accesses. */
1573 static struct access *
1574 sort_and_splice_var_accesses (tree var)
1576 int i, j, access_count;
1577 struct access *res, **prev_acc_ptr = &res;
1578 VEC (access_p, heap) *access_vec;
1580 HOST_WIDE_INT low = -1, high = 0;
1582 access_vec = get_base_access_vector (var);
1585 access_count = VEC_length (access_p, access_vec);
1587 /* Sort by <OFFSET, SIZE>. */
1588 VEC_qsort (access_p, access_vec, compare_access_positions);
1591 while (i < access_count)
1593 struct access *access = VEC_index (access_p, access_vec, i);
1594 bool grp_write = access->write;
1595 bool grp_read = !access->write;
1596 bool grp_assignment_read = access->grp_assignment_read;
1597 bool grp_assignment_write = access->grp_assignment_write;
1598 bool multiple_reads = false;
1599 bool total_scalarization = access->total_scalarization;
1600 bool grp_partial_lhs = access->grp_partial_lhs;
1601 bool first_scalar = is_gimple_reg_type (access->type);
1602 bool unscalarizable_region = access->grp_unscalarizable_region;
1604 if (first || access->offset >= high)
1607 low = access->offset;
1608 high = access->offset + access->size;
1610 else if (access->offset > low && access->offset + access->size > high)
1613 gcc_assert (access->offset >= low
1614 && access->offset + access->size <= high);
1617 while (j < access_count)
1619 struct access *ac2 = VEC_index (access_p, access_vec, j);
1620 if (ac2->offset != access->offset || ac2->size != access->size)
1627 multiple_reads = true;
1631 grp_assignment_read |= ac2->grp_assignment_read;
1632 grp_assignment_write |= ac2->grp_assignment_write;
1633 grp_partial_lhs |= ac2->grp_partial_lhs;
1634 unscalarizable_region |= ac2->grp_unscalarizable_region;
1635 total_scalarization |= ac2->total_scalarization;
1636 relink_to_new_repr (access, ac2);
1638 /* If there are both aggregate-type and scalar-type accesses with
1639 this combination of size and offset, the comparison function
1640 should have put the scalars first. */
1641 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1642 ac2->group_representative = access;
1648 access->group_representative = access;
1649 access->grp_write = grp_write;
1650 access->grp_read = grp_read;
1651 access->grp_assignment_read = grp_assignment_read;
1652 access->grp_assignment_write = grp_assignment_write;
1653 access->grp_hint = multiple_reads || total_scalarization;
1654 access->grp_partial_lhs = grp_partial_lhs;
1655 access->grp_unscalarizable_region = unscalarizable_region;
1656 if (access->first_link)
1657 add_access_to_work_queue (access);
1659 *prev_acc_ptr = access;
1660 prev_acc_ptr = &access->next_grp;
1663 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1667 /* Create a variable for the given ACCESS which determines the type, name and a
1668 few other properties. Return the variable declaration and store it also to
1669 ACCESS->replacement. */
1672 create_access_replacement (struct access *access, bool rename)
1676 repl = create_tmp_var (access->type, "SR");
1678 add_referenced_var (repl);
1680 mark_sym_for_renaming (repl);
1682 if (!access->grp_partial_lhs
1683 && (TREE_CODE (access->type) == COMPLEX_TYPE
1684 || TREE_CODE (access->type) == VECTOR_TYPE))
1685 DECL_GIMPLE_REG_P (repl) = 1;
1687 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1688 DECL_ARTIFICIAL (repl) = 1;
1689 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1691 if (DECL_NAME (access->base)
1692 && !DECL_IGNORED_P (access->base)
1693 && !DECL_ARTIFICIAL (access->base))
1695 char *pretty_name = make_fancy_name (access->expr);
1696 tree debug_expr = unshare_expr (access->expr), d;
1698 DECL_NAME (repl) = get_identifier (pretty_name);
1699 obstack_free (&name_obstack, pretty_name);
1701 /* Get rid of any SSA_NAMEs embedded in debug_expr,
1702 as DECL_DEBUG_EXPR isn't considered when looking for still
1703 used SSA_NAMEs and thus they could be freed. All debug info
1704 generation cares is whether something is constant or variable
1705 and that get_ref_base_and_extent works properly on the
1707 for (d = debug_expr; handled_component_p (d); d = TREE_OPERAND (d, 0))
1708 switch (TREE_CODE (d))
1711 case ARRAY_RANGE_REF:
1712 if (TREE_OPERAND (d, 1)
1713 && TREE_CODE (TREE_OPERAND (d, 1)) == SSA_NAME)
1714 TREE_OPERAND (d, 1) = SSA_NAME_VAR (TREE_OPERAND (d, 1));
1715 if (TREE_OPERAND (d, 3)
1716 && TREE_CODE (TREE_OPERAND (d, 3)) == SSA_NAME)
1717 TREE_OPERAND (d, 3) = SSA_NAME_VAR (TREE_OPERAND (d, 3));
1720 if (TREE_OPERAND (d, 2)
1721 && TREE_CODE (TREE_OPERAND (d, 2)) == SSA_NAME)
1722 TREE_OPERAND (d, 2) = SSA_NAME_VAR (TREE_OPERAND (d, 2));
1727 SET_DECL_DEBUG_EXPR (repl, debug_expr);
1728 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1729 if (access->grp_no_warning)
1730 TREE_NO_WARNING (repl) = 1;
1732 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1735 TREE_NO_WARNING (repl) = 1;
1739 fprintf (dump_file, "Created a replacement for ");
1740 print_generic_expr (dump_file, access->base, 0);
1741 fprintf (dump_file, " offset: %u, size: %u: ",
1742 (unsigned) access->offset, (unsigned) access->size);
1743 print_generic_expr (dump_file, repl, 0);
1744 fprintf (dump_file, "\n");
1746 sra_stats.replacements++;
1751 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1754 get_access_replacement (struct access *access)
1756 gcc_assert (access->grp_to_be_replaced);
1758 if (!access->replacement_decl)
1759 access->replacement_decl = create_access_replacement (access, true);
1760 return access->replacement_decl;
1763 /* Return ACCESS scalar replacement, create it if it does not exist yet but do
1764 not mark it for renaming. */
1767 get_unrenamed_access_replacement (struct access *access)
1769 gcc_assert (!access->grp_to_be_replaced);
1771 if (!access->replacement_decl)
1772 access->replacement_decl = create_access_replacement (access, false);
1773 return access->replacement_decl;
1777 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1778 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1779 to it is not "within" the root. Return false iff some accesses partially
1783 build_access_subtree (struct access **access)
1785 struct access *root = *access, *last_child = NULL;
1786 HOST_WIDE_INT limit = root->offset + root->size;
1788 *access = (*access)->next_grp;
1789 while (*access && (*access)->offset + (*access)->size <= limit)
1792 root->first_child = *access;
1794 last_child->next_sibling = *access;
1795 last_child = *access;
1797 if (!build_access_subtree (access))
1801 if (*access && (*access)->offset < limit)
1807 /* Build a tree of access representatives, ACCESS is the pointer to the first
1808 one, others are linked in a list by the next_grp field. Return false iff
1809 some accesses partially overlap. */
1812 build_access_trees (struct access *access)
1816 struct access *root = access;
1818 if (!build_access_subtree (&access))
1820 root->next_grp = access;
1825 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1829 expr_with_var_bounded_array_refs_p (tree expr)
1831 while (handled_component_p (expr))
1833 if (TREE_CODE (expr) == ARRAY_REF
1834 && !host_integerp (array_ref_low_bound (expr), 0))
1836 expr = TREE_OPERAND (expr, 0);
1841 enum mark_rw_status { SRA_MRRW_NOTHING, SRA_MRRW_DIRECT, SRA_MRRW_ASSIGN};
1843 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1844 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all
1845 sorts of access flags appropriately along the way, notably always set
1846 grp_read and grp_assign_read according to MARK_READ and grp_write when
1849 Creating a replacement for a scalar access is considered beneficial if its
1850 grp_hint is set (this means we are either attempting total scalarization or
1851 there is more than one direct read access) or according to the following
1854 Access written to individually (once or more times)
1856 | Parent written to in an assignment statement
1858 | | Access read individually _once_
1860 | | | Parent read in an assignment statement
1862 | | | | Scalarize Comment
1863 -----------------------------------------------------------------------------
1864 0 0 0 0 No access for the scalar
1865 0 0 0 1 No access for the scalar
1866 0 0 1 0 No Single read - won't help
1867 0 0 1 1 No The same case
1868 0 1 0 0 No access for the scalar
1869 0 1 0 1 No access for the scalar
1870 0 1 1 0 Yes s = *g; return s.i;
1871 0 1 1 1 Yes The same case as above
1872 1 0 0 0 No Won't help
1873 1 0 0 1 Yes s.i = 1; *g = s;
1874 1 0 1 0 Yes s.i = 5; g = s.i;
1875 1 0 1 1 Yes The same case as above
1876 1 1 0 0 No Won't help.
1877 1 1 0 1 Yes s.i = 1; *g = s;
1878 1 1 1 0 Yes s = *g; return s.i;
1879 1 1 1 1 Yes Any of the above yeses */
1882 analyze_access_subtree (struct access *root, bool allow_replacements,
1883 enum mark_rw_status mark_read,
1884 enum mark_rw_status mark_write)
1886 struct access *child;
1887 HOST_WIDE_INT limit = root->offset + root->size;
1888 HOST_WIDE_INT covered_to = root->offset;
1889 bool scalar = is_gimple_reg_type (root->type);
1890 bool hole = false, sth_created = false;
1891 bool direct_read = root->grp_read;
1892 bool direct_write = root->grp_write;
1894 if (root->grp_assignment_read)
1895 mark_read = SRA_MRRW_ASSIGN;
1896 else if (mark_read == SRA_MRRW_ASSIGN)
1899 root->grp_assignment_read = 1;
1901 else if (mark_read == SRA_MRRW_DIRECT)
1903 else if (root->grp_read)
1904 mark_read = SRA_MRRW_DIRECT;
1906 if (root->grp_assignment_write)
1907 mark_write = SRA_MRRW_ASSIGN;
1908 else if (mark_write == SRA_MRRW_ASSIGN)
1910 root->grp_write = 1;
1911 root->grp_assignment_write = 1;
1913 else if (mark_write == SRA_MRRW_DIRECT)
1914 root->grp_write = 1;
1915 else if (root->grp_write)
1916 mark_write = SRA_MRRW_DIRECT;
1918 if (root->grp_unscalarizable_region)
1919 allow_replacements = false;
1921 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1922 allow_replacements = false;
1924 for (child = root->first_child; child; child = child->next_sibling)
1926 if (!hole && child->offset < covered_to)
1929 covered_to += child->size;
1931 sth_created |= analyze_access_subtree (child,
1932 allow_replacements && !scalar,
1933 mark_read, mark_write);
1935 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1936 hole |= !child->grp_covered;
1939 if (allow_replacements && scalar && !root->first_child
1941 || ((direct_write || root->grp_assignment_write)
1942 && (direct_read || root->grp_assignment_read))))
1944 if (dump_file && (dump_flags & TDF_DETAILS))
1946 fprintf (dump_file, "Marking ");
1947 print_generic_expr (dump_file, root->base, 0);
1948 fprintf (dump_file, " offset: %u, size: %u: ",
1949 (unsigned) root->offset, (unsigned) root->size);
1950 fprintf (dump_file, " to be replaced.\n");
1953 root->grp_to_be_replaced = 1;
1957 else if (covered_to < limit)
1960 if (sth_created && !hole)
1962 root->grp_covered = 1;
1965 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1966 root->grp_unscalarized_data = 1; /* not covered and written to */
1972 /* Analyze all access trees linked by next_grp by the means of
1973 analyze_access_subtree. */
1975 analyze_access_trees (struct access *access)
1981 if (analyze_access_subtree (access, true,
1982 SRA_MRRW_NOTHING, SRA_MRRW_NOTHING))
1984 access = access->next_grp;
1990 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1991 SIZE would conflict with an already existing one. If exactly such a child
1992 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1995 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1996 HOST_WIDE_INT size, struct access **exact_match)
1998 struct access *child;
2000 for (child = lacc->first_child; child; child = child->next_sibling)
2002 if (child->offset == norm_offset && child->size == size)
2004 *exact_match = child;
2008 if (child->offset < norm_offset + size
2009 && child->offset + child->size > norm_offset)
2016 /* Create a new child access of PARENT, with all properties just like MODEL
2017 except for its offset and with its grp_write false and grp_read true.
2018 Return the new access or NULL if it cannot be created. Note that this access
2019 is created long after all splicing and sorting, it's not located in any
2020 access vector and is automatically a representative of its group. */
2022 static struct access *
2023 create_artificial_child_access (struct access *parent, struct access *model,
2024 HOST_WIDE_INT new_offset)
2026 struct access *access;
2027 struct access **child;
2028 tree expr = parent->base;
2030 gcc_assert (!model->grp_unscalarizable_region);
2032 access = (struct access *) pool_alloc (access_pool);
2033 memset (access, 0, sizeof (struct access));
2034 if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
2037 access->grp_no_warning = true;
2038 expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
2039 new_offset, model, NULL, false);
2042 access->base = parent->base;
2043 access->expr = expr;
2044 access->offset = new_offset;
2045 access->size = model->size;
2046 access->type = model->type;
2047 access->grp_write = true;
2048 access->grp_read = false;
2050 child = &parent->first_child;
2051 while (*child && (*child)->offset < new_offset)
2052 child = &(*child)->next_sibling;
2054 access->next_sibling = *child;
2061 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
2062 true if any new subaccess was created. Additionally, if RACC is a scalar
2063 access but LACC is not, change the type of the latter, if possible. */
2066 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
2068 struct access *rchild;
2069 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
2072 if (is_gimple_reg_type (lacc->type)
2073 || lacc->grp_unscalarizable_region
2074 || racc->grp_unscalarizable_region)
2077 if (!lacc->first_child && !racc->first_child
2078 && is_gimple_reg_type (racc->type))
2080 tree t = lacc->base;
2082 lacc->type = racc->type;
2083 if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t), lacc->offset,
2088 lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
2089 lacc->base, lacc->offset,
2091 lacc->grp_no_warning = true;
2096 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
2098 struct access *new_acc = NULL;
2099 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
2101 if (rchild->grp_unscalarizable_region)
2104 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
2109 rchild->grp_hint = 1;
2110 new_acc->grp_hint |= new_acc->grp_read;
2111 if (rchild->first_child)
2112 ret |= propagate_subaccesses_across_link (new_acc, rchild);
2117 rchild->grp_hint = 1;
2118 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
2122 if (racc->first_child)
2123 propagate_subaccesses_across_link (new_acc, rchild);
2130 /* Propagate all subaccesses across assignment links. */
2133 propagate_all_subaccesses (void)
2135 while (work_queue_head)
2137 struct access *racc = pop_access_from_work_queue ();
2138 struct assign_link *link;
2140 gcc_assert (racc->first_link);
2142 for (link = racc->first_link; link; link = link->next)
2144 struct access *lacc = link->lacc;
2146 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2148 lacc = lacc->group_representative;
2149 if (propagate_subaccesses_across_link (lacc, racc)
2150 && lacc->first_link)
2151 add_access_to_work_queue (lacc);
2156 /* Go through all accesses collected throughout the (intraprocedural) analysis
2157 stage, exclude overlapping ones, identify representatives and build trees
2158 out of them, making decisions about scalarization on the way. Return true
2159 iff there are any to-be-scalarized variables after this stage. */
2162 analyze_all_variable_accesses (void)
2165 bitmap tmp = BITMAP_ALLOC (NULL);
2167 unsigned i, max_total_scalarization_size;
2169 max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2170 * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2172 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2173 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2174 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2176 tree var = referenced_var (i);
2178 if (TREE_CODE (var) == VAR_DECL
2179 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2180 <= max_total_scalarization_size)
2181 && type_consists_of_records_p (TREE_TYPE (var)))
2183 completely_scalarize_record (var, var, 0, var);
2184 if (dump_file && (dump_flags & TDF_DETAILS))
2186 fprintf (dump_file, "Will attempt to totally scalarize ");
2187 print_generic_expr (dump_file, var, 0);
2188 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2193 bitmap_copy (tmp, candidate_bitmap);
2194 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2196 tree var = referenced_var (i);
2197 struct access *access;
2199 access = sort_and_splice_var_accesses (var);
2200 if (!access || !build_access_trees (access))
2201 disqualify_candidate (var,
2202 "No or inhibitingly overlapping accesses.");
2205 propagate_all_subaccesses ();
2207 bitmap_copy (tmp, candidate_bitmap);
2208 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2210 tree var = referenced_var (i);
2211 struct access *access = get_first_repr_for_decl (var);
2213 if (analyze_access_trees (access))
2216 if (dump_file && (dump_flags & TDF_DETAILS))
2218 fprintf (dump_file, "\nAccess trees for ");
2219 print_generic_expr (dump_file, var, 0);
2220 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2221 dump_access_tree (dump_file, access);
2222 fprintf (dump_file, "\n");
2226 disqualify_candidate (var, "No scalar replacements to be created.");
2233 statistics_counter_event (cfun, "Scalarized aggregates", res);
2240 /* Generate statements copying scalar replacements of accesses within a subtree
2241 into or out of AGG. ACCESS, all its children, siblings and their children
2242 are to be processed. AGG is an aggregate type expression (can be a
2243 declaration but does not have to be, it can for example also be a mem_ref or
2244 a series of handled components). TOP_OFFSET is the offset of the processed
2245 subtree which has to be subtracted from offsets of individual accesses to
2246 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
2247 replacements in the interval <start_offset, start_offset + chunk_size>,
2248 otherwise copy all. GSI is a statement iterator used to place the new
2249 statements. WRITE should be true when the statements should write from AGG
2250 to the replacement and false if vice versa. if INSERT_AFTER is true, new
2251 statements will be added after the current statement in GSI, they will be
2252 added before the statement otherwise. */
2255 generate_subtree_copies (struct access *access, tree agg,
2256 HOST_WIDE_INT top_offset,
2257 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2258 gimple_stmt_iterator *gsi, bool write,
2259 bool insert_after, location_t loc)
2263 if (chunk_size && access->offset >= start_offset + chunk_size)
2266 if (access->grp_to_be_replaced
2268 || access->offset + access->size > start_offset))
2270 tree expr, repl = get_access_replacement (access);
2273 expr = build_ref_for_model (loc, agg, access->offset - top_offset,
2274 access, gsi, insert_after);
2278 if (access->grp_partial_lhs)
2279 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2281 insert_after ? GSI_NEW_STMT
2283 stmt = gimple_build_assign (repl, expr);
2287 TREE_NO_WARNING (repl) = 1;
2288 if (access->grp_partial_lhs)
2289 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2291 insert_after ? GSI_NEW_STMT
2293 stmt = gimple_build_assign (expr, repl);
2295 gimple_set_location (stmt, loc);
2298 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2300 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2302 sra_stats.subtree_copies++;
2305 if (access->first_child)
2306 generate_subtree_copies (access->first_child, agg, top_offset,
2307 start_offset, chunk_size, gsi,
2308 write, insert_after, loc);
2310 access = access->next_sibling;
2315 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2316 the root of the subtree to be processed. GSI is the statement iterator used
2317 for inserting statements which are added after the current statement if
2318 INSERT_AFTER is true or before it otherwise. */
2321 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2322 bool insert_after, location_t loc)
2325 struct access *child;
2327 if (access->grp_to_be_replaced)
2331 stmt = gimple_build_assign (get_access_replacement (access),
2332 build_zero_cst (access->type));
2334 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2336 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2338 gimple_set_location (stmt, loc);
2341 for (child = access->first_child; child; child = child->next_sibling)
2342 init_subtree_with_zero (child, gsi, insert_after, loc);
2345 /* Search for an access representative for the given expression EXPR and
2346 return it or NULL if it cannot be found. */
2348 static struct access *
2349 get_access_for_expr (tree expr)
2351 HOST_WIDE_INT offset, size, max_size;
2354 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2355 a different size than the size of its argument and we need the latter
2357 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2358 expr = TREE_OPERAND (expr, 0);
2360 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2361 if (max_size == -1 || !DECL_P (base))
2364 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2367 return get_var_base_offset_size_access (base, offset, max_size);
2370 /* Replace the expression EXPR with a scalar replacement if there is one and
2371 generate other statements to do type conversion or subtree copying if
2372 necessary. GSI is used to place newly created statements, WRITE is true if
2373 the expression is being written to (it is on a LHS of a statement or output
2374 in an assembly statement). */
2377 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
2380 struct access *access;
2383 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2386 expr = &TREE_OPERAND (*expr, 0);
2391 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2392 expr = &TREE_OPERAND (*expr, 0);
2393 access = get_access_for_expr (*expr);
2396 type = TREE_TYPE (*expr);
2398 loc = gimple_location (gsi_stmt (*gsi));
2399 if (access->grp_to_be_replaced)
2401 tree repl = get_access_replacement (access);
2402 /* If we replace a non-register typed access simply use the original
2403 access expression to extract the scalar component afterwards.
2404 This happens if scalarizing a function return value or parameter
2405 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2406 gcc.c-torture/compile/20011217-1.c.
2408 We also want to use this when accessing a complex or vector which can
2409 be accessed as a different type too, potentially creating a need for
2410 type conversion (see PR42196) and when scalarized unions are involved
2411 in assembler statements (see PR42398). */
2412 if (!useless_type_conversion_p (type, access->type))
2416 ref = build_ref_for_model (loc, access->base, access->offset, access,
2423 if (access->grp_partial_lhs)
2424 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2425 false, GSI_NEW_STMT);
2426 stmt = gimple_build_assign (repl, ref);
2427 gimple_set_location (stmt, loc);
2428 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2434 if (access->grp_partial_lhs)
2435 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2436 true, GSI_SAME_STMT);
2437 stmt = gimple_build_assign (ref, repl);
2438 gimple_set_location (stmt, loc);
2439 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2447 if (access->first_child)
2449 HOST_WIDE_INT start_offset, chunk_size;
2451 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2452 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2454 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2455 start_offset = access->offset
2456 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2459 start_offset = chunk_size = 0;
2461 generate_subtree_copies (access->first_child, access->base, 0,
2462 start_offset, chunk_size, gsi, write, write,
2468 /* Where scalar replacements of the RHS have been written to when a replacement
2469 of a LHS of an assigments cannot be direclty loaded from a replacement of
2471 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2472 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2473 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2475 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2476 base aggregate if there are unscalarized data or directly to LHS of the
2477 statement that is pointed to by GSI otherwise. */
2479 static enum unscalarized_data_handling
2480 handle_unscalarized_data_in_subtree (struct access *top_racc,
2481 gimple_stmt_iterator *gsi)
2483 if (top_racc->grp_unscalarized_data)
2485 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2487 gimple_location (gsi_stmt (*gsi)));
2488 return SRA_UDH_RIGHT;
2492 tree lhs = gimple_assign_lhs (gsi_stmt (*gsi));
2493 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2494 0, 0, gsi, false, false,
2495 gimple_location (gsi_stmt (*gsi)));
2496 return SRA_UDH_LEFT;
2501 /* Try to generate statements to load all sub-replacements in an access subtree
2502 formed by children of LACC from scalar replacements in the TOP_RACC subtree.
2503 If that is not possible, refresh the TOP_RACC base aggregate and load the
2504 accesses from it. LEFT_OFFSET is the offset of the left whole subtree being
2505 copied. NEW_GSI is stmt iterator used for statement insertions after the
2506 original assignment, OLD_GSI is used to insert statements before the
2507 assignment. *REFRESHED keeps the information whether we have needed to
2508 refresh replacements of the LHS and from which side of the assignments this
2512 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2513 HOST_WIDE_INT left_offset,
2514 gimple_stmt_iterator *old_gsi,
2515 gimple_stmt_iterator *new_gsi,
2516 enum unscalarized_data_handling *refreshed)
2518 location_t loc = gimple_location (gsi_stmt (*old_gsi));
2519 for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
2521 if (lacc->grp_to_be_replaced)
2523 struct access *racc;
2524 HOST_WIDE_INT offset = lacc->offset - left_offset + top_racc->offset;
2528 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2529 if (racc && racc->grp_to_be_replaced)
2531 rhs = get_access_replacement (racc);
2532 if (!useless_type_conversion_p (lacc->type, racc->type))
2533 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2537 /* No suitable access on the right hand side, need to load from
2538 the aggregate. See if we have to update it first... */
2539 if (*refreshed == SRA_UDH_NONE)
2540 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2543 if (*refreshed == SRA_UDH_LEFT)
2544 rhs = build_ref_for_model (loc, lacc->base, lacc->offset, lacc,
2547 rhs = build_ref_for_model (loc, top_racc->base, offset, lacc,
2551 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2552 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2553 gimple_set_location (stmt, loc);
2555 sra_stats.subreplacements++;
2557 else if (*refreshed == SRA_UDH_NONE
2558 && lacc->grp_read && !lacc->grp_covered)
2559 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2562 if (lacc->first_child)
2563 load_assign_lhs_subreplacements (lacc, top_racc, left_offset,
2564 old_gsi, new_gsi, refreshed);
2568 /* Result code for SRA assignment modification. */
2569 enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
2570 SRA_AM_MODIFIED, /* stmt changed but not
2572 SRA_AM_REMOVED }; /* stmt eliminated */
2574 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2575 to the assignment and GSI is the statement iterator pointing at it. Returns
2576 the same values as sra_modify_assign. */
2578 static enum assignment_mod_result
2579 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2581 tree lhs = gimple_assign_lhs (*stmt);
2585 acc = get_access_for_expr (lhs);
2589 loc = gimple_location (*stmt);
2590 if (VEC_length (constructor_elt,
2591 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2593 /* I have never seen this code path trigger but if it can happen the
2594 following should handle it gracefully. */
2595 if (access_has_children_p (acc))
2596 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2598 return SRA_AM_MODIFIED;
2601 if (acc->grp_covered)
2603 init_subtree_with_zero (acc, gsi, false, loc);
2604 unlink_stmt_vdef (*stmt);
2605 gsi_remove (gsi, true);
2606 return SRA_AM_REMOVED;
2610 init_subtree_with_zero (acc, gsi, true, loc);
2611 return SRA_AM_MODIFIED;
2615 /* Create and return a new suitable default definition SSA_NAME for RACC which
2616 is an access describing an uninitialized part of an aggregate that is being
2620 get_repl_default_def_ssa_name (struct access *racc)
2624 decl = get_unrenamed_access_replacement (racc);
2626 repl = gimple_default_def (cfun, decl);
2629 repl = make_ssa_name (decl, gimple_build_nop ());
2630 set_default_def (decl, repl);
2636 /* Return true if REF has a COMPONENT_REF with a bit-field field declaration
2640 contains_bitfld_comp_ref_p (const_tree ref)
2642 while (handled_component_p (ref))
2644 if (TREE_CODE (ref) == COMPONENT_REF
2645 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
2647 ref = TREE_OPERAND (ref, 0);
2653 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
2654 bit-field field declaration somewhere in it. */
2657 contains_vce_or_bfcref_p (const_tree ref)
2659 while (handled_component_p (ref))
2661 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
2662 || (TREE_CODE (ref) == COMPONENT_REF
2663 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
2665 ref = TREE_OPERAND (ref, 0);
2671 /* Examine both sides of the assignment statement pointed to by STMT, replace
2672 them with a scalare replacement if there is one and generate copying of
2673 replacements if scalarized aggregates have been used in the assignment. GSI
2674 is used to hold generated statements for type conversions and subtree
2677 static enum assignment_mod_result
2678 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2680 struct access *lacc, *racc;
2682 bool modify_this_stmt = false;
2683 bool force_gimple_rhs = false;
2685 gimple_stmt_iterator orig_gsi = *gsi;
2687 if (!gimple_assign_single_p (*stmt))
2689 lhs = gimple_assign_lhs (*stmt);
2690 rhs = gimple_assign_rhs1 (*stmt);
2692 if (TREE_CODE (rhs) == CONSTRUCTOR)
2693 return sra_modify_constructor_assign (stmt, gsi);
2695 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2696 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2697 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2699 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2701 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2703 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2706 lacc = get_access_for_expr (lhs);
2707 racc = get_access_for_expr (rhs);
2711 loc = gimple_location (*stmt);
2712 if (lacc && lacc->grp_to_be_replaced)
2714 lhs = get_access_replacement (lacc);
2715 gimple_assign_set_lhs (*stmt, lhs);
2716 modify_this_stmt = true;
2717 if (lacc->grp_partial_lhs)
2718 force_gimple_rhs = true;
2722 if (racc && racc->grp_to_be_replaced)
2724 rhs = get_access_replacement (racc);
2725 modify_this_stmt = true;
2726 if (racc->grp_partial_lhs)
2727 force_gimple_rhs = true;
2731 if (modify_this_stmt)
2733 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2735 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2736 ??? This should move to fold_stmt which we simply should
2737 call after building a VIEW_CONVERT_EXPR here. */
2738 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2739 && !contains_bitfld_comp_ref_p (lhs)
2740 && !access_has_children_p (lacc))
2742 lhs = build_ref_for_offset (loc, lhs, 0, TREE_TYPE (rhs),
2744 gimple_assign_set_lhs (*stmt, lhs);
2746 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2747 && !contains_vce_or_bfcref_p (rhs)
2748 && !access_has_children_p (racc))
2749 rhs = build_ref_for_offset (loc, rhs, 0, TREE_TYPE (lhs),
2752 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2754 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
2756 if (is_gimple_reg_type (TREE_TYPE (lhs))
2757 && TREE_CODE (lhs) != SSA_NAME)
2758 force_gimple_rhs = true;
2763 /* From this point on, the function deals with assignments in between
2764 aggregates when at least one has scalar reductions of some of its
2765 components. There are three possible scenarios: Both the LHS and RHS have
2766 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2768 In the first case, we would like to load the LHS components from RHS
2769 components whenever possible. If that is not possible, we would like to
2770 read it directly from the RHS (after updating it by storing in it its own
2771 components). If there are some necessary unscalarized data in the LHS,
2772 those will be loaded by the original assignment too. If neither of these
2773 cases happen, the original statement can be removed. Most of this is done
2774 by load_assign_lhs_subreplacements.
2776 In the second case, we would like to store all RHS scalarized components
2777 directly into LHS and if they cover the aggregate completely, remove the
2778 statement too. In the third case, we want the LHS components to be loaded
2779 directly from the RHS (DSE will remove the original statement if it
2782 This is a bit complex but manageable when types match and when unions do
2783 not cause confusion in a way that we cannot really load a component of LHS
2784 from the RHS or vice versa (the access representing this level can have
2785 subaccesses that are accessible only through a different union field at a
2786 higher level - different from the one used in the examined expression).
2789 Therefore, I specially handle a fourth case, happening when there is a
2790 specific type cast or it is impossible to locate a scalarized subaccess on
2791 the other side of the expression. If that happens, I simply "refresh" the
2792 RHS by storing in it is scalarized components leave the original statement
2793 there to do the copying and then load the scalar replacements of the LHS.
2794 This is what the first branch does. */
2796 if (gimple_has_volatile_ops (*stmt)
2797 || contains_vce_or_bfcref_p (rhs)
2798 || contains_vce_or_bfcref_p (lhs))
2800 if (access_has_children_p (racc))
2801 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2802 gsi, false, false, loc);
2803 if (access_has_children_p (lacc))
2804 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2805 gsi, true, true, loc);
2806 sra_stats.separate_lhs_rhs_handling++;
2810 if (access_has_children_p (lacc) && access_has_children_p (racc))
2812 gimple_stmt_iterator orig_gsi = *gsi;
2813 enum unscalarized_data_handling refreshed;
2815 if (lacc->grp_read && !lacc->grp_covered)
2816 refreshed = handle_unscalarized_data_in_subtree (racc, gsi);
2818 refreshed = SRA_UDH_NONE;
2820 load_assign_lhs_subreplacements (lacc, racc, lacc->offset,
2821 &orig_gsi, gsi, &refreshed);
2822 if (refreshed != SRA_UDH_RIGHT)
2825 unlink_stmt_vdef (*stmt);
2826 gsi_remove (&orig_gsi, true);
2827 sra_stats.deleted++;
2828 return SRA_AM_REMOVED;
2835 if (!racc->grp_to_be_replaced && !racc->grp_unscalarized_data)
2839 fprintf (dump_file, "Removing load: ");
2840 print_gimple_stmt (dump_file, *stmt, 0, 0);
2843 if (TREE_CODE (lhs) == SSA_NAME)
2845 rhs = get_repl_default_def_ssa_name (racc);
2846 if (!useless_type_conversion_p (TREE_TYPE (lhs),
2848 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
2849 TREE_TYPE (lhs), rhs);
2853 if (racc->first_child)
2854 generate_subtree_copies (racc->first_child, lhs,
2855 racc->offset, 0, 0, gsi,
2858 gcc_assert (*stmt == gsi_stmt (*gsi));
2859 unlink_stmt_vdef (*stmt);
2860 gsi_remove (gsi, true);
2861 sra_stats.deleted++;
2862 return SRA_AM_REMOVED;
2865 else if (racc->first_child)
2866 generate_subtree_copies (racc->first_child, lhs, racc->offset,
2867 0, 0, gsi, false, true, loc);
2869 if (access_has_children_p (lacc))
2870 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2871 0, 0, gsi, true, true, loc);
2875 /* This gimplification must be done after generate_subtree_copies, lest we
2876 insert the subtree copies in the middle of the gimplified sequence. */
2877 if (force_gimple_rhs)
2878 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
2879 true, GSI_SAME_STMT);
2880 if (gimple_assign_rhs1 (*stmt) != rhs)
2882 modify_this_stmt = true;
2883 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
2884 gcc_assert (*stmt == gsi_stmt (orig_gsi));
2887 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2890 /* Traverse the function body and all modifications as decided in
2891 analyze_all_variable_accesses. Return true iff the CFG has been
2895 sra_modify_function_body (void)
2897 bool cfg_changed = false;
2902 gimple_stmt_iterator gsi = gsi_start_bb (bb);
2903 while (!gsi_end_p (gsi))
2905 gimple stmt = gsi_stmt (gsi);
2906 enum assignment_mod_result assign_result;
2907 bool modified = false, deleted = false;
2911 switch (gimple_code (stmt))
2914 t = gimple_return_retval_ptr (stmt);
2915 if (*t != NULL_TREE)
2916 modified |= sra_modify_expr (t, &gsi, false);
2920 assign_result = sra_modify_assign (&stmt, &gsi);
2921 modified |= assign_result == SRA_AM_MODIFIED;
2922 deleted = assign_result == SRA_AM_REMOVED;
2926 /* Operands must be processed before the lhs. */
2927 for (i = 0; i < gimple_call_num_args (stmt); i++)
2929 t = gimple_call_arg_ptr (stmt, i);
2930 modified |= sra_modify_expr (t, &gsi, false);
2933 if (gimple_call_lhs (stmt))
2935 t = gimple_call_lhs_ptr (stmt);
2936 modified |= sra_modify_expr (t, &gsi, true);
2941 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
2943 t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
2944 modified |= sra_modify_expr (t, &gsi, false);
2946 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
2948 t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
2949 modified |= sra_modify_expr (t, &gsi, true);
2960 if (maybe_clean_eh_stmt (stmt)
2961 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2972 /* Generate statements initializing scalar replacements of parts of function
2976 initialize_parameter_reductions (void)
2978 gimple_stmt_iterator gsi;
2979 gimple_seq seq = NULL;
2982 for (parm = DECL_ARGUMENTS (current_function_decl);
2984 parm = DECL_CHAIN (parm))
2986 VEC (access_p, heap) *access_vec;
2987 struct access *access;
2989 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2991 access_vec = get_base_access_vector (parm);
2997 seq = gimple_seq_alloc ();
2998 gsi = gsi_start (seq);
3001 for (access = VEC_index (access_p, access_vec, 0);
3003 access = access->next_grp)
3004 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3005 EXPR_LOCATION (parm));
3009 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
3012 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
3013 it reveals there are components of some aggregates to be scalarized, it runs
3014 the required transformations. */
3016 perform_intra_sra (void)
3021 if (!find_var_candidates ())
3024 if (!scan_function ())
3027 if (!analyze_all_variable_accesses ())
3030 if (sra_modify_function_body ())
3031 ret = TODO_update_ssa | TODO_cleanup_cfg;
3033 ret = TODO_update_ssa;
3034 initialize_parameter_reductions ();
3036 statistics_counter_event (cfun, "Scalar replacements created",
3037 sra_stats.replacements);
3038 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3039 statistics_counter_event (cfun, "Subtree copy stmts",
3040 sra_stats.subtree_copies);
3041 statistics_counter_event (cfun, "Subreplacement stmts",
3042 sra_stats.subreplacements);
3043 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3044 statistics_counter_event (cfun, "Separate LHS and RHS handling",
3045 sra_stats.separate_lhs_rhs_handling);
3048 sra_deinitialize ();
3052 /* Perform early intraprocedural SRA. */
3054 early_intra_sra (void)
3056 sra_mode = SRA_MODE_EARLY_INTRA;
3057 return perform_intra_sra ();
3060 /* Perform "late" intraprocedural SRA. */
3062 late_intra_sra (void)
3064 sra_mode = SRA_MODE_INTRA;
3065 return perform_intra_sra ();
3070 gate_intra_sra (void)
3072 return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3076 struct gimple_opt_pass pass_sra_early =
3081 gate_intra_sra, /* gate */
3082 early_intra_sra, /* execute */
3085 0, /* static_pass_number */
3086 TV_TREE_SRA, /* tv_id */
3087 PROP_cfg | PROP_ssa, /* properties_required */
3088 0, /* properties_provided */
3089 0, /* properties_destroyed */
3090 0, /* todo_flags_start */
3094 | TODO_verify_ssa /* todo_flags_finish */
3098 struct gimple_opt_pass pass_sra =
3103 gate_intra_sra, /* gate */
3104 late_intra_sra, /* execute */
3107 0, /* static_pass_number */
3108 TV_TREE_SRA, /* tv_id */
3109 PROP_cfg | PROP_ssa, /* properties_required */
3110 0, /* properties_provided */
3111 0, /* properties_destroyed */
3112 TODO_update_address_taken, /* todo_flags_start */
3116 | TODO_verify_ssa /* todo_flags_finish */
3121 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3125 is_unused_scalar_param (tree parm)
3128 return (is_gimple_reg (parm)
3129 && (!(name = gimple_default_def (cfun, parm))
3130 || has_zero_uses (name)));
3133 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3134 examine whether there are any direct or otherwise infeasible ones. If so,
3135 return true, otherwise return false. PARM must be a gimple register with a
3136 non-NULL default definition. */
3139 ptr_parm_has_direct_uses (tree parm)
3141 imm_use_iterator ui;
3143 tree name = gimple_default_def (cfun, parm);
3146 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3149 use_operand_p use_p;
3151 if (is_gimple_debug (stmt))
3154 /* Valid uses include dereferences on the lhs and the rhs. */
3155 if (gimple_has_lhs (stmt))
3157 tree lhs = gimple_get_lhs (stmt);
3158 while (handled_component_p (lhs))
3159 lhs = TREE_OPERAND (lhs, 0);
3160 if (TREE_CODE (lhs) == MEM_REF
3161 && TREE_OPERAND (lhs, 0) == name
3162 && integer_zerop (TREE_OPERAND (lhs, 1))
3163 && types_compatible_p (TREE_TYPE (lhs),
3164 TREE_TYPE (TREE_TYPE (name))))
3167 if (gimple_assign_single_p (stmt))
3169 tree rhs = gimple_assign_rhs1 (stmt);
3170 while (handled_component_p (rhs))
3171 rhs = TREE_OPERAND (rhs, 0);
3172 if (TREE_CODE (rhs) == MEM_REF
3173 && TREE_OPERAND (rhs, 0) == name
3174 && integer_zerop (TREE_OPERAND (rhs, 1))
3175 && types_compatible_p (TREE_TYPE (rhs),
3176 TREE_TYPE (TREE_TYPE (name))))
3179 else if (is_gimple_call (stmt))
3182 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3184 tree arg = gimple_call_arg (stmt, i);
3185 while (handled_component_p (arg))
3186 arg = TREE_OPERAND (arg, 0);
3187 if (TREE_CODE (arg) == MEM_REF
3188 && TREE_OPERAND (arg, 0) == name
3189 && integer_zerop (TREE_OPERAND (arg, 1))
3190 && types_compatible_p (TREE_TYPE (arg),
3191 TREE_TYPE (TREE_TYPE (name))))
3196 /* If the number of valid uses does not match the number of
3197 uses in this stmt there is an unhandled use. */
3198 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
3205 BREAK_FROM_IMM_USE_STMT (ui);
3211 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3212 them in candidate_bitmap. Note that these do not necessarily include
3213 parameter which are unused and thus can be removed. Return true iff any
3214 such candidate has been found. */
3217 find_param_candidates (void)
3223 for (parm = DECL_ARGUMENTS (current_function_decl);
3225 parm = DECL_CHAIN (parm))
3227 tree type = TREE_TYPE (parm);
3231 if (TREE_THIS_VOLATILE (parm)
3232 || TREE_ADDRESSABLE (parm)
3233 || (!is_gimple_reg_type (type) && is_va_list_type (type)))
3236 if (is_unused_scalar_param (parm))
3242 if (POINTER_TYPE_P (type))
3244 type = TREE_TYPE (type);
3246 if (TREE_CODE (type) == FUNCTION_TYPE
3247 || TYPE_VOLATILE (type)
3248 || (TREE_CODE (type) == ARRAY_TYPE
3249 && TYPE_NONALIASED_COMPONENT (type))
3250 || !is_gimple_reg (parm)
3251 || is_va_list_type (type)
3252 || ptr_parm_has_direct_uses (parm))
3255 else if (!AGGREGATE_TYPE_P (type))
3258 if (!COMPLETE_TYPE_P (type)
3259 || !host_integerp (TYPE_SIZE (type), 1)
3260 || tree_low_cst (TYPE_SIZE (type), 1) == 0
3261 || (AGGREGATE_TYPE_P (type)
3262 && type_internals_preclude_sra_p (type)))
3265 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3267 if (dump_file && (dump_flags & TDF_DETAILS))
3269 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3270 print_generic_expr (dump_file, parm, 0);
3271 fprintf (dump_file, "\n");
3275 func_param_count = count;
3279 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3283 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3286 struct access *repr = (struct access *) data;
3288 repr->grp_maybe_modified = 1;
3292 /* Analyze what representatives (in linked lists accessible from
3293 REPRESENTATIVES) can be modified by side effects of statements in the
3294 current function. */
3297 analyze_modified_params (VEC (access_p, heap) *representatives)
3301 for (i = 0; i < func_param_count; i++)
3303 struct access *repr;
3305 for (repr = VEC_index (access_p, representatives, i);
3307 repr = repr->next_grp)
3309 struct access *access;
3313 if (no_accesses_p (repr))
3315 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3316 || repr->grp_maybe_modified)
3319 ao_ref_init (&ar, repr->expr);
3320 visited = BITMAP_ALLOC (NULL);
3321 for (access = repr; access; access = access->next_sibling)
3323 /* All accesses are read ones, otherwise grp_maybe_modified would
3324 be trivially set. */
3325 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3326 mark_maybe_modified, repr, &visited);
3327 if (repr->grp_maybe_modified)
3330 BITMAP_FREE (visited);
3335 /* Propagate distances in bb_dereferences in the opposite direction than the
3336 control flow edges, in each step storing the maximum of the current value
3337 and the minimum of all successors. These steps are repeated until the table
3338 stabilizes. Note that BBs which might terminate the functions (according to
3339 final_bbs bitmap) never updated in this way. */
3342 propagate_dereference_distances (void)
3344 VEC (basic_block, heap) *queue;
3347 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3348 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3351 VEC_quick_push (basic_block, queue, bb);
3355 while (!VEC_empty (basic_block, queue))
3359 bool change = false;
3362 bb = VEC_pop (basic_block, queue);
3365 if (bitmap_bit_p (final_bbs, bb->index))
3368 for (i = 0; i < func_param_count; i++)
3370 int idx = bb->index * func_param_count + i;
3372 HOST_WIDE_INT inh = 0;
3374 FOR_EACH_EDGE (e, ei, bb->succs)
3376 int succ_idx = e->dest->index * func_param_count + i;
3378 if (e->src == EXIT_BLOCK_PTR)
3384 inh = bb_dereferences [succ_idx];
3386 else if (bb_dereferences [succ_idx] < inh)
3387 inh = bb_dereferences [succ_idx];
3390 if (!first && bb_dereferences[idx] < inh)
3392 bb_dereferences[idx] = inh;
3397 if (change && !bitmap_bit_p (final_bbs, bb->index))
3398 FOR_EACH_EDGE (e, ei, bb->preds)
3403 e->src->aux = e->src;
3404 VEC_quick_push (basic_block, queue, e->src);
3408 VEC_free (basic_block, heap, queue);
3411 /* Dump a dereferences TABLE with heading STR to file F. */
3414 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3418 fprintf (dump_file, str);
3419 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3421 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3422 if (bb != EXIT_BLOCK_PTR)
3425 for (i = 0; i < func_param_count; i++)
3427 int idx = bb->index * func_param_count + i;
3428 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3433 fprintf (dump_file, "\n");
3436 /* Determine what (parts of) parameters passed by reference that are not
3437 assigned to are not certainly dereferenced in this function and thus the
3438 dereferencing cannot be safely moved to the caller without potentially
3439 introducing a segfault. Mark such REPRESENTATIVES as
3440 grp_not_necessarilly_dereferenced.
3442 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3443 part is calculated rather than simple booleans are calculated for each
3444 pointer parameter to handle cases when only a fraction of the whole
3445 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3448 The maximum dereference distances for each pointer parameter and BB are
3449 already stored in bb_dereference. This routine simply propagates these
3450 values upwards by propagate_dereference_distances and then compares the
3451 distances of individual parameters in the ENTRY BB to the equivalent
3452 distances of each representative of a (fraction of a) parameter. */
3455 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3459 if (dump_file && (dump_flags & TDF_DETAILS))
3460 dump_dereferences_table (dump_file,
3461 "Dereference table before propagation:\n",
3464 propagate_dereference_distances ();
3466 if (dump_file && (dump_flags & TDF_DETAILS))
3467 dump_dereferences_table (dump_file,
3468 "Dereference table after propagation:\n",
3471 for (i = 0; i < func_param_count; i++)
3473 struct access *repr = VEC_index (access_p, representatives, i);
3474 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3476 if (!repr || no_accesses_p (repr))
3481 if ((repr->offset + repr->size) > bb_dereferences[idx])
3482 repr->grp_not_necessarilly_dereferenced = 1;
3483 repr = repr->next_grp;
3489 /* Return the representative access for the parameter declaration PARM if it is
3490 a scalar passed by reference which is not written to and the pointer value
3491 is not used directly. Thus, if it is legal to dereference it in the caller
3492 and we can rule out modifications through aliases, such parameter should be
3493 turned into one passed by value. Return NULL otherwise. */
3495 static struct access *
3496 unmodified_by_ref_scalar_representative (tree parm)
3498 int i, access_count;
3499 struct access *repr;
3500 VEC (access_p, heap) *access_vec;
3502 access_vec = get_base_access_vector (parm);
3503 gcc_assert (access_vec);
3504 repr = VEC_index (access_p, access_vec, 0);
3507 repr->group_representative = repr;
3509 access_count = VEC_length (access_p, access_vec);
3510 for (i = 1; i < access_count; i++)
3512 struct access *access = VEC_index (access_p, access_vec, i);
3515 access->group_representative = repr;
3516 access->next_sibling = repr->next_sibling;
3517 repr->next_sibling = access;
3521 repr->grp_scalar_ptr = 1;
3525 /* Return true iff this access precludes IPA-SRA of the parameter it is
3529 access_precludes_ipa_sra_p (struct access *access)
3531 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3532 is incompatible assign in a call statement (and possibly even in asm
3533 statements). This can be relaxed by using a new temporary but only for
3534 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3535 intraprocedural SRA we deal with this by keeping the old aggregate around,
3536 something we cannot do in IPA-SRA.) */
3538 && (is_gimple_call (access->stmt)
3539 || gimple_code (access->stmt) == GIMPLE_ASM))
3546 /* Sort collected accesses for parameter PARM, identify representatives for
3547 each accessed region and link them together. Return NULL if there are
3548 different but overlapping accesses, return the special ptr value meaning
3549 there are no accesses for this parameter if that is the case and return the
3550 first representative otherwise. Set *RO_GRP if there is a group of accesses
3551 with only read (i.e. no write) accesses. */
3553 static struct access *
3554 splice_param_accesses (tree parm, bool *ro_grp)
3556 int i, j, access_count, group_count;
3557 int agg_size, total_size = 0;
3558 struct access *access, *res, **prev_acc_ptr = &res;
3559 VEC (access_p, heap) *access_vec;
3561 access_vec = get_base_access_vector (parm);
3563 return &no_accesses_representant;
3564 access_count = VEC_length (access_p, access_vec);
3566 VEC_qsort (access_p, access_vec, compare_access_positions);
3571 while (i < access_count)
3575 access = VEC_index (access_p, access_vec, i);
3576 modification = access->write;
3577 if (access_precludes_ipa_sra_p (access))
3579 a1_alias_type = reference_alias_ptr_type (access->expr);
3581 /* Access is about to become group representative unless we find some
3582 nasty overlap which would preclude us from breaking this parameter
3586 while (j < access_count)
3588 struct access *ac2 = VEC_index (access_p, access_vec, j);
3589 if (ac2->offset != access->offset)
3591 /* All or nothing law for parameters. */
3592 if (access->offset + access->size > ac2->offset)
3597 else if (ac2->size != access->size)
3600 if (access_precludes_ipa_sra_p (ac2)
3601 || (ac2->type != access->type
3602 && (TREE_ADDRESSABLE (ac2->type)
3603 || TREE_ADDRESSABLE (access->type)))
3604 || (reference_alias_ptr_type (ac2->expr) != a1_alias_type))
3607 modification |= ac2->write;
3608 ac2->group_representative = access;
3609 ac2->next_sibling = access->next_sibling;
3610 access->next_sibling = ac2;
3615 access->grp_maybe_modified = modification;
3618 *prev_acc_ptr = access;
3619 prev_acc_ptr = &access->next_grp;
3620 total_size += access->size;
3624 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3625 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3627 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3628 if (total_size >= agg_size)
3631 gcc_assert (group_count > 0);
3635 /* Decide whether parameters with representative accesses given by REPR should
3636 be reduced into components. */
3639 decide_one_param_reduction (struct access *repr)
3641 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3646 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3647 gcc_assert (cur_parm_size > 0);
3649 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3652 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3657 agg_size = cur_parm_size;
3663 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3664 print_generic_expr (dump_file, parm, 0);
3665 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3666 for (acc = repr; acc; acc = acc->next_grp)
3667 dump_access (dump_file, acc, true);
3671 new_param_count = 0;
3673 for (; repr; repr = repr->next_grp)
3675 gcc_assert (parm == repr->base);
3677 /* Taking the address of a non-addressable field is verboten. */
3678 if (by_ref && repr->non_addressable)
3681 if (!by_ref || (!repr->grp_maybe_modified
3682 && !repr->grp_not_necessarilly_dereferenced))
3683 total_size += repr->size;
3685 total_size += cur_parm_size;
3690 gcc_assert (new_param_count > 0);
3692 if (optimize_function_for_size_p (cfun))
3693 parm_size_limit = cur_parm_size;
3695 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3698 if (total_size < agg_size
3699 && total_size <= parm_size_limit)
3702 fprintf (dump_file, " ....will be split into %i components\n",
3704 return new_param_count;
3710 /* The order of the following enums is important, we need to do extra work for
3711 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3712 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3713 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3715 /* Identify representatives of all accesses to all candidate parameters for
3716 IPA-SRA. Return result based on what representatives have been found. */
3718 static enum ipa_splicing_result
3719 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3721 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3723 struct access *repr;
3725 *representatives = VEC_alloc (access_p, heap, func_param_count);
3727 for (parm = DECL_ARGUMENTS (current_function_decl);
3729 parm = DECL_CHAIN (parm))
3731 if (is_unused_scalar_param (parm))
3733 VEC_quick_push (access_p, *representatives,
3734 &no_accesses_representant);
3735 if (result == NO_GOOD_ACCESS)
3736 result = UNUSED_PARAMS;
3738 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3739 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3740 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3742 repr = unmodified_by_ref_scalar_representative (parm);
3743 VEC_quick_push (access_p, *representatives, repr);
3745 result = UNMODIF_BY_REF_ACCESSES;
3747 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3749 bool ro_grp = false;
3750 repr = splice_param_accesses (parm, &ro_grp);
3751 VEC_quick_push (access_p, *representatives, repr);
3753 if (repr && !no_accesses_p (repr))
3755 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3758 result = UNMODIF_BY_REF_ACCESSES;
3759 else if (result < MODIF_BY_REF_ACCESSES)
3760 result = MODIF_BY_REF_ACCESSES;
3762 else if (result < BY_VAL_ACCESSES)
3763 result = BY_VAL_ACCESSES;
3765 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3766 result = UNUSED_PARAMS;
3769 VEC_quick_push (access_p, *representatives, NULL);
3772 if (result == NO_GOOD_ACCESS)
3774 VEC_free (access_p, heap, *representatives);
3775 *representatives = NULL;
3776 return NO_GOOD_ACCESS;
3782 /* Return the index of BASE in PARMS. Abort if it is not found. */
3785 get_param_index (tree base, VEC(tree, heap) *parms)
3789 len = VEC_length (tree, parms);
3790 for (i = 0; i < len; i++)
3791 if (VEC_index (tree, parms, i) == base)
3796 /* Convert the decisions made at the representative level into compact
3797 parameter adjustments. REPRESENTATIVES are pointers to first
3798 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3799 final number of adjustments. */
3801 static ipa_parm_adjustment_vec
3802 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3803 int adjustments_count)
3805 VEC (tree, heap) *parms;
3806 ipa_parm_adjustment_vec adjustments;
3810 gcc_assert (adjustments_count > 0);
3811 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3812 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3813 parm = DECL_ARGUMENTS (current_function_decl);
3814 for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm))
3816 struct access *repr = VEC_index (access_p, representatives, i);
3818 if (!repr || no_accesses_p (repr))
3820 struct ipa_parm_adjustment *adj;
3822 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3823 memset (adj, 0, sizeof (*adj));
3824 adj->base_index = get_param_index (parm, parms);
3827 adj->copy_param = 1;
3829 adj->remove_param = 1;
3833 struct ipa_parm_adjustment *adj;
3834 int index = get_param_index (parm, parms);
3836 for (; repr; repr = repr->next_grp)
3838 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3839 memset (adj, 0, sizeof (*adj));
3840 gcc_assert (repr->base == parm);
3841 adj->base_index = index;
3842 adj->base = repr->base;
3843 adj->type = repr->type;
3844 adj->alias_ptr_type = reference_alias_ptr_type (repr->expr);
3845 adj->offset = repr->offset;
3846 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3847 && (repr->grp_maybe_modified
3848 || repr->grp_not_necessarilly_dereferenced));
3853 VEC_free (tree, heap, parms);
3857 /* Analyze the collected accesses and produce a plan what to do with the
3858 parameters in the form of adjustments, NULL meaning nothing. */
3860 static ipa_parm_adjustment_vec
3861 analyze_all_param_acesses (void)
3863 enum ipa_splicing_result repr_state;
3864 bool proceed = false;
3865 int i, adjustments_count = 0;
3866 VEC (access_p, heap) *representatives;
3867 ipa_parm_adjustment_vec adjustments;
3869 repr_state = splice_all_param_accesses (&representatives);
3870 if (repr_state == NO_GOOD_ACCESS)
3873 /* If there are any parameters passed by reference which are not modified
3874 directly, we need to check whether they can be modified indirectly. */
3875 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3877 analyze_caller_dereference_legality (representatives);
3878 analyze_modified_params (representatives);
3881 for (i = 0; i < func_param_count; i++)
3883 struct access *repr = VEC_index (access_p, representatives, i);
3885 if (repr && !no_accesses_p (repr))
3887 if (repr->grp_scalar_ptr)
3889 adjustments_count++;
3890 if (repr->grp_not_necessarilly_dereferenced
3891 || repr->grp_maybe_modified)
3892 VEC_replace (access_p, representatives, i, NULL);
3896 sra_stats.scalar_by_ref_to_by_val++;
3901 int new_components = decide_one_param_reduction (repr);
3903 if (new_components == 0)
3905 VEC_replace (access_p, representatives, i, NULL);
3906 adjustments_count++;
3910 adjustments_count += new_components;
3911 sra_stats.aggregate_params_reduced++;
3912 sra_stats.param_reductions_created += new_components;
3919 if (no_accesses_p (repr))
3922 sra_stats.deleted_unused_parameters++;
3924 adjustments_count++;
3928 if (!proceed && dump_file)
3929 fprintf (dump_file, "NOT proceeding to change params.\n");
3932 adjustments = turn_representatives_into_adjustments (representatives,
3937 VEC_free (access_p, heap, representatives);
3941 /* If a parameter replacement identified by ADJ does not yet exist in the form
3942 of declaration, create it and record it, otherwise return the previously
3946 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3949 if (!adj->new_ssa_base)
3951 char *pretty_name = make_fancy_name (adj->base);
3953 repl = create_tmp_reg (TREE_TYPE (adj->base), "ISR");
3954 DECL_NAME (repl) = get_identifier (pretty_name);
3955 obstack_free (&name_obstack, pretty_name);
3958 add_referenced_var (repl);
3959 adj->new_ssa_base = repl;
3962 repl = adj->new_ssa_base;
3966 /* Find the first adjustment for a particular parameter BASE in a vector of
3967 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3970 static struct ipa_parm_adjustment *
3971 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3975 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3976 for (i = 0; i < len; i++)
3978 struct ipa_parm_adjustment *adj;
3980 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3981 if (!adj->copy_param && adj->base == base)
3988 /* If the statement STMT defines an SSA_NAME of a parameter which is to be
3989 removed because its value is not used, replace the SSA_NAME with a one
3990 relating to a created VAR_DECL together all of its uses and return true.
3991 ADJUSTMENTS is a pointer to an adjustments vector. */
3994 replace_removed_params_ssa_names (gimple stmt,
3995 ipa_parm_adjustment_vec adjustments)
3997 struct ipa_parm_adjustment *adj;
3998 tree lhs, decl, repl, name;
4000 if (gimple_code (stmt) == GIMPLE_PHI)
4001 lhs = gimple_phi_result (stmt);
4002 else if (is_gimple_assign (stmt))
4003 lhs = gimple_assign_lhs (stmt);
4004 else if (is_gimple_call (stmt))
4005 lhs = gimple_call_lhs (stmt);
4009 if (TREE_CODE (lhs) != SSA_NAME)
4011 decl = SSA_NAME_VAR (lhs);
4012 if (TREE_CODE (decl) != PARM_DECL)
4015 adj = get_adjustment_for_base (adjustments, decl);
4019 repl = get_replaced_param_substitute (adj);
4020 name = make_ssa_name (repl, stmt);
4024 fprintf (dump_file, "replacing an SSA name of a removed param ");
4025 print_generic_expr (dump_file, lhs, 0);
4026 fprintf (dump_file, " with ");
4027 print_generic_expr (dump_file, name, 0);
4028 fprintf (dump_file, "\n");
4031 if (is_gimple_assign (stmt))
4032 gimple_assign_set_lhs (stmt, name);
4033 else if (is_gimple_call (stmt))
4034 gimple_call_set_lhs (stmt, name);
4036 gimple_phi_set_result (stmt, name);
4038 replace_uses_by (lhs, name);
4039 release_ssa_name (lhs);
4043 /* If the expression *EXPR should be replaced by a reduction of a parameter, do
4044 so. ADJUSTMENTS is a pointer to a vector of adjustments. CONVERT
4045 specifies whether the function should care about type incompatibility the
4046 current and new expressions. If it is false, the function will leave
4047 incompatibility issues to the caller. Return true iff the expression
4051 sra_ipa_modify_expr (tree *expr, bool convert,
4052 ipa_parm_adjustment_vec adjustments)
4055 struct ipa_parm_adjustment *adj, *cand = NULL;
4056 HOST_WIDE_INT offset, size, max_size;
4059 len = VEC_length (ipa_parm_adjustment_t, adjustments);
4061 if (TREE_CODE (*expr) == BIT_FIELD_REF
4062 || TREE_CODE (*expr) == IMAGPART_EXPR
4063 || TREE_CODE (*expr) == REALPART_EXPR)
4065 expr = &TREE_OPERAND (*expr, 0);
4069 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
4070 if (!base || size == -1 || max_size == -1)
4073 if (TREE_CODE (base) == MEM_REF)
4075 offset += mem_ref_offset (base).low * BITS_PER_UNIT;
4076 base = TREE_OPERAND (base, 0);
4079 base = get_ssa_base_param (base);
4080 if (!base || TREE_CODE (base) != PARM_DECL)
4083 for (i = 0; i < len; i++)
4085 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
4087 if (adj->base == base &&
4088 (adj->offset == offset || adj->remove_param))
4094 if (!cand || cand->copy_param || cand->remove_param)
4098 src = build_simple_mem_ref (cand->reduction);
4100 src = cand->reduction;
4102 if (dump_file && (dump_flags & TDF_DETAILS))
4104 fprintf (dump_file, "About to replace expr ");
4105 print_generic_expr (dump_file, *expr, 0);
4106 fprintf (dump_file, " with ");
4107 print_generic_expr (dump_file, src, 0);
4108 fprintf (dump_file, "\n");
4111 if (convert && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
4113 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
4121 /* If the statement pointed to by STMT_PTR contains any expressions that need
4122 to replaced with a different one as noted by ADJUSTMENTS, do so. Handle any
4123 potential type incompatibilities (GSI is used to accommodate conversion
4124 statements and must point to the statement). Return true iff the statement
4128 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi,
4129 ipa_parm_adjustment_vec adjustments)
4131 gimple stmt = *stmt_ptr;
4132 tree *lhs_p, *rhs_p;
4135 if (!gimple_assign_single_p (stmt))
4138 rhs_p = gimple_assign_rhs1_ptr (stmt);
4139 lhs_p = gimple_assign_lhs_ptr (stmt);
4141 any = sra_ipa_modify_expr (rhs_p, false, adjustments);
4142 any |= sra_ipa_modify_expr (lhs_p, false, adjustments);
4145 tree new_rhs = NULL_TREE;
4147 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
4149 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
4151 /* V_C_Es of constructors can cause trouble (PR 42714). */
4152 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
4153 *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
4155 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
4158 new_rhs = fold_build1_loc (gimple_location (stmt),
4159 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
4162 else if (REFERENCE_CLASS_P (*rhs_p)
4163 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
4164 && !is_gimple_reg (*lhs_p))
4165 /* This can happen when an assignment in between two single field
4166 structures is turned into an assignment in between two pointers to
4167 scalars (PR 42237). */
4172 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
4173 true, GSI_SAME_STMT);
4175 gimple_assign_set_rhs_from_tree (gsi, tmp);
4184 /* Traverse the function body and all modifications as described in
4185 ADJUSTMENTS. Return true iff the CFG has been changed. */
4188 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments)
4190 bool cfg_changed = false;
4195 gimple_stmt_iterator gsi;
4197 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4198 replace_removed_params_ssa_names (gsi_stmt (gsi), adjustments);
4200 gsi = gsi_start_bb (bb);
4201 while (!gsi_end_p (gsi))
4203 gimple stmt = gsi_stmt (gsi);
4204 bool modified = false;
4208 switch (gimple_code (stmt))
4211 t = gimple_return_retval_ptr (stmt);
4212 if (*t != NULL_TREE)
4213 modified |= sra_ipa_modify_expr (t, true, adjustments);
4217 modified |= sra_ipa_modify_assign (&stmt, &gsi, adjustments);
4218 modified |= replace_removed_params_ssa_names (stmt, adjustments);
4222 /* Operands must be processed before the lhs. */
4223 for (i = 0; i < gimple_call_num_args (stmt); i++)
4225 t = gimple_call_arg_ptr (stmt, i);
4226 modified |= sra_ipa_modify_expr (t, true, adjustments);
4229 if (gimple_call_lhs (stmt))
4231 t = gimple_call_lhs_ptr (stmt);
4232 modified |= sra_ipa_modify_expr (t, false, adjustments);
4233 modified |= replace_removed_params_ssa_names (stmt,
4239 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
4241 t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
4242 modified |= sra_ipa_modify_expr (t, true, adjustments);
4244 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
4246 t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
4247 modified |= sra_ipa_modify_expr (t, false, adjustments);
4258 if (maybe_clean_eh_stmt (stmt)
4259 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
4269 /* Call gimple_debug_bind_reset_value on all debug statements describing
4270 gimple register parameters that are being removed or replaced. */
4273 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
4277 len = VEC_length (ipa_parm_adjustment_t, adjustments);
4278 for (i = 0; i < len; i++)
4280 struct ipa_parm_adjustment *adj;
4281 imm_use_iterator ui;
4285 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
4286 if (adj->copy_param || !is_gimple_reg (adj->base))
4288 name = gimple_default_def (cfun, adj->base);
4291 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
4293 /* All other users must have been removed by
4294 ipa_sra_modify_function_body. */
4295 gcc_assert (is_gimple_debug (stmt));
4296 gimple_debug_bind_reset_value (stmt);
4302 /* Return true iff all callers have at least as many actual arguments as there
4303 are formal parameters in the current function. */
4306 all_callers_have_enough_arguments_p (struct cgraph_node *node)
4308 struct cgraph_edge *cs;
4309 for (cs = node->callers; cs; cs = cs->next_caller)
4310 if (!callsite_has_enough_arguments_p (cs->call_stmt))
4317 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
4320 convert_callers (struct cgraph_node *node, tree old_decl,
4321 ipa_parm_adjustment_vec adjustments)
4323 tree old_cur_fndecl = current_function_decl;
4324 struct cgraph_edge *cs;
4325 basic_block this_block;
4326 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
4328 for (cs = node->callers; cs; cs = cs->next_caller)
4330 current_function_decl = cs->caller->decl;
4331 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
4334 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
4335 cs->caller->uid, cs->callee->uid,
4336 cgraph_node_name (cs->caller),
4337 cgraph_node_name (cs->callee));
4339 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
4344 for (cs = node->callers; cs; cs = cs->next_caller)
4345 if (bitmap_set_bit (recomputed_callers, cs->caller->uid))
4346 compute_inline_parameters (cs->caller);
4347 BITMAP_FREE (recomputed_callers);
4349 current_function_decl = old_cur_fndecl;
4351 if (!encountered_recursive_call)
4354 FOR_EACH_BB (this_block)
4356 gimple_stmt_iterator gsi;
4358 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4360 gimple stmt = gsi_stmt (gsi);
4362 if (gimple_code (stmt) != GIMPLE_CALL)
4364 call_fndecl = gimple_call_fndecl (stmt);
4365 if (call_fndecl == old_decl)
4368 fprintf (dump_file, "Adjusting recursive call");
4369 gimple_call_set_fndecl (stmt, node->decl);
4370 ipa_modify_call_arguments (NULL, stmt, adjustments);
4378 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4379 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */
4382 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4384 struct cgraph_node *new_node;
4385 struct cgraph_edge *cs;
4387 VEC (cgraph_edge_p, heap) * redirect_callers;
4391 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
4393 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
4394 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
4395 VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
4397 rebuild_cgraph_edges ();
4399 current_function_decl = NULL_TREE;
4401 new_node = cgraph_function_versioning (node, redirect_callers, NULL, NULL,
4402 NULL, NULL, "isra");
4403 current_function_decl = new_node->decl;
4404 push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
4406 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
4407 cfg_changed = ipa_sra_modify_function_body (adjustments);
4408 sra_ipa_reset_debug_stmts (adjustments);
4409 convert_callers (new_node, node->decl, adjustments);
4410 cgraph_make_node_local (new_node);
4414 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4415 attributes, return true otherwise. NODE is the cgraph node of the current
4419 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4421 if (!cgraph_node_can_be_local_p (node))
4424 fprintf (dump_file, "Function not local to this compilation unit.\n");
4428 if (!tree_versionable_function_p (node->decl))
4431 fprintf (dump_file, "Function is not versionable.\n");
4435 if (DECL_VIRTUAL_P (current_function_decl))
4438 fprintf (dump_file, "Function is a virtual method.\n");
4442 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
4443 && node->global.size >= MAX_INLINE_INSNS_AUTO)
4446 fprintf (dump_file, "Function too big to be made truly local.\n");
4454 "Function has no callers in this compilation unit.\n");
4461 fprintf (dump_file, "Function uses stdarg. \n");
4465 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
4471 /* Perform early interprocedural SRA. */
4474 ipa_early_sra (void)
4476 struct cgraph_node *node = cgraph_node (current_function_decl);
4477 ipa_parm_adjustment_vec adjustments;
4480 if (!ipa_sra_preliminary_function_checks (node))
4484 sra_mode = SRA_MODE_EARLY_IPA;
4486 if (!find_param_candidates ())
4489 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
4493 if (!all_callers_have_enough_arguments_p (node))
4496 fprintf (dump_file, "There are callers with insufficient number of "
4501 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
4503 * last_basic_block_for_function (cfun));
4504 final_bbs = BITMAP_ALLOC (NULL);
4507 if (encountered_apply_args)
4510 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4514 if (encountered_unchangable_recursive_call)
4517 fprintf (dump_file, "Function calls itself with insufficient "
4518 "number of arguments.\n");
4522 adjustments = analyze_all_param_acesses ();
4526 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4528 if (modify_function (node, adjustments))
4529 ret = TODO_update_ssa | TODO_cleanup_cfg;
4531 ret = TODO_update_ssa;
4532 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4534 statistics_counter_event (cfun, "Unused parameters deleted",
4535 sra_stats.deleted_unused_parameters);
4536 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4537 sra_stats.scalar_by_ref_to_by_val);
4538 statistics_counter_event (cfun, "Aggregate parameters broken up",
4539 sra_stats.aggregate_params_reduced);
4540 statistics_counter_event (cfun, "Aggregate parameter components created",
4541 sra_stats.param_reductions_created);
4544 BITMAP_FREE (final_bbs);
4545 free (bb_dereferences);
4547 sra_deinitialize ();
4551 /* Return if early ipa sra shall be performed. */
4553 ipa_early_sra_gate (void)
4555 return flag_ipa_sra && dbg_cnt (eipa_sra);
4558 struct gimple_opt_pass pass_early_ipa_sra =
4562 "eipa_sra", /* name */
4563 ipa_early_sra_gate, /* gate */
4564 ipa_early_sra, /* execute */
4567 0, /* static_pass_number */
4568 TV_IPA_SRA, /* tv_id */
4569 0, /* properties_required */
4570 0, /* properties_provided */
4571 0, /* properties_destroyed */
4572 0, /* todo_flags_start */
4573 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */