Branch data 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-2024 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 : :
104 : : /* Enumeration of all aggregate reductions we can do. */
105 : : enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
106 : : SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
107 : : SRA_MODE_INTRA }; /* late intraprocedural SRA */
108 : :
109 : : /* Global variable describing which aggregate reduction we are performing at
110 : : the moment. */
111 : : static enum sra_mode sra_mode;
112 : :
113 : : struct assign_link;
114 : :
115 : : /* ACCESS represents each access to an aggregate variable (as a whole or a
116 : : part). It can also represent a group of accesses that refer to exactly the
117 : : same fragment of an aggregate (i.e. those that have exactly the same offset
118 : : and size). Such representatives for a single aggregate, once determined,
119 : : are linked in a linked list and have the group fields set.
120 : :
121 : : Moreover, when doing intraprocedural SRA, a tree is built from those
122 : : representatives (by the means of first_child and next_sibling pointers), in
123 : : which all items in a subtree are "within" the root, i.e. their offset is
124 : : greater or equal to offset of the root and offset+size is smaller or equal
125 : : to offset+size of the root. Children of an access are sorted by offset.
126 : :
127 : : Note that accesses to parts of vector and complex number types always
128 : : represented by an access to the whole complex number or a vector. It is a
129 : : duty of the modifying functions to replace them appropriately. */
130 : :
131 : : struct access
132 : : {
133 : : /* Values returned by `get_ref_base_and_extent' for each component reference
134 : : If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
135 : : `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
136 : : HOST_WIDE_INT offset;
137 : : HOST_WIDE_INT size;
138 : : tree base;
139 : :
140 : : /* Expression. It is context dependent so do not use it to create new
141 : : expressions to access the original aggregate. See PR 42154 for a
142 : : testcase. */
143 : : tree expr;
144 : : /* Type. */
145 : : tree type;
146 : :
147 : : /* The statement this access belongs to. */
148 : : gimple *stmt;
149 : :
150 : : /* Next group representative for this aggregate. */
151 : : struct access *next_grp;
152 : :
153 : : /* Pointer to the group representative. Pointer to itself if the struct is
154 : : the representative. */
155 : : struct access *group_representative;
156 : :
157 : : /* After access tree has been constructed, this points to the parent of the
158 : : current access, if there is one. NULL for roots. */
159 : : struct access *parent;
160 : :
161 : : /* If this access has any children (in terms of the definition above), this
162 : : points to the first one. */
163 : : struct access *first_child;
164 : :
165 : : /* In intraprocedural SRA, pointer to the next sibling in the access tree as
166 : : described above. */
167 : : struct access *next_sibling;
168 : :
169 : : /* Pointers to the first and last element in the linked list of assign
170 : : links for propagation from LHS to RHS. */
171 : : struct assign_link *first_rhs_link, *last_rhs_link;
172 : :
173 : : /* Pointers to the first and last element in the linked list of assign
174 : : links for propagation from LHS to RHS. */
175 : : struct assign_link *first_lhs_link, *last_lhs_link;
176 : :
177 : : /* Pointer to the next access in the work queues. */
178 : : struct access *next_rhs_queued, *next_lhs_queued;
179 : :
180 : : /* Replacement variable for this access "region." Never to be accessed
181 : : directly, always only by the means of get_access_replacement() and only
182 : : when grp_to_be_replaced flag is set. */
183 : : tree replacement_decl;
184 : :
185 : : /* Is this access made in reverse storage order? */
186 : : unsigned reverse : 1;
187 : :
188 : : /* Is this particular access write access? */
189 : : unsigned write : 1;
190 : :
191 : : /* Is this access currently in the rhs work queue? */
192 : : unsigned grp_rhs_queued : 1;
193 : :
194 : : /* Is this access currently in the lhs work queue? */
195 : : unsigned grp_lhs_queued : 1;
196 : :
197 : : /* Does this group contain a write access? This flag is propagated down the
198 : : access tree. */
199 : : unsigned grp_write : 1;
200 : :
201 : : /* Does this group contain a read access? This flag is propagated down the
202 : : access tree. */
203 : : unsigned grp_read : 1;
204 : :
205 : : /* Does this group contain a read access that comes from an assignment
206 : : statement? This flag is propagated down the access tree. */
207 : : unsigned grp_assignment_read : 1;
208 : :
209 : : /* Does this group contain a write access that comes from an assignment
210 : : statement? This flag is propagated down the access tree. */
211 : : unsigned grp_assignment_write : 1;
212 : :
213 : : /* Does this group contain a read access through a scalar type? This flag is
214 : : not propagated in the access tree in any direction. */
215 : : unsigned grp_scalar_read : 1;
216 : :
217 : : /* Does this group contain a write access through a scalar type? This flag
218 : : is not propagated in the access tree in any direction. */
219 : : unsigned grp_scalar_write : 1;
220 : :
221 : : /* In a root of an access tree, true means that the entire tree should be
222 : : totally scalarized - that all scalar leafs should be scalarized and
223 : : non-root grp_total_scalarization accesses should be honored. Otherwise,
224 : : non-root accesses with grp_total_scalarization should never get scalar
225 : : replacements. */
226 : : unsigned grp_total_scalarization : 1;
227 : :
228 : : /* Other passes of the analysis use this bit to make function
229 : : analyze_access_subtree create scalar replacements for this group if
230 : : possible. */
231 : : unsigned grp_hint : 1;
232 : :
233 : : /* Is the subtree rooted in this access fully covered by scalar
234 : : replacements? */
235 : : unsigned grp_covered : 1;
236 : :
237 : : /* If set to true, this access and all below it in an access tree must not be
238 : : scalarized. */
239 : : unsigned grp_unscalarizable_region : 1;
240 : :
241 : : /* Whether data have been written to parts of the aggregate covered by this
242 : : access which is not to be scalarized. This flag is propagated up in the
243 : : access tree. */
244 : : unsigned grp_unscalarized_data : 1;
245 : :
246 : : /* Set if all accesses in the group consist of the same chain of
247 : : COMPONENT_REFs and ARRAY_REFs. */
248 : : unsigned grp_same_access_path : 1;
249 : :
250 : : /* Does this access and/or group contain a write access through a
251 : : BIT_FIELD_REF? */
252 : : unsigned grp_partial_lhs : 1;
253 : :
254 : : /* Set when a scalar replacement should be created for this variable. */
255 : : unsigned grp_to_be_replaced : 1;
256 : :
257 : : /* Set when we want a replacement for the sole purpose of having it in
258 : : generated debug statements. */
259 : : unsigned grp_to_be_debug_replaced : 1;
260 : :
261 : : /* Should TREE_NO_WARNING of a replacement be set? */
262 : : unsigned grp_no_warning : 1;
263 : :
264 : : /* Result of propagation accross link from LHS to RHS. */
265 : : unsigned grp_result_of_prop_from_lhs : 1;
266 : : };
267 : :
268 : : typedef struct access *access_p;
269 : :
270 : :
271 : : /* Alloc pool for allocating access structures. */
272 : : static object_allocator<struct access> access_pool ("SRA accesses");
273 : :
274 : : /* A structure linking lhs and rhs accesses from an aggregate assignment. They
275 : : are used to propagate subaccesses from rhs to lhs and vice versa as long as
276 : : they don't conflict with what is already there. In the RHS->LHS direction,
277 : : we also propagate grp_write flag to lazily mark that the access contains any
278 : : meaningful data. */
279 : : struct assign_link
280 : : {
281 : : struct access *lacc, *racc;
282 : : struct assign_link *next_rhs, *next_lhs;
283 : : };
284 : :
285 : : /* Alloc pool for allocating assign link structures. */
286 : : static object_allocator<assign_link> assign_link_pool ("SRA links");
287 : :
288 : : /* Base (tree) -> Vector (vec<access_p> *) map. */
289 : : static hash_map<tree, auto_vec<access_p> > *base_access_vec;
290 : :
291 : : /* Hash to limit creation of artificial accesses */
292 : : static hash_map<tree, unsigned> *propagation_budget;
293 : :
294 : : /* Candidate hash table helpers. */
295 : :
296 : : struct uid_decl_hasher : nofree_ptr_hash <tree_node>
297 : : {
298 : : static inline hashval_t hash (const tree_node *);
299 : : static inline bool equal (const tree_node *, const tree_node *);
300 : : };
301 : :
302 : : /* Hash a tree in a uid_decl_map. */
303 : :
304 : : inline hashval_t
305 : 78139764 : uid_decl_hasher::hash (const tree_node *item)
306 : : {
307 : 78139764 : return item->decl_minimal.uid;
308 : : }
309 : :
310 : : /* Return true if the DECL_UID in both trees are equal. */
311 : :
312 : : inline bool
313 : 89722086 : uid_decl_hasher::equal (const tree_node *a, const tree_node *b)
314 : : {
315 : 89722086 : return (a->decl_minimal.uid == b->decl_minimal.uid);
316 : : }
317 : :
318 : : /* Set of candidates. */
319 : : static bitmap candidate_bitmap;
320 : : static hash_table<uid_decl_hasher> *candidates;
321 : :
322 : : /* For a candidate UID return the candidates decl. */
323 : :
324 : : static inline tree
325 : 14037129 : candidate (unsigned uid)
326 : : {
327 : 14037129 : tree_node t;
328 : 14037129 : t.decl_minimal.uid = uid;
329 : 14037129 : return candidates->find_with_hash (&t, static_cast <hashval_t> (uid));
330 : : }
331 : :
332 : : /* Bitmap of candidates which we should try to entirely scalarize away and
333 : : those which cannot be (because they are and need be used as a whole). */
334 : : static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
335 : :
336 : : /* Bitmap of candidates in the constant pool, which cannot be scalarized
337 : : because this would produce non-constant expressions (e.g. Ada). */
338 : : static bitmap disqualified_constants;
339 : :
340 : : /* Bitmap of candidates which are passed by reference in call arguments. */
341 : : static bitmap passed_by_ref_in_call;
342 : :
343 : : /* Obstack for creation of fancy names. */
344 : : static struct obstack name_obstack;
345 : :
346 : : /* Head of a linked list of accesses that need to have its subaccesses
347 : : propagated to their assignment counterparts. */
348 : : static struct access *rhs_work_queue_head, *lhs_work_queue_head;
349 : :
350 : : /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
351 : : representative fields are dumped, otherwise those which only describe the
352 : : individual access are. */
353 : :
354 : : static struct
355 : : {
356 : : /* Number of processed aggregates is readily available in
357 : : analyze_all_variable_accesses and so is not stored here. */
358 : :
359 : : /* Number of created scalar replacements. */
360 : : int replacements;
361 : :
362 : : /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
363 : : expression. */
364 : : int exprs;
365 : :
366 : : /* Number of statements created by generate_subtree_copies. */
367 : : int subtree_copies;
368 : :
369 : : /* Number of statements created by load_assign_lhs_subreplacements. */
370 : : int subreplacements;
371 : :
372 : : /* Number of times sra_modify_assign has deleted a statement. */
373 : : int deleted;
374 : :
375 : : /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
376 : : RHS reparately due to type conversions or nonexistent matching
377 : : references. */
378 : : int separate_lhs_rhs_handling;
379 : :
380 : : /* Number of parameters that were removed because they were unused. */
381 : : int deleted_unused_parameters;
382 : :
383 : : /* Number of scalars passed as parameters by reference that have been
384 : : converted to be passed by value. */
385 : : int scalar_by_ref_to_by_val;
386 : :
387 : : /* Number of aggregate parameters that were replaced by one or more of their
388 : : components. */
389 : : int aggregate_params_reduced;
390 : :
391 : : /* Numbber of components created when splitting aggregate parameters. */
392 : : int param_reductions_created;
393 : :
394 : : /* Number of deferred_init calls that are modified. */
395 : : int deferred_init;
396 : :
397 : : /* Number of deferred_init calls that are created by
398 : : generate_subtree_deferred_init. */
399 : : int subtree_deferred_init;
400 : : } sra_stats;
401 : :
402 : : static void
403 : 36 : dump_access (FILE *f, struct access *access, bool grp)
404 : : {
405 : 36 : fprintf (f, "access { ");
406 : 36 : fprintf (f, "base = (%d)'", DECL_UID (access->base));
407 : 36 : print_generic_expr (f, access->base);
408 : 36 : fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
409 : 36 : fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
410 : 36 : fprintf (f, ", expr = ");
411 : 36 : print_generic_expr (f, access->expr);
412 : 36 : fprintf (f, ", type = ");
413 : 36 : print_generic_expr (f, access->type);
414 : 36 : fprintf (f, ", reverse = %d", access->reverse);
415 : 36 : if (grp)
416 : 36 : fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
417 : : "grp_assignment_write = %d, grp_scalar_read = %d, "
418 : : "grp_scalar_write = %d, grp_total_scalarization = %d, "
419 : : "grp_hint = %d, grp_covered = %d, "
420 : : "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
421 : : "grp_same_access_path = %d, grp_partial_lhs = %d, "
422 : : "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d}\n",
423 : 36 : access->grp_read, access->grp_write, access->grp_assignment_read,
424 : 36 : access->grp_assignment_write, access->grp_scalar_read,
425 : 36 : access->grp_scalar_write, access->grp_total_scalarization,
426 : 36 : access->grp_hint, access->grp_covered,
427 : 36 : access->grp_unscalarizable_region, access->grp_unscalarized_data,
428 : 36 : access->grp_same_access_path, access->grp_partial_lhs,
429 : 36 : access->grp_to_be_replaced, access->grp_to_be_debug_replaced);
430 : : else
431 : 0 : fprintf (f, ", write = %d, grp_total_scalarization = %d, "
432 : : "grp_partial_lhs = %d}\n",
433 : 0 : access->write, access->grp_total_scalarization,
434 : 0 : access->grp_partial_lhs);
435 : 36 : }
436 : :
437 : : /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
438 : :
439 : : static void
440 : 18 : dump_access_tree_1 (FILE *f, struct access *access, int level)
441 : : {
442 : 36 : do
443 : : {
444 : 36 : int i;
445 : :
446 : 62 : for (i = 0; i < level; i++)
447 : 26 : fputs ("* ", f);
448 : :
449 : 36 : dump_access (f, access, true);
450 : :
451 : 36 : if (access->first_child)
452 : 8 : dump_access_tree_1 (f, access->first_child, level + 1);
453 : :
454 : 36 : access = access->next_sibling;
455 : : }
456 : 36 : while (access);
457 : 18 : }
458 : :
459 : : /* Dump all access trees for a variable, given the pointer to the first root in
460 : : ACCESS. */
461 : :
462 : : static void
463 : 9 : dump_access_tree (FILE *f, struct access *access)
464 : : {
465 : 19 : for (; access; access = access->next_grp)
466 : 10 : dump_access_tree_1 (f, access, 0);
467 : 9 : }
468 : :
469 : : /* Return true iff ACC is non-NULL and has subaccesses. */
470 : :
471 : : static inline bool
472 : 14471776 : access_has_children_p (struct access *acc)
473 : : {
474 : 7899820 : return acc && acc->first_child;
475 : : }
476 : :
477 : : /* Return true iff ACC is (partly) covered by at least one replacement. */
478 : :
479 : : static bool
480 : 797 : access_has_replacements_p (struct access *acc)
481 : : {
482 : 797 : struct access *child;
483 : 797 : if (acc->grp_to_be_replaced)
484 : : return true;
485 : 662 : for (child = acc->first_child; child; child = child->next_sibling)
486 : 147 : if (access_has_replacements_p (child))
487 : : return true;
488 : : return false;
489 : : }
490 : :
491 : : /* Return a vector of pointers to accesses for the variable given in BASE or
492 : : NULL if there is none. */
493 : :
494 : : static vec<access_p> *
495 : 22759250 : get_base_access_vector (tree base)
496 : : {
497 : 0 : return base_access_vec->get (base);
498 : : }
499 : :
500 : : /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
501 : : in ACCESS. Return NULL if it cannot be found. */
502 : :
503 : : static struct access *
504 : 9969645 : find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
505 : : HOST_WIDE_INT size)
506 : : {
507 : 25255277 : while (access && (access->offset != offset || access->size != size))
508 : : {
509 : 5315987 : struct access *child = access->first_child;
510 : :
511 : 10267909 : while (child && (child->offset + child->size <= offset))
512 : 4951922 : child = child->next_sibling;
513 : : access = child;
514 : : }
515 : :
516 : : /* Total scalarization does not replace single field structures with their
517 : : single field but rather creates an access for them underneath. Look for
518 : : it. */
519 : 9969645 : if (access)
520 : 10110362 : while (access->first_child
521 : 3229640 : && access->first_child->offset == offset
522 : 13269678 : && access->first_child->size == size)
523 : : access = access->first_child;
524 : :
525 : 9969645 : return access;
526 : : }
527 : :
528 : : /* Return the first group representative for DECL or NULL if none exists. */
529 : :
530 : : static struct access *
531 : 18955721 : get_first_repr_for_decl (tree base)
532 : : {
533 : 18955721 : vec<access_p> *access_vec;
534 : :
535 : 18955721 : access_vec = get_base_access_vector (base);
536 : 18955721 : if (!access_vec)
537 : : return NULL;
538 : :
539 : 18955721 : return (*access_vec)[0];
540 : : }
541 : :
542 : : /* Find an access representative for the variable BASE and given OFFSET and
543 : : SIZE. Requires that access trees have already been built. Return NULL if
544 : : it cannot be found. */
545 : :
546 : : static struct access *
547 : 8634642 : get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
548 : : HOST_WIDE_INT size)
549 : : {
550 : 8634642 : struct access *access;
551 : :
552 : 8634642 : access = get_first_repr_for_decl (base);
553 : 19454884 : while (access && (access->offset + access->size <= offset))
554 : 2185600 : access = access->next_grp;
555 : 8634642 : if (!access)
556 : : return NULL;
557 : :
558 : 8634611 : return find_access_in_subtree (access, offset, size);
559 : : }
560 : :
561 : : /* Add LINK to the linked list of assign links of RACC. */
562 : :
563 : : static void
564 : 1179348 : add_link_to_rhs (struct access *racc, struct assign_link *link)
565 : : {
566 : 1179348 : gcc_assert (link->racc == racc);
567 : :
568 : 1179348 : if (!racc->first_rhs_link)
569 : : {
570 : 1179348 : gcc_assert (!racc->last_rhs_link);
571 : 1179348 : racc->first_rhs_link = link;
572 : : }
573 : : else
574 : 0 : racc->last_rhs_link->next_rhs = link;
575 : :
576 : 1179348 : racc->last_rhs_link = link;
577 : 1179348 : link->next_rhs = NULL;
578 : 1179348 : }
579 : :
580 : : /* Add LINK to the linked list of lhs assign links of LACC. */
581 : :
582 : : static void
583 : 1179348 : add_link_to_lhs (struct access *lacc, struct assign_link *link)
584 : : {
585 : 1179348 : gcc_assert (link->lacc == lacc);
586 : :
587 : 1179348 : if (!lacc->first_lhs_link)
588 : : {
589 : 1179348 : gcc_assert (!lacc->last_lhs_link);
590 : 1179348 : lacc->first_lhs_link = link;
591 : : }
592 : : else
593 : 0 : lacc->last_lhs_link->next_lhs = link;
594 : :
595 : 1179348 : lacc->last_lhs_link = link;
596 : 1179348 : link->next_lhs = NULL;
597 : 1179348 : }
598 : :
599 : : /* Move all link structures in their linked list in OLD_ACC to the linked list
600 : : in NEW_ACC. */
601 : : static void
602 : 4663125 : relink_to_new_repr (struct access *new_acc, struct access *old_acc)
603 : : {
604 : 4663125 : if (old_acc->first_rhs_link)
605 : : {
606 : :
607 : 835667 : if (new_acc->first_rhs_link)
608 : : {
609 : 150403 : gcc_assert (!new_acc->last_rhs_link->next_rhs);
610 : 150403 : gcc_assert (!old_acc->last_rhs_link
611 : : || !old_acc->last_rhs_link->next_rhs);
612 : :
613 : 150403 : new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link;
614 : 150403 : new_acc->last_rhs_link = old_acc->last_rhs_link;
615 : : }
616 : : else
617 : : {
618 : 685264 : gcc_assert (!new_acc->last_rhs_link);
619 : :
620 : 685264 : new_acc->first_rhs_link = old_acc->first_rhs_link;
621 : 685264 : new_acc->last_rhs_link = old_acc->last_rhs_link;
622 : : }
623 : 835667 : old_acc->first_rhs_link = old_acc->last_rhs_link = NULL;
624 : : }
625 : : else
626 : 3827458 : gcc_assert (!old_acc->last_rhs_link);
627 : :
628 : 4663125 : if (old_acc->first_lhs_link)
629 : : {
630 : :
631 : 349058 : if (new_acc->first_lhs_link)
632 : : {
633 : 149632 : gcc_assert (!new_acc->last_lhs_link->next_lhs);
634 : 149632 : gcc_assert (!old_acc->last_lhs_link
635 : : || !old_acc->last_lhs_link->next_lhs);
636 : :
637 : 149632 : new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link;
638 : 149632 : new_acc->last_lhs_link = old_acc->last_lhs_link;
639 : : }
640 : : else
641 : : {
642 : 199426 : gcc_assert (!new_acc->last_lhs_link);
643 : :
644 : 199426 : new_acc->first_lhs_link = old_acc->first_lhs_link;
645 : 199426 : new_acc->last_lhs_link = old_acc->last_lhs_link;
646 : : }
647 : 349058 : old_acc->first_lhs_link = old_acc->last_lhs_link = NULL;
648 : : }
649 : : else
650 : 4314067 : gcc_assert (!old_acc->last_lhs_link);
651 : :
652 : 4663125 : }
653 : :
654 : : /* Add ACCESS to the work to queue for propagation of subaccesses from RHS to
655 : : LHS (which is actually a stack). */
656 : :
657 : : static void
658 : 3851600 : add_access_to_rhs_work_queue (struct access *access)
659 : : {
660 : 3851600 : if (access->first_rhs_link && !access->grp_rhs_queued)
661 : : {
662 : 1509898 : gcc_assert (!access->next_rhs_queued);
663 : 1509898 : access->next_rhs_queued = rhs_work_queue_head;
664 : 1509898 : access->grp_rhs_queued = 1;
665 : 1509898 : rhs_work_queue_head = access;
666 : : }
667 : 3851600 : }
668 : :
669 : : /* Add ACCESS to the work to queue for propagation of subaccesses from LHS to
670 : : RHS (which is actually a stack). */
671 : :
672 : : static void
673 : 1416075 : add_access_to_lhs_work_queue (struct access *access)
674 : : {
675 : 1416075 : if (access->first_lhs_link && !access->grp_lhs_queued)
676 : : {
677 : 1181811 : gcc_assert (!access->next_lhs_queued);
678 : 1181811 : access->next_lhs_queued = lhs_work_queue_head;
679 : 1181811 : access->grp_lhs_queued = 1;
680 : 1181811 : lhs_work_queue_head = access;
681 : : }
682 : 1416075 : }
683 : :
684 : : /* Pop an access from the work queue for propagating from RHS to LHS, and
685 : : return it, assuming there is one. */
686 : :
687 : : static struct access *
688 : 1509898 : pop_access_from_rhs_work_queue (void)
689 : : {
690 : 1509898 : struct access *access = rhs_work_queue_head;
691 : :
692 : 1509898 : rhs_work_queue_head = access->next_rhs_queued;
693 : 1509898 : access->next_rhs_queued = NULL;
694 : 1509898 : access->grp_rhs_queued = 0;
695 : 1509898 : return access;
696 : : }
697 : :
698 : : /* Pop an access from the work queue for propagating from LHS to RHS, and
699 : : return it, assuming there is one. */
700 : :
701 : : static struct access *
702 : 1181811 : pop_access_from_lhs_work_queue (void)
703 : : {
704 : 1181811 : struct access *access = lhs_work_queue_head;
705 : :
706 : 1181811 : lhs_work_queue_head = access->next_lhs_queued;
707 : 1181811 : access->next_lhs_queued = NULL;
708 : 1181811 : access->grp_lhs_queued = 0;
709 : 1181811 : return access;
710 : : }
711 : :
712 : : /* Allocate necessary structures. */
713 : :
714 : : static void
715 : 3206652 : sra_initialize (void)
716 : : {
717 : 3206652 : candidate_bitmap = BITMAP_ALLOC (NULL);
718 : 6413304 : candidates = new hash_table<uid_decl_hasher>
719 : 5972430 : (vec_safe_length (cfun->local_decls) / 2);
720 : 3206652 : should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
721 : 3206652 : cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
722 : 3206652 : disqualified_constants = BITMAP_ALLOC (NULL);
723 : 3206652 : passed_by_ref_in_call = BITMAP_ALLOC (NULL);
724 : 3206652 : gcc_obstack_init (&name_obstack);
725 : 3206652 : base_access_vec = new hash_map<tree, auto_vec<access_p> >;
726 : 3206652 : memset (&sra_stats, 0, sizeof (sra_stats));
727 : 3206652 : }
728 : :
729 : : /* Deallocate all general structures. */
730 : :
731 : : static void
732 : 3206652 : sra_deinitialize (void)
733 : : {
734 : 3206652 : BITMAP_FREE (candidate_bitmap);
735 : 3206652 : delete candidates;
736 : 3206652 : candidates = NULL;
737 : 3206652 : BITMAP_FREE (should_scalarize_away_bitmap);
738 : 3206652 : BITMAP_FREE (cannot_scalarize_away_bitmap);
739 : 3206652 : BITMAP_FREE (disqualified_constants);
740 : 3206652 : BITMAP_FREE (passed_by_ref_in_call);
741 : 3206652 : access_pool.release ();
742 : 3206652 : assign_link_pool.release ();
743 : 3206652 : obstack_free (&name_obstack, NULL);
744 : :
745 : 6413304 : delete base_access_vec;
746 : 3206652 : }
747 : :
748 : : /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */
749 : :
750 : 37979273 : static bool constant_decl_p (tree decl)
751 : : {
752 : 32972721 : return VAR_P (decl) && DECL_IN_CONSTANT_POOL (decl);
753 : : }
754 : :
755 : : /* Remove DECL from candidates for SRA and write REASON to the dump file if
756 : : there is one. */
757 : :
758 : : static void
759 : 3906387 : disqualify_candidate (tree decl, const char *reason)
760 : : {
761 : 3906387 : if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl)))
762 : 1991186 : candidates->remove_elt_with_hash (decl, DECL_UID (decl));
763 : 3906387 : if (constant_decl_p (decl))
764 : 4039 : bitmap_set_bit (disqualified_constants, DECL_UID (decl));
765 : :
766 : 3906387 : if (dump_file && (dump_flags & TDF_DETAILS))
767 : : {
768 : 8 : fprintf (dump_file, "! Disqualifying ");
769 : 8 : print_generic_expr (dump_file, decl);
770 : 8 : fprintf (dump_file, " - %s\n", reason);
771 : : }
772 : 3906387 : }
773 : :
774 : : /* Return true iff the type contains a field or an element which does not allow
775 : : scalarization. Use VISITED_TYPES to avoid re-checking already checked
776 : : (sub-)types. */
777 : :
778 : : static bool
779 : 7407309 : type_internals_preclude_sra_p_1 (tree type, const char **msg,
780 : : hash_set<tree> *visited_types)
781 : : {
782 : 7407309 : tree fld;
783 : 7407309 : tree et;
784 : :
785 : 7407309 : if (visited_types->contains (type))
786 : : return false;
787 : 7128202 : visited_types->add (type);
788 : :
789 : 7128202 : switch (TREE_CODE (type))
790 : : {
791 : 6524018 : case RECORD_TYPE:
792 : 6524018 : case UNION_TYPE:
793 : 6524018 : case QUAL_UNION_TYPE:
794 : 112041934 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
795 : 105527583 : if (TREE_CODE (fld) == FIELD_DECL)
796 : : {
797 : 15615586 : if (TREE_CODE (fld) == FUNCTION_DECL)
798 : : continue;
799 : 15615586 : tree ft = TREE_TYPE (fld);
800 : :
801 : 15615586 : if (TREE_THIS_VOLATILE (fld))
802 : : {
803 : 833 : *msg = "volatile structure field";
804 : 833 : return true;
805 : : }
806 : 15614753 : if (!DECL_FIELD_OFFSET (fld))
807 : : {
808 : 0 : *msg = "no structure field offset";
809 : 0 : return true;
810 : : }
811 : 15614753 : if (!DECL_SIZE (fld))
812 : : {
813 : 7725 : *msg = "zero structure field size";
814 : 7725 : return true;
815 : : }
816 : 15607028 : if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld)))
817 : : {
818 : 0 : *msg = "structure field offset not fixed";
819 : 0 : return true;
820 : : }
821 : 15607028 : if (!tree_fits_uhwi_p (DECL_SIZE (fld)))
822 : : {
823 : 0 : *msg = "structure field size not fixed";
824 : 0 : return true;
825 : : }
826 : 15607028 : if (!tree_fits_shwi_p (bit_position (fld)))
827 : : {
828 : 0 : *msg = "structure field size too big";
829 : 0 : return true;
830 : : }
831 : 15607028 : if (AGGREGATE_TYPE_P (ft)
832 : 15607028 : && int_bit_position (fld) % BITS_PER_UNIT != 0)
833 : : {
834 : 0 : *msg = "structure field is bit field";
835 : 0 : return true;
836 : : }
837 : :
838 : 15607028 : if (AGGREGATE_TYPE_P (ft)
839 : 15607028 : && type_internals_preclude_sra_p_1 (ft, msg, visited_types))
840 : : return true;
841 : : }
842 : :
843 : : return false;
844 : :
845 : 495060 : case ARRAY_TYPE:
846 : 495060 : et = TREE_TYPE (type);
847 : :
848 : 495060 : if (TYPE_VOLATILE (et))
849 : : {
850 : 0 : *msg = "element type is volatile";
851 : 0 : return true;
852 : : }
853 : :
854 : 495060 : if (AGGREGATE_TYPE_P (et)
855 : 495060 : && type_internals_preclude_sra_p_1 (et, msg, visited_types))
856 : : return true;
857 : :
858 : : return false;
859 : :
860 : : default:
861 : : return false;
862 : : }
863 : : }
864 : :
865 : : /* Return true iff the type contains a field or an element which does not allow
866 : : scalarization. */
867 : :
868 : : bool
869 : 4406648 : type_internals_preclude_sra_p (tree type, const char **msg)
870 : : {
871 : 4406648 : hash_set<tree> visited_types;
872 : 4406648 : return type_internals_preclude_sra_p_1 (type, msg, &visited_types);
873 : 4406648 : }
874 : :
875 : :
876 : : /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
877 : : the three fields. Also add it to the vector of accesses corresponding to
878 : : the base. Finally, return the new access. */
879 : :
880 : : static struct access *
881 : 13486558 : create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
882 : : {
883 : 13486558 : struct access *access = access_pool.allocate ();
884 : :
885 : 13486558 : memset (access, 0, sizeof (struct access));
886 : 13486558 : access->base = base;
887 : 13486558 : access->offset = offset;
888 : 13486558 : access->size = size;
889 : :
890 : 13486558 : base_access_vec->get_or_insert (base).safe_push (access);
891 : :
892 : 13486558 : return access;
893 : : }
894 : :
895 : : static bool maybe_add_sra_candidate (tree);
896 : :
897 : : /* Create and insert access for EXPR. Return created access, or NULL if it is
898 : : not possible. Also scan for uses of constant pool as we go along and add
899 : : to candidates. */
900 : :
901 : : static struct access *
902 : 25491030 : create_access (tree expr, gimple *stmt, bool write)
903 : : {
904 : 25491030 : struct access *access;
905 : 25491030 : poly_int64 poffset, psize, pmax_size;
906 : 25491030 : tree base = expr;
907 : 25491030 : bool reverse, unscalarizable_region = false;
908 : :
909 : 25491030 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
910 : : &reverse);
911 : :
912 : : /* For constant-pool entries, check we can substitute the constant value. */
913 : 25491030 : if (constant_decl_p (base)
914 : 2934 : && !bitmap_bit_p (disqualified_constants, DECL_UID (base)))
915 : : {
916 : 2934 : if (expr != base
917 : 7 : && !is_gimple_reg_type (TREE_TYPE (expr))
918 : 2934 : && dump_file && (dump_flags & TDF_DETAILS))
919 : : {
920 : : /* This occurs in Ada with accesses to ARRAY_RANGE_REFs,
921 : : and elements of multidimensional arrays (which are
922 : : multi-element arrays in their own right). */
923 : 0 : fprintf (dump_file, "Allowing non-reg-type load of part"
924 : : " of constant-pool entry: ");
925 : 0 : print_generic_expr (dump_file, expr);
926 : : }
927 : 2934 : maybe_add_sra_candidate (base);
928 : : }
929 : :
930 : 25491030 : if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
931 : 12000986 : return NULL;
932 : :
933 : 13490044 : if (write && TREE_READONLY (base))
934 : : {
935 : 3119 : disqualify_candidate (base, "Encountered a store to a read-only decl.");
936 : 3119 : return NULL;
937 : : }
938 : :
939 : 13486925 : HOST_WIDE_INT offset, size, max_size;
940 : 13486925 : if (!poffset.is_constant (&offset)
941 : 13486925 : || !psize.is_constant (&size)
942 : 13486925 : || !pmax_size.is_constant (&max_size))
943 : : {
944 : : disqualify_candidate (base, "Encountered a polynomial-sized access.");
945 : : return NULL;
946 : : }
947 : :
948 : 13486925 : if (size != max_size)
949 : : {
950 : 330970 : size = max_size;
951 : 330970 : unscalarizable_region = true;
952 : : }
953 : 13486925 : if (size == 0)
954 : : return NULL;
955 : 13486923 : if (offset < 0)
956 : : {
957 : 36 : disqualify_candidate (base, "Encountered a negative offset access.");
958 : 36 : return NULL;
959 : : }
960 : 13486887 : if (size < 0)
961 : : {
962 : 31 : disqualify_candidate (base, "Encountered an unconstrained access.");
963 : 31 : return NULL;
964 : : }
965 : 13486856 : if (offset + size > tree_to_shwi (DECL_SIZE (base)))
966 : : {
967 : 297 : disqualify_candidate (base, "Encountered an access beyond the base.");
968 : 297 : return NULL;
969 : : }
970 : 13486559 : if (TREE_CODE (TREE_TYPE (expr)) == BITINT_TYPE
971 : 13486559 : && size > WIDE_INT_MAX_PRECISION - 1)
972 : : {
973 : 1 : disqualify_candidate (base, "Encountered too large _BitInt access.");
974 : 1 : return NULL;
975 : : }
976 : :
977 : 13486558 : access = create_access_1 (base, offset, size);
978 : 13486558 : access->expr = expr;
979 : 13486558 : access->type = TREE_TYPE (expr);
980 : 13486558 : access->write = write;
981 : 13486558 : access->grp_unscalarizable_region = unscalarizable_region;
982 : 13486558 : access->stmt = stmt;
983 : 13486558 : access->reverse = reverse;
984 : :
985 : 13486558 : return access;
986 : : }
987 : :
988 : : /* Given an array type TYPE, extract element size to *EL_SIZE, minimum index to
989 : : *IDX and maximum index to *MAX so that the caller can iterate over all
990 : : elements and return true, except if the array is known to be zero-length,
991 : : then return false. */
992 : :
993 : : static bool
994 : 15099 : prepare_iteration_over_array_elts (tree type, HOST_WIDE_INT *el_size,
995 : : offset_int *idx, offset_int *max)
996 : : {
997 : 15099 : tree elem_size = TYPE_SIZE (TREE_TYPE (type));
998 : 15099 : gcc_assert (elem_size && tree_fits_shwi_p (elem_size));
999 : 15099 : *el_size = tree_to_shwi (elem_size);
1000 : 15099 : gcc_assert (*el_size > 0);
1001 : :
1002 : 15099 : tree minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1003 : 15099 : gcc_assert (TREE_CODE (minidx) == INTEGER_CST);
1004 : 15099 : tree maxidx = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1005 : : /* Skip (some) zero-length arrays; others have MAXIDX == MINIDX - 1. */
1006 : 15099 : if (!maxidx)
1007 : : return false;
1008 : 15099 : gcc_assert (TREE_CODE (maxidx) == INTEGER_CST);
1009 : 15099 : tree domain = TYPE_DOMAIN (type);
1010 : : /* MINIDX and MAXIDX are inclusive, and must be interpreted in
1011 : : DOMAIN (e.g. signed int, whereas min/max may be size_int). */
1012 : 15099 : *idx = wi::to_offset (minidx);
1013 : 15099 : *max = wi::to_offset (maxidx);
1014 : 15099 : if (!TYPE_UNSIGNED (domain))
1015 : : {
1016 : 15099 : *idx = wi::sext (*idx, TYPE_PRECISION (domain));
1017 : 15099 : *max = wi::sext (*max, TYPE_PRECISION (domain));
1018 : : }
1019 : : return true;
1020 : : }
1021 : :
1022 : : /* A structure to track collecting padding and hold collected padding
1023 : : information. */
1024 : :
1025 : 62907 : class sra_padding_collecting
1026 : : {
1027 : : public:
1028 : : /* Given that there won't be any data until at least OFFSET, add an
1029 : : appropriate entry to the list of paddings or extend the last one. */
1030 : : void record_padding (HOST_WIDE_INT offset);
1031 : : /* Vector of pairs describing contiguous pieces of padding, each pair
1032 : : consisting of offset and length. */
1033 : : auto_vec<std::pair<HOST_WIDE_INT, HOST_WIDE_INT>, 10> m_padding;
1034 : : /* Offset where data should continue after the last seen actual bit of data
1035 : : if there was no padding. */
1036 : : HOST_WIDE_INT m_data_until = 0;
1037 : : };
1038 : :
1039 : : /* Given that there won't be any data until at least OFFSET, add an appropriate
1040 : : entry to the list of paddings or extend the last one. */
1041 : :
1042 : 180900 : void sra_padding_collecting::record_padding (HOST_WIDE_INT offset)
1043 : : {
1044 : 180900 : if (offset > m_data_until)
1045 : : {
1046 : 11178 : HOST_WIDE_INT psz = offset - m_data_until;
1047 : 11178 : if (!m_padding.is_empty ()
1048 : 544 : && ((m_padding[m_padding.length () - 1].first
1049 : 544 : + m_padding[m_padding.length () - 1].second) == offset))
1050 : 0 : m_padding[m_padding.length () - 1].second += psz;
1051 : : else
1052 : 11178 : m_padding.safe_push (std::make_pair (m_data_until, psz));
1053 : : }
1054 : 180900 : }
1055 : :
1056 : : /* Return true iff TYPE is totally scalarizable - i.e. a RECORD_TYPE or
1057 : : fixed-length ARRAY_TYPE with fields that are either of gimple register types
1058 : : (excluding bit-fields) or (recursively) scalarizable types. CONST_DECL must
1059 : : be true if we are considering a decl from constant pool. If it is false,
1060 : : char arrays will be refused.
1061 : :
1062 : : TOTAL_OFFSET is the offset of TYPE within any outer type that is being
1063 : : examined.
1064 : :
1065 : : If PC is non-NULL, collect padding information into the vector within the
1066 : : structure. The information is however only complete if the function returns
1067 : : true and does not contain any padding at its end. */
1068 : :
1069 : : static bool
1070 : 3471128 : totally_scalarizable_type_p (tree type, bool const_decl,
1071 : : HOST_WIDE_INT total_offset,
1072 : : sra_padding_collecting *pc)
1073 : : {
1074 : 3471128 : if (is_gimple_reg_type (type))
1075 : : {
1076 : 2245505 : if (pc)
1077 : : {
1078 : 116640 : pc->record_padding (total_offset);
1079 : 116640 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1080 : : }
1081 : 2245505 : return true;
1082 : : }
1083 : 1225623 : if (type_contains_placeholder_p (type))
1084 : : return false;
1085 : :
1086 : 1225623 : bool have_predecessor_field = false;
1087 : 1225623 : HOST_WIDE_INT prev_pos = 0;
1088 : :
1089 : 1225623 : switch (TREE_CODE (type))
1090 : : {
1091 : 1181920 : case RECORD_TYPE:
1092 : 16781646 : for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1093 : 15631773 : if (TREE_CODE (fld) == FIELD_DECL)
1094 : : {
1095 : 2455605 : tree ft = TREE_TYPE (fld);
1096 : :
1097 : 2455605 : if (!DECL_SIZE (fld))
1098 : : return false;
1099 : 2455601 : if (zerop (DECL_SIZE (fld)))
1100 : 48360 : continue;
1101 : :
1102 : 2407241 : HOST_WIDE_INT pos = int_bit_position (fld);
1103 : 2407241 : if (have_predecessor_field
1104 : 2407241 : && pos <= prev_pos)
1105 : : return false;
1106 : :
1107 : 2407241 : have_predecessor_field = true;
1108 : 2407241 : prev_pos = pos;
1109 : :
1110 : 2407241 : if (DECL_BIT_FIELD (fld))
1111 : : return false;
1112 : :
1113 : 2405943 : if (!totally_scalarizable_type_p (ft, const_decl, total_offset + pos,
1114 : : pc))
1115 : : return false;
1116 : : }
1117 : :
1118 : : return true;
1119 : :
1120 : 27141 : case ARRAY_TYPE:
1121 : 27141 : {
1122 : 27141 : HOST_WIDE_INT min_elem_size;
1123 : 27141 : if (const_decl)
1124 : : min_elem_size = 0;
1125 : : else
1126 : 21027 : min_elem_size = BITS_PER_UNIT;
1127 : :
1128 : 27141 : if (TYPE_DOMAIN (type) == NULL_TREE
1129 : 27141 : || !tree_fits_shwi_p (TYPE_SIZE (type))
1130 : 27141 : || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type)))
1131 : 27141 : || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size)
1132 : 47632 : || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1133 : : return false;
1134 : 20491 : if (tree_to_shwi (TYPE_SIZE (type)) == 0
1135 : 20491 : && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE)
1136 : : /* Zero-element array, should not prevent scalarization. */
1137 : : ;
1138 : 20491 : else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0)
1139 : 20491 : || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type))))
1140 : : /* Variable-length array, do not allow scalarization. */
1141 : : return false;
1142 : :
1143 : 20443 : unsigned old_padding_len = 0;
1144 : 20443 : if (pc)
1145 : 6010 : old_padding_len = pc->m_padding.length ();
1146 : 20443 : tree elem = TREE_TYPE (type);
1147 : 20443 : if (!totally_scalarizable_type_p (elem, const_decl, total_offset, pc))
1148 : : return false;
1149 : 15194 : if (pc)
1150 : : {
1151 : 5914 : unsigned new_padding_len = pc->m_padding.length ();
1152 : 5914 : HOST_WIDE_INT el_size;
1153 : 5914 : offset_int idx, max;
1154 : 5914 : if (!prepare_iteration_over_array_elts (type, &el_size, &idx, &max))
1155 : 0 : return true;
1156 : 5914 : pc->record_padding (total_offset + el_size);
1157 : 5914 : ++idx;
1158 : 5914 : for (HOST_WIDE_INT pos = total_offset + el_size;
1159 : 16734 : idx <= max;
1160 : 10820 : pos += el_size, ++idx)
1161 : : {
1162 : 10847 : for (unsigned i = old_padding_len; i < new_padding_len; i++)
1163 : : {
1164 : 27 : HOST_WIDE_INT pp
1165 : 27 : = pos + pc->m_padding[i].first - total_offset;
1166 : 27 : HOST_WIDE_INT psz = pc->m_padding[i].second;
1167 : 27 : pc->m_padding.safe_push (std::make_pair (pp, psz));
1168 : : }
1169 : : }
1170 : 5914 : pc->m_data_until = total_offset + tree_to_shwi (TYPE_SIZE (type));
1171 : : }
1172 : : return true;
1173 : : }
1174 : : default:
1175 : : return false;
1176 : : }
1177 : : }
1178 : :
1179 : : /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */
1180 : :
1181 : : static inline bool
1182 : 51629279 : contains_view_convert_expr_p (const_tree ref)
1183 : : {
1184 : 71304067 : while (handled_component_p (ref))
1185 : : {
1186 : 19684049 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
1187 : : return true;
1188 : 19674788 : ref = TREE_OPERAND (ref, 0);
1189 : : }
1190 : :
1191 : : return false;
1192 : : }
1193 : :
1194 : : /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a
1195 : : bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool
1196 : : it points to will be set if REF contains any of the above or a MEM_REF
1197 : : expression that effectively performs type conversion. */
1198 : :
1199 : : static bool
1200 : 7405556 : contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL)
1201 : : {
1202 : 9073423 : while (handled_component_p (ref))
1203 : : {
1204 : 2050006 : if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
1205 : 2050006 : || (TREE_CODE (ref) == COMPONENT_REF
1206 : 1423405 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
1207 : : {
1208 : 382139 : if (type_changing_p)
1209 : 200580 : *type_changing_p = true;
1210 : 382139 : return true;
1211 : : }
1212 : 1667867 : ref = TREE_OPERAND (ref, 0);
1213 : : }
1214 : :
1215 : 7023417 : if (!type_changing_p
1216 : 3496514 : || TREE_CODE (ref) != MEM_REF
1217 : 7110053 : || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR)
1218 : : return false;
1219 : :
1220 : 86636 : tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
1221 : 86636 : if (TYPE_MAIN_VARIANT (TREE_TYPE (ref))
1222 : 86636 : != TYPE_MAIN_VARIANT (TREE_TYPE (mem)))
1223 : 67319 : *type_changing_p = true;
1224 : :
1225 : : return false;
1226 : : }
1227 : :
1228 : : /* Search the given tree for a declaration by skipping handled components and
1229 : : exclude it from the candidates. */
1230 : :
1231 : : static void
1232 : 904740 : disqualify_base_of_expr (tree t, const char *reason)
1233 : : {
1234 : 904740 : t = get_base_address (t);
1235 : 904740 : if (t && DECL_P (t))
1236 : 837009 : disqualify_candidate (t, reason);
1237 : 904740 : }
1238 : :
1239 : : /* Return true if the BIT_FIELD_REF read EXPR is handled by SRA. */
1240 : :
1241 : : static bool
1242 : 68479 : sra_handled_bf_read_p (tree expr)
1243 : : {
1244 : 68479 : uint64_t size, offset;
1245 : 68479 : if (bit_field_size (expr).is_constant (&size)
1246 : 68479 : && bit_field_offset (expr).is_constant (&offset)
1247 : 68479 : && size % BITS_PER_UNIT == 0
1248 : 68479 : && offset % BITS_PER_UNIT == 0
1249 : 68547 : && pow2p_hwi (size))
1250 : 68383 : return true;
1251 : : return false;
1252 : : }
1253 : :
1254 : : /* Scan expression EXPR and create access structures for all accesses to
1255 : : candidates for scalarization. Return the created access or NULL if none is
1256 : : created. */
1257 : :
1258 : : static struct access *
1259 : 53410815 : build_access_from_expr_1 (tree expr, gimple *stmt, bool write)
1260 : : {
1261 : : /* We only allow ADDR_EXPRs in arguments of function calls and those must
1262 : : have been dealt with in build_access_from_call_arg. Any other address
1263 : : taking should have been caught by scan_visit_addr. */
1264 : 53410815 : if (TREE_CODE (expr) == ADDR_EXPR)
1265 : : {
1266 : 1781535 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1267 : 1781535 : gcc_assert (!DECL_P (base)
1268 : : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)));
1269 : 1781535 : return NULL;
1270 : : }
1271 : :
1272 : 51629280 : struct access *ret = NULL;
1273 : 51629280 : bool partial_ref;
1274 : :
1275 : 51629280 : if ((TREE_CODE (expr) == BIT_FIELD_REF
1276 : 41198 : && (write || !sra_handled_bf_read_p (expr)))
1277 : 51628132 : || TREE_CODE (expr) == IMAGPART_EXPR
1278 : 103233646 : || TREE_CODE (expr) == REALPART_EXPR)
1279 : : {
1280 : 47524 : expr = TREE_OPERAND (expr, 0);
1281 : 47524 : partial_ref = true;
1282 : : }
1283 : : else
1284 : : partial_ref = false;
1285 : :
1286 : 51629280 : if (storage_order_barrier_p (expr))
1287 : : {
1288 : 1 : disqualify_base_of_expr (expr, "storage order barrier.");
1289 : 1 : return NULL;
1290 : : }
1291 : :
1292 : : /* We need to dive through V_C_Es in order to get the size of its parameter
1293 : : and not the result type. Ada produces such statements. We are also
1294 : : capable of handling the topmost V_C_E but not any of those buried in other
1295 : : handled components. */
1296 : 51629279 : if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
1297 : 278041 : expr = TREE_OPERAND (expr, 0);
1298 : :
1299 : 51629279 : if (contains_view_convert_expr_p (expr))
1300 : : {
1301 : 9261 : disqualify_base_of_expr (expr, "V_C_E under a different handled "
1302 : : "component.");
1303 : 9261 : return NULL;
1304 : : }
1305 : 51620018 : if (TREE_THIS_VOLATILE (expr))
1306 : : {
1307 : 26927 : disqualify_base_of_expr (expr, "part of a volatile reference.");
1308 : 26927 : return NULL;
1309 : : }
1310 : :
1311 : 51593091 : switch (TREE_CODE (expr))
1312 : : {
1313 : 2795433 : case MEM_REF:
1314 : 2795433 : if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR)
1315 : : return NULL;
1316 : : /* fall through */
1317 : 25491030 : case VAR_DECL:
1318 : 25491030 : case PARM_DECL:
1319 : 25491030 : case RESULT_DECL:
1320 : 25491030 : case COMPONENT_REF:
1321 : 25491030 : case ARRAY_REF:
1322 : 25491030 : case ARRAY_RANGE_REF:
1323 : 25491030 : case BIT_FIELD_REF:
1324 : 25491030 : ret = create_access (expr, stmt, write);
1325 : 25491030 : break;
1326 : :
1327 : : default:
1328 : : break;
1329 : : }
1330 : :
1331 : 50056818 : if (write && partial_ref && ret)
1332 : 4261 : ret->grp_partial_lhs = 1;
1333 : :
1334 : : return ret;
1335 : : }
1336 : :
1337 : : /* Scan expression EXPR and create access structures for all accesses to
1338 : : candidates for scalarization. Return true if any access has been inserted.
1339 : : STMT must be the statement from which the expression is taken, WRITE must be
1340 : : true if the expression is a store and false otherwise. */
1341 : :
1342 : : static bool
1343 : 14605880 : build_access_from_expr (tree expr, gimple *stmt, bool write)
1344 : : {
1345 : 14605880 : struct access *access;
1346 : :
1347 : 14605880 : access = build_access_from_expr_1 (expr, stmt, write);
1348 : 14605880 : if (access)
1349 : : {
1350 : : /* This means the aggregate is accesses as a whole in a way other than an
1351 : : assign statement and thus cannot be removed even if we had a scalar
1352 : : replacement for everything. */
1353 : 2286365 : if (cannot_scalarize_away_bitmap)
1354 : 2286365 : bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1355 : 2286365 : return true;
1356 : : }
1357 : : return false;
1358 : : }
1359 : :
1360 : : enum out_edge_check { SRA_OUTGOING_EDGES_UNCHECKED, SRA_OUTGOING_EDGES_OK,
1361 : : SRA_OUTGOING_EDGES_FAIL };
1362 : :
1363 : : /* Return true if STMT terminates BB and there is an abnormal edge going out of
1364 : : the BB and remember the decision in OE_CHECK. */
1365 : :
1366 : : static bool
1367 : 2541930 : abnormal_edge_after_stmt_p (gimple *stmt, enum out_edge_check *oe_check)
1368 : : {
1369 : 2541930 : if (*oe_check == SRA_OUTGOING_EDGES_OK)
1370 : : return false;
1371 : 1539435 : if (*oe_check == SRA_OUTGOING_EDGES_FAIL)
1372 : : return true;
1373 : 1539214 : if (stmt_ends_bb_p (stmt))
1374 : : {
1375 : 625420 : edge e;
1376 : 625420 : edge_iterator ei;
1377 : 1619988 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1378 : 995048 : if (e->flags & EDGE_ABNORMAL)
1379 : : {
1380 : 480 : *oe_check = SRA_OUTGOING_EDGES_FAIL;
1381 : 480 : return true;
1382 : : }
1383 : : }
1384 : 1538734 : *oe_check = SRA_OUTGOING_EDGES_OK;
1385 : 1538734 : return false;
1386 : : }
1387 : :
1388 : : /* Scan expression EXPR which is an argument of a call and create access
1389 : : structures for all accesses to candidates for scalarization. Return true
1390 : : if any access has been inserted. STMT must be the statement from which the
1391 : : expression is taken. CAN_BE_RETURNED must be true if call argument flags
1392 : : do not rule out that the argument is directly returned. OE_CHECK is used
1393 : : to remember result of a test for abnormal outgoing edges after this
1394 : : statement. */
1395 : :
1396 : : static bool
1397 : 10345243 : build_access_from_call_arg (tree expr, gimple *stmt, bool can_be_returned,
1398 : : enum out_edge_check *oe_check)
1399 : : {
1400 : 10345243 : if (TREE_CODE (expr) == ADDR_EXPR)
1401 : : {
1402 : 3409266 : tree base = get_base_address (TREE_OPERAND (expr, 0));
1403 : :
1404 : 3409266 : if (can_be_returned)
1405 : : {
1406 : 867336 : disqualify_base_of_expr (base, "Address possibly returned, "
1407 : : "leading to an alis SRA may not know.");
1408 : 867336 : return false;
1409 : : }
1410 : 2541930 : if (abnormal_edge_after_stmt_p (stmt, oe_check))
1411 : : {
1412 : 701 : disqualify_base_of_expr (base, "May lead to need to add statements "
1413 : : "to abnormal edge.");
1414 : 701 : return false;
1415 : : }
1416 : :
1417 : 2541229 : bool read = build_access_from_expr (base, stmt, false);
1418 : 2541229 : bool write = build_access_from_expr (base, stmt, true);
1419 : 2541229 : if (read || write)
1420 : : {
1421 : 220057 : if (dump_file && (dump_flags & TDF_DETAILS))
1422 : : {
1423 : 0 : fprintf (dump_file, "Allowed ADDR_EXPR of ");
1424 : 0 : print_generic_expr (dump_file, base);
1425 : 0 : fprintf (dump_file, " because of ");
1426 : 0 : print_gimple_stmt (dump_file, stmt, 0);
1427 : 0 : fprintf (dump_file, "\n");
1428 : : }
1429 : 220057 : bitmap_set_bit (passed_by_ref_in_call, DECL_UID (base));
1430 : 220057 : return true;
1431 : : }
1432 : : else
1433 : : return false;
1434 : : }
1435 : :
1436 : 6935977 : return build_access_from_expr (expr, stmt, false);
1437 : : }
1438 : :
1439 : :
1440 : : /* Return the single non-EH successor edge of BB or NULL if there is none or
1441 : : more than one. */
1442 : :
1443 : : static edge
1444 : 1503612 : single_non_eh_succ (basic_block bb)
1445 : : {
1446 : 1503612 : edge e, res = NULL;
1447 : 1503612 : edge_iterator ei;
1448 : :
1449 : 4509406 : FOR_EACH_EDGE (e, ei, bb->succs)
1450 : 3006147 : if (!(e->flags & EDGE_EH))
1451 : : {
1452 : 1503848 : if (res)
1453 : : return NULL;
1454 : : res = e;
1455 : : }
1456 : :
1457 : : return res;
1458 : : }
1459 : :
1460 : : /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
1461 : : there is no alternative spot where to put statements SRA might need to
1462 : : generate after it. The spot we are looking for is an edge leading to a
1463 : : single non-EH successor, if it exists and is indeed single. RHS may be
1464 : : NULL, in that case ignore it. */
1465 : :
1466 : : static bool
1467 : 21552110 : disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs)
1468 : : {
1469 : 21552110 : if (stmt_ends_bb_p (stmt))
1470 : : {
1471 : 1387336 : if (single_non_eh_succ (gimple_bb (stmt)))
1472 : : return false;
1473 : :
1474 : 470 : disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1475 : 470 : if (rhs)
1476 : 0 : disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1477 : 470 : return true;
1478 : : }
1479 : : return false;
1480 : : }
1481 : :
1482 : : /* Return true if the nature of BASE is such that it contains data even if
1483 : : there is no write to it in the function. */
1484 : :
1485 : : static bool
1486 : 3483583 : comes_initialized_p (tree base)
1487 : : {
1488 : 0 : return TREE_CODE (base) == PARM_DECL || constant_decl_p (base);
1489 : : }
1490 : :
1491 : : /* Scan expressions occurring in STMT, create access structures for all accesses
1492 : : to candidates for scalarization and remove those candidates which occur in
1493 : : statements or expressions that prevent them from being split apart. Return
1494 : : true if any access has been inserted. */
1495 : :
1496 : : static bool
1497 : 29343895 : build_accesses_from_assign (gimple *stmt)
1498 : : {
1499 : 29343895 : tree lhs, rhs;
1500 : 29343895 : struct access *lacc, *racc;
1501 : :
1502 : 29343895 : if (!gimple_assign_single_p (stmt)
1503 : : /* Scope clobbers don't influence scalarization. */
1504 : 29343895 : || gimple_clobber_p (stmt))
1505 : : return false;
1506 : :
1507 : 19402449 : lhs = gimple_assign_lhs (stmt);
1508 : 19402449 : rhs = gimple_assign_rhs1 (stmt);
1509 : :
1510 : 19402449 : if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
1511 : : return false;
1512 : :
1513 : 19402449 : racc = build_access_from_expr_1 (rhs, stmt, false);
1514 : 19402449 : lacc = build_access_from_expr_1 (lhs, stmt, true);
1515 : :
1516 : 19402449 : if (lacc)
1517 : : {
1518 : 6089271 : lacc->grp_assignment_write = 1;
1519 : 6089271 : if (storage_order_barrier_p (rhs))
1520 : 1 : lacc->grp_unscalarizable_region = 1;
1521 : :
1522 : 6089271 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type))
1523 : : {
1524 : 1941602 : bool type_changing_p = false;
1525 : 1941602 : contains_vce_or_bfcref_p (lhs, &type_changing_p);
1526 : 1941602 : if (type_changing_p)
1527 : 116064 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1528 : 58032 : DECL_UID (lacc->base));
1529 : : }
1530 : : }
1531 : :
1532 : 19402449 : if (racc)
1533 : : {
1534 : 5110894 : racc->grp_assignment_read = 1;
1535 : 5110894 : if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type))
1536 : : {
1537 : 1755492 : bool type_changing_p = false;
1538 : 1755492 : contains_vce_or_bfcref_p (rhs, &type_changing_p);
1539 : :
1540 : 3301117 : if (type_changing_p || gimple_has_volatile_ops (stmt))
1541 : 420452 : bitmap_set_bit (cannot_scalarize_away_bitmap,
1542 : 210226 : DECL_UID (racc->base));
1543 : : else
1544 : 3090532 : bitmap_set_bit (should_scalarize_away_bitmap,
1545 : 1545266 : DECL_UID (racc->base));
1546 : : }
1547 : 5110894 : if (storage_order_barrier_p (lhs))
1548 : 0 : racc->grp_unscalarizable_region = 1;
1549 : : }
1550 : :
1551 : 19402449 : if (lacc && racc
1552 : 1373868 : && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1553 : 1373868 : && !lacc->grp_unscalarizable_region
1554 : 1373420 : && !racc->grp_unscalarizable_region
1555 : 1372815 : && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1556 : 1372815 : && lacc->size == racc->size
1557 : 20775178 : && useless_type_conversion_p (lacc->type, racc->type))
1558 : : {
1559 : 1179348 : struct assign_link *link;
1560 : :
1561 : 1179348 : link = assign_link_pool.allocate ();
1562 : 1179348 : memset (link, 0, sizeof (struct assign_link));
1563 : :
1564 : 1179348 : link->lacc = lacc;
1565 : 1179348 : link->racc = racc;
1566 : 1179348 : add_link_to_rhs (racc, link);
1567 : 1179348 : add_link_to_lhs (lacc, link);
1568 : 1179348 : add_access_to_rhs_work_queue (racc);
1569 : 1179348 : add_access_to_lhs_work_queue (lacc);
1570 : :
1571 : : /* Let's delay marking the areas as written until propagation of accesses
1572 : : across link, unless the nature of rhs tells us that its data comes
1573 : : from elsewhere. */
1574 : 1179348 : if (!comes_initialized_p (racc->base))
1575 : 1085536 : lacc->write = false;
1576 : : }
1577 : :
1578 : 19402449 : return lacc || racc;
1579 : : }
1580 : :
1581 : : /* Callback of walk_stmt_load_store_addr_ops visit_addr used to detect taking
1582 : : addresses of candidates a places which are not call arguments. Such
1583 : : candidates are disqalified from SRA. This also applies to GIMPLE_ASM
1584 : : operands with memory constrains which cannot be scalarized. */
1585 : :
1586 : : static bool
1587 : 2089449 : scan_visit_addr (gimple *, tree op, tree, void *)
1588 : : {
1589 : 2089449 : op = get_base_address (op);
1590 : 2089449 : if (op
1591 : 2089449 : && DECL_P (op))
1592 : 1121387 : disqualify_candidate (op, "Address taken in a non-call-argument context.");
1593 : :
1594 : 2089449 : return false;
1595 : : }
1596 : :
1597 : : /* Scan function and look for interesting expressions and create access
1598 : : structures for them. Return true iff any access is created. */
1599 : :
1600 : : static bool
1601 : 699509 : scan_function (void)
1602 : : {
1603 : 699509 : basic_block bb;
1604 : 699509 : bool ret = false;
1605 : :
1606 : 11864541 : FOR_EACH_BB_FN (bb, cfun)
1607 : : {
1608 : 11165032 : gimple_stmt_iterator gsi;
1609 : 15297154 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1610 : 4132122 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), NULL, NULL, NULL,
1611 : : scan_visit_addr);
1612 : :
1613 : 100399241 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1614 : : {
1615 : 78069177 : gimple *stmt = gsi_stmt (gsi);
1616 : 78069177 : tree t;
1617 : 78069177 : unsigned i;
1618 : :
1619 : 78069177 : if (gimple_code (stmt) != GIMPLE_CALL)
1620 : 72912529 : walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1621 : : scan_visit_addr);
1622 : :
1623 : 78069177 : switch (gimple_code (stmt))
1624 : : {
1625 : 690027 : case GIMPLE_RETURN:
1626 : 690027 : t = gimple_return_retval (as_a <greturn *> (stmt));
1627 : 690027 : if (t != NULL_TREE)
1628 : 422391 : ret |= build_access_from_expr (t, stmt, false);
1629 : : break;
1630 : :
1631 : 29343895 : case GIMPLE_ASSIGN:
1632 : 29343895 : ret |= build_accesses_from_assign (stmt);
1633 : 29343895 : break;
1634 : :
1635 : 5156648 : case GIMPLE_CALL:
1636 : 5156648 : {
1637 : 5156648 : enum out_edge_check oe_check = SRA_OUTGOING_EDGES_UNCHECKED;
1638 : 5156648 : gcall *call = as_a <gcall *> (stmt);
1639 : 15461576 : for (i = 0; i < gimple_call_num_args (call); i++)
1640 : : {
1641 : 10304928 : bool can_be_returned;
1642 : 10304928 : if (gimple_call_lhs (call))
1643 : : {
1644 : 4140487 : int af = gimple_call_arg_flags (call, i);
1645 : 4140487 : can_be_returned = !(af & EAF_NOT_RETURNED_DIRECTLY);
1646 : : }
1647 : : else
1648 : : can_be_returned = false;
1649 : 10304928 : ret |= build_access_from_call_arg (gimple_call_arg (call,
1650 : : i),
1651 : : stmt, can_be_returned,
1652 : : &oe_check);
1653 : : }
1654 : 5156648 : if (gimple_call_chain(stmt))
1655 : 40315 : ret |= build_access_from_call_arg (gimple_call_chain(call),
1656 : : stmt, false, &oe_check);
1657 : : }
1658 : :
1659 : 5156648 : t = gimple_call_lhs (stmt);
1660 : 5156648 : if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
1661 : : {
1662 : : /* If the STMT is a call to DEFERRED_INIT, avoid setting
1663 : : cannot_scalarize_away_bitmap. */
1664 : 2149191 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
1665 : 37 : ret |= !!build_access_from_expr_1 (t, stmt, true);
1666 : : else
1667 : 2149154 : ret |= build_access_from_expr (t, stmt, true);
1668 : : }
1669 : : break;
1670 : :
1671 : 9493 : case GIMPLE_ASM:
1672 : 9493 : {
1673 : 9493 : gasm *asm_stmt = as_a <gasm *> (stmt);
1674 : 18986 : if (stmt_ends_bb_p (asm_stmt)
1675 : 9510 : && !single_succ_p (gimple_bb (asm_stmt)))
1676 : : {
1677 : 32 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1678 : : {
1679 : 17 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1680 : 17 : disqualify_base_of_expr (t, "OP of asm goto.");
1681 : : }
1682 : 42 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1683 : : {
1684 : 27 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1685 : 27 : disqualify_base_of_expr (t, "OP of asm goto.");
1686 : : }
1687 : : }
1688 : : else
1689 : : {
1690 : 17738 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
1691 : : {
1692 : 8260 : t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1693 : 8260 : ret |= build_access_from_expr (t, asm_stmt, false);
1694 : : }
1695 : 17118 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
1696 : : {
1697 : 7640 : t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
1698 : 7640 : ret |= build_access_from_expr (t, asm_stmt, true);
1699 : : }
1700 : : }
1701 : : }
1702 : : break;
1703 : :
1704 : : default:
1705 : : break;
1706 : : }
1707 : : }
1708 : : }
1709 : :
1710 : 699509 : return ret;
1711 : : }
1712 : :
1713 : : /* Helper of QSORT function. There are pointers to accesses in the array. An
1714 : : access is considered smaller than another if it has smaller offset or if the
1715 : : offsets are the same but is size is bigger. */
1716 : :
1717 : : static int
1718 : 108698271 : compare_access_positions (const void *a, const void *b)
1719 : : {
1720 : 108698271 : const access_p *fp1 = (const access_p *) a;
1721 : 108698271 : const access_p *fp2 = (const access_p *) b;
1722 : 108698271 : const access_p f1 = *fp1;
1723 : 108698271 : const access_p f2 = *fp2;
1724 : :
1725 : 108698271 : if (f1->offset != f2->offset)
1726 : 95154580 : return f1->offset < f2->offset ? -1 : 1;
1727 : :
1728 : 44073136 : if (f1->size == f2->size)
1729 : : {
1730 : 29990492 : if (f1->type == f2->type)
1731 : : return 0;
1732 : : /* Put any non-aggregate type before any aggregate type. */
1733 : 3854735 : else if (!is_gimple_reg_type (f1->type)
1734 : 3854735 : && is_gimple_reg_type (f2->type))
1735 : : return 1;
1736 : 2724258 : else if (is_gimple_reg_type (f1->type)
1737 : 2724258 : && !is_gimple_reg_type (f2->type))
1738 : : return -1;
1739 : : /* Put any complex or vector type before any other scalar type. */
1740 : 1216495 : else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1741 : 1216495 : && TREE_CODE (f1->type) != VECTOR_TYPE
1742 : 1162315 : && (TREE_CODE (f2->type) == COMPLEX_TYPE
1743 : 1162315 : || VECTOR_TYPE_P (f2->type)))
1744 : : return 1;
1745 : 1178031 : else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1746 : : || VECTOR_TYPE_P (f1->type))
1747 : 54180 : && TREE_CODE (f2->type) != COMPLEX_TYPE
1748 : 52559 : && TREE_CODE (f2->type) != VECTOR_TYPE)
1749 : : return -1;
1750 : : /* Put any integral type before any non-integral type. When splicing, we
1751 : : make sure that those with insufficient precision and occupying the
1752 : : same space are not scalarized. */
1753 : 1127274 : else if (INTEGRAL_TYPE_P (f1->type)
1754 : 295699 : && !INTEGRAL_TYPE_P (f2->type))
1755 : : return -1;
1756 : 1022690 : else if (!INTEGRAL_TYPE_P (f1->type)
1757 : 831575 : && INTEGRAL_TYPE_P (f2->type))
1758 : : return 1;
1759 : : /* Put the integral type with the bigger precision first. */
1760 : 916732 : else if (INTEGRAL_TYPE_P (f1->type)
1761 : 191115 : && INTEGRAL_TYPE_P (f2->type)
1762 : 1107847 : && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
1763 : 10131 : return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1764 : : /* Stabilize the sort. */
1765 : 906601 : return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1766 : : }
1767 : :
1768 : : /* We want the bigger accesses first, thus the opposite operator in the next
1769 : : line: */
1770 : 14082644 : return f1->size > f2->size ? -1 : 1;
1771 : : }
1772 : :
1773 : :
1774 : : /* Append a name of the declaration to the name obstack. A helper function for
1775 : : make_fancy_name. */
1776 : :
1777 : : static void
1778 : 1971514 : make_fancy_decl_name (tree decl)
1779 : : {
1780 : 1971514 : char buffer[32];
1781 : :
1782 : 1971514 : tree name = DECL_NAME (decl);
1783 : 1971514 : if (name)
1784 : 1907424 : obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1785 : : IDENTIFIER_LENGTH (name));
1786 : : else
1787 : : {
1788 : 64090 : sprintf (buffer, "D%u", DECL_UID (decl));
1789 : 64090 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1790 : : }
1791 : 1971514 : }
1792 : :
1793 : : /* Helper for make_fancy_name. */
1794 : :
1795 : : static void
1796 : 2148195 : make_fancy_name_1 (tree expr)
1797 : : {
1798 : 2280256 : char buffer[32];
1799 : 2280256 : tree index;
1800 : :
1801 : 2280256 : if (DECL_P (expr))
1802 : : {
1803 : 956092 : make_fancy_decl_name (expr);
1804 : 956092 : return;
1805 : : }
1806 : :
1807 : 1324164 : switch (TREE_CODE (expr))
1808 : : {
1809 : 1015422 : case COMPONENT_REF:
1810 : 1015422 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1811 : 1015422 : obstack_1grow (&name_obstack, '$');
1812 : 1015422 : make_fancy_decl_name (TREE_OPERAND (expr, 1));
1813 : 1015422 : break;
1814 : :
1815 : 45663 : case ARRAY_REF:
1816 : 45663 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1817 : 45663 : obstack_1grow (&name_obstack, '$');
1818 : : /* Arrays with only one element may not have a constant as their
1819 : : index. */
1820 : 45663 : index = TREE_OPERAND (expr, 1);
1821 : 45663 : if (TREE_CODE (index) != INTEGER_CST)
1822 : : break;
1823 : 45560 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1824 : 45560 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1825 : 45560 : break;
1826 : :
1827 : 132061 : case BIT_FIELD_REF:
1828 : 132061 : case ADDR_EXPR:
1829 : 132061 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1830 : 132061 : break;
1831 : :
1832 : 130901 : case MEM_REF:
1833 : 130901 : make_fancy_name_1 (TREE_OPERAND (expr, 0));
1834 : 130901 : if (!integer_zerop (TREE_OPERAND (expr, 1)))
1835 : : {
1836 : 39958 : obstack_1grow (&name_obstack, '$');
1837 : 79916 : sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1838 : 39958 : TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1839 : 39958 : obstack_grow (&name_obstack, buffer, strlen (buffer));
1840 : : }
1841 : : break;
1842 : :
1843 : 0 : case REALPART_EXPR:
1844 : 0 : case IMAGPART_EXPR:
1845 : 0 : gcc_unreachable (); /* we treat these as scalars. */
1846 : : break;
1847 : : default:
1848 : : break;
1849 : : }
1850 : : }
1851 : :
1852 : : /* Create a human readable name for replacement variable of ACCESS. */
1853 : :
1854 : : static char *
1855 : 956209 : make_fancy_name (tree expr)
1856 : : {
1857 : 956209 : make_fancy_name_1 (expr);
1858 : 956209 : obstack_1grow (&name_obstack, '\0');
1859 : 956209 : return XOBFINISH (&name_obstack, char *);
1860 : : }
1861 : :
1862 : : /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1863 : : EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is
1864 : : something for which get_addr_base_and_unit_offset returns NULL, gsi must
1865 : : be non-NULL and is used to insert new statements either before or below
1866 : : the current one as specified by INSERT_AFTER. This function is not capable
1867 : : of handling bitfields. */
1868 : :
1869 : : tree
1870 : 1068589 : build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
1871 : : bool reverse, tree exp_type, gimple_stmt_iterator *gsi,
1872 : : bool insert_after)
1873 : : {
1874 : 1068589 : tree prev_base = base;
1875 : 1068589 : tree off;
1876 : 1068589 : tree mem_ref;
1877 : 1068589 : poly_int64 base_offset;
1878 : 1068589 : unsigned HOST_WIDE_INT misalign;
1879 : 1068589 : unsigned int align;
1880 : :
1881 : : /* Preserve address-space information. */
1882 : 1068589 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base));
1883 : 1068589 : if (as != TYPE_ADDR_SPACE (exp_type))
1884 : 8 : exp_type = build_qualified_type (exp_type,
1885 : 4 : TYPE_QUALS (exp_type)
1886 : 4 : | ENCODE_QUAL_ADDR_SPACE (as));
1887 : :
1888 : 1068589 : poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT);
1889 : 1068589 : get_object_alignment_1 (base, &align, &misalign);
1890 : 1068589 : base = get_addr_base_and_unit_offset (base, &base_offset);
1891 : :
1892 : : /* get_addr_base_and_unit_offset returns NULL for references with a variable
1893 : : offset such as array[var_index]. */
1894 : 1068589 : if (!base)
1895 : : {
1896 : 10282 : gassign *stmt;
1897 : 10282 : tree tmp, addr;
1898 : :
1899 : 10282 : gcc_checking_assert (gsi);
1900 : 10282 : tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base)));
1901 : 10282 : addr = build_fold_addr_expr (unshare_expr (prev_base));
1902 : 10282 : STRIP_USELESS_TYPE_CONVERSION (addr);
1903 : 10282 : stmt = gimple_build_assign (tmp, addr);
1904 : 10282 : gimple_set_location (stmt, loc);
1905 : 10282 : if (insert_after)
1906 : 5419 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1907 : : else
1908 : 4863 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1909 : :
1910 : 10282 : off = build_int_cst (reference_alias_ptr_type (prev_base), byte_offset);
1911 : 10282 : base = tmp;
1912 : : }
1913 : 1058307 : else if (TREE_CODE (base) == MEM_REF)
1914 : : {
1915 : 67026 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1916 : : base_offset + byte_offset);
1917 : 67026 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1918 : 67026 : base = unshare_expr (TREE_OPERAND (base, 0));
1919 : : }
1920 : : else
1921 : : {
1922 : 991281 : off = build_int_cst (reference_alias_ptr_type (prev_base),
1923 : : base_offset + byte_offset);
1924 : 991281 : base = build_fold_addr_expr (unshare_expr (base));
1925 : : }
1926 : :
1927 : 1068589 : unsigned int align_bound = known_alignment (misalign + offset);
1928 : 1068589 : if (align_bound != 0)
1929 : 744278 : align = MIN (align, align_bound);
1930 : 1068589 : if (align != TYPE_ALIGN (exp_type))
1931 : 263892 : exp_type = build_aligned_type (exp_type, align);
1932 : :
1933 : 1068589 : mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1934 : 1068589 : REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse;
1935 : 1068589 : if (TREE_THIS_VOLATILE (prev_base))
1936 : 6 : TREE_THIS_VOLATILE (mem_ref) = 1;
1937 : 1068589 : if (TREE_SIDE_EFFECTS (prev_base))
1938 : 62 : TREE_SIDE_EFFECTS (mem_ref) = 1;
1939 : 1068589 : return mem_ref;
1940 : : }
1941 : :
1942 : : /* Construct and return a memory reference that is equal to a portion of
1943 : : MODEL->expr but is based on BASE. If this cannot be done, return NULL. */
1944 : :
1945 : : static tree
1946 : 2460757 : build_reconstructed_reference (location_t, tree base, struct access *model)
1947 : : {
1948 : 2460757 : tree expr = model->expr;
1949 : : /* We have to make sure to start just below the outermost union. */
1950 : 2460757 : tree start_expr = expr;
1951 : 5480376 : while (handled_component_p (expr))
1952 : : {
1953 : 3019619 : if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == UNION_TYPE)
1954 : 17054 : start_expr = expr;
1955 : 3019619 : expr = TREE_OPERAND (expr, 0);
1956 : : }
1957 : :
1958 : : expr = start_expr;
1959 : : tree prev_expr = NULL_TREE;
1960 : 5414339 : while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
1961 : : {
1962 : 3106147 : if (!handled_component_p (expr))
1963 : : return NULL_TREE;
1964 : 2953582 : prev_expr = expr;
1965 : 2953582 : expr = TREE_OPERAND (expr, 0);
1966 : : }
1967 : :
1968 : : /* Guard against broken VIEW_CONVERT_EXPRs... */
1969 : 2309280 : if (!prev_expr)
1970 : : return NULL_TREE;
1971 : :
1972 : 2308192 : TREE_OPERAND (prev_expr, 0) = base;
1973 : 2308192 : tree ref = unshare_expr (model->expr);
1974 : 2308192 : TREE_OPERAND (prev_expr, 0) = expr;
1975 : 2308192 : return ref;
1976 : : }
1977 : :
1978 : : /* Construct a memory reference to a part of an aggregate BASE at the given
1979 : : OFFSET and of the same type as MODEL. In case this is a reference to a
1980 : : bit-field, the function will replicate the last component_ref of model's
1981 : : expr to access it. INSERT_AFTER and GSI have the same meaning as in
1982 : : build_ref_for_offset, furthermore, when GSI is NULL, the function expects
1983 : : that it re-builds the entire reference from a DECL to the final access and
1984 : : so will create a MEM_REF when OFFSET does not exactly match offset of
1985 : : MODEL. */
1986 : :
1987 : : static tree
1988 : 3312817 : build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1989 : : struct access *model, gimple_stmt_iterator *gsi,
1990 : : bool insert_after)
1991 : : {
1992 : 3312817 : gcc_assert (offset >= 0);
1993 : 3312817 : if (TREE_CODE (model->expr) == COMPONENT_REF
1994 : 3312817 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
1995 : : {
1996 : : /* This access represents a bit-field. */
1997 : 10433 : tree t, exp_type, fld = TREE_OPERAND (model->expr, 1);
1998 : :
1999 : 10433 : offset -= int_bit_position (fld);
2000 : 10433 : exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0));
2001 : 10433 : t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type,
2002 : : gsi, insert_after);
2003 : : /* The flag will be set on the record type. */
2004 : 10433 : REF_REVERSE_STORAGE_ORDER (t) = 0;
2005 : 10433 : return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld,
2006 : 10433 : NULL_TREE);
2007 : : }
2008 : : else
2009 : : {
2010 : 3302384 : tree res;
2011 : 3302384 : if (model->grp_same_access_path
2012 : 2460830 : && !TREE_THIS_VOLATILE (base)
2013 : 2460824 : && (TYPE_ADDR_SPACE (TREE_TYPE (base))
2014 : 2460824 : == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
2015 : 2460820 : && (offset == model->offset
2016 : 17294 : || (gsi && offset <= model->offset))
2017 : : /* build_reconstructed_reference can still fail if we have already
2018 : : massaged BASE because of another type incompatibility. */
2019 : 5763141 : && (res = build_reconstructed_reference (loc, base, model)))
2020 : : return res;
2021 : : else
2022 : 994192 : return build_ref_for_offset (loc, base, offset, model->reverse,
2023 : : model->type, gsi, insert_after);
2024 : : }
2025 : : }
2026 : :
2027 : : /* Attempt to build a memory reference that we could but into a gimple
2028 : : debug_bind statement. Similar to build_ref_for_model but punts if it has to
2029 : : create statements and return s NULL instead. This function also ignores
2030 : : alignment issues and so its results should never end up in non-debug
2031 : : statements. */
2032 : :
2033 : : static tree
2034 : 682 : build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
2035 : : struct access *model)
2036 : : {
2037 : 682 : poly_int64 base_offset;
2038 : 682 : tree off;
2039 : :
2040 : 682 : if (TREE_CODE (model->expr) == COMPONENT_REF
2041 : 682 : && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1)))
2042 : : return NULL_TREE;
2043 : :
2044 : 682 : base = get_addr_base_and_unit_offset (base, &base_offset);
2045 : 682 : if (!base)
2046 : : return NULL_TREE;
2047 : 682 : if (TREE_CODE (base) == MEM_REF)
2048 : : {
2049 : 147 : off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
2050 : 147 : base_offset + offset / BITS_PER_UNIT);
2051 : 147 : off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
2052 : 147 : base = unshare_expr (TREE_OPERAND (base, 0));
2053 : : }
2054 : : else
2055 : : {
2056 : 535 : off = build_int_cst (reference_alias_ptr_type (base),
2057 : 535 : base_offset + offset / BITS_PER_UNIT);
2058 : 535 : base = build_fold_addr_expr (unshare_expr (base));
2059 : : }
2060 : :
2061 : 682 : return fold_build2_loc (loc, MEM_REF, model->type, base, off);
2062 : : }
2063 : :
2064 : : /* Construct a memory reference consisting of component_refs and array_refs to
2065 : : a part of an aggregate *RES (which is of type TYPE). The requested part
2066 : : should have type EXP_TYPE at be the given OFFSET. This function might not
2067 : : succeed, it returns true when it does and only then *RES points to something
2068 : : meaningful. This function should be used only to build expressions that we
2069 : : might need to present to user (e.g. in warnings). In all other situations,
2070 : : build_ref_for_model or build_ref_for_offset should be used instead. */
2071 : :
2072 : : static bool
2073 : 2970169 : build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
2074 : : tree exp_type)
2075 : : {
2076 : 3015097 : while (1)
2077 : : {
2078 : 2992633 : tree fld;
2079 : 2992633 : tree tr_size, index, minidx;
2080 : 2992633 : HOST_WIDE_INT el_size;
2081 : :
2082 : 2992633 : if (offset == 0 && exp_type
2083 : 2992633 : && types_compatible_p (exp_type, type))
2084 : : return true;
2085 : :
2086 : 1777291 : switch (TREE_CODE (type))
2087 : : {
2088 : 1701381 : case UNION_TYPE:
2089 : 1701381 : case QUAL_UNION_TYPE:
2090 : 1701381 : case RECORD_TYPE:
2091 : 11990766 : for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
2092 : : {
2093 : 11951378 : HOST_WIDE_INT pos, size;
2094 : 11951378 : tree tr_pos, expr, *expr_ptr;
2095 : :
2096 : 11951378 : if (TREE_CODE (fld) != FIELD_DECL)
2097 : 10201393 : continue;
2098 : :
2099 : 2859795 : tr_pos = bit_position (fld);
2100 : 2859795 : if (!tr_pos || !tree_fits_uhwi_p (tr_pos))
2101 : 0 : continue;
2102 : 2859795 : pos = tree_to_uhwi (tr_pos);
2103 : 2859795 : gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
2104 : 2859795 : tr_size = DECL_SIZE (fld);
2105 : 2859795 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2106 : 0 : continue;
2107 : 2859795 : size = tree_to_uhwi (tr_size);
2108 : 2859795 : if (size == 0)
2109 : : {
2110 : 38079 : if (pos != offset)
2111 : 15590 : continue;
2112 : : }
2113 : 2821716 : else if (pos > offset || (pos + size) <= offset)
2114 : 1094220 : continue;
2115 : :
2116 : 1749985 : expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
2117 : : NULL_TREE);
2118 : 1749985 : expr_ptr = &expr;
2119 : 1749985 : if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
2120 : : offset - pos, exp_type))
2121 : : {
2122 : 1661993 : *res = expr;
2123 : 1661993 : return true;
2124 : : }
2125 : : }
2126 : : return false;
2127 : :
2128 : 22464 : case ARRAY_TYPE:
2129 : 22464 : tr_size = TYPE_SIZE (TREE_TYPE (type));
2130 : 22464 : if (!tr_size || !tree_fits_uhwi_p (tr_size))
2131 : : return false;
2132 : 22464 : el_size = tree_to_uhwi (tr_size);
2133 : :
2134 : 22464 : minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
2135 : 22464 : if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
2136 : : return false;
2137 : 22464 : index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
2138 : 22464 : if (!integer_zerop (minidx))
2139 : 566 : index = int_const_binop (PLUS_EXPR, index, minidx);
2140 : 22464 : *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
2141 : : NULL_TREE, NULL_TREE);
2142 : 22464 : offset = offset % el_size;
2143 : 22464 : type = TREE_TYPE (type);
2144 : 22464 : break;
2145 : :
2146 : 53446 : default:
2147 : 53446 : if (offset != 0)
2148 : : return false;
2149 : :
2150 : 50169 : if (exp_type)
2151 : : return false;
2152 : : else
2153 : : return true;
2154 : : }
2155 : 22464 : }
2156 : : }
2157 : :
2158 : : /* Print message to dump file why a variable was rejected. */
2159 : :
2160 : : static void
2161 : 13584823 : reject (tree var, const char *msg)
2162 : : {
2163 : 13584823 : if (dump_file && (dump_flags & TDF_DETAILS))
2164 : : {
2165 : 28 : fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
2166 : 28 : print_generic_expr (dump_file, var);
2167 : 28 : fprintf (dump_file, "\n");
2168 : : }
2169 : 13584823 : }
2170 : :
2171 : : /* Return true if VAR is a candidate for SRA. */
2172 : :
2173 : : static bool
2174 : 17430842 : maybe_add_sra_candidate (tree var)
2175 : : {
2176 : 17430842 : tree type = TREE_TYPE (var);
2177 : 17430842 : const char *msg;
2178 : 17430842 : tree_node **slot;
2179 : :
2180 : 17430842 : if (!AGGREGATE_TYPE_P (type))
2181 : : {
2182 : 12198923 : reject (var, "not aggregate");
2183 : 12198923 : return false;
2184 : : }
2185 : :
2186 : 5231919 : if ((is_global_var (var)
2187 : : /* There are cases where non-addressable variables fail the
2188 : : pt_solutions_check test, e.g in gcc.dg/uninit-40.c. */
2189 : 5032242 : || (TREE_ADDRESSABLE (var)
2190 : 1349016 : && pt_solution_includes (&cfun->gimple_df->escaped_return, var))
2191 : 3850165 : || (TREE_CODE (var) == RESULT_DECL
2192 : 0 : && !DECL_BY_REFERENCE (var)
2193 : 0 : && aggregate_value_p (var, current_function_decl)))
2194 : : /* Allow constant-pool entries that "need to live in memory". */
2195 : 6413996 : && !constant_decl_p (var))
2196 : : {
2197 : 1379957 : reject (var, "needs to live in memory and escapes or global");
2198 : 1379957 : return false;
2199 : : }
2200 : 3851962 : if (TREE_THIS_VOLATILE (var))
2201 : : {
2202 : 576 : reject (var, "is volatile");
2203 : 576 : return false;
2204 : : }
2205 : 3851386 : if (!COMPLETE_TYPE_P (type))
2206 : : {
2207 : 0 : reject (var, "has incomplete type");
2208 : 0 : return false;
2209 : : }
2210 : 3851386 : if (!tree_fits_shwi_p (TYPE_SIZE (type)))
2211 : : {
2212 : 44 : reject (var, "type size not fixed");
2213 : 44 : return false;
2214 : : }
2215 : 3851342 : if (tree_to_shwi (TYPE_SIZE (type)) == 0)
2216 : : {
2217 : 5089 : reject (var, "type size is zero");
2218 : 5089 : return false;
2219 : : }
2220 : 3846253 : if (type_internals_preclude_sra_p (type, &msg))
2221 : : {
2222 : 234 : reject (var, msg);
2223 : 234 : return false;
2224 : : }
2225 : 3846019 : if (/* Fix for PR 41089. tree-stdarg.cc needs to have va_lists intact but
2226 : : we also want to schedule it rather late. Thus we ignore it in
2227 : : the early pass. */
2228 : 3846019 : (sra_mode == SRA_MODE_EARLY_INTRA
2229 : 3846019 : && is_va_list_type (type)))
2230 : : {
2231 : 0 : reject (var, "is va_list");
2232 : 0 : return false;
2233 : : }
2234 : :
2235 : 3846019 : bitmap_set_bit (candidate_bitmap, DECL_UID (var));
2236 : 3846019 : slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT);
2237 : 3846019 : *slot = var;
2238 : :
2239 : 3846019 : if (dump_file && (dump_flags & TDF_DETAILS))
2240 : : {
2241 : 14 : fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
2242 : 14 : print_generic_expr (dump_file, var);
2243 : 14 : fprintf (dump_file, "\n");
2244 : : }
2245 : :
2246 : : return true;
2247 : : }
2248 : :
2249 : : /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
2250 : : those with type which is suitable for scalarization. */
2251 : :
2252 : : static bool
2253 : 3206652 : find_var_candidates (void)
2254 : : {
2255 : 3206652 : tree var, parm;
2256 : 3206652 : unsigned int i;
2257 : 3206652 : bool ret = false;
2258 : :
2259 : 3206652 : for (parm = DECL_ARGUMENTS (current_function_decl);
2260 : 9968896 : parm;
2261 : 6762244 : parm = DECL_CHAIN (parm))
2262 : 6762244 : ret |= maybe_add_sra_candidate (parm);
2263 : :
2264 : 16638094 : FOR_EACH_LOCAL_DECL (cfun, i, var)
2265 : : {
2266 : 10665664 : if (!VAR_P (var))
2267 : 0 : continue;
2268 : :
2269 : 10665664 : ret |= maybe_add_sra_candidate (var);
2270 : : }
2271 : :
2272 : 3206652 : return ret;
2273 : : }
2274 : :
2275 : : /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
2276 : : ending either with a DECL or a MEM_REF with zero offset. */
2277 : :
2278 : : static bool
2279 : 9306772 : path_comparable_for_same_access (tree expr)
2280 : : {
2281 : 16705951 : while (handled_component_p (expr))
2282 : : {
2283 : 7509060 : if (TREE_CODE (expr) == ARRAY_REF)
2284 : : {
2285 : : /* SSA name indices can occur here too when the array is of sie one.
2286 : : But we cannot just re-use array_refs with SSA names elsewhere in
2287 : : the function, so disallow non-constant indices. TODO: Remove this
2288 : : limitation after teaching build_reconstructed_reference to replace
2289 : : the index with the index type lower bound. */
2290 : 566581 : if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
2291 : : return false;
2292 : : }
2293 : 7399179 : expr = TREE_OPERAND (expr, 0);
2294 : : }
2295 : :
2296 : 9196891 : if (TREE_CODE (expr) == MEM_REF)
2297 : : {
2298 : 728949 : if (!zerop (TREE_OPERAND (expr, 1)))
2299 : : return false;
2300 : : }
2301 : : else
2302 : 8467942 : gcc_assert (DECL_P (expr));
2303 : :
2304 : : return true;
2305 : : }
2306 : :
2307 : : /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
2308 : : true if the chain of these handled components are exactly the same as EXP2
2309 : : and the expression under them is the same DECL or an equivalent MEM_REF.
2310 : : The reference picked by compare_access_positions must go to EXP1. */
2311 : :
2312 : : static bool
2313 : 4292678 : same_access_path_p (tree exp1, tree exp2)
2314 : : {
2315 : 4292678 : if (TREE_CODE (exp1) != TREE_CODE (exp2))
2316 : : {
2317 : : /* Special case single-field structures loaded sometimes as the field
2318 : : and sometimes as the structure. If the field is of a scalar type,
2319 : : compare_access_positions will put it into exp1.
2320 : :
2321 : : TODO: The gimple register type condition can be removed if teach
2322 : : compare_access_positions to put inner types first. */
2323 : 402716 : if (is_gimple_reg_type (TREE_TYPE (exp1))
2324 : 391675 : && TREE_CODE (exp1) == COMPONENT_REF
2325 : 723158 : && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
2326 : 320442 : == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
2327 : 279295 : exp1 = TREE_OPERAND (exp1, 0);
2328 : : else
2329 : : return false;
2330 : : }
2331 : :
2332 : 4169257 : if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF))
2333 : : return false;
2334 : :
2335 : : return true;
2336 : : }
2337 : :
2338 : : /* Sort all accesses for the given variable, check for partial overlaps and
2339 : : return NULL if there are any. If there are none, pick a representative for
2340 : : each combination of offset and size and create a linked list out of them.
2341 : : Return the pointer to the first representative and make sure it is the first
2342 : : one in the vector of accesses. */
2343 : :
2344 : : static struct access *
2345 : 3745936 : sort_and_splice_var_accesses (tree var)
2346 : : {
2347 : 3745936 : int i, j, access_count;
2348 : 3745936 : struct access *res, **prev_acc_ptr = &res;
2349 : 3745936 : vec<access_p> *access_vec;
2350 : 3745936 : bool first = true;
2351 : 3745936 : HOST_WIDE_INT low = -1, high = 0;
2352 : :
2353 : 3745936 : access_vec = get_base_access_vector (var);
2354 : 3745936 : if (!access_vec)
2355 : : return NULL;
2356 : 3714157 : access_count = access_vec->length ();
2357 : :
2358 : : /* Sort by <OFFSET, SIZE>. */
2359 : 3714157 : access_vec->qsort (compare_access_positions);
2360 : :
2361 : : i = 0;
2362 : 12356141 : while (i < access_count)
2363 : : {
2364 : 8647135 : struct access *access = (*access_vec)[i];
2365 : 8647135 : bool grp_write = access->write;
2366 : 8647135 : bool grp_read = !access->write;
2367 : 8647135 : bool grp_scalar_write = access->write
2368 : 8647135 : && is_gimple_reg_type (access->type);
2369 : 8647135 : bool grp_scalar_read = !access->write
2370 : 8647135 : && is_gimple_reg_type (access->type);
2371 : 8647135 : bool grp_assignment_read = access->grp_assignment_read;
2372 : 8647135 : bool grp_assignment_write = access->grp_assignment_write;
2373 : 8647135 : bool multiple_scalar_reads = false;
2374 : 8647135 : bool grp_partial_lhs = access->grp_partial_lhs;
2375 : 8647135 : bool first_scalar = is_gimple_reg_type (access->type);
2376 : 8647135 : bool unscalarizable_region = access->grp_unscalarizable_region;
2377 : 8647135 : bool grp_same_access_path = true;
2378 : 8647135 : bool bf_non_full_precision
2379 : 8647135 : = (INTEGRAL_TYPE_P (access->type)
2380 : 2808413 : && TYPE_PRECISION (access->type) != access->size
2381 : 136481 : && TREE_CODE (access->expr) == COMPONENT_REF
2382 : 8705673 : && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1)));
2383 : :
2384 : 8647135 : if (first || access->offset >= high)
2385 : : {
2386 : 4088250 : first = false;
2387 : 4088250 : low = access->offset;
2388 : 4088250 : high = access->offset + access->size;
2389 : : }
2390 : 4558885 : else if (access->offset > low && access->offset + access->size > high)
2391 : : return NULL;
2392 : : else
2393 : 4558300 : gcc_assert (access->offset >= low
2394 : : && access->offset + access->size <= high);
2395 : :
2396 : 8646550 : if (INTEGRAL_TYPE_P (access->type)
2397 : 2807931 : && TYPE_PRECISION (access->type) != access->size
2398 : 8782583 : && bitmap_bit_p (passed_by_ref_in_call, DECL_UID (access->base)))
2399 : : {
2400 : : /* This can lead to performance regressions because we can generate
2401 : : excessive zero extensions. */
2402 : 4566 : if (dump_file && (dump_flags & TDF_DETAILS))
2403 : : {
2404 : 0 : fprintf (dump_file, "Won't scalarize ");
2405 : 0 : print_generic_expr (dump_file, access->base);
2406 : 0 : fprintf (dump_file, "(%d), it is passed by reference to a call "
2407 : : "and there are accesses with precision not covering "
2408 : 0 : "their type size.", DECL_UID (access->base));
2409 : : }
2410 : 4566 : return NULL;
2411 : : }
2412 : :
2413 : 8641984 : grp_same_access_path = path_comparable_for_same_access (access->expr);
2414 : :
2415 : 8641984 : j = i + 1;
2416 : 13305109 : while (j < access_count)
2417 : : {
2418 : 9596103 : struct access *ac2 = (*access_vec)[j];
2419 : 9596103 : if (ac2->offset != access->offset || ac2->size != access->size)
2420 : : break;
2421 : 4663125 : if (ac2->write)
2422 : : {
2423 : 981675 : grp_write = true;
2424 : 981675 : grp_scalar_write = (grp_scalar_write
2425 : 981675 : || is_gimple_reg_type (ac2->type));
2426 : : }
2427 : : else
2428 : : {
2429 : 3681450 : grp_read = true;
2430 : 3681450 : if (is_gimple_reg_type (ac2->type))
2431 : : {
2432 : 1472848 : if (grp_scalar_read)
2433 : : multiple_scalar_reads = true;
2434 : : else
2435 : 307394 : grp_scalar_read = true;
2436 : : }
2437 : : }
2438 : 4663125 : grp_assignment_read |= ac2->grp_assignment_read;
2439 : 4663125 : grp_assignment_write |= ac2->grp_assignment_write;
2440 : 4663125 : grp_partial_lhs |= ac2->grp_partial_lhs;
2441 : 4663125 : unscalarizable_region |= ac2->grp_unscalarizable_region;
2442 : 4663125 : relink_to_new_repr (access, ac2);
2443 : :
2444 : : /* If there are both aggregate-type and scalar-type accesses with
2445 : : this combination of size and offset, the comparison function
2446 : : should have put the scalars first. */
2447 : 4663125 : gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
2448 : : /* It also prefers integral types to non-integral. However, when the
2449 : : precision of the selected type does not span the entire area and
2450 : : should also be used for a non-integer (i.e. float), we must not
2451 : : let that happen. Normally analyze_access_subtree expands the type
2452 : : to cover the entire area but for bit-fields it doesn't. */
2453 : 4663125 : if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
2454 : : {
2455 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2456 : : {
2457 : 0 : fprintf (dump_file, "Cannot scalarize the following access "
2458 : : "because insufficient precision integer type was "
2459 : : "selected.\n ");
2460 : 0 : dump_access (dump_file, access, false);
2461 : : }
2462 : : unscalarizable_region = true;
2463 : : }
2464 : :
2465 : 4663125 : if (grp_same_access_path
2466 : 4663125 : && !same_access_path_p (access->expr, ac2->expr))
2467 : : grp_same_access_path = false;
2468 : :
2469 : 4663125 : ac2->group_representative = access;
2470 : 4663125 : j++;
2471 : : }
2472 : :
2473 : 8641984 : i = j;
2474 : :
2475 : 8641984 : access->group_representative = access;
2476 : 8641984 : access->grp_write = grp_write;
2477 : 8641984 : access->grp_read = grp_read;
2478 : 8641984 : access->grp_scalar_read = grp_scalar_read;
2479 : 8641984 : access->grp_scalar_write = grp_scalar_write;
2480 : 8641984 : access->grp_assignment_read = grp_assignment_read;
2481 : 8641984 : access->grp_assignment_write = grp_assignment_write;
2482 : 8641984 : access->grp_hint = multiple_scalar_reads && !constant_decl_p (var);
2483 : 8641984 : access->grp_partial_lhs = grp_partial_lhs;
2484 : 8641984 : access->grp_unscalarizable_region = unscalarizable_region;
2485 : 8641984 : access->grp_same_access_path = grp_same_access_path;
2486 : :
2487 : 8641984 : *prev_acc_ptr = access;
2488 : 8641984 : prev_acc_ptr = &access->next_grp;
2489 : : }
2490 : :
2491 : 3709006 : gcc_assert (res == (*access_vec)[0]);
2492 : : return res;
2493 : : }
2494 : :
2495 : : /* Create a variable for the given ACCESS which determines the type, name and a
2496 : : few other properties. Return the variable declaration and store it also to
2497 : : ACCESS->replacement. REG_TREE is used when creating a declaration to base a
2498 : : default-definition SSA name on in order to facilitate an uninitialized
2499 : : warning. It is used instead of the actual ACCESS type if that is not of a
2500 : : gimple register type. */
2501 : :
2502 : : static tree
2503 : 3924725 : create_access_replacement (struct access *access, tree reg_type = NULL_TREE)
2504 : : {
2505 : 3924725 : tree repl;
2506 : :
2507 : 3924725 : tree type = access->type;
2508 : 3924725 : if (reg_type && !is_gimple_reg_type (type))
2509 : : type = reg_type;
2510 : :
2511 : 3924725 : if (access->grp_to_be_debug_replaced)
2512 : : {
2513 : 116625 : repl = create_tmp_var_raw (access->type);
2514 : 116625 : DECL_CONTEXT (repl) = current_function_decl;
2515 : : }
2516 : : else
2517 : : /* Drop any special alignment on the type if it's not on the main
2518 : : variant. This avoids issues with weirdo ABIs like AAPCS. */
2519 : 3808100 : repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type),
2520 : 3808100 : TYPE_QUALS (type)), "SR");
2521 : 3924725 : if (access->grp_partial_lhs
2522 : 3924725 : && is_gimple_reg_type (type))
2523 : 681 : DECL_NOT_GIMPLE_REG_P (repl) = 1;
2524 : :
2525 : 3924725 : DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
2526 : 3924725 : DECL_ARTIFICIAL (repl) = 1;
2527 : 3924725 : DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
2528 : :
2529 : 3924725 : if (DECL_NAME (access->base)
2530 : 3031756 : && !DECL_IGNORED_P (access->base)
2531 : 4888103 : && !DECL_ARTIFICIAL (access->base))
2532 : : {
2533 : 956209 : char *pretty_name = make_fancy_name (access->expr);
2534 : 956209 : tree debug_expr = unshare_expr_without_location (access->expr), d;
2535 : 956209 : bool fail = false;
2536 : :
2537 : 956209 : DECL_NAME (repl) = get_identifier (pretty_name);
2538 : 956209 : DECL_NAMELESS (repl) = 1;
2539 : 956209 : obstack_free (&name_obstack, pretty_name);
2540 : :
2541 : : /* Get rid of any SSA_NAMEs embedded in debug_expr,
2542 : : as DECL_DEBUG_EXPR isn't considered when looking for still
2543 : : used SSA_NAMEs and thus they could be freed. All debug info
2544 : : generation cares is whether something is constant or variable
2545 : : and that get_ref_base_and_extent works properly on the
2546 : : expression. It cannot handle accesses at a non-constant offset
2547 : : though, so just give up in those cases. */
2548 : 1193453 : for (d = debug_expr;
2549 : 3236669 : !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF);
2550 : 1193453 : d = TREE_OPERAND (d, 0))
2551 : 1193453 : switch (TREE_CODE (d))
2552 : : {
2553 : 45780 : case ARRAY_REF:
2554 : 45780 : case ARRAY_RANGE_REF:
2555 : 45780 : if (TREE_OPERAND (d, 1)
2556 : 45780 : && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST)
2557 : : fail = true;
2558 : 45780 : if (TREE_OPERAND (d, 3)
2559 : 45780 : && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST)
2560 : : fail = true;
2561 : : /* FALLTHRU */
2562 : 1061392 : case COMPONENT_REF:
2563 : 1061392 : if (TREE_OPERAND (d, 2)
2564 : 1061392 : && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST)
2565 : : fail = true;
2566 : : break;
2567 : 130901 : case MEM_REF:
2568 : 130901 : if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR)
2569 : : fail = true;
2570 : : else
2571 : 130901 : d = TREE_OPERAND (d, 0);
2572 : : break;
2573 : : default:
2574 : : break;
2575 : : }
2576 : 956209 : if (!fail)
2577 : : {
2578 : 956106 : SET_DECL_DEBUG_EXPR (repl, debug_expr);
2579 : 956106 : DECL_HAS_DEBUG_EXPR_P (repl) = 1;
2580 : : }
2581 : 956209 : if (access->grp_no_warning)
2582 : 484 : suppress_warning (repl /* Be more selective! */);
2583 : : else
2584 : 955725 : copy_warning (repl, access->base);
2585 : : }
2586 : : else
2587 : 2968516 : suppress_warning (repl /* Be more selective! */);
2588 : :
2589 : 3924725 : if (dump_file)
2590 : : {
2591 : 159 : if (access->grp_to_be_debug_replaced)
2592 : : {
2593 : 4 : fprintf (dump_file, "Created a debug-only replacement for ");
2594 : 4 : print_generic_expr (dump_file, access->base);
2595 : 4 : fprintf (dump_file, " offset: %u, size: %u\n",
2596 : 4 : (unsigned) access->offset, (unsigned) access->size);
2597 : : }
2598 : : else
2599 : : {
2600 : 155 : fprintf (dump_file, "Created a replacement for ");
2601 : 155 : print_generic_expr (dump_file, access->base);
2602 : 155 : fprintf (dump_file, " offset: %u, size: %u: ",
2603 : 155 : (unsigned) access->offset, (unsigned) access->size);
2604 : 155 : print_generic_expr (dump_file, repl, TDF_UID);
2605 : 155 : fprintf (dump_file, "\n");
2606 : : }
2607 : : }
2608 : 3924725 : sra_stats.replacements++;
2609 : :
2610 : 3924725 : return repl;
2611 : : }
2612 : :
2613 : : /* Return ACCESS scalar replacement, which must exist. */
2614 : :
2615 : : static inline tree
2616 : 12644396 : get_access_replacement (struct access *access)
2617 : : {
2618 : 12644396 : gcc_checking_assert (access->replacement_decl);
2619 : 12644396 : return access->replacement_decl;
2620 : : }
2621 : :
2622 : :
2623 : : /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2624 : : linked list along the way. Stop when *ACCESS is NULL or the access pointed
2625 : : to it is not "within" the root. Return false iff some accesses partially
2626 : : overlap. */
2627 : :
2628 : : static bool
2629 : 8622597 : build_access_subtree (struct access **access)
2630 : : {
2631 : 8622597 : struct access *root = *access, *last_child = NULL;
2632 : 8622597 : HOST_WIDE_INT limit = root->offset + root->size;
2633 : :
2634 : 8622597 : *access = (*access)->next_grp;
2635 : 13159627 : while (*access && (*access)->offset + (*access)->size <= limit)
2636 : : {
2637 : 4539509 : if (!last_child)
2638 : 1833030 : root->first_child = *access;
2639 : : else
2640 : 2706479 : last_child->next_sibling = *access;
2641 : 4539509 : last_child = *access;
2642 : 4539509 : (*access)->parent = root;
2643 : 4539509 : (*access)->grp_write |= root->grp_write;
2644 : :
2645 : 4539509 : if (!build_access_subtree (access))
2646 : : return false;
2647 : : }
2648 : :
2649 : 8620118 : if (*access && (*access)->offset < limit)
2650 : : return false;
2651 : :
2652 : : return true;
2653 : : }
2654 : :
2655 : : /* Build a tree of access representatives, ACCESS is the pointer to the first
2656 : : one, others are linked in a list by the next_grp field. Return false iff
2657 : : some accesses partially overlap. */
2658 : :
2659 : : static bool
2660 : 3709006 : build_access_trees (struct access *access)
2661 : : {
2662 : 7789725 : while (access)
2663 : : {
2664 : 4083088 : struct access *root = access;
2665 : :
2666 : 4083088 : if (!build_access_subtree (&access))
2667 : : return false;
2668 : 4080719 : root->next_grp = access;
2669 : : }
2670 : : return true;
2671 : : }
2672 : :
2673 : : /* Traverse the access forest where ROOT is the first root and verify that
2674 : : various important invariants hold true. */
2675 : :
2676 : : DEBUG_FUNCTION void
2677 : 3706637 : verify_sra_access_forest (struct access *root)
2678 : : {
2679 : 3706637 : struct access *access = root;
2680 : 3706637 : tree first_base = root->base;
2681 : 3706637 : gcc_assert (DECL_P (first_base));
2682 : 10345267 : do
2683 : : {
2684 : 10345267 : gcc_assert (access->base == first_base);
2685 : 10345267 : if (access->parent)
2686 : 6264563 : gcc_assert (access->offset >= access->parent->offset
2687 : : && access->size <= access->parent->size);
2688 : 10345267 : if (access->next_sibling)
2689 : 3641396 : gcc_assert (access->next_sibling->offset
2690 : : >= access->offset + access->size);
2691 : :
2692 : 10345267 : poly_int64 poffset, psize, pmax_size;
2693 : 10345267 : bool reverse;
2694 : 10345267 : tree base = get_ref_base_and_extent (access->expr, &poffset, &psize,
2695 : : &pmax_size, &reverse);
2696 : 10345267 : HOST_WIDE_INT offset, size, max_size;
2697 : 10345267 : if (!poffset.is_constant (&offset)
2698 : 10345267 : || !psize.is_constant (&size)
2699 : 10345267 : || !pmax_size.is_constant (&max_size))
2700 : : gcc_unreachable ();
2701 : 10345267 : gcc_assert (base == first_base);
2702 : 10345267 : gcc_assert (offset == access->offset);
2703 : 10345267 : gcc_assert (access->grp_unscalarizable_region
2704 : : || access->grp_total_scalarization
2705 : : || size == max_size);
2706 : 10345267 : gcc_assert (access->grp_unscalarizable_region
2707 : : || !is_gimple_reg_type (access->type)
2708 : : || size == access->size);
2709 : 10345267 : gcc_assert (reverse == access->reverse);
2710 : :
2711 : 10345267 : if (access->first_child)
2712 : : {
2713 : 2623167 : gcc_assert (access->first_child->parent == access);
2714 : : access = access->first_child;
2715 : : }
2716 : 7722100 : else if (access->next_sibling)
2717 : : {
2718 : 3478455 : gcc_assert (access->next_sibling->parent == access->parent);
2719 : : access = access->next_sibling;
2720 : : }
2721 : : else
2722 : : {
2723 : 6866812 : while (access->parent && !access->next_sibling)
2724 : : access = access->parent;
2725 : 4243645 : if (access->next_sibling)
2726 : : access = access->next_sibling;
2727 : : else
2728 : : {
2729 : 4080704 : gcc_assert (access == root);
2730 : 4080704 : root = root->next_grp;
2731 : 4080704 : access = root;
2732 : : }
2733 : : }
2734 : : }
2735 : 10345267 : while (access);
2736 : 3706637 : }
2737 : :
2738 : : /* Verify access forests of all candidates with accesses by calling
2739 : : verify_access_forest on each on them. */
2740 : :
2741 : : DEBUG_FUNCTION void
2742 : 652308 : verify_all_sra_access_forests (void)
2743 : : {
2744 : 652308 : bitmap_iterator bi;
2745 : 652308 : unsigned i;
2746 : 4358945 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2747 : : {
2748 : 3706637 : tree var = candidate (i);
2749 : 3706637 : struct access *access = get_first_repr_for_decl (var);
2750 : 3706637 : if (access)
2751 : : {
2752 : 3706637 : gcc_assert (access->base == var);
2753 : 3706637 : verify_sra_access_forest (access);
2754 : : }
2755 : : }
2756 : 652308 : }
2757 : :
2758 : : /* Return true if expr contains some ARRAY_REFs into a variable bounded
2759 : : array. */
2760 : :
2761 : : static bool
2762 : 10109587 : expr_with_var_bounded_array_refs_p (tree expr)
2763 : : {
2764 : 18962559 : while (handled_component_p (expr))
2765 : : {
2766 : 8852972 : if (TREE_CODE (expr) == ARRAY_REF
2767 : 8852972 : && !tree_fits_shwi_p (array_ref_low_bound (expr)))
2768 : : return true;
2769 : 8852972 : expr = TREE_OPERAND (expr, 0);
2770 : : }
2771 : : return false;
2772 : : }
2773 : :
2774 : : /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2775 : : both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY
2776 : : is set, we are totally scalarizing the aggregate. Also set all sorts of
2777 : : access flags appropriately along the way, notably always set grp_read and
2778 : : grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is
2779 : : true.
2780 : :
2781 : : Creating a replacement for a scalar access is considered beneficial if its
2782 : : grp_hint ot TOTALLY is set (this means either that there is more than one
2783 : : direct read access or that we are attempting total scalarization) or
2784 : : according to the following table:
2785 : :
2786 : : Access written to through a scalar type (once or more times)
2787 : : |
2788 : : | Written to in an assignment statement
2789 : : | |
2790 : : | | Access read as scalar _once_
2791 : : | | |
2792 : : | | | Read in an assignment statement
2793 : : | | | |
2794 : : | | | | Scalarize Comment
2795 : : -----------------------------------------------------------------------------
2796 : : 0 0 0 0 No access for the scalar
2797 : : 0 0 0 1 No access for the scalar
2798 : : 0 0 1 0 No Single read - won't help
2799 : : 0 0 1 1 No The same case
2800 : : 0 1 0 0 No access for the scalar
2801 : : 0 1 0 1 No access for the scalar
2802 : : 0 1 1 0 Yes s = *g; return s.i;
2803 : : 0 1 1 1 Yes The same case as above
2804 : : 1 0 0 0 No Won't help
2805 : : 1 0 0 1 Yes s.i = 1; *g = s;
2806 : : 1 0 1 0 Yes s.i = 5; g = s.i;
2807 : : 1 0 1 1 Yes The same case as above
2808 : : 1 1 0 0 No Won't help.
2809 : : 1 1 0 1 Yes s.i = 1; *g = s;
2810 : : 1 1 1 0 Yes s = *g; return s.i;
2811 : : 1 1 1 1 Yes Any of the above yeses */
2812 : :
2813 : : static bool
2814 : 10345267 : analyze_access_subtree (struct access *root, struct access *parent,
2815 : : bool allow_replacements, bool totally)
2816 : : {
2817 : 10345267 : struct access *child;
2818 : 10345267 : HOST_WIDE_INT limit = root->offset + root->size;
2819 : 10345267 : HOST_WIDE_INT covered_to = root->offset;
2820 : 10345267 : bool scalar = is_gimple_reg_type (root->type);
2821 : 10345267 : bool hole = false, sth_created = false;
2822 : :
2823 : 10345267 : if (parent)
2824 : : {
2825 : 6264563 : if (parent->grp_read)
2826 : 5112302 : root->grp_read = 1;
2827 : 6264563 : if (parent->grp_assignment_read)
2828 : 2601771 : root->grp_assignment_read = 1;
2829 : 6264563 : if (parent->grp_write)
2830 : 3587926 : root->grp_write = 1;
2831 : 6264563 : if (parent->grp_assignment_write)
2832 : 3095453 : root->grp_assignment_write = 1;
2833 : 6264563 : if (!parent->grp_same_access_path)
2834 : 274191 : root->grp_same_access_path = 0;
2835 : : }
2836 : :
2837 : 10345267 : if (root->grp_unscalarizable_region)
2838 : : allow_replacements = false;
2839 : :
2840 : 10236307 : if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2841 : : allow_replacements = false;
2842 : :
2843 : 10345267 : if (!totally && root->grp_result_of_prop_from_lhs)
2844 : 10345267 : allow_replacements = false;
2845 : :
2846 : 16609830 : for (child = root->first_child; child; child = child->next_sibling)
2847 : : {
2848 : 6264563 : hole |= covered_to < child->offset;
2849 : 6264563 : sth_created |= analyze_access_subtree (child, root,
2850 : 6264563 : allow_replacements && !scalar
2851 : 6264563 : && !root->grp_partial_lhs,
2852 : : totally);
2853 : :
2854 : 6264563 : root->grp_unscalarized_data |= child->grp_unscalarized_data;
2855 : 6264563 : if (child->grp_covered)
2856 : 3511922 : covered_to += child->size;
2857 : : else
2858 : : hole = true;
2859 : : }
2860 : :
2861 : 10345267 : if (allow_replacements && scalar && !root->first_child
2862 : 6628592 : && (totally || !root->grp_total_scalarization)
2863 : : && (totally
2864 : 4494060 : || root->grp_hint
2865 : 3848714 : || ((root->grp_scalar_read || root->grp_assignment_read)
2866 : 1417732 : && (root->grp_scalar_write || root->grp_assignment_write))))
2867 : : {
2868 : : /* Always create access replacements that cover the whole access.
2869 : : For integral types this means the precision has to match.
2870 : : Avoid assumptions based on the integral type kind, too. */
2871 : 3807591 : if (INTEGRAL_TYPE_P (root->type)
2872 : 1646023 : && ((TREE_CODE (root->type) != INTEGER_TYPE
2873 : 1646023 : && TREE_CODE (root->type) != BITINT_TYPE)
2874 : 1581699 : || TYPE_PRECISION (root->type) != root->size)
2875 : : /* But leave bitfield accesses alone. */
2876 : 3871922 : && (TREE_CODE (root->expr) != COMPONENT_REF
2877 : 63531 : || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1))))
2878 : : {
2879 : 63964 : tree rt = root->type;
2880 : 63964 : gcc_assert ((root->offset % BITS_PER_UNIT) == 0
2881 : : && (root->size % BITS_PER_UNIT) == 0);
2882 : 63964 : if (TREE_CODE (root->type) == BITINT_TYPE)
2883 : 7 : root->type = build_bitint_type (root->size, TYPE_UNSIGNED (rt));
2884 : : else
2885 : 63957 : root->type = build_nonstandard_integer_type (root->size,
2886 : 63957 : TYPE_UNSIGNED (rt));
2887 : 127928 : root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base,
2888 : 63964 : root->offset, root->reverse,
2889 : : root->type, NULL, false);
2890 : :
2891 : 63964 : if (dump_file && (dump_flags & TDF_DETAILS))
2892 : : {
2893 : 0 : fprintf (dump_file, "Changing the type of a replacement for ");
2894 : 0 : print_generic_expr (dump_file, root->base);
2895 : 0 : fprintf (dump_file, " offset: %u, size: %u ",
2896 : 0 : (unsigned) root->offset, (unsigned) root->size);
2897 : 0 : fprintf (dump_file, " to an integer.\n");
2898 : : }
2899 : : }
2900 : :
2901 : 3807591 : root->grp_to_be_replaced = 1;
2902 : 3807591 : root->replacement_decl = create_access_replacement (root);
2903 : 3807591 : sth_created = true;
2904 : 3807591 : hole = false;
2905 : 3807591 : }
2906 : : else
2907 : : {
2908 : 6537676 : if (allow_replacements
2909 : 2828492 : && scalar && !root->first_child
2910 : 2821001 : && !root->grp_total_scalarization
2911 : 2821001 : && (root->grp_scalar_write || root->grp_assignment_write)
2912 : 8968658 : && !bitmap_bit_p (cannot_scalarize_away_bitmap,
2913 : 2430982 : DECL_UID (root->base)))
2914 : : {
2915 : 315723 : gcc_checking_assert (!root->grp_scalar_read
2916 : : && !root->grp_assignment_read);
2917 : 315723 : sth_created = true;
2918 : 315723 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2919 : : {
2920 : 116625 : root->grp_to_be_debug_replaced = 1;
2921 : 116625 : root->replacement_decl = create_access_replacement (root);
2922 : : }
2923 : : }
2924 : :
2925 : 6537676 : if (covered_to < limit)
2926 : 5215735 : hole = true;
2927 : 6537676 : if (scalar || !allow_replacements)
2928 : 3194801 : root->grp_total_scalarization = 0;
2929 : : }
2930 : :
2931 : 10345267 : if (!hole || totally)
2932 : 5204992 : root->grp_covered = 1;
2933 : 5140275 : else if (root->grp_write || comes_initialized_p (root->base))
2934 : 4432202 : root->grp_unscalarized_data = 1; /* not covered and written to */
2935 : 10345267 : return sth_created;
2936 : : }
2937 : :
2938 : : /* Analyze all access trees linked by next_grp by the means of
2939 : : analyze_access_subtree. */
2940 : : static bool
2941 : 3706637 : analyze_access_trees (struct access *access)
2942 : : {
2943 : 3706637 : bool ret = false;
2944 : :
2945 : 7787341 : while (access)
2946 : : {
2947 : 4080704 : if (analyze_access_subtree (access, NULL, true,
2948 : 4080704 : access->grp_total_scalarization))
2949 : 2105454 : ret = true;
2950 : 4080704 : access = access->next_grp;
2951 : : }
2952 : :
2953 : 3706637 : return ret;
2954 : : }
2955 : :
2956 : : /* Return true iff a potential new child of ACC at offset OFFSET and with size
2957 : : SIZE would conflict with an already existing one. If exactly such a child
2958 : : already exists in ACC, store a pointer to it in EXACT_MATCH. */
2959 : :
2960 : : static bool
2961 : 6490048 : child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset,
2962 : : HOST_WIDE_INT size, struct access **exact_match)
2963 : : {
2964 : 6490048 : struct access *child;
2965 : :
2966 : 11266267 : for (child = acc->first_child; child; child = child->next_sibling)
2967 : : {
2968 : 10198609 : if (child->offset == norm_offset && child->size == size)
2969 : : {
2970 : 5400818 : *exact_match = child;
2971 : 5400818 : return true;
2972 : : }
2973 : :
2974 : 4797791 : if (child->offset < norm_offset + size
2975 : 4730275 : && child->offset + child->size > norm_offset)
2976 : : return true;
2977 : : }
2978 : :
2979 : : return false;
2980 : : }
2981 : :
2982 : : /* Create a new child access of PARENT, with all properties just like MODEL
2983 : : except for its offset and with its grp_write false and grp_read true.
2984 : : Return the new access or NULL if it cannot be created. Note that this
2985 : : access is created long after all splicing and sorting, it's not located in
2986 : : any access vector and is automatically a representative of its group. Set
2987 : : the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */
2988 : :
2989 : : static struct access *
2990 : 1063641 : create_artificial_child_access (struct access *parent, struct access *model,
2991 : : HOST_WIDE_INT new_offset,
2992 : : bool set_grp_read, bool set_grp_write)
2993 : : {
2994 : 1063641 : struct access **child;
2995 : 1063641 : tree expr = parent->base;
2996 : :
2997 : 1063641 : gcc_assert (!model->grp_unscalarizable_region);
2998 : :
2999 : 1063641 : struct access *access = access_pool.allocate ();
3000 : 1063641 : memset (access, 0, sizeof (struct access));
3001 : 1063641 : if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
3002 : : model->type))
3003 : : {
3004 : 4746 : access->grp_no_warning = true;
3005 : 4746 : expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
3006 : : new_offset, model, NULL, false);
3007 : : }
3008 : :
3009 : 1063641 : access->base = parent->base;
3010 : 1063641 : access->expr = expr;
3011 : 1063641 : access->offset = new_offset;
3012 : 1063641 : access->size = model->size;
3013 : 1063641 : access->type = model->type;
3014 : 1063641 : access->parent = parent;
3015 : 1063641 : access->grp_read = set_grp_read;
3016 : 1063641 : access->grp_write = set_grp_write;
3017 : 1063641 : access->reverse = model->reverse;
3018 : :
3019 : 1063641 : child = &parent->first_child;
3020 : 1834971 : while (*child && (*child)->offset < new_offset)
3021 : 771330 : child = &(*child)->next_sibling;
3022 : :
3023 : 1063641 : access->next_sibling = *child;
3024 : 1063641 : *child = access;
3025 : :
3026 : 1063641 : return access;
3027 : : }
3028 : :
3029 : :
3030 : : /* Beginning with ACCESS, traverse its whole access subtree and mark all
3031 : : sub-trees as written to. If any of them has not been marked so previously
3032 : : and has assignment links leading from it, re-enqueue it. */
3033 : :
3034 : : static void
3035 : 997288 : subtree_mark_written_and_rhs_enqueue (struct access *access)
3036 : : {
3037 : 997288 : if (access->grp_write)
3038 : : return;
3039 : 968511 : access->grp_write = true;
3040 : 968511 : add_access_to_rhs_work_queue (access);
3041 : :
3042 : 968511 : struct access *child;
3043 : 1176066 : for (child = access->first_child; child; child = child->next_sibling)
3044 : 207555 : subtree_mark_written_and_rhs_enqueue (child);
3045 : : }
3046 : :
3047 : : /* If there is still budget to create a propagation access for DECL, return
3048 : : true and decrement the budget. Otherwise return false. */
3049 : :
3050 : : static bool
3051 : 1067239 : budget_for_propagation_access (tree decl)
3052 : : {
3053 : 1067239 : unsigned b, *p = propagation_budget->get (decl);
3054 : 1067239 : if (p)
3055 : 593904 : b = *p;
3056 : : else
3057 : 473335 : b = param_sra_max_propagations;
3058 : :
3059 : 1067239 : if (b == 0)
3060 : : return false;
3061 : 1063645 : b--;
3062 : :
3063 : 1063645 : if (b == 0 && dump_file && (dump_flags & TDF_DETAILS))
3064 : : {
3065 : 0 : fprintf (dump_file, "The propagation budget of ");
3066 : 0 : print_generic_expr (dump_file, decl);
3067 : 0 : fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl));
3068 : : }
3069 : 1063645 : propagation_budget->put (decl, b);
3070 : 1063645 : return true;
3071 : : }
3072 : :
3073 : : /* Return true if ACC or any of its subaccesses has grp_child set. */
3074 : :
3075 : : static bool
3076 : 1731 : access_or_its_child_written (struct access *acc)
3077 : : {
3078 : 1731 : if (acc->grp_write)
3079 : : return true;
3080 : 1789 : for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling)
3081 : 413 : if (access_or_its_child_written (sub))
3082 : : return true;
3083 : : return false;
3084 : : }
3085 : :
3086 : : /* Propagate subaccesses and grp_write flags of RACC across an assignment link
3087 : : to LACC. Enqueue sub-accesses as necessary so that the write flag is
3088 : : propagated transitively. Return true if anything changed. Additionally, if
3089 : : RACC is a scalar access but LACC is not, change the type of the latter, if
3090 : : possible. */
3091 : :
3092 : : static bool
3093 : 3385416 : propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc)
3094 : : {
3095 : 3385416 : struct access *rchild;
3096 : 3385416 : HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
3097 : 3385416 : bool ret = false;
3098 : :
3099 : : /* IF the LHS is still not marked as being written to, we only need to do so
3100 : : if the RHS at this level actually was. */
3101 : 3385416 : if (!lacc->grp_write)
3102 : : {
3103 : 1254322 : gcc_checking_assert (!comes_initialized_p (racc->base));
3104 : 1254322 : if (racc->grp_write)
3105 : : {
3106 : 590890 : subtree_mark_written_and_rhs_enqueue (lacc);
3107 : 590890 : ret = true;
3108 : : }
3109 : : }
3110 : :
3111 : 3385416 : if (is_gimple_reg_type (lacc->type)
3112 : 2464369 : || lacc->grp_unscalarizable_region
3113 : 5849152 : || racc->grp_unscalarizable_region)
3114 : : {
3115 : 923024 : if (!lacc->grp_write)
3116 : : {
3117 : 65410 : ret = true;
3118 : 65410 : subtree_mark_written_and_rhs_enqueue (lacc);
3119 : : }
3120 : 923024 : return ret;
3121 : : }
3122 : :
3123 : 2462392 : if (is_gimple_reg_type (racc->type))
3124 : : {
3125 : 156903 : if (!lacc->grp_write)
3126 : : {
3127 : 1662 : ret = true;
3128 : 1662 : subtree_mark_written_and_rhs_enqueue (lacc);
3129 : : }
3130 : 156903 : if (!lacc->first_child && !racc->first_child)
3131 : : {
3132 : : /* We are about to change the access type from aggregate to scalar,
3133 : : so we need to put the reverse flag onto the access, if any. */
3134 : 156543 : const bool reverse
3135 : 156543 : = TYPE_REVERSE_STORAGE_ORDER (lacc->type)
3136 : 1 : && !POINTER_TYPE_P (racc->type)
3137 : 156543 : && !VECTOR_TYPE_P (racc->type);
3138 : 156543 : tree t = lacc->base;
3139 : :
3140 : 156543 : lacc->type = racc->type;
3141 : 156543 : if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
3142 : : lacc->offset, racc->type))
3143 : : {
3144 : 156447 : lacc->expr = t;
3145 : 156447 : lacc->grp_same_access_path = true;
3146 : : }
3147 : : else
3148 : : {
3149 : 96 : lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
3150 : : lacc->base, lacc->offset,
3151 : : racc, NULL, false);
3152 : 96 : if (TREE_CODE (lacc->expr) == MEM_REF)
3153 : 96 : REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse;
3154 : 96 : lacc->grp_no_warning = true;
3155 : 96 : lacc->grp_same_access_path = false;
3156 : : }
3157 : 156543 : lacc->reverse = reverse;
3158 : : }
3159 : 156903 : return ret;
3160 : : }
3161 : :
3162 : 5605453 : for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
3163 : : {
3164 : 3299964 : struct access *new_acc = NULL;
3165 : 3299964 : HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
3166 : :
3167 : 3299964 : if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size,
3168 : : &new_acc))
3169 : : {
3170 : 2700410 : if (new_acc)
3171 : : {
3172 : 2685109 : if (!new_acc->grp_write && rchild->grp_write)
3173 : : {
3174 : 128985 : gcc_assert (!lacc->grp_write);
3175 : 128985 : subtree_mark_written_and_rhs_enqueue (new_acc);
3176 : 128985 : ret = true;
3177 : : }
3178 : :
3179 : 2685109 : rchild->grp_hint = 1;
3180 : 2685109 : new_acc->grp_hint |= new_acc->grp_read;
3181 : 2685109 : if (rchild->first_child
3182 : 2685109 : && propagate_subaccesses_from_rhs (new_acc, rchild))
3183 : : {
3184 : 1274 : ret = 1;
3185 : 1274 : add_access_to_rhs_work_queue (new_acc);
3186 : : }
3187 : : }
3188 : : else
3189 : : {
3190 : 15301 : if (!lacc->grp_write)
3191 : : {
3192 : 2051 : ret = true;
3193 : 2051 : subtree_mark_written_and_rhs_enqueue (lacc);
3194 : : }
3195 : : }
3196 : 2704407 : continue;
3197 : : }
3198 : :
3199 : 603551 : if (rchild->grp_unscalarizable_region
3200 : 599554 : || !budget_for_propagation_access (lacc->base))
3201 : : {
3202 : 3997 : if (!lacc->grp_write && access_or_its_child_written (rchild))
3203 : : {
3204 : 326 : ret = true;
3205 : 326 : subtree_mark_written_and_rhs_enqueue (lacc);
3206 : : }
3207 : 3997 : continue;
3208 : : }
3209 : :
3210 : 595557 : rchild->grp_hint = 1;
3211 : : /* Because get_ref_base_and_extent always includes padding in size for
3212 : : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3213 : : type, we might be actually attempting to here to create a child of the
3214 : : same type as the parent. */
3215 : 595557 : if (!types_compatible_p (lacc->type, rchild->type))
3216 : 595557 : new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
3217 : : false,
3218 : 595557 : (lacc->grp_write
3219 : 595557 : || rchild->grp_write));
3220 : : else
3221 : 0 : new_acc = lacc;
3222 : 595557 : gcc_checking_assert (new_acc);
3223 : 595557 : if (racc->first_child)
3224 : 595557 : propagate_subaccesses_from_rhs (new_acc, rchild);
3225 : :
3226 : 595557 : add_access_to_rhs_work_queue (lacc);
3227 : 595557 : ret = true;
3228 : : }
3229 : :
3230 : : return ret;
3231 : : }
3232 : :
3233 : : /* Propagate subaccesses of LACC across an assignment link to RACC if they
3234 : : should inhibit total scalarization of the corresponding area. No flags are
3235 : : being propagated in the process. Return true if anything changed. */
3236 : :
3237 : : static bool
3238 : 5310697 : propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc)
3239 : : {
3240 : 5310697 : if (is_gimple_reg_type (racc->type)
3241 : 1894967 : || lacc->grp_unscalarizable_region
3242 : 7204289 : || racc->grp_unscalarizable_region)
3243 : : return false;
3244 : :
3245 : : /* TODO: Do we want set some new racc flag to stop potential total
3246 : : scalarization if lacc is a scalar access (and none fo the two have
3247 : : children)? */
3248 : :
3249 : 1893590 : bool ret = false;
3250 : 1893590 : HOST_WIDE_INT norm_delta = racc->offset - lacc->offset;
3251 : 1893590 : for (struct access *lchild = lacc->first_child;
3252 : 5087436 : lchild;
3253 : 3193846 : lchild = lchild->next_sibling)
3254 : : {
3255 : 3193846 : struct access *matching_acc = NULL;
3256 : 3193846 : HOST_WIDE_INT norm_offset = lchild->offset + norm_delta;
3257 : :
3258 : 5919604 : if (lchild->grp_unscalarizable_region
3259 : 3190084 : || child_would_conflict_in_acc (racc, norm_offset, lchild->size,
3260 : : &matching_acc)
3261 : 3661950 : || !budget_for_propagation_access (racc->base))
3262 : : {
3263 : 2725758 : if (matching_acc
3264 : 2725758 : && propagate_subaccesses_from_lhs (lchild, matching_acc))
3265 : 195 : add_access_to_lhs_work_queue (matching_acc);
3266 : 2725758 : continue;
3267 : : }
3268 : :
3269 : : /* Because get_ref_base_and_extent always includes padding in size for
3270 : : accesses to DECLs but not necessarily for COMPONENT_REFs of the same
3271 : : type, we might be actually attempting to here to create a child of the
3272 : : same type as the parent. */
3273 : 468088 : if (!types_compatible_p (racc->type, lchild->type))
3274 : : {
3275 : 468084 : struct access *new_acc
3276 : 468084 : = create_artificial_child_access (racc, lchild, norm_offset,
3277 : : true, false);
3278 : 468084 : new_acc->grp_result_of_prop_from_lhs = 1;
3279 : 468084 : propagate_subaccesses_from_lhs (lchild, new_acc);
3280 : : }
3281 : : else
3282 : 4 : propagate_subaccesses_from_lhs (lchild, racc);
3283 : 468088 : ret = true;
3284 : : }
3285 : : return ret;
3286 : : }
3287 : :
3288 : : /* Propagate all subaccesses across assignment links. */
3289 : :
3290 : : static void
3291 : 652308 : propagate_all_subaccesses (void)
3292 : : {
3293 : 652308 : propagation_budget = new hash_map<tree, unsigned>;
3294 : 2162206 : while (rhs_work_queue_head)
3295 : : {
3296 : 1509898 : struct access *racc = pop_access_from_rhs_work_queue ();
3297 : 1509898 : struct assign_link *link;
3298 : :
3299 : 1509898 : if (racc->group_representative)
3300 : 1509441 : racc= racc->group_representative;
3301 : 1509898 : gcc_assert (racc->first_rhs_link);
3302 : :
3303 : 4286037 : for (link = racc->first_rhs_link; link; link = link->next_rhs)
3304 : : {
3305 : 2776139 : struct access *lacc = link->lacc;
3306 : :
3307 : 2776139 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3308 : 4692 : continue;
3309 : 2771447 : lacc = lacc->group_representative;
3310 : :
3311 : 2771447 : bool reque_parents = false;
3312 : 2771447 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3313 : : {
3314 : 1369 : if (!lacc->grp_write)
3315 : : {
3316 : 409 : subtree_mark_written_and_rhs_enqueue (lacc);
3317 : 409 : reque_parents = true;
3318 : : }
3319 : : }
3320 : 2770078 : else if (propagate_subaccesses_from_rhs (lacc, racc))
3321 : : reque_parents = true;
3322 : :
3323 : : if (reque_parents)
3324 : 1106910 : do
3325 : : {
3326 : 1106910 : add_access_to_rhs_work_queue (lacc);
3327 : 1106910 : lacc = lacc->parent;
3328 : : }
3329 : 1106910 : while (lacc);
3330 : : }
3331 : : }
3332 : :
3333 : 1834119 : while (lhs_work_queue_head)
3334 : : {
3335 : 1181811 : struct access *lacc = pop_access_from_lhs_work_queue ();
3336 : 1181811 : struct assign_link *link;
3337 : :
3338 : 1181811 : if (lacc->group_representative)
3339 : 1178824 : lacc = lacc->group_representative;
3340 : 1181811 : gcc_assert (lacc->first_lhs_link);
3341 : :
3342 : 1181811 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
3343 : 3207 : continue;
3344 : :
3345 : 3306005 : for (link = lacc->first_lhs_link; link; link = link->next_lhs)
3346 : : {
3347 : 2127401 : struct access *racc = link->racc;
3348 : :
3349 : 2127401 : if (racc->group_representative)
3350 : 2127127 : racc = racc->group_representative;
3351 : 2127401 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base)))
3352 : 501 : continue;
3353 : 2126900 : if (propagate_subaccesses_from_lhs (lacc, racc))
3354 : 236532 : add_access_to_lhs_work_queue (racc);
3355 : : }
3356 : : }
3357 : 1304616 : delete propagation_budget;
3358 : 652308 : }
3359 : :
3360 : : /* Return true if the forest beginning with ROOT does not contain
3361 : : unscalarizable regions or non-byte aligned accesses. */
3362 : :
3363 : : static bool
3364 : 987951 : can_totally_scalarize_forest_p (struct access *root)
3365 : : {
3366 : 987951 : struct access *access = root;
3367 : 2577965 : do
3368 : : {
3369 : 2577965 : if (access->grp_unscalarizable_region
3370 : 2576363 : || (access->offset % BITS_PER_UNIT) != 0
3371 : 2575609 : || (access->size % BITS_PER_UNIT) != 0
3372 : 5149950 : || (is_gimple_reg_type (access->type)
3373 : 1619274 : && access->first_child))
3374 : : return false;
3375 : :
3376 : 2571849 : if (access->first_child)
3377 : : access = access->first_child;
3378 : 1838057 : else if (access->next_sibling)
3379 : : access = access->next_sibling;
3380 : : else
3381 : : {
3382 : 1769629 : while (access->parent && !access->next_sibling)
3383 : : access = access->parent;
3384 : 1040616 : if (access->next_sibling)
3385 : : access = access->next_sibling;
3386 : : else
3387 : : {
3388 : 985601 : gcc_assert (access == root);
3389 : 985601 : root = root->next_grp;
3390 : 985601 : access = root;
3391 : : }
3392 : : }
3393 : : }
3394 : 2571849 : while (access);
3395 : : return true;
3396 : : }
3397 : :
3398 : : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3399 : : reference EXPR for total scalarization purposes and mark it as such. Within
3400 : : the children of PARENT, link it in between PTR and NEXT_SIBLING. */
3401 : :
3402 : : static struct access *
3403 : 664788 : create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos,
3404 : : HOST_WIDE_INT size, tree type, tree expr,
3405 : : struct access **ptr,
3406 : : struct access *next_sibling)
3407 : : {
3408 : 664788 : struct access *access = access_pool.allocate ();
3409 : 664788 : memset (access, 0, sizeof (struct access));
3410 : 664788 : access->base = parent->base;
3411 : 664788 : access->offset = pos;
3412 : 664788 : access->size = size;
3413 : 664788 : access->expr = expr;
3414 : 664788 : access->type = type;
3415 : 664788 : access->parent = parent;
3416 : 664788 : access->grp_write = parent->grp_write;
3417 : 664788 : access->grp_total_scalarization = 1;
3418 : 664788 : access->grp_hint = 1;
3419 : 664788 : access->grp_same_access_path = path_comparable_for_same_access (expr);
3420 : 664788 : access->reverse = reverse_storage_order_for_component_p (expr);
3421 : :
3422 : 664788 : access->next_sibling = next_sibling;
3423 : 664788 : *ptr = access;
3424 : 664788 : return access;
3425 : : }
3426 : :
3427 : : /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and
3428 : : reference EXPR for total scalarization purposes and mark it as such, link it
3429 : : at *PTR and reshape the tree so that those elements at *PTR and their
3430 : : siblings which fall within the part described by POS and SIZE are moved to
3431 : : be children of the new access. If a partial overlap is detected, return
3432 : : NULL. */
3433 : :
3434 : : static struct access *
3435 : 664788 : create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos,
3436 : : HOST_WIDE_INT size, tree type, tree expr,
3437 : : struct access **ptr)
3438 : : {
3439 : 664788 : struct access **p = ptr;
3440 : :
3441 : 793069 : while (*p && (*p)->offset < pos + size)
3442 : : {
3443 : 128281 : if ((*p)->offset + (*p)->size > pos + size)
3444 : : return NULL;
3445 : 128281 : p = &(*p)->next_sibling;
3446 : : }
3447 : :
3448 : 664788 : struct access *next_child = *ptr;
3449 : 664788 : struct access *new_acc
3450 : 664788 : = create_total_scalarization_access (parent, pos, size, type, expr,
3451 : : ptr, *p);
3452 : 664788 : if (p != ptr)
3453 : : {
3454 : 52569 : new_acc->first_child = next_child;
3455 : 52569 : *p = NULL;
3456 : 180850 : for (struct access *a = next_child; a; a = a->next_sibling)
3457 : 128281 : a->parent = new_acc;
3458 : : }
3459 : : return new_acc;
3460 : : }
3461 : :
3462 : : static bool totally_scalarize_subtree (struct access *root);
3463 : :
3464 : : /* Return true if INNER is either the same type as OUTER or if it is the type
3465 : : of a record field in OUTER at offset zero, possibly in nested
3466 : : sub-records. */
3467 : :
3468 : : static bool
3469 : 192574 : access_and_field_type_match_p (tree outer, tree inner)
3470 : : {
3471 : 192574 : if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner))
3472 : : return true;
3473 : 86 : if (TREE_CODE (outer) != RECORD_TYPE)
3474 : : return false;
3475 : 74 : tree fld = TYPE_FIELDS (outer);
3476 : 2003 : while (fld)
3477 : : {
3478 : 1944 : if (TREE_CODE (fld) == FIELD_DECL)
3479 : : {
3480 : 81 : if (!zerop (DECL_FIELD_OFFSET (fld)))
3481 : : return false;
3482 : 81 : if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner)
3483 : : return true;
3484 : 73 : if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE)
3485 : 66 : fld = TYPE_FIELDS (TREE_TYPE (fld));
3486 : : else
3487 : : return false;
3488 : : }
3489 : : else
3490 : 1863 : fld = DECL_CHAIN (fld);
3491 : : }
3492 : : return false;
3493 : : }
3494 : :
3495 : : /* Return type of total_should_skip_creating_access indicating whether a total
3496 : : scalarization access for a field/element should be created, whether it
3497 : : already exists or whether the entire total scalarization has to fail. */
3498 : :
3499 : : enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED};
3500 : :
3501 : : /* Do all the necessary steps in total scalarization when the given aggregate
3502 : : type has a TYPE at POS with the given SIZE should be put into PARENT and
3503 : : when we have processed all its siblings with smaller offsets up until and
3504 : : including LAST_SEEN_SIBLING (which can be NULL).
3505 : :
3506 : : If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as
3507 : : appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with
3508 : : creating a new access, TOTAL_FLD_DONE if access or accesses capable of
3509 : : representing the described part of the aggregate for the purposes of total
3510 : : scalarization already exist or TOTAL_FLD_FAILED if there is a problem which
3511 : : prevents total scalarization from happening at all. */
3512 : :
3513 : : static enum total_sra_field_state
3514 : 2207074 : total_should_skip_creating_access (struct access *parent,
3515 : : struct access **last_seen_sibling,
3516 : : tree type, HOST_WIDE_INT pos,
3517 : : HOST_WIDE_INT size)
3518 : : {
3519 : 2207074 : struct access *next_child;
3520 : 2207074 : if (!*last_seen_sibling)
3521 : 1033163 : next_child = parent->first_child;
3522 : : else
3523 : 1173911 : next_child = (*last_seen_sibling)->next_sibling;
3524 : :
3525 : : /* First, traverse the chain of siblings until it points to an access with
3526 : : offset at least equal to POS. Check all skipped accesses whether they
3527 : : span the POS boundary and if so, return with a failure. */
3528 : 2207087 : while (next_child && next_child->offset < pos)
3529 : : {
3530 : 13 : if (next_child->offset + next_child->size > pos)
3531 : : return TOTAL_FLD_FAILED;
3532 : 13 : *last_seen_sibling = next_child;
3533 : 13 : next_child = next_child->next_sibling;
3534 : : }
3535 : :
3536 : : /* Now check whether next_child has exactly the right POS and SIZE and if so,
3537 : : whether it can represent what we need and can be totally scalarized
3538 : : itself. */
3539 : 2207074 : if (next_child && next_child->offset == pos
3540 : 1594391 : && next_child->size == size)
3541 : : {
3542 : 1542167 : if (!is_gimple_reg_type (next_child->type)
3543 : 1542167 : && (!access_and_field_type_match_p (type, next_child->type)
3544 : 192496 : || !totally_scalarize_subtree (next_child)))
3545 : 78 : return TOTAL_FLD_FAILED;
3546 : :
3547 : 1542089 : *last_seen_sibling = next_child;
3548 : 1542089 : return TOTAL_FLD_DONE;
3549 : : }
3550 : :
3551 : : /* If the child we're looking at would partially overlap, we just cannot
3552 : : totally scalarize. */
3553 : : if (next_child
3554 : 76403 : && next_child->offset < pos + size
3555 : 52688 : && next_child->offset + next_child->size > pos + size)
3556 : : return TOTAL_FLD_FAILED;
3557 : :
3558 : 664838 : if (is_gimple_reg_type (type))
3559 : : {
3560 : : /* We don't scalarize accesses that are children of other scalar type
3561 : : accesses, so if we go on and create an access for a register type,
3562 : : there should not be any pre-existing children. There are rare cases
3563 : : where the requested type is a vector but we already have register
3564 : : accesses for all its elements which is equally good. Detect that
3565 : : situation or whether we need to bail out. */
3566 : :
3567 : : HOST_WIDE_INT covered = pos;
3568 : : bool skipping = false;
3569 : : while (next_child
3570 : 552783 : && next_child->offset + next_child->size <= pos + size)
3571 : : {
3572 : 176 : if (next_child->offset != covered
3573 : 176 : || !is_gimple_reg_type (next_child->type))
3574 : : return TOTAL_FLD_FAILED;
3575 : :
3576 : 176 : covered += next_child->size;
3577 : 176 : *last_seen_sibling = next_child;
3578 : 176 : next_child = next_child->next_sibling;
3579 : 176 : skipping = true;
3580 : : }
3581 : :
3582 : 552607 : if (skipping)
3583 : : {
3584 : 50 : if (covered != pos + size)
3585 : : return TOTAL_FLD_FAILED;
3586 : : else
3587 : : return TOTAL_FLD_DONE;
3588 : : }
3589 : : }
3590 : :
3591 : : return TOTAL_FLD_CREATE;
3592 : : }
3593 : :
3594 : : /* Go over sub-tree rooted in ROOT and attempt to create scalar accesses
3595 : : spanning all uncovered areas covered by ROOT, return false if the attempt
3596 : : failed. All created accesses will have grp_unscalarizable_region set (and
3597 : : should be ignored if the function returns false). */
3598 : :
3599 : : static bool
3600 : 1034345 : totally_scalarize_subtree (struct access *root)
3601 : : {
3602 : 1034345 : gcc_checking_assert (!root->grp_unscalarizable_region);
3603 : 1034345 : gcc_checking_assert (!is_gimple_reg_type (root->type));
3604 : :
3605 : 1034345 : struct access *last_seen_sibling = NULL;
3606 : :
3607 : 1034345 : switch (TREE_CODE (root->type))
3608 : : {
3609 : 1025160 : case RECORD_TYPE:
3610 : 12194816 : for (tree fld = TYPE_FIELDS (root->type); fld; fld = DECL_CHAIN (fld))
3611 : 11169825 : if (TREE_CODE (fld) == FIELD_DECL)
3612 : : {
3613 : 2220851 : tree ft = TREE_TYPE (fld);
3614 : 2220851 : HOST_WIDE_INT fsize = tree_to_uhwi (DECL_SIZE (fld));
3615 : 2220851 : if (!fsize)
3616 : 30848 : continue;
3617 : :
3618 : 2190003 : HOST_WIDE_INT pos = root->offset + int_bit_position (fld);
3619 : 2190003 : if (pos + fsize > root->offset + root->size)
3620 : : return false;
3621 : 2190003 : enum total_sra_field_state
3622 : 2190003 : state = total_should_skip_creating_access (root,
3623 : : &last_seen_sibling,
3624 : : ft, pos, fsize);
3625 : 2190003 : switch (state)
3626 : : {
3627 : : case TOTAL_FLD_FAILED:
3628 : : return false;
3629 : 1539297 : case TOTAL_FLD_DONE:
3630 : 1539297 : continue;
3631 : 650557 : case TOTAL_FLD_CREATE:
3632 : 650557 : break;
3633 : 0 : default:
3634 : 0 : gcc_unreachable ();
3635 : : }
3636 : :
3637 : 1301114 : struct access **p = (last_seen_sibling
3638 : 650557 : ? &last_seen_sibling->next_sibling
3639 : : : &root->first_child);
3640 : 650557 : tree nref = build3 (COMPONENT_REF, ft, root->expr, fld, NULL_TREE);
3641 : 650557 : struct access *new_child
3642 : 650557 : = create_total_access_and_reshape (root, pos, fsize, ft, nref, p);
3643 : 650557 : if (!new_child)
3644 : : return false;
3645 : :
3646 : 650557 : if (!is_gimple_reg_type (ft)
3647 : 650557 : && !totally_scalarize_subtree (new_child))
3648 : : return false;
3649 : 650537 : last_seen_sibling = new_child;
3650 : : }
3651 : : break;
3652 : 9185 : case ARRAY_TYPE:
3653 : 9185 : {
3654 : 9185 : tree elemtype = TREE_TYPE (root->type);
3655 : 9185 : HOST_WIDE_INT el_size;
3656 : 9185 : offset_int idx, max;
3657 : 9185 : if (!prepare_iteration_over_array_elts (root->type, &el_size,
3658 : : &idx, &max))
3659 : : break;
3660 : :
3661 : 9185 : for (HOST_WIDE_INT pos = root->offset;
3662 : 26248 : idx <= max;
3663 : 17063 : pos += el_size, ++idx)
3664 : : {
3665 : 17071 : enum total_sra_field_state
3666 : 17071 : state = total_should_skip_creating_access (root,
3667 : : &last_seen_sibling,
3668 : : elemtype, pos,
3669 : : el_size);
3670 : 17071 : switch (state)
3671 : : {
3672 : : case TOTAL_FLD_FAILED:
3673 : 8 : return false;
3674 : 2834 : case TOTAL_FLD_DONE:
3675 : 2834 : continue;
3676 : 14231 : case TOTAL_FLD_CREATE:
3677 : 14231 : break;
3678 : 0 : default:
3679 : 0 : gcc_unreachable ();
3680 : : }
3681 : :
3682 : 28462 : struct access **p = (last_seen_sibling
3683 : 14231 : ? &last_seen_sibling->next_sibling
3684 : : : &root->first_child);
3685 : 28462 : tree nref = build4 (ARRAY_REF, elemtype, root->expr,
3686 : 14231 : wide_int_to_tree (TYPE_DOMAIN (root->type),
3687 : : idx),
3688 : : NULL_TREE, NULL_TREE);
3689 : 14231 : struct access *new_child
3690 : 14231 : = create_total_access_and_reshape (root, pos, el_size, elemtype,
3691 : : nref, p);
3692 : 14231 : if (!new_child)
3693 : : return false;
3694 : :
3695 : 14231 : if (!is_gimple_reg_type (elemtype)
3696 : 14231 : && !totally_scalarize_subtree (new_child))
3697 : : return false;
3698 : 14229 : last_seen_sibling = new_child;
3699 : : }
3700 : : }
3701 : 9177 : break;
3702 : 0 : default:
3703 : 0 : gcc_unreachable ();
3704 : : }
3705 : : return true;
3706 : : }
3707 : :
3708 : : /* Get the total total scalarization size limit in the current function. */
3709 : :
3710 : : unsigned HOST_WIDE_INT
3711 : 658729 : sra_get_max_scalarization_size (void)
3712 : : {
3713 : 658729 : bool optimize_speed_p = !optimize_function_for_size_p (cfun);
3714 : : /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>,
3715 : : fall back to a target default. */
3716 : 658729 : unsigned HOST_WIDE_INT max_scalarization_size
3717 : 658729 : = get_move_ratio (optimize_speed_p) * UNITS_PER_WORD;
3718 : :
3719 : 658729 : if (optimize_speed_p)
3720 : : {
3721 : 640477 : if (OPTION_SET_P (param_sra_max_scalarization_size_speed))
3722 : 9 : max_scalarization_size = param_sra_max_scalarization_size_speed;
3723 : : }
3724 : : else
3725 : : {
3726 : 18252 : if (OPTION_SET_P (param_sra_max_scalarization_size_size))
3727 : 0 : max_scalarization_size = param_sra_max_scalarization_size_size;
3728 : : }
3729 : 658729 : max_scalarization_size *= BITS_PER_UNIT;
3730 : 658729 : return max_scalarization_size;
3731 : : }
3732 : :
3733 : : /* Go through all accesses collected throughout the (intraprocedural) analysis
3734 : : stage, exclude overlapping ones, identify representatives and build trees
3735 : : out of them, making decisions about scalarization on the way. Return true
3736 : : iff there are any to-be-scalarized variables after this stage. */
3737 : :
3738 : : static bool
3739 : 652308 : analyze_all_variable_accesses (void)
3740 : : {
3741 : 652308 : int res = 0;
3742 : 652308 : bitmap tmp = BITMAP_ALLOC (NULL);
3743 : 652308 : bitmap_iterator bi;
3744 : 652308 : unsigned i;
3745 : :
3746 : 652308 : bitmap_copy (tmp, candidate_bitmap);
3747 : 4398244 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3748 : : {
3749 : 3745936 : tree var = candidate (i);
3750 : 3745936 : struct access *access;
3751 : :
3752 : 3745936 : access = sort_and_splice_var_accesses (var);
3753 : 3745936 : if (!access || !build_access_trees (access))
3754 : 39299 : disqualify_candidate (var,
3755 : : "No or inhibitingly overlapping accesses.");
3756 : : }
3757 : :
3758 : 652308 : propagate_all_subaccesses ();
3759 : :
3760 : 652308 : unsigned HOST_WIDE_INT max_scalarization_size
3761 : 652308 : = sra_get_max_scalarization_size ();
3762 : 4358945 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
3763 : 3706637 : if (bitmap_bit_p (should_scalarize_away_bitmap, i)
3764 : 3706637 : && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
3765 : : {
3766 : 1076490 : tree var = candidate (i);
3767 : 1076490 : if (!VAR_P (var))
3768 : 77791 : continue;
3769 : :
3770 : 998699 : if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) > max_scalarization_size)
3771 : : {
3772 : 11970 : if (dump_file && (dump_flags & TDF_DETAILS))
3773 : : {
3774 : 0 : fprintf (dump_file, "Too big to totally scalarize: ");
3775 : 0 : print_generic_expr (dump_file, var);
3776 : 0 : fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
3777 : : }
3778 : 11970 : continue;
3779 : : }
3780 : :
3781 : 986729 : bool all_types_ok = true;
3782 : 986729 : for (struct access *access = get_first_repr_for_decl (var);
3783 : 1948563 : access;
3784 : 961834 : access = access->next_grp)
3785 : 987951 : if (!can_totally_scalarize_forest_p (access)
3786 : 1969786 : || !totally_scalarizable_type_p (access->type,
3787 : 981835 : constant_decl_p (var),
3788 : : 0, nullptr))
3789 : : {
3790 : : all_types_ok = false;
3791 : : break;
3792 : : }
3793 : 986729 : if (!all_types_ok)
3794 : 26117 : continue;
3795 : :
3796 : 960612 : if (dump_file && (dump_flags & TDF_DETAILS))
3797 : : {
3798 : 4 : fprintf (dump_file, "Will attempt to totally scalarize ");
3799 : 4 : print_generic_expr (dump_file, var);
3800 : 4 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3801 : : }
3802 : 960612 : bool scalarized = true;
3803 : 960612 : for (struct access *access = get_first_repr_for_decl (var);
3804 : 1922288 : access;
3805 : 961676 : access = access->next_grp)
3806 : 961831 : if (!is_gimple_reg_type (access->type)
3807 : 961831 : && !totally_scalarize_subtree (access))
3808 : : {
3809 : : scalarized = false;
3810 : : break;
3811 : : }
3812 : :
3813 : 960612 : if (scalarized)
3814 : 960457 : for (struct access *access = get_first_repr_for_decl (var);
3815 : 1922133 : access;
3816 : 961676 : access = access->next_grp)
3817 : 961676 : access->grp_total_scalarization = true;
3818 : : }
3819 : :
3820 : 652308 : if (flag_checking)
3821 : 652308 : verify_all_sra_access_forests ();
3822 : :
3823 : 652308 : bitmap_copy (tmp, candidate_bitmap);
3824 : 4358945 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
3825 : : {
3826 : 3706637 : tree var = candidate (i);
3827 : 3706637 : struct access *access = get_first_repr_for_decl (var);
3828 : :
3829 : 3706637 : if (analyze_access_trees (access))
3830 : : {
3831 : 1801429 : res++;
3832 : 1801429 : if (dump_file && (dump_flags & TDF_DETAILS))
3833 : : {
3834 : 9 : fprintf (dump_file, "\nAccess trees for ");
3835 : 9 : print_generic_expr (dump_file, var);
3836 : 9 : fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
3837 : 9 : dump_access_tree (dump_file, access);
3838 : 9 : fprintf (dump_file, "\n");
3839 : : }
3840 : : }
3841 : : else
3842 : 1905208 : disqualify_candidate (var, "No scalar replacements to be created.");
3843 : : }
3844 : :
3845 : 652308 : BITMAP_FREE (tmp);
3846 : :
3847 : 652308 : if (res)
3848 : : {
3849 : 395678 : statistics_counter_event (cfun, "Scalarized aggregates", res);
3850 : 395678 : return true;
3851 : : }
3852 : : else
3853 : : return false;
3854 : : }
3855 : :
3856 : : /* Generate statements copying scalar replacements of accesses within a subtree
3857 : : into or out of AGG. ACCESS, all its children, siblings and their children
3858 : : are to be processed. AGG is an aggregate type expression (can be a
3859 : : declaration but does not have to be, it can for example also be a mem_ref or
3860 : : a series of handled components). TOP_OFFSET is the offset of the processed
3861 : : subtree which has to be subtracted from offsets of individual accesses to
3862 : : get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only
3863 : : replacements in the interval <start_offset, start_offset + chunk_size>,
3864 : : otherwise copy all. GSI is a statement iterator used to place the new
3865 : : statements. WRITE should be true when the statements should write from AGG
3866 : : to the replacement and false if vice versa. if INSERT_AFTER is true, new
3867 : : statements will be added after the current statement in GSI, they will be
3868 : : added before the statement otherwise. */
3869 : :
3870 : : static void
3871 : 1627585 : generate_subtree_copies (struct access *access, tree agg,
3872 : : HOST_WIDE_INT top_offset,
3873 : : HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
3874 : : gimple_stmt_iterator *gsi, bool write,
3875 : : bool insert_after, location_t loc)
3876 : : {
3877 : : /* Never write anything into constant pool decls. See PR70602. */
3878 : 3255170 : if (!write && constant_decl_p (agg))
3879 : : return;
3880 : 3830121 : do
3881 : : {
3882 : 3830121 : if (chunk_size && access->offset >= start_offset + chunk_size)
3883 : : return;
3884 : :
3885 : 3830121 : if (access->grp_to_be_replaced
3886 : 3086380 : && (chunk_size == 0
3887 : 0 : || access->offset + access->size > start_offset))
3888 : : {
3889 : 3086380 : tree expr, repl = get_access_replacement (access);
3890 : 3086380 : gassign *stmt;
3891 : :
3892 : 3086380 : expr = build_ref_for_model (loc, agg, access->offset - top_offset,
3893 : : access, gsi, insert_after);
3894 : :
3895 : 3086380 : if (write)
3896 : : {
3897 : 1558882 : if (access->grp_partial_lhs)
3898 : 26 : expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
3899 : 26 : !insert_after,
3900 : : insert_after ? GSI_NEW_STMT
3901 : : : GSI_SAME_STMT);
3902 : 1558882 : stmt = gimple_build_assign (repl, expr);
3903 : : }
3904 : : else
3905 : : {
3906 : 1527498 : suppress_warning (repl /* Be more selective! */);
3907 : 1527498 : if (access->grp_partial_lhs)
3908 : 85 : repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
3909 : 85 : !insert_after,
3910 : : insert_after ? GSI_NEW_STMT
3911 : : : GSI_SAME_STMT);
3912 : 1527498 : stmt = gimple_build_assign (expr, repl);
3913 : : }
3914 : 3086380 : gimple_set_location (stmt, loc);
3915 : :
3916 : 3086380 : if (insert_after)
3917 : 1558882 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3918 : : else
3919 : 1527498 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3920 : 3086380 : update_stmt (stmt);
3921 : 3086380 : sra_stats.subtree_copies++;
3922 : 3086380 : }
3923 : 743741 : else if (write
3924 : 302520 : && access->grp_to_be_debug_replaced
3925 : 668 : && (chunk_size == 0
3926 : 0 : || access->offset + access->size > start_offset))
3927 : : {
3928 : 668 : gdebug *ds;
3929 : 1336 : tree drhs = build_debug_ref_for_model (loc, agg,
3930 : 668 : access->offset - top_offset,
3931 : : access);
3932 : 668 : ds = gimple_build_debug_bind (get_access_replacement (access),
3933 : : drhs, gsi_stmt (*gsi));
3934 : 668 : if (insert_after)
3935 : 668 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
3936 : : else
3937 : 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3938 : : }
3939 : :
3940 : 3830121 : if (access->first_child)
3941 : 368607 : generate_subtree_copies (access->first_child, agg, top_offset,
3942 : : start_offset, chunk_size, gsi,
3943 : : write, insert_after, loc);
3944 : :
3945 : 3830121 : access = access->next_sibling;
3946 : : }
3947 : 3830121 : while (access);
3948 : : }
3949 : :
3950 : : /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
3951 : : root of the subtree to be processed. GSI is the statement iterator used
3952 : : for inserting statements which are added after the current statement if
3953 : : INSERT_AFTER is true or before it otherwise. */
3954 : :
3955 : : static void
3956 : 532892 : init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
3957 : : bool insert_after, location_t loc)
3958 : :
3959 : : {
3960 : 532892 : struct access *child;
3961 : :
3962 : 532892 : if (access->grp_to_be_replaced)
3963 : : {
3964 : 263389 : gassign *stmt;
3965 : :
3966 : 263389 : stmt = gimple_build_assign (get_access_replacement (access),
3967 : : build_zero_cst (access->type));
3968 : 263389 : if (insert_after)
3969 : 22383 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
3970 : : else
3971 : 241006 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
3972 : 263389 : update_stmt (stmt);
3973 : 263389 : gimple_set_location (stmt, loc);
3974 : : }
3975 : 269503 : else if (access->grp_to_be_debug_replaced)
3976 : : {
3977 : 21220 : gdebug *ds
3978 : 21220 : = gimple_build_debug_bind (get_access_replacement (access),
3979 : : build_zero_cst (access->type),
3980 : : gsi_stmt (*gsi));
3981 : 21220 : if (insert_after)
3982 : 21220 : gsi_insert_after (gsi, ds, GSI_NEW_STMT);
3983 : : else
3984 : 0 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3985 : : }
3986 : :
3987 : 922851 : for (child = access->first_child; child; child = child->next_sibling)
3988 : 389959 : init_subtree_with_zero (child, gsi, insert_after, loc);
3989 : 532892 : }
3990 : :
3991 : : /* Clobber all scalar replacements in an access subtree. ACCESS is the
3992 : : root of the subtree to be processed. GSI is the statement iterator used
3993 : : for inserting statements which are added after the current statement if
3994 : : INSERT_AFTER is true or before it otherwise. */
3995 : :
3996 : : static void
3997 : 2718338 : clobber_subtree (struct access *access, gimple_stmt_iterator *gsi,
3998 : : bool insert_after, location_t loc)
3999 : :
4000 : : {
4001 : 2718338 : struct access *child;
4002 : :
4003 : 2718338 : if (access->grp_to_be_replaced)
4004 : : {
4005 : 1826388 : tree rep = get_access_replacement (access);
4006 : 1826388 : tree clobber = build_clobber (access->type);
4007 : 1826388 : gimple *stmt = gimple_build_assign (rep, clobber);
4008 : :
4009 : 1826388 : if (insert_after)
4010 : 272448 : gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
4011 : : else
4012 : 1553940 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
4013 : 1826388 : update_stmt (stmt);
4014 : 1826388 : gimple_set_location (stmt, loc);
4015 : : }
4016 : :
4017 : 4432547 : for (child = access->first_child; child; child = child->next_sibling)
4018 : 1714209 : clobber_subtree (child, gsi, insert_after, loc);
4019 : 2718338 : }
4020 : :
4021 : : /* Search for an access representative for the given expression EXPR and
4022 : : return it or NULL if it cannot be found. */
4023 : :
4024 : : static struct access *
4025 : 42356458 : get_access_for_expr (tree expr)
4026 : : {
4027 : 42356458 : poly_int64 poffset, psize, pmax_size;
4028 : 42356458 : HOST_WIDE_INT offset, max_size;
4029 : 42356458 : tree base;
4030 : 42356458 : bool reverse;
4031 : :
4032 : : /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
4033 : : a different size than the size of its argument and we need the latter
4034 : : one. */
4035 : 42356458 : if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
4036 : 250333 : expr = TREE_OPERAND (expr, 0);
4037 : :
4038 : 42356458 : base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size,
4039 : : &reverse);
4040 : 84608735 : if (!known_size_p (pmax_size)
4041 : 42252277 : || !pmax_size.is_constant (&max_size)
4042 : 42252277 : || !poffset.is_constant (&offset)
4043 : 42356458 : || !DECL_P (base))
4044 : : return NULL;
4045 : :
4046 : 20052230 : if (tree basesize = DECL_SIZE (base))
4047 : : {
4048 : 20012997 : poly_int64 sz;
4049 : 20012997 : if (offset < 0
4050 : 20012981 : || !poly_int_tree_p (basesize, &sz)
4051 : 40025978 : || known_le (sz, offset))
4052 : 5993 : return NULL;
4053 : : }
4054 : :
4055 : 20046237 : if (max_size == 0
4056 : 20046237 : || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
4057 : 11411595 : return NULL;
4058 : :
4059 : 8634642 : return get_var_base_offset_size_access (base, offset, max_size);
4060 : : }
4061 : :
4062 : : /* Replace the expression EXPR with a scalar replacement if there is one and
4063 : : generate other statements to do type conversion or subtree copying if
4064 : : necessary. WRITE is true if the expression is being written to (it is on a
4065 : : LHS of a statement or output in an assembly statement). STMT_GSI is used to
4066 : : place newly created statements before the processed statement, REFRESH_GSI
4067 : : is used to place them afterwards - unless the processed statement must end a
4068 : : BB in which case it is placed on the outgoing non-EH edge. REFRESH_GSI and
4069 : : is then used to continue iteration over the BB. If sra_modify_expr is
4070 : : called only once with WRITE equal to true on a given statement, both
4071 : : iterator parameters can point to the same one. */
4072 : :
4073 : : static bool
4074 : 7078157 : sra_modify_expr (tree *expr, bool write, gimple_stmt_iterator *stmt_gsi,
4075 : : gimple_stmt_iterator *refresh_gsi)
4076 : : {
4077 : 7078157 : location_t loc;
4078 : 7078157 : struct access *access;
4079 : 7078157 : tree type, bfr, orig_expr;
4080 : 7078157 : bool partial_cplx_access = false;
4081 : :
4082 : 7078157 : if (TREE_CODE (*expr) == BIT_FIELD_REF
4083 : 7078157 : && (write || !sra_handled_bf_read_p (*expr)))
4084 : : {
4085 : 627 : bfr = *expr;
4086 : 627 : expr = &TREE_OPERAND (*expr, 0);
4087 : : }
4088 : : else
4089 : : bfr = NULL_TREE;
4090 : :
4091 : 7078157 : if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
4092 : : {
4093 : 24915 : expr = &TREE_OPERAND (*expr, 0);
4094 : 24915 : partial_cplx_access = true;
4095 : : }
4096 : 7078157 : access = get_access_for_expr (*expr);
4097 : 7078157 : if (!access)
4098 : : return false;
4099 : 149476 : type = TREE_TYPE (*expr);
4100 : 149476 : orig_expr = *expr;
4101 : :
4102 : 149476 : loc = gimple_location (gsi_stmt (*stmt_gsi));
4103 : 149476 : gimple_stmt_iterator alt_gsi = gsi_none ();
4104 : 149476 : if (write && stmt_ends_bb_p (gsi_stmt (*stmt_gsi)))
4105 : : {
4106 : 32851 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*stmt_gsi)));
4107 : 32851 : refresh_gsi = &alt_gsi;
4108 : : }
4109 : :
4110 : 149476 : if (access->grp_to_be_replaced)
4111 : : {
4112 : 22382 : tree repl = get_access_replacement (access);
4113 : : /* If we replace a non-register typed access simply use the original
4114 : : access expression to extract the scalar component afterwards.
4115 : : This happens if scalarizing a function return value or parameter
4116 : : like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
4117 : : gcc.c-torture/compile/20011217-1.c.
4118 : :
4119 : : We also want to use this when accessing a complex or vector which can
4120 : : be accessed as a different type too, potentially creating a need for
4121 : : type conversion (see PR42196) and when scalarized unions are involved
4122 : : in assembler statements (see PR42398). */
4123 : 22382 : if (!bfr && !useless_type_conversion_p (type, access->type))
4124 : : {
4125 : 19074 : tree ref;
4126 : :
4127 : 19074 : ref = build_ref_for_model (loc, orig_expr, 0, access, stmt_gsi,
4128 : : false);
4129 : :
4130 : 19074 : if (partial_cplx_access)
4131 : : {
4132 : : /* VIEW_CONVERT_EXPRs in partial complex access are always fine in
4133 : : the case of a write because in such case the replacement cannot
4134 : : be a gimple register. In the case of a load, we have to
4135 : : differentiate in between a register an non-register
4136 : : replacement. */
4137 : 15 : tree t = build1 (VIEW_CONVERT_EXPR, type, repl);
4138 : 15 : gcc_checking_assert (!write || access->grp_partial_lhs);
4139 : 15 : if (!access->grp_partial_lhs)
4140 : : {
4141 : 12 : tree tmp = make_ssa_name (type);
4142 : 12 : gassign *stmt = gimple_build_assign (tmp, t);
4143 : : /* This is always a read. */
4144 : 12 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4145 : 12 : t = tmp;
4146 : : }
4147 : 15 : *expr = t;
4148 : : }
4149 : 19059 : else if (write)
4150 : : {
4151 : 7032 : gassign *stmt;
4152 : :
4153 : 7032 : if (access->grp_partial_lhs)
4154 : 6 : ref = force_gimple_operand_gsi (refresh_gsi, ref, true,
4155 : : NULL_TREE, false, GSI_NEW_STMT);
4156 : 7032 : stmt = gimple_build_assign (repl, ref);
4157 : 7032 : gimple_set_location (stmt, loc);
4158 : 7032 : gsi_insert_after (refresh_gsi, stmt, GSI_NEW_STMT);
4159 : : }
4160 : : else
4161 : : {
4162 : 12027 : gassign *stmt;
4163 : :
4164 : 12027 : if (access->grp_partial_lhs)
4165 : 6 : repl = force_gimple_operand_gsi (stmt_gsi, repl, true,
4166 : : NULL_TREE, true,
4167 : : GSI_SAME_STMT);
4168 : 12027 : stmt = gimple_build_assign (ref, repl);
4169 : 12027 : gimple_set_location (stmt, loc);
4170 : 12027 : gsi_insert_before (stmt_gsi, stmt, GSI_SAME_STMT);
4171 : : }
4172 : : }
4173 : : else
4174 : : {
4175 : : /* If we are going to replace a scalar field in a structure with
4176 : : reverse storage order by a stand-alone scalar, we are going to
4177 : : effectively byte-swap the scalar and we also need to byte-swap
4178 : : the portion of it represented by the bit-field. */
4179 : 3308 : if (bfr && REF_REVERSE_STORAGE_ORDER (bfr))
4180 : : {
4181 : 0 : REF_REVERSE_STORAGE_ORDER (bfr) = 0;
4182 : 0 : TREE_OPERAND (bfr, 2)
4183 : 0 : = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (repl)),
4184 : : size_binop (PLUS_EXPR, TREE_OPERAND (bfr, 1),
4185 : : TREE_OPERAND (bfr, 2)));
4186 : : }
4187 : :
4188 : 3308 : *expr = repl;
4189 : : }
4190 : :
4191 : 22382 : sra_stats.exprs++;
4192 : : }
4193 : 127094 : else if (write && access->grp_to_be_debug_replaced)
4194 : : {
4195 : 12 : gdebug *ds = gimple_build_debug_bind (get_access_replacement (access),
4196 : : NULL_TREE,
4197 : : gsi_stmt (*stmt_gsi));
4198 : 12 : gsi_insert_after (stmt_gsi, ds, GSI_NEW_STMT);
4199 : : }
4200 : :
4201 : 149476 : if (access->first_child && !TREE_READONLY (access->base))
4202 : : {
4203 : 124670 : HOST_WIDE_INT start_offset, chunk_size;
4204 : 124670 : if (bfr
4205 : 0 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
4206 : 124670 : && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
4207 : : {
4208 : 0 : chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
4209 : 0 : start_offset = access->offset
4210 : 0 : + tree_to_uhwi (TREE_OPERAND (bfr, 2));
4211 : : }
4212 : : else
4213 : : start_offset = chunk_size = 0;
4214 : :
4215 : 201418 : generate_subtree_copies (access->first_child, orig_expr, access->offset,
4216 : : start_offset, chunk_size,
4217 : : write ? refresh_gsi : stmt_gsi,
4218 : : write, write, loc);
4219 : : }
4220 : : return true;
4221 : : }
4222 : :
4223 : : /* If EXPR, which must be a call argument, is an ADDR_EXPR, generate writes and
4224 : : reads from its base before and after the call statement given in CALL_GSI
4225 : : and return true if any copying took place. Otherwise call sra_modify_expr
4226 : : on EXPR and return its value. FLAGS is what the gimple_call_arg_flags
4227 : : return for the given parameter. */
4228 : :
4229 : : static bool
4230 : 7602911 : sra_modify_call_arg (tree *expr, gimple_stmt_iterator *call_gsi,
4231 : : gimple_stmt_iterator *refresh_gsi, int flags)
4232 : : {
4233 : 7602911 : if (TREE_CODE (*expr) != ADDR_EXPR)
4234 : 5097535 : return sra_modify_expr (expr, false, call_gsi, refresh_gsi);
4235 : :
4236 : 2505376 : if (flags & EAF_UNUSED)
4237 : : return false;
4238 : :
4239 : 2501651 : tree base = get_base_address (TREE_OPERAND (*expr, 0));
4240 : 2501651 : if (!DECL_P (base))
4241 : : return false;
4242 : 1994123 : struct access *access = get_access_for_expr (base);
4243 : 1994123 : if (!access)
4244 : : return false;
4245 : :
4246 : 31531 : gimple *stmt = gsi_stmt (*call_gsi);
4247 : 31531 : location_t loc = gimple_location (stmt);
4248 : 31531 : generate_subtree_copies (access, base, 0, 0, 0, call_gsi, false, false,
4249 : : loc);
4250 : :
4251 : 31531 : if (flags & EAF_NO_DIRECT_CLOBBER)
4252 : : return true;
4253 : :
4254 : 21941 : if (!stmt_ends_bb_p (stmt))
4255 : 16956 : generate_subtree_copies (access, base, 0, 0, 0, refresh_gsi, true,
4256 : : true, loc);
4257 : : else
4258 : : {
4259 : 4985 : edge e;
4260 : 4985 : edge_iterator ei;
4261 : 14954 : FOR_EACH_EDGE (e, ei, gsi_bb (*call_gsi)->succs)
4262 : : {
4263 : 9969 : gimple_stmt_iterator alt_gsi = gsi_start_edge (e);
4264 : 9969 : generate_subtree_copies (access, base, 0, 0, 0, &alt_gsi, true,
4265 : : true, loc);
4266 : : }
4267 : : }
4268 : : return true;
4269 : : }
4270 : :
4271 : : /* Where scalar replacements of the RHS have been written to when a replacement
4272 : : of a LHS of an assigments cannot be direclty loaded from a replacement of
4273 : : the RHS. */
4274 : : enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
4275 : : SRA_UDH_RIGHT, /* Data flushed to the RHS. */
4276 : : SRA_UDH_LEFT }; /* Data flushed to the LHS. */
4277 : :
4278 : : struct subreplacement_assignment_data
4279 : : {
4280 : : /* Offset of the access representing the lhs of the assignment. */
4281 : : HOST_WIDE_INT left_offset;
4282 : :
4283 : : /* LHS and RHS of the original assignment. */
4284 : : tree assignment_lhs, assignment_rhs;
4285 : :
4286 : : /* Access representing the rhs of the whole assignment. */
4287 : : struct access *top_racc;
4288 : :
4289 : : /* Stmt iterator used for statement insertions after the original assignment.
4290 : : It points to the main GSI used to traverse a BB during function body
4291 : : modification. */
4292 : : gimple_stmt_iterator *new_gsi;
4293 : :
4294 : : /* Stmt iterator used for statement insertions before the original
4295 : : assignment. Keeps on pointing to the original statement. */
4296 : : gimple_stmt_iterator old_gsi;
4297 : :
4298 : : /* Location of the assignment. */
4299 : : location_t loc;
4300 : :
4301 : : /* Keeps the information whether we have needed to refresh replacements of
4302 : : the LHS and from which side of the assignments this takes place. */
4303 : : enum unscalarized_data_handling refreshed;
4304 : : };
4305 : :
4306 : : /* Store all replacements in the access tree rooted in TOP_RACC either to their
4307 : : base aggregate if there are unscalarized data or directly to LHS of the
4308 : : statement that is pointed to by GSI otherwise. */
4309 : :
4310 : : static void
4311 : 69645 : handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
4312 : : {
4313 : 69645 : tree src;
4314 : : /* If the RHS is a load from a constant, we do not need to (and must not)
4315 : : flush replacements to it and can use it directly as if we did. */
4316 : 69645 : if (TREE_READONLY (sad->top_racc->base))
4317 : : {
4318 : 5 : sad->refreshed = SRA_UDH_RIGHT;
4319 : 5 : return;
4320 : : }
4321 : 69640 : if (sad->top_racc->grp_unscalarized_data)
4322 : : {
4323 : 19566 : src = sad->assignment_rhs;
4324 : 19566 : sad->refreshed = SRA_UDH_RIGHT;
4325 : : }
4326 : : else
4327 : : {
4328 : 50074 : src = sad->assignment_lhs;
4329 : 50074 : sad->refreshed = SRA_UDH_LEFT;
4330 : : }
4331 : 69640 : generate_subtree_copies (sad->top_racc->first_child, src,
4332 : : sad->top_racc->offset, 0, 0,
4333 : : &sad->old_gsi, false, false, sad->loc);
4334 : : }
4335 : :
4336 : : /* Try to generate statements to load all sub-replacements in an access subtree
4337 : : formed by children of LACC from scalar replacements in the SAD->top_racc
4338 : : subtree. If that is not possible, refresh the SAD->top_racc base aggregate
4339 : : and load the accesses from it. */
4340 : :
4341 : : static void
4342 : 627022 : load_assign_lhs_subreplacements (struct access *lacc,
4343 : : struct subreplacement_assignment_data *sad)
4344 : : {
4345 : 2057181 : for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
4346 : : {
4347 : 1430159 : HOST_WIDE_INT offset;
4348 : 1430159 : offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
4349 : :
4350 : 1430159 : if (lacc->grp_to_be_replaced)
4351 : : {
4352 : 1294162 : struct access *racc;
4353 : 1294162 : gassign *stmt;
4354 : 1294162 : tree rhs;
4355 : :
4356 : 1294162 : racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
4357 : 1294162 : if (racc && racc->grp_to_be_replaced)
4358 : : {
4359 : 1271700 : rhs = get_access_replacement (racc);
4360 : 1271700 : bool vce = false;
4361 : 1271700 : if (!useless_type_conversion_p (lacc->type, racc->type))
4362 : : {
4363 : 28 : rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4364 : : lacc->type, rhs);
4365 : 28 : vce = true;
4366 : : }
4367 : :
4368 : 1271700 : if (lacc->grp_partial_lhs && (vce || racc->grp_partial_lhs))
4369 : 0 : rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
4370 : : NULL_TREE, true, GSI_SAME_STMT);
4371 : : }
4372 : : else
4373 : : {
4374 : : /* No suitable access on the right hand side, need to load from
4375 : : the aggregate. See if we have to update it first... */
4376 : 22462 : if (sad->refreshed == SRA_UDH_NONE)
4377 : 11213 : handle_unscalarized_data_in_subtree (sad);
4378 : :
4379 : 22462 : if (sad->refreshed == SRA_UDH_LEFT)
4380 : 271 : rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
4381 : 271 : lacc->offset - sad->left_offset,
4382 : : lacc, sad->new_gsi, true);
4383 : : else
4384 : 22191 : rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
4385 : 22191 : lacc->offset - sad->left_offset,
4386 : : lacc, sad->new_gsi, true);
4387 : 22462 : if (lacc->grp_partial_lhs)
4388 : 3 : rhs = force_gimple_operand_gsi (sad->new_gsi,
4389 : : rhs, true, NULL_TREE,
4390 : : false, GSI_NEW_STMT);
4391 : : }
4392 : :
4393 : 1294162 : stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
4394 : 1294162 : gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
4395 : 1294162 : gimple_set_location (stmt, sad->loc);
4396 : 1294162 : update_stmt (stmt);
4397 : 1294162 : sra_stats.subreplacements++;
4398 : : }
4399 : : else
4400 : : {
4401 : 135997 : if (sad->refreshed == SRA_UDH_NONE
4402 : 46728 : && lacc->grp_read && !lacc->grp_covered)
4403 : 10 : handle_unscalarized_data_in_subtree (sad);
4404 : :
4405 : 135997 : if (lacc && lacc->grp_to_be_debug_replaced)
4406 : : {
4407 : 40872 : gdebug *ds;
4408 : 40872 : tree drhs;
4409 : 40872 : struct access *racc = find_access_in_subtree (sad->top_racc,
4410 : : offset,
4411 : : lacc->size);
4412 : :
4413 : 40872 : if (racc && racc->grp_to_be_replaced)
4414 : : {
4415 : 40868 : if (racc->grp_write || constant_decl_p (racc->base))
4416 : 39484 : drhs = get_access_replacement (racc);
4417 : : else
4418 : : drhs = NULL;
4419 : : }
4420 : 4 : else if (sad->refreshed == SRA_UDH_LEFT)
4421 : 0 : drhs = build_debug_ref_for_model (sad->loc, lacc->base,
4422 : : lacc->offset, lacc);
4423 : 4 : else if (sad->refreshed == SRA_UDH_RIGHT)
4424 : 4 : drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
4425 : : offset, lacc);
4426 : : else
4427 : : drhs = NULL_TREE;
4428 : 39488 : if (drhs
4429 : 39488 : && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
4430 : 469 : drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
4431 : : lacc->type, drhs);
4432 : 40872 : ds = gimple_build_debug_bind (get_access_replacement (lacc),
4433 : : drhs, gsi_stmt (sad->old_gsi));
4434 : 40872 : gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
4435 : : }
4436 : : }
4437 : :
4438 : 1430159 : if (lacc->first_child)
4439 : 56577 : load_assign_lhs_subreplacements (lacc, sad);
4440 : : }
4441 : 627022 : }
4442 : :
4443 : : /* Result code for SRA assignment modification. */
4444 : : enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */
4445 : : SRA_AM_MODIFIED, /* stmt changed but not
4446 : : removed */
4447 : : SRA_AM_REMOVED }; /* stmt eliminated */
4448 : :
4449 : : /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
4450 : : to the assignment and GSI is the statement iterator pointing at it. Returns
4451 : : the same values as sra_modify_assign. */
4452 : :
4453 : : static enum assignment_mod_result
4454 : 2612874 : sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4455 : : {
4456 : 2612874 : tree lhs = gimple_assign_lhs (stmt);
4457 : 2612874 : struct access *acc = get_access_for_expr (lhs);
4458 : 2612874 : if (!acc)
4459 : : return SRA_AM_NONE;
4460 : 1147062 : location_t loc = gimple_location (stmt);
4461 : :
4462 : 1147062 : if (gimple_clobber_p (stmt))
4463 : : {
4464 : : /* Clobber the replacement variable. */
4465 : 1004129 : clobber_subtree (acc, gsi, !acc->grp_covered, loc);
4466 : : /* Remove clobbers of fully scalarized variables, they are dead. */
4467 : 1004129 : if (acc->grp_covered)
4468 : : {
4469 : 844010 : unlink_stmt_vdef (stmt);
4470 : 844010 : gsi_remove (gsi, true);
4471 : 844010 : release_defs (stmt);
4472 : 844010 : return SRA_AM_REMOVED;
4473 : : }
4474 : : else
4475 : : return SRA_AM_MODIFIED;
4476 : : }
4477 : :
4478 : 142933 : if (CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)) > 0)
4479 : : {
4480 : : /* I have never seen this code path trigger but if it can happen the
4481 : : following should handle it gracefully. */
4482 : 0 : if (access_has_children_p (acc))
4483 : 0 : generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
4484 : : true, true, loc);
4485 : 0 : return SRA_AM_MODIFIED;
4486 : : }
4487 : :
4488 : 142933 : if (acc->grp_covered)
4489 : : {
4490 : 91639 : init_subtree_with_zero (acc, gsi, false, loc);
4491 : 91639 : unlink_stmt_vdef (stmt);
4492 : 91639 : gsi_remove (gsi, true);
4493 : 91639 : release_defs (stmt);
4494 : 91639 : return SRA_AM_REMOVED;
4495 : : }
4496 : : else
4497 : : {
4498 : 51294 : init_subtree_with_zero (acc, gsi, true, loc);
4499 : 51294 : return SRA_AM_MODIFIED;
4500 : : }
4501 : : }
4502 : :
4503 : : /* Create and return a new suitable default definition SSA_NAME for RACC which
4504 : : is an access describing an uninitialized part of an aggregate that is being
4505 : : loaded. REG_TREE is used instead of the actual RACC type if that is not of
4506 : : a gimple register type. */
4507 : :
4508 : : static tree
4509 : 509 : get_repl_default_def_ssa_name (struct access *racc, tree reg_type)
4510 : : {
4511 : 509 : gcc_checking_assert (!racc->grp_to_be_replaced
4512 : : && !racc->grp_to_be_debug_replaced);
4513 : 509 : if (!racc->replacement_decl)
4514 : 509 : racc->replacement_decl = create_access_replacement (racc, reg_type);
4515 : 509 : return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
4516 : : }
4517 : :
4518 : :
4519 : : /* Generate statements to call .DEFERRED_INIT to initialize scalar replacements
4520 : : of accesses within a subtree ACCESS; all its children, siblings and their
4521 : : children are to be processed.
4522 : : GSI is a statement iterator used to place the new statements. */
4523 : : static void
4524 : 9 : generate_subtree_deferred_init (struct access *access,
4525 : : tree init_type,
4526 : : tree decl_name,
4527 : : gimple_stmt_iterator *gsi,
4528 : : location_t loc)
4529 : : {
4530 : 29 : do
4531 : : {
4532 : 29 : if (access->grp_to_be_replaced)
4533 : : {
4534 : 28 : tree repl = get_access_replacement (access);
4535 : 28 : gimple *call
4536 : 28 : = gimple_build_call_internal (IFN_DEFERRED_INIT, 3,
4537 : 28 : TYPE_SIZE_UNIT (TREE_TYPE (repl)),
4538 : : init_type, decl_name);
4539 : 28 : gimple_call_set_lhs (call, repl);
4540 : 28 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
4541 : 28 : update_stmt (call);
4542 : 28 : gimple_set_location (call, loc);
4543 : 28 : sra_stats.subtree_deferred_init++;
4544 : : }
4545 : 29 : if (access->first_child)
4546 : 0 : generate_subtree_deferred_init (access->first_child, init_type,
4547 : : decl_name, gsi, loc);
4548 : :
4549 : 29 : access = access ->next_sibling;
4550 : : }
4551 : 29 : while (access);
4552 : 9 : }
4553 : :
4554 : : /* For a call to .DEFERRED_INIT:
4555 : : var = .DEFERRED_INIT (size_of_var, init_type, name_of_var);
4556 : : examine the LHS variable VAR and replace it with a scalar replacement if
4557 : : there is one, also replace the RHS call to a call to .DEFERRED_INIT of
4558 : : the corresponding scalar relacement variable. Examine the subtree and
4559 : : do the scalar replacements in the subtree too. STMT is the call, GSI is
4560 : : the statment iterator to place newly created statement. */
4561 : :
4562 : : static enum assignment_mod_result
4563 : 12 : sra_modify_deferred_init (gimple *stmt, gimple_stmt_iterator *gsi)
4564 : : {
4565 : 12 : tree lhs = gimple_call_lhs (stmt);
4566 : 12 : tree init_type = gimple_call_arg (stmt, 1);
4567 : 12 : tree decl_name = gimple_call_arg (stmt, 2);
4568 : :
4569 : 12 : struct access *lhs_access = get_access_for_expr (lhs);
4570 : 12 : if (!lhs_access)
4571 : : return SRA_AM_NONE;
4572 : :
4573 : 12 : location_t loc = gimple_location (stmt);
4574 : :
4575 : 12 : if (lhs_access->grp_to_be_replaced)
4576 : : {
4577 : 3 : tree lhs_repl = get_access_replacement (lhs_access);
4578 : 3 : gimple_call_set_lhs (stmt, lhs_repl);
4579 : 3 : tree arg0_repl = TYPE_SIZE_UNIT (TREE_TYPE (lhs_repl));
4580 : 3 : gimple_call_set_arg (stmt, 0, arg0_repl);
4581 : 3 : sra_stats.deferred_init++;
4582 : 3 : gcc_assert (!lhs_access->first_child);
4583 : : return SRA_AM_MODIFIED;
4584 : : }
4585 : :
4586 : 9 : if (lhs_access->first_child)
4587 : 9 : generate_subtree_deferred_init (lhs_access->first_child,
4588 : : init_type, decl_name, gsi, loc);
4589 : 9 : if (lhs_access->grp_covered)
4590 : : {
4591 : 7 : unlink_stmt_vdef (stmt);
4592 : 7 : gsi_remove (gsi, true);
4593 : 7 : release_defs (stmt);
4594 : 7 : return SRA_AM_REMOVED;
4595 : : }
4596 : :
4597 : : return SRA_AM_MODIFIED;
4598 : : }
4599 : :
4600 : : /* Examine both sides of the assignment statement pointed to by STMT, replace
4601 : : them with a scalare replacement if there is one and generate copying of
4602 : : replacements if scalarized aggregates have been used in the assignment. GSI
4603 : : is used to hold generated statements for type conversions and subtree
4604 : : copying. */
4605 : :
4606 : : static enum assignment_mod_result
4607 : 22733692 : sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
4608 : : {
4609 : 22733692 : struct access *lacc, *racc;
4610 : 22733692 : tree lhs, rhs;
4611 : 22733692 : bool modify_this_stmt = false;
4612 : 22733692 : bool force_gimple_rhs = false;
4613 : 22733692 : location_t loc;
4614 : 22733692 : gimple_stmt_iterator orig_gsi = *gsi;
4615 : :
4616 : 22733692 : if (!gimple_assign_single_p (stmt))
4617 : : return SRA_AM_NONE;
4618 : 17974062 : lhs = gimple_assign_lhs (stmt);
4619 : 17974062 : rhs = gimple_assign_rhs1 (stmt);
4620 : :
4621 : 17974062 : if (TREE_CODE (rhs) == CONSTRUCTOR)
4622 : 2612874 : return sra_modify_constructor_assign (stmt, gsi);
4623 : :
4624 : 15352311 : if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
4625 : 15349070 : || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
4626 : 15336273 : || (TREE_CODE (rhs) == BIT_FIELD_REF && !sra_handled_bf_read_p (rhs))
4627 : 30697457 : || TREE_CODE (lhs) == BIT_FIELD_REF)
4628 : : {
4629 : 25542 : modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
4630 : : false, gsi, gsi);
4631 : 25542 : modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
4632 : : true, gsi, gsi);
4633 : 47872 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4634 : : }
4635 : :
4636 : 15335646 : lacc = get_access_for_expr (lhs);
4637 : 15335646 : racc = get_access_for_expr (rhs);
4638 : 15335646 : if (!lacc && !racc)
4639 : : return SRA_AM_NONE;
4640 : : /* Avoid modifying initializations of constant-pool replacements. */
4641 : 6413167 : if (racc && (racc->replacement_decl == lhs))
4642 : : return SRA_AM_NONE;
4643 : :
4644 : 6413160 : loc = gimple_location (stmt);
4645 : 6413160 : if (lacc && lacc->grp_to_be_replaced)
4646 : : {
4647 : 1764961 : lhs = get_access_replacement (lacc);
4648 : 1764961 : gimple_assign_set_lhs (stmt, lhs);
4649 : 1764961 : modify_this_stmt = true;
4650 : 1764961 : if (lacc->grp_partial_lhs)
4651 : 77 : force_gimple_rhs = true;
4652 : 1764961 : sra_stats.exprs++;
4653 : : }
4654 : :
4655 : 6413160 : if (racc && racc->grp_to_be_replaced)
4656 : : {
4657 : 2931300 : rhs = get_access_replacement (racc);
4658 : 2931300 : modify_this_stmt = true;
4659 : 2931300 : if (racc->grp_partial_lhs)
4660 : 572 : force_gimple_rhs = true;
4661 : 2931300 : sra_stats.exprs++;
4662 : : }
4663 : 1062372 : else if (racc
4664 : : && !racc->grp_unscalarized_data
4665 : 1062372 : && !racc->grp_unscalarizable_region
4666 : 933761 : && TREE_CODE (lhs) == SSA_NAME
4667 : 650 : && !access_has_replacements_p (racc))
4668 : : {
4669 : 509 : rhs = get_repl_default_def_ssa_name (racc, TREE_TYPE (lhs));
4670 : 509 : modify_this_stmt = true;
4671 : 509 : sra_stats.exprs++;
4672 : : }
4673 : :
4674 : 6413160 : if (modify_this_stmt
4675 : 6413160 : && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4676 : : {
4677 : : /* If we can avoid creating a VIEW_CONVERT_EXPR, then do so.
4678 : : ??? This should move to fold_stmt which we simply should
4679 : : call after building a VIEW_CONVERT_EXPR here. */
4680 : 450091 : if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
4681 : 112463 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (lhs)) == racc->reverse
4682 : 338021 : && !contains_bitfld_component_ref_p (lhs))
4683 : : {
4684 : 112462 : lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
4685 : 112462 : gimple_assign_set_lhs (stmt, lhs);
4686 : : }
4687 : 113097 : else if (lacc
4688 : 88523 : && AGGREGATE_TYPE_P (TREE_TYPE (rhs))
4689 : 67659 : && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (rhs)) == lacc->reverse
4690 : 180756 : && !contains_vce_or_bfcref_p (rhs))
4691 : 67597 : rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
4692 : :
4693 : 225559 : if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
4694 : : {
4695 : 45500 : rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
4696 : 45500 : if (is_gimple_reg_type (TREE_TYPE (lhs))
4697 : 45500 : && TREE_CODE (lhs) != SSA_NAME)
4698 : 6413160 : force_gimple_rhs = true;
4699 : : }
4700 : : }
4701 : :
4702 : 6413160 : if (lacc && lacc->grp_to_be_debug_replaced)
4703 : : {
4704 : 81440 : tree dlhs = get_access_replacement (lacc);
4705 : 81440 : tree drhs = unshare_expr (rhs);
4706 : 81440 : if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
4707 : : {
4708 : 22 : if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
4709 : 21 : && !contains_vce_or_bfcref_p (drhs))
4710 : 10 : drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
4711 : 11 : if (drhs
4712 : 22 : && !useless_type_conversion_p (TREE_TYPE (dlhs),
4713 : 11 : TREE_TYPE (drhs)))
4714 : 1 : drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
4715 : 1 : TREE_TYPE (dlhs), drhs);
4716 : : }
4717 : 81440 : gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
4718 : 81440 : gsi_insert_before (gsi, ds, GSI_SAME_STMT);
4719 : : }
4720 : :
4721 : : /* From this point on, the function deals with assignments in between
4722 : : aggregates when at least one has scalar reductions of some of its
4723 : : components. There are three possible scenarios: Both the LHS and RHS have
4724 : : to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
4725 : :
4726 : : In the first case, we would like to load the LHS components from RHS
4727 : : components whenever possible. If that is not possible, we would like to
4728 : : read it directly from the RHS (after updating it by storing in it its own
4729 : : components). If there are some necessary unscalarized data in the LHS,
4730 : : those will be loaded by the original assignment too. If neither of these
4731 : : cases happen, the original statement can be removed. Most of this is done
4732 : : by load_assign_lhs_subreplacements.
4733 : :
4734 : : In the second case, we would like to store all RHS scalarized components
4735 : : directly into LHS and if they cover the aggregate completely, remove the
4736 : : statement too. In the third case, we want the LHS components to be loaded
4737 : : directly from the RHS (DSE will remove the original statement if it
4738 : : becomes redundant).
4739 : :
4740 : : This is a bit complex but manageable when types match and when unions do
4741 : : not cause confusion in a way that we cannot really load a component of LHS
4742 : : from the RHS or vice versa (the access representing this level can have
4743 : : subaccesses that are accessible only through a different union field at a
4744 : : higher level - different from the one used in the examined expression).
4745 : : Unions are fun.
4746 : :
4747 : : Therefore, I specially handle a fourth case, happening when there is a
4748 : : specific type cast or it is impossible to locate a scalarized subaccess on
4749 : : the other side of the expression. If that happens, I simply "refresh" the
4750 : : RHS by storing in it is scalarized components leave the original statement
4751 : : there to do the copying and then load the scalar replacements of the LHS.
4752 : : This is what the first branch does. */
4753 : :
4754 : 6413160 : if (modify_this_stmt
4755 : 1910838 : || gimple_has_volatile_ops (stmt)
4756 : 1910484 : || contains_vce_or_bfcref_p (rhs)
4757 : 1730309 : || contains_vce_or_bfcref_p (lhs)
4758 : 8142147 : || stmt_ends_bb_p (stmt))
4759 : : {
4760 : : /* No need to copy into a constant, it comes pre-initialized. */
4761 : 4783523 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4762 : 15334 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4763 : : gsi, false, false, loc);
4764 : 4768189 : if (access_has_children_p (lacc))
4765 : : {
4766 : 260043 : gimple_stmt_iterator alt_gsi = gsi_none ();
4767 : 260043 : if (stmt_ends_bb_p (stmt))
4768 : : {
4769 : 83425 : alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
4770 : 83425 : gsi = &alt_gsi;
4771 : : }
4772 : 260043 : generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
4773 : : gsi, true, true, loc);
4774 : : }
4775 : 4768189 : sra_stats.separate_lhs_rhs_handling++;
4776 : :
4777 : : /* This gimplification must be done after generate_subtree_copies,
4778 : : lest we insert the subtree copies in the middle of the gimplified
4779 : : sequence. */
4780 : 4768189 : if (force_gimple_rhs)
4781 : 21564 : rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
4782 : : true, GSI_SAME_STMT);
4783 : 4768189 : if (gimple_assign_rhs1 (stmt) != rhs)
4784 : : {
4785 : 3020249 : modify_this_stmt = true;
4786 : 3020249 : gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
4787 : 3020249 : gcc_assert (stmt == gsi_stmt (orig_gsi));
4788 : : }
4789 : :
4790 : 6250262 : return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
4791 : : }
4792 : : else
4793 : : {
4794 : 2447982 : if (access_has_children_p (lacc)
4795 : 1644981 : && access_has_children_p (racc)
4796 : : /* When an access represents an unscalarizable region, it usually
4797 : : represents accesses with variable offset and thus must not be used
4798 : : to generate new memory accesses. */
4799 : 570455 : && !lacc->grp_unscalarizable_region
4800 : 570451 : && !racc->grp_unscalarizable_region)
4801 : : {
4802 : 570445 : struct subreplacement_assignment_data sad;
4803 : :
4804 : 570445 : sad.left_offset = lacc->offset;
4805 : 570445 : sad.assignment_lhs = lhs;
4806 : 570445 : sad.assignment_rhs = rhs;
4807 : 570445 : sad.top_racc = racc;
4808 : 570445 : sad.old_gsi = *gsi;
4809 : 570445 : sad.new_gsi = gsi;
4810 : 570445 : sad.loc = gimple_location (stmt);
4811 : 570445 : sad.refreshed = SRA_UDH_NONE;
4812 : :
4813 : 570445 : if (lacc->grp_read && !lacc->grp_covered)
4814 : 58422 : handle_unscalarized_data_in_subtree (&sad);
4815 : :
4816 : 570445 : load_assign_lhs_subreplacements (lacc, &sad);
4817 : 570445 : if (sad.refreshed != SRA_UDH_RIGHT)
4818 : : {
4819 : 550874 : gsi_next (gsi);
4820 : 550874 : unlink_stmt_vdef (stmt);
4821 : 550874 : gsi_remove (&sad.old_gsi, true);
4822 : 550874 : release_defs (stmt);
4823 : 550874 : sra_stats.deleted++;
4824 : 550874 : return SRA_AM_REMOVED;
4825 : : }
4826 : : }
4827 : : else
4828 : : {
4829 : 1074526 : if (access_has_children_p (racc)
4830 : 406068 : && !racc->grp_unscalarized_data
4831 : 368082 : && TREE_CODE (lhs) != SSA_NAME)
4832 : : {
4833 : 368081 : if (dump_file)
4834 : : {
4835 : 6 : fprintf (dump_file, "Removing load: ");
4836 : 6 : print_gimple_stmt (dump_file, stmt, 0);
4837 : : }
4838 : 368081 : generate_subtree_copies (racc->first_child, lhs,
4839 : : racc->offset, 0, 0, gsi,
4840 : : false, false, loc);
4841 : 368081 : gcc_assert (stmt == gsi_stmt (*gsi));
4842 : 368081 : unlink_stmt_vdef (stmt);
4843 : 368081 : gsi_remove (gsi, true);
4844 : 368081 : release_defs (stmt);
4845 : 368081 : sra_stats.deleted++;
4846 : 368081 : return SRA_AM_REMOVED;
4847 : : }
4848 : : /* Restore the aggregate RHS from its components so the
4849 : : prevailing aggregate copy does the right thing. */
4850 : 744432 : if (access_has_children_p (racc) && !TREE_READONLY (racc->base))
4851 : 37972 : generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
4852 : : gsi, false, false, loc);
4853 : : /* Re-load the components of the aggregate copy destination.
4854 : : But use the RHS aggregate to load from to expose more
4855 : : optimization opportunities. */
4856 : 706445 : if (access_has_children_p (lacc))
4857 : 232562 : generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
4858 : : 0, 0, gsi, true, true, loc);
4859 : : }
4860 : :
4861 : 726016 : return SRA_AM_NONE;
4862 : : }
4863 : : }
4864 : :
4865 : : /* Set any scalar replacements of values in the constant pool to the initial
4866 : : value of the constant. (Constant-pool decls like *.LC0 have effectively
4867 : : been initialized before the program starts, we must do the same for their
4868 : : replacements.) Thus, we output statements like 'SR.1 = *.LC0[0];' into
4869 : : the function's entry block. */
4870 : :
4871 : : static void
4872 : 395678 : initialize_constant_pool_replacements (void)
4873 : : {
4874 : 395678 : gimple_seq seq = NULL;
4875 : 395678 : gimple_stmt_iterator gsi = gsi_start (seq);
4876 : 395678 : bitmap_iterator bi;
4877 : 395678 : unsigned i;
4878 : :
4879 : 2197107 : EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
4880 : : {
4881 : 1801429 : tree var = candidate (i);
4882 : 1801429 : if (!constant_decl_p (var))
4883 : 1801422 : continue;
4884 : :
4885 : 7 : struct access *access = get_first_repr_for_decl (var);
4886 : :
4887 : 28 : while (access)
4888 : : {
4889 : 14 : if (access->replacement_decl)
4890 : : {
4891 : 7 : gassign *stmt
4892 : 7 : = gimple_build_assign (get_access_replacement (access),
4893 : : unshare_expr (access->expr));
4894 : 7 : if (dump_file && (dump_flags & TDF_DETAILS))
4895 : : {
4896 : 0 : fprintf (dump_file, "Generating constant initializer: ");
4897 : 0 : print_gimple_stmt (dump_file, stmt, 0);
4898 : 0 : fprintf (dump_file, "\n");
4899 : : }
4900 : 7 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
4901 : 7 : update_stmt (stmt);
4902 : : }
4903 : :
4904 : 14 : if (access->first_child)
4905 : : access = access->first_child;
4906 : 7 : else if (access->next_sibling)
4907 : : access = access->next_sibling;
4908 : : else
4909 : : {
4910 : 14 : while (access->parent && !access->next_sibling)
4911 : : access = access->parent;
4912 : 7 : if (access->next_sibling)
4913 : : access = access->next_sibling;
4914 : : else
4915 : 7 : access = access->next_grp;
4916 : : }
4917 : : }
4918 : : }
4919 : :
4920 : 395678 : seq = gsi_seq (gsi);
4921 : 395678 : if (seq)
4922 : 7 : gsi_insert_seq_on_edge_immediate (
4923 : 7 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
4924 : 395678 : }
4925 : :
4926 : : /* Traverse the function body and all modifications as decided in
4927 : : analyze_all_variable_accesses. Return true iff the CFG has been
4928 : : changed. */
4929 : :
4930 : : static bool
4931 : 395678 : sra_modify_function_body (void)
4932 : : {
4933 : 395678 : bool cfg_changed = false;
4934 : 395678 : basic_block bb;
4935 : :
4936 : 395678 : initialize_constant_pool_replacements ();
4937 : :
4938 : 8980144 : FOR_EACH_BB_FN (bb, cfun)
4939 : : {
4940 : 8584466 : gimple_stmt_iterator gsi = gsi_start_bb (bb);
4941 : 66273915 : while (!gsi_end_p (gsi))
4942 : : {
4943 : 57689449 : gimple *stmt = gsi_stmt (gsi);
4944 : 57689449 : enum assignment_mod_result assign_result;
4945 : 57689449 : bool modified = false, deleted = false;
4946 : 57689449 : tree *t;
4947 : 57689449 : unsigned i;
4948 : :
4949 : 57689449 : switch (gimple_code (stmt))
4950 : : {
4951 : 393710 : case GIMPLE_RETURN:
4952 : 393710 : t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
4953 : 393710 : if (*t != NULL_TREE)
4954 : 264673 : modified |= sra_modify_expr (t, false, &gsi, &gsi);
4955 : : break;
4956 : :
4957 : 22733692 : case GIMPLE_ASSIGN:
4958 : 22733692 : assign_result = sra_modify_assign (stmt, &gsi);
4959 : 22733692 : modified |= assign_result == SRA_AM_MODIFIED;
4960 : 22733692 : deleted = assign_result == SRA_AM_REMOVED;
4961 : 22733692 : break;
4962 : :
4963 : 3779692 : case GIMPLE_CALL:
4964 : : /* Handle calls to .DEFERRED_INIT specially. */
4965 : 3779692 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
4966 : : {
4967 : 12 : assign_result = sra_modify_deferred_init (stmt, &gsi);
4968 : 12 : modified |= assign_result == SRA_AM_MODIFIED;
4969 : 12 : deleted = assign_result == SRA_AM_REMOVED;
4970 : : }
4971 : : else
4972 : : {
4973 : 3779680 : gcall *call = as_a <gcall *> (stmt);
4974 : 3779680 : gimple_stmt_iterator call_gsi = gsi;
4975 : :
4976 : : /* Operands must be processed before the lhs. */
4977 : 11352364 : for (i = 0; i < gimple_call_num_args (call); i++)
4978 : : {
4979 : 7572684 : int flags = gimple_call_arg_flags (call, i);
4980 : 7572684 : t = gimple_call_arg_ptr (call, i);
4981 : 7572684 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi, flags);
4982 : : }
4983 : 3779680 : if (gimple_call_chain (call))
4984 : : {
4985 : 30227 : t = gimple_call_chain_ptr (call);
4986 : 30227 : int flags = gimple_call_static_chain_flags (call);
4987 : 30227 : modified |= sra_modify_call_arg (t, &call_gsi, &gsi,
4988 : : flags);
4989 : : }
4990 : 3779680 : if (gimple_call_lhs (call))
4991 : : {
4992 : 1661665 : t = gimple_call_lhs_ptr (call);
4993 : 1661665 : modified |= sra_modify_expr (t, true, &call_gsi, &gsi);
4994 : : }
4995 : : }
4996 : : break;
4997 : :
4998 : 4629 : case GIMPLE_ASM:
4999 : 4629 : {
5000 : 4629 : gimple_stmt_iterator stmt_gsi = gsi;
5001 : 4629 : gasm *asm_stmt = as_a <gasm *> (stmt);
5002 : 10687 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
5003 : : {
5004 : 1429 : t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
5005 : 1429 : modified |= sra_modify_expr (t, false, &stmt_gsi, &gsi);
5006 : : }
5007 : 6400 : for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
5008 : : {
5009 : 1771 : t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
5010 : 1771 : modified |= sra_modify_expr (t, true, &stmt_gsi, &gsi);
5011 : : }
5012 : : }
5013 : 4629 : break;
5014 : :
5015 : : default:
5016 : : break;
5017 : : }
5018 : :
5019 : 26782686 : if (modified)
5020 : : {
5021 : 4873633 : update_stmt (stmt);
5022 : 4873633 : if (maybe_clean_eh_stmt (stmt)
5023 : 4873633 : && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
5024 : : cfg_changed = true;
5025 : : }
5026 : 57689449 : if (!deleted)
5027 : 55834838 : gsi_next (&gsi);
5028 : : }
5029 : : }
5030 : :
5031 : 395678 : gsi_commit_edge_inserts ();
5032 : 395678 : return cfg_changed;
5033 : : }
5034 : :
5035 : : /* Generate statements initializing scalar replacements of parts of function
5036 : : parameters. */
5037 : :
5038 : : static void
5039 : 395678 : initialize_parameter_reductions (void)
5040 : : {
5041 : 395678 : gimple_stmt_iterator gsi;
5042 : 395678 : gimple_seq seq = NULL;
5043 : 395678 : tree parm;
5044 : :
5045 : 395678 : gsi = gsi_start (seq);
5046 : 395678 : for (parm = DECL_ARGUMENTS (current_function_decl);
5047 : 1171049 : parm;
5048 : 775371 : parm = DECL_CHAIN (parm))
5049 : : {
5050 : 775371 : vec<access_p> *access_vec;
5051 : 775371 : struct access *access;
5052 : :
5053 : 775371 : if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
5054 : 717778 : continue;
5055 : 57593 : access_vec = get_base_access_vector (parm);
5056 : 57593 : if (!access_vec)
5057 : 0 : continue;
5058 : :
5059 : 57593 : for (access = (*access_vec)[0];
5060 : 149813 : access;
5061 : 92220 : access = access->next_grp)
5062 : 92220 : generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
5063 : 92220 : EXPR_LOCATION (parm));
5064 : : }
5065 : :
5066 : 395678 : seq = gsi_seq (gsi);
5067 : 395678 : if (seq)
5068 : 45873 : gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
5069 : 395678 : }
5070 : :
5071 : : /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
5072 : : it reveals there are components of some aggregates to be scalarized, it runs
5073 : : the required transformations. */
5074 : : static unsigned int
5075 : 3206652 : perform_intra_sra (void)
5076 : : {
5077 : 3206652 : int ret = 0;
5078 : 3206652 : sra_initialize ();
5079 : :
5080 : 3206652 : if (!find_var_candidates ())
5081 : 2507143 : goto out;
5082 : :
5083 : 699509 : if (!scan_function ())
5084 : 47201 : goto out;
5085 : :
5086 : 652308 : if (!analyze_all_variable_accesses ())
5087 : 256630 : goto out;
5088 : :
5089 : 395678 : if (sra_modify_function_body ())
5090 : : ret = TODO_update_ssa | TODO_cleanup_cfg;
5091 : : else
5092 : 395656 : ret = TODO_update_ssa;
5093 : 395678 : initialize_parameter_reductions ();
5094 : :
5095 : 395678 : statistics_counter_event (cfun, "Scalar replacements created",
5096 : : sra_stats.replacements);
5097 : 395678 : statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
5098 : 395678 : statistics_counter_event (cfun, "Subtree copy stmts",
5099 : : sra_stats.subtree_copies);
5100 : 395678 : statistics_counter_event (cfun, "Subreplacement stmts",
5101 : : sra_stats.subreplacements);
5102 : 395678 : statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
5103 : 395678 : statistics_counter_event (cfun, "Separate LHS and RHS handling",
5104 : : sra_stats.separate_lhs_rhs_handling);
5105 : :
5106 : 3206652 : out:
5107 : 3206652 : sra_deinitialize ();
5108 : 3206652 : return ret;
5109 : : }
5110 : :
5111 : : /* Perform early intraprocedural SRA. */
5112 : : static unsigned int
5113 : 2221683 : early_intra_sra (void)
5114 : : {
5115 : 2221683 : sra_mode = SRA_MODE_EARLY_INTRA;
5116 : 0 : return perform_intra_sra ();
5117 : : }
5118 : :
5119 : : /* Perform "late" intraprocedural SRA. */
5120 : : static unsigned int
5121 : 984969 : late_intra_sra (void)
5122 : : {
5123 : 984969 : sra_mode = SRA_MODE_INTRA;
5124 : 0 : return perform_intra_sra ();
5125 : : }
5126 : :
5127 : :
5128 : : static bool
5129 : 3210836 : gate_intra_sra (void)
5130 : : {
5131 : 3210836 : return flag_tree_sra != 0 && dbg_cnt (tree_sra);
5132 : : }
5133 : :
5134 : :
5135 : : namespace {
5136 : :
5137 : : const pass_data pass_data_sra_early =
5138 : : {
5139 : : GIMPLE_PASS, /* type */
5140 : : "esra", /* name */
5141 : : OPTGROUP_NONE, /* optinfo_flags */
5142 : : TV_TREE_SRA, /* tv_id */
5143 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
5144 : : 0, /* properties_provided */
5145 : : 0, /* properties_destroyed */
5146 : : 0, /* todo_flags_start */
5147 : : TODO_update_ssa, /* todo_flags_finish */
5148 : : };
5149 : :
5150 : : class pass_sra_early : public gimple_opt_pass
5151 : : {
5152 : : public:
5153 : 281914 : pass_sra_early (gcc::context *ctxt)
5154 : 563828 : : gimple_opt_pass (pass_data_sra_early, ctxt)
5155 : : {}
5156 : :
5157 : : /* opt_pass methods: */
5158 : 2225453 : bool gate (function *) final override { return gate_intra_sra (); }
5159 : 2221683 : unsigned int execute (function *) final override
5160 : : {
5161 : 2221683 : return early_intra_sra ();
5162 : : }
5163 : :
5164 : : }; // class pass_sra_early
5165 : :
5166 : : } // anon namespace
5167 : :
5168 : : gimple_opt_pass *
5169 : 281914 : make_pass_sra_early (gcc::context *ctxt)
5170 : : {
5171 : 281914 : return new pass_sra_early (ctxt);
5172 : : }
5173 : :
5174 : : namespace {
5175 : :
5176 : : const pass_data pass_data_sra =
5177 : : {
5178 : : GIMPLE_PASS, /* type */
5179 : : "sra", /* name */
5180 : : OPTGROUP_NONE, /* optinfo_flags */
5181 : : TV_TREE_SRA, /* tv_id */
5182 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
5183 : : 0, /* properties_provided */
5184 : : 0, /* properties_destroyed */
5185 : : TODO_update_address_taken, /* todo_flags_start */
5186 : : TODO_update_ssa, /* todo_flags_finish */
5187 : : };
5188 : :
5189 : : class pass_sra : public gimple_opt_pass
5190 : : {
5191 : : public:
5192 : 281914 : pass_sra (gcc::context *ctxt)
5193 : 563828 : : gimple_opt_pass (pass_data_sra, ctxt)
5194 : : {}
5195 : :
5196 : : /* opt_pass methods: */
5197 : 985383 : bool gate (function *) final override { return gate_intra_sra (); }
5198 : 984969 : unsigned int execute (function *) final override { return late_intra_sra (); }
5199 : :
5200 : : }; // class pass_sra
5201 : :
5202 : : } // anon namespace
5203 : :
5204 : : gimple_opt_pass *
5205 : 281914 : make_pass_sra (gcc::context *ctxt)
5206 : : {
5207 : 281914 : return new pass_sra (ctxt);
5208 : : }
5209 : :
5210 : :
5211 : : /* If type T cannot be totally scalarized, return false. Otherwise return true
5212 : : and push to the vector within PC offsets and lengths of all padding in the
5213 : : type as total scalarization would encounter it. */
5214 : :
5215 : : static bool
5216 : 62907 : check_ts_and_push_padding_to_vec (tree type, sra_padding_collecting *pc)
5217 : : {
5218 : 62907 : if (!totally_scalarizable_type_p (type, true /* optimistic value */,
5219 : : 0, pc))
5220 : : return false;
5221 : :
5222 : 58346 : pc->record_padding (tree_to_shwi (TYPE_SIZE (type)));
5223 : 58346 : return true;
5224 : : }
5225 : :
5226 : : /* Given two types in an assignment, return true either if any one cannot be
5227 : : totally scalarized or if they have padding (i.e. not copied bits) */
5228 : :
5229 : : bool
5230 : 33732 : sra_total_scalarization_would_copy_same_data_p (tree t1, tree t2)
5231 : : {
5232 : 33732 : sra_padding_collecting p1;
5233 : 33732 : if (!check_ts_and_push_padding_to_vec (t1, &p1))
5234 : : return true;
5235 : :
5236 : 29175 : sra_padding_collecting p2;
5237 : 29175 : if (!check_ts_and_push_padding_to_vec (t2, &p2))
5238 : : return true;
5239 : :
5240 : 29171 : unsigned l = p1.m_padding.length ();
5241 : 58342 : if (l != p2.m_padding.length ())
5242 : : return false;
5243 : 34740 : for (unsigned i = 0; i < l; i++)
5244 : 5574 : if (p1.m_padding[i].first != p2.m_padding[i].first
5245 : 5574 : || p1.m_padding[i].second != p2.m_padding[i].second)
5246 : : return false;
5247 : :
5248 : : return true;
5249 : 29175 : }
5250 : :
|
