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 across 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 82145930 : uid_decl_hasher::hash (const tree_node *item)
307 : {
308 82145930 : return item->decl_minimal.uid;
309 : }
310 :
311 : /* Return true if the DECL_UID in both trees are equal. */
312 :
313 : inline bool
314 94622469 : uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
315 : {
316 94622469 : 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 15147354 : candidate (unsigned uid)
327 : {
328 15147354 : tree_node t;
329 15147354 : t.decl_minimal.uid = uid;
330 15147354 : 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 : /* Number 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 16547707 : access_has_children_p (struct access *acc)
474 : {
475 8828883 : 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 558 : access_has_replacements_p (struct access *acc)
482 : {
483 558 : struct access *child;
484 558 : if (acc->grp_to_be_replaced)
485 : return true;
486 564 : 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 24391884 : 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 10699369 : find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
506 : HOST_WIDE_INT size)
507 : {
508 16530775 : while (access && (access->offset != offset || access->size != size))
509 : {
510 5831406 : struct access *child = access->first_child;
511 :
512 12602215 : while (child && (child->offset + child->size <= offset))
513 6770809 : child = child->next_sibling;
514 5831406 : 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 10699369 : if (access)
521 10750075 : while (access->first_child
522 3216592 : && access->first_child->offset == offset
523 13875683 : && access->first_child->size == size)
524 : access = access->first_child;
525 :
526 10699369 : return access;
527 : }
528 :
529 : /* Return the first group representative for DECL or NULL if none exists. */
530 :
531 : static struct access *
532 20063885 : get_first_repr_for_decl (tree base)
533 : {
534 20063885 : vec<access_p> *access_vec;
535 :
536 20063885 : access_vec = get_base_access_vector (base);
537 20063885 : if (!access_vec)
538 : return NULL;
539 :
540 20063885 : 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 9621073 : get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
549 : HOST_WIDE_INT size)
550 : {
551 9621073 : struct access *access;
552 :
553 9621073 : access = get_first_repr_for_decl (base);
554 22189467 : while (access && (access->offset + access->size <= offset))
555 2947321 : access = access->next_grp;
556 9621073 : if (!access)
557 : return NULL;
558 :
559 9621073 : 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 1364681 : add_link_to_rhs (struct access *racc, struct assign_link *link)
566 : {
567 1364681 : gcc_assert (link->racc == racc);
568 :
569 1364681 : if (!racc->first_rhs_link)
570 : {
571 1364681 : gcc_assert (!racc->last_rhs_link);
572 1364681 : racc->first_rhs_link = link;
573 : }
574 : else
575 0 : racc->last_rhs_link->next_rhs = link;
576 :
577 1364681 : racc->last_rhs_link = link;
578 1364681 : link->next_rhs = NULL;
579 1364681 : }
580 :
581 : /* Add LINK to the linked list of lhs assign links of LACC. */
582 :
583 : static void
584 1364681 : add_link_to_lhs (struct access *lacc, struct assign_link *link)
585 : {
586 1364681 : gcc_assert (link->lacc == lacc);
587 :
588 1364681 : if (!lacc->first_lhs_link)
589 : {
590 1364681 : gcc_assert (!lacc->last_lhs_link);
591 1364681 : lacc->first_lhs_link = link;
592 : }
593 : else
594 0 : lacc->last_lhs_link->next_lhs = link;
595 :
596 1364681 : lacc->last_lhs_link = link;
597 1364681 : link->next_lhs = NULL;
598 1364681 : }
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 5458557 : relink_to_new_repr (struct access *new_acc, struct access *old_acc)
604 : {
605 5458557 : if (old_acc->first_rhs_link)
606 : {
607 :
608 900392 : if (new_acc->first_rhs_link)
609 : {
610 285940 : gcc_assert (!new_acc->last_rhs_link->next_rhs);
611 285940 : gcc_assert (!old_acc->last_rhs_link
612 : || !old_acc->last_rhs_link->next_rhs);
613 :
614 285940 : new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link;
615 285940 : new_acc->last_rhs_link = old_acc->last_rhs_link;
616 : }
617 : else
618 : {
619 614452 : gcc_assert (!new_acc->last_rhs_link);
620 :
621 614452 : new_acc->first_rhs_link = old_acc->first_rhs_link;
622 614452 : new_acc->last_rhs_link = old_acc->last_rhs_link;
623 : }
624 900392 : old_acc->first_rhs_link = old_acc->last_rhs_link = NULL;
625 : }
626 : else
627 4558165 : gcc_assert (!old_acc->last_rhs_link);
628 :
629 5458557 : if (old_acc->first_lhs_link)
630 : {
631 :
632 365836 : if (new_acc->first_lhs_link)
633 : {
634 151550 : gcc_assert (!new_acc->last_lhs_link->next_lhs);
635 151550 : gcc_assert (!old_acc->last_lhs_link
636 : || !old_acc->last_lhs_link->next_lhs);
637 :
638 151550 : new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link;
639 151550 : new_acc->last_lhs_link = old_acc->last_lhs_link;
640 : }
641 : else
642 : {
643 214286 : gcc_assert (!new_acc->last_lhs_link);
644 :
645 214286 : new_acc->first_lhs_link = old_acc->first_lhs_link;
646 214286 : new_acc->last_lhs_link = old_acc->last_lhs_link;
647 : }
648 365836 : old_acc->first_lhs_link = old_acc->last_lhs_link = NULL;
649 : }
650 : else
651 5092721 : gcc_assert (!old_acc->last_lhs_link);
652 :
653 5458557 : }
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 4785888 : add_access_to_rhs_work_queue (struct access *access)
660 : {
661 4785888 : if (access->first_rhs_link && !access->grp_rhs_queued)
662 : {
663 1576308 : gcc_assert (!access->next_rhs_queued);
664 1576308 : access->next_rhs_queued = rhs_work_queue_head;
665 1576308 : access->grp_rhs_queued = 1;
666 1576308 : rhs_work_queue_head = access;
667 : }
668 4785888 : }
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 1711252 : add_access_to_lhs_work_queue (struct access *access)
675 : {
676 1711252 : if (access->first_lhs_link && !access->grp_lhs_queued)
677 : {
678 1366369 : gcc_assert (!access->next_lhs_queued);
679 1366369 : access->next_lhs_queued = lhs_work_queue_head;
680 1366369 : access->grp_lhs_queued = 1;
681 1366369 : lhs_work_queue_head = access;
682 : }
683 1711252 : }
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 1576308 : pop_access_from_rhs_work_queue (void)
690 : {
691 1576308 : struct access *access = rhs_work_queue_head;
692 :
693 1576308 : rhs_work_queue_head = access->next_rhs_queued;
694 1576308 : access->next_rhs_queued = NULL;
695 1576308 : access->grp_rhs_queued = 0;
696 1576308 : 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 1366369 : pop_access_from_lhs_work_queue (void)
704 : {
705 1366369 : struct access *access = lhs_work_queue_head;
706 :
707 1366369 : lhs_work_queue_head = access->next_lhs_queued;
708 1366369 : access->next_lhs_queued = NULL;
709 1366369 : access->grp_lhs_queued = 0;
710 1366369 : return access;
711 : }
712 :
713 : /* Allocate necessary structures. */
714 :
715 : static void
716 3603288 : sra_initialize (void)
717 : {
718 3603288 : candidate_bitmap = BITMAP_ALLOC (NULL);
719 7206576 : candidates = new hash_table<uid_decl_hasher>
720 6711531 : (vec_safe_length (cfun->local_decls) / 2);
721 3603288 : should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
722 3603288 : cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
723 3603288 : disqualified_constants = BITMAP_ALLOC (NULL);
724 3603288 : passed_by_ref_in_call = BITMAP_ALLOC (NULL);
725 3603288 : gcc_obstack_init (&name_obstack);
726 3603288 : base_access_vec = new hash_map<tree, auto_vec<access_p> >;
727 3603288 : memset (&sra_stats, 0, sizeof (sra_stats));
728 3603288 : }
729 :
730 : /* Deallocate all general structures. */
731 :
732 : static void
733 3603288 : sra_deinitialize (void)
734 : {
735 3603288 : BITMAP_FREE (candidate_bitmap);
736 3603288 : delete candidates;
737 3603288 : candidates = NULL;
738 3603288 : BITMAP_FREE (should_scalarize_away_bitmap);
739 3603288 : BITMAP_FREE (cannot_scalarize_away_bitmap);
740 3603288 : BITMAP_FREE (disqualified_constants);
741 3603288 : BITMAP_FREE (passed_by_ref_in_call);
742 3603288 : access_pool.release ();
743 3603288 : assign_link_pool.release ();
744 3603288 : obstack_free (&name_obstack, NULL);
745 :
746 7206576 : delete base_access_vec;
747 3603288 : }
748 :
749 : /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
750 :
751 43636593 : static bool constant_decl_p (tree decl)
752 : {
753 37732407 : 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 4577284 : disqualify_candidate (tree decl, const char *reason)
761 : {
762 4577284 : if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
763 2447058 : candidates->remove_elt_with_hash (decl, DECL_UID (decl));
764 4577284 : if (constant_decl_p (decl))
765 4155 : bitmap_set_bit (disqualified_constants, DECL_UID (decl));
766 :
767 4577284 : 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 4577284 : }
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 8705823 : type_internals_preclude_sra_p_1 (tree type, const char **msg,
781 : hash_set<tree> *visited_types)
782 : {
783 8705823 : tree fld;
784 8705823 : tree et;
785 :
786 8705823 : if (visited_types->contains (type))
787 : return false;
788 8386980 : visited_types->add (type);
789 :
790 8386980 : switch (TREE_CODE (type))
791 : {
792 7695484 : case RECORD_TYPE:
793 7695484 : case UNION_TYPE:
794 7695484 : case QUAL_UNION_TYPE:
795 159879743 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
796 152194714 : if (TREE_CODE (fld) == FIELD_DECL)
797 : {
798 17242450 : if (TREE_CODE (fld) == FUNCTION_DECL)
799 : continue;
800 17242450 : tree ft = TREE_TYPE (fld);
801 :
802 17242450 : if (TREE_THIS_VOLATILE (fld))
803 : {
804 903 : *msg = "volatile structure field";
805 903 : return true;
806 : }
807 17241547 : if (!DECL_FIELD_OFFSET (fld))
808 : {
809 0 : *msg = "no structure field offset";
810 0 : return true;
811 : }
812 17241547 : if (!DECL_SIZE (fld))
813 : {
814 8443 : *msg = "zero structure field size";
815 8443 : return true;
816 : }
817 17233104 : if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
818 : {
819 0 : *msg = "structure field offset not fixed";
820 0 : return true;
821 : }
822 17233104 : if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
823 : {
824 0 : *msg = "structure field size not fixed";
825 0 : return true;
826 : }
827 17233104 : if (!tree_fits_shwi_p (bit_position (fld)))
828 : {
829 0 : *msg = "structure field size too big";
830 0 : return true;
831 : }
832 17233104 : if (AGGREGATE_TYPE_P (ft)
833 17233104 : && int_bit_position (fld) % BITS_PER_UNIT != 0)
834 : {
835 0 : *msg = "structure field is bit field";
836 0 : return true;
837 : }
838 :
839 17233104 : if (AGGREGATE_TYPE_P (ft)
840 17233104 : && type_internals_preclude_sra_p_1 (ft, msg, visited_types))
841 : return true;
842 : }
843 :
844 : return false;
845 :
846 566399 : case ARRAY_TYPE:
847 566399 : et = TREE_TYPE (type);
848 :
849 566399 : if (TYPE_VOLATILE (et))
850 : {
851 0 : *msg = "element type is volatile";
852 0 : return true;
853 : }
854 :
855 566399 : if (AGGREGATE_TYPE_P (et)
856 566399 : && 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 5026128 : type_internals_preclude_sra_p (tree type, const char **msg)
871 : {
872 5026128 : hash_set<tree> visited_types;
873 5026128 : return type_internals_preclude_sra_p_1 (type, msg, &visited_types);
874 5026128 : }
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 15249644 : create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
883 : {
884 15249644 : struct access *access = access_pool.allocate ();
885 :
886 15249644 : memset (access, 0, sizeof (struct access));
887 15249644 : access->base = base;
888 15249644 : access->offset = offset;
889 15249644 : access->size = size;
890 :
891 15249644 : base_access_vec->get_or_insert (base).safe_push (access);
892 :
893 15249644 : 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 29364792 : create_access (tree expr, gimple *stmt, bool write)
904 : {
905 29364792 : struct access *access;
906 29364792 : poly_int64 poffset, psize, pmax_size;
907 29364792 : tree base = expr;
908 29364792 : bool reverse, unscalarizable_region = false;
909 :
910 29364792 : 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 29364792 : if (constant_decl_p (base)
915 3846 : && !bitmap_bit_p (disqualified_constants, DECL_UID (base)))
916 : {
917 3846 : if (expr != base
918 349 : && !is_gimple_reg_type (TREE_TYPE (expr))
919 3932 : && 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 3846 : maybe_add_sra_candidate (base);
929 : }
930 :
931 29364792 : if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
932 : return NULL;
933 :
934 15260947 : if (write && TREE_READONLY (base))
935 : {
936 10654 : disqualify_candidate (base, "Encountered a store to a read-only decl.");
937 10654 : return NULL;
938 : }
939 :
940 15250293 : HOST_WIDE_INT offset, size, max_size;
941 15250293 : if (!poffset.is_constant (&offset)
942 15250293 : || !psize.is_constant (&size)
943 15250293 : || !pmax_size.is_constant (&max_size))
944 : {
945 : disqualify_candidate (base, "Encountered a polynomial-sized access.");
946 : return NULL;
947 : }
948 :
949 15250293 : if (size != max_size)
950 : {
951 378769 : size = max_size;
952 378769 : unscalarizable_region = true;
953 : }
954 15250293 : if (size == 0)
955 : return NULL;
956 15250291 : if (offset < 0)
957 : {
958 34 : disqualify_candidate (base, "Encountered a negative offset access.");
959 34 : return NULL;
960 : }
961 15250257 : if (size < 0)
962 : {
963 24 : disqualify_candidate (base, "Encountered an unconstrained access.");
964 24 : return NULL;
965 : }
966 15250233 : if (offset + size > tree_to_shwi (DECL_SIZE (base)))
967 : {
968 587 : disqualify_candidate (base, "Encountered an access beyond the base.");
969 587 : return NULL;
970 : }
971 15249646 : if (BITINT_TYPE_P (TREE_TYPE (expr)) && size > WIDE_INT_MAX_PRECISION - 1)
972 : {
973 2 : disqualify_candidate (base, "Encountered too large _BitInt access.");
974 2 : return NULL;
975 : }
976 :
977 15249644 : access = create_access_1 (base, offset, size);
978 15249644 : access->expr = expr;
979 15249644 : access->type = TREE_TYPE (expr);
980 15249644 : access->write = write;
981 15249644 : access->grp_unscalarizable_region = unscalarizable_region;
982 15249644 : access->grp_same_access_path = true;
983 15249644 : access->stmt = stmt;
984 15249644 : access->reverse = reverse;
985 :
986 15249644 : return access;
987 : }
988 :
989 : /* Given an array type TYPE, extract element size to *EL_SIZE, minimum index to
990 : *IDX and maximum index to *MAX so that the caller can iterate over all
991 : elements and return true, except if the array is known to be zero-length,
992 : then return false. */
993 :
994 : static bool
995 18220 : prepare_iteration_over_array_elts (tree type, HOST_WIDE_INT *el_size,
996 : offset_int *idx, offset_int *max)
997 : {
998 18220 : tree elem_size = TYPE_SIZE (TREE_TYPE (type));
999 18220 : gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
1000 18220 : *el_size = tree_to_shwi (elem_size);
1001 18220 : gcc_assert (*el_size > 0);
1002 :
1003 18220 : tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1004 18220 : gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1005 18220 : tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1006 : /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1007 18220 : if (!maxidx)
1008 : return false;
1009 18220 : gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1010 18220 : tree domain = TYPE_DOMAIN (type);
1011 : /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1012 : DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1013 18220 : *idx = wi::to_offset (minidx);
1014 18220 : *max = wi::to_offset (maxidx);
1015 18220 : if (!TYPE_UNSIGNED (domain))
1016 : {
1017 18220 : *idx = wi::sext (*idx, TYPE_PRECISION (domain));
1018 18220 : *max = wi::sext (*max, TYPE_PRECISION (domain));
1019 : }
1020 : return true;
1021 : }
1022 :
1023 : /* A structure to track collecting padding and hold collected padding
1024 : information. */
1025 :
1026 26348 : class sra_padding_collecting
1027 : {
1028 : public:
1029 : /* Given that there won't be any data until at least OFFSET, add an
1030 : appropriate entry to the list of paddings or extend the last one. */
1031 : void record_padding (HOST_WIDE_INT offset);
1032 : /* Vector of pairs describing contiguous pieces of padding, each pair
1033 : consisting of offset and length. */
1034 : auto_vec<std::pair<HOST_WIDE_INT, HOST_WIDE_INT>, 10> m_padding;
1035 : /* Offset where data should continue after the last seen actual bit of data
1036 : if there was no padding. */
1037 : HOST_WIDE_INT m_data_until = 0;
1038 : };
1039 :
1040 : /* Given that there won't be any data until at least OFFSET, add an appropriate
1041 : entry to the list of paddings or extend the last one. */
1042 :
1043 73730 : void sra_padding_collecting::record_padding (HOST_WIDE_INT offset)
1044 : {
1045 73730 : if (offset > m_data_until)
1046 : {
1047 5590 : HOST_WIDE_INT psz = offset - m_data_until;
1048 5590 : if (!m_padding.is_empty ()
1049 278 : && ((m_padding[m_padding.length () - 1].first
1050 278 : + m_padding[m_padding.length () - 1].second) == offset))
1051 0 : m_padding[m_padding.length () - 1].second += psz;
1052 : else
1053 5590 : m_padding.safe_push (std::make_pair (m_data_until, psz));
1054 : }
1055 73730 : }
1056 :
1057 : /* Return true iff TYPE is totally scalarizable - i.e. a RECORD_TYPE or
1058 : fixed-length ARRAY_TYPE with fields that are either of gimple register types
1059 : (excluding bit-fields) or (recursively) scalarizable types. CONST_DECL must
1060 : be true if we are considering a decl from constant pool. If it is false,
1061 : char arrays will be refused.
1062 :
1063 : TOTAL_OFFSET is the offset of TYPE within any outer type that is being
1064 : examined.
1065 :
1066 : If PC is non-NULL, collect padding information into the vector within the
1067 : structure. The information is however only complete if the function returns
1068 : true and does not contain any padding at its end. */
1069 :
1070 : static bool
1071 2763414 : totally_scalarizable_type_p (tree type, bool const_decl,
1072 : HOST_WIDE_INT total_offset,
1073 : sra_padding_collecting *pc)
1074 : {
1075 2763414 : if (is_gimple_reg_type (type))
1076 : {
1077 1802939 : if (pc)
1078 : {
1079 45846 : pc->record_padding (total_offset);
1080 45846 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1081 : }
1082 : return true;
1083 : }
1084 960475 : if (type_contains_placeholder_p (type))
1085 : return false;
1086 :
1087 960475 : bool have_predecessor_field = false;
1088 960475 : HOST_WIDE_INT prev_pos = 0;
1089 :
1090 960475 : switch (TREE_CODE (type))
1091 : {
1092 925931 : case RECORD_TYPE:
1093 13760603 : for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1094 12856477 : if (TREE_CODE (fld) == FIELD_DECL)
1095 : {
1096 1991883 : tree ft = TREE_TYPE (fld);
1097 :
1098 1991883 : if (!DECL_SIZE (fld))
1099 : return false;
1100 1991883 : if (zerop (DECL_SIZE (fld)))
1101 51172 : continue;
1102 :
1103 1940711 : HOST_WIDE_INT pos = int_bit_position (fld);
1104 1940711 : if (have_predecessor_field
1105 1940711 : && pos <= prev_pos)
1106 : return false;
1107 :
1108 1940711 : have_predecessor_field = true;
1109 1940711 : prev_pos = pos;
1110 :
1111 1940711 : if (DECL_BIT_FIELD (fld))
1112 : return false;
1113 :
1114 1939057 : if (!totally_scalarizable_type_p (ft, const_decl, total_offset + pos,
1115 : pc))
1116 : return false;
1117 : }
1118 :
1119 : return true;
1120 :
1121 25036 : case ARRAY_TYPE:
1122 25036 : {
1123 25036 : HOST_WIDE_INT min_elem_size;
1124 25036 : if (const_decl)
1125 : min_elem_size = 0;
1126 : else
1127 22393 : min_elem_size = BITS_PER_UNIT;
1128 :
1129 25036 : if (TYPE_DOMAIN (type) == NULL_TREE
1130 25036 : || !tree_fits_shwi_p (TYPE_SIZE (type))
1131 25036 : || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1132 25036 : || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1133 44477 : || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1134 : return false;
1135 19441 : if (tree_to_shwi (TYPE_SIZE (type)) == 0
1136 19441 : && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1137 : /* Zero-element array, should not prevent scalarization. */
1138 : ;
1139 19441 : else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1140 19441 : || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1141 : /* Variable-length array, do not allow scalarization. */
1142 : return false;
1143 :
1144 19405 : unsigned old_padding_len = 0;
1145 19405 : if (pc)
1146 2482 : old_padding_len = pc->m_padding.length ();
1147 19405 : tree elem = TREE_TYPE (type);
1148 19405 : if (!totally_scalarizable_type_p (elem, const_decl, total_offset, pc))
1149 : return false;
1150 19266 : if (pc)
1151 : {
1152 2482 : unsigned new_padding_len = pc->m_padding.length ();
1153 2482 : HOST_WIDE_INT el_size;
1154 2482 : offset_int idx, max;
1155 2482 : if (!prepare_iteration_over_array_elts (type, &el_size, &idx, &max))
1156 0 : return true;
1157 2482 : pc->record_padding (total_offset + el_size);
1158 2482 : ++idx;
1159 2482 : for (HOST_WIDE_INT pos = total_offset + el_size;
1160 115410 : idx <= max;
1161 112928 : pos += el_size, ++idx)
1162 : {
1163 112955 : for (unsigned i = old_padding_len; i < new_padding_len; i++)
1164 : {
1165 27 : HOST_WIDE_INT pp
1166 27 : = pos + pc->m_padding[i].first - total_offset;
1167 27 : HOST_WIDE_INT psz = pc->m_padding[i].second;
1168 27 : pc->m_padding.safe_push (std::make_pair (pp, psz));
1169 : }
1170 : }
1171 2482 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1172 : }
1173 : return true;
1174 : }
1175 : default:
1176 : return false;
1177 : }
1178 : }
1179 :
1180 : /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1181 :
1182 : static inline bool
1183 60587119 : contains_view_convert_expr_p (const_tree ref)
1184 : {
1185 83363449 : while (handled_component_p (ref))
1186 : {
1187 22787668 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1188 : return true;
1189 22776330 : ref = TREE_OPERAND (ref, 0);
1190 : }
1191 :
1192 : return false;
1193 : }
1194 :
1195 : /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1196 : bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1197 : it points to will be set if REF contains any of the above or a MEM_REF
1198 : expression that effectively performs type conversion. */
1199 :
1200 : static bool
1201 7851633 : contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1202 : {
1203 10114894 : while (handled_component_p (ref))
1204 : {
1205 2648334 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1206 2648334 : || (TREE_CODE (ref) == COMPONENT_REF
1207 1926703 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1208 : {
1209 385073 : if (type_changing_p)
1210 200555 : *type_changing_p = true;
1211 : return true;
1212 : }
1213 2263261 : ref = TREE_OPERAND (ref, 0);
1214 : }
1215 :
1216 7466560 : if (!type_changing_p
1217 3646476 : || TREE_CODE (ref) != MEM_REF
1218 7596504 : || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1219 : return false;
1220 :
1221 129944 : tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1222 129944 : if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1223 129944 : != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1224 100121 : *type_changing_p = true;
1225 :
1226 : return false;
1227 : }
1228 :
1229 : /* Search the given tree for a declaration by skipping handled components and
1230 : exclude it from the candidates. */
1231 :
1232 : static void
1233 1060292 : disqualify_base_of_expr (tree t, const char *reason)
1234 : {
1235 1060292 : t = get_base_address (t);
1236 1060292 : if (t && DECL_P (t))
1237 849241 : disqualify_candidate (t, reason);
1238 1060292 : }
1239 :
1240 : /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1241 :
1242 : static bool
1243 238466 : sra_handled_bf_read_p (tree expr)
1244 : {
1245 238466 : uint64_t size, offset;
1246 238466 : if (bit_field_size (expr).is_constant (&size)
1247 238466 : && bit_field_offset (expr).is_constant (&offset)
1248 238466 : && size % BITS_PER_UNIT == 0
1249 238466 : && offset % BITS_PER_UNIT == 0
1250 238534 : && pow2p_hwi (size))
1251 238374 : return true;
1252 : return false;
1253 : }
1254 :
1255 : /* Scan expression EXPR and create access structures for all accesses to
1256 : candidates for scalarization. Return the created access or NULL if none is
1257 : created. */
1258 :
1259 : static struct access *
1260 62672774 : build_access_from_expr_1 (tree expr, gimple *stmt, bool write)
1261 : {
1262 : /* We only allow ADDR_EXPRs in arguments of function calls and those must
1263 : have been dealt with in build_access_from_call_arg. Any other address
1264 : taking should have been caught by scan_visit_addr. */
1265 62672774 : if (TREE_CODE (expr) == ADDR_EXPR)
1266 : {
1267 2085654 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1268 2085654 : gcc_assert (!DECL_P (base)
1269 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)));
1270 : return NULL;
1271 : }
1272 :
1273 60587120 : struct access *ret = NULL;
1274 60587120 : bool partial_ref;
1275 :
1276 60587120 : if ((TREE_CODE (expr) == BIT_FIELD_REF
1277 130274 : && (write || !sra_handled_bf_read_p (expr)))
1278 60585991 : || TREE_CODE (expr) == IMAGPART_EXPR
1279 121141589 : || TREE_CODE (expr) == REALPART_EXPR)
1280 : {
1281 63062 : expr = TREE_OPERAND (expr, 0);
1282 63062 : partial_ref = true;
1283 : }
1284 : else
1285 : partial_ref = false;
1286 :
1287 60587120 : if (storage_order_barrier_p (expr))
1288 : {
1289 1 : disqualify_base_of_expr (expr, "storage order barrier.");
1290 1 : return NULL;
1291 : }
1292 :
1293 : /* We are capable of handling the topmost V_C_E but not any of those
1294 : buried in other handled components. */
1295 60889114 : if (contains_view_convert_expr_p (TREE_CODE (expr) == VIEW_CONVERT_EXPR
1296 301995 : ? TREE_OPERAND (expr, 0) : expr))
1297 : {
1298 11338 : disqualify_base_of_expr (expr, "V_C_E under a different handled "
1299 : "component.");
1300 11338 : return NULL;
1301 : }
1302 :
1303 60575781 : if (TREE_THIS_VOLATILE (expr))
1304 : {
1305 22177 : disqualify_base_of_expr (expr, "part of a volatile reference.");
1306 22177 : return NULL;
1307 : }
1308 :
1309 60553604 : switch (TREE_CODE (expr))
1310 : {
1311 3673632 : case MEM_REF:
1312 3673632 : if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR)
1313 : return NULL;
1314 : /* fall through */
1315 29364792 : case VAR_DECL:
1316 29364792 : case PARM_DECL:
1317 29364792 : case RESULT_DECL:
1318 29364792 : case COMPONENT_REF:
1319 29364792 : case ARRAY_REF:
1320 29364792 : case ARRAY_RANGE_REF:
1321 29364792 : case BIT_FIELD_REF:
1322 29364792 : case VIEW_CONVERT_EXPR:
1323 29364792 : ret = create_access (expr, stmt, write);
1324 29364792 : break;
1325 :
1326 : default:
1327 : break;
1328 : }
1329 :
1330 58717754 : if (write && partial_ref && ret)
1331 5289 : ret->grp_partial_lhs = 1;
1332 :
1333 : return ret;
1334 : }
1335 :
1336 : /* Scan expression EXPR and create access structures for all accesses to
1337 : candidates for scalarization. Return true if any access has been inserted.
1338 : STMT must be the statement from which the expression is taken, WRITE must be
1339 : true if the expression is a store and false otherwise. */
1340 :
1341 : static bool
1342 17601310 : build_access_from_expr (tree expr, gimple *stmt, bool write)
1343 : {
1344 17601310 : struct access *access;
1345 :
1346 17601310 : access = build_access_from_expr_1 (expr, stmt, write);
1347 17601310 : if (access)
1348 : {
1349 : /* This means the aggregate is accesses as a whole in a way other than an
1350 : assign statement and thus cannot be removed even if we had a scalar
1351 : replacement for everything. */
1352 2657005 : if (cannot_scalarize_away_bitmap)
1353 2657005 : bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1354 : return true;
1355 : }
1356 : return false;
1357 : }
1358 :
1359 : enum out_edge_check { SRA_OUTGOING_EDGES_UNCHECKED, SRA_OUTGOING_EDGES_OK,
1360 : SRA_OUTGOING_EDGES_FAIL };
1361 :
1362 : /* Return true if STMT terminates BB and there is an abnormal edge going out of
1363 : the BB and remember the decision in OE_CHECK. */
1364 :
1365 : static bool
1366 3244212 : abnormal_edge_after_stmt_p (gimple *stmt, enum out_edge_check *oe_check)
1367 : {
1368 3244212 : if (*oe_check == SRA_OUTGOING_EDGES_OK)
1369 : return false;
1370 1888561 : if (*oe_check == SRA_OUTGOING_EDGES_FAIL)
1371 : return true;
1372 1888335 : if (stmt_ends_bb_p (stmt))
1373 : {
1374 766369 : edge e;
1375 766369 : edge_iterator ei;
1376 1998841 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1377 1232958 : if (e->flags & EDGE_ABNORMAL)
1378 : {
1379 486 : *oe_check = SRA_OUTGOING_EDGES_FAIL;
1380 486 : return true;
1381 : }
1382 : }
1383 1887849 : *oe_check = SRA_OUTGOING_EDGES_OK;
1384 1887849 : return false;
1385 : }
1386 :
1387 : /* Scan expression EXPR which is an argument of a call and create access
1388 : structures for all accesses to candidates for scalarization. Return true
1389 : if any access has been inserted. STMT must be the statement from which the
1390 : expression is taken. CAN_BE_RETURNED must be true if call argument flags
1391 : do not rule out that the argument is directly returned. OE_CHECK is used
1392 : to remember result of a test for abnormal outgoing edges after this
1393 : statement. */
1394 :
1395 : static bool
1396 12458038 : build_access_from_call_arg (tree expr, gimple *stmt, bool can_be_returned,
1397 : enum out_edge_check *oe_check)
1398 : {
1399 12458038 : if (gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
1400 : {
1401 57 : tree base = expr;
1402 57 : if (TREE_CODE (expr) == ADDR_EXPR)
1403 10 : base = get_base_address (TREE_OPERAND (expr, 0));
1404 57 : disqualify_base_of_expr (base, "Passed to a returns_twice call.");
1405 57 : return false;
1406 : }
1407 :
1408 12457981 : if (TREE_CODE (expr) == ADDR_EXPR)
1409 : {
1410 4269626 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1411 :
1412 4269626 : if (can_be_returned)
1413 : {
1414 1025414 : disqualify_base_of_expr (base, "Address possibly returned, "
1415 : "leading to an alias SRA may not know.");
1416 1025414 : return false;
1417 : }
1418 3244212 : if (abnormal_edge_after_stmt_p (stmt, oe_check))
1419 : {
1420 712 : disqualify_base_of_expr (base, "May lead to need to add statements "
1421 : "to abnormal edge.");
1422 712 : return false;
1423 : }
1424 :
1425 3243500 : bool read = build_access_from_expr (base, stmt, false);
1426 3243500 : bool write = build_access_from_expr (base, stmt, true);
1427 3243500 : if (read || write)
1428 : {
1429 309743 : if (dump_file && (dump_flags & TDF_DETAILS))
1430 : {
1431 0 : fprintf (dump_file, "Allowed ADDR_EXPR of ");
1432 0 : print_generic_expr (dump_file, base);
1433 0 : fprintf (dump_file, " because of ");
1434 0 : print_gimple_stmt (dump_file, stmt, 0);
1435 0 : fprintf (dump_file, "\n");
1436 : }
1437 309743 : bitmap_set_bit (passed_by_ref_in_call, DECL_UID (base));
1438 309743 : return true;
1439 : }
1440 : else
1441 : return false;
1442 : }
1443 :
1444 8188355 : return build_access_from_expr (expr, stmt, false);
1445 : }
1446 :
1447 :
1448 : /* Return the single non-EH successor edge of BB or NULL if there is none or
1449 : more than one. */
1450 :
1451 : static edge
1452 1511103 : single_non_eh_succ (basic_block bb)
1453 : {
1454 1511103 : edge e, res = NULL;
1455 1511103 : edge_iterator ei;
1456 :
1457 4531840 : FOR_EACH_EDGE (e, ei, bb->succs)
1458 3021157 : if (!(e->flags & EDGE_EH))
1459 : {
1460 1511406 : if (res)
1461 : return NULL;
1462 : res = e;
1463 : }
1464 :
1465 : return res;
1466 : }
1467 :
1468 : /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1469 : there is no alternative spot where to put statements SRA might need to
1470 : generate after it. The spot we are looking for is an edge leading to a
1471 : single non-EH successor, if it exists and is indeed single. RHS may be
1472 : NULL, in that case ignore it. */
1473 :
1474 : static bool
1475 25017423 : disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1476 : {
1477 25017423 : if (stmt_ends_bb_p (stmt))
1478 : {
1479 1390289 : if (single_non_eh_succ (gimple_bb (stmt)))
1480 : return false;
1481 :
1482 537 : disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1483 537 : if (rhs)
1484 0 : disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1485 : return true;
1486 : }
1487 : return false;
1488 : }
1489 :
1490 : /* Return true if the nature of BASE is such that it contains data even if
1491 : there is no write to it in the function. */
1492 :
1493 : static bool
1494 4204579 : comes_initialized_p (tree base)
1495 : {
1496 0 : return TREE_CODE (base) == PARM_DECL || constant_decl_p (base);
1497 : }
1498 :
1499 : /* Scan expressions occurring in STMT, create access structures for all accesses
1500 : to candidates for scalarization and remove those candidates which occur in
1501 : statements or expressions that prevent them from being split apart. Return
1502 : true if any access has been inserted. */
1503 :
1504 : static bool
1505 34392597 : build_accesses_from_assign (gimple *stmt)
1506 : {
1507 34392597 : tree lhs, rhs;
1508 34392597 : struct access *lacc, *racc;
1509 :
1510 34392597 : if (!gimple_assign_single_p (stmt)
1511 : /* Scope clobbers don't influence scalarization. */
1512 34392597 : || gimple_clobber_p (stmt))
1513 : return false;
1514 :
1515 22463027 : lhs = gimple_assign_lhs (stmt);
1516 22463027 : rhs = gimple_assign_rhs1 (stmt);
1517 :
1518 22463027 : if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1519 : return false;
1520 :
1521 22463027 : racc = build_access_from_expr_1 (rhs, stmt, false);
1522 22463027 : lacc = build_access_from_expr_1 (lhs, stmt, true);
1523 :
1524 22463027 : bool tbaa_hazard
1525 22463027 : = !types_equal_for_same_type_for_tbaa_p (TREE_TYPE (lhs), TREE_TYPE (rhs));
1526 :
1527 22463027 : if (lacc)
1528 : {
1529 6841828 : lacc->grp_assignment_write = 1;
1530 6841828 : if (storage_order_barrier_p (rhs))
1531 1 : lacc->grp_unscalarizable_region = 1;
1532 :
1533 6841828 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1534 : {
1535 1994606 : bool type_changing_p = false;
1536 1994606 : contains_vce_or_bfcref_p (lhs, &type_changing_p);
1537 1994606 : if (type_changing_p)
1538 151326 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1539 75663 : DECL_UID (lacc->base));
1540 : }
1541 6841828 : if (tbaa_hazard)
1542 875937 : lacc->grp_same_access_path = false;
1543 : }
1544 :
1545 22463027 : if (racc)
1546 : {
1547 5688126 : racc->grp_assignment_read = 1;
1548 5688126 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1549 : {
1550 1852425 : bool type_changing_p = false;
1551 1852425 : contains_vce_or_bfcref_p (rhs, &type_changing_p);
1552 :
1553 3479837 : if (type_changing_p || gimple_has_volatile_ops (stmt))
1554 450772 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1555 225386 : DECL_UID (racc->base));
1556 : else
1557 3254078 : bitmap_set_bit (should_scalarize_away_bitmap,
1558 1627039 : DECL_UID (racc->base));
1559 : }
1560 5688126 : if (storage_order_barrier_p (lhs))
1561 0 : racc->grp_unscalarizable_region = 1;
1562 5688126 : if (tbaa_hazard)
1563 71456 : racc->grp_same_access_path = false;
1564 : }
1565 :
1566 22463027 : if (lacc && racc
1567 1366290 : && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1568 1366290 : && !lacc->grp_unscalarizable_region
1569 1365705 : && !racc->grp_unscalarizable_region
1570 1364907 : && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1571 1364907 : && lacc->size == racc->size
1572 23827708 : && useless_type_conversion_p (lacc->type, racc->type))
1573 : {
1574 1364681 : struct assign_link *link;
1575 :
1576 1364681 : link = assign_link_pool.allocate ();
1577 1364681 : memset (link, 0, sizeof (struct assign_link));
1578 :
1579 1364681 : link->lacc = lacc;
1580 1364681 : link->racc = racc;
1581 1364681 : add_link_to_rhs (racc, link);
1582 1364681 : add_link_to_lhs (lacc, link);
1583 1364681 : add_access_to_rhs_work_queue (racc);
1584 1364681 : add_access_to_lhs_work_queue (lacc);
1585 :
1586 : /* Let's delay marking the areas as written until propagation of accesses
1587 : across link, unless the nature of rhs tells us that its data comes
1588 : from elsewhere. */
1589 1364681 : if (!comes_initialized_p (racc->base))
1590 1268075 : lacc->write = false;
1591 : }
1592 :
1593 22463027 : return lacc || racc;
1594 : }
1595 :
1596 : /* Callback of walk_stmt_load_store_addr_ops visit_addr used to detect taking
1597 : addresses of candidates a places which are not call arguments. Such
1598 : candidates are disqalified from SRA. This also applies to GIMPLE_ASM
1599 : operands with memory constrains which cannot be scalarized. */
1600 :
1601 : static bool
1602 2452850 : scan_visit_addr (gimple *, tree op, tree, void *)
1603 : {
1604 2452850 : op = get_base_address (op);
1605 2452850 : if (op
1606 2452850 : && DECL_P (op))
1607 1330786 : disqualify_candidate (op, "Address taken in a non-call-argument context.");
1608 :
1609 2452850 : return false;
1610 : }
1611 :
1612 : /* Scan function and look for interesting expressions and create access
1613 : structures for them. Return true iff any access is created. */
1614 :
1615 : static bool
1616 826864 : scan_function (void)
1617 : {
1618 826864 : basic_block bb;
1619 826864 : bool ret = false;
1620 :
1621 13917576 : FOR_EACH_BB_FN (bb, cfun)
1622 : {
1623 13090712 : gimple_stmt_iterator gsi;
1624 17791476 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1625 4700764 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), NULL, NULL, NULL,
1626 : scan_visit_addr);
1627 :
1628 131321944 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1629 : {
1630 105140520 : gimple *stmt = gsi_stmt (gsi);
1631 105140520 : tree t;
1632 105140520 : unsigned i;
1633 :
1634 105140520 : if (gimple_code (stmt) != GIMPLE_CALL)
1635 98916592 : walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1636 : scan_visit_addr);
1637 :
1638 105140520 : switch (gimple_code (stmt))
1639 : {
1640 819636 : case GIMPLE_RETURN:
1641 819636 : t = gimple_return_retval (as_a <greturn *> (stmt));
1642 819636 : if (t != NULL_TREE)
1643 485763 : ret |= build_access_from_expr (t, stmt, false);
1644 : break;
1645 :
1646 34392597 : case GIMPLE_ASSIGN:
1647 34392597 : ret |= build_accesses_from_assign (stmt);
1648 34392597 : break;
1649 :
1650 6223928 : case GIMPLE_CALL:
1651 6223928 : {
1652 6223928 : enum out_edge_check oe_check = SRA_OUTGOING_EDGES_UNCHECKED;
1653 6223928 : gcall *call = as_a <gcall *> (stmt);
1654 24865320 : for (i = 0; i < gimple_call_num_args (call); i++)
1655 : {
1656 12417464 : bool can_be_returned;
1657 12417464 : if (gimple_call_lhs (call))
1658 : {
1659 5045158 : int af = gimple_call_arg_flags (call, i);
1660 5045158 : can_be_returned = !(af & EAF_NOT_RETURNED_DIRECTLY);
1661 : }
1662 : else
1663 : can_be_returned = false;
1664 12417464 : ret |= build_access_from_call_arg (gimple_call_arg (call,
1665 : i),
1666 : stmt, can_be_returned,
1667 : &oe_check);
1668 : }
1669 6223928 : if (gimple_call_chain(stmt))
1670 40574 : ret |= build_access_from_call_arg (gimple_call_chain(call),
1671 : stmt, false, &oe_check);
1672 : }
1673 :
1674 6223928 : t = gimple_call_lhs (stmt);
1675 6223928 : if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
1676 : {
1677 : /* If the STMT is a call to DEFERRED_INIT, avoid setting
1678 : cannot_scalarize_away_bitmap. */
1679 2553859 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
1680 : {
1681 145410 : struct access *access
1682 145410 : = build_access_from_expr_1 (t, stmt, true);
1683 145410 : if (access)
1684 62685 : access->grp_assignment_write = 1;
1685 145410 : ret |= access != NULL;
1686 : }
1687 : else
1688 2408449 : ret |= build_access_from_expr (t, stmt, true);
1689 : }
1690 : break;
1691 :
1692 15441 : case GIMPLE_ASM:
1693 15441 : {
1694 15441 : gasm *asm_stmt = as_a <gasm *> (stmt);
1695 15441 : if (stmt_ends_bb_p (asm_stmt)
1696 15458 : && !single_succ_p (gimple_bb (asm_stmt)))
1697 : {
1698 38 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1699 : {
1700 21 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1701 21 : disqualify_base_of_expr (t, "OP of asm goto.");
1702 : }
1703 52 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1704 : {
1705 35 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1706 35 : disqualify_base_of_expr (t, "OP of asm goto.");
1707 : }
1708 : }
1709 : else
1710 : {
1711 31780 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1712 : {
1713 16356 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1714 16356 : ret |= build_access_from_expr (t, asm_stmt, false);
1715 : }
1716 30811 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1717 : {
1718 15387 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1719 15387 : ret |= build_access_from_expr (t, asm_stmt, true);
1720 : }
1721 : }
1722 : }
1723 : break;
1724 :
1725 : default:
1726 : break;
1727 : }
1728 : }
1729 : }
1730 :
1731 826864 : return ret;
1732 : }
1733 :
1734 : /* Helper of QSORT function. There are pointers to accesses in the array. An
1735 : access is considered smaller than another if it has smaller offset or if the
1736 : offsets are the same but is size is bigger. */
1737 :
1738 : static int
1739 132812769 : compare_access_positions (const void *a, const void *b)
1740 : {
1741 132812769 : const access_p *fp1 = (const access_p *) a;
1742 132812769 : const access_p *fp2 = (const access_p *) b;
1743 132812769 : const access_p f1 = *fp1;
1744 132812769 : const access_p f2 = *fp2;
1745 :
1746 132812769 : if (f1->offset != f2->offset)
1747 80923558 : return f1->offset < f2->offset ? -1 : 1;
1748 :
1749 51889211 : if (f1->size == f2->size)
1750 : {
1751 35810076 : if (f1->type == f2->type)
1752 : return 0;
1753 : /* Put any non-aggregate type before any aggregate type. */
1754 6026931 : else if (!is_gimple_reg_type (f1->type)
1755 6026931 : && is_gimple_reg_type (f2->type))
1756 : return 1;
1757 4561828 : else if (is_gimple_reg_type (f1->type)
1758 4561828 : && !is_gimple_reg_type (f2->type))
1759 : return -1;
1760 : /* Put any complex or vector type before any other scalar type. */
1761 2684002 : else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1762 2684002 : && TREE_CODE (f1->type) != VECTOR_TYPE
1763 2592046 : && (TREE_CODE (f2->type) == COMPLEX_TYPE
1764 2592046 : || VECTOR_TYPE_P (f2->type)))
1765 : return 1;
1766 2638641 : else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1767 : || VECTOR_TYPE_P (f1->type))
1768 91956 : && TREE_CODE (f2->type) != COMPLEX_TYPE
1769 89460 : && TREE_CODE (f2->type) != VECTOR_TYPE)
1770 : return -1;
1771 : /* Put any integral type before any non-integral type. When splicing, we
1772 : make sure that those with insufficient precision and occupying the
1773 : same space are not scalarized. */
1774 2573945 : else if (INTEGRAL_TYPE_P (f1->type)
1775 389197 : && !INTEGRAL_TYPE_P (f2->type))
1776 : return -1;
1777 2460083 : else if (!INTEGRAL_TYPE_P (f1->type)
1778 2184748 : && INTEGRAL_TYPE_P (f2->type))
1779 : return 1;
1780 : /* Put the integral type with the bigger precision first. */
1781 2348181 : else if (INTEGRAL_TYPE_P (f1->type)
1782 275335 : && INTEGRAL_TYPE_P (f2->type)
1783 2623516 : && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1784 37924 : return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1785 : /* Stabilize the sort. */
1786 2310257 : return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1787 : }
1788 :
1789 : /* We want the bigger accesses first, thus the opposite operator in the next
1790 : line: */
1791 16079135 : return f1->size > f2->size ? -1 : 1;
1792 : }
1793 :
1794 :
1795 : /* Append a name of the declaration to the name obstack. A helper function for
1796 : make_fancy_name. */
1797 :
1798 : static void
1799 2163230 : make_fancy_decl_name (tree decl)
1800 : {
1801 2163230 : char buffer[32];
1802 :
1803 2163230 : tree name = DECL_NAME (decl);
1804 2163230 : if (name)
1805 2093767 : obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1806 : IDENTIFIER_LENGTH (name));
1807 : else
1808 : {
1809 69463 : sprintf (buffer, "D%u", DECL_UID (decl));
1810 69463 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1811 : }
1812 2163230 : }
1813 :
1814 : /* Helper for make_fancy_name. */
1815 :
1816 : static void
1817 2464642 : make_fancy_name_1 (tree expr)
1818 : {
1819 2702377 : char buffer[32];
1820 2702377 : tree index;
1821 :
1822 2702377 : if (DECL_P (expr))
1823 : {
1824 1070496 : make_fancy_decl_name (expr);
1825 1070496 : return;
1826 : }
1827 :
1828 1631881 : switch (TREE_CODE (expr))
1829 : {
1830 1092734 : case COMPONENT_REF:
1831 1092734 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1832 1092734 : obstack_1grow (&name_obstack, '$');
1833 1092734 : make_fancy_decl_name (TREE_OPERAND (expr, 1));
1834 1092734 : break;
1835 :
1836 65419 : case ARRAY_REF:
1837 65419 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1838 65419 : obstack_1grow (&name_obstack, '$');
1839 : /* Arrays with only one element may not have a constant as their
1840 : index. */
1841 65419 : index = TREE_OPERAND (expr, 1);
1842 65419 : if (TREE_CODE (index) != INTEGER_CST)
1843 : break;
1844 65290 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1845 65290 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1846 65290 : break;
1847 :
1848 237735 : case BIT_FIELD_REF:
1849 237735 : case ADDR_EXPR:
1850 237735 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1851 237735 : break;
1852 :
1853 235705 : case MEM_REF:
1854 235705 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1855 235705 : if (!integer_zerop (TREE_OPERAND (expr, 1)))
1856 : {
1857 75956 : obstack_1grow (&name_obstack, '$');
1858 151912 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1859 75956 : TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1860 75956 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1861 : }
1862 : break;
1863 :
1864 0 : case REALPART_EXPR:
1865 0 : case IMAGPART_EXPR:
1866 0 : gcc_unreachable (); /* we treat these as scalars. */
1867 : break;
1868 : default:
1869 : break;
1870 : }
1871 : }
1872 :
1873 : /* Create a human readable name for replacement variable of ACCESS. */
1874 :
1875 : static char *
1876 1070784 : make_fancy_name (tree expr)
1877 : {
1878 1070784 : make_fancy_name_1 (expr);
1879 1070784 : obstack_1grow (&name_obstack, '\0');
1880 1070784 : return XOBFINISH (&name_obstack, char *);
1881 : }
1882 :
1883 : /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1884 : EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1885 : something for which get_addr_base_and_unit_offset returns NULL, gsi must
1886 : be non-NULL and is used to insert new statements either before or below
1887 : the current one as specified by INSERT_AFTER. This function is not capable
1888 : of handling bitfields. If FORCE_REF_ALL is true then the memory access
1889 : will use alias-set zero. */
1890 :
1891 : static tree
1892 2569767 : build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
1893 : bool reverse, tree exp_type, gimple_stmt_iterator *gsi,
1894 : bool insert_after, bool force_ref_all = false)
1895 : {
1896 2569767 : tree prev_base = base;
1897 2569767 : tree off;
1898 2569767 : tree mem_ref;
1899 2569767 : poly_int64 base_offset;
1900 2569767 : unsigned HOST_WIDE_INT misalign;
1901 2569767 : unsigned int align;
1902 :
1903 : /* Preserve address-space information. */
1904 2569767 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1905 2569767 : if (as != TYPE_ADDR_SPACE (exp_type))
1906 4 : exp_type = build_qualified_type (exp_type,
1907 2 : TYPE_QUALS (exp_type)
1908 2 : | ENCODE_QUAL_ADDR_SPACE (as));
1909 :
1910 2569767 : poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1911 2569767 : get_object_alignment_1 (base, &align, &misalign);
1912 2569767 : base = get_addr_base_and_unit_offset (base, &base_offset);
1913 :
1914 : /* get_addr_base_and_unit_offset returns NULL for references with a variable
1915 : offset such as array[var_index]. */
1916 2569767 : if (!base)
1917 : {
1918 35788 : gassign *stmt;
1919 35788 : tree tmp, addr;
1920 :
1921 35788 : gcc_checking_assert (gsi);
1922 35788 : tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1923 35788 : addr = build_fold_addr_expr (unshare_expr (prev_base));
1924 35788 : STRIP_USELESS_TYPE_CONVERSION (addr);
1925 35788 : stmt = gimple_build_assign (tmp, addr);
1926 35788 : gimple_set_location (stmt, loc);
1927 35788 : if (insert_after)
1928 10024 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1929 : else
1930 25764 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1931 :
1932 35788 : off = build_int_cst (force_ref_all ? ptr_type_node
1933 35788 : : reference_alias_ptr_type (prev_base), byte_offset);
1934 35788 : base = tmp;
1935 : }
1936 2533979 : else if (TREE_CODE (base) == MEM_REF)
1937 : {
1938 423268 : off = build_int_cst (force_ref_all ? ptr_type_node
1939 211634 : : TREE_TYPE (TREE_OPERAND (base, 1)),
1940 : base_offset + byte_offset);
1941 211634 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1942 211634 : base = unshare_expr (TREE_OPERAND (base, 0));
1943 : }
1944 : else
1945 : {
1946 4276167 : off = build_int_cst (force_ref_all ? ptr_type_node
1947 1953822 : : reference_alias_ptr_type (prev_base),
1948 : base_offset + byte_offset);
1949 2322345 : base = build_fold_addr_expr (unshare_expr (base));
1950 : }
1951 :
1952 2569767 : unsigned int align_bound = known_alignment (misalign + offset);
1953 2569767 : if (align_bound != 0)
1954 1677136 : align = MIN (align, align_bound);
1955 2569767 : if (align != TYPE_ALIGN (exp_type))
1956 524476 : exp_type = build_aligned_type (exp_type, align);
1957 :
1958 2569767 : mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1959 2569767 : REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1960 2569767 : if (TREE_THIS_VOLATILE (prev_base))
1961 6 : TREE_THIS_VOLATILE (mem_ref) = 1;
1962 2569767 : if (TREE_SIDE_EFFECTS (prev_base))
1963 126 : TREE_SIDE_EFFECTS (mem_ref) = 1;
1964 2569767 : return mem_ref;
1965 : }
1966 :
1967 : /* Construct and return a memory reference that is equal to a portion of
1968 : MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1969 :
1970 : static tree
1971 1691597 : build_reconstructed_reference (location_t, tree base, struct access *model)
1972 : {
1973 1691597 : tree expr = model->expr;
1974 : /* We have to make sure to start just below the outermost union. */
1975 1691597 : tree start_expr = expr;
1976 3482486 : while (handled_component_p (expr))
1977 : {
1978 1790889 : if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == UNION_TYPE)
1979 7794 : start_expr = expr;
1980 1790889 : expr = TREE_OPERAND (expr, 0);
1981 : }
1982 :
1983 : expr = start_expr;
1984 : tree prev_expr = NULL_TREE;
1985 3456937 : while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
1986 : {
1987 1848844 : if (!handled_component_p (expr))
1988 : return NULL_TREE;
1989 1765340 : prev_expr = expr;
1990 1765340 : expr = TREE_OPERAND (expr, 0);
1991 : }
1992 :
1993 : /* Guard against broken VIEW_CONVERT_EXPRs... */
1994 1608093 : if (!prev_expr)
1995 : return NULL_TREE;
1996 :
1997 1607117 : TREE_OPERAND (prev_expr, 0) = base;
1998 1607117 : tree ref = unshare_expr (model->expr);
1999 1607117 : TREE_OPERAND (prev_expr, 0) = expr;
2000 1607117 : return ref;
2001 : }
2002 :
2003 : /* Construct a memory reference to a part of an aggregate BASE at the given
2004 : OFFSET and of the same type as MODEL. In case this is a reference to a
2005 : bit-field, the function will replicate the last component_ref of model's
2006 : expr to access it. INSERT_AFTER and GSI have the same meaning as in
2007 : build_ref_for_offset, furthermore, when GSI is NULL, the function expects
2008 : that it re-builds the entire reference from a DECL to the final access and
2009 : so will create a MEM_REF when OFFSET does not exactly match offset of
2010 : MODEL. If FORCE_REF_ALL is true then the memory access will use
2011 : alias-set zero. */
2012 :
2013 : static tree
2014 4109298 : build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2015 : struct access *model, gimple_stmt_iterator *gsi,
2016 : bool insert_after, bool force_ref_all = false)
2017 : {
2018 4109298 : gcc_assert (offset >= 0);
2019 4109298 : if (TREE_CODE (model->expr) == COMPONENT_REF
2020 4109298 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2021 : {
2022 : /* This access represents a bit-field. */
2023 32426 : tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
2024 :
2025 32426 : offset -= int_bit_position (fld);
2026 32426 : exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
2027 32426 : t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type,
2028 : gsi, insert_after, force_ref_all);
2029 : /* The flag will be set on the record type. */
2030 32426 : REF_REVERSE_STORAGE_ORDER (t) = 0;
2031 32426 : return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
2032 32426 : NULL_TREE);
2033 : }
2034 : else
2035 : {
2036 4076872 : tree res;
2037 4076872 : if (model->grp_same_access_path
2038 1781930 : && !force_ref_all
2039 1691630 : && !TREE_THIS_VOLATILE (base)
2040 1691624 : && (TYPE_ADDR_SPACE (TREE_TYPE (base))
2041 1691624 : == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
2042 1691623 : && (offset == model->offset
2043 11431 : || (gsi && offset <= model->offset))
2044 : /* build_reconstructed_reference can still fail if we have already
2045 : massaged BASE because of another type incompatibility. */
2046 5768469 : && (res = build_reconstructed_reference (loc, base, model)))
2047 : return res;
2048 : else
2049 2469755 : return build_ref_for_offset (loc, base, offset, model->reverse,
2050 : model->type, gsi, insert_after,
2051 : force_ref_all);
2052 : }
2053 : }
2054 :
2055 : /* Attempt to build a memory reference that we could but into a gimple
2056 : debug_bind statement. Similar to build_ref_for_model but punts if it has to
2057 : create statements and return s NULL instead. This function also ignores
2058 : alignment issues and so its results should never end up in non-debug
2059 : statements. */
2060 :
2061 : static tree
2062 5982 : build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2063 : struct access *model)
2064 : {
2065 5982 : poly_int64 base_offset;
2066 5982 : tree off;
2067 :
2068 5982 : if (TREE_CODE (model->expr) == COMPONENT_REF
2069 5982 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2070 : return NULL_TREE;
2071 :
2072 5982 : base = get_addr_base_and_unit_offset (base, &base_offset);
2073 5982 : if (!base)
2074 : return NULL_TREE;
2075 5982 : if (TREE_CODE (base) == MEM_REF)
2076 : {
2077 188 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
2078 188 : base_offset + offset / BITS_PER_UNIT);
2079 188 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
2080 188 : base = unshare_expr (TREE_OPERAND (base, 0));
2081 : }
2082 : else
2083 : {
2084 5794 : off = build_int_cst (reference_alias_ptr_type (base),
2085 5794 : base_offset + offset / BITS_PER_UNIT);
2086 5794 : base = build_fold_addr_expr (unshare_expr (base));
2087 : }
2088 :
2089 5982 : return fold_build2_loc (loc, MEM_REF, model->type, base, off);
2090 : }
2091 :
2092 : /* Construct a memory reference consisting of component_refs and array_refs to
2093 : a part of an aggregate *RES which is of type TYPE. The requested part
2094 : should have type EXP_TYPE at the given OFFSET. CUR_SIZE must be the size of
2095 : *RES unless it is known that *RES alone cannot be the result. This function
2096 : might not succeed, it returns true when it does and only then *RES points to
2097 : something meaningful.
2098 :
2099 : This function should be used only to build expressions that we might need to
2100 : present to user (e.g. in warnings). In all other situations,
2101 : build_ref_for_model or build_ref_for_offset should be used instead. */
2102 :
2103 : static bool
2104 4012244 : build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
2105 : HOST_WIDE_INT cur_size, tree exp_type,
2106 : HOST_WIDE_INT exp_size)
2107 : {
2108 4075160 : while (1)
2109 : {
2110 4043702 : tree fld;
2111 4043702 : tree tr_size, index, minidx;
2112 4043702 : HOST_WIDE_INT el_size;
2113 :
2114 4043702 : if (offset == 0
2115 4043702 : && cur_size == exp_size
2116 4043702 : && types_compatible_p (exp_type, type))
2117 : return true;
2118 :
2119 2460182 : switch (TREE_CODE (type))
2120 : {
2121 2395374 : case UNION_TYPE:
2122 2395374 : case QUAL_UNION_TYPE:
2123 2395374 : case RECORD_TYPE:
2124 15123479 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
2125 : {
2126 15027326 : HOST_WIDE_INT pos, size;
2127 15027326 : tree tr_pos, expr, *expr_ptr;
2128 :
2129 15027326 : if (TREE_CODE (fld) != FIELD_DECL)
2130 12631933 : continue;
2131 :
2132 3954284 : tr_pos = bit_position (fld);
2133 3954284 : if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
2134 0 : continue;
2135 3954284 : pos = tree_to_uhwi (tr_pos);
2136 3954284 : gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
2137 3954284 : tr_size = DECL_SIZE (fld);
2138 3954284 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2139 0 : continue;
2140 3954284 : size = tree_to_uhwi (tr_size);
2141 3954284 : if (size == 0)
2142 : {
2143 81003 : if (pos != offset)
2144 33236 : continue;
2145 : }
2146 3873281 : else if (pos > offset || (pos + size) <= offset)
2147 1525655 : continue;
2148 :
2149 2395393 : expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
2150 : NULL_TREE);
2151 2395393 : expr_ptr = &expr;
2152 2395393 : if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
2153 : offset - pos, size,
2154 : exp_type, exp_size))
2155 : {
2156 2299221 : *res = expr;
2157 2299221 : return true;
2158 : }
2159 : }
2160 : return false;
2161 :
2162 31458 : case ARRAY_TYPE:
2163 31458 : tr_size = TYPE_SIZE (TREE_TYPE (type));
2164 31458 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2165 : return false;
2166 31458 : el_size = tree_to_uhwi (tr_size);
2167 :
2168 31458 : minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
2169 31458 : if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
2170 : return false;
2171 31458 : index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
2172 31458 : if (!integer_zerop (minidx))
2173 563 : index = int_const_binop (PLUS_EXPR, index, minidx);
2174 31458 : *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
2175 : NULL_TREE, NULL_TREE);
2176 31458 : offset = offset % el_size;
2177 31458 : cur_size = el_size;
2178 31458 : type = TREE_TYPE (type);
2179 31458 : break;
2180 :
2181 : default:
2182 : return false;
2183 : }
2184 31458 : }
2185 : }
2186 :
2187 : /* Print message to dump file why a variable was rejected. */
2188 :
2189 : static void
2190 15309091 : reject (tree var, const char *msg)
2191 : {
2192 15309091 : 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 15309091 : }
2199 :
2200 : /* Return true if VAR is a candidate for SRA. */
2201 :
2202 : static bool
2203 19694206 : maybe_add_sra_candidate (tree var)
2204 : {
2205 19694206 : tree type = TREE_TYPE (var);
2206 19694206 : const char *msg;
2207 19694206 : tree_node **slot;
2208 :
2209 19694206 : if (!AGGREGATE_TYPE_P (type))
2210 : {
2211 13716780 : reject (var, "not aggregate");
2212 13716780 : return false;
2213 : }
2214 :
2215 5977426 : 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 5752958 : || (TREE_ADDRESSABLE (var)
2219 1595678 : && pt_solution_includes (&cfun->gimple_df->escaped_return, var))
2220 4389302 : || (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 7341082 : && !constant_decl_p (var))
2225 : {
2226 1585504 : reject (var, "needs to live in memory and escapes or global");
2227 1585504 : return false;
2228 : }
2229 4391922 : if (TREE_THIS_VOLATILE (var))
2230 : {
2231 591 : reject (var, "is volatile");
2232 591 : return false;
2233 : }
2234 4391331 : if (!COMPLETE_TYPE_P (type))
2235 : {
2236 0 : reject (var, "has incomplete type");
2237 0 : return false;
2238 : }
2239 4391331 : if (!tree_fits_shwi_p (TYPE_SIZE (type)))
2240 : {
2241 43 : reject (var, "type size not fixed");
2242 43 : return false;
2243 : }
2244 4391288 : if (tree_to_shwi (TYPE_SIZE (type)) == 0)
2245 : {
2246 5917 : reject (var, "type size is zero");
2247 5917 : return false;
2248 : }
2249 4385371 : if (type_internals_preclude_sra_p (type, &msg))
2250 : {
2251 256 : reject (var, msg);
2252 256 : return false;
2253 : }
2254 4385115 : 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 4385115 : (sra_mode == SRA_MODE_EARLY_INTRA
2258 4385115 : && is_va_list_type (type)))
2259 : {
2260 0 : reject (var, "is va_list");
2261 0 : return false;
2262 : }
2263 :
2264 4385115 : bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2265 4385115 : slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2266 4385115 : *slot = var;
2267 :
2268 4385115 : 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 3603288 : find_var_candidates (void)
2283 : {
2284 3603288 : tree var, parm;
2285 3603288 : unsigned int i;
2286 3603288 : bool ret = false;
2287 :
2288 3603288 : for (parm = DECL_ARGUMENTS (current_function_decl);
2289 11128142 : parm;
2290 7524854 : parm = DECL_CHAIN (parm))
2291 7524854 : ret |= maybe_add_sra_candidate (parm);
2292 :
2293 18877037 : FOR_EACH_LOCAL_DECL (cfun, i, var)
2294 : {
2295 12165506 : if (!VAR_P (var))
2296 0 : continue;
2297 :
2298 12165506 : ret |= maybe_add_sra_candidate (var);
2299 : }
2300 :
2301 3603288 : 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 8778742 : path_comparable_for_same_access (tree expr)
2309 : {
2310 15100994 : while (handled_component_p (expr))
2311 : {
2312 6445308 : if (TREE_CODE (expr) == ARRAY_REF)
2313 : {
2314 : /* SSA name indices can occur here too when the array is of size 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 666663 : if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
2320 : return false;
2321 : }
2322 6322252 : expr = TREE_OPERAND (expr, 0);
2323 : }
2324 :
2325 8655686 : if (TREE_CODE (expr) == MEM_REF)
2326 : {
2327 1086921 : if (!zerop (TREE_OPERAND (expr, 1)))
2328 : return false;
2329 629170 : gcc_assert (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
2330 : && DECL_P (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)));
2331 629170 : if (TYPE_MAIN_VARIANT (TREE_TYPE (expr))
2332 629170 : != TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))))
2333 379665 : return false;
2334 : }
2335 : else
2336 7568765 : 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 4421718 : same_access_path_p (tree exp1, tree exp2)
2348 : {
2349 4421718 : 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 635144 : if (is_gimple_reg_type (TREE_TYPE (exp1))
2358 414067 : && TREE_CODE (exp1) == COMPONENT_REF
2359 1043915 : && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
2360 408771 : == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
2361 381965 : exp1 = TREE_OPERAND (exp1, 0);
2362 : else
2363 : return false;
2364 : }
2365 :
2366 4168539 : 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 5617393 : types_risk_mangled_binary_repr_p (tree t1, tree t2)
2378 : {
2379 5617393 : if (mode_can_transfer_bits (TYPE_MODE (t1)))
2380 : return false;
2381 :
2382 2820 : 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 4259842 : sort_and_splice_var_accesses (tree var)
2393 : {
2394 4259842 : int i, j, access_count;
2395 4259842 : struct access *res, **prev_acc_ptr = &res;
2396 4259842 : vec<access_p> *access_vec;
2397 4259842 : bool first = true;
2398 4259842 : HOST_WIDE_INT low = -1, high = 0;
2399 :
2400 4259842 : access_vec = get_base_access_vector (var);
2401 4259842 : if (!access_vec)
2402 : return NULL;
2403 4083422 : access_count = access_vec->length ();
2404 :
2405 : /* Sort by <OFFSET, SIZE>. */
2406 4083422 : access_vec->qsort (compare_access_positions);
2407 :
2408 4083422 : i = 0;
2409 13671449 : while (i < access_count)
2410 : {
2411 9593110 : struct access *access = (*access_vec)[i];
2412 9593110 : bool grp_write = access->write;
2413 9593110 : bool grp_read = !access->write;
2414 9593110 : bool grp_scalar_write = access->write
2415 9593110 : && is_gimple_reg_type (access->type);
2416 9593110 : bool grp_scalar_read = !access->write
2417 9593110 : && is_gimple_reg_type (access->type);
2418 9593110 : bool grp_assignment_read = access->grp_assignment_read;
2419 9593110 : bool grp_assignment_write = access->grp_assignment_write;
2420 9593110 : bool multiple_scalar_reads = false;
2421 9593110 : bool grp_partial_lhs = access->grp_partial_lhs;
2422 9593110 : bool first_scalar = is_gimple_reg_type (access->type);
2423 9593110 : bool unscalarizable_region = access->grp_unscalarizable_region;
2424 9593110 : bool grp_same_access_path = access->grp_same_access_path;
2425 9593110 : bool bf_non_full_precision
2426 9593110 : = (INTEGRAL_TYPE_P (access->type)
2427 3208538 : && TYPE_PRECISION (access->type) != access->size
2428 165587 : && TREE_CODE (access->expr) == COMPONENT_REF
2429 9668266 : && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2430 :
2431 9593110 : if (first || access->offset >= high)
2432 : {
2433 4515508 : first = false;
2434 4515508 : low = access->offset;
2435 4515508 : high = access->offset + access->size;
2436 : }
2437 5077602 : else if (access->offset > low && access->offset + access->size > high)
2438 : return NULL;
2439 : else
2440 5076962 : gcc_assert (access->offset >= low
2441 : && access->offset + access->size <= high);
2442 :
2443 9592470 : if (INTEGRAL_TYPE_P (access->type)
2444 3208075 : && TYPE_PRECISION (access->type) != access->size
2445 9757632 : && 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 4443 : 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 : return NULL;
2458 : }
2459 :
2460 9588027 : if (grp_same_access_path)
2461 8778742 : grp_same_access_path = path_comparable_for_same_access (access->expr);
2462 :
2463 9588027 : j = i + 1;
2464 15046584 : while (j < access_count)
2465 : {
2466 10968245 : struct access *ac2 = (*access_vec)[j];
2467 10968245 : if (ac2->offset != access->offset || ac2->size != access->size)
2468 : break;
2469 5458557 : if (ac2->write)
2470 : {
2471 1334330 : grp_write = true;
2472 1334330 : grp_scalar_write = (grp_scalar_write
2473 1334330 : || is_gimple_reg_type (ac2->type));
2474 : }
2475 : else
2476 : {
2477 4124227 : grp_read = true;
2478 4124227 : if (is_gimple_reg_type (ac2->type))
2479 : {
2480 1784151 : if (grp_scalar_read)
2481 : multiple_scalar_reads = true;
2482 : else
2483 385212 : grp_scalar_read = true;
2484 : }
2485 : }
2486 5458557 : grp_assignment_read |= ac2->grp_assignment_read;
2487 5458557 : grp_assignment_write |= ac2->grp_assignment_write;
2488 5458557 : grp_partial_lhs |= ac2->grp_partial_lhs;
2489 5458557 : unscalarizable_region |= ac2->grp_unscalarizable_region;
2490 5458557 : 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 5458557 : 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 5458557 : 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 5458557 : else if (types_risk_mangled_binary_repr_p (access->type, ac2->type))
2513 : {
2514 862 : 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 5458557 : if (!first_scalar && !types_compatible_p (access->type, ac2->type))
2527 448588 : bitmap_set_bit (cannot_scalarize_away_bitmap,
2528 224294 : DECL_UID (access->base));
2529 :
2530 5458557 : if (grp_same_access_path
2531 5458557 : && (!ac2->grp_same_access_path
2532 4421718 : || !same_access_path_p (access->expr, ac2->expr)))
2533 : grp_same_access_path = false;
2534 :
2535 5458557 : ac2->group_representative = access;
2536 5458557 : j++;
2537 : }
2538 :
2539 9588027 : i = j;
2540 :
2541 9588027 : access->group_representative = access;
2542 9588027 : access->grp_write = grp_write;
2543 9588027 : access->grp_read = grp_read;
2544 9588027 : access->grp_scalar_read = grp_scalar_read;
2545 9588027 : access->grp_scalar_write = grp_scalar_write;
2546 9588027 : access->grp_assignment_read = grp_assignment_read;
2547 9588027 : access->grp_assignment_write = grp_assignment_write;
2548 9588027 : access->grp_hint = multiple_scalar_reads && !constant_decl_p (var);
2549 9588027 : access->grp_partial_lhs = grp_partial_lhs;
2550 9588027 : access->grp_unscalarizable_region = unscalarizable_region;
2551 9588027 : access->grp_same_access_path = grp_same_access_path;
2552 :
2553 9588027 : *prev_acc_ptr = access;
2554 9588027 : prev_acc_ptr = &access->next_grp;
2555 : }
2556 :
2557 4078339 : 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 4012524 : create_access_replacement (struct access *access, tree reg_type = NULL_TREE)
2570 : {
2571 4012524 : tree repl;
2572 :
2573 4012524 : tree type = access->type;
2574 4012524 : if (reg_type && !is_gimple_reg_type (type))
2575 : type = reg_type;
2576 :
2577 4012524 : if (access->grp_to_be_debug_replaced)
2578 : {
2579 264465 : repl = create_tmp_var_raw (access->type);
2580 264465 : 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 3748059 : repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type),
2586 3748059 : TYPE_QUALS (type)), "SR");
2587 4012524 : if (access->grp_partial_lhs
2588 4012524 : && is_gimple_reg_type (type))
2589 992 : DECL_NOT_GIMPLE_REG_P (repl) = 1;
2590 :
2591 4012524 : DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2592 4012524 : DECL_ARTIFICIAL (repl) = 1;
2593 4012524 : DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2594 :
2595 4012524 : if (DECL_NAME (access->base)
2596 4012524 : && ((!DECL_IGNORED_P (access->base) && !DECL_ARTIFICIAL (access->base))
2597 1887282 : || (VAR_P (access->base) && DECL_NONLOCAL_FRAME (access->base))))
2598 : {
2599 1070784 : char *pretty_name = make_fancy_name (access->expr);
2600 1070784 : tree debug_expr = unshare_expr_without_location (access->expr), d;
2601 1070784 : bool fail = false;
2602 :
2603 1070784 : DECL_NAME (repl) = get_identifier (pretty_name);
2604 1070784 : DECL_NAMELESS (repl) = 1;
2605 1070784 : 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 1070784 : for (d = debug_expr;
2615 3773518 : !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2616 1396373 : d = TREE_OPERAND (d, 0))
2617 1396373 : switch (TREE_CODE (d))
2618 : {
2619 65535 : case ARRAY_REF:
2620 65535 : case ARRAY_RANGE_REF:
2621 65535 : if (TREE_OPERAND (d, 1)
2622 65535 : && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2623 : fail = true;
2624 65535 : if (TREE_OPERAND (d, 3)
2625 65535 : && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2626 : fail = true;
2627 : /* FALLTHRU */
2628 1158467 : case COMPONENT_REF:
2629 1158467 : if (TREE_OPERAND (d, 2)
2630 1158467 : && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2631 : fail = true;
2632 : break;
2633 235705 : case MEM_REF:
2634 235705 : if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2635 : fail = true;
2636 : else
2637 235705 : d = TREE_OPERAND (d, 0);
2638 : break;
2639 : default:
2640 : break;
2641 : }
2642 1070784 : if (!fail)
2643 : {
2644 1070656 : SET_DECL_DEBUG_EXPR (repl, debug_expr);
2645 1070656 : DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2646 : }
2647 1070784 : if (access->grp_no_warning)
2648 499 : suppress_warning (repl /* Be more selective! */);
2649 : else
2650 1070285 : copy_warning (repl, access->base);
2651 : }
2652 : else
2653 2941740 : suppress_warning (repl /* Be more selective! */);
2654 :
2655 4012524 : 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 4012524 : sra_stats.replacements++;
2675 :
2676 4012524 : return repl;
2677 : }
2678 :
2679 : /* Return ACCESS scalar replacement, which must exist. */
2680 :
2681 : static inline tree
2682 13756034 : get_access_replacement (struct access *access)
2683 : {
2684 13756034 : gcc_checking_assert (access->replacement_decl);
2685 13756034 : 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 9564540 : build_access_subtree (struct access **access)
2696 : {
2697 9564540 : struct access *root = *access, *last_child = NULL;
2698 9564540 : HOST_WIDE_INT limit = root->offset + root->size;
2699 :
2700 9564540 : *access = (*access)->next_grp;
2701 14616087 : while (*access && (*access)->offset + (*access)->size <= limit)
2702 : {
2703 5054132 : if (!last_child)
2704 2024318 : root->first_child = *access;
2705 : else
2706 3029814 : last_child->next_sibling = *access;
2707 5054132 : last_child = *access;
2708 5054132 : (*access)->parent = root;
2709 5054132 : (*access)->grp_write |= root->grp_write;
2710 :
2711 5054132 : if (!build_access_subtree (access))
2712 : return false;
2713 : }
2714 :
2715 9561955 : if (*access && (*access)->offset < limit)
2716 2401 : 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 4078339 : build_access_trees (struct access *access)
2727 : {
2728 8586346 : while (access)
2729 : {
2730 4510408 : struct access *root = access;
2731 :
2732 4510408 : if (!build_access_subtree (&access))
2733 : return false;
2734 4508007 : 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 4075938 : verify_sra_access_forest (struct access *root)
2744 : {
2745 4075938 : struct access *access = root;
2746 4075938 : tree first_base = root->base;
2747 4075938 : gcc_assert (DECL_P (first_base));
2748 11520966 : do
2749 : {
2750 11520966 : gcc_assert (access->base == first_base);
2751 11520966 : if (access->parent)
2752 7012974 : gcc_assert (access->offset >= access->parent->offset
2753 : && access->size <= access->parent->size);
2754 11520966 : if (access->next_sibling)
2755 4133112 : gcc_assert (access->next_sibling->offset
2756 : >= access->offset + access->size);
2757 :
2758 11520966 : poly_int64 poffset, psize, pmax_size;
2759 11520966 : bool reverse;
2760 11520966 : tree base = get_ref_base_and_extent (access->expr, &poffset, &psize,
2761 : &pmax_size, &reverse);
2762 11520966 : HOST_WIDE_INT offset, size, max_size;
2763 11520966 : if (!poffset.is_constant (&offset)
2764 11520966 : || !psize.is_constant (&size)
2765 11520966 : || !pmax_size.is_constant (&max_size))
2766 : gcc_unreachable ();
2767 11520966 : gcc_assert (base == first_base);
2768 11520966 : gcc_assert (offset == access->offset);
2769 11520966 : gcc_assert (access->grp_unscalarizable_region
2770 : || access->grp_total_scalarization
2771 : || size == max_size);
2772 11520966 : gcc_assert (access->grp_unscalarizable_region
2773 : || !is_gimple_reg_type (access->type)
2774 : || size == access->size);
2775 11520966 : gcc_assert (reverse == access->reverse);
2776 :
2777 11520966 : if (access->first_child)
2778 : {
2779 2879862 : gcc_assert (access->first_child->parent == access);
2780 : access = access->first_child;
2781 : }
2782 8641104 : else if (access->next_sibling)
2783 : {
2784 3946928 : gcc_assert (access->next_sibling->parent == access->parent);
2785 : access = access->next_sibling;
2786 : }
2787 : else
2788 : {
2789 7574038 : while (access->parent && !access->next_sibling)
2790 : access = access->parent;
2791 4694176 : if (access->next_sibling)
2792 : access = access->next_sibling;
2793 : else
2794 : {
2795 4507992 : gcc_assert (access == root);
2796 4507992 : root = root->next_grp;
2797 4507992 : access = root;
2798 : }
2799 : }
2800 : }
2801 11520966 : while (access);
2802 4075938 : }
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 769971 : verify_all_sra_access_forests (void)
2809 : {
2810 769971 : bitmap_iterator bi;
2811 769971 : unsigned i;
2812 4845909 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2813 : {
2814 4075938 : tree var = candidate (i);
2815 4075938 : struct access *access = get_first_repr_for_decl (var);
2816 4075938 : if (access)
2817 : {
2818 4075938 : gcc_assert (access->base == var);
2819 4075938 : verify_sra_access_forest (access);
2820 : }
2821 : }
2822 769971 : }
2823 :
2824 : /* Return true if expr contains some ARRAY_REFs into a variable bounded
2825 : array. */
2826 :
2827 : static bool
2828 11135244 : expr_with_var_bounded_array_refs_p (tree expr)
2829 : {
2830 20997906 : while (handled_component_p (expr))
2831 : {
2832 9862662 : if (TREE_CODE (expr) == ARRAY_REF
2833 9862662 : && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2834 : return true;
2835 9862662 : 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 11520966 : analyze_access_subtree (struct access *root, struct access *parent,
2881 : bool allow_replacements, bool totally)
2882 : {
2883 11520966 : struct access *child;
2884 11520966 : HOST_WIDE_INT limit = root->offset + root->size;
2885 11520966 : HOST_WIDE_INT covered_to = root->offset;
2886 11520966 : bool scalar = is_gimple_reg_type (root->type);
2887 11520966 : bool hole = false, sth_created = false;
2888 :
2889 11520966 : if (parent)
2890 : {
2891 7012974 : if (parent->grp_read)
2892 6221172 : root->grp_read = 1;
2893 7012974 : if (parent->grp_assignment_read)
2894 2925606 : root->grp_assignment_read = 1;
2895 7012974 : if (parent->grp_write)
2896 4110233 : root->grp_write = 1;
2897 7012974 : if (parent->grp_assignment_write)
2898 3005805 : root->grp_assignment_write = 1;
2899 7012974 : if (!parent->grp_same_access_path)
2900 1180959 : root->grp_same_access_path = 0;
2901 : }
2902 :
2903 11520966 : if (root->grp_unscalarizable_region)
2904 : allow_replacements = false;
2905 :
2906 11395871 : if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2907 : allow_replacements = false;
2908 :
2909 11520966 : if (!totally && root->grp_result_of_prop_from_lhs)
2910 11520966 : allow_replacements = false;
2911 :
2912 18533940 : for (child = root->first_child; child; child = child->next_sibling)
2913 : {
2914 7012974 : if (totally)
2915 1860745 : covered_to = child->offset;
2916 : else
2917 5152229 : hole |= covered_to < child->offset;
2918 7012974 : sth_created |= analyze_access_subtree (child, root,
2919 7012974 : allow_replacements && !scalar
2920 6726413 : && !root->grp_partial_lhs,
2921 : totally);
2922 :
2923 7012974 : root->grp_unscalarized_data |= child->grp_unscalarized_data;
2924 7012974 : if (child->grp_covered)
2925 3346789 : covered_to += child->size;
2926 : else
2927 : hole = true;
2928 7012974 : if (totally && !hole)
2929 1859521 : covered_to = limit;
2930 : }
2931 :
2932 11520966 : if (allow_replacements && scalar && !root->first_child
2933 6985585 : && (totally || !root->grp_total_scalarization)
2934 : && (totally
2935 5211505 : || root->grp_hint
2936 4386106 : || ((root->grp_scalar_read || root->grp_assignment_read)
2937 1534116 : && (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 3747507 : if (INTEGRAL_TYPE_P (root->type)
2943 1683490 : && ((TREE_CODE (root->type) != INTEGER_TYPE
2944 1683490 : && TREE_CODE (root->type) != BITINT_TYPE)
2945 1615624 : || TYPE_PRECISION (root->type) != root->size)
2946 : /* But leave bitfield accesses alone. */
2947 3815386 : && (TREE_CODE (root->expr) != COMPONENT_REF
2948 66831 : || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2949 : {
2950 67586 : tree rt = root->type;
2951 67586 : gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2952 : && (root->size % BITS_PER_UNIT) == 0);
2953 67586 : if (BITINT_TYPE_P (root->type))
2954 13 : root->type = build_bitint_type (root->size, TYPE_UNSIGNED (rt));
2955 : else
2956 67573 : root->type = build_nonstandard_integer_type (root->size,
2957 67573 : TYPE_UNSIGNED (rt));
2958 135172 : root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2959 67586 : root->offset, root->reverse,
2960 : root->type, NULL, false);
2961 :
2962 67586 : 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 3747507 : root->grp_to_be_replaced = 1;
2973 3747507 : root->replacement_decl = create_access_replacement (root);
2974 3747507 : sth_created = true;
2975 3747507 : hole = false;
2976 : }
2977 : else
2978 : {
2979 7773459 : if (allow_replacements
2980 3247654 : && scalar && !root->first_child
2981 3238078 : && !root->grp_total_scalarization
2982 3237938 : && (root->grp_scalar_write || root->grp_assignment_write)
2983 10625449 : && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2984 2851990 : DECL_UID (root->base)))
2985 : {
2986 491414 : gcc_checking_assert (!root->grp_scalar_read
2987 : && !root->grp_assignment_read);
2988 491414 : sth_created = true;
2989 491414 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2990 : {
2991 264465 : root->grp_to_be_debug_replaced = 1;
2992 264465 : root->replacement_decl = create_access_replacement (root);
2993 : }
2994 : }
2995 :
2996 7773459 : if (covered_to < limit)
2997 6521674 : hole = true;
2998 7773459 : if (scalar || !allow_replacements)
2999 4211221 : root->grp_total_scalarization = 0;
3000 : }
3001 :
3002 11520966 : if (!hole)
3003 4998896 : root->grp_covered = 1;
3004 6522070 : else if (root->grp_write || comes_initialized_p (root->base))
3005 5733731 : root->grp_unscalarized_data = 1; /* not covered and written to */
3006 11520966 : 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 4075938 : analyze_access_trees (struct access *access)
3013 : {
3014 4075938 : bool ret = false;
3015 :
3016 8583930 : while (access)
3017 : {
3018 4507992 : if (analyze_access_subtree (access, NULL, true,
3019 4507992 : access->grp_total_scalarization))
3020 2228547 : ret = true;
3021 4507992 : access = access->next_grp;
3022 : }
3023 :
3024 4075938 : 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 6951778 : child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset,
3033 : HOST_WIDE_INT size, struct access **exact_match)
3034 : {
3035 6951778 : struct access *child;
3036 :
3037 12233769 : for (child = acc->first_child; child; child = child->next_sibling)
3038 : {
3039 10771030 : if (child->offset == norm_offset && child->size == size)
3040 : {
3041 5450113 : *exact_match = child;
3042 5450113 : return true;
3043 : }
3044 :
3045 5320917 : if (child->offset < norm_offset + size
3046 5245847 : && 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 access if SET_GRP_WRITE is true. */
3059 :
3060 : static struct access *
3061 1458015 : 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 1458015 : struct access **child;
3066 1458015 : tree expr = parent->base;
3067 :
3068 1458015 : gcc_assert (!model->grp_unscalarizable_region);
3069 :
3070 1458015 : struct access *access = access_pool.allocate ();
3071 1458015 : memset (access, 0, sizeof (struct access));
3072 1458015 : if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
3073 : parent->size, model->type,
3074 : model->size))
3075 : {
3076 32525 : access->grp_no_warning = true;
3077 32525 : expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
3078 : new_offset, model, NULL, false);
3079 : }
3080 :
3081 1458015 : access->base = parent->base;
3082 1458015 : access->expr = expr;
3083 1458015 : access->offset = new_offset;
3084 1458015 : access->size = model->size;
3085 1458015 : access->type = model->type;
3086 1458015 : access->parent = parent;
3087 1458015 : access->grp_read = set_grp_read;
3088 1458015 : access->grp_write = set_grp_write;
3089 1458015 : access->reverse = model->reverse;
3090 :
3091 1458015 : child = &parent->first_child;
3092 2675995 : while (*child && (*child)->offset < new_offset)
3093 1217980 : child = &(*child)->next_sibling;
3094 :
3095 1458015 : access->next_sibling = *child;
3096 1458015 : *child = access;
3097 :
3098 1458015 : return access;
3099 : }
3100 :
3101 :
3102 : /* Beginning with ACCESS, traverse its whole access subtree and mark all
3103 : sub-trees as written to. If any of them has not been marked so previously
3104 : and has assignment links leading from it, re-enqueue it. */
3105 :
3106 : static void
3107 1629960 : subtree_mark_written_and_rhs_enqueue (struct access *access)
3108 : {
3109 1629960 : if (access->grp_write)
3110 : return;
3111 1556954 : access->grp_write = true;
3112 1556954 : add_access_to_rhs_work_queue (access);
3113 :
3114 1556954 : struct access *child;
3115 2180554 : for (child = access->first_child; child; child = child->next_sibling)
3116 623600 : subtree_mark_written_and_rhs_enqueue (child);
3117 : }
3118 :
3119 : /* If there is still budget to create a propagation access for DECL, return
3120 : true and decrement the budget. Otherwise return false. */
3121 :
3122 : static bool
3123 1461625 : budget_for_propagation_access (tree decl)
3124 : {
3125 1461625 : unsigned b, *p = propagation_budget->get (decl);
3126 1461625 : if (p)
3127 883438 : b = *p;
3128 : else
3129 578187 : b = param_sra_max_propagations;
3130 :
3131 1461625 : if (b == 0)
3132 : return false;
3133 1458021 : b--;
3134 :
3135 1458021 : if (b == 0 && dump_file && (dump_flags & TDF_DETAILS))
3136 : {
3137 0 : fprintf (dump_file, "The propagation budget of ");
3138 0 : print_generic_expr (dump_file, decl);
3139 0 : fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl));
3140 : }
3141 1458021 : propagation_budget->put (decl, b);
3142 1458021 : return true;
3143 : }
3144 :
3145 : /* Return true if ACC or any of its subaccesses has grp_child set. */
3146 :
3147 : static bool
3148 2107 : access_or_its_child_written (struct access *acc)
3149 : {
3150 2107 : if (acc->grp_write)
3151 : return true;
3152 2339 : for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling)
3153 599 : if (access_or_its_child_written (sub))
3154 : return true;
3155 : return false;
3156 : }
3157 :
3158 : /* Propagate subaccesses and grp_write flags of RACC across an assignment link
3159 : to LACC. Enqueue sub-accesses as necessary so that the write flag is
3160 : propagated transitively. Return true if anything changed. Additionally, if
3161 : RACC is a scalar access but LACC is not, change the type of the latter, if
3162 : possible. */
3163 :
3164 : static bool
3165 3694717 : propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc)
3166 : {
3167 3694717 : struct access *rchild;
3168 3694717 : HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
3169 3694717 : bool ret = false;
3170 :
3171 : /* IF the LHS is still not marked as being written to, we only need to do so
3172 : if the RHS at this level actually was. */
3173 3694717 : if (!lacc->grp_write)
3174 : {
3175 1672494 : gcc_checking_assert (!comes_initialized_p (racc->base));
3176 1672494 : if (racc->grp_write)
3177 : {
3178 800498 : subtree_mark_written_and_rhs_enqueue (lacc);
3179 800498 : ret = true;
3180 : }
3181 : }
3182 :
3183 3694717 : if (is_gimple_reg_type (lacc->type)
3184 2869732 : || lacc->grp_unscalarizable_region
3185 6563833 : || racc->grp_unscalarizable_region)
3186 : {
3187 826710 : if (!lacc->grp_write)
3188 : {
3189 18709 : ret = true;
3190 18709 : subtree_mark_written_and_rhs_enqueue (lacc);
3191 : }
3192 : return ret;
3193 : }
3194 :
3195 2868007 : if (is_gimple_reg_type (racc->type))
3196 : {
3197 159502 : if (!lacc->grp_write)
3198 : {
3199 3265 : ret = true;
3200 3265 : subtree_mark_written_and_rhs_enqueue (lacc);
3201 : }
3202 159502 : if (!lacc->first_child
3203 159214 : && !racc->first_child
3204 318338 : && !types_risk_mangled_binary_repr_p (racc->type, lacc->type))
3205 : {
3206 : /* We are about to change the access type from aggregate to scalar,
3207 : so we need to put the reverse flag onto the access, if any. */
3208 158836 : const bool reverse
3209 158836 : = TYPE_REVERSE_STORAGE_ORDER (lacc->type)
3210 1 : && !POINTER_TYPE_P (racc->type)
3211 158836 : && !VECTOR_TYPE_P (racc->type);
3212 158836 : tree t = lacc->base;
3213 :
3214 158836 : lacc->type = racc->type;
3215 : /* We know racc and lacc are of different types so can pass -1 as
3216 : cur_size. */
3217 158836 : if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
3218 : lacc->offset, -1,
3219 : racc->type, racc->size))
3220 : {
3221 158030 : lacc->expr = t;
3222 158030 : lacc->grp_same_access_path = true;
3223 : }
3224 : else
3225 : {
3226 806 : lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
3227 : lacc->base, lacc->offset,
3228 : racc, NULL, false);
3229 806 : if (TREE_CODE (lacc->expr) == MEM_REF)
3230 806 : REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse;
3231 806 : lacc->grp_no_warning = true;
3232 806 : lacc->grp_same_access_path = false;
3233 : }
3234 158836 : lacc->reverse = reverse;
3235 : }
3236 : return ret;
3237 : }
3238 :
3239 5865572 : for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
3240 : {
3241 3157067 : struct access *new_acc = NULL;
3242 3157067 : HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
3243 :
3244 3157067 : if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size,
3245 : &new_acc))
3246 : {
3247 2569401 : if (new_acc)
3248 : {
3249 2544549 : if (!new_acc->grp_write && rchild->grp_write)
3250 : {
3251 178065 : gcc_assert (!lacc->grp_write);
3252 178065 : subtree_mark_written_and_rhs_enqueue (new_acc);
3253 178065 : ret = true;
3254 : }
3255 :
3256 2544549 : rchild->grp_hint = 1;
3257 2544549 : new_acc->grp_hint |= new_acc->grp_read;
3258 2544549 : if (rchild->first_child
3259 2544549 : && propagate_subaccesses_from_rhs (new_acc, rchild))
3260 : {
3261 1466 : ret = 1;
3262 1466 : add_access_to_rhs_work_queue (new_acc);
3263 : }
3264 : }
3265 : else
3266 : {
3267 24852 : if (!lacc->grp_write)
3268 : {
3269 5083 : ret = true;
3270 5083 : subtree_mark_written_and_rhs_enqueue (lacc);
3271 : }
3272 : }
3273 2574093 : continue;
3274 : }
3275 :
3276 592358 : if (rchild->grp_unscalarizable_region
3277 587666 : || !budget_for_propagation_access (lacc->base))
3278 : {
3279 4692 : if (!lacc->grp_write && access_or_its_child_written (rchild))
3280 : {
3281 334 : ret = true;
3282 334 : subtree_mark_written_and_rhs_enqueue (lacc);
3283 : }
3284 4692 : continue;
3285 : }
3286 :
3287 582974 : rchild->grp_hint = 1;
3288 : /* Because get_ref_base_and_extent always includes padding in size for
3289 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3290 : type, we might be actually attempting to here to create a child of the
3291 : same type as the parent. */
3292 582974 : if (!types_compatible_p (lacc->type, rchild->type))
3293 582974 : new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
3294 : false,
3295 582974 : (lacc->grp_write
3296 283422 : || rchild->grp_write));
3297 : else
3298 0 : new_acc = lacc;
3299 582974 : gcc_checking_assert (new_acc);
3300 582974 : if (racc->first_child)
3301 582974 : propagate_subaccesses_from_rhs (new_acc, rchild);
3302 :
3303 582974 : add_access_to_rhs_work_queue (lacc);
3304 582974 : ret = true;
3305 : }
3306 :
3307 : return ret;
3308 : }
3309 :
3310 : /* Propagate subaccesses of LACC across an assignment link to RACC if they
3311 : should inhibit total scalarization of the corresponding area. No flags are
3312 : being propagated in the process. Return true if anything changed. */
3313 :
3314 : static bool
3315 6089415 : propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc)
3316 : {
3317 6089415 : if (is_gimple_reg_type (racc->type)
3318 2137346 : || lacc->grp_unscalarizable_region
3319 8225721 : || racc->grp_unscalarizable_region)
3320 : return false;
3321 :
3322 : /* TODO: Do we want set some new racc flag to stop potential total
3323 : scalarization if lacc is a scalar access (and none fo the two have
3324 : children)? */
3325 :
3326 2136283 : bool ret = false;
3327 2136283 : HOST_WIDE_INT norm_delta = racc->offset - lacc->offset;
3328 2136283 : for (struct access *lchild = lacc->first_child;
3329 5935501 : lchild;
3330 3799218 : lchild = lchild->next_sibling)
3331 : {
3332 3799218 : struct access *matching_acc = NULL;
3333 3799218 : HOST_WIDE_INT norm_offset = lchild->offset + norm_delta;
3334 :
3335 6723389 : if (lchild->grp_unscalarizable_region
3336 3794711 : || child_would_conflict_in_acc (racc, norm_offset, lchild->size,
3337 : &matching_acc)
3338 4674291 : || !budget_for_propagation_access (racc->base))
3339 : {
3340 2924171 : if (matching_acc
3341 2924171 : && propagate_subaccesses_from_lhs (lchild, matching_acc))
3342 201 : add_access_to_lhs_work_queue (matching_acc);
3343 2924171 : continue;
3344 : }
3345 :
3346 : /* Because get_ref_base_and_extent always includes padding in size for
3347 : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3348 : type, we might be actually attempting to here to create a child of the
3349 : same type as the parent. */
3350 875047 : if (!types_compatible_p (racc->type, lchild->type))
3351 : {
3352 875041 : struct access *new_acc
3353 875041 : = create_artificial_child_access (racc, lchild, norm_offset,
3354 : true, false);
3355 875041 : new_acc->grp_result_of_prop_from_lhs = 1;
3356 875041 : propagate_subaccesses_from_lhs (lchild, new_acc);
3357 : }
3358 : else
3359 6 : propagate_subaccesses_from_lhs (lchild, racc);
3360 875047 : ret = true;
3361 : }
3362 : return ret;
3363 : }
3364 :
3365 : /* Propagate all subaccesses across assignment links. */
3366 :
3367 : static void
3368 769971 : propagate_all_subaccesses (void)
3369 : {
3370 769971 : propagation_budget = new hash_map<tree, unsigned>;
3371 2346279 : while (rhs_work_queue_head)
3372 : {
3373 1576308 : struct access *racc = pop_access_from_rhs_work_queue ();
3374 1576308 : struct assign_link *link;
3375 :
3376 1576308 : if (racc->group_representative)
3377 1575680 : racc= racc->group_representative;
3378 1576308 : gcc_assert (racc->first_rhs_link);
3379 :
3380 4676132 : for (link = racc->first_rhs_link; link; link = link->next_rhs)
3381 : {
3382 3099824 : struct access *lacc = link->lacc;
3383 :
3384 3099824 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3385 7208 : continue;
3386 3092616 : lacc = lacc->group_representative;
3387 :
3388 3092616 : bool reque_parents = false;
3389 3092616 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3390 : {
3391 1610 : if (!lacc->grp_write)
3392 : {
3393 406 : subtree_mark_written_and_rhs_enqueue (lacc);
3394 406 : reque_parents = true;
3395 : }
3396 : }
3397 3091006 : else if (propagate_subaccesses_from_rhs (lacc, racc))
3398 : reque_parents = true;
3399 :
3400 1131205 : if (reque_parents)
3401 1279813 : do
3402 : {
3403 1279813 : add_access_to_rhs_work_queue (lacc);
3404 1279813 : lacc = lacc->parent;
3405 : }
3406 1279813 : while (lacc);
3407 : }
3408 : }
3409 :
3410 2136340 : while (lhs_work_queue_head)
3411 : {
3412 1366369 : struct access *lacc = pop_access_from_lhs_work_queue ();
3413 1366369 : struct assign_link *link;
3414 :
3415 1366369 : if (lacc->group_representative)
3416 1362827 : lacc = lacc->group_representative;
3417 1366369 : gcc_assert (lacc->first_lhs_link);
3418 :
3419 1366369 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3420 4268 : continue;
3421 :
3422 3671670 : for (link = lacc->first_lhs_link; link; link = link->next_lhs)
3423 : {
3424 2309569 : struct access *racc = link->racc;
3425 :
3426 2309569 : if (racc->group_representative)
3427 2309050 : racc = racc->group_representative;
3428 2309569 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3429 765 : continue;
3430 2308804 : if (propagate_subaccesses_from_lhs (lacc, racc))
3431 346370 : add_access_to_lhs_work_queue (racc);
3432 : }
3433 : }
3434 1539942 : delete propagation_budget;
3435 769971 : }
3436 :
3437 : /* Return true if the forest beginning with ROOT does not contain
3438 : unscalarizable regions or non-byte aligned accesses. */
3439 :
3440 : static bool
3441 785186 : can_totally_scalarize_forest_p (struct access *root)
3442 : {
3443 785186 : struct access *access = root;
3444 2233640 : do
3445 : {
3446 2233640 : if (access->grp_unscalarizable_region
3447 2231601 : || (access->offset % BITS_PER_UNIT) != 0
3448 2231216 : || (access->size % BITS_PER_UNIT) != 0
3449 4461051 : || (is_gimple_reg_type (access->type)
3450 1473038 : && access->first_child))
3451 : return false;
3452 :
3453 2227058 : if (access->first_child)
3454 : access = access->first_child;
3455 1593586 : else if (access->next_sibling)
3456 : access = access->next_sibling;
3457 : else
3458 : {
3459 1484440 : while (access->parent && !access->next_sibling)
3460 : access = access->parent;
3461 855936 : if (access->next_sibling)
3462 : access = access->next_sibling;
3463 : else
3464 : {
3465 802350 : gcc_assert (access == root);
3466 802350 : root = root->next_grp;
3467 802350 : access = root;
3468 : }
3469 : }
3470 : }
3471 2227058 : while (access);
3472 : return true;
3473 : }
3474 :
3475 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3476 : reference EXPR for total scalarization purposes and mark it as such. Within
3477 : the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3478 :
3479 : static struct access *
3480 504698 : create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos,
3481 : HOST_WIDE_INT size, tree type, tree expr,
3482 : struct access **ptr,
3483 : struct access *next_sibling)
3484 : {
3485 504698 : struct access *access = access_pool.allocate ();
3486 504698 : memset (access, 0, sizeof (struct access));
3487 504698 : access->base = parent->base;
3488 504698 : access->offset = pos;
3489 504698 : access->size = size;
3490 504698 : access->expr = expr;
3491 504698 : access->type = type;
3492 504698 : access->parent = parent;
3493 504698 : access->grp_write = parent->grp_write;
3494 504698 : access->grp_total_scalarization = 1;
3495 504698 : access->grp_hint = 1;
3496 504698 : access->grp_same_access_path = 0;
3497 504698 : access->reverse = reverse_storage_order_for_component_p (expr);
3498 :
3499 504698 : access->next_sibling = next_sibling;
3500 504698 : *ptr = access;
3501 504698 : return access;
3502 : }
3503 :
3504 : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3505 : reference EXPR for total scalarization purposes and mark it as such, link it
3506 : at *PTR and reshape the tree so that those elements at *PTR and their
3507 : siblings which fall within the part described by POS and SIZE are moved to
3508 : be children of the new access. If a partial overlap is detected, return
3509 : NULL. */
3510 :
3511 : static struct access *
3512 504698 : create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos,
3513 : HOST_WIDE_INT size, tree type, tree expr,
3514 : struct access **ptr)
3515 : {
3516 504698 : struct access **p = ptr;
3517 :
3518 712830 : while (*p && (*p)->offset < pos + size)
3519 : {
3520 208132 : if ((*p)->offset + (*p)->size > pos + size)
3521 : return NULL;
3522 208132 : p = &(*p)->next_sibling;
3523 : }
3524 :
3525 504698 : struct access *next_child = *ptr;
3526 504698 : struct access *new_acc
3527 504698 : = create_total_scalarization_access (parent, pos, size, type, expr,
3528 : ptr, *p);
3529 504698 : if (p != ptr)
3530 : {
3531 84540 : new_acc->first_child = next_child;
3532 84540 : *p = NULL;
3533 292672 : for (struct access *a = next_child; a; a = a->next_sibling)
3534 208132 : a->parent = new_acc;
3535 : }
3536 : return new_acc;
3537 : }
3538 :
3539 : static bool totally_scalarize_subtree (struct access *root);
3540 :
3541 : /* Return true if INNER is either the same type as OUTER or if it is the type
3542 : of a record field in OUTER at offset zero, possibly in nested
3543 : sub-records. */
3544 :
3545 : static bool
3546 181896 : access_and_field_type_match_p (tree outer, tree inner)
3547 : {
3548 181896 : if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner))
3549 : return true;
3550 572 : if (TREE_CODE (outer) != RECORD_TYPE)
3551 : return false;
3552 560 : tree fld = TYPE_FIELDS (outer);
3553 11281 : while (fld)
3554 : {
3555 11087 : if (TREE_CODE (fld) == FIELD_DECL)
3556 : {
3557 625 : if (!zerop (DECL_FIELD_OFFSET (fld)))
3558 : return false;
3559 625 : if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner)
3560 : return true;
3561 443 : if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE)
3562 259 : fld = TYPE_FIELDS (TREE_TYPE (fld));
3563 : else
3564 : return false;
3565 : }
3566 : else
3567 10462 : fld = DECL_CHAIN (fld);
3568 : }
3569 : return false;
3570 : }
3571 :
3572 : /* Return type of total_should_skip_creating_access indicating whether a total
3573 : scalarization access for a field/element should be created, whether it
3574 : already exists or whether the entire total scalarization has to fail. */
3575 :
3576 : enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED};
3577 :
3578 : /* Do all the necessary steps in total scalarization when the given aggregate
3579 : type has a TYPE at POS with the given SIZE should be put into PARENT and
3580 : when we have processed all its siblings with smaller offsets up until and
3581 : including LAST_SEEN_SIBLING (which can be NULL).
3582 :
3583 : If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3584 : appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3585 : creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3586 : representing the described part of the aggregate for the purposes of total
3587 : scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3588 : prevents total scalarization from happening at all. */
3589 :
3590 : static enum total_sra_field_state
3591 1861045 : total_should_skip_creating_access (struct access *parent,
3592 : struct access **last_seen_sibling,
3593 : tree type, HOST_WIDE_INT pos,
3594 : HOST_WIDE_INT size)
3595 : {
3596 1861045 : struct access *next_child;
3597 1861045 : if (!*last_seen_sibling)
3598 849067 : next_child = parent->first_child;
3599 : else
3600 1011978 : next_child = (*last_seen_sibling)->next_sibling;
3601 :
3602 : /* First, traverse the chain of siblings until it points to an access with
3603 : offset at least equal to POS. Check all skipped accesses whether they
3604 : span the POS boundary and if so, return with a failure. */
3605 1861054 : while (next_child && next_child->offset < pos)
3606 : {
3607 9 : if (next_child->offset + next_child->size > pos)
3608 : return TOTAL_FLD_FAILED;
3609 9 : *last_seen_sibling = next_child;
3610 9 : next_child = next_child->next_sibling;
3611 : }
3612 :
3613 : /* Now check whether next_child has exactly the right POS and SIZE and if so,
3614 : whether it can represent what we need and can be totally scalarized
3615 : itself. */
3616 1861045 : if (next_child && next_child->offset == pos
3617 1437392 : && next_child->size == size)
3618 : {
3619 1356119 : if (!is_gimple_reg_type (next_child->type)
3620 1356119 : && (!access_and_field_type_match_p (type, next_child->type)
3621 181506 : || !totally_scalarize_subtree (next_child)))
3622 : return TOTAL_FLD_FAILED;
3623 :
3624 1355683 : *last_seen_sibling = next_child;
3625 1355683 : return TOTAL_FLD_DONE;
3626 : }
3627 :
3628 : /* If the child we're looking at would partially overlap, we just cannot
3629 : totally scalarize. */
3630 : if (next_child
3631 113364 : && next_child->offset < pos + size
3632 84768 : && next_child->offset + next_child->size > pos + size)
3633 : return TOTAL_FLD_FAILED;
3634 :
3635 504886 : if (is_gimple_reg_type (type))
3636 : {
3637 : /* We don't scalarize accesses that are children of other scalar type
3638 : accesses, so if we go on and create an access for a register type,
3639 : there should not be any pre-existing children. There are rare cases
3640 : where the requested type is a vector but we already have register
3641 : accesses for all its elements which is equally good. Detect that
3642 : situation or whether we need to bail out. */
3643 :
3644 : HOST_WIDE_INT covered = pos;
3645 : bool skipping = false;
3646 : while (next_child
3647 378531 : && next_child->offset + next_child->size <= pos + size)
3648 : {
3649 748 : if (next_child->offset != covered
3650 748 : || !is_gimple_reg_type (next_child->type))
3651 : return TOTAL_FLD_FAILED;
3652 :
3653 748 : covered += next_child->size;
3654 748 : *last_seen_sibling = next_child;
3655 748 : next_child = next_child->next_sibling;
3656 748 : skipping = true;
3657 : }
3658 :
3659 377783 : if (skipping)
3660 : {
3661 188 : if (covered != pos + size)
3662 : return TOTAL_FLD_FAILED;
3663 : else
3664 168 : return TOTAL_FLD_DONE;
3665 : }
3666 : }
3667 :
3668 : return TOTAL_FLD_CREATE;
3669 : }
3670 :
3671 : /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3672 : spanning all uncovered areas covered by ROOT, return false if the attempt
3673 : failed. All created accesses will have grp_unscalarizable_region set (and
3674 : should be ignored if the function returns false). */
3675 :
3676 : static bool
3677 849583 : totally_scalarize_subtree (struct access *root)
3678 : {
3679 849583 : gcc_checking_assert (!root->grp_unscalarizable_region);
3680 849583 : gcc_checking_assert (!is_gimple_reg_type (root->type));
3681 :
3682 849583 : struct access *last_seen_sibling = NULL;
3683 :
3684 849583 : switch (TREE_CODE (root->type))
3685 : {
3686 833845 : case RECORD_TYPE:
3687 10922162 : for (tree fld = TYPE_FIELDS (root->type); fld; fld = DECL_CHAIN (fld))
3688 10088840 : if (TREE_CODE (fld) == FIELD_DECL)
3689 : {
3690 1864650 : tree ft = TREE_TYPE (fld);
3691 1864650 : HOST_WIDE_INT fsize = tree_to_uhwi (DECL_SIZE (fld));
3692 1864650 : if (!fsize)
3693 39511 : continue;
3694 :
3695 1825139 : HOST_WIDE_INT pos = root->offset + int_bit_position (fld);
3696 1825139 : if (pos + fsize > root->offset + root->size)
3697 : return false;
3698 1825139 : enum total_sra_field_state
3699 1825139 : state = total_should_skip_creating_access (root,
3700 : &last_seen_sibling,
3701 : ft, pos, fsize);
3702 1825139 : switch (state)
3703 : {
3704 : case TOTAL_FLD_FAILED:
3705 : return false;
3706 1345675 : case TOTAL_FLD_DONE:
3707 1345675 : continue;
3708 479020 : case TOTAL_FLD_CREATE:
3709 479020 : break;
3710 0 : default:
3711 0 : gcc_unreachable ();
3712 : }
3713 :
3714 479020 : struct access **p = (last_seen_sibling
3715 479020 : ? &last_seen_sibling->next_sibling
3716 : : &root->first_child);
3717 479020 : tree nref = build3 (COMPONENT_REF, ft, root->expr, fld, NULL_TREE);
3718 479020 : struct access *new_child
3719 479020 : = create_total_access_and_reshape (root, pos, fsize, ft, nref, p);
3720 479020 : if (!new_child)
3721 : return false;
3722 :
3723 479020 : if (!is_gimple_reg_type (ft)
3724 479020 : && !totally_scalarize_subtree (new_child))
3725 : return false;
3726 478941 : last_seen_sibling = new_child;
3727 : }
3728 : break;
3729 15738 : case ARRAY_TYPE:
3730 15738 : {
3731 15738 : tree elemtype = TREE_TYPE (root->type);
3732 15738 : HOST_WIDE_INT el_size;
3733 15738 : offset_int idx, max;
3734 15738 : if (!prepare_iteration_over_array_elts (root->type, &el_size,
3735 : &idx, &max))
3736 : break;
3737 :
3738 15738 : for (HOST_WIDE_INT pos = root->offset;
3739 51592 : idx <= max;
3740 35854 : pos += el_size, ++idx)
3741 : {
3742 35906 : enum total_sra_field_state
3743 35906 : state = total_should_skip_creating_access (root,
3744 : &last_seen_sibling,
3745 : elemtype, pos,
3746 : el_size);
3747 35906 : switch (state)
3748 : {
3749 : case TOTAL_FLD_FAILED:
3750 52 : return false;
3751 10176 : case TOTAL_FLD_DONE:
3752 10176 : continue;
3753 25678 : case TOTAL_FLD_CREATE:
3754 25678 : break;
3755 0 : default:
3756 0 : gcc_unreachable ();
3757 : }
3758 :
3759 25678 : struct access **p = (last_seen_sibling
3760 25678 : ? &last_seen_sibling->next_sibling
3761 : : &root->first_child);
3762 51356 : tree nref = build4 (ARRAY_REF, elemtype, root->expr,
3763 25678 : wide_int_to_tree (TYPE_DOMAIN (root->type),
3764 25678 : idx),
3765 : NULL_TREE, NULL_TREE);
3766 25678 : struct access *new_child
3767 25678 : = create_total_access_and_reshape (root, pos, el_size, elemtype,
3768 : nref, p);
3769 25678 : if (!new_child)
3770 : return false;
3771 :
3772 25678 : if (!is_gimple_reg_type (elemtype)
3773 25678 : && !totally_scalarize_subtree (new_child))
3774 : return false;
3775 25678 : last_seen_sibling = new_child;
3776 : }
3777 : }
3778 15686 : break;
3779 0 : default:
3780 0 : gcc_unreachable ();
3781 : }
3782 : return true;
3783 : }
3784 :
3785 : /* Get the total total scalarization size limit in the current function. */
3786 :
3787 : unsigned HOST_WIDE_INT
3788 773955 : sra_get_max_scalarization_size (void)
3789 : {
3790 773955 : bool optimize_speed_p = !optimize_function_for_size_p (cfun);
3791 : /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3792 : fall back to a target default. */
3793 773955 : unsigned HOST_WIDE_INT max_scalarization_size
3794 773955 : = get_move_ratio (optimize_speed_p) * MOVE_MAX;
3795 :
3796 773955 : if (optimize_speed_p)
3797 : {
3798 753243 : if (OPTION_SET_P (param_sra_max_scalarization_size_speed))
3799 9 : max_scalarization_size = param_sra_max_scalarization_size_speed;
3800 : }
3801 : else
3802 : {
3803 20712 : if (OPTION_SET_P (param_sra_max_scalarization_size_size))
3804 0 : max_scalarization_size = param_sra_max_scalarization_size_size;
3805 : }
3806 773955 : max_scalarization_size *= BITS_PER_UNIT;
3807 773955 : return max_scalarization_size;
3808 : }
3809 :
3810 : /* Go through all accesses collected throughout the (intraprocedural) analysis
3811 : stage, exclude overlapping ones, identify representatives and build trees
3812 : out of them, making decisions about scalarization on the way. Return true
3813 : iff there are any to-be-scalarized variables after this stage. */
3814 :
3815 : static bool
3816 769971 : analyze_all_variable_accesses (void)
3817 : {
3818 769971 : int res = 0;
3819 769971 : bitmap tmp = BITMAP_ALLOC (NULL);
3820 769971 : bitmap_iterator bi;
3821 769971 : unsigned i;
3822 :
3823 769971 : bitmap_copy (tmp, candidate_bitmap);
3824 5029813 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3825 : {
3826 4259842 : tree var = candidate (i);
3827 4259842 : struct access *access;
3828 :
3829 4259842 : access = sort_and_splice_var_accesses (var);
3830 4259842 : if (!access || !build_access_trees (access))
3831 183904 : disqualify_candidate (var,
3832 : "No or inhibitingly overlapping accesses.");
3833 : }
3834 :
3835 769971 : propagate_all_subaccesses ();
3836 :
3837 769971 : unsigned HOST_WIDE_INT max_scalarization_size
3838 769971 : = sra_get_max_scalarization_size ();
3839 4845909 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3840 4075938 : if (bitmap_bit_p (should_scalarize_away_bitmap, i)
3841 4075938 : && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
3842 : {
3843 861750 : tree var = candidate (i);
3844 861750 : if (!VAR_P (var))
3845 75669 : continue;
3846 :
3847 786081 : if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) > max_scalarization_size)
3848 : {
3849 7360 : if (dump_file && (dump_flags & TDF_DETAILS))
3850 : {
3851 0 : fprintf (dump_file, "Too big to totally scalarize: ");
3852 0 : print_generic_expr (dump_file, var);
3853 0 : fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
3854 : }
3855 7360 : continue;
3856 : }
3857 :
3858 778721 : bool all_types_ok = true;
3859 778721 : for (struct access *access = get_first_repr_for_decl (var);
3860 1541478 : access;
3861 762757 : access = access->next_grp)
3862 785186 : if (!can_totally_scalarize_forest_p (access)
3863 1563790 : || !totally_scalarizable_type_p (access->type,
3864 : constant_decl_p (var),
3865 : 0, nullptr))
3866 : {
3867 : all_types_ok = false;
3868 : break;
3869 : }
3870 778721 : if (!all_types_ok)
3871 22429 : continue;
3872 :
3873 756292 : if (dump_file && (dump_flags & TDF_DETAILS))
3874 : {
3875 1 : fprintf (dump_file, "Will attempt to totally scalarize ");
3876 1 : print_generic_expr (dump_file, var);
3877 1 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3878 : }
3879 756292 : bool scalarized = true;
3880 756292 : for (struct access *access = get_first_repr_for_decl (var);
3881 1518597 : access;
3882 762305 : access = access->next_grp)
3883 762755 : if (!is_gimple_reg_type (access->type)
3884 762755 : && !totally_scalarize_subtree (access))
3885 : {
3886 : scalarized = false;
3887 : break;
3888 : }
3889 :
3890 756292 : if (scalarized)
3891 755842 : for (struct access *access = get_first_repr_for_decl (var);
3892 1518147 : access;
3893 762305 : access = access->next_grp)
3894 762305 : access->grp_total_scalarization = true;
3895 : }
3896 :
3897 769971 : if (flag_checking)
3898 769971 : verify_all_sra_access_forests ();
3899 :
3900 769971 : bitmap_copy (tmp, candidate_bitmap);
3901 4845909 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3902 : {
3903 4075938 : tree var = candidate (i);
3904 4075938 : struct access *access = get_first_repr_for_decl (var);
3905 :
3906 4075938 : if (analyze_access_trees (access))
3907 : {
3908 1873886 : res++;
3909 1873886 : if (dump_file && (dump_flags & TDF_DETAILS))
3910 : {
3911 8 : fprintf (dump_file, "\nAccess trees for ");
3912 8 : print_generic_expr (dump_file, var);
3913 8 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3914 8 : dump_access_tree (dump_file, access);
3915 8 : fprintf (dump_file, "\n");
3916 : }
3917 : }
3918 : else
3919 2202052 : disqualify_candidate (var, "No scalar replacements to be created.");
3920 : }
3921 :
3922 769971 : BITMAP_FREE (tmp);
3923 :
3924 769971 : if (res)
3925 : {
3926 458524 : statistics_counter_event (cfun, "Scalarized aggregates", res);
3927 458524 : return true;
3928 : }
3929 : else
3930 : return false;
3931 : }
3932 :
3933 : /* Generate statements copying scalar replacements of accesses within a subtree
3934 : into or out of AGG. ACCESS, all its children, siblings and their children
3935 : are to be processed. AGG is an aggregate type expression (can be a
3936 : declaration but does not have to be, it can for example also be a mem_ref or
3937 : a series of handled components). TOP_OFFSET is the offset of the processed
3938 : subtree which has to be subtracted from offsets of individual accesses to
3939 : get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3940 : replacements in the interval <start_offset, start_offset + chunk_size>,
3941 : otherwise copy all. GSI is a statement iterator used to place the new
3942 : statements. WRITE should be true when the statements should write from AGG
3943 : to the replacement and false if vice versa. If INSERT_AFTER is true, new
3944 : statements will be added after the current statement in GSI, they will be
3945 : added before the statement otherwise. If FORCE_REF_ALL is true then
3946 : memory accesses will use alias-set zero. */
3947 :
3948 : static void
3949 1984434 : generate_subtree_copies (struct access *access, tree agg,
3950 : HOST_WIDE_INT top_offset,
3951 : HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
3952 : gimple_stmt_iterator *gsi, bool write,
3953 : bool insert_after, location_t loc,
3954 : bool force_ref_all = false)
3955 : {
3956 : /* Never write anything into constant pool decls. See PR70602. */
3957 3064760 : if (!write && constant_decl_p (agg))
3958 : return;
3959 4793727 : do
3960 : {
3961 4793727 : if (chunk_size && access->offset >= start_offset + chunk_size)
3962 : return;
3963 :
3964 4793727 : if (access->grp_to_be_replaced
3965 3755662 : && (chunk_size == 0
3966 0 : || access->offset + access->size > start_offset))
3967 : {
3968 3755662 : tree expr, repl = get_access_replacement (access);
3969 3755662 : gassign *stmt;
3970 :
3971 3755662 : expr = build_ref_for_model (loc, agg, access->offset - top_offset,
3972 : access, gsi, insert_after, force_ref_all);
3973 :
3974 3755662 : if (write)
3975 : {
3976 1678184 : if (access->grp_partial_lhs)
3977 8 : expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
3978 : !insert_after,
3979 : insert_after ? GSI_NEW_STMT
3980 : : GSI_SAME_STMT);
3981 1678184 : stmt = gimple_build_assign (repl, expr);
3982 : }
3983 : else
3984 : {
3985 2077478 : suppress_warning (repl /* Be more selective! */);
3986 2077478 : if (access->grp_partial_lhs)
3987 144 : repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3988 : !insert_after,
3989 : insert_after ? GSI_NEW_STMT
3990 : : GSI_SAME_STMT);
3991 2077478 : stmt = gimple_build_assign (expr, repl);
3992 : }
3993 3755662 : gimple_set_location (stmt, loc);
3994 :
3995 3755662 : if (insert_after)
3996 1678184 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3997 : else
3998 2077478 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3999 3755662 : update_stmt (stmt);
4000 3755662 : sra_stats.subtree_copies++;
4001 3755662 : }
4002 1038065 : else if (write
4003 403294 : && access->grp_to_be_debug_replaced
4004 5781 : && (chunk_size == 0
4005 0 : || access->offset + access->size > start_offset))
4006 : {
4007 5781 : gdebug *ds;
4008 11562 : tree drhs = build_debug_ref_for_model (loc, agg,
4009 5781 : access->offset - top_offset,
4010 : access);
4011 5781 : ds = gimple_build_debug_bind (get_access_replacement (access),
4012 : drhs, gsi_stmt (*gsi));
4013 5781 : if (insert_after)
4014 5781 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4015 : else
4016 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4017 : }
4018 :
4019 4793727 : if (access->first_child)
4020 486256 : generate_subtree_copies (access->first_child, agg, top_offset,
4021 : start_offset, chunk_size, gsi,
4022 : write, insert_after, loc, force_ref_all);
4023 :
4024 4793727 : access = access->next_sibling;
4025 : }
4026 4793727 : while (access);
4027 : }
4028 :
4029 : /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
4030 : root of the subtree to be processed. GSI is the statement iterator used
4031 : for inserting statements which are added after the current statement if
4032 : INSERT_AFTER is true or before it otherwise. */
4033 :
4034 : static void
4035 554310 : init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
4036 : bool insert_after, location_t loc)
4037 :
4038 : {
4039 554310 : struct access *child;
4040 :
4041 554310 : if (access->grp_to_be_replaced)
4042 : {
4043 255480 : gassign *stmt;
4044 :
4045 255480 : stmt = gimple_build_assign (get_access_replacement (access),
4046 : build_zero_cst (access->type));
4047 255480 : if (insert_after)
4048 36246 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4049 : else
4050 219234 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4051 255480 : update_stmt (stmt);
4052 255480 : gimple_set_location (stmt, loc);
4053 : }
4054 298830 : else if (access->grp_to_be_debug_replaced)
4055 : {
4056 30170 : gdebug *ds
4057 30170 : = gimple_build_debug_bind (get_access_replacement (access),
4058 : build_zero_cst (access->type),
4059 : gsi_stmt (*gsi));
4060 30170 : if (insert_after)
4061 30170 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
4062 : else
4063 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4064 : }
4065 :
4066 957880 : for (child = access->first_child; child; child = child->next_sibling)
4067 403570 : init_subtree_with_zero (child, gsi, insert_after, loc);
4068 554310 : }
4069 :
4070 : /* Clobber all scalar replacements in an access subtree. ACCESS is the
4071 : root of the subtree to be processed. GSI is the statement iterator used
4072 : for inserting statements which are added after the current statement if
4073 : INSERT_AFTER is true or before it otherwise. */
4074 :
4075 : static void
4076 3043774 : clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
4077 : bool insert_after, location_t loc)
4078 :
4079 : {
4080 3043774 : struct access *child;
4081 :
4082 3043774 : if (access->grp_to_be_replaced)
4083 : {
4084 1947073 : tree rep = get_access_replacement (access);
4085 1947073 : tree clobber = build_clobber (access->type);
4086 1947073 : gimple *stmt = gimple_build_assign (rep, clobber);
4087 :
4088 1947073 : if (insert_after)
4089 391942 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4090 : else
4091 1555131 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4092 1947073 : update_stmt (stmt);
4093 1947073 : gimple_set_location (stmt, loc);
4094 : }
4095 :
4096 5003603 : for (child = access->first_child; child; child = child->next_sibling)
4097 1959829 : clobber_subtree (child, gsi, insert_after, loc);
4098 3043774 : }
4099 :
4100 : /* Search for an access representative for the given expression EXPR and
4101 : return it or NULL if it cannot be found. */
4102 :
4103 : static struct access *
4104 48715426 : get_access_for_expr (tree expr)
4105 : {
4106 48715426 : poly_int64 poffset, psize, pmax_size;
4107 48715426 : HOST_WIDE_INT offset, max_size;
4108 48715426 : tree base;
4109 48715426 : bool reverse;
4110 :
4111 48715426 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
4112 : &reverse);
4113 48715426 : if (!known_size_p (pmax_size)
4114 48561680 : || !pmax_size.is_constant (&max_size)
4115 48561680 : || !poffset.is_constant (&offset)
4116 48715426 : || !DECL_P (base))
4117 : return NULL;
4118 :
4119 22777873 : if (tree basesize = DECL_SIZE (base))
4120 : {
4121 22732778 : poly_int64 sz;
4122 22732778 : if (offset < 0
4123 22732762 : || !poly_int_tree_p (basesize, &sz)
4124 45465540 : || known_le (sz, offset))
4125 7044 : return NULL;
4126 : }
4127 :
4128 22770829 : if (max_size == 0
4129 22770829 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
4130 : return NULL;
4131 :
4132 9621073 : return get_var_base_offset_size_access (base, offset, max_size);
4133 : }
4134 :
4135 : /* Replace the expression EXPR with a scalar replacement if there is one and
4136 : generate other statements to do type conversion or subtree copying if
4137 : necessary. WRITE is true if the expression is being written to (it is on a
4138 : LHS of a statement or output in an assembly statement). STMT_GSI is used to
4139 : place newly created statements before the processed statement, REFRESH_GSI
4140 : is used to place them afterwards - unless the processed statement must end a
4141 : BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
4142 : is then used to continue iteration over the BB. If sra_modify_expr is
4143 : called only once with WRITE equal to true on a given statement, both
4144 : iterator parameters can point to the same one. */
4145 :
4146 : static bool
4147 7860792 : sra_modify_expr (tree *expr, bool write, gimple_stmt_iterator *stmt_gsi,
4148 : gimple_stmt_iterator *refresh_gsi)
4149 : {
4150 7860792 : location_t loc;
4151 7860792 : struct access *access;
4152 7860792 : tree type, bfr, orig_expr;
4153 7860792 : bool partial_cplx_access = false;
4154 :
4155 7860792 : if (TREE_CODE (*expr) == BIT_FIELD_REF
4156 7860792 : && (write || !sra_handled_bf_read_p (*expr)))
4157 : {
4158 597 : bfr = *expr;
4159 597 : expr = &TREE_OPERAND (*expr, 0);
4160 : }
4161 : else
4162 : bfr = NULL_TREE;
4163 :
4164 7860792 : if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
4165 : {
4166 30182 : expr = &TREE_OPERAND (*expr, 0);
4167 30182 : partial_cplx_access = true;
4168 : }
4169 7860792 : access = get_access_for_expr (*expr);
4170 7860792 : if (!access)
4171 : return false;
4172 212049 : type = TREE_TYPE (*expr);
4173 212049 : orig_expr = *expr;
4174 :
4175 212049 : loc = gimple_location (gsi_stmt (*stmt_gsi));
4176 212049 : gimple_stmt_iterator alt_gsi = gsi_none ();
4177 212049 : if (write && stmt_ends_bb_p (gsi_stmt (*stmt_gsi)))
4178 : {
4179 45747 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi)));
4180 45747 : refresh_gsi = &alt_gsi;
4181 : }
4182 :
4183 212049 : if (access->grp_to_be_replaced)
4184 : {
4185 56497 : tree repl = get_access_replacement (access);
4186 : /* If we replace a non-register typed access simply use the original
4187 : access expression to extract the scalar component afterwards.
4188 : This happens if scalarizing a function return value or parameter
4189 : like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
4190 : gcc.c-torture/compile/20011217-1.c.
4191 :
4192 : We also want to use this when accessing a complex or vector which can
4193 : be accessed as a different type too, potentially creating a need for
4194 : type conversion (see PR42196) and when scalarized unions are involved
4195 : in assembler statements (see PR42398). */
4196 56497 : if (!bfr && !useless_type_conversion_p (type, access->type))
4197 : {
4198 52205 : tree ref;
4199 :
4200 52205 : ref = build_ref_for_model (loc, orig_expr, 0, access, stmt_gsi,
4201 : false);
4202 :
4203 52205 : if (partial_cplx_access)
4204 : {
4205 : /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4206 : the case of a write because in such case the replacement cannot
4207 : be a gimple register. In the case of a load, we have to
4208 : differentiate in between a register an non-register
4209 : replacement. */
4210 29 : tree t = build1 (VIEW_CONVERT_EXPR, type, repl);
4211 29 : gcc_checking_assert (!write || access->grp_partial_lhs);
4212 29 : if (!access->grp_partial_lhs)
4213 : {
4214 26 : tree tmp = make_ssa_name (type);
4215 26 : gassign *stmt = gimple_build_assign (tmp, t);
4216 : /* This is always a read. */
4217 26 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4218 26 : t = tmp;
4219 : }
4220 29 : *expr = t;
4221 : }
4222 52176 : else if (write)
4223 : {
4224 15764 : gassign *stmt;
4225 :
4226 15764 : if (access->grp_partial_lhs)
4227 6 : ref = force_gimple_operand_gsi (refresh_gsi, ref, true,
4228 : NULL_TREE, false, GSI_NEW_STMT);
4229 15764 : stmt = gimple_build_assign (repl, ref);
4230 15764 : gimple_set_location (stmt, loc);
4231 15764 : gsi_insert_after (refresh_gsi, stmt, GSI_NEW_STMT);
4232 : }
4233 : else
4234 : {
4235 36412 : if (TREE_READONLY (access->base))
4236 : return false;
4237 :
4238 36379 : gassign *stmt;
4239 36379 : if (access->grp_partial_lhs)
4240 49 : repl = force_gimple_operand_gsi (stmt_gsi, repl, true,
4241 : NULL_TREE, true,
4242 : GSI_SAME_STMT);
4243 36379 : stmt = gimple_build_assign (ref, repl);
4244 36379 : gimple_set_location (stmt, loc);
4245 36379 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4246 : }
4247 : }
4248 : else
4249 : {
4250 : /* If we are going to replace a scalar field in a structure with
4251 : reverse storage order by a stand-alone scalar, we are going to
4252 : effectively byte-swap the scalar and we also need to byte-swap
4253 : the portion of it represented by the bit-field. */
4254 4292 : if (bfr && REF_REVERSE_STORAGE_ORDER (bfr))
4255 : {
4256 0 : REF_REVERSE_STORAGE_ORDER (bfr) = 0;
4257 0 : TREE_OPERAND (bfr, 2)
4258 0 : = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (repl)),
4259 : size_binop (PLUS_EXPR, TREE_OPERAND (bfr, 1),
4260 : TREE_OPERAND (bfr, 2)));
4261 : }
4262 :
4263 4292 : *expr = repl;
4264 : }
4265 :
4266 56464 : sra_stats.exprs++;
4267 : }
4268 155552 : else if (write && access->grp_to_be_debug_replaced)
4269 : {
4270 12 : gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
4271 : NULL_TREE,
4272 : gsi_stmt (*stmt_gsi));
4273 12 : gsi_insert_after (stmt_gsi, ds, GSI_NEW_STMT);
4274 : }
4275 :
4276 212016 : if (access->first_child && !TREE_READONLY (access->base))
4277 : {
4278 151807 : HOST_WIDE_INT start_offset, chunk_size;
4279 151807 : if (bfr
4280 0 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
4281 151807 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
4282 : {
4283 0 : chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
4284 0 : start_offset = access->offset
4285 0 : + tree_to_uhwi (TREE_OPERAND (bfr, 2));
4286 : }
4287 : else
4288 : start_offset = chunk_size = 0;
4289 :
4290 251645 : generate_subtree_copies (access->first_child, orig_expr, access->offset,
4291 : start_offset, chunk_size,
4292 : write ? refresh_gsi : stmt_gsi,
4293 : write, write, loc);
4294 : }
4295 : return true;
4296 : }
4297 :
4298 : /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4299 : reads from its base before and after the call statement given in CALL_GSI
4300 : and return true if any copying took place. Otherwise call sra_modify_expr
4301 : on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4302 : return for the given parameter. */
4303 :
4304 : static bool
4305 8647849 : sra_modify_call_arg (tree *expr, gimple_stmt_iterator *call_gsi,
4306 : gimple_stmt_iterator *refresh_gsi, int flags)
4307 : {
4308 8647849 : if (TREE_CODE (*expr) != ADDR_EXPR)
4309 5677395 : return sra_modify_expr (expr, false, call_gsi, refresh_gsi);
4310 :
4311 2970454 : if (flags & EAF_UNUSED)
4312 : return false;
4313 :
4314 2966789 : tree base = get_base_address (TREE_OPERAND (*expr, 0));
4315 2966789 : if (!DECL_P (base))
4316 : return false;
4317 2237309 : struct access *access = get_access_for_expr (base);
4318 2237309 : if (!access)
4319 : return false;
4320 :
4321 57261 : gimple *stmt = gsi_stmt (*call_gsi);
4322 57261 : location_t loc = gimple_location (stmt);
4323 57261 : generate_subtree_copies (access, base, 0, 0, 0, call_gsi, false, false,
4324 : loc, true);
4325 :
4326 57261 : if (flags & EAF_NO_DIRECT_CLOBBER)
4327 : return true;
4328 :
4329 39849 : if (!stmt_ends_bb_p (stmt))
4330 29076 : generate_subtree_copies (access, base, 0, 0, 0, refresh_gsi, true,
4331 : true, loc, true);
4332 : else
4333 : {
4334 10773 : edge e;
4335 10773 : edge_iterator ei;
4336 32296 : FOR_EACH_EDGE (e, ei, gsi_bb (*call_gsi)->succs)
4337 : {
4338 21523 : gimple_stmt_iterator alt_gsi = gsi_start_edge (e);
4339 21523 : generate_subtree_copies (access, base, 0, 0, 0, &alt_gsi, true,
4340 : true, loc, true);
4341 : }
4342 : }
4343 : return true;
4344 : }
4345 :
4346 : /* Where scalar replacements of the RHS have been written to when a replacement
4347 : of a LHS of an assignments cannot be directly loaded from a replacement of
4348 : the RHS. */
4349 : enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
4350 : SRA_UDH_RIGHT, /* Data flushed to the RHS. */
4351 : SRA_UDH_LEFT }; /* Data flushed to the LHS. */
4352 :
4353 : struct subreplacement_assignment_data
4354 : {
4355 : /* Offset of the access representing the lhs of the assignment. */
4356 : HOST_WIDE_INT left_offset;
4357 :
4358 : /* LHS and RHS of the original assignment. */
4359 : tree assignment_lhs, assignment_rhs;
4360 :
4361 : /* Access representing the rhs of the whole assignment. */
4362 : struct access *top_racc;
4363 :
4364 : /* Stmt iterator used for statement insertions after the original assignment.
4365 : It points to the main GSI used to traverse a BB during function body
4366 : modification. */
4367 : gimple_stmt_iterator *new_gsi;
4368 :
4369 : /* Stmt iterator used for statement insertions before the original
4370 : assignment. Keeps on pointing to the original statement. */
4371 : gimple_stmt_iterator old_gsi;
4372 :
4373 : /* Location of the assignment. */
4374 : location_t loc;
4375 :
4376 : /* Keeps the information whether we have needed to refresh replacements of
4377 : the LHS and from which side of the assignments this takes place. */
4378 : enum unscalarized_data_handling refreshed;
4379 : };
4380 :
4381 : /* Store all replacements in the access tree rooted in TOP_RACC either to their
4382 : base aggregate if there are unscalarized data or directly to LHS of the
4383 : statement that is pointed to by GSI otherwise. */
4384 :
4385 : static void
4386 115801 : handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
4387 : {
4388 115801 : tree src;
4389 : /* If the RHS is a load from a constant, we do not need to (and must not)
4390 : flush replacements to it and can use it directly as if we did. */
4391 115801 : if (TREE_READONLY (sad->top_racc->base))
4392 : {
4393 9 : sad->refreshed = SRA_UDH_RIGHT;
4394 9 : return;
4395 : }
4396 115792 : if (sad->top_racc->grp_unscalarized_data)
4397 : {
4398 26093 : src = sad->assignment_rhs;
4399 26093 : sad->refreshed = SRA_UDH_RIGHT;
4400 : }
4401 : else
4402 : {
4403 89699 : src = sad->assignment_lhs;
4404 89699 : sad->refreshed = SRA_UDH_LEFT;
4405 : }
4406 115792 : generate_subtree_copies (sad->top_racc->first_child, src,
4407 : sad->top_racc->offset, 0, 0,
4408 : &sad->old_gsi, false, false, sad->loc);
4409 : }
4410 :
4411 : /* Try to generate statements to load all sub-replacements in an access subtree
4412 : formed by children of LACC from scalar replacements in the SAD->top_racc
4413 : subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4414 : and load the accesses from it. */
4415 :
4416 : static void
4417 507775 : load_assign_lhs_subreplacements (struct access *lacc,
4418 : struct subreplacement_assignment_data *sad)
4419 : {
4420 1672499 : for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
4421 : {
4422 1164724 : HOST_WIDE_INT offset;
4423 1164724 : offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
4424 :
4425 1164724 : if (lacc->grp_to_be_replaced)
4426 : {
4427 959766 : struct access *racc;
4428 959766 : gassign *stmt;
4429 959766 : tree rhs;
4430 :
4431 959766 : racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
4432 959766 : if (racc && racc->grp_to_be_replaced)
4433 : {
4434 933733 : rhs = get_access_replacement (racc);
4435 933733 : bool vce = false;
4436 933733 : if (!useless_type_conversion_p (lacc->type, racc->type))
4437 : {
4438 31 : rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4439 : lacc->type, rhs);
4440 31 : vce = true;
4441 : }
4442 :
4443 933733 : if (lacc->grp_partial_lhs && (vce || racc->grp_partial_lhs))
4444 3 : rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
4445 : NULL_TREE, true, GSI_SAME_STMT);
4446 : }
4447 : else
4448 : {
4449 : /* No suitable access on the right hand side, need to load from
4450 : the aggregate. See if we have to update it first... */
4451 26033 : if (sad->refreshed == SRA_UDH_NONE)
4452 13092 : handle_unscalarized_data_in_subtree (sad);
4453 :
4454 26033 : if (sad->refreshed == SRA_UDH_LEFT)
4455 562 : rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
4456 562 : lacc->offset - sad->left_offset,
4457 : lacc, sad->new_gsi, true);
4458 : else
4459 25471 : rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
4460 25471 : lacc->offset - sad->left_offset,
4461 : lacc, sad->new_gsi, true);
4462 26033 : if (lacc->grp_partial_lhs)
4463 1 : rhs = force_gimple_operand_gsi (sad->new_gsi,
4464 : rhs, true, NULL_TREE,
4465 : false, GSI_NEW_STMT);
4466 : }
4467 :
4468 959766 : stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
4469 959766 : gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
4470 959766 : gimple_set_location (stmt, sad->loc);
4471 959766 : update_stmt (stmt);
4472 959766 : sra_stats.subreplacements++;
4473 : }
4474 : else
4475 : {
4476 204958 : if (sad->refreshed == SRA_UDH_NONE
4477 28254 : && lacc->grp_read && !lacc->grp_covered)
4478 24 : handle_unscalarized_data_in_subtree (sad);
4479 :
4480 204958 : if (lacc && lacc->grp_to_be_debug_replaced)
4481 : {
4482 118530 : gdebug *ds;
4483 118530 : tree drhs;
4484 118530 : struct access *racc = find_access_in_subtree (sad->top_racc,
4485 : offset,
4486 : lacc->size);
4487 :
4488 118530 : if (racc && racc->grp_to_be_replaced)
4489 : {
4490 118385 : if (racc->grp_write || constant_decl_p (racc->base))
4491 115086 : drhs = get_access_replacement (racc);
4492 : else
4493 : drhs = NULL;
4494 : }
4495 145 : else if (sad->refreshed == SRA_UDH_LEFT)
4496 0 : drhs = build_debug_ref_for_model (sad->loc, lacc->base,
4497 : lacc->offset, lacc);
4498 145 : else if (sad->refreshed == SRA_UDH_RIGHT)
4499 143 : drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
4500 : offset, lacc);
4501 : else
4502 : drhs = NULL_TREE;
4503 115086 : if (drhs
4504 115229 : && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
4505 2273 : drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4506 : lacc->type, drhs);
4507 118530 : ds = gimple_build_debug_bind (get_access_replacement (lacc),
4508 : drhs, gsi_stmt (sad->old_gsi));
4509 118530 : gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
4510 : }
4511 : }
4512 :
4513 1164724 : if (lacc->first_child)
4514 37920 : load_assign_lhs_subreplacements (lacc, sad);
4515 : }
4516 507775 : }
4517 :
4518 : /* Result code for SRA assignment modification. */
4519 : enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
4520 : SRA_AM_MODIFIED, /* stmt changed but not
4521 : removed */
4522 : SRA_AM_REMOVED }; /* stmt eliminated */
4523 :
4524 : /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4525 : to the assignment and GSI is the statement iterator pointing at it. Returns
4526 : the same values as sra_modify_assign. */
4527 :
4528 : static enum assignment_mod_result
4529 3078466 : sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4530 : {
4531 3078466 : tree lhs = gimple_assign_lhs (stmt);
4532 3078466 : struct access *acc = get_access_for_expr (lhs);
4533 3078466 : if (!acc)
4534 : return SRA_AM_NONE;
4535 1234685 : location_t loc = gimple_location (stmt);
4536 :
4537 1234685 : if (gimple_clobber_p (stmt))
4538 : {
4539 : /* Clobber the replacement variable. */
4540 1083945 : clobber_subtree (acc, gsi, !acc->grp_covered, loc);
4541 : /* Remove clobbers of fully scalarized variables, they are dead. */
4542 1083945 : if (acc->grp_covered)
4543 : {
4544 826765 : unlink_stmt_vdef (stmt);
4545 826765 : gsi_remove (gsi, true);
4546 826765 : release_defs (stmt);
4547 826765 : return SRA_AM_REMOVED;
4548 : }
4549 : else
4550 : return SRA_AM_MODIFIED;
4551 : }
4552 :
4553 150740 : if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
4554 : {
4555 : /* I have never seen this code path trigger but if it can happen the
4556 : following should handle it gracefully. */
4557 0 : if (access_has_children_p (acc))
4558 0 : generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
4559 : true, true, loc);
4560 : return SRA_AM_MODIFIED;
4561 : }
4562 :
4563 150740 : if (acc->grp_covered)
4564 : {
4565 82030 : init_subtree_with_zero (acc, gsi, false, loc);
4566 82030 : unlink_stmt_vdef (stmt);
4567 82030 : gsi_remove (gsi, true);
4568 82030 : release_defs (stmt);
4569 82030 : return SRA_AM_REMOVED;
4570 : }
4571 : else
4572 : {
4573 68710 : init_subtree_with_zero (acc, gsi, true, loc);
4574 68710 : return SRA_AM_MODIFIED;
4575 : }
4576 : }
4577 :
4578 : /* Create and return a new suitable default definition SSA_NAME for RACC which
4579 : is an access describing an uninitialized part of an aggregate that is being
4580 : loaded. REG_TREE is used instead of the actual RACC type if that is not of
4581 : a gimple register type. */
4582 :
4583 : static tree
4584 552 : get_repl_default_def_ssa_name (struct access *racc, tree reg_type)
4585 : {
4586 552 : gcc_checking_assert (!racc->grp_to_be_replaced
4587 : && !racc->grp_to_be_debug_replaced);
4588 552 : if (!racc->replacement_decl)
4589 552 : racc->replacement_decl = create_access_replacement (racc, reg_type);
4590 552 : return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
4591 : }
4592 :
4593 :
4594 : /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4595 : of accesses within a subtree ACCESS; all its children, siblings and their
4596 : children are to be processed.
4597 : GSI is a statement iterator used to place the new statements. */
4598 : static void
4599 34290 : generate_subtree_deferred_init (struct access *access,
4600 : tree init_type,
4601 : tree decl_name,
4602 : gimple_stmt_iterator *gsi,
4603 : location_t loc)
4604 : {
4605 79094 : do
4606 : {
4607 79094 : if (access->grp_to_be_replaced)
4608 : {
4609 62226 : tree repl = get_access_replacement (access);
4610 62226 : gimple *call
4611 62226 : = gimple_build_call_internal (IFN_DEFERRED_INIT, 3,
4612 62226 : TYPE_SIZE_UNIT (TREE_TYPE (repl)),
4613 : init_type, decl_name);
4614 62226 : gimple_call_set_lhs (call, repl);
4615 62226 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
4616 62226 : update_stmt (call);
4617 62226 : gimple_set_location (call, loc);
4618 62226 : sra_stats.subtree_deferred_init++;
4619 : }
4620 79094 : if (access->first_child)
4621 4836 : generate_subtree_deferred_init (access->first_child, init_type,
4622 : decl_name, gsi, loc);
4623 :
4624 79094 : access = access ->next_sibling;
4625 : }
4626 79094 : while (access);
4627 34290 : }
4628 :
4629 : /* For a call to .DEFERRED_INIT:
4630 : var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4631 : examine the LHS variable VAR and replace it with a scalar replacement if
4632 : there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4633 : the corresponding scalar relacement variable. Examine the subtree and
4634 : do the scalar replacements in the subtree too. STMT is the call, GSI is
4635 : the statement iterator to place newly created statement. */
4636 :
4637 : static enum assignment_mod_result
4638 117829 : sra_modify_deferred_init (gimple *stmt, gimple_stmt_iterator *gsi)
4639 : {
4640 117829 : tree lhs = gimple_call_lhs (stmt);
4641 117829 : tree init_type = gimple_call_arg (stmt, 1);
4642 117829 : tree decl_name = gimple_call_arg (stmt, 2);
4643 :
4644 117829 : struct access *lhs_access = get_access_for_expr (lhs);
4645 117829 : if (!lhs_access)
4646 : return SRA_AM_NONE;
4647 :
4648 44884 : location_t loc = gimple_location (stmt);
4649 :
4650 44884 : if (lhs_access->grp_to_be_replaced)
4651 : {
4652 14861 : tree lhs_repl = get_access_replacement (lhs_access);
4653 14861 : gimple_call_set_lhs (stmt, lhs_repl);
4654 14861 : tree arg0_repl = TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl));
4655 14861 : gimple_call_set_arg (stmt, 0, arg0_repl);
4656 14861 : sra_stats.deferred_init++;
4657 14861 : gcc_assert (!lhs_access->first_child);
4658 : return SRA_AM_MODIFIED;
4659 : }
4660 :
4661 30023 : if (lhs_access->first_child)
4662 29454 : generate_subtree_deferred_init (lhs_access->first_child,
4663 : init_type, decl_name, gsi, loc);
4664 30023 : if (lhs_access->grp_covered)
4665 : {
4666 18969 : unlink_stmt_vdef (stmt);
4667 18969 : gsi_remove (gsi, true);
4668 18969 : release_defs (stmt);
4669 18969 : return SRA_AM_REMOVED;
4670 : }
4671 :
4672 : return SRA_AM_MODIFIED;
4673 : }
4674 :
4675 : /* Examine both sides of the assignment statement pointed to by STMT, replace
4676 : them with a scalare replacement if there is one and generate copying of
4677 : replacements if scalarized aggregates have been used in the assignment. GSI
4678 : is used to hold generated statements for type conversions and subtree
4679 : copying. */
4680 :
4681 : static enum assignment_mod_result
4682 26646654 : sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4683 : {
4684 26646654 : struct access *lacc, *racc;
4685 26646654 : tree lhs, rhs;
4686 26646654 : bool modify_this_stmt = false;
4687 26646654 : bool force_gimple_rhs = false;
4688 26646654 : location_t loc;
4689 26646654 : gimple_stmt_iterator orig_gsi = *gsi;
4690 :
4691 26646654 : if (!gimple_assign_single_p (stmt))
4692 : return SRA_AM_NONE;
4693 20819760 : lhs = gimple_assign_lhs (stmt);
4694 20819760 : rhs = gimple_assign_rhs1 (stmt);
4695 :
4696 20819760 : if (TREE_CODE (rhs) == CONSTRUCTOR)
4697 3078466 : return sra_modify_constructor_assign (stmt, gsi);
4698 :
4699 17730558 : if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
4700 17726549 : || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
4701 17711112 : || (TREE_CODE (rhs) == BIT_FIELD_REF && !sra_handled_bf_read_p (rhs))
4702 35452402 : || TREE_CODE (lhs) == BIT_FIELD_REF)
4703 : {
4704 30779 : modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
4705 : false, gsi, gsi);
4706 30779 : modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
4707 : true, gsi, gsi);
4708 30779 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4709 : }
4710 :
4711 17710515 : lacc = get_access_for_expr (lhs);
4712 17710515 : racc = get_access_for_expr (rhs);
4713 17710515 : if (!lacc && !racc)
4714 : return SRA_AM_NONE;
4715 : /* Avoid modifying initializations of constant-pool replacements. */
4716 7262876 : if (racc && (racc->replacement_decl == lhs))
4717 : return SRA_AM_NONE;
4718 :
4719 7257895 : loc = gimple_location (stmt);
4720 7257895 : if (lacc && lacc->grp_to_be_replaced)
4721 : {
4722 2029856 : lhs = get_access_replacement (lacc);
4723 2029856 : gimple_assign_set_lhs (stmt, lhs);
4724 2029856 : modify_this_stmt = true;
4725 2029856 : if (lacc->grp_partial_lhs)
4726 87 : force_gimple_rhs = true;
4727 2029856 : sra_stats.exprs++;
4728 : }
4729 :
4730 7257895 : if (racc && racc->grp_to_be_replaced)
4731 : {
4732 3307952 : rhs = get_access_replacement (racc);
4733 3307952 : modify_this_stmt = true;
4734 3307952 : if (racc->grp_partial_lhs)
4735 879 : force_gimple_rhs = true;
4736 3307952 : sra_stats.exprs++;
4737 : }
4738 1123991 : else if (racc
4739 1123991 : && !racc->grp_unscalarized_data
4740 897513 : && !racc->grp_unscalarizable_region
4741 897511 : && TREE_CODE (lhs) == SSA_NAME
4742 552 : && !access_has_replacements_p (racc))
4743 : {
4744 552 : rhs = get_repl_default_def_ssa_name (racc, TREE_TYPE (lhs));
4745 552 : modify_this_stmt = true;
4746 552 : sra_stats.exprs++;
4747 : }
4748 :
4749 3308504 : if (modify_this_stmt
4750 7257895 : && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4751 : {
4752 : /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4753 : ??? This should move to fold_stmt which we simply should
4754 : call after building a VIEW_CONVERT_EXPR here. */
4755 610792 : if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
4756 172974 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs)) == racc->reverse
4757 478875 : && !contains_bitfld_component_ref_p (lhs))
4758 : {
4759 172973 : lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
4760 172973 : gimple_assign_set_lhs (stmt, lhs);
4761 : }
4762 132929 : else if (lacc
4763 101635 : && AGGREGATE_TYPE_P (TREE_TYPE (rhs))
4764 69718 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs)) == lacc->reverse
4765 202647 : && !contains_vce_or_bfcref_p (rhs))
4766 69094 : rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
4767 :
4768 305902 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4769 : {
4770 63835 : rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
4771 63835 : if (is_gimple_reg_type (TREE_TYPE (lhs))
4772 63835 : && TREE_CODE (lhs) != SSA_NAME)
4773 7257895 : force_gimple_rhs = true;
4774 : }
4775 : }
4776 :
4777 7257895 : if (lacc && lacc->grp_to_be_debug_replaced)
4778 : {
4779 158368 : tree dlhs = get_access_replacement (lacc);
4780 158368 : tree drhs = unshare_expr (rhs);
4781 158368 : if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
4782 : {
4783 10588 : if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
4784 5352 : && !contains_vce_or_bfcref_p (drhs))
4785 58 : drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
4786 5294 : if (drhs
4787 10588 : && !useless_type_conversion_p (TREE_TYPE (dlhs),
4788 5294 : TREE_TYPE (drhs)))
4789 5236 : drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
4790 5236 : TREE_TYPE (dlhs), drhs);
4791 : }
4792 158368 : gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
4793 158368 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4794 : }
4795 :
4796 : /* From this point on, the function deals with assignments in between
4797 : aggregates when at least one has scalar reductions of some of its
4798 : components. There are three possible scenarios: Both the LHS and RHS have
4799 : to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4800 :
4801 : In the first case, we would like to load the LHS components from RHS
4802 : components whenever possible. If that is not possible, we would like to
4803 : read it directly from the RHS (after updating it by storing in it its own
4804 : components). If there are some necessary unscalarized data in the LHS,
4805 : those will be loaded by the original assignment too. If neither of these
4806 : cases happen, the original statement can be removed. Most of this is done
4807 : by load_assign_lhs_subreplacements.
4808 :
4809 : In the second case, we would like to store all RHS scalarized components
4810 : directly into LHS and if they cover the aggregate completely, remove the
4811 : statement too. In the third case, we want the LHS components to be loaded
4812 : directly from the RHS (DSE will remove the original statement if it
4813 : becomes redundant).
4814 :
4815 : This is a bit complex but manageable when types match and when unions do
4816 : not cause confusion in a way that we cannot really load a component of LHS
4817 : from the RHS or vice versa (the access representing this level can have
4818 : subaccesses that are accessible only through a different union field at a
4819 : higher level - different from the one used in the examined expression).
4820 : Unions are fun.
4821 :
4822 : Therefore, I specially handle a fourth case, happening when there is a
4823 : specific type cast or it is impossible to locate a scalarized subaccess on
4824 : the other side of the expression. If that happens, I simply "refresh" the
4825 : RHS by storing in it is scalarized components leave the original statement
4826 : there to do the copying and then load the scalar replacements of the LHS.
4827 : This is what the first branch does. */
4828 :
4829 7257895 : if (modify_this_stmt
4830 2058309 : || gimple_has_volatile_ops (stmt)
4831 2057929 : || contains_vce_or_bfcref_p (rhs)
4832 1876897 : || contains_vce_or_bfcref_p (lhs)
4833 9131930 : || stmt_ends_bb_p (stmt))
4834 : {
4835 : /* No need to copy into a constant, it comes pre-initialized. */
4836 5481680 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4837 21889 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4838 : gsi, false, false, loc);
4839 5459791 : if (access_has_children_p (lacc))
4840 : {
4841 252218 : gimple_stmt_iterator alt_gsi = gsi_none ();
4842 252218 : if (stmt_ends_bb_p (stmt))
4843 : {
4844 75067 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
4845 75067 : gsi = &alt_gsi;
4846 : }
4847 252218 : generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
4848 : gsi, true, true, loc);
4849 : }
4850 5459791 : sra_stats.separate_lhs_rhs_handling++;
4851 :
4852 : /* This gimplification must be done after generate_subtree_copies,
4853 : lest we insert the subtree copies in the middle of the gimplified
4854 : sequence. */
4855 5459791 : if (force_gimple_rhs)
4856 33490 : rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
4857 : true, GSI_SAME_STMT);
4858 5459791 : if (gimple_assign_rhs1 (stmt) != rhs)
4859 : {
4860 3410031 : modify_this_stmt = true;
4861 3410031 : gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
4862 3410031 : gcc_assert (stmt == gsi_stmt (orig_gsi));
4863 : }
4864 :
4865 2049760 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4866 : }
4867 : else
4868 : {
4869 2514370 : if (access_has_children_p (lacc)
4870 1798115 : && access_has_children_p (racc)
4871 : /* When an access represents an unscalarizable region, it usually
4872 : represents accesses with variable offset and thus must not be used
4873 : to generate new memory accesses. */
4874 469866 : && !lacc->grp_unscalarizable_region
4875 469861 : && !racc->grp_unscalarizable_region)
4876 : {
4877 469855 : struct subreplacement_assignment_data sad;
4878 :
4879 469855 : sad.left_offset = lacc->offset;
4880 469855 : sad.assignment_lhs = lhs;
4881 469855 : sad.assignment_rhs = rhs;
4882 469855 : sad.top_racc = racc;
4883 469855 : sad.old_gsi = *gsi;
4884 469855 : sad.new_gsi = gsi;
4885 469855 : sad.loc = gimple_location (stmt);
4886 469855 : sad.refreshed = SRA_UDH_NONE;
4887 :
4888 469855 : if (lacc->grp_read && !lacc->grp_covered)
4889 102685 : handle_unscalarized_data_in_subtree (&sad);
4890 :
4891 469855 : load_assign_lhs_subreplacements (lacc, &sad);
4892 469855 : if (sad.refreshed != SRA_UDH_RIGHT)
4893 : {
4894 443753 : gsi_next (gsi);
4895 443753 : unlink_stmt_vdef (stmt);
4896 443753 : gsi_remove (&sad.old_gsi, true);
4897 443753 : release_defs (stmt);
4898 443753 : sra_stats.deleted++;
4899 443753 : return SRA_AM_REMOVED;
4900 : }
4901 : }
4902 : else
4903 : {
4904 1328249 : if (access_has_children_p (racc)
4905 496752 : && !racc->grp_unscalarized_data
4906 435497 : && TREE_CODE (lhs) != SSA_NAME)
4907 : {
4908 435496 : if (dump_file)
4909 : {
4910 5 : fprintf (dump_file, "Removing load: ");
4911 5 : print_gimple_stmt (dump_file, stmt, 0);
4912 : }
4913 435496 : generate_subtree_copies (racc->first_child, lhs,
4914 : racc->offset, 0, 0, gsi,
4915 : false, false, loc);
4916 435496 : gcc_assert (stmt == gsi_stmt (*gsi));
4917 435496 : unlink_stmt_vdef (stmt);
4918 435496 : gsi_remove (gsi, true);
4919 435496 : release_defs (stmt);
4920 435496 : sra_stats.deleted++;
4921 435496 : return SRA_AM_REMOVED;
4922 : }
4923 : /* Restore the aggregate RHS from its components so the
4924 : prevailing aggregate copy does the right thing. */
4925 954009 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4926 61241 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4927 : gsi, false, false, loc);
4928 : /* Re-load the components of the aggregate copy destination.
4929 : But use the RHS aggregate to load from to expose more
4930 : optimization opportunities. */
4931 892753 : if (access_has_children_p (lacc))
4932 : {
4933 246406 : generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
4934 : 0, 0, gsi, true, true, loc);
4935 246406 : if (lacc->grp_covered)
4936 : {
4937 181623 : unlink_stmt_vdef (stmt);
4938 181623 : gsi_remove (& orig_gsi, true);
4939 181623 : release_defs (stmt);
4940 181623 : sra_stats.deleted++;
4941 181623 : return SRA_AM_REMOVED;
4942 : }
4943 : }
4944 : }
4945 :
4946 : return SRA_AM_NONE;
4947 : }
4948 : }
4949 :
4950 : /* Set any scalar replacements of values in the constant pool to the initial
4951 : value of the constant. (Constant-pool decls like *.LC0 have effectively
4952 : been initialized before the program starts, we must do the same for their
4953 : replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4954 : the function's entry block. */
4955 :
4956 : static void
4957 458524 : initialize_constant_pool_replacements (void)
4958 : {
4959 458524 : gimple_seq seq = NULL;
4960 458524 : gimple_stmt_iterator gsi = gsi_start (seq);
4961 458524 : bitmap_iterator bi;
4962 458524 : unsigned i;
4963 :
4964 2332410 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
4965 : {
4966 1873886 : tree var = candidate (i);
4967 1873886 : if (!constant_decl_p (var))
4968 1873805 : continue;
4969 :
4970 81 : struct access *access = get_first_repr_for_decl (var);
4971 :
4972 6386 : while (access)
4973 : {
4974 6224 : if (access->replacement_decl)
4975 : {
4976 4981 : gassign *stmt
4977 4981 : = gimple_build_assign (get_access_replacement (access),
4978 : unshare_expr (access->expr));
4979 4981 : if (dump_file && (dump_flags & TDF_DETAILS))
4980 : {
4981 0 : fprintf (dump_file, "Generating constant initializer: ");
4982 0 : print_gimple_stmt (dump_file, stmt, 0);
4983 0 : fprintf (dump_file, "\n");
4984 : }
4985 4981 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
4986 4981 : update_stmt (stmt);
4987 : }
4988 :
4989 6224 : if (access->first_child)
4990 : access = access->first_child;
4991 4981 : else if (access->next_sibling)
4992 : access = access->next_sibling;
4993 : else
4994 : {
4995 2351 : while (access->parent && !access->next_sibling)
4996 : access = access->parent;
4997 1108 : if (access->next_sibling)
4998 : access = access->next_sibling;
4999 : else
5000 81 : access = access->next_grp;
5001 : }
5002 : }
5003 : }
5004 :
5005 458524 : seq = gsi_seq (gsi);
5006 458524 : if (seq)
5007 76 : gsi_insert_seq_on_edge_immediate (
5008 76 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5009 458524 : }
5010 :
5011 : /* Traverse the function body and all modifications as decided in
5012 : analyze_all_variable_accesses. Return true iff the CFG has been
5013 : changed. */
5014 :
5015 : static bool
5016 458524 : sra_modify_function_body (void)
5017 : {
5018 458524 : bool cfg_changed = false;
5019 458524 : basic_block bb;
5020 :
5021 458524 : initialize_constant_pool_replacements ();
5022 :
5023 10303009 : FOR_EACH_BB_FN (bb, cfun)
5024 : {
5025 9844485 : gimple_stmt_iterator gsi = gsi_start_bb (bb);
5026 88249902 : while (!gsi_end_p (gsi))
5027 : {
5028 78405417 : gimple *stmt = gsi_stmt (gsi);
5029 78405417 : enum assignment_mod_result assign_result;
5030 78405417 : bool modified = false, deleted = false;
5031 78405417 : tree *t;
5032 78405417 : unsigned i;
5033 :
5034 78405417 : switch (gimple_code (stmt))
5035 : {
5036 456785 : case GIMPLE_RETURN:
5037 456785 : t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
5038 456785 : if (*t != NULL_TREE)
5039 297253 : modified |= sra_modify_expr (t, false, &gsi, &gsi);
5040 : break;
5041 :
5042 26646654 : case GIMPLE_ASSIGN:
5043 26646654 : assign_result = sra_modify_assign (stmt, &gsi);
5044 26646654 : modified |= assign_result == SRA_AM_MODIFIED;
5045 26646654 : deleted = assign_result == SRA_AM_REMOVED;
5046 26646654 : break;
5047 :
5048 4472469 : case GIMPLE_CALL:
5049 : /* Handle calls to .DEFERRED_INIT specially. */
5050 4472469 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
5051 : {
5052 117829 : assign_result = sra_modify_deferred_init (stmt, &gsi);
5053 117829 : modified |= assign_result == SRA_AM_MODIFIED;
5054 117829 : deleted = assign_result == SRA_AM_REMOVED;
5055 : }
5056 : else
5057 : {
5058 4354640 : gcall *call = as_a <gcall *> (stmt);
5059 4354640 : gimple_stmt_iterator call_gsi = gsi;
5060 :
5061 : /* Operands must be processed before the lhs. */
5062 12973161 : for (i = 0; i < gimple_call_num_args (call); i++)
5063 : {
5064 8618521 : int flags = gimple_call_arg_flags (call, i);
5065 8618521 : t = gimple_call_arg_ptr (call, i);
5066 8618521 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi, flags);
5067 : }
5068 4354640 : if (gimple_call_chain (call))
5069 : {
5070 29328 : t = gimple_call_chain_ptr (call);
5071 29328 : int flags = gimple_call_static_chain_flags (call);
5072 29328 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi,
5073 : flags);
5074 : }
5075 4354640 : if (gimple_call_lhs (call))
5076 : {
5077 1814912 : t = gimple_call_lhs_ptr (call);
5078 1814912 : modified |= sra_modify_expr (t, true, &call_gsi, &gsi);
5079 : }
5080 : }
5081 : break;
5082 :
5083 7805 : case GIMPLE_ASM:
5084 7805 : {
5085 7805 : gimple_stmt_iterator stmt_gsi = gsi;
5086 7805 : gasm *asm_stmt = as_a <gasm *> (stmt);
5087 20295 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5088 : {
5089 4685 : t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5090 4685 : modified |= sra_modify_expr (t, false, &stmt_gsi, &gsi);
5091 : }
5092 12794 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5093 : {
5094 4989 : t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5095 4989 : modified |= sra_modify_expr (t, true, &stmt_gsi, &gsi);
5096 : }
5097 : }
5098 7805 : break;
5099 :
5100 : default:
5101 : break;
5102 : }
5103 :
5104 31424181 : if (modified)
5105 : {
5106 5798330 : update_stmt (stmt);
5107 5798330 : if (maybe_clean_eh_stmt (stmt)
5108 5798330 : && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5109 : cfg_changed = true;
5110 : }
5111 78405417 : if (!deleted)
5112 76416781 : gsi_next (&gsi);
5113 : }
5114 : }
5115 :
5116 458524 : gsi_commit_edge_inserts ();
5117 458524 : return cfg_changed;
5118 : }
5119 :
5120 : /* Generate statements initializing scalar replacements of parts of function
5121 : parameters. */
5122 :
5123 : static void
5124 458524 : initialize_parameter_reductions (void)
5125 : {
5126 458524 : gimple_stmt_iterator gsi;
5127 458524 : gimple_seq seq = NULL;
5128 458524 : tree parm;
5129 :
5130 458524 : gsi = gsi_start (seq);
5131 458524 : for (parm = DECL_ARGUMENTS (current_function_decl);
5132 1387275 : parm;
5133 928751 : parm = DECL_CHAIN (parm))
5134 : {
5135 928751 : vec<access_p> *access_vec;
5136 928751 : struct access *access;
5137 :
5138 928751 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
5139 860594 : continue;
5140 68157 : access_vec = get_base_access_vector (parm);
5141 68157 : if (!access_vec)
5142 0 : continue;
5143 :
5144 68157 : for (access = (*access_vec)[0];
5145 173626 : access;
5146 105469 : access = access->next_grp)
5147 105469 : generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
5148 105469 : EXPR_LOCATION (parm));
5149 : }
5150 :
5151 458524 : seq = gsi_seq (gsi);
5152 458524 : if (seq)
5153 53945 : gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5154 458524 : }
5155 :
5156 : /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
5157 : it reveals there are components of some aggregates to be scalarized, it runs
5158 : the required transformations. */
5159 : static unsigned int
5160 3603288 : perform_intra_sra (void)
5161 : {
5162 3603288 : int ret = 0;
5163 3603288 : sra_initialize ();
5164 :
5165 3603288 : if (!find_var_candidates ())
5166 2776424 : goto out;
5167 :
5168 826864 : if (!scan_function ())
5169 56893 : goto out;
5170 :
5171 769971 : if (!analyze_all_variable_accesses ())
5172 311447 : goto out;
5173 :
5174 458524 : if (sra_modify_function_body ())
5175 : ret = TODO_update_ssa | TODO_cleanup_cfg;
5176 : else
5177 458502 : ret = TODO_update_ssa;
5178 458524 : initialize_parameter_reductions ();
5179 :
5180 458524 : statistics_counter_event (cfun, "Scalar replacements created",
5181 : sra_stats.replacements);
5182 458524 : statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
5183 458524 : statistics_counter_event (cfun, "Subtree copy stmts",
5184 : sra_stats.subtree_copies);
5185 458524 : statistics_counter_event (cfun, "Subreplacement stmts",
5186 : sra_stats.subreplacements);
5187 458524 : statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
5188 458524 : statistics_counter_event (cfun, "Separate LHS and RHS handling",
5189 : sra_stats.separate_lhs_rhs_handling);
5190 :
5191 3603288 : out:
5192 3603288 : sra_deinitialize ();
5193 3603288 : return ret;
5194 : }
5195 :
5196 : /* Perform early intraprocedural SRA. */
5197 : static unsigned int
5198 2541339 : early_intra_sra (void)
5199 : {
5200 2541339 : sra_mode = SRA_MODE_EARLY_INTRA;
5201 0 : return perform_intra_sra ();
5202 : }
5203 :
5204 : /* Perform "late" intraprocedural SRA. */
5205 : static unsigned int
5206 1061949 : late_intra_sra (void)
5207 : {
5208 1061949 : sra_mode = SRA_MODE_INTRA;
5209 0 : return perform_intra_sra ();
5210 : }
5211 :
5212 :
5213 : static bool
5214 3607295 : gate_intra_sra (void)
5215 : {
5216 3607295 : return flag_tree_sra != 0 && dbg_cnt (tree_sra);
5217 : }
5218 :
5219 :
5220 : namespace {
5221 :
5222 : const pass_data pass_data_sra_early =
5223 : {
5224 : GIMPLE_PASS, /* type */
5225 : "esra", /* name */
5226 : OPTGROUP_NONE, /* optinfo_flags */
5227 : TV_TREE_SRA, /* tv_id */
5228 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5229 : 0, /* properties_provided */
5230 : 0, /* properties_destroyed */
5231 : 0, /* todo_flags_start */
5232 : TODO_update_ssa, /* todo_flags_finish */
5233 : };
5234 :
5235 : class pass_sra_early : public gimple_opt_pass
5236 : {
5237 : public:
5238 294587 : pass_sra_early (gcc::context *ctxt)
5239 589174 : : gimple_opt_pass (pass_data_sra_early, ctxt)
5240 : {}
5241 :
5242 : /* opt_pass methods: */
5243 2544882 : bool gate (function *) final override { return gate_intra_sra (); }
5244 2541339 : unsigned int execute (function *) final override
5245 : {
5246 2541339 : return early_intra_sra ();
5247 : }
5248 :
5249 : }; // class pass_sra_early
5250 :
5251 : } // anon namespace
5252 :
5253 : gimple_opt_pass *
5254 294587 : make_pass_sra_early (gcc::context *ctxt)
5255 : {
5256 294587 : return new pass_sra_early (ctxt);
5257 : }
5258 :
5259 : namespace {
5260 :
5261 : const pass_data pass_data_sra =
5262 : {
5263 : GIMPLE_PASS, /* type */
5264 : "sra", /* name */
5265 : OPTGROUP_NONE, /* optinfo_flags */
5266 : TV_TREE_SRA, /* tv_id */
5267 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5268 : 0, /* properties_provided */
5269 : 0, /* properties_destroyed */
5270 : TODO_update_address_taken, /* todo_flags_start */
5271 : TODO_update_ssa, /* todo_flags_finish */
5272 : };
5273 :
5274 : class pass_sra : public gimple_opt_pass
5275 : {
5276 : public:
5277 294587 : pass_sra (gcc::context *ctxt)
5278 589174 : : gimple_opt_pass (pass_data_sra, ctxt)
5279 : {}
5280 :
5281 : /* opt_pass methods: */
5282 1062413 : bool gate (function *) final override { return gate_intra_sra (); }
5283 1061949 : unsigned int execute (function *) final override { return late_intra_sra (); }
5284 :
5285 : }; // class pass_sra
5286 :
5287 : } // anon namespace
5288 :
5289 : gimple_opt_pass *
5290 294587 : make_pass_sra (gcc::context *ctxt)
5291 : {
5292 294587 : return new pass_sra (ctxt);
5293 : }
5294 :
5295 :
5296 : /* If type T cannot be totally scalarized, return false. Otherwise return true
5297 : and push to the vector within PC offsets and lengths of all padding in the
5298 : type as total scalarization would encounter it. */
5299 :
5300 : static bool
5301 26348 : check_ts_and_push_padding_to_vec (tree type, sra_padding_collecting *pc)
5302 : {
5303 26348 : if (!totally_scalarizable_type_p (type, true /* optimistic value */,
5304 : 0, pc))
5305 : return false;
5306 :
5307 25402 : pc->record_padding (tree_to_shwi (TYPE_SIZE (type)));
5308 25402 : return true;
5309 : }
5310 :
5311 : /* Given two types in an assignment, return true either if any one cannot be
5312 : totally scalarized or if they have padding (i.e. not copied bits) */
5313 :
5314 : bool
5315 13647 : sra_total_scalarization_would_copy_same_data_p (tree t1, tree t2)
5316 : {
5317 13647 : sra_padding_collecting p1;
5318 13647 : if (!check_ts_and_push_padding_to_vec (t1, &p1))
5319 : return true;
5320 :
5321 12701 : sra_padding_collecting p2;
5322 12701 : if (!check_ts_and_push_padding_to_vec (t2, &p2))
5323 : return true;
5324 :
5325 12701 : unsigned l = p1.m_padding.length ();
5326 25402 : if (l != p2.m_padding.length ())
5327 : return false;
5328 15484 : for (unsigned i = 0; i < l; i++)
5329 2786 : if (p1.m_padding[i].first != p2.m_padding[i].first
5330 2786 : || p1.m_padding[i].second != p2.m_padding[i].second)
5331 : return false;
5332 :
5333 : return true;
5334 12701 : }
5335 :
|
