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 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
148 described above. In IPA-SRA this is a pointer to the next access
149 belonging to the same group (having the same representative). */
150 struct access
*next_sibling
;
152 /* Pointers to the first and last element in the linked list of assign
154 struct assign_link
*first_link
, *last_link
;
156 /* Pointer to the next access in the work queue. */
157 struct access
*next_queued
;
159 /* Replacement variable for this access "region." Never to be accessed
160 directly, always only by the means of get_access_replacement() and only
161 when grp_to_be_replaced flag is set. */
162 tree replacement_decl
;
164 /* Is this particular access write access? */
167 /* Is this access currently in the work queue? */
168 unsigned grp_queued
: 1;
170 /* Does this group contain a write access? This flag is propagated down the
172 unsigned grp_write
: 1;
174 /* Does this group contain a read access? This flag is propagated down the
176 unsigned grp_read
: 1;
178 /* Other passes of the analysis use this bit to make function
179 analyze_access_subtree create scalar replacements for this group if
181 unsigned grp_hint
: 1;
183 /* Is the subtree rooted in this access fully covered by scalar
185 unsigned grp_covered
: 1;
187 /* If set to true, this access and all below it in an access tree must not be
189 unsigned grp_unscalarizable_region
: 1;
191 /* Whether data have been written to parts of the aggregate covered by this
192 access which is not to be scalarized. This flag is propagated up in the
194 unsigned grp_unscalarized_data
: 1;
196 /* Does this access and/or group contain a write access through a
198 unsigned grp_partial_lhs
: 1;
200 /* Set when a scalar replacement should be created for this variable. We do
201 the decision and creation at different places because create_tmp_var
202 cannot be called from within FOR_EACH_REFERENCED_VAR. */
203 unsigned grp_to_be_replaced
: 1;
205 /* Is it possible that the group refers to data which might be (directly or
206 otherwise) modified? */
207 unsigned grp_maybe_modified
: 1;
209 /* Set when this is a representative of a pointer to scalar (i.e. by
210 reference) parameter which we consider for turning into a plain scalar
211 (i.e. a by value parameter). */
212 unsigned grp_scalar_ptr
: 1;
214 /* Set when we discover that this pointer is not safe to dereference in the
216 unsigned grp_not_necessarilly_dereferenced
: 1;
219 typedef struct access
*access_p
;
221 DEF_VEC_P (access_p
);
222 DEF_VEC_ALLOC_P (access_p
, heap
);
224 /* Alloc pool for allocating access structures. */
225 static alloc_pool access_pool
;
227 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
228 are used to propagate subaccesses from rhs to lhs as long as they don't
229 conflict with what is already there. */
232 struct access
*lacc
, *racc
;
233 struct assign_link
*next
;
236 /* Alloc pool for allocating assign link structures. */
237 static alloc_pool link_pool
;
239 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
240 static struct pointer_map_t
*base_access_vec
;
242 /* Bitmap of candidates. */
243 static bitmap candidate_bitmap
;
245 /* Obstack for creation of fancy names. */
246 static struct obstack name_obstack
;
248 /* Head of a linked list of accesses that need to have its subaccesses
249 propagated to their assignment counterparts. */
250 static struct access
*work_queue_head
;
252 /* Number of parameters of the analyzed function when doing early ipa SRA. */
253 static int func_param_count
;
255 /* scan_function sets the following to true if it encounters a call to
256 __builtin_apply_args. */
257 static bool encountered_apply_args
;
259 /* This is a table in which for each basic block and parameter there is a
260 distance (offset + size) in that parameter which is dereferenced and
261 accessed in that BB. */
262 static HOST_WIDE_INT
*bb_dereferences
;
263 /* Bitmap of BBs that can cause the function to "stop" progressing by
264 returning, throwing externally, looping infinitely or calling a function
265 which might abort etc.. */
266 static bitmap final_bbs
;
268 /* Representative of no accesses at all. */
269 static struct access no_accesses_representant
;
271 /* Predicate to test the special value. */
274 no_accesses_p (struct access
*access
)
276 return access
== &no_accesses_representant
;
279 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
280 representative fields are dumped, otherwise those which only describe the
281 individual access are. */
285 /* Number of processed aggregates is readily available in
286 analyze_all_variable_accesses and so is not stored here. */
288 /* Number of created scalar replacements. */
291 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
295 /* Number of statements created by generate_subtree_copies. */
298 /* Number of statements created by load_assign_lhs_subreplacements. */
301 /* Number of times sra_modify_assign has deleted a statement. */
304 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
305 RHS reparately due to type conversions or nonexistent matching
307 int separate_lhs_rhs_handling
;
309 /* Number of parameters that were removed because they were unused. */
310 int deleted_unused_parameters
;
312 /* Number of scalars passed as parameters by reference that have been
313 converted to be passed by value. */
314 int scalar_by_ref_to_by_val
;
316 /* Number of aggregate parameters that were replaced by one or more of their
318 int aggregate_params_reduced
;
320 /* Numbber of components created when splitting aggregate parameters. */
321 int param_reductions_created
;
325 dump_access (FILE *f
, struct access
*access
, bool grp
)
327 fprintf (f
, "access { ");
328 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
329 print_generic_expr (f
, access
->base
, 0);
330 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
331 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
332 fprintf (f
, ", expr = ");
333 print_generic_expr (f
, access
->expr
, 0);
334 fprintf (f
, ", type = ");
335 print_generic_expr (f
, access
->type
, 0);
337 fprintf (f
, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
338 "grp_covered = %d, grp_unscalarizable_region = %d, "
339 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
340 "grp_to_be_replaced = %d\n grp_maybe_modified = %d, "
341 "grp_not_necessarilly_dereferenced = %d\n",
342 access
->grp_write
, access
->grp_read
, access
->grp_hint
,
343 access
->grp_covered
, access
->grp_unscalarizable_region
,
344 access
->grp_unscalarized_data
, access
->grp_partial_lhs
,
345 access
->grp_to_be_replaced
, access
->grp_maybe_modified
,
346 access
->grp_not_necessarilly_dereferenced
);
348 fprintf (f
, ", write = %d, grp_partial_lhs = %d\n", access
->write
,
349 access
->grp_partial_lhs
);
352 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
355 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
361 for (i
= 0; i
< level
; i
++)
362 fputs ("* ", dump_file
);
364 dump_access (f
, access
, true);
366 if (access
->first_child
)
367 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
369 access
= access
->next_sibling
;
374 /* Dump all access trees for a variable, given the pointer to the first root in
378 dump_access_tree (FILE *f
, struct access
*access
)
380 for (; access
; access
= access
->next_grp
)
381 dump_access_tree_1 (f
, access
, 0);
384 /* Return true iff ACC is non-NULL and has subaccesses. */
387 access_has_children_p (struct access
*acc
)
389 return acc
&& acc
->first_child
;
392 /* Return a vector of pointers to accesses for the variable given in BASE or
393 NULL if there is none. */
395 static VEC (access_p
, heap
) *
396 get_base_access_vector (tree base
)
400 slot
= pointer_map_contains (base_access_vec
, base
);
404 return *(VEC (access_p
, heap
) **) slot
;
407 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
408 in ACCESS. Return NULL if it cannot be found. */
410 static struct access
*
411 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
414 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
416 struct access
*child
= access
->first_child
;
418 while (child
&& (child
->offset
+ child
->size
<= offset
))
419 child
= child
->next_sibling
;
426 /* Return the first group representative for DECL or NULL if none exists. */
428 static struct access
*
429 get_first_repr_for_decl (tree base
)
431 VEC (access_p
, heap
) *access_vec
;
433 access_vec
= get_base_access_vector (base
);
437 return VEC_index (access_p
, access_vec
, 0);
440 /* Find an access representative for the variable BASE and given OFFSET and
441 SIZE. Requires that access trees have already been built. Return NULL if
442 it cannot be found. */
444 static struct access
*
445 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
448 struct access
*access
;
450 access
= get_first_repr_for_decl (base
);
451 while (access
&& (access
->offset
+ access
->size
<= offset
))
452 access
= access
->next_grp
;
456 return find_access_in_subtree (access
, offset
, size
);
459 /* Add LINK to the linked list of assign links of RACC. */
461 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
463 gcc_assert (link
->racc
== racc
);
465 if (!racc
->first_link
)
467 gcc_assert (!racc
->last_link
);
468 racc
->first_link
= link
;
471 racc
->last_link
->next
= link
;
473 racc
->last_link
= link
;
477 /* Move all link structures in their linked list in OLD_RACC to the linked list
480 relink_to_new_repr (struct access
*new_racc
, struct access
*old_racc
)
482 if (!old_racc
->first_link
)
484 gcc_assert (!old_racc
->last_link
);
488 if (new_racc
->first_link
)
490 gcc_assert (!new_racc
->last_link
->next
);
491 gcc_assert (!old_racc
->last_link
|| !old_racc
->last_link
->next
);
493 new_racc
->last_link
->next
= old_racc
->first_link
;
494 new_racc
->last_link
= old_racc
->last_link
;
498 gcc_assert (!new_racc
->last_link
);
500 new_racc
->first_link
= old_racc
->first_link
;
501 new_racc
->last_link
= old_racc
->last_link
;
503 old_racc
->first_link
= old_racc
->last_link
= NULL
;
506 /* Add ACCESS to the work queue (which is actually a stack). */
509 add_access_to_work_queue (struct access
*access
)
511 if (!access
->grp_queued
)
513 gcc_assert (!access
->next_queued
);
514 access
->next_queued
= work_queue_head
;
515 access
->grp_queued
= 1;
516 work_queue_head
= access
;
520 /* Pop an access from the work queue, and return it, assuming there is one. */
522 static struct access
*
523 pop_access_from_work_queue (void)
525 struct access
*access
= work_queue_head
;
527 work_queue_head
= access
->next_queued
;
528 access
->next_queued
= NULL
;
529 access
->grp_queued
= 0;
534 /* Allocate necessary structures. */
537 sra_initialize (void)
539 candidate_bitmap
= BITMAP_ALLOC (NULL
);
540 gcc_obstack_init (&name_obstack
);
541 access_pool
= create_alloc_pool ("SRA accesses", sizeof (struct access
), 16);
542 link_pool
= create_alloc_pool ("SRA links", sizeof (struct assign_link
), 16);
543 base_access_vec
= pointer_map_create ();
544 memset (&sra_stats
, 0, sizeof (sra_stats
));
545 encountered_apply_args
= false;
548 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
551 delete_base_accesses (const void *key ATTRIBUTE_UNUSED
, void **value
,
552 void *data ATTRIBUTE_UNUSED
)
554 VEC (access_p
, heap
) *access_vec
;
555 access_vec
= (VEC (access_p
, heap
) *) *value
;
556 VEC_free (access_p
, heap
, access_vec
);
561 /* Deallocate all general structures. */
564 sra_deinitialize (void)
566 BITMAP_FREE (candidate_bitmap
);
567 free_alloc_pool (access_pool
);
568 free_alloc_pool (link_pool
);
569 obstack_free (&name_obstack
, NULL
);
571 pointer_map_traverse (base_access_vec
, delete_base_accesses
, NULL
);
572 pointer_map_destroy (base_access_vec
);
575 /* Remove DECL from candidates for SRA and write REASON to the dump file if
578 disqualify_candidate (tree decl
, const char *reason
)
580 bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
));
582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
584 fprintf (dump_file
, "! Disqualifying ");
585 print_generic_expr (dump_file
, decl
, 0);
586 fprintf (dump_file
, " - %s\n", reason
);
590 /* Return true iff the type contains a field or an element which does not allow
594 type_internals_preclude_sra_p (tree type
)
599 switch (TREE_CODE (type
))
603 case QUAL_UNION_TYPE
:
604 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
605 if (TREE_CODE (fld
) == FIELD_DECL
)
607 tree ft
= TREE_TYPE (fld
);
609 if (TREE_THIS_VOLATILE (fld
)
610 || !DECL_FIELD_OFFSET (fld
) || !DECL_SIZE (fld
)
611 || !host_integerp (DECL_FIELD_OFFSET (fld
), 1)
612 || !host_integerp (DECL_SIZE (fld
), 1))
615 if (AGGREGATE_TYPE_P (ft
)
616 && type_internals_preclude_sra_p (ft
))
623 et
= TREE_TYPE (type
);
625 if (AGGREGATE_TYPE_P (et
))
626 return type_internals_preclude_sra_p (et
);
635 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
636 base variable if it is. Return T if it is not an SSA_NAME. */
639 get_ssa_base_param (tree t
)
641 if (TREE_CODE (t
) == SSA_NAME
)
643 if (SSA_NAME_IS_DEFAULT_DEF (t
))
644 return SSA_NAME_VAR (t
);
651 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
652 belongs to, unless the BB has already been marked as a potentially
656 mark_parm_dereference (tree base
, HOST_WIDE_INT dist
, gimple stmt
)
658 basic_block bb
= gimple_bb (stmt
);
659 int idx
, parm_index
= 0;
662 if (bitmap_bit_p (final_bbs
, bb
->index
))
665 for (parm
= DECL_ARGUMENTS (current_function_decl
);
666 parm
&& parm
!= base
;
667 parm
= TREE_CHAIN (parm
))
670 gcc_assert (parm_index
< func_param_count
);
672 idx
= bb
->index
* func_param_count
+ parm_index
;
673 if (bb_dereferences
[idx
] < dist
)
674 bb_dereferences
[idx
] = dist
;
677 /* Create and insert access for EXPR. Return created access, or NULL if it is
680 static struct access
*
681 create_access (tree expr
, gimple stmt
, bool write
)
683 struct access
*access
;
685 VEC (access_p
,heap
) *vec
;
686 HOST_WIDE_INT offset
, size
, max_size
;
688 bool ptr
, unscalarizable_region
= false;
690 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
692 if (sra_mode
== SRA_MODE_EARLY_IPA
&& INDIRECT_REF_P (base
))
694 base
= get_ssa_base_param (TREE_OPERAND (base
, 0));
702 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
705 if (sra_mode
== SRA_MODE_EARLY_IPA
)
707 if (size
< 0 || size
!= max_size
)
709 disqualify_candidate (base
, "Encountered a variable sized access.");
712 if ((offset
% BITS_PER_UNIT
) != 0 || (size
% BITS_PER_UNIT
) != 0)
714 disqualify_candidate (base
,
715 "Encountered an acces not aligned to a byte.");
720 mark_parm_dereference (base
, offset
+ size
, stmt
);
724 if (size
!= max_size
)
727 unscalarizable_region
= true;
731 disqualify_candidate (base
, "Encountered an unconstrained access.");
736 access
= (struct access
*) pool_alloc (access_pool
);
737 memset (access
, 0, sizeof (struct access
));
740 access
->offset
= offset
;
743 access
->type
= TREE_TYPE (expr
);
744 access
->write
= write
;
745 access
->grp_unscalarizable_region
= unscalarizable_region
;
748 slot
= pointer_map_contains (base_access_vec
, base
);
750 vec
= (VEC (access_p
, heap
) *) *slot
;
752 vec
= VEC_alloc (access_p
, heap
, 32);
754 VEC_safe_push (access_p
, heap
, vec
, access
);
756 *((struct VEC (access_p
,heap
) **)
757 pointer_map_insert (base_access_vec
, base
)) = vec
;
763 /* Search the given tree for a declaration by skipping handled components and
764 exclude it from the candidates. */
767 disqualify_base_of_expr (tree t
, const char *reason
)
769 while (handled_component_p (t
))
770 t
= TREE_OPERAND (t
, 0);
772 if (sra_mode
== SRA_MODE_EARLY_IPA
)
774 if (INDIRECT_REF_P (t
))
775 t
= TREE_OPERAND (t
, 0);
776 t
= get_ssa_base_param (t
);
780 disqualify_candidate (t
, reason
);
783 /* Scan expression EXPR and create access structures for all accesses to
784 candidates for scalarization. Return the created access or NULL if none is
787 static struct access
*
788 build_access_from_expr_1 (tree
*expr_ptr
, gimple stmt
, bool write
)
790 struct access
*ret
= NULL
;
791 tree expr
= *expr_ptr
;
794 if (TREE_CODE (expr
) == BIT_FIELD_REF
795 || TREE_CODE (expr
) == IMAGPART_EXPR
796 || TREE_CODE (expr
) == REALPART_EXPR
)
798 expr
= TREE_OPERAND (expr
, 0);
804 /* We need to dive through V_C_Es in order to get the size of its parameter
805 and not the result type. Ada produces such statements. We are also
806 capable of handling the topmost V_C_E but not any of those buried in other
807 handled components. */
808 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
809 expr
= TREE_OPERAND (expr
, 0);
811 if (contains_view_convert_expr_p (expr
))
813 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
818 switch (TREE_CODE (expr
))
821 if (sra_mode
!= SRA_MODE_EARLY_IPA
)
829 case ARRAY_RANGE_REF
:
830 ret
= create_access (expr
, stmt
, write
);
837 if (write
&& partial_ref
&& ret
)
838 ret
->grp_partial_lhs
= 1;
843 /* Callback of scan_function. Scan expression EXPR and create access
844 structures for all accesses to candidates for scalarization. Return true if
845 any access has been inserted. */
848 build_access_from_expr (tree
*expr_ptr
,
849 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
, bool write
,
850 void *data ATTRIBUTE_UNUSED
)
852 return build_access_from_expr_1 (expr_ptr
, gsi_stmt (*gsi
), write
) != NULL
;
855 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
856 modes in which it matters, return true iff they have been disqualified. RHS
857 may be NULL, in that case ignore it. If we scalarize an aggregate in
858 intra-SRA we may need to add statements after each statement. This is not
859 possible if a statement unconditionally has to end the basic block. */
861 disqualify_ops_if_throwing_stmt (gimple stmt
, tree lhs
, tree rhs
)
863 if ((sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
864 && (stmt_can_throw_internal (stmt
) || stmt_ends_bb_p (stmt
)))
866 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
868 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
875 /* Result code for scan_assign callback for scan_function. */
876 enum scan_assign_result
{ SRA_SA_NONE
, /* nothing done for the stmt */
877 SRA_SA_PROCESSED
, /* stmt analyzed/changed */
878 SRA_SA_REMOVED
}; /* stmt redundant and eliminated */
881 /* Callback of scan_function. Scan expressions occuring in the statement
882 pointed to by STMT_EXPR, create access structures for all accesses to
883 candidates for scalarization and remove those candidates which occur in
884 statements or expressions that prevent them from being split apart. Return
885 true if any access has been inserted. */
887 static enum scan_assign_result
888 build_accesses_from_assign (gimple
*stmt_ptr
,
889 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
890 void *data ATTRIBUTE_UNUSED
)
892 gimple stmt
= *stmt_ptr
;
893 tree
*lhs_ptr
, *rhs_ptr
;
894 struct access
*lacc
, *racc
;
896 if (!gimple_assign_single_p (stmt
))
899 lhs_ptr
= gimple_assign_lhs_ptr (stmt
);
900 rhs_ptr
= gimple_assign_rhs1_ptr (stmt
);
902 if (disqualify_ops_if_throwing_stmt (stmt
, *lhs_ptr
, *rhs_ptr
))
905 racc
= build_access_from_expr_1 (rhs_ptr
, stmt
, false);
906 lacc
= build_access_from_expr_1 (lhs_ptr
, stmt
, true);
909 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
910 && !lacc
->grp_unscalarizable_region
911 && !racc
->grp_unscalarizable_region
912 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr
))
913 /* FIXME: Turn the following line into an assert after PR 40058 is
915 && lacc
->size
== racc
->size
916 && useless_type_conversion_p (lacc
->type
, racc
->type
))
918 struct assign_link
*link
;
920 link
= (struct assign_link
*) pool_alloc (link_pool
);
921 memset (link
, 0, sizeof (struct assign_link
));
926 add_link_to_rhs (racc
, link
);
929 return (lacc
|| racc
) ? SRA_SA_PROCESSED
: SRA_SA_NONE
;
932 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
933 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
936 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED
, tree op
,
937 void *data ATTRIBUTE_UNUSED
)
940 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
946 /* Scan function and look for interesting statements. Return true if any has
947 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
948 called on all expressions within statements except assign statements and
949 those deemed entirely unsuitable for some reason (all operands in such
950 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
951 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
952 called on assign statements and those call statements which have a lhs, it
953 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
954 pass and thus no statement is being modified. DATA is a pointer passed to
955 all callbacks. If any single callback returns true, this function also
956 returns true, otherwise it returns false. */
959 scan_function (bool (*scan_expr
) (tree
*, gimple_stmt_iterator
*, bool, void *),
960 enum scan_assign_result (*scan_assign
) (gimple
*,
961 gimple_stmt_iterator
*,
963 bool (*handle_ssa_defs
)(gimple
, void *),
964 bool analysis_stage
, void *data
)
966 gimple_stmt_iterator gsi
;
974 bool bb_changed
= false;
977 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
978 ret
|= handle_ssa_defs (gsi_stmt (gsi
), data
);
980 gsi
= gsi_start_bb (bb
);
981 while (!gsi_end_p (gsi
))
983 gimple stmt
= gsi_stmt (gsi
);
984 enum scan_assign_result assign_result
;
985 bool any
= false, deleted
= false;
987 if (analysis_stage
&& final_bbs
&& stmt_can_throw_external (stmt
))
988 bitmap_set_bit (final_bbs
, bb
->index
);
989 switch (gimple_code (stmt
))
992 t
= gimple_return_retval_ptr (stmt
);
994 any
|= scan_expr (t
, &gsi
, false, data
);
995 if (analysis_stage
&& final_bbs
)
996 bitmap_set_bit (final_bbs
, bb
->index
);
1000 assign_result
= scan_assign (&stmt
, &gsi
, data
);
1001 any
|= assign_result
== SRA_SA_PROCESSED
;
1002 deleted
= assign_result
== SRA_SA_REMOVED
;
1003 if (handle_ssa_defs
&& assign_result
!= SRA_SA_REMOVED
)
1004 any
|= handle_ssa_defs (stmt
, data
);
1008 /* Operands must be processed before the lhs. */
1009 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1011 tree
*argp
= gimple_call_arg_ptr (stmt
, i
);
1012 any
|= scan_expr (argp
, &gsi
, false, data
);
1017 tree dest
= gimple_call_fndecl (stmt
);
1018 int flags
= gimple_call_flags (stmt
);
1021 && DECL_BUILT_IN_CLASS (dest
) == BUILT_IN_NORMAL
1022 && DECL_FUNCTION_CODE (dest
) == BUILT_IN_APPLY_ARGS
)
1023 encountered_apply_args
= true;
1026 && (flags
& (ECF_CONST
| ECF_PURE
)) == 0)
1027 bitmap_set_bit (final_bbs
, bb
->index
);
1030 if (gimple_call_lhs (stmt
))
1032 tree
*lhs_ptr
= gimple_call_lhs_ptr (stmt
);
1034 || !disqualify_ops_if_throwing_stmt (stmt
,
1037 any
|= scan_expr (lhs_ptr
, &gsi
, true, data
);
1038 if (handle_ssa_defs
)
1039 any
|= handle_ssa_defs (stmt
, data
);
1047 walk_stmt_load_store_addr_ops (stmt
, NULL
, NULL
, NULL
,
1050 bitmap_set_bit (final_bbs
, bb
->index
);
1052 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
1054 tree
*op
= &TREE_VALUE (gimple_asm_input_op (stmt
, i
));
1055 any
|= scan_expr (op
, &gsi
, false, data
);
1057 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
1059 tree
*op
= &TREE_VALUE (gimple_asm_output_op (stmt
, i
));
1060 any
|= scan_expr (op
, &gsi
, true, data
);
1072 if (!analysis_stage
)
1076 maybe_clean_eh_stmt (stmt
);
1087 if (!analysis_stage
&& bb_changed
&& sra_mode
== SRA_MODE_EARLY_IPA
)
1088 gimple_purge_dead_eh_edges (bb
);
1094 /* Helper of QSORT function. There are pointers to accesses in the array. An
1095 access is considered smaller than another if it has smaller offset or if the
1096 offsets are the same but is size is bigger. */
1099 compare_access_positions (const void *a
, const void *b
)
1101 const access_p
*fp1
= (const access_p
*) a
;
1102 const access_p
*fp2
= (const access_p
*) b
;
1103 const access_p f1
= *fp1
;
1104 const access_p f2
= *fp2
;
1106 if (f1
->offset
!= f2
->offset
)
1107 return f1
->offset
< f2
->offset
? -1 : 1;
1109 if (f1
->size
== f2
->size
)
1111 /* Put any non-aggregate type before any aggregate type. */
1112 if (!is_gimple_reg_type (f1
->type
)
1113 && is_gimple_reg_type (f2
->type
))
1115 else if (is_gimple_reg_type (f1
->type
)
1116 && !is_gimple_reg_type (f2
->type
))
1118 /* Put the integral type with the bigger precision first. */
1119 else if (INTEGRAL_TYPE_P (f1
->type
)
1120 && INTEGRAL_TYPE_P (f2
->type
))
1121 return TYPE_PRECISION (f1
->type
) > TYPE_PRECISION (f2
->type
) ? -1 : 1;
1122 /* Put any integral type with non-full precision last. */
1123 else if (INTEGRAL_TYPE_P (f1
->type
)
1124 && (TREE_INT_CST_LOW (TYPE_SIZE (f1
->type
))
1125 != TYPE_PRECISION (f1
->type
)))
1127 else if (INTEGRAL_TYPE_P (f2
->type
)
1128 && (TREE_INT_CST_LOW (TYPE_SIZE (f2
->type
))
1129 != TYPE_PRECISION (f2
->type
)))
1131 /* Stabilize the sort. */
1132 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1135 /* We want the bigger accesses first, thus the opposite operator in the next
1137 return f1
->size
> f2
->size
? -1 : 1;
1141 /* Append a name of the declaration to the name obstack. A helper function for
1145 make_fancy_decl_name (tree decl
)
1149 tree name
= DECL_NAME (decl
);
1151 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1152 IDENTIFIER_LENGTH (name
));
1155 sprintf (buffer
, "D%u", DECL_UID (decl
));
1156 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1160 /* Helper for make_fancy_name. */
1163 make_fancy_name_1 (tree expr
)
1170 make_fancy_decl_name (expr
);
1174 switch (TREE_CODE (expr
))
1177 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1178 obstack_1grow (&name_obstack
, '$');
1179 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1183 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1184 obstack_1grow (&name_obstack
, '$');
1185 /* Arrays with only one element may not have a constant as their
1187 index
= TREE_OPERAND (expr
, 1);
1188 if (TREE_CODE (index
) != INTEGER_CST
)
1190 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1191 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1198 gcc_unreachable (); /* we treat these as scalars. */
1205 /* Create a human readable name for replacement variable of ACCESS. */
1208 make_fancy_name (tree expr
)
1210 make_fancy_name_1 (expr
);
1211 obstack_1grow (&name_obstack
, '\0');
1212 return XOBFINISH (&name_obstack
, char *);
1215 /* Helper function for build_ref_for_offset. */
1218 build_ref_for_offset_1 (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1224 tree tr_size
, index
, minidx
;
1225 HOST_WIDE_INT el_size
;
1227 if (offset
== 0 && exp_type
1228 && types_compatible_p (exp_type
, type
))
1231 switch (TREE_CODE (type
))
1234 case QUAL_UNION_TYPE
:
1236 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
1238 HOST_WIDE_INT pos
, size
;
1239 tree expr
, *expr_ptr
;
1241 if (TREE_CODE (fld
) != FIELD_DECL
)
1244 pos
= int_bit_position (fld
);
1245 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1246 tr_size
= DECL_SIZE (fld
);
1247 if (!tr_size
|| !host_integerp (tr_size
, 1))
1249 size
= tree_low_cst (tr_size
, 1);
1250 if (pos
> offset
|| (pos
+ size
) <= offset
)
1255 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1261 if (build_ref_for_offset_1 (expr_ptr
, TREE_TYPE (fld
),
1262 offset
- pos
, exp_type
))
1272 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1273 if (!tr_size
|| !host_integerp (tr_size
, 1))
1275 el_size
= tree_low_cst (tr_size
, 1);
1277 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1278 if (TREE_CODE (minidx
) != INTEGER_CST
)
1282 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1283 if (!integer_zerop (minidx
))
1284 index
= int_const_binop (PLUS_EXPR
, index
, minidx
, 0);
1285 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1286 NULL_TREE
, NULL_TREE
);
1288 offset
= offset
% el_size
;
1289 type
= TREE_TYPE (type
);
1304 /* Construct an expression that would reference a part of aggregate *EXPR of
1305 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1306 function only determines whether it can build such a reference without
1307 actually doing it, otherwise, the tree it points to is unshared first and
1308 then used as a base for furhter sub-references.
1310 FIXME: Eventually this should be replaced with
1311 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1312 minor rewrite of fold_stmt.
1316 build_ref_for_offset (tree
*expr
, tree type
, HOST_WIDE_INT offset
,
1317 tree exp_type
, bool allow_ptr
)
1319 location_t loc
= expr
? EXPR_LOCATION (*expr
) : UNKNOWN_LOCATION
;
1322 *expr
= unshare_expr (*expr
);
1324 if (allow_ptr
&& POINTER_TYPE_P (type
))
1326 type
= TREE_TYPE (type
);
1328 *expr
= fold_build1_loc (loc
, INDIRECT_REF
, type
, *expr
);
1331 return build_ref_for_offset_1 (expr
, type
, offset
, exp_type
);
1334 /* Return true iff TYPE is stdarg va_list type. */
1337 is_va_list_type (tree type
)
1339 return TYPE_MAIN_VARIANT (type
) == TYPE_MAIN_VARIANT (va_list_type_node
);
1342 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1343 those with type which is suitable for scalarization. */
1346 find_var_candidates (void)
1349 referenced_var_iterator rvi
;
1352 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1354 if (TREE_CODE (var
) != VAR_DECL
&& TREE_CODE (var
) != PARM_DECL
)
1356 type
= TREE_TYPE (var
);
1358 if (!AGGREGATE_TYPE_P (type
)
1359 || needs_to_live_in_memory (var
)
1360 || TREE_THIS_VOLATILE (var
)
1361 || !COMPLETE_TYPE_P (type
)
1362 || !host_integerp (TYPE_SIZE (type
), 1)
1363 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
1364 || type_internals_preclude_sra_p (type
)
1365 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1366 we also want to schedule it rather late. Thus we ignore it in
1368 || (sra_mode
== SRA_MODE_EARLY_INTRA
1369 && is_va_list_type (type
)))
1372 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1376 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1377 print_generic_expr (dump_file
, var
, 0);
1378 fprintf (dump_file
, "\n");
1386 /* Sort all accesses for the given variable, check for partial overlaps and
1387 return NULL if there are any. If there are none, pick a representative for
1388 each combination of offset and size and create a linked list out of them.
1389 Return the pointer to the first representative and make sure it is the first
1390 one in the vector of accesses. */
1392 static struct access
*
1393 sort_and_splice_var_accesses (tree var
)
1395 int i
, j
, access_count
;
1396 struct access
*res
, **prev_acc_ptr
= &res
;
1397 VEC (access_p
, heap
) *access_vec
;
1399 HOST_WIDE_INT low
= -1, high
= 0;
1401 access_vec
= get_base_access_vector (var
);
1404 access_count
= VEC_length (access_p
, access_vec
);
1406 /* Sort by <OFFSET, SIZE>. */
1407 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
1408 compare_access_positions
);
1411 while (i
< access_count
)
1413 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
1414 bool grp_write
= access
->write
;
1415 bool grp_read
= !access
->write
;
1416 bool multiple_reads
= false;
1417 bool grp_partial_lhs
= access
->grp_partial_lhs
;
1418 bool first_scalar
= is_gimple_reg_type (access
->type
);
1419 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
1421 if (first
|| access
->offset
>= high
)
1424 low
= access
->offset
;
1425 high
= access
->offset
+ access
->size
;
1427 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
1430 gcc_assert (access
->offset
>= low
1431 && access
->offset
+ access
->size
<= high
);
1434 while (j
< access_count
)
1436 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
1437 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
1444 multiple_reads
= true;
1448 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
1449 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
1450 relink_to_new_repr (access
, ac2
);
1452 /* If there are both aggregate-type and scalar-type accesses with
1453 this combination of size and offset, the comparison function
1454 should have put the scalars first. */
1455 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
1456 ac2
->group_representative
= access
;
1462 access
->group_representative
= access
;
1463 access
->grp_write
= grp_write
;
1464 access
->grp_read
= grp_read
;
1465 access
->grp_hint
= multiple_reads
;
1466 access
->grp_partial_lhs
= grp_partial_lhs
;
1467 access
->grp_unscalarizable_region
= unscalarizable_region
;
1468 if (access
->first_link
)
1469 add_access_to_work_queue (access
);
1471 *prev_acc_ptr
= access
;
1472 prev_acc_ptr
= &access
->next_grp
;
1475 gcc_assert (res
== VEC_index (access_p
, access_vec
, 0));
1479 /* Create a variable for the given ACCESS which determines the type, name and a
1480 few other properties. Return the variable declaration and store it also to
1481 ACCESS->replacement. */
1484 create_access_replacement (struct access
*access
)
1488 repl
= create_tmp_var (access
->type
, "SR");
1490 add_referenced_var (repl
);
1491 mark_sym_for_renaming (repl
);
1493 if (!access
->grp_partial_lhs
1494 && (TREE_CODE (access
->type
) == COMPLEX_TYPE
1495 || TREE_CODE (access
->type
) == VECTOR_TYPE
))
1496 DECL_GIMPLE_REG_P (repl
) = 1;
1498 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
1499 DECL_ARTIFICIAL (repl
) = 1;
1501 if (DECL_NAME (access
->base
)
1502 && !DECL_IGNORED_P (access
->base
)
1503 && !DECL_ARTIFICIAL (access
->base
))
1505 char *pretty_name
= make_fancy_name (access
->expr
);
1507 DECL_NAME (repl
) = get_identifier (pretty_name
);
1508 obstack_free (&name_obstack
, pretty_name
);
1510 SET_DECL_DEBUG_EXPR (repl
, access
->expr
);
1511 DECL_DEBUG_EXPR_IS_FROM (repl
) = 1;
1512 DECL_IGNORED_P (repl
) = 0;
1515 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
1516 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
1520 fprintf (dump_file
, "Created a replacement for ");
1521 print_generic_expr (dump_file
, access
->base
, 0);
1522 fprintf (dump_file
, " offset: %u, size: %u: ",
1523 (unsigned) access
->offset
, (unsigned) access
->size
);
1524 print_generic_expr (dump_file
, repl
, 0);
1525 fprintf (dump_file
, "\n");
1527 sra_stats
.replacements
++;
1532 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1535 get_access_replacement (struct access
*access
)
1537 gcc_assert (access
->grp_to_be_replaced
);
1539 if (!access
->replacement_decl
)
1540 access
->replacement_decl
= create_access_replacement (access
);
1541 return access
->replacement_decl
;
1544 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1545 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1546 to it is not "within" the root. */
1549 build_access_subtree (struct access
**access
)
1551 struct access
*root
= *access
, *last_child
= NULL
;
1552 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1554 *access
= (*access
)->next_grp
;
1555 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
1558 root
->first_child
= *access
;
1560 last_child
->next_sibling
= *access
;
1561 last_child
= *access
;
1563 build_access_subtree (access
);
1567 /* Build a tree of access representatives, ACCESS is the pointer to the first
1568 one, others are linked in a list by the next_grp field. Decide about scalar
1569 replacements on the way, return true iff any are to be created. */
1572 build_access_trees (struct access
*access
)
1576 struct access
*root
= access
;
1578 build_access_subtree (&access
);
1579 root
->next_grp
= access
;
1583 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1587 expr_with_var_bounded_array_refs_p (tree expr
)
1589 while (handled_component_p (expr
))
1591 if (TREE_CODE (expr
) == ARRAY_REF
1592 && !host_integerp (array_ref_low_bound (expr
), 0))
1594 expr
= TREE_OPERAND (expr
, 0);
1599 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1600 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1601 all sorts of access flags appropriately along the way, notably always ser
1602 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1605 analyze_access_subtree (struct access
*root
, bool allow_replacements
,
1606 bool mark_read
, bool mark_write
)
1608 struct access
*child
;
1609 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1610 HOST_WIDE_INT covered_to
= root
->offset
;
1611 bool scalar
= is_gimple_reg_type (root
->type
);
1612 bool hole
= false, sth_created
= false;
1613 bool direct_read
= root
->grp_read
;
1616 root
->grp_read
= true;
1617 else if (root
->grp_read
)
1621 root
->grp_write
= true;
1622 else if (root
->grp_write
)
1625 if (root
->grp_unscalarizable_region
)
1626 allow_replacements
= false;
1628 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
1629 allow_replacements
= false;
1631 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
1633 if (!hole
&& child
->offset
< covered_to
)
1636 covered_to
+= child
->size
;
1638 sth_created
|= analyze_access_subtree (child
, allow_replacements
,
1639 mark_read
, mark_write
);
1641 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
1642 hole
|= !child
->grp_covered
;
1645 if (allow_replacements
&& scalar
&& !root
->first_child
1647 || (direct_read
&& root
->grp_write
)))
1649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1651 fprintf (dump_file
, "Marking ");
1652 print_generic_expr (dump_file
, root
->base
, 0);
1653 fprintf (dump_file
, " offset: %u, size: %u: ",
1654 (unsigned) root
->offset
, (unsigned) root
->size
);
1655 fprintf (dump_file
, " to be replaced.\n");
1658 root
->grp_to_be_replaced
= 1;
1662 else if (covered_to
< limit
)
1665 if (sth_created
&& !hole
)
1667 root
->grp_covered
= 1;
1670 if (root
->grp_write
|| TREE_CODE (root
->base
) == PARM_DECL
)
1671 root
->grp_unscalarized_data
= 1; /* not covered and written to */
1677 /* Analyze all access trees linked by next_grp by the means of
1678 analyze_access_subtree. */
1680 analyze_access_trees (struct access
*access
)
1686 if (analyze_access_subtree (access
, true, false, false))
1688 access
= access
->next_grp
;
1694 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1695 SIZE would conflict with an already existing one. If exactly such a child
1696 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1699 child_would_conflict_in_lacc (struct access
*lacc
, HOST_WIDE_INT norm_offset
,
1700 HOST_WIDE_INT size
, struct access
**exact_match
)
1702 struct access
*child
;
1704 for (child
= lacc
->first_child
; child
; child
= child
->next_sibling
)
1706 if (child
->offset
== norm_offset
&& child
->size
== size
)
1708 *exact_match
= child
;
1712 if (child
->offset
< norm_offset
+ size
1713 && child
->offset
+ child
->size
> norm_offset
)
1720 /* Create a new child access of PARENT, with all properties just like MODEL
1721 except for its offset and with its grp_write false and grp_read true.
1722 Return the new access or NULL if it cannot be created. Note that this access
1723 is created long after all splicing and sorting, it's not located in any
1724 access vector and is automatically a representative of its group. */
1726 static struct access
*
1727 create_artificial_child_access (struct access
*parent
, struct access
*model
,
1728 HOST_WIDE_INT new_offset
)
1730 struct access
*access
;
1731 struct access
**child
;
1732 tree expr
= parent
->base
;;
1734 gcc_assert (!model
->grp_unscalarizable_region
);
1736 if (!build_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
1737 model
->type
, false))
1740 access
= (struct access
*) pool_alloc (access_pool
);
1741 memset (access
, 0, sizeof (struct access
));
1742 access
->base
= parent
->base
;
1743 access
->expr
= expr
;
1744 access
->offset
= new_offset
;
1745 access
->size
= model
->size
;
1746 access
->type
= model
->type
;
1747 access
->grp_write
= true;
1748 access
->grp_read
= false;
1750 child
= &parent
->first_child
;
1751 while (*child
&& (*child
)->offset
< new_offset
)
1752 child
= &(*child
)->next_sibling
;
1754 access
->next_sibling
= *child
;
1761 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1762 true if any new subaccess was created. Additionally, if RACC is a scalar
1763 access but LACC is not, change the type of the latter, if possible. */
1766 propagate_subaccesses_across_link (struct access
*lacc
, struct access
*racc
)
1768 struct access
*rchild
;
1769 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
1772 if (is_gimple_reg_type (lacc
->type
)
1773 || lacc
->grp_unscalarizable_region
1774 || racc
->grp_unscalarizable_region
)
1777 if (!lacc
->first_child
&& !racc
->first_child
1778 && is_gimple_reg_type (racc
->type
))
1780 tree t
= lacc
->base
;
1782 if (build_ref_for_offset (&t
, TREE_TYPE (t
), lacc
->offset
, racc
->type
,
1786 lacc
->type
= racc
->type
;
1791 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
1793 struct access
*new_acc
= NULL
;
1794 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
1796 if (rchild
->grp_unscalarizable_region
)
1799 if (child_would_conflict_in_lacc (lacc
, norm_offset
, rchild
->size
,
1804 rchild
->grp_hint
= 1;
1805 new_acc
->grp_hint
|= new_acc
->grp_read
;
1806 if (rchild
->first_child
)
1807 ret
|= propagate_subaccesses_across_link (new_acc
, rchild
);
1812 /* If a (part of) a union field is on the RHS of an assignment, it can
1813 have sub-accesses which do not make sense on the LHS (PR 40351).
1814 Check that this is not the case. */
1815 if (!build_ref_for_offset (NULL
, TREE_TYPE (lacc
->base
), norm_offset
,
1816 rchild
->type
, false))
1819 rchild
->grp_hint
= 1;
1820 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
);
1824 if (racc
->first_child
)
1825 propagate_subaccesses_across_link (new_acc
, rchild
);
1832 /* Propagate all subaccesses across assignment links. */
1835 propagate_all_subaccesses (void)
1837 while (work_queue_head
)
1839 struct access
*racc
= pop_access_from_work_queue ();
1840 struct assign_link
*link
;
1842 gcc_assert (racc
->first_link
);
1844 for (link
= racc
->first_link
; link
; link
= link
->next
)
1846 struct access
*lacc
= link
->lacc
;
1848 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
1850 lacc
= lacc
->group_representative
;
1851 if (propagate_subaccesses_across_link (lacc
, racc
)
1852 && lacc
->first_link
)
1853 add_access_to_work_queue (lacc
);
1858 /* Go through all accesses collected throughout the (intraprocedural) analysis
1859 stage, exclude overlapping ones, identify representatives and build trees
1860 out of them, making decisions about scalarization on the way. Return true
1861 iff there are any to-be-scalarized variables after this stage. */
1864 analyze_all_variable_accesses (void)
1867 referenced_var_iterator rvi
;
1870 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1871 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1873 struct access
*access
;
1875 access
= sort_and_splice_var_accesses (var
);
1877 build_access_trees (access
);
1879 disqualify_candidate (var
,
1880 "No or inhibitingly overlapping accesses.");
1883 propagate_all_subaccesses ();
1885 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1886 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1888 struct access
*access
= get_first_repr_for_decl (var
);
1890 if (analyze_access_trees (access
))
1893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1895 fprintf (dump_file
, "\nAccess trees for ");
1896 print_generic_expr (dump_file
, var
, 0);
1897 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
1898 dump_access_tree (dump_file
, access
);
1899 fprintf (dump_file
, "\n");
1903 disqualify_candidate (var
, "No scalar replacements to be created.");
1908 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
1915 /* Return true iff a reference statement into aggregate AGG can be built for
1916 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1917 or a child of its sibling. TOP_OFFSET is the offset from the processed
1918 access subtree that has to be subtracted from offset of each access. */
1921 ref_expr_for_all_replacements_p (struct access
*access
, tree agg
,
1922 HOST_WIDE_INT top_offset
)
1926 if (access
->grp_to_be_replaced
1927 && !build_ref_for_offset (NULL
, TREE_TYPE (agg
),
1928 access
->offset
- top_offset
,
1929 access
->type
, false))
1932 if (access
->first_child
1933 && !ref_expr_for_all_replacements_p (access
->first_child
, agg
,
1937 access
= access
->next_sibling
;
1944 /* Generate statements copying scalar replacements of accesses within a subtree
1945 into or out of AGG. ACCESS is the first child of the root of the subtree to
1946 be processed. AGG is an aggregate type expression (can be a declaration but
1947 does not have to be, it can for example also be an indirect_ref).
1948 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1949 from offsets of individual accesses to get corresponding offsets for AGG.
1950 If CHUNK_SIZE is non-null, copy only replacements in the interval
1951 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1952 statement iterator used to place the new statements. WRITE should be true
1953 when the statements should write from AGG to the replacement and false if
1954 vice versa. if INSERT_AFTER is true, new statements will be added after the
1955 current statement in GSI, they will be added before the statement
1959 generate_subtree_copies (struct access
*access
, tree agg
,
1960 HOST_WIDE_INT top_offset
,
1961 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
1962 gimple_stmt_iterator
*gsi
, bool write
,
1969 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
1972 if (access
->grp_to_be_replaced
1974 || access
->offset
+ access
->size
> start_offset
))
1976 tree repl
= get_access_replacement (access
);
1980 ref_found
= build_ref_for_offset (&expr
, TREE_TYPE (agg
),
1981 access
->offset
- top_offset
,
1982 access
->type
, false);
1983 gcc_assert (ref_found
);
1987 if (access
->grp_partial_lhs
)
1988 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
1990 insert_after
? GSI_NEW_STMT
1992 stmt
= gimple_build_assign (repl
, expr
);
1996 TREE_NO_WARNING (repl
) = 1;
1997 if (access
->grp_partial_lhs
)
1998 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2000 insert_after
? GSI_NEW_STMT
2002 stmt
= gimple_build_assign (expr
, repl
);
2006 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2008 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2010 sra_stats
.subtree_copies
++;
2013 if (access
->first_child
)
2014 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
2015 start_offset
, chunk_size
, gsi
,
2016 write
, insert_after
);
2018 access
= access
->next_sibling
;
2023 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2024 the root of the subtree to be processed. GSI is the statement iterator used
2025 for inserting statements which are added after the current statement if
2026 INSERT_AFTER is true or before it otherwise. */
2029 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
2033 struct access
*child
;
2035 if (access
->grp_to_be_replaced
)
2039 stmt
= gimple_build_assign (get_access_replacement (access
),
2040 fold_convert (access
->type
,
2041 integer_zero_node
));
2043 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2045 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2049 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2050 init_subtree_with_zero (child
, gsi
, insert_after
);
2053 /* Search for an access representative for the given expression EXPR and
2054 return it or NULL if it cannot be found. */
2056 static struct access
*
2057 get_access_for_expr (tree expr
)
2059 HOST_WIDE_INT offset
, size
, max_size
;
2062 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2063 a different size than the size of its argument and we need the latter
2065 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
2066 expr
= TREE_OPERAND (expr
, 0);
2068 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
2069 if (max_size
== -1 || !DECL_P (base
))
2072 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
2075 return get_var_base_offset_size_access (base
, offset
, max_size
);
2078 /* Callback for scan_function. Replace the expression EXPR with a scalar
2079 replacement if there is one and generate other statements to do type
2080 conversion or subtree copying if necessary. GSI is used to place newly
2081 created statements, WRITE is true if the expression is being written to (it
2082 is on a LHS of a statement or output in an assembly statement). */
2085 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
,
2086 void *data ATTRIBUTE_UNUSED
)
2088 struct access
*access
;
2091 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
2094 expr
= &TREE_OPERAND (*expr
, 0);
2099 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
2100 expr
= &TREE_OPERAND (*expr
, 0);
2101 access
= get_access_for_expr (*expr
);
2104 type
= TREE_TYPE (*expr
);
2106 if (access
->grp_to_be_replaced
)
2108 tree repl
= get_access_replacement (access
);
2109 /* If we replace a non-register typed access simply use the original
2110 access expression to extract the scalar component afterwards.
2111 This happens if scalarizing a function return value or parameter
2112 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2113 gcc.c-torture/compile/20011217-1.c. */
2114 if (!is_gimple_reg_type (type
))
2119 tree ref
= unshare_expr (access
->expr
);
2120 if (access
->grp_partial_lhs
)
2121 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
2122 false, GSI_NEW_STMT
);
2123 stmt
= gimple_build_assign (repl
, ref
);
2124 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2128 if (access
->grp_partial_lhs
)
2129 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2130 true, GSI_SAME_STMT
);
2131 stmt
= gimple_build_assign (unshare_expr (access
->expr
), repl
);
2132 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2137 gcc_assert (useless_type_conversion_p (type
, access
->type
));
2143 if (access
->first_child
)
2145 HOST_WIDE_INT start_offset
, chunk_size
;
2147 && host_integerp (TREE_OPERAND (bfr
, 1), 1)
2148 && host_integerp (TREE_OPERAND (bfr
, 2), 1))
2150 chunk_size
= tree_low_cst (TREE_OPERAND (bfr
, 1), 1);
2151 start_offset
= access
->offset
2152 + tree_low_cst (TREE_OPERAND (bfr
, 2), 1);
2155 start_offset
= chunk_size
= 0;
2157 generate_subtree_copies (access
->first_child
, access
->base
, 0,
2158 start_offset
, chunk_size
, gsi
, write
, write
);
2163 /* Where scalar replacements of the RHS have been written to when a replacement
2164 of a LHS of an assigments cannot be direclty loaded from a replacement of
2166 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
2167 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
2168 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
2170 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2171 base aggregate if there are unscalarized data or directly to LHS
2174 static enum unscalarized_data_handling
2175 handle_unscalarized_data_in_subtree (struct access
*top_racc
, tree lhs
,
2176 gimple_stmt_iterator
*gsi
)
2178 if (top_racc
->grp_unscalarized_data
)
2180 generate_subtree_copies (top_racc
->first_child
, top_racc
->base
, 0, 0, 0,
2182 return SRA_UDH_RIGHT
;
2186 generate_subtree_copies (top_racc
->first_child
, lhs
, top_racc
->offset
,
2187 0, 0, gsi
, false, false);
2188 return SRA_UDH_LEFT
;
2193 /* Try to generate statements to load all sub-replacements in an access
2194 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2195 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2196 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2197 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2198 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2199 the rhs top aggregate has already been refreshed by contents of its scalar
2200 reductions and is set to true if this function has to do it. */
2203 load_assign_lhs_subreplacements (struct access
*lacc
, struct access
*top_racc
,
2204 HOST_WIDE_INT left_offset
,
2205 HOST_WIDE_INT right_offset
,
2206 gimple_stmt_iterator
*old_gsi
,
2207 gimple_stmt_iterator
*new_gsi
,
2208 enum unscalarized_data_handling
*refreshed
,
2211 location_t loc
= EXPR_LOCATION (lacc
->expr
);
2214 if (lacc
->grp_to_be_replaced
)
2216 struct access
*racc
;
2217 HOST_WIDE_INT offset
= lacc
->offset
- left_offset
+ right_offset
;
2221 racc
= find_access_in_subtree (top_racc
, offset
, lacc
->size
);
2222 if (racc
&& racc
->grp_to_be_replaced
)
2224 rhs
= get_access_replacement (racc
);
2225 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
2226 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, lacc
->type
, rhs
);
2232 /* No suitable access on the right hand side, need to load from
2233 the aggregate. See if we have to update it first... */
2234 if (*refreshed
== SRA_UDH_NONE
)
2235 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
,
2238 if (*refreshed
== SRA_UDH_LEFT
)
2239 rhs
= unshare_expr (lacc
->expr
);
2242 rhs
= top_racc
->base
;
2243 repl_found
= build_ref_for_offset (&rhs
,
2244 TREE_TYPE (top_racc
->base
),
2245 offset
, lacc
->type
, false);
2246 gcc_assert (repl_found
);
2250 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
2251 gsi_insert_after (new_gsi
, stmt
, GSI_NEW_STMT
);
2253 sra_stats
.subreplacements
++;
2255 else if (*refreshed
== SRA_UDH_NONE
2256 && lacc
->grp_read
&& !lacc
->grp_covered
)
2257 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
, lhs
,
2260 if (lacc
->first_child
)
2261 load_assign_lhs_subreplacements (lacc
->first_child
, top_racc
,
2262 left_offset
, right_offset
,
2263 old_gsi
, new_gsi
, refreshed
, lhs
);
2264 lacc
= lacc
->next_sibling
;
2269 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2270 to the assignment and GSI is the statement iterator pointing at it. Returns
2271 the same values as sra_modify_assign. */
2273 static enum scan_assign_result
2274 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
2276 tree lhs
= gimple_assign_lhs (*stmt
);
2279 acc
= get_access_for_expr (lhs
);
2283 if (VEC_length (constructor_elt
,
2284 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt
))) > 0)
2286 /* I have never seen this code path trigger but if it can happen the
2287 following should handle it gracefully. */
2288 if (access_has_children_p (acc
))
2289 generate_subtree_copies (acc
->first_child
, acc
->base
, 0, 0, 0, gsi
,
2291 return SRA_SA_PROCESSED
;
2294 if (acc
->grp_covered
)
2296 init_subtree_with_zero (acc
, gsi
, false);
2297 unlink_stmt_vdef (*stmt
);
2298 gsi_remove (gsi
, true);
2299 return SRA_SA_REMOVED
;
2303 init_subtree_with_zero (acc
, gsi
, true);
2304 return SRA_SA_PROCESSED
;
2309 /* Callback of scan_function to process assign statements. It examines both
2310 sides of the statement, replaces them with a scalare replacement if there is
2311 one and generating copying of replacements if scalarized aggregates have been
2312 used in the assignment. STMT is a pointer to the assign statement, GSI is
2313 used to hold generated statements for type conversions and subtree
2316 static enum scan_assign_result
2317 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
2318 void *data ATTRIBUTE_UNUSED
)
2320 struct access
*lacc
, *racc
;
2322 bool modify_this_stmt
= false;
2323 bool force_gimple_rhs
= false;
2324 location_t loc
= gimple_location (*stmt
);
2326 if (!gimple_assign_single_p (*stmt
))
2328 lhs
= gimple_assign_lhs (*stmt
);
2329 rhs
= gimple_assign_rhs1 (*stmt
);
2331 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
2332 return sra_modify_constructor_assign (stmt
, gsi
);
2334 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
2335 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
2336 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
2338 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (*stmt
),
2340 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (*stmt
),
2342 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2345 lacc
= get_access_for_expr (lhs
);
2346 racc
= get_access_for_expr (rhs
);
2350 if (lacc
&& lacc
->grp_to_be_replaced
)
2352 lhs
= get_access_replacement (lacc
);
2353 gimple_assign_set_lhs (*stmt
, lhs
);
2354 modify_this_stmt
= true;
2355 if (lacc
->grp_partial_lhs
)
2356 force_gimple_rhs
= true;
2360 if (racc
&& racc
->grp_to_be_replaced
)
2362 rhs
= get_access_replacement (racc
);
2363 modify_this_stmt
= true;
2364 if (racc
->grp_partial_lhs
)
2365 force_gimple_rhs
= true;
2369 if (modify_this_stmt
)
2371 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2373 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2374 ??? This should move to fold_stmt which we simply should
2375 call after building a VIEW_CONVERT_EXPR here. */
2376 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
2377 && !access_has_children_p (lacc
))
2380 if (build_ref_for_offset (&expr
, TREE_TYPE (lhs
), 0,
2381 TREE_TYPE (rhs
), false))
2384 gimple_assign_set_lhs (*stmt
, expr
);
2387 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
2388 && !access_has_children_p (racc
))
2391 if (build_ref_for_offset (&expr
, TREE_TYPE (rhs
), 0,
2392 TREE_TYPE (lhs
), false))
2395 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2397 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
), rhs
);
2398 if (!is_gimple_reg (lhs
))
2399 force_gimple_rhs
= true;
2403 if (force_gimple_rhs
)
2404 rhs
= force_gimple_operand_gsi (gsi
, rhs
, true, NULL_TREE
,
2405 true, GSI_SAME_STMT
);
2406 if (gimple_assign_rhs1 (*stmt
) != rhs
)
2408 gimple_assign_set_rhs_from_tree (gsi
, rhs
);
2409 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2413 /* From this point on, the function deals with assignments in between
2414 aggregates when at least one has scalar reductions of some of its
2415 components. There are three possible scenarios: Both the LHS and RHS have
2416 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2418 In the first case, we would like to load the LHS components from RHS
2419 components whenever possible. If that is not possible, we would like to
2420 read it directly from the RHS (after updating it by storing in it its own
2421 components). If there are some necessary unscalarized data in the LHS,
2422 those will be loaded by the original assignment too. If neither of these
2423 cases happen, the original statement can be removed. Most of this is done
2424 by load_assign_lhs_subreplacements.
2426 In the second case, we would like to store all RHS scalarized components
2427 directly into LHS and if they cover the aggregate completely, remove the
2428 statement too. In the third case, we want the LHS components to be loaded
2429 directly from the RHS (DSE will remove the original statement if it
2432 This is a bit complex but manageable when types match and when unions do
2433 not cause confusion in a way that we cannot really load a component of LHS
2434 from the RHS or vice versa (the access representing this level can have
2435 subaccesses that are accessible only through a different union field at a
2436 higher level - different from the one used in the examined expression).
2439 Therefore, I specially handle a fourth case, happening when there is a
2440 specific type cast or it is impossible to locate a scalarized subaccess on
2441 the other side of the expression. If that happens, I simply "refresh" the
2442 RHS by storing in it is scalarized components leave the original statement
2443 there to do the copying and then load the scalar replacements of the LHS.
2444 This is what the first branch does. */
2446 if (contains_view_convert_expr_p (rhs
) || contains_view_convert_expr_p (lhs
)
2447 || (access_has_children_p (racc
)
2448 && !ref_expr_for_all_replacements_p (racc
, lhs
, racc
->offset
))
2449 || (access_has_children_p (lacc
)
2450 && !ref_expr_for_all_replacements_p (lacc
, rhs
, lacc
->offset
)))
2452 if (access_has_children_p (racc
))
2453 generate_subtree_copies (racc
->first_child
, racc
->base
, 0, 0, 0,
2455 if (access_has_children_p (lacc
))
2456 generate_subtree_copies (lacc
->first_child
, lacc
->base
, 0, 0, 0,
2458 sra_stats
.separate_lhs_rhs_handling
++;
2462 if (access_has_children_p (lacc
) && access_has_children_p (racc
))
2464 gimple_stmt_iterator orig_gsi
= *gsi
;
2465 enum unscalarized_data_handling refreshed
;
2467 if (lacc
->grp_read
&& !lacc
->grp_covered
)
2468 refreshed
= handle_unscalarized_data_in_subtree (racc
, lhs
, gsi
);
2470 refreshed
= SRA_UDH_NONE
;
2472 load_assign_lhs_subreplacements (lacc
->first_child
, racc
,
2473 lacc
->offset
, racc
->offset
,
2474 &orig_gsi
, gsi
, &refreshed
, lhs
);
2475 if (refreshed
!= SRA_UDH_RIGHT
)
2477 if (*stmt
== gsi_stmt (*gsi
))
2480 unlink_stmt_vdef (*stmt
);
2481 gsi_remove (&orig_gsi
, true);
2482 sra_stats
.deleted
++;
2483 return SRA_SA_REMOVED
;
2488 if (access_has_children_p (racc
))
2490 if (!racc
->grp_unscalarized_data
)
2492 generate_subtree_copies (racc
->first_child
, lhs
,
2493 racc
->offset
, 0, 0, gsi
,
2495 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2496 unlink_stmt_vdef (*stmt
);
2497 gsi_remove (gsi
, true);
2498 sra_stats
.deleted
++;
2499 return SRA_SA_REMOVED
;
2502 generate_subtree_copies (racc
->first_child
, lhs
,
2503 racc
->offset
, 0, 0, gsi
, false, true);
2505 else if (access_has_children_p (lacc
))
2506 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
2507 0, 0, gsi
, true, true);
2510 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2513 /* Generate statements initializing scalar replacements of parts of function
2517 initialize_parameter_reductions (void)
2519 gimple_stmt_iterator gsi
;
2520 gimple_seq seq
= NULL
;
2523 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2525 parm
= TREE_CHAIN (parm
))
2527 VEC (access_p
, heap
) *access_vec
;
2528 struct access
*access
;
2530 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
2532 access_vec
= get_base_access_vector (parm
);
2538 seq
= gimple_seq_alloc ();
2539 gsi
= gsi_start (seq
);
2542 for (access
= VEC_index (access_p
, access_vec
, 0);
2544 access
= access
->next_grp
)
2545 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true);
2549 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR
), seq
);
2552 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2553 it reveals there are components of some aggregates to be scalarized, it runs
2554 the required transformations. */
2556 perform_intra_sra (void)
2561 if (!find_var_candidates ())
2564 if (!scan_function (build_access_from_expr
, build_accesses_from_assign
, NULL
,
2568 if (!analyze_all_variable_accesses ())
2571 scan_function (sra_modify_expr
, sra_modify_assign
, NULL
, false, NULL
);
2572 initialize_parameter_reductions ();
2574 statistics_counter_event (cfun
, "Scalar replacements created",
2575 sra_stats
.replacements
);
2576 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
2577 statistics_counter_event (cfun
, "Subtree copy stmts",
2578 sra_stats
.subtree_copies
);
2579 statistics_counter_event (cfun
, "Subreplacement stmts",
2580 sra_stats
.subreplacements
);
2581 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
2582 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
2583 sra_stats
.separate_lhs_rhs_handling
);
2585 ret
= TODO_update_ssa
;
2588 sra_deinitialize ();
2592 /* Perform early intraprocedural SRA. */
2594 early_intra_sra (void)
2596 sra_mode
= SRA_MODE_EARLY_INTRA
;
2597 return perform_intra_sra ();
2600 /* Perform "late" intraprocedural SRA. */
2602 late_intra_sra (void)
2604 sra_mode
= SRA_MODE_INTRA
;
2605 return perform_intra_sra ();
2610 gate_intra_sra (void)
2612 return flag_tree_sra
!= 0;
2616 struct gimple_opt_pass pass_sra_early
=
2621 gate_intra_sra
, /* gate */
2622 early_intra_sra
, /* execute */
2625 0, /* static_pass_number */
2626 TV_TREE_SRA
, /* tv_id */
2627 PROP_cfg
| PROP_ssa
, /* properties_required */
2628 0, /* properties_provided */
2629 0, /* properties_destroyed */
2630 0, /* todo_flags_start */
2634 | TODO_verify_ssa
/* todo_flags_finish */
2638 struct gimple_opt_pass pass_sra
=
2643 gate_intra_sra
, /* gate */
2644 late_intra_sra
, /* execute */
2647 0, /* static_pass_number */
2648 TV_TREE_SRA
, /* tv_id */
2649 PROP_cfg
| PROP_ssa
, /* properties_required */
2650 0, /* properties_provided */
2651 0, /* properties_destroyed */
2652 TODO_update_address_taken
, /* todo_flags_start */
2656 | TODO_verify_ssa
/* todo_flags_finish */
2661 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2665 is_unused_scalar_param (tree parm
)
2668 return (is_gimple_reg (parm
)
2669 && (!(name
= gimple_default_def (cfun
, parm
))
2670 || has_zero_uses (name
)));
2673 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2674 examine whether there are any direct or otherwise infeasible ones. If so,
2675 return true, otherwise return false. PARM must be a gimple register with a
2676 non-NULL default definition. */
2679 ptr_parm_has_direct_uses (tree parm
)
2681 imm_use_iterator ui
;
2683 tree name
= gimple_default_def (cfun
, parm
);
2686 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
2688 if (gimple_assign_single_p (stmt
))
2690 tree rhs
= gimple_assign_rhs1 (stmt
);
2693 else if (TREE_CODE (rhs
) == ADDR_EXPR
)
2697 rhs
= TREE_OPERAND (rhs
, 0);
2699 while (handled_component_p (rhs
));
2700 if (INDIRECT_REF_P (rhs
) && TREE_OPERAND (rhs
, 0) == name
)
2704 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
2706 tree t
= gimple_return_retval (stmt
);
2710 else if (is_gimple_call (stmt
))
2713 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
2715 tree arg
= gimple_call_arg (stmt
, i
);
2723 else if (!is_gimple_debug (stmt
))
2727 BREAK_FROM_IMM_USE_STMT (ui
);
2733 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2734 them in candidate_bitmap. Note that these do not necessarily include
2735 parameter which are unused and thus can be removed. Return true iff any
2736 such candidate has been found. */
2739 find_param_candidates (void)
2745 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2747 parm
= TREE_CHAIN (parm
))
2749 tree type
= TREE_TYPE (parm
);
2753 if (TREE_THIS_VOLATILE (parm
)
2754 || TREE_ADDRESSABLE (parm
)
2755 || is_va_list_type (type
))
2758 if (is_unused_scalar_param (parm
))
2764 if (POINTER_TYPE_P (type
))
2766 type
= TREE_TYPE (type
);
2768 if (TREE_CODE (type
) == FUNCTION_TYPE
2769 || TYPE_VOLATILE (type
)
2770 || !is_gimple_reg (parm
)
2771 || is_va_list_type (type
)
2772 || ptr_parm_has_direct_uses (parm
))
2775 else if (!AGGREGATE_TYPE_P (type
))
2778 if (!COMPLETE_TYPE_P (type
)
2779 || !host_integerp (TYPE_SIZE (type
), 1)
2780 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
2781 || (AGGREGATE_TYPE_P (type
)
2782 && type_internals_preclude_sra_p (type
)))
2785 bitmap_set_bit (candidate_bitmap
, DECL_UID (parm
));
2787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2789 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (parm
));
2790 print_generic_expr (dump_file
, parm
, 0);
2791 fprintf (dump_file
, "\n");
2795 func_param_count
= count
;
2799 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2803 mark_maybe_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
2806 struct access
*repr
= (struct access
*) data
;
2808 repr
->grp_maybe_modified
= 1;
2812 /* Analyze what representatives (in linked lists accessible from
2813 REPRESENTATIVES) can be modified by side effects of statements in the
2814 current function. */
2817 analyze_modified_params (VEC (access_p
, heap
) *representatives
)
2821 for (i
= 0; i
< func_param_count
; i
++)
2823 struct access
*repr
;
2825 for (repr
= VEC_index (access_p
, representatives
, i
);
2827 repr
= repr
->next_grp
)
2829 struct access
*access
;
2833 if (no_accesses_p (repr
))
2835 if (!POINTER_TYPE_P (TREE_TYPE (repr
->base
))
2836 || repr
->grp_maybe_modified
)
2839 ao_ref_init (&ar
, repr
->expr
);
2840 visited
= BITMAP_ALLOC (NULL
);
2841 for (access
= repr
; access
; access
= access
->next_sibling
)
2843 /* All accesses are read ones, otherwise grp_maybe_modified would
2844 be trivially set. */
2845 walk_aliased_vdefs (&ar
, gimple_vuse (access
->stmt
),
2846 mark_maybe_modified
, repr
, &visited
);
2847 if (repr
->grp_maybe_modified
)
2850 BITMAP_FREE (visited
);
2855 /* Propagate distances in bb_dereferences in the opposite direction than the
2856 control flow edges, in each step storing the maximum of the current value
2857 and the minimum of all successors. These steps are repeated until the table
2858 stabilizes. Note that BBs which might terminate the functions (according to
2859 final_bbs bitmap) never updated in this way. */
2862 propagate_dereference_distances (void)
2864 VEC (basic_block
, heap
) *queue
;
2867 queue
= VEC_alloc (basic_block
, heap
, last_basic_block_for_function (cfun
));
2868 VEC_quick_push (basic_block
, queue
, ENTRY_BLOCK_PTR
);
2871 VEC_quick_push (basic_block
, queue
, bb
);
2875 while (!VEC_empty (basic_block
, queue
))
2879 bool change
= false;
2882 bb
= VEC_pop (basic_block
, queue
);
2885 if (bitmap_bit_p (final_bbs
, bb
->index
))
2888 for (i
= 0; i
< func_param_count
; i
++)
2890 int idx
= bb
->index
* func_param_count
+ i
;
2892 HOST_WIDE_INT inh
= 0;
2894 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2896 int succ_idx
= e
->dest
->index
* func_param_count
+ i
;
2898 if (e
->src
== EXIT_BLOCK_PTR
)
2904 inh
= bb_dereferences
[succ_idx
];
2906 else if (bb_dereferences
[succ_idx
] < inh
)
2907 inh
= bb_dereferences
[succ_idx
];
2910 if (!first
&& bb_dereferences
[idx
] < inh
)
2912 bb_dereferences
[idx
] = inh
;
2917 if (change
&& !bitmap_bit_p (final_bbs
, bb
->index
))
2918 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2923 e
->src
->aux
= e
->src
;
2924 VEC_quick_push (basic_block
, queue
, e
->src
);
2928 VEC_free (basic_block
, heap
, queue
);
2931 /* Dump a dereferences TABLE with heading STR to file F. */
2934 dump_dereferences_table (FILE *f
, const char *str
, HOST_WIDE_INT
*table
)
2938 fprintf (dump_file
, str
);
2939 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
2941 fprintf (f
, "%4i %i ", bb
->index
, bitmap_bit_p (final_bbs
, bb
->index
));
2942 if (bb
!= EXIT_BLOCK_PTR
)
2945 for (i
= 0; i
< func_param_count
; i
++)
2947 int idx
= bb
->index
* func_param_count
+ i
;
2948 fprintf (f
, " %4" HOST_WIDE_INT_PRINT
"d", table
[idx
]);
2953 fprintf (dump_file
, "\n");
2956 /* Determine what (parts of) parameters passed by reference that are not
2957 assigned to are not certainly dereferenced in this function and thus the
2958 dereferencing cannot be safely moved to the caller without potentially
2959 introducing a segfault. Mark such REPRESENTATIVES as
2960 grp_not_necessarilly_dereferenced.
2962 The dereferenced maximum "distance," i.e. the offset + size of the accessed
2963 part is calculated rather than simple booleans are calculated for each
2964 pointer parameter to handle cases when only a fraction of the whole
2965 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
2968 The maximum dereference distances for each pointer parameter and BB are
2969 already stored in bb_dereference. This routine simply propagates these
2970 values upwards by propagate_dereference_distances and then compares the
2971 distances of individual parameters in the ENTRY BB to the equivalent
2972 distances of each representative of a (fraction of a) parameter. */
2975 analyze_caller_dereference_legality (VEC (access_p
, heap
) *representatives
)
2979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2980 dump_dereferences_table (dump_file
,
2981 "Dereference table before propagation:\n",
2984 propagate_dereference_distances ();
2986 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2987 dump_dereferences_table (dump_file
,
2988 "Dereference table after propagation:\n",
2991 for (i
= 0; i
< func_param_count
; i
++)
2993 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
2994 int idx
= ENTRY_BLOCK_PTR
->index
* func_param_count
+ i
;
2996 if (!repr
|| no_accesses_p (repr
))
3001 if ((repr
->offset
+ repr
->size
) > bb_dereferences
[idx
])
3002 repr
->grp_not_necessarilly_dereferenced
= 1;
3003 repr
= repr
->next_grp
;
3009 /* Return the representative access for the parameter declaration PARM if it is
3010 a scalar passed by reference which is not written to and the pointer value
3011 is not used directly. Thus, if it is legal to dereference it in the caller
3012 and we can rule out modifications through aliases, such parameter should be
3013 turned into one passed by value. Return NULL otherwise. */
3015 static struct access
*
3016 unmodified_by_ref_scalar_representative (tree parm
)
3018 int i
, access_count
;
3019 struct access
*repr
;
3020 VEC (access_p
, heap
) *access_vec
;
3022 access_vec
= get_base_access_vector (parm
);
3023 gcc_assert (access_vec
);
3024 repr
= VEC_index (access_p
, access_vec
, 0);
3027 repr
->group_representative
= repr
;
3029 access_count
= VEC_length (access_p
, access_vec
);
3030 for (i
= 1; i
< access_count
; i
++)
3032 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
3035 access
->group_representative
= repr
;
3036 access
->next_sibling
= repr
->next_sibling
;
3037 repr
->next_sibling
= access
;
3041 repr
->grp_scalar_ptr
= 1;
3045 /* Sort collected accesses for parameter PARM, identify representatives for
3046 each accessed region and link them together. Return NULL if there are
3047 different but overlapping accesses, return the special ptr value meaning
3048 there are no accesses for this parameter if that is the case and return the
3049 first representative otherwise. Set *RO_GRP if there is a group of accesses
3050 with only read (i.e. no write) accesses. */
3052 static struct access
*
3053 splice_param_accesses (tree parm
, bool *ro_grp
)
3055 int i
, j
, access_count
, group_count
;
3056 int agg_size
, total_size
= 0;
3057 struct access
*access
, *res
, **prev_acc_ptr
= &res
;
3058 VEC (access_p
, heap
) *access_vec
;
3060 access_vec
= get_base_access_vector (parm
);
3062 return &no_accesses_representant
;
3063 access_count
= VEC_length (access_p
, access_vec
);
3065 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
3066 compare_access_positions
);
3071 while (i
< access_count
)
3074 access
= VEC_index (access_p
, access_vec
, i
);
3075 modification
= access
->write
;
3077 /* Access is about to become group representative unless we find some
3078 nasty overlap which would preclude us from breaking this parameter
3082 while (j
< access_count
)
3084 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
3085 if (ac2
->offset
!= access
->offset
)
3087 /* All or nothing law for parameters. */
3088 if (access
->offset
+ access
->size
> ac2
->offset
)
3093 else if (ac2
->size
!= access
->size
)
3096 modification
|= ac2
->write
;
3097 ac2
->group_representative
= access
;
3098 ac2
->next_sibling
= access
->next_sibling
;
3099 access
->next_sibling
= ac2
;
3104 access
->grp_maybe_modified
= modification
;
3107 *prev_acc_ptr
= access
;
3108 prev_acc_ptr
= &access
->next_grp
;
3109 total_size
+= access
->size
;
3113 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3114 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3116 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3117 if (total_size
>= agg_size
)
3120 gcc_assert (group_count
> 0);
3124 /* Decide whether parameters with representative accesses given by REPR should
3125 be reduced into components. */
3128 decide_one_param_reduction (struct access
*repr
)
3130 int total_size
, cur_parm_size
, agg_size
, new_param_count
, parm_size_limit
;
3135 cur_parm_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3136 gcc_assert (cur_parm_size
> 0);
3138 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3141 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3146 agg_size
= cur_parm_size
;
3152 fprintf (dump_file
, "Evaluating PARAM group sizes for ");
3153 print_generic_expr (dump_file
, parm
, 0);
3154 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (parm
));
3155 for (acc
= repr
; acc
; acc
= acc
->next_grp
)
3156 dump_access (dump_file
, acc
, true);
3160 new_param_count
= 0;
3162 for (; repr
; repr
= repr
->next_grp
)
3164 gcc_assert (parm
== repr
->base
);
3167 if (!by_ref
|| (!repr
->grp_maybe_modified
3168 && !repr
->grp_not_necessarilly_dereferenced
))
3169 total_size
+= repr
->size
;
3171 total_size
+= cur_parm_size
;
3174 gcc_assert (new_param_count
> 0);
3176 if (optimize_function_for_size_p (cfun
))
3177 parm_size_limit
= cur_parm_size
;
3179 parm_size_limit
= (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR
)
3182 if (total_size
< agg_size
3183 && total_size
<= parm_size_limit
)
3186 fprintf (dump_file
, " ....will be split into %i components\n",
3188 return new_param_count
;
3194 /* The order of the following enums is important, we need to do extra work for
3195 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3196 enum ipa_splicing_result
{ NO_GOOD_ACCESS
, UNUSED_PARAMS
, BY_VAL_ACCESSES
,
3197 MODIF_BY_REF_ACCESSES
, UNMODIF_BY_REF_ACCESSES
};
3199 /* Identify representatives of all accesses to all candidate parameters for
3200 IPA-SRA. Return result based on what representatives have been found. */
3202 static enum ipa_splicing_result
3203 splice_all_param_accesses (VEC (access_p
, heap
) **representatives
)
3205 enum ipa_splicing_result result
= NO_GOOD_ACCESS
;
3207 struct access
*repr
;
3209 *representatives
= VEC_alloc (access_p
, heap
, func_param_count
);
3211 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3213 parm
= TREE_CHAIN (parm
))
3215 if (is_unused_scalar_param (parm
))
3217 VEC_quick_push (access_p
, *representatives
,
3218 &no_accesses_representant
);
3219 if (result
== NO_GOOD_ACCESS
)
3220 result
= UNUSED_PARAMS
;
3222 else if (POINTER_TYPE_P (TREE_TYPE (parm
))
3223 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm
)))
3224 && bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3226 repr
= unmodified_by_ref_scalar_representative (parm
);
3227 VEC_quick_push (access_p
, *representatives
, repr
);
3229 result
= UNMODIF_BY_REF_ACCESSES
;
3231 else if (bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3233 bool ro_grp
= false;
3234 repr
= splice_param_accesses (parm
, &ro_grp
);
3235 VEC_quick_push (access_p
, *representatives
, repr
);
3237 if (repr
&& !no_accesses_p (repr
))
3239 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3242 result
= UNMODIF_BY_REF_ACCESSES
;
3243 else if (result
< MODIF_BY_REF_ACCESSES
)
3244 result
= MODIF_BY_REF_ACCESSES
;
3246 else if (result
< BY_VAL_ACCESSES
)
3247 result
= BY_VAL_ACCESSES
;
3249 else if (no_accesses_p (repr
) && (result
== NO_GOOD_ACCESS
))
3250 result
= UNUSED_PARAMS
;
3253 VEC_quick_push (access_p
, *representatives
, NULL
);
3256 if (result
== NO_GOOD_ACCESS
)
3258 VEC_free (access_p
, heap
, *representatives
);
3259 *representatives
= NULL
;
3260 return NO_GOOD_ACCESS
;
3266 /* Return the index of BASE in PARMS. Abort if it is not found. */
3269 get_param_index (tree base
, VEC(tree
, heap
) *parms
)
3273 len
= VEC_length (tree
, parms
);
3274 for (i
= 0; i
< len
; i
++)
3275 if (VEC_index (tree
, parms
, i
) == base
)
3280 /* Convert the decisions made at the representative level into compact
3281 parameter adjustments. REPRESENTATIVES are pointers to first
3282 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3283 final number of adjustments. */
3285 static ipa_parm_adjustment_vec
3286 turn_representatives_into_adjustments (VEC (access_p
, heap
) *representatives
,
3287 int adjustments_count
)
3289 VEC (tree
, heap
) *parms
;
3290 ipa_parm_adjustment_vec adjustments
;
3294 gcc_assert (adjustments_count
> 0);
3295 parms
= ipa_get_vector_of_formal_parms (current_function_decl
);
3296 adjustments
= VEC_alloc (ipa_parm_adjustment_t
, heap
, adjustments_count
);
3297 parm
= DECL_ARGUMENTS (current_function_decl
);
3298 for (i
= 0; i
< func_param_count
; i
++, parm
= TREE_CHAIN (parm
))
3300 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3302 if (!repr
|| no_accesses_p (repr
))
3304 struct ipa_parm_adjustment
*adj
;
3306 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3307 memset (adj
, 0, sizeof (*adj
));
3308 adj
->base_index
= get_param_index (parm
, parms
);
3311 adj
->copy_param
= 1;
3313 adj
->remove_param
= 1;
3317 struct ipa_parm_adjustment
*adj
;
3318 int index
= get_param_index (parm
, parms
);
3320 for (; repr
; repr
= repr
->next_grp
)
3322 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3323 memset (adj
, 0, sizeof (*adj
));
3324 gcc_assert (repr
->base
== parm
);
3325 adj
->base_index
= index
;
3326 adj
->base
= repr
->base
;
3327 adj
->type
= repr
->type
;
3328 adj
->offset
= repr
->offset
;
3329 adj
->by_ref
= (POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3330 && (repr
->grp_maybe_modified
3331 || repr
->grp_not_necessarilly_dereferenced
));
3336 VEC_free (tree
, heap
, parms
);
3340 /* Analyze the collected accesses and produce a plan what to do with the
3341 parameters in the form of adjustments, NULL meaning nothing. */
3343 static ipa_parm_adjustment_vec
3344 analyze_all_param_acesses (void)
3346 enum ipa_splicing_result repr_state
;
3347 bool proceed
= false;
3348 int i
, adjustments_count
= 0;
3349 VEC (access_p
, heap
) *representatives
;
3350 ipa_parm_adjustment_vec adjustments
;
3352 repr_state
= splice_all_param_accesses (&representatives
);
3353 if (repr_state
== NO_GOOD_ACCESS
)
3356 /* If there are any parameters passed by reference which are not modified
3357 directly, we need to check whether they can be modified indirectly. */
3358 if (repr_state
== UNMODIF_BY_REF_ACCESSES
)
3360 analyze_caller_dereference_legality (representatives
);
3361 analyze_modified_params (representatives
);
3364 for (i
= 0; i
< func_param_count
; i
++)
3366 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3368 if (repr
&& !no_accesses_p (repr
))
3370 if (repr
->grp_scalar_ptr
)
3372 adjustments_count
++;
3373 if (repr
->grp_not_necessarilly_dereferenced
3374 || repr
->grp_maybe_modified
)
3375 VEC_replace (access_p
, representatives
, i
, NULL
);
3379 sra_stats
.scalar_by_ref_to_by_val
++;
3384 int new_components
= decide_one_param_reduction (repr
);
3386 if (new_components
== 0)
3388 VEC_replace (access_p
, representatives
, i
, NULL
);
3389 adjustments_count
++;
3393 adjustments_count
+= new_components
;
3394 sra_stats
.aggregate_params_reduced
++;
3395 sra_stats
.param_reductions_created
+= new_components
;
3402 if (no_accesses_p (repr
))
3405 sra_stats
.deleted_unused_parameters
++;
3407 adjustments_count
++;
3411 if (!proceed
&& dump_file
)
3412 fprintf (dump_file
, "NOT proceeding to change params.\n");
3415 adjustments
= turn_representatives_into_adjustments (representatives
,
3420 VEC_free (access_p
, heap
, representatives
);
3424 /* If a parameter replacement identified by ADJ does not yet exist in the form
3425 of declaration, create it and record it, otherwise return the previously
3429 get_replaced_param_substitute (struct ipa_parm_adjustment
*adj
)
3432 if (!adj
->new_ssa_base
)
3434 char *pretty_name
= make_fancy_name (adj
->base
);
3436 repl
= make_rename_temp (TREE_TYPE (adj
->base
), "ISR");
3437 DECL_NAME (repl
) = get_identifier (pretty_name
);
3438 obstack_free (&name_obstack
, pretty_name
);
3441 add_referenced_var (repl
);
3442 adj
->new_ssa_base
= repl
;
3445 repl
= adj
->new_ssa_base
;
3449 /* Find the first adjustment for a particular parameter BASE in a vector of
3450 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3453 static struct ipa_parm_adjustment
*
3454 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments
, tree base
)
3458 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3459 for (i
= 0; i
< len
; i
++)
3461 struct ipa_parm_adjustment
*adj
;
3463 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3464 if (!adj
->copy_param
&& adj
->base
== base
)
3471 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3472 parameter which is to be removed because its value is not used, replace the
3473 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3474 uses too. DATA is a pointer to an adjustments vector. */
3477 replace_removed_params_ssa_names (gimple stmt
, void *data
)
3479 VEC (ipa_parm_adjustment_t
, heap
) *adjustments
;
3480 struct ipa_parm_adjustment
*adj
;
3481 tree lhs
, decl
, repl
, name
;
3483 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3484 if (gimple_code (stmt
) == GIMPLE_PHI
)
3485 lhs
= gimple_phi_result (stmt
);
3486 else if (is_gimple_assign (stmt
))
3487 lhs
= gimple_assign_lhs (stmt
);
3488 else if (is_gimple_call (stmt
))
3489 lhs
= gimple_call_lhs (stmt
);
3493 if (TREE_CODE (lhs
) != SSA_NAME
)
3495 decl
= SSA_NAME_VAR (lhs
);
3496 if (TREE_CODE (decl
) != PARM_DECL
)
3499 adj
= get_adjustment_for_base (adjustments
, decl
);
3503 repl
= get_replaced_param_substitute (adj
);
3504 name
= make_ssa_name (repl
, stmt
);
3508 fprintf (dump_file
, "replacing an SSA name of a removed param ");
3509 print_generic_expr (dump_file
, lhs
, 0);
3510 fprintf (dump_file
, " with ");
3511 print_generic_expr (dump_file
, name
, 0);
3512 fprintf (dump_file
, "\n");
3515 if (is_gimple_assign (stmt
))
3516 gimple_assign_set_lhs (stmt
, name
);
3517 else if (is_gimple_call (stmt
))
3518 gimple_call_set_lhs (stmt
, name
);
3520 gimple_phi_set_result (stmt
, name
);
3522 replace_uses_by (lhs
, name
);
3526 /* Callback for scan_function. If the expression *EXPR should be replaced by a
3527 reduction of a parameter, do so. DATA is a pointer to a vector of
3531 sra_ipa_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
3532 bool write ATTRIBUTE_UNUSED
, void *data
)
3534 ipa_parm_adjustment_vec adjustments
;
3536 struct ipa_parm_adjustment
*adj
, *cand
= NULL
;
3537 HOST_WIDE_INT offset
, size
, max_size
;
3540 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3541 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3543 if (TREE_CODE (*expr
) == BIT_FIELD_REF
3544 || TREE_CODE (*expr
) == IMAGPART_EXPR
3545 || TREE_CODE (*expr
) == REALPART_EXPR
)
3546 expr
= &TREE_OPERAND (*expr
, 0);
3547 while (TREE_CODE (*expr
) == NOP_EXPR
3548 || TREE_CODE (*expr
) == VIEW_CONVERT_EXPR
)
3549 expr
= &TREE_OPERAND (*expr
, 0);
3551 base
= get_ref_base_and_extent (*expr
, &offset
, &size
, &max_size
);
3552 if (!base
|| size
== -1 || max_size
== -1)
3555 if (INDIRECT_REF_P (base
))
3556 base
= TREE_OPERAND (base
, 0);
3558 base
= get_ssa_base_param (base
);
3559 if (!base
|| TREE_CODE (base
) != PARM_DECL
)
3562 for (i
= 0; i
< len
; i
++)
3564 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3566 if (adj
->base
== base
&&
3567 (adj
->offset
== offset
|| adj
->remove_param
))
3573 if (!cand
|| cand
->copy_param
|| cand
->remove_param
)
3579 src
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (cand
->reduction
)),
3581 folded
= gimple_fold_indirect_ref (src
);
3586 src
= cand
->reduction
;
3588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3590 fprintf (dump_file
, "About to replace expr ");
3591 print_generic_expr (dump_file
, *expr
, 0);
3592 fprintf (dump_file
, " with ");
3593 print_generic_expr (dump_file
, src
, 0);
3594 fprintf (dump_file
, "\n");
3597 if (!useless_type_conversion_p (TREE_TYPE (*expr
), cand
->type
))
3599 tree vce
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (*expr
), src
);
3607 /* Callback for scan_function to process assign statements. Performs
3608 essentially the same function like sra_ipa_modify_expr. */
3610 static enum scan_assign_result
3611 sra_ipa_modify_assign (gimple
*stmt_ptr
,
3612 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
, void *data
)
3614 gimple stmt
= *stmt_ptr
;
3617 if (!gimple_assign_single_p (stmt
))
3620 any
|= sra_ipa_modify_expr (gimple_assign_rhs1_ptr (stmt
), gsi
, false,
3622 any
|= sra_ipa_modify_expr (gimple_assign_lhs_ptr (stmt
), gsi
, true, data
);
3624 return any
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
3627 /* Call gimple_debug_bind_reset_value on all debug statements describing
3628 gimple register parameters that are being removed or replaced. */
3631 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments
)
3635 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3636 for (i
= 0; i
< len
; i
++)
3638 struct ipa_parm_adjustment
*adj
;
3639 imm_use_iterator ui
;
3643 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3644 if (adj
->copy_param
|| !is_gimple_reg (adj
->base
))
3646 name
= gimple_default_def (cfun
, adj
->base
);
3649 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
3651 /* All other users must have been removed by scan_function. */
3652 gcc_assert (is_gimple_debug (stmt
));
3653 gimple_debug_bind_reset_value (stmt
);
3659 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3662 convert_callers (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3664 tree old_cur_fndecl
= current_function_decl
;
3665 struct cgraph_edge
*cs
;
3666 basic_block this_block
;
3667 bitmap recomputed_callers
= BITMAP_ALLOC (NULL
);
3669 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3671 current_function_decl
= cs
->caller
->decl
;
3672 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
3675 fprintf (dump_file
, "Adjusting call (%i -> %i) %s -> %s\n",
3676 cs
->caller
->uid
, cs
->callee
->uid
,
3677 cgraph_node_name (cs
->caller
),
3678 cgraph_node_name (cs
->callee
));
3680 ipa_modify_call_arguments (cs
, cs
->call_stmt
, adjustments
);
3685 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3686 if (!bitmap_bit_p (recomputed_callers
, cs
->caller
->uid
))
3688 compute_inline_parameters (cs
->caller
);
3689 bitmap_set_bit (recomputed_callers
, cs
->caller
->uid
);
3691 BITMAP_FREE (recomputed_callers
);
3693 current_function_decl
= old_cur_fndecl
;
3694 FOR_EACH_BB (this_block
)
3696 gimple_stmt_iterator gsi
;
3698 for (gsi
= gsi_start_bb (this_block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3700 gimple stmt
= gsi_stmt (gsi
);
3701 if (gimple_code (stmt
) == GIMPLE_CALL
3702 && gimple_call_fndecl (stmt
) == node
->decl
)
3705 fprintf (dump_file
, "Adjusting recursive call");
3706 ipa_modify_call_arguments (NULL
, stmt
, adjustments
);
3714 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3715 as given in ADJUSTMENTS. */
3718 modify_function (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3720 ipa_modify_formal_parameters (current_function_decl
, adjustments
, "ISRA");
3721 scan_function (sra_ipa_modify_expr
, sra_ipa_modify_assign
,
3722 replace_removed_params_ssa_names
, false, adjustments
);
3723 sra_ipa_reset_debug_stmts (adjustments
);
3724 convert_callers (node
, adjustments
);
3725 cgraph_make_node_local (node
);
3729 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3730 attributes, return true otherwise. NODE is the cgraph node of the current
3734 ipa_sra_preliminary_function_checks (struct cgraph_node
*node
)
3736 if (!cgraph_node_can_be_local_p (node
))
3739 fprintf (dump_file
, "Function not local to this compilation unit.\n");
3743 if (DECL_VIRTUAL_P (current_function_decl
))
3746 fprintf (dump_file
, "Function is a virtual method.\n");
3750 if ((DECL_COMDAT (node
->decl
) || DECL_EXTERNAL (node
->decl
))
3751 && node
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
3754 fprintf (dump_file
, "Function too big to be made truly local.\n");
3762 "Function has no callers in this compilation unit.\n");
3769 fprintf (dump_file
, "Function uses stdarg. \n");
3776 /* Perform early interprocedural SRA. */
3779 ipa_early_sra (void)
3781 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
3782 ipa_parm_adjustment_vec adjustments
;
3785 if (!ipa_sra_preliminary_function_checks (node
))
3789 sra_mode
= SRA_MODE_EARLY_IPA
;
3791 if (!find_param_candidates ())
3794 fprintf (dump_file
, "Function has no IPA-SRA candidates.\n");
3798 bb_dereferences
= XCNEWVEC (HOST_WIDE_INT
,
3800 * last_basic_block_for_function (cfun
));
3801 final_bbs
= BITMAP_ALLOC (NULL
);
3803 scan_function (build_access_from_expr
, build_accesses_from_assign
,
3805 if (encountered_apply_args
)
3808 fprintf (dump_file
, "Function calls __builtin_apply_args().\n");
3812 adjustments
= analyze_all_param_acesses ();
3816 ipa_dump_param_adjustments (dump_file
, adjustments
, current_function_decl
);
3818 modify_function (node
, adjustments
);
3819 VEC_free (ipa_parm_adjustment_t
, heap
, adjustments
);
3820 ret
= TODO_update_ssa
;
3822 statistics_counter_event (cfun
, "Unused parameters deleted",
3823 sra_stats
.deleted_unused_parameters
);
3824 statistics_counter_event (cfun
, "Scalar parameters converted to by-value",
3825 sra_stats
.scalar_by_ref_to_by_val
);
3826 statistics_counter_event (cfun
, "Aggregate parameters broken up",
3827 sra_stats
.aggregate_params_reduced
);
3828 statistics_counter_event (cfun
, "Aggregate parameter components created",
3829 sra_stats
.param_reductions_created
);
3832 BITMAP_FREE (final_bbs
);
3833 free (bb_dereferences
);
3835 sra_deinitialize ();
3839 /* Return if early ipa sra shall be performed. */
3841 ipa_early_sra_gate (void)
3843 return flag_ipa_sra
;
3846 struct gimple_opt_pass pass_early_ipa_sra
=
3850 "eipa_sra", /* name */
3851 ipa_early_sra_gate
, /* gate */
3852 ipa_early_sra
, /* execute */
3855 0, /* static_pass_number */
3856 TV_IPA_SRA
, /* tv_id */
3857 0, /* properties_required */
3858 0, /* properties_provided */
3859 0, /* properties_destroyed */
3860 0, /* todo_flags_start */
3861 TODO_dump_func
| TODO_dump_cgraph
/* todo_flags_finish */