1	/* Alias analysis for GNU C
2	Copyright (C) 1997-2024 Free Software Foundation, Inc.
3	Contributed by John Carr (jfc@mit.edu).
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "target.h"
26	#include "rtl.h"
27	#include "tree.h"
28	#include "gimple.h"
29	#include "df.h"
30	#include "memmodel.h"
31	#include "tm_p.h"
32	#include "gimple-ssa.h"
33	#include "emit-rtl.h"
34	#include "alias.h"
35	#include "fold-const.h"
36	#include "varasm.h"
37	#include "cselib.h"
38	#include "langhooks.h"
39	#include "cfganal.h"
40	#include "rtl-iter.h"
41	#include "cgraph.h"
42	#include "ipa-utils.h"
43
44	/* The aliasing API provided here solves related but different problems:
45
46	Say there exists (in c)
47
48	struct X {
49	struct Y y1;
50	struct Z z2;
51	} x1, *px1, *px2;
52
53	struct Y y2, *py;
54	struct Z z2, *pz;
55
56
57	py = &x1.y1;
58	px2 = &x1;
59
60	Consider the four questions:
61
62	Can a store to x1 interfere with px2->y1?
63	Can a store to x1 interfere with px2->z2?
64	Can a store to x1 change the value pointed to by with py?
65	Can a store to x1 change the value pointed to by with pz?
66
67	The answer to these questions can be yes, yes, yes, and maybe.
68
69	The first two questions can be answered with a simple examination
70	of the type system. If structure X contains a field of type Y then
71	a store through a pointer to an X can overwrite any field that is
72	contained (recursively) in an X (unless we know that px1 != px2).
73
74	The last two questions can be solved in the same way as the first
75	two questions but this is too conservative. The observation is
76	that in some cases we can know which (if any) fields are addressed
77	and if those addresses are used in bad ways. This analysis may be
78	language specific. In C, arbitrary operations may be applied to
79	pointers. However, there is some indication that this may be too
80	conservative for some C++ types.
81
82	The pass ipa-type-escape does this analysis for the types whose
83	instances do not escape across the compilation boundary.
84
85	Historically in GCC, these two problems were combined and a single
86	data structure that was used to represent the solution to these
87	problems. We now have two similar but different data structures,
88	The data structure to solve the last two questions is similar to
89	the first, but does not contain the fields whose address are never
90	taken. For types that do escape the compilation unit, the data
91	structures will have identical information.
92	*/
93
94	/* The alias sets assigned to MEMs assist the back-end in determining
95	which MEMs can alias which other MEMs. In general, two MEMs in
96	different alias sets cannot alias each other, with one important
97	exception. Consider something like:
98
99	struct S { int i; double d; };
100
101	a store to an `S' can alias something of either type `int' or type
102	`double'. (However, a store to an `int' cannot alias a `double'
103	and vice versa.) We indicate this via a tree structure that looks
104	like:
105	struct S
106	/ \
107	/ \
108	|/_ _\|
109	int double
110
111	(The arrows are directed and point downwards.)
112	In this situation we say the alias set for `struct S' is the
113	`superset' and that those for `int' and `double' are `subsets'.
114
115	To see whether two alias sets can point to the same memory, we must
116	see if either alias set is a subset of the other. We need not trace
117	past immediate descendants, however, since we propagate all
118	grandchildren up one level.
119
120	Alias set zero is implicitly a superset of all other alias sets.
121	However, this is no actual entry for alias set zero. It is an
122	error to attempt to explicitly construct a subset of zero. */
123
124	struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {};
125
126	struct GTY(()) alias_set_entry {
127	/* The alias set number, as stored in MEM_ALIAS_SET. */
128	alias_set_type alias_set;
129
130	/* Nonzero if would have a child of zero: this effectively makes this
131	alias set the same as alias set zero. */
132	bool has_zero_child;
133	/* Nonzero if alias set corresponds to pointer type itself (i.e. not to
134	aggregate contaiing pointer.
135	This is used for a special case where we need an universal pointer type
136	compatible with all other pointer types. */
137	bool is_pointer;
138	/* Nonzero if is_pointer or if one of childs have has_pointer set. */
139	bool has_pointer;
140
141	/* The children of the alias set. These are not just the immediate
142	children, but, in fact, all descendants. So, if we have:
143
144	struct T { struct S s; float f; }
145
146	continuing our example above, the children here will be all of
147	`int', `double', `float', and `struct S'. */
148	hash_map<alias_set_hash, int> *children;
149	};
150
151	static int compare_base_symbol_refs (const_rtx, const_rtx,
152	HOST_WIDE_INT * = NULL);
153
154	/* Query statistics for the different low-level disambiguators.
155	A high-level query may trigger multiple of them. */
156
157	static struct {
158	unsigned long long num_alias_zero;
159	unsigned long long num_same_alias_set;
160	unsigned long long num_same_objects;
161	unsigned long long num_volatile;
162	unsigned long long num_dag;
163	unsigned long long num_universal;
164	unsigned long long num_disambiguated;
165	} alias_stats;
166
167
168	/* Set up all info needed to perform alias analysis on memory references. */
169
170	/* Returns the size in bytes of the mode of X. */
171	#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
172
173	/* Cap the number of passes we make over the insns propagating alias
174	information through set chains.
175	??? 10 is a completely arbitrary choice. This should be based on the
176	maximum loop depth in the CFG, but we do not have this information
177	available (even if current_loops _is_ available). */
178	#define MAX_ALIAS_LOOP_PASSES 10
179
180	/* reg_base_value[N] gives an address to which register N is related.
181	If all sets after the first add or subtract to the current value
182	or otherwise modify it so it does not point to a different top level
183	object, reg_base_value[N] is equal to the address part of the source
184	of the first set.
185
186	A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
187	expressions represent three types of base:
188
189	1. incoming arguments. There is just one ADDRESS to represent all
190	arguments, since we do not know at this level whether accesses
191	based on different arguments can alias. The ADDRESS has id 0.
192
193	2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
194	(if distinct from frame_pointer_rtx) and arg_pointer_rtx.
195	Each of these rtxes has a separate ADDRESS associated with it,
196	each with a negative id.
197
198	GCC is (and is required to be) precise in which register it
199	chooses to access a particular region of stack. We can therefore
200	assume that accesses based on one of these rtxes do not alias
201	accesses based on another of these rtxes.
202
203	3. bases that are derived from malloc()ed memory (REG_NOALIAS).
204	Each such piece of memory has a separate ADDRESS associated
205	with it, each with an id greater than 0.
206
207	Accesses based on one ADDRESS do not alias accesses based on other
208	ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
209	alias globals either; the ADDRESSes have Pmode to indicate this.
210	The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
211	indicate this. */
212
213	static GTY(()) vec<rtx, va_gc> *reg_base_value;
214	static rtx *new_reg_base_value;
215
216	/* The single VOIDmode ADDRESS that represents all argument bases.
217	It has id 0. */
218	static GTY(()) rtx arg_base_value;
219
220	/* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
221	static int unique_id;
222
223	/* We preserve the copy of old array around to avoid amount of garbage
224	produced. About 8% of garbage produced were attributed to this
225	array. */
226	static GTY((deletable)) vec<rtx, va_gc> *old_reg_base_value;
227
228	/* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
229	registers. */
230	#define UNIQUE_BASE_VALUE_SP -1
231	#define UNIQUE_BASE_VALUE_ARGP -2
232	#define UNIQUE_BASE_VALUE_FP -3
233	#define UNIQUE_BASE_VALUE_HFP -4
234
235	#define static_reg_base_value \
236	(this_target_rtl->x_static_reg_base_value)
237
238	#define REG_BASE_VALUE(X) \
239	(REGNO (X) < vec_safe_length (reg_base_value) \
240	? (*reg_base_value)[REGNO (X)] : 0)
241
242	/* Vector indexed by N giving the initial (unchanging) value known for
243	pseudo-register N. This vector is initialized in init_alias_analysis,
244	and does not change until end_alias_analysis is called. */
245	static GTY(()) vec<rtx, va_gc> *reg_known_value;
246
247	/* Vector recording for each reg_known_value whether it is due to a
248	REG_EQUIV note. Future passes (viz., reload) may replace the
249	pseudo with the equivalent expression and so we account for the
250	dependences that would be introduced if that happens.
251
252	The REG_EQUIV notes created in assign_parms may mention the arg
253	pointer, and there are explicit insns in the RTL that modify the
254	arg pointer. Thus we must ensure that such insns don't get
255	scheduled across each other because that would invalidate the
256	REG_EQUIV notes. One could argue that the REG_EQUIV notes are
257	wrong, but solving the problem in the scheduler will likely give
258	better code, so we do it here. */
259	static sbitmap reg_known_equiv_p;
260
261	/* True when scanning insns from the start of the rtl to the
262	NOTE_INSN_FUNCTION_BEG note. */
263	static bool copying_arguments;
264
265
266	/* The splay-tree used to store the various alias set entries. */
267	static GTY (()) vec<alias_set_entry *, va_gc> *alias_sets;
268
269	/* Build a decomposed reference object for querying the alias-oracle
270	from the MEM rtx and store it in *REF.
271	Returns false if MEM is not suitable for the alias-oracle. */
272
273	static bool
274	ao_ref_from_mem (ao_ref *ref, const_rtx mem)
275	{
276	tree expr = MEM_EXPR (mem);
277	tree base;
278
279	if (!expr)
280	return false;
281
282	ao_ref_init (ref, expr);
283
284	/* Get the base of the reference and see if we have to reject or
285	adjust it. */
286	base = ao_ref_base (ref);
287	if (base == NULL_TREE)
288	return false;
289
290	/* The tree oracle doesn't like bases that are neither decls
291	nor indirect references of SSA names. */
292	if (!(DECL_P (base)
293	|| (TREE_CODE (base) == MEM_REF
294	&& TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
295	|| (TREE_CODE (base) == TARGET_MEM_REF
296	&& TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
297	return false;
298
299	ref->ref_alias_set = MEM_ALIAS_SET (mem);
300
301	/* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
302	is conservative, so trust it. */
303	if (!MEM_OFFSET_KNOWN_P (mem)
304	|| !MEM_SIZE_KNOWN_P (mem))
305	return true;
306
307	/* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size
308	drop ref->ref. */
309	if (maybe_lt (MEM_OFFSET (mem), b: 0)
310	|| (ref->max_size_known_p ()
311	&& maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT,
312	ref->max_size)))
313	ref->ref = NULL_TREE;
314
315	/* Refine size and offset we got from analyzing MEM_EXPR by using
316	MEM_SIZE and MEM_OFFSET. */
317
318	ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
319	ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
320
321	/* The MEM may extend into adjacent fields, so adjust max_size if
322	necessary. */
323	if (ref->max_size_known_p ())
324	ref->max_size = upper_bound (a: ref->max_size, b: ref->size);
325
326	/* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of
327	the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
328	if (MEM_EXPR (mem) != get_spill_slot_decl (false)
329	&& (maybe_lt (a: ref->offset, b: 0)
330	|| (DECL_P (ref->base)
331	&& (DECL_SIZE (ref->base) == NULL_TREE
332	|| !poly_int_tree_p (DECL_SIZE (ref->base))
333	|| maybe_lt (a: wi::to_poly_offset (DECL_SIZE (ref->base)),
334	b: ref->offset + ref->size)))))
335	return false;
336
337	return true;
338	}
339
340	/* Query the alias-oracle on whether the two memory rtx X and MEM may
341	alias. If TBAA_P is set also apply TBAA. Returns true if the
342	two rtxen may alias, false otherwise. */
343
344	static bool
345	rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
346	{
347	ao_ref ref1, ref2;
348
349	if (!ao_ref_from_mem (ref: &ref1, mem: x)
350	|| !ao_ref_from_mem (ref: &ref2, mem))
351	return true;
352
353	return refs_may_alias_p_1 (&ref1, &ref2,
354	tbaa_p
355	&& MEM_ALIAS_SET (x) != 0
356	&& MEM_ALIAS_SET (mem) != 0);
357	}
358
359	/* Return true if the ref EARLIER behaves the same as LATER with respect
360	to TBAA for every memory reference that might follow LATER. */
361
362	bool
363	refs_same_for_tbaa_p (tree earlier, tree later)
364	{
365	ao_ref earlier_ref, later_ref;
366	ao_ref_init (&earlier_ref, earlier);
367	ao_ref_init (&later_ref, later);
368	alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref);
369	alias_set_type later_set = ao_ref_alias_set (&later_ref);
370	if (!(earlier_set == later_set
371	|| alias_set_subset_of (later_set, earlier_set)))
372	return false;
373	alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref);
374	alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref);
375	return (earlier_base_set == later_base_set
376	|| alias_set_subset_of (later_base_set, earlier_base_set));
377	}
378
379	/* Similar to refs_same_for_tbaa_p() but for use on MEM rtxs. */
380	bool
381	mems_same_for_tbaa_p (rtx earlier, rtx later)
382	{
383	gcc_assert (MEM_P (earlier));
384	gcc_assert (MEM_P (later));
385
386	return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later)
387	|| alias_set_subset_of (MEM_ALIAS_SET (later),
388	MEM_ALIAS_SET (earlier)))
389	&& (!MEM_EXPR (earlier)
390	|| refs_same_for_tbaa_p (MEM_EXPR (earlier), MEM_EXPR (later))));
391	}
392
393	/* Returns a pointer to the alias set entry for ALIAS_SET, if there is
394	such an entry, or NULL otherwise. */
395
396	static inline alias_set_entry *
397	get_alias_set_entry (alias_set_type alias_set)
398	{
399	return (*alias_sets)[alias_set];
400	}
401
402	/* Returns true if the alias sets for MEM1 and MEM2 are such that
403	the two MEMs cannot alias each other. */
404
405	static inline bool
406	mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
407	{
408	return (flag_strict_aliasing
409	&& ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
410	MEM_ALIAS_SET (mem2)));
411	}
412
413	/* Return true if the first alias set is a subset of the second. */
414
415	bool
416	alias_set_subset_of (alias_set_type set1, alias_set_type set2)
417	{
418	alias_set_entry *ase2;
419
420	/* Disable TBAA oracle with !flag_strict_aliasing. */
421	if (!flag_strict_aliasing)
422	return true;
423
424	/* Everything is a subset of the "aliases everything" set. */
425	if (set2 == 0)
426	return true;
427
428	/* Check if set1 is a subset of set2. */
429	ase2 = get_alias_set_entry (alias_set: set2);
430	if (ase2 != 0
431	&& (ase2->has_zero_child
432	|| (ase2->children && ase2->children->get (k: set1))))
433	return true;
434
435	/* As a special case we consider alias set of "void *" to be both subset
436	and superset of every alias set of a pointer. This extra symmetry does
437	not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
438	to return true on the following testcase:
439
440	void *ptr;
441	char **ptr2=(char **)&ptr;
442	*ptr2 = ...
443
444	Additionally if a set contains universal pointer, we consider every pointer
445	to be a subset of it, but we do not represent this explicitely - doing so
446	would require us to update transitive closure each time we introduce new
447	pointer type. This makes aliasing_component_refs_p to return true
448	on the following testcase:
449
450	struct a {void *ptr;}
451	char **ptr = (char **)&a.ptr;
452	ptr = ...
453
454	This makes void * truly universal pointer type. See pointer handling in
455	get_alias_set for more details. */
456	if (ase2 && ase2->has_pointer)
457	{
458	alias_set_entry *ase1 = get_alias_set_entry (alias_set: set1);
459
460	if (ase1 && ase1->is_pointer)
461	{
462	alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
463	/* If one is ptr_type_node and other is pointer, then we consider
464	them subset of each other. */
465	if (set1 == voidptr_set || set2 == voidptr_set)
466	return true;
467	/* If SET2 contains universal pointer's alias set, then we consdier
468	every (non-universal) pointer. */
469	if (ase2->children && set1 != voidptr_set
470	&& ase2->children->get (k: voidptr_set))
471	return true;
472	}
473	}
474	return false;
475	}
476
477	/* Return true if the two specified alias sets may conflict. */
478
479	bool
480	alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
481	{
482	alias_set_entry *ase1;
483	alias_set_entry *ase2;
484
485	/* The easy case. */
486	if (alias_sets_must_conflict_p (set1, set2))
487	return true;
488
489	/* See if the first alias set is a subset of the second. */
490	ase1 = get_alias_set_entry (alias_set: set1);
491	if (ase1 != 0
492	&& ase1->children && ase1->children->get (k: set2))
493	{
494	++alias_stats.num_dag;
495	return true;
496	}
497
498	/* Now do the same, but with the alias sets reversed. */
499	ase2 = get_alias_set_entry (alias_set: set2);
500	if (ase2 != 0
501	&& ase2->children && ase2->children->get (k: set1))
502	{
503	++alias_stats.num_dag;
504	return true;
505	}
506
507	/* We want void * to be compatible with any other pointer without
508	really dropping it to alias set 0. Doing so would make it
509	compatible with all non-pointer types too.
510
511	This is not strictly necessary by the C/C++ language
512	standards, but avoids common type punning mistakes. In
513	addition to that, we need the existence of such universal
514	pointer to implement Fortran's C_PTR type (which is defined as
515	type compatible with all C pointers). */
516	if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
517	{
518	alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
519
520	/* If one of the sets corresponds to universal pointer,
521	we consider it to conflict with anything that is
522	or contains pointer. */
523	if (set1 == voidptr_set || set2 == voidptr_set)
524	{
525	++alias_stats.num_universal;
526	return true;
527	}
528	/* If one of sets is (non-universal) pointer and the other
529	contains universal pointer, we also get conflict. */
530	if (ase1->is_pointer && set2 != voidptr_set
531	&& ase2->children && ase2->children->get (k: voidptr_set))
532	{
533	++alias_stats.num_universal;
534	return true;
535	}
536	if (ase2->is_pointer && set1 != voidptr_set
537	&& ase1->children && ase1->children->get (k: voidptr_set))
538	{
539	++alias_stats.num_universal;
540	return true;
541	}
542	}
543
544	++alias_stats.num_disambiguated;
545
546	/* The two alias sets are distinct and neither one is the
547	child of the other. Therefore, they cannot conflict. */
548	return false;
549	}
550
551	/* Return true if the two specified alias sets will always conflict. */
552
553	bool
554	alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
555	{
556	/* Disable TBAA oracle with !flag_strict_aliasing. */
557	if (!flag_strict_aliasing)
558	return true;
559	if (set1 == 0 || set2 == 0)
560	{
561	++alias_stats.num_alias_zero;
562	return true;
563	}
564	if (set1 == set2)
565	{
566	++alias_stats.num_same_alias_set;
567	return true;
568	}
569
570	return false;
571	}
572
573	/* Return true if any MEM object of type T1 will always conflict (using the
574	dependency routines in this file) with any MEM object of type T2.
575	This is used when allocating temporary storage. If T1 and/or T2 are
576	NULL_TREE, it means we know nothing about the storage. */
577
578	bool
579	objects_must_conflict_p (tree t1, tree t2)
580	{
581	alias_set_type set1, set2;
582
583	/* If neither has a type specified, we don't know if they'll conflict
584	because we may be using them to store objects of various types, for
585	example the argument and local variables areas of inlined functions. */
586	if (t1 == 0 && t2 == 0)
587	return false;
588
589	/* If they are the same type, they must conflict. */
590	if (t1 == t2)
591	{
592	++alias_stats.num_same_objects;
593	return true;
594	}
595	/* Likewise if both are volatile. */
596	if (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))
597	{
598	++alias_stats.num_volatile;
599	return true;
600	}
601
602	set1 = t1 ? get_alias_set (t1) : 0;
603	set2 = t2 ? get_alias_set (t2) : 0;
604
605	/* We can't use alias_sets_conflict_p because we must make sure
606	that every subtype of t1 will conflict with every subtype of
607	t2 for which a pair of subobjects of these respective subtypes
608	overlaps on the stack. */
609	return alias_sets_must_conflict_p (set1, set2);
610	}
611
612	/* Return true if T is an end of the access path which can be used
613	by type based alias oracle. */
614
615	bool
616	ends_tbaa_access_path_p (const_tree t)
617	{
618	switch (TREE_CODE (t))
619	{
620	case COMPONENT_REF:
621	if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
622	return true;
623	/* Permit type-punning when accessing a union, provided the access
624	is directly through the union. For example, this code does not
625	permit taking the address of a union member and then storing
626	through it. Even the type-punning allowed here is a GCC
627	extension, albeit a common and useful one; the C standard says
628	that such accesses have implementation-defined behavior. */
629	else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
630	return true;
631	break;
632
633	case ARRAY_REF:
634	case ARRAY_RANGE_REF:
635	if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
636	return true;
637	break;
638
639	case REALPART_EXPR:
640	case IMAGPART_EXPR:
641	break;
642
643	case BIT_FIELD_REF:
644	case VIEW_CONVERT_EXPR:
645	/* Bitfields and casts are never addressable. */
646	return true;
647	break;
648
649	default:
650	gcc_unreachable ();
651	}
652	return false;
653	}
654
655	/* Return the outermost parent of component present in the chain of
656	component references handled by get_inner_reference in T with the
657	following property:
658	- the component is non-addressable
659	or NULL_TREE if no such parent exists. In the former cases, the alias
660	set of this parent is the alias set that must be used for T itself. */
661
662	tree
663	component_uses_parent_alias_set_from (const_tree t)
664	{
665	const_tree found = NULL_TREE;
666
667	while (handled_component_p (t))
668	{
669	if (ends_tbaa_access_path_p (t))
670	found = t;
671
672	t = TREE_OPERAND (t, 0);
673	}
674
675	if (found)
676	return TREE_OPERAND (found, 0);
677
678	return NULL_TREE;
679	}
680
681
682	/* Return whether the pointer-type T effective for aliasing may
683	access everything and thus the reference has to be assigned
684	alias-set zero. */
685
686	static bool
687	ref_all_alias_ptr_type_p (const_tree t)
688	{
689	return (VOID_TYPE_P (TREE_TYPE (t))
690	|| TYPE_REF_CAN_ALIAS_ALL (t));
691	}
692
693	/* Return the alias set for the memory pointed to by T, which may be
694	either a type or an expression. Return -1 if there is nothing
695	special about dereferencing T. */
696
697	static alias_set_type
698	get_deref_alias_set_1 (tree t)
699	{
700	/* All we care about is the type. */
701	if (! TYPE_P (t))
702	t = TREE_TYPE (t);
703
704	/* If we have an INDIRECT_REF via a void pointer, we don't
705	know anything about what that might alias. Likewise if the
706	pointer is marked that way. */
707	if (ref_all_alias_ptr_type_p (t))
708	return 0;
709
710	return -1;
711	}
712
713	/* Return the alias set for the memory pointed to by T, which may be
714	either a type or an expression. */
715
716	alias_set_type
717	get_deref_alias_set (tree t)
718	{
719	/* If we're not doing any alias analysis, just assume everything
720	aliases everything else. */
721	if (!flag_strict_aliasing)
722	return 0;
723
724	alias_set_type set = get_deref_alias_set_1 (t);
725
726	/* Fall back to the alias-set of the pointed-to type. */
727	if (set == -1)
728	{
729	if (! TYPE_P (t))
730	t = TREE_TYPE (t);
731	set = get_alias_set (TREE_TYPE (t));
732	}
733
734	return set;
735	}
736
737	/* Return the pointer-type relevant for TBAA purposes from the
738	memory reference tree *T or NULL_TREE in which case *T is
739	adjusted to point to the outermost component reference that
740	can be used for assigning an alias set. */
741
742	tree
743	reference_alias_ptr_type_1 (tree *t)
744	{
745	tree inner;
746
747	/* Get the base object of the reference. */
748	inner = *t;
749	while (handled_component_p (t: inner))
750	{
751	/* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
752	the type of any component references that wrap it to
753	determine the alias-set. */
754	if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
755	*t = TREE_OPERAND (inner, 0);
756	inner = TREE_OPERAND (inner, 0);
757	}
758
759	/* Handle pointer dereferences here, they can override the
760	alias-set. */
761	if (INDIRECT_REF_P (inner)
762	&& ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
763	return TREE_TYPE (TREE_OPERAND (inner, 0));
764	else if (TREE_CODE (inner) == TARGET_MEM_REF)
765	return TREE_TYPE (TMR_OFFSET (inner));
766	else if (TREE_CODE (inner) == MEM_REF
767	&& ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
768	return TREE_TYPE (TREE_OPERAND (inner, 1));
769
770	/* If the innermost reference is a MEM_REF that has a
771	conversion embedded treat it like a VIEW_CONVERT_EXPR above,
772	using the memory access type for determining the alias-set. */
773	if (TREE_CODE (inner) == MEM_REF
774	&& (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
775	!= TYPE_MAIN_VARIANT
776	(TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1))))))
777	{
778	tree alias_ptrtype = TREE_TYPE (TREE_OPERAND (inner, 1));
779	/* Unless we have the (aggregate) effective type of the access
780	somewhere on the access path. If we have for example
781	(&a->elts[i])->l.len exposed by abstraction we'd see
782	MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
783	of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
784	example. See PR111715. */
785	tree inner = *t;
786	while (handled_component_p (t: inner)
787	&& (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
788	!= TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype))))
789	inner = TREE_OPERAND (inner, 0);
790	if (TREE_CODE (inner) == MEM_REF)
791	return alias_ptrtype;
792	}
793
794	/* Otherwise, pick up the outermost object that we could have
795	a pointer to. */
796	tree tem = component_uses_parent_alias_set_from (t: *t);
797	if (tem)
798	*t = tem;
799
800	return NULL_TREE;
801	}
802
803	/* Return the pointer-type relevant for TBAA purposes from the
804	gimple memory reference tree T. This is the type to be used for
805	the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
806	and guarantees that get_alias_set will return the same alias
807	set for T and the replacement. */
808
809	tree
810	reference_alias_ptr_type (tree t)
811	{
812	/* If the frontend assigns this alias-set zero, preserve that. */
813	if (lang_hooks.get_alias_set (t) == 0)
814	return ptr_type_node;
815
816	tree ptype = reference_alias_ptr_type_1 (t: &t);
817	/* If there is a given pointer type for aliasing purposes, return it. */
818	if (ptype != NULL_TREE)
819	return ptype;
820
821	/* Otherwise build one from the outermost component reference we
822	may use. */
823	if (TREE_CODE (t) == MEM_REF
824	|| TREE_CODE (t) == TARGET_MEM_REF)
825	return TREE_TYPE (TREE_OPERAND (t, 1));
826	else
827	return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
828	}
829
830	/* Return whether the pointer-types T1 and T2 used to determine
831	two alias sets of two references will yield the same answer
832	from get_deref_alias_set. */
833
834	bool
835	alias_ptr_types_compatible_p (tree t1, tree t2)
836	{
837	if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
838	return true;
839
840	if (ref_all_alias_ptr_type_p (t: t1)
841	|| ref_all_alias_ptr_type_p (t: t2))
842	return false;
843
844	/* This function originally abstracts from simply comparing
845	get_deref_alias_set so that we are sure this still computes
846	the same result after LTO type merging is applied.
847	When in LTO type merging is done we can actually do this compare.
848	*/
849	if (in_lto_p)
850	return get_deref_alias_set (t: t1) == get_deref_alias_set (t: t2);
851	else
852	return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
853	== TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
854	}
855
856	/* Create emptry alias set entry. */
857
858	alias_set_entry *
859	init_alias_set_entry (alias_set_type set)
860	{
861	alias_set_entry *ase = ggc_alloc<alias_set_entry> ();
862	ase->alias_set = set;
863	ase->children = NULL;
864	ase->has_zero_child = false;
865	ase->is_pointer = false;
866	ase->has_pointer = false;
867	gcc_checking_assert (!get_alias_set_entry (set));
868	(*alias_sets)[set] = ase;
869	return ase;
870	}
871
872	/* Return the alias set for T, which may be either a type or an
873	expression. Call language-specific routine for help, if needed. */
874
875	alias_set_type
876	get_alias_set (tree t)
877	{
878	alias_set_type set;
879
880	/* We cannot give up with -fno-strict-aliasing because we need to build
881	proper type representations for possible functions which are built with
882	-fstrict-aliasing. */
883
884	/* return 0 if this or its type is an error. */
885	if (t == error_mark_node
886	|| (! TYPE_P (t)
887	&& (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
888	return 0;
889
890	/* We can be passed either an expression or a type. This and the
891	language-specific routine may make mutually-recursive calls to each other
892	to figure out what to do. At each juncture, we see if this is a tree
893	that the language may need to handle specially. First handle things that
894	aren't types. */
895	if (! TYPE_P (t))
896	{
897	/* Give the language a chance to do something with this tree
898	before we look at it. */
899	STRIP_NOPS (t);
900	set = lang_hooks.get_alias_set (t);
901	if (set != -1)
902	return set;
903
904	/* Get the alias pointer-type to use or the outermost object
905	that we could have a pointer to. */
906	tree ptype = reference_alias_ptr_type_1 (t: &t);
907	if (ptype != NULL)
908	return get_deref_alias_set (t: ptype);
909
910	/* If we've already determined the alias set for a decl, just return
911	it. This is necessary for C++ anonymous unions, whose component
912	variables don't look like union members (boo!). */
913	if (VAR_P (t)
914	&& DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
915	return MEM_ALIAS_SET (DECL_RTL (t));
916
917	/* Now all we care about is the type. */
918	t = TREE_TYPE (t);
919	}
920
921	/* Variant qualifiers don't affect the alias set, so get the main
922	variant. */
923	t = TYPE_MAIN_VARIANT (t);
924
925	if (AGGREGATE_TYPE_P (t)
926	&& TYPE_TYPELESS_STORAGE (t))
927	return 0;
928
929	/* Always use the canonical type as well. If this is a type that
930	requires structural comparisons to identify compatible types
931	use alias set zero. */
932	if (TYPE_STRUCTURAL_EQUALITY_P (t))
933	{
934	/* Allow the language to specify another alias set for this
935	type. */
936	set = lang_hooks.get_alias_set (t);
937	if (set != -1)
938	return set;
939	/* Handle structure type equality for pointer types, arrays and vectors.
940	This is easy to do, because the code below ignores canonical types on
941	these anyway. This is important for LTO, where TYPE_CANONICAL for
942	pointers cannot be meaningfully computed by the frontend. */
943	if (canonical_type_used_p (t))
944	{
945	/* In LTO we set canonical types for all types where it makes
946	sense to do so. Double check we did not miss some type. */
947	gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
948	return 0;
949	}
950	}
951	else
952	{
953	t = TYPE_CANONICAL (t);
954	gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
955	}
956
957	/* If this is a type with a known alias set, return it. */
958	gcc_checking_assert (t == TYPE_MAIN_VARIANT (t));
959	if (TYPE_ALIAS_SET_KNOWN_P (t))
960	return TYPE_ALIAS_SET (t);
961
962	/* We don't want to set TYPE_ALIAS_SET for incomplete types. */
963	if (!COMPLETE_TYPE_P (t))
964	{
965	/* For arrays with unknown size the conservative answer is the
966	alias set of the element type. */
967	if (TREE_CODE (t) == ARRAY_TYPE)
968	return get_alias_set (TREE_TYPE (t));
969
970	/* But return zero as a conservative answer for incomplete types. */
971	return 0;
972	}
973
974	/* See if the language has special handling for this type. */
975	set = lang_hooks.get_alias_set (t);
976	if (set != -1)
977	return set;
978
979	/* There are no objects of FUNCTION_TYPE, so there's no point in
980	using up an alias set for them. (There are, of course, pointers
981	and references to functions, but that's different.) */
982	else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
983	set = 0;
984
985	/* Unless the language specifies otherwise, let vector types alias
986	their components. This avoids some nasty type punning issues in
987	normal usage. And indeed lets vectors be treated more like an
988	array slice. */
989	else if (TREE_CODE (t) == VECTOR_TYPE)
990	set = get_alias_set (TREE_TYPE (t));
991
992	/* Unless the language specifies otherwise, treat array types the
993	same as their components. This avoids the asymmetry we get
994	through recording the components. Consider accessing a
995	character(kind=1) through a reference to a character(kind=1)[1:1].
996	Or consider if we want to assign integer(kind=4)[0:D.1387] and
997	integer(kind=4)[4] the same alias set or not.
998	Just be pragmatic here and make sure the array and its element
999	type get the same alias set assigned. */
1000	else if (TREE_CODE (t) == ARRAY_TYPE
1001	&& (!TYPE_NONALIASED_COMPONENT (t)
1002	|| TYPE_STRUCTURAL_EQUALITY_P (t)))
1003	set = get_alias_set (TREE_TYPE (t));
1004
1005	/* From the former common C and C++ langhook implementation:
1006
1007	Unfortunately, there is no canonical form of a pointer type.
1008	In particular, if we have `typedef int I', then `int *', and
1009	`I *' are different types. So, we have to pick a canonical
1010	representative. We do this below.
1011
1012	Technically, this approach is actually more conservative that
1013	it needs to be. In particular, `const int *' and `int *'
1014	should be in different alias sets, according to the C and C++
1015	standard, since their types are not the same, and so,
1016	technically, an `int **' and `const int **' cannot point at
1017	the same thing.
1018
1019	But, the standard is wrong. In particular, this code is
1020	legal C++:
1021
1022	int *ip;
1023	int **ipp = &ip;
1024	const int* const* cipp = ipp;
1025	And, it doesn't make sense for that to be legal unless you
1026	can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1027	the pointed-to types. This issue has been reported to the
1028	C++ committee.
1029
1030	For this reason go to canonical type of the unqalified pointer type.
1031	Until GCC 6 this code set all pointers sets to have alias set of
1032	ptr_type_node but that is a bad idea, because it prevents disabiguations
1033	in between pointers. For Firefox this accounts about 20% of all
1034	disambiguations in the program. */
1035	else if (POINTER_TYPE_P (t) && t != ptr_type_node)
1036	{
1037	tree p;
1038	auto_vec <bool, 8> reference;
1039
1040	/* Unnest all pointers and references.
1041	We also want to make pointer to array/vector equivalent to pointer to
1042	its element (see the reasoning above). Skip all those types, too. */
1043	for (p = t; POINTER_TYPE_P (p)
1044	|| (TREE_CODE (p) == ARRAY_TYPE
1045	&& (!TYPE_NONALIASED_COMPONENT (p)
1046	|| !COMPLETE_TYPE_P (p)
1047	|| TYPE_STRUCTURAL_EQUALITY_P (p)))
1048	|| TREE_CODE (p) == VECTOR_TYPE;
1049	p = TREE_TYPE (p))
1050	{
1051	/* Ada supports recursive pointers. Instead of doing recursion
1052	check, just give up once the preallocated space of 8 elements
1053	is up. In this case just punt to void * alias set. */
1054	if (reference.length () == 8)
1055	{
1056	p = ptr_type_node;
1057	break;
1058	}
1059	if (TREE_CODE (p) == REFERENCE_TYPE)
1060	/* In LTO we want languages that use references to be compatible
1061	with languages that use pointers. */
1062	reference.safe_push (obj: true && !in_lto_p);
1063	if (TREE_CODE (p) == POINTER_TYPE)
1064	reference.safe_push (obj: false);
1065	}
1066	p = TYPE_MAIN_VARIANT (p);
1067
1068	/* In LTO for C++ programs we can turn incomplete types to complete
1069	using ODR name lookup. */
1070	if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (t: p))
1071	{
1072	p = prevailing_odr_type (type: p);
1073	gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p);
1074	}
1075
1076	/* Make void * compatible with char * and also void **.
1077	Programs are commonly violating TBAA by this.
1078
1079	We also make void * to conflict with every pointer
1080	(see record_component_aliases) and thus it is safe it to use it for
1081	pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1082	if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
1083	set = get_alias_set (ptr_type_node);
1084	else
1085	{
1086	/* Rebuild pointer type starting from canonical types using
1087	unqualified pointers and references only. This way all such
1088	pointers will have the same alias set and will conflict with
1089	each other.
1090
1091	Most of time we already have pointers or references of a given type.
1092	If not we build new one just to be sure that if someone later
1093	(probably only middle-end can, as we should assign all alias
1094	classes only after finishing translation unit) builds the pointer
1095	type, the canonical type will match. */
1096	p = TYPE_CANONICAL (p);
1097	while (!reference.is_empty ())
1098	{
1099	if (reference.pop ())
1100	p = build_reference_type (p);
1101	else
1102	p = build_pointer_type (p);
1103	gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1104	/* build_pointer_type should always return the canonical type.
1105	For LTO TYPE_CANOINCAL may be NULL, because we do not compute
1106	them. Be sure that frontends do not glob canonical types of
1107	pointers in unexpected way and that p == TYPE_CANONICAL (p)
1108	in all other cases. */
1109	gcc_checking_assert (!TYPE_CANONICAL (p)
1110	|| p == TYPE_CANONICAL (p));
1111	}
1112
1113	/* Assign the alias set to both p and t.
1114	We cannot call get_alias_set (p) here as that would trigger
1115	infinite recursion when p == t. In other cases it would just
1116	trigger unnecesary legwork of rebuilding the pointer again. */
1117	gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1118	if (TYPE_ALIAS_SET_KNOWN_P (p))
1119	set = TYPE_ALIAS_SET (p);
1120	else
1121	{
1122	set = new_alias_set ();
1123	TYPE_ALIAS_SET (p) = set;
1124	}
1125	}
1126	}
1127	/* Alias set of ptr_type_node is special and serve as universal pointer which
1128	is TBAA compatible with every other pointer type. Be sure we have the
1129	alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1130	of pointer types NULL. */
1131	else if (t == ptr_type_node)
1132	set = new_alias_set ();
1133
1134	/* Otherwise make a new alias set for this type. */
1135	else
1136	{
1137	/* Each canonical type gets its own alias set, so canonical types
1138	shouldn't form a tree. It doesn't really matter for types
1139	we handle specially above, so only check it where it possibly
1140	would result in a bogus alias set. */
1141	gcc_checking_assert (TYPE_CANONICAL (t) == t);
1142
1143	set = new_alias_set ();
1144	}
1145
1146	TYPE_ALIAS_SET (t) = set;
1147
1148	/* If this is an aggregate type or a complex type, we must record any
1149	component aliasing information. */
1150	if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
1151	record_component_aliases (t);
1152
1153	/* We treat pointer types specially in alias_set_subset_of. */
1154	if (POINTER_TYPE_P (t) && set)
1155	{
1156	alias_set_entry *ase = get_alias_set_entry (alias_set: set);
1157	if (!ase)
1158	ase = init_alias_set_entry (set);
1159	ase->is_pointer = true;
1160	ase->has_pointer = true;
1161	}
1162
1163	return set;
1164	}
1165
1166	/* Return a brand-new alias set. */
1167
1168	alias_set_type
1169	new_alias_set (void)
1170	{
1171	if (alias_sets == 0)
1172	vec_safe_push (v&: alias_sets, obj: (alias_set_entry *) NULL);
1173	vec_safe_push (v&: alias_sets, obj: (alias_set_entry *) NULL);
1174	return alias_sets->length () - 1;
1175	}
1176
1177	/* Indicate that things in SUBSET can alias things in SUPERSET, but that
1178	not everything that aliases SUPERSET also aliases SUBSET. For example,
1179	in C, a store to an `int' can alias a load of a structure containing an
1180	`int', and vice versa. But it can't alias a load of a 'double' member
1181	of the same structure. Here, the structure would be the SUPERSET and
1182	`int' the SUBSET. This relationship is also described in the comment at
1183	the beginning of this file.
1184
1185	This function should be called only once per SUPERSET/SUBSET pair.
1186
1187	It is illegal for SUPERSET to be zero; everything is implicitly a
1188	subset of alias set zero. */
1189
1190	void
1191	record_alias_subset (alias_set_type superset, alias_set_type subset)
1192	{
1193	alias_set_entry *superset_entry;
1194	alias_set_entry *subset_entry;
1195
1196	/* It is possible in complex type situations for both sets to be the same,
1197	in which case we can ignore this operation. */
1198	if (superset == subset)
1199	return;
1200
1201	gcc_assert (superset);
1202
1203	superset_entry = get_alias_set_entry (alias_set: superset);
1204	if (superset_entry == 0)
1205	{
1206	/* Create an entry for the SUPERSET, so that we have a place to
1207	attach the SUBSET. */
1208	superset_entry = init_alias_set_entry (set: superset);
1209	}
1210
1211	if (subset == 0)
1212	superset_entry->has_zero_child = 1;
1213	else
1214	{
1215	if (!superset_entry->children)
1216	superset_entry->children
1217	= hash_map<alias_set_hash, int>::create_ggc (size: 64);
1218
1219	/* Enter the SUBSET itself as a child of the SUPERSET. If it was
1220	already there we're done. */
1221	if (superset_entry->children->put (k: subset, v: 0))
1222	return;
1223
1224	subset_entry = get_alias_set_entry (alias_set: subset);
1225	/* If there is an entry for the subset, enter all of its children
1226	(if they are not already present) as children of the SUPERSET. */
1227	if (subset_entry)
1228	{
1229	if (subset_entry->has_zero_child)
1230	superset_entry->has_zero_child = true;
1231	if (subset_entry->has_pointer)
1232	superset_entry->has_pointer = true;
1233
1234	if (subset_entry->children)
1235	{
1236	hash_map<alias_set_hash, int>::iterator iter
1237	= subset_entry->children->begin ();
1238	for (; iter != subset_entry->children->end (); ++iter)
1239	superset_entry->children->put (k: (*iter).first, v: (*iter).second);
1240	}
1241	}
1242	}
1243	}
1244
1245	/* Record that component types of TYPE, if any, are part of SUPERSET for
1246	aliasing purposes. For record types, we only record component types
1247	for fields that are not marked non-addressable. For array types, we
1248	only record the component type if it is not marked non-aliased. */
1249
1250	void
1251	record_component_aliases (tree type, alias_set_type superset)
1252	{
1253	tree field;
1254
1255	if (superset == 0)
1256	return;
1257
1258	switch (TREE_CODE (type))
1259	{
1260	case RECORD_TYPE:
1261	case UNION_TYPE:
1262	case QUAL_UNION_TYPE:
1263	{
1264	/* LTO non-ODR type merging does not make any difference between
1265	component pointer types. We may have
1266
1267	struct foo {int *a;};
1268
1269	as TYPE_CANONICAL of
1270
1271	struct bar {float *a;};
1272
1273	Because accesses to int * and float * do not alias, we would get
1274	false negative when accessing the same memory location by
1275	float ** and bar *. We thus record the canonical type as:
1276
1277	struct {void *a;};
1278
1279	void * is special cased and works as a universal pointer type.
1280	Accesses to it conflicts with accesses to any other pointer
1281	type. */
1282	bool void_pointers = in_lto_p
1283	&& (!odr_type_p (t: type)
1284	|| !odr_based_tbaa_p (type));
1285	for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
1286	if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
1287	{
1288	tree t = TREE_TYPE (field);
1289	if (void_pointers)
1290	{
1291	/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1292	element type and that type has to be normalized to void *,
1293	too, in the case it is a pointer. */
1294	while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
1295	{
1296	gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
1297	t = TREE_TYPE (t);
1298	}
1299	if (POINTER_TYPE_P (t))
1300	t = ptr_type_node;
1301	else if (flag_checking)
1302	gcc_checking_assert (get_alias_set (t)
1303	== get_alias_set (TREE_TYPE (field)));
1304	}
1305
1306	alias_set_type set = get_alias_set (t);
1307	record_alias_subset (superset, subset: set);
1308	/* If the field has alias-set zero make sure to still record
1309	any componets of it. This makes sure that for
1310	struct A {
1311	struct B {
1312	int i;
1313	char c[4];
1314	} b;
1315	};
1316	in C++ even though 'B' has alias-set zero because
1317	TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1318	'int' as subset. */
1319	if (set == 0)
1320	record_component_aliases (type: t, superset);
1321	}
1322	}
1323	break;
1324
1325	case COMPLEX_TYPE:
1326	record_alias_subset (superset, subset: get_alias_set (TREE_TYPE (type)));
1327	break;
1328
1329	/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1330	element type. */
1331
1332	default:
1333	break;
1334	}
1335	}
1336
1337	/* Record that component types of TYPE, if any, are part of that type for
1338	aliasing purposes. For record types, we only record component types
1339	for fields that are not marked non-addressable. For array types, we
1340	only record the component type if it is not marked non-aliased. */
1341
1342	void
1343	record_component_aliases (tree type)
1344	{
1345	alias_set_type superset = get_alias_set (t: type);
1346	record_component_aliases (type, superset);
1347	}
1348
1349
1350	/* Allocate an alias set for use in storing and reading from the varargs
1351	spill area. */
1352
1353	static GTY(()) alias_set_type varargs_set = -1;
1354
1355	alias_set_type
1356	get_varargs_alias_set (void)
1357	{
1358	#if 1
1359	/* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1360	varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1361	consistently use the varargs alias set for loads from the varargs
1362	area. So don't use it anywhere. */
1363	return 0;
1364	#else
1365	if (varargs_set == -1)
1366	varargs_set = new_alias_set ();
1367
1368	return varargs_set;
1369	#endif
1370	}
1371
1372	/* Likewise, but used for the fixed portions of the frame, e.g., register
1373	save areas. */
1374
1375	static GTY(()) alias_set_type frame_set = -1;
1376
1377	alias_set_type
1378	get_frame_alias_set (void)
1379	{
1380	if (frame_set == -1)
1381	frame_set = new_alias_set ();
1382
1383	return frame_set;
1384	}
1385
1386	/* Create a new, unique base with id ID. */
1387
1388	static rtx
1389	unique_base_value (HOST_WIDE_INT id)
1390	{
1391	return gen_rtx_ADDRESS (Pmode, id);
1392	}
1393
1394	/* Return true if accesses based on any other base value cannot alias
1395	those based on X. */
1396
1397	static bool
1398	unique_base_value_p (rtx x)
1399	{
1400	return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1401	}
1402
1403	/* Inside SRC, the source of a SET, find a base address. */
1404
1405	static rtx
1406	find_base_value (rtx src)
1407	{
1408	unsigned int regno;
1409	scalar_int_mode int_mode;
1410
1411	#if defined (FIND_BASE_TERM)
1412	/* Try machine-dependent ways to find the base term. */
1413	src = FIND_BASE_TERM (src);
1414	#endif
1415
1416	switch (GET_CODE (src))
1417	{
1418	case SYMBOL_REF:
1419	case LABEL_REF:
1420	return src;
1421
1422	case REG:
1423	regno = REGNO (src);
1424	/* At the start of a function, argument registers have known base
1425	values which may be lost later. Returning an ADDRESS
1426	expression here allows optimization based on argument values
1427	even when the argument registers are used for other purposes. */
1428	if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1429	return new_reg_base_value[regno];
1430
1431	/* If a pseudo has a known base value, return it. Do not do this
1432	for non-fixed hard regs since it can result in a circular
1433	dependency chain for registers which have values at function entry.
1434
1435	The test above is not sufficient because the scheduler may move
1436	a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1437	if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1438	&& regno < vec_safe_length (v: reg_base_value))
1439	{
1440	/* If we're inside init_alias_analysis, use new_reg_base_value
1441	to reduce the number of relaxation iterations. */
1442	if (new_reg_base_value && new_reg_base_value[regno]
1443	&& DF_REG_DEF_COUNT (regno) == 1)
1444	return new_reg_base_value[regno];
1445
1446	if ((*reg_base_value)[regno])
1447	return (*reg_base_value)[regno];
1448	}
1449
1450	return 0;
1451
1452	case MEM:
1453	/* Check for an argument passed in memory. Only record in the
1454	copying-arguments block; it is too hard to track changes
1455	otherwise. */
1456	if (copying_arguments
1457	&& (XEXP (src, 0) == arg_pointer_rtx
1458	|| (GET_CODE (XEXP (src, 0)) == PLUS
1459	&& XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1460	return arg_base_value;
1461	return 0;
1462
1463	case CONST:
1464	src = XEXP (src, 0);
1465	if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1466	break;
1467
1468	/* fall through */
1469
1470	case PLUS:
1471	case MINUS:
1472	{
1473	rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1474
1475	/* If either operand is a CONST_INT, then the other is the base. */
1476	if (CONST_INT_P (src_1))
1477	return find_base_value (src: src_0);
1478	else if (CONST_INT_P (src_0))
1479	return find_base_value (src: src_1);
1480
1481	return 0;
1482	}
1483
1484	case LO_SUM:
1485	/* The standard form is (lo_sum reg sym) so look only at the
1486	second operand. */
1487	return find_base_value (XEXP (src, 1));
1488
1489	case AND:
1490	/* Look through aligning ANDs. And AND with zero or one with
1491	the LSB set isn't one (see for example PR92462). */
1492	if (CONST_INT_P (XEXP (src, 1))
1493	&& INTVAL (XEXP (src, 1)) != 0
1494	&& (INTVAL (XEXP (src, 1)) & 1) == 0)
1495	return find_base_value (XEXP (src, 0));
1496	return 0;
1497
1498	case TRUNCATE:
1499	/* As we do not know which address space the pointer is referring to, we can
1500	handle this only if the target does not support different pointer or
1501	address modes depending on the address space. */
1502	if (!target_default_pointer_address_modes_p ())
1503	break;
1504	if (!is_a <scalar_int_mode> (GET_MODE (src), result: &int_mode)
1505	|| GET_MODE_PRECISION (mode: int_mode) < GET_MODE_PRECISION (Pmode))
1506	break;
1507	/* Fall through. */
1508	case HIGH:
1509	case PRE_INC:
1510	case PRE_DEC:
1511	case POST_INC:
1512	case POST_DEC:
1513	case PRE_MODIFY:
1514	case POST_MODIFY:
1515	return find_base_value (XEXP (src, 0));
1516
1517	case ZERO_EXTEND:
1518	case SIGN_EXTEND: /* used for NT/Alpha pointers */
1519	/* As we do not know which address space the pointer is referring to, we can
1520	handle this only if the target does not support different pointer or
1521	address modes depending on the address space. */
1522	if (!target_default_pointer_address_modes_p ())
1523	break;
1524
1525	{
1526	rtx temp = find_base_value (XEXP (src, 0));
1527
1528	if (temp != 0 && CONSTANT_P (temp))
1529	temp = convert_memory_address (Pmode, temp);
1530
1531	return temp;
1532	}
1533
1534	default:
1535	break;
1536	}
1537
1538	return 0;
1539	}
1540
1541	/* Called from init_alias_analysis indirectly through note_stores,
1542	or directly if DEST is a register with a REG_NOALIAS note attached.
1543	SET is null in the latter case. */
1544
1545	/* While scanning insns to find base values, reg_seen[N] is nonzero if
1546	register N has been set in this function. */
1547	static sbitmap reg_seen;
1548
1549	static void
1550	record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1551	{
1552	unsigned regno;
1553	rtx src;
1554	int n;
1555
1556	if (!REG_P (dest))
1557	return;
1558
1559	regno = REGNO (dest);
1560
1561	gcc_checking_assert (regno < reg_base_value->length ());
1562
1563	n = REG_NREGS (dest);
1564	if (n != 1)
1565	{
1566	while (--n >= 0)
1567	{
1568	bitmap_set_bit (map: reg_seen, bitno: regno + n);
1569	new_reg_base_value[regno + n] = 0;
1570	}
1571	return;
1572	}
1573
1574	if (set)
1575	{
1576	/* A CLOBBER wipes out any old value but does not prevent a previously
1577	unset register from acquiring a base address (i.e. reg_seen is not
1578	set). */
1579	if (GET_CODE (set) == CLOBBER)
1580	{
1581	new_reg_base_value[regno] = 0;
1582	return;
1583	}
1584
1585	src = SET_SRC (set);
1586	}
1587	else
1588	{
1589	/* There's a REG_NOALIAS note against DEST. */
1590	if (bitmap_bit_p (map: reg_seen, bitno: regno))
1591	{
1592	new_reg_base_value[regno] = 0;
1593	return;
1594	}
1595	bitmap_set_bit (map: reg_seen, bitno: regno);
1596	new_reg_base_value[regno] = unique_base_value (id: unique_id++);
1597	return;
1598	}
1599
1600	/* If this is not the first set of REGNO, see whether the new value
1601	is related to the old one. There are two cases of interest:
1602
1603	(1) The register might be assigned an entirely new value
1604	that has the same base term as the original set.
1605
1606	(2) The set might be a simple self-modification that
1607	cannot change REGNO's base value.
1608
1609	If neither case holds, reject the original base value as invalid.
1610	Note that the following situation is not detected:
1611
1612	extern int x, y; int *p = &x; p += (&y-&x);
1613
1614	ANSI C does not allow computing the difference of addresses
1615	of distinct top level objects. */
1616	if (new_reg_base_value[regno] != 0
1617	&& find_base_value (src) != new_reg_base_value[regno])
1618	switch (GET_CODE (src))
1619	{
1620	case LO_SUM:
1621	case MINUS:
1622	if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1623	new_reg_base_value[regno] = 0;
1624	break;
1625	case PLUS:
1626	/* If the value we add in the PLUS is also a valid base value,
1627	this might be the actual base value, and the original value
1628	an index. */
1629	{
1630	rtx other = NULL_RTX;
1631
1632	if (XEXP (src, 0) == dest)
1633	other = XEXP (src, 1);
1634	else if (XEXP (src, 1) == dest)
1635	other = XEXP (src, 0);
1636
1637	if (! other || find_base_value (src: other))
1638	new_reg_base_value[regno] = 0;
1639	break;
1640	}
1641	case AND:
1642	if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1643	new_reg_base_value[regno] = 0;
1644	break;
1645	default:
1646	new_reg_base_value[regno] = 0;
1647	break;
1648	}
1649	/* If this is the first set of a register, record the value. */
1650	else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1651	&& ! bitmap_bit_p (map: reg_seen, bitno: regno) && new_reg_base_value[regno] == 0)
1652	new_reg_base_value[regno] = find_base_value (src);
1653
1654	bitmap_set_bit (map: reg_seen, bitno: regno);
1655	}
1656
1657	/* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1658	using hard registers with non-null REG_BASE_VALUE for renaming. */
1659	rtx
1660	get_reg_base_value (unsigned int regno)
1661	{
1662	return (*reg_base_value)[regno];
1663	}
1664
1665	/* If a value is known for REGNO, return it. */
1666
1667	rtx
1668	get_reg_known_value (unsigned int regno)
1669	{
1670	if (regno >= FIRST_PSEUDO_REGISTER)
1671	{
1672	regno -= FIRST_PSEUDO_REGISTER;
1673	if (regno < vec_safe_length (v: reg_known_value))
1674	return (*reg_known_value)[regno];
1675	}
1676	return NULL;
1677	}
1678
1679	/* Set it. */
1680
1681	static void
1682	set_reg_known_value (unsigned int regno, rtx val)
1683	{
1684	if (regno >= FIRST_PSEUDO_REGISTER)
1685	{
1686	regno -= FIRST_PSEUDO_REGISTER;
1687	if (regno < vec_safe_length (v: reg_known_value))
1688	(*reg_known_value)[regno] = val;
1689	}
1690	}
1691
1692	/* Similarly for reg_known_equiv_p. */
1693
1694	bool
1695	get_reg_known_equiv_p (unsigned int regno)
1696	{
1697	if (regno >= FIRST_PSEUDO_REGISTER)
1698	{
1699	regno -= FIRST_PSEUDO_REGISTER;
1700	if (regno < vec_safe_length (v: reg_known_value))
1701	return bitmap_bit_p (map: reg_known_equiv_p, bitno: regno);
1702	}
1703	return false;
1704	}
1705
1706	static void
1707	set_reg_known_equiv_p (unsigned int regno, bool val)
1708	{
1709	if (regno >= FIRST_PSEUDO_REGISTER)
1710	{
1711	regno -= FIRST_PSEUDO_REGISTER;
1712	if (regno < vec_safe_length (v: reg_known_value))
1713	{
1714	if (val)
1715	bitmap_set_bit (map: reg_known_equiv_p, bitno: regno);
1716	else
1717	bitmap_clear_bit (map: reg_known_equiv_p, bitno: regno);
1718	}
1719	}
1720	}
1721
1722
1723	/* Returns a canonical version of X, from the point of view alias
1724	analysis. (For example, if X is a MEM whose address is a register,
1725	and the register has a known value (say a SYMBOL_REF), then a MEM
1726	whose address is the SYMBOL_REF is returned.) */
1727
1728	rtx
1729	canon_rtx (rtx x)
1730	{
1731	/* Recursively look for equivalences. */
1732	if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1733	{
1734	rtx t = get_reg_known_value (REGNO (x));
1735	if (t == x)
1736	return x;
1737	if (t)
1738	return canon_rtx (x: t);
1739	}
1740
1741	if (GET_CODE (x) == PLUS)
1742	{
1743	rtx x0 = canon_rtx (XEXP (x, 0));
1744	rtx x1 = canon_rtx (XEXP (x, 1));
1745
1746	if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1747	return simplify_gen_binary (code: PLUS, GET_MODE (x), op0: x0, op1: x1);
1748	}
1749
1750	/* This gives us much better alias analysis when called from
1751	the loop optimizer. Note we want to leave the original
1752	MEM alone, but need to return the canonicalized MEM with
1753	all the flags with their original values. */
1754	else if (MEM_P (x))
1755	x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1756
1757	return x;
1758	}
1759
1760	/* Return true if X and Y are identical-looking rtx's.
1761	Expect that X and Y has been already canonicalized.
1762
1763	We use the data in reg_known_value above to see if two registers with
1764	different numbers are, in fact, equivalent. */
1765
1766	static bool
1767	rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1768	{
1769	int i;
1770	int j;
1771	enum rtx_code code;
1772	const char *fmt;
1773
1774	if (x == 0 && y == 0)
1775	return true;
1776	if (x == 0 || y == 0)
1777	return false;
1778
1779	if (x == y)
1780	return true;
1781
1782	code = GET_CODE (x);
1783	/* Rtx's of different codes cannot be equal. */
1784	if (code != GET_CODE (y))
1785	return false;
1786
1787	/* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1788	(REG:SI x) and (REG:HI x) are NOT equivalent. */
1789
1790	if (GET_MODE (x) != GET_MODE (y))
1791	return false;
1792
1793	/* Some RTL can be compared without a recursive examination. */
1794	switch (code)
1795	{
1796	case REG:
1797	return REGNO (x) == REGNO (y);
1798
1799	case LABEL_REF:
1800	return label_ref_label (ref: x) == label_ref_label (ref: y);
1801
1802	case SYMBOL_REF:
1803	{
1804	HOST_WIDE_INT distance = 0;
1805	return (compare_base_symbol_refs (x, y, &distance) == 1
1806	&& distance == 0);
1807	}
1808
1809	case ENTRY_VALUE:
1810	/* This is magic, don't go through canonicalization et al. */
1811	return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1812
1813	case VALUE:
1814	CASE_CONST_UNIQUE:
1815	/* Pointer equality guarantees equality for these nodes. */
1816	return false;
1817
1818	default:
1819	break;
1820	}
1821
1822	/* canon_rtx knows how to handle plus. No need to canonicalize. */
1823	if (code == PLUS)
1824	return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1825	&& rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1826	|| (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1827	&& rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1828	/* For commutative operations, the RTX match if the operand match in any
1829	order. Also handle the simple binary and unary cases without a loop. */
1830	if (COMMUTATIVE_P (x))
1831	{
1832	rtx xop0 = canon_rtx (XEXP (x, 0));
1833	rtx yop0 = canon_rtx (XEXP (y, 0));
1834	rtx yop1 = canon_rtx (XEXP (y, 1));
1835
1836	return ((rtx_equal_for_memref_p (x: xop0, y: yop0)
1837	&& rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)), y: yop1))
1838	|| (rtx_equal_for_memref_p (x: xop0, y: yop1)
1839	&& rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)), y: yop0)));
1840	}
1841	else if (NON_COMMUTATIVE_P (x))
1842	{
1843	return (rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 0)),
1844	y: canon_rtx (XEXP (y, 0)))
1845	&& rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)),
1846	y: canon_rtx (XEXP (y, 1))));
1847	}
1848	else if (UNARY_P (x))
1849	return rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 0)),
1850	y: canon_rtx (XEXP (y, 0)));
1851
1852	/* Compare the elements. If any pair of corresponding elements
1853	fail to match, return false for the whole things.
1854
1855	Limit cases to types which actually appear in addresses. */
1856
1857	fmt = GET_RTX_FORMAT (code);
1858	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1859	{
1860	switch (fmt[i])
1861	{
1862	case 'i':
1863	if (XINT (x, i) != XINT (y, i))
1864	return false;
1865	break;
1866
1867	case 'p':
1868	if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1869	return false;
1870	break;
1871
1872	case 'E':
1873	/* Two vectors must have the same length. */
1874	if (XVECLEN (x, i) != XVECLEN (y, i))
1875	return false;
1876
1877	/* And the corresponding elements must match. */
1878	for (j = 0; j < XVECLEN (x, i); j++)
1879	if (rtx_equal_for_memref_p (x: canon_rtx (XVECEXP (x, i, j)),
1880	y: canon_rtx (XVECEXP (y, i, j))) == 0)
1881	return false;
1882	break;
1883
1884	case 'e':
1885	if (rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, i)),
1886	y: canon_rtx (XEXP (y, i))) == 0)
1887	return false;
1888	break;
1889
1890	/* This can happen for asm operands. */
1891	case 's':
1892	if (strcmp (XSTR (x, i), XSTR (y, i)))
1893	return false;
1894	break;
1895
1896	/* This can happen for an asm which clobbers memory. */
1897	case '0':
1898	break;
1899
1900	/* It is believed that rtx's at this level will never
1901	contain anything but integers and other rtx's,
1902	except for within LABEL_REFs and SYMBOL_REFs. */
1903	default:
1904	gcc_unreachable ();
1905	}
1906	}
1907	return true;
1908	}
1909
1910	static rtx
1911	find_base_term (rtx x, vec<std::pair<cselib_val *,
1912	struct elt_loc_list *> > &visited_vals)
1913	{
1914	cselib_val *val;
1915	struct elt_loc_list *l, *f;
1916	rtx ret;
1917	scalar_int_mode int_mode;
1918
1919	#if defined (FIND_BASE_TERM)
1920	/* Try machine-dependent ways to find the base term. */
1921	x = FIND_BASE_TERM (x);
1922	#endif
1923
1924	switch (GET_CODE (x))
1925	{
1926	case REG:
1927	return REG_BASE_VALUE (x);
1928
1929	case TRUNCATE:
1930	/* As we do not know which address space the pointer is referring to, we can
1931	handle this only if the target does not support different pointer or
1932	address modes depending on the address space. */
1933	if (!target_default_pointer_address_modes_p ())
1934	return 0;
1935	if (!is_a <scalar_int_mode> (GET_MODE (x), result: &int_mode)
1936	|| GET_MODE_PRECISION (mode: int_mode) < GET_MODE_PRECISION (Pmode))
1937	return 0;
1938	/* Fall through. */
1939	case HIGH:
1940	case PRE_INC:
1941	case PRE_DEC:
1942	case POST_INC:
1943	case POST_DEC:
1944	case PRE_MODIFY:
1945	case POST_MODIFY:
1946	return find_base_term (XEXP (x, 0), visited_vals);
1947
1948	case ZERO_EXTEND:
1949	case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1950	/* As we do not know which address space the pointer is referring to, we can
1951	handle this only if the target does not support different pointer or
1952	address modes depending on the address space. */
1953	if (!target_default_pointer_address_modes_p ())
1954	return 0;
1955
1956	{
1957	rtx temp = find_base_term (XEXP (x, 0), visited_vals);
1958
1959	if (temp != 0 && CONSTANT_P (temp))
1960	temp = convert_memory_address (Pmode, temp);
1961
1962	return temp;
1963	}
1964
1965	case VALUE:
1966	val = CSELIB_VAL_PTR (x);
1967	ret = NULL_RTX;
1968
1969	if (!val)
1970	return ret;
1971
1972	if (cselib_sp_based_value_p (val))
1973	return static_reg_base_value[STACK_POINTER_REGNUM];
1974
1975	if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
1976	return ret;
1977
1978	f = val->locs;
1979	/* Reset val->locs to avoid infinite recursion. */
1980	if (f)
1981	visited_vals.safe_push (obj: std::make_pair (x&: val, y&: f));
1982	val->locs = NULL;
1983
1984	for (l = f; l; l = l->next)
1985	if (GET_CODE (l->loc) == VALUE
1986	&& CSELIB_VAL_PTR (l->loc)->locs
1987	&& !CSELIB_VAL_PTR (l->loc)->locs->next
1988	&& CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1989	continue;
1990	else if ((ret = find_base_term (x: l->loc, visited_vals)) != 0)
1991	break;
1992
1993	return ret;
1994
1995	case LO_SUM:
1996	/* The standard form is (lo_sum reg sym) so look only at the
1997	second operand. */
1998	return find_base_term (XEXP (x, 1), visited_vals);
1999
2000	case CONST:
2001	x = XEXP (x, 0);
2002	if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2003	return 0;
2004	/* Fall through. */
2005	case PLUS:
2006	case MINUS:
2007	{
2008	rtx tmp1 = XEXP (x, 0);
2009	rtx tmp2 = XEXP (x, 1);
2010
2011	/* This is a little bit tricky since we have to determine which of
2012	the two operands represents the real base address. Otherwise this
2013	routine may return the index register instead of the base register.
2014
2015	That may cause us to believe no aliasing was possible, when in
2016	fact aliasing is possible.
2017
2018	We use a few simple tests to guess the base register. Additional
2019	tests can certainly be added. For example, if one of the operands
2020	is a shift or multiply, then it must be the index register and the
2021	other operand is the base register. */
2022
2023	if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2024	return find_base_term (x: tmp2, visited_vals);
2025
2026	if (CONST_INT_P (tmp1))
2027	std::swap (a&: tmp1, b&: tmp2);
2028
2029	/* We can only handle binary operators when one of the operands
2030	never leads to a base value. */
2031	if (CONST_INT_P (tmp2))
2032	return find_base_term (x: tmp1, visited_vals);
2033
2034	/* We could not determine which of the two operands was the
2035	base register and which was the index. So we can determine
2036	nothing from the base alias check. */
2037	return 0;
2038	}
2039
2040	case AND:
2041	/* Look through aligning ANDs. And AND with zero or one with
2042	the LSB set isn't one (see for example PR92462). */
2043	if (CONST_INT_P (XEXP (x, 1))
2044	&& INTVAL (XEXP (x, 1)) != 0
2045	&& (INTVAL (XEXP (x, 1)) & 1) == 0)
2046	return find_base_term (XEXP (x, 0), visited_vals);
2047	return 0;
2048
2049	case SYMBOL_REF:
2050	case LABEL_REF:
2051	return x;
2052
2053	default:
2054	return 0;
2055	}
2056	}
2057
2058	/* Wrapper around the worker above which removes locs from visited VALUEs
2059	to avoid visiting them multiple times. We unwind that changes here. */
2060
2061	static rtx
2062	find_base_term (rtx x)
2063	{
2064	auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2065	rtx res = find_base_term (x, visited_vals);
2066	for (unsigned i = 0; i < visited_vals.length (); ++i)
2067	visited_vals[i].first->locs = visited_vals[i].second;
2068	return res;
2069	}
2070
2071	/* Return true if accesses to address X may alias accesses based
2072	on the stack pointer. */
2073
2074	bool
2075	may_be_sp_based_p (rtx x)
2076	{
2077	rtx base = find_base_term (x);
2078	return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2079	}
2080
2081	/* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2082	if they refer to different objects and -1 if we cannot decide. */
2083
2084	int
2085	compare_base_decls (tree base1, tree base2)
2086	{
2087	int ret;
2088	gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2089	if (base1 == base2)
2090	return 1;
2091
2092	/* If we have two register decls with register specification we
2093	cannot decide unless their assembler names are the same. */
2094	if (VAR_P (base1)
2095	&& VAR_P (base2)
2096	&& DECL_HARD_REGISTER (base1)
2097	&& DECL_HARD_REGISTER (base2)
2098	&& DECL_ASSEMBLER_NAME_SET_P (base1)
2099	&& DECL_ASSEMBLER_NAME_SET_P (base2))
2100	{
2101	if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2102	return 1;
2103	return -1;
2104	}
2105
2106	/* Declarations of non-automatic variables may have aliases. All other
2107	decls are unique. */
2108	if (!decl_in_symtab_p (decl: base1)
2109	|| !decl_in_symtab_p (decl: base2))
2110	return 0;
2111
2112	/* Don't cause symbols to be inserted by the act of checking. */
2113	symtab_node *node1 = symtab_node::get (decl: base1);
2114	if (!node1)
2115	return 0;
2116	symtab_node *node2 = symtab_node::get (decl: base2);
2117	if (!node2)
2118	return 0;
2119
2120	ret = node1->equal_address_to (s2: node2, memory_accessed: true);
2121	return ret;
2122	}
2123
2124	/* Compare SYMBOL_REFs X_BASE and Y_BASE.
2125
2126	- Return 1 if Y_BASE - X_BASE is constant, adding that constant
2127	to *DISTANCE if DISTANCE is nonnull.
2128
2129	- Return 0 if no accesses based on X_BASE can alias Y_BASE.
2130
2131	- Return -1 if one of the two results applies, but we can't tell
2132	which at compile time. Update DISTANCE in the same way as
2133	for a return value of 1, for the case in which that holds. */
2134
2135	static int
2136	compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2137	HOST_WIDE_INT *distance)
2138	{
2139	tree x_decl = SYMBOL_REF_DECL (x_base);
2140	tree y_decl = SYMBOL_REF_DECL (y_base);
2141	bool binds_def = true;
2142	bool swap = false;
2143
2144	if (XSTR (x_base, 0) == XSTR (y_base, 0))
2145	return 1;
2146	if (x_decl && y_decl)
2147	return compare_base_decls (base1: x_decl, base2: y_decl);
2148	if (x_decl || y_decl)
2149	{
2150	if (!x_decl)
2151	{
2152	swap = true;
2153	std::swap (a&: x_decl, b&: y_decl);
2154	std::swap (a&: x_base, b&: y_base);
2155	}
2156	/* We handle specially only section anchors. Other symbols are
2157	either equal (via aliasing) or refer to different objects. */
2158	if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2159	return -1;
2160	/* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2161	to ignore CONST_DECLs because they are readonly. */
2162	if (!VAR_P (x_decl)
2163	|| (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2164	return 0;
2165
2166	symtab_node *x_node = symtab_node::get_create (node: x_decl)
2167	->ultimate_alias_target ();
2168	/* External variable cannot be in section anchor. */
2169	if (!x_node->definition)
2170	return 0;
2171	x_base = XEXP (DECL_RTL (x_node->decl), 0);
2172	/* If not in anchor, we can disambiguate. */
2173	if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2174	return 0;
2175
2176	/* We have an alias of anchored variable. If it can be interposed;
2177	we must assume it may or may not alias its anchor. */
2178	binds_def = decl_binds_to_current_def_p (x_decl);
2179	}
2180	/* If we have variable in section anchor, we can compare by offset. */
2181	if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2182	&& SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2183	{
2184	if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2185	return 0;
2186	if (distance)
2187	*distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2188	- SYMBOL_REF_BLOCK_OFFSET (x_base));
2189	return binds_def ? 1 : -1;
2190	}
2191	/* Either the symbols are equal (via aliasing) or they refer to
2192	different objects. */
2193	return -1;
2194	}
2195
2196	/* Return false if the addresses X and Y are known to point to different
2197	objects, true if they might be pointers to the same object. */
2198
2199	static bool
2200	base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2201	machine_mode x_mode, machine_mode y_mode)
2202	{
2203	/* If the address itself has no known base see if a known equivalent
2204	value has one. If either address still has no known base, nothing
2205	is known about aliasing. */
2206	if (x_base == 0)
2207	{
2208	rtx x_c;
2209
2210	if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2211	return true;
2212
2213	x_base = find_base_term (x: x_c);
2214	if (x_base == 0)
2215	return true;
2216	}
2217
2218	if (y_base == 0)
2219	{
2220	rtx y_c;
2221	if (! flag_expensive_optimizations || (y_c = canon_rtx (x: y)) == y)
2222	return true;
2223
2224	y_base = find_base_term (x: y_c);
2225	if (y_base == 0)
2226	return true;
2227	}
2228
2229	/* If the base addresses are equal nothing is known about aliasing. */
2230	if (rtx_equal_p (x_base, y_base))
2231	return true;
2232
2233	/* The base addresses are different expressions. If they are not accessed
2234	via AND, there is no conflict. We can bring knowledge of object
2235	alignment into play here. For example, on alpha, "char a, b;" can
2236	alias one another, though "char a; long b;" cannot. AND addresses may
2237	implicitly alias surrounding objects; i.e. unaligned access in DImode
2238	via AND address can alias all surrounding object types except those
2239	with aligment 8 or higher. */
2240	if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2241	return true;
2242	if (GET_CODE (x) == AND
2243	&& (!CONST_INT_P (XEXP (x, 1))
2244	|| (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2245	return true;
2246	if (GET_CODE (y) == AND
2247	&& (!CONST_INT_P (XEXP (y, 1))
2248	|| (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2249	return true;
2250
2251	/* Differing symbols not accessed via AND never alias. */
2252	if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2253	return compare_base_symbol_refs (x_base, y_base) != 0;
2254
2255	if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2256	return false;
2257
2258	if (unique_base_value_p (x: x_base) || unique_base_value_p (x: y_base))
2259	return false;
2260
2261	return true;
2262	}
2263
2264	/* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2265	(or equal to) that of V. */
2266
2267	static bool
2268	refs_newer_value_p (const_rtx expr, rtx v)
2269	{
2270	int minuid = CSELIB_VAL_PTR (v)->uid;
2271	subrtx_iterator::array_type array;
2272	FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2273	if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid)
2274	return true;
2275	return false;
2276	}
2277
2278	/* Convert the address X into something we can use. This is done by returning
2279	it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2280	we call cselib to get a more useful rtx. */
2281
2282	rtx
2283	get_addr (rtx x)
2284	{
2285	cselib_val *v;
2286	struct elt_loc_list *l;
2287
2288	if (GET_CODE (x) != VALUE)
2289	{
2290	if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2291	&& GET_CODE (XEXP (x, 0)) == VALUE
2292	&& CONST_SCALAR_INT_P (XEXP (x, 1)))
2293	{
2294	rtx op0 = get_addr (XEXP (x, 0));
2295	if (op0 != XEXP (x, 0))
2296	{
2297	poly_int64 c;
2298	if (GET_CODE (x) == PLUS
2299	&& poly_int_rtx_p (XEXP (x, 1), res: &c))
2300	return plus_constant (GET_MODE (x), op0, c);
2301	return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2302	op0, XEXP (x, 1));
2303	}
2304	}
2305	return x;
2306	}
2307	v = CSELIB_VAL_PTR (x);
2308	if (v)
2309	{
2310	bool have_equivs = cselib_have_permanent_equivalences ();
2311	if (have_equivs)
2312	v = canonical_cselib_val (val: v);
2313	for (l = v->locs; l; l = l->next)
2314	if (CONSTANT_P (l->loc))
2315	return l->loc;
2316	for (l = v->locs; l; l = l->next)
2317	if (!REG_P (l->loc) && !MEM_P (l->loc)
2318	/* Avoid infinite recursion when potentially dealing with
2319	var-tracking artificial equivalences, by skipping the
2320	equivalences themselves, and not choosing expressions
2321	that refer to newer VALUEs. */
2322	&& (!have_equivs
2323	|| (GET_CODE (l->loc) != VALUE
2324	&& !refs_newer_value_p (expr: l->loc, v: x))))
2325	return l->loc;
2326	if (have_equivs)
2327	{
2328	for (l = v->locs; l; l = l->next)
2329	if (REG_P (l->loc)
2330	|| (GET_CODE (l->loc) != VALUE
2331	&& !refs_newer_value_p (expr: l->loc, v: x)))
2332	return l->loc;
2333	/* Return the canonical value. */
2334	return v->val_rtx;
2335	}
2336	if (v->locs)
2337	return v->locs->loc;
2338	}
2339	return x;
2340	}
2341
2342	/* Return the address of the (N_REFS + 1)th memory reference to ADDR
2343	where SIZE is the size in bytes of the memory reference. If ADDR
2344	is not modified by the memory reference then ADDR is returned. */
2345
2346	static rtx
2347	addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2348	{
2349	poly_int64 offset = 0;
2350
2351	switch (GET_CODE (addr))
2352	{
2353	case PRE_INC:
2354	offset = (n_refs + 1) * size;
2355	break;
2356	case PRE_DEC:
2357	offset = -(n_refs + 1) * size;
2358	break;
2359	case POST_INC:
2360	offset = n_refs * size;
2361	break;
2362	case POST_DEC:
2363	offset = -n_refs * size;
2364	break;
2365
2366	default:
2367	return addr;
2368	}
2369
2370	addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2371	addr = canon_rtx (x: addr);
2372
2373	return addr;
2374	}
2375
2376	/* Return TRUE if an object X sized at XSIZE bytes and another object
2377	Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2378	any of the sizes is zero, assume an overlap, otherwise use the
2379	absolute value of the sizes as the actual sizes. */
2380
2381	static inline bool
2382	offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2383	{
2384	if (known_eq (xsize, 0) || known_eq (ysize, 0))
2385	return true;
2386
2387	if (maybe_ge (c, 0))
2388	return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2389	else
2390	return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2391	}
2392
2393	/* Return one if X and Y (memory addresses) reference the
2394	same location in memory or if the references overlap.
2395	Return zero if they do not overlap, else return
2396	minus one in which case they still might reference the same location.
2397
2398	C is an offset accumulator. When
2399	C is nonzero, we are testing aliases between X and Y + C.
2400	XSIZE is the size in bytes of the X reference,
2401	similarly YSIZE is the size in bytes for Y.
2402	Expect that canon_rtx has been already called for X and Y.
2403
2404	If XSIZE or YSIZE is zero, we do not know the amount of memory being
2405	referenced (the reference was BLKmode), so make the most pessimistic
2406	assumptions.
2407
2408	If XSIZE or YSIZE is negative, we may access memory outside the object
2409	being referenced as a side effect. This can happen when using AND to
2410	align memory references, as is done on the Alpha.
2411
2412	Nice to notice that varying addresses cannot conflict with fp if no
2413	local variables had their addresses taken, but that's too hard now.
2414
2415	??? Contrary to the tree alias oracle this does not return
2416	one for X + non-constant and Y + non-constant when X and Y are equal.
2417	If that is fixed the TBAA hack for union type-punning can be removed. */
2418
2419	static int
2420	memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2421	poly_int64 c)
2422	{
2423	if (GET_CODE (x) == VALUE)
2424	{
2425	if (REG_P (y))
2426	{
2427	struct elt_loc_list *l = NULL;
2428	if (CSELIB_VAL_PTR (x))
2429	for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2430	l; l = l->next)
2431	if (REG_P (l->loc) && rtx_equal_for_memref_p (x: l->loc, y))
2432	break;
2433	if (l)
2434	x = y;
2435	else
2436	x = get_addr (x);
2437	}
2438	/* Don't call get_addr if y is the same VALUE. */
2439	else if (x != y)
2440	x = get_addr (x);
2441	}
2442	if (GET_CODE (y) == VALUE)
2443	{
2444	if (REG_P (x))
2445	{
2446	struct elt_loc_list *l = NULL;
2447	if (CSELIB_VAL_PTR (y))
2448	for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2449	l; l = l->next)
2450	if (REG_P (l->loc) && rtx_equal_for_memref_p (x: l->loc, y: x))
2451	break;
2452	if (l)
2453	y = x;
2454	else
2455	y = get_addr (x: y);
2456	}
2457	/* Don't call get_addr if x is the same VALUE. */
2458	else if (y != x)
2459	y = get_addr (x: y);
2460	}
2461	if (GET_CODE (x) == HIGH)
2462	x = XEXP (x, 0);
2463	else if (GET_CODE (x) == LO_SUM)
2464	x = XEXP (x, 1);
2465	else
2466	x = addr_side_effect_eval (addr: x, size: maybe_lt (a: xsize, b: 0) ? -xsize : xsize, n_refs: 0);
2467	if (GET_CODE (y) == HIGH)
2468	y = XEXP (y, 0);
2469	else if (GET_CODE (y) == LO_SUM)
2470	y = XEXP (y, 1);
2471	else
2472	y = addr_side_effect_eval (addr: y, size: maybe_lt (a: ysize, b: 0) ? -ysize : ysize, n_refs: 0);
2473
2474	if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2475	{
2476	HOST_WIDE_INT distance = 0;
2477	int cmp = compare_base_symbol_refs (x_base: x, y_base: y, distance: &distance);
2478
2479	/* If both decls are the same, decide by offsets. */
2480	if (cmp == 1)
2481	return offset_overlap_p (c: c + distance, xsize, ysize);
2482	/* Assume a potential overlap for symbolic addresses that went
2483	through alignment adjustments (i.e., that have negative
2484	sizes), because we can't know how far they are from each
2485	other. */
2486	if (maybe_lt (a: xsize, b: 0) || maybe_lt (a: ysize, b: 0))
2487	return -1;
2488	/* If decls are different or we know by offsets that there is no overlap,
2489	we win. */
2490	if (!cmp || !offset_overlap_p (c: c + distance, xsize, ysize))
2491	return 0;
2492	/* Decls may or may not be different and offsets overlap....*/
2493	return -1;
2494	}
2495	else if (rtx_equal_for_memref_p (x, y))
2496	{
2497	return offset_overlap_p (c, xsize, ysize);
2498	}
2499
2500	/* This code used to check for conflicts involving stack references and
2501	globals but the base address alias code now handles these cases. */
2502
2503	if (GET_CODE (x) == PLUS)
2504	{
2505	/* The fact that X is canonicalized means that this
2506	PLUS rtx is canonicalized. */
2507	rtx x0 = XEXP (x, 0);
2508	rtx x1 = XEXP (x, 1);
2509
2510	/* However, VALUEs might end up in different positions even in
2511	canonical PLUSes. Comparing their addresses is enough. */
2512	if (x0 == y)
2513	return memrefs_conflict_p (xsize, x: x1, ysize, const0_rtx, c);
2514	else if (x1 == y)
2515	return memrefs_conflict_p (xsize, x: x0, ysize, const0_rtx, c);
2516
2517	poly_int64 cx1, cy1;
2518	if (GET_CODE (y) == PLUS)
2519	{
2520	/* The fact that Y is canonicalized means that this
2521	PLUS rtx is canonicalized. */
2522	rtx y0 = XEXP (y, 0);
2523	rtx y1 = XEXP (y, 1);
2524
2525	if (x0 == y1)
2526	return memrefs_conflict_p (xsize, x: x1, ysize, y: y0, c);
2527	if (x1 == y0)
2528	return memrefs_conflict_p (xsize, x: x0, ysize, y: y1, c);
2529
2530	if (rtx_equal_for_memref_p (x: x1, y: y1))
2531	return memrefs_conflict_p (xsize, x: x0, ysize, y: y0, c);
2532	if (rtx_equal_for_memref_p (x: x0, y: y0))
2533	return memrefs_conflict_p (xsize, x: x1, ysize, y: y1, c);
2534	if (poly_int_rtx_p (x: x1, res: &cx1))
2535	{
2536	if (poly_int_rtx_p (x: y1, res: &cy1))
2537	return memrefs_conflict_p (xsize, x: x0, ysize, y: y0,
2538	c: c - cx1 + cy1);
2539	else
2540	return memrefs_conflict_p (xsize, x: x0, ysize, y, c: c - cx1);
2541	}
2542	else if (poly_int_rtx_p (x: y1, res: &cy1))
2543	return memrefs_conflict_p (xsize, x, ysize, y: y0, c: c + cy1);
2544
2545	return -1;
2546	}
2547	else if (poly_int_rtx_p (x: x1, res: &cx1))
2548	return memrefs_conflict_p (xsize, x: x0, ysize, y, c: c - cx1);
2549	}
2550	else if (GET_CODE (y) == PLUS)
2551	{
2552	/* The fact that Y is canonicalized means that this
2553	PLUS rtx is canonicalized. */
2554	rtx y0 = XEXP (y, 0);
2555	rtx y1 = XEXP (y, 1);
2556
2557	if (x == y0)
2558	return memrefs_conflict_p (xsize, const0_rtx, ysize, y: y1, c);
2559	if (x == y1)
2560	return memrefs_conflict_p (xsize, const0_rtx, ysize, y: y0, c);
2561
2562	poly_int64 cy1;
2563	if (poly_int_rtx_p (x: y1, res: &cy1))
2564	return memrefs_conflict_p (xsize, x, ysize, y: y0, c: c + cy1);
2565	else
2566	return -1;
2567	}
2568
2569	if (GET_CODE (x) == GET_CODE (y))
2570	switch (GET_CODE (x))
2571	{
2572	case MULT:
2573	{
2574	/* Handle cases where we expect the second operands to be the
2575	same, and check only whether the first operand would conflict
2576	or not. */
2577	rtx x0, y0;
2578	rtx x1 = canon_rtx (XEXP (x, 1));
2579	rtx y1 = canon_rtx (XEXP (y, 1));
2580	if (! rtx_equal_for_memref_p (x: x1, y: y1))
2581	return -1;
2582	x0 = canon_rtx (XEXP (x, 0));
2583	y0 = canon_rtx (XEXP (y, 0));
2584	if (rtx_equal_for_memref_p (x: x0, y: y0))
2585	return offset_overlap_p (c, xsize, ysize);
2586
2587	/* Can't properly adjust our sizes. */
2588	poly_int64 c1;
2589	if (!poly_int_rtx_p (x: x1, res: &c1)
2590	|| !can_div_trunc_p (a: xsize, b: c1, quotient: &xsize)
2591	|| !can_div_trunc_p (a: ysize, b: c1, quotient: &ysize)
2592	|| !can_div_trunc_p (a: c, b: c1, quotient: &c))
2593	return -1;
2594	return memrefs_conflict_p (xsize, x: x0, ysize, y: y0, c);
2595	}
2596
2597	default:
2598	break;
2599	}
2600
2601	/* Deal with alignment ANDs by adjusting offset and size so as to
2602	cover the maximum range, without taking any previously known
2603	alignment into account. Make a size negative after such an
2604	adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2605	assume a potential overlap, because they may end up in contiguous
2606	memory locations and the stricter-alignment access may span over
2607	part of both. */
2608	if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2609	{
2610	HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2611	unsigned HOST_WIDE_INT uc = sc;
2612	if (sc < 0 && pow2_or_zerop (x: -uc))
2613	{
2614	if (maybe_gt (xsize, 0))
2615	xsize = -xsize;
2616	if (maybe_ne (a: xsize, b: 0))
2617	xsize += sc + 1;
2618	c -= sc + 1;
2619	return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2620	ysize, y, c);
2621	}
2622	}
2623	if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2624	{
2625	HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2626	unsigned HOST_WIDE_INT uc = sc;
2627	if (sc < 0 && pow2_or_zerop (x: -uc))
2628	{
2629	if (maybe_gt (ysize, 0))
2630	ysize = -ysize;
2631	if (maybe_ne (a: ysize, b: 0))
2632	ysize += sc + 1;
2633	c += sc + 1;
2634	return memrefs_conflict_p (xsize, x,
2635	ysize, y: canon_rtx (XEXP (y, 0)), c);
2636	}
2637	}
2638
2639	if (CONSTANT_P (x))
2640	{
2641	poly_int64 cx, cy;
2642	if (poly_int_rtx_p (x, res: &cx) && poly_int_rtx_p (x: y, res: &cy))
2643	{
2644	c += cy - cx;
2645	return offset_overlap_p (c, xsize, ysize);
2646	}
2647
2648	if (GET_CODE (x) == CONST)
2649	{
2650	if (GET_CODE (y) == CONST)
2651	return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2652	ysize, y: canon_rtx (XEXP (y, 0)), c);
2653	else
2654	return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2655	ysize, y, c);
2656	}
2657	if (GET_CODE (y) == CONST)
2658	return memrefs_conflict_p (xsize, x, ysize,
2659	y: canon_rtx (XEXP (y, 0)), c);
2660
2661	/* Assume a potential overlap for symbolic addresses that went
2662	through alignment adjustments (i.e., that have negative
2663	sizes), because we can't know how far they are from each
2664	other. */
2665	if (CONSTANT_P (y))
2666	return (maybe_lt (a: xsize, b: 0)
2667	|| maybe_lt (a: ysize, b: 0)
2668	|| offset_overlap_p (c, xsize, ysize));
2669
2670	return -1;
2671	}
2672
2673	return -1;
2674	}
2675
2676	/* Functions to compute memory dependencies.
2677
2678	Since we process the insns in execution order, we can build tables
2679	to keep track of what registers are fixed (and not aliased), what registers
2680	are varying in known ways, and what registers are varying in unknown
2681	ways.
2682
2683	If both memory references are volatile, then there must always be a
2684	dependence between the two references, since their order cannot be
2685	changed. A volatile and non-volatile reference can be interchanged
2686	though.
2687
2688	We also must allow AND addresses, because they may generate accesses
2689	outside the object being referenced. This is used to generate aligned
2690	addresses from unaligned addresses, for instance, the alpha
2691	storeqi_unaligned pattern. */
2692
2693	/* Read dependence: X is read after read in MEM takes place. There can
2694	only be a dependence here if both reads are volatile, or if either is
2695	an explicit barrier. */
2696
2697	bool
2698	read_dependence (const_rtx mem, const_rtx x)
2699	{
2700	if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2701	return true;
2702	if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2703	|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2704	return true;
2705	return false;
2706	}
2707
2708	/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2709
2710	static tree
2711	decl_for_component_ref (tree x)
2712	{
2713	do
2714	{
2715	x = TREE_OPERAND (x, 0);
2716	}
2717	while (x && TREE_CODE (x) == COMPONENT_REF);
2718
2719	return x && DECL_P (x) ? x : NULL_TREE;
2720	}
2721
2722	/* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2723	for the offset of the field reference. *KNOWN_P says whether the
2724	offset is known. */
2725
2726	static void
2727	adjust_offset_for_component_ref (tree x, bool *known_p,
2728	poly_int64 *offset)
2729	{
2730	if (!*known_p)
2731	return;
2732	do
2733	{
2734	tree xoffset = component_ref_field_offset (x);
2735	tree field = TREE_OPERAND (x, 1);
2736	if (!poly_int_tree_p (t: xoffset))
2737	{
2738	*known_p = false;
2739	return;
2740	}
2741
2742	poly_offset_int woffset
2743	= (wi::to_poly_offset (t: xoffset)
2744	+ (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2745	>> LOG2_BITS_PER_UNIT)
2746	+ *offset);
2747	if (!woffset.to_shwi (r: offset))
2748	{
2749	*known_p = false;
2750	return;
2751	}
2752
2753	x = TREE_OPERAND (x, 0);
2754	}
2755	while (x && TREE_CODE (x) == COMPONENT_REF);
2756	}
2757
2758	/* Return true if we can determine the exprs corresponding to memrefs
2759	X and Y and they do not overlap.
2760	If LOOP_VARIANT is set, skip offset-based disambiguation */
2761
2762	bool
2763	nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2764	{
2765	tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2766	rtx rtlx, rtly;
2767	rtx basex, basey;
2768	bool moffsetx_known_p, moffsety_known_p;
2769	poly_int64 moffsetx = 0, moffsety = 0;
2770	poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2771
2772	/* Unless both have exprs, we can't tell anything. */
2773	if (exprx == 0 || expry == 0)
2774	return false;
2775
2776	/* For spill-slot accesses make sure we have valid offsets. */
2777	if ((exprx == get_spill_slot_decl (false)
2778	&& ! MEM_OFFSET_KNOWN_P (x))
2779	|| (expry == get_spill_slot_decl (false)
2780	&& ! MEM_OFFSET_KNOWN_P (y)))
2781	return false;
2782
2783	/* If the field reference test failed, look at the DECLs involved. */
2784	moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2785	if (moffsetx_known_p)
2786	moffsetx = MEM_OFFSET (x);
2787	if (TREE_CODE (exprx) == COMPONENT_REF)
2788	{
2789	tree t = decl_for_component_ref (x: exprx);
2790	if (! t)
2791	return false;
2792	adjust_offset_for_component_ref (x: exprx, known_p: &moffsetx_known_p, offset: &moffsetx);
2793	exprx = t;
2794	}
2795
2796	moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2797	if (moffsety_known_p)
2798	moffsety = MEM_OFFSET (y);
2799	if (TREE_CODE (expry) == COMPONENT_REF)
2800	{
2801	tree t = decl_for_component_ref (x: expry);
2802	if (! t)
2803	return false;
2804	adjust_offset_for_component_ref (x: expry, known_p: &moffsety_known_p, offset: &moffsety);
2805	expry = t;
2806	}
2807
2808	if (! DECL_P (exprx) || ! DECL_P (expry))
2809	return false;
2810
2811	/* If we refer to different gimple registers, or one gimple register
2812	and one non-gimple-register, we know they can't overlap. First,
2813	gimple registers don't have their addresses taken. Now, there
2814	could be more than one stack slot for (different versions of) the
2815	same gimple register, but we can presumably tell they don't
2816	overlap based on offsets from stack base addresses elsewhere.
2817	It's important that we don't proceed to DECL_RTL, because gimple
2818	registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2819	able to do anything about them since no SSA information will have
2820	remained to guide it. */
2821	if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2822	return exprx != expry
2823	|| (moffsetx_known_p && moffsety_known_p
2824	&& MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2825	&& !offset_overlap_p (c: moffsety - moffsetx,
2826	MEM_SIZE (x), MEM_SIZE (y)));
2827
2828	/* With invalid code we can end up storing into the constant pool.
2829	Bail out to avoid ICEing when creating RTL for this.
2830	See gfortran.dg/lto/20091028-2_0.f90. */
2831	if (TREE_CODE (exprx) == CONST_DECL
2832	|| TREE_CODE (expry) == CONST_DECL)
2833	return true;
2834
2835	/* If one decl is known to be a function or label in a function and
2836	the other is some kind of data, they can't overlap. */
2837	if ((TREE_CODE (exprx) == FUNCTION_DECL
2838	|| TREE_CODE (exprx) == LABEL_DECL)
2839	!= (TREE_CODE (expry) == FUNCTION_DECL
2840	|| TREE_CODE (expry) == LABEL_DECL))
2841	return true;
2842
2843	/* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2844	living in multiple places), we can't tell anything. Exception
2845	are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2846	if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2847	|| (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2848	return false;
2849
2850	rtlx = DECL_RTL (exprx);
2851	rtly = DECL_RTL (expry);
2852
2853	/* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2854	can't overlap unless they are the same because we never reuse that part
2855	of the stack frame used for locals for spilled pseudos. */
2856	if ((!MEM_P (rtlx) || !MEM_P (rtly))
2857	&& ! rtx_equal_p (rtlx, rtly))
2858	return true;
2859
2860	/* If we have MEMs referring to different address spaces (which can
2861	potentially overlap), we cannot easily tell from the addresses
2862	whether the references overlap. */
2863	if (MEM_P (rtlx) && MEM_P (rtly)
2864	&& MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2865	return false;
2866
2867	/* Get the base and offsets of both decls. If either is a register, we
2868	know both are and are the same, so use that as the base. The only
2869	we can avoid overlap is if we can deduce that they are nonoverlapping
2870	pieces of that decl, which is very rare. */
2871	basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2872	basex = strip_offset_and_add (x: basex, offset: &offsetx);
2873
2874	basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2875	basey = strip_offset_and_add (x: basey, offset: &offsety);
2876
2877	/* If the bases are different, we know they do not overlap if both
2878	are constants or if one is a constant and the other a pointer into the
2879	stack frame. Otherwise a different base means we can't tell if they
2880	overlap or not. */
2881	if (compare_base_decls (base1: exprx, base2: expry) == 0)
2882	return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2883	|| (CONSTANT_P (basex) && REG_P (basey)
2884	&& REGNO_PTR_FRAME_P (REGNO (basey)))
2885	|| (CONSTANT_P (basey) && REG_P (basex)
2886	&& REGNO_PTR_FRAME_P (REGNO (basex))));
2887
2888	/* Offset based disambiguation not appropriate for loop invariant */
2889	if (loop_invariant)
2890	return false;
2891
2892	/* Offset based disambiguation is OK even if we do not know that the
2893	declarations are necessarily different
2894	(i.e. compare_base_decls (exprx, expry) == -1) */
2895
2896	sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2897	: MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2898	: -1);
2899	sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2900	: MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2901	: -1);
2902
2903	/* If we have an offset for either memref, it can update the values computed
2904	above. */
2905	if (moffsetx_known_p)
2906	offsetx += moffsetx, sizex -= moffsetx;
2907	if (moffsety_known_p)
2908	offsety += moffsety, sizey -= moffsety;
2909
2910	/* If a memref has both a size and an offset, we can use the smaller size.
2911	We can't do this if the offset isn't known because we must view this
2912	memref as being anywhere inside the DECL's MEM. */
2913	if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2914	sizex = MEM_SIZE (x);
2915	if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2916	sizey = MEM_SIZE (y);
2917
2918	return !ranges_maybe_overlap_p (pos1: offsetx, size1: sizex, pos2: offsety, size2: sizey);
2919	}
2920
2921	/* Helper for true_dependence and canon_true_dependence.
2922	Checks for true dependence: X is read after store in MEM takes place.
2923
2924	If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2925	NULL_RTX, and the canonical addresses of MEM and X are both computed
2926	here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2927
2928	If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2929
2930	Returns true if there is a true dependence, false otherwise. */
2931
2932	static bool
2933	true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
2934	const_rtx x, rtx x_addr, bool mem_canonicalized)
2935	{
2936	rtx true_mem_addr;
2937	rtx base;
2938	int ret;
2939
2940	gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2941	: (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2942
2943	if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2944	return true;
2945
2946	/* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2947	This is used in epilogue deallocation functions, and in cselib. */
2948	if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2949	return true;
2950	if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2951	return true;
2952	if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2953	|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2954	return true;
2955
2956	if (! x_addr)
2957	x_addr = XEXP (x, 0);
2958	x_addr = get_addr (x: x_addr);
2959
2960	if (! mem_addr)
2961	{
2962	mem_addr = XEXP (mem, 0);
2963	if (mem_mode == VOIDmode)
2964	mem_mode = GET_MODE (mem);
2965	}
2966	true_mem_addr = get_addr (x: mem_addr);
2967
2968	/* Read-only memory is by definition never modified, and therefore can't
2969	conflict with anything. However, don't assume anything when AND
2970	addresses are involved and leave to the code below to determine
2971	dependence. We don't expect to find read-only set on MEM, but
2972	stupid user tricks can produce them, so don't die. */
2973	if (MEM_READONLY_P (x)
2974	&& GET_CODE (x_addr) != AND
2975	&& GET_CODE (true_mem_addr) != AND)
2976	return false;
2977
2978	/* If we have MEMs referring to different address spaces (which can
2979	potentially overlap), we cannot easily tell from the addresses
2980	whether the references overlap. */
2981	if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2982	return true;
2983
2984	base = find_base_term (x: x_addr);
2985	if (base && (GET_CODE (base) == LABEL_REF
2986	|| (GET_CODE (base) == SYMBOL_REF
2987	&& CONSTANT_POOL_ADDRESS_P (base))))
2988	return false;
2989
2990	rtx mem_base = find_base_term (x: true_mem_addr);
2991	if (! base_alias_check (x: x_addr, x_base: base, y: true_mem_addr, y_base: mem_base,
2992	GET_MODE (x), y_mode: mem_mode))
2993	return false;
2994
2995	x_addr = canon_rtx (x: x_addr);
2996	if (!mem_canonicalized)
2997	mem_addr = canon_rtx (x: true_mem_addr);
2998
2999	if ((ret = memrefs_conflict_p (xsize: GET_MODE_SIZE (mode: mem_mode), x: mem_addr,
3000	SIZE_FOR_MODE (x), y: x_addr, c: 0)) != -1)
3001	return !!ret;
3002
3003	if (mems_in_disjoint_alias_sets_p (mem1: x, mem2: mem))
3004	return false;
3005
3006	if (nonoverlapping_memrefs_p (x: mem, y: x, loop_invariant: false))
3007	return false;
3008
3009	return rtx_refs_may_alias_p (x, mem, tbaa_p: true);
3010	}
3011
3012	/* True dependence: X is read after store in MEM takes place. */
3013
3014	bool
3015	true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3016	{
3017	return true_dependence_1 (mem, mem_mode, NULL_RTX,
3018	x, NULL_RTX, /*mem_canonicalized=*/false);
3019	}
3020
3021	/* Canonical true dependence: X is read after store in MEM takes place.
3022	Variant of true_dependence which assumes MEM has already been
3023	canonicalized (hence we no longer do that here).
3024	The mem_addr argument has been added, since true_dependence_1 computed
3025	this value prior to canonicalizing. */
3026
3027	bool
3028	canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3029	const_rtx x, rtx x_addr)
3030	{
3031	return true_dependence_1 (mem, mem_mode, mem_addr,
3032	x, x_addr, /*mem_canonicalized=*/true);
3033	}
3034
3035	/* Returns true if a write to X might alias a previous read from
3036	(or, if WRITEP is true, a write to) MEM.
3037	If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3038	and X_MODE the mode for that access.
3039	If MEM_CANONICALIZED is true, MEM is canonicalized. */
3040
3041	static bool
3042	write_dependence_p (const_rtx mem,
3043	const_rtx x, machine_mode x_mode, rtx x_addr,
3044	bool mem_canonicalized, bool x_canonicalized, bool writep)
3045	{
3046	rtx mem_addr;
3047	rtx true_mem_addr, true_x_addr;
3048	rtx base;
3049	int ret;
3050
3051	gcc_checking_assert (x_canonicalized
3052	? (x_addr != NULL_RTX
3053	&& (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3054	: (x_addr == NULL_RTX && x_mode == VOIDmode));
3055
3056	if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3057	return true;
3058
3059	/* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3060	This is used in epilogue deallocation functions. */
3061	if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3062	return true;
3063	if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3064	return true;
3065	if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3066	|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3067	return true;
3068
3069	if (!x_addr)
3070	x_addr = XEXP (x, 0);
3071	true_x_addr = get_addr (x: x_addr);
3072
3073	mem_addr = XEXP (mem, 0);
3074	true_mem_addr = get_addr (x: mem_addr);
3075
3076	/* A read from read-only memory can't conflict with read-write memory.
3077	Don't assume anything when AND addresses are involved and leave to
3078	the code below to determine dependence. */
3079	if (!writep
3080	&& MEM_READONLY_P (mem)
3081	&& GET_CODE (true_x_addr) != AND
3082	&& GET_CODE (true_mem_addr) != AND)
3083	return false;
3084
3085	/* If we have MEMs referring to different address spaces (which can
3086	potentially overlap), we cannot easily tell from the addresses
3087	whether the references overlap. */
3088	if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3089	return true;
3090
3091	base = find_base_term (x: true_mem_addr);
3092	if (! writep
3093	&& base
3094	&& (GET_CODE (base) == LABEL_REF
3095	|| (GET_CODE (base) == SYMBOL_REF
3096	&& CONSTANT_POOL_ADDRESS_P (base))))
3097	return false;
3098
3099	rtx x_base = find_base_term (x: true_x_addr);
3100	if (! base_alias_check (x: true_x_addr, x_base, y: true_mem_addr, y_base: base,
3101	GET_MODE (x), GET_MODE (mem)))
3102	return false;
3103
3104	if (!x_canonicalized)
3105	{
3106	x_addr = canon_rtx (x: true_x_addr);
3107	x_mode = GET_MODE (x);
3108	}
3109	if (!mem_canonicalized)
3110	mem_addr = canon_rtx (x: true_mem_addr);
3111
3112	if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), x: mem_addr,
3113	ysize: GET_MODE_SIZE (mode: x_mode), y: x_addr, c: 0)) != -1)
3114	return !!ret;
3115
3116	if (nonoverlapping_memrefs_p (x, y: mem, loop_invariant: false))
3117	return false;
3118
3119	return rtx_refs_may_alias_p (x, mem, tbaa_p: false);
3120	}
3121
3122	/* Anti dependence: X is written after read in MEM takes place. */
3123
3124	bool
3125	anti_dependence (const_rtx mem, const_rtx x)
3126	{
3127	return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3128	/*mem_canonicalized=*/false,
3129	/*x_canonicalized*/false, /*writep=*/false);
3130	}
3131
3132	/* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3133	Also, consider X in X_MODE (which might be from an enclosing
3134	STRICT_LOW_PART / ZERO_EXTRACT).
3135	If MEM_CANONICALIZED is true, MEM is canonicalized. */
3136
3137	bool
3138	canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3139	const_rtx x, machine_mode x_mode, rtx x_addr)
3140	{
3141	return write_dependence_p (mem, x, x_mode, x_addr,
3142	mem_canonicalized, /*x_canonicalized=*/true,
3143	/*writep=*/false);
3144	}
3145
3146	/* Output dependence: X is written after store in MEM takes place. */
3147
3148	bool
3149	output_dependence (const_rtx mem, const_rtx x)
3150	{
3151	return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3152	/*mem_canonicalized=*/false,
3153	/*x_canonicalized*/false, /*writep=*/true);
3154	}
3155
3156	/* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3157	Also, consider X in X_MODE (which might be from an enclosing
3158	STRICT_LOW_PART / ZERO_EXTRACT).
3159	If MEM_CANONICALIZED is true, MEM is canonicalized. */
3160
3161	bool
3162	canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3163	const_rtx x, machine_mode x_mode, rtx x_addr)
3164	{
3165	return write_dependence_p (mem, x, x_mode, x_addr,
3166	mem_canonicalized, /*x_canonicalized=*/true,
3167	/*writep=*/true);
3168	}
3169
3170
3171
3172	/* Check whether X may be aliased with MEM. Don't do offset-based
3173	memory disambiguation & TBAA. */
3174	bool
3175	may_alias_p (const_rtx mem, const_rtx x)
3176	{
3177	rtx x_addr, mem_addr;
3178
3179	if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3180	return true;
3181
3182	/* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3183	This is used in epilogue deallocation functions. */
3184	if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3185	return true;
3186	if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3187	return true;
3188	if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3189	|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3190	return true;
3191
3192	x_addr = XEXP (x, 0);
3193	x_addr = get_addr (x: x_addr);
3194
3195	mem_addr = XEXP (mem, 0);
3196	mem_addr = get_addr (x: mem_addr);
3197
3198	/* Read-only memory is by definition never modified, and therefore can't
3199	conflict with anything. However, don't assume anything when AND
3200	addresses are involved and leave to the code below to determine
3201	dependence. We don't expect to find read-only set on MEM, but
3202	stupid user tricks can produce them, so don't die. */
3203	if (MEM_READONLY_P (x)
3204	&& GET_CODE (x_addr) != AND
3205	&& GET_CODE (mem_addr) != AND)
3206	return false;
3207
3208	/* If we have MEMs referring to different address spaces (which can
3209	potentially overlap), we cannot easily tell from the addresses
3210	whether the references overlap. */
3211	if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3212	return true;
3213
3214	rtx x_base = find_base_term (x: x_addr);
3215	rtx mem_base = find_base_term (x: mem_addr);
3216	if (! base_alias_check (x: x_addr, x_base, y: mem_addr, y_base: mem_base,
3217	GET_MODE (x), GET_MODE (mem_addr)))
3218	return false;
3219
3220	if (nonoverlapping_memrefs_p (x: mem, y: x, loop_invariant: true))
3221	return false;
3222
3223	/* TBAA not valid for loop_invarint */
3224	return rtx_refs_may_alias_p (x, mem, tbaa_p: false);
3225	}
3226
3227	void
3228	init_alias_target (void)
3229	{
3230	int i;
3231
3232	if (!arg_base_value)
3233	arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3234
3235	memset (static_reg_base_value, c: 0, n: sizeof static_reg_base_value);
3236
3237	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3238	/* Check whether this register can hold an incoming pointer
3239	argument. FUNCTION_ARG_REGNO_P tests outgoing register
3240	numbers, so translate if necessary due to register windows. */
3241	if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3242	&& targetm.hard_regno_mode_ok (i, Pmode))
3243	static_reg_base_value[i] = arg_base_value;
3244
3245	/* RTL code is required to be consistent about whether it uses the
3246	stack pointer, the frame pointer or the argument pointer to
3247	access a given area of the frame. We can therefore use the
3248	base address to distinguish between the different areas. */
3249	static_reg_base_value[STACK_POINTER_REGNUM]
3250	= unique_base_value (UNIQUE_BASE_VALUE_SP);
3251	static_reg_base_value[ARG_POINTER_REGNUM]
3252	= unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3253	static_reg_base_value[FRAME_POINTER_REGNUM]
3254	= unique_base_value (UNIQUE_BASE_VALUE_FP);
3255
3256	/* The above rules extend post-reload, with eliminations applying
3257	consistently to each of the three pointers. Cope with cases in
3258	which the frame pointer is eliminated to the hard frame pointer
3259	rather than the stack pointer. */
3260	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3261	static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3262	= unique_base_value (UNIQUE_BASE_VALUE_HFP);
3263	}
3264
3265	/* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3266	to be memory reference. */
3267	static bool memory_modified;
3268	static void
3269	memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3270	{
3271	if (MEM_P (x))
3272	{
3273	if (anti_dependence (mem: x, x: (const_rtx)data) || output_dependence (mem: x, x: (const_rtx)data))
3274	memory_modified = true;
3275	}
3276	}
3277
3278
3279	/* Return true when INSN possibly modify memory contents of MEM
3280	(i.e. address can be modified). */
3281	bool
3282	memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3283	{
3284	if (!INSN_P (insn))
3285	return false;
3286	/* Conservatively assume all non-readonly MEMs might be modified in
3287	calls. */
3288	if (CALL_P (insn))
3289	return true;
3290	memory_modified = false;
3291	note_stores (as_a<const rtx_insn *> (p: insn), memory_modified_1,
3292	CONST_CAST_RTX(mem));
3293	return memory_modified;
3294	}
3295
3296	/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3297	array. */
3298
3299	void
3300	init_alias_analysis (void)
3301	{
3302	const bool frame_pointer_eliminated
3303	= reload_completed
3304	&& !frame_pointer_needed
3305	&& targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3306	unsigned int maxreg = max_reg_num ();
3307	bool changed;
3308	int pass, i;
3309	unsigned int ui;
3310	rtx_insn *insn;
3311	rtx val;
3312	int rpo_cnt;
3313	int *rpo;
3314
3315	timevar_push (tv: TV_ALIAS_ANALYSIS);
3316
3317	vec_safe_grow_cleared (v&: reg_known_value, len: maxreg - FIRST_PSEUDO_REGISTER,
3318	exact: true);
3319	reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3320	bitmap_clear (reg_known_equiv_p);
3321
3322	/* If we have memory allocated from the previous run, use it. */
3323	if (old_reg_base_value)
3324	reg_base_value = old_reg_base_value;
3325
3326	if (reg_base_value)
3327	reg_base_value->truncate (size: 0);
3328
3329	vec_safe_grow_cleared (v&: reg_base_value, len: maxreg, exact: true);
3330
3331	new_reg_base_value = XNEWVEC (rtx, maxreg);
3332	reg_seen = sbitmap_alloc (maxreg);
3333
3334	/* The basic idea is that each pass through this loop will use the
3335	"constant" information from the previous pass to propagate alias
3336	information through another level of assignments.
3337
3338	The propagation is done on the CFG in reverse post-order, to propagate
3339	things forward as far as possible in each iteration.
3340
3341	This could get expensive if the assignment chains are long. Maybe
3342	we should throttle the number of iterations, possibly based on
3343	the optimization level or flag_expensive_optimizations.
3344
3345	We could propagate more information in the first pass by making use
3346	of DF_REG_DEF_COUNT to determine immediately that the alias information
3347	for a pseudo is "constant".
3348
3349	A program with an uninitialized variable can cause an infinite loop
3350	here. Instead of doing a full dataflow analysis to detect such problems
3351	we just cap the number of iterations for the loop.
3352
3353	The state of the arrays for the set chain in question does not matter
3354	since the program has undefined behavior. */
3355
3356	rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3357	rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3358
3359	pass = 0;
3360	do
3361	{
3362	/* Assume nothing will change this iteration of the loop. */
3363	changed = false;
3364
3365	/* We want to assign the same IDs each iteration of this loop, so
3366	start counting from one each iteration of the loop. */
3367	unique_id = 1;
3368
3369	/* We're at the start of the function each iteration through the
3370	loop, so we're copying arguments. */
3371	copying_arguments = true;
3372
3373	/* Wipe the potential alias information clean for this pass. */
3374	memset (s: new_reg_base_value, c: 0, n: maxreg * sizeof (rtx));
3375
3376	/* Wipe the reg_seen array clean. */
3377	bitmap_clear (reg_seen);
3378
3379	/* Initialize the alias information for this pass. */
3380	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3381	if (static_reg_base_value[i]
3382	/* Don't treat the hard frame pointer as special if we
3383	eliminated the frame pointer to the stack pointer. */
3384	&& !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3385	{
3386	new_reg_base_value[i] = static_reg_base_value[i];
3387	bitmap_set_bit (map: reg_seen, bitno: i);
3388	}
3389
3390	/* Walk the insns adding values to the new_reg_base_value array. */
3391	for (i = 0; i < rpo_cnt; i++)
3392	{
3393	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3394	FOR_BB_INSNS (bb, insn)
3395	{
3396	if (NONDEBUG_INSN_P (insn))
3397	{
3398	rtx note, set;
3399
3400	/* Treat the hard frame pointer as special unless we
3401	eliminated the frame pointer to the stack pointer. */
3402	if (!frame_pointer_eliminated
3403	&& modified_in_p (hard_frame_pointer_rtx, insn))
3404	continue;
3405
3406	/* If this insn has a noalias note, process it, Otherwise,
3407	scan for sets. A simple set will have no side effects
3408	which could change the base value of any other register. */
3409	if (GET_CODE (PATTERN (insn)) == SET
3410	&& REG_NOTES (insn) != 0
3411	&& find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3412	record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3413	else
3414	note_stores (insn, record_set, NULL);
3415
3416	set = single_set (insn);
3417
3418	if (set != 0
3419	&& REG_P (SET_DEST (set))
3420	&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3421	{
3422	unsigned int regno = REGNO (SET_DEST (set));
3423	rtx src = SET_SRC (set);
3424	rtx t;
3425
3426	note = find_reg_equal_equiv_note (insn);
3427	if (note && REG_NOTE_KIND (note) == REG_EQUAL
3428	&& DF_REG_DEF_COUNT (regno) != 1)
3429	note = NULL_RTX;
3430
3431	poly_int64 offset;
3432	if (note != NULL_RTX
3433	&& GET_CODE (XEXP (note, 0)) != EXPR_LIST
3434	&& ! rtx_varies_p (XEXP (note, 0), 1)
3435	&& ! reg_overlap_mentioned_p (SET_DEST (set),
3436	XEXP (note, 0)))
3437	{
3438	set_reg_known_value (regno, XEXP (note, 0));
3439	set_reg_known_equiv_p (regno,
3440	REG_NOTE_KIND (note) == REG_EQUIV);
3441	}
3442	else if (DF_REG_DEF_COUNT (regno) == 1
3443	&& GET_CODE (src) == PLUS
3444	&& REG_P (XEXP (src, 0))
3445	&& (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3446	&& poly_int_rtx_p (XEXP (src, 1), res: &offset))
3447	{
3448	t = plus_constant (GET_MODE (src), t, offset);
3449	set_reg_known_value (regno, val: t);
3450	set_reg_known_equiv_p (regno, val: false);
3451	}
3452	else if (DF_REG_DEF_COUNT (regno) == 1
3453	&& ! rtx_varies_p (src, 1))
3454	{
3455	set_reg_known_value (regno, val: src);
3456	set_reg_known_equiv_p (regno, val: false);
3457	}
3458	}
3459	}
3460	else if (NOTE_P (insn)
3461	&& NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3462	copying_arguments = false;
3463	}
3464	}
3465
3466	/* Now propagate values from new_reg_base_value to reg_base_value. */
3467	gcc_assert (maxreg == (unsigned int) max_reg_num ());
3468
3469	for (ui = 0; ui < maxreg; ui++)
3470	{
3471	if (new_reg_base_value[ui]
3472	&& new_reg_base_value[ui] != (*reg_base_value)[ui]
3473	&& ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3474	{
3475	(*reg_base_value)[ui] = new_reg_base_value[ui];
3476	changed = true;
3477	}
3478	}
3479	}
3480	while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3481	XDELETEVEC (rpo);
3482
3483	/* Fill in the remaining entries. */
3484	FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3485	{
3486	int regno = i + FIRST_PSEUDO_REGISTER;
3487	if (! val)
3488	set_reg_known_value (regno, val: regno_reg_rtx[regno]);
3489	}
3490
3491	/* Clean up. */
3492	free (ptr: new_reg_base_value);
3493	new_reg_base_value = 0;
3494	sbitmap_free (map: reg_seen);
3495	reg_seen = 0;
3496	timevar_pop (tv: TV_ALIAS_ANALYSIS);
3497	}
3498
3499	/* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3500	Special API for var-tracking pass purposes. */
3501
3502	void
3503	vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3504	{
3505	(*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3506	}
3507
3508	void
3509	end_alias_analysis (void)
3510	{
3511	old_reg_base_value = reg_base_value;
3512	vec_free (v&: reg_known_value);
3513	sbitmap_free (map: reg_known_equiv_p);
3514	}
3515
3516	void
3517	dump_alias_stats_in_alias_c (FILE *s)
3518	{
3519	fprintf (stream: s, format: " TBAA oracle: %llu disambiguations %llu queries\n"
3520	" %llu are in alias set 0\n"
3521	" %llu queries asked about the same object\n"
3522	" %llu queries asked about the same alias set\n"
3523	" %llu access volatile\n"
3524	" %llu are dependent in the DAG\n"
3525	" %llu are aritificially in conflict with void *\n",
3526	alias_stats.num_disambiguated,
3527	alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3528	+ alias_stats.num_same_objects + alias_stats.num_volatile
3529	+ alias_stats.num_dag + alias_stats.num_disambiguated
3530	+ alias_stats.num_universal,
3531	alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3532	alias_stats.num_same_objects, alias_stats.num_volatile,
3533	alias_stats.num_dag, alias_stats.num_universal);
3534	}
3535	#include "gt-alias.h"
3536