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