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;
933 disqualify_candidate (base
, "Encountered an unconstrained access.");
937 access
= create_access_1 (base
, offset
, size
);
939 access
->type
= TREE_TYPE (expr
);
940 access
->write
= write
;
941 access
->grp_unscalarizable_region
= unscalarizable_region
;
943 access
->reverse
= reverse
;
949 /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length
950 ARRAY_TYPE with fields that are either of gimple register types (excluding
951 bit-fields) or (recursively) scalarizable types. CONST_DECL must be true if
952 we are considering a decl from constant pool. If it is false, char arrays
956 scalarizable_type_p (tree type
, bool const_decl
)
958 if (is_gimple_reg_type (type
))
960 if (type_contains_placeholder_p (type
))
963 bool have_predecessor_field
= false;
964 HOST_WIDE_INT prev_pos
= 0;
966 switch (TREE_CODE (type
))
969 for (tree fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
970 if (TREE_CODE (fld
) == FIELD_DECL
)
972 tree ft
= TREE_TYPE (fld
);
974 if (zerop (DECL_SIZE (fld
)))
977 HOST_WIDE_INT pos
= int_bit_position (fld
);
978 if (have_predecessor_field
982 have_predecessor_field
= true;
985 if (DECL_BIT_FIELD (fld
))
988 if (!scalarizable_type_p (ft
, const_decl
))
996 HOST_WIDE_INT min_elem_size
;
1000 min_elem_size
= BITS_PER_UNIT
;
1002 if (TYPE_DOMAIN (type
) == NULL_TREE
1003 || !tree_fits_shwi_p (TYPE_SIZE (type
))
1004 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type
)))
1005 || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type
))) <= min_elem_size
)
1006 || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type
))))
1008 if (tree_to_shwi (TYPE_SIZE (type
)) == 0
1009 && TYPE_MAX_VALUE (TYPE_DOMAIN (type
)) == NULL_TREE
)
1010 /* Zero-element array, should not prevent scalarization. */
1012 else if ((tree_to_shwi (TYPE_SIZE (type
)) <= 0)
1013 || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type
))))
1014 /* Variable-length array, do not allow scalarization. */
1017 tree elem
= TREE_TYPE (type
);
1018 if (!scalarizable_type_p (elem
, const_decl
))
1027 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1030 contains_view_convert_expr_p (const_tree ref
)
1032 while (handled_component_p (ref
))
1034 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
)
1036 ref
= TREE_OPERAND (ref
, 0);
1042 /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1043 bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1044 it points to will be set if REF contains any of the above or a MEM_REF
1045 expression that effectively performs type conversion. */
1048 contains_vce_or_bfcref_p (const_tree ref
, bool *type_changing_p
= NULL
)
1050 while (handled_component_p (ref
))
1052 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
1053 || (TREE_CODE (ref
) == COMPONENT_REF
1054 && DECL_BIT_FIELD (TREE_OPERAND (ref
, 1))))
1056 if (type_changing_p
)
1057 *type_changing_p
= true;
1060 ref
= TREE_OPERAND (ref
, 0);
1063 if (!type_changing_p
1064 || TREE_CODE (ref
) != MEM_REF
1065 || TREE_CODE (TREE_OPERAND (ref
, 0)) != ADDR_EXPR
)
1068 tree mem
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
1069 if (TYPE_MAIN_VARIANT (TREE_TYPE (ref
))
1070 != TYPE_MAIN_VARIANT (TREE_TYPE (mem
)))
1071 *type_changing_p
= true;
1076 /* Search the given tree for a declaration by skipping handled components and
1077 exclude it from the candidates. */
1080 disqualify_base_of_expr (tree t
, const char *reason
)
1082 t
= get_base_address (t
);
1083 if (t
&& DECL_P (t
))
1084 disqualify_candidate (t
, reason
);
1087 /* Scan expression EXPR and create access structures for all accesses to
1088 candidates for scalarization. Return the created access or NULL if none is
1091 static struct access
*
1092 build_access_from_expr_1 (tree expr
, gimple
*stmt
, bool write
)
1094 struct access
*ret
= NULL
;
1097 if (TREE_CODE (expr
) == BIT_FIELD_REF
1098 || TREE_CODE (expr
) == IMAGPART_EXPR
1099 || TREE_CODE (expr
) == REALPART_EXPR
)
1101 expr
= TREE_OPERAND (expr
, 0);
1105 partial_ref
= false;
1107 if (storage_order_barrier_p (expr
))
1109 disqualify_base_of_expr (expr
, "storage order barrier.");
1113 /* We need to dive through V_C_Es in order to get the size of its parameter
1114 and not the result type. Ada produces such statements. We are also
1115 capable of handling the topmost V_C_E but not any of those buried in other
1116 handled components. */
1117 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
1118 expr
= TREE_OPERAND (expr
, 0);
1120 if (contains_view_convert_expr_p (expr
))
1122 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
1126 if (TREE_THIS_VOLATILE (expr
))
1128 disqualify_base_of_expr (expr
, "part of a volatile reference.");
1132 switch (TREE_CODE (expr
))
1135 if (TREE_CODE (TREE_OPERAND (expr
, 0)) != ADDR_EXPR
)
1143 case ARRAY_RANGE_REF
:
1144 ret
= create_access (expr
, stmt
, write
);
1151 if (write
&& partial_ref
&& ret
)
1152 ret
->grp_partial_lhs
= 1;
1157 /* Scan expression EXPR and create access structures for all accesses to
1158 candidates for scalarization. Return true if any access has been inserted.
1159 STMT must be the statement from which the expression is taken, WRITE must be
1160 true if the expression is a store and false otherwise. */
1163 build_access_from_expr (tree expr
, gimple
*stmt
, bool write
)
1165 struct access
*access
;
1167 access
= build_access_from_expr_1 (expr
, stmt
, write
);
1170 /* This means the aggregate is accesses as a whole in a way other than an
1171 assign statement and thus cannot be removed even if we had a scalar
1172 replacement for everything. */
1173 if (cannot_scalarize_away_bitmap
)
1174 bitmap_set_bit (cannot_scalarize_away_bitmap
, DECL_UID (access
->base
));
1180 /* Return the single non-EH successor edge of BB or NULL if there is none or
1184 single_non_eh_succ (basic_block bb
)
1189 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1190 if (!(e
->flags
& EDGE_EH
))
1200 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1201 there is no alternative spot where to put statements SRA might need to
1202 generate after it. The spot we are looking for is an edge leading to a
1203 single non-EH successor, if it exists and is indeed single. RHS may be
1204 NULL, in that case ignore it. */
1207 disqualify_if_bad_bb_terminating_stmt (gimple
*stmt
, tree lhs
, tree rhs
)
1209 if (stmt_ends_bb_p (stmt
))
1211 if (single_non_eh_succ (gimple_bb (stmt
)))
1214 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
1216 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
1222 /* Return true if the nature of BASE is such that it contains data even if
1223 there is no write to it in the function. */
1226 comes_initialized_p (tree base
)
1228 return TREE_CODE (base
) == PARM_DECL
|| constant_decl_p (base
);
1231 /* Scan expressions occurring in STMT, create access structures for all accesses
1232 to candidates for scalarization and remove those candidates which occur in
1233 statements or expressions that prevent them from being split apart. Return
1234 true if any access has been inserted. */
1237 build_accesses_from_assign (gimple
*stmt
)
1240 struct access
*lacc
, *racc
;
1242 if (!gimple_assign_single_p (stmt
)
1243 /* Scope clobbers don't influence scalarization. */
1244 || gimple_clobber_p (stmt
))
1247 lhs
= gimple_assign_lhs (stmt
);
1248 rhs
= gimple_assign_rhs1 (stmt
);
1250 if (disqualify_if_bad_bb_terminating_stmt (stmt
, lhs
, rhs
))
1253 racc
= build_access_from_expr_1 (rhs
, stmt
, false);
1254 lacc
= build_access_from_expr_1 (lhs
, stmt
, true);
1258 lacc
->grp_assignment_write
= 1;
1259 if (storage_order_barrier_p (rhs
))
1260 lacc
->grp_unscalarizable_region
= 1;
1262 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (lacc
->type
))
1264 bool type_changing_p
= false;
1265 contains_vce_or_bfcref_p (lhs
, &type_changing_p
);
1266 if (type_changing_p
)
1267 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1268 DECL_UID (lacc
->base
));
1274 racc
->grp_assignment_read
= 1;
1275 if (should_scalarize_away_bitmap
&& !is_gimple_reg_type (racc
->type
))
1277 bool type_changing_p
= false;
1278 contains_vce_or_bfcref_p (rhs
, &type_changing_p
);
1280 if (type_changing_p
|| gimple_has_volatile_ops (stmt
))
1281 bitmap_set_bit (cannot_scalarize_away_bitmap
,
1282 DECL_UID (racc
->base
));
1284 bitmap_set_bit (should_scalarize_away_bitmap
,
1285 DECL_UID (racc
->base
));
1287 if (storage_order_barrier_p (lhs
))
1288 racc
->grp_unscalarizable_region
= 1;
1292 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1293 && !lacc
->grp_unscalarizable_region
1294 && !racc
->grp_unscalarizable_region
1295 && AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
1296 && lacc
->size
== racc
->size
1297 && useless_type_conversion_p (lacc
->type
, racc
->type
))
1299 struct assign_link
*link
;
1301 link
= assign_link_pool
.allocate ();
1302 memset (link
, 0, sizeof (struct assign_link
));
1306 add_link_to_rhs (racc
, link
);
1307 add_link_to_lhs (lacc
, link
);
1308 add_access_to_rhs_work_queue (racc
);
1309 add_access_to_lhs_work_queue (lacc
);
1311 /* Let's delay marking the areas as written until propagation of accesses
1312 across link, unless the nature of rhs tells us that its data comes
1314 if (!comes_initialized_p (racc
->base
))
1315 lacc
->write
= false;
1318 return lacc
|| racc
;
1321 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1322 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1325 asm_visit_addr (gimple
*, tree op
, tree
, void *)
1327 op
= get_base_address (op
);
1330 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
1335 /* Scan function and look for interesting expressions and create access
1336 structures for them. Return true iff any access is created. */
1339 scan_function (void)
1344 FOR_EACH_BB_FN (bb
, cfun
)
1346 gimple_stmt_iterator gsi
;
1347 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1349 gimple
*stmt
= gsi_stmt (gsi
);
1353 switch (gimple_code (stmt
))
1356 t
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1358 ret
|= build_access_from_expr (t
, stmt
, false);
1362 ret
|= build_accesses_from_assign (stmt
);
1366 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1367 ret
|= build_access_from_expr (gimple_call_arg (stmt
, i
),
1370 t
= gimple_call_lhs (stmt
);
1371 if (t
&& !disqualify_if_bad_bb_terminating_stmt (stmt
, t
, NULL
))
1372 ret
|= build_access_from_expr (t
, stmt
, true);
1377 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1378 walk_stmt_load_store_addr_ops (asm_stmt
, NULL
, NULL
, NULL
,
1380 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
1382 t
= TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
1383 ret
|= build_access_from_expr (t
, asm_stmt
, false);
1385 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
1387 t
= TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
1388 ret
|= build_access_from_expr (t
, asm_stmt
, true);
1402 /* Helper of QSORT function. There are pointers to accesses in the array. An
1403 access is considered smaller than another if it has smaller offset or if the
1404 offsets are the same but is size is bigger. */
1407 compare_access_positions (const void *a
, const void *b
)
1409 const access_p
*fp1
= (const access_p
*) a
;
1410 const access_p
*fp2
= (const access_p
*) b
;
1411 const access_p f1
= *fp1
;
1412 const access_p f2
= *fp2
;
1414 if (f1
->offset
!= f2
->offset
)
1415 return f1
->offset
< f2
->offset
? -1 : 1;
1417 if (f1
->size
== f2
->size
)
1419 if (f1
->type
== f2
->type
)
1421 /* Put any non-aggregate type before any aggregate type. */
1422 else if (!is_gimple_reg_type (f1
->type
)
1423 && is_gimple_reg_type (f2
->type
))
1425 else if (is_gimple_reg_type (f1
->type
)
1426 && !is_gimple_reg_type (f2
->type
))
1428 /* Put any complex or vector type before any other scalar type. */
1429 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1430 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1431 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1432 || TREE_CODE (f2
->type
) == VECTOR_TYPE
))
1434 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1435 || TREE_CODE (f1
->type
) == VECTOR_TYPE
)
1436 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1437 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1439 /* Put any integral type before any non-integral type. When splicing, we
1440 make sure that those with insufficient precision and occupying the
1441 same space are not scalarized. */
1442 else if (INTEGRAL_TYPE_P (f1
->type
)
1443 && !INTEGRAL_TYPE_P (f2
->type
))
1445 else if (!INTEGRAL_TYPE_P (f1
->type
)
1446 && INTEGRAL_TYPE_P (f2
->type
))
1448 /* Put the integral type with the bigger precision first. */
1449 else if (INTEGRAL_TYPE_P (f1
->type
)
1450 && INTEGRAL_TYPE_P (f2
->type
)
1451 && (TYPE_PRECISION (f2
->type
) != TYPE_PRECISION (f1
->type
)))
1452 return TYPE_PRECISION (f2
->type
) - TYPE_PRECISION (f1
->type
);
1453 /* Stabilize the sort. */
1454 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1457 /* We want the bigger accesses first, thus the opposite operator in the next
1459 return f1
->size
> f2
->size
? -1 : 1;
1463 /* Append a name of the declaration to the name obstack. A helper function for
1467 make_fancy_decl_name (tree decl
)
1471 tree name
= DECL_NAME (decl
);
1473 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1474 IDENTIFIER_LENGTH (name
));
1477 sprintf (buffer
, "D%u", DECL_UID (decl
));
1478 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1482 /* Helper for make_fancy_name. */
1485 make_fancy_name_1 (tree expr
)
1492 make_fancy_decl_name (expr
);
1496 switch (TREE_CODE (expr
))
1499 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1500 obstack_1grow (&name_obstack
, '$');
1501 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1505 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1506 obstack_1grow (&name_obstack
, '$');
1507 /* Arrays with only one element may not have a constant as their
1509 index
= TREE_OPERAND (expr
, 1);
1510 if (TREE_CODE (index
) != INTEGER_CST
)
1512 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1513 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1517 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1521 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1522 if (!integer_zerop (TREE_OPERAND (expr
, 1)))
1524 obstack_1grow (&name_obstack
, '$');
1525 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
,
1526 TREE_INT_CST_LOW (TREE_OPERAND (expr
, 1)));
1527 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1534 gcc_unreachable (); /* we treat these as scalars. */
1541 /* Create a human readable name for replacement variable of ACCESS. */
1544 make_fancy_name (tree expr
)
1546 make_fancy_name_1 (expr
);
1547 obstack_1grow (&name_obstack
, '\0');
1548 return XOBFINISH (&name_obstack
, char *);
1551 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1552 EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1553 something for which get_addr_base_and_unit_offset returns NULL, gsi must
1554 be non-NULL and is used to insert new statements either before or below
1555 the current one as specified by INSERT_AFTER. This function is not capable
1556 of handling bitfields. */
1559 build_ref_for_offset (location_t loc
, tree base
, poly_int64 offset
,
1560 bool reverse
, tree exp_type
, gimple_stmt_iterator
*gsi
,
1563 tree prev_base
= base
;
1566 poly_int64 base_offset
;
1567 unsigned HOST_WIDE_INT misalign
;
1570 /* Preserve address-space information. */
1571 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (base
));
1572 if (as
!= TYPE_ADDR_SPACE (exp_type
))
1573 exp_type
= build_qualified_type (exp_type
,
1574 TYPE_QUALS (exp_type
)
1575 | ENCODE_QUAL_ADDR_SPACE (as
));
1577 poly_int64 byte_offset
= exact_div (offset
, BITS_PER_UNIT
);
1578 get_object_alignment_1 (base
, &align
, &misalign
);
1579 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1581 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1582 offset such as array[var_index]. */
1588 gcc_checking_assert (gsi
);
1589 tmp
= make_ssa_name (build_pointer_type (TREE_TYPE (prev_base
)));
1590 addr
= build_fold_addr_expr (unshare_expr (prev_base
));
1591 STRIP_USELESS_TYPE_CONVERSION (addr
);
1592 stmt
= gimple_build_assign (tmp
, addr
);
1593 gimple_set_location (stmt
, loc
);
1595 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
1597 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1599 off
= build_int_cst (reference_alias_ptr_type (prev_base
), byte_offset
);
1602 else if (TREE_CODE (base
) == MEM_REF
)
1604 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1605 base_offset
+ byte_offset
);
1606 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1607 base
= unshare_expr (TREE_OPERAND (base
, 0));
1611 off
= build_int_cst (reference_alias_ptr_type (prev_base
),
1612 base_offset
+ byte_offset
);
1613 base
= build_fold_addr_expr (unshare_expr (base
));
1616 unsigned int align_bound
= known_alignment (misalign
+ offset
);
1617 if (align_bound
!= 0)
1618 align
= MIN (align
, align_bound
);
1619 if (align
!= TYPE_ALIGN (exp_type
))
1620 exp_type
= build_aligned_type (exp_type
, align
);
1622 mem_ref
= fold_build2_loc (loc
, MEM_REF
, exp_type
, base
, off
);
1623 REF_REVERSE_STORAGE_ORDER (mem_ref
) = reverse
;
1624 if (TREE_THIS_VOLATILE (prev_base
))
1625 TREE_THIS_VOLATILE (mem_ref
) = 1;
1626 if (TREE_SIDE_EFFECTS (prev_base
))
1627 TREE_SIDE_EFFECTS (mem_ref
) = 1;
1631 /* Construct and return a memory reference that is equal to a portion of
1632 MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1635 build_reconstructed_reference (location_t
, tree base
, struct access
*model
)
1637 tree expr
= model
->expr
, prev_expr
= NULL
;
1638 while (!types_compatible_p (TREE_TYPE (expr
), TREE_TYPE (base
)))
1640 if (!handled_component_p (expr
))
1643 expr
= TREE_OPERAND (expr
, 0);
1646 /* Guard against broken VIEW_CONVERT_EXPRs... */
1650 TREE_OPERAND (prev_expr
, 0) = base
;
1651 tree ref
= unshare_expr (model
->expr
);
1652 TREE_OPERAND (prev_expr
, 0) = expr
;
1656 /* Construct a memory reference to a part of an aggregate BASE at the given
1657 OFFSET and of the same type as MODEL. In case this is a reference to a
1658 bit-field, the function will replicate the last component_ref of model's
1659 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1660 build_ref_for_offset. */
1663 build_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1664 struct access
*model
, gimple_stmt_iterator
*gsi
,
1667 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1668 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1670 /* This access represents a bit-field. */
1671 tree t
, exp_type
, fld
= TREE_OPERAND (model
->expr
, 1);
1673 offset
-= int_bit_position (fld
);
1674 exp_type
= TREE_TYPE (TREE_OPERAND (model
->expr
, 0));
1675 t
= build_ref_for_offset (loc
, base
, offset
, model
->reverse
, exp_type
,
1677 /* The flag will be set on the record type. */
1678 REF_REVERSE_STORAGE_ORDER (t
) = 0;
1679 return fold_build3_loc (loc
, COMPONENT_REF
, TREE_TYPE (fld
), t
, fld
,
1685 if (model
->grp_same_access_path
1686 && !TREE_THIS_VOLATILE (base
)
1687 && (TYPE_ADDR_SPACE (TREE_TYPE (base
))
1688 == TYPE_ADDR_SPACE (TREE_TYPE (model
->expr
)))
1689 && offset
<= model
->offset
1690 /* build_reconstructed_reference can still fail if we have already
1691 massaged BASE because of another type incompatibility. */
1692 && (res
= build_reconstructed_reference (loc
, base
, model
)))
1695 return build_ref_for_offset (loc
, base
, offset
, model
->reverse
,
1696 model
->type
, gsi
, insert_after
);
1700 /* Attempt to build a memory reference that we could but into a gimple
1701 debug_bind statement. Similar to build_ref_for_model but punts if it has to
1702 create statements and return s NULL instead. This function also ignores
1703 alignment issues and so its results should never end up in non-debug
1707 build_debug_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1708 struct access
*model
)
1710 poly_int64 base_offset
;
1713 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1714 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1717 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1720 if (TREE_CODE (base
) == MEM_REF
)
1722 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1723 base_offset
+ offset
/ BITS_PER_UNIT
);
1724 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1725 base
= unshare_expr (TREE_OPERAND (base
, 0));
1729 off
= build_int_cst (reference_alias_ptr_type (base
),
1730 base_offset
+ offset
/ BITS_PER_UNIT
);
1731 base
= build_fold_addr_expr (unshare_expr (base
));
1734 return fold_build2_loc (loc
, MEM_REF
, model
->type
, base
, off
);
1737 /* Construct a memory reference consisting of component_refs and array_refs to
1738 a part of an aggregate *RES (which is of type TYPE). The requested part
1739 should have type EXP_TYPE at be the given OFFSET. This function might not
1740 succeed, it returns true when it does and only then *RES points to something
1741 meaningful. This function should be used only to build expressions that we
1742 might need to present to user (e.g. in warnings). In all other situations,
1743 build_ref_for_model or build_ref_for_offset should be used instead. */
1746 build_user_friendly_ref_for_offset (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1752 tree tr_size
, index
, minidx
;
1753 HOST_WIDE_INT el_size
;
1755 if (offset
== 0 && exp_type
1756 && types_compatible_p (exp_type
, type
))
1759 switch (TREE_CODE (type
))
1762 case QUAL_UNION_TYPE
:
1764 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1766 HOST_WIDE_INT pos
, size
;
1767 tree tr_pos
, expr
, *expr_ptr
;
1769 if (TREE_CODE (fld
) != FIELD_DECL
)
1772 tr_pos
= bit_position (fld
);
1773 if (!tr_pos
|| !tree_fits_uhwi_p (tr_pos
))
1775 pos
= tree_to_uhwi (tr_pos
);
1776 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1777 tr_size
= DECL_SIZE (fld
);
1778 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1780 size
= tree_to_uhwi (tr_size
);
1786 else if (pos
> offset
|| (pos
+ size
) <= offset
)
1789 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1792 if (build_user_friendly_ref_for_offset (expr_ptr
, TREE_TYPE (fld
),
1793 offset
- pos
, exp_type
))
1802 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1803 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1805 el_size
= tree_to_uhwi (tr_size
);
1807 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1808 if (TREE_CODE (minidx
) != INTEGER_CST
|| el_size
== 0)
1810 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1811 if (!integer_zerop (minidx
))
1812 index
= int_const_binop (PLUS_EXPR
, index
, minidx
);
1813 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1814 NULL_TREE
, NULL_TREE
);
1815 offset
= offset
% el_size
;
1816 type
= TREE_TYPE (type
);
1831 /* Print message to dump file why a variable was rejected. */
1834 reject (tree var
, const char *msg
)
1836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1838 fprintf (dump_file
, "Rejected (%d): %s: ", DECL_UID (var
), msg
);
1839 print_generic_expr (dump_file
, var
);
1840 fprintf (dump_file
, "\n");
1844 /* Return true if VAR is a candidate for SRA. */
1847 maybe_add_sra_candidate (tree var
)
1849 tree type
= TREE_TYPE (var
);
1853 if (!AGGREGATE_TYPE_P (type
))
1855 reject (var
, "not aggregate");
1858 /* Allow constant-pool entries that "need to live in memory". */
1859 if (needs_to_live_in_memory (var
) && !constant_decl_p (var
))
1861 reject (var
, "needs to live in memory");
1864 if (TREE_THIS_VOLATILE (var
))
1866 reject (var
, "is volatile");
1869 if (!COMPLETE_TYPE_P (type
))
1871 reject (var
, "has incomplete type");
1874 if (!tree_fits_uhwi_p (TYPE_SIZE (type
)))
1876 reject (var
, "type size not fixed");
1879 if (tree_to_uhwi (TYPE_SIZE (type
)) == 0)
1881 reject (var
, "type size is zero");
1884 if (type_internals_preclude_sra_p (type
, &msg
))
1889 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1890 we also want to schedule it rather late. Thus we ignore it in
1892 (sra_mode
== SRA_MODE_EARLY_INTRA
1893 && is_va_list_type (type
)))
1895 reject (var
, "is va_list");
1899 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1900 slot
= candidates
->find_slot_with_hash (var
, DECL_UID (var
), INSERT
);
1903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1905 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1906 print_generic_expr (dump_file
, var
);
1907 fprintf (dump_file
, "\n");
1913 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1914 those with type which is suitable for scalarization. */
1917 find_var_candidates (void)
1923 for (parm
= DECL_ARGUMENTS (current_function_decl
);
1925 parm
= DECL_CHAIN (parm
))
1926 ret
|= maybe_add_sra_candidate (parm
);
1928 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
1933 ret
|= maybe_add_sra_candidate (var
);
1939 /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
1940 ending either with a DECL or a MEM_REF with zero offset. */
1943 path_comparable_for_same_access (tree expr
)
1945 while (handled_component_p (expr
))
1947 if (TREE_CODE (expr
) == ARRAY_REF
)
1949 /* SSA name indices can occur here too when the array is of sie one.
1950 But we cannot just re-use array_refs with SSA names elsewhere in
1951 the function, so disallow non-constant indices. TODO: Remove this
1952 limitation after teaching build_reconstructed_reference to replace
1953 the index with the index type lower bound. */
1954 if (TREE_CODE (TREE_OPERAND (expr
, 1)) != INTEGER_CST
)
1957 expr
= TREE_OPERAND (expr
, 0);
1960 if (TREE_CODE (expr
) == MEM_REF
)
1962 if (!zerop (TREE_OPERAND (expr
, 1)))
1966 gcc_assert (DECL_P (expr
));
1971 /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
1972 true if the chain of these handled components are exactly the same as EXP2
1973 and the expression under them is the same DECL or an equivalent MEM_REF.
1974 The reference picked by compare_access_positions must go to EXP1. */
1977 same_access_path_p (tree exp1
, tree exp2
)
1979 if (TREE_CODE (exp1
) != TREE_CODE (exp2
))
1981 /* Special case single-field structures loaded sometimes as the field
1982 and sometimes as the structure. If the field is of a scalar type,
1983 compare_access_positions will put it into exp1.
1985 TODO: The gimple register type condition can be removed if teach
1986 compare_access_positions to put inner types first. */
1987 if (is_gimple_reg_type (TREE_TYPE (exp1
))
1988 && TREE_CODE (exp1
) == COMPONENT_REF
1989 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1
, 0)))
1990 == TYPE_MAIN_VARIANT (TREE_TYPE (exp2
))))
1991 exp1
= TREE_OPERAND (exp1
, 0);
1996 if (!operand_equal_p (exp1
, exp2
, OEP_ADDRESS_OF
))
2002 /* Sort all accesses for the given variable, check for partial overlaps and
2003 return NULL if there are any. If there are none, pick a representative for
2004 each combination of offset and size and create a linked list out of them.
2005 Return the pointer to the first representative and make sure it is the first
2006 one in the vector of accesses. */
2008 static struct access
*
2009 sort_and_splice_var_accesses (tree var
)
2011 int i
, j
, access_count
;
2012 struct access
*res
, **prev_acc_ptr
= &res
;
2013 vec
<access_p
> *access_vec
;
2015 HOST_WIDE_INT low
= -1, high
= 0;
2017 access_vec
= get_base_access_vector (var
);
2020 access_count
= access_vec
->length ();
2022 /* Sort by <OFFSET, SIZE>. */
2023 access_vec
->qsort (compare_access_positions
);
2026 while (i
< access_count
)
2028 struct access
*access
= (*access_vec
)[i
];
2029 bool grp_write
= access
->write
;
2030 bool grp_read
= !access
->write
;
2031 bool grp_scalar_write
= access
->write
2032 && is_gimple_reg_type (access
->type
);
2033 bool grp_scalar_read
= !access
->write
2034 && is_gimple_reg_type (access
->type
);
2035 bool grp_assignment_read
= access
->grp_assignment_read
;
2036 bool grp_assignment_write
= access
->grp_assignment_write
;
2037 bool multiple_scalar_reads
= false;
2038 bool grp_partial_lhs
= access
->grp_partial_lhs
;
2039 bool first_scalar
= is_gimple_reg_type (access
->type
);
2040 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
2041 bool grp_same_access_path
= true;
2042 bool bf_non_full_precision
2043 = (INTEGRAL_TYPE_P (access
->type
)
2044 && TYPE_PRECISION (access
->type
) != access
->size
2045 && TREE_CODE (access
->expr
) == COMPONENT_REF
2046 && DECL_BIT_FIELD (TREE_OPERAND (access
->expr
, 1)));
2048 if (first
|| access
->offset
>= high
)
2051 low
= access
->offset
;
2052 high
= access
->offset
+ access
->size
;
2054 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
2057 gcc_assert (access
->offset
>= low
2058 && access
->offset
+ access
->size
<= high
);
2060 grp_same_access_path
= path_comparable_for_same_access (access
->expr
);
2063 while (j
< access_count
)
2065 struct access
*ac2
= (*access_vec
)[j
];
2066 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
2071 grp_scalar_write
= (grp_scalar_write
2072 || is_gimple_reg_type (ac2
->type
));
2077 if (is_gimple_reg_type (ac2
->type
))
2079 if (grp_scalar_read
)
2080 multiple_scalar_reads
= true;
2082 grp_scalar_read
= true;
2085 grp_assignment_read
|= ac2
->grp_assignment_read
;
2086 grp_assignment_write
|= ac2
->grp_assignment_write
;
2087 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
2088 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
2089 relink_to_new_repr (access
, ac2
);
2091 /* If there are both aggregate-type and scalar-type accesses with
2092 this combination of size and offset, the comparison function
2093 should have put the scalars first. */
2094 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
2095 /* It also prefers integral types to non-integral. However, when the
2096 precision of the selected type does not span the entire area and
2097 should also be used for a non-integer (i.e. float), we must not
2098 let that happen. Normally analyze_access_subtree expands the type
2099 to cover the entire area but for bit-fields it doesn't. */
2100 if (bf_non_full_precision
&& !INTEGRAL_TYPE_P (ac2
->type
))
2102 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2104 fprintf (dump_file
, "Cannot scalarize the following access "
2105 "because insufficient precision integer type was "
2107 dump_access (dump_file
, access
, false);
2109 unscalarizable_region
= true;
2112 if (grp_same_access_path
2113 && !same_access_path_p (access
->expr
, ac2
->expr
))
2114 grp_same_access_path
= false;
2116 ac2
->group_representative
= access
;
2122 access
->group_representative
= access
;
2123 access
->grp_write
= grp_write
;
2124 access
->grp_read
= grp_read
;
2125 access
->grp_scalar_read
= grp_scalar_read
;
2126 access
->grp_scalar_write
= grp_scalar_write
;
2127 access
->grp_assignment_read
= grp_assignment_read
;
2128 access
->grp_assignment_write
= grp_assignment_write
;
2129 access
->grp_hint
= multiple_scalar_reads
&& !constant_decl_p (var
);
2130 access
->grp_partial_lhs
= grp_partial_lhs
;
2131 access
->grp_unscalarizable_region
= unscalarizable_region
;
2132 access
->grp_same_access_path
= grp_same_access_path
;
2134 *prev_acc_ptr
= access
;
2135 prev_acc_ptr
= &access
->next_grp
;
2138 gcc_assert (res
== (*access_vec
)[0]);
2142 /* Create a variable for the given ACCESS which determines the type, name and a
2143 few other properties. Return the variable declaration and store it also to
2144 ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2145 default-definition SSA name on on in order to facilitate an uninitialized
2146 warning. It is used instead of the actual ACCESS type if that is not of a
2147 gimple register type. */
2150 create_access_replacement (struct access
*access
, tree reg_type
= NULL_TREE
)
2154 tree type
= access
->type
;
2155 if (reg_type
&& !is_gimple_reg_type (type
))
2158 if (access
->grp_to_be_debug_replaced
)
2160 repl
= create_tmp_var_raw (access
->type
);
2161 DECL_CONTEXT (repl
) = current_function_decl
;
2164 /* Drop any special alignment on the type if it's not on the main
2165 variant. This avoids issues with weirdo ABIs like AAPCS. */
2166 repl
= create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type
),
2167 TYPE_QUALS (type
)), "SR");
2168 if (TREE_CODE (type
) == COMPLEX_TYPE
2169 || TREE_CODE (type
) == VECTOR_TYPE
)
2171 if (!access
->grp_partial_lhs
)
2172 DECL_GIMPLE_REG_P (repl
) = 1;
2174 else if (access
->grp_partial_lhs
2175 && is_gimple_reg_type (type
))
2176 TREE_ADDRESSABLE (repl
) = 1;
2178 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
2179 DECL_ARTIFICIAL (repl
) = 1;
2180 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
2182 if (DECL_NAME (access
->base
)
2183 && !DECL_IGNORED_P (access
->base
)
2184 && !DECL_ARTIFICIAL (access
->base
))
2186 char *pretty_name
= make_fancy_name (access
->expr
);
2187 tree debug_expr
= unshare_expr_without_location (access
->expr
), d
;
2190 DECL_NAME (repl
) = get_identifier (pretty_name
);
2191 DECL_NAMELESS (repl
) = 1;
2192 obstack_free (&name_obstack
, pretty_name
);
2194 /* Get rid of any SSA_NAMEs embedded in debug_expr,
2195 as DECL_DEBUG_EXPR isn't considered when looking for still
2196 used SSA_NAMEs and thus they could be freed. All debug info
2197 generation cares is whether something is constant or variable
2198 and that get_ref_base_and_extent works properly on the
2199 expression. It cannot handle accesses at a non-constant offset
2200 though, so just give up in those cases. */
2201 for (d
= debug_expr
;
2202 !fail
&& (handled_component_p (d
) || TREE_CODE (d
) == MEM_REF
);
2203 d
= TREE_OPERAND (d
, 0))
2204 switch (TREE_CODE (d
))
2207 case ARRAY_RANGE_REF
:
2208 if (TREE_OPERAND (d
, 1)
2209 && TREE_CODE (TREE_OPERAND (d
, 1)) != INTEGER_CST
)
2211 if (TREE_OPERAND (d
, 3)
2212 && TREE_CODE (TREE_OPERAND (d
, 3)) != INTEGER_CST
)
2216 if (TREE_OPERAND (d
, 2)
2217 && TREE_CODE (TREE_OPERAND (d
, 2)) != INTEGER_CST
)
2221 if (TREE_CODE (TREE_OPERAND (d
, 0)) != ADDR_EXPR
)
2224 d
= TREE_OPERAND (d
, 0);
2231 SET_DECL_DEBUG_EXPR (repl
, debug_expr
);
2232 DECL_HAS_DEBUG_EXPR_P (repl
) = 1;
2234 if (access
->grp_no_warning
)
2235 TREE_NO_WARNING (repl
) = 1;
2237 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
2240 TREE_NO_WARNING (repl
) = 1;
2244 if (access
->grp_to_be_debug_replaced
)
2246 fprintf (dump_file
, "Created a debug-only replacement for ");
2247 print_generic_expr (dump_file
, access
->base
);
2248 fprintf (dump_file
, " offset: %u, size: %u\n",
2249 (unsigned) access
->offset
, (unsigned) access
->size
);
2253 fprintf (dump_file
, "Created a replacement for ");
2254 print_generic_expr (dump_file
, access
->base
);
2255 fprintf (dump_file
, " offset: %u, size: %u: ",
2256 (unsigned) access
->offset
, (unsigned) access
->size
);
2257 print_generic_expr (dump_file
, repl
);
2258 fprintf (dump_file
, "\n");
2261 sra_stats
.replacements
++;
2266 /* Return ACCESS scalar replacement, which must exist. */
2269 get_access_replacement (struct access
*access
)
2271 gcc_checking_assert (access
->replacement_decl
);
2272 return access
->replacement_decl
;
2276 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2277 linked list along the way. Stop when *ACCESS is NULL or the access pointed
2278 to it is not "within" the root. Return false iff some accesses partially
2282 build_access_subtree (struct access
**access
)
2284 struct access
*root
= *access
, *last_child
= NULL
;
2285 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2287 *access
= (*access
)->next_grp
;
2288 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
2291 root
->first_child
= *access
;
2293 last_child
->next_sibling
= *access
;
2294 last_child
= *access
;
2295 (*access
)->parent
= root
;
2296 (*access
)->grp_write
|= root
->grp_write
;
2298 if (!build_access_subtree (access
))
2302 if (*access
&& (*access
)->offset
< limit
)
2308 /* Build a tree of access representatives, ACCESS is the pointer to the first
2309 one, others are linked in a list by the next_grp field. Return false iff
2310 some accesses partially overlap. */
2313 build_access_trees (struct access
*access
)
2317 struct access
*root
= access
;
2319 if (!build_access_subtree (&access
))
2321 root
->next_grp
= access
;
2326 /* Traverse the access forest where ROOT is the first root and verify that
2327 various important invariants hold true. */
2330 verify_sra_access_forest (struct access
*root
)
2332 struct access
*access
= root
;
2333 tree first_base
= root
->base
;
2334 gcc_assert (DECL_P (first_base
));
2337 gcc_assert (access
->base
== first_base
);
2339 gcc_assert (access
->offset
>= access
->parent
->offset
2340 && access
->size
<= access
->parent
->size
);
2341 if (access
->next_sibling
)
2342 gcc_assert (access
->next_sibling
->offset
2343 >= access
->offset
+ access
->size
);
2345 poly_int64 poffset
, psize
, pmax_size
;
2347 tree base
= get_ref_base_and_extent (access
->expr
, &poffset
, &psize
,
2348 &pmax_size
, &reverse
);
2349 HOST_WIDE_INT offset
, size
, max_size
;
2350 if (!poffset
.is_constant (&offset
)
2351 || !psize
.is_constant (&size
)
2352 || !pmax_size
.is_constant (&max_size
))
2354 gcc_assert (base
== first_base
);
2355 gcc_assert (offset
== access
->offset
);
2356 gcc_assert (access
->grp_unscalarizable_region
2357 || size
== max_size
);
2358 gcc_assert (!is_gimple_reg_type (access
->type
)
2359 || max_size
== access
->size
);
2360 gcc_assert (reverse
== access
->reverse
);
2362 if (access
->first_child
)
2364 gcc_assert (access
->first_child
->parent
== access
);
2365 access
= access
->first_child
;
2367 else if (access
->next_sibling
)
2369 gcc_assert (access
->next_sibling
->parent
== access
->parent
);
2370 access
= access
->next_sibling
;
2374 while (access
->parent
&& !access
->next_sibling
)
2375 access
= access
->parent
;
2376 if (access
->next_sibling
)
2377 access
= access
->next_sibling
;
2380 gcc_assert (access
== root
);
2381 root
= root
->next_grp
;
2389 /* Verify access forests of all candidates with accesses by calling
2390 verify_access_forest on each on them. */
2393 verify_all_sra_access_forests (void)
2397 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
2399 tree var
= candidate (i
);
2400 struct access
*access
= get_first_repr_for_decl (var
);
2403 gcc_assert (access
->base
== var
);
2404 verify_sra_access_forest (access
);
2409 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2413 expr_with_var_bounded_array_refs_p (tree expr
)
2415 while (handled_component_p (expr
))
2417 if (TREE_CODE (expr
) == ARRAY_REF
2418 && !tree_fits_shwi_p (array_ref_low_bound (expr
)))
2420 expr
= TREE_OPERAND (expr
, 0);
2425 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2426 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2427 is set, we are totally scalarizing the aggregate. Also set all sorts of
2428 access flags appropriately along the way, notably always set grp_read and
2429 grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2432 Creating a replacement for a scalar access is considered beneficial if its
2433 grp_hint ot TOTALLY is set (this means either that there is more than one
2434 direct read access or that we are attempting total scalarization) or
2435 according to the following table:
2437 Access written to through a scalar type (once or more times)
2439 | Written to in an assignment statement
2441 | | Access read as scalar _once_
2443 | | | Read in an assignment statement
2445 | | | | Scalarize Comment
2446 -----------------------------------------------------------------------------
2447 0 0 0 0 No access for the scalar
2448 0 0 0 1 No access for the scalar
2449 0 0 1 0 No Single read - won't help
2450 0 0 1 1 No The same case
2451 0 1 0 0 No access for the scalar
2452 0 1 0 1 No access for the scalar
2453 0 1 1 0 Yes s = *g; return s.i;
2454 0 1 1 1 Yes The same case as above
2455 1 0 0 0 No Won't help
2456 1 0 0 1 Yes s.i = 1; *g = s;
2457 1 0 1 0 Yes s.i = 5; g = s.i;
2458 1 0 1 1 Yes The same case as above
2459 1 1 0 0 No Won't help.
2460 1 1 0 1 Yes s.i = 1; *g = s;
2461 1 1 1 0 Yes s = *g; return s.i;
2462 1 1 1 1 Yes Any of the above yeses */
2465 analyze_access_subtree (struct access
*root
, struct access
*parent
,
2466 bool allow_replacements
, bool totally
)
2468 struct access
*child
;
2469 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2470 HOST_WIDE_INT covered_to
= root
->offset
;
2471 bool scalar
= is_gimple_reg_type (root
->type
);
2472 bool hole
= false, sth_created
= false;
2476 if (parent
->grp_read
)
2478 if (parent
->grp_assignment_read
)
2479 root
->grp_assignment_read
= 1;
2480 if (parent
->grp_write
)
2481 root
->grp_write
= 1;
2482 if (parent
->grp_assignment_write
)
2483 root
->grp_assignment_write
= 1;
2484 if (!parent
->grp_same_access_path
)
2485 root
->grp_same_access_path
= 0;
2488 if (root
->grp_unscalarizable_region
)
2489 allow_replacements
= false;
2491 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
2492 allow_replacements
= false;
2494 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
2496 hole
|= covered_to
< child
->offset
;
2497 sth_created
|= analyze_access_subtree (child
, root
,
2498 allow_replacements
&& !scalar
,
2501 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
2502 if (child
->grp_covered
)
2503 covered_to
+= child
->size
;
2508 if (allow_replacements
&& scalar
&& !root
->first_child
2509 && (totally
|| !root
->grp_total_scalarization
)
2512 || ((root
->grp_scalar_read
|| root
->grp_assignment_read
)
2513 && (root
->grp_scalar_write
|| root
->grp_assignment_write
))))
2515 /* Always create access replacements that cover the whole access.
2516 For integral types this means the precision has to match.
2517 Avoid assumptions based on the integral type kind, too. */
2518 if (INTEGRAL_TYPE_P (root
->type
)
2519 && (TREE_CODE (root
->type
) != INTEGER_TYPE
2520 || TYPE_PRECISION (root
->type
) != root
->size
)
2521 /* But leave bitfield accesses alone. */
2522 && (TREE_CODE (root
->expr
) != COMPONENT_REF
2523 || !DECL_BIT_FIELD (TREE_OPERAND (root
->expr
, 1))))
2525 tree rt
= root
->type
;
2526 gcc_assert ((root
->offset
% BITS_PER_UNIT
) == 0
2527 && (root
->size
% BITS_PER_UNIT
) == 0);
2528 root
->type
= build_nonstandard_integer_type (root
->size
,
2529 TYPE_UNSIGNED (rt
));
2530 root
->expr
= build_ref_for_offset (UNKNOWN_LOCATION
, root
->base
,
2531 root
->offset
, root
->reverse
,
2532 root
->type
, NULL
, false);
2534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2536 fprintf (dump_file
, "Changing the type of a replacement for ");
2537 print_generic_expr (dump_file
, root
->base
);
2538 fprintf (dump_file
, " offset: %u, size: %u ",
2539 (unsigned) root
->offset
, (unsigned) root
->size
);
2540 fprintf (dump_file
, " to an integer.\n");
2544 root
->grp_to_be_replaced
= 1;
2545 root
->replacement_decl
= create_access_replacement (root
);
2551 if (allow_replacements
2552 && scalar
&& !root
->first_child
2553 && !root
->grp_total_scalarization
2554 && (root
->grp_scalar_write
|| root
->grp_assignment_write
)
2555 && !bitmap_bit_p (cannot_scalarize_away_bitmap
,
2556 DECL_UID (root
->base
)))
2558 gcc_checking_assert (!root
->grp_scalar_read
2559 && !root
->grp_assignment_read
);
2561 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2563 root
->grp_to_be_debug_replaced
= 1;
2564 root
->replacement_decl
= create_access_replacement (root
);
2568 if (covered_to
< limit
)
2570 if (scalar
|| !allow_replacements
)
2571 root
->grp_total_scalarization
= 0;
2574 if (!hole
|| totally
)
2575 root
->grp_covered
= 1;
2576 else if (root
->grp_write
|| comes_initialized_p (root
->base
))
2577 root
->grp_unscalarized_data
= 1; /* not covered and written to */
2581 /* Analyze all access trees linked by next_grp by the means of
2582 analyze_access_subtree. */
2584 analyze_access_trees (struct access
*access
)
2590 if (analyze_access_subtree (access
, NULL
, true,
2591 access
->grp_total_scalarization
))
2593 access
= access
->next_grp
;
2599 /* Return true iff a potential new child of ACC at offset OFFSET and with size
2600 SIZE would conflict with an already existing one. If exactly such a child
2601 already exists in ACC, store a pointer to it in EXACT_MATCH. */
2604 child_would_conflict_in_acc (struct access
*acc
, HOST_WIDE_INT norm_offset
,
2605 HOST_WIDE_INT size
, struct access
**exact_match
)
2607 struct access
*child
;
2609 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
2611 if (child
->offset
== norm_offset
&& child
->size
== size
)
2613 *exact_match
= child
;
2617 if (child
->offset
< norm_offset
+ size
2618 && child
->offset
+ child
->size
> norm_offset
)
2625 /* Create a new child access of PARENT, with all properties just like MODEL
2626 except for its offset and with its grp_write false and grp_read true.
2627 Return the new access or NULL if it cannot be created. Note that this
2628 access is created long after all splicing and sorting, it's not located in
2629 any access vector and is automatically a representative of its group. Set
2630 the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
2632 static struct access
*
2633 create_artificial_child_access (struct access
*parent
, struct access
*model
,
2634 HOST_WIDE_INT new_offset
,
2635 bool set_grp_read
, bool set_grp_write
)
2637 struct access
**child
;
2638 tree expr
= parent
->base
;
2640 gcc_assert (!model
->grp_unscalarizable_region
);
2642 struct access
*access
= access_pool
.allocate ();
2643 memset (access
, 0, sizeof (struct access
));
2644 if (!build_user_friendly_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
2647 access
->grp_no_warning
= true;
2648 expr
= build_ref_for_model (EXPR_LOCATION (parent
->base
), parent
->base
,
2649 new_offset
, model
, NULL
, false);
2652 access
->base
= parent
->base
;
2653 access
->expr
= expr
;
2654 access
->offset
= new_offset
;
2655 access
->size
= model
->size
;
2656 access
->type
= model
->type
;
2657 access
->parent
= parent
;
2658 access
->grp_read
= set_grp_read
;
2659 access
->grp_write
= set_grp_write
;
2660 access
->reverse
= model
->reverse
;
2662 child
= &parent
->first_child
;
2663 while (*child
&& (*child
)->offset
< new_offset
)
2664 child
= &(*child
)->next_sibling
;
2666 access
->next_sibling
= *child
;
2673 /* Beginning with ACCESS, traverse its whole access subtree and mark all
2674 sub-trees as written to. If any of them has not been marked so previously
2675 and has assignment links leading from it, re-enqueue it. */
2678 subtree_mark_written_and_rhs_enqueue (struct access
*access
)
2680 if (access
->grp_write
)
2682 access
->grp_write
= true;
2683 add_access_to_rhs_work_queue (access
);
2685 struct access
*child
;
2686 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2687 subtree_mark_written_and_rhs_enqueue (child
);
2690 /* Propagate subaccesses and grp_write flags of RACC across an assignment link
2691 to LACC. Enqueue sub-accesses as necessary so that the write flag is
2692 propagated transitively. Return true if anything changed. Additionally, if
2693 RACC is a scalar access but LACC is not, change the type of the latter, if
2697 propagate_subaccesses_from_rhs (struct access
*lacc
, struct access
*racc
)
2699 struct access
*rchild
;
2700 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
2703 /* IF the LHS is still not marked as being written to, we only need to do so
2704 if the RHS at this level actually was. */
2705 if (!lacc
->grp_write
)
2707 gcc_checking_assert (!comes_initialized_p (racc
->base
));
2708 if (racc
->grp_write
)
2710 subtree_mark_written_and_rhs_enqueue (lacc
);
2715 if (is_gimple_reg_type (lacc
->type
)
2716 || lacc
->grp_unscalarizable_region
2717 || racc
->grp_unscalarizable_region
)
2719 if (!lacc
->grp_write
)
2722 subtree_mark_written_and_rhs_enqueue (lacc
);
2727 if (is_gimple_reg_type (racc
->type
))
2729 if (!lacc
->grp_write
)
2732 subtree_mark_written_and_rhs_enqueue (lacc
);
2734 if (!lacc
->first_child
&& !racc
->first_child
)
2736 tree t
= lacc
->base
;
2738 lacc
->type
= racc
->type
;
2739 if (build_user_friendly_ref_for_offset (&t
, TREE_TYPE (t
),
2740 lacc
->offset
, racc
->type
))
2743 lacc
->grp_same_access_path
= true;
2747 lacc
->expr
= build_ref_for_model (EXPR_LOCATION (lacc
->base
),
2748 lacc
->base
, lacc
->offset
,
2750 lacc
->grp_no_warning
= true;
2751 lacc
->grp_same_access_path
= false;
2757 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
2759 struct access
*new_acc
= NULL
;
2760 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
2762 if (child_would_conflict_in_acc (lacc
, norm_offset
, rchild
->size
,
2767 if (!new_acc
->grp_write
&& rchild
->grp_write
)
2769 gcc_assert (!lacc
->grp_write
);
2770 subtree_mark_written_and_rhs_enqueue (new_acc
);
2774 rchild
->grp_hint
= 1;
2775 new_acc
->grp_hint
|= new_acc
->grp_read
;
2776 if (rchild
->first_child
2777 && propagate_subaccesses_from_rhs (new_acc
, rchild
))
2780 add_access_to_rhs_work_queue (new_acc
);
2785 if (!lacc
->grp_write
)
2788 subtree_mark_written_and_rhs_enqueue (lacc
);
2794 if (rchild
->grp_unscalarizable_region
)
2796 if (rchild
->grp_write
&& !lacc
->grp_write
)
2799 subtree_mark_written_and_rhs_enqueue (lacc
);
2804 rchild
->grp_hint
= 1;
2805 /* Because get_ref_base_and_extent always includes padding in size for
2806 accesses to DECLs but not necessarily for COMPONENT_REFs of the same
2807 type, we might be actually attempting to here to create a child of the
2808 same type as the parent. */
2809 if (!types_compatible_p (lacc
->type
, rchild
->type
))
2810 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
,
2813 || rchild
->grp_write
));
2816 gcc_checking_assert (new_acc
);
2817 if (racc
->first_child
)
2818 propagate_subaccesses_from_rhs (new_acc
, rchild
);
2820 add_access_to_rhs_work_queue (lacc
);
2827 /* Propagate subaccesses of LACC across an assignment link to RACC if they
2828 should inhibit total scalarization of the corresponding area. No flags are
2829 being propagated in the process. Return true if anything changed. */
2832 propagate_subaccesses_from_lhs (struct access
*lacc
, struct access
*racc
)
2834 if (is_gimple_reg_type (racc
->type
)
2835 || lacc
->grp_unscalarizable_region
2836 || racc
->grp_unscalarizable_region
)
2839 /* TODO: Do we want set some new racc flag to stop potential total
2840 scalarization if lacc is a scalar access (and none fo the two have
2844 HOST_WIDE_INT norm_delta
= racc
->offset
- lacc
->offset
;
2845 for (struct access
*lchild
= lacc
->first_child
;
2847 lchild
= lchild
->next_sibling
)
2849 struct access
*matching_acc
= NULL
;
2850 HOST_WIDE_INT norm_offset
= lchild
->offset
+ norm_delta
;
2852 if (lchild
->grp_unscalarizable_region
2853 || child_would_conflict_in_acc (racc
, norm_offset
, lchild
->size
,
2857 && propagate_subaccesses_from_lhs (lchild
, matching_acc
))
2858 add_access_to_lhs_work_queue (matching_acc
);
2862 /* Because get_ref_base_and_extent always includes padding in size for
2863 accesses to DECLs but not necessarily for COMPONENT_REFs of the same
2864 type, we might be actually attempting to here to create a child of the
2865 same type as the parent. */
2866 if (!types_compatible_p (racc
->type
, lchild
->type
))
2868 struct access
*new_acc
2869 = create_artificial_child_access (racc
, lchild
, norm_offset
,
2871 propagate_subaccesses_from_lhs (lchild
, new_acc
);
2874 propagate_subaccesses_from_lhs (lchild
, racc
);
2880 /* Propagate all subaccesses across assignment links. */
2883 propagate_all_subaccesses (void)
2885 while (rhs_work_queue_head
)
2887 struct access
*racc
= pop_access_from_rhs_work_queue ();
2888 struct assign_link
*link
;
2890 if (racc
->group_representative
)
2891 racc
= racc
->group_representative
;
2892 gcc_assert (racc
->first_rhs_link
);
2894 for (link
= racc
->first_rhs_link
; link
; link
= link
->next_rhs
)
2896 struct access
*lacc
= link
->lacc
;
2898 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2900 lacc
= lacc
->group_representative
;
2902 bool reque_parents
= false;
2903 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
2905 if (!lacc
->grp_write
)
2907 subtree_mark_written_and_rhs_enqueue (lacc
);
2908 reque_parents
= true;
2911 else if (propagate_subaccesses_from_rhs (lacc
, racc
))
2912 reque_parents
= true;
2917 add_access_to_rhs_work_queue (lacc
);
2918 lacc
= lacc
->parent
;
2924 while (lhs_work_queue_head
)
2926 struct access
*lacc
= pop_access_from_lhs_work_queue ();
2927 struct assign_link
*link
;
2929 if (lacc
->group_representative
)
2930 lacc
= lacc
->group_representative
;
2931 gcc_assert (lacc
->first_lhs_link
);
2933 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2936 for (link
= lacc
->first_lhs_link
; link
; link
= link
->next_lhs
)
2938 struct access
*racc
= link
->racc
;
2940 if (racc
->group_representative
)
2941 racc
= racc
->group_representative
;
2942 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (racc
->base
)))
2944 if (propagate_subaccesses_from_lhs (lacc
, racc
))
2945 add_access_to_lhs_work_queue (racc
);
2950 /* Return true if the forest beginning with ROOT does not contain
2951 unscalarizable regions or non-byte aligned accesses. */
2954 can_totally_scalarize_forest_p (struct access
*root
)
2956 struct access
*access
= root
;
2959 if (access
->grp_unscalarizable_region
2960 || (access
->offset
% BITS_PER_UNIT
) != 0
2961 || (access
->size
% BITS_PER_UNIT
) != 0
2962 || (is_gimple_reg_type (access
->type
)
2963 && access
->first_child
))
2966 if (access
->first_child
)
2967 access
= access
->first_child
;
2968 else if (access
->next_sibling
)
2969 access
= access
->next_sibling
;
2972 while (access
->parent
&& !access
->next_sibling
)
2973 access
= access
->parent
;
2974 if (access
->next_sibling
)
2975 access
= access
->next_sibling
;
2978 gcc_assert (access
== root
);
2979 root
= root
->next_grp
;
2988 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
2989 reference EXPR for total scalarization purposes and mark it as such. Within
2990 the children of PARENT, link it in between PTR and NEXT_SIBLING. */
2992 static struct access
*
2993 create_total_scalarization_access (struct access
*parent
, HOST_WIDE_INT pos
,
2994 HOST_WIDE_INT size
, tree type
, tree expr
,
2995 struct access
**ptr
,
2996 struct access
*next_sibling
)
2998 struct access
*access
= access_pool
.allocate ();
2999 memset (access
, 0, sizeof (struct access
));
3000 access
->base
= parent
->base
;
3001 access
->offset
= pos
;
3002 access
->size
= size
;
3003 access
->expr
= expr
;
3004 access
->type
= type
;
3005 access
->parent
= parent
;
3006 access
->grp_write
= parent
->grp_write
;
3007 access
->grp_total_scalarization
= 1;
3008 access
->grp_hint
= 1;
3009 access
->grp_same_access_path
= path_comparable_for_same_access (expr
);
3010 access
->reverse
= reverse_storage_order_for_component_p (expr
);
3012 access
->next_sibling
= next_sibling
;
3017 /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3018 reference EXPR for total scalarization purposes and mark it as such, link it
3019 at *PTR and reshape the tree so that those elements at *PTR and their
3020 siblings which fall within the part described by POS and SIZE are moved to
3021 be children of the new access. If a partial overlap is detected, return
3024 static struct access
*
3025 create_total_access_and_reshape (struct access
*parent
, HOST_WIDE_INT pos
,
3026 HOST_WIDE_INT size
, tree type
, tree expr
,
3027 struct access
**ptr
)
3029 struct access
**p
= ptr
;
3031 while (*p
&& (*p
)->offset
< pos
+ size
)
3033 if ((*p
)->offset
+ (*p
)->size
> pos
+ size
)
3035 p
= &(*p
)->next_sibling
;
3038 struct access
*next_child
= *ptr
;
3039 struct access
*new_acc
3040 = create_total_scalarization_access (parent
, pos
, size
, type
, expr
,
3044 new_acc
->first_child
= next_child
;
3046 for (struct access
*a
= next_child
; a
; a
= a
->next_sibling
)
3047 a
->parent
= new_acc
;
3052 static bool totally_scalarize_subtree (struct access
*root
);
3054 /* Return true if INNER is either the same type as OUTER or if it is the type
3055 of a record field in OUTER at offset zero, possibly in nested
3059 access_and_field_type_match_p (tree outer
, tree inner
)
3061 if (TYPE_MAIN_VARIANT (outer
) == TYPE_MAIN_VARIANT (inner
))
3063 if (TREE_CODE (outer
) != RECORD_TYPE
)
3065 tree fld
= TYPE_FIELDS (outer
);
3068 if (TREE_CODE (fld
) == FIELD_DECL
)
3070 if (!zerop (DECL_FIELD_OFFSET (fld
)))
3072 if (TYPE_MAIN_VARIANT (TREE_TYPE (fld
)) == inner
)
3074 if (TREE_CODE (TREE_TYPE (fld
)) == RECORD_TYPE
)
3075 fld
= TYPE_FIELDS (TREE_TYPE (fld
));
3080 fld
= DECL_CHAIN (fld
);
3085 /* Return type of total_should_skip_creating_access indicating whether a total
3086 scalarization access for a field/element should be created, whether it
3087 already exists or whether the entire total scalarization has to fail. */
3089 enum total_sra_field_state
{TOTAL_FLD_CREATE
, TOTAL_FLD_DONE
, TOTAL_FLD_FAILED
};
3091 /* Do all the necessary steps in total scalarization when the given aggregate
3092 type has a TYPE at POS with the given SIZE should be put into PARENT and
3093 when we have processed all its siblings with smaller offsets up until and
3094 including LAST_SEEN_SIBLING (which can be NULL).
3096 If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3097 appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3098 creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3099 representing the described part of the aggregate for the purposes of total
3100 scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3101 prevents total scalarization from happening at all. */
3103 static enum total_sra_field_state
3104 total_should_skip_creating_access (struct access
*parent
,
3105 struct access
**last_seen_sibling
,
3106 tree type
, HOST_WIDE_INT pos
,
3109 struct access
*next_child
;
3110 if (!*last_seen_sibling
)
3111 next_child
= parent
->first_child
;
3113 next_child
= (*last_seen_sibling
)->next_sibling
;
3115 /* First, traverse the chain of siblings until it points to an access with
3116 offset at least equal to POS. Check all skipped accesses whether they
3117 span the POS boundary and if so, return with a failure. */
3118 while (next_child
&& next_child
->offset
< pos
)
3120 if (next_child
->offset
+ next_child
->size
> pos
)
3121 return TOTAL_FLD_FAILED
;
3122 *last_seen_sibling
= next_child
;
3123 next_child
= next_child
->next_sibling
;
3126 /* Now check whether next_child has exactly the right POS and SIZE and if so,
3127 whether it can represent what we need and can be totally scalarized
3129 if (next_child
&& next_child
->offset
== pos
3130 && next_child
->size
== size
)
3132 if (!is_gimple_reg_type (next_child
->type
)
3133 && (!access_and_field_type_match_p (type
, next_child
->type
)
3134 || !totally_scalarize_subtree (next_child
)))
3135 return TOTAL_FLD_FAILED
;
3137 *last_seen_sibling
= next_child
;
3138 return TOTAL_FLD_DONE
;
3141 /* If the child we're looking at would partially overlap, we just cannot
3142 totally scalarize. */
3144 && next_child
->offset
< pos
+ size
3145 && next_child
->offset
+ next_child
->size
> pos
+ size
)
3146 return TOTAL_FLD_FAILED
;
3148 if (is_gimple_reg_type (type
))
3150 /* We don't scalarize accesses that are children of other scalar type
3151 accesses, so if we go on and create an access for a register type,
3152 there should not be any pre-existing children. There are rare cases
3153 where the requested type is a vector but we already have register
3154 accesses for all its elements which is equally good. Detect that
3155 situation or whether we need to bail out. */
3157 HOST_WIDE_INT covered
= pos
;
3158 bool skipping
= false;
3160 && next_child
->offset
+ next_child
->size
<= pos
+ size
)
3162 if (next_child
->offset
!= covered
3163 || !is_gimple_reg_type (next_child
->type
))
3164 return TOTAL_FLD_FAILED
;
3166 covered
+= next_child
->size
;
3167 *last_seen_sibling
= next_child
;
3168 next_child
= next_child
->next_sibling
;
3174 if (covered
!= pos
+ size
)
3175 return TOTAL_FLD_FAILED
;
3177 return TOTAL_FLD_DONE
;
3181 return TOTAL_FLD_CREATE
;
3184 /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3185 spanning all uncovered areas covered by ROOT, return false if the attempt
3186 failed. All created accesses will have grp_unscalarizable_region set (and
3187 should be ignored if the function returns false). */
3190 totally_scalarize_subtree (struct access
*root
)
3192 gcc_checking_assert (!root
->grp_unscalarizable_region
);
3193 gcc_checking_assert (!is_gimple_reg_type (root
->type
));
3195 struct access
*last_seen_sibling
= NULL
;
3197 switch (TREE_CODE (root
->type
))
3200 for (tree fld
= TYPE_FIELDS (root
->type
); fld
; fld
= DECL_CHAIN (fld
))
3201 if (TREE_CODE (fld
) == FIELD_DECL
)
3203 tree ft
= TREE_TYPE (fld
);
3204 HOST_WIDE_INT fsize
= tree_to_uhwi (DECL_SIZE (fld
));
3208 HOST_WIDE_INT pos
= root
->offset
+ int_bit_position (fld
);
3209 enum total_sra_field_state
3210 state
= total_should_skip_creating_access (root
,
3215 case TOTAL_FLD_FAILED
:
3217 case TOTAL_FLD_DONE
:
3219 case TOTAL_FLD_CREATE
:
3225 struct access
**p
= (last_seen_sibling
3226 ? &last_seen_sibling
->next_sibling
3227 : &root
->first_child
);
3228 tree nref
= build3 (COMPONENT_REF
, ft
, root
->expr
, fld
, NULL_TREE
);
3229 struct access
*new_child
3230 = create_total_access_and_reshape (root
, pos
, fsize
, ft
, nref
, p
);
3234 if (!is_gimple_reg_type (ft
)
3235 && !totally_scalarize_subtree (new_child
))
3237 last_seen_sibling
= new_child
;
3242 tree elemtype
= TREE_TYPE (root
->type
);
3243 tree elem_size
= TYPE_SIZE (elemtype
);
3244 gcc_assert (elem_size
&& tree_fits_shwi_p (elem_size
));
3245 HOST_WIDE_INT el_size
= tree_to_shwi (elem_size
);
3246 gcc_assert (el_size
> 0);
3248 tree minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (root
->type
));
3249 gcc_assert (TREE_CODE (minidx
) == INTEGER_CST
);
3250 tree maxidx
= TYPE_MAX_VALUE (TYPE_DOMAIN (root
->type
));
3251 /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
3254 gcc_assert (TREE_CODE (maxidx
) == INTEGER_CST
);
3255 tree domain
= TYPE_DOMAIN (root
->type
);
3256 /* MINIDX and MAXIDX are inclusive, and must be interpreted in
3257 DOMAIN (e.g. signed int, whereas min/max may be size_int). */
3258 offset_int idx
= wi::to_offset (minidx
);
3259 offset_int max
= wi::to_offset (maxidx
);
3260 if (!TYPE_UNSIGNED (domain
))
3262 idx
= wi::sext (idx
, TYPE_PRECISION (domain
));
3263 max
= wi::sext (max
, TYPE_PRECISION (domain
));
3265 for (HOST_WIDE_INT pos
= root
->offset
;
3267 pos
+= el_size
, ++idx
)
3269 enum total_sra_field_state
3270 state
= total_should_skip_creating_access (root
,
3276 case TOTAL_FLD_FAILED
:
3278 case TOTAL_FLD_DONE
:
3280 case TOTAL_FLD_CREATE
:
3286 struct access
**p
= (last_seen_sibling
3287 ? &last_seen_sibling
->next_sibling
3288 : &root
->first_child
);
3289 tree nref
= build4 (ARRAY_REF
, elemtype
, root
->expr
,
3290 wide_int_to_tree (domain
, idx
),
3291 NULL_TREE
, NULL_TREE
);
3292 struct access
*new_child
3293 = create_total_access_and_reshape (root
, pos
, el_size
, elemtype
,
3298 if (!is_gimple_reg_type (elemtype
)
3299 && !totally_scalarize_subtree (new_child
))
3301 last_seen_sibling
= new_child
;
3313 /* Go through all accesses collected throughout the (intraprocedural) analysis
3314 stage, exclude overlapping ones, identify representatives and build trees
3315 out of them, making decisions about scalarization on the way. Return true
3316 iff there are any to-be-scalarized variables after this stage. */
3319 analyze_all_variable_accesses (void)
3322 bitmap tmp
= BITMAP_ALLOC (NULL
);
3326 bitmap_copy (tmp
, candidate_bitmap
);
3327 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3329 tree var
= candidate (i
);
3330 struct access
*access
;
3332 access
= sort_and_splice_var_accesses (var
);
3333 if (!access
|| !build_access_trees (access
))
3334 disqualify_candidate (var
,
3335 "No or inhibitingly overlapping accesses.");
3338 propagate_all_subaccesses ();
3340 bool optimize_speed_p
= !optimize_function_for_size_p (cfun
);
3341 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3342 fall back to a target default. */
3343 unsigned HOST_WIDE_INT max_scalarization_size
3344 = get_move_ratio (optimize_speed_p
) * UNITS_PER_WORD
;
3346 if (optimize_speed_p
)
3348 if (global_options_set
.x_param_sra_max_scalarization_size_speed
)
3349 max_scalarization_size
= param_sra_max_scalarization_size_speed
;
3353 if (global_options_set
.x_param_sra_max_scalarization_size_size
)
3354 max_scalarization_size
= param_sra_max_scalarization_size_size
;
3356 max_scalarization_size
*= BITS_PER_UNIT
;
3358 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
3359 if (bitmap_bit_p (should_scalarize_away_bitmap
, i
)
3360 && !bitmap_bit_p (cannot_scalarize_away_bitmap
, i
))
3362 tree var
= candidate (i
);
3366 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var
))) > max_scalarization_size
)
3368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 fprintf (dump_file
, "Too big to totally scalarize: ");
3371 print_generic_expr (dump_file
, var
);
3372 fprintf (dump_file
, " (UID: %u)\n", DECL_UID (var
));
3377 bool all_types_ok
= true;
3378 for (struct access
*access
= get_first_repr_for_decl (var
);
3380 access
= access
->next_grp
)
3381 if (!can_totally_scalarize_forest_p (access
)
3382 || !scalarizable_type_p (access
->type
, constant_decl_p (var
)))
3384 all_types_ok
= false;
3390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3392 fprintf (dump_file
, "Will attempt to totally scalarize ");
3393 print_generic_expr (dump_file
, var
);
3394 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3396 bool scalarized
= true;
3397 for (struct access
*access
= get_first_repr_for_decl (var
);
3399 access
= access
->next_grp
)
3400 if (!is_gimple_reg_type (access
->type
)
3401 && !totally_scalarize_subtree (access
))
3408 for (struct access
*access
= get_first_repr_for_decl (var
);
3410 access
= access
->next_grp
)
3411 access
->grp_total_scalarization
= true;
3415 verify_all_sra_access_forests ();
3417 bitmap_copy (tmp
, candidate_bitmap
);
3418 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
3420 tree var
= candidate (i
);
3421 struct access
*access
= get_first_repr_for_decl (var
);
3423 if (analyze_access_trees (access
))
3426 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3428 fprintf (dump_file
, "\nAccess trees for ");
3429 print_generic_expr (dump_file
, var
);
3430 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
3431 dump_access_tree (dump_file
, access
);
3432 fprintf (dump_file
, "\n");
3436 disqualify_candidate (var
, "No scalar replacements to be created.");
3443 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
3450 /* Generate statements copying scalar replacements of accesses within a subtree
3451 into or out of AGG. ACCESS, all its children, siblings and their children
3452 are to be processed. AGG is an aggregate type expression (can be a
3453 declaration but does not have to be, it can for example also be a mem_ref or
3454 a series of handled components). TOP_OFFSET is the offset of the processed
3455 subtree which has to be subtracted from offsets of individual accesses to
3456 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3457 replacements in the interval <start_offset, start_offset + chunk_size>,
3458 otherwise copy all. GSI is a statement iterator used to place the new
3459 statements. WRITE should be true when the statements should write from AGG
3460 to the replacement and false if vice versa. if INSERT_AFTER is true, new
3461 statements will be added after the current statement in GSI, they will be
3462 added before the statement otherwise. */
3465 generate_subtree_copies (struct access
*access
, tree agg
,
3466 HOST_WIDE_INT top_offset
,
3467 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
3468 gimple_stmt_iterator
*gsi
, bool write
,
3469 bool insert_after
, location_t loc
)
3471 /* Never write anything into constant pool decls. See PR70602. */
3472 if (!write
&& constant_decl_p (agg
))
3476 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
3479 if (access
->grp_to_be_replaced
3481 || access
->offset
+ access
->size
> start_offset
))
3483 tree expr
, repl
= get_access_replacement (access
);
3486 expr
= build_ref_for_model (loc
, agg
, access
->offset
- top_offset
,
3487 access
, gsi
, insert_after
);
3491 if (access
->grp_partial_lhs
)
3492 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
3494 insert_after
? GSI_NEW_STMT
3496 stmt
= gimple_build_assign (repl
, expr
);
3500 TREE_NO_WARNING (repl
) = 1;
3501 if (access
->grp_partial_lhs
)
3502 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
3504 insert_after
? GSI_NEW_STMT
3506 stmt
= gimple_build_assign (expr
, repl
);
3508 gimple_set_location (stmt
, loc
);
3511 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3513 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3515 sra_stats
.subtree_copies
++;
3518 && access
->grp_to_be_debug_replaced
3520 || access
->offset
+ access
->size
> start_offset
))
3523 tree drhs
= build_debug_ref_for_model (loc
, agg
,
3524 access
->offset
- top_offset
,
3526 ds
= gimple_build_debug_bind (get_access_replacement (access
),
3527 drhs
, gsi_stmt (*gsi
));
3529 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3531 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3534 if (access
->first_child
)
3535 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
3536 start_offset
, chunk_size
, gsi
,
3537 write
, insert_after
, loc
);
3539 access
= access
->next_sibling
;
3544 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
3545 root of the subtree to be processed. GSI is the statement iterator used
3546 for inserting statements which are added after the current statement if
3547 INSERT_AFTER is true or before it otherwise. */
3550 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
3551 bool insert_after
, location_t loc
)
3554 struct access
*child
;
3556 if (access
->grp_to_be_replaced
)
3560 stmt
= gimple_build_assign (get_access_replacement (access
),
3561 build_zero_cst (access
->type
));
3563 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3565 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3567 gimple_set_location (stmt
, loc
);
3569 else if (access
->grp_to_be_debug_replaced
)
3572 = gimple_build_debug_bind (get_access_replacement (access
),
3573 build_zero_cst (access
->type
),
3576 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3578 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3581 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3582 init_subtree_with_zero (child
, gsi
, insert_after
, loc
);
3585 /* Clobber all scalar replacements in an access subtree. ACCESS is the
3586 root of the subtree to be processed. GSI is the statement iterator used
3587 for inserting statements which are added after the current statement if
3588 INSERT_AFTER is true or before it otherwise. */
3591 clobber_subtree (struct access
*access
, gimple_stmt_iterator
*gsi
,
3592 bool insert_after
, location_t loc
)
3595 struct access
*child
;
3597 if (access
->grp_to_be_replaced
)
3599 tree rep
= get_access_replacement (access
);
3600 tree clobber
= build_clobber (access
->type
);
3601 gimple
*stmt
= gimple_build_assign (rep
, clobber
);
3604 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3606 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3608 gimple_set_location (stmt
, loc
);
3611 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
3612 clobber_subtree (child
, gsi
, insert_after
, loc
);
3615 /* Search for an access representative for the given expression EXPR and
3616 return it or NULL if it cannot be found. */
3618 static struct access
*
3619 get_access_for_expr (tree expr
)
3621 poly_int64 poffset
, psize
, pmax_size
;
3622 HOST_WIDE_INT offset
, max_size
;
3626 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
3627 a different size than the size of its argument and we need the latter
3629 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
3630 expr
= TREE_OPERAND (expr
, 0);
3632 base
= get_ref_base_and_extent (expr
, &poffset
, &psize
, &pmax_size
,
3634 if (!known_size_p (pmax_size
)
3635 || !pmax_size
.is_constant (&max_size
)
3636 || !poffset
.is_constant (&offset
)
3640 if (tree basesize
= DECL_SIZE (base
))
3644 || !poly_int_tree_p (basesize
, &sz
)
3645 || known_le (sz
, offset
))
3650 || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
3653 return get_var_base_offset_size_access (base
, offset
, max_size
);
3656 /* Replace the expression EXPR with a scalar replacement if there is one and
3657 generate other statements to do type conversion or subtree copying if
3658 necessary. GSI is used to place newly created statements, WRITE is true if
3659 the expression is being written to (it is on a LHS of a statement or output
3660 in an assembly statement). */
3663 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
)
3666 struct access
*access
;
3667 tree type
, bfr
, orig_expr
;
3669 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
3672 expr
= &TREE_OPERAND (*expr
, 0);
3677 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
3678 expr
= &TREE_OPERAND (*expr
, 0);
3679 access
= get_access_for_expr (*expr
);
3682 type
= TREE_TYPE (*expr
);
3685 loc
= gimple_location (gsi_stmt (*gsi
));
3686 gimple_stmt_iterator alt_gsi
= gsi_none ();
3687 if (write
&& stmt_ends_bb_p (gsi_stmt (*gsi
)))
3689 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
3693 if (access
->grp_to_be_replaced
)
3695 tree repl
= get_access_replacement (access
);
3696 /* If we replace a non-register typed access simply use the original
3697 access expression to extract the scalar component afterwards.
3698 This happens if scalarizing a function return value or parameter
3699 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
3700 gcc.c-torture/compile/20011217-1.c.
3702 We also want to use this when accessing a complex or vector which can
3703 be accessed as a different type too, potentially creating a need for
3704 type conversion (see PR42196) and when scalarized unions are involved
3705 in assembler statements (see PR42398). */
3706 if (!useless_type_conversion_p (type
, access
->type
))
3710 ref
= build_ref_for_model (loc
, orig_expr
, 0, access
, gsi
, false);
3716 if (access
->grp_partial_lhs
)
3717 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
3718 false, GSI_NEW_STMT
);
3719 stmt
= gimple_build_assign (repl
, ref
);
3720 gimple_set_location (stmt
, loc
);
3721 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
3727 if (access
->grp_partial_lhs
)
3728 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
3729 true, GSI_SAME_STMT
);
3730 stmt
= gimple_build_assign (ref
, repl
);
3731 gimple_set_location (stmt
, loc
);
3732 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
3739 else if (write
&& access
->grp_to_be_debug_replaced
)
3741 gdebug
*ds
= gimple_build_debug_bind (get_access_replacement (access
),
3744 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
3747 if (access
->first_child
)
3749 HOST_WIDE_INT start_offset
, chunk_size
;
3751 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 1))
3752 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 2)))
3754 chunk_size
= tree_to_uhwi (TREE_OPERAND (bfr
, 1));
3755 start_offset
= access
->offset
3756 + tree_to_uhwi (TREE_OPERAND (bfr
, 2));
3759 start_offset
= chunk_size
= 0;
3761 generate_subtree_copies (access
->first_child
, orig_expr
, access
->offset
,
3762 start_offset
, chunk_size
, gsi
, write
, write
,
3768 /* Where scalar replacements of the RHS have been written to when a replacement
3769 of a LHS of an assigments cannot be direclty loaded from a replacement of
3771 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
3772 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
3773 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
3775 struct subreplacement_assignment_data
3777 /* Offset of the access representing the lhs of the assignment. */
3778 HOST_WIDE_INT left_offset
;
3780 /* LHS and RHS of the original assignment. */
3781 tree assignment_lhs
, assignment_rhs
;
3783 /* Access representing the rhs of the whole assignment. */
3784 struct access
*top_racc
;
3786 /* Stmt iterator used for statement insertions after the original assignment.
3787 It points to the main GSI used to traverse a BB during function body
3789 gimple_stmt_iterator
*new_gsi
;
3791 /* Stmt iterator used for statement insertions before the original
3792 assignment. Keeps on pointing to the original statement. */
3793 gimple_stmt_iterator old_gsi
;
3795 /* Location of the assignment. */
3798 /* Keeps the information whether we have needed to refresh replacements of
3799 the LHS and from which side of the assignments this takes place. */
3800 enum unscalarized_data_handling refreshed
;
3803 /* Store all replacements in the access tree rooted in TOP_RACC either to their
3804 base aggregate if there are unscalarized data or directly to LHS of the
3805 statement that is pointed to by GSI otherwise. */
3808 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data
*sad
)
3811 if (sad
->top_racc
->grp_unscalarized_data
)
3813 src
= sad
->assignment_rhs
;
3814 sad
->refreshed
= SRA_UDH_RIGHT
;
3818 src
= sad
->assignment_lhs
;
3819 sad
->refreshed
= SRA_UDH_LEFT
;
3821 generate_subtree_copies (sad
->top_racc
->first_child
, src
,
3822 sad
->top_racc
->offset
, 0, 0,
3823 &sad
->old_gsi
, false, false, sad
->loc
);
3826 /* Try to generate statements to load all sub-replacements in an access subtree
3827 formed by children of LACC from scalar replacements in the SAD->top_racc
3828 subtree. If that is not possible, refresh the SAD->top_racc base aggregate
3829 and load the accesses from it. */
3832 load_assign_lhs_subreplacements (struct access
*lacc
,
3833 struct subreplacement_assignment_data
*sad
)
3835 for (lacc
= lacc
->first_child
; lacc
; lacc
= lacc
->next_sibling
)
3837 HOST_WIDE_INT offset
;
3838 offset
= lacc
->offset
- sad
->left_offset
+ sad
->top_racc
->offset
;
3840 if (lacc
->grp_to_be_replaced
)
3842 struct access
*racc
;
3846 racc
= find_access_in_subtree (sad
->top_racc
, offset
, lacc
->size
);
3847 if (racc
&& racc
->grp_to_be_replaced
)
3849 rhs
= get_access_replacement (racc
);
3850 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
3851 rhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3854 if (racc
->grp_partial_lhs
&& lacc
->grp_partial_lhs
)
3855 rhs
= force_gimple_operand_gsi (&sad
->old_gsi
, rhs
, true,
3856 NULL_TREE
, true, GSI_SAME_STMT
);
3860 /* No suitable access on the right hand side, need to load from
3861 the aggregate. See if we have to update it first... */
3862 if (sad
->refreshed
== SRA_UDH_NONE
)
3863 handle_unscalarized_data_in_subtree (sad
);
3865 if (sad
->refreshed
== SRA_UDH_LEFT
)
3866 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_lhs
,
3867 lacc
->offset
- sad
->left_offset
,
3868 lacc
, sad
->new_gsi
, true);
3870 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_rhs
,
3871 lacc
->offset
- sad
->left_offset
,
3872 lacc
, sad
->new_gsi
, true);
3873 if (lacc
->grp_partial_lhs
)
3874 rhs
= force_gimple_operand_gsi (sad
->new_gsi
,
3875 rhs
, true, NULL_TREE
,
3876 false, GSI_NEW_STMT
);
3879 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
3880 gsi_insert_after (sad
->new_gsi
, stmt
, GSI_NEW_STMT
);
3881 gimple_set_location (stmt
, sad
->loc
);
3883 sra_stats
.subreplacements
++;
3887 if (sad
->refreshed
== SRA_UDH_NONE
3888 && lacc
->grp_read
&& !lacc
->grp_covered
)
3889 handle_unscalarized_data_in_subtree (sad
);
3891 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
3895 struct access
*racc
= find_access_in_subtree (sad
->top_racc
,
3899 if (racc
&& racc
->grp_to_be_replaced
)
3901 if (racc
->grp_write
|| constant_decl_p (racc
->base
))
3902 drhs
= get_access_replacement (racc
);
3906 else if (sad
->refreshed
== SRA_UDH_LEFT
)
3907 drhs
= build_debug_ref_for_model (sad
->loc
, lacc
->base
,
3908 lacc
->offset
, lacc
);
3909 else if (sad
->refreshed
== SRA_UDH_RIGHT
)
3910 drhs
= build_debug_ref_for_model (sad
->loc
, sad
->top_racc
->base
,
3915 && !useless_type_conversion_p (lacc
->type
, TREE_TYPE (drhs
)))
3916 drhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3918 ds
= gimple_build_debug_bind (get_access_replacement (lacc
),
3919 drhs
, gsi_stmt (sad
->old_gsi
));
3920 gsi_insert_after (sad
->new_gsi
, ds
, GSI_NEW_STMT
);
3924 if (lacc
->first_child
)
3925 load_assign_lhs_subreplacements (lacc
, sad
);
3929 /* Result code for SRA assignment modification. */
3930 enum assignment_mod_result
{ SRA_AM_NONE
, /* nothing done for the stmt */
3931 SRA_AM_MODIFIED
, /* stmt changed but not
3933 SRA_AM_REMOVED
}; /* stmt eliminated */
3935 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
3936 to the assignment and GSI is the statement iterator pointing at it. Returns
3937 the same values as sra_modify_assign. */
3939 static enum assignment_mod_result
3940 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
3942 tree lhs
= gimple_assign_lhs (stmt
);
3943 struct access
*acc
= get_access_for_expr (lhs
);
3946 location_t loc
= gimple_location (stmt
);
3948 if (gimple_clobber_p (stmt
))
3950 /* Clobber the replacement variable. */
3951 clobber_subtree (acc
, gsi
, !acc
->grp_covered
, loc
);
3952 /* Remove clobbers of fully scalarized variables, they are dead. */
3953 if (acc
->grp_covered
)
3955 unlink_stmt_vdef (stmt
);
3956 gsi_remove (gsi
, true);
3957 release_defs (stmt
);
3958 return SRA_AM_REMOVED
;
3961 return SRA_AM_MODIFIED
;
3964 if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
)) > 0)
3966 /* I have never seen this code path trigger but if it can happen the
3967 following should handle it gracefully. */
3968 if (access_has_children_p (acc
))
3969 generate_subtree_copies (acc
->first_child
, lhs
, acc
->offset
, 0, 0, gsi
,
3971 return SRA_AM_MODIFIED
;
3974 if (acc
->grp_covered
)
3976 init_subtree_with_zero (acc
, gsi
, false, loc
);
3977 unlink_stmt_vdef (stmt
);
3978 gsi_remove (gsi
, true);
3979 release_defs (stmt
);
3980 return SRA_AM_REMOVED
;
3984 init_subtree_with_zero (acc
, gsi
, true, loc
);
3985 return SRA_AM_MODIFIED
;
3989 /* Create and return a new suitable default definition SSA_NAME for RACC which
3990 is an access describing an uninitialized part of an aggregate that is being
3991 loaded. REG_TREE is used instead of the actual RACC type if that is not of
3992 a gimple register type. */
3995 get_repl_default_def_ssa_name (struct access
*racc
, tree reg_type
)
3997 gcc_checking_assert (!racc
->grp_to_be_replaced
3998 && !racc
->grp_to_be_debug_replaced
);
3999 if (!racc
->replacement_decl
)
4000 racc
->replacement_decl
= create_access_replacement (racc
, reg_type
);
4001 return get_or_create_ssa_default_def (cfun
, racc
->replacement_decl
);
4004 /* Examine both sides of the assignment statement pointed to by STMT, replace
4005 them with a scalare replacement if there is one and generate copying of
4006 replacements if scalarized aggregates have been used in the assignment. GSI
4007 is used to hold generated statements for type conversions and subtree
4010 static enum assignment_mod_result
4011 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
4013 struct access
*lacc
, *racc
;
4015 bool modify_this_stmt
= false;
4016 bool force_gimple_rhs
= false;
4018 gimple_stmt_iterator orig_gsi
= *gsi
;
4020 if (!gimple_assign_single_p (stmt
))
4022 lhs
= gimple_assign_lhs (stmt
);
4023 rhs
= gimple_assign_rhs1 (stmt
);
4025 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
4026 return sra_modify_constructor_assign (stmt
, gsi
);
4028 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
4029 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
4030 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
4032 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (stmt
),
4034 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (stmt
),
4036 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4039 lacc
= get_access_for_expr (lhs
);
4040 racc
= get_access_for_expr (rhs
);
4043 /* Avoid modifying initializations of constant-pool replacements. */
4044 if (racc
&& (racc
->replacement_decl
== lhs
))
4047 loc
= gimple_location (stmt
);
4048 if (lacc
&& lacc
->grp_to_be_replaced
)
4050 lhs
= get_access_replacement (lacc
);
4051 gimple_assign_set_lhs (stmt
, lhs
);
4052 modify_this_stmt
= true;
4053 if (lacc
->grp_partial_lhs
)
4054 force_gimple_rhs
= true;
4058 if (racc
&& racc
->grp_to_be_replaced
)
4060 rhs
= get_access_replacement (racc
);
4061 modify_this_stmt
= true;
4062 if (racc
->grp_partial_lhs
)
4063 force_gimple_rhs
= true;
4067 && !racc
->grp_unscalarized_data
4068 && !racc
->grp_unscalarizable_region
4069 && TREE_CODE (lhs
) == SSA_NAME
4070 && !access_has_replacements_p (racc
))
4072 rhs
= get_repl_default_def_ssa_name (racc
, TREE_TYPE (lhs
));
4073 modify_this_stmt
= true;
4077 if (modify_this_stmt
)
4079 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4081 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
4082 ??? This should move to fold_stmt which we simply should
4083 call after building a VIEW_CONVERT_EXPR here. */
4084 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
4085 && !contains_bitfld_component_ref_p (lhs
))
4087 lhs
= build_ref_for_model (loc
, lhs
, 0, racc
, gsi
, false);
4088 gimple_assign_set_lhs (stmt
, lhs
);
4091 && AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
4092 && !contains_vce_or_bfcref_p (rhs
))
4093 rhs
= build_ref_for_model (loc
, rhs
, 0, lacc
, gsi
, false);
4095 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
4097 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
),
4099 if (is_gimple_reg_type (TREE_TYPE (lhs
))
4100 && TREE_CODE (lhs
) != SSA_NAME
)
4101 force_gimple_rhs
= true;
4106 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
4108 tree dlhs
= get_access_replacement (lacc
);
4109 tree drhs
= unshare_expr (rhs
);
4110 if (!useless_type_conversion_p (TREE_TYPE (dlhs
), TREE_TYPE (drhs
)))
4112 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs
))
4113 && !contains_vce_or_bfcref_p (drhs
))
4114 drhs
= build_debug_ref_for_model (loc
, drhs
, 0, lacc
);
4116 && !useless_type_conversion_p (TREE_TYPE (dlhs
),
4118 drhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
4119 TREE_TYPE (dlhs
), drhs
);
4121 gdebug
*ds
= gimple_build_debug_bind (dlhs
, drhs
, stmt
);
4122 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
4125 /* From this point on, the function deals with assignments in between
4126 aggregates when at least one has scalar reductions of some of its
4127 components. There are three possible scenarios: Both the LHS and RHS have
4128 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4130 In the first case, we would like to load the LHS components from RHS
4131 components whenever possible. If that is not possible, we would like to
4132 read it directly from the RHS (after updating it by storing in it its own
4133 components). If there are some necessary unscalarized data in the LHS,
4134 those will be loaded by the original assignment too. If neither of these
4135 cases happen, the original statement can be removed. Most of this is done
4136 by load_assign_lhs_subreplacements.
4138 In the second case, we would like to store all RHS scalarized components
4139 directly into LHS and if they cover the aggregate completely, remove the
4140 statement too. In the third case, we want the LHS components to be loaded
4141 directly from the RHS (DSE will remove the original statement if it
4144 This is a bit complex but manageable when types match and when unions do
4145 not cause confusion in a way that we cannot really load a component of LHS
4146 from the RHS or vice versa (the access representing this level can have
4147 subaccesses that are accessible only through a different union field at a
4148 higher level - different from the one used in the examined expression).
4151 Therefore, I specially handle a fourth case, happening when there is a
4152 specific type cast or it is impossible to locate a scalarized subaccess on
4153 the other side of the expression. If that happens, I simply "refresh" the
4154 RHS by storing in it is scalarized components leave the original statement
4155 there to do the copying and then load the scalar replacements of the LHS.
4156 This is what the first branch does. */
4158 if (modify_this_stmt
4159 || gimple_has_volatile_ops (stmt
)
4160 || contains_vce_or_bfcref_p (rhs
)
4161 || contains_vce_or_bfcref_p (lhs
)
4162 || stmt_ends_bb_p (stmt
))
4164 /* No need to copy into a constant-pool, it comes pre-initialized. */
4165 if (access_has_children_p (racc
) && !constant_decl_p (racc
->base
))
4166 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4167 gsi
, false, false, loc
);
4168 if (access_has_children_p (lacc
))
4170 gimple_stmt_iterator alt_gsi
= gsi_none ();
4171 if (stmt_ends_bb_p (stmt
))
4173 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
4176 generate_subtree_copies (lacc
->first_child
, lhs
, lacc
->offset
, 0, 0,
4177 gsi
, true, true, loc
);
4179 sra_stats
.separate_lhs_rhs_handling
++;
4181 /* This gimplification must be done after generate_subtree_copies,
4182 lest we insert the subtree copies in the middle of the gimplified
4184 if (force_gimple_rhs
)
4185 rhs
= force_gimple_operand_gsi (&orig_gsi
, rhs
, true, NULL_TREE
,
4186 true, GSI_SAME_STMT
);
4187 if (gimple_assign_rhs1 (stmt
) != rhs
)
4189 modify_this_stmt
= true;
4190 gimple_assign_set_rhs_from_tree (&orig_gsi
, rhs
);
4191 gcc_assert (stmt
== gsi_stmt (orig_gsi
));
4194 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
4198 if (access_has_children_p (lacc
)
4199 && access_has_children_p (racc
)
4200 /* When an access represents an unscalarizable region, it usually
4201 represents accesses with variable offset and thus must not be used
4202 to generate new memory accesses. */
4203 && !lacc
->grp_unscalarizable_region
4204 && !racc
->grp_unscalarizable_region
)
4206 struct subreplacement_assignment_data sad
;
4208 sad
.left_offset
= lacc
->offset
;
4209 sad
.assignment_lhs
= lhs
;
4210 sad
.assignment_rhs
= rhs
;
4211 sad
.top_racc
= racc
;
4214 sad
.loc
= gimple_location (stmt
);
4215 sad
.refreshed
= SRA_UDH_NONE
;
4217 if (lacc
->grp_read
&& !lacc
->grp_covered
)
4218 handle_unscalarized_data_in_subtree (&sad
);
4220 load_assign_lhs_subreplacements (lacc
, &sad
);
4221 if (sad
.refreshed
!= SRA_UDH_RIGHT
)
4224 unlink_stmt_vdef (stmt
);
4225 gsi_remove (&sad
.old_gsi
, true);
4226 release_defs (stmt
);
4227 sra_stats
.deleted
++;
4228 return SRA_AM_REMOVED
;
4233 if (access_has_children_p (racc
)
4234 && !racc
->grp_unscalarized_data
4235 && TREE_CODE (lhs
) != SSA_NAME
)
4239 fprintf (dump_file
, "Removing load: ");
4240 print_gimple_stmt (dump_file
, stmt
, 0);
4242 generate_subtree_copies (racc
->first_child
, lhs
,
4243 racc
->offset
, 0, 0, gsi
,
4245 gcc_assert (stmt
== gsi_stmt (*gsi
));
4246 unlink_stmt_vdef (stmt
);
4247 gsi_remove (gsi
, true);
4248 release_defs (stmt
);
4249 sra_stats
.deleted
++;
4250 return SRA_AM_REMOVED
;
4252 /* Restore the aggregate RHS from its components so the
4253 prevailing aggregate copy does the right thing. */
4254 if (access_has_children_p (racc
))
4255 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
4256 gsi
, false, false, loc
);
4257 /* Re-load the components of the aggregate copy destination.
4258 But use the RHS aggregate to load from to expose more
4259 optimization opportunities. */
4260 if (access_has_children_p (lacc
))
4261 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
4262 0, 0, gsi
, true, true, loc
);
4269 /* Set any scalar replacements of values in the constant pool to the initial
4270 value of the constant. (Constant-pool decls like *.LC0 have effectively
4271 been initialized before the program starts, we must do the same for their
4272 replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4273 the function's entry block. */
4276 initialize_constant_pool_replacements (void)
4278 gimple_seq seq
= NULL
;
4279 gimple_stmt_iterator gsi
= gsi_start (seq
);
4283 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
4285 tree var
= candidate (i
);
4286 if (!constant_decl_p (var
))
4289 struct access
*access
= get_first_repr_for_decl (var
);
4293 if (access
->replacement_decl
)
4296 = gimple_build_assign (get_access_replacement (access
),
4297 unshare_expr (access
->expr
));
4298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4300 fprintf (dump_file
, "Generating constant initializer: ");
4301 print_gimple_stmt (dump_file
, stmt
, 0);
4302 fprintf (dump_file
, "\n");
4304 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
4308 if (access
->first_child
)
4309 access
= access
->first_child
;
4310 else if (access
->next_sibling
)
4311 access
= access
->next_sibling
;
4314 while (access
->parent
&& !access
->next_sibling
)
4315 access
= access
->parent
;
4316 if (access
->next_sibling
)
4317 access
= access
->next_sibling
;
4319 access
= access
->next_grp
;
4324 seq
= gsi_seq (gsi
);
4326 gsi_insert_seq_on_edge_immediate (
4327 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4330 /* Traverse the function body and all modifications as decided in
4331 analyze_all_variable_accesses. Return true iff the CFG has been
4335 sra_modify_function_body (void)
4337 bool cfg_changed
= false;
4340 initialize_constant_pool_replacements ();
4342 FOR_EACH_BB_FN (bb
, cfun
)
4344 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
4345 while (!gsi_end_p (gsi
))
4347 gimple
*stmt
= gsi_stmt (gsi
);
4348 enum assignment_mod_result assign_result
;
4349 bool modified
= false, deleted
= false;
4353 switch (gimple_code (stmt
))
4356 t
= gimple_return_retval_ptr (as_a
<greturn
*> (stmt
));
4357 if (*t
!= NULL_TREE
)
4358 modified
|= sra_modify_expr (t
, &gsi
, false);
4362 assign_result
= sra_modify_assign (stmt
, &gsi
);
4363 modified
|= assign_result
== SRA_AM_MODIFIED
;
4364 deleted
= assign_result
== SRA_AM_REMOVED
;
4368 /* Operands must be processed before the lhs. */
4369 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
4371 t
= gimple_call_arg_ptr (stmt
, i
);
4372 modified
|= sra_modify_expr (t
, &gsi
, false);
4375 if (gimple_call_lhs (stmt
))
4377 t
= gimple_call_lhs_ptr (stmt
);
4378 modified
|= sra_modify_expr (t
, &gsi
, true);
4384 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
4385 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
4387 t
= &TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
4388 modified
|= sra_modify_expr (t
, &gsi
, false);
4390 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
4392 t
= &TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
4393 modified
|= sra_modify_expr (t
, &gsi
, true);
4405 if (maybe_clean_eh_stmt (stmt
)
4406 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
4414 gsi_commit_edge_inserts ();
4418 /* Generate statements initializing scalar replacements of parts of function
4422 initialize_parameter_reductions (void)
4424 gimple_stmt_iterator gsi
;
4425 gimple_seq seq
= NULL
;
4428 gsi
= gsi_start (seq
);
4429 for (parm
= DECL_ARGUMENTS (current_function_decl
);
4431 parm
= DECL_CHAIN (parm
))
4433 vec
<access_p
> *access_vec
;
4434 struct access
*access
;
4436 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
4438 access_vec
= get_base_access_vector (parm
);
4442 for (access
= (*access_vec
)[0];
4444 access
= access
->next_grp
)
4445 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true,
4446 EXPR_LOCATION (parm
));
4449 seq
= gsi_seq (gsi
);
4451 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
4454 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
4455 it reveals there are components of some aggregates to be scalarized, it runs
4456 the required transformations. */
4458 perform_intra_sra (void)
4463 if (!find_var_candidates ())
4466 if (!scan_function ())
4469 if (!analyze_all_variable_accesses ())
4472 if (sra_modify_function_body ())
4473 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
4475 ret
= TODO_update_ssa
;
4476 initialize_parameter_reductions ();
4478 statistics_counter_event (cfun
, "Scalar replacements created",
4479 sra_stats
.replacements
);
4480 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
4481 statistics_counter_event (cfun
, "Subtree copy stmts",
4482 sra_stats
.subtree_copies
);
4483 statistics_counter_event (cfun
, "Subreplacement stmts",
4484 sra_stats
.subreplacements
);
4485 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
4486 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
4487 sra_stats
.separate_lhs_rhs_handling
);
4490 sra_deinitialize ();
4494 /* Perform early intraprocedural SRA. */
4496 early_intra_sra (void)
4498 sra_mode
= SRA_MODE_EARLY_INTRA
;
4499 return perform_intra_sra ();
4502 /* Perform "late" intraprocedural SRA. */
4504 late_intra_sra (void)
4506 sra_mode
= SRA_MODE_INTRA
;
4507 return perform_intra_sra ();
4512 gate_intra_sra (void)
4514 return flag_tree_sra
!= 0 && dbg_cnt (tree_sra
);
4520 const pass_data pass_data_sra_early
=
4522 GIMPLE_PASS
, /* type */
4524 OPTGROUP_NONE
, /* optinfo_flags */
4525 TV_TREE_SRA
, /* tv_id */
4526 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4527 0, /* properties_provided */
4528 0, /* properties_destroyed */
4529 0, /* todo_flags_start */
4530 TODO_update_ssa
, /* todo_flags_finish */
4533 class pass_sra_early
: public gimple_opt_pass
4536 pass_sra_early (gcc::context
*ctxt
)
4537 : gimple_opt_pass (pass_data_sra_early
, ctxt
)
4540 /* opt_pass methods: */
4541 virtual bool gate (function
*) { return gate_intra_sra (); }
4542 virtual unsigned int execute (function
*) { return early_intra_sra (); }
4544 }; // class pass_sra_early
4549 make_pass_sra_early (gcc::context
*ctxt
)
4551 return new pass_sra_early (ctxt
);
4556 const pass_data pass_data_sra
=
4558 GIMPLE_PASS
, /* type */
4560 OPTGROUP_NONE
, /* optinfo_flags */
4561 TV_TREE_SRA
, /* tv_id */
4562 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4563 0, /* properties_provided */
4564 0, /* properties_destroyed */
4565 TODO_update_address_taken
, /* todo_flags_start */
4566 TODO_update_ssa
, /* todo_flags_finish */
4569 class pass_sra
: public gimple_opt_pass
4572 pass_sra (gcc::context
*ctxt
)
4573 : gimple_opt_pass (pass_data_sra
, ctxt
)
4576 /* opt_pass methods: */
4577 virtual bool gate (function
*) { return gate_intra_sra (); }
4578 virtual unsigned int execute (function
*) { return late_intra_sra (); }
4580 }; // class pass_sra
4585 make_pass_sra (gcc::context
*ctxt
)
4587 return new pass_sra (ctxt
);