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 ADA records are half-unions, treat all of them the same. */
1235 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1237 HOST_WIDE_INT pos, size;
1238 tree expr, *expr_ptr;
1240 if (TREE_CODE (fld) != FIELD_DECL)
1243 pos = int_bit_position (fld);
1244 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1245 size = tree_low_cst (DECL_SIZE (fld), 1);
1246 if (pos > offset || (pos + size) <= offset)
1251 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1257 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1258 offset - pos, exp_type))
1268 tr_size = TYPE_SIZE (TREE_TYPE (type));
1269 if (!tr_size || !host_integerp (tr_size, 1))
1271 el_size = tree_low_cst (tr_size, 1);
1273 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1274 if (TREE_CODE (minidx) != INTEGER_CST)
1278 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1279 if (!integer_zerop (minidx))
1280 index = int_const_binop (PLUS_EXPR, index, minidx, 0);
1281 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1282 NULL_TREE, NULL_TREE);
1284 offset = offset % el_size;
1285 type = TREE_TYPE (type);
1300 /* Construct an expression that would reference a part of aggregate *EXPR of
1301 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1302 function only determines whether it can build such a reference without
1305 FIXME: Eventually this should be replaced with
1306 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1307 minor rewrite of fold_stmt.
1311 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1312 tree exp_type, bool allow_ptr)
1314 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1316 if (allow_ptr && POINTER_TYPE_P (type))
1318 type = TREE_TYPE (type);
1320 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1323 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1326 /* Return true iff TYPE is stdarg va_list type. */
1329 is_va_list_type (tree type)
1331 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1334 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1335 those with type which is suitable for scalarization. */
1338 find_var_candidates (void)
1341 referenced_var_iterator rvi;
1344 FOR_EACH_REFERENCED_VAR (var, rvi)
1346 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1348 type = TREE_TYPE (var);
1350 if (!AGGREGATE_TYPE_P (type)
1351 || needs_to_live_in_memory (var)
1352 || TREE_THIS_VOLATILE (var)
1353 || !COMPLETE_TYPE_P (type)
1354 || !host_integerp (TYPE_SIZE (type), 1)
1355 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1356 || type_internals_preclude_sra_p (type)
1357 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1358 we also want to schedule it rather late. Thus we ignore it in
1360 || (sra_mode == SRA_MODE_EARLY_INTRA
1361 && is_va_list_type (type)))
1364 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1366 if (dump_file && (dump_flags & TDF_DETAILS))
1368 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1369 print_generic_expr (dump_file, var, 0);
1370 fprintf (dump_file, "\n");
1378 /* Sort all accesses for the given variable, check for partial overlaps and
1379 return NULL if there are any. If there are none, pick a representative for
1380 each combination of offset and size and create a linked list out of them.
1381 Return the pointer to the first representative and make sure it is the first
1382 one in the vector of accesses. */
1384 static struct access *
1385 sort_and_splice_var_accesses (tree var)
1387 int i, j, access_count;
1388 struct access *res, **prev_acc_ptr = &res;
1389 VEC (access_p, heap) *access_vec;
1391 HOST_WIDE_INT low = -1, high = 0;
1393 access_vec = get_base_access_vector (var);
1396 access_count = VEC_length (access_p, access_vec);
1398 /* Sort by <OFFSET, SIZE>. */
1399 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1400 compare_access_positions);
1403 while (i < access_count)
1405 struct access *access = VEC_index (access_p, access_vec, i);
1406 bool grp_write = access->write;
1407 bool grp_read = !access->write;
1408 bool multiple_reads = false;
1409 bool grp_partial_lhs = access->grp_partial_lhs;
1410 bool first_scalar = is_gimple_reg_type (access->type);
1411 bool unscalarizable_region = access->grp_unscalarizable_region;
1413 if (first || access->offset >= high)
1416 low = access->offset;
1417 high = access->offset + access->size;
1419 else if (access->offset > low && access->offset + access->size > high)
1422 gcc_assert (access->offset >= low
1423 && access->offset + access->size <= high);
1426 while (j < access_count)
1428 struct access *ac2 = VEC_index (access_p, access_vec, j);
1429 if (ac2->offset != access->offset || ac2->size != access->size)
1436 multiple_reads = true;
1440 grp_partial_lhs |= ac2->grp_partial_lhs;
1441 unscalarizable_region |= ac2->grp_unscalarizable_region;
1442 relink_to_new_repr (access, ac2);
1444 /* If there are both aggregate-type and scalar-type accesses with
1445 this combination of size and offset, the comparison function
1446 should have put the scalars first. */
1447 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1448 ac2->group_representative = access;
1454 access->group_representative = access;
1455 access->grp_write = grp_write;
1456 access->grp_read = grp_read;
1457 access->grp_hint = multiple_reads;
1458 access->grp_partial_lhs = grp_partial_lhs;
1459 access->grp_unscalarizable_region = unscalarizable_region;
1460 if (access->first_link)
1461 add_access_to_work_queue (access);
1463 *prev_acc_ptr = access;
1464 prev_acc_ptr = &access->next_grp;
1467 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1471 /* Create a variable for the given ACCESS which determines the type, name and a
1472 few other properties. Return the variable declaration and store it also to
1473 ACCESS->replacement. */
1476 create_access_replacement (struct access *access)
1480 repl = create_tmp_var (access->type, "SR");
1482 add_referenced_var (repl);
1483 mark_sym_for_renaming (repl);
1485 if (!access->grp_partial_lhs
1486 && (TREE_CODE (access->type) == COMPLEX_TYPE
1487 || TREE_CODE (access->type) == VECTOR_TYPE))
1488 DECL_GIMPLE_REG_P (repl) = 1;
1490 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1491 DECL_ARTIFICIAL (repl) = 1;
1493 if (DECL_NAME (access->base)
1494 && !DECL_IGNORED_P (access->base)
1495 && !DECL_ARTIFICIAL (access->base))
1497 char *pretty_name = make_fancy_name (access->expr);
1499 DECL_NAME (repl) = get_identifier (pretty_name);
1500 obstack_free (&name_obstack, pretty_name);
1502 SET_DECL_DEBUG_EXPR (repl, access->expr);
1503 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1504 DECL_IGNORED_P (repl) = 0;
1507 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1508 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1512 fprintf (dump_file, "Created a replacement for ");
1513 print_generic_expr (dump_file, access->base, 0);
1514 fprintf (dump_file, " offset: %u, size: %u: ",
1515 (unsigned) access->offset, (unsigned) access->size);
1516 print_generic_expr (dump_file, repl, 0);
1517 fprintf (dump_file, "\n");
1519 sra_stats.replacements++;
1524 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1527 get_access_replacement (struct access *access)
1529 gcc_assert (access->grp_to_be_replaced);
1531 if (!access->replacement_decl)
1532 access->replacement_decl = create_access_replacement (access);
1533 return access->replacement_decl;
1536 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1537 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1538 to it is not "within" the root. */
1541 build_access_subtree (struct access **access)
1543 struct access *root = *access, *last_child = NULL;
1544 HOST_WIDE_INT limit = root->offset + root->size;
1546 *access = (*access)->next_grp;
1547 while (*access && (*access)->offset + (*access)->size <= limit)
1550 root->first_child = *access;
1552 last_child->next_sibling = *access;
1553 last_child = *access;
1555 build_access_subtree (access);
1559 /* Build a tree of access representatives, ACCESS is the pointer to the first
1560 one, others are linked in a list by the next_grp field. Decide about scalar
1561 replacements on the way, return true iff any are to be created. */
1564 build_access_trees (struct access *access)
1568 struct access *root = access;
1570 build_access_subtree (&access);
1571 root->next_grp = access;
1575 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1579 expr_with_var_bounded_array_refs_p (tree expr)
1581 while (handled_component_p (expr))
1583 if (TREE_CODE (expr) == ARRAY_REF
1584 && !host_integerp (array_ref_low_bound (expr), 0))
1586 expr = TREE_OPERAND (expr, 0);
1591 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1592 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1593 all sorts of access flags appropriately along the way, notably always ser
1594 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1597 analyze_access_subtree (struct access *root, bool allow_replacements,
1598 bool mark_read, bool mark_write)
1600 struct access *child;
1601 HOST_WIDE_INT limit = root->offset + root->size;
1602 HOST_WIDE_INT covered_to = root->offset;
1603 bool scalar = is_gimple_reg_type (root->type);
1604 bool hole = false, sth_created = false;
1605 bool direct_read = root->grp_read;
1608 root->grp_read = true;
1609 else if (root->grp_read)
1613 root->grp_write = true;
1614 else if (root->grp_write)
1617 if (root->grp_unscalarizable_region)
1618 allow_replacements = false;
1620 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
1621 allow_replacements = false;
1623 for (child = root->first_child; child; child = child->next_sibling)
1625 if (!hole && child->offset < covered_to)
1628 covered_to += child->size;
1630 sth_created |= analyze_access_subtree (child, allow_replacements,
1631 mark_read, mark_write);
1633 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1634 hole |= !child->grp_covered;
1637 if (allow_replacements && scalar && !root->first_child
1639 || (direct_read && root->grp_write)))
1641 if (dump_file && (dump_flags & TDF_DETAILS))
1643 fprintf (dump_file, "Marking ");
1644 print_generic_expr (dump_file, root->base, 0);
1645 fprintf (dump_file, " offset: %u, size: %u: ",
1646 (unsigned) root->offset, (unsigned) root->size);
1647 fprintf (dump_file, " to be replaced.\n");
1650 root->grp_to_be_replaced = 1;
1654 else if (covered_to < limit)
1657 if (sth_created && !hole)
1659 root->grp_covered = 1;
1662 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1663 root->grp_unscalarized_data = 1; /* not covered and written to */
1669 /* Analyze all access trees linked by next_grp by the means of
1670 analyze_access_subtree. */
1672 analyze_access_trees (struct access *access)
1678 if (analyze_access_subtree (access, true, false, false))
1680 access = access->next_grp;
1686 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1687 SIZE would conflict with an already existing one. If exactly such a child
1688 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1691 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1692 HOST_WIDE_INT size, struct access **exact_match)
1694 struct access *child;
1696 for (child = lacc->first_child; child; child = child->next_sibling)
1698 if (child->offset == norm_offset && child->size == size)
1700 *exact_match = child;
1704 if (child->offset < norm_offset + size
1705 && child->offset + child->size > norm_offset)
1712 /* Create a new child access of PARENT, with all properties just like MODEL
1713 except for its offset and with its grp_write false and grp_read true.
1714 Return the new access or NULL if it cannot be created. Note that this access
1715 is created long after all splicing and sorting, it's not located in any
1716 access vector and is automatically a representative of its group. */
1718 static struct access *
1719 create_artificial_child_access (struct access *parent, struct access *model,
1720 HOST_WIDE_INT new_offset)
1722 struct access *access;
1723 struct access **child;
1724 tree expr = parent->base;;
1726 gcc_assert (!model->grp_unscalarizable_region);
1728 if (!build_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
1729 model->type, false))
1732 access = (struct access *) pool_alloc (access_pool);
1733 memset (access, 0, sizeof (struct access));
1734 access->base = parent->base;
1735 access->expr = expr;
1736 access->offset = new_offset;
1737 access->size = model->size;
1738 access->type = model->type;
1739 access->grp_write = true;
1740 access->grp_read = false;
1742 child = &parent->first_child;
1743 while (*child && (*child)->offset < new_offset)
1744 child = &(*child)->next_sibling;
1746 access->next_sibling = *child;
1753 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1754 true if any new subaccess was created. Additionally, if RACC is a scalar
1755 access but LACC is not, change the type of the latter, if possible. */
1758 propagate_subacesses_accross_link (struct access *lacc, struct access *racc)
1760 struct access *rchild;
1761 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1764 if (is_gimple_reg_type (lacc->type)
1765 || lacc->grp_unscalarizable_region
1766 || racc->grp_unscalarizable_region)
1769 if (!lacc->first_child && !racc->first_child
1770 && is_gimple_reg_type (racc->type))
1772 tree t = lacc->base;
1774 if (build_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type,
1778 lacc->type = racc->type;
1783 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1785 struct access *new_acc = NULL;
1786 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1788 if (rchild->grp_unscalarizable_region)
1791 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1796 rchild->grp_hint = 1;
1797 new_acc->grp_hint |= new_acc->grp_read;
1798 if (rchild->first_child)
1799 ret |= propagate_subacesses_accross_link (new_acc, rchild);
1804 /* If a (part of) a union field is on the RHS of an assignment, it can
1805 have sub-accesses which do not make sense on the LHS (PR 40351).
1806 Check that this is not the case. */
1807 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1808 rchild->type, false))
1811 rchild->grp_hint = 1;
1812 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1816 if (racc->first_child)
1817 propagate_subacesses_accross_link (new_acc, rchild);
1824 /* Propagate all subaccesses across assignment links. */
1827 propagate_all_subaccesses (void)
1829 while (work_queue_head)
1831 struct access *racc = pop_access_from_work_queue ();
1832 struct assign_link *link;
1834 gcc_assert (racc->first_link);
1836 for (link = racc->first_link; link; link = link->next)
1838 struct access *lacc = link->lacc;
1840 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1842 lacc = lacc->group_representative;
1843 if (propagate_subacesses_accross_link (lacc, racc)
1844 && lacc->first_link)
1845 add_access_to_work_queue (lacc);
1850 /* Go through all accesses collected throughout the (intraprocedural) analysis
1851 stage, exclude overlapping ones, identify representatives and build trees
1852 out of them, making decisions about scalarization on the way. Return true
1853 iff there are any to-be-scalarized variables after this stage. */
1856 analyze_all_variable_accesses (void)
1859 referenced_var_iterator rvi;
1862 FOR_EACH_REFERENCED_VAR (var, rvi)
1863 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1865 struct access *access;
1867 access = sort_and_splice_var_accesses (var);
1869 build_access_trees (access);
1871 disqualify_candidate (var,
1872 "No or inhibitingly overlapping accesses.");
1875 propagate_all_subaccesses ();
1877 FOR_EACH_REFERENCED_VAR (var, rvi)
1878 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1880 struct access *access = get_first_repr_for_decl (var);
1882 if (analyze_access_trees (access))
1885 if (dump_file && (dump_flags & TDF_DETAILS))
1887 fprintf (dump_file, "\nAccess trees for ");
1888 print_generic_expr (dump_file, var, 0);
1889 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1890 dump_access_tree (dump_file, access);
1891 fprintf (dump_file, "\n");
1895 disqualify_candidate (var, "No scalar replacements to be created.");
1900 statistics_counter_event (cfun, "Scalarized aggregates", res);
1907 /* Return true iff a reference statement into aggregate AGG can be built for
1908 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1909 or a child of its sibling. TOP_OFFSET is the offset from the processed
1910 access subtree that has to be subtracted from offset of each access. */
1913 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1914 HOST_WIDE_INT top_offset)
1918 if (access->grp_to_be_replaced
1919 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1920 access->offset - top_offset,
1921 access->type, false))
1924 if (access->first_child
1925 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1929 access = access->next_sibling;
1936 /* Generate statements copying scalar replacements of accesses within a subtree
1937 into or out of AGG. ACCESS is the first child of the root of the subtree to
1938 be processed. AGG is an aggregate type expression (can be a declaration but
1939 does not have to be, it can for example also be an indirect_ref).
1940 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1941 from offsets of individual accesses to get corresponding offsets for AGG.
1942 If CHUNK_SIZE is non-null, copy only replacements in the interval
1943 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1944 statement iterator used to place the new statements. WRITE should be true
1945 when the statements should write from AGG to the replacement and false if
1946 vice versa. if INSERT_AFTER is true, new statements will be added after the
1947 current statement in GSI, they will be added before the statement
1951 generate_subtree_copies (struct access *access, tree agg,
1952 HOST_WIDE_INT top_offset,
1953 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1954 gimple_stmt_iterator *gsi, bool write,
1959 tree expr = unshare_expr (agg);
1961 if (chunk_size && access->offset >= start_offset + chunk_size)
1964 if (access->grp_to_be_replaced
1966 || access->offset + access->size > start_offset))
1968 tree repl = get_access_replacement (access);
1972 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1973 access->offset - top_offset,
1974 access->type, false);
1975 gcc_assert (ref_found);
1979 if (access->grp_partial_lhs)
1980 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
1982 insert_after ? GSI_NEW_STMT
1984 stmt = gimple_build_assign (repl, expr);
1988 TREE_NO_WARNING (repl) = 1;
1989 if (access->grp_partial_lhs)
1990 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1992 insert_after ? GSI_NEW_STMT
1994 stmt = gimple_build_assign (expr, repl);
1998 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2000 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2002 sra_stats.subtree_copies++;
2005 if (access->first_child)
2006 generate_subtree_copies (access->first_child, agg, top_offset,
2007 start_offset, chunk_size, gsi,
2008 write, insert_after);
2010 access = access->next_sibling;
2015 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2016 the root of the subtree to be processed. GSI is the statement iterator used
2017 for inserting statements which are added after the current statement if
2018 INSERT_AFTER is true or before it otherwise. */
2021 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2025 struct access *child;
2027 if (access->grp_to_be_replaced)
2031 stmt = gimple_build_assign (get_access_replacement (access),
2032 fold_convert (access->type,
2033 integer_zero_node));
2035 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2037 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2041 for (child = access->first_child; child; child = child->next_sibling)
2042 init_subtree_with_zero (child, gsi, insert_after);
2045 /* Search for an access representative for the given expression EXPR and
2046 return it or NULL if it cannot be found. */
2048 static struct access *
2049 get_access_for_expr (tree expr)
2051 HOST_WIDE_INT offset, size, max_size;
2054 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2055 a different size than the size of its argument and we need the latter
2057 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2058 expr = TREE_OPERAND (expr, 0);
2060 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2061 if (max_size == -1 || !DECL_P (base))
2064 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2067 return get_var_base_offset_size_access (base, offset, max_size);
2070 /* Callback for scan_function. Replace the expression EXPR with a scalar
2071 replacement if there is one and generate other statements to do type
2072 conversion or subtree copying if necessary. GSI is used to place newly
2073 created statements, WRITE is true if the expression is being written to (it
2074 is on a LHS of a statement or output in an assembly statement). */
2077 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
2078 void *data ATTRIBUTE_UNUSED)
2080 struct access *access;
2083 if (TREE_CODE (*expr) == BIT_FIELD_REF)
2086 expr = &TREE_OPERAND (*expr, 0);
2091 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2092 expr = &TREE_OPERAND (*expr, 0);
2093 access = get_access_for_expr (*expr);
2096 type = TREE_TYPE (*expr);
2098 if (access->grp_to_be_replaced)
2100 tree repl = get_access_replacement (access);
2101 /* If we replace a non-register typed access simply use the original
2102 access expression to extract the scalar component afterwards.
2103 This happens if scalarizing a function return value or parameter
2104 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2105 gcc.c-torture/compile/20011217-1.c. */
2106 if (!is_gimple_reg_type (type))
2111 tree ref = unshare_expr (access->expr);
2112 if (access->grp_partial_lhs)
2113 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2114 false, GSI_NEW_STMT);
2115 stmt = gimple_build_assign (repl, ref);
2116 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2120 if (access->grp_partial_lhs)
2121 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2122 true, GSI_SAME_STMT);
2123 stmt = gimple_build_assign (unshare_expr (access->expr), repl);
2124 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2129 gcc_assert (useless_type_conversion_p (type, access->type));
2135 if (access->first_child)
2137 HOST_WIDE_INT start_offset, chunk_size;
2139 && host_integerp (TREE_OPERAND (bfr, 1), 1)
2140 && host_integerp (TREE_OPERAND (bfr, 2), 1))
2142 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2143 start_offset = access->offset
2144 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2147 start_offset = chunk_size = 0;
2149 generate_subtree_copies (access->first_child, access->base, 0,
2150 start_offset, chunk_size, gsi, write, write);
2155 /* Where scalar replacements of the RHS have been written to when a replacement
2156 of a LHS of an assigments cannot be direclty loaded from a replacement of
2158 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
2159 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2160 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2162 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2163 base aggregate if there are unscalarized data or directly to LHS
2166 static enum unscalarized_data_handling
2167 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
2168 gimple_stmt_iterator *gsi)
2170 if (top_racc->grp_unscalarized_data)
2172 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2174 return SRA_UDH_RIGHT;
2178 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2179 0, 0, gsi, false, false);
2180 return SRA_UDH_LEFT;
2185 /* Try to generate statements to load all sub-replacements in an access
2186 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2187 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2188 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2189 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2190 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2191 the rhs top aggregate has already been refreshed by contents of its scalar
2192 reductions and is set to true if this function has to do it. */
2195 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2196 HOST_WIDE_INT left_offset,
2197 HOST_WIDE_INT right_offset,
2198 gimple_stmt_iterator *old_gsi,
2199 gimple_stmt_iterator *new_gsi,
2200 enum unscalarized_data_handling *refreshed,
2203 location_t loc = EXPR_LOCATION (lacc->expr);
2206 if (lacc->grp_to_be_replaced)
2208 struct access *racc;
2209 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
2213 racc = find_access_in_subtree (top_racc, offset, lacc->size);
2214 if (racc && racc->grp_to_be_replaced)
2216 rhs = get_access_replacement (racc);
2217 if (!useless_type_conversion_p (lacc->type, racc->type))
2218 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2224 /* No suitable access on the right hand side, need to load from
2225 the aggregate. See if we have to update it first... */
2226 if (*refreshed == SRA_UDH_NONE)
2227 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2230 if (*refreshed == SRA_UDH_LEFT)
2231 rhs = unshare_expr (lacc->expr);
2234 rhs = unshare_expr (top_racc->base);
2235 repl_found = build_ref_for_offset (&rhs,
2236 TREE_TYPE (top_racc->base),
2237 offset, lacc->type, false);
2238 gcc_assert (repl_found);
2242 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2243 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2245 sra_stats.subreplacements++;
2247 else if (*refreshed == SRA_UDH_NONE
2248 && lacc->grp_read && !lacc->grp_covered)
2249 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2252 if (lacc->first_child)
2253 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2254 left_offset, right_offset,
2255 old_gsi, new_gsi, refreshed, lhs);
2256 lacc = lacc->next_sibling;
2261 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2262 to the assignment and GSI is the statement iterator pointing at it. Returns
2263 the same values as sra_modify_assign. */
2265 static enum scan_assign_result
2266 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2268 tree lhs = gimple_assign_lhs (*stmt);
2271 acc = get_access_for_expr (lhs);
2275 if (VEC_length (constructor_elt,
2276 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2278 /* I have never seen this code path trigger but if it can happen the
2279 following should handle it gracefully. */
2280 if (access_has_children_p (acc))
2281 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2283 return SRA_SA_PROCESSED;
2286 if (acc->grp_covered)
2288 init_subtree_with_zero (acc, gsi, false);
2289 unlink_stmt_vdef (*stmt);
2290 gsi_remove (gsi, true);
2291 return SRA_SA_REMOVED;
2295 init_subtree_with_zero (acc, gsi, true);
2296 return SRA_SA_PROCESSED;
2301 /* Callback of scan_function to process assign statements. It examines both
2302 sides of the statement, replaces them with a scalare replacement if there is
2303 one and generating copying of replacements if scalarized aggregates have been
2304 used in the assignment. STMT is a pointer to the assign statement, GSI is
2305 used to hold generated statements for type conversions and subtree
2308 static enum scan_assign_result
2309 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2310 void *data ATTRIBUTE_UNUSED)
2312 struct access *lacc, *racc;
2314 bool modify_this_stmt = false;
2315 bool force_gimple_rhs = false;
2316 location_t loc = gimple_location (*stmt);
2318 if (!gimple_assign_single_p (*stmt))
2320 lhs = gimple_assign_lhs (*stmt);
2321 rhs = gimple_assign_rhs1 (*stmt);
2323 if (TREE_CODE (rhs) == CONSTRUCTOR)
2324 return sra_modify_constructor_assign (stmt, gsi);
2326 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2327 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2328 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2330 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2332 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2334 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2337 lacc = get_access_for_expr (lhs);
2338 racc = get_access_for_expr (rhs);
2342 if (lacc && lacc->grp_to_be_replaced)
2344 lhs = get_access_replacement (lacc);
2345 gimple_assign_set_lhs (*stmt, lhs);
2346 modify_this_stmt = true;
2347 if (lacc->grp_partial_lhs)
2348 force_gimple_rhs = true;
2352 if (racc && racc->grp_to_be_replaced)
2354 rhs = get_access_replacement (racc);
2355 modify_this_stmt = true;
2356 if (racc->grp_partial_lhs)
2357 force_gimple_rhs = true;
2361 if (modify_this_stmt)
2363 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2365 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2366 ??? This should move to fold_stmt which we simply should
2367 call after building a VIEW_CONVERT_EXPR here. */
2368 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2369 && !access_has_children_p (lacc))
2371 tree expr = unshare_expr (lhs);
2372 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2373 TREE_TYPE (rhs), false))
2376 gimple_assign_set_lhs (*stmt, expr);
2379 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2380 && !access_has_children_p (racc))
2382 tree expr = unshare_expr (rhs);
2383 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2384 TREE_TYPE (lhs), false))
2387 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2389 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2390 if (!is_gimple_reg (lhs))
2391 force_gimple_rhs = true;
2395 if (force_gimple_rhs)
2396 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2397 true, GSI_SAME_STMT);
2398 if (gimple_assign_rhs1 (*stmt) != rhs)
2400 gimple_assign_set_rhs_from_tree (gsi, rhs);
2401 gcc_assert (*stmt == gsi_stmt (*gsi));
2405 /* From this point on, the function deals with assignments in between
2406 aggregates when at least one has scalar reductions of some of its
2407 components. There are three possible scenarios: Both the LHS and RHS have
2408 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2410 In the first case, we would like to load the LHS components from RHS
2411 components whenever possible. If that is not possible, we would like to
2412 read it directly from the RHS (after updating it by storing in it its own
2413 components). If there are some necessary unscalarized data in the LHS,
2414 those will be loaded by the original assignment too. If neither of these
2415 cases happen, the original statement can be removed. Most of this is done
2416 by load_assign_lhs_subreplacements.
2418 In the second case, we would like to store all RHS scalarized components
2419 directly into LHS and if they cover the aggregate completely, remove the
2420 statement too. In the third case, we want the LHS components to be loaded
2421 directly from the RHS (DSE will remove the original statement if it
2424 This is a bit complex but manageable when types match and when unions do
2425 not cause confusion in a way that we cannot really load a component of LHS
2426 from the RHS or vice versa (the access representing this level can have
2427 subaccesses that are accessible only through a different union field at a
2428 higher level - different from the one used in the examined expression).
2431 Therefore, I specially handle a fourth case, happening when there is a
2432 specific type cast or it is impossible to locate a scalarized subaccess on
2433 the other side of the expression. If that happens, I simply "refresh" the
2434 RHS by storing in it is scalarized components leave the original statement
2435 there to do the copying and then load the scalar replacements of the LHS.
2436 This is what the first branch does. */
2438 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2439 || (access_has_children_p (racc)
2440 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2441 || (access_has_children_p (lacc)
2442 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2444 if (access_has_children_p (racc))
2445 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2447 if (access_has_children_p (lacc))
2448 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2450 sra_stats.separate_lhs_rhs_handling++;
2454 if (access_has_children_p (lacc) && access_has_children_p (racc))
2456 gimple_stmt_iterator orig_gsi = *gsi;
2457 enum unscalarized_data_handling refreshed;
2459 if (lacc->grp_read && !lacc->grp_covered)
2460 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2462 refreshed = SRA_UDH_NONE;
2464 load_assign_lhs_subreplacements (lacc->first_child, racc,
2465 lacc->offset, racc->offset,
2466 &orig_gsi, gsi, &refreshed, lhs);
2467 if (refreshed != SRA_UDH_RIGHT)
2469 if (*stmt == gsi_stmt (*gsi))
2472 unlink_stmt_vdef (*stmt);
2473 gsi_remove (&orig_gsi, true);
2474 sra_stats.deleted++;
2475 return SRA_SA_REMOVED;
2480 if (access_has_children_p (racc))
2482 if (!racc->grp_unscalarized_data)
2484 generate_subtree_copies (racc->first_child, lhs,
2485 racc->offset, 0, 0, gsi,
2487 gcc_assert (*stmt == gsi_stmt (*gsi));
2488 unlink_stmt_vdef (*stmt);
2489 gsi_remove (gsi, true);
2490 sra_stats.deleted++;
2491 return SRA_SA_REMOVED;
2494 generate_subtree_copies (racc->first_child, lhs,
2495 racc->offset, 0, 0, gsi, false, true);
2497 else if (access_has_children_p (lacc))
2498 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2499 0, 0, gsi, true, true);
2502 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2505 /* Generate statements initializing scalar replacements of parts of function
2509 initialize_parameter_reductions (void)
2511 gimple_stmt_iterator gsi;
2512 gimple_seq seq = NULL;
2515 for (parm = DECL_ARGUMENTS (current_function_decl);
2517 parm = TREE_CHAIN (parm))
2519 VEC (access_p, heap) *access_vec;
2520 struct access *access;
2522 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2524 access_vec = get_base_access_vector (parm);
2530 seq = gimple_seq_alloc ();
2531 gsi = gsi_start (seq);
2534 for (access = VEC_index (access_p, access_vec, 0);
2536 access = access->next_grp)
2537 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2541 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2544 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2545 it reveals there are components of some aggregates to be scalarized, it runs
2546 the required transformations. */
2548 perform_intra_sra (void)
2553 if (!find_var_candidates ())
2556 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2560 if (!analyze_all_variable_accesses ())
2563 scan_function (sra_modify_expr, sra_modify_assign, NULL, false, NULL);
2564 initialize_parameter_reductions ();
2566 statistics_counter_event (cfun, "Scalar replacements created",
2567 sra_stats.replacements);
2568 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2569 statistics_counter_event (cfun, "Subtree copy stmts",
2570 sra_stats.subtree_copies);
2571 statistics_counter_event (cfun, "Subreplacement stmts",
2572 sra_stats.subreplacements);
2573 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2574 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2575 sra_stats.separate_lhs_rhs_handling);
2577 ret = TODO_update_ssa;
2580 sra_deinitialize ();
2584 /* Perform early intraprocedural SRA. */
2586 early_intra_sra (void)
2588 sra_mode = SRA_MODE_EARLY_INTRA;
2589 return perform_intra_sra ();
2592 /* Perform "late" intraprocedural SRA. */
2594 late_intra_sra (void)
2596 sra_mode = SRA_MODE_INTRA;
2597 return perform_intra_sra ();
2602 gate_intra_sra (void)
2604 return flag_tree_sra != 0;
2608 struct gimple_opt_pass pass_sra_early =
2613 gate_intra_sra, /* gate */
2614 early_intra_sra, /* execute */
2617 0, /* static_pass_number */
2618 TV_TREE_SRA, /* tv_id */
2619 PROP_cfg | PROP_ssa, /* properties_required */
2620 0, /* properties_provided */
2621 0, /* properties_destroyed */
2622 0, /* todo_flags_start */
2626 | TODO_verify_ssa /* todo_flags_finish */
2630 struct gimple_opt_pass pass_sra =
2635 gate_intra_sra, /* gate */
2636 late_intra_sra, /* execute */
2639 0, /* static_pass_number */
2640 TV_TREE_SRA, /* tv_id */
2641 PROP_cfg | PROP_ssa, /* properties_required */
2642 0, /* properties_provided */
2643 0, /* properties_destroyed */
2644 TODO_update_address_taken, /* todo_flags_start */
2648 | TODO_verify_ssa /* todo_flags_finish */
2653 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2657 is_unused_scalar_param (tree parm)
2660 return (is_gimple_reg (parm)
2661 && (!(name = gimple_default_def (cfun, parm))
2662 || has_zero_uses (name)));
2665 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2666 examine whether there are any direct or otherwise infeasible ones. If so,
2667 return true, otherwise return false. PARM must be a gimple register with a
2668 non-NULL default definition. */
2671 ptr_parm_has_direct_uses (tree parm)
2673 imm_use_iterator ui;
2675 tree name = gimple_default_def (cfun, parm);
2678 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
2680 if (gimple_assign_single_p (stmt))
2682 tree rhs = gimple_assign_rhs1 (stmt);
2685 else if (TREE_CODE (rhs) == ADDR_EXPR)
2689 rhs = TREE_OPERAND (rhs, 0);
2691 while (handled_component_p (rhs));
2692 if (INDIRECT_REF_P (rhs) && TREE_OPERAND (rhs, 0) == name)
2696 else if (gimple_code (stmt) == GIMPLE_RETURN)
2698 tree t = gimple_return_retval (stmt);
2702 else if (is_gimple_call (stmt))
2705 for (i = 0; i < gimple_call_num_args (stmt); i++)
2707 tree arg = gimple_call_arg (stmt, i);
2715 else if (!is_gimple_debug (stmt))
2719 BREAK_FROM_IMM_USE_STMT (ui);
2725 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2726 them in candidate_bitmap. Note that these do not necessarily include
2727 parameter which are unused and thus can be removed. Return true iff any
2728 such candidate has been found. */
2731 find_param_candidates (void)
2737 for (parm = DECL_ARGUMENTS (current_function_decl);
2739 parm = TREE_CHAIN (parm))
2741 tree type = TREE_TYPE (parm);
2745 if (TREE_THIS_VOLATILE (parm)
2746 || TREE_ADDRESSABLE (parm)
2747 || is_va_list_type (type))
2750 if (is_unused_scalar_param (parm))
2756 if (POINTER_TYPE_P (type))
2758 type = TREE_TYPE (type);
2760 if (TREE_CODE (type) == FUNCTION_TYPE
2761 || TYPE_VOLATILE (type)
2762 || !is_gimple_reg (parm)
2763 || is_va_list_type (type)
2764 || ptr_parm_has_direct_uses (parm))
2767 else if (!AGGREGATE_TYPE_P (type))
2770 if (!COMPLETE_TYPE_P (type)
2771 || !host_integerp (TYPE_SIZE (type), 1)
2772 || tree_low_cst (TYPE_SIZE (type), 1) == 0
2773 || (AGGREGATE_TYPE_P (type)
2774 && type_internals_preclude_sra_p (type)))
2777 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
2779 if (dump_file && (dump_flags & TDF_DETAILS))
2781 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
2782 print_generic_expr (dump_file, parm, 0);
2783 fprintf (dump_file, "\n");
2787 func_param_count = count;
2791 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2795 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
2798 struct access *repr = (struct access *) data;
2800 repr->grp_maybe_modified = 1;
2804 /* Analyze what representatives (in linked lists accessible from
2805 REPRESENTATIVES) can be modified by side effects of statements in the
2806 current function. */
2809 analyze_modified_params (VEC (access_p, heap) *representatives)
2813 for (i = 0; i < func_param_count; i++)
2815 struct access *repr = VEC_index (access_p, representatives, i);
2816 VEC (access_p, heap) *access_vec;
2817 int j, access_count;
2820 if (!repr || no_accesses_p (repr))
2823 if (!POINTER_TYPE_P (TREE_TYPE (parm))
2824 || repr->grp_maybe_modified)
2827 access_vec = get_base_access_vector (parm);
2828 access_count = VEC_length (access_p, access_vec);
2829 for (j = 0; j < access_count; j++)
2831 struct access *access;
2834 /* All accesses are read ones, otherwise grp_maybe_modified would be
2836 access = VEC_index (access_p, access_vec, j);
2837 ao_ref_init (&ar, access->expr);
2838 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
2839 mark_maybe_modified, repr, NULL);
2840 if (repr->grp_maybe_modified)
2846 /* Propagate distances in bb_dereferences in the opposite direction than the
2847 control flow edges, in each step storing the maximum of the current value
2848 and the minimum of all successors. These steps are repeated until the table
2849 stabilizes. Note that BBs which might terminate the functions (according to
2850 final_bbs bitmap) never updated in this way. */
2853 propagate_dereference_distances (void)
2855 VEC (basic_block, heap) *queue;
2858 queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
2859 VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
2862 VEC_quick_push (basic_block, queue, bb);
2866 while (!VEC_empty (basic_block, queue))
2870 bool change = false;
2873 bb = VEC_pop (basic_block, queue);
2876 if (bitmap_bit_p (final_bbs, bb->index))
2879 for (i = 0; i < func_param_count; i++)
2881 int idx = bb->index * func_param_count + i;
2883 HOST_WIDE_INT inh = 0;
2885 FOR_EACH_EDGE (e, ei, bb->succs)
2887 int succ_idx = e->dest->index * func_param_count + i;
2889 if (e->src == EXIT_BLOCK_PTR)
2895 inh = bb_dereferences [succ_idx];
2897 else if (bb_dereferences [succ_idx] < inh)
2898 inh = bb_dereferences [succ_idx];
2901 if (!first && bb_dereferences[idx] < inh)
2903 bb_dereferences[idx] = inh;
2908 if (change && !bitmap_bit_p (final_bbs, bb->index))
2909 FOR_EACH_EDGE (e, ei, bb->preds)
2914 e->src->aux = e->src;
2915 VEC_quick_push (basic_block, queue, e->src);
2919 VEC_free (basic_block, heap, queue);
2922 /* Dump a dereferences TABLE with heading STR to file F. */
2925 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
2929 fprintf (dump_file, str);
2930 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2932 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
2933 if (bb != EXIT_BLOCK_PTR)
2936 for (i = 0; i < func_param_count; i++)
2938 int idx = bb->index * func_param_count + i;
2939 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
2944 fprintf (dump_file, "\n");
2947 /* Determine what (parts of) parameters passed by reference that are not
2948 assigned to are not certainly dereferenced in this function and thus the
2949 dereferencing cannot be safely moved to the caller without potentially
2950 introducing a segfault. Mark such REPRESENTATIVES as
2951 grp_not_necessarilly_dereferenced.
2953 The dereferenced maximum "distance," i.e. the offset + size of the accessed
2954 part is calculated rather than simple booleans are calculated for each
2955 pointer parameter to handle cases when only a fraction of the whole
2956 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
2959 The maximum dereference distances for each pointer parameter and BB are
2960 already stored in bb_dereference. This routine simply propagates these
2961 values upwards by propagate_dereference_distances and then compares the
2962 distances of individual parameters in the ENTRY BB to the equivalent
2963 distances of each representative of a (fraction of a) parameter. */
2966 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
2970 if (dump_file && (dump_flags & TDF_DETAILS))
2971 dump_dereferences_table (dump_file,
2972 "Dereference table before propagation:\n",
2975 propagate_dereference_distances ();
2977 if (dump_file && (dump_flags & TDF_DETAILS))
2978 dump_dereferences_table (dump_file,
2979 "Dereference table after propagation:\n",
2982 for (i = 0; i < func_param_count; i++)
2984 struct access *repr = VEC_index (access_p, representatives, i);
2985 int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
2987 if (!repr || no_accesses_p (repr))
2992 if ((repr->offset + repr->size) > bb_dereferences[idx])
2993 repr->grp_not_necessarilly_dereferenced = 1;
2994 repr = repr->next_grp;
3000 /* Return the representative access for the parameter declaration PARM if it is
3001 a scalar passed by reference which is not written to and the pointer value
3002 is not used directly. Thus, if it is legal to dereference it in the caller
3003 and we can rule out modifications through aliases, such parameter should be
3004 turned into one passed by value. Return NULL otherwise. */
3006 static struct access *
3007 unmodified_by_ref_scalar_representative (tree parm)
3009 int i, access_count;
3010 struct access *access;
3011 VEC (access_p, heap) *access_vec;
3013 access_vec = get_base_access_vector (parm);
3014 gcc_assert (access_vec);
3015 access_count = VEC_length (access_p, access_vec);
3017 for (i = 0; i < access_count; i++)
3019 access = VEC_index (access_p, access_vec, i);
3024 access = VEC_index (access_p, access_vec, 0);
3025 access->grp_read = 1;
3026 access->grp_scalar_ptr = 1;
3030 /* Sort collected accesses for parameter PARM, identify representatives for
3031 each accessed region and link them together. Return NULL if there are
3032 different but overlapping accesses, return the special ptr value meaning
3033 there are no accesses for this parameter if that is the case and return the
3034 first representative otherwise. Set *RO_GRP if there is a group of accesses
3035 with only read (i.e. no write) accesses. */
3037 static struct access *
3038 splice_param_accesses (tree parm, bool *ro_grp)
3040 int i, j, access_count, group_count;
3041 int agg_size, total_size = 0;
3042 struct access *access, *res, **prev_acc_ptr = &res;
3043 VEC (access_p, heap) *access_vec;
3045 access_vec = get_base_access_vector (parm);
3047 return &no_accesses_representant;
3048 access_count = VEC_length (access_p, access_vec);
3050 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
3051 compare_access_positions);
3056 while (i < access_count)
3059 access = VEC_index (access_p, access_vec, i);
3060 modification = access->write;
3062 /* Access is about to become group representative unless we find some
3063 nasty overlap which would preclude us from breaking this parameter
3067 while (j < access_count)
3069 struct access *ac2 = VEC_index (access_p, access_vec, j);
3070 if (ac2->offset != access->offset)
3072 /* All or nothing law for parameters. */
3073 if (access->offset + access->size > ac2->offset)
3078 else if (ac2->size != access->size)
3081 modification |= ac2->write;
3086 access->grp_maybe_modified = modification;
3089 *prev_acc_ptr = access;
3090 prev_acc_ptr = &access->next_grp;
3091 total_size += access->size;
3095 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3096 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3098 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3099 if (total_size >= agg_size)
3102 gcc_assert (group_count > 0);
3106 /* Decide whether parameters with representative accesses given by REPR should
3107 be reduced into components. */
3110 decide_one_param_reduction (struct access *repr)
3112 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3117 cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3118 gcc_assert (cur_parm_size > 0);
3120 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3123 agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3128 agg_size = cur_parm_size;
3134 fprintf (dump_file, "Evaluating PARAM group sizes for ");
3135 print_generic_expr (dump_file, parm, 0);
3136 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3137 for (acc = repr; acc; acc = acc->next_grp)
3138 dump_access (dump_file, acc, true);
3142 new_param_count = 0;
3144 for (; repr; repr = repr->next_grp)
3146 gcc_assert (parm == repr->base);
3149 if (!by_ref || (!repr->grp_maybe_modified
3150 && !repr->grp_not_necessarilly_dereferenced))
3151 total_size += repr->size;
3153 total_size += cur_parm_size;
3156 gcc_assert (new_param_count > 0);
3158 if (optimize_function_for_size_p (cfun))
3159 parm_size_limit = cur_parm_size;
3161 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3164 if (total_size < agg_size
3165 && total_size <= parm_size_limit)
3168 fprintf (dump_file, " ....will be split into %i components\n",
3170 return new_param_count;
3176 /* The order of the following enums is important, we need to do extra work for
3177 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3178 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
3179 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
3181 /* Identify representatives of all accesses to all candidate parameters for
3182 IPA-SRA. Return result based on what representatives have been found. */
3184 static enum ipa_splicing_result
3185 splice_all_param_accesses (VEC (access_p, heap) **representatives)
3187 enum ipa_splicing_result result = NO_GOOD_ACCESS;
3189 struct access *repr;
3191 *representatives = VEC_alloc (access_p, heap, func_param_count);
3193 for (parm = DECL_ARGUMENTS (current_function_decl);
3195 parm = TREE_CHAIN (parm))
3197 if (is_unused_scalar_param (parm))
3199 VEC_quick_push (access_p, *representatives,
3200 &no_accesses_representant);
3201 if (result == NO_GOOD_ACCESS)
3202 result = UNUSED_PARAMS;
3204 else if (POINTER_TYPE_P (TREE_TYPE (parm))
3205 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
3206 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3208 repr = unmodified_by_ref_scalar_representative (parm);
3209 VEC_quick_push (access_p, *representatives, repr);
3211 result = UNMODIF_BY_REF_ACCESSES;
3213 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3215 bool ro_grp = false;
3216 repr = splice_param_accesses (parm, &ro_grp);
3217 VEC_quick_push (access_p, *representatives, repr);
3219 if (repr && !no_accesses_p (repr))
3221 if (POINTER_TYPE_P (TREE_TYPE (parm)))
3224 result = UNMODIF_BY_REF_ACCESSES;
3225 else if (result < MODIF_BY_REF_ACCESSES)
3226 result = MODIF_BY_REF_ACCESSES;
3228 else if (result < BY_VAL_ACCESSES)
3229 result = BY_VAL_ACCESSES;
3231 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
3232 result = UNUSED_PARAMS;
3235 VEC_quick_push (access_p, *representatives, NULL);
3238 if (result == NO_GOOD_ACCESS)
3240 VEC_free (access_p, heap, *representatives);
3241 *representatives = NULL;
3242 return NO_GOOD_ACCESS;
3248 /* Return the index of BASE in PARMS. Abort if it is not found. */
3251 get_param_index (tree base, VEC(tree, heap) *parms)
3255 len = VEC_length (tree, parms);
3256 for (i = 0; i < len; i++)
3257 if (VEC_index (tree, parms, i) == base)
3262 /* Convert the decisions made at the representative level into compact
3263 parameter adjustments. REPRESENTATIVES are pointers to first
3264 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3265 final number of adjustments. */
3267 static ipa_parm_adjustment_vec
3268 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
3269 int adjustments_count)
3271 VEC (tree, heap) *parms;
3272 ipa_parm_adjustment_vec adjustments;
3276 gcc_assert (adjustments_count > 0);
3277 parms = ipa_get_vector_of_formal_parms (current_function_decl);
3278 adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
3279 parm = DECL_ARGUMENTS (current_function_decl);
3280 for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
3282 struct access *repr = VEC_index (access_p, representatives, i);
3284 if (!repr || no_accesses_p (repr))
3286 struct ipa_parm_adjustment *adj;
3288 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3289 memset (adj, 0, sizeof (*adj));
3290 adj->base_index = get_param_index (parm, parms);
3293 adj->copy_param = 1;
3295 adj->remove_param = 1;
3299 struct ipa_parm_adjustment *adj;
3300 int index = get_param_index (parm, parms);
3302 for (; repr; repr = repr->next_grp)
3304 adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
3305 memset (adj, 0, sizeof (*adj));
3306 gcc_assert (repr->base == parm);
3307 adj->base_index = index;
3308 adj->base = repr->base;
3309 adj->type = repr->type;
3310 adj->offset = repr->offset;
3311 adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
3312 && (repr->grp_maybe_modified
3313 || repr->grp_not_necessarilly_dereferenced));
3318 VEC_free (tree, heap, parms);
3322 /* Analyze the collected accesses and produce a plan what to do with the
3323 parameters in the form of adjustments, NULL meaning nothing. */
3325 static ipa_parm_adjustment_vec
3326 analyze_all_param_acesses (void)
3328 enum ipa_splicing_result repr_state;
3329 bool proceed = false;
3330 int i, adjustments_count = 0;
3331 VEC (access_p, heap) *representatives;
3332 ipa_parm_adjustment_vec adjustments;
3334 repr_state = splice_all_param_accesses (&representatives);
3335 if (repr_state == NO_GOOD_ACCESS)
3338 /* If there are any parameters passed by reference which are not modified
3339 directly, we need to check whether they can be modified indirectly. */
3340 if (repr_state == UNMODIF_BY_REF_ACCESSES)
3342 analyze_caller_dereference_legality (representatives);
3343 analyze_modified_params (representatives);
3346 for (i = 0; i < func_param_count; i++)
3348 struct access *repr = VEC_index (access_p, representatives, i);
3350 if (repr && !no_accesses_p (repr))
3352 if (repr->grp_scalar_ptr)
3354 adjustments_count++;
3355 if (repr->grp_not_necessarilly_dereferenced
3356 || repr->grp_maybe_modified)
3357 VEC_replace (access_p, representatives, i, NULL);
3361 sra_stats.scalar_by_ref_to_by_val++;
3366 int new_components = decide_one_param_reduction (repr);
3368 if (new_components == 0)
3370 VEC_replace (access_p, representatives, i, NULL);
3371 adjustments_count++;
3375 adjustments_count += new_components;
3376 sra_stats.aggregate_params_reduced++;
3377 sra_stats.param_reductions_created += new_components;
3384 if (no_accesses_p (repr))
3387 sra_stats.deleted_unused_parameters++;
3389 adjustments_count++;
3393 if (!proceed && dump_file)
3394 fprintf (dump_file, "NOT proceeding to change params.\n");
3397 adjustments = turn_representatives_into_adjustments (representatives,
3402 VEC_free (access_p, heap, representatives);
3406 /* If a parameter replacement identified by ADJ does not yet exist in the form
3407 of declaration, create it and record it, otherwise return the previously
3411 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
3414 if (!adj->new_ssa_base)
3416 char *pretty_name = make_fancy_name (adj->base);
3418 repl = make_rename_temp (TREE_TYPE (adj->base), "ISR");
3419 DECL_NAME (repl) = get_identifier (pretty_name);
3420 obstack_free (&name_obstack, pretty_name);
3423 add_referenced_var (repl);
3424 adj->new_ssa_base = repl;
3427 repl = adj->new_ssa_base;
3431 /* Find the first adjustment for a particular parameter BASE in a vector of
3432 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3435 static struct ipa_parm_adjustment *
3436 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
3440 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3441 for (i = 0; i < len; i++)
3443 struct ipa_parm_adjustment *adj;
3445 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3446 if (!adj->copy_param && adj->base == base)
3453 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3454 parameter which is to be removed because its value is not used, replace the
3455 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3456 uses too. DATA is a pointer to an adjustments vector. */
3459 replace_removed_params_ssa_names (gimple stmt, void *data)
3461 VEC (ipa_parm_adjustment_t, heap) *adjustments;
3462 struct ipa_parm_adjustment *adj;
3463 tree lhs, decl, repl, name;
3465 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3466 if (gimple_code (stmt) == GIMPLE_PHI)
3467 lhs = gimple_phi_result (stmt);
3468 else if (is_gimple_assign (stmt))
3469 lhs = gimple_assign_lhs (stmt);
3470 else if (is_gimple_call (stmt))
3471 lhs = gimple_call_lhs (stmt);
3475 if (TREE_CODE (lhs) != SSA_NAME)
3477 decl = SSA_NAME_VAR (lhs);
3478 if (TREE_CODE (decl) != PARM_DECL)
3481 adj = get_adjustment_for_base (adjustments, decl);
3485 repl = get_replaced_param_substitute (adj);
3486 name = make_ssa_name (repl, stmt);
3490 fprintf (dump_file, "replacing an SSA name of a removed param ");
3491 print_generic_expr (dump_file, lhs, 0);
3492 fprintf (dump_file, " with ");
3493 print_generic_expr (dump_file, name, 0);
3494 fprintf (dump_file, "\n");
3497 if (is_gimple_assign (stmt))
3498 gimple_assign_set_lhs (stmt, name);
3499 else if (is_gimple_call (stmt))
3500 gimple_call_set_lhs (stmt, name);
3502 gimple_phi_set_result (stmt, name);
3504 replace_uses_by (lhs, name);
3508 /* Callback for scan_function. If the expression *EXPR should be replaced by a
3509 reduction of a parameter, do so. DATA is a pointer to a vector of
3513 sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
3514 bool write ATTRIBUTE_UNUSED, void *data)
3516 ipa_parm_adjustment_vec adjustments;
3518 struct ipa_parm_adjustment *adj, *cand = NULL;
3519 HOST_WIDE_INT offset, size, max_size;
3522 adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
3523 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3525 if (TREE_CODE (*expr) == BIT_FIELD_REF
3526 || TREE_CODE (*expr) == IMAGPART_EXPR
3527 || TREE_CODE (*expr) == REALPART_EXPR)
3528 expr = &TREE_OPERAND (*expr, 0);
3529 while (TREE_CODE (*expr) == NOP_EXPR
3530 || TREE_CODE (*expr) == VIEW_CONVERT_EXPR)
3531 expr = &TREE_OPERAND (*expr, 0);
3533 base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
3534 if (!base || size == -1 || max_size == -1)
3537 if (INDIRECT_REF_P (base))
3538 base = TREE_OPERAND (base, 0);
3540 base = get_ssa_base_param (base);
3541 if (!base || TREE_CODE (base) != PARM_DECL)
3544 for (i = 0; i < len; i++)
3546 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3548 if (adj->base == base &&
3549 (adj->offset == offset || adj->remove_param))
3555 if (!cand || cand->copy_param || cand->remove_param)
3561 src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
3563 folded = gimple_fold_indirect_ref (src);
3568 src = cand->reduction;
3570 if (dump_file && (dump_flags & TDF_DETAILS))
3572 fprintf (dump_file, "About to replace expr ");
3573 print_generic_expr (dump_file, *expr, 0);
3574 fprintf (dump_file, " with ");
3575 print_generic_expr (dump_file, src, 0);
3576 fprintf (dump_file, "\n");
3579 if (!useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
3581 tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
3589 /* Callback for scan_function to process assign statements. Performs
3590 essentially the same function like sra_ipa_modify_expr. */
3592 static enum scan_assign_result
3593 sra_ipa_modify_assign (gimple *stmt_ptr,
3594 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, void *data)
3596 gimple stmt = *stmt_ptr;
3599 if (!gimple_assign_single_p (stmt))
3602 any |= sra_ipa_modify_expr (gimple_assign_rhs1_ptr (stmt), gsi, false,
3604 any |= sra_ipa_modify_expr (gimple_assign_lhs_ptr (stmt), gsi, true, data);
3606 return any ? SRA_SA_PROCESSED : SRA_SA_NONE;
3609 /* Call gimple_debug_bind_reset_value on all debug statements describing
3610 gimple register parameters that are being removed or replaced. */
3613 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
3617 len = VEC_length (ipa_parm_adjustment_t, adjustments);
3618 for (i = 0; i < len; i++)
3620 struct ipa_parm_adjustment *adj;
3621 imm_use_iterator ui;
3625 adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
3626 if (adj->copy_param || !is_gimple_reg (adj->base))
3628 name = gimple_default_def (cfun, adj->base);
3631 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3633 /* All other users must have been removed by scan_function. */
3634 gcc_assert (is_gimple_debug (stmt));
3635 gimple_debug_bind_reset_value (stmt);
3641 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3644 convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3646 tree old_cur_fndecl = current_function_decl;
3647 struct cgraph_edge *cs;
3648 basic_block this_block;
3649 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
3651 for (cs = node->callers; cs; cs = cs->next_caller)
3653 current_function_decl = cs->caller->decl;
3654 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
3657 fprintf (dump_file, "Adjusting call (%i -> %i) %s -> %s\n",
3658 cs->caller->uid, cs->callee->uid,
3659 cgraph_node_name (cs->caller),
3660 cgraph_node_name (cs->callee));
3662 ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
3667 for (cs = node->callers; cs; cs = cs->next_caller)
3668 if (!bitmap_bit_p (recomputed_callers, cs->caller->uid))
3670 compute_inline_parameters (cs->caller);
3671 bitmap_set_bit (recomputed_callers, cs->caller->uid);
3673 BITMAP_FREE (recomputed_callers);
3675 current_function_decl = old_cur_fndecl;
3676 FOR_EACH_BB (this_block)
3678 gimple_stmt_iterator gsi;
3680 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
3682 gimple stmt = gsi_stmt (gsi);
3683 if (gimple_code (stmt) == GIMPLE_CALL
3684 && gimple_call_fndecl (stmt) == node->decl)
3687 fprintf (dump_file, "Adjusting recursive call");
3688 ipa_modify_call_arguments (NULL, stmt, adjustments);
3696 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3697 as given in ADJUSTMENTS. */
3700 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
3702 ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
3703 scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
3704 replace_removed_params_ssa_names, false, adjustments);
3705 sra_ipa_reset_debug_stmts (adjustments);
3706 convert_callers (node, adjustments);
3707 cgraph_make_node_local (node);
3711 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3712 attributes, return true otherwise. NODE is the cgraph node of the current
3716 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
3718 if (!cgraph_node_can_be_local_p (node))
3721 fprintf (dump_file, "Function not local to this compilation unit.\n");
3725 if (DECL_VIRTUAL_P (current_function_decl))
3728 fprintf (dump_file, "Function is a virtual method.\n");
3732 if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
3733 && node->global.size >= MAX_INLINE_INSNS_AUTO)
3736 fprintf (dump_file, "Function too big to be made truly local.\n");
3744 "Function has no callers in this compilation unit.\n");
3751 fprintf (dump_file, "Function uses stdarg. \n");
3758 /* Perform early interprocedural SRA. */
3761 ipa_early_sra (void)
3763 struct cgraph_node *node = cgraph_node (current_function_decl);
3764 ipa_parm_adjustment_vec adjustments;
3767 if (!ipa_sra_preliminary_function_checks (node))
3771 sra_mode = SRA_MODE_EARLY_IPA;
3773 if (!find_param_candidates ())
3776 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
3780 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
3782 * last_basic_block_for_function (cfun));
3783 final_bbs = BITMAP_ALLOC (NULL);
3785 scan_function (build_access_from_expr, build_accesses_from_assign,
3787 if (encountered_apply_args)
3790 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
3794 adjustments = analyze_all_param_acesses ();
3798 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
3800 modify_function (node, adjustments);
3801 VEC_free (ipa_parm_adjustment_t, heap, adjustments);
3802 ret = TODO_update_ssa;
3804 statistics_counter_event (cfun, "Unused parameters deleted",
3805 sra_stats.deleted_unused_parameters);
3806 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
3807 sra_stats.scalar_by_ref_to_by_val);
3808 statistics_counter_event (cfun, "Aggregate parameters broken up",
3809 sra_stats.aggregate_params_reduced);
3810 statistics_counter_event (cfun, "Aggregate parameter components created",
3811 sra_stats.param_reductions_created);
3814 BITMAP_FREE (final_bbs);
3815 free (bb_dereferences);
3817 sra_deinitialize ();
3821 /* Return if early ipa sra shall be performed. */
3823 ipa_early_sra_gate (void)
3825 return flag_ipa_sra;
3828 struct gimple_opt_pass pass_early_ipa_sra =
3832 "eipa_sra", /* name */
3833 ipa_early_sra_gate, /* gate */
3834 ipa_early_sra, /* execute */
3837 0, /* static_pass_number */
3838 TV_IPA_SRA, /* tv_id */
3839 0, /* properties_required */
3840 0, /* properties_provided */
3841 0, /* properties_destroyed */
3842 0, /* todo_flags_start */
3843 TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */