1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
3 optimizers.
4 Copyright (C) 2008-2018 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
6
7 This file is part of GCC.
8
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
12 version.
13
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
17 for more details.
18
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/>. */
22
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.
27
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
31 conversions.
32
33 Both passes operate in four stages:
34
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.
38
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.
46
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
49 accesses.
50
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.
55
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).
60
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.
64
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.
67
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. */
73
74 #include "config.h"
75 #include "system.h"
76 #include "coretypes.h"
77 #include "backend.h"
78 #include "target.h"
79 #include "rtl.h"
80 #include "tree.h"
81 #include "gimple.h"
82 #include "predict.h"
83 #include "alloc-pool.h"
84 #include "tree-pass.h"
85 #include "ssa.h"
86 #include "cgraph.h"
87 #include "gimple-pretty-print.h"
88 #include "alias.h"
89 #include "fold-const.h"
90 #include "tree-eh.h"
91 #include "stor-layout.h"
92 #include "gimplify.h"
93 #include "gimple-iterator.h"
94 #include "gimplify-me.h"
95 #include "gimple-walk.h"
96 #include "tree-cfg.h"
97 #include "tree-dfa.h"
98 #include "tree-ssa.h"
99 #include "symbol-summary.h"
100 #include "ipa-param-manipulation.h"
101 #include "ipa-prop.h"
102 #include "params.h"
103 #include "dbgcnt.h"
104 #include "tree-inline.h"
105 #include "ipa-fnsummary.h"
106 #include "ipa-utils.h"
107 #include "builtins.h"
108
109 /* Enumeration of all aggregate reductions we can do. */
110 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
111 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
112 SRA_MODE_INTRA }; /* late intraprocedural SRA */
113
114 /* Global variable describing which aggregate reduction we are performing at
115 the moment. */
116 static enum sra_mode sra_mode;
117
118 struct assign_link;
119
120 /* ACCESS represents each access to an aggregate variable (as a whole or a
121 part). It can also represent a group of accesses that refer to exactly the
122 same fragment of an aggregate (i.e. those that have exactly the same offset
123 and size). Such representatives for a single aggregate, once determined,
124 are linked in a linked list and have the group fields set.
125
126 Moreover, when doing intraprocedural SRA, a tree is built from those
127 representatives (by the means of first_child and next_sibling pointers), in
128 which all items in a subtree are "within" the root, i.e. their offset is
129 greater or equal to offset of the root and offset+size is smaller or equal
130 to offset+size of the root. Children of an access are sorted by offset.
131
132 Note that accesses to parts of vector and complex number types always
133 represented by an access to the whole complex number or a vector. It is a
134 duty of the modifying functions to replace them appropriately. */
135
136 struct access
137 {
138 /* Values returned by `get_ref_base_and_extent' for each component reference
139 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
140 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
141 HOST_WIDE_INT offset;
142 HOST_WIDE_INT size;
143 tree base;
144
145 /* Expression. It is context dependent so do not use it to create new
146 expressions to access the original aggregate. See PR 42154 for a
147 testcase. */
148 tree expr;
149 /* Type. */
150 tree type;
151
152 /* The statement this access belongs to. */
153 gimple *stmt;
154
155 /* Next group representative for this aggregate. */
156 struct access *next_grp;
157
158 /* Pointer to the group representative. Pointer to itself if the struct is
159 the representative. */
160 struct access *group_representative;
161
162 /* After access tree has been constructed, this points to the parent of the
163 current access, if there is one. NULL for roots. */
164 struct access *parent;
165
166 /* If this access has any children (in terms of the definition above), this
167 points to the first one. */
168 struct access *first_child;
169
170 /* In intraprocedural SRA, pointer to the next sibling in the access tree as
171 described above. In IPA-SRA this is a pointer to the next access
172 belonging to the same group (having the same representative). */
173 struct access *next_sibling;
174
175 /* Pointers to the first and last element in the linked list of assign
176 links. */
177 struct assign_link *first_link, *last_link;
178
179 /* Pointer to the next access in the work queue. */
180 struct access *next_queued;
181
182 /* Replacement variable for this access "region." Never to be accessed
183 directly, always only by the means of get_access_replacement() and only
184 when grp_to_be_replaced flag is set. */
185 tree replacement_decl;
186
187 /* Is this access an access to a non-addressable field? */
188 unsigned non_addressable : 1;
189
190 /* Is this access made in reverse storage order? */
191 unsigned reverse : 1;
192
193 /* Is this particular access write access? */
194 unsigned write : 1;
195
196 /* Is this access currently in the work queue? */
197 unsigned grp_queued : 1;
198
199 /* Does this group contain a write access? This flag is propagated down the
200 access tree. */
201 unsigned grp_write : 1;
202
203 /* Does this group contain a read access? This flag is propagated down the
204 access tree. */
205 unsigned grp_read : 1;
206
207 /* Does this group contain a read access that comes from an assignment
208 statement? This flag is propagated down the access tree. */
209 unsigned grp_assignment_read : 1;
210
211 /* Does this group contain a write access that comes from an assignment
212 statement? This flag is propagated down the access tree. */
213 unsigned grp_assignment_write : 1;
214
215 /* Does this group contain a read access through a scalar type? This flag is
216 not propagated in the access tree in any direction. */
217 unsigned grp_scalar_read : 1;
218
219 /* Does this group contain a write access through a scalar type? This flag
220 is not propagated in the access tree in any direction. */
221 unsigned grp_scalar_write : 1;
222
223 /* Is this access an artificial one created to scalarize some record
224 entirely? */
225 unsigned grp_total_scalarization : 1;
226
227 /* Other passes of the analysis use this bit to make function
228 analyze_access_subtree create scalar replacements for this group if
229 possible. */
230 unsigned grp_hint : 1;
231
232 /* Is the subtree rooted in this access fully covered by scalar
233 replacements? */
234 unsigned grp_covered : 1;
235
236 /* If set to true, this access and all below it in an access tree must not be
237 scalarized. */
238 unsigned grp_unscalarizable_region : 1;
239
240 /* Whether data have been written to parts of the aggregate covered by this
241 access which is not to be scalarized. This flag is propagated up in the
242 access tree. */
243 unsigned grp_unscalarized_data : 1;
244
245 /* Does this access and/or group contain a write access through a
246 BIT_FIELD_REF? */
247 unsigned grp_partial_lhs : 1;
248
249 /* Set when a scalar replacement should be created for this variable. */
250 unsigned grp_to_be_replaced : 1;
251
252 /* Set when we want a replacement for the sole purpose of having it in
253 generated debug statements. */
254 unsigned grp_to_be_debug_replaced : 1;
255
256 /* Should TREE_NO_WARNING of a replacement be set? */
257 unsigned grp_no_warning : 1;
258
259 /* Is it possible that the group refers to data which might be (directly or
260 otherwise) modified? */
261 unsigned grp_maybe_modified : 1;
262
263 /* Set when this is a representative of a pointer to scalar (i.e. by
264 reference) parameter which we consider for turning into a plain scalar
265 (i.e. a by value parameter). */
266 unsigned grp_scalar_ptr : 1;
267
268 /* Set when we discover that this pointer is not safe to dereference in the
269 caller. */
270 unsigned grp_not_necessarilly_dereferenced : 1;
271 };
272
273 typedef struct access *access_p;
274
275
276 /* Alloc pool for allocating access structures. */
277 static object_allocator<struct access> access_pool ("SRA accesses");
278
279 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
280 are used to propagate subaccesses from rhs to lhs as long as they don't
281 conflict with what is already there. */
282 struct assign_link
283 {
284 struct access *lacc, *racc;
285 struct assign_link *next;
286 };
287
288 /* Alloc pool for allocating assign link structures. */
289 static object_allocator<assign_link> assign_link_pool ("SRA links");
290
291 /* Base (tree) -> Vector (vec<access_p> *) map. */
292 static hash_map<tree, auto_vec<access_p> > *base_access_vec;
293
294 /* Candidate hash table helpers. */
295
296 struct uid_decl_hasher : nofree_ptr_hash <tree_node>
297 {
298 static inline hashval_t hash (const tree_node *);
299 static inline bool equal (const tree_node *, const tree_node *);
300 };
301
302 /* Hash a tree in a uid_decl_map. */
303
304 inline hashval_t
hash(const tree_node * item)305 uid_decl_hasher::hash (const tree_node *item)
306 {
307 return item->decl_minimal.uid;
308 }
309
310 /* Return true if the DECL_UID in both trees are equal. */
311
312 inline bool
equal(const tree_node * a,const tree_node * b)313 uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
314 {
315 return (a->decl_minimal.uid == b->decl_minimal.uid);
316 }
317
318 /* Set of candidates. */
319 static bitmap candidate_bitmap;
320 static hash_table<uid_decl_hasher> *candidates;
321
322 /* For a candidate UID return the candidates decl. */
323
324 static inline tree
candidate(unsigned uid)325 candidate (unsigned uid)
326 {
327 tree_node t;
328 t.decl_minimal.uid = uid;
329 return candidates->find_with_hash (&t, static_cast <hashval_t> (uid));
330 }
331
332 /* Bitmap of candidates which we should try to entirely scalarize away and
333 those which cannot be (because they are and need be used as a whole). */
334 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
335
336 /* Bitmap of candidates in the constant pool, which cannot be scalarized
337 because this would produce non-constant expressions (e.g. Ada). */
338 static bitmap disqualified_constants;
339
340 /* Obstack for creation of fancy names. */
341 static struct obstack name_obstack;
342
343 /* Head of a linked list of accesses that need to have its subaccesses
344 propagated to their assignment counterparts. */
345 static struct access *work_queue_head;
346
347 /* Number of parameters of the analyzed function when doing early ipa SRA. */
348 static int func_param_count;
349
350 /* scan_function sets the following to true if it encounters a call to
351 __builtin_apply_args. */
352 static bool encountered_apply_args;
353
354 /* Set by scan_function when it finds a recursive call. */
355 static bool encountered_recursive_call;
356
357 /* Set by scan_function when it finds a recursive call with less actual
358 arguments than formal parameters.. */
359 static bool encountered_unchangable_recursive_call;
360
361 /* This is a table in which for each basic block and parameter there is a
362 distance (offset + size) in that parameter which is dereferenced and
363 accessed in that BB. */
364 static HOST_WIDE_INT *bb_dereferences;
365 /* Bitmap of BBs that can cause the function to "stop" progressing by
366 returning, throwing externally, looping infinitely or calling a function
367 which might abort etc.. */
368 static bitmap final_bbs;
369
370 /* Representative of no accesses at all. */
371 static struct access no_accesses_representant;
372
373 /* Predicate to test the special value. */
374
375 static inline bool
no_accesses_p(struct access * access)376 no_accesses_p (struct access *access)
377 {
378 return access == &no_accesses_representant;
379 }
380
381 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
382 representative fields are dumped, otherwise those which only describe the
383 individual access are. */
384
385 static struct
386 {
387 /* Number of processed aggregates is readily available in
388 analyze_all_variable_accesses and so is not stored here. */
389
390 /* Number of created scalar replacements. */
391 int replacements;
392
393 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
394 expression. */
395 int exprs;
396
397 /* Number of statements created by generate_subtree_copies. */
398 int subtree_copies;
399
400 /* Number of statements created by load_assign_lhs_subreplacements. */
401 int subreplacements;
402
403 /* Number of times sra_modify_assign has deleted a statement. */
404 int deleted;
405
406 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
407 RHS reparately due to type conversions or nonexistent matching
408 references. */
409 int separate_lhs_rhs_handling;
410
411 /* Number of parameters that were removed because they were unused. */
412 int deleted_unused_parameters;
413
414 /* Number of scalars passed as parameters by reference that have been
415 converted to be passed by value. */
416 int scalar_by_ref_to_by_val;
417
418 /* Number of aggregate parameters that were replaced by one or more of their
419 components. */
420 int aggregate_params_reduced;
421
422 /* Numbber of components created when splitting aggregate parameters. */
423 int param_reductions_created;
424 } sra_stats;
425
426 static void
dump_access(FILE * f,struct access * access,bool grp)427 dump_access (FILE *f, struct access *access, bool grp)
428 {
429 fprintf (f, "access { ");
430 fprintf (f, "base = (%d)'", DECL_UID (access->base));
431 print_generic_expr (f, access->base);
432 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
433 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
434 fprintf (f, ", expr = ");
435 print_generic_expr (f, access->expr);
436 fprintf (f, ", type = ");
437 print_generic_expr (f, access->type);
438 fprintf (f, ", non_addressable = %d, reverse = %d",
439 access->non_addressable, access->reverse);
440 if (grp)
441 fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
442 "grp_assignment_write = %d, grp_scalar_read = %d, "
443 "grp_scalar_write = %d, grp_total_scalarization = %d, "
444 "grp_hint = %d, grp_covered = %d, "
445 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
446 "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
447 "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
448 "grp_not_necessarilly_dereferenced = %d\n",
449 access->grp_read, access->grp_write, access->grp_assignment_read,
450 access->grp_assignment_write, access->grp_scalar_read,
451 access->grp_scalar_write, access->grp_total_scalarization,
452 access->grp_hint, access->grp_covered,
453 access->grp_unscalarizable_region, access->grp_unscalarized_data,
454 access->grp_partial_lhs, access->grp_to_be_replaced,
455 access->grp_to_be_debug_replaced, access->grp_maybe_modified,
456 access->grp_not_necessarilly_dereferenced);
457 else
458 fprintf (f, ", write = %d, grp_total_scalarization = %d, "
459 "grp_partial_lhs = %d\n",
460 access->write, access->grp_total_scalarization,
461 access->grp_partial_lhs);
462 }
463
464 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
465
466 static void
dump_access_tree_1(FILE * f,struct access * access,int level)467 dump_access_tree_1 (FILE *f, struct access *access, int level)
468 {
469 do
470 {
471 int i;
472
473 for (i = 0; i < level; i++)
474 fputs ("* ", f);
475
476 dump_access (f, access, true);
477
478 if (access->first_child)
479 dump_access_tree_1 (f, access->first_child, level + 1);
480
481 access = access->next_sibling;
482 }
483 while (access);
484 }
485
486 /* Dump all access trees for a variable, given the pointer to the first root in
487 ACCESS. */
488
489 static void
dump_access_tree(FILE * f,struct access * access)490 dump_access_tree (FILE *f, struct access *access)
491 {
492 for (; access; access = access->next_grp)
493 dump_access_tree_1 (f, access, 0);
494 }
495
496 /* Return true iff ACC is non-NULL and has subaccesses. */
497
498 static inline bool
access_has_children_p(struct access * acc)499 access_has_children_p (struct access *acc)
500 {
501 return acc && acc->first_child;
502 }
503
504 /* Return true iff ACC is (partly) covered by at least one replacement. */
505
506 static bool
access_has_replacements_p(struct access * acc)507 access_has_replacements_p (struct access *acc)
508 {
509 struct access *child;
510 if (acc->grp_to_be_replaced)
511 return true;
512 for (child = acc->first_child; child; child = child->next_sibling)
513 if (access_has_replacements_p (child))
514 return true;
515 return false;
516 }
517
518 /* Return a vector of pointers to accesses for the variable given in BASE or
519 NULL if there is none. */
520
521 static vec<access_p> *
get_base_access_vector(tree base)522 get_base_access_vector (tree base)
523 {
524 return base_access_vec->get (base);
525 }
526
527 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
528 in ACCESS. Return NULL if it cannot be found. */
529
530 static struct access *
find_access_in_subtree(struct access * access,HOST_WIDE_INT offset,HOST_WIDE_INT size)531 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
532 HOST_WIDE_INT size)
533 {
534 while (access && (access->offset != offset || access->size != size))
535 {
536 struct access *child = access->first_child;
537
538 while (child && (child->offset + child->size <= offset))
539 child = child->next_sibling;
540 access = child;
541 }
542
543 return access;
544 }
545
546 /* Return the first group representative for DECL or NULL if none exists. */
547
548 static struct access *
get_first_repr_for_decl(tree base)549 get_first_repr_for_decl (tree base)
550 {
551 vec<access_p> *access_vec;
552
553 access_vec = get_base_access_vector (base);
554 if (!access_vec)
555 return NULL;
556
557 return (*access_vec)[0];
558 }
559
560 /* Find an access representative for the variable BASE and given OFFSET and
561 SIZE. Requires that access trees have already been built. Return NULL if
562 it cannot be found. */
563
564 static struct access *
get_var_base_offset_size_access(tree base,HOST_WIDE_INT offset,HOST_WIDE_INT size)565 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
566 HOST_WIDE_INT size)
567 {
568 struct access *access;
569
570 access = get_first_repr_for_decl (base);
571 while (access && (access->offset + access->size <= offset))
572 access = access->next_grp;
573 if (!access)
574 return NULL;
575
576 return find_access_in_subtree (access, offset, size);
577 }
578
579 /* Add LINK to the linked list of assign links of RACC. */
580 static void
add_link_to_rhs(struct access * racc,struct assign_link * link)581 add_link_to_rhs (struct access *racc, struct assign_link *link)
582 {
583 gcc_assert (link->racc == racc);
584
585 if (!racc->first_link)
586 {
587 gcc_assert (!racc->last_link);
588 racc->first_link = link;
589 }
590 else
591 racc->last_link->next = link;
592
593 racc->last_link = link;
594 link->next = NULL;
595 }
596
597 /* Move all link structures in their linked list in OLD_RACC to the linked list
598 in NEW_RACC. */
599 static void
relink_to_new_repr(struct access * new_racc,struct access * old_racc)600 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
601 {
602 if (!old_racc->first_link)
603 {
604 gcc_assert (!old_racc->last_link);
605 return;
606 }
607
608 if (new_racc->first_link)
609 {
610 gcc_assert (!new_racc->last_link->next);
611 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
612
613 new_racc->last_link->next = old_racc->first_link;
614 new_racc->last_link = old_racc->last_link;
615 }
616 else
617 {
618 gcc_assert (!new_racc->last_link);
619
620 new_racc->first_link = old_racc->first_link;
621 new_racc->last_link = old_racc->last_link;
622 }
623 old_racc->first_link = old_racc->last_link = NULL;
624 }
625
626 /* Add ACCESS to the work queue (which is actually a stack). */
627
628 static void
add_access_to_work_queue(struct access * access)629 add_access_to_work_queue (struct access *access)
630 {
631 if (access->first_link && !access->grp_queued)
632 {
633 gcc_assert (!access->next_queued);
634 access->next_queued = work_queue_head;
635 access->grp_queued = 1;
636 work_queue_head = access;
637 }
638 }
639
640 /* Pop an access from the work queue, and return it, assuming there is one. */
641
642 static struct access *
pop_access_from_work_queue(void)643 pop_access_from_work_queue (void)
644 {
645 struct access *access = work_queue_head;
646
647 work_queue_head = access->next_queued;
648 access->next_queued = NULL;
649 access->grp_queued = 0;
650 return access;
651 }
652
653
654 /* Allocate necessary structures. */
655
656 static void
sra_initialize(void)657 sra_initialize (void)
658 {
659 candidate_bitmap = BITMAP_ALLOC (NULL);
660 candidates = new hash_table<uid_decl_hasher>
661 (vec_safe_length (cfun->local_decls) / 2);
662 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
663 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
664 disqualified_constants = BITMAP_ALLOC (NULL);
665 gcc_obstack_init (&name_obstack);
666 base_access_vec = new hash_map<tree, auto_vec<access_p> >;
667 memset (&sra_stats, 0, sizeof (sra_stats));
668 encountered_apply_args = false;
669 encountered_recursive_call = false;
670 encountered_unchangable_recursive_call = false;
671 }
672
673 /* Deallocate all general structures. */
674
675 static void
sra_deinitialize(void)676 sra_deinitialize (void)
677 {
678 BITMAP_FREE (candidate_bitmap);
679 delete candidates;
680 candidates = NULL;
681 BITMAP_FREE (should_scalarize_away_bitmap);
682 BITMAP_FREE (cannot_scalarize_away_bitmap);
683 BITMAP_FREE (disqualified_constants);
684 access_pool.release ();
685 assign_link_pool.release ();
686 obstack_free (&name_obstack, NULL);
687
688 delete base_access_vec;
689 }
690
691 /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
692
constant_decl_p(tree decl)693 static bool constant_decl_p (tree decl)
694 {
695 return VAR_P (decl) && DECL_IN_CONSTANT_POOL (decl);
696 }
697
698 /* Remove DECL from candidates for SRA and write REASON to the dump file if
699 there is one. */
700
701 static void
disqualify_candidate(tree decl,const char * reason)702 disqualify_candidate (tree decl, const char *reason)
703 {
704 if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
705 candidates->remove_elt_with_hash (decl, DECL_UID (decl));
706 if (constant_decl_p (decl))
707 bitmap_set_bit (disqualified_constants, DECL_UID (decl));
708
709 if (dump_file && (dump_flags & TDF_DETAILS))
710 {
711 fprintf (dump_file, "! Disqualifying ");
712 print_generic_expr (dump_file, decl);
713 fprintf (dump_file, " - %s\n", reason);
714 }
715 }
716
717 /* Return true iff the type contains a field or an element which does not allow
718 scalarization. */
719
720 static bool
type_internals_preclude_sra_p(tree type,const char ** msg)721 type_internals_preclude_sra_p (tree type, const char **msg)
722 {
723 tree fld;
724 tree et;
725
726 switch (TREE_CODE (type))
727 {
728 case RECORD_TYPE:
729 case UNION_TYPE:
730 case QUAL_UNION_TYPE:
731 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
732 if (TREE_CODE (fld) == FIELD_DECL)
733 {
734 tree ft = TREE_TYPE (fld);
735
736 if (TREE_THIS_VOLATILE (fld))
737 {
738 *msg = "volatile structure field";
739 return true;
740 }
741 if (!DECL_FIELD_OFFSET (fld))
742 {
743 *msg = "no structure field offset";
744 return true;
745 }
746 if (!DECL_SIZE (fld))
747 {
748 *msg = "zero structure field size";
749 return true;
750 }
751 if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
752 {
753 *msg = "structure field offset not fixed";
754 return true;
755 }
756 if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
757 {
758 *msg = "structure field size not fixed";
759 return true;
760 }
761 if (!tree_fits_shwi_p (bit_position (fld)))
762 {
763 *msg = "structure field size too big";
764 return true;
765 }
766 if (AGGREGATE_TYPE_P (ft)
767 && int_bit_position (fld) % BITS_PER_UNIT != 0)
768 {
769 *msg = "structure field is bit field";
770 return true;
771 }
772
773 if (AGGREGATE_TYPE_P (ft) && type_internals_preclude_sra_p (ft, msg))
774 return true;
775 }
776
777 return false;
778
779 case ARRAY_TYPE:
780 et = TREE_TYPE (type);
781
782 if (TYPE_VOLATILE (et))
783 {
784 *msg = "element type is volatile";
785 return true;
786 }
787
788 if (AGGREGATE_TYPE_P (et) && type_internals_preclude_sra_p (et, msg))
789 return true;
790
791 return false;
792
793 default:
794 return false;
795 }
796 }
797
798 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
799 base variable if it is. Return T if it is not an SSA_NAME. */
800
801 static tree
get_ssa_base_param(tree t)802 get_ssa_base_param (tree t)
803 {
804 if (TREE_CODE (t) == SSA_NAME)
805 {
806 if (SSA_NAME_IS_DEFAULT_DEF (t))
807 return SSA_NAME_VAR (t);
808 else
809 return NULL_TREE;
810 }
811 return t;
812 }
813
814 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
815 belongs to, unless the BB has already been marked as a potentially
816 final. */
817
818 static void
mark_parm_dereference(tree base,HOST_WIDE_INT dist,gimple * stmt)819 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple *stmt)
820 {
821 basic_block bb = gimple_bb (stmt);
822 int idx, parm_index = 0;
823 tree parm;
824
825 if (bitmap_bit_p (final_bbs, bb->index))
826 return;
827
828 for (parm = DECL_ARGUMENTS (current_function_decl);
829 parm && parm != base;
830 parm = DECL_CHAIN (parm))
831 parm_index++;
832
833 gcc_assert (parm_index < func_param_count);
834
835 idx = bb->index * func_param_count + parm_index;
836 if (bb_dereferences[idx] < dist)
837 bb_dereferences[idx] = dist;
838 }
839
840 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
841 the three fields. Also add it to the vector of accesses corresponding to
842 the base. Finally, return the new access. */
843
844 static struct access *
create_access_1(tree base,HOST_WIDE_INT offset,HOST_WIDE_INT size)845 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
846 {
847 struct access *access = access_pool.allocate ();
848
849 memset (access, 0, sizeof (struct access));
850 access->base = base;
851 access->offset = offset;
852 access->size = size;
853
854 base_access_vec->get_or_insert (base).safe_push (access);
855
856 return access;
857 }
858
859 static bool maybe_add_sra_candidate (tree);
860
861 /* Create and insert access for EXPR. Return created access, or NULL if it is
862 not possible. Also scan for uses of constant pool as we go along and add
863 to candidates. */
864
865 static struct access *
create_access(tree expr,gimple * stmt,bool write)866 create_access (tree expr, gimple *stmt, bool write)
867 {
868 struct access *access;
869 poly_int64 poffset, psize, pmax_size;
870 HOST_WIDE_INT offset, size, max_size;
871 tree base = expr;
872 bool reverse, ptr, unscalarizable_region = false;
873
874 base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
875 &reverse);
876 if (!poffset.is_constant (&offset)
877 || !psize.is_constant (&size)
878 || !pmax_size.is_constant (&max_size))
879 {
880 disqualify_candidate (base, "Encountered a polynomial-sized access.");
881 return NULL;
882 }
883
884 if (sra_mode == SRA_MODE_EARLY_IPA
885 && TREE_CODE (base) == MEM_REF)
886 {
887 base = get_ssa_base_param (TREE_OPERAND (base, 0));
888 if (!base)
889 return NULL;
890 ptr = true;
891 }
892 else
893 ptr = false;
894
895 /* For constant-pool entries, check we can substitute the constant value. */
896 if (constant_decl_p (base)
897 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA))
898 {
899 gcc_assert (!bitmap_bit_p (disqualified_constants, DECL_UID (base)));
900 if (expr != base
901 && !is_gimple_reg_type (TREE_TYPE (expr))
902 && dump_file && (dump_flags & TDF_DETAILS))
903 {
904 /* This occurs in Ada with accesses to ARRAY_RANGE_REFs,
905 and elements of multidimensional arrays (which are
906 multi-element arrays in their own right). */
907 fprintf (dump_file, "Allowing non-reg-type load of part"
908 " of constant-pool entry: ");
909 print_generic_expr (dump_file, expr);
910 }
911 maybe_add_sra_candidate (base);
912 }
913
914 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
915 return NULL;
916
917 if (sra_mode == SRA_MODE_EARLY_IPA)
918 {
919 if (size < 0 || size != max_size)
920 {
921 disqualify_candidate (base, "Encountered a variable sized access.");
922 return NULL;
923 }
924 if (TREE_CODE (expr) == COMPONENT_REF
925 && DECL_BIT_FIELD (TREE_OPERAND (expr, 1)))
926 {
927 disqualify_candidate (base, "Encountered a bit-field access.");
928 return NULL;
929 }
930 gcc_checking_assert ((offset % BITS_PER_UNIT) == 0);
931
932 if (ptr)
933 mark_parm_dereference (base, offset + size, stmt);
934 }
935 else
936 {
937 if (size != max_size)
938 {
939 size = max_size;
940 unscalarizable_region = true;
941 }
942 if (size < 0)
943 {
944 disqualify_candidate (base, "Encountered an unconstrained access.");
945 return NULL;
946 }
947 }
948
949 access = create_access_1 (base, offset, size);
950 access->expr = expr;
951 access->type = TREE_TYPE (expr);
952 access->write = write;
953 access->grp_unscalarizable_region = unscalarizable_region;
954 access->stmt = stmt;
955 access->reverse = reverse;
956
957 if (TREE_CODE (expr) == COMPONENT_REF
958 && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1)))
959 access->non_addressable = 1;
960
961 return access;
962 }
963
964
965 /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length
966 ARRAY_TYPE with fields that are either of gimple register types (excluding
967 bit-fields) or (recursively) scalarizable types. CONST_DECL must be true if
968 we are considering a decl from constant pool. If it is false, char arrays
969 will be refused. */
970
971 static bool
scalarizable_type_p(tree type,bool const_decl)972 scalarizable_type_p (tree type, bool const_decl)
973 {
974 gcc_assert (!is_gimple_reg_type (type));
975 if (type_contains_placeholder_p (type))
976 return false;
977
978 switch (TREE_CODE (type))
979 {
980 case RECORD_TYPE:
981 for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
982 if (TREE_CODE (fld) == FIELD_DECL)
983 {
984 tree ft = TREE_TYPE (fld);
985
986 if (DECL_BIT_FIELD (fld))
987 return false;
988
989 if (!is_gimple_reg_type (ft)
990 && !scalarizable_type_p (ft, const_decl))
991 return false;
992 }
993
994 return true;
995
996 case ARRAY_TYPE:
997 {
998 HOST_WIDE_INT min_elem_size;
999 if (const_decl)
1000 min_elem_size = 0;
1001 else
1002 min_elem_size = BITS_PER_UNIT;
1003
1004 if (TYPE_DOMAIN (type) == NULL_TREE
1005 || !tree_fits_shwi_p (TYPE_SIZE (type))
1006 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1007 || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1008 || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1009 return false;
1010 if (tree_to_shwi (TYPE_SIZE (type)) == 0
1011 && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1012 /* Zero-element array, should not prevent scalarization. */
1013 ;
1014 else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1015 || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1016 /* Variable-length array, do not allow scalarization. */
1017 return false;
1018
1019 tree elem = TREE_TYPE (type);
1020 if (!is_gimple_reg_type (elem)
1021 && !scalarizable_type_p (elem, const_decl))
1022 return false;
1023 return true;
1024 }
1025 default:
1026 return false;
1027 }
1028 }
1029
1030 static void scalarize_elem (tree, HOST_WIDE_INT, HOST_WIDE_INT, bool, tree, tree);
1031
1032 /* Create total_scalarization accesses for all scalar fields of a member
1033 of type DECL_TYPE conforming to scalarizable_type_p. BASE
1034 must be the top-most VAR_DECL representing the variable; within that,
1035 OFFSET locates the member and REF must be the memory reference expression for
1036 the member. */
1037
1038 static void
completely_scalarize(tree base,tree decl_type,HOST_WIDE_INT offset,tree ref)1039 completely_scalarize (tree base, tree decl_type, HOST_WIDE_INT offset, tree ref)
1040 {
1041 switch (TREE_CODE (decl_type))
1042 {
1043 case RECORD_TYPE:
1044 for (tree fld = TYPE_FIELDS (decl_type); fld; fld = DECL_CHAIN (fld))
1045 if (TREE_CODE (fld) == FIELD_DECL)
1046 {
1047 HOST_WIDE_INT pos = offset + int_bit_position (fld);
1048 tree ft = TREE_TYPE (fld);
1049 tree nref = build3 (COMPONENT_REF, ft, ref, fld, NULL_TREE);
1050
1051 scalarize_elem (base, pos, tree_to_uhwi (DECL_SIZE (fld)),
1052 TYPE_REVERSE_STORAGE_ORDER (decl_type),
1053 nref, ft);
1054 }
1055 break;
1056 case ARRAY_TYPE:
1057 {
1058 tree elemtype = TREE_TYPE (decl_type);
1059 tree elem_size = TYPE_SIZE (elemtype);
1060 gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
1061 HOST_WIDE_INT el_size = tree_to_shwi (elem_size);
1062 gcc_assert (el_size > 0);
1063
1064 tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (decl_type));
1065 gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1066 tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (decl_type));
1067 /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1068 if (maxidx)
1069 {
1070 gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1071 tree domain = TYPE_DOMAIN (decl_type);
1072 /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1073 DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1074 offset_int idx = wi::to_offset (minidx);
1075 offset_int max = wi::to_offset (maxidx);
1076 if (!TYPE_UNSIGNED (domain))
1077 {
1078 idx = wi::sext (idx, TYPE_PRECISION (domain));
1079 max = wi::sext (max, TYPE_PRECISION (domain));
1080 }
1081 for (int el_off = offset; idx <= max; ++idx)
1082 {
1083 tree nref = build4 (ARRAY_REF, elemtype,
1084 ref,
1085 wide_int_to_tree (domain, idx),
1086 NULL_TREE, NULL_TREE);
1087 scalarize_elem (base, el_off, el_size,
1088 TYPE_REVERSE_STORAGE_ORDER (decl_type),
1089 nref, elemtype);
1090 el_off += el_size;
1091 }
1092 }
1093 }
1094 break;
1095 default:
1096 gcc_unreachable ();
1097 }
1098 }
1099
1100 /* Create total_scalarization accesses for a member of type TYPE, which must
1101 satisfy either is_gimple_reg_type or scalarizable_type_p. BASE must be the
1102 top-most VAR_DECL representing the variable; within that, POS and SIZE locate
1103 the member, REVERSE gives its torage order. and REF must be the reference
1104 expression for it. */
1105
1106 static void
scalarize_elem(tree base,HOST_WIDE_INT pos,HOST_WIDE_INT size,bool reverse,tree ref,tree type)1107 scalarize_elem (tree base, HOST_WIDE_INT pos, HOST_WIDE_INT size, bool reverse,
1108 tree ref, tree type)
1109 {
1110 if (is_gimple_reg_type (type))
1111 {
1112 struct access *access = create_access_1 (base, pos, size);
1113 access->expr = ref;
1114 access->type = type;
1115 access->grp_total_scalarization = 1;
1116 access->reverse = reverse;
1117 /* Accesses for intraprocedural SRA can have their stmt NULL. */
1118 }
1119 else
1120 completely_scalarize (base, type, pos, ref);
1121 }
1122
1123 /* Create a total_scalarization access for VAR as a whole. VAR must be of a
1124 RECORD_TYPE or ARRAY_TYPE conforming to scalarizable_type_p. */
1125
1126 static void
create_total_scalarization_access(tree var)1127 create_total_scalarization_access (tree var)
1128 {
1129 HOST_WIDE_INT size = tree_to_uhwi (DECL_SIZE (var));
1130 struct access *access;
1131
1132 access = create_access_1 (var, 0, size);
1133 access->expr = var;
1134 access->type = TREE_TYPE (var);
1135 access->grp_total_scalarization = 1;
1136 }
1137
1138 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1139
1140 static inline bool
contains_view_convert_expr_p(const_tree ref)1141 contains_view_convert_expr_p (const_tree ref)
1142 {
1143 while (handled_component_p (ref))
1144 {
1145 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1146 return true;
1147 ref = TREE_OPERAND (ref, 0);
1148 }
1149
1150 return false;
1151 }
1152
1153 /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1154 bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1155 it points to will be set if REF contains any of the above or a MEM_REF
1156 expression that effectively performs type conversion. */
1157
1158 static bool
1159 contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1160 {
1161 while (handled_component_p (ref))
1162 {
1163 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1164 || (TREE_CODE (ref) == COMPONENT_REF
1165 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1166 {
1167 if (type_changing_p)
1168 *type_changing_p = true;
1169 return true;
1170 }
1171 ref = TREE_OPERAND (ref, 0);
1172 }
1173
1174 if (!type_changing_p
1175 || TREE_CODE (ref) != MEM_REF
1176 || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1177 return false;
1178
1179 tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1180 if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1181 != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1182 *type_changing_p = true;
1183
1184 return false;
1185 }
1186
1187 /* Search the given tree for a declaration by skipping handled components and
1188 exclude it from the candidates. */
1189
1190 static void
disqualify_base_of_expr(tree t,const char * reason)1191 disqualify_base_of_expr (tree t, const char *reason)
1192 {
1193 t = get_base_address (t);
1194 if (sra_mode == SRA_MODE_EARLY_IPA
1195 && TREE_CODE (t) == MEM_REF)
1196 t = get_ssa_base_param (TREE_OPERAND (t, 0));
1197
1198 if (t && DECL_P (t))
1199 disqualify_candidate (t, reason);
1200 }
1201
1202 /* Scan expression EXPR and create access structures for all accesses to
1203 candidates for scalarization. Return the created access or NULL if none is
1204 created. */
1205
1206 static struct access *
build_access_from_expr_1(tree expr,gimple * stmt,bool write)1207 build_access_from_expr_1 (tree expr, gimple *stmt, bool write)
1208 {
1209 struct access *ret = NULL;
1210 bool partial_ref;
1211
1212 if (TREE_CODE (expr) == BIT_FIELD_REF
1213 || TREE_CODE (expr) == IMAGPART_EXPR
1214 || TREE_CODE (expr) == REALPART_EXPR)
1215 {
1216 expr = TREE_OPERAND (expr, 0);
1217 partial_ref = true;
1218 }
1219 else
1220 partial_ref = false;
1221
1222 if (storage_order_barrier_p (expr))
1223 {
1224 disqualify_base_of_expr (expr, "storage order barrier.");
1225 return NULL;
1226 }
1227
1228 /* We need to dive through V_C_Es in order to get the size of its parameter
1229 and not the result type. Ada produces such statements. We are also
1230 capable of handling the topmost V_C_E but not any of those buried in other
1231 handled components. */
1232 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
1233 expr = TREE_OPERAND (expr, 0);
1234
1235 if (contains_view_convert_expr_p (expr))
1236 {
1237 disqualify_base_of_expr (expr, "V_C_E under a different handled "
1238 "component.");
1239 return NULL;
1240 }
1241 if (TREE_THIS_VOLATILE (expr))
1242 {
1243 disqualify_base_of_expr (expr, "part of a volatile reference.");
1244 return NULL;
1245 }
1246
1247 switch (TREE_CODE (expr))
1248 {
1249 case MEM_REF:
1250 if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR
1251 && sra_mode != SRA_MODE_EARLY_IPA)
1252 return NULL;
1253 /* fall through */
1254 case VAR_DECL:
1255 case PARM_DECL:
1256 case RESULT_DECL:
1257 case COMPONENT_REF:
1258 case ARRAY_REF:
1259 case ARRAY_RANGE_REF:
1260 ret = create_access (expr, stmt, write);
1261 break;
1262
1263 default:
1264 break;
1265 }
1266
1267 if (write && partial_ref && ret)
1268 ret->grp_partial_lhs = 1;
1269
1270 return ret;
1271 }
1272
1273 /* Scan expression EXPR and create access structures for all accesses to
1274 candidates for scalarization. Return true if any access has been inserted.
1275 STMT must be the statement from which the expression is taken, WRITE must be
1276 true if the expression is a store and false otherwise. */
1277
1278 static bool
build_access_from_expr(tree expr,gimple * stmt,bool write)1279 build_access_from_expr (tree expr, gimple *stmt, bool write)
1280 {
1281 struct access *access;
1282
1283 access = build_access_from_expr_1 (expr, stmt, write);
1284 if (access)
1285 {
1286 /* This means the aggregate is accesses as a whole in a way other than an
1287 assign statement and thus cannot be removed even if we had a scalar
1288 replacement for everything. */
1289 if (cannot_scalarize_away_bitmap)
1290 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1291 return true;
1292 }
1293 return false;
1294 }
1295
1296 /* Return the single non-EH successor edge of BB or NULL if there is none or
1297 more than one. */
1298
1299 static edge
single_non_eh_succ(basic_block bb)1300 single_non_eh_succ (basic_block bb)
1301 {
1302 edge e, res = NULL;
1303 edge_iterator ei;
1304
1305 FOR_EACH_EDGE (e, ei, bb->succs)
1306 if (!(e->flags & EDGE_EH))
1307 {
1308 if (res)
1309 return NULL;
1310 res = e;
1311 }
1312
1313 return res;
1314 }
1315
1316 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1317 there is no alternative spot where to put statements SRA might need to
1318 generate after it. The spot we are looking for is an edge leading to a
1319 single non-EH successor, if it exists and is indeed single. RHS may be
1320 NULL, in that case ignore it. */
1321
1322 static bool
disqualify_if_bad_bb_terminating_stmt(gimple * stmt,tree lhs,tree rhs)1323 disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1324 {
1325 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1326 && stmt_ends_bb_p (stmt))
1327 {
1328 if (single_non_eh_succ (gimple_bb (stmt)))
1329 return false;
1330
1331 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1332 if (rhs)
1333 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1334 return true;
1335 }
1336 return false;
1337 }
1338
1339 /* Return true if the nature of BASE is such that it contains data even if
1340 there is no write to it in the function. */
1341
1342 static bool
comes_initialized_p(tree base)1343 comes_initialized_p (tree base)
1344 {
1345 return TREE_CODE (base) == PARM_DECL || constant_decl_p (base);
1346 }
1347
1348 /* Scan expressions occurring in STMT, create access structures for all accesses
1349 to candidates for scalarization and remove those candidates which occur in
1350 statements or expressions that prevent them from being split apart. Return
1351 true if any access has been inserted. */
1352
1353 static bool
build_accesses_from_assign(gimple * stmt)1354 build_accesses_from_assign (gimple *stmt)
1355 {
1356 tree lhs, rhs;
1357 struct access *lacc, *racc;
1358
1359 if (!gimple_assign_single_p (stmt)
1360 /* Scope clobbers don't influence scalarization. */
1361 || gimple_clobber_p (stmt))
1362 return false;
1363
1364 lhs = gimple_assign_lhs (stmt);
1365 rhs = gimple_assign_rhs1 (stmt);
1366
1367 if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1368 return false;
1369
1370 racc = build_access_from_expr_1 (rhs, stmt, false);
1371 lacc = build_access_from_expr_1 (lhs, stmt, true);
1372
1373 if (lacc)
1374 {
1375 lacc->grp_assignment_write = 1;
1376 if (storage_order_barrier_p (rhs))
1377 lacc->grp_unscalarizable_region = 1;
1378
1379 if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1380 {
1381 bool type_changing_p = false;
1382 contains_vce_or_bfcref_p (lhs, &type_changing_p);
1383 if (type_changing_p)
1384 bitmap_set_bit (cannot_scalarize_away_bitmap,
1385 DECL_UID (lacc->base));
1386 }
1387 }
1388
1389 if (racc)
1390 {
1391 racc->grp_assignment_read = 1;
1392 if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1393 {
1394 bool type_changing_p = false;
1395 contains_vce_or_bfcref_p (rhs, &type_changing_p);
1396
1397 if (type_changing_p || gimple_has_volatile_ops (stmt))
1398 bitmap_set_bit (cannot_scalarize_away_bitmap,
1399 DECL_UID (racc->base));
1400 else
1401 bitmap_set_bit (should_scalarize_away_bitmap,
1402 DECL_UID (racc->base));
1403 }
1404 if (storage_order_barrier_p (lhs))
1405 racc->grp_unscalarizable_region = 1;
1406 }
1407
1408 if (lacc && racc
1409 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1410 && !lacc->grp_unscalarizable_region
1411 && !racc->grp_unscalarizable_region
1412 && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1413 && lacc->size == racc->size
1414 && useless_type_conversion_p (lacc->type, racc->type))
1415 {
1416 struct assign_link *link;
1417
1418 link = assign_link_pool.allocate ();
1419 memset (link, 0, sizeof (struct assign_link));
1420
1421 link->lacc = lacc;
1422 link->racc = racc;
1423 add_link_to_rhs (racc, link);
1424 add_access_to_work_queue (racc);
1425
1426 /* Let's delay marking the areas as written until propagation of accesses
1427 across link, unless the nature of rhs tells us that its data comes
1428 from elsewhere. */
1429 if (!comes_initialized_p (racc->base))
1430 lacc->write = false;
1431 }
1432
1433 return lacc || racc;
1434 }
1435
1436 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1437 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
1438
1439 static bool
asm_visit_addr(gimple *,tree op,tree,void *)1440 asm_visit_addr (gimple *, tree op, tree, void *)
1441 {
1442 op = get_base_address (op);
1443 if (op
1444 && DECL_P (op))
1445 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1446
1447 return false;
1448 }
1449
1450 /* Return true iff callsite CALL has at least as many actual arguments as there
1451 are formal parameters of the function currently processed by IPA-SRA and
1452 that their types match. */
1453
1454 static inline bool
callsite_arguments_match_p(gimple * call)1455 callsite_arguments_match_p (gimple *call)
1456 {
1457 if (gimple_call_num_args (call) < (unsigned) func_param_count)
1458 return false;
1459
1460 tree parm;
1461 int i;
1462 for (parm = DECL_ARGUMENTS (current_function_decl), i = 0;
1463 parm;
1464 parm = DECL_CHAIN (parm), i++)
1465 {
1466 tree arg = gimple_call_arg (call, i);
1467 if (!useless_type_conversion_p (TREE_TYPE (parm), TREE_TYPE (arg)))
1468 return false;
1469 }
1470 return true;
1471 }
1472
1473 /* Scan function and look for interesting expressions and create access
1474 structures for them. Return true iff any access is created. */
1475
1476 static bool
scan_function(void)1477 scan_function (void)
1478 {
1479 basic_block bb;
1480 bool ret = false;
1481
1482 FOR_EACH_BB_FN (bb, cfun)
1483 {
1484 gimple_stmt_iterator gsi;
1485 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1486 {
1487 gimple *stmt = gsi_stmt (gsi);
1488 tree t;
1489 unsigned i;
1490
1491 if (final_bbs && stmt_can_throw_external (stmt))
1492 bitmap_set_bit (final_bbs, bb->index);
1493 switch (gimple_code (stmt))
1494 {
1495 case GIMPLE_RETURN:
1496 t = gimple_return_retval (as_a <greturn *> (stmt));
1497 if (t != NULL_TREE)
1498 ret |= build_access_from_expr (t, stmt, false);
1499 if (final_bbs)
1500 bitmap_set_bit (final_bbs, bb->index);
1501 break;
1502
1503 case GIMPLE_ASSIGN:
1504 ret |= build_accesses_from_assign (stmt);
1505 break;
1506
1507 case GIMPLE_CALL:
1508 for (i = 0; i < gimple_call_num_args (stmt); i++)
1509 ret |= build_access_from_expr (gimple_call_arg (stmt, i),
1510 stmt, false);
1511
1512 if (sra_mode == SRA_MODE_EARLY_IPA)
1513 {
1514 tree dest = gimple_call_fndecl (stmt);
1515 int flags = gimple_call_flags (stmt);
1516
1517 if (dest)
1518 {
1519 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1520 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1521 encountered_apply_args = true;
1522 if (recursive_call_p (current_function_decl, dest))
1523 {
1524 encountered_recursive_call = true;
1525 if (!callsite_arguments_match_p (stmt))
1526 encountered_unchangable_recursive_call = true;
1527 }
1528 }
1529
1530 if (final_bbs
1531 && (flags & (ECF_CONST | ECF_PURE)) == 0)
1532 bitmap_set_bit (final_bbs, bb->index);
1533 }
1534
1535 t = gimple_call_lhs (stmt);
1536 if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
1537 ret |= build_access_from_expr (t, stmt, true);
1538 break;
1539
1540 case GIMPLE_ASM:
1541 {
1542 gasm *asm_stmt = as_a <gasm *> (stmt);
1543 walk_stmt_load_store_addr_ops (asm_stmt, NULL, NULL, NULL,
1544 asm_visit_addr);
1545 if (final_bbs)
1546 bitmap_set_bit (final_bbs, bb->index);
1547
1548 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1549 {
1550 t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1551 ret |= build_access_from_expr (t, asm_stmt, false);
1552 }
1553 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1554 {
1555 t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1556 ret |= build_access_from_expr (t, asm_stmt, true);
1557 }
1558 }
1559 break;
1560
1561 default:
1562 break;
1563 }
1564 }
1565 }
1566
1567 return ret;
1568 }
1569
1570 /* Helper of QSORT function. There are pointers to accesses in the array. An
1571 access is considered smaller than another if it has smaller offset or if the
1572 offsets are the same but is size is bigger. */
1573
1574 static int
compare_access_positions(const void * a,const void * b)1575 compare_access_positions (const void *a, const void *b)
1576 {
1577 const access_p *fp1 = (const access_p *) a;
1578 const access_p *fp2 = (const access_p *) b;
1579 const access_p f1 = *fp1;
1580 const access_p f2 = *fp2;
1581
1582 if (f1->offset != f2->offset)
1583 return f1->offset < f2->offset ? -1 : 1;
1584
1585 if (f1->size == f2->size)
1586 {
1587 if (f1->type == f2->type)
1588 return 0;
1589 /* Put any non-aggregate type before any aggregate type. */
1590 else if (!is_gimple_reg_type (f1->type)
1591 && is_gimple_reg_type (f2->type))
1592 return 1;
1593 else if (is_gimple_reg_type (f1->type)
1594 && !is_gimple_reg_type (f2->type))
1595 return -1;
1596 /* Put any complex or vector type before any other scalar type. */
1597 else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1598 && TREE_CODE (f1->type) != VECTOR_TYPE
1599 && (TREE_CODE (f2->type) == COMPLEX_TYPE
1600 || TREE_CODE (f2->type) == VECTOR_TYPE))
1601 return 1;
1602 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1603 || TREE_CODE (f1->type) == VECTOR_TYPE)
1604 && TREE_CODE (f2->type) != COMPLEX_TYPE
1605 && TREE_CODE (f2->type) != VECTOR_TYPE)
1606 return -1;
1607 /* Put any integral type before any non-integral type. When splicing, we
1608 make sure that those with insufficient precision and occupying the
1609 same space are not scalarized. */
1610 else if (INTEGRAL_TYPE_P (f1->type)
1611 && !INTEGRAL_TYPE_P (f2->type))
1612 return -1;
1613 else if (!INTEGRAL_TYPE_P (f1->type)
1614 && INTEGRAL_TYPE_P (f2->type))
1615 return 1;
1616 /* Put the integral type with the bigger precision first. */
1617 else if (INTEGRAL_TYPE_P (f1->type)
1618 && INTEGRAL_TYPE_P (f2->type)
1619 && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1620 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1621 /* Stabilize the sort. */
1622 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1623 }
1624
1625 /* We want the bigger accesses first, thus the opposite operator in the next
1626 line: */
1627 return f1->size > f2->size ? -1 : 1;
1628 }
1629
1630
1631 /* Append a name of the declaration to the name obstack. A helper function for
1632 make_fancy_name. */
1633
1634 static void
make_fancy_decl_name(tree decl)1635 make_fancy_decl_name (tree decl)
1636 {
1637 char buffer[32];
1638
1639 tree name = DECL_NAME (decl);
1640 if (name)
1641 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1642 IDENTIFIER_LENGTH (name));
1643 else
1644 {
1645 sprintf (buffer, "D%u", DECL_UID (decl));
1646 obstack_grow (&name_obstack, buffer, strlen (buffer));
1647 }
1648 }
1649
1650 /* Helper for make_fancy_name. */
1651
1652 static void
make_fancy_name_1(tree expr)1653 make_fancy_name_1 (tree expr)
1654 {
1655 char buffer[32];
1656 tree index;
1657
1658 if (DECL_P (expr))
1659 {
1660 make_fancy_decl_name (expr);
1661 return;
1662 }
1663
1664 switch (TREE_CODE (expr))
1665 {
1666 case COMPONENT_REF:
1667 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1668 obstack_1grow (&name_obstack, '$');
1669 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1670 break;
1671
1672 case ARRAY_REF:
1673 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1674 obstack_1grow (&name_obstack, '$');
1675 /* Arrays with only one element may not have a constant as their
1676 index. */
1677 index = TREE_OPERAND (expr, 1);
1678 if (TREE_CODE (index) != INTEGER_CST)
1679 break;
1680 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1681 obstack_grow (&name_obstack, buffer, strlen (buffer));
1682 break;
1683
1684 case ADDR_EXPR:
1685 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1686 break;
1687
1688 case MEM_REF:
1689 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1690 if (!integer_zerop (TREE_OPERAND (expr, 1)))
1691 {
1692 obstack_1grow (&name_obstack, '$');
1693 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1694 TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1695 obstack_grow (&name_obstack, buffer, strlen (buffer));
1696 }
1697 break;
1698
1699 case BIT_FIELD_REF:
1700 case REALPART_EXPR:
1701 case IMAGPART_EXPR:
1702 gcc_unreachable (); /* we treat these as scalars. */
1703 break;
1704 default:
1705 break;
1706 }
1707 }
1708
1709 /* Create a human readable name for replacement variable of ACCESS. */
1710
1711 static char *
make_fancy_name(tree expr)1712 make_fancy_name (tree expr)
1713 {
1714 make_fancy_name_1 (expr);
1715 obstack_1grow (&name_obstack, '\0');
1716 return XOBFINISH (&name_obstack, char *);
1717 }
1718
1719 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1720 EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1721 something for which get_addr_base_and_unit_offset returns NULL, gsi must
1722 be non-NULL and is used to insert new statements either before or below
1723 the current one as specified by INSERT_AFTER. This function is not capable
1724 of handling bitfields. */
1725
1726 tree
build_ref_for_offset(location_t loc,tree base,poly_int64 offset,bool reverse,tree exp_type,gimple_stmt_iterator * gsi,bool insert_after)1727 build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
1728 bool reverse, tree exp_type, gimple_stmt_iterator *gsi,
1729 bool insert_after)
1730 {
1731 tree prev_base = base;
1732 tree off;
1733 tree mem_ref;
1734 poly_int64 base_offset;
1735 unsigned HOST_WIDE_INT misalign;
1736 unsigned int align;
1737
1738 /* Preserve address-space information. */
1739 addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1740 if (as != TYPE_ADDR_SPACE (exp_type))
1741 exp_type = build_qualified_type (exp_type,
1742 TYPE_QUALS (exp_type)
1743 | ENCODE_QUAL_ADDR_SPACE (as));
1744
1745 poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1746 get_object_alignment_1 (base, &align, &misalign);
1747 base = get_addr_base_and_unit_offset (base, &base_offset);
1748
1749 /* get_addr_base_and_unit_offset returns NULL for references with a variable
1750 offset such as array[var_index]. */
1751 if (!base)
1752 {
1753 gassign *stmt;
1754 tree tmp, addr;
1755
1756 gcc_checking_assert (gsi);
1757 tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1758 addr = build_fold_addr_expr (unshare_expr (prev_base));
1759 STRIP_USELESS_TYPE_CONVERSION (addr);
1760 stmt = gimple_build_assign (tmp, addr);
1761 gimple_set_location (stmt, loc);
1762 if (insert_after)
1763 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1764 else
1765 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1766
1767 off = build_int_cst (reference_alias_ptr_type (prev_base), byte_offset);
1768 base = tmp;
1769 }
1770 else if (TREE_CODE (base) == MEM_REF)
1771 {
1772 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1773 base_offset + byte_offset);
1774 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1775 base = unshare_expr (TREE_OPERAND (base, 0));
1776 }
1777 else
1778 {
1779 off = build_int_cst (reference_alias_ptr_type (prev_base),
1780 base_offset + byte_offset);
1781 base = build_fold_addr_expr (unshare_expr (base));
1782 }
1783
1784 unsigned int align_bound = known_alignment (misalign + offset);
1785 if (align_bound != 0)
1786 align = MIN (align, align_bound);
1787 if (align != TYPE_ALIGN (exp_type))
1788 exp_type = build_aligned_type (exp_type, align);
1789
1790 mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1791 REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1792 if (TREE_THIS_VOLATILE (prev_base))
1793 TREE_THIS_VOLATILE (mem_ref) = 1;
1794 if (TREE_SIDE_EFFECTS (prev_base))
1795 TREE_SIDE_EFFECTS (mem_ref) = 1;
1796 return mem_ref;
1797 }
1798
1799 /* Construct a memory reference to a part of an aggregate BASE at the given
1800 OFFSET and of the same type as MODEL. In case this is a reference to a
1801 bit-field, the function will replicate the last component_ref of model's
1802 expr to access it. GSI and INSERT_AFTER have the same meaning as in
1803 build_ref_for_offset. */
1804
1805 static tree
build_ref_for_model(location_t loc,tree base,HOST_WIDE_INT offset,struct access * model,gimple_stmt_iterator * gsi,bool insert_after)1806 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1807 struct access *model, gimple_stmt_iterator *gsi,
1808 bool insert_after)
1809 {
1810 if (TREE_CODE (model->expr) == COMPONENT_REF
1811 && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
1812 {
1813 /* This access represents a bit-field. */
1814 tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
1815
1816 offset -= int_bit_position (fld);
1817 exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
1818 t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type,
1819 gsi, insert_after);
1820 /* The flag will be set on the record type. */
1821 REF_REVERSE_STORAGE_ORDER (t) = 0;
1822 return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
1823 NULL_TREE);
1824 }
1825 else
1826 return
1827 build_ref_for_offset (loc, base, offset, model->reverse, model->type,
1828 gsi, insert_after);
1829 }
1830
1831 /* Attempt to build a memory reference that we could but into a gimple
1832 debug_bind statement. Similar to build_ref_for_model but punts if it has to
1833 create statements and return s NULL instead. This function also ignores
1834 alignment issues and so its results should never end up in non-debug
1835 statements. */
1836
1837 static tree
build_debug_ref_for_model(location_t loc,tree base,HOST_WIDE_INT offset,struct access * model)1838 build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1839 struct access *model)
1840 {
1841 poly_int64 base_offset;
1842 tree off;
1843
1844 if (TREE_CODE (model->expr) == COMPONENT_REF
1845 && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
1846 return NULL_TREE;
1847
1848 base = get_addr_base_and_unit_offset (base, &base_offset);
1849 if (!base)
1850 return NULL_TREE;
1851 if (TREE_CODE (base) == MEM_REF)
1852 {
1853 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1854 base_offset + offset / BITS_PER_UNIT);
1855 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1856 base = unshare_expr (TREE_OPERAND (base, 0));
1857 }
1858 else
1859 {
1860 off = build_int_cst (reference_alias_ptr_type (base),
1861 base_offset + offset / BITS_PER_UNIT);
1862 base = build_fold_addr_expr (unshare_expr (base));
1863 }
1864
1865 return fold_build2_loc (loc, MEM_REF, model->type, base, off);
1866 }
1867
1868 /* Construct a memory reference consisting of component_refs and array_refs to
1869 a part of an aggregate *RES (which is of type TYPE). The requested part
1870 should have type EXP_TYPE at be the given OFFSET. This function might not
1871 succeed, it returns true when it does and only then *RES points to something
1872 meaningful. This function should be used only to build expressions that we
1873 might need to present to user (e.g. in warnings). In all other situations,
1874 build_ref_for_model or build_ref_for_offset should be used instead. */
1875
1876 static bool
build_user_friendly_ref_for_offset(tree * res,tree type,HOST_WIDE_INT offset,tree exp_type)1877 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
1878 tree exp_type)
1879 {
1880 while (1)
1881 {
1882 tree fld;
1883 tree tr_size, index, minidx;
1884 HOST_WIDE_INT el_size;
1885
1886 if (offset == 0 && exp_type
1887 && types_compatible_p (exp_type, type))
1888 return true;
1889
1890 switch (TREE_CODE (type))
1891 {
1892 case UNION_TYPE:
1893 case QUAL_UNION_TYPE:
1894 case RECORD_TYPE:
1895 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1896 {
1897 HOST_WIDE_INT pos, size;
1898 tree tr_pos, expr, *expr_ptr;
1899
1900 if (TREE_CODE (fld) != FIELD_DECL)
1901 continue;
1902
1903 tr_pos = bit_position (fld);
1904 if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
1905 continue;
1906 pos = tree_to_uhwi (tr_pos);
1907 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1908 tr_size = DECL_SIZE (fld);
1909 if (!tr_size || !tree_fits_uhwi_p (tr_size))
1910 continue;
1911 size = tree_to_uhwi (tr_size);
1912 if (size == 0)
1913 {
1914 if (pos != offset)
1915 continue;
1916 }
1917 else if (pos > offset || (pos + size) <= offset)
1918 continue;
1919
1920 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1921 NULL_TREE);
1922 expr_ptr = &expr;
1923 if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
1924 offset - pos, exp_type))
1925 {
1926 *res = expr;
1927 return true;
1928 }
1929 }
1930 return false;
1931
1932 case ARRAY_TYPE:
1933 tr_size = TYPE_SIZE (TREE_TYPE (type));
1934 if (!tr_size || !tree_fits_uhwi_p (tr_size))
1935 return false;
1936 el_size = tree_to_uhwi (tr_size);
1937
1938 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1939 if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
1940 return false;
1941 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1942 if (!integer_zerop (minidx))
1943 index = int_const_binop (PLUS_EXPR, index, minidx);
1944 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1945 NULL_TREE, NULL_TREE);
1946 offset = offset % el_size;
1947 type = TREE_TYPE (type);
1948 break;
1949
1950 default:
1951 if (offset != 0)
1952 return false;
1953
1954 if (exp_type)
1955 return false;
1956 else
1957 return true;
1958 }
1959 }
1960 }
1961
1962 /* Return true iff TYPE is stdarg va_list type. */
1963
1964 static inline bool
is_va_list_type(tree type)1965 is_va_list_type (tree type)
1966 {
1967 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1968 }
1969
1970 /* Print message to dump file why a variable was rejected. */
1971
1972 static void
reject(tree var,const char * msg)1973 reject (tree var, const char *msg)
1974 {
1975 if (dump_file && (dump_flags & TDF_DETAILS))
1976 {
1977 fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
1978 print_generic_expr (dump_file, var);
1979 fprintf (dump_file, "\n");
1980 }
1981 }
1982
1983 /* Return true if VAR is a candidate for SRA. */
1984
1985 static bool
maybe_add_sra_candidate(tree var)1986 maybe_add_sra_candidate (tree var)
1987 {
1988 tree type = TREE_TYPE (var);
1989 const char *msg;
1990 tree_node **slot;
1991
1992 if (!AGGREGATE_TYPE_P (type))
1993 {
1994 reject (var, "not aggregate");
1995 return false;
1996 }
1997 /* Allow constant-pool entries (that "need to live in memory")
1998 unless we are doing IPA SRA. */
1999 if (needs_to_live_in_memory (var)
2000 && (sra_mode == SRA_MODE_EARLY_IPA || !constant_decl_p (var)))
2001 {
2002 reject (var, "needs to live in memory");
2003 return false;
2004 }
2005 if (TREE_THIS_VOLATILE (var))
2006 {
2007 reject (var, "is volatile");
2008 return false;
2009 }
2010 if (!COMPLETE_TYPE_P (type))
2011 {
2012 reject (var, "has incomplete type");
2013 return false;
2014 }
2015 if (!tree_fits_uhwi_p (TYPE_SIZE (type)))
2016 {
2017 reject (var, "type size not fixed");
2018 return false;
2019 }
2020 if (tree_to_uhwi (TYPE_SIZE (type)) == 0)
2021 {
2022 reject (var, "type size is zero");
2023 return false;
2024 }
2025 if (type_internals_preclude_sra_p (type, &msg))
2026 {
2027 reject (var, msg);
2028 return false;
2029 }
2030 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but
2031 we also want to schedule it rather late. Thus we ignore it in
2032 the early pass. */
2033 (sra_mode == SRA_MODE_EARLY_INTRA
2034 && is_va_list_type (type)))
2035 {
2036 reject (var, "is va_list");
2037 return false;
2038 }
2039
2040 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2041 slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2042 *slot = var;
2043
2044 if (dump_file && (dump_flags & TDF_DETAILS))
2045 {
2046 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
2047 print_generic_expr (dump_file, var);
2048 fprintf (dump_file, "\n");
2049 }
2050
2051 return true;
2052 }
2053
2054 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
2055 those with type which is suitable for scalarization. */
2056
2057 static bool
find_var_candidates(void)2058 find_var_candidates (void)
2059 {
2060 tree var, parm;
2061 unsigned int i;
2062 bool ret = false;
2063
2064 for (parm = DECL_ARGUMENTS (current_function_decl);
2065 parm;
2066 parm = DECL_CHAIN (parm))
2067 ret |= maybe_add_sra_candidate (parm);
2068
2069 FOR_EACH_LOCAL_DECL (cfun, i, var)
2070 {
2071 if (!VAR_P (var))
2072 continue;
2073
2074 ret |= maybe_add_sra_candidate (var);
2075 }
2076
2077 return ret;
2078 }
2079
2080 /* Sort all accesses for the given variable, check for partial overlaps and
2081 return NULL if there are any. If there are none, pick a representative for
2082 each combination of offset and size and create a linked list out of them.
2083 Return the pointer to the first representative and make sure it is the first
2084 one in the vector of accesses. */
2085
2086 static struct access *
sort_and_splice_var_accesses(tree var)2087 sort_and_splice_var_accesses (tree var)
2088 {
2089 int i, j, access_count;
2090 struct access *res, **prev_acc_ptr = &res;
2091 vec<access_p> *access_vec;
2092 bool first = true;
2093 HOST_WIDE_INT low = -1, high = 0;
2094
2095 access_vec = get_base_access_vector (var);
2096 if (!access_vec)
2097 return NULL;
2098 access_count = access_vec->length ();
2099
2100 /* Sort by <OFFSET, SIZE>. */
2101 access_vec->qsort (compare_access_positions);
2102
2103 i = 0;
2104 while (i < access_count)
2105 {
2106 struct access *access = (*access_vec)[i];
2107 bool grp_write = access->write;
2108 bool grp_read = !access->write;
2109 bool grp_scalar_write = access->write
2110 && is_gimple_reg_type (access->type);
2111 bool grp_scalar_read = !access->write
2112 && is_gimple_reg_type (access->type);
2113 bool grp_assignment_read = access->grp_assignment_read;
2114 bool grp_assignment_write = access->grp_assignment_write;
2115 bool multiple_scalar_reads = false;
2116 bool total_scalarization = access->grp_total_scalarization;
2117 bool grp_partial_lhs = access->grp_partial_lhs;
2118 bool first_scalar = is_gimple_reg_type (access->type);
2119 bool unscalarizable_region = access->grp_unscalarizable_region;
2120 bool bf_non_full_precision
2121 = (INTEGRAL_TYPE_P (access->type)
2122 && TYPE_PRECISION (access->type) != access->size
2123 && TREE_CODE (access->expr) == COMPONENT_REF
2124 && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2125
2126 if (first || access->offset >= high)
2127 {
2128 first = false;
2129 low = access->offset;
2130 high = access->offset + access->size;
2131 }
2132 else if (access->offset > low && access->offset + access->size > high)
2133 return NULL;
2134 else
2135 gcc_assert (access->offset >= low
2136 && access->offset + access->size <= high);
2137
2138 j = i + 1;
2139 while (j < access_count)
2140 {
2141 struct access *ac2 = (*access_vec)[j];
2142 if (ac2->offset != access->offset || ac2->size != access->size)
2143 break;
2144 if (ac2->write)
2145 {
2146 grp_write = true;
2147 grp_scalar_write = (grp_scalar_write
2148 || is_gimple_reg_type (ac2->type));
2149 }
2150 else
2151 {
2152 grp_read = true;
2153 if (is_gimple_reg_type (ac2->type))
2154 {
2155 if (grp_scalar_read)
2156 multiple_scalar_reads = true;
2157 else
2158 grp_scalar_read = true;
2159 }
2160 }
2161 grp_assignment_read |= ac2->grp_assignment_read;
2162 grp_assignment_write |= ac2->grp_assignment_write;
2163 grp_partial_lhs |= ac2->grp_partial_lhs;
2164 unscalarizable_region |= ac2->grp_unscalarizable_region;
2165 total_scalarization |= ac2->grp_total_scalarization;
2166 relink_to_new_repr (access, ac2);
2167
2168 /* If there are both aggregate-type and scalar-type accesses with
2169 this combination of size and offset, the comparison function
2170 should have put the scalars first. */
2171 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
2172 /* It also prefers integral types to non-integral. However, when the
2173 precision of the selected type does not span the entire area and
2174 should also be used for a non-integer (i.e. float), we must not
2175 let that happen. Normally analyze_access_subtree expands the type
2176 to cover the entire area but for bit-fields it doesn't. */
2177 if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
2178 {
2179 if (dump_file && (dump_flags & TDF_DETAILS))
2180 {
2181 fprintf (dump_file, "Cannot scalarize the following access "
2182 "because insufficient precision integer type was "
2183 "selected.\n ");
2184 dump_access (dump_file, access, false);
2185 }
2186 unscalarizable_region = true;
2187 }
2188 ac2->group_representative = access;
2189 j++;
2190 }
2191
2192 i = j;
2193
2194 access->group_representative = access;
2195 access->grp_write = grp_write;
2196 access->grp_read = grp_read;
2197 access->grp_scalar_read = grp_scalar_read;
2198 access->grp_scalar_write = grp_scalar_write;
2199 access->grp_assignment_read = grp_assignment_read;
2200 access->grp_assignment_write = grp_assignment_write;
2201 access->grp_hint = total_scalarization
2202 || (multiple_scalar_reads && !constant_decl_p (var));
2203 access->grp_total_scalarization = total_scalarization;
2204 access->grp_partial_lhs = grp_partial_lhs;
2205 access->grp_unscalarizable_region = unscalarizable_region;
2206
2207 *prev_acc_ptr = access;
2208 prev_acc_ptr = &access->next_grp;
2209 }
2210
2211 gcc_assert (res == (*access_vec)[0]);
2212 return res;
2213 }
2214
2215 /* Create a variable for the given ACCESS which determines the type, name and a
2216 few other properties. Return the variable declaration and store it also to
2217 ACCESS->replacement. */
2218
2219 static tree
create_access_replacement(struct access * access)2220 create_access_replacement (struct access *access)
2221 {
2222 tree repl;
2223
2224 if (access->grp_to_be_debug_replaced)
2225 {
2226 repl = create_tmp_var_raw (access->type);
2227 DECL_CONTEXT (repl) = current_function_decl;
2228 }
2229 else
2230 /* Drop any special alignment on the type if it's not on the main
2231 variant. This avoids issues with weirdo ABIs like AAPCS. */
2232 repl = create_tmp_var (build_qualified_type
2233 (TYPE_MAIN_VARIANT (access->type),
2234 TYPE_QUALS (access->type)), "SR");
2235 if (TREE_CODE (access->type) == COMPLEX_TYPE
2236 || TREE_CODE (access->type) == VECTOR_TYPE)
2237 {
2238 if (!access->grp_partial_lhs)
2239 DECL_GIMPLE_REG_P (repl) = 1;
2240 }
2241 else if (access->grp_partial_lhs
2242 && is_gimple_reg_type (access->type))
2243 TREE_ADDRESSABLE (repl) = 1;
2244
2245 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2246 DECL_ARTIFICIAL (repl) = 1;
2247 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2248
2249 if (DECL_NAME (access->base)
2250 && !DECL_IGNORED_P (access->base)
2251 && !DECL_ARTIFICIAL (access->base))
2252 {
2253 char *pretty_name = make_fancy_name (access->expr);
2254 tree debug_expr = unshare_expr_without_location (access->expr), d;
2255 bool fail = false;
2256
2257 DECL_NAME (repl) = get_identifier (pretty_name);
2258 DECL_NAMELESS (repl) = 1;
2259 obstack_free (&name_obstack, pretty_name);
2260
2261 /* Get rid of any SSA_NAMEs embedded in debug_expr,
2262 as DECL_DEBUG_EXPR isn't considered when looking for still
2263 used SSA_NAMEs and thus they could be freed. All debug info
2264 generation cares is whether something is constant or variable
2265 and that get_ref_base_and_extent works properly on the
2266 expression. It cannot handle accesses at a non-constant offset
2267 though, so just give up in those cases. */
2268 for (d = debug_expr;
2269 !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2270 d = TREE_OPERAND (d, 0))
2271 switch (TREE_CODE (d))
2272 {
2273 case ARRAY_REF:
2274 case ARRAY_RANGE_REF:
2275 if (TREE_OPERAND (d, 1)
2276 && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2277 fail = true;
2278 if (TREE_OPERAND (d, 3)
2279 && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2280 fail = true;
2281 /* FALLTHRU */
2282 case COMPONENT_REF:
2283 if (TREE_OPERAND (d, 2)
2284 && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2285 fail = true;
2286 break;
2287 case MEM_REF:
2288 if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2289 fail = true;
2290 else
2291 d = TREE_OPERAND (d, 0);
2292 break;
2293 default:
2294 break;
2295 }
2296 if (!fail)
2297 {
2298 SET_DECL_DEBUG_EXPR (repl, debug_expr);
2299 DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2300 }
2301 if (access->grp_no_warning)
2302 TREE_NO_WARNING (repl) = 1;
2303 else
2304 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
2305 }
2306 else
2307 TREE_NO_WARNING (repl) = 1;
2308
2309 if (dump_file)
2310 {
2311 if (access->grp_to_be_debug_replaced)
2312 {
2313 fprintf (dump_file, "Created a debug-only replacement for ");
2314 print_generic_expr (dump_file, access->base);
2315 fprintf (dump_file, " offset: %u, size: %u\n",
2316 (unsigned) access->offset, (unsigned) access->size);
2317 }
2318 else
2319 {
2320 fprintf (dump_file, "Created a replacement for ");
2321 print_generic_expr (dump_file, access->base);
2322 fprintf (dump_file, " offset: %u, size: %u: ",
2323 (unsigned) access->offset, (unsigned) access->size);
2324 print_generic_expr (dump_file, repl);
2325 fprintf (dump_file, "\n");
2326 }
2327 }
2328 sra_stats.replacements++;
2329
2330 return repl;
2331 }
2332
2333 /* Return ACCESS scalar replacement, which must exist. */
2334
2335 static inline tree
get_access_replacement(struct access * access)2336 get_access_replacement (struct access *access)
2337 {
2338 gcc_checking_assert (access->replacement_decl);
2339 return access->replacement_decl;
2340 }
2341
2342
2343 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2344 linked list along the way. Stop when *ACCESS is NULL or the access pointed
2345 to it is not "within" the root. Return false iff some accesses partially
2346 overlap. */
2347
2348 static bool
build_access_subtree(struct access ** access)2349 build_access_subtree (struct access **access)
2350 {
2351 struct access *root = *access, *last_child = NULL;
2352 HOST_WIDE_INT limit = root->offset + root->size;
2353
2354 *access = (*access)->next_grp;
2355 while (*access && (*access)->offset + (*access)->size <= limit)
2356 {
2357 if (!last_child)
2358 root->first_child = *access;
2359 else
2360 last_child->next_sibling = *access;
2361 last_child = *access;
2362 (*access)->parent = root;
2363 (*access)->grp_write |= root->grp_write;
2364
2365 if (!build_access_subtree (access))
2366 return false;
2367 }
2368
2369 if (*access && (*access)->offset < limit)
2370 return false;
2371
2372 return true;
2373 }
2374
2375 /* Build a tree of access representatives, ACCESS is the pointer to the first
2376 one, others are linked in a list by the next_grp field. Return false iff
2377 some accesses partially overlap. */
2378
2379 static bool
build_access_trees(struct access * access)2380 build_access_trees (struct access *access)
2381 {
2382 while (access)
2383 {
2384 struct access *root = access;
2385
2386 if (!build_access_subtree (&access))
2387 return false;
2388 root->next_grp = access;
2389 }
2390 return true;
2391 }
2392
2393 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2394 array. */
2395
2396 static bool
expr_with_var_bounded_array_refs_p(tree expr)2397 expr_with_var_bounded_array_refs_p (tree expr)
2398 {
2399 while (handled_component_p (expr))
2400 {
2401 if (TREE_CODE (expr) == ARRAY_REF
2402 && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2403 return true;
2404 expr = TREE_OPERAND (expr, 0);
2405 }
2406 return false;
2407 }
2408
2409 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2410 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all
2411 sorts of access flags appropriately along the way, notably always set
2412 grp_read and grp_assign_read according to MARK_READ and grp_write when
2413 MARK_WRITE is true.
2414
2415 Creating a replacement for a scalar access is considered beneficial if its
2416 grp_hint is set (this means we are either attempting total scalarization or
2417 there is more than one direct read access) or according to the following
2418 table:
2419
2420 Access written to through a scalar type (once or more times)
2421 |
2422 | Written to in an assignment statement
2423 | |
2424 | | Access read as scalar _once_
2425 | | |
2426 | | | Read in an assignment statement
2427 | | | |
2428 | | | | Scalarize Comment
2429 -----------------------------------------------------------------------------
2430 0 0 0 0 No access for the scalar
2431 0 0 0 1 No access for the scalar
2432 0 0 1 0 No Single read - won't help
2433 0 0 1 1 No The same case
2434 0 1 0 0 No access for the scalar
2435 0 1 0 1 No access for the scalar
2436 0 1 1 0 Yes s = *g; return s.i;
2437 0 1 1 1 Yes The same case as above
2438 1 0 0 0 No Won't help
2439 1 0 0 1 Yes s.i = 1; *g = s;
2440 1 0 1 0 Yes s.i = 5; g = s.i;
2441 1 0 1 1 Yes The same case as above
2442 1 1 0 0 No Won't help.
2443 1 1 0 1 Yes s.i = 1; *g = s;
2444 1 1 1 0 Yes s = *g; return s.i;
2445 1 1 1 1 Yes Any of the above yeses */
2446
2447 static bool
analyze_access_subtree(struct access * root,struct access * parent,bool allow_replacements)2448 analyze_access_subtree (struct access *root, struct access *parent,
2449 bool allow_replacements)
2450 {
2451 struct access *child;
2452 HOST_WIDE_INT limit = root->offset + root->size;
2453 HOST_WIDE_INT covered_to = root->offset;
2454 bool scalar = is_gimple_reg_type (root->type);
2455 bool hole = false, sth_created = false;
2456
2457 if (parent)
2458 {
2459 if (parent->grp_read)
2460 root->grp_read = 1;
2461 if (parent->grp_assignment_read)
2462 root->grp_assignment_read = 1;
2463 if (parent->grp_write)
2464 root->grp_write = 1;
2465 if (parent->grp_assignment_write)
2466 root->grp_assignment_write = 1;
2467 if (parent->grp_total_scalarization)
2468 root->grp_total_scalarization = 1;
2469 }
2470
2471 if (root->grp_unscalarizable_region)
2472 allow_replacements = false;
2473
2474 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2475 allow_replacements = false;
2476
2477 for (child = root->first_child; child; child = child->next_sibling)
2478 {
2479 hole |= covered_to < child->offset;
2480 sth_created |= analyze_access_subtree (child, root,
2481 allow_replacements && !scalar);
2482
2483 root->grp_unscalarized_data |= child->grp_unscalarized_data;
2484 root->grp_total_scalarization &= child->grp_total_scalarization;
2485 if (child->grp_covered)
2486 covered_to += child->size;
2487 else
2488 hole = true;
2489 }
2490
2491 if (allow_replacements && scalar && !root->first_child
2492 && (root->grp_hint
2493 || ((root->grp_scalar_read || root->grp_assignment_read)
2494 && (root->grp_scalar_write || root->grp_assignment_write))))
2495 {
2496 /* Always create access replacements that cover the whole access.
2497 For integral types this means the precision has to match.
2498 Avoid assumptions based on the integral type kind, too. */
2499 if (INTEGRAL_TYPE_P (root->type)
2500 && (TREE_CODE (root->type) != INTEGER_TYPE
2501 || TYPE_PRECISION (root->type) != root->size)
2502 /* But leave bitfield accesses alone. */
2503 && (TREE_CODE (root->expr) != COMPONENT_REF
2504 || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2505 {
2506 tree rt = root->type;
2507 gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2508 && (root->size % BITS_PER_UNIT) == 0);
2509 root->type = build_nonstandard_integer_type (root->size,
2510 TYPE_UNSIGNED (rt));
2511 root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2512 root->offset, root->reverse,
2513 root->type, NULL, false);
2514
2515 if (dump_file && (dump_flags & TDF_DETAILS))
2516 {
2517 fprintf (dump_file, "Changing the type of a replacement for ");
2518 print_generic_expr (dump_file, root->base);
2519 fprintf (dump_file, " offset: %u, size: %u ",
2520 (unsigned) root->offset, (unsigned) root->size);
2521 fprintf (dump_file, " to an integer.\n");
2522 }
2523 }
2524
2525 root->grp_to_be_replaced = 1;
2526 root->replacement_decl = create_access_replacement (root);
2527 sth_created = true;
2528 hole = false;
2529 }
2530 else
2531 {
2532 if (allow_replacements
2533 && scalar && !root->first_child
2534 && (root->grp_scalar_write || root->grp_assignment_write)
2535 && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2536 DECL_UID (root->base)))
2537 {
2538 gcc_checking_assert (!root->grp_scalar_read
2539 && !root->grp_assignment_read);
2540 sth_created = true;
2541 if (MAY_HAVE_DEBUG_BIND_STMTS)
2542 {
2543 root->grp_to_be_debug_replaced = 1;
2544 root->replacement_decl = create_access_replacement (root);
2545 }
2546 }
2547
2548 if (covered_to < limit)
2549 hole = true;
2550 if (scalar || !allow_replacements)
2551 root->grp_total_scalarization = 0;
2552 }
2553
2554 if (!hole || root->grp_total_scalarization)
2555 root->grp_covered = 1;
2556 else if (root->grp_write || comes_initialized_p (root->base))
2557 root->grp_unscalarized_data = 1; /* not covered and written to */
2558 return sth_created;
2559 }
2560
2561 /* Analyze all access trees linked by next_grp by the means of
2562 analyze_access_subtree. */
2563 static bool
analyze_access_trees(struct access * access)2564 analyze_access_trees (struct access *access)
2565 {
2566 bool ret = false;
2567
2568 while (access)
2569 {
2570 if (analyze_access_subtree (access, NULL, true))
2571 ret = true;
2572 access = access->next_grp;
2573 }
2574
2575 return ret;
2576 }
2577
2578 /* Return true iff a potential new child of LACC at offset OFFSET and with size
2579 SIZE would conflict with an already existing one. If exactly such a child
2580 already exists in LACC, store a pointer to it in EXACT_MATCH. */
2581
2582 static bool
child_would_conflict_in_lacc(struct access * lacc,HOST_WIDE_INT norm_offset,HOST_WIDE_INT size,struct access ** exact_match)2583 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
2584 HOST_WIDE_INT size, struct access **exact_match)
2585 {
2586 struct access *child;
2587
2588 for (child = lacc->first_child; child; child = child->next_sibling)
2589 {
2590 if (child->offset == norm_offset && child->size == size)
2591 {
2592 *exact_match = child;
2593 return true;
2594 }
2595
2596 if (child->offset < norm_offset + size
2597 && child->offset + child->size > norm_offset)
2598 return true;
2599 }
2600
2601 return false;
2602 }
2603
2604 /* Create a new child access of PARENT, with all properties just like MODEL
2605 except for its offset and with its grp_write false and grp_read true.
2606 Return the new access or NULL if it cannot be created. Note that this
2607 access is created long after all splicing and sorting, it's not located in
2608 any access vector and is automatically a representative of its group. Set
2609 the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
2610
2611 static struct access *
create_artificial_child_access(struct access * parent,struct access * model,HOST_WIDE_INT new_offset,bool set_grp_write)2612 create_artificial_child_access (struct access *parent, struct access *model,
2613 HOST_WIDE_INT new_offset,
2614 bool set_grp_write)
2615 {
2616 struct access **child;
2617 tree expr = parent->base;
2618
2619 gcc_assert (!model->grp_unscalarizable_region);
2620
2621 struct access *access = access_pool.allocate ();
2622 memset (access, 0, sizeof (struct access));
2623 if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
2624 model->type))
2625 {
2626 access->grp_no_warning = true;
2627 expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
2628 new_offset, model, NULL, false);
2629 }
2630
2631 access->base = parent->base;
2632 access->expr = expr;
2633 access->offset = new_offset;
2634 access->size = model->size;
2635 access->type = model->type;
2636 access->grp_write = set_grp_write;
2637 access->grp_read = false;
2638 access->reverse = model->reverse;
2639
2640 child = &parent->first_child;
2641 while (*child && (*child)->offset < new_offset)
2642 child = &(*child)->next_sibling;
2643
2644 access->next_sibling = *child;
2645 *child = access;
2646
2647 return access;
2648 }
2649
2650
2651 /* Beginning with ACCESS, traverse its whole access subtree and mark all
2652 sub-trees as written to. If any of them has not been marked so previously
2653 and has assignment links leading from it, re-enqueue it. */
2654
2655 static void
subtree_mark_written_and_enqueue(struct access * access)2656 subtree_mark_written_and_enqueue (struct access *access)
2657 {
2658 if (access->grp_write)
2659 return;
2660 access->grp_write = true;
2661 add_access_to_work_queue (access);
2662
2663 struct access *child;
2664 for (child = access->first_child; child; child = child->next_sibling)
2665 subtree_mark_written_and_enqueue (child);
2666 }
2667
2668 /* Propagate subaccesses and grp_write flags of RACC across an assignment link
2669 to LACC. Enqueue sub-accesses as necessary so that the write flag is
2670 propagated transitively. Return true if anything changed. Additionally, if
2671 RACC is a scalar access but LACC is not, change the type of the latter, if
2672 possible. */
2673
2674 static bool
propagate_subaccesses_across_link(struct access * lacc,struct access * racc)2675 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
2676 {
2677 struct access *rchild;
2678 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
2679 bool ret = false;
2680
2681 /* IF the LHS is still not marked as being written to, we only need to do so
2682 if the RHS at this level actually was. */
2683 if (!lacc->grp_write)
2684 {
2685 gcc_checking_assert (!comes_initialized_p (racc->base));
2686 if (racc->grp_write)
2687 {
2688 subtree_mark_written_and_enqueue (lacc);
2689 ret = true;
2690 }
2691 }
2692
2693 if (is_gimple_reg_type (lacc->type)
2694 || lacc->grp_unscalarizable_region
2695 || racc->grp_unscalarizable_region)
2696 {
2697 if (!lacc->grp_write)
2698 {
2699 ret = true;
2700 subtree_mark_written_and_enqueue (lacc);
2701 }
2702 return ret;
2703 }
2704
2705 if (is_gimple_reg_type (racc->type))
2706 {
2707 if (!lacc->grp_write)
2708 {
2709 ret = true;
2710 subtree_mark_written_and_enqueue (lacc);
2711 }
2712 if (!lacc->first_child && !racc->first_child)
2713 {
2714 tree t = lacc->base;
2715
2716 lacc->type = racc->type;
2717 if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
2718 lacc->offset, racc->type))
2719 lacc->expr = t;
2720 else
2721 {
2722 lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
2723 lacc->base, lacc->offset,
2724 racc, NULL, false);
2725 lacc->grp_no_warning = true;
2726 }
2727 }
2728 return ret;
2729 }
2730
2731 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
2732 {
2733 struct access *new_acc = NULL;
2734 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
2735
2736 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
2737 &new_acc))
2738 {
2739 if (new_acc)
2740 {
2741 if (!new_acc->grp_write && rchild->grp_write)
2742 {
2743 gcc_assert (!lacc->grp_write);
2744 subtree_mark_written_and_enqueue (new_acc);
2745 ret = true;
2746 }
2747
2748 rchild->grp_hint = 1;
2749 new_acc->grp_hint |= new_acc->grp_read;
2750 if (rchild->first_child
2751 && propagate_subaccesses_across_link (new_acc, rchild))
2752 {
2753 ret = 1;
2754 add_access_to_work_queue (new_acc);
2755 }
2756 }
2757 else
2758 {
2759 if (!lacc->grp_write)
2760 {
2761 ret = true;
2762 subtree_mark_written_and_enqueue (lacc);
2763 }
2764 }
2765 continue;
2766 }
2767
2768 if (rchild->grp_unscalarizable_region)
2769 {
2770 if (rchild->grp_write && !lacc->grp_write)
2771 {
2772 ret = true;
2773 subtree_mark_written_and_enqueue (lacc);
2774 }
2775 continue;
2776 }
2777
2778 rchild->grp_hint = 1;
2779 new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
2780 lacc->grp_write
2781 || rchild->grp_write);
2782 gcc_checking_assert (new_acc);
2783 if (racc->first_child)
2784 propagate_subaccesses_across_link (new_acc, rchild);
2785
2786 add_access_to_work_queue (lacc);
2787 ret = true;
2788 }
2789
2790 return ret;
2791 }
2792
2793 /* Propagate all subaccesses across assignment links. */
2794
2795 static void
propagate_all_subaccesses(void)2796 propagate_all_subaccesses (void)
2797 {
2798 while (work_queue_head)
2799 {
2800 struct access *racc = pop_access_from_work_queue ();
2801 struct assign_link *link;
2802
2803 if (racc->group_representative)
2804 racc= racc->group_representative;
2805 gcc_assert (racc->first_link);
2806
2807 for (link = racc->first_link; link; link = link->next)
2808 {
2809 struct access *lacc = link->lacc;
2810
2811 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2812 continue;
2813 lacc = lacc->group_representative;
2814
2815 bool reque_parents = false;
2816 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
2817 {
2818 if (!lacc->grp_write)
2819 {
2820 subtree_mark_written_and_enqueue (lacc);
2821 reque_parents = true;
2822 }
2823 }
2824 else if (propagate_subaccesses_across_link (lacc, racc))
2825 reque_parents = true;
2826
2827 if (reque_parents)
2828 do
2829 {
2830 add_access_to_work_queue (lacc);
2831 lacc = lacc->parent;
2832 }
2833 while (lacc);
2834 }
2835 }
2836 }
2837
2838 /* Go through all accesses collected throughout the (intraprocedural) analysis
2839 stage, exclude overlapping ones, identify representatives and build trees
2840 out of them, making decisions about scalarization on the way. Return true
2841 iff there are any to-be-scalarized variables after this stage. */
2842
2843 static bool
analyze_all_variable_accesses(void)2844 analyze_all_variable_accesses (void)
2845 {
2846 int res = 0;
2847 bitmap tmp = BITMAP_ALLOC (NULL);
2848 bitmap_iterator bi;
2849 unsigned i;
2850 bool optimize_speed_p = !optimize_function_for_size_p (cfun);
2851
2852 enum compiler_param param = optimize_speed_p
2853 ? PARAM_SRA_MAX_SCALARIZATION_SIZE_SPEED
2854 : PARAM_SRA_MAX_SCALARIZATION_SIZE_SIZE;
2855
2856 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
2857 fall back to a target default. */
2858 unsigned HOST_WIDE_INT max_scalarization_size
2859 = global_options_set.x_param_values[param]
2860 ? PARAM_VALUE (param)
2861 : get_move_ratio (optimize_speed_p) * UNITS_PER_WORD;
2862
2863 max_scalarization_size *= BITS_PER_UNIT;
2864
2865 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2866 if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2867 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2868 {
2869 tree var = candidate (i);
2870
2871 if (VAR_P (var) && scalarizable_type_p (TREE_TYPE (var),
2872 constant_decl_p (var)))
2873 {
2874 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var)))
2875 <= max_scalarization_size)
2876 {
2877 create_total_scalarization_access (var);
2878 completely_scalarize (var, TREE_TYPE (var), 0, var);
2879 statistics_counter_event (cfun,
2880 "Totally-scalarized aggregates", 1);
2881 if (dump_file && (dump_flags & TDF_DETAILS))
2882 {
2883 fprintf (dump_file, "Will attempt to totally scalarize ");
2884 print_generic_expr (dump_file, var);
2885 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2886 }
2887 }
2888 else if (dump_file && (dump_flags & TDF_DETAILS))
2889 {
2890 fprintf (dump_file, "Too big to totally scalarize: ");
2891 print_generic_expr (dump_file, var);
2892 fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
2893 }
2894 }
2895 }
2896
2897 bitmap_copy (tmp, candidate_bitmap);
2898 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2899 {
2900 tree var = candidate (i);
2901 struct access *access;
2902
2903 access = sort_and_splice_var_accesses (var);
2904 if (!access || !build_access_trees (access))
2905 disqualify_candidate (var,
2906 "No or inhibitingly overlapping accesses.");
2907 }
2908
2909 propagate_all_subaccesses ();
2910
2911 bitmap_copy (tmp, candidate_bitmap);
2912 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2913 {
2914 tree var = candidate (i);
2915 struct access *access = get_first_repr_for_decl (var);
2916
2917 if (analyze_access_trees (access))
2918 {
2919 res++;
2920 if (dump_file && (dump_flags & TDF_DETAILS))
2921 {
2922 fprintf (dump_file, "\nAccess trees for ");
2923 print_generic_expr (dump_file, var);
2924 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2925 dump_access_tree (dump_file, access);
2926 fprintf (dump_file, "\n");
2927 }
2928 }
2929 else
2930 disqualify_candidate (var, "No scalar replacements to be created.");
2931 }
2932
2933 BITMAP_FREE (tmp);
2934
2935 if (res)
2936 {
2937 statistics_counter_event (cfun, "Scalarized aggregates", res);
2938 return true;
2939 }
2940 else
2941 return false;
2942 }
2943
2944 /* Generate statements copying scalar replacements of accesses within a subtree
2945 into or out of AGG. ACCESS, all its children, siblings and their children
2946 are to be processed. AGG is an aggregate type expression (can be a
2947 declaration but does not have to be, it can for example also be a mem_ref or
2948 a series of handled components). TOP_OFFSET is the offset of the processed
2949 subtree which has to be subtracted from offsets of individual accesses to
2950 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
2951 replacements in the interval <start_offset, start_offset + chunk_size>,
2952 otherwise copy all. GSI is a statement iterator used to place the new
2953 statements. WRITE should be true when the statements should write from AGG
2954 to the replacement and false if vice versa. if INSERT_AFTER is true, new
2955 statements will be added after the current statement in GSI, they will be
2956 added before the statement otherwise. */
2957
2958 static void
generate_subtree_copies(struct access * access,tree agg,HOST_WIDE_INT top_offset,HOST_WIDE_INT start_offset,HOST_WIDE_INT chunk_size,gimple_stmt_iterator * gsi,bool write,bool insert_after,location_t loc)2959 generate_subtree_copies (struct access *access, tree agg,
2960 HOST_WIDE_INT top_offset,
2961 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2962 gimple_stmt_iterator *gsi, bool write,
2963 bool insert_after, location_t loc)
2964 {
2965 /* Never write anything into constant pool decls. See PR70602. */
2966 if (!write && constant_decl_p (agg))
2967 return;
2968 do
2969 {
2970 if (chunk_size && access->offset >= start_offset + chunk_size)
2971 return;
2972
2973 if (access->grp_to_be_replaced
2974 && (chunk_size == 0
2975 || access->offset + access->size > start_offset))
2976 {
2977 tree expr, repl = get_access_replacement (access);
2978 gassign *stmt;
2979
2980 expr = build_ref_for_model (loc, agg, access->offset - top_offset,
2981 access, gsi, insert_after);
2982
2983 if (write)
2984 {
2985 if (access->grp_partial_lhs)
2986 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2987 !insert_after,
2988 insert_after ? GSI_NEW_STMT
2989 : GSI_SAME_STMT);
2990 stmt = gimple_build_assign (repl, expr);
2991 }
2992 else
2993 {
2994 TREE_NO_WARNING (repl) = 1;
2995 if (access->grp_partial_lhs)
2996 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2997 !insert_after,
2998 insert_after ? GSI_NEW_STMT
2999 : GSI_SAME_STMT);
3000 stmt = gimple_build_assign (expr, repl);
3001 }
3002 gimple_set_location (stmt, loc);
3003
3004 if (insert_after)
3005 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3006 else
3007 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3008 update_stmt (stmt);
3009 sra_stats.subtree_copies++;
3010 }
3011 else if (write
3012 && access->grp_to_be_debug_replaced
3013 && (chunk_size == 0
3014 || access->offset + access->size > start_offset))
3015 {
3016 gdebug *ds;
3017 tree drhs = build_debug_ref_for_model (loc, agg,
3018 access->offset - top_offset,
3019 access);
3020 ds = gimple_build_debug_bind (get_access_replacement (access),
3021 drhs, gsi_stmt (*gsi));
3022 if (insert_after)
3023 gsi_insert_after (gsi, ds, GSI_NEW_STMT);
3024 else
3025 gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3026 }
3027
3028 if (access->first_child)
3029 generate_subtree_copies (access->first_child, agg, top_offset,
3030 start_offset, chunk_size, gsi,
3031 write, insert_after, loc);
3032
3033 access = access->next_sibling;
3034 }
3035 while (access);
3036 }
3037
3038 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
3039 root of the subtree to be processed. GSI is the statement iterator used
3040 for inserting statements which are added after the current statement if
3041 INSERT_AFTER is true or before it otherwise. */
3042
3043 static void
init_subtree_with_zero(struct access * access,gimple_stmt_iterator * gsi,bool insert_after,location_t loc)3044 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
3045 bool insert_after, location_t loc)
3046
3047 {
3048 struct access *child;
3049
3050 if (access->grp_to_be_replaced)
3051 {
3052 gassign *stmt;
3053
3054 stmt = gimple_build_assign (get_access_replacement (access),
3055 build_zero_cst (access->type));
3056 if (insert_after)
3057 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3058 else
3059 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3060 update_stmt (stmt);
3061 gimple_set_location (stmt, loc);
3062 }
3063 else if (access->grp_to_be_debug_replaced)
3064 {
3065 gdebug *ds
3066 = gimple_build_debug_bind (get_access_replacement (access),
3067 build_zero_cst (access->type),
3068 gsi_stmt (*gsi));
3069 if (insert_after)
3070 gsi_insert_after (gsi, ds, GSI_NEW_STMT);
3071 else
3072 gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3073 }
3074
3075 for (child = access->first_child; child; child = child->next_sibling)
3076 init_subtree_with_zero (child, gsi, insert_after, loc);
3077 }
3078
3079 /* Clobber all scalar replacements in an access subtree. ACCESS is the
3080 root of the subtree to be processed. GSI is the statement iterator used
3081 for inserting statements which are added after the current statement if
3082 INSERT_AFTER is true or before it otherwise. */
3083
3084 static void
clobber_subtree(struct access * access,gimple_stmt_iterator * gsi,bool insert_after,location_t loc)3085 clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
3086 bool insert_after, location_t loc)
3087
3088 {
3089 struct access *child;
3090
3091 if (access->grp_to_be_replaced)
3092 {
3093 tree rep = get_access_replacement (access);
3094 tree clobber = build_constructor (access->type, NULL);
3095 TREE_THIS_VOLATILE (clobber) = 1;
3096 gimple *stmt = gimple_build_assign (rep, clobber);
3097
3098 if (insert_after)
3099 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3100 else
3101 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3102 update_stmt (stmt);
3103 gimple_set_location (stmt, loc);
3104 }
3105
3106 for (child = access->first_child; child; child = child->next_sibling)
3107 clobber_subtree (child, gsi, insert_after, loc);
3108 }
3109
3110 /* Search for an access representative for the given expression EXPR and
3111 return it or NULL if it cannot be found. */
3112
3113 static struct access *
get_access_for_expr(tree expr)3114 get_access_for_expr (tree expr)
3115 {
3116 poly_int64 poffset, psize, pmax_size;
3117 HOST_WIDE_INT offset, max_size;
3118 tree base;
3119 bool reverse;
3120
3121 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
3122 a different size than the size of its argument and we need the latter
3123 one. */
3124 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3125 expr = TREE_OPERAND (expr, 0);
3126
3127 base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
3128 &reverse);
3129 if (!known_size_p (pmax_size)
3130 || !pmax_size.is_constant (&max_size)
3131 || !poffset.is_constant (&offset)
3132 || !DECL_P (base))
3133 return NULL;
3134
3135 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
3136 return NULL;
3137
3138 return get_var_base_offset_size_access (base, offset, max_size);
3139 }
3140
3141 /* Replace the expression EXPR with a scalar replacement if there is one and
3142 generate other statements to do type conversion or subtree copying if
3143 necessary. GSI is used to place newly created statements, WRITE is true if
3144 the expression is being written to (it is on a LHS of a statement or output
3145 in an assembly statement). */
3146
3147 static bool
sra_modify_expr(tree * expr,gimple_stmt_iterator * gsi,bool write)3148 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
3149 {
3150 location_t loc;
3151 struct access *access;
3152 tree type, bfr, orig_expr;
3153
3154 if (TREE_CODE (*expr) == BIT_FIELD_REF)
3155 {
3156 bfr = *expr;
3157 expr = &TREE_OPERAND (*expr, 0);
3158 }
3159 else
3160 bfr = NULL_TREE;
3161
3162 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
3163 expr = &TREE_OPERAND (*expr, 0);
3164 access = get_access_for_expr (*expr);
3165 if (!access)
3166 return false;
3167 type = TREE_TYPE (*expr);
3168 orig_expr = *expr;
3169
3170 loc = gimple_location (gsi_stmt (*gsi));
3171 gimple_stmt_iterator alt_gsi = gsi_none ();
3172 if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
3173 {
3174 alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
3175 gsi = &alt_gsi;
3176 }
3177
3178 if (access->grp_to_be_replaced)
3179 {
3180 tree repl = get_access_replacement (access);
3181 /* If we replace a non-register typed access simply use the original
3182 access expression to extract the scalar component afterwards.
3183 This happens if scalarizing a function return value or parameter
3184 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
3185 gcc.c-torture/compile/20011217-1.c.
3186
3187 We also want to use this when accessing a complex or vector which can
3188 be accessed as a different type too, potentially creating a need for
3189 type conversion (see PR42196) and when scalarized unions are involved
3190 in assembler statements (see PR42398). */
3191 if (!useless_type_conversion_p (type, access->type))
3192 {
3193 tree ref;
3194
3195 ref = build_ref_for_model (loc, orig_expr, 0, access, gsi, false);
3196
3197 if (write)
3198 {
3199 gassign *stmt;
3200
3201 if (access->grp_partial_lhs)
3202 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
3203 false, GSI_NEW_STMT);
3204 stmt = gimple_build_assign (repl, ref);
3205 gimple_set_location (stmt, loc);
3206 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3207 }
3208 else
3209 {
3210 gassign *stmt;
3211
3212 if (access->grp_partial_lhs)
3213 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3214 true, GSI_SAME_STMT);
3215 stmt = gimple_build_assign (ref, repl);
3216 gimple_set_location (stmt, loc);
3217 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3218 }
3219 }
3220 else
3221 *expr = repl;
3222 sra_stats.exprs++;
3223 }
3224 else if (write && access->grp_to_be_debug_replaced)
3225 {
3226 gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
3227 NULL_TREE,
3228 gsi_stmt (*gsi));
3229 gsi_insert_after (gsi, ds, GSI_NEW_STMT);
3230 }
3231
3232 if (access->first_child)
3233 {
3234 HOST_WIDE_INT start_offset, chunk_size;
3235 if (bfr
3236 && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
3237 && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
3238 {
3239 chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
3240 start_offset = access->offset
3241 + tree_to_uhwi (TREE_OPERAND (bfr, 2));
3242 }
3243 else
3244 start_offset = chunk_size = 0;
3245
3246 generate_subtree_copies (access->first_child, orig_expr, access->offset,
3247 start_offset, chunk_size, gsi, write, write,
3248 loc);
3249 }
3250 return true;
3251 }
3252
3253 /* Where scalar replacements of the RHS have been written to when a replacement
3254 of a LHS of an assigments cannot be direclty loaded from a replacement of
3255 the RHS. */
3256 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
3257 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
3258 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
3259
3260 struct subreplacement_assignment_data
3261 {
3262 /* Offset of the access representing the lhs of the assignment. */
3263 HOST_WIDE_INT left_offset;
3264
3265 /* LHS and RHS of the original assignment. */
3266 tree assignment_lhs, assignment_rhs;
3267
3268 /* Access representing the rhs of the whole assignment. */
3269 struct access *top_racc;
3270
3271 /* Stmt iterator used for statement insertions after the original assignment.
3272 It points to the main GSI used to traverse a BB during function body
3273 modification. */
3274 gimple_stmt_iterator *new_gsi;
3275
3276 /* Stmt iterator used for statement insertions before the original
3277 assignment. Keeps on pointing to the original statement. */
3278 gimple_stmt_iterator old_gsi;
3279
3280 /* Location of the assignment. */
3281 location_t loc;
3282
3283 /* Keeps the information whether we have needed to refresh replacements of
3284 the LHS and from which side of the assignments this takes place. */
3285 enum unscalarized_data_handling refreshed;
3286 };
3287
3288 /* Store all replacements in the access tree rooted in TOP_RACC either to their
3289 base aggregate if there are unscalarized data or directly to LHS of the
3290 statement that is pointed to by GSI otherwise. */
3291
3292 static void
handle_unscalarized_data_in_subtree(struct subreplacement_assignment_data * sad)3293 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
3294 {
3295 tree src;
3296 if (sad->top_racc->grp_unscalarized_data)
3297 {
3298 src = sad->assignment_rhs;
3299 sad->refreshed = SRA_UDH_RIGHT;
3300 }
3301 else
3302 {
3303 src = sad->assignment_lhs;
3304 sad->refreshed = SRA_UDH_LEFT;
3305 }
3306 generate_subtree_copies (sad->top_racc->first_child, src,
3307 sad->top_racc->offset, 0, 0,
3308 &sad->old_gsi, false, false, sad->loc);
3309 }
3310
3311 /* Try to generate statements to load all sub-replacements in an access subtree
3312 formed by children of LACC from scalar replacements in the SAD->top_racc
3313 subtree. If that is not possible, refresh the SAD->top_racc base aggregate
3314 and load the accesses from it. */
3315
3316 static void
load_assign_lhs_subreplacements(struct access * lacc,struct subreplacement_assignment_data * sad)3317 load_assign_lhs_subreplacements (struct access *lacc,
3318 struct subreplacement_assignment_data *sad)
3319 {
3320 for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
3321 {
3322 HOST_WIDE_INT offset;
3323 offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
3324
3325 if (lacc->grp_to_be_replaced)
3326 {
3327 struct access *racc;
3328 gassign *stmt;
3329 tree rhs;
3330
3331 racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
3332 if (racc && racc->grp_to_be_replaced)
3333 {
3334 rhs = get_access_replacement (racc);
3335 if (!useless_type_conversion_p (lacc->type, racc->type))
3336 rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
3337 lacc->type, rhs);
3338
3339 if (racc->grp_partial_lhs && lacc->grp_partial_lhs)
3340 rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
3341 NULL_TREE, true, GSI_SAME_STMT);
3342 }
3343 else
3344 {
3345 /* No suitable access on the right hand side, need to load from
3346 the aggregate. See if we have to update it first... */
3347 if (sad->refreshed == SRA_UDH_NONE)
3348 handle_unscalarized_data_in_subtree (sad);
3349
3350 if (sad->refreshed == SRA_UDH_LEFT)
3351 rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
3352 lacc->offset - sad->left_offset,
3353 lacc, sad->new_gsi, true);
3354 else
3355 rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
3356 lacc->offset - sad->left_offset,
3357 lacc, sad->new_gsi, true);
3358 if (lacc->grp_partial_lhs)
3359 rhs = force_gimple_operand_gsi (sad->new_gsi,
3360 rhs, true, NULL_TREE,
3361 false, GSI_NEW_STMT);
3362 }
3363
3364 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
3365 gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
3366 gimple_set_location (stmt, sad->loc);
3367 update_stmt (stmt);
3368 sra_stats.subreplacements++;
3369 }
3370 else
3371 {
3372 if (sad->refreshed == SRA_UDH_NONE
3373 && lacc->grp_read && !lacc->grp_covered)
3374 handle_unscalarized_data_in_subtree (sad);
3375
3376 if (lacc && lacc->grp_to_be_debug_replaced)
3377 {
3378 gdebug *ds;
3379 tree drhs;
3380 struct access *racc = find_access_in_subtree (sad->top_racc,
3381 offset,
3382 lacc->size);
3383
3384 if (racc && racc->grp_to_be_replaced)
3385 {
3386 if (racc->grp_write || constant_decl_p (racc->base))
3387 drhs = get_access_replacement (racc);
3388 else
3389 drhs = NULL;
3390 }
3391 else if (sad->refreshed == SRA_UDH_LEFT)
3392 drhs = build_debug_ref_for_model (sad->loc, lacc->base,
3393 lacc->offset, lacc);
3394 else if (sad->refreshed == SRA_UDH_RIGHT)
3395 drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
3396 offset, lacc);
3397 else
3398 drhs = NULL_TREE;
3399 if (drhs
3400 && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
3401 drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
3402 lacc->type, drhs);
3403 ds = gimple_build_debug_bind (get_access_replacement (lacc),
3404 drhs, gsi_stmt (sad->old_gsi));
3405 gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
3406 }
3407 }
3408
3409 if (lacc->first_child)
3410 load_assign_lhs_subreplacements (lacc, sad);
3411 }
3412 }
3413
3414 /* Result code for SRA assignment modification. */
3415 enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
3416 SRA_AM_MODIFIED, /* stmt changed but not
3417 removed */
3418 SRA_AM_REMOVED }; /* stmt eliminated */
3419
3420 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
3421 to the assignment and GSI is the statement iterator pointing at it. Returns
3422 the same values as sra_modify_assign. */
3423
3424 static enum assignment_mod_result
sra_modify_constructor_assign(gimple * stmt,gimple_stmt_iterator * gsi)3425 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
3426 {
3427 tree lhs = gimple_assign_lhs (stmt);
3428 struct access *acc = get_access_for_expr (lhs);
3429 if (!acc)
3430 return SRA_AM_NONE;
3431 location_t loc = gimple_location (stmt);
3432
3433 if (gimple_clobber_p (stmt))
3434 {
3435 /* Clobber the replacement variable. */
3436 clobber_subtree (acc, gsi, !acc->grp_covered, loc);
3437 /* Remove clobbers of fully scalarized variables, they are dead. */
3438 if (acc->grp_covered)
3439 {
3440 unlink_stmt_vdef (stmt);
3441 gsi_remove (gsi, true);
3442 release_defs (stmt);
3443 return SRA_AM_REMOVED;
3444 }
3445 else
3446 return SRA_AM_MODIFIED;
3447 }
3448
3449 if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
3450 {
3451 /* I have never seen this code path trigger but if it can happen the
3452 following should handle it gracefully. */
3453 if (access_has_children_p (acc))
3454 generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
3455 true, true, loc);
3456 return SRA_AM_MODIFIED;
3457 }
3458
3459 if (acc->grp_covered)
3460 {
3461 init_subtree_with_zero (acc, gsi, false, loc);
3462 unlink_stmt_vdef (stmt);
3463 gsi_remove (gsi, true);
3464 release_defs (stmt);
3465 return SRA_AM_REMOVED;
3466 }
3467 else
3468 {
3469 init_subtree_with_zero (acc, gsi, true, loc);
3470 return SRA_AM_MODIFIED;
3471 }
3472 }
3473
3474 /* Create and return a new suitable default definition SSA_NAME for RACC which
3475 is an access describing an uninitialized part of an aggregate that is being
3476 loaded. */
3477
3478 static tree
get_repl_default_def_ssa_name(struct access * racc)3479 get_repl_default_def_ssa_name (struct access *racc)
3480 {
3481 gcc_checking_assert (!racc->grp_to_be_replaced
3482 && !racc->grp_to_be_debug_replaced);
3483 if (!racc->replacement_decl)
3484 racc->replacement_decl = create_access_replacement (racc);
3485 return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
3486 }
3487
3488 /* Examine both sides of the assignment statement pointed to by STMT, replace
3489 them with a scalare replacement if there is one and generate copying of
3490 replacements if scalarized aggregates have been used in the assignment. GSI
3491 is used to hold generated statements for type conversions and subtree
3492 copying. */
3493
3494 static enum assignment_mod_result
sra_modify_assign(gimple * stmt,gimple_stmt_iterator * gsi)3495 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
3496 {
3497 struct access *lacc, *racc;
3498 tree lhs, rhs;
3499 bool modify_this_stmt = false;
3500 bool force_gimple_rhs = false;
3501 location_t loc;
3502 gimple_stmt_iterator orig_gsi = *gsi;
3503
3504 if (!gimple_assign_single_p (stmt))
3505 return SRA_AM_NONE;
3506 lhs = gimple_assign_lhs (stmt);
3507 rhs = gimple_assign_rhs1 (stmt);
3508
3509 if (TREE_CODE (rhs) == CONSTRUCTOR)
3510 return sra_modify_constructor_assign (stmt, gsi);
3511
3512 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
3513 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
3514 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
3515 {
3516 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
3517 gsi, false);
3518 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
3519 gsi, true);
3520 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3521 }
3522
3523 lacc = get_access_for_expr (lhs);
3524 racc = get_access_for_expr (rhs);
3525 if (!lacc && !racc)
3526 return SRA_AM_NONE;
3527 /* Avoid modifying initializations of constant-pool replacements. */
3528 if (racc && (racc->replacement_decl == lhs))
3529 return SRA_AM_NONE;
3530
3531 loc = gimple_location (stmt);
3532 if (lacc && lacc->grp_to_be_replaced)
3533 {
3534 lhs = get_access_replacement (lacc);
3535 gimple_assign_set_lhs (stmt, lhs);
3536 modify_this_stmt = true;
3537 if (lacc->grp_partial_lhs)
3538 force_gimple_rhs = true;
3539 sra_stats.exprs++;
3540 }
3541
3542 if (racc && racc->grp_to_be_replaced)
3543 {
3544 rhs = get_access_replacement (racc);
3545 modify_this_stmt = true;
3546 if (racc->grp_partial_lhs)
3547 force_gimple_rhs = true;
3548 sra_stats.exprs++;
3549 }
3550 else if (racc
3551 && !racc->grp_unscalarized_data
3552 && !racc->grp_unscalarizable_region
3553 && TREE_CODE (lhs) == SSA_NAME
3554 && !access_has_replacements_p (racc))
3555 {
3556 rhs = get_repl_default_def_ssa_name (racc);
3557 modify_this_stmt = true;
3558 sra_stats.exprs++;
3559 }
3560
3561 if (modify_this_stmt)
3562 {
3563 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3564 {
3565 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
3566 ??? This should move to fold_stmt which we simply should
3567 call after building a VIEW_CONVERT_EXPR here. */
3568 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
3569 && !contains_bitfld_component_ref_p (lhs))
3570 {
3571 lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
3572 gimple_assign_set_lhs (stmt, lhs);
3573 }
3574 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
3575 && !contains_vce_or_bfcref_p (rhs))
3576 rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
3577
3578 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3579 {
3580 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
3581 rhs);
3582 if (is_gimple_reg_type (TREE_TYPE (lhs))
3583 && TREE_CODE (lhs) != SSA_NAME)
3584 force_gimple_rhs = true;
3585 }
3586 }
3587 }
3588
3589 if (lacc && lacc->grp_to_be_debug_replaced)
3590 {
3591 tree dlhs = get_access_replacement (lacc);
3592 tree drhs = unshare_expr (rhs);
3593 if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
3594 {
3595 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
3596 && !contains_vce_or_bfcref_p (drhs))
3597 drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
3598 if (drhs
3599 && !useless_type_conversion_p (TREE_TYPE (dlhs),
3600 TREE_TYPE (drhs)))
3601 drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
3602 TREE_TYPE (dlhs), drhs);
3603 }
3604 gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
3605 gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3606 }
3607
3608 /* From this point on, the function deals with assignments in between
3609 aggregates when at least one has scalar reductions of some of its
3610 components. There are three possible scenarios: Both the LHS and RHS have
3611 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
3612
3613 In the first case, we would like to load the LHS components from RHS
3614 components whenever possible. If that is not possible, we would like to
3615 read it directly from the RHS (after updating it by storing in it its own
3616 components). If there are some necessary unscalarized data in the LHS,
3617 those will be loaded by the original assignment too. If neither of these
3618 cases happen, the original statement can be removed. Most of this is done
3619 by load_assign_lhs_subreplacements.
3620
3621 In the second case, we would like to store all RHS scalarized components
3622 directly into LHS and if they cover the aggregate completely, remove the
3623 statement too. In the third case, we want the LHS components to be loaded
3624 directly from the RHS (DSE will remove the original statement if it
3625 becomes redundant).
3626
3627 This is a bit complex but manageable when types match and when unions do
3628 not cause confusion in a way that we cannot really load a component of LHS
3629 from the RHS or vice versa (the access representing this level can have
3630 subaccesses that are accessible only through a different union field at a
3631 higher level - different from the one used in the examined expression).
3632 Unions are fun.
3633
3634 Therefore, I specially handle a fourth case, happening when there is a
3635 specific type cast or it is impossible to locate a scalarized subaccess on
3636 the other side of the expression. If that happens, I simply "refresh" the
3637 RHS by storing in it is scalarized components leave the original statement
3638 there to do the copying and then load the scalar replacements of the LHS.
3639 This is what the first branch does. */
3640
3641 if (modify_this_stmt
3642 || gimple_has_volatile_ops (stmt)
3643 || contains_vce_or_bfcref_p (rhs)
3644 || contains_vce_or_bfcref_p (lhs)
3645 || stmt_ends_bb_p (stmt))
3646 {
3647 /* No need to copy into a constant-pool, it comes pre-initialized. */
3648 if (access_has_children_p (racc) && !constant_decl_p (racc->base))
3649 generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
3650 gsi, false, false, loc);
3651 if (access_has_children_p (lacc))
3652 {
3653 gimple_stmt_iterator alt_gsi = gsi_none ();
3654 if (stmt_ends_bb_p (stmt))
3655 {
3656 alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
3657 gsi = &alt_gsi;
3658 }
3659 generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
3660 gsi, true, true, loc);
3661 }
3662 sra_stats.separate_lhs_rhs_handling++;
3663
3664 /* This gimplification must be done after generate_subtree_copies,
3665 lest we insert the subtree copies in the middle of the gimplified
3666 sequence. */
3667 if (force_gimple_rhs)
3668 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
3669 true, GSI_SAME_STMT);
3670 if (gimple_assign_rhs1 (stmt) != rhs)
3671 {
3672 modify_this_stmt = true;
3673 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
3674 gcc_assert (stmt == gsi_stmt (orig_gsi));
3675 }
3676
3677 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3678 }
3679 else
3680 {
3681 if (access_has_children_p (lacc)
3682 && access_has_children_p (racc)
3683 /* When an access represents an unscalarizable region, it usually
3684 represents accesses with variable offset and thus must not be used
3685 to generate new memory accesses. */
3686 && !lacc->grp_unscalarizable_region
3687 && !racc->grp_unscalarizable_region)
3688 {
3689 struct subreplacement_assignment_data sad;
3690
3691 sad.left_offset = lacc->offset;
3692 sad.assignment_lhs = lhs;
3693 sad.assignment_rhs = rhs;
3694 sad.top_racc = racc;
3695 sad.old_gsi = *gsi;
3696 sad.new_gsi = gsi;
3697 sad.loc = gimple_location (stmt);
3698 sad.refreshed = SRA_UDH_NONE;
3699
3700 if (lacc->grp_read && !lacc->grp_covered)
3701 handle_unscalarized_data_in_subtree (&sad);
3702
3703 load_assign_lhs_subreplacements (lacc, &sad);
3704 if (sad.refreshed != SRA_UDH_RIGHT)
3705 {
3706 gsi_next (gsi);
3707 unlink_stmt_vdef (stmt);
3708 gsi_remove (&sad.old_gsi, true);
3709 release_defs (stmt);
3710 sra_stats.deleted++;
3711 return SRA_AM_REMOVED;
3712 }
3713 }
3714 else
3715 {
3716 if (access_has_children_p (racc)
3717 && !racc->grp_unscalarized_data
3718 && TREE_CODE (lhs) != SSA_NAME)
3719 {
3720 if (dump_file)
3721 {
3722 fprintf (dump_file, "Removing load: ");
3723 print_gimple_stmt (dump_file, stmt, 0);
3724 }
3725 generate_subtree_copies (racc->first_child, lhs,
3726 racc->offset, 0, 0, gsi,
3727 false, false, loc);
3728 gcc_assert (stmt == gsi_stmt (*gsi));
3729 unlink_stmt_vdef (stmt);
3730 gsi_remove (gsi, true);
3731 release_defs (stmt);
3732 sra_stats.deleted++;
3733 return SRA_AM_REMOVED;
3734 }
3735 /* Restore the aggregate RHS from its components so the
3736 prevailing aggregate copy does the right thing. */
3737 if (access_has_children_p (racc))
3738 generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
3739 gsi, false, false, loc);
3740 /* Re-load the components of the aggregate copy destination.
3741 But use the RHS aggregate to load from to expose more
3742 optimization opportunities. */
3743 if (access_has_children_p (lacc))
3744 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
3745 0, 0, gsi, true, true, loc);
3746 }
3747
3748 return SRA_AM_NONE;
3749 }
3750 }
3751
3752 /* Set any scalar replacements of values in the constant pool to the initial
3753 value of the constant. (Constant-pool decls like *.LC0 have effectively
3754 been initialized before the program starts, we must do the same for their
3755 replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
3756 the function's entry block. */
3757
3758 static void
initialize_constant_pool_replacements(void)3759 initialize_constant_pool_replacements (void)
3760 {
3761 gimple_seq seq = NULL;
3762 gimple_stmt_iterator gsi = gsi_start (seq);
3763 bitmap_iterator bi;
3764 unsigned i;
3765
3766 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3767 {
3768 tree var = candidate (i);
3769 if (!constant_decl_p (var))
3770 continue;
3771 vec<access_p> *access_vec = get_base_access_vector (var);
3772 if (!access_vec)
3773 continue;
3774 for (unsigned i = 0; i < access_vec->length (); i++)
3775 {
3776 struct access *access = (*access_vec)[i];
3777 if (!access->replacement_decl)
3778 continue;
3779 gassign *stmt
3780 = gimple_build_assign (get_access_replacement (access),
3781 unshare_expr (access->expr));
3782 if (dump_file && (dump_flags & TDF_DETAILS))
3783 {
3784 fprintf (dump_file, "Generating constant initializer: ");
3785 print_gimple_stmt (dump_file, stmt, 0);
3786 fprintf (dump_file, "\n");
3787 }
3788 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
3789 update_stmt (stmt);
3790 }
3791 }
3792
3793 seq = gsi_seq (gsi);
3794 if (seq)
3795 gsi_insert_seq_on_edge_immediate (
3796 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
3797 }
3798
3799 /* Traverse the function body and all modifications as decided in
3800 analyze_all_variable_accesses. Return true iff the CFG has been
3801 changed. */
3802
3803 static bool
sra_modify_function_body(void)3804 sra_modify_function_body (void)
3805 {
3806 bool cfg_changed = false;
3807 basic_block bb;
3808
3809 initialize_constant_pool_replacements ();
3810
3811 FOR_EACH_BB_FN (bb, cfun)
3812 {
3813 gimple_stmt_iterator gsi = gsi_start_bb (bb);
3814 while (!gsi_end_p (gsi))
3815 {
3816 gimple *stmt = gsi_stmt (gsi);
3817 enum assignment_mod_result assign_result;
3818 bool modified = false, deleted = false;
3819 tree *t;
3820 unsigned i;
3821
3822 switch (gimple_code (stmt))
3823 {
3824 case GIMPLE_RETURN:
3825 t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
3826 if (*t != NULL_TREE)
3827 modified |= sra_modify_expr (t, &gsi, false);
3828 break;
3829
3830 case GIMPLE_ASSIGN:
3831 assign_result = sra_modify_assign (stmt, &gsi);
3832 modified |= assign_result == SRA_AM_MODIFIED;
3833 deleted = assign_result == SRA_AM_REMOVED;
3834 break;
3835
3836 case GIMPLE_CALL:
3837 /* Operands must be processed before the lhs. */
3838 for (i = 0; i < gimple_call_num_args (stmt); i++)
3839 {
3840 t = gimple_call_arg_ptr (stmt, i);
3841 modified |= sra_modify_expr (t, &gsi, false);
3842 }
3843
3844 if (gimple_call_lhs (stmt))
3845 {
3846 t = gimple_call_lhs_ptr (stmt);
3847 modified |= sra_modify_expr (t, &gsi, true);
3848 }
3849 break;
3850
3851 case GIMPLE_ASM:
3852 {
3853 gasm *asm_stmt = as_a <gasm *> (stmt);
3854 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
3855 {
3856 t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
3857 modified |= sra_modify_expr (t, &gsi, false);
3858 }
3859 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
3860 {
3861 t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
3862 modified |= sra_modify_expr (t, &gsi, true);
3863 }
3864 }
3865 break;
3866
3867 default:
3868 break;
3869 }
3870
3871 if (modified)
3872 {
3873 update_stmt (stmt);
3874 if (maybe_clean_eh_stmt (stmt)
3875 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
3876 cfg_changed = true;
3877 }
3878 if (!deleted)
3879 gsi_next (&gsi);
3880 }
3881 }
3882
3883 gsi_commit_edge_inserts ();
3884 return cfg_changed;
3885 }
3886
3887 /* Generate statements initializing scalar replacements of parts of function
3888 parameters. */
3889
3890 static void
initialize_parameter_reductions(void)3891 initialize_parameter_reductions (void)
3892 {
3893 gimple_stmt_iterator gsi;
3894 gimple_seq seq = NULL;
3895 tree parm;
3896
3897 gsi = gsi_start (seq);
3898 for (parm = DECL_ARGUMENTS (current_function_decl);
3899 parm;
3900 parm = DECL_CHAIN (parm))
3901 {
3902 vec<access_p> *access_vec;
3903 struct access *access;
3904
3905 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3906 continue;
3907 access_vec = get_base_access_vector (parm);
3908 if (!access_vec)
3909 continue;
3910
3911 for (access = (*access_vec)[0];
3912 access;
3913 access = access->next_grp)
3914 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3915 EXPR_LOCATION (parm));
3916 }
3917
3918 seq = gsi_seq (gsi);
3919 if (seq)
3920 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
3921 }
3922
3923 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
3924 it reveals there are components of some aggregates to be scalarized, it runs
3925 the required transformations. */
3926 static unsigned int
perform_intra_sra(void)3927 perform_intra_sra (void)
3928 {
3929 int ret = 0;
3930 sra_initialize ();
3931
3932 if (!find_var_candidates ())
3933 goto out;
3934
3935 if (!scan_function ())
3936 goto out;
3937
3938 if (!analyze_all_variable_accesses ())
3939 goto out;
3940
3941 if (sra_modify_function_body ())
3942 ret = TODO_update_ssa | TODO_cleanup_cfg;
3943 else
3944 ret = TODO_update_ssa;
3945 initialize_parameter_reductions ();
3946
3947 statistics_counter_event (cfun, "Scalar replacements created",
3948 sra_stats.replacements);
3949 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3950 statistics_counter_event (cfun, "Subtree copy stmts",
3951 sra_stats.subtree_copies);
3952 statistics_counter_event (cfun, "Subreplacement stmts",
3953 sra_stats.subreplacements);
3954 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3955 statistics_counter_event (cfun, "Separate LHS and RHS handling",
3956 sra_stats.separate_lhs_rhs_handling);
3957
3958 out:
3959 sra_deinitialize ();
3960 return ret;
3961 }
3962
3963 /* Perform early intraprocedural SRA. */
3964 static unsigned int
early_intra_sra(void)3965 early_intra_sra (void)
3966 {
3967 sra_mode = SRA_MODE_EARLY_INTRA;
3968 return perform_intra_sra ();
3969 }
3970
3971 /* Perform "late" intraprocedural SRA. */
3972 static unsigned int
late_intra_sra(void)3973 late_intra_sra (void)
3974 {
3975 sra_mode = SRA_MODE_INTRA;
3976 return perform_intra_sra ();
3977 }
3978
3979
3980 static bool
gate_intra_sra(void)3981 gate_intra_sra (void)
3982 {
3983 return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3984 }
3985
3986
3987 namespace {
3988
3989 const pass_data pass_data_sra_early =
3990 {
3991 GIMPLE_PASS, /* type */
3992 "esra", /* name */
3993 OPTGROUP_NONE, /* optinfo_flags */
3994 TV_TREE_SRA, /* tv_id */
3995 ( PROP_cfg | PROP_ssa ), /* properties_required */
3996 0, /* properties_provided */
3997 0, /* properties_destroyed */
3998 0, /* todo_flags_start */
3999 TODO_update_ssa, /* todo_flags_finish */
4000 };
4001
4002 class pass_sra_early : public gimple_opt_pass
4003 {
4004 public:
pass_sra_early(gcc::context * ctxt)4005 pass_sra_early (gcc::context *ctxt)
4006 : gimple_opt_pass (pass_data_sra_early, ctxt)
4007 {}
4008
4009 /* opt_pass methods: */
gate(function *)4010 virtual bool gate (function *) { return gate_intra_sra (); }
execute(function *)4011 virtual unsigned int execute (function *) { return early_intra_sra (); }
4012
4013 }; // class pass_sra_early
4014
4015 } // anon namespace
4016
4017 gimple_opt_pass *
make_pass_sra_early(gcc::context * ctxt)4018 make_pass_sra_early (gcc::context *ctxt)
4019 {
4020 return new pass_sra_early (ctxt);
4021 }
4022
4023 namespace {
4024
4025 const pass_data pass_data_sra =
4026 {
4027 GIMPLE_PASS, /* type */
4028 "sra", /* name */
4029 OPTGROUP_NONE, /* optinfo_flags */
4030 TV_TREE_SRA, /* tv_id */
4031 ( PROP_cfg | PROP_ssa ), /* properties_required */
4032 0, /* properties_provided */
4033 0, /* properties_destroyed */
4034 TODO_update_address_taken, /* todo_flags_start */
4035 TODO_update_ssa, /* todo_flags_finish */
4036 };
4037
4038 class pass_sra : public gimple_opt_pass
4039 {
4040 public:
pass_sra(gcc::context * ctxt)4041 pass_sra (gcc::context *ctxt)
4042 : gimple_opt_pass (pass_data_sra, ctxt)
4043 {}
4044
4045 /* opt_pass methods: */
gate(function *)4046 virtual bool gate (function *) { return gate_intra_sra (); }
execute(function *)4047 virtual unsigned int execute (function *) { return late_intra_sra (); }
4048
4049 }; // class pass_sra
4050
4051 } // anon namespace
4052
4053 gimple_opt_pass *
make_pass_sra(gcc::context * ctxt)4054 make_pass_sra (gcc::context *ctxt)
4055 {
4056 return new pass_sra (ctxt);
4057 }
4058
4059
4060 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
4061 parameter. */
4062
4063 static bool
is_unused_scalar_param(tree parm)4064 is_unused_scalar_param (tree parm)
4065 {
4066 tree name;
4067 return (is_gimple_reg (parm)
4068 && (!(name = ssa_default_def (cfun, parm))
4069 || has_zero_uses (name)));
4070 }
4071
4072 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
4073 examine whether there are any direct or otherwise infeasible ones. If so,
4074 return true, otherwise return false. PARM must be a gimple register with a
4075 non-NULL default definition. */
4076
4077 static bool
ptr_parm_has_direct_uses(tree parm)4078 ptr_parm_has_direct_uses (tree parm)
4079 {
4080 imm_use_iterator ui;
4081 gimple *stmt;
4082 tree name = ssa_default_def (cfun, parm);
4083 bool ret = false;
4084
4085 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
4086 {
4087 int uses_ok = 0;
4088 use_operand_p use_p;
4089
4090 if (is_gimple_debug (stmt))
4091 continue;
4092
4093 /* Valid uses include dereferences on the lhs and the rhs. */
4094 if (gimple_has_lhs (stmt))
4095 {
4096 tree lhs = gimple_get_lhs (stmt);
4097 while (handled_component_p (lhs))
4098 lhs = TREE_OPERAND (lhs, 0);
4099 if (TREE_CODE (lhs) == MEM_REF
4100 && TREE_OPERAND (lhs, 0) == name
4101 && integer_zerop (TREE_OPERAND (lhs, 1))
4102 && types_compatible_p (TREE_TYPE (lhs),
4103 TREE_TYPE (TREE_TYPE (name)))
4104 && !TREE_THIS_VOLATILE (lhs))
4105 uses_ok++;
4106 }
4107 if (gimple_assign_single_p (stmt))
4108 {
4109 tree rhs = gimple_assign_rhs1 (stmt);
4110 while (handled_component_p (rhs))
4111 rhs = TREE_OPERAND (rhs, 0);
4112 if (TREE_CODE (rhs) == MEM_REF
4113 && TREE_OPERAND (rhs, 0) == name
4114 && integer_zerop (TREE_OPERAND (rhs, 1))
4115 && types_compatible_p (TREE_TYPE (rhs),
4116 TREE_TYPE (TREE_TYPE (name)))
4117 && !TREE_THIS_VOLATILE (rhs))
4118 uses_ok++;
4119 }
4120 else if (is_gimple_call (stmt))
4121 {
4122 unsigned i;
4123 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4124 {
4125 tree arg = gimple_call_arg (stmt, i);
4126 while (handled_component_p (arg))
4127 arg = TREE_OPERAND (arg, 0);
4128 if (TREE_CODE (arg) == MEM_REF
4129 && TREE_OPERAND (arg, 0) == name
4130 && integer_zerop (TREE_OPERAND (arg, 1))
4131 && types_compatible_p (TREE_TYPE (arg),
4132 TREE_TYPE (TREE_TYPE (name)))
4133 && !TREE_THIS_VOLATILE (arg))
4134 uses_ok++;
4135 }
4136 }
4137
4138 /* If the number of valid uses does not match the number of
4139 uses in this stmt there is an unhandled use. */
4140 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
4141 --uses_ok;
4142
4143 if (uses_ok != 0)
4144 ret = true;
4145
4146 if (ret)
4147 BREAK_FROM_IMM_USE_STMT (ui);
4148 }
4149
4150 return ret;
4151 }
4152
4153 /* Identify candidates for reduction for IPA-SRA based on their type and mark
4154 them in candidate_bitmap. Note that these do not necessarily include
4155 parameter which are unused and thus can be removed. Return true iff any
4156 such candidate has been found. */
4157
4158 static bool
find_param_candidates(void)4159 find_param_candidates (void)
4160 {
4161 tree parm;
4162 int count = 0;
4163 bool ret = false;
4164 const char *msg;
4165
4166 for (parm = DECL_ARGUMENTS (current_function_decl);
4167 parm;
4168 parm = DECL_CHAIN (parm))
4169 {
4170 tree type = TREE_TYPE (parm);
4171 tree_node **slot;
4172
4173 count++;
4174
4175 if (TREE_THIS_VOLATILE (parm)
4176 || TREE_ADDRESSABLE (parm)
4177 || (!is_gimple_reg_type (type) && is_va_list_type (type)))
4178 continue;
4179
4180 if (is_unused_scalar_param (parm))
4181 {
4182 ret = true;
4183 continue;
4184 }
4185
4186 if (POINTER_TYPE_P (type))
4187 {
4188 type = TREE_TYPE (type);
4189
4190 if (TREE_CODE (type) == FUNCTION_TYPE
4191 || TYPE_VOLATILE (type)
4192 || (TREE_CODE (type) == ARRAY_TYPE
4193 && TYPE_NONALIASED_COMPONENT (type))
4194 || !is_gimple_reg (parm)
4195 || is_va_list_type (type)
4196 || ptr_parm_has_direct_uses (parm))
4197 continue;
4198 }
4199 else if (!AGGREGATE_TYPE_P (type))
4200 continue;
4201
4202 if (!COMPLETE_TYPE_P (type)
4203 || !tree_fits_uhwi_p (TYPE_SIZE (type))
4204 || tree_to_uhwi (TYPE_SIZE (type)) == 0
4205 || (AGGREGATE_TYPE_P (type)
4206 && type_internals_preclude_sra_p (type, &msg)))
4207 continue;
4208
4209 bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
4210 slot = candidates->find_slot_with_hash (parm, DECL_UID (parm), INSERT);
4211 *slot = parm;
4212
4213 ret = true;
4214 if (dump_file && (dump_flags & TDF_DETAILS))
4215 {
4216 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
4217 print_generic_expr (dump_file, parm);
4218 fprintf (dump_file, "\n");
4219 }
4220 }
4221
4222 func_param_count = count;
4223 return ret;
4224 }
4225
4226 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
4227 maybe_modified. */
4228
4229 static bool
mark_maybe_modified(ao_ref * ao ATTRIBUTE_UNUSED,tree vdef ATTRIBUTE_UNUSED,void * data)4230 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
4231 void *data)
4232 {
4233 struct access *repr = (struct access *) data;
4234
4235 repr->grp_maybe_modified = 1;
4236 return true;
4237 }
4238
4239 /* Analyze what representatives (in linked lists accessible from
4240 REPRESENTATIVES) can be modified by side effects of statements in the
4241 current function. */
4242
4243 static void
analyze_modified_params(vec<access_p> representatives)4244 analyze_modified_params (vec<access_p> representatives)
4245 {
4246 int i;
4247
4248 for (i = 0; i < func_param_count; i++)
4249 {
4250 struct access *repr;
4251
4252 for (repr = representatives[i];
4253 repr;
4254 repr = repr->next_grp)
4255 {
4256 struct access *access;
4257 bitmap visited;
4258 ao_ref ar;
4259
4260 if (no_accesses_p (repr))
4261 continue;
4262 if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
4263 || repr->grp_maybe_modified)
4264 continue;
4265
4266 ao_ref_init (&ar, repr->expr);
4267 visited = BITMAP_ALLOC (NULL);
4268 for (access = repr; access; access = access->next_sibling)
4269 {
4270 /* All accesses are read ones, otherwise grp_maybe_modified would
4271 be trivially set. */
4272 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
4273 mark_maybe_modified, repr, &visited);
4274 if (repr->grp_maybe_modified)
4275 break;
4276 }
4277 BITMAP_FREE (visited);
4278 }
4279 }
4280 }
4281
4282 /* Propagate distances in bb_dereferences in the opposite direction than the
4283 control flow edges, in each step storing the maximum of the current value
4284 and the minimum of all successors. These steps are repeated until the table
4285 stabilizes. Note that BBs which might terminate the functions (according to
4286 final_bbs bitmap) never updated in this way. */
4287
4288 static void
propagate_dereference_distances(void)4289 propagate_dereference_distances (void)
4290 {
4291 basic_block bb;
4292
4293 auto_vec<basic_block> queue (last_basic_block_for_fn (cfun));
4294 queue.quick_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4295 FOR_EACH_BB_FN (bb, cfun)
4296 {
4297 queue.quick_push (bb);
4298 bb->aux = bb;
4299 }
4300
4301 while (!queue.is_empty ())
4302 {
4303 edge_iterator ei;
4304 edge e;
4305 bool change = false;
4306 int i;
4307
4308 bb = queue.pop ();
4309 bb->aux = NULL;
4310
4311 if (bitmap_bit_p (final_bbs, bb->index))
4312 continue;
4313
4314 for (i = 0; i < func_param_count; i++)
4315 {
4316 int idx = bb->index * func_param_count + i;
4317 bool first = true;
4318 HOST_WIDE_INT inh = 0;
4319
4320 FOR_EACH_EDGE (e, ei, bb->succs)
4321 {
4322 int succ_idx = e->dest->index * func_param_count + i;
4323
4324 if (e->src == EXIT_BLOCK_PTR_FOR_FN (cfun))
4325 continue;
4326
4327 if (first)
4328 {
4329 first = false;
4330 inh = bb_dereferences [succ_idx];
4331 }
4332 else if (bb_dereferences [succ_idx] < inh)
4333 inh = bb_dereferences [succ_idx];
4334 }
4335
4336 if (!first && bb_dereferences[idx] < inh)
4337 {
4338 bb_dereferences[idx] = inh;
4339 change = true;
4340 }
4341 }
4342
4343 if (change && !bitmap_bit_p (final_bbs, bb->index))
4344 FOR_EACH_EDGE (e, ei, bb->preds)
4345 {
4346 if (e->src->aux)
4347 continue;
4348
4349 e->src->aux = e->src;
4350 queue.quick_push (e->src);
4351 }
4352 }
4353 }
4354
4355 /* Dump a dereferences TABLE with heading STR to file F. */
4356
4357 static void
dump_dereferences_table(FILE * f,const char * str,HOST_WIDE_INT * table)4358 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
4359 {
4360 basic_block bb;
4361
4362 fprintf (dump_file, "%s", str);
4363 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
4364 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
4365 {
4366 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index));
4367 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4368 {
4369 int i;
4370 for (i = 0; i < func_param_count; i++)
4371 {
4372 int idx = bb->index * func_param_count + i;
4373 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
4374 }
4375 }
4376 fprintf (f, "\n");
4377 }
4378 fprintf (dump_file, "\n");
4379 }
4380
4381 /* Determine what (parts of) parameters passed by reference that are not
4382 assigned to are not certainly dereferenced in this function and thus the
4383 dereferencing cannot be safely moved to the caller without potentially
4384 introducing a segfault. Mark such REPRESENTATIVES as
4385 grp_not_necessarilly_dereferenced.
4386
4387 The dereferenced maximum "distance," i.e. the offset + size of the accessed
4388 part is calculated rather than simple booleans are calculated for each
4389 pointer parameter to handle cases when only a fraction of the whole
4390 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
4391 an example).
4392
4393 The maximum dereference distances for each pointer parameter and BB are
4394 already stored in bb_dereference. This routine simply propagates these
4395 values upwards by propagate_dereference_distances and then compares the
4396 distances of individual parameters in the ENTRY BB to the equivalent
4397 distances of each representative of a (fraction of a) parameter. */
4398
4399 static void
analyze_caller_dereference_legality(vec<access_p> representatives)4400 analyze_caller_dereference_legality (vec<access_p> representatives)
4401 {
4402 int i;
4403
4404 if (dump_file && (dump_flags & TDF_DETAILS))
4405 dump_dereferences_table (dump_file,
4406 "Dereference table before propagation:\n",
4407 bb_dereferences);
4408
4409 propagate_dereference_distances ();
4410
4411 if (dump_file && (dump_flags & TDF_DETAILS))
4412 dump_dereferences_table (dump_file,
4413 "Dereference table after propagation:\n",
4414 bb_dereferences);
4415
4416 for (i = 0; i < func_param_count; i++)
4417 {
4418 struct access *repr = representatives[i];
4419 int idx = ENTRY_BLOCK_PTR_FOR_FN (cfun)->index * func_param_count + i;
4420
4421 if (!repr || no_accesses_p (repr))
4422 continue;
4423
4424 do
4425 {
4426 if ((repr->offset + repr->size) > bb_dereferences[idx])
4427 repr->grp_not_necessarilly_dereferenced = 1;
4428 repr = repr->next_grp;
4429 }
4430 while (repr);
4431 }
4432 }
4433
4434 /* Return the representative access for the parameter declaration PARM if it is
4435 a scalar passed by reference which is not written to and the pointer value
4436 is not used directly. Thus, if it is legal to dereference it in the caller
4437 and we can rule out modifications through aliases, such parameter should be
4438 turned into one passed by value. Return NULL otherwise. */
4439
4440 static struct access *
unmodified_by_ref_scalar_representative(tree parm)4441 unmodified_by_ref_scalar_representative (tree parm)
4442 {
4443 int i, access_count;
4444 struct access *repr;
4445 vec<access_p> *access_vec;
4446
4447 access_vec = get_base_access_vector (parm);
4448 gcc_assert (access_vec);
4449 repr = (*access_vec)[0];
4450 if (repr->write)
4451 return NULL;
4452 repr->group_representative = repr;
4453
4454 access_count = access_vec->length ();
4455 for (i = 1; i < access_count; i++)
4456 {
4457 struct access *access = (*access_vec)[i];
4458 if (access->write)
4459 return NULL;
4460 access->group_representative = repr;
4461 access->next_sibling = repr->next_sibling;
4462 repr->next_sibling = access;
4463 }
4464
4465 repr->grp_read = 1;
4466 repr->grp_scalar_ptr = 1;
4467 return repr;
4468 }
4469
4470 /* Return true iff this ACCESS precludes IPA-SRA of the parameter it is
4471 associated with. REQ_ALIGN is the minimum required alignment. */
4472
4473 static bool
access_precludes_ipa_sra_p(struct access * access,unsigned int req_align)4474 access_precludes_ipa_sra_p (struct access *access, unsigned int req_align)
4475 {
4476 unsigned int exp_align;
4477 /* Avoid issues such as the second simple testcase in PR 42025. The problem
4478 is incompatible assign in a call statement (and possibly even in asm
4479 statements). This can be relaxed by using a new temporary but only for
4480 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
4481 intraprocedural SRA we deal with this by keeping the old aggregate around,
4482 something we cannot do in IPA-SRA.) */
4483 if (access->write
4484 && (is_gimple_call (access->stmt)
4485 || gimple_code (access->stmt) == GIMPLE_ASM))
4486 return true;
4487
4488 exp_align = get_object_alignment (access->expr);
4489 if (exp_align < req_align)
4490 return true;
4491
4492 return false;
4493 }
4494
4495
4496 /* Sort collected accesses for parameter PARM, identify representatives for
4497 each accessed region and link them together. Return NULL if there are
4498 different but overlapping accesses, return the special ptr value meaning
4499 there are no accesses for this parameter if that is the case and return the
4500 first representative otherwise. Set *RO_GRP if there is a group of accesses
4501 with only read (i.e. no write) accesses. */
4502
4503 static struct access *
splice_param_accesses(tree parm,bool * ro_grp)4504 splice_param_accesses (tree parm, bool *ro_grp)
4505 {
4506 int i, j, access_count, group_count;
4507 int total_size = 0;
4508 struct access *access, *res, **prev_acc_ptr = &res;
4509 vec<access_p> *access_vec;
4510
4511 access_vec = get_base_access_vector (parm);
4512 if (!access_vec)
4513 return &no_accesses_representant;
4514 access_count = access_vec->length ();
4515
4516 access_vec->qsort (compare_access_positions);
4517
4518 i = 0;
4519 total_size = 0;
4520 group_count = 0;
4521 while (i < access_count)
4522 {
4523 bool modification;
4524 tree a1_alias_type;
4525 access = (*access_vec)[i];
4526 modification = access->write;
4527 if (access_precludes_ipa_sra_p (access, TYPE_ALIGN (access->type)))
4528 return NULL;
4529 a1_alias_type = reference_alias_ptr_type (access->expr);
4530
4531 /* Access is about to become group representative unless we find some
4532 nasty overlap which would preclude us from breaking this parameter
4533 apart. */
4534
4535 j = i + 1;
4536 while (j < access_count)
4537 {
4538 struct access *ac2 = (*access_vec)[j];
4539 if (ac2->offset != access->offset)
4540 {
4541 /* All or nothing law for parameters. */
4542 if (access->offset + access->size > ac2->offset)
4543 return NULL;
4544 else
4545 break;
4546 }
4547 else if (ac2->size != access->size)
4548 return NULL;
4549
4550 if (access_precludes_ipa_sra_p (ac2, TYPE_ALIGN (access->type))
4551 || (ac2->type != access->type
4552 && (TREE_ADDRESSABLE (ac2->type)
4553 || TREE_ADDRESSABLE (access->type)))
4554 || (reference_alias_ptr_type (ac2->expr) != a1_alias_type))
4555 return NULL;
4556
4557 modification |= ac2->write;
4558 ac2->group_representative = access;
4559 ac2->next_sibling = access->next_sibling;
4560 access->next_sibling = ac2;
4561 j++;
4562 }
4563
4564 group_count++;
4565 access->grp_maybe_modified = modification;
4566 if (!modification)
4567 *ro_grp = true;
4568 *prev_acc_ptr = access;
4569 prev_acc_ptr = &access->next_grp;
4570 total_size += access->size;
4571 i = j;
4572 }
4573
4574 gcc_assert (group_count > 0);
4575 return res;
4576 }
4577
4578 /* Decide whether parameters with representative accesses given by REPR should
4579 be reduced into components. */
4580
4581 static int
decide_one_param_reduction(struct access * repr)4582 decide_one_param_reduction (struct access *repr)
4583 {
4584 HOST_WIDE_INT total_size, cur_parm_size;
4585 bool by_ref;
4586 tree parm;
4587
4588 parm = repr->base;
4589 cur_parm_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm)));
4590 gcc_assert (cur_parm_size > 0);
4591
4592 if (POINTER_TYPE_P (TREE_TYPE (parm)))
4593 by_ref = true;
4594 else
4595 by_ref = false;
4596
4597 if (dump_file)
4598 {
4599 struct access *acc;
4600 fprintf (dump_file, "Evaluating PARAM group sizes for ");
4601 print_generic_expr (dump_file, parm);
4602 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
4603 for (acc = repr; acc; acc = acc->next_grp)
4604 dump_access (dump_file, acc, true);
4605 }
4606
4607 total_size = 0;
4608 int new_param_count = 0;
4609
4610 for (; repr; repr = repr->next_grp)
4611 {
4612 gcc_assert (parm == repr->base);
4613
4614 /* Taking the address of a non-addressable field is verboten. */
4615 if (by_ref && repr->non_addressable)
4616 return 0;
4617
4618 /* Do not decompose a non-BLKmode param in a way that would
4619 create BLKmode params. Especially for by-reference passing
4620 (thus, pointer-type param) this is hardly worthwhile. */
4621 if (DECL_MODE (parm) != BLKmode
4622 && TYPE_MODE (repr->type) == BLKmode)
4623 return 0;
4624
4625 if (!by_ref || (!repr->grp_maybe_modified
4626 && !repr->grp_not_necessarilly_dereferenced))
4627 total_size += repr->size;
4628 else
4629 total_size += cur_parm_size;
4630
4631 new_param_count++;
4632 }
4633
4634 gcc_assert (new_param_count > 0);
4635
4636 if (!by_ref)
4637 {
4638 if (total_size >= cur_parm_size)
4639 return 0;
4640 }
4641 else
4642 {
4643 int parm_num_limit;
4644 if (optimize_function_for_size_p (cfun))
4645 parm_num_limit = 1;
4646 else
4647 parm_num_limit = PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR);
4648
4649 if (new_param_count > parm_num_limit
4650 || total_size > (parm_num_limit * cur_parm_size))
4651 return 0;
4652 }
4653
4654 if (dump_file)
4655 fprintf (dump_file, " ....will be split into %i components\n",
4656 new_param_count);
4657 return new_param_count;
4658 }
4659
4660 /* The order of the following enums is important, we need to do extra work for
4661 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
4662 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
4663 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
4664
4665 /* Identify representatives of all accesses to all candidate parameters for
4666 IPA-SRA. Return result based on what representatives have been found. */
4667
4668 static enum ipa_splicing_result
splice_all_param_accesses(vec<access_p> & representatives)4669 splice_all_param_accesses (vec<access_p> &representatives)
4670 {
4671 enum ipa_splicing_result result = NO_GOOD_ACCESS;
4672 tree parm;
4673 struct access *repr;
4674
4675 representatives.create (func_param_count);
4676
4677 for (parm = DECL_ARGUMENTS (current_function_decl);
4678 parm;
4679 parm = DECL_CHAIN (parm))
4680 {
4681 if (is_unused_scalar_param (parm))
4682 {
4683 representatives.quick_push (&no_accesses_representant);
4684 if (result == NO_GOOD_ACCESS)
4685 result = UNUSED_PARAMS;
4686 }
4687 else if (POINTER_TYPE_P (TREE_TYPE (parm))
4688 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
4689 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4690 {
4691 repr = unmodified_by_ref_scalar_representative (parm);
4692 representatives.quick_push (repr);
4693 if (repr)
4694 result = UNMODIF_BY_REF_ACCESSES;
4695 }
4696 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4697 {
4698 bool ro_grp = false;
4699 repr = splice_param_accesses (parm, &ro_grp);
4700 representatives.quick_push (repr);
4701
4702 if (repr && !no_accesses_p (repr))
4703 {
4704 if (POINTER_TYPE_P (TREE_TYPE (parm)))
4705 {
4706 if (ro_grp)
4707 result = UNMODIF_BY_REF_ACCESSES;
4708 else if (result < MODIF_BY_REF_ACCESSES)
4709 result = MODIF_BY_REF_ACCESSES;
4710 }
4711 else if (result < BY_VAL_ACCESSES)
4712 result = BY_VAL_ACCESSES;
4713 }
4714 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
4715 result = UNUSED_PARAMS;
4716 }
4717 else
4718 representatives.quick_push (NULL);
4719 }
4720
4721 if (result == NO_GOOD_ACCESS)
4722 {
4723 representatives.release ();
4724 return NO_GOOD_ACCESS;
4725 }
4726
4727 return result;
4728 }
4729
4730 /* Return the index of BASE in PARMS. Abort if it is not found. */
4731
4732 static inline int
get_param_index(tree base,vec<tree> parms)4733 get_param_index (tree base, vec<tree> parms)
4734 {
4735 int i, len;
4736
4737 len = parms.length ();
4738 for (i = 0; i < len; i++)
4739 if (parms[i] == base)
4740 return i;
4741 gcc_unreachable ();
4742 }
4743
4744 /* Convert the decisions made at the representative level into compact
4745 parameter adjustments. REPRESENTATIVES are pointers to first
4746 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
4747 final number of adjustments. */
4748
4749 static ipa_parm_adjustment_vec
turn_representatives_into_adjustments(vec<access_p> representatives,int adjustments_count)4750 turn_representatives_into_adjustments (vec<access_p> representatives,
4751 int adjustments_count)
4752 {
4753 vec<tree> parms;
4754 ipa_parm_adjustment_vec adjustments;
4755 tree parm;
4756 int i;
4757
4758 gcc_assert (adjustments_count > 0);
4759 parms = ipa_get_vector_of_formal_parms (current_function_decl);
4760 adjustments.create (adjustments_count);
4761 parm = DECL_ARGUMENTS (current_function_decl);
4762 for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm))
4763 {
4764 struct access *repr = representatives[i];
4765
4766 if (!repr || no_accesses_p (repr))
4767 {
4768 struct ipa_parm_adjustment adj;
4769
4770 memset (&adj, 0, sizeof (adj));
4771 adj.base_index = get_param_index (parm, parms);
4772 adj.base = parm;
4773 if (!repr)
4774 adj.op = IPA_PARM_OP_COPY;
4775 else
4776 adj.op = IPA_PARM_OP_REMOVE;
4777 adj.arg_prefix = "ISRA";
4778 adjustments.quick_push (adj);
4779 }
4780 else
4781 {
4782 struct ipa_parm_adjustment adj;
4783 int index = get_param_index (parm, parms);
4784
4785 for (; repr; repr = repr->next_grp)
4786 {
4787 memset (&adj, 0, sizeof (adj));
4788 gcc_assert (repr->base == parm);
4789 adj.base_index = index;
4790 adj.base = repr->base;
4791 adj.type = repr->type;
4792 adj.alias_ptr_type = reference_alias_ptr_type (repr->expr);
4793 adj.offset = repr->offset;
4794 adj.reverse = repr->reverse;
4795 adj.by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
4796 && (repr->grp_maybe_modified
4797 || repr->grp_not_necessarilly_dereferenced));
4798 adj.arg_prefix = "ISRA";
4799 adjustments.quick_push (adj);
4800 }
4801 }
4802 }
4803 parms.release ();
4804 return adjustments;
4805 }
4806
4807 /* Analyze the collected accesses and produce a plan what to do with the
4808 parameters in the form of adjustments, NULL meaning nothing. */
4809
4810 static ipa_parm_adjustment_vec
analyze_all_param_acesses(void)4811 analyze_all_param_acesses (void)
4812 {
4813 enum ipa_splicing_result repr_state;
4814 bool proceed = false;
4815 int i, adjustments_count = 0;
4816 vec<access_p> representatives;
4817 ipa_parm_adjustment_vec adjustments;
4818
4819 repr_state = splice_all_param_accesses (representatives);
4820 if (repr_state == NO_GOOD_ACCESS)
4821 return ipa_parm_adjustment_vec ();
4822
4823 /* If there are any parameters passed by reference which are not modified
4824 directly, we need to check whether they can be modified indirectly. */
4825 if (repr_state == UNMODIF_BY_REF_ACCESSES)
4826 {
4827 analyze_caller_dereference_legality (representatives);
4828 analyze_modified_params (representatives);
4829 }
4830
4831 for (i = 0; i < func_param_count; i++)
4832 {
4833 struct access *repr = representatives[i];
4834
4835 if (repr && !no_accesses_p (repr))
4836 {
4837 if (repr->grp_scalar_ptr)
4838 {
4839 adjustments_count++;
4840 if (repr->grp_not_necessarilly_dereferenced
4841 || repr->grp_maybe_modified)
4842 representatives[i] = NULL;
4843 else
4844 {
4845 proceed = true;
4846 sra_stats.scalar_by_ref_to_by_val++;
4847 }
4848 }
4849 else
4850 {
4851 int new_components = decide_one_param_reduction (repr);
4852
4853 if (new_components == 0)
4854 {
4855 representatives[i] = NULL;
4856 adjustments_count++;
4857 }
4858 else
4859 {
4860 adjustments_count += new_components;
4861 sra_stats.aggregate_params_reduced++;
4862 sra_stats.param_reductions_created += new_components;
4863 proceed = true;
4864 }
4865 }
4866 }
4867 else
4868 {
4869 if (no_accesses_p (repr))
4870 {
4871 proceed = true;
4872 sra_stats.deleted_unused_parameters++;
4873 }
4874 adjustments_count++;
4875 }
4876 }
4877
4878 if (!proceed && dump_file)
4879 fprintf (dump_file, "NOT proceeding to change params.\n");
4880
4881 if (proceed)
4882 adjustments = turn_representatives_into_adjustments (representatives,
4883 adjustments_count);
4884 else
4885 adjustments = ipa_parm_adjustment_vec ();
4886
4887 representatives.release ();
4888 return adjustments;
4889 }
4890
4891 /* If a parameter replacement identified by ADJ does not yet exist in the form
4892 of declaration, create it and record it, otherwise return the previously
4893 created one. */
4894
4895 static tree
get_replaced_param_substitute(struct ipa_parm_adjustment * adj)4896 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
4897 {
4898 tree repl;
4899 if (!adj->new_ssa_base)
4900 {
4901 char *pretty_name = make_fancy_name (adj->base);
4902
4903 repl = create_tmp_reg (TREE_TYPE (adj->base), "ISR");
4904 DECL_NAME (repl) = get_identifier (pretty_name);
4905 DECL_NAMELESS (repl) = 1;
4906 obstack_free (&name_obstack, pretty_name);
4907
4908 adj->new_ssa_base = repl;
4909 }
4910 else
4911 repl = adj->new_ssa_base;
4912 return repl;
4913 }
4914
4915 /* Find the first adjustment for a particular parameter BASE in a vector of
4916 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such
4917 adjustment. */
4918
4919 static struct ipa_parm_adjustment *
get_adjustment_for_base(ipa_parm_adjustment_vec adjustments,tree base)4920 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
4921 {
4922 int i, len;
4923
4924 len = adjustments.length ();
4925 for (i = 0; i < len; i++)
4926 {
4927 struct ipa_parm_adjustment *adj;
4928
4929 adj = &adjustments[i];
4930 if (adj->op != IPA_PARM_OP_COPY && adj->base == base)
4931 return adj;
4932 }
4933
4934 return NULL;
4935 }
4936
4937 /* If OLD_NAME, which is being defined by statement STMT, is an SSA_NAME of a
4938 parameter which is to be removed because its value is not used, create a new
4939 SSA_NAME relating to a replacement VAR_DECL, replace all uses of the
4940 original with it and return it. If there is no need to re-map, return NULL.
4941 ADJUSTMENTS is a pointer to a vector of IPA-SRA adjustments. */
4942
4943 static tree
replace_removed_params_ssa_names(tree old_name,gimple * stmt,ipa_parm_adjustment_vec adjustments)4944 replace_removed_params_ssa_names (tree old_name, gimple *stmt,
4945 ipa_parm_adjustment_vec adjustments)
4946 {
4947 struct ipa_parm_adjustment *adj;
4948 tree decl, repl, new_name;
4949
4950 if (TREE_CODE (old_name) != SSA_NAME)
4951 return NULL;
4952
4953 decl = SSA_NAME_VAR (old_name);
4954 if (decl == NULL_TREE
4955 || TREE_CODE (decl) != PARM_DECL)
4956 return NULL;
4957
4958 adj = get_adjustment_for_base (adjustments, decl);
4959 if (!adj)
4960 return NULL;
4961
4962 repl = get_replaced_param_substitute (adj);
4963 new_name = make_ssa_name (repl, stmt);
4964 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name)
4965 = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (old_name);
4966
4967 if (dump_file)
4968 {
4969 fprintf (dump_file, "replacing an SSA name of a removed param ");
4970 print_generic_expr (dump_file, old_name);
4971 fprintf (dump_file, " with ");
4972 print_generic_expr (dump_file, new_name);
4973 fprintf (dump_file, "\n");
4974 }
4975
4976 replace_uses_by (old_name, new_name);
4977 return new_name;
4978 }
4979
4980 /* If the statement STMT contains any expressions that need to replaced with a
4981 different one as noted by ADJUSTMENTS, do so. Handle any potential type
4982 incompatibilities (GSI is used to accommodate conversion statements and must
4983 point to the statement). Return true iff the statement was modified. */
4984
4985 static bool
sra_ipa_modify_assign(gimple * stmt,gimple_stmt_iterator * gsi,ipa_parm_adjustment_vec adjustments)4986 sra_ipa_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
4987 ipa_parm_adjustment_vec adjustments)
4988 {
4989 tree *lhs_p, *rhs_p;
4990 bool any;
4991
4992 if (!gimple_assign_single_p (stmt))
4993 return false;
4994
4995 rhs_p = gimple_assign_rhs1_ptr (stmt);
4996 lhs_p = gimple_assign_lhs_ptr (stmt);
4997
4998 any = ipa_modify_expr (rhs_p, false, adjustments);
4999 any |= ipa_modify_expr (lhs_p, false, adjustments);
5000 if (any)
5001 {
5002 tree new_rhs = NULL_TREE;
5003
5004 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
5005 {
5006 if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
5007 {
5008 /* V_C_Es of constructors can cause trouble (PR 42714). */
5009 if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
5010 *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
5011 else
5012 *rhs_p = build_constructor (TREE_TYPE (*lhs_p),
5013 NULL);
5014 }
5015 else
5016 new_rhs = fold_build1_loc (gimple_location (stmt),
5017 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
5018 *rhs_p);
5019 }
5020 else if (REFERENCE_CLASS_P (*rhs_p)
5021 && is_gimple_reg_type (TREE_TYPE (*lhs_p))
5022 && !is_gimple_reg (*lhs_p))
5023 /* This can happen when an assignment in between two single field
5024 structures is turned into an assignment in between two pointers to
5025 scalars (PR 42237). */
5026 new_rhs = *rhs_p;
5027
5028 if (new_rhs)
5029 {
5030 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
5031 true, GSI_SAME_STMT);
5032
5033 gimple_assign_set_rhs_from_tree (gsi, tmp);
5034 }
5035
5036 return true;
5037 }
5038
5039 return false;
5040 }
5041
5042 /* Traverse the function body and all modifications as described in
5043 ADJUSTMENTS. Return true iff the CFG has been changed. */
5044
5045 bool
ipa_sra_modify_function_body(ipa_parm_adjustment_vec adjustments)5046 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments)
5047 {
5048 bool cfg_changed = false;
5049 basic_block bb;
5050
5051 FOR_EACH_BB_FN (bb, cfun)
5052 {
5053 gimple_stmt_iterator gsi;
5054
5055 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5056 {
5057 gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
5058 tree new_lhs, old_lhs = gimple_phi_result (phi);
5059 new_lhs = replace_removed_params_ssa_names (old_lhs, phi, adjustments);
5060 if (new_lhs)
5061 {
5062 gimple_phi_set_result (phi, new_lhs);
5063 release_ssa_name (old_lhs);
5064 }
5065 }
5066
5067 gsi = gsi_start_bb (bb);
5068 while (!gsi_end_p (gsi))
5069 {
5070 gimple *stmt = gsi_stmt (gsi);
5071 bool modified = false;
5072 tree *t;
5073 unsigned i;
5074
5075 switch (gimple_code (stmt))
5076 {
5077 case GIMPLE_RETURN:
5078 t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
5079 if (*t != NULL_TREE)
5080 modified |= ipa_modify_expr (t, true, adjustments);
5081 break;
5082
5083 case GIMPLE_ASSIGN:
5084 modified |= sra_ipa_modify_assign (stmt, &gsi, adjustments);
5085 break;
5086
5087 case GIMPLE_CALL:
5088 /* Operands must be processed before the lhs. */
5089 for (i = 0; i < gimple_call_num_args (stmt); i++)
5090 {
5091 t = gimple_call_arg_ptr (stmt, i);
5092 modified |= ipa_modify_expr (t, true, adjustments);
5093 }
5094
5095 if (gimple_call_lhs (stmt))
5096 {
5097 t = gimple_call_lhs_ptr (stmt);
5098 modified |= ipa_modify_expr (t, false, adjustments);
5099 }
5100 break;
5101
5102 case GIMPLE_ASM:
5103 {
5104 gasm *asm_stmt = as_a <gasm *> (stmt);
5105 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5106 {
5107 t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5108 modified |= ipa_modify_expr (t, true, adjustments);
5109 }
5110 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5111 {
5112 t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5113 modified |= ipa_modify_expr (t, false, adjustments);
5114 }
5115 }
5116 break;
5117
5118 default:
5119 break;
5120 }
5121
5122 def_operand_p defp;
5123 ssa_op_iter iter;
5124 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
5125 {
5126 tree old_def = DEF_FROM_PTR (defp);
5127 if (tree new_def = replace_removed_params_ssa_names (old_def, stmt,
5128 adjustments))
5129 {
5130 SET_DEF (defp, new_def);
5131 release_ssa_name (old_def);
5132 modified = true;
5133 }
5134 }
5135
5136 if (modified)
5137 {
5138 update_stmt (stmt);
5139 if (maybe_clean_eh_stmt (stmt)
5140 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5141 cfg_changed = true;
5142 }
5143 gsi_next (&gsi);
5144 }
5145 }
5146
5147 return cfg_changed;
5148 }
5149
5150 /* Call gimple_debug_bind_reset_value on all debug statements describing
5151 gimple register parameters that are being removed or replaced. */
5152
5153 static void
sra_ipa_reset_debug_stmts(ipa_parm_adjustment_vec adjustments)5154 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
5155 {
5156 int i, len;
5157 gimple_stmt_iterator *gsip = NULL, gsi;
5158
5159 if (MAY_HAVE_DEBUG_STMTS && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
5160 {
5161 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5162 gsip = &gsi;
5163 }
5164 len = adjustments.length ();
5165 for (i = 0; i < len; i++)
5166 {
5167 struct ipa_parm_adjustment *adj;
5168 imm_use_iterator ui;
5169 gimple *stmt;
5170 gdebug *def_temp;
5171 tree name, vexpr, copy = NULL_TREE;
5172 use_operand_p use_p;
5173
5174 adj = &adjustments[i];
5175 if (adj->op == IPA_PARM_OP_COPY || !is_gimple_reg (adj->base))
5176 continue;
5177 name = ssa_default_def (cfun, adj->base);
5178 vexpr = NULL;
5179 if (name)
5180 FOR_EACH_IMM_USE_STMT (stmt, ui, name)
5181 {
5182 if (gimple_clobber_p (stmt))
5183 {
5184 gimple_stmt_iterator cgsi = gsi_for_stmt (stmt);
5185 unlink_stmt_vdef (stmt);
5186 gsi_remove (&cgsi, true);
5187 release_defs (stmt);
5188 continue;
5189 }
5190 /* All other users must have been removed by
5191 ipa_sra_modify_function_body. */
5192 gcc_assert (is_gimple_debug (stmt));
5193 if (vexpr == NULL && gsip != NULL)
5194 {
5195 gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
5196 vexpr = make_node (DEBUG_EXPR_DECL);
5197 def_temp = gimple_build_debug_source_bind (vexpr, adj->base,
5198 NULL);
5199 DECL_ARTIFICIAL (vexpr) = 1;
5200 TREE_TYPE (vexpr) = TREE_TYPE (name);
5201 SET_DECL_MODE (vexpr, DECL_MODE (adj->base));
5202 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
5203 }
5204 if (vexpr)
5205 {
5206 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
5207 SET_USE (use_p, vexpr);
5208 }
5209 else
5210 gimple_debug_bind_reset_value (stmt);
5211 update_stmt (stmt);
5212 }
5213 /* Create a VAR_DECL for debug info purposes. */
5214 if (!DECL_IGNORED_P (adj->base))
5215 {
5216 copy = build_decl (DECL_SOURCE_LOCATION (current_function_decl),
5217 VAR_DECL, DECL_NAME (adj->base),
5218 TREE_TYPE (adj->base));
5219 if (DECL_PT_UID_SET_P (adj->base))
5220 SET_DECL_PT_UID (copy, DECL_PT_UID (adj->base));
5221 TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (adj->base);
5222 TREE_READONLY (copy) = TREE_READONLY (adj->base);
5223 TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (adj->base);
5224 DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (adj->base);
5225 DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (adj->base);
5226 DECL_IGNORED_P (copy) = DECL_IGNORED_P (adj->base);
5227 DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (adj->base);
5228 DECL_SEEN_IN_BIND_EXPR_P (copy) = 1;
5229 SET_DECL_RTL (copy, 0);
5230 TREE_USED (copy) = 1;
5231 DECL_CONTEXT (copy) = current_function_decl;
5232 add_local_decl (cfun, copy);
5233 DECL_CHAIN (copy) =
5234 BLOCK_VARS (DECL_INITIAL (current_function_decl));
5235 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = copy;
5236 }
5237 if (gsip != NULL && copy && target_for_debug_bind (adj->base))
5238 {
5239 gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
5240 if (vexpr)
5241 def_temp = gimple_build_debug_bind (copy, vexpr, NULL);
5242 else
5243 def_temp = gimple_build_debug_source_bind (copy, adj->base,
5244 NULL);
5245 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
5246 }
5247 }
5248 }
5249
5250 /* Return false if all callers have at least as many actual arguments as there
5251 are formal parameters in the current function and that their types
5252 match. */
5253
5254 static bool
some_callers_have_mismatched_arguments_p(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)5255 some_callers_have_mismatched_arguments_p (struct cgraph_node *node,
5256 void *data ATTRIBUTE_UNUSED)
5257 {
5258 struct cgraph_edge *cs;
5259 for (cs = node->callers; cs; cs = cs->next_caller)
5260 if (!cs->call_stmt || !callsite_arguments_match_p (cs->call_stmt))
5261 return true;
5262
5263 return false;
5264 }
5265
5266 /* Return false if all callers have vuse attached to a call statement. */
5267
5268 static bool
some_callers_have_no_vuse_p(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)5269 some_callers_have_no_vuse_p (struct cgraph_node *node,
5270 void *data ATTRIBUTE_UNUSED)
5271 {
5272 struct cgraph_edge *cs;
5273 for (cs = node->callers; cs; cs = cs->next_caller)
5274 if (!cs->call_stmt || !gimple_vuse (cs->call_stmt))
5275 return true;
5276
5277 return false;
5278 }
5279
5280 /* Convert all callers of NODE. */
5281
5282 static bool
convert_callers_for_node(struct cgraph_node * node,void * data)5283 convert_callers_for_node (struct cgraph_node *node,
5284 void *data)
5285 {
5286 ipa_parm_adjustment_vec *adjustments = (ipa_parm_adjustment_vec *) data;
5287 bitmap recomputed_callers = BITMAP_ALLOC (NULL);
5288 struct cgraph_edge *cs;
5289
5290 for (cs = node->callers; cs; cs = cs->next_caller)
5291 {
5292 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
5293
5294 if (dump_file)
5295 fprintf (dump_file, "Adjusting call %s -> %s\n",
5296 cs->caller->dump_name (), cs->callee->dump_name ());
5297
5298 ipa_modify_call_arguments (cs, cs->call_stmt, *adjustments);
5299
5300 pop_cfun ();
5301 }
5302
5303 for (cs = node->callers; cs; cs = cs->next_caller)
5304 if (bitmap_set_bit (recomputed_callers, cs->caller->uid)
5305 && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (cs->caller->decl)))
5306 compute_fn_summary (cs->caller, true);
5307 BITMAP_FREE (recomputed_callers);
5308
5309 return true;
5310 }
5311
5312 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
5313
5314 static void
convert_callers(struct cgraph_node * node,tree old_decl,ipa_parm_adjustment_vec adjustments)5315 convert_callers (struct cgraph_node *node, tree old_decl,
5316 ipa_parm_adjustment_vec adjustments)
5317 {
5318 basic_block this_block;
5319
5320 node->call_for_symbol_and_aliases (convert_callers_for_node,
5321 &adjustments, false);
5322
5323 if (!encountered_recursive_call)
5324 return;
5325
5326 FOR_EACH_BB_FN (this_block, cfun)
5327 {
5328 gimple_stmt_iterator gsi;
5329
5330 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
5331 {
5332 gcall *stmt;
5333 tree call_fndecl;
5334 stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
5335 if (!stmt)
5336 continue;
5337 call_fndecl = gimple_call_fndecl (stmt);
5338 if (call_fndecl == old_decl)
5339 {
5340 if (dump_file)
5341 fprintf (dump_file, "Adjusting recursive call");
5342 gimple_call_set_fndecl (stmt, node->decl);
5343 ipa_modify_call_arguments (NULL, stmt, adjustments);
5344 }
5345 }
5346 }
5347
5348 return;
5349 }
5350
5351 /* Perform all the modification required in IPA-SRA for NODE to have parameters
5352 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */
5353
5354 static bool
modify_function(struct cgraph_node * node,ipa_parm_adjustment_vec adjustments)5355 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
5356 {
5357 struct cgraph_node *new_node;
5358 bool cfg_changed;
5359
5360 cgraph_edge::rebuild_edges ();
5361 free_dominance_info (CDI_DOMINATORS);
5362 pop_cfun ();
5363
5364 /* This must be done after rebuilding cgraph edges for node above.
5365 Otherwise any recursive calls to node that are recorded in
5366 redirect_callers will be corrupted. */
5367 vec<cgraph_edge *> redirect_callers = node->collect_callers ();
5368 new_node = node->create_version_clone_with_body (redirect_callers, NULL,
5369 NULL, false, NULL, NULL,
5370 "isra");
5371 redirect_callers.release ();
5372
5373 push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
5374 ipa_modify_formal_parameters (current_function_decl, adjustments);
5375 cfg_changed = ipa_sra_modify_function_body (adjustments);
5376 sra_ipa_reset_debug_stmts (adjustments);
5377 convert_callers (new_node, node->decl, adjustments);
5378 new_node->make_local ();
5379 return cfg_changed;
5380 }
5381
5382 /* Means of communication between ipa_sra_check_caller and
5383 ipa_sra_preliminary_function_checks. */
5384
5385 struct ipa_sra_check_caller_data
5386 {
5387 bool has_callers;
5388 bool bad_arg_alignment;
5389 bool has_thunk;
5390 };
5391
5392 /* If NODE has a caller, mark that fact in DATA which is pointer to
5393 ipa_sra_check_caller_data. Also check all aggregate arguments in all known
5394 calls if they are unit aligned and if not, set the appropriate flag in DATA
5395 too. */
5396
5397 static bool
ipa_sra_check_caller(struct cgraph_node * node,void * data)5398 ipa_sra_check_caller (struct cgraph_node *node, void *data)
5399 {
5400 if (!node->callers)
5401 return false;
5402
5403 struct ipa_sra_check_caller_data *iscc;
5404 iscc = (struct ipa_sra_check_caller_data *) data;
5405 iscc->has_callers = true;
5406
5407 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
5408 {
5409 if (cs->caller->thunk.thunk_p)
5410 {
5411 iscc->has_thunk = true;
5412 return true;
5413 }
5414 gimple *call_stmt = cs->call_stmt;
5415 unsigned count = gimple_call_num_args (call_stmt);
5416 for (unsigned i = 0; i < count; i++)
5417 {
5418 tree arg = gimple_call_arg (call_stmt, i);
5419 if (is_gimple_reg (arg))
5420 continue;
5421
5422 tree offset;
5423 poly_int64 bitsize, bitpos;
5424 machine_mode mode;
5425 int unsignedp, reversep, volatilep = 0;
5426 get_inner_reference (arg, &bitsize, &bitpos, &offset, &mode,
5427 &unsignedp, &reversep, &volatilep);
5428 if (!multiple_p (bitpos, BITS_PER_UNIT))
5429 {
5430 iscc->bad_arg_alignment = true;
5431 return true;
5432 }
5433 }
5434 }
5435
5436 return false;
5437 }
5438
5439 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
5440 attributes, return true otherwise. NODE is the cgraph node of the current
5441 function. */
5442
5443 static bool
ipa_sra_preliminary_function_checks(struct cgraph_node * node)5444 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
5445 {
5446 if (!node->can_be_local_p ())
5447 {
5448 if (dump_file)
5449 fprintf (dump_file, "Function not local to this compilation unit.\n");
5450 return false;
5451 }
5452
5453 if (!node->local.can_change_signature)
5454 {
5455 if (dump_file)
5456 fprintf (dump_file, "Function can not change signature.\n");
5457 return false;
5458 }
5459
5460 if (!tree_versionable_function_p (node->decl))
5461 {
5462 if (dump_file)
5463 fprintf (dump_file, "Function is not versionable.\n");
5464 return false;
5465 }
5466
5467 if (!opt_for_fn (node->decl, optimize)
5468 || !opt_for_fn (node->decl, flag_ipa_sra))
5469 {
5470 if (dump_file)
5471 fprintf (dump_file, "Function not optimized.\n");
5472 return false;
5473 }
5474
5475 if (DECL_VIRTUAL_P (current_function_decl))
5476 {
5477 if (dump_file)
5478 fprintf (dump_file, "Function is a virtual method.\n");
5479 return false;
5480 }
5481
5482 if ((DECL_ONE_ONLY (node->decl) || DECL_EXTERNAL (node->decl))
5483 && ipa_fn_summaries->get (node)->size >= MAX_INLINE_INSNS_AUTO)
5484 {
5485 if (dump_file)
5486 fprintf (dump_file, "Function too big to be made truly local.\n");
5487 return false;
5488 }
5489
5490 if (cfun->stdarg)
5491 {
5492 if (dump_file)
5493 fprintf (dump_file, "Function uses stdarg. \n");
5494 return false;
5495 }
5496
5497 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
5498 return false;
5499
5500 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
5501 {
5502 if (dump_file)
5503 fprintf (dump_file, "Always inline function will be inlined "
5504 "anyway. \n");
5505 return false;
5506 }
5507
5508 struct ipa_sra_check_caller_data iscc;
5509 memset (&iscc, 0, sizeof(iscc));
5510 node->call_for_symbol_and_aliases (ipa_sra_check_caller, &iscc, true);
5511 if (!iscc.has_callers)
5512 {
5513 if (dump_file)
5514 fprintf (dump_file,
5515 "Function has no callers in this compilation unit.\n");
5516 return false;
5517 }
5518
5519 if (iscc.bad_arg_alignment)
5520 {
5521 if (dump_file)
5522 fprintf (dump_file,
5523 "A function call has an argument with non-unit alignment.\n");
5524 return false;
5525 }
5526
5527 if (iscc.has_thunk)
5528 {
5529 if (dump_file)
5530 fprintf (dump_file,
5531 "A has thunk.\n");
5532 return false;
5533 }
5534
5535 return true;
5536 }
5537
5538 /* Perform early interprocedural SRA. */
5539
5540 static unsigned int
ipa_early_sra(void)5541 ipa_early_sra (void)
5542 {
5543 struct cgraph_node *node = cgraph_node::get (current_function_decl);
5544 ipa_parm_adjustment_vec adjustments;
5545 int ret = 0;
5546
5547 if (!ipa_sra_preliminary_function_checks (node))
5548 return 0;
5549
5550 sra_initialize ();
5551 sra_mode = SRA_MODE_EARLY_IPA;
5552
5553 if (!find_param_candidates ())
5554 {
5555 if (dump_file)
5556 fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
5557 goto simple_out;
5558 }
5559
5560 if (node->call_for_symbol_and_aliases
5561 (some_callers_have_mismatched_arguments_p, NULL, true))
5562 {
5563 if (dump_file)
5564 fprintf (dump_file, "There are callers with insufficient number of "
5565 "arguments or arguments with type mismatches.\n");
5566 goto simple_out;
5567 }
5568
5569 if (node->call_for_symbol_and_aliases
5570 (some_callers_have_no_vuse_p, NULL, true))
5571 {
5572 if (dump_file)
5573 fprintf (dump_file, "There are callers with no VUSE attached "
5574 "to a call stmt.\n");
5575 goto simple_out;
5576 }
5577
5578 bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
5579 func_param_count
5580 * last_basic_block_for_fn (cfun));
5581 final_bbs = BITMAP_ALLOC (NULL);
5582
5583 scan_function ();
5584 if (encountered_apply_args)
5585 {
5586 if (dump_file)
5587 fprintf (dump_file, "Function calls __builtin_apply_args().\n");
5588 goto out;
5589 }
5590
5591 if (encountered_unchangable_recursive_call)
5592 {
5593 if (dump_file)
5594 fprintf (dump_file, "Function calls itself with insufficient "
5595 "number of arguments.\n");
5596 goto out;
5597 }
5598
5599 adjustments = analyze_all_param_acesses ();
5600 if (!adjustments.exists ())
5601 goto out;
5602 if (dump_file)
5603 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
5604
5605 if (modify_function (node, adjustments))
5606 ret = TODO_update_ssa | TODO_cleanup_cfg;
5607 else
5608 ret = TODO_update_ssa;
5609 adjustments.release ();
5610
5611 statistics_counter_event (cfun, "Unused parameters deleted",
5612 sra_stats.deleted_unused_parameters);
5613 statistics_counter_event (cfun, "Scalar parameters converted to by-value",
5614 sra_stats.scalar_by_ref_to_by_val);
5615 statistics_counter_event (cfun, "Aggregate parameters broken up",
5616 sra_stats.aggregate_params_reduced);
5617 statistics_counter_event (cfun, "Aggregate parameter components created",
5618 sra_stats.param_reductions_created);
5619
5620 out:
5621 BITMAP_FREE (final_bbs);
5622 free (bb_dereferences);
5623 simple_out:
5624 sra_deinitialize ();
5625 return ret;
5626 }
5627
5628 namespace {
5629
5630 const pass_data pass_data_early_ipa_sra =
5631 {
5632 GIMPLE_PASS, /* type */
5633 "eipa_sra", /* name */
5634 OPTGROUP_NONE, /* optinfo_flags */
5635 TV_IPA_SRA, /* tv_id */
5636 0, /* properties_required */
5637 0, /* properties_provided */
5638 0, /* properties_destroyed */
5639 0, /* todo_flags_start */
5640 TODO_dump_symtab, /* todo_flags_finish */
5641 };
5642
5643 class pass_early_ipa_sra : public gimple_opt_pass
5644 {
5645 public:
pass_early_ipa_sra(gcc::context * ctxt)5646 pass_early_ipa_sra (gcc::context *ctxt)
5647 : gimple_opt_pass (pass_data_early_ipa_sra, ctxt)
5648 {}
5649
5650 /* opt_pass methods: */
gate(function *)5651 virtual bool gate (function *) { return flag_ipa_sra && dbg_cnt (eipa_sra); }
execute(function *)5652 virtual unsigned int execute (function *) { return ipa_early_sra (); }
5653
5654 }; // class pass_early_ipa_sra
5655
5656 } // anon namespace
5657
5658 gimple_opt_pass *
make_pass_early_ipa_sra(gcc::context * ctxt)5659 make_pass_early_ipa_sra (gcc::context *ctxt)
5660 {
5661 return new pass_early_ipa_sra (ctxt);
5662 }
5663