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