1 /* Alias analysis for GNU C
2 Copyright (C) 1997-2020 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
32 #include "gimple-ssa.h"
35 #include "fold-const.h"
38 #include "langhooks.h"
42 #include "ipa-utils.h"
44 /* The aliasing API provided here solves related but different problems:
46 Say there exists (in c)
60 Consider the four questions:
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?
67 The answer to these questions can be yes, yes, yes, and maybe.
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).
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.
82 The pass ipa-type-escape does this analysis for the types whose
83 instances do not escape across the compilation boundary.
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.
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:
99 struct S { int i; double d; };
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
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'.
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.
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. */
124 struct alias_set_hash
: int_hash
<int, INT_MIN
, INT_MIN
+ 1> {};
126 struct GTY(()) alias_set_entry
{
127 /* The alias set number, as stored in MEM_ALIAS_SET. */
128 alias_set_type alias_set
;
130 /* Nonzero if would have a child of zero: this effectively makes this
131 alias set the same as alias set zero. */
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. */
138 /* Nonzero if is_pointer or if one of childs have has_pointer set. */
141 /* The children of the alias set. These are not just the immediate
142 children, but, in fact, all descendants. So, if we have:
144 struct T { struct S s; float f; }
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
;
151 static int rtx_equal_for_memref_p (const_rtx
, const_rtx
);
152 static void record_set (rtx
, const_rtx
, void *);
153 static int base_alias_check (rtx
, rtx
, rtx
, rtx
, machine_mode
,
155 static rtx
find_base_value (rtx
);
156 static int mems_in_disjoint_alias_sets_p (const_rtx
, const_rtx
);
157 static alias_set_entry
*get_alias_set_entry (alias_set_type
);
158 static tree
decl_for_component_ref (tree
);
159 static int write_dependence_p (const_rtx
,
160 const_rtx
, machine_mode
, rtx
,
162 static int compare_base_symbol_refs (const_rtx
, const_rtx
);
164 static void memory_modified_1 (rtx
, const_rtx
, void *);
166 /* Query statistics for the different low-level disambiguators.
167 A high-level query may trigger multiple of them. */
170 unsigned long long num_alias_zero
;
171 unsigned long long num_same_alias_set
;
172 unsigned long long num_same_objects
;
173 unsigned long long num_volatile
;
174 unsigned long long num_dag
;
175 unsigned long long num_universal
;
176 unsigned long long num_disambiguated
;
180 /* Set up all info needed to perform alias analysis on memory references. */
182 /* Returns the size in bytes of the mode of X. */
183 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
185 /* Cap the number of passes we make over the insns propagating alias
186 information through set chains.
187 ??? 10 is a completely arbitrary choice. This should be based on the
188 maximum loop depth in the CFG, but we do not have this information
189 available (even if current_loops _is_ available). */
190 #define MAX_ALIAS_LOOP_PASSES 10
192 /* reg_base_value[N] gives an address to which register N is related.
193 If all sets after the first add or subtract to the current value
194 or otherwise modify it so it does not point to a different top level
195 object, reg_base_value[N] is equal to the address part of the source
198 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
199 expressions represent three types of base:
201 1. incoming arguments. There is just one ADDRESS to represent all
202 arguments, since we do not know at this level whether accesses
203 based on different arguments can alias. The ADDRESS has id 0.
205 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
206 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
207 Each of these rtxes has a separate ADDRESS associated with it,
208 each with a negative id.
210 GCC is (and is required to be) precise in which register it
211 chooses to access a particular region of stack. We can therefore
212 assume that accesses based on one of these rtxes do not alias
213 accesses based on another of these rtxes.
215 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
216 Each such piece of memory has a separate ADDRESS associated
217 with it, each with an id greater than 0.
219 Accesses based on one ADDRESS do not alias accesses based on other
220 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
221 alias globals either; the ADDRESSes have Pmode to indicate this.
222 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
225 static GTY(()) vec
<rtx
, va_gc
> *reg_base_value
;
226 static rtx
*new_reg_base_value
;
228 /* The single VOIDmode ADDRESS that represents all argument bases.
230 static GTY(()) rtx arg_base_value
;
232 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
233 static int unique_id
;
235 /* We preserve the copy of old array around to avoid amount of garbage
236 produced. About 8% of garbage produced were attributed to this
238 static GTY((deletable
)) vec
<rtx
, va_gc
> *old_reg_base_value
;
240 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
242 #define UNIQUE_BASE_VALUE_SP -1
243 #define UNIQUE_BASE_VALUE_ARGP -2
244 #define UNIQUE_BASE_VALUE_FP -3
245 #define UNIQUE_BASE_VALUE_HFP -4
247 #define static_reg_base_value \
248 (this_target_rtl->x_static_reg_base_value)
250 #define REG_BASE_VALUE(X) \
251 (REGNO (X) < vec_safe_length (reg_base_value) \
252 ? (*reg_base_value)[REGNO (X)] : 0)
254 /* Vector indexed by N giving the initial (unchanging) value known for
255 pseudo-register N. This vector is initialized in init_alias_analysis,
256 and does not change until end_alias_analysis is called. */
257 static GTY(()) vec
<rtx
, va_gc
> *reg_known_value
;
259 /* Vector recording for each reg_known_value whether it is due to a
260 REG_EQUIV note. Future passes (viz., reload) may replace the
261 pseudo with the equivalent expression and so we account for the
262 dependences that would be introduced if that happens.
264 The REG_EQUIV notes created in assign_parms may mention the arg
265 pointer, and there are explicit insns in the RTL that modify the
266 arg pointer. Thus we must ensure that such insns don't get
267 scheduled across each other because that would invalidate the
268 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
269 wrong, but solving the problem in the scheduler will likely give
270 better code, so we do it here. */
271 static sbitmap reg_known_equiv_p
;
273 /* True when scanning insns from the start of the rtl to the
274 NOTE_INSN_FUNCTION_BEG note. */
275 static bool copying_arguments
;
278 /* The splay-tree used to store the various alias set entries. */
279 static GTY (()) vec
<alias_set_entry
*, va_gc
> *alias_sets
;
281 /* Build a decomposed reference object for querying the alias-oracle
282 from the MEM rtx and store it in *REF.
283 Returns false if MEM is not suitable for the alias-oracle. */
286 ao_ref_from_mem (ao_ref
*ref
, const_rtx mem
)
288 tree expr
= MEM_EXPR (mem
);
294 ao_ref_init (ref
, expr
);
296 /* Get the base of the reference and see if we have to reject or
298 base
= ao_ref_base (ref
);
299 if (base
== NULL_TREE
)
302 /* The tree oracle doesn't like bases that are neither decls
303 nor indirect references of SSA names. */
305 || (TREE_CODE (base
) == MEM_REF
306 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
307 || (TREE_CODE (base
) == TARGET_MEM_REF
308 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)))
311 ref
->ref_alias_set
= MEM_ALIAS_SET (mem
);
313 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
314 is conservative, so trust it. */
315 if (!MEM_OFFSET_KNOWN_P (mem
)
316 || !MEM_SIZE_KNOWN_P (mem
))
319 /* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size
321 if (maybe_lt (MEM_OFFSET (mem
), 0)
322 || (ref
->max_size_known_p ()
323 && maybe_gt ((MEM_OFFSET (mem
) + MEM_SIZE (mem
)) * BITS_PER_UNIT
,
325 ref
->ref
= NULL_TREE
;
327 /* Refine size and offset we got from analyzing MEM_EXPR by using
328 MEM_SIZE and MEM_OFFSET. */
330 ref
->offset
+= MEM_OFFSET (mem
) * BITS_PER_UNIT
;
331 ref
->size
= MEM_SIZE (mem
) * BITS_PER_UNIT
;
333 /* The MEM may extend into adjacent fields, so adjust max_size if
335 if (ref
->max_size_known_p ())
336 ref
->max_size
= upper_bound (ref
->max_size
, ref
->size
);
338 /* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of
339 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
340 if (MEM_EXPR (mem
) != get_spill_slot_decl (false)
341 && (maybe_lt (ref
->offset
, 0)
342 || (DECL_P (ref
->base
)
343 && (DECL_SIZE (ref
->base
) == NULL_TREE
344 || !poly_int_tree_p (DECL_SIZE (ref
->base
))
345 || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref
->base
)),
346 ref
->offset
+ ref
->size
)))))
352 /* Query the alias-oracle on whether the two memory rtx X and MEM may
353 alias. If TBAA_P is set also apply TBAA. Returns true if the
354 two rtxen may alias, false otherwise. */
357 rtx_refs_may_alias_p (const_rtx x
, const_rtx mem
, bool tbaa_p
)
361 if (!ao_ref_from_mem (&ref1
, x
)
362 || !ao_ref_from_mem (&ref2
, mem
))
365 return refs_may_alias_p_1 (&ref1
, &ref2
,
367 && MEM_ALIAS_SET (x
) != 0
368 && MEM_ALIAS_SET (mem
) != 0);
371 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
372 such an entry, or NULL otherwise. */
374 static inline alias_set_entry
*
375 get_alias_set_entry (alias_set_type alias_set
)
377 return (*alias_sets
)[alias_set
];
380 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
381 the two MEMs cannot alias each other. */
384 mems_in_disjoint_alias_sets_p (const_rtx mem1
, const_rtx mem2
)
386 return (flag_strict_aliasing
387 && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
),
388 MEM_ALIAS_SET (mem2
)));
391 /* Return true if the first alias set is a subset of the second. */
394 alias_set_subset_of (alias_set_type set1
, alias_set_type set2
)
396 alias_set_entry
*ase2
;
398 /* Disable TBAA oracle with !flag_strict_aliasing. */
399 if (!flag_strict_aliasing
)
402 /* Everything is a subset of the "aliases everything" set. */
406 /* Check if set1 is a subset of set2. */
407 ase2
= get_alias_set_entry (set2
);
409 && (ase2
->has_zero_child
410 || (ase2
->children
&& ase2
->children
->get (set1
))))
413 /* As a special case we consider alias set of "void *" to be both subset
414 and superset of every alias set of a pointer. This extra symmetry does
415 not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
416 to return true on the following testcase:
419 char **ptr2=(char **)&ptr;
422 Additionally if a set contains universal pointer, we consider every pointer
423 to be a subset of it, but we do not represent this explicitely - doing so
424 would require us to update transitive closure each time we introduce new
425 pointer type. This makes aliasing_component_refs_p to return true
426 on the following testcase:
428 struct a {void *ptr;}
429 char **ptr = (char **)&a.ptr;
432 This makes void * truly universal pointer type. See pointer handling in
433 get_alias_set for more details. */
434 if (ase2
&& ase2
->has_pointer
)
436 alias_set_entry
*ase1
= get_alias_set_entry (set1
);
438 if (ase1
&& ase1
->is_pointer
)
440 alias_set_type voidptr_set
= TYPE_ALIAS_SET (ptr_type_node
);
441 /* If one is ptr_type_node and other is pointer, then we consider
442 them subset of each other. */
443 if (set1
== voidptr_set
|| set2
== voidptr_set
)
445 /* If SET2 contains universal pointer's alias set, then we consdier
446 every (non-universal) pointer. */
447 if (ase2
->children
&& set1
!= voidptr_set
448 && ase2
->children
->get (voidptr_set
))
455 /* Return 1 if the two specified alias sets may conflict. */
458 alias_sets_conflict_p (alias_set_type set1
, alias_set_type set2
)
460 alias_set_entry
*ase1
;
461 alias_set_entry
*ase2
;
464 if (alias_sets_must_conflict_p (set1
, set2
))
467 /* See if the first alias set is a subset of the second. */
468 ase1
= get_alias_set_entry (set1
);
470 && ase1
->children
&& ase1
->children
->get (set2
))
472 ++alias_stats
.num_dag
;
476 /* Now do the same, but with the alias sets reversed. */
477 ase2
= get_alias_set_entry (set2
);
479 && ase2
->children
&& ase2
->children
->get (set1
))
481 ++alias_stats
.num_dag
;
485 /* We want void * to be compatible with any other pointer without
486 really dropping it to alias set 0. Doing so would make it
487 compatible with all non-pointer types too.
489 This is not strictly necessary by the C/C++ language
490 standards, but avoids common type punning mistakes. In
491 addition to that, we need the existence of such universal
492 pointer to implement Fortran's C_PTR type (which is defined as
493 type compatible with all C pointers). */
494 if (ase1
&& ase2
&& ase1
->has_pointer
&& ase2
->has_pointer
)
496 alias_set_type voidptr_set
= TYPE_ALIAS_SET (ptr_type_node
);
498 /* If one of the sets corresponds to universal pointer,
499 we consider it to conflict with anything that is
500 or contains pointer. */
501 if (set1
== voidptr_set
|| set2
== voidptr_set
)
503 ++alias_stats
.num_universal
;
506 /* If one of sets is (non-universal) pointer and the other
507 contains universal pointer, we also get conflict. */
508 if (ase1
->is_pointer
&& set2
!= voidptr_set
509 && ase2
->children
&& ase2
->children
->get (voidptr_set
))
511 ++alias_stats
.num_universal
;
514 if (ase2
->is_pointer
&& set1
!= voidptr_set
515 && ase1
->children
&& ase1
->children
->get (voidptr_set
))
517 ++alias_stats
.num_universal
;
522 ++alias_stats
.num_disambiguated
;
524 /* The two alias sets are distinct and neither one is the
525 child of the other. Therefore, they cannot conflict. */
529 /* Return 1 if the two specified alias sets will always conflict. */
532 alias_sets_must_conflict_p (alias_set_type set1
, alias_set_type set2
)
534 /* Disable TBAA oracle with !flag_strict_aliasing. */
535 if (!flag_strict_aliasing
)
537 if (set1
== 0 || set2
== 0)
539 ++alias_stats
.num_alias_zero
;
544 ++alias_stats
.num_same_alias_set
;
551 /* Return 1 if any MEM object of type T1 will always conflict (using the
552 dependency routines in this file) with any MEM object of type T2.
553 This is used when allocating temporary storage. If T1 and/or T2 are
554 NULL_TREE, it means we know nothing about the storage. */
557 objects_must_conflict_p (tree t1
, tree t2
)
559 alias_set_type set1
, set2
;
561 /* If neither has a type specified, we don't know if they'll conflict
562 because we may be using them to store objects of various types, for
563 example the argument and local variables areas of inlined functions. */
564 if (t1
== 0 && t2
== 0)
567 /* If they are the same type, they must conflict. */
570 ++alias_stats
.num_same_objects
;
573 /* Likewise if both are volatile. */
574 if (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
))
576 ++alias_stats
.num_volatile
;
580 set1
= t1
? get_alias_set (t1
) : 0;
581 set2
= t2
? get_alias_set (t2
) : 0;
583 /* We can't use alias_sets_conflict_p because we must make sure
584 that every subtype of t1 will conflict with every subtype of
585 t2 for which a pair of subobjects of these respective subtypes
586 overlaps on the stack. */
587 return alias_sets_must_conflict_p (set1
, set2
);
590 /* Return the outermost parent of component present in the chain of
591 component references handled by get_inner_reference in T with the
593 - the component is non-addressable
594 or NULL_TREE if no such parent exists. In the former cases, the alias
595 set of this parent is the alias set that must be used for T itself. */
598 component_uses_parent_alias_set_from (const_tree t
)
600 const_tree found
= NULL_TREE
;
602 while (handled_component_p (t
))
604 switch (TREE_CODE (t
))
607 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
609 /* Permit type-punning when accessing a union, provided the access
610 is directly through the union. For example, this code does not
611 permit taking the address of a union member and then storing
612 through it. Even the type-punning allowed here is a GCC
613 extension, albeit a common and useful one; the C standard says
614 that such accesses have implementation-defined behavior. */
615 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t
, 0))) == UNION_TYPE
)
620 case ARRAY_RANGE_REF
:
621 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
630 case VIEW_CONVERT_EXPR
:
631 /* Bitfields and casts are never addressable. */
639 t
= TREE_OPERAND (t
, 0);
643 return TREE_OPERAND (found
, 0);
649 /* Return whether the pointer-type T effective for aliasing may
650 access everything and thus the reference has to be assigned
654 ref_all_alias_ptr_type_p (const_tree t
)
656 return (TREE_CODE (TREE_TYPE (t
)) == VOID_TYPE
657 || TYPE_REF_CAN_ALIAS_ALL (t
));
660 /* Return the alias set for the memory pointed to by T, which may be
661 either a type or an expression. Return -1 if there is nothing
662 special about dereferencing T. */
664 static alias_set_type
665 get_deref_alias_set_1 (tree t
)
667 /* All we care about is the type. */
671 /* If we have an INDIRECT_REF via a void pointer, we don't
672 know anything about what that might alias. Likewise if the
673 pointer is marked that way. */
674 if (ref_all_alias_ptr_type_p (t
))
680 /* Return the alias set for the memory pointed to by T, which may be
681 either a type or an expression. */
684 get_deref_alias_set (tree t
)
686 /* If we're not doing any alias analysis, just assume everything
687 aliases everything else. */
688 if (!flag_strict_aliasing
)
691 alias_set_type set
= get_deref_alias_set_1 (t
);
693 /* Fall back to the alias-set of the pointed-to type. */
698 set
= get_alias_set (TREE_TYPE (t
));
704 /* Return the pointer-type relevant for TBAA purposes from the
705 memory reference tree *T or NULL_TREE in which case *T is
706 adjusted to point to the outermost component reference that
707 can be used for assigning an alias set. */
710 reference_alias_ptr_type_1 (tree
*t
)
714 /* Get the base object of the reference. */
716 while (handled_component_p (inner
))
718 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
719 the type of any component references that wrap it to
720 determine the alias-set. */
721 if (TREE_CODE (inner
) == VIEW_CONVERT_EXPR
)
722 *t
= TREE_OPERAND (inner
, 0);
723 inner
= TREE_OPERAND (inner
, 0);
726 /* Handle pointer dereferences here, they can override the
728 if (INDIRECT_REF_P (inner
)
729 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 0))))
730 return TREE_TYPE (TREE_OPERAND (inner
, 0));
731 else if (TREE_CODE (inner
) == TARGET_MEM_REF
)
732 return TREE_TYPE (TMR_OFFSET (inner
));
733 else if (TREE_CODE (inner
) == MEM_REF
734 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 1))))
735 return TREE_TYPE (TREE_OPERAND (inner
, 1));
737 /* If the innermost reference is a MEM_REF that has a
738 conversion embedded treat it like a VIEW_CONVERT_EXPR above,
739 using the memory access type for determining the alias-set. */
740 if (TREE_CODE (inner
) == MEM_REF
741 && (TYPE_MAIN_VARIANT (TREE_TYPE (inner
))
743 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner
, 1))))))
744 return TREE_TYPE (TREE_OPERAND (inner
, 1));
746 /* Otherwise, pick up the outermost object that we could have
748 tree tem
= component_uses_parent_alias_set_from (*t
);
755 /* Return the pointer-type relevant for TBAA purposes from the
756 gimple memory reference tree T. This is the type to be used for
757 the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
758 and guarantees that get_alias_set will return the same alias
759 set for T and the replacement. */
762 reference_alias_ptr_type (tree t
)
764 /* If the frontend assigns this alias-set zero, preserve that. */
765 if (lang_hooks
.get_alias_set (t
) == 0)
766 return ptr_type_node
;
768 tree ptype
= reference_alias_ptr_type_1 (&t
);
769 /* If there is a given pointer type for aliasing purposes, return it. */
770 if (ptype
!= NULL_TREE
)
773 /* Otherwise build one from the outermost component reference we
775 if (TREE_CODE (t
) == MEM_REF
776 || TREE_CODE (t
) == TARGET_MEM_REF
)
777 return TREE_TYPE (TREE_OPERAND (t
, 1));
779 return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t
)));
782 /* Return whether the pointer-types T1 and T2 used to determine
783 two alias sets of two references will yield the same answer
784 from get_deref_alias_set. */
787 alias_ptr_types_compatible_p (tree t1
, tree t2
)
789 if (TYPE_MAIN_VARIANT (t1
) == TYPE_MAIN_VARIANT (t2
))
792 if (ref_all_alias_ptr_type_p (t1
)
793 || ref_all_alias_ptr_type_p (t2
))
796 /* This function originally abstracts from simply comparing
797 get_deref_alias_set so that we are sure this still computes
798 the same result after LTO type merging is applied.
799 When in LTO type merging is done we can actually do this compare.
802 return get_deref_alias_set (t1
) == get_deref_alias_set (t2
);
804 return (TYPE_MAIN_VARIANT (TREE_TYPE (t1
))
805 == TYPE_MAIN_VARIANT (TREE_TYPE (t2
)));
808 /* Create emptry alias set entry. */
811 init_alias_set_entry (alias_set_type set
)
813 alias_set_entry
*ase
= ggc_alloc
<alias_set_entry
> ();
814 ase
->alias_set
= set
;
815 ase
->children
= NULL
;
816 ase
->has_zero_child
= false;
817 ase
->is_pointer
= false;
818 ase
->has_pointer
= false;
819 gcc_checking_assert (!get_alias_set_entry (set
));
820 (*alias_sets
)[set
] = ase
;
824 /* Return the alias set for T, which may be either a type or an
825 expression. Call language-specific routine for help, if needed. */
828 get_alias_set (tree t
)
832 /* We cannot give up with -fno-strict-aliasing because we need to build
833 proper type representation for possible functions which are build with
834 -fstrict-aliasing. */
836 /* return 0 if this or its type is an error. */
837 if (t
== error_mark_node
839 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
842 /* We can be passed either an expression or a type. This and the
843 language-specific routine may make mutually-recursive calls to each other
844 to figure out what to do. At each juncture, we see if this is a tree
845 that the language may need to handle specially. First handle things that
849 /* Give the language a chance to do something with this tree
850 before we look at it. */
852 set
= lang_hooks
.get_alias_set (t
);
856 /* Get the alias pointer-type to use or the outermost object
857 that we could have a pointer to. */
858 tree ptype
= reference_alias_ptr_type_1 (&t
);
860 return get_deref_alias_set (ptype
);
862 /* If we've already determined the alias set for a decl, just return
863 it. This is necessary for C++ anonymous unions, whose component
864 variables don't look like union members (boo!). */
866 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
867 return MEM_ALIAS_SET (DECL_RTL (t
));
869 /* Now all we care about is the type. */
873 /* Variant qualifiers don't affect the alias set, so get the main
875 t
= TYPE_MAIN_VARIANT (t
);
877 if (AGGREGATE_TYPE_P (t
)
878 && TYPE_TYPELESS_STORAGE (t
))
881 /* Always use the canonical type as well. If this is a type that
882 requires structural comparisons to identify compatible types
883 use alias set zero. */
884 if (TYPE_STRUCTURAL_EQUALITY_P (t
))
886 /* Allow the language to specify another alias set for this
888 set
= lang_hooks
.get_alias_set (t
);
891 /* Handle structure type equality for pointer types, arrays and vectors.
892 This is easy to do, because the code bellow ignore canonical types on
893 these anyway. This is important for LTO, where TYPE_CANONICAL for
894 pointers cannot be meaningfuly computed by the frotnend. */
895 if (canonical_type_used_p (t
))
897 /* In LTO we set canonical types for all types where it makes
898 sense to do so. Double check we did not miss some type. */
899 gcc_checking_assert (!in_lto_p
|| !type_with_alias_set_p (t
));
905 t
= TYPE_CANONICAL (t
);
906 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t
));
909 /* If this is a type with a known alias set, return it. */
910 gcc_checking_assert (t
== TYPE_MAIN_VARIANT (t
));
911 if (TYPE_ALIAS_SET_KNOWN_P (t
))
912 return TYPE_ALIAS_SET (t
);
914 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
915 if (!COMPLETE_TYPE_P (t
))
917 /* For arrays with unknown size the conservative answer is the
918 alias set of the element type. */
919 if (TREE_CODE (t
) == ARRAY_TYPE
)
920 return get_alias_set (TREE_TYPE (t
));
922 /* But return zero as a conservative answer for incomplete types. */
926 /* See if the language has special handling for this type. */
927 set
= lang_hooks
.get_alias_set (t
);
931 /* There are no objects of FUNCTION_TYPE, so there's no point in
932 using up an alias set for them. (There are, of course, pointers
933 and references to functions, but that's different.) */
934 else if (TREE_CODE (t
) == FUNCTION_TYPE
|| TREE_CODE (t
) == METHOD_TYPE
)
937 /* Unless the language specifies otherwise, let vector types alias
938 their components. This avoids some nasty type punning issues in
939 normal usage. And indeed lets vectors be treated more like an
941 else if (TREE_CODE (t
) == VECTOR_TYPE
)
942 set
= get_alias_set (TREE_TYPE (t
));
944 /* Unless the language specifies otherwise, treat array types the
945 same as their components. This avoids the asymmetry we get
946 through recording the components. Consider accessing a
947 character(kind=1) through a reference to a character(kind=1)[1:1].
948 Or consider if we want to assign integer(kind=4)[0:D.1387] and
949 integer(kind=4)[4] the same alias set or not.
950 Just be pragmatic here and make sure the array and its element
951 type get the same alias set assigned. */
952 else if (TREE_CODE (t
) == ARRAY_TYPE
953 && (!TYPE_NONALIASED_COMPONENT (t
)
954 || TYPE_STRUCTURAL_EQUALITY_P (t
)))
955 set
= get_alias_set (TREE_TYPE (t
));
957 /* From the former common C and C++ langhook implementation:
959 Unfortunately, there is no canonical form of a pointer type.
960 In particular, if we have `typedef int I', then `int *', and
961 `I *' are different types. So, we have to pick a canonical
962 representative. We do this below.
964 Technically, this approach is actually more conservative that
965 it needs to be. In particular, `const int *' and `int *'
966 should be in different alias sets, according to the C and C++
967 standard, since their types are not the same, and so,
968 technically, an `int **' and `const int **' cannot point at
971 But, the standard is wrong. In particular, this code is
976 const int* const* cipp = ipp;
977 And, it doesn't make sense for that to be legal unless you
978 can dereference IPP and CIPP. So, we ignore cv-qualifiers on
979 the pointed-to types. This issue has been reported to the
982 For this reason go to canonical type of the unqalified pointer type.
983 Until GCC 6 this code set all pointers sets to have alias set of
984 ptr_type_node but that is a bad idea, because it prevents disabiguations
985 in between pointers. For Firefox this accounts about 20% of all
986 disambiguations in the program. */
987 else if (POINTER_TYPE_P (t
) && t
!= ptr_type_node
)
990 auto_vec
<bool, 8> reference
;
992 /* Unnest all pointers and references.
993 We also want to make pointer to array/vector equivalent to pointer to
994 its element (see the reasoning above). Skip all those types, too. */
995 for (p
= t
; POINTER_TYPE_P (p
)
996 || (TREE_CODE (p
) == ARRAY_TYPE
997 && (!TYPE_NONALIASED_COMPONENT (p
)
998 || !COMPLETE_TYPE_P (p
)
999 || TYPE_STRUCTURAL_EQUALITY_P (p
)))
1000 || TREE_CODE (p
) == VECTOR_TYPE
;
1003 /* Ada supports recusive pointers. Instead of doing recrusion check
1004 just give up once the preallocated space of 8 elements is up.
1005 In this case just punt to void * alias set. */
1006 if (reference
.length () == 8)
1011 if (TREE_CODE (p
) == REFERENCE_TYPE
)
1012 /* In LTO we want languages that use references to be compatible
1013 with languages that use pointers. */
1014 reference
.safe_push (true && !in_lto_p
);
1015 if (TREE_CODE (p
) == POINTER_TYPE
)
1016 reference
.safe_push (false);
1018 p
= TYPE_MAIN_VARIANT (p
);
1020 /* In LTO for C++ programs we can turn in complete types to complete
1021 using ODR name lookup. */
1022 if (in_lto_p
&& TYPE_STRUCTURAL_EQUALITY_P (p
) && odr_type_p (p
))
1024 p
= prevailing_odr_type (p
);
1025 gcc_checking_assert (TYPE_MAIN_VARIANT (p
) == p
);
1028 /* Make void * compatible with char * and also void **.
1029 Programs are commonly violating TBAA by this.
1031 We also make void * to conflict with every pointer
1032 (see record_component_aliases) and thus it is safe it to use it for
1033 pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1034 if (TREE_CODE (p
) == VOID_TYPE
|| TYPE_STRUCTURAL_EQUALITY_P (p
))
1035 set
= get_alias_set (ptr_type_node
);
1038 /* Rebuild pointer type starting from canonical types using
1039 unqualified pointers and references only. This way all such
1040 pointers will have the same alias set and will conflict with
1043 Most of time we already have pointers or references of a given type.
1044 If not we build new one just to be sure that if someone later
1045 (probably only middle-end can, as we should assign all alias
1046 classes only after finishing translation unit) builds the pointer
1047 type, the canonical type will match. */
1048 p
= TYPE_CANONICAL (p
);
1049 while (!reference
.is_empty ())
1051 if (reference
.pop ())
1052 p
= build_reference_type (p
);
1054 p
= build_pointer_type (p
);
1055 gcc_checking_assert (p
== TYPE_MAIN_VARIANT (p
));
1056 /* build_pointer_type should always return the canonical type.
1057 For LTO TYPE_CANOINCAL may be NULL, because we do not compute
1058 them. Be sure that frontends do not glob canonical types of
1059 pointers in unexpected way and that p == TYPE_CANONICAL (p)
1060 in all other cases. */
1061 gcc_checking_assert (!TYPE_CANONICAL (p
)
1062 || p
== TYPE_CANONICAL (p
));
1065 /* Assign the alias set to both p and t.
1066 We cannot call get_alias_set (p) here as that would trigger
1067 infinite recursion when p == t. In other cases it would just
1068 trigger unnecesary legwork of rebuilding the pointer again. */
1069 gcc_checking_assert (p
== TYPE_MAIN_VARIANT (p
));
1070 if (TYPE_ALIAS_SET_KNOWN_P (p
))
1071 set
= TYPE_ALIAS_SET (p
);
1074 set
= new_alias_set ();
1075 TYPE_ALIAS_SET (p
) = set
;
1079 /* Alias set of ptr_type_node is special and serve as universal pointer which
1080 is TBAA compatible with every other pointer type. Be sure we have the
1081 alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1082 of pointer types NULL. */
1083 else if (t
== ptr_type_node
)
1084 set
= new_alias_set ();
1086 /* Otherwise make a new alias set for this type. */
1089 /* Each canonical type gets its own alias set, so canonical types
1090 shouldn't form a tree. It doesn't really matter for types
1091 we handle specially above, so only check it where it possibly
1092 would result in a bogus alias set. */
1093 gcc_checking_assert (TYPE_CANONICAL (t
) == t
);
1095 set
= new_alias_set ();
1098 TYPE_ALIAS_SET (t
) = set
;
1100 /* If this is an aggregate type or a complex type, we must record any
1101 component aliasing information. */
1102 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
1103 record_component_aliases (t
);
1105 /* We treat pointer types specially in alias_set_subset_of. */
1106 if (POINTER_TYPE_P (t
) && set
)
1108 alias_set_entry
*ase
= get_alias_set_entry (set
);
1110 ase
= init_alias_set_entry (set
);
1111 ase
->is_pointer
= true;
1112 ase
->has_pointer
= true;
1118 /* Return a brand-new alias set. */
1121 new_alias_set (void)
1123 if (alias_sets
== 0)
1124 vec_safe_push (alias_sets
, (alias_set_entry
*) NULL
);
1125 vec_safe_push (alias_sets
, (alias_set_entry
*) NULL
);
1126 return alias_sets
->length () - 1;
1129 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1130 not everything that aliases SUPERSET also aliases SUBSET. For example,
1131 in C, a store to an `int' can alias a load of a structure containing an
1132 `int', and vice versa. But it can't alias a load of a 'double' member
1133 of the same structure. Here, the structure would be the SUPERSET and
1134 `int' the SUBSET. This relationship is also described in the comment at
1135 the beginning of this file.
1137 This function should be called only once per SUPERSET/SUBSET pair.
1139 It is illegal for SUPERSET to be zero; everything is implicitly a
1140 subset of alias set zero. */
1143 record_alias_subset (alias_set_type superset
, alias_set_type subset
)
1145 alias_set_entry
*superset_entry
;
1146 alias_set_entry
*subset_entry
;
1148 /* It is possible in complex type situations for both sets to be the same,
1149 in which case we can ignore this operation. */
1150 if (superset
== subset
)
1153 gcc_assert (superset
);
1155 superset_entry
= get_alias_set_entry (superset
);
1156 if (superset_entry
== 0)
1158 /* Create an entry for the SUPERSET, so that we have a place to
1159 attach the SUBSET. */
1160 superset_entry
= init_alias_set_entry (superset
);
1164 superset_entry
->has_zero_child
= 1;
1167 if (!superset_entry
->children
)
1168 superset_entry
->children
1169 = hash_map
<alias_set_hash
, int>::create_ggc (64);
1171 /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1172 already there we're done. */
1173 if (superset_entry
->children
->put (subset
, 0))
1176 subset_entry
= get_alias_set_entry (subset
);
1177 /* If there is an entry for the subset, enter all of its children
1178 (if they are not already present) as children of the SUPERSET. */
1181 if (subset_entry
->has_zero_child
)
1182 superset_entry
->has_zero_child
= true;
1183 if (subset_entry
->has_pointer
)
1184 superset_entry
->has_pointer
= true;
1186 if (subset_entry
->children
)
1188 hash_map
<alias_set_hash
, int>::iterator iter
1189 = subset_entry
->children
->begin ();
1190 for (; iter
!= subset_entry
->children
->end (); ++iter
)
1191 superset_entry
->children
->put ((*iter
).first
, (*iter
).second
);
1197 /* Record that component types of TYPE, if any, are part of SUPERSET for
1198 aliasing purposes. For record types, we only record component types
1199 for fields that are not marked non-addressable. For array types, we
1200 only record the component type if it is not marked non-aliased. */
1203 record_component_aliases (tree type
, alias_set_type superset
)
1210 switch (TREE_CODE (type
))
1214 case QUAL_UNION_TYPE
:
1216 /* LTO non-ODR type merging does not make any difference between
1217 component pointer types. We may have
1219 struct foo {int *a;};
1221 as TYPE_CANONICAL of
1223 struct bar {float *a;};
1225 Because accesses to int * and float * do not alias, we would get
1226 false negative when accessing the same memory location by
1227 float ** and bar *. We thus record the canonical type as:
1231 void * is special cased and works as a universal pointer type.
1232 Accesses to it conflicts with accesses to any other pointer
1234 bool void_pointers
= in_lto_p
1235 && (!odr_type_p (type
)
1236 || !odr_based_tbaa_p (type
));
1237 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= DECL_CHAIN (field
))
1238 if (TREE_CODE (field
) == FIELD_DECL
&& !DECL_NONADDRESSABLE_P (field
))
1240 tree t
= TREE_TYPE (field
);
1243 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1244 element type and that type has to be normalized to void *,
1245 too, in the case it is a pointer. */
1246 while (!canonical_type_used_p (t
) && !POINTER_TYPE_P (t
))
1248 gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t
));
1251 if (POINTER_TYPE_P (t
))
1253 else if (flag_checking
)
1254 gcc_checking_assert (get_alias_set (t
)
1255 == get_alias_set (TREE_TYPE (field
)));
1258 alias_set_type set
= get_alias_set (t
);
1259 record_alias_subset (superset
, set
);
1260 /* If the field has alias-set zero make sure to still record
1261 any componets of it. This makes sure that for
1268 in C++ even though 'B' has alias-set zero because
1269 TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1272 record_component_aliases (t
, superset
);
1278 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
1281 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1289 /* Record that component types of TYPE, if any, are part of that type for
1290 aliasing purposes. For record types, we only record component types
1291 for fields that are not marked non-addressable. For array types, we
1292 only record the component type if it is not marked non-aliased. */
1295 record_component_aliases (tree type
)
1297 alias_set_type superset
= get_alias_set (type
);
1298 record_component_aliases (type
, superset
);
1302 /* Allocate an alias set for use in storing and reading from the varargs
1305 static GTY(()) alias_set_type varargs_set
= -1;
1308 get_varargs_alias_set (void)
1311 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1312 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1313 consistently use the varargs alias set for loads from the varargs
1314 area. So don't use it anywhere. */
1317 if (varargs_set
== -1)
1318 varargs_set
= new_alias_set ();
1324 /* Likewise, but used for the fixed portions of the frame, e.g., register
1327 static GTY(()) alias_set_type frame_set
= -1;
1330 get_frame_alias_set (void)
1332 if (frame_set
== -1)
1333 frame_set
= new_alias_set ();
1338 /* Create a new, unique base with id ID. */
1341 unique_base_value (HOST_WIDE_INT id
)
1343 return gen_rtx_ADDRESS (Pmode
, id
);
1346 /* Return true if accesses based on any other base value cannot alias
1347 those based on X. */
1350 unique_base_value_p (rtx x
)
1352 return GET_CODE (x
) == ADDRESS
&& GET_MODE (x
) == Pmode
;
1355 /* Return true if X is known to be a base value. */
1358 known_base_value_p (rtx x
)
1360 switch (GET_CODE (x
))
1367 /* Arguments may or may not be bases; we don't know for sure. */
1368 return GET_MODE (x
) != VOIDmode
;
1375 /* Inside SRC, the source of a SET, find a base address. */
1378 find_base_value (rtx src
)
1381 scalar_int_mode int_mode
;
1383 #if defined (FIND_BASE_TERM)
1384 /* Try machine-dependent ways to find the base term. */
1385 src
= FIND_BASE_TERM (src
);
1388 switch (GET_CODE (src
))
1395 regno
= REGNO (src
);
1396 /* At the start of a function, argument registers have known base
1397 values which may be lost later. Returning an ADDRESS
1398 expression here allows optimization based on argument values
1399 even when the argument registers are used for other purposes. */
1400 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
1401 return new_reg_base_value
[regno
];
1403 /* If a pseudo has a known base value, return it. Do not do this
1404 for non-fixed hard regs since it can result in a circular
1405 dependency chain for registers which have values at function entry.
1407 The test above is not sufficient because the scheduler may move
1408 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1409 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
1410 && regno
< vec_safe_length (reg_base_value
))
1412 /* If we're inside init_alias_analysis, use new_reg_base_value
1413 to reduce the number of relaxation iterations. */
1414 if (new_reg_base_value
&& new_reg_base_value
[regno
]
1415 && DF_REG_DEF_COUNT (regno
) == 1)
1416 return new_reg_base_value
[regno
];
1418 if ((*reg_base_value
)[regno
])
1419 return (*reg_base_value
)[regno
];
1425 /* Check for an argument passed in memory. Only record in the
1426 copying-arguments block; it is too hard to track changes
1428 if (copying_arguments
1429 && (XEXP (src
, 0) == arg_pointer_rtx
1430 || (GET_CODE (XEXP (src
, 0)) == PLUS
1431 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
1432 return arg_base_value
;
1436 src
= XEXP (src
, 0);
1437 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
1445 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
1447 /* If either operand is a REG that is a known pointer, then it
1449 if (REG_P (src_0
) && REG_POINTER (src_0
))
1450 return find_base_value (src_0
);
1451 if (REG_P (src_1
) && REG_POINTER (src_1
))
1452 return find_base_value (src_1
);
1454 /* If either operand is a REG, then see if we already have
1455 a known value for it. */
1458 temp
= find_base_value (src_0
);
1465 temp
= find_base_value (src_1
);
1470 /* If either base is named object or a special address
1471 (like an argument or stack reference), then use it for the
1473 if (src_0
!= 0 && known_base_value_p (src_0
))
1476 if (src_1
!= 0 && known_base_value_p (src_1
))
1479 /* Guess which operand is the base address:
1480 If either operand is a symbol, then it is the base. If
1481 either operand is a CONST_INT, then the other is the base. */
1482 if (CONST_INT_P (src_1
) || CONSTANT_P (src_0
))
1483 return find_base_value (src_0
);
1484 else if (CONST_INT_P (src_0
) || CONSTANT_P (src_1
))
1485 return find_base_value (src_1
);
1491 /* The standard form is (lo_sum reg sym) so look only at the
1493 return find_base_value (XEXP (src
, 1));
1496 /* Look through aligning ANDs. And AND with zero or one with
1497 the LSB set isn't one (see for example PR92462). */
1498 if (CONST_INT_P (XEXP (src
, 1))
1499 && INTVAL (XEXP (src
, 1)) != 0
1500 && (INTVAL (XEXP (src
, 1)) & 1) == 0)
1501 return find_base_value (XEXP (src
, 0));
1505 /* As we do not know which address space the pointer is referring to, we can
1506 handle this only if the target does not support different pointer or
1507 address modes depending on the address space. */
1508 if (!target_default_pointer_address_modes_p ())
1510 if (!is_a
<scalar_int_mode
> (GET_MODE (src
), &int_mode
)
1511 || GET_MODE_PRECISION (int_mode
) < GET_MODE_PRECISION (Pmode
))
1521 return find_base_value (XEXP (src
, 0));
1524 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
1525 /* As we do not know which address space the pointer is referring to, we can
1526 handle this only if the target does not support different pointer or
1527 address modes depending on the address space. */
1528 if (!target_default_pointer_address_modes_p ())
1532 rtx temp
= find_base_value (XEXP (src
, 0));
1534 if (temp
!= 0 && CONSTANT_P (temp
))
1535 temp
= convert_memory_address (Pmode
, temp
);
1547 /* Called from init_alias_analysis indirectly through note_stores,
1548 or directly if DEST is a register with a REG_NOALIAS note attached.
1549 SET is null in the latter case. */
1551 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1552 register N has been set in this function. */
1553 static sbitmap reg_seen
;
1556 record_set (rtx dest
, const_rtx set
, void *data ATTRIBUTE_UNUSED
)
1565 regno
= REGNO (dest
);
1567 gcc_checking_assert (regno
< reg_base_value
->length ());
1569 n
= REG_NREGS (dest
);
1574 bitmap_set_bit (reg_seen
, regno
+ n
);
1575 new_reg_base_value
[regno
+ n
] = 0;
1582 /* A CLOBBER wipes out any old value but does not prevent a previously
1583 unset register from acquiring a base address (i.e. reg_seen is not
1585 if (GET_CODE (set
) == CLOBBER
)
1587 new_reg_base_value
[regno
] = 0;
1591 src
= SET_SRC (set
);
1595 /* There's a REG_NOALIAS note against DEST. */
1596 if (bitmap_bit_p (reg_seen
, regno
))
1598 new_reg_base_value
[regno
] = 0;
1601 bitmap_set_bit (reg_seen
, regno
);
1602 new_reg_base_value
[regno
] = unique_base_value (unique_id
++);
1606 /* If this is not the first set of REGNO, see whether the new value
1607 is related to the old one. There are two cases of interest:
1609 (1) The register might be assigned an entirely new value
1610 that has the same base term as the original set.
1612 (2) The set might be a simple self-modification that
1613 cannot change REGNO's base value.
1615 If neither case holds, reject the original base value as invalid.
1616 Note that the following situation is not detected:
1618 extern int x, y; int *p = &x; p += (&y-&x);
1620 ANSI C does not allow computing the difference of addresses
1621 of distinct top level objects. */
1622 if (new_reg_base_value
[regno
] != 0
1623 && find_base_value (src
) != new_reg_base_value
[regno
])
1624 switch (GET_CODE (src
))
1628 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1629 new_reg_base_value
[regno
] = 0;
1632 /* If the value we add in the PLUS is also a valid base value,
1633 this might be the actual base value, and the original value
1636 rtx other
= NULL_RTX
;
1638 if (XEXP (src
, 0) == dest
)
1639 other
= XEXP (src
, 1);
1640 else if (XEXP (src
, 1) == dest
)
1641 other
= XEXP (src
, 0);
1643 if (! other
|| find_base_value (other
))
1644 new_reg_base_value
[regno
] = 0;
1648 if (XEXP (src
, 0) != dest
|| !CONST_INT_P (XEXP (src
, 1)))
1649 new_reg_base_value
[regno
] = 0;
1652 new_reg_base_value
[regno
] = 0;
1655 /* If this is the first set of a register, record the value. */
1656 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1657 && ! bitmap_bit_p (reg_seen
, regno
) && new_reg_base_value
[regno
] == 0)
1658 new_reg_base_value
[regno
] = find_base_value (src
);
1660 bitmap_set_bit (reg_seen
, regno
);
1663 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1664 using hard registers with non-null REG_BASE_VALUE for renaming. */
1666 get_reg_base_value (unsigned int regno
)
1668 return (*reg_base_value
)[regno
];
1671 /* If a value is known for REGNO, return it. */
1674 get_reg_known_value (unsigned int regno
)
1676 if (regno
>= FIRST_PSEUDO_REGISTER
)
1678 regno
-= FIRST_PSEUDO_REGISTER
;
1679 if (regno
< vec_safe_length (reg_known_value
))
1680 return (*reg_known_value
)[regno
];
1688 set_reg_known_value (unsigned int regno
, rtx val
)
1690 if (regno
>= FIRST_PSEUDO_REGISTER
)
1692 regno
-= FIRST_PSEUDO_REGISTER
;
1693 if (regno
< vec_safe_length (reg_known_value
))
1694 (*reg_known_value
)[regno
] = val
;
1698 /* Similarly for reg_known_equiv_p. */
1701 get_reg_known_equiv_p (unsigned int regno
)
1703 if (regno
>= FIRST_PSEUDO_REGISTER
)
1705 regno
-= FIRST_PSEUDO_REGISTER
;
1706 if (regno
< vec_safe_length (reg_known_value
))
1707 return bitmap_bit_p (reg_known_equiv_p
, regno
);
1713 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1715 if (regno
>= FIRST_PSEUDO_REGISTER
)
1717 regno
-= FIRST_PSEUDO_REGISTER
;
1718 if (regno
< vec_safe_length (reg_known_value
))
1721 bitmap_set_bit (reg_known_equiv_p
, regno
);
1723 bitmap_clear_bit (reg_known_equiv_p
, regno
);
1729 /* Returns a canonical version of X, from the point of view alias
1730 analysis. (For example, if X is a MEM whose address is a register,
1731 and the register has a known value (say a SYMBOL_REF), then a MEM
1732 whose address is the SYMBOL_REF is returned.) */
1737 /* Recursively look for equivalences. */
1738 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1740 rtx t
= get_reg_known_value (REGNO (x
));
1744 return canon_rtx (t
);
1747 if (GET_CODE (x
) == PLUS
)
1749 rtx x0
= canon_rtx (XEXP (x
, 0));
1750 rtx x1
= canon_rtx (XEXP (x
, 1));
1752 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1753 return simplify_gen_binary (PLUS
, GET_MODE (x
), x0
, x1
);
1756 /* This gives us much better alias analysis when called from
1757 the loop optimizer. Note we want to leave the original
1758 MEM alone, but need to return the canonicalized MEM with
1759 all the flags with their original values. */
1761 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1766 /* Return 1 if X and Y are identical-looking rtx's.
1767 Expect that X and Y has been already canonicalized.
1769 We use the data in reg_known_value above to see if two registers with
1770 different numbers are, in fact, equivalent. */
1773 rtx_equal_for_memref_p (const_rtx x
, const_rtx y
)
1780 if (x
== 0 && y
== 0)
1782 if (x
== 0 || y
== 0)
1788 code
= GET_CODE (x
);
1789 /* Rtx's of different codes cannot be equal. */
1790 if (code
!= GET_CODE (y
))
1793 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1794 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1796 if (GET_MODE (x
) != GET_MODE (y
))
1799 /* Some RTL can be compared without a recursive examination. */
1803 return REGNO (x
) == REGNO (y
);
1806 return label_ref_label (x
) == label_ref_label (y
);
1809 return compare_base_symbol_refs (x
, y
) == 1;
1812 /* This is magic, don't go through canonicalization et al. */
1813 return rtx_equal_p (ENTRY_VALUE_EXP (x
), ENTRY_VALUE_EXP (y
));
1817 /* Pointer equality guarantees equality for these nodes. */
1824 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1826 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1827 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1828 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1829 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1830 /* For commutative operations, the RTX match if the operand match in any
1831 order. Also handle the simple binary and unary cases without a loop. */
1832 if (COMMUTATIVE_P (x
))
1834 rtx xop0
= canon_rtx (XEXP (x
, 0));
1835 rtx yop0
= canon_rtx (XEXP (y
, 0));
1836 rtx yop1
= canon_rtx (XEXP (y
, 1));
1838 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1839 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1840 || (rtx_equal_for_memref_p (xop0
, yop1
)
1841 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1843 else if (NON_COMMUTATIVE_P (x
))
1845 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1846 canon_rtx (XEXP (y
, 0)))
1847 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1848 canon_rtx (XEXP (y
, 1))));
1850 else if (UNARY_P (x
))
1851 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1852 canon_rtx (XEXP (y
, 0)));
1854 /* Compare the elements. If any pair of corresponding elements
1855 fail to match, return 0 for the whole things.
1857 Limit cases to types which actually appear in addresses. */
1859 fmt
= GET_RTX_FORMAT (code
);
1860 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1865 if (XINT (x
, i
) != XINT (y
, i
))
1870 if (maybe_ne (SUBREG_BYTE (x
), SUBREG_BYTE (y
)))
1875 /* Two vectors must have the same length. */
1876 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1879 /* And the corresponding elements must match. */
1880 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1881 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1882 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1887 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1888 canon_rtx (XEXP (y
, i
))) == 0)
1892 /* This can happen for asm operands. */
1894 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1898 /* This can happen for an asm which clobbers memory. */
1902 /* It is believed that rtx's at this level will never
1903 contain anything but integers and other rtx's,
1904 except for within LABEL_REFs and SYMBOL_REFs. */
1913 find_base_term (rtx x
, vec
<std::pair
<cselib_val
*,
1914 struct elt_loc_list
*> > &visited_vals
)
1917 struct elt_loc_list
*l
, *f
;
1919 scalar_int_mode int_mode
;
1921 #if defined (FIND_BASE_TERM)
1922 /* Try machine-dependent ways to find the base term. */
1923 x
= FIND_BASE_TERM (x
);
1926 switch (GET_CODE (x
))
1929 return REG_BASE_VALUE (x
);
1932 /* As we do not know which address space the pointer is referring to, we can
1933 handle this only if the target does not support different pointer or
1934 address modes depending on the address space. */
1935 if (!target_default_pointer_address_modes_p ())
1937 if (!is_a
<scalar_int_mode
> (GET_MODE (x
), &int_mode
)
1938 || GET_MODE_PRECISION (int_mode
) < GET_MODE_PRECISION (Pmode
))
1948 return find_base_term (XEXP (x
, 0), visited_vals
);
1951 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1952 /* As we do not know which address space the pointer is referring to, we can
1953 handle this only if the target does not support different pointer or
1954 address modes depending on the address space. */
1955 if (!target_default_pointer_address_modes_p ())
1959 rtx temp
= find_base_term (XEXP (x
, 0), visited_vals
);
1961 if (temp
!= 0 && CONSTANT_P (temp
))
1962 temp
= convert_memory_address (Pmode
, temp
);
1968 val
= CSELIB_VAL_PTR (x
);
1974 if (cselib_sp_based_value_p (val
))
1975 return static_reg_base_value
[STACK_POINTER_REGNUM
];
1978 /* Reset val->locs to avoid infinite recursion. */
1980 visited_vals
.safe_push (std::make_pair (val
, f
));
1983 for (l
= f
; l
; l
= l
->next
)
1984 if (GET_CODE (l
->loc
) == VALUE
1985 && CSELIB_VAL_PTR (l
->loc
)->locs
1986 && !CSELIB_VAL_PTR (l
->loc
)->locs
->next
1987 && CSELIB_VAL_PTR (l
->loc
)->locs
->loc
== x
)
1989 else if ((ret
= find_base_term (l
->loc
, visited_vals
)) != 0)
1995 /* The standard form is (lo_sum reg sym) so look only at the
1997 return find_base_term (XEXP (x
, 1), visited_vals
);
2001 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
2007 rtx tmp1
= XEXP (x
, 0);
2008 rtx tmp2
= XEXP (x
, 1);
2010 /* This is a little bit tricky since we have to determine which of
2011 the two operands represents the real base address. Otherwise this
2012 routine may return the index register instead of the base register.
2014 That may cause us to believe no aliasing was possible, when in
2015 fact aliasing is possible.
2017 We use a few simple tests to guess the base register. Additional
2018 tests can certainly be added. For example, if one of the operands
2019 is a shift or multiply, then it must be the index register and the
2020 other operand is the base register. */
2022 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
2023 return find_base_term (tmp2
, visited_vals
);
2025 /* If either operand is known to be a pointer, then prefer it
2026 to determine the base term. */
2027 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
2029 else if (REG_P (tmp2
) && REG_POINTER (tmp2
))
2030 std::swap (tmp1
, tmp2
);
2031 /* If second argument is constant which has base term, prefer it
2032 over variable tmp1. See PR64025. */
2033 else if (CONSTANT_P (tmp2
) && !CONST_INT_P (tmp2
))
2034 std::swap (tmp1
, tmp2
);
2036 /* Go ahead and find the base term for both operands. If either base
2037 term is from a pointer or is a named object or a special address
2038 (like an argument or stack reference), then use it for the
2040 rtx base
= find_base_term (tmp1
, visited_vals
);
2041 if (base
!= NULL_RTX
2042 && ((REG_P (tmp1
) && REG_POINTER (tmp1
))
2043 || known_base_value_p (base
)))
2045 base
= find_base_term (tmp2
, visited_vals
);
2046 if (base
!= NULL_RTX
2047 && ((REG_P (tmp2
) && REG_POINTER (tmp2
))
2048 || known_base_value_p (base
)))
2051 /* We could not determine which of the two operands was the
2052 base register and which was the index. So we can determine
2053 nothing from the base alias check. */
2058 /* Look through aligning ANDs. And AND with zero or one with
2059 the LSB set isn't one (see for example PR92462). */
2060 if (CONST_INT_P (XEXP (x
, 1))
2061 && INTVAL (XEXP (x
, 1)) != 0
2062 && (INTVAL (XEXP (x
, 1)) & 1) == 0)
2063 return find_base_term (XEXP (x
, 0), visited_vals
);
2075 /* Wrapper around the worker above which removes locs from visited VALUEs
2076 to avoid visiting them multiple times. We unwind that changes here. */
2079 find_base_term (rtx x
)
2081 auto_vec
<std::pair
<cselib_val
*, struct elt_loc_list
*>, 32> visited_vals
;
2082 rtx res
= find_base_term (x
, visited_vals
);
2083 for (unsigned i
= 0; i
< visited_vals
.length (); ++i
)
2084 visited_vals
[i
].first
->locs
= visited_vals
[i
].second
;
2088 /* Return true if accesses to address X may alias accesses based
2089 on the stack pointer. */
2092 may_be_sp_based_p (rtx x
)
2094 rtx base
= find_base_term (x
);
2095 return !base
|| base
== static_reg_base_value
[STACK_POINTER_REGNUM
];
2098 /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2099 if they refer to different objects and -1 if we cannot decide. */
2102 compare_base_decls (tree base1
, tree base2
)
2105 gcc_checking_assert (DECL_P (base1
) && DECL_P (base2
));
2109 /* If we have two register decls with register specification we
2110 cannot decide unless their assembler names are the same. */
2111 if (DECL_REGISTER (base1
)
2112 && DECL_REGISTER (base2
)
2113 && HAS_DECL_ASSEMBLER_NAME_P (base1
)
2114 && HAS_DECL_ASSEMBLER_NAME_P (base2
)
2115 && DECL_ASSEMBLER_NAME_SET_P (base1
)
2116 && DECL_ASSEMBLER_NAME_SET_P (base2
))
2118 if (DECL_ASSEMBLER_NAME_RAW (base1
) == DECL_ASSEMBLER_NAME_RAW (base2
))
2123 /* Declarations of non-automatic variables may have aliases. All other
2124 decls are unique. */
2125 if (!decl_in_symtab_p (base1
)
2126 || !decl_in_symtab_p (base2
))
2129 /* Don't cause symbols to be inserted by the act of checking. */
2130 symtab_node
*node1
= symtab_node::get (base1
);
2133 symtab_node
*node2
= symtab_node::get (base2
);
2137 ret
= node1
->equal_address_to (node2
, true);
2141 /* Same as compare_base_decls but for SYMBOL_REF. */
2144 compare_base_symbol_refs (const_rtx x_base
, const_rtx y_base
)
2146 tree x_decl
= SYMBOL_REF_DECL (x_base
);
2147 tree y_decl
= SYMBOL_REF_DECL (y_base
);
2148 bool binds_def
= true;
2150 if (XSTR (x_base
, 0) == XSTR (y_base
, 0))
2152 if (x_decl
&& y_decl
)
2153 return compare_base_decls (x_decl
, y_decl
);
2154 if (x_decl
|| y_decl
)
2158 std::swap (x_decl
, y_decl
);
2159 std::swap (x_base
, y_base
);
2161 /* We handle specially only section anchors and assume that other
2162 labels may overlap with user variables in an arbitrary way. */
2163 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base
))
2165 /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2166 to ignore CONST_DECLs because they are readonly. */
2168 || (!TREE_STATIC (x_decl
) && !TREE_PUBLIC (x_decl
)))
2171 symtab_node
*x_node
= symtab_node::get_create (x_decl
)
2172 ->ultimate_alias_target ();
2173 /* External variable cannot be in section anchor. */
2174 if (!x_node
->definition
)
2176 x_base
= XEXP (DECL_RTL (x_node
->decl
), 0);
2177 /* If not in anchor, we can disambiguate. */
2178 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base
))
2181 /* We have an alias of anchored variable. If it can be interposed;
2182 we must assume it may or may not alias its anchor. */
2183 binds_def
= decl_binds_to_current_def_p (x_decl
);
2185 /* If we have variable in section anchor, we can compare by offset. */
2186 if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base
)
2187 && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base
))
2189 if (SYMBOL_REF_BLOCK (x_base
) != SYMBOL_REF_BLOCK (y_base
))
2191 if (SYMBOL_REF_BLOCK_OFFSET (x_base
) == SYMBOL_REF_BLOCK_OFFSET (y_base
))
2192 return binds_def
? 1 : -1;
2193 if (SYMBOL_REF_ANCHOR_P (x_base
) != SYMBOL_REF_ANCHOR_P (y_base
))
2197 /* In general we assume that memory locations pointed to by different labels
2198 may overlap in undefined ways. */
2202 /* Return 0 if the addresses X and Y are known to point to different
2203 objects, 1 if they might be pointers to the same object. */
2206 base_alias_check (rtx x
, rtx x_base
, rtx y
, rtx y_base
,
2207 machine_mode x_mode
, machine_mode y_mode
)
2209 /* If the address itself has no known base see if a known equivalent
2210 value has one. If either address still has no known base, nothing
2211 is known about aliasing. */
2216 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
2219 x_base
= find_base_term (x_c
);
2227 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
2230 y_base
= find_base_term (y_c
);
2235 /* If the base addresses are equal nothing is known about aliasing. */
2236 if (rtx_equal_p (x_base
, y_base
))
2239 /* The base addresses are different expressions. If they are not accessed
2240 via AND, there is no conflict. We can bring knowledge of object
2241 alignment into play here. For example, on alpha, "char a, b;" can
2242 alias one another, though "char a; long b;" cannot. AND addresses may
2243 implicitly alias surrounding objects; i.e. unaligned access in DImode
2244 via AND address can alias all surrounding object types except those
2245 with aligment 8 or higher. */
2246 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
2248 if (GET_CODE (x
) == AND
2249 && (!CONST_INT_P (XEXP (x
, 1))
2250 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
2252 if (GET_CODE (y
) == AND
2253 && (!CONST_INT_P (XEXP (y
, 1))
2254 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
2257 /* Differing symbols not accessed via AND never alias. */
2258 if (GET_CODE (x_base
) == SYMBOL_REF
&& GET_CODE (y_base
) == SYMBOL_REF
)
2259 return compare_base_symbol_refs (x_base
, y_base
) != 0;
2261 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
2264 if (unique_base_value_p (x_base
) || unique_base_value_p (y_base
))
2270 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2271 (or equal to) that of V. */
2274 refs_newer_value_p (const_rtx expr
, rtx v
)
2276 int minuid
= CSELIB_VAL_PTR (v
)->uid
;
2277 subrtx_iterator::array_type array
;
2278 FOR_EACH_SUBRTX (iter
, array
, expr
, NONCONST
)
2279 if (GET_CODE (*iter
) == VALUE
&& CSELIB_VAL_PTR (*iter
)->uid
>= minuid
)
2284 /* Convert the address X into something we can use. This is done by returning
2285 it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2286 we call cselib to get a more useful rtx. */
2292 struct elt_loc_list
*l
;
2294 if (GET_CODE (x
) != VALUE
)
2296 if ((GET_CODE (x
) == PLUS
|| GET_CODE (x
) == MINUS
)
2297 && GET_CODE (XEXP (x
, 0)) == VALUE
2298 && CONST_SCALAR_INT_P (XEXP (x
, 1)))
2300 rtx op0
= get_addr (XEXP (x
, 0));
2301 if (op0
!= XEXP (x
, 0))
2304 if (GET_CODE (x
) == PLUS
2305 && poly_int_rtx_p (XEXP (x
, 1), &c
))
2306 return plus_constant (GET_MODE (x
), op0
, c
);
2307 return simplify_gen_binary (GET_CODE (x
), GET_MODE (x
),
2313 v
= CSELIB_VAL_PTR (x
);
2316 bool have_equivs
= cselib_have_permanent_equivalences ();
2318 v
= canonical_cselib_val (v
);
2319 for (l
= v
->locs
; l
; l
= l
->next
)
2320 if (CONSTANT_P (l
->loc
))
2322 for (l
= v
->locs
; l
; l
= l
->next
)
2323 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
)
2324 /* Avoid infinite recursion when potentially dealing with
2325 var-tracking artificial equivalences, by skipping the
2326 equivalences themselves, and not choosing expressions
2327 that refer to newer VALUEs. */
2329 || (GET_CODE (l
->loc
) != VALUE
2330 && !refs_newer_value_p (l
->loc
, x
))))
2334 for (l
= v
->locs
; l
; l
= l
->next
)
2336 || (GET_CODE (l
->loc
) != VALUE
2337 && !refs_newer_value_p (l
->loc
, x
)))
2339 /* Return the canonical value. */
2343 return v
->locs
->loc
;
2348 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2349 where SIZE is the size in bytes of the memory reference. If ADDR
2350 is not modified by the memory reference then ADDR is returned. */
2353 addr_side_effect_eval (rtx addr
, poly_int64 size
, int n_refs
)
2355 poly_int64 offset
= 0;
2357 switch (GET_CODE (addr
))
2360 offset
= (n_refs
+ 1) * size
;
2363 offset
= -(n_refs
+ 1) * size
;
2366 offset
= n_refs
* size
;
2369 offset
= -n_refs
* size
;
2376 addr
= plus_constant (GET_MODE (addr
), XEXP (addr
, 0), offset
);
2377 addr
= canon_rtx (addr
);
2382 /* Return TRUE if an object X sized at XSIZE bytes and another object
2383 Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2384 any of the sizes is zero, assume an overlap, otherwise use the
2385 absolute value of the sizes as the actual sizes. */
2388 offset_overlap_p (poly_int64 c
, poly_int64 xsize
, poly_int64 ysize
)
2390 if (known_eq (xsize
, 0) || known_eq (ysize
, 0))
2393 if (maybe_ge (c
, 0))
2394 return maybe_gt (maybe_lt (xsize
, 0) ? -xsize
: xsize
, c
);
2396 return maybe_gt (maybe_lt (ysize
, 0) ? -ysize
: ysize
, -c
);
2399 /* Return one if X and Y (memory addresses) reference the
2400 same location in memory or if the references overlap.
2401 Return zero if they do not overlap, else return
2402 minus one in which case they still might reference the same location.
2404 C is an offset accumulator. When
2405 C is nonzero, we are testing aliases between X and Y + C.
2406 XSIZE is the size in bytes of the X reference,
2407 similarly YSIZE is the size in bytes for Y.
2408 Expect that canon_rtx has been already called for X and Y.
2410 If XSIZE or YSIZE is zero, we do not know the amount of memory being
2411 referenced (the reference was BLKmode), so make the most pessimistic
2414 If XSIZE or YSIZE is negative, we may access memory outside the object
2415 being referenced as a side effect. This can happen when using AND to
2416 align memory references, as is done on the Alpha.
2418 Nice to notice that varying addresses cannot conflict with fp if no
2419 local variables had their addresses taken, but that's too hard now.
2421 ??? Contrary to the tree alias oracle this does not return
2422 one for X + non-constant and Y + non-constant when X and Y are equal.
2423 If that is fixed the TBAA hack for union type-punning can be removed. */
2426 memrefs_conflict_p (poly_int64 xsize
, rtx x
, poly_int64 ysize
, rtx y
,
2429 if (GET_CODE (x
) == VALUE
)
2433 struct elt_loc_list
*l
= NULL
;
2434 if (CSELIB_VAL_PTR (x
))
2435 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (x
))->locs
;
2437 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, y
))
2444 /* Don't call get_addr if y is the same VALUE. */
2448 if (GET_CODE (y
) == VALUE
)
2452 struct elt_loc_list
*l
= NULL
;
2453 if (CSELIB_VAL_PTR (y
))
2454 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (y
))->locs
;
2456 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, x
))
2463 /* Don't call get_addr if x is the same VALUE. */
2467 if (GET_CODE (x
) == HIGH
)
2469 else if (GET_CODE (x
) == LO_SUM
)
2472 x
= addr_side_effect_eval (x
, maybe_lt (xsize
, 0) ? -xsize
: xsize
, 0);
2473 if (GET_CODE (y
) == HIGH
)
2475 else if (GET_CODE (y
) == LO_SUM
)
2478 y
= addr_side_effect_eval (y
, maybe_lt (ysize
, 0) ? -ysize
: ysize
, 0);
2480 if (GET_CODE (x
) == SYMBOL_REF
&& GET_CODE (y
) == SYMBOL_REF
)
2482 int cmp
= compare_base_symbol_refs (x
,y
);
2484 /* If both decls are the same, decide by offsets. */
2486 return offset_overlap_p (c
, xsize
, ysize
);
2487 /* Assume a potential overlap for symbolic addresses that went
2488 through alignment adjustments (i.e., that have negative
2489 sizes), because we can't know how far they are from each
2491 if (maybe_lt (xsize
, 0) || maybe_lt (ysize
, 0))
2493 /* If decls are different or we know by offsets that there is no overlap,
2495 if (!cmp
|| !offset_overlap_p (c
, xsize
, ysize
))
2497 /* Decls may or may not be different and offsets overlap....*/
2500 else if (rtx_equal_for_memref_p (x
, y
))
2502 return offset_overlap_p (c
, xsize
, ysize
);
2505 /* This code used to check for conflicts involving stack references and
2506 globals but the base address alias code now handles these cases. */
2508 if (GET_CODE (x
) == PLUS
)
2510 /* The fact that X is canonicalized means that this
2511 PLUS rtx is canonicalized. */
2512 rtx x0
= XEXP (x
, 0);
2513 rtx x1
= XEXP (x
, 1);
2515 /* However, VALUEs might end up in different positions even in
2516 canonical PLUSes. Comparing their addresses is enough. */
2518 return memrefs_conflict_p (xsize
, x1
, ysize
, const0_rtx
, c
);
2520 return memrefs_conflict_p (xsize
, x0
, ysize
, const0_rtx
, c
);
2522 poly_int64 cx1
, cy1
;
2523 if (GET_CODE (y
) == PLUS
)
2525 /* The fact that Y is canonicalized means that this
2526 PLUS rtx is canonicalized. */
2527 rtx y0
= XEXP (y
, 0);
2528 rtx y1
= XEXP (y
, 1);
2531 return memrefs_conflict_p (xsize
, x1
, ysize
, y0
, c
);
2533 return memrefs_conflict_p (xsize
, x0
, ysize
, y1
, c
);
2535 if (rtx_equal_for_memref_p (x1
, y1
))
2536 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2537 if (rtx_equal_for_memref_p (x0
, y0
))
2538 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
2539 if (poly_int_rtx_p (x1
, &cx1
))
2541 if (poly_int_rtx_p (y1
, &cy1
))
2542 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
2545 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- cx1
);
2547 else if (poly_int_rtx_p (y1
, &cy1
))
2548 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ cy1
);
2552 else if (poly_int_rtx_p (x1
, &cx1
))
2553 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- cx1
);
2555 else if (GET_CODE (y
) == PLUS
)
2557 /* The fact that Y is canonicalized means that this
2558 PLUS rtx is canonicalized. */
2559 rtx y0
= XEXP (y
, 0);
2560 rtx y1
= XEXP (y
, 1);
2563 return memrefs_conflict_p (xsize
, const0_rtx
, ysize
, y1
, c
);
2565 return memrefs_conflict_p (xsize
, const0_rtx
, ysize
, y0
, c
);
2568 if (poly_int_rtx_p (y1
, &cy1
))
2569 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ cy1
);
2574 if (GET_CODE (x
) == GET_CODE (y
))
2575 switch (GET_CODE (x
))
2579 /* Handle cases where we expect the second operands to be the
2580 same, and check only whether the first operand would conflict
2583 rtx x1
= canon_rtx (XEXP (x
, 1));
2584 rtx y1
= canon_rtx (XEXP (y
, 1));
2585 if (! rtx_equal_for_memref_p (x1
, y1
))
2587 x0
= canon_rtx (XEXP (x
, 0));
2588 y0
= canon_rtx (XEXP (y
, 0));
2589 if (rtx_equal_for_memref_p (x0
, y0
))
2590 return offset_overlap_p (c
, xsize
, ysize
);
2592 /* Can't properly adjust our sizes. */
2594 if (!poly_int_rtx_p (x1
, &c1
)
2595 || !can_div_trunc_p (xsize
, c1
, &xsize
)
2596 || !can_div_trunc_p (ysize
, c1
, &ysize
)
2597 || !can_div_trunc_p (c
, c1
, &c
))
2599 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2606 /* Deal with alignment ANDs by adjusting offset and size so as to
2607 cover the maximum range, without taking any previously known
2608 alignment into account. Make a size negative after such an
2609 adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2610 assume a potential overlap, because they may end up in contiguous
2611 memory locations and the stricter-alignment access may span over
2613 if (GET_CODE (x
) == AND
&& CONST_INT_P (XEXP (x
, 1)))
2615 HOST_WIDE_INT sc
= INTVAL (XEXP (x
, 1));
2616 unsigned HOST_WIDE_INT uc
= sc
;
2617 if (sc
< 0 && pow2_or_zerop (-uc
))
2619 if (maybe_gt (xsize
, 0))
2621 if (maybe_ne (xsize
, 0))
2624 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2628 if (GET_CODE (y
) == AND
&& CONST_INT_P (XEXP (y
, 1)))
2630 HOST_WIDE_INT sc
= INTVAL (XEXP (y
, 1));
2631 unsigned HOST_WIDE_INT uc
= sc
;
2632 if (sc
< 0 && pow2_or_zerop (-uc
))
2634 if (maybe_gt (ysize
, 0))
2636 if (maybe_ne (ysize
, 0))
2639 return memrefs_conflict_p (xsize
, x
,
2640 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2647 if (poly_int_rtx_p (x
, &cx
) && poly_int_rtx_p (y
, &cy
))
2650 return offset_overlap_p (c
, xsize
, ysize
);
2653 if (GET_CODE (x
) == CONST
)
2655 if (GET_CODE (y
) == CONST
)
2656 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2657 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2659 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2662 if (GET_CODE (y
) == CONST
)
2663 return memrefs_conflict_p (xsize
, x
, ysize
,
2664 canon_rtx (XEXP (y
, 0)), c
);
2666 /* Assume a potential overlap for symbolic addresses that went
2667 through alignment adjustments (i.e., that have negative
2668 sizes), because we can't know how far they are from each
2671 return (maybe_lt (xsize
, 0)
2672 || maybe_lt (ysize
, 0)
2673 || offset_overlap_p (c
, xsize
, ysize
));
2681 /* Functions to compute memory dependencies.
2683 Since we process the insns in execution order, we can build tables
2684 to keep track of what registers are fixed (and not aliased), what registers
2685 are varying in known ways, and what registers are varying in unknown
2688 If both memory references are volatile, then there must always be a
2689 dependence between the two references, since their order cannot be
2690 changed. A volatile and non-volatile reference can be interchanged
2693 We also must allow AND addresses, because they may generate accesses
2694 outside the object being referenced. This is used to generate aligned
2695 addresses from unaligned addresses, for instance, the alpha
2696 storeqi_unaligned pattern. */
2698 /* Read dependence: X is read after read in MEM takes place. There can
2699 only be a dependence here if both reads are volatile, or if either is
2700 an explicit barrier. */
2703 read_dependence (const_rtx mem
, const_rtx x
)
2705 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2707 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2708 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2713 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2716 decl_for_component_ref (tree x
)
2720 x
= TREE_OPERAND (x
, 0);
2722 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2724 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
2727 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2728 for the offset of the field reference. *KNOWN_P says whether the
2732 adjust_offset_for_component_ref (tree x
, bool *known_p
,
2739 tree xoffset
= component_ref_field_offset (x
);
2740 tree field
= TREE_OPERAND (x
, 1);
2741 if (!poly_int_tree_p (xoffset
))
2747 poly_offset_int woffset
2748 = (wi::to_poly_offset (xoffset
)
2749 + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field
))
2750 >> LOG2_BITS_PER_UNIT
)
2752 if (!woffset
.to_shwi (offset
))
2758 x
= TREE_OPERAND (x
, 0);
2760 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2763 /* Return nonzero if we can determine the exprs corresponding to memrefs
2764 X and Y and they do not overlap.
2765 If LOOP_VARIANT is set, skip offset-based disambiguation */
2768 nonoverlapping_memrefs_p (const_rtx x
, const_rtx y
, bool loop_invariant
)
2770 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
2773 bool moffsetx_known_p
, moffsety_known_p
;
2774 poly_int64 moffsetx
= 0, moffsety
= 0;
2775 poly_int64 offsetx
= 0, offsety
= 0, sizex
, sizey
;
2777 /* Unless both have exprs, we can't tell anything. */
2778 if (exprx
== 0 || expry
== 0)
2781 /* For spill-slot accesses make sure we have valid offsets. */
2782 if ((exprx
== get_spill_slot_decl (false)
2783 && ! MEM_OFFSET_KNOWN_P (x
))
2784 || (expry
== get_spill_slot_decl (false)
2785 && ! MEM_OFFSET_KNOWN_P (y
)))
2788 /* If the field reference test failed, look at the DECLs involved. */
2789 moffsetx_known_p
= MEM_OFFSET_KNOWN_P (x
);
2790 if (moffsetx_known_p
)
2791 moffsetx
= MEM_OFFSET (x
);
2792 if (TREE_CODE (exprx
) == COMPONENT_REF
)
2794 tree t
= decl_for_component_ref (exprx
);
2797 adjust_offset_for_component_ref (exprx
, &moffsetx_known_p
, &moffsetx
);
2801 moffsety_known_p
= MEM_OFFSET_KNOWN_P (y
);
2802 if (moffsety_known_p
)
2803 moffsety
= MEM_OFFSET (y
);
2804 if (TREE_CODE (expry
) == COMPONENT_REF
)
2806 tree t
= decl_for_component_ref (expry
);
2809 adjust_offset_for_component_ref (expry
, &moffsety_known_p
, &moffsety
);
2813 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2816 /* If we refer to different gimple registers, or one gimple register
2817 and one non-gimple-register, we know they can't overlap. First,
2818 gimple registers don't have their addresses taken. Now, there
2819 could be more than one stack slot for (different versions of) the
2820 same gimple register, but we can presumably tell they don't
2821 overlap based on offsets from stack base addresses elsewhere.
2822 It's important that we don't proceed to DECL_RTL, because gimple
2823 registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2824 able to do anything about them since no SSA information will have
2825 remained to guide it. */
2826 if (is_gimple_reg (exprx
) || is_gimple_reg (expry
))
2827 return exprx
!= expry
2828 || (moffsetx_known_p
&& moffsety_known_p
2829 && MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
)
2830 && !offset_overlap_p (moffsety
- moffsetx
,
2831 MEM_SIZE (x
), MEM_SIZE (y
)));
2833 /* With invalid code we can end up storing into the constant pool.
2834 Bail out to avoid ICEing when creating RTL for this.
2835 See gfortran.dg/lto/20091028-2_0.f90. */
2836 if (TREE_CODE (exprx
) == CONST_DECL
2837 || TREE_CODE (expry
) == CONST_DECL
)
2840 /* If one decl is known to be a function or label in a function and
2841 the other is some kind of data, they can't overlap. */
2842 if ((TREE_CODE (exprx
) == FUNCTION_DECL
2843 || TREE_CODE (exprx
) == LABEL_DECL
)
2844 != (TREE_CODE (expry
) == FUNCTION_DECL
2845 || TREE_CODE (expry
) == LABEL_DECL
))
2848 /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2849 living in multiple places), we can't tell anything. Exception
2850 are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2851 if ((!DECL_RTL_SET_P (exprx
) && TREE_CODE (exprx
) != FUNCTION_DECL
)
2852 || (!DECL_RTL_SET_P (expry
) && TREE_CODE (expry
) != FUNCTION_DECL
))
2855 rtlx
= DECL_RTL (exprx
);
2856 rtly
= DECL_RTL (expry
);
2858 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2859 can't overlap unless they are the same because we never reuse that part
2860 of the stack frame used for locals for spilled pseudos. */
2861 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2862 && ! rtx_equal_p (rtlx
, rtly
))
2865 /* If we have MEMs referring to different address spaces (which can
2866 potentially overlap), we cannot easily tell from the addresses
2867 whether the references overlap. */
2868 if (MEM_P (rtlx
) && MEM_P (rtly
)
2869 && MEM_ADDR_SPACE (rtlx
) != MEM_ADDR_SPACE (rtly
))
2872 /* Get the base and offsets of both decls. If either is a register, we
2873 know both are and are the same, so use that as the base. The only
2874 we can avoid overlap is if we can deduce that they are nonoverlapping
2875 pieces of that decl, which is very rare. */
2876 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2877 basex
= strip_offset_and_add (basex
, &offsetx
);
2879 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2880 basey
= strip_offset_and_add (basey
, &offsety
);
2882 /* If the bases are different, we know they do not overlap if both
2883 are constants or if one is a constant and the other a pointer into the
2884 stack frame. Otherwise a different base means we can't tell if they
2886 if (compare_base_decls (exprx
, expry
) == 0)
2887 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2888 || (CONSTANT_P (basex
) && REG_P (basey
)
2889 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2890 || (CONSTANT_P (basey
) && REG_P (basex
)
2891 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2893 /* Offset based disambiguation not appropriate for loop invariant */
2897 /* Offset based disambiguation is OK even if we do not know that the
2898 declarations are necessarily different
2899 (i.e. compare_base_decls (exprx, expry) == -1) */
2901 sizex
= (!MEM_P (rtlx
) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx
)))
2902 : MEM_SIZE_KNOWN_P (rtlx
) ? MEM_SIZE (rtlx
)
2904 sizey
= (!MEM_P (rtly
) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly
)))
2905 : MEM_SIZE_KNOWN_P (rtly
) ? MEM_SIZE (rtly
)
2908 /* If we have an offset for either memref, it can update the values computed
2910 if (moffsetx_known_p
)
2911 offsetx
+= moffsetx
, sizex
-= moffsetx
;
2912 if (moffsety_known_p
)
2913 offsety
+= moffsety
, sizey
-= moffsety
;
2915 /* If a memref has both a size and an offset, we can use the smaller size.
2916 We can't do this if the offset isn't known because we must view this
2917 memref as being anywhere inside the DECL's MEM. */
2918 if (MEM_SIZE_KNOWN_P (x
) && moffsetx_known_p
)
2919 sizex
= MEM_SIZE (x
);
2920 if (MEM_SIZE_KNOWN_P (y
) && moffsety_known_p
)
2921 sizey
= MEM_SIZE (y
);
2923 return !ranges_maybe_overlap_p (offsetx
, sizex
, offsety
, sizey
);
2926 /* Helper for true_dependence and canon_true_dependence.
2927 Checks for true dependence: X is read after store in MEM takes place.
2929 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2930 NULL_RTX, and the canonical addresses of MEM and X are both computed
2931 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2933 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2935 Returns 1 if there is a true dependence, 0 otherwise. */
2938 true_dependence_1 (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
2939 const_rtx x
, rtx x_addr
, bool mem_canonicalized
)
2945 gcc_checking_assert (mem_canonicalized
? (mem_addr
!= NULL_RTX
)
2946 : (mem_addr
== NULL_RTX
&& x_addr
== NULL_RTX
));
2948 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2951 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2952 This is used in epilogue deallocation functions, and in cselib. */
2953 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2955 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2957 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2958 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2962 x_addr
= XEXP (x
, 0);
2963 x_addr
= get_addr (x_addr
);
2967 mem_addr
= XEXP (mem
, 0);
2968 if (mem_mode
== VOIDmode
)
2969 mem_mode
= GET_MODE (mem
);
2971 true_mem_addr
= get_addr (mem_addr
);
2973 /* Read-only memory is by definition never modified, and therefore can't
2974 conflict with anything. However, don't assume anything when AND
2975 addresses are involved and leave to the code below to determine
2976 dependence. We don't expect to find read-only set on MEM, but
2977 stupid user tricks can produce them, so don't die. */
2978 if (MEM_READONLY_P (x
)
2979 && GET_CODE (x_addr
) != AND
2980 && GET_CODE (true_mem_addr
) != AND
)
2983 /* If we have MEMs referring to different address spaces (which can
2984 potentially overlap), we cannot easily tell from the addresses
2985 whether the references overlap. */
2986 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2989 base
= find_base_term (x_addr
);
2990 if (base
&& (GET_CODE (base
) == LABEL_REF
2991 || (GET_CODE (base
) == SYMBOL_REF
2992 && CONSTANT_POOL_ADDRESS_P (base
))))
2995 rtx mem_base
= find_base_term (true_mem_addr
);
2996 if (! base_alias_check (x_addr
, base
, true_mem_addr
, mem_base
,
2997 GET_MODE (x
), mem_mode
))
3000 x_addr
= canon_rtx (x_addr
);
3001 if (!mem_canonicalized
)
3002 mem_addr
= canon_rtx (true_mem_addr
);
3004 if ((ret
= memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
3005 SIZE_FOR_MODE (x
), x_addr
, 0)) != -1)
3008 if (mems_in_disjoint_alias_sets_p (x
, mem
))
3011 if (nonoverlapping_memrefs_p (mem
, x
, false))
3014 return rtx_refs_may_alias_p (x
, mem
, true);
3017 /* True dependence: X is read after store in MEM takes place. */
3020 true_dependence (const_rtx mem
, machine_mode mem_mode
, const_rtx x
)
3022 return true_dependence_1 (mem
, mem_mode
, NULL_RTX
,
3023 x
, NULL_RTX
, /*mem_canonicalized=*/false);
3026 /* Canonical true dependence: X is read after store in MEM takes place.
3027 Variant of true_dependence which assumes MEM has already been
3028 canonicalized (hence we no longer do that here).
3029 The mem_addr argument has been added, since true_dependence_1 computed
3030 this value prior to canonicalizing. */
3033 canon_true_dependence (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
3034 const_rtx x
, rtx x_addr
)
3036 return true_dependence_1 (mem
, mem_mode
, mem_addr
,
3037 x
, x_addr
, /*mem_canonicalized=*/true);
3040 /* Returns nonzero if a write to X might alias a previous read from
3041 (or, if WRITEP is true, a write to) MEM.
3042 If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3043 and X_MODE the mode for that access.
3044 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3047 write_dependence_p (const_rtx mem
,
3048 const_rtx x
, machine_mode x_mode
, rtx x_addr
,
3049 bool mem_canonicalized
, bool x_canonicalized
, bool writep
)
3052 rtx true_mem_addr
, true_x_addr
;
3056 gcc_checking_assert (x_canonicalized
3057 ? (x_addr
!= NULL_RTX
3058 && (x_mode
!= VOIDmode
|| GET_MODE (x
) == VOIDmode
))
3059 : (x_addr
== NULL_RTX
&& x_mode
== VOIDmode
));
3061 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
3064 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3065 This is used in epilogue deallocation functions. */
3066 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
3068 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
3070 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
3071 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
3075 x_addr
= XEXP (x
, 0);
3076 true_x_addr
= get_addr (x_addr
);
3078 mem_addr
= XEXP (mem
, 0);
3079 true_mem_addr
= get_addr (mem_addr
);
3081 /* A read from read-only memory can't conflict with read-write memory.
3082 Don't assume anything when AND addresses are involved and leave to
3083 the code below to determine dependence. */
3085 && MEM_READONLY_P (mem
)
3086 && GET_CODE (true_x_addr
) != AND
3087 && GET_CODE (true_mem_addr
) != AND
)
3090 /* If we have MEMs referring to different address spaces (which can
3091 potentially overlap), we cannot easily tell from the addresses
3092 whether the references overlap. */
3093 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
3096 base
= find_base_term (true_mem_addr
);
3099 && (GET_CODE (base
) == LABEL_REF
3100 || (GET_CODE (base
) == SYMBOL_REF
3101 && CONSTANT_POOL_ADDRESS_P (base
))))
3104 rtx x_base
= find_base_term (true_x_addr
);
3105 if (! base_alias_check (true_x_addr
, x_base
, true_mem_addr
, base
,
3106 GET_MODE (x
), GET_MODE (mem
)))
3109 if (!x_canonicalized
)
3111 x_addr
= canon_rtx (true_x_addr
);
3112 x_mode
= GET_MODE (x
);
3114 if (!mem_canonicalized
)
3115 mem_addr
= canon_rtx (true_mem_addr
);
3117 if ((ret
= memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
3118 GET_MODE_SIZE (x_mode
), x_addr
, 0)) != -1)
3121 if (nonoverlapping_memrefs_p (x
, mem
, false))
3124 return rtx_refs_may_alias_p (x
, mem
, false);
3127 /* Anti dependence: X is written after read in MEM takes place. */
3130 anti_dependence (const_rtx mem
, const_rtx x
)
3132 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
3133 /*mem_canonicalized=*/false,
3134 /*x_canonicalized*/false, /*writep=*/false);
3137 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3138 Also, consider X in X_MODE (which might be from an enclosing
3139 STRICT_LOW_PART / ZERO_EXTRACT).
3140 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3143 canon_anti_dependence (const_rtx mem
, bool mem_canonicalized
,
3144 const_rtx x
, machine_mode x_mode
, rtx x_addr
)
3146 return write_dependence_p (mem
, x
, x_mode
, x_addr
,
3147 mem_canonicalized
, /*x_canonicalized=*/true,
3151 /* Output dependence: X is written after store in MEM takes place. */
3154 output_dependence (const_rtx mem
, const_rtx x
)
3156 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
3157 /*mem_canonicalized=*/false,
3158 /*x_canonicalized*/false, /*writep=*/true);
3161 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3162 Also, consider X in X_MODE (which might be from an enclosing
3163 STRICT_LOW_PART / ZERO_EXTRACT).
3164 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3167 canon_output_dependence (const_rtx mem
, bool mem_canonicalized
,
3168 const_rtx x
, machine_mode x_mode
, rtx x_addr
)
3170 return write_dependence_p (mem
, x
, x_mode
, x_addr
,
3171 mem_canonicalized
, /*x_canonicalized=*/true,
3177 /* Check whether X may be aliased with MEM. Don't do offset-based
3178 memory disambiguation & TBAA. */
3180 may_alias_p (const_rtx mem
, const_rtx x
)
3182 rtx x_addr
, mem_addr
;
3184 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
3187 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3188 This is used in epilogue deallocation functions. */
3189 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
3191 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
3193 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
3194 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
3197 x_addr
= XEXP (x
, 0);
3198 x_addr
= get_addr (x_addr
);
3200 mem_addr
= XEXP (mem
, 0);
3201 mem_addr
= get_addr (mem_addr
);
3203 /* Read-only memory is by definition never modified, and therefore can't
3204 conflict with anything. However, don't assume anything when AND
3205 addresses are involved and leave to the code below to determine
3206 dependence. We don't expect to find read-only set on MEM, but
3207 stupid user tricks can produce them, so don't die. */
3208 if (MEM_READONLY_P (x
)
3209 && GET_CODE (x_addr
) != AND
3210 && GET_CODE (mem_addr
) != AND
)
3213 /* If we have MEMs referring to different address spaces (which can
3214 potentially overlap), we cannot easily tell from the addresses
3215 whether the references overlap. */
3216 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
3219 rtx x_base
= find_base_term (x_addr
);
3220 rtx mem_base
= find_base_term (mem_addr
);
3221 if (! base_alias_check (x_addr
, x_base
, mem_addr
, mem_base
,
3222 GET_MODE (x
), GET_MODE (mem_addr
)))
3225 if (nonoverlapping_memrefs_p (mem
, x
, true))
3228 /* TBAA not valid for loop_invarint */
3229 return rtx_refs_may_alias_p (x
, mem
, false);
3233 init_alias_target (void)
3237 if (!arg_base_value
)
3238 arg_base_value
= gen_rtx_ADDRESS (VOIDmode
, 0);
3240 memset (static_reg_base_value
, 0, sizeof static_reg_base_value
);
3242 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3243 /* Check whether this register can hold an incoming pointer
3244 argument. FUNCTION_ARG_REGNO_P tests outgoing register
3245 numbers, so translate if necessary due to register windows. */
3246 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
3247 && targetm
.hard_regno_mode_ok (i
, Pmode
))
3248 static_reg_base_value
[i
] = arg_base_value
;
3250 /* RTL code is required to be consistent about whether it uses the
3251 stack pointer, the frame pointer or the argument pointer to
3252 access a given area of the frame. We can therefore use the
3253 base address to distinguish between the different areas. */
3254 static_reg_base_value
[STACK_POINTER_REGNUM
]
3255 = unique_base_value (UNIQUE_BASE_VALUE_SP
);
3256 static_reg_base_value
[ARG_POINTER_REGNUM
]
3257 = unique_base_value (UNIQUE_BASE_VALUE_ARGP
);
3258 static_reg_base_value
[FRAME_POINTER_REGNUM
]
3259 = unique_base_value (UNIQUE_BASE_VALUE_FP
);
3261 /* The above rules extend post-reload, with eliminations applying
3262 consistently to each of the three pointers. Cope with cases in
3263 which the frame pointer is eliminated to the hard frame pointer
3264 rather than the stack pointer. */
3265 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
3266 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
3267 = unique_base_value (UNIQUE_BASE_VALUE_HFP
);
3270 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3271 to be memory reference. */
3272 static bool memory_modified
;
3274 memory_modified_1 (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
3278 if (anti_dependence (x
, (const_rtx
)data
) || output_dependence (x
, (const_rtx
)data
))
3279 memory_modified
= true;
3284 /* Return true when INSN possibly modify memory contents of MEM
3285 (i.e. address can be modified). */
3287 memory_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
3291 /* Conservatively assume all non-readonly MEMs might be modified in
3295 memory_modified
= false;
3296 note_stores (as_a
<const rtx_insn
*> (insn
), memory_modified_1
,
3297 CONST_CAST_RTX(mem
));
3298 return memory_modified
;
3301 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3305 init_alias_analysis (void)
3307 unsigned int maxreg
= max_reg_num ();
3316 timevar_push (TV_ALIAS_ANALYSIS
);
3318 vec_safe_grow_cleared (reg_known_value
, maxreg
- FIRST_PSEUDO_REGISTER
);
3319 reg_known_equiv_p
= sbitmap_alloc (maxreg
- FIRST_PSEUDO_REGISTER
);
3320 bitmap_clear (reg_known_equiv_p
);
3322 /* If we have memory allocated from the previous run, use it. */
3323 if (old_reg_base_value
)
3324 reg_base_value
= old_reg_base_value
;
3327 reg_base_value
->truncate (0);
3329 vec_safe_grow_cleared (reg_base_value
, maxreg
);
3331 new_reg_base_value
= XNEWVEC (rtx
, maxreg
);
3332 reg_seen
= sbitmap_alloc (maxreg
);
3334 /* The basic idea is that each pass through this loop will use the
3335 "constant" information from the previous pass to propagate alias
3336 information through another level of assignments.
3338 The propagation is done on the CFG in reverse post-order, to propagate
3339 things forward as far as possible in each iteration.
3341 This could get expensive if the assignment chains are long. Maybe
3342 we should throttle the number of iterations, possibly based on
3343 the optimization level or flag_expensive_optimizations.
3345 We could propagate more information in the first pass by making use
3346 of DF_REG_DEF_COUNT to determine immediately that the alias information
3347 for a pseudo is "constant".
3349 A program with an uninitialized variable can cause an infinite loop
3350 here. Instead of doing a full dataflow analysis to detect such problems
3351 we just cap the number of iterations for the loop.
3353 The state of the arrays for the set chain in question does not matter
3354 since the program has undefined behavior. */
3356 rpo
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
3357 rpo_cnt
= pre_and_rev_post_order_compute (NULL
, rpo
, false);
3359 /* The prologue/epilogue insns are not threaded onto the
3360 insn chain until after reload has completed. Thus,
3361 there is no sense wasting time checking if INSN is in
3362 the prologue/epilogue until after reload has completed. */
3363 bool could_be_prologue_epilogue
= ((targetm
.have_prologue ()
3364 || targetm
.have_epilogue ())
3365 && reload_completed
);
3370 /* Assume nothing will change this iteration of the loop. */
3373 /* We want to assign the same IDs each iteration of this loop, so
3374 start counting from one each iteration of the loop. */
3377 /* We're at the start of the function each iteration through the
3378 loop, so we're copying arguments. */
3379 copying_arguments
= true;
3381 /* Wipe the potential alias information clean for this pass. */
3382 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
3384 /* Wipe the reg_seen array clean. */
3385 bitmap_clear (reg_seen
);
3387 /* Initialize the alias information for this pass. */
3388 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3389 if (static_reg_base_value
[i
]
3390 /* Don't treat the hard frame pointer as special if we
3391 eliminated the frame pointer to the stack pointer instead. */
3392 && !(i
== HARD_FRAME_POINTER_REGNUM
3394 && !frame_pointer_needed
3395 && targetm
.can_eliminate (FRAME_POINTER_REGNUM
,
3396 STACK_POINTER_REGNUM
)))
3398 new_reg_base_value
[i
] = static_reg_base_value
[i
];
3399 bitmap_set_bit (reg_seen
, i
);
3402 /* Walk the insns adding values to the new_reg_base_value array. */
3403 for (i
= 0; i
< rpo_cnt
; i
++)
3405 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, rpo
[i
]);
3406 FOR_BB_INSNS (bb
, insn
)
3408 if (NONDEBUG_INSN_P (insn
))
3412 if (could_be_prologue_epilogue
3413 && prologue_epilogue_contains (insn
))
3416 /* If this insn has a noalias note, process it, Otherwise,
3417 scan for sets. A simple set will have no side effects
3418 which could change the base value of any other register. */
3420 if (GET_CODE (PATTERN (insn
)) == SET
3421 && REG_NOTES (insn
) != 0
3422 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
3423 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
3425 note_stores (insn
, record_set
, NULL
);
3427 set
= single_set (insn
);
3430 && REG_P (SET_DEST (set
))
3431 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
3433 unsigned int regno
= REGNO (SET_DEST (set
));
3434 rtx src
= SET_SRC (set
);
3437 note
= find_reg_equal_equiv_note (insn
);
3438 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
3439 && DF_REG_DEF_COUNT (regno
) != 1)
3443 if (note
!= NULL_RTX
3444 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
3445 && ! rtx_varies_p (XEXP (note
, 0), 1)
3446 && ! reg_overlap_mentioned_p (SET_DEST (set
),
3449 set_reg_known_value (regno
, XEXP (note
, 0));
3450 set_reg_known_equiv_p (regno
,
3451 REG_NOTE_KIND (note
) == REG_EQUIV
);
3453 else if (DF_REG_DEF_COUNT (regno
) == 1
3454 && GET_CODE (src
) == PLUS
3455 && REG_P (XEXP (src
, 0))
3456 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
3457 && poly_int_rtx_p (XEXP (src
, 1), &offset
))
3459 t
= plus_constant (GET_MODE (src
), t
, offset
);
3460 set_reg_known_value (regno
, t
);
3461 set_reg_known_equiv_p (regno
, false);
3463 else if (DF_REG_DEF_COUNT (regno
) == 1
3464 && ! rtx_varies_p (src
, 1))
3466 set_reg_known_value (regno
, src
);
3467 set_reg_known_equiv_p (regno
, false);
3471 else if (NOTE_P (insn
)
3472 && NOTE_KIND (insn
) == NOTE_INSN_FUNCTION_BEG
)
3473 copying_arguments
= false;
3477 /* Now propagate values from new_reg_base_value to reg_base_value. */
3478 gcc_assert (maxreg
== (unsigned int) max_reg_num ());
3480 for (ui
= 0; ui
< maxreg
; ui
++)
3482 if (new_reg_base_value
[ui
]
3483 && new_reg_base_value
[ui
] != (*reg_base_value
)[ui
]
3484 && ! rtx_equal_p (new_reg_base_value
[ui
], (*reg_base_value
)[ui
]))
3486 (*reg_base_value
)[ui
] = new_reg_base_value
[ui
];
3491 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
3494 /* Fill in the remaining entries. */
3495 FOR_EACH_VEC_ELT (*reg_known_value
, i
, val
)
3497 int regno
= i
+ FIRST_PSEUDO_REGISTER
;
3499 set_reg_known_value (regno
, regno_reg_rtx
[regno
]);
3503 free (new_reg_base_value
);
3504 new_reg_base_value
= 0;
3505 sbitmap_free (reg_seen
);
3507 timevar_pop (TV_ALIAS_ANALYSIS
);
3510 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3511 Special API for var-tracking pass purposes. */
3514 vt_equate_reg_base_value (const_rtx reg1
, const_rtx reg2
)
3516 (*reg_base_value
)[REGNO (reg1
)] = REG_BASE_VALUE (reg2
);
3520 end_alias_analysis (void)
3522 old_reg_base_value
= reg_base_value
;
3523 vec_free (reg_known_value
);
3524 sbitmap_free (reg_known_equiv_p
);
3528 dump_alias_stats_in_alias_c (FILE *s
)
3530 fprintf (s
, " TBAA oracle: %llu disambiguations %llu queries\n"
3531 " %llu are in alias set 0\n"
3532 " %llu queries asked about the same object\n"
3533 " %llu queries asked about the same alias set\n"
3534 " %llu access volatile\n"
3535 " %llu are dependent in the DAG\n"
3536 " %llu are aritificially in conflict with void *\n",
3537 alias_stats
.num_disambiguated
,
3538 alias_stats
.num_alias_zero
+ alias_stats
.num_same_alias_set
3539 + alias_stats
.num_same_objects
+ alias_stats
.num_volatile
3540 + alias_stats
.num_dag
+ alias_stats
.num_disambiguated
3541 + alias_stats
.num_universal
,
3542 alias_stats
.num_alias_zero
, alias_stats
.num_same_alias_set
,
3543 alias_stats
.num_same_objects
, alias_stats
.num_volatile
,
3544 alias_stats
.num_dag
, alias_stats
.num_universal
);
3546 #include "gt-alias.h"