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
;
128 /* Expression. It is context dependent so do not use it to create new
129 expressions to access the original aggregate. See PR 42154 for a
135 /* The statement this access belongs to. */
138 /* Next group representative for this aggregate. */
139 struct access
*next_grp
;
141 /* Pointer to the group representative. Pointer to itself if the struct is
142 the representative. */
143 struct access
*group_representative
;
145 /* If this access has any children (in terms of the definition above), this
146 points to the first one. */
147 struct access
*first_child
;
149 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
150 described above. In IPA-SRA this is a pointer to the next access
151 belonging to the same group (having the same representative). */
152 struct access
*next_sibling
;
154 /* Pointers to the first and last element in the linked list of assign
156 struct assign_link
*first_link
, *last_link
;
158 /* Pointer to the next access in the work queue. */
159 struct access
*next_queued
;
161 /* Replacement variable for this access "region." Never to be accessed
162 directly, always only by the means of get_access_replacement() and only
163 when grp_to_be_replaced flag is set. */
164 tree replacement_decl
;
166 /* Is this particular access write access? */
169 /* Is this access currently in the work queue? */
170 unsigned grp_queued
: 1;
172 /* Does this group contain a write access? This flag is propagated down the
174 unsigned grp_write
: 1;
176 /* Does this group contain a read access? This flag is propagated down the
178 unsigned grp_read
: 1;
180 /* Other passes of the analysis use this bit to make function
181 analyze_access_subtree create scalar replacements for this group if
183 unsigned grp_hint
: 1;
185 /* Is the subtree rooted in this access fully covered by scalar
187 unsigned grp_covered
: 1;
189 /* If set to true, this access and all below it in an access tree must not be
191 unsigned grp_unscalarizable_region
: 1;
193 /* Whether data have been written to parts of the aggregate covered by this
194 access which is not to be scalarized. This flag is propagated up in the
196 unsigned grp_unscalarized_data
: 1;
198 /* Does this access and/or group contain a write access through a
200 unsigned grp_partial_lhs
: 1;
202 /* Does this group contain accesses to different types? (I.e. through a union
203 or a similar mechanism). */
204 unsigned grp_different_types
: 1;
206 /* Set when a scalar replacement should be created for this variable. We do
207 the decision and creation at different places because create_tmp_var
208 cannot be called from within FOR_EACH_REFERENCED_VAR. */
209 unsigned grp_to_be_replaced
: 1;
211 /* Is it possible that the group refers to data which might be (directly or
212 otherwise) modified? */
213 unsigned grp_maybe_modified
: 1;
215 /* Set when this is a representative of a pointer to scalar (i.e. by
216 reference) parameter which we consider for turning into a plain scalar
217 (i.e. a by value parameter). */
218 unsigned grp_scalar_ptr
: 1;
220 /* Set when we discover that this pointer is not safe to dereference in the
222 unsigned grp_not_necessarilly_dereferenced
: 1;
225 typedef struct access
*access_p
;
227 DEF_VEC_P (access_p
);
228 DEF_VEC_ALLOC_P (access_p
, heap
);
230 /* Alloc pool for allocating access structures. */
231 static alloc_pool access_pool
;
233 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
234 are used to propagate subaccesses from rhs to lhs as long as they don't
235 conflict with what is already there. */
238 struct access
*lacc
, *racc
;
239 struct assign_link
*next
;
242 /* Alloc pool for allocating assign link structures. */
243 static alloc_pool link_pool
;
245 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
246 static struct pointer_map_t
*base_access_vec
;
248 /* Bitmap of candidates. */
249 static bitmap candidate_bitmap
;
251 /* Obstack for creation of fancy names. */
252 static struct obstack name_obstack
;
254 /* Head of a linked list of accesses that need to have its subaccesses
255 propagated to their assignment counterparts. */
256 static struct access
*work_queue_head
;
258 /* Number of parameters of the analyzed function when doing early ipa SRA. */
259 static int func_param_count
;
261 /* scan_function sets the following to true if it encounters a call to
262 __builtin_apply_args. */
263 static bool encountered_apply_args
;
265 /* This is a table in which for each basic block and parameter there is a
266 distance (offset + size) in that parameter which is dereferenced and
267 accessed in that BB. */
268 static HOST_WIDE_INT
*bb_dereferences
;
269 /* Bitmap of BBs that can cause the function to "stop" progressing by
270 returning, throwing externally, looping infinitely or calling a function
271 which might abort etc.. */
272 static bitmap final_bbs
;
274 /* Representative of no accesses at all. */
275 static struct access no_accesses_representant
;
277 /* Predicate to test the special value. */
280 no_accesses_p (struct access
*access
)
282 return access
== &no_accesses_representant
;
285 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
286 representative fields are dumped, otherwise those which only describe the
287 individual access are. */
291 /* Number of processed aggregates is readily available in
292 analyze_all_variable_accesses and so is not stored here. */
294 /* Number of created scalar replacements. */
297 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
301 /* Number of statements created by generate_subtree_copies. */
304 /* Number of statements created by load_assign_lhs_subreplacements. */
307 /* Number of times sra_modify_assign has deleted a statement. */
310 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
311 RHS reparately due to type conversions or nonexistent matching
313 int separate_lhs_rhs_handling
;
315 /* Number of parameters that were removed because they were unused. */
316 int deleted_unused_parameters
;
318 /* Number of scalars passed as parameters by reference that have been
319 converted to be passed by value. */
320 int scalar_by_ref_to_by_val
;
322 /* Number of aggregate parameters that were replaced by one or more of their
324 int aggregate_params_reduced
;
326 /* Numbber of components created when splitting aggregate parameters. */
327 int param_reductions_created
;
331 dump_access (FILE *f
, struct access
*access
, bool grp
)
333 fprintf (f
, "access { ");
334 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
335 print_generic_expr (f
, access
->base
, 0);
336 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
337 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
338 fprintf (f
, ", expr = ");
339 print_generic_expr (f
, access
->expr
, 0);
340 fprintf (f
, ", type = ");
341 print_generic_expr (f
, access
->type
, 0);
343 fprintf (f
, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
344 "grp_covered = %d, grp_unscalarizable_region = %d, "
345 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
346 "grp_different_types = %d, grp_to_be_replaced = %d, "
347 "grp_maybe_modified = %d, "
348 "grp_not_necessarilly_dereferenced = %d\n",
349 access
->grp_write
, access
->grp_read
, access
->grp_hint
,
350 access
->grp_covered
, access
->grp_unscalarizable_region
,
351 access
->grp_unscalarized_data
, access
->grp_partial_lhs
,
352 access
->grp_different_types
, access
->grp_to_be_replaced
,
353 access
->grp_maybe_modified
,
354 access
->grp_not_necessarilly_dereferenced
);
356 fprintf (f
, ", write = %d, grp_partial_lhs = %d\n", access
->write
,
357 access
->grp_partial_lhs
);
360 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
363 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
369 for (i
= 0; i
< level
; i
++)
370 fputs ("* ", dump_file
);
372 dump_access (f
, access
, true);
374 if (access
->first_child
)
375 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
377 access
= access
->next_sibling
;
382 /* Dump all access trees for a variable, given the pointer to the first root in
386 dump_access_tree (FILE *f
, struct access
*access
)
388 for (; access
; access
= access
->next_grp
)
389 dump_access_tree_1 (f
, access
, 0);
392 /* Return true iff ACC is non-NULL and has subaccesses. */
395 access_has_children_p (struct access
*acc
)
397 return acc
&& acc
->first_child
;
400 /* Return a vector of pointers to accesses for the variable given in BASE or
401 NULL if there is none. */
403 static VEC (access_p
, heap
) *
404 get_base_access_vector (tree base
)
408 slot
= pointer_map_contains (base_access_vec
, base
);
412 return *(VEC (access_p
, heap
) **) slot
;
415 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
416 in ACCESS. Return NULL if it cannot be found. */
418 static struct access
*
419 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
422 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
424 struct access
*child
= access
->first_child
;
426 while (child
&& (child
->offset
+ child
->size
<= offset
))
427 child
= child
->next_sibling
;
434 /* Return the first group representative for DECL or NULL if none exists. */
436 static struct access
*
437 get_first_repr_for_decl (tree base
)
439 VEC (access_p
, heap
) *access_vec
;
441 access_vec
= get_base_access_vector (base
);
445 return VEC_index (access_p
, access_vec
, 0);
448 /* Find an access representative for the variable BASE and given OFFSET and
449 SIZE. Requires that access trees have already been built. Return NULL if
450 it cannot be found. */
452 static struct access
*
453 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
456 struct access
*access
;
458 access
= get_first_repr_for_decl (base
);
459 while (access
&& (access
->offset
+ access
->size
<= offset
))
460 access
= access
->next_grp
;
464 return find_access_in_subtree (access
, offset
, size
);
467 /* Add LINK to the linked list of assign links of RACC. */
469 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
471 gcc_assert (link
->racc
== racc
);
473 if (!racc
->first_link
)
475 gcc_assert (!racc
->last_link
);
476 racc
->first_link
= link
;
479 racc
->last_link
->next
= link
;
481 racc
->last_link
= link
;
485 /* Move all link structures in their linked list in OLD_RACC to the linked list
488 relink_to_new_repr (struct access
*new_racc
, struct access
*old_racc
)
490 if (!old_racc
->first_link
)
492 gcc_assert (!old_racc
->last_link
);
496 if (new_racc
->first_link
)
498 gcc_assert (!new_racc
->last_link
->next
);
499 gcc_assert (!old_racc
->last_link
|| !old_racc
->last_link
->next
);
501 new_racc
->last_link
->next
= old_racc
->first_link
;
502 new_racc
->last_link
= old_racc
->last_link
;
506 gcc_assert (!new_racc
->last_link
);
508 new_racc
->first_link
= old_racc
->first_link
;
509 new_racc
->last_link
= old_racc
->last_link
;
511 old_racc
->first_link
= old_racc
->last_link
= NULL
;
514 /* Add ACCESS to the work queue (which is actually a stack). */
517 add_access_to_work_queue (struct access
*access
)
519 if (!access
->grp_queued
)
521 gcc_assert (!access
->next_queued
);
522 access
->next_queued
= work_queue_head
;
523 access
->grp_queued
= 1;
524 work_queue_head
= access
;
528 /* Pop an access from the work queue, and return it, assuming there is one. */
530 static struct access
*
531 pop_access_from_work_queue (void)
533 struct access
*access
= work_queue_head
;
535 work_queue_head
= access
->next_queued
;
536 access
->next_queued
= NULL
;
537 access
->grp_queued
= 0;
542 /* Allocate necessary structures. */
545 sra_initialize (void)
547 candidate_bitmap
= BITMAP_ALLOC (NULL
);
548 gcc_obstack_init (&name_obstack
);
549 access_pool
= create_alloc_pool ("SRA accesses", sizeof (struct access
), 16);
550 link_pool
= create_alloc_pool ("SRA links", sizeof (struct assign_link
), 16);
551 base_access_vec
= pointer_map_create ();
552 memset (&sra_stats
, 0, sizeof (sra_stats
));
553 encountered_apply_args
= false;
556 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
559 delete_base_accesses (const void *key ATTRIBUTE_UNUSED
, void **value
,
560 void *data ATTRIBUTE_UNUSED
)
562 VEC (access_p
, heap
) *access_vec
;
563 access_vec
= (VEC (access_p
, heap
) *) *value
;
564 VEC_free (access_p
, heap
, access_vec
);
569 /* Deallocate all general structures. */
572 sra_deinitialize (void)
574 BITMAP_FREE (candidate_bitmap
);
575 free_alloc_pool (access_pool
);
576 free_alloc_pool (link_pool
);
577 obstack_free (&name_obstack
, NULL
);
579 pointer_map_traverse (base_access_vec
, delete_base_accesses
, NULL
);
580 pointer_map_destroy (base_access_vec
);
583 /* Remove DECL from candidates for SRA and write REASON to the dump file if
586 disqualify_candidate (tree decl
, const char *reason
)
588 bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
));
590 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
592 fprintf (dump_file
, "! Disqualifying ");
593 print_generic_expr (dump_file
, decl
, 0);
594 fprintf (dump_file
, " - %s\n", reason
);
598 /* Return true iff the type contains a field or an element which does not allow
602 type_internals_preclude_sra_p (tree type
)
607 switch (TREE_CODE (type
))
611 case QUAL_UNION_TYPE
:
612 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
613 if (TREE_CODE (fld
) == FIELD_DECL
)
615 tree ft
= TREE_TYPE (fld
);
617 if (TREE_THIS_VOLATILE (fld
)
618 || !DECL_FIELD_OFFSET (fld
) || !DECL_SIZE (fld
)
619 || !host_integerp (DECL_FIELD_OFFSET (fld
), 1)
620 || !host_integerp (DECL_SIZE (fld
), 1))
623 if (AGGREGATE_TYPE_P (ft
)
624 && type_internals_preclude_sra_p (ft
))
631 et
= TREE_TYPE (type
);
633 if (AGGREGATE_TYPE_P (et
))
634 return type_internals_preclude_sra_p (et
);
643 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
644 base variable if it is. Return T if it is not an SSA_NAME. */
647 get_ssa_base_param (tree t
)
649 if (TREE_CODE (t
) == SSA_NAME
)
651 if (SSA_NAME_IS_DEFAULT_DEF (t
))
652 return SSA_NAME_VAR (t
);
659 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
660 belongs to, unless the BB has already been marked as a potentially
664 mark_parm_dereference (tree base
, HOST_WIDE_INT dist
, gimple stmt
)
666 basic_block bb
= gimple_bb (stmt
);
667 int idx
, parm_index
= 0;
670 if (bitmap_bit_p (final_bbs
, bb
->index
))
673 for (parm
= DECL_ARGUMENTS (current_function_decl
);
674 parm
&& parm
!= base
;
675 parm
= TREE_CHAIN (parm
))
678 gcc_assert (parm_index
< func_param_count
);
680 idx
= bb
->index
* func_param_count
+ parm_index
;
681 if (bb_dereferences
[idx
] < dist
)
682 bb_dereferences
[idx
] = dist
;
685 /* Create and insert access for EXPR. Return created access, or NULL if it is
688 static struct access
*
689 create_access (tree expr
, gimple stmt
, bool write
)
691 struct access
*access
;
693 VEC (access_p
,heap
) *vec
;
694 HOST_WIDE_INT offset
, size
, max_size
;
696 bool ptr
, unscalarizable_region
= false;
698 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
700 if (sra_mode
== SRA_MODE_EARLY_IPA
&& INDIRECT_REF_P (base
))
702 base
= get_ssa_base_param (TREE_OPERAND (base
, 0));
710 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
713 if (sra_mode
== SRA_MODE_EARLY_IPA
)
715 if (size
< 0 || size
!= max_size
)
717 disqualify_candidate (base
, "Encountered a variable sized access.");
720 if ((offset
% BITS_PER_UNIT
) != 0 || (size
% BITS_PER_UNIT
) != 0)
722 disqualify_candidate (base
,
723 "Encountered an acces not aligned to a byte.");
728 mark_parm_dereference (base
, offset
+ size
, stmt
);
732 if (size
!= max_size
)
735 unscalarizable_region
= true;
739 disqualify_candidate (base
, "Encountered an unconstrained access.");
744 access
= (struct access
*) pool_alloc (access_pool
);
745 memset (access
, 0, sizeof (struct access
));
748 access
->offset
= offset
;
751 access
->type
= TREE_TYPE (expr
);
752 access
->write
= write
;
753 access
->grp_unscalarizable_region
= unscalarizable_region
;
756 slot
= pointer_map_contains (base_access_vec
, base
);
758 vec
= (VEC (access_p
, heap
) *) *slot
;
760 vec
= VEC_alloc (access_p
, heap
, 32);
762 VEC_safe_push (access_p
, heap
, vec
, access
);
764 *((struct VEC (access_p
,heap
) **)
765 pointer_map_insert (base_access_vec
, base
)) = vec
;
771 /* Search the given tree for a declaration by skipping handled components and
772 exclude it from the candidates. */
775 disqualify_base_of_expr (tree t
, const char *reason
)
777 while (handled_component_p (t
))
778 t
= TREE_OPERAND (t
, 0);
780 if (sra_mode
== SRA_MODE_EARLY_IPA
)
782 if (INDIRECT_REF_P (t
))
783 t
= TREE_OPERAND (t
, 0);
784 t
= get_ssa_base_param (t
);
788 disqualify_candidate (t
, reason
);
791 /* Scan expression EXPR and create access structures for all accesses to
792 candidates for scalarization. Return the created access or NULL if none is
795 static struct access
*
796 build_access_from_expr_1 (tree
*expr_ptr
, gimple stmt
, bool write
)
798 struct access
*ret
= NULL
;
799 tree expr
= *expr_ptr
;
802 if (TREE_CODE (expr
) == BIT_FIELD_REF
803 || TREE_CODE (expr
) == IMAGPART_EXPR
804 || TREE_CODE (expr
) == REALPART_EXPR
)
806 expr
= TREE_OPERAND (expr
, 0);
812 /* We need to dive through V_C_Es in order to get the size of its parameter
813 and not the result type. Ada produces such statements. We are also
814 capable of handling the topmost V_C_E but not any of those buried in other
815 handled components. */
816 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
817 expr
= TREE_OPERAND (expr
, 0);
819 if (contains_view_convert_expr_p (expr
))
821 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
826 switch (TREE_CODE (expr
))
829 if (sra_mode
!= SRA_MODE_EARLY_IPA
)
837 case ARRAY_RANGE_REF
:
838 ret
= create_access (expr
, stmt
, write
);
845 if (write
&& partial_ref
&& ret
)
846 ret
->grp_partial_lhs
= 1;
851 /* Callback of scan_function. Scan expression EXPR and create access
852 structures for all accesses to candidates for scalarization. Return true if
853 any access has been inserted. */
856 build_access_from_expr (tree
*expr_ptr
,
857 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
, bool write
,
858 void *data ATTRIBUTE_UNUSED
)
860 return build_access_from_expr_1 (expr_ptr
, gsi_stmt (*gsi
), write
) != NULL
;
863 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
864 modes in which it matters, return true iff they have been disqualified. RHS
865 may be NULL, in that case ignore it. If we scalarize an aggregate in
866 intra-SRA we may need to add statements after each statement. This is not
867 possible if a statement unconditionally has to end the basic block. */
869 disqualify_ops_if_throwing_stmt (gimple stmt
, tree lhs
, tree rhs
)
871 if ((sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
872 && (stmt_can_throw_internal (stmt
) || stmt_ends_bb_p (stmt
)))
874 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
876 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
883 /* Result code for scan_assign callback for scan_function. */
884 enum scan_assign_result
{ SRA_SA_NONE
, /* nothing done for the stmt */
885 SRA_SA_PROCESSED
, /* stmt analyzed/changed */
886 SRA_SA_REMOVED
}; /* stmt redundant and eliminated */
889 /* Callback of scan_function. Scan expressions occuring in the statement
890 pointed to by STMT_EXPR, create access structures for all accesses to
891 candidates for scalarization and remove those candidates which occur in
892 statements or expressions that prevent them from being split apart. Return
893 true if any access has been inserted. */
895 static enum scan_assign_result
896 build_accesses_from_assign (gimple
*stmt_ptr
,
897 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
898 void *data ATTRIBUTE_UNUSED
)
900 gimple stmt
= *stmt_ptr
;
901 tree
*lhs_ptr
, *rhs_ptr
;
902 struct access
*lacc
, *racc
;
904 if (!gimple_assign_single_p (stmt
))
907 lhs_ptr
= gimple_assign_lhs_ptr (stmt
);
908 rhs_ptr
= gimple_assign_rhs1_ptr (stmt
);
910 if (disqualify_ops_if_throwing_stmt (stmt
, *lhs_ptr
, *rhs_ptr
))
913 racc
= build_access_from_expr_1 (rhs_ptr
, stmt
, false);
914 lacc
= build_access_from_expr_1 (lhs_ptr
, stmt
, true);
917 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
918 && !lacc
->grp_unscalarizable_region
919 && !racc
->grp_unscalarizable_region
920 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr
))
921 /* FIXME: Turn the following line into an assert after PR 40058 is
923 && lacc
->size
== racc
->size
924 && useless_type_conversion_p (lacc
->type
, racc
->type
))
926 struct assign_link
*link
;
928 link
= (struct assign_link
*) pool_alloc (link_pool
);
929 memset (link
, 0, sizeof (struct assign_link
));
934 add_link_to_rhs (racc
, link
);
937 return (lacc
|| racc
) ? SRA_SA_PROCESSED
: SRA_SA_NONE
;
940 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
941 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
944 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED
, tree op
,
945 void *data ATTRIBUTE_UNUSED
)
948 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
954 /* Scan function and look for interesting statements. Return true if any has
955 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
956 called on all expressions within statements except assign statements and
957 those deemed entirely unsuitable for some reason (all operands in such
958 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
959 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
960 called on assign statements and those call statements which have a lhs, it
961 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
962 pass and thus no statement is being modified. DATA is a pointer passed to
963 all callbacks. If any single callback returns true, this function also
964 returns true, otherwise it returns false. */
967 scan_function (bool (*scan_expr
) (tree
*, gimple_stmt_iterator
*, bool, void *),
968 enum scan_assign_result (*scan_assign
) (gimple
*,
969 gimple_stmt_iterator
*,
971 bool (*handle_ssa_defs
)(gimple
, void *),
972 bool analysis_stage
, void *data
)
974 gimple_stmt_iterator gsi
;
982 bool bb_changed
= false;
985 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
986 ret
|= handle_ssa_defs (gsi_stmt (gsi
), data
);
988 gsi
= gsi_start_bb (bb
);
989 while (!gsi_end_p (gsi
))
991 gimple stmt
= gsi_stmt (gsi
);
992 enum scan_assign_result assign_result
;
993 bool any
= false, deleted
= false;
995 if (analysis_stage
&& final_bbs
&& stmt_can_throw_external (stmt
))
996 bitmap_set_bit (final_bbs
, bb
->index
);
997 switch (gimple_code (stmt
))
1000 t
= gimple_return_retval_ptr (stmt
);
1001 if (*t
!= NULL_TREE
)
1002 any
|= scan_expr (t
, &gsi
, false, data
);
1003 if (analysis_stage
&& final_bbs
)
1004 bitmap_set_bit (final_bbs
, bb
->index
);
1008 assign_result
= scan_assign (&stmt
, &gsi
, data
);
1009 any
|= assign_result
== SRA_SA_PROCESSED
;
1010 deleted
= assign_result
== SRA_SA_REMOVED
;
1011 if (handle_ssa_defs
&& assign_result
!= SRA_SA_REMOVED
)
1012 any
|= handle_ssa_defs (stmt
, data
);
1016 /* Operands must be processed before the lhs. */
1017 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1019 tree
*argp
= gimple_call_arg_ptr (stmt
, i
);
1020 any
|= scan_expr (argp
, &gsi
, false, data
);
1025 tree dest
= gimple_call_fndecl (stmt
);
1026 int flags
= gimple_call_flags (stmt
);
1029 && DECL_BUILT_IN_CLASS (dest
) == BUILT_IN_NORMAL
1030 && DECL_FUNCTION_CODE (dest
) == BUILT_IN_APPLY_ARGS
)
1031 encountered_apply_args
= true;
1034 && (flags
& (ECF_CONST
| ECF_PURE
)) == 0)
1035 bitmap_set_bit (final_bbs
, bb
->index
);
1038 if (gimple_call_lhs (stmt
))
1040 tree
*lhs_ptr
= gimple_call_lhs_ptr (stmt
);
1042 || !disqualify_ops_if_throwing_stmt (stmt
,
1045 any
|= scan_expr (lhs_ptr
, &gsi
, true, data
);
1046 if (handle_ssa_defs
)
1047 any
|= handle_ssa_defs (stmt
, data
);
1055 walk_stmt_load_store_addr_ops (stmt
, NULL
, NULL
, NULL
,
1058 bitmap_set_bit (final_bbs
, bb
->index
);
1060 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
1062 tree
*op
= &TREE_VALUE (gimple_asm_input_op (stmt
, i
));
1063 any
|= scan_expr (op
, &gsi
, false, data
);
1065 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
1067 tree
*op
= &TREE_VALUE (gimple_asm_output_op (stmt
, i
));
1068 any
|= scan_expr (op
, &gsi
, true, data
);
1080 if (!analysis_stage
)
1084 maybe_clean_eh_stmt (stmt
);
1095 if (!analysis_stage
&& bb_changed
&& sra_mode
== SRA_MODE_EARLY_IPA
)
1096 gimple_purge_dead_eh_edges (bb
);
1102 /* Helper of QSORT function. There are pointers to accesses in the array. An
1103 access is considered smaller than another if it has smaller offset or if the
1104 offsets are the same but is size is bigger. */
1107 compare_access_positions (const void *a
, const void *b
)
1109 const access_p
*fp1
= (const access_p
*) a
;
1110 const access_p
*fp2
= (const access_p
*) b
;
1111 const access_p f1
= *fp1
;
1112 const access_p f2
= *fp2
;
1114 if (f1
->offset
!= f2
->offset
)
1115 return f1
->offset
< f2
->offset
? -1 : 1;
1117 if (f1
->size
== f2
->size
)
1119 /* Put any non-aggregate type before any aggregate type. */
1120 if (!is_gimple_reg_type (f1
->type
)
1121 && is_gimple_reg_type (f2
->type
))
1123 else if (is_gimple_reg_type (f1
->type
)
1124 && !is_gimple_reg_type (f2
->type
))
1126 /* Put any complex or vector type before any other scalar type. */
1127 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1128 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1129 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1130 || TREE_CODE (f2
->type
) == VECTOR_TYPE
))
1132 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1133 || TREE_CODE (f1
->type
) == VECTOR_TYPE
)
1134 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1135 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1137 /* Put the integral type with the bigger precision first. */
1138 else if (INTEGRAL_TYPE_P (f1
->type
)
1139 && INTEGRAL_TYPE_P (f2
->type
))
1140 return TYPE_PRECISION (f1
->type
) > TYPE_PRECISION (f2
->type
) ? -1 : 1;
1141 /* Put any integral type with non-full precision last. */
1142 else if (INTEGRAL_TYPE_P (f1
->type
)
1143 && (TREE_INT_CST_LOW (TYPE_SIZE (f1
->type
))
1144 != TYPE_PRECISION (f1
->type
)))
1146 else if (INTEGRAL_TYPE_P (f2
->type
)
1147 && (TREE_INT_CST_LOW (TYPE_SIZE (f2
->type
))
1148 != TYPE_PRECISION (f2
->type
)))
1150 /* Stabilize the sort. */
1151 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1154 /* We want the bigger accesses first, thus the opposite operator in the next
1156 return f1
->size
> f2
->size
? -1 : 1;
1160 /* Append a name of the declaration to the name obstack. A helper function for
1164 make_fancy_decl_name (tree decl
)
1168 tree name
= DECL_NAME (decl
);
1170 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1171 IDENTIFIER_LENGTH (name
));
1174 sprintf (buffer
, "D%u", DECL_UID (decl
));
1175 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1179 /* Helper for make_fancy_name. */
1182 make_fancy_name_1 (tree expr
)
1189 make_fancy_decl_name (expr
);
1193 switch (TREE_CODE (expr
))
1196 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1197 obstack_1grow (&name_obstack
, '$');
1198 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1202 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1203 obstack_1grow (&name_obstack
, '$');
1204 /* Arrays with only one element may not have a constant as their
1206 index
= TREE_OPERAND (expr
, 1);
1207 if (TREE_CODE (index
) != INTEGER_CST
)
1209 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1210 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1217 gcc_unreachable (); /* we treat these as scalars. */
1224 /* Create a human readable name for replacement variable of ACCESS. */
1227 make_fancy_name (tree expr
)
1229 make_fancy_name_1 (expr
);
1230 obstack_1grow (&name_obstack
, '\0');
1231 return XOBFINISH (&name_obstack
, char *);
1234 /* Helper function for build_ref_for_offset. */
1237 build_ref_for_offset_1 (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1243 tree tr_size
, index
, minidx
;
1244 HOST_WIDE_INT el_size
;
1246 if (offset
== 0 && exp_type
1247 && types_compatible_p (exp_type
, type
))
1250 switch (TREE_CODE (type
))
1253 case QUAL_UNION_TYPE
:
1255 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
1257 HOST_WIDE_INT pos
, size
;
1258 tree expr
, *expr_ptr
;
1260 if (TREE_CODE (fld
) != FIELD_DECL
)
1263 pos
= int_bit_position (fld
);
1264 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1265 tr_size
= DECL_SIZE (fld
);
1266 if (!tr_size
|| !host_integerp (tr_size
, 1))
1268 size
= tree_low_cst (tr_size
, 1);
1269 if (pos
> offset
|| (pos
+ size
) <= offset
)
1274 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1280 if (build_ref_for_offset_1 (expr_ptr
, TREE_TYPE (fld
),
1281 offset
- pos
, exp_type
))
1291 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1292 if (!tr_size
|| !host_integerp (tr_size
, 1))
1294 el_size
= tree_low_cst (tr_size
, 1);
1296 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1297 if (TREE_CODE (minidx
) != INTEGER_CST
)
1301 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1302 if (!integer_zerop (minidx
))
1303 index
= int_const_binop (PLUS_EXPR
, index
, minidx
, 0);
1304 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1305 NULL_TREE
, NULL_TREE
);
1307 offset
= offset
% el_size
;
1308 type
= TREE_TYPE (type
);
1323 /* Construct an expression that would reference a part of aggregate *EXPR of
1324 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1325 function only determines whether it can build such a reference without
1326 actually doing it, otherwise, the tree it points to is unshared first and
1327 then used as a base for furhter sub-references.
1329 FIXME: Eventually this should be replaced with
1330 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1331 minor rewrite of fold_stmt.
1335 build_ref_for_offset (tree
*expr
, tree type
, HOST_WIDE_INT offset
,
1336 tree exp_type
, bool allow_ptr
)
1338 location_t loc
= expr
? EXPR_LOCATION (*expr
) : UNKNOWN_LOCATION
;
1341 *expr
= unshare_expr (*expr
);
1343 if (allow_ptr
&& POINTER_TYPE_P (type
))
1345 type
= TREE_TYPE (type
);
1347 *expr
= fold_build1_loc (loc
, INDIRECT_REF
, type
, *expr
);
1350 return build_ref_for_offset_1 (expr
, type
, offset
, exp_type
);
1353 /* Return true iff TYPE is stdarg va_list type. */
1356 is_va_list_type (tree type
)
1358 return TYPE_MAIN_VARIANT (type
) == TYPE_MAIN_VARIANT (va_list_type_node
);
1361 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1362 those with type which is suitable for scalarization. */
1365 find_var_candidates (void)
1368 referenced_var_iterator rvi
;
1371 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1373 if (TREE_CODE (var
) != VAR_DECL
&& TREE_CODE (var
) != PARM_DECL
)
1375 type
= TREE_TYPE (var
);
1377 if (!AGGREGATE_TYPE_P (type
)
1378 || needs_to_live_in_memory (var
)
1379 || TREE_THIS_VOLATILE (var
)
1380 || !COMPLETE_TYPE_P (type
)
1381 || !host_integerp (TYPE_SIZE (type
), 1)
1382 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
1383 || type_internals_preclude_sra_p (type
)
1384 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1385 we also want to schedule it rather late. Thus we ignore it in
1387 || (sra_mode
== SRA_MODE_EARLY_INTRA
1388 && is_va_list_type (type
)))
1391 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1395 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1396 print_generic_expr (dump_file
, var
, 0);
1397 fprintf (dump_file
, "\n");
1405 /* Sort all accesses for the given variable, check for partial overlaps and
1406 return NULL if there are any. If there are none, pick a representative for
1407 each combination of offset and size and create a linked list out of them.
1408 Return the pointer to the first representative and make sure it is the first
1409 one in the vector of accesses. */
1411 static struct access
*
1412 sort_and_splice_var_accesses (tree var
)
1414 int i
, j
, access_count
;
1415 struct access
*res
, **prev_acc_ptr
= &res
;
1416 VEC (access_p
, heap
) *access_vec
;
1418 HOST_WIDE_INT low
= -1, high
= 0;
1420 access_vec
= get_base_access_vector (var
);
1423 access_count
= VEC_length (access_p
, access_vec
);
1425 /* Sort by <OFFSET, SIZE>. */
1426 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
1427 compare_access_positions
);
1430 while (i
< access_count
)
1432 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
1433 bool grp_write
= access
->write
;
1434 bool grp_read
= !access
->write
;
1435 bool multiple_reads
= false;
1436 bool grp_partial_lhs
= access
->grp_partial_lhs
;
1437 bool grp_different_types
= false;
1438 bool first_scalar
= is_gimple_reg_type (access
->type
);
1439 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
1441 if (first
|| access
->offset
>= high
)
1444 low
= access
->offset
;
1445 high
= access
->offset
+ access
->size
;
1447 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
1450 gcc_assert (access
->offset
>= low
1451 && access
->offset
+ access
->size
<= high
);
1454 while (j
< access_count
)
1456 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
1457 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
1464 multiple_reads
= true;
1468 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
1469 grp_different_types
|= !types_compatible_p (access
->type
, ac2
->type
);
1470 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
1471 relink_to_new_repr (access
, ac2
);
1473 /* If there are both aggregate-type and scalar-type accesses with
1474 this combination of size and offset, the comparison function
1475 should have put the scalars first. */
1476 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
1477 ac2
->group_representative
= access
;
1483 access
->group_representative
= access
;
1484 access
->grp_write
= grp_write
;
1485 access
->grp_read
= grp_read
;
1486 access
->grp_hint
= multiple_reads
;
1487 access
->grp_partial_lhs
= grp_partial_lhs
;
1488 access
->grp_different_types
= grp_different_types
;
1489 access
->grp_unscalarizable_region
= unscalarizable_region
;
1490 if (access
->first_link
)
1491 add_access_to_work_queue (access
);
1493 *prev_acc_ptr
= access
;
1494 prev_acc_ptr
= &access
->next_grp
;
1497 gcc_assert (res
== VEC_index (access_p
, access_vec
, 0));
1501 /* Create a variable for the given ACCESS which determines the type, name and a
1502 few other properties. Return the variable declaration and store it also to
1503 ACCESS->replacement. */
1506 create_access_replacement (struct access
*access
)
1510 repl
= create_tmp_var (access
->type
, "SR");
1512 add_referenced_var (repl
);
1513 mark_sym_for_renaming (repl
);
1515 if (!access
->grp_partial_lhs
1516 && (TREE_CODE (access
->type
) == COMPLEX_TYPE
1517 || TREE_CODE (access
->type
) == VECTOR_TYPE
))
1518 DECL_GIMPLE_REG_P (repl
) = 1;
1520 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
1521 DECL_ARTIFICIAL (repl
) = 1;
1523 if (DECL_NAME (access
->base
)
1524 && !DECL_IGNORED_P (access
->base
)
1525 && !DECL_ARTIFICIAL (access
->base
))
1527 char *pretty_name
= make_fancy_name (access
->expr
);
1529 DECL_NAME (repl
) = get_identifier (pretty_name
);
1530 obstack_free (&name_obstack
, pretty_name
);
1532 SET_DECL_DEBUG_EXPR (repl
, access
->expr
);
1533 DECL_DEBUG_EXPR_IS_FROM (repl
) = 1;
1534 DECL_IGNORED_P (repl
) = 0;
1537 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
1538 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
1542 fprintf (dump_file
, "Created a replacement for ");
1543 print_generic_expr (dump_file
, access
->base
, 0);
1544 fprintf (dump_file
, " offset: %u, size: %u: ",
1545 (unsigned) access
->offset
, (unsigned) access
->size
);
1546 print_generic_expr (dump_file
, repl
, 0);
1547 fprintf (dump_file
, "\n");
1549 sra_stats
.replacements
++;
1554 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1557 get_access_replacement (struct access
*access
)
1559 gcc_assert (access
->grp_to_be_replaced
);
1561 if (!access
->replacement_decl
)
1562 access
->replacement_decl
= create_access_replacement (access
);
1563 return access
->replacement_decl
;
1566 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1567 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1568 to it is not "within" the root. */
1571 build_access_subtree (struct access
**access
)
1573 struct access
*root
= *access
, *last_child
= NULL
;
1574 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1576 *access
= (*access
)->next_grp
;
1577 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
1580 root
->first_child
= *access
;
1582 last_child
->next_sibling
= *access
;
1583 last_child
= *access
;
1585 build_access_subtree (access
);
1589 /* Build a tree of access representatives, ACCESS is the pointer to the first
1590 one, others are linked in a list by the next_grp field. Decide about scalar
1591 replacements on the way, return true iff any are to be created. */
1594 build_access_trees (struct access
*access
)
1598 struct access
*root
= access
;
1600 build_access_subtree (&access
);
1601 root
->next_grp
= access
;
1605 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1609 expr_with_var_bounded_array_refs_p (tree expr
)
1611 while (handled_component_p (expr
))
1613 if (TREE_CODE (expr
) == ARRAY_REF
1614 && !host_integerp (array_ref_low_bound (expr
), 0))
1616 expr
= TREE_OPERAND (expr
, 0);
1621 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1622 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1623 all sorts of access flags appropriately along the way, notably always ser
1624 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1627 analyze_access_subtree (struct access
*root
, bool allow_replacements
,
1628 bool mark_read
, bool mark_write
)
1630 struct access
*child
;
1631 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1632 HOST_WIDE_INT covered_to
= root
->offset
;
1633 bool scalar
= is_gimple_reg_type (root
->type
);
1634 bool hole
= false, sth_created
= false;
1635 bool direct_read
= root
->grp_read
;
1638 root
->grp_read
= true;
1639 else if (root
->grp_read
)
1643 root
->grp_write
= true;
1644 else if (root
->grp_write
)
1647 if (root
->grp_unscalarizable_region
)
1648 allow_replacements
= false;
1650 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
1651 allow_replacements
= false;
1653 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
1655 if (!hole
&& child
->offset
< covered_to
)
1658 covered_to
+= child
->size
;
1660 sth_created
|= analyze_access_subtree (child
, allow_replacements
,
1661 mark_read
, mark_write
);
1663 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
1664 hole
|= !child
->grp_covered
;
1667 if (allow_replacements
&& scalar
&& !root
->first_child
1669 || (direct_read
&& root
->grp_write
)))
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1673 fprintf (dump_file
, "Marking ");
1674 print_generic_expr (dump_file
, root
->base
, 0);
1675 fprintf (dump_file
, " offset: %u, size: %u: ",
1676 (unsigned) root
->offset
, (unsigned) root
->size
);
1677 fprintf (dump_file
, " to be replaced.\n");
1680 root
->grp_to_be_replaced
= 1;
1684 else if (covered_to
< limit
)
1687 if (sth_created
&& !hole
)
1689 root
->grp_covered
= 1;
1692 if (root
->grp_write
|| TREE_CODE (root
->base
) == PARM_DECL
)
1693 root
->grp_unscalarized_data
= 1; /* not covered and written to */
1699 /* Analyze all access trees linked by next_grp by the means of
1700 analyze_access_subtree. */
1702 analyze_access_trees (struct access
*access
)
1708 if (analyze_access_subtree (access
, true, false, false))
1710 access
= access
->next_grp
;
1716 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1717 SIZE would conflict with an already existing one. If exactly such a child
1718 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1721 child_would_conflict_in_lacc (struct access
*lacc
, HOST_WIDE_INT norm_offset
,
1722 HOST_WIDE_INT size
, struct access
**exact_match
)
1724 struct access
*child
;
1726 for (child
= lacc
->first_child
; child
; child
= child
->next_sibling
)
1728 if (child
->offset
== norm_offset
&& child
->size
== size
)
1730 *exact_match
= child
;
1734 if (child
->offset
< norm_offset
+ size
1735 && child
->offset
+ child
->size
> norm_offset
)
1742 /* Create a new child access of PARENT, with all properties just like MODEL
1743 except for its offset and with its grp_write false and grp_read true.
1744 Return the new access or NULL if it cannot be created. Note that this access
1745 is created long after all splicing and sorting, it's not located in any
1746 access vector and is automatically a representative of its group. */
1748 static struct access
*
1749 create_artificial_child_access (struct access
*parent
, struct access
*model
,
1750 HOST_WIDE_INT new_offset
)
1752 struct access
*access
;
1753 struct access
**child
;
1754 tree expr
= parent
->base
;;
1756 gcc_assert (!model
->grp_unscalarizable_region
);
1758 if (!build_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
1759 model
->type
, false))
1762 access
= (struct access
*) pool_alloc (access_pool
);
1763 memset (access
, 0, sizeof (struct access
));
1764 access
->base
= parent
->base
;
1765 access
->expr
= expr
;
1766 access
->offset
= new_offset
;
1767 access
->size
= model
->size
;
1768 access
->type
= model
->type
;
1769 access
->grp_write
= true;
1770 access
->grp_read
= false;
1772 child
= &parent
->first_child
;
1773 while (*child
&& (*child
)->offset
< new_offset
)
1774 child
= &(*child
)->next_sibling
;
1776 access
->next_sibling
= *child
;
1783 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1784 true if any new subaccess was created. Additionally, if RACC is a scalar
1785 access but LACC is not, change the type of the latter, if possible. */
1788 propagate_subaccesses_across_link (struct access
*lacc
, struct access
*racc
)
1790 struct access
*rchild
;
1791 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
1794 if (is_gimple_reg_type (lacc
->type
)
1795 || lacc
->grp_unscalarizable_region
1796 || racc
->grp_unscalarizable_region
)
1799 if (!lacc
->first_child
&& !racc
->first_child
1800 && is_gimple_reg_type (racc
->type
))
1802 tree t
= lacc
->base
;
1804 if (build_ref_for_offset (&t
, TREE_TYPE (t
), lacc
->offset
, racc
->type
,
1808 lacc
->type
= racc
->type
;
1813 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
1815 struct access
*new_acc
= NULL
;
1816 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
1818 if (rchild
->grp_unscalarizable_region
)
1821 if (child_would_conflict_in_lacc (lacc
, norm_offset
, rchild
->size
,
1826 rchild
->grp_hint
= 1;
1827 new_acc
->grp_hint
|= new_acc
->grp_read
;
1828 if (rchild
->first_child
)
1829 ret
|= propagate_subaccesses_across_link (new_acc
, rchild
);
1834 /* If a (part of) a union field is on the RHS of an assignment, it can
1835 have sub-accesses which do not make sense on the LHS (PR 40351).
1836 Check that this is not the case. */
1837 if (!build_ref_for_offset (NULL
, TREE_TYPE (lacc
->base
), norm_offset
,
1838 rchild
->type
, false))
1841 rchild
->grp_hint
= 1;
1842 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
);
1846 if (racc
->first_child
)
1847 propagate_subaccesses_across_link (new_acc
, rchild
);
1854 /* Propagate all subaccesses across assignment links. */
1857 propagate_all_subaccesses (void)
1859 while (work_queue_head
)
1861 struct access
*racc
= pop_access_from_work_queue ();
1862 struct assign_link
*link
;
1864 gcc_assert (racc
->first_link
);
1866 for (link
= racc
->first_link
; link
; link
= link
->next
)
1868 struct access
*lacc
= link
->lacc
;
1870 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
1872 lacc
= lacc
->group_representative
;
1873 if (propagate_subaccesses_across_link (lacc
, racc
)
1874 && lacc
->first_link
)
1875 add_access_to_work_queue (lacc
);
1880 /* Go through all accesses collected throughout the (intraprocedural) analysis
1881 stage, exclude overlapping ones, identify representatives and build trees
1882 out of them, making decisions about scalarization on the way. Return true
1883 iff there are any to-be-scalarized variables after this stage. */
1886 analyze_all_variable_accesses (void)
1889 referenced_var_iterator rvi
;
1892 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1893 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1895 struct access
*access
;
1897 access
= sort_and_splice_var_accesses (var
);
1899 build_access_trees (access
);
1901 disqualify_candidate (var
,
1902 "No or inhibitingly overlapping accesses.");
1905 propagate_all_subaccesses ();
1907 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1908 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1910 struct access
*access
= get_first_repr_for_decl (var
);
1912 if (analyze_access_trees (access
))
1915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1917 fprintf (dump_file
, "\nAccess trees for ");
1918 print_generic_expr (dump_file
, var
, 0);
1919 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
1920 dump_access_tree (dump_file
, access
);
1921 fprintf (dump_file
, "\n");
1925 disqualify_candidate (var
, "No scalar replacements to be created.");
1930 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
1937 /* Return true iff a reference statement into aggregate AGG can be built for
1938 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1939 or a child of its sibling. TOP_OFFSET is the offset from the processed
1940 access subtree that has to be subtracted from offset of each access. */
1943 ref_expr_for_all_replacements_p (struct access
*access
, tree agg
,
1944 HOST_WIDE_INT top_offset
)
1948 if (access
->grp_to_be_replaced
1949 && !build_ref_for_offset (NULL
, TREE_TYPE (agg
),
1950 access
->offset
- top_offset
,
1951 access
->type
, false))
1954 if (access
->first_child
1955 && !ref_expr_for_all_replacements_p (access
->first_child
, agg
,
1959 access
= access
->next_sibling
;
1966 /* Generate statements copying scalar replacements of accesses within a subtree
1967 into or out of AGG. ACCESS is the first child of the root of the subtree to
1968 be processed. AGG is an aggregate type expression (can be a declaration but
1969 does not have to be, it can for example also be an indirect_ref).
1970 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1971 from offsets of individual accesses to get corresponding offsets for AGG.
1972 If CHUNK_SIZE is non-null, copy only replacements in the interval
1973 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1974 statement iterator used to place the new statements. WRITE should be true
1975 when the statements should write from AGG to the replacement and false if
1976 vice versa. if INSERT_AFTER is true, new statements will be added after the
1977 current statement in GSI, they will be added before the statement
1981 generate_subtree_copies (struct access
*access
, tree agg
,
1982 HOST_WIDE_INT top_offset
,
1983 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
1984 gimple_stmt_iterator
*gsi
, bool write
,
1991 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
1994 if (access
->grp_to_be_replaced
1996 || access
->offset
+ access
->size
> start_offset
))
1998 tree repl
= get_access_replacement (access
);
2002 ref_found
= build_ref_for_offset (&expr
, TREE_TYPE (agg
),
2003 access
->offset
- top_offset
,
2004 access
->type
, false);
2005 gcc_assert (ref_found
);
2009 if (access
->grp_partial_lhs
)
2010 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
2012 insert_after
? GSI_NEW_STMT
2014 stmt
= gimple_build_assign (repl
, expr
);
2018 TREE_NO_WARNING (repl
) = 1;
2019 if (access
->grp_partial_lhs
)
2020 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2022 insert_after
? GSI_NEW_STMT
2024 stmt
= gimple_build_assign (expr
, repl
);
2028 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2030 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2032 sra_stats
.subtree_copies
++;
2035 if (access
->first_child
)
2036 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
2037 start_offset
, chunk_size
, gsi
,
2038 write
, insert_after
);
2040 access
= access
->next_sibling
;
2045 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2046 the root of the subtree to be processed. GSI is the statement iterator used
2047 for inserting statements which are added after the current statement if
2048 INSERT_AFTER is true or before it otherwise. */
2051 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
2055 struct access
*child
;
2057 if (access
->grp_to_be_replaced
)
2061 stmt
= gimple_build_assign (get_access_replacement (access
),
2062 fold_convert (access
->type
,
2063 integer_zero_node
));
2065 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2067 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2071 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2072 init_subtree_with_zero (child
, gsi
, insert_after
);
2075 /* Search for an access representative for the given expression EXPR and
2076 return it or NULL if it cannot be found. */
2078 static struct access
*
2079 get_access_for_expr (tree expr
)
2081 HOST_WIDE_INT offset
, size
, max_size
;
2084 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2085 a different size than the size of its argument and we need the latter
2087 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
2088 expr
= TREE_OPERAND (expr
, 0);
2090 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
2091 if (max_size
== -1 || !DECL_P (base
))
2094 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
2097 return get_var_base_offset_size_access (base
, offset
, max_size
);
2100 /* Callback for scan_function. Replace the expression EXPR with a scalar
2101 replacement if there is one and generate other statements to do type
2102 conversion or subtree copying if necessary. GSI is used to place newly
2103 created statements, WRITE is true if the expression is being written to (it
2104 is on a LHS of a statement or output in an assembly statement). */
2107 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
,
2108 void *data ATTRIBUTE_UNUSED
)
2110 struct access
*access
;
2113 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
2116 expr
= &TREE_OPERAND (*expr
, 0);
2121 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
2122 expr
= &TREE_OPERAND (*expr
, 0);
2123 access
= get_access_for_expr (*expr
);
2126 type
= TREE_TYPE (*expr
);
2128 if (access
->grp_to_be_replaced
)
2130 tree repl
= get_access_replacement (access
);
2131 /* If we replace a non-register typed access simply use the original
2132 access expression to extract the scalar component afterwards.
2133 This happens if scalarizing a function return value or parameter
2134 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2135 gcc.c-torture/compile/20011217-1.c.
2137 We also want to use this when accessing a complex or vector which can
2138 be accessed as a different type too, potentially creating a need for
2139 type conversion (see PR42196). */
2140 if (!is_gimple_reg_type (type
)
2141 || (access
->grp_different_types
2142 && (TREE_CODE (type
) == COMPLEX_TYPE
2143 || TREE_CODE (type
) == VECTOR_TYPE
)))
2145 tree ref
= access
->base
;
2148 ok
= build_ref_for_offset (&ref
, TREE_TYPE (ref
),
2149 access
->offset
, access
->type
, false);
2156 if (access
->grp_partial_lhs
)
2157 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
2158 false, GSI_NEW_STMT
);
2159 stmt
= gimple_build_assign (repl
, ref
);
2160 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2166 if (access
->grp_partial_lhs
)
2167 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2168 true, GSI_SAME_STMT
);
2169 stmt
= gimple_build_assign (ref
, repl
);
2170 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2175 gcc_assert (useless_type_conversion_p (type
, access
->type
));
2181 if (access
->first_child
)
2183 HOST_WIDE_INT start_offset
, chunk_size
;
2185 && host_integerp (TREE_OPERAND (bfr
, 1), 1)
2186 && host_integerp (TREE_OPERAND (bfr
, 2), 1))
2188 chunk_size
= tree_low_cst (TREE_OPERAND (bfr
, 1), 1);
2189 start_offset
= access
->offset
2190 + tree_low_cst (TREE_OPERAND (bfr
, 2), 1);
2193 start_offset
= chunk_size
= 0;
2195 generate_subtree_copies (access
->first_child
, access
->base
, 0,
2196 start_offset
, chunk_size
, gsi
, write
, write
);
2201 /* Where scalar replacements of the RHS have been written to when a replacement
2202 of a LHS of an assigments cannot be direclty loaded from a replacement of
2204 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
2205 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
2206 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
2208 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2209 base aggregate if there are unscalarized data or directly to LHS
2212 static enum unscalarized_data_handling
2213 handle_unscalarized_data_in_subtree (struct access
*top_racc
, tree lhs
,
2214 gimple_stmt_iterator
*gsi
)
2216 if (top_racc
->grp_unscalarized_data
)
2218 generate_subtree_copies (top_racc
->first_child
, top_racc
->base
, 0, 0, 0,
2220 return SRA_UDH_RIGHT
;
2224 generate_subtree_copies (top_racc
->first_child
, lhs
, top_racc
->offset
,
2225 0, 0, gsi
, false, false);
2226 return SRA_UDH_LEFT
;
2231 /* Try to generate statements to load all sub-replacements in an access
2232 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2233 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2234 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2235 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2236 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2237 the rhs top aggregate has already been refreshed by contents of its scalar
2238 reductions and is set to true if this function has to do it. */
2241 load_assign_lhs_subreplacements (struct access
*lacc
, struct access
*top_racc
,
2242 HOST_WIDE_INT left_offset
,
2243 HOST_WIDE_INT right_offset
,
2244 gimple_stmt_iterator
*old_gsi
,
2245 gimple_stmt_iterator
*new_gsi
,
2246 enum unscalarized_data_handling
*refreshed
,
2249 location_t loc
= EXPR_LOCATION (lacc
->expr
);
2252 if (lacc
->grp_to_be_replaced
)
2254 struct access
*racc
;
2255 HOST_WIDE_INT offset
= lacc
->offset
- left_offset
+ right_offset
;
2259 racc
= find_access_in_subtree (top_racc
, offset
, lacc
->size
);
2260 if (racc
&& racc
->grp_to_be_replaced
)
2262 rhs
= get_access_replacement (racc
);
2263 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
2264 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, lacc
->type
, rhs
);
2268 /* No suitable access on the right hand side, need to load from
2269 the aggregate. See if we have to update it first... */
2270 if (*refreshed
== SRA_UDH_NONE
)
2271 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
,
2274 if (*refreshed
== SRA_UDH_LEFT
)
2279 repl_found
= build_ref_for_offset (&rhs
, TREE_TYPE (rhs
),
2280 lacc
->offset
, lacc
->type
,
2282 gcc_assert (repl_found
);
2288 rhs
= top_racc
->base
;
2289 repl_found
= build_ref_for_offset (&rhs
,
2290 TREE_TYPE (top_racc
->base
),
2291 offset
, lacc
->type
, false);
2292 gcc_assert (repl_found
);
2296 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
2297 gsi_insert_after (new_gsi
, stmt
, GSI_NEW_STMT
);
2299 sra_stats
.subreplacements
++;
2301 else if (*refreshed
== SRA_UDH_NONE
2302 && lacc
->grp_read
&& !lacc
->grp_covered
)
2303 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
, lhs
,
2306 if (lacc
->first_child
)
2307 load_assign_lhs_subreplacements (lacc
->first_child
, top_racc
,
2308 left_offset
, right_offset
,
2309 old_gsi
, new_gsi
, refreshed
, lhs
);
2310 lacc
= lacc
->next_sibling
;
2315 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2316 to the assignment and GSI is the statement iterator pointing at it. Returns
2317 the same values as sra_modify_assign. */
2319 static enum scan_assign_result
2320 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
2322 tree lhs
= gimple_assign_lhs (*stmt
);
2325 acc
= get_access_for_expr (lhs
);
2329 if (VEC_length (constructor_elt
,
2330 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt
))) > 0)
2332 /* I have never seen this code path trigger but if it can happen the
2333 following should handle it gracefully. */
2334 if (access_has_children_p (acc
))
2335 generate_subtree_copies (acc
->first_child
, acc
->base
, 0, 0, 0, gsi
,
2337 return SRA_SA_PROCESSED
;
2340 if (acc
->grp_covered
)
2342 init_subtree_with_zero (acc
, gsi
, false);
2343 unlink_stmt_vdef (*stmt
);
2344 gsi_remove (gsi
, true);
2345 return SRA_SA_REMOVED
;
2349 init_subtree_with_zero (acc
, gsi
, true);
2350 return SRA_SA_PROCESSED
;
2355 /* Callback of scan_function to process assign statements. It examines both
2356 sides of the statement, replaces them with a scalare replacement if there is
2357 one and generating copying of replacements if scalarized aggregates have been
2358 used in the assignment. STMT is a pointer to the assign statement, GSI is
2359 used to hold generated statements for type conversions and subtree
2362 static enum scan_assign_result
2363 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
2364 void *data ATTRIBUTE_UNUSED
)
2366 struct access
*lacc
, *racc
;
2368 bool modify_this_stmt
= false;
2369 bool force_gimple_rhs
= false;
2370 location_t loc
= gimple_location (*stmt
);
2372 if (!gimple_assign_single_p (*stmt
))
2374 lhs
= gimple_assign_lhs (*stmt
);
2375 rhs
= gimple_assign_rhs1 (*stmt
);
2377 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
2378 return sra_modify_constructor_assign (stmt
, gsi
);
2380 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
2381 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
2382 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
2384 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (*stmt
),
2386 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (*stmt
),
2388 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2391 lacc
= get_access_for_expr (lhs
);
2392 racc
= get_access_for_expr (rhs
);
2396 if (lacc
&& lacc
->grp_to_be_replaced
)
2398 lhs
= get_access_replacement (lacc
);
2399 gimple_assign_set_lhs (*stmt
, lhs
);
2400 modify_this_stmt
= true;
2401 if (lacc
->grp_partial_lhs
)
2402 force_gimple_rhs
= true;
2406 if (racc
&& racc
->grp_to_be_replaced
)
2408 rhs
= get_access_replacement (racc
);
2409 modify_this_stmt
= true;
2410 if (racc
->grp_partial_lhs
)
2411 force_gimple_rhs
= true;
2415 if (modify_this_stmt
)
2417 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2419 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2420 ??? This should move to fold_stmt which we simply should
2421 call after building a VIEW_CONVERT_EXPR here. */
2422 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
2423 && !access_has_children_p (lacc
))
2426 if (build_ref_for_offset (&expr
, TREE_TYPE (lhs
), 0,
2427 TREE_TYPE (rhs
), false))
2430 gimple_assign_set_lhs (*stmt
, expr
);
2433 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
2434 && !access_has_children_p (racc
))
2437 if (build_ref_for_offset (&expr
, TREE_TYPE (rhs
), 0,
2438 TREE_TYPE (lhs
), false))
2441 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2443 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
), rhs
);
2444 if (!is_gimple_reg (lhs
))
2445 force_gimple_rhs
= true;
2449 if (force_gimple_rhs
)
2450 rhs
= force_gimple_operand_gsi (gsi
, rhs
, true, NULL_TREE
,
2451 true, GSI_SAME_STMT
);
2452 if (gimple_assign_rhs1 (*stmt
) != rhs
)
2454 gimple_assign_set_rhs_from_tree (gsi
, rhs
);
2455 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2459 /* From this point on, the function deals with assignments in between
2460 aggregates when at least one has scalar reductions of some of its
2461 components. There are three possible scenarios: Both the LHS and RHS have
2462 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2464 In the first case, we would like to load the LHS components from RHS
2465 components whenever possible. If that is not possible, we would like to
2466 read it directly from the RHS (after updating it by storing in it its own
2467 components). If there are some necessary unscalarized data in the LHS,
2468 those will be loaded by the original assignment too. If neither of these
2469 cases happen, the original statement can be removed. Most of this is done
2470 by load_assign_lhs_subreplacements.
2472 In the second case, we would like to store all RHS scalarized components
2473 directly into LHS and if they cover the aggregate completely, remove the
2474 statement too. In the third case, we want the LHS components to be loaded
2475 directly from the RHS (DSE will remove the original statement if it
2478 This is a bit complex but manageable when types match and when unions do
2479 not cause confusion in a way that we cannot really load a component of LHS
2480 from the RHS or vice versa (the access representing this level can have
2481 subaccesses that are accessible only through a different union field at a
2482 higher level - different from the one used in the examined expression).
2485 Therefore, I specially handle a fourth case, happening when there is a
2486 specific type cast or it is impossible to locate a scalarized subaccess on
2487 the other side of the expression. If that happens, I simply "refresh" the
2488 RHS by storing in it is scalarized components leave the original statement
2489 there to do the copying and then load the scalar replacements of the LHS.
2490 This is what the first branch does. */
2492 if (contains_view_convert_expr_p (rhs
) || contains_view_convert_expr_p (lhs
)
2493 || (access_has_children_p (racc
)
2494 && !ref_expr_for_all_replacements_p (racc
, lhs
, racc
->offset
))
2495 || (access_has_children_p (lacc
)
2496 && !ref_expr_for_all_replacements_p (lacc
, rhs
, lacc
->offset
)))
2498 if (access_has_children_p (racc
))
2499 generate_subtree_copies (racc
->first_child
, racc
->base
, 0, 0, 0,
2501 if (access_has_children_p (lacc
))
2502 generate_subtree_copies (lacc
->first_child
, lacc
->base
, 0, 0, 0,
2504 sra_stats
.separate_lhs_rhs_handling
++;
2508 if (access_has_children_p (lacc
) && access_has_children_p (racc
))
2510 gimple_stmt_iterator orig_gsi
= *gsi
;
2511 enum unscalarized_data_handling refreshed
;
2513 if (lacc
->grp_read
&& !lacc
->grp_covered
)
2514 refreshed
= handle_unscalarized_data_in_subtree (racc
, lhs
, gsi
);
2516 refreshed
= SRA_UDH_NONE
;
2518 load_assign_lhs_subreplacements (lacc
->first_child
, racc
,
2519 lacc
->offset
, racc
->offset
,
2520 &orig_gsi
, gsi
, &refreshed
, lhs
);
2521 if (refreshed
!= SRA_UDH_RIGHT
)
2523 if (*stmt
== gsi_stmt (*gsi
))
2526 unlink_stmt_vdef (*stmt
);
2527 gsi_remove (&orig_gsi
, true);
2528 sra_stats
.deleted
++;
2529 return SRA_SA_REMOVED
;
2534 if (access_has_children_p (racc
))
2536 if (!racc
->grp_unscalarized_data
)
2538 generate_subtree_copies (racc
->first_child
, lhs
,
2539 racc
->offset
, 0, 0, gsi
,
2541 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2542 unlink_stmt_vdef (*stmt
);
2543 gsi_remove (gsi
, true);
2544 sra_stats
.deleted
++;
2545 return SRA_SA_REMOVED
;
2548 generate_subtree_copies (racc
->first_child
, lhs
,
2549 racc
->offset
, 0, 0, gsi
, false, true);
2551 else if (access_has_children_p (lacc
))
2552 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
2553 0, 0, gsi
, true, true);
2556 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2559 /* Generate statements initializing scalar replacements of parts of function
2563 initialize_parameter_reductions (void)
2565 gimple_stmt_iterator gsi
;
2566 gimple_seq seq
= NULL
;
2569 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2571 parm
= TREE_CHAIN (parm
))
2573 VEC (access_p
, heap
) *access_vec
;
2574 struct access
*access
;
2576 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
2578 access_vec
= get_base_access_vector (parm
);
2584 seq
= gimple_seq_alloc ();
2585 gsi
= gsi_start (seq
);
2588 for (access
= VEC_index (access_p
, access_vec
, 0);
2590 access
= access
->next_grp
)
2591 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true);
2595 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR
), seq
);
2598 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2599 it reveals there are components of some aggregates to be scalarized, it runs
2600 the required transformations. */
2602 perform_intra_sra (void)
2607 if (!find_var_candidates ())
2610 if (!scan_function (build_access_from_expr
, build_accesses_from_assign
, NULL
,
2614 if (!analyze_all_variable_accesses ())
2617 scan_function (sra_modify_expr
, sra_modify_assign
, NULL
, false, NULL
);
2618 initialize_parameter_reductions ();
2620 statistics_counter_event (cfun
, "Scalar replacements created",
2621 sra_stats
.replacements
);
2622 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
2623 statistics_counter_event (cfun
, "Subtree copy stmts",
2624 sra_stats
.subtree_copies
);
2625 statistics_counter_event (cfun
, "Subreplacement stmts",
2626 sra_stats
.subreplacements
);
2627 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
2628 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
2629 sra_stats
.separate_lhs_rhs_handling
);
2631 ret
= TODO_update_ssa
;
2634 sra_deinitialize ();
2638 /* Perform early intraprocedural SRA. */
2640 early_intra_sra (void)
2642 sra_mode
= SRA_MODE_EARLY_INTRA
;
2643 return perform_intra_sra ();
2646 /* Perform "late" intraprocedural SRA. */
2648 late_intra_sra (void)
2650 sra_mode
= SRA_MODE_INTRA
;
2651 return perform_intra_sra ();
2656 gate_intra_sra (void)
2658 return flag_tree_sra
!= 0;
2662 struct gimple_opt_pass pass_sra_early
=
2667 gate_intra_sra
, /* gate */
2668 early_intra_sra
, /* execute */
2671 0, /* static_pass_number */
2672 TV_TREE_SRA
, /* tv_id */
2673 PROP_cfg
| PROP_ssa
, /* properties_required */
2674 0, /* properties_provided */
2675 0, /* properties_destroyed */
2676 0, /* todo_flags_start */
2680 | TODO_verify_ssa
/* todo_flags_finish */
2684 struct gimple_opt_pass pass_sra
=
2689 gate_intra_sra
, /* gate */
2690 late_intra_sra
, /* execute */
2693 0, /* static_pass_number */
2694 TV_TREE_SRA
, /* tv_id */
2695 PROP_cfg
| PROP_ssa
, /* properties_required */
2696 0, /* properties_provided */
2697 0, /* properties_destroyed */
2698 TODO_update_address_taken
, /* todo_flags_start */
2702 | TODO_verify_ssa
/* todo_flags_finish */
2707 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2711 is_unused_scalar_param (tree parm
)
2714 return (is_gimple_reg (parm
)
2715 && (!(name
= gimple_default_def (cfun
, parm
))
2716 || has_zero_uses (name
)));
2719 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2720 examine whether there are any direct or otherwise infeasible ones. If so,
2721 return true, otherwise return false. PARM must be a gimple register with a
2722 non-NULL default definition. */
2725 ptr_parm_has_direct_uses (tree parm
)
2727 imm_use_iterator ui
;
2729 tree name
= gimple_default_def (cfun
, parm
);
2732 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
2734 if (gimple_assign_single_p (stmt
))
2736 tree rhs
= gimple_assign_rhs1 (stmt
);
2739 else if (TREE_CODE (rhs
) == ADDR_EXPR
)
2743 rhs
= TREE_OPERAND (rhs
, 0);
2745 while (handled_component_p (rhs
));
2746 if (INDIRECT_REF_P (rhs
) && TREE_OPERAND (rhs
, 0) == name
)
2750 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
2752 tree t
= gimple_return_retval (stmt
);
2756 else if (is_gimple_call (stmt
))
2759 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
2761 tree arg
= gimple_call_arg (stmt
, i
);
2769 else if (!is_gimple_debug (stmt
))
2773 BREAK_FROM_IMM_USE_STMT (ui
);
2779 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2780 them in candidate_bitmap. Note that these do not necessarily include
2781 parameter which are unused and thus can be removed. Return true iff any
2782 such candidate has been found. */
2785 find_param_candidates (void)
2791 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2793 parm
= TREE_CHAIN (parm
))
2795 tree type
= TREE_TYPE (parm
);
2799 if (TREE_THIS_VOLATILE (parm
)
2800 || TREE_ADDRESSABLE (parm
)
2801 || is_va_list_type (type
))
2804 if (is_unused_scalar_param (parm
))
2810 if (POINTER_TYPE_P (type
))
2812 type
= TREE_TYPE (type
);
2814 if (TREE_CODE (type
) == FUNCTION_TYPE
2815 || TYPE_VOLATILE (type
)
2816 || !is_gimple_reg (parm
)
2817 || is_va_list_type (type
)
2818 || ptr_parm_has_direct_uses (parm
))
2821 else if (!AGGREGATE_TYPE_P (type
))
2824 if (!COMPLETE_TYPE_P (type
)
2825 || !host_integerp (TYPE_SIZE (type
), 1)
2826 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
2827 || (AGGREGATE_TYPE_P (type
)
2828 && type_internals_preclude_sra_p (type
)))
2831 bitmap_set_bit (candidate_bitmap
, DECL_UID (parm
));
2833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2835 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (parm
));
2836 print_generic_expr (dump_file
, parm
, 0);
2837 fprintf (dump_file
, "\n");
2841 func_param_count
= count
;
2845 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2849 mark_maybe_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
2852 struct access
*repr
= (struct access
*) data
;
2854 repr
->grp_maybe_modified
= 1;
2858 /* Analyze what representatives (in linked lists accessible from
2859 REPRESENTATIVES) can be modified by side effects of statements in the
2860 current function. */
2863 analyze_modified_params (VEC (access_p
, heap
) *representatives
)
2867 for (i
= 0; i
< func_param_count
; i
++)
2869 struct access
*repr
;
2871 for (repr
= VEC_index (access_p
, representatives
, i
);
2873 repr
= repr
->next_grp
)
2875 struct access
*access
;
2879 if (no_accesses_p (repr
))
2881 if (!POINTER_TYPE_P (TREE_TYPE (repr
->base
))
2882 || repr
->grp_maybe_modified
)
2885 ao_ref_init (&ar
, repr
->expr
);
2886 visited
= BITMAP_ALLOC (NULL
);
2887 for (access
= repr
; access
; access
= access
->next_sibling
)
2889 /* All accesses are read ones, otherwise grp_maybe_modified would
2890 be trivially set. */
2891 walk_aliased_vdefs (&ar
, gimple_vuse (access
->stmt
),
2892 mark_maybe_modified
, repr
, &visited
);
2893 if (repr
->grp_maybe_modified
)
2896 BITMAP_FREE (visited
);
2901 /* Propagate distances in bb_dereferences in the opposite direction than the
2902 control flow edges, in each step storing the maximum of the current value
2903 and the minimum of all successors. These steps are repeated until the table
2904 stabilizes. Note that BBs which might terminate the functions (according to
2905 final_bbs bitmap) never updated in this way. */
2908 propagate_dereference_distances (void)
2910 VEC (basic_block
, heap
) *queue
;
2913 queue
= VEC_alloc (basic_block
, heap
, last_basic_block_for_function (cfun
));
2914 VEC_quick_push (basic_block
, queue
, ENTRY_BLOCK_PTR
);
2917 VEC_quick_push (basic_block
, queue
, bb
);
2921 while (!VEC_empty (basic_block
, queue
))
2925 bool change
= false;
2928 bb
= VEC_pop (basic_block
, queue
);
2931 if (bitmap_bit_p (final_bbs
, bb
->index
))
2934 for (i
= 0; i
< func_param_count
; i
++)
2936 int idx
= bb
->index
* func_param_count
+ i
;
2938 HOST_WIDE_INT inh
= 0;
2940 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2942 int succ_idx
= e
->dest
->index
* func_param_count
+ i
;
2944 if (e
->src
== EXIT_BLOCK_PTR
)
2950 inh
= bb_dereferences
[succ_idx
];
2952 else if (bb_dereferences
[succ_idx
] < inh
)
2953 inh
= bb_dereferences
[succ_idx
];
2956 if (!first
&& bb_dereferences
[idx
] < inh
)
2958 bb_dereferences
[idx
] = inh
;
2963 if (change
&& !bitmap_bit_p (final_bbs
, bb
->index
))
2964 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2969 e
->src
->aux
= e
->src
;
2970 VEC_quick_push (basic_block
, queue
, e
->src
);
2974 VEC_free (basic_block
, heap
, queue
);
2977 /* Dump a dereferences TABLE with heading STR to file F. */
2980 dump_dereferences_table (FILE *f
, const char *str
, HOST_WIDE_INT
*table
)
2984 fprintf (dump_file
, str
);
2985 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
2987 fprintf (f
, "%4i %i ", bb
->index
, bitmap_bit_p (final_bbs
, bb
->index
));
2988 if (bb
!= EXIT_BLOCK_PTR
)
2991 for (i
= 0; i
< func_param_count
; i
++)
2993 int idx
= bb
->index
* func_param_count
+ i
;
2994 fprintf (f
, " %4" HOST_WIDE_INT_PRINT
"d", table
[idx
]);
2999 fprintf (dump_file
, "\n");
3002 /* Determine what (parts of) parameters passed by reference that are not
3003 assigned to are not certainly dereferenced in this function and thus the
3004 dereferencing cannot be safely moved to the caller without potentially
3005 introducing a segfault. Mark such REPRESENTATIVES as
3006 grp_not_necessarilly_dereferenced.
3008 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3009 part is calculated rather than simple booleans are calculated for each
3010 pointer parameter to handle cases when only a fraction of the whole
3011 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3014 The maximum dereference distances for each pointer parameter and BB are
3015 already stored in bb_dereference. This routine simply propagates these
3016 values upwards by propagate_dereference_distances and then compares the
3017 distances of individual parameters in the ENTRY BB to the equivalent
3018 distances of each representative of a (fraction of a) parameter. */
3021 analyze_caller_dereference_legality (VEC (access_p
, heap
) *representatives
)
3025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3026 dump_dereferences_table (dump_file
,
3027 "Dereference table before propagation:\n",
3030 propagate_dereference_distances ();
3032 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3033 dump_dereferences_table (dump_file
,
3034 "Dereference table after propagation:\n",
3037 for (i
= 0; i
< func_param_count
; i
++)
3039 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3040 int idx
= ENTRY_BLOCK_PTR
->index
* func_param_count
+ i
;
3042 if (!repr
|| no_accesses_p (repr
))
3047 if ((repr
->offset
+ repr
->size
) > bb_dereferences
[idx
])
3048 repr
->grp_not_necessarilly_dereferenced
= 1;
3049 repr
= repr
->next_grp
;
3055 /* Return the representative access for the parameter declaration PARM if it is
3056 a scalar passed by reference which is not written to and the pointer value
3057 is not used directly. Thus, if it is legal to dereference it in the caller
3058 and we can rule out modifications through aliases, such parameter should be
3059 turned into one passed by value. Return NULL otherwise. */
3061 static struct access
*
3062 unmodified_by_ref_scalar_representative (tree parm
)
3064 int i
, access_count
;
3065 struct access
*repr
;
3066 VEC (access_p
, heap
) *access_vec
;
3068 access_vec
= get_base_access_vector (parm
);
3069 gcc_assert (access_vec
);
3070 repr
= VEC_index (access_p
, access_vec
, 0);
3073 repr
->group_representative
= repr
;
3075 access_count
= VEC_length (access_p
, access_vec
);
3076 for (i
= 1; i
< access_count
; i
++)
3078 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
3081 access
->group_representative
= repr
;
3082 access
->next_sibling
= repr
->next_sibling
;
3083 repr
->next_sibling
= access
;
3087 repr
->grp_scalar_ptr
= 1;
3091 /* Return true iff this access precludes IPA-SRA of the parameter it is
3095 access_precludes_ipa_sra_p (struct access
*access
)
3097 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3098 is incompatible assign in a call statement (and possibly even in asm
3099 statements). This can be relaxed by using a new temporary but only for
3100 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3101 intraprocedural SRA we deal with this by keeping the old aggregate around,
3102 something we cannot do in IPA-SRA.) */
3104 && (is_gimple_call (access
->stmt
)
3105 || gimple_code (access
->stmt
) == GIMPLE_ASM
))
3112 /* Sort collected accesses for parameter PARM, identify representatives for
3113 each accessed region and link them together. Return NULL if there are
3114 different but overlapping accesses, return the special ptr value meaning
3115 there are no accesses for this parameter if that is the case and return the
3116 first representative otherwise. Set *RO_GRP if there is a group of accesses
3117 with only read (i.e. no write) accesses. */
3119 static struct access
*
3120 splice_param_accesses (tree parm
, bool *ro_grp
)
3122 int i
, j
, access_count
, group_count
;
3123 int agg_size
, total_size
= 0;
3124 struct access
*access
, *res
, **prev_acc_ptr
= &res
;
3125 VEC (access_p
, heap
) *access_vec
;
3127 access_vec
= get_base_access_vector (parm
);
3129 return &no_accesses_representant
;
3130 access_count
= VEC_length (access_p
, access_vec
);
3132 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
3133 compare_access_positions
);
3138 while (i
< access_count
)
3141 access
= VEC_index (access_p
, access_vec
, i
);
3142 modification
= access
->write
;
3143 if (access_precludes_ipa_sra_p (access
))
3146 /* Access is about to become group representative unless we find some
3147 nasty overlap which would preclude us from breaking this parameter
3151 while (j
< access_count
)
3153 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
3154 if (ac2
->offset
!= access
->offset
)
3156 /* All or nothing law for parameters. */
3157 if (access
->offset
+ access
->size
> ac2
->offset
)
3162 else if (ac2
->size
!= access
->size
)
3165 if (access_precludes_ipa_sra_p (ac2
))
3168 modification
|= ac2
->write
;
3169 ac2
->group_representative
= access
;
3170 ac2
->next_sibling
= access
->next_sibling
;
3171 access
->next_sibling
= ac2
;
3176 access
->grp_maybe_modified
= modification
;
3179 *prev_acc_ptr
= access
;
3180 prev_acc_ptr
= &access
->next_grp
;
3181 total_size
+= access
->size
;
3185 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3186 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3188 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3189 if (total_size
>= agg_size
)
3192 gcc_assert (group_count
> 0);
3196 /* Decide whether parameters with representative accesses given by REPR should
3197 be reduced into components. */
3200 decide_one_param_reduction (struct access
*repr
)
3202 int total_size
, cur_parm_size
, agg_size
, new_param_count
, parm_size_limit
;
3207 cur_parm_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3208 gcc_assert (cur_parm_size
> 0);
3210 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3213 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3218 agg_size
= cur_parm_size
;
3224 fprintf (dump_file
, "Evaluating PARAM group sizes for ");
3225 print_generic_expr (dump_file
, parm
, 0);
3226 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (parm
));
3227 for (acc
= repr
; acc
; acc
= acc
->next_grp
)
3228 dump_access (dump_file
, acc
, true);
3232 new_param_count
= 0;
3234 for (; repr
; repr
= repr
->next_grp
)
3236 gcc_assert (parm
== repr
->base
);
3239 if (!by_ref
|| (!repr
->grp_maybe_modified
3240 && !repr
->grp_not_necessarilly_dereferenced
))
3241 total_size
+= repr
->size
;
3243 total_size
+= cur_parm_size
;
3246 gcc_assert (new_param_count
> 0);
3248 if (optimize_function_for_size_p (cfun
))
3249 parm_size_limit
= cur_parm_size
;
3251 parm_size_limit
= (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR
)
3254 if (total_size
< agg_size
3255 && total_size
<= parm_size_limit
)
3258 fprintf (dump_file
, " ....will be split into %i components\n",
3260 return new_param_count
;
3266 /* The order of the following enums is important, we need to do extra work for
3267 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3268 enum ipa_splicing_result
{ NO_GOOD_ACCESS
, UNUSED_PARAMS
, BY_VAL_ACCESSES
,
3269 MODIF_BY_REF_ACCESSES
, UNMODIF_BY_REF_ACCESSES
};
3271 /* Identify representatives of all accesses to all candidate parameters for
3272 IPA-SRA. Return result based on what representatives have been found. */
3274 static enum ipa_splicing_result
3275 splice_all_param_accesses (VEC (access_p
, heap
) **representatives
)
3277 enum ipa_splicing_result result
= NO_GOOD_ACCESS
;
3279 struct access
*repr
;
3281 *representatives
= VEC_alloc (access_p
, heap
, func_param_count
);
3283 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3285 parm
= TREE_CHAIN (parm
))
3287 if (is_unused_scalar_param (parm
))
3289 VEC_quick_push (access_p
, *representatives
,
3290 &no_accesses_representant
);
3291 if (result
== NO_GOOD_ACCESS
)
3292 result
= UNUSED_PARAMS
;
3294 else if (POINTER_TYPE_P (TREE_TYPE (parm
))
3295 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm
)))
3296 && bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3298 repr
= unmodified_by_ref_scalar_representative (parm
);
3299 VEC_quick_push (access_p
, *representatives
, repr
);
3301 result
= UNMODIF_BY_REF_ACCESSES
;
3303 else if (bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3305 bool ro_grp
= false;
3306 repr
= splice_param_accesses (parm
, &ro_grp
);
3307 VEC_quick_push (access_p
, *representatives
, repr
);
3309 if (repr
&& !no_accesses_p (repr
))
3311 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3314 result
= UNMODIF_BY_REF_ACCESSES
;
3315 else if (result
< MODIF_BY_REF_ACCESSES
)
3316 result
= MODIF_BY_REF_ACCESSES
;
3318 else if (result
< BY_VAL_ACCESSES
)
3319 result
= BY_VAL_ACCESSES
;
3321 else if (no_accesses_p (repr
) && (result
== NO_GOOD_ACCESS
))
3322 result
= UNUSED_PARAMS
;
3325 VEC_quick_push (access_p
, *representatives
, NULL
);
3328 if (result
== NO_GOOD_ACCESS
)
3330 VEC_free (access_p
, heap
, *representatives
);
3331 *representatives
= NULL
;
3332 return NO_GOOD_ACCESS
;
3338 /* Return the index of BASE in PARMS. Abort if it is not found. */
3341 get_param_index (tree base
, VEC(tree
, heap
) *parms
)
3345 len
= VEC_length (tree
, parms
);
3346 for (i
= 0; i
< len
; i
++)
3347 if (VEC_index (tree
, parms
, i
) == base
)
3352 /* Convert the decisions made at the representative level into compact
3353 parameter adjustments. REPRESENTATIVES are pointers to first
3354 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3355 final number of adjustments. */
3357 static ipa_parm_adjustment_vec
3358 turn_representatives_into_adjustments (VEC (access_p
, heap
) *representatives
,
3359 int adjustments_count
)
3361 VEC (tree
, heap
) *parms
;
3362 ipa_parm_adjustment_vec adjustments
;
3366 gcc_assert (adjustments_count
> 0);
3367 parms
= ipa_get_vector_of_formal_parms (current_function_decl
);
3368 adjustments
= VEC_alloc (ipa_parm_adjustment_t
, heap
, adjustments_count
);
3369 parm
= DECL_ARGUMENTS (current_function_decl
);
3370 for (i
= 0; i
< func_param_count
; i
++, parm
= TREE_CHAIN (parm
))
3372 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3374 if (!repr
|| no_accesses_p (repr
))
3376 struct ipa_parm_adjustment
*adj
;
3378 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3379 memset (adj
, 0, sizeof (*adj
));
3380 adj
->base_index
= get_param_index (parm
, parms
);
3383 adj
->copy_param
= 1;
3385 adj
->remove_param
= 1;
3389 struct ipa_parm_adjustment
*adj
;
3390 int index
= get_param_index (parm
, parms
);
3392 for (; repr
; repr
= repr
->next_grp
)
3394 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3395 memset (adj
, 0, sizeof (*adj
));
3396 gcc_assert (repr
->base
== parm
);
3397 adj
->base_index
= index
;
3398 adj
->base
= repr
->base
;
3399 adj
->type
= repr
->type
;
3400 adj
->offset
= repr
->offset
;
3401 adj
->by_ref
= (POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3402 && (repr
->grp_maybe_modified
3403 || repr
->grp_not_necessarilly_dereferenced
));
3408 VEC_free (tree
, heap
, parms
);
3412 /* Analyze the collected accesses and produce a plan what to do with the
3413 parameters in the form of adjustments, NULL meaning nothing. */
3415 static ipa_parm_adjustment_vec
3416 analyze_all_param_acesses (void)
3418 enum ipa_splicing_result repr_state
;
3419 bool proceed
= false;
3420 int i
, adjustments_count
= 0;
3421 VEC (access_p
, heap
) *representatives
;
3422 ipa_parm_adjustment_vec adjustments
;
3424 repr_state
= splice_all_param_accesses (&representatives
);
3425 if (repr_state
== NO_GOOD_ACCESS
)
3428 /* If there are any parameters passed by reference which are not modified
3429 directly, we need to check whether they can be modified indirectly. */
3430 if (repr_state
== UNMODIF_BY_REF_ACCESSES
)
3432 analyze_caller_dereference_legality (representatives
);
3433 analyze_modified_params (representatives
);
3436 for (i
= 0; i
< func_param_count
; i
++)
3438 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3440 if (repr
&& !no_accesses_p (repr
))
3442 if (repr
->grp_scalar_ptr
)
3444 adjustments_count
++;
3445 if (repr
->grp_not_necessarilly_dereferenced
3446 || repr
->grp_maybe_modified
)
3447 VEC_replace (access_p
, representatives
, i
, NULL
);
3451 sra_stats
.scalar_by_ref_to_by_val
++;
3456 int new_components
= decide_one_param_reduction (repr
);
3458 if (new_components
== 0)
3460 VEC_replace (access_p
, representatives
, i
, NULL
);
3461 adjustments_count
++;
3465 adjustments_count
+= new_components
;
3466 sra_stats
.aggregate_params_reduced
++;
3467 sra_stats
.param_reductions_created
+= new_components
;
3474 if (no_accesses_p (repr
))
3477 sra_stats
.deleted_unused_parameters
++;
3479 adjustments_count
++;
3483 if (!proceed
&& dump_file
)
3484 fprintf (dump_file
, "NOT proceeding to change params.\n");
3487 adjustments
= turn_representatives_into_adjustments (representatives
,
3492 VEC_free (access_p
, heap
, representatives
);
3496 /* If a parameter replacement identified by ADJ does not yet exist in the form
3497 of declaration, create it and record it, otherwise return the previously
3501 get_replaced_param_substitute (struct ipa_parm_adjustment
*adj
)
3504 if (!adj
->new_ssa_base
)
3506 char *pretty_name
= make_fancy_name (adj
->base
);
3508 repl
= create_tmp_var (TREE_TYPE (adj
->base
), "ISR");
3509 if (TREE_CODE (TREE_TYPE (repl
)) == COMPLEX_TYPE
3510 || TREE_CODE (TREE_TYPE (repl
)) == VECTOR_TYPE
)
3511 DECL_GIMPLE_REG_P (repl
) = 1;
3512 DECL_NAME (repl
) = get_identifier (pretty_name
);
3513 obstack_free (&name_obstack
, pretty_name
);
3516 add_referenced_var (repl
);
3517 adj
->new_ssa_base
= repl
;
3520 repl
= adj
->new_ssa_base
;
3524 /* Find the first adjustment for a particular parameter BASE in a vector of
3525 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3528 static struct ipa_parm_adjustment
*
3529 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments
, tree base
)
3533 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3534 for (i
= 0; i
< len
; i
++)
3536 struct ipa_parm_adjustment
*adj
;
3538 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3539 if (!adj
->copy_param
&& adj
->base
== base
)
3546 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3547 parameter which is to be removed because its value is not used, replace the
3548 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3549 uses too and return true (update_stmt is then issued for the statement by
3550 the caller). DATA is a pointer to an adjustments vector. */
3553 replace_removed_params_ssa_names (gimple stmt
, void *data
)
3555 VEC (ipa_parm_adjustment_t
, heap
) *adjustments
;
3556 struct ipa_parm_adjustment
*adj
;
3557 tree lhs
, decl
, repl
, name
;
3559 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3560 if (gimple_code (stmt
) == GIMPLE_PHI
)
3561 lhs
= gimple_phi_result (stmt
);
3562 else if (is_gimple_assign (stmt
))
3563 lhs
= gimple_assign_lhs (stmt
);
3564 else if (is_gimple_call (stmt
))
3565 lhs
= gimple_call_lhs (stmt
);
3569 if (TREE_CODE (lhs
) != SSA_NAME
)
3571 decl
= SSA_NAME_VAR (lhs
);
3572 if (TREE_CODE (decl
) != PARM_DECL
)
3575 adj
= get_adjustment_for_base (adjustments
, decl
);
3579 repl
= get_replaced_param_substitute (adj
);
3580 name
= make_ssa_name (repl
, stmt
);
3584 fprintf (dump_file
, "replacing an SSA name of a removed param ");
3585 print_generic_expr (dump_file
, lhs
, 0);
3586 fprintf (dump_file
, " with ");
3587 print_generic_expr (dump_file
, name
, 0);
3588 fprintf (dump_file
, "\n");
3591 if (is_gimple_assign (stmt
))
3592 gimple_assign_set_lhs (stmt
, name
);
3593 else if (is_gimple_call (stmt
))
3594 gimple_call_set_lhs (stmt
, name
);
3596 gimple_phi_set_result (stmt
, name
);
3598 replace_uses_by (lhs
, name
);
3602 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3603 expression *EXPR should be replaced by a reduction of a parameter, do so.
3604 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3605 whether the function should care about type incompatibility the current and
3606 new expressions. If it is true, the function will leave incompatibility
3607 issues to the caller.
3609 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3610 a write (LHS) expression. */
3613 sra_ipa_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
3614 bool dont_convert
, void *data
)
3616 ipa_parm_adjustment_vec adjustments
;
3618 struct ipa_parm_adjustment
*adj
, *cand
= NULL
;
3619 HOST_WIDE_INT offset
, size
, max_size
;
3622 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3623 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3625 if (TREE_CODE (*expr
) == BIT_FIELD_REF
3626 || TREE_CODE (*expr
) == IMAGPART_EXPR
3627 || TREE_CODE (*expr
) == REALPART_EXPR
)
3629 expr
= &TREE_OPERAND (*expr
, 0);
3630 dont_convert
= false;
3633 base
= get_ref_base_and_extent (*expr
, &offset
, &size
, &max_size
);
3634 if (!base
|| size
== -1 || max_size
== -1)
3637 if (INDIRECT_REF_P (base
))
3638 base
= TREE_OPERAND (base
, 0);
3640 base
= get_ssa_base_param (base
);
3641 if (!base
|| TREE_CODE (base
) != PARM_DECL
)
3644 for (i
= 0; i
< len
; i
++)
3646 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3648 if (adj
->base
== base
&&
3649 (adj
->offset
== offset
|| adj
->remove_param
))
3655 if (!cand
|| cand
->copy_param
|| cand
->remove_param
)
3661 src
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (cand
->reduction
)),
3663 folded
= gimple_fold_indirect_ref (src
);
3668 src
= cand
->reduction
;
3670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3672 fprintf (dump_file
, "About to replace expr ");
3673 print_generic_expr (dump_file
, *expr
, 0);
3674 fprintf (dump_file
, " with ");
3675 print_generic_expr (dump_file
, src
, 0);
3676 fprintf (dump_file
, "\n");
3680 && !useless_type_conversion_p (TREE_TYPE (*expr
), cand
->type
))
3682 tree vce
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (*expr
), src
);
3690 /* Callback for scan_function to process assign statements. Performs
3691 essentially the same function like sra_ipa_modify_expr. */
3693 static enum scan_assign_result
3694 sra_ipa_modify_assign (gimple
*stmt_ptr
, gimple_stmt_iterator
*gsi
, void *data
)
3696 gimple stmt
= *stmt_ptr
;
3697 tree
*lhs_p
, *rhs_p
;
3700 if (!gimple_assign_single_p (stmt
))
3703 rhs_p
= gimple_assign_rhs1_ptr (stmt
);
3704 lhs_p
= gimple_assign_lhs_ptr (stmt
);
3706 any
= sra_ipa_modify_expr (rhs_p
, gsi
, true, data
);
3707 any
|= sra_ipa_modify_expr (lhs_p
, gsi
, true, data
);
3710 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p
), TREE_TYPE (*rhs_p
)))
3712 location_t loc
= gimple_location (stmt
);
3713 tree vce
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
3714 TREE_TYPE (*lhs_p
), *rhs_p
);
3715 tree tmp
= force_gimple_operand_gsi (gsi
, vce
, true, NULL_TREE
,
3716 true, GSI_SAME_STMT
);
3718 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
3721 return SRA_SA_PROCESSED
;
3727 /* Call gimple_debug_bind_reset_value on all debug statements describing
3728 gimple register parameters that are being removed or replaced. */
3731 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments
)
3735 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3736 for (i
= 0; i
< len
; i
++)
3738 struct ipa_parm_adjustment
*adj
;
3739 imm_use_iterator ui
;
3743 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3744 if (adj
->copy_param
|| !is_gimple_reg (adj
->base
))
3746 name
= gimple_default_def (cfun
, adj
->base
);
3749 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
3751 /* All other users must have been removed by scan_function. */
3752 gcc_assert (is_gimple_debug (stmt
));
3753 gimple_debug_bind_reset_value (stmt
);
3759 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3762 convert_callers (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3764 tree old_cur_fndecl
= current_function_decl
;
3765 struct cgraph_edge
*cs
;
3766 basic_block this_block
;
3767 bitmap recomputed_callers
= BITMAP_ALLOC (NULL
);
3769 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3771 current_function_decl
= cs
->caller
->decl
;
3772 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
3775 fprintf (dump_file
, "Adjusting call (%i -> %i) %s -> %s\n",
3776 cs
->caller
->uid
, cs
->callee
->uid
,
3777 cgraph_node_name (cs
->caller
),
3778 cgraph_node_name (cs
->callee
));
3780 ipa_modify_call_arguments (cs
, cs
->call_stmt
, adjustments
);
3785 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3786 if (!bitmap_bit_p (recomputed_callers
, cs
->caller
->uid
))
3788 compute_inline_parameters (cs
->caller
);
3789 bitmap_set_bit (recomputed_callers
, cs
->caller
->uid
);
3791 BITMAP_FREE (recomputed_callers
);
3793 current_function_decl
= old_cur_fndecl
;
3794 FOR_EACH_BB (this_block
)
3796 gimple_stmt_iterator gsi
;
3798 for (gsi
= gsi_start_bb (this_block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3800 gimple stmt
= gsi_stmt (gsi
);
3801 if (gimple_code (stmt
) == GIMPLE_CALL
3802 && gimple_call_fndecl (stmt
) == node
->decl
)
3805 fprintf (dump_file
, "Adjusting recursive call");
3806 ipa_modify_call_arguments (NULL
, stmt
, adjustments
);
3814 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3815 as given in ADJUSTMENTS. */
3818 modify_function (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3820 ipa_modify_formal_parameters (current_function_decl
, adjustments
, "ISRA");
3821 scan_function (sra_ipa_modify_expr
, sra_ipa_modify_assign
,
3822 replace_removed_params_ssa_names
, false, adjustments
);
3823 sra_ipa_reset_debug_stmts (adjustments
);
3824 convert_callers (node
, adjustments
);
3825 cgraph_make_node_local (node
);
3829 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3830 attributes, return true otherwise. NODE is the cgraph node of the current
3834 ipa_sra_preliminary_function_checks (struct cgraph_node
*node
)
3836 if (!cgraph_node_can_be_local_p (node
))
3839 fprintf (dump_file
, "Function not local to this compilation unit.\n");
3843 if (DECL_VIRTUAL_P (current_function_decl
))
3846 fprintf (dump_file
, "Function is a virtual method.\n");
3850 if ((DECL_COMDAT (node
->decl
) || DECL_EXTERNAL (node
->decl
))
3851 && node
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
3854 fprintf (dump_file
, "Function too big to be made truly local.\n");
3862 "Function has no callers in this compilation unit.\n");
3869 fprintf (dump_file
, "Function uses stdarg. \n");
3876 /* Perform early interprocedural SRA. */
3879 ipa_early_sra (void)
3881 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
3882 ipa_parm_adjustment_vec adjustments
;
3885 if (!ipa_sra_preliminary_function_checks (node
))
3889 sra_mode
= SRA_MODE_EARLY_IPA
;
3891 if (!find_param_candidates ())
3894 fprintf (dump_file
, "Function has no IPA-SRA candidates.\n");
3898 bb_dereferences
= XCNEWVEC (HOST_WIDE_INT
,
3900 * last_basic_block_for_function (cfun
));
3901 final_bbs
= BITMAP_ALLOC (NULL
);
3903 scan_function (build_access_from_expr
, build_accesses_from_assign
,
3905 if (encountered_apply_args
)
3908 fprintf (dump_file
, "Function calls __builtin_apply_args().\n");
3912 adjustments
= analyze_all_param_acesses ();
3916 ipa_dump_param_adjustments (dump_file
, adjustments
, current_function_decl
);
3918 modify_function (node
, adjustments
);
3919 VEC_free (ipa_parm_adjustment_t
, heap
, adjustments
);
3920 ret
= TODO_update_ssa
;
3922 statistics_counter_event (cfun
, "Unused parameters deleted",
3923 sra_stats
.deleted_unused_parameters
);
3924 statistics_counter_event (cfun
, "Scalar parameters converted to by-value",
3925 sra_stats
.scalar_by_ref_to_by_val
);
3926 statistics_counter_event (cfun
, "Aggregate parameters broken up",
3927 sra_stats
.aggregate_params_reduced
);
3928 statistics_counter_event (cfun
, "Aggregate parameter components created",
3929 sra_stats
.param_reductions_created
);
3932 BITMAP_FREE (final_bbs
);
3933 free (bb_dereferences
);
3935 sra_deinitialize ();
3939 /* Return if early ipa sra shall be performed. */
3941 ipa_early_sra_gate (void)
3943 return flag_ipa_sra
;
3946 struct gimple_opt_pass pass_early_ipa_sra
=
3950 "eipa_sra", /* name */
3951 ipa_early_sra_gate
, /* gate */
3952 ipa_early_sra
, /* execute */
3955 0, /* static_pass_number */
3956 TV_IPA_SRA
, /* tv_id */
3957 0, /* properties_required */
3958 0, /* properties_provided */
3959 0, /* properties_destroyed */
3960 0, /* todo_flags_start */
3961 TODO_dump_func
| TODO_dump_cgraph
/* todo_flags_finish */