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