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 78321573 : uid_decl_hasher::hash (const tree_node *item)
307 : {
308 78321573 : return item->decl_minimal.uid;
309 : }
310 :
311 : /* Return true if the DECL_UID in both trees are equal. */
312 :
313 : inline bool
314 90215681 : uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
315 : {
316 90215681 : 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 14323237 : candidate (unsigned uid)
327 : {
328 14323237 : tree_node t;
329 14323237 : t.decl_minimal.uid = uid;
330 14323237 : 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 15871831 : access_has_children_p (struct access *acc)
474 : {
475 8459521 : 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 23117365 : 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 10202256 : find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
506 : HOST_WIDE_INT size)
507 : {
508 26026148 : while (access && (access->offset != offset || access->size != size))
509 : {
510 5621636 : struct access *child = access->first_child;
511 :
512 11481109 : while (child && (child->offset + child->size <= offset))
513 5859473 : 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 10202256 : if (access)
521 10241177 : while (access->first_child
522 3096407 : && access->first_child->offset == offset
523 13244541 : && access->first_child->size == size)
524 : access = access->first_child;
525 :
526 10202256 : return access;
527 : }
528 :
529 : /* Return the first group representative for DECL or NULL if none exists. */
530 :
531 : static struct access *
532 19026663 : get_first_repr_for_decl (tree base)
533 : {
534 19026663 : vec<access_p> *access_vec;
535 :
536 19026663 : access_vec = get_base_access_vector (base);
537 19026663 : if (!access_vec)
538 : return NULL;
539 :
540 19026663 : 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 9137837 : get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
549 : HOST_WIDE_INT size)
550 : {
551 9137837 : struct access *access;
552 :
553 9137837 : access = get_first_repr_for_decl (base);
554 21131516 : while (access && (access->offset + access->size <= offset))
555 2855842 : access = access->next_grp;
556 9137837 : if (!access)
557 : return NULL;
558 :
559 9137837 : 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 1310448 : add_link_to_rhs (struct access *racc, struct assign_link *link)
566 : {
567 1310448 : gcc_assert (link->racc == racc);
568 :
569 1310448 : if (!racc->first_rhs_link)
570 : {
571 1310448 : gcc_assert (!racc->last_rhs_link);
572 1310448 : racc->first_rhs_link = link;
573 : }
574 : else
575 0 : racc->last_rhs_link->next_rhs = link;
576 :
577 1310448 : racc->last_rhs_link = link;
578 1310448 : link->next_rhs = NULL;
579 1310448 : }
580 :
581 : /* Add LINK to the linked list of lhs assign links of LACC. */
582 :
583 : static void
584 1310448 : add_link_to_lhs (struct access *lacc, struct assign_link *link)
585 : {
586 1310448 : gcc_assert (link->lacc == lacc);
587 :
588 1310448 : if (!lacc->first_lhs_link)
589 : {
590 1310448 : gcc_assert (!lacc->last_lhs_link);
591 1310448 : lacc->first_lhs_link = link;
592 : }
593 : else
594 0 : lacc->last_lhs_link->next_lhs = link;
595 :
596 1310448 : lacc->last_lhs_link = link;
597 1310448 : link->next_lhs = NULL;
598 1310448 : }
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 5219501 : relink_to_new_repr (struct access *new_acc, struct access *old_acc)
604 : {
605 5219501 : if (old_acc->first_rhs_link)
606 : {
607 :
608 857650 : if (new_acc->first_rhs_link)
609 : {
610 281669 : gcc_assert (!new_acc->last_rhs_link->next_rhs);
611 281669 : gcc_assert (!old_acc->last_rhs_link
612 : || !old_acc->last_rhs_link->next_rhs);
613 :
614 281669 : new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link;
615 281669 : new_acc->last_rhs_link = old_acc->last_rhs_link;
616 : }
617 : else
618 : {
619 575981 : gcc_assert (!new_acc->last_rhs_link);
620 :
621 575981 : new_acc->first_rhs_link = old_acc->first_rhs_link;
622 575981 : new_acc->last_rhs_link = old_acc->last_rhs_link;
623 : }
624 857650 : old_acc->first_rhs_link = old_acc->last_rhs_link = NULL;
625 : }
626 : else
627 4361851 : gcc_assert (!old_acc->last_rhs_link);
628 :
629 5219501 : if (old_acc->first_lhs_link)
630 : {
631 :
632 357737 : if (new_acc->first_lhs_link)
633 : {
634 157356 : gcc_assert (!new_acc->last_lhs_link->next_lhs);
635 157356 : gcc_assert (!old_acc->last_lhs_link
636 : || !old_acc->last_lhs_link->next_lhs);
637 :
638 157356 : new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link;
639 157356 : new_acc->last_lhs_link = old_acc->last_lhs_link;
640 : }
641 : else
642 : {
643 200381 : gcc_assert (!new_acc->last_lhs_link);
644 :
645 200381 : new_acc->first_lhs_link = old_acc->first_lhs_link;
646 200381 : new_acc->last_lhs_link = old_acc->last_lhs_link;
647 : }
648 357737 : old_acc->first_lhs_link = old_acc->last_lhs_link = NULL;
649 : }
650 : else
651 4861764 : gcc_assert (!old_acc->last_lhs_link);
652 :
653 5219501 : }
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 4604018 : add_access_to_rhs_work_queue (struct access *access)
660 : {
661 4604018 : if (access->first_rhs_link && !access->grp_rhs_queued)
662 : {
663 1517888 : gcc_assert (!access->next_rhs_queued);
664 1517888 : access->next_rhs_queued = rhs_work_queue_head;
665 1517888 : access->grp_rhs_queued = 1;
666 1517888 : rhs_work_queue_head = access;
667 : }
668 4604018 : }
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 1662566 : add_access_to_lhs_work_queue (struct access *access)
675 : {
676 1662566 : if (access->first_lhs_link && !access->grp_lhs_queued)
677 : {
678 1312250 : gcc_assert (!access->next_lhs_queued);
679 1312250 : access->next_lhs_queued = lhs_work_queue_head;
680 1312250 : access->grp_lhs_queued = 1;
681 1312250 : lhs_work_queue_head = access;
682 : }
683 1662566 : }
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 1517888 : pop_access_from_rhs_work_queue (void)
690 : {
691 1517888 : struct access *access = rhs_work_queue_head;
692 :
693 1517888 : rhs_work_queue_head = access->next_rhs_queued;
694 1517888 : access->next_rhs_queued = NULL;
695 1517888 : access->grp_rhs_queued = 0;
696 1517888 : 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 1312250 : pop_access_from_lhs_work_queue (void)
704 : {
705 1312250 : struct access *access = lhs_work_queue_head;
706 :
707 1312250 : lhs_work_queue_head = access->next_lhs_queued;
708 1312250 : access->next_lhs_queued = NULL;
709 1312250 : access->grp_lhs_queued = 0;
710 1312250 : return access;
711 : }
712 :
713 : /* Allocate necessary structures. */
714 :
715 : static void
716 3437811 : sra_initialize (void)
717 : {
718 3437811 : candidate_bitmap = BITMAP_ALLOC (NULL);
719 6875622 : candidates = new hash_table<uid_decl_hasher>
720 6402533 : (vec_safe_length (cfun->local_decls) / 2);
721 3437811 : should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
722 3437811 : cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
723 3437811 : disqualified_constants = BITMAP_ALLOC (NULL);
724 3437811 : passed_by_ref_in_call = BITMAP_ALLOC (NULL);
725 3437811 : gcc_obstack_init (&name_obstack);
726 3437811 : base_access_vec = new hash_map<tree, auto_vec<access_p> >;
727 3437811 : memset (&sra_stats, 0, sizeof (sra_stats));
728 3437811 : }
729 :
730 : /* Deallocate all general structures. */
731 :
732 : static void
733 3437811 : sra_deinitialize (void)
734 : {
735 3437811 : BITMAP_FREE (candidate_bitmap);
736 3437811 : delete candidates;
737 3437811 : candidates = NULL;
738 3437811 : BITMAP_FREE (should_scalarize_away_bitmap);
739 3437811 : BITMAP_FREE (cannot_scalarize_away_bitmap);
740 3437811 : BITMAP_FREE (disqualified_constants);
741 3437811 : BITMAP_FREE (passed_by_ref_in_call);
742 3437811 : access_pool.release ();
743 3437811 : assign_link_pool.release ();
744 3437811 : obstack_free (&name_obstack, NULL);
745 :
746 6875622 : delete base_access_vec;
747 3437811 : }
748 :
749 : /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
750 :
751 41552900 : static bool constant_decl_p (tree decl)
752 : {
753 35977195 : 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 4392551 : disqualify_candidate (tree decl, const char *reason)
761 : {
762 4392551 : if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
763 2316538 : candidates->remove_elt_with_hash (decl, DECL_UID (decl));
764 4392551 : if (constant_decl_p (decl))
765 4107 : bitmap_set_bit (disqualified_constants, DECL_UID (decl));
766 :
767 4392551 : 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 4392551 : }
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 8083950 : type_internals_preclude_sra_p_1 (tree type, const char **msg,
781 : hash_set<tree> *visited_types)
782 : {
783 8083950 : tree fld;
784 8083950 : tree et;
785 :
786 8083950 : if (visited_types->contains (type))
787 : return false;
788 7791099 : visited_types->add (type);
789 :
790 7791099 : switch (TREE_CODE (type))
791 : {
792 7130627 : case RECORD_TYPE:
793 7130627 : case UNION_TYPE:
794 7130627 : case QUAL_UNION_TYPE:
795 135522502 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
796 128402334 : if (TREE_CODE (fld) == FIELD_DECL)
797 : {
798 16498361 : if (TREE_CODE (fld) == FUNCTION_DECL)
799 : continue;
800 16498361 : tree ft = TREE_TYPE (fld);
801 :
802 16498361 : if (TREE_THIS_VOLATILE (fld))
803 : {
804 905 : *msg = "volatile structure field";
805 905 : return true;
806 : }
807 16497456 : if (!DECL_FIELD_OFFSET (fld))
808 : {
809 0 : *msg = "no structure field offset";
810 0 : return true;
811 : }
812 16497456 : if (!DECL_SIZE (fld))
813 : {
814 8443 : *msg = "zero structure field size";
815 8443 : return true;
816 : }
817 16489013 : if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
818 : {
819 0 : *msg = "structure field offset not fixed";
820 0 : return true;
821 : }
822 16489013 : if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
823 : {
824 0 : *msg = "structure field size not fixed";
825 0 : return true;
826 : }
827 16489013 : if (!tree_fits_shwi_p (bit_position (fld)))
828 : {
829 0 : *msg = "structure field size too big";
830 0 : return true;
831 : }
832 16489013 : if (AGGREGATE_TYPE_P (ft)
833 16489013 : && int_bit_position (fld) % BITS_PER_UNIT != 0)
834 : {
835 0 : *msg = "structure field is bit field";
836 0 : return true;
837 : }
838 :
839 16489013 : if (AGGREGATE_TYPE_P (ft)
840 16489013 : && type_internals_preclude_sra_p_1 (ft, msg, visited_types))
841 : return true;
842 : }
843 :
844 : return false;
845 :
846 539421 : case ARRAY_TYPE:
847 539421 : et = TREE_TYPE (type);
848 :
849 539421 : if (TYPE_VOLATILE (et))
850 : {
851 0 : *msg = "element type is volatile";
852 0 : return true;
853 : }
854 :
855 539421 : if (AGGREGATE_TYPE_P (et)
856 539421 : && 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 4745270 : type_internals_preclude_sra_p (tree type, const char **msg)
871 : {
872 4745270 : hash_set<tree> visited_types;
873 4745270 : return type_internals_preclude_sra_p_1 (type, msg, &visited_types);
874 4745270 : }
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 14593989 : create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
883 : {
884 14593989 : struct access *access = access_pool.allocate ();
885 :
886 14593989 : memset (access, 0, sizeof (struct access));
887 14593989 : access->base = base;
888 14593989 : access->offset = offset;
889 14593989 : access->size = size;
890 :
891 14593989 : base_access_vec->get_or_insert (base).safe_push (access);
892 :
893 14593989 : 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 27886182 : create_access (tree expr, gimple *stmt, bool write)
904 : {
905 27886182 : struct access *access;
906 27886182 : poly_int64 poffset, psize, pmax_size;
907 27886182 : tree base = expr;
908 27886182 : bool reverse, unscalarizable_region = false;
909 :
910 27886182 : 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 27886182 : if (constant_decl_p (base)
915 3690 : && !bitmap_bit_p (disqualified_constants, DECL_UID (base)))
916 : {
917 3690 : if (expr != base
918 275 : && !is_gimple_reg_type (TREE_TYPE (expr))
919 3702 : && 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 3690 : maybe_add_sra_candidate (base);
929 : }
930 :
931 27886182 : if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
932 13284917 : return NULL;
933 :
934 14601265 : if (write && TREE_READONLY (base))
935 : {
936 6376 : disqualify_candidate (base, "Encountered a store to a read-only decl.");
937 6376 : return NULL;
938 : }
939 :
940 14594889 : HOST_WIDE_INT offset, size, max_size;
941 14594889 : if (!poffset.is_constant (&offset)
942 14594889 : || !psize.is_constant (&size)
943 14594889 : || !pmax_size.is_constant (&max_size))
944 : {
945 : disqualify_candidate (base, "Encountered a polynomial-sized access.");
946 : return NULL;
947 : }
948 :
949 14594889 : if (size != max_size)
950 : {
951 384005 : size = max_size;
952 384005 : unscalarizable_region = true;
953 : }
954 14594889 : if (size == 0)
955 : return NULL;
956 14594887 : if (offset < 0)
957 : {
958 34 : disqualify_candidate (base, "Encountered a negative offset access.");
959 34 : return NULL;
960 : }
961 14594853 : if (size < 0)
962 : {
963 24 : disqualify_candidate (base, "Encountered an unconstrained access.");
964 24 : return NULL;
965 : }
966 14594829 : if (offset + size > tree_to_shwi (DECL_SIZE (base)))
967 : {
968 839 : disqualify_candidate (base, "Encountered an access beyond the base.");
969 839 : return NULL;
970 : }
971 14593990 : if (TREE_CODE (TREE_TYPE (expr)) == BITINT_TYPE
972 14593990 : && size > WIDE_INT_MAX_PRECISION - 1)
973 : {
974 1 : disqualify_candidate (base, "Encountered too large _BitInt access.");
975 1 : return NULL;
976 : }
977 :
978 14593989 : access = create_access_1 (base, offset, size);
979 14593989 : access->expr = expr;
980 14593989 : access->type = TREE_TYPE (expr);
981 14593989 : access->write = write;
982 14593989 : access->grp_unscalarizable_region = unscalarizable_region;
983 14593989 : access->grp_same_access_path = true;
984 14593989 : access->stmt = stmt;
985 14593989 : access->reverse = reverse;
986 :
987 14593989 : return access;
988 : }
989 :
990 : /* Given an array type TYPE, extract element size to *EL_SIZE, minimum index to
991 : *IDX and maximum index to *MAX so that the caller can iterate over all
992 : elements and return true, except if the array is known to be zero-length,
993 : then return false. */
994 :
995 : static bool
996 23017 : prepare_iteration_over_array_elts (tree type, HOST_WIDE_INT *el_size,
997 : offset_int *idx, offset_int *max)
998 : {
999 23017 : tree elem_size = TYPE_SIZE (TREE_TYPE (type));
1000 23017 : gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
1001 23017 : *el_size = tree_to_shwi (elem_size);
1002 23017 : gcc_assert (*el_size > 0);
1003 :
1004 23017 : tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1005 23017 : gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1006 23017 : tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1007 : /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1008 23017 : if (!maxidx)
1009 : return false;
1010 23017 : gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1011 23017 : tree domain = TYPE_DOMAIN (type);
1012 : /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1013 : DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1014 23017 : *idx = wi::to_offset (minidx);
1015 23017 : *max = wi::to_offset (maxidx);
1016 23017 : if (!TYPE_UNSIGNED (domain))
1017 : {
1018 23017 : *idx = wi::sext (*idx, TYPE_PRECISION (domain));
1019 23017 : *max = wi::sext (*max, TYPE_PRECISION (domain));
1020 : }
1021 : return true;
1022 : }
1023 :
1024 : /* A structure to track collecting padding and hold collected padding
1025 : information. */
1026 :
1027 70886 : class sra_padding_collecting
1028 : {
1029 : public:
1030 : /* Given that there won't be any data until at least OFFSET, add an
1031 : appropriate entry to the list of paddings or extend the last one. */
1032 : void record_padding (HOST_WIDE_INT offset);
1033 : /* Vector of pairs describing contiguous pieces of padding, each pair
1034 : consisting of offset and length. */
1035 : auto_vec<std::pair<HOST_WIDE_INT, HOST_WIDE_INT>, 10> m_padding;
1036 : /* Offset where data should continue after the last seen actual bit of data
1037 : if there was no padding. */
1038 : HOST_WIDE_INT m_data_until = 0;
1039 : };
1040 :
1041 : /* Given that there won't be any data until at least OFFSET, add an appropriate
1042 : entry to the list of paddings or extend the last one. */
1043 :
1044 200972 : void sra_padding_collecting::record_padding (HOST_WIDE_INT offset)
1045 : {
1046 200972 : if (offset > m_data_until)
1047 : {
1048 15764 : HOST_WIDE_INT psz = offset - m_data_until;
1049 15764 : if (!m_padding.is_empty ()
1050 574 : && ((m_padding[m_padding.length () - 1].first
1051 574 : + m_padding[m_padding.length () - 1].second) == offset))
1052 0 : m_padding[m_padding.length () - 1].second += psz;
1053 : else
1054 15764 : m_padding.safe_push (std::make_pair (m_data_until, psz));
1055 : }
1056 200972 : }
1057 :
1058 : /* Return true iff TYPE is totally scalarizable - i.e. a RECORD_TYPE or
1059 : fixed-length ARRAY_TYPE with fields that are either of gimple register types
1060 : (excluding bit-fields) or (recursively) scalarizable types. CONST_DECL must
1061 : be true if we are considering a decl from constant pool. If it is false,
1062 : char arrays will be refused.
1063 :
1064 : TOTAL_OFFSET is the offset of TYPE within any outer type that is being
1065 : examined.
1066 :
1067 : If PC is non-NULL, collect padding information into the vector within the
1068 : structure. The information is however only complete if the function returns
1069 : true and does not contain any padding at its end. */
1070 :
1071 : static bool
1072 2840556 : totally_scalarizable_type_p (tree type, bool const_decl,
1073 : HOST_WIDE_INT total_offset,
1074 : sra_padding_collecting *pc)
1075 : {
1076 2840556 : if (is_gimple_reg_type (type))
1077 : {
1078 1825453 : if (pc)
1079 : {
1080 128438 : pc->record_padding (total_offset);
1081 128438 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1082 : }
1083 1825453 : return true;
1084 : }
1085 1015103 : if (type_contains_placeholder_p (type))
1086 : return false;
1087 :
1088 1015103 : bool have_predecessor_field = false;
1089 1015103 : HOST_WIDE_INT prev_pos = 0;
1090 :
1091 1015103 : switch (TREE_CODE (type))
1092 : {
1093 969447 : case RECORD_TYPE:
1094 14414268 : for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1095 13474495 : if (TREE_CODE (fld) == FIELD_DECL)
1096 : {
1097 2062181 : tree ft = TREE_TYPE (fld);
1098 :
1099 2062181 : if (!DECL_SIZE (fld))
1100 : return false;
1101 2062181 : if (zerop (DECL_SIZE (fld)))
1102 52100 : continue;
1103 :
1104 2010081 : HOST_WIDE_INT pos = int_bit_position (fld);
1105 2010081 : if (have_predecessor_field
1106 2010081 : && pos <= prev_pos)
1107 : return false;
1108 :
1109 2010081 : have_predecessor_field = true;
1110 2010081 : prev_pos = pos;
1111 :
1112 2010081 : if (DECL_BIT_FIELD (fld))
1113 : return false;
1114 :
1115 2008305 : if (!totally_scalarizable_type_p (ft, const_decl, total_offset + pos,
1116 : pc))
1117 : return false;
1118 : }
1119 :
1120 : return true;
1121 :
1122 29592 : case ARRAY_TYPE:
1123 29592 : {
1124 29592 : HOST_WIDE_INT min_elem_size;
1125 29592 : if (const_decl)
1126 : min_elem_size = 0;
1127 : else
1128 19803 : min_elem_size = BITS_PER_UNIT;
1129 :
1130 29592 : if (TYPE_DOMAIN (type) == NULL_TREE
1131 29592 : || !tree_fits_shwi_p (TYPE_SIZE (type))
1132 29592 : || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1133 29592 : || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1134 53615 : || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1135 : return false;
1136 24023 : if (tree_to_shwi (TYPE_SIZE (type)) == 0
1137 24023 : && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1138 : /* Zero-element array, should not prevent scalarization. */
1139 : ;
1140 24023 : else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1141 24023 : || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1142 : /* Variable-length array, do not allow scalarization. */
1143 : return false;
1144 :
1145 23987 : unsigned old_padding_len = 0;
1146 23987 : if (pc)
1147 9628 : old_padding_len = pc->m_padding.length ();
1148 23987 : tree elem = TREE_TYPE (type);
1149 23987 : if (!totally_scalarizable_type_p (elem, const_decl, total_offset, pc))
1150 : return false;
1151 23848 : if (pc)
1152 : {
1153 9628 : unsigned new_padding_len = pc->m_padding.length ();
1154 9628 : HOST_WIDE_INT el_size;
1155 9628 : offset_int idx, max;
1156 9628 : if (!prepare_iteration_over_array_elts (type, &el_size, &idx, &max))
1157 0 : return true;
1158 9628 : pc->record_padding (total_offset + el_size);
1159 9628 : ++idx;
1160 9628 : for (HOST_WIDE_INT pos = total_offset + el_size;
1161 261898 : idx <= max;
1162 252270 : pos += el_size, ++idx)
1163 : {
1164 252297 : for (unsigned i = old_padding_len; i < new_padding_len; i++)
1165 : {
1166 27 : HOST_WIDE_INT pp
1167 27 : = pos + pc->m_padding[i].first - total_offset;
1168 27 : HOST_WIDE_INT psz = pc->m_padding[i].second;
1169 27 : pc->m_padding.safe_push (std::make_pair (pp, psz));
1170 : }
1171 : }
1172 9628 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1173 : }
1174 : return true;
1175 : }
1176 : default:
1177 : return false;
1178 : }
1179 : }
1180 :
1181 : /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1182 :
1183 : static inline bool
1184 57412034 : contains_view_convert_expr_p (const_tree ref)
1185 : {
1186 79085233 : while (handled_component_p (ref))
1187 : {
1188 21683261 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1189 : return true;
1190 21673199 : ref = TREE_OPERAND (ref, 0);
1191 : }
1192 :
1193 : return false;
1194 : }
1195 :
1196 : /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1197 : bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1198 : it points to will be set if REF contains any of the above or a MEM_REF
1199 : expression that effectively performs type conversion. */
1200 :
1201 : static bool
1202 7631727 : contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1203 : {
1204 9841347 : while (handled_component_p (ref))
1205 : {
1206 2594041 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1207 2594041 : || (TREE_CODE (ref) == COMPONENT_REF
1208 1880163 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1209 : {
1210 384421 : if (type_changing_p)
1211 199983 : *type_changing_p = true;
1212 384421 : return true;
1213 : }
1214 2209620 : ref = TREE_OPERAND (ref, 0);
1215 : }
1216 :
1217 7247306 : if (!type_changing_p
1218 3510015 : || TREE_CODE (ref) != MEM_REF
1219 7359094 : || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1220 : return false;
1221 :
1222 111788 : tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1223 111788 : if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1224 111788 : != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1225 86616 : *type_changing_p = true;
1226 :
1227 : return false;
1228 : }
1229 :
1230 : /* Search the given tree for a declaration by skipping handled components and
1231 : exclude it from the candidates. */
1232 :
1233 : static void
1234 994564 : disqualify_base_of_expr (tree t, const char *reason)
1235 : {
1236 994564 : t = get_base_address (t);
1237 994564 : if (t && DECL_P (t))
1238 836485 : disqualify_candidate (t, reason);
1239 994564 : }
1240 :
1241 : /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1242 :
1243 : static bool
1244 162942 : sra_handled_bf_read_p (tree expr)
1245 : {
1246 162942 : uint64_t size, offset;
1247 162942 : if (bit_field_size (expr).is_constant (&size)
1248 162942 : && bit_field_offset (expr).is_constant (&offset)
1249 162942 : && size % BITS_PER_UNIT == 0
1250 162942 : && offset % BITS_PER_UNIT == 0
1251 163010 : && pow2p_hwi (size))
1252 162850 : return true;
1253 : return false;
1254 : }
1255 :
1256 : /* Scan expression EXPR and create access structures for all accesses to
1257 : candidates for scalarization. Return the created access or NULL if none is
1258 : created. */
1259 :
1260 : static struct access *
1261 59396493 : build_access_from_expr_1 (tree expr, gimple *stmt, bool write)
1262 : {
1263 : /* We only allow ADDR_EXPRs in arguments of function calls and those must
1264 : have been dealt with in build_access_from_call_arg. Any other address
1265 : taking should have been caught by scan_visit_addr. */
1266 59396493 : if (TREE_CODE (expr) == ADDR_EXPR)
1267 : {
1268 1984458 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1269 1984458 : gcc_assert (!DECL_P (base)
1270 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)));
1271 1984458 : return NULL;
1272 : }
1273 :
1274 57412035 : struct access *ret = NULL;
1275 57412035 : bool partial_ref;
1276 :
1277 57412035 : if ((TREE_CODE (expr) == BIT_FIELD_REF
1278 91285 : && (write || !sra_handled_bf_read_p (expr)))
1279 57410917 : || TREE_CODE (expr) == IMAGPART_EXPR
1280 114798411 : || TREE_CODE (expr) == REALPART_EXPR)
1281 : {
1282 48959 : expr = TREE_OPERAND (expr, 0);
1283 48959 : partial_ref = true;
1284 : }
1285 : else
1286 : partial_ref = false;
1287 :
1288 57412035 : if (storage_order_barrier_p (expr))
1289 : {
1290 1 : disqualify_base_of_expr (expr, "storage order barrier.");
1291 1 : return NULL;
1292 : }
1293 :
1294 : /* We are capable of handling the topmost V_C_E but not any of those
1295 : buried in other handled components. */
1296 57702990 : if (contains_view_convert_expr_p (TREE_CODE (expr) == VIEW_CONVERT_EXPR
1297 290956 : ? TREE_OPERAND (expr, 0) : expr))
1298 : {
1299 10062 : disqualify_base_of_expr (expr, "V_C_E under a different handled "
1300 : "component.");
1301 10062 : return NULL;
1302 : }
1303 :
1304 57401972 : if (TREE_THIS_VOLATILE (expr))
1305 : {
1306 21986 : disqualify_base_of_expr (expr, "part of a volatile reference.");
1307 21986 : return NULL;
1308 : }
1309 :
1310 57379986 : switch (TREE_CODE (expr))
1311 : {
1312 3489954 : case MEM_REF:
1313 3489954 : if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR)
1314 : return NULL;
1315 : /* fall through */
1316 27886182 : case VAR_DECL:
1317 27886182 : case PARM_DECL:
1318 27886182 : case RESULT_DECL:
1319 27886182 : case COMPONENT_REF:
1320 27886182 : case ARRAY_REF:
1321 27886182 : case ARRAY_RANGE_REF:
1322 27886182 : case BIT_FIELD_REF:
1323 27886182 : case VIEW_CONVERT_EXPR:
1324 27886182 : ret = create_access (expr, stmt, write);
1325 27886182 : break;
1326 :
1327 : default:
1328 : break;
1329 : }
1330 :
1331 55619118 : if (write && partial_ref && ret)
1332 4351 : ret->grp_partial_lhs = 1;
1333 :
1334 : return ret;
1335 : }
1336 :
1337 : /* Scan expression EXPR and create access structures for all accesses to
1338 : candidates for scalarization. Return true if any access has been inserted.
1339 : STMT must be the statement from which the expression is taken, WRITE must be
1340 : true if the expression is a store and false otherwise. */
1341 :
1342 : static bool
1343 16404391 : build_access_from_expr (tree expr, gimple *stmt, bool write)
1344 : {
1345 16404391 : struct access *access;
1346 :
1347 16404391 : access = build_access_from_expr_1 (expr, stmt, write);
1348 16404391 : if (access)
1349 : {
1350 : /* This means the aggregate is accesses as a whole in a way other than an
1351 : assign statement and thus cannot be removed even if we had a scalar
1352 : replacement for everything. */
1353 2505095 : if (cannot_scalarize_away_bitmap)
1354 2505095 : bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1355 2505095 : return true;
1356 : }
1357 : return false;
1358 : }
1359 :
1360 : enum out_edge_check { SRA_OUTGOING_EDGES_UNCHECKED, SRA_OUTGOING_EDGES_OK,
1361 : SRA_OUTGOING_EDGES_FAIL };
1362 :
1363 : /* Return true if STMT terminates BB and there is an abnormal edge going out of
1364 : the BB and remember the decision in OE_CHECK. */
1365 :
1366 : static bool
1367 2967967 : abnormal_edge_after_stmt_p (gimple *stmt, enum out_edge_check *oe_check)
1368 : {
1369 2967967 : if (*oe_check == SRA_OUTGOING_EDGES_OK)
1370 : return false;
1371 1735536 : if (*oe_check == SRA_OUTGOING_EDGES_FAIL)
1372 : return true;
1373 1735310 : if (stmt_ends_bb_p (stmt))
1374 : {
1375 710138 : edge e;
1376 710138 : edge_iterator ei;
1377 1848669 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1378 1139017 : if (e->flags & EDGE_ABNORMAL)
1379 : {
1380 486 : *oe_check = SRA_OUTGOING_EDGES_FAIL;
1381 486 : return true;
1382 : }
1383 : }
1384 1734824 : *oe_check = SRA_OUTGOING_EDGES_OK;
1385 1734824 : return false;
1386 : }
1387 :
1388 : /* Scan expression EXPR which is an argument of a call and create access
1389 : structures for all accesses to candidates for scalarization. Return true
1390 : if any access has been inserted. STMT must be the statement from which the
1391 : expression is taken. CAN_BE_RETURNED must be true if call argument flags
1392 : do not rule out that the argument is directly returned. OE_CHECK is used
1393 : to remember result of a test for abnormal outgoing edges after this
1394 : statement. */
1395 :
1396 : static bool
1397 11635739 : build_access_from_call_arg (tree expr, gimple *stmt, bool can_be_returned,
1398 : enum out_edge_check *oe_check)
1399 : {
1400 11635739 : if (gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
1401 : {
1402 57 : tree base = expr;
1403 57 : if (TREE_CODE (expr) == ADDR_EXPR)
1404 10 : base = get_base_address (TREE_OPERAND (expr, 0));
1405 57 : disqualify_base_of_expr (base, "Passed to a returns_twice call.");
1406 57 : return false;
1407 : }
1408 :
1409 11635682 : if (TREE_CODE (expr) == ADDR_EXPR)
1410 : {
1411 3929132 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1412 :
1413 3929132 : if (can_be_returned)
1414 : {
1415 961165 : disqualify_base_of_expr (base, "Address possibly returned, "
1416 : "leading to an alis SRA may not know.");
1417 961165 : return false;
1418 : }
1419 2967967 : if (abnormal_edge_after_stmt_p (stmt, oe_check))
1420 : {
1421 712 : disqualify_base_of_expr (base, "May lead to need to add statements "
1422 : "to abnormal edge.");
1423 712 : return false;
1424 : }
1425 :
1426 2967255 : bool read = build_access_from_expr (base, stmt, false);
1427 2967255 : bool write = build_access_from_expr (base, stmt, true);
1428 2967255 : if (read || write)
1429 : {
1430 276241 : if (dump_file && (dump_flags & TDF_DETAILS))
1431 : {
1432 0 : fprintf (dump_file, "Allowed ADDR_EXPR of ");
1433 0 : print_generic_expr (dump_file, base);
1434 0 : fprintf (dump_file, " because of ");
1435 0 : print_gimple_stmt (dump_file, stmt, 0);
1436 0 : fprintf (dump_file, "\n");
1437 : }
1438 276241 : bitmap_set_bit (passed_by_ref_in_call, DECL_UID (base));
1439 276241 : return true;
1440 : }
1441 : else
1442 : return false;
1443 : }
1444 :
1445 7706550 : return build_access_from_expr (expr, stmt, false);
1446 : }
1447 :
1448 :
1449 : /* Return the single non-EH successor edge of BB or NULL if there is none or
1450 : more than one. */
1451 :
1452 : static edge
1453 1464626 : single_non_eh_succ (basic_block bb)
1454 : {
1455 1464626 : edge e, res = NULL;
1456 1464626 : edge_iterator ei;
1457 :
1458 4392409 : FOR_EACH_EDGE (e, ei, bb->succs)
1459 2928203 : if (!(e->flags & EDGE_EH))
1460 : {
1461 1464929 : if (res)
1462 : return NULL;
1463 : res = e;
1464 : }
1465 :
1466 : return res;
1467 : }
1468 :
1469 : /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1470 : there is no alternative spot where to put statements SRA might need to
1471 : generate after it. The spot we are looking for is an edge leading to a
1472 : single non-EH successor, if it exists and is indeed single. RHS may be
1473 : NULL, in that case ignore it. */
1474 :
1475 : static bool
1476 23839825 : disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1477 : {
1478 23839825 : if (stmt_ends_bb_p (stmt))
1479 : {
1480 1353120 : if (single_non_eh_succ (gimple_bb (stmt)))
1481 : return false;
1482 :
1483 537 : disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1484 537 : if (rhs)
1485 0 : disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1486 537 : return true;
1487 : }
1488 : return false;
1489 : }
1490 :
1491 : /* Return true if the nature of BASE is such that it contains data even if
1492 : there is no write to it in the function. */
1493 :
1494 : static bool
1495 4051732 : comes_initialized_p (tree base)
1496 : {
1497 0 : return TREE_CODE (base) == PARM_DECL || constant_decl_p (base);
1498 : }
1499 :
1500 : /* Scan expressions occurring in STMT, create access structures for all accesses
1501 : to candidates for scalarization and remove those candidates which occur in
1502 : statements or expressions that prevent them from being split apart. Return
1503 : true if any access has been inserted. */
1504 :
1505 : static bool
1506 32667757 : build_accesses_from_assign (gimple *stmt)
1507 : {
1508 32667757 : tree lhs, rhs;
1509 32667757 : struct access *lacc, *racc;
1510 :
1511 32667757 : if (!gimple_assign_single_p (stmt)
1512 : /* Scope clobbers don't influence scalarization. */
1513 32667757 : || gimple_clobber_p (stmt))
1514 : return false;
1515 :
1516 21444992 : lhs = gimple_assign_lhs (stmt);
1517 21444992 : rhs = gimple_assign_rhs1 (stmt);
1518 :
1519 21444992 : if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1520 : return false;
1521 :
1522 21444992 : racc = build_access_from_expr_1 (rhs, stmt, false);
1523 21444992 : lacc = build_access_from_expr_1 (lhs, stmt, true);
1524 :
1525 21444992 : bool tbaa_hazard
1526 21444992 : = !types_equal_for_same_type_for_tbaa_p (TREE_TYPE (lhs), TREE_TYPE (rhs));
1527 :
1528 21444992 : if (lacc)
1529 : {
1530 6552181 : lacc->grp_assignment_write = 1;
1531 6552181 : if (storage_order_barrier_p (rhs))
1532 1 : lacc->grp_unscalarizable_region = 1;
1533 :
1534 6552181 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1535 : {
1536 1924350 : bool type_changing_p = false;
1537 1924350 : contains_vce_or_bfcref_p (lhs, &type_changing_p);
1538 1924350 : if (type_changing_p)
1539 137288 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1540 68644 : DECL_UID (lacc->base));
1541 : }
1542 6552181 : if (tbaa_hazard)
1543 838302 : lacc->grp_same_access_path = false;
1544 : }
1545 :
1546 21444992 : if (racc)
1547 : {
1548 5492431 : racc->grp_assignment_read = 1;
1549 5492431 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1550 : {
1551 1785648 : bool type_changing_p = false;
1552 1785648 : contains_vce_or_bfcref_p (rhs, &type_changing_p);
1553 :
1554 3353341 : if (type_changing_p || gimple_has_volatile_ops (stmt))
1555 436656 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1556 218328 : DECL_UID (racc->base));
1557 : else
1558 3134640 : bitmap_set_bit (should_scalarize_away_bitmap,
1559 1567320 : DECL_UID (racc->base));
1560 : }
1561 5492431 : if (storage_order_barrier_p (lhs))
1562 0 : racc->grp_unscalarizable_region = 1;
1563 5492431 : if (tbaa_hazard)
1564 66093 : racc->grp_same_access_path = false;
1565 : }
1566 :
1567 21444992 : if (lacc && racc
1568 1312013 : && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1569 1312013 : && !lacc->grp_unscalarizable_region
1570 1311464 : && !racc->grp_unscalarizable_region
1571 1310672 : && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1572 1310672 : && lacc->size == racc->size
1573 22755440 : && useless_type_conversion_p (lacc->type, racc->type))
1574 : {
1575 1310448 : struct assign_link *link;
1576 :
1577 1310448 : link = assign_link_pool.allocate ();
1578 1310448 : memset (link, 0, sizeof (struct assign_link));
1579 :
1580 1310448 : link->lacc = lacc;
1581 1310448 : link->racc = racc;
1582 1310448 : add_link_to_rhs (racc, link);
1583 1310448 : add_link_to_lhs (lacc, link);
1584 1310448 : add_access_to_rhs_work_queue (racc);
1585 1310448 : add_access_to_lhs_work_queue (lacc);
1586 :
1587 : /* Let's delay marking the areas as written until propagation of accesses
1588 : across link, unless the nature of rhs tells us that its data comes
1589 : from elsewhere. */
1590 1310448 : if (!comes_initialized_p (racc->base))
1591 1217463 : lacc->write = false;
1592 : }
1593 :
1594 21444992 : return lacc || racc;
1595 : }
1596 :
1597 : /* Callback of walk_stmt_load_store_addr_ops visit_addr used to detect taking
1598 : addresses of candidates a places which are not call arguments. Such
1599 : candidates are disqalified from SRA. This also applies to GIMPLE_ASM
1600 : operands with memory constrains which cannot be scalarized. */
1601 :
1602 : static bool
1603 2338497 : scan_visit_addr (gimple *, tree op, tree, void *)
1604 : {
1605 2338497 : op = get_base_address (op);
1606 2338497 : if (op
1607 2338497 : && DECL_P (op))
1608 1287659 : disqualify_candidate (op, "Address taken in a non-call-argument context.");
1609 :
1610 2338497 : return false;
1611 : }
1612 :
1613 : /* Scan function and look for interesting expressions and create access
1614 : structures for them. Return true iff any access is created. */
1615 :
1616 : static bool
1617 758474 : scan_function (void)
1618 : {
1619 758474 : basic_block bb;
1620 758474 : bool ret = false;
1621 :
1622 13193495 : FOR_EACH_BB_FN (bb, cfun)
1623 : {
1624 12435021 : gimple_stmt_iterator gsi;
1625 17022062 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1626 4587041 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), NULL, NULL, NULL,
1627 : scan_visit_addr);
1628 :
1629 118456457 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1630 : {
1631 93586415 : gimple *stmt = gsi_stmt (gsi);
1632 93586415 : tree t;
1633 93586415 : unsigned i;
1634 :
1635 93586415 : if (gimple_code (stmt) != GIMPLE_CALL)
1636 87780610 : walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1637 : scan_visit_addr);
1638 :
1639 93586415 : switch (gimple_code (stmt))
1640 : {
1641 751361 : case GIMPLE_RETURN:
1642 751361 : t = gimple_return_retval (as_a <greturn *> (stmt));
1643 751361 : if (t != NULL_TREE)
1644 447736 : ret |= build_access_from_expr (t, stmt, false);
1645 : break;
1646 :
1647 32667757 : case GIMPLE_ASSIGN:
1648 32667757 : ret |= build_accesses_from_assign (stmt);
1649 32667757 : break;
1650 :
1651 5805805 : case GIMPLE_CALL:
1652 5805805 : {
1653 5805805 : enum out_edge_check oe_check = SRA_OUTGOING_EDGES_UNCHECKED;
1654 5805805 : gcall *call = as_a <gcall *> (stmt);
1655 17400984 : for (i = 0; i < gimple_call_num_args (call); i++)
1656 : {
1657 11595179 : bool can_be_returned;
1658 11595179 : if (gimple_call_lhs (call))
1659 : {
1660 4676079 : int af = gimple_call_arg_flags (call, i);
1661 4676079 : can_be_returned = !(af & EAF_NOT_RETURNED_DIRECTLY);
1662 : }
1663 : else
1664 : can_be_returned = false;
1665 11595179 : ret |= build_access_from_call_arg (gimple_call_arg (call,
1666 : i),
1667 : stmt, can_be_returned,
1668 : &oe_check);
1669 : }
1670 5805805 : if (gimple_call_chain(stmt))
1671 40560 : ret |= build_access_from_call_arg (gimple_call_chain(call),
1672 : stmt, false, &oe_check);
1673 : }
1674 :
1675 5805805 : t = gimple_call_lhs (stmt);
1676 5805805 : if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
1677 : {
1678 : /* If the STMT is a call to DEFERRED_INIT, avoid setting
1679 : cannot_scalarize_away_bitmap. */
1680 2394296 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
1681 : {
1682 102118 : struct access *access
1683 102118 : = build_access_from_expr_1 (t, stmt, true);
1684 102118 : if (access)
1685 44282 : access->grp_assignment_write = 1;
1686 102118 : ret |= access != NULL;
1687 : }
1688 : else
1689 2292178 : ret |= build_access_from_expr (t, stmt, true);
1690 : }
1691 : break;
1692 :
1693 13326 : case GIMPLE_ASM:
1694 13326 : {
1695 13326 : gasm *asm_stmt = as_a <gasm *> (stmt);
1696 13326 : if (stmt_ends_bb_p (asm_stmt)
1697 13341 : && !single_succ_p (gimple_bb (asm_stmt)))
1698 : {
1699 32 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1700 : {
1701 17 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1702 17 : disqualify_base_of_expr (t, "OP of asm goto.");
1703 : }
1704 42 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1705 : {
1706 27 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1707 27 : disqualify_base_of_expr (t, "OP of asm goto.");
1708 : }
1709 : }
1710 : else
1711 : {
1712 25511 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1713 : {
1714 12200 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1715 12200 : ret |= build_access_from_expr (t, asm_stmt, false);
1716 : }
1717 24528 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1718 : {
1719 11217 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1720 11217 : ret |= build_access_from_expr (t, asm_stmt, true);
1721 : }
1722 : }
1723 : }
1724 : break;
1725 :
1726 : default:
1727 : break;
1728 : }
1729 : }
1730 : }
1731 :
1732 758474 : return ret;
1733 : }
1734 :
1735 : /* Helper of QSORT function. There are pointers to accesses in the array. An
1736 : access is considered smaller than another if it has smaller offset or if the
1737 : offsets are the same but is size is bigger. */
1738 :
1739 : static int
1740 127718513 : compare_access_positions (const void *a, const void *b)
1741 : {
1742 127718513 : const access_p *fp1 = (const access_p *) a;
1743 127718513 : const access_p *fp2 = (const access_p *) b;
1744 127718513 : const access_p f1 = *fp1;
1745 127718513 : const access_p f2 = *fp2;
1746 :
1747 127718513 : if (f1->offset != f2->offset)
1748 114369093 : return f1->offset < f2->offset ? -1 : 1;
1749 :
1750 50142818 : if (f1->size == f2->size)
1751 : {
1752 34577370 : if (f1->type == f2->type)
1753 : return 0;
1754 : /* Put any non-aggregate type before any aggregate type. */
1755 5623503 : else if (!is_gimple_reg_type (f1->type)
1756 5623503 : && is_gimple_reg_type (f2->type))
1757 : return 1;
1758 4320473 : else if (is_gimple_reg_type (f1->type)
1759 4320473 : && !is_gimple_reg_type (f2->type))
1760 : return -1;
1761 : /* Put any complex or vector type before any other scalar type. */
1762 2634594 : else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1763 2634594 : && TREE_CODE (f1->type) != VECTOR_TYPE
1764 2548909 : && (TREE_CODE (f2->type) == COMPLEX_TYPE
1765 2548909 : || VECTOR_TYPE_P (f2->type)))
1766 : return 1;
1767 2589298 : else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1768 : || VECTOR_TYPE_P (f1->type))
1769 85685 : && TREE_CODE (f2->type) != COMPLEX_TYPE
1770 83365 : && TREE_CODE (f2->type) != VECTOR_TYPE)
1771 : return -1;
1772 : /* Put any integral type before any non-integral type. When splicing, we
1773 : make sure that those with insufficient precision and occupying the
1774 : same space are not scalarized. */
1775 2524781 : else if (INTEGRAL_TYPE_P (f1->type)
1776 391598 : && !INTEGRAL_TYPE_P (f2->type))
1777 : return -1;
1778 2410919 : else if (!INTEGRAL_TYPE_P (f1->type)
1779 2133183 : && INTEGRAL_TYPE_P (f2->type))
1780 : return 1;
1781 : /* Put the integral type with the bigger precision first. */
1782 2299032 : else if (INTEGRAL_TYPE_P (f1->type)
1783 277736 : && INTEGRAL_TYPE_P (f2->type)
1784 2576768 : && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1785 32440 : return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1786 : /* Stabilize the sort. */
1787 2266592 : return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1788 : }
1789 :
1790 : /* We want the bigger accesses first, thus the opposite operator in the next
1791 : line: */
1792 15565448 : return f1->size > f2->size ? -1 : 1;
1793 : }
1794 :
1795 :
1796 : /* Append a name of the declaration to the name obstack. A helper function for
1797 : make_fancy_name. */
1798 :
1799 : static void
1800 2047686 : make_fancy_decl_name (tree decl)
1801 : {
1802 2047686 : char buffer[32];
1803 :
1804 2047686 : tree name = DECL_NAME (decl);
1805 2047686 : if (name)
1806 1984704 : obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1807 : IDENTIFIER_LENGTH (name));
1808 : else
1809 : {
1810 62982 : sprintf (buffer, "D%u", DECL_UID (decl));
1811 62982 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1812 : }
1813 2047686 : }
1814 :
1815 : /* Helper for make_fancy_name. */
1816 :
1817 : static void
1818 2321958 : make_fancy_name_1 (tree expr)
1819 : {
1820 2539284 : char buffer[32];
1821 2539284 : tree index;
1822 :
1823 2539284 : if (DECL_P (expr))
1824 : {
1825 1014322 : make_fancy_decl_name (expr);
1826 1014322 : return;
1827 : }
1828 :
1829 1524962 : switch (TREE_CODE (expr))
1830 : {
1831 1033364 : case COMPONENT_REF:
1832 1033364 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1833 1033364 : obstack_1grow (&name_obstack, '$');
1834 1033364 : make_fancy_decl_name (TREE_OPERAND (expr, 1));
1835 1033364 : break;
1836 :
1837 58911 : case ARRAY_REF:
1838 58911 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1839 58911 : obstack_1grow (&name_obstack, '$');
1840 : /* Arrays with only one element may not have a constant as their
1841 : index. */
1842 58911 : index = TREE_OPERAND (expr, 1);
1843 58911 : if (TREE_CODE (index) != INTEGER_CST)
1844 : break;
1845 58789 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1846 58789 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1847 58789 : break;
1848 :
1849 217326 : case BIT_FIELD_REF:
1850 217326 : case ADDR_EXPR:
1851 217326 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1852 217326 : break;
1853 :
1854 215135 : case MEM_REF:
1855 215135 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1856 215135 : if (!integer_zerop (TREE_OPERAND (expr, 1)))
1857 : {
1858 70255 : obstack_1grow (&name_obstack, '$');
1859 140510 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1860 70255 : TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1861 70255 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1862 : }
1863 : break;
1864 :
1865 0 : case REALPART_EXPR:
1866 0 : case IMAGPART_EXPR:
1867 0 : gcc_unreachable (); /* we treat these as scalars. */
1868 : break;
1869 : default:
1870 : break;
1871 : }
1872 : }
1873 :
1874 : /* Create a human readable name for replacement variable of ACCESS. */
1875 :
1876 : static char *
1877 1014548 : make_fancy_name (tree expr)
1878 : {
1879 1014548 : make_fancy_name_1 (expr);
1880 1014548 : obstack_1grow (&name_obstack, '\0');
1881 1014548 : return XOBFINISH (&name_obstack, char *);
1882 : }
1883 :
1884 : /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1885 : EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1886 : something for which get_addr_base_and_unit_offset returns NULL, gsi must
1887 : be non-NULL and is used to insert new statements either before or below
1888 : the current one as specified by INSERT_AFTER. This function is not capable
1889 : of handling bitfields. If FORCE_REF_ALL is true then the memory access
1890 : will use alias-set zero. */
1891 :
1892 : static tree
1893 2439549 : build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
1894 : bool reverse, tree exp_type, gimple_stmt_iterator *gsi,
1895 : bool insert_after, bool force_ref_all = false)
1896 : {
1897 2439549 : tree prev_base = base;
1898 2439549 : tree off;
1899 2439549 : tree mem_ref;
1900 2439549 : poly_int64 base_offset;
1901 2439549 : unsigned HOST_WIDE_INT misalign;
1902 2439549 : unsigned int align;
1903 :
1904 : /* Preserve address-space information. */
1905 2439549 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1906 2439549 : if (as != TYPE_ADDR_SPACE (exp_type))
1907 4 : exp_type = build_qualified_type (exp_type,
1908 2 : TYPE_QUALS (exp_type)
1909 2 : | ENCODE_QUAL_ADDR_SPACE (as));
1910 :
1911 2439549 : poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1912 2439549 : get_object_alignment_1 (base, &align, &misalign);
1913 2439549 : base = get_addr_base_and_unit_offset (base, &base_offset);
1914 :
1915 : /* get_addr_base_and_unit_offset returns NULL for references with a variable
1916 : offset such as array[var_index]. */
1917 2439549 : if (!base)
1918 : {
1919 34161 : gassign *stmt;
1920 34161 : tree tmp, addr;
1921 :
1922 34161 : gcc_checking_assert (gsi);
1923 34161 : tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1924 34161 : addr = build_fold_addr_expr (unshare_expr (prev_base));
1925 34161 : STRIP_USELESS_TYPE_CONVERSION (addr);
1926 34161 : stmt = gimple_build_assign (tmp, addr);
1927 34161 : gimple_set_location (stmt, loc);
1928 34161 : if (insert_after)
1929 9432 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1930 : else
1931 24729 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1932 :
1933 34161 : off = build_int_cst (force_ref_all ? ptr_type_node
1934 34161 : : reference_alias_ptr_type (prev_base), byte_offset);
1935 34161 : base = tmp;
1936 : }
1937 2405388 : else if (TREE_CODE (base) == MEM_REF)
1938 : {
1939 398160 : off = build_int_cst (force_ref_all ? ptr_type_node
1940 199080 : : TREE_TYPE (TREE_OPERAND (base, 1)),
1941 : base_offset + byte_offset);
1942 199080 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1943 199080 : base = unshare_expr (TREE_OPERAND (base, 0));
1944 : }
1945 : else
1946 : {
1947 4067956 : off = build_int_cst (force_ref_all ? ptr_type_node
1948 1861648 : : reference_alias_ptr_type (prev_base),
1949 : base_offset + byte_offset);
1950 2206308 : base = build_fold_addr_expr (unshare_expr (base));
1951 : }
1952 :
1953 2439549 : unsigned int align_bound = known_alignment (misalign + offset);
1954 2439549 : if (align_bound != 0)
1955 1600799 : align = MIN (align, align_bound);
1956 2439549 : if (align != TYPE_ALIGN (exp_type))
1957 489013 : exp_type = build_aligned_type (exp_type, align);
1958 :
1959 2439549 : mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1960 2439549 : REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1961 2439549 : if (TREE_THIS_VOLATILE (prev_base))
1962 6 : TREE_THIS_VOLATILE (mem_ref) = 1;
1963 2439549 : if (TREE_SIDE_EFFECTS (prev_base))
1964 126 : TREE_SIDE_EFFECTS (mem_ref) = 1;
1965 2439549 : return mem_ref;
1966 : }
1967 :
1968 : /* Construct and return a memory reference that is equal to a portion of
1969 : MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1970 :
1971 : static tree
1972 1742121 : build_reconstructed_reference (location_t, tree base, struct access *model)
1973 : {
1974 1742121 : tree expr = model->expr;
1975 : /* We have to make sure to start just below the outermost union. */
1976 1742121 : tree start_expr = expr;
1977 3503016 : while (handled_component_p (expr))
1978 : {
1979 1760895 : if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == UNION_TYPE)
1980 9001 : start_expr = expr;
1981 1760895 : expr = TREE_OPERAND (expr, 0);
1982 : }
1983 :
1984 : expr = start_expr;
1985 : tree prev_expr = NULL_TREE;
1986 3478475 : while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
1987 : {
1988 1907666 : if (!handled_component_p (expr))
1989 : return NULL_TREE;
1990 1736354 : prev_expr = expr;
1991 1736354 : expr = TREE_OPERAND (expr, 0);
1992 : }
1993 :
1994 : /* Guard against broken VIEW_CONVERT_EXPRs... */
1995 1570809 : if (!prev_expr)
1996 : return NULL_TREE;
1997 :
1998 1569833 : TREE_OPERAND (prev_expr, 0) = base;
1999 1569833 : tree ref = unshare_expr (model->expr);
2000 1569833 : TREE_OPERAND (prev_expr, 0) = expr;
2001 1569833 : return ref;
2002 : }
2003 :
2004 : /* Construct a memory reference to a part of an aggregate BASE at the given
2005 : OFFSET and of the same type as MODEL. In case this is a reference to a
2006 : bit-field, the function will replicate the last component_ref of model's
2007 : expr to access it. INSERT_AFTER and GSI have the same meaning as in
2008 : build_ref_for_offset, furthermore, when GSI is NULL, the function expects
2009 : that it re-builds the entire reference from a DECL to the final access and
2010 : so will create a MEM_REF when OFFSET does not exactly match offset of
2011 : MODEL. If FORCE_REF_ALL is true then the memory access will use
2012 : alias-set zero. */
2013 :
2014 : static tree
2015 3949800 : build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2016 : struct access *model, gimple_stmt_iterator *gsi,
2017 : bool insert_after, bool force_ref_all = false)
2018 : {
2019 3949800 : gcc_assert (offset >= 0);
2020 3949800 : if (TREE_CODE (model->expr) == COMPONENT_REF
2021 3949800 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2022 : {
2023 : /* This access represents a bit-field. */
2024 41450 : tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
2025 :
2026 41450 : offset -= int_bit_position (fld);
2027 41450 : exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
2028 41450 : t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type,
2029 : gsi, insert_after, force_ref_all);
2030 : /* The flag will be set on the record type. */
2031 41450 : REF_REVERSE_STORAGE_ORDER (t) = 0;
2032 41450 : return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
2033 41450 : NULL_TREE);
2034 : }
2035 : else
2036 : {
2037 3908350 : tree res;
2038 3908350 : if (model->grp_same_access_path
2039 1862111 : && !force_ref_all
2040 1742213 : && !TREE_THIS_VOLATILE (base)
2041 1742207 : && (TYPE_ADDR_SPACE (TREE_TYPE (base))
2042 1742207 : == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
2043 1742206 : && (offset == model->offset
2044 10309 : || (gsi && offset <= model->offset))
2045 : /* build_reconstructed_reference can still fail if we have already
2046 : massaged BASE because of another type incompatibility. */
2047 5650471 : && (res = build_reconstructed_reference (loc, base, model)))
2048 : return res;
2049 : else
2050 2338517 : return build_ref_for_offset (loc, base, offset, model->reverse,
2051 : model->type, gsi, insert_after,
2052 : force_ref_all);
2053 : }
2054 : }
2055 :
2056 : /* Attempt to build a memory reference that we could but into a gimple
2057 : debug_bind statement. Similar to build_ref_for_model but punts if it has to
2058 : create statements and return s NULL instead. This function also ignores
2059 : alignment issues and so its results should never end up in non-debug
2060 : statements. */
2061 :
2062 : static tree
2063 5937 : build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2064 : struct access *model)
2065 : {
2066 5937 : poly_int64 base_offset;
2067 5937 : tree off;
2068 :
2069 5937 : if (TREE_CODE (model->expr) == COMPONENT_REF
2070 5937 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2071 : return NULL_TREE;
2072 :
2073 5937 : base = get_addr_base_and_unit_offset (base, &base_offset);
2074 5937 : if (!base)
2075 : return NULL_TREE;
2076 5937 : if (TREE_CODE (base) == MEM_REF)
2077 : {
2078 201 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
2079 201 : base_offset + offset / BITS_PER_UNIT);
2080 201 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
2081 201 : base = unshare_expr (TREE_OPERAND (base, 0));
2082 : }
2083 : else
2084 : {
2085 5736 : off = build_int_cst (reference_alias_ptr_type (base),
2086 5736 : base_offset + offset / BITS_PER_UNIT);
2087 5736 : base = build_fold_addr_expr (unshare_expr (base));
2088 : }
2089 :
2090 5937 : return fold_build2_loc (loc, MEM_REF, model->type, base, off);
2091 : }
2092 :
2093 : /* Construct a memory reference consisting of component_refs and array_refs to
2094 : a part of an aggregate *RES (which is of type TYPE). The requested part
2095 : should have type EXP_TYPE at be the given OFFSET. This function might not
2096 : succeed, it returns true when it does and only then *RES points to something
2097 : meaningful. This function should be used only to build expressions that we
2098 : might need to present to user (e.g. in warnings). In all other situations,
2099 : build_ref_for_model or build_ref_for_offset should be used instead. */
2100 :
2101 : static bool
2102 3850925 : build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
2103 : tree exp_type)
2104 : {
2105 3905817 : while (1)
2106 : {
2107 3878371 : tree fld;
2108 3878371 : tree tr_size, index, minidx;
2109 3878371 : HOST_WIDE_INT el_size;
2110 :
2111 3878371 : if (offset == 0 && exp_type
2112 3878371 : && types_compatible_p (exp_type, type))
2113 : return true;
2114 :
2115 2345410 : switch (TREE_CODE (type))
2116 : {
2117 2288090 : case UNION_TYPE:
2118 2288090 : case QUAL_UNION_TYPE:
2119 2288090 : case RECORD_TYPE:
2120 12341662 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
2121 : {
2122 12273280 : HOST_WIDE_INT pos, size;
2123 12273280 : tree tr_pos, expr, *expr_ptr;
2124 :
2125 12273280 : if (TREE_CODE (fld) != FIELD_DECL)
2126 9983637 : continue;
2127 :
2128 3803778 : tr_pos = bit_position (fld);
2129 3803778 : if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
2130 0 : continue;
2131 3803778 : pos = tree_to_uhwi (tr_pos);
2132 3803778 : gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
2133 3803778 : tr_size = DECL_SIZE (fld);
2134 3803778 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2135 0 : continue;
2136 3803778 : size = tree_to_uhwi (tr_size);
2137 3803778 : if (size == 0)
2138 : {
2139 53360 : if (pos != offset)
2140 22064 : continue;
2141 : }
2142 3750418 : else if (pos > offset || (pos + size) <= offset)
2143 1492071 : continue;
2144 :
2145 2289643 : expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
2146 : NULL_TREE);
2147 2289643 : expr_ptr = &expr;
2148 2289643 : if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
2149 : offset - pos, exp_type))
2150 : {
2151 2219708 : *res = expr;
2152 2219708 : return true;
2153 : }
2154 : }
2155 : return false;
2156 :
2157 27446 : case ARRAY_TYPE:
2158 27446 : tr_size = TYPE_SIZE (TREE_TYPE (type));
2159 27446 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2160 : return false;
2161 27446 : el_size = tree_to_uhwi (tr_size);
2162 :
2163 27446 : minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
2164 27446 : if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
2165 : return false;
2166 27446 : index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
2167 27446 : if (!integer_zerop (minidx))
2168 563 : index = int_const_binop (PLUS_EXPR, index, minidx);
2169 27446 : *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
2170 : NULL_TREE, NULL_TREE);
2171 27446 : offset = offset % el_size;
2172 27446 : type = TREE_TYPE (type);
2173 27446 : break;
2174 :
2175 29874 : default:
2176 29874 : if (offset != 0)
2177 : return false;
2178 :
2179 29466 : if (exp_type)
2180 : return false;
2181 : else
2182 : return true;
2183 : }
2184 27446 : }
2185 : }
2186 :
2187 : /* Print message to dump file why a variable was rejected. */
2188 :
2189 : static void
2190 14744563 : reject (tree var, const char *msg)
2191 : {
2192 14744563 : 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 14744563 : }
2199 :
2200 : /* Return true if VAR is a candidate for SRA. */
2201 :
2202 : static bool
2203 18881501 : maybe_add_sra_candidate (tree var)
2204 : {
2205 18881501 : tree type = TREE_TYPE (var);
2206 18881501 : const char *msg;
2207 18881501 : tree_node **slot;
2208 :
2209 18881501 : if (!AGGREGATE_TYPE_P (type))
2210 : {
2211 13226631 : reject (var, "not aggregate");
2212 13226631 : return false;
2213 : }
2214 :
2215 5654870 : 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 5433855 : || (TREE_ADDRESSABLE (var)
2219 1497937 : && pt_solution_includes (&cfun->gimple_df->escaped_return, var))
2220 4141062 : || (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 6947663 : && !constant_decl_p (var))
2225 : {
2226 1511272 : reject (var, "needs to live in memory and escapes or global");
2227 1511272 : return false;
2228 : }
2229 4143598 : if (TREE_THIS_VOLATILE (var))
2230 : {
2231 539 : reject (var, "is volatile");
2232 539 : return false;
2233 : }
2234 4143059 : if (!COMPLETE_TYPE_P (type))
2235 : {
2236 0 : reject (var, "has incomplete type");
2237 0 : return false;
2238 : }
2239 4143059 : if (!tree_fits_shwi_p (TYPE_SIZE (type)))
2240 : {
2241 43 : reject (var, "type size not fixed");
2242 43 : return false;
2243 : }
2244 4143016 : if (tree_to_shwi (TYPE_SIZE (type)) == 0)
2245 : {
2246 5822 : reject (var, "type size is zero");
2247 5822 : return false;
2248 : }
2249 4137194 : if (type_internals_preclude_sra_p (type, &msg))
2250 : {
2251 256 : reject (var, msg);
2252 256 : return false;
2253 : }
2254 4136938 : 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 4136938 : (sra_mode == SRA_MODE_EARLY_INTRA
2258 4136938 : && is_va_list_type (type)))
2259 : {
2260 0 : reject (var, "is va_list");
2261 0 : return false;
2262 : }
2263 :
2264 4136938 : bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2265 4136938 : slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2266 4136938 : *slot = var;
2267 :
2268 4136938 : 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 3437811 : find_var_candidates (void)
2283 : {
2284 3437811 : tree var, parm;
2285 3437811 : unsigned int i;
2286 3437811 : bool ret = false;
2287 :
2288 3437811 : for (parm = DECL_ARGUMENTS (current_function_decl);
2289 10656407 : parm;
2290 7218596 : parm = DECL_CHAIN (parm))
2291 7218596 : ret |= maybe_add_sra_candidate (parm);
2292 :
2293 18061748 : FOR_EACH_LOCAL_DECL (cfun, i, var)
2294 : {
2295 11659215 : if (!VAR_P (var))
2296 0 : continue;
2297 :
2298 11659215 : ret |= maybe_add_sra_candidate (var);
2299 : }
2300 :
2301 3437811 : 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 8401617 : path_comparable_for_same_access (tree expr)
2309 : {
2310 14451963 : while (handled_component_p (expr))
2311 : {
2312 6174776 : 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 641921 : if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
2320 : return false;
2321 : }
2322 6050346 : expr = TREE_OPERAND (expr, 0);
2323 : }
2324 :
2325 8277187 : if (TREE_CODE (expr) == MEM_REF)
2326 : {
2327 1003715 : if (!zerop (TREE_OPERAND (expr, 1)))
2328 : return false;
2329 : }
2330 : else
2331 7273472 : gcc_assert (DECL_P (expr));
2332 :
2333 : return true;
2334 : }
2335 :
2336 : /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
2337 : true if the chain of these handled components are exactly the same as EXP2
2338 : and the expression under them is the same DECL or an equivalent MEM_REF.
2339 : The reference picked by compare_access_positions must go to EXP1. */
2340 :
2341 : static bool
2342 4443225 : same_access_path_p (tree exp1, tree exp2)
2343 : {
2344 4443225 : if (TREE_CODE (exp1) != TREE_CODE (exp2))
2345 : {
2346 : /* Special case single-field structures loaded sometimes as the field
2347 : and sometimes as the structure. If the field is of a scalar type,
2348 : compare_access_positions will put it into exp1.
2349 :
2350 : TODO: The gimple register type condition can be removed if teach
2351 : compare_access_positions to put inner types first. */
2352 676209 : if (is_gimple_reg_type (TREE_TYPE (exp1))
2353 455386 : && TREE_CODE (exp1) == COMPONENT_REF
2354 1042229 : && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
2355 366020 : == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
2356 327613 : exp1 = TREE_OPERAND (exp1, 0);
2357 : else
2358 : return false;
2359 : }
2360 :
2361 4094629 : if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF))
2362 : return false;
2363 :
2364 : return true;
2365 : }
2366 :
2367 : /* Return true when either T1 is a type that, when loaded into a register and
2368 : stored back to memory will yield the same bits or when both T1 and T2 are
2369 : compatible. */
2370 :
2371 : static bool
2372 5354589 : types_risk_mangled_binary_repr_p (tree t1, tree t2)
2373 : {
2374 5354589 : if (mode_can_transfer_bits (TYPE_MODE (t1)))
2375 : return false;
2376 :
2377 2687 : return !types_compatible_p (t1, t2);
2378 : }
2379 :
2380 : /* Sort all accesses for the given variable, check for partial overlaps and
2381 : return NULL if there are any. If there are none, pick a representative for
2382 : each combination of offset and size and create a linked list out of them.
2383 : Return the pointer to the first representative and make sure it is the first
2384 : one in the vector of accesses. */
2385 :
2386 : static struct access *
2387 4023892 : sort_and_splice_var_accesses (tree var)
2388 : {
2389 4023892 : int i, j, access_count;
2390 4023892 : struct access *res, **prev_acc_ptr = &res;
2391 4023892 : vec<access_p> *access_vec;
2392 4023892 : bool first = true;
2393 4023892 : HOST_WIDE_INT low = -1, high = 0;
2394 :
2395 4023892 : access_vec = get_base_access_vector (var);
2396 4023892 : if (!access_vec)
2397 : return NULL;
2398 3868502 : access_count = access_vec->length ();
2399 :
2400 : /* Sort by <OFFSET, SIZE>. */
2401 3868502 : access_vec->qsort (compare_access_positions);
2402 :
2403 : i = 0;
2404 13045482 : while (i < access_count)
2405 : {
2406 9181906 : struct access *access = (*access_vec)[i];
2407 9181906 : bool grp_write = access->write;
2408 9181906 : bool grp_read = !access->write;
2409 9181906 : bool grp_scalar_write = access->write
2410 9181906 : && is_gimple_reg_type (access->type);
2411 9181906 : bool grp_scalar_read = !access->write
2412 9181906 : && is_gimple_reg_type (access->type);
2413 9181906 : bool grp_assignment_read = access->grp_assignment_read;
2414 9181906 : bool grp_assignment_write = access->grp_assignment_write;
2415 9181906 : bool multiple_scalar_reads = false;
2416 9181906 : bool grp_partial_lhs = access->grp_partial_lhs;
2417 9181906 : bool first_scalar = is_gimple_reg_type (access->type);
2418 9181906 : bool unscalarizable_region = access->grp_unscalarizable_region;
2419 9181906 : bool grp_same_access_path = access->grp_same_access_path;
2420 9181906 : bool bf_non_full_precision
2421 9181906 : = (INTEGRAL_TYPE_P (access->type)
2422 3075026 : && TYPE_PRECISION (access->type) != access->size
2423 157956 : && TREE_CODE (access->expr) == COMPONENT_REF
2424 9248265 : && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2425 :
2426 9181906 : if (first || access->offset >= high)
2427 : {
2428 4285349 : first = false;
2429 4285349 : low = access->offset;
2430 4285349 : high = access->offset + access->size;
2431 : }
2432 4896557 : else if (access->offset > low && access->offset + access->size > high)
2433 : return NULL;
2434 : else
2435 4895930 : gcc_assert (access->offset >= low
2436 : && access->offset + access->size <= high);
2437 :
2438 9181279 : if (INTEGRAL_TYPE_P (access->type)
2439 3074570 : && TYPE_PRECISION (access->type) != access->size
2440 9338817 : && bitmap_bit_p (passed_by_ref_in_call, DECL_UID (access->base)))
2441 : {
2442 : /* This can lead to performance regressions because we can generate
2443 : excessive zero extensions. */
2444 4299 : if (dump_file && (dump_flags & TDF_DETAILS))
2445 : {
2446 0 : fprintf (dump_file, "Won't scalarize ");
2447 0 : print_generic_expr (dump_file, access->base);
2448 0 : fprintf (dump_file, "(%d), it is passed by reference to a call "
2449 : "and there are accesses with precision not covering "
2450 0 : "their type size.", DECL_UID (access->base));
2451 : }
2452 4299 : return NULL;
2453 : }
2454 :
2455 9176980 : if (grp_same_access_path)
2456 8401617 : grp_same_access_path = path_comparable_for_same_access (access->expr);
2457 :
2458 9176980 : j = i + 1;
2459 14396481 : while (j < access_count)
2460 : {
2461 10532905 : struct access *ac2 = (*access_vec)[j];
2462 10532905 : if (ac2->offset != access->offset || ac2->size != access->size)
2463 : break;
2464 5219501 : if (ac2->write)
2465 : {
2466 1260970 : grp_write = true;
2467 1260970 : grp_scalar_write = (grp_scalar_write
2468 1260970 : || is_gimple_reg_type (ac2->type));
2469 : }
2470 : else
2471 : {
2472 3958531 : grp_read = true;
2473 3958531 : if (is_gimple_reg_type (ac2->type))
2474 : {
2475 1732727 : if (grp_scalar_read)
2476 : multiple_scalar_reads = true;
2477 : else
2478 366722 : grp_scalar_read = true;
2479 : }
2480 : }
2481 5219501 : grp_assignment_read |= ac2->grp_assignment_read;
2482 5219501 : grp_assignment_write |= ac2->grp_assignment_write;
2483 5219501 : grp_partial_lhs |= ac2->grp_partial_lhs;
2484 5219501 : unscalarizable_region |= ac2->grp_unscalarizable_region;
2485 5219501 : relink_to_new_repr (access, ac2);
2486 :
2487 : /* If there are both aggregate-type and scalar-type accesses with
2488 : this combination of size and offset, the comparison function
2489 : should have put the scalars first. */
2490 5219501 : gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
2491 : /* It also prefers integral types to non-integral. However, when the
2492 : precision of the selected type does not span the entire area and
2493 : should also be used for a non-integer (i.e. float), we must not
2494 : let that happen. Normally analyze_access_subtree expands the type
2495 : to cover the entire area but for bit-fields it doesn't. */
2496 5219501 : if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
2497 : {
2498 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2499 : {
2500 0 : fprintf (dump_file, "Cannot scalarize the following access "
2501 : "because insufficient precision integer type was "
2502 : "selected.\n ");
2503 0 : dump_access (dump_file, access, false);
2504 : }
2505 : unscalarizable_region = true;
2506 : }
2507 5219501 : else if (types_risk_mangled_binary_repr_p (access->type, ac2->type))
2508 : {
2509 818 : if (dump_file && (dump_flags & TDF_DETAILS))
2510 : {
2511 0 : fprintf (dump_file, "Cannot scalarize the following access "
2512 : "because data would be held in a mode which is not "
2513 : "guaranteed to preserve all bits.\n ");
2514 0 : dump_access (dump_file, access, false);
2515 : }
2516 : unscalarizable_region = true;
2517 : }
2518 : /* If there the same place is accessed with two incompatible
2519 : aggregate types, trying to base total scalarization on either of
2520 : them can be wrong. */
2521 5219501 : if (!first_scalar && !types_compatible_p (access->type, ac2->type))
2522 448788 : bitmap_set_bit (cannot_scalarize_away_bitmap,
2523 224394 : DECL_UID (access->base));
2524 :
2525 5219501 : if (grp_same_access_path
2526 5219501 : && (!ac2->grp_same_access_path
2527 4443225 : || !same_access_path_p (access->expr, ac2->expr)))
2528 : grp_same_access_path = false;
2529 :
2530 5219501 : ac2->group_representative = access;
2531 5219501 : j++;
2532 : }
2533 :
2534 9176980 : i = j;
2535 :
2536 9176980 : access->group_representative = access;
2537 9176980 : access->grp_write = grp_write;
2538 9176980 : access->grp_read = grp_read;
2539 9176980 : access->grp_scalar_read = grp_scalar_read;
2540 9176980 : access->grp_scalar_write = grp_scalar_write;
2541 9176980 : access->grp_assignment_read = grp_assignment_read;
2542 9176980 : access->grp_assignment_write = grp_assignment_write;
2543 9176980 : access->grp_hint = multiple_scalar_reads && !constant_decl_p (var);
2544 9176980 : access->grp_partial_lhs = grp_partial_lhs;
2545 9176980 : access->grp_unscalarizable_region = unscalarizable_region;
2546 9176980 : access->grp_same_access_path = grp_same_access_path;
2547 :
2548 9176980 : *prev_acc_ptr = access;
2549 9176980 : prev_acc_ptr = &access->next_grp;
2550 : }
2551 :
2552 3863576 : gcc_assert (res == (*access_vec)[0]);
2553 : return res;
2554 : }
2555 :
2556 : /* Create a variable for the given ACCESS which determines the type, name and a
2557 : few other properties. Return the variable declaration and store it also to
2558 : ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2559 : default-definition SSA name on in order to facilitate an uninitialized
2560 : warning. It is used instead of the actual ACCESS type if that is not of a
2561 : gimple register type. */
2562 :
2563 : static tree
2564 3822967 : create_access_replacement (struct access *access, tree reg_type = NULL_TREE)
2565 : {
2566 3822967 : tree repl;
2567 :
2568 3822967 : tree type = access->type;
2569 3822967 : if (reg_type && !is_gimple_reg_type (type))
2570 : type = reg_type;
2571 :
2572 3822967 : if (access->grp_to_be_debug_replaced)
2573 : {
2574 238804 : repl = create_tmp_var_raw (access->type);
2575 238804 : DECL_CONTEXT (repl) = current_function_decl;
2576 : }
2577 : else
2578 : /* Drop any special alignment on the type if it's not on the main
2579 : variant. This avoids issues with weirdo ABIs like AAPCS. */
2580 3584163 : repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type),
2581 3584163 : TYPE_QUALS (type)), "SR");
2582 3822967 : if (access->grp_partial_lhs
2583 3822967 : && is_gimple_reg_type (type))
2584 664 : DECL_NOT_GIMPLE_REG_P (repl) = 1;
2585 :
2586 3822967 : DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2587 3822967 : DECL_ARTIFICIAL (repl) = 1;
2588 3822967 : DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2589 :
2590 3822967 : if (DECL_NAME (access->base)
2591 3822967 : && ((!DECL_IGNORED_P (access->base) && !DECL_ARTIFICIAL (access->base))
2592 1865714 : || (VAR_P (access->base) && DECL_NONLOCAL_FRAME (access->base))))
2593 : {
2594 1014548 : char *pretty_name = make_fancy_name (access->expr);
2595 1014548 : tree debug_expr = unshare_expr_without_location (access->expr), d;
2596 1014548 : bool fail = false;
2597 :
2598 1014548 : DECL_NAME (repl) = get_identifier (pretty_name);
2599 1014548 : DECL_NAMELESS (repl) = 1;
2600 1014548 : obstack_free (&name_obstack, pretty_name);
2601 :
2602 : /* Get rid of any SSA_NAMEs embedded in debug_expr,
2603 : as DECL_DEBUG_EXPR isn't considered when looking for still
2604 : used SSA_NAMEs and thus they could be freed. All debug info
2605 : generation cares is whether something is constant or variable
2606 : and that get_ref_base_and_extent works properly on the
2607 : expression. It cannot handle accesses at a non-constant offset
2608 : though, so just give up in those cases. */
2609 1309986 : for (d = debug_expr;
2610 3554096 : !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2611 1309986 : d = TREE_OPERAND (d, 0))
2612 1309986 : switch (TREE_CODE (d))
2613 : {
2614 58987 : case ARRAY_REF:
2615 58987 : case ARRAY_RANGE_REF:
2616 58987 : if (TREE_OPERAND (d, 1)
2617 58987 : && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2618 : fail = true;
2619 58987 : if (TREE_OPERAND (d, 3)
2620 58987 : && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2621 : fail = true;
2622 : /* FALLTHRU */
2623 1092511 : case COMPONENT_REF:
2624 1092511 : if (TREE_OPERAND (d, 2)
2625 1092511 : && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2626 : fail = true;
2627 : break;
2628 215135 : case MEM_REF:
2629 215135 : if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2630 : fail = true;
2631 : else
2632 215135 : d = TREE_OPERAND (d, 0);
2633 : break;
2634 : default:
2635 : break;
2636 : }
2637 1014548 : if (!fail)
2638 : {
2639 1014427 : SET_DECL_DEBUG_EXPR (repl, debug_expr);
2640 1014427 : DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2641 : }
2642 1014548 : if (access->grp_no_warning)
2643 380 : suppress_warning (repl /* Be more selective! */);
2644 : else
2645 1014168 : copy_warning (repl, access->base);
2646 : }
2647 : else
2648 2808419 : suppress_warning (repl /* Be more selective! */);
2649 :
2650 3822967 : if (dump_file)
2651 : {
2652 145 : if (access->grp_to_be_debug_replaced)
2653 : {
2654 4 : fprintf (dump_file, "Created a debug-only replacement for ");
2655 4 : print_generic_expr (dump_file, access->base);
2656 4 : fprintf (dump_file, " offset: %u, size: %u\n",
2657 4 : (unsigned) access->offset, (unsigned) access->size);
2658 : }
2659 : else
2660 : {
2661 141 : fprintf (dump_file, "Created a replacement for ");
2662 141 : print_generic_expr (dump_file, access->base);
2663 141 : fprintf (dump_file, " offset: %u, size: %u: ",
2664 141 : (unsigned) access->offset, (unsigned) access->size);
2665 141 : print_generic_expr (dump_file, repl, TDF_UID);
2666 141 : fprintf (dump_file, "\n");
2667 : }
2668 : }
2669 3822967 : sra_stats.replacements++;
2670 :
2671 3822967 : return repl;
2672 : }
2673 :
2674 : /* Return ACCESS scalar replacement, which must exist. */
2675 :
2676 : static inline tree
2677 13108506 : get_access_replacement (struct access *access)
2678 : {
2679 13108506 : gcc_checking_assert (access->replacement_decl);
2680 13108506 : return access->replacement_decl;
2681 : }
2682 :
2683 :
2684 : /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2685 : linked list along the way. Stop when *ACCESS is NULL or the access pointed
2686 : to it is not "within" the root. Return false iff some accesses partially
2687 : overlap. */
2688 :
2689 : static bool
2690 9152938 : build_access_subtree (struct access **access)
2691 : {
2692 9152938 : struct access *root = *access, *last_child = NULL;
2693 9152938 : HOST_WIDE_INT limit = root->offset + root->size;
2694 :
2695 9152938 : *access = (*access)->next_grp;
2696 14022646 : while (*access && (*access)->offset + (*access)->size <= limit)
2697 : {
2698 4872532 : if (!last_child)
2699 1959942 : root->first_child = *access;
2700 : else
2701 2912590 : last_child->next_sibling = *access;
2702 4872532 : last_child = *access;
2703 4872532 : (*access)->parent = root;
2704 4872532 : (*access)->grp_write |= root->grp_write;
2705 :
2706 4872532 : if (!build_access_subtree (access))
2707 : return false;
2708 : }
2709 :
2710 9150114 : if (*access && (*access)->offset < limit)
2711 : return false;
2712 :
2713 : return true;
2714 : }
2715 :
2716 : /* Build a tree of access representatives, ACCESS is the pointer to the first
2717 : one, others are linked in a list by the next_grp field. Return false iff
2718 : some accesses partially overlap. */
2719 :
2720 : static bool
2721 3863576 : build_access_trees (struct access *access)
2722 : {
2723 8141339 : while (access)
2724 : {
2725 4280406 : struct access *root = access;
2726 :
2727 4280406 : if (!build_access_subtree (&access))
2728 : return false;
2729 4277763 : root->next_grp = access;
2730 : }
2731 : return true;
2732 : }
2733 :
2734 : /* Traverse the access forest where ROOT is the first root and verify that
2735 : various important invariants hold true. */
2736 :
2737 : DEBUG_FUNCTION void
2738 3860933 : verify_sra_access_forest (struct access *root)
2739 : {
2740 3860933 : struct access *access = root;
2741 3860933 : tree first_base = root->base;
2742 3860933 : gcc_assert (DECL_P (first_base));
2743 11057994 : do
2744 : {
2745 11057994 : gcc_assert (access->base == first_base);
2746 11057994 : if (access->parent)
2747 6780246 : gcc_assert (access->offset >= access->parent->offset
2748 : && access->size <= access->parent->size);
2749 11057994 : if (access->next_sibling)
2750 3992645 : gcc_assert (access->next_sibling->offset
2751 : >= access->offset + access->size);
2752 :
2753 11057994 : poly_int64 poffset, psize, pmax_size;
2754 11057994 : bool reverse;
2755 11057994 : tree base = get_ref_base_and_extent (access->expr, &poffset, &psize,
2756 : &pmax_size, &reverse);
2757 11057994 : HOST_WIDE_INT offset, size, max_size;
2758 11057994 : if (!poffset.is_constant (&offset)
2759 11057994 : || !psize.is_constant (&size)
2760 11057994 : || !pmax_size.is_constant (&max_size))
2761 : gcc_unreachable ();
2762 11057994 : gcc_assert (base == first_base);
2763 11057994 : gcc_assert (offset == access->offset);
2764 11057994 : gcc_assert (access->grp_unscalarizable_region
2765 : || access->grp_total_scalarization
2766 : || size == max_size);
2767 11057994 : gcc_assert (access->grp_unscalarizable_region
2768 : || !is_gimple_reg_type (access->type)
2769 : || size == access->size);
2770 11057994 : gcc_assert (reverse == access->reverse);
2771 :
2772 11057994 : if (access->first_child)
2773 : {
2774 2787601 : gcc_assert (access->first_child->parent == access);
2775 : access = access->first_child;
2776 : }
2777 8270393 : else if (access->next_sibling)
2778 : {
2779 3812229 : gcc_assert (access->next_sibling->parent == access->parent);
2780 : access = access->next_sibling;
2781 : }
2782 : else
2783 : {
2784 7245765 : while (access->parent && !access->next_sibling)
2785 : access = access->parent;
2786 4458164 : if (access->next_sibling)
2787 : access = access->next_sibling;
2788 : else
2789 : {
2790 4277748 : gcc_assert (access == root);
2791 4277748 : root = root->next_grp;
2792 4277748 : access = root;
2793 : }
2794 : }
2795 : }
2796 11057994 : while (access);
2797 3860933 : }
2798 :
2799 : /* Verify access forests of all candidates with accesses by calling
2800 : verify_access_forest on each on them. */
2801 :
2802 : DEBUG_FUNCTION void
2803 709147 : verify_all_sra_access_forests (void)
2804 : {
2805 709147 : bitmap_iterator bi;
2806 709147 : unsigned i;
2807 4570080 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2808 : {
2809 3860933 : tree var = candidate (i);
2810 3860933 : struct access *access = get_first_repr_for_decl (var);
2811 3860933 : if (access)
2812 : {
2813 3860933 : gcc_assert (access->base == var);
2814 3860933 : verify_sra_access_forest (access);
2815 : }
2816 : }
2817 709147 : }
2818 :
2819 : /* Return true if expr contains some ARRAY_REFs into a variable bounded
2820 : array. */
2821 :
2822 : static bool
2823 10674458 : expr_with_var_bounded_array_refs_p (tree expr)
2824 : {
2825 20109882 : while (handled_component_p (expr))
2826 : {
2827 9435424 : if (TREE_CODE (expr) == ARRAY_REF
2828 9435424 : && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2829 : return true;
2830 9435424 : expr = TREE_OPERAND (expr, 0);
2831 : }
2832 : return false;
2833 : }
2834 :
2835 : /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2836 : both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2837 : is set, we are totally scalarizing the aggregate. Also set all sorts of
2838 : access flags appropriately along the way, notably always set grp_read and
2839 : grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2840 : true.
2841 :
2842 : Creating a replacement for a scalar access is considered beneficial if its
2843 : grp_hint ot TOTALLY is set (this means either that there is more than one
2844 : direct read access or that we are attempting total scalarization) or
2845 : according to the following table:
2846 :
2847 : Access written to through a scalar type (once or more times)
2848 : |
2849 : | Written to in an assignment statement
2850 : | |
2851 : | | Access read as scalar _once_
2852 : | | |
2853 : | | | Read in an assignment statement
2854 : | | | |
2855 : | | | | Scalarize Comment
2856 : -----------------------------------------------------------------------------
2857 : 0 0 0 0 No access for the scalar
2858 : 0 0 0 1 No access for the scalar
2859 : 0 0 1 0 No Single read - won't help
2860 : 0 0 1 1 No The same case
2861 : 0 1 0 0 No access for the scalar
2862 : 0 1 0 1 No access for the scalar
2863 : 0 1 1 0 Yes s = *g; return s.i;
2864 : 0 1 1 1 Yes The same case as above
2865 : 1 0 0 0 No Won't help
2866 : 1 0 0 1 Yes s.i = 1; *g = s;
2867 : 1 0 1 0 Yes s.i = 5; g = s.i;
2868 : 1 0 1 1 Yes The same case as above
2869 : 1 1 0 0 No Won't help.
2870 : 1 1 0 1 Yes s.i = 1; *g = s;
2871 : 1 1 1 0 Yes s = *g; return s.i;
2872 : 1 1 1 1 Yes Any of the above yeses */
2873 :
2874 : static bool
2875 11057994 : analyze_access_subtree (struct access *root, struct access *parent,
2876 : bool allow_replacements, bool totally)
2877 : {
2878 11057994 : struct access *child;
2879 11057994 : HOST_WIDE_INT limit = root->offset + root->size;
2880 11057994 : HOST_WIDE_INT covered_to = root->offset;
2881 11057994 : bool scalar = is_gimple_reg_type (root->type);
2882 11057994 : bool hole = false, sth_created = false;
2883 :
2884 11057994 : if (parent)
2885 : {
2886 6780246 : if (parent->grp_read)
2887 6037385 : root->grp_read = 1;
2888 6780246 : if (parent->grp_assignment_read)
2889 2851824 : root->grp_assignment_read = 1;
2890 6780246 : if (parent->grp_write)
2891 3999405 : root->grp_write = 1;
2892 6780246 : if (parent->grp_assignment_write)
2893 2905802 : root->grp_assignment_write = 1;
2894 6780246 : if (!parent->grp_same_access_path)
2895 1117437 : root->grp_same_access_path = 0;
2896 : }
2897 :
2898 11057994 : if (root->grp_unscalarizable_region)
2899 : allow_replacements = false;
2900 :
2901 10932494 : if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2902 : allow_replacements = false;
2903 :
2904 11057994 : if (!totally && root->grp_result_of_prop_from_lhs)
2905 11057994 : allow_replacements = false;
2906 :
2907 17838240 : for (child = root->first_child; child; child = child->next_sibling)
2908 : {
2909 6780246 : if (totally)
2910 1813576 : covered_to = child->offset;
2911 : else
2912 4966670 : hole |= covered_to < child->offset;
2913 6780246 : sth_created |= analyze_access_subtree (child, root,
2914 6780246 : allow_replacements && !scalar
2915 6780246 : && !root->grp_partial_lhs,
2916 : totally);
2917 :
2918 6780246 : root->grp_unscalarized_data |= child->grp_unscalarized_data;
2919 6780246 : if (child->grp_covered)
2920 3236976 : covered_to += child->size;
2921 : else
2922 : hole = true;
2923 6780246 : if (totally && !hole)
2924 1812804 : covered_to = limit;
2925 : }
2926 :
2927 11057994 : if (allow_replacements && scalar && !root->first_child
2928 6652575 : && (totally || !root->grp_total_scalarization)
2929 : && (totally
2930 4942144 : || root->grp_hint
2931 4159905 : || ((root->grp_scalar_read || root->grp_assignment_read)
2932 1442611 : && (root->grp_scalar_write || root->grp_assignment_write))))
2933 : {
2934 : /* Always create access replacements that cover the whole access.
2935 : For integral types this means the precision has to match.
2936 : Avoid assumptions based on the integral type kind, too. */
2937 3583619 : if (INTEGRAL_TYPE_P (root->type)
2938 1605144 : && ((TREE_CODE (root->type) != INTEGER_TYPE
2939 1605144 : && TREE_CODE (root->type) != BITINT_TYPE)
2940 1545287 : || TYPE_PRECISION (root->type) != root->size)
2941 : /* But leave bitfield accesses alone. */
2942 3643482 : && (TREE_CODE (root->expr) != COMPONENT_REF
2943 58962 : || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2944 : {
2945 59582 : tree rt = root->type;
2946 59582 : gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2947 : && (root->size % BITS_PER_UNIT) == 0);
2948 59582 : if (TREE_CODE (root->type) == BITINT_TYPE)
2949 6 : root->type = build_bitint_type (root->size, TYPE_UNSIGNED (rt));
2950 : else
2951 59576 : root->type = build_nonstandard_integer_type (root->size,
2952 59576 : TYPE_UNSIGNED (rt));
2953 119164 : root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2954 59582 : root->offset, root->reverse,
2955 : root->type, NULL, false);
2956 :
2957 59582 : if (dump_file && (dump_flags & TDF_DETAILS))
2958 : {
2959 0 : fprintf (dump_file, "Changing the type of a replacement for ");
2960 0 : print_generic_expr (dump_file, root->base);
2961 0 : fprintf (dump_file, " offset: %u, size: %u ",
2962 0 : (unsigned) root->offset, (unsigned) root->size);
2963 0 : fprintf (dump_file, " to an integer.\n");
2964 : }
2965 : }
2966 :
2967 3583619 : root->grp_to_be_replaced = 1;
2968 3583619 : root->replacement_decl = create_access_replacement (root);
2969 3583619 : sth_created = true;
2970 3583619 : hole = false;
2971 : }
2972 : else
2973 : {
2974 7474375 : if (allow_replacements
2975 3078316 : && scalar && !root->first_child
2976 3068956 : && !root->grp_total_scalarization
2977 3068816 : && (root->grp_scalar_write || root->grp_assignment_write)
2978 10191669 : && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2979 2717294 : DECL_UID (root->base)))
2980 : {
2981 454214 : gcc_checking_assert (!root->grp_scalar_read
2982 : && !root->grp_assignment_read);
2983 454214 : sth_created = true;
2984 454214 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2985 : {
2986 238804 : root->grp_to_be_debug_replaced = 1;
2987 238804 : root->replacement_decl = create_access_replacement (root);
2988 : }
2989 : }
2990 :
2991 7474375 : if (covered_to < limit)
2992 6266204 : hole = true;
2993 7474375 : if (scalar || !allow_replacements)
2994 4047749 : root->grp_total_scalarization = 0;
2995 : }
2996 :
2997 11057994 : if (!hole)
2998 4791570 : root->grp_covered = 1;
2999 6266424 : else if (root->grp_write || comes_initialized_p (root->base))
3000 5508389 : root->grp_unscalarized_data = 1; /* not covered and written to */
3001 11057994 : return sth_created;
3002 : }
3003 :
3004 : /* Analyze all access trees linked by next_grp by the means of
3005 : analyze_access_subtree. */
3006 : static bool
3007 3860933 : analyze_access_trees (struct access *access)
3008 : {
3009 3860933 : bool ret = false;
3010 :
3011 8138681 : while (access)
3012 : {
3013 4277748 : if (analyze_access_subtree (access, NULL, true,
3014 4277748 : access->grp_total_scalarization))
3015 2103314 : ret = true;
3016 4277748 : access = access->next_grp;
3017 : }
3018 :
3019 3860933 : return ret;
3020 : }
3021 :
3022 : /* Return true iff a potential new child of ACC at offset OFFSET and with size
3023 : SIZE would conflict with an already existing one. If exactly such a child
3024 : already exists in ACC, store a pointer to it in EXACT_MATCH. */
3025 :
3026 : static bool
3027 6923494 : child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset,
3028 : HOST_WIDE_INT size, struct access **exact_match)
3029 : {
3030 6923494 : struct access *child;
3031 :
3032 12142991 : for (child = acc->first_child; child; child = child->next_sibling)
3033 : {
3034 10709696 : if (child->offset == norm_offset && child->size == size)
3035 : {
3036 5444470 : *exact_match = child;
3037 5444470 : return true;
3038 : }
3039 :
3040 5265226 : if (child->offset < norm_offset + size
3041 5191094 : && child->offset + child->size > norm_offset)
3042 : return true;
3043 : }
3044 :
3045 : return false;
3046 : }
3047 :
3048 : /* Create a new child access of PARENT, with all properties just like MODEL
3049 : except for its offset and with its grp_write false and grp_read true.
3050 : Return the new access or NULL if it cannot be created. Note that this
3051 : access is created long after all splicing and sorting, it's not located in
3052 : any access vector and is automatically a representative of its group. Set
3053 : the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
3054 :
3055 : static struct access *
3056 1426194 : create_artificial_child_access (struct access *parent, struct access *model,
3057 : HOST_WIDE_INT new_offset,
3058 : bool set_grp_read, bool set_grp_write)
3059 : {
3060 1426194 : struct access **child;
3061 1426194 : tree expr = parent->base;
3062 :
3063 1426194 : gcc_assert (!model->grp_unscalarizable_region);
3064 :
3065 1426194 : struct access *access = access_pool.allocate ();
3066 1426194 : memset (access, 0, sizeof (struct access));
3067 1426194 : if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
3068 : model->type))
3069 : {
3070 28073 : access->grp_no_warning = true;
3071 28073 : expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
3072 : new_offset, model, NULL, false);
3073 : }
3074 :
3075 1426194 : access->base = parent->base;
3076 1426194 : access->expr = expr;
3077 1426194 : access->offset = new_offset;
3078 1426194 : access->size = model->size;
3079 1426194 : access->type = model->type;
3080 1426194 : access->parent = parent;
3081 1426194 : access->grp_read = set_grp_read;
3082 1426194 : access->grp_write = set_grp_write;
3083 1426194 : access->reverse = model->reverse;
3084 :
3085 1426194 : child = &parent->first_child;
3086 2614074 : while (*child && (*child)->offset < new_offset)
3087 1187880 : child = &(*child)->next_sibling;
3088 :
3089 1426194 : access->next_sibling = *child;
3090 1426194 : *child = access;
3091 :
3092 1426194 : return access;
3093 : }
3094 :
3095 :
3096 : /* Beginning with ACCESS, traverse its whole access subtree and mark all
3097 : sub-trees as written to. If any of them has not been marked so previously
3098 : and has assignment links leading from it, re-enqueue it. */
3099 :
3100 : static void
3101 1600525 : subtree_mark_written_and_rhs_enqueue (struct access *access)
3102 : {
3103 1600525 : if (access->grp_write)
3104 : return;
3105 1520467 : access->grp_write = true;
3106 1520467 : add_access_to_rhs_work_queue (access);
3107 :
3108 1520467 : struct access *child;
3109 2156714 : for (child = access->first_child; child; child = child->next_sibling)
3110 636247 : subtree_mark_written_and_rhs_enqueue (child);
3111 : }
3112 :
3113 : /* If there is still budget to create a propagation access for DECL, return
3114 : true and decrement the budget. Otherwise return false. */
3115 :
3116 : static bool
3117 1430328 : budget_for_propagation_access (tree decl)
3118 : {
3119 1430328 : unsigned b, *p = propagation_budget->get (decl);
3120 1430328 : if (p)
3121 862267 : b = *p;
3122 : else
3123 568061 : b = param_sra_max_propagations;
3124 :
3125 1430328 : if (b == 0)
3126 : return false;
3127 1426200 : b--;
3128 :
3129 1426200 : if (b == 0 && dump_file && (dump_flags & TDF_DETAILS))
3130 : {
3131 0 : fprintf (dump_file, "The propagation budget of ");
3132 0 : print_generic_expr (dump_file, decl);
3133 0 : fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl));
3134 : }
3135 1426200 : propagation_budget->put (decl, b);
3136 1426200 : return true;
3137 : }
3138 :
3139 : /* Return true if ACC or any of its subaccesses has grp_child set. */
3140 :
3141 : static bool
3142 2544 : access_or_its_child_written (struct access *acc)
3143 : {
3144 2544 : if (acc->grp_write)
3145 : return true;
3146 2387 : for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling)
3147 615 : if (access_or_its_child_written (sub))
3148 : return true;
3149 : return false;
3150 : }
3151 :
3152 : /* Propagate subaccesses and grp_write flags of RACC across an assignment link
3153 : to LACC. Enqueue sub-accesses as necessary so that the write flag is
3154 : propagated transitively. Return true if anything changed. Additionally, if
3155 : RACC is a scalar access but LACC is not, change the type of the latter, if
3156 : possible. */
3157 :
3158 : static bool
3159 3583414 : propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc)
3160 : {
3161 3583414 : struct access *rchild;
3162 3583414 : HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
3163 3583414 : bool ret = false;
3164 :
3165 : /* IF the LHS is still not marked as being written to, we only need to do so
3166 : if the RHS at this level actually was. */
3167 3583414 : if (!lacc->grp_write)
3168 : {
3169 1617404 : gcc_checking_assert (!comes_initialized_p (racc->base));
3170 1617404 : if (racc->grp_write)
3171 : {
3172 767307 : subtree_mark_written_and_rhs_enqueue (lacc);
3173 767307 : ret = true;
3174 : }
3175 : }
3176 :
3177 3583414 : if (is_gimple_reg_type (lacc->type)
3178 2811976 : || lacc->grp_unscalarizable_region
3179 6394777 : || racc->grp_unscalarizable_region)
3180 : {
3181 773109 : if (!lacc->grp_write)
3182 : {
3183 17357 : ret = true;
3184 17357 : subtree_mark_written_and_rhs_enqueue (lacc);
3185 : }
3186 773109 : return ret;
3187 : }
3188 :
3189 2810305 : if (is_gimple_reg_type (racc->type))
3190 : {
3191 135570 : if (!lacc->grp_write)
3192 : {
3193 2438 : ret = true;
3194 2438 : subtree_mark_written_and_rhs_enqueue (lacc);
3195 : }
3196 135570 : if (!lacc->first_child
3197 135390 : && !racc->first_child
3198 270658 : && !types_risk_mangled_binary_repr_p (racc->type, lacc->type))
3199 : {
3200 : /* We are about to change the access type from aggregate to scalar,
3201 : so we need to put the reverse flag onto the access, if any. */
3202 135088 : const bool reverse
3203 135088 : = TYPE_REVERSE_STORAGE_ORDER (lacc->type)
3204 1 : && !POINTER_TYPE_P (racc->type)
3205 135088 : && !VECTOR_TYPE_P (racc->type);
3206 135088 : tree t = lacc->base;
3207 :
3208 135088 : lacc->type = racc->type;
3209 135088 : if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
3210 : lacc->offset, racc->type))
3211 : {
3212 134840 : lacc->expr = t;
3213 134840 : lacc->grp_same_access_path = true;
3214 : }
3215 : else
3216 : {
3217 248 : lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
3218 : lacc->base, lacc->offset,
3219 : racc, NULL, false);
3220 248 : if (TREE_CODE (lacc->expr) == MEM_REF)
3221 248 : REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse;
3222 248 : lacc->grp_no_warning = true;
3223 248 : lacc->grp_same_access_path = false;
3224 : }
3225 135088 : lacc->reverse = reverse;
3226 : }
3227 135570 : return ret;
3228 : }
3229 :
3230 5776321 : for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
3231 : {
3232 3101586 : struct access *new_acc = NULL;
3233 3101586 : HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
3234 :
3235 3101586 : if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size,
3236 : &new_acc))
3237 : {
3238 2550736 : if (new_acc)
3239 : {
3240 2523291 : if (!new_acc->grp_write && rchild->grp_write)
3241 : {
3242 168874 : gcc_assert (!lacc->grp_write);
3243 168874 : subtree_mark_written_and_rhs_enqueue (new_acc);
3244 168874 : ret = true;
3245 : }
3246 :
3247 2523291 : rchild->grp_hint = 1;
3248 2523291 : new_acc->grp_hint |= new_acc->grp_read;
3249 2523291 : if (rchild->first_child
3250 2523291 : && propagate_subaccesses_from_rhs (new_acc, rchild))
3251 : {
3252 1275 : ret = 1;
3253 1275 : add_access_to_rhs_work_queue (new_acc);
3254 : }
3255 : }
3256 : else
3257 : {
3258 27445 : if (!lacc->grp_write)
3259 : {
3260 7075 : ret = true;
3261 7075 : subtree_mark_written_and_rhs_enqueue (lacc);
3262 : }
3263 : }
3264 2557805 : continue;
3265 : }
3266 :
3267 557919 : if (rchild->grp_unscalarizable_region
3268 549733 : || (rchild->size % BITS_PER_UNIT) != 0
3269 1098733 : || !budget_for_propagation_access (lacc->base))
3270 : {
3271 7069 : if (!lacc->grp_write && access_or_its_child_written (rchild))
3272 : {
3273 739 : ret = true;
3274 739 : subtree_mark_written_and_rhs_enqueue (lacc);
3275 : }
3276 7069 : continue;
3277 : }
3278 :
3279 543781 : rchild->grp_hint = 1;
3280 : /* Because get_ref_base_and_extent always includes padding in size for
3281 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3282 : type, we might be actually attempting to here to create a child of the
3283 : same type as the parent. */
3284 543781 : if (!types_compatible_p (lacc->type, rchild->type))
3285 543781 : new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
3286 : false,
3287 543781 : (lacc->grp_write
3288 543781 : || rchild->grp_write));
3289 : else
3290 0 : new_acc = lacc;
3291 543781 : gcc_checking_assert (new_acc);
3292 543781 : if (racc->first_child)
3293 543781 : propagate_subaccesses_from_rhs (new_acc, rchild);
3294 :
3295 543781 : add_access_to_rhs_work_queue (lacc);
3296 543781 : ret = true;
3297 : }
3298 :
3299 : return ret;
3300 : }
3301 :
3302 : /* Propagate subaccesses of LACC across an assignment link to RACC if they
3303 : should inhibit total scalarization of the corresponding area. No flags are
3304 : being propagated in the process. Return true if anything changed. */
3305 :
3306 : static bool
3307 6090940 : propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc)
3308 : {
3309 6090940 : if (is_gimple_reg_type (racc->type)
3310 2148719 : || lacc->grp_unscalarizable_region
3311 8238640 : || racc->grp_unscalarizable_region)
3312 : return false;
3313 :
3314 : /* TODO: Do we want set some new racc flag to stop potential total
3315 : scalarization if lacc is a scalar access (and none fo the two have
3316 : children)? */
3317 :
3318 2147681 : bool ret = false;
3319 2147681 : HOST_WIDE_INT norm_delta = racc->offset - lacc->offset;
3320 2147681 : for (struct access *lchild = lacc->first_child;
3321 5975131 : lchild;
3322 3827450 : lchild = lchild->next_sibling)
3323 : {
3324 3827450 : struct access *matching_acc = NULL;
3325 3827450 : HOST_WIDE_INT norm_offset = lchild->offset + norm_delta;
3326 :
3327 6772481 : if (lchild->grp_unscalarizable_region
3328 3822806 : || (lchild->size % BITS_PER_UNIT) != 0
3329 3821908 : || child_would_conflict_in_acc (racc, norm_offset, lchild->size,
3330 : &matching_acc)
3331 4709895 : || !budget_for_propagation_access (racc->base))
3332 : {
3333 2945031 : if (matching_acc
3334 2945031 : && propagate_subaccesses_from_lhs (lchild, matching_acc))
3335 195 : add_access_to_lhs_work_queue (matching_acc);
3336 2945031 : continue;
3337 : }
3338 :
3339 : /* Because get_ref_base_and_extent always includes padding in size for
3340 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3341 : type, we might be actually attempting to here to create a child of the
3342 : same type as the parent. */
3343 882419 : if (!types_compatible_p (racc->type, lchild->type))
3344 : {
3345 882413 : struct access *new_acc
3346 882413 : = create_artificial_child_access (racc, lchild, norm_offset,
3347 : true, false);
3348 882413 : new_acc->grp_result_of_prop_from_lhs = 1;
3349 882413 : propagate_subaccesses_from_lhs (lchild, new_acc);
3350 : }
3351 : else
3352 6 : propagate_subaccesses_from_lhs (lchild, racc);
3353 882419 : ret = true;
3354 : }
3355 : return ret;
3356 : }
3357 :
3358 : /* Propagate all subaccesses across assignment links. */
3359 :
3360 : static void
3361 709147 : propagate_all_subaccesses (void)
3362 : {
3363 709147 : propagation_budget = new hash_map<tree, unsigned>;
3364 2227035 : while (rhs_work_queue_head)
3365 : {
3366 1517888 : struct access *racc = pop_access_from_rhs_work_queue ();
3367 1517888 : struct assign_link *link;
3368 :
3369 1517888 : if (racc->group_representative)
3370 1517190 : racc= racc->group_representative;
3371 1517888 : gcc_assert (racc->first_rhs_link);
3372 :
3373 4546451 : for (link = racc->first_rhs_link; link; link = link->next_rhs)
3374 : {
3375 3028563 : struct access *lacc = link->lacc;
3376 :
3377 3028563 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3378 6947 : continue;
3379 3021616 : lacc = lacc->group_representative;
3380 :
3381 3021616 : bool reque_parents = false;
3382 3021616 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3383 : {
3384 1716 : if (!lacc->grp_write)
3385 : {
3386 488 : subtree_mark_written_and_rhs_enqueue (lacc);
3387 488 : reque_parents = true;
3388 : }
3389 : }
3390 3019900 : else if (propagate_subaccesses_from_rhs (lacc, racc))
3391 : reque_parents = true;
3392 :
3393 : if (reque_parents)
3394 1228047 : do
3395 : {
3396 1228047 : add_access_to_rhs_work_queue (lacc);
3397 1228047 : lacc = lacc->parent;
3398 : }
3399 1228047 : while (lacc);
3400 : }
3401 : }
3402 :
3403 2021397 : while (lhs_work_queue_head)
3404 : {
3405 1312250 : struct access *lacc = pop_access_from_lhs_work_queue ();
3406 1312250 : struct assign_link *link;
3407 :
3408 1312250 : if (lacc->group_representative)
3409 1309047 : lacc = lacc->group_representative;
3410 1312250 : gcc_assert (lacc->first_lhs_link);
3411 :
3412 1312250 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3413 4037 : continue;
3414 :
3415 3596292 : for (link = lacc->first_lhs_link; link; link = link->next_lhs)
3416 : {
3417 2288079 : struct access *racc = link->racc;
3418 :
3419 2288079 : if (racc->group_representative)
3420 2287546 : racc = racc->group_representative;
3421 2288079 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3422 737 : continue;
3423 2287342 : if (propagate_subaccesses_from_lhs (lacc, racc))
3424 351923 : add_access_to_lhs_work_queue (racc);
3425 : }
3426 : }
3427 1418294 : delete propagation_budget;
3428 709147 : }
3429 :
3430 : /* Return true if the forest beginning with ROOT does not contain
3431 : unscalarizable regions or non-byte aligned accesses. */
3432 :
3433 : static bool
3434 742205 : can_totally_scalarize_forest_p (struct access *root)
3435 : {
3436 742205 : struct access *access = root;
3437 2156279 : do
3438 : {
3439 2156279 : if (access->grp_unscalarizable_region
3440 2154293 : || (access->offset % BITS_PER_UNIT) != 0
3441 2153935 : || (access->size % BITS_PER_UNIT) != 0
3442 4308014 : || (is_gimple_reg_type (access->type)
3443 1413025 : && access->first_child))
3444 : return false;
3445 :
3446 2151452 : if (access->first_child)
3447 : access = access->first_child;
3448 1530612 : else if (access->next_sibling)
3449 : access = access->next_sibling;
3450 : else
3451 : {
3452 1430933 : while (access->parent && !access->next_sibling)
3453 : access = access->parent;
3454 813438 : if (access->next_sibling)
3455 : access = access->next_sibling;
3456 : else
3457 : {
3458 760415 : gcc_assert (access == root);
3459 760415 : root = root->next_grp;
3460 760415 : access = root;
3461 : }
3462 : }
3463 : }
3464 2151452 : while (access);
3465 : return true;
3466 : }
3467 :
3468 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3469 : reference EXPR for total scalarization purposes and mark it as such. Within
3470 : the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3471 :
3472 : static struct access *
3473 485706 : create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos,
3474 : HOST_WIDE_INT size, tree type, tree expr,
3475 : struct access **ptr,
3476 : struct access *next_sibling)
3477 : {
3478 485706 : struct access *access = access_pool.allocate ();
3479 485706 : memset (access, 0, sizeof (struct access));
3480 485706 : access->base = parent->base;
3481 485706 : access->offset = pos;
3482 485706 : access->size = size;
3483 485706 : access->expr = expr;
3484 485706 : access->type = type;
3485 485706 : access->parent = parent;
3486 485706 : access->grp_write = parent->grp_write;
3487 485706 : access->grp_total_scalarization = 1;
3488 485706 : access->grp_hint = 1;
3489 485706 : access->grp_same_access_path = 0;
3490 485706 : access->reverse = reverse_storage_order_for_component_p (expr);
3491 :
3492 485706 : access->next_sibling = next_sibling;
3493 485706 : *ptr = access;
3494 485706 : return access;
3495 : }
3496 :
3497 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3498 : reference EXPR for total scalarization purposes and mark it as such, link it
3499 : at *PTR and reshape the tree so that those elements at *PTR and their
3500 : siblings which fall within the part described by POS and SIZE are moved to
3501 : be children of the new access. If a partial overlap is detected, return
3502 : NULL. */
3503 :
3504 : static struct access *
3505 485706 : create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos,
3506 : HOST_WIDE_INT size, tree type, tree expr,
3507 : struct access **ptr)
3508 : {
3509 485706 : struct access **p = ptr;
3510 :
3511 672352 : while (*p && (*p)->offset < pos + size)
3512 : {
3513 186646 : if ((*p)->offset + (*p)->size > pos + size)
3514 : return NULL;
3515 186646 : p = &(*p)->next_sibling;
3516 : }
3517 :
3518 485706 : struct access *next_child = *ptr;
3519 485706 : struct access *new_acc
3520 485706 : = create_total_scalarization_access (parent, pos, size, type, expr,
3521 : ptr, *p);
3522 485706 : if (p != ptr)
3523 : {
3524 76172 : new_acc->first_child = next_child;
3525 76172 : *p = NULL;
3526 262818 : for (struct access *a = next_child; a; a = a->next_sibling)
3527 186646 : a->parent = new_acc;
3528 : }
3529 : return new_acc;
3530 : }
3531 :
3532 : static bool totally_scalarize_subtree (struct access *root);
3533 :
3534 : /* Return true if INNER is either the same type as OUTER or if it is the type
3535 : of a record field in OUTER at offset zero, possibly in nested
3536 : sub-records. */
3537 :
3538 : static bool
3539 180502 : access_and_field_type_match_p (tree outer, tree inner)
3540 : {
3541 180502 : if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner))
3542 : return true;
3543 411 : if (TREE_CODE (outer) != RECORD_TYPE)
3544 : return false;
3545 406 : tree fld = TYPE_FIELDS (outer);
3546 6920 : while (fld)
3547 : {
3548 6763 : if (TREE_CODE (fld) == FIELD_DECL)
3549 : {
3550 434 : if (!zerop (DECL_FIELD_OFFSET (fld)))
3551 : return false;
3552 434 : if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner)
3553 : return true;
3554 369 : if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE)
3555 185 : fld = TYPE_FIELDS (TREE_TYPE (fld));
3556 : else
3557 : return false;
3558 : }
3559 : else
3560 6329 : fld = DECL_CHAIN (fld);
3561 : }
3562 : return false;
3563 : }
3564 :
3565 : /* Return type of total_should_skip_creating_access indicating whether a total
3566 : scalarization access for a field/element should be created, whether it
3567 : already exists or whether the entire total scalarization has to fail. */
3568 :
3569 : enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED};
3570 :
3571 : /* Do all the necessary steps in total scalarization when the given aggregate
3572 : type has a TYPE at POS with the given SIZE should be put into PARENT and
3573 : when we have processed all its siblings with smaller offsets up until and
3574 : including LAST_SEEN_SIBLING (which can be NULL).
3575 :
3576 : If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3577 : appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3578 : creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3579 : representing the described part of the aggregate for the purposes of total
3580 : scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3581 : prevents total scalarization from happening at all. */
3582 :
3583 : static enum total_sra_field_state
3584 1814172 : total_should_skip_creating_access (struct access *parent,
3585 : struct access **last_seen_sibling,
3586 : tree type, HOST_WIDE_INT pos,
3587 : HOST_WIDE_INT size)
3588 : {
3589 1814172 : struct access *next_child;
3590 1814172 : if (!*last_seen_sibling)
3591 824971 : next_child = parent->first_child;
3592 : else
3593 989201 : next_child = (*last_seen_sibling)->next_sibling;
3594 :
3595 : /* First, traverse the chain of siblings until it points to an access with
3596 : offset at least equal to POS. Check all skipped accesses whether they
3597 : span the POS boundary and if so, return with a failure. */
3598 1814173 : while (next_child && next_child->offset < pos)
3599 : {
3600 1 : if (next_child->offset + next_child->size > pos)
3601 : return TOTAL_FLD_FAILED;
3602 1 : *last_seen_sibling = next_child;
3603 1 : next_child = next_child->next_sibling;
3604 : }
3605 :
3606 : /* Now check whether next_child has exactly the right POS and SIZE and if so,
3607 : whether it can represent what we need and can be totally scalarized
3608 : itself. */
3609 1814172 : if (next_child && next_child->offset == pos
3610 1401707 : && next_child->size == size)
3611 : {
3612 1328318 : if (!is_gimple_reg_type (next_child->type)
3613 1328318 : && (!access_and_field_type_match_p (type, next_child->type)
3614 180156 : || !totally_scalarize_subtree (next_child)))
3615 392 : return TOTAL_FLD_FAILED;
3616 :
3617 1327926 : *last_seen_sibling = next_child;
3618 1327926 : return TOTAL_FLD_DONE;
3619 : }
3620 :
3621 : /* If the child we're looking at would partially overlap, we just cannot
3622 : totally scalarize. */
3623 : if (next_child
3624 103231 : && next_child->offset < pos + size
3625 76320 : && next_child->offset + next_child->size > pos + size)
3626 : return TOTAL_FLD_FAILED;
3627 :
3628 485818 : if (is_gimple_reg_type (type))
3629 : {
3630 : /* We don't scalarize accesses that are children of other scalar type
3631 : accesses, so if we go on and create an access for a register type,
3632 : there should not be any pre-existing children. There are rare cases
3633 : where the requested type is a vector but we already have register
3634 : accesses for all its elements which is equally good. Detect that
3635 : situation or whether we need to bail out. */
3636 :
3637 : HOST_WIDE_INT covered = pos;
3638 : bool skipping = false;
3639 : while (next_child
3640 370155 : && next_child->offset + next_child->size <= pos + size)
3641 : {
3642 428 : if (next_child->offset != covered
3643 428 : || !is_gimple_reg_type (next_child->type))
3644 : return TOTAL_FLD_FAILED;
3645 :
3646 428 : covered += next_child->size;
3647 428 : *last_seen_sibling = next_child;
3648 428 : next_child = next_child->next_sibling;
3649 428 : skipping = true;
3650 : }
3651 :
3652 369727 : if (skipping)
3653 : {
3654 112 : if (covered != pos + size)
3655 : return TOTAL_FLD_FAILED;
3656 : else
3657 : return TOTAL_FLD_DONE;
3658 : }
3659 : }
3660 :
3661 : return TOTAL_FLD_CREATE;
3662 : }
3663 :
3664 : /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3665 : spanning all uncovered areas covered by ROOT, return false if the attempt
3666 : failed. All created accesses will have grp_unscalarizable_region set (and
3667 : should be ignored if the function returns false). */
3668 :
3669 : static bool
3670 825319 : totally_scalarize_subtree (struct access *root)
3671 : {
3672 825319 : gcc_checking_assert (!root->grp_unscalarizable_region);
3673 825319 : gcc_checking_assert (!is_gimple_reg_type (root->type));
3674 :
3675 825319 : struct access *last_seen_sibling = NULL;
3676 :
3677 825319 : switch (TREE_CODE (root->type))
3678 : {
3679 811930 : case RECORD_TYPE:
3680 9767789 : for (tree fld = TYPE_FIELDS (root->type); fld; fld = DECL_CHAIN (fld))
3681 8956330 : if (TREE_CODE (fld) == FIELD_DECL)
3682 : {
3683 1815303 : tree ft = TREE_TYPE (fld);
3684 1815303 : HOST_WIDE_INT fsize = tree_to_uhwi (DECL_SIZE (fld));
3685 1815303 : if (!fsize)
3686 31479 : continue;
3687 :
3688 1783824 : HOST_WIDE_INT pos = root->offset + int_bit_position (fld);
3689 1783824 : if (pos + fsize > root->offset + root->size)
3690 : return false;
3691 1783824 : enum total_sra_field_state
3692 1783824 : state = total_should_skip_creating_access (root,
3693 : &last_seen_sibling,
3694 : ft, pos, fsize);
3695 1783824 : switch (state)
3696 : {
3697 : case TOTAL_FLD_FAILED:
3698 : return false;
3699 1321541 : case TOTAL_FLD_DONE:
3700 1321541 : continue;
3701 461883 : case TOTAL_FLD_CREATE:
3702 461883 : break;
3703 0 : default:
3704 0 : gcc_unreachable ();
3705 : }
3706 :
3707 461883 : struct access **p = (last_seen_sibling
3708 461883 : ? &last_seen_sibling->next_sibling
3709 : : &root->first_child);
3710 461883 : tree nref = build3 (COMPONENT_REF, ft, root->expr, fld, NULL_TREE);
3711 461883 : struct access *new_child
3712 461883 : = create_total_access_and_reshape (root, pos, fsize, ft, nref, p);
3713 461883 : if (!new_child)
3714 : return false;
3715 :
3716 461883 : if (!is_gimple_reg_type (ft)
3717 461883 : && !totally_scalarize_subtree (new_child))
3718 : return false;
3719 461812 : last_seen_sibling = new_child;
3720 : }
3721 : break;
3722 13389 : case ARRAY_TYPE:
3723 13389 : {
3724 13389 : tree elemtype = TREE_TYPE (root->type);
3725 13389 : HOST_WIDE_INT el_size;
3726 13389 : offset_int idx, max;
3727 13389 : if (!prepare_iteration_over_array_elts (root->type, &el_size,
3728 : &idx, &max))
3729 : break;
3730 :
3731 13389 : for (HOST_WIDE_INT pos = root->offset;
3732 43689 : idx <= max;
3733 30300 : pos += el_size, ++idx)
3734 : {
3735 30348 : enum total_sra_field_state
3736 30348 : state = total_should_skip_creating_access (root,
3737 : &last_seen_sibling,
3738 : elemtype, pos,
3739 : el_size);
3740 30348 : switch (state)
3741 : {
3742 : case TOTAL_FLD_FAILED:
3743 48 : return false;
3744 6477 : case TOTAL_FLD_DONE:
3745 6477 : continue;
3746 23823 : case TOTAL_FLD_CREATE:
3747 23823 : break;
3748 0 : default:
3749 0 : gcc_unreachable ();
3750 : }
3751 :
3752 23823 : struct access **p = (last_seen_sibling
3753 23823 : ? &last_seen_sibling->next_sibling
3754 : : &root->first_child);
3755 47646 : tree nref = build4 (ARRAY_REF, elemtype, root->expr,
3756 23823 : wide_int_to_tree (TYPE_DOMAIN (root->type),
3757 23823 : idx),
3758 : NULL_TREE, NULL_TREE);
3759 23823 : struct access *new_child
3760 23823 : = create_total_access_and_reshape (root, pos, el_size, elemtype,
3761 : nref, p);
3762 23823 : if (!new_child)
3763 : return false;
3764 :
3765 23823 : if (!is_gimple_reg_type (elemtype)
3766 23823 : && !totally_scalarize_subtree (new_child))
3767 : return false;
3768 23823 : last_seen_sibling = new_child;
3769 : }
3770 : }
3771 13341 : break;
3772 0 : default:
3773 0 : gcc_unreachable ();
3774 : }
3775 : return true;
3776 : }
3777 :
3778 : /* Get the total total scalarization size limit in the current function. */
3779 :
3780 : unsigned HOST_WIDE_INT
3781 715952 : sra_get_max_scalarization_size (void)
3782 : {
3783 715952 : bool optimize_speed_p = !optimize_function_for_size_p (cfun);
3784 : /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3785 : fall back to a target default. */
3786 715952 : unsigned HOST_WIDE_INT max_scalarization_size
3787 715952 : = get_move_ratio (optimize_speed_p) * MOVE_MAX;
3788 :
3789 715952 : if (optimize_speed_p)
3790 : {
3791 696298 : if (OPTION_SET_P (param_sra_max_scalarization_size_speed))
3792 9 : max_scalarization_size = param_sra_max_scalarization_size_speed;
3793 : }
3794 : else
3795 : {
3796 19654 : if (OPTION_SET_P (param_sra_max_scalarization_size_size))
3797 0 : max_scalarization_size = param_sra_max_scalarization_size_size;
3798 : }
3799 715952 : max_scalarization_size *= BITS_PER_UNIT;
3800 715952 : return max_scalarization_size;
3801 : }
3802 :
3803 : /* Go through all accesses collected throughout the (intraprocedural) analysis
3804 : stage, exclude overlapping ones, identify representatives and build trees
3805 : out of them, making decisions about scalarization on the way. Return true
3806 : iff there are any to-be-scalarized variables after this stage. */
3807 :
3808 : static bool
3809 709147 : analyze_all_variable_accesses (void)
3810 : {
3811 709147 : int res = 0;
3812 709147 : bitmap tmp = BITMAP_ALLOC (NULL);
3813 709147 : bitmap_iterator bi;
3814 709147 : unsigned i;
3815 :
3816 709147 : bitmap_copy (tmp, candidate_bitmap);
3817 4733039 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3818 : {
3819 4023892 : tree var = candidate (i);
3820 4023892 : struct access *access;
3821 :
3822 4023892 : access = sort_and_splice_var_accesses (var);
3823 4023892 : if (!access || !build_access_trees (access))
3824 162959 : disqualify_candidate (var,
3825 : "No or inhibitingly overlapping accesses.");
3826 : }
3827 :
3828 709147 : propagate_all_subaccesses ();
3829 :
3830 709147 : unsigned HOST_WIDE_INT max_scalarization_size
3831 709147 : = sra_get_max_scalarization_size ();
3832 4570080 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3833 3860933 : if (bitmap_bit_p (should_scalarize_away_bitmap, i)
3834 3860933 : && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
3835 : {
3836 814720 : tree var = candidate (i);
3837 814720 : if (!VAR_P (var))
3838 71625 : continue;
3839 :
3840 743095 : if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) > max_scalarization_size)
3841 : {
3842 7140 : if (dump_file && (dump_flags & TDF_DETAILS))
3843 : {
3844 0 : fprintf (dump_file, "Too big to totally scalarize: ");
3845 0 : print_generic_expr (dump_file, var);
3846 0 : fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
3847 : }
3848 7140 : continue;
3849 : }
3850 :
3851 735955 : bool all_types_ok = true;
3852 735955 : for (struct access *access = get_first_repr_for_decl (var);
3853 1457868 : access;
3854 721913 : access = access->next_grp)
3855 742205 : if (!can_totally_scalarize_forest_p (access)
3856 1479583 : || !totally_scalarizable_type_p (access->type,
3857 737378 : constant_decl_p (var),
3858 : 0, nullptr))
3859 : {
3860 : all_types_ok = false;
3861 : break;
3862 : }
3863 735955 : if (!all_types_ok)
3864 20292 : continue;
3865 :
3866 715663 : if (dump_file && (dump_flags & TDF_DETAILS))
3867 : {
3868 1 : fprintf (dump_file, "Will attempt to totally scalarize ");
3869 1 : print_generic_expr (dump_file, var);
3870 1 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3871 : }
3872 715663 : bool scalarized = true;
3873 715663 : for (struct access *access = get_first_repr_for_decl (var);
3874 1437172 : access;
3875 721509 : access = access->next_grp)
3876 721911 : if (!is_gimple_reg_type (access->type)
3877 721911 : && !totally_scalarize_subtree (access))
3878 : {
3879 : scalarized = false;
3880 : break;
3881 : }
3882 :
3883 715663 : if (scalarized)
3884 715261 : for (struct access *access = get_first_repr_for_decl (var);
3885 1436770 : access;
3886 721509 : access = access->next_grp)
3887 721509 : access->grp_total_scalarization = true;
3888 : }
3889 :
3890 709147 : if (flag_checking)
3891 709147 : verify_all_sra_access_forests ();
3892 :
3893 709147 : bitmap_copy (tmp, candidate_bitmap);
3894 4570080 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3895 : {
3896 3860933 : tree var = candidate (i);
3897 3860933 : struct access *access = get_first_repr_for_decl (var);
3898 :
3899 3860933 : if (analyze_access_trees (access))
3900 : {
3901 1762759 : res++;
3902 1762759 : if (dump_file && (dump_flags & TDF_DETAILS))
3903 : {
3904 8 : fprintf (dump_file, "\nAccess trees for ");
3905 8 : print_generic_expr (dump_file, var);
3906 8 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3907 8 : dump_access_tree (dump_file, access);
3908 8 : fprintf (dump_file, "\n");
3909 : }
3910 : }
3911 : else
3912 2098174 : disqualify_candidate (var, "No scalar replacements to be created.");
3913 : }
3914 :
3915 709147 : BITMAP_FREE (tmp);
3916 :
3917 709147 : if (res)
3918 : {
3919 421956 : statistics_counter_event (cfun, "Scalarized aggregates", res);
3920 421956 : return true;
3921 : }
3922 : else
3923 : return false;
3924 : }
3925 :
3926 : /* Generate statements copying scalar replacements of accesses within a subtree
3927 : into or out of AGG. ACCESS, all its children, siblings and their children
3928 : are to be processed. AGG is an aggregate type expression (can be a
3929 : declaration but does not have to be, it can for example also be a mem_ref or
3930 : a series of handled components). TOP_OFFSET is the offset of the processed
3931 : subtree which has to be subtracted from offsets of individual accesses to
3932 : get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3933 : replacements in the interval <start_offset, start_offset + chunk_size>,
3934 : otherwise copy all. GSI is a statement iterator used to place the new
3935 : statements. WRITE should be true when the statements should write from AGG
3936 : to the replacement and false if vice versa. If INSERT_AFTER is true, new
3937 : statements will be added after the current statement in GSI, they will be
3938 : added before the statement otherwise. If FORCE_REF_ALL is true then
3939 : memory accesses will use alias-set zero. */
3940 :
3941 : static void
3942 1916879 : generate_subtree_copies (struct access *access, tree agg,
3943 : HOST_WIDE_INT top_offset,
3944 : HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
3945 : gimple_stmt_iterator *gsi, bool write,
3946 : bool insert_after, location_t loc,
3947 : bool force_ref_all = false)
3948 : {
3949 : /* Never write anything into constant pool decls. See PR70602. */
3950 3833758 : if (!write && constant_decl_p (agg))
3951 : return;
3952 4640904 : do
3953 : {
3954 4640904 : if (chunk_size && access->offset >= start_offset + chunk_size)
3955 : return;
3956 :
3957 4640904 : if (access->grp_to_be_replaced
3958 3634992 : && (chunk_size == 0
3959 0 : || access->offset + access->size > start_offset))
3960 : {
3961 3634992 : tree expr, repl = get_access_replacement (access);
3962 3634992 : gassign *stmt;
3963 :
3964 3634992 : expr = build_ref_for_model (loc, agg, access->offset - top_offset,
3965 : access, gsi, insert_after, force_ref_all);
3966 :
3967 3634992 : if (write)
3968 : {
3969 1648405 : if (access->grp_partial_lhs)
3970 8 : expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
3971 8 : !insert_after,
3972 : insert_after ? GSI_NEW_STMT
3973 : : GSI_SAME_STMT);
3974 1648405 : stmt = gimple_build_assign (repl, expr);
3975 : }
3976 : else
3977 : {
3978 1986587 : suppress_warning (repl /* Be more selective! */);
3979 1986587 : if (access->grp_partial_lhs)
3980 72 : repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3981 72 : !insert_after,
3982 : insert_after ? GSI_NEW_STMT
3983 : : GSI_SAME_STMT);
3984 1986587 : stmt = gimple_build_assign (expr, repl);
3985 : }
3986 3634992 : gimple_set_location (stmt, loc);
3987 :
3988 3634992 : if (insert_after)
3989 1648405 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3990 : else
3991 1986587 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3992 3634992 : update_stmt (stmt);
3993 3634992 : sra_stats.subtree_copies++;
3994 3634992 : }
3995 1005912 : else if (write
3996 386759 : && access->grp_to_be_debug_replaced
3997 5729 : && (chunk_size == 0
3998 0 : || access->offset + access->size > start_offset))
3999 : {
4000 5729 : gdebug *ds;
4001 11458 : tree drhs = build_debug_ref_for_model (loc, agg,
4002 5729 : access->offset - top_offset,
4003 : access);
4004 5729 : ds = gimple_build_debug_bind (get_access_replacement (access),
4005 : drhs, gsi_stmt (*gsi));
4006 5729 : if (insert_after)
4007 5729 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4008 : else
4009 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4010 : }
4011 :
4012 4640904 : if (access->first_child)
4013 460721 : generate_subtree_copies (access->first_child, agg, top_offset,
4014 : start_offset, chunk_size, gsi,
4015 : write, insert_after, loc, force_ref_all);
4016 :
4017 4640904 : access = access->next_sibling;
4018 : }
4019 4640904 : while (access);
4020 : }
4021 :
4022 : /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
4023 : root of the subtree to be processed. GSI is the statement iterator used
4024 : for inserting statements which are added after the current statement if
4025 : INSERT_AFTER is true or before it otherwise. */
4026 :
4027 : static void
4028 547177 : init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
4029 : bool insert_after, location_t loc)
4030 :
4031 : {
4032 547177 : struct access *child;
4033 :
4034 547177 : if (access->grp_to_be_replaced)
4035 : {
4036 251871 : gassign *stmt;
4037 :
4038 251871 : stmt = gimple_build_assign (get_access_replacement (access),
4039 : build_zero_cst (access->type));
4040 251871 : if (insert_after)
4041 36498 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4042 : else
4043 215373 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4044 251871 : update_stmt (stmt);
4045 251871 : gimple_set_location (stmt, loc);
4046 : }
4047 295306 : else if (access->grp_to_be_debug_replaced)
4048 : {
4049 29231 : gdebug *ds
4050 29231 : = gimple_build_debug_bind (get_access_replacement (access),
4051 : build_zero_cst (access->type),
4052 : gsi_stmt (*gsi));
4053 29231 : if (insert_after)
4054 29231 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4055 : else
4056 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4057 : }
4058 :
4059 944835 : for (child = access->first_child; child; child = child->next_sibling)
4060 397658 : init_subtree_with_zero (child, gsi, insert_after, loc);
4061 547177 : }
4062 :
4063 : /* Clobber all scalar replacements in an access subtree. ACCESS is the
4064 : root of the subtree to be processed. GSI is the statement iterator used
4065 : for inserting statements which are added after the current statement if
4066 : INSERT_AFTER is true or before it otherwise. */
4067 :
4068 : static void
4069 2815010 : clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
4070 : bool insert_after, location_t loc)
4071 :
4072 : {
4073 2815010 : struct access *child;
4074 :
4075 2815010 : if (access->grp_to_be_replaced)
4076 : {
4077 1796918 : tree rep = get_access_replacement (access);
4078 1796918 : tree clobber = build_clobber (access->type);
4079 1796918 : gimple *stmt = gimple_build_assign (rep, clobber);
4080 :
4081 1796918 : if (insert_after)
4082 370848 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4083 : else
4084 1426070 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4085 1796918 : update_stmt (stmt);
4086 1796918 : gimple_set_location (stmt, loc);
4087 : }
4088 :
4089 4637314 : for (child = access->first_child; child; child = child->next_sibling)
4090 1822304 : clobber_subtree (child, gsi, insert_after, loc);
4091 2815010 : }
4092 :
4093 : /* Search for an access representative for the given expression EXPR and
4094 : return it or NULL if it cannot be found. */
4095 :
4096 : static struct access *
4097 46493644 : get_access_for_expr (tree expr)
4098 : {
4099 46493644 : poly_int64 poffset, psize, pmax_size;
4100 46493644 : HOST_WIDE_INT offset, max_size;
4101 46493644 : tree base;
4102 46493644 : bool reverse;
4103 :
4104 46493644 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
4105 : &reverse);
4106 46493644 : if (!known_size_p (pmax_size)
4107 46345279 : || !pmax_size.is_constant (&max_size)
4108 46345279 : || !poffset.is_constant (&offset)
4109 46493644 : || !DECL_P (base))
4110 : return NULL;
4111 :
4112 21742305 : if (tree basesize = DECL_SIZE (base))
4113 : {
4114 21699173 : poly_int64 sz;
4115 21699173 : if (offset < 0
4116 21699157 : || !poly_int_tree_p (basesize, &sz)
4117 43398330 : || known_le (sz, offset))
4118 7023 : return NULL;
4119 : }
4120 :
4121 21735282 : if (max_size == 0
4122 21735282 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
4123 12597445 : return NULL;
4124 :
4125 9137837 : return get_var_base_offset_size_access (base, offset, max_size);
4126 : }
4127 :
4128 : /* Replace the expression EXPR with a scalar replacement if there is one and
4129 : generate other statements to do type conversion or subtree copying if
4130 : necessary. WRITE is true if the expression is being written to (it is on a
4131 : LHS of a statement or output in an assembly statement). STMT_GSI is used to
4132 : place newly created statements before the processed statement, REFRESH_GSI
4133 : is used to place them afterwards - unless the processed statement must end a
4134 : BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
4135 : is then used to continue iteration over the BB. If sra_modify_expr is
4136 : called only once with WRITE equal to true on a given statement, both
4137 : iterator parameters can point to the same one. */
4138 :
4139 : static bool
4140 7507247 : sra_modify_expr (tree *expr, bool write, gimple_stmt_iterator *stmt_gsi,
4141 : gimple_stmt_iterator *refresh_gsi)
4142 : {
4143 7507247 : location_t loc;
4144 7507247 : struct access *access;
4145 7507247 : tree type, bfr, orig_expr;
4146 7507247 : bool partial_cplx_access = false;
4147 :
4148 7507247 : if (TREE_CODE (*expr) == BIT_FIELD_REF
4149 7507247 : && (write || !sra_handled_bf_read_p (*expr)))
4150 : {
4151 586 : bfr = *expr;
4152 586 : expr = &TREE_OPERAND (*expr, 0);
4153 : }
4154 : else
4155 : bfr = NULL_TREE;
4156 :
4157 7507247 : if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
4158 : {
4159 25071 : expr = &TREE_OPERAND (*expr, 0);
4160 25071 : partial_cplx_access = true;
4161 : }
4162 7507247 : access = get_access_for_expr (*expr);
4163 7507247 : if (!access)
4164 : return false;
4165 196922 : type = TREE_TYPE (*expr);
4166 196922 : orig_expr = *expr;
4167 :
4168 196922 : loc = gimple_location (gsi_stmt (*stmt_gsi));
4169 196922 : gimple_stmt_iterator alt_gsi = gsi_none ();
4170 196922 : if (write && stmt_ends_bb_p (gsi_stmt (*stmt_gsi)))
4171 : {
4172 36435 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi)));
4173 36435 : refresh_gsi = &alt_gsi;
4174 : }
4175 :
4176 196922 : if (access->grp_to_be_replaced)
4177 : {
4178 48645 : tree repl = get_access_replacement (access);
4179 : /* If we replace a non-register typed access simply use the original
4180 : access expression to extract the scalar component afterwards.
4181 : This happens if scalarizing a function return value or parameter
4182 : like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
4183 : gcc.c-torture/compile/20011217-1.c.
4184 :
4185 : We also want to use this when accessing a complex or vector which can
4186 : be accessed as a different type too, potentially creating a need for
4187 : type conversion (see PR42196) and when scalarized unions are involved
4188 : in assembler statements (see PR42398). */
4189 48645 : if (!bfr && !useless_type_conversion_p (type, access->type))
4190 : {
4191 45209 : tree ref;
4192 :
4193 45209 : ref = build_ref_for_model (loc, orig_expr, 0, access, stmt_gsi,
4194 : false);
4195 :
4196 45209 : if (partial_cplx_access)
4197 : {
4198 : /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4199 : the case of a write because in such case the replacement cannot
4200 : be a gimple register. In the case of a load, we have to
4201 : differentiate in between a register an non-register
4202 : replacement. */
4203 29 : tree t = build1 (VIEW_CONVERT_EXPR, type, repl);
4204 29 : gcc_checking_assert (!write || access->grp_partial_lhs);
4205 29 : if (!access->grp_partial_lhs)
4206 : {
4207 26 : tree tmp = make_ssa_name (type);
4208 26 : gassign *stmt = gimple_build_assign (tmp, t);
4209 : /* This is always a read. */
4210 26 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4211 26 : t = tmp;
4212 : }
4213 29 : *expr = t;
4214 : }
4215 45180 : else if (write)
4216 : {
4217 11454 : gassign *stmt;
4218 :
4219 11454 : if (access->grp_partial_lhs)
4220 6 : ref = force_gimple_operand_gsi (refresh_gsi, ref, true,
4221 : NULL_TREE, false, GSI_NEW_STMT);
4222 11454 : stmt = gimple_build_assign (repl, ref);
4223 11454 : gimple_set_location (stmt, loc);
4224 11454 : gsi_insert_after (refresh_gsi, stmt, GSI_NEW_STMT);
4225 : }
4226 : else
4227 : {
4228 33726 : if (TREE_READONLY (access->base))
4229 : return false;
4230 :
4231 33707 : gassign *stmt;
4232 33707 : if (access->grp_partial_lhs)
4233 15 : repl = force_gimple_operand_gsi (stmt_gsi, repl, true,
4234 : NULL_TREE, true,
4235 : GSI_SAME_STMT);
4236 33707 : stmt = gimple_build_assign (ref, repl);
4237 33707 : gimple_set_location (stmt, loc);
4238 33707 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4239 : }
4240 : }
4241 : else
4242 : {
4243 : /* If we are going to replace a scalar field in a structure with
4244 : reverse storage order by a stand-alone scalar, we are going to
4245 : effectively byte-swap the scalar and we also need to byte-swap
4246 : the portion of it represented by the bit-field. */
4247 3436 : if (bfr && REF_REVERSE_STORAGE_ORDER (bfr))
4248 : {
4249 0 : REF_REVERSE_STORAGE_ORDER (bfr) = 0;
4250 0 : TREE_OPERAND (bfr, 2)
4251 0 : = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (repl)),
4252 : size_binop (PLUS_EXPR, TREE_OPERAND (bfr, 1),
4253 : TREE_OPERAND (bfr, 2)));
4254 : }
4255 :
4256 3436 : *expr = repl;
4257 : }
4258 :
4259 48626 : sra_stats.exprs++;
4260 : }
4261 148277 : else if (write && access->grp_to_be_debug_replaced)
4262 : {
4263 12 : gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
4264 : NULL_TREE,
4265 : gsi_stmt (*stmt_gsi));
4266 12 : gsi_insert_after (stmt_gsi, ds, GSI_NEW_STMT);
4267 : }
4268 :
4269 196903 : if (access->first_child && !TREE_READONLY (access->base))
4270 : {
4271 144650 : HOST_WIDE_INT start_offset, chunk_size;
4272 144650 : if (bfr
4273 0 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
4274 144650 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
4275 : {
4276 0 : chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
4277 0 : start_offset = access->offset
4278 0 : + tree_to_uhwi (TREE_OPERAND (bfr, 2));
4279 : }
4280 : else
4281 : start_offset = chunk_size = 0;
4282 :
4283 242182 : generate_subtree_copies (access->first_child, orig_expr, access->offset,
4284 : start_offset, chunk_size,
4285 : write ? refresh_gsi : stmt_gsi,
4286 : write, write, loc);
4287 : }
4288 : return true;
4289 : }
4290 :
4291 : /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4292 : reads from its base before and after the call statement given in CALL_GSI
4293 : and return true if any copying took place. Otherwise call sra_modify_expr
4294 : on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4295 : return for the given parameter. */
4296 :
4297 : static bool
4298 8242828 : sra_modify_call_arg (tree *expr, gimple_stmt_iterator *call_gsi,
4299 : gimple_stmt_iterator *refresh_gsi, int flags)
4300 : {
4301 8242828 : if (TREE_CODE (*expr) != ADDR_EXPR)
4302 5442502 : return sra_modify_expr (expr, false, call_gsi, refresh_gsi);
4303 :
4304 2800326 : if (flags & EAF_UNUSED)
4305 : return false;
4306 :
4307 2796755 : tree base = get_base_address (TREE_OPERAND (*expr, 0));
4308 2796755 : if (!DECL_P (base))
4309 : return false;
4310 2120991 : struct access *access = get_access_for_expr (base);
4311 2120991 : if (!access)
4312 : return false;
4313 :
4314 51022 : gimple *stmt = gsi_stmt (*call_gsi);
4315 51022 : location_t loc = gimple_location (stmt);
4316 51022 : generate_subtree_copies (access, base, 0, 0, 0, call_gsi, false, false,
4317 : loc, true);
4318 :
4319 51022 : if (flags & EAF_NO_DIRECT_CLOBBER)
4320 : return true;
4321 :
4322 35953 : if (!stmt_ends_bb_p (stmt))
4323 26179 : generate_subtree_copies (access, base, 0, 0, 0, refresh_gsi, true,
4324 : true, loc, true);
4325 : else
4326 : {
4327 9774 : edge e;
4328 9774 : edge_iterator ei;
4329 29299 : FOR_EACH_EDGE (e, ei, gsi_bb (*call_gsi)->succs)
4330 : {
4331 19525 : gimple_stmt_iterator alt_gsi = gsi_start_edge (e);
4332 19525 : generate_subtree_copies (access, base, 0, 0, 0, &alt_gsi, true,
4333 : true, loc, true);
4334 : }
4335 : }
4336 : return true;
4337 : }
4338 :
4339 : /* Where scalar replacements of the RHS have been written to when a replacement
4340 : of a LHS of an assigments cannot be direclty loaded from a replacement of
4341 : the RHS. */
4342 : enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
4343 : SRA_UDH_RIGHT, /* Data flushed to the RHS. */
4344 : SRA_UDH_LEFT }; /* Data flushed to the LHS. */
4345 :
4346 : struct subreplacement_assignment_data
4347 : {
4348 : /* Offset of the access representing the lhs of the assignment. */
4349 : HOST_WIDE_INT left_offset;
4350 :
4351 : /* LHS and RHS of the original assignment. */
4352 : tree assignment_lhs, assignment_rhs;
4353 :
4354 : /* Access representing the rhs of the whole assignment. */
4355 : struct access *top_racc;
4356 :
4357 : /* Stmt iterator used for statement insertions after the original assignment.
4358 : It points to the main GSI used to traverse a BB during function body
4359 : modification. */
4360 : gimple_stmt_iterator *new_gsi;
4361 :
4362 : /* Stmt iterator used for statement insertions before the original
4363 : assignment. Keeps on pointing to the original statement. */
4364 : gimple_stmt_iterator old_gsi;
4365 :
4366 : /* Location of the assignment. */
4367 : location_t loc;
4368 :
4369 : /* Keeps the information whether we have needed to refresh replacements of
4370 : the LHS and from which side of the assignments this takes place. */
4371 : enum unscalarized_data_handling refreshed;
4372 : };
4373 :
4374 : /* Store all replacements in the access tree rooted in TOP_RACC either to their
4375 : base aggregate if there are unscalarized data or directly to LHS of the
4376 : statement that is pointed to by GSI otherwise. */
4377 :
4378 : static void
4379 112839 : handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
4380 : {
4381 112839 : tree src;
4382 : /* If the RHS is a load from a constant, we do not need to (and must not)
4383 : flush replacements to it and can use it directly as if we did. */
4384 112839 : if (TREE_READONLY (sad->top_racc->base))
4385 : {
4386 7 : sad->refreshed = SRA_UDH_RIGHT;
4387 7 : return;
4388 : }
4389 112832 : if (sad->top_racc->grp_unscalarized_data)
4390 : {
4391 27666 : src = sad->assignment_rhs;
4392 27666 : sad->refreshed = SRA_UDH_RIGHT;
4393 : }
4394 : else
4395 : {
4396 85166 : src = sad->assignment_lhs;
4397 85166 : sad->refreshed = SRA_UDH_LEFT;
4398 : }
4399 112832 : generate_subtree_copies (sad->top_racc->first_child, src,
4400 : sad->top_racc->offset, 0, 0,
4401 : &sad->old_gsi, false, false, sad->loc);
4402 : }
4403 :
4404 : /* Try to generate statements to load all sub-replacements in an access subtree
4405 : formed by children of LACC from scalar replacements in the SAD->top_racc
4406 : subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4407 : and load the accesses from it. */
4408 :
4409 : static void
4410 501432 : load_assign_lhs_subreplacements (struct access *lacc,
4411 : struct subreplacement_assignment_data *sad)
4412 : {
4413 1646884 : for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
4414 : {
4415 1145452 : HOST_WIDE_INT offset;
4416 1145452 : offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
4417 :
4418 1145452 : if (lacc->grp_to_be_replaced)
4419 : {
4420 955539 : struct access *racc;
4421 955539 : gassign *stmt;
4422 955539 : tree rhs;
4423 :
4424 955539 : racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
4425 955539 : if (racc && racc->grp_to_be_replaced)
4426 : {
4427 927707 : rhs = get_access_replacement (racc);
4428 927707 : bool vce = false;
4429 927707 : if (!useless_type_conversion_p (lacc->type, racc->type))
4430 : {
4431 31 : rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4432 : lacc->type, rhs);
4433 31 : vce = true;
4434 : }
4435 :
4436 927707 : if (lacc->grp_partial_lhs && (vce || racc->grp_partial_lhs))
4437 3 : rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
4438 : NULL_TREE, true, GSI_SAME_STMT);
4439 : }
4440 : else
4441 : {
4442 : /* No suitable access on the right hand side, need to load from
4443 : the aggregate. See if we have to update it first... */
4444 27832 : if (sad->refreshed == SRA_UDH_NONE)
4445 14989 : handle_unscalarized_data_in_subtree (sad);
4446 :
4447 27832 : if (sad->refreshed == SRA_UDH_LEFT)
4448 482 : rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
4449 482 : lacc->offset - sad->left_offset,
4450 : lacc, sad->new_gsi, true);
4451 : else
4452 27350 : rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
4453 27350 : lacc->offset - sad->left_offset,
4454 : lacc, sad->new_gsi, true);
4455 27832 : if (lacc->grp_partial_lhs)
4456 1 : rhs = force_gimple_operand_gsi (sad->new_gsi,
4457 : rhs, true, NULL_TREE,
4458 : false, GSI_NEW_STMT);
4459 : }
4460 :
4461 955539 : stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
4462 955539 : gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
4463 955539 : gimple_set_location (stmt, sad->loc);
4464 955539 : update_stmt (stmt);
4465 955539 : sra_stats.subreplacements++;
4466 : }
4467 : else
4468 : {
4469 189913 : if (sad->refreshed == SRA_UDH_NONE
4470 27156 : && lacc->grp_read && !lacc->grp_covered)
4471 24 : handle_unscalarized_data_in_subtree (sad);
4472 :
4473 189913 : if (lacc && lacc->grp_to_be_debug_replaced)
4474 : {
4475 108880 : gdebug *ds;
4476 108880 : tree drhs;
4477 108880 : struct access *racc = find_access_in_subtree (sad->top_racc,
4478 : offset,
4479 : lacc->size);
4480 :
4481 108880 : if (racc && racc->grp_to_be_replaced)
4482 : {
4483 108731 : if (racc->grp_write || constant_decl_p (racc->base))
4484 105635 : drhs = get_access_replacement (racc);
4485 : else
4486 : drhs = NULL;
4487 : }
4488 149 : else if (sad->refreshed == SRA_UDH_LEFT)
4489 0 : drhs = build_debug_ref_for_model (sad->loc, lacc->base,
4490 : lacc->offset, lacc);
4491 149 : else if (sad->refreshed == SRA_UDH_RIGHT)
4492 147 : drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
4493 : offset, lacc);
4494 : else
4495 : drhs = NULL_TREE;
4496 105635 : if (drhs
4497 105782 : && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
4498 1941 : drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4499 : lacc->type, drhs);
4500 108880 : ds = gimple_build_debug_bind (get_access_replacement (lacc),
4501 : drhs, gsi_stmt (sad->old_gsi));
4502 108880 : gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
4503 : }
4504 : }
4505 :
4506 1145452 : if (lacc->first_child)
4507 36483 : load_assign_lhs_subreplacements (lacc, sad);
4508 : }
4509 501432 : }
4510 :
4511 : /* Result code for SRA assignment modification. */
4512 : enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
4513 : SRA_AM_MODIFIED, /* stmt changed but not
4514 : removed */
4515 : SRA_AM_REMOVED }; /* stmt eliminated */
4516 :
4517 : /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4518 : to the assignment and GSI is the statement iterator pointing at it. Returns
4519 : the same values as sra_modify_assign. */
4520 :
4521 : static enum assignment_mod_result
4522 2823397 : sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4523 : {
4524 2823397 : tree lhs = gimple_assign_lhs (stmt);
4525 2823397 : struct access *acc = get_access_for_expr (lhs);
4526 2823397 : if (!acc)
4527 : return SRA_AM_NONE;
4528 1142225 : location_t loc = gimple_location (stmt);
4529 :
4530 1142225 : if (gimple_clobber_p (stmt))
4531 : {
4532 : /* Clobber the replacement variable. */
4533 992706 : clobber_subtree (acc, gsi, !acc->grp_covered, loc);
4534 : /* Remove clobbers of fully scalarized variables, they are dead. */
4535 992706 : if (acc->grp_covered)
4536 : {
4537 752934 : unlink_stmt_vdef (stmt);
4538 752934 : gsi_remove (gsi, true);
4539 752934 : release_defs (stmt);
4540 752934 : return SRA_AM_REMOVED;
4541 : }
4542 : else
4543 : return SRA_AM_MODIFIED;
4544 : }
4545 :
4546 149519 : if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
4547 : {
4548 : /* I have never seen this code path trigger but if it can happen the
4549 : following should handle it gracefully. */
4550 0 : if (access_has_children_p (acc))
4551 0 : generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
4552 : true, true, loc);
4553 0 : return SRA_AM_MODIFIED;
4554 : }
4555 :
4556 149519 : if (acc->grp_covered)
4557 : {
4558 80718 : init_subtree_with_zero (acc, gsi, false, loc);
4559 80718 : unlink_stmt_vdef (stmt);
4560 80718 : gsi_remove (gsi, true);
4561 80718 : release_defs (stmt);
4562 80718 : return SRA_AM_REMOVED;
4563 : }
4564 : else
4565 : {
4566 68801 : init_subtree_with_zero (acc, gsi, true, loc);
4567 68801 : return SRA_AM_MODIFIED;
4568 : }
4569 : }
4570 :
4571 : /* Create and return a new suitable default definition SSA_NAME for RACC which
4572 : is an access describing an uninitialized part of an aggregate that is being
4573 : loaded. REG_TREE is used instead of the actual RACC type if that is not of
4574 : a gimple register type. */
4575 :
4576 : static tree
4577 544 : get_repl_default_def_ssa_name (struct access *racc, tree reg_type)
4578 : {
4579 544 : gcc_checking_assert (!racc->grp_to_be_replaced
4580 : && !racc->grp_to_be_debug_replaced);
4581 544 : if (!racc->replacement_decl)
4582 544 : racc->replacement_decl = create_access_replacement (racc, reg_type);
4583 544 : return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
4584 : }
4585 :
4586 :
4587 : /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4588 : of accesses within a subtree ACCESS; all its children, siblings and their
4589 : children are to be processed.
4590 : GSI is a statement iterator used to place the new statements. */
4591 : static void
4592 23419 : generate_subtree_deferred_init (struct access *access,
4593 : tree init_type,
4594 : tree decl_name,
4595 : gimple_stmt_iterator *gsi,
4596 : location_t loc)
4597 : {
4598 52512 : do
4599 : {
4600 52512 : if (access->grp_to_be_replaced)
4601 : {
4602 40625 : tree repl = get_access_replacement (access);
4603 40625 : gimple *call
4604 40625 : = gimple_build_call_internal (IFN_DEFERRED_INIT, 3,
4605 40625 : TYPE_SIZE_UNIT (TREE_TYPE (repl)),
4606 : init_type, decl_name);
4607 40625 : gimple_call_set_lhs (call, repl);
4608 40625 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
4609 40625 : update_stmt (call);
4610 40625 : gimple_set_location (call, loc);
4611 40625 : sra_stats.subtree_deferred_init++;
4612 : }
4613 52512 : if (access->first_child)
4614 3684 : generate_subtree_deferred_init (access->first_child, init_type,
4615 : decl_name, gsi, loc);
4616 :
4617 52512 : access = access ->next_sibling;
4618 : }
4619 52512 : while (access);
4620 23419 : }
4621 :
4622 : /* For a call to .DEFERRED_INIT:
4623 : var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4624 : examine the LHS variable VAR and replace it with a scalar replacement if
4625 : there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4626 : the corresponding scalar relacement variable. Examine the subtree and
4627 : do the scalar replacements in the subtree too. STMT is the call, GSI is
4628 : the statement iterator to place newly created statement. */
4629 :
4630 : static enum assignment_mod_result
4631 82033 : sra_modify_deferred_init (gimple *stmt, gimple_stmt_iterator *gsi)
4632 : {
4633 82033 : tree lhs = gimple_call_lhs (stmt);
4634 82033 : tree init_type = gimple_call_arg (stmt, 1);
4635 82033 : tree decl_name = gimple_call_arg (stmt, 2);
4636 :
4637 82033 : struct access *lhs_access = get_access_for_expr (lhs);
4638 82033 : if (!lhs_access)
4639 : return SRA_AM_NONE;
4640 :
4641 29569 : location_t loc = gimple_location (stmt);
4642 :
4643 29569 : if (lhs_access->grp_to_be_replaced)
4644 : {
4645 9479 : tree lhs_repl = get_access_replacement (lhs_access);
4646 9479 : gimple_call_set_lhs (stmt, lhs_repl);
4647 9479 : tree arg0_repl = TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl));
4648 9479 : gimple_call_set_arg (stmt, 0, arg0_repl);
4649 9479 : sra_stats.deferred_init++;
4650 9479 : gcc_assert (!lhs_access->first_child);
4651 : return SRA_AM_MODIFIED;
4652 : }
4653 :
4654 20090 : if (lhs_access->first_child)
4655 19735 : generate_subtree_deferred_init (lhs_access->first_child,
4656 : init_type, decl_name, gsi, loc);
4657 20090 : if (lhs_access->grp_covered)
4658 : {
4659 12113 : unlink_stmt_vdef (stmt);
4660 12113 : gsi_remove (gsi, true);
4661 12113 : release_defs (stmt);
4662 12113 : return SRA_AM_REMOVED;
4663 : }
4664 :
4665 : return SRA_AM_MODIFIED;
4666 : }
4667 :
4668 : /* Examine both sides of the assignment statement pointed to by STMT, replace
4669 : them with a scalare replacement if there is one and generate copying of
4670 : replacements if scalarized aggregates have been used in the assignment. GSI
4671 : is used to hold generated statements for type conversions and subtree
4672 : copying. */
4673 :
4674 : static enum assignment_mod_result
4675 25390258 : sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4676 : {
4677 25390258 : struct access *lacc, *racc;
4678 25390258 : tree lhs, rhs;
4679 25390258 : bool modify_this_stmt = false;
4680 25390258 : bool force_gimple_rhs = false;
4681 25390258 : location_t loc;
4682 25390258 : gimple_stmt_iterator orig_gsi = *gsi;
4683 :
4684 25390258 : if (!gimple_assign_single_p (stmt))
4685 : return SRA_AM_NONE;
4686 19829042 : lhs = gimple_assign_lhs (stmt);
4687 19829042 : rhs = gimple_assign_rhs1 (stmt);
4688 :
4689 19829042 : if (TREE_CODE (rhs) == CONSTRUCTOR)
4690 2823397 : return sra_modify_constructor_assign (stmt, gsi);
4691 :
4692 16996654 : if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
4693 16993458 : || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
4694 16980574 : || (TREE_CODE (rhs) == BIT_FIELD_REF && !sra_handled_bf_read_p (rhs))
4695 33986215 : || TREE_CODE (lhs) == BIT_FIELD_REF)
4696 : {
4697 25657 : modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
4698 : false, gsi, gsi);
4699 25657 : modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
4700 : true, gsi, gsi);
4701 47958 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4702 : }
4703 :
4704 16979988 : lacc = get_access_for_expr (lhs);
4705 16979988 : racc = get_access_for_expr (rhs);
4706 16979988 : if (!lacc && !racc)
4707 : return SRA_AM_NONE;
4708 : /* Avoid modifying initializations of constant-pool replacements. */
4709 6948376 : if (racc && (racc->replacement_decl == lhs))
4710 : return SRA_AM_NONE;
4711 :
4712 6943395 : loc = gimple_location (stmt);
4713 6943395 : if (lacc && lacc->grp_to_be_replaced)
4714 : {
4715 1878736 : lhs = get_access_replacement (lacc);
4716 1878736 : gimple_assign_set_lhs (stmt, lhs);
4717 1878736 : modify_this_stmt = true;
4718 1878736 : if (lacc->grp_partial_lhs)
4719 85 : force_gimple_rhs = true;
4720 1878736 : sra_stats.exprs++;
4721 : }
4722 :
4723 6943395 : if (racc && racc->grp_to_be_replaced)
4724 : {
4725 3167202 : rhs = get_access_replacement (racc);
4726 3167202 : modify_this_stmt = true;
4727 3167202 : if (racc->grp_partial_lhs)
4728 557 : force_gimple_rhs = true;
4729 3167202 : sra_stats.exprs++;
4730 : }
4731 1099926 : else if (racc
4732 1099926 : && !racc->grp_unscalarized_data
4733 873581 : && !racc->grp_unscalarizable_region
4734 873579 : && TREE_CODE (lhs) == SSA_NAME
4735 544 : && !access_has_replacements_p (racc))
4736 : {
4737 544 : rhs = get_repl_default_def_ssa_name (racc, TREE_TYPE (lhs));
4738 544 : modify_this_stmt = true;
4739 544 : sra_stats.exprs++;
4740 : }
4741 :
4742 3167746 : if (modify_this_stmt
4743 6943395 : && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4744 : {
4745 : /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4746 : ??? This should move to fold_stmt which we simply should
4747 : call after building a VIEW_CONVERT_EXPR here. */
4748 533822 : if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
4749 148397 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs)) == racc->reverse
4750 415813 : && !contains_bitfld_component_ref_p (lhs))
4751 : {
4752 148396 : lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
4753 148396 : gimple_assign_set_lhs (stmt, lhs);
4754 : }
4755 119021 : else if (lacc
4756 91311 : && AGGREGATE_TYPE_P (TREE_TYPE (rhs))
4757 65521 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs)) == lacc->reverse
4758 184542 : && !contains_vce_or_bfcref_p (rhs))
4759 65050 : rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
4760 :
4761 267417 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4762 : {
4763 53971 : rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
4764 53971 : if (is_gimple_reg_type (TREE_TYPE (lhs))
4765 53971 : && TREE_CODE (lhs) != SSA_NAME)
4766 6943395 : force_gimple_rhs = true;
4767 : }
4768 : }
4769 :
4770 6943395 : if (lacc && lacc->grp_to_be_debug_replaced)
4771 : {
4772 142324 : tree dlhs = get_access_replacement (lacc);
4773 142324 : tree drhs = unshare_expr (rhs);
4774 142324 : if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
4775 : {
4776 3412 : if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
4777 1767 : && !contains_vce_or_bfcref_p (drhs))
4778 61 : drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
4779 1706 : if (drhs
4780 3412 : && !useless_type_conversion_p (TREE_TYPE (dlhs),
4781 1706 : TREE_TYPE (drhs)))
4782 1645 : drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
4783 1645 : TREE_TYPE (dlhs), drhs);
4784 : }
4785 142324 : gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
4786 142324 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4787 : }
4788 :
4789 : /* From this point on, the function deals with assignments in between
4790 : aggregates when at least one has scalar reductions of some of its
4791 : components. There are three possible scenarios: Both the LHS and RHS have
4792 : to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4793 :
4794 : In the first case, we would like to load the LHS components from RHS
4795 : components whenever possible. If that is not possible, we would like to
4796 : read it directly from the RHS (after updating it by storing in it its own
4797 : components). If there are some necessary unscalarized data in the LHS,
4798 : those will be loaded by the original assignment too. If neither of these
4799 : cases happen, the original statement can be removed. Most of this is done
4800 : by load_assign_lhs_subreplacements.
4801 :
4802 : In the second case, we would like to store all RHS scalarized components
4803 : directly into LHS and if they cover the aggregate completely, remove the
4804 : statement too. In the third case, we want the LHS components to be loaded
4805 : directly from the RHS (DSE will remove the original statement if it
4806 : becomes redundant).
4807 :
4808 : This is a bit complex but manageable when types match and when unions do
4809 : not cause confusion in a way that we cannot really load a component of LHS
4810 : from the RHS or vice versa (the access representing this level can have
4811 : subaccesses that are accessible only through a different union field at a
4812 : higher level - different from the one used in the examined expression).
4813 : Unions are fun.
4814 :
4815 : Therefore, I specially handle a fourth case, happening when there is a
4816 : specific type cast or it is impossible to locate a scalarized subaccess on
4817 : the other side of the expression. If that happens, I simply "refresh" the
4818 : RHS by storing in it is scalarized components leave the original statement
4819 : there to do the copying and then load the scalar replacements of the LHS.
4820 : This is what the first branch does. */
4821 :
4822 6943395 : if (modify_this_stmt
4823 2018692 : || gimple_has_volatile_ops (stmt)
4824 2018312 : || contains_vce_or_bfcref_p (rhs)
4825 1837835 : || contains_vce_or_bfcref_p (lhs)
4826 8777740 : || stmt_ends_bb_p (stmt))
4827 : {
4828 : /* No need to copy into a constant, it comes pre-initialized. */
4829 5202470 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4830 17482 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4831 : gsi, false, false, loc);
4832 5184988 : if (access_has_children_p (lacc))
4833 : {
4834 252200 : gimple_stmt_iterator alt_gsi = gsi_none ();
4835 252200 : if (stmt_ends_bb_p (stmt))
4836 : {
4837 75071 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
4838 75071 : gsi = &alt_gsi;
4839 : }
4840 252200 : generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
4841 : gsi, true, true, loc);
4842 : }
4843 5184988 : sra_stats.separate_lhs_rhs_handling++;
4844 :
4845 : /* This gimplification must be done after generate_subtree_copies,
4846 : lest we insert the subtree copies in the middle of the gimplified
4847 : sequence. */
4848 5184988 : if (force_gimple_rhs)
4849 26886 : rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
4850 : true, GSI_SAME_STMT);
4851 5184988 : if (gimple_assign_rhs1 (stmt) != rhs)
4852 : {
4853 3258951 : modify_this_stmt = true;
4854 3258951 : gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
4855 3258951 : gcc_assert (stmt == gsi_stmt (orig_gsi));
4856 : }
4857 :
4858 6850740 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4859 : }
4860 : else
4861 : {
4862 2466389 : if (access_has_children_p (lacc)
4863 1758418 : && access_has_children_p (racc)
4864 : /* When an access represents an unscalarizable region, it usually
4865 : represents accesses with variable offset and thus must not be used
4866 : to generate new memory accesses. */
4867 464960 : && !lacc->grp_unscalarizable_region
4868 464955 : && !racc->grp_unscalarizable_region)
4869 : {
4870 464949 : struct subreplacement_assignment_data sad;
4871 :
4872 464949 : sad.left_offset = lacc->offset;
4873 464949 : sad.assignment_lhs = lhs;
4874 464949 : sad.assignment_rhs = rhs;
4875 464949 : sad.top_racc = racc;
4876 464949 : sad.old_gsi = *gsi;
4877 464949 : sad.new_gsi = gsi;
4878 464949 : sad.loc = gimple_location (stmt);
4879 464949 : sad.refreshed = SRA_UDH_NONE;
4880 :
4881 464949 : if (lacc->grp_read && !lacc->grp_covered)
4882 97826 : handle_unscalarized_data_in_subtree (&sad);
4883 :
4884 464949 : load_assign_lhs_subreplacements (lacc, &sad);
4885 464949 : if (sad.refreshed != SRA_UDH_RIGHT)
4886 : {
4887 437276 : gsi_next (gsi);
4888 437276 : unlink_stmt_vdef (stmt);
4889 437276 : gsi_remove (&sad.old_gsi, true);
4890 437276 : release_defs (stmt);
4891 437276 : sra_stats.deleted++;
4892 437276 : return SRA_AM_REMOVED;
4893 : }
4894 : }
4895 : else
4896 : {
4897 1293458 : if (access_has_children_p (racc)
4898 485065 : && !racc->grp_unscalarized_data
4899 422455 : && TREE_CODE (lhs) != SSA_NAME)
4900 : {
4901 422454 : if (dump_file)
4902 : {
4903 5 : fprintf (dump_file, "Removing load: ");
4904 5 : print_gimple_stmt (dump_file, stmt, 0);
4905 : }
4906 422454 : generate_subtree_copies (racc->first_child, lhs,
4907 : racc->offset, 0, 0, gsi,
4908 : false, false, loc);
4909 422454 : gcc_assert (stmt == gsi_stmt (*gsi));
4910 422454 : unlink_stmt_vdef (stmt);
4911 422454 : gsi_remove (gsi, true);
4912 422454 : release_defs (stmt);
4913 422454 : sra_stats.deleted++;
4914 422454 : return SRA_AM_REMOVED;
4915 : }
4916 : /* Restore the aggregate RHS from its components so the
4917 : prevailing aggregate copy does the right thing. */
4918 933615 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4919 62596 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4920 : gsi, false, false, loc);
4921 : /* Re-load the components of the aggregate copy destination.
4922 : But use the RHS aggregate to load from to expose more
4923 : optimization opportunities. */
4924 871004 : if (access_has_children_p (lacc))
4925 : {
4926 243028 : generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
4927 : 0, 0, gsi, true, true, loc);
4928 243028 : if (lacc->grp_covered)
4929 : {
4930 175997 : unlink_stmt_vdef (stmt);
4931 175997 : gsi_remove (& orig_gsi, true);
4932 175997 : release_defs (stmt);
4933 175997 : sra_stats.deleted++;
4934 175997 : return SRA_AM_REMOVED;
4935 : }
4936 : }
4937 : }
4938 :
4939 722680 : return SRA_AM_NONE;
4940 : }
4941 : }
4942 :
4943 : /* Set any scalar replacements of values in the constant pool to the initial
4944 : value of the constant. (Constant-pool decls like *.LC0 have effectively
4945 : been initialized before the program starts, we must do the same for their
4946 : replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4947 : the function's entry block. */
4948 :
4949 : static void
4950 421956 : initialize_constant_pool_replacements (void)
4951 : {
4952 421956 : gimple_seq seq = NULL;
4953 421956 : gimple_stmt_iterator gsi = gsi_start (seq);
4954 421956 : bitmap_iterator bi;
4955 421956 : unsigned i;
4956 :
4957 2184715 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
4958 : {
4959 1762759 : tree var = candidate (i);
4960 1762759 : if (!constant_decl_p (var))
4961 1762678 : continue;
4962 :
4963 81 : struct access *access = get_first_repr_for_decl (var);
4964 :
4965 6386 : while (access)
4966 : {
4967 6224 : if (access->replacement_decl)
4968 : {
4969 4981 : gassign *stmt
4970 4981 : = gimple_build_assign (get_access_replacement (access),
4971 : unshare_expr (access->expr));
4972 4981 : if (dump_file && (dump_flags & TDF_DETAILS))
4973 : {
4974 0 : fprintf (dump_file, "Generating constant initializer: ");
4975 0 : print_gimple_stmt (dump_file, stmt, 0);
4976 0 : fprintf (dump_file, "\n");
4977 : }
4978 4981 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
4979 4981 : update_stmt (stmt);
4980 : }
4981 :
4982 6224 : if (access->first_child)
4983 : access = access->first_child;
4984 4981 : else if (access->next_sibling)
4985 : access = access->next_sibling;
4986 : else
4987 : {
4988 2351 : while (access->parent && !access->next_sibling)
4989 : access = access->parent;
4990 1108 : if (access->next_sibling)
4991 : access = access->next_sibling;
4992 : else
4993 81 : access = access->next_grp;
4994 : }
4995 : }
4996 : }
4997 :
4998 421956 : seq = gsi_seq (gsi);
4999 421956 : if (seq)
5000 76 : gsi_insert_seq_on_edge_immediate (
5001 76 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5002 421956 : }
5003 :
5004 : /* Traverse the function body and all modifications as decided in
5005 : analyze_all_variable_accesses. Return true iff the CFG has been
5006 : changed. */
5007 :
5008 : static bool
5009 421956 : sra_modify_function_body (void)
5010 : {
5011 421956 : bool cfg_changed = false;
5012 421956 : basic_block bb;
5013 :
5014 421956 : initialize_constant_pool_replacements ();
5015 :
5016 9851999 : FOR_EACH_BB_FN (bb, cfun)
5017 : {
5018 9430043 : gimple_stmt_iterator gsi = gsi_start_bb (bb);
5019 80390421 : while (!gsi_end_p (gsi))
5020 : {
5021 70960378 : gimple *stmt = gsi_stmt (gsi);
5022 70960378 : enum assignment_mod_result assign_result;
5023 70960378 : bool modified = false, deleted = false;
5024 70960378 : tree *t;
5025 70960378 : unsigned i;
5026 :
5027 70960378 : switch (gimple_code (stmt))
5028 : {
5029 420299 : case GIMPLE_RETURN:
5030 420299 : t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
5031 420299 : if (*t != NULL_TREE)
5032 273679 : modified |= sra_modify_expr (t, false, &gsi, &gsi);
5033 : break;
5034 :
5035 25390258 : case GIMPLE_ASSIGN:
5036 25390258 : assign_result = sra_modify_assign (stmt, &gsi);
5037 25390258 : modified |= assign_result == SRA_AM_MODIFIED;
5038 25390258 : deleted = assign_result == SRA_AM_REMOVED;
5039 25390258 : break;
5040 :
5041 4222409 : case GIMPLE_CALL:
5042 : /* Handle calls to .DEFERRED_INIT specially. */
5043 4222409 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
5044 : {
5045 82033 : assign_result = sra_modify_deferred_init (stmt, &gsi);
5046 82033 : modified |= assign_result == SRA_AM_MODIFIED;
5047 82033 : deleted = assign_result == SRA_AM_REMOVED;
5048 : }
5049 : else
5050 : {
5051 4140376 : gcall *call = as_a <gcall *> (stmt);
5052 4140376 : gimple_stmt_iterator call_gsi = gsi;
5053 :
5054 : /* Operands must be processed before the lhs. */
5055 12353910 : for (i = 0; i < gimple_call_num_args (call); i++)
5056 : {
5057 8213534 : int flags = gimple_call_arg_flags (call, i);
5058 8213534 : t = gimple_call_arg_ptr (call, i);
5059 8213534 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi, flags);
5060 : }
5061 4140376 : if (gimple_call_chain (call))
5062 : {
5063 29294 : t = gimple_call_chain_ptr (call);
5064 29294 : int flags = gimple_call_static_chain_flags (call);
5065 29294 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi,
5066 : flags);
5067 : }
5068 4140376 : if (gimple_call_lhs (call))
5069 : {
5070 1732202 : t = gimple_call_lhs_ptr (call);
5071 1732202 : modified |= sra_modify_expr (t, true, &call_gsi, &gsi);
5072 : }
5073 : }
5074 : break;
5075 :
5076 7236 : case GIMPLE_ASM:
5077 7236 : {
5078 7236 : gimple_stmt_iterator stmt_gsi = gsi;
5079 7236 : gasm *asm_stmt = as_a <gasm *> (stmt);
5080 18101 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5081 : {
5082 3629 : t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5083 3629 : modified |= sra_modify_expr (t, false, &stmt_gsi, &gsi);
5084 : }
5085 11157 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5086 : {
5087 3921 : t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5088 3921 : modified |= sra_modify_expr (t, true, &stmt_gsi, &gsi);
5089 : }
5090 : }
5091 7236 : break;
5092 :
5093 : default:
5094 : break;
5095 : }
5096 :
5097 29893582 : if (modified)
5098 : {
5099 5475439 : update_stmt (stmt);
5100 5475439 : if (maybe_clean_eh_stmt (stmt)
5101 5475439 : && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5102 : cfg_changed = true;
5103 : }
5104 70960378 : if (!deleted)
5105 69078886 : gsi_next (&gsi);
5106 : }
5107 : }
5108 :
5109 421956 : gsi_commit_edge_inserts ();
5110 421956 : return cfg_changed;
5111 : }
5112 :
5113 : /* Generate statements initializing scalar replacements of parts of function
5114 : parameters. */
5115 :
5116 : static void
5117 421956 : initialize_parameter_reductions (void)
5118 : {
5119 421956 : gimple_stmt_iterator gsi;
5120 421956 : gimple_seq seq = NULL;
5121 421956 : tree parm;
5122 :
5123 421956 : gsi = gsi_start (seq);
5124 421956 : for (parm = DECL_ARGUMENTS (current_function_decl);
5125 1262988 : parm;
5126 841032 : parm = DECL_CHAIN (parm))
5127 : {
5128 841032 : vec<access_p> *access_vec;
5129 841032 : struct access *access;
5130 :
5131 841032 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
5132 774222 : continue;
5133 66810 : access_vec = get_base_access_vector (parm);
5134 66810 : if (!access_vec)
5135 0 : continue;
5136 :
5137 66810 : for (access = (*access_vec)[0];
5138 171000 : access;
5139 104190 : access = access->next_grp)
5140 104190 : generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
5141 104190 : EXPR_LOCATION (parm));
5142 : }
5143 :
5144 421956 : seq = gsi_seq (gsi);
5145 421956 : if (seq)
5146 52987 : gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5147 421956 : }
5148 :
5149 : /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
5150 : it reveals there are components of some aggregates to be scalarized, it runs
5151 : the required transformations. */
5152 : static unsigned int
5153 3437811 : perform_intra_sra (void)
5154 : {
5155 3437811 : int ret = 0;
5156 3437811 : sra_initialize ();
5157 :
5158 3437811 : if (!find_var_candidates ())
5159 2679337 : goto out;
5160 :
5161 758474 : if (!scan_function ())
5162 49327 : goto out;
5163 :
5164 709147 : if (!analyze_all_variable_accesses ())
5165 287191 : goto out;
5166 :
5167 421956 : if (sra_modify_function_body ())
5168 : ret = TODO_update_ssa | TODO_cleanup_cfg;
5169 : else
5170 421934 : ret = TODO_update_ssa;
5171 421956 : initialize_parameter_reductions ();
5172 :
5173 421956 : statistics_counter_event (cfun, "Scalar replacements created",
5174 : sra_stats.replacements);
5175 421956 : statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
5176 421956 : statistics_counter_event (cfun, "Subtree copy stmts",
5177 : sra_stats.subtree_copies);
5178 421956 : statistics_counter_event (cfun, "Subreplacement stmts",
5179 : sra_stats.subreplacements);
5180 421956 : statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
5181 421956 : statistics_counter_event (cfun, "Separate LHS and RHS handling",
5182 : sra_stats.separate_lhs_rhs_handling);
5183 :
5184 3437811 : out:
5185 3437811 : sra_deinitialize ();
5186 3437811 : return ret;
5187 : }
5188 :
5189 : /* Perform early intraprocedural SRA. */
5190 : static unsigned int
5191 2400219 : early_intra_sra (void)
5192 : {
5193 2400219 : sra_mode = SRA_MODE_EARLY_INTRA;
5194 0 : return perform_intra_sra ();
5195 : }
5196 :
5197 : /* Perform "late" intraprocedural SRA. */
5198 : static unsigned int
5199 1037592 : late_intra_sra (void)
5200 : {
5201 1037592 : sra_mode = SRA_MODE_INTRA;
5202 0 : return perform_intra_sra ();
5203 : }
5204 :
5205 :
5206 : static bool
5207 3442006 : gate_intra_sra (void)
5208 : {
5209 3442006 : return flag_tree_sra != 0 && dbg_cnt (tree_sra);
5210 : }
5211 :
5212 :
5213 : namespace {
5214 :
5215 : const pass_data pass_data_sra_early =
5216 : {
5217 : GIMPLE_PASS, /* type */
5218 : "esra", /* name */
5219 : OPTGROUP_NONE, /* optinfo_flags */
5220 : TV_TREE_SRA, /* tv_id */
5221 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5222 : 0, /* properties_provided */
5223 : 0, /* properties_destroyed */
5224 : 0, /* todo_flags_start */
5225 : TODO_update_ssa, /* todo_flags_finish */
5226 : };
5227 :
5228 : class pass_sra_early : public gimple_opt_pass
5229 : {
5230 : public:
5231 287872 : pass_sra_early (gcc::context *ctxt)
5232 575744 : : gimple_opt_pass (pass_data_sra_early, ctxt)
5233 : {}
5234 :
5235 : /* opt_pass methods: */
5236 2403979 : bool gate (function *) final override { return gate_intra_sra (); }
5237 2400219 : unsigned int execute (function *) final override
5238 : {
5239 2400219 : return early_intra_sra ();
5240 : }
5241 :
5242 : }; // class pass_sra_early
5243 :
5244 : } // anon namespace
5245 :
5246 : gimple_opt_pass *
5247 287872 : make_pass_sra_early (gcc::context *ctxt)
5248 : {
5249 287872 : return new pass_sra_early (ctxt);
5250 : }
5251 :
5252 : namespace {
5253 :
5254 : const pass_data pass_data_sra =
5255 : {
5256 : GIMPLE_PASS, /* type */
5257 : "sra", /* name */
5258 : OPTGROUP_NONE, /* optinfo_flags */
5259 : TV_TREE_SRA, /* tv_id */
5260 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5261 : 0, /* properties_provided */
5262 : 0, /* properties_destroyed */
5263 : TODO_update_address_taken, /* todo_flags_start */
5264 : TODO_update_ssa, /* todo_flags_finish */
5265 : };
5266 :
5267 : class pass_sra : public gimple_opt_pass
5268 : {
5269 : public:
5270 287872 : pass_sra (gcc::context *ctxt)
5271 575744 : : gimple_opt_pass (pass_data_sra, ctxt)
5272 : {}
5273 :
5274 : /* opt_pass methods: */
5275 1038027 : bool gate (function *) final override { return gate_intra_sra (); }
5276 1037592 : unsigned int execute (function *) final override { return late_intra_sra (); }
5277 :
5278 : }; // class pass_sra
5279 :
5280 : } // anon namespace
5281 :
5282 : gimple_opt_pass *
5283 287872 : make_pass_sra (gcc::context *ctxt)
5284 : {
5285 287872 : return new pass_sra (ctxt);
5286 : }
5287 :
5288 :
5289 : /* If type T cannot be totally scalarized, return false. Otherwise return true
5290 : and push to the vector within PC offsets and lengths of all padding in the
5291 : type as total scalarization would encounter it. */
5292 :
5293 : static bool
5294 70886 : check_ts_and_push_padding_to_vec (tree type, sra_padding_collecting *pc)
5295 : {
5296 70886 : if (!totally_scalarizable_type_p (type, true /* optimistic value */,
5297 : 0, pc))
5298 : return false;
5299 :
5300 62906 : pc->record_padding (tree_to_shwi (TYPE_SIZE (type)));
5301 62906 : return true;
5302 : }
5303 :
5304 : /* Given two types in an assignment, return true either if any one cannot be
5305 : totally scalarized or if they have padding (i.e. not copied bits) */
5306 :
5307 : bool
5308 39433 : sra_total_scalarization_would_copy_same_data_p (tree t1, tree t2)
5309 : {
5310 39433 : sra_padding_collecting p1;
5311 39433 : if (!check_ts_and_push_padding_to_vec (t1, &p1))
5312 : return true;
5313 :
5314 31453 : sra_padding_collecting p2;
5315 31453 : if (!check_ts_and_push_padding_to_vec (t2, &p2))
5316 : return true;
5317 :
5318 31453 : unsigned l = p1.m_padding.length ();
5319 62906 : if (l != p2.m_padding.length ())
5320 : return false;
5321 39322 : for (unsigned i = 0; i < l; i++)
5322 7872 : if (p1.m_padding[i].first != p2.m_padding[i].first
5323 7872 : || p1.m_padding[i].second != p2.m_padding[i].second)
5324 : return false;
5325 :
5326 : return true;
5327 31453 : }
5328 :
|
