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