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