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 77829469 : uid_decl_hasher::hash (const tree_node *item)
307 : {
308 77829469 : return item->decl_minimal.uid;
309 : }
310 :
311 : /* Return true if the DECL_UID in both trees are equal. */
312 :
313 : inline bool
314 89619823 : uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
315 : {
316 89619823 : 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 14241377 : candidate (unsigned uid)
327 : {
328 14241377 : tree_node t;
329 14241377 : t.decl_minimal.uid = uid;
330 14241377 : 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 15790238 : access_has_children_p (struct access *acc)
474 : {
475 8413031 : 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 22983131 : 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 10123974 : find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
506 : HOST_WIDE_INT size)
507 : {
508 25816668 : while (access && (access->offset != offset || access->size != size))
509 : {
510 5568720 : struct access *child = access->first_child;
511 :
512 12128638 : while (child && (child->offset + child->size <= offset))
513 6559918 : 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 10123974 : if (access)
521 10167370 : while (access->first_child
522 3053860 : && access->first_child->offset == offset
523 13132062 : && access->first_child->size == size)
524 : access = access->first_child;
525 :
526 10123974 : return access;
527 : }
528 :
529 : /* Return the first group representative for DECL or NULL if none exists. */
530 :
531 : static struct access *
532 18916073 : get_first_repr_for_decl (tree base)
533 : {
534 18916073 : vec<access_p> *access_vec;
535 :
536 18916073 : access_vec = get_base_access_vector (base);
537 18916073 : if (!access_vec)
538 : return NULL;
539 :
540 18916073 : 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 9080765 : get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
549 : HOST_WIDE_INT size)
550 : {
551 9080765 : struct access *access;
552 :
553 9080765 : access = get_first_repr_for_decl (base);
554 21023378 : while (access && (access->offset + access->size <= offset))
555 2861848 : access = access->next_grp;
556 9080765 : if (!access)
557 : return NULL;
558 :
559 9080765 : 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 1297655 : add_link_to_rhs (struct access *racc, struct assign_link *link)
566 : {
567 1297655 : gcc_assert (link->racc == racc);
568 :
569 1297655 : if (!racc->first_rhs_link)
570 : {
571 1297655 : gcc_assert (!racc->last_rhs_link);
572 1297655 : racc->first_rhs_link = link;
573 : }
574 : else
575 0 : racc->last_rhs_link->next_rhs = link;
576 :
577 1297655 : racc->last_rhs_link = link;
578 1297655 : link->next_rhs = NULL;
579 1297655 : }
580 :
581 : /* Add LINK to the linked list of lhs assign links of LACC. */
582 :
583 : static void
584 1297655 : add_link_to_lhs (struct access *lacc, struct assign_link *link)
585 : {
586 1297655 : gcc_assert (link->lacc == lacc);
587 :
588 1297655 : if (!lacc->first_lhs_link)
589 : {
590 1297655 : gcc_assert (!lacc->last_lhs_link);
591 1297655 : lacc->first_lhs_link = link;
592 : }
593 : else
594 0 : lacc->last_lhs_link->next_lhs = link;
595 :
596 1297655 : lacc->last_lhs_link = link;
597 1297655 : link->next_lhs = NULL;
598 1297655 : }
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 5174812 : relink_to_new_repr (struct access *new_acc, struct access *old_acc)
604 : {
605 5174812 : if (old_acc->first_rhs_link)
606 : {
607 :
608 852298 : if (new_acc->first_rhs_link)
609 : {
610 279172 : gcc_assert (!new_acc->last_rhs_link->next_rhs);
611 279172 : gcc_assert (!old_acc->last_rhs_link
612 : || !old_acc->last_rhs_link->next_rhs);
613 :
614 279172 : new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link;
615 279172 : new_acc->last_rhs_link = old_acc->last_rhs_link;
616 : }
617 : else
618 : {
619 573126 : gcc_assert (!new_acc->last_rhs_link);
620 :
621 573126 : new_acc->first_rhs_link = old_acc->first_rhs_link;
622 573126 : new_acc->last_rhs_link = old_acc->last_rhs_link;
623 : }
624 852298 : old_acc->first_rhs_link = old_acc->last_rhs_link = NULL;
625 : }
626 : else
627 4322514 : gcc_assert (!old_acc->last_rhs_link);
628 :
629 5174812 : if (old_acc->first_lhs_link)
630 : {
631 :
632 351592 : if (new_acc->first_lhs_link)
633 : {
634 151199 : gcc_assert (!new_acc->last_lhs_link->next_lhs);
635 151199 : gcc_assert (!old_acc->last_lhs_link
636 : || !old_acc->last_lhs_link->next_lhs);
637 :
638 151199 : new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link;
639 151199 : new_acc->last_lhs_link = old_acc->last_lhs_link;
640 : }
641 : else
642 : {
643 200393 : gcc_assert (!new_acc->last_lhs_link);
644 :
645 200393 : new_acc->first_lhs_link = old_acc->first_lhs_link;
646 200393 : new_acc->last_lhs_link = old_acc->last_lhs_link;
647 : }
648 351592 : old_acc->first_lhs_link = old_acc->last_lhs_link = NULL;
649 : }
650 : else
651 4823220 : gcc_assert (!old_acc->last_lhs_link);
652 :
653 5174812 : }
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 4571188 : add_access_to_rhs_work_queue (struct access *access)
660 : {
661 4571188 : if (access->first_rhs_link && !access->grp_rhs_queued)
662 : {
663 1501935 : gcc_assert (!access->next_rhs_queued);
664 1501935 : access->next_rhs_queued = rhs_work_queue_head;
665 1501935 : access->grp_rhs_queued = 1;
666 1501935 : rhs_work_queue_head = access;
667 : }
668 4571188 : }
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 1645542 : add_access_to_lhs_work_queue (struct access *access)
675 : {
676 1645542 : if (access->first_lhs_link && !access->grp_lhs_queued)
677 : {
678 1299457 : gcc_assert (!access->next_lhs_queued);
679 1299457 : access->next_lhs_queued = lhs_work_queue_head;
680 1299457 : access->grp_lhs_queued = 1;
681 1299457 : lhs_work_queue_head = access;
682 : }
683 1645542 : }
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 1501935 : pop_access_from_rhs_work_queue (void)
690 : {
691 1501935 : struct access *access = rhs_work_queue_head;
692 :
693 1501935 : rhs_work_queue_head = access->next_rhs_queued;
694 1501935 : access->next_rhs_queued = NULL;
695 1501935 : access->grp_rhs_queued = 0;
696 1501935 : 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 1299457 : pop_access_from_lhs_work_queue (void)
704 : {
705 1299457 : struct access *access = lhs_work_queue_head;
706 :
707 1299457 : lhs_work_queue_head = access->next_lhs_queued;
708 1299457 : access->next_lhs_queued = NULL;
709 1299457 : access->grp_lhs_queued = 0;
710 1299457 : return access;
711 : }
712 :
713 : /* Allocate necessary structures. */
714 :
715 : static void
716 3474809 : sra_initialize (void)
717 : {
718 3474809 : candidate_bitmap = BITMAP_ALLOC (NULL);
719 6949618 : candidates = new hash_table<uid_decl_hasher>
720 6467094 : (vec_safe_length (cfun->local_decls) / 2);
721 3474809 : should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
722 3474809 : cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
723 3474809 : disqualified_constants = BITMAP_ALLOC (NULL);
724 3474809 : passed_by_ref_in_call = BITMAP_ALLOC (NULL);
725 3474809 : gcc_obstack_init (&name_obstack);
726 3474809 : base_access_vec = new hash_map<tree, auto_vec<access_p> >;
727 3474809 : memset (&sra_stats, 0, sizeof (sra_stats));
728 3474809 : }
729 :
730 : /* Deallocate all general structures. */
731 :
732 : static void
733 3474809 : sra_deinitialize (void)
734 : {
735 3474809 : BITMAP_FREE (candidate_bitmap);
736 3474809 : delete candidates;
737 3474809 : candidates = NULL;
738 3474809 : BITMAP_FREE (should_scalarize_away_bitmap);
739 3474809 : BITMAP_FREE (cannot_scalarize_away_bitmap);
740 3474809 : BITMAP_FREE (disqualified_constants);
741 3474809 : BITMAP_FREE (passed_by_ref_in_call);
742 3474809 : access_pool.release ();
743 3474809 : assign_link_pool.release ();
744 3474809 : obstack_free (&name_obstack, NULL);
745 :
746 6949618 : delete base_access_vec;
747 3474809 : }
748 :
749 : /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
750 :
751 41271868 : static bool constant_decl_p (tree decl)
752 : {
753 35748041 : 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 4347241 : disqualify_candidate (tree decl, const char *reason)
761 : {
762 4347241 : if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
763 2303985 : candidates->remove_elt_with_hash (decl, DECL_UID (decl));
764 4347241 : if (constant_decl_p (decl))
765 4137 : bitmap_set_bit (disqualified_constants, DECL_UID (decl));
766 :
767 4347241 : 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 4347241 : }
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 8091310 : type_internals_preclude_sra_p_1 (tree type, const char **msg,
781 : hash_set<tree> *visited_types)
782 : {
783 8091310 : tree fld;
784 8091310 : tree et;
785 :
786 8091310 : if (visited_types->contains (type))
787 : return false;
788 7797131 : visited_types->add (type);
789 :
790 7797131 : switch (TREE_CODE (type))
791 : {
792 7132678 : case RECORD_TYPE:
793 7132678 : case UNION_TYPE:
794 7132678 : case QUAL_UNION_TYPE:
795 135783529 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
796 128661310 : if (TREE_CODE (fld) == FIELD_DECL)
797 : {
798 16453612 : if (TREE_CODE (fld) == FUNCTION_DECL)
799 : continue;
800 16453612 : tree ft = TREE_TYPE (fld);
801 :
802 16453612 : if (TREE_THIS_VOLATILE (fld))
803 : {
804 905 : *msg = "volatile structure field";
805 905 : return true;
806 : }
807 16452707 : if (!DECL_FIELD_OFFSET (fld))
808 : {
809 0 : *msg = "no structure field offset";
810 0 : return true;
811 : }
812 16452707 : if (!DECL_SIZE (fld))
813 : {
814 8443 : *msg = "zero structure field size";
815 8443 : return true;
816 : }
817 16444264 : if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
818 : {
819 0 : *msg = "structure field offset not fixed";
820 0 : return true;
821 : }
822 16444264 : if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
823 : {
824 0 : *msg = "structure field size not fixed";
825 0 : return true;
826 : }
827 16444264 : if (!tree_fits_shwi_p (bit_position (fld)))
828 : {
829 0 : *msg = "structure field size too big";
830 0 : return true;
831 : }
832 16444264 : if (AGGREGATE_TYPE_P (ft)
833 16444264 : && int_bit_position (fld) % BITS_PER_UNIT != 0)
834 : {
835 0 : *msg = "structure field is bit field";
836 0 : return true;
837 : }
838 :
839 16444264 : if (AGGREGATE_TYPE_P (ft)
840 16444264 : && type_internals_preclude_sra_p_1 (ft, msg, visited_types))
841 : return true;
842 : }
843 :
844 : return false;
845 :
846 543761 : case ARRAY_TYPE:
847 543761 : et = TREE_TYPE (type);
848 :
849 543761 : if (TYPE_VOLATILE (et))
850 : {
851 0 : *msg = "element type is volatile";
852 0 : return true;
853 : }
854 :
855 543761 : if (AGGREGATE_TYPE_P (et)
856 543761 : && 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 4728000 : type_internals_preclude_sra_p (tree type, const char **msg)
871 : {
872 4728000 : hash_set<tree> visited_types;
873 4728000 : return type_internals_preclude_sra_p_1 (type, msg, &visited_types);
874 4728000 : }
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 14496323 : create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
883 : {
884 14496323 : struct access *access = access_pool.allocate ();
885 :
886 14496323 : memset (access, 0, sizeof (struct access));
887 14496323 : access->base = base;
888 14496323 : access->offset = offset;
889 14496323 : access->size = size;
890 :
891 14496323 : base_access_vec->get_or_insert (base).safe_push (access);
892 :
893 14496323 : 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 27702756 : create_access (tree expr, gimple *stmt, bool write)
904 : {
905 27702756 : struct access *access;
906 27702756 : poly_int64 poffset, psize, pmax_size;
907 27702756 : tree base = expr;
908 27702756 : bool reverse, unscalarizable_region = false;
909 :
910 27702756 : 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 27702756 : if (constant_decl_p (base)
915 3776 : && !bitmap_bit_p (disqualified_constants, DECL_UID (base)))
916 : {
917 3776 : if (expr != base
918 349 : && !is_gimple_reg_type (TREE_TYPE (expr))
919 3862 : && 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 3776 : maybe_add_sra_candidate (base);
929 : }
930 :
931 27702756 : if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
932 13199330 : return NULL;
933 :
934 14503426 : if (write && TREE_READONLY (base))
935 : {
936 6203 : disqualify_candidate (base, "Encountered a store to a read-only decl.");
937 6203 : return NULL;
938 : }
939 :
940 14497223 : HOST_WIDE_INT offset, size, max_size;
941 14497223 : if (!poffset.is_constant (&offset)
942 14497223 : || !psize.is_constant (&size)
943 14497223 : || !pmax_size.is_constant (&max_size))
944 : {
945 : disqualify_candidate (base, "Encountered a polynomial-sized access.");
946 : return NULL;
947 : }
948 :
949 14497223 : if (size != max_size)
950 : {
951 378371 : size = max_size;
952 378371 : unscalarizable_region = true;
953 : }
954 14497223 : if (size == 0)
955 : return NULL;
956 14497221 : if (offset < 0)
957 : {
958 34 : disqualify_candidate (base, "Encountered a negative offset access.");
959 34 : return NULL;
960 : }
961 14497187 : if (size < 0)
962 : {
963 24 : disqualify_candidate (base, "Encountered an unconstrained access.");
964 24 : return NULL;
965 : }
966 14497163 : 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 14496324 : if (TREE_CODE (TREE_TYPE (expr)) == BITINT_TYPE
972 14496324 : && size > WIDE_INT_MAX_PRECISION - 1)
973 : {
974 1 : disqualify_candidate (base, "Encountered too large _BitInt access.");
975 1 : return NULL;
976 : }
977 :
978 14496323 : access = create_access_1 (base, offset, size);
979 14496323 : access->expr = expr;
980 14496323 : access->type = TREE_TYPE (expr);
981 14496323 : access->write = write;
982 14496323 : access->grp_unscalarizable_region = unscalarizable_region;
983 14496323 : access->grp_same_access_path = true;
984 14496323 : access->stmt = stmt;
985 14496323 : access->reverse = reverse;
986 :
987 14496323 : 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 21483 : prepare_iteration_over_array_elts (tree type, HOST_WIDE_INT *el_size,
997 : offset_int *idx, offset_int *max)
998 : {
999 21483 : tree elem_size = TYPE_SIZE (TREE_TYPE (type));
1000 21483 : gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
1001 21483 : *el_size = tree_to_shwi (elem_size);
1002 21483 : gcc_assert (*el_size > 0);
1003 :
1004 21483 : tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1005 21483 : gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1006 21483 : tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1007 : /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1008 21483 : if (!maxidx)
1009 : return false;
1010 21483 : gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1011 21483 : 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 21483 : *idx = wi::to_offset (minidx);
1015 21483 : *max = wi::to_offset (maxidx);
1016 21483 : if (!TYPE_UNSIGNED (domain))
1017 : {
1018 21483 : *idx = wi::sext (*idx, TYPE_PRECISION (domain));
1019 21483 : *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 67767 : 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 190146 : void sra_padding_collecting::record_padding (HOST_WIDE_INT offset)
1045 : {
1046 190146 : if (offset > m_data_until)
1047 : {
1048 13588 : HOST_WIDE_INT psz = offset - m_data_until;
1049 13588 : 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 13588 : m_padding.safe_push (std::make_pair (m_data_until, psz));
1055 : }
1056 190146 : }
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 2814101 : totally_scalarizable_type_p (tree type, bool const_decl,
1073 : HOST_WIDE_INT total_offset,
1074 : sra_padding_collecting *pc)
1075 : {
1076 2814101 : if (is_gimple_reg_type (type))
1077 : {
1078 1808714 : if (pc)
1079 : {
1080 122330 : pc->record_padding (total_offset);
1081 122330 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1082 : }
1083 1808714 : return true;
1084 : }
1085 1005387 : if (type_contains_placeholder_p (type))
1086 : return false;
1087 :
1088 1005387 : bool have_predecessor_field = false;
1089 1005387 : HOST_WIDE_INT prev_pos = 0;
1090 :
1091 1005387 : switch (TREE_CODE (type))
1092 : {
1093 961407 : case RECORD_TYPE:
1094 14022949 : for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1095 13092072 : if (TREE_CODE (fld) == FIELD_DECL)
1096 : {
1097 2043096 : tree ft = TREE_TYPE (fld);
1098 :
1099 2043096 : if (!DECL_SIZE (fld))
1100 : return false;
1101 2043096 : if (zerop (DECL_SIZE (fld)))
1102 51722 : continue;
1103 :
1104 1991374 : HOST_WIDE_INT pos = int_bit_position (fld);
1105 1991374 : if (have_predecessor_field
1106 1991374 : && pos <= prev_pos)
1107 : return false;
1108 :
1109 1991374 : have_predecessor_field = true;
1110 1991374 : prev_pos = pos;
1111 :
1112 1991374 : if (DECL_BIT_FIELD (fld))
1113 : return false;
1114 :
1115 1988636 : if (!totally_scalarizable_type_p (ft, const_decl, total_offset + pos,
1116 : pc))
1117 : return false;
1118 : }
1119 :
1120 : return true;
1121 :
1122 27955 : case ARRAY_TYPE:
1123 27955 : {
1124 27955 : HOST_WIDE_INT min_elem_size;
1125 27955 : if (const_decl)
1126 : min_elem_size = 0;
1127 : else
1128 19792 : min_elem_size = BITS_PER_UNIT;
1129 :
1130 27955 : if (TYPE_DOMAIN (type) == NULL_TREE
1131 27955 : || !tree_fits_shwi_p (TYPE_SIZE (type))
1132 27955 : || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1133 27955 : || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1134 50345 : || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1135 : return false;
1136 22390 : if (tree_to_shwi (TYPE_SIZE (type)) == 0
1137 22390 : && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1138 : /* Zero-element array, should not prevent scalarization. */
1139 : ;
1140 22390 : else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1141 22390 : || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1142 : /* Variable-length array, do not allow scalarization. */
1143 : return false;
1144 :
1145 22354 : unsigned old_padding_len = 0;
1146 22354 : if (pc)
1147 8002 : old_padding_len = pc->m_padding.length ();
1148 22354 : tree elem = TREE_TYPE (type);
1149 22354 : if (!totally_scalarizable_type_p (elem, const_decl, total_offset, pc))
1150 : return false;
1151 22215 : if (pc)
1152 : {
1153 8002 : unsigned new_padding_len = pc->m_padding.length ();
1154 8002 : HOST_WIDE_INT el_size;
1155 8002 : offset_int idx, max;
1156 8002 : if (!prepare_iteration_over_array_elts (type, &el_size, &idx, &max))
1157 0 : return true;
1158 8002 : pc->record_padding (total_offset + el_size);
1159 8002 : ++idx;
1160 8002 : for (HOST_WIDE_INT pos = total_offset + el_size;
1161 158590 : idx <= max;
1162 150588 : pos += el_size, ++idx)
1163 : {
1164 150615 : 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 8002 : 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 56951634 : contains_view_convert_expr_p (const_tree ref)
1185 : {
1186 78473337 : while (handled_component_p (ref))
1187 : {
1188 21531767 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1189 : return true;
1190 21521703 : 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 7558762 : contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1203 : {
1204 9769251 : while (handled_component_p (ref))
1205 : {
1206 2594668 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1207 2594668 : || (TREE_CODE (ref) == COMPONENT_REF
1208 1880320 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1209 : {
1210 384179 : if (type_changing_p)
1211 200056 : *type_changing_p = true;
1212 384179 : return true;
1213 : }
1214 2210489 : ref = TREE_OPERAND (ref, 0);
1215 : }
1216 :
1217 7174583 : if (!type_changing_p
1218 3471112 : || TREE_CODE (ref) != MEM_REF
1219 7284341 : || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1220 : return false;
1221 :
1222 109758 : tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1223 109758 : if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1224 109758 : != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1225 84744 : *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 988524 : disqualify_base_of_expr (tree t, const char *reason)
1235 : {
1236 988524 : t = get_base_address (t);
1237 988524 : if (t && DECL_P (t))
1238 829046 : disqualify_candidate (t, reason);
1239 988524 : }
1240 :
1241 : /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1242 :
1243 : static bool
1244 140229 : sra_handled_bf_read_p (tree expr)
1245 : {
1246 140229 : uint64_t size, offset;
1247 140229 : if (bit_field_size (expr).is_constant (&size)
1248 140229 : && bit_field_offset (expr).is_constant (&offset)
1249 140229 : && size % BITS_PER_UNIT == 0
1250 140229 : && offset % BITS_PER_UNIT == 0
1251 140297 : && pow2p_hwi (size))
1252 140137 : 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 58925164 : 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 58925164 : if (TREE_CODE (expr) == ADDR_EXPR)
1267 : {
1268 1973529 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1269 1973529 : gcc_assert (!DECL_P (base)
1270 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)));
1271 1973529 : return NULL;
1272 : }
1273 :
1274 56951635 : struct access *ret = NULL;
1275 56951635 : bool partial_ref;
1276 :
1277 56951635 : if ((TREE_CODE (expr) == BIT_FIELD_REF
1278 79614 : && (write || !sra_handled_bf_read_p (expr)))
1279 56950517 : || TREE_CODE (expr) == IMAGPART_EXPR
1280 113877732 : || TREE_CODE (expr) == REALPART_EXPR)
1281 : {
1282 48717 : expr = TREE_OPERAND (expr, 0);
1283 48717 : partial_ref = true;
1284 : }
1285 : else
1286 : partial_ref = false;
1287 :
1288 56951635 : 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 57242651 : if (contains_view_convert_expr_p (TREE_CODE (expr) == VIEW_CONVERT_EXPR
1297 291017 : ? TREE_OPERAND (expr, 0) : expr))
1298 : {
1299 10064 : disqualify_base_of_expr (expr, "V_C_E under a different handled "
1300 : "component.");
1301 10064 : return NULL;
1302 : }
1303 :
1304 56941570 : if (TREE_THIS_VOLATILE (expr))
1305 : {
1306 21996 : disqualify_base_of_expr (expr, "part of a volatile reference.");
1307 21996 : return NULL;
1308 : }
1309 :
1310 56919574 : switch (TREE_CODE (expr))
1311 : {
1312 3476007 : case MEM_REF:
1313 3476007 : if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR)
1314 : return NULL;
1315 : /* fall through */
1316 27702756 : case VAR_DECL:
1317 27702756 : case PARM_DECL:
1318 27702756 : case RESULT_DECL:
1319 27702756 : case COMPONENT_REF:
1320 27702756 : case ARRAY_REF:
1321 27702756 : case ARRAY_RANGE_REF:
1322 27702756 : case BIT_FIELD_REF:
1323 27702756 : case VIEW_CONVERT_EXPR:
1324 27702756 : ret = create_access (expr, stmt, write);
1325 27702756 : break;
1326 :
1327 : default:
1328 : break;
1329 : }
1330 :
1331 55193097 : 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 16329520 : build_access_from_expr (tree expr, gimple *stmt, bool write)
1344 : {
1345 16329520 : struct access *access;
1346 :
1347 16329520 : access = build_access_from_expr_1 (expr, stmt, write);
1348 16329520 : 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 2480937 : if (cannot_scalarize_away_bitmap)
1354 2480937 : bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1355 2480937 : 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 2980269 : abnormal_edge_after_stmt_p (gimple *stmt, enum out_edge_check *oe_check)
1368 : {
1369 2980269 : if (*oe_check == SRA_OUTGOING_EDGES_OK)
1370 : return false;
1371 1737200 : if (*oe_check == SRA_OUTGOING_EDGES_FAIL)
1372 : return true;
1373 1736974 : if (stmt_ends_bb_p (stmt))
1374 : {
1375 709946 : edge e;
1376 709946 : edge_iterator ei;
1377 1851420 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1378 1141960 : if (e->flags & EDGE_ABNORMAL)
1379 : {
1380 486 : *oe_check = SRA_OUTGOING_EDGES_FAIL;
1381 486 : return true;
1382 : }
1383 : }
1384 1736488 : *oe_check = SRA_OUTGOING_EDGES_OK;
1385 1736488 : 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 11568015 : build_access_from_call_arg (tree expr, gimple *stmt, bool can_be_returned,
1398 : enum out_edge_check *oe_check)
1399 : {
1400 11568015 : 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 11567958 : if (TREE_CODE (expr) == ADDR_EXPR)
1410 : {
1411 3935382 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1412 :
1413 3935382 : if (can_be_returned)
1414 : {
1415 955113 : disqualify_base_of_expr (base, "Address possibly returned, "
1416 : "leading to an alis SRA may not know.");
1417 955113 : return false;
1418 : }
1419 2980269 : 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 2979557 : bool read = build_access_from_expr (base, stmt, false);
1427 2979557 : bool write = build_access_from_expr (base, stmt, true);
1428 2979557 : if (read || write)
1429 : {
1430 274248 : 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 274248 : bitmap_set_bit (passed_by_ref_in_call, DECL_UID (base));
1439 274248 : return true;
1440 : }
1441 : else
1442 : return false;
1443 : }
1444 :
1445 7632576 : 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 1461104 : single_non_eh_succ (basic_block bb)
1454 : {
1455 1461104 : edge e, res = NULL;
1456 1461104 : edge_iterator ei;
1457 :
1458 4381843 : FOR_EACH_EDGE (e, ei, bb->succs)
1459 2921159 : if (!(e->flags & EDGE_EH))
1460 : {
1461 1461407 : 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 23618059 : disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1477 : {
1478 23618059 : if (stmt_ends_bb_p (stmt))
1479 : {
1480 1350086 : 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 4021182 : 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 32310544 : build_accesses_from_assign (gimple *stmt)
1507 : {
1508 32310544 : tree lhs, rhs;
1509 32310544 : struct access *lacc, *racc;
1510 :
1511 32310544 : if (!gimple_assign_single_p (stmt)
1512 : /* Scope clobbers don't influence scalarization. */
1513 32310544 : || gimple_clobber_p (stmt))
1514 : return false;
1515 :
1516 21246526 : lhs = gimple_assign_lhs (stmt);
1517 21246526 : rhs = gimple_assign_rhs1 (stmt);
1518 :
1519 21246526 : if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1520 : return false;
1521 :
1522 21246526 : racc = build_access_from_expr_1 (rhs, stmt, false);
1523 21246526 : lacc = build_access_from_expr_1 (lhs, stmt, true);
1524 :
1525 21246526 : bool tbaa_hazard
1526 21246526 : = !types_equal_for_same_type_for_tbaa_p (TREE_TYPE (lhs), TREE_TYPE (rhs));
1527 :
1528 21246526 : if (lacc)
1529 : {
1530 6518767 : lacc->grp_assignment_write = 1;
1531 6518767 : if (storage_order_barrier_p (rhs))
1532 1 : lacc->grp_unscalarizable_region = 1;
1533 :
1534 6518767 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1535 : {
1536 1901907 : bool type_changing_p = false;
1537 1901907 : contains_vce_or_bfcref_p (lhs, &type_changing_p);
1538 1901907 : if (type_changing_p)
1539 133040 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1540 66520 : DECL_UID (lacc->base));
1541 : }
1542 6518767 : if (tbaa_hazard)
1543 841581 : lacc->grp_same_access_path = false;
1544 : }
1545 :
1546 21246526 : if (racc)
1547 : {
1548 5452341 : racc->grp_assignment_read = 1;
1549 5452341 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1550 : {
1551 1769261 : bool type_changing_p = false;
1552 1769261 : contains_vce_or_bfcref_p (rhs, &type_changing_p);
1553 :
1554 3320242 : if (type_changing_p || gimple_has_volatile_ops (stmt))
1555 437306 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1556 218653 : DECL_UID (racc->base));
1557 : else
1558 3101216 : bitmap_set_bit (should_scalarize_away_bitmap,
1559 1550608 : DECL_UID (racc->base));
1560 : }
1561 5452341 : if (storage_order_barrier_p (lhs))
1562 0 : racc->grp_unscalarizable_region = 1;
1563 5452341 : if (tbaa_hazard)
1564 66284 : racc->grp_same_access_path = false;
1565 : }
1566 :
1567 21246526 : if (lacc && racc
1568 1299234 : && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1569 1299234 : && !lacc->grp_unscalarizable_region
1570 1298680 : && !racc->grp_unscalarizable_region
1571 1297883 : && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1572 1297883 : && lacc->size == racc->size
1573 22544181 : && useless_type_conversion_p (lacc->type, racc->type))
1574 : {
1575 1297655 : struct assign_link *link;
1576 :
1577 1297655 : link = assign_link_pool.allocate ();
1578 1297655 : memset (link, 0, sizeof (struct assign_link));
1579 :
1580 1297655 : link->lacc = lacc;
1581 1297655 : link->racc = racc;
1582 1297655 : add_link_to_rhs (racc, link);
1583 1297655 : add_link_to_lhs (lacc, link);
1584 1297655 : add_access_to_rhs_work_queue (racc);
1585 1297655 : 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 1297655 : if (!comes_initialized_p (racc->base))
1591 1205464 : lacc->write = false;
1592 : }
1593 :
1594 21246526 : 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 2305581 : scan_visit_addr (gimple *, tree op, tree, void *)
1604 : {
1605 2305581 : op = get_base_address (op);
1606 2305581 : if (op
1607 2305581 : && DECL_P (op))
1608 1262355 : disqualify_candidate (op, "Address taken in a non-call-argument context.");
1609 :
1610 2305581 : 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 757092 : scan_function (void)
1618 : {
1619 757092 : basic_block bb;
1620 757092 : bool ret = false;
1621 :
1622 13052147 : FOR_EACH_BB_FN (bb, cfun)
1623 : {
1624 12295055 : gimple_stmt_iterator gsi;
1625 16796798 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1626 4501743 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), NULL, NULL, NULL,
1627 : scan_visit_addr);
1628 :
1629 117126817 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1630 : {
1631 92536707 : gimple *stmt = gsi_stmt (gsi);
1632 92536707 : tree t;
1633 92536707 : unsigned i;
1634 :
1635 92536707 : if (gimple_code (stmt) != GIMPLE_CALL)
1636 86749763 : walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1637 : scan_visit_addr);
1638 :
1639 92536707 : switch (gimple_code (stmt))
1640 : {
1641 749922 : case GIMPLE_RETURN:
1642 749922 : t = gimple_return_retval (as_a <greturn *> (stmt));
1643 749922 : if (t != NULL_TREE)
1644 446065 : ret |= build_access_from_expr (t, stmt, false);
1645 : break;
1646 :
1647 32310544 : case GIMPLE_ASSIGN:
1648 32310544 : ret |= build_accesses_from_assign (stmt);
1649 32310544 : break;
1650 :
1651 5786944 : case GIMPLE_CALL:
1652 5786944 : {
1653 5786944 : enum out_edge_check oe_check = SRA_OUTGOING_EDGES_UNCHECKED;
1654 5786944 : gcall *call = as_a <gcall *> (stmt);
1655 17314399 : for (i = 0; i < gimple_call_num_args (call); i++)
1656 : {
1657 11527455 : bool can_be_returned;
1658 11527455 : if (gimple_call_lhs (call))
1659 : {
1660 4602649 : int af = gimple_call_arg_flags (call, i);
1661 4602649 : can_be_returned = !(af & EAF_NOT_RETURNED_DIRECTLY);
1662 : }
1663 : else
1664 : can_be_returned = false;
1665 11527455 : ret |= build_access_from_call_arg (gimple_call_arg (call,
1666 : i),
1667 : stmt, can_be_returned,
1668 : &oe_check);
1669 : }
1670 5786944 : 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 5786944 : t = gimple_call_lhs (stmt);
1676 5786944 : 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 2370996 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
1681 : {
1682 102592 : struct access *access
1683 102592 : = build_access_from_expr_1 (t, stmt, true);
1684 102592 : if (access)
1685 44278 : access->grp_assignment_write = 1;
1686 102592 : ret |= access != NULL;
1687 : }
1688 : else
1689 2268404 : ret |= build_access_from_expr (t, stmt, true);
1690 : }
1691 : break;
1692 :
1693 13312 : case GIMPLE_ASM:
1694 13312 : {
1695 13312 : gasm *asm_stmt = as_a <gasm *> (stmt);
1696 13312 : if (stmt_ends_bb_p (asm_stmt)
1697 13327 : && !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 25469 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1713 : {
1714 12172 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1715 12172 : ret |= build_access_from_expr (t, asm_stmt, false);
1716 : }
1717 24486 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1718 : {
1719 11189 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1720 11189 : ret |= build_access_from_expr (t, asm_stmt, true);
1721 : }
1722 : }
1723 : }
1724 : break;
1725 :
1726 : default:
1727 : break;
1728 : }
1729 : }
1730 : }
1731 :
1732 757092 : 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 127474939 : compare_access_positions (const void *a, const void *b)
1741 : {
1742 127474939 : const access_p *fp1 = (const access_p *) a;
1743 127474939 : const access_p *fp2 = (const access_p *) b;
1744 127474939 : const access_p f1 = *fp1;
1745 127474939 : const access_p f2 = *fp2;
1746 :
1747 127474939 : if (f1->offset != f2->offset)
1748 114705325 : return f1->offset < f2->offset ? -1 : 1;
1749 :
1750 49690057 : if (f1->size == f2->size)
1751 : {
1752 34288111 : if (f1->type == f2->type)
1753 : return 0;
1754 : /* Put any non-aggregate type before any aggregate type. */
1755 5599480 : else if (!is_gimple_reg_type (f1->type)
1756 5599480 : && is_gimple_reg_type (f2->type))
1757 : return 1;
1758 4293787 : else if (is_gimple_reg_type (f1->type)
1759 4293787 : && !is_gimple_reg_type (f2->type))
1760 : return -1;
1761 : /* Put any complex or vector type before any other scalar type. */
1762 2606962 : else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1763 2606962 : && TREE_CODE (f1->type) != VECTOR_TYPE
1764 2521277 : && (TREE_CODE (f2->type) == COMPLEX_TYPE
1765 2521277 : || VECTOR_TYPE_P (f2->type)))
1766 : return 1;
1767 2561666 : 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 2497149 : else if (INTEGRAL_TYPE_P (f1->type)
1776 373101 : && !INTEGRAL_TYPE_P (f2->type))
1777 : return -1;
1778 2383287 : else if (!INTEGRAL_TYPE_P (f1->type)
1779 2124048 : && INTEGRAL_TYPE_P (f2->type))
1780 : return 1;
1781 : /* Put the integral type with the bigger precision first. */
1782 2271400 : else if (INTEGRAL_TYPE_P (f1->type)
1783 259239 : && INTEGRAL_TYPE_P (f2->type)
1784 2530639 : && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1785 32470 : return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1786 : /* Stabilize the sort. */
1787 2238930 : 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 15401946 : 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 2020231 : make_fancy_decl_name (tree decl)
1801 : {
1802 2020231 : char buffer[32];
1803 :
1804 2020231 : tree name = DECL_NAME (decl);
1805 2020231 : if (name)
1806 1957335 : obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1807 : IDENTIFIER_LENGTH (name));
1808 : else
1809 : {
1810 62896 : sprintf (buffer, "D%u", DECL_UID (decl));
1811 62896 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1812 : }
1813 2020231 : }
1814 :
1815 : /* Helper for make_fancy_name. */
1816 :
1817 : static void
1818 2293966 : make_fancy_name_1 (tree expr)
1819 : {
1820 2510605 : char buffer[32];
1821 2510605 : tree index;
1822 :
1823 2510605 : if (DECL_P (expr))
1824 : {
1825 1002494 : make_fancy_decl_name (expr);
1826 1002494 : return;
1827 : }
1828 :
1829 1508111 : switch (TREE_CODE (expr))
1830 : {
1831 1017737 : case COMPONENT_REF:
1832 1017737 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1833 1017737 : obstack_1grow (&name_obstack, '$');
1834 1017737 : make_fancy_decl_name (TREE_OPERAND (expr, 1));
1835 1017737 : break;
1836 :
1837 58645 : case ARRAY_REF:
1838 58645 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1839 58645 : obstack_1grow (&name_obstack, '$');
1840 : /* Arrays with only one element may not have a constant as their
1841 : index. */
1842 58645 : index = TREE_OPERAND (expr, 1);
1843 58645 : if (TREE_CODE (index) != INTEGER_CST)
1844 : break;
1845 58523 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1846 58523 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1847 58523 : break;
1848 :
1849 216639 : case BIT_FIELD_REF:
1850 216639 : case ADDR_EXPR:
1851 216639 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1852 216639 : break;
1853 :
1854 214864 : case MEM_REF:
1855 214864 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1856 214864 : if (!integer_zerop (TREE_OPERAND (expr, 1)))
1857 : {
1858 69624 : obstack_1grow (&name_obstack, '$');
1859 139248 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1860 69624 : TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1861 69624 : 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 1002720 : make_fancy_name (tree expr)
1878 : {
1879 1002720 : make_fancy_name_1 (expr);
1880 1002720 : obstack_1grow (&name_obstack, '\0');
1881 1002720 : 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 2436875 : 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 2436875 : tree prev_base = base;
1898 2436875 : tree off;
1899 2436875 : tree mem_ref;
1900 2436875 : poly_int64 base_offset;
1901 2436875 : unsigned HOST_WIDE_INT misalign;
1902 2436875 : unsigned int align;
1903 :
1904 : /* Preserve address-space information. */
1905 2436875 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1906 2436875 : 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 2436875 : poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1912 2436875 : get_object_alignment_1 (base, &align, &misalign);
1913 2436875 : 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 2436875 : if (!base)
1918 : {
1919 34251 : gassign *stmt;
1920 34251 : tree tmp, addr;
1921 :
1922 34251 : gcc_checking_assert (gsi);
1923 34251 : tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1924 34251 : addr = build_fold_addr_expr (unshare_expr (prev_base));
1925 34251 : STRIP_USELESS_TYPE_CONVERSION (addr);
1926 34251 : stmt = gimple_build_assign (tmp, addr);
1927 34251 : gimple_set_location (stmt, loc);
1928 34251 : if (insert_after)
1929 9481 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1930 : else
1931 24770 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1932 :
1933 34251 : off = build_int_cst (force_ref_all ? ptr_type_node
1934 34251 : : reference_alias_ptr_type (prev_base), byte_offset);
1935 34251 : base = tmp;
1936 : }
1937 2402624 : else if (TREE_CODE (base) == MEM_REF)
1938 : {
1939 402194 : off = build_int_cst (force_ref_all ? ptr_type_node
1940 201097 : : TREE_TYPE (TREE_OPERAND (base, 1)),
1941 : base_offset + byte_offset);
1942 201097 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1943 201097 : base = unshare_expr (TREE_OPERAND (base, 0));
1944 : }
1945 : else
1946 : {
1947 4064863 : off = build_int_cst (force_ref_all ? ptr_type_node
1948 1863336 : : reference_alias_ptr_type (prev_base),
1949 : base_offset + byte_offset);
1950 2201527 : base = build_fold_addr_expr (unshare_expr (base));
1951 : }
1952 :
1953 2436875 : unsigned int align_bound = known_alignment (misalign + offset);
1954 2436875 : if (align_bound != 0)
1955 1608660 : align = MIN (align, align_bound);
1956 2436875 : if (align != TYPE_ALIGN (exp_type))
1957 489932 : exp_type = build_aligned_type (exp_type, align);
1958 :
1959 2436875 : mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1960 2436875 : REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1961 2436875 : if (TREE_THIS_VOLATILE (prev_base))
1962 6 : TREE_THIS_VOLATILE (mem_ref) = 1;
1963 2436875 : if (TREE_SIDE_EFFECTS (prev_base))
1964 126 : TREE_SIDE_EFFECTS (mem_ref) = 1;
1965 2436875 : 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 1615459 : build_reconstructed_reference (location_t, tree base, struct access *model)
1973 : {
1974 1615459 : tree expr = model->expr;
1975 : /* We have to make sure to start just below the outermost union. */
1976 1615459 : tree start_expr = expr;
1977 3328966 : while (handled_component_p (expr))
1978 : {
1979 1713507 : if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == UNION_TYPE)
1980 7088 : start_expr = expr;
1981 1713507 : expr = TREE_OPERAND (expr, 0);
1982 : }
1983 :
1984 : expr = start_expr;
1985 : tree prev_expr = NULL_TREE;
1986 3306705 : while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
1987 : {
1988 1759332 : if (!handled_component_p (expr))
1989 : return NULL_TREE;
1990 1691246 : prev_expr = expr;
1991 1691246 : expr = TREE_OPERAND (expr, 0);
1992 : }
1993 :
1994 : /* Guard against broken VIEW_CONVERT_EXPRs... */
1995 1547373 : if (!prev_expr)
1996 : return NULL_TREE;
1997 :
1998 1546397 : TREE_OPERAND (prev_expr, 0) = base;
1999 1546397 : tree ref = unshare_expr (model->expr);
2000 1546397 : TREE_OPERAND (prev_expr, 0) = expr;
2001 1546397 : 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 3924901 : 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 3924901 : gcc_assert (offset >= 0);
2020 3924901 : if (TREE_CODE (model->expr) == COMPONENT_REF
2021 3924901 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2022 : {
2023 : /* This access represents a bit-field. */
2024 28978 : tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
2025 :
2026 28978 : offset -= int_bit_position (fld);
2027 28978 : exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
2028 28978 : 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 28978 : REF_REVERSE_STORAGE_ORDER (t) = 0;
2032 28978 : return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
2033 28978 : NULL_TREE);
2034 : }
2035 : else
2036 : {
2037 3895923 : tree res;
2038 3895923 : if (model->grp_same_access_path
2039 1704043 : && !force_ref_all
2040 1615484 : && !TREE_THIS_VOLATILE (base)
2041 1615478 : && (TYPE_ADDR_SPACE (TREE_TYPE (base))
2042 1615478 : == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
2043 1615477 : && (offset == model->offset
2044 10203 : || (gsi && offset <= model->offset))
2045 : /* build_reconstructed_reference can still fail if we have already
2046 : massaged BASE because of another type incompatibility. */
2047 5511382 : && (res = build_reconstructed_reference (loc, base, model)))
2048 : return res;
2049 : else
2050 2349526 : 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 5932 : build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2064 : struct access *model)
2065 : {
2066 5932 : poly_int64 base_offset;
2067 5932 : tree off;
2068 :
2069 5932 : if (TREE_CODE (model->expr) == COMPONENT_REF
2070 5932 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2071 : return NULL_TREE;
2072 :
2073 5932 : base = get_addr_base_and_unit_offset (base, &base_offset);
2074 5932 : if (!base)
2075 : return NULL_TREE;
2076 5932 : if (TREE_CODE (base) == MEM_REF)
2077 : {
2078 196 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
2079 196 : base_offset + offset / BITS_PER_UNIT);
2080 196 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
2081 196 : 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 5932 : 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 3823309 : build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
2103 : tree exp_type)
2104 : {
2105 3878761 : while (1)
2106 : {
2107 3851035 : tree fld;
2108 3851035 : tree tr_size, index, minidx;
2109 3851035 : HOST_WIDE_INT el_size;
2110 :
2111 3851035 : if (offset == 0 && exp_type
2112 3851035 : && types_compatible_p (exp_type, type))
2113 : return true;
2114 :
2115 2330595 : switch (TREE_CODE (type))
2116 : {
2117 2274764 : case UNION_TYPE:
2118 2274764 : case QUAL_UNION_TYPE:
2119 2274764 : case RECORD_TYPE:
2120 12009147 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
2121 : {
2122 11941344 : HOST_WIDE_INT pos, size;
2123 11941344 : tree tr_pos, expr, *expr_ptr;
2124 :
2125 11941344 : if (TREE_CODE (fld) != FIELD_DECL)
2126 9666532 : continue;
2127 :
2128 3782174 : tr_pos = bit_position (fld);
2129 3782174 : if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
2130 0 : continue;
2131 3782174 : pos = tree_to_uhwi (tr_pos);
2132 3782174 : gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
2133 3782174 : tr_size = DECL_SIZE (fld);
2134 3782174 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2135 0 : continue;
2136 3782174 : size = tree_to_uhwi (tr_size);
2137 3782174 : if (size == 0)
2138 : {
2139 53296 : if (pos != offset)
2140 21925 : continue;
2141 : }
2142 3728878 : else if (pos > offset || (pos + size) <= offset)
2143 1485437 : continue;
2144 :
2145 2274812 : expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
2146 : NULL_TREE);
2147 2274812 : expr_ptr = &expr;
2148 2274812 : if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
2149 : offset - pos, exp_type))
2150 : {
2151 2206961 : *res = expr;
2152 2206961 : return true;
2153 : }
2154 : }
2155 : return false;
2156 :
2157 27726 : case ARRAY_TYPE:
2158 27726 : tr_size = TYPE_SIZE (TREE_TYPE (type));
2159 27726 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2160 : return false;
2161 27726 : el_size = tree_to_uhwi (tr_size);
2162 :
2163 27726 : minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
2164 27726 : if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
2165 : return false;
2166 27726 : index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
2167 27726 : if (!integer_zerop (minidx))
2168 563 : index = int_const_binop (PLUS_EXPR, index, minidx);
2169 27726 : *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
2170 : NULL_TREE, NULL_TREE);
2171 27726 : offset = offset % el_size;
2172 27726 : type = TREE_TYPE (type);
2173 27726 : break;
2174 :
2175 28105 : default:
2176 28105 : if (offset != 0)
2177 : return false;
2178 :
2179 27697 : if (exp_type)
2180 : return false;
2181 : else
2182 : return true;
2183 : }
2184 27726 : }
2185 : }
2186 :
2187 : /* Print message to dump file why a variable was rejected. */
2188 :
2189 : static void
2190 14781876 : reject (tree var, const char *msg)
2191 : {
2192 14781876 : 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 14781876 : }
2199 :
2200 : /* Return true if VAR is a candidate for SRA. */
2201 :
2202 : static bool
2203 18896608 : maybe_add_sra_candidate (tree var)
2204 : {
2205 18896608 : tree type = TREE_TYPE (var);
2206 18896608 : const char *msg;
2207 18896608 : tree_node **slot;
2208 :
2209 18896608 : if (!AGGREGATE_TYPE_P (type))
2210 : {
2211 13255603 : reject (var, "not aggregate");
2212 13255603 : return false;
2213 : }
2214 :
2215 5641005 : 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 5418885 : || (TREE_ADDRESSABLE (var)
2219 1503935 : && pt_solution_includes (&cfun->gimple_df->escaped_return, var))
2220 4118772 : || (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 6941118 : && !constant_decl_p (var))
2225 : {
2226 1519613 : reject (var, "needs to live in memory and escapes or global");
2227 1519613 : return false;
2228 : }
2229 4121392 : if (TREE_THIS_VOLATILE (var))
2230 : {
2231 539 : reject (var, "is volatile");
2232 539 : return false;
2233 : }
2234 4120853 : if (!COMPLETE_TYPE_P (type))
2235 : {
2236 0 : reject (var, "has incomplete type");
2237 0 : return false;
2238 : }
2239 4120853 : if (!tree_fits_shwi_p (TYPE_SIZE (type)))
2240 : {
2241 43 : reject (var, "type size not fixed");
2242 43 : return false;
2243 : }
2244 4120810 : if (tree_to_shwi (TYPE_SIZE (type)) == 0)
2245 : {
2246 5822 : reject (var, "type size is zero");
2247 5822 : return false;
2248 : }
2249 4114988 : if (type_internals_preclude_sra_p (type, &msg))
2250 : {
2251 256 : reject (var, msg);
2252 256 : return false;
2253 : }
2254 4114732 : 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 4114732 : (sra_mode == SRA_MODE_EARLY_INTRA
2258 4114732 : && is_va_list_type (type)))
2259 : {
2260 0 : reject (var, "is va_list");
2261 0 : return false;
2262 : }
2263 :
2264 4114732 : bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2265 4114732 : slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2266 4114732 : *slot = var;
2267 :
2268 4114732 : 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 3474809 : find_var_candidates (void)
2283 : {
2284 3474809 : tree var, parm;
2285 3474809 : unsigned int i;
2286 3474809 : bool ret = false;
2287 :
2288 3474809 : for (parm = DECL_ARGUMENTS (current_function_decl);
2289 10745726 : parm;
2290 7270917 : parm = DECL_CHAIN (parm))
2291 7270917 : ret |= maybe_add_sra_candidate (parm);
2292 :
2293 18089009 : FOR_EACH_LOCAL_DECL (cfun, i, var)
2294 : {
2295 11621915 : if (!VAR_P (var))
2296 0 : continue;
2297 :
2298 11621915 : ret |= maybe_add_sra_candidate (var);
2299 : }
2300 :
2301 3474809 : 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 8350021 : path_comparable_for_same_access (tree expr)
2309 : {
2310 14383565 : while (handled_component_p (expr))
2311 : {
2312 6155070 : 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 643706 : if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
2320 : return false;
2321 : }
2322 6033544 : expr = TREE_OPERAND (expr, 0);
2323 : }
2324 :
2325 8228495 : if (TREE_CODE (expr) == MEM_REF)
2326 : {
2327 998087 : if (!zerop (TREE_OPERAND (expr, 1)))
2328 : return false;
2329 566557 : gcc_assert (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
2330 : && DECL_P (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)));
2331 566557 : if (TYPE_MAIN_VARIANT (TREE_TYPE (expr))
2332 566557 : != TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))))
2333 : return false;
2334 : }
2335 : else
2336 7230408 : gcc_assert (DECL_P (expr));
2337 :
2338 : return true;
2339 : }
2340 :
2341 : /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
2342 : true if the chain of these handled components are exactly the same as EXP2
2343 : and the expression under them is the same DECL or an equivalent MEM_REF.
2344 : The reference picked by compare_access_positions must go to EXP1. */
2345 :
2346 : static bool
2347 4218281 : same_access_path_p (tree exp1, tree exp2)
2348 : {
2349 4218281 : if (TREE_CODE (exp1) != TREE_CODE (exp2))
2350 : {
2351 : /* Special case single-field structures loaded sometimes as the field
2352 : and sometimes as the structure. If the field is of a scalar type,
2353 : compare_access_positions will put it into exp1.
2354 :
2355 : TODO: The gimple register type condition can be removed if teach
2356 : compare_access_positions to put inner types first. */
2357 575379 : if (is_gimple_reg_type (TREE_TYPE (exp1))
2358 355335 : && TREE_CODE (exp1) == COMPONENT_REF
2359 925927 : && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
2360 350548 : == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
2361 325268 : exp1 = TREE_OPERAND (exp1, 0);
2362 : else
2363 : return false;
2364 : }
2365 :
2366 3968170 : if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF))
2367 : return false;
2368 :
2369 : return true;
2370 : }
2371 :
2372 : /* Return true when either T1 is a type that, when loaded into a register and
2373 : stored back to memory will yield the same bits or when both T1 and T2 are
2374 : compatible. */
2375 :
2376 : static bool
2377 5311053 : types_risk_mangled_binary_repr_p (tree t1, tree t2)
2378 : {
2379 5311053 : if (mode_can_transfer_bits (TYPE_MODE (t1)))
2380 : return false;
2381 :
2382 2727 : return !types_compatible_p (t1, t2);
2383 : }
2384 :
2385 : /* Sort all accesses for the given variable, check for partial overlaps and
2386 : return NULL if there are any. If there are none, pick a representative for
2387 : each combination of offset and size and create a linked list out of them.
2388 : Return the pointer to the first representative and make sure it is the first
2389 : one in the vector of accesses. */
2390 :
2391 : static struct access *
2392 4000482 : sort_and_splice_var_accesses (tree var)
2393 : {
2394 4000482 : int i, j, access_count;
2395 4000482 : struct access *res, **prev_acc_ptr = &res;
2396 4000482 : vec<access_p> *access_vec;
2397 4000482 : bool first = true;
2398 4000482 : HOST_WIDE_INT low = -1, high = 0;
2399 :
2400 4000482 : access_vec = get_base_access_vector (var);
2401 4000482 : if (!access_vec)
2402 : return NULL;
2403 3845127 : access_count = access_vec->length ();
2404 :
2405 : /* Sort by <OFFSET, SIZE>. */
2406 3845127 : access_vec->qsort (compare_access_positions);
2407 :
2408 : i = 0;
2409 12969142 : while (i < access_count)
2410 : {
2411 9128886 : struct access *access = (*access_vec)[i];
2412 9128886 : bool grp_write = access->write;
2413 9128886 : bool grp_read = !access->write;
2414 9128886 : bool grp_scalar_write = access->write
2415 9128886 : && is_gimple_reg_type (access->type);
2416 9128886 : bool grp_scalar_read = !access->write
2417 9128886 : && is_gimple_reg_type (access->type);
2418 9128886 : bool grp_assignment_read = access->grp_assignment_read;
2419 9128886 : bool grp_assignment_write = access->grp_assignment_write;
2420 9128886 : bool multiple_scalar_reads = false;
2421 9128886 : bool grp_partial_lhs = access->grp_partial_lhs;
2422 9128886 : bool first_scalar = is_gimple_reg_type (access->type);
2423 9128886 : bool unscalarizable_region = access->grp_unscalarizable_region;
2424 9128886 : bool grp_same_access_path = access->grp_same_access_path;
2425 9128886 : bool bf_non_full_precision
2426 9128886 : = (INTEGRAL_TYPE_P (access->type)
2427 3067855 : && TYPE_PRECISION (access->type) != access->size
2428 155210 : && TREE_CODE (access->expr) == COMPONENT_REF
2429 9195357 : && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2430 :
2431 9128886 : if (first || access->offset >= high)
2432 : {
2433 4262656 : first = false;
2434 4262656 : low = access->offset;
2435 4262656 : high = access->offset + access->size;
2436 : }
2437 4866230 : else if (access->offset > low && access->offset + access->size > high)
2438 : return NULL;
2439 : else
2440 4865598 : gcc_assert (access->offset >= low
2441 : && access->offset + access->size <= high);
2442 :
2443 9128254 : if (INTEGRAL_TYPE_P (access->type)
2444 3067394 : && TYPE_PRECISION (access->type) != access->size
2445 9283041 : && bitmap_bit_p (passed_by_ref_in_call, DECL_UID (access->base)))
2446 : {
2447 : /* This can lead to performance regressions because we can generate
2448 : excessive zero extensions. */
2449 4239 : if (dump_file && (dump_flags & TDF_DETAILS))
2450 : {
2451 0 : fprintf (dump_file, "Won't scalarize ");
2452 0 : print_generic_expr (dump_file, access->base);
2453 0 : fprintf (dump_file, "(%d), it is passed by reference to a call "
2454 : "and there are accesses with precision not covering "
2455 0 : "their type size.", DECL_UID (access->base));
2456 : }
2457 4239 : return NULL;
2458 : }
2459 :
2460 9124015 : if (grp_same_access_path)
2461 8350021 : grp_same_access_path = path_comparable_for_same_access (access->expr);
2462 :
2463 9124015 : j = i + 1;
2464 14298827 : while (j < access_count)
2465 : {
2466 10458571 : struct access *ac2 = (*access_vec)[j];
2467 10458571 : if (ac2->offset != access->offset || ac2->size != access->size)
2468 : break;
2469 5174812 : if (ac2->write)
2470 : {
2471 1248259 : grp_write = true;
2472 1248259 : grp_scalar_write = (grp_scalar_write
2473 1248259 : || is_gimple_reg_type (ac2->type));
2474 : }
2475 : else
2476 : {
2477 3926553 : grp_read = true;
2478 3926553 : if (is_gimple_reg_type (ac2->type))
2479 : {
2480 1720807 : if (grp_scalar_read)
2481 : multiple_scalar_reads = true;
2482 : else
2483 362725 : grp_scalar_read = true;
2484 : }
2485 : }
2486 5174812 : grp_assignment_read |= ac2->grp_assignment_read;
2487 5174812 : grp_assignment_write |= ac2->grp_assignment_write;
2488 5174812 : grp_partial_lhs |= ac2->grp_partial_lhs;
2489 5174812 : unscalarizable_region |= ac2->grp_unscalarizable_region;
2490 5174812 : relink_to_new_repr (access, ac2);
2491 :
2492 : /* If there are both aggregate-type and scalar-type accesses with
2493 : this combination of size and offset, the comparison function
2494 : should have put the scalars first. */
2495 5174812 : gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
2496 : /* It also prefers integral types to non-integral. However, when the
2497 : precision of the selected type does not span the entire area and
2498 : should also be used for a non-integer (i.e. float), we must not
2499 : let that happen. Normally analyze_access_subtree expands the type
2500 : to cover the entire area but for bit-fields it doesn't. */
2501 5174812 : if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
2502 : {
2503 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2504 : {
2505 0 : fprintf (dump_file, "Cannot scalarize the following access "
2506 : "because insufficient precision integer type was "
2507 : "selected.\n ");
2508 0 : dump_access (dump_file, access, false);
2509 : }
2510 : unscalarizable_region = true;
2511 : }
2512 5174812 : else if (types_risk_mangled_binary_repr_p (access->type, ac2->type))
2513 : {
2514 818 : if (dump_file && (dump_flags & TDF_DETAILS))
2515 : {
2516 0 : fprintf (dump_file, "Cannot scalarize the following access "
2517 : "because data would be held in a mode which is not "
2518 : "guaranteed to preserve all bits.\n ");
2519 0 : dump_access (dump_file, access, false);
2520 : }
2521 : unscalarizable_region = true;
2522 : }
2523 : /* If there the same place is accessed with two incompatible
2524 : aggregate types, trying to base total scalarization on either of
2525 : them can be wrong. */
2526 5174812 : if (!first_scalar && !types_compatible_p (access->type, ac2->type))
2527 448434 : bitmap_set_bit (cannot_scalarize_away_bitmap,
2528 224217 : DECL_UID (access->base));
2529 :
2530 5174812 : if (grp_same_access_path
2531 5174812 : && (!ac2->grp_same_access_path
2532 4218281 : || !same_access_path_p (access->expr, ac2->expr)))
2533 : grp_same_access_path = false;
2534 :
2535 5174812 : ac2->group_representative = access;
2536 5174812 : j++;
2537 : }
2538 :
2539 9124015 : i = j;
2540 :
2541 9124015 : access->group_representative = access;
2542 9124015 : access->grp_write = grp_write;
2543 9124015 : access->grp_read = grp_read;
2544 9124015 : access->grp_scalar_read = grp_scalar_read;
2545 9124015 : access->grp_scalar_write = grp_scalar_write;
2546 9124015 : access->grp_assignment_read = grp_assignment_read;
2547 9124015 : access->grp_assignment_write = grp_assignment_write;
2548 9124015 : access->grp_hint = multiple_scalar_reads && !constant_decl_p (var);
2549 9124015 : access->grp_partial_lhs = grp_partial_lhs;
2550 9124015 : access->grp_unscalarizable_region = unscalarizable_region;
2551 9124015 : access->grp_same_access_path = grp_same_access_path;
2552 :
2553 9124015 : *prev_acc_ptr = access;
2554 9124015 : prev_acc_ptr = &access->next_grp;
2555 : }
2556 :
2557 3840256 : gcc_assert (res == (*access_vec)[0]);
2558 : return res;
2559 : }
2560 :
2561 : /* Create a variable for the given ACCESS which determines the type, name and a
2562 : few other properties. Return the variable declaration and store it also to
2563 : ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2564 : default-definition SSA name on in order to facilitate an uninitialized
2565 : warning. It is used instead of the actual ACCESS type if that is not of a
2566 : gimple register type. */
2567 :
2568 : static tree
2569 3803969 : create_access_replacement (struct access *access, tree reg_type = NULL_TREE)
2570 : {
2571 3803969 : tree repl;
2572 :
2573 3803969 : tree type = access->type;
2574 3803969 : if (reg_type && !is_gimple_reg_type (type))
2575 : type = reg_type;
2576 :
2577 3803969 : if (access->grp_to_be_debug_replaced)
2578 : {
2579 234415 : repl = create_tmp_var_raw (access->type);
2580 234415 : DECL_CONTEXT (repl) = current_function_decl;
2581 : }
2582 : else
2583 : /* Drop any special alignment on the type if it's not on the main
2584 : variant. This avoids issues with weirdo ABIs like AAPCS. */
2585 3569554 : repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type),
2586 3569554 : TYPE_QUALS (type)), "SR");
2587 3803969 : if (access->grp_partial_lhs
2588 3803969 : && is_gimple_reg_type (type))
2589 664 : DECL_NOT_GIMPLE_REG_P (repl) = 1;
2590 :
2591 3803969 : DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2592 3803969 : DECL_ARTIFICIAL (repl) = 1;
2593 3803969 : DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2594 :
2595 3803969 : if (DECL_NAME (access->base)
2596 3803969 : && ((!DECL_IGNORED_P (access->base) && !DECL_ARTIFICIAL (access->base))
2597 1868281 : || (VAR_P (access->base) && DECL_NONLOCAL_FRAME (access->base))))
2598 : {
2599 1002720 : char *pretty_name = make_fancy_name (access->expr);
2600 1002720 : tree debug_expr = unshare_expr_without_location (access->expr), d;
2601 1002720 : bool fail = false;
2602 :
2603 1002720 : DECL_NAME (repl) = get_identifier (pretty_name);
2604 1002720 : DECL_NAMELESS (repl) = 1;
2605 1002720 : obstack_free (&name_obstack, pretty_name);
2606 :
2607 : /* Get rid of any SSA_NAMEs embedded in debug_expr,
2608 : as DECL_DEBUG_EXPR isn't considered when looking for still
2609 : used SSA_NAMEs and thus they could be freed. All debug info
2610 : generation cares is whether something is constant or variable
2611 : and that get_ref_base_and_extent works properly on the
2612 : expression. It cannot handle accesses at a non-constant offset
2613 : though, so just give up in those cases. */
2614 1293406 : for (d = debug_expr;
2615 3513589 : !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2616 1293406 : d = TREE_OPERAND (d, 0))
2617 1293406 : switch (TREE_CODE (d))
2618 : {
2619 58721 : case ARRAY_REF:
2620 58721 : case ARRAY_RANGE_REF:
2621 58721 : if (TREE_OPERAND (d, 1)
2622 58721 : && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2623 : fail = true;
2624 58721 : if (TREE_OPERAND (d, 3)
2625 58721 : && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2626 : fail = true;
2627 : /* FALLTHRU */
2628 1076618 : case COMPONENT_REF:
2629 1076618 : if (TREE_OPERAND (d, 2)
2630 1076618 : && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2631 : fail = true;
2632 : break;
2633 214864 : case MEM_REF:
2634 214864 : if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2635 : fail = true;
2636 : else
2637 214864 : d = TREE_OPERAND (d, 0);
2638 : break;
2639 : default:
2640 : break;
2641 : }
2642 1002720 : if (!fail)
2643 : {
2644 1002599 : SET_DECL_DEBUG_EXPR (repl, debug_expr);
2645 1002599 : DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2646 : }
2647 1002720 : if (access->grp_no_warning)
2648 380 : suppress_warning (repl /* Be more selective! */);
2649 : else
2650 1002340 : copy_warning (repl, access->base);
2651 : }
2652 : else
2653 2801249 : suppress_warning (repl /* Be more selective! */);
2654 :
2655 3803969 : if (dump_file)
2656 : {
2657 145 : if (access->grp_to_be_debug_replaced)
2658 : {
2659 4 : fprintf (dump_file, "Created a debug-only replacement for ");
2660 4 : print_generic_expr (dump_file, access->base);
2661 4 : fprintf (dump_file, " offset: %u, size: %u\n",
2662 4 : (unsigned) access->offset, (unsigned) access->size);
2663 : }
2664 : else
2665 : {
2666 141 : fprintf (dump_file, "Created a replacement for ");
2667 141 : print_generic_expr (dump_file, access->base);
2668 141 : fprintf (dump_file, " offset: %u, size: %u: ",
2669 141 : (unsigned) access->offset, (unsigned) access->size);
2670 141 : print_generic_expr (dump_file, repl, TDF_UID);
2671 141 : fprintf (dump_file, "\n");
2672 : }
2673 : }
2674 3803969 : sra_stats.replacements++;
2675 :
2676 3803969 : return repl;
2677 : }
2678 :
2679 : /* Return ACCESS scalar replacement, which must exist. */
2680 :
2681 : static inline tree
2682 13008145 : get_access_replacement (struct access *access)
2683 : {
2684 13008145 : gcc_checking_assert (access->replacement_decl);
2685 13008145 : return access->replacement_decl;
2686 : }
2687 :
2688 :
2689 : /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2690 : linked list along the way. Stop when *ACCESS is NULL or the access pointed
2691 : to it is not "within" the root. Return false iff some accesses partially
2692 : overlap. */
2693 :
2694 : static bool
2695 9101241 : build_access_subtree (struct access **access)
2696 : {
2697 9101241 : struct access *root = *access, *last_child = NULL;
2698 9101241 : HOST_WIDE_INT limit = root->offset + root->size;
2699 :
2700 9101241 : *access = (*access)->next_grp;
2701 13942220 : while (*access && (*access)->offset + (*access)->size <= limit)
2702 : {
2703 4843473 : if (!last_child)
2704 1936759 : root->first_child = *access;
2705 : else
2706 2906714 : last_child->next_sibling = *access;
2707 4843473 : last_child = *access;
2708 4843473 : (*access)->parent = root;
2709 4843473 : (*access)->grp_write |= root->grp_write;
2710 :
2711 4843473 : if (!build_access_subtree (access))
2712 : return false;
2713 : }
2714 :
2715 9098747 : if (*access && (*access)->offset < limit)
2716 : return false;
2717 :
2718 : return true;
2719 : }
2720 :
2721 : /* Build a tree of access representatives, ACCESS is the pointer to the first
2722 : one, others are linked in a list by the next_grp field. Return false iff
2723 : some accesses partially overlap. */
2724 :
2725 : static bool
2726 3840256 : build_access_trees (struct access *access)
2727 : {
2728 8095711 : while (access)
2729 : {
2730 4257768 : struct access *root = access;
2731 :
2732 4257768 : if (!build_access_subtree (&access))
2733 : return false;
2734 4255455 : root->next_grp = access;
2735 : }
2736 : return true;
2737 : }
2738 :
2739 : /* Traverse the access forest where ROOT is the first root and verify that
2740 : various important invariants hold true. */
2741 :
2742 : DEBUG_FUNCTION void
2743 3837943 : verify_sra_access_forest (struct access *root)
2744 : {
2745 3837943 : struct access *access = root;
2746 3837943 : tree first_base = root->base;
2747 3837943 : gcc_assert (DECL_P (first_base));
2748 10994241 : do
2749 : {
2750 10994241 : gcc_assert (access->base == first_base);
2751 10994241 : if (access->parent)
2752 6738801 : gcc_assert (access->offset >= access->parent->offset
2753 : && access->size <= access->parent->size);
2754 10994241 : if (access->next_sibling)
2755 3979092 : gcc_assert (access->next_sibling->offset
2756 : >= access->offset + access->size);
2757 :
2758 10994241 : poly_int64 poffset, psize, pmax_size;
2759 10994241 : bool reverse;
2760 10994241 : tree base = get_ref_base_and_extent (access->expr, &poffset, &psize,
2761 : &pmax_size, &reverse);
2762 10994241 : HOST_WIDE_INT offset, size, max_size;
2763 10994241 : if (!poffset.is_constant (&offset)
2764 10994241 : || !psize.is_constant (&size)
2765 10994241 : || !pmax_size.is_constant (&max_size))
2766 : gcc_unreachable ();
2767 10994241 : gcc_assert (base == first_base);
2768 10994241 : gcc_assert (offset == access->offset);
2769 10994241 : gcc_assert (access->grp_unscalarizable_region
2770 : || access->grp_total_scalarization
2771 : || size == max_size);
2772 10994241 : gcc_assert (access->grp_unscalarizable_region
2773 : || !is_gimple_reg_type (access->type)
2774 : || size == access->size);
2775 10994241 : gcc_assert (reverse == access->reverse);
2776 :
2777 10994241 : if (access->first_child)
2778 : {
2779 2759709 : gcc_assert (access->first_child->parent == access);
2780 : access = access->first_child;
2781 : }
2782 8234532 : else if (access->next_sibling)
2783 : {
2784 3798450 : gcc_assert (access->next_sibling->parent == access->parent);
2785 : access = access->next_sibling;
2786 : }
2787 : else
2788 : {
2789 7195791 : while (access->parent && !access->next_sibling)
2790 : access = access->parent;
2791 4436082 : if (access->next_sibling)
2792 : access = access->next_sibling;
2793 : else
2794 : {
2795 4255440 : gcc_assert (access == root);
2796 4255440 : root = root->next_grp;
2797 4255440 : access = root;
2798 : }
2799 : }
2800 : }
2801 10994241 : while (access);
2802 3837943 : }
2803 :
2804 : /* Verify access forests of all candidates with accesses by calling
2805 : verify_access_forest on each on them. */
2806 :
2807 : DEBUG_FUNCTION void
2808 707540 : verify_all_sra_access_forests (void)
2809 : {
2810 707540 : bitmap_iterator bi;
2811 707540 : unsigned i;
2812 4545483 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2813 : {
2814 3837943 : tree var = candidate (i);
2815 3837943 : struct access *access = get_first_repr_for_decl (var);
2816 3837943 : if (access)
2817 : {
2818 3837943 : gcc_assert (access->base == var);
2819 3837943 : verify_sra_access_forest (access);
2820 : }
2821 : }
2822 707540 : }
2823 :
2824 : /* Return true if expr contains some ARRAY_REFs into a variable bounded
2825 : array. */
2826 :
2827 : static bool
2828 10612044 : expr_with_var_bounded_array_refs_p (tree expr)
2829 : {
2830 20018190 : while (handled_component_p (expr))
2831 : {
2832 9406146 : if (TREE_CODE (expr) == ARRAY_REF
2833 9406146 : && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2834 : return true;
2835 9406146 : expr = TREE_OPERAND (expr, 0);
2836 : }
2837 : return false;
2838 : }
2839 :
2840 : /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2841 : both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2842 : is set, we are totally scalarizing the aggregate. Also set all sorts of
2843 : access flags appropriately along the way, notably always set grp_read and
2844 : grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2845 : true.
2846 :
2847 : Creating a replacement for a scalar access is considered beneficial if its
2848 : grp_hint ot TOTALLY is set (this means either that there is more than one
2849 : direct read access or that we are attempting total scalarization) or
2850 : according to the following table:
2851 :
2852 : Access written to through a scalar type (once or more times)
2853 : |
2854 : | Written to in an assignment statement
2855 : | |
2856 : | | Access read as scalar _once_
2857 : | | |
2858 : | | | Read in an assignment statement
2859 : | | | |
2860 : | | | | Scalarize Comment
2861 : -----------------------------------------------------------------------------
2862 : 0 0 0 0 No access for the scalar
2863 : 0 0 0 1 No access for the scalar
2864 : 0 0 1 0 No Single read - won't help
2865 : 0 0 1 1 No The same case
2866 : 0 1 0 0 No access for the scalar
2867 : 0 1 0 1 No access for the scalar
2868 : 0 1 1 0 Yes s = *g; return s.i;
2869 : 0 1 1 1 Yes The same case as above
2870 : 1 0 0 0 No Won't help
2871 : 1 0 0 1 Yes s.i = 1; *g = s;
2872 : 1 0 1 0 Yes s.i = 5; g = s.i;
2873 : 1 0 1 1 Yes The same case as above
2874 : 1 1 0 0 No Won't help.
2875 : 1 1 0 1 Yes s.i = 1; *g = s;
2876 : 1 1 1 0 Yes s = *g; return s.i;
2877 : 1 1 1 1 Yes Any of the above yeses */
2878 :
2879 : static bool
2880 10994241 : analyze_access_subtree (struct access *root, struct access *parent,
2881 : bool allow_replacements, bool totally)
2882 : {
2883 10994241 : struct access *child;
2884 10994241 : HOST_WIDE_INT limit = root->offset + root->size;
2885 10994241 : HOST_WIDE_INT covered_to = root->offset;
2886 10994241 : bool scalar = is_gimple_reg_type (root->type);
2887 10994241 : bool hole = false, sth_created = false;
2888 :
2889 10994241 : if (parent)
2890 : {
2891 6738801 : if (parent->grp_read)
2892 5999020 : root->grp_read = 1;
2893 6738801 : if (parent->grp_assignment_read)
2894 2832837 : root->grp_assignment_read = 1;
2895 6738801 : if (parent->grp_write)
2896 3977222 : root->grp_write = 1;
2897 6738801 : if (parent->grp_assignment_write)
2898 2881610 : root->grp_assignment_write = 1;
2899 6738801 : if (!parent->grp_same_access_path)
2900 1147376 : root->grp_same_access_path = 0;
2901 : }
2902 :
2903 10994241 : if (root->grp_unscalarizable_region)
2904 : allow_replacements = false;
2905 :
2906 10870527 : if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2907 : allow_replacements = false;
2908 :
2909 10994241 : if (!totally && root->grp_result_of_prop_from_lhs)
2910 10994241 : allow_replacements = false;
2911 :
2912 17733042 : for (child = root->first_child; child; child = child->next_sibling)
2913 : {
2914 6738801 : if (totally)
2915 1799221 : covered_to = child->offset;
2916 : else
2917 4939580 : hole |= covered_to < child->offset;
2918 6738801 : sth_created |= analyze_access_subtree (child, root,
2919 6738801 : allow_replacements && !scalar
2920 6738801 : && !root->grp_partial_lhs,
2921 : totally);
2922 :
2923 6738801 : root->grp_unscalarized_data |= child->grp_unscalarized_data;
2924 6738801 : if (child->grp_covered)
2925 3216260 : covered_to += child->size;
2926 : else
2927 : hole = true;
2928 6738801 : if (totally && !hole)
2929 1798464 : covered_to = limit;
2930 : }
2931 :
2932 10994241 : if (allow_replacements && scalar && !root->first_child
2933 6628520 : && (totally || !root->grp_total_scalarization)
2934 : && (totally
2935 4928472 : || root->grp_hint
2936 4158138 : || ((root->grp_scalar_read || root->grp_assignment_read)
2937 1449649 : && (root->grp_scalar_write || root->grp_assignment_write))))
2938 : {
2939 : /* Always create access replacements that cover the whole access.
2940 : For integral types this means the precision has to match.
2941 : Avoid assumptions based on the integral type kind, too. */
2942 3569010 : if (INTEGRAL_TYPE_P (root->type)
2943 1599538 : && ((TREE_CODE (root->type) != INTEGER_TYPE
2944 1599538 : && TREE_CODE (root->type) != BITINT_TYPE)
2945 1540892 : || TYPE_PRECISION (root->type) != root->size)
2946 : /* But leave bitfield accesses alone. */
2947 3627662 : && (TREE_CODE (root->expr) != COMPONENT_REF
2948 57666 : || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2949 : {
2950 58371 : tree rt = root->type;
2951 58371 : gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2952 : && (root->size % BITS_PER_UNIT) == 0);
2953 58371 : if (TREE_CODE (root->type) == BITINT_TYPE)
2954 6 : root->type = build_bitint_type (root->size, TYPE_UNSIGNED (rt));
2955 : else
2956 58365 : root->type = build_nonstandard_integer_type (root->size,
2957 58365 : TYPE_UNSIGNED (rt));
2958 116742 : root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2959 58371 : root->offset, root->reverse,
2960 : root->type, NULL, false);
2961 :
2962 58371 : if (dump_file && (dump_flags & TDF_DETAILS))
2963 : {
2964 0 : fprintf (dump_file, "Changing the type of a replacement for ");
2965 0 : print_generic_expr (dump_file, root->base);
2966 0 : fprintf (dump_file, " offset: %u, size: %u ",
2967 0 : (unsigned) root->offset, (unsigned) root->size);
2968 0 : fprintf (dump_file, " to an integer.\n");
2969 : }
2970 : }
2971 :
2972 3569010 : root->grp_to_be_replaced = 1;
2973 3569010 : root->replacement_decl = create_access_replacement (root);
2974 3569010 : sth_created = true;
2975 3569010 : hole = false;
2976 : }
2977 : else
2978 : {
2979 7425231 : if (allow_replacements
2980 3068852 : && scalar && !root->first_child
2981 3059510 : && !root->grp_total_scalarization
2982 3059370 : && (root->grp_scalar_write || root->grp_assignment_write)
2983 10133720 : && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2984 2708489 : DECL_UID (root->base)))
2985 : {
2986 451961 : gcc_checking_assert (!root->grp_scalar_read
2987 : && !root->grp_assignment_read);
2988 451961 : sth_created = true;
2989 451961 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2990 : {
2991 234415 : root->grp_to_be_debug_replaced = 1;
2992 234415 : root->replacement_decl = create_access_replacement (root);
2993 : }
2994 : }
2995 :
2996 7425231 : if (covered_to < limit)
2997 6225985 : hole = true;
2998 7425231 : if (scalar || !allow_replacements)
2999 4031260 : root->grp_total_scalarization = 0;
3000 : }
3001 :
3002 10994241 : if (!hole)
3003 4768036 : root->grp_covered = 1;
3004 6226205 : else if (root->grp_write || comes_initialized_p (root->base))
3005 5475078 : root->grp_unscalarized_data = 1; /* not covered and written to */
3006 10994241 : return sth_created;
3007 : }
3008 :
3009 : /* Analyze all access trees linked by next_grp by the means of
3010 : analyze_access_subtree. */
3011 : static bool
3012 3837943 : analyze_access_trees (struct access *access)
3013 : {
3014 3837943 : bool ret = false;
3015 :
3016 8093383 : while (access)
3017 : {
3018 4255440 : if (analyze_access_subtree (access, NULL, true,
3019 4255440 : access->grp_total_scalarization))
3020 2093288 : ret = true;
3021 4255440 : access = access->next_grp;
3022 : }
3023 :
3024 3837943 : return ret;
3025 : }
3026 :
3027 : /* Return true iff a potential new child of ACC at offset OFFSET and with size
3028 : SIZE would conflict with an already existing one. If exactly such a child
3029 : already exists in ACC, store a pointer to it in EXACT_MATCH. */
3030 :
3031 : static bool
3032 6841747 : child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset,
3033 : HOST_WIDE_INT size, struct access **exact_match)
3034 : {
3035 6841747 : struct access *child;
3036 :
3037 12020287 : for (child = acc->first_child; child; child = child->next_sibling)
3038 : {
3039 10599857 : if (child->offset == norm_offset && child->size == size)
3040 : {
3041 5383022 : *exact_match = child;
3042 5383022 : return true;
3043 : }
3044 :
3045 5216835 : if (child->offset < norm_offset + size
3046 5143642 : && child->offset + child->size > norm_offset)
3047 : return true;
3048 : }
3049 :
3050 : return false;
3051 : }
3052 :
3053 : /* Create a new child access of PARENT, with all properties just like MODEL
3054 : except for its offset and with its grp_write false and grp_read true.
3055 : Return the new access or NULL if it cannot be created. Note that this
3056 : access is created long after all splicing and sorting, it's not located in
3057 : any access vector and is automatically a representative of its group. Set
3058 : the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
3059 :
3060 : static struct access *
3061 1412256 : create_artificial_child_access (struct access *parent, struct access *model,
3062 : HOST_WIDE_INT new_offset,
3063 : bool set_grp_read, bool set_grp_write)
3064 : {
3065 1412256 : struct access **child;
3066 1412256 : tree expr = parent->base;
3067 :
3068 1412256 : gcc_assert (!model->grp_unscalarizable_region);
3069 :
3070 1412256 : struct access *access = access_pool.allocate ();
3071 1412256 : memset (access, 0, sizeof (struct access));
3072 1412256 : if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
3073 : model->type))
3074 : {
3075 27809 : access->grp_no_warning = true;
3076 27809 : expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
3077 : new_offset, model, NULL, false);
3078 : }
3079 :
3080 1412256 : access->base = parent->base;
3081 1412256 : access->expr = expr;
3082 1412256 : access->offset = new_offset;
3083 1412256 : access->size = model->size;
3084 1412256 : access->type = model->type;
3085 1412256 : access->parent = parent;
3086 1412256 : access->grp_read = set_grp_read;
3087 1412256 : access->grp_write = set_grp_write;
3088 1412256 : access->reverse = model->reverse;
3089 :
3090 1412256 : child = &parent->first_child;
3091 2591802 : while (*child && (*child)->offset < new_offset)
3092 1179546 : child = &(*child)->next_sibling;
3093 :
3094 1412256 : access->next_sibling = *child;
3095 1412256 : *child = access;
3096 :
3097 1412256 : return access;
3098 : }
3099 :
3100 :
3101 : /* Beginning with ACCESS, traverse its whole access subtree and mark all
3102 : sub-trees as written to. If any of them has not been marked so previously
3103 : and has assignment links leading from it, re-enqueue it. */
3104 :
3105 : static void
3106 1586390 : subtree_mark_written_and_rhs_enqueue (struct access *access)
3107 : {
3108 1586390 : if (access->grp_write)
3109 : return;
3110 1514984 : access->grp_write = true;
3111 1514984 : add_access_to_rhs_work_queue (access);
3112 :
3113 1514984 : struct access *child;
3114 2141334 : for (child = access->first_child; child; child = child->next_sibling)
3115 626350 : subtree_mark_written_and_rhs_enqueue (child);
3116 : }
3117 :
3118 : /* If there is still budget to create a propagation access for DECL, return
3119 : true and decrement the budget. Otherwise return false. */
3120 :
3121 : static bool
3122 1416390 : budget_for_propagation_access (tree decl)
3123 : {
3124 1416390 : unsigned b, *p = propagation_budget->get (decl);
3125 1416390 : if (p)
3126 857774 : b = *p;
3127 : else
3128 558616 : b = param_sra_max_propagations;
3129 :
3130 1416390 : if (b == 0)
3131 : return false;
3132 1412262 : b--;
3133 :
3134 1412262 : if (b == 0 && dump_file && (dump_flags & TDF_DETAILS))
3135 : {
3136 0 : fprintf (dump_file, "The propagation budget of ");
3137 0 : print_generic_expr (dump_file, decl);
3138 0 : fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl));
3139 : }
3140 1412262 : propagation_budget->put (decl, b);
3141 1412262 : return true;
3142 : }
3143 :
3144 : /* Return true if ACC or any of its subaccesses has grp_child set. */
3145 :
3146 : static bool
3147 3094 : access_or_its_child_written (struct access *acc)
3148 : {
3149 3094 : if (acc->grp_write)
3150 : return true;
3151 2327 : for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling)
3152 595 : if (access_or_its_child_written (sub))
3153 : return true;
3154 : return false;
3155 : }
3156 :
3157 : /* Propagate subaccesses and grp_write flags of RACC across an assignment link
3158 : to LACC. Enqueue sub-accesses as necessary so that the write flag is
3159 : propagated transitively. Return true if anything changed. Additionally, if
3160 : RACC is a scalar access but LACC is not, change the type of the latter, if
3161 : possible. */
3162 :
3163 : static bool
3164 3553044 : propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc)
3165 : {
3166 3553044 : struct access *rchild;
3167 3553044 : HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
3168 3553044 : bool ret = false;
3169 :
3170 : /* IF the LHS is still not marked as being written to, we only need to do so
3171 : if the RHS at this level actually was. */
3172 3553044 : if (!lacc->grp_write)
3173 : {
3174 1606208 : gcc_checking_assert (!comes_initialized_p (racc->base));
3175 1606208 : if (racc->grp_write)
3176 : {
3177 768132 : subtree_mark_written_and_rhs_enqueue (lacc);
3178 768132 : ret = true;
3179 : }
3180 : }
3181 :
3182 3553044 : if (is_gimple_reg_type (lacc->type)
3183 2793009 : || lacc->grp_unscalarizable_region
3184 6345440 : || racc->grp_unscalarizable_region)
3185 : {
3186 761706 : if (!lacc->grp_write)
3187 : {
3188 17633 : ret = true;
3189 17633 : subtree_mark_written_and_rhs_enqueue (lacc);
3190 : }
3191 761706 : return ret;
3192 : }
3193 :
3194 2791338 : if (is_gimple_reg_type (racc->type))
3195 : {
3196 136723 : if (!lacc->grp_write)
3197 : {
3198 2531 : ret = true;
3199 2531 : subtree_mark_written_and_rhs_enqueue (lacc);
3200 : }
3201 136723 : if (!lacc->first_child
3202 136543 : && !racc->first_child
3203 272964 : && !types_risk_mangled_binary_repr_p (racc->type, lacc->type))
3204 : {
3205 : /* We are about to change the access type from aggregate to scalar,
3206 : so we need to put the reverse flag onto the access, if any. */
3207 136241 : const bool reverse
3208 136241 : = TYPE_REVERSE_STORAGE_ORDER (lacc->type)
3209 1 : && !POINTER_TYPE_P (racc->type)
3210 136241 : && !VECTOR_TYPE_P (racc->type);
3211 136241 : tree t = lacc->base;
3212 :
3213 136241 : lacc->type = racc->type;
3214 136241 : if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
3215 : lacc->offset, racc->type))
3216 : {
3217 135993 : lacc->expr = t;
3218 135993 : lacc->grp_same_access_path = true;
3219 : }
3220 : else
3221 : {
3222 248 : lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
3223 : lacc->base, lacc->offset,
3224 : racc, NULL, false);
3225 248 : if (TREE_CODE (lacc->expr) == MEM_REF)
3226 248 : REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse;
3227 248 : lacc->grp_no_warning = true;
3228 248 : lacc->grp_same_access_path = false;
3229 : }
3230 136241 : lacc->reverse = reverse;
3231 : }
3232 136723 : return ret;
3233 : }
3234 :
3235 5726403 : for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
3236 : {
3237 3071788 : struct access *new_acc = NULL;
3238 3071788 : HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
3239 :
3240 3071788 : if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size,
3241 : &new_acc))
3242 : {
3243 2527930 : if (new_acc)
3244 : {
3245 2503440 : if (!new_acc->grp_write && rchild->grp_write)
3246 : {
3247 165016 : gcc_assert (!lacc->grp_write);
3248 165016 : subtree_mark_written_and_rhs_enqueue (new_acc);
3249 165016 : ret = true;
3250 : }
3251 :
3252 2503440 : rchild->grp_hint = 1;
3253 2503440 : new_acc->grp_hint |= new_acc->grp_read;
3254 2503440 : if (rchild->first_child
3255 2503440 : && propagate_subaccesses_from_rhs (new_acc, rchild))
3256 : {
3257 1275 : ret = 1;
3258 1275 : add_access_to_rhs_work_queue (new_acc);
3259 : }
3260 : }
3261 : else
3262 : {
3263 24490 : if (!lacc->grp_write)
3264 : {
3265 4907 : ret = true;
3266 4907 : subtree_mark_written_and_rhs_enqueue (lacc);
3267 : }
3268 : }
3269 2536072 : continue;
3270 : }
3271 :
3272 552000 : if (rchild->grp_unscalarizable_region
3273 542783 : || (rchild->size % BITS_PER_UNIT) != 0
3274 1083676 : || !budget_for_propagation_access (lacc->base))
3275 : {
3276 8142 : if (!lacc->grp_write && access_or_its_child_written (rchild))
3277 : {
3278 1329 : ret = true;
3279 1329 : subtree_mark_written_and_rhs_enqueue (lacc);
3280 : }
3281 8142 : continue;
3282 : }
3283 :
3284 535716 : rchild->grp_hint = 1;
3285 : /* Because get_ref_base_and_extent always includes padding in size for
3286 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3287 : type, we might be actually attempting to here to create a child of the
3288 : same type as the parent. */
3289 535716 : if (!types_compatible_p (lacc->type, rchild->type))
3290 535716 : new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
3291 : false,
3292 535716 : (lacc->grp_write
3293 535716 : || rchild->grp_write));
3294 : else
3295 0 : new_acc = lacc;
3296 535716 : gcc_checking_assert (new_acc);
3297 535716 : if (racc->first_child)
3298 535716 : propagate_subaccesses_from_rhs (new_acc, rchild);
3299 :
3300 535716 : add_access_to_rhs_work_queue (lacc);
3301 535716 : ret = true;
3302 : }
3303 :
3304 : return ret;
3305 : }
3306 :
3307 : /* Propagate subaccesses of LACC across an assignment link to RACC if they
3308 : should inhibit total scalarization of the corresponding area. No flags are
3309 : being propagated in the process. Return true if anything changed. */
3310 :
3311 : static bool
3312 6014125 : propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc)
3313 : {
3314 6014125 : if (is_gimple_reg_type (racc->type)
3315 2118755 : || lacc->grp_unscalarizable_region
3316 8131861 : || racc->grp_unscalarizable_region)
3317 : return false;
3318 :
3319 : /* TODO: Do we want set some new racc flag to stop potential total
3320 : scalarization if lacc is a scalar access (and none fo the two have
3321 : children)? */
3322 :
3323 2117717 : bool ret = false;
3324 2117717 : HOST_WIDE_INT norm_delta = racc->offset - lacc->offset;
3325 2117717 : for (struct access *lchild = lacc->first_child;
3326 5893023 : lchild;
3327 3775306 : lchild = lchild->next_sibling)
3328 : {
3329 3775306 : struct access *matching_acc = NULL;
3330 3775306 : HOST_WIDE_INT norm_offset = lchild->offset + norm_delta;
3331 :
3332 6674066 : if (lchild->grp_unscalarizable_region
3333 3770857 : || (lchild->size % BITS_PER_UNIT) != 0
3334 3769959 : || child_would_conflict_in_acc (racc, norm_offset, lchild->size,
3335 : &matching_acc)
3336 4651878 : || !budget_for_propagation_access (racc->base))
3337 : {
3338 2898760 : if (matching_acc
3339 2898760 : && propagate_subaccesses_from_lhs (lchild, matching_acc))
3340 195 : add_access_to_lhs_work_queue (matching_acc);
3341 2898760 : continue;
3342 : }
3343 :
3344 : /* Because get_ref_base_and_extent always includes padding in size for
3345 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3346 : type, we might be actually attempting to here to create a child of the
3347 : same type as the parent. */
3348 876546 : if (!types_compatible_p (racc->type, lchild->type))
3349 : {
3350 876540 : struct access *new_acc
3351 876540 : = create_artificial_child_access (racc, lchild, norm_offset,
3352 : true, false);
3353 876540 : new_acc->grp_result_of_prop_from_lhs = 1;
3354 876540 : propagate_subaccesses_from_lhs (lchild, new_acc);
3355 : }
3356 : else
3357 6 : propagate_subaccesses_from_lhs (lchild, racc);
3358 876546 : ret = true;
3359 : }
3360 : return ret;
3361 : }
3362 :
3363 : /* Propagate all subaccesses across assignment links. */
3364 :
3365 : static void
3366 707540 : propagate_all_subaccesses (void)
3367 : {
3368 707540 : propagation_budget = new hash_map<tree, unsigned>;
3369 2209475 : while (rhs_work_queue_head)
3370 : {
3371 1501935 : struct access *racc = pop_access_from_rhs_work_queue ();
3372 1501935 : struct assign_link *link;
3373 :
3374 1501935 : if (racc->group_representative)
3375 1501238 : racc= racc->group_representative;
3376 1501935 : gcc_assert (racc->first_rhs_link);
3377 :
3378 4507993 : for (link = racc->first_rhs_link; link; link = link->next_rhs)
3379 : {
3380 3006058 : struct access *lacc = link->lacc;
3381 :
3382 3006058 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3383 6757 : continue;
3384 2999301 : lacc = lacc->group_representative;
3385 :
3386 2999301 : bool reque_parents = false;
3387 2999301 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3388 : {
3389 1720 : if (!lacc->grp_write)
3390 : {
3391 492 : subtree_mark_written_and_rhs_enqueue (lacc);
3392 492 : reque_parents = true;
3393 : }
3394 : }
3395 2997581 : else if (propagate_subaccesses_from_rhs (lacc, racc))
3396 : reque_parents = true;
3397 :
3398 : if (reque_parents)
3399 1221558 : do
3400 : {
3401 1221558 : add_access_to_rhs_work_queue (lacc);
3402 1221558 : lacc = lacc->parent;
3403 : }
3404 1221558 : while (lacc);
3405 : }
3406 : }
3407 :
3408 2006997 : while (lhs_work_queue_head)
3409 : {
3410 1299457 : struct access *lacc = pop_access_from_lhs_work_queue ();
3411 1299457 : struct assign_link *link;
3412 :
3413 1299457 : if (lacc->group_representative)
3414 1296271 : lacc = lacc->group_representative;
3415 1299457 : gcc_assert (lacc->first_lhs_link);
3416 :
3417 1299457 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3418 3879 : continue;
3419 :
3420 3554316 : for (link = lacc->first_lhs_link; link; link = link->next_lhs)
3421 : {
3422 2258738 : struct access *racc = link->racc;
3423 :
3424 2258738 : if (racc->group_representative)
3425 2258206 : racc = racc->group_representative;
3426 2258738 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3427 741 : continue;
3428 2257997 : if (propagate_subaccesses_from_lhs (lacc, racc))
3429 347692 : add_access_to_lhs_work_queue (racc);
3430 : }
3431 : }
3432 1415080 : delete propagation_budget;
3433 707540 : }
3434 :
3435 : /* Return true if the forest beginning with ROOT does not contain
3436 : unscalarizable regions or non-byte aligned accesses. */
3437 :
3438 : static bool
3439 740744 : can_totally_scalarize_forest_p (struct access *root)
3440 : {
3441 740744 : struct access *access = root;
3442 2141715 : do
3443 : {
3444 2141715 : if (access->grp_unscalarizable_region
3445 2139745 : || (access->offset % BITS_PER_UNIT) != 0
3446 2139387 : || (access->size % BITS_PER_UNIT) != 0
3447 4278313 : || (is_gimple_reg_type (access->type)
3448 1403133 : && access->first_child))
3449 : return false;
3450 :
3451 2136315 : if (access->first_child)
3452 : access = access->first_child;
3453 1521818 : else if (access->next_sibling)
3454 : access = access->next_sibling;
3455 : else
3456 : {
3457 1422129 : while (access->parent && !access->next_sibling)
3458 : access = access->parent;
3459 811550 : if (access->next_sibling)
3460 : access = access->next_sibling;
3461 : else
3462 : {
3463 758498 : gcc_assert (access == root);
3464 758498 : root = root->next_grp;
3465 758498 : access = root;
3466 : }
3467 : }
3468 : }
3469 2136315 : while (access);
3470 : return true;
3471 : }
3472 :
3473 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3474 : reference EXPR for total scalarization purposes and mark it as such. Within
3475 : the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3476 :
3477 : static struct access *
3478 486811 : create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos,
3479 : HOST_WIDE_INT size, tree type, tree expr,
3480 : struct access **ptr,
3481 : struct access *next_sibling)
3482 : {
3483 486811 : struct access *access = access_pool.allocate ();
3484 486811 : memset (access, 0, sizeof (struct access));
3485 486811 : access->base = parent->base;
3486 486811 : access->offset = pos;
3487 486811 : access->size = size;
3488 486811 : access->expr = expr;
3489 486811 : access->type = type;
3490 486811 : access->parent = parent;
3491 486811 : access->grp_write = parent->grp_write;
3492 486811 : access->grp_total_scalarization = 1;
3493 486811 : access->grp_hint = 1;
3494 486811 : access->grp_same_access_path = 0;
3495 486811 : access->reverse = reverse_storage_order_for_component_p (expr);
3496 :
3497 486811 : access->next_sibling = next_sibling;
3498 486811 : *ptr = access;
3499 486811 : return access;
3500 : }
3501 :
3502 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3503 : reference EXPR for total scalarization purposes and mark it as such, link it
3504 : at *PTR and reshape the tree so that those elements at *PTR and their
3505 : siblings which fall within the part described by POS and SIZE are moved to
3506 : be children of the new access. If a partial overlap is detected, return
3507 : NULL. */
3508 :
3509 : static struct access *
3510 486811 : create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos,
3511 : HOST_WIDE_INT size, tree type, tree expr,
3512 : struct access **ptr)
3513 : {
3514 486811 : struct access **p = ptr;
3515 :
3516 673542 : while (*p && (*p)->offset < pos + size)
3517 : {
3518 186731 : if ((*p)->offset + (*p)->size > pos + size)
3519 : return NULL;
3520 186731 : p = &(*p)->next_sibling;
3521 : }
3522 :
3523 486811 : struct access *next_child = *ptr;
3524 486811 : struct access *new_acc
3525 486811 : = create_total_scalarization_access (parent, pos, size, type, expr,
3526 : ptr, *p);
3527 486811 : if (p != ptr)
3528 : {
3529 76028 : new_acc->first_child = next_child;
3530 76028 : *p = NULL;
3531 262759 : for (struct access *a = next_child; a; a = a->next_sibling)
3532 186731 : a->parent = new_acc;
3533 : }
3534 : return new_acc;
3535 : }
3536 :
3537 : static bool totally_scalarize_subtree (struct access *root);
3538 :
3539 : /* Return true if INNER is either the same type as OUTER or if it is the type
3540 : of a record field in OUTER at offset zero, possibly in nested
3541 : sub-records. */
3542 :
3543 : static bool
3544 180545 : access_and_field_type_match_p (tree outer, tree inner)
3545 : {
3546 180545 : if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner))
3547 : return true;
3548 411 : if (TREE_CODE (outer) != RECORD_TYPE)
3549 : return false;
3550 406 : tree fld = TYPE_FIELDS (outer);
3551 6920 : while (fld)
3552 : {
3553 6763 : if (TREE_CODE (fld) == FIELD_DECL)
3554 : {
3555 434 : if (!zerop (DECL_FIELD_OFFSET (fld)))
3556 : return false;
3557 434 : if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner)
3558 : return true;
3559 369 : if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE)
3560 185 : fld = TYPE_FIELDS (TREE_TYPE (fld));
3561 : else
3562 : return false;
3563 : }
3564 : else
3565 6329 : fld = DECL_CHAIN (fld);
3566 : }
3567 : return false;
3568 : }
3569 :
3570 : /* Return type of total_should_skip_creating_access indicating whether a total
3571 : scalarization access for a field/element should be created, whether it
3572 : already exists or whether the entire total scalarization has to fail. */
3573 :
3574 : enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED};
3575 :
3576 : /* Do all the necessary steps in total scalarization when the given aggregate
3577 : type has a TYPE at POS with the given SIZE should be put into PARENT and
3578 : when we have processed all its siblings with smaller offsets up until and
3579 : including LAST_SEEN_SIBLING (which can be NULL).
3580 :
3581 : If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3582 : appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3583 : creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3584 : representing the described part of the aggregate for the purposes of total
3585 : scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3586 : prevents total scalarization from happening at all. */
3587 :
3588 : static enum total_sra_field_state
3589 1799832 : total_should_skip_creating_access (struct access *parent,
3590 : struct access **last_seen_sibling,
3591 : tree type, HOST_WIDE_INT pos,
3592 : HOST_WIDE_INT size)
3593 : {
3594 1799832 : struct access *next_child;
3595 1799832 : if (!*last_seen_sibling)
3596 818034 : next_child = parent->first_child;
3597 : else
3598 981798 : next_child = (*last_seen_sibling)->next_sibling;
3599 :
3600 : /* First, traverse the chain of siblings until it points to an access with
3601 : offset at least equal to POS. Check all skipped accesses whether they
3602 : span the POS boundary and if so, return with a failure. */
3603 1799833 : while (next_child && next_child->offset < pos)
3604 : {
3605 1 : if (next_child->offset + next_child->size > pos)
3606 : return TOTAL_FLD_FAILED;
3607 1 : *last_seen_sibling = next_child;
3608 1 : next_child = next_child->next_sibling;
3609 : }
3610 :
3611 : /* Now check whether next_child has exactly the right POS and SIZE and if so,
3612 : whether it can represent what we need and can be totally scalarized
3613 : itself. */
3614 1799832 : if (next_child && next_child->offset == pos
3615 1386078 : && next_child->size == size)
3616 : {
3617 1312873 : if (!is_gimple_reg_type (next_child->type)
3618 1312873 : && (!access_and_field_type_match_p (type, next_child->type)
3619 180199 : || !totally_scalarize_subtree (next_child)))
3620 392 : return TOTAL_FLD_FAILED;
3621 :
3622 1312481 : *last_seen_sibling = next_child;
3623 1312481 : return TOTAL_FLD_DONE;
3624 : }
3625 :
3626 : /* If the child we're looking at would partially overlap, we just cannot
3627 : totally scalarize. */
3628 : if (next_child
3629 103195 : && next_child->offset < pos + size
3630 76176 : && next_child->offset + next_child->size > pos + size)
3631 : return TOTAL_FLD_FAILED;
3632 :
3633 486923 : if (is_gimple_reg_type (type))
3634 : {
3635 : /* We don't scalarize accesses that are children of other scalar type
3636 : accesses, so if we go on and create an access for a register type,
3637 : there should not be any pre-existing children. There are rare cases
3638 : where the requested type is a vector but we already have register
3639 : accesses for all its elements which is equally good. Detect that
3640 : situation or whether we need to bail out. */
3641 :
3642 : HOST_WIDE_INT covered = pos;
3643 : bool skipping = false;
3644 : while (next_child
3645 371399 : && next_child->offset + next_child->size <= pos + size)
3646 : {
3647 428 : if (next_child->offset != covered
3648 428 : || !is_gimple_reg_type (next_child->type))
3649 : return TOTAL_FLD_FAILED;
3650 :
3651 428 : covered += next_child->size;
3652 428 : *last_seen_sibling = next_child;
3653 428 : next_child = next_child->next_sibling;
3654 428 : skipping = true;
3655 : }
3656 :
3657 370971 : if (skipping)
3658 : {
3659 112 : if (covered != pos + size)
3660 : return TOTAL_FLD_FAILED;
3661 : else
3662 : return TOTAL_FLD_DONE;
3663 : }
3664 : }
3665 :
3666 : return TOTAL_FLD_CREATE;
3667 : }
3668 :
3669 : /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3670 : spanning all uncovered areas covered by ROOT, return false if the attempt
3671 : failed. All created accesses will have grp_unscalarizable_region set (and
3672 : should be ignored if the function returns false). */
3673 :
3674 : static bool
3675 818382 : totally_scalarize_subtree (struct access *root)
3676 : {
3677 818382 : gcc_checking_assert (!root->grp_unscalarizable_region);
3678 818382 : gcc_checking_assert (!is_gimple_reg_type (root->type));
3679 :
3680 818382 : struct access *last_seen_sibling = NULL;
3681 :
3682 818382 : switch (TREE_CODE (root->type))
3683 : {
3684 804901 : case RECORD_TYPE:
3685 9449171 : for (tree fld = TYPE_FIELDS (root->type); fld; fld = DECL_CHAIN (fld))
3686 8644741 : if (TREE_CODE (fld) == FIELD_DECL)
3687 : {
3688 1800558 : tree ft = TREE_TYPE (fld);
3689 1800558 : HOST_WIDE_INT fsize = tree_to_uhwi (DECL_SIZE (fld));
3690 1800558 : if (!fsize)
3691 31178 : continue;
3692 :
3693 1769380 : HOST_WIDE_INT pos = root->offset + int_bit_position (fld);
3694 1769380 : if (pos + fsize > root->offset + root->size)
3695 : return false;
3696 1769380 : enum total_sra_field_state
3697 1769380 : state = total_should_skip_creating_access (root,
3698 : &last_seen_sibling,
3699 : ft, pos, fsize);
3700 1769380 : switch (state)
3701 : {
3702 : case TOTAL_FLD_FAILED:
3703 : return false;
3704 1306084 : case TOTAL_FLD_DONE:
3705 1306084 : continue;
3706 462896 : case TOTAL_FLD_CREATE:
3707 462896 : break;
3708 0 : default:
3709 0 : gcc_unreachable ();
3710 : }
3711 :
3712 462896 : struct access **p = (last_seen_sibling
3713 462896 : ? &last_seen_sibling->next_sibling
3714 : : &root->first_child);
3715 462896 : tree nref = build3 (COMPONENT_REF, ft, root->expr, fld, NULL_TREE);
3716 462896 : struct access *new_child
3717 462896 : = create_total_access_and_reshape (root, pos, fsize, ft, nref, p);
3718 462896 : if (!new_child)
3719 : return false;
3720 :
3721 462896 : if (!is_gimple_reg_type (ft)
3722 462896 : && !totally_scalarize_subtree (new_child))
3723 : return false;
3724 462825 : last_seen_sibling = new_child;
3725 : }
3726 : break;
3727 13481 : case ARRAY_TYPE:
3728 13481 : {
3729 13481 : tree elemtype = TREE_TYPE (root->type);
3730 13481 : HOST_WIDE_INT el_size;
3731 13481 : offset_int idx, max;
3732 13481 : if (!prepare_iteration_over_array_elts (root->type, &el_size,
3733 : &idx, &max))
3734 : break;
3735 :
3736 13481 : for (HOST_WIDE_INT pos = root->offset;
3737 43885 : idx <= max;
3738 30404 : pos += el_size, ++idx)
3739 : {
3740 30452 : enum total_sra_field_state
3741 30452 : state = total_should_skip_creating_access (root,
3742 : &last_seen_sibling,
3743 : elemtype, pos,
3744 : el_size);
3745 30452 : switch (state)
3746 : {
3747 : case TOTAL_FLD_FAILED:
3748 48 : return false;
3749 6489 : case TOTAL_FLD_DONE:
3750 6489 : continue;
3751 23915 : case TOTAL_FLD_CREATE:
3752 23915 : break;
3753 0 : default:
3754 0 : gcc_unreachable ();
3755 : }
3756 :
3757 23915 : struct access **p = (last_seen_sibling
3758 23915 : ? &last_seen_sibling->next_sibling
3759 : : &root->first_child);
3760 47830 : tree nref = build4 (ARRAY_REF, elemtype, root->expr,
3761 23915 : wide_int_to_tree (TYPE_DOMAIN (root->type),
3762 23915 : idx),
3763 : NULL_TREE, NULL_TREE);
3764 23915 : struct access *new_child
3765 23915 : = create_total_access_and_reshape (root, pos, el_size, elemtype,
3766 : nref, p);
3767 23915 : if (!new_child)
3768 : return false;
3769 :
3770 23915 : if (!is_gimple_reg_type (elemtype)
3771 23915 : && !totally_scalarize_subtree (new_child))
3772 : return false;
3773 23915 : last_seen_sibling = new_child;
3774 : }
3775 : }
3776 13433 : break;
3777 0 : default:
3778 0 : gcc_unreachable ();
3779 : }
3780 : return true;
3781 : }
3782 :
3783 : /* Get the total total scalarization size limit in the current function. */
3784 :
3785 : unsigned HOST_WIDE_INT
3786 714386 : sra_get_max_scalarization_size (void)
3787 : {
3788 714386 : bool optimize_speed_p = !optimize_function_for_size_p (cfun);
3789 : /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3790 : fall back to a target default. */
3791 714386 : unsigned HOST_WIDE_INT max_scalarization_size
3792 714386 : = get_move_ratio (optimize_speed_p) * MOVE_MAX;
3793 :
3794 714386 : if (optimize_speed_p)
3795 : {
3796 694480 : if (OPTION_SET_P (param_sra_max_scalarization_size_speed))
3797 9 : max_scalarization_size = param_sra_max_scalarization_size_speed;
3798 : }
3799 : else
3800 : {
3801 19906 : if (OPTION_SET_P (param_sra_max_scalarization_size_size))
3802 0 : max_scalarization_size = param_sra_max_scalarization_size_size;
3803 : }
3804 714386 : max_scalarization_size *= BITS_PER_UNIT;
3805 714386 : return max_scalarization_size;
3806 : }
3807 :
3808 : /* Go through all accesses collected throughout the (intraprocedural) analysis
3809 : stage, exclude overlapping ones, identify representatives and build trees
3810 : out of them, making decisions about scalarization on the way. Return true
3811 : iff there are any to-be-scalarized variables after this stage. */
3812 :
3813 : static bool
3814 707540 : analyze_all_variable_accesses (void)
3815 : {
3816 707540 : int res = 0;
3817 707540 : bitmap tmp = BITMAP_ALLOC (NULL);
3818 707540 : bitmap_iterator bi;
3819 707540 : unsigned i;
3820 :
3821 707540 : bitmap_copy (tmp, candidate_bitmap);
3822 4708022 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3823 : {
3824 4000482 : tree var = candidate (i);
3825 4000482 : struct access *access;
3826 :
3827 4000482 : access = sort_and_splice_var_accesses (var);
3828 4000482 : if (!access || !build_access_trees (access))
3829 162539 : disqualify_candidate (var,
3830 : "No or inhibitingly overlapping accesses.");
3831 : }
3832 :
3833 707540 : propagate_all_subaccesses ();
3834 :
3835 707540 : unsigned HOST_WIDE_INT max_scalarization_size
3836 707540 : = sra_get_max_scalarization_size ();
3837 4545483 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3838 3837943 : if (bitmap_bit_p (should_scalarize_away_bitmap, i)
3839 3837943 : && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
3840 : {
3841 813266 : tree var = candidate (i);
3842 813266 : if (!VAR_P (var))
3843 71662 : continue;
3844 :
3845 741604 : if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) > max_scalarization_size)
3846 : {
3847 7149 : if (dump_file && (dump_flags & TDF_DETAILS))
3848 : {
3849 0 : fprintf (dump_file, "Too big to totally scalarize: ");
3850 0 : print_generic_expr (dump_file, var);
3851 0 : fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
3852 : }
3853 7149 : continue;
3854 : }
3855 :
3856 734455 : bool all_types_ok = true;
3857 734455 : for (struct access *access = get_first_repr_for_decl (var);
3858 1453388 : access;
3859 718933 : access = access->next_grp)
3860 740744 : if (!can_totally_scalarize_forest_p (access)
3861 1476088 : || !totally_scalarizable_type_p (access->type,
3862 735344 : constant_decl_p (var),
3863 : 0, nullptr))
3864 : {
3865 : all_types_ok = false;
3866 : break;
3867 : }
3868 734455 : if (!all_types_ok)
3869 21811 : continue;
3870 :
3871 712644 : if (dump_file && (dump_flags & TDF_DETAILS))
3872 : {
3873 1 : fprintf (dump_file, "Will attempt to totally scalarize ");
3874 1 : print_generic_expr (dump_file, var);
3875 1 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3876 : }
3877 712644 : bool scalarized = true;
3878 712644 : for (struct access *access = get_first_repr_for_decl (var);
3879 1431173 : access;
3880 718529 : access = access->next_grp)
3881 718931 : if (!is_gimple_reg_type (access->type)
3882 718931 : && !totally_scalarize_subtree (access))
3883 : {
3884 : scalarized = false;
3885 : break;
3886 : }
3887 :
3888 712644 : if (scalarized)
3889 712242 : for (struct access *access = get_first_repr_for_decl (var);
3890 1430771 : access;
3891 718529 : access = access->next_grp)
3892 718529 : access->grp_total_scalarization = true;
3893 : }
3894 :
3895 707540 : if (flag_checking)
3896 707540 : verify_all_sra_access_forests ();
3897 :
3898 707540 : bitmap_copy (tmp, candidate_bitmap);
3899 4545483 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3900 : {
3901 3837943 : tree var = candidate (i);
3902 3837943 : struct access *access = get_first_repr_for_decl (var);
3903 :
3904 3837943 : if (analyze_access_trees (access))
3905 : {
3906 1751743 : res++;
3907 1751743 : if (dump_file && (dump_flags & TDF_DETAILS))
3908 : {
3909 8 : fprintf (dump_file, "\nAccess trees for ");
3910 8 : print_generic_expr (dump_file, var);
3911 8 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3912 8 : dump_access_tree (dump_file, access);
3913 8 : fprintf (dump_file, "\n");
3914 : }
3915 : }
3916 : else
3917 2086200 : disqualify_candidate (var, "No scalar replacements to be created.");
3918 : }
3919 :
3920 707540 : BITMAP_FREE (tmp);
3921 :
3922 707540 : if (res)
3923 : {
3924 420484 : statistics_counter_event (cfun, "Scalarized aggregates", res);
3925 420484 : return true;
3926 : }
3927 : else
3928 : return false;
3929 : }
3930 :
3931 : /* Generate statements copying scalar replacements of accesses within a subtree
3932 : into or out of AGG. ACCESS, all its children, siblings and their children
3933 : are to be processed. AGG is an aggregate type expression (can be a
3934 : declaration but does not have to be, it can for example also be a mem_ref or
3935 : a series of handled components). TOP_OFFSET is the offset of the processed
3936 : subtree which has to be subtracted from offsets of individual accesses to
3937 : get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3938 : replacements in the interval <start_offset, start_offset + chunk_size>,
3939 : otherwise copy all. GSI is a statement iterator used to place the new
3940 : statements. WRITE should be true when the statements should write from AGG
3941 : to the replacement and false if vice versa. If INSERT_AFTER is true, new
3942 : statements will be added after the current statement in GSI, they will be
3943 : added before the statement otherwise. If FORCE_REF_ALL is true then
3944 : memory accesses will use alias-set zero. */
3945 :
3946 : static void
3947 1898782 : generate_subtree_copies (struct access *access, tree agg,
3948 : HOST_WIDE_INT top_offset,
3949 : HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
3950 : gimple_stmt_iterator *gsi, bool write,
3951 : bool insert_after, location_t loc,
3952 : bool force_ref_all = false)
3953 : {
3954 : /* Never write anything into constant pool decls. See PR70602. */
3955 3797564 : if (!write && constant_decl_p (agg))
3956 : return;
3957 4612342 : do
3958 : {
3959 4612342 : if (chunk_size && access->offset >= start_offset + chunk_size)
3960 : return;
3961 :
3962 4612342 : if (access->grp_to_be_replaced
3963 3613671 : && (chunk_size == 0
3964 0 : || access->offset + access->size > start_offset))
3965 : {
3966 3613671 : tree expr, repl = get_access_replacement (access);
3967 3613671 : gassign *stmt;
3968 :
3969 3613671 : expr = build_ref_for_model (loc, agg, access->offset - top_offset,
3970 : access, gsi, insert_after, force_ref_all);
3971 :
3972 3613671 : if (write)
3973 : {
3974 1639225 : if (access->grp_partial_lhs)
3975 8 : expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
3976 8 : !insert_after,
3977 : insert_after ? GSI_NEW_STMT
3978 : : GSI_SAME_STMT);
3979 1639225 : stmt = gimple_build_assign (repl, expr);
3980 : }
3981 : else
3982 : {
3983 1974446 : suppress_warning (repl /* Be more selective! */);
3984 1974446 : if (access->grp_partial_lhs)
3985 72 : repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3986 72 : !insert_after,
3987 : insert_after ? GSI_NEW_STMT
3988 : : GSI_SAME_STMT);
3989 1974446 : stmt = gimple_build_assign (expr, repl);
3990 : }
3991 3613671 : gimple_set_location (stmt, loc);
3992 :
3993 3613671 : if (insert_after)
3994 1639225 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3995 : else
3996 1974446 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3997 3613671 : update_stmt (stmt);
3998 3613671 : sra_stats.subtree_copies++;
3999 3613671 : }
4000 998671 : else if (write
4001 385923 : && access->grp_to_be_debug_replaced
4002 5724 : && (chunk_size == 0
4003 0 : || access->offset + access->size > start_offset))
4004 : {
4005 5724 : gdebug *ds;
4006 11448 : tree drhs = build_debug_ref_for_model (loc, agg,
4007 5724 : access->offset - top_offset,
4008 : access);
4009 5724 : ds = gimple_build_debug_bind (get_access_replacement (access),
4010 : drhs, gsi_stmt (*gsi));
4011 5724 : if (insert_after)
4012 5724 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4013 : else
4014 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4015 : }
4016 :
4017 4612342 : if (access->first_child)
4018 458851 : generate_subtree_copies (access->first_child, agg, top_offset,
4019 : start_offset, chunk_size, gsi,
4020 : write, insert_after, loc, force_ref_all);
4021 :
4022 4612342 : access = access->next_sibling;
4023 : }
4024 4612342 : while (access);
4025 : }
4026 :
4027 : /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
4028 : root of the subtree to be processed. GSI is the statement iterator used
4029 : for inserting statements which are added after the current statement if
4030 : INSERT_AFTER is true or before it otherwise. */
4031 :
4032 : static void
4033 541084 : init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
4034 : bool insert_after, location_t loc)
4035 :
4036 : {
4037 541084 : struct access *child;
4038 :
4039 541084 : if (access->grp_to_be_replaced)
4040 : {
4041 248761 : gassign *stmt;
4042 :
4043 248761 : stmt = gimple_build_assign (get_access_replacement (access),
4044 : build_zero_cst (access->type));
4045 248761 : if (insert_after)
4046 33393 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4047 : else
4048 215368 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4049 248761 : update_stmt (stmt);
4050 248761 : gimple_set_location (stmt, loc);
4051 : }
4052 292323 : else if (access->grp_to_be_debug_replaced)
4053 : {
4054 29417 : gdebug *ds
4055 29417 : = gimple_build_debug_bind (get_access_replacement (access),
4056 : build_zero_cst (access->type),
4057 : gsi_stmt (*gsi));
4058 29417 : if (insert_after)
4059 29417 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4060 : else
4061 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4062 : }
4063 :
4064 935806 : for (child = access->first_child; child; child = child->next_sibling)
4065 394722 : init_subtree_with_zero (child, gsi, insert_after, loc);
4066 541084 : }
4067 :
4068 : /* Clobber all scalar replacements in an access subtree. ACCESS is the
4069 : root of the subtree to be processed. GSI is the statement iterator used
4070 : for inserting statements which are added after the current statement if
4071 : INSERT_AFTER is true or before it otherwise. */
4072 :
4073 : static void
4074 2780241 : clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
4075 : bool insert_after, location_t loc)
4076 :
4077 : {
4078 2780241 : struct access *child;
4079 :
4080 2780241 : if (access->grp_to_be_replaced)
4081 : {
4082 1776410 : tree rep = get_access_replacement (access);
4083 1776410 : tree clobber = build_clobber (access->type);
4084 1776410 : gimple *stmt = gimple_build_assign (rep, clobber);
4085 :
4086 1776410 : if (insert_after)
4087 358860 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4088 : else
4089 1417550 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4090 1776410 : update_stmt (stmt);
4091 1776410 : gimple_set_location (stmt, loc);
4092 : }
4093 :
4094 4575728 : for (child = access->first_child; child; child = child->next_sibling)
4095 1795487 : clobber_subtree (child, gsi, insert_after, loc);
4096 2780241 : }
4097 :
4098 : /* Search for an access representative for the given expression EXPR and
4099 : return it or NULL if it cannot be found. */
4100 :
4101 : static struct access *
4102 46140466 : get_access_for_expr (tree expr)
4103 : {
4104 46140466 : poly_int64 poffset, psize, pmax_size;
4105 46140466 : HOST_WIDE_INT offset, max_size;
4106 46140466 : tree base;
4107 46140466 : bool reverse;
4108 :
4109 46140466 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
4110 : &reverse);
4111 46140466 : if (!known_size_p (pmax_size)
4112 45991440 : || !pmax_size.is_constant (&max_size)
4113 45991440 : || !poffset.is_constant (&offset)
4114 46140466 : || !DECL_P (base))
4115 : return NULL;
4116 :
4117 21626726 : if (tree basesize = DECL_SIZE (base))
4118 : {
4119 21583106 : poly_int64 sz;
4120 21583106 : if (offset < 0
4121 21583090 : || !poly_int_tree_p (basesize, &sz)
4122 43166196 : || known_le (sz, offset))
4123 7023 : return NULL;
4124 : }
4125 :
4126 21619703 : if (max_size == 0
4127 21619703 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
4128 12538938 : return NULL;
4129 :
4130 9080765 : return get_var_base_offset_size_access (base, offset, max_size);
4131 : }
4132 :
4133 : /* Replace the expression EXPR with a scalar replacement if there is one and
4134 : generate other statements to do type conversion or subtree copying if
4135 : necessary. WRITE is true if the expression is being written to (it is on a
4136 : LHS of a statement or output in an assembly statement). STMT_GSI is used to
4137 : place newly created statements before the processed statement, REFRESH_GSI
4138 : is used to place them afterwards - unless the processed statement must end a
4139 : BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
4140 : is then used to continue iteration over the BB. If sra_modify_expr is
4141 : called only once with WRITE equal to true on a given statement, both
4142 : iterator parameters can point to the same one. */
4143 :
4144 : static bool
4145 7430325 : sra_modify_expr (tree *expr, bool write, gimple_stmt_iterator *stmt_gsi,
4146 : gimple_stmt_iterator *refresh_gsi)
4147 : {
4148 7430325 : location_t loc;
4149 7430325 : struct access *access;
4150 7430325 : tree type, bfr, orig_expr;
4151 7430325 : bool partial_cplx_access = false;
4152 :
4153 7430325 : if (TREE_CODE (*expr) == BIT_FIELD_REF
4154 7430325 : && (write || !sra_handled_bf_read_p (*expr)))
4155 : {
4156 586 : bfr = *expr;
4157 586 : expr = &TREE_OPERAND (*expr, 0);
4158 : }
4159 : else
4160 : bfr = NULL_TREE;
4161 :
4162 7430325 : if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
4163 : {
4164 24831 : expr = &TREE_OPERAND (*expr, 0);
4165 24831 : partial_cplx_access = true;
4166 : }
4167 7430325 : access = get_access_for_expr (*expr);
4168 7430325 : if (!access)
4169 : return false;
4170 193784 : type = TREE_TYPE (*expr);
4171 193784 : orig_expr = *expr;
4172 :
4173 193784 : loc = gimple_location (gsi_stmt (*stmt_gsi));
4174 193784 : gimple_stmt_iterator alt_gsi = gsi_none ();
4175 193784 : if (write && stmt_ends_bb_p (gsi_stmt (*stmt_gsi)))
4176 : {
4177 35947 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi)));
4178 35947 : refresh_gsi = &alt_gsi;
4179 : }
4180 :
4181 193784 : if (access->grp_to_be_replaced)
4182 : {
4183 47868 : tree repl = get_access_replacement (access);
4184 : /* If we replace a non-register typed access simply use the original
4185 : access expression to extract the scalar component afterwards.
4186 : This happens if scalarizing a function return value or parameter
4187 : like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
4188 : gcc.c-torture/compile/20011217-1.c.
4189 :
4190 : We also want to use this when accessing a complex or vector which can
4191 : be accessed as a different type too, potentially creating a need for
4192 : type conversion (see PR42196) and when scalarized unions are involved
4193 : in assembler statements (see PR42398). */
4194 47868 : if (!bfr && !useless_type_conversion_p (type, access->type))
4195 : {
4196 44432 : tree ref;
4197 :
4198 44432 : ref = build_ref_for_model (loc, orig_expr, 0, access, stmt_gsi,
4199 : false);
4200 :
4201 44432 : if (partial_cplx_access)
4202 : {
4203 : /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4204 : the case of a write because in such case the replacement cannot
4205 : be a gimple register. In the case of a load, we have to
4206 : differentiate in between a register an non-register
4207 : replacement. */
4208 29 : tree t = build1 (VIEW_CONVERT_EXPR, type, repl);
4209 29 : gcc_checking_assert (!write || access->grp_partial_lhs);
4210 29 : if (!access->grp_partial_lhs)
4211 : {
4212 26 : tree tmp = make_ssa_name (type);
4213 26 : gassign *stmt = gimple_build_assign (tmp, t);
4214 : /* This is always a read. */
4215 26 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4216 26 : t = tmp;
4217 : }
4218 29 : *expr = t;
4219 : }
4220 44403 : else if (write)
4221 : {
4222 10639 : gassign *stmt;
4223 :
4224 10639 : if (access->grp_partial_lhs)
4225 6 : ref = force_gimple_operand_gsi (refresh_gsi, ref, true,
4226 : NULL_TREE, false, GSI_NEW_STMT);
4227 10639 : stmt = gimple_build_assign (repl, ref);
4228 10639 : gimple_set_location (stmt, loc);
4229 10639 : gsi_insert_after (refresh_gsi, stmt, GSI_NEW_STMT);
4230 : }
4231 : else
4232 : {
4233 33764 : if (TREE_READONLY (access->base))
4234 : return false;
4235 :
4236 33745 : gassign *stmt;
4237 33745 : if (access->grp_partial_lhs)
4238 15 : repl = force_gimple_operand_gsi (stmt_gsi, repl, true,
4239 : NULL_TREE, true,
4240 : GSI_SAME_STMT);
4241 33745 : stmt = gimple_build_assign (ref, repl);
4242 33745 : gimple_set_location (stmt, loc);
4243 33745 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4244 : }
4245 : }
4246 : else
4247 : {
4248 : /* If we are going to replace a scalar field in a structure with
4249 : reverse storage order by a stand-alone scalar, we are going to
4250 : effectively byte-swap the scalar and we also need to byte-swap
4251 : the portion of it represented by the bit-field. */
4252 3436 : if (bfr && REF_REVERSE_STORAGE_ORDER (bfr))
4253 : {
4254 0 : REF_REVERSE_STORAGE_ORDER (bfr) = 0;
4255 0 : TREE_OPERAND (bfr, 2)
4256 0 : = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (repl)),
4257 : size_binop (PLUS_EXPR, TREE_OPERAND (bfr, 1),
4258 : TREE_OPERAND (bfr, 2)));
4259 : }
4260 :
4261 3436 : *expr = repl;
4262 : }
4263 :
4264 47849 : sra_stats.exprs++;
4265 : }
4266 145916 : else if (write && access->grp_to_be_debug_replaced)
4267 : {
4268 12 : gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
4269 : NULL_TREE,
4270 : gsi_stmt (*stmt_gsi));
4271 12 : gsi_insert_after (stmt_gsi, ds, GSI_NEW_STMT);
4272 : }
4273 :
4274 193765 : if (access->first_child && !TREE_READONLY (access->base))
4275 : {
4276 142289 : HOST_WIDE_INT start_offset, chunk_size;
4277 142289 : if (bfr
4278 0 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
4279 142289 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
4280 : {
4281 0 : chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
4282 0 : start_offset = access->offset
4283 0 : + tree_to_uhwi (TREE_OPERAND (bfr, 2));
4284 : }
4285 : else
4286 : start_offset = chunk_size = 0;
4287 :
4288 237712 : generate_subtree_copies (access->first_child, orig_expr, access->offset,
4289 : start_offset, chunk_size,
4290 : write ? refresh_gsi : stmt_gsi,
4291 : write, write, loc);
4292 : }
4293 : return true;
4294 : }
4295 :
4296 : /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4297 : reads from its base before and after the call statement given in CALL_GSI
4298 : and return true if any copying took place. Otherwise call sra_modify_expr
4299 : on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4300 : return for the given parameter. */
4301 :
4302 : static bool
4303 8190241 : sra_modify_call_arg (tree *expr, gimple_stmt_iterator *call_gsi,
4304 : gimple_stmt_iterator *refresh_gsi, int flags)
4305 : {
4306 8190241 : if (TREE_CODE (*expr) != ADDR_EXPR)
4307 5383872 : return sra_modify_expr (expr, false, call_gsi, refresh_gsi);
4308 :
4309 2806369 : if (flags & EAF_UNUSED)
4310 : return false;
4311 :
4312 2802795 : tree base = get_base_address (TREE_OPERAND (*expr, 0));
4313 2802795 : if (!DECL_P (base))
4314 : return false;
4315 2125022 : struct access *access = get_access_for_expr (base);
4316 2125022 : if (!access)
4317 : return false;
4318 :
4319 50286 : gimple *stmt = gsi_stmt (*call_gsi);
4320 50286 : location_t loc = gimple_location (stmt);
4321 50286 : generate_subtree_copies (access, base, 0, 0, 0, call_gsi, false, false,
4322 : loc, true);
4323 :
4324 50286 : if (flags & EAF_NO_DIRECT_CLOBBER)
4325 : return true;
4326 :
4327 35562 : if (!stmt_ends_bb_p (stmt))
4328 25316 : generate_subtree_copies (access, base, 0, 0, 0, refresh_gsi, true,
4329 : true, loc, true);
4330 : else
4331 : {
4332 10246 : edge e;
4333 10246 : edge_iterator ei;
4334 30715 : FOR_EACH_EDGE (e, ei, gsi_bb (*call_gsi)->succs)
4335 : {
4336 20469 : gimple_stmt_iterator alt_gsi = gsi_start_edge (e);
4337 20469 : generate_subtree_copies (access, base, 0, 0, 0, &alt_gsi, true,
4338 : true, loc, true);
4339 : }
4340 : }
4341 : return true;
4342 : }
4343 :
4344 : /* Where scalar replacements of the RHS have been written to when a replacement
4345 : of a LHS of an assigments cannot be direclty loaded from a replacement of
4346 : the RHS. */
4347 : enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
4348 : SRA_UDH_RIGHT, /* Data flushed to the RHS. */
4349 : SRA_UDH_LEFT }; /* Data flushed to the LHS. */
4350 :
4351 : struct subreplacement_assignment_data
4352 : {
4353 : /* Offset of the access representing the lhs of the assignment. */
4354 : HOST_WIDE_INT left_offset;
4355 :
4356 : /* LHS and RHS of the original assignment. */
4357 : tree assignment_lhs, assignment_rhs;
4358 :
4359 : /* Access representing the rhs of the whole assignment. */
4360 : struct access *top_racc;
4361 :
4362 : /* Stmt iterator used for statement insertions after the original assignment.
4363 : It points to the main GSI used to traverse a BB during function body
4364 : modification. */
4365 : gimple_stmt_iterator *new_gsi;
4366 :
4367 : /* Stmt iterator used for statement insertions before the original
4368 : assignment. Keeps on pointing to the original statement. */
4369 : gimple_stmt_iterator old_gsi;
4370 :
4371 : /* Location of the assignment. */
4372 : location_t loc;
4373 :
4374 : /* Keeps the information whether we have needed to refresh replacements of
4375 : the LHS and from which side of the assignments this takes place. */
4376 : enum unscalarized_data_handling refreshed;
4377 : };
4378 :
4379 : /* Store all replacements in the access tree rooted in TOP_RACC either to their
4380 : base aggregate if there are unscalarized data or directly to LHS of the
4381 : statement that is pointed to by GSI otherwise. */
4382 :
4383 : static void
4384 107531 : handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
4385 : {
4386 107531 : tree src;
4387 : /* If the RHS is a load from a constant, we do not need to (and must not)
4388 : flush replacements to it and can use it directly as if we did. */
4389 107531 : if (TREE_READONLY (sad->top_racc->base))
4390 : {
4391 7 : sad->refreshed = SRA_UDH_RIGHT;
4392 7 : return;
4393 : }
4394 107524 : if (sad->top_racc->grp_unscalarized_data)
4395 : {
4396 25227 : src = sad->assignment_rhs;
4397 25227 : sad->refreshed = SRA_UDH_RIGHT;
4398 : }
4399 : else
4400 : {
4401 82297 : src = sad->assignment_lhs;
4402 82297 : sad->refreshed = SRA_UDH_LEFT;
4403 : }
4404 107524 : generate_subtree_copies (sad->top_racc->first_child, src,
4405 : sad->top_racc->offset, 0, 0,
4406 : &sad->old_gsi, false, false, sad->loc);
4407 : }
4408 :
4409 : /* Try to generate statements to load all sub-replacements in an access subtree
4410 : formed by children of LACC from scalar replacements in the SAD->top_racc
4411 : subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4412 : and load the accesses from it. */
4413 :
4414 : static void
4415 491302 : load_assign_lhs_subreplacements (struct access *lacc,
4416 : struct subreplacement_assignment_data *sad)
4417 : {
4418 1615277 : for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
4419 : {
4420 1123975 : HOST_WIDE_INT offset;
4421 1123975 : offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
4422 :
4423 1123975 : if (lacc->grp_to_be_replaced)
4424 : {
4425 938559 : struct access *racc;
4426 938559 : gassign *stmt;
4427 938559 : tree rhs;
4428 :
4429 938559 : racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
4430 938559 : if (racc && racc->grp_to_be_replaced)
4431 : {
4432 912857 : rhs = get_access_replacement (racc);
4433 912857 : bool vce = false;
4434 912857 : if (!useless_type_conversion_p (lacc->type, racc->type))
4435 : {
4436 31 : rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4437 : lacc->type, rhs);
4438 31 : vce = true;
4439 : }
4440 :
4441 912857 : if (lacc->grp_partial_lhs && (vce || racc->grp_partial_lhs))
4442 3 : rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
4443 : NULL_TREE, true, GSI_SAME_STMT);
4444 : }
4445 : else
4446 : {
4447 : /* No suitable access on the right hand side, need to load from
4448 : the aggregate. See if we have to update it first... */
4449 25702 : if (sad->refreshed == SRA_UDH_NONE)
4450 12862 : handle_unscalarized_data_in_subtree (sad);
4451 :
4452 25702 : if (sad->refreshed == SRA_UDH_LEFT)
4453 482 : rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
4454 482 : lacc->offset - sad->left_offset,
4455 : lacc, sad->new_gsi, true);
4456 : else
4457 25220 : rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
4458 25220 : lacc->offset - sad->left_offset,
4459 : lacc, sad->new_gsi, true);
4460 25702 : if (lacc->grp_partial_lhs)
4461 1 : rhs = force_gimple_operand_gsi (sad->new_gsi,
4462 : rhs, true, NULL_TREE,
4463 : false, GSI_NEW_STMT);
4464 : }
4465 :
4466 938559 : stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
4467 938559 : gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
4468 938559 : gimple_set_location (stmt, sad->loc);
4469 938559 : update_stmt (stmt);
4470 938559 : sra_stats.subreplacements++;
4471 : }
4472 : else
4473 : {
4474 185416 : if (sad->refreshed == SRA_UDH_NONE
4475 27184 : && lacc->grp_read && !lacc->grp_covered)
4476 24 : handle_unscalarized_data_in_subtree (sad);
4477 :
4478 185416 : if (lacc && lacc->grp_to_be_debug_replaced)
4479 : {
4480 104650 : gdebug *ds;
4481 104650 : tree drhs;
4482 104650 : struct access *racc = find_access_in_subtree (sad->top_racc,
4483 : offset,
4484 : lacc->size);
4485 :
4486 104650 : if (racc && racc->grp_to_be_replaced)
4487 : {
4488 104501 : if (racc->grp_write || constant_decl_p (racc->base))
4489 101384 : drhs = get_access_replacement (racc);
4490 : else
4491 : drhs = NULL;
4492 : }
4493 149 : else if (sad->refreshed == SRA_UDH_LEFT)
4494 0 : drhs = build_debug_ref_for_model (sad->loc, lacc->base,
4495 : lacc->offset, lacc);
4496 149 : else if (sad->refreshed == SRA_UDH_RIGHT)
4497 147 : drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
4498 : offset, lacc);
4499 : else
4500 : drhs = NULL_TREE;
4501 101384 : if (drhs
4502 101531 : && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
4503 1941 : drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4504 : lacc->type, drhs);
4505 104650 : ds = gimple_build_debug_bind (get_access_replacement (lacc),
4506 : drhs, gsi_stmt (sad->old_gsi));
4507 104650 : gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
4508 : }
4509 : }
4510 :
4511 1123975 : if (lacc->first_child)
4512 36454 : load_assign_lhs_subreplacements (lacc, sad);
4513 : }
4514 491302 : }
4515 :
4516 : /* Result code for SRA assignment modification. */
4517 : enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
4518 : SRA_AM_MODIFIED, /* stmt changed but not
4519 : removed */
4520 : SRA_AM_REMOVED }; /* stmt eliminated */
4521 :
4522 : /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4523 : to the assignment and GSI is the statement iterator pointing at it. Returns
4524 : the same values as sra_modify_assign. */
4525 :
4526 : static enum assignment_mod_result
4527 2809438 : sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4528 : {
4529 2809438 : tree lhs = gimple_assign_lhs (stmt);
4530 2809438 : struct access *acc = get_access_for_expr (lhs);
4531 2809438 : if (!acc)
4532 : return SRA_AM_NONE;
4533 1131116 : location_t loc = gimple_location (stmt);
4534 :
4535 1131116 : if (gimple_clobber_p (stmt))
4536 : {
4537 : /* Clobber the replacement variable. */
4538 984754 : clobber_subtree (acc, gsi, !acc->grp_covered, loc);
4539 : /* Remove clobbers of fully scalarized variables, they are dead. */
4540 984754 : if (acc->grp_covered)
4541 : {
4542 750420 : unlink_stmt_vdef (stmt);
4543 750420 : gsi_remove (gsi, true);
4544 750420 : release_defs (stmt);
4545 750420 : return SRA_AM_REMOVED;
4546 : }
4547 : else
4548 : return SRA_AM_MODIFIED;
4549 : }
4550 :
4551 146362 : if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
4552 : {
4553 : /* I have never seen this code path trigger but if it can happen the
4554 : following should handle it gracefully. */
4555 0 : if (access_has_children_p (acc))
4556 0 : generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
4557 : true, true, loc);
4558 0 : return SRA_AM_MODIFIED;
4559 : }
4560 :
4561 146362 : if (acc->grp_covered)
4562 : {
4563 80666 : init_subtree_with_zero (acc, gsi, false, loc);
4564 80666 : unlink_stmt_vdef (stmt);
4565 80666 : gsi_remove (gsi, true);
4566 80666 : release_defs (stmt);
4567 80666 : return SRA_AM_REMOVED;
4568 : }
4569 : else
4570 : {
4571 65696 : init_subtree_with_zero (acc, gsi, true, loc);
4572 65696 : return SRA_AM_MODIFIED;
4573 : }
4574 : }
4575 :
4576 : /* Create and return a new suitable default definition SSA_NAME for RACC which
4577 : is an access describing an uninitialized part of an aggregate that is being
4578 : loaded. REG_TREE is used instead of the actual RACC type if that is not of
4579 : a gimple register type. */
4580 :
4581 : static tree
4582 544 : get_repl_default_def_ssa_name (struct access *racc, tree reg_type)
4583 : {
4584 544 : gcc_checking_assert (!racc->grp_to_be_replaced
4585 : && !racc->grp_to_be_debug_replaced);
4586 544 : if (!racc->replacement_decl)
4587 544 : racc->replacement_decl = create_access_replacement (racc, reg_type);
4588 544 : return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
4589 : }
4590 :
4591 :
4592 : /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4593 : of accesses within a subtree ACCESS; all its children, siblings and their
4594 : children are to be processed.
4595 : GSI is a statement iterator used to place the new statements. */
4596 : static void
4597 23469 : generate_subtree_deferred_init (struct access *access,
4598 : tree init_type,
4599 : tree decl_name,
4600 : gimple_stmt_iterator *gsi,
4601 : location_t loc)
4602 : {
4603 52646 : do
4604 : {
4605 52646 : if (access->grp_to_be_replaced)
4606 : {
4607 40764 : tree repl = get_access_replacement (access);
4608 40764 : gimple *call
4609 40764 : = gimple_build_call_internal (IFN_DEFERRED_INIT, 3,
4610 40764 : TYPE_SIZE_UNIT (TREE_TYPE (repl)),
4611 : init_type, decl_name);
4612 40764 : gimple_call_set_lhs (call, repl);
4613 40764 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
4614 40764 : update_stmt (call);
4615 40764 : gimple_set_location (call, loc);
4616 40764 : sra_stats.subtree_deferred_init++;
4617 : }
4618 52646 : if (access->first_child)
4619 3684 : generate_subtree_deferred_init (access->first_child, init_type,
4620 : decl_name, gsi, loc);
4621 :
4622 52646 : access = access ->next_sibling;
4623 : }
4624 52646 : while (access);
4625 23469 : }
4626 :
4627 : /* For a call to .DEFERRED_INIT:
4628 : var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4629 : examine the LHS variable VAR and replace it with a scalar replacement if
4630 : there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4631 : the corresponding scalar relacement variable. Examine the subtree and
4632 : do the scalar replacements in the subtree too. STMT is the call, GSI is
4633 : the statement iterator to place newly created statement. */
4634 :
4635 : static enum assignment_mod_result
4636 82477 : sra_modify_deferred_init (gimple *stmt, gimple_stmt_iterator *gsi)
4637 : {
4638 82477 : tree lhs = gimple_call_lhs (stmt);
4639 82477 : tree init_type = gimple_call_arg (stmt, 1);
4640 82477 : tree decl_name = gimple_call_arg (stmt, 2);
4641 :
4642 82477 : struct access *lhs_access = get_access_for_expr (lhs);
4643 82477 : if (!lhs_access)
4644 : return SRA_AM_NONE;
4645 :
4646 29701 : location_t loc = gimple_location (stmt);
4647 :
4648 29701 : if (lhs_access->grp_to_be_replaced)
4649 : {
4650 9561 : tree lhs_repl = get_access_replacement (lhs_access);
4651 9561 : gimple_call_set_lhs (stmt, lhs_repl);
4652 9561 : tree arg0_repl = TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl));
4653 9561 : gimple_call_set_arg (stmt, 0, arg0_repl);
4654 9561 : sra_stats.deferred_init++;
4655 9561 : gcc_assert (!lhs_access->first_child);
4656 : return SRA_AM_MODIFIED;
4657 : }
4658 :
4659 20140 : if (lhs_access->first_child)
4660 19785 : generate_subtree_deferred_init (lhs_access->first_child,
4661 : init_type, decl_name, gsi, loc);
4662 20140 : if (lhs_access->grp_covered)
4663 : {
4664 12248 : unlink_stmt_vdef (stmt);
4665 12248 : gsi_remove (gsi, true);
4666 12248 : release_defs (stmt);
4667 12248 : return SRA_AM_REMOVED;
4668 : }
4669 :
4670 : return SRA_AM_MODIFIED;
4671 : }
4672 :
4673 : /* Examine both sides of the assignment statement pointed to by STMT, replace
4674 : them with a scalare replacement if there is one and generate copying of
4675 : replacements if scalarized aggregates have been used in the assignment. GSI
4676 : is used to hold generated statements for type conversions and subtree
4677 : copying. */
4678 :
4679 : static enum assignment_mod_result
4680 25113847 : sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4681 : {
4682 25113847 : struct access *lacc, *racc;
4683 25113847 : tree lhs, rhs;
4684 25113847 : bool modify_this_stmt = false;
4685 25113847 : bool force_gimple_rhs = false;
4686 25113847 : location_t loc;
4687 25113847 : gimple_stmt_iterator orig_gsi = *gsi;
4688 :
4689 25113847 : if (!gimple_assign_single_p (stmt))
4690 : return SRA_AM_NONE;
4691 19681457 : lhs = gimple_assign_lhs (stmt);
4692 19681457 : rhs = gimple_assign_rhs1 (stmt);
4693 :
4694 19681457 : if (TREE_CODE (rhs) == CONSTRUCTOR)
4695 2809438 : return sra_modify_constructor_assign (stmt, gsi);
4696 :
4697 16863148 : if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
4698 16859952 : || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
4699 16847188 : || (TREE_CODE (rhs) == BIT_FIELD_REF && !sra_handled_bf_read_p (rhs))
4700 33719203 : || TREE_CODE (lhs) == BIT_FIELD_REF)
4701 : {
4702 25417 : modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
4703 : false, gsi, gsi);
4704 25417 : modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
4705 : true, gsi, gsi);
4706 47478 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4707 : }
4708 :
4709 16846602 : lacc = get_access_for_expr (lhs);
4710 16846602 : racc = get_access_for_expr (rhs);
4711 16846602 : if (!lacc && !racc)
4712 : return SRA_AM_NONE;
4713 : /* Avoid modifying initializations of constant-pool replacements. */
4714 6914897 : if (racc && (racc->replacement_decl == lhs))
4715 : return SRA_AM_NONE;
4716 :
4717 6909916 : loc = gimple_location (stmt);
4718 6909916 : if (lacc && lacc->grp_to_be_replaced)
4719 : {
4720 1876680 : lhs = get_access_replacement (lacc);
4721 1876680 : gimple_assign_set_lhs (stmt, lhs);
4722 1876680 : modify_this_stmt = true;
4723 1876680 : if (lacc->grp_partial_lhs)
4724 85 : force_gimple_rhs = true;
4725 1876680 : sra_stats.exprs++;
4726 : }
4727 :
4728 6909916 : if (racc && racc->grp_to_be_replaced)
4729 : {
4730 3154669 : rhs = get_access_replacement (racc);
4731 3154669 : modify_this_stmt = true;
4732 3154669 : if (racc->grp_partial_lhs)
4733 557 : force_gimple_rhs = true;
4734 3154669 : sra_stats.exprs++;
4735 : }
4736 1086629 : else if (racc
4737 1086629 : && !racc->grp_unscalarized_data
4738 864812 : && !racc->grp_unscalarizable_region
4739 864810 : && TREE_CODE (lhs) == SSA_NAME
4740 544 : && !access_has_replacements_p (racc))
4741 : {
4742 544 : rhs = get_repl_default_def_ssa_name (racc, TREE_TYPE (lhs));
4743 544 : modify_this_stmt = true;
4744 544 : sra_stats.exprs++;
4745 : }
4746 :
4747 3155213 : if (modify_this_stmt
4748 6909916 : && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4749 : {
4750 : /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4751 : ??? This should move to fold_stmt which we simply should
4752 : call after building a VIEW_CONVERT_EXPR here. */
4753 533166 : if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
4754 149204 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs)) == racc->reverse
4755 416292 : && !contains_bitfld_component_ref_p (lhs))
4756 : {
4757 149203 : lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
4758 149203 : gimple_assign_set_lhs (stmt, lhs);
4759 : }
4760 117886 : else if (lacc
4761 90172 : && AGGREGATE_TYPE_P (TREE_TYPE (rhs))
4762 64307 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs)) == lacc->reverse
4763 182193 : && !contains_vce_or_bfcref_p (rhs))
4764 63836 : rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
4765 :
4766 267089 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4767 : {
4768 54050 : rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
4769 54050 : if (is_gimple_reg_type (TREE_TYPE (lhs))
4770 54050 : && TREE_CODE (lhs) != SSA_NAME)
4771 6909916 : force_gimple_rhs = true;
4772 : }
4773 : }
4774 :
4775 6909916 : if (lacc && lacc->grp_to_be_debug_replaced)
4776 : {
4777 142177 : tree dlhs = get_access_replacement (lacc);
4778 142177 : tree drhs = unshare_expr (rhs);
4779 142177 : if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
4780 : {
4781 3412 : if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
4782 1767 : && !contains_vce_or_bfcref_p (drhs))
4783 61 : drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
4784 1706 : if (drhs
4785 3412 : && !useless_type_conversion_p (TREE_TYPE (dlhs),
4786 1706 : TREE_TYPE (drhs)))
4787 1645 : drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
4788 1645 : TREE_TYPE (dlhs), drhs);
4789 : }
4790 142177 : gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
4791 142177 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4792 : }
4793 :
4794 : /* From this point on, the function deals with assignments in between
4795 : aggregates when at least one has scalar reductions of some of its
4796 : components. There are three possible scenarios: Both the LHS and RHS have
4797 : to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4798 :
4799 : In the first case, we would like to load the LHS components from RHS
4800 : components whenever possible. If that is not possible, we would like to
4801 : read it directly from the RHS (after updating it by storing in it its own
4802 : components). If there are some necessary unscalarized data in the LHS,
4803 : those will be loaded by the original assignment too. If neither of these
4804 : cases happen, the original statement can be removed. Most of this is done
4805 : by load_assign_lhs_subreplacements.
4806 :
4807 : In the second case, we would like to store all RHS scalarized components
4808 : directly into LHS and if they cover the aggregate completely, remove the
4809 : statement too. In the third case, we want the LHS components to be loaded
4810 : directly from the RHS (DSE will remove the original statement if it
4811 : becomes redundant).
4812 :
4813 : This is a bit complex but manageable when types match and when unions do
4814 : not cause confusion in a way that we cannot really load a component of LHS
4815 : from the RHS or vice versa (the access representing this level can have
4816 : subaccesses that are accessible only through a different union field at a
4817 : higher level - different from the one used in the examined expression).
4818 : Unions are fun.
4819 :
4820 : Therefore, I specially handle a fourth case, happening when there is a
4821 : specific type cast or it is impossible to locate a scalarized subaccess on
4822 : the other side of the expression. If that happens, I simply "refresh" the
4823 : RHS by storing in it is scalarized components leave the original statement
4824 : there to do the copying and then load the scalar replacements of the LHS.
4825 : This is what the first branch does. */
4826 :
4827 6909916 : if (modify_this_stmt
4828 2002233 : || gimple_has_volatile_ops (stmt)
4829 2001853 : || contains_vce_or_bfcref_p (rhs)
4830 1821373 : || contains_vce_or_bfcref_p (lhs)
4831 8728117 : || stmt_ends_bb_p (stmt))
4832 : {
4833 : /* No need to copy into a constant, it comes pre-initialized. */
4834 5185135 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4835 17482 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4836 : gsi, false, false, loc);
4837 5167653 : if (access_has_children_p (lacc))
4838 : {
4839 252200 : gimple_stmt_iterator alt_gsi = gsi_none ();
4840 252200 : if (stmt_ends_bb_p (stmt))
4841 : {
4842 75071 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
4843 75071 : gsi = &alt_gsi;
4844 : }
4845 252200 : generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
4846 : gsi, true, true, loc);
4847 : }
4848 5167653 : sra_stats.separate_lhs_rhs_handling++;
4849 :
4850 : /* This gimplification must be done after generate_subtree_copies,
4851 : lest we insert the subtree copies in the middle of the gimplified
4852 : sequence. */
4853 5167653 : if (force_gimple_rhs)
4854 26961 : rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
4855 : true, GSI_SAME_STMT);
4856 5167653 : if (gimple_assign_rhs1 (stmt) != rhs)
4857 : {
4858 3245279 : modify_this_stmt = true;
4859 3245279 : gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
4860 3245279 : gcc_assert (stmt == gsi_stmt (orig_gsi));
4861 : }
4862 :
4863 6830057 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4864 : }
4865 : else
4866 : {
4867 2435381 : if (access_has_children_p (lacc)
4868 1742274 : && access_has_children_p (racc)
4869 : /* When an access represents an unscalarizable region, it usually
4870 : represents accesses with variable offset and thus must not be used
4871 : to generate new memory accesses. */
4872 454859 : && !lacc->grp_unscalarizable_region
4873 454854 : && !racc->grp_unscalarizable_region)
4874 : {
4875 454848 : struct subreplacement_assignment_data sad;
4876 :
4877 454848 : sad.left_offset = lacc->offset;
4878 454848 : sad.assignment_lhs = lhs;
4879 454848 : sad.assignment_rhs = rhs;
4880 454848 : sad.top_racc = racc;
4881 454848 : sad.old_gsi = *gsi;
4882 454848 : sad.new_gsi = gsi;
4883 454848 : sad.loc = gimple_location (stmt);
4884 454848 : sad.refreshed = SRA_UDH_NONE;
4885 :
4886 454848 : if (lacc->grp_read && !lacc->grp_covered)
4887 94645 : handle_unscalarized_data_in_subtree (&sad);
4888 :
4889 454848 : load_assign_lhs_subreplacements (lacc, &sad);
4890 454848 : if (sad.refreshed != SRA_UDH_RIGHT)
4891 : {
4892 429614 : gsi_next (gsi);
4893 429614 : unlink_stmt_vdef (stmt);
4894 429614 : gsi_remove (&sad.old_gsi, true);
4895 429614 : release_defs (stmt);
4896 429614 : sra_stats.deleted++;
4897 429614 : return SRA_AM_REMOVED;
4898 : }
4899 : }
4900 : else
4901 : {
4902 1287415 : if (access_has_children_p (racc)
4903 482359 : && !racc->grp_unscalarized_data
4904 421348 : && TREE_CODE (lhs) != SSA_NAME)
4905 : {
4906 421347 : if (dump_file)
4907 : {
4908 5 : fprintf (dump_file, "Removing load: ");
4909 5 : print_gimple_stmt (dump_file, stmt, 0);
4910 : }
4911 421347 : generate_subtree_copies (racc->first_child, lhs,
4912 : racc->offset, 0, 0, gsi,
4913 : false, false, loc);
4914 421347 : gcc_assert (stmt == gsi_stmt (*gsi));
4915 421347 : unlink_stmt_vdef (stmt);
4916 421347 : gsi_remove (gsi, true);
4917 421347 : release_defs (stmt);
4918 421347 : sra_stats.deleted++;
4919 421347 : return SRA_AM_REMOVED;
4920 : }
4921 : /* Restore the aggregate RHS from its components so the
4922 : prevailing aggregate copy does the right thing. */
4923 927080 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4924 60997 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4925 : gsi, false, false, loc);
4926 : /* Re-load the components of the aggregate copy destination.
4927 : But use the RHS aggregate to load from to expose more
4928 : optimization opportunities. */
4929 866068 : if (access_has_children_p (lacc))
4930 : {
4931 238265 : generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
4932 : 0, 0, gsi, true, true, loc);
4933 238265 : if (lacc->grp_covered)
4934 : {
4935 175393 : unlink_stmt_vdef (stmt);
4936 175393 : gsi_remove (& orig_gsi, true);
4937 175393 : release_defs (stmt);
4938 175393 : sra_stats.deleted++;
4939 175393 : return SRA_AM_REMOVED;
4940 : }
4941 : }
4942 : }
4943 :
4944 715909 : return SRA_AM_NONE;
4945 : }
4946 : }
4947 :
4948 : /* Set any scalar replacements of values in the constant pool to the initial
4949 : value of the constant. (Constant-pool decls like *.LC0 have effectively
4950 : been initialized before the program starts, we must do the same for their
4951 : replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4952 : the function's entry block. */
4953 :
4954 : static void
4955 420484 : initialize_constant_pool_replacements (void)
4956 : {
4957 420484 : gimple_seq seq = NULL;
4958 420484 : gimple_stmt_iterator gsi = gsi_start (seq);
4959 420484 : bitmap_iterator bi;
4960 420484 : unsigned i;
4961 :
4962 2172227 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
4963 : {
4964 1751743 : tree var = candidate (i);
4965 1751743 : if (!constant_decl_p (var))
4966 1751662 : continue;
4967 :
4968 81 : struct access *access = get_first_repr_for_decl (var);
4969 :
4970 6386 : while (access)
4971 : {
4972 6224 : if (access->replacement_decl)
4973 : {
4974 4981 : gassign *stmt
4975 4981 : = gimple_build_assign (get_access_replacement (access),
4976 : unshare_expr (access->expr));
4977 4981 : if (dump_file && (dump_flags & TDF_DETAILS))
4978 : {
4979 0 : fprintf (dump_file, "Generating constant initializer: ");
4980 0 : print_gimple_stmt (dump_file, stmt, 0);
4981 0 : fprintf (dump_file, "\n");
4982 : }
4983 4981 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
4984 4981 : update_stmt (stmt);
4985 : }
4986 :
4987 6224 : if (access->first_child)
4988 : access = access->first_child;
4989 4981 : else if (access->next_sibling)
4990 : access = access->next_sibling;
4991 : else
4992 : {
4993 2351 : while (access->parent && !access->next_sibling)
4994 : access = access->parent;
4995 1108 : if (access->next_sibling)
4996 : access = access->next_sibling;
4997 : else
4998 81 : access = access->next_grp;
4999 : }
5000 : }
5001 : }
5002 :
5003 420484 : seq = gsi_seq (gsi);
5004 420484 : if (seq)
5005 76 : gsi_insert_seq_on_edge_immediate (
5006 76 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5007 420484 : }
5008 :
5009 : /* Traverse the function body and all modifications as decided in
5010 : analyze_all_variable_accesses. Return true iff the CFG has been
5011 : changed. */
5012 :
5013 : static bool
5014 420484 : sra_modify_function_body (void)
5015 : {
5016 420484 : bool cfg_changed = false;
5017 420484 : basic_block bb;
5018 :
5019 420484 : initialize_constant_pool_replacements ();
5020 :
5021 9731958 : FOR_EACH_BB_FN (bb, cfun)
5022 : {
5023 9311474 : gimple_stmt_iterator gsi = gsi_start_bb (bb);
5024 79291178 : while (!gsi_end_p (gsi))
5025 : {
5026 69979704 : gimple *stmt = gsi_stmt (gsi);
5027 69979704 : enum assignment_mod_result assign_result;
5028 69979704 : bool modified = false, deleted = false;
5029 69979704 : tree *t;
5030 69979704 : unsigned i;
5031 :
5032 69979704 : switch (gimple_code (stmt))
5033 : {
5034 418780 : case GIMPLE_RETURN:
5035 418780 : t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
5036 418780 : if (*t != NULL_TREE)
5037 272940 : modified |= sra_modify_expr (t, false, &gsi, &gsi);
5038 : break;
5039 :
5040 25113847 : case GIMPLE_ASSIGN:
5041 25113847 : assign_result = sra_modify_assign (stmt, &gsi);
5042 25113847 : modified |= assign_result == SRA_AM_MODIFIED;
5043 25113847 : deleted = assign_result == SRA_AM_REMOVED;
5044 25113847 : break;
5045 :
5046 4206809 : case GIMPLE_CALL:
5047 : /* Handle calls to .DEFERRED_INIT specially. */
5048 4206809 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
5049 : {
5050 82477 : assign_result = sra_modify_deferred_init (stmt, &gsi);
5051 82477 : modified |= assign_result == SRA_AM_MODIFIED;
5052 82477 : deleted = assign_result == SRA_AM_REMOVED;
5053 : }
5054 : else
5055 : {
5056 4124332 : gcall *call = as_a <gcall *> (stmt);
5057 4124332 : gimple_stmt_iterator call_gsi = gsi;
5058 :
5059 : /* Operands must be processed before the lhs. */
5060 12285279 : for (i = 0; i < gimple_call_num_args (call); i++)
5061 : {
5062 8160947 : int flags = gimple_call_arg_flags (call, i);
5063 8160947 : t = gimple_call_arg_ptr (call, i);
5064 8160947 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi, flags);
5065 : }
5066 4124332 : if (gimple_call_chain (call))
5067 : {
5068 29294 : t = gimple_call_chain_ptr (call);
5069 29294 : int flags = gimple_call_static_chain_flags (call);
5070 29294 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi,
5071 : flags);
5072 : }
5073 4124332 : if (gimple_call_lhs (call))
5074 : {
5075 1715229 : t = gimple_call_lhs_ptr (call);
5076 1715229 : modified |= sra_modify_expr (t, true, &call_gsi, &gsi);
5077 : }
5078 : }
5079 : break;
5080 :
5081 7211 : case GIMPLE_ASM:
5082 7211 : {
5083 7211 : gimple_stmt_iterator stmt_gsi = gsi;
5084 7211 : gasm *asm_stmt = as_a <gasm *> (stmt);
5085 18001 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5086 : {
5087 3579 : t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5088 3579 : modified |= sra_modify_expr (t, false, &stmt_gsi, &gsi);
5089 : }
5090 11082 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5091 : {
5092 3871 : t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5093 3871 : modified |= sra_modify_expr (t, true, &stmt_gsi, &gsi);
5094 : }
5095 : }
5096 7211 : break;
5097 :
5098 : default:
5099 : break;
5100 : }
5101 :
5102 29600807 : if (modified)
5103 : {
5104 5446977 : update_stmt (stmt);
5105 5446977 : if (maybe_clean_eh_stmt (stmt)
5106 5446977 : && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5107 : cfg_changed = true;
5108 : }
5109 69979704 : if (!deleted)
5110 68110016 : gsi_next (&gsi);
5111 : }
5112 : }
5113 :
5114 420484 : gsi_commit_edge_inserts ();
5115 420484 : return cfg_changed;
5116 : }
5117 :
5118 : /* Generate statements initializing scalar replacements of parts of function
5119 : parameters. */
5120 :
5121 : static void
5122 420484 : initialize_parameter_reductions (void)
5123 : {
5124 420484 : gimple_stmt_iterator gsi;
5125 420484 : gimple_seq seq = NULL;
5126 420484 : tree parm;
5127 :
5128 420484 : gsi = gsi_start (seq);
5129 420484 : for (parm = DECL_ARGUMENTS (current_function_decl);
5130 1253944 : parm;
5131 833460 : parm = DECL_CHAIN (parm))
5132 : {
5133 833460 : vec<access_p> *access_vec;
5134 833460 : struct access *access;
5135 :
5136 833460 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
5137 766884 : continue;
5138 66576 : access_vec = get_base_access_vector (parm);
5139 66576 : if (!access_vec)
5140 0 : continue;
5141 :
5142 66576 : for (access = (*access_vec)[0];
5143 170332 : access;
5144 103756 : access = access->next_grp)
5145 103756 : generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
5146 103756 : EXPR_LOCATION (parm));
5147 : }
5148 :
5149 420484 : seq = gsi_seq (gsi);
5150 420484 : if (seq)
5151 52622 : gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5152 420484 : }
5153 :
5154 : /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
5155 : it reveals there are components of some aggregates to be scalarized, it runs
5156 : the required transformations. */
5157 : static unsigned int
5158 3474809 : perform_intra_sra (void)
5159 : {
5160 3474809 : int ret = 0;
5161 3474809 : sra_initialize ();
5162 :
5163 3474809 : if (!find_var_candidates ())
5164 2717717 : goto out;
5165 :
5166 757092 : if (!scan_function ())
5167 49552 : goto out;
5168 :
5169 707540 : if (!analyze_all_variable_accesses ())
5170 287056 : goto out;
5171 :
5172 420484 : if (sra_modify_function_body ())
5173 : ret = TODO_update_ssa | TODO_cleanup_cfg;
5174 : else
5175 420462 : ret = TODO_update_ssa;
5176 420484 : initialize_parameter_reductions ();
5177 :
5178 420484 : statistics_counter_event (cfun, "Scalar replacements created",
5179 : sra_stats.replacements);
5180 420484 : statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
5181 420484 : statistics_counter_event (cfun, "Subtree copy stmts",
5182 : sra_stats.subtree_copies);
5183 420484 : statistics_counter_event (cfun, "Subreplacement stmts",
5184 : sra_stats.subreplacements);
5185 420484 : statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
5186 420484 : statistics_counter_event (cfun, "Separate LHS and RHS handling",
5187 : sra_stats.separate_lhs_rhs_handling);
5188 :
5189 3474809 : out:
5190 3474809 : sra_deinitialize ();
5191 3474809 : return ret;
5192 : }
5193 :
5194 : /* Perform early intraprocedural SRA. */
5195 : static unsigned int
5196 2431882 : early_intra_sra (void)
5197 : {
5198 2431882 : sra_mode = SRA_MODE_EARLY_INTRA;
5199 0 : return perform_intra_sra ();
5200 : }
5201 :
5202 : /* Perform "late" intraprocedural SRA. */
5203 : static unsigned int
5204 1042927 : late_intra_sra (void)
5205 : {
5206 1042927 : sra_mode = SRA_MODE_INTRA;
5207 0 : return perform_intra_sra ();
5208 : }
5209 :
5210 :
5211 : static bool
5212 3479004 : gate_intra_sra (void)
5213 : {
5214 3479004 : return flag_tree_sra != 0 && dbg_cnt (tree_sra);
5215 : }
5216 :
5217 :
5218 : namespace {
5219 :
5220 : const pass_data pass_data_sra_early =
5221 : {
5222 : GIMPLE_PASS, /* type */
5223 : "esra", /* name */
5224 : OPTGROUP_NONE, /* optinfo_flags */
5225 : TV_TREE_SRA, /* tv_id */
5226 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5227 : 0, /* properties_provided */
5228 : 0, /* properties_destroyed */
5229 : 0, /* todo_flags_start */
5230 : TODO_update_ssa, /* todo_flags_finish */
5231 : };
5232 :
5233 : class pass_sra_early : public gimple_opt_pass
5234 : {
5235 : public:
5236 288775 : pass_sra_early (gcc::context *ctxt)
5237 577550 : : gimple_opt_pass (pass_data_sra_early, ctxt)
5238 : {}
5239 :
5240 : /* opt_pass methods: */
5241 2435642 : bool gate (function *) final override { return gate_intra_sra (); }
5242 2431882 : unsigned int execute (function *) final override
5243 : {
5244 2431882 : return early_intra_sra ();
5245 : }
5246 :
5247 : }; // class pass_sra_early
5248 :
5249 : } // anon namespace
5250 :
5251 : gimple_opt_pass *
5252 288775 : make_pass_sra_early (gcc::context *ctxt)
5253 : {
5254 288775 : return new pass_sra_early (ctxt);
5255 : }
5256 :
5257 : namespace {
5258 :
5259 : const pass_data pass_data_sra =
5260 : {
5261 : GIMPLE_PASS, /* type */
5262 : "sra", /* name */
5263 : OPTGROUP_NONE, /* optinfo_flags */
5264 : TV_TREE_SRA, /* tv_id */
5265 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5266 : 0, /* properties_provided */
5267 : 0, /* properties_destroyed */
5268 : TODO_update_address_taken, /* todo_flags_start */
5269 : TODO_update_ssa, /* todo_flags_finish */
5270 : };
5271 :
5272 : class pass_sra : public gimple_opt_pass
5273 : {
5274 : public:
5275 288775 : pass_sra (gcc::context *ctxt)
5276 577550 : : gimple_opt_pass (pass_data_sra, ctxt)
5277 : {}
5278 :
5279 : /* opt_pass methods: */
5280 1043362 : bool gate (function *) final override { return gate_intra_sra (); }
5281 1042927 : unsigned int execute (function *) final override { return late_intra_sra (); }
5282 :
5283 : }; // class pass_sra
5284 :
5285 : } // anon namespace
5286 :
5287 : gimple_opt_pass *
5288 288775 : make_pass_sra (gcc::context *ctxt)
5289 : {
5290 288775 : return new pass_sra (ctxt);
5291 : }
5292 :
5293 :
5294 : /* If type T cannot be totally scalarized, return false. Otherwise return true
5295 : and push to the vector within PC offsets and lengths of all padding in the
5296 : type as total scalarization would encounter it. */
5297 :
5298 : static bool
5299 67767 : check_ts_and_push_padding_to_vec (tree type, sra_padding_collecting *pc)
5300 : {
5301 67767 : if (!totally_scalarizable_type_p (type, true /* optimistic value */,
5302 : 0, pc))
5303 : return false;
5304 :
5305 59814 : pc->record_padding (tree_to_shwi (TYPE_SIZE (type)));
5306 59814 : return true;
5307 : }
5308 :
5309 : /* Given two types in an assignment, return true either if any one cannot be
5310 : totally scalarized or if they have padding (i.e. not copied bits) */
5311 :
5312 : bool
5313 37860 : sra_total_scalarization_would_copy_same_data_p (tree t1, tree t2)
5314 : {
5315 37860 : sra_padding_collecting p1;
5316 37860 : if (!check_ts_and_push_padding_to_vec (t1, &p1))
5317 : return true;
5318 :
5319 29907 : sra_padding_collecting p2;
5320 29907 : if (!check_ts_and_push_padding_to_vec (t2, &p2))
5321 : return true;
5322 :
5323 29907 : unsigned l = p1.m_padding.length ();
5324 59814 : if (l != p2.m_padding.length ())
5325 : return false;
5326 36688 : for (unsigned i = 0; i < l; i++)
5327 6784 : if (p1.m_padding[i].first != p2.m_padding[i].first
5328 6784 : || p1.m_padding[i].second != p2.m_padding[i].second)
5329 : return false;
5330 :
5331 : return true;
5332 29907 : }
5333 :
|
