1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009, 2010 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 "tree-pretty-print.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
92 #include "tree-inline.h"
93 #include "gimple-pretty-print.h"
95 /* Enumeration of all aggregate reductions we can do. */
96 enum sra_mode
{ SRA_MODE_EARLY_IPA
, /* early call regularization */
97 SRA_MODE_EARLY_INTRA
, /* early intraprocedural SRA */
98 SRA_MODE_INTRA
}; /* late intraprocedural SRA */
100 /* Global variable describing which aggregate reduction we are performing at
102 static enum sra_mode sra_mode
;
106 /* ACCESS represents each access to an aggregate variable (as a whole or a
107 part). It can also represent a group of accesses that refer to exactly the
108 same fragment of an aggregate (i.e. those that have exactly the same offset
109 and size). Such representatives for a single aggregate, once determined,
110 are linked in a linked list and have the group fields set.
112 Moreover, when doing intraprocedural SRA, a tree is built from those
113 representatives (by the means of first_child and next_sibling pointers), in
114 which all items in a subtree are "within" the root, i.e. their offset is
115 greater or equal to offset of the root and offset+size is smaller or equal
116 to offset+size of the root. Children of an access are sorted by offset.
118 Note that accesses to parts of vector and complex number types always
119 represented by an access to the whole complex number or a vector. It is a
120 duty of the modifying functions to replace them appropriately. */
124 /* Values returned by `get_ref_base_and_extent' for each component reference
125 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
126 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
127 HOST_WIDE_INT offset
;
131 /* Expression. It is context dependent so do not use it to create new
132 expressions to access the original aggregate. See PR 42154 for a
138 /* The statement this access belongs to. */
141 /* Next group representative for this aggregate. */
142 struct access
*next_grp
;
144 /* Pointer to the group representative. Pointer to itself if the struct is
145 the representative. */
146 struct access
*group_representative
;
148 /* If this access has any children (in terms of the definition above), this
149 points to the first one. */
150 struct access
*first_child
;
152 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
153 described above. In IPA-SRA this is a pointer to the next access
154 belonging to the same group (having the same representative). */
155 struct access
*next_sibling
;
157 /* Pointers to the first and last element in the linked list of assign
159 struct assign_link
*first_link
, *last_link
;
161 /* Pointer to the next access in the work queue. */
162 struct access
*next_queued
;
164 /* Replacement variable for this access "region." Never to be accessed
165 directly, always only by the means of get_access_replacement() and only
166 when grp_to_be_replaced flag is set. */
167 tree replacement_decl
;
169 /* Is this particular access write access? */
172 /* Is this access an artificial one created to scalarize some record
174 unsigned total_scalarization
: 1;
176 /* Is this access currently in the work queue? */
177 unsigned grp_queued
: 1;
179 /* Does this group contain a write access? This flag is propagated down the
181 unsigned grp_write
: 1;
183 /* Does this group contain a read access? This flag is propagated down the
185 unsigned grp_read
: 1;
187 /* Does this group contain a read access that comes from an assignment
188 statement? This flag is propagated down the access tree. */
189 unsigned grp_assignment_read
: 1;
191 /* Other passes of the analysis use this bit to make function
192 analyze_access_subtree create scalar replacements for this group if
194 unsigned grp_hint
: 1;
196 /* Is the subtree rooted in this access fully covered by scalar
198 unsigned grp_covered
: 1;
200 /* If set to true, this access and all below it in an access tree must not be
202 unsigned grp_unscalarizable_region
: 1;
204 /* Whether data have been written to parts of the aggregate covered by this
205 access which is not to be scalarized. This flag is propagated up in the
207 unsigned grp_unscalarized_data
: 1;
209 /* Does this access and/or group contain a write access through a
211 unsigned grp_partial_lhs
: 1;
213 /* Set when a scalar replacement should be created for this variable. We do
214 the decision and creation at different places because create_tmp_var
215 cannot be called from within FOR_EACH_REFERENCED_VAR. */
216 unsigned grp_to_be_replaced
: 1;
218 /* Is it possible that the group refers to data which might be (directly or
219 otherwise) modified? */
220 unsigned grp_maybe_modified
: 1;
222 /* Set when this is a representative of a pointer to scalar (i.e. by
223 reference) parameter which we consider for turning into a plain scalar
224 (i.e. a by value parameter). */
225 unsigned grp_scalar_ptr
: 1;
227 /* Set when we discover that this pointer is not safe to dereference in the
229 unsigned grp_not_necessarilly_dereferenced
: 1;
232 typedef struct access
*access_p
;
234 DEF_VEC_P (access_p
);
235 DEF_VEC_ALLOC_P (access_p
, heap
);
237 /* Alloc pool for allocating access structures. */
238 static alloc_pool access_pool
;
240 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
241 are used to propagate subaccesses from rhs to lhs as long as they don't
242 conflict with what is already there. */
245 struct access
*lacc
, *racc
;
246 struct assign_link
*next
;
249 /* Alloc pool for allocating assign link structures. */
250 static alloc_pool link_pool
;
252 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
253 static struct pointer_map_t
*base_access_vec
;
255 /* Bitmap of candidates. */
256 static bitmap candidate_bitmap
;
258 /* Bitmap of candidates which we should try to entirely scalarize away and
259 those which cannot be (because they are and need be used as a whole). */
260 static bitmap should_scalarize_away_bitmap
, cannot_scalarize_away_bitmap
;
262 /* Obstack for creation of fancy names. */
263 static struct obstack name_obstack
;
265 /* Head of a linked list of accesses that need to have its subaccesses
266 propagated to their assignment counterparts. */
267 static struct access
*work_queue_head
;
269 /* Number of parameters of the analyzed function when doing early ipa SRA. */
270 static int func_param_count
;
272 /* scan_function sets the following to true if it encounters a call to
273 __builtin_apply_args. */
274 static bool encountered_apply_args
;
276 /* Set by scan_function when it finds a recursive call. */
277 static bool encountered_recursive_call
;
279 /* Set by scan_function when it finds a recursive call with less actual
280 arguments than formal parameters.. */
281 static bool encountered_unchangable_recursive_call
;
283 /* This is a table in which for each basic block and parameter there is a
284 distance (offset + size) in that parameter which is dereferenced and
285 accessed in that BB. */
286 static HOST_WIDE_INT
*bb_dereferences
;
287 /* Bitmap of BBs that can cause the function to "stop" progressing by
288 returning, throwing externally, looping infinitely or calling a function
289 which might abort etc.. */
290 static bitmap final_bbs
;
292 /* Representative of no accesses at all. */
293 static struct access no_accesses_representant
;
295 /* Predicate to test the special value. */
298 no_accesses_p (struct access
*access
)
300 return access
== &no_accesses_representant
;
303 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
304 representative fields are dumped, otherwise those which only describe the
305 individual access are. */
309 /* Number of processed aggregates is readily available in
310 analyze_all_variable_accesses and so is not stored here. */
312 /* Number of created scalar replacements. */
315 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
319 /* Number of statements created by generate_subtree_copies. */
322 /* Number of statements created by load_assign_lhs_subreplacements. */
325 /* Number of times sra_modify_assign has deleted a statement. */
328 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
329 RHS reparately due to type conversions or nonexistent matching
331 int separate_lhs_rhs_handling
;
333 /* Number of parameters that were removed because they were unused. */
334 int deleted_unused_parameters
;
336 /* Number of scalars passed as parameters by reference that have been
337 converted to be passed by value. */
338 int scalar_by_ref_to_by_val
;
340 /* Number of aggregate parameters that were replaced by one or more of their
342 int aggregate_params_reduced
;
344 /* Numbber of components created when splitting aggregate parameters. */
345 int param_reductions_created
;
349 dump_access (FILE *f
, struct access
*access
, bool grp
)
351 fprintf (f
, "access { ");
352 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
353 print_generic_expr (f
, access
->base
, 0);
354 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
355 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
356 fprintf (f
, ", expr = ");
357 print_generic_expr (f
, access
->expr
, 0);
358 fprintf (f
, ", type = ");
359 print_generic_expr (f
, access
->type
, 0);
361 fprintf (f
, ", grp_write = %d, total_scalarization = %d, "
362 "grp_read = %d, grp_hint = %d, grp_assignment_read = %d,"
363 "grp_covered = %d, grp_unscalarizable_region = %d, "
364 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
365 "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
366 "grp_not_necessarilly_dereferenced = %d\n",
367 access
->grp_write
, access
->total_scalarization
,
368 access
->grp_read
, access
->grp_hint
, access
->grp_assignment_read
,
369 access
->grp_covered
, access
->grp_unscalarizable_region
,
370 access
->grp_unscalarized_data
, access
->grp_partial_lhs
,
371 access
->grp_to_be_replaced
, access
->grp_maybe_modified
,
372 access
->grp_not_necessarilly_dereferenced
);
374 fprintf (f
, ", write = %d, total_scalarization = %d, "
375 "grp_partial_lhs = %d\n",
376 access
->write
, access
->total_scalarization
,
377 access
->grp_partial_lhs
);
380 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
383 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
389 for (i
= 0; i
< level
; i
++)
390 fputs ("* ", dump_file
);
392 dump_access (f
, access
, true);
394 if (access
->first_child
)
395 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
397 access
= access
->next_sibling
;
402 /* Dump all access trees for a variable, given the pointer to the first root in
406 dump_access_tree (FILE *f
, struct access
*access
)
408 for (; access
; access
= access
->next_grp
)
409 dump_access_tree_1 (f
, access
, 0);
412 /* Return true iff ACC is non-NULL and has subaccesses. */
415 access_has_children_p (struct access
*acc
)
417 return acc
&& acc
->first_child
;
420 /* Return a vector of pointers to accesses for the variable given in BASE or
421 NULL if there is none. */
423 static VEC (access_p
, heap
) *
424 get_base_access_vector (tree base
)
428 slot
= pointer_map_contains (base_access_vec
, base
);
432 return *(VEC (access_p
, heap
) **) slot
;
435 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
436 in ACCESS. Return NULL if it cannot be found. */
438 static struct access
*
439 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
442 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
444 struct access
*child
= access
->first_child
;
446 while (child
&& (child
->offset
+ child
->size
<= offset
))
447 child
= child
->next_sibling
;
454 /* Return the first group representative for DECL or NULL if none exists. */
456 static struct access
*
457 get_first_repr_for_decl (tree base
)
459 VEC (access_p
, heap
) *access_vec
;
461 access_vec
= get_base_access_vector (base
);
465 return VEC_index (access_p
, access_vec
, 0);
468 /* Find an access representative for the variable BASE and given OFFSET and
469 SIZE. Requires that access trees have already been built. Return NULL if
470 it cannot be found. */
472 static struct access
*
473 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
476 struct access
*access
;
478 access
= get_first_repr_for_decl (base
);
479 while (access
&& (access
->offset
+ access
->size
<= offset
))
480 access
= access
->next_grp
;
484 return find_access_in_subtree (access
, offset
, size
);
487 /* Add LINK to the linked list of assign links of RACC. */
489 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
491 gcc_assert (link
->racc
== racc
);
493 if (!racc
->first_link
)
495 gcc_assert (!racc
->last_link
);
496 racc
->first_link
= link
;
499 racc
->last_link
->next
= link
;
501 racc
->last_link
= link
;
505 /* Move all link structures in their linked list in OLD_RACC to the linked list
508 relink_to_new_repr (struct access
*new_racc
, struct access
*old_racc
)
510 if (!old_racc
->first_link
)
512 gcc_assert (!old_racc
->last_link
);
516 if (new_racc
->first_link
)
518 gcc_assert (!new_racc
->last_link
->next
);
519 gcc_assert (!old_racc
->last_link
|| !old_racc
->last_link
->next
);
521 new_racc
->last_link
->next
= old_racc
->first_link
;
522 new_racc
->last_link
= old_racc
->last_link
;
526 gcc_assert (!new_racc
->last_link
);
528 new_racc
->first_link
= old_racc
->first_link
;
529 new_racc
->last_link
= old_racc
->last_link
;
531 old_racc
->first_link
= old_racc
->last_link
= NULL
;
534 /* Add ACCESS to the work queue (which is actually a stack). */
537 add_access_to_work_queue (struct access
*access
)
539 if (!access
->grp_queued
)
541 gcc_assert (!access
->next_queued
);
542 access
->next_queued
= work_queue_head
;
543 access
->grp_queued
= 1;
544 work_queue_head
= access
;
548 /* Pop an access from the work queue, and return it, assuming there is one. */
550 static struct access
*
551 pop_access_from_work_queue (void)
553 struct access
*access
= work_queue_head
;
555 work_queue_head
= access
->next_queued
;
556 access
->next_queued
= NULL
;
557 access
->grp_queued
= 0;
562 /* Allocate necessary structures. */
565 sra_initialize (void)
567 candidate_bitmap
= BITMAP_ALLOC (NULL
);
568 should_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
569 cannot_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
570 gcc_obstack_init (&name_obstack
);
571 access_pool
= create_alloc_pool ("SRA accesses", sizeof (struct access
), 16);
572 link_pool
= create_alloc_pool ("SRA links", sizeof (struct assign_link
), 16);
573 base_access_vec
= pointer_map_create ();
574 memset (&sra_stats
, 0, sizeof (sra_stats
));
575 encountered_apply_args
= false;
576 encountered_recursive_call
= false;
577 encountered_unchangable_recursive_call
= false;
580 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
583 delete_base_accesses (const void *key ATTRIBUTE_UNUSED
, void **value
,
584 void *data ATTRIBUTE_UNUSED
)
586 VEC (access_p
, heap
) *access_vec
;
587 access_vec
= (VEC (access_p
, heap
) *) *value
;
588 VEC_free (access_p
, heap
, access_vec
);
593 /* Deallocate all general structures. */
596 sra_deinitialize (void)
598 BITMAP_FREE (candidate_bitmap
);
599 BITMAP_FREE (should_scalarize_away_bitmap
);
600 BITMAP_FREE (cannot_scalarize_away_bitmap
);
601 free_alloc_pool (access_pool
);
602 free_alloc_pool (link_pool
);
603 obstack_free (&name_obstack
, NULL
);
605 pointer_map_traverse (base_access_vec
, delete_base_accesses
, NULL
);
606 pointer_map_destroy (base_access_vec
);
609 /* Remove DECL from candidates for SRA and write REASON to the dump file if
612 disqualify_candidate (tree decl
, const char *reason
)
614 bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
));
616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
618 fprintf (dump_file
, "! Disqualifying ");
619 print_generic_expr (dump_file
, decl
, 0);
620 fprintf (dump_file
, " - %s\n", reason
);
624 /* Return true iff the type contains a field or an element which does not allow
628 type_internals_preclude_sra_p (tree type
)
633 switch (TREE_CODE (type
))
637 case QUAL_UNION_TYPE
:
638 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
639 if (TREE_CODE (fld
) == FIELD_DECL
)
641 tree ft
= TREE_TYPE (fld
);
643 if (TREE_THIS_VOLATILE (fld
)
644 || !DECL_FIELD_OFFSET (fld
) || !DECL_SIZE (fld
)
645 || !host_integerp (DECL_FIELD_OFFSET (fld
), 1)
646 || !host_integerp (DECL_SIZE (fld
), 1))
649 if (AGGREGATE_TYPE_P (ft
)
650 && type_internals_preclude_sra_p (ft
))
657 et
= TREE_TYPE (type
);
659 if (AGGREGATE_TYPE_P (et
))
660 return type_internals_preclude_sra_p (et
);
669 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
670 base variable if it is. Return T if it is not an SSA_NAME. */
673 get_ssa_base_param (tree t
)
675 if (TREE_CODE (t
) == SSA_NAME
)
677 if (SSA_NAME_IS_DEFAULT_DEF (t
))
678 return SSA_NAME_VAR (t
);
685 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
686 belongs to, unless the BB has already been marked as a potentially
690 mark_parm_dereference (tree base
, HOST_WIDE_INT dist
, gimple stmt
)
692 basic_block bb
= gimple_bb (stmt
);
693 int idx
, parm_index
= 0;
696 if (bitmap_bit_p (final_bbs
, bb
->index
))
699 for (parm
= DECL_ARGUMENTS (current_function_decl
);
700 parm
&& parm
!= base
;
701 parm
= DECL_CHAIN (parm
))
704 gcc_assert (parm_index
< func_param_count
);
706 idx
= bb
->index
* func_param_count
+ parm_index
;
707 if (bb_dereferences
[idx
] < dist
)
708 bb_dereferences
[idx
] = dist
;
711 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
712 the three fields. Also add it to the vector of accesses corresponding to
713 the base. Finally, return the new access. */
715 static struct access
*
716 create_access_1 (tree base
, HOST_WIDE_INT offset
, HOST_WIDE_INT size
)
718 VEC (access_p
, heap
) *vec
;
719 struct access
*access
;
722 access
= (struct access
*) pool_alloc (access_pool
);
723 memset (access
, 0, sizeof (struct access
));
725 access
->offset
= offset
;
728 slot
= pointer_map_contains (base_access_vec
, base
);
730 vec
= (VEC (access_p
, heap
) *) *slot
;
732 vec
= VEC_alloc (access_p
, heap
, 32);
734 VEC_safe_push (access_p
, heap
, vec
, access
);
736 *((struct VEC (access_p
,heap
) **)
737 pointer_map_insert (base_access_vec
, base
)) = vec
;
742 /* Create and insert access for EXPR. Return created access, or NULL if it is
745 static struct access
*
746 create_access (tree expr
, gimple stmt
, bool write
)
748 struct access
*access
;
749 HOST_WIDE_INT offset
, size
, max_size
;
751 bool ptr
, unscalarizable_region
= false;
753 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
755 if (sra_mode
== SRA_MODE_EARLY_IPA
756 && TREE_CODE (base
) == MEM_REF
)
758 base
= get_ssa_base_param (TREE_OPERAND (base
, 0));
766 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
769 if (sra_mode
== SRA_MODE_EARLY_IPA
)
771 if (size
< 0 || size
!= max_size
)
773 disqualify_candidate (base
, "Encountered a variable sized access.");
776 if ((offset
% BITS_PER_UNIT
) != 0 || (size
% BITS_PER_UNIT
) != 0)
778 disqualify_candidate (base
,
779 "Encountered an acces not aligned to a byte.");
784 mark_parm_dereference (base
, offset
+ size
, stmt
);
788 if (size
!= max_size
)
791 unscalarizable_region
= true;
795 disqualify_candidate (base
, "Encountered an unconstrained access.");
800 access
= create_access_1 (base
, offset
, size
);
802 access
->type
= TREE_TYPE (expr
);
803 access
->write
= write
;
804 access
->grp_unscalarizable_region
= unscalarizable_region
;
811 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
812 register types or (recursively) records with only these two kinds of fields.
813 It also returns false if any of these records has a zero-size field as its
814 last field or has a bit-field. */
817 type_consists_of_records_p (tree type
)
820 bool last_fld_has_zero_size
= false;
822 if (TREE_CODE (type
) != RECORD_TYPE
)
825 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
826 if (TREE_CODE (fld
) == FIELD_DECL
)
828 tree ft
= TREE_TYPE (fld
);
830 if (DECL_BIT_FIELD (fld
))
833 if (!is_gimple_reg_type (ft
)
834 && !type_consists_of_records_p (ft
))
837 last_fld_has_zero_size
= tree_low_cst (DECL_SIZE (fld
), 1) == 0;
840 if (last_fld_has_zero_size
)
846 /* Create total_scalarization accesses for all scalar type fields in DECL that
847 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE
848 must be the top-most VAR_DECL representing the variable, OFFSET must be the
849 offset of DECL within BASE. REF must be the memory reference expression for
853 completely_scalarize_record (tree base
, tree decl
, HOST_WIDE_INT offset
,
856 tree fld
, decl_type
= TREE_TYPE (decl
);
858 for (fld
= TYPE_FIELDS (decl_type
); fld
; fld
= DECL_CHAIN (fld
))
859 if (TREE_CODE (fld
) == FIELD_DECL
)
861 HOST_WIDE_INT pos
= offset
+ int_bit_position (fld
);
862 tree ft
= TREE_TYPE (fld
);
863 tree nref
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), ref
, fld
,
866 if (is_gimple_reg_type (ft
))
868 struct access
*access
;
871 size
= tree_low_cst (DECL_SIZE (fld
), 1);
872 access
= create_access_1 (base
, pos
, size
);
875 access
->total_scalarization
= 1;
876 /* Accesses for intraprocedural SRA can have their stmt NULL. */
879 completely_scalarize_record (base
, fld
, pos
, nref
);
884 /* Search the given tree for a declaration by skipping handled components and
885 exclude it from the candidates. */
888 disqualify_base_of_expr (tree t
, const char *reason
)
890 t
= get_base_address (t
);
891 if (sra_mode
== SRA_MODE_EARLY_IPA
892 && TREE_CODE (t
) == MEM_REF
)
893 t
= get_ssa_base_param (TREE_OPERAND (t
, 0));
896 disqualify_candidate (t
, reason
);
899 /* Scan expression EXPR and create access structures for all accesses to
900 candidates for scalarization. Return the created access or NULL if none is
903 static struct access
*
904 build_access_from_expr_1 (tree expr
, gimple stmt
, bool write
)
906 struct access
*ret
= NULL
;
909 if (TREE_CODE (expr
) == BIT_FIELD_REF
910 || TREE_CODE (expr
) == IMAGPART_EXPR
911 || TREE_CODE (expr
) == REALPART_EXPR
)
913 expr
= TREE_OPERAND (expr
, 0);
919 /* We need to dive through V_C_Es in order to get the size of its parameter
920 and not the result type. Ada produces such statements. We are also
921 capable of handling the topmost V_C_E but not any of those buried in other
922 handled components. */
923 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
924 expr
= TREE_OPERAND (expr
, 0);
926 if (contains_view_convert_expr_p (expr
))
928 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
933 switch (TREE_CODE (expr
))
936 if (TREE_CODE (TREE_OPERAND (expr
, 0)) != ADDR_EXPR
937 && sra_mode
!= SRA_MODE_EARLY_IPA
)
945 case ARRAY_RANGE_REF
:
946 ret
= create_access (expr
, stmt
, write
);
953 if (write
&& partial_ref
&& ret
)
954 ret
->grp_partial_lhs
= 1;
959 /* Scan expression EXPR and create access structures for all accesses to
960 candidates for scalarization. Return true if any access has been inserted.
961 STMT must be the statement from which the expression is taken, WRITE must be
962 true if the expression is a store and false otherwise. */
965 build_access_from_expr (tree expr
, gimple stmt
, bool write
)
967 struct access
*access
;
969 access
= build_access_from_expr_1 (expr
, stmt
, write
);
972 /* This means the aggregate is accesses as a whole in a way other than an
973 assign statement and thus cannot be removed even if we had a scalar
974 replacement for everything. */
975 if (cannot_scalarize_away_bitmap
)
976 bitmap_set_bit (cannot_scalarize_away_bitmap
, DECL_UID (access
->base
));
982 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
983 modes in which it matters, return true iff they have been disqualified. RHS
984 may be NULL, in that case ignore it. If we scalarize an aggregate in
985 intra-SRA we may need to add statements after each statement. This is not
986 possible if a statement unconditionally has to end the basic block. */
988 disqualify_ops_if_throwing_stmt (gimple stmt
, tree lhs
, tree rhs
)
990 if ((sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
991 && (stmt_can_throw_internal (stmt
) || stmt_ends_bb_p (stmt
)))
993 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
995 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
1001 /* Scan expressions occuring in STMT, create access structures for all accesses
1002 to candidates for scalarization and remove those candidates which occur in
1003 statements or expressions that prevent them from being split apart. Return
1004 true if any access has been inserted. */
1007 build_accesses_from_assign (gimple stmt
)
1010 struct access
*lacc
, *racc
;
1012 if (!gimple_assign_single_p (stmt
))
1015 lhs
= gimple_assign_lhs (stmt
);
1016 rhs
= gimple_assign_rhs1 (stmt
);
1018 if (disqualify_ops_if_throwing_stmt (stmt
, lhs
, rhs
))
1021 racc
= build_access_from_expr_1 (rhs
, stmt
, false);
1022 lacc
= build_access_from_expr_1 (lhs
, stmt
, true);
1026 racc
->grp_assignment_read
= 1;
1027 if (should_scalarize_away_bitmap
&& !gimple_has_volatile_ops (stmt
)
1028 && !is_gimple_reg_type (racc
->type
))
1029 bitmap_set_bit (should_scalarize_away_bitmap
, DECL_UID (racc
->base
));
1033 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1034 && !lacc
->grp_unscalarizable_region
1035 && !racc
->grp_unscalarizable_region
1036 && AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
1037 /* FIXME: Turn the following line into an assert after PR 40058 is
1039 && lacc
->size
== racc
->size
1040 && useless_type_conversion_p (lacc
->type
, racc
->type
))
1042 struct assign_link
*link
;
1044 link
= (struct assign_link
*) pool_alloc (link_pool
);
1045 memset (link
, 0, sizeof (struct assign_link
));
1050 add_link_to_rhs (racc
, link
);
1053 return lacc
|| racc
;
1056 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1057 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1060 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED
, tree op
,
1061 void *data ATTRIBUTE_UNUSED
)
1063 op
= get_base_address (op
);
1066 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
1071 /* Return true iff callsite CALL has at least as many actual arguments as there
1072 are formal parameters of the function currently processed by IPA-SRA. */
1075 callsite_has_enough_arguments_p (gimple call
)
1077 return gimple_call_num_args (call
) >= (unsigned) func_param_count
;
1080 /* Scan function and look for interesting expressions and create access
1081 structures for them. Return true iff any access is created. */
1084 scan_function (void)
1091 gimple_stmt_iterator gsi
;
1092 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1094 gimple stmt
= gsi_stmt (gsi
);
1098 if (final_bbs
&& stmt_can_throw_external (stmt
))
1099 bitmap_set_bit (final_bbs
, bb
->index
);
1100 switch (gimple_code (stmt
))
1103 t
= gimple_return_retval (stmt
);
1105 ret
|= build_access_from_expr (t
, stmt
, false);
1107 bitmap_set_bit (final_bbs
, bb
->index
);
1111 ret
|= build_accesses_from_assign (stmt
);
1115 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1116 ret
|= build_access_from_expr (gimple_call_arg (stmt
, i
),
1119 if (sra_mode
== SRA_MODE_EARLY_IPA
)
1121 tree dest
= gimple_call_fndecl (stmt
);
1122 int flags
= gimple_call_flags (stmt
);
1126 if (DECL_BUILT_IN_CLASS (dest
) == BUILT_IN_NORMAL
1127 && DECL_FUNCTION_CODE (dest
) == BUILT_IN_APPLY_ARGS
)
1128 encountered_apply_args
= true;
1129 if (cgraph_get_node (dest
)
1130 == cgraph_get_node (current_function_decl
))
1132 encountered_recursive_call
= true;
1133 if (!callsite_has_enough_arguments_p (stmt
))
1134 encountered_unchangable_recursive_call
= true;
1139 && (flags
& (ECF_CONST
| ECF_PURE
)) == 0)
1140 bitmap_set_bit (final_bbs
, bb
->index
);
1143 t
= gimple_call_lhs (stmt
);
1144 if (t
&& !disqualify_ops_if_throwing_stmt (stmt
, t
, NULL
))
1145 ret
|= build_access_from_expr (t
, stmt
, true);
1149 walk_stmt_load_store_addr_ops (stmt
, NULL
, NULL
, NULL
,
1152 bitmap_set_bit (final_bbs
, bb
->index
);
1154 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
1156 t
= TREE_VALUE (gimple_asm_input_op (stmt
, i
));
1157 ret
|= build_access_from_expr (t
, stmt
, false);
1159 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
1161 t
= TREE_VALUE (gimple_asm_output_op (stmt
, i
));
1162 ret
|= build_access_from_expr (t
, stmt
, true);
1175 /* Helper of QSORT function. There are pointers to accesses in the array. An
1176 access is considered smaller than another if it has smaller offset or if the
1177 offsets are the same but is size is bigger. */
1180 compare_access_positions (const void *a
, const void *b
)
1182 const access_p
*fp1
= (const access_p
*) a
;
1183 const access_p
*fp2
= (const access_p
*) b
;
1184 const access_p f1
= *fp1
;
1185 const access_p f2
= *fp2
;
1187 if (f1
->offset
!= f2
->offset
)
1188 return f1
->offset
< f2
->offset
? -1 : 1;
1190 if (f1
->size
== f2
->size
)
1192 if (f1
->type
== f2
->type
)
1194 /* Put any non-aggregate type before any aggregate type. */
1195 else if (!is_gimple_reg_type (f1
->type
)
1196 && is_gimple_reg_type (f2
->type
))
1198 else if (is_gimple_reg_type (f1
->type
)
1199 && !is_gimple_reg_type (f2
->type
))
1201 /* Put any complex or vector type before any other scalar type. */
1202 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1203 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1204 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1205 || TREE_CODE (f2
->type
) == VECTOR_TYPE
))
1207 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1208 || TREE_CODE (f1
->type
) == VECTOR_TYPE
)
1209 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1210 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1212 /* Put the integral type with the bigger precision first. */
1213 else if (INTEGRAL_TYPE_P (f1
->type
)
1214 && INTEGRAL_TYPE_P (f2
->type
))
1215 return TYPE_PRECISION (f2
->type
) - TYPE_PRECISION (f1
->type
);
1216 /* Put any integral type with non-full precision last. */
1217 else if (INTEGRAL_TYPE_P (f1
->type
)
1218 && (TREE_INT_CST_LOW (TYPE_SIZE (f1
->type
))
1219 != TYPE_PRECISION (f1
->type
)))
1221 else if (INTEGRAL_TYPE_P (f2
->type
)
1222 && (TREE_INT_CST_LOW (TYPE_SIZE (f2
->type
))
1223 != TYPE_PRECISION (f2
->type
)))
1225 /* Stabilize the sort. */
1226 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1229 /* We want the bigger accesses first, thus the opposite operator in the next
1231 return f1
->size
> f2
->size
? -1 : 1;
1235 /* Append a name of the declaration to the name obstack. A helper function for
1239 make_fancy_decl_name (tree decl
)
1243 tree name
= DECL_NAME (decl
);
1245 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1246 IDENTIFIER_LENGTH (name
));
1249 sprintf (buffer
, "D%u", DECL_UID (decl
));
1250 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1254 /* Helper for make_fancy_name. */
1257 make_fancy_name_1 (tree expr
)
1264 make_fancy_decl_name (expr
);
1268 switch (TREE_CODE (expr
))
1271 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1272 obstack_1grow (&name_obstack
, '$');
1273 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1277 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1278 obstack_1grow (&name_obstack
, '$');
1279 /* Arrays with only one element may not have a constant as their
1281 index
= TREE_OPERAND (expr
, 1);
1282 if (TREE_CODE (index
) != INTEGER_CST
)
1284 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1285 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1289 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1293 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1294 if (!integer_zerop (TREE_OPERAND (expr
, 1)))
1296 obstack_1grow (&name_obstack
, '$');
1297 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
,
1298 TREE_INT_CST_LOW (TREE_OPERAND (expr
, 1)));
1299 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1306 gcc_unreachable (); /* we treat these as scalars. */
1313 /* Create a human readable name for replacement variable of ACCESS. */
1316 make_fancy_name (tree expr
)
1318 make_fancy_name_1 (expr
);
1319 obstack_1grow (&name_obstack
, '\0');
1320 return XOBFINISH (&name_obstack
, char *);
1323 /* Helper function for build_ref_for_offset.
1325 FIXME: Eventually this should be rewritten to either re-use the
1326 original access expression unshared (which is good for alias
1327 analysis) or to build a MEM_REF expression. */
1330 build_ref_for_offset_1 (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1336 tree tr_size
, index
, minidx
;
1337 HOST_WIDE_INT el_size
;
1339 if (offset
== 0 && exp_type
1340 && types_compatible_p (exp_type
, type
))
1343 switch (TREE_CODE (type
))
1346 case QUAL_UNION_TYPE
:
1348 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1350 HOST_WIDE_INT pos
, size
;
1351 tree expr
, *expr_ptr
;
1353 if (TREE_CODE (fld
) != FIELD_DECL
)
1356 pos
= int_bit_position (fld
);
1357 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1358 tr_size
= DECL_SIZE (fld
);
1359 if (!tr_size
|| !host_integerp (tr_size
, 1))
1361 size
= tree_low_cst (tr_size
, 1);
1367 else if (pos
> offset
|| (pos
+ size
) <= offset
)
1372 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1378 if (build_ref_for_offset_1 (expr_ptr
, TREE_TYPE (fld
),
1379 offset
- pos
, exp_type
))
1389 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1390 if (!tr_size
|| !host_integerp (tr_size
, 1))
1392 el_size
= tree_low_cst (tr_size
, 1);
1394 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1395 if (TREE_CODE (minidx
) != INTEGER_CST
|| el_size
== 0)
1399 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1400 if (!integer_zerop (minidx
))
1401 index
= int_const_binop (PLUS_EXPR
, index
, minidx
, 0);
1402 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1403 NULL_TREE
, NULL_TREE
);
1405 offset
= offset
% el_size
;
1406 type
= TREE_TYPE (type
);
1421 /* Construct an expression that would reference a part of aggregate *EXPR of
1422 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1423 function only determines whether it can build such a reference without
1424 actually doing it, otherwise, the tree it points to is unshared first and
1425 then used as a base for furhter sub-references. */
1428 build_ref_for_offset (tree
*expr
, tree type
, HOST_WIDE_INT offset
,
1429 tree exp_type
, bool allow_ptr
)
1431 location_t loc
= expr
? EXPR_LOCATION (*expr
) : UNKNOWN_LOCATION
;
1434 *expr
= unshare_expr (*expr
);
1436 if (allow_ptr
&& POINTER_TYPE_P (type
))
1438 type
= TREE_TYPE (type
);
1440 *expr
= build_simple_mem_ref_loc (loc
, *expr
);
1443 return build_ref_for_offset_1 (expr
, type
, offset
, exp_type
);
1446 /* Return true iff TYPE is stdarg va_list type. */
1449 is_va_list_type (tree type
)
1451 return TYPE_MAIN_VARIANT (type
) == TYPE_MAIN_VARIANT (va_list_type_node
);
1454 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1455 those with type which is suitable for scalarization. */
1458 find_var_candidates (void)
1461 referenced_var_iterator rvi
;
1464 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1466 if (TREE_CODE (var
) != VAR_DECL
&& TREE_CODE (var
) != PARM_DECL
)
1468 type
= TREE_TYPE (var
);
1470 if (!AGGREGATE_TYPE_P (type
)
1471 || needs_to_live_in_memory (var
)
1472 || TREE_THIS_VOLATILE (var
)
1473 || !COMPLETE_TYPE_P (type
)
1474 || !host_integerp (TYPE_SIZE (type
), 1)
1475 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
1476 || type_internals_preclude_sra_p (type
)
1477 /* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1478 we also want to schedule it rather late. Thus we ignore it in
1480 || (sra_mode
== SRA_MODE_EARLY_INTRA
1481 && is_va_list_type (type
)))
1484 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1488 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1489 print_generic_expr (dump_file
, var
, 0);
1490 fprintf (dump_file
, "\n");
1498 /* Sort all accesses for the given variable, check for partial overlaps and
1499 return NULL if there are any. If there are none, pick a representative for
1500 each combination of offset and size and create a linked list out of them.
1501 Return the pointer to the first representative and make sure it is the first
1502 one in the vector of accesses. */
1504 static struct access
*
1505 sort_and_splice_var_accesses (tree var
)
1507 int i
, j
, access_count
;
1508 struct access
*res
, **prev_acc_ptr
= &res
;
1509 VEC (access_p
, heap
) *access_vec
;
1511 HOST_WIDE_INT low
= -1, high
= 0;
1513 access_vec
= get_base_access_vector (var
);
1516 access_count
= VEC_length (access_p
, access_vec
);
1518 /* Sort by <OFFSET, SIZE>. */
1519 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
1520 compare_access_positions
);
1523 while (i
< access_count
)
1525 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
1526 bool grp_write
= access
->write
;
1527 bool grp_read
= !access
->write
;
1528 bool grp_assignment_read
= access
->grp_assignment_read
;
1529 bool multiple_reads
= false;
1530 bool total_scalarization
= access
->total_scalarization
;
1531 bool grp_partial_lhs
= access
->grp_partial_lhs
;
1532 bool first_scalar
= is_gimple_reg_type (access
->type
);
1533 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
1535 if (first
|| access
->offset
>= high
)
1538 low
= access
->offset
;
1539 high
= access
->offset
+ access
->size
;
1541 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
1544 gcc_assert (access
->offset
>= low
1545 && access
->offset
+ access
->size
<= high
);
1548 while (j
< access_count
)
1550 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
1551 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
1558 multiple_reads
= true;
1562 grp_assignment_read
|= ac2
->grp_assignment_read
;
1563 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
1564 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
1565 total_scalarization
|= ac2
->total_scalarization
;
1566 relink_to_new_repr (access
, ac2
);
1568 /* If there are both aggregate-type and scalar-type accesses with
1569 this combination of size and offset, the comparison function
1570 should have put the scalars first. */
1571 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
1572 ac2
->group_representative
= access
;
1578 access
->group_representative
= access
;
1579 access
->grp_write
= grp_write
;
1580 access
->grp_read
= grp_read
;
1581 access
->grp_assignment_read
= grp_assignment_read
;
1582 access
->grp_hint
= multiple_reads
|| total_scalarization
;
1583 access
->grp_partial_lhs
= grp_partial_lhs
;
1584 access
->grp_unscalarizable_region
= unscalarizable_region
;
1585 if (access
->first_link
)
1586 add_access_to_work_queue (access
);
1588 *prev_acc_ptr
= access
;
1589 prev_acc_ptr
= &access
->next_grp
;
1592 gcc_assert (res
== VEC_index (access_p
, access_vec
, 0));
1596 /* Create a variable for the given ACCESS which determines the type, name and a
1597 few other properties. Return the variable declaration and store it also to
1598 ACCESS->replacement. */
1601 create_access_replacement (struct access
*access
, bool rename
)
1605 repl
= create_tmp_var (access
->type
, "SR");
1607 add_referenced_var (repl
);
1609 mark_sym_for_renaming (repl
);
1611 if (!access
->grp_partial_lhs
1612 && (TREE_CODE (access
->type
) == COMPLEX_TYPE
1613 || TREE_CODE (access
->type
) == VECTOR_TYPE
))
1614 DECL_GIMPLE_REG_P (repl
) = 1;
1616 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
1617 DECL_ARTIFICIAL (repl
) = 1;
1618 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
1620 if (DECL_NAME (access
->base
)
1621 && !DECL_IGNORED_P (access
->base
)
1622 && !DECL_ARTIFICIAL (access
->base
))
1624 char *pretty_name
= make_fancy_name (access
->expr
);
1625 tree debug_expr
= unshare_expr (access
->expr
), d
;
1627 DECL_NAME (repl
) = get_identifier (pretty_name
);
1628 obstack_free (&name_obstack
, pretty_name
);
1630 /* Get rid of any SSA_NAMEs embedded in debug_expr,
1631 as DECL_DEBUG_EXPR isn't considered when looking for still
1632 used SSA_NAMEs and thus they could be freed. All debug info
1633 generation cares is whether something is constant or variable
1634 and that get_ref_base_and_extent works properly on the
1636 for (d
= debug_expr
; handled_component_p (d
); d
= TREE_OPERAND (d
, 0))
1637 switch (TREE_CODE (d
))
1640 case ARRAY_RANGE_REF
:
1641 if (TREE_OPERAND (d
, 1)
1642 && TREE_CODE (TREE_OPERAND (d
, 1)) == SSA_NAME
)
1643 TREE_OPERAND (d
, 1) = SSA_NAME_VAR (TREE_OPERAND (d
, 1));
1644 if (TREE_OPERAND (d
, 3)
1645 && TREE_CODE (TREE_OPERAND (d
, 3)) == SSA_NAME
)
1646 TREE_OPERAND (d
, 3) = SSA_NAME_VAR (TREE_OPERAND (d
, 3));
1649 if (TREE_OPERAND (d
, 2)
1650 && TREE_CODE (TREE_OPERAND (d
, 2)) == SSA_NAME
)
1651 TREE_OPERAND (d
, 2) = SSA_NAME_VAR (TREE_OPERAND (d
, 2));
1656 SET_DECL_DEBUG_EXPR (repl
, debug_expr
);
1657 DECL_DEBUG_EXPR_IS_FROM (repl
) = 1;
1658 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
1661 TREE_NO_WARNING (repl
) = 1;
1665 fprintf (dump_file
, "Created a replacement for ");
1666 print_generic_expr (dump_file
, access
->base
, 0);
1667 fprintf (dump_file
, " offset: %u, size: %u: ",
1668 (unsigned) access
->offset
, (unsigned) access
->size
);
1669 print_generic_expr (dump_file
, repl
, 0);
1670 fprintf (dump_file
, "\n");
1672 sra_stats
.replacements
++;
1677 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1680 get_access_replacement (struct access
*access
)
1682 gcc_assert (access
->grp_to_be_replaced
);
1684 if (!access
->replacement_decl
)
1685 access
->replacement_decl
= create_access_replacement (access
, true);
1686 return access
->replacement_decl
;
1689 /* Return ACCESS scalar replacement, create it if it does not exist yet but do
1690 not mark it for renaming. */
1693 get_unrenamed_access_replacement (struct access
*access
)
1695 gcc_assert (!access
->grp_to_be_replaced
);
1697 if (!access
->replacement_decl
)
1698 access
->replacement_decl
= create_access_replacement (access
, false);
1699 return access
->replacement_decl
;
1703 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1704 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1705 to it is not "within" the root. Return false iff some accesses partially
1709 build_access_subtree (struct access
**access
)
1711 struct access
*root
= *access
, *last_child
= NULL
;
1712 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1714 *access
= (*access
)->next_grp
;
1715 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
1718 root
->first_child
= *access
;
1720 last_child
->next_sibling
= *access
;
1721 last_child
= *access
;
1723 if (!build_access_subtree (access
))
1727 if (*access
&& (*access
)->offset
< limit
)
1733 /* Build a tree of access representatives, ACCESS is the pointer to the first
1734 one, others are linked in a list by the next_grp field. Return false iff
1735 some accesses partially overlap. */
1738 build_access_trees (struct access
*access
)
1742 struct access
*root
= access
;
1744 if (!build_access_subtree (&access
))
1746 root
->next_grp
= access
;
1751 /* Return true if expr contains some ARRAY_REFs into a variable bounded
1755 expr_with_var_bounded_array_refs_p (tree expr
)
1757 while (handled_component_p (expr
))
1759 if (TREE_CODE (expr
) == ARRAY_REF
1760 && !host_integerp (array_ref_low_bound (expr
), 0))
1762 expr
= TREE_OPERAND (expr
, 0);
1767 enum mark_read_status
{ SRA_MR_NOT_READ
, SRA_MR_READ
, SRA_MR_ASSIGN_READ
};
1769 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1770 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all
1771 sorts of access flags appropriately along the way, notably always set
1772 grp_read and grp_assign_read according to MARK_READ and grp_write when
1773 MARK_WRITE is true. */
1776 analyze_access_subtree (struct access
*root
, bool allow_replacements
,
1777 enum mark_read_status mark_read
, bool mark_write
)
1779 struct access
*child
;
1780 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
1781 HOST_WIDE_INT covered_to
= root
->offset
;
1782 bool scalar
= is_gimple_reg_type (root
->type
);
1783 bool hole
= false, sth_created
= false;
1784 bool direct_read
= root
->grp_read
;
1786 if (mark_read
== SRA_MR_ASSIGN_READ
)
1789 root
->grp_assignment_read
= 1;
1791 if (mark_read
== SRA_MR_READ
)
1793 else if (root
->grp_assignment_read
)
1794 mark_read
= SRA_MR_ASSIGN_READ
;
1795 else if (root
->grp_read
)
1796 mark_read
= SRA_MR_READ
;
1799 root
->grp_write
= true;
1800 else if (root
->grp_write
)
1803 if (root
->grp_unscalarizable_region
)
1804 allow_replacements
= false;
1806 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
1807 allow_replacements
= false;
1809 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
1811 if (!hole
&& child
->offset
< covered_to
)
1814 covered_to
+= child
->size
;
1816 sth_created
|= analyze_access_subtree (child
,
1817 allow_replacements
&& !scalar
,
1818 mark_read
, mark_write
);
1820 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
1821 hole
|= !child
->grp_covered
;
1824 if (allow_replacements
&& scalar
&& !root
->first_child
1826 || (root
->grp_write
&& (direct_read
|| root
->grp_assignment_read
)))
1827 /* We must not ICE later on when trying to build an access to the
1828 original data within the aggregate even when it is impossible to do in
1829 a defined way like in the PR 42703 testcase. Therefore we check
1830 pre-emptively here that we will be able to do that. */
1831 && build_ref_for_offset (NULL
, TREE_TYPE (root
->base
), root
->offset
,
1834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1836 fprintf (dump_file
, "Marking ");
1837 print_generic_expr (dump_file
, root
->base
, 0);
1838 fprintf (dump_file
, " offset: %u, size: %u: ",
1839 (unsigned) root
->offset
, (unsigned) root
->size
);
1840 fprintf (dump_file
, " to be replaced.\n");
1843 root
->grp_to_be_replaced
= 1;
1847 else if (covered_to
< limit
)
1850 if (sth_created
&& !hole
)
1852 root
->grp_covered
= 1;
1855 if (root
->grp_write
|| TREE_CODE (root
->base
) == PARM_DECL
)
1856 root
->grp_unscalarized_data
= 1; /* not covered and written to */
1862 /* Analyze all access trees linked by next_grp by the means of
1863 analyze_access_subtree. */
1865 analyze_access_trees (struct access
*access
)
1871 if (analyze_access_subtree (access
, true, SRA_MR_NOT_READ
, false))
1873 access
= access
->next_grp
;
1879 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1880 SIZE would conflict with an already existing one. If exactly such a child
1881 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1884 child_would_conflict_in_lacc (struct access
*lacc
, HOST_WIDE_INT norm_offset
,
1885 HOST_WIDE_INT size
, struct access
**exact_match
)
1887 struct access
*child
;
1889 for (child
= lacc
->first_child
; child
; child
= child
->next_sibling
)
1891 if (child
->offset
== norm_offset
&& child
->size
== size
)
1893 *exact_match
= child
;
1897 if (child
->offset
< norm_offset
+ size
1898 && child
->offset
+ child
->size
> norm_offset
)
1905 /* Create a new child access of PARENT, with all properties just like MODEL
1906 except for its offset and with its grp_write false and grp_read true.
1907 Return the new access or NULL if it cannot be created. Note that this access
1908 is created long after all splicing and sorting, it's not located in any
1909 access vector and is automatically a representative of its group. */
1911 static struct access
*
1912 create_artificial_child_access (struct access
*parent
, struct access
*model
,
1913 HOST_WIDE_INT new_offset
)
1915 struct access
*access
;
1916 struct access
**child
;
1917 tree expr
= parent
->base
;;
1919 gcc_assert (!model
->grp_unscalarizable_region
);
1921 if (!build_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
1922 model
->type
, false))
1925 access
= (struct access
*) pool_alloc (access_pool
);
1926 memset (access
, 0, sizeof (struct access
));
1927 access
->base
= parent
->base
;
1928 access
->expr
= expr
;
1929 access
->offset
= new_offset
;
1930 access
->size
= model
->size
;
1931 access
->type
= model
->type
;
1932 access
->grp_write
= true;
1933 access
->grp_read
= false;
1935 child
= &parent
->first_child
;
1936 while (*child
&& (*child
)->offset
< new_offset
)
1937 child
= &(*child
)->next_sibling
;
1939 access
->next_sibling
= *child
;
1946 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1947 true if any new subaccess was created. Additionally, if RACC is a scalar
1948 access but LACC is not, change the type of the latter, if possible. */
1951 propagate_subaccesses_across_link (struct access
*lacc
, struct access
*racc
)
1953 struct access
*rchild
;
1954 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
1957 if (is_gimple_reg_type (lacc
->type
)
1958 || lacc
->grp_unscalarizable_region
1959 || racc
->grp_unscalarizable_region
)
1962 if (!lacc
->first_child
&& !racc
->first_child
1963 && is_gimple_reg_type (racc
->type
))
1965 tree t
= lacc
->base
;
1967 if (build_ref_for_offset (&t
, TREE_TYPE (t
), lacc
->offset
, racc
->type
,
1971 lacc
->type
= racc
->type
;
1976 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
1978 struct access
*new_acc
= NULL
;
1979 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
1981 if (rchild
->grp_unscalarizable_region
)
1984 if (child_would_conflict_in_lacc (lacc
, norm_offset
, rchild
->size
,
1989 rchild
->grp_hint
= 1;
1990 new_acc
->grp_hint
|= new_acc
->grp_read
;
1991 if (rchild
->first_child
)
1992 ret
|= propagate_subaccesses_across_link (new_acc
, rchild
);
1997 /* If a (part of) a union field is on the RHS of an assignment, it can
1998 have sub-accesses which do not make sense on the LHS (PR 40351).
1999 Check that this is not the case. */
2000 if (!build_ref_for_offset (NULL
, TREE_TYPE (lacc
->base
), norm_offset
,
2001 rchild
->type
, false))
2004 rchild
->grp_hint
= 1;
2005 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
);
2009 if (racc
->first_child
)
2010 propagate_subaccesses_across_link (new_acc
, rchild
);
2017 /* Propagate all subaccesses across assignment links. */
2020 propagate_all_subaccesses (void)
2022 while (work_queue_head
)
2024 struct access
*racc
= pop_access_from_work_queue ();
2025 struct assign_link
*link
;
2027 gcc_assert (racc
->first_link
);
2029 for (link
= racc
->first_link
; link
; link
= link
->next
)
2031 struct access
*lacc
= link
->lacc
;
2033 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2035 lacc
= lacc
->group_representative
;
2036 if (propagate_subaccesses_across_link (lacc
, racc
)
2037 && lacc
->first_link
)
2038 add_access_to_work_queue (lacc
);
2043 /* Go through all accesses collected throughout the (intraprocedural) analysis
2044 stage, exclude overlapping ones, identify representatives and build trees
2045 out of them, making decisions about scalarization on the way. Return true
2046 iff there are any to-be-scalarized variables after this stage. */
2049 analyze_all_variable_accesses (void)
2052 bitmap tmp
= BITMAP_ALLOC (NULL
);
2054 unsigned i
, max_total_scalarization_size
;
2056 max_total_scalarization_size
= UNITS_PER_WORD
* BITS_PER_UNIT
2057 * MOVE_RATIO (optimize_function_for_speed_p (cfun
));
2059 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
2060 if (bitmap_bit_p (should_scalarize_away_bitmap
, i
)
2061 && !bitmap_bit_p (cannot_scalarize_away_bitmap
, i
))
2063 tree var
= referenced_var (i
);
2065 if (TREE_CODE (var
) == VAR_DECL
2066 && ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var
)), 1)
2067 <= max_total_scalarization_size
)
2068 && type_consists_of_records_p (TREE_TYPE (var
)))
2070 completely_scalarize_record (var
, var
, 0, var
);
2071 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2073 fprintf (dump_file
, "Will attempt to totally scalarize ");
2074 print_generic_expr (dump_file
, var
, 0);
2075 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
2080 bitmap_copy (tmp
, candidate_bitmap
);
2081 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2083 tree var
= referenced_var (i
);
2084 struct access
*access
;
2086 access
= sort_and_splice_var_accesses (var
);
2087 if (!access
|| !build_access_trees (access
))
2088 disqualify_candidate (var
,
2089 "No or inhibitingly overlapping accesses.");
2092 propagate_all_subaccesses ();
2094 bitmap_copy (tmp
, candidate_bitmap
);
2095 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2097 tree var
= referenced_var (i
);
2098 struct access
*access
= get_first_repr_for_decl (var
);
2100 if (analyze_access_trees (access
))
2103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2105 fprintf (dump_file
, "\nAccess trees for ");
2106 print_generic_expr (dump_file
, var
, 0);
2107 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
2108 dump_access_tree (dump_file
, access
);
2109 fprintf (dump_file
, "\n");
2113 disqualify_candidate (var
, "No scalar replacements to be created.");
2120 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
2127 /* Return true iff a reference statement into aggregate AGG can be built for
2128 every single to-be-replaced accesses that is a child of ACCESS, its sibling
2129 or a child of its sibling. TOP_OFFSET is the offset from the processed
2130 access subtree that has to be subtracted from offset of each access. */
2133 ref_expr_for_all_replacements_p (struct access
*access
, tree agg
,
2134 HOST_WIDE_INT top_offset
)
2138 if (access
->grp_to_be_replaced
2139 && !build_ref_for_offset (NULL
, TREE_TYPE (agg
),
2140 access
->offset
- top_offset
,
2141 access
->type
, false))
2144 if (access
->first_child
2145 && !ref_expr_for_all_replacements_p (access
->first_child
, agg
,
2149 access
= access
->next_sibling
;
2156 /* Generate statements copying scalar replacements of accesses within a subtree
2157 into or out of AGG. ACCESS is the first child of the root of the subtree to
2158 be processed. AGG is an aggregate type expression (can be a declaration but
2159 does not have to be, it can for example also be an indirect_ref).
2160 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
2161 from offsets of individual accesses to get corresponding offsets for AGG.
2162 If CHUNK_SIZE is non-null, copy only replacements in the interval
2163 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
2164 statement iterator used to place the new statements. WRITE should be true
2165 when the statements should write from AGG to the replacement and false if
2166 vice versa. if INSERT_AFTER is true, new statements will be added after the
2167 current statement in GSI, they will be added before the statement
2171 generate_subtree_copies (struct access
*access
, tree agg
,
2172 HOST_WIDE_INT top_offset
,
2173 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
2174 gimple_stmt_iterator
*gsi
, bool write
,
2181 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
2184 if (access
->grp_to_be_replaced
2186 || access
->offset
+ access
->size
> start_offset
))
2188 tree repl
= get_access_replacement (access
);
2192 ref_found
= build_ref_for_offset (&expr
, TREE_TYPE (agg
),
2193 access
->offset
- top_offset
,
2194 access
->type
, false);
2195 gcc_assert (ref_found
);
2199 if (access
->grp_partial_lhs
)
2200 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
2202 insert_after
? GSI_NEW_STMT
2204 stmt
= gimple_build_assign (repl
, expr
);
2208 TREE_NO_WARNING (repl
) = 1;
2209 if (access
->grp_partial_lhs
)
2210 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2212 insert_after
? GSI_NEW_STMT
2214 stmt
= gimple_build_assign (expr
, repl
);
2218 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2220 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2222 sra_stats
.subtree_copies
++;
2225 if (access
->first_child
)
2226 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
2227 start_offset
, chunk_size
, gsi
,
2228 write
, insert_after
);
2230 access
= access
->next_sibling
;
2235 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2236 the root of the subtree to be processed. GSI is the statement iterator used
2237 for inserting statements which are added after the current statement if
2238 INSERT_AFTER is true or before it otherwise. */
2241 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
2245 struct access
*child
;
2247 if (access
->grp_to_be_replaced
)
2251 stmt
= gimple_build_assign (get_access_replacement (access
),
2252 fold_convert (access
->type
,
2253 integer_zero_node
));
2255 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2257 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2261 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2262 init_subtree_with_zero (child
, gsi
, insert_after
);
2265 /* Search for an access representative for the given expression EXPR and
2266 return it or NULL if it cannot be found. */
2268 static struct access
*
2269 get_access_for_expr (tree expr
)
2271 HOST_WIDE_INT offset
, size
, max_size
;
2274 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2275 a different size than the size of its argument and we need the latter
2277 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
2278 expr
= TREE_OPERAND (expr
, 0);
2280 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
);
2281 if (max_size
== -1 || !DECL_P (base
))
2284 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
2287 return get_var_base_offset_size_access (base
, offset
, max_size
);
2290 /* Replace the expression EXPR with a scalar replacement if there is one and
2291 generate other statements to do type conversion or subtree copying if
2292 necessary. GSI is used to place newly created statements, WRITE is true if
2293 the expression is being written to (it is on a LHS of a statement or output
2294 in an assembly statement). */
2297 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
)
2299 struct access
*access
;
2302 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
2305 expr
= &TREE_OPERAND (*expr
, 0);
2310 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
2311 expr
= &TREE_OPERAND (*expr
, 0);
2312 access
= get_access_for_expr (*expr
);
2315 type
= TREE_TYPE (*expr
);
2317 if (access
->grp_to_be_replaced
)
2319 tree repl
= get_access_replacement (access
);
2320 /* If we replace a non-register typed access simply use the original
2321 access expression to extract the scalar component afterwards.
2322 This happens if scalarizing a function return value or parameter
2323 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2324 gcc.c-torture/compile/20011217-1.c.
2326 We also want to use this when accessing a complex or vector which can
2327 be accessed as a different type too, potentially creating a need for
2328 type conversion (see PR42196) and when scalarized unions are involved
2329 in assembler statements (see PR42398). */
2330 if (!useless_type_conversion_p (type
, access
->type
))
2332 tree ref
= access
->base
;
2335 ok
= build_ref_for_offset (&ref
, TREE_TYPE (ref
),
2336 access
->offset
, access
->type
, false);
2343 if (access
->grp_partial_lhs
)
2344 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
2345 false, GSI_NEW_STMT
);
2346 stmt
= gimple_build_assign (repl
, ref
);
2347 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2353 if (access
->grp_partial_lhs
)
2354 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2355 true, GSI_SAME_STMT
);
2356 stmt
= gimple_build_assign (ref
, repl
);
2357 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2365 if (access
->first_child
)
2367 HOST_WIDE_INT start_offset
, chunk_size
;
2369 && host_integerp (TREE_OPERAND (bfr
, 1), 1)
2370 && host_integerp (TREE_OPERAND (bfr
, 2), 1))
2372 chunk_size
= tree_low_cst (TREE_OPERAND (bfr
, 1), 1);
2373 start_offset
= access
->offset
2374 + tree_low_cst (TREE_OPERAND (bfr
, 2), 1);
2377 start_offset
= chunk_size
= 0;
2379 generate_subtree_copies (access
->first_child
, access
->base
, 0,
2380 start_offset
, chunk_size
, gsi
, write
, write
);
2385 /* Where scalar replacements of the RHS have been written to when a replacement
2386 of a LHS of an assigments cannot be direclty loaded from a replacement of
2388 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
2389 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
2390 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
2392 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2393 base aggregate if there are unscalarized data or directly to LHS
2396 static enum unscalarized_data_handling
2397 handle_unscalarized_data_in_subtree (struct access
*top_racc
, tree lhs
,
2398 gimple_stmt_iterator
*gsi
)
2400 if (top_racc
->grp_unscalarized_data
)
2402 generate_subtree_copies (top_racc
->first_child
, top_racc
->base
, 0, 0, 0,
2404 return SRA_UDH_RIGHT
;
2408 generate_subtree_copies (top_racc
->first_child
, lhs
, top_racc
->offset
,
2409 0, 0, gsi
, false, false);
2410 return SRA_UDH_LEFT
;
2415 /* Try to generate statements to load all sub-replacements in an access
2416 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
2417 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
2418 load the accesses from it. LEFT_OFFSET is the offset of the left whole
2419 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
2420 NEW_GSI is stmt iterator used for statement insertions after the original
2421 assignment, OLD_GSI is used to insert statements before the assignment.
2422 *REFRESHED keeps the information whether we have needed to refresh
2423 replacements of the LHS and from which side of the assignments this takes
2427 load_assign_lhs_subreplacements (struct access
*lacc
, struct access
*top_racc
,
2428 HOST_WIDE_INT left_offset
,
2429 HOST_WIDE_INT right_offset
,
2430 gimple_stmt_iterator
*old_gsi
,
2431 gimple_stmt_iterator
*new_gsi
,
2432 enum unscalarized_data_handling
*refreshed
,
2435 location_t loc
= EXPR_LOCATION (lacc
->expr
);
2438 if (lacc
->grp_to_be_replaced
)
2440 struct access
*racc
;
2441 HOST_WIDE_INT offset
= lacc
->offset
- left_offset
+ right_offset
;
2445 racc
= find_access_in_subtree (top_racc
, offset
, lacc
->size
);
2446 if (racc
&& racc
->grp_to_be_replaced
)
2448 rhs
= get_access_replacement (racc
);
2449 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
2450 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, lacc
->type
, rhs
);
2454 /* No suitable access on the right hand side, need to load from
2455 the aggregate. See if we have to update it first... */
2456 if (*refreshed
== SRA_UDH_NONE
)
2457 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
,
2460 if (*refreshed
== SRA_UDH_LEFT
)
2465 repl_found
= build_ref_for_offset (&rhs
, TREE_TYPE (rhs
),
2466 lacc
->offset
, lacc
->type
,
2468 gcc_assert (repl_found
);
2474 rhs
= top_racc
->base
;
2475 repl_found
= build_ref_for_offset (&rhs
,
2476 TREE_TYPE (top_racc
->base
),
2477 offset
, lacc
->type
, false);
2478 gcc_assert (repl_found
);
2482 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
2483 gsi_insert_after (new_gsi
, stmt
, GSI_NEW_STMT
);
2485 sra_stats
.subreplacements
++;
2487 else if (*refreshed
== SRA_UDH_NONE
2488 && lacc
->grp_read
&& !lacc
->grp_covered
)
2489 *refreshed
= handle_unscalarized_data_in_subtree (top_racc
, lhs
,
2492 if (lacc
->first_child
)
2493 load_assign_lhs_subreplacements (lacc
->first_child
, top_racc
,
2494 left_offset
, right_offset
,
2495 old_gsi
, new_gsi
, refreshed
, lhs
);
2496 lacc
= lacc
->next_sibling
;
2501 /* Result code for SRA assignment modification. */
2502 enum assignment_mod_result
{ SRA_AM_NONE
, /* nothing done for the stmt */
2503 SRA_AM_MODIFIED
, /* stmt changed but not
2505 SRA_AM_REMOVED
}; /* stmt eliminated */
2507 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2508 to the assignment and GSI is the statement iterator pointing at it. Returns
2509 the same values as sra_modify_assign. */
2511 static enum assignment_mod_result
2512 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
2514 tree lhs
= gimple_assign_lhs (*stmt
);
2517 acc
= get_access_for_expr (lhs
);
2521 if (VEC_length (constructor_elt
,
2522 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt
))) > 0)
2524 /* I have never seen this code path trigger but if it can happen the
2525 following should handle it gracefully. */
2526 if (access_has_children_p (acc
))
2527 generate_subtree_copies (acc
->first_child
, acc
->base
, 0, 0, 0, gsi
,
2529 return SRA_AM_MODIFIED
;
2532 if (acc
->grp_covered
)
2534 init_subtree_with_zero (acc
, gsi
, false);
2535 unlink_stmt_vdef (*stmt
);
2536 gsi_remove (gsi
, true);
2537 return SRA_AM_REMOVED
;
2541 init_subtree_with_zero (acc
, gsi
, true);
2542 return SRA_AM_MODIFIED
;
2546 /* Create and return a new suitable default definition SSA_NAME for RACC which
2547 is an access describing an uninitialized part of an aggregate that is being
2551 get_repl_default_def_ssa_name (struct access
*racc
)
2555 decl
= get_unrenamed_access_replacement (racc
);
2557 repl
= gimple_default_def (cfun
, decl
);
2560 repl
= make_ssa_name (decl
, gimple_build_nop ());
2561 set_default_def (decl
, repl
);
2567 /* Examine both sides of the assignment statement pointed to by STMT, replace
2568 them with a scalare replacement if there is one and generate copying of
2569 replacements if scalarized aggregates have been used in the assignment. GSI
2570 is used to hold generated statements for type conversions and subtree
2573 static enum assignment_mod_result
2574 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
2576 struct access
*lacc
, *racc
;
2578 bool modify_this_stmt
= false;
2579 bool force_gimple_rhs
= false;
2580 location_t loc
= gimple_location (*stmt
);
2581 gimple_stmt_iterator orig_gsi
= *gsi
;
2583 if (!gimple_assign_single_p (*stmt
))
2585 lhs
= gimple_assign_lhs (*stmt
);
2586 rhs
= gimple_assign_rhs1 (*stmt
);
2588 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
2589 return sra_modify_constructor_assign (stmt
, gsi
);
2591 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
2592 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
2593 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
2595 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (*stmt
),
2597 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (*stmt
),
2599 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
2602 lacc
= get_access_for_expr (lhs
);
2603 racc
= get_access_for_expr (rhs
);
2607 if (lacc
&& lacc
->grp_to_be_replaced
)
2609 lhs
= get_access_replacement (lacc
);
2610 gimple_assign_set_lhs (*stmt
, lhs
);
2611 modify_this_stmt
= true;
2612 if (lacc
->grp_partial_lhs
)
2613 force_gimple_rhs
= true;
2617 if (racc
&& racc
->grp_to_be_replaced
)
2619 rhs
= get_access_replacement (racc
);
2620 modify_this_stmt
= true;
2621 if (racc
->grp_partial_lhs
)
2622 force_gimple_rhs
= true;
2626 if (modify_this_stmt
)
2628 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2630 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2631 ??? This should move to fold_stmt which we simply should
2632 call after building a VIEW_CONVERT_EXPR here. */
2633 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
2634 && !access_has_children_p (lacc
))
2637 if (build_ref_for_offset (&expr
, TREE_TYPE (lhs
), 0,
2638 TREE_TYPE (rhs
), false))
2641 gimple_assign_set_lhs (*stmt
, expr
);
2644 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
2645 && !access_has_children_p (racc
))
2648 if (build_ref_for_offset (&expr
, TREE_TYPE (rhs
), 0,
2649 TREE_TYPE (lhs
), false))
2652 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2654 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
), rhs
);
2655 if (is_gimple_reg_type (TREE_TYPE (lhs
))
2656 && TREE_CODE (lhs
) != SSA_NAME
)
2657 force_gimple_rhs
= true;
2662 /* From this point on, the function deals with assignments in between
2663 aggregates when at least one has scalar reductions of some of its
2664 components. There are three possible scenarios: Both the LHS and RHS have
2665 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2667 In the first case, we would like to load the LHS components from RHS
2668 components whenever possible. If that is not possible, we would like to
2669 read it directly from the RHS (after updating it by storing in it its own
2670 components). If there are some necessary unscalarized data in the LHS,
2671 those will be loaded by the original assignment too. If neither of these
2672 cases happen, the original statement can be removed. Most of this is done
2673 by load_assign_lhs_subreplacements.
2675 In the second case, we would like to store all RHS scalarized components
2676 directly into LHS and if they cover the aggregate completely, remove the
2677 statement too. In the third case, we want the LHS components to be loaded
2678 directly from the RHS (DSE will remove the original statement if it
2681 This is a bit complex but manageable when types match and when unions do
2682 not cause confusion in a way that we cannot really load a component of LHS
2683 from the RHS or vice versa (the access representing this level can have
2684 subaccesses that are accessible only through a different union field at a
2685 higher level - different from the one used in the examined expression).
2688 Therefore, I specially handle a fourth case, happening when there is a
2689 specific type cast or it is impossible to locate a scalarized subaccess on
2690 the other side of the expression. If that happens, I simply "refresh" the
2691 RHS by storing in it is scalarized components leave the original statement
2692 there to do the copying and then load the scalar replacements of the LHS.
2693 This is what the first branch does. */
2695 if (gimple_has_volatile_ops (*stmt
)
2696 || contains_view_convert_expr_p (rhs
)
2697 || contains_view_convert_expr_p (lhs
)
2698 || (access_has_children_p (racc
)
2699 && !ref_expr_for_all_replacements_p (racc
, lhs
, racc
->offset
))
2700 || (access_has_children_p (lacc
)
2701 && !ref_expr_for_all_replacements_p (lacc
, rhs
, lacc
->offset
)))
2703 if (access_has_children_p (racc
))
2704 generate_subtree_copies (racc
->first_child
, racc
->base
, 0, 0, 0,
2706 if (access_has_children_p (lacc
))
2707 generate_subtree_copies (lacc
->first_child
, lacc
->base
, 0, 0, 0,
2709 sra_stats
.separate_lhs_rhs_handling
++;
2713 if (access_has_children_p (lacc
) && access_has_children_p (racc
))
2715 gimple_stmt_iterator orig_gsi
= *gsi
;
2716 enum unscalarized_data_handling refreshed
;
2718 if (lacc
->grp_read
&& !lacc
->grp_covered
)
2719 refreshed
= handle_unscalarized_data_in_subtree (racc
, lhs
, gsi
);
2721 refreshed
= SRA_UDH_NONE
;
2723 load_assign_lhs_subreplacements (lacc
->first_child
, racc
,
2724 lacc
->offset
, racc
->offset
,
2725 &orig_gsi
, gsi
, &refreshed
, lhs
);
2726 if (refreshed
!= SRA_UDH_RIGHT
)
2729 unlink_stmt_vdef (*stmt
);
2730 gsi_remove (&orig_gsi
, true);
2731 sra_stats
.deleted
++;
2732 return SRA_AM_REMOVED
;
2739 if (!racc
->grp_to_be_replaced
&& !racc
->grp_unscalarized_data
)
2743 fprintf (dump_file
, "Removing load: ");
2744 print_gimple_stmt (dump_file
, *stmt
, 0, 0);
2747 if (TREE_CODE (lhs
) == SSA_NAME
)
2749 rhs
= get_repl_default_def_ssa_name (racc
);
2750 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
2752 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
2753 TREE_TYPE (lhs
), rhs
);
2757 if (racc
->first_child
)
2758 generate_subtree_copies (racc
->first_child
, lhs
,
2759 racc
->offset
, 0, 0, gsi
,
2762 gcc_assert (*stmt
== gsi_stmt (*gsi
));
2763 unlink_stmt_vdef (*stmt
);
2764 gsi_remove (gsi
, true);
2765 sra_stats
.deleted
++;
2766 return SRA_AM_REMOVED
;
2769 else if (racc
->first_child
)
2770 generate_subtree_copies (racc
->first_child
, lhs
,
2771 racc
->offset
, 0, 0, gsi
, false, true);
2773 if (access_has_children_p (lacc
))
2774 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
2775 0, 0, gsi
, true, true);
2779 /* This gimplification must be done after generate_subtree_copies, lest we
2780 insert the subtree copies in the middle of the gimplified sequence. */
2781 if (force_gimple_rhs
)
2782 rhs
= force_gimple_operand_gsi (&orig_gsi
, rhs
, true, NULL_TREE
,
2783 true, GSI_SAME_STMT
);
2784 if (gimple_assign_rhs1 (*stmt
) != rhs
)
2786 modify_this_stmt
= true;
2787 gimple_assign_set_rhs_from_tree (&orig_gsi
, rhs
);
2788 gcc_assert (*stmt
== gsi_stmt (orig_gsi
));
2791 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
2794 /* Traverse the function body and all modifications as decided in
2795 analyze_all_variable_accesses. Return true iff the CFG has been
2799 sra_modify_function_body (void)
2801 bool cfg_changed
= false;
2806 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
2807 while (!gsi_end_p (gsi
))
2809 gimple stmt
= gsi_stmt (gsi
);
2810 enum assignment_mod_result assign_result
;
2811 bool modified
= false, deleted
= false;
2815 switch (gimple_code (stmt
))
2818 t
= gimple_return_retval_ptr (stmt
);
2819 if (*t
!= NULL_TREE
)
2820 modified
|= sra_modify_expr (t
, &gsi
, false);
2824 assign_result
= sra_modify_assign (&stmt
, &gsi
);
2825 modified
|= assign_result
== SRA_AM_MODIFIED
;
2826 deleted
= assign_result
== SRA_AM_REMOVED
;
2830 /* Operands must be processed before the lhs. */
2831 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
2833 t
= gimple_call_arg_ptr (stmt
, i
);
2834 modified
|= sra_modify_expr (t
, &gsi
, false);
2837 if (gimple_call_lhs (stmt
))
2839 t
= gimple_call_lhs_ptr (stmt
);
2840 modified
|= sra_modify_expr (t
, &gsi
, true);
2845 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
2847 t
= &TREE_VALUE (gimple_asm_input_op (stmt
, i
));
2848 modified
|= sra_modify_expr (t
, &gsi
, false);
2850 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
2852 t
= &TREE_VALUE (gimple_asm_output_op (stmt
, i
));
2853 modified
|= sra_modify_expr (t
, &gsi
, true);
2864 if (maybe_clean_eh_stmt (stmt
)
2865 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
2876 /* Generate statements initializing scalar replacements of parts of function
2880 initialize_parameter_reductions (void)
2882 gimple_stmt_iterator gsi
;
2883 gimple_seq seq
= NULL
;
2886 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2888 parm
= DECL_CHAIN (parm
))
2890 VEC (access_p
, heap
) *access_vec
;
2891 struct access
*access
;
2893 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
2895 access_vec
= get_base_access_vector (parm
);
2901 seq
= gimple_seq_alloc ();
2902 gsi
= gsi_start (seq
);
2905 for (access
= VEC_index (access_p
, access_vec
, 0);
2907 access
= access
->next_grp
)
2908 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true);
2912 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR
), seq
);
2915 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2916 it reveals there are components of some aggregates to be scalarized, it runs
2917 the required transformations. */
2919 perform_intra_sra (void)
2924 if (!find_var_candidates ())
2927 if (!scan_function ())
2930 if (!analyze_all_variable_accesses ())
2933 if (sra_modify_function_body ())
2934 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
2936 ret
= TODO_update_ssa
;
2937 initialize_parameter_reductions ();
2939 statistics_counter_event (cfun
, "Scalar replacements created",
2940 sra_stats
.replacements
);
2941 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
2942 statistics_counter_event (cfun
, "Subtree copy stmts",
2943 sra_stats
.subtree_copies
);
2944 statistics_counter_event (cfun
, "Subreplacement stmts",
2945 sra_stats
.subreplacements
);
2946 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
2947 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
2948 sra_stats
.separate_lhs_rhs_handling
);
2951 sra_deinitialize ();
2955 /* Perform early intraprocedural SRA. */
2957 early_intra_sra (void)
2959 sra_mode
= SRA_MODE_EARLY_INTRA
;
2960 return perform_intra_sra ();
2963 /* Perform "late" intraprocedural SRA. */
2965 late_intra_sra (void)
2967 sra_mode
= SRA_MODE_INTRA
;
2968 return perform_intra_sra ();
2973 gate_intra_sra (void)
2975 return flag_tree_sra
!= 0 && dbg_cnt (tree_sra
);
2979 struct gimple_opt_pass pass_sra_early
=
2984 gate_intra_sra
, /* gate */
2985 early_intra_sra
, /* execute */
2988 0, /* static_pass_number */
2989 TV_TREE_SRA
, /* tv_id */
2990 PROP_cfg
| PROP_ssa
, /* properties_required */
2991 0, /* properties_provided */
2992 0, /* properties_destroyed */
2993 0, /* todo_flags_start */
2997 | TODO_verify_ssa
/* todo_flags_finish */
3001 struct gimple_opt_pass pass_sra
=
3006 gate_intra_sra
, /* gate */
3007 late_intra_sra
, /* execute */
3010 0, /* static_pass_number */
3011 TV_TREE_SRA
, /* tv_id */
3012 PROP_cfg
| PROP_ssa
, /* properties_required */
3013 0, /* properties_provided */
3014 0, /* properties_destroyed */
3015 TODO_update_address_taken
, /* todo_flags_start */
3019 | TODO_verify_ssa
/* todo_flags_finish */
3024 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3028 is_unused_scalar_param (tree parm
)
3031 return (is_gimple_reg (parm
)
3032 && (!(name
= gimple_default_def (cfun
, parm
))
3033 || has_zero_uses (name
)));
3036 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3037 examine whether there are any direct or otherwise infeasible ones. If so,
3038 return true, otherwise return false. PARM must be a gimple register with a
3039 non-NULL default definition. */
3042 ptr_parm_has_direct_uses (tree parm
)
3044 imm_use_iterator ui
;
3046 tree name
= gimple_default_def (cfun
, parm
);
3049 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
3052 use_operand_p use_p
;
3054 if (is_gimple_debug (stmt
))
3057 /* Valid uses include dereferences on the lhs and the rhs. */
3058 if (gimple_has_lhs (stmt
))
3060 tree lhs
= gimple_get_lhs (stmt
);
3061 while (handled_component_p (lhs
))
3062 lhs
= TREE_OPERAND (lhs
, 0);
3063 if (TREE_CODE (lhs
) == MEM_REF
3064 && TREE_OPERAND (lhs
, 0) == name
3065 && integer_zerop (TREE_OPERAND (lhs
, 1))
3066 && types_compatible_p (TREE_TYPE (lhs
),
3067 TREE_TYPE (TREE_TYPE (name
))))
3070 if (gimple_assign_single_p (stmt
))
3072 tree rhs
= gimple_assign_rhs1 (stmt
);
3073 while (handled_component_p (rhs
))
3074 rhs
= TREE_OPERAND (rhs
, 0);
3075 if (TREE_CODE (rhs
) == MEM_REF
3076 && TREE_OPERAND (rhs
, 0) == name
3077 && integer_zerop (TREE_OPERAND (rhs
, 1))
3078 && types_compatible_p (TREE_TYPE (rhs
),
3079 TREE_TYPE (TREE_TYPE (name
))))
3082 else if (is_gimple_call (stmt
))
3085 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3087 tree arg
= gimple_call_arg (stmt
, i
);
3088 while (handled_component_p (arg
))
3089 arg
= TREE_OPERAND (arg
, 0);
3090 if (TREE_CODE (arg
) == MEM_REF
3091 && TREE_OPERAND (arg
, 0) == name
3092 && integer_zerop (TREE_OPERAND (arg
, 1))
3093 && types_compatible_p (TREE_TYPE (arg
),
3094 TREE_TYPE (TREE_TYPE (name
))))
3099 /* If the number of valid uses does not match the number of
3100 uses in this stmt there is an unhandled use. */
3101 FOR_EACH_IMM_USE_ON_STMT (use_p
, ui
)
3108 BREAK_FROM_IMM_USE_STMT (ui
);
3114 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3115 them in candidate_bitmap. Note that these do not necessarily include
3116 parameter which are unused and thus can be removed. Return true iff any
3117 such candidate has been found. */
3120 find_param_candidates (void)
3126 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3128 parm
= DECL_CHAIN (parm
))
3130 tree type
= TREE_TYPE (parm
);
3134 if (TREE_THIS_VOLATILE (parm
)
3135 || TREE_ADDRESSABLE (parm
)
3136 || (!is_gimple_reg_type (type
) && is_va_list_type (type
)))
3139 if (is_unused_scalar_param (parm
))
3145 if (POINTER_TYPE_P (type
))
3147 type
= TREE_TYPE (type
);
3149 if (TREE_CODE (type
) == FUNCTION_TYPE
3150 || TYPE_VOLATILE (type
)
3151 || (TREE_CODE (type
) == ARRAY_TYPE
3152 && TYPE_NONALIASED_COMPONENT (type
))
3153 || !is_gimple_reg (parm
)
3154 || is_va_list_type (type
)
3155 || ptr_parm_has_direct_uses (parm
))
3158 else if (!AGGREGATE_TYPE_P (type
))
3161 if (!COMPLETE_TYPE_P (type
)
3162 || !host_integerp (TYPE_SIZE (type
), 1)
3163 || tree_low_cst (TYPE_SIZE (type
), 1) == 0
3164 || (AGGREGATE_TYPE_P (type
)
3165 && type_internals_preclude_sra_p (type
)))
3168 bitmap_set_bit (candidate_bitmap
, DECL_UID (parm
));
3170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3172 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (parm
));
3173 print_generic_expr (dump_file
, parm
, 0);
3174 fprintf (dump_file
, "\n");
3178 func_param_count
= count
;
3182 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3186 mark_maybe_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
3189 struct access
*repr
= (struct access
*) data
;
3191 repr
->grp_maybe_modified
= 1;
3195 /* Analyze what representatives (in linked lists accessible from
3196 REPRESENTATIVES) can be modified by side effects of statements in the
3197 current function. */
3200 analyze_modified_params (VEC (access_p
, heap
) *representatives
)
3204 for (i
= 0; i
< func_param_count
; i
++)
3206 struct access
*repr
;
3208 for (repr
= VEC_index (access_p
, representatives
, i
);
3210 repr
= repr
->next_grp
)
3212 struct access
*access
;
3216 if (no_accesses_p (repr
))
3218 if (!POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3219 || repr
->grp_maybe_modified
)
3222 ao_ref_init (&ar
, repr
->expr
);
3223 visited
= BITMAP_ALLOC (NULL
);
3224 for (access
= repr
; access
; access
= access
->next_sibling
)
3226 /* All accesses are read ones, otherwise grp_maybe_modified would
3227 be trivially set. */
3228 walk_aliased_vdefs (&ar
, gimple_vuse (access
->stmt
),
3229 mark_maybe_modified
, repr
, &visited
);
3230 if (repr
->grp_maybe_modified
)
3233 BITMAP_FREE (visited
);
3238 /* Propagate distances in bb_dereferences in the opposite direction than the
3239 control flow edges, in each step storing the maximum of the current value
3240 and the minimum of all successors. These steps are repeated until the table
3241 stabilizes. Note that BBs which might terminate the functions (according to
3242 final_bbs bitmap) never updated in this way. */
3245 propagate_dereference_distances (void)
3247 VEC (basic_block
, heap
) *queue
;
3250 queue
= VEC_alloc (basic_block
, heap
, last_basic_block_for_function (cfun
));
3251 VEC_quick_push (basic_block
, queue
, ENTRY_BLOCK_PTR
);
3254 VEC_quick_push (basic_block
, queue
, bb
);
3258 while (!VEC_empty (basic_block
, queue
))
3262 bool change
= false;
3265 bb
= VEC_pop (basic_block
, queue
);
3268 if (bitmap_bit_p (final_bbs
, bb
->index
))
3271 for (i
= 0; i
< func_param_count
; i
++)
3273 int idx
= bb
->index
* func_param_count
+ i
;
3275 HOST_WIDE_INT inh
= 0;
3277 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3279 int succ_idx
= e
->dest
->index
* func_param_count
+ i
;
3281 if (e
->src
== EXIT_BLOCK_PTR
)
3287 inh
= bb_dereferences
[succ_idx
];
3289 else if (bb_dereferences
[succ_idx
] < inh
)
3290 inh
= bb_dereferences
[succ_idx
];
3293 if (!first
&& bb_dereferences
[idx
] < inh
)
3295 bb_dereferences
[idx
] = inh
;
3300 if (change
&& !bitmap_bit_p (final_bbs
, bb
->index
))
3301 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3306 e
->src
->aux
= e
->src
;
3307 VEC_quick_push (basic_block
, queue
, e
->src
);
3311 VEC_free (basic_block
, heap
, queue
);
3314 /* Dump a dereferences TABLE with heading STR to file F. */
3317 dump_dereferences_table (FILE *f
, const char *str
, HOST_WIDE_INT
*table
)
3321 fprintf (dump_file
, str
);
3322 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
3324 fprintf (f
, "%4i %i ", bb
->index
, bitmap_bit_p (final_bbs
, bb
->index
));
3325 if (bb
!= EXIT_BLOCK_PTR
)
3328 for (i
= 0; i
< func_param_count
; i
++)
3330 int idx
= bb
->index
* func_param_count
+ i
;
3331 fprintf (f
, " %4" HOST_WIDE_INT_PRINT
"d", table
[idx
]);
3336 fprintf (dump_file
, "\n");
3339 /* Determine what (parts of) parameters passed by reference that are not
3340 assigned to are not certainly dereferenced in this function and thus the
3341 dereferencing cannot be safely moved to the caller without potentially
3342 introducing a segfault. Mark such REPRESENTATIVES as
3343 grp_not_necessarilly_dereferenced.
3345 The dereferenced maximum "distance," i.e. the offset + size of the accessed
3346 part is calculated rather than simple booleans are calculated for each
3347 pointer parameter to handle cases when only a fraction of the whole
3348 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3351 The maximum dereference distances for each pointer parameter and BB are
3352 already stored in bb_dereference. This routine simply propagates these
3353 values upwards by propagate_dereference_distances and then compares the
3354 distances of individual parameters in the ENTRY BB to the equivalent
3355 distances of each representative of a (fraction of a) parameter. */
3358 analyze_caller_dereference_legality (VEC (access_p
, heap
) *representatives
)
3362 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3363 dump_dereferences_table (dump_file
,
3364 "Dereference table before propagation:\n",
3367 propagate_dereference_distances ();
3369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 dump_dereferences_table (dump_file
,
3371 "Dereference table after propagation:\n",
3374 for (i
= 0; i
< func_param_count
; i
++)
3376 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3377 int idx
= ENTRY_BLOCK_PTR
->index
* func_param_count
+ i
;
3379 if (!repr
|| no_accesses_p (repr
))
3384 if ((repr
->offset
+ repr
->size
) > bb_dereferences
[idx
])
3385 repr
->grp_not_necessarilly_dereferenced
= 1;
3386 repr
= repr
->next_grp
;
3392 /* Return the representative access for the parameter declaration PARM if it is
3393 a scalar passed by reference which is not written to and the pointer value
3394 is not used directly. Thus, if it is legal to dereference it in the caller
3395 and we can rule out modifications through aliases, such parameter should be
3396 turned into one passed by value. Return NULL otherwise. */
3398 static struct access
*
3399 unmodified_by_ref_scalar_representative (tree parm
)
3401 int i
, access_count
;
3402 struct access
*repr
;
3403 VEC (access_p
, heap
) *access_vec
;
3405 access_vec
= get_base_access_vector (parm
);
3406 gcc_assert (access_vec
);
3407 repr
= VEC_index (access_p
, access_vec
, 0);
3410 repr
->group_representative
= repr
;
3412 access_count
= VEC_length (access_p
, access_vec
);
3413 for (i
= 1; i
< access_count
; i
++)
3415 struct access
*access
= VEC_index (access_p
, access_vec
, i
);
3418 access
->group_representative
= repr
;
3419 access
->next_sibling
= repr
->next_sibling
;
3420 repr
->next_sibling
= access
;
3424 repr
->grp_scalar_ptr
= 1;
3428 /* Return true iff this access precludes IPA-SRA of the parameter it is
3432 access_precludes_ipa_sra_p (struct access
*access
)
3434 /* Avoid issues such as the second simple testcase in PR 42025. The problem
3435 is incompatible assign in a call statement (and possibly even in asm
3436 statements). This can be relaxed by using a new temporary but only for
3437 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3438 intraprocedural SRA we deal with this by keeping the old aggregate around,
3439 something we cannot do in IPA-SRA.) */
3441 && (is_gimple_call (access
->stmt
)
3442 || gimple_code (access
->stmt
) == GIMPLE_ASM
))
3449 /* Sort collected accesses for parameter PARM, identify representatives for
3450 each accessed region and link them together. Return NULL if there are
3451 different but overlapping accesses, return the special ptr value meaning
3452 there are no accesses for this parameter if that is the case and return the
3453 first representative otherwise. Set *RO_GRP if there is a group of accesses
3454 with only read (i.e. no write) accesses. */
3456 static struct access
*
3457 splice_param_accesses (tree parm
, bool *ro_grp
)
3459 int i
, j
, access_count
, group_count
;
3460 int agg_size
, total_size
= 0;
3461 struct access
*access
, *res
, **prev_acc_ptr
= &res
;
3462 VEC (access_p
, heap
) *access_vec
;
3464 access_vec
= get_base_access_vector (parm
);
3466 return &no_accesses_representant
;
3467 access_count
= VEC_length (access_p
, access_vec
);
3469 qsort (VEC_address (access_p
, access_vec
), access_count
, sizeof (access_p
),
3470 compare_access_positions
);
3475 while (i
< access_count
)
3478 access
= VEC_index (access_p
, access_vec
, i
);
3479 modification
= access
->write
;
3480 if (access_precludes_ipa_sra_p (access
))
3483 /* Access is about to become group representative unless we find some
3484 nasty overlap which would preclude us from breaking this parameter
3488 while (j
< access_count
)
3490 struct access
*ac2
= VEC_index (access_p
, access_vec
, j
);
3491 if (ac2
->offset
!= access
->offset
)
3493 /* All or nothing law for parameters. */
3494 if (access
->offset
+ access
->size
> ac2
->offset
)
3499 else if (ac2
->size
!= access
->size
)
3502 if (access_precludes_ipa_sra_p (ac2
))
3505 modification
|= ac2
->write
;
3506 ac2
->group_representative
= access
;
3507 ac2
->next_sibling
= access
->next_sibling
;
3508 access
->next_sibling
= ac2
;
3513 access
->grp_maybe_modified
= modification
;
3516 *prev_acc_ptr
= access
;
3517 prev_acc_ptr
= &access
->next_grp
;
3518 total_size
+= access
->size
;
3522 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3523 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3525 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3526 if (total_size
>= agg_size
)
3529 gcc_assert (group_count
> 0);
3533 /* Decide whether parameters with representative accesses given by REPR should
3534 be reduced into components. */
3537 decide_one_param_reduction (struct access
*repr
)
3539 int total_size
, cur_parm_size
, agg_size
, new_param_count
, parm_size_limit
;
3544 cur_parm_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (parm
)), 1);
3545 gcc_assert (cur_parm_size
> 0);
3547 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3550 agg_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))), 1);
3555 agg_size
= cur_parm_size
;
3561 fprintf (dump_file
, "Evaluating PARAM group sizes for ");
3562 print_generic_expr (dump_file
, parm
, 0);
3563 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (parm
));
3564 for (acc
= repr
; acc
; acc
= acc
->next_grp
)
3565 dump_access (dump_file
, acc
, true);
3569 new_param_count
= 0;
3571 for (; repr
; repr
= repr
->next_grp
)
3573 gcc_assert (parm
== repr
->base
);
3576 if (!by_ref
|| (!repr
->grp_maybe_modified
3577 && !repr
->grp_not_necessarilly_dereferenced
))
3578 total_size
+= repr
->size
;
3580 total_size
+= cur_parm_size
;
3583 gcc_assert (new_param_count
> 0);
3585 if (optimize_function_for_size_p (cfun
))
3586 parm_size_limit
= cur_parm_size
;
3588 parm_size_limit
= (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR
)
3591 if (total_size
< agg_size
3592 && total_size
<= parm_size_limit
)
3595 fprintf (dump_file
, " ....will be split into %i components\n",
3597 return new_param_count
;
3603 /* The order of the following enums is important, we need to do extra work for
3604 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
3605 enum ipa_splicing_result
{ NO_GOOD_ACCESS
, UNUSED_PARAMS
, BY_VAL_ACCESSES
,
3606 MODIF_BY_REF_ACCESSES
, UNMODIF_BY_REF_ACCESSES
};
3608 /* Identify representatives of all accesses to all candidate parameters for
3609 IPA-SRA. Return result based on what representatives have been found. */
3611 static enum ipa_splicing_result
3612 splice_all_param_accesses (VEC (access_p
, heap
) **representatives
)
3614 enum ipa_splicing_result result
= NO_GOOD_ACCESS
;
3616 struct access
*repr
;
3618 *representatives
= VEC_alloc (access_p
, heap
, func_param_count
);
3620 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3622 parm
= DECL_CHAIN (parm
))
3624 if (is_unused_scalar_param (parm
))
3626 VEC_quick_push (access_p
, *representatives
,
3627 &no_accesses_representant
);
3628 if (result
== NO_GOOD_ACCESS
)
3629 result
= UNUSED_PARAMS
;
3631 else if (POINTER_TYPE_P (TREE_TYPE (parm
))
3632 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm
)))
3633 && bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3635 repr
= unmodified_by_ref_scalar_representative (parm
);
3636 VEC_quick_push (access_p
, *representatives
, repr
);
3638 result
= UNMODIF_BY_REF_ACCESSES
;
3640 else if (bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3642 bool ro_grp
= false;
3643 repr
= splice_param_accesses (parm
, &ro_grp
);
3644 VEC_quick_push (access_p
, *representatives
, repr
);
3646 if (repr
&& !no_accesses_p (repr
))
3648 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
3651 result
= UNMODIF_BY_REF_ACCESSES
;
3652 else if (result
< MODIF_BY_REF_ACCESSES
)
3653 result
= MODIF_BY_REF_ACCESSES
;
3655 else if (result
< BY_VAL_ACCESSES
)
3656 result
= BY_VAL_ACCESSES
;
3658 else if (no_accesses_p (repr
) && (result
== NO_GOOD_ACCESS
))
3659 result
= UNUSED_PARAMS
;
3662 VEC_quick_push (access_p
, *representatives
, NULL
);
3665 if (result
== NO_GOOD_ACCESS
)
3667 VEC_free (access_p
, heap
, *representatives
);
3668 *representatives
= NULL
;
3669 return NO_GOOD_ACCESS
;
3675 /* Return the index of BASE in PARMS. Abort if it is not found. */
3678 get_param_index (tree base
, VEC(tree
, heap
) *parms
)
3682 len
= VEC_length (tree
, parms
);
3683 for (i
= 0; i
< len
; i
++)
3684 if (VEC_index (tree
, parms
, i
) == base
)
3689 /* Convert the decisions made at the representative level into compact
3690 parameter adjustments. REPRESENTATIVES are pointers to first
3691 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
3692 final number of adjustments. */
3694 static ipa_parm_adjustment_vec
3695 turn_representatives_into_adjustments (VEC (access_p
, heap
) *representatives
,
3696 int adjustments_count
)
3698 VEC (tree
, heap
) *parms
;
3699 ipa_parm_adjustment_vec adjustments
;
3703 gcc_assert (adjustments_count
> 0);
3704 parms
= ipa_get_vector_of_formal_parms (current_function_decl
);
3705 adjustments
= VEC_alloc (ipa_parm_adjustment_t
, heap
, adjustments_count
);
3706 parm
= DECL_ARGUMENTS (current_function_decl
);
3707 for (i
= 0; i
< func_param_count
; i
++, parm
= DECL_CHAIN (parm
))
3709 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3711 if (!repr
|| no_accesses_p (repr
))
3713 struct ipa_parm_adjustment
*adj
;
3715 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3716 memset (adj
, 0, sizeof (*adj
));
3717 adj
->base_index
= get_param_index (parm
, parms
);
3720 adj
->copy_param
= 1;
3722 adj
->remove_param
= 1;
3726 struct ipa_parm_adjustment
*adj
;
3727 int index
= get_param_index (parm
, parms
);
3729 for (; repr
; repr
= repr
->next_grp
)
3731 adj
= VEC_quick_push (ipa_parm_adjustment_t
, adjustments
, NULL
);
3732 memset (adj
, 0, sizeof (*adj
));
3733 gcc_assert (repr
->base
== parm
);
3734 adj
->base_index
= index
;
3735 adj
->base
= repr
->base
;
3736 adj
->type
= repr
->type
;
3737 adj
->offset
= repr
->offset
;
3738 adj
->by_ref
= (POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3739 && (repr
->grp_maybe_modified
3740 || repr
->grp_not_necessarilly_dereferenced
));
3745 VEC_free (tree
, heap
, parms
);
3749 /* Analyze the collected accesses and produce a plan what to do with the
3750 parameters in the form of adjustments, NULL meaning nothing. */
3752 static ipa_parm_adjustment_vec
3753 analyze_all_param_acesses (void)
3755 enum ipa_splicing_result repr_state
;
3756 bool proceed
= false;
3757 int i
, adjustments_count
= 0;
3758 VEC (access_p
, heap
) *representatives
;
3759 ipa_parm_adjustment_vec adjustments
;
3761 repr_state
= splice_all_param_accesses (&representatives
);
3762 if (repr_state
== NO_GOOD_ACCESS
)
3765 /* If there are any parameters passed by reference which are not modified
3766 directly, we need to check whether they can be modified indirectly. */
3767 if (repr_state
== UNMODIF_BY_REF_ACCESSES
)
3769 analyze_caller_dereference_legality (representatives
);
3770 analyze_modified_params (representatives
);
3773 for (i
= 0; i
< func_param_count
; i
++)
3775 struct access
*repr
= VEC_index (access_p
, representatives
, i
);
3777 if (repr
&& !no_accesses_p (repr
))
3779 if (repr
->grp_scalar_ptr
)
3781 adjustments_count
++;
3782 if (repr
->grp_not_necessarilly_dereferenced
3783 || repr
->grp_maybe_modified
)
3784 VEC_replace (access_p
, representatives
, i
, NULL
);
3788 sra_stats
.scalar_by_ref_to_by_val
++;
3793 int new_components
= decide_one_param_reduction (repr
);
3795 if (new_components
== 0)
3797 VEC_replace (access_p
, representatives
, i
, NULL
);
3798 adjustments_count
++;
3802 adjustments_count
+= new_components
;
3803 sra_stats
.aggregate_params_reduced
++;
3804 sra_stats
.param_reductions_created
+= new_components
;
3811 if (no_accesses_p (repr
))
3814 sra_stats
.deleted_unused_parameters
++;
3816 adjustments_count
++;
3820 if (!proceed
&& dump_file
)
3821 fprintf (dump_file
, "NOT proceeding to change params.\n");
3824 adjustments
= turn_representatives_into_adjustments (representatives
,
3829 VEC_free (access_p
, heap
, representatives
);
3833 /* If a parameter replacement identified by ADJ does not yet exist in the form
3834 of declaration, create it and record it, otherwise return the previously
3838 get_replaced_param_substitute (struct ipa_parm_adjustment
*adj
)
3841 if (!adj
->new_ssa_base
)
3843 char *pretty_name
= make_fancy_name (adj
->base
);
3845 repl
= create_tmp_reg (TREE_TYPE (adj
->base
), "ISR");
3846 DECL_NAME (repl
) = get_identifier (pretty_name
);
3847 obstack_free (&name_obstack
, pretty_name
);
3850 add_referenced_var (repl
);
3851 adj
->new_ssa_base
= repl
;
3854 repl
= adj
->new_ssa_base
;
3858 /* Find the first adjustment for a particular parameter BASE in a vector of
3859 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
3862 static struct ipa_parm_adjustment
*
3863 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments
, tree base
)
3867 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3868 for (i
= 0; i
< len
; i
++)
3870 struct ipa_parm_adjustment
*adj
;
3872 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3873 if (!adj
->copy_param
&& adj
->base
== base
)
3880 /* If the statement STMT defines an SSA_NAME of a parameter which is to be
3881 removed because its value is not used, replace the SSA_NAME with a one
3882 relating to a created VAR_DECL together all of its uses and return true.
3883 ADJUSTMENTS is a pointer to an adjustments vector. */
3886 replace_removed_params_ssa_names (gimple stmt
,
3887 ipa_parm_adjustment_vec adjustments
)
3889 struct ipa_parm_adjustment
*adj
;
3890 tree lhs
, decl
, repl
, name
;
3892 if (gimple_code (stmt
) == GIMPLE_PHI
)
3893 lhs
= gimple_phi_result (stmt
);
3894 else if (is_gimple_assign (stmt
))
3895 lhs
= gimple_assign_lhs (stmt
);
3896 else if (is_gimple_call (stmt
))
3897 lhs
= gimple_call_lhs (stmt
);
3901 if (TREE_CODE (lhs
) != SSA_NAME
)
3903 decl
= SSA_NAME_VAR (lhs
);
3904 if (TREE_CODE (decl
) != PARM_DECL
)
3907 adj
= get_adjustment_for_base (adjustments
, decl
);
3911 repl
= get_replaced_param_substitute (adj
);
3912 name
= make_ssa_name (repl
, stmt
);
3916 fprintf (dump_file
, "replacing an SSA name of a removed param ");
3917 print_generic_expr (dump_file
, lhs
, 0);
3918 fprintf (dump_file
, " with ");
3919 print_generic_expr (dump_file
, name
, 0);
3920 fprintf (dump_file
, "\n");
3923 if (is_gimple_assign (stmt
))
3924 gimple_assign_set_lhs (stmt
, name
);
3925 else if (is_gimple_call (stmt
))
3926 gimple_call_set_lhs (stmt
, name
);
3928 gimple_phi_set_result (stmt
, name
);
3930 replace_uses_by (lhs
, name
);
3931 release_ssa_name (lhs
);
3935 /* If the expression *EXPR should be replaced by a reduction of a parameter, do
3936 so. ADJUSTMENTS is a pointer to a vector of adjustments. CONVERT
3937 specifies whether the function should care about type incompatibility the
3938 current and new expressions. If it is false, the function will leave
3939 incompatibility issues to the caller. Return true iff the expression
3943 sra_ipa_modify_expr (tree
*expr
, bool convert
,
3944 ipa_parm_adjustment_vec adjustments
)
3947 struct ipa_parm_adjustment
*adj
, *cand
= NULL
;
3948 HOST_WIDE_INT offset
, size
, max_size
;
3951 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
3953 if (TREE_CODE (*expr
) == BIT_FIELD_REF
3954 || TREE_CODE (*expr
) == IMAGPART_EXPR
3955 || TREE_CODE (*expr
) == REALPART_EXPR
)
3957 expr
= &TREE_OPERAND (*expr
, 0);
3961 base
= get_ref_base_and_extent (*expr
, &offset
, &size
, &max_size
);
3962 if (!base
|| size
== -1 || max_size
== -1)
3965 if (TREE_CODE (base
) == MEM_REF
)
3967 offset
+= mem_ref_offset (base
).low
* BITS_PER_UNIT
;
3968 base
= TREE_OPERAND (base
, 0);
3971 base
= get_ssa_base_param (base
);
3972 if (!base
|| TREE_CODE (base
) != PARM_DECL
)
3975 for (i
= 0; i
< len
; i
++)
3977 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
3979 if (adj
->base
== base
&&
3980 (adj
->offset
== offset
|| adj
->remove_param
))
3986 if (!cand
|| cand
->copy_param
|| cand
->remove_param
)
3990 src
= build_simple_mem_ref (cand
->reduction
);
3992 src
= cand
->reduction
;
3994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3996 fprintf (dump_file
, "About to replace expr ");
3997 print_generic_expr (dump_file
, *expr
, 0);
3998 fprintf (dump_file
, " with ");
3999 print_generic_expr (dump_file
, src
, 0);
4000 fprintf (dump_file
, "\n");
4003 if (convert
&& !useless_type_conversion_p (TREE_TYPE (*expr
), cand
->type
))
4005 tree vce
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (*expr
), src
);
4013 /* If the statement pointed to by STMT_PTR contains any expressions that need
4014 to replaced with a different one as noted by ADJUSTMENTS, do so. Handle any
4015 potential type incompatibilities (GSI is used to accommodate conversion
4016 statements and must point to the statement). Return true iff the statement
4020 sra_ipa_modify_assign (gimple
*stmt_ptr
, gimple_stmt_iterator
*gsi
,
4021 ipa_parm_adjustment_vec adjustments
)
4023 gimple stmt
= *stmt_ptr
;
4024 tree
*lhs_p
, *rhs_p
;
4027 if (!gimple_assign_single_p (stmt
))
4030 rhs_p
= gimple_assign_rhs1_ptr (stmt
);
4031 lhs_p
= gimple_assign_lhs_ptr (stmt
);
4033 any
= sra_ipa_modify_expr (rhs_p
, false, adjustments
);
4034 any
|= sra_ipa_modify_expr (lhs_p
, false, adjustments
);
4037 tree new_rhs
= NULL_TREE
;
4039 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p
), TREE_TYPE (*rhs_p
)))
4041 if (TREE_CODE (*rhs_p
) == CONSTRUCTOR
)
4043 /* V_C_Es of constructors can cause trouble (PR 42714). */
4044 if (is_gimple_reg_type (TREE_TYPE (*lhs_p
)))
4045 *rhs_p
= fold_convert (TREE_TYPE (*lhs_p
), integer_zero_node
);
4047 *rhs_p
= build_constructor (TREE_TYPE (*lhs_p
), 0);
4050 new_rhs
= fold_build1_loc (gimple_location (stmt
),
4051 VIEW_CONVERT_EXPR
, TREE_TYPE (*lhs_p
),
4054 else if (REFERENCE_CLASS_P (*rhs_p
)
4055 && is_gimple_reg_type (TREE_TYPE (*lhs_p
))
4056 && !is_gimple_reg (*lhs_p
))
4057 /* This can happen when an assignment in between two single field
4058 structures is turned into an assignment in between two pointers to
4059 scalars (PR 42237). */
4064 tree tmp
= force_gimple_operand_gsi (gsi
, new_rhs
, true, NULL_TREE
,
4065 true, GSI_SAME_STMT
);
4067 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
4076 /* Traverse the function body and all modifications as described in
4077 ADJUSTMENTS. Return true iff the CFG has been changed. */
4080 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments
)
4082 bool cfg_changed
= false;
4087 gimple_stmt_iterator gsi
;
4089 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4090 replace_removed_params_ssa_names (gsi_stmt (gsi
), adjustments
);
4092 gsi
= gsi_start_bb (bb
);
4093 while (!gsi_end_p (gsi
))
4095 gimple stmt
= gsi_stmt (gsi
);
4096 bool modified
= false;
4100 switch (gimple_code (stmt
))
4103 t
= gimple_return_retval_ptr (stmt
);
4104 if (*t
!= NULL_TREE
)
4105 modified
|= sra_ipa_modify_expr (t
, true, adjustments
);
4109 modified
|= sra_ipa_modify_assign (&stmt
, &gsi
, adjustments
);
4110 modified
|= replace_removed_params_ssa_names (stmt
, adjustments
);
4114 /* Operands must be processed before the lhs. */
4115 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
4117 t
= gimple_call_arg_ptr (stmt
, i
);
4118 modified
|= sra_ipa_modify_expr (t
, true, adjustments
);
4121 if (gimple_call_lhs (stmt
))
4123 t
= gimple_call_lhs_ptr (stmt
);
4124 modified
|= sra_ipa_modify_expr (t
, false, adjustments
);
4125 modified
|= replace_removed_params_ssa_names (stmt
,
4131 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
4133 t
= &TREE_VALUE (gimple_asm_input_op (stmt
, i
));
4134 modified
|= sra_ipa_modify_expr (t
, true, adjustments
);
4136 for (i
= 0; i
< gimple_asm_noutputs (stmt
); i
++)
4138 t
= &TREE_VALUE (gimple_asm_output_op (stmt
, i
));
4139 modified
|= sra_ipa_modify_expr (t
, false, adjustments
);
4150 if (maybe_clean_eh_stmt (stmt
)
4151 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
4161 /* Call gimple_debug_bind_reset_value on all debug statements describing
4162 gimple register parameters that are being removed or replaced. */
4165 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments
)
4169 len
= VEC_length (ipa_parm_adjustment_t
, adjustments
);
4170 for (i
= 0; i
< len
; i
++)
4172 struct ipa_parm_adjustment
*adj
;
4173 imm_use_iterator ui
;
4177 adj
= VEC_index (ipa_parm_adjustment_t
, adjustments
, i
);
4178 if (adj
->copy_param
|| !is_gimple_reg (adj
->base
))
4180 name
= gimple_default_def (cfun
, adj
->base
);
4183 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
4185 /* All other users must have been removed by
4186 ipa_sra_modify_function_body. */
4187 gcc_assert (is_gimple_debug (stmt
));
4188 gimple_debug_bind_reset_value (stmt
);
4194 /* Return true iff all callers have at least as many actual arguments as there
4195 are formal parameters in the current function. */
4198 all_callers_have_enough_arguments_p (struct cgraph_node
*node
)
4200 struct cgraph_edge
*cs
;
4201 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4202 if (!callsite_has_enough_arguments_p (cs
->call_stmt
))
4209 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
4212 convert_callers (struct cgraph_node
*node
, tree old_decl
,
4213 ipa_parm_adjustment_vec adjustments
)
4215 tree old_cur_fndecl
= current_function_decl
;
4216 struct cgraph_edge
*cs
;
4217 basic_block this_block
;
4218 bitmap recomputed_callers
= BITMAP_ALLOC (NULL
);
4220 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4222 current_function_decl
= cs
->caller
->decl
;
4223 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
4226 fprintf (dump_file
, "Adjusting call (%i -> %i) %s -> %s\n",
4227 cs
->caller
->uid
, cs
->callee
->uid
,
4228 cgraph_node_name (cs
->caller
),
4229 cgraph_node_name (cs
->callee
));
4231 ipa_modify_call_arguments (cs
, cs
->call_stmt
, adjustments
);
4236 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4237 if (bitmap_set_bit (recomputed_callers
, cs
->caller
->uid
))
4238 compute_inline_parameters (cs
->caller
);
4239 BITMAP_FREE (recomputed_callers
);
4241 current_function_decl
= old_cur_fndecl
;
4243 if (!encountered_recursive_call
)
4246 FOR_EACH_BB (this_block
)
4248 gimple_stmt_iterator gsi
;
4250 for (gsi
= gsi_start_bb (this_block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4252 gimple stmt
= gsi_stmt (gsi
);
4254 if (gimple_code (stmt
) != GIMPLE_CALL
)
4256 call_fndecl
= gimple_call_fndecl (stmt
);
4257 if (call_fndecl
== old_decl
)
4260 fprintf (dump_file
, "Adjusting recursive call");
4261 gimple_call_set_fndecl (stmt
, node
->decl
);
4262 ipa_modify_call_arguments (NULL
, stmt
, adjustments
);
4270 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4271 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */
4274 modify_function (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
4276 struct cgraph_node
*new_node
;
4277 struct cgraph_edge
*cs
;
4279 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
4283 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
4285 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
4286 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
4287 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
4289 rebuild_cgraph_edges ();
4291 current_function_decl
= NULL_TREE
;
4293 new_node
= cgraph_function_versioning (node
, redirect_callers
, NULL
, NULL
,
4294 NULL
, NULL
, "isra");
4295 current_function_decl
= new_node
->decl
;
4296 push_cfun (DECL_STRUCT_FUNCTION (new_node
->decl
));
4298 ipa_modify_formal_parameters (current_function_decl
, adjustments
, "ISRA");
4299 cfg_changed
= ipa_sra_modify_function_body (adjustments
);
4300 sra_ipa_reset_debug_stmts (adjustments
);
4301 convert_callers (new_node
, node
->decl
, adjustments
);
4302 cgraph_make_node_local (new_node
);
4306 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4307 attributes, return true otherwise. NODE is the cgraph node of the current
4311 ipa_sra_preliminary_function_checks (struct cgraph_node
*node
)
4313 if (!cgraph_node_can_be_local_p (node
))
4316 fprintf (dump_file
, "Function not local to this compilation unit.\n");
4320 if (!tree_versionable_function_p (node
->decl
))
4323 fprintf (dump_file
, "Function is not versionable.\n");
4327 if (DECL_VIRTUAL_P (current_function_decl
))
4330 fprintf (dump_file
, "Function is a virtual method.\n");
4334 if ((DECL_COMDAT (node
->decl
) || DECL_EXTERNAL (node
->decl
))
4335 && node
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
4338 fprintf (dump_file
, "Function too big to be made truly local.\n");
4346 "Function has no callers in this compilation unit.\n");
4353 fprintf (dump_file
, "Function uses stdarg. \n");
4357 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
4363 /* Perform early interprocedural SRA. */
4366 ipa_early_sra (void)
4368 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
4369 ipa_parm_adjustment_vec adjustments
;
4372 if (!ipa_sra_preliminary_function_checks (node
))
4376 sra_mode
= SRA_MODE_EARLY_IPA
;
4378 if (!find_param_candidates ())
4381 fprintf (dump_file
, "Function has no IPA-SRA candidates.\n");
4385 if (!all_callers_have_enough_arguments_p (node
))
4388 fprintf (dump_file
, "There are callers with insufficient number of "
4393 bb_dereferences
= XCNEWVEC (HOST_WIDE_INT
,
4395 * last_basic_block_for_function (cfun
));
4396 final_bbs
= BITMAP_ALLOC (NULL
);
4399 if (encountered_apply_args
)
4402 fprintf (dump_file
, "Function calls __builtin_apply_args().\n");
4406 if (encountered_unchangable_recursive_call
)
4409 fprintf (dump_file
, "Function calls itself with insufficient "
4410 "number of arguments.\n");
4414 adjustments
= analyze_all_param_acesses ();
4418 ipa_dump_param_adjustments (dump_file
, adjustments
, current_function_decl
);
4420 if (modify_function (node
, adjustments
))
4421 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
4423 ret
= TODO_update_ssa
;
4424 VEC_free (ipa_parm_adjustment_t
, heap
, adjustments
);
4426 statistics_counter_event (cfun
, "Unused parameters deleted",
4427 sra_stats
.deleted_unused_parameters
);
4428 statistics_counter_event (cfun
, "Scalar parameters converted to by-value",
4429 sra_stats
.scalar_by_ref_to_by_val
);
4430 statistics_counter_event (cfun
, "Aggregate parameters broken up",
4431 sra_stats
.aggregate_params_reduced
);
4432 statistics_counter_event (cfun
, "Aggregate parameter components created",
4433 sra_stats
.param_reductions_created
);
4436 BITMAP_FREE (final_bbs
);
4437 free (bb_dereferences
);
4439 sra_deinitialize ();
4443 /* Return if early ipa sra shall be performed. */
4445 ipa_early_sra_gate (void)
4447 return flag_ipa_sra
&& dbg_cnt (eipa_sra
);
4450 struct gimple_opt_pass pass_early_ipa_sra
=
4454 "eipa_sra", /* name */
4455 ipa_early_sra_gate
, /* gate */
4456 ipa_early_sra
, /* execute */
4459 0, /* static_pass_number */
4460 TV_IPA_SRA
, /* tv_id */
4461 0, /* properties_required */
4462 0, /* properties_provided */
4463 0, /* properties_destroyed */
4464 0, /* todo_flags_start */
4465 TODO_dump_func
| TODO_dump_cgraph
/* todo_flags_finish */