1/* Alias analysis for GNU C
2 Copyright (C) 1997-2023 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
124struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {};
125
126struct 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
151static 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
157static 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
213static GTY(()) vec<rtx, va_gc> *reg_base_value;
214static rtx *new_reg_base_value;
215
216/* The single VOIDmode ADDRESS that represents all argument bases.
217 It has id 0. */
218static GTY(()) rtx arg_base_value;
219
220/* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
221static 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. */
226static 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. */
245static 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. */
259static 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. */
263static bool copying_arguments;
264
265
266/* The splay-tree used to store the various alias set entries. */
267static 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
273static bool
274ao_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
344static bool
345rtx_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
362bool
363refs_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. */
380bool
381mems_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
396static inline alias_set_entry *
397get_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
405static inline bool
406mems_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
415bool
416alias_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
479bool
480alias_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
553bool
554alias_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
578bool
579objects_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
615bool
616ends_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
662tree
663component_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
686static bool
687ref_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
697static alias_set_type
698get_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
716alias_set_type
717get_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
742tree
743reference_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
809tree
810reference_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
834bool
835alias_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
858alias_set_entry *
859init_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
875alias_set_type
876get_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
1168alias_set_type
1169new_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
1190void
1191record_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
1250void
1251record_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
1342void
1343record_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
1353static GTY(()) alias_set_type varargs_set = -1;
1354
1355alias_set_type
1356get_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
1375static GTY(()) alias_set_type frame_set = -1;
1376
1377alias_set_type
1378get_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
1388static rtx
1389unique_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
1397static bool
1398unique_base_value_p (rtx x)
1399{
1400 return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1401}
1402
1403/* Return true if X is known to be a base value. */
1404
1405static bool
1406known_base_value_p (rtx x)
1407{
1408 switch (GET_CODE (x))
1409 {
1410 case LABEL_REF:
1411 case SYMBOL_REF:
1412 return true;
1413
1414 case ADDRESS:
1415 /* Arguments may or may not be bases; we don't know for sure. */
1416 return GET_MODE (x) != VOIDmode;
1417
1418 default:
1419 return false;
1420 }
1421}
1422
1423/* Inside SRC, the source of a SET, find a base address. */
1424
1425static rtx
1426find_base_value (rtx src)
1427{
1428 unsigned int regno;
1429 scalar_int_mode int_mode;
1430
1431#if defined (FIND_BASE_TERM)
1432 /* Try machine-dependent ways to find the base term. */
1433 src = FIND_BASE_TERM (src);
1434#endif
1435
1436 switch (GET_CODE (src))
1437 {
1438 case SYMBOL_REF:
1439 case LABEL_REF:
1440 return src;
1441
1442 case REG:
1443 regno = REGNO (src);
1444 /* At the start of a function, argument registers have known base
1445 values which may be lost later. Returning an ADDRESS
1446 expression here allows optimization based on argument values
1447 even when the argument registers are used for other purposes. */
1448 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1449 return new_reg_base_value[regno];
1450
1451 /* If a pseudo has a known base value, return it. Do not do this
1452 for non-fixed hard regs since it can result in a circular
1453 dependency chain for registers which have values at function entry.
1454
1455 The test above is not sufficient because the scheduler may move
1456 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1457 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1458 && regno < vec_safe_length (v: reg_base_value))
1459 {
1460 /* If we're inside init_alias_analysis, use new_reg_base_value
1461 to reduce the number of relaxation iterations. */
1462 if (new_reg_base_value && new_reg_base_value[regno]
1463 && DF_REG_DEF_COUNT (regno) == 1)
1464 return new_reg_base_value[regno];
1465
1466 if ((*reg_base_value)[regno])
1467 return (*reg_base_value)[regno];
1468 }
1469
1470 return 0;
1471
1472 case MEM:
1473 /* Check for an argument passed in memory. Only record in the
1474 copying-arguments block; it is too hard to track changes
1475 otherwise. */
1476 if (copying_arguments
1477 && (XEXP (src, 0) == arg_pointer_rtx
1478 || (GET_CODE (XEXP (src, 0)) == PLUS
1479 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1480 return arg_base_value;
1481 return 0;
1482
1483 case CONST:
1484 src = XEXP (src, 0);
1485 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1486 break;
1487
1488 /* fall through */
1489
1490 case PLUS:
1491 case MINUS:
1492 {
1493 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1494
1495 /* If either operand is a REG that is a known pointer, then it
1496 is the base. */
1497 if (REG_P (src_0) && REG_POINTER (src_0))
1498 return find_base_value (src: src_0);
1499 if (REG_P (src_1) && REG_POINTER (src_1))
1500 return find_base_value (src: src_1);
1501
1502 /* If either operand is a REG, then see if we already have
1503 a known value for it. */
1504 if (REG_P (src_0))
1505 {
1506 temp = find_base_value (src: src_0);
1507 if (temp != 0)
1508 src_0 = temp;
1509 }
1510
1511 if (REG_P (src_1))
1512 {
1513 temp = find_base_value (src: src_1);
1514 if (temp!= 0)
1515 src_1 = temp;
1516 }
1517
1518 /* If either base is named object or a special address
1519 (like an argument or stack reference), then use it for the
1520 base term. */
1521 if (src_0 != 0 && known_base_value_p (x: src_0))
1522 return src_0;
1523
1524 if (src_1 != 0 && known_base_value_p (x: src_1))
1525 return src_1;
1526
1527 /* Guess which operand is the base address:
1528 If either operand is a symbol, then it is the base. If
1529 either operand is a CONST_INT, then the other is the base. */
1530 if (CONST_INT_P (src_1) || CONSTANT_P (src_0))
1531 return find_base_value (src: src_0);
1532 else if (CONST_INT_P (src_0) || CONSTANT_P (src_1))
1533 return find_base_value (src: src_1);
1534
1535 return 0;
1536 }
1537
1538 case LO_SUM:
1539 /* The standard form is (lo_sum reg sym) so look only at the
1540 second operand. */
1541 return find_base_value (XEXP (src, 1));
1542
1543 case AND:
1544 /* Look through aligning ANDs. And AND with zero or one with
1545 the LSB set isn't one (see for example PR92462). */
1546 if (CONST_INT_P (XEXP (src, 1))
1547 && INTVAL (XEXP (src, 1)) != 0
1548 && (INTVAL (XEXP (src, 1)) & 1) == 0)
1549 return find_base_value (XEXP (src, 0));
1550 return 0;
1551
1552 case TRUNCATE:
1553 /* As we do not know which address space the pointer is referring to, we can
1554 handle this only if the target does not support different pointer or
1555 address modes depending on the address space. */
1556 if (!target_default_pointer_address_modes_p ())
1557 break;
1558 if (!is_a <scalar_int_mode> (GET_MODE (src), result: &int_mode)
1559 || GET_MODE_PRECISION (mode: int_mode) < GET_MODE_PRECISION (Pmode))
1560 break;
1561 /* Fall through. */
1562 case HIGH:
1563 case PRE_INC:
1564 case PRE_DEC:
1565 case POST_INC:
1566 case POST_DEC:
1567 case PRE_MODIFY:
1568 case POST_MODIFY:
1569 return find_base_value (XEXP (src, 0));
1570
1571 case ZERO_EXTEND:
1572 case SIGN_EXTEND: /* used for NT/Alpha pointers */
1573 /* As we do not know which address space the pointer is referring to, we can
1574 handle this only if the target does not support different pointer or
1575 address modes depending on the address space. */
1576 if (!target_default_pointer_address_modes_p ())
1577 break;
1578
1579 {
1580 rtx temp = find_base_value (XEXP (src, 0));
1581
1582 if (temp != 0 && CONSTANT_P (temp))
1583 temp = convert_memory_address (Pmode, temp);
1584
1585 return temp;
1586 }
1587
1588 default:
1589 break;
1590 }
1591
1592 return 0;
1593}
1594
1595/* Called from init_alias_analysis indirectly through note_stores,
1596 or directly if DEST is a register with a REG_NOALIAS note attached.
1597 SET is null in the latter case. */
1598
1599/* While scanning insns to find base values, reg_seen[N] is nonzero if
1600 register N has been set in this function. */
1601static sbitmap reg_seen;
1602
1603static void
1604record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1605{
1606 unsigned regno;
1607 rtx src;
1608 int n;
1609
1610 if (!REG_P (dest))
1611 return;
1612
1613 regno = REGNO (dest);
1614
1615 gcc_checking_assert (regno < reg_base_value->length ());
1616
1617 n = REG_NREGS (dest);
1618 if (n != 1)
1619 {
1620 while (--n >= 0)
1621 {
1622 bitmap_set_bit (map: reg_seen, bitno: regno + n);
1623 new_reg_base_value[regno + n] = 0;
1624 }
1625 return;
1626 }
1627
1628 if (set)
1629 {
1630 /* A CLOBBER wipes out any old value but does not prevent a previously
1631 unset register from acquiring a base address (i.e. reg_seen is not
1632 set). */
1633 if (GET_CODE (set) == CLOBBER)
1634 {
1635 new_reg_base_value[regno] = 0;
1636 return;
1637 }
1638
1639 src = SET_SRC (set);
1640 }
1641 else
1642 {
1643 /* There's a REG_NOALIAS note against DEST. */
1644 if (bitmap_bit_p (map: reg_seen, bitno: regno))
1645 {
1646 new_reg_base_value[regno] = 0;
1647 return;
1648 }
1649 bitmap_set_bit (map: reg_seen, bitno: regno);
1650 new_reg_base_value[regno] = unique_base_value (id: unique_id++);
1651 return;
1652 }
1653
1654 /* If this is not the first set of REGNO, see whether the new value
1655 is related to the old one. There are two cases of interest:
1656
1657 (1) The register might be assigned an entirely new value
1658 that has the same base term as the original set.
1659
1660 (2) The set might be a simple self-modification that
1661 cannot change REGNO's base value.
1662
1663 If neither case holds, reject the original base value as invalid.
1664 Note that the following situation is not detected:
1665
1666 extern int x, y; int *p = &x; p += (&y-&x);
1667
1668 ANSI C does not allow computing the difference of addresses
1669 of distinct top level objects. */
1670 if (new_reg_base_value[regno] != 0
1671 && find_base_value (src) != new_reg_base_value[regno])
1672 switch (GET_CODE (src))
1673 {
1674 case LO_SUM:
1675 case MINUS:
1676 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1677 new_reg_base_value[regno] = 0;
1678 break;
1679 case PLUS:
1680 /* If the value we add in the PLUS is also a valid base value,
1681 this might be the actual base value, and the original value
1682 an index. */
1683 {
1684 rtx other = NULL_RTX;
1685
1686 if (XEXP (src, 0) == dest)
1687 other = XEXP (src, 1);
1688 else if (XEXP (src, 1) == dest)
1689 other = XEXP (src, 0);
1690
1691 if (! other || find_base_value (src: other))
1692 new_reg_base_value[regno] = 0;
1693 break;
1694 }
1695 case AND:
1696 if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1697 new_reg_base_value[regno] = 0;
1698 break;
1699 default:
1700 new_reg_base_value[regno] = 0;
1701 break;
1702 }
1703 /* If this is the first set of a register, record the value. */
1704 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1705 && ! bitmap_bit_p (map: reg_seen, bitno: regno) && new_reg_base_value[regno] == 0)
1706 new_reg_base_value[regno] = find_base_value (src);
1707
1708 bitmap_set_bit (map: reg_seen, bitno: regno);
1709}
1710
1711/* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1712 using hard registers with non-null REG_BASE_VALUE for renaming. */
1713rtx
1714get_reg_base_value (unsigned int regno)
1715{
1716 return (*reg_base_value)[regno];
1717}
1718
1719/* If a value is known for REGNO, return it. */
1720
1721rtx
1722get_reg_known_value (unsigned int regno)
1723{
1724 if (regno >= FIRST_PSEUDO_REGISTER)
1725 {
1726 regno -= FIRST_PSEUDO_REGISTER;
1727 if (regno < vec_safe_length (v: reg_known_value))
1728 return (*reg_known_value)[regno];
1729 }
1730 return NULL;
1731}
1732
1733/* Set it. */
1734
1735static void
1736set_reg_known_value (unsigned int regno, rtx val)
1737{
1738 if (regno >= FIRST_PSEUDO_REGISTER)
1739 {
1740 regno -= FIRST_PSEUDO_REGISTER;
1741 if (regno < vec_safe_length (v: reg_known_value))
1742 (*reg_known_value)[regno] = val;
1743 }
1744}
1745
1746/* Similarly for reg_known_equiv_p. */
1747
1748bool
1749get_reg_known_equiv_p (unsigned int regno)
1750{
1751 if (regno >= FIRST_PSEUDO_REGISTER)
1752 {
1753 regno -= FIRST_PSEUDO_REGISTER;
1754 if (regno < vec_safe_length (v: reg_known_value))
1755 return bitmap_bit_p (map: reg_known_equiv_p, bitno: regno);
1756 }
1757 return false;
1758}
1759
1760static void
1761set_reg_known_equiv_p (unsigned int regno, bool val)
1762{
1763 if (regno >= FIRST_PSEUDO_REGISTER)
1764 {
1765 regno -= FIRST_PSEUDO_REGISTER;
1766 if (regno < vec_safe_length (v: reg_known_value))
1767 {
1768 if (val)
1769 bitmap_set_bit (map: reg_known_equiv_p, bitno: regno);
1770 else
1771 bitmap_clear_bit (map: reg_known_equiv_p, bitno: regno);
1772 }
1773 }
1774}
1775
1776
1777/* Returns a canonical version of X, from the point of view alias
1778 analysis. (For example, if X is a MEM whose address is a register,
1779 and the register has a known value (say a SYMBOL_REF), then a MEM
1780 whose address is the SYMBOL_REF is returned.) */
1781
1782rtx
1783canon_rtx (rtx x)
1784{
1785 /* Recursively look for equivalences. */
1786 if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1787 {
1788 rtx t = get_reg_known_value (REGNO (x));
1789 if (t == x)
1790 return x;
1791 if (t)
1792 return canon_rtx (x: t);
1793 }
1794
1795 if (GET_CODE (x) == PLUS)
1796 {
1797 rtx x0 = canon_rtx (XEXP (x, 0));
1798 rtx x1 = canon_rtx (XEXP (x, 1));
1799
1800 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1801 return simplify_gen_binary (code: PLUS, GET_MODE (x), op0: x0, op1: x1);
1802 }
1803
1804 /* This gives us much better alias analysis when called from
1805 the loop optimizer. Note we want to leave the original
1806 MEM alone, but need to return the canonicalized MEM with
1807 all the flags with their original values. */
1808 else if (MEM_P (x))
1809 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1810
1811 return x;
1812}
1813
1814/* Return true if X and Y are identical-looking rtx's.
1815 Expect that X and Y has been already canonicalized.
1816
1817 We use the data in reg_known_value above to see if two registers with
1818 different numbers are, in fact, equivalent. */
1819
1820static bool
1821rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1822{
1823 int i;
1824 int j;
1825 enum rtx_code code;
1826 const char *fmt;
1827
1828 if (x == 0 && y == 0)
1829 return true;
1830 if (x == 0 || y == 0)
1831 return false;
1832
1833 if (x == y)
1834 return true;
1835
1836 code = GET_CODE (x);
1837 /* Rtx's of different codes cannot be equal. */
1838 if (code != GET_CODE (y))
1839 return false;
1840
1841 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1842 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1843
1844 if (GET_MODE (x) != GET_MODE (y))
1845 return false;
1846
1847 /* Some RTL can be compared without a recursive examination. */
1848 switch (code)
1849 {
1850 case REG:
1851 return REGNO (x) == REGNO (y);
1852
1853 case LABEL_REF:
1854 return label_ref_label (ref: x) == label_ref_label (ref: y);
1855
1856 case SYMBOL_REF:
1857 {
1858 HOST_WIDE_INT distance = 0;
1859 return (compare_base_symbol_refs (x, y, &distance) == 1
1860 && distance == 0);
1861 }
1862
1863 case ENTRY_VALUE:
1864 /* This is magic, don't go through canonicalization et al. */
1865 return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1866
1867 case VALUE:
1868 CASE_CONST_UNIQUE:
1869 /* Pointer equality guarantees equality for these nodes. */
1870 return false;
1871
1872 default:
1873 break;
1874 }
1875
1876 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1877 if (code == PLUS)
1878 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1879 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1880 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1881 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1882 /* For commutative operations, the RTX match if the operand match in any
1883 order. Also handle the simple binary and unary cases without a loop. */
1884 if (COMMUTATIVE_P (x))
1885 {
1886 rtx xop0 = canon_rtx (XEXP (x, 0));
1887 rtx yop0 = canon_rtx (XEXP (y, 0));
1888 rtx yop1 = canon_rtx (XEXP (y, 1));
1889
1890 return ((rtx_equal_for_memref_p (x: xop0, y: yop0)
1891 && rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)), y: yop1))
1892 || (rtx_equal_for_memref_p (x: xop0, y: yop1)
1893 && rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)), y: yop0)));
1894 }
1895 else if (NON_COMMUTATIVE_P (x))
1896 {
1897 return (rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 0)),
1898 y: canon_rtx (XEXP (y, 0)))
1899 && rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 1)),
1900 y: canon_rtx (XEXP (y, 1))));
1901 }
1902 else if (UNARY_P (x))
1903 return rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, 0)),
1904 y: canon_rtx (XEXP (y, 0)));
1905
1906 /* Compare the elements. If any pair of corresponding elements
1907 fail to match, return false for the whole things.
1908
1909 Limit cases to types which actually appear in addresses. */
1910
1911 fmt = GET_RTX_FORMAT (code);
1912 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1913 {
1914 switch (fmt[i])
1915 {
1916 case 'i':
1917 if (XINT (x, i) != XINT (y, i))
1918 return false;
1919 break;
1920
1921 case 'p':
1922 if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1923 return false;
1924 break;
1925
1926 case 'E':
1927 /* Two vectors must have the same length. */
1928 if (XVECLEN (x, i) != XVECLEN (y, i))
1929 return false;
1930
1931 /* And the corresponding elements must match. */
1932 for (j = 0; j < XVECLEN (x, i); j++)
1933 if (rtx_equal_for_memref_p (x: canon_rtx (XVECEXP (x, i, j)),
1934 y: canon_rtx (XVECEXP (y, i, j))) == 0)
1935 return false;
1936 break;
1937
1938 case 'e':
1939 if (rtx_equal_for_memref_p (x: canon_rtx (XEXP (x, i)),
1940 y: canon_rtx (XEXP (y, i))) == 0)
1941 return false;
1942 break;
1943
1944 /* This can happen for asm operands. */
1945 case 's':
1946 if (strcmp (XSTR (x, i), XSTR (y, i)))
1947 return false;
1948 break;
1949
1950 /* This can happen for an asm which clobbers memory. */
1951 case '0':
1952 break;
1953
1954 /* It is believed that rtx's at this level will never
1955 contain anything but integers and other rtx's,
1956 except for within LABEL_REFs and SYMBOL_REFs. */
1957 default:
1958 gcc_unreachable ();
1959 }
1960 }
1961 return true;
1962}
1963
1964static rtx
1965find_base_term (rtx x, vec<std::pair<cselib_val *,
1966 struct elt_loc_list *> > &visited_vals)
1967{
1968 cselib_val *val;
1969 struct elt_loc_list *l, *f;
1970 rtx ret;
1971 scalar_int_mode int_mode;
1972
1973#if defined (FIND_BASE_TERM)
1974 /* Try machine-dependent ways to find the base term. */
1975 x = FIND_BASE_TERM (x);
1976#endif
1977
1978 switch (GET_CODE (x))
1979 {
1980 case REG:
1981 return REG_BASE_VALUE (x);
1982
1983 case TRUNCATE:
1984 /* As we do not know which address space the pointer is referring to, we can
1985 handle this only if the target does not support different pointer or
1986 address modes depending on the address space. */
1987 if (!target_default_pointer_address_modes_p ())
1988 return 0;
1989 if (!is_a <scalar_int_mode> (GET_MODE (x), result: &int_mode)
1990 || GET_MODE_PRECISION (mode: int_mode) < GET_MODE_PRECISION (Pmode))
1991 return 0;
1992 /* Fall through. */
1993 case HIGH:
1994 case PRE_INC:
1995 case PRE_DEC:
1996 case POST_INC:
1997 case POST_DEC:
1998 case PRE_MODIFY:
1999 case POST_MODIFY:
2000 return find_base_term (XEXP (x, 0), visited_vals);
2001
2002 case ZERO_EXTEND:
2003 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
2004 /* As we do not know which address space the pointer is referring to, we can
2005 handle this only if the target does not support different pointer or
2006 address modes depending on the address space. */
2007 if (!target_default_pointer_address_modes_p ())
2008 return 0;
2009
2010 {
2011 rtx temp = find_base_term (XEXP (x, 0), visited_vals);
2012
2013 if (temp != 0 && CONSTANT_P (temp))
2014 temp = convert_memory_address (Pmode, temp);
2015
2016 return temp;
2017 }
2018
2019 case VALUE:
2020 val = CSELIB_VAL_PTR (x);
2021 ret = NULL_RTX;
2022
2023 if (!val)
2024 return ret;
2025
2026 if (cselib_sp_based_value_p (val))
2027 return static_reg_base_value[STACK_POINTER_REGNUM];
2028
2029 if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
2030 return ret;
2031
2032 f = val->locs;
2033 /* Reset val->locs to avoid infinite recursion. */
2034 if (f)
2035 visited_vals.safe_push (obj: std::make_pair (x&: val, y&: f));
2036 val->locs = NULL;
2037
2038 for (l = f; l; l = l->next)
2039 if (GET_CODE (l->loc) == VALUE
2040 && CSELIB_VAL_PTR (l->loc)->locs
2041 && !CSELIB_VAL_PTR (l->loc)->locs->next
2042 && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
2043 continue;
2044 else if ((ret = find_base_term (x: l->loc, visited_vals)) != 0)
2045 break;
2046
2047 return ret;
2048
2049 case LO_SUM:
2050 /* The standard form is (lo_sum reg sym) so look only at the
2051 second operand. */
2052 return find_base_term (XEXP (x, 1), visited_vals);
2053
2054 case CONST:
2055 x = XEXP (x, 0);
2056 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2057 return 0;
2058 /* Fall through. */
2059 case PLUS:
2060 case MINUS:
2061 {
2062 rtx tmp1 = XEXP (x, 0);
2063 rtx tmp2 = XEXP (x, 1);
2064
2065 /* This is a little bit tricky since we have to determine which of
2066 the two operands represents the real base address. Otherwise this
2067 routine may return the index register instead of the base register.
2068
2069 That may cause us to believe no aliasing was possible, when in
2070 fact aliasing is possible.
2071
2072 We use a few simple tests to guess the base register. Additional
2073 tests can certainly be added. For example, if one of the operands
2074 is a shift or multiply, then it must be the index register and the
2075 other operand is the base register. */
2076
2077 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2078 return find_base_term (x: tmp2, visited_vals);
2079
2080 /* If either operand is known to be a pointer, then prefer it
2081 to determine the base term. */
2082 if (REG_P (tmp1) && REG_POINTER (tmp1))
2083 ;
2084 else if (REG_P (tmp2) && REG_POINTER (tmp2))
2085 std::swap (a&: tmp1, b&: tmp2);
2086 /* If second argument is constant which has base term, prefer it
2087 over variable tmp1. See PR64025. */
2088 else if (CONSTANT_P (tmp2) && !CONST_INT_P (tmp2))
2089 std::swap (a&: tmp1, b&: tmp2);
2090
2091 /* Go ahead and find the base term for both operands. If either base
2092 term is from a pointer or is a named object or a special address
2093 (like an argument or stack reference), then use it for the
2094 base term. */
2095 rtx base = find_base_term (x: tmp1, visited_vals);
2096 if (base != NULL_RTX
2097 && ((REG_P (tmp1) && REG_POINTER (tmp1))
2098 || known_base_value_p (x: base)))
2099 return base;
2100 base = find_base_term (x: tmp2, visited_vals);
2101 if (base != NULL_RTX
2102 && ((REG_P (tmp2) && REG_POINTER (tmp2))
2103 || known_base_value_p (x: base)))
2104 return base;
2105
2106 /* We could not determine which of the two operands was the
2107 base register and which was the index. So we can determine
2108 nothing from the base alias check. */
2109 return 0;
2110 }
2111
2112 case AND:
2113 /* Look through aligning ANDs. And AND with zero or one with
2114 the LSB set isn't one (see for example PR92462). */
2115 if (CONST_INT_P (XEXP (x, 1))
2116 && INTVAL (XEXP (x, 1)) != 0
2117 && (INTVAL (XEXP (x, 1)) & 1) == 0)
2118 return find_base_term (XEXP (x, 0), visited_vals);
2119 return 0;
2120
2121 case SYMBOL_REF:
2122 case LABEL_REF:
2123 return x;
2124
2125 default:
2126 return 0;
2127 }
2128}
2129
2130/* Wrapper around the worker above which removes locs from visited VALUEs
2131 to avoid visiting them multiple times. We unwind that changes here. */
2132
2133static rtx
2134find_base_term (rtx x)
2135{
2136 auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2137 rtx res = find_base_term (x, visited_vals);
2138 for (unsigned i = 0; i < visited_vals.length (); ++i)
2139 visited_vals[i].first->locs = visited_vals[i].second;
2140 return res;
2141}
2142
2143/* Return true if accesses to address X may alias accesses based
2144 on the stack pointer. */
2145
2146bool
2147may_be_sp_based_p (rtx x)
2148{
2149 rtx base = find_base_term (x);
2150 return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2151}
2152
2153/* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2154 if they refer to different objects and -1 if we cannot decide. */
2155
2156int
2157compare_base_decls (tree base1, tree base2)
2158{
2159 int ret;
2160 gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2161 if (base1 == base2)
2162 return 1;
2163
2164 /* If we have two register decls with register specification we
2165 cannot decide unless their assembler names are the same. */
2166 if (VAR_P (base1)
2167 && VAR_P (base2)
2168 && DECL_HARD_REGISTER (base1)
2169 && DECL_HARD_REGISTER (base2)
2170 && DECL_ASSEMBLER_NAME_SET_P (base1)
2171 && DECL_ASSEMBLER_NAME_SET_P (base2))
2172 {
2173 if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2174 return 1;
2175 return -1;
2176 }
2177
2178 /* Declarations of non-automatic variables may have aliases. All other
2179 decls are unique. */
2180 if (!decl_in_symtab_p (decl: base1)
2181 || !decl_in_symtab_p (decl: base2))
2182 return 0;
2183
2184 /* Don't cause symbols to be inserted by the act of checking. */
2185 symtab_node *node1 = symtab_node::get (decl: base1);
2186 if (!node1)
2187 return 0;
2188 symtab_node *node2 = symtab_node::get (decl: base2);
2189 if (!node2)
2190 return 0;
2191
2192 ret = node1->equal_address_to (s2: node2, memory_accessed: true);
2193 return ret;
2194}
2195
2196/* Compare SYMBOL_REFs X_BASE and Y_BASE.
2197
2198 - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2199 to *DISTANCE if DISTANCE is nonnull.
2200
2201 - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2202
2203 - Return -1 if one of the two results applies, but we can't tell
2204 which at compile time. Update DISTANCE in the same way as
2205 for a return value of 1, for the case in which that holds. */
2206
2207static int
2208compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2209 HOST_WIDE_INT *distance)
2210{
2211 tree x_decl = SYMBOL_REF_DECL (x_base);
2212 tree y_decl = SYMBOL_REF_DECL (y_base);
2213 bool binds_def = true;
2214 bool swap = false;
2215
2216 if (XSTR (x_base, 0) == XSTR (y_base, 0))
2217 return 1;
2218 if (x_decl && y_decl)
2219 return compare_base_decls (base1: x_decl, base2: y_decl);
2220 if (x_decl || y_decl)
2221 {
2222 if (!x_decl)
2223 {
2224 swap = true;
2225 std::swap (a&: x_decl, b&: y_decl);
2226 std::swap (a&: x_base, b&: y_base);
2227 }
2228 /* We handle specially only section anchors. Other symbols are
2229 either equal (via aliasing) or refer to different objects. */
2230 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2231 return -1;
2232 /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2233 to ignore CONST_DECLs because they are readonly. */
2234 if (!VAR_P (x_decl)
2235 || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2236 return 0;
2237
2238 symtab_node *x_node = symtab_node::get_create (node: x_decl)
2239 ->ultimate_alias_target ();
2240 /* External variable cannot be in section anchor. */
2241 if (!x_node->definition)
2242 return 0;
2243 x_base = XEXP (DECL_RTL (x_node->decl), 0);
2244 /* If not in anchor, we can disambiguate. */
2245 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2246 return 0;
2247
2248 /* We have an alias of anchored variable. If it can be interposed;
2249 we must assume it may or may not alias its anchor. */
2250 binds_def = decl_binds_to_current_def_p (x_decl);
2251 }
2252 /* If we have variable in section anchor, we can compare by offset. */
2253 if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2254 && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2255 {
2256 if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2257 return 0;
2258 if (distance)
2259 *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2260 - SYMBOL_REF_BLOCK_OFFSET (x_base));
2261 return binds_def ? 1 : -1;
2262 }
2263 /* Either the symbols are equal (via aliasing) or they refer to
2264 different objects. */
2265 return -1;
2266}
2267
2268/* Return false if the addresses X and Y are known to point to different
2269 objects, true if they might be pointers to the same object. */
2270
2271static bool
2272base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2273 machine_mode x_mode, machine_mode y_mode)
2274{
2275 /* If the address itself has no known base see if a known equivalent
2276 value has one. If either address still has no known base, nothing
2277 is known about aliasing. */
2278 if (x_base == 0)
2279 {
2280 rtx x_c;
2281
2282 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2283 return true;
2284
2285 x_base = find_base_term (x: x_c);
2286 if (x_base == 0)
2287 return true;
2288 }
2289
2290 if (y_base == 0)
2291 {
2292 rtx y_c;
2293 if (! flag_expensive_optimizations || (y_c = canon_rtx (x: y)) == y)
2294 return true;
2295
2296 y_base = find_base_term (x: y_c);
2297 if (y_base == 0)
2298 return true;
2299 }
2300
2301 /* If the base addresses are equal nothing is known about aliasing. */
2302 if (rtx_equal_p (x_base, y_base))
2303 return true;
2304
2305 /* The base addresses are different expressions. If they are not accessed
2306 via AND, there is no conflict. We can bring knowledge of object
2307 alignment into play here. For example, on alpha, "char a, b;" can
2308 alias one another, though "char a; long b;" cannot. AND addresses may
2309 implicitly alias surrounding objects; i.e. unaligned access in DImode
2310 via AND address can alias all surrounding object types except those
2311 with aligment 8 or higher. */
2312 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2313 return true;
2314 if (GET_CODE (x) == AND
2315 && (!CONST_INT_P (XEXP (x, 1))
2316 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2317 return true;
2318 if (GET_CODE (y) == AND
2319 && (!CONST_INT_P (XEXP (y, 1))
2320 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2321 return true;
2322
2323 /* Differing symbols not accessed via AND never alias. */
2324 if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2325 return compare_base_symbol_refs (x_base, y_base) != 0;
2326
2327 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2328 return false;
2329
2330 if (unique_base_value_p (x: x_base) || unique_base_value_p (x: y_base))
2331 return false;
2332
2333 return true;
2334}
2335
2336/* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2337 (or equal to) that of V. */
2338
2339static bool
2340refs_newer_value_p (const_rtx expr, rtx v)
2341{
2342 int minuid = CSELIB_VAL_PTR (v)->uid;
2343 subrtx_iterator::array_type array;
2344 FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2345 if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid)
2346 return true;
2347 return false;
2348}
2349
2350/* Convert the address X into something we can use. This is done by returning
2351 it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2352 we call cselib to get a more useful rtx. */
2353
2354rtx
2355get_addr (rtx x)
2356{
2357 cselib_val *v;
2358 struct elt_loc_list *l;
2359
2360 if (GET_CODE (x) != VALUE)
2361 {
2362 if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2363 && GET_CODE (XEXP (x, 0)) == VALUE
2364 && CONST_SCALAR_INT_P (XEXP (x, 1)))
2365 {
2366 rtx op0 = get_addr (XEXP (x, 0));
2367 if (op0 != XEXP (x, 0))
2368 {
2369 poly_int64 c;
2370 if (GET_CODE (x) == PLUS
2371 && poly_int_rtx_p (XEXP (x, 1), res: &c))
2372 return plus_constant (GET_MODE (x), op0, c);
2373 return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2374 op0, XEXP (x, 1));
2375 }
2376 }
2377 return x;
2378 }
2379 v = CSELIB_VAL_PTR (x);
2380 if (v)
2381 {
2382 bool have_equivs = cselib_have_permanent_equivalences ();
2383 if (have_equivs)
2384 v = canonical_cselib_val (val: v);
2385 for (l = v->locs; l; l = l->next)
2386 if (CONSTANT_P (l->loc))
2387 return l->loc;
2388 for (l = v->locs; l; l = l->next)
2389 if (!REG_P (l->loc) && !MEM_P (l->loc)
2390 /* Avoid infinite recursion when potentially dealing with
2391 var-tracking artificial equivalences, by skipping the
2392 equivalences themselves, and not choosing expressions
2393 that refer to newer VALUEs. */
2394 && (!have_equivs
2395 || (GET_CODE (l->loc) != VALUE
2396 && !refs_newer_value_p (expr: l->loc, v: x))))
2397 return l->loc;
2398 if (have_equivs)
2399 {
2400 for (l = v->locs; l; l = l->next)
2401 if (REG_P (l->loc)
2402 || (GET_CODE (l->loc) != VALUE
2403 && !refs_newer_value_p (expr: l->loc, v: x)))
2404 return l->loc;
2405 /* Return the canonical value. */
2406 return v->val_rtx;
2407 }
2408 if (v->locs)
2409 return v->locs->loc;
2410 }
2411 return x;
2412}
2413
2414/* Return the address of the (N_REFS + 1)th memory reference to ADDR
2415 where SIZE is the size in bytes of the memory reference. If ADDR
2416 is not modified by the memory reference then ADDR is returned. */
2417
2418static rtx
2419addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2420{
2421 poly_int64 offset = 0;
2422
2423 switch (GET_CODE (addr))
2424 {
2425 case PRE_INC:
2426 offset = (n_refs + 1) * size;
2427 break;
2428 case PRE_DEC:
2429 offset = -(n_refs + 1) * size;
2430 break;
2431 case POST_INC:
2432 offset = n_refs * size;
2433 break;
2434 case POST_DEC:
2435 offset = -n_refs * size;
2436 break;
2437
2438 default:
2439 return addr;
2440 }
2441
2442 addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2443 addr = canon_rtx (x: addr);
2444
2445 return addr;
2446}
2447
2448/* Return TRUE if an object X sized at XSIZE bytes and another object
2449 Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2450 any of the sizes is zero, assume an overlap, otherwise use the
2451 absolute value of the sizes as the actual sizes. */
2452
2453static inline bool
2454offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2455{
2456 if (known_eq (xsize, 0) || known_eq (ysize, 0))
2457 return true;
2458
2459 if (maybe_ge (c, 0))
2460 return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2461 else
2462 return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2463}
2464
2465/* Return one if X and Y (memory addresses) reference the
2466 same location in memory or if the references overlap.
2467 Return zero if they do not overlap, else return
2468 minus one in which case they still might reference the same location.
2469
2470 C is an offset accumulator. When
2471 C is nonzero, we are testing aliases between X and Y + C.
2472 XSIZE is the size in bytes of the X reference,
2473 similarly YSIZE is the size in bytes for Y.
2474 Expect that canon_rtx has been already called for X and Y.
2475
2476 If XSIZE or YSIZE is zero, we do not know the amount of memory being
2477 referenced (the reference was BLKmode), so make the most pessimistic
2478 assumptions.
2479
2480 If XSIZE or YSIZE is negative, we may access memory outside the object
2481 being referenced as a side effect. This can happen when using AND to
2482 align memory references, as is done on the Alpha.
2483
2484 Nice to notice that varying addresses cannot conflict with fp if no
2485 local variables had their addresses taken, but that's too hard now.
2486
2487 ??? Contrary to the tree alias oracle this does not return
2488 one for X + non-constant and Y + non-constant when X and Y are equal.
2489 If that is fixed the TBAA hack for union type-punning can be removed. */
2490
2491static int
2492memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2493 poly_int64 c)
2494{
2495 if (GET_CODE (x) == VALUE)
2496 {
2497 if (REG_P (y))
2498 {
2499 struct elt_loc_list *l = NULL;
2500 if (CSELIB_VAL_PTR (x))
2501 for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2502 l; l = l->next)
2503 if (REG_P (l->loc) && rtx_equal_for_memref_p (x: l->loc, y))
2504 break;
2505 if (l)
2506 x = y;
2507 else
2508 x = get_addr (x);
2509 }
2510 /* Don't call get_addr if y is the same VALUE. */
2511 else if (x != y)
2512 x = get_addr (x);
2513 }
2514 if (GET_CODE (y) == VALUE)
2515 {
2516 if (REG_P (x))
2517 {
2518 struct elt_loc_list *l = NULL;
2519 if (CSELIB_VAL_PTR (y))
2520 for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2521 l; l = l->next)
2522 if (REG_P (l->loc) && rtx_equal_for_memref_p (x: l->loc, y: x))
2523 break;
2524 if (l)
2525 y = x;
2526 else
2527 y = get_addr (x: y);
2528 }
2529 /* Don't call get_addr if x is the same VALUE. */
2530 else if (y != x)
2531 y = get_addr (x: y);
2532 }
2533 if (GET_CODE (x) == HIGH)
2534 x = XEXP (x, 0);
2535 else if (GET_CODE (x) == LO_SUM)
2536 x = XEXP (x, 1);
2537 else
2538 x = addr_side_effect_eval (addr: x, size: maybe_lt (a: xsize, b: 0) ? -xsize : xsize, n_refs: 0);
2539 if (GET_CODE (y) == HIGH)
2540 y = XEXP (y, 0);
2541 else if (GET_CODE (y) == LO_SUM)
2542 y = XEXP (y, 1);
2543 else
2544 y = addr_side_effect_eval (addr: y, size: maybe_lt (a: ysize, b: 0) ? -ysize : ysize, n_refs: 0);
2545
2546 if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2547 {
2548 HOST_WIDE_INT distance = 0;
2549 int cmp = compare_base_symbol_refs (x_base: x, y_base: y, distance: &distance);
2550
2551 /* If both decls are the same, decide by offsets. */
2552 if (cmp == 1)
2553 return offset_overlap_p (c: c + distance, xsize, ysize);
2554 /* Assume a potential overlap for symbolic addresses that went
2555 through alignment adjustments (i.e., that have negative
2556 sizes), because we can't know how far they are from each
2557 other. */
2558 if (maybe_lt (a: xsize, b: 0) || maybe_lt (a: ysize, b: 0))
2559 return -1;
2560 /* If decls are different or we know by offsets that there is no overlap,
2561 we win. */
2562 if (!cmp || !offset_overlap_p (c: c + distance, xsize, ysize))
2563 return 0;
2564 /* Decls may or may not be different and offsets overlap....*/
2565 return -1;
2566 }
2567 else if (rtx_equal_for_memref_p (x, y))
2568 {
2569 return offset_overlap_p (c, xsize, ysize);
2570 }
2571
2572 /* This code used to check for conflicts involving stack references and
2573 globals but the base address alias code now handles these cases. */
2574
2575 if (GET_CODE (x) == PLUS)
2576 {
2577 /* The fact that X is canonicalized means that this
2578 PLUS rtx is canonicalized. */
2579 rtx x0 = XEXP (x, 0);
2580 rtx x1 = XEXP (x, 1);
2581
2582 /* However, VALUEs might end up in different positions even in
2583 canonical PLUSes. Comparing their addresses is enough. */
2584 if (x0 == y)
2585 return memrefs_conflict_p (xsize, x: x1, ysize, const0_rtx, c);
2586 else if (x1 == y)
2587 return memrefs_conflict_p (xsize, x: x0, ysize, const0_rtx, c);
2588
2589 poly_int64 cx1, cy1;
2590 if (GET_CODE (y) == PLUS)
2591 {
2592 /* The fact that Y is canonicalized means that this
2593 PLUS rtx is canonicalized. */
2594 rtx y0 = XEXP (y, 0);
2595 rtx y1 = XEXP (y, 1);
2596
2597 if (x0 == y1)
2598 return memrefs_conflict_p (xsize, x: x1, ysize, y: y0, c);
2599 if (x1 == y0)
2600 return memrefs_conflict_p (xsize, x: x0, ysize, y: y1, c);
2601
2602 if (rtx_equal_for_memref_p (x: x1, y: y1))
2603 return memrefs_conflict_p (xsize, x: x0, ysize, y: y0, c);
2604 if (rtx_equal_for_memref_p (x: x0, y: y0))
2605 return memrefs_conflict_p (xsize, x: x1, ysize, y: y1, c);
2606 if (poly_int_rtx_p (x: x1, res: &cx1))
2607 {
2608 if (poly_int_rtx_p (x: y1, res: &cy1))
2609 return memrefs_conflict_p (xsize, x: x0, ysize, y: y0,
2610 c: c - cx1 + cy1);
2611 else
2612 return memrefs_conflict_p (xsize, x: x0, ysize, y, c: c - cx1);
2613 }
2614 else if (poly_int_rtx_p (x: y1, res: &cy1))
2615 return memrefs_conflict_p (xsize, x, ysize, y: y0, c: c + cy1);
2616
2617 return -1;
2618 }
2619 else if (poly_int_rtx_p (x: x1, res: &cx1))
2620 return memrefs_conflict_p (xsize, x: x0, ysize, y, c: c - cx1);
2621 }
2622 else if (GET_CODE (y) == PLUS)
2623 {
2624 /* The fact that Y is canonicalized means that this
2625 PLUS rtx is canonicalized. */
2626 rtx y0 = XEXP (y, 0);
2627 rtx y1 = XEXP (y, 1);
2628
2629 if (x == y0)
2630 return memrefs_conflict_p (xsize, const0_rtx, ysize, y: y1, c);
2631 if (x == y1)
2632 return memrefs_conflict_p (xsize, const0_rtx, ysize, y: y0, c);
2633
2634 poly_int64 cy1;
2635 if (poly_int_rtx_p (x: y1, res: &cy1))
2636 return memrefs_conflict_p (xsize, x, ysize, y: y0, c: c + cy1);
2637 else
2638 return -1;
2639 }
2640
2641 if (GET_CODE (x) == GET_CODE (y))
2642 switch (GET_CODE (x))
2643 {
2644 case MULT:
2645 {
2646 /* Handle cases where we expect the second operands to be the
2647 same, and check only whether the first operand would conflict
2648 or not. */
2649 rtx x0, y0;
2650 rtx x1 = canon_rtx (XEXP (x, 1));
2651 rtx y1 = canon_rtx (XEXP (y, 1));
2652 if (! rtx_equal_for_memref_p (x: x1, y: y1))
2653 return -1;
2654 x0 = canon_rtx (XEXP (x, 0));
2655 y0 = canon_rtx (XEXP (y, 0));
2656 if (rtx_equal_for_memref_p (x: x0, y: y0))
2657 return offset_overlap_p (c, xsize, ysize);
2658
2659 /* Can't properly adjust our sizes. */
2660 poly_int64 c1;
2661 if (!poly_int_rtx_p (x: x1, res: &c1)
2662 || !can_div_trunc_p (a: xsize, b: c1, quotient: &xsize)
2663 || !can_div_trunc_p (a: ysize, b: c1, quotient: &ysize)
2664 || !can_div_trunc_p (a: c, b: c1, quotient: &c))
2665 return -1;
2666 return memrefs_conflict_p (xsize, x: x0, ysize, y: y0, c);
2667 }
2668
2669 default:
2670 break;
2671 }
2672
2673 /* Deal with alignment ANDs by adjusting offset and size so as to
2674 cover the maximum range, without taking any previously known
2675 alignment into account. Make a size negative after such an
2676 adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2677 assume a potential overlap, because they may end up in contiguous
2678 memory locations and the stricter-alignment access may span over
2679 part of both. */
2680 if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2681 {
2682 HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2683 unsigned HOST_WIDE_INT uc = sc;
2684 if (sc < 0 && pow2_or_zerop (x: -uc))
2685 {
2686 if (maybe_gt (xsize, 0))
2687 xsize = -xsize;
2688 if (maybe_ne (a: xsize, b: 0))
2689 xsize += sc + 1;
2690 c -= sc + 1;
2691 return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2692 ysize, y, c);
2693 }
2694 }
2695 if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2696 {
2697 HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2698 unsigned HOST_WIDE_INT uc = sc;
2699 if (sc < 0 && pow2_or_zerop (x: -uc))
2700 {
2701 if (maybe_gt (ysize, 0))
2702 ysize = -ysize;
2703 if (maybe_ne (a: ysize, b: 0))
2704 ysize += sc + 1;
2705 c += sc + 1;
2706 return memrefs_conflict_p (xsize, x,
2707 ysize, y: canon_rtx (XEXP (y, 0)), c);
2708 }
2709 }
2710
2711 if (CONSTANT_P (x))
2712 {
2713 poly_int64 cx, cy;
2714 if (poly_int_rtx_p (x, res: &cx) && poly_int_rtx_p (x: y, res: &cy))
2715 {
2716 c += cy - cx;
2717 return offset_overlap_p (c, xsize, ysize);
2718 }
2719
2720 if (GET_CODE (x) == CONST)
2721 {
2722 if (GET_CODE (y) == CONST)
2723 return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2724 ysize, y: canon_rtx (XEXP (y, 0)), c);
2725 else
2726 return memrefs_conflict_p (xsize, x: canon_rtx (XEXP (x, 0)),
2727 ysize, y, c);
2728 }
2729 if (GET_CODE (y) == CONST)
2730 return memrefs_conflict_p (xsize, x, ysize,
2731 y: canon_rtx (XEXP (y, 0)), c);
2732
2733 /* Assume a potential overlap for symbolic addresses that went
2734 through alignment adjustments (i.e., that have negative
2735 sizes), because we can't know how far they are from each
2736 other. */
2737 if (CONSTANT_P (y))
2738 return (maybe_lt (a: xsize, b: 0)
2739 || maybe_lt (a: ysize, b: 0)
2740 || offset_overlap_p (c, xsize, ysize));
2741
2742 return -1;
2743 }
2744
2745 return -1;
2746}
2747
2748/* Functions to compute memory dependencies.
2749
2750 Since we process the insns in execution order, we can build tables
2751 to keep track of what registers are fixed (and not aliased), what registers
2752 are varying in known ways, and what registers are varying in unknown
2753 ways.
2754
2755 If both memory references are volatile, then there must always be a
2756 dependence between the two references, since their order cannot be
2757 changed. A volatile and non-volatile reference can be interchanged
2758 though.
2759
2760 We also must allow AND addresses, because they may generate accesses
2761 outside the object being referenced. This is used to generate aligned
2762 addresses from unaligned addresses, for instance, the alpha
2763 storeqi_unaligned pattern. */
2764
2765/* Read dependence: X is read after read in MEM takes place. There can
2766 only be a dependence here if both reads are volatile, or if either is
2767 an explicit barrier. */
2768
2769bool
2770read_dependence (const_rtx mem, const_rtx x)
2771{
2772 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2773 return true;
2774 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2775 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2776 return true;
2777 return false;
2778}
2779
2780/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2781
2782static tree
2783decl_for_component_ref (tree x)
2784{
2785 do
2786 {
2787 x = TREE_OPERAND (x, 0);
2788 }
2789 while (x && TREE_CODE (x) == COMPONENT_REF);
2790
2791 return x && DECL_P (x) ? x : NULL_TREE;
2792}
2793
2794/* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2795 for the offset of the field reference. *KNOWN_P says whether the
2796 offset is known. */
2797
2798static void
2799adjust_offset_for_component_ref (tree x, bool *known_p,
2800 poly_int64 *offset)
2801{
2802 if (!*known_p)
2803 return;
2804 do
2805 {
2806 tree xoffset = component_ref_field_offset (x);
2807 tree field = TREE_OPERAND (x, 1);
2808 if (!poly_int_tree_p (t: xoffset))
2809 {
2810 *known_p = false;
2811 return;
2812 }
2813
2814 poly_offset_int woffset
2815 = (wi::to_poly_offset (t: xoffset)
2816 + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2817 >> LOG2_BITS_PER_UNIT)
2818 + *offset);
2819 if (!woffset.to_shwi (r: offset))
2820 {
2821 *known_p = false;
2822 return;
2823 }
2824
2825 x = TREE_OPERAND (x, 0);
2826 }
2827 while (x && TREE_CODE (x) == COMPONENT_REF);
2828}
2829
2830/* Return true if we can determine the exprs corresponding to memrefs
2831 X and Y and they do not overlap.
2832 If LOOP_VARIANT is set, skip offset-based disambiguation */
2833
2834bool
2835nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2836{
2837 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2838 rtx rtlx, rtly;
2839 rtx basex, basey;
2840 bool moffsetx_known_p, moffsety_known_p;
2841 poly_int64 moffsetx = 0, moffsety = 0;
2842 poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2843
2844 /* Unless both have exprs, we can't tell anything. */
2845 if (exprx == 0 || expry == 0)
2846 return false;
2847
2848 /* For spill-slot accesses make sure we have valid offsets. */
2849 if ((exprx == get_spill_slot_decl (false)
2850 && ! MEM_OFFSET_KNOWN_P (x))
2851 || (expry == get_spill_slot_decl (false)
2852 && ! MEM_OFFSET_KNOWN_P (y)))
2853 return false;
2854
2855 /* If the field reference test failed, look at the DECLs involved. */
2856 moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2857 if (moffsetx_known_p)
2858 moffsetx = MEM_OFFSET (x);
2859 if (TREE_CODE (exprx) == COMPONENT_REF)
2860 {
2861 tree t = decl_for_component_ref (x: exprx);
2862 if (! t)
2863 return false;
2864 adjust_offset_for_component_ref (x: exprx, known_p: &moffsetx_known_p, offset: &moffsetx);
2865 exprx = t;
2866 }
2867
2868 moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2869 if (moffsety_known_p)
2870 moffsety = MEM_OFFSET (y);
2871 if (TREE_CODE (expry) == COMPONENT_REF)
2872 {
2873 tree t = decl_for_component_ref (x: expry);
2874 if (! t)
2875 return false;
2876 adjust_offset_for_component_ref (x: expry, known_p: &moffsety_known_p, offset: &moffsety);
2877 expry = t;
2878 }
2879
2880 if (! DECL_P (exprx) || ! DECL_P (expry))
2881 return false;
2882
2883 /* If we refer to different gimple registers, or one gimple register
2884 and one non-gimple-register, we know they can't overlap. First,
2885 gimple registers don't have their addresses taken. Now, there
2886 could be more than one stack slot for (different versions of) the
2887 same gimple register, but we can presumably tell they don't
2888 overlap based on offsets from stack base addresses elsewhere.
2889 It's important that we don't proceed to DECL_RTL, because gimple
2890 registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2891 able to do anything about them since no SSA information will have
2892 remained to guide it. */
2893 if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2894 return exprx != expry
2895 || (moffsetx_known_p && moffsety_known_p
2896 && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2897 && !offset_overlap_p (c: moffsety - moffsetx,
2898 MEM_SIZE (x), MEM_SIZE (y)));
2899
2900 /* With invalid code we can end up storing into the constant pool.
2901 Bail out to avoid ICEing when creating RTL for this.
2902 See gfortran.dg/lto/20091028-2_0.f90. */
2903 if (TREE_CODE (exprx) == CONST_DECL
2904 || TREE_CODE (expry) == CONST_DECL)
2905 return true;
2906
2907 /* If one decl is known to be a function or label in a function and
2908 the other is some kind of data, they can't overlap. */
2909 if ((TREE_CODE (exprx) == FUNCTION_DECL
2910 || TREE_CODE (exprx) == LABEL_DECL)
2911 != (TREE_CODE (expry) == FUNCTION_DECL
2912 || TREE_CODE (expry) == LABEL_DECL))
2913 return true;
2914
2915 /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2916 living in multiple places), we can't tell anything. Exception
2917 are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2918 if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2919 || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2920 return false;
2921
2922 rtlx = DECL_RTL (exprx);
2923 rtly = DECL_RTL (expry);
2924
2925 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2926 can't overlap unless they are the same because we never reuse that part
2927 of the stack frame used for locals for spilled pseudos. */
2928 if ((!MEM_P (rtlx) || !MEM_P (rtly))
2929 && ! rtx_equal_p (rtlx, rtly))
2930 return true;
2931
2932 /* If we have MEMs referring to different address spaces (which can
2933 potentially overlap), we cannot easily tell from the addresses
2934 whether the references overlap. */
2935 if (MEM_P (rtlx) && MEM_P (rtly)
2936 && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2937 return false;
2938
2939 /* Get the base and offsets of both decls. If either is a register, we
2940 know both are and are the same, so use that as the base. The only
2941 we can avoid overlap is if we can deduce that they are nonoverlapping
2942 pieces of that decl, which is very rare. */
2943 basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2944 basex = strip_offset_and_add (x: basex, offset: &offsetx);
2945
2946 basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2947 basey = strip_offset_and_add (x: basey, offset: &offsety);
2948
2949 /* If the bases are different, we know they do not overlap if both
2950 are constants or if one is a constant and the other a pointer into the
2951 stack frame. Otherwise a different base means we can't tell if they
2952 overlap or not. */
2953 if (compare_base_decls (base1: exprx, base2: expry) == 0)
2954 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2955 || (CONSTANT_P (basex) && REG_P (basey)
2956 && REGNO_PTR_FRAME_P (REGNO (basey)))
2957 || (CONSTANT_P (basey) && REG_P (basex)
2958 && REGNO_PTR_FRAME_P (REGNO (basex))));
2959
2960 /* Offset based disambiguation not appropriate for loop invariant */
2961 if (loop_invariant)
2962 return false;
2963
2964 /* Offset based disambiguation is OK even if we do not know that the
2965 declarations are necessarily different
2966 (i.e. compare_base_decls (exprx, expry) == -1) */
2967
2968 sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2969 : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2970 : -1);
2971 sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2972 : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2973 : -1);
2974
2975 /* If we have an offset for either memref, it can update the values computed
2976 above. */
2977 if (moffsetx_known_p)
2978 offsetx += moffsetx, sizex -= moffsetx;
2979 if (moffsety_known_p)
2980 offsety += moffsety, sizey -= moffsety;
2981
2982 /* If a memref has both a size and an offset, we can use the smaller size.
2983 We can't do this if the offset isn't known because we must view this
2984 memref as being anywhere inside the DECL's MEM. */
2985 if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2986 sizex = MEM_SIZE (x);
2987 if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2988 sizey = MEM_SIZE (y);
2989
2990 return !ranges_maybe_overlap_p (pos1: offsetx, size1: sizex, pos2: offsety, size2: sizey);
2991}
2992
2993/* Helper for true_dependence and canon_true_dependence.
2994 Checks for true dependence: X is read after store in MEM takes place.
2995
2996 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2997 NULL_RTX, and the canonical addresses of MEM and X are both computed
2998 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2999
3000 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
3001
3002 Returns true if there is a true dependence, false otherwise. */
3003
3004static bool
3005true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3006 const_rtx x, rtx x_addr, bool mem_canonicalized)
3007{
3008 rtx true_mem_addr;
3009 rtx base;
3010 int ret;
3011
3012 gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
3013 : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
3014
3015 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3016 return true;
3017
3018 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3019 This is used in epilogue deallocation functions, and in cselib. */
3020 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3021 return true;
3022 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3023 return true;
3024 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3025 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3026 return true;
3027
3028 if (! x_addr)
3029 x_addr = XEXP (x, 0);
3030 x_addr = get_addr (x: x_addr);
3031
3032 if (! mem_addr)
3033 {
3034 mem_addr = XEXP (mem, 0);
3035 if (mem_mode == VOIDmode)
3036 mem_mode = GET_MODE (mem);
3037 }
3038 true_mem_addr = get_addr (x: mem_addr);
3039
3040 /* Read-only memory is by definition never modified, and therefore can't
3041 conflict with anything. However, don't assume anything when AND
3042 addresses are involved and leave to the code below to determine
3043 dependence. We don't expect to find read-only set on MEM, but
3044 stupid user tricks can produce them, so don't die. */
3045 if (MEM_READONLY_P (x)
3046 && GET_CODE (x_addr) != AND
3047 && GET_CODE (true_mem_addr) != AND)
3048 return false;
3049
3050 /* If we have MEMs referring to different address spaces (which can
3051 potentially overlap), we cannot easily tell from the addresses
3052 whether the references overlap. */
3053 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3054 return true;
3055
3056 base = find_base_term (x: x_addr);
3057 if (base && (GET_CODE (base) == LABEL_REF
3058 || (GET_CODE (base) == SYMBOL_REF
3059 && CONSTANT_POOL_ADDRESS_P (base))))
3060 return false;
3061
3062 rtx mem_base = find_base_term (x: true_mem_addr);
3063 if (! base_alias_check (x: x_addr, x_base: base, y: true_mem_addr, y_base: mem_base,
3064 GET_MODE (x), y_mode: mem_mode))
3065 return false;
3066
3067 x_addr = canon_rtx (x: x_addr);
3068 if (!mem_canonicalized)
3069 mem_addr = canon_rtx (x: true_mem_addr);
3070
3071 if ((ret = memrefs_conflict_p (xsize: GET_MODE_SIZE (mode: mem_mode), x: mem_addr,
3072 SIZE_FOR_MODE (x), y: x_addr, c: 0)) != -1)
3073 return !!ret;
3074
3075 if (mems_in_disjoint_alias_sets_p (mem1: x, mem2: mem))
3076 return false;
3077
3078 if (nonoverlapping_memrefs_p (x: mem, y: x, loop_invariant: false))
3079 return false;
3080
3081 return rtx_refs_may_alias_p (x, mem, tbaa_p: true);
3082}
3083
3084/* True dependence: X is read after store in MEM takes place. */
3085
3086bool
3087true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3088{
3089 return true_dependence_1 (mem, mem_mode, NULL_RTX,
3090 x, NULL_RTX, /*mem_canonicalized=*/false);
3091}
3092
3093/* Canonical true dependence: X is read after store in MEM takes place.
3094 Variant of true_dependence which assumes MEM has already been
3095 canonicalized (hence we no longer do that here).
3096 The mem_addr argument has been added, since true_dependence_1 computed
3097 this value prior to canonicalizing. */
3098
3099bool
3100canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3101 const_rtx x, rtx x_addr)
3102{
3103 return true_dependence_1 (mem, mem_mode, mem_addr,
3104 x, x_addr, /*mem_canonicalized=*/true);
3105}
3106
3107/* Returns true if a write to X might alias a previous read from
3108 (or, if WRITEP is true, a write to) MEM.
3109 If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3110 and X_MODE the mode for that access.
3111 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3112
3113static bool
3114write_dependence_p (const_rtx mem,
3115 const_rtx x, machine_mode x_mode, rtx x_addr,
3116 bool mem_canonicalized, bool x_canonicalized, bool writep)
3117{
3118 rtx mem_addr;
3119 rtx true_mem_addr, true_x_addr;
3120 rtx base;
3121 int ret;
3122
3123 gcc_checking_assert (x_canonicalized
3124 ? (x_addr != NULL_RTX
3125 && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3126 : (x_addr == NULL_RTX && x_mode == VOIDmode));
3127
3128 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3129 return true;
3130
3131 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3132 This is used in epilogue deallocation functions. */
3133 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3134 return true;
3135 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3136 return true;
3137 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3138 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3139 return true;
3140
3141 if (!x_addr)
3142 x_addr = XEXP (x, 0);
3143 true_x_addr = get_addr (x: x_addr);
3144
3145 mem_addr = XEXP (mem, 0);
3146 true_mem_addr = get_addr (x: mem_addr);
3147
3148 /* A read from read-only memory can't conflict with read-write memory.
3149 Don't assume anything when AND addresses are involved and leave to
3150 the code below to determine dependence. */
3151 if (!writep
3152 && MEM_READONLY_P (mem)
3153 && GET_CODE (true_x_addr) != AND
3154 && GET_CODE (true_mem_addr) != AND)
3155 return false;
3156
3157 /* If we have MEMs referring to different address spaces (which can
3158 potentially overlap), we cannot easily tell from the addresses
3159 whether the references overlap. */
3160 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3161 return true;
3162
3163 base = find_base_term (x: true_mem_addr);
3164 if (! writep
3165 && base
3166 && (GET_CODE (base) == LABEL_REF
3167 || (GET_CODE (base) == SYMBOL_REF
3168 && CONSTANT_POOL_ADDRESS_P (base))))
3169 return false;
3170
3171 rtx x_base = find_base_term (x: true_x_addr);
3172 if (! base_alias_check (x: true_x_addr, x_base, y: true_mem_addr, y_base: base,
3173 GET_MODE (x), GET_MODE (mem)))
3174 return false;
3175
3176 if (!x_canonicalized)
3177 {
3178 x_addr = canon_rtx (x: true_x_addr);
3179 x_mode = GET_MODE (x);
3180 }
3181 if (!mem_canonicalized)
3182 mem_addr = canon_rtx (x: true_mem_addr);
3183
3184 if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), x: mem_addr,
3185 ysize: GET_MODE_SIZE (mode: x_mode), y: x_addr, c: 0)) != -1)
3186 return !!ret;
3187
3188 if (nonoverlapping_memrefs_p (x, y: mem, loop_invariant: false))
3189 return false;
3190
3191 return rtx_refs_may_alias_p (x, mem, tbaa_p: false);
3192}
3193
3194/* Anti dependence: X is written after read in MEM takes place. */
3195
3196bool
3197anti_dependence (const_rtx mem, const_rtx x)
3198{
3199 return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3200 /*mem_canonicalized=*/false,
3201 /*x_canonicalized*/false, /*writep=*/false);
3202}
3203
3204/* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3205 Also, consider X in X_MODE (which might be from an enclosing
3206 STRICT_LOW_PART / ZERO_EXTRACT).
3207 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3208
3209bool
3210canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3211 const_rtx x, machine_mode x_mode, rtx x_addr)
3212{
3213 return write_dependence_p (mem, x, x_mode, x_addr,
3214 mem_canonicalized, /*x_canonicalized=*/true,
3215 /*writep=*/false);
3216}
3217
3218/* Output dependence: X is written after store in MEM takes place. */
3219
3220bool
3221output_dependence (const_rtx mem, const_rtx x)
3222{
3223 return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3224 /*mem_canonicalized=*/false,
3225 /*x_canonicalized*/false, /*writep=*/true);
3226}
3227
3228/* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3229 Also, consider X in X_MODE (which might be from an enclosing
3230 STRICT_LOW_PART / ZERO_EXTRACT).
3231 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3232
3233bool
3234canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3235 const_rtx x, machine_mode x_mode, rtx x_addr)
3236{
3237 return write_dependence_p (mem, x, x_mode, x_addr,
3238 mem_canonicalized, /*x_canonicalized=*/true,
3239 /*writep=*/true);
3240}
3241
3242
3243
3244/* Check whether X may be aliased with MEM. Don't do offset-based
3245 memory disambiguation & TBAA. */
3246bool
3247may_alias_p (const_rtx mem, const_rtx x)
3248{
3249 rtx x_addr, mem_addr;
3250
3251 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3252 return true;
3253
3254 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3255 This is used in epilogue deallocation functions. */
3256 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3257 return true;
3258 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3259 return true;
3260 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3261 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3262 return true;
3263
3264 x_addr = XEXP (x, 0);
3265 x_addr = get_addr (x: x_addr);
3266
3267 mem_addr = XEXP (mem, 0);
3268 mem_addr = get_addr (x: mem_addr);
3269
3270 /* Read-only memory is by definition never modified, and therefore can't
3271 conflict with anything. However, don't assume anything when AND
3272 addresses are involved and leave to the code below to determine
3273 dependence. We don't expect to find read-only set on MEM, but
3274 stupid user tricks can produce them, so don't die. */
3275 if (MEM_READONLY_P (x)
3276 && GET_CODE (x_addr) != AND
3277 && GET_CODE (mem_addr) != AND)
3278 return false;
3279
3280 /* If we have MEMs referring to different address spaces (which can
3281 potentially overlap), we cannot easily tell from the addresses
3282 whether the references overlap. */
3283 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3284 return true;
3285
3286 rtx x_base = find_base_term (x: x_addr);
3287 rtx mem_base = find_base_term (x: mem_addr);
3288 if (! base_alias_check (x: x_addr, x_base, y: mem_addr, y_base: mem_base,
3289 GET_MODE (x), GET_MODE (mem_addr)))
3290 return false;
3291
3292 if (nonoverlapping_memrefs_p (x: mem, y: x, loop_invariant: true))
3293 return false;
3294
3295 /* TBAA not valid for loop_invarint */
3296 return rtx_refs_may_alias_p (x, mem, tbaa_p: false);
3297}
3298
3299void
3300init_alias_target (void)
3301{
3302 int i;
3303
3304 if (!arg_base_value)
3305 arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3306
3307 memset (static_reg_base_value, c: 0, n: sizeof static_reg_base_value);
3308
3309 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3310 /* Check whether this register can hold an incoming pointer
3311 argument. FUNCTION_ARG_REGNO_P tests outgoing register
3312 numbers, so translate if necessary due to register windows. */
3313 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3314 && targetm.hard_regno_mode_ok (i, Pmode))
3315 static_reg_base_value[i] = arg_base_value;
3316
3317 /* RTL code is required to be consistent about whether it uses the
3318 stack pointer, the frame pointer or the argument pointer to
3319 access a given area of the frame. We can therefore use the
3320 base address to distinguish between the different areas. */
3321 static_reg_base_value[STACK_POINTER_REGNUM]
3322 = unique_base_value (UNIQUE_BASE_VALUE_SP);
3323 static_reg_base_value[ARG_POINTER_REGNUM]
3324 = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3325 static_reg_base_value[FRAME_POINTER_REGNUM]
3326 = unique_base_value (UNIQUE_BASE_VALUE_FP);
3327
3328 /* The above rules extend post-reload, with eliminations applying
3329 consistently to each of the three pointers. Cope with cases in
3330 which the frame pointer is eliminated to the hard frame pointer
3331 rather than the stack pointer. */
3332 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3333 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3334 = unique_base_value (UNIQUE_BASE_VALUE_HFP);
3335}
3336
3337/* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3338 to be memory reference. */
3339static bool memory_modified;
3340static void
3341memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3342{
3343 if (MEM_P (x))
3344 {
3345 if (anti_dependence (mem: x, x: (const_rtx)data) || output_dependence (mem: x, x: (const_rtx)data))
3346 memory_modified = true;
3347 }
3348}
3349
3350
3351/* Return true when INSN possibly modify memory contents of MEM
3352 (i.e. address can be modified). */
3353bool
3354memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3355{
3356 if (!INSN_P (insn))
3357 return false;
3358 /* Conservatively assume all non-readonly MEMs might be modified in
3359 calls. */
3360 if (CALL_P (insn))
3361 return true;
3362 memory_modified = false;
3363 note_stores (as_a<const rtx_insn *> (p: insn), memory_modified_1,
3364 CONST_CAST_RTX(mem));
3365 return memory_modified;
3366}
3367
3368/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3369 array. */
3370
3371void
3372init_alias_analysis (void)
3373{
3374 const bool frame_pointer_eliminated
3375 = reload_completed
3376 && !frame_pointer_needed
3377 && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3378 unsigned int maxreg = max_reg_num ();
3379 bool changed;
3380 int pass, i;
3381 unsigned int ui;
3382 rtx_insn *insn;
3383 rtx val;
3384 int rpo_cnt;
3385 int *rpo;
3386
3387 timevar_push (tv: TV_ALIAS_ANALYSIS);
3388
3389 vec_safe_grow_cleared (v&: reg_known_value, len: maxreg - FIRST_PSEUDO_REGISTER,
3390 exact: true);
3391 reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3392 bitmap_clear (reg_known_equiv_p);
3393
3394 /* If we have memory allocated from the previous run, use it. */
3395 if (old_reg_base_value)
3396 reg_base_value = old_reg_base_value;
3397
3398 if (reg_base_value)
3399 reg_base_value->truncate (size: 0);
3400
3401 vec_safe_grow_cleared (v&: reg_base_value, len: maxreg, exact: true);
3402
3403 new_reg_base_value = XNEWVEC (rtx, maxreg);
3404 reg_seen = sbitmap_alloc (maxreg);
3405
3406 /* The basic idea is that each pass through this loop will use the
3407 "constant" information from the previous pass to propagate alias
3408 information through another level of assignments.
3409
3410 The propagation is done on the CFG in reverse post-order, to propagate
3411 things forward as far as possible in each iteration.
3412
3413 This could get expensive if the assignment chains are long. Maybe
3414 we should throttle the number of iterations, possibly based on
3415 the optimization level or flag_expensive_optimizations.
3416
3417 We could propagate more information in the first pass by making use
3418 of DF_REG_DEF_COUNT to determine immediately that the alias information
3419 for a pseudo is "constant".
3420
3421 A program with an uninitialized variable can cause an infinite loop
3422 here. Instead of doing a full dataflow analysis to detect such problems
3423 we just cap the number of iterations for the loop.
3424
3425 The state of the arrays for the set chain in question does not matter
3426 since the program has undefined behavior. */
3427
3428 rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3429 rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3430
3431 pass = 0;
3432 do
3433 {
3434 /* Assume nothing will change this iteration of the loop. */
3435 changed = false;
3436
3437 /* We want to assign the same IDs each iteration of this loop, so
3438 start counting from one each iteration of the loop. */
3439 unique_id = 1;
3440
3441 /* We're at the start of the function each iteration through the
3442 loop, so we're copying arguments. */
3443 copying_arguments = true;
3444
3445 /* Wipe the potential alias information clean for this pass. */
3446 memset (s: new_reg_base_value, c: 0, n: maxreg * sizeof (rtx));
3447
3448 /* Wipe the reg_seen array clean. */
3449 bitmap_clear (reg_seen);
3450
3451 /* Initialize the alias information for this pass. */
3452 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3453 if (static_reg_base_value[i]
3454 /* Don't treat the hard frame pointer as special if we
3455 eliminated the frame pointer to the stack pointer. */
3456 && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3457 {
3458 new_reg_base_value[i] = static_reg_base_value[i];
3459 bitmap_set_bit (map: reg_seen, bitno: i);
3460 }
3461
3462 /* Walk the insns adding values to the new_reg_base_value array. */
3463 for (i = 0; i < rpo_cnt; i++)
3464 {
3465 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3466 FOR_BB_INSNS (bb, insn)
3467 {
3468 if (NONDEBUG_INSN_P (insn))
3469 {
3470 rtx note, set;
3471
3472 /* Treat the hard frame pointer as special unless we
3473 eliminated the frame pointer to the stack pointer. */
3474 if (!frame_pointer_eliminated
3475 && modified_in_p (hard_frame_pointer_rtx, insn))
3476 continue;
3477
3478 /* If this insn has a noalias note, process it, Otherwise,
3479 scan for sets. A simple set will have no side effects
3480 which could change the base value of any other register. */
3481 if (GET_CODE (PATTERN (insn)) == SET
3482 && REG_NOTES (insn) != 0
3483 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3484 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3485 else
3486 note_stores (insn, record_set, NULL);
3487
3488 set = single_set (insn);
3489
3490 if (set != 0
3491 && REG_P (SET_DEST (set))
3492 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3493 {
3494 unsigned int regno = REGNO (SET_DEST (set));
3495 rtx src = SET_SRC (set);
3496 rtx t;
3497
3498 note = find_reg_equal_equiv_note (insn);
3499 if (note && REG_NOTE_KIND (note) == REG_EQUAL
3500 && DF_REG_DEF_COUNT (regno) != 1)
3501 note = NULL_RTX;
3502
3503 poly_int64 offset;
3504 if (note != NULL_RTX
3505 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3506 && ! rtx_varies_p (XEXP (note, 0), 1)
3507 && ! reg_overlap_mentioned_p (SET_DEST (set),
3508 XEXP (note, 0)))
3509 {
3510 set_reg_known_value (regno, XEXP (note, 0));
3511 set_reg_known_equiv_p (regno,
3512 REG_NOTE_KIND (note) == REG_EQUIV);
3513 }
3514 else if (DF_REG_DEF_COUNT (regno) == 1
3515 && GET_CODE (src) == PLUS
3516 && REG_P (XEXP (src, 0))
3517 && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3518 && poly_int_rtx_p (XEXP (src, 1), res: &offset))
3519 {
3520 t = plus_constant (GET_MODE (src), t, offset);
3521 set_reg_known_value (regno, val: t);
3522 set_reg_known_equiv_p (regno, val: false);
3523 }
3524 else if (DF_REG_DEF_COUNT (regno) == 1
3525 && ! rtx_varies_p (src, 1))
3526 {
3527 set_reg_known_value (regno, val: src);
3528 set_reg_known_equiv_p (regno, val: false);
3529 }
3530 }
3531 }
3532 else if (NOTE_P (insn)
3533 && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3534 copying_arguments = false;
3535 }
3536 }
3537
3538 /* Now propagate values from new_reg_base_value to reg_base_value. */
3539 gcc_assert (maxreg == (unsigned int) max_reg_num ());
3540
3541 for (ui = 0; ui < maxreg; ui++)
3542 {
3543 if (new_reg_base_value[ui]
3544 && new_reg_base_value[ui] != (*reg_base_value)[ui]
3545 && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3546 {
3547 (*reg_base_value)[ui] = new_reg_base_value[ui];
3548 changed = true;
3549 }
3550 }
3551 }
3552 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3553 XDELETEVEC (rpo);
3554
3555 /* Fill in the remaining entries. */
3556 FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3557 {
3558 int regno = i + FIRST_PSEUDO_REGISTER;
3559 if (! val)
3560 set_reg_known_value (regno, val: regno_reg_rtx[regno]);
3561 }
3562
3563 /* Clean up. */
3564 free (ptr: new_reg_base_value);
3565 new_reg_base_value = 0;
3566 sbitmap_free (map: reg_seen);
3567 reg_seen = 0;
3568 timevar_pop (tv: TV_ALIAS_ANALYSIS);
3569}
3570
3571/* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3572 Special API for var-tracking pass purposes. */
3573
3574void
3575vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3576{
3577 (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3578}
3579
3580void
3581end_alias_analysis (void)
3582{
3583 old_reg_base_value = reg_base_value;
3584 vec_free (v&: reg_known_value);
3585 sbitmap_free (map: reg_known_equiv_p);
3586}
3587
3588void
3589dump_alias_stats_in_alias_c (FILE *s)
3590{
3591 fprintf (stream: s, format: " TBAA oracle: %llu disambiguations %llu queries\n"
3592 " %llu are in alias set 0\n"
3593 " %llu queries asked about the same object\n"
3594 " %llu queries asked about the same alias set\n"
3595 " %llu access volatile\n"
3596 " %llu are dependent in the DAG\n"
3597 " %llu are aritificially in conflict with void *\n",
3598 alias_stats.num_disambiguated,
3599 alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3600 + alias_stats.num_same_objects + alias_stats.num_volatile
3601 + alias_stats.num_dag + alias_stats.num_disambiguated
3602 + alias_stats.num_universal,
3603 alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3604 alias_stats.num_same_objects, alias_stats.num_volatile,
3605 alias_stats.num_dag, alias_stats.num_universal);
3606}
3607#include "gt-alias.h"
3608

source code of gcc/alias.cc