1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008-2020 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;
265 typedef struct access
*access_p
;
268 /* Alloc pool for allocating access structures. */
269 static object_allocator
<struct access
> access_pool ("SRA accesses");
271 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
272 are used to propagate subaccesses from rhs to lhs and vice versa as long as
273 they don't conflict with what is already there. In the RHS->LHS direction,
274 we also propagate grp_write flag to lazily mark that the access contains any
278 struct access
*lacc
, *racc
;
279 struct assign_link
*next_rhs
, *next_lhs
;
282 /* Alloc pool for allocating assign link structures. */
283 static object_allocator
<assign_link
> assign_link_pool ("SRA links");
285 /* Base (tree) -> Vector (vec<access_p> *) map. */
286 static hash_map
<tree
, auto_vec
<access_p
> > *base_access_vec
;
288 /* Candidate hash table helpers. */
290 struct uid_decl_hasher
: nofree_ptr_hash
<tree_node
>
292 static inline hashval_t
hash (const tree_node
*);
293 static inline bool equal (const tree_node
*, const tree_node
*);
296 /* Hash a tree in a uid_decl_map. */
299 uid_decl_hasher::hash (const tree_node
*item
)
301 return item
->decl_minimal
.uid
;
304 /* Return true if the DECL_UID in both trees are equal. */
307 uid_decl_hasher::equal (const tree_node
*a
, const tree_node
*b
)
309 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
312 /* Set of candidates. */
313 static bitmap candidate_bitmap
;
314 static hash_table
<uid_decl_hasher
> *candidates
;
316 /* For a candidate UID return the candidates decl. */
319 candidate (unsigned uid
)
322 t
.decl_minimal
.uid
= uid
;
323 return candidates
->find_with_hash (&t
, static_cast <hashval_t
> (uid
));
326 /* Bitmap of candidates which we should try to entirely scalarize away and
327 those which cannot be (because they are and need be used as a whole). */
328 static bitmap should_scalarize_away_bitmap
, cannot_scalarize_away_bitmap
;
330 /* Bitmap of candidates in the constant pool, which cannot be scalarized
331 because this would produce non-constant expressions (e.g. Ada). */
332 static bitmap disqualified_constants
;
334 /* Obstack for creation of fancy names. */
335 static struct obstack name_obstack
;
337 /* Head of a linked list of accesses that need to have its subaccesses
338 propagated to their assignment counterparts. */
339 static struct access
*rhs_work_queue_head
, *lhs_work_queue_head
;
341 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
342 representative fields are dumped, otherwise those which only describe the
343 individual access are. */
347 /* Number of processed aggregates is readily available in
348 analyze_all_variable_accesses and so is not stored here. */
350 /* Number of created scalar replacements. */
353 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
357 /* Number of statements created by generate_subtree_copies. */
360 /* Number of statements created by load_assign_lhs_subreplacements. */
363 /* Number of times sra_modify_assign has deleted a statement. */
366 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
367 RHS reparately due to type conversions or nonexistent matching
369 int separate_lhs_rhs_handling
;
371 /* Number of parameters that were removed because they were unused. */
372 int deleted_unused_parameters
;
374 /* Number of scalars passed as parameters by reference that have been
375 converted to be passed by value. */
376 int scalar_by_ref_to_by_val
;
378 /* Number of aggregate parameters that were replaced by one or more of their
380 int aggregate_params_reduced
;
382 /* Numbber of components created when splitting aggregate parameters. */
383 int param_reductions_created
;
387 dump_access (FILE *f
, struct access
*access
, bool grp
)
389 fprintf (f
, "access { ");
390 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
391 print_generic_expr (f
, access
->base
);
392 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
393 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
394 fprintf (f
, ", expr = ");
395 print_generic_expr (f
, access
->expr
);
396 fprintf (f
, ", type = ");
397 print_generic_expr (f
, access
->type
);
398 fprintf (f
, ", reverse = %d", access
->reverse
);
400 fprintf (f
, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
401 "grp_assignment_write = %d, grp_scalar_read = %d, "
402 "grp_scalar_write = %d, grp_total_scalarization = %d, "
403 "grp_hint = %d, grp_covered = %d, "
404 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
405 "grp_same_access_path = %d, grp_partial_lhs = %d, "
406 "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d}\n",
407 access
->grp_read
, access
->grp_write
, access
->grp_assignment_read
,
408 access
->grp_assignment_write
, access
->grp_scalar_read
,
409 access
->grp_scalar_write
, access
->grp_total_scalarization
,
410 access
->grp_hint
, access
->grp_covered
,
411 access
->grp_unscalarizable_region
, access
->grp_unscalarized_data
,
412 access
->grp_same_access_path
, access
->grp_partial_lhs
,
413 access
->grp_to_be_replaced
, access
->grp_to_be_debug_replaced
);
415 fprintf (f
, ", write = %d, grp_total_scalarization = %d, "
416 "grp_partial_lhs = %d}\n",
417 access
->write
, access
->grp_total_scalarization
,
418 access
->grp_partial_lhs
);
421 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
424 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
430 for (i
= 0; i
< level
; i
++)
433 dump_access (f
, access
, true);
435 if (access
->first_child
)
436 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
438 access
= access
->next_sibling
;
443 /* Dump all access trees for a variable, given the pointer to the first root in
447 dump_access_tree (FILE *f
, struct access
*access
)
449 for (; access
; access
= access
->next_grp
)
450 dump_access_tree_1 (f
, access
, 0);
453 /* Return true iff ACC is non-NULL and has subaccesses. */
456 access_has_children_p (struct access
*acc
)
458 return acc
&& acc
->first_child
;
461 /* Return true iff ACC is (partly) covered by at least one replacement. */
464 access_has_replacements_p (struct access
*acc
)
466 struct access
*child
;
467 if (acc
->grp_to_be_replaced
)
469 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
470 if (access_has_replacements_p (child
))
475 /* Return a vector of pointers to accesses for the variable given in BASE or
476 NULL if there is none. */
478 static vec
<access_p
> *
479 get_base_access_vector (tree base
)
481 return base_access_vec
->get (base
);
484 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
485 in ACCESS. Return NULL if it cannot be found. */
487 static struct access
*
488 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
491 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
493 struct access
*child
= access
->first_child
;
495 while (child
&& (child
->offset
+ child
->size
<= offset
))
496 child
= child
->next_sibling
;
500 /* Total scalarization does not replace single field structures with their
501 single field but rather creates an access for them underneath. Look for
504 while (access
->first_child
505 && access
->first_child
->offset
== offset
506 && access
->first_child
->size
== size
)
507 access
= access
->first_child
;
512 /* Return the first group representative for DECL or NULL if none exists. */
514 static struct access
*
515 get_first_repr_for_decl (tree base
)
517 vec
<access_p
> *access_vec
;
519 access_vec
= get_base_access_vector (base
);
523 return (*access_vec
)[0];
526 /* Find an access representative for the variable BASE and given OFFSET and
527 SIZE. Requires that access trees have already been built. Return NULL if
528 it cannot be found. */
530 static struct access
*
531 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
534 struct access
*access
;
536 access
= get_first_repr_for_decl (base
);
537 while (access
&& (access
->offset
+ access
->size
<= offset
))
538 access
= access
->next_grp
;
542 return find_access_in_subtree (access
, offset
, size
);
545 /* Add LINK to the linked list of assign links of RACC. */
548 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
550 gcc_assert (link
->racc
== racc
);
552 if (!racc
->first_rhs_link
)
554 gcc_assert (!racc
->last_rhs_link
);
555 racc
->first_rhs_link
= link
;
558 racc
->last_rhs_link
->next_rhs
= link
;
560 racc
->last_rhs_link
= link
;
561 link
->next_rhs
= NULL
;
564 /* Add LINK to the linked list of lhs assign links of LACC. */
567 add_link_to_lhs (struct access
*lacc
, struct assign_link
*link
)
569 gcc_assert (link
->lacc
== lacc
);
571 if (!lacc
->first_lhs_link
)
573 gcc_assert (!lacc
->last_lhs_link
);
574 lacc
->first_lhs_link
= link
;
577 lacc
->last_lhs_link
->next_lhs
= link
;
579 lacc
->last_lhs_link
= link
;
580 link
->next_lhs
= NULL
;
583 /* Move all link structures in their linked list in OLD_ACC to the linked list
586 relink_to_new_repr (struct access
*new_acc
, struct access
*old_acc
)
588 if (old_acc
->first_rhs_link
)
591 if (new_acc
->first_rhs_link
)
593 gcc_assert (!new_acc
->last_rhs_link
->next_rhs
);
594 gcc_assert (!old_acc
->last_rhs_link
595 || !old_acc
->last_rhs_link
->next_rhs
);
597 new_acc
->last_rhs_link
->next_rhs
= old_acc
->first_rhs_link
;
598 new_acc
->last_rhs_link
= old_acc
->last_rhs_link
;
602 gcc_assert (!new_acc
->last_rhs_link
);
604 new_acc
->first_rhs_link
= old_acc
->first_rhs_link
;
605 new_acc
->last_rhs_link
= old_acc
->last_rhs_link
;
607 old_acc
->first_rhs_link
= old_acc
->last_rhs_link
= NULL
;
610 gcc_assert (!old_acc
->last_rhs_link
);
612 if (old_acc
->first_lhs_link
)
615 if (new_acc
->first_lhs_link
)
617 gcc_assert (!new_acc
->last_lhs_link
->next_lhs
);
618 gcc_assert (!old_acc
->last_lhs_link
619 || !old_acc
->last_lhs_link
->next_lhs
);
621 new_acc
->last_lhs_link
->next_lhs
= old_acc
->first_lhs_link
;
622 new_acc
->last_lhs_link
= old_acc
->last_lhs_link
;
626 gcc_assert (!new_acc
->last_lhs_link
);
628 new_acc
->first_lhs_link
= old_acc
->first_lhs_link
;
629 new_acc
->last_lhs_link
= old_acc
->last_lhs_link
;
631 old_acc
->first_lhs_link
= old_acc
->last_lhs_link
= NULL
;
634 gcc_assert (!old_acc
->last_lhs_link
);
638 /* Add ACCESS to the work to queue for propagation of subaccesses from RHS to
639 LHS (which is actually a stack). */
642 add_access_to_rhs_work_queue (struct access
*access
)
644 if (access
->first_rhs_link
&& !access
->grp_rhs_queued
)
646 gcc_assert (!access
->next_rhs_queued
);
647 access
->next_rhs_queued
= rhs_work_queue_head
;
648 access
->grp_rhs_queued
= 1;
649 rhs_work_queue_head
= access
;
653 /* Add ACCESS to the work to queue for propagation of subaccesses from LHS to
654 RHS (which is actually a stack). */
657 add_access_to_lhs_work_queue (struct access
*access
)
659 if (access
->first_lhs_link
&& !access
->grp_lhs_queued
)
661 gcc_assert (!access
->next_lhs_queued
);
662 access
->next_lhs_queued
= lhs_work_queue_head
;
663 access
->grp_lhs_queued
= 1;
664 lhs_work_queue_head
= access
;
668 /* Pop an access from the work queue for propagating from RHS to LHS, and
669 return it, assuming there is one. */
671 static struct access
*
672 pop_access_from_rhs_work_queue (void)
674 struct access
*access
= rhs_work_queue_head
;
676 rhs_work_queue_head
= access
->next_rhs_queued
;
677 access
->next_rhs_queued
= NULL
;
678 access
->grp_rhs_queued
= 0;
682 /* Pop an access from the work queue for propagating from LHS to RHS, and
683 return it, assuming there is one. */
685 static struct access
*
686 pop_access_from_lhs_work_queue (void)
688 struct access
*access
= lhs_work_queue_head
;
690 lhs_work_queue_head
= access
->next_lhs_queued
;
691 access
->next_lhs_queued
= NULL
;
692 access
->grp_lhs_queued
= 0;
696 /* Allocate necessary structures. */
699 sra_initialize (void)
701 candidate_bitmap
= BITMAP_ALLOC (NULL
);
702 candidates
= new hash_table
<uid_decl_hasher
>
703 (vec_safe_length (cfun
->local_decls
) / 2);
704 should_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
705 cannot_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
706 disqualified_constants
= BITMAP_ALLOC (NULL
);
707 gcc_obstack_init (&name_obstack
);
708 base_access_vec
= new hash_map
<tree
, auto_vec
<access_p
> >;
709 memset (&sra_stats
, 0, sizeof (sra_stats
));
712 /* Deallocate all general structures. */
715 sra_deinitialize (void)
717 BITMAP_FREE (candidate_bitmap
);
720 BITMAP_FREE (should_scalarize_away_bitmap
);
721 BITMAP_FREE (cannot_scalarize_away_bitmap
);
722 BITMAP_FREE (disqualified_constants
);
723 access_pool
.release ();
724 assign_link_pool
.release ();
725 obstack_free (&name_obstack
, NULL
);
727 delete base_access_vec
;
730 /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
732 static bool constant_decl_p (tree decl
)
734 return VAR_P (decl
) && DECL_IN_CONSTANT_POOL (decl
);
737 /* Remove DECL from candidates for SRA and write REASON to the dump file if
741 disqualify_candidate (tree decl
, const char *reason
)
743 if (bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
)))
744 candidates
->remove_elt_with_hash (decl
, DECL_UID (decl
));
745 if (constant_decl_p (decl
))
746 bitmap_set_bit (disqualified_constants
, DECL_UID (decl
));
748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
750 fprintf (dump_file
, "! Disqualifying ");
751 print_generic_expr (dump_file
, decl
);
752 fprintf (dump_file
, " - %s\n", reason
);
756 /* Return true iff the type contains a field or an element which does not allow
757 scalarization. Use VISITED_TYPES to avoid re-checking already checked
761 type_internals_preclude_sra_p_1 (tree type
, const char **msg
,
762 hash_set
<tree
> *visited_types
)
767 if (visited_types
->contains (type
))
769 visited_types
->add (type
);
771 switch (TREE_CODE (type
))
775 case QUAL_UNION_TYPE
:
776 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
777 if (TREE_CODE (fld
) == FIELD_DECL
)
779 if (TREE_CODE (fld
) == FUNCTION_DECL
)
781 tree ft
= TREE_TYPE (fld
);
783 if (TREE_THIS_VOLATILE (fld
))
785 *msg
= "volatile structure field";
788 if (!DECL_FIELD_OFFSET (fld
))
790 *msg
= "no structure field offset";
793 if (!DECL_SIZE (fld
))
795 *msg
= "zero structure field size";
798 if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld
)))
800 *msg
= "structure field offset not fixed";
803 if (!tree_fits_uhwi_p (DECL_SIZE (fld
)))
805 *msg
= "structure field size not fixed";
808 if (!tree_fits_shwi_p (bit_position (fld
)))
810 *msg
= "structure field size too big";
813 if (AGGREGATE_TYPE_P (ft
)
814 && int_bit_position (fld
) % BITS_PER_UNIT
!= 0)
816 *msg
= "structure field is bit field";
820 if (AGGREGATE_TYPE_P (ft
)
821 && type_internals_preclude_sra_p_1 (ft
, msg
, visited_types
))
828 et
= TREE_TYPE (type
);
830 if (TYPE_VOLATILE (et
))
832 *msg
= "element type is volatile";
836 if (AGGREGATE_TYPE_P (et
)
837 && type_internals_preclude_sra_p_1 (et
, msg
, visited_types
))
847 /* Return true iff the type contains a field or an element which does not allow
851 type_internals_preclude_sra_p (tree type
, const char **msg
)
853 hash_set
<tree
> visited_types
;
854 return type_internals_preclude_sra_p_1 (type
, msg
, &visited_types
);
858 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
859 the three fields. Also add it to the vector of accesses corresponding to
860 the base. Finally, return the new access. */
862 static struct access
*
863 create_access_1 (tree base
, HOST_WIDE_INT offset
, HOST_WIDE_INT size
)
865 struct access
*access
= access_pool
.allocate ();
867 memset (access
, 0, sizeof (struct access
));
869 access
->offset
= offset
;
872 base_access_vec
->get_or_insert (base
).safe_push (access
);
877 static bool maybe_add_sra_candidate (tree
);
879 /* Create and insert access for EXPR. Return created access, or NULL if it is
880 not possible. Also scan for uses of constant pool as we go along and add
883 static struct access
*
884 create_access (tree expr
, gimple
*stmt
, bool write
)
886 struct access
*access
;
887 poly_int64 poffset
, psize
, pmax_size
;
889 bool reverse
, unscalarizable_region
= false;
891 base
= get_ref_base_and_extent (expr
, &poffset
, &psize
, &pmax_size
,
894 /* For constant-pool entries, check we can substitute the constant value. */
895 if (constant_decl_p (base
))
897 gcc_assert (!bitmap_bit_p (disqualified_constants
, DECL_UID (base
)));
899 && !is_gimple_reg_type (TREE_TYPE (expr
))
900 && dump_file
&& (dump_flags
& TDF_DETAILS
))
902 /* This occurs in Ada with accesses to ARRAY_RANGE_REFs,
903 and elements of multidimensional arrays (which are
904 multi-element arrays in their own right). */
905 fprintf (dump_file
, "Allowing non-reg-type load of part"
906 " of constant-pool entry: ");
907 print_generic_expr (dump_file
, expr
);
909 maybe_add_sra_candidate (base
);
912 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
915 HOST_WIDE_INT offset
, size
, max_size
;
916 if (!poffset
.is_constant (&offset
)
917 || !psize
.is_constant (&size
)
918 || !pmax_size
.is_constant (&max_size
))
920 disqualify_candidate (base
, "Encountered a polynomial-sized access.");
924 if (size
!= max_size
)
927 unscalarizable_region
= true;
931 disqualify_candidate (base
, "Encountered an unconstrained access.");
935 access
= create_access_1 (base
, offset
, size
);
937 access
->type
= TREE_TYPE (expr
);
938 access
->write
= write
;
939 access
->grp_unscalarizable_region
= unscalarizable_region
;
941 access
->reverse
= reverse
;
947 /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length
948 ARRAY_TYPE with fields that are either of gimple register types (excluding
949 bit-fields) or (recursively) scalarizable types. CONST_DECL must be true if
950 we are considering a decl from constant pool. If it is false, char arrays
954 scalarizable_type_p (tree type
, bool const_decl
)
956 if (is_gimple_reg_type (type
))
958 if (type_contains_placeholder_p (type
))
961 switch (TREE_CODE (type
))
964 for (tree fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
965 if (TREE_CODE (fld
) == FIELD_DECL
)
967 tree ft
= TREE_TYPE (fld
);
969 if (DECL_BIT_FIELD (fld
))
972 if (!scalarizable_type_p (ft
, const_decl
))
980 HOST_WIDE_INT min_elem_size
;
984 min_elem_size
= BITS_PER_UNIT
;
986 if (TYPE_DOMAIN (type
) == NULL_TREE
987 || !tree_fits_shwi_p (TYPE_SIZE (type
))
988 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type
)))
989 || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type
))) <= min_elem_size
)
990 || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type
))))
992 if (tree_to_shwi (TYPE_SIZE (type
)) == 0
993 && TYPE_MAX_VALUE (TYPE_DOMAIN (type
)) == NULL_TREE
)
994 /* Zero-element array, should not prevent scalarization. */
996 else if ((tree_to_shwi (TYPE_SIZE (type
)) <= 0)
997 || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type
))))
998 /* Variable-length array, do not allow scalarization. */
1001 tree elem
= TREE_TYPE (type
);
1002 if (!scalarizable_type_p (elem
, const_decl
))
1011 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1014 contains_view_convert_expr_p (const_tree ref
)
1016 while (handled_component_p (ref
))
1018 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
)
1020 ref
= TREE_OPERAND (ref
, 0);
1026 /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1027 bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1028 it points to will be set if REF contains any of the above or a MEM_REF
1029 expression that effectively performs type conversion. */
1032 contains_vce_or_bfcref_p (const_tree ref
, bool *type_changing_p
= NULL
)
1034 while (handled_component_p (ref
))
1036 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
1037 || (TREE_CODE (ref
) == COMPONENT_REF
1038 && DECL_BIT_FIELD (TREE_OPERAND (ref
, 1))))
1040 if (type_changing_p
)
1041 *type_changing_p
= true;
1044 ref
= TREE_OPERAND (ref
, 0);
1047 if (!type_changing_p
1048 || TREE_CODE (ref
) != MEM_REF
1049 || TREE_CODE (TREE_OPERAND (ref
, 0)) != ADDR_EXPR
)
1052 tree mem
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
1053 if (TYPE_MAIN_VARIANT (TREE_TYPE (ref
))
1054 != TYPE_MAIN_VARIANT (TREE_TYPE (mem
)))
1055 *type_changing_p
= true;
1060 /* Search the given tree for a declaration by skipping handled components and
1061 exclude it from the candidates. */
1064 disqualify_base_of_expr (tree t
, const char *reason
)
1066 t
= get_base_address (t
);
1067 if (t
&& DECL_P (t
))
1068 disqualify_candidate (t
, reason
);
1071 /* Scan expression EXPR and create access structures for all accesses to
1072 candidates for scalarization. Return the created access or NULL if none is
1075 static struct access
*
1076 build_access_from_expr_1 (tree expr
, gimple
*stmt
, bool write
)
1078 struct access
*ret
= NULL
;
1081 if (TREE_CODE (expr
) == BIT_FIELD_REF
1082 || TREE_CODE (expr
) == IMAGPART_EXPR
1083 || TREE_CODE (expr
) == REALPART_EXPR
)
1085 expr
= TREE_OPERAND (expr
, 0);
1089 partial_ref
= false;
1091 if (storage_order_barrier_p (expr
))
1093 disqualify_base_of_expr (expr
, "storage order barrier.");
1097 /* We need to dive through V_C_Es in order to get the size of its parameter
1098 and not the result type. Ada produces such statements. We are also
1099 capable of handling the topmost V_C_E but not any of those buried in other
1100 handled components. */
1101 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
1102 expr
= TREE_OPERAND (expr
, 0);
1104 if (contains_view_convert_expr_p (expr
))
1106 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
1110 if (TREE_THIS_VOLATILE (expr
))
1112 disqualify_base_of_expr (expr
, "part of a volatile reference.");
1116 switch (TREE_CODE (expr
))
1119 if (TREE_CODE (TREE_OPERAND (expr
, 0)) != ADDR_EXPR
)
1127 case ARRAY_RANGE_REF
:
1128 ret
= create_access (expr
, stmt
, write
);
1135 if (write
&& partial_ref
&& ret
)
1136 ret
->grp_partial_lhs
= 1;
1141 /* Scan expression EXPR and create access structures for all accesses to
1142 candidates for scalarization. Return true if any access has been inserted.
1143 STMT must be the statement from which the expression is taken, WRITE must be
1144 true if the expression is a store and false otherwise. */
1147 build_access_from_expr (tree expr
, gimple
*stmt
, bool write
)
1149 struct access
*access
;
1151 access
= build_access_from_expr_1 (expr
, stmt
, write
);
1154 /* This means the aggregate is accesses as a whole in a way other than an
1155 assign statement and thus cannot be removed even if we had a scalar
1156 replacement for everything. */
1157 if (cannot_scalarize_away_bitmap
)
1158 bitmap_set_bit (cannot_scalarize_away_bitmap
, DECL_UID (access
->base
));
1164 /* Return the single non-EH successor edge of BB or NULL if there is none or
1168 single_non_eh_succ (basic_block bb
)
1173 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1174 if (!(e
->flags
& EDGE_EH
))
1184 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1185 there is no alternative spot where to put statements SRA might need to
1186 generate after it. The spot we are looking for is an edge leading to a
1187 single non-EH successor, if it exists and is indeed single. RHS may be
1188 NULL, in that case ignore it. */
1191 disqualify_if_bad_bb_terminating_stmt (gimple
*stmt
, tree lhs
, tree rhs
)
1193 if (stmt_ends_bb_p (stmt
))
1195 if (single_non_eh_succ (gimple_bb (stmt
)))
1198 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
1200 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
1206 /* Return true if the nature of BASE is such that it contains data even if
1207 there is no write to it in the function. */
1210 comes_initialized_p (tree base
)
1212 return TREE_CODE (base
) == PARM_DECL
|| constant_decl_p (base
);
1215 /* Scan expressions occurring in STMT, create access structures for all accesses
1216 to candidates for scalarization and remove those candidates which occur in
1217 statements or expressions that prevent them from being split apart. Return
1218 true if any access has been inserted. */
1221 build_accesses_from_assign (gimple
*stmt
)
1224 struct access
*lacc
, *racc
;
1226 if (!gimple_assign_single_p (stmt
)
1227 /* Scope clobbers don't influence scalarization. */
1228 || gimple_clobber_p (stmt
))
1231 lhs
= gimple_assign_lhs (stmt
);
1232 rhs
= gimple_assign_rhs1 (stmt
);
1234 if (disqualify_if_bad_bb_terminating_stmt (stmt
, lhs
, rhs
))
1237 racc
= build_access_from_expr_1 (rhs
, stmt
, false);
1238 lacc
= build_access_from_expr_1 (lhs
, stmt
, true);
1242 lacc
->grp_assignment_write
= 1;
1243 if (storage_order_barrier_p (rhs
))
1244 lacc
->grp_unscalarizable_region
= 1;
1246 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (lacc
->type
))
1248 bool type_changing_p
= false;
1249 contains_vce_or_bfcref_p (lhs
, &type_changing_p
);
1250 if (type_changing_p
)
1251 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1252 DECL_UID (lacc
->base
));
1258 racc
->grp_assignment_read
= 1;
1259 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (racc
->type
))
1261 bool type_changing_p
= false;
1262 contains_vce_or_bfcref_p (rhs
, &type_changing_p
);
1264 if (type_changing_p
|| gimple_has_volatile_ops (stmt
))
1265 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1266 DECL_UID (racc
->base
));
1268 bitmap_set_bit (should_scalarize_away_bitmap
,
1269 DECL_UID (racc
->base
));
1271 if (storage_order_barrier_p (lhs
))
1272 racc
->grp_unscalarizable_region
= 1;
1276 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1277 && !lacc
->grp_unscalarizable_region
1278 && !racc
->grp_unscalarizable_region
1279 && AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
1280 && lacc
->size
== racc
->size
1281 && useless_type_conversion_p (lacc
->type
, racc
->type
))
1283 struct assign_link
*link
;
1285 link
= assign_link_pool
.allocate ();
1286 memset (link
, 0, sizeof (struct assign_link
));
1290 add_link_to_rhs (racc
, link
);
1291 add_link_to_lhs (lacc
, link
);
1292 add_access_to_rhs_work_queue (racc
);
1293 add_access_to_lhs_work_queue (lacc
);
1295 /* Let's delay marking the areas as written until propagation of accesses
1296 across link, unless the nature of rhs tells us that its data comes
1298 if (!comes_initialized_p (racc
->base
))
1299 lacc
->write
= false;
1302 return lacc
|| racc
;
1305 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1306 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1309 asm_visit_addr (gimple
*, tree op
, tree
, void *)
1311 op
= get_base_address (op
);
1314 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
1319 /* Scan function and look for interesting expressions and create access
1320 structures for them. Return true iff any access is created. */
1323 scan_function (void)
1328 FOR_EACH_BB_FN (bb
, cfun
)
1330 gimple_stmt_iterator gsi
;
1331 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1333 gimple
*stmt
= gsi_stmt (gsi
);
1337 switch (gimple_code (stmt
))
1340 t
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1342 ret
|= build_access_from_expr (t
, stmt
, false);
1346 ret
|= build_accesses_from_assign (stmt
);
1350 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1351 ret
|= build_access_from_expr (gimple_call_arg (stmt
, i
),
1354 t
= gimple_call_lhs (stmt
);
1355 if (t
&& !disqualify_if_bad_bb_terminating_stmt (stmt
, t
, NULL
))
1356 ret
|= build_access_from_expr (t
, stmt
, true);
1361 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1362 walk_stmt_load_store_addr_ops (asm_stmt
, NULL
, NULL
, NULL
,
1364 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
1366 t
= TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
1367 ret
|= build_access_from_expr (t
, asm_stmt
, false);
1369 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
1371 t
= TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
1372 ret
|= build_access_from_expr (t
, asm_stmt
, true);
1386 /* Helper of QSORT function. There are pointers to accesses in the array. An
1387 access is considered smaller than another if it has smaller offset or if the
1388 offsets are the same but is size is bigger. */
1391 compare_access_positions (const void *a
, const void *b
)
1393 const access_p
*fp1
= (const access_p
*) a
;
1394 const access_p
*fp2
= (const access_p
*) b
;
1395 const access_p f1
= *fp1
;
1396 const access_p f2
= *fp2
;
1398 if (f1
->offset
!= f2
->offset
)
1399 return f1
->offset
< f2
->offset
? -1 : 1;
1401 if (f1
->size
== f2
->size
)
1403 if (f1
->type
== f2
->type
)
1405 /* Put any non-aggregate type before any aggregate type. */
1406 else if (!is_gimple_reg_type (f1
->type
)
1407 && is_gimple_reg_type (f2
->type
))
1409 else if (is_gimple_reg_type (f1
->type
)
1410 && !is_gimple_reg_type (f2
->type
))
1412 /* Put any complex or vector type before any other scalar type. */
1413 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1414 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1415 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1416 || TREE_CODE (f2
->type
) == VECTOR_TYPE
))
1418 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1419 || TREE_CODE (f1
->type
) == VECTOR_TYPE
)
1420 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1421 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1423 /* Put any integral type before any non-integral type. When splicing, we
1424 make sure that those with insufficient precision and occupying the
1425 same space are not scalarized. */
1426 else if (INTEGRAL_TYPE_P (f1
->type
)
1427 && !INTEGRAL_TYPE_P (f2
->type
))
1429 else if (!INTEGRAL_TYPE_P (f1
->type
)
1430 && INTEGRAL_TYPE_P (f2
->type
))
1432 /* Put the integral type with the bigger precision first. */
1433 else if (INTEGRAL_TYPE_P (f1
->type
)
1434 && INTEGRAL_TYPE_P (f2
->type
)
1435 && (TYPE_PRECISION (f2
->type
) != TYPE_PRECISION (f1
->type
)))
1436 return TYPE_PRECISION (f2
->type
) - TYPE_PRECISION (f1
->type
);
1437 /* Stabilize the sort. */
1438 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1441 /* We want the bigger accesses first, thus the opposite operator in the next
1443 return f1
->size
> f2
->size
? -1 : 1;
1447 /* Append a name of the declaration to the name obstack. A helper function for
1451 make_fancy_decl_name (tree decl
)
1455 tree name
= DECL_NAME (decl
);
1457 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1458 IDENTIFIER_LENGTH (name
));
1461 sprintf (buffer
, "D%u", DECL_UID (decl
));
1462 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1466 /* Helper for make_fancy_name. */
1469 make_fancy_name_1 (tree expr
)
1476 make_fancy_decl_name (expr
);
1480 switch (TREE_CODE (expr
))
1483 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1484 obstack_1grow (&name_obstack
, '$');
1485 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1489 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1490 obstack_1grow (&name_obstack
, '$');
1491 /* Arrays with only one element may not have a constant as their
1493 index
= TREE_OPERAND (expr
, 1);
1494 if (TREE_CODE (index
) != INTEGER_CST
)
1496 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1497 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1501 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1505 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1506 if (!integer_zerop (TREE_OPERAND (expr
, 1)))
1508 obstack_1grow (&name_obstack
, '$');
1509 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
,
1510 TREE_INT_CST_LOW (TREE_OPERAND (expr
, 1)));
1511 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1518 gcc_unreachable (); /* we treat these as scalars. */
1525 /* Create a human readable name for replacement variable of ACCESS. */
1528 make_fancy_name (tree expr
)
1530 make_fancy_name_1 (expr
);
1531 obstack_1grow (&name_obstack
, '\0');
1532 return XOBFINISH (&name_obstack
, char *);
1535 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1536 EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1537 something for which get_addr_base_and_unit_offset returns NULL, gsi must
1538 be non-NULL and is used to insert new statements either before or below
1539 the current one as specified by INSERT_AFTER. This function is not capable
1540 of handling bitfields. */
1543 build_ref_for_offset (location_t loc
, tree base
, poly_int64 offset
,
1544 bool reverse
, tree exp_type
, gimple_stmt_iterator
*gsi
,
1547 tree prev_base
= base
;
1550 poly_int64 base_offset
;
1551 unsigned HOST_WIDE_INT misalign
;
1554 /* Preserve address-space information. */
1555 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (base
));
1556 if (as
!= TYPE_ADDR_SPACE (exp_type
))
1557 exp_type
= build_qualified_type (exp_type
,
1558 TYPE_QUALS (exp_type
)
1559 | ENCODE_QUAL_ADDR_SPACE (as
));
1561 poly_int64 byte_offset
= exact_div (offset
, BITS_PER_UNIT
);
1562 get_object_alignment_1 (base
, &align
, &misalign
);
1563 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1565 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1566 offset such as array[var_index]. */
1572 gcc_checking_assert (gsi
);
1573 tmp
= make_ssa_name (build_pointer_type (TREE_TYPE (prev_base
)));
1574 addr
= build_fold_addr_expr (unshare_expr (prev_base
));
1575 STRIP_USELESS_TYPE_CONVERSION (addr
);
1576 stmt
= gimple_build_assign (tmp
, addr
);
1577 gimple_set_location (stmt
, loc
);
1579 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
1581 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1583 off
= build_int_cst (reference_alias_ptr_type (prev_base
), byte_offset
);
1586 else if (TREE_CODE (base
) == MEM_REF
)
1588 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1589 base_offset
+ byte_offset
);
1590 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1591 base
= unshare_expr (TREE_OPERAND (base
, 0));
1595 off
= build_int_cst (reference_alias_ptr_type (prev_base
),
1596 base_offset
+ byte_offset
);
1597 base
= build_fold_addr_expr (unshare_expr (base
));
1600 unsigned int align_bound
= known_alignment (misalign
+ offset
);
1601 if (align_bound
!= 0)
1602 align
= MIN (align
, align_bound
);
1603 if (align
!= TYPE_ALIGN (exp_type
))
1604 exp_type
= build_aligned_type (exp_type
, align
);
1606 mem_ref
= fold_build2_loc (loc
, MEM_REF
, exp_type
, base
, off
);
1607 REF_REVERSE_STORAGE_ORDER (mem_ref
) = reverse
;
1608 if (TREE_THIS_VOLATILE (prev_base
))
1609 TREE_THIS_VOLATILE (mem_ref
) = 1;
1610 if (TREE_SIDE_EFFECTS (prev_base
))
1611 TREE_SIDE_EFFECTS (mem_ref
) = 1;
1615 /* Construct and return a memory reference that is equal to a portion of
1616 MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1619 build_reconstructed_reference (location_t
, tree base
, struct access
*model
)
1621 tree expr
= model
->expr
, prev_expr
= NULL
;
1622 while (!types_compatible_p (TREE_TYPE (expr
), TREE_TYPE (base
)))
1624 if (!handled_component_p (expr
))
1627 expr
= TREE_OPERAND (expr
, 0);
1630 /* Guard against broken VIEW_CONVERT_EXPRs... */
1634 TREE_OPERAND (prev_expr
, 0) = base
;
1635 tree ref
= unshare_expr (model
->expr
);
1636 TREE_OPERAND (prev_expr
, 0) = expr
;
1640 /* Construct a memory reference to a part of an aggregate BASE at the given
1641 OFFSET and of the same type as MODEL. In case this is a reference to a
1642 bit-field, the function will replicate the last component_ref of model's
1643 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1644 build_ref_for_offset. */
1647 build_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1648 struct access
*model
, gimple_stmt_iterator
*gsi
,
1651 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1652 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1654 /* This access represents a bit-field. */
1655 tree t
, exp_type
, fld
= TREE_OPERAND (model
->expr
, 1);
1657 offset
-= int_bit_position (fld
);
1658 exp_type
= TREE_TYPE (TREE_OPERAND (model
->expr
, 0));
1659 t
= build_ref_for_offset (loc
, base
, offset
, model
->reverse
, exp_type
,
1661 /* The flag will be set on the record type. */
1662 REF_REVERSE_STORAGE_ORDER (t
) = 0;
1663 return fold_build3_loc (loc
, COMPONENT_REF
, TREE_TYPE (fld
), t
, fld
,
1669 if (model
->grp_same_access_path
1670 && !TREE_THIS_VOLATILE (base
)
1671 && (TYPE_ADDR_SPACE (TREE_TYPE (base
))
1672 == TYPE_ADDR_SPACE (TREE_TYPE (model
->expr
)))
1673 && offset
<= model
->offset
1674 /* build_reconstructed_reference can still fail if we have already
1675 massaged BASE because of another type incompatibility. */
1676 && (res
= build_reconstructed_reference (loc
, base
, model
)))
1679 return build_ref_for_offset (loc
, base
, offset
, model
->reverse
,
1680 model
->type
, gsi
, insert_after
);
1684 /* Attempt to build a memory reference that we could but into a gimple
1685 debug_bind statement. Similar to build_ref_for_model but punts if it has to
1686 create statements and return s NULL instead. This function also ignores
1687 alignment issues and so its results should never end up in non-debug
1691 build_debug_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1692 struct access
*model
)
1694 poly_int64 base_offset
;
1697 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1698 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1701 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1704 if (TREE_CODE (base
) == MEM_REF
)
1706 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1707 base_offset
+ offset
/ BITS_PER_UNIT
);
1708 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1709 base
= unshare_expr (TREE_OPERAND (base
, 0));
1713 off
= build_int_cst (reference_alias_ptr_type (base
),
1714 base_offset
+ offset
/ BITS_PER_UNIT
);
1715 base
= build_fold_addr_expr (unshare_expr (base
));
1718 return fold_build2_loc (loc
, MEM_REF
, model
->type
, base
, off
);
1721 /* Construct a memory reference consisting of component_refs and array_refs to
1722 a part of an aggregate *RES (which is of type TYPE). The requested part
1723 should have type EXP_TYPE at be the given OFFSET. This function might not
1724 succeed, it returns true when it does and only then *RES points to something
1725 meaningful. This function should be used only to build expressions that we
1726 might need to present to user (e.g. in warnings). In all other situations,
1727 build_ref_for_model or build_ref_for_offset should be used instead. */
1730 build_user_friendly_ref_for_offset (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1736 tree tr_size
, index
, minidx
;
1737 HOST_WIDE_INT el_size
;
1739 if (offset
== 0 && exp_type
1740 && types_compatible_p (exp_type
, type
))
1743 switch (TREE_CODE (type
))
1746 case QUAL_UNION_TYPE
:
1748 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1750 HOST_WIDE_INT pos
, size
;
1751 tree tr_pos
, expr
, *expr_ptr
;
1753 if (TREE_CODE (fld
) != FIELD_DECL
)
1756 tr_pos
= bit_position (fld
);
1757 if (!tr_pos
|| !tree_fits_uhwi_p (tr_pos
))
1759 pos
= tree_to_uhwi (tr_pos
);
1760 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1761 tr_size
= DECL_SIZE (fld
);
1762 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1764 size
= tree_to_uhwi (tr_size
);
1770 else if (pos
> offset
|| (pos
+ size
) <= offset
)
1773 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1776 if (build_user_friendly_ref_for_offset (expr_ptr
, TREE_TYPE (fld
),
1777 offset
- pos
, exp_type
))
1786 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1787 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1789 el_size
= tree_to_uhwi (tr_size
);
1791 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1792 if (TREE_CODE (minidx
) != INTEGER_CST
|| el_size
== 0)
1794 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1795 if (!integer_zerop (minidx
))
1796 index
= int_const_binop (PLUS_EXPR
, index
, minidx
);
1797 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1798 NULL_TREE
, NULL_TREE
);
1799 offset
= offset
% el_size
;
1800 type
= TREE_TYPE (type
);
1815 /* Print message to dump file why a variable was rejected. */
1818 reject (tree var
, const char *msg
)
1820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1822 fprintf (dump_file
, "Rejected (%d): %s: ", DECL_UID (var
), msg
);
1823 print_generic_expr (dump_file
, var
);
1824 fprintf (dump_file
, "\n");
1828 /* Return true if VAR is a candidate for SRA. */
1831 maybe_add_sra_candidate (tree var
)
1833 tree type
= TREE_TYPE (var
);
1837 if (!AGGREGATE_TYPE_P (type
))
1839 reject (var
, "not aggregate");
1842 /* Allow constant-pool entries that "need to live in memory". */
1843 if (needs_to_live_in_memory (var
) && !constant_decl_p (var
))
1845 reject (var
, "needs to live in memory");
1848 if (TREE_THIS_VOLATILE (var
))
1850 reject (var
, "is volatile");
1853 if (!COMPLETE_TYPE_P (type
))
1855 reject (var
, "has incomplete type");
1858 if (!tree_fits_uhwi_p (TYPE_SIZE (type
)))
1860 reject (var
, "type size not fixed");
1863 if (tree_to_uhwi (TYPE_SIZE (type
)) == 0)
1865 reject (var
, "type size is zero");
1868 if (type_internals_preclude_sra_p (type
, &msg
))
1873 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1874 we also want to schedule it rather late. Thus we ignore it in
1876 (sra_mode
== SRA_MODE_EARLY_INTRA
1877 && is_va_list_type (type
)))
1879 reject (var
, "is va_list");
1883 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1884 slot
= candidates
->find_slot_with_hash (var
, DECL_UID (var
), INSERT
);
1887 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1889 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1890 print_generic_expr (dump_file
, var
);
1891 fprintf (dump_file
, "\n");
1897 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1898 those with type which is suitable for scalarization. */
1901 find_var_candidates (void)
1907 for (parm
= DECL_ARGUMENTS (current_function_decl
);
1909 parm
= DECL_CHAIN (parm
))
1910 ret
|= maybe_add_sra_candidate (parm
);
1912 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
1917 ret
|= maybe_add_sra_candidate (var
);
1923 /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
1924 ending either with a DECL or a MEM_REF with zero offset. */
1927 path_comparable_for_same_access (tree expr
)
1929 while (handled_component_p (expr
))
1931 if (TREE_CODE (expr
) == ARRAY_REF
)
1933 /* SSA name indices can occur here too when the array is of sie one.
1934 But we cannot just re-use array_refs with SSA names elsewhere in
1935 the function, so disallow non-constant indices. TODO: Remove this
1936 limitation after teaching build_reconstructed_reference to replace
1937 the index with the index type lower bound. */
1938 if (TREE_CODE (TREE_OPERAND (expr
, 1)) != INTEGER_CST
)
1941 expr
= TREE_OPERAND (expr
, 0);
1944 if (TREE_CODE (expr
) == MEM_REF
)
1946 if (!zerop (TREE_OPERAND (expr
, 1)))
1950 gcc_assert (DECL_P (expr
));
1955 /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
1956 true if the chain of these handled components are exactly the same as EXP2
1957 and the expression under them is the same DECL or an equivalent MEM_REF.
1958 The reference picked by compare_access_positions must go to EXP1. */
1961 same_access_path_p (tree exp1
, tree exp2
)
1963 if (TREE_CODE (exp1
) != TREE_CODE (exp2
))
1965 /* Special case single-field structures loaded sometimes as the field
1966 and sometimes as the structure. If the field is of a scalar type,
1967 compare_access_positions will put it into exp1.
1969 TODO: The gimple register type condition can be removed if teach
1970 compare_access_positions to put inner types first. */
1971 if (is_gimple_reg_type (TREE_TYPE (exp1
))
1972 && TREE_CODE (exp1
) == COMPONENT_REF
1973 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1
, 0)))
1974 == TYPE_MAIN_VARIANT (TREE_TYPE (exp2
))))
1975 exp1
= TREE_OPERAND (exp1
, 0);
1980 if (!operand_equal_p (exp1
, exp2
, OEP_ADDRESS_OF
))
1986 /* Sort all accesses for the given variable, check for partial overlaps and
1987 return NULL if there are any. If there are none, pick a representative for
1988 each combination of offset and size and create a linked list out of them.
1989 Return the pointer to the first representative and make sure it is the first
1990 one in the vector of accesses. */
1992 static struct access
*
1993 sort_and_splice_var_accesses (tree var
)
1995 int i
, j
, access_count
;
1996 struct access
*res
, **prev_acc_ptr
= &res
;
1997 vec
<access_p
> *access_vec
;
1999 HOST_WIDE_INT low
= -1, high
= 0;
2001 access_vec
= get_base_access_vector (var
);
2004 access_count
= access_vec
->length ();
2006 /* Sort by <OFFSET, SIZE>. */
2007 access_vec
->qsort (compare_access_positions
);
2010 while (i
< access_count
)
2012 struct access
*access
= (*access_vec
)[i
];
2013 bool grp_write
= access
->write
;
2014 bool grp_read
= !access
->write
;
2015 bool grp_scalar_write
= access
->write
2016 && is_gimple_reg_type (access
->type
);
2017 bool grp_scalar_read
= !access
->write
2018 && is_gimple_reg_type (access
->type
);
2019 bool grp_assignment_read
= access
->grp_assignment_read
;
2020 bool grp_assignment_write
= access
->grp_assignment_write
;
2021 bool multiple_scalar_reads
= false;
2022 bool grp_partial_lhs
= access
->grp_partial_lhs
;
2023 bool first_scalar
= is_gimple_reg_type (access
->type
);
2024 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
2025 bool grp_same_access_path
= true;
2026 bool bf_non_full_precision
2027 = (INTEGRAL_TYPE_P (access
->type
)
2028 && TYPE_PRECISION (access
->type
) != access
->size
2029 && TREE_CODE (access
->expr
) == COMPONENT_REF
2030 && DECL_BIT_FIELD (TREE_OPERAND (access
->expr
, 1)));
2032 if (first
|| access
->offset
>= high
)
2035 low
= access
->offset
;
2036 high
= access
->offset
+ access
->size
;
2038 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
2041 gcc_assert (access
->offset
>= low
2042 && access
->offset
+ access
->size
<= high
);
2044 grp_same_access_path
= path_comparable_for_same_access (access
->expr
);
2047 while (j
< access_count
)
2049 struct access
*ac2
= (*access_vec
)[j
];
2050 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
2055 grp_scalar_write
= (grp_scalar_write
2056 || is_gimple_reg_type (ac2
->type
));
2061 if (is_gimple_reg_type (ac2
->type
))
2063 if (grp_scalar_read
)
2064 multiple_scalar_reads
= true;
2066 grp_scalar_read
= true;
2069 grp_assignment_read
|= ac2
->grp_assignment_read
;
2070 grp_assignment_write
|= ac2
->grp_assignment_write
;
2071 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
2072 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
2073 relink_to_new_repr (access
, ac2
);
2075 /* If there are both aggregate-type and scalar-type accesses with
2076 this combination of size and offset, the comparison function
2077 should have put the scalars first. */
2078 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
2079 /* It also prefers integral types to non-integral. However, when the
2080 precision of the selected type does not span the entire area and
2081 should also be used for a non-integer (i.e. float), we must not
2082 let that happen. Normally analyze_access_subtree expands the type
2083 to cover the entire area but for bit-fields it doesn't. */
2084 if (bf_non_full_precision
&& !INTEGRAL_TYPE_P (ac2
->type
))
2086 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2088 fprintf (dump_file
, "Cannot scalarize the following access "
2089 "because insufficient precision integer type was "
2091 dump_access (dump_file
, access
, false);
2093 unscalarizable_region
= true;
2096 if (grp_same_access_path
2097 && !same_access_path_p (access
->expr
, ac2
->expr
))
2098 grp_same_access_path
= false;
2100 ac2
->group_representative
= access
;
2106 access
->group_representative
= access
;
2107 access
->grp_write
= grp_write
;
2108 access
->grp_read
= grp_read
;
2109 access
->grp_scalar_read
= grp_scalar_read
;
2110 access
->grp_scalar_write
= grp_scalar_write
;
2111 access
->grp_assignment_read
= grp_assignment_read
;
2112 access
->grp_assignment_write
= grp_assignment_write
;
2113 access
->grp_hint
= multiple_scalar_reads
&& !constant_decl_p (var
);
2114 access
->grp_partial_lhs
= grp_partial_lhs
;
2115 access
->grp_unscalarizable_region
= unscalarizable_region
;
2116 access
->grp_same_access_path
= grp_same_access_path
;
2118 *prev_acc_ptr
= access
;
2119 prev_acc_ptr
= &access
->next_grp
;
2122 gcc_assert (res
== (*access_vec
)[0]);
2126 /* Create a variable for the given ACCESS which determines the type, name and a
2127 few other properties. Return the variable declaration and store it also to
2128 ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2129 default-definition SSA name on on in order to facilitate an uninitialized
2130 warning. It is used instead of the actual ACCESS type if that is not of a
2131 gimple register type. */
2134 create_access_replacement (struct access
*access
, tree reg_type
= NULL_TREE
)
2138 tree type
= access
->type
;
2139 if (reg_type
&& !is_gimple_reg_type (type
))
2142 if (access
->grp_to_be_debug_replaced
)
2144 repl
= create_tmp_var_raw (access
->type
);
2145 DECL_CONTEXT (repl
) = current_function_decl
;
2148 /* Drop any special alignment on the type if it's not on the main
2149 variant. This avoids issues with weirdo ABIs like AAPCS. */
2150 repl
= create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type
),
2151 TYPE_QUALS (type
)), "SR");
2152 if (TREE_CODE (type
) == COMPLEX_TYPE
2153 || TREE_CODE (type
) == VECTOR_TYPE
)
2155 if (!access
->grp_partial_lhs
)
2156 DECL_GIMPLE_REG_P (repl
) = 1;
2158 else if (access
->grp_partial_lhs
2159 && is_gimple_reg_type (type
))
2160 TREE_ADDRESSABLE (repl
) = 1;
2162 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
2163 DECL_ARTIFICIAL (repl
) = 1;
2164 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
2166 if (DECL_NAME (access
->base
)
2167 && !DECL_IGNORED_P (access
->base
)
2168 && !DECL_ARTIFICIAL (access
->base
))
2170 char *pretty_name
= make_fancy_name (access
->expr
);
2171 tree debug_expr
= unshare_expr_without_location (access
->expr
), d
;
2174 DECL_NAME (repl
) = get_identifier (pretty_name
);
2175 DECL_NAMELESS (repl
) = 1;
2176 obstack_free (&name_obstack
, pretty_name
);
2178 /* Get rid of any SSA_NAMEs embedded in debug_expr,
2179 as DECL_DEBUG_EXPR isn't considered when looking for still
2180 used SSA_NAMEs and thus they could be freed. All debug info
2181 generation cares is whether something is constant or variable
2182 and that get_ref_base_and_extent works properly on the
2183 expression. It cannot handle accesses at a non-constant offset
2184 though, so just give up in those cases. */
2185 for (d
= debug_expr
;
2186 !fail
&& (handled_component_p (d
) || TREE_CODE (d
) == MEM_REF
);
2187 d
= TREE_OPERAND (d
, 0))
2188 switch (TREE_CODE (d
))
2191 case ARRAY_RANGE_REF
:
2192 if (TREE_OPERAND (d
, 1)
2193 && TREE_CODE (TREE_OPERAND (d
, 1)) != INTEGER_CST
)
2195 if (TREE_OPERAND (d
, 3)
2196 && TREE_CODE (TREE_OPERAND (d
, 3)) != INTEGER_CST
)
2200 if (TREE_OPERAND (d
, 2)
2201 && TREE_CODE (TREE_OPERAND (d
, 2)) != INTEGER_CST
)
2205 if (TREE_CODE (TREE_OPERAND (d
, 0)) != ADDR_EXPR
)
2208 d
= TREE_OPERAND (d
, 0);
2215 SET_DECL_DEBUG_EXPR (repl
, debug_expr
);
2216 DECL_HAS_DEBUG_EXPR_P (repl
) = 1;
2218 if (access
->grp_no_warning
)
2219 TREE_NO_WARNING (repl
) = 1;
2221 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
2224 TREE_NO_WARNING (repl
) = 1;
2228 if (access
->grp_to_be_debug_replaced
)
2230 fprintf (dump_file
, "Created a debug-only replacement for ");
2231 print_generic_expr (dump_file
, access
->base
);
2232 fprintf (dump_file
, " offset: %u, size: %u\n",
2233 (unsigned) access
->offset
, (unsigned) access
->size
);
2237 fprintf (dump_file
, "Created a replacement for ");
2238 print_generic_expr (dump_file
, access
->base
);
2239 fprintf (dump_file
, " offset: %u, size: %u: ",
2240 (unsigned) access
->offset
, (unsigned) access
->size
);
2241 print_generic_expr (dump_file
, repl
);
2242 fprintf (dump_file
, "\n");
2245 sra_stats
.replacements
++;
2250 /* Return ACCESS scalar replacement, which must exist. */
2253 get_access_replacement (struct access
*access
)
2255 gcc_checking_assert (access
->replacement_decl
);
2256 return access
->replacement_decl
;
2260 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2261 linked list along the way. Stop when *ACCESS is NULL or the access pointed
2262 to it is not "within" the root. Return false iff some accesses partially
2266 build_access_subtree (struct access
**access
)
2268 struct access
*root
= *access
, *last_child
= NULL
;
2269 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2271 *access
= (*access
)->next_grp
;
2272 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
2275 root
->first_child
= *access
;
2277 last_child
->next_sibling
= *access
;
2278 last_child
= *access
;
2279 (*access
)->parent
= root
;
2280 (*access
)->grp_write
|= root
->grp_write
;
2282 if (!build_access_subtree (access
))
2286 if (*access
&& (*access
)->offset
< limit
)
2292 /* Build a tree of access representatives, ACCESS is the pointer to the first
2293 one, others are linked in a list by the next_grp field. Return false iff
2294 some accesses partially overlap. */
2297 build_access_trees (struct access
*access
)
2301 struct access
*root
= access
;
2303 if (!build_access_subtree (&access
))
2305 root
->next_grp
= access
;
2310 /* Traverse the access forest where ROOT is the first root and verify that
2311 various important invariants hold true. */
2314 verify_sra_access_forest (struct access
*root
)
2316 struct access
*access
= root
;
2317 tree first_base
= root
->base
;
2318 gcc_assert (DECL_P (first_base
));
2321 gcc_assert (access
->base
== first_base
);
2323 gcc_assert (access
->offset
>= access
->parent
->offset
2324 && access
->size
<= access
->parent
->size
);
2325 if (access
->next_sibling
)
2326 gcc_assert (access
->next_sibling
->offset
2327 >= access
->offset
+ access
->size
);
2329 poly_int64 poffset
, psize
, pmax_size
;
2331 tree base
= get_ref_base_and_extent (access
->expr
, &poffset
, &psize
,
2332 &pmax_size
, &reverse
);
2333 HOST_WIDE_INT offset
, size
, max_size
;
2334 if (!poffset
.is_constant (&offset
)
2335 || !psize
.is_constant (&size
)
2336 || !pmax_size
.is_constant (&max_size
))
2338 gcc_assert (base
== first_base
);
2339 gcc_assert (offset
== access
->offset
);
2340 gcc_assert (access
->grp_unscalarizable_region
2341 || size
== max_size
);
2342 gcc_assert (max_size
== access
->size
);
2343 gcc_assert (reverse
== access
->reverse
);
2345 if (access
->first_child
)
2347 gcc_assert (access
->first_child
->parent
== access
);
2348 access
= access
->first_child
;
2350 else if (access
->next_sibling
)
2352 gcc_assert (access
->next_sibling
->parent
== access
->parent
);
2353 access
= access
->next_sibling
;
2357 while (access
->parent
&& !access
->next_sibling
)
2358 access
= access
->parent
;
2359 if (access
->next_sibling
)
2360 access
= access
->next_sibling
;
2363 gcc_assert (access
== root
);
2364 root
= root
->next_grp
;
2372 /* Verify access forests of all candidates with accesses by calling
2373 verify_access_forest on each on them. */
2376 verify_all_sra_access_forests (void)
2380 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
2382 tree var
= candidate (i
);
2383 struct access
*access
= get_first_repr_for_decl (var
);
2386 gcc_assert (access
->base
== var
);
2387 verify_sra_access_forest (access
);
2392 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2396 expr_with_var_bounded_array_refs_p (tree expr
)
2398 while (handled_component_p (expr
))
2400 if (TREE_CODE (expr
) == ARRAY_REF
2401 && !tree_fits_shwi_p (array_ref_low_bound (expr
)))
2403 expr
= TREE_OPERAND (expr
, 0);
2408 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2409 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2410 is set, we are totally scalarizing the aggregate. Also set all sorts of
2411 access flags appropriately along the way, notably always set grp_read and
2412 grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2415 Creating a replacement for a scalar access is considered beneficial if its
2416 grp_hint ot TOTALLY is set (this means either that there is more than one
2417 direct read access or that we are attempting total scalarization) or
2418 according to the following table:
2420 Access written to through a scalar type (once or more times)
2422 | Written to in an assignment statement
2424 | | Access read as scalar _once_
2426 | | | Read in an assignment statement
2428 | | | | Scalarize Comment
2429 -----------------------------------------------------------------------------
2430 0 0 0 0 No access for the scalar
2431 0 0 0 1 No access for the scalar
2432 0 0 1 0 No Single read - won't help
2433 0 0 1 1 No The same case
2434 0 1 0 0 No access for the scalar
2435 0 1 0 1 No access for the scalar
2436 0 1 1 0 Yes s = *g; return s.i;
2437 0 1 1 1 Yes The same case as above
2438 1 0 0 0 No Won't help
2439 1 0 0 1 Yes s.i = 1; *g = s;
2440 1 0 1 0 Yes s.i = 5; g = s.i;
2441 1 0 1 1 Yes The same case as above
2442 1 1 0 0 No Won't help.
2443 1 1 0 1 Yes s.i = 1; *g = s;
2444 1 1 1 0 Yes s = *g; return s.i;
2445 1 1 1 1 Yes Any of the above yeses */
2448 analyze_access_subtree (struct access
*root
, struct access
*parent
,
2449 bool allow_replacements
, bool totally
)
2451 struct access
*child
;
2452 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2453 HOST_WIDE_INT covered_to
= root
->offset
;
2454 bool scalar
= is_gimple_reg_type (root
->type
);
2455 bool hole
= false, sth_created
= false;
2459 if (parent
->grp_read
)
2461 if (parent
->grp_assignment_read
)
2462 root
->grp_assignment_read
= 1;
2463 if (parent
->grp_write
)
2464 root
->grp_write
= 1;
2465 if (parent
->grp_assignment_write
)
2466 root
->grp_assignment_write
= 1;
2467 if (!parent
->grp_same_access_path
)
2468 root
->grp_same_access_path
= 0;
2471 if (root
->grp_unscalarizable_region
)
2472 allow_replacements
= false;
2474 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
2475 allow_replacements
= false;
2477 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
2479 hole
|= covered_to
< child
->offset
;
2480 sth_created
|= analyze_access_subtree (child
, root
,
2481 allow_replacements
&& !scalar
,
2484 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
2485 if (child
->grp_covered
)
2486 covered_to
+= child
->size
;
2491 if (allow_replacements
&& scalar
&& !root
->first_child
2492 && (totally
|| !root
->grp_total_scalarization
)
2495 || ((root
->grp_scalar_read
|| root
->grp_assignment_read
)
2496 && (root
->grp_scalar_write
|| root
->grp_assignment_write
))))
2498 /* Always create access replacements that cover the whole access.
2499 For integral types this means the precision has to match.
2500 Avoid assumptions based on the integral type kind, too. */
2501 if (INTEGRAL_TYPE_P (root
->type
)
2502 && (TREE_CODE (root
->type
) != INTEGER_TYPE
2503 || TYPE_PRECISION (root
->type
) != root
->size
)
2504 /* But leave bitfield accesses alone. */
2505 && (TREE_CODE (root
->expr
) != COMPONENT_REF
2506 || !DECL_BIT_FIELD (TREE_OPERAND (root
->expr
, 1))))
2508 tree rt
= root
->type
;
2509 gcc_assert ((root
->offset
% BITS_PER_UNIT
) == 0
2510 && (root
->size
% BITS_PER_UNIT
) == 0);
2511 root
->type
= build_nonstandard_integer_type (root
->size
,
2512 TYPE_UNSIGNED (rt
));
2513 root
->expr
= build_ref_for_offset (UNKNOWN_LOCATION
, root
->base
,
2514 root
->offset
, root
->reverse
,
2515 root
->type
, NULL
, false);
2517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2519 fprintf (dump_file
, "Changing the type of a replacement for ");
2520 print_generic_expr (dump_file
, root
->base
);
2521 fprintf (dump_file
, " offset: %u, size: %u ",
2522 (unsigned) root
->offset
, (unsigned) root
->size
);
2523 fprintf (dump_file
, " to an integer.\n");
2527 root
->grp_to_be_replaced
= 1;
2528 root
->replacement_decl
= create_access_replacement (root
);
2534 if (allow_replacements
2535 && scalar
&& !root
->first_child
2536 && !root
->grp_total_scalarization
2537 && (root
->grp_scalar_write
|| root
->grp_assignment_write
)
2538 && !bitmap_bit_p (cannot_scalarize_away_bitmap
,
2539 DECL_UID (root
->base
)))
2541 gcc_checking_assert (!root
->grp_scalar_read
2542 && !root
->grp_assignment_read
);
2544 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2546 root
->grp_to_be_debug_replaced
= 1;
2547 root
->replacement_decl
= create_access_replacement (root
);
2551 if (covered_to
< limit
)
2553 if (scalar
|| !allow_replacements
)
2554 root
->grp_total_scalarization
= 0;
2557 if (!hole
|| totally
)
2558 root
->grp_covered
= 1;
2559 else if (root
->grp_write
|| comes_initialized_p (root
->base
))
2560 root
->grp_unscalarized_data
= 1; /* not covered and written to */
2564 /* Analyze all access trees linked by next_grp by the means of
2565 analyze_access_subtree. */
2567 analyze_access_trees (struct access
*access
)
2573 if (analyze_access_subtree (access
, NULL
, true,
2574 access
->grp_total_scalarization
))
2576 access
= access
->next_grp
;
2582 /* Return true iff a potential new child of ACC at offset OFFSET and with size
2583 SIZE would conflict with an already existing one. If exactly such a child
2584 already exists in ACC, store a pointer to it in EXACT_MATCH. */
2587 child_would_conflict_in_acc (struct access
*acc
, HOST_WIDE_INT norm_offset
,
2588 HOST_WIDE_INT size
, struct access
**exact_match
)
2590 struct access
*child
;
2592 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
2594 if (child
->offset
== norm_offset
&& child
->size
== size
)
2596 *exact_match
= child
;
2600 if (child
->offset
< norm_offset
+ size
2601 && child
->offset
+ child
->size
> norm_offset
)
2608 /* Create a new child access of PARENT, with all properties just like MODEL
2609 except for its offset and with its grp_write false and grp_read true.
2610 Return the new access or NULL if it cannot be created. Note that this
2611 access is created long after all splicing and sorting, it's not located in
2612 any access vector and is automatically a representative of its group. Set
2613 the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
2615 static struct access
*
2616 create_artificial_child_access (struct access
*parent
, struct access
*model
,
2617 HOST_WIDE_INT new_offset
,
2618 bool set_grp_read
, bool set_grp_write
)
2620 struct access
**child
;
2621 tree expr
= parent
->base
;
2623 gcc_assert (!model
->grp_unscalarizable_region
);
2625 struct access
*access
= access_pool
.allocate ();
2626 memset (access
, 0, sizeof (struct access
));
2627 if (!build_user_friendly_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
2630 access
->grp_no_warning
= true;
2631 expr
= build_ref_for_model (EXPR_LOCATION (parent
->base
), parent
->base
,
2632 new_offset
, model
, NULL
, false);
2635 access
->base
= parent
->base
;
2636 access
->expr
= expr
;
2637 access
->offset
= new_offset
;
2638 access
->size
= model
->size
;
2639 access
->type
= model
->type
;
2640 access
->parent
= parent
;
2641 access
->grp_read
= set_grp_read
;
2642 access
->grp_write
= set_grp_write
;
2643 access
->reverse
= model
->reverse
;
2645 child
= &parent
->first_child
;
2646 while (*child
&& (*child
)->offset
< new_offset
)
2647 child
= &(*child
)->next_sibling
;
2649 access
->next_sibling
= *child
;
2656 /* Beginning with ACCESS, traverse its whole access subtree and mark all
2657 sub-trees as written to. If any of them has not been marked so previously
2658 and has assignment links leading from it, re-enqueue it. */
2661 subtree_mark_written_and_rhs_enqueue (struct access
*access
)
2663 if (access
->grp_write
)
2665 access
->grp_write
= true;
2666 add_access_to_rhs_work_queue (access
);
2668 struct access
*child
;
2669 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2670 subtree_mark_written_and_rhs_enqueue (child
);
2673 /* Propagate subaccesses and grp_write flags of RACC across an assignment link
2674 to LACC. Enqueue sub-accesses as necessary so that the write flag is
2675 propagated transitively. Return true if anything changed. Additionally, if
2676 RACC is a scalar access but LACC is not, change the type of the latter, if
2680 propagate_subaccesses_from_rhs (struct access
*lacc
, struct access
*racc
)
2682 struct access
*rchild
;
2683 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
2686 /* IF the LHS is still not marked as being written to, we only need to do so
2687 if the RHS at this level actually was. */
2688 if (!lacc
->grp_write
)
2690 gcc_checking_assert (!comes_initialized_p (racc
->base
));
2691 if (racc
->grp_write
)
2693 subtree_mark_written_and_rhs_enqueue (lacc
);
2698 if (is_gimple_reg_type (lacc
->type
)
2699 || lacc
->grp_unscalarizable_region
2700 || racc
->grp_unscalarizable_region
)
2702 if (!lacc
->grp_write
)
2705 subtree_mark_written_and_rhs_enqueue (lacc
);
2710 if (is_gimple_reg_type (racc
->type
))
2712 if (!lacc
->grp_write
)
2715 subtree_mark_written_and_rhs_enqueue (lacc
);
2717 if (!lacc
->first_child
&& !racc
->first_child
)
2719 tree t
= lacc
->base
;
2721 lacc
->type
= racc
->type
;
2722 if (build_user_friendly_ref_for_offset (&t
, TREE_TYPE (t
),
2723 lacc
->offset
, racc
->type
))
2726 lacc
->grp_same_access_path
= true;
2730 lacc
->expr
= build_ref_for_model (EXPR_LOCATION (lacc
->base
),
2731 lacc
->base
, lacc
->offset
,
2733 lacc
->grp_no_warning
= true;
2734 lacc
->grp_same_access_path
= false;
2740 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
2742 struct access
*new_acc
= NULL
;
2743 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
2745 if (child_would_conflict_in_acc (lacc
, norm_offset
, rchild
->size
,
2750 if (!new_acc
->grp_write
&& rchild
->grp_write
)
2752 gcc_assert (!lacc
->grp_write
);
2753 subtree_mark_written_and_rhs_enqueue (new_acc
);
2757 rchild
->grp_hint
= 1;
2758 new_acc
->grp_hint
|= new_acc
->grp_read
;
2759 if (rchild
->first_child
2760 && propagate_subaccesses_from_rhs (new_acc
, rchild
))
2763 add_access_to_rhs_work_queue (new_acc
);
2768 if (!lacc
->grp_write
)
2771 subtree_mark_written_and_rhs_enqueue (lacc
);
2777 if (rchild
->grp_unscalarizable_region
)
2779 if (rchild
->grp_write
&& !lacc
->grp_write
)
2782 subtree_mark_written_and_rhs_enqueue (lacc
);
2787 rchild
->grp_hint
= 1;
2788 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
,
2789 false, (lacc
->grp_write
2790 || rchild
->grp_write
));
2791 gcc_checking_assert (new_acc
);
2792 if (racc
->first_child
)
2793 propagate_subaccesses_from_rhs (new_acc
, rchild
);
2795 add_access_to_rhs_work_queue (lacc
);
2802 /* Propagate subaccesses of LACC across an assignment link to RACC if they
2803 should inhibit total scalarization of the corresponding area. No flags are
2804 being propagated in the process. Return true if anything changed. */
2807 propagate_subaccesses_from_lhs (struct access
*lacc
, struct access
*racc
)
2809 if (is_gimple_reg_type (racc
->type
)
2810 || lacc
->grp_unscalarizable_region
2811 || racc
->grp_unscalarizable_region
)
2814 /* TODO: Do we want set some new racc flag to stop potential total
2815 scalarization if lacc is a scalar access (and none fo the two have
2819 HOST_WIDE_INT norm_delta
= racc
->offset
- lacc
->offset
;
2820 for (struct access
*lchild
= lacc
->first_child
;
2822 lchild
= lchild
->next_sibling
)
2824 struct access
*matching_acc
= NULL
;
2825 HOST_WIDE_INT norm_offset
= lchild
->offset
+ norm_delta
;
2827 if (lchild
->grp_unscalarizable_region
2828 || child_would_conflict_in_acc (racc
, norm_offset
, lchild
->size
,
2832 && propagate_subaccesses_from_lhs (lchild
, matching_acc
))
2833 add_access_to_lhs_work_queue (matching_acc
);
2837 struct access
*new_acc
2838 = create_artificial_child_access (racc
, lchild
, norm_offset
,
2840 propagate_subaccesses_from_lhs (lchild
, new_acc
);
2846 /* Propagate all subaccesses across assignment links. */
2849 propagate_all_subaccesses (void)
2851 while (rhs_work_queue_head
)
2853 struct access
*racc
= pop_access_from_rhs_work_queue ();
2854 struct assign_link
*link
;
2856 if (racc
->group_representative
)
2857 racc
= racc
->group_representative
;
2858 gcc_assert (racc
->first_rhs_link
);
2860 for (link
= racc
->first_rhs_link
; link
; link
= link
->next_rhs
)
2862 struct access
*lacc
= link
->lacc
;
2864 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2866 lacc
= lacc
->group_representative
;
2868 bool reque_parents
= false;
2869 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
2871 if (!lacc
->grp_write
)
2873 subtree_mark_written_and_rhs_enqueue (lacc
);
2874 reque_parents
= true;
2877 else if (propagate_subaccesses_from_rhs (lacc
, racc
))
2878 reque_parents
= true;
2883 add_access_to_rhs_work_queue (lacc
);
2884 lacc
= lacc
->parent
;
2890 while (lhs_work_queue_head
)
2892 struct access
*lacc
= pop_access_from_lhs_work_queue ();
2893 struct assign_link
*link
;
2895 if (lacc
->group_representative
)
2896 lacc
= lacc
->group_representative
;
2897 gcc_assert (lacc
->first_lhs_link
);
2899 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2902 for (link
= lacc
->first_lhs_link
; link
; link
= link
->next_lhs
)
2904 struct access
*racc
= link
->racc
;
2906 if (racc
->group_representative
)
2907 racc
= racc
->group_representative
;
2908 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
2910 if (propagate_subaccesses_from_lhs (lacc
, racc
))
2911 add_access_to_lhs_work_queue (racc
);
2916 /* Return true if the forest beginning with ROOT does not contain
2917 unscalarizable regions or non-byte aligned accesses. */
2920 can_totally_scalarize_forest_p (struct access
*root
)
2922 struct access
*access
= root
;
2925 if (access
->grp_unscalarizable_region
2926 || (access
->offset
% BITS_PER_UNIT
) != 0
2927 || (access
->size
% BITS_PER_UNIT
) != 0
2928 || (is_gimple_reg_type (access
->type
)
2929 && access
->first_child
))
2932 if (access
->first_child
)
2933 access
= access
->first_child
;
2934 else if (access
->next_sibling
)
2935 access
= access
->next_sibling
;
2938 while (access
->parent
&& !access
->next_sibling
)
2939 access
= access
->parent
;
2940 if (access
->next_sibling
)
2941 access
= access
->next_sibling
;
2944 gcc_assert (access
== root
);
2945 root
= root
->next_grp
;
2954 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
2955 reference EXPR for total scalarization purposes and mark it as such. Within
2956 the children of PARENT, link it in between PTR and NEXT_SIBLING. */
2958 static struct access
*
2959 create_total_scalarization_access (struct access
*parent
, HOST_WIDE_INT pos
,
2960 HOST_WIDE_INT size
, tree type
, tree expr
,
2961 struct access
**ptr
,
2962 struct access
*next_sibling
)
2964 struct access
*access
= access_pool
.allocate ();
2965 memset (access
, 0, sizeof (struct access
));
2966 access
->base
= parent
->base
;
2967 access
->offset
= pos
;
2968 access
->size
= size
;
2969 access
->expr
= expr
;
2970 access
->type
= type
;
2971 access
->parent
= parent
;
2972 access
->grp_write
= parent
->grp_write
;
2973 access
->grp_total_scalarization
= 1;
2974 access
->grp_hint
= 1;
2975 access
->grp_same_access_path
= path_comparable_for_same_access (expr
);
2976 access
->reverse
= reverse_storage_order_for_component_p (expr
);
2978 access
->next_sibling
= next_sibling
;
2983 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
2984 reference EXPR for total scalarization purposes and mark it as such, link it
2985 at *PTR and reshape the tree so that those elements at *PTR and their
2986 siblings which fall within the part described by POS and SIZE are moved to
2987 be children of the new access. If a partial overlap is detected, return
2990 static struct access
*
2991 create_total_access_and_reshape (struct access
*parent
, HOST_WIDE_INT pos
,
2992 HOST_WIDE_INT size
, tree type
, tree expr
,
2993 struct access
**ptr
)
2995 struct access
**p
= ptr
;
2997 while (*p
&& (*p
)->offset
< pos
+ size
)
2999 if ((*p
)->offset
+ (*p
)->size
> pos
+ size
)
3001 p
= &(*p
)->next_sibling
;
3004 struct access
*next_child
= *ptr
;
3005 struct access
*new_acc
3006 = create_total_scalarization_access (parent
, pos
, size
, type
, expr
,
3010 new_acc
->first_child
= next_child
;
3012 for (struct access
*a
= next_child
; a
; a
= a
->next_sibling
)
3013 a
->parent
= new_acc
;
3018 static bool totally_scalarize_subtree (struct access
*root
);
3020 /* Return true if INNER is either the same type as OUTER or if it is the type
3021 of a record field in OUTER at offset zero, possibly in nested
3025 access_and_field_type_match_p (tree outer
, tree inner
)
3027 if (TYPE_MAIN_VARIANT (outer
) == TYPE_MAIN_VARIANT (inner
))
3029 if (TREE_CODE (outer
) != RECORD_TYPE
)
3031 tree fld
= TYPE_FIELDS (outer
);
3034 if (TREE_CODE (fld
) == FIELD_DECL
)
3036 if (!zerop (DECL_FIELD_OFFSET (fld
)))
3038 if (TYPE_MAIN_VARIANT (TREE_TYPE (fld
)) == inner
)
3040 if (TREE_CODE (TREE_TYPE (fld
)) == RECORD_TYPE
)
3041 fld
= TYPE_FIELDS (TREE_TYPE (fld
));
3046 fld
= DECL_CHAIN (fld
);
3051 /* Return type of total_should_skip_creating_access indicating whether a total
3052 scalarization access for a field/element should be created, whether it
3053 already exists or whether the entire total scalarization has to fail. */
3055 enum total_sra_field_state
{TOTAL_FLD_CREATE
, TOTAL_FLD_DONE
, TOTAL_FLD_FAILED
};
3057 /* Do all the necessary steps in total scalarization when the given aggregate
3058 type has a TYPE at POS with the given SIZE should be put into PARENT and
3059 when we have processed all its siblings with smaller offsets up until and
3060 including LAST_SEEN_SIBLING (which can be NULL).
3062 If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3063 appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3064 creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3065 representing the described part of the aggregate for the purposes of total
3066 scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3067 prevents total scalarization from happening at all. */
3069 static enum total_sra_field_state
3070 total_should_skip_creating_access (struct access
*parent
,
3071 struct access
**last_seen_sibling
,
3072 tree type
, HOST_WIDE_INT pos
,
3075 struct access
*next_child
;
3076 if (!*last_seen_sibling
)
3077 next_child
= parent
->first_child
;
3079 next_child
= (*last_seen_sibling
)->next_sibling
;
3081 /* First, traverse the chain of siblings until it points to an access with
3082 offset at least equal to POS. Check all skipped accesses whether they
3083 span the POS boundary and if so, return with a failure. */
3084 while (next_child
&& next_child
->offset
< pos
)
3086 if (next_child
->offset
+ next_child
->size
> pos
)
3087 return TOTAL_FLD_FAILED
;
3088 *last_seen_sibling
= next_child
;
3089 next_child
= next_child
->next_sibling
;
3092 /* Now check whether next_child has exactly the right POS and SIZE and if so,
3093 whether it can represent what we need and can be totally scalarized
3095 if (next_child
&& next_child
->offset
== pos
3096 && next_child
->size
== size
)
3098 if (!is_gimple_reg_type (next_child
->type
)
3099 && (!access_and_field_type_match_p (type
, next_child
->type
)
3100 || !totally_scalarize_subtree (next_child
)))
3101 return TOTAL_FLD_FAILED
;
3103 *last_seen_sibling
= next_child
;
3104 return TOTAL_FLD_DONE
;
3107 /* If the child we're looking at would partially overlap, we just cannot
3108 totally scalarize. */
3110 && next_child
->offset
< pos
+ size
3111 && next_child
->offset
+ next_child
->size
> pos
+ size
)
3112 return TOTAL_FLD_FAILED
;
3114 if (is_gimple_reg_type (type
))
3116 /* We don't scalarize accesses that are children of other scalar type
3117 accesses, so if we go on and create an access for a register type,
3118 there should not be any pre-existing children. There are rare cases
3119 where the requested type is a vector but we already have register
3120 accesses for all its elements which is equally good. Detect that
3121 situation or whether we need to bail out. */
3123 HOST_WIDE_INT covered
= pos
;
3124 bool skipping
= false;
3126 && next_child
->offset
+ next_child
->size
<= pos
+ size
)
3128 if (next_child
->offset
!= covered
3129 || !is_gimple_reg_type (next_child
->type
))
3130 return TOTAL_FLD_FAILED
;
3132 covered
+= next_child
->size
;
3133 *last_seen_sibling
= next_child
;
3134 next_child
= next_child
->next_sibling
;
3140 if (covered
!= pos
+ size
)
3141 return TOTAL_FLD_FAILED
;
3143 return TOTAL_FLD_DONE
;
3147 return TOTAL_FLD_CREATE
;
3150 /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3151 spanning all uncovered areas covered by ROOT, return false if the attempt
3152 failed. All created accesses will have grp_unscalarizable_region set (and
3153 should be ignored if the function returns false). */
3156 totally_scalarize_subtree (struct access
*root
)
3158 gcc_checking_assert (!root
->grp_unscalarizable_region
);
3159 gcc_checking_assert (!is_gimple_reg_type (root
->type
));
3161 struct access
*last_seen_sibling
= NULL
;
3163 switch (TREE_CODE (root
->type
))
3166 for (tree fld
= TYPE_FIELDS (root
->type
); fld
; fld
= DECL_CHAIN (fld
))
3167 if (TREE_CODE (fld
) == FIELD_DECL
)
3169 tree ft
= TREE_TYPE (fld
);
3170 HOST_WIDE_INT fsize
= tree_to_uhwi (DECL_SIZE (fld
));
3174 HOST_WIDE_INT pos
= root
->offset
+ int_bit_position (fld
);
3175 enum total_sra_field_state
3176 state
= total_should_skip_creating_access (root
,
3181 case TOTAL_FLD_FAILED
:
3183 case TOTAL_FLD_DONE
:
3185 case TOTAL_FLD_CREATE
:
3191 struct access
**p
= (last_seen_sibling
3192 ? &last_seen_sibling
->next_sibling
3193 : &root
->first_child
);
3194 tree nref
= build3 (COMPONENT_REF
, ft
, root
->expr
, fld
, NULL_TREE
);
3195 struct access
*new_child
3196 = create_total_access_and_reshape (root
, pos
, fsize
, ft
, nref
, p
);
3200 if (!is_gimple_reg_type (ft
)
3201 && !totally_scalarize_subtree (new_child
))
3203 last_seen_sibling
= new_child
;
3208 tree elemtype
= TREE_TYPE (root
->type
);
3209 tree elem_size
= TYPE_SIZE (elemtype
);
3210 gcc_assert (elem_size
&& tree_fits_shwi_p (elem_size
));
3211 HOST_WIDE_INT el_size
= tree_to_shwi (elem_size
);
3212 gcc_assert (el_size
> 0);
3214 tree minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (root
->type
));
3215 gcc_assert (TREE_CODE (minidx
) == INTEGER_CST
);
3216 tree maxidx
= TYPE_MAX_VALUE (TYPE_DOMAIN (root
->type
));
3217 /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
3220 gcc_assert (TREE_CODE (maxidx
) == INTEGER_CST
);
3221 tree domain
= TYPE_DOMAIN (root
->type
);
3222 /* MINIDX and MAXIDX are inclusive, and must be interpreted in
3223 DOMAIN (e.g. signed int, whereas min/max may be size_int). */
3224 offset_int idx
= wi::to_offset (minidx
);
3225 offset_int max
= wi::to_offset (maxidx
);
3226 if (!TYPE_UNSIGNED (domain
))
3228 idx
= wi::sext (idx
, TYPE_PRECISION (domain
));
3229 max
= wi::sext (max
, TYPE_PRECISION (domain
));
3231 for (HOST_WIDE_INT pos
= root
->offset
;
3233 pos
+= el_size
, ++idx
)
3235 enum total_sra_field_state
3236 state
= total_should_skip_creating_access (root
,
3242 case TOTAL_FLD_FAILED
:
3244 case TOTAL_FLD_DONE
:
3246 case TOTAL_FLD_CREATE
:
3252 struct access
**p
= (last_seen_sibling
3253 ? &last_seen_sibling
->next_sibling
3254 : &root
->first_child
);
3255 tree nref
= build4 (ARRAY_REF
, elemtype
, root
->expr
,
3256 wide_int_to_tree (domain
, idx
),
3257 NULL_TREE
, NULL_TREE
);
3258 struct access
*new_child
3259 = create_total_access_and_reshape (root
, pos
, el_size
, elemtype
,
3264 if (!is_gimple_reg_type (elemtype
)
3265 && !totally_scalarize_subtree (new_child
))
3267 last_seen_sibling
= new_child
;
3279 /* Go through all accesses collected throughout the (intraprocedural) analysis
3280 stage, exclude overlapping ones, identify representatives and build trees
3281 out of them, making decisions about scalarization on the way. Return true
3282 iff there are any to-be-scalarized variables after this stage. */
3285 analyze_all_variable_accesses (void)
3288 bitmap tmp
= BITMAP_ALLOC (NULL
);
3292 bitmap_copy (tmp
, candidate_bitmap
);
3293 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3295 tree var
= candidate (i
);
3296 struct access
*access
;
3298 access
= sort_and_splice_var_accesses (var
);
3299 if (!access
|| !build_access_trees (access
))
3300 disqualify_candidate (var
,
3301 "No or inhibitingly overlapping accesses.");
3304 propagate_all_subaccesses ();
3306 bool optimize_speed_p
= !optimize_function_for_size_p (cfun
);
3307 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3308 fall back to a target default. */
3309 unsigned HOST_WIDE_INT max_scalarization_size
3310 = get_move_ratio (optimize_speed_p
) * UNITS_PER_WORD
;
3312 if (optimize_speed_p
)
3314 if (global_options_set
.x_param_sra_max_scalarization_size_speed
)
3315 max_scalarization_size
= param_sra_max_scalarization_size_speed
;
3319 if (global_options_set
.x_param_sra_max_scalarization_size_size
)
3320 max_scalarization_size
= param_sra_max_scalarization_size_size
;
3322 max_scalarization_size
*= BITS_PER_UNIT
;
3324 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
3325 if (bitmap_bit_p (should_scalarize_away_bitmap
, i
)
3326 && !bitmap_bit_p (cannot_scalarize_away_bitmap
, i
))
3328 tree var
= candidate (i
);
3332 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var
))) > max_scalarization_size
)
3334 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 fprintf (dump_file
, "Too big to totally scalarize: ");
3337 print_generic_expr (dump_file
, var
);
3338 fprintf (dump_file
, " (UID: %u)\n", DECL_UID (var
));
3343 bool all_types_ok
= true;
3344 for (struct access
*access
= get_first_repr_for_decl (var
);
3346 access
= access
->next_grp
)
3347 if (!can_totally_scalarize_forest_p (access
)
3348 || !scalarizable_type_p (access
->type
, constant_decl_p (var
)))
3350 all_types_ok
= false;
3356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3358 fprintf (dump_file
, "Will attempt to totally scalarize ");
3359 print_generic_expr (dump_file
, var
);
3360 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3362 bool scalarized
= true;
3363 for (struct access
*access
= get_first_repr_for_decl (var
);
3365 access
= access
->next_grp
)
3366 if (!is_gimple_reg_type (access
->type
)
3367 && !totally_scalarize_subtree (access
))
3374 for (struct access
*access
= get_first_repr_for_decl (var
);
3376 access
= access
->next_grp
)
3377 access
->grp_total_scalarization
= true;
3381 verify_all_sra_access_forests ();
3383 bitmap_copy (tmp
, candidate_bitmap
);
3384 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3386 tree var
= candidate (i
);
3387 struct access
*access
= get_first_repr_for_decl (var
);
3389 if (analyze_access_trees (access
))
3392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3394 fprintf (dump_file
, "\nAccess trees for ");
3395 print_generic_expr (dump_file
, var
);
3396 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3397 dump_access_tree (dump_file
, access
);
3398 fprintf (dump_file
, "\n");
3402 disqualify_candidate (var
, "No scalar replacements to be created.");
3409 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
3416 /* Generate statements copying scalar replacements of accesses within a subtree
3417 into or out of AGG. ACCESS, all its children, siblings and their children
3418 are to be processed. AGG is an aggregate type expression (can be a
3419 declaration but does not have to be, it can for example also be a mem_ref or
3420 a series of handled components). TOP_OFFSET is the offset of the processed
3421 subtree which has to be subtracted from offsets of individual accesses to
3422 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3423 replacements in the interval <start_offset, start_offset + chunk_size>,
3424 otherwise copy all. GSI is a statement iterator used to place the new
3425 statements. WRITE should be true when the statements should write from AGG
3426 to the replacement and false if vice versa. if INSERT_AFTER is true, new
3427 statements will be added after the current statement in GSI, they will be
3428 added before the statement otherwise. */
3431 generate_subtree_copies (struct access
*access
, tree agg
,
3432 HOST_WIDE_INT top_offset
,
3433 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
3434 gimple_stmt_iterator
*gsi
, bool write
,
3435 bool insert_after
, location_t loc
)
3437 /* Never write anything into constant pool decls. See PR70602. */
3438 if (!write
&& constant_decl_p (agg
))
3442 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
3445 if (access
->grp_to_be_replaced
3447 || access
->offset
+ access
->size
> start_offset
))
3449 tree expr
, repl
= get_access_replacement (access
);
3452 expr
= build_ref_for_model (loc
, agg
, access
->offset
- top_offset
,
3453 access
, gsi
, insert_after
);
3457 if (access
->grp_partial_lhs
)
3458 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
3460 insert_after
? GSI_NEW_STMT
3462 stmt
= gimple_build_assign (repl
, expr
);
3466 TREE_NO_WARNING (repl
) = 1;
3467 if (access
->grp_partial_lhs
)
3468 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
3470 insert_after
? GSI_NEW_STMT
3472 stmt
= gimple_build_assign (expr
, repl
);
3474 gimple_set_location (stmt
, loc
);
3477 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3479 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3481 sra_stats
.subtree_copies
++;
3484 && access
->grp_to_be_debug_replaced
3486 || access
->offset
+ access
->size
> start_offset
))
3489 tree drhs
= build_debug_ref_for_model (loc
, agg
,
3490 access
->offset
- top_offset
,
3492 ds
= gimple_build_debug_bind (get_access_replacement (access
),
3493 drhs
, gsi_stmt (*gsi
));
3495 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3497 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3500 if (access
->first_child
)
3501 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
3502 start_offset
, chunk_size
, gsi
,
3503 write
, insert_after
, loc
);
3505 access
= access
->next_sibling
;
3510 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
3511 root of the subtree to be processed. GSI is the statement iterator used
3512 for inserting statements which are added after the current statement if
3513 INSERT_AFTER is true or before it otherwise. */
3516 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
3517 bool insert_after
, location_t loc
)
3520 struct access
*child
;
3522 if (access
->grp_to_be_replaced
)
3526 stmt
= gimple_build_assign (get_access_replacement (access
),
3527 build_zero_cst (access
->type
));
3529 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3531 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3533 gimple_set_location (stmt
, loc
);
3535 else if (access
->grp_to_be_debug_replaced
)
3538 = gimple_build_debug_bind (get_access_replacement (access
),
3539 build_zero_cst (access
->type
),
3542 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3544 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3547 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3548 init_subtree_with_zero (child
, gsi
, insert_after
, loc
);
3551 /* Clobber all scalar replacements in an access subtree. ACCESS is the
3552 root of the subtree to be processed. GSI is the statement iterator used
3553 for inserting statements which are added after the current statement if
3554 INSERT_AFTER is true or before it otherwise. */
3557 clobber_subtree (struct access
*access
, gimple_stmt_iterator
*gsi
,
3558 bool insert_after
, location_t loc
)
3561 struct access
*child
;
3563 if (access
->grp_to_be_replaced
)
3565 tree rep
= get_access_replacement (access
);
3566 tree clobber
= build_clobber (access
->type
);
3567 gimple
*stmt
= gimple_build_assign (rep
, clobber
);
3570 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3572 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3574 gimple_set_location (stmt
, loc
);
3577 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3578 clobber_subtree (child
, gsi
, insert_after
, loc
);
3581 /* Search for an access representative for the given expression EXPR and
3582 return it or NULL if it cannot be found. */
3584 static struct access
*
3585 get_access_for_expr (tree expr
)
3587 poly_int64 poffset
, psize
, pmax_size
;
3588 HOST_WIDE_INT offset
, max_size
;
3592 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
3593 a different size than the size of its argument and we need the latter
3595 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
3596 expr
= TREE_OPERAND (expr
, 0);
3598 base
= get_ref_base_and_extent (expr
, &poffset
, &psize
, &pmax_size
,
3600 if (!known_size_p (pmax_size
)
3601 || !pmax_size
.is_constant (&max_size
)
3602 || !poffset
.is_constant (&offset
)
3606 if (tree basesize
= DECL_SIZE (base
))
3610 || !poly_int_tree_p (basesize
, &sz
)
3611 || known_le (sz
, offset
))
3615 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
3618 return get_var_base_offset_size_access (base
, offset
, max_size
);
3621 /* Replace the expression EXPR with a scalar replacement if there is one and
3622 generate other statements to do type conversion or subtree copying if
3623 necessary. GSI is used to place newly created statements, WRITE is true if
3624 the expression is being written to (it is on a LHS of a statement or output
3625 in an assembly statement). */
3628 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
)
3631 struct access
*access
;
3632 tree type
, bfr
, orig_expr
;
3634 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
3637 expr
= &TREE_OPERAND (*expr
, 0);
3642 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
3643 expr
= &TREE_OPERAND (*expr
, 0);
3644 access
= get_access_for_expr (*expr
);
3647 type
= TREE_TYPE (*expr
);
3650 loc
= gimple_location (gsi_stmt (*gsi
));
3651 gimple_stmt_iterator alt_gsi
= gsi_none ();
3652 if (write
&& stmt_ends_bb_p (gsi_stmt (*gsi
)))
3654 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
3658 if (access
->grp_to_be_replaced
)
3660 tree repl
= get_access_replacement (access
);
3661 /* If we replace a non-register typed access simply use the original
3662 access expression to extract the scalar component afterwards.
3663 This happens if scalarizing a function return value or parameter
3664 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
3665 gcc.c-torture/compile/20011217-1.c.
3667 We also want to use this when accessing a complex or vector which can
3668 be accessed as a different type too, potentially creating a need for
3669 type conversion (see PR42196) and when scalarized unions are involved
3670 in assembler statements (see PR42398). */
3671 if (!useless_type_conversion_p (type
, access
->type
))
3675 ref
= build_ref_for_model (loc
, orig_expr
, 0, access
, gsi
, false);
3681 if (access
->grp_partial_lhs
)
3682 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
3683 false, GSI_NEW_STMT
);
3684 stmt
= gimple_build_assign (repl
, ref
);
3685 gimple_set_location (stmt
, loc
);
3686 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3692 if (access
->grp_partial_lhs
)
3693 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
3694 true, GSI_SAME_STMT
);
3695 stmt
= gimple_build_assign (ref
, repl
);
3696 gimple_set_location (stmt
, loc
);
3697 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3704 else if (write
&& access
->grp_to_be_debug_replaced
)
3706 gdebug
*ds
= gimple_build_debug_bind (get_access_replacement (access
),
3709 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3712 if (access
->first_child
)
3714 HOST_WIDE_INT start_offset
, chunk_size
;
3716 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 1))
3717 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 2)))
3719 chunk_size
= tree_to_uhwi (TREE_OPERAND (bfr
, 1));
3720 start_offset
= access
->offset
3721 + tree_to_uhwi (TREE_OPERAND (bfr
, 2));
3724 start_offset
= chunk_size
= 0;
3726 generate_subtree_copies (access
->first_child
, orig_expr
, access
->offset
,
3727 start_offset
, chunk_size
, gsi
, write
, write
,
3733 /* Where scalar replacements of the RHS have been written to when a replacement
3734 of a LHS of an assigments cannot be direclty loaded from a replacement of
3736 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
3737 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
3738 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
3740 struct subreplacement_assignment_data
3742 /* Offset of the access representing the lhs of the assignment. */
3743 HOST_WIDE_INT left_offset
;
3745 /* LHS and RHS of the original assignment. */
3746 tree assignment_lhs
, assignment_rhs
;
3748 /* Access representing the rhs of the whole assignment. */
3749 struct access
*top_racc
;
3751 /* Stmt iterator used for statement insertions after the original assignment.
3752 It points to the main GSI used to traverse a BB during function body
3754 gimple_stmt_iterator
*new_gsi
;
3756 /* Stmt iterator used for statement insertions before the original
3757 assignment. Keeps on pointing to the original statement. */
3758 gimple_stmt_iterator old_gsi
;
3760 /* Location of the assignment. */
3763 /* Keeps the information whether we have needed to refresh replacements of
3764 the LHS and from which side of the assignments this takes place. */
3765 enum unscalarized_data_handling refreshed
;
3768 /* Store all replacements in the access tree rooted in TOP_RACC either to their
3769 base aggregate if there are unscalarized data or directly to LHS of the
3770 statement that is pointed to by GSI otherwise. */
3773 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data
*sad
)
3776 if (sad
->top_racc
->grp_unscalarized_data
)
3778 src
= sad
->assignment_rhs
;
3779 sad
->refreshed
= SRA_UDH_RIGHT
;
3783 src
= sad
->assignment_lhs
;
3784 sad
->refreshed
= SRA_UDH_LEFT
;
3786 generate_subtree_copies (sad
->top_racc
->first_child
, src
,
3787 sad
->top_racc
->offset
, 0, 0,
3788 &sad
->old_gsi
, false, false, sad
->loc
);
3791 /* Try to generate statements to load all sub-replacements in an access subtree
3792 formed by children of LACC from scalar replacements in the SAD->top_racc
3793 subtree. If that is not possible, refresh the SAD->top_racc base aggregate
3794 and load the accesses from it. */
3797 load_assign_lhs_subreplacements (struct access
*lacc
,
3798 struct subreplacement_assignment_data
*sad
)
3800 for (lacc
= lacc
->first_child
; lacc
; lacc
= lacc
->next_sibling
)
3802 HOST_WIDE_INT offset
;
3803 offset
= lacc
->offset
- sad
->left_offset
+ sad
->top_racc
->offset
;
3805 if (lacc
->grp_to_be_replaced
)
3807 struct access
*racc
;
3811 racc
= find_access_in_subtree (sad
->top_racc
, offset
, lacc
->size
);
3812 if (racc
&& racc
->grp_to_be_replaced
)
3814 rhs
= get_access_replacement (racc
);
3815 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
3816 rhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3819 if (racc
->grp_partial_lhs
&& lacc
->grp_partial_lhs
)
3820 rhs
= force_gimple_operand_gsi (&sad
->old_gsi
, rhs
, true,
3821 NULL_TREE
, true, GSI_SAME_STMT
);
3825 /* No suitable access on the right hand side, need to load from
3826 the aggregate. See if we have to update it first... */
3827 if (sad
->refreshed
== SRA_UDH_NONE
)
3828 handle_unscalarized_data_in_subtree (sad
);
3830 if (sad
->refreshed
== SRA_UDH_LEFT
)
3831 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_lhs
,
3832 lacc
->offset
- sad
->left_offset
,
3833 lacc
, sad
->new_gsi
, true);
3835 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_rhs
,
3836 lacc
->offset
- sad
->left_offset
,
3837 lacc
, sad
->new_gsi
, true);
3838 if (lacc
->grp_partial_lhs
)
3839 rhs
= force_gimple_operand_gsi (sad
->new_gsi
,
3840 rhs
, true, NULL_TREE
,
3841 false, GSI_NEW_STMT
);
3844 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
3845 gsi_insert_after (sad
->new_gsi
, stmt
, GSI_NEW_STMT
);
3846 gimple_set_location (stmt
, sad
->loc
);
3848 sra_stats
.subreplacements
++;
3852 if (sad
->refreshed
== SRA_UDH_NONE
3853 && lacc
->grp_read
&& !lacc
->grp_covered
)
3854 handle_unscalarized_data_in_subtree (sad
);
3856 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
3860 struct access
*racc
= find_access_in_subtree (sad
->top_racc
,
3864 if (racc
&& racc
->grp_to_be_replaced
)
3866 if (racc
->grp_write
|| constant_decl_p (racc
->base
))
3867 drhs
= get_access_replacement (racc
);
3871 else if (sad
->refreshed
== SRA_UDH_LEFT
)
3872 drhs
= build_debug_ref_for_model (sad
->loc
, lacc
->base
,
3873 lacc
->offset
, lacc
);
3874 else if (sad
->refreshed
== SRA_UDH_RIGHT
)
3875 drhs
= build_debug_ref_for_model (sad
->loc
, sad
->top_racc
->base
,
3880 && !useless_type_conversion_p (lacc
->type
, TREE_TYPE (drhs
)))
3881 drhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3883 ds
= gimple_build_debug_bind (get_access_replacement (lacc
),
3884 drhs
, gsi_stmt (sad
->old_gsi
));
3885 gsi_insert_after (sad
->new_gsi
, ds
, GSI_NEW_STMT
);
3889 if (lacc
->first_child
)
3890 load_assign_lhs_subreplacements (lacc
, sad
);
3894 /* Result code for SRA assignment modification. */
3895 enum assignment_mod_result
{ SRA_AM_NONE
, /* nothing done for the stmt */
3896 SRA_AM_MODIFIED
, /* stmt changed but not
3898 SRA_AM_REMOVED
}; /* stmt eliminated */
3900 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
3901 to the assignment and GSI is the statement iterator pointing at it. Returns
3902 the same values as sra_modify_assign. */
3904 static enum assignment_mod_result
3905 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
3907 tree lhs
= gimple_assign_lhs (stmt
);
3908 struct access
*acc
= get_access_for_expr (lhs
);
3911 location_t loc
= gimple_location (stmt
);
3913 if (gimple_clobber_p (stmt
))
3915 /* Clobber the replacement variable. */
3916 clobber_subtree (acc
, gsi
, !acc
->grp_covered
, loc
);
3917 /* Remove clobbers of fully scalarized variables, they are dead. */
3918 if (acc
->grp_covered
)
3920 unlink_stmt_vdef (stmt
);
3921 gsi_remove (gsi
, true);
3922 release_defs (stmt
);
3923 return SRA_AM_REMOVED
;
3926 return SRA_AM_MODIFIED
;
3929 if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
)) > 0)
3931 /* I have never seen this code path trigger but if it can happen the
3932 following should handle it gracefully. */
3933 if (access_has_children_p (acc
))
3934 generate_subtree_copies (acc
->first_child
, lhs
, acc
->offset
, 0, 0, gsi
,
3936 return SRA_AM_MODIFIED
;
3939 if (acc
->grp_covered
)
3941 init_subtree_with_zero (acc
, gsi
, false, loc
);
3942 unlink_stmt_vdef (stmt
);
3943 gsi_remove (gsi
, true);
3944 release_defs (stmt
);
3945 return SRA_AM_REMOVED
;
3949 init_subtree_with_zero (acc
, gsi
, true, loc
);
3950 return SRA_AM_MODIFIED
;
3954 /* Create and return a new suitable default definition SSA_NAME for RACC which
3955 is an access describing an uninitialized part of an aggregate that is being
3956 loaded. REG_TREE is used instead of the actual RACC type if that is not of
3957 a gimple register type. */
3960 get_repl_default_def_ssa_name (struct access
*racc
, tree reg_type
)
3962 gcc_checking_assert (!racc
->grp_to_be_replaced
3963 && !racc
->grp_to_be_debug_replaced
);
3964 if (!racc
->replacement_decl
)
3965 racc
->replacement_decl
= create_access_replacement (racc
, reg_type
);
3966 return get_or_create_ssa_default_def (cfun
, racc
->replacement_decl
);
3969 /* Examine both sides of the assignment statement pointed to by STMT, replace
3970 them with a scalare replacement if there is one and generate copying of
3971 replacements if scalarized aggregates have been used in the assignment. GSI
3972 is used to hold generated statements for type conversions and subtree
3975 static enum assignment_mod_result
3976 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
3978 struct access
*lacc
, *racc
;
3980 bool modify_this_stmt
= false;
3981 bool force_gimple_rhs
= false;
3983 gimple_stmt_iterator orig_gsi
= *gsi
;
3985 if (!gimple_assign_single_p (stmt
))
3987 lhs
= gimple_assign_lhs (stmt
);
3988 rhs
= gimple_assign_rhs1 (stmt
);
3990 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
3991 return sra_modify_constructor_assign (stmt
, gsi
);
3993 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
3994 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
3995 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
3997 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (stmt
),
3999 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (stmt
),
4001 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4004 lacc
= get_access_for_expr (lhs
);
4005 racc
= get_access_for_expr (rhs
);
4008 /* Avoid modifying initializations of constant-pool replacements. */
4009 if (racc
&& (racc
->replacement_decl
== lhs
))
4012 loc
= gimple_location (stmt
);
4013 if (lacc
&& lacc
->grp_to_be_replaced
)
4015 lhs
= get_access_replacement (lacc
);
4016 gimple_assign_set_lhs (stmt
, lhs
);
4017 modify_this_stmt
= true;
4018 if (lacc
->grp_partial_lhs
)
4019 force_gimple_rhs
= true;
4023 if (racc
&& racc
->grp_to_be_replaced
)
4025 rhs
= get_access_replacement (racc
);
4026 modify_this_stmt
= true;
4027 if (racc
->grp_partial_lhs
)
4028 force_gimple_rhs
= true;
4032 && !racc
->grp_unscalarized_data
4033 && !racc
->grp_unscalarizable_region
4034 && TREE_CODE (lhs
) == SSA_NAME
4035 && !access_has_replacements_p (racc
))
4037 rhs
= get_repl_default_def_ssa_name (racc
, TREE_TYPE (lhs
));
4038 modify_this_stmt
= true;
4042 if (modify_this_stmt
)
4044 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4046 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
4047 ??? This should move to fold_stmt which we simply should
4048 call after building a VIEW_CONVERT_EXPR here. */
4049 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
4050 && !contains_bitfld_component_ref_p (lhs
))
4052 lhs
= build_ref_for_model (loc
, lhs
, 0, racc
, gsi
, false);
4053 gimple_assign_set_lhs (stmt
, lhs
);
4056 && AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
4057 && !contains_vce_or_bfcref_p (rhs
))
4058 rhs
= build_ref_for_model (loc
, rhs
, 0, lacc
, gsi
, false);
4060 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4062 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
),
4064 if (is_gimple_reg_type (TREE_TYPE (lhs
))
4065 && TREE_CODE (lhs
) != SSA_NAME
)
4066 force_gimple_rhs
= true;
4071 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
4073 tree dlhs
= get_access_replacement (lacc
);
4074 tree drhs
= unshare_expr (rhs
);
4075 if (!useless_type_conversion_p (TREE_TYPE (dlhs
), TREE_TYPE (drhs
)))
4077 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs
))
4078 && !contains_vce_or_bfcref_p (drhs
))
4079 drhs
= build_debug_ref_for_model (loc
, drhs
, 0, lacc
);
4081 && !useless_type_conversion_p (TREE_TYPE (dlhs
),
4083 drhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
4084 TREE_TYPE (dlhs
), drhs
);
4086 gdebug
*ds
= gimple_build_debug_bind (dlhs
, drhs
, stmt
);
4087 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
4090 /* From this point on, the function deals with assignments in between
4091 aggregates when at least one has scalar reductions of some of its
4092 components. There are three possible scenarios: Both the LHS and RHS have
4093 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4095 In the first case, we would like to load the LHS components from RHS
4096 components whenever possible. If that is not possible, we would like to
4097 read it directly from the RHS (after updating it by storing in it its own
4098 components). If there are some necessary unscalarized data in the LHS,
4099 those will be loaded by the original assignment too. If neither of these
4100 cases happen, the original statement can be removed. Most of this is done
4101 by load_assign_lhs_subreplacements.
4103 In the second case, we would like to store all RHS scalarized components
4104 directly into LHS and if they cover the aggregate completely, remove the
4105 statement too. In the third case, we want the LHS components to be loaded
4106 directly from the RHS (DSE will remove the original statement if it
4109 This is a bit complex but manageable when types match and when unions do
4110 not cause confusion in a way that we cannot really load a component of LHS
4111 from the RHS or vice versa (the access representing this level can have
4112 subaccesses that are accessible only through a different union field at a
4113 higher level - different from the one used in the examined expression).
4116 Therefore, I specially handle a fourth case, happening when there is a
4117 specific type cast or it is impossible to locate a scalarized subaccess on
4118 the other side of the expression. If that happens, I simply "refresh" the
4119 RHS by storing in it is scalarized components leave the original statement
4120 there to do the copying and then load the scalar replacements of the LHS.
4121 This is what the first branch does. */
4123 if (modify_this_stmt
4124 || gimple_has_volatile_ops (stmt
)
4125 || contains_vce_or_bfcref_p (rhs
)
4126 || contains_vce_or_bfcref_p (lhs
)
4127 || stmt_ends_bb_p (stmt
))
4129 /* No need to copy into a constant-pool, it comes pre-initialized. */
4130 if (access_has_children_p (racc
) && !constant_decl_p (racc
->base
))
4131 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4132 gsi
, false, false, loc
);
4133 if (access_has_children_p (lacc
))
4135 gimple_stmt_iterator alt_gsi
= gsi_none ();
4136 if (stmt_ends_bb_p (stmt
))
4138 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
4141 generate_subtree_copies (lacc
->first_child
, lhs
, lacc
->offset
, 0, 0,
4142 gsi
, true, true, loc
);
4144 sra_stats
.separate_lhs_rhs_handling
++;
4146 /* This gimplification must be done after generate_subtree_copies,
4147 lest we insert the subtree copies in the middle of the gimplified
4149 if (force_gimple_rhs
)
4150 rhs
= force_gimple_operand_gsi (&orig_gsi
, rhs
, true, NULL_TREE
,
4151 true, GSI_SAME_STMT
);
4152 if (gimple_assign_rhs1 (stmt
) != rhs
)
4154 modify_this_stmt
= true;
4155 gimple_assign_set_rhs_from_tree (&orig_gsi
, rhs
);
4156 gcc_assert (stmt
== gsi_stmt (orig_gsi
));
4159 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4163 if (access_has_children_p (lacc
)
4164 && access_has_children_p (racc
)
4165 /* When an access represents an unscalarizable region, it usually
4166 represents accesses with variable offset and thus must not be used
4167 to generate new memory accesses. */
4168 && !lacc
->grp_unscalarizable_region
4169 && !racc
->grp_unscalarizable_region
)
4171 struct subreplacement_assignment_data sad
;
4173 sad
.left_offset
= lacc
->offset
;
4174 sad
.assignment_lhs
= lhs
;
4175 sad
.assignment_rhs
= rhs
;
4176 sad
.top_racc
= racc
;
4179 sad
.loc
= gimple_location (stmt
);
4180 sad
.refreshed
= SRA_UDH_NONE
;
4182 if (lacc
->grp_read
&& !lacc
->grp_covered
)
4183 handle_unscalarized_data_in_subtree (&sad
);
4185 load_assign_lhs_subreplacements (lacc
, &sad
);
4186 if (sad
.refreshed
!= SRA_UDH_RIGHT
)
4189 unlink_stmt_vdef (stmt
);
4190 gsi_remove (&sad
.old_gsi
, true);
4191 release_defs (stmt
);
4192 sra_stats
.deleted
++;
4193 return SRA_AM_REMOVED
;
4198 if (access_has_children_p (racc
)
4199 && !racc
->grp_unscalarized_data
4200 && TREE_CODE (lhs
) != SSA_NAME
)
4204 fprintf (dump_file
, "Removing load: ");
4205 print_gimple_stmt (dump_file
, stmt
, 0);
4207 generate_subtree_copies (racc
->first_child
, lhs
,
4208 racc
->offset
, 0, 0, gsi
,
4210 gcc_assert (stmt
== gsi_stmt (*gsi
));
4211 unlink_stmt_vdef (stmt
);
4212 gsi_remove (gsi
, true);
4213 release_defs (stmt
);
4214 sra_stats
.deleted
++;
4215 return SRA_AM_REMOVED
;
4217 /* Restore the aggregate RHS from its components so the
4218 prevailing aggregate copy does the right thing. */
4219 if (access_has_children_p (racc
))
4220 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4221 gsi
, false, false, loc
);
4222 /* Re-load the components of the aggregate copy destination.
4223 But use the RHS aggregate to load from to expose more
4224 optimization opportunities. */
4225 if (access_has_children_p (lacc
))
4226 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
4227 0, 0, gsi
, true, true, loc
);
4234 /* Set any scalar replacements of values in the constant pool to the initial
4235 value of the constant. (Constant-pool decls like *.LC0 have effectively
4236 been initialized before the program starts, we must do the same for their
4237 replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4238 the function's entry block. */
4241 initialize_constant_pool_replacements (void)
4243 gimple_seq seq
= NULL
;
4244 gimple_stmt_iterator gsi
= gsi_start (seq
);
4248 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
4250 tree var
= candidate (i
);
4251 if (!constant_decl_p (var
))
4254 struct access
*access
= get_first_repr_for_decl (var
);
4258 if (access
->replacement_decl
)
4261 = gimple_build_assign (get_access_replacement (access
),
4262 unshare_expr (access
->expr
));
4263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4265 fprintf (dump_file
, "Generating constant initializer: ");
4266 print_gimple_stmt (dump_file
, stmt
, 0);
4267 fprintf (dump_file
, "\n");
4269 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
4273 if (access
->first_child
)
4274 access
= access
->first_child
;
4275 else if (access
->next_sibling
)
4276 access
= access
->next_sibling
;
4279 while (access
->parent
&& !access
->next_sibling
)
4280 access
= access
->parent
;
4281 if (access
->next_sibling
)
4282 access
= access
->next_sibling
;
4284 access
= access
->next_grp
;
4289 seq
= gsi_seq (gsi
);
4291 gsi_insert_seq_on_edge_immediate (
4292 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4295 /* Traverse the function body and all modifications as decided in
4296 analyze_all_variable_accesses. Return true iff the CFG has been
4300 sra_modify_function_body (void)
4302 bool cfg_changed
= false;
4305 initialize_constant_pool_replacements ();
4307 FOR_EACH_BB_FN (bb
, cfun
)
4309 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
4310 while (!gsi_end_p (gsi
))
4312 gimple
*stmt
= gsi_stmt (gsi
);
4313 enum assignment_mod_result assign_result
;
4314 bool modified
= false, deleted
= false;
4318 switch (gimple_code (stmt
))
4321 t
= gimple_return_retval_ptr (as_a
<greturn
*> (stmt
));
4322 if (*t
!= NULL_TREE
)
4323 modified
|= sra_modify_expr (t
, &gsi
, false);
4327 assign_result
= sra_modify_assign (stmt
, &gsi
);
4328 modified
|= assign_result
== SRA_AM_MODIFIED
;
4329 deleted
= assign_result
== SRA_AM_REMOVED
;
4333 /* Operands must be processed before the lhs. */
4334 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
4336 t
= gimple_call_arg_ptr (stmt
, i
);
4337 modified
|= sra_modify_expr (t
, &gsi
, false);
4340 if (gimple_call_lhs (stmt
))
4342 t
= gimple_call_lhs_ptr (stmt
);
4343 modified
|= sra_modify_expr (t
, &gsi
, true);
4349 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
4350 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
4352 t
= &TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
4353 modified
|= sra_modify_expr (t
, &gsi
, false);
4355 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
4357 t
= &TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
4358 modified
|= sra_modify_expr (t
, &gsi
, true);
4370 if (maybe_clean_eh_stmt (stmt
)
4371 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
4379 gsi_commit_edge_inserts ();
4383 /* Generate statements initializing scalar replacements of parts of function
4387 initialize_parameter_reductions (void)
4389 gimple_stmt_iterator gsi
;
4390 gimple_seq seq
= NULL
;
4393 gsi
= gsi_start (seq
);
4394 for (parm
= DECL_ARGUMENTS (current_function_decl
);
4396 parm
= DECL_CHAIN (parm
))
4398 vec
<access_p
> *access_vec
;
4399 struct access
*access
;
4401 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
4403 access_vec
= get_base_access_vector (parm
);
4407 for (access
= (*access_vec
)[0];
4409 access
= access
->next_grp
)
4410 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true,
4411 EXPR_LOCATION (parm
));
4414 seq
= gsi_seq (gsi
);
4416 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4419 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
4420 it reveals there are components of some aggregates to be scalarized, it runs
4421 the required transformations. */
4423 perform_intra_sra (void)
4428 if (!find_var_candidates ())
4431 if (!scan_function ())
4434 if (!analyze_all_variable_accesses ())
4437 if (sra_modify_function_body ())
4438 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
4440 ret
= TODO_update_ssa
;
4441 initialize_parameter_reductions ();
4443 statistics_counter_event (cfun
, "Scalar replacements created",
4444 sra_stats
.replacements
);
4445 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
4446 statistics_counter_event (cfun
, "Subtree copy stmts",
4447 sra_stats
.subtree_copies
);
4448 statistics_counter_event (cfun
, "Subreplacement stmts",
4449 sra_stats
.subreplacements
);
4450 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
4451 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
4452 sra_stats
.separate_lhs_rhs_handling
);
4455 sra_deinitialize ();
4459 /* Perform early intraprocedural SRA. */
4461 early_intra_sra (void)
4463 sra_mode
= SRA_MODE_EARLY_INTRA
;
4464 return perform_intra_sra ();
4467 /* Perform "late" intraprocedural SRA. */
4469 late_intra_sra (void)
4471 sra_mode
= SRA_MODE_INTRA
;
4472 return perform_intra_sra ();
4477 gate_intra_sra (void)
4479 return flag_tree_sra
!= 0 && dbg_cnt (tree_sra
);
4485 const pass_data pass_data_sra_early
=
4487 GIMPLE_PASS
, /* type */
4489 OPTGROUP_NONE
, /* optinfo_flags */
4490 TV_TREE_SRA
, /* tv_id */
4491 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4492 0, /* properties_provided */
4493 0, /* properties_destroyed */
4494 0, /* todo_flags_start */
4495 TODO_update_ssa
, /* todo_flags_finish */
4498 class pass_sra_early
: public gimple_opt_pass
4501 pass_sra_early (gcc::context
*ctxt
)
4502 : gimple_opt_pass (pass_data_sra_early
, ctxt
)
4505 /* opt_pass methods: */
4506 virtual bool gate (function
*) { return gate_intra_sra (); }
4507 virtual unsigned int execute (function
*) { return early_intra_sra (); }
4509 }; // class pass_sra_early
4514 make_pass_sra_early (gcc::context
*ctxt
)
4516 return new pass_sra_early (ctxt
);
4521 const pass_data pass_data_sra
=
4523 GIMPLE_PASS
, /* type */
4525 OPTGROUP_NONE
, /* optinfo_flags */
4526 TV_TREE_SRA
, /* tv_id */
4527 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4528 0, /* properties_provided */
4529 0, /* properties_destroyed */
4530 TODO_update_address_taken
, /* todo_flags_start */
4531 TODO_update_ssa
, /* todo_flags_finish */
4534 class pass_sra
: public gimple_opt_pass
4537 pass_sra (gcc::context
*ctxt
)
4538 : gimple_opt_pass (pass_data_sra
, ctxt
)
4541 /* opt_pass methods: */
4542 virtual bool gate (function
*) { return gate_intra_sra (); }
4543 virtual unsigned int execute (function
*) { return late_intra_sra (); }
4545 }; // class pass_sra
4550 make_pass_sra (gcc::context
*ctxt
)
4552 return new pass_sra (ctxt
);