1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008-2015 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"
99 #include "symbol-summary.h"
100 #include "ipa-prop.h"
103 #include "tree-inline.h"
104 #include "ipa-inline.h"
105 #include "ipa-utils.h"
106 #include "builtins.h"
108 /* Enumeration of all aggregate reductions we can do. */
109 enum sra_mode
{ SRA_MODE_EARLY_IPA
, /* early call regularization */
110 SRA_MODE_EARLY_INTRA
, /* early intraprocedural SRA */
111 SRA_MODE_INTRA
}; /* late intraprocedural SRA */
113 /* Global variable describing which aggregate reduction we are performing at
115 static enum sra_mode sra_mode
;
119 /* ACCESS represents each access to an aggregate variable (as a whole or a
120 part). It can also represent a group of accesses that refer to exactly the
121 same fragment of an aggregate (i.e. those that have exactly the same offset
122 and size). Such representatives for a single aggregate, once determined,
123 are linked in a linked list and have the group fields set.
125 Moreover, when doing intraprocedural SRA, a tree is built from those
126 representatives (by the means of first_child and next_sibling pointers), in
127 which all items in a subtree are "within" the root, i.e. their offset is
128 greater or equal to offset of the root and offset+size is smaller or equal
129 to offset+size of the root. Children of an access are sorted by offset.
131 Note that accesses to parts of vector and complex number types always
132 represented by an access to the whole complex number or a vector. It is a
133 duty of the modifying functions to replace them appropriately. */
137 /* Values returned by `get_ref_base_and_extent' for each component reference
138 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
139 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
140 HOST_WIDE_INT offset
;
144 /* Expression. It is context dependent so do not use it to create new
145 expressions to access the original aggregate. See PR 42154 for a
151 /* The statement this access belongs to. */
154 /* Next group representative for this aggregate. */
155 struct access
*next_grp
;
157 /* Pointer to the group representative. Pointer to itself if the struct is
158 the representative. */
159 struct access
*group_representative
;
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
166 described above. In IPA-SRA this is a pointer to the next access
167 belonging to the same group (having the same representative). */
168 struct access
*next_sibling
;
170 /* Pointers to the first and last element in the linked list of assign
172 struct assign_link
*first_link
, *last_link
;
174 /* Pointer to the next access in the work queue. */
175 struct access
*next_queued
;
177 /* Replacement variable for this access "region." Never to be accessed
178 directly, always only by the means of get_access_replacement() and only
179 when grp_to_be_replaced flag is set. */
180 tree replacement_decl
;
182 /* Is this access an access to a non-addressable field? */
183 unsigned non_addressable
: 1;
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 work queue? */
192 unsigned grp_queued
: 1;
194 /* Does this group contain a write access? This flag is propagated down the
196 unsigned grp_write
: 1;
198 /* Does this group contain a read access? This flag is propagated down the
200 unsigned grp_read
: 1;
202 /* Does this group contain a read access that comes from an assignment
203 statement? This flag is propagated down the access tree. */
204 unsigned grp_assignment_read
: 1;
206 /* Does this group contain a write access that comes from an assignment
207 statement? This flag is propagated down the access tree. */
208 unsigned grp_assignment_write
: 1;
210 /* Does this group contain a read access through a scalar type? This flag is
211 not propagated in the access tree in any direction. */
212 unsigned grp_scalar_read
: 1;
214 /* Does this group contain a write access through a scalar type? This flag
215 is not propagated in the access tree in any direction. */
216 unsigned grp_scalar_write
: 1;
218 /* Is this access an artificial one created to scalarize some record
220 unsigned grp_total_scalarization
: 1;
222 /* Other passes of the analysis use this bit to make function
223 analyze_access_subtree create scalar replacements for this group if
225 unsigned grp_hint
: 1;
227 /* Is the subtree rooted in this access fully covered by scalar
229 unsigned grp_covered
: 1;
231 /* If set to true, this access and all below it in an access tree must not be
233 unsigned grp_unscalarizable_region
: 1;
235 /* Whether data have been written to parts of the aggregate covered by this
236 access which is not to be scalarized. This flag is propagated up in the
238 unsigned grp_unscalarized_data
: 1;
240 /* Does this access and/or group contain a write access through a
242 unsigned grp_partial_lhs
: 1;
244 /* Set when a scalar replacement should be created for this variable. */
245 unsigned grp_to_be_replaced
: 1;
247 /* Set when we want a replacement for the sole purpose of having it in
248 generated debug statements. */
249 unsigned grp_to_be_debug_replaced
: 1;
251 /* Should TREE_NO_WARNING of a replacement be set? */
252 unsigned grp_no_warning
: 1;
254 /* Is it possible that the group refers to data which might be (directly or
255 otherwise) modified? */
256 unsigned grp_maybe_modified
: 1;
258 /* Set when this is a representative of a pointer to scalar (i.e. by
259 reference) parameter which we consider for turning into a plain scalar
260 (i.e. a by value parameter). */
261 unsigned grp_scalar_ptr
: 1;
263 /* Set when we discover that this pointer is not safe to dereference in the
265 unsigned grp_not_necessarilly_dereferenced
: 1;
268 typedef struct access
*access_p
;
271 /* Alloc pool for allocating access structures. */
272 static object_allocator
<struct access
> access_pool ("SRA accesses");
274 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
275 are used to propagate subaccesses from rhs to lhs as long as they don't
276 conflict with what is already there. */
279 struct access
*lacc
, *racc
;
280 struct assign_link
*next
;
283 /* Alloc pool for allocating assign link structures. */
284 static object_allocator
<assign_link
> assign_link_pool ("SRA links");
286 /* Base (tree) -> Vector (vec<access_p> *) map. */
287 static hash_map
<tree
, auto_vec
<access_p
> > *base_access_vec
;
289 /* Candidate hash table helpers. */
291 struct uid_decl_hasher
: nofree_ptr_hash
<tree_node
>
293 static inline hashval_t
hash (const tree_node
*);
294 static inline bool equal (const tree_node
*, const tree_node
*);
297 /* Hash a tree in a uid_decl_map. */
300 uid_decl_hasher::hash (const tree_node
*item
)
302 return item
->decl_minimal
.uid
;
305 /* Return true if the DECL_UID in both trees are equal. */
308 uid_decl_hasher::equal (const tree_node
*a
, const tree_node
*b
)
310 return (a
->decl_minimal
.uid
== b
->decl_minimal
.uid
);
313 /* Set of candidates. */
314 static bitmap candidate_bitmap
;
315 static hash_table
<uid_decl_hasher
> *candidates
;
317 /* For a candidate UID return the candidates decl. */
320 candidate (unsigned uid
)
323 t
.decl_minimal
.uid
= uid
;
324 return candidates
->find_with_hash (&t
, static_cast <hashval_t
> (uid
));
327 /* Bitmap of candidates which we should try to entirely scalarize away and
328 those which cannot be (because they are and need be used as a whole). */
329 static bitmap should_scalarize_away_bitmap
, cannot_scalarize_away_bitmap
;
331 /* Obstack for creation of fancy names. */
332 static struct obstack name_obstack
;
334 /* Head of a linked list of accesses that need to have its subaccesses
335 propagated to their assignment counterparts. */
336 static struct access
*work_queue_head
;
338 /* Number of parameters of the analyzed function when doing early ipa SRA. */
339 static int func_param_count
;
341 /* scan_function sets the following to true if it encounters a call to
342 __builtin_apply_args. */
343 static bool encountered_apply_args
;
345 /* Set by scan_function when it finds a recursive call. */
346 static bool encountered_recursive_call
;
348 /* Set by scan_function when it finds a recursive call with less actual
349 arguments than formal parameters.. */
350 static bool encountered_unchangable_recursive_call
;
352 /* This is a table in which for each basic block and parameter there is a
353 distance (offset + size) in that parameter which is dereferenced and
354 accessed in that BB. */
355 static HOST_WIDE_INT
*bb_dereferences
;
356 /* Bitmap of BBs that can cause the function to "stop" progressing by
357 returning, throwing externally, looping infinitely or calling a function
358 which might abort etc.. */
359 static bitmap final_bbs
;
361 /* Representative of no accesses at all. */
362 static struct access no_accesses_representant
;
364 /* Predicate to test the special value. */
367 no_accesses_p (struct access
*access
)
369 return access
== &no_accesses_representant
;
372 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
373 representative fields are dumped, otherwise those which only describe the
374 individual access are. */
378 /* Number of processed aggregates is readily available in
379 analyze_all_variable_accesses and so is not stored here. */
381 /* Number of created scalar replacements. */
384 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
388 /* Number of statements created by generate_subtree_copies. */
391 /* Number of statements created by load_assign_lhs_subreplacements. */
394 /* Number of times sra_modify_assign has deleted a statement. */
397 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
398 RHS reparately due to type conversions or nonexistent matching
400 int separate_lhs_rhs_handling
;
402 /* Number of parameters that were removed because they were unused. */
403 int deleted_unused_parameters
;
405 /* Number of scalars passed as parameters by reference that have been
406 converted to be passed by value. */
407 int scalar_by_ref_to_by_val
;
409 /* Number of aggregate parameters that were replaced by one or more of their
411 int aggregate_params_reduced
;
413 /* Numbber of components created when splitting aggregate parameters. */
414 int param_reductions_created
;
418 dump_access (FILE *f
, struct access
*access
, bool grp
)
420 fprintf (f
, "access { ");
421 fprintf (f
, "base = (%d)'", DECL_UID (access
->base
));
422 print_generic_expr (f
, access
->base
, 0);
423 fprintf (f
, "', offset = " HOST_WIDE_INT_PRINT_DEC
, access
->offset
);
424 fprintf (f
, ", size = " HOST_WIDE_INT_PRINT_DEC
, access
->size
);
425 fprintf (f
, ", expr = ");
426 print_generic_expr (f
, access
->expr
, 0);
427 fprintf (f
, ", type = ");
428 print_generic_expr (f
, access
->type
, 0);
429 fprintf (f
, ", non_addressable = %d, reverse = %d",
430 access
->non_addressable
, access
->reverse
);
432 fprintf (f
, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
433 "grp_assignment_write = %d, grp_scalar_read = %d, "
434 "grp_scalar_write = %d, grp_total_scalarization = %d, "
435 "grp_hint = %d, grp_covered = %d, "
436 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
437 "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
438 "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
439 "grp_not_necessarilly_dereferenced = %d\n",
440 access
->grp_read
, access
->grp_write
, access
->grp_assignment_read
,
441 access
->grp_assignment_write
, access
->grp_scalar_read
,
442 access
->grp_scalar_write
, access
->grp_total_scalarization
,
443 access
->grp_hint
, access
->grp_covered
,
444 access
->grp_unscalarizable_region
, access
->grp_unscalarized_data
,
445 access
->grp_partial_lhs
, access
->grp_to_be_replaced
,
446 access
->grp_to_be_debug_replaced
, access
->grp_maybe_modified
,
447 access
->grp_not_necessarilly_dereferenced
);
449 fprintf (f
, ", write = %d, grp_total_scalarization = %d, "
450 "grp_partial_lhs = %d\n",
451 access
->write
, access
->grp_total_scalarization
,
452 access
->grp_partial_lhs
);
455 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
458 dump_access_tree_1 (FILE *f
, struct access
*access
, int level
)
464 for (i
= 0; i
< level
; i
++)
465 fputs ("* ", dump_file
);
467 dump_access (f
, access
, true);
469 if (access
->first_child
)
470 dump_access_tree_1 (f
, access
->first_child
, level
+ 1);
472 access
= access
->next_sibling
;
477 /* Dump all access trees for a variable, given the pointer to the first root in
481 dump_access_tree (FILE *f
, struct access
*access
)
483 for (; access
; access
= access
->next_grp
)
484 dump_access_tree_1 (f
, access
, 0);
487 /* Return true iff ACC is non-NULL and has subaccesses. */
490 access_has_children_p (struct access
*acc
)
492 return acc
&& acc
->first_child
;
495 /* Return true iff ACC is (partly) covered by at least one replacement. */
498 access_has_replacements_p (struct access
*acc
)
500 struct access
*child
;
501 if (acc
->grp_to_be_replaced
)
503 for (child
= acc
->first_child
; child
; child
= child
->next_sibling
)
504 if (access_has_replacements_p (child
))
509 /* Return a vector of pointers to accesses for the variable given in BASE or
510 NULL if there is none. */
512 static vec
<access_p
> *
513 get_base_access_vector (tree base
)
515 return base_access_vec
->get (base
);
518 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
519 in ACCESS. Return NULL if it cannot be found. */
521 static struct access
*
522 find_access_in_subtree (struct access
*access
, HOST_WIDE_INT offset
,
525 while (access
&& (access
->offset
!= offset
|| access
->size
!= size
))
527 struct access
*child
= access
->first_child
;
529 while (child
&& (child
->offset
+ child
->size
<= offset
))
530 child
= child
->next_sibling
;
537 /* Return the first group representative for DECL or NULL if none exists. */
539 static struct access
*
540 get_first_repr_for_decl (tree base
)
542 vec
<access_p
> *access_vec
;
544 access_vec
= get_base_access_vector (base
);
548 return (*access_vec
)[0];
551 /* Find an access representative for the variable BASE and given OFFSET and
552 SIZE. Requires that access trees have already been built. Return NULL if
553 it cannot be found. */
555 static struct access
*
556 get_var_base_offset_size_access (tree base
, HOST_WIDE_INT offset
,
559 struct access
*access
;
561 access
= get_first_repr_for_decl (base
);
562 while (access
&& (access
->offset
+ access
->size
<= offset
))
563 access
= access
->next_grp
;
567 return find_access_in_subtree (access
, offset
, size
);
570 /* Add LINK to the linked list of assign links of RACC. */
572 add_link_to_rhs (struct access
*racc
, struct assign_link
*link
)
574 gcc_assert (link
->racc
== racc
);
576 if (!racc
->first_link
)
578 gcc_assert (!racc
->last_link
);
579 racc
->first_link
= link
;
582 racc
->last_link
->next
= link
;
584 racc
->last_link
= link
;
588 /* Move all link structures in their linked list in OLD_RACC to the linked list
591 relink_to_new_repr (struct access
*new_racc
, struct access
*old_racc
)
593 if (!old_racc
->first_link
)
595 gcc_assert (!old_racc
->last_link
);
599 if (new_racc
->first_link
)
601 gcc_assert (!new_racc
->last_link
->next
);
602 gcc_assert (!old_racc
->last_link
|| !old_racc
->last_link
->next
);
604 new_racc
->last_link
->next
= old_racc
->first_link
;
605 new_racc
->last_link
= old_racc
->last_link
;
609 gcc_assert (!new_racc
->last_link
);
611 new_racc
->first_link
= old_racc
->first_link
;
612 new_racc
->last_link
= old_racc
->last_link
;
614 old_racc
->first_link
= old_racc
->last_link
= NULL
;
617 /* Add ACCESS to the work queue (which is actually a stack). */
620 add_access_to_work_queue (struct access
*access
)
622 if (!access
->grp_queued
)
624 gcc_assert (!access
->next_queued
);
625 access
->next_queued
= work_queue_head
;
626 access
->grp_queued
= 1;
627 work_queue_head
= access
;
631 /* Pop an access from the work queue, and return it, assuming there is one. */
633 static struct access
*
634 pop_access_from_work_queue (void)
636 struct access
*access
= work_queue_head
;
638 work_queue_head
= access
->next_queued
;
639 access
->next_queued
= NULL
;
640 access
->grp_queued
= 0;
645 /* Allocate necessary structures. */
648 sra_initialize (void)
650 candidate_bitmap
= BITMAP_ALLOC (NULL
);
651 candidates
= new hash_table
<uid_decl_hasher
>
652 (vec_safe_length (cfun
->local_decls
) / 2);
653 should_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
654 cannot_scalarize_away_bitmap
= BITMAP_ALLOC (NULL
);
655 gcc_obstack_init (&name_obstack
);
656 base_access_vec
= new hash_map
<tree
, auto_vec
<access_p
> >;
657 memset (&sra_stats
, 0, sizeof (sra_stats
));
658 encountered_apply_args
= false;
659 encountered_recursive_call
= false;
660 encountered_unchangable_recursive_call
= false;
663 /* Deallocate all general structures. */
666 sra_deinitialize (void)
668 BITMAP_FREE (candidate_bitmap
);
671 BITMAP_FREE (should_scalarize_away_bitmap
);
672 BITMAP_FREE (cannot_scalarize_away_bitmap
);
673 access_pool
.release ();
674 assign_link_pool
.release ();
675 obstack_free (&name_obstack
, NULL
);
677 delete base_access_vec
;
680 /* Remove DECL from candidates for SRA and write REASON to the dump file if
683 disqualify_candidate (tree decl
, const char *reason
)
685 if (bitmap_clear_bit (candidate_bitmap
, DECL_UID (decl
)))
686 candidates
->remove_elt_with_hash (decl
, DECL_UID (decl
));
688 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
690 fprintf (dump_file
, "! Disqualifying ");
691 print_generic_expr (dump_file
, decl
, 0);
692 fprintf (dump_file
, " - %s\n", reason
);
696 /* Return true iff the type contains a field or an element which does not allow
700 type_internals_preclude_sra_p (tree type
, const char **msg
)
705 switch (TREE_CODE (type
))
709 case QUAL_UNION_TYPE
:
710 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
711 if (TREE_CODE (fld
) == FIELD_DECL
)
713 tree ft
= TREE_TYPE (fld
);
715 if (TREE_THIS_VOLATILE (fld
))
717 *msg
= "volatile structure field";
720 if (!DECL_FIELD_OFFSET (fld
))
722 *msg
= "no structure field offset";
725 if (!DECL_SIZE (fld
))
727 *msg
= "zero structure field size";
730 if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld
)))
732 *msg
= "structure field offset not fixed";
735 if (!tree_fits_uhwi_p (DECL_SIZE (fld
)))
737 *msg
= "structure field size not fixed";
740 if (!tree_fits_shwi_p (bit_position (fld
)))
742 *msg
= "structure field size too big";
745 if (AGGREGATE_TYPE_P (ft
)
746 && int_bit_position (fld
) % BITS_PER_UNIT
!= 0)
748 *msg
= "structure field is bit field";
752 if (AGGREGATE_TYPE_P (ft
) && type_internals_preclude_sra_p (ft
, msg
))
759 et
= TREE_TYPE (type
);
761 if (TYPE_VOLATILE (et
))
763 *msg
= "element type is volatile";
767 if (AGGREGATE_TYPE_P (et
) && type_internals_preclude_sra_p (et
, msg
))
777 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
778 base variable if it is. Return T if it is not an SSA_NAME. */
781 get_ssa_base_param (tree t
)
783 if (TREE_CODE (t
) == SSA_NAME
)
785 if (SSA_NAME_IS_DEFAULT_DEF (t
))
786 return SSA_NAME_VAR (t
);
793 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
794 belongs to, unless the BB has already been marked as a potentially
798 mark_parm_dereference (tree base
, HOST_WIDE_INT dist
, gimple
*stmt
)
800 basic_block bb
= gimple_bb (stmt
);
801 int idx
, parm_index
= 0;
804 if (bitmap_bit_p (final_bbs
, bb
->index
))
807 for (parm
= DECL_ARGUMENTS (current_function_decl
);
808 parm
&& parm
!= base
;
809 parm
= DECL_CHAIN (parm
))
812 gcc_assert (parm_index
< func_param_count
);
814 idx
= bb
->index
* func_param_count
+ parm_index
;
815 if (bb_dereferences
[idx
] < dist
)
816 bb_dereferences
[idx
] = dist
;
819 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
820 the three fields. Also add it to the vector of accesses corresponding to
821 the base. Finally, return the new access. */
823 static struct access
*
824 create_access_1 (tree base
, HOST_WIDE_INT offset
, HOST_WIDE_INT size
)
826 struct access
*access
= access_pool
.allocate ();
828 memset (access
, 0, sizeof (struct access
));
830 access
->offset
= offset
;
833 base_access_vec
->get_or_insert (base
).safe_push (access
);
838 /* Create and insert access for EXPR. Return created access, or NULL if it is
841 static struct access
*
842 create_access (tree expr
, gimple
*stmt
, bool write
)
844 struct access
*access
;
845 HOST_WIDE_INT offset
, size
, max_size
;
847 bool reverse
, ptr
, unscalarizable_region
= false;
849 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
, &reverse
);
851 if (sra_mode
== SRA_MODE_EARLY_IPA
852 && TREE_CODE (base
) == MEM_REF
)
854 base
= get_ssa_base_param (TREE_OPERAND (base
, 0));
862 if (!DECL_P (base
) || !bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
865 if (sra_mode
== SRA_MODE_EARLY_IPA
)
867 if (size
< 0 || size
!= max_size
)
869 disqualify_candidate (base
, "Encountered a variable sized access.");
872 if (TREE_CODE (expr
) == COMPONENT_REF
873 && DECL_BIT_FIELD (TREE_OPERAND (expr
, 1)))
875 disqualify_candidate (base
, "Encountered a bit-field access.");
878 gcc_checking_assert ((offset
% BITS_PER_UNIT
) == 0);
881 mark_parm_dereference (base
, offset
+ size
, stmt
);
885 if (size
!= max_size
)
888 unscalarizable_region
= true;
892 disqualify_candidate (base
, "Encountered an unconstrained access.");
897 access
= create_access_1 (base
, offset
, size
);
899 access
->type
= TREE_TYPE (expr
);
900 access
->write
= write
;
901 access
->grp_unscalarizable_region
= unscalarizable_region
;
903 access
->reverse
= reverse
;
905 if (TREE_CODE (expr
) == COMPONENT_REF
906 && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1)))
907 access
->non_addressable
= 1;
913 /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length
914 ARRAY_TYPE with fields that are either of gimple register types (excluding
915 bit-fields) or (recursively) scalarizable types. */
918 scalarizable_type_p (tree type
)
920 gcc_assert (!is_gimple_reg_type (type
));
922 switch (TREE_CODE (type
))
925 for (tree fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
926 if (TREE_CODE (fld
) == FIELD_DECL
)
928 tree ft
= TREE_TYPE (fld
);
930 if (DECL_BIT_FIELD (fld
))
933 if (!is_gimple_reg_type (ft
)
934 && !scalarizable_type_p (ft
))
942 if (TYPE_DOMAIN (type
) == NULL_TREE
943 || !tree_fits_shwi_p (TYPE_SIZE (type
))
944 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type
)))
945 || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type
))) <= 0)
946 || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type
))))
948 if (tree_to_shwi (TYPE_SIZE (type
)) == 0
949 && TYPE_MAX_VALUE (TYPE_DOMAIN (type
)) == NULL_TREE
)
950 /* Zero-element array, should not prevent scalarization. */
952 else if ((tree_to_shwi (TYPE_SIZE (type
)) <= 0)
953 || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type
))))
954 /* Variable-length array, do not allow scalarization. */
957 tree elem
= TREE_TYPE (type
);
958 if (!is_gimple_reg_type (elem
)
959 && !scalarizable_type_p (elem
))
968 static void scalarize_elem (tree
, HOST_WIDE_INT
, HOST_WIDE_INT
, bool, tree
, tree
);
970 /* Create total_scalarization accesses for all scalar fields of a member
971 of type DECL_TYPE conforming to scalarizable_type_p. BASE
972 must be the top-most VAR_DECL representing the variable; within that,
973 OFFSET locates the member and REF must be the memory reference expression for
977 completely_scalarize (tree base
, tree decl_type
, HOST_WIDE_INT offset
, tree ref
)
979 switch (TREE_CODE (decl_type
))
982 for (tree fld
= TYPE_FIELDS (decl_type
); fld
; fld
= DECL_CHAIN (fld
))
983 if (TREE_CODE (fld
) == FIELD_DECL
)
985 HOST_WIDE_INT pos
= offset
+ int_bit_position (fld
);
986 tree ft
= TREE_TYPE (fld
);
987 tree nref
= build3 (COMPONENT_REF
, ft
, ref
, fld
, NULL_TREE
);
989 scalarize_elem (base
, pos
, tree_to_uhwi (DECL_SIZE (fld
)),
990 TYPE_REVERSE_STORAGE_ORDER (decl_type
),
996 tree elemtype
= TREE_TYPE (decl_type
);
997 tree elem_size
= TYPE_SIZE (elemtype
);
998 gcc_assert (elem_size
&& tree_fits_shwi_p (elem_size
));
999 HOST_WIDE_INT el_size
= tree_to_shwi (elem_size
);
1000 gcc_assert (el_size
> 0);
1002 tree minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (decl_type
));
1003 gcc_assert (TREE_CODE (minidx
) == INTEGER_CST
);
1004 tree maxidx
= TYPE_MAX_VALUE (TYPE_DOMAIN (decl_type
));
1005 /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1008 gcc_assert (TREE_CODE (maxidx
) == INTEGER_CST
);
1009 tree domain
= TYPE_DOMAIN (decl_type
);
1010 /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1011 DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1012 offset_int idx
= wi::to_offset (minidx
);
1013 offset_int max
= wi::to_offset (maxidx
);
1014 if (!TYPE_UNSIGNED (domain
))
1016 idx
= wi::sext (idx
, TYPE_PRECISION (domain
));
1017 max
= wi::sext (max
, TYPE_PRECISION (domain
));
1019 for (int el_off
= offset
; wi::les_p (idx
, max
); ++idx
)
1021 tree nref
= build4 (ARRAY_REF
, elemtype
,
1023 wide_int_to_tree (domain
, idx
),
1024 NULL_TREE
, NULL_TREE
);
1025 scalarize_elem (base
, el_off
, el_size
,
1026 TYPE_REVERSE_STORAGE_ORDER (decl_type
),
1038 /* Create total_scalarization accesses for a member of type TYPE, which must
1039 satisfy either is_gimple_reg_type or scalarizable_type_p. BASE must be the
1040 top-most VAR_DECL representing the variable; within that, POS and SIZE locate
1041 the member, REVERSE gives its torage order. and REF must be the reference
1042 expression for it. */
1045 scalarize_elem (tree base
, HOST_WIDE_INT pos
, HOST_WIDE_INT size
, bool reverse
,
1046 tree ref
, tree type
)
1048 if (is_gimple_reg_type (type
))
1050 struct access
*access
= create_access_1 (base
, pos
, size
);
1052 access
->type
= type
;
1053 access
->grp_total_scalarization
= 1;
1054 access
->reverse
= reverse
;
1055 /* Accesses for intraprocedural SRA can have their stmt NULL. */
1058 completely_scalarize (base
, type
, pos
, ref
);
1061 /* Create a total_scalarization access for VAR as a whole. VAR must be of a
1062 RECORD_TYPE or ARRAY_TYPE conforming to scalarizable_type_p. */
1065 create_total_scalarization_access (tree var
)
1067 HOST_WIDE_INT size
= tree_to_uhwi (DECL_SIZE (var
));
1068 struct access
*access
;
1070 access
= create_access_1 (var
, 0, size
);
1072 access
->type
= TREE_TYPE (var
);
1073 access
->grp_total_scalarization
= 1;
1076 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1079 contains_view_convert_expr_p (const_tree ref
)
1081 while (handled_component_p (ref
))
1083 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
)
1085 ref
= TREE_OPERAND (ref
, 0);
1091 /* Search the given tree for a declaration by skipping handled components and
1092 exclude it from the candidates. */
1095 disqualify_base_of_expr (tree t
, const char *reason
)
1097 t
= get_base_address (t
);
1098 if (sra_mode
== SRA_MODE_EARLY_IPA
1099 && TREE_CODE (t
) == MEM_REF
)
1100 t
= get_ssa_base_param (TREE_OPERAND (t
, 0));
1102 if (t
&& DECL_P (t
))
1103 disqualify_candidate (t
, reason
);
1106 /* Scan expression EXPR and create access structures for all accesses to
1107 candidates for scalarization. Return the created access or NULL if none is
1110 static struct access
*
1111 build_access_from_expr_1 (tree expr
, gimple
*stmt
, bool write
)
1113 struct access
*ret
= NULL
;
1116 if (TREE_CODE (expr
) == BIT_FIELD_REF
1117 || TREE_CODE (expr
) == IMAGPART_EXPR
1118 || TREE_CODE (expr
) == REALPART_EXPR
)
1120 expr
= TREE_OPERAND (expr
, 0);
1124 partial_ref
= false;
1126 /* We need to dive through V_C_Es in order to get the size of its parameter
1127 and not the result type. Ada produces such statements. We are also
1128 capable of handling the topmost V_C_E but not any of those buried in other
1129 handled components. */
1130 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
&& !storage_order_barrier_p (expr
))
1131 expr
= TREE_OPERAND (expr
, 0);
1133 if (contains_view_convert_expr_p (expr
))
1135 disqualify_base_of_expr (expr
, "V_C_E under a different handled "
1139 if (TREE_THIS_VOLATILE (expr
))
1141 disqualify_base_of_expr (expr
, "part of a volatile reference.");
1145 switch (TREE_CODE (expr
))
1148 if (TREE_CODE (TREE_OPERAND (expr
, 0)) != ADDR_EXPR
1149 && sra_mode
!= SRA_MODE_EARLY_IPA
)
1157 case ARRAY_RANGE_REF
:
1158 ret
= create_access (expr
, stmt
, write
);
1165 if (write
&& partial_ref
&& ret
)
1166 ret
->grp_partial_lhs
= 1;
1171 /* Scan expression EXPR and create access structures for all accesses to
1172 candidates for scalarization. Return true if any access has been inserted.
1173 STMT must be the statement from which the expression is taken, WRITE must be
1174 true if the expression is a store and false otherwise. */
1177 build_access_from_expr (tree expr
, gimple
*stmt
, bool write
)
1179 struct access
*access
;
1181 access
= build_access_from_expr_1 (expr
, stmt
, write
);
1184 /* This means the aggregate is accesses as a whole in a way other than an
1185 assign statement and thus cannot be removed even if we had a scalar
1186 replacement for everything. */
1187 if (cannot_scalarize_away_bitmap
)
1188 bitmap_set_bit (cannot_scalarize_away_bitmap
, DECL_UID (access
->base
));
1194 /* Return the single non-EH successor edge of BB or NULL if there is none or
1198 single_non_eh_succ (basic_block bb
)
1203 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1204 if (!(e
->flags
& EDGE_EH
))
1214 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1215 there is no alternative spot where to put statements SRA might need to
1216 generate after it. The spot we are looking for is an edge leading to a
1217 single non-EH successor, if it exists and is indeed single. RHS may be
1218 NULL, in that case ignore it. */
1221 disqualify_if_bad_bb_terminating_stmt (gimple
*stmt
, tree lhs
, tree rhs
)
1223 if ((sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1224 && stmt_ends_bb_p (stmt
))
1226 if (single_non_eh_succ (gimple_bb (stmt
)))
1229 disqualify_base_of_expr (lhs
, "LHS of a throwing stmt.");
1231 disqualify_base_of_expr (rhs
, "RHS of a throwing stmt.");
1237 /* Scan expressions occurring in STMT, create access structures for all accesses
1238 to candidates for scalarization and remove those candidates which occur in
1239 statements or expressions that prevent them from being split apart. Return
1240 true if any access has been inserted. */
1243 build_accesses_from_assign (gimple
*stmt
)
1246 struct access
*lacc
, *racc
;
1248 if (!gimple_assign_single_p (stmt
)
1249 /* Scope clobbers don't influence scalarization. */
1250 || gimple_clobber_p (stmt
))
1253 lhs
= gimple_assign_lhs (stmt
);
1254 rhs
= gimple_assign_rhs1 (stmt
);
1256 if (disqualify_if_bad_bb_terminating_stmt (stmt
, lhs
, rhs
))
1259 racc
= build_access_from_expr_1 (rhs
, stmt
, false);
1260 lacc
= build_access_from_expr_1 (lhs
, stmt
, true);
1264 lacc
->grp_assignment_write
= 1;
1265 if (storage_order_barrier_p (rhs
))
1266 lacc
->grp_unscalarizable_region
= 1;
1271 racc
->grp_assignment_read
= 1;
1272 if (should_scalarize_away_bitmap
&& !gimple_has_volatile_ops (stmt
)
1273 && !is_gimple_reg_type (racc
->type
))
1274 bitmap_set_bit (should_scalarize_away_bitmap
, DECL_UID (racc
->base
));
1275 if (storage_order_barrier_p (lhs
))
1276 racc
->grp_unscalarizable_region
= 1;
1280 && (sra_mode
== SRA_MODE_EARLY_INTRA
|| sra_mode
== SRA_MODE_INTRA
)
1281 && !lacc
->grp_unscalarizable_region
1282 && !racc
->grp_unscalarizable_region
1283 && AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
1284 && lacc
->size
== racc
->size
1285 && useless_type_conversion_p (lacc
->type
, racc
->type
))
1287 struct assign_link
*link
;
1289 link
= assign_link_pool
.allocate ();
1290 memset (link
, 0, sizeof (struct assign_link
));
1295 add_link_to_rhs (racc
, link
);
1298 return lacc
|| racc
;
1301 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1302 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1305 asm_visit_addr (gimple
*, tree op
, tree
, void *)
1307 op
= get_base_address (op
);
1310 disqualify_candidate (op
, "Non-scalarizable GIMPLE_ASM operand.");
1315 /* Return true iff callsite CALL has at least as many actual arguments as there
1316 are formal parameters of the function currently processed by IPA-SRA and
1317 that their types match. */
1320 callsite_arguments_match_p (gimple
*call
)
1322 if (gimple_call_num_args (call
) < (unsigned) func_param_count
)
1327 for (parm
= DECL_ARGUMENTS (current_function_decl
), i
= 0;
1329 parm
= DECL_CHAIN (parm
), i
++)
1331 tree arg
= gimple_call_arg (call
, i
);
1332 if (!useless_type_conversion_p (TREE_TYPE (parm
), TREE_TYPE (arg
)))
1338 /* Scan function and look for interesting expressions and create access
1339 structures for them. Return true iff any access is created. */
1342 scan_function (void)
1347 FOR_EACH_BB_FN (bb
, cfun
)
1349 gimple_stmt_iterator gsi
;
1350 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1352 gimple
*stmt
= gsi_stmt (gsi
);
1356 if (final_bbs
&& stmt_can_throw_external (stmt
))
1357 bitmap_set_bit (final_bbs
, bb
->index
);
1358 switch (gimple_code (stmt
))
1361 t
= gimple_return_retval (as_a
<greturn
*> (stmt
));
1363 ret
|= build_access_from_expr (t
, stmt
, false);
1365 bitmap_set_bit (final_bbs
, bb
->index
);
1369 ret
|= build_accesses_from_assign (stmt
);
1373 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
1374 ret
|= build_access_from_expr (gimple_call_arg (stmt
, i
),
1377 if (sra_mode
== SRA_MODE_EARLY_IPA
)
1379 tree dest
= gimple_call_fndecl (stmt
);
1380 int flags
= gimple_call_flags (stmt
);
1384 if (DECL_BUILT_IN_CLASS (dest
) == BUILT_IN_NORMAL
1385 && DECL_FUNCTION_CODE (dest
) == BUILT_IN_APPLY_ARGS
)
1386 encountered_apply_args
= true;
1387 if (recursive_call_p (current_function_decl
, dest
))
1389 encountered_recursive_call
= true;
1390 if (!callsite_arguments_match_p (stmt
))
1391 encountered_unchangable_recursive_call
= true;
1396 && (flags
& (ECF_CONST
| ECF_PURE
)) == 0)
1397 bitmap_set_bit (final_bbs
, bb
->index
);
1400 t
= gimple_call_lhs (stmt
);
1401 if (t
&& !disqualify_if_bad_bb_terminating_stmt (stmt
, t
, NULL
))
1402 ret
|= build_access_from_expr (t
, stmt
, true);
1407 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1408 walk_stmt_load_store_addr_ops (asm_stmt
, NULL
, NULL
, NULL
,
1411 bitmap_set_bit (final_bbs
, bb
->index
);
1413 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
1415 t
= TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
1416 ret
|= build_access_from_expr (t
, asm_stmt
, false);
1418 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
1420 t
= TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
1421 ret
|= build_access_from_expr (t
, asm_stmt
, true);
1435 /* Helper of QSORT function. There are pointers to accesses in the array. An
1436 access is considered smaller than another if it has smaller offset or if the
1437 offsets are the same but is size is bigger. */
1440 compare_access_positions (const void *a
, const void *b
)
1442 const access_p
*fp1
= (const access_p
*) a
;
1443 const access_p
*fp2
= (const access_p
*) b
;
1444 const access_p f1
= *fp1
;
1445 const access_p f2
= *fp2
;
1447 if (f1
->offset
!= f2
->offset
)
1448 return f1
->offset
< f2
->offset
? -1 : 1;
1450 if (f1
->size
== f2
->size
)
1452 if (f1
->type
== f2
->type
)
1454 /* Put any non-aggregate type before any aggregate type. */
1455 else if (!is_gimple_reg_type (f1
->type
)
1456 && is_gimple_reg_type (f2
->type
))
1458 else if (is_gimple_reg_type (f1
->type
)
1459 && !is_gimple_reg_type (f2
->type
))
1461 /* Put any complex or vector type before any other scalar type. */
1462 else if (TREE_CODE (f1
->type
) != COMPLEX_TYPE
1463 && TREE_CODE (f1
->type
) != VECTOR_TYPE
1464 && (TREE_CODE (f2
->type
) == COMPLEX_TYPE
1465 || TREE_CODE (f2
->type
) == VECTOR_TYPE
))
1467 else if ((TREE_CODE (f1
->type
) == COMPLEX_TYPE
1468 || TREE_CODE (f1
->type
) == VECTOR_TYPE
)
1469 && TREE_CODE (f2
->type
) != COMPLEX_TYPE
1470 && TREE_CODE (f2
->type
) != VECTOR_TYPE
)
1472 /* Put the integral type with the bigger precision first. */
1473 else if (INTEGRAL_TYPE_P (f1
->type
)
1474 && INTEGRAL_TYPE_P (f2
->type
))
1475 return TYPE_PRECISION (f2
->type
) - TYPE_PRECISION (f1
->type
);
1476 /* Put any integral type with non-full precision last. */
1477 else if (INTEGRAL_TYPE_P (f1
->type
)
1478 && (TREE_INT_CST_LOW (TYPE_SIZE (f1
->type
))
1479 != TYPE_PRECISION (f1
->type
)))
1481 else if (INTEGRAL_TYPE_P (f2
->type
)
1482 && (TREE_INT_CST_LOW (TYPE_SIZE (f2
->type
))
1483 != TYPE_PRECISION (f2
->type
)))
1485 /* Stabilize the sort. */
1486 return TYPE_UID (f1
->type
) - TYPE_UID (f2
->type
);
1489 /* We want the bigger accesses first, thus the opposite operator in the next
1491 return f1
->size
> f2
->size
? -1 : 1;
1495 /* Append a name of the declaration to the name obstack. A helper function for
1499 make_fancy_decl_name (tree decl
)
1503 tree name
= DECL_NAME (decl
);
1505 obstack_grow (&name_obstack
, IDENTIFIER_POINTER (name
),
1506 IDENTIFIER_LENGTH (name
));
1509 sprintf (buffer
, "D%u", DECL_UID (decl
));
1510 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1514 /* Helper for make_fancy_name. */
1517 make_fancy_name_1 (tree expr
)
1524 make_fancy_decl_name (expr
);
1528 switch (TREE_CODE (expr
))
1531 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1532 obstack_1grow (&name_obstack
, '$');
1533 make_fancy_decl_name (TREE_OPERAND (expr
, 1));
1537 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1538 obstack_1grow (&name_obstack
, '$');
1539 /* Arrays with only one element may not have a constant as their
1541 index
= TREE_OPERAND (expr
, 1);
1542 if (TREE_CODE (index
) != INTEGER_CST
)
1544 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
, TREE_INT_CST_LOW (index
));
1545 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1549 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1553 make_fancy_name_1 (TREE_OPERAND (expr
, 0));
1554 if (!integer_zerop (TREE_OPERAND (expr
, 1)))
1556 obstack_1grow (&name_obstack
, '$');
1557 sprintf (buffer
, HOST_WIDE_INT_PRINT_DEC
,
1558 TREE_INT_CST_LOW (TREE_OPERAND (expr
, 1)));
1559 obstack_grow (&name_obstack
, buffer
, strlen (buffer
));
1566 gcc_unreachable (); /* we treat these as scalars. */
1573 /* Create a human readable name for replacement variable of ACCESS. */
1576 make_fancy_name (tree expr
)
1578 make_fancy_name_1 (expr
);
1579 obstack_1grow (&name_obstack
, '\0');
1580 return XOBFINISH (&name_obstack
, char *);
1583 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1584 EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1585 something for which get_addr_base_and_unit_offset returns NULL, gsi must
1586 be non-NULL and is used to insert new statements either before or below
1587 the current one as specified by INSERT_AFTER. This function is not capable
1588 of handling bitfields. */
1591 build_ref_for_offset (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1592 bool reverse
, tree exp_type
, gimple_stmt_iterator
*gsi
,
1595 tree prev_base
= base
;
1598 HOST_WIDE_INT base_offset
;
1599 unsigned HOST_WIDE_INT misalign
;
1602 gcc_checking_assert (offset
% BITS_PER_UNIT
== 0);
1603 get_object_alignment_1 (base
, &align
, &misalign
);
1604 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1606 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1607 offset such as array[var_index]. */
1613 gcc_checking_assert (gsi
);
1614 tmp
= make_ssa_name (build_pointer_type (TREE_TYPE (prev_base
)));
1615 addr
= build_fold_addr_expr (unshare_expr (prev_base
));
1616 STRIP_USELESS_TYPE_CONVERSION (addr
);
1617 stmt
= gimple_build_assign (tmp
, addr
);
1618 gimple_set_location (stmt
, loc
);
1620 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
1622 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1624 off
= build_int_cst (reference_alias_ptr_type (prev_base
),
1625 offset
/ BITS_PER_UNIT
);
1628 else if (TREE_CODE (base
) == MEM_REF
)
1630 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1631 base_offset
+ offset
/ BITS_PER_UNIT
);
1632 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1633 base
= unshare_expr (TREE_OPERAND (base
, 0));
1637 off
= build_int_cst (reference_alias_ptr_type (base
),
1638 base_offset
+ offset
/ BITS_PER_UNIT
);
1639 base
= build_fold_addr_expr (unshare_expr (base
));
1642 misalign
= (misalign
+ offset
) & (align
- 1);
1644 align
= (misalign
& -misalign
);
1645 if (align
!= TYPE_ALIGN (exp_type
))
1646 exp_type
= build_aligned_type (exp_type
, align
);
1648 mem_ref
= fold_build2_loc (loc
, MEM_REF
, exp_type
, base
, off
);
1649 REF_REVERSE_STORAGE_ORDER (mem_ref
) = reverse
;
1650 if (TREE_THIS_VOLATILE (prev_base
))
1651 TREE_THIS_VOLATILE (mem_ref
) = 1;
1652 if (TREE_SIDE_EFFECTS (prev_base
))
1653 TREE_SIDE_EFFECTS (mem_ref
) = 1;
1657 /* Construct a memory reference to a part of an aggregate BASE at the given
1658 OFFSET and of the same type as MODEL. In case this is a reference to a
1659 bit-field, the function will replicate the last component_ref of model's
1660 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1661 build_ref_for_offset. */
1664 build_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1665 struct access
*model
, gimple_stmt_iterator
*gsi
,
1668 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1669 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1671 /* This access represents a bit-field. */
1672 tree t
, exp_type
, fld
= TREE_OPERAND (model
->expr
, 1);
1674 offset
-= int_bit_position (fld
);
1675 exp_type
= TREE_TYPE (TREE_OPERAND (model
->expr
, 0));
1676 t
= build_ref_for_offset (loc
, base
, offset
, model
->reverse
, exp_type
,
1678 /* The flag will be set on the record type. */
1679 REF_REVERSE_STORAGE_ORDER (t
) = 0;
1680 return fold_build3_loc (loc
, COMPONENT_REF
, TREE_TYPE (fld
), t
, fld
,
1685 build_ref_for_offset (loc
, base
, offset
, model
->reverse
, model
->type
,
1689 /* Attempt to build a memory reference that we could but into a gimple
1690 debug_bind statement. Similar to build_ref_for_model but punts if it has to
1691 create statements and return s NULL instead. This function also ignores
1692 alignment issues and so its results should never end up in non-debug
1696 build_debug_ref_for_model (location_t loc
, tree base
, HOST_WIDE_INT offset
,
1697 struct access
*model
)
1699 HOST_WIDE_INT base_offset
;
1702 if (TREE_CODE (model
->expr
) == COMPONENT_REF
1703 && DECL_BIT_FIELD (TREE_OPERAND (model
->expr
, 1)))
1706 base
= get_addr_base_and_unit_offset (base
, &base_offset
);
1709 if (TREE_CODE (base
) == MEM_REF
)
1711 off
= build_int_cst (TREE_TYPE (TREE_OPERAND (base
, 1)),
1712 base_offset
+ offset
/ BITS_PER_UNIT
);
1713 off
= int_const_binop (PLUS_EXPR
, TREE_OPERAND (base
, 1), off
);
1714 base
= unshare_expr (TREE_OPERAND (base
, 0));
1718 off
= build_int_cst (reference_alias_ptr_type (base
),
1719 base_offset
+ offset
/ BITS_PER_UNIT
);
1720 base
= build_fold_addr_expr (unshare_expr (base
));
1723 return fold_build2_loc (loc
, MEM_REF
, model
->type
, base
, off
);
1726 /* Construct a memory reference consisting of component_refs and array_refs to
1727 a part of an aggregate *RES (which is of type TYPE). The requested part
1728 should have type EXP_TYPE at be the given OFFSET. This function might not
1729 succeed, it returns true when it does and only then *RES points to something
1730 meaningful. This function should be used only to build expressions that we
1731 might need to present to user (e.g. in warnings). In all other situations,
1732 build_ref_for_model or build_ref_for_offset should be used instead. */
1735 build_user_friendly_ref_for_offset (tree
*res
, tree type
, HOST_WIDE_INT offset
,
1741 tree tr_size
, index
, minidx
;
1742 HOST_WIDE_INT el_size
;
1744 if (offset
== 0 && exp_type
1745 && types_compatible_p (exp_type
, type
))
1748 switch (TREE_CODE (type
))
1751 case QUAL_UNION_TYPE
:
1753 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1755 HOST_WIDE_INT pos
, size
;
1756 tree tr_pos
, expr
, *expr_ptr
;
1758 if (TREE_CODE (fld
) != FIELD_DECL
)
1761 tr_pos
= bit_position (fld
);
1762 if (!tr_pos
|| !tree_fits_uhwi_p (tr_pos
))
1764 pos
= tree_to_uhwi (tr_pos
);
1765 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
|| pos
== 0);
1766 tr_size
= DECL_SIZE (fld
);
1767 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1769 size
= tree_to_uhwi (tr_size
);
1775 else if (pos
> offset
|| (pos
+ size
) <= offset
)
1778 expr
= build3 (COMPONENT_REF
, TREE_TYPE (fld
), *res
, fld
,
1781 if (build_user_friendly_ref_for_offset (expr_ptr
, TREE_TYPE (fld
),
1782 offset
- pos
, exp_type
))
1791 tr_size
= TYPE_SIZE (TREE_TYPE (type
));
1792 if (!tr_size
|| !tree_fits_uhwi_p (tr_size
))
1794 el_size
= tree_to_uhwi (tr_size
);
1796 minidx
= TYPE_MIN_VALUE (TYPE_DOMAIN (type
));
1797 if (TREE_CODE (minidx
) != INTEGER_CST
|| el_size
== 0)
1799 index
= build_int_cst (TYPE_DOMAIN (type
), offset
/ el_size
);
1800 if (!integer_zerop (minidx
))
1801 index
= int_const_binop (PLUS_EXPR
, index
, minidx
);
1802 *res
= build4 (ARRAY_REF
, TREE_TYPE (type
), *res
, index
,
1803 NULL_TREE
, NULL_TREE
);
1804 offset
= offset
% el_size
;
1805 type
= TREE_TYPE (type
);
1820 /* Return true iff TYPE is stdarg va_list type. */
1823 is_va_list_type (tree type
)
1825 return TYPE_MAIN_VARIANT (type
) == TYPE_MAIN_VARIANT (va_list_type_node
);
1828 /* Print message to dump file why a variable was rejected. */
1831 reject (tree var
, const char *msg
)
1833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1835 fprintf (dump_file
, "Rejected (%d): %s: ", DECL_UID (var
), msg
);
1836 print_generic_expr (dump_file
, var
, 0);
1837 fprintf (dump_file
, "\n");
1841 /* Return true if VAR is a candidate for SRA. */
1844 maybe_add_sra_candidate (tree var
)
1846 tree type
= TREE_TYPE (var
);
1850 if (!AGGREGATE_TYPE_P (type
))
1852 reject (var
, "not aggregate");
1855 if (needs_to_live_in_memory (var
))
1857 reject (var
, "needs to live in memory");
1860 if (TREE_THIS_VOLATILE (var
))
1862 reject (var
, "is volatile");
1865 if (!COMPLETE_TYPE_P (type
))
1867 reject (var
, "has incomplete type");
1870 if (!tree_fits_uhwi_p (TYPE_SIZE (type
)))
1872 reject (var
, "type size not fixed");
1875 if (tree_to_uhwi (TYPE_SIZE (type
)) == 0)
1877 reject (var
, "type size is zero");
1880 if (type_internals_preclude_sra_p (type
, &msg
))
1885 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
1886 we also want to schedule it rather late. Thus we ignore it in
1888 (sra_mode
== SRA_MODE_EARLY_INTRA
1889 && is_va_list_type (type
)))
1891 reject (var
, "is va_list");
1895 bitmap_set_bit (candidate_bitmap
, DECL_UID (var
));
1896 slot
= candidates
->find_slot_with_hash (var
, DECL_UID (var
), INSERT
);
1899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1901 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (var
));
1902 print_generic_expr (dump_file
, var
, 0);
1903 fprintf (dump_file
, "\n");
1909 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1910 those with type which is suitable for scalarization. */
1913 find_var_candidates (void)
1919 for (parm
= DECL_ARGUMENTS (current_function_decl
);
1921 parm
= DECL_CHAIN (parm
))
1922 ret
|= maybe_add_sra_candidate (parm
);
1924 FOR_EACH_LOCAL_DECL (cfun
, i
, var
)
1926 if (TREE_CODE (var
) != VAR_DECL
)
1929 ret
|= maybe_add_sra_candidate (var
);
1935 /* Sort all accesses for the given variable, check for partial overlaps and
1936 return NULL if there are any. If there are none, pick a representative for
1937 each combination of offset and size and create a linked list out of them.
1938 Return the pointer to the first representative and make sure it is the first
1939 one in the vector of accesses. */
1941 static struct access
*
1942 sort_and_splice_var_accesses (tree var
)
1944 int i
, j
, access_count
;
1945 struct access
*res
, **prev_acc_ptr
= &res
;
1946 vec
<access_p
> *access_vec
;
1948 HOST_WIDE_INT low
= -1, high
= 0;
1950 access_vec
= get_base_access_vector (var
);
1953 access_count
= access_vec
->length ();
1955 /* Sort by <OFFSET, SIZE>. */
1956 access_vec
->qsort (compare_access_positions
);
1959 while (i
< access_count
)
1961 struct access
*access
= (*access_vec
)[i
];
1962 bool grp_write
= access
->write
;
1963 bool grp_read
= !access
->write
;
1964 bool grp_scalar_write
= access
->write
1965 && is_gimple_reg_type (access
->type
);
1966 bool grp_scalar_read
= !access
->write
1967 && is_gimple_reg_type (access
->type
);
1968 bool grp_assignment_read
= access
->grp_assignment_read
;
1969 bool grp_assignment_write
= access
->grp_assignment_write
;
1970 bool multiple_scalar_reads
= false;
1971 bool total_scalarization
= access
->grp_total_scalarization
;
1972 bool grp_partial_lhs
= access
->grp_partial_lhs
;
1973 bool first_scalar
= is_gimple_reg_type (access
->type
);
1974 bool unscalarizable_region
= access
->grp_unscalarizable_region
;
1976 if (first
|| access
->offset
>= high
)
1979 low
= access
->offset
;
1980 high
= access
->offset
+ access
->size
;
1982 else if (access
->offset
> low
&& access
->offset
+ access
->size
> high
)
1985 gcc_assert (access
->offset
>= low
1986 && access
->offset
+ access
->size
<= high
);
1989 while (j
< access_count
)
1991 struct access
*ac2
= (*access_vec
)[j
];
1992 if (ac2
->offset
!= access
->offset
|| ac2
->size
!= access
->size
)
1997 grp_scalar_write
= (grp_scalar_write
1998 || is_gimple_reg_type (ac2
->type
));
2003 if (is_gimple_reg_type (ac2
->type
))
2005 if (grp_scalar_read
)
2006 multiple_scalar_reads
= true;
2008 grp_scalar_read
= true;
2011 grp_assignment_read
|= ac2
->grp_assignment_read
;
2012 grp_assignment_write
|= ac2
->grp_assignment_write
;
2013 grp_partial_lhs
|= ac2
->grp_partial_lhs
;
2014 unscalarizable_region
|= ac2
->grp_unscalarizable_region
;
2015 total_scalarization
|= ac2
->grp_total_scalarization
;
2016 relink_to_new_repr (access
, ac2
);
2018 /* If there are both aggregate-type and scalar-type accesses with
2019 this combination of size and offset, the comparison function
2020 should have put the scalars first. */
2021 gcc_assert (first_scalar
|| !is_gimple_reg_type (ac2
->type
));
2022 ac2
->group_representative
= access
;
2028 access
->group_representative
= access
;
2029 access
->grp_write
= grp_write
;
2030 access
->grp_read
= grp_read
;
2031 access
->grp_scalar_read
= grp_scalar_read
;
2032 access
->grp_scalar_write
= grp_scalar_write
;
2033 access
->grp_assignment_read
= grp_assignment_read
;
2034 access
->grp_assignment_write
= grp_assignment_write
;
2035 access
->grp_hint
= multiple_scalar_reads
|| total_scalarization
;
2036 access
->grp_total_scalarization
= total_scalarization
;
2037 access
->grp_partial_lhs
= grp_partial_lhs
;
2038 access
->grp_unscalarizable_region
= unscalarizable_region
;
2039 if (access
->first_link
)
2040 add_access_to_work_queue (access
);
2042 *prev_acc_ptr
= access
;
2043 prev_acc_ptr
= &access
->next_grp
;
2046 gcc_assert (res
== (*access_vec
)[0]);
2050 /* Create a variable for the given ACCESS which determines the type, name and a
2051 few other properties. Return the variable declaration and store it also to
2052 ACCESS->replacement. */
2055 create_access_replacement (struct access
*access
)
2059 if (access
->grp_to_be_debug_replaced
)
2061 repl
= create_tmp_var_raw (access
->type
);
2062 DECL_CONTEXT (repl
) = current_function_decl
;
2065 /* Drop any special alignment on the type if it's not on the main
2066 variant. This avoids issues with weirdo ABIs like AAPCS. */
2067 repl
= create_tmp_var (build_qualified_type
2068 (TYPE_MAIN_VARIANT (access
->type
),
2069 TYPE_QUALS (access
->type
)), "SR");
2070 if (TREE_CODE (access
->type
) == COMPLEX_TYPE
2071 || TREE_CODE (access
->type
) == VECTOR_TYPE
)
2073 if (!access
->grp_partial_lhs
)
2074 DECL_GIMPLE_REG_P (repl
) = 1;
2076 else if (access
->grp_partial_lhs
2077 && is_gimple_reg_type (access
->type
))
2078 TREE_ADDRESSABLE (repl
) = 1;
2080 DECL_SOURCE_LOCATION (repl
) = DECL_SOURCE_LOCATION (access
->base
);
2081 DECL_ARTIFICIAL (repl
) = 1;
2082 DECL_IGNORED_P (repl
) = DECL_IGNORED_P (access
->base
);
2084 if (DECL_NAME (access
->base
)
2085 && !DECL_IGNORED_P (access
->base
)
2086 && !DECL_ARTIFICIAL (access
->base
))
2088 char *pretty_name
= make_fancy_name (access
->expr
);
2089 tree debug_expr
= unshare_expr_without_location (access
->expr
), d
;
2092 DECL_NAME (repl
) = get_identifier (pretty_name
);
2093 obstack_free (&name_obstack
, pretty_name
);
2095 /* Get rid of any SSA_NAMEs embedded in debug_expr,
2096 as DECL_DEBUG_EXPR isn't considered when looking for still
2097 used SSA_NAMEs and thus they could be freed. All debug info
2098 generation cares is whether something is constant or variable
2099 and that get_ref_base_and_extent works properly on the
2100 expression. It cannot handle accesses at a non-constant offset
2101 though, so just give up in those cases. */
2102 for (d
= debug_expr
;
2103 !fail
&& (handled_component_p (d
) || TREE_CODE (d
) == MEM_REF
);
2104 d
= TREE_OPERAND (d
, 0))
2105 switch (TREE_CODE (d
))
2108 case ARRAY_RANGE_REF
:
2109 if (TREE_OPERAND (d
, 1)
2110 && TREE_CODE (TREE_OPERAND (d
, 1)) != INTEGER_CST
)
2112 if (TREE_OPERAND (d
, 3)
2113 && TREE_CODE (TREE_OPERAND (d
, 3)) != INTEGER_CST
)
2117 if (TREE_OPERAND (d
, 2)
2118 && TREE_CODE (TREE_OPERAND (d
, 2)) != INTEGER_CST
)
2122 if (TREE_CODE (TREE_OPERAND (d
, 0)) != ADDR_EXPR
)
2125 d
= TREE_OPERAND (d
, 0);
2132 SET_DECL_DEBUG_EXPR (repl
, debug_expr
);
2133 DECL_HAS_DEBUG_EXPR_P (repl
) = 1;
2135 if (access
->grp_no_warning
)
2136 TREE_NO_WARNING (repl
) = 1;
2138 TREE_NO_WARNING (repl
) = TREE_NO_WARNING (access
->base
);
2141 TREE_NO_WARNING (repl
) = 1;
2145 if (access
->grp_to_be_debug_replaced
)
2147 fprintf (dump_file
, "Created a debug-only replacement for ");
2148 print_generic_expr (dump_file
, access
->base
, 0);
2149 fprintf (dump_file
, " offset: %u, size: %u\n",
2150 (unsigned) access
->offset
, (unsigned) access
->size
);
2154 fprintf (dump_file
, "Created a replacement for ");
2155 print_generic_expr (dump_file
, access
->base
, 0);
2156 fprintf (dump_file
, " offset: %u, size: %u: ",
2157 (unsigned) access
->offset
, (unsigned) access
->size
);
2158 print_generic_expr (dump_file
, repl
, 0);
2159 fprintf (dump_file
, "\n");
2162 sra_stats
.replacements
++;
2167 /* Return ACCESS scalar replacement, which must exist. */
2170 get_access_replacement (struct access
*access
)
2172 gcc_checking_assert (access
->replacement_decl
);
2173 return access
->replacement_decl
;
2177 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2178 linked list along the way. Stop when *ACCESS is NULL or the access pointed
2179 to it is not "within" the root. Return false iff some accesses partially
2183 build_access_subtree (struct access
**access
)
2185 struct access
*root
= *access
, *last_child
= NULL
;
2186 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2188 *access
= (*access
)->next_grp
;
2189 while (*access
&& (*access
)->offset
+ (*access
)->size
<= limit
)
2192 root
->first_child
= *access
;
2194 last_child
->next_sibling
= *access
;
2195 last_child
= *access
;
2197 if (!build_access_subtree (access
))
2201 if (*access
&& (*access
)->offset
< limit
)
2207 /* Build a tree of access representatives, ACCESS is the pointer to the first
2208 one, others are linked in a list by the next_grp field. Return false iff
2209 some accesses partially overlap. */
2212 build_access_trees (struct access
*access
)
2216 struct access
*root
= access
;
2218 if (!build_access_subtree (&access
))
2220 root
->next_grp
= access
;
2225 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2229 expr_with_var_bounded_array_refs_p (tree expr
)
2231 while (handled_component_p (expr
))
2233 if (TREE_CODE (expr
) == ARRAY_REF
2234 && !tree_fits_shwi_p (array_ref_low_bound (expr
)))
2236 expr
= TREE_OPERAND (expr
, 0);
2241 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2242 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all
2243 sorts of access flags appropriately along the way, notably always set
2244 grp_read and grp_assign_read according to MARK_READ and grp_write when
2247 Creating a replacement for a scalar access is considered beneficial if its
2248 grp_hint is set (this means we are either attempting total scalarization or
2249 there is more than one direct read access) or according to the following
2252 Access written to through a scalar type (once or more times)
2254 | Written to in an assignment statement
2256 | | Access read as scalar _once_
2258 | | | Read in an assignment statement
2260 | | | | Scalarize Comment
2261 -----------------------------------------------------------------------------
2262 0 0 0 0 No access for the scalar
2263 0 0 0 1 No access for the scalar
2264 0 0 1 0 No Single read - won't help
2265 0 0 1 1 No The same case
2266 0 1 0 0 No access for the scalar
2267 0 1 0 1 No access for the scalar
2268 0 1 1 0 Yes s = *g; return s.i;
2269 0 1 1 1 Yes The same case as above
2270 1 0 0 0 No Won't help
2271 1 0 0 1 Yes s.i = 1; *g = s;
2272 1 0 1 0 Yes s.i = 5; g = s.i;
2273 1 0 1 1 Yes The same case as above
2274 1 1 0 0 No Won't help.
2275 1 1 0 1 Yes s.i = 1; *g = s;
2276 1 1 1 0 Yes s = *g; return s.i;
2277 1 1 1 1 Yes Any of the above yeses */
2280 analyze_access_subtree (struct access
*root
, struct access
*parent
,
2281 bool allow_replacements
)
2283 struct access
*child
;
2284 HOST_WIDE_INT limit
= root
->offset
+ root
->size
;
2285 HOST_WIDE_INT covered_to
= root
->offset
;
2286 bool scalar
= is_gimple_reg_type (root
->type
);
2287 bool hole
= false, sth_created
= false;
2291 if (parent
->grp_read
)
2293 if (parent
->grp_assignment_read
)
2294 root
->grp_assignment_read
= 1;
2295 if (parent
->grp_write
)
2296 root
->grp_write
= 1;
2297 if (parent
->grp_assignment_write
)
2298 root
->grp_assignment_write
= 1;
2299 if (parent
->grp_total_scalarization
)
2300 root
->grp_total_scalarization
= 1;
2303 if (root
->grp_unscalarizable_region
)
2304 allow_replacements
= false;
2306 if (allow_replacements
&& expr_with_var_bounded_array_refs_p (root
->expr
))
2307 allow_replacements
= false;
2309 for (child
= root
->first_child
; child
; child
= child
->next_sibling
)
2311 hole
|= covered_to
< child
->offset
;
2312 sth_created
|= analyze_access_subtree (child
, root
,
2313 allow_replacements
&& !scalar
);
2315 root
->grp_unscalarized_data
|= child
->grp_unscalarized_data
;
2316 root
->grp_total_scalarization
&= child
->grp_total_scalarization
;
2317 if (child
->grp_covered
)
2318 covered_to
+= child
->size
;
2323 if (allow_replacements
&& scalar
&& !root
->first_child
2325 || ((root
->grp_scalar_read
|| root
->grp_assignment_read
)
2326 && (root
->grp_scalar_write
|| root
->grp_assignment_write
))))
2328 /* Always create access replacements that cover the whole access.
2329 For integral types this means the precision has to match.
2330 Avoid assumptions based on the integral type kind, too. */
2331 if (INTEGRAL_TYPE_P (root
->type
)
2332 && (TREE_CODE (root
->type
) != INTEGER_TYPE
2333 || TYPE_PRECISION (root
->type
) != root
->size
)
2334 /* But leave bitfield accesses alone. */
2335 && (TREE_CODE (root
->expr
) != COMPONENT_REF
2336 || !DECL_BIT_FIELD (TREE_OPERAND (root
->expr
, 1))))
2338 tree rt
= root
->type
;
2339 gcc_assert ((root
->offset
% BITS_PER_UNIT
) == 0
2340 && (root
->size
% BITS_PER_UNIT
) == 0);
2341 root
->type
= build_nonstandard_integer_type (root
->size
,
2342 TYPE_UNSIGNED (rt
));
2343 root
->expr
= build_ref_for_offset (UNKNOWN_LOCATION
, root
->base
,
2344 root
->offset
, root
->reverse
,
2345 root
->type
, NULL
, false);
2347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2349 fprintf (dump_file
, "Changing the type of a replacement for ");
2350 print_generic_expr (dump_file
, root
->base
, 0);
2351 fprintf (dump_file
, " offset: %u, size: %u ",
2352 (unsigned) root
->offset
, (unsigned) root
->size
);
2353 fprintf (dump_file
, " to an integer.\n");
2357 root
->grp_to_be_replaced
= 1;
2358 root
->replacement_decl
= create_access_replacement (root
);
2364 if (allow_replacements
2365 && scalar
&& !root
->first_child
2366 && (root
->grp_scalar_write
|| root
->grp_assignment_write
)
2367 && !bitmap_bit_p (cannot_scalarize_away_bitmap
,
2368 DECL_UID (root
->base
)))
2370 gcc_checking_assert (!root
->grp_scalar_read
2371 && !root
->grp_assignment_read
);
2373 if (MAY_HAVE_DEBUG_STMTS
)
2375 root
->grp_to_be_debug_replaced
= 1;
2376 root
->replacement_decl
= create_access_replacement (root
);
2380 if (covered_to
< limit
)
2383 root
->grp_total_scalarization
= 0;
2386 if (!hole
|| root
->grp_total_scalarization
)
2387 root
->grp_covered
= 1;
2388 else if (root
->grp_write
|| TREE_CODE (root
->base
) == PARM_DECL
)
2389 root
->grp_unscalarized_data
= 1; /* not covered and written to */
2393 /* Analyze all access trees linked by next_grp by the means of
2394 analyze_access_subtree. */
2396 analyze_access_trees (struct access
*access
)
2402 if (analyze_access_subtree (access
, NULL
, true))
2404 access
= access
->next_grp
;
2410 /* Return true iff a potential new child of LACC at offset OFFSET and with size
2411 SIZE would conflict with an already existing one. If exactly such a child
2412 already exists in LACC, store a pointer to it in EXACT_MATCH. */
2415 child_would_conflict_in_lacc (struct access
*lacc
, HOST_WIDE_INT norm_offset
,
2416 HOST_WIDE_INT size
, struct access
**exact_match
)
2418 struct access
*child
;
2420 for (child
= lacc
->first_child
; child
; child
= child
->next_sibling
)
2422 if (child
->offset
== norm_offset
&& child
->size
== size
)
2424 *exact_match
= child
;
2428 if (child
->offset
< norm_offset
+ size
2429 && child
->offset
+ child
->size
> norm_offset
)
2436 /* Create a new child access of PARENT, with all properties just like MODEL
2437 except for its offset and with its grp_write false and grp_read true.
2438 Return the new access or NULL if it cannot be created. Note that this access
2439 is created long after all splicing and sorting, it's not located in any
2440 access vector and is automatically a representative of its group. */
2442 static struct access
*
2443 create_artificial_child_access (struct access
*parent
, struct access
*model
,
2444 HOST_WIDE_INT new_offset
)
2446 struct access
**child
;
2447 tree expr
= parent
->base
;
2449 gcc_assert (!model
->grp_unscalarizable_region
);
2451 struct access
*access
= access_pool
.allocate ();
2452 memset (access
, 0, sizeof (struct access
));
2453 if (!build_user_friendly_ref_for_offset (&expr
, TREE_TYPE (expr
), new_offset
,
2456 access
->grp_no_warning
= true;
2457 expr
= build_ref_for_model (EXPR_LOCATION (parent
->base
), parent
->base
,
2458 new_offset
, model
, NULL
, false);
2461 access
->base
= parent
->base
;
2462 access
->expr
= expr
;
2463 access
->offset
= new_offset
;
2464 access
->size
= model
->size
;
2465 access
->type
= model
->type
;
2466 access
->grp_write
= true;
2467 access
->grp_read
= false;
2468 access
->reverse
= model
->reverse
;
2470 child
= &parent
->first_child
;
2471 while (*child
&& (*child
)->offset
< new_offset
)
2472 child
= &(*child
)->next_sibling
;
2474 access
->next_sibling
= *child
;
2481 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
2482 true if any new subaccess was created. Additionally, if RACC is a scalar
2483 access but LACC is not, change the type of the latter, if possible. */
2486 propagate_subaccesses_across_link (struct access
*lacc
, struct access
*racc
)
2488 struct access
*rchild
;
2489 HOST_WIDE_INT norm_delta
= lacc
->offset
- racc
->offset
;
2492 if (is_gimple_reg_type (lacc
->type
)
2493 || lacc
->grp_unscalarizable_region
2494 || racc
->grp_unscalarizable_region
)
2497 if (is_gimple_reg_type (racc
->type
))
2499 if (!lacc
->first_child
&& !racc
->first_child
)
2501 tree t
= lacc
->base
;
2503 lacc
->type
= racc
->type
;
2504 if (build_user_friendly_ref_for_offset (&t
, TREE_TYPE (t
),
2505 lacc
->offset
, racc
->type
))
2509 lacc
->expr
= build_ref_for_model (EXPR_LOCATION (lacc
->base
),
2510 lacc
->base
, lacc
->offset
,
2512 lacc
->grp_no_warning
= true;
2518 for (rchild
= racc
->first_child
; rchild
; rchild
= rchild
->next_sibling
)
2520 struct access
*new_acc
= NULL
;
2521 HOST_WIDE_INT norm_offset
= rchild
->offset
+ norm_delta
;
2523 if (rchild
->grp_unscalarizable_region
)
2526 if (child_would_conflict_in_lacc (lacc
, norm_offset
, rchild
->size
,
2531 rchild
->grp_hint
= 1;
2532 new_acc
->grp_hint
|= new_acc
->grp_read
;
2533 if (rchild
->first_child
)
2534 ret
|= propagate_subaccesses_across_link (new_acc
, rchild
);
2539 rchild
->grp_hint
= 1;
2540 new_acc
= create_artificial_child_access (lacc
, rchild
, norm_offset
);
2544 if (racc
->first_child
)
2545 propagate_subaccesses_across_link (new_acc
, rchild
);
2552 /* Propagate all subaccesses across assignment links. */
2555 propagate_all_subaccesses (void)
2557 while (work_queue_head
)
2559 struct access
*racc
= pop_access_from_work_queue ();
2560 struct assign_link
*link
;
2562 gcc_assert (racc
->first_link
);
2564 for (link
= racc
->first_link
; link
; link
= link
->next
)
2566 struct access
*lacc
= link
->lacc
;
2568 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (lacc
->base
)))
2570 lacc
= lacc
->group_representative
;
2571 if (propagate_subaccesses_across_link (lacc
, racc
)
2572 && lacc
->first_link
)
2573 add_access_to_work_queue (lacc
);
2578 /* Go through all accesses collected throughout the (intraprocedural) analysis
2579 stage, exclude overlapping ones, identify representatives and build trees
2580 out of them, making decisions about scalarization on the way. Return true
2581 iff there are any to-be-scalarized variables after this stage. */
2584 analyze_all_variable_accesses (void)
2587 bitmap tmp
= BITMAP_ALLOC (NULL
);
2590 bool optimize_speed_p
= !optimize_function_for_size_p (cfun
);
2592 enum compiler_param param
= optimize_speed_p
2593 ? PARAM_SRA_MAX_SCALARIZATION_SIZE_SPEED
2594 : PARAM_SRA_MAX_SCALARIZATION_SIZE_SIZE
;
2596 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
2597 fall back to a target default. */
2598 unsigned HOST_WIDE_INT max_scalarization_size
2599 = global_options_set
.x_param_values
[param
]
2600 ? PARAM_VALUE (param
)
2601 : get_move_ratio (optimize_speed_p
) * UNITS_PER_WORD
;
2603 max_scalarization_size
*= BITS_PER_UNIT
;
2605 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap
, 0, i
, bi
)
2606 if (bitmap_bit_p (should_scalarize_away_bitmap
, i
)
2607 && !bitmap_bit_p (cannot_scalarize_away_bitmap
, i
))
2609 tree var
= candidate (i
);
2611 if (TREE_CODE (var
) == VAR_DECL
2612 && scalarizable_type_p (TREE_TYPE (var
)))
2614 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var
)))
2615 <= max_scalarization_size
)
2617 create_total_scalarization_access (var
);
2618 completely_scalarize (var
, TREE_TYPE (var
), 0, var
);
2619 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, "Will attempt to totally scalarize ");
2622 print_generic_expr (dump_file
, var
, 0);
2623 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
2626 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2628 fprintf (dump_file
, "Too big to totally scalarize: ");
2629 print_generic_expr (dump_file
, var
, 0);
2630 fprintf (dump_file
, " (UID: %u)\n", DECL_UID (var
));
2635 bitmap_copy (tmp
, candidate_bitmap
);
2636 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2638 tree var
= candidate (i
);
2639 struct access
*access
;
2641 access
= sort_and_splice_var_accesses (var
);
2642 if (!access
|| !build_access_trees (access
))
2643 disqualify_candidate (var
,
2644 "No or inhibitingly overlapping accesses.");
2647 propagate_all_subaccesses ();
2649 bitmap_copy (tmp
, candidate_bitmap
);
2650 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2652 tree var
= candidate (i
);
2653 struct access
*access
= get_first_repr_for_decl (var
);
2655 if (analyze_access_trees (access
))
2658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2660 fprintf (dump_file
, "\nAccess trees for ");
2661 print_generic_expr (dump_file
, var
, 0);
2662 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (var
));
2663 dump_access_tree (dump_file
, access
);
2664 fprintf (dump_file
, "\n");
2668 disqualify_candidate (var
, "No scalar replacements to be created.");
2675 statistics_counter_event (cfun
, "Scalarized aggregates", res
);
2682 /* Generate statements copying scalar replacements of accesses within a subtree
2683 into or out of AGG. ACCESS, all its children, siblings and their children
2684 are to be processed. AGG is an aggregate type expression (can be a
2685 declaration but does not have to be, it can for example also be a mem_ref or
2686 a series of handled components). TOP_OFFSET is the offset of the processed
2687 subtree which has to be subtracted from offsets of individual accesses to
2688 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
2689 replacements in the interval <start_offset, start_offset + chunk_size>,
2690 otherwise copy all. GSI is a statement iterator used to place the new
2691 statements. WRITE should be true when the statements should write from AGG
2692 to the replacement and false if vice versa. if INSERT_AFTER is true, new
2693 statements will be added after the current statement in GSI, they will be
2694 added before the statement otherwise. */
2697 generate_subtree_copies (struct access
*access
, tree agg
,
2698 HOST_WIDE_INT top_offset
,
2699 HOST_WIDE_INT start_offset
, HOST_WIDE_INT chunk_size
,
2700 gimple_stmt_iterator
*gsi
, bool write
,
2701 bool insert_after
, location_t loc
)
2705 if (chunk_size
&& access
->offset
>= start_offset
+ chunk_size
)
2708 if (access
->grp_to_be_replaced
2710 || access
->offset
+ access
->size
> start_offset
))
2712 tree expr
, repl
= get_access_replacement (access
);
2715 expr
= build_ref_for_model (loc
, agg
, access
->offset
- top_offset
,
2716 access
, gsi
, insert_after
);
2720 if (access
->grp_partial_lhs
)
2721 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL_TREE
,
2723 insert_after
? GSI_NEW_STMT
2725 stmt
= gimple_build_assign (repl
, expr
);
2729 TREE_NO_WARNING (repl
) = 1;
2730 if (access
->grp_partial_lhs
)
2731 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2733 insert_after
? GSI_NEW_STMT
2735 stmt
= gimple_build_assign (expr
, repl
);
2737 gimple_set_location (stmt
, loc
);
2740 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2742 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2744 sra_stats
.subtree_copies
++;
2747 && access
->grp_to_be_debug_replaced
2749 || access
->offset
+ access
->size
> start_offset
))
2752 tree drhs
= build_debug_ref_for_model (loc
, agg
,
2753 access
->offset
- top_offset
,
2755 ds
= gimple_build_debug_bind (get_access_replacement (access
),
2756 drhs
, gsi_stmt (*gsi
));
2758 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
2760 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
2763 if (access
->first_child
)
2764 generate_subtree_copies (access
->first_child
, agg
, top_offset
,
2765 start_offset
, chunk_size
, gsi
,
2766 write
, insert_after
, loc
);
2768 access
= access
->next_sibling
;
2773 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
2774 the root of the subtree to be processed. GSI is the statement iterator used
2775 for inserting statements which are added after the current statement if
2776 INSERT_AFTER is true or before it otherwise. */
2779 init_subtree_with_zero (struct access
*access
, gimple_stmt_iterator
*gsi
,
2780 bool insert_after
, location_t loc
)
2783 struct access
*child
;
2785 if (access
->grp_to_be_replaced
)
2789 stmt
= gimple_build_assign (get_access_replacement (access
),
2790 build_zero_cst (access
->type
));
2792 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2794 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2796 gimple_set_location (stmt
, loc
);
2798 else if (access
->grp_to_be_debug_replaced
)
2801 = gimple_build_debug_bind (get_access_replacement (access
),
2802 build_zero_cst (access
->type
),
2805 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
2807 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
2810 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2811 init_subtree_with_zero (child
, gsi
, insert_after
, loc
);
2814 /* Clobber all scalar replacements in an access subtree. ACCESS is the the
2815 root of the subtree to be processed. GSI is the statement iterator used
2816 for inserting statements which are added after the current statement if
2817 INSERT_AFTER is true or before it otherwise. */
2820 clobber_subtree (struct access
*access
, gimple_stmt_iterator
*gsi
,
2821 bool insert_after
, location_t loc
)
2824 struct access
*child
;
2826 if (access
->grp_to_be_replaced
)
2828 tree rep
= get_access_replacement (access
);
2829 tree clobber
= build_constructor (access
->type
, NULL
);
2830 TREE_THIS_VOLATILE (clobber
) = 1;
2831 gimple
*stmt
= gimple_build_assign (rep
, clobber
);
2834 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2836 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2838 gimple_set_location (stmt
, loc
);
2841 for (child
= access
->first_child
; child
; child
= child
->next_sibling
)
2842 clobber_subtree (child
, gsi
, insert_after
, loc
);
2845 /* Search for an access representative for the given expression EXPR and
2846 return it or NULL if it cannot be found. */
2848 static struct access
*
2849 get_access_for_expr (tree expr
)
2851 HOST_WIDE_INT offset
, size
, max_size
;
2855 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2856 a different size than the size of its argument and we need the latter
2858 if (TREE_CODE (expr
) == VIEW_CONVERT_EXPR
)
2859 expr
= TREE_OPERAND (expr
, 0);
2861 base
= get_ref_base_and_extent (expr
, &offset
, &size
, &max_size
, &reverse
);
2862 if (max_size
== -1 || !DECL_P (base
))
2865 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (base
)))
2868 return get_var_base_offset_size_access (base
, offset
, max_size
);
2871 /* Replace the expression EXPR with a scalar replacement if there is one and
2872 generate other statements to do type conversion or subtree copying if
2873 necessary. GSI is used to place newly created statements, WRITE is true if
2874 the expression is being written to (it is on a LHS of a statement or output
2875 in an assembly statement). */
2878 sra_modify_expr (tree
*expr
, gimple_stmt_iterator
*gsi
, bool write
)
2881 struct access
*access
;
2882 tree type
, bfr
, orig_expr
;
2884 if (TREE_CODE (*expr
) == BIT_FIELD_REF
)
2887 expr
= &TREE_OPERAND (*expr
, 0);
2892 if (TREE_CODE (*expr
) == REALPART_EXPR
|| TREE_CODE (*expr
) == IMAGPART_EXPR
)
2893 expr
= &TREE_OPERAND (*expr
, 0);
2894 access
= get_access_for_expr (*expr
);
2897 type
= TREE_TYPE (*expr
);
2900 loc
= gimple_location (gsi_stmt (*gsi
));
2901 gimple_stmt_iterator alt_gsi
= gsi_none ();
2902 if (write
&& stmt_ends_bb_p (gsi_stmt (*gsi
)))
2904 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
2908 if (access
->grp_to_be_replaced
)
2910 tree repl
= get_access_replacement (access
);
2911 /* If we replace a non-register typed access simply use the original
2912 access expression to extract the scalar component afterwards.
2913 This happens if scalarizing a function return value or parameter
2914 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2915 gcc.c-torture/compile/20011217-1.c.
2917 We also want to use this when accessing a complex or vector which can
2918 be accessed as a different type too, potentially creating a need for
2919 type conversion (see PR42196) and when scalarized unions are involved
2920 in assembler statements (see PR42398). */
2921 if (!useless_type_conversion_p (type
, access
->type
))
2925 ref
= build_ref_for_model (loc
, orig_expr
, 0, access
, gsi
, false);
2931 if (access
->grp_partial_lhs
)
2932 ref
= force_gimple_operand_gsi (gsi
, ref
, true, NULL_TREE
,
2933 false, GSI_NEW_STMT
);
2934 stmt
= gimple_build_assign (repl
, ref
);
2935 gimple_set_location (stmt
, loc
);
2936 gsi_insert_after (gsi
, stmt
, GSI_NEW_STMT
);
2942 if (access
->grp_partial_lhs
)
2943 repl
= force_gimple_operand_gsi (gsi
, repl
, true, NULL_TREE
,
2944 true, GSI_SAME_STMT
);
2945 stmt
= gimple_build_assign (ref
, repl
);
2946 gimple_set_location (stmt
, loc
);
2947 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
2954 else if (write
&& access
->grp_to_be_debug_replaced
)
2956 gdebug
*ds
= gimple_build_debug_bind (get_access_replacement (access
),
2959 gsi_insert_after (gsi
, ds
, GSI_NEW_STMT
);
2962 if (access
->first_child
)
2964 HOST_WIDE_INT start_offset
, chunk_size
;
2966 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 1))
2967 && tree_fits_uhwi_p (TREE_OPERAND (bfr
, 2)))
2969 chunk_size
= tree_to_uhwi (TREE_OPERAND (bfr
, 1));
2970 start_offset
= access
->offset
2971 + tree_to_uhwi (TREE_OPERAND (bfr
, 2));
2974 start_offset
= chunk_size
= 0;
2976 generate_subtree_copies (access
->first_child
, orig_expr
, access
->offset
,
2977 start_offset
, chunk_size
, gsi
, write
, write
,
2983 /* Where scalar replacements of the RHS have been written to when a replacement
2984 of a LHS of an assigments cannot be direclty loaded from a replacement of
2986 enum unscalarized_data_handling
{ SRA_UDH_NONE
, /* Nothing done so far. */
2987 SRA_UDH_RIGHT
, /* Data flushed to the RHS. */
2988 SRA_UDH_LEFT
}; /* Data flushed to the LHS. */
2990 struct subreplacement_assignment_data
2992 /* Offset of the access representing the lhs of the assignment. */
2993 HOST_WIDE_INT left_offset
;
2995 /* LHS and RHS of the original assignment. */
2996 tree assignment_lhs
, assignment_rhs
;
2998 /* Access representing the rhs of the whole assignment. */
2999 struct access
*top_racc
;
3001 /* Stmt iterator used for statement insertions after the original assignment.
3002 It points to the main GSI used to traverse a BB during function body
3004 gimple_stmt_iterator
*new_gsi
;
3006 /* Stmt iterator used for statement insertions before the original
3007 assignment. Keeps on pointing to the original statement. */
3008 gimple_stmt_iterator old_gsi
;
3010 /* Location of the assignment. */
3013 /* Keeps the information whether we have needed to refresh replacements of
3014 the LHS and from which side of the assignments this takes place. */
3015 enum unscalarized_data_handling refreshed
;
3018 /* Store all replacements in the access tree rooted in TOP_RACC either to their
3019 base aggregate if there are unscalarized data or directly to LHS of the
3020 statement that is pointed to by GSI otherwise. */
3023 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data
*sad
)
3026 if (sad
->top_racc
->grp_unscalarized_data
)
3028 src
= sad
->assignment_rhs
;
3029 sad
->refreshed
= SRA_UDH_RIGHT
;
3033 src
= sad
->assignment_lhs
;
3034 sad
->refreshed
= SRA_UDH_LEFT
;
3036 generate_subtree_copies (sad
->top_racc
->first_child
, src
,
3037 sad
->top_racc
->offset
, 0, 0,
3038 &sad
->old_gsi
, false, false, sad
->loc
);
3041 /* Try to generate statements to load all sub-replacements in an access subtree
3042 formed by children of LACC from scalar replacements in the SAD->top_racc
3043 subtree. If that is not possible, refresh the SAD->top_racc base aggregate
3044 and load the accesses from it. */
3047 load_assign_lhs_subreplacements (struct access
*lacc
,
3048 struct subreplacement_assignment_data
*sad
)
3050 for (lacc
= lacc
->first_child
; lacc
; lacc
= lacc
->next_sibling
)
3052 HOST_WIDE_INT offset
;
3053 offset
= lacc
->offset
- sad
->left_offset
+ sad
->top_racc
->offset
;
3055 if (lacc
->grp_to_be_replaced
)
3057 struct access
*racc
;
3061 racc
= find_access_in_subtree (sad
->top_racc
, offset
, lacc
->size
);
3062 if (racc
&& racc
->grp_to_be_replaced
)
3064 rhs
= get_access_replacement (racc
);
3065 if (!useless_type_conversion_p (lacc
->type
, racc
->type
))
3066 rhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3069 if (racc
->grp_partial_lhs
&& lacc
->grp_partial_lhs
)
3070 rhs
= force_gimple_operand_gsi (&sad
->old_gsi
, rhs
, true,
3071 NULL_TREE
, true, GSI_SAME_STMT
);
3075 /* No suitable access on the right hand side, need to load from
3076 the aggregate. See if we have to update it first... */
3077 if (sad
->refreshed
== SRA_UDH_NONE
)
3078 handle_unscalarized_data_in_subtree (sad
);
3080 if (sad
->refreshed
== SRA_UDH_LEFT
)
3081 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_lhs
,
3082 lacc
->offset
- sad
->left_offset
,
3083 lacc
, sad
->new_gsi
, true);
3085 rhs
= build_ref_for_model (sad
->loc
, sad
->assignment_rhs
,
3086 lacc
->offset
- sad
->left_offset
,
3087 lacc
, sad
->new_gsi
, true);
3088 if (lacc
->grp_partial_lhs
)
3089 rhs
= force_gimple_operand_gsi (sad
->new_gsi
,
3090 rhs
, true, NULL_TREE
,
3091 false, GSI_NEW_STMT
);
3094 stmt
= gimple_build_assign (get_access_replacement (lacc
), rhs
);
3095 gsi_insert_after (sad
->new_gsi
, stmt
, GSI_NEW_STMT
);
3096 gimple_set_location (stmt
, sad
->loc
);
3098 sra_stats
.subreplacements
++;
3102 if (sad
->refreshed
== SRA_UDH_NONE
3103 && lacc
->grp_read
&& !lacc
->grp_covered
)
3104 handle_unscalarized_data_in_subtree (sad
);
3106 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
3110 struct access
*racc
= find_access_in_subtree (sad
->top_racc
,
3114 if (racc
&& racc
->grp_to_be_replaced
)
3116 if (racc
->grp_write
)
3117 drhs
= get_access_replacement (racc
);
3121 else if (sad
->refreshed
== SRA_UDH_LEFT
)
3122 drhs
= build_debug_ref_for_model (sad
->loc
, lacc
->base
,
3123 lacc
->offset
, lacc
);
3124 else if (sad
->refreshed
== SRA_UDH_RIGHT
)
3125 drhs
= build_debug_ref_for_model (sad
->loc
, sad
->top_racc
->base
,
3130 && !useless_type_conversion_p (lacc
->type
, TREE_TYPE (drhs
)))
3131 drhs
= fold_build1_loc (sad
->loc
, VIEW_CONVERT_EXPR
,
3133 ds
= gimple_build_debug_bind (get_access_replacement (lacc
),
3134 drhs
, gsi_stmt (sad
->old_gsi
));
3135 gsi_insert_after (sad
->new_gsi
, ds
, GSI_NEW_STMT
);
3139 if (lacc
->first_child
)
3140 load_assign_lhs_subreplacements (lacc
, sad
);
3144 /* Result code for SRA assignment modification. */
3145 enum assignment_mod_result
{ SRA_AM_NONE
, /* nothing done for the stmt */
3146 SRA_AM_MODIFIED
, /* stmt changed but not
3148 SRA_AM_REMOVED
}; /* stmt eliminated */
3150 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
3151 to the assignment and GSI is the statement iterator pointing at it. Returns
3152 the same values as sra_modify_assign. */
3154 static enum assignment_mod_result
3155 sra_modify_constructor_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
3157 tree lhs
= gimple_assign_lhs (stmt
);
3158 struct access
*acc
= get_access_for_expr (lhs
);
3161 location_t loc
= gimple_location (stmt
);
3163 if (gimple_clobber_p (stmt
))
3165 /* Clobber the replacement variable. */
3166 clobber_subtree (acc
, gsi
, !acc
->grp_covered
, loc
);
3167 /* Remove clobbers of fully scalarized variables, they are dead. */
3168 if (acc
->grp_covered
)
3170 unlink_stmt_vdef (stmt
);
3171 gsi_remove (gsi
, true);
3172 release_defs (stmt
);
3173 return SRA_AM_REMOVED
;
3176 return SRA_AM_MODIFIED
;
3179 if (vec_safe_length (CONSTRUCTOR_ELTS (gimple_assign_rhs1 (stmt
))) > 0)
3181 /* I have never seen this code path trigger but if it can happen the
3182 following should handle it gracefully. */
3183 if (access_has_children_p (acc
))
3184 generate_subtree_copies (acc
->first_child
, lhs
, acc
->offset
, 0, 0, gsi
,
3186 return SRA_AM_MODIFIED
;
3189 if (acc
->grp_covered
)
3191 init_subtree_with_zero (acc
, gsi
, false, loc
);
3192 unlink_stmt_vdef (stmt
);
3193 gsi_remove (gsi
, true);
3194 release_defs (stmt
);
3195 return SRA_AM_REMOVED
;
3199 init_subtree_with_zero (acc
, gsi
, true, loc
);
3200 return SRA_AM_MODIFIED
;
3204 /* Create and return a new suitable default definition SSA_NAME for RACC which
3205 is an access describing an uninitialized part of an aggregate that is being
3209 get_repl_default_def_ssa_name (struct access
*racc
)
3211 gcc_checking_assert (!racc
->grp_to_be_replaced
3212 && !racc
->grp_to_be_debug_replaced
);
3213 if (!racc
->replacement_decl
)
3214 racc
->replacement_decl
= create_access_replacement (racc
);
3215 return get_or_create_ssa_default_def (cfun
, racc
->replacement_decl
);
3218 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
3219 bit-field field declaration somewhere in it. */
3222 contains_vce_or_bfcref_p (const_tree ref
)
3224 while (handled_component_p (ref
))
3226 if (TREE_CODE (ref
) == VIEW_CONVERT_EXPR
3227 || (TREE_CODE (ref
) == COMPONENT_REF
3228 && DECL_BIT_FIELD (TREE_OPERAND (ref
, 1))))
3230 ref
= TREE_OPERAND (ref
, 0);
3236 /* Examine both sides of the assignment statement pointed to by STMT, replace
3237 them with a scalare replacement if there is one and generate copying of
3238 replacements if scalarized aggregates have been used in the assignment. GSI
3239 is used to hold generated statements for type conversions and subtree
3242 static enum assignment_mod_result
3243 sra_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
)
3245 struct access
*lacc
, *racc
;
3247 bool modify_this_stmt
= false;
3248 bool force_gimple_rhs
= false;
3250 gimple_stmt_iterator orig_gsi
= *gsi
;
3252 if (!gimple_assign_single_p (stmt
))
3254 lhs
= gimple_assign_lhs (stmt
);
3255 rhs
= gimple_assign_rhs1 (stmt
);
3257 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
3258 return sra_modify_constructor_assign (stmt
, gsi
);
3260 if (TREE_CODE (rhs
) == REALPART_EXPR
|| TREE_CODE (lhs
) == REALPART_EXPR
3261 || TREE_CODE (rhs
) == IMAGPART_EXPR
|| TREE_CODE (lhs
) == IMAGPART_EXPR
3262 || TREE_CODE (rhs
) == BIT_FIELD_REF
|| TREE_CODE (lhs
) == BIT_FIELD_REF
)
3264 modify_this_stmt
= sra_modify_expr (gimple_assign_rhs1_ptr (stmt
),
3266 modify_this_stmt
|= sra_modify_expr (gimple_assign_lhs_ptr (stmt
),
3268 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
3271 lacc
= get_access_for_expr (lhs
);
3272 racc
= get_access_for_expr (rhs
);
3276 loc
= gimple_location (stmt
);
3277 if (lacc
&& lacc
->grp_to_be_replaced
)
3279 lhs
= get_access_replacement (lacc
);
3280 gimple_assign_set_lhs (stmt
, lhs
);
3281 modify_this_stmt
= true;
3282 if (lacc
->grp_partial_lhs
)
3283 force_gimple_rhs
= true;
3287 if (racc
&& racc
->grp_to_be_replaced
)
3289 rhs
= get_access_replacement (racc
);
3290 modify_this_stmt
= true;
3291 if (racc
->grp_partial_lhs
)
3292 force_gimple_rhs
= true;
3296 && !racc
->grp_unscalarized_data
3297 && TREE_CODE (lhs
) == SSA_NAME
3298 && !access_has_replacements_p (racc
))
3300 rhs
= get_repl_default_def_ssa_name (racc
);
3301 modify_this_stmt
= true;
3305 if (modify_this_stmt
)
3307 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3309 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
3310 ??? This should move to fold_stmt which we simply should
3311 call after building a VIEW_CONVERT_EXPR here. */
3312 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs
))
3313 && !contains_bitfld_component_ref_p (lhs
))
3315 lhs
= build_ref_for_model (loc
, lhs
, 0, racc
, gsi
, false);
3316 gimple_assign_set_lhs (stmt
, lhs
);
3318 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs
))
3319 && !contains_vce_or_bfcref_p (rhs
))
3320 rhs
= build_ref_for_model (loc
, rhs
, 0, lacc
, gsi
, false);
3322 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3324 rhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
, TREE_TYPE (lhs
),
3326 if (is_gimple_reg_type (TREE_TYPE (lhs
))
3327 && TREE_CODE (lhs
) != SSA_NAME
)
3328 force_gimple_rhs
= true;
3333 if (lacc
&& lacc
->grp_to_be_debug_replaced
)
3335 tree dlhs
= get_access_replacement (lacc
);
3336 tree drhs
= unshare_expr (rhs
);
3337 if (!useless_type_conversion_p (TREE_TYPE (dlhs
), TREE_TYPE (drhs
)))
3339 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs
))
3340 && !contains_vce_or_bfcref_p (drhs
))
3341 drhs
= build_debug_ref_for_model (loc
, drhs
, 0, lacc
);
3343 && !useless_type_conversion_p (TREE_TYPE (dlhs
),
3345 drhs
= fold_build1_loc (loc
, VIEW_CONVERT_EXPR
,
3346 TREE_TYPE (dlhs
), drhs
);
3348 gdebug
*ds
= gimple_build_debug_bind (dlhs
, drhs
, stmt
);
3349 gsi_insert_before (gsi
, ds
, GSI_SAME_STMT
);
3352 /* From this point on, the function deals with assignments in between
3353 aggregates when at least one has scalar reductions of some of its
3354 components. There are three possible scenarios: Both the LHS and RHS have
3355 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
3357 In the first case, we would like to load the LHS components from RHS
3358 components whenever possible. If that is not possible, we would like to
3359 read it directly from the RHS (after updating it by storing in it its own
3360 components). If there are some necessary unscalarized data in the LHS,
3361 those will be loaded by the original assignment too. If neither of these
3362 cases happen, the original statement can be removed. Most of this is done
3363 by load_assign_lhs_subreplacements.
3365 In the second case, we would like to store all RHS scalarized components
3366 directly into LHS and if they cover the aggregate completely, remove the
3367 statement too. In the third case, we want the LHS components to be loaded
3368 directly from the RHS (DSE will remove the original statement if it
3371 This is a bit complex but manageable when types match and when unions do
3372 not cause confusion in a way that we cannot really load a component of LHS
3373 from the RHS or vice versa (the access representing this level can have
3374 subaccesses that are accessible only through a different union field at a
3375 higher level - different from the one used in the examined expression).
3378 Therefore, I specially handle a fourth case, happening when there is a
3379 specific type cast or it is impossible to locate a scalarized subaccess on
3380 the other side of the expression. If that happens, I simply "refresh" the
3381 RHS by storing in it is scalarized components leave the original statement
3382 there to do the copying and then load the scalar replacements of the LHS.
3383 This is what the first branch does. */
3385 if (modify_this_stmt
3386 || gimple_has_volatile_ops (stmt
)
3387 || contains_vce_or_bfcref_p (rhs
)
3388 || contains_vce_or_bfcref_p (lhs
)
3389 || stmt_ends_bb_p (stmt
))
3391 if (access_has_children_p (racc
))
3392 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
3393 gsi
, false, false, loc
);
3394 if (access_has_children_p (lacc
))
3396 gimple_stmt_iterator alt_gsi
= gsi_none ();
3397 if (stmt_ends_bb_p (stmt
))
3399 alt_gsi
= gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi
)));
3402 generate_subtree_copies (lacc
->first_child
, lhs
, lacc
->offset
, 0, 0,
3403 gsi
, true, true, loc
);
3405 sra_stats
.separate_lhs_rhs_handling
++;
3407 /* This gimplification must be done after generate_subtree_copies,
3408 lest we insert the subtree copies in the middle of the gimplified
3410 if (force_gimple_rhs
)
3411 rhs
= force_gimple_operand_gsi (&orig_gsi
, rhs
, true, NULL_TREE
,
3412 true, GSI_SAME_STMT
);
3413 if (gimple_assign_rhs1 (stmt
) != rhs
)
3415 modify_this_stmt
= true;
3416 gimple_assign_set_rhs_from_tree (&orig_gsi
, rhs
);
3417 gcc_assert (stmt
== gsi_stmt (orig_gsi
));
3420 return modify_this_stmt
? SRA_AM_MODIFIED
: SRA_AM_NONE
;
3424 if (access_has_children_p (lacc
)
3425 && access_has_children_p (racc
)
3426 /* When an access represents an unscalarizable region, it usually
3427 represents accesses with variable offset and thus must not be used
3428 to generate new memory accesses. */
3429 && !lacc
->grp_unscalarizable_region
3430 && !racc
->grp_unscalarizable_region
)
3432 struct subreplacement_assignment_data sad
;
3434 sad
.left_offset
= lacc
->offset
;
3435 sad
.assignment_lhs
= lhs
;
3436 sad
.assignment_rhs
= rhs
;
3437 sad
.top_racc
= racc
;
3440 sad
.loc
= gimple_location (stmt
);
3441 sad
.refreshed
= SRA_UDH_NONE
;
3443 if (lacc
->grp_read
&& !lacc
->grp_covered
)
3444 handle_unscalarized_data_in_subtree (&sad
);
3446 load_assign_lhs_subreplacements (lacc
, &sad
);
3447 if (sad
.refreshed
!= SRA_UDH_RIGHT
)
3450 unlink_stmt_vdef (stmt
);
3451 gsi_remove (&sad
.old_gsi
, true);
3452 release_defs (stmt
);
3453 sra_stats
.deleted
++;
3454 return SRA_AM_REMOVED
;
3459 if (access_has_children_p (racc
)
3460 && !racc
->grp_unscalarized_data
)
3464 fprintf (dump_file
, "Removing load: ");
3465 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3467 generate_subtree_copies (racc
->first_child
, lhs
,
3468 racc
->offset
, 0, 0, gsi
,
3470 gcc_assert (stmt
== gsi_stmt (*gsi
));
3471 unlink_stmt_vdef (stmt
);
3472 gsi_remove (gsi
, true);
3473 release_defs (stmt
);
3474 sra_stats
.deleted
++;
3475 return SRA_AM_REMOVED
;
3477 /* Restore the aggregate RHS from its components so the
3478 prevailing aggregate copy does the right thing. */
3479 if (access_has_children_p (racc
))
3480 generate_subtree_copies (racc
->first_child
, rhs
, racc
->offset
, 0, 0,
3481 gsi
, false, false, loc
);
3482 /* Re-load the components of the aggregate copy destination.
3483 But use the RHS aggregate to load from to expose more
3484 optimization opportunities. */
3485 if (access_has_children_p (lacc
))
3486 generate_subtree_copies (lacc
->first_child
, rhs
, lacc
->offset
,
3487 0, 0, gsi
, true, true, loc
);
3494 /* Traverse the function body and all modifications as decided in
3495 analyze_all_variable_accesses. Return true iff the CFG has been
3499 sra_modify_function_body (void)
3501 bool cfg_changed
= false;
3504 FOR_EACH_BB_FN (bb
, cfun
)
3506 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3507 while (!gsi_end_p (gsi
))
3509 gimple
*stmt
= gsi_stmt (gsi
);
3510 enum assignment_mod_result assign_result
;
3511 bool modified
= false, deleted
= false;
3515 switch (gimple_code (stmt
))
3518 t
= gimple_return_retval_ptr (as_a
<greturn
*> (stmt
));
3519 if (*t
!= NULL_TREE
)
3520 modified
|= sra_modify_expr (t
, &gsi
, false);
3524 assign_result
= sra_modify_assign (stmt
, &gsi
);
3525 modified
|= assign_result
== SRA_AM_MODIFIED
;
3526 deleted
= assign_result
== SRA_AM_REMOVED
;
3530 /* Operands must be processed before the lhs. */
3531 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
3533 t
= gimple_call_arg_ptr (stmt
, i
);
3534 modified
|= sra_modify_expr (t
, &gsi
, false);
3537 if (gimple_call_lhs (stmt
))
3539 t
= gimple_call_lhs_ptr (stmt
);
3540 modified
|= sra_modify_expr (t
, &gsi
, true);
3546 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
3547 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
3549 t
= &TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
3550 modified
|= sra_modify_expr (t
, &gsi
, false);
3552 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
3554 t
= &TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
3555 modified
|= sra_modify_expr (t
, &gsi
, true);
3567 if (maybe_clean_eh_stmt (stmt
)
3568 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
3576 gsi_commit_edge_inserts ();
3580 /* Generate statements initializing scalar replacements of parts of function
3584 initialize_parameter_reductions (void)
3586 gimple_stmt_iterator gsi
;
3587 gimple_seq seq
= NULL
;
3590 gsi
= gsi_start (seq
);
3591 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3593 parm
= DECL_CHAIN (parm
))
3595 vec
<access_p
> *access_vec
;
3596 struct access
*access
;
3598 if (!bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
3600 access_vec
= get_base_access_vector (parm
);
3604 for (access
= (*access_vec
)[0];
3606 access
= access
->next_grp
)
3607 generate_subtree_copies (access
, parm
, 0, 0, 0, &gsi
, true, true,
3608 EXPR_LOCATION (parm
));
3611 seq
= gsi_seq (gsi
);
3613 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), seq
);
3616 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
3617 it reveals there are components of some aggregates to be scalarized, it runs
3618 the required transformations. */
3620 perform_intra_sra (void)
3625 if (!find_var_candidates ())
3628 if (!scan_function ())
3631 if (!analyze_all_variable_accesses ())
3634 if (sra_modify_function_body ())
3635 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
3637 ret
= TODO_update_ssa
;
3638 initialize_parameter_reductions ();
3640 statistics_counter_event (cfun
, "Scalar replacements created",
3641 sra_stats
.replacements
);
3642 statistics_counter_event (cfun
, "Modified expressions", sra_stats
.exprs
);
3643 statistics_counter_event (cfun
, "Subtree copy stmts",
3644 sra_stats
.subtree_copies
);
3645 statistics_counter_event (cfun
, "Subreplacement stmts",
3646 sra_stats
.subreplacements
);
3647 statistics_counter_event (cfun
, "Deleted stmts", sra_stats
.deleted
);
3648 statistics_counter_event (cfun
, "Separate LHS and RHS handling",
3649 sra_stats
.separate_lhs_rhs_handling
);
3652 sra_deinitialize ();
3656 /* Perform early intraprocedural SRA. */
3658 early_intra_sra (void)
3660 sra_mode
= SRA_MODE_EARLY_INTRA
;
3661 return perform_intra_sra ();
3664 /* Perform "late" intraprocedural SRA. */
3666 late_intra_sra (void)
3668 sra_mode
= SRA_MODE_INTRA
;
3669 return perform_intra_sra ();
3674 gate_intra_sra (void)
3676 return flag_tree_sra
!= 0 && dbg_cnt (tree_sra
);
3682 const pass_data pass_data_sra_early
=
3684 GIMPLE_PASS
, /* type */
3686 OPTGROUP_NONE
, /* optinfo_flags */
3687 TV_TREE_SRA
, /* tv_id */
3688 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3689 0, /* properties_provided */
3690 0, /* properties_destroyed */
3691 0, /* todo_flags_start */
3692 TODO_update_ssa
, /* todo_flags_finish */
3695 class pass_sra_early
: public gimple_opt_pass
3698 pass_sra_early (gcc::context
*ctxt
)
3699 : gimple_opt_pass (pass_data_sra_early
, ctxt
)
3702 /* opt_pass methods: */
3703 virtual bool gate (function
*) { return gate_intra_sra (); }
3704 virtual unsigned int execute (function
*) { return early_intra_sra (); }
3706 }; // class pass_sra_early
3711 make_pass_sra_early (gcc::context
*ctxt
)
3713 return new pass_sra_early (ctxt
);
3718 const pass_data pass_data_sra
=
3720 GIMPLE_PASS
, /* type */
3722 OPTGROUP_NONE
, /* optinfo_flags */
3723 TV_TREE_SRA
, /* tv_id */
3724 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3725 0, /* properties_provided */
3726 0, /* properties_destroyed */
3727 TODO_update_address_taken
, /* todo_flags_start */
3728 TODO_update_ssa
, /* todo_flags_finish */
3731 class pass_sra
: public gimple_opt_pass
3734 pass_sra (gcc::context
*ctxt
)
3735 : gimple_opt_pass (pass_data_sra
, ctxt
)
3738 /* opt_pass methods: */
3739 virtual bool gate (function
*) { return gate_intra_sra (); }
3740 virtual unsigned int execute (function
*) { return late_intra_sra (); }
3742 }; // class pass_sra
3747 make_pass_sra (gcc::context
*ctxt
)
3749 return new pass_sra (ctxt
);
3753 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3757 is_unused_scalar_param (tree parm
)
3760 return (is_gimple_reg (parm
)
3761 && (!(name
= ssa_default_def (cfun
, parm
))
3762 || has_zero_uses (name
)));
3765 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3766 examine whether there are any direct or otherwise infeasible ones. If so,
3767 return true, otherwise return false. PARM must be a gimple register with a
3768 non-NULL default definition. */
3771 ptr_parm_has_direct_uses (tree parm
)
3773 imm_use_iterator ui
;
3775 tree name
= ssa_default_def (cfun
, parm
);
3778 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
3781 use_operand_p use_p
;
3783 if (is_gimple_debug (stmt
))
3786 /* Valid uses include dereferences on the lhs and the rhs. */
3787 if (gimple_has_lhs (stmt
))
3789 tree lhs
= gimple_get_lhs (stmt
);
3790 while (handled_component_p (lhs
))
3791 lhs
= TREE_OPERAND (lhs
, 0);
3792 if (TREE_CODE (lhs
) == MEM_REF
3793 && TREE_OPERAND (lhs
, 0) == name
3794 && integer_zerop (TREE_OPERAND (lhs
, 1))
3795 && types_compatible_p (TREE_TYPE (lhs
),
3796 TREE_TYPE (TREE_TYPE (name
)))
3797 && !TREE_THIS_VOLATILE (lhs
))
3800 if (gimple_assign_single_p (stmt
))
3802 tree rhs
= gimple_assign_rhs1 (stmt
);
3803 while (handled_component_p (rhs
))
3804 rhs
= TREE_OPERAND (rhs
, 0);
3805 if (TREE_CODE (rhs
) == MEM_REF
3806 && TREE_OPERAND (rhs
, 0) == name
3807 && integer_zerop (TREE_OPERAND (rhs
, 1))
3808 && types_compatible_p (TREE_TYPE (rhs
),
3809 TREE_TYPE (TREE_TYPE (name
)))
3810 && !TREE_THIS_VOLATILE (rhs
))
3813 else if (is_gimple_call (stmt
))
3816 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
3818 tree arg
= gimple_call_arg (stmt
, i
);
3819 while (handled_component_p (arg
))
3820 arg
= TREE_OPERAND (arg
, 0);
3821 if (TREE_CODE (arg
) == MEM_REF
3822 && TREE_OPERAND (arg
, 0) == name
3823 && integer_zerop (TREE_OPERAND (arg
, 1))
3824 && types_compatible_p (TREE_TYPE (arg
),
3825 TREE_TYPE (TREE_TYPE (name
)))
3826 && !TREE_THIS_VOLATILE (arg
))
3831 /* If the number of valid uses does not match the number of
3832 uses in this stmt there is an unhandled use. */
3833 FOR_EACH_IMM_USE_ON_STMT (use_p
, ui
)
3840 BREAK_FROM_IMM_USE_STMT (ui
);
3846 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3847 them in candidate_bitmap. Note that these do not necessarily include
3848 parameter which are unused and thus can be removed. Return true iff any
3849 such candidate has been found. */
3852 find_param_candidates (void)
3859 for (parm
= DECL_ARGUMENTS (current_function_decl
);
3861 parm
= DECL_CHAIN (parm
))
3863 tree type
= TREE_TYPE (parm
);
3868 if (TREE_THIS_VOLATILE (parm
)
3869 || TREE_ADDRESSABLE (parm
)
3870 || (!is_gimple_reg_type (type
) && is_va_list_type (type
)))
3873 if (is_unused_scalar_param (parm
))
3879 if (POINTER_TYPE_P (type
))
3881 type
= TREE_TYPE (type
);
3883 if (TREE_CODE (type
) == FUNCTION_TYPE
3884 || TYPE_VOLATILE (type
)
3885 || (TREE_CODE (type
) == ARRAY_TYPE
3886 && TYPE_NONALIASED_COMPONENT (type
))
3887 || !is_gimple_reg (parm
)
3888 || is_va_list_type (type
)
3889 || ptr_parm_has_direct_uses (parm
))
3892 else if (!AGGREGATE_TYPE_P (type
))
3895 if (!COMPLETE_TYPE_P (type
)
3896 || !tree_fits_uhwi_p (TYPE_SIZE (type
))
3897 || tree_to_uhwi (TYPE_SIZE (type
)) == 0
3898 || (AGGREGATE_TYPE_P (type
)
3899 && type_internals_preclude_sra_p (type
, &msg
)))
3902 bitmap_set_bit (candidate_bitmap
, DECL_UID (parm
));
3903 slot
= candidates
->find_slot_with_hash (parm
, DECL_UID (parm
), INSERT
);
3907 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3909 fprintf (dump_file
, "Candidate (%d): ", DECL_UID (parm
));
3910 print_generic_expr (dump_file
, parm
, 0);
3911 fprintf (dump_file
, "\n");
3915 func_param_count
= count
;
3919 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3923 mark_maybe_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
3926 struct access
*repr
= (struct access
*) data
;
3928 repr
->grp_maybe_modified
= 1;
3932 /* Analyze what representatives (in linked lists accessible from
3933 REPRESENTATIVES) can be modified by side effects of statements in the
3934 current function. */
3937 analyze_modified_params (vec
<access_p
> representatives
)
3941 for (i
= 0; i
< func_param_count
; i
++)
3943 struct access
*repr
;
3945 for (repr
= representatives
[i
];
3947 repr
= repr
->next_grp
)
3949 struct access
*access
;
3953 if (no_accesses_p (repr
))
3955 if (!POINTER_TYPE_P (TREE_TYPE (repr
->base
))
3956 || repr
->grp_maybe_modified
)
3959 ao_ref_init (&ar
, repr
->expr
);
3960 visited
= BITMAP_ALLOC (NULL
);
3961 for (access
= repr
; access
; access
= access
->next_sibling
)
3963 /* All accesses are read ones, otherwise grp_maybe_modified would
3964 be trivially set. */
3965 walk_aliased_vdefs (&ar
, gimple_vuse (access
->stmt
),
3966 mark_maybe_modified
, repr
, &visited
);
3967 if (repr
->grp_maybe_modified
)
3970 BITMAP_FREE (visited
);
3975 /* Propagate distances in bb_dereferences in the opposite direction than the
3976 control flow edges, in each step storing the maximum of the current value
3977 and the minimum of all successors. These steps are repeated until the table
3978 stabilizes. Note that BBs which might terminate the functions (according to
3979 final_bbs bitmap) never updated in this way. */
3982 propagate_dereference_distances (void)
3986 auto_vec
<basic_block
> queue (last_basic_block_for_fn (cfun
));
3987 queue
.quick_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3988 FOR_EACH_BB_FN (bb
, cfun
)
3990 queue
.quick_push (bb
);
3994 while (!queue
.is_empty ())
3998 bool change
= false;
4004 if (bitmap_bit_p (final_bbs
, bb
->index
))
4007 for (i
= 0; i
< func_param_count
; i
++)
4009 int idx
= bb
->index
* func_param_count
+ i
;
4011 HOST_WIDE_INT inh
= 0;
4013 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4015 int succ_idx
= e
->dest
->index
* func_param_count
+ i
;
4017 if (e
->src
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4023 inh
= bb_dereferences
[succ_idx
];
4025 else if (bb_dereferences
[succ_idx
] < inh
)
4026 inh
= bb_dereferences
[succ_idx
];
4029 if (!first
&& bb_dereferences
[idx
] < inh
)
4031 bb_dereferences
[idx
] = inh
;
4036 if (change
&& !bitmap_bit_p (final_bbs
, bb
->index
))
4037 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4042 e
->src
->aux
= e
->src
;
4043 queue
.quick_push (e
->src
);
4048 /* Dump a dereferences TABLE with heading STR to file F. */
4051 dump_dereferences_table (FILE *f
, const char *str
, HOST_WIDE_INT
*table
)
4055 fprintf (dump_file
, "%s", str
);
4056 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
4057 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
4059 fprintf (f
, "%4i %i ", bb
->index
, bitmap_bit_p (final_bbs
, bb
->index
));
4060 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4063 for (i
= 0; i
< func_param_count
; i
++)
4065 int idx
= bb
->index
* func_param_count
+ i
;
4066 fprintf (f
, " %4" HOST_WIDE_INT_PRINT
"d", table
[idx
]);
4071 fprintf (dump_file
, "\n");
4074 /* Determine what (parts of) parameters passed by reference that are not
4075 assigned to are not certainly dereferenced in this function and thus the
4076 dereferencing cannot be safely moved to the caller without potentially
4077 introducing a segfault. Mark such REPRESENTATIVES as
4078 grp_not_necessarilly_dereferenced.
4080 The dereferenced maximum "distance," i.e. the offset + size of the accessed
4081 part is calculated rather than simple booleans are calculated for each
4082 pointer parameter to handle cases when only a fraction of the whole
4083 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
4086 The maximum dereference distances for each pointer parameter and BB are
4087 already stored in bb_dereference. This routine simply propagates these
4088 values upwards by propagate_dereference_distances and then compares the
4089 distances of individual parameters in the ENTRY BB to the equivalent
4090 distances of each representative of a (fraction of a) parameter. */
4093 analyze_caller_dereference_legality (vec
<access_p
> representatives
)
4097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4098 dump_dereferences_table (dump_file
,
4099 "Dereference table before propagation:\n",
4102 propagate_dereference_distances ();
4104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4105 dump_dereferences_table (dump_file
,
4106 "Dereference table after propagation:\n",
4109 for (i
= 0; i
< func_param_count
; i
++)
4111 struct access
*repr
= representatives
[i
];
4112 int idx
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
* func_param_count
+ i
;
4114 if (!repr
|| no_accesses_p (repr
))
4119 if ((repr
->offset
+ repr
->size
) > bb_dereferences
[idx
])
4120 repr
->grp_not_necessarilly_dereferenced
= 1;
4121 repr
= repr
->next_grp
;
4127 /* Return the representative access for the parameter declaration PARM if it is
4128 a scalar passed by reference which is not written to and the pointer value
4129 is not used directly. Thus, if it is legal to dereference it in the caller
4130 and we can rule out modifications through aliases, such parameter should be
4131 turned into one passed by value. Return NULL otherwise. */
4133 static struct access
*
4134 unmodified_by_ref_scalar_representative (tree parm
)
4136 int i
, access_count
;
4137 struct access
*repr
;
4138 vec
<access_p
> *access_vec
;
4140 access_vec
= get_base_access_vector (parm
);
4141 gcc_assert (access_vec
);
4142 repr
= (*access_vec
)[0];
4145 repr
->group_representative
= repr
;
4147 access_count
= access_vec
->length ();
4148 for (i
= 1; i
< access_count
; i
++)
4150 struct access
*access
= (*access_vec
)[i
];
4153 access
->group_representative
= repr
;
4154 access
->next_sibling
= repr
->next_sibling
;
4155 repr
->next_sibling
= access
;
4159 repr
->grp_scalar_ptr
= 1;
4163 /* Return true iff this ACCESS precludes IPA-SRA of the parameter it is
4164 associated with. REQ_ALIGN is the minimum required alignment. */
4167 access_precludes_ipa_sra_p (struct access
*access
, unsigned int req_align
)
4169 unsigned int exp_align
;
4170 /* Avoid issues such as the second simple testcase in PR 42025. The problem
4171 is incompatible assign in a call statement (and possibly even in asm
4172 statements). This can be relaxed by using a new temporary but only for
4173 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
4174 intraprocedural SRA we deal with this by keeping the old aggregate around,
4175 something we cannot do in IPA-SRA.) */
4177 && (is_gimple_call (access
->stmt
)
4178 || gimple_code (access
->stmt
) == GIMPLE_ASM
))
4181 exp_align
= get_object_alignment (access
->expr
);
4182 if (exp_align
< req_align
)
4189 /* Sort collected accesses for parameter PARM, identify representatives for
4190 each accessed region and link them together. Return NULL if there are
4191 different but overlapping accesses, return the special ptr value meaning
4192 there are no accesses for this parameter if that is the case and return the
4193 first representative otherwise. Set *RO_GRP if there is a group of accesses
4194 with only read (i.e. no write) accesses. */
4196 static struct access
*
4197 splice_param_accesses (tree parm
, bool *ro_grp
)
4199 int i
, j
, access_count
, group_count
;
4200 int agg_size
, total_size
= 0;
4201 struct access
*access
, *res
, **prev_acc_ptr
= &res
;
4202 vec
<access_p
> *access_vec
;
4204 access_vec
= get_base_access_vector (parm
);
4206 return &no_accesses_representant
;
4207 access_count
= access_vec
->length ();
4209 access_vec
->qsort (compare_access_positions
);
4214 while (i
< access_count
)
4218 access
= (*access_vec
)[i
];
4219 modification
= access
->write
;
4220 if (access_precludes_ipa_sra_p (access
, TYPE_ALIGN (access
->type
)))
4222 a1_alias_type
= reference_alias_ptr_type (access
->expr
);
4224 /* Access is about to become group representative unless we find some
4225 nasty overlap which would preclude us from breaking this parameter
4229 while (j
< access_count
)
4231 struct access
*ac2
= (*access_vec
)[j
];
4232 if (ac2
->offset
!= access
->offset
)
4234 /* All or nothing law for parameters. */
4235 if (access
->offset
+ access
->size
> ac2
->offset
)
4240 else if (ac2
->size
!= access
->size
)
4243 if (access_precludes_ipa_sra_p (ac2
, TYPE_ALIGN (access
->type
))
4244 || (ac2
->type
!= access
->type
4245 && (TREE_ADDRESSABLE (ac2
->type
)
4246 || TREE_ADDRESSABLE (access
->type
)))
4247 || (reference_alias_ptr_type (ac2
->expr
) != a1_alias_type
))
4250 modification
|= ac2
->write
;
4251 ac2
->group_representative
= access
;
4252 ac2
->next_sibling
= access
->next_sibling
;
4253 access
->next_sibling
= ac2
;
4258 access
->grp_maybe_modified
= modification
;
4261 *prev_acc_ptr
= access
;
4262 prev_acc_ptr
= &access
->next_grp
;
4263 total_size
+= access
->size
;
4267 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
4268 agg_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))));
4270 agg_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm
)));
4271 if (total_size
>= agg_size
)
4274 gcc_assert (group_count
> 0);
4278 /* Decide whether parameters with representative accesses given by REPR should
4279 be reduced into components. */
4282 decide_one_param_reduction (struct access
*repr
)
4284 int total_size
, cur_parm_size
, agg_size
, new_param_count
, parm_size_limit
;
4289 cur_parm_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm
)));
4290 gcc_assert (cur_parm_size
> 0);
4292 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
4295 agg_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm
))));
4300 agg_size
= cur_parm_size
;
4306 fprintf (dump_file
, "Evaluating PARAM group sizes for ");
4307 print_generic_expr (dump_file
, parm
, 0);
4308 fprintf (dump_file
, " (UID: %u): \n", DECL_UID (parm
));
4309 for (acc
= repr
; acc
; acc
= acc
->next_grp
)
4310 dump_access (dump_file
, acc
, true);
4314 new_param_count
= 0;
4316 for (; repr
; repr
= repr
->next_grp
)
4318 gcc_assert (parm
== repr
->base
);
4320 /* Taking the address of a non-addressable field is verboten. */
4321 if (by_ref
&& repr
->non_addressable
)
4324 /* Do not decompose a non-BLKmode param in a way that would
4325 create BLKmode params. Especially for by-reference passing
4326 (thus, pointer-type param) this is hardly worthwhile. */
4327 if (DECL_MODE (parm
) != BLKmode
4328 && TYPE_MODE (repr
->type
) == BLKmode
)
4331 if (!by_ref
|| (!repr
->grp_maybe_modified
4332 && !repr
->grp_not_necessarilly_dereferenced
))
4333 total_size
+= repr
->size
;
4335 total_size
+= cur_parm_size
;
4340 gcc_assert (new_param_count
> 0);
4342 if (optimize_function_for_size_p (cfun
))
4343 parm_size_limit
= cur_parm_size
;
4345 parm_size_limit
= (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR
)
4348 if (total_size
< agg_size
4349 && total_size
<= parm_size_limit
)
4352 fprintf (dump_file
, " ....will be split into %i components\n",
4354 return new_param_count
;
4360 /* The order of the following enums is important, we need to do extra work for
4361 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
4362 enum ipa_splicing_result
{ NO_GOOD_ACCESS
, UNUSED_PARAMS
, BY_VAL_ACCESSES
,
4363 MODIF_BY_REF_ACCESSES
, UNMODIF_BY_REF_ACCESSES
};
4365 /* Identify representatives of all accesses to all candidate parameters for
4366 IPA-SRA. Return result based on what representatives have been found. */
4368 static enum ipa_splicing_result
4369 splice_all_param_accesses (vec
<access_p
> &representatives
)
4371 enum ipa_splicing_result result
= NO_GOOD_ACCESS
;
4373 struct access
*repr
;
4375 representatives
.create (func_param_count
);
4377 for (parm
= DECL_ARGUMENTS (current_function_decl
);
4379 parm
= DECL_CHAIN (parm
))
4381 if (is_unused_scalar_param (parm
))
4383 representatives
.quick_push (&no_accesses_representant
);
4384 if (result
== NO_GOOD_ACCESS
)
4385 result
= UNUSED_PARAMS
;
4387 else if (POINTER_TYPE_P (TREE_TYPE (parm
))
4388 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm
)))
4389 && bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
4391 repr
= unmodified_by_ref_scalar_representative (parm
);
4392 representatives
.quick_push (repr
);
4394 result
= UNMODIF_BY_REF_ACCESSES
;
4396 else if (bitmap_bit_p (candidate_bitmap
, DECL_UID (parm
)))
4398 bool ro_grp
= false;
4399 repr
= splice_param_accesses (parm
, &ro_grp
);
4400 representatives
.quick_push (repr
);
4402 if (repr
&& !no_accesses_p (repr
))
4404 if (POINTER_TYPE_P (TREE_TYPE (parm
)))
4407 result
= UNMODIF_BY_REF_ACCESSES
;
4408 else if (result
< MODIF_BY_REF_ACCESSES
)
4409 result
= MODIF_BY_REF_ACCESSES
;
4411 else if (result
< BY_VAL_ACCESSES
)
4412 result
= BY_VAL_ACCESSES
;
4414 else if (no_accesses_p (repr
) && (result
== NO_GOOD_ACCESS
))
4415 result
= UNUSED_PARAMS
;
4418 representatives
.quick_push (NULL
);
4421 if (result
== NO_GOOD_ACCESS
)
4423 representatives
.release ();
4424 return NO_GOOD_ACCESS
;
4430 /* Return the index of BASE in PARMS. Abort if it is not found. */
4433 get_param_index (tree base
, vec
<tree
> parms
)
4437 len
= parms
.length ();
4438 for (i
= 0; i
< len
; i
++)
4439 if (parms
[i
] == base
)
4444 /* Convert the decisions made at the representative level into compact
4445 parameter adjustments. REPRESENTATIVES are pointers to first
4446 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
4447 final number of adjustments. */
4449 static ipa_parm_adjustment_vec
4450 turn_representatives_into_adjustments (vec
<access_p
> representatives
,
4451 int adjustments_count
)
4454 ipa_parm_adjustment_vec adjustments
;
4458 gcc_assert (adjustments_count
> 0);
4459 parms
= ipa_get_vector_of_formal_parms (current_function_decl
);
4460 adjustments
.create (adjustments_count
);
4461 parm
= DECL_ARGUMENTS (current_function_decl
);
4462 for (i
= 0; i
< func_param_count
; i
++, parm
= DECL_CHAIN (parm
))
4464 struct access
*repr
= representatives
[i
];
4466 if (!repr
|| no_accesses_p (repr
))
4468 struct ipa_parm_adjustment adj
;
4470 memset (&adj
, 0, sizeof (adj
));
4471 adj
.base_index
= get_param_index (parm
, parms
);
4474 adj
.op
= IPA_PARM_OP_COPY
;
4476 adj
.op
= IPA_PARM_OP_REMOVE
;
4477 adj
.arg_prefix
= "ISRA";
4478 adjustments
.quick_push (adj
);
4482 struct ipa_parm_adjustment adj
;
4483 int index
= get_param_index (parm
, parms
);
4485 for (; repr
; repr
= repr
->next_grp
)
4487 memset (&adj
, 0, sizeof (adj
));
4488 gcc_assert (repr
->base
== parm
);
4489 adj
.base_index
= index
;
4490 adj
.base
= repr
->base
;
4491 adj
.type
= repr
->type
;
4492 adj
.alias_ptr_type
= reference_alias_ptr_type (repr
->expr
);
4493 adj
.offset
= repr
->offset
;
4494 adj
.reverse
= repr
->reverse
;
4495 adj
.by_ref
= (POINTER_TYPE_P (TREE_TYPE (repr
->base
))
4496 && (repr
->grp_maybe_modified
4497 || repr
->grp_not_necessarilly_dereferenced
));
4498 adj
.arg_prefix
= "ISRA";
4499 adjustments
.quick_push (adj
);
4507 /* Analyze the collected accesses and produce a plan what to do with the
4508 parameters in the form of adjustments, NULL meaning nothing. */
4510 static ipa_parm_adjustment_vec
4511 analyze_all_param_acesses (void)
4513 enum ipa_splicing_result repr_state
;
4514 bool proceed
= false;
4515 int i
, adjustments_count
= 0;
4516 vec
<access_p
> representatives
;
4517 ipa_parm_adjustment_vec adjustments
;
4519 repr_state
= splice_all_param_accesses (representatives
);
4520 if (repr_state
== NO_GOOD_ACCESS
)
4521 return ipa_parm_adjustment_vec ();
4523 /* If there are any parameters passed by reference which are not modified
4524 directly, we need to check whether they can be modified indirectly. */
4525 if (repr_state
== UNMODIF_BY_REF_ACCESSES
)
4527 analyze_caller_dereference_legality (representatives
);
4528 analyze_modified_params (representatives
);
4531 for (i
= 0; i
< func_param_count
; i
++)
4533 struct access
*repr
= representatives
[i
];
4535 if (repr
&& !no_accesses_p (repr
))
4537 if (repr
->grp_scalar_ptr
)
4539 adjustments_count
++;
4540 if (repr
->grp_not_necessarilly_dereferenced
4541 || repr
->grp_maybe_modified
)
4542 representatives
[i
] = NULL
;
4546 sra_stats
.scalar_by_ref_to_by_val
++;
4551 int new_components
= decide_one_param_reduction (repr
);
4553 if (new_components
== 0)
4555 representatives
[i
] = NULL
;
4556 adjustments_count
++;
4560 adjustments_count
+= new_components
;
4561 sra_stats
.aggregate_params_reduced
++;
4562 sra_stats
.param_reductions_created
+= new_components
;
4569 if (no_accesses_p (repr
))
4572 sra_stats
.deleted_unused_parameters
++;
4574 adjustments_count
++;
4578 if (!proceed
&& dump_file
)
4579 fprintf (dump_file
, "NOT proceeding to change params.\n");
4582 adjustments
= turn_representatives_into_adjustments (representatives
,
4585 adjustments
= ipa_parm_adjustment_vec ();
4587 representatives
.release ();
4591 /* If a parameter replacement identified by ADJ does not yet exist in the form
4592 of declaration, create it and record it, otherwise return the previously
4596 get_replaced_param_substitute (struct ipa_parm_adjustment
*adj
)
4599 if (!adj
->new_ssa_base
)
4601 char *pretty_name
= make_fancy_name (adj
->base
);
4603 repl
= create_tmp_reg (TREE_TYPE (adj
->base
), "ISR");
4604 DECL_NAME (repl
) = get_identifier (pretty_name
);
4605 obstack_free (&name_obstack
, pretty_name
);
4607 adj
->new_ssa_base
= repl
;
4610 repl
= adj
->new_ssa_base
;
4614 /* Find the first adjustment for a particular parameter BASE in a vector of
4615 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
4618 static struct ipa_parm_adjustment
*
4619 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments
, tree base
)
4623 len
= adjustments
.length ();
4624 for (i
= 0; i
< len
; i
++)
4626 struct ipa_parm_adjustment
*adj
;
4628 adj
= &adjustments
[i
];
4629 if (adj
->op
!= IPA_PARM_OP_COPY
&& adj
->base
== base
)
4636 /* If OLD_NAME, which is being defined by statement STMT, is an SSA_NAME of a
4637 parameter which is to be removed because its value is not used, create a new
4638 SSA_NAME relating to a replacement VAR_DECL, replace all uses of the
4639 original with it and return it. If there is no need to re-map, return NULL.
4640 ADJUSTMENTS is a pointer to a vector of IPA-SRA adjustments. */
4643 replace_removed_params_ssa_names (tree old_name
, gimple
*stmt
,
4644 ipa_parm_adjustment_vec adjustments
)
4646 struct ipa_parm_adjustment
*adj
;
4647 tree decl
, repl
, new_name
;
4649 if (TREE_CODE (old_name
) != SSA_NAME
)
4652 decl
= SSA_NAME_VAR (old_name
);
4653 if (decl
== NULL_TREE
4654 || TREE_CODE (decl
) != PARM_DECL
)
4657 adj
= get_adjustment_for_base (adjustments
, decl
);
4661 repl
= get_replaced_param_substitute (adj
);
4662 new_name
= make_ssa_name (repl
, stmt
);
4666 fprintf (dump_file
, "replacing an SSA name of a removed param ");
4667 print_generic_expr (dump_file
, old_name
, 0);
4668 fprintf (dump_file
, " with ");
4669 print_generic_expr (dump_file
, new_name
, 0);
4670 fprintf (dump_file
, "\n");
4673 replace_uses_by (old_name
, new_name
);
4677 /* If the statement STMT contains any expressions that need to replaced with a
4678 different one as noted by ADJUSTMENTS, do so. Handle any potential type
4679 incompatibilities (GSI is used to accommodate conversion statements and must
4680 point to the statement). Return true iff the statement was modified. */
4683 sra_ipa_modify_assign (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
4684 ipa_parm_adjustment_vec adjustments
)
4686 tree
*lhs_p
, *rhs_p
;
4689 if (!gimple_assign_single_p (stmt
))
4692 rhs_p
= gimple_assign_rhs1_ptr (stmt
);
4693 lhs_p
= gimple_assign_lhs_ptr (stmt
);
4695 any
= ipa_modify_expr (rhs_p
, false, adjustments
);
4696 any
|= ipa_modify_expr (lhs_p
, false, adjustments
);
4699 tree new_rhs
= NULL_TREE
;
4701 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p
), TREE_TYPE (*rhs_p
)))
4703 if (TREE_CODE (*rhs_p
) == CONSTRUCTOR
)
4705 /* V_C_Es of constructors can cause trouble (PR 42714). */
4706 if (is_gimple_reg_type (TREE_TYPE (*lhs_p
)))
4707 *rhs_p
= build_zero_cst (TREE_TYPE (*lhs_p
));
4709 *rhs_p
= build_constructor (TREE_TYPE (*lhs_p
),
4713 new_rhs
= fold_build1_loc (gimple_location (stmt
),
4714 VIEW_CONVERT_EXPR
, TREE_TYPE (*lhs_p
),
4717 else if (REFERENCE_CLASS_P (*rhs_p
)
4718 && is_gimple_reg_type (TREE_TYPE (*lhs_p
))
4719 && !is_gimple_reg (*lhs_p
))
4720 /* This can happen when an assignment in between two single field
4721 structures is turned into an assignment in between two pointers to
4722 scalars (PR 42237). */
4727 tree tmp
= force_gimple_operand_gsi (gsi
, new_rhs
, true, NULL_TREE
,
4728 true, GSI_SAME_STMT
);
4730 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
4739 /* Traverse the function body and all modifications as described in
4740 ADJUSTMENTS. Return true iff the CFG has been changed. */
4743 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments
)
4745 bool cfg_changed
= false;
4748 FOR_EACH_BB_FN (bb
, cfun
)
4750 gimple_stmt_iterator gsi
;
4752 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4754 gphi
*phi
= as_a
<gphi
*> (gsi_stmt (gsi
));
4755 tree new_lhs
, old_lhs
= gimple_phi_result (phi
);
4756 new_lhs
= replace_removed_params_ssa_names (old_lhs
, phi
, adjustments
);
4759 gimple_phi_set_result (phi
, new_lhs
);
4760 release_ssa_name (old_lhs
);
4764 gsi
= gsi_start_bb (bb
);
4765 while (!gsi_end_p (gsi
))
4767 gimple
*stmt
= gsi_stmt (gsi
);
4768 bool modified
= false;
4772 switch (gimple_code (stmt
))
4775 t
= gimple_return_retval_ptr (as_a
<greturn
*> (stmt
));
4776 if (*t
!= NULL_TREE
)
4777 modified
|= ipa_modify_expr (t
, true, adjustments
);
4781 modified
|= sra_ipa_modify_assign (stmt
, &gsi
, adjustments
);
4785 /* Operands must be processed before the lhs. */
4786 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
4788 t
= gimple_call_arg_ptr (stmt
, i
);
4789 modified
|= ipa_modify_expr (t
, true, adjustments
);
4792 if (gimple_call_lhs (stmt
))
4794 t
= gimple_call_lhs_ptr (stmt
);
4795 modified
|= ipa_modify_expr (t
, false, adjustments
);
4801 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
4802 for (i
= 0; i
< gimple_asm_ninputs (asm_stmt
); i
++)
4804 t
= &TREE_VALUE (gimple_asm_input_op (asm_stmt
, i
));
4805 modified
|= ipa_modify_expr (t
, true, adjustments
);
4807 for (i
= 0; i
< gimple_asm_noutputs (asm_stmt
); i
++)
4809 t
= &TREE_VALUE (gimple_asm_output_op (asm_stmt
, i
));
4810 modified
|= ipa_modify_expr (t
, false, adjustments
);
4821 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
4823 tree old_def
= DEF_FROM_PTR (defp
);
4824 if (tree new_def
= replace_removed_params_ssa_names (old_def
, stmt
,
4827 SET_DEF (defp
, new_def
);
4828 release_ssa_name (old_def
);
4836 if (maybe_clean_eh_stmt (stmt
)
4837 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
4847 /* Call gimple_debug_bind_reset_value on all debug statements describing
4848 gimple register parameters that are being removed or replaced. */
4851 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments
)
4854 gimple_stmt_iterator
*gsip
= NULL
, gsi
;
4856 if (MAY_HAVE_DEBUG_STMTS
&& single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun
)))
4858 gsi
= gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
4861 len
= adjustments
.length ();
4862 for (i
= 0; i
< len
; i
++)
4864 struct ipa_parm_adjustment
*adj
;
4865 imm_use_iterator ui
;
4868 tree name
, vexpr
, copy
= NULL_TREE
;
4869 use_operand_p use_p
;
4871 adj
= &adjustments
[i
];
4872 if (adj
->op
== IPA_PARM_OP_COPY
|| !is_gimple_reg (adj
->base
))
4874 name
= ssa_default_def (cfun
, adj
->base
);
4877 FOR_EACH_IMM_USE_STMT (stmt
, ui
, name
)
4879 if (gimple_clobber_p (stmt
))
4881 gimple_stmt_iterator cgsi
= gsi_for_stmt (stmt
);
4882 unlink_stmt_vdef (stmt
);
4883 gsi_remove (&cgsi
, true);
4884 release_defs (stmt
);
4887 /* All other users must have been removed by
4888 ipa_sra_modify_function_body. */
4889 gcc_assert (is_gimple_debug (stmt
));
4890 if (vexpr
== NULL
&& gsip
!= NULL
)
4892 gcc_assert (TREE_CODE (adj
->base
) == PARM_DECL
);
4893 vexpr
= make_node (DEBUG_EXPR_DECL
);
4894 def_temp
= gimple_build_debug_source_bind (vexpr
, adj
->base
,
4896 DECL_ARTIFICIAL (vexpr
) = 1;
4897 TREE_TYPE (vexpr
) = TREE_TYPE (name
);
4898 DECL_MODE (vexpr
) = DECL_MODE (adj
->base
);
4899 gsi_insert_before (gsip
, def_temp
, GSI_SAME_STMT
);
4903 FOR_EACH_IMM_USE_ON_STMT (use_p
, ui
)
4904 SET_USE (use_p
, vexpr
);
4907 gimple_debug_bind_reset_value (stmt
);
4910 /* Create a VAR_DECL for debug info purposes. */
4911 if (!DECL_IGNORED_P (adj
->base
))
4913 copy
= build_decl (DECL_SOURCE_LOCATION (current_function_decl
),
4914 VAR_DECL
, DECL_NAME (adj
->base
),
4915 TREE_TYPE (adj
->base
));
4916 if (DECL_PT_UID_SET_P (adj
->base
))
4917 SET_DECL_PT_UID (copy
, DECL_PT_UID (adj
->base
));
4918 TREE_ADDRESSABLE (copy
) = TREE_ADDRESSABLE (adj
->base
);
4919 TREE_READONLY (copy
) = TREE_READONLY (adj
->base
);
4920 TREE_THIS_VOLATILE (copy
) = TREE_THIS_VOLATILE (adj
->base
);
4921 DECL_GIMPLE_REG_P (copy
) = DECL_GIMPLE_REG_P (adj
->base
);
4922 DECL_ARTIFICIAL (copy
) = DECL_ARTIFICIAL (adj
->base
);
4923 DECL_IGNORED_P (copy
) = DECL_IGNORED_P (adj
->base
);
4924 DECL_ABSTRACT_ORIGIN (copy
) = DECL_ORIGIN (adj
->base
);
4925 DECL_SEEN_IN_BIND_EXPR_P (copy
) = 1;
4926 SET_DECL_RTL (copy
, 0);
4927 TREE_USED (copy
) = 1;
4928 DECL_CONTEXT (copy
) = current_function_decl
;
4929 add_local_decl (cfun
, copy
);
4931 BLOCK_VARS (DECL_INITIAL (current_function_decl
));
4932 BLOCK_VARS (DECL_INITIAL (current_function_decl
)) = copy
;
4934 if (gsip
!= NULL
&& copy
&& target_for_debug_bind (adj
->base
))
4936 gcc_assert (TREE_CODE (adj
->base
) == PARM_DECL
);
4938 def_temp
= gimple_build_debug_bind (copy
, vexpr
, NULL
);
4940 def_temp
= gimple_build_debug_source_bind (copy
, adj
->base
,
4942 gsi_insert_before (gsip
, def_temp
, GSI_SAME_STMT
);
4947 /* Return false if all callers have at least as many actual arguments as there
4948 are formal parameters in the current function and that their types
4952 some_callers_have_mismatched_arguments_p (struct cgraph_node
*node
,
4953 void *data ATTRIBUTE_UNUSED
)
4955 struct cgraph_edge
*cs
;
4956 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4957 if (!cs
->call_stmt
|| !callsite_arguments_match_p (cs
->call_stmt
))
4963 /* Return false if all callers have vuse attached to a call statement. */
4966 some_callers_have_no_vuse_p (struct cgraph_node
*node
,
4967 void *data ATTRIBUTE_UNUSED
)
4969 struct cgraph_edge
*cs
;
4970 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4971 if (!cs
->call_stmt
|| !gimple_vuse (cs
->call_stmt
))
4977 /* Convert all callers of NODE. */
4980 convert_callers_for_node (struct cgraph_node
*node
,
4983 ipa_parm_adjustment_vec
*adjustments
= (ipa_parm_adjustment_vec
*) data
;
4984 bitmap recomputed_callers
= BITMAP_ALLOC (NULL
);
4985 struct cgraph_edge
*cs
;
4987 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4989 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
4992 fprintf (dump_file
, "Adjusting call %s/%i -> %s/%i\n",
4993 xstrdup_for_dump (cs
->caller
->name ()),
4995 xstrdup_for_dump (cs
->callee
->name ()),
4998 ipa_modify_call_arguments (cs
, cs
->call_stmt
, *adjustments
);
5003 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5004 if (bitmap_set_bit (recomputed_callers
, cs
->caller
->uid
)
5005 && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (cs
->caller
->decl
)))
5006 compute_inline_parameters (cs
->caller
, true);
5007 BITMAP_FREE (recomputed_callers
);
5012 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
5015 convert_callers (struct cgraph_node
*node
, tree old_decl
,
5016 ipa_parm_adjustment_vec adjustments
)
5018 basic_block this_block
;
5020 node
->call_for_symbol_and_aliases (convert_callers_for_node
,
5021 &adjustments
, false);
5023 if (!encountered_recursive_call
)
5026 FOR_EACH_BB_FN (this_block
, cfun
)
5028 gimple_stmt_iterator gsi
;
5030 for (gsi
= gsi_start_bb (this_block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
5034 stmt
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
5037 call_fndecl
= gimple_call_fndecl (stmt
);
5038 if (call_fndecl
== old_decl
)
5041 fprintf (dump_file
, "Adjusting recursive call");
5042 gimple_call_set_fndecl (stmt
, node
->decl
);
5043 ipa_modify_call_arguments (NULL
, stmt
, adjustments
);
5051 /* Perform all the modification required in IPA-SRA for NODE to have parameters
5052 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */
5055 modify_function (struct cgraph_node
*node
, ipa_parm_adjustment_vec adjustments
)
5057 struct cgraph_node
*new_node
;
5060 cgraph_edge::rebuild_edges ();
5061 free_dominance_info (CDI_DOMINATORS
);
5064 /* This must be done after rebuilding cgraph edges for node above.
5065 Otherwise any recursive calls to node that are recorded in
5066 redirect_callers will be corrupted. */
5067 vec
<cgraph_edge
*> redirect_callers
= node
->collect_callers ();
5068 new_node
= node
->create_version_clone_with_body (redirect_callers
, NULL
,
5069 NULL
, false, NULL
, NULL
,
5071 redirect_callers
.release ();
5073 push_cfun (DECL_STRUCT_FUNCTION (new_node
->decl
));
5074 ipa_modify_formal_parameters (current_function_decl
, adjustments
);
5075 cfg_changed
= ipa_sra_modify_function_body (adjustments
);
5076 sra_ipa_reset_debug_stmts (adjustments
);
5077 convert_callers (new_node
, node
->decl
, adjustments
);
5078 new_node
->make_local ();
5082 /* Means of communication between ipa_sra_check_caller and
5083 ipa_sra_preliminary_function_checks. */
5085 struct ipa_sra_check_caller_data
5088 bool bad_arg_alignment
;
5092 /* If NODE has a caller, mark that fact in DATA which is pointer to
5093 ipa_sra_check_caller_data. Also check all aggregate arguments in all known
5094 calls if they are unit aligned and if not, set the appropriate flag in DATA
5098 ipa_sra_check_caller (struct cgraph_node
*node
, void *data
)
5103 struct ipa_sra_check_caller_data
*iscc
;
5104 iscc
= (struct ipa_sra_check_caller_data
*) data
;
5105 iscc
->has_callers
= true;
5107 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5109 if (cs
->caller
->thunk
.thunk_p
)
5111 iscc
->has_thunk
= true;
5114 gimple
*call_stmt
= cs
->call_stmt
;
5115 unsigned count
= gimple_call_num_args (call_stmt
);
5116 for (unsigned i
= 0; i
< count
; i
++)
5118 tree arg
= gimple_call_arg (call_stmt
, i
);
5119 if (is_gimple_reg (arg
))
5123 HOST_WIDE_INT bitsize
, bitpos
;
5125 int unsignedp
, reversep
, volatilep
= 0;
5126 get_inner_reference (arg
, &bitsize
, &bitpos
, &offset
, &mode
,
5127 &unsignedp
, &reversep
, &volatilep
, false);
5128 if (bitpos
% BITS_PER_UNIT
)
5130 iscc
->bad_arg_alignment
= true;
5139 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
5140 attributes, return true otherwise. NODE is the cgraph node of the current
5144 ipa_sra_preliminary_function_checks (struct cgraph_node
*node
)
5146 if (!node
->can_be_local_p ())
5149 fprintf (dump_file
, "Function not local to this compilation unit.\n");
5153 if (!node
->local
.can_change_signature
)
5156 fprintf (dump_file
, "Function can not change signature.\n");
5160 if (!tree_versionable_function_p (node
->decl
))
5163 fprintf (dump_file
, "Function is not versionable.\n");
5167 if (!opt_for_fn (node
->decl
, optimize
)
5168 || !opt_for_fn (node
->decl
, flag_ipa_sra
))
5171 fprintf (dump_file
, "Function not optimized.\n");
5175 if (DECL_VIRTUAL_P (current_function_decl
))
5178 fprintf (dump_file
, "Function is a virtual method.\n");
5182 if ((DECL_ONE_ONLY (node
->decl
) || DECL_EXTERNAL (node
->decl
))
5183 && inline_summaries
->get (node
)->size
>= MAX_INLINE_INSNS_AUTO
)
5186 fprintf (dump_file
, "Function too big to be made truly local.\n");
5193 fprintf (dump_file
, "Function uses stdarg. \n");
5197 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
5200 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
5203 fprintf (dump_file
, "Always inline function will be inlined "
5208 struct ipa_sra_check_caller_data iscc
;
5209 memset (&iscc
, 0, sizeof(iscc
));
5210 node
->call_for_symbol_and_aliases (ipa_sra_check_caller
, &iscc
, true);
5211 if (!iscc
.has_callers
)
5215 "Function has no callers in this compilation unit.\n");
5219 if (iscc
.bad_arg_alignment
)
5223 "A function call has an argument with non-unit alignment.\n");
5238 /* Perform early interprocedural SRA. */
5241 ipa_early_sra (void)
5243 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
5244 ipa_parm_adjustment_vec adjustments
;
5247 if (!ipa_sra_preliminary_function_checks (node
))
5251 sra_mode
= SRA_MODE_EARLY_IPA
;
5253 if (!find_param_candidates ())
5256 fprintf (dump_file
, "Function has no IPA-SRA candidates.\n");
5260 if (node
->call_for_symbol_and_aliases
5261 (some_callers_have_mismatched_arguments_p
, NULL
, true))
5264 fprintf (dump_file
, "There are callers with insufficient number of "
5265 "arguments or arguments with type mismatches.\n");
5269 if (node
->call_for_symbol_and_aliases
5270 (some_callers_have_no_vuse_p
, NULL
, true))
5273 fprintf (dump_file
, "There are callers with no VUSE attached "
5274 "to a call stmt.\n");
5278 bb_dereferences
= XCNEWVEC (HOST_WIDE_INT
,
5280 * last_basic_block_for_fn (cfun
));
5281 final_bbs
= BITMAP_ALLOC (NULL
);
5284 if (encountered_apply_args
)
5287 fprintf (dump_file
, "Function calls __builtin_apply_args().\n");
5291 if (encountered_unchangable_recursive_call
)
5294 fprintf (dump_file
, "Function calls itself with insufficient "
5295 "number of arguments.\n");
5299 adjustments
= analyze_all_param_acesses ();
5300 if (!adjustments
.exists ())
5303 ipa_dump_param_adjustments (dump_file
, adjustments
, current_function_decl
);
5305 if (modify_function (node
, adjustments
))
5306 ret
= TODO_update_ssa
| TODO_cleanup_cfg
;
5308 ret
= TODO_update_ssa
;
5309 adjustments
.release ();
5311 statistics_counter_event (cfun
, "Unused parameters deleted",
5312 sra_stats
.deleted_unused_parameters
);
5313 statistics_counter_event (cfun
, "Scalar parameters converted to by-value",
5314 sra_stats
.scalar_by_ref_to_by_val
);
5315 statistics_counter_event (cfun
, "Aggregate parameters broken up",
5316 sra_stats
.aggregate_params_reduced
);
5317 statistics_counter_event (cfun
, "Aggregate parameter components created",
5318 sra_stats
.param_reductions_created
);
5321 BITMAP_FREE (final_bbs
);
5322 free (bb_dereferences
);
5324 sra_deinitialize ();
5330 const pass_data pass_data_early_ipa_sra
=
5332 GIMPLE_PASS
, /* type */
5333 "eipa_sra", /* name */
5334 OPTGROUP_NONE
, /* optinfo_flags */
5335 TV_IPA_SRA
, /* tv_id */
5336 0, /* properties_required */
5337 0, /* properties_provided */
5338 0, /* properties_destroyed */
5339 0, /* todo_flags_start */
5340 TODO_dump_symtab
, /* todo_flags_finish */
5343 class pass_early_ipa_sra
: public gimple_opt_pass
5346 pass_early_ipa_sra (gcc::context
*ctxt
)
5347 : gimple_opt_pass (pass_data_early_ipa_sra
, ctxt
)
5350 /* opt_pass methods: */
5351 virtual bool gate (function
*) { return flag_ipa_sra
&& dbg_cnt (eipa_sra
); }
5352 virtual unsigned int execute (function
*) { return ipa_early_sra (); }
5354 }; // class pass_early_ipa_sra
5359 make_pass_early_ipa_sra (gcc::context
*ctxt
)
5361 return new pass_early_ipa_sra (ctxt
);