Line data Source code
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-2026 Free Software Foundation, Inc.
5 : Contributed by Martin Jambor <mjambor@suse.cz>
6 :
7 : This file is part of GCC.
8 :
9 : GCC is free software; you can redistribute it and/or modify it under
10 : the terms of the GNU General Public License as published by the Free
11 : Software Foundation; either version 3, or (at your option) any later
12 : version.
13 :
14 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 : for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GCC; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 : twice, once in the early stages of compilation (early SRA) and once in the
25 : late stages (late SRA). The aim of both is to turn references to scalar
26 : parts of aggregates into uses of independent scalar variables.
27 :
28 : The two passes are nearly identical, the only difference is that early SRA
29 : does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 : statement because together with inlining this can lead to weird type
31 : conversions.
32 :
33 : Both passes operate in four stages:
34 :
35 : 1. The declarations that have properties which make them candidates for
36 : scalarization are identified in function find_var_candidates(). The
37 : candidates are stored in candidate_bitmap.
38 :
39 : 2. The function body is scanned. In the process, declarations which are
40 : used in a manner that prevent their scalarization are removed from the
41 : candidate bitmap. More importantly, for every access into an aggregate,
42 : an access structure (struct access) is created by create_access() and
43 : stored in a vector associated with the aggregate. Among other
44 : information, the aggregate declaration, the offset and size of the access
45 : and its type are stored in the structure.
46 :
47 : On a related note, assign_link structures are created for every assign
48 : statement between candidate aggregates and attached to the related
49 : accesses.
50 :
51 : 3. The vectors of accesses are analyzed. They are first sorted according to
52 : their offset and size and then scanned for partially overlapping accesses
53 : (i.e. those which overlap but one is not entirely within another). Such
54 : an access disqualifies the whole aggregate from being scalarized.
55 :
56 : If there is no such inhibiting overlap, a representative access structure
57 : is chosen for every unique combination of offset and size. Afterwards,
58 : the pass builds a set of trees from these structures, in which children
59 : of an access are within their parent (in terms of offset and size).
60 :
61 : Then accesses are propagated whenever possible (i.e. in cases when it
62 : does not create a partially overlapping access) across assign_links from
63 : the right hand side to the left hand side.
64 :
65 : Then the set of trees for each declaration is traversed again and those
66 : accesses which should be replaced by a scalar are identified.
67 :
68 : 4. The function is traversed again, and for every reference into an
69 : aggregate that has some component which is about to be scalarized,
70 : statements are amended and new statements are created as necessary.
71 : Finally, if a parameter got scalarized, the scalar replacements are
72 : initialized with values from respective parameter aggregates. */
73 :
74 : #include "config.h"
75 : #include "system.h"
76 : #include "coretypes.h"
77 : #include "backend.h"
78 : #include "target.h"
79 : #include "rtl.h"
80 : #include "tree.h"
81 : #include "gimple.h"
82 : #include "predict.h"
83 : #include "alloc-pool.h"
84 : #include "tree-pass.h"
85 : #include "ssa.h"
86 : #include "cgraph.h"
87 : #include "gimple-pretty-print.h"
88 : #include "alias.h"
89 : #include "fold-const.h"
90 : #include "tree-eh.h"
91 : #include "stor-layout.h"
92 : #include "gimplify.h"
93 : #include "gimple-iterator.h"
94 : #include "gimplify-me.h"
95 : #include "gimple-walk.h"
96 : #include "tree-cfg.h"
97 : #include "tree-dfa.h"
98 : #include "tree-ssa.h"
99 : #include "dbgcnt.h"
100 : #include "builtins.h"
101 : #include "tree-sra.h"
102 : #include "opts.h"
103 : #include "tree-ssa-alias-compare.h"
104 :
105 : /* Enumeration of all aggregate reductions we can do. */
106 : enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
107 : SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
108 : SRA_MODE_INTRA }; /* late intraprocedural SRA */
109 :
110 : /* Global variable describing which aggregate reduction we are performing at
111 : the moment. */
112 : static enum sra_mode sra_mode;
113 :
114 : struct assign_link;
115 :
116 : /* ACCESS represents each access to an aggregate variable (as a whole or a
117 : part). It can also represent a group of accesses that refer to exactly the
118 : same fragment of an aggregate (i.e. those that have exactly the same offset
119 : and size). Such representatives for a single aggregate, once determined,
120 : are linked in a linked list and have the group fields set.
121 :
122 : Moreover, when doing intraprocedural SRA, a tree is built from those
123 : representatives (by the means of first_child and next_sibling pointers), in
124 : which all items in a subtree are "within" the root, i.e. their offset is
125 : greater or equal to offset of the root and offset+size is smaller or equal
126 : to offset+size of the root. Children of an access are sorted by offset.
127 :
128 : Note that accesses to parts of vector and complex number types always
129 : represented by an access to the whole complex number or a vector. It is a
130 : duty of the modifying functions to replace them appropriately. */
131 :
132 : struct access
133 : {
134 : /* Values returned by `get_ref_base_and_extent' for each component reference
135 : If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
136 : `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
137 : HOST_WIDE_INT offset;
138 : HOST_WIDE_INT size;
139 : tree base;
140 :
141 : /* Expression. It is context dependent so do not use it to create new
142 : expressions to access the original aggregate. See PR 42154 for a
143 : testcase. */
144 : tree expr;
145 : /* Type. */
146 : tree type;
147 :
148 : /* The statement this access belongs to. */
149 : gimple *stmt;
150 :
151 : /* Next group representative for this aggregate. */
152 : struct access *next_grp;
153 :
154 : /* Pointer to the group representative. Pointer to itself if the struct is
155 : the representative. */
156 : struct access *group_representative;
157 :
158 : /* After access tree has been constructed, this points to the parent of the
159 : current access, if there is one. NULL for roots. */
160 : struct access *parent;
161 :
162 : /* If this access has any children (in terms of the definition above), this
163 : points to the first one. */
164 : struct access *first_child;
165 :
166 : /* In intraprocedural SRA, pointer to the next sibling in the access tree as
167 : described above. */
168 : struct access *next_sibling;
169 :
170 : /* Pointers to the first and last element in the linked list of assign
171 : links for propagation from LHS to RHS. */
172 : struct assign_link *first_rhs_link, *last_rhs_link;
173 :
174 : /* Pointers to the first and last element in the linked list of assign
175 : links for propagation from LHS to RHS. */
176 : struct assign_link *first_lhs_link, *last_lhs_link;
177 :
178 : /* Pointer to the next access in the work queues. */
179 : struct access *next_rhs_queued, *next_lhs_queued;
180 :
181 : /* Replacement variable for this access "region." Never to be accessed
182 : directly, always only by the means of get_access_replacement() and only
183 : when grp_to_be_replaced flag is set. */
184 : tree replacement_decl;
185 :
186 : /* Is this access made in reverse storage order? */
187 : unsigned reverse : 1;
188 :
189 : /* Is this particular access write access? */
190 : unsigned write : 1;
191 :
192 : /* Is this access currently in the rhs work queue? */
193 : unsigned grp_rhs_queued : 1;
194 :
195 : /* Is this access currently in the lhs work queue? */
196 : unsigned grp_lhs_queued : 1;
197 :
198 : /* Does this group contain a write access? This flag is propagated down the
199 : access tree. */
200 : unsigned grp_write : 1;
201 :
202 : /* Does this group contain a read access? This flag is propagated down the
203 : access tree. */
204 : unsigned grp_read : 1;
205 :
206 : /* Does this group contain a read access that comes from an assignment
207 : statement? This flag is propagated down the access tree. */
208 : unsigned grp_assignment_read : 1;
209 :
210 : /* Does this group contain a write access that comes from an assignment
211 : statement? This flag is propagated down the access tree. */
212 : unsigned grp_assignment_write : 1;
213 :
214 : /* Does this group contain a read access through a scalar type? This flag is
215 : not propagated in the access tree in any direction. */
216 : unsigned grp_scalar_read : 1;
217 :
218 : /* Does this group contain a write access through a scalar type? This flag
219 : is not propagated in the access tree in any direction. */
220 : unsigned grp_scalar_write : 1;
221 :
222 : /* In a root of an access tree, true means that the entire tree should be
223 : totally scalarized - that all scalar leafs should be scalarized and
224 : non-root grp_total_scalarization accesses should be honored. Otherwise,
225 : non-root accesses with grp_total_scalarization should never get scalar
226 : replacements. */
227 : unsigned grp_total_scalarization : 1;
228 :
229 : /* Other passes of the analysis use this bit to make function
230 : analyze_access_subtree create scalar replacements for this group if
231 : possible. */
232 : unsigned grp_hint : 1;
233 :
234 : /* Is the subtree rooted in this access fully covered by scalar
235 : replacements? */
236 : unsigned grp_covered : 1;
237 :
238 : /* If set to true, this access and all below it in an access tree must not be
239 : scalarized. */
240 : unsigned grp_unscalarizable_region : 1;
241 :
242 : /* Whether data have been written to parts of the aggregate covered by this
243 : access which is not to be scalarized. This flag is propagated up in the
244 : access tree. */
245 : unsigned grp_unscalarized_data : 1;
246 :
247 : /* Set if all accesses in the group consist of the same chain of
248 : COMPONENT_REFs and ARRAY_REFs. */
249 : unsigned grp_same_access_path : 1;
250 :
251 : /* Does this access and/or group contain a write access through a
252 : BIT_FIELD_REF? */
253 : unsigned grp_partial_lhs : 1;
254 :
255 : /* Set when a scalar replacement should be created for this variable. */
256 : unsigned grp_to_be_replaced : 1;
257 :
258 : /* Set when we want a replacement for the sole purpose of having it in
259 : generated debug statements. */
260 : unsigned grp_to_be_debug_replaced : 1;
261 :
262 : /* Should TREE_NO_WARNING of a replacement be set? */
263 : unsigned grp_no_warning : 1;
264 :
265 : /* Result of propagation accross link from LHS to RHS. */
266 : unsigned grp_result_of_prop_from_lhs : 1;
267 : };
268 :
269 : typedef struct access *access_p;
270 :
271 :
272 : /* Alloc pool for allocating access structures. */
273 : static object_allocator<struct access> access_pool ("SRA accesses");
274 :
275 : /* A structure linking lhs and rhs accesses from an aggregate assignment. They
276 : are used to propagate subaccesses from rhs to lhs and vice versa as long as
277 : they don't conflict with what is already there. In the RHS->LHS direction,
278 : we also propagate grp_write flag to lazily mark that the access contains any
279 : meaningful data. */
280 : struct assign_link
281 : {
282 : struct access *lacc, *racc;
283 : struct assign_link *next_rhs, *next_lhs;
284 : };
285 :
286 : /* Alloc pool for allocating assign link structures. */
287 : static object_allocator<assign_link> assign_link_pool ("SRA links");
288 :
289 : /* Base (tree) -> Vector (vec<access_p> *) map. */
290 : static hash_map<tree, auto_vec<access_p> > *base_access_vec;
291 :
292 : /* Hash to limit creation of artificial accesses */
293 : static hash_map<tree, unsigned> *propagation_budget;
294 :
295 : /* Candidate hash table helpers. */
296 :
297 : struct uid_decl_hasher : nofree_ptr_hash <tree_node>
298 : {
299 : static inline hashval_t hash (const tree_node *);
300 : static inline bool equal (const tree_node *, const tree_node *);
301 : };
302 :
303 : /* Hash a tree in a uid_decl_map. */
304 :
305 : inline hashval_t
306 78344004 : uid_decl_hasher::hash (const tree_node *item)
307 : {
308 78344004 : return item->decl_minimal.uid;
309 : }
310 :
311 : /* Return true if the DECL_UID in both trees are equal. */
312 :
313 : inline bool
314 90189252 : uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
315 : {
316 90189252 : return (a->decl_minimal.uid == b->decl_minimal.uid);
317 : }
318 :
319 : /* Set of candidates. */
320 : static bitmap candidate_bitmap;
321 : static hash_table<uid_decl_hasher> *candidates;
322 :
323 : /* For a candidate UID return the candidates decl. */
324 :
325 : static inline tree
326 14405321 : candidate (unsigned uid)
327 : {
328 14405321 : tree_node t;
329 14405321 : t.decl_minimal.uid = uid;
330 14405321 : return candidates->find_with_hash (&t, static_cast <hashval_t> (uid));
331 : }
332 :
333 : /* Bitmap of candidates which we should try to entirely scalarize away and
334 : those which cannot be (because they are and need be used as a whole). */
335 : static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
336 :
337 : /* Bitmap of candidates in the constant pool, which cannot be scalarized
338 : because this would produce non-constant expressions (e.g. Ada). */
339 : static bitmap disqualified_constants;
340 :
341 : /* Bitmap of candidates which are passed by reference in call arguments. */
342 : static bitmap passed_by_ref_in_call;
343 :
344 : /* Obstack for creation of fancy names. */
345 : static struct obstack name_obstack;
346 :
347 : /* Head of a linked list of accesses that need to have its subaccesses
348 : propagated to their assignment counterparts. */
349 : static struct access *rhs_work_queue_head, *lhs_work_queue_head;
350 :
351 : /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
352 : representative fields are dumped, otherwise those which only describe the
353 : individual access are. */
354 :
355 : static struct
356 : {
357 : /* Number of processed aggregates is readily available in
358 : analyze_all_variable_accesses and so is not stored here. */
359 :
360 : /* Number of created scalar replacements. */
361 : int replacements;
362 :
363 : /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
364 : expression. */
365 : int exprs;
366 :
367 : /* Number of statements created by generate_subtree_copies. */
368 : int subtree_copies;
369 :
370 : /* Number of statements created by load_assign_lhs_subreplacements. */
371 : int subreplacements;
372 :
373 : /* Number of times sra_modify_assign has deleted a statement. */
374 : int deleted;
375 :
376 : /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
377 : RHS reparately due to type conversions or nonexistent matching
378 : references. */
379 : int separate_lhs_rhs_handling;
380 :
381 : /* Number of parameters that were removed because they were unused. */
382 : int deleted_unused_parameters;
383 :
384 : /* Number of scalars passed as parameters by reference that have been
385 : converted to be passed by value. */
386 : int scalar_by_ref_to_by_val;
387 :
388 : /* Number of aggregate parameters that were replaced by one or more of their
389 : components. */
390 : int aggregate_params_reduced;
391 :
392 : /* Numbber of components created when splitting aggregate parameters. */
393 : int param_reductions_created;
394 :
395 : /* Number of deferred_init calls that are modified. */
396 : int deferred_init;
397 :
398 : /* Number of deferred_init calls that are created by
399 : generate_subtree_deferred_init. */
400 : int subtree_deferred_init;
401 : } sra_stats;
402 :
403 : static void
404 26 : dump_access (FILE *f, struct access *access, bool grp)
405 : {
406 26 : fprintf (f, "access { ");
407 26 : fprintf (f, "base = (%d)'", DECL_UID (access->base));
408 26 : print_generic_expr (f, access->base);
409 26 : fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
410 26 : fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
411 26 : fprintf (f, ", expr = ");
412 26 : print_generic_expr (f, access->expr);
413 26 : fprintf (f, ", type = ");
414 26 : print_generic_expr (f, access->type);
415 26 : fprintf (f, ", reverse = %d", access->reverse);
416 26 : if (grp)
417 26 : fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
418 : "grp_assignment_write = %d, grp_scalar_read = %d, "
419 : "grp_scalar_write = %d, grp_total_scalarization = %d, "
420 : "grp_hint = %d, grp_covered = %d, "
421 : "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
422 : "grp_same_access_path = %d, grp_partial_lhs = %d, "
423 : "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d}\n",
424 26 : access->grp_read, access->grp_write, access->grp_assignment_read,
425 26 : access->grp_assignment_write, access->grp_scalar_read,
426 26 : access->grp_scalar_write, access->grp_total_scalarization,
427 26 : access->grp_hint, access->grp_covered,
428 26 : access->grp_unscalarizable_region, access->grp_unscalarized_data,
429 26 : access->grp_same_access_path, access->grp_partial_lhs,
430 26 : access->grp_to_be_replaced, access->grp_to_be_debug_replaced);
431 : else
432 0 : fprintf (f, ", write = %d, grp_total_scalarization = %d, "
433 : "grp_partial_lhs = %d}\n",
434 0 : access->write, access->grp_total_scalarization,
435 0 : access->grp_partial_lhs);
436 26 : }
437 :
438 : /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
439 :
440 : static void
441 16 : dump_access_tree_1 (FILE *f, struct access *access, int level)
442 : {
443 26 : do
444 : {
445 26 : int i;
446 :
447 43 : for (i = 0; i < level; i++)
448 17 : fputs ("* ", f);
449 :
450 26 : dump_access (f, access, true);
451 :
452 26 : if (access->first_child)
453 7 : dump_access_tree_1 (f, access->first_child, level + 1);
454 :
455 26 : access = access->next_sibling;
456 : }
457 26 : while (access);
458 16 : }
459 :
460 : /* Dump all access trees for a variable, given the pointer to the first root in
461 : ACCESS. */
462 :
463 : static void
464 8 : dump_access_tree (FILE *f, struct access *access)
465 : {
466 17 : for (; access; access = access->next_grp)
467 9 : dump_access_tree_1 (f, access, 0);
468 8 : }
469 :
470 : /* Return true iff ACC is non-NULL and has subaccesses. */
471 :
472 : static inline bool
473 15948461 : access_has_children_p (struct access *acc)
474 : {
475 8495330 : return acc && acc->first_child;
476 : }
477 :
478 : /* Return true iff ACC is (partly) covered by at least one replacement. */
479 :
480 : static bool
481 550 : access_has_replacements_p (struct access *acc)
482 : {
483 550 : struct access *child;
484 550 : if (acc->grp_to_be_replaced)
485 : return true;
486 556 : for (child = acc->first_child; child; child = child->next_sibling)
487 6 : if (access_has_replacements_p (child))
488 : return true;
489 : return false;
490 : }
491 :
492 : /* Return a vector of pointers to accesses for the variable given in BASE or
493 : NULL if there is none. */
494 :
495 : static vec<access_p> *
496 23256688 : get_base_access_vector (tree base)
497 : {
498 0 : return base_access_vec->get (base);
499 : }
500 :
501 : /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
502 : in ACCESS. Return NULL if it cannot be found. */
503 :
504 : static struct access *
505 10244976 : find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
506 : HOST_WIDE_INT size)
507 : {
508 26123461 : while (access && (access->offset != offset || access->size != size))
509 : {
510 5633509 : struct access *child = access->first_child;
511 :
512 12228144 : while (child && (child->offset + child->size <= offset))
513 6594635 : child = child->next_sibling;
514 : access = child;
515 : }
516 :
517 : /* Total scalarization does not replace single field structures with their
518 : single field but rather creates an access for them underneath. Look for
519 : it. */
520 10244976 : if (access)
521 10291144 : while (access->first_child
522 3108476 : && access->first_child->offset == offset
523 13312451 : && access->first_child->size == size)
524 : access = access->first_child;
525 :
526 10244976 : return access;
527 : }
528 :
529 : /* Return the first group representative for DECL or NULL if none exists. */
530 :
531 : static struct access *
532 19143551 : get_first_repr_for_decl (tree base)
533 : {
534 19143551 : vec<access_p> *access_vec;
535 :
536 19143551 : access_vec = get_base_access_vector (base);
537 19143551 : if (!access_vec)
538 : return NULL;
539 :
540 19143551 : return (*access_vec)[0];
541 : }
542 :
543 : /* Find an access representative for the variable BASE and given OFFSET and
544 : SIZE. Requires that access trees have already been built. Return NULL if
545 : it cannot be found. */
546 :
547 : static struct access *
548 9194409 : get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
549 : HOST_WIDE_INT size)
550 : {
551 9194409 : struct access *access;
552 :
553 9194409 : access = get_first_repr_for_decl (base);
554 21276812 : while (access && (access->offset + access->size <= offset))
555 2887994 : access = access->next_grp;
556 9194409 : if (!access)
557 : return NULL;
558 :
559 9194409 : return find_access_in_subtree (access, offset, size);
560 : }
561 :
562 : /* Add LINK to the linked list of assign links of RACC. */
563 :
564 : static void
565 1310149 : add_link_to_rhs (struct access *racc, struct assign_link *link)
566 : {
567 1310149 : gcc_assert (link->racc == racc);
568 :
569 1310149 : if (!racc->first_rhs_link)
570 : {
571 1310149 : gcc_assert (!racc->last_rhs_link);
572 1310149 : racc->first_rhs_link = link;
573 : }
574 : else
575 0 : racc->last_rhs_link->next_rhs = link;
576 :
577 1310149 : racc->last_rhs_link = link;
578 1310149 : link->next_rhs = NULL;
579 1310149 : }
580 :
581 : /* Add LINK to the linked list of lhs assign links of LACC. */
582 :
583 : static void
584 1310149 : add_link_to_lhs (struct access *lacc, struct assign_link *link)
585 : {
586 1310149 : gcc_assert (link->lacc == lacc);
587 :
588 1310149 : if (!lacc->first_lhs_link)
589 : {
590 1310149 : gcc_assert (!lacc->last_lhs_link);
591 1310149 : lacc->first_lhs_link = link;
592 : }
593 : else
594 0 : lacc->last_lhs_link->next_lhs = link;
595 :
596 1310149 : lacc->last_lhs_link = link;
597 1310149 : link->next_lhs = NULL;
598 1310149 : }
599 :
600 : /* Move all link structures in their linked list in OLD_ACC to the linked list
601 : in NEW_ACC. */
602 : static void
603 5222763 : relink_to_new_repr (struct access *new_acc, struct access *old_acc)
604 : {
605 5222763 : if (old_acc->first_rhs_link)
606 : {
607 :
608 855958 : if (new_acc->first_rhs_link)
609 : {
610 279851 : gcc_assert (!new_acc->last_rhs_link->next_rhs);
611 279851 : gcc_assert (!old_acc->last_rhs_link
612 : || !old_acc->last_rhs_link->next_rhs);
613 :
614 279851 : new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link;
615 279851 : new_acc->last_rhs_link = old_acc->last_rhs_link;
616 : }
617 : else
618 : {
619 576107 : gcc_assert (!new_acc->last_rhs_link);
620 :
621 576107 : new_acc->first_rhs_link = old_acc->first_rhs_link;
622 576107 : new_acc->last_rhs_link = old_acc->last_rhs_link;
623 : }
624 855958 : old_acc->first_rhs_link = old_acc->last_rhs_link = NULL;
625 : }
626 : else
627 4366805 : gcc_assert (!old_acc->last_rhs_link);
628 :
629 5222763 : if (old_acc->first_lhs_link)
630 : {
631 :
632 353282 : if (new_acc->first_lhs_link)
633 : {
634 151067 : gcc_assert (!new_acc->last_lhs_link->next_lhs);
635 151067 : gcc_assert (!old_acc->last_lhs_link
636 : || !old_acc->last_lhs_link->next_lhs);
637 :
638 151067 : new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link;
639 151067 : new_acc->last_lhs_link = old_acc->last_lhs_link;
640 : }
641 : else
642 : {
643 202215 : gcc_assert (!new_acc->last_lhs_link);
644 :
645 202215 : new_acc->first_lhs_link = old_acc->first_lhs_link;
646 202215 : new_acc->last_lhs_link = old_acc->last_lhs_link;
647 : }
648 353282 : old_acc->first_lhs_link = old_acc->last_lhs_link = NULL;
649 : }
650 : else
651 4869481 : gcc_assert (!old_acc->last_lhs_link);
652 :
653 5222763 : }
654 :
655 : /* Add ACCESS to the work to queue for propagation of subaccesses from RHS to
656 : LHS (which is actually a stack). */
657 :
658 : static void
659 4618006 : add_access_to_rhs_work_queue (struct access *access)
660 : {
661 4618006 : if (access->first_rhs_link && !access->grp_rhs_queued)
662 : {
663 1515181 : gcc_assert (!access->next_rhs_queued);
664 1515181 : access->next_rhs_queued = rhs_work_queue_head;
665 1515181 : access->grp_rhs_queued = 1;
666 1515181 : rhs_work_queue_head = access;
667 : }
668 4618006 : }
669 :
670 : /* Add ACCESS to the work to queue for propagation of subaccesses from LHS to
671 : RHS (which is actually a stack). */
672 :
673 : static void
674 1658617 : add_access_to_lhs_work_queue (struct access *access)
675 : {
676 1658617 : if (access->first_lhs_link && !access->grp_lhs_queued)
677 : {
678 1311939 : gcc_assert (!access->next_lhs_queued);
679 1311939 : access->next_lhs_queued = lhs_work_queue_head;
680 1311939 : access->grp_lhs_queued = 1;
681 1311939 : lhs_work_queue_head = access;
682 : }
683 1658617 : }
684 :
685 : /* Pop an access from the work queue for propagating from RHS to LHS, and
686 : return it, assuming there is one. */
687 :
688 : static struct access *
689 1515181 : pop_access_from_rhs_work_queue (void)
690 : {
691 1515181 : struct access *access = rhs_work_queue_head;
692 :
693 1515181 : rhs_work_queue_head = access->next_rhs_queued;
694 1515181 : access->next_rhs_queued = NULL;
695 1515181 : access->grp_rhs_queued = 0;
696 1515181 : return access;
697 : }
698 :
699 : /* Pop an access from the work queue for propagating from LHS to RHS, and
700 : return it, assuming there is one. */
701 :
702 : static struct access *
703 1311939 : pop_access_from_lhs_work_queue (void)
704 : {
705 1311939 : struct access *access = lhs_work_queue_head;
706 :
707 1311939 : lhs_work_queue_head = access->next_lhs_queued;
708 1311939 : access->next_lhs_queued = NULL;
709 1311939 : access->grp_lhs_queued = 0;
710 1311939 : return access;
711 : }
712 :
713 : /* Allocate necessary structures. */
714 :
715 : static void
716 3475668 : sra_initialize (void)
717 : {
718 3475668 : candidate_bitmap = BITMAP_ALLOC (NULL);
719 6951336 : candidates = new hash_table<uid_decl_hasher>
720 6470470 : (vec_safe_length (cfun->local_decls) / 2);
721 3475668 : should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
722 3475668 : cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
723 3475668 : disqualified_constants = BITMAP_ALLOC (NULL);
724 3475668 : passed_by_ref_in_call = BITMAP_ALLOC (NULL);
725 3475668 : gcc_obstack_init (&name_obstack);
726 3475668 : base_access_vec = new hash_map<tree, auto_vec<access_p> >;
727 3475668 : memset (&sra_stats, 0, sizeof (sra_stats));
728 3475668 : }
729 :
730 : /* Deallocate all general structures. */
731 :
732 : static void
733 3475668 : sra_deinitialize (void)
734 : {
735 3475668 : BITMAP_FREE (candidate_bitmap);
736 3475668 : delete candidates;
737 3475668 : candidates = NULL;
738 3475668 : BITMAP_FREE (should_scalarize_away_bitmap);
739 3475668 : BITMAP_FREE (cannot_scalarize_away_bitmap);
740 3475668 : BITMAP_FREE (disqualified_constants);
741 3475668 : BITMAP_FREE (passed_by_ref_in_call);
742 3475668 : access_pool.release ();
743 3475668 : assign_link_pool.release ();
744 3475668 : obstack_free (&name_obstack, NULL);
745 :
746 6951336 : delete base_access_vec;
747 3475668 : }
748 :
749 : /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
750 :
751 41729781 : static bool constant_decl_p (tree decl)
752 : {
753 36112527 : return VAR_P (decl) && DECL_IN_CONSTANT_POOL (decl);
754 : }
755 :
756 : /* Remove DECL from candidates for SRA and write REASON to the dump file if
757 : there is one. */
758 :
759 : static void
760 4382995 : disqualify_candidate (tree decl, const char *reason)
761 : {
762 4382995 : if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
763 2334216 : candidates->remove_elt_with_hash (decl, DECL_UID (decl));
764 4382995 : if (constant_decl_p (decl))
765 4143 : bitmap_set_bit (disqualified_constants, DECL_UID (decl));
766 :
767 4382995 : if (dump_file && (dump_flags & TDF_DETAILS))
768 : {
769 24 : fprintf (dump_file, "! Disqualifying ");
770 24 : print_generic_expr (dump_file, decl);
771 24 : fprintf (dump_file, " - %s\n", reason);
772 : }
773 4382995 : }
774 :
775 : /* Return true iff the type contains a field or an element which does not allow
776 : scalarization. Use VISITED_TYPES to avoid re-checking already checked
777 : (sub-)types. */
778 :
779 : static bool
780 8203955 : type_internals_preclude_sra_p_1 (tree type, const char **msg,
781 : hash_set<tree> *visited_types)
782 : {
783 8203955 : tree fld;
784 8203955 : tree et;
785 :
786 8203955 : if (visited_types->contains (type))
787 : return false;
788 7906271 : visited_types->add (type);
789 :
790 7906271 : switch (TREE_CODE (type))
791 : {
792 7242359 : case RECORD_TYPE:
793 7242359 : case UNION_TYPE:
794 7242359 : case QUAL_UNION_TYPE:
795 140601836 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
796 133369936 : if (TREE_CODE (fld) == FIELD_DECL)
797 : {
798 16628201 : if (TREE_CODE (fld) == FUNCTION_DECL)
799 : continue;
800 16628201 : tree ft = TREE_TYPE (fld);
801 :
802 16628201 : if (TREE_THIS_VOLATILE (fld))
803 : {
804 905 : *msg = "volatile structure field";
805 905 : return true;
806 : }
807 16627296 : if (!DECL_FIELD_OFFSET (fld))
808 : {
809 0 : *msg = "no structure field offset";
810 0 : return true;
811 : }
812 16627296 : if (!DECL_SIZE (fld))
813 : {
814 8443 : *msg = "zero structure field size";
815 8443 : return true;
816 : }
817 16618853 : if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
818 : {
819 0 : *msg = "structure field offset not fixed";
820 0 : return true;
821 : }
822 16618853 : if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
823 : {
824 0 : *msg = "structure field size not fixed";
825 0 : return true;
826 : }
827 16618853 : if (!tree_fits_shwi_p (bit_position (fld)))
828 : {
829 0 : *msg = "structure field size too big";
830 0 : return true;
831 : }
832 16618853 : if (AGGREGATE_TYPE_P (ft)
833 16618853 : && int_bit_position (fld) % BITS_PER_UNIT != 0)
834 : {
835 0 : *msg = "structure field is bit field";
836 0 : return true;
837 : }
838 :
839 16618853 : if (AGGREGATE_TYPE_P (ft)
840 16618853 : && type_internals_preclude_sra_p_1 (ft, msg, visited_types))
841 : return true;
842 : }
843 :
844 : return false;
845 :
846 543302 : case ARRAY_TYPE:
847 543302 : et = TREE_TYPE (type);
848 :
849 543302 : if (TYPE_VOLATILE (et))
850 : {
851 0 : *msg = "element type is volatile";
852 0 : return true;
853 : }
854 :
855 543302 : if (AGGREGATE_TYPE_P (et)
856 543302 : && type_internals_preclude_sra_p_1 (et, msg, visited_types))
857 : return true;
858 :
859 : return false;
860 :
861 : default:
862 : return false;
863 : }
864 : }
865 :
866 : /* Return true iff the type contains a field or an element which does not allow
867 : scalarization. */
868 :
869 : bool
870 4778360 : type_internals_preclude_sra_p (tree type, const char **msg)
871 : {
872 4778360 : hash_set<tree> visited_types;
873 4778360 : return type_internals_preclude_sra_p_1 (type, msg, &visited_types);
874 4778360 : }
875 :
876 :
877 : /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
878 : the three fields. Also add it to the vector of accesses corresponding to
879 : the base. Finally, return the new access. */
880 :
881 : static struct access *
882 14666479 : create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
883 : {
884 14666479 : struct access *access = access_pool.allocate ();
885 :
886 14666479 : memset (access, 0, sizeof (struct access));
887 14666479 : access->base = base;
888 14666479 : access->offset = offset;
889 14666479 : access->size = size;
890 :
891 14666479 : base_access_vec->get_or_insert (base).safe_push (access);
892 :
893 14666479 : return access;
894 : }
895 :
896 : static bool maybe_add_sra_candidate (tree);
897 :
898 : /* Create and insert access for EXPR. Return created access, or NULL if it is
899 : not possible. Also scan for uses of constant pool as we go along and add
900 : to candidates. */
901 :
902 : static struct access *
903 28035058 : create_access (tree expr, gimple *stmt, bool write)
904 : {
905 28035058 : struct access *access;
906 28035058 : poly_int64 poffset, psize, pmax_size;
907 28035058 : tree base = expr;
908 28035058 : bool reverse, unscalarizable_region = false;
909 :
910 28035058 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
911 : &reverse);
912 :
913 : /* For constant-pool entries, check we can substitute the constant value. */
914 28035058 : if (constant_decl_p (base)
915 3788 : && !bitmap_bit_p (disqualified_constants, DECL_UID (base)))
916 : {
917 3788 : if (expr != base
918 349 : && !is_gimple_reg_type (TREE_TYPE (expr))
919 3874 : && dump_file && (dump_flags & TDF_DETAILS))
920 : {
921 : /* This occurs in Ada with accesses to ARRAY_RANGE_REFs,
922 : and elements of multidimensional arrays (which are
923 : multi-element arrays in their own right). */
924 0 : fprintf (dump_file, "Allowing non-reg-type load of part"
925 : " of constant-pool entry: ");
926 0 : print_generic_expr (dump_file, expr);
927 : }
928 3788 : maybe_add_sra_candidate (base);
929 : }
930 :
931 28035058 : if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
932 13358862 : return NULL;
933 :
934 14676196 : if (write && TREE_READONLY (base))
935 : {
936 8819 : disqualify_candidate (base, "Encountered a store to a read-only decl.");
937 8819 : return NULL;
938 : }
939 :
940 14667377 : HOST_WIDE_INT offset, size, max_size;
941 14667377 : if (!poffset.is_constant (&offset)
942 14667377 : || !psize.is_constant (&size)
943 14667377 : || !pmax_size.is_constant (&max_size))
944 : {
945 : disqualify_candidate (base, "Encountered a polynomial-sized access.");
946 : return NULL;
947 : }
948 :
949 14667377 : if (size != max_size)
950 : {
951 378855 : size = max_size;
952 378855 : unscalarizable_region = true;
953 : }
954 14667377 : if (size == 0)
955 : return NULL;
956 14667375 : if (offset < 0)
957 : {
958 34 : disqualify_candidate (base, "Encountered a negative offset access.");
959 34 : return NULL;
960 : }
961 14667341 : if (size < 0)
962 : {
963 24 : disqualify_candidate (base, "Encountered an unconstrained access.");
964 24 : return NULL;
965 : }
966 14667317 : if (offset + size > tree_to_shwi (DECL_SIZE (base)))
967 : {
968 837 : disqualify_candidate (base, "Encountered an access beyond the base.");
969 837 : return NULL;
970 : }
971 14666480 : if (BITINT_TYPE_P (TREE_TYPE (expr)) && size > WIDE_INT_MAX_PRECISION - 1)
972 : {
973 1 : disqualify_candidate (base, "Encountered too large _BitInt access.");
974 1 : return NULL;
975 : }
976 :
977 14666479 : access = create_access_1 (base, offset, size);
978 14666479 : access->expr = expr;
979 14666479 : access->type = TREE_TYPE (expr);
980 14666479 : access->write = write;
981 14666479 : access->grp_unscalarizable_region = unscalarizable_region;
982 14666479 : access->grp_same_access_path = true;
983 14666479 : access->stmt = stmt;
984 14666479 : access->reverse = reverse;
985 :
986 14666479 : return access;
987 : }
988 :
989 : /* Given an array type TYPE, extract element size to *EL_SIZE, minimum index to
990 : *IDX and maximum index to *MAX so that the caller can iterate over all
991 : elements and return true, except if the array is known to be zero-length,
992 : then return false. */
993 :
994 : static bool
995 21568 : prepare_iteration_over_array_elts (tree type, HOST_WIDE_INT *el_size,
996 : offset_int *idx, offset_int *max)
997 : {
998 21568 : tree elem_size = TYPE_SIZE (TREE_TYPE (type));
999 21568 : gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
1000 21568 : *el_size = tree_to_shwi (elem_size);
1001 21568 : gcc_assert (*el_size > 0);
1002 :
1003 21568 : tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1004 21568 : gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1005 21568 : tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1006 : /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1007 21568 : if (!maxidx)
1008 : return false;
1009 21568 : gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1010 21568 : tree domain = TYPE_DOMAIN (type);
1011 : /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1012 : DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1013 21568 : *idx = wi::to_offset (minidx);
1014 21568 : *max = wi::to_offset (maxidx);
1015 21568 : if (!TYPE_UNSIGNED (domain))
1016 : {
1017 21568 : *idx = wi::sext (*idx, TYPE_PRECISION (domain));
1018 21568 : *max = wi::sext (*max, TYPE_PRECISION (domain));
1019 : }
1020 : return true;
1021 : }
1022 :
1023 : /* A structure to track collecting padding and hold collected padding
1024 : information. */
1025 :
1026 73391 : class sra_padding_collecting
1027 : {
1028 : public:
1029 : /* Given that there won't be any data until at least OFFSET, add an
1030 : appropriate entry to the list of paddings or extend the last one. */
1031 : void record_padding (HOST_WIDE_INT offset);
1032 : /* Vector of pairs describing contiguous pieces of padding, each pair
1033 : consisting of offset and length. */
1034 : auto_vec<std::pair<HOST_WIDE_INT, HOST_WIDE_INT>, 10> m_padding;
1035 : /* Offset where data should continue after the last seen actual bit of data
1036 : if there was no padding. */
1037 : HOST_WIDE_INT m_data_until = 0;
1038 : };
1039 :
1040 : /* Given that there won't be any data until at least OFFSET, add an appropriate
1041 : entry to the list of paddings or extend the last one. */
1042 :
1043 207690 : void sra_padding_collecting::record_padding (HOST_WIDE_INT offset)
1044 : {
1045 207690 : if (offset > m_data_until)
1046 : {
1047 13524 : HOST_WIDE_INT psz = offset - m_data_until;
1048 13524 : if (!m_padding.is_empty ()
1049 574 : && ((m_padding[m_padding.length () - 1].first
1050 574 : + m_padding[m_padding.length () - 1].second) == offset))
1051 0 : m_padding[m_padding.length () - 1].second += psz;
1052 : else
1053 13524 : m_padding.safe_push (std::make_pair (m_data_until, psz));
1054 : }
1055 207690 : }
1056 :
1057 : /* Return true iff TYPE is totally scalarizable - i.e. a RECORD_TYPE or
1058 : fixed-length ARRAY_TYPE with fields that are either of gimple register types
1059 : (excluding bit-fields) or (recursively) scalarizable types. CONST_DECL must
1060 : be true if we are considering a decl from constant pool. If it is false,
1061 : char arrays will be refused.
1062 :
1063 : TOTAL_OFFSET is the offset of TYPE within any outer type that is being
1064 : examined.
1065 :
1066 : If PC is non-NULL, collect padding information into the vector within the
1067 : structure. The information is however only complete if the function returns
1068 : true and does not contain any padding at its end. */
1069 :
1070 : static bool
1071 2859697 : totally_scalarizable_type_p (tree type, bool const_decl,
1072 : HOST_WIDE_INT total_offset,
1073 : sra_padding_collecting *pc)
1074 : {
1075 2859697 : if (is_gimple_reg_type (type))
1076 : {
1077 1836274 : if (pc)
1078 : {
1079 134194 : pc->record_padding (total_offset);
1080 134194 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1081 : }
1082 1836274 : return true;
1083 : }
1084 1023423 : if (type_contains_placeholder_p (type))
1085 : return false;
1086 :
1087 1023423 : bool have_predecessor_field = false;
1088 1023423 : HOST_WIDE_INT prev_pos = 0;
1089 :
1090 1023423 : switch (TREE_CODE (type))
1091 : {
1092 979352 : case RECORD_TYPE:
1093 14627337 : for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1094 13677256 : if (TREE_CODE (fld) == FIELD_DECL)
1095 : {
1096 2076457 : tree ft = TREE_TYPE (fld);
1097 :
1098 2076457 : if (!DECL_SIZE (fld))
1099 : return false;
1100 2076457 : if (zerop (DECL_SIZE (fld)))
1101 52741 : continue;
1102 :
1103 2023716 : HOST_WIDE_INT pos = int_bit_position (fld);
1104 2023716 : if (have_predecessor_field
1105 2023716 : && pos <= prev_pos)
1106 : return false;
1107 :
1108 2023716 : have_predecessor_field = true;
1109 2023716 : prev_pos = pos;
1110 :
1111 2023716 : if (DECL_BIT_FIELD (fld))
1112 : return false;
1113 :
1114 2022096 : if (!totally_scalarizable_type_p (ft, const_decl, total_offset + pos,
1115 : pc))
1116 : return false;
1117 : }
1118 :
1119 : return true;
1120 :
1121 28047 : case ARRAY_TYPE:
1122 28047 : {
1123 28047 : HOST_WIDE_INT min_elem_size;
1124 28047 : if (const_decl)
1125 : min_elem_size = 0;
1126 : else
1127 19884 : min_elem_size = BITS_PER_UNIT;
1128 :
1129 28047 : if (TYPE_DOMAIN (type) == NULL_TREE
1130 28047 : || !tree_fits_shwi_p (TYPE_SIZE (type))
1131 28047 : || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1132 28047 : || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1133 50531 : || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1134 : return false;
1135 22484 : if (tree_to_shwi (TYPE_SIZE (type)) == 0
1136 22484 : && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1137 : /* Zero-element array, should not prevent scalarization. */
1138 : ;
1139 22484 : else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1140 22484 : || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1141 : /* Variable-length array, do not allow scalarization. */
1142 : return false;
1143 :
1144 22448 : unsigned old_padding_len = 0;
1145 22448 : if (pc)
1146 8002 : old_padding_len = pc->m_padding.length ();
1147 22448 : tree elem = TREE_TYPE (type);
1148 22448 : if (!totally_scalarizable_type_p (elem, const_decl, total_offset, pc))
1149 : return false;
1150 22309 : if (pc)
1151 : {
1152 8002 : unsigned new_padding_len = pc->m_padding.length ();
1153 8002 : HOST_WIDE_INT el_size;
1154 8002 : offset_int idx, max;
1155 8002 : if (!prepare_iteration_over_array_elts (type, &el_size, &idx, &max))
1156 0 : return true;
1157 8002 : pc->record_padding (total_offset + el_size);
1158 8002 : ++idx;
1159 8002 : for (HOST_WIDE_INT pos = total_offset + el_size;
1160 158590 : idx <= max;
1161 150588 : pos += el_size, ++idx)
1162 : {
1163 150615 : for (unsigned i = old_padding_len; i < new_padding_len; i++)
1164 : {
1165 27 : HOST_WIDE_INT pp
1166 27 : = pos + pc->m_padding[i].first - total_offset;
1167 27 : HOST_WIDE_INT psz = pc->m_padding[i].second;
1168 27 : pc->m_padding.safe_push (std::make_pair (pp, psz));
1169 : }
1170 : }
1171 8002 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1172 : }
1173 : return true;
1174 : }
1175 : default:
1176 : return false;
1177 : }
1178 : }
1179 :
1180 : /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1181 :
1182 : static inline bool
1183 57809944 : contains_view_convert_expr_p (const_tree ref)
1184 : {
1185 79715059 : while (handled_component_p (ref))
1186 : {
1187 21915340 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1188 : return true;
1189 21905115 : ref = TREE_OPERAND (ref, 0);
1190 : }
1191 :
1192 : return false;
1193 : }
1194 :
1195 : /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1196 : bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1197 : it points to will be set if REF contains any of the above or a MEM_REF
1198 : expression that effectively performs type conversion. */
1199 :
1200 : static bool
1201 7624081 : contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1202 : {
1203 9849617 : while (handled_component_p (ref))
1204 : {
1205 2609800 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1206 2609800 : || (TREE_CODE (ref) == COMPONENT_REF
1207 1894726 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1208 : {
1209 384264 : if (type_changing_p)
1210 200087 : *type_changing_p = true;
1211 384264 : return true;
1212 : }
1213 2225536 : ref = TREE_OPERAND (ref, 0);
1214 : }
1215 :
1216 7239817 : if (!type_changing_p
1217 3501670 : || TREE_CODE (ref) != MEM_REF
1218 7359017 : || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1219 : return false;
1220 :
1221 119200 : tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1222 119200 : if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1223 119200 : != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1224 93910 : *type_changing_p = true;
1225 :
1226 : return false;
1227 : }
1228 :
1229 : /* Search the given tree for a declaration by skipping handled components and
1230 : exclude it from the candidates. */
1231 :
1232 : static void
1233 998227 : disqualify_base_of_expr (tree t, const char *reason)
1234 : {
1235 998227 : t = get_base_address (t);
1236 998227 : if (t && DECL_P (t))
1237 830400 : disqualify_candidate (t, reason);
1238 998227 : }
1239 :
1240 : /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1241 :
1242 : static bool
1243 140825 : sra_handled_bf_read_p (tree expr)
1244 : {
1245 140825 : uint64_t size, offset;
1246 140825 : if (bit_field_size (expr).is_constant (&size)
1247 140825 : && bit_field_offset (expr).is_constant (&offset)
1248 140825 : && size % BITS_PER_UNIT == 0
1249 140825 : && offset % BITS_PER_UNIT == 0
1250 140893 : && pow2p_hwi (size))
1251 140733 : return true;
1252 : return false;
1253 : }
1254 :
1255 : /* Scan expression EXPR and create access structures for all accesses to
1256 : candidates for scalarization. Return the created access or NULL if none is
1257 : created. */
1258 :
1259 : static struct access *
1260 59806861 : build_access_from_expr_1 (tree expr, gimple *stmt, bool write)
1261 : {
1262 : /* We only allow ADDR_EXPRs in arguments of function calls and those must
1263 : have been dealt with in build_access_from_call_arg. Any other address
1264 : taking should have been caught by scan_visit_addr. */
1265 59806861 : if (TREE_CODE (expr) == ADDR_EXPR)
1266 : {
1267 1996916 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1268 1996916 : gcc_assert (!DECL_P (base)
1269 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)));
1270 1996916 : return NULL;
1271 : }
1272 :
1273 57809945 : struct access *ret = NULL;
1274 57809945 : bool partial_ref;
1275 :
1276 57809945 : if ((TREE_CODE (expr) == BIT_FIELD_REF
1277 79897 : && (write || !sra_handled_bf_read_p (expr)))
1278 57808827 : || TREE_CODE (expr) == IMAGPART_EXPR
1279 115594113 : || TREE_CODE (expr) == REALPART_EXPR)
1280 : {
1281 49188 : expr = TREE_OPERAND (expr, 0);
1282 49188 : partial_ref = true;
1283 : }
1284 : else
1285 : partial_ref = false;
1286 :
1287 57809945 : if (storage_order_barrier_p (expr))
1288 : {
1289 1 : disqualify_base_of_expr (expr, "storage order barrier.");
1290 1 : return NULL;
1291 : }
1292 :
1293 : /* We are capable of handling the topmost V_C_E but not any of those
1294 : buried in other handled components. */
1295 58101243 : if (contains_view_convert_expr_p (TREE_CODE (expr) == VIEW_CONVERT_EXPR
1296 291299 : ? TREE_OPERAND (expr, 0) : expr))
1297 : {
1298 10225 : disqualify_base_of_expr (expr, "V_C_E under a different handled "
1299 : "component.");
1300 10225 : return NULL;
1301 : }
1302 :
1303 57799719 : if (TREE_THIS_VOLATILE (expr))
1304 : {
1305 21997 : disqualify_base_of_expr (expr, "part of a volatile reference.");
1306 21997 : return NULL;
1307 : }
1308 :
1309 57777722 : switch (TREE_CODE (expr))
1310 : {
1311 3529222 : case MEM_REF:
1312 3529222 : if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR)
1313 : return NULL;
1314 : /* fall through */
1315 28035058 : case VAR_DECL:
1316 28035058 : case PARM_DECL:
1317 28035058 : case RESULT_DECL:
1318 28035058 : case COMPONENT_REF:
1319 28035058 : case ARRAY_REF:
1320 28035058 : case ARRAY_RANGE_REF:
1321 28035058 : case BIT_FIELD_REF:
1322 28035058 : case VIEW_CONVERT_EXPR:
1323 28035058 : ret = create_access (expr, stmt, write);
1324 28035058 : break;
1325 :
1326 : default:
1327 : break;
1328 : }
1329 :
1330 56008566 : if (write && partial_ref && ret)
1331 4353 : ret->grp_partial_lhs = 1;
1332 :
1333 : return ret;
1334 : }
1335 :
1336 : /* Scan expression EXPR and create access structures for all accesses to
1337 : candidates for scalarization. Return true if any access has been inserted.
1338 : STMT must be the statement from which the expression is taken, WRITE must be
1339 : true if the expression is a store and false otherwise. */
1340 :
1341 : static bool
1342 16586742 : build_access_from_expr (tree expr, gimple *stmt, bool write)
1343 : {
1344 16586742 : struct access *access;
1345 :
1346 16586742 : access = build_access_from_expr_1 (expr, stmt, write);
1347 16586742 : if (access)
1348 : {
1349 : /* This means the aggregate is accesses as a whole in a way other than an
1350 : assign statement and thus cannot be removed even if we had a scalar
1351 : replacement for everything. */
1352 2520042 : if (cannot_scalarize_away_bitmap)
1353 2520042 : bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1354 2520042 : return true;
1355 : }
1356 : return false;
1357 : }
1358 :
1359 : enum out_edge_check { SRA_OUTGOING_EDGES_UNCHECKED, SRA_OUTGOING_EDGES_OK,
1360 : SRA_OUTGOING_EDGES_FAIL };
1361 :
1362 : /* Return true if STMT terminates BB and there is an abnormal edge going out of
1363 : the BB and remember the decision in OE_CHECK. */
1364 :
1365 : static bool
1366 3006474 : abnormal_edge_after_stmt_p (gimple *stmt, enum out_edge_check *oe_check)
1367 : {
1368 3006474 : if (*oe_check == SRA_OUTGOING_EDGES_OK)
1369 : return false;
1370 1751843 : if (*oe_check == SRA_OUTGOING_EDGES_FAIL)
1371 : return true;
1372 1751617 : if (stmt_ends_bb_p (stmt))
1373 : {
1374 712754 : edge e;
1375 712754 : edge_iterator ei;
1376 1851043 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1377 1138775 : if (e->flags & EDGE_ABNORMAL)
1378 : {
1379 486 : *oe_check = SRA_OUTGOING_EDGES_FAIL;
1380 486 : return true;
1381 : }
1382 : }
1383 1751131 : *oe_check = SRA_OUTGOING_EDGES_OK;
1384 1751131 : return false;
1385 : }
1386 :
1387 : /* Scan expression EXPR which is an argument of a call and create access
1388 : structures for all accesses to candidates for scalarization. Return true
1389 : if any access has been inserted. STMT must be the statement from which the
1390 : expression is taken. CAN_BE_RETURNED must be true if call argument flags
1391 : do not rule out that the argument is directly returned. OE_CHECK is used
1392 : to remember result of a test for abnormal outgoing edges after this
1393 : statement. */
1394 :
1395 : static bool
1396 11757560 : build_access_from_call_arg (tree expr, gimple *stmt, bool can_be_returned,
1397 : enum out_edge_check *oe_check)
1398 : {
1399 11757560 : if (gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
1400 : {
1401 57 : tree base = expr;
1402 57 : if (TREE_CODE (expr) == ADDR_EXPR)
1403 10 : base = get_base_address (TREE_OPERAND (expr, 0));
1404 57 : disqualify_base_of_expr (base, "Passed to a returns_twice call.");
1405 57 : return false;
1406 : }
1407 :
1408 11757503 : if (TREE_CODE (expr) == ADDR_EXPR)
1409 : {
1410 3971128 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1411 :
1412 3971128 : if (can_be_returned)
1413 : {
1414 964654 : disqualify_base_of_expr (base, "Address possibly returned, "
1415 : "leading to an alis SRA may not know.");
1416 964654 : return false;
1417 : }
1418 3006474 : if (abnormal_edge_after_stmt_p (stmt, oe_check))
1419 : {
1420 712 : disqualify_base_of_expr (base, "May lead to need to add statements "
1421 : "to abnormal edge.");
1422 712 : return false;
1423 : }
1424 :
1425 3005762 : bool read = build_access_from_expr (base, stmt, false);
1426 3005762 : bool write = build_access_from_expr (base, stmt, true);
1427 3005762 : if (read || write)
1428 : {
1429 278181 : if (dump_file && (dump_flags & TDF_DETAILS))
1430 : {
1431 0 : fprintf (dump_file, "Allowed ADDR_EXPR of ");
1432 0 : print_generic_expr (dump_file, base);
1433 0 : fprintf (dump_file, " because of ");
1434 0 : print_gimple_stmt (dump_file, stmt, 0);
1435 0 : fprintf (dump_file, "\n");
1436 : }
1437 278181 : bitmap_set_bit (passed_by_ref_in_call, DECL_UID (base));
1438 278181 : return true;
1439 : }
1440 : else
1441 : return false;
1442 : }
1443 :
1444 7786375 : return build_access_from_expr (expr, stmt, false);
1445 : }
1446 :
1447 :
1448 : /* Return the single non-EH successor edge of BB or NULL if there is none or
1449 : more than one. */
1450 :
1451 : static edge
1452 1484251 : single_non_eh_succ (basic_block bb)
1453 : {
1454 1484251 : edge e, res = NULL;
1455 1484251 : edge_iterator ei;
1456 :
1457 4451284 : FOR_EACH_EDGE (e, ei, bb->succs)
1458 2967453 : if (!(e->flags & EDGE_EH))
1459 : {
1460 1484554 : if (res)
1461 : return NULL;
1462 : res = e;
1463 : }
1464 :
1465 : return res;
1466 : }
1467 :
1468 : /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1469 : there is no alternative spot where to put statements SRA might need to
1470 : generate after it. The spot we are looking for is an edge leading to a
1471 : single non-EH successor, if it exists and is indeed single. RHS may be
1472 : NULL, in that case ignore it. */
1473 :
1474 : static bool
1475 23971805 : disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1476 : {
1477 23971805 : if (stmt_ends_bb_p (stmt))
1478 : {
1479 1369534 : if (single_non_eh_succ (gimple_bb (stmt)))
1480 : return false;
1481 :
1482 537 : disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1483 537 : if (rhs)
1484 0 : disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1485 537 : return true;
1486 : }
1487 : return false;
1488 : }
1489 :
1490 : /* Return true if the nature of BASE is such that it contains data even if
1491 : there is no write to it in the function. */
1492 :
1493 : static bool
1494 4056681 : comes_initialized_p (tree base)
1495 : {
1496 0 : return TREE_CODE (base) == PARM_DECL || constant_decl_p (base);
1497 : }
1498 :
1499 : /* Scan expressions occurring in STMT, create access structures for all accesses
1500 : to candidates for scalarization and remove those candidates which occur in
1501 : statements or expressions that prevent them from being split apart. Return
1502 : true if any access has been inserted. */
1503 :
1504 : static bool
1505 32887142 : build_accesses_from_assign (gimple *stmt)
1506 : {
1507 32887142 : tree lhs, rhs;
1508 32887142 : struct access *lacc, *racc;
1509 :
1510 32887142 : if (!gimple_assign_single_p (stmt)
1511 : /* Scope clobbers don't influence scalarization. */
1512 32887142 : || gimple_clobber_p (stmt))
1513 : return false;
1514 :
1515 21555879 : lhs = gimple_assign_lhs (stmt);
1516 21555879 : rhs = gimple_assign_rhs1 (stmt);
1517 :
1518 21555879 : if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1519 : return false;
1520 :
1521 21555879 : racc = build_access_from_expr_1 (rhs, stmt, false);
1522 21555879 : lacc = build_access_from_expr_1 (lhs, stmt, true);
1523 :
1524 21555879 : bool tbaa_hazard
1525 21555879 : = !types_equal_for_same_type_for_tbaa_p (TREE_TYPE (lhs), TREE_TYPE (rhs));
1526 :
1527 21555879 : if (lacc)
1528 : {
1529 6583627 : lacc->grp_assignment_write = 1;
1530 6583627 : if (storage_order_barrier_p (rhs))
1531 1 : lacc->grp_unscalarizable_region = 1;
1532 :
1533 6583627 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1534 : {
1535 1917514 : bool type_changing_p = false;
1536 1917514 : contains_vce_or_bfcref_p (lhs, &type_changing_p);
1537 1917514 : if (type_changing_p)
1538 142408 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1539 71204 : DECL_UID (lacc->base));
1540 : }
1541 6583627 : if (tbaa_hazard)
1542 845229 : lacc->grp_same_access_path = false;
1543 : }
1544 :
1545 21555879 : if (racc)
1546 : {
1547 5515601 : racc->grp_assignment_read = 1;
1548 5515601 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1549 : {
1550 1784243 : bool type_changing_p = false;
1551 1784243 : contains_vce_or_bfcref_p (rhs, &type_changing_p);
1552 :
1553 3345693 : if (type_changing_p || gimple_has_volatile_ops (stmt))
1554 446332 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1555 223166 : DECL_UID (racc->base));
1556 : else
1557 3122154 : bitmap_set_bit (should_scalarize_away_bitmap,
1558 1561077 : DECL_UID (racc->base));
1559 : }
1560 5515601 : if (storage_order_barrier_p (lhs))
1561 0 : racc->grp_unscalarizable_region = 1;
1562 5515601 : if (tbaa_hazard)
1563 69091 : racc->grp_same_access_path = false;
1564 : }
1565 :
1566 21555879 : if (lacc && racc
1567 1311728 : && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1568 1311728 : && !lacc->grp_unscalarizable_region
1569 1311174 : && !racc->grp_unscalarizable_region
1570 1310377 : && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1571 1310377 : && lacc->size == racc->size
1572 22866028 : && useless_type_conversion_p (lacc->type, racc->type))
1573 : {
1574 1310149 : struct assign_link *link;
1575 :
1576 1310149 : link = assign_link_pool.allocate ();
1577 1310149 : memset (link, 0, sizeof (struct assign_link));
1578 :
1579 1310149 : link->lacc = lacc;
1580 1310149 : link->racc = racc;
1581 1310149 : add_link_to_rhs (racc, link);
1582 1310149 : add_link_to_lhs (lacc, link);
1583 1310149 : add_access_to_rhs_work_queue (racc);
1584 1310149 : add_access_to_lhs_work_queue (lacc);
1585 :
1586 : /* Let's delay marking the areas as written until propagation of accesses
1587 : across link, unless the nature of rhs tells us that its data comes
1588 : from elsewhere. */
1589 1310149 : if (!comes_initialized_p (racc->base))
1590 1217926 : lacc->write = false;
1591 : }
1592 :
1593 21555879 : return lacc || racc;
1594 : }
1595 :
1596 : /* Callback of walk_stmt_load_store_addr_ops visit_addr used to detect taking
1597 : addresses of candidates a places which are not call arguments. Such
1598 : candidates are disqalified from SRA. This also applies to GIMPLE_ASM
1599 : operands with memory constrains which cannot be scalarized. */
1600 :
1601 : static bool
1602 2331187 : scan_visit_addr (gimple *, tree op, tree, void *)
1603 : {
1604 2331187 : op = get_base_address (op);
1605 2331187 : if (op
1606 2331187 : && DECL_P (op))
1607 1266832 : disqualify_candidate (op, "Address taken in a non-call-argument context.");
1608 :
1609 2331187 : return false;
1610 : }
1611 :
1612 : /* Scan function and look for interesting expressions and create access
1613 : structures for them. Return true iff any access is created. */
1614 :
1615 : static bool
1616 782105 : scan_function (void)
1617 : {
1618 782105 : basic_block bb;
1619 782105 : bool ret = false;
1620 :
1621 13303952 : FOR_EACH_BB_FN (bb, cfun)
1622 : {
1623 12521847 : gimple_stmt_iterator gsi;
1624 17076568 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1625 4554721 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), NULL, NULL, NULL,
1626 : scan_visit_addr);
1627 :
1628 120634969 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1629 : {
1630 95591275 : gimple *stmt = gsi_stmt (gsi);
1631 95591275 : tree t;
1632 95591275 : unsigned i;
1633 :
1634 95591275 : if (gimple_code (stmt) != GIMPLE_CALL)
1635 89697551 : walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1636 : scan_visit_addr);
1637 :
1638 95591275 : switch (gimple_code (stmt))
1639 : {
1640 774928 : case GIMPLE_RETURN:
1641 774928 : t = gimple_return_retval (as_a <greturn *> (stmt));
1642 774928 : if (t != NULL_TREE)
1643 458342 : ret |= build_access_from_expr (t, stmt, false);
1644 : break;
1645 :
1646 32887142 : case GIMPLE_ASSIGN:
1647 32887142 : ret |= build_accesses_from_assign (stmt);
1648 32887142 : break;
1649 :
1650 5893724 : case GIMPLE_CALL:
1651 5893724 : {
1652 5893724 : enum out_edge_check oe_check = SRA_OUTGOING_EDGES_UNCHECKED;
1653 5893724 : gcall *call = as_a <gcall *> (stmt);
1654 17610710 : for (i = 0; i < gimple_call_num_args (call); i++)
1655 : {
1656 11716986 : bool can_be_returned;
1657 11716986 : if (gimple_call_lhs (call))
1658 : {
1659 4707300 : int af = gimple_call_arg_flags (call, i);
1660 4707300 : can_be_returned = !(af & EAF_NOT_RETURNED_DIRECTLY);
1661 : }
1662 : else
1663 : can_be_returned = false;
1664 11716986 : ret |= build_access_from_call_arg (gimple_call_arg (call,
1665 : i),
1666 : stmt, can_be_returned,
1667 : &oe_check);
1668 : }
1669 5893724 : if (gimple_call_chain(stmt))
1670 40574 : ret |= build_access_from_call_arg (gimple_call_chain(call),
1671 : stmt, false, &oe_check);
1672 : }
1673 :
1674 5893724 : t = gimple_call_lhs (stmt);
1675 5893724 : if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
1676 : {
1677 : /* If the STMT is a call to DEFERRED_INIT, avoid setting
1678 : cannot_scalarize_away_bitmap. */
1679 2415389 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
1680 : {
1681 108361 : struct access *access
1682 108361 : = build_access_from_expr_1 (t, stmt, true);
1683 108361 : if (access)
1684 47209 : access->grp_assignment_write = 1;
1685 108361 : ret |= access != NULL;
1686 : }
1687 : else
1688 2307028 : ret |= build_access_from_expr (t, stmt, true);
1689 : }
1690 : break;
1691 :
1692 13348 : case GIMPLE_ASM:
1693 13348 : {
1694 13348 : gasm *asm_stmt = as_a <gasm *> (stmt);
1695 13348 : if (stmt_ends_bb_p (asm_stmt)
1696 13363 : && !single_succ_p (gimple_bb (asm_stmt)))
1697 : {
1698 32 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1699 : {
1700 17 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1701 17 : disqualify_base_of_expr (t, "OP of asm goto.");
1702 : }
1703 42 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1704 : {
1705 27 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1706 27 : disqualify_base_of_expr (t, "OP of asm goto.");
1707 : }
1708 : }
1709 : else
1710 : {
1711 25561 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1712 : {
1713 12228 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1714 12228 : ret |= build_access_from_expr (t, asm_stmt, false);
1715 : }
1716 24578 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1717 : {
1718 11245 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1719 11245 : ret |= build_access_from_expr (t, asm_stmt, true);
1720 : }
1721 : }
1722 : }
1723 : break;
1724 :
1725 : default:
1726 : break;
1727 : }
1728 : }
1729 : }
1730 :
1731 782105 : return ret;
1732 : }
1733 :
1734 : /* Helper of QSORT function. There are pointers to accesses in the array. An
1735 : access is considered smaller than another if it has smaller offset or if the
1736 : offsets are the same but is size is bigger. */
1737 :
1738 : static int
1739 128518256 : compare_access_positions (const void *a, const void *b)
1740 : {
1741 128518256 : const access_p *fp1 = (const access_p *) a;
1742 128518256 : const access_p *fp2 = (const access_p *) b;
1743 128518256 : const access_p f1 = *fp1;
1744 128518256 : const access_p f2 = *fp2;
1745 :
1746 128518256 : if (f1->offset != f2->offset)
1747 115823218 : return f1->offset < f2->offset ? -1 : 1;
1748 :
1749 49979470 : if (f1->size == f2->size)
1750 : {
1751 34418597 : if (f1->type == f2->type)
1752 : return 0;
1753 : /* Put any non-aggregate type before any aggregate type. */
1754 5625287 : else if (!is_gimple_reg_type (f1->type)
1755 5625287 : && is_gimple_reg_type (f2->type))
1756 : return 1;
1757 4311419 : else if (is_gimple_reg_type (f1->type)
1758 4311419 : && !is_gimple_reg_type (f2->type))
1759 : return -1;
1760 : /* Put any complex or vector type before any other scalar type. */
1761 2613651 : else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1762 2613651 : && TREE_CODE (f1->type) != VECTOR_TYPE
1763 2527960 : && (TREE_CODE (f2->type) == COMPLEX_TYPE
1764 2527960 : || VECTOR_TYPE_P (f2->type)))
1765 : return 1;
1766 2568353 : else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1767 : || VECTOR_TYPE_P (f1->type))
1768 85691 : && TREE_CODE (f2->type) != COMPLEX_TYPE
1769 83371 : && TREE_CODE (f2->type) != VECTOR_TYPE)
1770 : return -1;
1771 : /* Put any integral type before any non-integral type. When splicing, we
1772 : make sure that those with insufficient precision and occupying the
1773 : same space are not scalarized. */
1774 2503830 : else if (INTEGRAL_TYPE_P (f1->type)
1775 370141 : && !INTEGRAL_TYPE_P (f2->type))
1776 : return -1;
1777 2389968 : else if (!INTEGRAL_TYPE_P (f1->type)
1778 2133689 : && INTEGRAL_TYPE_P (f2->type))
1779 : return 1;
1780 : /* Put the integral type with the bigger precision first. */
1781 2278081 : else if (INTEGRAL_TYPE_P (f1->type)
1782 256279 : && INTEGRAL_TYPE_P (f2->type)
1783 2534360 : && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1784 32587 : return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1785 : /* Stabilize the sort. */
1786 2245494 : return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1787 : }
1788 :
1789 : /* We want the bigger accesses first, thus the opposite operator in the next
1790 : line: */
1791 15560873 : return f1->size > f2->size ? -1 : 1;
1792 : }
1793 :
1794 :
1795 : /* Append a name of the declaration to the name obstack. A helper function for
1796 : make_fancy_name. */
1797 :
1798 : static void
1799 2058090 : make_fancy_decl_name (tree decl)
1800 : {
1801 2058090 : char buffer[32];
1802 :
1803 2058090 : tree name = DECL_NAME (decl);
1804 2058090 : if (name)
1805 1994301 : obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1806 : IDENTIFIER_LENGTH (name));
1807 : else
1808 : {
1809 63789 : sprintf (buffer, "D%u", DECL_UID (decl));
1810 63789 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1811 : }
1812 2058090 : }
1813 :
1814 : /* Helper for make_fancy_name. */
1815 :
1816 : static void
1817 2334360 : make_fancy_name_1 (tree expr)
1818 : {
1819 2553328 : char buffer[32];
1820 2553328 : tree index;
1821 :
1822 2553328 : if (DECL_P (expr))
1823 : {
1824 1020874 : make_fancy_decl_name (expr);
1825 1020874 : return;
1826 : }
1827 :
1828 1532454 : switch (TREE_CODE (expr))
1829 : {
1830 1037216 : case COMPONENT_REF:
1831 1037216 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1832 1037216 : obstack_1grow (&name_obstack, '$');
1833 1037216 : make_fancy_decl_name (TREE_OPERAND (expr, 1));
1834 1037216 : break;
1835 :
1836 58813 : case ARRAY_REF:
1837 58813 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1838 58813 : obstack_1grow (&name_obstack, '$');
1839 : /* Arrays with only one element may not have a constant as their
1840 : index. */
1841 58813 : index = TREE_OPERAND (expr, 1);
1842 58813 : if (TREE_CODE (index) != INTEGER_CST)
1843 : break;
1844 58689 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1845 58689 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1846 58689 : break;
1847 :
1848 218968 : case BIT_FIELD_REF:
1849 218968 : case ADDR_EXPR:
1850 218968 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1851 218968 : break;
1852 :
1853 217231 : case MEM_REF:
1854 217231 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1855 217231 : if (!integer_zerop (TREE_OPERAND (expr, 1)))
1856 : {
1857 70889 : obstack_1grow (&name_obstack, '$');
1858 141778 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1859 70889 : TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1860 70889 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1861 : }
1862 : break;
1863 :
1864 0 : case REALPART_EXPR:
1865 0 : case IMAGPART_EXPR:
1866 0 : gcc_unreachable (); /* we treat these as scalars. */
1867 : break;
1868 : default:
1869 : break;
1870 : }
1871 : }
1872 :
1873 : /* Create a human readable name for replacement variable of ACCESS. */
1874 :
1875 : static char *
1876 1021100 : make_fancy_name (tree expr)
1877 : {
1878 1021100 : make_fancy_name_1 (expr);
1879 1021100 : obstack_1grow (&name_obstack, '\0');
1880 1021100 : return XOBFINISH (&name_obstack, char *);
1881 : }
1882 :
1883 : /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1884 : EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1885 : something for which get_addr_base_and_unit_offset returns NULL, gsi must
1886 : be non-NULL and is used to insert new statements either before or below
1887 : the current one as specified by INSERT_AFTER. This function is not capable
1888 : of handling bitfields. If FORCE_REF_ALL is true then the memory access
1889 : will use alias-set zero. */
1890 :
1891 : static tree
1892 2449349 : build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
1893 : bool reverse, tree exp_type, gimple_stmt_iterator *gsi,
1894 : bool insert_after, bool force_ref_all = false)
1895 : {
1896 2449349 : tree prev_base = base;
1897 2449349 : tree off;
1898 2449349 : tree mem_ref;
1899 2449349 : poly_int64 base_offset;
1900 2449349 : unsigned HOST_WIDE_INT misalign;
1901 2449349 : unsigned int align;
1902 :
1903 : /* Preserve address-space information. */
1904 2449349 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1905 2449349 : if (as != TYPE_ADDR_SPACE (exp_type))
1906 4 : exp_type = build_qualified_type (exp_type,
1907 2 : TYPE_QUALS (exp_type)
1908 2 : | ENCODE_QUAL_ADDR_SPACE (as));
1909 :
1910 2449349 : poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1911 2449349 : get_object_alignment_1 (base, &align, &misalign);
1912 2449349 : base = get_addr_base_and_unit_offset (base, &base_offset);
1913 :
1914 : /* get_addr_base_and_unit_offset returns NULL for references with a variable
1915 : offset such as array[var_index]. */
1916 2449349 : if (!base)
1917 : {
1918 34244 : gassign *stmt;
1919 34244 : tree tmp, addr;
1920 :
1921 34244 : gcc_checking_assert (gsi);
1922 34244 : tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1923 34244 : addr = build_fold_addr_expr (unshare_expr (prev_base));
1924 34244 : STRIP_USELESS_TYPE_CONVERSION (addr);
1925 34244 : stmt = gimple_build_assign (tmp, addr);
1926 34244 : gimple_set_location (stmt, loc);
1927 34244 : if (insert_after)
1928 9468 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1929 : else
1930 24776 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1931 :
1932 34244 : off = build_int_cst (force_ref_all ? ptr_type_node
1933 34244 : : reference_alias_ptr_type (prev_base), byte_offset);
1934 34244 : base = tmp;
1935 : }
1936 2415105 : else if (TREE_CODE (base) == MEM_REF)
1937 : {
1938 408626 : off = build_int_cst (force_ref_all ? ptr_type_node
1939 204313 : : TREE_TYPE (TREE_OPERAND (base, 1)),
1940 : base_offset + byte_offset);
1941 204313 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1942 204313 : base = unshare_expr (TREE_OPERAND (base, 0));
1943 : }
1944 : else
1945 : {
1946 4081501 : off = build_int_cst (force_ref_all ? ptr_type_node
1947 1870709 : : reference_alias_ptr_type (prev_base),
1948 : base_offset + byte_offset);
1949 2210792 : base = build_fold_addr_expr (unshare_expr (base));
1950 : }
1951 :
1952 2449349 : unsigned int align_bound = known_alignment (misalign + offset);
1953 2449349 : if (align_bound != 0)
1954 1616506 : align = MIN (align, align_bound);
1955 2449349 : if (align != TYPE_ALIGN (exp_type))
1956 493037 : exp_type = build_aligned_type (exp_type, align);
1957 :
1958 2449349 : mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1959 2449349 : REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1960 2449349 : if (TREE_THIS_VOLATILE (prev_base))
1961 6 : TREE_THIS_VOLATILE (mem_ref) = 1;
1962 2449349 : if (TREE_SIDE_EFFECTS (prev_base))
1963 126 : TREE_SIDE_EFFECTS (mem_ref) = 1;
1964 2449349 : return mem_ref;
1965 : }
1966 :
1967 : /* Construct and return a memory reference that is equal to a portion of
1968 : MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1969 :
1970 : static tree
1971 1635580 : build_reconstructed_reference (location_t, tree base, struct access *model)
1972 : {
1973 1635580 : tree expr = model->expr;
1974 : /* We have to make sure to start just below the outermost union. */
1975 1635580 : tree start_expr = expr;
1976 3372400 : while (handled_component_p (expr))
1977 : {
1978 1736820 : if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == UNION_TYPE)
1979 7071 : start_expr = expr;
1980 1736820 : expr = TREE_OPERAND (expr, 0);
1981 : }
1982 :
1983 : expr = start_expr;
1984 : tree prev_expr = NULL_TREE;
1985 3349266 : while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
1986 : {
1987 1781787 : if (!handled_component_p (expr))
1988 : return NULL_TREE;
1989 1713686 : prev_expr = expr;
1990 1713686 : expr = TREE_OPERAND (expr, 0);
1991 : }
1992 :
1993 : /* Guard against broken VIEW_CONVERT_EXPRs... */
1994 1567479 : if (!prev_expr)
1995 : return NULL_TREE;
1996 :
1997 1566503 : TREE_OPERAND (prev_expr, 0) = base;
1998 1566503 : tree ref = unshare_expr (model->expr);
1999 1566503 : TREE_OPERAND (prev_expr, 0) = expr;
2000 1566503 : return ref;
2001 : }
2002 :
2003 : /* Construct a memory reference to a part of an aggregate BASE at the given
2004 : OFFSET and of the same type as MODEL. In case this is a reference to a
2005 : bit-field, the function will replicate the last component_ref of model's
2006 : expr to access it. INSERT_AFTER and GSI have the same meaning as in
2007 : build_ref_for_offset, furthermore, when GSI is NULL, the function expects
2008 : that it re-builds the entire reference from a DECL to the final access and
2009 : so will create a MEM_REF when OFFSET does not exactly match offset of
2010 : MODEL. If FORCE_REF_ALL is true then the memory access will use
2011 : alias-set zero. */
2012 :
2013 : static tree
2014 3957417 : build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2015 : struct access *model, gimple_stmt_iterator *gsi,
2016 : bool insert_after, bool force_ref_all = false)
2017 : {
2018 3957417 : gcc_assert (offset >= 0);
2019 3957417 : if (TREE_CODE (model->expr) == COMPONENT_REF
2020 3957417 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2021 : {
2022 : /* This access represents a bit-field. */
2023 29044 : tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
2024 :
2025 29044 : offset -= int_bit_position (fld);
2026 29044 : exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
2027 29044 : t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type,
2028 : gsi, insert_after, force_ref_all);
2029 : /* The flag will be set on the record type. */
2030 29044 : REF_REVERSE_STORAGE_ORDER (t) = 0;
2031 29044 : return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
2032 29044 : NULL_TREE);
2033 : }
2034 : else
2035 : {
2036 3928373 : tree res;
2037 3928373 : if (model->grp_same_access_path
2038 1721850 : && !force_ref_all
2039 1635605 : && !TREE_THIS_VOLATILE (base)
2040 1635599 : && (TYPE_ADDR_SPACE (TREE_TYPE (base))
2041 1635599 : == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
2042 1635598 : && (offset == model->offset
2043 10342 : || (gsi && offset <= model->offset))
2044 : /* build_reconstructed_reference can still fail if we have already
2045 : massaged BASE because of another type incompatibility. */
2046 5563953 : && (res = build_reconstructed_reference (loc, base, model)))
2047 : return res;
2048 : else
2049 2361870 : return build_ref_for_offset (loc, base, offset, model->reverse,
2050 : model->type, gsi, insert_after,
2051 : force_ref_all);
2052 : }
2053 : }
2054 :
2055 : /* Attempt to build a memory reference that we could but into a gimple
2056 : debug_bind statement. Similar to build_ref_for_model but punts if it has to
2057 : create statements and return s NULL instead. This function also ignores
2058 : alignment issues and so its results should never end up in non-debug
2059 : statements. */
2060 :
2061 : static tree
2062 5928 : build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2063 : struct access *model)
2064 : {
2065 5928 : poly_int64 base_offset;
2066 5928 : tree off;
2067 :
2068 5928 : if (TREE_CODE (model->expr) == COMPONENT_REF
2069 5928 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2070 : return NULL_TREE;
2071 :
2072 5928 : base = get_addr_base_and_unit_offset (base, &base_offset);
2073 5928 : if (!base)
2074 : return NULL_TREE;
2075 5928 : if (TREE_CODE (base) == MEM_REF)
2076 : {
2077 196 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
2078 196 : base_offset + offset / BITS_PER_UNIT);
2079 196 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
2080 196 : base = unshare_expr (TREE_OPERAND (base, 0));
2081 : }
2082 : else
2083 : {
2084 5732 : off = build_int_cst (reference_alias_ptr_type (base),
2085 5732 : base_offset + offset / BITS_PER_UNIT);
2086 5732 : base = build_fold_addr_expr (unshare_expr (base));
2087 : }
2088 :
2089 5928 : return fold_build2_loc (loc, MEM_REF, model->type, base, off);
2090 : }
2091 :
2092 : /* Construct a memory reference consisting of component_refs and array_refs to
2093 : a part of an aggregate *RES which is of type TYPE. The requested part
2094 : should have type EXP_TYPE at the given OFFSET. CUR_SIZE must be the size of
2095 : *RES unless it is known that *RES alone cannot be the result. This function
2096 : might not succeed, it returns true when it does and only then *RES points to
2097 : something meaningful.
2098 :
2099 : This function should be used only to build expressions that we might need to
2100 : present to user (e.g. in warnings). In all other situations,
2101 : build_ref_for_model or build_ref_for_offset should be used instead. */
2102 :
2103 : static bool
2104 3878658 : build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
2105 : HOST_WIDE_INT cur_size, tree exp_type,
2106 : HOST_WIDE_INT exp_size)
2107 : {
2108 3934470 : while (1)
2109 : {
2110 3906564 : tree fld;
2111 3906564 : tree tr_size, index, minidx;
2112 3906564 : HOST_WIDE_INT el_size;
2113 :
2114 3906564 : if (offset == 0
2115 3906564 : && cur_size == exp_size
2116 3906564 : && types_compatible_p (exp_type, type))
2117 : return true;
2118 :
2119 2364211 : switch (TREE_CODE (type))
2120 : {
2121 2308301 : case UNION_TYPE:
2122 2308301 : case QUAL_UNION_TYPE:
2123 2308301 : case RECORD_TYPE:
2124 12466004 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
2125 : {
2126 12396958 : HOST_WIDE_INT pos, size;
2127 12396958 : tree tr_pos, expr, *expr_ptr;
2128 :
2129 12396958 : if (TREE_CODE (fld) != FIELD_DECL)
2130 10088596 : continue;
2131 :
2132 3830421 : tr_pos = bit_position (fld);
2133 3830421 : if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
2134 0 : continue;
2135 3830421 : pos = tree_to_uhwi (tr_pos);
2136 3830421 : gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
2137 3830421 : tr_size = DECL_SIZE (fld);
2138 3830421 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2139 0 : continue;
2140 3830421 : size = tree_to_uhwi (tr_size);
2141 3830421 : if (size == 0)
2142 : {
2143 56271 : if (pos != offset)
2144 23355 : continue;
2145 : }
2146 3774150 : else if (pos > offset || (pos + size) <= offset)
2147 1498704 : continue;
2148 :
2149 2308362 : expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
2150 : NULL_TREE);
2151 2308362 : expr_ptr = &expr;
2152 2308362 : if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
2153 : offset - pos, size,
2154 : exp_type, exp_size))
2155 : {
2156 2239255 : *res = expr;
2157 2239255 : return true;
2158 : }
2159 : }
2160 : return false;
2161 :
2162 27906 : case ARRAY_TYPE:
2163 27906 : tr_size = TYPE_SIZE (TREE_TYPE (type));
2164 27906 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2165 : return false;
2166 27906 : el_size = tree_to_uhwi (tr_size);
2167 :
2168 27906 : minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
2169 27906 : if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
2170 : return false;
2171 27906 : index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
2172 27906 : if (!integer_zerop (minidx))
2173 563 : index = int_const_binop (PLUS_EXPR, index, minidx);
2174 27906 : *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
2175 : NULL_TREE, NULL_TREE);
2176 27906 : offset = offset % el_size;
2177 27906 : cur_size = el_size;
2178 27906 : type = TREE_TYPE (type);
2179 27906 : break;
2180 :
2181 : default:
2182 : return false;
2183 : }
2184 27906 : }
2185 : }
2186 :
2187 : /* Print message to dump file why a variable was rejected. */
2188 :
2189 : static void
2190 14809865 : reject (tree var, const char *msg)
2191 : {
2192 14809865 : if (dump_file && (dump_flags & TDF_DETAILS))
2193 : {
2194 28 : fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
2195 28 : print_generic_expr (dump_file, var);
2196 28 : fprintf (dump_file, "\n");
2197 : }
2198 14809865 : }
2199 :
2200 : /* Return true if VAR is a candidate for SRA. */
2201 :
2202 : static bool
2203 18973767 : maybe_add_sra_candidate (tree var)
2204 : {
2205 18973767 : tree type = TREE_TYPE (var);
2206 18973767 : const char *msg;
2207 18973767 : tree_node **slot;
2208 :
2209 18973767 : if (!AGGREGATE_TYPE_P (type))
2210 : {
2211 13270474 : reject (var, "not aggregate");
2212 13270474 : return false;
2213 : }
2214 :
2215 5703293 : if ((is_global_var (var)
2216 : /* There are cases where non-addressable variables fail the
2217 : pt_solutions_check test, e.g in gcc.dg/uninit-40.c. */
2218 5477244 : || (TREE_ADDRESSABLE (var)
2219 1516726 : && pt_solution_includes (&cfun->gimple_df->escaped_return, var))
2220 4167949 : || (TREE_CODE (var) == RESULT_DECL
2221 0 : && !DECL_BY_REFERENCE (var)
2222 0 : && aggregate_value_p (var, current_function_decl)))
2223 : /* Allow constant-pool entries that "need to live in memory". */
2224 7012588 : && !constant_decl_p (var))
2225 : {
2226 1532724 : reject (var, "needs to live in memory and escapes or global");
2227 1532724 : return false;
2228 : }
2229 4170569 : if (TREE_THIS_VOLATILE (var))
2230 : {
2231 539 : reject (var, "is volatile");
2232 539 : return false;
2233 : }
2234 4170030 : if (!COMPLETE_TYPE_P (type))
2235 : {
2236 0 : reject (var, "has incomplete type");
2237 0 : return false;
2238 : }
2239 4170030 : if (!tree_fits_shwi_p (TYPE_SIZE (type)))
2240 : {
2241 43 : reject (var, "type size not fixed");
2242 43 : return false;
2243 : }
2244 4169987 : if (tree_to_shwi (TYPE_SIZE (type)) == 0)
2245 : {
2246 5829 : reject (var, "type size is zero");
2247 5829 : return false;
2248 : }
2249 4164158 : if (type_internals_preclude_sra_p (type, &msg))
2250 : {
2251 256 : reject (var, msg);
2252 256 : return false;
2253 : }
2254 4163902 : if (/* Fix for PR 41089. tree-stdarg.cc needs to have va_lists intact but
2255 : we also want to schedule it rather late. Thus we ignore it in
2256 : the early pass. */
2257 4163902 : (sra_mode == SRA_MODE_EARLY_INTRA
2258 4163902 : && is_va_list_type (type)))
2259 : {
2260 0 : reject (var, "is va_list");
2261 0 : return false;
2262 : }
2263 :
2264 4163902 : bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2265 4163902 : slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2266 4163902 : *slot = var;
2267 :
2268 4163902 : if (dump_file && (dump_flags & TDF_DETAILS))
2269 : {
2270 29 : fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
2271 29 : print_generic_expr (dump_file, var);
2272 29 : fprintf (dump_file, "\n");
2273 : }
2274 :
2275 : return true;
2276 : }
2277 :
2278 : /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
2279 : those with type which is suitable for scalarization. */
2280 :
2281 : static bool
2282 3475668 : find_var_candidates (void)
2283 : {
2284 3475668 : tree var, parm;
2285 3475668 : unsigned int i;
2286 3475668 : bool ret = false;
2287 :
2288 3475668 : for (parm = DECL_ARGUMENTS (current_function_decl);
2289 10759829 : parm;
2290 7284161 : parm = DECL_CHAIN (parm))
2291 7284161 : ret |= maybe_add_sra_candidate (parm);
2292 :
2293 18156288 : FOR_EACH_LOCAL_DECL (cfun, i, var)
2294 : {
2295 11685818 : if (!VAR_P (var))
2296 0 : continue;
2297 :
2298 11685818 : ret |= maybe_add_sra_candidate (var);
2299 : }
2300 :
2301 3475668 : return ret;
2302 : }
2303 :
2304 : /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
2305 : ending either with a DECL or a MEM_REF with zero offset. */
2306 :
2307 : static bool
2308 8467485 : path_comparable_for_same_access (tree expr)
2309 : {
2310 14580134 : while (handled_component_p (expr))
2311 : {
2312 6234320 : if (TREE_CODE (expr) == ARRAY_REF)
2313 : {
2314 : /* SSA name indices can occur here too when the array is of sie one.
2315 : But we cannot just re-use array_refs with SSA names elsewhere in
2316 : the function, so disallow non-constant indices. TODO: Remove this
2317 : limitation after teaching build_reconstructed_reference to replace
2318 : the index with the index type lower bound. */
2319 646544 : if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
2320 : return false;
2321 : }
2322 6112649 : expr = TREE_OPERAND (expr, 0);
2323 : }
2324 :
2325 8345814 : if (TREE_CODE (expr) == MEM_REF)
2326 : {
2327 1017131 : if (!zerop (TREE_OPERAND (expr, 1)))
2328 : return false;
2329 577981 : gcc_assert (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
2330 : && DECL_P (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)));
2331 577981 : if (TYPE_MAIN_VARIANT (TREE_TYPE (expr))
2332 577981 : != TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))))
2333 : return false;
2334 : }
2335 : else
2336 7328683 : gcc_assert (DECL_P (expr));
2337 :
2338 : return true;
2339 : }
2340 :
2341 : /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
2342 : true if the chain of these handled components are exactly the same as EXP2
2343 : and the expression under them is the same DECL or an equivalent MEM_REF.
2344 : The reference picked by compare_access_positions must go to EXP1. */
2345 :
2346 : static bool
2347 4246722 : same_access_path_p (tree exp1, tree exp2)
2348 : {
2349 4246722 : if (TREE_CODE (exp1) != TREE_CODE (exp2))
2350 : {
2351 : /* Special case single-field structures loaded sometimes as the field
2352 : and sometimes as the structure. If the field is of a scalar type,
2353 : compare_access_positions will put it into exp1.
2354 :
2355 : TODO: The gimple register type condition can be removed if teach
2356 : compare_access_positions to put inner types first. */
2357 575661 : if (is_gimple_reg_type (TREE_TYPE (exp1))
2358 355384 : && TREE_CODE (exp1) == COMPONENT_REF
2359 926251 : && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
2360 350590 : == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
2361 324927 : exp1 = TREE_OPERAND (exp1, 0);
2362 : else
2363 : return false;
2364 : }
2365 :
2366 3995988 : if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF))
2367 : return false;
2368 :
2369 : return true;
2370 : }
2371 :
2372 : /* Return true when either T1 is a type that, when loaded into a register and
2373 : stored back to memory will yield the same bits or when both T1 and T2 are
2374 : compatible. */
2375 :
2376 : static bool
2377 5359540 : types_risk_mangled_binary_repr_p (tree t1, tree t2)
2378 : {
2379 5359540 : if (mode_can_transfer_bits (TYPE_MODE (t1)))
2380 : return false;
2381 :
2382 2758 : return !types_compatible_p (t1, t2);
2383 : }
2384 :
2385 : /* Sort all accesses for the given variable, check for partial overlaps and
2386 : return NULL if there are any. If there are none, pick a representative for
2387 : each combination of offset and size and create a linked list out of them.
2388 : Return the pointer to the first representative and make sure it is the first
2389 : one in the vector of accesses. */
2390 :
2391 : static struct access *
2392 4046647 : sort_and_splice_var_accesses (tree var)
2393 : {
2394 4046647 : int i, j, access_count;
2395 4046647 : struct access *res, **prev_acc_ptr = &res;
2396 4046647 : vec<access_p> *access_vec;
2397 4046647 : bool first = true;
2398 4046647 : HOST_WIDE_INT low = -1, high = 0;
2399 :
2400 4046647 : access_vec = get_base_access_vector (var);
2401 4046647 : if (!access_vec)
2402 : return NULL;
2403 3890834 : access_count = access_vec->length ();
2404 :
2405 : /* Sort by <OFFSET, SIZE>. */
2406 3890834 : access_vec->qsort (compare_access_positions);
2407 :
2408 : i = 0;
2409 13136069 : while (i < access_count)
2410 : {
2411 9250150 : struct access *access = (*access_vec)[i];
2412 9250150 : bool grp_write = access->write;
2413 9250150 : bool grp_read = !access->write;
2414 9250150 : bool grp_scalar_write = access->write
2415 9250150 : && is_gimple_reg_type (access->type);
2416 9250150 : bool grp_scalar_read = !access->write
2417 9250150 : && is_gimple_reg_type (access->type);
2418 9250150 : bool grp_assignment_read = access->grp_assignment_read;
2419 9250150 : bool grp_assignment_write = access->grp_assignment_write;
2420 9250150 : bool multiple_scalar_reads = false;
2421 9250150 : bool grp_partial_lhs = access->grp_partial_lhs;
2422 9250150 : bool first_scalar = is_gimple_reg_type (access->type);
2423 9250150 : bool unscalarizable_region = access->grp_unscalarizable_region;
2424 9250150 : bool grp_same_access_path = access->grp_same_access_path;
2425 9250150 : bool bf_non_full_precision
2426 9250150 : = (INTEGRAL_TYPE_P (access->type)
2427 3100936 : && TYPE_PRECISION (access->type) != access->size
2428 155663 : && TREE_CODE (access->expr) == COMPONENT_REF
2429 9316677 : && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2430 :
2431 9250150 : if (first || access->offset >= high)
2432 : {
2433 4312955 : first = false;
2434 4312955 : low = access->offset;
2435 4312955 : high = access->offset + access->size;
2436 : }
2437 4937195 : else if (access->offset > low && access->offset + access->size > high)
2438 : return NULL;
2439 : else
2440 4936561 : gcc_assert (access->offset >= low
2441 : && access->offset + access->size <= high);
2442 :
2443 9249516 : if (INTEGRAL_TYPE_P (access->type)
2444 3100473 : && TYPE_PRECISION (access->type) != access->size
2445 9404754 : && bitmap_bit_p (passed_by_ref_in_call, DECL_UID (access->base)))
2446 : {
2447 : /* This can lead to performance regressions because we can generate
2448 : excessive zero extensions. */
2449 4281 : if (dump_file && (dump_flags & TDF_DETAILS))
2450 : {
2451 0 : fprintf (dump_file, "Won't scalarize ");
2452 0 : print_generic_expr (dump_file, access->base);
2453 0 : fprintf (dump_file, "(%d), it is passed by reference to a call "
2454 : "and there are accesses with precision not covering "
2455 0 : "their type size.", DECL_UID (access->base));
2456 : }
2457 4281 : return NULL;
2458 : }
2459 :
2460 9245235 : if (grp_same_access_path)
2461 8467485 : grp_same_access_path = path_comparable_for_same_access (access->expr);
2462 :
2463 9245235 : j = i + 1;
2464 14467998 : while (j < access_count)
2465 : {
2466 10582079 : struct access *ac2 = (*access_vec)[j];
2467 10582079 : if (ac2->offset != access->offset || ac2->size != access->size)
2468 : break;
2469 5222763 : if (ac2->write)
2470 : {
2471 1262445 : grp_write = true;
2472 1262445 : grp_scalar_write = (grp_scalar_write
2473 1262445 : || is_gimple_reg_type (ac2->type));
2474 : }
2475 : else
2476 : {
2477 3960318 : grp_read = true;
2478 3960318 : if (is_gimple_reg_type (ac2->type))
2479 : {
2480 1734724 : if (grp_scalar_read)
2481 : multiple_scalar_reads = true;
2482 : else
2483 367480 : grp_scalar_read = true;
2484 : }
2485 : }
2486 5222763 : grp_assignment_read |= ac2->grp_assignment_read;
2487 5222763 : grp_assignment_write |= ac2->grp_assignment_write;
2488 5222763 : grp_partial_lhs |= ac2->grp_partial_lhs;
2489 5222763 : unscalarizable_region |= ac2->grp_unscalarizable_region;
2490 5222763 : relink_to_new_repr (access, ac2);
2491 :
2492 : /* If there are both aggregate-type and scalar-type accesses with
2493 : this combination of size and offset, the comparison function
2494 : should have put the scalars first. */
2495 5222763 : gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
2496 : /* It also prefers integral types to non-integral. However, when the
2497 : precision of the selected type does not span the entire area and
2498 : should also be used for a non-integer (i.e. float), we must not
2499 : let that happen. Normally analyze_access_subtree expands the type
2500 : to cover the entire area but for bit-fields it doesn't. */
2501 5222763 : if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
2502 : {
2503 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2504 : {
2505 0 : fprintf (dump_file, "Cannot scalarize the following access "
2506 : "because insufficient precision integer type was "
2507 : "selected.\n ");
2508 0 : dump_access (dump_file, access, false);
2509 : }
2510 : unscalarizable_region = true;
2511 : }
2512 5222763 : else if (types_risk_mangled_binary_repr_p (access->type, ac2->type))
2513 : {
2514 818 : if (dump_file && (dump_flags & TDF_DETAILS))
2515 : {
2516 0 : fprintf (dump_file, "Cannot scalarize the following access "
2517 : "because data would be held in a mode which is not "
2518 : "guaranteed to preserve all bits.\n ");
2519 0 : dump_access (dump_file, access, false);
2520 : }
2521 : unscalarizable_region = true;
2522 : }
2523 : /* If there the same place is accessed with two incompatible
2524 : aggregate types, trying to base total scalarization on either of
2525 : them can be wrong. */
2526 5222763 : if (!first_scalar && !types_compatible_p (access->type, ac2->type))
2527 448744 : bitmap_set_bit (cannot_scalarize_away_bitmap,
2528 224372 : DECL_UID (access->base));
2529 :
2530 5222763 : if (grp_same_access_path
2531 5222763 : && (!ac2->grp_same_access_path
2532 4246722 : || !same_access_path_p (access->expr, ac2->expr)))
2533 : grp_same_access_path = false;
2534 :
2535 5222763 : ac2->group_representative = access;
2536 5222763 : j++;
2537 : }
2538 :
2539 9245235 : i = j;
2540 :
2541 9245235 : access->group_representative = access;
2542 9245235 : access->grp_write = grp_write;
2543 9245235 : access->grp_read = grp_read;
2544 9245235 : access->grp_scalar_read = grp_scalar_read;
2545 9245235 : access->grp_scalar_write = grp_scalar_write;
2546 9245235 : access->grp_assignment_read = grp_assignment_read;
2547 9245235 : access->grp_assignment_write = grp_assignment_write;
2548 9245235 : access->grp_hint = multiple_scalar_reads && !constant_decl_p (var);
2549 9245235 : access->grp_partial_lhs = grp_partial_lhs;
2550 9245235 : access->grp_unscalarizable_region = unscalarizable_region;
2551 9245235 : access->grp_same_access_path = grp_same_access_path;
2552 :
2553 9245235 : *prev_acc_ptr = access;
2554 9245235 : prev_acc_ptr = &access->next_grp;
2555 : }
2556 :
2557 3885919 : gcc_assert (res == (*access_vec)[0]);
2558 : return res;
2559 : }
2560 :
2561 : /* Create a variable for the given ACCESS which determines the type, name and a
2562 : few other properties. Return the variable declaration and store it also to
2563 : ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2564 : default-definition SSA name on in order to facilitate an uninitialized
2565 : warning. It is used instead of the actual ACCESS type if that is not of a
2566 : gimple register type. */
2567 :
2568 : static tree
2569 3843804 : create_access_replacement (struct access *access, tree reg_type = NULL_TREE)
2570 : {
2571 3843804 : tree repl;
2572 :
2573 3843804 : tree type = access->type;
2574 3843804 : if (reg_type && !is_gimple_reg_type (type))
2575 : type = reg_type;
2576 :
2577 3843804 : if (access->grp_to_be_debug_replaced)
2578 : {
2579 237883 : repl = create_tmp_var_raw (access->type);
2580 237883 : DECL_CONTEXT (repl) = current_function_decl;
2581 : }
2582 : else
2583 : /* Drop any special alignment on the type if it's not on the main
2584 : variant. This avoids issues with weirdo ABIs like AAPCS. */
2585 3605921 : repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type),
2586 3605921 : TYPE_QUALS (type)), "SR");
2587 3843804 : if (access->grp_partial_lhs
2588 3843804 : && is_gimple_reg_type (type))
2589 664 : DECL_NOT_GIMPLE_REG_P (repl) = 1;
2590 :
2591 3843804 : DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2592 3843804 : DECL_ARTIFICIAL (repl) = 1;
2593 3843804 : DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2594 :
2595 3843804 : if (DECL_NAME (access->base)
2596 3843804 : && ((!DECL_IGNORED_P (access->base) && !DECL_ARTIFICIAL (access->base))
2597 1871786 : || (VAR_P (access->base) && DECL_NONLOCAL_FRAME (access->base))))
2598 : {
2599 1021100 : char *pretty_name = make_fancy_name (access->expr);
2600 1021100 : tree debug_expr = unshare_expr_without_location (access->expr), d;
2601 1021100 : bool fail = false;
2602 :
2603 1021100 : DECL_NAME (repl) = get_identifier (pretty_name);
2604 1021100 : DECL_NAMELESS (repl) = 1;
2605 1021100 : obstack_free (&name_obstack, pretty_name);
2606 :
2607 : /* Get rid of any SSA_NAMEs embedded in debug_expr,
2608 : as DECL_DEBUG_EXPR isn't considered when looking for still
2609 : used SSA_NAMEs and thus they could be freed. All debug info
2610 : generation cares is whether something is constant or variable
2611 : and that get_ref_base_and_extent works properly on the
2612 : expression. It cannot handle accesses at a non-constant offset
2613 : though, so just give up in those cases. */
2614 1315380 : for (d = debug_expr;
2615 3574688 : !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2616 1315380 : d = TREE_OPERAND (d, 0))
2617 1315380 : switch (TREE_CODE (d))
2618 : {
2619 58889 : case ARRAY_REF:
2620 58889 : case ARRAY_RANGE_REF:
2621 58889 : if (TREE_OPERAND (d, 1)
2622 58889 : && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2623 : fail = true;
2624 58889 : if (TREE_OPERAND (d, 3)
2625 58889 : && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2626 : fail = true;
2627 : /* FALLTHRU */
2628 1096263 : case COMPONENT_REF:
2629 1096263 : if (TREE_OPERAND (d, 2)
2630 1096263 : && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2631 : fail = true;
2632 : break;
2633 217231 : case MEM_REF:
2634 217231 : if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2635 : fail = true;
2636 : else
2637 217231 : d = TREE_OPERAND (d, 0);
2638 : break;
2639 : default:
2640 : break;
2641 : }
2642 1021100 : if (!fail)
2643 : {
2644 1020977 : SET_DECL_DEBUG_EXPR (repl, debug_expr);
2645 1020977 : DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2646 : }
2647 1021100 : if (access->grp_no_warning)
2648 385 : suppress_warning (repl /* Be more selective! */);
2649 : else
2650 1020715 : copy_warning (repl, access->base);
2651 : }
2652 : else
2653 2822704 : suppress_warning (repl /* Be more selective! */);
2654 :
2655 3843804 : if (dump_file)
2656 : {
2657 145 : if (access->grp_to_be_debug_replaced)
2658 : {
2659 4 : fprintf (dump_file, "Created a debug-only replacement for ");
2660 4 : print_generic_expr (dump_file, access->base);
2661 4 : fprintf (dump_file, " offset: %u, size: %u\n",
2662 4 : (unsigned) access->offset, (unsigned) access->size);
2663 : }
2664 : else
2665 : {
2666 141 : fprintf (dump_file, "Created a replacement for ");
2667 141 : print_generic_expr (dump_file, access->base);
2668 141 : fprintf (dump_file, " offset: %u, size: %u: ",
2669 141 : (unsigned) access->offset, (unsigned) access->size);
2670 141 : print_generic_expr (dump_file, repl, TDF_UID);
2671 141 : fprintf (dump_file, "\n");
2672 : }
2673 : }
2674 3843804 : sra_stats.replacements++;
2675 :
2676 3843804 : return repl;
2677 : }
2678 :
2679 : /* Return ACCESS scalar replacement, which must exist. */
2680 :
2681 : static inline tree
2682 13169301 : get_access_replacement (struct access *access)
2683 : {
2684 13169301 : gcc_checking_assert (access->replacement_decl);
2685 13169301 : return access->replacement_decl;
2686 : }
2687 :
2688 :
2689 : /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2690 : linked list along the way. Stop when *ACCESS is NULL or the access pointed
2691 : to it is not "within" the root. Return false iff some accesses partially
2692 : overlap. */
2693 :
2694 : static bool
2695 9222311 : build_access_subtree (struct access **access)
2696 : {
2697 9222311 : struct access *root = *access, *last_child = NULL;
2698 9222311 : HOST_WIDE_INT limit = root->offset + root->size;
2699 :
2700 9222311 : *access = (*access)->next_grp;
2701 14134092 : while (*access && (*access)->offset + (*access)->size <= limit)
2702 : {
2703 4914288 : if (!last_child)
2704 1968028 : root->first_child = *access;
2705 : else
2706 2946260 : last_child->next_sibling = *access;
2707 4914288 : last_child = *access;
2708 4914288 : (*access)->parent = root;
2709 4914288 : (*access)->grp_write |= root->grp_write;
2710 :
2711 4914288 : if (!build_access_subtree (access))
2712 : return false;
2713 : }
2714 :
2715 9219804 : if (*access && (*access)->offset < limit)
2716 : return false;
2717 :
2718 : return true;
2719 : }
2720 :
2721 : /* Build a tree of access representatives, ACCESS is the pointer to the first
2722 : one, others are linked in a list by the next_grp field. Return false iff
2723 : some accesses partially overlap. */
2724 :
2725 : static bool
2726 3885919 : build_access_trees (struct access *access)
2727 : {
2728 8191616 : while (access)
2729 : {
2730 4308023 : struct access *root = access;
2731 :
2732 4308023 : if (!build_access_subtree (&access))
2733 : return false;
2734 4305697 : root->next_grp = access;
2735 : }
2736 : return true;
2737 : }
2738 :
2739 : /* Traverse the access forest where ROOT is the first root and verify that
2740 : various important invariants hold true. */
2741 :
2742 : DEBUG_FUNCTION void
2743 3883593 : verify_sra_access_forest (struct access *root)
2744 : {
2745 3883593 : struct access *access = root;
2746 3883593 : tree first_base = root->base;
2747 3883593 : gcc_assert (DECL_P (first_base));
2748 11140338 : do
2749 : {
2750 11140338 : gcc_assert (access->base == first_base);
2751 11140338 : if (access->parent)
2752 6834656 : gcc_assert (access->offset >= access->parent->offset
2753 : && access->size <= access->parent->size);
2754 11140338 : if (access->next_sibling)
2755 4031328 : gcc_assert (access->next_sibling->offset
2756 : >= access->offset + access->size);
2757 :
2758 11140338 : poly_int64 poffset, psize, pmax_size;
2759 11140338 : bool reverse;
2760 11140338 : tree base = get_ref_base_and_extent (access->expr, &poffset, &psize,
2761 : &pmax_size, &reverse);
2762 11140338 : HOST_WIDE_INT offset, size, max_size;
2763 11140338 : if (!poffset.is_constant (&offset)
2764 11140338 : || !psize.is_constant (&size)
2765 11140338 : || !pmax_size.is_constant (&max_size))
2766 : gcc_unreachable ();
2767 11140338 : gcc_assert (base == first_base);
2768 11140338 : gcc_assert (offset == access->offset);
2769 11140338 : gcc_assert (access->grp_unscalarizable_region
2770 : || access->grp_total_scalarization
2771 : || size == max_size);
2772 11140338 : gcc_assert (access->grp_unscalarizable_region
2773 : || !is_gimple_reg_type (access->type)
2774 : || size == access->size);
2775 11140338 : gcc_assert (reverse == access->reverse);
2776 :
2777 11140338 : if (access->first_child)
2778 : {
2779 2803328 : gcc_assert (access->first_child->parent == access);
2780 : access = access->first_child;
2781 : }
2782 8337010 : else if (access->next_sibling)
2783 : {
2784 3850048 : gcc_assert (access->next_sibling->parent == access->parent);
2785 : access = access->next_sibling;
2786 : }
2787 : else
2788 : {
2789 7290290 : while (access->parent && !access->next_sibling)
2790 : access = access->parent;
2791 4486962 : if (access->next_sibling)
2792 : access = access->next_sibling;
2793 : else
2794 : {
2795 4305682 : gcc_assert (access == root);
2796 4305682 : root = root->next_grp;
2797 4305682 : access = root;
2798 : }
2799 : }
2800 : }
2801 11140338 : while (access);
2802 3883593 : }
2803 :
2804 : /* Verify access forests of all candidates with accesses by calling
2805 : verify_access_forest on each on them. */
2806 :
2807 : DEBUG_FUNCTION void
2808 730214 : verify_all_sra_access_forests (void)
2809 : {
2810 730214 : bitmap_iterator bi;
2811 730214 : unsigned i;
2812 4613807 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2813 : {
2814 3883593 : tree var = candidate (i);
2815 3883593 : struct access *access = get_first_repr_for_decl (var);
2816 3883593 : if (access)
2817 : {
2818 3883593 : gcc_assert (access->base == var);
2819 3883593 : verify_sra_access_forest (access);
2820 : }
2821 : }
2822 730214 : }
2823 :
2824 : /* Return true if expr contains some ARRAY_REFs into a variable bounded
2825 : array. */
2826 :
2827 : static bool
2828 10757742 : expr_with_var_bounded_array_refs_p (tree expr)
2829 : {
2830 20287808 : while (handled_component_p (expr))
2831 : {
2832 9530066 : if (TREE_CODE (expr) == ARRAY_REF
2833 9530066 : && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2834 : return true;
2835 9530066 : expr = TREE_OPERAND (expr, 0);
2836 : }
2837 : return false;
2838 : }
2839 :
2840 : /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2841 : both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2842 : is set, we are totally scalarizing the aggregate. Also set all sorts of
2843 : access flags appropriately along the way, notably always set grp_read and
2844 : grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2845 : true.
2846 :
2847 : Creating a replacement for a scalar access is considered beneficial if its
2848 : grp_hint ot TOTALLY is set (this means either that there is more than one
2849 : direct read access or that we are attempting total scalarization) or
2850 : according to the following table:
2851 :
2852 : Access written to through a scalar type (once or more times)
2853 : |
2854 : | Written to in an assignment statement
2855 : | |
2856 : | | Access read as scalar _once_
2857 : | | |
2858 : | | | Read in an assignment statement
2859 : | | | |
2860 : | | | | Scalarize Comment
2861 : -----------------------------------------------------------------------------
2862 : 0 0 0 0 No access for the scalar
2863 : 0 0 0 1 No access for the scalar
2864 : 0 0 1 0 No Single read - won't help
2865 : 0 0 1 1 No The same case
2866 : 0 1 0 0 No access for the scalar
2867 : 0 1 0 1 No access for the scalar
2868 : 0 1 1 0 Yes s = *g; return s.i;
2869 : 0 1 1 1 Yes The same case as above
2870 : 1 0 0 0 No Won't help
2871 : 1 0 0 1 Yes s.i = 1; *g = s;
2872 : 1 0 1 0 Yes s.i = 5; g = s.i;
2873 : 1 0 1 1 Yes The same case as above
2874 : 1 1 0 0 No Won't help.
2875 : 1 1 0 1 Yes s.i = 1; *g = s;
2876 : 1 1 1 0 Yes s = *g; return s.i;
2877 : 1 1 1 1 Yes Any of the above yeses */
2878 :
2879 : static bool
2880 11140338 : analyze_access_subtree (struct access *root, struct access *parent,
2881 : bool allow_replacements, bool totally)
2882 : {
2883 11140338 : struct access *child;
2884 11140338 : HOST_WIDE_INT limit = root->offset + root->size;
2885 11140338 : HOST_WIDE_INT covered_to = root->offset;
2886 11140338 : bool scalar = is_gimple_reg_type (root->type);
2887 11140338 : bool hole = false, sth_created = false;
2888 :
2889 11140338 : if (parent)
2890 : {
2891 6834656 : if (parent->grp_read)
2892 6062767 : root->grp_read = 1;
2893 6834656 : if (parent->grp_assignment_read)
2894 2859666 : root->grp_assignment_read = 1;
2895 6834656 : if (parent->grp_write)
2896 4033867 : root->grp_write = 1;
2897 6834656 : if (parent->grp_assignment_write)
2898 2917117 : root->grp_assignment_write = 1;
2899 6834656 : if (!parent->grp_same_access_path)
2900 1154529 : root->grp_same_access_path = 0;
2901 : }
2902 :
2903 11140338 : if (root->grp_unscalarizable_region)
2904 : allow_replacements = false;
2905 :
2906 11016531 : if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2907 : allow_replacements = false;
2908 :
2909 11140338 : if (!totally && root->grp_result_of_prop_from_lhs)
2910 11140338 : allow_replacements = false;
2911 :
2912 17974994 : for (child = root->first_child; child; child = child->next_sibling)
2913 : {
2914 6834656 : if (totally)
2915 1818345 : covered_to = child->offset;
2916 : else
2917 5016311 : hole |= covered_to < child->offset;
2918 6834656 : sth_created |= analyze_access_subtree (child, root,
2919 6834656 : allow_replacements && !scalar
2920 6834656 : && !root->grp_partial_lhs,
2921 : totally);
2922 :
2923 6834656 : root->grp_unscalarized_data |= child->grp_unscalarized_data;
2924 6834656 : if (child->grp_covered)
2925 3250856 : covered_to += child->size;
2926 : else
2927 : hole = true;
2928 6834656 : if (totally && !hole)
2929 1817396 : covered_to = limit;
2930 : }
2931 :
2932 11140338 : if (allow_replacements && scalar && !root->first_child
2933 6723486 : && (totally || !root->grp_total_scalarization)
2934 : && (totally
2935 5007508 : || root->grp_hint
2936 4225209 : || ((root->grp_scalar_read || root->grp_assignment_read)
2937 1482447 : && (root->grp_scalar_write || root->grp_assignment_write))))
2938 : {
2939 : /* Always create access replacements that cover the whole access.
2940 : For integral types this means the precision has to match.
2941 : Avoid assumptions based on the integral type kind, too. */
2942 3605377 : if (INTEGRAL_TYPE_P (root->type)
2943 1612303 : && ((TREE_CODE (root->type) != INTEGER_TYPE
2944 1612303 : && TREE_CODE (root->type) != BITINT_TYPE)
2945 1553581 : || TYPE_PRECISION (root->type) != root->size)
2946 : /* But leave bitfield accesses alone. */
2947 3664105 : && (TREE_CODE (root->expr) != COMPONENT_REF
2948 57742 : || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2949 : {
2950 58435 : tree rt = root->type;
2951 58435 : gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2952 : && (root->size % BITS_PER_UNIT) == 0);
2953 58435 : if (BITINT_TYPE_P (root->type))
2954 6 : root->type = build_bitint_type (root->size, TYPE_UNSIGNED (rt));
2955 : else
2956 58429 : root->type = build_nonstandard_integer_type (root->size,
2957 58429 : TYPE_UNSIGNED (rt));
2958 116870 : root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2959 58435 : root->offset, root->reverse,
2960 : root->type, NULL, false);
2961 :
2962 58435 : if (dump_file && (dump_flags & TDF_DETAILS))
2963 : {
2964 0 : fprintf (dump_file, "Changing the type of a replacement for ");
2965 0 : print_generic_expr (dump_file, root->base);
2966 0 : fprintf (dump_file, " offset: %u, size: %u ",
2967 0 : (unsigned) root->offset, (unsigned) root->size);
2968 0 : fprintf (dump_file, " to an integer.\n");
2969 : }
2970 : }
2971 :
2972 3605377 : root->grp_to_be_replaced = 1;
2973 3605377 : root->replacement_decl = create_access_replacement (root);
2974 3605377 : sth_created = true;
2975 3605377 : hole = false;
2976 : }
2977 : else
2978 : {
2979 7534961 : if (allow_replacements
2980 3127481 : && scalar && !root->first_child
2981 3118109 : && !root->grp_total_scalarization
2982 3117969 : && (root->grp_scalar_write || root->grp_assignment_write)
2983 10277723 : && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2984 2742762 : DECL_UID (root->base)))
2985 : {
2986 457672 : gcc_checking_assert (!root->grp_scalar_read
2987 : && !root->grp_assignment_read);
2988 457672 : sth_created = true;
2989 457672 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2990 : {
2991 237883 : root->grp_to_be_debug_replaced = 1;
2992 237883 : root->replacement_decl = create_access_replacement (root);
2993 : }
2994 : }
2995 :
2996 7534961 : if (covered_to < limit)
2997 6319450 : hole = true;
2998 7534961 : if (scalar || !allow_replacements)
2999 4091195 : root->grp_total_scalarization = 0;
3000 : }
3001 :
3002 11140338 : if (!hole)
3003 4820572 : root->grp_covered = 1;
3004 6319766 : else if (root->grp_write || comes_initialized_p (root->base))
3005 5558143 : root->grp_unscalarized_data = 1; /* not covered and written to */
3006 11140338 : return sth_created;
3007 : }
3008 :
3009 : /* Analyze all access trees linked by next_grp by the means of
3010 : analyze_access_subtree. */
3011 : static bool
3012 3883593 : analyze_access_trees (struct access *access)
3013 : {
3014 3883593 : bool ret = false;
3015 :
3016 8189275 : while (access)
3017 : {
3018 4305682 : if (analyze_access_subtree (access, NULL, true,
3019 4305682 : access->grp_total_scalarization))
3020 2116505 : ret = true;
3021 4305682 : access = access->next_grp;
3022 : }
3023 :
3024 3883593 : return ret;
3025 : }
3026 :
3027 : /* Return true iff a potential new child of ACC at offset OFFSET and with size
3028 : SIZE would conflict with an already existing one. If exactly such a child
3029 : already exists in ACC, store a pointer to it in EXACT_MATCH. */
3030 :
3031 : static bool
3032 6889637 : child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset,
3033 : HOST_WIDE_INT size, struct access **exact_match)
3034 : {
3035 6889637 : struct access *child;
3036 :
3037 12098707 : for (child = acc->first_child; child; child = child->next_sibling)
3038 : {
3039 10659979 : if (child->offset == norm_offset && child->size == size)
3040 : {
3041 5412270 : *exact_match = child;
3042 5412270 : return true;
3043 : }
3044 :
3045 5247709 : if (child->offset < norm_offset + size
3046 5174391 : && child->offset + child->size > norm_offset)
3047 : return true;
3048 : }
3049 :
3050 : return false;
3051 : }
3052 :
3053 : /* Create a new child access of PARENT, with all properties just like MODEL
3054 : except for its offset and with its grp_write false and grp_read true.
3055 : Return the new access or NULL if it cannot be created. Note that this
3056 : access is created long after all splicing and sorting, it's not located in
3057 : any access vector and is automatically a representative of its group. Set
3058 : the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
3059 :
3060 : static struct access *
3061 1433519 : create_artificial_child_access (struct access *parent, struct access *model,
3062 : HOST_WIDE_INT new_offset,
3063 : bool set_grp_read, bool set_grp_write)
3064 : {
3065 1433519 : struct access **child;
3066 1433519 : tree expr = parent->base;
3067 :
3068 1433519 : gcc_assert (!model->grp_unscalarizable_region);
3069 :
3070 1433519 : struct access *access = access_pool.allocate ();
3071 1433519 : memset (access, 0, sizeof (struct access));
3072 1433519 : if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
3073 : parent->size, model->type,
3074 : model->size))
3075 : {
3076 27695 : access->grp_no_warning = true;
3077 27695 : expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
3078 : new_offset, model, NULL, false);
3079 : }
3080 :
3081 1433519 : access->base = parent->base;
3082 1433519 : access->expr = expr;
3083 1433519 : access->offset = new_offset;
3084 1433519 : access->size = model->size;
3085 1433519 : access->type = model->type;
3086 1433519 : access->parent = parent;
3087 1433519 : access->grp_read = set_grp_read;
3088 1433519 : access->grp_write = set_grp_write;
3089 1433519 : access->reverse = model->reverse;
3090 :
3091 1433519 : child = &parent->first_child;
3092 2626664 : while (*child && (*child)->offset < new_offset)
3093 1193145 : child = &(*child)->next_sibling;
3094 :
3095 1433519 : access->next_sibling = *child;
3096 1433519 : *child = access;
3097 :
3098 1433519 : return access;
3099 : }
3100 :
3101 :
3102 : /* Beginning with ACCESS, traverse its whole access subtree and mark all
3103 : sub-trees as written to. If any of them has not been marked so previously
3104 : and has assignment links leading from it, re-enqueue it. */
3105 :
3106 : static void
3107 1589829 : subtree_mark_written_and_rhs_enqueue (struct access *access)
3108 : {
3109 1589829 : if (access->grp_write)
3110 : return;
3111 1518172 : access->grp_write = true;
3112 1518172 : add_access_to_rhs_work_queue (access);
3113 :
3114 1518172 : struct access *child;
3115 2145784 : for (child = access->first_child; child; child = child->next_sibling)
3116 627612 : subtree_mark_written_and_rhs_enqueue (child);
3117 : }
3118 :
3119 : /* If there is still budget to create a propagation access for DECL, return
3120 : true and decrement the budget. Otherwise return false. */
3121 :
3122 : static bool
3123 1437653 : budget_for_propagation_access (tree decl)
3124 : {
3125 1437653 : unsigned b, *p = propagation_budget->get (decl);
3126 1437653 : if (p)
3127 869106 : b = *p;
3128 : else
3129 568547 : b = param_sra_max_propagations;
3130 :
3131 1437653 : if (b == 0)
3132 : return false;
3133 1433525 : b--;
3134 :
3135 1433525 : if (b == 0 && dump_file && (dump_flags & TDF_DETAILS))
3136 : {
3137 0 : fprintf (dump_file, "The propagation budget of ");
3138 0 : print_generic_expr (dump_file, decl);
3139 0 : fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl));
3140 : }
3141 1433525 : propagation_budget->put (decl, b);
3142 1433525 : return true;
3143 : }
3144 :
3145 : /* Return true if ACC or any of its subaccesses has grp_child set. */
3146 :
3147 : static bool
3148 2189 : access_or_its_child_written (struct access *acc)
3149 : {
3150 2189 : if (acc->grp_write)
3151 : return true;
3152 2327 : for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling)
3153 595 : if (access_or_its_child_written (sub))
3154 : return true;
3155 : return false;
3156 : }
3157 :
3158 : /* Propagate subaccesses and grp_write flags of RACC across an assignment link
3159 : to LACC. Enqueue sub-accesses as necessary so that the write flag is
3160 : propagated transitively. Return true if anything changed. Additionally, if
3161 : RACC is a scalar access but LACC is not, change the type of the latter, if
3162 : possible. */
3163 :
3164 : static bool
3165 3589496 : propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc)
3166 : {
3167 3589496 : struct access *rchild;
3168 3589496 : HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
3169 3589496 : bool ret = false;
3170 :
3171 : /* IF the LHS is still not marked as being written to, we only need to do so
3172 : if the RHS at this level actually was. */
3173 3589496 : if (!lacc->grp_write)
3174 : {
3175 1618319 : gcc_checking_assert (!comes_initialized_p (racc->base));
3176 1618319 : if (racc->grp_write)
3177 : {
3178 770706 : subtree_mark_written_and_rhs_enqueue (lacc);
3179 770706 : ret = true;
3180 : }
3181 : }
3182 :
3183 3589496 : if (is_gimple_reg_type (lacc->type)
3184 2808489 : || lacc->grp_unscalarizable_region
3185 6397372 : || racc->grp_unscalarizable_region)
3186 : {
3187 782674 : if (!lacc->grp_write)
3188 : {
3189 17696 : ret = true;
3190 17696 : subtree_mark_written_and_rhs_enqueue (lacc);
3191 : }
3192 782674 : return ret;
3193 : }
3194 :
3195 2806822 : if (is_gimple_reg_type (racc->type))
3196 : {
3197 137259 : if (!lacc->grp_write)
3198 : {
3199 2344 : ret = true;
3200 2344 : subtree_mark_written_and_rhs_enqueue (lacc);
3201 : }
3202 137259 : if (!lacc->first_child
3203 137079 : && !racc->first_child
3204 274036 : && !types_risk_mangled_binary_repr_p (racc->type, lacc->type))
3205 : {
3206 : /* We are about to change the access type from aggregate to scalar,
3207 : so we need to put the reverse flag onto the access, if any. */
3208 136777 : const bool reverse
3209 136777 : = TYPE_REVERSE_STORAGE_ORDER (lacc->type)
3210 1 : && !POINTER_TYPE_P (racc->type)
3211 136777 : && !VECTOR_TYPE_P (racc->type);
3212 136777 : tree t = lacc->base;
3213 :
3214 136777 : lacc->type = racc->type;
3215 : /* We know racc and lacc are of different types so can pass -1 as
3216 : cur_size. */
3217 136777 : if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
3218 : lacc->offset, -1,
3219 : racc->type, racc->size))
3220 : {
3221 136529 : lacc->expr = t;
3222 136529 : lacc->grp_same_access_path = true;
3223 : }
3224 : else
3225 : {
3226 248 : lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
3227 : lacc->base, lacc->offset,
3228 : racc, NULL, false);
3229 248 : if (TREE_CODE (lacc->expr) == MEM_REF)
3230 248 : REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse;
3231 248 : lacc->grp_no_warning = true;
3232 248 : lacc->grp_same_access_path = false;
3233 : }
3234 136777 : lacc->reverse = reverse;
3235 : }
3236 137259 : return ret;
3237 : }
3238 :
3239 5764731 : for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
3240 : {
3241 3095168 : struct access *new_acc = NULL;
3242 3095168 : HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
3243 :
3244 3095168 : if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size,
3245 : &new_acc))
3246 : {
3247 2534277 : if (new_acc)
3248 : {
3249 2509669 : if (!new_acc->grp_write && rchild->grp_write)
3250 : {
3251 165595 : gcc_assert (!lacc->grp_write);
3252 165595 : subtree_mark_written_and_rhs_enqueue (new_acc);
3253 165595 : ret = true;
3254 : }
3255 :
3256 2509669 : rchild->grp_hint = 1;
3257 2509669 : new_acc->grp_hint |= new_acc->grp_read;
3258 2509669 : if (rchild->first_child
3259 2509669 : && propagate_subaccesses_from_rhs (new_acc, rchild))
3260 : {
3261 1293 : ret = 1;
3262 1293 : add_access_to_rhs_work_queue (new_acc);
3263 : }
3264 : }
3265 : else
3266 : {
3267 24608 : if (!lacc->grp_write)
3268 : {
3269 4957 : ret = true;
3270 4957 : subtree_mark_written_and_rhs_enqueue (lacc);
3271 : }
3272 : }
3273 2539454 : continue;
3274 : }
3275 :
3276 566068 : if (rchild->grp_unscalarizable_region
3277 560891 : || !budget_for_propagation_access (lacc->base))
3278 : {
3279 5177 : if (!lacc->grp_write && access_or_its_child_written (rchild))
3280 : {
3281 424 : ret = true;
3282 424 : subtree_mark_written_and_rhs_enqueue (lacc);
3283 : }
3284 5177 : continue;
3285 : }
3286 :
3287 555714 : rchild->grp_hint = 1;
3288 : /* Because get_ref_base_and_extent always includes padding in size for
3289 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3290 : type, we might be actually attempting to here to create a child of the
3291 : same type as the parent. */
3292 555714 : if (!types_compatible_p (lacc->type, rchild->type))
3293 555714 : new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
3294 : false,
3295 555714 : (lacc->grp_write
3296 555714 : || rchild->grp_write));
3297 : else
3298 0 : new_acc = lacc;
3299 555714 : gcc_checking_assert (new_acc);
3300 555714 : if (racc->first_child)
3301 555714 : propagate_subaccesses_from_rhs (new_acc, rchild);
3302 :
3303 555714 : add_access_to_rhs_work_queue (lacc);
3304 555714 : ret = true;
3305 : }
3306 :
3307 : return ret;
3308 : }
3309 :
3310 : /* Propagate subaccesses of LACC across an assignment link to RACC if they
3311 : should inhibit total scalarization of the corresponding area. No flags are
3312 : being propagated in the process. Return true if anything changed. */
3313 :
3314 : static bool
3315 6050960 : propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc)
3316 : {
3317 6050960 : if (is_gimple_reg_type (racc->type)
3318 2130231 : || lacc->grp_unscalarizable_region
3319 8180180 : || racc->grp_unscalarizable_region)
3320 : return false;
3321 :
3322 : /* TODO: Do we want set some new racc flag to stop potential total
3323 : scalarization if lacc is a scalar access (and none fo the two have
3324 : children)? */
3325 :
3326 2129201 : bool ret = false;
3327 2129201 : HOST_WIDE_INT norm_delta = racc->offset - lacc->offset;
3328 2129201 : for (struct access *lchild = lacc->first_child;
3329 5928122 : lchild;
3330 3798921 : lchild = lchild->next_sibling)
3331 : {
3332 3798921 : struct access *matching_acc = NULL;
3333 3798921 : HOST_WIDE_INT norm_offset = lchild->offset + norm_delta;
3334 :
3335 6720031 : if (lchild->grp_unscalarizable_region
3336 3794469 : || child_would_conflict_in_acc (racc, norm_offset, lchild->size,
3337 : &matching_acc)
3338 4676758 : || !budget_for_propagation_access (racc->base))
3339 : {
3340 2921110 : if (matching_acc
3341 2921110 : && propagate_subaccesses_from_lhs (lchild, matching_acc))
3342 198 : add_access_to_lhs_work_queue (matching_acc);
3343 2921110 : continue;
3344 : }
3345 :
3346 : /* Because get_ref_base_and_extent always includes padding in size for
3347 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3348 : type, we might be actually attempting to here to create a child of the
3349 : same type as the parent. */
3350 877811 : if (!types_compatible_p (racc->type, lchild->type))
3351 : {
3352 877805 : struct access *new_acc
3353 877805 : = create_artificial_child_access (racc, lchild, norm_offset,
3354 : true, false);
3355 877805 : new_acc->grp_result_of_prop_from_lhs = 1;
3356 877805 : propagate_subaccesses_from_lhs (lchild, new_acc);
3357 : }
3358 : else
3359 6 : propagate_subaccesses_from_lhs (lchild, racc);
3360 877811 : ret = true;
3361 : }
3362 : return ret;
3363 : }
3364 :
3365 : /* Propagate all subaccesses across assignment links. */
3366 :
3367 : static void
3368 730214 : propagate_all_subaccesses (void)
3369 : {
3370 730214 : propagation_budget = new hash_map<tree, unsigned>;
3371 2245395 : while (rhs_work_queue_head)
3372 : {
3373 1515181 : struct access *racc = pop_access_from_rhs_work_queue ();
3374 1515181 : struct assign_link *link;
3375 :
3376 1515181 : if (racc->group_representative)
3377 1514466 : racc= racc->group_representative;
3378 1515181 : gcc_assert (racc->first_rhs_link);
3379 :
3380 4537568 : for (link = racc->first_rhs_link; link; link = link->next_rhs)
3381 : {
3382 3022387 : struct access *lacc = link->lacc;
3383 :
3384 3022387 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3385 6722 : continue;
3386 3015665 : lacc = lacc->group_representative;
3387 :
3388 3015665 : bool reque_parents = false;
3389 3015665 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3390 : {
3391 1639 : if (!lacc->grp_write)
3392 : {
3393 495 : subtree_mark_written_and_rhs_enqueue (lacc);
3394 495 : reque_parents = true;
3395 : }
3396 : }
3397 3014026 : else if (propagate_subaccesses_from_rhs (lacc, racc))
3398 : reque_parents = true;
3399 :
3400 : if (reque_parents)
3401 1232678 : do
3402 : {
3403 1232678 : add_access_to_rhs_work_queue (lacc);
3404 1232678 : lacc = lacc->parent;
3405 : }
3406 1232678 : while (lacc);
3407 : }
3408 : }
3409 :
3410 2042153 : while (lhs_work_queue_head)
3411 : {
3412 1311939 : struct access *lacc = pop_access_from_lhs_work_queue ();
3413 1311939 : struct assign_link *link;
3414 :
3415 1311939 : if (lacc->group_representative)
3416 1308742 : lacc = lacc->group_representative;
3417 1311939 : gcc_assert (lacc->first_lhs_link);
3418 :
3419 1311939 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3420 3889 : continue;
3421 :
3422 3579394 : for (link = lacc->first_lhs_link; link; link = link->next_lhs)
3423 : {
3424 2271344 : struct access *racc = link->racc;
3425 :
3426 2271344 : if (racc->group_representative)
3427 2270749 : racc = racc->group_representative;
3428 2271344 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3429 796 : continue;
3430 2270548 : if (propagate_subaccesses_from_lhs (lacc, racc))
3431 348270 : add_access_to_lhs_work_queue (racc);
3432 : }
3433 : }
3434 1460428 : delete propagation_budget;
3435 730214 : }
3436 :
3437 : /* Return true if the forest beginning with ROOT does not contain
3438 : unscalarizable regions or non-byte aligned accesses. */
3439 :
3440 : static bool
3441 748238 : can_totally_scalarize_forest_p (struct access *root)
3442 : {
3443 748238 : struct access *access = root;
3444 2164685 : do
3445 : {
3446 2164685 : if (access->grp_unscalarizable_region
3447 2162716 : || (access->offset % BITS_PER_UNIT) != 0
3448 2162331 : || (access->size % BITS_PER_UNIT) != 0
3449 4323178 : || (is_gimple_reg_type (access->type)
3450 1417093 : && access->first_child))
3451 : return false;
3452 :
3453 2158209 : if (access->first_child)
3454 : access = access->first_child;
3455 1535884 : else if (access->next_sibling)
3456 : access = access->next_sibling;
3457 : else
3458 : {
3459 1435284 : while (access->parent && !access->next_sibling)
3460 : access = access->parent;
3461 817954 : if (access->next_sibling)
3462 : access = access->next_sibling;
3463 : else
3464 : {
3465 764889 : gcc_assert (access == root);
3466 764889 : root = root->next_grp;
3467 764889 : access = root;
3468 : }
3469 : }
3470 : }
3471 2158209 : while (access);
3472 : return true;
3473 : }
3474 :
3475 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3476 : reference EXPR for total scalarization purposes and mark it as such. Within
3477 : the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3478 :
3479 : static struct access *
3480 490609 : create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos,
3481 : HOST_WIDE_INT size, tree type, tree expr,
3482 : struct access **ptr,
3483 : struct access *next_sibling)
3484 : {
3485 490609 : struct access *access = access_pool.allocate ();
3486 490609 : memset (access, 0, sizeof (struct access));
3487 490609 : access->base = parent->base;
3488 490609 : access->offset = pos;
3489 490609 : access->size = size;
3490 490609 : access->expr = expr;
3491 490609 : access->type = type;
3492 490609 : access->parent = parent;
3493 490609 : access->grp_write = parent->grp_write;
3494 490609 : access->grp_total_scalarization = 1;
3495 490609 : access->grp_hint = 1;
3496 490609 : access->grp_same_access_path = 0;
3497 490609 : access->reverse = reverse_storage_order_for_component_p (expr);
3498 :
3499 490609 : access->next_sibling = next_sibling;
3500 490609 : *ptr = access;
3501 490609 : return access;
3502 : }
3503 :
3504 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3505 : reference EXPR for total scalarization purposes and mark it as such, link it
3506 : at *PTR and reshape the tree so that those elements at *PTR and their
3507 : siblings which fall within the part described by POS and SIZE are moved to
3508 : be children of the new access. If a partial overlap is detected, return
3509 : NULL. */
3510 :
3511 : static struct access *
3512 490609 : create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos,
3513 : HOST_WIDE_INT size, tree type, tree expr,
3514 : struct access **ptr)
3515 : {
3516 490609 : struct access **p = ptr;
3517 :
3518 680532 : while (*p && (*p)->offset < pos + size)
3519 : {
3520 189923 : if ((*p)->offset + (*p)->size > pos + size)
3521 : return NULL;
3522 189923 : p = &(*p)->next_sibling;
3523 : }
3524 :
3525 490609 : struct access *next_child = *ptr;
3526 490609 : struct access *new_acc
3527 490609 : = create_total_scalarization_access (parent, pos, size, type, expr,
3528 : ptr, *p);
3529 490609 : if (p != ptr)
3530 : {
3531 77648 : new_acc->first_child = next_child;
3532 77648 : *p = NULL;
3533 267571 : for (struct access *a = next_child; a; a = a->next_sibling)
3534 189923 : a->parent = new_acc;
3535 : }
3536 : return new_acc;
3537 : }
3538 :
3539 : static bool totally_scalarize_subtree (struct access *root);
3540 :
3541 : /* Return true if INNER is either the same type as OUTER or if it is the type
3542 : of a record field in OUTER at offset zero, possibly in nested
3543 : sub-records. */
3544 :
3545 : static bool
3546 180672 : access_and_field_type_match_p (tree outer, tree inner)
3547 : {
3548 180672 : if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner))
3549 : return true;
3550 525 : if (TREE_CODE (outer) != RECORD_TYPE)
3551 : return false;
3552 513 : tree fld = TYPE_FIELDS (outer);
3553 9856 : while (fld)
3554 : {
3555 9699 : if (TREE_CODE (fld) == FIELD_DECL)
3556 : {
3557 574 : if (!zerop (DECL_FIELD_OFFSET (fld)))
3558 : return false;
3559 574 : if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner)
3560 : return true;
3561 402 : if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE)
3562 218 : fld = TYPE_FIELDS (TREE_TYPE (fld));
3563 : else
3564 : return false;
3565 : }
3566 : else
3567 9125 : fld = DECL_CHAIN (fld);
3568 : }
3569 : return false;
3570 : }
3571 :
3572 : /* Return type of total_should_skip_creating_access indicating whether a total
3573 : scalarization access for a field/element should be created, whether it
3574 : already exists or whether the entire total scalarization has to fail. */
3575 :
3576 : enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED};
3577 :
3578 : /* Do all the necessary steps in total scalarization when the given aggregate
3579 : type has a TYPE at POS with the given SIZE should be put into PARENT and
3580 : when we have processed all its siblings with smaller offsets up until and
3581 : including LAST_SEEN_SIBLING (which can be NULL).
3582 :
3583 : If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3584 : appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3585 : creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3586 : representing the described part of the aggregate for the purposes of total
3587 : scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3588 : prevents total scalarization from happening at all. */
3589 :
3590 : static enum total_sra_field_state
3591 1818963 : total_should_skip_creating_access (struct access *parent,
3592 : struct access **last_seen_sibling,
3593 : tree type, HOST_WIDE_INT pos,
3594 : HOST_WIDE_INT size)
3595 : {
3596 1818963 : struct access *next_child;
3597 1818963 : if (!*last_seen_sibling)
3598 828615 : next_child = parent->first_child;
3599 : else
3600 990348 : next_child = (*last_seen_sibling)->next_sibling;
3601 :
3602 : /* First, traverse the chain of siblings until it points to an access with
3603 : offset at least equal to POS. Check all skipped accesses whether they
3604 : span the POS boundary and if so, return with a failure. */
3605 1818964 : while (next_child && next_child->offset < pos)
3606 : {
3607 1 : if (next_child->offset + next_child->size > pos)
3608 : return TOTAL_FLD_FAILED;
3609 1 : *last_seen_sibling = next_child;
3610 1 : next_child = next_child->next_sibling;
3611 : }
3612 :
3613 : /* Now check whether next_child has exactly the right POS and SIZE and if so,
3614 : whether it can represent what we need and can be totally scalarized
3615 : itself. */
3616 1818963 : if (next_child && next_child->offset == pos
3617 1402983 : && next_child->size == size)
3618 : {
3619 1328206 : if (!is_gimple_reg_type (next_child->type)
3620 1328206 : && (!access_and_field_type_match_p (type, next_child->type)
3621 180319 : || !totally_scalarize_subtree (next_child)))
3622 399 : return TOTAL_FLD_FAILED;
3623 :
3624 1327807 : *last_seen_sibling = next_child;
3625 1327807 : return TOTAL_FLD_DONE;
3626 : }
3627 :
3628 : /* If the child we're looking at would partially overlap, we just cannot
3629 : totally scalarize. */
3630 : if (next_child
3631 105040 : && next_child->offset < pos + size
3632 77796 : && next_child->offset + next_child->size > pos + size)
3633 : return TOTAL_FLD_FAILED;
3634 :
3635 490721 : if (is_gimple_reg_type (type))
3636 : {
3637 : /* We don't scalarize accesses that are children of other scalar type
3638 : accesses, so if we go on and create an access for a register type,
3639 : there should not be any pre-existing children. There are rare cases
3640 : where the requested type is a vector but we already have register
3641 : accesses for all its elements which is equally good. Detect that
3642 : situation or whether we need to bail out. */
3643 :
3644 : HOST_WIDE_INT covered = pos;
3645 : bool skipping = false;
3646 : while (next_child
3647 372477 : && next_child->offset + next_child->size <= pos + size)
3648 : {
3649 428 : if (next_child->offset != covered
3650 428 : || !is_gimple_reg_type (next_child->type))
3651 : return TOTAL_FLD_FAILED;
3652 :
3653 428 : covered += next_child->size;
3654 428 : *last_seen_sibling = next_child;
3655 428 : next_child = next_child->next_sibling;
3656 428 : skipping = true;
3657 : }
3658 :
3659 372049 : if (skipping)
3660 : {
3661 112 : if (covered != pos + size)
3662 : return TOTAL_FLD_FAILED;
3663 : else
3664 : return TOTAL_FLD_DONE;
3665 : }
3666 : }
3667 :
3668 : return TOTAL_FLD_CREATE;
3669 : }
3670 :
3671 : /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3672 : spanning all uncovered areas covered by ROOT, return false if the attempt
3673 : failed. All created accesses will have grp_unscalarizable_region set (and
3674 : should be ignored if the function returns false). */
3675 :
3676 : static bool
3677 829059 : totally_scalarize_subtree (struct access *root)
3678 : {
3679 829059 : gcc_checking_assert (!root->grp_unscalarizable_region);
3680 829059 : gcc_checking_assert (!is_gimple_reg_type (root->type));
3681 :
3682 829059 : struct access *last_seen_sibling = NULL;
3683 :
3684 829059 : switch (TREE_CODE (root->type))
3685 : {
3686 815493 : case RECORD_TYPE:
3687 9856851 : for (tree fld = TYPE_FIELDS (root->type); fld; fld = DECL_CHAIN (fld))
3688 9041836 : if (TREE_CODE (fld) == FIELD_DECL)
3689 : {
3690 1820710 : tree ft = TREE_TYPE (fld);
3691 1820710 : HOST_WIDE_INT fsize = tree_to_uhwi (DECL_SIZE (fld));
3692 1820710 : if (!fsize)
3693 32281 : continue;
3694 :
3695 1788429 : HOST_WIDE_INT pos = root->offset + int_bit_position (fld);
3696 1788429 : if (pos + fsize > root->offset + root->size)
3697 : return false;
3698 1788429 : enum total_sra_field_state
3699 1788429 : state = total_should_skip_creating_access (root,
3700 : &last_seen_sibling,
3701 : ft, pos, fsize);
3702 1788429 : switch (state)
3703 : {
3704 : case TOTAL_FLD_FAILED:
3705 : return false;
3706 1321433 : case TOTAL_FLD_DONE:
3707 1321433 : continue;
3708 466589 : case TOTAL_FLD_CREATE:
3709 466589 : break;
3710 0 : default:
3711 0 : gcc_unreachable ();
3712 : }
3713 :
3714 466589 : struct access **p = (last_seen_sibling
3715 466589 : ? &last_seen_sibling->next_sibling
3716 : : &root->first_child);
3717 466589 : tree nref = build3 (COMPONENT_REF, ft, root->expr, fld, NULL_TREE);
3718 466589 : struct access *new_child
3719 466589 : = create_total_access_and_reshape (root, pos, fsize, ft, nref, p);
3720 466589 : if (!new_child)
3721 : return false;
3722 :
3723 466589 : if (!is_gimple_reg_type (ft)
3724 466589 : && !totally_scalarize_subtree (new_child))
3725 : return false;
3726 466518 : last_seen_sibling = new_child;
3727 : }
3728 : break;
3729 13566 : case ARRAY_TYPE:
3730 13566 : {
3731 13566 : tree elemtype = TREE_TYPE (root->type);
3732 13566 : HOST_WIDE_INT el_size;
3733 13566 : offset_int idx, max;
3734 13566 : if (!prepare_iteration_over_array_elts (root->type, &el_size,
3735 : &idx, &max))
3736 : break;
3737 :
3738 13566 : for (HOST_WIDE_INT pos = root->offset;
3739 44052 : idx <= max;
3740 30486 : pos += el_size, ++idx)
3741 : {
3742 30534 : enum total_sra_field_state
3743 30534 : state = total_should_skip_creating_access (root,
3744 : &last_seen_sibling,
3745 : elemtype, pos,
3746 : el_size);
3747 30534 : switch (state)
3748 : {
3749 : case TOTAL_FLD_FAILED:
3750 48 : return false;
3751 6466 : case TOTAL_FLD_DONE:
3752 6466 : continue;
3753 24020 : case TOTAL_FLD_CREATE:
3754 24020 : break;
3755 0 : default:
3756 0 : gcc_unreachable ();
3757 : }
3758 :
3759 24020 : struct access **p = (last_seen_sibling
3760 24020 : ? &last_seen_sibling->next_sibling
3761 : : &root->first_child);
3762 48040 : tree nref = build4 (ARRAY_REF, elemtype, root->expr,
3763 24020 : wide_int_to_tree (TYPE_DOMAIN (root->type),
3764 24020 : idx),
3765 : NULL_TREE, NULL_TREE);
3766 24020 : struct access *new_child
3767 24020 : = create_total_access_and_reshape (root, pos, el_size, elemtype,
3768 : nref, p);
3769 24020 : if (!new_child)
3770 : return false;
3771 :
3772 24020 : if (!is_gimple_reg_type (elemtype)
3773 24020 : && !totally_scalarize_subtree (new_child))
3774 : return false;
3775 24020 : last_seen_sibling = new_child;
3776 : }
3777 : }
3778 13518 : break;
3779 0 : default:
3780 0 : gcc_unreachable ();
3781 : }
3782 : return true;
3783 : }
3784 :
3785 : /* Get the total total scalarization size limit in the current function. */
3786 :
3787 : unsigned HOST_WIDE_INT
3788 737114 : sra_get_max_scalarization_size (void)
3789 : {
3790 737114 : bool optimize_speed_p = !optimize_function_for_size_p (cfun);
3791 : /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3792 : fall back to a target default. */
3793 737114 : unsigned HOST_WIDE_INT max_scalarization_size
3794 737114 : = get_move_ratio (optimize_speed_p) * MOVE_MAX;
3795 :
3796 737114 : if (optimize_speed_p)
3797 : {
3798 716962 : if (OPTION_SET_P (param_sra_max_scalarization_size_speed))
3799 9 : max_scalarization_size = param_sra_max_scalarization_size_speed;
3800 : }
3801 : else
3802 : {
3803 20152 : if (OPTION_SET_P (param_sra_max_scalarization_size_size))
3804 0 : max_scalarization_size = param_sra_max_scalarization_size_size;
3805 : }
3806 737114 : max_scalarization_size *= BITS_PER_UNIT;
3807 737114 : return max_scalarization_size;
3808 : }
3809 :
3810 : /* Go through all accesses collected throughout the (intraprocedural) analysis
3811 : stage, exclude overlapping ones, identify representatives and build trees
3812 : out of them, making decisions about scalarization on the way. Return true
3813 : iff there are any to-be-scalarized variables after this stage. */
3814 :
3815 : static bool
3816 730214 : analyze_all_variable_accesses (void)
3817 : {
3818 730214 : int res = 0;
3819 730214 : bitmap tmp = BITMAP_ALLOC (NULL);
3820 730214 : bitmap_iterator bi;
3821 730214 : unsigned i;
3822 :
3823 730214 : bitmap_copy (tmp, candidate_bitmap);
3824 4776861 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3825 : {
3826 4046647 : tree var = candidate (i);
3827 4046647 : struct access *access;
3828 :
3829 4046647 : access = sort_and_splice_var_accesses (var);
3830 4046647 : if (!access || !build_access_trees (access))
3831 163054 : disqualify_candidate (var,
3832 : "No or inhibitingly overlapping accesses.");
3833 : }
3834 :
3835 730214 : propagate_all_subaccesses ();
3836 :
3837 730214 : unsigned HOST_WIDE_INT max_scalarization_size
3838 730214 : = sra_get_max_scalarization_size ();
3839 4613807 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3840 3883593 : if (bitmap_bit_p (should_scalarize_away_bitmap, i)
3841 3883593 : && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
3842 : {
3843 820889 : tree var = candidate (i);
3844 820889 : if (!VAR_P (var))
3845 71734 : continue;
3846 :
3847 749155 : if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) > max_scalarization_size)
3848 : {
3849 7179 : if (dump_file && (dump_flags & TDF_DETAILS))
3850 : {
3851 0 : fprintf (dump_file, "Too big to totally scalarize: ");
3852 0 : print_generic_expr (dump_file, var);
3853 0 : fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
3854 : }
3855 7179 : continue;
3856 : }
3857 :
3858 741976 : bool all_types_ok = true;
3859 741976 : for (struct access *access = get_first_repr_for_decl (var);
3860 1468392 : access;
3861 726416 : access = access->next_grp)
3862 748238 : if (!can_totally_scalarize_forest_p (access)
3863 1490000 : || !totally_scalarizable_type_p (access->type,
3864 741762 : constant_decl_p (var),
3865 : 0, nullptr))
3866 : {
3867 : all_types_ok = false;
3868 : break;
3869 : }
3870 741976 : if (!all_types_ok)
3871 21822 : continue;
3872 :
3873 720154 : if (dump_file && (dump_flags & TDF_DETAILS))
3874 : {
3875 1 : fprintf (dump_file, "Will attempt to totally scalarize ");
3876 1 : print_generic_expr (dump_file, var);
3877 1 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3878 : }
3879 720154 : bool scalarized = true;
3880 720154 : for (struct access *access = get_first_repr_for_decl (var);
3881 1446159 : access;
3882 726005 : access = access->next_grp)
3883 726414 : if (!is_gimple_reg_type (access->type)
3884 726414 : && !totally_scalarize_subtree (access))
3885 : {
3886 : scalarized = false;
3887 : break;
3888 : }
3889 :
3890 720154 : if (scalarized)
3891 719745 : for (struct access *access = get_first_repr_for_decl (var);
3892 1445750 : access;
3893 726005 : access = access->next_grp)
3894 726005 : access->grp_total_scalarization = true;
3895 : }
3896 :
3897 730214 : if (flag_checking)
3898 730214 : verify_all_sra_access_forests ();
3899 :
3900 730214 : bitmap_copy (tmp, candidate_bitmap);
3901 4613807 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3902 : {
3903 3883593 : tree var = candidate (i);
3904 3883593 : struct access *access = get_first_repr_for_decl (var);
3905 :
3906 3883593 : if (analyze_access_trees (access))
3907 : {
3908 1770599 : res++;
3909 1770599 : if (dump_file && (dump_flags & TDF_DETAILS))
3910 : {
3911 8 : fprintf (dump_file, "\nAccess trees for ");
3912 8 : print_generic_expr (dump_file, var);
3913 8 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3914 8 : dump_access_tree (dump_file, access);
3915 8 : fprintf (dump_file, "\n");
3916 : }
3917 : }
3918 : else
3919 2112994 : disqualify_candidate (var, "No scalar replacements to be created.");
3920 : }
3921 :
3922 730214 : BITMAP_FREE (tmp);
3923 :
3924 730214 : if (res)
3925 : {
3926 432236 : statistics_counter_event (cfun, "Scalarized aggregates", res);
3927 432236 : return true;
3928 : }
3929 : else
3930 : return false;
3931 : }
3932 :
3933 : /* Generate statements copying scalar replacements of accesses within a subtree
3934 : into or out of AGG. ACCESS, all its children, siblings and their children
3935 : are to be processed. AGG is an aggregate type expression (can be a
3936 : declaration but does not have to be, it can for example also be a mem_ref or
3937 : a series of handled components). TOP_OFFSET is the offset of the processed
3938 : subtree which has to be subtracted from offsets of individual accesses to
3939 : get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3940 : replacements in the interval <start_offset, start_offset + chunk_size>,
3941 : otherwise copy all. GSI is a statement iterator used to place the new
3942 : statements. WRITE should be true when the statements should write from AGG
3943 : to the replacement and false if vice versa. If INSERT_AFTER is true, new
3944 : statements will be added after the current statement in GSI, they will be
3945 : added before the statement otherwise. If FORCE_REF_ALL is true then
3946 : memory accesses will use alias-set zero. */
3947 :
3948 : static void
3949 1915175 : generate_subtree_copies (struct access *access, tree agg,
3950 : HOST_WIDE_INT top_offset,
3951 : HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
3952 : gimple_stmt_iterator *gsi, bool write,
3953 : bool insert_after, location_t loc,
3954 : bool force_ref_all = false)
3955 : {
3956 : /* Never write anything into constant pool decls. See PR70602. */
3957 3830350 : if (!write && constant_decl_p (agg))
3958 : return;
3959 4646726 : do
3960 : {
3961 4646726 : if (chunk_size && access->offset >= start_offset + chunk_size)
3962 : return;
3963 :
3964 4646726 : if (access->grp_to_be_replaced
3965 3645020 : && (chunk_size == 0
3966 0 : || access->offset + access->size > start_offset))
3967 : {
3968 3645020 : tree expr, repl = get_access_replacement (access);
3969 3645020 : gassign *stmt;
3970 :
3971 3645020 : expr = build_ref_for_model (loc, agg, access->offset - top_offset,
3972 : access, gsi, insert_after, force_ref_all);
3973 :
3974 3645020 : if (write)
3975 : {
3976 1648625 : if (access->grp_partial_lhs)
3977 8 : expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
3978 8 : !insert_after,
3979 : insert_after ? GSI_NEW_STMT
3980 : : GSI_SAME_STMT);
3981 1648625 : stmt = gimple_build_assign (repl, expr);
3982 : }
3983 : else
3984 : {
3985 1996395 : suppress_warning (repl /* Be more selective! */);
3986 1996395 : if (access->grp_partial_lhs)
3987 72 : repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3988 72 : !insert_after,
3989 : insert_after ? GSI_NEW_STMT
3990 : : GSI_SAME_STMT);
3991 1996395 : stmt = gimple_build_assign (expr, repl);
3992 : }
3993 3645020 : gimple_set_location (stmt, loc);
3994 :
3995 3645020 : if (insert_after)
3996 1648625 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3997 : else
3998 1996395 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3999 3645020 : update_stmt (stmt);
4000 3645020 : sra_stats.subtree_copies++;
4001 3645020 : }
4002 1001706 : else if (write
4003 389161 : && access->grp_to_be_debug_replaced
4004 5724 : && (chunk_size == 0
4005 0 : || access->offset + access->size > start_offset))
4006 : {
4007 5724 : gdebug *ds;
4008 11448 : tree drhs = build_debug_ref_for_model (loc, agg,
4009 5724 : access->offset - top_offset,
4010 : access);
4011 5724 : ds = gimple_build_debug_bind (get_access_replacement (access),
4012 : drhs, gsi_stmt (*gsi));
4013 5724 : if (insert_after)
4014 5724 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4015 : else
4016 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4017 : }
4018 :
4019 4646726 : if (access->first_child)
4020 461263 : generate_subtree_copies (access->first_child, agg, top_offset,
4021 : start_offset, chunk_size, gsi,
4022 : write, insert_after, loc, force_ref_all);
4023 :
4024 4646726 : access = access->next_sibling;
4025 : }
4026 4646726 : while (access);
4027 : }
4028 :
4029 : /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
4030 : root of the subtree to be processed. GSI is the statement iterator used
4031 : for inserting statements which are added after the current statement if
4032 : INSERT_AFTER is true or before it otherwise. */
4033 :
4034 : static void
4035 542041 : init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
4036 : bool insert_after, location_t loc)
4037 :
4038 : {
4039 542041 : struct access *child;
4040 :
4041 542041 : if (access->grp_to_be_replaced)
4042 : {
4043 248507 : gassign *stmt;
4044 :
4045 248507 : stmt = gimple_build_assign (get_access_replacement (access),
4046 : build_zero_cst (access->type));
4047 248507 : if (insert_after)
4048 33178 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4049 : else
4050 215329 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4051 248507 : update_stmt (stmt);
4052 248507 : gimple_set_location (stmt, loc);
4053 : }
4054 293534 : else if (access->grp_to_be_debug_replaced)
4055 : {
4056 29640 : gdebug *ds
4057 29640 : = gimple_build_debug_bind (get_access_replacement (access),
4058 : build_zero_cst (access->type),
4059 : gsi_stmt (*gsi));
4060 29640 : if (insert_after)
4061 29640 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4062 : else
4063 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4064 : }
4065 :
4066 937324 : for (child = access->first_child; child; child = child->next_sibling)
4067 395283 : init_subtree_with_zero (child, gsi, insert_after, loc);
4068 542041 : }
4069 :
4070 : /* Clobber all scalar replacements in an access subtree. ACCESS is the
4071 : root of the subtree to be processed. GSI is the statement iterator used
4072 : for inserting statements which are added after the current statement if
4073 : INSERT_AFTER is true or before it otherwise. */
4074 :
4075 : static void
4076 2869168 : clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
4077 : bool insert_after, location_t loc)
4078 :
4079 : {
4080 2869168 : struct access *child;
4081 :
4082 2869168 : if (access->grp_to_be_replaced)
4083 : {
4084 1827516 : tree rep = get_access_replacement (access);
4085 1827516 : tree clobber = build_clobber (access->type);
4086 1827516 : gimple *stmt = gimple_build_assign (rep, clobber);
4087 :
4088 1827516 : if (insert_after)
4089 368260 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4090 : else
4091 1459256 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4092 1827516 : update_stmt (stmt);
4093 1827516 : gimple_set_location (stmt, loc);
4094 : }
4095 :
4096 4726176 : for (child = access->first_child; child; child = child->next_sibling)
4097 1857008 : clobber_subtree (child, gsi, insert_after, loc);
4098 2869168 : }
4099 :
4100 : /* Search for an access representative for the given expression EXPR and
4101 : return it or NULL if it cannot be found. */
4102 :
4103 : static struct access *
4104 46546440 : get_access_for_expr (tree expr)
4105 : {
4106 46546440 : poly_int64 poffset, psize, pmax_size;
4107 46546440 : HOST_WIDE_INT offset, max_size;
4108 46546440 : tree base;
4109 46546440 : bool reverse;
4110 :
4111 46546440 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
4112 : &reverse);
4113 46546440 : if (!known_size_p (pmax_size)
4114 46396945 : || !pmax_size.is_constant (&max_size)
4115 46396945 : || !poffset.is_constant (&offset)
4116 46546440 : || !DECL_P (base))
4117 : return NULL;
4118 :
4119 21781289 : if (tree basesize = DECL_SIZE (base))
4120 : {
4121 21737567 : poly_int64 sz;
4122 21737567 : if (offset < 0
4123 21737551 : || !poly_int_tree_p (basesize, &sz)
4124 43475118 : || known_le (sz, offset))
4125 7029 : return NULL;
4126 : }
4127 :
4128 21774260 : if (max_size == 0
4129 21774260 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
4130 12579851 : return NULL;
4131 :
4132 9194409 : return get_var_base_offset_size_access (base, offset, max_size);
4133 : }
4134 :
4135 : /* Replace the expression EXPR with a scalar replacement if there is one and
4136 : generate other statements to do type conversion or subtree copying if
4137 : necessary. WRITE is true if the expression is being written to (it is on a
4138 : LHS of a statement or output in an assembly statement). STMT_GSI is used to
4139 : place newly created statements before the processed statement, REFRESH_GSI
4140 : is used to place them afterwards - unless the processed statement must end a
4141 : BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
4142 : is then used to continue iteration over the BB. If sra_modify_expr is
4143 : called only once with WRITE equal to true on a given statement, both
4144 : iterator parameters can point to the same one. */
4145 :
4146 : static bool
4147 7518175 : sra_modify_expr (tree *expr, bool write, gimple_stmt_iterator *stmt_gsi,
4148 : gimple_stmt_iterator *refresh_gsi)
4149 : {
4150 7518175 : location_t loc;
4151 7518175 : struct access *access;
4152 7518175 : tree type, bfr, orig_expr;
4153 7518175 : bool partial_cplx_access = false;
4154 :
4155 7518175 : if (TREE_CODE (*expr) == BIT_FIELD_REF
4156 7518175 : && (write || !sra_handled_bf_read_p (*expr)))
4157 : {
4158 586 : bfr = *expr;
4159 586 : expr = &TREE_OPERAND (*expr, 0);
4160 : }
4161 : else
4162 : bfr = NULL_TREE;
4163 :
4164 7518175 : if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
4165 : {
4166 24994 : expr = &TREE_OPERAND (*expr, 0);
4167 24994 : partial_cplx_access = true;
4168 : }
4169 7518175 : access = get_access_for_expr (*expr);
4170 7518175 : if (!access)
4171 : return false;
4172 198012 : type = TREE_TYPE (*expr);
4173 198012 : orig_expr = *expr;
4174 :
4175 198012 : loc = gimple_location (gsi_stmt (*stmt_gsi));
4176 198012 : gimple_stmt_iterator alt_gsi = gsi_none ();
4177 198012 : if (write && stmt_ends_bb_p (gsi_stmt (*stmt_gsi)))
4178 : {
4179 39646 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi)));
4180 39646 : refresh_gsi = &alt_gsi;
4181 : }
4182 :
4183 198012 : if (access->grp_to_be_replaced)
4184 : {
4185 48114 : tree repl = get_access_replacement (access);
4186 : /* If we replace a non-register typed access simply use the original
4187 : access expression to extract the scalar component afterwards.
4188 : This happens if scalarizing a function return value or parameter
4189 : like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
4190 : gcc.c-torture/compile/20011217-1.c.
4191 :
4192 : We also want to use this when accessing a complex or vector which can
4193 : be accessed as a different type too, potentially creating a need for
4194 : type conversion (see PR42196) and when scalarized unions are involved
4195 : in assembler statements (see PR42398). */
4196 48114 : if (!bfr && !useless_type_conversion_p (type, access->type))
4197 : {
4198 44678 : tree ref;
4199 :
4200 44678 : ref = build_ref_for_model (loc, orig_expr, 0, access, stmt_gsi,
4201 : false);
4202 :
4203 44678 : if (partial_cplx_access)
4204 : {
4205 : /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4206 : the case of a write because in such case the replacement cannot
4207 : be a gimple register. In the case of a load, we have to
4208 : differentiate in between a register an non-register
4209 : replacement. */
4210 29 : tree t = build1 (VIEW_CONVERT_EXPR, type, repl);
4211 29 : gcc_checking_assert (!write || access->grp_partial_lhs);
4212 29 : if (!access->grp_partial_lhs)
4213 : {
4214 26 : tree tmp = make_ssa_name (type);
4215 26 : gassign *stmt = gimple_build_assign (tmp, t);
4216 : /* This is always a read. */
4217 26 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4218 26 : t = tmp;
4219 : }
4220 29 : *expr = t;
4221 : }
4222 44649 : else if (write)
4223 : {
4224 10706 : gassign *stmt;
4225 :
4226 10706 : if (access->grp_partial_lhs)
4227 6 : ref = force_gimple_operand_gsi (refresh_gsi, ref, true,
4228 : NULL_TREE, false, GSI_NEW_STMT);
4229 10706 : stmt = gimple_build_assign (repl, ref);
4230 10706 : gimple_set_location (stmt, loc);
4231 10706 : gsi_insert_after (refresh_gsi, stmt, GSI_NEW_STMT);
4232 : }
4233 : else
4234 : {
4235 33943 : if (TREE_READONLY (access->base))
4236 : return false;
4237 :
4238 33924 : gassign *stmt;
4239 33924 : if (access->grp_partial_lhs)
4240 15 : repl = force_gimple_operand_gsi (stmt_gsi, repl, true,
4241 : NULL_TREE, true,
4242 : GSI_SAME_STMT);
4243 33924 : stmt = gimple_build_assign (ref, repl);
4244 33924 : gimple_set_location (stmt, loc);
4245 33924 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4246 : }
4247 : }
4248 : else
4249 : {
4250 : /* If we are going to replace a scalar field in a structure with
4251 : reverse storage order by a stand-alone scalar, we are going to
4252 : effectively byte-swap the scalar and we also need to byte-swap
4253 : the portion of it represented by the bit-field. */
4254 3436 : if (bfr && REF_REVERSE_STORAGE_ORDER (bfr))
4255 : {
4256 0 : REF_REVERSE_STORAGE_ORDER (bfr) = 0;
4257 0 : TREE_OPERAND (bfr, 2)
4258 0 : = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (repl)),
4259 : size_binop (PLUS_EXPR, TREE_OPERAND (bfr, 1),
4260 : TREE_OPERAND (bfr, 2)));
4261 : }
4262 :
4263 3436 : *expr = repl;
4264 : }
4265 :
4266 48095 : sra_stats.exprs++;
4267 : }
4268 149898 : else if (write && access->grp_to_be_debug_replaced)
4269 : {
4270 12 : gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
4271 : NULL_TREE,
4272 : gsi_stmt (*stmt_gsi));
4273 12 : gsi_insert_after (stmt_gsi, ds, GSI_NEW_STMT);
4274 : }
4275 :
4276 197993 : if (access->first_child && !TREE_READONLY (access->base))
4277 : {
4278 146268 : HOST_WIDE_INT start_offset, chunk_size;
4279 146268 : if (bfr
4280 0 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
4281 146268 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
4282 : {
4283 0 : chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
4284 0 : start_offset = access->offset
4285 0 : + tree_to_uhwi (TREE_OPERAND (bfr, 2));
4286 : }
4287 : else
4288 : start_offset = chunk_size = 0;
4289 :
4290 242207 : generate_subtree_copies (access->first_child, orig_expr, access->offset,
4291 : start_offset, chunk_size,
4292 : write ? refresh_gsi : stmt_gsi,
4293 : write, write, loc);
4294 : }
4295 : return true;
4296 : }
4297 :
4298 : /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4299 : reads from its base before and after the call statement given in CALL_GSI
4300 : and return true if any copying took place. Otherwise call sra_modify_expr
4301 : on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4302 : return for the given parameter. */
4303 :
4304 : static bool
4305 8255984 : sra_modify_call_arg (tree *expr, gimple_stmt_iterator *call_gsi,
4306 : gimple_stmt_iterator *refresh_gsi, int flags)
4307 : {
4308 8255984 : if (TREE_CODE (*expr) != ADDR_EXPR)
4309 5448324 : return sra_modify_expr (expr, false, call_gsi, refresh_gsi);
4310 :
4311 2807660 : if (flags & EAF_UNUSED)
4312 : return false;
4313 :
4314 2804098 : tree base = get_base_address (TREE_OPERAND (*expr, 0));
4315 2804098 : if (!DECL_P (base))
4316 : return false;
4317 2123264 : struct access *access = get_access_for_expr (base);
4318 2123264 : if (!access)
4319 : return false;
4320 :
4321 49996 : gimple *stmt = gsi_stmt (*call_gsi);
4322 49996 : location_t loc = gimple_location (stmt);
4323 49996 : generate_subtree_copies (access, base, 0, 0, 0, call_gsi, false, false,
4324 : loc, true);
4325 :
4326 49996 : if (flags & EAF_NO_DIRECT_CLOBBER)
4327 : return true;
4328 :
4329 35319 : if (!stmt_ends_bb_p (stmt))
4330 24968 : generate_subtree_copies (access, base, 0, 0, 0, refresh_gsi, true,
4331 : true, loc, true);
4332 : else
4333 : {
4334 10351 : edge e;
4335 10351 : edge_iterator ei;
4336 31030 : FOR_EACH_EDGE (e, ei, gsi_bb (*call_gsi)->succs)
4337 : {
4338 20679 : gimple_stmt_iterator alt_gsi = gsi_start_edge (e);
4339 20679 : generate_subtree_copies (access, base, 0, 0, 0, &alt_gsi, true,
4340 : true, loc, true);
4341 : }
4342 : }
4343 : return true;
4344 : }
4345 :
4346 : /* Where scalar replacements of the RHS have been written to when a replacement
4347 : of a LHS of an assigments cannot be direclty loaded from a replacement of
4348 : the RHS. */
4349 : enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
4350 : SRA_UDH_RIGHT, /* Data flushed to the RHS. */
4351 : SRA_UDH_LEFT }; /* Data flushed to the LHS. */
4352 :
4353 : struct subreplacement_assignment_data
4354 : {
4355 : /* Offset of the access representing the lhs of the assignment. */
4356 : HOST_WIDE_INT left_offset;
4357 :
4358 : /* LHS and RHS of the original assignment. */
4359 : tree assignment_lhs, assignment_rhs;
4360 :
4361 : /* Access representing the rhs of the whole assignment. */
4362 : struct access *top_racc;
4363 :
4364 : /* Stmt iterator used for statement insertions after the original assignment.
4365 : It points to the main GSI used to traverse a BB during function body
4366 : modification. */
4367 : gimple_stmt_iterator *new_gsi;
4368 :
4369 : /* Stmt iterator used for statement insertions before the original
4370 : assignment. Keeps on pointing to the original statement. */
4371 : gimple_stmt_iterator old_gsi;
4372 :
4373 : /* Location of the assignment. */
4374 : location_t loc;
4375 :
4376 : /* Keeps the information whether we have needed to refresh replacements of
4377 : the LHS and from which side of the assignments this takes place. */
4378 : enum unscalarized_data_handling refreshed;
4379 : };
4380 :
4381 : /* Store all replacements in the access tree rooted in TOP_RACC either to their
4382 : base aggregate if there are unscalarized data or directly to LHS of the
4383 : statement that is pointed to by GSI otherwise. */
4384 :
4385 : static void
4386 108656 : handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
4387 : {
4388 108656 : tree src;
4389 : /* If the RHS is a load from a constant, we do not need to (and must not)
4390 : flush replacements to it and can use it directly as if we did. */
4391 108656 : if (TREE_READONLY (sad->top_racc->base))
4392 : {
4393 7 : sad->refreshed = SRA_UDH_RIGHT;
4394 7 : return;
4395 : }
4396 108649 : if (sad->top_racc->grp_unscalarized_data)
4397 : {
4398 25545 : src = sad->assignment_rhs;
4399 25545 : sad->refreshed = SRA_UDH_RIGHT;
4400 : }
4401 : else
4402 : {
4403 83104 : src = sad->assignment_lhs;
4404 83104 : sad->refreshed = SRA_UDH_LEFT;
4405 : }
4406 108649 : generate_subtree_copies (sad->top_racc->first_child, src,
4407 : sad->top_racc->offset, 0, 0,
4408 : &sad->old_gsi, false, false, sad->loc);
4409 : }
4410 :
4411 : /* Try to generate statements to load all sub-replacements in an access subtree
4412 : formed by children of LACC from scalar replacements in the SAD->top_racc
4413 : subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4414 : and load the accesses from it. */
4415 :
4416 : static void
4417 494189 : load_assign_lhs_subreplacements (struct access *lacc,
4418 : struct subreplacement_assignment_data *sad)
4419 : {
4420 1625980 : for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
4421 : {
4422 1131791 : HOST_WIDE_INT offset;
4423 1131791 : offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
4424 :
4425 1131791 : if (lacc->grp_to_be_replaced)
4426 : {
4427 943205 : struct access *racc;
4428 943205 : gassign *stmt;
4429 943205 : tree rhs;
4430 :
4431 943205 : racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
4432 943205 : if (racc && racc->grp_to_be_replaced)
4433 : {
4434 917481 : rhs = get_access_replacement (racc);
4435 917481 : bool vce = false;
4436 917481 : if (!useless_type_conversion_p (lacc->type, racc->type))
4437 : {
4438 31 : rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4439 : lacc->type, rhs);
4440 31 : vce = true;
4441 : }
4442 :
4443 917481 : if (lacc->grp_partial_lhs && (vce || racc->grp_partial_lhs))
4444 3 : rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
4445 : NULL_TREE, true, GSI_SAME_STMT);
4446 : }
4447 : else
4448 : {
4449 : /* No suitable access on the right hand side, need to load from
4450 : the aggregate. See if we have to update it first... */
4451 25724 : if (sad->refreshed == SRA_UDH_NONE)
4452 12874 : handle_unscalarized_data_in_subtree (sad);
4453 :
4454 25724 : if (sad->refreshed == SRA_UDH_LEFT)
4455 498 : rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
4456 498 : lacc->offset - sad->left_offset,
4457 : lacc, sad->new_gsi, true);
4458 : else
4459 25226 : rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
4460 25226 : lacc->offset - sad->left_offset,
4461 : lacc, sad->new_gsi, true);
4462 25724 : if (lacc->grp_partial_lhs)
4463 1 : rhs = force_gimple_operand_gsi (sad->new_gsi,
4464 : rhs, true, NULL_TREE,
4465 : false, GSI_NEW_STMT);
4466 : }
4467 :
4468 943205 : stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
4469 943205 : gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
4470 943205 : gimple_set_location (stmt, sad->loc);
4471 943205 : update_stmt (stmt);
4472 943205 : sra_stats.subreplacements++;
4473 : }
4474 : else
4475 : {
4476 188586 : if (sad->refreshed == SRA_UDH_NONE
4477 27264 : && lacc->grp_read && !lacc->grp_covered)
4478 24 : handle_unscalarized_data_in_subtree (sad);
4479 :
4480 188586 : if (lacc && lacc->grp_to_be_debug_replaced)
4481 : {
4482 107362 : gdebug *ds;
4483 107362 : tree drhs;
4484 107362 : struct access *racc = find_access_in_subtree (sad->top_racc,
4485 : offset,
4486 : lacc->size);
4487 :
4488 107362 : if (racc && racc->grp_to_be_replaced)
4489 : {
4490 107217 : if (racc->grp_write || constant_decl_p (racc->base))
4491 104097 : drhs = get_access_replacement (racc);
4492 : else
4493 : drhs = NULL;
4494 : }
4495 145 : else if (sad->refreshed == SRA_UDH_LEFT)
4496 0 : drhs = build_debug_ref_for_model (sad->loc, lacc->base,
4497 : lacc->offset, lacc);
4498 145 : else if (sad->refreshed == SRA_UDH_RIGHT)
4499 143 : drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
4500 : offset, lacc);
4501 : else
4502 : drhs = NULL_TREE;
4503 104097 : if (drhs
4504 104240 : && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
4505 1941 : drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4506 : lacc->type, drhs);
4507 107362 : ds = gimple_build_debug_bind (get_access_replacement (lacc),
4508 : drhs, gsi_stmt (sad->old_gsi));
4509 107362 : gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
4510 : }
4511 : }
4512 :
4513 1131791 : if (lacc->first_child)
4514 36537 : load_assign_lhs_subreplacements (lacc, sad);
4515 : }
4516 494189 : }
4517 :
4518 : /* Result code for SRA assignment modification. */
4519 : enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
4520 : SRA_AM_MODIFIED, /* stmt changed but not
4521 : removed */
4522 : SRA_AM_REMOVED }; /* stmt eliminated */
4523 :
4524 : /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4525 : to the assignment and GSI is the statement iterator pointing at it. Returns
4526 : the same values as sra_modify_assign. */
4527 :
4528 : static enum assignment_mod_result
4529 2841178 : sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4530 : {
4531 2841178 : tree lhs = gimple_assign_lhs (stmt);
4532 2841178 : struct access *acc = get_access_for_expr (lhs);
4533 2841178 : if (!acc)
4534 : return SRA_AM_NONE;
4535 1158918 : location_t loc = gimple_location (stmt);
4536 :
4537 1158918 : if (gimple_clobber_p (stmt))
4538 : {
4539 : /* Clobber the replacement variable. */
4540 1012160 : clobber_subtree (acc, gsi, !acc->grp_covered, loc);
4541 : /* Remove clobbers of fully scalarized variables, they are dead. */
4542 1012160 : if (acc->grp_covered)
4543 : {
4544 769841 : unlink_stmt_vdef (stmt);
4545 769841 : gsi_remove (gsi, true);
4546 769841 : release_defs (stmt);
4547 769841 : return SRA_AM_REMOVED;
4548 : }
4549 : else
4550 : return SRA_AM_MODIFIED;
4551 : }
4552 :
4553 146758 : if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
4554 : {
4555 : /* I have never seen this code path trigger but if it can happen the
4556 : following should handle it gracefully. */
4557 0 : if (access_has_children_p (acc))
4558 0 : generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
4559 : true, true, loc);
4560 0 : return SRA_AM_MODIFIED;
4561 : }
4562 :
4563 146758 : if (acc->grp_covered)
4564 : {
4565 80640 : init_subtree_with_zero (acc, gsi, false, loc);
4566 80640 : unlink_stmt_vdef (stmt);
4567 80640 : gsi_remove (gsi, true);
4568 80640 : release_defs (stmt);
4569 80640 : return SRA_AM_REMOVED;
4570 : }
4571 : else
4572 : {
4573 66118 : init_subtree_with_zero (acc, gsi, true, loc);
4574 66118 : return SRA_AM_MODIFIED;
4575 : }
4576 : }
4577 :
4578 : /* Create and return a new suitable default definition SSA_NAME for RACC which
4579 : is an access describing an uninitialized part of an aggregate that is being
4580 : loaded. REG_TREE is used instead of the actual RACC type if that is not of
4581 : a gimple register type. */
4582 :
4583 : static tree
4584 544 : get_repl_default_def_ssa_name (struct access *racc, tree reg_type)
4585 : {
4586 544 : gcc_checking_assert (!racc->grp_to_be_replaced
4587 : && !racc->grp_to_be_debug_replaced);
4588 544 : if (!racc->replacement_decl)
4589 544 : racc->replacement_decl = create_access_replacement (racc, reg_type);
4590 544 : return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
4591 : }
4592 :
4593 :
4594 : /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4595 : of accesses within a subtree ACCESS; all its children, siblings and their
4596 : children are to be processed.
4597 : GSI is a statement iterator used to place the new statements. */
4598 : static void
4599 26218 : generate_subtree_deferred_init (struct access *access,
4600 : tree init_type,
4601 : tree decl_name,
4602 : gimple_stmt_iterator *gsi,
4603 : location_t loc)
4604 : {
4605 58377 : do
4606 : {
4607 58377 : if (access->grp_to_be_replaced)
4608 : {
4609 46233 : tree repl = get_access_replacement (access);
4610 46233 : gimple *call
4611 46233 : = gimple_build_call_internal (IFN_DEFERRED_INIT, 3,
4612 46233 : TYPE_SIZE_UNIT (TREE_TYPE (repl)),
4613 : init_type, decl_name);
4614 46233 : gimple_call_set_lhs (call, repl);
4615 46233 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
4616 46233 : update_stmt (call);
4617 46233 : gimple_set_location (call, loc);
4618 46233 : sra_stats.subtree_deferred_init++;
4619 : }
4620 58377 : if (access->first_child)
4621 3710 : generate_subtree_deferred_init (access->first_child, init_type,
4622 : decl_name, gsi, loc);
4623 :
4624 58377 : access = access ->next_sibling;
4625 : }
4626 58377 : while (access);
4627 26218 : }
4628 :
4629 : /* For a call to .DEFERRED_INIT:
4630 : var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4631 : examine the LHS variable VAR and replace it with a scalar replacement if
4632 : there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4633 : the corresponding scalar relacement variable. Examine the subtree and
4634 : do the scalar replacements in the subtree too. STMT is the call, GSI is
4635 : the statement iterator to place newly created statement. */
4636 :
4637 : static enum assignment_mod_result
4638 86909 : sra_modify_deferred_init (gimple *stmt, gimple_stmt_iterator *gsi)
4639 : {
4640 86909 : tree lhs = gimple_call_lhs (stmt);
4641 86909 : tree init_type = gimple_call_arg (stmt, 1);
4642 86909 : tree decl_name = gimple_call_arg (stmt, 2);
4643 :
4644 86909 : struct access *lhs_access = get_access_for_expr (lhs);
4645 86909 : if (!lhs_access)
4646 : return SRA_AM_NONE;
4647 :
4648 32493 : location_t loc = gimple_location (stmt);
4649 :
4650 32493 : if (lhs_access->grp_to_be_replaced)
4651 : {
4652 9630 : tree lhs_repl = get_access_replacement (lhs_access);
4653 9630 : gimple_call_set_lhs (stmt, lhs_repl);
4654 9630 : tree arg0_repl = TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl));
4655 9630 : gimple_call_set_arg (stmt, 0, arg0_repl);
4656 9630 : sra_stats.deferred_init++;
4657 9630 : gcc_assert (!lhs_access->first_child);
4658 : return SRA_AM_MODIFIED;
4659 : }
4660 :
4661 22863 : if (lhs_access->first_child)
4662 22508 : generate_subtree_deferred_init (lhs_access->first_child,
4663 : init_type, decl_name, gsi, loc);
4664 22863 : if (lhs_access->grp_covered)
4665 : {
4666 14573 : unlink_stmt_vdef (stmt);
4667 14573 : gsi_remove (gsi, true);
4668 14573 : release_defs (stmt);
4669 14573 : return SRA_AM_REMOVED;
4670 : }
4671 :
4672 : return SRA_AM_MODIFIED;
4673 : }
4674 :
4675 : /* Examine both sides of the assignment statement pointed to by STMT, replace
4676 : them with a scalare replacement if there is one and generate copying of
4677 : replacements if scalarized aggregates have been used in the assignment. GSI
4678 : is used to hold generated statements for type conversions and subtree
4679 : copying. */
4680 :
4681 : static enum assignment_mod_result
4682 25394827 : sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4683 : {
4684 25394827 : struct access *lacc, *racc;
4685 25394827 : tree lhs, rhs;
4686 25394827 : bool modify_this_stmt = false;
4687 25394827 : bool force_gimple_rhs = false;
4688 25394827 : location_t loc;
4689 25394827 : gimple_stmt_iterator orig_gsi = *gsi;
4690 :
4691 25394827 : if (!gimple_assign_single_p (stmt))
4692 : return SRA_AM_NONE;
4693 19855215 : lhs = gimple_assign_lhs (stmt);
4694 19855215 : rhs = gimple_assign_rhs1 (stmt);
4695 :
4696 19855215 : if (TREE_CODE (rhs) == CONSTRUCTOR)
4697 2841178 : return sra_modify_constructor_assign (stmt, gsi);
4698 :
4699 17005087 : if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
4700 17001891 : || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
4701 16989043 : || (TREE_CODE (rhs) == BIT_FIELD_REF && !sra_handled_bf_read_p (rhs))
4702 34003076 : || TREE_CODE (lhs) == BIT_FIELD_REF)
4703 : {
4704 25580 : modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
4705 : false, gsi, gsi);
4706 25580 : modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
4707 : true, gsi, gsi);
4708 47804 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4709 : }
4710 :
4711 16988457 : lacc = get_access_for_expr (lhs);
4712 16988457 : racc = get_access_for_expr (rhs);
4713 16988457 : if (!lacc && !racc)
4714 : return SRA_AM_NONE;
4715 : /* Avoid modifying initializations of constant-pool replacements. */
4716 6988148 : if (racc && (racc->replacement_decl == lhs))
4717 : return SRA_AM_NONE;
4718 :
4719 6983167 : loc = gimple_location (stmt);
4720 6983167 : if (lacc && lacc->grp_to_be_replaced)
4721 : {
4722 1909432 : lhs = get_access_replacement (lacc);
4723 1909432 : gimple_assign_set_lhs (stmt, lhs);
4724 1909432 : modify_this_stmt = true;
4725 1909432 : if (lacc->grp_partial_lhs)
4726 85 : force_gimple_rhs = true;
4727 1909432 : sra_stats.exprs++;
4728 : }
4729 :
4730 6983167 : if (racc && racc->grp_to_be_replaced)
4731 : {
4732 3179471 : rhs = get_access_replacement (racc);
4733 3179471 : modify_this_stmt = true;
4734 3179471 : if (racc->grp_partial_lhs)
4735 557 : force_gimple_rhs = true;
4736 3179471 : sra_stats.exprs++;
4737 : }
4738 1099954 : else if (racc
4739 1099954 : && !racc->grp_unscalarized_data
4740 876209 : && !racc->grp_unscalarizable_region
4741 876207 : && TREE_CODE (lhs) == SSA_NAME
4742 544 : && !access_has_replacements_p (racc))
4743 : {
4744 544 : rhs = get_repl_default_def_ssa_name (racc, TREE_TYPE (lhs));
4745 544 : modify_this_stmt = true;
4746 544 : sra_stats.exprs++;
4747 : }
4748 :
4749 3180015 : if (modify_this_stmt
4750 6983167 : && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4751 : {
4752 : /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4753 : ??? This should move to fold_stmt which we simply should
4754 : call after building a VIEW_CONVERT_EXPR here. */
4755 535298 : if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
4756 149251 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs)) == racc->reverse
4757 417405 : && !contains_bitfld_component_ref_p (lhs))
4758 : {
4759 149250 : lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
4760 149250 : gimple_assign_set_lhs (stmt, lhs);
4761 : }
4762 118905 : else if (lacc
4763 91169 : && AGGREGATE_TYPE_P (TREE_TYPE (rhs))
4764 65272 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs)) == lacc->reverse
4765 184177 : && !contains_vce_or_bfcref_p (rhs))
4766 64802 : rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
4767 :
4768 268155 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4769 : {
4770 54103 : rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
4771 54103 : if (is_gimple_reg_type (TREE_TYPE (lhs))
4772 54103 : && TREE_CODE (lhs) != SSA_NAME)
4773 6983167 : force_gimple_rhs = true;
4774 : }
4775 : }
4776 :
4777 6983167 : if (lacc && lacc->grp_to_be_debug_replaced)
4778 : {
4779 142876 : tree dlhs = get_access_replacement (lacc);
4780 142876 : tree drhs = unshare_expr (rhs);
4781 142876 : if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
4782 : {
4783 3412 : if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
4784 1767 : && !contains_vce_or_bfcref_p (drhs))
4785 61 : drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
4786 1706 : if (drhs
4787 3412 : && !useless_type_conversion_p (TREE_TYPE (dlhs),
4788 1706 : TREE_TYPE (drhs)))
4789 1645 : drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
4790 1645 : TREE_TYPE (dlhs), drhs);
4791 : }
4792 142876 : gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
4793 142876 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4794 : }
4795 :
4796 : /* From this point on, the function deals with assignments in between
4797 : aggregates when at least one has scalar reductions of some of its
4798 : components. There are three possible scenarios: Both the LHS and RHS have
4799 : to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4800 :
4801 : In the first case, we would like to load the LHS components from RHS
4802 : components whenever possible. If that is not possible, we would like to
4803 : read it directly from the RHS (after updating it by storing in it its own
4804 : components). If there are some necessary unscalarized data in the LHS,
4805 : those will be loaded by the original assignment too. If neither of these
4806 : cases happen, the original statement can be removed. Most of this is done
4807 : by load_assign_lhs_subreplacements.
4808 :
4809 : In the second case, we would like to store all RHS scalarized components
4810 : directly into LHS and if they cover the aggregate completely, remove the
4811 : statement too. In the third case, we want the LHS components to be loaded
4812 : directly from the RHS (DSE will remove the original statement if it
4813 : becomes redundant).
4814 :
4815 : This is a bit complex but manageable when types match and when unions do
4816 : not cause confusion in a way that we cannot really load a component of LHS
4817 : from the RHS or vice versa (the access representing this level can have
4818 : subaccesses that are accessible only through a different union field at a
4819 : higher level - different from the one used in the examined expression).
4820 : Unions are fun.
4821 :
4822 : Therefore, I specially handle a fourth case, happening when there is a
4823 : specific type cast or it is impossible to locate a scalarized subaccess on
4824 : the other side of the expression. If that happens, I simply "refresh" the
4825 : RHS by storing in it is scalarized components leave the original statement
4826 : there to do the copying and then load the scalar replacements of the LHS.
4827 : This is what the first branch does. */
4828 :
4829 6983167 : if (modify_this_stmt
4830 2019130 : || gimple_has_volatile_ops (stmt)
4831 2018750 : || contains_vce_or_bfcref_p (rhs)
4832 1838241 : || contains_vce_or_bfcref_p (lhs)
4833 8818210 : || stmt_ends_bb_p (stmt))
4834 : {
4835 : /* No need to copy into a constant, it comes pre-initialized. */
4836 5241554 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4837 17492 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4838 : gsi, false, false, loc);
4839 5224062 : if (access_has_children_p (lacc))
4840 : {
4841 252209 : gimple_stmt_iterator alt_gsi = gsi_none ();
4842 252209 : if (stmt_ends_bb_p (stmt))
4843 : {
4844 75071 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
4845 75071 : gsi = &alt_gsi;
4846 : }
4847 252209 : generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
4848 : gsi, true, true, loc);
4849 : }
4850 5224062 : sra_stats.separate_lhs_rhs_handling++;
4851 :
4852 : /* This gimplification must be done after generate_subtree_copies,
4853 : lest we insert the subtree copies in the middle of the gimplified
4854 : sequence. */
4855 5224062 : if (force_gimple_rhs)
4856 26992 : rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
4857 : true, GSI_SAME_STMT);
4858 5224062 : if (gimple_assign_rhs1 (stmt) != rhs)
4859 : {
4860 3271077 : modify_this_stmt = true;
4861 3271077 : gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
4862 3271077 : gcc_assert (stmt == gsi_stmt (orig_gsi));
4863 : }
4864 :
4865 6917022 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4866 : }
4867 : else
4868 : {
4869 2456452 : if (access_has_children_p (lacc)
4870 1759116 : && access_has_children_p (racc)
4871 : /* When an access represents an unscalarizable region, it usually
4872 : represents accesses with variable offset and thus must not be used
4873 : to generate new memory accesses. */
4874 457663 : && !lacc->grp_unscalarizable_region
4875 457658 : && !racc->grp_unscalarizable_region)
4876 : {
4877 457652 : struct subreplacement_assignment_data sad;
4878 :
4879 457652 : sad.left_offset = lacc->offset;
4880 457652 : sad.assignment_lhs = lhs;
4881 457652 : sad.assignment_rhs = rhs;
4882 457652 : sad.top_racc = racc;
4883 457652 : sad.old_gsi = *gsi;
4884 457652 : sad.new_gsi = gsi;
4885 457652 : sad.loc = gimple_location (stmt);
4886 457652 : sad.refreshed = SRA_UDH_NONE;
4887 :
4888 457652 : if (lacc->grp_read && !lacc->grp_covered)
4889 95758 : handle_unscalarized_data_in_subtree (&sad);
4890 :
4891 457652 : load_assign_lhs_subreplacements (lacc, &sad);
4892 457652 : if (sad.refreshed != SRA_UDH_RIGHT)
4893 : {
4894 432100 : gsi_next (gsi);
4895 432100 : unlink_stmt_vdef (stmt);
4896 432100 : gsi_remove (&sad.old_gsi, true);
4897 432100 : release_defs (stmt);
4898 432100 : sra_stats.deleted++;
4899 432100 : return SRA_AM_REMOVED;
4900 : }
4901 : }
4902 : else
4903 : {
4904 1301453 : if (access_has_children_p (racc)
4905 490290 : && !racc->grp_unscalarized_data
4906 430238 : && TREE_CODE (lhs) != SSA_NAME)
4907 : {
4908 430237 : if (dump_file)
4909 : {
4910 5 : fprintf (dump_file, "Removing load: ");
4911 5 : print_gimple_stmt (dump_file, stmt, 0);
4912 : }
4913 430237 : generate_subtree_copies (racc->first_child, lhs,
4914 : racc->offset, 0, 0, gsi,
4915 : false, false, loc);
4916 430237 : gcc_assert (stmt == gsi_stmt (*gsi));
4917 430237 : unlink_stmt_vdef (stmt);
4918 430237 : gsi_remove (gsi, true);
4919 430237 : release_defs (stmt);
4920 430237 : sra_stats.deleted++;
4921 430237 : return SRA_AM_REMOVED;
4922 : }
4923 : /* Restore the aggregate RHS from its components so the
4924 : prevailing aggregate copy does the right thing. */
4925 931269 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4926 60038 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4927 : gsi, false, false, loc);
4928 : /* Re-load the components of the aggregate copy destination.
4929 : But use the RHS aggregate to load from to expose more
4930 : optimization opportunities. */
4931 871216 : if (access_has_children_p (lacc))
4932 : {
4933 239690 : generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
4934 : 0, 0, gsi, true, true, loc);
4935 239690 : if (lacc->grp_covered)
4936 : {
4937 177054 : unlink_stmt_vdef (stmt);
4938 177054 : gsi_remove (& orig_gsi, true);
4939 177054 : release_defs (stmt);
4940 177054 : sra_stats.deleted++;
4941 177054 : return SRA_AM_REMOVED;
4942 : }
4943 : }
4944 : }
4945 :
4946 719714 : return SRA_AM_NONE;
4947 : }
4948 : }
4949 :
4950 : /* Set any scalar replacements of values in the constant pool to the initial
4951 : value of the constant. (Constant-pool decls like *.LC0 have effectively
4952 : been initialized before the program starts, we must do the same for their
4953 : replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4954 : the function's entry block. */
4955 :
4956 : static void
4957 432236 : initialize_constant_pool_replacements (void)
4958 : {
4959 432236 : gimple_seq seq = NULL;
4960 432236 : gimple_stmt_iterator gsi = gsi_start (seq);
4961 432236 : bitmap_iterator bi;
4962 432236 : unsigned i;
4963 :
4964 2202835 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
4965 : {
4966 1770599 : tree var = candidate (i);
4967 1770599 : if (!constant_decl_p (var))
4968 1770518 : continue;
4969 :
4970 81 : struct access *access = get_first_repr_for_decl (var);
4971 :
4972 6386 : while (access)
4973 : {
4974 6224 : if (access->replacement_decl)
4975 : {
4976 4981 : gassign *stmt
4977 4981 : = gimple_build_assign (get_access_replacement (access),
4978 : unshare_expr (access->expr));
4979 4981 : if (dump_file && (dump_flags & TDF_DETAILS))
4980 : {
4981 0 : fprintf (dump_file, "Generating constant initializer: ");
4982 0 : print_gimple_stmt (dump_file, stmt, 0);
4983 0 : fprintf (dump_file, "\n");
4984 : }
4985 4981 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
4986 4981 : update_stmt (stmt);
4987 : }
4988 :
4989 6224 : if (access->first_child)
4990 : access = access->first_child;
4991 4981 : else if (access->next_sibling)
4992 : access = access->next_sibling;
4993 : else
4994 : {
4995 2351 : while (access->parent && !access->next_sibling)
4996 : access = access->parent;
4997 1108 : if (access->next_sibling)
4998 : access = access->next_sibling;
4999 : else
5000 81 : access = access->next_grp;
5001 : }
5002 : }
5003 : }
5004 :
5005 432236 : seq = gsi_seq (gsi);
5006 432236 : if (seq)
5007 76 : gsi_insert_seq_on_edge_immediate (
5008 76 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5009 432236 : }
5010 :
5011 : /* Traverse the function body and all modifications as decided in
5012 : analyze_all_variable_accesses. Return true iff the CFG has been
5013 : changed. */
5014 :
5015 : static bool
5016 432236 : sra_modify_function_body (void)
5017 : {
5018 432236 : bool cfg_changed = false;
5019 432236 : basic_block bb;
5020 :
5021 432236 : initialize_constant_pool_replacements ();
5022 :
5023 9844271 : FOR_EACH_BB_FN (bb, cfun)
5024 : {
5025 9412035 : gimple_stmt_iterator gsi = gsi_start_bb (bb);
5026 81101013 : while (!gsi_end_p (gsi))
5027 : {
5028 71688978 : gimple *stmt = gsi_stmt (gsi);
5029 71688978 : enum assignment_mod_result assign_result;
5030 71688978 : bool modified = false, deleted = false;
5031 71688978 : tree *t;
5032 71688978 : unsigned i;
5033 :
5034 71688978 : switch (gimple_code (stmt))
5035 : {
5036 430525 : case GIMPLE_RETURN:
5037 430525 : t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
5038 430525 : if (*t != NULL_TREE)
5039 280375 : modified |= sra_modify_expr (t, false, &gsi, &gsi);
5040 : break;
5041 :
5042 25394827 : case GIMPLE_ASSIGN:
5043 25394827 : assign_result = sra_modify_assign (stmt, &gsi);
5044 25394827 : modified |= assign_result == SRA_AM_MODIFIED;
5045 25394827 : deleted = assign_result == SRA_AM_REMOVED;
5046 25394827 : break;
5047 :
5048 4249319 : case GIMPLE_CALL:
5049 : /* Handle calls to .DEFERRED_INIT specially. */
5050 4249319 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
5051 : {
5052 86909 : assign_result = sra_modify_deferred_init (stmt, &gsi);
5053 86909 : modified |= assign_result == SRA_AM_MODIFIED;
5054 86909 : deleted = assign_result == SRA_AM_REMOVED;
5055 : }
5056 : else
5057 : {
5058 4162410 : gcall *call = as_a <gcall *> (stmt);
5059 4162410 : gimple_stmt_iterator call_gsi = gsi;
5060 :
5061 : /* Operands must be processed before the lhs. */
5062 12389098 : for (i = 0; i < gimple_call_num_args (call); i++)
5063 : {
5064 8226688 : int flags = gimple_call_arg_flags (call, i);
5065 8226688 : t = gimple_call_arg_ptr (call, i);
5066 8226688 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi, flags);
5067 : }
5068 4162410 : if (gimple_call_chain (call))
5069 : {
5070 29296 : t = gimple_call_chain_ptr (call);
5071 29296 : int flags = gimple_call_static_chain_flags (call);
5072 29296 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi,
5073 : flags);
5074 : }
5075 4162410 : if (gimple_call_lhs (call))
5076 : {
5077 1730818 : t = gimple_call_lhs_ptr (call);
5078 1730818 : modified |= sra_modify_expr (t, true, &call_gsi, &gsi);
5079 : }
5080 : }
5081 : break;
5082 :
5083 7231 : case GIMPLE_ASM:
5084 7231 : {
5085 7231 : gimple_stmt_iterator stmt_gsi = gsi;
5086 7231 : gasm *asm_stmt = as_a <gasm *> (stmt);
5087 18065 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5088 : {
5089 3603 : t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5090 3603 : modified |= sra_modify_expr (t, false, &stmt_gsi, &gsi);
5091 : }
5092 11126 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5093 : {
5094 3895 : t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5095 3895 : modified |= sra_modify_expr (t, true, &stmt_gsi, &gsi);
5096 : }
5097 : }
5098 7231 : break;
5099 :
5100 : default:
5101 : break;
5102 : }
5103 :
5104 29931752 : if (modified)
5105 : {
5106 5516651 : update_stmt (stmt);
5107 5516651 : if (maybe_clean_eh_stmt (stmt)
5108 5516651 : && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5109 : cfg_changed = true;
5110 : }
5111 71688978 : if (!deleted)
5112 69784533 : gsi_next (&gsi);
5113 : }
5114 : }
5115 :
5116 432236 : gsi_commit_edge_inserts ();
5117 432236 : return cfg_changed;
5118 : }
5119 :
5120 : /* Generate statements initializing scalar replacements of parts of function
5121 : parameters. */
5122 :
5123 : static void
5124 432236 : initialize_parameter_reductions (void)
5125 : {
5126 432236 : gimple_stmt_iterator gsi;
5127 432236 : gimple_seq seq = NULL;
5128 432236 : tree parm;
5129 :
5130 432236 : gsi = gsi_start (seq);
5131 432236 : for (parm = DECL_ARGUMENTS (current_function_decl);
5132 1298919 : parm;
5133 866683 : parm = DECL_CHAIN (parm))
5134 : {
5135 866683 : vec<access_p> *access_vec;
5136 866683 : struct access *access;
5137 :
5138 866683 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
5139 800193 : continue;
5140 66490 : access_vec = get_base_access_vector (parm);
5141 66490 : if (!access_vec)
5142 0 : continue;
5143 :
5144 66490 : for (access = (*access_vec)[0];
5145 170176 : access;
5146 103686 : access = access->next_grp)
5147 103686 : generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
5148 103686 : EXPR_LOCATION (parm));
5149 : }
5150 :
5151 432236 : seq = gsi_seq (gsi);
5152 432236 : if (seq)
5153 52623 : gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5154 432236 : }
5155 :
5156 : /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
5157 : it reveals there are components of some aggregates to be scalarized, it runs
5158 : the required transformations. */
5159 : static unsigned int
5160 3475668 : perform_intra_sra (void)
5161 : {
5162 3475668 : int ret = 0;
5163 3475668 : sra_initialize ();
5164 :
5165 3475668 : if (!find_var_candidates ())
5166 2693563 : goto out;
5167 :
5168 782105 : if (!scan_function ())
5169 51891 : goto out;
5170 :
5171 730214 : if (!analyze_all_variable_accesses ())
5172 297978 : goto out;
5173 :
5174 432236 : if (sra_modify_function_body ())
5175 : ret = TODO_update_ssa | TODO_cleanup_cfg;
5176 : else
5177 432214 : ret = TODO_update_ssa;
5178 432236 : initialize_parameter_reductions ();
5179 :
5180 432236 : statistics_counter_event (cfun, "Scalar replacements created",
5181 : sra_stats.replacements);
5182 432236 : statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
5183 432236 : statistics_counter_event (cfun, "Subtree copy stmts",
5184 : sra_stats.subtree_copies);
5185 432236 : statistics_counter_event (cfun, "Subreplacement stmts",
5186 : sra_stats.subreplacements);
5187 432236 : statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
5188 432236 : statistics_counter_event (cfun, "Separate LHS and RHS handling",
5189 : sra_stats.separate_lhs_rhs_handling);
5190 :
5191 3475668 : out:
5192 3475668 : sra_deinitialize ();
5193 3475668 : return ret;
5194 : }
5195 :
5196 : /* Perform early intraprocedural SRA. */
5197 : static unsigned int
5198 2431785 : early_intra_sra (void)
5199 : {
5200 2431785 : sra_mode = SRA_MODE_EARLY_INTRA;
5201 0 : return perform_intra_sra ();
5202 : }
5203 :
5204 : /* Perform "late" intraprocedural SRA. */
5205 : static unsigned int
5206 1043883 : late_intra_sra (void)
5207 : {
5208 1043883 : sra_mode = SRA_MODE_INTRA;
5209 0 : return perform_intra_sra ();
5210 : }
5211 :
5212 :
5213 : static bool
5214 3479629 : gate_intra_sra (void)
5215 : {
5216 3479629 : return flag_tree_sra != 0 && dbg_cnt (tree_sra);
5217 : }
5218 :
5219 :
5220 : namespace {
5221 :
5222 : const pass_data pass_data_sra_early =
5223 : {
5224 : GIMPLE_PASS, /* type */
5225 : "esra", /* name */
5226 : OPTGROUP_NONE, /* optinfo_flags */
5227 : TV_TREE_SRA, /* tv_id */
5228 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5229 : 0, /* properties_provided */
5230 : 0, /* properties_destroyed */
5231 : 0, /* todo_flags_start */
5232 : TODO_update_ssa, /* todo_flags_finish */
5233 : };
5234 :
5235 : class pass_sra_early : public gimple_opt_pass
5236 : {
5237 : public:
5238 288767 : pass_sra_early (gcc::context *ctxt)
5239 577534 : : gimple_opt_pass (pass_data_sra_early, ctxt)
5240 : {}
5241 :
5242 : /* opt_pass methods: */
5243 2435304 : bool gate (function *) final override { return gate_intra_sra (); }
5244 2431785 : unsigned int execute (function *) final override
5245 : {
5246 2431785 : return early_intra_sra ();
5247 : }
5248 :
5249 : }; // class pass_sra_early
5250 :
5251 : } // anon namespace
5252 :
5253 : gimple_opt_pass *
5254 288767 : make_pass_sra_early (gcc::context *ctxt)
5255 : {
5256 288767 : return new pass_sra_early (ctxt);
5257 : }
5258 :
5259 : namespace {
5260 :
5261 : const pass_data pass_data_sra =
5262 : {
5263 : GIMPLE_PASS, /* type */
5264 : "sra", /* name */
5265 : OPTGROUP_NONE, /* optinfo_flags */
5266 : TV_TREE_SRA, /* tv_id */
5267 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5268 : 0, /* properties_provided */
5269 : 0, /* properties_destroyed */
5270 : TODO_update_address_taken, /* todo_flags_start */
5271 : TODO_update_ssa, /* todo_flags_finish */
5272 : };
5273 :
5274 : class pass_sra : public gimple_opt_pass
5275 : {
5276 : public:
5277 288767 : pass_sra (gcc::context *ctxt)
5278 577534 : : gimple_opt_pass (pass_data_sra, ctxt)
5279 : {}
5280 :
5281 : /* opt_pass methods: */
5282 1044325 : bool gate (function *) final override { return gate_intra_sra (); }
5283 1043883 : unsigned int execute (function *) final override { return late_intra_sra (); }
5284 :
5285 : }; // class pass_sra
5286 :
5287 : } // anon namespace
5288 :
5289 : gimple_opt_pass *
5290 288767 : make_pass_sra (gcc::context *ctxt)
5291 : {
5292 288767 : return new pass_sra (ctxt);
5293 : }
5294 :
5295 :
5296 : /* If type T cannot be totally scalarized, return false. Otherwise return true
5297 : and push to the vector within PC offsets and lengths of all padding in the
5298 : type as total scalarization would encounter it. */
5299 :
5300 : static bool
5301 73391 : check_ts_and_push_padding_to_vec (tree type, sra_padding_collecting *pc)
5302 : {
5303 73391 : if (!totally_scalarizable_type_p (type, true /* optimistic value */,
5304 : 0, pc))
5305 : return false;
5306 :
5307 65494 : pc->record_padding (tree_to_shwi (TYPE_SIZE (type)));
5308 65494 : return true;
5309 : }
5310 :
5311 : /* Given two types in an assignment, return true either if any one cannot be
5312 : totally scalarized or if they have padding (i.e. not copied bits) */
5313 :
5314 : bool
5315 40644 : sra_total_scalarization_would_copy_same_data_p (tree t1, tree t2)
5316 : {
5317 40644 : sra_padding_collecting p1;
5318 40644 : if (!check_ts_and_push_padding_to_vec (t1, &p1))
5319 : return true;
5320 :
5321 32747 : sra_padding_collecting p2;
5322 32747 : if (!check_ts_and_push_padding_to_vec (t2, &p2))
5323 : return true;
5324 :
5325 32747 : unsigned l = p1.m_padding.length ();
5326 65494 : if (l != p2.m_padding.length ())
5327 : return false;
5328 39496 : for (unsigned i = 0; i < l; i++)
5329 6752 : if (p1.m_padding[i].first != p2.m_padding[i].first
5330 6752 : || p1.m_padding[i].second != p2.m_padding[i].second)
5331 : return false;
5332 :
5333 : return true;
5334 32747 : }
5335 :
|
