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