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 /* Set when a scalar replacement should be created for this variable. We do
203 the decision and creation at different places because create_tmp_var
204 cannot be called from within FOR_EACH_REFERENCED_VAR. */
205 unsigned grp_to_be_replaced
: 1;
207 /* Is it possible that the group refers to data which might be (directly or
208 otherwise) modified? */
209 unsigned grp_maybe_modified
: 1;
211 /* Set when this is a representative of a pointer to scalar (i.e. by
212 reference) parameter which we consider for turning into a plain scalar
213 (i.e. a by value parameter). */
214 unsigned grp_scalar_ptr
: 1;
216 /* Set when we discover that this pointer is not safe to dereference in the
218 unsigned grp_not_necessarilly_dereferenced
: 1;
221 typedef struct access
*access_p
;
223 DEF_VEC_P (access_p
);
224 DEF_VEC_ALLOC_P (access_p
, heap
);
226 /* Alloc pool for allocating access structures. */
227 static alloc_pool access_pool
;
229 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
230 are used to propagate subaccesses from rhs to lhs as long as they don't
231 conflict with what is already there. */
234 struct access
*lacc
, *racc
;
235 struct assign_link
*next
;
238 /* Alloc pool for allocating assign link structures. */
239 static alloc_pool link_pool
;
241 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
242 static struct pointer_map_t
*base_access_vec
;
244 /* Bitmap of candidates. */
245 static bitmap candidate_bitmap
;
247 /* Obstack for creation of fancy names. */
248 static struct obstack name_obstack
;
250 /* Head of a linked list of accesses that need to have its subaccesses
251 propagated to their assignment counterparts. */
252 static struct access
*work_queue_head
;
254 /* Number of parameters of the analyzed function when doing early ipa SRA. */
255 static int func_param_count
;
257 /* scan_function sets the following to true if it encounters a call to
258 __builtin_apply_args. */
259 static bool encountered_apply_args
;
261 /* This is a table in which for each basic block and parameter there is a
262 distance (offset + size) in that parameter which is dereferenced and
263 accessed in that BB. */
264 static HOST_WIDE_INT
*bb_dereferences
;
265 /* Bitmap of BBs that can cause the function to "stop" progressing by
266 returning, throwing externally, looping infinitely or calling a function
267 which might abort etc.. */
268 static bitmap final_bbs
;
270 /* Representative of no accesses at all. */
271 static struct access no_accesses_representant
;
273 /* Predicate to test the special value. */
276 no_accesses_p (struct access
*access
)
278 return access
== &no_accesses_representant
;
281 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
282 representative fields are dumped, otherwise those which only describe the
283 individual access are. */
287 /* Number of processed aggregates is readily available in
288 analyze_all_variable_accesses and so is not stored here. */
290 /* Number of created scalar replacements. */
293 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
297 /* Number of statements created by generate_subtree_copies. */
300 /* Number of statements created by load_assign_lhs_subreplacements. */
303 /* Number of times sra_modify_assign has deleted a statement. */
306 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
307 RHS reparately due to type conversions or nonexistent matching
309 int separate_lhs_rhs_handling
;
311 /* Number of parameters that were removed because they were unused. */
312 int deleted_unused_parameters
;
314 /* Number of scalars passed as parameters by reference that have been
315 converted to be passed by value. */
316 int scalar_by_ref_to_by_val
;
318 /* Number of aggregate parameters that were replaced by one or more of their
320 int aggregate_params_reduced
;
322 /* Numbber of components created when splitting aggregate parameters. */
323 int param_reductions_created
;
327 dump_access (FILE *f
, struct access
*access
, bool grp
)
329 fprintf (f
, "access { ");
330 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
331 print_generic_expr (f
, access
->base
, 0);
332 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
333 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
334 fprintf (f
, ", expr = ");
335 print_generic_expr (f
, access
->expr
, 0);
336 fprintf (f
, ", type = ");
337 print_generic_expr (f
, access
->type
, 0);
339 fprintf (f
, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
340 "grp_covered = %d, grp_unscalarizable_region = %d, "
341 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
342 "grp_to_be_replaced = %d\n grp_maybe_modified = %d, "
343 "grp_not_necessarilly_dereferenced = %d\n",
344 access
->grp_write
, access
->grp_read
, access
->grp_hint
,
345 access
->grp_covered
, access
->grp_unscalarizable_region
,
346 access
->grp_unscalarized_data
, access
->grp_partial_lhs
,
347 access
->grp_to_be_replaced
, access
->grp_maybe_modified
,
348 access
->grp_not_necessarilly_dereferenced
);
350 fprintf (f
, ", write = %d, grp_partial_lhs = %d\n", access
->write
,
351 access
->grp_partial_lhs
);
354 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
357 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
363 for (i
= 0; i
< level
; i
++)
364 fputs ("* ", dump_file
);
366 dump_access (f
, access
, true);
368 if (access
->first_child
)
369 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
371 access
= access
->next_sibling
;
376 /* Dump all access trees for a variable, given the pointer to the first root in
380 dump_access_tree (FILE *f
, struct access
*access
)
382 for (; access
; access
= access
->next_grp
)
383 dump_access_tree_1 (f
, access
, 0);
386 /* Return true iff ACC is non-NULL and has subaccesses. */
389 access_has_children_p (struct access
*acc
)
391 return acc
&& acc
->first_child
;
394 /* Return a vector of pointers to accesses for the variable given in BASE or
395 NULL if there is none. */
397 static VEC (access_p
, heap
) *
398 get_base_access_vector (tree base
)
402 slot
= pointer_map_contains (base_access_vec
, base
);
406 return *(VEC (access_p
, heap
) **) slot
;
409 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
410 in ACCESS. Return NULL if it cannot be found. */
412 static struct access
*
413 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
416 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
418 struct access
*child
= access
->first_child
;
420 while (child
&& (child
->offset
+ child
->size
<= offset
))
421 child
= child
->next_sibling
;
428 /* Return the first group representative for DECL or NULL if none exists. */
430 static struct access
*
431 get_first_repr_for_decl (tree base
)
433 VEC (access_p
, heap
) *access_vec
;
435 access_vec
= get_base_access_vector (base
);
439 return VEC_index (access_p
, access_vec
, 0);
442 /* Find an access representative for the variable BASE and given OFFSET and
443 SIZE. Requires that access trees have already been built. Return NULL if
444 it cannot be found. */
446 static struct access
*
447 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
450 struct access
*access
;
452 access
= get_first_repr_for_decl (base
);
453 while (access
&& (access
->offset
+ access
->size
<= offset
))
454 access
= access
->next_grp
;
458 return find_access_in_subtree (access
, offset
, size
);
461 /* Add LINK to the linked list of assign links of RACC. */
463 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
465 gcc_assert (link
->racc
== racc
);
467 if (!racc
->first_link
)
469 gcc_assert (!racc
->last_link
);
470 racc
->first_link
= link
;
473 racc
->last_link
->next
= link
;
475 racc
->last_link
= link
;
479 /* Move all link structures in their linked list in OLD_RACC to the linked list
482 relink_to_new_repr (struct access
*new_racc
, struct access
*old_racc
)
484 if (!old_racc
->first_link
)
486 gcc_assert (!old_racc
->last_link
);
490 if (new_racc
->first_link
)
492 gcc_assert (!new_racc
->last_link
->next
);
493 gcc_assert (!old_racc
->last_link
|| !old_racc
->last_link
->next
);
495 new_racc
->last_link
->next
= old_racc
->first_link
;
496 new_racc
->last_link
= old_racc
->last_link
;
500 gcc_assert (!new_racc
->last_link
);
502 new_racc
->first_link
= old_racc
->first_link
;
503 new_racc
->last_link
= old_racc
->last_link
;
505 old_racc
->first_link
= old_racc
->last_link
= NULL
;
508 /* Add ACCESS to the work queue (which is actually a stack). */
511 add_access_to_work_queue (struct access
*access
)
513 if (!access
->grp_queued
)
515 gcc_assert (!access
->next_queued
);
516 access
->next_queued
= work_queue_head
;
517 access
->grp_queued
= 1;
518 work_queue_head
= access
;
522 /* Pop an access from the work queue, and return it, assuming there is one. */
524 static struct access
*
525 pop_access_from_work_queue (void)
527 struct access
*access
= work_queue_head
;
529 work_queue_head
= access
->next_queued
;
530 access
->next_queued
= NULL
;
531 access
->grp_queued
= 0;
536 /* Allocate necessary structures. */
539 sra_initialize (void)
541 candidate_bitmap
= BITMAP_ALLOC (NULL
);
542 gcc_obstack_init (&name_obstack
);
543 access_pool
= create_alloc_pool ("SRA accesses", sizeof (struct access
), 16);
544 link_pool
= create_alloc_pool ("SRA links", sizeof (struct assign_link
), 16);
545 base_access_vec
= pointer_map_create ();
546 memset (&sra_stats
, 0, sizeof (sra_stats
));
547 encountered_apply_args
= false;
550 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
553 delete_base_accesses (const void *key ATTRIBUTE_UNUSED
, void **value
,
554 void *data ATTRIBUTE_UNUSED
)
556 VEC (access_p
, heap
) *access_vec
;
557 access_vec
= (VEC (access_p
, heap
) *) *value
;
558 VEC_free (access_p
, heap
, access_vec
);
563 /* Deallocate all general structures. */
566 sra_deinitialize (void)
568 BITMAP_FREE (candidate_bitmap
);
569 free_alloc_pool (access_pool
);
570 free_alloc_pool (link_pool
);
571 obstack_free (&name_obstack
, NULL
);
573 pointer_map_traverse (base_access_vec
, delete_base_accesses
, NULL
);
574 pointer_map_destroy (base_access_vec
);
577 /* Remove DECL from candidates for SRA and write REASON to the dump file if
580 disqualify_candidate (tree decl
, const char *reason
)
582 bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
));
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
586 fprintf (dump_file
, "! Disqualifying ");
587 print_generic_expr (dump_file
, decl
, 0);
588 fprintf (dump_file
, " - %s\n", reason
);
592 /* Return true iff the type contains a field or an element which does not allow
596 type_internals_preclude_sra_p (tree type
)
601 switch (TREE_CODE (type
))
605 case QUAL_UNION_TYPE
:
606 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
607 if (TREE_CODE (fld
) == FIELD_DECL
)
609 tree ft
= TREE_TYPE (fld
);
611 if (TREE_THIS_VOLATILE (fld
)
612 || !DECL_FIELD_OFFSET (fld
) || !DECL_SIZE (fld
)
613 || !host_integerp (DECL_FIELD_OFFSET (fld
), 1)
614 || !host_integerp (DECL_SIZE (fld
), 1))
617 if (AGGREGATE_TYPE_P (ft
)
618 && type_internals_preclude_sra_p (ft
))
625 et
= TREE_TYPE (type
);
627 if (AGGREGATE_TYPE_P (et
))
628 return type_internals_preclude_sra_p (et
);
637 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
638 base variable if it is. Return T if it is not an SSA_NAME. */
641 get_ssa_base_param (tree t
)
643 if (TREE_CODE (t
) == SSA_NAME
)
645 if (SSA_NAME_IS_DEFAULT_DEF (t
))
646 return SSA_NAME_VAR (t
);
653 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
654 belongs to, unless the BB has already been marked as a potentially
658 mark_parm_dereference (tree base
, HOST_WIDE_INT dist
, gimple stmt
)
660 basic_block bb
= gimple_bb (stmt
);
661 int idx
, parm_index
= 0;
664 if (bitmap_bit_p (final_bbs
, bb
->index
))
667 for (parm
= DECL_ARGUMENTS (current_function_decl
);
668 parm
&& parm
!= base
;
669 parm
= TREE_CHAIN (parm
))
672 gcc_assert (parm_index
< func_param_count
);
674 idx
= bb
->index
* func_param_count
+ parm_index
;
675 if (bb_dereferences
[idx
] < dist
)
676 bb_dereferences
[idx
] = dist
;
679 /* Create and insert access for EXPR. Return created access, or NULL if it is
682 static struct access
*
683 create_access (tree expr
, gimple stmt
, bool write
)
685 struct access
*access
;
687 VEC (access_p
,heap
) *vec
;
688 HOST_WIDE_INT offset
, size
, max_size
;
690 bool ptr
, unscalarizable_region
= false;
692 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
694 if (sra_mode
== SRA_MODE_EARLY_IPA
&& INDIRECT_REF_P (base
))
696 base
= get_ssa_base_param (TREE_OPERAND (base
, 0));
704 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
707 if (sra_mode
== SRA_MODE_EARLY_IPA
)
709 if (size
< 0 || size
!= max_size
)
711 disqualify_candidate (base
, "Encountered a variable sized access.");
714 if ((offset
% BITS_PER_UNIT
) != 0 || (size
% BITS_PER_UNIT
) != 0)
716 disqualify_candidate (base
,
717 "Encountered an acces not aligned to a byte.");
722 mark_parm_dereference (base
, offset
+ size
, stmt
);
726 if (size
!= max_size
)
729 unscalarizable_region
= true;
733 disqualify_candidate (base
, "Encountered an unconstrained access.");
738 access
= (struct access
*) pool_alloc (access_pool
);
739 memset (access
, 0, sizeof (struct access
));
742 access
->offset
= offset
;
745 access
->type
= TREE_TYPE (expr
);
746 access
->write
= write
;
747 access
->grp_unscalarizable_region
= unscalarizable_region
;
750 slot
= pointer_map_contains (base_access_vec
, base
);
752 vec
= (VEC (access_p
, heap
) *) *slot
;
754 vec
= VEC_alloc (access_p
, heap
, 32);
756 VEC_safe_push (access_p
, heap
, vec
, access
);
758 *((struct VEC (access_p
,heap
) **)
759 pointer_map_insert (base_access_vec
, base
)) = vec
;
765 /* Search the given tree for a declaration by skipping handled components and
766 exclude it from the candidates. */
769 disqualify_base_of_expr (tree t
, const char *reason
)
771 while (handled_component_p (t
))
772 t
= TREE_OPERAND (t
, 0);
774 if (sra_mode
== SRA_MODE_EARLY_IPA
)
776 if (INDIRECT_REF_P (t
))
777 t
= TREE_OPERAND (t
, 0);
778 t
= get_ssa_base_param (t
);
782 disqualify_candidate (t
, reason
);
785 /* Scan expression EXPR and create access structures for all accesses to
786 candidates for scalarization. Return the created access or NULL if none is
789 static struct access
*
790 build_access_from_expr_1 (tree
*expr_ptr
, gimple stmt
, bool write
)
792 struct access
*ret
= NULL
;
793 tree expr
= *expr_ptr
;
796 if (TREE_CODE (expr
) == BIT_FIELD_REF
797 || TREE_CODE (expr
) == IMAGPART_EXPR
798 || TREE_CODE (expr
) == REALPART_EXPR
)
800 expr
= TREE_OPERAND (expr
, 0);
806 /* We need to dive through V_C_Es in order to get the size of its parameter
807 and not the result type. Ada produces such statements. We are also
808 capable of handling the topmost V_C_E but not any of those buried in other
809 handled components. */
810 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
811 expr
= TREE_OPERAND (expr
, 0);
813 if (contains_view_convert_expr_p (expr
))
815 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
820 switch (TREE_CODE (expr
))
823 if (sra_mode
!= SRA_MODE_EARLY_IPA
)
831 case ARRAY_RANGE_REF
:
832 ret
= create_access (expr
, stmt
, write
);
839 if (write
&& partial_ref
&& ret
)
840 ret
->grp_partial_lhs
= 1;
845 /* Callback of scan_function. Scan expression EXPR and create access
846 structures for all accesses to candidates for scalarization. Return true if
847 any access has been inserted. */
850 build_access_from_expr (tree
*expr_ptr
,
851 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
, bool write
,
852 void *data ATTRIBUTE_UNUSED
)
854 return build_access_from_expr_1 (expr_ptr
, gsi_stmt (*gsi
), write
) != NULL
;
857 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
858 modes in which it matters, return true iff they have been disqualified. RHS
859 may be NULL, in that case ignore it. If we scalarize an aggregate in
860 intra-SRA we may need to add statements after each statement. This is not
861 possible if a statement unconditionally has to end the basic block. */
863 disqualify_ops_if_throwing_stmt (gimple stmt
, tree lhs
, tree rhs
)
865 if ((sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
866 && (stmt_can_throw_internal (stmt
) || stmt_ends_bb_p (stmt
)))
868 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
870 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
877 /* Result code for scan_assign callback for scan_function. */
878 enum scan_assign_result
{ SRA_SA_NONE
, /* nothing done for the stmt */
879 SRA_SA_PROCESSED
, /* stmt analyzed/changed */
880 SRA_SA_REMOVED
}; /* stmt redundant and eliminated */
883 /* Callback of scan_function. Scan expressions occuring in the statement
884 pointed to by STMT_EXPR, create access structures for all accesses to
885 candidates for scalarization and remove those candidates which occur in
886 statements or expressions that prevent them from being split apart. Return
887 true if any access has been inserted. */
889 static enum scan_assign_result
890 build_accesses_from_assign (gimple
*stmt_ptr
,
891 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
892 void *data ATTRIBUTE_UNUSED
)
894 gimple stmt
= *stmt_ptr
;
895 tree
*lhs_ptr
, *rhs_ptr
;
896 struct access
*lacc
, *racc
;
898 if (!gimple_assign_single_p (stmt
))
901 lhs_ptr
= gimple_assign_lhs_ptr (stmt
);
902 rhs_ptr
= gimple_assign_rhs1_ptr (stmt
);
904 if (disqualify_ops_if_throwing_stmt (stmt
, *lhs_ptr
, *rhs_ptr
))
907 racc
= build_access_from_expr_1 (rhs_ptr
, stmt
, false);
908 lacc
= build_access_from_expr_1 (lhs_ptr
, stmt
, true);
911 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
912 && !lacc
->grp_unscalarizable_region
913 && !racc
->grp_unscalarizable_region
914 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr
))
915 /* FIXME: Turn the following line into an assert after PR 40058 is
917 && lacc
->size
== racc
->size
918 && useless_type_conversion_p (lacc
->type
, racc
->type
))
920 struct assign_link
*link
;
922 link
= (struct assign_link
*) pool_alloc (link_pool
);
923 memset (link
, 0, sizeof (struct assign_link
));
928 add_link_to_rhs (racc
, link
);
931 return (lacc
|| racc
) ? SRA_SA_PROCESSED
: SRA_SA_NONE
;
934 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
935 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
938 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED
, tree op
,
939 void *data ATTRIBUTE_UNUSED
)
942 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
948 /* Scan function and look for interesting statements. Return true if any has
949 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
950 called on all expressions within statements except assign statements and
951 those deemed entirely unsuitable for some reason (all operands in such
952 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
953 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
954 called on assign statements and those call statements which have a lhs, it
955 can be NULL. ANALYSIS_STAGE is true when running in the analysis stage of a
956 pass and thus no statement is being modified. DATA is a pointer passed to
957 all callbacks. If any single callback returns true, this function also
958 returns true, otherwise it returns false. */
961 scan_function (bool (*scan_expr
) (tree
*, gimple_stmt_iterator
*, bool, void *),
962 enum scan_assign_result (*scan_assign
) (gimple
*,
963 gimple_stmt_iterator
*,
965 bool (*handle_ssa_defs
)(gimple
, void *),
966 bool analysis_stage
, void *data
)
968 gimple_stmt_iterator gsi
;
976 bool bb_changed
= false;
979 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
980 ret
|= handle_ssa_defs (gsi_stmt (gsi
), data
);
982 gsi
= gsi_start_bb (bb
);
983 while (!gsi_end_p (gsi
))
985 gimple stmt
= gsi_stmt (gsi
);
986 enum scan_assign_result assign_result
;
987 bool any
= false, deleted
= false;
989 if (analysis_stage
&& final_bbs
&& stmt_can_throw_external (stmt
))
990 bitmap_set_bit (final_bbs
, bb
->index
);
991 switch (gimple_code (stmt
))
994 t
= gimple_return_retval_ptr (stmt
);
996 any
|= scan_expr (t
, &gsi
, false, data
);
997 if (analysis_stage
&& final_bbs
)
998 bitmap_set_bit (final_bbs
, bb
->index
);
1002 assign_result
= scan_assign (&stmt
, &gsi
, data
);
1003 any
|= assign_result
== SRA_SA_PROCESSED
;
1004 deleted
= assign_result
== SRA_SA_REMOVED
;
1005 if (handle_ssa_defs
&& assign_result
!= SRA_SA_REMOVED
)
1006 any
|= handle_ssa_defs (stmt
, data
);
1010 /* Operands must be processed before the lhs. */
1011 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1013 tree
*argp
= gimple_call_arg_ptr (stmt
, i
);
1014 any
|= scan_expr (argp
, &gsi
, false, data
);
1019 tree dest
= gimple_call_fndecl (stmt
);
1020 int flags
= gimple_call_flags (stmt
);
1023 && DECL_BUILT_IN_CLASS (dest
) == BUILT_IN_NORMAL
1024 && DECL_FUNCTION_CODE (dest
) == BUILT_IN_APPLY_ARGS
)
1025 encountered_apply_args
= true;
1028 && (flags
& (ECF_CONST
| ECF_PURE
)) == 0)
1029 bitmap_set_bit (final_bbs
, bb
->index
);
1032 if (gimple_call_lhs (stmt
))
1034 tree
*lhs_ptr
= gimple_call_lhs_ptr (stmt
);
1036 || !disqualify_ops_if_throwing_stmt (stmt
,
1039 any
|= scan_expr (lhs_ptr
, &gsi
, true, data
);
1040 if (handle_ssa_defs
)
1041 any
|= handle_ssa_defs (stmt
, data
);
1049 walk_stmt_load_store_addr_ops (stmt
, NULL
, NULL
, NULL
,
1052 bitmap_set_bit (final_bbs
, bb
->index
);
1054 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
1056 tree
*op
= &TREE_VALUE (gimple_asm_input_op (stmt
, i
));
1057 any
|= scan_expr (op
, &gsi
, false, data
);
1059 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
1061 tree
*op
= &TREE_VALUE (gimple_asm_output_op (stmt
, i
));
1062 any
|= scan_expr (op
, &gsi
, true, data
);
1074 if (!analysis_stage
)
1078 maybe_clean_eh_stmt (stmt
);
1089 if (!analysis_stage
&& bb_changed
&& sra_mode
== SRA_MODE_EARLY_IPA
)
1090 gimple_purge_dead_eh_edges (bb
);
1096 /* Helper of QSORT function. There are pointers to accesses in the array. An
1097 access is considered smaller than another if it has smaller offset or if the
1098 offsets are the same but is size is bigger. */
1101 compare_access_positions (const void *a
, const void *b
)
1103 const access_p
*fp1
= (const access_p
*) a
;
1104 const access_p
*fp2
= (const access_p
*) b
;
1105 const access_p f1
= *fp1
;
1106 const access_p f2
= *fp2
;
1108 if (f1
->offset
!= f2
->offset
)
1109 return f1
->offset
< f2
->offset
? -1 : 1;
1111 if (f1
->size
== f2
->size
)
1113 /* Put any non-aggregate type before any aggregate type. */
1114 if (!is_gimple_reg_type (f1
->type
)
1115 && is_gimple_reg_type (f2
->type
))
1117 else if (is_gimple_reg_type (f1
->type
)
1118 && !is_gimple_reg_type (f2
->type
))
1120 /* Put the integral type with the bigger precision first. */
1121 else if (INTEGRAL_TYPE_P (f1
->type
)
1122 && INTEGRAL_TYPE_P (f2
->type
))
1123 return TYPE_PRECISION (f1
->type
) > TYPE_PRECISION (f2
->type
) ? -1 : 1;
1124 /* Put any integral type with non-full precision last. */
1125 else if (INTEGRAL_TYPE_P (f1
->type
)
1126 && (TREE_INT_CST_LOW (TYPE_SIZE (f1
->type
))
1127 != TYPE_PRECISION (f1
->type
)))
1129 else if (INTEGRAL_TYPE_P (f2
->type
)
1130 && (TREE_INT_CST_LOW (TYPE_SIZE (f2
->type
))
1131 != TYPE_PRECISION (f2
->type
)))
1133 /* Stabilize the sort. */
1134 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1137 /* We want the bigger accesses first, thus the opposite operator in the next
1139 return f1
->size
> f2
->size
? -1 : 1;
1143 /* Append a name of the declaration to the name obstack. A helper function for
1147 make_fancy_decl_name (tree decl
)
1151 tree name
= DECL_NAME (decl
);
1153 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1154 IDENTIFIER_LENGTH (name
));
1157 sprintf (buffer
, "D%u", DECL_UID (decl
));
1158 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1162 /* Helper for make_fancy_name. */
1165 make_fancy_name_1 (tree expr
)
1172 make_fancy_decl_name (expr
);
1176 switch (TREE_CODE (expr
))
1179 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1180 obstack_1grow (&name_obstack
, '$');
1181 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1185 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1186 obstack_1grow (&name_obstack
, '$');
1187 /* Arrays with only one element may not have a constant as their
1189 index
= TREE_OPERAND (expr
, 1);
1190 if (TREE_CODE (index
) != INTEGER_CST
)
1192 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1193 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1200 gcc_unreachable (); /* we treat these as scalars. */
1207 /* Create a human readable name for replacement variable of ACCESS. */
1210 make_fancy_name (tree expr
)
1212 make_fancy_name_1 (expr
);
1213 obstack_1grow (&name_obstack
, '\0');
1214 return XOBFINISH (&name_obstack
, char *);
1217 /* Helper function for build_ref_for_offset. */
1220 build_ref_for_offset_1 (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1226 tree tr_size
, index
, minidx
;
1227 HOST_WIDE_INT el_size
;
1229 if (offset
== 0 && exp_type
1230 && types_compatible_p (exp_type
, type
))
1233 switch (TREE_CODE (type
))
1236 case QUAL_UNION_TYPE
:
1238 for (fld
= TYPE_FIELDS (type
); fld
; fld
= TREE_CHAIN (fld
))
1240 HOST_WIDE_INT pos
, size
;
1241 tree expr
, *expr_ptr
;
1243 if (TREE_CODE (fld
) != FIELD_DECL
)
1246 pos
= int_bit_position (fld
);
1247 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1248 tr_size
= DECL_SIZE (fld
);
1249 if (!tr_size
|| !host_integerp (tr_size
, 1))
1251 size
= tree_low_cst (tr_size
, 1);
1252 if (pos
> offset
|| (pos
+ size
) <= offset
)
1257 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1263 if (build_ref_for_offset_1 (expr_ptr
, TREE_TYPE (fld
),
1264 offset
- pos
, exp_type
))
1274 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1275 if (!tr_size
|| !host_integerp (tr_size
, 1))
1277 el_size
= tree_low_cst (tr_size
, 1);
1279 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1280 if (TREE_CODE (minidx
) != INTEGER_CST
)
1284 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1285 if (!integer_zerop (minidx
))
1286 index
= int_const_binop (PLUS_EXPR
, index
, minidx
, 0);
1287 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1288 NULL_TREE
, NULL_TREE
);
1290 offset
= offset
% el_size
;
1291 type
= TREE_TYPE (type
);
1306 /* Construct an expression that would reference a part of aggregate *EXPR of
1307 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1308 function only determines whether it can build such a reference without
1309 actually doing it, otherwise, the tree it points to is unshared first and
1310 then used as a base for furhter sub-references.
1312 FIXME: Eventually this should be replaced with
1313 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1314 minor rewrite of fold_stmt.
1318 build_ref_for_offset (tree
*expr
, tree type
, HOST_WIDE_INT offset
,
1319 tree exp_type
, bool allow_ptr
)
1321 location_t loc
= expr
? EXPR_LOCATION (*expr
) : UNKNOWN_LOCATION
;
1324 *expr
= unshare_expr (*expr
);
1326 if (allow_ptr
&& POINTER_TYPE_P (type
))
1328 type
= TREE_TYPE (type
);
1330 *expr
= fold_build1_loc (loc
, INDIRECT_REF
, type
, *expr
);
1333 return build_ref_for_offset_1 (expr
, type
, offset
, exp_type
);
1336 /* Return true iff TYPE is stdarg va_list type. */
1339 is_va_list_type (tree type
)
1341 return TYPE_MAIN_VARIANT (type
) == TYPE_MAIN_VARIANT (va_list_type_node
);
1344 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1345 those with type which is suitable for scalarization. */
1348 find_var_candidates (void)
1351 referenced_var_iterator rvi
;
1354 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1356 if (TREE_CODE (var
) != VAR_DECL
&& TREE_CODE (var
) != PARM_DECL
)
1358 type
= TREE_TYPE (var
);
1360 if (!AGGREGATE_TYPE_P (type
)
1361 || needs_to_live_in_memory (var
)
1362 || TREE_THIS_VOLATILE (var
)
1363 || !COMPLETE_TYPE_P (type
)
1364 || !host_integerp (TYPE_SIZE (type
), 1)
1365 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
1366 || type_internals_preclude_sra_p (type
)
1367 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1368 we also want to schedule it rather late. Thus we ignore it in
1370 || (sra_mode
== SRA_MODE_EARLY_INTRA
1371 && is_va_list_type (type
)))
1374 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1378 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1379 print_generic_expr (dump_file
, var
, 0);
1380 fprintf (dump_file
, "\n");
1388 /* Sort all accesses for the given variable, check for partial overlaps and
1389 return NULL if there are any. If there are none, pick a representative for
1390 each combination of offset and size and create a linked list out of them.
1391 Return the pointer to the first representative and make sure it is the first
1392 one in the vector of accesses. */
1394 static struct access
*
1395 sort_and_splice_var_accesses (tree var
)
1397 int i
, j
, access_count
;
1398 struct access
*res
, **prev_acc_ptr
= &res
;
1399 VEC (access_p
, heap
) *access_vec
;
1401 HOST_WIDE_INT low
= -1, high
= 0;
1403 access_vec
= get_base_access_vector (var
);
1406 access_count
= VEC_length (access_p
, access_vec
);
1408 /* Sort by <OFFSET, SIZE>. */
1409 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
1410 compare_access_positions
);
1413 while (i
< access_count
)
1415 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
1416 bool grp_write
= access
->write
;
1417 bool grp_read
= !access
->write
;
1418 bool multiple_reads
= false;
1419 bool grp_partial_lhs
= access
->grp_partial_lhs
;
1420 bool first_scalar
= is_gimple_reg_type (access
->type
);
1421 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
1423 if (first
|| access
->offset
>= high
)
1426 low
= access
->offset
;
1427 high
= access
->offset
+ access
->size
;
1429 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
1432 gcc_assert (access
->offset
>= low
1433 && access
->offset
+ access
->size
<= high
);
1436 while (j
< access_count
)
1438 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
1439 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
1446 multiple_reads
= true;
1450 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
1451 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
1452 relink_to_new_repr (access
, ac2
);
1454 /* If there are both aggregate-type and scalar-type accesses with
1455 this combination of size and offset, the comparison function
1456 should have put the scalars first. */
1457 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
1458 ac2
->group_representative
= access
;
1464 access
->group_representative
= access
;
1465 access
->grp_write
= grp_write
;
1466 access
->grp_read
= grp_read
;
1467 access
->grp_hint
= multiple_reads
;
1468 access
->grp_partial_lhs
= grp_partial_lhs
;
1469 access
->grp_unscalarizable_region
= unscalarizable_region
;
1470 if (access
->first_link
)
1471 add_access_to_work_queue (access
);
1473 *prev_acc_ptr
= access
;
1474 prev_acc_ptr
= &access
->next_grp
;
1477 gcc_assert (res
== VEC_index (access_p
, access_vec
, 0));
1481 /* Create a variable for the given ACCESS which determines the type, name and a
1482 few other properties. Return the variable declaration and store it also to
1483 ACCESS->replacement. */
1486 create_access_replacement (struct access
*access
)
1490 repl
= create_tmp_var (access
->type
, "SR");
1492 add_referenced_var (repl
);
1493 mark_sym_for_renaming (repl
);
1495 if (!access
->grp_partial_lhs
1496 && (TREE_CODE (access
->type
) == COMPLEX_TYPE
1497 || TREE_CODE (access
->type
) == VECTOR_TYPE
))
1498 DECL_GIMPLE_REG_P (repl
) = 1;
1500 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
1501 DECL_ARTIFICIAL (repl
) = 1;
1503 if (DECL_NAME (access
->base
)
1504 && !DECL_IGNORED_P (access
->base
)
1505 && !DECL_ARTIFICIAL (access
->base
))
1507 char *pretty_name
= make_fancy_name (access
->expr
);
1509 DECL_NAME (repl
) = get_identifier (pretty_name
);
1510 obstack_free (&name_obstack
, pretty_name
);
1512 SET_DECL_DEBUG_EXPR (repl
, access
->expr
);
1513 DECL_DEBUG_EXPR_IS_FROM (repl
) = 1;
1514 DECL_IGNORED_P (repl
) = 0;
1517 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
1518 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
1522 fprintf (dump_file
, "Created a replacement for ");
1523 print_generic_expr (dump_file
, access
->base
, 0);
1524 fprintf (dump_file
, " offset: %u, size: %u: ",
1525 (unsigned) access
->offset
, (unsigned) access
->size
);
1526 print_generic_expr (dump_file
, repl
, 0);
1527 fprintf (dump_file
, "\n");
1529 sra_stats
.replacements
++;
1534 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1537 get_access_replacement (struct access
*access
)
1539 gcc_assert (access
->grp_to_be_replaced
);
1541 if (!access
->replacement_decl
)
1542 access
->replacement_decl
= create_access_replacement (access
);
1543 return access
->replacement_decl
;
1546 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1547 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1548 to it is not "within" the root. */
1551 build_access_subtree (struct access
**access
)
1553 struct access
*root
= *access
, *last_child
= NULL
;
1554 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1556 *access
= (*access
)->next_grp
;
1557 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
1560 root
->first_child
= *access
;
1562 last_child
->next_sibling
= *access
;
1563 last_child
= *access
;
1565 build_access_subtree (access
);
1569 /* Build a tree of access representatives, ACCESS is the pointer to the first
1570 one, others are linked in a list by the next_grp field. Decide about scalar
1571 replacements on the way, return true iff any are to be created. */
1574 build_access_trees (struct access
*access
)
1578 struct access
*root
= access
;
1580 build_access_subtree (&access
);
1581 root
->next_grp
= access
;
1585 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1589 expr_with_var_bounded_array_refs_p (tree expr
)
1591 while (handled_component_p (expr
))
1593 if (TREE_CODE (expr
) == ARRAY_REF
1594 && !host_integerp (array_ref_low_bound (expr
), 0))
1596 expr
= TREE_OPERAND (expr
, 0);
1601 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1602 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1603 all sorts of access flags appropriately along the way, notably always ser
1604 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1607 analyze_access_subtree (struct access
*root
, bool allow_replacements
,
1608 bool mark_read
, bool mark_write
)
1610 struct access
*child
;
1611 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1612 HOST_WIDE_INT covered_to
= root
->offset
;
1613 bool scalar
= is_gimple_reg_type (root
->type
);
1614 bool hole
= false, sth_created
= false;
1615 bool direct_read
= root
->grp_read
;
1618 root
->grp_read
= true;
1619 else if (root
->grp_read
)
1623 root
->grp_write
= true;
1624 else if (root
->grp_write
)
1627 if (root
->grp_unscalarizable_region
)
1628 allow_replacements
= false;
1630 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
1631 allow_replacements
= false;
1633 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
1635 if (!hole
&& child
->offset
< covered_to
)
1638 covered_to
+= child
->size
;
1640 sth_created
|= analyze_access_subtree (child
, allow_replacements
,
1641 mark_read
, mark_write
);
1643 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
1644 hole
|= !child
->grp_covered
;
1647 if (allow_replacements
&& scalar
&& !root
->first_child
1649 || (direct_read
&& root
->grp_write
)))
1651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1653 fprintf (dump_file
, "Marking ");
1654 print_generic_expr (dump_file
, root
->base
, 0);
1655 fprintf (dump_file
, " offset: %u, size: %u: ",
1656 (unsigned) root
->offset
, (unsigned) root
->size
);
1657 fprintf (dump_file
, " to be replaced.\n");
1660 root
->grp_to_be_replaced
= 1;
1664 else if (covered_to
< limit
)
1667 if (sth_created
&& !hole
)
1669 root
->grp_covered
= 1;
1672 if (root
->grp_write
|| TREE_CODE (root
->base
) == PARM_DECL
)
1673 root
->grp_unscalarized_data
= 1; /* not covered and written to */
1679 /* Analyze all access trees linked by next_grp by the means of
1680 analyze_access_subtree. */
1682 analyze_access_trees (struct access
*access
)
1688 if (analyze_access_subtree (access
, true, false, false))
1690 access
= access
->next_grp
;
1696 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1697 SIZE would conflict with an already existing one. If exactly such a child
1698 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1701 child_would_conflict_in_lacc (struct access
*lacc
, HOST_WIDE_INT norm_offset
,
1702 HOST_WIDE_INT size
, struct access
**exact_match
)
1704 struct access
*child
;
1706 for (child
= lacc
->first_child
; child
; child
= child
->next_sibling
)
1708 if (child
->offset
== norm_offset
&& child
->size
== size
)
1710 *exact_match
= child
;
1714 if (child
->offset
< norm_offset
+ size
1715 && child
->offset
+ child
->size
> norm_offset
)
1722 /* Create a new child access of PARENT, with all properties just like MODEL
1723 except for its offset and with its grp_write false and grp_read true.
1724 Return the new access or NULL if it cannot be created. Note that this access
1725 is created long after all splicing and sorting, it's not located in any
1726 access vector and is automatically a representative of its group. */
1728 static struct access
*
1729 create_artificial_child_access (struct access
*parent
, struct access
*model
,
1730 HOST_WIDE_INT new_offset
)
1732 struct access
*access
;
1733 struct access
**child
;
1734 tree expr
= parent
->base
;;
1736 gcc_assert (!model
->grp_unscalarizable_region
);
1738 if (!build_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
1739 model
->type
, false))
1742 access
= (struct access
*) pool_alloc (access_pool
);
1743 memset (access
, 0, sizeof (struct access
));
1744 access
->base
= parent
->base
;
1745 access
->expr
= expr
;
1746 access
->offset
= new_offset
;
1747 access
->size
= model
->size
;
1748 access
->type
= model
->type
;
1749 access
->grp_write
= true;
1750 access
->grp_read
= false;
1752 child
= &parent
->first_child
;
1753 while (*child
&& (*child
)->offset
< new_offset
)
1754 child
= &(*child
)->next_sibling
;
1756 access
->next_sibling
= *child
;
1763 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1764 true if any new subaccess was created. Additionally, if RACC is a scalar
1765 access but LACC is not, change the type of the latter, if possible. */
1768 propagate_subaccesses_across_link (struct access
*lacc
, struct access
*racc
)
1770 struct access
*rchild
;
1771 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
1774 if (is_gimple_reg_type (lacc
->type
)
1775 || lacc
->grp_unscalarizable_region
1776 || racc
->grp_unscalarizable_region
)
1779 if (!lacc
->first_child
&& !racc
->first_child
1780 && is_gimple_reg_type (racc
->type
))
1782 tree t
= lacc
->base
;
1784 if (build_ref_for_offset (&t
, TREE_TYPE (t
), lacc
->offset
, racc
->type
,
1788 lacc
->type
= racc
->type
;
1793 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
1795 struct access
*new_acc
= NULL
;
1796 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
1798 if (rchild
->grp_unscalarizable_region
)
1801 if (child_would_conflict_in_lacc (lacc
, norm_offset
, rchild
->size
,
1806 rchild
->grp_hint
= 1;
1807 new_acc
->grp_hint
|= new_acc
->grp_read
;
1808 if (rchild
->first_child
)
1809 ret
|= propagate_subaccesses_across_link (new_acc
, rchild
);
1814 /* If a (part of) a union field is on the RHS of an assignment, it can
1815 have sub-accesses which do not make sense on the LHS (PR 40351).
1816 Check that this is not the case. */
1817 if (!build_ref_for_offset (NULL
, TREE_TYPE (lacc
->base
), norm_offset
,
1818 rchild
->type
, false))
1821 rchild
->grp_hint
= 1;
1822 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
);
1826 if (racc
->first_child
)
1827 propagate_subaccesses_across_link (new_acc
, rchild
);
1834 /* Propagate all subaccesses across assignment links. */
1837 propagate_all_subaccesses (void)
1839 while (work_queue_head
)
1841 struct access
*racc
= pop_access_from_work_queue ();
1842 struct assign_link
*link
;
1844 gcc_assert (racc
->first_link
);
1846 for (link
= racc
->first_link
; link
; link
= link
->next
)
1848 struct access
*lacc
= link
->lacc
;
1850 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
1852 lacc
= lacc
->group_representative
;
1853 if (propagate_subaccesses_across_link (lacc
, racc
)
1854 && lacc
->first_link
)
1855 add_access_to_work_queue (lacc
);
1860 /* Go through all accesses collected throughout the (intraprocedural) analysis
1861 stage, exclude overlapping ones, identify representatives and build trees
1862 out of them, making decisions about scalarization on the way. Return true
1863 iff there are any to-be-scalarized variables after this stage. */
1866 analyze_all_variable_accesses (void)
1869 referenced_var_iterator rvi
;
1872 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1873 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1875 struct access
*access
;
1877 access
= sort_and_splice_var_accesses (var
);
1879 build_access_trees (access
);
1881 disqualify_candidate (var
,
1882 "No or inhibitingly overlapping accesses.");
1885 propagate_all_subaccesses ();
1887 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1888 if (bitmap_bit_p (candidate_bitmap
, DECL_UID (var
)))
1890 struct access
*access
= get_first_repr_for_decl (var
);
1892 if (analyze_access_trees (access
))
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1897 fprintf (dump_file
, "\nAccess trees for ");
1898 print_generic_expr (dump_file
, var
, 0);
1899 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
1900 dump_access_tree (dump_file
, access
);
1901 fprintf (dump_file
, "\n");
1905 disqualify_candidate (var
, "No scalar replacements to be created.");
1910 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
1917 /* Return true iff a reference statement into aggregate AGG can be built for
1918 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1919 or a child of its sibling. TOP_OFFSET is the offset from the processed
1920 access subtree that has to be subtracted from offset of each access. */
1923 ref_expr_for_all_replacements_p (struct access
*access
, tree agg
,
1924 HOST_WIDE_INT top_offset
)
1928 if (access
->grp_to_be_replaced
1929 && !build_ref_for_offset (NULL
, TREE_TYPE (agg
),
1930 access
->offset
- top_offset
,
1931 access
->type
, false))
1934 if (access
->first_child
1935 && !ref_expr_for_all_replacements_p (access
->first_child
, agg
,
1939 access
= access
->next_sibling
;
1946 /* Generate statements copying scalar replacements of accesses within a subtree
1947 into or out of AGG. ACCESS is the first child of the root of the subtree to
1948 be processed. AGG is an aggregate type expression (can be a declaration but
1949 does not have to be, it can for example also be an indirect_ref).
1950 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1951 from offsets of individual accesses to get corresponding offsets for AGG.
1952 If CHUNK_SIZE is non-null, copy only replacements in the interval
1953 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1954 statement iterator used to place the new statements. WRITE should be true
1955 when the statements should write from AGG to the replacement and false if
1956 vice versa. if INSERT_AFTER is true, new statements will be added after the
1957 current statement in GSI, they will be added before the statement
1961 generate_subtree_copies (struct access
*access
, tree agg
,
1962 HOST_WIDE_INT top_offset
,
1963 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
1964 gimple_stmt_iterator
*gsi
, bool write
,
1971 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
1974 if (access
->grp_to_be_replaced
1976 || access
->offset
+ access
->size
> start_offset
))
1978 tree repl
= get_access_replacement (access
);
1982 ref_found
= build_ref_for_offset (&expr
, TREE_TYPE (agg
),
1983 access
->offset
- top_offset
,
1984 access
->type
, false);
1985 gcc_assert (ref_found
);
1989 if (access
->grp_partial_lhs
)
1990 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
1992 insert_after
? GSI_NEW_STMT
1994 stmt
= gimple_build_assign (repl
, expr
);
1998 TREE_NO_WARNING (repl
) = 1;
1999 if (access
->grp_partial_lhs
)
2000 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2002 insert_after
? GSI_NEW_STMT
2004 stmt
= gimple_build_assign (expr
, repl
);
2008 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2010 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2012 sra_stats
.subtree_copies
++;
2015 if (access
->first_child
)
2016 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
2017 start_offset
, chunk_size
, gsi
,
2018 write
, insert_after
);
2020 access
= access
->next_sibling
;
2025 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2026 the root of the subtree to be processed. GSI is the statement iterator used
2027 for inserting statements which are added after the current statement if
2028 INSERT_AFTER is true or before it otherwise. */
2031 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
2035 struct access
*child
;
2037 if (access
->grp_to_be_replaced
)
2041 stmt
= gimple_build_assign (get_access_replacement (access
),
2042 fold_convert (access
->type
,
2043 integer_zero_node
));
2045 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2047 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2051 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2052 init_subtree_with_zero (child
, gsi
, insert_after
);
2055 /* Search for an access representative for the given expression EXPR and
2056 return it or NULL if it cannot be found. */
2058 static struct access
*
2059 get_access_for_expr (tree expr
)
2061 HOST_WIDE_INT offset
, size
, max_size
;
2064 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2065 a different size than the size of its argument and we need the latter
2067 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
2068 expr
= TREE_OPERAND (expr
, 0);
2070 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
2071 if (max_size
== -1 || !DECL_P (base
))
2074 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
2077 return get_var_base_offset_size_access (base
, offset
, max_size
);
2080 /* Callback for scan_function. Replace the expression EXPR with a scalar
2081 replacement if there is one and generate other statements to do type
2082 conversion or subtree copying if necessary. GSI is used to place newly
2083 created statements, WRITE is true if the expression is being written to (it
2084 is on a LHS of a statement or output in an assembly statement). */
2087 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
,
2088 void *data ATTRIBUTE_UNUSED
)
2090 struct access
*access
;
2093 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
2096 expr
= &TREE_OPERAND (*expr
, 0);
2101 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
2102 expr
= &TREE_OPERAND (*expr
, 0);
2103 access
= get_access_for_expr (*expr
);
2106 type
= TREE_TYPE (*expr
);
2108 if (access
->grp_to_be_replaced
)
2110 tree repl
= get_access_replacement (access
);
2111 /* If we replace a non-register typed access simply use the original
2112 access expression to extract the scalar component afterwards.
2113 This happens if scalarizing a function return value or parameter
2114 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2115 gcc.c-torture/compile/20011217-1.c. */
2116 if (!is_gimple_reg_type (type
))
2118 tree ref
= access
->base
;
2121 ok
= build_ref_for_offset (&ref
, TREE_TYPE (ref
),
2122 access
->offset
, access
->type
, false);
2129 if (access
->grp_partial_lhs
)
2130 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
2131 false, GSI_NEW_STMT
);
2132 stmt
= gimple_build_assign (repl
, ref
);
2133 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2139 if (access
->grp_partial_lhs
)
2140 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2141 true, GSI_SAME_STMT
);
2142 stmt
= gimple_build_assign (ref
, repl
);
2143 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2148 gcc_assert (useless_type_conversion_p (type
, access
->type
));
2154 if (access
->first_child
)
2156 HOST_WIDE_INT start_offset
, chunk_size
;
2158 && host_integerp (TREE_OPERAND (bfr
, 1), 1)
2159 && host_integerp (TREE_OPERAND (bfr
, 2), 1))
2161 chunk_size
= tree_low_cst (TREE_OPERAND (bfr
, 1), 1);
2162 start_offset
= access
->offset
2163 + tree_low_cst (TREE_OPERAND (bfr
, 2), 1);
2166 start_offset
= chunk_size
= 0;
2168 generate_subtree_copies (access
->first_child
, access
->base
, 0,
2169 start_offset
, chunk_size
, gsi
, write
, write
);
2174 /* Where scalar replacements of the RHS have been written to when a replacement
2175 of a LHS of an assigments cannot be direclty loaded from a replacement of
2177 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
2178 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
2179 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
2181 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2182 base aggregate if there are unscalarized data or directly to LHS
2185 static enum unscalarized_data_handling
2186 handle_unscalarized_data_in_subtree (struct access
*top_racc
, tree lhs
,
2187 gimple_stmt_iterator
*gsi
)
2189 if (top_racc
->grp_unscalarized_data
)
2191 generate_subtree_copies (top_racc
->first_child
, top_racc
->base
, 0, 0, 0,
2193 return SRA_UDH_RIGHT
;
2197 generate_subtree_copies (top_racc
->first_child
, lhs
, top_racc
->offset
,
2198 0, 0, gsi
, false, false);
2199 return SRA_UDH_LEFT
;
2204 /* Try to generate statements to load all sub-replacements in an access
2205 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2206 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2207 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2208 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2209 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
2210 the rhs top aggregate has already been refreshed by contents of its scalar
2211 reductions and is set to true if this function has to do it. */
2214 load_assign_lhs_subreplacements (struct access
*lacc
, struct access
*top_racc
,
2215 HOST_WIDE_INT left_offset
,
2216 HOST_WIDE_INT right_offset
,
2217 gimple_stmt_iterator
*old_gsi
,
2218 gimple_stmt_iterator
*new_gsi
,
2219 enum unscalarized_data_handling
*refreshed
,
2222 location_t loc
= EXPR_LOCATION (lacc
->expr
);
2225 if (lacc
->grp_to_be_replaced
)
2227 struct access
*racc
;
2228 HOST_WIDE_INT offset
= lacc
->offset
- left_offset
+ right_offset
;
2232 racc
= find_access_in_subtree (top_racc
, offset
, lacc
->size
);
2233 if (racc
&& racc
->grp_to_be_replaced
)
2235 rhs
= get_access_replacement (racc
);
2236 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
2237 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, lacc
->type
, rhs
);
2241 /* No suitable access on the right hand side, need to load from
2242 the aggregate. See if we have to update it first... */
2243 if (*refreshed
== SRA_UDH_NONE
)
2244 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
,
2247 if (*refreshed
== SRA_UDH_LEFT
)
2252 repl_found
= build_ref_for_offset (&rhs
, TREE_TYPE (rhs
),
2253 lacc
->offset
, lacc
->type
,
2255 gcc_assert (repl_found
);
2261 rhs
= top_racc
->base
;
2262 repl_found
= build_ref_for_offset (&rhs
,
2263 TREE_TYPE (top_racc
->base
),
2264 offset
, lacc
->type
, false);
2265 gcc_assert (repl_found
);
2269 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
2270 gsi_insert_after (new_gsi
, stmt
, GSI_NEW_STMT
);
2272 sra_stats
.subreplacements
++;
2274 else if (*refreshed
== SRA_UDH_NONE
2275 && lacc
->grp_read
&& !lacc
->grp_covered
)
2276 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
, lhs
,
2279 if (lacc
->first_child
)
2280 load_assign_lhs_subreplacements (lacc
->first_child
, top_racc
,
2281 left_offset
, right_offset
,
2282 old_gsi
, new_gsi
, refreshed
, lhs
);
2283 lacc
= lacc
->next_sibling
;
2288 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2289 to the assignment and GSI is the statement iterator pointing at it. Returns
2290 the same values as sra_modify_assign. */
2292 static enum scan_assign_result
2293 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
2295 tree lhs
= gimple_assign_lhs (*stmt
);
2298 acc
= get_access_for_expr (lhs
);
2302 if (VEC_length (constructor_elt
,
2303 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt
))) > 0)
2305 /* I have never seen this code path trigger but if it can happen the
2306 following should handle it gracefully. */
2307 if (access_has_children_p (acc
))
2308 generate_subtree_copies (acc
->first_child
, acc
->base
, 0, 0, 0, gsi
,
2310 return SRA_SA_PROCESSED
;
2313 if (acc
->grp_covered
)
2315 init_subtree_with_zero (acc
, gsi
, false);
2316 unlink_stmt_vdef (*stmt
);
2317 gsi_remove (gsi
, true);
2318 return SRA_SA_REMOVED
;
2322 init_subtree_with_zero (acc
, gsi
, true);
2323 return SRA_SA_PROCESSED
;
2328 /* Callback of scan_function to process assign statements. It examines both
2329 sides of the statement, replaces them with a scalare replacement if there is
2330 one and generating copying of replacements if scalarized aggregates have been
2331 used in the assignment. STMT is a pointer to the assign statement, GSI is
2332 used to hold generated statements for type conversions and subtree
2335 static enum scan_assign_result
2336 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
2337 void *data ATTRIBUTE_UNUSED
)
2339 struct access
*lacc
, *racc
;
2341 bool modify_this_stmt
= false;
2342 bool force_gimple_rhs
= false;
2343 location_t loc
= gimple_location (*stmt
);
2345 if (!gimple_assign_single_p (*stmt
))
2347 lhs
= gimple_assign_lhs (*stmt
);
2348 rhs
= gimple_assign_rhs1 (*stmt
);
2350 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
2351 return sra_modify_constructor_assign (stmt
, gsi
);
2353 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
2354 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
2355 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
2357 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (*stmt
),
2359 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (*stmt
),
2361 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2364 lacc
= get_access_for_expr (lhs
);
2365 racc
= get_access_for_expr (rhs
);
2369 if (lacc
&& lacc
->grp_to_be_replaced
)
2371 lhs
= get_access_replacement (lacc
);
2372 gimple_assign_set_lhs (*stmt
, lhs
);
2373 modify_this_stmt
= true;
2374 if (lacc
->grp_partial_lhs
)
2375 force_gimple_rhs
= true;
2379 if (racc
&& racc
->grp_to_be_replaced
)
2381 rhs
= get_access_replacement (racc
);
2382 modify_this_stmt
= true;
2383 if (racc
->grp_partial_lhs
)
2384 force_gimple_rhs
= true;
2388 if (modify_this_stmt
)
2390 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2392 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2393 ??? This should move to fold_stmt which we simply should
2394 call after building a VIEW_CONVERT_EXPR here. */
2395 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
2396 && !access_has_children_p (lacc
))
2399 if (build_ref_for_offset (&expr
, TREE_TYPE (lhs
), 0,
2400 TREE_TYPE (rhs
), false))
2403 gimple_assign_set_lhs (*stmt
, expr
);
2406 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
2407 && !access_has_children_p (racc
))
2410 if (build_ref_for_offset (&expr
, TREE_TYPE (rhs
), 0,
2411 TREE_TYPE (lhs
), false))
2414 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2416 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
), rhs
);
2417 if (!is_gimple_reg (lhs
))
2418 force_gimple_rhs
= true;
2422 if (force_gimple_rhs
)
2423 rhs
= force_gimple_operand_gsi (gsi
, rhs
, true, NULL_TREE
,
2424 true, GSI_SAME_STMT
);
2425 if (gimple_assign_rhs1 (*stmt
) != rhs
)
2427 gimple_assign_set_rhs_from_tree (gsi
, rhs
);
2428 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2432 /* From this point on, the function deals with assignments in between
2433 aggregates when at least one has scalar reductions of some of its
2434 components. There are three possible scenarios: Both the LHS and RHS have
2435 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2437 In the first case, we would like to load the LHS components from RHS
2438 components whenever possible. If that is not possible, we would like to
2439 read it directly from the RHS (after updating it by storing in it its own
2440 components). If there are some necessary unscalarized data in the LHS,
2441 those will be loaded by the original assignment too. If neither of these
2442 cases happen, the original statement can be removed. Most of this is done
2443 by load_assign_lhs_subreplacements.
2445 In the second case, we would like to store all RHS scalarized components
2446 directly into LHS and if they cover the aggregate completely, remove the
2447 statement too. In the third case, we want the LHS components to be loaded
2448 directly from the RHS (DSE will remove the original statement if it
2451 This is a bit complex but manageable when types match and when unions do
2452 not cause confusion in a way that we cannot really load a component of LHS
2453 from the RHS or vice versa (the access representing this level can have
2454 subaccesses that are accessible only through a different union field at a
2455 higher level - different from the one used in the examined expression).
2458 Therefore, I specially handle a fourth case, happening when there is a
2459 specific type cast or it is impossible to locate a scalarized subaccess on
2460 the other side of the expression. If that happens, I simply "refresh" the
2461 RHS by storing in it is scalarized components leave the original statement
2462 there to do the copying and then load the scalar replacements of the LHS.
2463 This is what the first branch does. */
2465 if (contains_view_convert_expr_p (rhs
) || contains_view_convert_expr_p (lhs
)
2466 || (access_has_children_p (racc
)
2467 && !ref_expr_for_all_replacements_p (racc
, lhs
, racc
->offset
))
2468 || (access_has_children_p (lacc
)
2469 && !ref_expr_for_all_replacements_p (lacc
, rhs
, lacc
->offset
)))
2471 if (access_has_children_p (racc
))
2472 generate_subtree_copies (racc
->first_child
, racc
->base
, 0, 0, 0,
2474 if (access_has_children_p (lacc
))
2475 generate_subtree_copies (lacc
->first_child
, lacc
->base
, 0, 0, 0,
2477 sra_stats
.separate_lhs_rhs_handling
++;
2481 if (access_has_children_p (lacc
) && access_has_children_p (racc
))
2483 gimple_stmt_iterator orig_gsi
= *gsi
;
2484 enum unscalarized_data_handling refreshed
;
2486 if (lacc
->grp_read
&& !lacc
->grp_covered
)
2487 refreshed
= handle_unscalarized_data_in_subtree (racc
, lhs
, gsi
);
2489 refreshed
= SRA_UDH_NONE
;
2491 load_assign_lhs_subreplacements (lacc
->first_child
, racc
,
2492 lacc
->offset
, racc
->offset
,
2493 &orig_gsi
, gsi
, &refreshed
, lhs
);
2494 if (refreshed
!= SRA_UDH_RIGHT
)
2496 if (*stmt
== gsi_stmt (*gsi
))
2499 unlink_stmt_vdef (*stmt
);
2500 gsi_remove (&orig_gsi
, true);
2501 sra_stats
.deleted
++;
2502 return SRA_SA_REMOVED
;
2507 if (access_has_children_p (racc
))
2509 if (!racc
->grp_unscalarized_data
)
2511 generate_subtree_copies (racc
->first_child
, lhs
,
2512 racc
->offset
, 0, 0, gsi
,
2514 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2515 unlink_stmt_vdef (*stmt
);
2516 gsi_remove (gsi
, true);
2517 sra_stats
.deleted
++;
2518 return SRA_SA_REMOVED
;
2521 generate_subtree_copies (racc
->first_child
, lhs
,
2522 racc
->offset
, 0, 0, gsi
, false, true);
2524 else if (access_has_children_p (lacc
))
2525 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
2526 0, 0, gsi
, true, true);
2529 return modify_this_stmt
? SRA_SA_PROCESSED
: SRA_SA_NONE
;
2532 /* Generate statements initializing scalar replacements of parts of function
2536 initialize_parameter_reductions (void)
2538 gimple_stmt_iterator gsi
;
2539 gimple_seq seq
= NULL
;
2542 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2544 parm
= TREE_CHAIN (parm
))
2546 VEC (access_p
, heap
) *access_vec
;
2547 struct access
*access
;
2549 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
2551 access_vec
= get_base_access_vector (parm
);
2557 seq
= gimple_seq_alloc ();
2558 gsi
= gsi_start (seq
);
2561 for (access
= VEC_index (access_p
, access_vec
, 0);
2563 access
= access
->next_grp
)
2564 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true);
2568 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR
), seq
);
2571 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2572 it reveals there are components of some aggregates to be scalarized, it runs
2573 the required transformations. */
2575 perform_intra_sra (void)
2580 if (!find_var_candidates ())
2583 if (!scan_function (build_access_from_expr
, build_accesses_from_assign
, NULL
,
2587 if (!analyze_all_variable_accesses ())
2590 scan_function (sra_modify_expr
, sra_modify_assign
, NULL
, false, NULL
);
2591 initialize_parameter_reductions ();
2593 statistics_counter_event (cfun
, "Scalar replacements created",
2594 sra_stats
.replacements
);
2595 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
2596 statistics_counter_event (cfun
, "Subtree copy stmts",
2597 sra_stats
.subtree_copies
);
2598 statistics_counter_event (cfun
, "Subreplacement stmts",
2599 sra_stats
.subreplacements
);
2600 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
2601 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
2602 sra_stats
.separate_lhs_rhs_handling
);
2604 ret
= TODO_update_ssa
;
2607 sra_deinitialize ();
2611 /* Perform early intraprocedural SRA. */
2613 early_intra_sra (void)
2615 sra_mode
= SRA_MODE_EARLY_INTRA
;
2616 return perform_intra_sra ();
2619 /* Perform "late" intraprocedural SRA. */
2621 late_intra_sra (void)
2623 sra_mode
= SRA_MODE_INTRA
;
2624 return perform_intra_sra ();
2629 gate_intra_sra (void)
2631 return flag_tree_sra
!= 0;
2635 struct gimple_opt_pass pass_sra_early
=
2640 gate_intra_sra
, /* gate */
2641 early_intra_sra
, /* execute */
2644 0, /* static_pass_number */
2645 TV_TREE_SRA
, /* tv_id */
2646 PROP_cfg
| PROP_ssa
, /* properties_required */
2647 0, /* properties_provided */
2648 0, /* properties_destroyed */
2649 0, /* todo_flags_start */
2653 | TODO_verify_ssa
/* todo_flags_finish */
2657 struct gimple_opt_pass pass_sra
=
2662 gate_intra_sra
, /* gate */
2663 late_intra_sra
, /* execute */
2666 0, /* static_pass_number */
2667 TV_TREE_SRA
, /* tv_id */
2668 PROP_cfg
| PROP_ssa
, /* properties_required */
2669 0, /* properties_provided */
2670 0, /* properties_destroyed */
2671 TODO_update_address_taken
, /* todo_flags_start */
2675 | TODO_verify_ssa
/* todo_flags_finish */
2680 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
2684 is_unused_scalar_param (tree parm
)
2687 return (is_gimple_reg (parm
)
2688 && (!(name
= gimple_default_def (cfun
, parm
))
2689 || has_zero_uses (name
)));
2692 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
2693 examine whether there are any direct or otherwise infeasible ones. If so,
2694 return true, otherwise return false. PARM must be a gimple register with a
2695 non-NULL default definition. */
2698 ptr_parm_has_direct_uses (tree parm
)
2700 imm_use_iterator ui
;
2702 tree name
= gimple_default_def (cfun
, parm
);
2705 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
2707 if (gimple_assign_single_p (stmt
))
2709 tree rhs
= gimple_assign_rhs1 (stmt
);
2712 else if (TREE_CODE (rhs
) == ADDR_EXPR
)
2716 rhs
= TREE_OPERAND (rhs
, 0);
2718 while (handled_component_p (rhs
));
2719 if (INDIRECT_REF_P (rhs
) && TREE_OPERAND (rhs
, 0) == name
)
2723 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
2725 tree t
= gimple_return_retval (stmt
);
2729 else if (is_gimple_call (stmt
))
2732 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
2734 tree arg
= gimple_call_arg (stmt
, i
);
2742 else if (!is_gimple_debug (stmt
))
2746 BREAK_FROM_IMM_USE_STMT (ui
);
2752 /* Identify candidates for reduction for IPA-SRA based on their type and mark
2753 them in candidate_bitmap. Note that these do not necessarily include
2754 parameter which are unused and thus can be removed. Return true iff any
2755 such candidate has been found. */
2758 find_param_candidates (void)
2764 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2766 parm
= TREE_CHAIN (parm
))
2768 tree type
= TREE_TYPE (parm
);
2772 if (TREE_THIS_VOLATILE (parm
)
2773 || TREE_ADDRESSABLE (parm
)
2774 || is_va_list_type (type
))
2777 if (is_unused_scalar_param (parm
))
2783 if (POINTER_TYPE_P (type
))
2785 type
= TREE_TYPE (type
);
2787 if (TREE_CODE (type
) == FUNCTION_TYPE
2788 || TYPE_VOLATILE (type
)
2789 || !is_gimple_reg (parm
)
2790 || is_va_list_type (type
)
2791 || ptr_parm_has_direct_uses (parm
))
2794 else if (!AGGREGATE_TYPE_P (type
))
2797 if (!COMPLETE_TYPE_P (type
)
2798 || !host_integerp (TYPE_SIZE (type
), 1)
2799 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
2800 || (AGGREGATE_TYPE_P (type
)
2801 && type_internals_preclude_sra_p (type
)))
2804 bitmap_set_bit (candidate_bitmap
, DECL_UID (parm
));
2806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2808 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (parm
));
2809 print_generic_expr (dump_file
, parm
, 0);
2810 fprintf (dump_file
, "\n");
2814 func_param_count
= count
;
2818 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
2822 mark_maybe_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
2825 struct access
*repr
= (struct access
*) data
;
2827 repr
->grp_maybe_modified
= 1;
2831 /* Analyze what representatives (in linked lists accessible from
2832 REPRESENTATIVES) can be modified by side effects of statements in the
2833 current function. */
2836 analyze_modified_params (VEC (access_p
, heap
) *representatives
)
2840 for (i
= 0; i
< func_param_count
; i
++)
2842 struct access
*repr
;
2844 for (repr
= VEC_index (access_p
, representatives
, i
);
2846 repr
= repr
->next_grp
)
2848 struct access
*access
;
2852 if (no_accesses_p (repr
))
2854 if (!POINTER_TYPE_P (TREE_TYPE (repr
->base
))
2855 || repr
->grp_maybe_modified
)
2858 ao_ref_init (&ar
, repr
->expr
);
2859 visited
= BITMAP_ALLOC (NULL
);
2860 for (access
= repr
; access
; access
= access
->next_sibling
)
2862 /* All accesses are read ones, otherwise grp_maybe_modified would
2863 be trivially set. */
2864 walk_aliased_vdefs (&ar
, gimple_vuse (access
->stmt
),
2865 mark_maybe_modified
, repr
, &visited
);
2866 if (repr
->grp_maybe_modified
)
2869 BITMAP_FREE (visited
);
2874 /* Propagate distances in bb_dereferences in the opposite direction than the
2875 control flow edges, in each step storing the maximum of the current value
2876 and the minimum of all successors. These steps are repeated until the table
2877 stabilizes. Note that BBs which might terminate the functions (according to
2878 final_bbs bitmap) never updated in this way. */
2881 propagate_dereference_distances (void)
2883 VEC (basic_block
, heap
) *queue
;
2886 queue
= VEC_alloc (basic_block
, heap
, last_basic_block_for_function (cfun
));
2887 VEC_quick_push (basic_block
, queue
, ENTRY_BLOCK_PTR
);
2890 VEC_quick_push (basic_block
, queue
, bb
);
2894 while (!VEC_empty (basic_block
, queue
))
2898 bool change
= false;
2901 bb
= VEC_pop (basic_block
, queue
);
2904 if (bitmap_bit_p (final_bbs
, bb
->index
))
2907 for (i
= 0; i
< func_param_count
; i
++)
2909 int idx
= bb
->index
* func_param_count
+ i
;
2911 HOST_WIDE_INT inh
= 0;
2913 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2915 int succ_idx
= e
->dest
->index
* func_param_count
+ i
;
2917 if (e
->src
== EXIT_BLOCK_PTR
)
2923 inh
= bb_dereferences
[succ_idx
];
2925 else if (bb_dereferences
[succ_idx
] < inh
)
2926 inh
= bb_dereferences
[succ_idx
];
2929 if (!first
&& bb_dereferences
[idx
] < inh
)
2931 bb_dereferences
[idx
] = inh
;
2936 if (change
&& !bitmap_bit_p (final_bbs
, bb
->index
))
2937 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2942 e
->src
->aux
= e
->src
;
2943 VEC_quick_push (basic_block
, queue
, e
->src
);
2947 VEC_free (basic_block
, heap
, queue
);
2950 /* Dump a dereferences TABLE with heading STR to file F. */
2953 dump_dereferences_table (FILE *f
, const char *str
, HOST_WIDE_INT
*table
)
2957 fprintf (dump_file
, str
);
2958 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
2960 fprintf (f
, "%4i %i ", bb
->index
, bitmap_bit_p (final_bbs
, bb
->index
));
2961 if (bb
!= EXIT_BLOCK_PTR
)
2964 for (i
= 0; i
< func_param_count
; i
++)
2966 int idx
= bb
->index
* func_param_count
+ i
;
2967 fprintf (f
, " %4" HOST_WIDE_INT_PRINT
"d", table
[idx
]);
2972 fprintf (dump_file
, "\n");
2975 /* Determine what (parts of) parameters passed by reference that are not
2976 assigned to are not certainly dereferenced in this function and thus the
2977 dereferencing cannot be safely moved to the caller without potentially
2978 introducing a segfault. Mark such REPRESENTATIVES as
2979 grp_not_necessarilly_dereferenced.
2981 The dereferenced maximum "distance," i.e. the offset + size of the accessed
2982 part is calculated rather than simple booleans are calculated for each
2983 pointer parameter to handle cases when only a fraction of the whole
2984 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
2987 The maximum dereference distances for each pointer parameter and BB are
2988 already stored in bb_dereference. This routine simply propagates these
2989 values upwards by propagate_dereference_distances and then compares the
2990 distances of individual parameters in the ENTRY BB to the equivalent
2991 distances of each representative of a (fraction of a) parameter. */
2994 analyze_caller_dereference_legality (VEC (access_p
, heap
) *representatives
)
2998 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2999 dump_dereferences_table (dump_file
,
3000 "Dereference table before propagation:\n",
3003 propagate_dereference_distances ();
3005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3006 dump_dereferences_table (dump_file
,
3007 "Dereference table after propagation:\n",
3010 for (i
= 0; i
< func_param_count
; i
++)
3012 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3013 int idx
= ENTRY_BLOCK_PTR
->index
* func_param_count
+ i
;
3015 if (!repr
|| no_accesses_p (repr
))
3020 if ((repr
->offset
+ repr
->size
) > bb_dereferences
[idx
])
3021 repr
->grp_not_necessarilly_dereferenced
= 1;
3022 repr
= repr
->next_grp
;
3028 /* Return the representative access for the parameter declaration PARM if it is
3029 a scalar passed by reference which is not written to and the pointer value
3030 is not used directly. Thus, if it is legal to dereference it in the caller
3031 and we can rule out modifications through aliases, such parameter should be
3032 turned into one passed by value. Return NULL otherwise. */
3034 static struct access
*
3035 unmodified_by_ref_scalar_representative (tree parm
)
3037 int i
, access_count
;
3038 struct access
*repr
;
3039 VEC (access_p
, heap
) *access_vec
;
3041 access_vec
= get_base_access_vector (parm
);
3042 gcc_assert (access_vec
);
3043 repr
= VEC_index (access_p
, access_vec
, 0);
3046 repr
->group_representative
= repr
;
3048 access_count
= VEC_length (access_p
, access_vec
);
3049 for (i
= 1; i
< access_count
; i
++)
3051 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
3054 access
->group_representative
= repr
;
3055 access
->next_sibling
= repr
->next_sibling
;
3056 repr
->next_sibling
= access
;
3060 repr
->grp_scalar_ptr
= 1;
3064 /* Return true iff this access precludes IPA-SRA of the parameter it is
3068 access_precludes_ipa_sra_p (struct access
*access
)
3070 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3071 is incompatible assign in a call statement (and possibly even in asm
3072 statements). This can be relaxed by using a new temporary but only for
3073 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3074 intraprocedural SRA we deal with this by keeping the old aggregate around,
3075 something we cannot do in IPA-SRA.) */
3077 && (is_gimple_call (access
->stmt
)
3078 || gimple_code (access
->stmt
) == GIMPLE_ASM
))
3085 /* Sort collected accesses for parameter PARM, identify representatives for
3086 each accessed region and link them together. Return NULL if there are
3087 different but overlapping accesses, return the special ptr value meaning
3088 there are no accesses for this parameter if that is the case and return the
3089 first representative otherwise. Set *RO_GRP if there is a group of accesses
3090 with only read (i.e. no write) accesses. */
3092 static struct access
*
3093 splice_param_accesses (tree parm
, bool *ro_grp
)
3095 int i
, j
, access_count
, group_count
;
3096 int agg_size
, total_size
= 0;
3097 struct access
*access
, *res
, **prev_acc_ptr
= &res
;
3098 VEC (access_p
, heap
) *access_vec
;
3100 access_vec
= get_base_access_vector (parm
);
3102 return &no_accesses_representant
;
3103 access_count
= VEC_length (access_p
, access_vec
);
3105 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
3106 compare_access_positions
);
3111 while (i
< access_count
)
3114 access
= VEC_index (access_p
, access_vec
, i
);
3115 modification
= access
->write
;
3116 if (access_precludes_ipa_sra_p (access
))
3119 /* Access is about to become group representative unless we find some
3120 nasty overlap which would preclude us from breaking this parameter
3124 while (j
< access_count
)
3126 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
3127 if (ac2
->offset
!= access
->offset
)
3129 /* All or nothing law for parameters. */
3130 if (access
->offset
+ access
->size
> ac2
->offset
)
3135 else if (ac2
->size
!= access
->size
)
3138 if (access_precludes_ipa_sra_p (ac2
))
3141 modification
|= ac2
->write
;
3142 ac2
->group_representative
= access
;
3143 ac2
->next_sibling
= access
->next_sibling
;
3144 access
->next_sibling
= ac2
;
3149 access
->grp_maybe_modified
= modification
;
3152 *prev_acc_ptr
= access
;
3153 prev_acc_ptr
= &access
->next_grp
;
3154 total_size
+= access
->size
;
3158 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3159 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3161 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3162 if (total_size
>= agg_size
)
3165 gcc_assert (group_count
> 0);
3169 /* Decide whether parameters with representative accesses given by REPR should
3170 be reduced into components. */
3173 decide_one_param_reduction (struct access
*repr
)
3175 int total_size
, cur_parm_size
, agg_size
, new_param_count
, parm_size_limit
;
3180 cur_parm_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3181 gcc_assert (cur_parm_size
> 0);
3183 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3186 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3191 agg_size
= cur_parm_size
;
3197 fprintf (dump_file
, "Evaluating PARAM group sizes for ");
3198 print_generic_expr (dump_file
, parm
, 0);
3199 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (parm
));
3200 for (acc
= repr
; acc
; acc
= acc
->next_grp
)
3201 dump_access (dump_file
, acc
, true);
3205 new_param_count
= 0;
3207 for (; repr
; repr
= repr
->next_grp
)
3209 gcc_assert (parm
== repr
->base
);
3212 if (!by_ref
|| (!repr
->grp_maybe_modified
3213 && !repr
->grp_not_necessarilly_dereferenced
))
3214 total_size
+= repr
->size
;
3216 total_size
+= cur_parm_size
;
3219 gcc_assert (new_param_count
> 0);
3221 if (optimize_function_for_size_p (cfun
))
3222 parm_size_limit
= cur_parm_size
;
3224 parm_size_limit
= (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR
)
3227 if (total_size
< agg_size
3228 && total_size
<= parm_size_limit
)
3231 fprintf (dump_file
, " ....will be split into %i components\n",
3233 return new_param_count
;
3239 /* The order of the following enums is important, we need to do extra work for
3240 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3241 enum ipa_splicing_result
{ NO_GOOD_ACCESS
, UNUSED_PARAMS
, BY_VAL_ACCESSES
,
3242 MODIF_BY_REF_ACCESSES
, UNMODIF_BY_REF_ACCESSES
};
3244 /* Identify representatives of all accesses to all candidate parameters for
3245 IPA-SRA. Return result based on what representatives have been found. */
3247 static enum ipa_splicing_result
3248 splice_all_param_accesses (VEC (access_p
, heap
) **representatives
)
3250 enum ipa_splicing_result result
= NO_GOOD_ACCESS
;
3252 struct access
*repr
;
3254 *representatives
= VEC_alloc (access_p
, heap
, func_param_count
);
3256 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3258 parm
= TREE_CHAIN (parm
))
3260 if (is_unused_scalar_param (parm
))
3262 VEC_quick_push (access_p
, *representatives
,
3263 &no_accesses_representant
);
3264 if (result
== NO_GOOD_ACCESS
)
3265 result
= UNUSED_PARAMS
;
3267 else if (POINTER_TYPE_P (TREE_TYPE (parm
))
3268 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm
)))
3269 && bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3271 repr
= unmodified_by_ref_scalar_representative (parm
);
3272 VEC_quick_push (access_p
, *representatives
, repr
);
3274 result
= UNMODIF_BY_REF_ACCESSES
;
3276 else if (bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3278 bool ro_grp
= false;
3279 repr
= splice_param_accesses (parm
, &ro_grp
);
3280 VEC_quick_push (access_p
, *representatives
, repr
);
3282 if (repr
&& !no_accesses_p (repr
))
3284 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3287 result
= UNMODIF_BY_REF_ACCESSES
;
3288 else if (result
< MODIF_BY_REF_ACCESSES
)
3289 result
= MODIF_BY_REF_ACCESSES
;
3291 else if (result
< BY_VAL_ACCESSES
)
3292 result
= BY_VAL_ACCESSES
;
3294 else if (no_accesses_p (repr
) && (result
== NO_GOOD_ACCESS
))
3295 result
= UNUSED_PARAMS
;
3298 VEC_quick_push (access_p
, *representatives
, NULL
);
3301 if (result
== NO_GOOD_ACCESS
)
3303 VEC_free (access_p
, heap
, *representatives
);
3304 *representatives
= NULL
;
3305 return NO_GOOD_ACCESS
;
3311 /* Return the index of BASE in PARMS. Abort if it is not found. */
3314 get_param_index (tree base
, VEC(tree
, heap
) *parms
)
3318 len
= VEC_length (tree
, parms
);
3319 for (i
= 0; i
< len
; i
++)
3320 if (VEC_index (tree
, parms
, i
) == base
)
3325 /* Convert the decisions made at the representative level into compact
3326 parameter adjustments. REPRESENTATIVES are pointers to first
3327 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3328 final number of adjustments. */
3330 static ipa_parm_adjustment_vec
3331 turn_representatives_into_adjustments (VEC (access_p
, heap
) *representatives
,
3332 int adjustments_count
)
3334 VEC (tree
, heap
) *parms
;
3335 ipa_parm_adjustment_vec adjustments
;
3339 gcc_assert (adjustments_count
> 0);
3340 parms
= ipa_get_vector_of_formal_parms (current_function_decl
);
3341 adjustments
= VEC_alloc (ipa_parm_adjustment_t
, heap
, adjustments_count
);
3342 parm
= DECL_ARGUMENTS (current_function_decl
);
3343 for (i
= 0; i
< func_param_count
; i
++, parm
= TREE_CHAIN (parm
))
3345 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3347 if (!repr
|| no_accesses_p (repr
))
3349 struct ipa_parm_adjustment
*adj
;
3351 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3352 memset (adj
, 0, sizeof (*adj
));
3353 adj
->base_index
= get_param_index (parm
, parms
);
3356 adj
->copy_param
= 1;
3358 adj
->remove_param
= 1;
3362 struct ipa_parm_adjustment
*adj
;
3363 int index
= get_param_index (parm
, parms
);
3365 for (; repr
; repr
= repr
->next_grp
)
3367 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3368 memset (adj
, 0, sizeof (*adj
));
3369 gcc_assert (repr
->base
== parm
);
3370 adj
->base_index
= index
;
3371 adj
->base
= repr
->base
;
3372 adj
->type
= repr
->type
;
3373 adj
->offset
= repr
->offset
;
3374 adj
->by_ref
= (POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3375 && (repr
->grp_maybe_modified
3376 || repr
->grp_not_necessarilly_dereferenced
));
3381 VEC_free (tree
, heap
, parms
);
3385 /* Analyze the collected accesses and produce a plan what to do with the
3386 parameters in the form of adjustments, NULL meaning nothing. */
3388 static ipa_parm_adjustment_vec
3389 analyze_all_param_acesses (void)
3391 enum ipa_splicing_result repr_state
;
3392 bool proceed
= false;
3393 int i
, adjustments_count
= 0;
3394 VEC (access_p
, heap
) *representatives
;
3395 ipa_parm_adjustment_vec adjustments
;
3397 repr_state
= splice_all_param_accesses (&representatives
);
3398 if (repr_state
== NO_GOOD_ACCESS
)
3401 /* If there are any parameters passed by reference which are not modified
3402 directly, we need to check whether they can be modified indirectly. */
3403 if (repr_state
== UNMODIF_BY_REF_ACCESSES
)
3405 analyze_caller_dereference_legality (representatives
);
3406 analyze_modified_params (representatives
);
3409 for (i
= 0; i
< func_param_count
; i
++)
3411 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3413 if (repr
&& !no_accesses_p (repr
))
3415 if (repr
->grp_scalar_ptr
)
3417 adjustments_count
++;
3418 if (repr
->grp_not_necessarilly_dereferenced
3419 || repr
->grp_maybe_modified
)
3420 VEC_replace (access_p
, representatives
, i
, NULL
);
3424 sra_stats
.scalar_by_ref_to_by_val
++;
3429 int new_components
= decide_one_param_reduction (repr
);
3431 if (new_components
== 0)
3433 VEC_replace (access_p
, representatives
, i
, NULL
);
3434 adjustments_count
++;
3438 adjustments_count
+= new_components
;
3439 sra_stats
.aggregate_params_reduced
++;
3440 sra_stats
.param_reductions_created
+= new_components
;
3447 if (no_accesses_p (repr
))
3450 sra_stats
.deleted_unused_parameters
++;
3452 adjustments_count
++;
3456 if (!proceed
&& dump_file
)
3457 fprintf (dump_file
, "NOT proceeding to change params.\n");
3460 adjustments
= turn_representatives_into_adjustments (representatives
,
3465 VEC_free (access_p
, heap
, representatives
);
3469 /* If a parameter replacement identified by ADJ does not yet exist in the form
3470 of declaration, create it and record it, otherwise return the previously
3474 get_replaced_param_substitute (struct ipa_parm_adjustment
*adj
)
3477 if (!adj
->new_ssa_base
)
3479 char *pretty_name
= make_fancy_name (adj
->base
);
3481 repl
= make_rename_temp (TREE_TYPE (adj
->base
), "ISR");
3482 DECL_NAME (repl
) = get_identifier (pretty_name
);
3483 obstack_free (&name_obstack
, pretty_name
);
3486 add_referenced_var (repl
);
3487 adj
->new_ssa_base
= repl
;
3490 repl
= adj
->new_ssa_base
;
3494 /* Find the first adjustment for a particular parameter BASE in a vector of
3495 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3498 static struct ipa_parm_adjustment
*
3499 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments
, tree base
)
3503 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3504 for (i
= 0; i
< len
; i
++)
3506 struct ipa_parm_adjustment
*adj
;
3508 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3509 if (!adj
->copy_param
&& adj
->base
== base
)
3516 /* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
3517 parameter which is to be removed because its value is not used, replace the
3518 SSA_NAME with a one relating to a created VAR_DECL and replace all of its
3519 uses too. DATA is a pointer to an adjustments vector. */
3522 replace_removed_params_ssa_names (gimple stmt
, void *data
)
3524 VEC (ipa_parm_adjustment_t
, heap
) *adjustments
;
3525 struct ipa_parm_adjustment
*adj
;
3526 tree lhs
, decl
, repl
, name
;
3528 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3529 if (gimple_code (stmt
) == GIMPLE_PHI
)
3530 lhs
= gimple_phi_result (stmt
);
3531 else if (is_gimple_assign (stmt
))
3532 lhs
= gimple_assign_lhs (stmt
);
3533 else if (is_gimple_call (stmt
))
3534 lhs
= gimple_call_lhs (stmt
);
3538 if (TREE_CODE (lhs
) != SSA_NAME
)
3540 decl
= SSA_NAME_VAR (lhs
);
3541 if (TREE_CODE (decl
) != PARM_DECL
)
3544 adj
= get_adjustment_for_base (adjustments
, decl
);
3548 repl
= get_replaced_param_substitute (adj
);
3549 name
= make_ssa_name (repl
, stmt
);
3553 fprintf (dump_file
, "replacing an SSA name of a removed param ");
3554 print_generic_expr (dump_file
, lhs
, 0);
3555 fprintf (dump_file
, " with ");
3556 print_generic_expr (dump_file
, name
, 0);
3557 fprintf (dump_file
, "\n");
3560 if (is_gimple_assign (stmt
))
3561 gimple_assign_set_lhs (stmt
, name
);
3562 else if (is_gimple_call (stmt
))
3563 gimple_call_set_lhs (stmt
, name
);
3565 gimple_phi_set_result (stmt
, name
);
3567 replace_uses_by (lhs
, name
);
3571 /* Callback for scan_function and helper to sra_ipa_modify_assign. If the
3572 expression *EXPR should be replaced by a reduction of a parameter, do so.
3573 DATA is a pointer to a vector of adjustments. DONT_CONVERT specifies
3574 whether the function should care about type incompatibility the current and
3575 new expressions. If it is true, the function will leave incompatibility
3576 issues to the caller.
3578 When called directly by scan_function, DONT_CONVERT is true when the EXPR is
3579 a write (LHS) expression. */
3582 sra_ipa_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
3583 bool dont_convert
, void *data
)
3585 ipa_parm_adjustment_vec adjustments
;
3587 struct ipa_parm_adjustment
*adj
, *cand
= NULL
;
3588 HOST_WIDE_INT offset
, size
, max_size
;
3591 adjustments
= (VEC (ipa_parm_adjustment_t
, heap
) *) data
;
3592 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3594 if (TREE_CODE (*expr
) == BIT_FIELD_REF
3595 || TREE_CODE (*expr
) == IMAGPART_EXPR
3596 || TREE_CODE (*expr
) == REALPART_EXPR
)
3598 expr
= &TREE_OPERAND (*expr
, 0);
3599 dont_convert
= false;
3602 base
= get_ref_base_and_extent (*expr
, &offset
, &size
, &max_size
);
3603 if (!base
|| size
== -1 || max_size
== -1)
3606 if (INDIRECT_REF_P (base
))
3607 base
= TREE_OPERAND (base
, 0);
3609 base
= get_ssa_base_param (base
);
3610 if (!base
|| TREE_CODE (base
) != PARM_DECL
)
3613 for (i
= 0; i
< len
; i
++)
3615 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3617 if (adj
->base
== base
&&
3618 (adj
->offset
== offset
|| adj
->remove_param
))
3624 if (!cand
|| cand
->copy_param
|| cand
->remove_param
)
3630 src
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (cand
->reduction
)),
3632 folded
= gimple_fold_indirect_ref (src
);
3637 src
= cand
->reduction
;
3639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3641 fprintf (dump_file
, "About to replace expr ");
3642 print_generic_expr (dump_file
, *expr
, 0);
3643 fprintf (dump_file
, " with ");
3644 print_generic_expr (dump_file
, src
, 0);
3645 fprintf (dump_file
, "\n");
3649 && !useless_type_conversion_p (TREE_TYPE (*expr
), cand
->type
))
3651 tree vce
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (*expr
), src
);
3659 /* Callback for scan_function to process assign statements. Performs
3660 essentially the same function like sra_ipa_modify_expr. */
3662 static enum scan_assign_result
3663 sra_ipa_modify_assign (gimple
*stmt_ptr
, gimple_stmt_iterator
*gsi
, void *data
)
3665 gimple stmt
= *stmt_ptr
;
3666 tree
*lhs_p
, *rhs_p
;
3669 if (!gimple_assign_single_p (stmt
))
3672 rhs_p
= gimple_assign_rhs1_ptr (stmt
);
3673 lhs_p
= gimple_assign_lhs_ptr (stmt
);
3675 any
= sra_ipa_modify_expr (rhs_p
, gsi
, true, data
);
3676 any
|= sra_ipa_modify_expr (lhs_p
, gsi
, true, data
);
3679 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p
), TREE_TYPE (*rhs_p
)))
3681 location_t loc
= gimple_location (stmt
);
3682 tree vce
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
3683 TREE_TYPE (*lhs_p
), *rhs_p
);
3684 tree tmp
= force_gimple_operand_gsi (gsi
, vce
, true, NULL_TREE
,
3685 true, GSI_SAME_STMT
);
3687 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
3690 return SRA_SA_PROCESSED
;
3696 /* Call gimple_debug_bind_reset_value on all debug statements describing
3697 gimple register parameters that are being removed or replaced. */
3700 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments
)
3704 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3705 for (i
= 0; i
< len
; i
++)
3707 struct ipa_parm_adjustment
*adj
;
3708 imm_use_iterator ui
;
3712 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3713 if (adj
->copy_param
|| !is_gimple_reg (adj
->base
))
3715 name
= gimple_default_def (cfun
, adj
->base
);
3718 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
3720 /* All other users must have been removed by scan_function. */
3721 gcc_assert (is_gimple_debug (stmt
));
3722 gimple_debug_bind_reset_value (stmt
);
3728 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
3731 convert_callers (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3733 tree old_cur_fndecl
= current_function_decl
;
3734 struct cgraph_edge
*cs
;
3735 basic_block this_block
;
3736 bitmap recomputed_callers
= BITMAP_ALLOC (NULL
);
3738 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3740 current_function_decl
= cs
->caller
->decl
;
3741 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
3744 fprintf (dump_file
, "Adjusting call (%i -> %i) %s -> %s\n",
3745 cs
->caller
->uid
, cs
->callee
->uid
,
3746 cgraph_node_name (cs
->caller
),
3747 cgraph_node_name (cs
->callee
));
3749 ipa_modify_call_arguments (cs
, cs
->call_stmt
, adjustments
);
3754 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3755 if (!bitmap_bit_p (recomputed_callers
, cs
->caller
->uid
))
3757 compute_inline_parameters (cs
->caller
);
3758 bitmap_set_bit (recomputed_callers
, cs
->caller
->uid
);
3760 BITMAP_FREE (recomputed_callers
);
3762 current_function_decl
= old_cur_fndecl
;
3763 FOR_EACH_BB (this_block
)
3765 gimple_stmt_iterator gsi
;
3767 for (gsi
= gsi_start_bb (this_block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3769 gimple stmt
= gsi_stmt (gsi
);
3770 if (gimple_code (stmt
) == GIMPLE_CALL
3771 && gimple_call_fndecl (stmt
) == node
->decl
)
3774 fprintf (dump_file
, "Adjusting recursive call");
3775 ipa_modify_call_arguments (NULL
, stmt
, adjustments
);
3783 /* Perform all the modification required in IPA-SRA for NODE to have parameters
3784 as given in ADJUSTMENTS. */
3787 modify_function (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
3789 ipa_modify_formal_parameters (current_function_decl
, adjustments
, "ISRA");
3790 scan_function (sra_ipa_modify_expr
, sra_ipa_modify_assign
,
3791 replace_removed_params_ssa_names
, false, adjustments
);
3792 sra_ipa_reset_debug_stmts (adjustments
);
3793 convert_callers (node
, adjustments
);
3794 cgraph_make_node_local (node
);
3798 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
3799 attributes, return true otherwise. NODE is the cgraph node of the current
3803 ipa_sra_preliminary_function_checks (struct cgraph_node
*node
)
3805 if (!cgraph_node_can_be_local_p (node
))
3808 fprintf (dump_file
, "Function not local to this compilation unit.\n");
3812 if (DECL_VIRTUAL_P (current_function_decl
))
3815 fprintf (dump_file
, "Function is a virtual method.\n");
3819 if ((DECL_COMDAT (node
->decl
) || DECL_EXTERNAL (node
->decl
))
3820 && node
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
3823 fprintf (dump_file
, "Function too big to be made truly local.\n");
3831 "Function has no callers in this compilation unit.\n");
3838 fprintf (dump_file
, "Function uses stdarg. \n");
3845 /* Perform early interprocedural SRA. */
3848 ipa_early_sra (void)
3850 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
3851 ipa_parm_adjustment_vec adjustments
;
3854 if (!ipa_sra_preliminary_function_checks (node
))
3858 sra_mode
= SRA_MODE_EARLY_IPA
;
3860 if (!find_param_candidates ())
3863 fprintf (dump_file
, "Function has no IPA-SRA candidates.\n");
3867 bb_dereferences
= XCNEWVEC (HOST_WIDE_INT
,
3869 * last_basic_block_for_function (cfun
));
3870 final_bbs
= BITMAP_ALLOC (NULL
);
3872 scan_function (build_access_from_expr
, build_accesses_from_assign
,
3874 if (encountered_apply_args
)
3877 fprintf (dump_file
, "Function calls __builtin_apply_args().\n");
3881 adjustments
= analyze_all_param_acesses ();
3885 ipa_dump_param_adjustments (dump_file
, adjustments
, current_function_decl
);
3887 modify_function (node
, adjustments
);
3888 VEC_free (ipa_parm_adjustment_t
, heap
, adjustments
);
3889 ret
= TODO_update_ssa
;
3891 statistics_counter_event (cfun
, "Unused parameters deleted",
3892 sra_stats
.deleted_unused_parameters
);
3893 statistics_counter_event (cfun
, "Scalar parameters converted to by-value",
3894 sra_stats
.scalar_by_ref_to_by_val
);
3895 statistics_counter_event (cfun
, "Aggregate parameters broken up",
3896 sra_stats
.aggregate_params_reduced
);
3897 statistics_counter_event (cfun
, "Aggregate parameter components created",
3898 sra_stats
.param_reductions_created
);
3901 BITMAP_FREE (final_bbs
);
3902 free (bb_dereferences
);
3904 sra_deinitialize ();
3908 /* Return if early ipa sra shall be performed. */
3910 ipa_early_sra_gate (void)
3912 return flag_ipa_sra
;
3915 struct gimple_opt_pass pass_early_ipa_sra
=
3919 "eipa_sra", /* name */
3920 ipa_early_sra_gate
, /* gate */
3921 ipa_early_sra
, /* execute */
3924 0, /* static_pass_number */
3925 TV_IPA_SRA
, /* tv_id */
3926 0, /* properties_required */
3927 0, /* properties_provided */
3928 0, /* properties_destroyed */
3929 0, /* todo_flags_start */
3930 TODO_dump_func
| TODO_dump_cgraph
/* todo_flags_finish */