1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009 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;
133 /* The statement this access belongs to. */
136 /* Next group representative for this aggregate. */
137 struct access *next_grp;
139 /* Pointer to the group representative. Pointer to itself if the struct is
140 the representative. */
141 struct access *group_representative;
143 /* If this access has any children (in terms of the definition above), this
144 points to the first one. */
145 struct access *first_child;
147 /* Pointer to the next sibling in the access tree as described above. */
148 struct access *next_sibling;
150 /* Pointers to the first and last element in the linked list of assign
152 struct assign_link *first_link, *last_link;
154 /* Pointer to the next access in the work queue. */
155 struct access *next_queued;
157 /* Replacement variable for this access "region." Never to be accessed
158 directly, always only by the means of get_access_replacement() and only
159 when grp_to_be_replaced flag is set. */
160 tree replacement_decl;
162 /* Is this particular access write access? */
165 /* Is this access currently in the work queue? */
166 unsigned grp_queued : 1;
168 /* Does this group contain a write access? This flag is propagated down the
170 unsigned grp_write : 1;
172 /* Does this group contain a read access? This flag is propagated down the
174 unsigned grp_read : 1;
176 /* Other passes of the analysis use this bit to make function
177 analyze_access_subtree create scalar replacements for this group if
179 unsigned grp_hint : 1;
181 /* Is the subtree rooted in this access fully covered by scalar
183 unsigned grp_covered : 1;
185 /* If set to true, this access and all below it in an access tree must not be
187 unsigned grp_unscalarizable_region : 1;
189 /* Whether data have been written to parts of the aggregate covered by this
190 access which is not to be scalarized. This flag is propagated up in the
192 unsigned grp_unscalarized_data : 1;
194 /* Does this access and/or group contain a write access through a
196 unsigned grp_partial_lhs : 1;
198 /* Set when a scalar replacement should be created for this variable. We do
199 the decision and creation at different places because create_tmp_var
200 cannot be called from within FOR_EACH_REFERENCED_VAR. */
201 unsigned grp_to_be_replaced : 1;
203 /* Is it possible that the group refers to data which might be (directly or
204 otherwise) modified? */
205 unsigned grp_maybe_modified : 1;
207 /* Set when this is a representative of a pointer to scalar (i.e. by
208 reference) parameter which we consider for turning into a plain scalar
209 (i.e. a by value parameter). */
210 unsigned grp_scalar_ptr : 1;
212 /* Set when we discover that this pointer is not safe to dereference in the
214 unsigned grp_not_necessarilly_dereferenced : 1;
217 typedef struct access *access_p;
219 DEF_VEC_P (access_p);
220 DEF_VEC_ALLOC_P (access_p, heap);
222 /* Alloc pool for allocating access structures. */
223 static alloc_pool access_pool;
225 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
226 are used to propagate subaccesses from rhs to lhs as long as they don't
227 conflict with what is already there. */
230 struct access *lacc, *racc;
231 struct assign_link *next;
234 /* Alloc pool for allocating assign link structures. */
235 static alloc_pool link_pool;
237 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
238 static struct pointer_map_t *base_access_vec;
240 /* Bitmap of candidates. */
241 static bitmap candidate_bitmap;
243 /* Obstack for creation of fancy names. */
244 static struct obstack name_obstack;
246 /* Head of a linked list of accesses that need to have its subaccesses
247 propagated to their assignment counterparts. */
248 static struct access *work_queue_head;
250 /* Number of parameters of the analyzed function when doing early ipa SRA. */
251 static int func_param_count;
253 /* scan_function sets the following to true if it encounters a call to
254 __builtin_apply_args. */
255 static bool encountered_apply_args;
257 /* This is a table in which for each basic block and parameter there is a
258 distance (offset + size) in that parameter which is dereferenced and
259 accessed in that BB. */
260 static HOST_WIDE_INT *bb_dereferences;
261 /* Bitmap of BBs that can cause the function to "stop" progressing by
262 returning, throwing externally, looping infinitely or calling a function
263 which might abort etc.. */
264 static bitmap final_bbs;
266 /* Representative of no accesses at all. */
267 static struct access no_accesses_representant;
269 /* Predicate to test the special value. */
272 no_accesses_p (struct access *access)
274 return access == &no_accesses_representant;
277 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
278 representative fields are dumped, otherwise those which only describe the
279 individual access are. */
283 /* Number of processed aggregates is readily available in
284 analyze_all_variable_accesses and so is not stored here. */
286 /* Number of created scalar replacements. */
289 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
293 /* Number of statements created by generate_subtree_copies. */
296 /* Number of statements created by load_assign_lhs_subreplacements. */
299 /* Number of times sra_modify_assign has deleted a statement. */
302 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
303 RHS reparately due to type conversions or nonexistent matching
305 int separate_lhs_rhs_handling;
307 /* Number of parameters that were removed because they were unused. */
308 int deleted_unused_parameters;
310 /* Number of scalars passed as parameters by reference that have been
311 converted to be passed by value. */
312 int scalar_by_ref_to_by_val;
314 /* Number of aggregate parameters that were replaced by one or more of their
316 int aggregate_params_reduced;
318 /* Numbber of components created when splitting aggregate parameters. */
319 int param_reductions_created;
323 dump_access (FILE *f, struct access *access, bool grp)
325 fprintf (f, "access { ");
326 fprintf (f, "base = (%d)'", DECL_UID (access->base));
327 print_generic_expr (f, access->base, 0);
328 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
329 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
330 fprintf (f, ", expr = ");
331 print_generic_expr (f, access->expr, 0);
332 fprintf (f, ", type = ");
333 print_generic_expr (f, access->type, 0);
335 fprintf (f, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
336 "grp_covered = %d, grp_unscalarizable_region = %d, "
337 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
338 "grp_to_be_replaced = %d\n grp_maybe_modified = %d, "
339 "grp_not_necessarilly_dereferenced = %d\n",
340 access->grp_write, access->grp_read, access->grp_hint,
341 access->grp_covered, access->grp_unscalarizable_region,
342 access->grp_unscalarized_data, access->grp_partial_lhs,
343 access->grp_to_be_replaced, access->grp_maybe_modified,
344 access->grp_not_necessarilly_dereferenced);
346 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
347 access->grp_partial_lhs);
350 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
353 dump_access_tree_1 (FILE *f, struct access *access, int level)
359 for (i = 0; i < level; i++)
360 fputs ("* ", dump_file);
362 dump_access (f, access, true);
364 if (access->first_child)
365 dump_access_tree_1 (f, access->first_child, level + 1);
367 access = access->next_sibling;
372 /* Dump all access trees for a variable, given the pointer to the first root in
376 dump_access_tree (FILE *f, struct access *access)
378 for (; access; access = access->next_grp)
379 dump_access_tree_1 (f, access, 0);
382 /* Return true iff ACC is non-NULL and has subaccesses. */
385 access_has_children_p (struct access *acc)
387 return acc && acc->first_child;
390 /* Return a vector of pointers to accesses for the variable given in BASE or
391 NULL if there is none. */
393 static VEC (access_p, heap) *
394 get_base_access_vector (tree base)
398 slot = pointer_map_contains (base_access_vec, base);
402 return *(VEC (access_p, heap) **) slot;
405 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
406 in ACCESS. Return NULL if it cannot be found. */
408 static struct access *
409 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
412 while (access && (access->offset != offset || access->size != size))
414 struct access *child = access->first_child;
416 while (child && (child->offset + child->size <= offset))
417 child = child->next_sibling;
424 /* Return the first group representative for DECL or NULL if none exists. */
426 static struct access *
427 get_first_repr_for_decl (tree base)
429 VEC (access_p, heap) *access_vec;
431 access_vec = get_base_access_vector (base);
435 return VEC_index (access_p, access_vec, 0);
438 /* Find an access representative for the variable BASE and given OFFSET and
439 SIZE. Requires that access trees have already been built. Return NULL if
440 it cannot be found. */
442 static struct access *
443 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
446 struct access *access;
448 access = get_first_repr_for_decl (base);
449 while (access && (access->offset + access->size <= offset))
450 access = access->next_grp;
454 return find_access_in_subtree (access, offset, size);
457 /* Add LINK to the linked list of assign links of RACC. */
459 add_link_to_rhs (struct access *racc, struct assign_link *link)
461 gcc_assert (link->racc == racc);
463 if (!racc->first_link)
465 gcc_assert (!racc->last_link);
466 racc->first_link = link;
469 racc->last_link->next = link;
471 racc->last_link = link;
475 /* Move all link structures in their linked list in OLD_RACC to the linked list
478 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
480 if (!old_racc->first_link)
482 gcc_assert (!old_racc->last_link);
486 if (new_racc->first_link)
488 gcc_assert (!new_racc->last_link->next);
489 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
491 new_racc->last_link->next = old_racc->first_link;
492 new_racc->last_link = old_racc->last_link;
496 gcc_assert (!new_racc->last_link);
498 new_racc->first_link = old_racc->first_link;
499 new_racc->last_link = old_racc->last_link;
501 old_racc->first_link = old_racc->last_link = NULL;
504 /* Add ACCESS to the work queue (which is actually a stack). */
507 add_access_to_work_queue (struct access *access)
509 if (!access->grp_queued)
511 gcc_assert (!access->next_queued);
512 access->next_queued = work_queue_head;
513 access->grp_queued = 1;
514 work_queue_head = access;
518 /* Pop an access from the work queue, and return it, assuming there is one. */
520 static struct access *
521 pop_access_from_work_queue (void)
523 struct access *access = work_queue_head;
525 work_queue_head = access->next_queued;
526 access->next_queued = NULL;
527 access->grp_queued = 0;
532 /* Allocate necessary structures. */
535 sra_initialize (void)
537 candidate_bitmap = BITMAP_ALLOC (NULL);
538 gcc_obstack_init (&name_obstack);
539 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
540 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
541 base_access_vec = pointer_map_create ();
542 memset (&sra_stats, 0, sizeof (sra_stats));
543 encountered_apply_args = false;
546 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
549 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
550 void *data ATTRIBUTE_UNUSED)
552 VEC (access_p, heap) *access_vec;
553 access_vec = (VEC (access_p, heap) *) *value;
554 VEC_free (access_p, heap, access_vec);
559 /* Deallocate all general structures. */
562 sra_deinitialize (void)
564 BITMAP_FREE (candidate_bitmap);
565 free_alloc_pool (access_pool);
566 free_alloc_pool (link_pool);
567 obstack_free (&name_obstack, NULL);
569 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
570 pointer_map_destroy (base_access_vec);
573 /* Remove DECL from candidates for SRA and write REASON to the dump file if
576 disqualify_candidate (tree decl, const char *reason)
578 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
580 if (dump_file && (dump_flags & TDF_DETAILS))
582 fprintf (dump_file, "! Disqualifying ");
583 print_generic_expr (dump_file, decl, 0);
584 fprintf (dump_file, " - %s\n", reason);
588 /* Return true iff the type contains a field or an element which does not allow
592 type_internals_preclude_sra_p (tree type)
597 switch (TREE_CODE (type))
601 case QUAL_UNION_TYPE:
602 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
603 if (TREE_CODE (fld) == FIELD_DECL)
605 tree ft = TREE_TYPE (fld);
607 if (TREE_THIS_VOLATILE (fld)
608 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
609 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
610 || !host_integerp (DECL_SIZE (fld), 1))
613 if (AGGREGATE_TYPE_P (ft)
614 && type_internals_preclude_sra_p (ft))
621 et = TREE_TYPE (type);
623 if (AGGREGATE_TYPE_P (et))
624 return type_internals_preclude_sra_p (et);
633 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
634 base variable if it is. Return T if it is not an SSA_NAME. */
637 get_ssa_base_param (tree t)
639 if (TREE_CODE (t) == SSA_NAME)
641 if (SSA_NAME_IS_DEFAULT_DEF (t))
642 return SSA_NAME_VAR (t);
649 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
650 belongs to, unless the BB has already been marked as a potentially
654 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
656 basic_block bb = gimple_bb (stmt);
657 int idx, parm_index = 0;
660 if (bitmap_bit_p (final_bbs, bb->index))
663 for (parm = DECL_ARGUMENTS (current_function_decl);
664 parm && parm != base;
665 parm = TREE_CHAIN (parm))
668 gcc_assert (parm_index < func_param_count);
670 idx = bb->index * func_param_count + parm_index;
671 if (bb_dereferences[idx] < dist)
672 bb_dereferences[idx] = dist;
675 /* Create and insert access for EXPR. Return created access, or NULL if it is
678 static struct access *
679 create_access (tree expr, gimple stmt, bool write)
681 struct access *access;
683 VEC (access_p,heap) *vec;
684 HOST_WIDE_INT offset, size, max_size;
686 bool ptr, unscalarizable_region = false;
688 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
690 if (sra_mode == SRA_MODE_EARLY_IPA && INDIRECT_REF_P (base))
692 base = get_ssa_base_param (TREE_OPERAND (base, 0));
700 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
703 if (sra_mode == SRA_MODE_EARLY_IPA)
705 if (size < 0 || size != max_size)
707 disqualify_candidate (base, "Encountered a variable sized access.");
710 if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
712 disqualify_candidate (base,
713 "Encountered an acces not aligned to a byte.");
718 mark_parm_dereference (base, offset + size, stmt);
722 if (size != max_size)
725 unscalarizable_region = true;
729 disqualify_candidate (base, "Encountered an unconstrained access.");
734 access = (struct access *) pool_alloc (access_pool);
735 memset (access, 0, sizeof (struct access));
738 access->offset = offset;
741 access->type = TREE_TYPE (expr);
742 access->write = write;
743 access->grp_unscalarizable_region = unscalarizable_region;
746 slot = pointer_map_contains (base_access_vec, base);
748 vec = (VEC (access_p, heap) *) *slot;
750 vec = VEC_alloc (access_p, heap, 32);
752 VEC_safe_push (access_p, heap, vec, access);
754 *((struct VEC (access_p,heap) **)
755 pointer_map_insert (base_access_vec, base)) = vec;
761 /* Search the given tree for a declaration by skipping handled components and
762 exclude it from the candidates. */
765 disqualify_base_of_expr (tree t, const char *reason)
767 while (handled_component_p (t))
768 t = TREE_OPERAND (t, 0);
770 if (sra_mode == SRA_MODE_EARLY_IPA)
772 if (INDIRECT_REF_P (t))
773 t = TREE_OPERAND (t, 0);
774 t = get_ssa_base_param (t);
778 disqualify_candidate (t, reason);
781 /* Scan expression EXPR and create access structures for all accesses to
782 candidates for scalarization. Return the created access or NULL if none is
785 static struct access *
786 build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
788 struct access *ret = NULL;
789 tree expr = *expr_ptr;
792 if (TREE_CODE (expr) == BIT_FIELD_REF
793 || TREE_CODE (expr) == IMAGPART_EXPR
794 || TREE_CODE (expr) == REALPART_EXPR)
796 expr = TREE_OPERAND (expr, 0);
802 /* We need to dive through V_C_Es in order to get the size of its parameter
803 and not the result type. Ada produces such statements. We are also
804 capable of handling the topmost V_C_E but not any of those buried in other
805 handled components. */
806 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
807 expr = TREE_OPERAND (expr, 0);
809 if (contains_view_convert_expr_p (expr))
811 disqualify_base_of_expr (expr, "V_C_E under a different handled "
816 switch (TREE_CODE (expr))
819 if (sra_mode != SRA_MODE_EARLY_IPA)
827 case ARRAY_RANGE_REF:
828 ret = create_access (expr, stmt, write);
835 if (write && partial_ref && ret)
836 ret->grp_partial_lhs = 1;
841 /* Callback of scan_function. Scan expression EXPR and create access
842 structures for all accesses to candidates for scalarization. Return true if
843 any access has been inserted. */
846 build_access_from_expr (tree *expr_ptr,
847 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
848 void *data ATTRIBUTE_UNUSED)
850 return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
853 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
854 modes in which it matters, return true iff they have been disqualified. RHS
855 may be NULL, in that case ignore it. If we scalarize an aggregate in
856 intra-SRA we may need to add statements after each statement. This is not
857 possible if a statement unconditionally has to end the basic block. */
859 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
861 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
862 && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
864 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
866 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
873 /* Result code for scan_assign callback for scan_function. */
874 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
875 SRA_SA_PROCESSED, /* stmt analyzed/changed */
876 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
879 /* Callback of scan_function. Scan expressions occuring in the statement
880 pointed to by STMT_EXPR, create access structures for all accesses to
881 candidates for scalarization and remove those candidates which occur in
882 statements or expressions that prevent them from being split apart. Return
883 true if any access has been inserted. */
885 static enum scan_assign_result
886 build_accesses_from_assign (gimple *stmt_ptr,
887 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
888 void *data ATTRIBUTE_UNUSED)
890 gimple stmt = *stmt_ptr;
891 tree *lhs_ptr, *rhs_ptr;
892 struct access *lacc, *racc;
894 if (!gimple_assign_single_p (stmt))
897 lhs_ptr = gimple_assign_lhs_ptr (stmt);
898 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
900 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
903 racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
904 lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
907 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
908 && !lacc->grp_unscalarizable_region
909 && !racc->grp_unscalarizable_region
910 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
911 /* FIXME: Turn the following line into an assert after PR 40058 is
913 && lacc->size == racc->size
914 && useless_type_conversion_p (lacc->type, racc->type))
916 struct assign_link *link;
918 link = (struct assign_link *) pool_alloc (link_pool);
919 memset (link, 0, sizeof (struct assign_link));
924 add_link_to_rhs (racc, link);
927 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
930 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
931 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
934 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
935 void *data ATTRIBUTE_UNUSED)
938 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
944 /* Scan function and look for interesting statements. Return true if any has
945 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
946 called on all expressions within statements except assign statements and
947 those deemed entirely unsuitable for some reason (all operands in such
948 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
949 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
950 called on assign statements and those call statements which have a lhs, it
951 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
952 pass and thus no statement is being modified. DATA is a pointer passed to
953 all callbacks. If any single callback returns true, this function also
954 returns true, otherwise it returns false. */
957 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
958 enum scan_assign_result (*scan_assign) (gimple *,
959 gimple_stmt_iterator *,
961 bool (*handle_ssa_defs)(gimple, void *),
962 bool analysis_stage, void *data)
964 gimple_stmt_iterator gsi;
972 bool bb_changed = false;
975 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
976 ret |= handle_ssa_defs (gsi_stmt (gsi), data);
978 gsi = gsi_start_bb (bb);
979 while (!gsi_end_p (gsi))
981 gimple stmt = gsi_stmt (gsi);
982 enum scan_assign_result assign_result;
983 bool any = false, deleted = false;
985 if (analysis_stage && final_bbs && stmt_can_throw_external (stmt))
986 bitmap_set_bit (final_bbs, bb->index);
987 switch (gimple_code (stmt))
990 t = gimple_return_retval_ptr (stmt);
992 any |= scan_expr (t, &gsi, false, data);
993 if (analysis_stage && final_bbs)
994 bitmap_set_bit (final_bbs, bb->index);
998 assign_result = scan_assign (&stmt, &gsi, data);
999 any |= assign_result == SRA_SA_PROCESSED;
1000 deleted = assign_result == SRA_SA_REMOVED;
1001 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
1002 any |= handle_ssa_defs (stmt, data);
1006 /* Operands must be processed before the lhs. */
1007 for (i = 0; i < gimple_call_num_args (stmt); i++)
1009 tree *argp = gimple_call_arg_ptr (stmt, i);
1010 any |= scan_expr (argp, &gsi, false, data);
1015 tree dest = gimple_call_fndecl (stmt);
1016 int flags = gimple_call_flags (stmt);
1019 && DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1020 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1021 encountered_apply_args = true;
1024 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1025 bitmap_set_bit (final_bbs, bb->index);
1028 if (gimple_call_lhs (stmt))
1030 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
1032 || !disqualify_ops_if_throwing_stmt (stmt,
1035 any |= scan_expr (lhs_ptr, &gsi, true, data);
1036 if (handle_ssa_defs)
1037 any |= handle_ssa_defs (stmt, data);
1045 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1048 bitmap_set_bit (final_bbs, bb->index);
1050 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1052 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
1053 any |= scan_expr (op, &gsi, false, data);
1055 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1057 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
1058 any |= scan_expr (op, &gsi, true, data);
1070 if (!analysis_stage)
1074 maybe_clean_eh_stmt (stmt);
1085 if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
1086 gimple_purge_dead_eh_edges (bb);
1092 /* Helper of QSORT function. There are pointers to accesses in the array. An
1093 access is considered smaller than another if it has smaller offset or if the
1094 offsets are the same but is size is bigger. */
1097 compare_access_positions (const void *a, const void *b)
1099 const access_p *fp1 = (const access_p *) a;
1100 const access_p *fp2 = (const access_p *) b;
1101 const access_p f1 = *fp1;
1102 const access_p f2 = *fp2;
1104 if (f1->offset != f2->offset)
1105 return f1->offset < f2->offset ? -1 : 1;
1107 if (f1->size == f2->size)
1109 /* Put any non-aggregate type before any aggregate type. */
1110 if (!is_gimple_reg_type (f1->type)
1111 && is_gimple_reg_type (f2->type))
1113 else if (is_gimple_reg_type (f1->type)
1114 && !is_gimple_reg_type (f2->type))
1116 /* Put the integral type with the bigger precision first. */
1117 else if (INTEGRAL_TYPE_P (f1->type)
1118 && INTEGRAL_TYPE_P (f2->type))
1119 return TYPE_PRECISION (f1->type) > TYPE_PRECISION (f2->type) ? -1 : 1;
1120 /* Put any integral type with non-full precision last. */
1121 else if (INTEGRAL_TYPE_P (f1->type)
1122 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1123 != TYPE_PRECISION (f1->type)))
1125 else if (INTEGRAL_TYPE_P (f2->type)
1126 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1127 != TYPE_PRECISION (f2->type)))
1129 /* Stabilize the sort. */
1130 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1133 /* We want the bigger accesses first, thus the opposite operator in the next
1135 return f1->size > f2->size ? -1 : 1;
1139 /* Append a name of the declaration to the name obstack. A helper function for
1143 make_fancy_decl_name (tree decl)
1147 tree name = DECL_NAME (decl);
1149 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1150 IDENTIFIER_LENGTH (name));
1153 sprintf (buffer, "D%u", DECL_UID (decl));
1154 obstack_grow (&name_obstack, buffer, strlen (buffer));
1158 /* Helper for make_fancy_name. */
1161 make_fancy_name_1 (tree expr)
1168 make_fancy_decl_name (expr);
1172 switch (TREE_CODE (expr))
1175 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1176 obstack_1grow (&name_obstack, '$');
1177 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1181 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1182 obstack_1grow (&name_obstack, '$');
1183 /* Arrays with only one element may not have a constant as their
1185 index = TREE_OPERAND (expr, 1);
1186 if (TREE_CODE (index) != INTEGER_CST)
1188 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1189 obstack_grow (&name_obstack, buffer, strlen (buffer));
1196 gcc_unreachable (); /* we treat these as scalars. */
1203 /* Create a human readable name for replacement variable of ACCESS. */
1206 make_fancy_name (tree expr)
1208 make_fancy_name_1 (expr);
1209 obstack_1grow (&name_obstack, '\0');
1210 return XOBFINISH (&name_obstack, char *);
1213 /* Helper function for build_ref_for_offset. */
1216 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1222 tree tr_size, index, minidx;
1223 HOST_WIDE_INT el_size;
1225 if (offset == 0 && exp_type
1226 && types_compatible_p (exp_type, type))
1229 switch (TREE_CODE (type))
1232 case QUAL_UNION_TYPE:
1234 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1236 HOST_WIDE_INT pos, size;
1237 tree expr, *expr_ptr;
1239 if (TREE_CODE (fld) != FIELD_DECL)
1242 pos = int_bit_position (fld);
1243 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1244 tr_size = DECL_SIZE (fld);
1245 if (!tr_size || !host_integerp (tr_size, 1))
1247 size = tree_low_cst (tr_size, 1);
1248 if (pos > offset || (pos + size) <= offset)
1253 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1259 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1260 offset - pos, exp_type))
1270 tr_size = TYPE_SIZE (TREE_TYPE (type));
1271 if (!tr_size || !host_integerp (tr_size, 1))
1273 el_size = tree_low_cst (tr_size, 1);
1275 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1276 if (TREE_CODE (minidx) != INTEGER_CST)
1280 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1281 if (!integer_zerop (minidx))
1282 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1283 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1284 NULL_TREE, NULL_TREE);
1286 offset = offset % el_size;
1287 type = TREE_TYPE (type);
1302 /* Construct an expression that would reference a part of aggregate *EXPR of
1303 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1304 function only determines whether it can build such a reference without
1305 actually doing it, otherwise, the tree it points to is unshared first and
1306 then used as a base for furhter sub-references.
1308 FIXME: Eventually this should be replaced with
1309 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1310 minor rewrite of fold_stmt.
1314 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1315 tree exp_type, bool allow_ptr)
1317 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1320 *expr = unshare_expr (*expr);
1322 if (allow_ptr && POINTER_TYPE_P (type))
1324 type = TREE_TYPE (type);
1326 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1329 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1332 /* Return true iff TYPE is stdarg va_list type. */
1335 is_va_list_type (tree type)
1337 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1340 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1341 those with type which is suitable for scalarization. */
1344 find_var_candidates (void)
1347 referenced_var_iterator rvi;
1350 FOR_EACH_REFERENCED_VAR (var, rvi)
1352 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1354 type = TREE_TYPE (var);
1356 if (!AGGREGATE_TYPE_P (type)
1357 || needs_to_live_in_memory (var)
1358 || TREE_THIS_VOLATILE (var)
1359 || !COMPLETE_TYPE_P (type)
1360 || !host_integerp (TYPE_SIZE (type), 1)
1361 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1362 || type_internals_preclude_sra_p (type)
1363 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1364 we also want to schedule it rather late. Thus we ignore it in
1366 || (sra_mode == SRA_MODE_EARLY_INTRA
1367 && is_va_list_type (type)))
1370 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1372 if (dump_file && (dump_flags & TDF_DETAILS))
1374 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1375 print_generic_expr (dump_file, var, 0);
1376 fprintf (dump_file, "\n");
1384 /* Sort all accesses for the given variable, check for partial overlaps and
1385 return NULL if there are any. If there are none, pick a representative for
1386 each combination of offset and size and create a linked list out of them.
1387 Return the pointer to the first representative and make sure it is the first
1388 one in the vector of accesses. */
1390 static struct access *
1391 sort_and_splice_var_accesses (tree var)
1393 int i, j, access_count;
1394 struct access *res, **prev_acc_ptr = &res;
1395 VEC (access_p, heap) *access_vec;
1397 HOST_WIDE_INT low = -1, high = 0;
1399 access_vec = get_base_access_vector (var);
1402 access_count = VEC_length (access_p, access_vec);
1404 /* Sort by <OFFSET, SIZE>. */
1405 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1406 compare_access_positions);
1409 while (i < access_count)
1411 struct access *access = VEC_index (access_p, access_vec, i);
1412 bool grp_write = access->write;
1413 bool grp_read = !access->write;
1414 bool multiple_reads = false;
1415 bool grp_partial_lhs = access->grp_partial_lhs;
1416 bool first_scalar = is_gimple_reg_type (access->type);
1417 bool unscalarizable_region = access->grp_unscalarizable_region;
1419 if (first || access->offset >= high)
1422 low = access->offset;
1423 high = access->offset + access->size;
1425 else if (access->offset > low && access->offset + access->size > high)
1428 gcc_assert (access->offset >= low
1429 && access->offset + access->size <= high);
1432 while (j < access_count)
1434 struct access *ac2 = VEC_index (access_p, access_vec, j);
1435 if (ac2->offset != access->offset || ac2->size != access->size)
1442 multiple_reads = true;
1446 grp_partial_lhs |= ac2->grp_partial_lhs;
1447 unscalarizable_region |= ac2->grp_unscalarizable_region;
1448 relink_to_new_repr (access, ac2);
1450 /* If there are both aggregate-type and scalar-type accesses with
1451 this combination of size and offset, the comparison function
1452 should have put the scalars first. */
1453 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1454 ac2->group_representative = access;
1460 access->group_representative = access;
1461 access->grp_write = grp_write;
1462 access->grp_read = grp_read;
1463 access->grp_hint = multiple_reads;
1464 access->grp_partial_lhs = grp_partial_lhs;
1465 access->grp_unscalarizable_region = unscalarizable_region;
1466 if (access->first_link)
1467 add_access_to_work_queue (access);
1469 *prev_acc_ptr = access;
1470 prev_acc_ptr = &access->next_grp;
1473 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1477 /* Create a variable for the given ACCESS which determines the type, name and a
1478 few other properties. Return the variable declaration and store it also to
1479 ACCESS->replacement. */
1482 create_access_replacement (struct access *access)
1486 repl = create_tmp_var (access->type, "SR");
1488 add_referenced_var (repl);
1489 mark_sym_for_renaming (repl);
1491 if (!access->grp_partial_lhs
1492 && (TREE_CODE (access->type) == COMPLEX_TYPE
1493 || TREE_CODE (access->type) == VECTOR_TYPE))
1494 DECL_GIMPLE_REG_P (repl) = 1;
1496 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1497 DECL_ARTIFICIAL (repl) = 1;
1499 if (DECL_NAME (access->base)
1500 && !DECL_IGNORED_P (access->base)
1501 && !DECL_ARTIFICIAL (access->base))
1503 char *pretty_name = make_fancy_name (access->expr);
1505 DECL_NAME (repl) = get_identifier (pretty_name);
1506 obstack_free (&name_obstack, pretty_name);
1508 SET_DECL_DEBUG_EXPR (repl, access->expr);
1509 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1510 DECL_IGNORED_P (repl) = 0;
1513 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1514 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1518 fprintf (dump_file, "Created a replacement for ");
1519 print_generic_expr (dump_file, access->base, 0);
1520 fprintf (dump_file, " offset: %u, size: %u: ",
1521 (unsigned) access->offset, (unsigned) access->size);
1522 print_generic_expr (dump_file, repl, 0);
1523 fprintf (dump_file, "\n");
1525 sra_stats.replacements++;
1530 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1533 get_access_replacement (struct access *access)
1535 gcc_assert (access->grp_to_be_replaced);
1537 if (!access->replacement_decl)
1538 access->replacement_decl = create_access_replacement (access);
1539 return access->replacement_decl;
1542 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1543 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1544 to it is not "within" the root. */
1547 build_access_subtree (struct access **access)
1549 struct access *root = *access, *last_child = NULL;
1550 HOST_WIDE_INT limit = root->offset + root->size;
1552 *access = (*access)->next_grp;
1553 while (*access && (*access)->offset + (*access)->size <= limit)
1556 root->first_child = *access;
1558 last_child->next_sibling = *access;
1559 last_child = *access;
1561 build_access_subtree (access);
1565 /* Build a tree of access representatives, ACCESS is the pointer to the first
1566 one, others are linked in a list by the next_grp field. Decide about scalar
1567 replacements on the way, return true iff any are to be created. */
1570 build_access_trees (struct access *access)
1574 struct access *root = access;
1576 build_access_subtree (&access);
1577 root->next_grp = access;
1581 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1585 expr_with_var_bounded_array_refs_p (tree expr)
1587 while (handled_component_p (expr))
1589 if (TREE_CODE (expr) == ARRAY_REF
1590 && !host_integerp (array_ref_low_bound (expr), 0))
1592 expr = TREE_OPERAND (expr, 0);
1597 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1598 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1599 all sorts of access flags appropriately along the way, notably always ser
1600 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1603 analyze_access_subtree (struct access *root, bool allow_replacements,
1604 bool mark_read, bool mark_write)
1606 struct access *child;
1607 HOST_WIDE_INT limit = root->offset + root->size;
1608 HOST_WIDE_INT covered_to = root->offset;
1609 bool scalar = is_gimple_reg_type (root->type);
1610 bool hole = false, sth_created = false;
1611 bool direct_read = root->grp_read;
1614 root->grp_read = true;
1615 else if (root->grp_read)
1619 root->grp_write = true;
1620 else if (root->grp_write)
1623 if (root->grp_unscalarizable_region)
1624 allow_replacements = false;
1626 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1627 allow_replacements = false;
1629 for (child = root->first_child; child; child = child->next_sibling)
1631 if (!hole && child->offset < covered_to)
1634 covered_to += child->size;
1636 sth_created |= analyze_access_subtree (child, allow_replacements,
1637 mark_read, mark_write);
1639 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1640 hole |= !child->grp_covered;
1643 if (allow_replacements && scalar && !root->first_child
1645 || (direct_read && root->grp_write)))
1647 if (dump_file && (dump_flags & TDF_DETAILS))
1649 fprintf (dump_file, "Marking ");
1650 print_generic_expr (dump_file, root->base, 0);
1651 fprintf (dump_file, " offset: %u, size: %u: ",
1652 (unsigned) root->offset, (unsigned) root->size);
1653 fprintf (dump_file, " to be replaced.\n");
1656 root->grp_to_be_replaced = 1;
1660 else if (covered_to < limit)
1663 if (sth_created && !hole)
1665 root->grp_covered = 1;
1668 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1669 root->grp_unscalarized_data = 1; /* not covered and written to */
1675 /* Analyze all access trees linked by next_grp by the means of
1676 analyze_access_subtree. */
1678 analyze_access_trees (struct access *access)
1684 if (analyze_access_subtree (access, true, false, false))
1686 access = access->next_grp;
1692 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1693 SIZE would conflict with an already existing one. If exactly such a child
1694 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1697 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1698 HOST_WIDE_INT size, struct access **exact_match)
1700 struct access *child;
1702 for (child = lacc->first_child; child; child = child->next_sibling)
1704 if (child->offset == norm_offset && child->size == size)
1706 *exact_match = child;
1710 if (child->offset < norm_offset + size
1711 && child->offset + child->size > norm_offset)
1718 /* Create a new child access of PARENT, with all properties just like MODEL
1719 except for its offset and with its grp_write false and grp_read true.
1720 Return the new access or NULL if it cannot be created. Note that this access
1721 is created long after all splicing and sorting, it's not located in any
1722 access vector and is automatically a representative of its group. */
1724 static struct access *
1725 create_artificial_child_access (struct access *parent, struct access *model,
1726 HOST_WIDE_INT new_offset)
1728 struct access *access;
1729 struct access **child;
1730 tree expr = parent->base;;
1732 gcc_assert (!model->grp_unscalarizable_region);
1734 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1735 model->type, false))
1738 access = (struct access *) pool_alloc (access_pool);
1739 memset (access, 0, sizeof (struct access));
1740 access->base = parent->base;
1741 access->expr = expr;
1742 access->offset = new_offset;
1743 access->size = model->size;
1744 access->type = model->type;
1745 access->grp_write = true;
1746 access->grp_read = false;
1748 child = &parent->first_child;
1749 while (*child && (*child)->offset < new_offset)
1750 child = &(*child)->next_sibling;
1752 access->next_sibling = *child;
1759 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1760 true if any new subaccess was created. Additionally, if RACC is a scalar
1761 access but LACC is not, change the type of the latter, if possible. */
1764 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1766 struct access *rchild;
1767 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1770 if (is_gimple_reg_type (lacc->type)
1771 || lacc->grp_unscalarizable_region
1772 || racc->grp_unscalarizable_region)
1775 if (!lacc->first_child && !racc->first_child
1776 && is_gimple_reg_type (racc->type))
1778 tree t = lacc->base;
1780 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1784 lacc->type = racc->type;
1789 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1791 struct access *new_acc = NULL;
1792 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1794 if (rchild->grp_unscalarizable_region)
1797 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1802 rchild->grp_hint = 1;
1803 new_acc->grp_hint |= new_acc->grp_read;
1804 if (rchild->first_child)
1805 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1810 /* If a (part of) a union field is on the RHS of an assignment, it can
1811 have sub-accesses which do not make sense on the LHS (PR 40351).
1812 Check that this is not the case. */
1813 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1814 rchild->type, false))
1817 rchild->grp_hint = 1;
1818 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1822 if (racc->first_child)
1823 propagate_subaccesses_across_link (new_acc, rchild);
1830 /* Propagate all subaccesses across assignment links. */
1833 propagate_all_subaccesses (void)
1835 while (work_queue_head)
1837 struct access *racc = pop_access_from_work_queue ();
1838 struct assign_link *link;
1840 gcc_assert (racc->first_link);
1842 for (link = racc->first_link; link; link = link->next)
1844 struct access *lacc = link->lacc;
1846 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1848 lacc = lacc->group_representative;
1849 if (propagate_subaccesses_across_link (lacc, racc)
1850 && lacc->first_link)
1851 add_access_to_work_queue (lacc);
1856 /* Go through all accesses collected throughout the (intraprocedural) analysis
1857 stage, exclude overlapping ones, identify representatives and build trees
1858 out of them, making decisions about scalarization on the way. Return true
1859 iff there are any to-be-scalarized variables after this stage. */
1862 analyze_all_variable_accesses (void)
1865 referenced_var_iterator rvi;
1868 FOR_EACH_REFERENCED_VAR (var, rvi)
1869 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1871 struct access *access;
1873 access = sort_and_splice_var_accesses (var);
1875 build_access_trees (access);
1877 disqualify_candidate (var,
1878 "No or inhibitingly overlapping accesses.");
1881 propagate_all_subaccesses ();
1883 FOR_EACH_REFERENCED_VAR (var, rvi)
1884 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1886 struct access *access = get_first_repr_for_decl (var);
1888 if (analyze_access_trees (access))
1891 if (dump_file && (dump_flags & TDF_DETAILS))
1893 fprintf (dump_file, "\nAccess trees for ");
1894 print_generic_expr (dump_file, var, 0);
1895 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1896 dump_access_tree (dump_file, access);
1897 fprintf (dump_file, "\n");
1901 disqualify_candidate (var, "No scalar replacements to be created.");
1906 statistics_counter_event (cfun, "Scalarized aggregates", res);
1913 /* Return true iff a reference statement into aggregate AGG can be built for
1914 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1915 or a child of its sibling. TOP_OFFSET is the offset from the processed
1916 access subtree that has to be subtracted from offset of each access. */
1919 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1920 HOST_WIDE_INT top_offset)
1924 if (access->grp_to_be_replaced
1925 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1926 access->offset - top_offset,
1927 access->type, false))
1930 if (access->first_child
1931 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1935 access = access->next_sibling;
1942 /* Generate statements copying scalar replacements of accesses within a subtree
1943 into or out of AGG. ACCESS is the first child of the root of the subtree to
1944 be processed. AGG is an aggregate type expression (can be a declaration but
1945 does not have to be, it can for example also be an indirect_ref).
1946 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1947 from offsets of individual accesses to get corresponding offsets for AGG.
1948 If CHUNK_SIZE is non-null, copy only replacements in the interval
1949 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1950 statement iterator used to place the new statements. WRITE should be true
1951 when the statements should write from AGG to the replacement and false if
1952 vice versa. if INSERT_AFTER is true, new statements will be added after the
1953 current statement in GSI, they will be added before the statement
1957 generate_subtree_copies (struct access *access, tree agg,
1958 HOST_WIDE_INT top_offset,
1959 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1960 gimple_stmt_iterator *gsi, bool write,
1967 if (chunk_size && access->offset >= start_offset + chunk_size)
1970 if (access->grp_to_be_replaced
1972 || access->offset + access->size > start_offset))
1974 tree repl = get_access_replacement (access);
1978 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1979 access->offset - top_offset,
1980 access->type, false);
1981 gcc_assert (ref_found);
1985 if (access->grp_partial_lhs)
1986 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
1988 insert_after ? GSI_NEW_STMT
1990 stmt = gimple_build_assign (repl, expr);
1994 TREE_NO_WARNING (repl) = 1;
1995 if (access->grp_partial_lhs)
1996 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1998 insert_after ? GSI_NEW_STMT
2000 stmt = gimple_build_assign (expr, repl);
2004 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2006 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2008 sra_stats.subtree_copies++;
2011 if (access->first_child)
2012 generate_subtree_copies (access->first_child, agg, top_offset,
2013 start_offset, chunk_size, gsi,
2014 write, insert_after);
2016 access = access->next_sibling;
2021 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2022 the root of the subtree to be processed. GSI is the statement iterator used
2023 for inserting statements which are added after the current statement if
2024 INSERT_AFTER is true or before it otherwise. */
2027 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2031 struct access *child;
2033 if (access->grp_to_be_replaced)
2037 stmt = gimple_build_assign (get_access_replacement (access),
2038 fold_convert (access->type,
2039 integer_zero_node));
2041 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2043 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2047 for (child = access->first_child; child; child = child->next_sibling)
2048 init_subtree_with_zero (child, gsi, insert_after);
2051 /* Search for an access representative for the given expression EXPR and
2052 return it or NULL if it cannot be found. */
2054 static struct access *
2055 get_access_for_expr (tree expr)
2057 HOST_WIDE_INT offset, size, max_size;
2060 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2061 a different size than the size of its argument and we need the latter
2063 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2064 expr = TREE_OPERAND (expr, 0);
2066 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2067 if (max_size == -1 || !DECL_P (base))
2070 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2073 return get_var_base_offset_size_access (base, offset, max_size);
2076 /* Callback for scan_function. Replace the expression EXPR with a scalar
2077 replacement if there is one and generate other statements to do type
2078 conversion or subtree copying if necessary. GSI is used to place newly
2079 created statements, WRITE is true if the expression is being written to (it
2080 is on a LHS of a statement or output in an assembly statement). */
2083 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2084 void *data ATTRIBUTE_UNUSED)
2086 struct access *access;
2089 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2092 expr = &TREE_OPERAND (*expr, 0);
2097 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2098 expr = &TREE_OPERAND (*expr, 0);
2099 access = get_access_for_expr (*expr);
2102 type = TREE_TYPE (*expr);
2104 if (access->grp_to_be_replaced)
2106 tree repl = get_access_replacement (access);
2107 /* If we replace a non-register typed access simply use the original
2108 access expression to extract the scalar component afterwards.
2109 This happens if scalarizing a function return value or parameter
2110 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2111 gcc.c-torture/compile/20011217-1.c. */
2112 if (!is_gimple_reg_type (type))
2117 tree ref = unshare_expr (access->expr);
2118 if (access->grp_partial_lhs)
2119 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2120 false, GSI_NEW_STMT);
2121 stmt = gimple_build_assign (repl, ref);
2122 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2126 if (access->grp_partial_lhs)
2127 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2128 true, GSI_SAME_STMT);
2129 stmt = gimple_build_assign (unshare_expr (access->expr), repl);
2130 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2135 gcc_assert (useless_type_conversion_p (type, access->type));
2141 if (access->first_child)
2143 HOST_WIDE_INT start_offset, chunk_size;
2145 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2146 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2148 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2149 start_offset = access->offset
2150 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2153 start_offset = chunk_size = 0;
2155 generate_subtree_copies (access->first_child, access->base, 0,
2156 start_offset, chunk_size, gsi, write, write);
2161 /* Where scalar replacements of the RHS have been written to when a replacement
2162 of a LHS of an assigments cannot be direclty loaded from a replacement of
2164 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2165 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2166 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2168 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2169 base aggregate if there are unscalarized data or directly to LHS
2172 static enum unscalarized_data_handling
2173 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2174 gimple_stmt_iterator *gsi)
2176 if (top_racc->grp_unscalarized_data)
2178 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2180 return SRA_UDH_RIGHT;
2184 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2185 0, 0, gsi, false, false);
2186 return SRA_UDH_LEFT;
2191 /* Try to generate statements to load all sub-replacements in an access
2192 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2193 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2194 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2195 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2196 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2197 the rhs top aggregate has already been refreshed by contents of its scalar
2198 reductions and is set to true if this function has to do it. */
2201 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2202 HOST_WIDE_INT left_offset,
2203 HOST_WIDE_INT right_offset,
2204 gimple_stmt_iterator *old_gsi,
2205 gimple_stmt_iterator *new_gsi,
2206 enum unscalarized_data_handling *refreshed,
2209 location_t loc = EXPR_LOCATION (lacc->expr);
2212 if (lacc->grp_to_be_replaced)
2214 struct access *racc;
2215 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2219 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2220 if (racc && racc->grp_to_be_replaced)
2222 rhs = get_access_replacement (racc);
2223 if (!useless_type_conversion_p (lacc->type, racc->type))
2224 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2230 /* No suitable access on the right hand side, need to load from
2231 the aggregate. See if we have to update it first... */
2232 if (*refreshed == SRA_UDH_NONE)
2233 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2236 if (*refreshed == SRA_UDH_LEFT)
2237 rhs = unshare_expr (lacc->expr);
2240 rhs = top_racc->base;
2241 repl_found = build_ref_for_offset (&rhs,
2242 TREE_TYPE (top_racc->base),
2243 offset, lacc->type, false);
2244 gcc_assert (repl_found);
2248 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2249 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2251 sra_stats.subreplacements++;
2253 else if (*refreshed == SRA_UDH_NONE
2254 && lacc->grp_read && !lacc->grp_covered)
2255 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2258 if (lacc->first_child)
2259 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2260 left_offset, right_offset,
2261 old_gsi, new_gsi, refreshed, lhs);
2262 lacc = lacc->next_sibling;
2267 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2268 to the assignment and GSI is the statement iterator pointing at it. Returns
2269 the same values as sra_modify_assign. */
2271 static enum scan_assign_result
2272 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2274 tree lhs = gimple_assign_lhs (*stmt);
2277 acc = get_access_for_expr (lhs);
2281 if (VEC_length (constructor_elt,
2282 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2284 /* I have never seen this code path trigger but if it can happen the
2285 following should handle it gracefully. */
2286 if (access_has_children_p (acc))
2287 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2289 return SRA_SA_PROCESSED;
2292 if (acc->grp_covered)
2294 init_subtree_with_zero (acc, gsi, false);
2295 unlink_stmt_vdef (*stmt);
2296 gsi_remove (gsi, true);
2297 return SRA_SA_REMOVED;
2301 init_subtree_with_zero (acc, gsi, true);
2302 return SRA_SA_PROCESSED;
2307 /* Callback of scan_function to process assign statements. It examines both
2308 sides of the statement, replaces them with a scalare replacement if there is
2309 one and generating copying of replacements if scalarized aggregates have been
2310 used in the assignment. STMT is a pointer to the assign statement, GSI is
2311 used to hold generated statements for type conversions and subtree
2314 static enum scan_assign_result
2315 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2316 void *data ATTRIBUTE_UNUSED)
2318 struct access *lacc, *racc;
2320 bool modify_this_stmt = false;
2321 bool force_gimple_rhs = false;
2322 location_t loc = gimple_location (*stmt);
2324 if (!gimple_assign_single_p (*stmt))
2326 lhs = gimple_assign_lhs (*stmt);
2327 rhs = gimple_assign_rhs1 (*stmt);
2329 if (TREE_CODE (rhs) == CONSTRUCTOR)
2330 return sra_modify_constructor_assign (stmt, gsi);
2332 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2333 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2334 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2336 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2338 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2340 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2343 lacc = get_access_for_expr (lhs);
2344 racc = get_access_for_expr (rhs);
2348 if (lacc && lacc->grp_to_be_replaced)
2350 lhs = get_access_replacement (lacc);
2351 gimple_assign_set_lhs (*stmt, lhs);
2352 modify_this_stmt = true;
2353 if (lacc->grp_partial_lhs)
2354 force_gimple_rhs = true;
2358 if (racc && racc->grp_to_be_replaced)
2360 rhs = get_access_replacement (racc);
2361 modify_this_stmt = true;
2362 if (racc->grp_partial_lhs)
2363 force_gimple_rhs = true;
2367 if (modify_this_stmt)
2369 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2371 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2372 ??? This should move to fold_stmt which we simply should
2373 call after building a VIEW_CONVERT_EXPR here. */
2374 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2375 && !access_has_children_p (lacc))
2378 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2379 TREE_TYPE (rhs), false))
2382 gimple_assign_set_lhs (*stmt, expr);
2385 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2386 && !access_has_children_p (racc))
2389 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2390 TREE_TYPE (lhs), false))
2393 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2395 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2396 if (!is_gimple_reg (lhs))
2397 force_gimple_rhs = true;
2401 if (force_gimple_rhs)
2402 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2403 true, GSI_SAME_STMT);
2404 if (gimple_assign_rhs1 (*stmt) != rhs)
2406 gimple_assign_set_rhs_from_tree (gsi, rhs);
2407 gcc_assert (*stmt == gsi_stmt (*gsi));
2411 /* From this point on, the function deals with assignments in between
2412 aggregates when at least one has scalar reductions of some of its
2413 components. There are three possible scenarios: Both the LHS and RHS have
2414 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2416 In the first case, we would like to load the LHS components from RHS
2417 components whenever possible. If that is not possible, we would like to
2418 read it directly from the RHS (after updating it by storing in it its own
2419 components). If there are some necessary unscalarized data in the LHS,
2420 those will be loaded by the original assignment too. If neither of these
2421 cases happen, the original statement can be removed. Most of this is done
2422 by load_assign_lhs_subreplacements.
2424 In the second case, we would like to store all RHS scalarized components
2425 directly into LHS and if they cover the aggregate completely, remove the
2426 statement too. In the third case, we want the LHS components to be loaded
2427 directly from the RHS (DSE will remove the original statement if it
2430 This is a bit complex but manageable when types match and when unions do
2431 not cause confusion in a way that we cannot really load a component of LHS
2432 from the RHS or vice versa (the access representing this level can have
2433 subaccesses that are accessible only through a different union field at a
2434 higher level - different from the one used in the examined expression).
2437 Therefore, I specially handle a fourth case, happening when there is a
2438 specific type cast or it is impossible to locate a scalarized subaccess on
2439 the other side of the expression. If that happens, I simply "refresh" the
2440 RHS by storing in it is scalarized components leave the original statement
2441 there to do the copying and then load the scalar replacements of the LHS.
2442 This is what the first branch does. */
2444 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2445 || (access_has_children_p (racc)
2446 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2447 || (access_has_children_p (lacc)
2448 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2450 if (access_has_children_p (racc))
2451 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2453 if (access_has_children_p (lacc))
2454 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2456 sra_stats.separate_lhs_rhs_handling++;
2460 if (access_has_children_p (lacc) && access_has_children_p (racc))
2462 gimple_stmt_iterator orig_gsi = *gsi;
2463 enum unscalarized_data_handling refreshed;
2465 if (lacc->grp_read && !lacc->grp_covered)
2466 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2468 refreshed = SRA_UDH_NONE;
2470 load_assign_lhs_subreplacements (lacc->first_child, racc,
2471 lacc->offset, racc->offset,
2472 &orig_gsi, gsi, &refreshed, lhs);
2473 if (refreshed != SRA_UDH_RIGHT)
2475 if (*stmt == gsi_stmt (*gsi))
2478 unlink_stmt_vdef (*stmt);
2479 gsi_remove (&orig_gsi, true);
2480 sra_stats.deleted++;
2481 return SRA_SA_REMOVED;
2486 if (access_has_children_p (racc))
2488 if (!racc->grp_unscalarized_data)
2490 generate_subtree_copies (racc->first_child, lhs,
2491 racc->offset, 0, 0, gsi,
2493 gcc_assert (*stmt == gsi_stmt (*gsi));
2494 unlink_stmt_vdef (*stmt);
2495 gsi_remove (gsi, true);
2496 sra_stats.deleted++;
2497 return SRA_SA_REMOVED;
2500 generate_subtree_copies (racc->first_child, lhs,
2501 racc->offset, 0, 0, gsi, false, true);
2503 else if (access_has_children_p (lacc))
2504 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2505 0, 0, gsi, true, true);
2508 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2511 /* Generate statements initializing scalar replacements of parts of function
2515 initialize_parameter_reductions (void)
2517 gimple_stmt_iterator gsi;
2518 gimple_seq seq = NULL;
2521 for (parm = DECL_ARGUMENTS (current_function_decl);
2523 parm = TREE_CHAIN (parm))
2525 VEC (access_p, heap) *access_vec;
2526 struct access *access;
2528 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2530 access_vec = get_base_access_vector (parm);
2536 seq = gimple_seq_alloc ();
2537 gsi = gsi_start (seq);
2540 for (access = VEC_index (access_p, access_vec, 0);
2542 access = access->next_grp)
2543 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2547 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2550 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2551 it reveals there are components of some aggregates to be scalarized, it runs
2552 the required transformations. */
2554 perform_intra_sra (void)
2559 if (!find_var_candidates ())
2562 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2566 if (!analyze_all_variable_accesses ())
2569 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2570 initialize_parameter_reductions ();
2572 statistics_counter_event (cfun, "Scalar replacements created",
2573 sra_stats.replacements);
2574 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2575 statistics_counter_event (cfun, "Subtree copy stmts",
2576 sra_stats.subtree_copies);
2577 statistics_counter_event (cfun, "Subreplacement stmts",
2578 sra_stats.subreplacements);
2579 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2580 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2581 sra_stats.separate_lhs_rhs_handling);
2583 ret = TODO_update_ssa;
2586 sra_deinitialize ();
2590 /* Perform early intraprocedural SRA. */
2592 early_intra_sra (void)
2594 sra_mode = SRA_MODE_EARLY_INTRA;
2595 return perform_intra_sra ();
2598 /* Perform "late" intraprocedural SRA. */
2600 late_intra_sra (void)
2602 sra_mode = SRA_MODE_INTRA;
2603 return perform_intra_sra ();
2608 gate_intra_sra (void)
2610 return flag_tree_sra != 0;
2614 struct gimple_opt_pass pass_sra_early =
2619 gate_intra_sra, /* gate */
2620 early_intra_sra, /* execute */
2623 0, /* static_pass_number */
2624 TV_TREE_SRA, /* tv_id */
2625 PROP_cfg | PROP_ssa, /* properties_required */
2626 0, /* properties_provided */
2627 0, /* properties_destroyed */
2628 0, /* todo_flags_start */
2632 | TODO_verify_ssa /* todo_flags_finish */
2636 struct gimple_opt_pass pass_sra =
2641 gate_intra_sra, /* gate */
2642 late_intra_sra, /* execute */
2645 0, /* static_pass_number */
2646 TV_TREE_SRA, /* tv_id */
2647 PROP_cfg | PROP_ssa, /* properties_required */
2648 0, /* properties_provided */
2649 0, /* properties_destroyed */
2650 TODO_update_address_taken, /* todo_flags_start */
2654 | TODO_verify_ssa /* todo_flags_finish */
2659 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2663 is_unused_scalar_param (tree parm)
2666 return (is_gimple_reg (parm)
2667 && (!(name = gimple_default_def (cfun, parm))
2668 || has_zero_uses (name)));
2671 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2672 examine whether there are any direct or otherwise infeasible ones. If so,
2673 return true, otherwise return false. PARM must be a gimple register with a
2674 non-NULL default definition. */
2677 ptr_parm_has_direct_uses (tree parm)
2679 imm_use_iterator ui;
2681 tree name = gimple_default_def (cfun, parm);
2684 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2686 if (gimple_assign_single_p (stmt))
2688 tree rhs = gimple_assign_rhs1 (stmt);
2691 else if (TREE_CODE (rhs) == ADDR_EXPR)
2695 rhs = TREE_OPERAND (rhs, 0);
2697 while (handled_component_p (rhs));
2698 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2702 else if (gimple_code (stmt) == GIMPLE_RETURN)
2704 tree t = gimple_return_retval (stmt);
2708 else if (is_gimple_call (stmt))
2711 for (i = 0; i < gimple_call_num_args (stmt); i++)
2713 tree arg = gimple_call_arg (stmt, i);
2721 else if (!is_gimple_debug (stmt))
2725 BREAK_FROM_IMM_USE_STMT (ui);
2731 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2732 them in candidate_bitmap. Note that these do not necessarily include
2733 parameter which are unused and thus can be removed. Return true iff any
2734 such candidate has been found. */
2737 find_param_candidates (void)
2743 for (parm = DECL_ARGUMENTS (current_function_decl);
2745 parm = TREE_CHAIN (parm))
2747 tree type = TREE_TYPE (parm);
2751 if (TREE_THIS_VOLATILE (parm)
2752 || TREE_ADDRESSABLE (parm)
2753 || is_va_list_type (type))
2756 if (is_unused_scalar_param (parm))
2762 if (POINTER_TYPE_P (type))
2764 type = TREE_TYPE (type);
2766 if (TREE_CODE (type) == FUNCTION_TYPE
2767 || TYPE_VOLATILE (type)
2768 || !is_gimple_reg (parm)
2769 || is_va_list_type (type)
2770 || ptr_parm_has_direct_uses (parm))
2773 else if (!AGGREGATE_TYPE_P (type))
2776 if (!COMPLETE_TYPE_P (type)
2777 || !host_integerp (TYPE_SIZE (type), 1)
2778 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2779 || (AGGREGATE_TYPE_P (type)
2780 && type_internals_preclude_sra_p (type)))
2783 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2785 if (dump_file && (dump_flags & TDF_DETAILS))
2787 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2788 print_generic_expr (dump_file, parm, 0);
2789 fprintf (dump_file, "\n");
2793 func_param_count = count;
2797 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2801 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2804 struct access *repr = (struct access *) data;
2806 repr->grp_maybe_modified = 1;
2810 /* Analyze what representatives (in linked lists accessible from
2811 REPRESENTATIVES) can be modified by side effects of statements in the
2812 current function. */
2815 analyze_modified_params (VEC (access_p, heap) *representatives)
2819 for (i = 0; i < func_param_count; i++)
2821 struct access *repr;
2823 for (repr = VEC_index (access_p, representatives, i);
2825 repr = repr->next_grp)
2827 VEC (access_p, heap) *access_vec;
2828 int j, access_count;
2831 if (no_accesses_p (repr))
2834 if (!POINTER_TYPE_P (TREE_TYPE (parm))
2835 || repr->grp_maybe_modified)
2838 access_vec = get_base_access_vector (parm);
2839 access_count = VEC_length (access_p, access_vec);
2840 for (j = 0; j < access_count; j++)
2842 struct access *access;
2845 /* All accesses are read ones, otherwise grp_maybe_modified would
2846 be trivially set. */
2847 access = VEC_index (access_p, access_vec, j);
2848 ao_ref_init (&ar, access->expr);
2849 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2850 mark_maybe_modified, repr, NULL);
2851 if (repr->grp_maybe_modified)
2858 /* Propagate distances in bb_dereferences in the opposite direction than the
2859 control flow edges, in each step storing the maximum of the current value
2860 and the minimum of all successors. These steps are repeated until the table
2861 stabilizes. Note that BBs which might terminate the functions (according to
2862 final_bbs bitmap) never updated in this way. */
2865 propagate_dereference_distances (void)
2867 VEC (basic_block, heap) *queue;
2870 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2871 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2874 VEC_quick_push (basic_block, queue, bb);
2878 while (!VEC_empty (basic_block, queue))
2882 bool change = false;
2885 bb = VEC_pop (basic_block, queue);
2888 if (bitmap_bit_p (final_bbs, bb->index))
2891 for (i = 0; i < func_param_count; i++)
2893 int idx = bb->index * func_param_count + i;
2895 HOST_WIDE_INT inh = 0;
2897 FOR_EACH_EDGE (e, ei, bb->succs)
2899 int succ_idx = e->dest->index * func_param_count + i;
2901 if (e->src == EXIT_BLOCK_PTR)
2907 inh = bb_dereferences [succ_idx];
2909 else if (bb_dereferences [succ_idx] < inh)
2910 inh = bb_dereferences [succ_idx];
2913 if (!first && bb_dereferences[idx] < inh)
2915 bb_dereferences[idx] = inh;
2920 if (change && !bitmap_bit_p (final_bbs, bb->index))
2921 FOR_EACH_EDGE (e, ei, bb->preds)
2926 e->src->aux = e->src;
2927 VEC_quick_push (basic_block, queue, e->src);
2931 VEC_free (basic_block, heap, queue);
2934 /* Dump a dereferences TABLE with heading STR to file F. */
2937 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2941 fprintf (dump_file, str);
2942 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2944 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2945 if (bb != EXIT_BLOCK_PTR)
2948 for (i = 0; i < func_param_count; i++)
2950 int idx = bb->index * func_param_count + i;
2951 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
2956 fprintf (dump_file, "\n");
2959 /* Determine what (parts of) parameters passed by reference that are not
2960 assigned to are not certainly dereferenced in this function and thus the
2961 dereferencing cannot be safely moved to the caller without potentially
2962 introducing a segfault. Mark such REPRESENTATIVES as
2963 grp_not_necessarilly_dereferenced.
2965 The dereferenced maximum "distance," i.e. the offset + size of the accessed
2966 part is calculated rather than simple booleans are calculated for each
2967 pointer parameter to handle cases when only a fraction of the whole
2968 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
2971 The maximum dereference distances for each pointer parameter and BB are
2972 already stored in bb_dereference. This routine simply propagates these
2973 values upwards by propagate_dereference_distances and then compares the
2974 distances of individual parameters in the ENTRY BB to the equivalent
2975 distances of each representative of a (fraction of a) parameter. */
2978 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
2982 if (dump_file && (dump_flags & TDF_DETAILS))
2983 dump_dereferences_table (dump_file,
2984 "Dereference table before propagation:\n",
2987 propagate_dereference_distances ();
2989 if (dump_file && (dump_flags & TDF_DETAILS))
2990 dump_dereferences_table (dump_file,
2991 "Dereference table after propagation:\n",
2994 for (i = 0; i < func_param_count; i++)
2996 struct access *repr = VEC_index (access_p, representatives, i);
2997 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
2999 if (!repr || no_accesses_p (repr))
3004 if ((repr->offset + repr->size) > bb_dereferences[idx])
3005 repr->grp_not_necessarilly_dereferenced = 1;
3006 repr = repr->next_grp;
3012 /* Return the representative access for the parameter declaration PARM if it is
3013 a scalar passed by reference which is not written to and the pointer value
3014 is not used directly. Thus, if it is legal to dereference it in the caller
3015 and we can rule out modifications through aliases, such parameter should be
3016 turned into one passed by value. Return NULL otherwise. */
3018 static struct access *
3019 unmodified_by_ref_scalar_representative (tree parm)
3021 int i, access_count;
3022 struct access *access;
3023 VEC (access_p, heap) *access_vec;
3025 access_vec = get_base_access_vector (parm);
3026 gcc_assert (access_vec);
3027 access_count = VEC_length (access_p, access_vec);
3029 for (i = 0; i < access_count; i++)
3031 access = VEC_index (access_p, access_vec, i);
3036 access = VEC_index (access_p, access_vec, 0);
3037 access->grp_read = 1;
3038 access->grp_scalar_ptr = 1;
3042 /* Sort collected accesses for parameter PARM, identify representatives for
3043 each accessed region and link them together. Return NULL if there are
3044 different but overlapping accesses, return the special ptr value meaning
3045 there are no accesses for this parameter if that is the case and return the
3046 first representative otherwise. Set *RO_GRP if there is a group of accesses
3047 with only read (i.e. no write) accesses. */
3049 static struct access *
3050 splice_param_accesses (tree parm, bool *ro_grp)
3052 int i, j, access_count, group_count;
3053 int agg_size, total_size = 0;
3054 struct access *access, *res, **prev_acc_ptr = &res;
3055 VEC (access_p, heap) *access_vec;
3057 access_vec = get_base_access_vector (parm);
3059 return &no_accesses_representant;
3060 access_count = VEC_length (access_p, access_vec);
3062 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3063 compare_access_positions);
3068 while (i < access_count)
3071 access = VEC_index (access_p, access_vec, i);
3072 modification = access->write;
3074 /* Access is about to become group representative unless we find some
3075 nasty overlap which would preclude us from breaking this parameter
3079 while (j < access_count)
3081 struct access *ac2 = VEC_index (access_p, access_vec, j);
3082 if (ac2->offset != access->offset)
3084 /* All or nothing law for parameters. */
3085 if (access->offset + access->size > ac2->offset)
3090 else if (ac2->size != access->size)
3093 modification |= ac2->write;
3098 access->grp_maybe_modified = modification;
3101 *prev_acc_ptr = access;
3102 prev_acc_ptr = &access->next_grp;
3103 total_size += access->size;
3107 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3108 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3110 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3111 if (total_size >= agg_size)
3114 gcc_assert (group_count > 0);
3118 /* Decide whether parameters with representative accesses given by REPR should
3119 be reduced into components. */
3122 decide_one_param_reduction (struct access *repr)
3124 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3129 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3130 gcc_assert (cur_parm_size > 0);
3132 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3135 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3140 agg_size = cur_parm_size;
3146 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3147 print_generic_expr (dump_file, parm, 0);
3148 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3149 for (acc = repr; acc; acc = acc->next_grp)
3150 dump_access (dump_file, acc, true);
3154 new_param_count = 0;
3156 for (; repr; repr = repr->next_grp)
3158 gcc_assert (parm == repr->base);
3161 if (!by_ref || (!repr->grp_maybe_modified
3162 && !repr->grp_not_necessarilly_dereferenced))
3163 total_size += repr->size;
3165 total_size += cur_parm_size;
3168 gcc_assert (new_param_count > 0);
3170 if (optimize_function_for_size_p (cfun))
3171 parm_size_limit = cur_parm_size;
3173 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3176 if (total_size < agg_size
3177 && total_size <= parm_size_limit)
3180 fprintf (dump_file, " ....will be split into %i components\n",
3182 return new_param_count;
3188 /* The order of the following enums is important, we need to do extra work for
3189 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3190 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3191 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3193 /* Identify representatives of all accesses to all candidate parameters for
3194 IPA-SRA. Return result based on what representatives have been found. */
3196 static enum ipa_splicing_result
3197 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3199 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3201 struct access *repr;
3203 *representatives = VEC_alloc (access_p, heap, func_param_count);
3205 for (parm = DECL_ARGUMENTS (current_function_decl);
3207 parm = TREE_CHAIN (parm))
3209 if (is_unused_scalar_param (parm))
3211 VEC_quick_push (access_p, *representatives,
3212 &no_accesses_representant);
3213 if (result == NO_GOOD_ACCESS)
3214 result = UNUSED_PARAMS;
3216 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3217 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3218 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3220 repr = unmodified_by_ref_scalar_representative (parm);
3221 VEC_quick_push (access_p, *representatives, repr);
3223 result = UNMODIF_BY_REF_ACCESSES;
3225 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3227 bool ro_grp = false;
3228 repr = splice_param_accesses (parm, &ro_grp);
3229 VEC_quick_push (access_p, *representatives, repr);
3231 if (repr && !no_accesses_p (repr))
3233 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3236 result = UNMODIF_BY_REF_ACCESSES;
3237 else if (result < MODIF_BY_REF_ACCESSES)
3238 result = MODIF_BY_REF_ACCESSES;
3240 else if (result < BY_VAL_ACCESSES)
3241 result = BY_VAL_ACCESSES;
3243 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3244 result = UNUSED_PARAMS;
3247 VEC_quick_push (access_p, *representatives, NULL);
3250 if (result == NO_GOOD_ACCESS)
3252 VEC_free (access_p, heap, *representatives);
3253 *representatives = NULL;
3254 return NO_GOOD_ACCESS;
3260 /* Return the index of BASE in PARMS. Abort if it is not found. */
3263 get_param_index (tree base, VEC(tree, heap) *parms)
3267 len = VEC_length (tree, parms);
3268 for (i = 0; i < len; i++)
3269 if (VEC_index (tree, parms, i) == base)
3274 /* Convert the decisions made at the representative level into compact
3275 parameter adjustments. REPRESENTATIVES are pointers to first
3276 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3277 final number of adjustments. */
3279 static ipa_parm_adjustment_vec
3280 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3281 int adjustments_count)
3283 VEC (tree, heap) *parms;
3284 ipa_parm_adjustment_vec adjustments;
3288 gcc_assert (adjustments_count > 0);
3289 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3290 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3291 parm = DECL_ARGUMENTS (current_function_decl);
3292 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3294 struct access *repr = VEC_index (access_p, representatives, i);
3296 if (!repr || no_accesses_p (repr))
3298 struct ipa_parm_adjustment *adj;
3300 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3301 memset (adj, 0, sizeof (*adj));
3302 adj->base_index = get_param_index (parm, parms);
3305 adj->copy_param = 1;
3307 adj->remove_param = 1;
3311 struct ipa_parm_adjustment *adj;
3312 int index = get_param_index (parm, parms);
3314 for (; repr; repr = repr->next_grp)
3316 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3317 memset (adj, 0, sizeof (*adj));
3318 gcc_assert (repr->base == parm);
3319 adj->base_index = index;
3320 adj->base = repr->base;
3321 adj->type = repr->type;
3322 adj->offset = repr->offset;
3323 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3324 && (repr->grp_maybe_modified
3325 || repr->grp_not_necessarilly_dereferenced));
3330 VEC_free (tree, heap, parms);
3334 /* Analyze the collected accesses and produce a plan what to do with the
3335 parameters in the form of adjustments, NULL meaning nothing. */
3337 static ipa_parm_adjustment_vec
3338 analyze_all_param_acesses (void)
3340 enum ipa_splicing_result repr_state;
3341 bool proceed = false;
3342 int i, adjustments_count = 0;
3343 VEC (access_p, heap) *representatives;
3344 ipa_parm_adjustment_vec adjustments;
3346 repr_state = splice_all_param_accesses (&representatives);
3347 if (repr_state == NO_GOOD_ACCESS)
3350 /* If there are any parameters passed by reference which are not modified
3351 directly, we need to check whether they can be modified indirectly. */
3352 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3354 analyze_caller_dereference_legality (representatives);
3355 analyze_modified_params (representatives);
3358 for (i = 0; i < func_param_count; i++)
3360 struct access *repr = VEC_index (access_p, representatives, i);
3362 if (repr && !no_accesses_p (repr))
3364 if (repr->grp_scalar_ptr)
3366 adjustments_count++;
3367 if (repr->grp_not_necessarilly_dereferenced
3368 || repr->grp_maybe_modified)
3369 VEC_replace (access_p, representatives, i, NULL);
3373 sra_stats.scalar_by_ref_to_by_val++;
3378 int new_components = decide_one_param_reduction (repr);
3380 if (new_components == 0)
3382 VEC_replace (access_p, representatives, i, NULL);
3383 adjustments_count++;
3387 adjustments_count += new_components;
3388 sra_stats.aggregate_params_reduced++;
3389 sra_stats.param_reductions_created += new_components;
3396 if (no_accesses_p (repr))
3399 sra_stats.deleted_unused_parameters++;
3401 adjustments_count++;
3405 if (!proceed && dump_file)
3406 fprintf (dump_file, "NOT proceeding to change params.\n");
3409 adjustments = turn_representatives_into_adjustments (representatives,
3414 VEC_free (access_p, heap, representatives);
3418 /* If a parameter replacement identified by ADJ does not yet exist in the form
3419 of declaration, create it and record it, otherwise return the previously
3423 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3426 if (!adj->new_ssa_base)
3428 char *pretty_name = make_fancy_name (adj->base);
3430 repl = make_rename_temp (TREE_TYPE (adj->base), "ISR");
3431 DECL_NAME (repl) = get_identifier (pretty_name);
3432 obstack_free (&name_obstack, pretty_name);
3435 add_referenced_var (repl);
3436 adj->new_ssa_base = repl;
3439 repl = adj->new_ssa_base;
3443 /* Find the first adjustment for a particular parameter BASE in a vector of
3444 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3447 static struct ipa_parm_adjustment *
3448 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3452 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3453 for (i = 0; i < len; i++)
3455 struct ipa_parm_adjustment *adj;
3457 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3458 if (!adj->copy_param && adj->base == base)
3465 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3466 parameter which is to be removed because its value is not used, replace the
3467 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3468 uses too. DATA is a pointer to an adjustments vector. */
3471 replace_removed_params_ssa_names (gimple stmt, void *data)
3473 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3474 struct ipa_parm_adjustment *adj;
3475 tree lhs, decl, repl, name;
3477 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3478 if (gimple_code (stmt) == GIMPLE_PHI)
3479 lhs = gimple_phi_result (stmt);
3480 else if (is_gimple_assign (stmt))
3481 lhs = gimple_assign_lhs (stmt);
3482 else if (is_gimple_call (stmt))
3483 lhs = gimple_call_lhs (stmt);
3487 if (TREE_CODE (lhs) != SSA_NAME)
3489 decl = SSA_NAME_VAR (lhs);
3490 if (TREE_CODE (decl) != PARM_DECL)
3493 adj = get_adjustment_for_base (adjustments, decl);
3497 repl = get_replaced_param_substitute (adj);
3498 name = make_ssa_name (repl, stmt);
3502 fprintf (dump_file, "replacing an SSA name of a removed param ");
3503 print_generic_expr (dump_file, lhs, 0);
3504 fprintf (dump_file, " with ");
3505 print_generic_expr (dump_file, name, 0);
3506 fprintf (dump_file, "\n");
3509 if (is_gimple_assign (stmt))
3510 gimple_assign_set_lhs (stmt, name);
3511 else if (is_gimple_call (stmt))
3512 gimple_call_set_lhs (stmt, name);
3514 gimple_phi_set_result (stmt, name);
3516 replace_uses_by (lhs, name);
3520 /* Callback for scan_function. If the expression *EXPR should be replaced by a
3521 reduction of a parameter, do so. DATA is a pointer to a vector of
3525 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3526 bool write ATTRIBUTE_UNUSED, void *data)
3528 ipa_parm_adjustment_vec adjustments;
3530 struct ipa_parm_adjustment *adj, *cand = NULL;
3531 HOST_WIDE_INT offset, size, max_size;
3534 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3535 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3537 if (TREE_CODE (*expr) == BIT_FIELD_REF
3538 || TREE_CODE (*expr) == IMAGPART_EXPR
3539 || TREE_CODE (*expr) == REALPART_EXPR)
3540 expr = &TREE_OPERAND (*expr, 0);
3541 while (TREE_CODE (*expr) == NOP_EXPR
3542 || TREE_CODE (*expr) == VIEW_CONVERT_EXPR)
3543 expr = &TREE_OPERAND (*expr, 0);
3545 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3546 if (!base || size == -1 || max_size == -1)
3549 if (INDIRECT_REF_P (base))
3550 base = TREE_OPERAND (base, 0);
3552 base = get_ssa_base_param (base);
3553 if (!base || TREE_CODE (base) != PARM_DECL)
3556 for (i = 0; i < len; i++)
3558 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3560 if (adj->base == base &&
3561 (adj->offset == offset || adj->remove_param))
3567 if (!cand || cand->copy_param || cand->remove_param)
3573 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3575 folded = gimple_fold_indirect_ref (src);
3580 src = cand->reduction;
3582 if (dump_file && (dump_flags & TDF_DETAILS))
3584 fprintf (dump_file, "About to replace expr ");
3585 print_generic_expr (dump_file, *expr, 0);
3586 fprintf (dump_file, " with ");
3587 print_generic_expr (dump_file, src, 0);
3588 fprintf (dump_file, "\n");
3591 if (!useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3593 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3601 /* Callback for scan_function to process assign statements. Performs
3602 essentially the same function like sra_ipa_modify_expr. */
3604 static enum scan_assign_result
3605 sra_ipa_modify_assign (gimple *stmt_ptr,
3606 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, void *data)
3608 gimple stmt = *stmt_ptr;
3611 if (!gimple_assign_single_p (stmt))
3614 any |= sra_ipa_modify_expr (gimple_assign_rhs1_ptr (stmt), gsi, false,
3616 any |= sra_ipa_modify_expr (gimple_assign_lhs_ptr (stmt), gsi, true, data);
3618 return any ? SRA_SA_PROCESSED : SRA_SA_NONE;
3621 /* Call gimple_debug_bind_reset_value on all debug statements describing
3622 gimple register parameters that are being removed or replaced. */
3625 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3629 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3630 for (i = 0; i < len; i++)
3632 struct ipa_parm_adjustment *adj;
3633 imm_use_iterator ui;
3637 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3638 if (adj->copy_param || !is_gimple_reg (adj->base))
3640 name = gimple_default_def (cfun, adj->base);
3643 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3645 /* All other users must have been removed by scan_function. */
3646 gcc_assert (is_gimple_debug (stmt));
3647 gimple_debug_bind_reset_value (stmt);
3653 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3656 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3658 tree old_cur_fndecl = current_function_decl;
3659 struct cgraph_edge *cs;
3660 basic_block this_block;
3661 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3663 for (cs = node->callers; cs; cs = cs->next_caller)
3665 current_function_decl = cs->caller->decl;
3666 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3669 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3670 cs->caller->uid, cs->callee->uid,
3671 cgraph_node_name (cs->caller),
3672 cgraph_node_name (cs->callee));
3674 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3679 for (cs = node->callers; cs; cs = cs->next_caller)
3680 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3682 compute_inline_parameters (cs->caller);
3683 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3685 BITMAP_FREE (recomputed_callers);
3687 current_function_decl = old_cur_fndecl;
3688 FOR_EACH_BB (this_block)
3690 gimple_stmt_iterator gsi;
3692 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3694 gimple stmt = gsi_stmt (gsi);
3695 if (gimple_code (stmt) == GIMPLE_CALL
3696 && gimple_call_fndecl (stmt) == node->decl)
3699 fprintf (dump_file, "Adjusting recursive call");
3700 ipa_modify_call_arguments (NULL, stmt, adjustments);
3708 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3709 as given in ADJUSTMENTS. */
3712 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3714 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3715 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3716 replace_removed_params_ssa_names, false, adjustments);
3717 sra_ipa_reset_debug_stmts (adjustments);
3718 convert_callers (node, adjustments);
3719 cgraph_make_node_local (node);
3723 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3724 attributes, return true otherwise. NODE is the cgraph node of the current
3728 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3730 if (!cgraph_node_can_be_local_p (node))
3733 fprintf (dump_file, "Function not local to this compilation unit.\n");
3737 if (DECL_VIRTUAL_P (current_function_decl))
3740 fprintf (dump_file, "Function is a virtual method.\n");
3744 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3745 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3748 fprintf (dump_file, "Function too big to be made truly local.\n");
3756 "Function has no callers in this compilation unit.\n");
3763 fprintf (dump_file, "Function uses stdarg. \n");
3770 /* Perform early interprocedural SRA. */
3773 ipa_early_sra (void)
3775 struct cgraph_node *node = cgraph_node (current_function_decl);
3776 ipa_parm_adjustment_vec adjustments;
3779 if (!ipa_sra_preliminary_function_checks (node))
3783 sra_mode = SRA_MODE_EARLY_IPA;
3785 if (!find_param_candidates ())
3788 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3792 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3794 * last_basic_block_for_function (cfun));
3795 final_bbs = BITMAP_ALLOC (NULL);
3797 scan_function (build_access_from_expr, build_accesses_from_assign,
3799 if (encountered_apply_args)
3802 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3806 adjustments = analyze_all_param_acesses ();
3810 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3812 modify_function (node, adjustments);
3813 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3814 ret = TODO_update_ssa;
3816 statistics_counter_event (cfun, "Unused parameters deleted",
3817 sra_stats.deleted_unused_parameters);
3818 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3819 sra_stats.scalar_by_ref_to_by_val);
3820 statistics_counter_event (cfun, "Aggregate parameters broken up",
3821 sra_stats.aggregate_params_reduced);
3822 statistics_counter_event (cfun, "Aggregate parameter components created",
3823 sra_stats.param_reductions_created);
3826 BITMAP_FREE (final_bbs);
3827 free (bb_dereferences);
3829 sra_deinitialize ();
3833 /* Return if early ipa sra shall be performed. */
3835 ipa_early_sra_gate (void)
3837 return flag_ipa_sra;
3840 struct gimple_opt_pass pass_early_ipa_sra =
3844 "eipa_sra", /* name */
3845 ipa_early_sra_gate, /* gate */
3846 ipa_early_sra, /* execute */
3849 0, /* static_pass_number */
3850 TV_IPA_SRA, /* tv_id */
3851 0, /* properties_required */
3852 0, /* properties_provided */
3853 0, /* properties_destroyed */
3854 0, /* todo_flags_start */
3855 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */