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 /* ??? Some records used to be half-unions in Ada so the code treats
1235 the 3 container types the same. This has been fixed in Ada. */
1236 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1238 HOST_WIDE_INT pos, size;
1239 tree expr, *expr_ptr;
1241 if (TREE_CODE (fld) != FIELD_DECL)
1244 pos = int_bit_position (fld);
1245 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1246 tr_size = DECL_SIZE (fld);
1247 if (!tr_size || !host_integerp (tr_size, 1))
1249 size = tree_low_cst (tr_size, 1);
1250 if (pos > offset || (pos + size) <= offset)
1255 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1261 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1262 offset - pos, exp_type))
1272 tr_size = TYPE_SIZE (TREE_TYPE (type));
1273 if (!tr_size || !host_integerp (tr_size, 1))
1275 el_size = tree_low_cst (tr_size, 1);
1277 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1278 if (TREE_CODE (minidx) != INTEGER_CST)
1282 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1283 if (!integer_zerop (minidx))
1284 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1285 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1286 NULL_TREE, NULL_TREE);
1288 offset = offset % el_size;
1289 type = TREE_TYPE (type);
1304 /* Construct an expression that would reference a part of aggregate *EXPR of
1305 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1306 function only determines whether it can build such a reference without
1307 actually doing it, otherwise, the tree it points to is unshared first and
1308 then used as a base for furhter sub-references.
1310 FIXME: Eventually this should be replaced with
1311 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1312 minor rewrite of fold_stmt.
1316 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1317 tree exp_type, bool allow_ptr)
1319 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1322 *expr = unshare_expr (*expr);
1324 if (allow_ptr && POINTER_TYPE_P (type))
1326 type = TREE_TYPE (type);
1328 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1331 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1334 /* Return true iff TYPE is stdarg va_list type. */
1337 is_va_list_type (tree type)
1339 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1342 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1343 those with type which is suitable for scalarization. */
1346 find_var_candidates (void)
1349 referenced_var_iterator rvi;
1352 FOR_EACH_REFERENCED_VAR (var, rvi)
1354 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1356 type = TREE_TYPE (var);
1358 if (!AGGREGATE_TYPE_P (type)
1359 || needs_to_live_in_memory (var)
1360 || TREE_THIS_VOLATILE (var)
1361 || !COMPLETE_TYPE_P (type)
1362 || !host_integerp (TYPE_SIZE (type), 1)
1363 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1364 || type_internals_preclude_sra_p (type)
1365 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1366 we also want to schedule it rather late. Thus we ignore it in
1368 || (sra_mode == SRA_MODE_EARLY_INTRA
1369 && is_va_list_type (type)))
1372 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1374 if (dump_file && (dump_flags & TDF_DETAILS))
1376 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1377 print_generic_expr (dump_file, var, 0);
1378 fprintf (dump_file, "\n");
1386 /* Sort all accesses for the given variable, check for partial overlaps and
1387 return NULL if there are any. If there are none, pick a representative for
1388 each combination of offset and size and create a linked list out of them.
1389 Return the pointer to the first representative and make sure it is the first
1390 one in the vector of accesses. */
1392 static struct access *
1393 sort_and_splice_var_accesses (tree var)
1395 int i, j, access_count;
1396 struct access *res, **prev_acc_ptr = &res;
1397 VEC (access_p, heap) *access_vec;
1399 HOST_WIDE_INT low = -1, high = 0;
1401 access_vec = get_base_access_vector (var);
1404 access_count = VEC_length (access_p, access_vec);
1406 /* Sort by <OFFSET, SIZE>. */
1407 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1408 compare_access_positions);
1411 while (i < access_count)
1413 struct access *access = VEC_index (access_p, access_vec, i);
1414 bool grp_write = access->write;
1415 bool grp_read = !access->write;
1416 bool multiple_reads = false;
1417 bool grp_partial_lhs = access->grp_partial_lhs;
1418 bool first_scalar = is_gimple_reg_type (access->type);
1419 bool unscalarizable_region = access->grp_unscalarizable_region;
1421 if (first || access->offset >= high)
1424 low = access->offset;
1425 high = access->offset + access->size;
1427 else if (access->offset > low && access->offset + access->size > high)
1430 gcc_assert (access->offset >= low
1431 && access->offset + access->size <= high);
1434 while (j < access_count)
1436 struct access *ac2 = VEC_index (access_p, access_vec, j);
1437 if (ac2->offset != access->offset || ac2->size != access->size)
1444 multiple_reads = true;
1448 grp_partial_lhs |= ac2->grp_partial_lhs;
1449 unscalarizable_region |= ac2->grp_unscalarizable_region;
1450 relink_to_new_repr (access, ac2);
1452 /* If there are both aggregate-type and scalar-type accesses with
1453 this combination of size and offset, the comparison function
1454 should have put the scalars first. */
1455 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1456 ac2->group_representative = access;
1462 access->group_representative = access;
1463 access->grp_write = grp_write;
1464 access->grp_read = grp_read;
1465 access->grp_hint = multiple_reads;
1466 access->grp_partial_lhs = grp_partial_lhs;
1467 access->grp_unscalarizable_region = unscalarizable_region;
1468 if (access->first_link)
1469 add_access_to_work_queue (access);
1471 *prev_acc_ptr = access;
1472 prev_acc_ptr = &access->next_grp;
1475 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1479 /* Create a variable for the given ACCESS which determines the type, name and a
1480 few other properties. Return the variable declaration and store it also to
1481 ACCESS->replacement. */
1484 create_access_replacement (struct access *access)
1488 repl = create_tmp_var (access->type, "SR");
1490 add_referenced_var (repl);
1491 mark_sym_for_renaming (repl);
1493 if (!access->grp_partial_lhs
1494 && (TREE_CODE (access->type) == COMPLEX_TYPE
1495 || TREE_CODE (access->type) == VECTOR_TYPE))
1496 DECL_GIMPLE_REG_P (repl) = 1;
1498 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1499 DECL_ARTIFICIAL (repl) = 1;
1501 if (DECL_NAME (access->base)
1502 && !DECL_IGNORED_P (access->base)
1503 && !DECL_ARTIFICIAL (access->base))
1505 char *pretty_name = make_fancy_name (access->expr);
1507 DECL_NAME (repl) = get_identifier (pretty_name);
1508 obstack_free (&name_obstack, pretty_name);
1510 SET_DECL_DEBUG_EXPR (repl, access->expr);
1511 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1512 DECL_IGNORED_P (repl) = 0;
1515 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1516 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1520 fprintf (dump_file, "Created a replacement for ");
1521 print_generic_expr (dump_file, access->base, 0);
1522 fprintf (dump_file, " offset: %u, size: %u: ",
1523 (unsigned) access->offset, (unsigned) access->size);
1524 print_generic_expr (dump_file, repl, 0);
1525 fprintf (dump_file, "\n");
1527 sra_stats.replacements++;
1532 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1535 get_access_replacement (struct access *access)
1537 gcc_assert (access->grp_to_be_replaced);
1539 if (!access->replacement_decl)
1540 access->replacement_decl = create_access_replacement (access);
1541 return access->replacement_decl;
1544 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1545 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1546 to it is not "within" the root. */
1549 build_access_subtree (struct access **access)
1551 struct access *root = *access, *last_child = NULL;
1552 HOST_WIDE_INT limit = root->offset + root->size;
1554 *access = (*access)->next_grp;
1555 while (*access && (*access)->offset + (*access)->size <= limit)
1558 root->first_child = *access;
1560 last_child->next_sibling = *access;
1561 last_child = *access;
1563 build_access_subtree (access);
1567 /* Build a tree of access representatives, ACCESS is the pointer to the first
1568 one, others are linked in a list by the next_grp field. Decide about scalar
1569 replacements on the way, return true iff any are to be created. */
1572 build_access_trees (struct access *access)
1576 struct access *root = access;
1578 build_access_subtree (&access);
1579 root->next_grp = access;
1583 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1587 expr_with_var_bounded_array_refs_p (tree expr)
1589 while (handled_component_p (expr))
1591 if (TREE_CODE (expr) == ARRAY_REF
1592 && !host_integerp (array_ref_low_bound (expr), 0))
1594 expr = TREE_OPERAND (expr, 0);
1599 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1600 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1601 all sorts of access flags appropriately along the way, notably always ser
1602 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1605 analyze_access_subtree (struct access *root, bool allow_replacements,
1606 bool mark_read, bool mark_write)
1608 struct access *child;
1609 HOST_WIDE_INT limit = root->offset + root->size;
1610 HOST_WIDE_INT covered_to = root->offset;
1611 bool scalar = is_gimple_reg_type (root->type);
1612 bool hole = false, sth_created = false;
1613 bool direct_read = root->grp_read;
1616 root->grp_read = true;
1617 else if (root->grp_read)
1621 root->grp_write = true;
1622 else if (root->grp_write)
1625 if (root->grp_unscalarizable_region)
1626 allow_replacements = false;
1628 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1629 allow_replacements = false;
1631 for (child = root->first_child; child; child = child->next_sibling)
1633 if (!hole && child->offset < covered_to)
1636 covered_to += child->size;
1638 sth_created |= analyze_access_subtree (child, allow_replacements,
1639 mark_read, mark_write);
1641 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1642 hole |= !child->grp_covered;
1645 if (allow_replacements && scalar && !root->first_child
1647 || (direct_read && root->grp_write)))
1649 if (dump_file && (dump_flags & TDF_DETAILS))
1651 fprintf (dump_file, "Marking ");
1652 print_generic_expr (dump_file, root->base, 0);
1653 fprintf (dump_file, " offset: %u, size: %u: ",
1654 (unsigned) root->offset, (unsigned) root->size);
1655 fprintf (dump_file, " to be replaced.\n");
1658 root->grp_to_be_replaced = 1;
1662 else if (covered_to < limit)
1665 if (sth_created && !hole)
1667 root->grp_covered = 1;
1670 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1671 root->grp_unscalarized_data = 1; /* not covered and written to */
1677 /* Analyze all access trees linked by next_grp by the means of
1678 analyze_access_subtree. */
1680 analyze_access_trees (struct access *access)
1686 if (analyze_access_subtree (access, true, false, false))
1688 access = access->next_grp;
1694 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1695 SIZE would conflict with an already existing one. If exactly such a child
1696 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1699 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1700 HOST_WIDE_INT size, struct access **exact_match)
1702 struct access *child;
1704 for (child = lacc->first_child; child; child = child->next_sibling)
1706 if (child->offset == norm_offset && child->size == size)
1708 *exact_match = child;
1712 if (child->offset < norm_offset + size
1713 && child->offset + child->size > norm_offset)
1720 /* Create a new child access of PARENT, with all properties just like MODEL
1721 except for its offset and with its grp_write false and grp_read true.
1722 Return the new access or NULL if it cannot be created. Note that this access
1723 is created long after all splicing and sorting, it's not located in any
1724 access vector and is automatically a representative of its group. */
1726 static struct access *
1727 create_artificial_child_access (struct access *parent, struct access *model,
1728 HOST_WIDE_INT new_offset)
1730 struct access *access;
1731 struct access **child;
1732 tree expr = parent->base;;
1734 gcc_assert (!model->grp_unscalarizable_region);
1736 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1737 model->type, false))
1740 access = (struct access *) pool_alloc (access_pool);
1741 memset (access, 0, sizeof (struct access));
1742 access->base = parent->base;
1743 access->expr = expr;
1744 access->offset = new_offset;
1745 access->size = model->size;
1746 access->type = model->type;
1747 access->grp_write = true;
1748 access->grp_read = false;
1750 child = &parent->first_child;
1751 while (*child && (*child)->offset < new_offset)
1752 child = &(*child)->next_sibling;
1754 access->next_sibling = *child;
1761 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1762 true if any new subaccess was created. Additionally, if RACC is a scalar
1763 access but LACC is not, change the type of the latter, if possible. */
1766 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
1768 struct access *rchild;
1769 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1772 if (is_gimple_reg_type (lacc->type)
1773 || lacc->grp_unscalarizable_region
1774 || racc->grp_unscalarizable_region)
1777 if (!lacc->first_child && !racc->first_child
1778 && is_gimple_reg_type (racc->type))
1780 tree t = lacc->base;
1782 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1786 lacc->type = racc->type;
1791 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1793 struct access *new_acc = NULL;
1794 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1796 if (rchild->grp_unscalarizable_region)
1799 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1804 rchild->grp_hint = 1;
1805 new_acc->grp_hint |= new_acc->grp_read;
1806 if (rchild->first_child)
1807 ret |= propagate_subaccesses_across_link (new_acc, rchild);
1812 /* If a (part of) a union field is on the RHS of an assignment, it can
1813 have sub-accesses which do not make sense on the LHS (PR 40351).
1814 Check that this is not the case. */
1815 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1816 rchild->type, false))
1819 rchild->grp_hint = 1;
1820 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1824 if (racc->first_child)
1825 propagate_subaccesses_across_link (new_acc, rchild);
1832 /* Propagate all subaccesses across assignment links. */
1835 propagate_all_subaccesses (void)
1837 while (work_queue_head)
1839 struct access *racc = pop_access_from_work_queue ();
1840 struct assign_link *link;
1842 gcc_assert (racc->first_link);
1844 for (link = racc->first_link; link; link = link->next)
1846 struct access *lacc = link->lacc;
1848 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1850 lacc = lacc->group_representative;
1851 if (propagate_subaccesses_across_link (lacc, racc)
1852 && lacc->first_link)
1853 add_access_to_work_queue (lacc);
1858 /* Go through all accesses collected throughout the (intraprocedural) analysis
1859 stage, exclude overlapping ones, identify representatives and build trees
1860 out of them, making decisions about scalarization on the way. Return true
1861 iff there are any to-be-scalarized variables after this stage. */
1864 analyze_all_variable_accesses (void)
1867 referenced_var_iterator rvi;
1870 FOR_EACH_REFERENCED_VAR (var, rvi)
1871 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1873 struct access *access;
1875 access = sort_and_splice_var_accesses (var);
1877 build_access_trees (access);
1879 disqualify_candidate (var,
1880 "No or inhibitingly overlapping accesses.");
1883 propagate_all_subaccesses ();
1885 FOR_EACH_REFERENCED_VAR (var, rvi)
1886 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1888 struct access *access = get_first_repr_for_decl (var);
1890 if (analyze_access_trees (access))
1893 if (dump_file && (dump_flags & TDF_DETAILS))
1895 fprintf (dump_file, "\nAccess trees for ");
1896 print_generic_expr (dump_file, var, 0);
1897 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1898 dump_access_tree (dump_file, access);
1899 fprintf (dump_file, "\n");
1903 disqualify_candidate (var, "No scalar replacements to be created.");
1908 statistics_counter_event (cfun, "Scalarized aggregates", res);
1915 /* Return true iff a reference statement into aggregate AGG can be built for
1916 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1917 or a child of its sibling. TOP_OFFSET is the offset from the processed
1918 access subtree that has to be subtracted from offset of each access. */
1921 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1922 HOST_WIDE_INT top_offset)
1926 if (access->grp_to_be_replaced
1927 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1928 access->offset - top_offset,
1929 access->type, false))
1932 if (access->first_child
1933 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1937 access = access->next_sibling;
1944 /* Generate statements copying scalar replacements of accesses within a subtree
1945 into or out of AGG. ACCESS is the first child of the root of the subtree to
1946 be processed. AGG is an aggregate type expression (can be a declaration but
1947 does not have to be, it can for example also be an indirect_ref).
1948 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1949 from offsets of individual accesses to get corresponding offsets for AGG.
1950 If CHUNK_SIZE is non-null, copy only replacements in the interval
1951 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1952 statement iterator used to place the new statements. WRITE should be true
1953 when the statements should write from AGG to the replacement and false if
1954 vice versa. if INSERT_AFTER is true, new statements will be added after the
1955 current statement in GSI, they will be added before the statement
1959 generate_subtree_copies (struct access *access, tree agg,
1960 HOST_WIDE_INT top_offset,
1961 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1962 gimple_stmt_iterator *gsi, bool write,
1969 if (chunk_size && access->offset >= start_offset + chunk_size)
1972 if (access->grp_to_be_replaced
1974 || access->offset + access->size > start_offset))
1976 tree repl = get_access_replacement (access);
1980 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1981 access->offset - top_offset,
1982 access->type, false);
1983 gcc_assert (ref_found);
1987 if (access->grp_partial_lhs)
1988 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
1990 insert_after ? GSI_NEW_STMT
1992 stmt = gimple_build_assign (repl, expr);
1996 TREE_NO_WARNING (repl) = 1;
1997 if (access->grp_partial_lhs)
1998 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2000 insert_after ? GSI_NEW_STMT
2002 stmt = gimple_build_assign (expr, repl);
2006 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2008 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2010 sra_stats.subtree_copies++;
2013 if (access->first_child)
2014 generate_subtree_copies (access->first_child, agg, top_offset,
2015 start_offset, chunk_size, gsi,
2016 write, insert_after);
2018 access = access->next_sibling;
2023 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2024 the root of the subtree to be processed. GSI is the statement iterator used
2025 for inserting statements which are added after the current statement if
2026 INSERT_AFTER is true or before it otherwise. */
2029 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2033 struct access *child;
2035 if (access->grp_to_be_replaced)
2039 stmt = gimple_build_assign (get_access_replacement (access),
2040 fold_convert (access->type,
2041 integer_zero_node));
2043 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2045 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2049 for (child = access->first_child; child; child = child->next_sibling)
2050 init_subtree_with_zero (child, gsi, insert_after);
2053 /* Search for an access representative for the given expression EXPR and
2054 return it or NULL if it cannot be found. */
2056 static struct access *
2057 get_access_for_expr (tree expr)
2059 HOST_WIDE_INT offset, size, max_size;
2062 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2063 a different size than the size of its argument and we need the latter
2065 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2066 expr = TREE_OPERAND (expr, 0);
2068 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2069 if (max_size == -1 || !DECL_P (base))
2072 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2075 return get_var_base_offset_size_access (base, offset, max_size);
2078 /* Callback for scan_function. Replace the expression EXPR with a scalar
2079 replacement if there is one and generate other statements to do type
2080 conversion or subtree copying if necessary. GSI is used to place newly
2081 created statements, WRITE is true if the expression is being written to (it
2082 is on a LHS of a statement or output in an assembly statement). */
2085 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2086 void *data ATTRIBUTE_UNUSED)
2088 struct access *access;
2091 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2094 expr = &TREE_OPERAND (*expr, 0);
2099 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2100 expr = &TREE_OPERAND (*expr, 0);
2101 access = get_access_for_expr (*expr);
2104 type = TREE_TYPE (*expr);
2106 if (access->grp_to_be_replaced)
2108 tree repl = get_access_replacement (access);
2109 /* If we replace a non-register typed access simply use the original
2110 access expression to extract the scalar component afterwards.
2111 This happens if scalarizing a function return value or parameter
2112 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2113 gcc.c-torture/compile/20011217-1.c. */
2114 if (!is_gimple_reg_type (type))
2119 tree ref = unshare_expr (access->expr);
2120 if (access->grp_partial_lhs)
2121 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2122 false, GSI_NEW_STMT);
2123 stmt = gimple_build_assign (repl, ref);
2124 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2128 if (access->grp_partial_lhs)
2129 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2130 true, GSI_SAME_STMT);
2131 stmt = gimple_build_assign (unshare_expr (access->expr), repl);
2132 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2137 gcc_assert (useless_type_conversion_p (type, access->type));
2143 if (access->first_child)
2145 HOST_WIDE_INT start_offset, chunk_size;
2147 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2148 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2150 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2151 start_offset = access->offset
2152 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2155 start_offset = chunk_size = 0;
2157 generate_subtree_copies (access->first_child, access->base, 0,
2158 start_offset, chunk_size, gsi, write, write);
2163 /* Where scalar replacements of the RHS have been written to when a replacement
2164 of a LHS of an assigments cannot be direclty loaded from a replacement of
2166 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2167 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2168 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2170 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2171 base aggregate if there are unscalarized data or directly to LHS
2174 static enum unscalarized_data_handling
2175 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2176 gimple_stmt_iterator *gsi)
2178 if (top_racc->grp_unscalarized_data)
2180 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2182 return SRA_UDH_RIGHT;
2186 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2187 0, 0, gsi, false, false);
2188 return SRA_UDH_LEFT;
2193 /* Try to generate statements to load all sub-replacements in an access
2194 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2195 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2196 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2197 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2198 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2199 the rhs top aggregate has already been refreshed by contents of its scalar
2200 reductions and is set to true if this function has to do it. */
2203 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2204 HOST_WIDE_INT left_offset,
2205 HOST_WIDE_INT right_offset,
2206 gimple_stmt_iterator *old_gsi,
2207 gimple_stmt_iterator *new_gsi,
2208 enum unscalarized_data_handling *refreshed,
2211 location_t loc = EXPR_LOCATION (lacc->expr);
2214 if (lacc->grp_to_be_replaced)
2216 struct access *racc;
2217 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2221 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2222 if (racc && racc->grp_to_be_replaced)
2224 rhs = get_access_replacement (racc);
2225 if (!useless_type_conversion_p (lacc->type, racc->type))
2226 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2232 /* No suitable access on the right hand side, need to load from
2233 the aggregate. See if we have to update it first... */
2234 if (*refreshed == SRA_UDH_NONE)
2235 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2238 if (*refreshed == SRA_UDH_LEFT)
2239 rhs = unshare_expr (lacc->expr);
2242 rhs = top_racc->base;
2243 repl_found = build_ref_for_offset (&rhs,
2244 TREE_TYPE (top_racc->base),
2245 offset, lacc->type, false);
2246 gcc_assert (repl_found);
2250 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2251 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2253 sra_stats.subreplacements++;
2255 else if (*refreshed == SRA_UDH_NONE
2256 && lacc->grp_read && !lacc->grp_covered)
2257 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2260 if (lacc->first_child)
2261 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2262 left_offset, right_offset,
2263 old_gsi, new_gsi, refreshed, lhs);
2264 lacc = lacc->next_sibling;
2269 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2270 to the assignment and GSI is the statement iterator pointing at it. Returns
2271 the same values as sra_modify_assign. */
2273 static enum scan_assign_result
2274 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2276 tree lhs = gimple_assign_lhs (*stmt);
2279 acc = get_access_for_expr (lhs);
2283 if (VEC_length (constructor_elt,
2284 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2286 /* I have never seen this code path trigger but if it can happen the
2287 following should handle it gracefully. */
2288 if (access_has_children_p (acc))
2289 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2291 return SRA_SA_PROCESSED;
2294 if (acc->grp_covered)
2296 init_subtree_with_zero (acc, gsi, false);
2297 unlink_stmt_vdef (*stmt);
2298 gsi_remove (gsi, true);
2299 return SRA_SA_REMOVED;
2303 init_subtree_with_zero (acc, gsi, true);
2304 return SRA_SA_PROCESSED;
2309 /* Callback of scan_function to process assign statements. It examines both
2310 sides of the statement, replaces them with a scalare replacement if there is
2311 one and generating copying of replacements if scalarized aggregates have been
2312 used in the assignment. STMT is a pointer to the assign statement, GSI is
2313 used to hold generated statements for type conversions and subtree
2316 static enum scan_assign_result
2317 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2318 void *data ATTRIBUTE_UNUSED)
2320 struct access *lacc, *racc;
2322 bool modify_this_stmt = false;
2323 bool force_gimple_rhs = false;
2324 location_t loc = gimple_location (*stmt);
2326 if (!gimple_assign_single_p (*stmt))
2328 lhs = gimple_assign_lhs (*stmt);
2329 rhs = gimple_assign_rhs1 (*stmt);
2331 if (TREE_CODE (rhs) == CONSTRUCTOR)
2332 return sra_modify_constructor_assign (stmt, gsi);
2334 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2335 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2336 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2338 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2340 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2342 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2345 lacc = get_access_for_expr (lhs);
2346 racc = get_access_for_expr (rhs);
2350 if (lacc && lacc->grp_to_be_replaced)
2352 lhs = get_access_replacement (lacc);
2353 gimple_assign_set_lhs (*stmt, lhs);
2354 modify_this_stmt = true;
2355 if (lacc->grp_partial_lhs)
2356 force_gimple_rhs = true;
2360 if (racc && racc->grp_to_be_replaced)
2362 rhs = get_access_replacement (racc);
2363 modify_this_stmt = true;
2364 if (racc->grp_partial_lhs)
2365 force_gimple_rhs = true;
2369 if (modify_this_stmt)
2371 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2373 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2374 ??? This should move to fold_stmt which we simply should
2375 call after building a VIEW_CONVERT_EXPR here. */
2376 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2377 && !access_has_children_p (lacc))
2380 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2381 TREE_TYPE (rhs), false))
2384 gimple_assign_set_lhs (*stmt, expr);
2387 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2388 && !access_has_children_p (racc))
2391 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2392 TREE_TYPE (lhs), false))
2395 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2397 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2398 if (!is_gimple_reg (lhs))
2399 force_gimple_rhs = true;
2403 if (force_gimple_rhs)
2404 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2405 true, GSI_SAME_STMT);
2406 if (gimple_assign_rhs1 (*stmt) != rhs)
2408 gimple_assign_set_rhs_from_tree (gsi, rhs);
2409 gcc_assert (*stmt == gsi_stmt (*gsi));
2413 /* From this point on, the function deals with assignments in between
2414 aggregates when at least one has scalar reductions of some of its
2415 components. There are three possible scenarios: Both the LHS and RHS have
2416 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2418 In the first case, we would like to load the LHS components from RHS
2419 components whenever possible. If that is not possible, we would like to
2420 read it directly from the RHS (after updating it by storing in it its own
2421 components). If there are some necessary unscalarized data in the LHS,
2422 those will be loaded by the original assignment too. If neither of these
2423 cases happen, the original statement can be removed. Most of this is done
2424 by load_assign_lhs_subreplacements.
2426 In the second case, we would like to store all RHS scalarized components
2427 directly into LHS and if they cover the aggregate completely, remove the
2428 statement too. In the third case, we want the LHS components to be loaded
2429 directly from the RHS (DSE will remove the original statement if it
2432 This is a bit complex but manageable when types match and when unions do
2433 not cause confusion in a way that we cannot really load a component of LHS
2434 from the RHS or vice versa (the access representing this level can have
2435 subaccesses that are accessible only through a different union field at a
2436 higher level - different from the one used in the examined expression).
2439 Therefore, I specially handle a fourth case, happening when there is a
2440 specific type cast or it is impossible to locate a scalarized subaccess on
2441 the other side of the expression. If that happens, I simply "refresh" the
2442 RHS by storing in it is scalarized components leave the original statement
2443 there to do the copying and then load the scalar replacements of the LHS.
2444 This is what the first branch does. */
2446 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2447 || (access_has_children_p (racc)
2448 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2449 || (access_has_children_p (lacc)
2450 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2452 if (access_has_children_p (racc))
2453 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2455 if (access_has_children_p (lacc))
2456 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2458 sra_stats.separate_lhs_rhs_handling++;
2462 if (access_has_children_p (lacc) && access_has_children_p (racc))
2464 gimple_stmt_iterator orig_gsi = *gsi;
2465 enum unscalarized_data_handling refreshed;
2467 if (lacc->grp_read && !lacc->grp_covered)
2468 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2470 refreshed = SRA_UDH_NONE;
2472 load_assign_lhs_subreplacements (lacc->first_child, racc,
2473 lacc->offset, racc->offset,
2474 &orig_gsi, gsi, &refreshed, lhs);
2475 if (refreshed != SRA_UDH_RIGHT)
2477 if (*stmt == gsi_stmt (*gsi))
2480 unlink_stmt_vdef (*stmt);
2481 gsi_remove (&orig_gsi, true);
2482 sra_stats.deleted++;
2483 return SRA_SA_REMOVED;
2488 if (access_has_children_p (racc))
2490 if (!racc->grp_unscalarized_data)
2492 generate_subtree_copies (racc->first_child, lhs,
2493 racc->offset, 0, 0, gsi,
2495 gcc_assert (*stmt == gsi_stmt (*gsi));
2496 unlink_stmt_vdef (*stmt);
2497 gsi_remove (gsi, true);
2498 sra_stats.deleted++;
2499 return SRA_SA_REMOVED;
2502 generate_subtree_copies (racc->first_child, lhs,
2503 racc->offset, 0, 0, gsi, false, true);
2505 else if (access_has_children_p (lacc))
2506 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2507 0, 0, gsi, true, true);
2510 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2513 /* Generate statements initializing scalar replacements of parts of function
2517 initialize_parameter_reductions (void)
2519 gimple_stmt_iterator gsi;
2520 gimple_seq seq = NULL;
2523 for (parm = DECL_ARGUMENTS (current_function_decl);
2525 parm = TREE_CHAIN (parm))
2527 VEC (access_p, heap) *access_vec;
2528 struct access *access;
2530 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2532 access_vec = get_base_access_vector (parm);
2538 seq = gimple_seq_alloc ();
2539 gsi = gsi_start (seq);
2542 for (access = VEC_index (access_p, access_vec, 0);
2544 access = access->next_grp)
2545 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2549 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2552 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2553 it reveals there are components of some aggregates to be scalarized, it runs
2554 the required transformations. */
2556 perform_intra_sra (void)
2561 if (!find_var_candidates ())
2564 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2568 if (!analyze_all_variable_accesses ())
2571 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2572 initialize_parameter_reductions ();
2574 statistics_counter_event (cfun, "Scalar replacements created",
2575 sra_stats.replacements);
2576 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2577 statistics_counter_event (cfun, "Subtree copy stmts",
2578 sra_stats.subtree_copies);
2579 statistics_counter_event (cfun, "Subreplacement stmts",
2580 sra_stats.subreplacements);
2581 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2582 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2583 sra_stats.separate_lhs_rhs_handling);
2585 ret = TODO_update_ssa;
2588 sra_deinitialize ();
2592 /* Perform early intraprocedural SRA. */
2594 early_intra_sra (void)
2596 sra_mode = SRA_MODE_EARLY_INTRA;
2597 return perform_intra_sra ();
2600 /* Perform "late" intraprocedural SRA. */
2602 late_intra_sra (void)
2604 sra_mode = SRA_MODE_INTRA;
2605 return perform_intra_sra ();
2610 gate_intra_sra (void)
2612 return flag_tree_sra != 0;
2616 struct gimple_opt_pass pass_sra_early =
2621 gate_intra_sra, /* gate */
2622 early_intra_sra, /* execute */
2625 0, /* static_pass_number */
2626 TV_TREE_SRA, /* tv_id */
2627 PROP_cfg | PROP_ssa, /* properties_required */
2628 0, /* properties_provided */
2629 0, /* properties_destroyed */
2630 0, /* todo_flags_start */
2634 | TODO_verify_ssa /* todo_flags_finish */
2638 struct gimple_opt_pass pass_sra =
2643 gate_intra_sra, /* gate */
2644 late_intra_sra, /* execute */
2647 0, /* static_pass_number */
2648 TV_TREE_SRA, /* tv_id */
2649 PROP_cfg | PROP_ssa, /* properties_required */
2650 0, /* properties_provided */
2651 0, /* properties_destroyed */
2652 TODO_update_address_taken, /* todo_flags_start */
2656 | TODO_verify_ssa /* todo_flags_finish */
2661 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2665 is_unused_scalar_param (tree parm)
2668 return (is_gimple_reg (parm)
2669 && (!(name = gimple_default_def (cfun, parm))
2670 || has_zero_uses (name)));
2673 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2674 examine whether there are any direct or otherwise infeasible ones. If so,
2675 return true, otherwise return false. PARM must be a gimple register with a
2676 non-NULL default definition. */
2679 ptr_parm_has_direct_uses (tree parm)
2681 imm_use_iterator ui;
2683 tree name = gimple_default_def (cfun, parm);
2686 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2688 if (gimple_assign_single_p (stmt))
2690 tree rhs = gimple_assign_rhs1 (stmt);
2693 else if (TREE_CODE (rhs) == ADDR_EXPR)
2697 rhs = TREE_OPERAND (rhs, 0);
2699 while (handled_component_p (rhs));
2700 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2704 else if (gimple_code (stmt) == GIMPLE_RETURN)
2706 tree t = gimple_return_retval (stmt);
2710 else if (is_gimple_call (stmt))
2713 for (i = 0; i < gimple_call_num_args (stmt); i++)
2715 tree arg = gimple_call_arg (stmt, i);
2723 else if (!is_gimple_debug (stmt))
2727 BREAK_FROM_IMM_USE_STMT (ui);
2733 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2734 them in candidate_bitmap. Note that these do not necessarily include
2735 parameter which are unused and thus can be removed. Return true iff any
2736 such candidate has been found. */
2739 find_param_candidates (void)
2745 for (parm = DECL_ARGUMENTS (current_function_decl);
2747 parm = TREE_CHAIN (parm))
2749 tree type = TREE_TYPE (parm);
2753 if (TREE_THIS_VOLATILE (parm)
2754 || TREE_ADDRESSABLE (parm)
2755 || is_va_list_type (type))
2758 if (is_unused_scalar_param (parm))
2764 if (POINTER_TYPE_P (type))
2766 type = TREE_TYPE (type);
2768 if (TREE_CODE (type) == FUNCTION_TYPE
2769 || TYPE_VOLATILE (type)
2770 || !is_gimple_reg (parm)
2771 || is_va_list_type (type)
2772 || ptr_parm_has_direct_uses (parm))
2775 else if (!AGGREGATE_TYPE_P (type))
2778 if (!COMPLETE_TYPE_P (type)
2779 || !host_integerp (TYPE_SIZE (type), 1)
2780 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2781 || (AGGREGATE_TYPE_P (type)
2782 && type_internals_preclude_sra_p (type)))
2785 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2787 if (dump_file && (dump_flags & TDF_DETAILS))
2789 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2790 print_generic_expr (dump_file, parm, 0);
2791 fprintf (dump_file, "\n");
2795 func_param_count = count;
2799 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2803 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2806 struct access *repr = (struct access *) data;
2808 repr->grp_maybe_modified = 1;
2812 /* Analyze what representatives (in linked lists accessible from
2813 REPRESENTATIVES) can be modified by side effects of statements in the
2814 current function. */
2817 analyze_modified_params (VEC (access_p, heap) *representatives)
2821 for (i = 0; i < func_param_count; i++)
2823 struct access *repr = VEC_index (access_p, representatives, i);
2824 VEC (access_p, heap) *access_vec;
2825 int j, access_count;
2828 if (!repr || no_accesses_p (repr))
2831 if (!POINTER_TYPE_P (TREE_TYPE (parm))
2832 || repr->grp_maybe_modified)
2835 access_vec = get_base_access_vector (parm);
2836 access_count = VEC_length (access_p, access_vec);
2837 for (j = 0; j < access_count; j++)
2839 struct access *access;
2842 /* All accesses are read ones, otherwise grp_maybe_modified would be
2844 access = VEC_index (access_p, access_vec, j);
2845 ao_ref_init (&ar, access->expr);
2846 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2847 mark_maybe_modified, repr, NULL);
2848 if (repr->grp_maybe_modified)
2854 /* Propagate distances in bb_dereferences in the opposite direction than the
2855 control flow edges, in each step storing the maximum of the current value
2856 and the minimum of all successors. These steps are repeated until the table
2857 stabilizes. Note that BBs which might terminate the functions (according to
2858 final_bbs bitmap) never updated in this way. */
2861 propagate_dereference_distances (void)
2863 VEC (basic_block, heap) *queue;
2866 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2867 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2870 VEC_quick_push (basic_block, queue, bb);
2874 while (!VEC_empty (basic_block, queue))
2878 bool change = false;
2881 bb = VEC_pop (basic_block, queue);
2884 if (bitmap_bit_p (final_bbs, bb->index))
2887 for (i = 0; i < func_param_count; i++)
2889 int idx = bb->index * func_param_count + i;
2891 HOST_WIDE_INT inh = 0;
2893 FOR_EACH_EDGE (e, ei, bb->succs)
2895 int succ_idx = e->dest->index * func_param_count + i;
2897 if (e->src == EXIT_BLOCK_PTR)
2903 inh = bb_dereferences [succ_idx];
2905 else if (bb_dereferences [succ_idx] < inh)
2906 inh = bb_dereferences [succ_idx];
2909 if (!first && bb_dereferences[idx] < inh)
2911 bb_dereferences[idx] = inh;
2916 if (change && !bitmap_bit_p (final_bbs, bb->index))
2917 FOR_EACH_EDGE (e, ei, bb->preds)
2922 e->src->aux = e->src;
2923 VEC_quick_push (basic_block, queue, e->src);
2927 VEC_free (basic_block, heap, queue);
2930 /* Dump a dereferences TABLE with heading STR to file F. */
2933 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2937 fprintf (dump_file, str);
2938 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2940 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2941 if (bb != EXIT_BLOCK_PTR)
2944 for (i = 0; i < func_param_count; i++)
2946 int idx = bb->index * func_param_count + i;
2947 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
2952 fprintf (dump_file, "\n");
2955 /* Determine what (parts of) parameters passed by reference that are not
2956 assigned to are not certainly dereferenced in this function and thus the
2957 dereferencing cannot be safely moved to the caller without potentially
2958 introducing a segfault. Mark such REPRESENTATIVES as
2959 grp_not_necessarilly_dereferenced.
2961 The dereferenced maximum "distance," i.e. the offset + size of the accessed
2962 part is calculated rather than simple booleans are calculated for each
2963 pointer parameter to handle cases when only a fraction of the whole
2964 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
2967 The maximum dereference distances for each pointer parameter and BB are
2968 already stored in bb_dereference. This routine simply propagates these
2969 values upwards by propagate_dereference_distances and then compares the
2970 distances of individual parameters in the ENTRY BB to the equivalent
2971 distances of each representative of a (fraction of a) parameter. */
2974 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
2978 if (dump_file && (dump_flags & TDF_DETAILS))
2979 dump_dereferences_table (dump_file,
2980 "Dereference table before propagation:\n",
2983 propagate_dereference_distances ();
2985 if (dump_file && (dump_flags & TDF_DETAILS))
2986 dump_dereferences_table (dump_file,
2987 "Dereference table after propagation:\n",
2990 for (i = 0; i < func_param_count; i++)
2992 struct access *repr = VEC_index (access_p, representatives, i);
2993 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
2995 if (!repr || no_accesses_p (repr))
3000 if ((repr->offset + repr->size) > bb_dereferences[idx])
3001 repr->grp_not_necessarilly_dereferenced = 1;
3002 repr = repr->next_grp;
3008 /* Return the representative access for the parameter declaration PARM if it is
3009 a scalar passed by reference which is not written to and the pointer value
3010 is not used directly. Thus, if it is legal to dereference it in the caller
3011 and we can rule out modifications through aliases, such parameter should be
3012 turned into one passed by value. Return NULL otherwise. */
3014 static struct access *
3015 unmodified_by_ref_scalar_representative (tree parm)
3017 int i, access_count;
3018 struct access *access;
3019 VEC (access_p, heap) *access_vec;
3021 access_vec = get_base_access_vector (parm);
3022 gcc_assert (access_vec);
3023 access_count = VEC_length (access_p, access_vec);
3025 for (i = 0; i < access_count; i++)
3027 access = VEC_index (access_p, access_vec, i);
3032 access = VEC_index (access_p, access_vec, 0);
3033 access->grp_read = 1;
3034 access->grp_scalar_ptr = 1;
3038 /* Sort collected accesses for parameter PARM, identify representatives for
3039 each accessed region and link them together. Return NULL if there are
3040 different but overlapping accesses, return the special ptr value meaning
3041 there are no accesses for this parameter if that is the case and return the
3042 first representative otherwise. Set *RO_GRP if there is a group of accesses
3043 with only read (i.e. no write) accesses. */
3045 static struct access *
3046 splice_param_accesses (tree parm, bool *ro_grp)
3048 int i, j, access_count, group_count;
3049 int agg_size, total_size = 0;
3050 struct access *access, *res, **prev_acc_ptr = &res;
3051 VEC (access_p, heap) *access_vec;
3053 access_vec = get_base_access_vector (parm);
3055 return &no_accesses_representant;
3056 access_count = VEC_length (access_p, access_vec);
3058 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3059 compare_access_positions);
3064 while (i < access_count)
3067 access = VEC_index (access_p, access_vec, i);
3068 modification = access->write;
3070 /* Access is about to become group representative unless we find some
3071 nasty overlap which would preclude us from breaking this parameter
3075 while (j < access_count)
3077 struct access *ac2 = VEC_index (access_p, access_vec, j);
3078 if (ac2->offset != access->offset)
3080 /* All or nothing law for parameters. */
3081 if (access->offset + access->size > ac2->offset)
3086 else if (ac2->size != access->size)
3089 modification |= ac2->write;
3094 access->grp_maybe_modified = modification;
3097 *prev_acc_ptr = access;
3098 prev_acc_ptr = &access->next_grp;
3099 total_size += access->size;
3103 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3104 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3106 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3107 if (total_size >= agg_size)
3110 gcc_assert (group_count > 0);
3114 /* Decide whether parameters with representative accesses given by REPR should
3115 be reduced into components. */
3118 decide_one_param_reduction (struct access *repr)
3120 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3125 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3126 gcc_assert (cur_parm_size > 0);
3128 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3131 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3136 agg_size = cur_parm_size;
3142 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3143 print_generic_expr (dump_file, parm, 0);
3144 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3145 for (acc = repr; acc; acc = acc->next_grp)
3146 dump_access (dump_file, acc, true);
3150 new_param_count = 0;
3152 for (; repr; repr = repr->next_grp)
3154 gcc_assert (parm == repr->base);
3157 if (!by_ref || (!repr->grp_maybe_modified
3158 && !repr->grp_not_necessarilly_dereferenced))
3159 total_size += repr->size;
3161 total_size += cur_parm_size;
3164 gcc_assert (new_param_count > 0);
3166 if (optimize_function_for_size_p (cfun))
3167 parm_size_limit = cur_parm_size;
3169 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3172 if (total_size < agg_size
3173 && total_size <= parm_size_limit)
3176 fprintf (dump_file, " ....will be split into %i components\n",
3178 return new_param_count;
3184 /* The order of the following enums is important, we need to do extra work for
3185 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3186 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3187 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3189 /* Identify representatives of all accesses to all candidate parameters for
3190 IPA-SRA. Return result based on what representatives have been found. */
3192 static enum ipa_splicing_result
3193 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3195 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3197 struct access *repr;
3199 *representatives = VEC_alloc (access_p, heap, func_param_count);
3201 for (parm = DECL_ARGUMENTS (current_function_decl);
3203 parm = TREE_CHAIN (parm))
3205 if (is_unused_scalar_param (parm))
3207 VEC_quick_push (access_p, *representatives,
3208 &no_accesses_representant);
3209 if (result == NO_GOOD_ACCESS)
3210 result = UNUSED_PARAMS;
3212 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3213 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3214 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3216 repr = unmodified_by_ref_scalar_representative (parm);
3217 VEC_quick_push (access_p, *representatives, repr);
3219 result = UNMODIF_BY_REF_ACCESSES;
3221 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3223 bool ro_grp = false;
3224 repr = splice_param_accesses (parm, &ro_grp);
3225 VEC_quick_push (access_p, *representatives, repr);
3227 if (repr && !no_accesses_p (repr))
3229 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3232 result = UNMODIF_BY_REF_ACCESSES;
3233 else if (result < MODIF_BY_REF_ACCESSES)
3234 result = MODIF_BY_REF_ACCESSES;
3236 else if (result < BY_VAL_ACCESSES)
3237 result = BY_VAL_ACCESSES;
3239 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3240 result = UNUSED_PARAMS;
3243 VEC_quick_push (access_p, *representatives, NULL);
3246 if (result == NO_GOOD_ACCESS)
3248 VEC_free (access_p, heap, *representatives);
3249 *representatives = NULL;
3250 return NO_GOOD_ACCESS;
3256 /* Return the index of BASE in PARMS. Abort if it is not found. */
3259 get_param_index (tree base, VEC(tree, heap) *parms)
3263 len = VEC_length (tree, parms);
3264 for (i = 0; i < len; i++)
3265 if (VEC_index (tree, parms, i) == base)
3270 /* Convert the decisions made at the representative level into compact
3271 parameter adjustments. REPRESENTATIVES are pointers to first
3272 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3273 final number of adjustments. */
3275 static ipa_parm_adjustment_vec
3276 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3277 int adjustments_count)
3279 VEC (tree, heap) *parms;
3280 ipa_parm_adjustment_vec adjustments;
3284 gcc_assert (adjustments_count > 0);
3285 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3286 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3287 parm = DECL_ARGUMENTS (current_function_decl);
3288 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3290 struct access *repr = VEC_index (access_p, representatives, i);
3292 if (!repr || no_accesses_p (repr))
3294 struct ipa_parm_adjustment *adj;
3296 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3297 memset (adj, 0, sizeof (*adj));
3298 adj->base_index = get_param_index (parm, parms);
3301 adj->copy_param = 1;
3303 adj->remove_param = 1;
3307 struct ipa_parm_adjustment *adj;
3308 int index = get_param_index (parm, parms);
3310 for (; repr; repr = repr->next_grp)
3312 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3313 memset (adj, 0, sizeof (*adj));
3314 gcc_assert (repr->base == parm);
3315 adj->base_index = index;
3316 adj->base = repr->base;
3317 adj->type = repr->type;
3318 adj->offset = repr->offset;
3319 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3320 && (repr->grp_maybe_modified
3321 || repr->grp_not_necessarilly_dereferenced));
3326 VEC_free (tree, heap, parms);
3330 /* Analyze the collected accesses and produce a plan what to do with the
3331 parameters in the form of adjustments, NULL meaning nothing. */
3333 static ipa_parm_adjustment_vec
3334 analyze_all_param_acesses (void)
3336 enum ipa_splicing_result repr_state;
3337 bool proceed = false;
3338 int i, adjustments_count = 0;
3339 VEC (access_p, heap) *representatives;
3340 ipa_parm_adjustment_vec adjustments;
3342 repr_state = splice_all_param_accesses (&representatives);
3343 if (repr_state == NO_GOOD_ACCESS)
3346 /* If there are any parameters passed by reference which are not modified
3347 directly, we need to check whether they can be modified indirectly. */
3348 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3350 analyze_caller_dereference_legality (representatives);
3351 analyze_modified_params (representatives);
3354 for (i = 0; i < func_param_count; i++)
3356 struct access *repr = VEC_index (access_p, representatives, i);
3358 if (repr && !no_accesses_p (repr))
3360 if (repr->grp_scalar_ptr)
3362 adjustments_count++;
3363 if (repr->grp_not_necessarilly_dereferenced
3364 || repr->grp_maybe_modified)
3365 VEC_replace (access_p, representatives, i, NULL);
3369 sra_stats.scalar_by_ref_to_by_val++;
3374 int new_components = decide_one_param_reduction (repr);
3376 if (new_components == 0)
3378 VEC_replace (access_p, representatives, i, NULL);
3379 adjustments_count++;
3383 adjustments_count += new_components;
3384 sra_stats.aggregate_params_reduced++;
3385 sra_stats.param_reductions_created += new_components;
3392 if (no_accesses_p (repr))
3395 sra_stats.deleted_unused_parameters++;
3397 adjustments_count++;
3401 if (!proceed && dump_file)
3402 fprintf (dump_file, "NOT proceeding to change params.\n");
3405 adjustments = turn_representatives_into_adjustments (representatives,
3410 VEC_free (access_p, heap, representatives);
3414 /* If a parameter replacement identified by ADJ does not yet exist in the form
3415 of declaration, create it and record it, otherwise return the previously
3419 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3422 if (!adj->new_ssa_base)
3424 char *pretty_name = make_fancy_name (adj->base);
3426 repl = make_rename_temp (TREE_TYPE (adj->base), "ISR");
3427 DECL_NAME (repl) = get_identifier (pretty_name);
3428 obstack_free (&name_obstack, pretty_name);
3431 add_referenced_var (repl);
3432 adj->new_ssa_base = repl;
3435 repl = adj->new_ssa_base;
3439 /* Find the first adjustment for a particular parameter BASE in a vector of
3440 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3443 static struct ipa_parm_adjustment *
3444 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3448 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3449 for (i = 0; i < len; i++)
3451 struct ipa_parm_adjustment *adj;
3453 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3454 if (!adj->copy_param && adj->base == base)
3461 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3462 parameter which is to be removed because its value is not used, replace the
3463 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3464 uses too. DATA is a pointer to an adjustments vector. */
3467 replace_removed_params_ssa_names (gimple stmt, void *data)
3469 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3470 struct ipa_parm_adjustment *adj;
3471 tree lhs, decl, repl, name;
3473 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3474 if (gimple_code (stmt) == GIMPLE_PHI)
3475 lhs = gimple_phi_result (stmt);
3476 else if (is_gimple_assign (stmt))
3477 lhs = gimple_assign_lhs (stmt);
3478 else if (is_gimple_call (stmt))
3479 lhs = gimple_call_lhs (stmt);
3483 if (TREE_CODE (lhs) != SSA_NAME)
3485 decl = SSA_NAME_VAR (lhs);
3486 if (TREE_CODE (decl) != PARM_DECL)
3489 adj = get_adjustment_for_base (adjustments, decl);
3493 repl = get_replaced_param_substitute (adj);
3494 name = make_ssa_name (repl, stmt);
3498 fprintf (dump_file, "replacing an SSA name of a removed param ");
3499 print_generic_expr (dump_file, lhs, 0);
3500 fprintf (dump_file, " with ");
3501 print_generic_expr (dump_file, name, 0);
3502 fprintf (dump_file, "\n");
3505 if (is_gimple_assign (stmt))
3506 gimple_assign_set_lhs (stmt, name);
3507 else if (is_gimple_call (stmt))
3508 gimple_call_set_lhs (stmt, name);
3510 gimple_phi_set_result (stmt, name);
3512 replace_uses_by (lhs, name);
3516 /* Callback for scan_function. If the expression *EXPR should be replaced by a
3517 reduction of a parameter, do so. DATA is a pointer to a vector of
3521 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3522 bool write ATTRIBUTE_UNUSED, void *data)
3524 ipa_parm_adjustment_vec adjustments;
3526 struct ipa_parm_adjustment *adj, *cand = NULL;
3527 HOST_WIDE_INT offset, size, max_size;
3530 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3531 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3533 if (TREE_CODE (*expr) == BIT_FIELD_REF
3534 || TREE_CODE (*expr) == IMAGPART_EXPR
3535 || TREE_CODE (*expr) == REALPART_EXPR)
3536 expr = &TREE_OPERAND (*expr, 0);
3537 while (TREE_CODE (*expr) == NOP_EXPR
3538 || TREE_CODE (*expr) == VIEW_CONVERT_EXPR)
3539 expr = &TREE_OPERAND (*expr, 0);
3541 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3542 if (!base || size == -1 || max_size == -1)
3545 if (INDIRECT_REF_P (base))
3546 base = TREE_OPERAND (base, 0);
3548 base = get_ssa_base_param (base);
3549 if (!base || TREE_CODE (base) != PARM_DECL)
3552 for (i = 0; i < len; i++)
3554 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3556 if (adj->base == base &&
3557 (adj->offset == offset || adj->remove_param))
3563 if (!cand || cand->copy_param || cand->remove_param)
3569 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3571 folded = gimple_fold_indirect_ref (src);
3576 src = cand->reduction;
3578 if (dump_file && (dump_flags & TDF_DETAILS))
3580 fprintf (dump_file, "About to replace expr ");
3581 print_generic_expr (dump_file, *expr, 0);
3582 fprintf (dump_file, " with ");
3583 print_generic_expr (dump_file, src, 0);
3584 fprintf (dump_file, "\n");
3587 if (!useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3589 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3597 /* Callback for scan_function to process assign statements. Performs
3598 essentially the same function like sra_ipa_modify_expr. */
3600 static enum scan_assign_result
3601 sra_ipa_modify_assign (gimple *stmt_ptr,
3602 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, void *data)
3604 gimple stmt = *stmt_ptr;
3607 if (!gimple_assign_single_p (stmt))
3610 any |= sra_ipa_modify_expr (gimple_assign_rhs1_ptr (stmt), gsi, false,
3612 any |= sra_ipa_modify_expr (gimple_assign_lhs_ptr (stmt), gsi, true, data);
3614 return any ? SRA_SA_PROCESSED : SRA_SA_NONE;
3617 /* Call gimple_debug_bind_reset_value on all debug statements describing
3618 gimple register parameters that are being removed or replaced. */
3621 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3625 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3626 for (i = 0; i < len; i++)
3628 struct ipa_parm_adjustment *adj;
3629 imm_use_iterator ui;
3633 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3634 if (adj->copy_param || !is_gimple_reg (adj->base))
3636 name = gimple_default_def (cfun, adj->base);
3639 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3641 /* All other users must have been removed by scan_function. */
3642 gcc_assert (is_gimple_debug (stmt));
3643 gimple_debug_bind_reset_value (stmt);
3649 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3652 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3654 tree old_cur_fndecl = current_function_decl;
3655 struct cgraph_edge *cs;
3656 basic_block this_block;
3657 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3659 for (cs = node->callers; cs; cs = cs->next_caller)
3661 current_function_decl = cs->caller->decl;
3662 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3665 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3666 cs->caller->uid, cs->callee->uid,
3667 cgraph_node_name (cs->caller),
3668 cgraph_node_name (cs->callee));
3670 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3675 for (cs = node->callers; cs; cs = cs->next_caller)
3676 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3678 compute_inline_parameters (cs->caller);
3679 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3681 BITMAP_FREE (recomputed_callers);
3683 current_function_decl = old_cur_fndecl;
3684 FOR_EACH_BB (this_block)
3686 gimple_stmt_iterator gsi;
3688 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3690 gimple stmt = gsi_stmt (gsi);
3691 if (gimple_code (stmt) == GIMPLE_CALL
3692 && gimple_call_fndecl (stmt) == node->decl)
3695 fprintf (dump_file, "Adjusting recursive call");
3696 ipa_modify_call_arguments (NULL, stmt, adjustments);
3704 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3705 as given in ADJUSTMENTS. */
3708 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3710 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3711 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3712 replace_removed_params_ssa_names, false, adjustments);
3713 sra_ipa_reset_debug_stmts (adjustments);
3714 convert_callers (node, adjustments);
3715 cgraph_make_node_local (node);
3719 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3720 attributes, return true otherwise. NODE is the cgraph node of the current
3724 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3726 if (!cgraph_node_can_be_local_p (node))
3729 fprintf (dump_file, "Function not local to this compilation unit.\n");
3733 if (DECL_VIRTUAL_P (current_function_decl))
3736 fprintf (dump_file, "Function is a virtual method.\n");
3740 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3741 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3744 fprintf (dump_file, "Function too big to be made truly local.\n");
3752 "Function has no callers in this compilation unit.\n");
3759 fprintf (dump_file, "Function uses stdarg. \n");
3766 /* Perform early interprocedural SRA. */
3769 ipa_early_sra (void)
3771 struct cgraph_node *node = cgraph_node (current_function_decl);
3772 ipa_parm_adjustment_vec adjustments;
3775 if (!ipa_sra_preliminary_function_checks (node))
3779 sra_mode = SRA_MODE_EARLY_IPA;
3781 if (!find_param_candidates ())
3784 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3788 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3790 * last_basic_block_for_function (cfun));
3791 final_bbs = BITMAP_ALLOC (NULL);
3793 scan_function (build_access_from_expr, build_accesses_from_assign,
3795 if (encountered_apply_args)
3798 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3802 adjustments = analyze_all_param_acesses ();
3806 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3808 modify_function (node, adjustments);
3809 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3810 ret = TODO_update_ssa;
3812 statistics_counter_event (cfun, "Unused parameters deleted",
3813 sra_stats.deleted_unused_parameters);
3814 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3815 sra_stats.scalar_by_ref_to_by_val);
3816 statistics_counter_event (cfun, "Aggregate parameters broken up",
3817 sra_stats.aggregate_params_reduced);
3818 statistics_counter_event (cfun, "Aggregate parameter components created",
3819 sra_stats.param_reductions_created);
3822 BITMAP_FREE (final_bbs);
3823 free (bb_dereferences);
3825 sra_deinitialize ();
3829 /* Return if early ipa sra shall be performed. */
3831 ipa_early_sra_gate (void)
3833 return flag_ipa_sra;
3836 struct gimple_opt_pass pass_early_ipa_sra =
3840 "eipa_sra", /* name */
3841 ipa_early_sra_gate, /* gate */
3842 ipa_early_sra, /* execute */
3845 0, /* static_pass_number */
3846 TV_IPA_SRA, /* tv_id */
3847 0, /* properties_required */
3848 0, /* properties_provided */
3849 0, /* properties_destroyed */
3850 0, /* todo_flags_start */
3851 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */