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