1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
82 #include "tree-flow.h"
84 #include "diagnostic.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 /* Enumeration of all aggregate reductions we can do. */
93 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
94 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
95 SRA_MODE_INTRA }; /* late intraprocedural SRA */
97 /* Global variable describing which aggregate reduction we are performing at
99 static enum sra_mode sra_mode;
103 /* ACCESS represents each access to an aggregate variable (as a whole or a
104 part). It can also represent a group of accesses that refer to exactly the
105 same fragment of an aggregate (i.e. those that have exactly the same offset
106 and size). Such representatives for a single aggregate, once determined,
107 are linked in a linked list and have the group fields set.
109 Moreover, when doing intraprocedural SRA, a tree is built from those
110 representatives (by the means of first_child and next_sibling pointers), in
111 which all items in a subtree are "within" the root, i.e. their offset is
112 greater or equal to offset of the root and offset+size is smaller or equal
113 to offset+size of the root. Children of an access are sorted by offset.
115 Note that accesses to parts of vector and complex number types always
116 represented by an access to the whole complex number or a vector. It is a
117 duty of the modifying functions to replace them appropriately. */
121 /* Values returned by `get_ref_base_and_extent' for each component reference
122 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
123 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
124 HOST_WIDE_INT offset;
128 /* Expression. It is context dependent so do not use it to create new
129 expressions to access the original aggregate. See PR 42154 for a
135 /* The statement this access belongs to. */
138 /* Next group representative for this aggregate. */
139 struct access *next_grp;
141 /* Pointer to the group representative. Pointer to itself if the struct is
142 the representative. */
143 struct access *group_representative;
145 /* If this access has any children (in terms of the definition above), this
146 points to the first one. */
147 struct access *first_child;
149 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
150 described above. In IPA-SRA this is a pointer to the next access
151 belonging to the same group (having the same representative). */
152 struct access *next_sibling;
154 /* Pointers to the first and last element in the linked list of assign
156 struct assign_link *first_link, *last_link;
158 /* Pointer to the next access in the work queue. */
159 struct access *next_queued;
161 /* Replacement variable for this access "region." Never to be accessed
162 directly, always only by the means of get_access_replacement() and only
163 when grp_to_be_replaced flag is set. */
164 tree replacement_decl;
166 /* Is this particular access write access? */
169 /* Is this access an artificial one created to scalarize some record
171 unsigned total_scalarization : 1;
173 /* Is this access currently in the work queue? */
174 unsigned grp_queued : 1;
176 /* Does this group contain a write access? This flag is propagated down the
178 unsigned grp_write : 1;
180 /* Does this group contain a read access? This flag is propagated down the
182 unsigned grp_read : 1;
184 /* Other passes of the analysis use this bit to make function
185 analyze_access_subtree create scalar replacements for this group if
187 unsigned grp_hint : 1;
189 /* Is the subtree rooted in this access fully covered by scalar
191 unsigned grp_covered : 1;
193 /* If set to true, this access and all below it in an access tree must not be
195 unsigned grp_unscalarizable_region : 1;
197 /* Whether data have been written to parts of the aggregate covered by this
198 access which is not to be scalarized. This flag is propagated up in the
200 unsigned grp_unscalarized_data : 1;
202 /* Does this access and/or group contain a write access through a
204 unsigned grp_partial_lhs : 1;
206 /* Set when a scalar replacement should be created for this variable. We do
207 the decision and creation at different places because create_tmp_var
208 cannot be called from within FOR_EACH_REFERENCED_VAR. */
209 unsigned grp_to_be_replaced : 1;
211 /* Is it possible that the group refers to data which might be (directly or
212 otherwise) modified? */
213 unsigned grp_maybe_modified : 1;
215 /* Set when this is a representative of a pointer to scalar (i.e. by
216 reference) parameter which we consider for turning into a plain scalar
217 (i.e. a by value parameter). */
218 unsigned grp_scalar_ptr : 1;
220 /* Set when we discover that this pointer is not safe to dereference in the
222 unsigned grp_not_necessarilly_dereferenced : 1;
225 typedef struct access *access_p;
227 DEF_VEC_P (access_p);
228 DEF_VEC_ALLOC_P (access_p, heap);
230 /* Alloc pool for allocating access structures. */
231 static alloc_pool access_pool;
233 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
234 are used to propagate subaccesses from rhs to lhs as long as they don't
235 conflict with what is already there. */
238 struct access *lacc, *racc;
239 struct assign_link *next;
242 /* Alloc pool for allocating assign link structures. */
243 static alloc_pool link_pool;
245 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
246 static struct pointer_map_t *base_access_vec;
248 /* Bitmap of candidates. */
249 static bitmap candidate_bitmap;
251 /* Bitmap of candidates which we should try to entirely scalarize away and
252 those which cannot be (because they are and need be used as a whole). */
253 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
255 /* Obstack for creation of fancy names. */
256 static struct obstack name_obstack;
258 /* Head of a linked list of accesses that need to have its subaccesses
259 propagated to their assignment counterparts. */
260 static struct access *work_queue_head;
262 /* Number of parameters of the analyzed function when doing early ipa SRA. */
263 static int func_param_count;
265 /* scan_function sets the following to true if it encounters a call to
266 __builtin_apply_args. */
267 static bool encountered_apply_args;
269 /* Set by scan_function when it finds a recursive call. */
270 static bool encountered_recursive_call;
272 /* Set by scan_function when it finds a recursive call with less actual
273 arguments than formal parameters.. */
274 static bool encountered_unchangable_recursive_call;
276 /* This is a table in which for each basic block and parameter there is a
277 distance (offset + size) in that parameter which is dereferenced and
278 accessed in that BB. */
279 static HOST_WIDE_INT *bb_dereferences;
280 /* Bitmap of BBs that can cause the function to "stop" progressing by
281 returning, throwing externally, looping infinitely or calling a function
282 which might abort etc.. */
283 static bitmap final_bbs;
285 /* Representative of no accesses at all. */
286 static struct access no_accesses_representant;
288 /* Predicate to test the special value. */
291 no_accesses_p (struct access *access)
293 return access == &no_accesses_representant;
296 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
297 representative fields are dumped, otherwise those which only describe the
298 individual access are. */
302 /* Number of processed aggregates is readily available in
303 analyze_all_variable_accesses and so is not stored here. */
305 /* Number of created scalar replacements. */
308 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
312 /* Number of statements created by generate_subtree_copies. */
315 /* Number of statements created by load_assign_lhs_subreplacements. */
318 /* Number of times sra_modify_assign has deleted a statement. */
321 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
322 RHS reparately due to type conversions or nonexistent matching
324 int separate_lhs_rhs_handling;
326 /* Number of parameters that were removed because they were unused. */
327 int deleted_unused_parameters;
329 /* Number of scalars passed as parameters by reference that have been
330 converted to be passed by value. */
331 int scalar_by_ref_to_by_val;
333 /* Number of aggregate parameters that were replaced by one or more of their
335 int aggregate_params_reduced;
337 /* Numbber of components created when splitting aggregate parameters. */
338 int param_reductions_created;
342 dump_access (FILE *f, struct access *access, bool grp)
344 fprintf (f, "access { ");
345 fprintf (f, "base = (%d)'", DECL_UID (access->base));
346 print_generic_expr (f, access->base, 0);
347 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
348 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
349 fprintf (f, ", expr = ");
350 print_generic_expr (f, access->expr, 0);
351 fprintf (f, ", type = ");
352 print_generic_expr (f, access->type, 0);
354 fprintf (f, ", grp_write = %d, total_scalarization = %d, "
355 "grp_read = %d, grp_hint = %d, "
356 "grp_covered = %d, grp_unscalarizable_region = %d, "
357 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
358 "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
359 "grp_not_necessarilly_dereferenced = %d\n",
360 access->grp_write, access->total_scalarization,
361 access->grp_read, access->grp_hint,
362 access->grp_covered, access->grp_unscalarizable_region,
363 access->grp_unscalarized_data, access->grp_partial_lhs,
364 access->grp_to_be_replaced, access->grp_maybe_modified,
365 access->grp_not_necessarilly_dereferenced);
367 fprintf (f, ", write = %d, total_scalarization = %d, "
368 "grp_partial_lhs = %d\n",
369 access->write, access->total_scalarization,
370 access->grp_partial_lhs);
373 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
376 dump_access_tree_1 (FILE *f, struct access *access, int level)
382 for (i = 0; i < level; i++)
383 fputs ("* ", dump_file);
385 dump_access (f, access, true);
387 if (access->first_child)
388 dump_access_tree_1 (f, access->first_child, level + 1);
390 access = access->next_sibling;
395 /* Dump all access trees for a variable, given the pointer to the first root in
399 dump_access_tree (FILE *f, struct access *access)
401 for (; access; access = access->next_grp)
402 dump_access_tree_1 (f, access, 0);
405 /* Return true iff ACC is non-NULL and has subaccesses. */
408 access_has_children_p (struct access *acc)
410 return acc && acc->first_child;
413 /* Return a vector of pointers to accesses for the variable given in BASE or
414 NULL if there is none. */
416 static VEC (access_p, heap) *
417 get_base_access_vector (tree base)
421 slot = pointer_map_contains (base_access_vec, base);
425 return *(VEC (access_p, heap) **) slot;
428 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
429 in ACCESS. Return NULL if it cannot be found. */
431 static struct access *
432 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
435 while (access && (access->offset != offset || access->size != size))
437 struct access *child = access->first_child;
439 while (child && (child->offset + child->size <= offset))
440 child = child->next_sibling;
447 /* Return the first group representative for DECL or NULL if none exists. */
449 static struct access *
450 get_first_repr_for_decl (tree base)
452 VEC (access_p, heap) *access_vec;
454 access_vec = get_base_access_vector (base);
458 return VEC_index (access_p, access_vec, 0);
461 /* Find an access representative for the variable BASE and given OFFSET and
462 SIZE. Requires that access trees have already been built. Return NULL if
463 it cannot be found. */
465 static struct access *
466 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
469 struct access *access;
471 access = get_first_repr_for_decl (base);
472 while (access && (access->offset + access->size <= offset))
473 access = access->next_grp;
477 return find_access_in_subtree (access, offset, size);
480 /* Add LINK to the linked list of assign links of RACC. */
482 add_link_to_rhs (struct access *racc, struct assign_link *link)
484 gcc_assert (link->racc == racc);
486 if (!racc->first_link)
488 gcc_assert (!racc->last_link);
489 racc->first_link = link;
492 racc->last_link->next = link;
494 racc->last_link = link;
498 /* Move all link structures in their linked list in OLD_RACC to the linked list
501 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
503 if (!old_racc->first_link)
505 gcc_assert (!old_racc->last_link);
509 if (new_racc->first_link)
511 gcc_assert (!new_racc->last_link->next);
512 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
514 new_racc->last_link->next = old_racc->first_link;
515 new_racc->last_link = old_racc->last_link;
519 gcc_assert (!new_racc->last_link);
521 new_racc->first_link = old_racc->first_link;
522 new_racc->last_link = old_racc->last_link;
524 old_racc->first_link = old_racc->last_link = NULL;
527 /* Add ACCESS to the work queue (which is actually a stack). */
530 add_access_to_work_queue (struct access *access)
532 if (!access->grp_queued)
534 gcc_assert (!access->next_queued);
535 access->next_queued = work_queue_head;
536 access->grp_queued = 1;
537 work_queue_head = access;
541 /* Pop an access from the work queue, and return it, assuming there is one. */
543 static struct access *
544 pop_access_from_work_queue (void)
546 struct access *access = work_queue_head;
548 work_queue_head = access->next_queued;
549 access->next_queued = NULL;
550 access->grp_queued = 0;
555 /* Allocate necessary structures. */
558 sra_initialize (void)
560 candidate_bitmap = BITMAP_ALLOC (NULL);
561 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
562 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
563 gcc_obstack_init (&name_obstack);
564 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
565 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
566 base_access_vec = pointer_map_create ();
567 memset (&sra_stats, 0, sizeof (sra_stats));
568 encountered_apply_args = false;
569 encountered_recursive_call = false;
570 encountered_unchangable_recursive_call = false;
573 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
576 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
577 void *data ATTRIBUTE_UNUSED)
579 VEC (access_p, heap) *access_vec;
580 access_vec = (VEC (access_p, heap) *) *value;
581 VEC_free (access_p, heap, access_vec);
586 /* Deallocate all general structures. */
589 sra_deinitialize (void)
591 BITMAP_FREE (candidate_bitmap);
592 BITMAP_FREE (should_scalarize_away_bitmap);
593 BITMAP_FREE (cannot_scalarize_away_bitmap);
594 free_alloc_pool (access_pool);
595 free_alloc_pool (link_pool);
596 obstack_free (&name_obstack, NULL);
598 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
599 pointer_map_destroy (base_access_vec);
602 /* Remove DECL from candidates for SRA and write REASON to the dump file if
605 disqualify_candidate (tree decl, const char *reason)
607 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
609 if (dump_file && (dump_flags & TDF_DETAILS))
611 fprintf (dump_file, "! Disqualifying ");
612 print_generic_expr (dump_file, decl, 0);
613 fprintf (dump_file, " - %s\n", reason);
617 /* Return true iff the type contains a field or an element which does not allow
621 type_internals_preclude_sra_p (tree type)
626 switch (TREE_CODE (type))
630 case QUAL_UNION_TYPE:
631 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
632 if (TREE_CODE (fld) == FIELD_DECL)
634 tree ft = TREE_TYPE (fld);
636 if (TREE_THIS_VOLATILE (fld)
637 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
638 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
639 || !host_integerp (DECL_SIZE (fld), 1))
642 if (AGGREGATE_TYPE_P (ft)
643 && type_internals_preclude_sra_p (ft))
650 et = TREE_TYPE (type);
652 if (AGGREGATE_TYPE_P (et))
653 return type_internals_preclude_sra_p (et);
662 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
663 base variable if it is. Return T if it is not an SSA_NAME. */
666 get_ssa_base_param (tree t)
668 if (TREE_CODE (t) == SSA_NAME)
670 if (SSA_NAME_IS_DEFAULT_DEF (t))
671 return SSA_NAME_VAR (t);
678 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
679 belongs to, unless the BB has already been marked as a potentially
683 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
685 basic_block bb = gimple_bb (stmt);
686 int idx, parm_index = 0;
689 if (bitmap_bit_p (final_bbs, bb->index))
692 for (parm = DECL_ARGUMENTS (current_function_decl);
693 parm && parm != base;
694 parm = TREE_CHAIN (parm))
697 gcc_assert (parm_index < func_param_count);
699 idx = bb->index * func_param_count + parm_index;
700 if (bb_dereferences[idx] < dist)
701 bb_dereferences[idx] = dist;
704 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
705 the three fields. Also add it to the vector of accesses corresponding to
706 the base. Finally, return the new access. */
708 static struct access *
709 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
711 VEC (access_p, heap) *vec;
712 struct access *access;
715 access = (struct access *) pool_alloc (access_pool);
716 memset (access, 0, sizeof (struct access));
718 access->offset = offset;
721 slot = pointer_map_contains (base_access_vec, base);
723 vec = (VEC (access_p, heap) *) *slot;
725 vec = VEC_alloc (access_p, heap, 32);
727 VEC_safe_push (access_p, heap, vec, access);
729 *((struct VEC (access_p,heap) **)
730 pointer_map_insert (base_access_vec, base)) = vec;
735 /* Create and insert access for EXPR. Return created access, or NULL if it is
738 static struct access *
739 create_access (tree expr, gimple stmt, bool write)
741 struct access *access;
742 HOST_WIDE_INT offset, size, max_size;
744 bool ptr, unscalarizable_region = false;
746 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
748 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
750 base = get_ssa_base_param (TREE_OPERAND (base, 0));
758 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
761 if (sra_mode == SRA_MODE_EARLY_IPA)
763 if (size < 0 || size != max_size)
765 disqualify_candidate (base, "Encountered a variable sized access.");
768 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
770 disqualify_candidate (base,
771 "Encountered an acces not aligned to a byte.");
776 mark_parm_dereference (base, offset + size, stmt);
780 if (size != max_size)
783 unscalarizable_region = true;
787 disqualify_candidate (base, "Encountered an unconstrained access.");
792 access = create_access_1 (base, offset, size);
794 access->type = TREE_TYPE (expr);
795 access->write = write;
796 access->grp_unscalarizable_region = unscalarizable_region;
803 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
804 register types or (recursively) records with only these two kinds of
808 type_consists_of_records_p (tree type)
812 if (TREE_CODE (type) != RECORD_TYPE)
815 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
816 if (TREE_CODE (fld) == FIELD_DECL)
818 tree ft = TREE_TYPE (fld);
820 if (!is_gimple_reg_type (ft)
821 && !type_consists_of_records_p (ft))
827 /* Create total_scalarization accesses for all scalar type fields in DECL that
828 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE
829 must be the top-most VAR_DECL representing the variable, OFFSET must be the
830 offset of DECL within BASE. */
833 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset)
835 tree fld, decl_type = TREE_TYPE (decl);
837 for (fld = TYPE_FIELDS (decl_type); fld; fld = TREE_CHAIN (fld))
838 if (TREE_CODE (fld) == FIELD_DECL)
840 HOST_WIDE_INT pos = offset + int_bit_position (fld);
841 tree ft = TREE_TYPE (fld);
843 if (is_gimple_reg_type (ft))
845 struct access *access;
850 size = tree_low_cst (DECL_SIZE (fld), 1);
852 ok = build_ref_for_offset (&expr, TREE_TYPE (base), pos,
856 access = create_access_1 (base, pos, size);
859 access->total_scalarization = 1;
860 /* Accesses for intraprocedural SRA can have their stmt NULL. */
863 completely_scalarize_record (base, fld, pos);
868 /* Search the given tree for a declaration by skipping handled components and
869 exclude it from the candidates. */
872 disqualify_base_of_expr (tree t, const char *reason)
874 while (handled_component_p (t))
875 t = TREE_OPERAND (t, 0);
877 if (sra_mode == SRA_MODE_EARLY_IPA)
879 if (INDIRECT_REF_P (t))
880 t = TREE_OPERAND (t, 0);
881 t = get_ssa_base_param (t);
885 disqualify_candidate (t, reason);
888 /* Scan expression EXPR and create access structures for all accesses to
889 candidates for scalarization. Return the created access or NULL if none is
892 static struct access *
893 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
895 struct access *ret = NULL;
896 tree expr = *expr_ptr;
899 if (TREE_CODE (expr) == BIT_FIELD_REF
900 || TREE_CODE (expr) == IMAGPART_EXPR
901 || TREE_CODE (expr) == REALPART_EXPR)
903 expr = TREE_OPERAND (expr, 0);
909 /* We need to dive through V_C_Es in order to get the size of its parameter
910 and not the result type. Ada produces such statements. We are also
911 capable of handling the topmost V_C_E but not any of those buried in other
912 handled components. */
913 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
914 expr = TREE_OPERAND (expr, 0);
916 if (contains_view_convert_expr_p (expr))
918 disqualify_base_of_expr (expr, "V_C_E under a different handled "
923 switch (TREE_CODE (expr))
926 if (sra_mode != SRA_MODE_EARLY_IPA)
934 case ARRAY_RANGE_REF:
935 ret = create_access (expr, stmt, write);
942 if (write && partial_ref && ret)
943 ret->grp_partial_lhs = 1;
948 /* Callback of scan_function. Scan expression EXPR and create access
949 structures for all accesses to candidates for scalarization. Return true if
950 any access has been inserted. */
953 build_access_from_expr (tree *expr_ptr,
954 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
955 void *data ATTRIBUTE_UNUSED)
957 struct access *access;
959 access = build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write);
962 /* This means the aggregate is accesses as a whole in a way other than an
963 assign statement and thus cannot be removed even if we had a scalar
964 replacement for everything. */
965 if (cannot_scalarize_away_bitmap)
966 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
972 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
973 modes in which it matters, return true iff they have been disqualified. RHS
974 may be NULL, in that case ignore it. If we scalarize an aggregate in
975 intra-SRA we may need to add statements after each statement. This is not
976 possible if a statement unconditionally has to end the basic block. */
978 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
980 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
981 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
983 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
985 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
992 /* Result code for scan_assign callback for scan_function. */
993 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
994 SRA_SA_PROCESSED, /* stmt analyzed/changed */
995 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
998 /* Callback of scan_function. Scan expressions occuring in the statement
999 pointed to by STMT_EXPR, create access structures for all accesses to
1000 candidates for scalarization and remove those candidates which occur in
1001 statements or expressions that prevent them from being split apart. Return
1002 true if any access has been inserted. */
1004 static enum scan_assign_result
1005 build_accesses_from_assign (gimple *stmt_ptr,
1006 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
1007 void *data ATTRIBUTE_UNUSED)
1009 gimple stmt = *stmt_ptr;
1010 tree *lhs_ptr, *rhs_ptr;
1011 struct access *lacc, *racc;
1013 if (!gimple_assign_single_p (stmt))
1016 lhs_ptr = gimple_assign_lhs_ptr (stmt);
1017 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
1019 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
1022 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
1023 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
1025 if (should_scalarize_away_bitmap && racc && !is_gimple_reg_type (racc->type))
1026 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1029 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1030 && !lacc->grp_unscalarizable_region
1031 && !racc->grp_unscalarizable_region
1032 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
1033 /* FIXME: Turn the following line into an assert after PR 40058 is
1035 && lacc->size == racc->size
1036 && useless_type_conversion_p (lacc->type, racc->type))
1038 struct assign_link *link;
1040 link = (struct assign_link *) pool_alloc (link_pool);
1041 memset (link, 0, sizeof (struct assign_link));
1046 add_link_to_rhs (racc, link);
1049 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
1052 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1053 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1056 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1057 void *data ATTRIBUTE_UNUSED)
1060 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1065 /* Return true iff callsite CALL has at least as many actual arguments as there
1066 are formal parameters of the function currently processed by IPA-SRA. */
1069 callsite_has_enough_arguments_p (gimple call)
1071 return gimple_call_num_args (call) >= (unsigned) func_param_count;
1074 /* Scan function and look for interesting statements. Return true if any has
1075 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
1076 called on all expressions within statements except assign statements and
1077 those deemed entirely unsuitable for some reason (all operands in such
1078 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
1079 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
1080 called on assign statements and those call statements which have a lhs, it
1081 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
1082 pass and thus no statement is being modified. DATA is a pointer passed to
1083 all callbacks. If any single callback returns true, this function also
1084 returns true, otherwise it returns false. */
1087 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
1088 enum scan_assign_result (*scan_assign) (gimple *,
1089 gimple_stmt_iterator *,
1091 bool (*handle_ssa_defs)(gimple, void *),
1092 bool analysis_stage, void *data)
1094 gimple_stmt_iterator gsi;
1102 bool bb_changed = false;
1104 if (handle_ssa_defs)
1105 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1106 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
1108 gsi = gsi_start_bb (bb);
1109 while (!gsi_end_p (gsi))
1111 gimple stmt = gsi_stmt (gsi);
1112 enum scan_assign_result assign_result;
1113 bool any = false, deleted = false;
1115 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
1116 bitmap_set_bit (final_bbs, bb->index);
1117 switch (gimple_code (stmt))
1120 t = gimple_return_retval_ptr (stmt);
1121 if (*t != NULL_TREE)
1122 any |= scan_expr (t, &gsi, false, data);
1123 if (analysis_stage && final_bbs)
1124 bitmap_set_bit (final_bbs, bb->index);
1128 assign_result = scan_assign (&stmt, &gsi, data);
1129 any |= assign_result == SRA_SA_PROCESSED;
1130 deleted = assign_result == SRA_SA_REMOVED;
1131 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1132 any |= handle_ssa_defs (stmt, data);
1136 /* Operands must be processed before the lhs. */
1137 for (i = 0; i < gimple_call_num_args (stmt); i++)
1139 tree *argp = gimple_call_arg_ptr (stmt, i);
1140 any |= scan_expr (argp, &gsi, false, data);
1143 if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
1145 tree dest = gimple_call_fndecl (stmt);
1146 int flags = gimple_call_flags (stmt);
1150 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1151 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1152 encountered_apply_args = true;
1153 if (cgraph_get_node (dest)
1154 == cgraph_get_node (current_function_decl))
1156 encountered_recursive_call = true;
1157 if (!callsite_has_enough_arguments_p (stmt))
1158 encountered_unchangable_recursive_call = true;
1163 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1164 bitmap_set_bit (final_bbs, bb->index);
1167 if (gimple_call_lhs (stmt))
1169 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1171 || !disqualify_ops_if_throwing_stmt (stmt,
1174 any |= scan_expr (lhs_ptr, &gsi, true, data);
1175 if (handle_ssa_defs)
1176 any |= handle_ssa_defs (stmt, data);
1184 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1187 bitmap_set_bit (final_bbs, bb->index);
1189 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1191 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1192 any |= scan_expr (op, &gsi, false, data);
1194 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1196 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1197 any |= scan_expr (op, &gsi, true, data);
1209 if (!analysis_stage)
1213 maybe_clean_eh_stmt (stmt);
1224 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1225 gimple_purge_dead_eh_edges (bb);
1231 /* Helper of QSORT function. There are pointers to accesses in the array. An
1232 access is considered smaller than another if it has smaller offset or if the
1233 offsets are the same but is size is bigger. */
1236 compare_access_positions (const void *a, const void *b)
1238 const access_p *fp1 = (const access_p *) a;
1239 const access_p *fp2 = (const access_p *) b;
1240 const access_p f1 = *fp1;
1241 const access_p f2 = *fp2;
1243 if (f1->offset != f2->offset)
1244 return f1->offset < f2->offset ? -1 : 1;
1246 if (f1->size == f2->size)
1248 if (f1->type == f2->type)
1250 /* Put any non-aggregate type before any aggregate type. */
1251 else if (!is_gimple_reg_type (f1->type)
1252 && is_gimple_reg_type (f2->type))
1254 else if (is_gimple_reg_type (f1->type)
1255 && !is_gimple_reg_type (f2->type))
1257 /* Put any complex or vector type before any other scalar type. */
1258 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1259 && TREE_CODE (f1->type) != VECTOR_TYPE
1260 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1261 || TREE_CODE (f2->type) == VECTOR_TYPE))
1263 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1264 || TREE_CODE (f1->type) == VECTOR_TYPE)
1265 && TREE_CODE (f2->type) != COMPLEX_TYPE
1266 && TREE_CODE (f2->type) != VECTOR_TYPE)
1268 /* Put the integral type with the bigger precision first. */
1269 else if (INTEGRAL_TYPE_P (f1->type)
1270 && INTEGRAL_TYPE_P (f2->type))
1271 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1272 /* Put any integral type with non-full precision last. */
1273 else if (INTEGRAL_TYPE_P (f1->type)
1274 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1275 != TYPE_PRECISION (f1->type)))
1277 else if (INTEGRAL_TYPE_P (f2->type)
1278 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1279 != TYPE_PRECISION (f2->type)))
1281 /* Stabilize the sort. */
1282 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1285 /* We want the bigger accesses first, thus the opposite operator in the next
1287 return f1->size > f2->size ? -1 : 1;
1291 /* Append a name of the declaration to the name obstack. A helper function for
1295 make_fancy_decl_name (tree decl)
1299 tree name = DECL_NAME (decl);
1301 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1302 IDENTIFIER_LENGTH (name));
1305 sprintf (buffer, "D%u", DECL_UID (decl));
1306 obstack_grow (&name_obstack, buffer, strlen (buffer));
1310 /* Helper for make_fancy_name. */
1313 make_fancy_name_1 (tree expr)
1320 make_fancy_decl_name (expr);
1324 switch (TREE_CODE (expr))
1327 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1328 obstack_1grow (&name_obstack, '$');
1329 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1333 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1334 obstack_1grow (&name_obstack, '$');
1335 /* Arrays with only one element may not have a constant as their
1337 index = TREE_OPERAND (expr, 1);
1338 if (TREE_CODE (index) != INTEGER_CST)
1340 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1341 obstack_grow (&name_obstack, buffer, strlen (buffer));
1348 gcc_unreachable (); /* we treat these as scalars. */
1355 /* Create a human readable name for replacement variable of ACCESS. */
1358 make_fancy_name (tree expr)
1360 make_fancy_name_1 (expr);
1361 obstack_1grow (&name_obstack, '\0');
1362 return XOBFINISH (&name_obstack, char *);
1365 /* Helper function for build_ref_for_offset. */
1368 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1374 tree tr_size, index, minidx;
1375 HOST_WIDE_INT el_size;
1377 if (offset == 0 && exp_type
1378 && types_compatible_p (exp_type, type))
1381 switch (TREE_CODE (type))
1384 case QUAL_UNION_TYPE:
1386 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1388 HOST_WIDE_INT pos, size;
1389 tree expr, *expr_ptr;
1391 if (TREE_CODE (fld) != FIELD_DECL)
1394 pos = int_bit_position (fld);
1395 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1396 tr_size = DECL_SIZE (fld);
1397 if (!tr_size || !host_integerp (tr_size, 1))
1399 size = tree_low_cst (tr_size, 1);
1405 else if (pos > offset || (pos + size) <= offset)
1410 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1416 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1417 offset - pos, exp_type))
1427 tr_size = TYPE_SIZE (TREE_TYPE (type));
1428 if (!tr_size || !host_integerp (tr_size, 1))
1430 el_size = tree_low_cst (tr_size, 1);
1432 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1433 if (TREE_CODE (minidx) != INTEGER_CST)
1437 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1438 if (!integer_zerop (minidx))
1439 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1440 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1441 NULL_TREE, NULL_TREE);
1443 offset = offset % el_size;
1444 type = TREE_TYPE (type);
1459 /* Construct an expression that would reference a part of aggregate *EXPR of
1460 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1461 function only determines whether it can build such a reference without
1462 actually doing it, otherwise, the tree it points to is unshared first and
1463 then used as a base for furhter sub-references.
1465 FIXME: Eventually this should be replaced with
1466 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1467 minor rewrite of fold_stmt.
1471 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1472 tree exp_type, bool allow_ptr)
1474 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1477 *expr = unshare_expr (*expr);
1479 if (allow_ptr && POINTER_TYPE_P (type))
1481 type = TREE_TYPE (type);
1483 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1486 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1489 /* Return true iff TYPE is stdarg va_list type. */
1492 is_va_list_type (tree type)
1494 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1497 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1498 those with type which is suitable for scalarization. */
1501 find_var_candidates (void)
1504 referenced_var_iterator rvi;
1507 FOR_EACH_REFERENCED_VAR (var, rvi)
1509 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1511 type = TREE_TYPE (var);
1513 if (!AGGREGATE_TYPE_P (type)
1514 || needs_to_live_in_memory (var)
1515 || TREE_THIS_VOLATILE (var)
1516 || !COMPLETE_TYPE_P (type)
1517 || !host_integerp (TYPE_SIZE (type), 1)
1518 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1519 || type_internals_preclude_sra_p (type)
1520 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1521 we also want to schedule it rather late. Thus we ignore it in
1523 || (sra_mode == SRA_MODE_EARLY_INTRA
1524 && is_va_list_type (type)))
1527 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1529 if (dump_file && (dump_flags & TDF_DETAILS))
1531 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1532 print_generic_expr (dump_file, var, 0);
1533 fprintf (dump_file, "\n");
1541 /* Sort all accesses for the given variable, check for partial overlaps and
1542 return NULL if there are any. If there are none, pick a representative for
1543 each combination of offset and size and create a linked list out of them.
1544 Return the pointer to the first representative and make sure it is the first
1545 one in the vector of accesses. */
1547 static struct access *
1548 sort_and_splice_var_accesses (tree var)
1550 int i, j, access_count;
1551 struct access *res, **prev_acc_ptr = &res;
1552 VEC (access_p, heap) *access_vec;
1554 HOST_WIDE_INT low = -1, high = 0;
1556 access_vec = get_base_access_vector (var);
1559 access_count = VEC_length (access_p, access_vec);
1561 /* Sort by <OFFSET, SIZE>. */
1562 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1563 compare_access_positions);
1566 while (i < access_count)
1568 struct access *access = VEC_index (access_p, access_vec, i);
1569 bool grp_write = access->write;
1570 bool grp_read = !access->write;
1571 bool multiple_reads = false;
1572 bool total_scalarization = access->total_scalarization;
1573 bool grp_partial_lhs = access->grp_partial_lhs;
1574 bool first_scalar = is_gimple_reg_type (access->type);
1575 bool unscalarizable_region = access->grp_unscalarizable_region;
1577 if (first || access->offset >= high)
1580 low = access->offset;
1581 high = access->offset + access->size;
1583 else if (access->offset > low && access->offset + access->size > high)
1586 gcc_assert (access->offset >= low
1587 && access->offset + access->size <= high);
1590 while (j < access_count)
1592 struct access *ac2 = VEC_index (access_p, access_vec, j);
1593 if (ac2->offset != access->offset || ac2->size != access->size)
1600 multiple_reads = true;
1604 grp_partial_lhs |= ac2->grp_partial_lhs;
1605 unscalarizable_region |= ac2->grp_unscalarizable_region;
1606 total_scalarization |= ac2->total_scalarization;
1607 relink_to_new_repr (access, ac2);
1609 /* If there are both aggregate-type and scalar-type accesses with
1610 this combination of size and offset, the comparison function
1611 should have put the scalars first. */
1612 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1613 ac2->group_representative = access;
1619 access->group_representative = access;
1620 access->grp_write = grp_write;
1621 access->grp_read = grp_read;
1622 access->grp_hint = multiple_reads || total_scalarization;
1623 access->grp_partial_lhs = grp_partial_lhs;
1624 access->grp_unscalarizable_region = unscalarizable_region;
1625 if (access->first_link)
1626 add_access_to_work_queue (access);
1628 *prev_acc_ptr = access;
1629 prev_acc_ptr = &access->next_grp;
1632 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1636 /* Create a variable for the given ACCESS which determines the type, name and a
1637 few other properties. Return the variable declaration and store it also to
1638 ACCESS->replacement. */
1641 create_access_replacement (struct access *access)
1645 repl = create_tmp_var (access->type, "SR");
1647 add_referenced_var (repl);
1648 mark_sym_for_renaming (repl);
1650 if (!access->grp_partial_lhs
1651 && (TREE_CODE (access->type) == COMPLEX_TYPE
1652 || TREE_CODE (access->type) == VECTOR_TYPE))
1653 DECL_GIMPLE_REG_P (repl) = 1;
1655 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1656 DECL_ARTIFICIAL (repl) = 1;
1658 if (DECL_NAME (access->base)
1659 && !DECL_IGNORED_P (access->base)
1660 && !DECL_ARTIFICIAL (access->base))
1662 char *pretty_name = make_fancy_name (access->expr);
1664 DECL_NAME (repl) = get_identifier (pretty_name);
1665 obstack_free (&name_obstack, pretty_name);
1667 SET_DECL_DEBUG_EXPR (repl, access->expr);
1668 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1669 DECL_IGNORED_P (repl) = 0;
1672 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1673 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1677 fprintf (dump_file, "Created a replacement for ");
1678 print_generic_expr (dump_file, access->base, 0);
1679 fprintf (dump_file, " offset: %u, size: %u: ",
1680 (unsigned) access->offset, (unsigned) access->size);
1681 print_generic_expr (dump_file, repl, 0);
1682 fprintf (dump_file, "\n");
1684 sra_stats.replacements++;
1689 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1692 get_access_replacement (struct access *access)
1694 gcc_assert (access->grp_to_be_replaced);
1696 if (!access->replacement_decl)
1697 access->replacement_decl = create_access_replacement (access);
1698 return access->replacement_decl;
1701 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1702 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1703 to it is not "within" the root. */
1706 build_access_subtree (struct access **access)
1708 struct access *root = *access, *last_child = NULL;
1709 HOST_WIDE_INT limit = root->offset + root->size;
1711 *access = (*access)->next_grp;
1712 while (*access && (*access)->offset + (*access)->size <= limit)
1715 root->first_child = *access;
1717 last_child->next_sibling = *access;
1718 last_child = *access;
1720 build_access_subtree (access);
1724 /* Build a tree of access representatives, ACCESS is the pointer to the first
1725 one, others are linked in a list by the next_grp field. Decide about scalar
1726 replacements on the way, return true iff any are to be created. */
1729 build_access_trees (struct access *access)
1733 struct access *root = access;
1735 build_access_subtree (&access);
1736 root->next_grp = access;
1740 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1744 expr_with_var_bounded_array_refs_p (tree expr)
1746 while (handled_component_p (expr))
1748 if (TREE_CODE (expr) == ARRAY_REF
1749 && !host_integerp (array_ref_low_bound (expr), 0))
1751 expr = TREE_OPERAND (expr, 0);
1756 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1757 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1758 all sorts of access flags appropriately along the way, notably always ser
1759 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1762 analyze_access_subtree (struct access *root, bool allow_replacements,
1763 bool mark_read, bool mark_write)
1765 struct access *child;
1766 HOST_WIDE_INT limit = root->offset + root->size;
1767 HOST_WIDE_INT covered_to = root->offset;
1768 bool scalar = is_gimple_reg_type (root->type);
1769 bool hole = false, sth_created = false;
1770 bool direct_read = root->grp_read;
1773 root->grp_read = true;
1774 else if (root->grp_read)
1778 root->grp_write = true;
1779 else if (root->grp_write)
1782 if (root->grp_unscalarizable_region)
1783 allow_replacements = false;
1785 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1786 allow_replacements = false;
1788 for (child = root->first_child; child; child = child->next_sibling)
1790 if (!hole && child->offset < covered_to)
1793 covered_to += child->size;
1795 sth_created |= analyze_access_subtree (child, allow_replacements,
1796 mark_read, mark_write);
1798 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1799 hole |= !child->grp_covered;
1802 if (allow_replacements && scalar && !root->first_child
1804 || (direct_read && root->grp_write))
1805 /* We must not ICE later on when trying to build an access to the
1806 original data within the aggregate even when it is impossible to do in
1807 a defined way like in the PR 42703 testcase. Therefore we check
1808 pre-emptively here that we will be able to do that. */
1809 && build_ref_for_offset (NULL, TREE_TYPE (root->base), root->offset,
1812 if (dump_file && (dump_flags & TDF_DETAILS))
1814 fprintf (dump_file, "Marking ");
1815 print_generic_expr (dump_file, root->base, 0);
1816 fprintf (dump_file, " offset: %u, size: %u: ",
1817 (unsigned) root->offset, (unsigned) root->size);
1818 fprintf (dump_file, " to be replaced.\n");
1821 root->grp_to_be_replaced = 1;
1825 else if (covered_to < limit)
1828 if (sth_created && !hole)
1830 root->grp_covered = 1;
1833 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1834 root->grp_unscalarized_data = 1; /* not covered and written to */
1840 /* Analyze all access trees linked by next_grp by the means of
1841 analyze_access_subtree. */
1843 analyze_access_trees (struct access *access)
1849 if (analyze_access_subtree (access, true, false, false))
1851 access = access->next_grp;
1857 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1858 SIZE would conflict with an already existing one. If exactly such a child
1859 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1862 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1863 HOST_WIDE_INT size, struct access **exact_match)
1865 struct access *child;
1867 for (child = lacc->first_child; child; child = child->next_sibling)
1869 if (child->offset == norm_offset && child->size == size)
1871 *exact_match = child;
1875 if (child->offset < norm_offset + size
1876 && child->offset + child->size > norm_offset)
1883 /* Create a new child access of PARENT, with all properties just like MODEL
1884 except for its offset and with its grp_write false and grp_read true.
1885 Return the new access or NULL if it cannot be created. Note that this access
1886 is created long after all splicing and sorting, it's not located in any
1887 access vector and is automatically a representative of its group. */
1889 static struct access *
1890 create_artificial_child_access (struct access *parent, struct access *model,
1891 HOST_WIDE_INT new_offset)
1893 struct access *access;
1894 struct access **child;
1895 tree expr = parent->base;;
1897 gcc_assert (!model->grp_unscalarizable_region);
1899 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1900 model->type, false))
1903 access = (struct access *) pool_alloc (access_pool);
1904 memset (access, 0, sizeof (struct access));
1905 access->base = parent->base;
1906 access->expr = expr;
1907 access->offset = new_offset;
1908 access->size = model->size;
1909 access->type = model->type;
1910 access->grp_write = true;
1911 access->grp_read = false;
1913 child = &parent->first_child;
1914 while (*child && (*child)->offset < new_offset)
1915 child = &(*child)->next_sibling;
1917 access->next_sibling = *child;
1924 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1925 true if any new subaccess was created. Additionally, if RACC is a scalar
1926 access but LACC is not, change the type of the latter, if possible. */
1929 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1931 struct access *rchild;
1932 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1935 if (is_gimple_reg_type (lacc->type)
1936 || lacc->grp_unscalarizable_region
1937 || racc->grp_unscalarizable_region)
1940 if (!lacc->first_child && !racc->first_child
1941 && is_gimple_reg_type (racc->type))
1943 tree t = lacc->base;
1945 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1949 lacc->type = racc->type;
1954 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1956 struct access *new_acc = NULL;
1957 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1959 if (rchild->grp_unscalarizable_region)
1962 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1967 rchild->grp_hint = 1;
1968 new_acc->grp_hint |= new_acc->grp_read;
1969 if (rchild->first_child)
1970 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1975 /* If a (part of) a union field is on the RHS of an assignment, it can
1976 have sub-accesses which do not make sense on the LHS (PR 40351).
1977 Check that this is not the case. */
1978 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1979 rchild->type, false))
1982 rchild->grp_hint = 1;
1983 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1987 if (racc->first_child)
1988 propagate_subaccesses_across_link (new_acc, rchild);
1995 /* Propagate all subaccesses across assignment links. */
1998 propagate_all_subaccesses (void)
2000 while (work_queue_head)
2002 struct access *racc = pop_access_from_work_queue ();
2003 struct assign_link *link;
2005 gcc_assert (racc->first_link);
2007 for (link = racc->first_link; link; link = link->next)
2009 struct access *lacc = link->lacc;
2011 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2013 lacc = lacc->group_representative;
2014 if (propagate_subaccesses_across_link (lacc, racc)
2015 && lacc->first_link)
2016 add_access_to_work_queue (lacc);
2021 /* Go through all accesses collected throughout the (intraprocedural) analysis
2022 stage, exclude overlapping ones, identify representatives and build trees
2023 out of them, making decisions about scalarization on the way. Return true
2024 iff there are any to-be-scalarized variables after this stage. */
2027 analyze_all_variable_accesses (void)
2030 bitmap tmp = BITMAP_ALLOC (NULL);
2032 unsigned i, max_total_scalarization_size;
2034 max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2035 * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2037 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2038 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2039 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2041 tree var = referenced_var (i);
2043 if (TREE_CODE (var) == VAR_DECL
2044 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2045 <= max_total_scalarization_size)
2046 && type_consists_of_records_p (TREE_TYPE (var)))
2048 completely_scalarize_record (var, var, 0);
2049 if (dump_file && (dump_flags & TDF_DETAILS))
2051 fprintf (dump_file, "Will attempt to totally scalarize ");
2052 print_generic_expr (dump_file, var, 0);
2053 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2058 bitmap_copy (tmp, candidate_bitmap);
2059 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2061 tree var = referenced_var (i);
2062 struct access *access;
2064 access = sort_and_splice_var_accesses (var);
2066 build_access_trees (access);
2068 disqualify_candidate (var,
2069 "No or inhibitingly overlapping accesses.");
2072 propagate_all_subaccesses ();
2074 bitmap_copy (tmp, candidate_bitmap);
2075 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2077 tree var = referenced_var (i);
2078 struct access *access = get_first_repr_for_decl (var);
2080 if (analyze_access_trees (access))
2083 if (dump_file && (dump_flags & TDF_DETAILS))
2085 fprintf (dump_file, "\nAccess trees for ");
2086 print_generic_expr (dump_file, var, 0);
2087 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2088 dump_access_tree (dump_file, access);
2089 fprintf (dump_file, "\n");
2093 disqualify_candidate (var, "No scalar replacements to be created.");
2100 statistics_counter_event (cfun, "Scalarized aggregates", res);
2107 /* Return true iff a reference statement into aggregate AGG can be built for
2108 every single to-be-replaced accesses that is a child of ACCESS, its sibling
2109 or a child of its sibling. TOP_OFFSET is the offset from the processed
2110 access subtree that has to be subtracted from offset of each access. */
2113 ref_expr_for_all_replacements_p (struct access *access, tree agg,
2114 HOST_WIDE_INT top_offset)
2118 if (access->grp_to_be_replaced
2119 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
2120 access->offset - top_offset,
2121 access->type, false))
2124 if (access->first_child
2125 && !ref_expr_for_all_replacements_p (access->first_child, agg,
2129 access = access->next_sibling;
2136 /* Generate statements copying scalar replacements of accesses within a subtree
2137 into or out of AGG. ACCESS is the first child of the root of the subtree to
2138 be processed. AGG is an aggregate type expression (can be a declaration but
2139 does not have to be, it can for example also be an indirect_ref).
2140 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2141 from offsets of individual accesses to get corresponding offsets for AGG.
2142 If CHUNK_SIZE is non-null, copy only replacements in the interval
2143 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2144 statement iterator used to place the new statements. WRITE should be true
2145 when the statements should write from AGG to the replacement and false if
2146 vice versa. if INSERT_AFTER is true, new statements will be added after the
2147 current statement in GSI, they will be added before the statement
2151 generate_subtree_copies (struct access *access, tree agg,
2152 HOST_WIDE_INT top_offset,
2153 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2154 gimple_stmt_iterator *gsi, bool write,
2161 if (chunk_size && access->offset >= start_offset + chunk_size)
2164 if (access->grp_to_be_replaced
2166 || access->offset + access->size > start_offset))
2168 tree repl = get_access_replacement (access);
2172 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
2173 access->offset - top_offset,
2174 access->type, false);
2175 gcc_assert (ref_found);
2179 if (access->grp_partial_lhs)
2180 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2182 insert_after ? GSI_NEW_STMT
2184 stmt = gimple_build_assign (repl, expr);
2188 TREE_NO_WARNING (repl) = 1;
2189 if (access->grp_partial_lhs)
2190 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2192 insert_after ? GSI_NEW_STMT
2194 stmt = gimple_build_assign (expr, repl);
2198 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2200 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2202 sra_stats.subtree_copies++;
2205 if (access->first_child)
2206 generate_subtree_copies (access->first_child, agg, top_offset,
2207 start_offset, chunk_size, gsi,
2208 write, insert_after);
2210 access = access->next_sibling;
2215 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2216 the root of the subtree to be processed. GSI is the statement iterator used
2217 for inserting statements which are added after the current statement if
2218 INSERT_AFTER is true or before it otherwise. */
2221 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2225 struct access *child;
2227 if (access->grp_to_be_replaced)
2231 stmt = gimple_build_assign (get_access_replacement (access),
2232 fold_convert (access->type,
2233 integer_zero_node));
2235 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2237 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2241 for (child = access->first_child; child; child = child->next_sibling)
2242 init_subtree_with_zero (child, gsi, insert_after);
2245 /* Search for an access representative for the given expression EXPR and
2246 return it or NULL if it cannot be found. */
2248 static struct access *
2249 get_access_for_expr (tree expr)
2251 HOST_WIDE_INT offset, size, max_size;
2254 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2255 a different size than the size of its argument and we need the latter
2257 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2258 expr = TREE_OPERAND (expr, 0);
2260 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2261 if (max_size == -1 || !DECL_P (base))
2264 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2267 return get_var_base_offset_size_access (base, offset, max_size);
2270 /* Callback for scan_function. Replace the expression EXPR with a scalar
2271 replacement if there is one and generate other statements to do type
2272 conversion or subtree copying if necessary. GSI is used to place newly
2273 created statements, WRITE is true if the expression is being written to (it
2274 is on a LHS of a statement or output in an assembly statement). */
2277 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2278 void *data ATTRIBUTE_UNUSED)
2280 struct access *access;
2283 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2286 expr = &TREE_OPERAND (*expr, 0);
2291 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2292 expr = &TREE_OPERAND (*expr, 0);
2293 access = get_access_for_expr (*expr);
2296 type = TREE_TYPE (*expr);
2298 if (access->grp_to_be_replaced)
2300 tree repl = get_access_replacement (access);
2301 /* If we replace a non-register typed access simply use the original
2302 access expression to extract the scalar component afterwards.
2303 This happens if scalarizing a function return value or parameter
2304 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2305 gcc.c-torture/compile/20011217-1.c.
2307 We also want to use this when accessing a complex or vector which can
2308 be accessed as a different type too, potentially creating a need for
2309 type conversion (see PR42196) and when scalarized unions are involved
2310 in assembler statements (see PR42398). */
2311 if (!useless_type_conversion_p (type, access->type))
2313 tree ref = access->base;
2316 ok = build_ref_for_offset (&ref, TREE_TYPE (ref),
2317 access->offset, access->type, false);
2324 if (access->grp_partial_lhs)
2325 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2326 false, GSI_NEW_STMT);
2327 stmt = gimple_build_assign (repl, ref);
2328 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2334 if (access->grp_partial_lhs)
2335 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2336 true, GSI_SAME_STMT);
2337 stmt = gimple_build_assign (ref, repl);
2338 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2346 if (access->first_child)
2348 HOST_WIDE_INT start_offset, chunk_size;
2350 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2351 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2353 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2354 start_offset = access->offset
2355 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2358 start_offset = chunk_size = 0;
2360 generate_subtree_copies (access->first_child, access->base, 0,
2361 start_offset, chunk_size, gsi, write, write);
2366 /* Where scalar replacements of the RHS have been written to when a replacement
2367 of a LHS of an assigments cannot be direclty loaded from a replacement of
2369 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2370 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2371 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2373 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2374 base aggregate if there are unscalarized data or directly to LHS
2377 static enum unscalarized_data_handling
2378 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2379 gimple_stmt_iterator *gsi)
2381 if (top_racc->grp_unscalarized_data)
2383 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2385 return SRA_UDH_RIGHT;
2389 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2390 0, 0, gsi, false, false);
2391 return SRA_UDH_LEFT;
2396 /* Try to generate statements to load all sub-replacements in an access
2397 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2398 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2399 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2400 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2401 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2402 the rhs top aggregate has already been refreshed by contents of its scalar
2403 reductions and is set to true if this function has to do it. */
2406 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2407 HOST_WIDE_INT left_offset,
2408 HOST_WIDE_INT right_offset,
2409 gimple_stmt_iterator *old_gsi,
2410 gimple_stmt_iterator *new_gsi,
2411 enum unscalarized_data_handling *refreshed,
2414 location_t loc = EXPR_LOCATION (lacc->expr);
2417 if (lacc->grp_to_be_replaced)
2419 struct access *racc;
2420 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2424 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2425 if (racc && racc->grp_to_be_replaced)
2427 rhs = get_access_replacement (racc);
2428 if (!useless_type_conversion_p (lacc->type, racc->type))
2429 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2433 /* No suitable access on the right hand side, need to load from
2434 the aggregate. See if we have to update it first... */
2435 if (*refreshed == SRA_UDH_NONE)
2436 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2439 if (*refreshed == SRA_UDH_LEFT)
2444 repl_found = build_ref_for_offset (&rhs, TREE_TYPE (rhs),
2445 lacc->offset, lacc->type,
2447 gcc_assert (repl_found);
2453 rhs = top_racc->base;
2454 repl_found = build_ref_for_offset (&rhs,
2455 TREE_TYPE (top_racc->base),
2456 offset, lacc->type, false);
2457 gcc_assert (repl_found);
2461 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2462 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2464 sra_stats.subreplacements++;
2466 else if (*refreshed == SRA_UDH_NONE
2467 && lacc->grp_read && !lacc->grp_covered)
2468 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2471 if (lacc->first_child)
2472 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2473 left_offset, right_offset,
2474 old_gsi, new_gsi, refreshed, lhs);
2475 lacc = lacc->next_sibling;
2480 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2481 to the assignment and GSI is the statement iterator pointing at it. Returns
2482 the same values as sra_modify_assign. */
2484 static enum scan_assign_result
2485 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2487 tree lhs = gimple_assign_lhs (*stmt);
2490 acc = get_access_for_expr (lhs);
2494 if (VEC_length (constructor_elt,
2495 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2497 /* I have never seen this code path trigger but if it can happen the
2498 following should handle it gracefully. */
2499 if (access_has_children_p (acc))
2500 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2502 return SRA_SA_PROCESSED;
2505 if (acc->grp_covered)
2507 init_subtree_with_zero (acc, gsi, false);
2508 unlink_stmt_vdef (*stmt);
2509 gsi_remove (gsi, true);
2510 return SRA_SA_REMOVED;
2514 init_subtree_with_zero (acc, gsi, true);
2515 return SRA_SA_PROCESSED;
2520 /* Callback of scan_function to process assign statements. It examines both
2521 sides of the statement, replaces them with a scalare replacement if there is
2522 one and generating copying of replacements if scalarized aggregates have been
2523 used in the assignment. STMT is a pointer to the assign statement, GSI is
2524 used to hold generated statements for type conversions and subtree
2527 static enum scan_assign_result
2528 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2529 void *data ATTRIBUTE_UNUSED)
2531 struct access *lacc, *racc;
2533 bool modify_this_stmt = false;
2534 bool force_gimple_rhs = false;
2535 location_t loc = gimple_location (*stmt);
2536 gimple_stmt_iterator orig_gsi = *gsi;
2538 if (!gimple_assign_single_p (*stmt))
2540 lhs = gimple_assign_lhs (*stmt);
2541 rhs = gimple_assign_rhs1 (*stmt);
2543 if (TREE_CODE (rhs) == CONSTRUCTOR)
2544 return sra_modify_constructor_assign (stmt, gsi);
2546 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2547 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2548 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2550 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2552 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2554 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2557 lacc = get_access_for_expr (lhs);
2558 racc = get_access_for_expr (rhs);
2562 if (lacc && lacc->grp_to_be_replaced)
2564 lhs = get_access_replacement (lacc);
2565 gimple_assign_set_lhs (*stmt, lhs);
2566 modify_this_stmt = true;
2567 if (lacc->grp_partial_lhs)
2568 force_gimple_rhs = true;
2572 if (racc && racc->grp_to_be_replaced)
2574 rhs = get_access_replacement (racc);
2575 modify_this_stmt = true;
2576 if (racc->grp_partial_lhs)
2577 force_gimple_rhs = true;
2581 if (modify_this_stmt)
2583 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2585 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2586 ??? This should move to fold_stmt which we simply should
2587 call after building a VIEW_CONVERT_EXPR here. */
2588 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2589 && !access_has_children_p (lacc))
2592 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2593 TREE_TYPE (rhs), false))
2596 gimple_assign_set_lhs (*stmt, expr);
2599 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2600 && !access_has_children_p (racc))
2603 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2604 TREE_TYPE (lhs), false))
2607 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2609 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2610 if (is_gimple_reg_type (TREE_TYPE (lhs))
2611 && TREE_CODE (lhs) != SSA_NAME)
2612 force_gimple_rhs = true;
2617 /* From this point on, the function deals with assignments in between
2618 aggregates when at least one has scalar reductions of some of its
2619 components. There are three possible scenarios: Both the LHS and RHS have
2620 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2622 In the first case, we would like to load the LHS components from RHS
2623 components whenever possible. If that is not possible, we would like to
2624 read it directly from the RHS (after updating it by storing in it its own
2625 components). If there are some necessary unscalarized data in the LHS,
2626 those will be loaded by the original assignment too. If neither of these
2627 cases happen, the original statement can be removed. Most of this is done
2628 by load_assign_lhs_subreplacements.
2630 In the second case, we would like to store all RHS scalarized components
2631 directly into LHS and if they cover the aggregate completely, remove the
2632 statement too. In the third case, we want the LHS components to be loaded
2633 directly from the RHS (DSE will remove the original statement if it
2636 This is a bit complex but manageable when types match and when unions do
2637 not cause confusion in a way that we cannot really load a component of LHS
2638 from the RHS or vice versa (the access representing this level can have
2639 subaccesses that are accessible only through a different union field at a
2640 higher level - different from the one used in the examined expression).
2643 Therefore, I specially handle a fourth case, happening when there is a
2644 specific type cast or it is impossible to locate a scalarized subaccess on
2645 the other side of the expression. If that happens, I simply "refresh" the
2646 RHS by storing in it is scalarized components leave the original statement
2647 there to do the copying and then load the scalar replacements of the LHS.
2648 This is what the first branch does. */
2650 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2651 || (access_has_children_p (racc)
2652 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2653 || (access_has_children_p (lacc)
2654 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2656 if (access_has_children_p (racc))
2657 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2659 if (access_has_children_p (lacc))
2660 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2662 sra_stats.separate_lhs_rhs_handling++;
2666 if (access_has_children_p (lacc) && access_has_children_p (racc))
2668 gimple_stmt_iterator orig_gsi = *gsi;
2669 enum unscalarized_data_handling refreshed;
2671 if (lacc->grp_read && !lacc->grp_covered)
2672 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2674 refreshed = SRA_UDH_NONE;
2676 load_assign_lhs_subreplacements (lacc->first_child, racc,
2677 lacc->offset, racc->offset,
2678 &orig_gsi, gsi, &refreshed, lhs);
2679 if (refreshed != SRA_UDH_RIGHT)
2681 if (*stmt == gsi_stmt (*gsi))
2684 unlink_stmt_vdef (*stmt);
2685 gsi_remove (&orig_gsi, true);
2686 sra_stats.deleted++;
2687 return SRA_SA_REMOVED;
2692 if (access_has_children_p (racc))
2694 if (!racc->grp_unscalarized_data
2695 /* Do not remove SSA name definitions (PR 42704). */
2696 && TREE_CODE (lhs) != SSA_NAME)
2698 generate_subtree_copies (racc->first_child, lhs,
2699 racc->offset, 0, 0, gsi,
2701 gcc_assert (*stmt == gsi_stmt (*gsi));
2702 unlink_stmt_vdef (*stmt);
2703 gsi_remove (gsi, true);
2704 sra_stats.deleted++;
2705 return SRA_SA_REMOVED;
2708 generate_subtree_copies (racc->first_child, lhs,
2709 racc->offset, 0, 0, gsi, false, true);
2711 else if (access_has_children_p (lacc))
2712 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2713 0, 0, gsi, true, true);
2717 /* This gimplification must be done after generate_subtree_copies, lest we
2718 insert the subtree copies in the middle of the gimplified sequence. */
2719 if (force_gimple_rhs)
2720 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
2721 true, GSI_SAME_STMT);
2722 if (gimple_assign_rhs1 (*stmt) != rhs)
2724 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
2725 gcc_assert (*stmt == gsi_stmt (orig_gsi));
2728 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2731 /* Generate statements initializing scalar replacements of parts of function
2735 initialize_parameter_reductions (void)
2737 gimple_stmt_iterator gsi;
2738 gimple_seq seq = NULL;
2741 for (parm = DECL_ARGUMENTS (current_function_decl);
2743 parm = TREE_CHAIN (parm))
2745 VEC (access_p, heap) *access_vec;
2746 struct access *access;
2748 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2750 access_vec = get_base_access_vector (parm);
2756 seq = gimple_seq_alloc ();
2757 gsi = gsi_start (seq);
2760 for (access = VEC_index (access_p, access_vec, 0);
2762 access = access->next_grp)
2763 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2767 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2770 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2771 it reveals there are components of some aggregates to be scalarized, it runs
2772 the required transformations. */
2774 perform_intra_sra (void)
2779 if (!find_var_candidates ())
2782 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2786 if (!analyze_all_variable_accesses ())
2789 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2790 initialize_parameter_reductions ();
2792 statistics_counter_event (cfun, "Scalar replacements created",
2793 sra_stats.replacements);
2794 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2795 statistics_counter_event (cfun, "Subtree copy stmts",
2796 sra_stats.subtree_copies);
2797 statistics_counter_event (cfun, "Subreplacement stmts",
2798 sra_stats.subreplacements);
2799 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2800 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2801 sra_stats.separate_lhs_rhs_handling);
2803 ret = TODO_update_ssa;
2806 sra_deinitialize ();
2810 /* Perform early intraprocedural SRA. */
2812 early_intra_sra (void)
2814 sra_mode = SRA_MODE_EARLY_INTRA;
2815 return perform_intra_sra ();
2818 /* Perform "late" intraprocedural SRA. */
2820 late_intra_sra (void)
2822 sra_mode = SRA_MODE_INTRA;
2823 return perform_intra_sra ();
2828 gate_intra_sra (void)
2830 return flag_tree_sra != 0;
2834 struct gimple_opt_pass pass_sra_early =
2839 gate_intra_sra, /* gate */
2840 early_intra_sra, /* execute */
2843 0, /* static_pass_number */
2844 TV_TREE_SRA, /* tv_id */
2845 PROP_cfg | PROP_ssa, /* properties_required */
2846 0, /* properties_provided */
2847 0, /* properties_destroyed */
2848 0, /* todo_flags_start */
2852 | TODO_verify_ssa /* todo_flags_finish */
2856 struct gimple_opt_pass pass_sra =
2861 gate_intra_sra, /* gate */
2862 late_intra_sra, /* execute */
2865 0, /* static_pass_number */
2866 TV_TREE_SRA, /* tv_id */
2867 PROP_cfg | PROP_ssa, /* properties_required */
2868 0, /* properties_provided */
2869 0, /* properties_destroyed */
2870 TODO_update_address_taken, /* todo_flags_start */
2874 | TODO_verify_ssa /* todo_flags_finish */
2879 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2883 is_unused_scalar_param (tree parm)
2886 return (is_gimple_reg (parm)
2887 && (!(name = gimple_default_def (cfun, parm))
2888 || has_zero_uses (name)));
2891 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2892 examine whether there are any direct or otherwise infeasible ones. If so,
2893 return true, otherwise return false. PARM must be a gimple register with a
2894 non-NULL default definition. */
2897 ptr_parm_has_direct_uses (tree parm)
2899 imm_use_iterator ui;
2901 tree name = gimple_default_def (cfun, parm);
2904 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2906 if (gimple_assign_single_p (stmt))
2908 tree rhs = gimple_assign_rhs1 (stmt);
2911 else if (TREE_CODE (rhs) == ADDR_EXPR)
2915 rhs = TREE_OPERAND (rhs, 0);
2917 while (handled_component_p (rhs));
2918 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2922 else if (gimple_code (stmt) == GIMPLE_RETURN)
2924 tree t = gimple_return_retval (stmt);
2928 else if (is_gimple_call (stmt))
2931 for (i = 0; i < gimple_call_num_args (stmt); i++)
2933 tree arg = gimple_call_arg (stmt, i);
2941 else if (!is_gimple_debug (stmt))
2945 BREAK_FROM_IMM_USE_STMT (ui);
2951 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2952 them in candidate_bitmap. Note that these do not necessarily include
2953 parameter which are unused and thus can be removed. Return true iff any
2954 such candidate has been found. */
2957 find_param_candidates (void)
2963 for (parm = DECL_ARGUMENTS (current_function_decl);
2965 parm = TREE_CHAIN (parm))
2967 tree type = TREE_TYPE (parm);
2971 if (TREE_THIS_VOLATILE (parm)
2972 || TREE_ADDRESSABLE (parm)
2973 || is_va_list_type (type))
2976 if (is_unused_scalar_param (parm))
2982 if (POINTER_TYPE_P (type))
2984 type = TREE_TYPE (type);
2986 if (TREE_CODE (type) == FUNCTION_TYPE
2987 || TYPE_VOLATILE (type)
2988 || !is_gimple_reg (parm)
2989 || is_va_list_type (type)
2990 || ptr_parm_has_direct_uses (parm))
2993 else if (!AGGREGATE_TYPE_P (type))
2996 if (!COMPLETE_TYPE_P (type)
2997 || !host_integerp (TYPE_SIZE (type), 1)
2998 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2999 || (AGGREGATE_TYPE_P (type)
3000 && type_internals_preclude_sra_p (type)))
3003 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3005 if (dump_file && (dump_flags & TDF_DETAILS))
3007 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3008 print_generic_expr (dump_file, parm, 0);
3009 fprintf (dump_file, "\n");
3013 func_param_count = count;
3017 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3021 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3024 struct access *repr = (struct access *) data;
3026 repr->grp_maybe_modified = 1;
3030 /* Analyze what representatives (in linked lists accessible from
3031 REPRESENTATIVES) can be modified by side effects of statements in the
3032 current function. */
3035 analyze_modified_params (VEC (access_p, heap) *representatives)
3039 for (i = 0; i < func_param_count; i++)
3041 struct access *repr;
3043 for (repr = VEC_index (access_p, representatives, i);
3045 repr = repr->next_grp)
3047 struct access *access;
3051 if (no_accesses_p (repr))
3053 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3054 || repr->grp_maybe_modified)
3057 ao_ref_init (&ar, repr->expr);
3058 visited = BITMAP_ALLOC (NULL);
3059 for (access = repr; access; access = access->next_sibling)
3061 /* All accesses are read ones, otherwise grp_maybe_modified would
3062 be trivially set. */
3063 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3064 mark_maybe_modified, repr, &visited);
3065 if (repr->grp_maybe_modified)
3068 BITMAP_FREE (visited);
3073 /* Propagate distances in bb_dereferences in the opposite direction than the
3074 control flow edges, in each step storing the maximum of the current value
3075 and the minimum of all successors. These steps are repeated until the table
3076 stabilizes. Note that BBs which might terminate the functions (according to
3077 final_bbs bitmap) never updated in this way. */
3080 propagate_dereference_distances (void)
3082 VEC (basic_block, heap) *queue;
3085 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3086 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3089 VEC_quick_push (basic_block, queue, bb);
3093 while (!VEC_empty (basic_block, queue))
3097 bool change = false;
3100 bb = VEC_pop (basic_block, queue);
3103 if (bitmap_bit_p (final_bbs, bb->index))
3106 for (i = 0; i < func_param_count; i++)
3108 int idx = bb->index * func_param_count + i;
3110 HOST_WIDE_INT inh = 0;
3112 FOR_EACH_EDGE (e, ei, bb->succs)
3114 int succ_idx = e->dest->index * func_param_count + i;
3116 if (e->src == EXIT_BLOCK_PTR)
3122 inh = bb_dereferences [succ_idx];
3124 else if (bb_dereferences [succ_idx] < inh)
3125 inh = bb_dereferences [succ_idx];
3128 if (!first && bb_dereferences[idx] < inh)
3130 bb_dereferences[idx] = inh;
3135 if (change && !bitmap_bit_p (final_bbs, bb->index))
3136 FOR_EACH_EDGE (e, ei, bb->preds)
3141 e->src->aux = e->src;
3142 VEC_quick_push (basic_block, queue, e->src);
3146 VEC_free (basic_block, heap, queue);
3149 /* Dump a dereferences TABLE with heading STR to file F. */
3152 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3156 fprintf (dump_file, str);
3157 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3159 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3160 if (bb != EXIT_BLOCK_PTR)
3163 for (i = 0; i < func_param_count; i++)
3165 int idx = bb->index * func_param_count + i;
3166 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3171 fprintf (dump_file, "\n");
3174 /* Determine what (parts of) parameters passed by reference that are not
3175 assigned to are not certainly dereferenced in this function and thus the
3176 dereferencing cannot be safely moved to the caller without potentially
3177 introducing a segfault. Mark such REPRESENTATIVES as
3178 grp_not_necessarilly_dereferenced.
3180 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3181 part is calculated rather than simple booleans are calculated for each
3182 pointer parameter to handle cases when only a fraction of the whole
3183 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3186 The maximum dereference distances for each pointer parameter and BB are
3187 already stored in bb_dereference. This routine simply propagates these
3188 values upwards by propagate_dereference_distances and then compares the
3189 distances of individual parameters in the ENTRY BB to the equivalent
3190 distances of each representative of a (fraction of a) parameter. */
3193 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3197 if (dump_file && (dump_flags & TDF_DETAILS))
3198 dump_dereferences_table (dump_file,
3199 "Dereference table before propagation:\n",
3202 propagate_dereference_distances ();
3204 if (dump_file && (dump_flags & TDF_DETAILS))
3205 dump_dereferences_table (dump_file,
3206 "Dereference table after propagation:\n",
3209 for (i = 0; i < func_param_count; i++)
3211 struct access *repr = VEC_index (access_p, representatives, i);
3212 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3214 if (!repr || no_accesses_p (repr))
3219 if ((repr->offset + repr->size) > bb_dereferences[idx])
3220 repr->grp_not_necessarilly_dereferenced = 1;
3221 repr = repr->next_grp;
3227 /* Return the representative access for the parameter declaration PARM if it is
3228 a scalar passed by reference which is not written to and the pointer value
3229 is not used directly. Thus, if it is legal to dereference it in the caller
3230 and we can rule out modifications through aliases, such parameter should be
3231 turned into one passed by value. Return NULL otherwise. */
3233 static struct access *
3234 unmodified_by_ref_scalar_representative (tree parm)
3236 int i, access_count;
3237 struct access *repr;
3238 VEC (access_p, heap) *access_vec;
3240 access_vec = get_base_access_vector (parm);
3241 gcc_assert (access_vec);
3242 repr = VEC_index (access_p, access_vec, 0);
3245 repr->group_representative = repr;
3247 access_count = VEC_length (access_p, access_vec);
3248 for (i = 1; i < access_count; i++)
3250 struct access *access = VEC_index (access_p, access_vec, i);
3253 access->group_representative = repr;
3254 access->next_sibling = repr->next_sibling;
3255 repr->next_sibling = access;
3259 repr->grp_scalar_ptr = 1;
3263 /* Return true iff this access precludes IPA-SRA of the parameter it is
3267 access_precludes_ipa_sra_p (struct access *access)
3269 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3270 is incompatible assign in a call statement (and possibly even in asm
3271 statements). This can be relaxed by using a new temporary but only for
3272 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3273 intraprocedural SRA we deal with this by keeping the old aggregate around,
3274 something we cannot do in IPA-SRA.) */
3276 && (is_gimple_call (access->stmt)
3277 || gimple_code (access->stmt) == GIMPLE_ASM))
3284 /* Sort collected accesses for parameter PARM, identify representatives for
3285 each accessed region and link them together. Return NULL if there are
3286 different but overlapping accesses, return the special ptr value meaning
3287 there are no accesses for this parameter if that is the case and return the
3288 first representative otherwise. Set *RO_GRP if there is a group of accesses
3289 with only read (i.e. no write) accesses. */
3291 static struct access *
3292 splice_param_accesses (tree parm, bool *ro_grp)
3294 int i, j, access_count, group_count;
3295 int agg_size, total_size = 0;
3296 struct access *access, *res, **prev_acc_ptr = &res;
3297 VEC (access_p, heap) *access_vec;
3299 access_vec = get_base_access_vector (parm);
3301 return &no_accesses_representant;
3302 access_count = VEC_length (access_p, access_vec);
3304 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3305 compare_access_positions);
3310 while (i < access_count)
3313 access = VEC_index (access_p, access_vec, i);
3314 modification = access->write;
3315 if (access_precludes_ipa_sra_p (access))
3318 /* Access is about to become group representative unless we find some
3319 nasty overlap which would preclude us from breaking this parameter
3323 while (j < access_count)
3325 struct access *ac2 = VEC_index (access_p, access_vec, j);
3326 if (ac2->offset != access->offset)
3328 /* All or nothing law for parameters. */
3329 if (access->offset + access->size > ac2->offset)
3334 else if (ac2->size != access->size)
3337 if (access_precludes_ipa_sra_p (ac2))
3340 modification |= ac2->write;
3341 ac2->group_representative = access;
3342 ac2->next_sibling = access->next_sibling;
3343 access->next_sibling = ac2;
3348 access->grp_maybe_modified = modification;
3351 *prev_acc_ptr = access;
3352 prev_acc_ptr = &access->next_grp;
3353 total_size += access->size;
3357 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3358 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3360 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3361 if (total_size >= agg_size)
3364 gcc_assert (group_count > 0);
3368 /* Decide whether parameters with representative accesses given by REPR should
3369 be reduced into components. */
3372 decide_one_param_reduction (struct access *repr)
3374 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3379 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3380 gcc_assert (cur_parm_size > 0);
3382 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3385 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3390 agg_size = cur_parm_size;
3396 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3397 print_generic_expr (dump_file, parm, 0);
3398 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3399 for (acc = repr; acc; acc = acc->next_grp)
3400 dump_access (dump_file, acc, true);
3404 new_param_count = 0;
3406 for (; repr; repr = repr->next_grp)
3408 gcc_assert (parm == repr->base);
3411 if (!by_ref || (!repr->grp_maybe_modified
3412 && !repr->grp_not_necessarilly_dereferenced))
3413 total_size += repr->size;
3415 total_size += cur_parm_size;
3418 gcc_assert (new_param_count > 0);
3420 if (optimize_function_for_size_p (cfun))
3421 parm_size_limit = cur_parm_size;
3423 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3426 if (total_size < agg_size
3427 && total_size <= parm_size_limit)
3430 fprintf (dump_file, " ....will be split into %i components\n",
3432 return new_param_count;
3438 /* The order of the following enums is important, we need to do extra work for
3439 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3440 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3441 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3443 /* Identify representatives of all accesses to all candidate parameters for
3444 IPA-SRA. Return result based on what representatives have been found. */
3446 static enum ipa_splicing_result
3447 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3449 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3451 struct access *repr;
3453 *representatives = VEC_alloc (access_p, heap, func_param_count);
3455 for (parm = DECL_ARGUMENTS (current_function_decl);
3457 parm = TREE_CHAIN (parm))
3459 if (is_unused_scalar_param (parm))
3461 VEC_quick_push (access_p, *representatives,
3462 &no_accesses_representant);
3463 if (result == NO_GOOD_ACCESS)
3464 result = UNUSED_PARAMS;
3466 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3467 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3468 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3470 repr = unmodified_by_ref_scalar_representative (parm);
3471 VEC_quick_push (access_p, *representatives, repr);
3473 result = UNMODIF_BY_REF_ACCESSES;
3475 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3477 bool ro_grp = false;
3478 repr = splice_param_accesses (parm, &ro_grp);
3479 VEC_quick_push (access_p, *representatives, repr);
3481 if (repr && !no_accesses_p (repr))
3483 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3486 result = UNMODIF_BY_REF_ACCESSES;
3487 else if (result < MODIF_BY_REF_ACCESSES)
3488 result = MODIF_BY_REF_ACCESSES;
3490 else if (result < BY_VAL_ACCESSES)
3491 result = BY_VAL_ACCESSES;
3493 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3494 result = UNUSED_PARAMS;
3497 VEC_quick_push (access_p, *representatives, NULL);
3500 if (result == NO_GOOD_ACCESS)
3502 VEC_free (access_p, heap, *representatives);
3503 *representatives = NULL;
3504 return NO_GOOD_ACCESS;
3510 /* Return the index of BASE in PARMS. Abort if it is not found. */
3513 get_param_index (tree base, VEC(tree, heap) *parms)
3517 len = VEC_length (tree, parms);
3518 for (i = 0; i < len; i++)
3519 if (VEC_index (tree, parms, i) == base)
3524 /* Convert the decisions made at the representative level into compact
3525 parameter adjustments. REPRESENTATIVES are pointers to first
3526 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3527 final number of adjustments. */
3529 static ipa_parm_adjustment_vec
3530 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3531 int adjustments_count)
3533 VEC (tree, heap) *parms;
3534 ipa_parm_adjustment_vec adjustments;
3538 gcc_assert (adjustments_count > 0);
3539 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3540 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3541 parm = DECL_ARGUMENTS (current_function_decl);
3542 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3544 struct access *repr = VEC_index (access_p, representatives, i);
3546 if (!repr || no_accesses_p (repr))
3548 struct ipa_parm_adjustment *adj;
3550 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3551 memset (adj, 0, sizeof (*adj));
3552 adj->base_index = get_param_index (parm, parms);
3555 adj->copy_param = 1;
3557 adj->remove_param = 1;
3561 struct ipa_parm_adjustment *adj;
3562 int index = get_param_index (parm, parms);
3564 for (; repr; repr = repr->next_grp)
3566 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3567 memset (adj, 0, sizeof (*adj));
3568 gcc_assert (repr->base == parm);
3569 adj->base_index = index;
3570 adj->base = repr->base;
3571 adj->type = repr->type;
3572 adj->offset = repr->offset;
3573 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3574 && (repr->grp_maybe_modified
3575 || repr->grp_not_necessarilly_dereferenced));
3580 VEC_free (tree, heap, parms);
3584 /* Analyze the collected accesses and produce a plan what to do with the
3585 parameters in the form of adjustments, NULL meaning nothing. */
3587 static ipa_parm_adjustment_vec
3588 analyze_all_param_acesses (void)
3590 enum ipa_splicing_result repr_state;
3591 bool proceed = false;
3592 int i, adjustments_count = 0;
3593 VEC (access_p, heap) *representatives;
3594 ipa_parm_adjustment_vec adjustments;
3596 repr_state = splice_all_param_accesses (&representatives);
3597 if (repr_state == NO_GOOD_ACCESS)
3600 /* If there are any parameters passed by reference which are not modified
3601 directly, we need to check whether they can be modified indirectly. */
3602 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3604 analyze_caller_dereference_legality (representatives);
3605 analyze_modified_params (representatives);
3608 for (i = 0; i < func_param_count; i++)
3610 struct access *repr = VEC_index (access_p, representatives, i);
3612 if (repr && !no_accesses_p (repr))
3614 if (repr->grp_scalar_ptr)
3616 adjustments_count++;
3617 if (repr->grp_not_necessarilly_dereferenced
3618 || repr->grp_maybe_modified)
3619 VEC_replace (access_p, representatives, i, NULL);
3623 sra_stats.scalar_by_ref_to_by_val++;
3628 int new_components = decide_one_param_reduction (repr);
3630 if (new_components == 0)
3632 VEC_replace (access_p, representatives, i, NULL);
3633 adjustments_count++;
3637 adjustments_count += new_components;
3638 sra_stats.aggregate_params_reduced++;
3639 sra_stats.param_reductions_created += new_components;
3646 if (no_accesses_p (repr))
3649 sra_stats.deleted_unused_parameters++;
3651 adjustments_count++;
3655 if (!proceed && dump_file)
3656 fprintf (dump_file, "NOT proceeding to change params.\n");
3659 adjustments = turn_representatives_into_adjustments (representatives,
3664 VEC_free (access_p, heap, representatives);
3668 /* If a parameter replacement identified by ADJ does not yet exist in the form
3669 of declaration, create it and record it, otherwise return the previously
3673 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3676 if (!adj->new_ssa_base)
3678 char *pretty_name = make_fancy_name (adj->base);
3680 repl = create_tmp_var (TREE_TYPE (adj->base), "ISR");
3681 if (TREE_CODE (TREE_TYPE (repl)) == COMPLEX_TYPE
3682 || TREE_CODE (TREE_TYPE (repl)) == VECTOR_TYPE)
3683 DECL_GIMPLE_REG_P (repl) = 1;
3684 DECL_NAME (repl) = get_identifier (pretty_name);
3685 obstack_free (&name_obstack, pretty_name);
3688 add_referenced_var (repl);
3689 adj->new_ssa_base = repl;
3692 repl = adj->new_ssa_base;
3696 /* Find the first adjustment for a particular parameter BASE in a vector of
3697 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3700 static struct ipa_parm_adjustment *
3701 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3705 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3706 for (i = 0; i < len; i++)
3708 struct ipa_parm_adjustment *adj;
3710 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3711 if (!adj->copy_param && adj->base == base)
3718 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3719 parameter which is to be removed because its value is not used, replace the
3720 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3721 uses too and return true (update_stmt is then issued for the statement by
3722 the caller). DATA is a pointer to an adjustments vector. */
3725 replace_removed_params_ssa_names (gimple stmt, void *data)
3727 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3728 struct ipa_parm_adjustment *adj;
3729 tree lhs, decl, repl, name;
3731 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3732 if (gimple_code (stmt) == GIMPLE_PHI)
3733 lhs = gimple_phi_result (stmt);
3734 else if (is_gimple_assign (stmt))
3735 lhs = gimple_assign_lhs (stmt);
3736 else if (is_gimple_call (stmt))
3737 lhs = gimple_call_lhs (stmt);
3741 if (TREE_CODE (lhs) != SSA_NAME)
3743 decl = SSA_NAME_VAR (lhs);
3744 if (TREE_CODE (decl) != PARM_DECL)
3747 adj = get_adjustment_for_base (adjustments, decl);
3751 repl = get_replaced_param_substitute (adj);
3752 name = make_ssa_name (repl, stmt);
3756 fprintf (dump_file, "replacing an SSA name of a removed param ");
3757 print_generic_expr (dump_file, lhs, 0);
3758 fprintf (dump_file, " with ");
3759 print_generic_expr (dump_file, name, 0);
3760 fprintf (dump_file, "\n");
3763 if (is_gimple_assign (stmt))
3764 gimple_assign_set_lhs (stmt, name);
3765 else if (is_gimple_call (stmt))
3766 gimple_call_set_lhs (stmt, name);
3768 gimple_phi_set_result (stmt, name);
3770 replace_uses_by (lhs, name);
3774 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3775 expression *EXPR should be replaced by a reduction of a parameter, do so.
3776 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3777 whether the function should care about type incompatibility the current and
3778 new expressions. If it is true, the function will leave incompatibility
3779 issues to the caller.
3781 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3782 a write (LHS) expression. */
3785 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3786 bool dont_convert, void *data)
3788 ipa_parm_adjustment_vec adjustments;
3790 struct ipa_parm_adjustment *adj, *cand = NULL;
3791 HOST_WIDE_INT offset, size, max_size;
3794 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3795 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3797 if (TREE_CODE (*expr) == BIT_FIELD_REF
3798 || TREE_CODE (*expr) == IMAGPART_EXPR
3799 || TREE_CODE (*expr) == REALPART_EXPR)
3801 expr = &TREE_OPERAND (*expr, 0);
3802 dont_convert = false;
3805 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3806 if (!base || size == -1 || max_size == -1)
3809 if (INDIRECT_REF_P (base))
3810 base = TREE_OPERAND (base, 0);
3812 base = get_ssa_base_param (base);
3813 if (!base || TREE_CODE (base) != PARM_DECL)
3816 for (i = 0; i < len; i++)
3818 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3820 if (adj->base == base &&
3821 (adj->offset == offset || adj->remove_param))
3827 if (!cand || cand->copy_param || cand->remove_param)
3833 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3835 folded = gimple_fold_indirect_ref (src);
3840 src = cand->reduction;
3842 if (dump_file && (dump_flags & TDF_DETAILS))
3844 fprintf (dump_file, "About to replace expr ");
3845 print_generic_expr (dump_file, *expr, 0);
3846 fprintf (dump_file, " with ");
3847 print_generic_expr (dump_file, src, 0);
3848 fprintf (dump_file, "\n");
3852 && !useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3854 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3862 /* Callback for scan_function to process assign statements. Performs
3863 essentially the same function like sra_ipa_modify_expr. */
3865 static enum scan_assign_result
3866 sra_ipa_modify_assign (gimple *stmt_ptr, gimple_stmt_iterator *gsi, void *data)
3868 gimple stmt = *stmt_ptr;
3869 tree *lhs_p, *rhs_p;
3872 if (!gimple_assign_single_p (stmt))
3875 rhs_p = gimple_assign_rhs1_ptr (stmt);
3876 lhs_p = gimple_assign_lhs_ptr (stmt);
3878 any = sra_ipa_modify_expr (rhs_p, gsi, true, data);
3879 any |= sra_ipa_modify_expr (lhs_p, gsi, true, data);
3882 tree new_rhs = NULL_TREE;
3884 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
3886 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
3888 /* V_C_Es of constructors can cause trouble (PR 42714). */
3889 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
3890 *rhs_p = fold_convert (TREE_TYPE (*lhs_p), integer_zero_node);
3892 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 0);
3895 new_rhs = fold_build1_loc (gimple_location (stmt),
3896 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
3899 else if (REFERENCE_CLASS_P (*rhs_p)
3900 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
3901 && !is_gimple_reg (*lhs_p))
3902 /* This can happen when an assignment in between two single field
3903 structures is turned into an assignment in between two pointers to
3904 scalars (PR 42237). */
3909 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
3910 true, GSI_SAME_STMT);
3912 gimple_assign_set_rhs_from_tree (gsi, tmp);
3915 return SRA_SA_PROCESSED;
3921 /* Call gimple_debug_bind_reset_value on all debug statements describing
3922 gimple register parameters that are being removed or replaced. */
3925 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3929 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3930 for (i = 0; i < len; i++)
3932 struct ipa_parm_adjustment *adj;
3933 imm_use_iterator ui;
3937 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3938 if (adj->copy_param || !is_gimple_reg (adj->base))
3940 name = gimple_default_def (cfun, adj->base);
3943 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3945 /* All other users must have been removed by scan_function. */
3946 gcc_assert (is_gimple_debug (stmt));
3947 gimple_debug_bind_reset_value (stmt);
3953 /* Return true iff all callers have at least as many actual arguments as there
3954 are formal parameters in the current function. */
3957 all_callers_have_enough_arguments_p (struct cgraph_node *node)
3959 struct cgraph_edge *cs;
3960 for (cs = node->callers; cs; cs = cs->next_caller)
3961 if (!callsite_has_enough_arguments_p (cs->call_stmt))
3968 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3971 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3973 tree old_cur_fndecl = current_function_decl;
3974 struct cgraph_edge *cs;
3975 basic_block this_block;
3976 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3978 for (cs = node->callers; cs; cs = cs->next_caller)
3980 current_function_decl = cs->caller->decl;
3981 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3984 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3985 cs->caller->uid, cs->callee->uid,
3986 cgraph_node_name (cs->caller),
3987 cgraph_node_name (cs->callee));
3989 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3994 for (cs = node->callers; cs; cs = cs->next_caller)
3995 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3997 compute_inline_parameters (cs->caller);
3998 bitmap_set_bit (recomputed_callers, cs->caller->uid);
4000 BITMAP_FREE (recomputed_callers);
4002 current_function_decl = old_cur_fndecl;
4004 if (!encountered_recursive_call)
4007 FOR_EACH_BB (this_block)
4009 gimple_stmt_iterator gsi;
4011 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4013 gimple stmt = gsi_stmt (gsi);
4015 if (gimple_code (stmt) != GIMPLE_CALL)
4017 call_fndecl = gimple_call_fndecl (stmt);
4018 if (call_fndecl && cgraph_get_node (call_fndecl) == node)
4021 fprintf (dump_file, "Adjusting recursive call");
4022 ipa_modify_call_arguments (NULL, stmt, adjustments);
4030 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4031 as given in ADJUSTMENTS. */
4034 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4036 struct cgraph_node *alias;
4037 for (alias = node->same_body; alias; alias = alias->next)
4038 ipa_modify_formal_parameters (alias->decl, adjustments, "ISRA");
4039 /* current_function_decl must be handled last, after same_body aliases,
4040 as following functions will use what it computed. */
4041 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
4042 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
4043 replace_removed_params_ssa_names, false, adjustments);
4044 sra_ipa_reset_debug_stmts (adjustments);
4045 convert_callers (node, adjustments);
4046 cgraph_make_node_local (node);
4050 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4051 attributes, return true otherwise. NODE is the cgraph node of the current
4055 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4057 if (!cgraph_node_can_be_local_p (node))
4060 fprintf (dump_file, "Function not local to this compilation unit.\n");
4064 if (DECL_VIRTUAL_P (current_function_decl))
4067 fprintf (dump_file, "Function is a virtual method.\n");
4071 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
4072 && node->global.size >= MAX_INLINE_INSNS_AUTO)
4075 fprintf (dump_file, "Function too big to be made truly local.\n");
4083 "Function has no callers in this compilation unit.\n");
4090 fprintf (dump_file, "Function uses stdarg. \n");
4097 /* Perform early interprocedural SRA. */
4100 ipa_early_sra (void)
4102 struct cgraph_node *node = cgraph_node (current_function_decl);
4103 ipa_parm_adjustment_vec adjustments;
4106 if (!ipa_sra_preliminary_function_checks (node))
4110 sra_mode = SRA_MODE_EARLY_IPA;
4112 if (!find_param_candidates ())
4115 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
4119 if (!all_callers_have_enough_arguments_p (node))
4122 fprintf (dump_file, "There are callers with insufficient number of "
4127 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
4129 * last_basic_block_for_function (cfun));
4130 final_bbs = BITMAP_ALLOC (NULL);
4132 scan_function (build_access_from_expr, build_accesses_from_assign,
4134 if (encountered_apply_args)
4137 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
4141 if (encountered_unchangable_recursive_call)
4144 fprintf (dump_file, "Function calls itself with insufficient "
4145 "number of arguments.\n");
4149 adjustments = analyze_all_param_acesses ();
4153 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
4155 modify_function (node, adjustments);
4156 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
4157 ret = TODO_update_ssa;
4159 statistics_counter_event (cfun, "Unused parameters deleted",
4160 sra_stats.deleted_unused_parameters);
4161 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
4162 sra_stats.scalar_by_ref_to_by_val);
4163 statistics_counter_event (cfun, "Aggregate parameters broken up",
4164 sra_stats.aggregate_params_reduced);
4165 statistics_counter_event (cfun, "Aggregate parameter components created",
4166 sra_stats.param_reductions_created);
4169 BITMAP_FREE (final_bbs);
4170 free (bb_dereferences);
4172 sra_deinitialize ();
4176 /* Return if early ipa sra shall be performed. */
4178 ipa_early_sra_gate (void)
4180 return flag_ipa_sra;
4183 struct gimple_opt_pass pass_early_ipa_sra =
4187 "eipa_sra", /* name */
4188 ipa_early_sra_gate, /* gate */
4189 ipa_early_sra, /* execute */
4192 0, /* static_pass_number */
4193 TV_IPA_SRA, /* tv_id */
4194 0, /* properties_required */
4195 0, /* properties_provided */
4196 0, /* properties_destroyed */
4197 0, /* todo_flags_start */
4198 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */