1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008-2024 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"
83 #include "alloc-pool.h"
84 #include "tree-pass.h"
87 #include "gimple-pretty-print.h"
89 #include "fold-const.h"
91 #include "stor-layout.h"
93 #include "gimple-iterator.h"
94 #include "gimplify-me.h"
95 #include "gimple-walk.h"
100 #include "builtins.h"
101 #include "tree-sra.h"
104 /* Enumeration of all aggregate reductions we can do. */
105 enum sra_mode
{ SRA_MODE_EARLY_IPA
, /* early call regularization */
106 SRA_MODE_EARLY_INTRA
, /* early intraprocedural SRA */
107 SRA_MODE_INTRA
}; /* late intraprocedural SRA */
109 /* Global variable describing which aggregate reduction we are performing at
111 static enum sra_mode sra_mode
;
115 /* ACCESS represents each access to an aggregate variable (as a whole or a
116 part). It can also represent a group of accesses that refer to exactly the
117 same fragment of an aggregate (i.e. those that have exactly the same offset
118 and size). Such representatives for a single aggregate, once determined,
119 are linked in a linked list and have the group fields set.
121 Moreover, when doing intraprocedural SRA, a tree is built from those
122 representatives (by the means of first_child and next_sibling pointers), in
123 which all items in a subtree are "within" the root, i.e. their offset is
124 greater or equal to offset of the root and offset+size is smaller or equal
125 to offset+size of the root. Children of an access are sorted by offset.
127 Note that accesses to parts of vector and complex number types always
128 represented by an access to the whole complex number or a vector. It is a
129 duty of the modifying functions to replace them appropriately. */
133 /* Values returned by `get_ref_base_and_extent' for each component reference
134 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
135 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
136 HOST_WIDE_INT offset
;
140 /* Expression. It is context dependent so do not use it to create new
141 expressions to access the original aggregate. See PR 42154 for a
147 /* The statement this access belongs to. */
150 /* Next group representative for this aggregate. */
151 struct access
*next_grp
;
153 /* Pointer to the group representative. Pointer to itself if the struct is
154 the representative. */
155 struct access
*group_representative
;
157 /* After access tree has been constructed, this points to the parent of the
158 current access, if there is one. NULL for roots. */
159 struct access
*parent
;
161 /* If this access has any children (in terms of the definition above), this
162 points to the first one. */
163 struct access
*first_child
;
165 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
167 struct access
*next_sibling
;
169 /* Pointers to the first and last element in the linked list of assign
170 links for propagation from LHS to RHS. */
171 struct assign_link
*first_rhs_link
, *last_rhs_link
;
173 /* Pointers to the first and last element in the linked list of assign
174 links for propagation from LHS to RHS. */
175 struct assign_link
*first_lhs_link
, *last_lhs_link
;
177 /* Pointer to the next access in the work queues. */
178 struct access
*next_rhs_queued
, *next_lhs_queued
;
180 /* Replacement variable for this access "region." Never to be accessed
181 directly, always only by the means of get_access_replacement() and only
182 when grp_to_be_replaced flag is set. */
183 tree replacement_decl
;
185 /* Is this access made in reverse storage order? */
186 unsigned reverse
: 1;
188 /* Is this particular access write access? */
191 /* Is this access currently in the rhs work queue? */
192 unsigned grp_rhs_queued
: 1;
194 /* Is this access currently in the lhs work queue? */
195 unsigned grp_lhs_queued
: 1;
197 /* Does this group contain a write access? This flag is propagated down the
199 unsigned grp_write
: 1;
201 /* Does this group contain a read access? This flag is propagated down the
203 unsigned grp_read
: 1;
205 /* Does this group contain a read access that comes from an assignment
206 statement? This flag is propagated down the access tree. */
207 unsigned grp_assignment_read
: 1;
209 /* Does this group contain a write access that comes from an assignment
210 statement? This flag is propagated down the access tree. */
211 unsigned grp_assignment_write
: 1;
213 /* Does this group contain a read access through a scalar type? This flag is
214 not propagated in the access tree in any direction. */
215 unsigned grp_scalar_read
: 1;
217 /* Does this group contain a write access through a scalar type? This flag
218 is not propagated in the access tree in any direction. */
219 unsigned grp_scalar_write
: 1;
221 /* In a root of an access tree, true means that the entire tree should be
222 totally scalarized - that all scalar leafs should be scalarized and
223 non-root grp_total_scalarization accesses should be honored. Otherwise,
224 non-root accesses with grp_total_scalarization should never get scalar
226 unsigned grp_total_scalarization
: 1;
228 /* Other passes of the analysis use this bit to make function
229 analyze_access_subtree create scalar replacements for this group if
231 unsigned grp_hint
: 1;
233 /* Is the subtree rooted in this access fully covered by scalar
235 unsigned grp_covered
: 1;
237 /* If set to true, this access and all below it in an access tree must not be
239 unsigned grp_unscalarizable_region
: 1;
241 /* Whether data have been written to parts of the aggregate covered by this
242 access which is not to be scalarized. This flag is propagated up in the
244 unsigned grp_unscalarized_data
: 1;
246 /* Set if all accesses in the group consist of the same chain of
247 COMPONENT_REFs and ARRAY_REFs. */
248 unsigned grp_same_access_path
: 1;
250 /* Does this access and/or group contain a write access through a
252 unsigned grp_partial_lhs
: 1;
254 /* Set when a scalar replacement should be created for this variable. */
255 unsigned grp_to_be_replaced
: 1;
257 /* Set when we want a replacement for the sole purpose of having it in
258 generated debug statements. */
259 unsigned grp_to_be_debug_replaced
: 1;
261 /* Should TREE_NO_WARNING of a replacement be set? */
262 unsigned grp_no_warning
: 1;
264 /* Result of propagation accross link from LHS to RHS. */
265 unsigned grp_result_of_prop_from_lhs
: 1;
268 typedef struct access
*access_p
;
271 /* Alloc pool for allocating access structures. */
272 static object_allocator
<struct access
> access_pool ("SRA accesses");
274 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
275 are used to propagate subaccesses from rhs to lhs and vice versa as long as
276 they don't conflict with what is already there. In the RHS->LHS direction,
277 we also propagate grp_write flag to lazily mark that the access contains any
281 struct access
*lacc
, *racc
;
282 struct assign_link
*next_rhs
, *next_lhs
;
285 /* Alloc pool for allocating assign link structures. */
286 static object_allocator
<assign_link
> assign_link_pool ("SRA links");
288 /* Base (tree) -> Vector (vec<access_p> *) map. */
289 static hash_map
<tree
, auto_vec
<access_p
> > *base_access_vec
;
291 /* Hash to limit creation of artificial accesses */
292 static hash_map
<tree
, unsigned> *propagation_budget
;
294 /* Candidate hash table helpers. */
296 struct uid_decl_hasher
: nofree_ptr_hash
<tree_node
>
298 static inline hashval_t
hash (const tree_node
*);
299 static inline bool equal (const tree_node
*, const tree_node
*);
302 /* Hash a tree in a uid_decl_map. */
305 uid_decl_hasher::hash (const tree_node
*item
)
307 return item
->decl_minimal
.uid
;
310 /* Return true if the DECL_UID in both trees are equal. */
313 uid_decl_hasher::equal (const tree_node
*a
, const tree_node
*b
)
315 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
318 /* Set of candidates. */
319 static bitmap candidate_bitmap
;
320 static hash_table
<uid_decl_hasher
> *candidates
;
322 /* For a candidate UID return the candidates decl. */
325 candidate (unsigned uid
)
328 t
.decl_minimal
.uid
= uid
;
329 return candidates
->find_with_hash (&t
, static_cast <hashval_t
> (uid
));
332 /* Bitmap of candidates which we should try to entirely scalarize away and
333 those which cannot be (because they are and need be used as a whole). */
334 static bitmap should_scalarize_away_bitmap
, cannot_scalarize_away_bitmap
;
336 /* Bitmap of candidates in the constant pool, which cannot be scalarized
337 because this would produce non-constant expressions (e.g. Ada). */
338 static bitmap disqualified_constants
;
340 /* Bitmap of candidates which are passed by reference in call arguments. */
341 static bitmap passed_by_ref_in_call
;
343 /* Obstack for creation of fancy names. */
344 static struct obstack name_obstack
;
346 /* Head of a linked list of accesses that need to have its subaccesses
347 propagated to their assignment counterparts. */
348 static struct access
*rhs_work_queue_head
, *lhs_work_queue_head
;
350 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
351 representative fields are dumped, otherwise those which only describe the
352 individual access are. */
356 /* Number of processed aggregates is readily available in
357 analyze_all_variable_accesses and so is not stored here. */
359 /* Number of created scalar replacements. */
362 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
366 /* Number of statements created by generate_subtree_copies. */
369 /* Number of statements created by load_assign_lhs_subreplacements. */
372 /* Number of times sra_modify_assign has deleted a statement. */
375 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
376 RHS reparately due to type conversions or nonexistent matching
378 int separate_lhs_rhs_handling
;
380 /* Number of parameters that were removed because they were unused. */
381 int deleted_unused_parameters
;
383 /* Number of scalars passed as parameters by reference that have been
384 converted to be passed by value. */
385 int scalar_by_ref_to_by_val
;
387 /* Number of aggregate parameters that were replaced by one or more of their
389 int aggregate_params_reduced
;
391 /* Numbber of components created when splitting aggregate parameters. */
392 int param_reductions_created
;
394 /* Number of deferred_init calls that are modified. */
397 /* Number of deferred_init calls that are created by
398 generate_subtree_deferred_init. */
399 int subtree_deferred_init
;
403 dump_access (FILE *f
, struct access
*access
, bool grp
)
405 fprintf (f
, "access { ");
406 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
407 print_generic_expr (f
, access
->base
);
408 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
409 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
410 fprintf (f
, ", expr = ");
411 print_generic_expr (f
, access
->expr
);
412 fprintf (f
, ", type = ");
413 print_generic_expr (f
, access
->type
);
414 fprintf (f
, ", reverse = %d", access
->reverse
);
416 fprintf (f
, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
417 "grp_assignment_write = %d, grp_scalar_read = %d, "
418 "grp_scalar_write = %d, grp_total_scalarization = %d, "
419 "grp_hint = %d, grp_covered = %d, "
420 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
421 "grp_same_access_path = %d, grp_partial_lhs = %d, "
422 "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d}\n",
423 access
->grp_read
, access
->grp_write
, access
->grp_assignment_read
,
424 access
->grp_assignment_write
, access
->grp_scalar_read
,
425 access
->grp_scalar_write
, access
->grp_total_scalarization
,
426 access
->grp_hint
, access
->grp_covered
,
427 access
->grp_unscalarizable_region
, access
->grp_unscalarized_data
,
428 access
->grp_same_access_path
, access
->grp_partial_lhs
,
429 access
->grp_to_be_replaced
, access
->grp_to_be_debug_replaced
);
431 fprintf (f
, ", write = %d, grp_total_scalarization = %d, "
432 "grp_partial_lhs = %d}\n",
433 access
->write
, access
->grp_total_scalarization
,
434 access
->grp_partial_lhs
);
437 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
440 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
446 for (i
= 0; i
< level
; i
++)
449 dump_access (f
, access
, true);
451 if (access
->first_child
)
452 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
454 access
= access
->next_sibling
;
459 /* Dump all access trees for a variable, given the pointer to the first root in
463 dump_access_tree (FILE *f
, struct access
*access
)
465 for (; access
; access
= access
->next_grp
)
466 dump_access_tree_1 (f
, access
, 0);
469 /* Return true iff ACC is non-NULL and has subaccesses. */
472 access_has_children_p (struct access
*acc
)
474 return acc
&& acc
->first_child
;
477 /* Return true iff ACC is (partly) covered by at least one replacement. */
480 access_has_replacements_p (struct access
*acc
)
482 struct access
*child
;
483 if (acc
->grp_to_be_replaced
)
485 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
486 if (access_has_replacements_p (child
))
491 /* Return a vector of pointers to accesses for the variable given in BASE or
492 NULL if there is none. */
494 static vec
<access_p
> *
495 get_base_access_vector (tree base
)
497 return base_access_vec
->get (base
);
500 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
501 in ACCESS. Return NULL if it cannot be found. */
503 static struct access
*
504 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
507 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
509 struct access
*child
= access
->first_child
;
511 while (child
&& (child
->offset
+ child
->size
<= offset
))
512 child
= child
->next_sibling
;
516 /* Total scalarization does not replace single field structures with their
517 single field but rather creates an access for them underneath. Look for
520 while (access
->first_child
521 && access
->first_child
->offset
== offset
522 && access
->first_child
->size
== size
)
523 access
= access
->first_child
;
528 /* Return the first group representative for DECL or NULL if none exists. */
530 static struct access
*
531 get_first_repr_for_decl (tree base
)
533 vec
<access_p
> *access_vec
;
535 access_vec
= get_base_access_vector (base
);
539 return (*access_vec
)[0];
542 /* Find an access representative for the variable BASE and given OFFSET and
543 SIZE. Requires that access trees have already been built. Return NULL if
544 it cannot be found. */
546 static struct access
*
547 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
550 struct access
*access
;
552 access
= get_first_repr_for_decl (base
);
553 while (access
&& (access
->offset
+ access
->size
<= offset
))
554 access
= access
->next_grp
;
558 return find_access_in_subtree (access
, offset
, size
);
561 /* Add LINK to the linked list of assign links of RACC. */
564 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
566 gcc_assert (link
->racc
== racc
);
568 if (!racc
->first_rhs_link
)
570 gcc_assert (!racc
->last_rhs_link
);
571 racc
->first_rhs_link
= link
;
574 racc
->last_rhs_link
->next_rhs
= link
;
576 racc
->last_rhs_link
= link
;
577 link
->next_rhs
= NULL
;
580 /* Add LINK to the linked list of lhs assign links of LACC. */
583 add_link_to_lhs (struct access
*lacc
, struct assign_link
*link
)
585 gcc_assert (link
->lacc
== lacc
);
587 if (!lacc
->first_lhs_link
)
589 gcc_assert (!lacc
->last_lhs_link
);
590 lacc
->first_lhs_link
= link
;
593 lacc
->last_lhs_link
->next_lhs
= link
;
595 lacc
->last_lhs_link
= link
;
596 link
->next_lhs
= NULL
;
599 /* Move all link structures in their linked list in OLD_ACC to the linked list
602 relink_to_new_repr (struct access
*new_acc
, struct access
*old_acc
)
604 if (old_acc
->first_rhs_link
)
607 if (new_acc
->first_rhs_link
)
609 gcc_assert (!new_acc
->last_rhs_link
->next_rhs
);
610 gcc_assert (!old_acc
->last_rhs_link
611 || !old_acc
->last_rhs_link
->next_rhs
);
613 new_acc
->last_rhs_link
->next_rhs
= old_acc
->first_rhs_link
;
614 new_acc
->last_rhs_link
= old_acc
->last_rhs_link
;
618 gcc_assert (!new_acc
->last_rhs_link
);
620 new_acc
->first_rhs_link
= old_acc
->first_rhs_link
;
621 new_acc
->last_rhs_link
= old_acc
->last_rhs_link
;
623 old_acc
->first_rhs_link
= old_acc
->last_rhs_link
= NULL
;
626 gcc_assert (!old_acc
->last_rhs_link
);
628 if (old_acc
->first_lhs_link
)
631 if (new_acc
->first_lhs_link
)
633 gcc_assert (!new_acc
->last_lhs_link
->next_lhs
);
634 gcc_assert (!old_acc
->last_lhs_link
635 || !old_acc
->last_lhs_link
->next_lhs
);
637 new_acc
->last_lhs_link
->next_lhs
= old_acc
->first_lhs_link
;
638 new_acc
->last_lhs_link
= old_acc
->last_lhs_link
;
642 gcc_assert (!new_acc
->last_lhs_link
);
644 new_acc
->first_lhs_link
= old_acc
->first_lhs_link
;
645 new_acc
->last_lhs_link
= old_acc
->last_lhs_link
;
647 old_acc
->first_lhs_link
= old_acc
->last_lhs_link
= NULL
;
650 gcc_assert (!old_acc
->last_lhs_link
);
654 /* Add ACCESS to the work to queue for propagation of subaccesses from RHS to
655 LHS (which is actually a stack). */
658 add_access_to_rhs_work_queue (struct access
*access
)
660 if (access
->first_rhs_link
&& !access
->grp_rhs_queued
)
662 gcc_assert (!access
->next_rhs_queued
);
663 access
->next_rhs_queued
= rhs_work_queue_head
;
664 access
->grp_rhs_queued
= 1;
665 rhs_work_queue_head
= access
;
669 /* Add ACCESS to the work to queue for propagation of subaccesses from LHS to
670 RHS (which is actually a stack). */
673 add_access_to_lhs_work_queue (struct access
*access
)
675 if (access
->first_lhs_link
&& !access
->grp_lhs_queued
)
677 gcc_assert (!access
->next_lhs_queued
);
678 access
->next_lhs_queued
= lhs_work_queue_head
;
679 access
->grp_lhs_queued
= 1;
680 lhs_work_queue_head
= access
;
684 /* Pop an access from the work queue for propagating from RHS to LHS, and
685 return it, assuming there is one. */
687 static struct access
*
688 pop_access_from_rhs_work_queue (void)
690 struct access
*access
= rhs_work_queue_head
;
692 rhs_work_queue_head
= access
->next_rhs_queued
;
693 access
->next_rhs_queued
= NULL
;
694 access
->grp_rhs_queued
= 0;
698 /* Pop an access from the work queue for propagating from LHS to RHS, and
699 return it, assuming there is one. */
701 static struct access
*
702 pop_access_from_lhs_work_queue (void)
704 struct access
*access
= lhs_work_queue_head
;
706 lhs_work_queue_head
= access
->next_lhs_queued
;
707 access
->next_lhs_queued
= NULL
;
708 access
->grp_lhs_queued
= 0;
712 /* Allocate necessary structures. */
715 sra_initialize (void)
717 candidate_bitmap
= BITMAP_ALLOC (NULL
);
718 candidates
= new hash_table
<uid_decl_hasher
>
719 (vec_safe_length (cfun
->local_decls
) / 2);
720 should_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
721 cannot_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
722 disqualified_constants
= BITMAP_ALLOC (NULL
);
723 passed_by_ref_in_call
= BITMAP_ALLOC (NULL
);
724 gcc_obstack_init (&name_obstack
);
725 base_access_vec
= new hash_map
<tree
, auto_vec
<access_p
> >;
726 memset (&sra_stats
, 0, sizeof (sra_stats
));
729 /* Deallocate all general structures. */
732 sra_deinitialize (void)
734 BITMAP_FREE (candidate_bitmap
);
737 BITMAP_FREE (should_scalarize_away_bitmap
);
738 BITMAP_FREE (cannot_scalarize_away_bitmap
);
739 BITMAP_FREE (disqualified_constants
);
740 BITMAP_FREE (passed_by_ref_in_call
);
741 access_pool
.release ();
742 assign_link_pool
.release ();
743 obstack_free (&name_obstack
, NULL
);
745 delete base_access_vec
;
748 /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
750 static bool constant_decl_p (tree decl
)
752 return VAR_P (decl
) && DECL_IN_CONSTANT_POOL (decl
);
755 /* Remove DECL from candidates for SRA and write REASON to the dump file if
759 disqualify_candidate (tree decl
, const char *reason
)
761 if (bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
)))
762 candidates
->remove_elt_with_hash (decl
, DECL_UID (decl
));
763 if (constant_decl_p (decl
))
764 bitmap_set_bit (disqualified_constants
, DECL_UID (decl
));
766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
768 fprintf (dump_file
, "! Disqualifying ");
769 print_generic_expr (dump_file
, decl
);
770 fprintf (dump_file
, " - %s\n", reason
);
774 /* Return true iff the type contains a field or an element which does not allow
775 scalarization. Use VISITED_TYPES to avoid re-checking already checked
779 type_internals_preclude_sra_p_1 (tree type
, const char **msg
,
780 hash_set
<tree
> *visited_types
)
785 if (visited_types
->contains (type
))
787 visited_types
->add (type
);
789 switch (TREE_CODE (type
))
793 case QUAL_UNION_TYPE
:
794 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
795 if (TREE_CODE (fld
) == FIELD_DECL
)
797 if (TREE_CODE (fld
) == FUNCTION_DECL
)
799 tree ft
= TREE_TYPE (fld
);
801 if (TREE_THIS_VOLATILE (fld
))
803 *msg
= "volatile structure field";
806 if (!DECL_FIELD_OFFSET (fld
))
808 *msg
= "no structure field offset";
811 if (!DECL_SIZE (fld
))
813 *msg
= "zero structure field size";
816 if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld
)))
818 *msg
= "structure field offset not fixed";
821 if (!tree_fits_uhwi_p (DECL_SIZE (fld
)))
823 *msg
= "structure field size not fixed";
826 if (!tree_fits_shwi_p (bit_position (fld
)))
828 *msg
= "structure field size too big";
831 if (AGGREGATE_TYPE_P (ft
)
832 && int_bit_position (fld
) % BITS_PER_UNIT
!= 0)
834 *msg
= "structure field is bit field";
838 if (AGGREGATE_TYPE_P (ft
)
839 && type_internals_preclude_sra_p_1 (ft
, msg
, visited_types
))
846 et
= TREE_TYPE (type
);
848 if (TYPE_VOLATILE (et
))
850 *msg
= "element type is volatile";
854 if (AGGREGATE_TYPE_P (et
)
855 && type_internals_preclude_sra_p_1 (et
, msg
, visited_types
))
865 /* Return true iff the type contains a field or an element which does not allow
869 type_internals_preclude_sra_p (tree type
, const char **msg
)
871 hash_set
<tree
> visited_types
;
872 return type_internals_preclude_sra_p_1 (type
, msg
, &visited_types
);
876 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
877 the three fields. Also add it to the vector of accesses corresponding to
878 the base. Finally, return the new access. */
880 static struct access
*
881 create_access_1 (tree base
, HOST_WIDE_INT offset
, HOST_WIDE_INT size
)
883 struct access
*access
= access_pool
.allocate ();
885 memset (access
, 0, sizeof (struct access
));
887 access
->offset
= offset
;
890 base_access_vec
->get_or_insert (base
).safe_push (access
);
895 static bool maybe_add_sra_candidate (tree
);
897 /* Create and insert access for EXPR. Return created access, or NULL if it is
898 not possible. Also scan for uses of constant pool as we go along and add
901 static struct access
*
902 create_access (tree expr
, gimple
*stmt
, bool write
)
904 struct access
*access
;
905 poly_int64 poffset
, psize
, pmax_size
;
907 bool reverse
, unscalarizable_region
= false;
909 base
= get_ref_base_and_extent (expr
, &poffset
, &psize
, &pmax_size
,
912 /* For constant-pool entries, check we can substitute the constant value. */
913 if (constant_decl_p (base
)
914 && !bitmap_bit_p (disqualified_constants
, DECL_UID (base
)))
917 && !is_gimple_reg_type (TREE_TYPE (expr
))
918 && dump_file
&& (dump_flags
& TDF_DETAILS
))
920 /* This occurs in Ada with accesses to ARRAY_RANGE_REFs,
921 and elements of multidimensional arrays (which are
922 multi-element arrays in their own right). */
923 fprintf (dump_file
, "Allowing non-reg-type load of part"
924 " of constant-pool entry: ");
925 print_generic_expr (dump_file
, expr
);
927 maybe_add_sra_candidate (base
);
930 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
933 if (write
&& TREE_READONLY (base
))
935 disqualify_candidate (base
, "Encountered a store to a read-only decl.");
939 HOST_WIDE_INT offset
, size
, max_size
;
940 if (!poffset
.is_constant (&offset
)
941 || !psize
.is_constant (&size
)
942 || !pmax_size
.is_constant (&max_size
))
944 disqualify_candidate (base
, "Encountered a polynomial-sized access.");
948 if (size
!= max_size
)
951 unscalarizable_region
= true;
957 disqualify_candidate (base
, "Encountered a negative offset access.");
962 disqualify_candidate (base
, "Encountered an unconstrained access.");
965 if (offset
+ size
> tree_to_shwi (DECL_SIZE (base
)))
967 disqualify_candidate (base
, "Encountered an access beyond the base.");
970 if (TREE_CODE (TREE_TYPE (expr
)) == BITINT_TYPE
971 && size
> WIDE_INT_MAX_PRECISION
- 1)
973 disqualify_candidate (base
, "Encountered too large _BitInt access.");
977 access
= create_access_1 (base
, offset
, size
);
979 access
->type
= TREE_TYPE (expr
);
980 access
->write
= write
;
981 access
->grp_unscalarizable_region
= unscalarizable_region
;
983 access
->reverse
= reverse
;
989 /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length
990 ARRAY_TYPE with fields that are either of gimple register types (excluding
991 bit-fields) or (recursively) scalarizable types. CONST_DECL must be true if
992 we are considering a decl from constant pool. If it is false, char arrays
996 scalarizable_type_p (tree type
, bool const_decl
)
998 if (is_gimple_reg_type (type
))
1000 if (type_contains_placeholder_p (type
))
1003 bool have_predecessor_field
= false;
1004 HOST_WIDE_INT prev_pos
= 0;
1006 switch (TREE_CODE (type
))
1009 for (tree fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1010 if (TREE_CODE (fld
) == FIELD_DECL
)
1012 tree ft
= TREE_TYPE (fld
);
1014 if (zerop (DECL_SIZE (fld
)))
1017 HOST_WIDE_INT pos
= int_bit_position (fld
);
1018 if (have_predecessor_field
1022 have_predecessor_field
= true;
1025 if (DECL_BIT_FIELD (fld
))
1028 if (!scalarizable_type_p (ft
, const_decl
))
1036 HOST_WIDE_INT min_elem_size
;
1040 min_elem_size
= BITS_PER_UNIT
;
1042 if (TYPE_DOMAIN (type
) == NULL_TREE
1043 || !tree_fits_shwi_p (TYPE_SIZE (type
))
1044 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type
)))
1045 || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type
))) <= min_elem_size
)
1046 || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type
))))
1048 if (tree_to_shwi (TYPE_SIZE (type
)) == 0
1049 && TYPE_MAX_VALUE (TYPE_DOMAIN (type
)) == NULL_TREE
)
1050 /* Zero-element array, should not prevent scalarization. */
1052 else if ((tree_to_shwi (TYPE_SIZE (type
)) <= 0)
1053 || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type
))))
1054 /* Variable-length array, do not allow scalarization. */
1057 tree elem
= TREE_TYPE (type
);
1058 if (!scalarizable_type_p (elem
, const_decl
))
1067 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1070 contains_view_convert_expr_p (const_tree ref
)
1072 while (handled_component_p (ref
))
1074 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
)
1076 ref
= TREE_OPERAND (ref
, 0);
1082 /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1083 bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1084 it points to will be set if REF contains any of the above or a MEM_REF
1085 expression that effectively performs type conversion. */
1088 contains_vce_or_bfcref_p (const_tree ref
, bool *type_changing_p
= NULL
)
1090 while (handled_component_p (ref
))
1092 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
1093 || (TREE_CODE (ref
) == COMPONENT_REF
1094 && DECL_BIT_FIELD (TREE_OPERAND (ref
, 1))))
1096 if (type_changing_p
)
1097 *type_changing_p
= true;
1100 ref
= TREE_OPERAND (ref
, 0);
1103 if (!type_changing_p
1104 || TREE_CODE (ref
) != MEM_REF
1105 || TREE_CODE (TREE_OPERAND (ref
, 0)) != ADDR_EXPR
)
1108 tree mem
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
1109 if (TYPE_MAIN_VARIANT (TREE_TYPE (ref
))
1110 != TYPE_MAIN_VARIANT (TREE_TYPE (mem
)))
1111 *type_changing_p
= true;
1116 /* Search the given tree for a declaration by skipping handled components and
1117 exclude it from the candidates. */
1120 disqualify_base_of_expr (tree t
, const char *reason
)
1122 t
= get_base_address (t
);
1123 if (t
&& DECL_P (t
))
1124 disqualify_candidate (t
, reason
);
1127 /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1130 sra_handled_bf_read_p (tree expr
)
1132 uint64_t size
, offset
;
1133 if (bit_field_size (expr
).is_constant (&size
)
1134 && bit_field_offset (expr
).is_constant (&offset
)
1135 && size
% BITS_PER_UNIT
== 0
1136 && offset
% BITS_PER_UNIT
== 0
1137 && pow2p_hwi (size
))
1142 /* Scan expression EXPR and create access structures for all accesses to
1143 candidates for scalarization. Return the created access or NULL if none is
1146 static struct access
*
1147 build_access_from_expr_1 (tree expr
, gimple
*stmt
, bool write
)
1149 /* We only allow ADDR_EXPRs in arguments of function calls and those must
1150 have been dealt with in build_access_from_call_arg. Any other address
1151 taking should have been caught by scan_visit_addr. */
1152 if (TREE_CODE (expr
) == ADDR_EXPR
)
1154 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
1155 gcc_assert (!DECL_P (base
)
1156 || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)));
1160 struct access
*ret
= NULL
;
1163 if ((TREE_CODE (expr
) == BIT_FIELD_REF
1164 && (write
|| !sra_handled_bf_read_p (expr
)))
1165 || TREE_CODE (expr
) == IMAGPART_EXPR
1166 || TREE_CODE (expr
) == REALPART_EXPR
)
1168 expr
= TREE_OPERAND (expr
, 0);
1172 partial_ref
= false;
1174 if (storage_order_barrier_p (expr
))
1176 disqualify_base_of_expr (expr
, "storage order barrier.");
1180 /* We need to dive through V_C_Es in order to get the size of its parameter
1181 and not the result type. Ada produces such statements. We are also
1182 capable of handling the topmost V_C_E but not any of those buried in other
1183 handled components. */
1184 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
1185 expr
= TREE_OPERAND (expr
, 0);
1187 if (contains_view_convert_expr_p (expr
))
1189 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
1193 if (TREE_THIS_VOLATILE (expr
))
1195 disqualify_base_of_expr (expr
, "part of a volatile reference.");
1199 switch (TREE_CODE (expr
))
1202 if (TREE_CODE (TREE_OPERAND (expr
, 0)) != ADDR_EXPR
)
1210 case ARRAY_RANGE_REF
:
1212 ret
= create_access (expr
, stmt
, write
);
1219 if (write
&& partial_ref
&& ret
)
1220 ret
->grp_partial_lhs
= 1;
1225 /* Scan expression EXPR and create access structures for all accesses to
1226 candidates for scalarization. Return true if any access has been inserted.
1227 STMT must be the statement from which the expression is taken, WRITE must be
1228 true if the expression is a store and false otherwise. */
1231 build_access_from_expr (tree expr
, gimple
*stmt
, bool write
)
1233 struct access
*access
;
1235 access
= build_access_from_expr_1 (expr
, stmt
, write
);
1238 /* This means the aggregate is accesses as a whole in a way other than an
1239 assign statement and thus cannot be removed even if we had a scalar
1240 replacement for everything. */
1241 if (cannot_scalarize_away_bitmap
)
1242 bitmap_set_bit (cannot_scalarize_away_bitmap
, DECL_UID (access
->base
));
1248 enum out_edge_check
{ SRA_OUTGOING_EDGES_UNCHECKED
, SRA_OUTGOING_EDGES_OK
,
1249 SRA_OUTGOING_EDGES_FAIL
};
1251 /* Return true if STMT terminates BB and there is an abnormal edge going out of
1252 the BB and remember the decision in OE_CHECK. */
1255 abnormal_edge_after_stmt_p (gimple
*stmt
, enum out_edge_check
*oe_check
)
1257 if (*oe_check
== SRA_OUTGOING_EDGES_OK
)
1259 if (*oe_check
== SRA_OUTGOING_EDGES_FAIL
)
1261 if (stmt_ends_bb_p (stmt
))
1265 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1266 if (e
->flags
& EDGE_ABNORMAL
)
1268 *oe_check
= SRA_OUTGOING_EDGES_FAIL
;
1272 *oe_check
= SRA_OUTGOING_EDGES_OK
;
1276 /* Scan expression EXPR which is an argument of a call and create access
1277 structures for all accesses to candidates for scalarization. Return true
1278 if any access has been inserted. STMT must be the statement from which the
1279 expression is taken. CAN_BE_RETURNED must be true if call argument flags
1280 do not rule out that the argument is directly returned. OE_CHECK is used
1281 to remember result of a test for abnormal outgoing edges after this
1285 build_access_from_call_arg (tree expr
, gimple
*stmt
, bool can_be_returned
,
1286 enum out_edge_check
*oe_check
)
1288 if (TREE_CODE (expr
) == ADDR_EXPR
)
1290 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
1292 if (can_be_returned
)
1294 disqualify_base_of_expr (base
, "Address possibly returned, "
1295 "leading to an alis SRA may not know.");
1298 if (abnormal_edge_after_stmt_p (stmt
, oe_check
))
1300 disqualify_base_of_expr (base
, "May lead to need to add statements "
1301 "to abnormal edge.");
1305 bool read
= build_access_from_expr (base
, stmt
, false);
1306 bool write
= build_access_from_expr (base
, stmt
, true);
1309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1311 fprintf (dump_file
, "Allowed ADDR_EXPR of ");
1312 print_generic_expr (dump_file
, base
);
1313 fprintf (dump_file
, " because of ");
1314 print_gimple_stmt (dump_file
, stmt
, 0);
1315 fprintf (dump_file
, "\n");
1317 bitmap_set_bit (passed_by_ref_in_call
, DECL_UID (base
));
1324 return build_access_from_expr (expr
, stmt
, false);
1328 /* Return the single non-EH successor edge of BB or NULL if there is none or
1332 single_non_eh_succ (basic_block bb
)
1337 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1338 if (!(e
->flags
& EDGE_EH
))
1348 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1349 there is no alternative spot where to put statements SRA might need to
1350 generate after it. The spot we are looking for is an edge leading to a
1351 single non-EH successor, if it exists and is indeed single. RHS may be
1352 NULL, in that case ignore it. */
1355 disqualify_if_bad_bb_terminating_stmt (gimple
*stmt
, tree lhs
, tree rhs
)
1357 if (stmt_ends_bb_p (stmt
))
1359 if (single_non_eh_succ (gimple_bb (stmt
)))
1362 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
1364 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
1370 /* Return true if the nature of BASE is such that it contains data even if
1371 there is no write to it in the function. */
1374 comes_initialized_p (tree base
)
1376 return TREE_CODE (base
) == PARM_DECL
|| constant_decl_p (base
);
1379 /* Scan expressions occurring in STMT, create access structures for all accesses
1380 to candidates for scalarization and remove those candidates which occur in
1381 statements or expressions that prevent them from being split apart. Return
1382 true if any access has been inserted. */
1385 build_accesses_from_assign (gimple
*stmt
)
1388 struct access
*lacc
, *racc
;
1390 if (!gimple_assign_single_p (stmt
)
1391 /* Scope clobbers don't influence scalarization. */
1392 || gimple_clobber_p (stmt
))
1395 lhs
= gimple_assign_lhs (stmt
);
1396 rhs
= gimple_assign_rhs1 (stmt
);
1398 if (disqualify_if_bad_bb_terminating_stmt (stmt
, lhs
, rhs
))
1401 racc
= build_access_from_expr_1 (rhs
, stmt
, false);
1402 lacc
= build_access_from_expr_1 (lhs
, stmt
, true);
1406 lacc
->grp_assignment_write
= 1;
1407 if (storage_order_barrier_p (rhs
))
1408 lacc
->grp_unscalarizable_region
= 1;
1410 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (lacc
->type
))
1412 bool type_changing_p
= false;
1413 contains_vce_or_bfcref_p (lhs
, &type_changing_p
);
1414 if (type_changing_p
)
1415 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1416 DECL_UID (lacc
->base
));
1422 racc
->grp_assignment_read
= 1;
1423 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (racc
->type
))
1425 bool type_changing_p
= false;
1426 contains_vce_or_bfcref_p (rhs
, &type_changing_p
);
1428 if (type_changing_p
|| gimple_has_volatile_ops (stmt
))
1429 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1430 DECL_UID (racc
->base
));
1432 bitmap_set_bit (should_scalarize_away_bitmap
,
1433 DECL_UID (racc
->base
));
1435 if (storage_order_barrier_p (lhs
))
1436 racc
->grp_unscalarizable_region
= 1;
1440 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1441 && !lacc
->grp_unscalarizable_region
1442 && !racc
->grp_unscalarizable_region
1443 && AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
1444 && lacc
->size
== racc
->size
1445 && useless_type_conversion_p (lacc
->type
, racc
->type
))
1447 struct assign_link
*link
;
1449 link
= assign_link_pool
.allocate ();
1450 memset (link
, 0, sizeof (struct assign_link
));
1454 add_link_to_rhs (racc
, link
);
1455 add_link_to_lhs (lacc
, link
);
1456 add_access_to_rhs_work_queue (racc
);
1457 add_access_to_lhs_work_queue (lacc
);
1459 /* Let's delay marking the areas as written until propagation of accesses
1460 across link, unless the nature of rhs tells us that its data comes
1462 if (!comes_initialized_p (racc
->base
))
1463 lacc
->write
= false;
1466 return lacc
|| racc
;
1469 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to detect taking
1470 addresses of candidates a places which are not call arguments. Such
1471 candidates are disqalified from SRA. This also applies to GIMPLE_ASM
1472 operands with memory constrains which cannot be scalarized. */
1475 scan_visit_addr (gimple
*, tree op
, tree
, void *)
1477 op
= get_base_address (op
);
1480 disqualify_candidate (op
, "Address taken in a non-call-argument context.");
1485 /* Scan function and look for interesting expressions and create access
1486 structures for them. Return true iff any access is created. */
1489 scan_function (void)
1494 FOR_EACH_BB_FN (bb
, cfun
)
1496 gimple_stmt_iterator gsi
;
1497 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1498 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), NULL
, NULL
, NULL
,
1501 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1503 gimple
*stmt
= gsi_stmt (gsi
);
1507 if (gimple_code (stmt
) != GIMPLE_CALL
)
1508 walk_stmt_load_store_addr_ops (stmt
, NULL
, NULL
, NULL
,
1511 switch (gimple_code (stmt
))
1514 t
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1516 ret
|= build_access_from_expr (t
, stmt
, false);
1520 ret
|= build_accesses_from_assign (stmt
);
1525 enum out_edge_check oe_check
= SRA_OUTGOING_EDGES_UNCHECKED
;
1526 gcall
*call
= as_a
<gcall
*> (stmt
);
1527 for (i
= 0; i
< gimple_call_num_args (call
); i
++)
1529 bool can_be_returned
;
1530 if (gimple_call_lhs (call
))
1532 int af
= gimple_call_arg_flags (call
, i
);
1533 can_be_returned
= !(af
& EAF_NOT_RETURNED_DIRECTLY
);
1536 can_be_returned
= false;
1537 ret
|= build_access_from_call_arg (gimple_call_arg (call
,
1539 stmt
, can_be_returned
,
1542 if (gimple_call_chain(stmt
))
1543 ret
|= build_access_from_call_arg (gimple_call_chain(call
),
1544 stmt
, false, &oe_check
);
1547 t
= gimple_call_lhs (stmt
);
1548 if (t
&& !disqualify_if_bad_bb_terminating_stmt (stmt
, t
, NULL
))
1550 /* If the STMT is a call to DEFERRED_INIT, avoid setting
1551 cannot_scalarize_away_bitmap. */
1552 if (gimple_call_internal_p (stmt
, IFN_DEFERRED_INIT
))
1553 ret
|= !!build_access_from_expr_1 (t
, stmt
, true);
1555 ret
|= build_access_from_expr (t
, stmt
, true);
1561 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1562 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
1564 t
= TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
1565 ret
|= build_access_from_expr (t
, asm_stmt
, false);
1567 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
1569 t
= TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
1570 ret
|= build_access_from_expr (t
, asm_stmt
, true);
1584 /* Helper of QSORT function. There are pointers to accesses in the array. An
1585 access is considered smaller than another if it has smaller offset or if the
1586 offsets are the same but is size is bigger. */
1589 compare_access_positions (const void *a
, const void *b
)
1591 const access_p
*fp1
= (const access_p
*) a
;
1592 const access_p
*fp2
= (const access_p
*) b
;
1593 const access_p f1
= *fp1
;
1594 const access_p f2
= *fp2
;
1596 if (f1
->offset
!= f2
->offset
)
1597 return f1
->offset
< f2
->offset
? -1 : 1;
1599 if (f1
->size
== f2
->size
)
1601 if (f1
->type
== f2
->type
)
1603 /* Put any non-aggregate type before any aggregate type. */
1604 else if (!is_gimple_reg_type (f1
->type
)
1605 && is_gimple_reg_type (f2
->type
))
1607 else if (is_gimple_reg_type (f1
->type
)
1608 && !is_gimple_reg_type (f2
->type
))
1610 /* Put any complex or vector type before any other scalar type. */
1611 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1612 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1613 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1614 || VECTOR_TYPE_P (f2
->type
)))
1616 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1617 || VECTOR_TYPE_P (f1
->type
))
1618 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1619 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1621 /* Put any integral type before any non-integral type. When splicing, we
1622 make sure that those with insufficient precision and occupying the
1623 same space are not scalarized. */
1624 else if (INTEGRAL_TYPE_P (f1
->type
)
1625 && !INTEGRAL_TYPE_P (f2
->type
))
1627 else if (!INTEGRAL_TYPE_P (f1
->type
)
1628 && INTEGRAL_TYPE_P (f2
->type
))
1630 /* Put the integral type with the bigger precision first. */
1631 else if (INTEGRAL_TYPE_P (f1
->type
)
1632 && INTEGRAL_TYPE_P (f2
->type
)
1633 && (TYPE_PRECISION (f2
->type
) != TYPE_PRECISION (f1
->type
)))
1634 return TYPE_PRECISION (f2
->type
) - TYPE_PRECISION (f1
->type
);
1635 /* Stabilize the sort. */
1636 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1639 /* We want the bigger accesses first, thus the opposite operator in the next
1641 return f1
->size
> f2
->size
? -1 : 1;
1645 /* Append a name of the declaration to the name obstack. A helper function for
1649 make_fancy_decl_name (tree decl
)
1653 tree name
= DECL_NAME (decl
);
1655 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1656 IDENTIFIER_LENGTH (name
));
1659 sprintf (buffer
, "D%u", DECL_UID (decl
));
1660 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1664 /* Helper for make_fancy_name. */
1667 make_fancy_name_1 (tree expr
)
1674 make_fancy_decl_name (expr
);
1678 switch (TREE_CODE (expr
))
1681 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1682 obstack_1grow (&name_obstack
, '$');
1683 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1687 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1688 obstack_1grow (&name_obstack
, '$');
1689 /* Arrays with only one element may not have a constant as their
1691 index
= TREE_OPERAND (expr
, 1);
1692 if (TREE_CODE (index
) != INTEGER_CST
)
1694 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1695 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1700 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1704 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1705 if (!integer_zerop (TREE_OPERAND (expr
, 1)))
1707 obstack_1grow (&name_obstack
, '$');
1708 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
,
1709 TREE_INT_CST_LOW (TREE_OPERAND (expr
, 1)));
1710 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1716 gcc_unreachable (); /* we treat these as scalars. */
1723 /* Create a human readable name for replacement variable of ACCESS. */
1726 make_fancy_name (tree expr
)
1728 make_fancy_name_1 (expr
);
1729 obstack_1grow (&name_obstack
, '\0');
1730 return XOBFINISH (&name_obstack
, char *);
1733 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1734 EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1735 something for which get_addr_base_and_unit_offset returns NULL, gsi must
1736 be non-NULL and is used to insert new statements either before or below
1737 the current one as specified by INSERT_AFTER. This function is not capable
1738 of handling bitfields. */
1741 build_ref_for_offset (location_t loc
, tree base
, poly_int64 offset
,
1742 bool reverse
, tree exp_type
, gimple_stmt_iterator
*gsi
,
1745 tree prev_base
= base
;
1748 poly_int64 base_offset
;
1749 unsigned HOST_WIDE_INT misalign
;
1752 /* Preserve address-space information. */
1753 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (base
));
1754 if (as
!= TYPE_ADDR_SPACE (exp_type
))
1755 exp_type
= build_qualified_type (exp_type
,
1756 TYPE_QUALS (exp_type
)
1757 | ENCODE_QUAL_ADDR_SPACE (as
));
1759 poly_int64 byte_offset
= exact_div (offset
, BITS_PER_UNIT
);
1760 get_object_alignment_1 (base
, &align
, &misalign
);
1761 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1763 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1764 offset such as array[var_index]. */
1770 gcc_checking_assert (gsi
);
1771 tmp
= make_ssa_name (build_pointer_type (TREE_TYPE (prev_base
)));
1772 addr
= build_fold_addr_expr (unshare_expr (prev_base
));
1773 STRIP_USELESS_TYPE_CONVERSION (addr
);
1774 stmt
= gimple_build_assign (tmp
, addr
);
1775 gimple_set_location (stmt
, loc
);
1777 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
1779 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1781 off
= build_int_cst (reference_alias_ptr_type (prev_base
), byte_offset
);
1784 else if (TREE_CODE (base
) == MEM_REF
)
1786 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1787 base_offset
+ byte_offset
);
1788 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1789 base
= unshare_expr (TREE_OPERAND (base
, 0));
1793 off
= build_int_cst (reference_alias_ptr_type (prev_base
),
1794 base_offset
+ byte_offset
);
1795 base
= build_fold_addr_expr (unshare_expr (base
));
1798 unsigned int align_bound
= known_alignment (misalign
+ offset
);
1799 if (align_bound
!= 0)
1800 align
= MIN (align
, align_bound
);
1801 if (align
!= TYPE_ALIGN (exp_type
))
1802 exp_type
= build_aligned_type (exp_type
, align
);
1804 mem_ref
= fold_build2_loc (loc
, MEM_REF
, exp_type
, base
, off
);
1805 REF_REVERSE_STORAGE_ORDER (mem_ref
) = reverse
;
1806 if (TREE_THIS_VOLATILE (prev_base
))
1807 TREE_THIS_VOLATILE (mem_ref
) = 1;
1808 if (TREE_SIDE_EFFECTS (prev_base
))
1809 TREE_SIDE_EFFECTS (mem_ref
) = 1;
1813 /* Construct and return a memory reference that is equal to a portion of
1814 MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1817 build_reconstructed_reference (location_t
, tree base
, struct access
*model
)
1819 tree expr
= model
->expr
;
1820 /* We have to make sure to start just below the outermost union. */
1821 tree start_expr
= expr
;
1822 while (handled_component_p (expr
))
1824 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr
, 0))) == UNION_TYPE
)
1826 expr
= TREE_OPERAND (expr
, 0);
1830 tree prev_expr
= NULL_TREE
;
1831 while (!types_compatible_p (TREE_TYPE (expr
), TREE_TYPE (base
)))
1833 if (!handled_component_p (expr
))
1836 expr
= TREE_OPERAND (expr
, 0);
1839 /* Guard against broken VIEW_CONVERT_EXPRs... */
1843 TREE_OPERAND (prev_expr
, 0) = base
;
1844 tree ref
= unshare_expr (model
->expr
);
1845 TREE_OPERAND (prev_expr
, 0) = expr
;
1849 /* Construct a memory reference to a part of an aggregate BASE at the given
1850 OFFSET and of the same type as MODEL. In case this is a reference to a
1851 bit-field, the function will replicate the last component_ref of model's
1852 expr to access it. INSERT_AFTER and GSI have the same meaning as in
1853 build_ref_for_offset, furthermore, when GSI is NULL, the function expects
1854 that it re-builds the entire reference from a DECL to the final access and
1855 so will create a MEM_REF when OFFSET does not exactly match offset of
1859 build_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1860 struct access
*model
, gimple_stmt_iterator
*gsi
,
1863 gcc_assert (offset
>= 0);
1864 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1865 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1867 /* This access represents a bit-field. */
1868 tree t
, exp_type
, fld
= TREE_OPERAND (model
->expr
, 1);
1870 offset
-= int_bit_position (fld
);
1871 exp_type
= TREE_TYPE (TREE_OPERAND (model
->expr
, 0));
1872 t
= build_ref_for_offset (loc
, base
, offset
, model
->reverse
, exp_type
,
1874 /* The flag will be set on the record type. */
1875 REF_REVERSE_STORAGE_ORDER (t
) = 0;
1876 return fold_build3_loc (loc
, COMPONENT_REF
, TREE_TYPE (fld
), t
, fld
,
1882 if (model
->grp_same_access_path
1883 && !TREE_THIS_VOLATILE (base
)
1884 && (TYPE_ADDR_SPACE (TREE_TYPE (base
))
1885 == TYPE_ADDR_SPACE (TREE_TYPE (model
->expr
)))
1886 && (offset
== model
->offset
1887 || (gsi
&& offset
<= model
->offset
))
1888 /* build_reconstructed_reference can still fail if we have already
1889 massaged BASE because of another type incompatibility. */
1890 && (res
= build_reconstructed_reference (loc
, base
, model
)))
1893 return build_ref_for_offset (loc
, base
, offset
, model
->reverse
,
1894 model
->type
, gsi
, insert_after
);
1898 /* Attempt to build a memory reference that we could but into a gimple
1899 debug_bind statement. Similar to build_ref_for_model but punts if it has to
1900 create statements and return s NULL instead. This function also ignores
1901 alignment issues and so its results should never end up in non-debug
1905 build_debug_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1906 struct access
*model
)
1908 poly_int64 base_offset
;
1911 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1912 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1915 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1918 if (TREE_CODE (base
) == MEM_REF
)
1920 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1921 base_offset
+ offset
/ BITS_PER_UNIT
);
1922 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1923 base
= unshare_expr (TREE_OPERAND (base
, 0));
1927 off
= build_int_cst (reference_alias_ptr_type (base
),
1928 base_offset
+ offset
/ BITS_PER_UNIT
);
1929 base
= build_fold_addr_expr (unshare_expr (base
));
1932 return fold_build2_loc (loc
, MEM_REF
, model
->type
, base
, off
);
1935 /* Construct a memory reference consisting of component_refs and array_refs to
1936 a part of an aggregate *RES (which is of type TYPE). The requested part
1937 should have type EXP_TYPE at be the given OFFSET. This function might not
1938 succeed, it returns true when it does and only then *RES points to something
1939 meaningful. This function should be used only to build expressions that we
1940 might need to present to user (e.g. in warnings). In all other situations,
1941 build_ref_for_model or build_ref_for_offset should be used instead. */
1944 build_user_friendly_ref_for_offset (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1950 tree tr_size
, index
, minidx
;
1951 HOST_WIDE_INT el_size
;
1953 if (offset
== 0 && exp_type
1954 && types_compatible_p (exp_type
, type
))
1957 switch (TREE_CODE (type
))
1960 case QUAL_UNION_TYPE
:
1962 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1964 HOST_WIDE_INT pos
, size
;
1965 tree tr_pos
, expr
, *expr_ptr
;
1967 if (TREE_CODE (fld
) != FIELD_DECL
)
1970 tr_pos
= bit_position (fld
);
1971 if (!tr_pos
|| !tree_fits_uhwi_p (tr_pos
))
1973 pos
= tree_to_uhwi (tr_pos
);
1974 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1975 tr_size
= DECL_SIZE (fld
);
1976 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1978 size
= tree_to_uhwi (tr_size
);
1984 else if (pos
> offset
|| (pos
+ size
) <= offset
)
1987 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1990 if (build_user_friendly_ref_for_offset (expr_ptr
, TREE_TYPE (fld
),
1991 offset
- pos
, exp_type
))
2000 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
2001 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
2003 el_size
= tree_to_uhwi (tr_size
);
2005 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
2006 if (TREE_CODE (minidx
) != INTEGER_CST
|| el_size
== 0)
2008 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
2009 if (!integer_zerop (minidx
))
2010 index
= int_const_binop (PLUS_EXPR
, index
, minidx
);
2011 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
2012 NULL_TREE
, NULL_TREE
);
2013 offset
= offset
% el_size
;
2014 type
= TREE_TYPE (type
);
2029 /* Print message to dump file why a variable was rejected. */
2032 reject (tree var
, const char *msg
)
2034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2036 fprintf (dump_file
, "Rejected (%d): %s: ", DECL_UID (var
), msg
);
2037 print_generic_expr (dump_file
, var
);
2038 fprintf (dump_file
, "\n");
2042 /* Return true if VAR is a candidate for SRA. */
2045 maybe_add_sra_candidate (tree var
)
2047 tree type
= TREE_TYPE (var
);
2051 if (!AGGREGATE_TYPE_P (type
))
2053 reject (var
, "not aggregate");
2057 if ((is_global_var (var
)
2058 /* There are cases where non-addressable variables fail the
2059 pt_solutions_check test, e.g in gcc.dg/uninit-40.c. */
2060 || (TREE_ADDRESSABLE (var
)
2061 && pt_solution_includes (&cfun
->gimple_df
->escaped_return
, var
))
2062 || (TREE_CODE (var
) == RESULT_DECL
2063 && !DECL_BY_REFERENCE (var
)
2064 && aggregate_value_p (var
, current_function_decl
)))
2065 /* Allow constant-pool entries that "need to live in memory". */
2066 && !constant_decl_p (var
))
2068 reject (var
, "needs to live in memory and escapes or global");
2071 if (TREE_THIS_VOLATILE (var
))
2073 reject (var
, "is volatile");
2076 if (!COMPLETE_TYPE_P (type
))
2078 reject (var
, "has incomplete type");
2081 if (!tree_fits_shwi_p (TYPE_SIZE (type
)))
2083 reject (var
, "type size not fixed");
2086 if (tree_to_shwi (TYPE_SIZE (type
)) == 0)
2088 reject (var
, "type size is zero");
2091 if (type_internals_preclude_sra_p (type
, &msg
))
2096 if (/* Fix for PR 41089. tree-stdarg.cc needs to have va_lists intact but
2097 we also want to schedule it rather late. Thus we ignore it in
2099 (sra_mode
== SRA_MODE_EARLY_INTRA
2100 && is_va_list_type (type
)))
2102 reject (var
, "is va_list");
2106 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
2107 slot
= candidates
->find_slot_with_hash (var
, DECL_UID (var
), INSERT
);
2110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2112 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
2113 print_generic_expr (dump_file
, var
);
2114 fprintf (dump_file
, "\n");
2120 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
2121 those with type which is suitable for scalarization. */
2124 find_var_candidates (void)
2130 for (parm
= DECL_ARGUMENTS (current_function_decl
);
2132 parm
= DECL_CHAIN (parm
))
2133 ret
|= maybe_add_sra_candidate (parm
);
2135 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
2140 ret
|= maybe_add_sra_candidate (var
);
2146 /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
2147 ending either with a DECL or a MEM_REF with zero offset. */
2150 path_comparable_for_same_access (tree expr
)
2152 while (handled_component_p (expr
))
2154 if (TREE_CODE (expr
) == ARRAY_REF
)
2156 /* SSA name indices can occur here too when the array is of sie one.
2157 But we cannot just re-use array_refs with SSA names elsewhere in
2158 the function, so disallow non-constant indices. TODO: Remove this
2159 limitation after teaching build_reconstructed_reference to replace
2160 the index with the index type lower bound. */
2161 if (TREE_CODE (TREE_OPERAND (expr
, 1)) != INTEGER_CST
)
2164 expr
= TREE_OPERAND (expr
, 0);
2167 if (TREE_CODE (expr
) == MEM_REF
)
2169 if (!zerop (TREE_OPERAND (expr
, 1)))
2173 gcc_assert (DECL_P (expr
));
2178 /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
2179 true if the chain of these handled components are exactly the same as EXP2
2180 and the expression under them is the same DECL or an equivalent MEM_REF.
2181 The reference picked by compare_access_positions must go to EXP1. */
2184 same_access_path_p (tree exp1
, tree exp2
)
2186 if (TREE_CODE (exp1
) != TREE_CODE (exp2
))
2188 /* Special case single-field structures loaded sometimes as the field
2189 and sometimes as the structure. If the field is of a scalar type,
2190 compare_access_positions will put it into exp1.
2192 TODO: The gimple register type condition can be removed if teach
2193 compare_access_positions to put inner types first. */
2194 if (is_gimple_reg_type (TREE_TYPE (exp1
))
2195 && TREE_CODE (exp1
) == COMPONENT_REF
2196 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1
, 0)))
2197 == TYPE_MAIN_VARIANT (TREE_TYPE (exp2
))))
2198 exp1
= TREE_OPERAND (exp1
, 0);
2203 if (!operand_equal_p (exp1
, exp2
, OEP_ADDRESS_OF
))
2209 /* Sort all accesses for the given variable, check for partial overlaps and
2210 return NULL if there are any. If there are none, pick a representative for
2211 each combination of offset and size and create a linked list out of them.
2212 Return the pointer to the first representative and make sure it is the first
2213 one in the vector of accesses. */
2215 static struct access
*
2216 sort_and_splice_var_accesses (tree var
)
2218 int i
, j
, access_count
;
2219 struct access
*res
, **prev_acc_ptr
= &res
;
2220 vec
<access_p
> *access_vec
;
2222 HOST_WIDE_INT low
= -1, high
= 0;
2224 access_vec
= get_base_access_vector (var
);
2227 access_count
= access_vec
->length ();
2229 /* Sort by <OFFSET, SIZE>. */
2230 access_vec
->qsort (compare_access_positions
);
2233 while (i
< access_count
)
2235 struct access
*access
= (*access_vec
)[i
];
2236 bool grp_write
= access
->write
;
2237 bool grp_read
= !access
->write
;
2238 bool grp_scalar_write
= access
->write
2239 && is_gimple_reg_type (access
->type
);
2240 bool grp_scalar_read
= !access
->write
2241 && is_gimple_reg_type (access
->type
);
2242 bool grp_assignment_read
= access
->grp_assignment_read
;
2243 bool grp_assignment_write
= access
->grp_assignment_write
;
2244 bool multiple_scalar_reads
= false;
2245 bool grp_partial_lhs
= access
->grp_partial_lhs
;
2246 bool first_scalar
= is_gimple_reg_type (access
->type
);
2247 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
2248 bool grp_same_access_path
= true;
2249 bool bf_non_full_precision
2250 = (INTEGRAL_TYPE_P (access
->type
)
2251 && TYPE_PRECISION (access
->type
) != access
->size
2252 && TREE_CODE (access
->expr
) == COMPONENT_REF
2253 && DECL_BIT_FIELD (TREE_OPERAND (access
->expr
, 1)));
2255 if (first
|| access
->offset
>= high
)
2258 low
= access
->offset
;
2259 high
= access
->offset
+ access
->size
;
2261 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
2264 gcc_assert (access
->offset
>= low
2265 && access
->offset
+ access
->size
<= high
);
2267 if (INTEGRAL_TYPE_P (access
->type
)
2268 && TYPE_PRECISION (access
->type
) != access
->size
2269 && bitmap_bit_p (passed_by_ref_in_call
, DECL_UID (access
->base
)))
2271 /* This can lead to performance regressions because we can generate
2272 excessive zero extensions. */
2273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2275 fprintf (dump_file
, "Won't scalarize ");
2276 print_generic_expr (dump_file
, access
->base
);
2277 fprintf (dump_file
, "(%d), it is passed by reference to a call "
2278 "and there are accesses with precision not covering "
2279 "their type size.", DECL_UID (access
->base
));
2284 grp_same_access_path
= path_comparable_for_same_access (access
->expr
);
2287 while (j
< access_count
)
2289 struct access
*ac2
= (*access_vec
)[j
];
2290 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
2295 grp_scalar_write
= (grp_scalar_write
2296 || is_gimple_reg_type (ac2
->type
));
2301 if (is_gimple_reg_type (ac2
->type
))
2303 if (grp_scalar_read
)
2304 multiple_scalar_reads
= true;
2306 grp_scalar_read
= true;
2309 grp_assignment_read
|= ac2
->grp_assignment_read
;
2310 grp_assignment_write
|= ac2
->grp_assignment_write
;
2311 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
2312 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
2313 relink_to_new_repr (access
, ac2
);
2315 /* If there are both aggregate-type and scalar-type accesses with
2316 this combination of size and offset, the comparison function
2317 should have put the scalars first. */
2318 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
2319 /* It also prefers integral types to non-integral. However, when the
2320 precision of the selected type does not span the entire area and
2321 should also be used for a non-integer (i.e. float), we must not
2322 let that happen. Normally analyze_access_subtree expands the type
2323 to cover the entire area but for bit-fields it doesn't. */
2324 if (bf_non_full_precision
&& !INTEGRAL_TYPE_P (ac2
->type
))
2326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 fprintf (dump_file
, "Cannot scalarize the following access "
2329 "because insufficient precision integer type was "
2331 dump_access (dump_file
, access
, false);
2333 unscalarizable_region
= true;
2336 if (grp_same_access_path
2337 && !same_access_path_p (access
->expr
, ac2
->expr
))
2338 grp_same_access_path
= false;
2340 ac2
->group_representative
= access
;
2346 access
->group_representative
= access
;
2347 access
->grp_write
= grp_write
;
2348 access
->grp_read
= grp_read
;
2349 access
->grp_scalar_read
= grp_scalar_read
;
2350 access
->grp_scalar_write
= grp_scalar_write
;
2351 access
->grp_assignment_read
= grp_assignment_read
;
2352 access
->grp_assignment_write
= grp_assignment_write
;
2353 access
->grp_hint
= multiple_scalar_reads
&& !constant_decl_p (var
);
2354 access
->grp_partial_lhs
= grp_partial_lhs
;
2355 access
->grp_unscalarizable_region
= unscalarizable_region
;
2356 access
->grp_same_access_path
= grp_same_access_path
;
2358 *prev_acc_ptr
= access
;
2359 prev_acc_ptr
= &access
->next_grp
;
2362 gcc_assert (res
== (*access_vec
)[0]);
2366 /* Create a variable for the given ACCESS which determines the type, name and a
2367 few other properties. Return the variable declaration and store it also to
2368 ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2369 default-definition SSA name on in order to facilitate an uninitialized
2370 warning. It is used instead of the actual ACCESS type if that is not of a
2371 gimple register type. */
2374 create_access_replacement (struct access
*access
, tree reg_type
= NULL_TREE
)
2378 tree type
= access
->type
;
2379 if (reg_type
&& !is_gimple_reg_type (type
))
2382 if (access
->grp_to_be_debug_replaced
)
2384 repl
= create_tmp_var_raw (access
->type
);
2385 DECL_CONTEXT (repl
) = current_function_decl
;
2388 /* Drop any special alignment on the type if it's not on the main
2389 variant. This avoids issues with weirdo ABIs like AAPCS. */
2390 repl
= create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type
),
2391 TYPE_QUALS (type
)), "SR");
2392 if (access
->grp_partial_lhs
2393 && is_gimple_reg_type (type
))
2394 DECL_NOT_GIMPLE_REG_P (repl
) = 1;
2396 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
2397 DECL_ARTIFICIAL (repl
) = 1;
2398 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
2400 if (DECL_NAME (access
->base
)
2401 && !DECL_IGNORED_P (access
->base
)
2402 && !DECL_ARTIFICIAL (access
->base
))
2404 char *pretty_name
= make_fancy_name (access
->expr
);
2405 tree debug_expr
= unshare_expr_without_location (access
->expr
), d
;
2408 DECL_NAME (repl
) = get_identifier (pretty_name
);
2409 DECL_NAMELESS (repl
) = 1;
2410 obstack_free (&name_obstack
, pretty_name
);
2412 /* Get rid of any SSA_NAMEs embedded in debug_expr,
2413 as DECL_DEBUG_EXPR isn't considered when looking for still
2414 used SSA_NAMEs and thus they could be freed. All debug info
2415 generation cares is whether something is constant or variable
2416 and that get_ref_base_and_extent works properly on the
2417 expression. It cannot handle accesses at a non-constant offset
2418 though, so just give up in those cases. */
2419 for (d
= debug_expr
;
2420 !fail
&& (handled_component_p (d
) || TREE_CODE (d
) == MEM_REF
);
2421 d
= TREE_OPERAND (d
, 0))
2422 switch (TREE_CODE (d
))
2425 case ARRAY_RANGE_REF
:
2426 if (TREE_OPERAND (d
, 1)
2427 && TREE_CODE (TREE_OPERAND (d
, 1)) != INTEGER_CST
)
2429 if (TREE_OPERAND (d
, 3)
2430 && TREE_CODE (TREE_OPERAND (d
, 3)) != INTEGER_CST
)
2434 if (TREE_OPERAND (d
, 2)
2435 && TREE_CODE (TREE_OPERAND (d
, 2)) != INTEGER_CST
)
2439 if (TREE_CODE (TREE_OPERAND (d
, 0)) != ADDR_EXPR
)
2442 d
= TREE_OPERAND (d
, 0);
2449 SET_DECL_DEBUG_EXPR (repl
, debug_expr
);
2450 DECL_HAS_DEBUG_EXPR_P (repl
) = 1;
2452 if (access
->grp_no_warning
)
2453 suppress_warning (repl
/* Be more selective! */);
2455 copy_warning (repl
, access
->base
);
2458 suppress_warning (repl
/* Be more selective! */);
2462 if (access
->grp_to_be_debug_replaced
)
2464 fprintf (dump_file
, "Created a debug-only replacement for ");
2465 print_generic_expr (dump_file
, access
->base
);
2466 fprintf (dump_file
, " offset: %u, size: %u\n",
2467 (unsigned) access
->offset
, (unsigned) access
->size
);
2471 fprintf (dump_file
, "Created a replacement for ");
2472 print_generic_expr (dump_file
, access
->base
);
2473 fprintf (dump_file
, " offset: %u, size: %u: ",
2474 (unsigned) access
->offset
, (unsigned) access
->size
);
2475 print_generic_expr (dump_file
, repl
, TDF_UID
);
2476 fprintf (dump_file
, "\n");
2479 sra_stats
.replacements
++;
2484 /* Return ACCESS scalar replacement, which must exist. */
2487 get_access_replacement (struct access
*access
)
2489 gcc_checking_assert (access
->replacement_decl
);
2490 return access
->replacement_decl
;
2494 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2495 linked list along the way. Stop when *ACCESS is NULL or the access pointed
2496 to it is not "within" the root. Return false iff some accesses partially
2500 build_access_subtree (struct access
**access
)
2502 struct access
*root
= *access
, *last_child
= NULL
;
2503 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2505 *access
= (*access
)->next_grp
;
2506 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
2509 root
->first_child
= *access
;
2511 last_child
->next_sibling
= *access
;
2512 last_child
= *access
;
2513 (*access
)->parent
= root
;
2514 (*access
)->grp_write
|= root
->grp_write
;
2516 if (!build_access_subtree (access
))
2520 if (*access
&& (*access
)->offset
< limit
)
2526 /* Build a tree of access representatives, ACCESS is the pointer to the first
2527 one, others are linked in a list by the next_grp field. Return false iff
2528 some accesses partially overlap. */
2531 build_access_trees (struct access
*access
)
2535 struct access
*root
= access
;
2537 if (!build_access_subtree (&access
))
2539 root
->next_grp
= access
;
2544 /* Traverse the access forest where ROOT is the first root and verify that
2545 various important invariants hold true. */
2548 verify_sra_access_forest (struct access
*root
)
2550 struct access
*access
= root
;
2551 tree first_base
= root
->base
;
2552 gcc_assert (DECL_P (first_base
));
2555 gcc_assert (access
->base
== first_base
);
2557 gcc_assert (access
->offset
>= access
->parent
->offset
2558 && access
->size
<= access
->parent
->size
);
2559 if (access
->next_sibling
)
2560 gcc_assert (access
->next_sibling
->offset
2561 >= access
->offset
+ access
->size
);
2563 poly_int64 poffset
, psize
, pmax_size
;
2565 tree base
= get_ref_base_and_extent (access
->expr
, &poffset
, &psize
,
2566 &pmax_size
, &reverse
);
2567 HOST_WIDE_INT offset
, size
, max_size
;
2568 if (!poffset
.is_constant (&offset
)
2569 || !psize
.is_constant (&size
)
2570 || !pmax_size
.is_constant (&max_size
))
2572 gcc_assert (base
== first_base
);
2573 gcc_assert (offset
== access
->offset
);
2574 gcc_assert (access
->grp_unscalarizable_region
2575 || access
->grp_total_scalarization
2576 || size
== max_size
);
2577 gcc_assert (access
->grp_unscalarizable_region
2578 || !is_gimple_reg_type (access
->type
)
2579 || size
== access
->size
);
2580 gcc_assert (reverse
== access
->reverse
);
2582 if (access
->first_child
)
2584 gcc_assert (access
->first_child
->parent
== access
);
2585 access
= access
->first_child
;
2587 else if (access
->next_sibling
)
2589 gcc_assert (access
->next_sibling
->parent
== access
->parent
);
2590 access
= access
->next_sibling
;
2594 while (access
->parent
&& !access
->next_sibling
)
2595 access
= access
->parent
;
2596 if (access
->next_sibling
)
2597 access
= access
->next_sibling
;
2600 gcc_assert (access
== root
);
2601 root
= root
->next_grp
;
2609 /* Verify access forests of all candidates with accesses by calling
2610 verify_access_forest on each on them. */
2613 verify_all_sra_access_forests (void)
2617 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
2619 tree var
= candidate (i
);
2620 struct access
*access
= get_first_repr_for_decl (var
);
2623 gcc_assert (access
->base
== var
);
2624 verify_sra_access_forest (access
);
2629 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2633 expr_with_var_bounded_array_refs_p (tree expr
)
2635 while (handled_component_p (expr
))
2637 if (TREE_CODE (expr
) == ARRAY_REF
2638 && !tree_fits_shwi_p (array_ref_low_bound (expr
)))
2640 expr
= TREE_OPERAND (expr
, 0);
2645 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2646 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2647 is set, we are totally scalarizing the aggregate. Also set all sorts of
2648 access flags appropriately along the way, notably always set grp_read and
2649 grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2652 Creating a replacement for a scalar access is considered beneficial if its
2653 grp_hint ot TOTALLY is set (this means either that there is more than one
2654 direct read access or that we are attempting total scalarization) or
2655 according to the following table:
2657 Access written to through a scalar type (once or more times)
2659 | Written to in an assignment statement
2661 | | Access read as scalar _once_
2663 | | | Read in an assignment statement
2665 | | | | Scalarize Comment
2666 -----------------------------------------------------------------------------
2667 0 0 0 0 No access for the scalar
2668 0 0 0 1 No access for the scalar
2669 0 0 1 0 No Single read - won't help
2670 0 0 1 1 No The same case
2671 0 1 0 0 No access for the scalar
2672 0 1 0 1 No access for the scalar
2673 0 1 1 0 Yes s = *g; return s.i;
2674 0 1 1 1 Yes The same case as above
2675 1 0 0 0 No Won't help
2676 1 0 0 1 Yes s.i = 1; *g = s;
2677 1 0 1 0 Yes s.i = 5; g = s.i;
2678 1 0 1 1 Yes The same case as above
2679 1 1 0 0 No Won't help.
2680 1 1 0 1 Yes s.i = 1; *g = s;
2681 1 1 1 0 Yes s = *g; return s.i;
2682 1 1 1 1 Yes Any of the above yeses */
2685 analyze_access_subtree (struct access
*root
, struct access
*parent
,
2686 bool allow_replacements
, bool totally
)
2688 struct access
*child
;
2689 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2690 HOST_WIDE_INT covered_to
= root
->offset
;
2691 bool scalar
= is_gimple_reg_type (root
->type
);
2692 bool hole
= false, sth_created
= false;
2696 if (parent
->grp_read
)
2698 if (parent
->grp_assignment_read
)
2699 root
->grp_assignment_read
= 1;
2700 if (parent
->grp_write
)
2701 root
->grp_write
= 1;
2702 if (parent
->grp_assignment_write
)
2703 root
->grp_assignment_write
= 1;
2704 if (!parent
->grp_same_access_path
)
2705 root
->grp_same_access_path
= 0;
2708 if (root
->grp_unscalarizable_region
)
2709 allow_replacements
= false;
2711 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
2712 allow_replacements
= false;
2714 if (!totally
&& root
->grp_result_of_prop_from_lhs
)
2715 allow_replacements
= false;
2717 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
2719 hole
|= covered_to
< child
->offset
;
2720 sth_created
|= analyze_access_subtree (child
, root
,
2721 allow_replacements
&& !scalar
,
2724 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
2725 if (child
->grp_covered
)
2726 covered_to
+= child
->size
;
2731 if (allow_replacements
&& scalar
&& !root
->first_child
2732 && (totally
|| !root
->grp_total_scalarization
)
2735 || ((root
->grp_scalar_read
|| root
->grp_assignment_read
)
2736 && (root
->grp_scalar_write
|| root
->grp_assignment_write
))))
2738 /* Always create access replacements that cover the whole access.
2739 For integral types this means the precision has to match.
2740 Avoid assumptions based on the integral type kind, too. */
2741 if (INTEGRAL_TYPE_P (root
->type
)
2742 && ((TREE_CODE (root
->type
) != INTEGER_TYPE
2743 && TREE_CODE (root
->type
) != BITINT_TYPE
)
2744 || TYPE_PRECISION (root
->type
) != root
->size
)
2745 /* But leave bitfield accesses alone. */
2746 && (TREE_CODE (root
->expr
) != COMPONENT_REF
2747 || !DECL_BIT_FIELD (TREE_OPERAND (root
->expr
, 1))))
2749 tree rt
= root
->type
;
2750 gcc_assert ((root
->offset
% BITS_PER_UNIT
) == 0
2751 && (root
->size
% BITS_PER_UNIT
) == 0);
2752 if (TREE_CODE (root
->type
) == BITINT_TYPE
)
2753 root
->type
= build_bitint_type (root
->size
, TYPE_UNSIGNED (rt
));
2755 root
->type
= build_nonstandard_integer_type (root
->size
,
2756 TYPE_UNSIGNED (rt
));
2757 root
->expr
= build_ref_for_offset (UNKNOWN_LOCATION
, root
->base
,
2758 root
->offset
, root
->reverse
,
2759 root
->type
, NULL
, false);
2761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2763 fprintf (dump_file
, "Changing the type of a replacement for ");
2764 print_generic_expr (dump_file
, root
->base
);
2765 fprintf (dump_file
, " offset: %u, size: %u ",
2766 (unsigned) root
->offset
, (unsigned) root
->size
);
2767 fprintf (dump_file
, " to an integer.\n");
2771 root
->grp_to_be_replaced
= 1;
2772 root
->replacement_decl
= create_access_replacement (root
);
2778 if (allow_replacements
2779 && scalar
&& !root
->first_child
2780 && !root
->grp_total_scalarization
2781 && (root
->grp_scalar_write
|| root
->grp_assignment_write
)
2782 && !bitmap_bit_p (cannot_scalarize_away_bitmap
,
2783 DECL_UID (root
->base
)))
2785 gcc_checking_assert (!root
->grp_scalar_read
2786 && !root
->grp_assignment_read
);
2788 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2790 root
->grp_to_be_debug_replaced
= 1;
2791 root
->replacement_decl
= create_access_replacement (root
);
2795 if (covered_to
< limit
)
2797 if (scalar
|| !allow_replacements
)
2798 root
->grp_total_scalarization
= 0;
2801 if (!hole
|| totally
)
2802 root
->grp_covered
= 1;
2803 else if (root
->grp_write
|| comes_initialized_p (root
->base
))
2804 root
->grp_unscalarized_data
= 1; /* not covered and written to */
2808 /* Analyze all access trees linked by next_grp by the means of
2809 analyze_access_subtree. */
2811 analyze_access_trees (struct access
*access
)
2817 if (analyze_access_subtree (access
, NULL
, true,
2818 access
->grp_total_scalarization
))
2820 access
= access
->next_grp
;
2826 /* Return true iff a potential new child of ACC at offset OFFSET and with size
2827 SIZE would conflict with an already existing one. If exactly such a child
2828 already exists in ACC, store a pointer to it in EXACT_MATCH. */
2831 child_would_conflict_in_acc (struct access
*acc
, HOST_WIDE_INT norm_offset
,
2832 HOST_WIDE_INT size
, struct access
**exact_match
)
2834 struct access
*child
;
2836 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
2838 if (child
->offset
== norm_offset
&& child
->size
== size
)
2840 *exact_match
= child
;
2844 if (child
->offset
< norm_offset
+ size
2845 && child
->offset
+ child
->size
> norm_offset
)
2852 /* Create a new child access of PARENT, with all properties just like MODEL
2853 except for its offset and with its grp_write false and grp_read true.
2854 Return the new access or NULL if it cannot be created. Note that this
2855 access is created long after all splicing and sorting, it's not located in
2856 any access vector and is automatically a representative of its group. Set
2857 the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
2859 static struct access
*
2860 create_artificial_child_access (struct access
*parent
, struct access
*model
,
2861 HOST_WIDE_INT new_offset
,
2862 bool set_grp_read
, bool set_grp_write
)
2864 struct access
**child
;
2865 tree expr
= parent
->base
;
2867 gcc_assert (!model
->grp_unscalarizable_region
);
2869 struct access
*access
= access_pool
.allocate ();
2870 memset (access
, 0, sizeof (struct access
));
2871 if (!build_user_friendly_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
2874 access
->grp_no_warning
= true;
2875 expr
= build_ref_for_model (EXPR_LOCATION (parent
->base
), parent
->base
,
2876 new_offset
, model
, NULL
, false);
2879 access
->base
= parent
->base
;
2880 access
->expr
= expr
;
2881 access
->offset
= new_offset
;
2882 access
->size
= model
->size
;
2883 access
->type
= model
->type
;
2884 access
->parent
= parent
;
2885 access
->grp_read
= set_grp_read
;
2886 access
->grp_write
= set_grp_write
;
2887 access
->reverse
= model
->reverse
;
2889 child
= &parent
->first_child
;
2890 while (*child
&& (*child
)->offset
< new_offset
)
2891 child
= &(*child
)->next_sibling
;
2893 access
->next_sibling
= *child
;
2900 /* Beginning with ACCESS, traverse its whole access subtree and mark all
2901 sub-trees as written to. If any of them has not been marked so previously
2902 and has assignment links leading from it, re-enqueue it. */
2905 subtree_mark_written_and_rhs_enqueue (struct access
*access
)
2907 if (access
->grp_write
)
2909 access
->grp_write
= true;
2910 add_access_to_rhs_work_queue (access
);
2912 struct access
*child
;
2913 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2914 subtree_mark_written_and_rhs_enqueue (child
);
2917 /* If there is still budget to create a propagation access for DECL, return
2918 true and decrement the budget. Otherwise return false. */
2921 budget_for_propagation_access (tree decl
)
2923 unsigned b
, *p
= propagation_budget
->get (decl
);
2927 b
= param_sra_max_propagations
;
2933 if (b
== 0 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2935 fprintf (dump_file
, "The propagation budget of ");
2936 print_generic_expr (dump_file
, decl
);
2937 fprintf (dump_file
, " (UID: %u) has been exhausted.\n", DECL_UID (decl
));
2939 propagation_budget
->put (decl
, b
);
2943 /* Return true if ACC or any of its subaccesses has grp_child set. */
2946 access_or_its_child_written (struct access
*acc
)
2950 for (struct access
*sub
= acc
->first_child
; sub
; sub
= sub
->next_sibling
)
2951 if (access_or_its_child_written (sub
))
2956 /* Propagate subaccesses and grp_write flags of RACC across an assignment link
2957 to LACC. Enqueue sub-accesses as necessary so that the write flag is
2958 propagated transitively. Return true if anything changed. Additionally, if
2959 RACC is a scalar access but LACC is not, change the type of the latter, if
2963 propagate_subaccesses_from_rhs (struct access
*lacc
, struct access
*racc
)
2965 struct access
*rchild
;
2966 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
2969 /* IF the LHS is still not marked as being written to, we only need to do so
2970 if the RHS at this level actually was. */
2971 if (!lacc
->grp_write
)
2973 gcc_checking_assert (!comes_initialized_p (racc
->base
));
2974 if (racc
->grp_write
)
2976 subtree_mark_written_and_rhs_enqueue (lacc
);
2981 if (is_gimple_reg_type (lacc
->type
)
2982 || lacc
->grp_unscalarizable_region
2983 || racc
->grp_unscalarizable_region
)
2985 if (!lacc
->grp_write
)
2988 subtree_mark_written_and_rhs_enqueue (lacc
);
2993 if (is_gimple_reg_type (racc
->type
))
2995 if (!lacc
->grp_write
)
2998 subtree_mark_written_and_rhs_enqueue (lacc
);
3000 if (!lacc
->first_child
&& !racc
->first_child
)
3002 /* We are about to change the access type from aggregate to scalar,
3003 so we need to put the reverse flag onto the access, if any. */
3005 = TYPE_REVERSE_STORAGE_ORDER (lacc
->type
)
3006 && !POINTER_TYPE_P (racc
->type
)
3007 && !VECTOR_TYPE_P (racc
->type
);
3008 tree t
= lacc
->base
;
3010 lacc
->type
= racc
->type
;
3011 if (build_user_friendly_ref_for_offset (&t
, TREE_TYPE (t
),
3012 lacc
->offset
, racc
->type
))
3015 lacc
->grp_same_access_path
= true;
3019 lacc
->expr
= build_ref_for_model (EXPR_LOCATION (lacc
->base
),
3020 lacc
->base
, lacc
->offset
,
3022 if (TREE_CODE (lacc
->expr
) == MEM_REF
)
3023 REF_REVERSE_STORAGE_ORDER (lacc
->expr
) = reverse
;
3024 lacc
->grp_no_warning
= true;
3025 lacc
->grp_same_access_path
= false;
3027 lacc
->reverse
= reverse
;
3032 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
3034 struct access
*new_acc
= NULL
;
3035 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
3037 if (child_would_conflict_in_acc (lacc
, norm_offset
, rchild
->size
,
3042 if (!new_acc
->grp_write
&& rchild
->grp_write
)
3044 gcc_assert (!lacc
->grp_write
);
3045 subtree_mark_written_and_rhs_enqueue (new_acc
);
3049 rchild
->grp_hint
= 1;
3050 new_acc
->grp_hint
|= new_acc
->grp_read
;
3051 if (rchild
->first_child
3052 && propagate_subaccesses_from_rhs (new_acc
, rchild
))
3055 add_access_to_rhs_work_queue (new_acc
);
3060 if (!lacc
->grp_write
)
3063 subtree_mark_written_and_rhs_enqueue (lacc
);
3069 if (rchild
->grp_unscalarizable_region
3070 || !budget_for_propagation_access (lacc
->base
))
3072 if (!lacc
->grp_write
&& access_or_its_child_written (rchild
))
3075 subtree_mark_written_and_rhs_enqueue (lacc
);
3080 rchild
->grp_hint
= 1;
3081 /* Because get_ref_base_and_extent always includes padding in size for
3082 accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3083 type, we might be actually attempting to here to create a child of the
3084 same type as the parent. */
3085 if (!types_compatible_p (lacc
->type
, rchild
->type
))
3086 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
,
3089 || rchild
->grp_write
));
3092 gcc_checking_assert (new_acc
);
3093 if (racc
->first_child
)
3094 propagate_subaccesses_from_rhs (new_acc
, rchild
);
3096 add_access_to_rhs_work_queue (lacc
);
3103 /* Propagate subaccesses of LACC across an assignment link to RACC if they
3104 should inhibit total scalarization of the corresponding area. No flags are
3105 being propagated in the process. Return true if anything changed. */
3108 propagate_subaccesses_from_lhs (struct access
*lacc
, struct access
*racc
)
3110 if (is_gimple_reg_type (racc
->type
)
3111 || lacc
->grp_unscalarizable_region
3112 || racc
->grp_unscalarizable_region
)
3115 /* TODO: Do we want set some new racc flag to stop potential total
3116 scalarization if lacc is a scalar access (and none fo the two have
3120 HOST_WIDE_INT norm_delta
= racc
->offset
- lacc
->offset
;
3121 for (struct access
*lchild
= lacc
->first_child
;
3123 lchild
= lchild
->next_sibling
)
3125 struct access
*matching_acc
= NULL
;
3126 HOST_WIDE_INT norm_offset
= lchild
->offset
+ norm_delta
;
3128 if (lchild
->grp_unscalarizable_region
3129 || child_would_conflict_in_acc (racc
, norm_offset
, lchild
->size
,
3131 || !budget_for_propagation_access (racc
->base
))
3134 && propagate_subaccesses_from_lhs (lchild
, matching_acc
))
3135 add_access_to_lhs_work_queue (matching_acc
);
3139 /* Because get_ref_base_and_extent always includes padding in size for
3140 accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3141 type, we might be actually attempting to here to create a child of the
3142 same type as the parent. */
3143 if (!types_compatible_p (racc
->type
, lchild
->type
))
3145 struct access
*new_acc
3146 = create_artificial_child_access (racc
, lchild
, norm_offset
,
3148 new_acc
->grp_result_of_prop_from_lhs
= 1;
3149 propagate_subaccesses_from_lhs (lchild
, new_acc
);
3152 propagate_subaccesses_from_lhs (lchild
, racc
);
3158 /* Propagate all subaccesses across assignment links. */
3161 propagate_all_subaccesses (void)
3163 propagation_budget
= new hash_map
<tree
, unsigned>;
3164 while (rhs_work_queue_head
)
3166 struct access
*racc
= pop_access_from_rhs_work_queue ();
3167 struct assign_link
*link
;
3169 if (racc
->group_representative
)
3170 racc
= racc
->group_representative
;
3171 gcc_assert (racc
->first_rhs_link
);
3173 for (link
= racc
->first_rhs_link
; link
; link
= link
->next_rhs
)
3175 struct access
*lacc
= link
->lacc
;
3177 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
3179 lacc
= lacc
->group_representative
;
3181 bool reque_parents
= false;
3182 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
3184 if (!lacc
->grp_write
)
3186 subtree_mark_written_and_rhs_enqueue (lacc
);
3187 reque_parents
= true;
3190 else if (propagate_subaccesses_from_rhs (lacc
, racc
))
3191 reque_parents
= true;
3196 add_access_to_rhs_work_queue (lacc
);
3197 lacc
= lacc
->parent
;
3203 while (lhs_work_queue_head
)
3205 struct access
*lacc
= pop_access_from_lhs_work_queue ();
3206 struct assign_link
*link
;
3208 if (lacc
->group_representative
)
3209 lacc
= lacc
->group_representative
;
3210 gcc_assert (lacc
->first_lhs_link
);
3212 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
3215 for (link
= lacc
->first_lhs_link
; link
; link
= link
->next_lhs
)
3217 struct access
*racc
= link
->racc
;
3219 if (racc
->group_representative
)
3220 racc
= racc
->group_representative
;
3221 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
3223 if (propagate_subaccesses_from_lhs (lacc
, racc
))
3224 add_access_to_lhs_work_queue (racc
);
3227 delete propagation_budget
;
3230 /* Return true if the forest beginning with ROOT does not contain
3231 unscalarizable regions or non-byte aligned accesses. */
3234 can_totally_scalarize_forest_p (struct access
*root
)
3236 struct access
*access
= root
;
3239 if (access
->grp_unscalarizable_region
3240 || (access
->offset
% BITS_PER_UNIT
) != 0
3241 || (access
->size
% BITS_PER_UNIT
) != 0
3242 || (is_gimple_reg_type (access
->type
)
3243 && access
->first_child
))
3246 if (access
->first_child
)
3247 access
= access
->first_child
;
3248 else if (access
->next_sibling
)
3249 access
= access
->next_sibling
;
3252 while (access
->parent
&& !access
->next_sibling
)
3253 access
= access
->parent
;
3254 if (access
->next_sibling
)
3255 access
= access
->next_sibling
;
3258 gcc_assert (access
== root
);
3259 root
= root
->next_grp
;
3268 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3269 reference EXPR for total scalarization purposes and mark it as such. Within
3270 the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3272 static struct access
*
3273 create_total_scalarization_access (struct access
*parent
, HOST_WIDE_INT pos
,
3274 HOST_WIDE_INT size
, tree type
, tree expr
,
3275 struct access
**ptr
,
3276 struct access
*next_sibling
)
3278 struct access
*access
= access_pool
.allocate ();
3279 memset (access
, 0, sizeof (struct access
));
3280 access
->base
= parent
->base
;
3281 access
->offset
= pos
;
3282 access
->size
= size
;
3283 access
->expr
= expr
;
3284 access
->type
= type
;
3285 access
->parent
= parent
;
3286 access
->grp_write
= parent
->grp_write
;
3287 access
->grp_total_scalarization
= 1;
3288 access
->grp_hint
= 1;
3289 access
->grp_same_access_path
= path_comparable_for_same_access (expr
);
3290 access
->reverse
= reverse_storage_order_for_component_p (expr
);
3292 access
->next_sibling
= next_sibling
;
3297 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3298 reference EXPR for total scalarization purposes and mark it as such, link it
3299 at *PTR and reshape the tree so that those elements at *PTR and their
3300 siblings which fall within the part described by POS and SIZE are moved to
3301 be children of the new access. If a partial overlap is detected, return
3304 static struct access
*
3305 create_total_access_and_reshape (struct access
*parent
, HOST_WIDE_INT pos
,
3306 HOST_WIDE_INT size
, tree type
, tree expr
,
3307 struct access
**ptr
)
3309 struct access
**p
= ptr
;
3311 while (*p
&& (*p
)->offset
< pos
+ size
)
3313 if ((*p
)->offset
+ (*p
)->size
> pos
+ size
)
3315 p
= &(*p
)->next_sibling
;
3318 struct access
*next_child
= *ptr
;
3319 struct access
*new_acc
3320 = create_total_scalarization_access (parent
, pos
, size
, type
, expr
,
3324 new_acc
->first_child
= next_child
;
3326 for (struct access
*a
= next_child
; a
; a
= a
->next_sibling
)
3327 a
->parent
= new_acc
;
3332 static bool totally_scalarize_subtree (struct access
*root
);
3334 /* Return true if INNER is either the same type as OUTER or if it is the type
3335 of a record field in OUTER at offset zero, possibly in nested
3339 access_and_field_type_match_p (tree outer
, tree inner
)
3341 if (TYPE_MAIN_VARIANT (outer
) == TYPE_MAIN_VARIANT (inner
))
3343 if (TREE_CODE (outer
) != RECORD_TYPE
)
3345 tree fld
= TYPE_FIELDS (outer
);
3348 if (TREE_CODE (fld
) == FIELD_DECL
)
3350 if (!zerop (DECL_FIELD_OFFSET (fld
)))
3352 if (TYPE_MAIN_VARIANT (TREE_TYPE (fld
)) == inner
)
3354 if (TREE_CODE (TREE_TYPE (fld
)) == RECORD_TYPE
)
3355 fld
= TYPE_FIELDS (TREE_TYPE (fld
));
3360 fld
= DECL_CHAIN (fld
);
3365 /* Return type of total_should_skip_creating_access indicating whether a total
3366 scalarization access for a field/element should be created, whether it
3367 already exists or whether the entire total scalarization has to fail. */
3369 enum total_sra_field_state
{TOTAL_FLD_CREATE
, TOTAL_FLD_DONE
, TOTAL_FLD_FAILED
};
3371 /* Do all the necessary steps in total scalarization when the given aggregate
3372 type has a TYPE at POS with the given SIZE should be put into PARENT and
3373 when we have processed all its siblings with smaller offsets up until and
3374 including LAST_SEEN_SIBLING (which can be NULL).
3376 If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3377 appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3378 creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3379 representing the described part of the aggregate for the purposes of total
3380 scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3381 prevents total scalarization from happening at all. */
3383 static enum total_sra_field_state
3384 total_should_skip_creating_access (struct access
*parent
,
3385 struct access
**last_seen_sibling
,
3386 tree type
, HOST_WIDE_INT pos
,
3389 struct access
*next_child
;
3390 if (!*last_seen_sibling
)
3391 next_child
= parent
->first_child
;
3393 next_child
= (*last_seen_sibling
)->next_sibling
;
3395 /* First, traverse the chain of siblings until it points to an access with
3396 offset at least equal to POS. Check all skipped accesses whether they
3397 span the POS boundary and if so, return with a failure. */
3398 while (next_child
&& next_child
->offset
< pos
)
3400 if (next_child
->offset
+ next_child
->size
> pos
)
3401 return TOTAL_FLD_FAILED
;
3402 *last_seen_sibling
= next_child
;
3403 next_child
= next_child
->next_sibling
;
3406 /* Now check whether next_child has exactly the right POS and SIZE and if so,
3407 whether it can represent what we need and can be totally scalarized
3409 if (next_child
&& next_child
->offset
== pos
3410 && next_child
->size
== size
)
3412 if (!is_gimple_reg_type (next_child
->type
)
3413 && (!access_and_field_type_match_p (type
, next_child
->type
)
3414 || !totally_scalarize_subtree (next_child
)))
3415 return TOTAL_FLD_FAILED
;
3417 *last_seen_sibling
= next_child
;
3418 return TOTAL_FLD_DONE
;
3421 /* If the child we're looking at would partially overlap, we just cannot
3422 totally scalarize. */
3424 && next_child
->offset
< pos
+ size
3425 && next_child
->offset
+ next_child
->size
> pos
+ size
)
3426 return TOTAL_FLD_FAILED
;
3428 if (is_gimple_reg_type (type
))
3430 /* We don't scalarize accesses that are children of other scalar type
3431 accesses, so if we go on and create an access for a register type,
3432 there should not be any pre-existing children. There are rare cases
3433 where the requested type is a vector but we already have register
3434 accesses for all its elements which is equally good. Detect that
3435 situation or whether we need to bail out. */
3437 HOST_WIDE_INT covered
= pos
;
3438 bool skipping
= false;
3440 && next_child
->offset
+ next_child
->size
<= pos
+ size
)
3442 if (next_child
->offset
!= covered
3443 || !is_gimple_reg_type (next_child
->type
))
3444 return TOTAL_FLD_FAILED
;
3446 covered
+= next_child
->size
;
3447 *last_seen_sibling
= next_child
;
3448 next_child
= next_child
->next_sibling
;
3454 if (covered
!= pos
+ size
)
3455 return TOTAL_FLD_FAILED
;
3457 return TOTAL_FLD_DONE
;
3461 return TOTAL_FLD_CREATE
;
3464 /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3465 spanning all uncovered areas covered by ROOT, return false if the attempt
3466 failed. All created accesses will have grp_unscalarizable_region set (and
3467 should be ignored if the function returns false). */
3470 totally_scalarize_subtree (struct access
*root
)
3472 gcc_checking_assert (!root
->grp_unscalarizable_region
);
3473 gcc_checking_assert (!is_gimple_reg_type (root
->type
));
3475 struct access
*last_seen_sibling
= NULL
;
3477 switch (TREE_CODE (root
->type
))
3480 for (tree fld
= TYPE_FIELDS (root
->type
); fld
; fld
= DECL_CHAIN (fld
))
3481 if (TREE_CODE (fld
) == FIELD_DECL
)
3483 tree ft
= TREE_TYPE (fld
);
3484 HOST_WIDE_INT fsize
= tree_to_uhwi (DECL_SIZE (fld
));
3488 HOST_WIDE_INT pos
= root
->offset
+ int_bit_position (fld
);
3489 if (pos
+ fsize
> root
->offset
+ root
->size
)
3491 enum total_sra_field_state
3492 state
= total_should_skip_creating_access (root
,
3497 case TOTAL_FLD_FAILED
:
3499 case TOTAL_FLD_DONE
:
3501 case TOTAL_FLD_CREATE
:
3507 struct access
**p
= (last_seen_sibling
3508 ? &last_seen_sibling
->next_sibling
3509 : &root
->first_child
);
3510 tree nref
= build3 (COMPONENT_REF
, ft
, root
->expr
, fld
, NULL_TREE
);
3511 struct access
*new_child
3512 = create_total_access_and_reshape (root
, pos
, fsize
, ft
, nref
, p
);
3516 if (!is_gimple_reg_type (ft
)
3517 && !totally_scalarize_subtree (new_child
))
3519 last_seen_sibling
= new_child
;
3524 tree elemtype
= TREE_TYPE (root
->type
);
3525 tree elem_size
= TYPE_SIZE (elemtype
);
3526 gcc_assert (elem_size
&& tree_fits_shwi_p (elem_size
));
3527 HOST_WIDE_INT el_size
= tree_to_shwi (elem_size
);
3528 gcc_assert (el_size
> 0);
3530 tree minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (root
->type
));
3531 gcc_assert (TREE_CODE (minidx
) == INTEGER_CST
);
3532 tree maxidx
= TYPE_MAX_VALUE (TYPE_DOMAIN (root
->type
));
3533 /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
3536 gcc_assert (TREE_CODE (maxidx
) == INTEGER_CST
);
3537 tree domain
= TYPE_DOMAIN (root
->type
);
3538 /* MINIDX and MAXIDX are inclusive, and must be interpreted in
3539 DOMAIN (e.g. signed int, whereas min/max may be size_int). */
3540 offset_int idx
= wi::to_offset (minidx
);
3541 offset_int max
= wi::to_offset (maxidx
);
3542 if (!TYPE_UNSIGNED (domain
))
3544 idx
= wi::sext (idx
, TYPE_PRECISION (domain
));
3545 max
= wi::sext (max
, TYPE_PRECISION (domain
));
3547 for (HOST_WIDE_INT pos
= root
->offset
;
3549 pos
+= el_size
, ++idx
)
3551 enum total_sra_field_state
3552 state
= total_should_skip_creating_access (root
,
3558 case TOTAL_FLD_FAILED
:
3560 case TOTAL_FLD_DONE
:
3562 case TOTAL_FLD_CREATE
:
3568 struct access
**p
= (last_seen_sibling
3569 ? &last_seen_sibling
->next_sibling
3570 : &root
->first_child
);
3571 tree nref
= build4 (ARRAY_REF
, elemtype
, root
->expr
,
3572 wide_int_to_tree (domain
, idx
),
3573 NULL_TREE
, NULL_TREE
);
3574 struct access
*new_child
3575 = create_total_access_and_reshape (root
, pos
, el_size
, elemtype
,
3580 if (!is_gimple_reg_type (elemtype
)
3581 && !totally_scalarize_subtree (new_child
))
3583 last_seen_sibling
= new_child
;
3595 /* Go through all accesses collected throughout the (intraprocedural) analysis
3596 stage, exclude overlapping ones, identify representatives and build trees
3597 out of them, making decisions about scalarization on the way. Return true
3598 iff there are any to-be-scalarized variables after this stage. */
3601 analyze_all_variable_accesses (void)
3604 bitmap tmp
= BITMAP_ALLOC (NULL
);
3608 bitmap_copy (tmp
, candidate_bitmap
);
3609 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3611 tree var
= candidate (i
);
3612 struct access
*access
;
3614 access
= sort_and_splice_var_accesses (var
);
3615 if (!access
|| !build_access_trees (access
))
3616 disqualify_candidate (var
,
3617 "No or inhibitingly overlapping accesses.");
3620 propagate_all_subaccesses ();
3622 bool optimize_speed_p
= !optimize_function_for_size_p (cfun
);
3623 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3624 fall back to a target default. */
3625 unsigned HOST_WIDE_INT max_scalarization_size
3626 = get_move_ratio (optimize_speed_p
) * UNITS_PER_WORD
;
3628 if (optimize_speed_p
)
3630 if (OPTION_SET_P (param_sra_max_scalarization_size_speed
))
3631 max_scalarization_size
= param_sra_max_scalarization_size_speed
;
3635 if (OPTION_SET_P (param_sra_max_scalarization_size_size
))
3636 max_scalarization_size
= param_sra_max_scalarization_size_size
;
3638 max_scalarization_size
*= BITS_PER_UNIT
;
3640 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
3641 if (bitmap_bit_p (should_scalarize_away_bitmap
, i
)
3642 && !bitmap_bit_p (cannot_scalarize_away_bitmap
, i
))
3644 tree var
= candidate (i
);
3648 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var
))) > max_scalarization_size
)
3650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3652 fprintf (dump_file
, "Too big to totally scalarize: ");
3653 print_generic_expr (dump_file
, var
);
3654 fprintf (dump_file
, " (UID: %u)\n", DECL_UID (var
));
3659 bool all_types_ok
= true;
3660 for (struct access
*access
= get_first_repr_for_decl (var
);
3662 access
= access
->next_grp
)
3663 if (!can_totally_scalarize_forest_p (access
)
3664 || !scalarizable_type_p (access
->type
, constant_decl_p (var
)))
3666 all_types_ok
= false;
3672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3674 fprintf (dump_file
, "Will attempt to totally scalarize ");
3675 print_generic_expr (dump_file
, var
);
3676 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3678 bool scalarized
= true;
3679 for (struct access
*access
= get_first_repr_for_decl (var
);
3681 access
= access
->next_grp
)
3682 if (!is_gimple_reg_type (access
->type
)
3683 && !totally_scalarize_subtree (access
))
3690 for (struct access
*access
= get_first_repr_for_decl (var
);
3692 access
= access
->next_grp
)
3693 access
->grp_total_scalarization
= true;
3697 verify_all_sra_access_forests ();
3699 bitmap_copy (tmp
, candidate_bitmap
);
3700 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3702 tree var
= candidate (i
);
3703 struct access
*access
= get_first_repr_for_decl (var
);
3705 if (analyze_access_trees (access
))
3708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3710 fprintf (dump_file
, "\nAccess trees for ");
3711 print_generic_expr (dump_file
, var
);
3712 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3713 dump_access_tree (dump_file
, access
);
3714 fprintf (dump_file
, "\n");
3718 disqualify_candidate (var
, "No scalar replacements to be created.");
3725 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
3732 /* Generate statements copying scalar replacements of accesses within a subtree
3733 into or out of AGG. ACCESS, all its children, siblings and their children
3734 are to be processed. AGG is an aggregate type expression (can be a
3735 declaration but does not have to be, it can for example also be a mem_ref or
3736 a series of handled components). TOP_OFFSET is the offset of the processed
3737 subtree which has to be subtracted from offsets of individual accesses to
3738 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3739 replacements in the interval <start_offset, start_offset + chunk_size>,
3740 otherwise copy all. GSI is a statement iterator used to place the new
3741 statements. WRITE should be true when the statements should write from AGG
3742 to the replacement and false if vice versa. if INSERT_AFTER is true, new
3743 statements will be added after the current statement in GSI, they will be
3744 added before the statement otherwise. */
3747 generate_subtree_copies (struct access
*access
, tree agg
,
3748 HOST_WIDE_INT top_offset
,
3749 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
3750 gimple_stmt_iterator
*gsi
, bool write
,
3751 bool insert_after
, location_t loc
)
3753 /* Never write anything into constant pool decls. See PR70602. */
3754 if (!write
&& constant_decl_p (agg
))
3758 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
3761 if (access
->grp_to_be_replaced
3763 || access
->offset
+ access
->size
> start_offset
))
3765 tree expr
, repl
= get_access_replacement (access
);
3768 expr
= build_ref_for_model (loc
, agg
, access
->offset
- top_offset
,
3769 access
, gsi
, insert_after
);
3773 if (access
->grp_partial_lhs
)
3774 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
3776 insert_after
? GSI_NEW_STMT
3778 stmt
= gimple_build_assign (repl
, expr
);
3782 suppress_warning (repl
/* Be more selective! */);
3783 if (access
->grp_partial_lhs
)
3784 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
3786 insert_after
? GSI_NEW_STMT
3788 stmt
= gimple_build_assign (expr
, repl
);
3790 gimple_set_location (stmt
, loc
);
3793 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3795 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3797 sra_stats
.subtree_copies
++;
3800 && access
->grp_to_be_debug_replaced
3802 || access
->offset
+ access
->size
> start_offset
))
3805 tree drhs
= build_debug_ref_for_model (loc
, agg
,
3806 access
->offset
- top_offset
,
3808 ds
= gimple_build_debug_bind (get_access_replacement (access
),
3809 drhs
, gsi_stmt (*gsi
));
3811 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3813 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3816 if (access
->first_child
)
3817 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
3818 start_offset
, chunk_size
, gsi
,
3819 write
, insert_after
, loc
);
3821 access
= access
->next_sibling
;
3826 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
3827 root of the subtree to be processed. GSI is the statement iterator used
3828 for inserting statements which are added after the current statement if
3829 INSERT_AFTER is true or before it otherwise. */
3832 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
3833 bool insert_after
, location_t loc
)
3836 struct access
*child
;
3838 if (access
->grp_to_be_replaced
)
3842 stmt
= gimple_build_assign (get_access_replacement (access
),
3843 build_zero_cst (access
->type
));
3845 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3847 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3849 gimple_set_location (stmt
, loc
);
3851 else if (access
->grp_to_be_debug_replaced
)
3854 = gimple_build_debug_bind (get_access_replacement (access
),
3855 build_zero_cst (access
->type
),
3858 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3860 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3863 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3864 init_subtree_with_zero (child
, gsi
, insert_after
, loc
);
3867 /* Clobber all scalar replacements in an access subtree. ACCESS is the
3868 root of the subtree to be processed. GSI is the statement iterator used
3869 for inserting statements which are added after the current statement if
3870 INSERT_AFTER is true or before it otherwise. */
3873 clobber_subtree (struct access
*access
, gimple_stmt_iterator
*gsi
,
3874 bool insert_after
, location_t loc
)
3877 struct access
*child
;
3879 if (access
->grp_to_be_replaced
)
3881 tree rep
= get_access_replacement (access
);
3882 tree clobber
= build_clobber (access
->type
);
3883 gimple
*stmt
= gimple_build_assign (rep
, clobber
);
3886 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3888 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3890 gimple_set_location (stmt
, loc
);
3893 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3894 clobber_subtree (child
, gsi
, insert_after
, loc
);
3897 /* Search for an access representative for the given expression EXPR and
3898 return it or NULL if it cannot be found. */
3900 static struct access
*
3901 get_access_for_expr (tree expr
)
3903 poly_int64 poffset
, psize
, pmax_size
;
3904 HOST_WIDE_INT offset
, max_size
;
3908 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
3909 a different size than the size of its argument and we need the latter
3911 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
3912 expr
= TREE_OPERAND (expr
, 0);
3914 base
= get_ref_base_and_extent (expr
, &poffset
, &psize
, &pmax_size
,
3916 if (!known_size_p (pmax_size
)
3917 || !pmax_size
.is_constant (&max_size
)
3918 || !poffset
.is_constant (&offset
)
3922 if (tree basesize
= DECL_SIZE (base
))
3926 || !poly_int_tree_p (basesize
, &sz
)
3927 || known_le (sz
, offset
))
3932 || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
3935 return get_var_base_offset_size_access (base
, offset
, max_size
);
3938 /* Replace the expression EXPR with a scalar replacement if there is one and
3939 generate other statements to do type conversion or subtree copying if
3940 necessary. WRITE is true if the expression is being written to (it is on a
3941 LHS of a statement or output in an assembly statement). STMT_GSI is used to
3942 place newly created statements before the processed statement, REFRESH_GSI
3943 is used to place them afterwards - unless the processed statement must end a
3944 BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
3945 is then used to continue iteration over the BB. If sra_modify_expr is
3946 called only once with WRITE equal to true on a given statement, both
3947 iterator parameters can point to the same one. */
3950 sra_modify_expr (tree
*expr
, bool write
, gimple_stmt_iterator
*stmt_gsi
,
3951 gimple_stmt_iterator
*refresh_gsi
)
3954 struct access
*access
;
3955 tree type
, bfr
, orig_expr
;
3956 bool partial_cplx_access
= false;
3958 if (TREE_CODE (*expr
) == BIT_FIELD_REF
3959 && (write
|| !sra_handled_bf_read_p (*expr
)))
3962 expr
= &TREE_OPERAND (*expr
, 0);
3967 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
3969 expr
= &TREE_OPERAND (*expr
, 0);
3970 partial_cplx_access
= true;
3972 access
= get_access_for_expr (*expr
);
3975 type
= TREE_TYPE (*expr
);
3978 loc
= gimple_location (gsi_stmt (*stmt_gsi
));
3979 gimple_stmt_iterator alt_gsi
= gsi_none ();
3980 if (write
&& stmt_ends_bb_p (gsi_stmt (*stmt_gsi
)))
3982 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi
)));
3983 refresh_gsi
= &alt_gsi
;
3986 if (access
->grp_to_be_replaced
)
3988 tree repl
= get_access_replacement (access
);
3989 /* If we replace a non-register typed access simply use the original
3990 access expression to extract the scalar component afterwards.
3991 This happens if scalarizing a function return value or parameter
3992 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
3993 gcc.c-torture/compile/20011217-1.c.
3995 We also want to use this when accessing a complex or vector which can
3996 be accessed as a different type too, potentially creating a need for
3997 type conversion (see PR42196) and when scalarized unions are involved
3998 in assembler statements (see PR42398). */
3999 if (!bfr
&& !useless_type_conversion_p (type
, access
->type
))
4003 ref
= build_ref_for_model (loc
, orig_expr
, 0, access
, stmt_gsi
,
4006 if (partial_cplx_access
)
4008 /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4009 the case of a write because in such case the replacement cannot
4010 be a gimple register. In the case of a load, we have to
4011 differentiate in between a register an non-register
4013 tree t
= build1 (VIEW_CONVERT_EXPR
, type
, repl
);
4014 gcc_checking_assert (!write
|| access
->grp_partial_lhs
);
4015 if (!access
->grp_partial_lhs
)
4017 tree tmp
= make_ssa_name (type
);
4018 gassign
*stmt
= gimple_build_assign (tmp
, t
);
4019 /* This is always a read. */
4020 gsi_insert_before (stmt_gsi
, stmt
, GSI_SAME_STMT
);
4029 if (access
->grp_partial_lhs
)
4030 ref
= force_gimple_operand_gsi (refresh_gsi
, ref
, true,
4031 NULL_TREE
, false, GSI_NEW_STMT
);
4032 stmt
= gimple_build_assign (repl
, ref
);
4033 gimple_set_location (stmt
, loc
);
4034 gsi_insert_after (refresh_gsi
, stmt
, GSI_NEW_STMT
);
4040 if (access
->grp_partial_lhs
)
4041 repl
= force_gimple_operand_gsi (stmt_gsi
, repl
, true,
4044 stmt
= gimple_build_assign (ref
, repl
);
4045 gimple_set_location (stmt
, loc
);
4046 gsi_insert_before (stmt_gsi
, stmt
, GSI_SAME_STMT
);
4051 /* If we are going to replace a scalar field in a structure with
4052 reverse storage order by a stand-alone scalar, we are going to
4053 effectively byte-swap the scalar and we also need to byte-swap
4054 the portion of it represented by the bit-field. */
4055 if (bfr
&& REF_REVERSE_STORAGE_ORDER (bfr
))
4057 REF_REVERSE_STORAGE_ORDER (bfr
) = 0;
4058 TREE_OPERAND (bfr
, 2)
4059 = size_binop (MINUS_EXPR
, TYPE_SIZE (TREE_TYPE (repl
)),
4060 size_binop (PLUS_EXPR
, TREE_OPERAND (bfr
, 1),
4061 TREE_OPERAND (bfr
, 2)));
4069 else if (write
&& access
->grp_to_be_debug_replaced
)
4071 gdebug
*ds
= gimple_build_debug_bind (get_access_replacement (access
),
4073 gsi_stmt (*stmt_gsi
));
4074 gsi_insert_after (stmt_gsi
, ds
, GSI_NEW_STMT
);
4077 if (access
->first_child
&& !TREE_READONLY (access
->base
))
4079 HOST_WIDE_INT start_offset
, chunk_size
;
4081 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 1))
4082 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 2)))
4084 chunk_size
= tree_to_uhwi (TREE_OPERAND (bfr
, 1));
4085 start_offset
= access
->offset
4086 + tree_to_uhwi (TREE_OPERAND (bfr
, 2));
4089 start_offset
= chunk_size
= 0;
4091 generate_subtree_copies (access
->first_child
, orig_expr
, access
->offset
,
4092 start_offset
, chunk_size
,
4093 write
? refresh_gsi
: stmt_gsi
,
4099 /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4100 reads from its base before and after the call statement given in CALL_GSI
4101 and return true if any copying took place. Otherwise call sra_modify_expr
4102 on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4103 return for the given parameter. */
4106 sra_modify_call_arg (tree
*expr
, gimple_stmt_iterator
*call_gsi
,
4107 gimple_stmt_iterator
*refresh_gsi
, int flags
)
4109 if (TREE_CODE (*expr
) != ADDR_EXPR
)
4110 return sra_modify_expr (expr
, false, call_gsi
, refresh_gsi
);
4112 if (flags
& EAF_UNUSED
)
4115 tree base
= get_base_address (TREE_OPERAND (*expr
, 0));
4118 struct access
*access
= get_access_for_expr (base
);
4122 gimple
*stmt
= gsi_stmt (*call_gsi
);
4123 location_t loc
= gimple_location (stmt
);
4124 generate_subtree_copies (access
, base
, 0, 0, 0, call_gsi
, false, false,
4127 if (flags
& EAF_NO_DIRECT_CLOBBER
)
4130 if (!stmt_ends_bb_p (stmt
))
4131 generate_subtree_copies (access
, base
, 0, 0, 0, refresh_gsi
, true,
4137 FOR_EACH_EDGE (e
, ei
, gsi_bb (*call_gsi
)->succs
)
4139 gimple_stmt_iterator alt_gsi
= gsi_start_edge (e
);
4140 generate_subtree_copies (access
, base
, 0, 0, 0, &alt_gsi
, true,
4147 /* Where scalar replacements of the RHS have been written to when a replacement
4148 of a LHS of an assigments cannot be direclty loaded from a replacement of
4150 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
4151 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
4152 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
4154 struct subreplacement_assignment_data
4156 /* Offset of the access representing the lhs of the assignment. */
4157 HOST_WIDE_INT left_offset
;
4159 /* LHS and RHS of the original assignment. */
4160 tree assignment_lhs
, assignment_rhs
;
4162 /* Access representing the rhs of the whole assignment. */
4163 struct access
*top_racc
;
4165 /* Stmt iterator used for statement insertions after the original assignment.
4166 It points to the main GSI used to traverse a BB during function body
4168 gimple_stmt_iterator
*new_gsi
;
4170 /* Stmt iterator used for statement insertions before the original
4171 assignment. Keeps on pointing to the original statement. */
4172 gimple_stmt_iterator old_gsi
;
4174 /* Location of the assignment. */
4177 /* Keeps the information whether we have needed to refresh replacements of
4178 the LHS and from which side of the assignments this takes place. */
4179 enum unscalarized_data_handling refreshed
;
4182 /* Store all replacements in the access tree rooted in TOP_RACC either to their
4183 base aggregate if there are unscalarized data or directly to LHS of the
4184 statement that is pointed to by GSI otherwise. */
4187 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data
*sad
)
4190 /* If the RHS is a load from a constant, we do not need to (and must not)
4191 flush replacements to it and can use it directly as if we did. */
4192 if (TREE_READONLY (sad
->top_racc
->base
))
4194 sad
->refreshed
= SRA_UDH_RIGHT
;
4197 if (sad
->top_racc
->grp_unscalarized_data
)
4199 src
= sad
->assignment_rhs
;
4200 sad
->refreshed
= SRA_UDH_RIGHT
;
4204 src
= sad
->assignment_lhs
;
4205 sad
->refreshed
= SRA_UDH_LEFT
;
4207 generate_subtree_copies (sad
->top_racc
->first_child
, src
,
4208 sad
->top_racc
->offset
, 0, 0,
4209 &sad
->old_gsi
, false, false, sad
->loc
);
4212 /* Try to generate statements to load all sub-replacements in an access subtree
4213 formed by children of LACC from scalar replacements in the SAD->top_racc
4214 subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4215 and load the accesses from it. */
4218 load_assign_lhs_subreplacements (struct access
*lacc
,
4219 struct subreplacement_assignment_data
*sad
)
4221 for (lacc
= lacc
->first_child
; lacc
; lacc
= lacc
->next_sibling
)
4223 HOST_WIDE_INT offset
;
4224 offset
= lacc
->offset
- sad
->left_offset
+ sad
->top_racc
->offset
;
4226 if (lacc
->grp_to_be_replaced
)
4228 struct access
*racc
;
4232 racc
= find_access_in_subtree (sad
->top_racc
, offset
, lacc
->size
);
4233 if (racc
&& racc
->grp_to_be_replaced
)
4235 rhs
= get_access_replacement (racc
);
4237 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
4239 rhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
4244 if (lacc
->grp_partial_lhs
&& (vce
|| racc
->grp_partial_lhs
))
4245 rhs
= force_gimple_operand_gsi (&sad
->old_gsi
, rhs
, true,
4246 NULL_TREE
, true, GSI_SAME_STMT
);
4250 /* No suitable access on the right hand side, need to load from
4251 the aggregate. See if we have to update it first... */
4252 if (sad
->refreshed
== SRA_UDH_NONE
)
4253 handle_unscalarized_data_in_subtree (sad
);
4255 if (sad
->refreshed
== SRA_UDH_LEFT
)
4256 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_lhs
,
4257 lacc
->offset
- sad
->left_offset
,
4258 lacc
, sad
->new_gsi
, true);
4260 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_rhs
,
4261 lacc
->offset
- sad
->left_offset
,
4262 lacc
, sad
->new_gsi
, true);
4263 if (lacc
->grp_partial_lhs
)
4264 rhs
= force_gimple_operand_gsi (sad
->new_gsi
,
4265 rhs
, true, NULL_TREE
,
4266 false, GSI_NEW_STMT
);
4269 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
4270 gsi_insert_after (sad
->new_gsi
, stmt
, GSI_NEW_STMT
);
4271 gimple_set_location (stmt
, sad
->loc
);
4273 sra_stats
.subreplacements
++;
4277 if (sad
->refreshed
== SRA_UDH_NONE
4278 && lacc
->grp_read
&& !lacc
->grp_covered
)
4279 handle_unscalarized_data_in_subtree (sad
);
4281 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
4285 struct access
*racc
= find_access_in_subtree (sad
->top_racc
,
4289 if (racc
&& racc
->grp_to_be_replaced
)
4291 if (racc
->grp_write
|| constant_decl_p (racc
->base
))
4292 drhs
= get_access_replacement (racc
);
4296 else if (sad
->refreshed
== SRA_UDH_LEFT
)
4297 drhs
= build_debug_ref_for_model (sad
->loc
, lacc
->base
,
4298 lacc
->offset
, lacc
);
4299 else if (sad
->refreshed
== SRA_UDH_RIGHT
)
4300 drhs
= build_debug_ref_for_model (sad
->loc
, sad
->top_racc
->base
,
4305 && !useless_type_conversion_p (lacc
->type
, TREE_TYPE (drhs
)))
4306 drhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
4308 ds
= gimple_build_debug_bind (get_access_replacement (lacc
),
4309 drhs
, gsi_stmt (sad
->old_gsi
));
4310 gsi_insert_after (sad
->new_gsi
, ds
, GSI_NEW_STMT
);
4314 if (lacc
->first_child
)
4315 load_assign_lhs_subreplacements (lacc
, sad
);
4319 /* Result code for SRA assignment modification. */
4320 enum assignment_mod_result
{ SRA_AM_NONE
, /* nothing done for the stmt */
4321 SRA_AM_MODIFIED
, /* stmt changed but not
4323 SRA_AM_REMOVED
}; /* stmt eliminated */
4325 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4326 to the assignment and GSI is the statement iterator pointing at it. Returns
4327 the same values as sra_modify_assign. */
4329 static enum assignment_mod_result
4330 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
4332 tree lhs
= gimple_assign_lhs (stmt
);
4333 struct access
*acc
= get_access_for_expr (lhs
);
4336 location_t loc
= gimple_location (stmt
);
4338 if (gimple_clobber_p (stmt
))
4340 /* Clobber the replacement variable. */
4341 clobber_subtree (acc
, gsi
, !acc
->grp_covered
, loc
);
4342 /* Remove clobbers of fully scalarized variables, they are dead. */
4343 if (acc
->grp_covered
)
4345 unlink_stmt_vdef (stmt
);
4346 gsi_remove (gsi
, true);
4347 release_defs (stmt
);
4348 return SRA_AM_REMOVED
;
4351 return SRA_AM_MODIFIED
;
4354 if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
)) > 0)
4356 /* I have never seen this code path trigger but if it can happen the
4357 following should handle it gracefully. */
4358 if (access_has_children_p (acc
))
4359 generate_subtree_copies (acc
->first_child
, lhs
, acc
->offset
, 0, 0, gsi
,
4361 return SRA_AM_MODIFIED
;
4364 if (acc
->grp_covered
)
4366 init_subtree_with_zero (acc
, gsi
, false, loc
);
4367 unlink_stmt_vdef (stmt
);
4368 gsi_remove (gsi
, true);
4369 release_defs (stmt
);
4370 return SRA_AM_REMOVED
;
4374 init_subtree_with_zero (acc
, gsi
, true, loc
);
4375 return SRA_AM_MODIFIED
;
4379 /* Create and return a new suitable default definition SSA_NAME for RACC which
4380 is an access describing an uninitialized part of an aggregate that is being
4381 loaded. REG_TREE is used instead of the actual RACC type if that is not of
4382 a gimple register type. */
4385 get_repl_default_def_ssa_name (struct access
*racc
, tree reg_type
)
4387 gcc_checking_assert (!racc
->grp_to_be_replaced
4388 && !racc
->grp_to_be_debug_replaced
);
4389 if (!racc
->replacement_decl
)
4390 racc
->replacement_decl
= create_access_replacement (racc
, reg_type
);
4391 return get_or_create_ssa_default_def (cfun
, racc
->replacement_decl
);
4395 /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4396 of accesses within a subtree ACCESS; all its children, siblings and their
4397 children are to be processed.
4398 GSI is a statement iterator used to place the new statements. */
4400 generate_subtree_deferred_init (struct access
*access
,
4403 gimple_stmt_iterator
*gsi
,
4408 if (access
->grp_to_be_replaced
)
4410 tree repl
= get_access_replacement (access
);
4412 = gimple_build_call_internal (IFN_DEFERRED_INIT
, 3,
4413 TYPE_SIZE_UNIT (TREE_TYPE (repl
)),
4414 init_type
, decl_name
);
4415 gimple_call_set_lhs (call
, repl
);
4416 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
4418 gimple_set_location (call
, loc
);
4419 sra_stats
.subtree_deferred_init
++;
4421 if (access
->first_child
)
4422 generate_subtree_deferred_init (access
->first_child
, init_type
,
4423 decl_name
, gsi
, loc
);
4425 access
= access
->next_sibling
;
4430 /* For a call to .DEFERRED_INIT:
4431 var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4432 examine the LHS variable VAR and replace it with a scalar replacement if
4433 there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4434 the corresponding scalar relacement variable. Examine the subtree and
4435 do the scalar replacements in the subtree too. STMT is the call, GSI is
4436 the statment iterator to place newly created statement. */
4438 static enum assignment_mod_result
4439 sra_modify_deferred_init (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
4441 tree lhs
= gimple_call_lhs (stmt
);
4442 tree init_type
= gimple_call_arg (stmt
, 1);
4443 tree decl_name
= gimple_call_arg (stmt
, 2);
4445 struct access
*lhs_access
= get_access_for_expr (lhs
);
4449 location_t loc
= gimple_location (stmt
);
4451 if (lhs_access
->grp_to_be_replaced
)
4453 tree lhs_repl
= get_access_replacement (lhs_access
);
4454 gimple_call_set_lhs (stmt
, lhs_repl
);
4455 tree arg0_repl
= TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl
));
4456 gimple_call_set_arg (stmt
, 0, arg0_repl
);
4457 sra_stats
.deferred_init
++;
4458 gcc_assert (!lhs_access
->first_child
);
4459 return SRA_AM_MODIFIED
;
4462 if (lhs_access
->first_child
)
4463 generate_subtree_deferred_init (lhs_access
->first_child
,
4464 init_type
, decl_name
, gsi
, loc
);
4465 if (lhs_access
->grp_covered
)
4467 unlink_stmt_vdef (stmt
);
4468 gsi_remove (gsi
, true);
4469 release_defs (stmt
);
4470 return SRA_AM_REMOVED
;
4473 return SRA_AM_MODIFIED
;
4476 /* Examine both sides of the assignment statement pointed to by STMT, replace
4477 them with a scalare replacement if there is one and generate copying of
4478 replacements if scalarized aggregates have been used in the assignment. GSI
4479 is used to hold generated statements for type conversions and subtree
4482 static enum assignment_mod_result
4483 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
4485 struct access
*lacc
, *racc
;
4487 bool modify_this_stmt
= false;
4488 bool force_gimple_rhs
= false;
4490 gimple_stmt_iterator orig_gsi
= *gsi
;
4492 if (!gimple_assign_single_p (stmt
))
4494 lhs
= gimple_assign_lhs (stmt
);
4495 rhs
= gimple_assign_rhs1 (stmt
);
4497 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
4498 return sra_modify_constructor_assign (stmt
, gsi
);
4500 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
4501 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
4502 || (TREE_CODE (rhs
) == BIT_FIELD_REF
&& !sra_handled_bf_read_p (rhs
))
4503 || TREE_CODE (lhs
) == BIT_FIELD_REF
)
4505 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (stmt
),
4507 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (stmt
),
4509 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4512 lacc
= get_access_for_expr (lhs
);
4513 racc
= get_access_for_expr (rhs
);
4516 /* Avoid modifying initializations of constant-pool replacements. */
4517 if (racc
&& (racc
->replacement_decl
== lhs
))
4520 loc
= gimple_location (stmt
);
4521 if (lacc
&& lacc
->grp_to_be_replaced
)
4523 lhs
= get_access_replacement (lacc
);
4524 gimple_assign_set_lhs (stmt
, lhs
);
4525 modify_this_stmt
= true;
4526 if (lacc
->grp_partial_lhs
)
4527 force_gimple_rhs
= true;
4531 if (racc
&& racc
->grp_to_be_replaced
)
4533 rhs
= get_access_replacement (racc
);
4534 modify_this_stmt
= true;
4535 if (racc
->grp_partial_lhs
)
4536 force_gimple_rhs
= true;
4540 && !racc
->grp_unscalarized_data
4541 && !racc
->grp_unscalarizable_region
4542 && TREE_CODE (lhs
) == SSA_NAME
4543 && !access_has_replacements_p (racc
))
4545 rhs
= get_repl_default_def_ssa_name (racc
, TREE_TYPE (lhs
));
4546 modify_this_stmt
= true;
4550 if (modify_this_stmt
4551 && !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4553 /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4554 ??? This should move to fold_stmt which we simply should
4555 call after building a VIEW_CONVERT_EXPR here. */
4556 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
4557 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs
)) == racc
->reverse
4558 && !contains_bitfld_component_ref_p (lhs
))
4560 lhs
= build_ref_for_model (loc
, lhs
, 0, racc
, gsi
, false);
4561 gimple_assign_set_lhs (stmt
, lhs
);
4564 && AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
4565 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs
)) == lacc
->reverse
4566 && !contains_vce_or_bfcref_p (rhs
))
4567 rhs
= build_ref_for_model (loc
, rhs
, 0, lacc
, gsi
, false);
4569 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4571 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
), rhs
);
4572 if (is_gimple_reg_type (TREE_TYPE (lhs
))
4573 && TREE_CODE (lhs
) != SSA_NAME
)
4574 force_gimple_rhs
= true;
4578 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
4580 tree dlhs
= get_access_replacement (lacc
);
4581 tree drhs
= unshare_expr (rhs
);
4582 if (!useless_type_conversion_p (TREE_TYPE (dlhs
), TREE_TYPE (drhs
)))
4584 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs
))
4585 && !contains_vce_or_bfcref_p (drhs
))
4586 drhs
= build_debug_ref_for_model (loc
, drhs
, 0, lacc
);
4588 && !useless_type_conversion_p (TREE_TYPE (dlhs
),
4590 drhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
4591 TREE_TYPE (dlhs
), drhs
);
4593 gdebug
*ds
= gimple_build_debug_bind (dlhs
, drhs
, stmt
);
4594 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
4597 /* From this point on, the function deals with assignments in between
4598 aggregates when at least one has scalar reductions of some of its
4599 components. There are three possible scenarios: Both the LHS and RHS have
4600 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4602 In the first case, we would like to load the LHS components from RHS
4603 components whenever possible. If that is not possible, we would like to
4604 read it directly from the RHS (after updating it by storing in it its own
4605 components). If there are some necessary unscalarized data in the LHS,
4606 those will be loaded by the original assignment too. If neither of these
4607 cases happen, the original statement can be removed. Most of this is done
4608 by load_assign_lhs_subreplacements.
4610 In the second case, we would like to store all RHS scalarized components
4611 directly into LHS and if they cover the aggregate completely, remove the
4612 statement too. In the third case, we want the LHS components to be loaded
4613 directly from the RHS (DSE will remove the original statement if it
4616 This is a bit complex but manageable when types match and when unions do
4617 not cause confusion in a way that we cannot really load a component of LHS
4618 from the RHS or vice versa (the access representing this level can have
4619 subaccesses that are accessible only through a different union field at a
4620 higher level - different from the one used in the examined expression).
4623 Therefore, I specially handle a fourth case, happening when there is a
4624 specific type cast or it is impossible to locate a scalarized subaccess on
4625 the other side of the expression. If that happens, I simply "refresh" the
4626 RHS by storing in it is scalarized components leave the original statement
4627 there to do the copying and then load the scalar replacements of the LHS.
4628 This is what the first branch does. */
4630 if (modify_this_stmt
4631 || gimple_has_volatile_ops (stmt
)
4632 || contains_vce_or_bfcref_p (rhs
)
4633 || contains_vce_or_bfcref_p (lhs
)
4634 || stmt_ends_bb_p (stmt
))
4636 /* No need to copy into a constant, it comes pre-initialized. */
4637 if (access_has_children_p (racc
) && !TREE_READONLY (racc
->base
))
4638 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4639 gsi
, false, false, loc
);
4640 if (access_has_children_p (lacc
))
4642 gimple_stmt_iterator alt_gsi
= gsi_none ();
4643 if (stmt_ends_bb_p (stmt
))
4645 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
4648 generate_subtree_copies (lacc
->first_child
, lhs
, lacc
->offset
, 0, 0,
4649 gsi
, true, true, loc
);
4651 sra_stats
.separate_lhs_rhs_handling
++;
4653 /* This gimplification must be done after generate_subtree_copies,
4654 lest we insert the subtree copies in the middle of the gimplified
4656 if (force_gimple_rhs
)
4657 rhs
= force_gimple_operand_gsi (&orig_gsi
, rhs
, true, NULL_TREE
,
4658 true, GSI_SAME_STMT
);
4659 if (gimple_assign_rhs1 (stmt
) != rhs
)
4661 modify_this_stmt
= true;
4662 gimple_assign_set_rhs_from_tree (&orig_gsi
, rhs
);
4663 gcc_assert (stmt
== gsi_stmt (orig_gsi
));
4666 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4670 if (access_has_children_p (lacc
)
4671 && access_has_children_p (racc
)
4672 /* When an access represents an unscalarizable region, it usually
4673 represents accesses with variable offset and thus must not be used
4674 to generate new memory accesses. */
4675 && !lacc
->grp_unscalarizable_region
4676 && !racc
->grp_unscalarizable_region
)
4678 struct subreplacement_assignment_data sad
;
4680 sad
.left_offset
= lacc
->offset
;
4681 sad
.assignment_lhs
= lhs
;
4682 sad
.assignment_rhs
= rhs
;
4683 sad
.top_racc
= racc
;
4686 sad
.loc
= gimple_location (stmt
);
4687 sad
.refreshed
= SRA_UDH_NONE
;
4689 if (lacc
->grp_read
&& !lacc
->grp_covered
)
4690 handle_unscalarized_data_in_subtree (&sad
);
4692 load_assign_lhs_subreplacements (lacc
, &sad
);
4693 if (sad
.refreshed
!= SRA_UDH_RIGHT
)
4696 unlink_stmt_vdef (stmt
);
4697 gsi_remove (&sad
.old_gsi
, true);
4698 release_defs (stmt
);
4699 sra_stats
.deleted
++;
4700 return SRA_AM_REMOVED
;
4705 if (access_has_children_p (racc
)
4706 && !racc
->grp_unscalarized_data
4707 && TREE_CODE (lhs
) != SSA_NAME
)
4711 fprintf (dump_file
, "Removing load: ");
4712 print_gimple_stmt (dump_file
, stmt
, 0);
4714 generate_subtree_copies (racc
->first_child
, lhs
,
4715 racc
->offset
, 0, 0, gsi
,
4717 gcc_assert (stmt
== gsi_stmt (*gsi
));
4718 unlink_stmt_vdef (stmt
);
4719 gsi_remove (gsi
, true);
4720 release_defs (stmt
);
4721 sra_stats
.deleted
++;
4722 return SRA_AM_REMOVED
;
4724 /* Restore the aggregate RHS from its components so the
4725 prevailing aggregate copy does the right thing. */
4726 if (access_has_children_p (racc
) && !TREE_READONLY (racc
->base
))
4727 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4728 gsi
, false, false, loc
);
4729 /* Re-load the components of the aggregate copy destination.
4730 But use the RHS aggregate to load from to expose more
4731 optimization opportunities. */
4732 if (access_has_children_p (lacc
))
4733 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
4734 0, 0, gsi
, true, true, loc
);
4741 /* Set any scalar replacements of values in the constant pool to the initial
4742 value of the constant. (Constant-pool decls like *.LC0 have effectively
4743 been initialized before the program starts, we must do the same for their
4744 replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4745 the function's entry block. */
4748 initialize_constant_pool_replacements (void)
4750 gimple_seq seq
= NULL
;
4751 gimple_stmt_iterator gsi
= gsi_start (seq
);
4755 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
4757 tree var
= candidate (i
);
4758 if (!constant_decl_p (var
))
4761 struct access
*access
= get_first_repr_for_decl (var
);
4765 if (access
->replacement_decl
)
4768 = gimple_build_assign (get_access_replacement (access
),
4769 unshare_expr (access
->expr
));
4770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4772 fprintf (dump_file
, "Generating constant initializer: ");
4773 print_gimple_stmt (dump_file
, stmt
, 0);
4774 fprintf (dump_file
, "\n");
4776 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
4780 if (access
->first_child
)
4781 access
= access
->first_child
;
4782 else if (access
->next_sibling
)
4783 access
= access
->next_sibling
;
4786 while (access
->parent
&& !access
->next_sibling
)
4787 access
= access
->parent
;
4788 if (access
->next_sibling
)
4789 access
= access
->next_sibling
;
4791 access
= access
->next_grp
;
4796 seq
= gsi_seq (gsi
);
4798 gsi_insert_seq_on_edge_immediate (
4799 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4802 /* Traverse the function body and all modifications as decided in
4803 analyze_all_variable_accesses. Return true iff the CFG has been
4807 sra_modify_function_body (void)
4809 bool cfg_changed
= false;
4812 initialize_constant_pool_replacements ();
4814 FOR_EACH_BB_FN (bb
, cfun
)
4816 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
4817 while (!gsi_end_p (gsi
))
4819 gimple
*stmt
= gsi_stmt (gsi
);
4820 enum assignment_mod_result assign_result
;
4821 bool modified
= false, deleted
= false;
4825 switch (gimple_code (stmt
))
4828 t
= gimple_return_retval_ptr (as_a
<greturn
*> (stmt
));
4829 if (*t
!= NULL_TREE
)
4830 modified
|= sra_modify_expr (t
, false, &gsi
, &gsi
);
4834 assign_result
= sra_modify_assign (stmt
, &gsi
);
4835 modified
|= assign_result
== SRA_AM_MODIFIED
;
4836 deleted
= assign_result
== SRA_AM_REMOVED
;
4840 /* Handle calls to .DEFERRED_INIT specially. */
4841 if (gimple_call_internal_p (stmt
, IFN_DEFERRED_INIT
))
4843 assign_result
= sra_modify_deferred_init (stmt
, &gsi
);
4844 modified
|= assign_result
== SRA_AM_MODIFIED
;
4845 deleted
= assign_result
== SRA_AM_REMOVED
;
4849 gcall
*call
= as_a
<gcall
*> (stmt
);
4850 gimple_stmt_iterator call_gsi
= gsi
;
4852 /* Operands must be processed before the lhs. */
4853 for (i
= 0; i
< gimple_call_num_args (call
); i
++)
4855 int flags
= gimple_call_arg_flags (call
, i
);
4856 t
= gimple_call_arg_ptr (call
, i
);
4857 modified
|= sra_modify_call_arg (t
, &call_gsi
, &gsi
, flags
);
4859 if (gimple_call_chain (call
))
4861 t
= gimple_call_chain_ptr (call
);
4862 int flags
= gimple_call_static_chain_flags (call
);
4863 modified
|= sra_modify_call_arg (t
, &call_gsi
, &gsi
,
4866 if (gimple_call_lhs (call
))
4868 t
= gimple_call_lhs_ptr (call
);
4869 modified
|= sra_modify_expr (t
, true, &call_gsi
, &gsi
);
4876 gimple_stmt_iterator stmt_gsi
= gsi
;
4877 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
4878 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
4880 t
= &TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
4881 modified
|= sra_modify_expr (t
, false, &stmt_gsi
, &gsi
);
4883 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
4885 t
= &TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
4886 modified
|= sra_modify_expr (t
, true, &stmt_gsi
, &gsi
);
4898 if (maybe_clean_eh_stmt (stmt
)
4899 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
4907 gsi_commit_edge_inserts ();
4911 /* Generate statements initializing scalar replacements of parts of function
4915 initialize_parameter_reductions (void)
4917 gimple_stmt_iterator gsi
;
4918 gimple_seq seq
= NULL
;
4921 gsi
= gsi_start (seq
);
4922 for (parm
= DECL_ARGUMENTS (current_function_decl
);
4924 parm
= DECL_CHAIN (parm
))
4926 vec
<access_p
> *access_vec
;
4927 struct access
*access
;
4929 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
4931 access_vec
= get_base_access_vector (parm
);
4935 for (access
= (*access_vec
)[0];
4937 access
= access
->next_grp
)
4938 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true,
4939 EXPR_LOCATION (parm
));
4942 seq
= gsi_seq (gsi
);
4944 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4947 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
4948 it reveals there are components of some aggregates to be scalarized, it runs
4949 the required transformations. */
4951 perform_intra_sra (void)
4956 if (!find_var_candidates ())
4959 if (!scan_function ())
4962 if (!analyze_all_variable_accesses ())
4965 if (sra_modify_function_body ())
4966 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
4968 ret
= TODO_update_ssa
;
4969 initialize_parameter_reductions ();
4971 statistics_counter_event (cfun
, "Scalar replacements created",
4972 sra_stats
.replacements
);
4973 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
4974 statistics_counter_event (cfun
, "Subtree copy stmts",
4975 sra_stats
.subtree_copies
);
4976 statistics_counter_event (cfun
, "Subreplacement stmts",
4977 sra_stats
.subreplacements
);
4978 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
4979 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
4980 sra_stats
.separate_lhs_rhs_handling
);
4983 sra_deinitialize ();
4987 /* Perform early intraprocedural SRA. */
4989 early_intra_sra (void)
4991 sra_mode
= SRA_MODE_EARLY_INTRA
;
4992 return perform_intra_sra ();
4995 /* Perform "late" intraprocedural SRA. */
4997 late_intra_sra (void)
4999 sra_mode
= SRA_MODE_INTRA
;
5000 return perform_intra_sra ();
5005 gate_intra_sra (void)
5007 return flag_tree_sra
!= 0 && dbg_cnt (tree_sra
);
5013 const pass_data pass_data_sra_early
=
5015 GIMPLE_PASS
, /* type */
5017 OPTGROUP_NONE
, /* optinfo_flags */
5018 TV_TREE_SRA
, /* tv_id */
5019 ( PROP_cfg
| PROP_ssa
), /* properties_required */
5020 0, /* properties_provided */
5021 0, /* properties_destroyed */
5022 0, /* todo_flags_start */
5023 TODO_update_ssa
, /* todo_flags_finish */
5026 class pass_sra_early
: public gimple_opt_pass
5029 pass_sra_early (gcc::context
*ctxt
)
5030 : gimple_opt_pass (pass_data_sra_early
, ctxt
)
5033 /* opt_pass methods: */
5034 bool gate (function
*) final override
{ return gate_intra_sra (); }
5035 unsigned int execute (function
*) final override
5037 return early_intra_sra ();
5040 }; // class pass_sra_early
5045 make_pass_sra_early (gcc::context
*ctxt
)
5047 return new pass_sra_early (ctxt
);
5052 const pass_data pass_data_sra
=
5054 GIMPLE_PASS
, /* type */
5056 OPTGROUP_NONE
, /* optinfo_flags */
5057 TV_TREE_SRA
, /* tv_id */
5058 ( PROP_cfg
| PROP_ssa
), /* properties_required */
5059 0, /* properties_provided */
5060 0, /* properties_destroyed */
5061 TODO_update_address_taken
, /* todo_flags_start */
5062 TODO_update_ssa
, /* todo_flags_finish */
5065 class pass_sra
: public gimple_opt_pass
5068 pass_sra (gcc::context
*ctxt
)
5069 : gimple_opt_pass (pass_data_sra
, ctxt
)
5072 /* opt_pass methods: */
5073 bool gate (function
*) final override
{ return gate_intra_sra (); }
5074 unsigned int execute (function
*) final override
{ return late_intra_sra (); }
5076 }; // class pass_sra
5081 make_pass_sra (gcc::context
*ctxt
)
5083 return new pass_sra (ctxt
);