1 /* Alias analysis for GNU C
2 Copyright (C) 1997-2024 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 compare_base_symbol_refs (const_rtx
, const_rtx
,
152 HOST_WIDE_INT
* = NULL
);
154 /* Query statistics for the different low-level disambiguators.
155 A high-level query may trigger multiple of them. */
158 unsigned long long num_alias_zero
;
159 unsigned long long num_same_alias_set
;
160 unsigned long long num_same_objects
;
161 unsigned long long num_volatile
;
162 unsigned long long num_dag
;
163 unsigned long long num_universal
;
164 unsigned long long num_disambiguated
;
168 /* Set up all info needed to perform alias analysis on memory references. */
170 /* Returns the size in bytes of the mode of X. */
171 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
173 /* Cap the number of passes we make over the insns propagating alias
174 information through set chains.
175 ??? 10 is a completely arbitrary choice. This should be based on the
176 maximum loop depth in the CFG, but we do not have this information
177 available (even if current_loops _is_ available). */
178 #define MAX_ALIAS_LOOP_PASSES 10
180 /* reg_base_value[N] gives an address to which register N is related.
181 If all sets after the first add or subtract to the current value
182 or otherwise modify it so it does not point to a different top level
183 object, reg_base_value[N] is equal to the address part of the source
186 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
187 expressions represent three types of base:
189 1. incoming arguments. There is just one ADDRESS to represent all
190 arguments, since we do not know at this level whether accesses
191 based on different arguments can alias. The ADDRESS has id 0.
193 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
194 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
195 Each of these rtxes has a separate ADDRESS associated with it,
196 each with a negative id.
198 GCC is (and is required to be) precise in which register it
199 chooses to access a particular region of stack. We can therefore
200 assume that accesses based on one of these rtxes do not alias
201 accesses based on another of these rtxes.
203 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
204 Each such piece of memory has a separate ADDRESS associated
205 with it, each with an id greater than 0.
207 Accesses based on one ADDRESS do not alias accesses based on other
208 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
209 alias globals either; the ADDRESSes have Pmode to indicate this.
210 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
213 static GTY(()) vec
<rtx
, va_gc
> *reg_base_value
;
214 static rtx
*new_reg_base_value
;
216 /* The single VOIDmode ADDRESS that represents all argument bases.
218 static GTY(()) rtx arg_base_value
;
220 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
221 static int unique_id
;
223 /* We preserve the copy of old array around to avoid amount of garbage
224 produced. About 8% of garbage produced were attributed to this
226 static GTY((deletable
)) vec
<rtx
, va_gc
> *old_reg_base_value
;
228 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
230 #define UNIQUE_BASE_VALUE_SP -1
231 #define UNIQUE_BASE_VALUE_ARGP -2
232 #define UNIQUE_BASE_VALUE_FP -3
233 #define UNIQUE_BASE_VALUE_HFP -4
235 #define static_reg_base_value \
236 (this_target_rtl->x_static_reg_base_value)
238 #define REG_BASE_VALUE(X) \
239 (REGNO (X) < vec_safe_length (reg_base_value) \
240 ? (*reg_base_value)[REGNO (X)] : 0)
242 /* Vector indexed by N giving the initial (unchanging) value known for
243 pseudo-register N. This vector is initialized in init_alias_analysis,
244 and does not change until end_alias_analysis is called. */
245 static GTY(()) vec
<rtx
, va_gc
> *reg_known_value
;
247 /* Vector recording for each reg_known_value whether it is due to a
248 REG_EQUIV note. Future passes (viz., reload) may replace the
249 pseudo with the equivalent expression and so we account for the
250 dependences that would be introduced if that happens.
252 The REG_EQUIV notes created in assign_parms may mention the arg
253 pointer, and there are explicit insns in the RTL that modify the
254 arg pointer. Thus we must ensure that such insns don't get
255 scheduled across each other because that would invalidate the
256 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
257 wrong, but solving the problem in the scheduler will likely give
258 better code, so we do it here. */
259 static sbitmap reg_known_equiv_p
;
261 /* True when scanning insns from the start of the rtl to the
262 NOTE_INSN_FUNCTION_BEG note. */
263 static bool copying_arguments
;
266 /* The splay-tree used to store the various alias set entries. */
267 static GTY (()) vec
<alias_set_entry
*, va_gc
> *alias_sets
;
269 /* Build a decomposed reference object for querying the alias-oracle
270 from the MEM rtx and store it in *REF.
271 Returns false if MEM is not suitable for the alias-oracle. */
274 ao_ref_from_mem (ao_ref
*ref
, const_rtx mem
)
276 tree expr
= MEM_EXPR (mem
);
282 ao_ref_init (ref
, expr
);
284 /* Get the base of the reference and see if we have to reject or
286 base
= ao_ref_base (ref
);
287 if (base
== NULL_TREE
)
290 /* The tree oracle doesn't like bases that are neither decls
291 nor indirect references of SSA names. */
293 || (TREE_CODE (base
) == MEM_REF
294 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
295 || (TREE_CODE (base
) == TARGET_MEM_REF
296 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)))
299 ref
->ref_alias_set
= MEM_ALIAS_SET (mem
);
301 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
302 is conservative, so trust it. */
303 if (!MEM_OFFSET_KNOWN_P (mem
)
304 || !MEM_SIZE_KNOWN_P (mem
))
307 /* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size
309 if (maybe_lt (MEM_OFFSET (mem
), 0)
310 || (ref
->max_size_known_p ()
311 && maybe_gt ((MEM_OFFSET (mem
) + MEM_SIZE (mem
)) * BITS_PER_UNIT
,
313 ref
->ref
= NULL_TREE
;
315 /* Refine size and offset we got from analyzing MEM_EXPR by using
316 MEM_SIZE and MEM_OFFSET. */
318 ref
->offset
+= MEM_OFFSET (mem
) * BITS_PER_UNIT
;
319 ref
->size
= MEM_SIZE (mem
) * BITS_PER_UNIT
;
321 /* The MEM may extend into adjacent fields, so adjust max_size if
323 if (ref
->max_size_known_p ())
324 ref
->max_size
= upper_bound (ref
->max_size
, ref
->size
);
326 /* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of
327 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
328 if (MEM_EXPR (mem
) != get_spill_slot_decl (false)
329 && (maybe_lt (ref
->offset
, 0)
330 || (DECL_P (ref
->base
)
331 && (DECL_SIZE (ref
->base
) == NULL_TREE
332 || !poly_int_tree_p (DECL_SIZE (ref
->base
))
333 || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref
->base
)),
334 ref
->offset
+ ref
->size
)))))
340 /* Query the alias-oracle on whether the two memory rtx X and MEM may
341 alias. If TBAA_P is set also apply TBAA. Returns true if the
342 two rtxen may alias, false otherwise. */
345 rtx_refs_may_alias_p (const_rtx x
, const_rtx mem
, bool tbaa_p
)
349 if (!ao_ref_from_mem (&ref1
, x
)
350 || !ao_ref_from_mem (&ref2
, mem
))
353 return refs_may_alias_p_1 (&ref1
, &ref2
,
355 && MEM_ALIAS_SET (x
) != 0
356 && MEM_ALIAS_SET (mem
) != 0);
359 /* Return true if the ref EARLIER behaves the same as LATER with respect
360 to TBAA for every memory reference that might follow LATER. */
363 refs_same_for_tbaa_p (tree earlier
, tree later
)
365 ao_ref earlier_ref
, later_ref
;
366 ao_ref_init (&earlier_ref
, earlier
);
367 ao_ref_init (&later_ref
, later
);
368 alias_set_type earlier_set
= ao_ref_alias_set (&earlier_ref
);
369 alias_set_type later_set
= ao_ref_alias_set (&later_ref
);
370 if (!(earlier_set
== later_set
371 || alias_set_subset_of (later_set
, earlier_set
)))
373 alias_set_type later_base_set
= ao_ref_base_alias_set (&later_ref
);
374 alias_set_type earlier_base_set
= ao_ref_base_alias_set (&earlier_ref
);
375 return (earlier_base_set
== later_base_set
376 || alias_set_subset_of (later_base_set
, earlier_base_set
));
379 /* Similar to refs_same_for_tbaa_p() but for use on MEM rtxs. */
381 mems_same_for_tbaa_p (rtx earlier
, rtx later
)
383 gcc_assert (MEM_P (earlier
));
384 gcc_assert (MEM_P (later
));
386 return ((MEM_ALIAS_SET (earlier
) == MEM_ALIAS_SET (later
)
387 || alias_set_subset_of (MEM_ALIAS_SET (later
),
388 MEM_ALIAS_SET (earlier
)))
389 && (!MEM_EXPR (earlier
)
390 || refs_same_for_tbaa_p (MEM_EXPR (earlier
), MEM_EXPR (later
))));
393 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
394 such an entry, or NULL otherwise. */
396 static inline alias_set_entry
*
397 get_alias_set_entry (alias_set_type alias_set
)
399 return (*alias_sets
)[alias_set
];
402 /* Returns true if the alias sets for MEM1 and MEM2 are such that
403 the two MEMs cannot alias each other. */
406 mems_in_disjoint_alias_sets_p (const_rtx mem1
, const_rtx mem2
)
408 return (flag_strict_aliasing
409 && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
),
410 MEM_ALIAS_SET (mem2
)));
413 /* Return true if the first alias set is a subset of the second. */
416 alias_set_subset_of (alias_set_type set1
, alias_set_type set2
)
418 alias_set_entry
*ase2
;
420 /* Disable TBAA oracle with !flag_strict_aliasing. */
421 if (!flag_strict_aliasing
)
424 /* Everything is a subset of the "aliases everything" set. */
428 /* Check if set1 is a subset of set2. */
429 ase2
= get_alias_set_entry (set2
);
431 && (ase2
->has_zero_child
432 || (ase2
->children
&& ase2
->children
->get (set1
))))
435 /* As a special case we consider alias set of "void *" to be both subset
436 and superset of every alias set of a pointer. This extra symmetry does
437 not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
438 to return true on the following testcase:
441 char **ptr2=(char **)&ptr;
444 Additionally if a set contains universal pointer, we consider every pointer
445 to be a subset of it, but we do not represent this explicitely - doing so
446 would require us to update transitive closure each time we introduce new
447 pointer type. This makes aliasing_component_refs_p to return true
448 on the following testcase:
450 struct a {void *ptr;}
451 char **ptr = (char **)&a.ptr;
454 This makes void * truly universal pointer type. See pointer handling in
455 get_alias_set for more details. */
456 if (ase2
&& ase2
->has_pointer
)
458 alias_set_entry
*ase1
= get_alias_set_entry (set1
);
460 if (ase1
&& ase1
->is_pointer
)
462 alias_set_type voidptr_set
= TYPE_ALIAS_SET (ptr_type_node
);
463 /* If one is ptr_type_node and other is pointer, then we consider
464 them subset of each other. */
465 if (set1
== voidptr_set
|| set2
== voidptr_set
)
467 /* If SET2 contains universal pointer's alias set, then we consdier
468 every (non-universal) pointer. */
469 if (ase2
->children
&& set1
!= voidptr_set
470 && ase2
->children
->get (voidptr_set
))
477 /* Return true if the two specified alias sets may conflict. */
480 alias_sets_conflict_p (alias_set_type set1
, alias_set_type set2
)
482 alias_set_entry
*ase1
;
483 alias_set_entry
*ase2
;
486 if (alias_sets_must_conflict_p (set1
, set2
))
489 /* See if the first alias set is a subset of the second. */
490 ase1
= get_alias_set_entry (set1
);
492 && ase1
->children
&& ase1
->children
->get (set2
))
494 ++alias_stats
.num_dag
;
498 /* Now do the same, but with the alias sets reversed. */
499 ase2
= get_alias_set_entry (set2
);
501 && ase2
->children
&& ase2
->children
->get (set1
))
503 ++alias_stats
.num_dag
;
507 /* We want void * to be compatible with any other pointer without
508 really dropping it to alias set 0. Doing so would make it
509 compatible with all non-pointer types too.
511 This is not strictly necessary by the C/C++ language
512 standards, but avoids common type punning mistakes. In
513 addition to that, we need the existence of such universal
514 pointer to implement Fortran's C_PTR type (which is defined as
515 type compatible with all C pointers). */
516 if (ase1
&& ase2
&& ase1
->has_pointer
&& ase2
->has_pointer
)
518 alias_set_type voidptr_set
= TYPE_ALIAS_SET (ptr_type_node
);
520 /* If one of the sets corresponds to universal pointer,
521 we consider it to conflict with anything that is
522 or contains pointer. */
523 if (set1
== voidptr_set
|| set2
== voidptr_set
)
525 ++alias_stats
.num_universal
;
528 /* If one of sets is (non-universal) pointer and the other
529 contains universal pointer, we also get conflict. */
530 if (ase1
->is_pointer
&& set2
!= voidptr_set
531 && ase2
->children
&& ase2
->children
->get (voidptr_set
))
533 ++alias_stats
.num_universal
;
536 if (ase2
->is_pointer
&& set1
!= voidptr_set
537 && ase1
->children
&& ase1
->children
->get (voidptr_set
))
539 ++alias_stats
.num_universal
;
544 ++alias_stats
.num_disambiguated
;
546 /* The two alias sets are distinct and neither one is the
547 child of the other. Therefore, they cannot conflict. */
551 /* Return true if the two specified alias sets will always conflict. */
554 alias_sets_must_conflict_p (alias_set_type set1
, alias_set_type set2
)
556 /* Disable TBAA oracle with !flag_strict_aliasing. */
557 if (!flag_strict_aliasing
)
559 if (set1
== 0 || set2
== 0)
561 ++alias_stats
.num_alias_zero
;
566 ++alias_stats
.num_same_alias_set
;
573 /* Return true if any MEM object of type T1 will always conflict (using the
574 dependency routines in this file) with any MEM object of type T2.
575 This is used when allocating temporary storage. If T1 and/or T2 are
576 NULL_TREE, it means we know nothing about the storage. */
579 objects_must_conflict_p (tree t1
, tree t2
)
581 alias_set_type set1
, set2
;
583 /* If neither has a type specified, we don't know if they'll conflict
584 because we may be using them to store objects of various types, for
585 example the argument and local variables areas of inlined functions. */
586 if (t1
== 0 && t2
== 0)
589 /* If they are the same type, they must conflict. */
592 ++alias_stats
.num_same_objects
;
595 /* Likewise if both are volatile. */
596 if (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
))
598 ++alias_stats
.num_volatile
;
602 set1
= t1
? get_alias_set (t1
) : 0;
603 set2
= t2
? get_alias_set (t2
) : 0;
605 /* We can't use alias_sets_conflict_p because we must make sure
606 that every subtype of t1 will conflict with every subtype of
607 t2 for which a pair of subobjects of these respective subtypes
608 overlaps on the stack. */
609 return alias_sets_must_conflict_p (set1
, set2
);
612 /* Return true if T is an end of the access path which can be used
613 by type based alias oracle. */
616 ends_tbaa_access_path_p (const_tree t
)
618 switch (TREE_CODE (t
))
621 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
623 /* Permit type-punning when accessing a union, provided the access
624 is directly through the union. For example, this code does not
625 permit taking the address of a union member and then storing
626 through it. Even the type-punning allowed here is a GCC
627 extension, albeit a common and useful one; the C standard says
628 that such accesses have implementation-defined behavior. */
629 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t
, 0))) == UNION_TYPE
)
634 case ARRAY_RANGE_REF
:
635 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
644 case VIEW_CONVERT_EXPR
:
645 /* Bitfields and casts are never addressable. */
655 /* Return the outermost parent of component present in the chain of
656 component references handled by get_inner_reference in T with the
658 - the component is non-addressable
659 or NULL_TREE if no such parent exists. In the former cases, the alias
660 set of this parent is the alias set that must be used for T itself. */
663 component_uses_parent_alias_set_from (const_tree t
)
665 const_tree found
= NULL_TREE
;
667 while (handled_component_p (t
))
669 if (ends_tbaa_access_path_p (t
))
672 t
= TREE_OPERAND (t
, 0);
676 return TREE_OPERAND (found
, 0);
682 /* Return whether the pointer-type T effective for aliasing may
683 access everything and thus the reference has to be assigned
687 ref_all_alias_ptr_type_p (const_tree t
)
689 return (VOID_TYPE_P (TREE_TYPE (t
))
690 || TYPE_REF_CAN_ALIAS_ALL (t
));
693 /* Return the alias set for the memory pointed to by T, which may be
694 either a type or an expression. Return -1 if there is nothing
695 special about dereferencing T. */
697 static alias_set_type
698 get_deref_alias_set_1 (tree t
)
700 /* All we care about is the type. */
704 /* If we have an INDIRECT_REF via a void pointer, we don't
705 know anything about what that might alias. Likewise if the
706 pointer is marked that way. */
707 if (ref_all_alias_ptr_type_p (t
))
713 /* Return the alias set for the memory pointed to by T, which may be
714 either a type or an expression. */
717 get_deref_alias_set (tree t
)
719 /* If we're not doing any alias analysis, just assume everything
720 aliases everything else. */
721 if (!flag_strict_aliasing
)
724 alias_set_type set
= get_deref_alias_set_1 (t
);
726 /* Fall back to the alias-set of the pointed-to type. */
731 set
= get_alias_set (TREE_TYPE (t
));
737 /* Return the pointer-type relevant for TBAA purposes from the
738 memory reference tree *T or NULL_TREE in which case *T is
739 adjusted to point to the outermost component reference that
740 can be used for assigning an alias set. */
743 reference_alias_ptr_type_1 (tree
*t
)
747 /* Get the base object of the reference. */
749 while (handled_component_p (inner
))
751 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
752 the type of any component references that wrap it to
753 determine the alias-set. */
754 if (TREE_CODE (inner
) == VIEW_CONVERT_EXPR
)
755 *t
= TREE_OPERAND (inner
, 0);
756 inner
= TREE_OPERAND (inner
, 0);
759 /* Handle pointer dereferences here, they can override the
761 if (INDIRECT_REF_P (inner
)
762 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 0))))
763 return TREE_TYPE (TREE_OPERAND (inner
, 0));
764 else if (TREE_CODE (inner
) == TARGET_MEM_REF
)
765 return TREE_TYPE (TMR_OFFSET (inner
));
766 else if (TREE_CODE (inner
) == MEM_REF
767 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 1))))
768 return TREE_TYPE (TREE_OPERAND (inner
, 1));
770 /* If the innermost reference is a MEM_REF that has a
771 conversion embedded treat it like a VIEW_CONVERT_EXPR above,
772 using the memory access type for determining the alias-set. */
773 if (TREE_CODE (inner
) == MEM_REF
774 && (TYPE_MAIN_VARIANT (TREE_TYPE (inner
))
776 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner
, 1))))))
778 tree alias_ptrtype
= TREE_TYPE (TREE_OPERAND (inner
, 1));
779 /* Unless we have the (aggregate) effective type of the access
780 somewhere on the access path. If we have for example
781 (&a->elts[i])->l.len exposed by abstraction we'd see
782 MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
783 of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
784 example. See PR111715. */
786 while (handled_component_p (inner
)
787 && (TYPE_MAIN_VARIANT (TREE_TYPE (inner
))
788 != TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype
))))
789 inner
= TREE_OPERAND (inner
, 0);
790 if (TREE_CODE (inner
) == MEM_REF
)
791 return alias_ptrtype
;
794 /* Otherwise, pick up the outermost object that we could have
796 tree tem
= component_uses_parent_alias_set_from (*t
);
803 /* Return the pointer-type relevant for TBAA purposes from the
804 gimple memory reference tree T. This is the type to be used for
805 the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
806 and guarantees that get_alias_set will return the same alias
807 set for T and the replacement. */
810 reference_alias_ptr_type (tree t
)
812 /* If the frontend assigns this alias-set zero, preserve that. */
813 if (lang_hooks
.get_alias_set (t
) == 0)
814 return ptr_type_node
;
816 tree ptype
= reference_alias_ptr_type_1 (&t
);
817 /* If there is a given pointer type for aliasing purposes, return it. */
818 if (ptype
!= NULL_TREE
)
821 /* Otherwise build one from the outermost component reference we
823 if (TREE_CODE (t
) == MEM_REF
824 || TREE_CODE (t
) == TARGET_MEM_REF
)
825 return TREE_TYPE (TREE_OPERAND (t
, 1));
827 return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t
)));
830 /* Return whether the pointer-types T1 and T2 used to determine
831 two alias sets of two references will yield the same answer
832 from get_deref_alias_set. */
835 alias_ptr_types_compatible_p (tree t1
, tree t2
)
837 if (TYPE_MAIN_VARIANT (t1
) == TYPE_MAIN_VARIANT (t2
))
840 if (ref_all_alias_ptr_type_p (t1
)
841 || ref_all_alias_ptr_type_p (t2
))
844 /* This function originally abstracts from simply comparing
845 get_deref_alias_set so that we are sure this still computes
846 the same result after LTO type merging is applied.
847 When in LTO type merging is done we can actually do this compare.
850 return get_deref_alias_set (t1
) == get_deref_alias_set (t2
);
852 return (TYPE_MAIN_VARIANT (TREE_TYPE (t1
))
853 == TYPE_MAIN_VARIANT (TREE_TYPE (t2
)));
856 /* Create emptry alias set entry. */
859 init_alias_set_entry (alias_set_type set
)
861 alias_set_entry
*ase
= ggc_alloc
<alias_set_entry
> ();
862 ase
->alias_set
= set
;
863 ase
->children
= NULL
;
864 ase
->has_zero_child
= false;
865 ase
->is_pointer
= false;
866 ase
->has_pointer
= false;
867 gcc_checking_assert (!get_alias_set_entry (set
));
868 (*alias_sets
)[set
] = ase
;
872 /* Return the alias set for T, which may be either a type or an
873 expression. Call language-specific routine for help, if needed. */
876 get_alias_set (tree t
)
880 /* We cannot give up with -fno-strict-aliasing because we need to build
881 proper type representations for possible functions which are built with
882 -fstrict-aliasing. */
884 /* return 0 if this or its type is an error. */
885 if (t
== error_mark_node
887 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
890 /* We can be passed either an expression or a type. This and the
891 language-specific routine may make mutually-recursive calls to each other
892 to figure out what to do. At each juncture, we see if this is a tree
893 that the language may need to handle specially. First handle things that
897 /* Give the language a chance to do something with this tree
898 before we look at it. */
900 set
= lang_hooks
.get_alias_set (t
);
904 /* Get the alias pointer-type to use or the outermost object
905 that we could have a pointer to. */
906 tree ptype
= reference_alias_ptr_type_1 (&t
);
908 return get_deref_alias_set (ptype
);
910 /* If we've already determined the alias set for a decl, just return
911 it. This is necessary for C++ anonymous unions, whose component
912 variables don't look like union members (boo!). */
914 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
915 return MEM_ALIAS_SET (DECL_RTL (t
));
917 /* Now all we care about is the type. */
921 /* Variant qualifiers don't affect the alias set, so get the main
923 t
= TYPE_MAIN_VARIANT (t
);
925 if (AGGREGATE_TYPE_P (t
)
926 && TYPE_TYPELESS_STORAGE (t
))
929 /* Always use the canonical type as well. If this is a type that
930 requires structural comparisons to identify compatible types
931 use alias set zero. */
932 if (TYPE_STRUCTURAL_EQUALITY_P (t
))
934 /* Allow the language to specify another alias set for this
936 set
= lang_hooks
.get_alias_set (t
);
939 /* Handle structure type equality for pointer types, arrays and vectors.
940 This is easy to do, because the code below ignores canonical types on
941 these anyway. This is important for LTO, where TYPE_CANONICAL for
942 pointers cannot be meaningfully computed by the frontend. */
943 if (canonical_type_used_p (t
))
945 /* In LTO we set canonical types for all types where it makes
946 sense to do so. Double check we did not miss some type. */
947 gcc_checking_assert (!in_lto_p
|| !type_with_alias_set_p (t
));
953 t
= TYPE_CANONICAL (t
);
954 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t
));
957 /* If this is a type with a known alias set, return it. */
958 gcc_checking_assert (t
== TYPE_MAIN_VARIANT (t
));
959 if (TYPE_ALIAS_SET_KNOWN_P (t
))
960 return TYPE_ALIAS_SET (t
);
962 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
963 if (!COMPLETE_TYPE_P (t
))
965 /* For arrays with unknown size the conservative answer is the
966 alias set of the element type. */
967 if (TREE_CODE (t
) == ARRAY_TYPE
)
968 return get_alias_set (TREE_TYPE (t
));
970 /* But return zero as a conservative answer for incomplete types. */
974 /* See if the language has special handling for this type. */
975 set
= lang_hooks
.get_alias_set (t
);
979 /* There are no objects of FUNCTION_TYPE, so there's no point in
980 using up an alias set for them. (There are, of course, pointers
981 and references to functions, but that's different.) */
982 else if (TREE_CODE (t
) == FUNCTION_TYPE
|| TREE_CODE (t
) == METHOD_TYPE
)
985 /* Unless the language specifies otherwise, let vector types alias
986 their components. This avoids some nasty type punning issues in
987 normal usage. And indeed lets vectors be treated more like an
989 else if (TREE_CODE (t
) == VECTOR_TYPE
)
990 set
= get_alias_set (TREE_TYPE (t
));
992 /* Unless the language specifies otherwise, treat array types the
993 same as their components. This avoids the asymmetry we get
994 through recording the components. Consider accessing a
995 character(kind=1) through a reference to a character(kind=1)[1:1].
996 Or consider if we want to assign integer(kind=4)[0:D.1387] and
997 integer(kind=4)[4] the same alias set or not.
998 Just be pragmatic here and make sure the array and its element
999 type get the same alias set assigned. */
1000 else if (TREE_CODE (t
) == ARRAY_TYPE
1001 && (!TYPE_NONALIASED_COMPONENT (t
)
1002 || TYPE_STRUCTURAL_EQUALITY_P (t
)))
1003 set
= get_alias_set (TREE_TYPE (t
));
1005 /* From the former common C and C++ langhook implementation:
1007 Unfortunately, there is no canonical form of a pointer type.
1008 In particular, if we have `typedef int I', then `int *', and
1009 `I *' are different types. So, we have to pick a canonical
1010 representative. We do this below.
1012 Technically, this approach is actually more conservative that
1013 it needs to be. In particular, `const int *' and `int *'
1014 should be in different alias sets, according to the C and C++
1015 standard, since their types are not the same, and so,
1016 technically, an `int **' and `const int **' cannot point at
1019 But, the standard is wrong. In particular, this code is
1024 const int* const* cipp = ipp;
1025 And, it doesn't make sense for that to be legal unless you
1026 can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1027 the pointed-to types. This issue has been reported to the
1030 For this reason go to canonical type of the unqalified pointer type.
1031 Until GCC 6 this code set all pointers sets to have alias set of
1032 ptr_type_node but that is a bad idea, because it prevents disabiguations
1033 in between pointers. For Firefox this accounts about 20% of all
1034 disambiguations in the program. */
1035 else if (POINTER_TYPE_P (t
) && t
!= ptr_type_node
)
1038 auto_vec
<bool, 8> reference
;
1040 /* Unnest all pointers and references.
1041 We also want to make pointer to array/vector equivalent to pointer to
1042 its element (see the reasoning above). Skip all those types, too. */
1043 for (p
= t
; POINTER_TYPE_P (p
)
1044 || (TREE_CODE (p
) == ARRAY_TYPE
1045 && (!TYPE_NONALIASED_COMPONENT (p
)
1046 || !COMPLETE_TYPE_P (p
)
1047 || TYPE_STRUCTURAL_EQUALITY_P (p
)))
1048 || TREE_CODE (p
) == VECTOR_TYPE
;
1051 /* Ada supports recursive pointers. Instead of doing recursion
1052 check, just give up once the preallocated space of 8 elements
1053 is up. In this case just punt to void * alias set. */
1054 if (reference
.length () == 8)
1059 if (TREE_CODE (p
) == REFERENCE_TYPE
)
1060 /* In LTO we want languages that use references to be compatible
1061 with languages that use pointers. */
1062 reference
.safe_push (true && !in_lto_p
);
1063 if (TREE_CODE (p
) == POINTER_TYPE
)
1064 reference
.safe_push (false);
1066 p
= TYPE_MAIN_VARIANT (p
);
1068 /* In LTO for C++ programs we can turn incomplete types to complete
1069 using ODR name lookup. */
1070 if (in_lto_p
&& TYPE_STRUCTURAL_EQUALITY_P (p
) && odr_type_p (p
))
1072 p
= prevailing_odr_type (p
);
1073 gcc_checking_assert (TYPE_MAIN_VARIANT (p
) == p
);
1076 /* Make void * compatible with char * and also void **.
1077 Programs are commonly violating TBAA by this.
1079 We also make void * to conflict with every pointer
1080 (see record_component_aliases) and thus it is safe it to use it for
1081 pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1082 if (TREE_CODE (p
) == VOID_TYPE
|| TYPE_STRUCTURAL_EQUALITY_P (p
))
1083 set
= get_alias_set (ptr_type_node
);
1086 /* Rebuild pointer type starting from canonical types using
1087 unqualified pointers and references only. This way all such
1088 pointers will have the same alias set and will conflict with
1091 Most of time we already have pointers or references of a given type.
1092 If not we build new one just to be sure that if someone later
1093 (probably only middle-end can, as we should assign all alias
1094 classes only after finishing translation unit) builds the pointer
1095 type, the canonical type will match. */
1096 p
= TYPE_CANONICAL (p
);
1097 while (!reference
.is_empty ())
1099 if (reference
.pop ())
1100 p
= build_reference_type (p
);
1102 p
= build_pointer_type (p
);
1103 gcc_checking_assert (p
== TYPE_MAIN_VARIANT (p
));
1104 /* build_pointer_type should always return the canonical type.
1105 For LTO TYPE_CANOINCAL may be NULL, because we do not compute
1106 them. Be sure that frontends do not glob canonical types of
1107 pointers in unexpected way and that p == TYPE_CANONICAL (p)
1108 in all other cases. */
1109 gcc_checking_assert (!TYPE_CANONICAL (p
)
1110 || p
== TYPE_CANONICAL (p
));
1113 /* Assign the alias set to both p and t.
1114 We cannot call get_alias_set (p) here as that would trigger
1115 infinite recursion when p == t. In other cases it would just
1116 trigger unnecesary legwork of rebuilding the pointer again. */
1117 gcc_checking_assert (p
== TYPE_MAIN_VARIANT (p
));
1118 if (TYPE_ALIAS_SET_KNOWN_P (p
))
1119 set
= TYPE_ALIAS_SET (p
);
1122 set
= new_alias_set ();
1123 TYPE_ALIAS_SET (p
) = set
;
1127 /* Alias set of ptr_type_node is special and serve as universal pointer which
1128 is TBAA compatible with every other pointer type. Be sure we have the
1129 alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1130 of pointer types NULL. */
1131 else if (t
== ptr_type_node
)
1132 set
= new_alias_set ();
1134 /* Otherwise make a new alias set for this type. */
1137 /* Each canonical type gets its own alias set, so canonical types
1138 shouldn't form a tree. It doesn't really matter for types
1139 we handle specially above, so only check it where it possibly
1140 would result in a bogus alias set. */
1141 gcc_checking_assert (TYPE_CANONICAL (t
) == t
);
1143 set
= new_alias_set ();
1146 TYPE_ALIAS_SET (t
) = set
;
1148 /* If this is an aggregate type or a complex type, we must record any
1149 component aliasing information. */
1150 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
1151 record_component_aliases (t
);
1153 /* We treat pointer types specially in alias_set_subset_of. */
1154 if (POINTER_TYPE_P (t
) && set
)
1156 alias_set_entry
*ase
= get_alias_set_entry (set
);
1158 ase
= init_alias_set_entry (set
);
1159 ase
->is_pointer
= true;
1160 ase
->has_pointer
= true;
1166 /* Return a brand-new alias set. */
1169 new_alias_set (void)
1171 if (alias_sets
== 0)
1172 vec_safe_push (alias_sets
, (alias_set_entry
*) NULL
);
1173 vec_safe_push (alias_sets
, (alias_set_entry
*) NULL
);
1174 return alias_sets
->length () - 1;
1177 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1178 not everything that aliases SUPERSET also aliases SUBSET. For example,
1179 in C, a store to an `int' can alias a load of a structure containing an
1180 `int', and vice versa. But it can't alias a load of a 'double' member
1181 of the same structure. Here, the structure would be the SUPERSET and
1182 `int' the SUBSET. This relationship is also described in the comment at
1183 the beginning of this file.
1185 This function should be called only once per SUPERSET/SUBSET pair.
1187 It is illegal for SUPERSET to be zero; everything is implicitly a
1188 subset of alias set zero. */
1191 record_alias_subset (alias_set_type superset
, alias_set_type subset
)
1193 alias_set_entry
*superset_entry
;
1194 alias_set_entry
*subset_entry
;
1196 /* It is possible in complex type situations for both sets to be the same,
1197 in which case we can ignore this operation. */
1198 if (superset
== subset
)
1201 gcc_assert (superset
);
1203 superset_entry
= get_alias_set_entry (superset
);
1204 if (superset_entry
== 0)
1206 /* Create an entry for the SUPERSET, so that we have a place to
1207 attach the SUBSET. */
1208 superset_entry
= init_alias_set_entry (superset
);
1212 superset_entry
->has_zero_child
= 1;
1215 if (!superset_entry
->children
)
1216 superset_entry
->children
1217 = hash_map
<alias_set_hash
, int>::create_ggc (64);
1219 /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1220 already there we're done. */
1221 if (superset_entry
->children
->put (subset
, 0))
1224 subset_entry
= get_alias_set_entry (subset
);
1225 /* If there is an entry for the subset, enter all of its children
1226 (if they are not already present) as children of the SUPERSET. */
1229 if (subset_entry
->has_zero_child
)
1230 superset_entry
->has_zero_child
= true;
1231 if (subset_entry
->has_pointer
)
1232 superset_entry
->has_pointer
= true;
1234 if (subset_entry
->children
)
1236 hash_map
<alias_set_hash
, int>::iterator iter
1237 = subset_entry
->children
->begin ();
1238 for (; iter
!= subset_entry
->children
->end (); ++iter
)
1239 superset_entry
->children
->put ((*iter
).first
, (*iter
).second
);
1245 /* Record that component types of TYPE, if any, are part of SUPERSET for
1246 aliasing purposes. For record types, we only record component types
1247 for fields that are not marked non-addressable. For array types, we
1248 only record the component type if it is not marked non-aliased. */
1251 record_component_aliases (tree type
, alias_set_type superset
)
1258 switch (TREE_CODE (type
))
1262 case QUAL_UNION_TYPE
:
1264 /* LTO non-ODR type merging does not make any difference between
1265 component pointer types. We may have
1267 struct foo {int *a;};
1269 as TYPE_CANONICAL of
1271 struct bar {float *a;};
1273 Because accesses to int * and float * do not alias, we would get
1274 false negative when accessing the same memory location by
1275 float ** and bar *. We thus record the canonical type as:
1279 void * is special cased and works as a universal pointer type.
1280 Accesses to it conflicts with accesses to any other pointer
1282 bool void_pointers
= in_lto_p
1283 && (!odr_type_p (type
)
1284 || !odr_based_tbaa_p (type
));
1285 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= DECL_CHAIN (field
))
1286 if (TREE_CODE (field
) == FIELD_DECL
&& !DECL_NONADDRESSABLE_P (field
))
1288 tree t
= TREE_TYPE (field
);
1291 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1292 element type and that type has to be normalized to void *,
1293 too, in the case it is a pointer. */
1294 while (!canonical_type_used_p (t
) && !POINTER_TYPE_P (t
))
1296 gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t
));
1299 if (POINTER_TYPE_P (t
))
1301 else if (flag_checking
)
1302 gcc_checking_assert (get_alias_set (t
)
1303 == get_alias_set (TREE_TYPE (field
)));
1306 alias_set_type set
= get_alias_set (t
);
1307 record_alias_subset (superset
, set
);
1308 /* If the field has alias-set zero make sure to still record
1309 any componets of it. This makes sure that for
1316 in C++ even though 'B' has alias-set zero because
1317 TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1320 record_component_aliases (t
, superset
);
1326 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
1329 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1337 /* Record that component types of TYPE, if any, are part of that type for
1338 aliasing purposes. For record types, we only record component types
1339 for fields that are not marked non-addressable. For array types, we
1340 only record the component type if it is not marked non-aliased. */
1343 record_component_aliases (tree type
)
1345 alias_set_type superset
= get_alias_set (type
);
1346 record_component_aliases (type
, superset
);
1350 /* Allocate an alias set for use in storing and reading from the varargs
1353 static GTY(()) alias_set_type varargs_set
= -1;
1356 get_varargs_alias_set (void)
1359 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1360 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1361 consistently use the varargs alias set for loads from the varargs
1362 area. So don't use it anywhere. */
1365 if (varargs_set
== -1)
1366 varargs_set
= new_alias_set ();
1372 /* Likewise, but used for the fixed portions of the frame, e.g., register
1375 static GTY(()) alias_set_type frame_set
= -1;
1378 get_frame_alias_set (void)
1380 if (frame_set
== -1)
1381 frame_set
= new_alias_set ();
1386 /* Create a new, unique base with id ID. */
1389 unique_base_value (HOST_WIDE_INT id
)
1391 return gen_rtx_ADDRESS (Pmode
, id
);
1394 /* Return true if accesses based on any other base value cannot alias
1395 those based on X. */
1398 unique_base_value_p (rtx x
)
1400 return GET_CODE (x
) == ADDRESS
&& GET_MODE (x
) == Pmode
;
1403 /* Inside SRC, the source of a SET, find a base address. */
1406 find_base_value (rtx src
)
1409 scalar_int_mode int_mode
;
1411 #if defined (FIND_BASE_TERM)
1412 /* Try machine-dependent ways to find the base term. */
1413 src
= FIND_BASE_TERM (src
);
1416 switch (GET_CODE (src
))
1423 regno
= REGNO (src
);
1424 /* At the start of a function, argument registers have known base
1425 values which may be lost later. Returning an ADDRESS
1426 expression here allows optimization based on argument values
1427 even when the argument registers are used for other purposes. */
1428 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
1429 return new_reg_base_value
[regno
];
1431 /* If a pseudo has a known base value, return it. Do not do this
1432 for non-fixed hard regs since it can result in a circular
1433 dependency chain for registers which have values at function entry.
1435 The test above is not sufficient because the scheduler may move
1436 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1437 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
1438 && regno
< vec_safe_length (reg_base_value
))
1440 /* If we're inside init_alias_analysis, use new_reg_base_value
1441 to reduce the number of relaxation iterations. */
1442 if (new_reg_base_value
&& new_reg_base_value
[regno
]
1443 && DF_REG_DEF_COUNT (regno
) == 1)
1444 return new_reg_base_value
[regno
];
1446 if ((*reg_base_value
)[regno
])
1447 return (*reg_base_value
)[regno
];
1453 /* Check for an argument passed in memory. Only record in the
1454 copying-arguments block; it is too hard to track changes
1456 if (copying_arguments
1457 && (XEXP (src
, 0) == arg_pointer_rtx
1458 || (GET_CODE (XEXP (src
, 0)) == PLUS
1459 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
1460 return arg_base_value
;
1464 src
= XEXP (src
, 0);
1465 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
1473 rtx src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
1475 /* If either operand is a CONST_INT, then the other is the base. */
1476 if (CONST_INT_P (src_1
))
1477 return find_base_value (src_0
);
1478 else if (CONST_INT_P (src_0
))
1479 return find_base_value (src_1
);
1485 /* The standard form is (lo_sum reg sym) so look only at the
1487 return find_base_value (XEXP (src
, 1));
1490 /* Look through aligning ANDs. And AND with zero or one with
1491 the LSB set isn't one (see for example PR92462). */
1492 if (CONST_INT_P (XEXP (src
, 1))
1493 && INTVAL (XEXP (src
, 1)) != 0
1494 && (INTVAL (XEXP (src
, 1)) & 1) == 0)
1495 return find_base_value (XEXP (src
, 0));
1499 /* As we do not know which address space the pointer is referring to, we can
1500 handle this only if the target does not support different pointer or
1501 address modes depending on the address space. */
1502 if (!target_default_pointer_address_modes_p ())
1504 if (!is_a
<scalar_int_mode
> (GET_MODE (src
), &int_mode
)
1505 || GET_MODE_PRECISION (int_mode
) < GET_MODE_PRECISION (Pmode
))
1515 return find_base_value (XEXP (src
, 0));
1518 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
1519 /* As we do not know which address space the pointer is referring to, we can
1520 handle this only if the target does not support different pointer or
1521 address modes depending on the address space. */
1522 if (!target_default_pointer_address_modes_p ())
1526 rtx temp
= find_base_value (XEXP (src
, 0));
1528 if (temp
!= 0 && CONSTANT_P (temp
))
1529 temp
= convert_memory_address (Pmode
, temp
);
1541 /* Called from init_alias_analysis indirectly through note_stores,
1542 or directly if DEST is a register with a REG_NOALIAS note attached.
1543 SET is null in the latter case. */
1545 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1546 register N has been set in this function. */
1547 static sbitmap reg_seen
;
1550 record_set (rtx dest
, const_rtx set
, void *data ATTRIBUTE_UNUSED
)
1559 regno
= REGNO (dest
);
1561 gcc_checking_assert (regno
< reg_base_value
->length ());
1563 n
= REG_NREGS (dest
);
1568 bitmap_set_bit (reg_seen
, regno
+ n
);
1569 new_reg_base_value
[regno
+ n
] = 0;
1576 /* A CLOBBER wipes out any old value but does not prevent a previously
1577 unset register from acquiring a base address (i.e. reg_seen is not
1579 if (GET_CODE (set
) == CLOBBER
)
1581 new_reg_base_value
[regno
] = 0;
1585 src
= SET_SRC (set
);
1589 /* There's a REG_NOALIAS note against DEST. */
1590 if (bitmap_bit_p (reg_seen
, regno
))
1592 new_reg_base_value
[regno
] = 0;
1595 bitmap_set_bit (reg_seen
, regno
);
1596 new_reg_base_value
[regno
] = unique_base_value (unique_id
++);
1600 /* If this is not the first set of REGNO, see whether the new value
1601 is related to the old one. There are two cases of interest:
1603 (1) The register might be assigned an entirely new value
1604 that has the same base term as the original set.
1606 (2) The set might be a simple self-modification that
1607 cannot change REGNO's base value.
1609 If neither case holds, reject the original base value as invalid.
1610 Note that the following situation is not detected:
1612 extern int x, y; int *p = &x; p += (&y-&x);
1614 ANSI C does not allow computing the difference of addresses
1615 of distinct top level objects. */
1616 if (new_reg_base_value
[regno
] != 0
1617 && find_base_value (src
) != new_reg_base_value
[regno
])
1618 switch (GET_CODE (src
))
1622 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1623 new_reg_base_value
[regno
] = 0;
1626 /* If the value we add in the PLUS is also a valid base value,
1627 this might be the actual base value, and the original value
1630 rtx other
= NULL_RTX
;
1632 if (XEXP (src
, 0) == dest
)
1633 other
= XEXP (src
, 1);
1634 else if (XEXP (src
, 1) == dest
)
1635 other
= XEXP (src
, 0);
1637 if (! other
|| find_base_value (other
))
1638 new_reg_base_value
[regno
] = 0;
1642 if (XEXP (src
, 0) != dest
|| !CONST_INT_P (XEXP (src
, 1)))
1643 new_reg_base_value
[regno
] = 0;
1646 new_reg_base_value
[regno
] = 0;
1649 /* If this is the first set of a register, record the value. */
1650 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1651 && ! bitmap_bit_p (reg_seen
, regno
) && new_reg_base_value
[regno
] == 0)
1652 new_reg_base_value
[regno
] = find_base_value (src
);
1654 bitmap_set_bit (reg_seen
, regno
);
1657 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1658 using hard registers with non-null REG_BASE_VALUE for renaming. */
1660 get_reg_base_value (unsigned int regno
)
1662 return (*reg_base_value
)[regno
];
1665 /* If a value is known for REGNO, return it. */
1668 get_reg_known_value (unsigned int regno
)
1670 if (regno
>= FIRST_PSEUDO_REGISTER
)
1672 regno
-= FIRST_PSEUDO_REGISTER
;
1673 if (regno
< vec_safe_length (reg_known_value
))
1674 return (*reg_known_value
)[regno
];
1682 set_reg_known_value (unsigned int regno
, rtx val
)
1684 if (regno
>= FIRST_PSEUDO_REGISTER
)
1686 regno
-= FIRST_PSEUDO_REGISTER
;
1687 if (regno
< vec_safe_length (reg_known_value
))
1688 (*reg_known_value
)[regno
] = val
;
1692 /* Similarly for reg_known_equiv_p. */
1695 get_reg_known_equiv_p (unsigned int regno
)
1697 if (regno
>= FIRST_PSEUDO_REGISTER
)
1699 regno
-= FIRST_PSEUDO_REGISTER
;
1700 if (regno
< vec_safe_length (reg_known_value
))
1701 return bitmap_bit_p (reg_known_equiv_p
, regno
);
1707 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1709 if (regno
>= FIRST_PSEUDO_REGISTER
)
1711 regno
-= FIRST_PSEUDO_REGISTER
;
1712 if (regno
< vec_safe_length (reg_known_value
))
1715 bitmap_set_bit (reg_known_equiv_p
, regno
);
1717 bitmap_clear_bit (reg_known_equiv_p
, regno
);
1723 /* Returns a canonical version of X, from the point of view alias
1724 analysis. (For example, if X is a MEM whose address is a register,
1725 and the register has a known value (say a SYMBOL_REF), then a MEM
1726 whose address is the SYMBOL_REF is returned.) */
1731 /* Recursively look for equivalences. */
1732 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1734 rtx t
= get_reg_known_value (REGNO (x
));
1738 return canon_rtx (t
);
1741 if (GET_CODE (x
) == PLUS
)
1743 rtx x0
= canon_rtx (XEXP (x
, 0));
1744 rtx x1
= canon_rtx (XEXP (x
, 1));
1746 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1747 return simplify_gen_binary (PLUS
, GET_MODE (x
), x0
, x1
);
1750 /* This gives us much better alias analysis when called from
1751 the loop optimizer. Note we want to leave the original
1752 MEM alone, but need to return the canonicalized MEM with
1753 all the flags with their original values. */
1755 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1760 /* Return true if X and Y are identical-looking rtx's.
1761 Expect that X and Y has been already canonicalized.
1763 We use the data in reg_known_value above to see if two registers with
1764 different numbers are, in fact, equivalent. */
1767 rtx_equal_for_memref_p (const_rtx x
, const_rtx y
)
1774 if (x
== 0 && y
== 0)
1776 if (x
== 0 || y
== 0)
1782 code
= GET_CODE (x
);
1783 /* Rtx's of different codes cannot be equal. */
1784 if (code
!= GET_CODE (y
))
1787 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1788 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1790 if (GET_MODE (x
) != GET_MODE (y
))
1793 /* Some RTL can be compared without a recursive examination. */
1797 return REGNO (x
) == REGNO (y
);
1800 return label_ref_label (x
) == label_ref_label (y
);
1804 HOST_WIDE_INT distance
= 0;
1805 return (compare_base_symbol_refs (x
, y
, &distance
) == 1
1810 /* This is magic, don't go through canonicalization et al. */
1811 return rtx_equal_p (ENTRY_VALUE_EXP (x
), ENTRY_VALUE_EXP (y
));
1815 /* Pointer equality guarantees equality for these nodes. */
1822 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1824 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1825 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1826 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1827 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1828 /* For commutative operations, the RTX match if the operand match in any
1829 order. Also handle the simple binary and unary cases without a loop. */
1830 if (COMMUTATIVE_P (x
))
1832 rtx xop0
= canon_rtx (XEXP (x
, 0));
1833 rtx yop0
= canon_rtx (XEXP (y
, 0));
1834 rtx yop1
= canon_rtx (XEXP (y
, 1));
1836 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1837 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1838 || (rtx_equal_for_memref_p (xop0
, yop1
)
1839 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1841 else if (NON_COMMUTATIVE_P (x
))
1843 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1844 canon_rtx (XEXP (y
, 0)))
1845 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1846 canon_rtx (XEXP (y
, 1))));
1848 else if (UNARY_P (x
))
1849 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1850 canon_rtx (XEXP (y
, 0)));
1852 /* Compare the elements. If any pair of corresponding elements
1853 fail to match, return false for the whole things.
1855 Limit cases to types which actually appear in addresses. */
1857 fmt
= GET_RTX_FORMAT (code
);
1858 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1863 if (XINT (x
, i
) != XINT (y
, i
))
1868 if (maybe_ne (SUBREG_BYTE (x
), SUBREG_BYTE (y
)))
1873 /* Two vectors must have the same length. */
1874 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1877 /* And the corresponding elements must match. */
1878 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1879 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1880 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1885 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1886 canon_rtx (XEXP (y
, i
))) == 0)
1890 /* This can happen for asm operands. */
1892 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1896 /* This can happen for an asm which clobbers memory. */
1900 /* It is believed that rtx's at this level will never
1901 contain anything but integers and other rtx's,
1902 except for within LABEL_REFs and SYMBOL_REFs. */
1911 find_base_term (rtx x
, vec
<std::pair
<cselib_val
*,
1912 struct elt_loc_list
*> > &visited_vals
)
1915 struct elt_loc_list
*l
, *f
;
1917 scalar_int_mode int_mode
;
1919 #if defined (FIND_BASE_TERM)
1920 /* Try machine-dependent ways to find the base term. */
1921 x
= FIND_BASE_TERM (x
);
1924 switch (GET_CODE (x
))
1927 return REG_BASE_VALUE (x
);
1930 /* As we do not know which address space the pointer is referring to, we can
1931 handle this only if the target does not support different pointer or
1932 address modes depending on the address space. */
1933 if (!target_default_pointer_address_modes_p ())
1935 if (!is_a
<scalar_int_mode
> (GET_MODE (x
), &int_mode
)
1936 || GET_MODE_PRECISION (int_mode
) < GET_MODE_PRECISION (Pmode
))
1946 return find_base_term (XEXP (x
, 0), visited_vals
);
1949 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1950 /* As we do not know which address space the pointer is referring to, we can
1951 handle this only if the target does not support different pointer or
1952 address modes depending on the address space. */
1953 if (!target_default_pointer_address_modes_p ())
1957 rtx temp
= find_base_term (XEXP (x
, 0), visited_vals
);
1959 if (temp
!= 0 && CONSTANT_P (temp
))
1960 temp
= convert_memory_address (Pmode
, temp
);
1966 val
= CSELIB_VAL_PTR (x
);
1972 if (cselib_sp_based_value_p (val
))
1973 return static_reg_base_value
[STACK_POINTER_REGNUM
];
1975 if (visited_vals
.length () > (unsigned) param_max_find_base_term_values
)
1979 /* Reset val->locs to avoid infinite recursion. */
1981 visited_vals
.safe_push (std::make_pair (val
, f
));
1984 for (l
= f
; l
; l
= l
->next
)
1985 if (GET_CODE (l
->loc
) == VALUE
1986 && CSELIB_VAL_PTR (l
->loc
)->locs
1987 && !CSELIB_VAL_PTR (l
->loc
)->locs
->next
1988 && CSELIB_VAL_PTR (l
->loc
)->locs
->loc
== x
)
1990 else if ((ret
= find_base_term (l
->loc
, visited_vals
)) != 0)
1996 /* The standard form is (lo_sum reg sym) so look only at the
1998 return find_base_term (XEXP (x
, 1), visited_vals
);
2002 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
2008 rtx tmp1
= XEXP (x
, 0);
2009 rtx tmp2
= XEXP (x
, 1);
2011 /* This is a little bit tricky since we have to determine which of
2012 the two operands represents the real base address. Otherwise this
2013 routine may return the index register instead of the base register.
2015 That may cause us to believe no aliasing was possible, when in
2016 fact aliasing is possible.
2018 We use a few simple tests to guess the base register. Additional
2019 tests can certainly be added. For example, if one of the operands
2020 is a shift or multiply, then it must be the index register and the
2021 other operand is the base register. */
2023 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
2024 return find_base_term (tmp2
, visited_vals
);
2026 if (CONST_INT_P (tmp1
))
2027 std::swap (tmp1
, tmp2
);
2029 /* We can only handle binary operators when one of the operands
2030 never leads to a base value. */
2031 if (CONST_INT_P (tmp2
))
2032 return find_base_term (tmp1
, visited_vals
);
2034 /* We could not determine which of the two operands was the
2035 base register and which was the index. So we can determine
2036 nothing from the base alias check. */
2041 /* Look through aligning ANDs. And AND with zero or one with
2042 the LSB set isn't one (see for example PR92462). */
2043 if (CONST_INT_P (XEXP (x
, 1))
2044 && INTVAL (XEXP (x
, 1)) != 0
2045 && (INTVAL (XEXP (x
, 1)) & 1) == 0)
2046 return find_base_term (XEXP (x
, 0), visited_vals
);
2058 /* Wrapper around the worker above which removes locs from visited VALUEs
2059 to avoid visiting them multiple times. We unwind that changes here. */
2062 find_base_term (rtx x
)
2064 auto_vec
<std::pair
<cselib_val
*, struct elt_loc_list
*>, 32> visited_vals
;
2065 rtx res
= find_base_term (x
, visited_vals
);
2066 for (unsigned i
= 0; i
< visited_vals
.length (); ++i
)
2067 visited_vals
[i
].first
->locs
= visited_vals
[i
].second
;
2071 /* Return true if accesses to address X may alias accesses based
2072 on the stack pointer. */
2075 may_be_sp_based_p (rtx x
)
2077 rtx base
= find_base_term (x
);
2078 return !base
|| base
== static_reg_base_value
[STACK_POINTER_REGNUM
];
2081 /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2082 if they refer to different objects and -1 if we cannot decide. */
2085 compare_base_decls (tree base1
, tree base2
)
2088 gcc_checking_assert (DECL_P (base1
) && DECL_P (base2
));
2092 /* If we have two register decls with register specification we
2093 cannot decide unless their assembler names are the same. */
2096 && DECL_HARD_REGISTER (base1
)
2097 && DECL_HARD_REGISTER (base2
)
2098 && DECL_ASSEMBLER_NAME_SET_P (base1
)
2099 && DECL_ASSEMBLER_NAME_SET_P (base2
))
2101 if (DECL_ASSEMBLER_NAME_RAW (base1
) == DECL_ASSEMBLER_NAME_RAW (base2
))
2106 /* Declarations of non-automatic variables may have aliases. All other
2107 decls are unique. */
2108 if (!decl_in_symtab_p (base1
)
2109 || !decl_in_symtab_p (base2
))
2112 /* Don't cause symbols to be inserted by the act of checking. */
2113 symtab_node
*node1
= symtab_node::get (base1
);
2116 symtab_node
*node2
= symtab_node::get (base2
);
2120 ret
= node1
->equal_address_to (node2
, true);
2124 /* Compare SYMBOL_REFs X_BASE and Y_BASE.
2126 - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2127 to *DISTANCE if DISTANCE is nonnull.
2129 - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2131 - Return -1 if one of the two results applies, but we can't tell
2132 which at compile time. Update DISTANCE in the same way as
2133 for a return value of 1, for the case in which that holds. */
2136 compare_base_symbol_refs (const_rtx x_base
, const_rtx y_base
,
2137 HOST_WIDE_INT
*distance
)
2139 tree x_decl
= SYMBOL_REF_DECL (x_base
);
2140 tree y_decl
= SYMBOL_REF_DECL (y_base
);
2141 bool binds_def
= true;
2144 if (XSTR (x_base
, 0) == XSTR (y_base
, 0))
2146 if (x_decl
&& y_decl
)
2147 return compare_base_decls (x_decl
, y_decl
);
2148 if (x_decl
|| y_decl
)
2153 std::swap (x_decl
, y_decl
);
2154 std::swap (x_base
, y_base
);
2156 /* We handle specially only section anchors. Other symbols are
2157 either equal (via aliasing) or refer to different objects. */
2158 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base
))
2160 /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2161 to ignore CONST_DECLs because they are readonly. */
2163 || (!TREE_STATIC (x_decl
) && !TREE_PUBLIC (x_decl
)))
2166 symtab_node
*x_node
= symtab_node::get_create (x_decl
)
2167 ->ultimate_alias_target ();
2168 /* External variable cannot be in section anchor. */
2169 if (!x_node
->definition
)
2171 x_base
= XEXP (DECL_RTL (x_node
->decl
), 0);
2172 /* If not in anchor, we can disambiguate. */
2173 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base
))
2176 /* We have an alias of anchored variable. If it can be interposed;
2177 we must assume it may or may not alias its anchor. */
2178 binds_def
= decl_binds_to_current_def_p (x_decl
);
2180 /* If we have variable in section anchor, we can compare by offset. */
2181 if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base
)
2182 && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base
))
2184 if (SYMBOL_REF_BLOCK (x_base
) != SYMBOL_REF_BLOCK (y_base
))
2187 *distance
+= (swap
? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base
)
2188 - SYMBOL_REF_BLOCK_OFFSET (x_base
));
2189 return binds_def
? 1 : -1;
2191 /* Either the symbols are equal (via aliasing) or they refer to
2192 different objects. */
2196 /* Return false if the addresses X and Y are known to point to different
2197 objects, true if they might be pointers to the same object. */
2200 base_alias_check (rtx x
, rtx x_base
, rtx y
, rtx y_base
,
2201 machine_mode x_mode
, machine_mode y_mode
)
2203 /* If the address itself has no known base see if a known equivalent
2204 value has one. If either address still has no known base, nothing
2205 is known about aliasing. */
2210 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
2213 x_base
= find_base_term (x_c
);
2221 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
2224 y_base
= find_base_term (y_c
);
2229 /* If the base addresses are equal nothing is known about aliasing. */
2230 if (rtx_equal_p (x_base
, y_base
))
2233 /* The base addresses are different expressions. If they are not accessed
2234 via AND, there is no conflict. We can bring knowledge of object
2235 alignment into play here. For example, on alpha, "char a, b;" can
2236 alias one another, though "char a; long b;" cannot. AND addresses may
2237 implicitly alias surrounding objects; i.e. unaligned access in DImode
2238 via AND address can alias all surrounding object types except those
2239 with aligment 8 or higher. */
2240 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
2242 if (GET_CODE (x
) == AND
2243 && (!CONST_INT_P (XEXP (x
, 1))
2244 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
2246 if (GET_CODE (y
) == AND
2247 && (!CONST_INT_P (XEXP (y
, 1))
2248 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
2251 /* Differing symbols not accessed via AND never alias. */
2252 if (GET_CODE (x_base
) == SYMBOL_REF
&& GET_CODE (y_base
) == SYMBOL_REF
)
2253 return compare_base_symbol_refs (x_base
, y_base
) != 0;
2255 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
2258 if (unique_base_value_p (x_base
) || unique_base_value_p (y_base
))
2264 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2265 (or equal to) that of V. */
2268 refs_newer_value_p (const_rtx expr
, rtx v
)
2270 int minuid
= CSELIB_VAL_PTR (v
)->uid
;
2271 subrtx_iterator::array_type array
;
2272 FOR_EACH_SUBRTX (iter
, array
, expr
, NONCONST
)
2273 if (GET_CODE (*iter
) == VALUE
&& CSELIB_VAL_PTR (*iter
)->uid
>= minuid
)
2278 /* Convert the address X into something we can use. This is done by returning
2279 it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2280 we call cselib to get a more useful rtx. */
2286 struct elt_loc_list
*l
;
2288 if (GET_CODE (x
) != VALUE
)
2290 if ((GET_CODE (x
) == PLUS
|| GET_CODE (x
) == MINUS
)
2291 && GET_CODE (XEXP (x
, 0)) == VALUE
2292 && CONST_SCALAR_INT_P (XEXP (x
, 1)))
2294 rtx op0
= get_addr (XEXP (x
, 0));
2295 if (op0
!= XEXP (x
, 0))
2298 if (GET_CODE (x
) == PLUS
2299 && poly_int_rtx_p (XEXP (x
, 1), &c
))
2300 return plus_constant (GET_MODE (x
), op0
, c
);
2301 return simplify_gen_binary (GET_CODE (x
), GET_MODE (x
),
2307 v
= CSELIB_VAL_PTR (x
);
2310 bool have_equivs
= cselib_have_permanent_equivalences ();
2312 v
= canonical_cselib_val (v
);
2313 for (l
= v
->locs
; l
; l
= l
->next
)
2314 if (CONSTANT_P (l
->loc
))
2316 for (l
= v
->locs
; l
; l
= l
->next
)
2317 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
)
2318 /* Avoid infinite recursion when potentially dealing with
2319 var-tracking artificial equivalences, by skipping the
2320 equivalences themselves, and not choosing expressions
2321 that refer to newer VALUEs. */
2323 || (GET_CODE (l
->loc
) != VALUE
2324 && !refs_newer_value_p (l
->loc
, x
))))
2328 for (l
= v
->locs
; l
; l
= l
->next
)
2330 || (GET_CODE (l
->loc
) != VALUE
2331 && !refs_newer_value_p (l
->loc
, x
)))
2333 /* Return the canonical value. */
2337 return v
->locs
->loc
;
2342 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2343 where SIZE is the size in bytes of the memory reference. If ADDR
2344 is not modified by the memory reference then ADDR is returned. */
2347 addr_side_effect_eval (rtx addr
, poly_int64 size
, int n_refs
)
2349 poly_int64 offset
= 0;
2351 switch (GET_CODE (addr
))
2354 offset
= (n_refs
+ 1) * size
;
2357 offset
= -(n_refs
+ 1) * size
;
2360 offset
= n_refs
* size
;
2363 offset
= -n_refs
* size
;
2370 addr
= plus_constant (GET_MODE (addr
), XEXP (addr
, 0), offset
);
2371 addr
= canon_rtx (addr
);
2376 /* Return TRUE if an object X sized at XSIZE bytes and another object
2377 Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2378 any of the sizes is zero, assume an overlap, otherwise use the
2379 absolute value of the sizes as the actual sizes. */
2382 offset_overlap_p (poly_int64 c
, poly_int64 xsize
, poly_int64 ysize
)
2384 if (known_eq (xsize
, 0) || known_eq (ysize
, 0))
2387 if (maybe_ge (c
, 0))
2388 return maybe_gt (maybe_lt (xsize
, 0) ? -xsize
: xsize
, c
);
2390 return maybe_gt (maybe_lt (ysize
, 0) ? -ysize
: ysize
, -c
);
2393 /* Return one if X and Y (memory addresses) reference the
2394 same location in memory or if the references overlap.
2395 Return zero if they do not overlap, else return
2396 minus one in which case they still might reference the same location.
2398 C is an offset accumulator. When
2399 C is nonzero, we are testing aliases between X and Y + C.
2400 XSIZE is the size in bytes of the X reference,
2401 similarly YSIZE is the size in bytes for Y.
2402 Expect that canon_rtx has been already called for X and Y.
2404 If XSIZE or YSIZE is zero, we do not know the amount of memory being
2405 referenced (the reference was BLKmode), so make the most pessimistic
2408 If XSIZE or YSIZE is negative, we may access memory outside the object
2409 being referenced as a side effect. This can happen when using AND to
2410 align memory references, as is done on the Alpha.
2412 Nice to notice that varying addresses cannot conflict with fp if no
2413 local variables had their addresses taken, but that's too hard now.
2415 ??? Contrary to the tree alias oracle this does not return
2416 one for X + non-constant and Y + non-constant when X and Y are equal.
2417 If that is fixed the TBAA hack for union type-punning can be removed. */
2420 memrefs_conflict_p (poly_int64 xsize
, rtx x
, poly_int64 ysize
, rtx y
,
2423 if (GET_CODE (x
) == VALUE
)
2427 struct elt_loc_list
*l
= NULL
;
2428 if (CSELIB_VAL_PTR (x
))
2429 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (x
))->locs
;
2431 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, y
))
2438 /* Don't call get_addr if y is the same VALUE. */
2442 if (GET_CODE (y
) == VALUE
)
2446 struct elt_loc_list
*l
= NULL
;
2447 if (CSELIB_VAL_PTR (y
))
2448 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (y
))->locs
;
2450 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, x
))
2457 /* Don't call get_addr if x is the same VALUE. */
2461 if (GET_CODE (x
) == HIGH
)
2463 else if (GET_CODE (x
) == LO_SUM
)
2466 x
= addr_side_effect_eval (x
, maybe_lt (xsize
, 0) ? -xsize
: xsize
, 0);
2467 if (GET_CODE (y
) == HIGH
)
2469 else if (GET_CODE (y
) == LO_SUM
)
2472 y
= addr_side_effect_eval (y
, maybe_lt (ysize
, 0) ? -ysize
: ysize
, 0);
2474 if (GET_CODE (x
) == SYMBOL_REF
&& GET_CODE (y
) == SYMBOL_REF
)
2476 HOST_WIDE_INT distance
= 0;
2477 int cmp
= compare_base_symbol_refs (x
, y
, &distance
);
2479 /* If both decls are the same, decide by offsets. */
2481 return offset_overlap_p (c
+ distance
, xsize
, ysize
);
2482 /* Assume a potential overlap for symbolic addresses that went
2483 through alignment adjustments (i.e., that have negative
2484 sizes), because we can't know how far they are from each
2486 if (maybe_lt (xsize
, 0) || maybe_lt (ysize
, 0))
2488 /* If decls are different or we know by offsets that there is no overlap,
2490 if (!cmp
|| !offset_overlap_p (c
+ distance
, xsize
, ysize
))
2492 /* Decls may or may not be different and offsets overlap....*/
2495 else if (rtx_equal_for_memref_p (x
, y
))
2497 return offset_overlap_p (c
, xsize
, ysize
);
2500 /* This code used to check for conflicts involving stack references and
2501 globals but the base address alias code now handles these cases. */
2503 if (GET_CODE (x
) == PLUS
)
2505 /* The fact that X is canonicalized means that this
2506 PLUS rtx is canonicalized. */
2507 rtx x0
= XEXP (x
, 0);
2508 rtx x1
= XEXP (x
, 1);
2510 /* However, VALUEs might end up in different positions even in
2511 canonical PLUSes. Comparing their addresses is enough. */
2513 return memrefs_conflict_p (xsize
, x1
, ysize
, const0_rtx
, c
);
2515 return memrefs_conflict_p (xsize
, x0
, ysize
, const0_rtx
, c
);
2517 poly_int64 cx1
, cy1
;
2518 if (GET_CODE (y
) == PLUS
)
2520 /* The fact that Y is canonicalized means that this
2521 PLUS rtx is canonicalized. */
2522 rtx y0
= XEXP (y
, 0);
2523 rtx y1
= XEXP (y
, 1);
2526 return memrefs_conflict_p (xsize
, x1
, ysize
, y0
, c
);
2528 return memrefs_conflict_p (xsize
, x0
, ysize
, y1
, c
);
2530 if (rtx_equal_for_memref_p (x1
, y1
))
2531 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2532 if (rtx_equal_for_memref_p (x0
, y0
))
2533 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
2534 if (poly_int_rtx_p (x1
, &cx1
))
2536 if (poly_int_rtx_p (y1
, &cy1
))
2537 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
2540 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- cx1
);
2542 else if (poly_int_rtx_p (y1
, &cy1
))
2543 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ cy1
);
2547 else if (poly_int_rtx_p (x1
, &cx1
))
2548 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- cx1
);
2550 else if (GET_CODE (y
) == PLUS
)
2552 /* The fact that Y is canonicalized means that this
2553 PLUS rtx is canonicalized. */
2554 rtx y0
= XEXP (y
, 0);
2555 rtx y1
= XEXP (y
, 1);
2558 return memrefs_conflict_p (xsize
, const0_rtx
, ysize
, y1
, c
);
2560 return memrefs_conflict_p (xsize
, const0_rtx
, ysize
, y0
, c
);
2563 if (poly_int_rtx_p (y1
, &cy1
))
2564 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ cy1
);
2569 if (GET_CODE (x
) == GET_CODE (y
))
2570 switch (GET_CODE (x
))
2574 /* Handle cases where we expect the second operands to be the
2575 same, and check only whether the first operand would conflict
2578 rtx x1
= canon_rtx (XEXP (x
, 1));
2579 rtx y1
= canon_rtx (XEXP (y
, 1));
2580 if (! rtx_equal_for_memref_p (x1
, y1
))
2582 x0
= canon_rtx (XEXP (x
, 0));
2583 y0
= canon_rtx (XEXP (y
, 0));
2584 if (rtx_equal_for_memref_p (x0
, y0
))
2585 return offset_overlap_p (c
, xsize
, ysize
);
2587 /* Can't properly adjust our sizes. */
2589 if (!poly_int_rtx_p (x1
, &c1
)
2590 || !can_div_trunc_p (xsize
, c1
, &xsize
)
2591 || !can_div_trunc_p (ysize
, c1
, &ysize
)
2592 || !can_div_trunc_p (c
, c1
, &c
))
2594 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2601 /* Deal with alignment ANDs by adjusting offset and size so as to
2602 cover the maximum range, without taking any previously known
2603 alignment into account. Make a size negative after such an
2604 adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2605 assume a potential overlap, because they may end up in contiguous
2606 memory locations and the stricter-alignment access may span over
2608 if (GET_CODE (x
) == AND
&& CONST_INT_P (XEXP (x
, 1)))
2610 HOST_WIDE_INT sc
= INTVAL (XEXP (x
, 1));
2611 unsigned HOST_WIDE_INT uc
= sc
;
2612 if (sc
< 0 && pow2_or_zerop (-uc
))
2614 if (maybe_gt (xsize
, 0))
2616 if (maybe_ne (xsize
, 0))
2619 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2623 if (GET_CODE (y
) == AND
&& CONST_INT_P (XEXP (y
, 1)))
2625 HOST_WIDE_INT sc
= INTVAL (XEXP (y
, 1));
2626 unsigned HOST_WIDE_INT uc
= sc
;
2627 if (sc
< 0 && pow2_or_zerop (-uc
))
2629 if (maybe_gt (ysize
, 0))
2631 if (maybe_ne (ysize
, 0))
2634 return memrefs_conflict_p (xsize
, x
,
2635 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2642 if (poly_int_rtx_p (x
, &cx
) && poly_int_rtx_p (y
, &cy
))
2645 return offset_overlap_p (c
, xsize
, ysize
);
2648 if (GET_CODE (x
) == CONST
)
2650 if (GET_CODE (y
) == CONST
)
2651 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2652 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2654 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2657 if (GET_CODE (y
) == CONST
)
2658 return memrefs_conflict_p (xsize
, x
, ysize
,
2659 canon_rtx (XEXP (y
, 0)), c
);
2661 /* Assume a potential overlap for symbolic addresses that went
2662 through alignment adjustments (i.e., that have negative
2663 sizes), because we can't know how far they are from each
2666 return (maybe_lt (xsize
, 0)
2667 || maybe_lt (ysize
, 0)
2668 || offset_overlap_p (c
, xsize
, ysize
));
2676 /* Functions to compute memory dependencies.
2678 Since we process the insns in execution order, we can build tables
2679 to keep track of what registers are fixed (and not aliased), what registers
2680 are varying in known ways, and what registers are varying in unknown
2683 If both memory references are volatile, then there must always be a
2684 dependence between the two references, since their order cannot be
2685 changed. A volatile and non-volatile reference can be interchanged
2688 We also must allow AND addresses, because they may generate accesses
2689 outside the object being referenced. This is used to generate aligned
2690 addresses from unaligned addresses, for instance, the alpha
2691 storeqi_unaligned pattern. */
2693 /* Read dependence: X is read after read in MEM takes place. There can
2694 only be a dependence here if both reads are volatile, or if either is
2695 an explicit barrier. */
2698 read_dependence (const_rtx mem
, const_rtx x
)
2700 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2702 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2703 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2708 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2711 decl_for_component_ref (tree x
)
2715 x
= TREE_OPERAND (x
, 0);
2717 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2719 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
2722 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2723 for the offset of the field reference. *KNOWN_P says whether the
2727 adjust_offset_for_component_ref (tree x
, bool *known_p
,
2734 tree xoffset
= component_ref_field_offset (x
);
2735 tree field
= TREE_OPERAND (x
, 1);
2736 if (!poly_int_tree_p (xoffset
))
2742 poly_offset_int woffset
2743 = (wi::to_poly_offset (xoffset
)
2744 + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field
))
2745 >> LOG2_BITS_PER_UNIT
)
2747 if (!woffset
.to_shwi (offset
))
2753 x
= TREE_OPERAND (x
, 0);
2755 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2758 /* Return true if we can determine the exprs corresponding to memrefs
2759 X and Y and they do not overlap.
2760 If LOOP_VARIANT is set, skip offset-based disambiguation */
2763 nonoverlapping_memrefs_p (const_rtx x
, const_rtx y
, bool loop_invariant
)
2765 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
2768 bool moffsetx_known_p
, moffsety_known_p
;
2769 poly_int64 moffsetx
= 0, moffsety
= 0;
2770 poly_int64 offsetx
= 0, offsety
= 0, sizex
, sizey
;
2772 /* Unless both have exprs, we can't tell anything. */
2773 if (exprx
== 0 || expry
== 0)
2776 /* For spill-slot accesses make sure we have valid offsets. */
2777 if ((exprx
== get_spill_slot_decl (false)
2778 && ! MEM_OFFSET_KNOWN_P (x
))
2779 || (expry
== get_spill_slot_decl (false)
2780 && ! MEM_OFFSET_KNOWN_P (y
)))
2783 /* If the field reference test failed, look at the DECLs involved. */
2784 moffsetx_known_p
= MEM_OFFSET_KNOWN_P (x
);
2785 if (moffsetx_known_p
)
2786 moffsetx
= MEM_OFFSET (x
);
2787 if (TREE_CODE (exprx
) == COMPONENT_REF
)
2789 tree t
= decl_for_component_ref (exprx
);
2792 adjust_offset_for_component_ref (exprx
, &moffsetx_known_p
, &moffsetx
);
2796 moffsety_known_p
= MEM_OFFSET_KNOWN_P (y
);
2797 if (moffsety_known_p
)
2798 moffsety
= MEM_OFFSET (y
);
2799 if (TREE_CODE (expry
) == COMPONENT_REF
)
2801 tree t
= decl_for_component_ref (expry
);
2804 adjust_offset_for_component_ref (expry
, &moffsety_known_p
, &moffsety
);
2808 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2811 /* If we refer to different gimple registers, or one gimple register
2812 and one non-gimple-register, we know they can't overlap. First,
2813 gimple registers don't have their addresses taken. Now, there
2814 could be more than one stack slot for (different versions of) the
2815 same gimple register, but we can presumably tell they don't
2816 overlap based on offsets from stack base addresses elsewhere.
2817 It's important that we don't proceed to DECL_RTL, because gimple
2818 registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2819 able to do anything about them since no SSA information will have
2820 remained to guide it. */
2821 if (is_gimple_reg (exprx
) || is_gimple_reg (expry
))
2822 return exprx
!= expry
2823 || (moffsetx_known_p
&& moffsety_known_p
2824 && MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
)
2825 && !offset_overlap_p (moffsety
- moffsetx
,
2826 MEM_SIZE (x
), MEM_SIZE (y
)));
2828 /* With invalid code we can end up storing into the constant pool.
2829 Bail out to avoid ICEing when creating RTL for this.
2830 See gfortran.dg/lto/20091028-2_0.f90. */
2831 if (TREE_CODE (exprx
) == CONST_DECL
2832 || TREE_CODE (expry
) == CONST_DECL
)
2835 /* If one decl is known to be a function or label in a function and
2836 the other is some kind of data, they can't overlap. */
2837 if ((TREE_CODE (exprx
) == FUNCTION_DECL
2838 || TREE_CODE (exprx
) == LABEL_DECL
)
2839 != (TREE_CODE (expry
) == FUNCTION_DECL
2840 || TREE_CODE (expry
) == LABEL_DECL
))
2843 /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2844 living in multiple places), we can't tell anything. Exception
2845 are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2846 if ((!DECL_RTL_SET_P (exprx
) && TREE_CODE (exprx
) != FUNCTION_DECL
)
2847 || (!DECL_RTL_SET_P (expry
) && TREE_CODE (expry
) != FUNCTION_DECL
))
2850 rtlx
= DECL_RTL (exprx
);
2851 rtly
= DECL_RTL (expry
);
2853 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2854 can't overlap unless they are the same because we never reuse that part
2855 of the stack frame used for locals for spilled pseudos. */
2856 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2857 && ! rtx_equal_p (rtlx
, rtly
))
2860 /* If we have MEMs referring to different address spaces (which can
2861 potentially overlap), we cannot easily tell from the addresses
2862 whether the references overlap. */
2863 if (MEM_P (rtlx
) && MEM_P (rtly
)
2864 && MEM_ADDR_SPACE (rtlx
) != MEM_ADDR_SPACE (rtly
))
2867 /* Get the base and offsets of both decls. If either is a register, we
2868 know both are and are the same, so use that as the base. The only
2869 we can avoid overlap is if we can deduce that they are nonoverlapping
2870 pieces of that decl, which is very rare. */
2871 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2872 basex
= strip_offset_and_add (basex
, &offsetx
);
2874 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2875 basey
= strip_offset_and_add (basey
, &offsety
);
2877 /* If the bases are different, we know they do not overlap if both
2878 are constants or if one is a constant and the other a pointer into the
2879 stack frame. Otherwise a different base means we can't tell if they
2881 if (compare_base_decls (exprx
, expry
) == 0)
2882 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2883 || (CONSTANT_P (basex
) && REG_P (basey
)
2884 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2885 || (CONSTANT_P (basey
) && REG_P (basex
)
2886 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2888 /* Offset based disambiguation not appropriate for loop invariant */
2892 /* Offset based disambiguation is OK even if we do not know that the
2893 declarations are necessarily different
2894 (i.e. compare_base_decls (exprx, expry) == -1) */
2896 sizex
= (!MEM_P (rtlx
) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx
)))
2897 : MEM_SIZE_KNOWN_P (rtlx
) ? MEM_SIZE (rtlx
)
2899 sizey
= (!MEM_P (rtly
) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly
)))
2900 : MEM_SIZE_KNOWN_P (rtly
) ? MEM_SIZE (rtly
)
2903 /* If we have an offset for either memref, it can update the values computed
2905 if (moffsetx_known_p
)
2906 offsetx
+= moffsetx
, sizex
-= moffsetx
;
2907 if (moffsety_known_p
)
2908 offsety
+= moffsety
, sizey
-= moffsety
;
2910 /* If a memref has both a size and an offset, we can use the smaller size.
2911 We can't do this if the offset isn't known because we must view this
2912 memref as being anywhere inside the DECL's MEM. */
2913 if (MEM_SIZE_KNOWN_P (x
) && moffsetx_known_p
)
2914 sizex
= MEM_SIZE (x
);
2915 if (MEM_SIZE_KNOWN_P (y
) && moffsety_known_p
)
2916 sizey
= MEM_SIZE (y
);
2918 return !ranges_maybe_overlap_p (offsetx
, sizex
, offsety
, sizey
);
2921 /* Helper for true_dependence and canon_true_dependence.
2922 Checks for true dependence: X is read after store in MEM takes place.
2924 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2925 NULL_RTX, and the canonical addresses of MEM and X are both computed
2926 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2928 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2930 Returns true if there is a true dependence, false otherwise. */
2933 true_dependence_1 (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
2934 const_rtx x
, rtx x_addr
, bool mem_canonicalized
)
2940 gcc_checking_assert (mem_canonicalized
? (mem_addr
!= NULL_RTX
)
2941 : (mem_addr
== NULL_RTX
&& x_addr
== NULL_RTX
));
2943 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2946 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2947 This is used in epilogue deallocation functions, and in cselib. */
2948 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2950 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2952 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2953 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2957 x_addr
= XEXP (x
, 0);
2958 x_addr
= get_addr (x_addr
);
2962 mem_addr
= XEXP (mem
, 0);
2963 if (mem_mode
== VOIDmode
)
2964 mem_mode
= GET_MODE (mem
);
2966 true_mem_addr
= get_addr (mem_addr
);
2968 /* Read-only memory is by definition never modified, and therefore can't
2969 conflict with anything. However, don't assume anything when AND
2970 addresses are involved and leave to the code below to determine
2971 dependence. We don't expect to find read-only set on MEM, but
2972 stupid user tricks can produce them, so don't die. */
2973 if (MEM_READONLY_P (x
)
2974 && GET_CODE (x_addr
) != AND
2975 && GET_CODE (true_mem_addr
) != AND
)
2978 /* If we have MEMs referring to different address spaces (which can
2979 potentially overlap), we cannot easily tell from the addresses
2980 whether the references overlap. */
2981 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2984 base
= find_base_term (x_addr
);
2985 if (base
&& (GET_CODE (base
) == LABEL_REF
2986 || (GET_CODE (base
) == SYMBOL_REF
2987 && CONSTANT_POOL_ADDRESS_P (base
))))
2990 rtx mem_base
= find_base_term (true_mem_addr
);
2991 if (! base_alias_check (x_addr
, base
, true_mem_addr
, mem_base
,
2992 GET_MODE (x
), mem_mode
))
2995 x_addr
= canon_rtx (x_addr
);
2996 if (!mem_canonicalized
)
2997 mem_addr
= canon_rtx (true_mem_addr
);
2999 if ((ret
= memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
3000 SIZE_FOR_MODE (x
), x_addr
, 0)) != -1)
3003 if (mems_in_disjoint_alias_sets_p (x
, mem
))
3006 if (nonoverlapping_memrefs_p (mem
, x
, false))
3009 return rtx_refs_may_alias_p (x
, mem
, true);
3012 /* True dependence: X is read after store in MEM takes place. */
3015 true_dependence (const_rtx mem
, machine_mode mem_mode
, const_rtx x
)
3017 return true_dependence_1 (mem
, mem_mode
, NULL_RTX
,
3018 x
, NULL_RTX
, /*mem_canonicalized=*/false);
3021 /* Canonical true dependence: X is read after store in MEM takes place.
3022 Variant of true_dependence which assumes MEM has already been
3023 canonicalized (hence we no longer do that here).
3024 The mem_addr argument has been added, since true_dependence_1 computed
3025 this value prior to canonicalizing. */
3028 canon_true_dependence (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
3029 const_rtx x
, rtx x_addr
)
3031 return true_dependence_1 (mem
, mem_mode
, mem_addr
,
3032 x
, x_addr
, /*mem_canonicalized=*/true);
3035 /* Returns true if a write to X might alias a previous read from
3036 (or, if WRITEP is true, a write to) MEM.
3037 If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3038 and X_MODE the mode for that access.
3039 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3042 write_dependence_p (const_rtx mem
,
3043 const_rtx x
, machine_mode x_mode
, rtx x_addr
,
3044 bool mem_canonicalized
, bool x_canonicalized
, bool writep
)
3047 rtx true_mem_addr
, true_x_addr
;
3051 gcc_checking_assert (x_canonicalized
3052 ? (x_addr
!= NULL_RTX
3053 && (x_mode
!= VOIDmode
|| GET_MODE (x
) == VOIDmode
))
3054 : (x_addr
== NULL_RTX
&& x_mode
== VOIDmode
));
3056 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
3059 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3060 This is used in epilogue deallocation functions. */
3061 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
3063 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
3065 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
3066 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
3070 x_addr
= XEXP (x
, 0);
3071 true_x_addr
= get_addr (x_addr
);
3073 mem_addr
= XEXP (mem
, 0);
3074 true_mem_addr
= get_addr (mem_addr
);
3076 /* A read from read-only memory can't conflict with read-write memory.
3077 Don't assume anything when AND addresses are involved and leave to
3078 the code below to determine dependence. */
3080 && MEM_READONLY_P (mem
)
3081 && GET_CODE (true_x_addr
) != AND
3082 && GET_CODE (true_mem_addr
) != AND
)
3085 /* If we have MEMs referring to different address spaces (which can
3086 potentially overlap), we cannot easily tell from the addresses
3087 whether the references overlap. */
3088 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
3091 base
= find_base_term (true_mem_addr
);
3094 && (GET_CODE (base
) == LABEL_REF
3095 || (GET_CODE (base
) == SYMBOL_REF
3096 && CONSTANT_POOL_ADDRESS_P (base
))))
3099 rtx x_base
= find_base_term (true_x_addr
);
3100 if (! base_alias_check (true_x_addr
, x_base
, true_mem_addr
, base
,
3101 GET_MODE (x
), GET_MODE (mem
)))
3104 if (!x_canonicalized
)
3106 x_addr
= canon_rtx (true_x_addr
);
3107 x_mode
= GET_MODE (x
);
3109 if (!mem_canonicalized
)
3110 mem_addr
= canon_rtx (true_mem_addr
);
3112 if ((ret
= memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
3113 GET_MODE_SIZE (x_mode
), x_addr
, 0)) != -1)
3116 if (nonoverlapping_memrefs_p (x
, mem
, false))
3119 return rtx_refs_may_alias_p (x
, mem
, false);
3122 /* Anti dependence: X is written after read in MEM takes place. */
3125 anti_dependence (const_rtx mem
, const_rtx x
)
3127 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
3128 /*mem_canonicalized=*/false,
3129 /*x_canonicalized*/false, /*writep=*/false);
3132 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3133 Also, consider X in X_MODE (which might be from an enclosing
3134 STRICT_LOW_PART / ZERO_EXTRACT).
3135 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3138 canon_anti_dependence (const_rtx mem
, bool mem_canonicalized
,
3139 const_rtx x
, machine_mode x_mode
, rtx x_addr
)
3141 return write_dependence_p (mem
, x
, x_mode
, x_addr
,
3142 mem_canonicalized
, /*x_canonicalized=*/true,
3146 /* Output dependence: X is written after store in MEM takes place. */
3149 output_dependence (const_rtx mem
, const_rtx x
)
3151 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
3152 /*mem_canonicalized=*/false,
3153 /*x_canonicalized*/false, /*writep=*/true);
3156 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3157 Also, consider X in X_MODE (which might be from an enclosing
3158 STRICT_LOW_PART / ZERO_EXTRACT).
3159 If MEM_CANONICALIZED is true, MEM is canonicalized. */
3162 canon_output_dependence (const_rtx mem
, bool mem_canonicalized
,
3163 const_rtx x
, machine_mode x_mode
, rtx x_addr
)
3165 return write_dependence_p (mem
, x
, x_mode
, x_addr
,
3166 mem_canonicalized
, /*x_canonicalized=*/true,
3172 /* Check whether X may be aliased with MEM. Don't do offset-based
3173 memory disambiguation & TBAA. */
3175 may_alias_p (const_rtx mem
, const_rtx x
)
3177 rtx x_addr
, mem_addr
;
3179 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
3182 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3183 This is used in epilogue deallocation functions. */
3184 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
3186 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
3188 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
3189 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
3192 x_addr
= XEXP (x
, 0);
3193 x_addr
= get_addr (x_addr
);
3195 mem_addr
= XEXP (mem
, 0);
3196 mem_addr
= get_addr (mem_addr
);
3198 /* Read-only memory is by definition never modified, and therefore can't
3199 conflict with anything. However, don't assume anything when AND
3200 addresses are involved and leave to the code below to determine
3201 dependence. We don't expect to find read-only set on MEM, but
3202 stupid user tricks can produce them, so don't die. */
3203 if (MEM_READONLY_P (x
)
3204 && GET_CODE (x_addr
) != AND
3205 && GET_CODE (mem_addr
) != AND
)
3208 /* If we have MEMs referring to different address spaces (which can
3209 potentially overlap), we cannot easily tell from the addresses
3210 whether the references overlap. */
3211 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
3214 rtx x_base
= find_base_term (x_addr
);
3215 rtx mem_base
= find_base_term (mem_addr
);
3216 if (! base_alias_check (x_addr
, x_base
, mem_addr
, mem_base
,
3217 GET_MODE (x
), GET_MODE (mem_addr
)))
3220 if (nonoverlapping_memrefs_p (mem
, x
, true))
3223 /* TBAA not valid for loop_invarint */
3224 return rtx_refs_may_alias_p (x
, mem
, false);
3228 init_alias_target (void)
3232 if (!arg_base_value
)
3233 arg_base_value
= gen_rtx_ADDRESS (VOIDmode
, 0);
3235 memset (static_reg_base_value
, 0, sizeof static_reg_base_value
);
3237 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3238 /* Check whether this register can hold an incoming pointer
3239 argument. FUNCTION_ARG_REGNO_P tests outgoing register
3240 numbers, so translate if necessary due to register windows. */
3241 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
3242 && targetm
.hard_regno_mode_ok (i
, Pmode
))
3243 static_reg_base_value
[i
] = arg_base_value
;
3245 /* RTL code is required to be consistent about whether it uses the
3246 stack pointer, the frame pointer or the argument pointer to
3247 access a given area of the frame. We can therefore use the
3248 base address to distinguish between the different areas. */
3249 static_reg_base_value
[STACK_POINTER_REGNUM
]
3250 = unique_base_value (UNIQUE_BASE_VALUE_SP
);
3251 static_reg_base_value
[ARG_POINTER_REGNUM
]
3252 = unique_base_value (UNIQUE_BASE_VALUE_ARGP
);
3253 static_reg_base_value
[FRAME_POINTER_REGNUM
]
3254 = unique_base_value (UNIQUE_BASE_VALUE_FP
);
3256 /* The above rules extend post-reload, with eliminations applying
3257 consistently to each of the three pointers. Cope with cases in
3258 which the frame pointer is eliminated to the hard frame pointer
3259 rather than the stack pointer. */
3260 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
3261 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
3262 = unique_base_value (UNIQUE_BASE_VALUE_HFP
);
3265 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3266 to be memory reference. */
3267 static bool memory_modified
;
3269 memory_modified_1 (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
3273 if (anti_dependence (x
, (const_rtx
)data
) || output_dependence (x
, (const_rtx
)data
))
3274 memory_modified
= true;
3279 /* Return true when INSN possibly modify memory contents of MEM
3280 (i.e. address can be modified). */
3282 memory_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
3286 /* Conservatively assume all non-readonly MEMs might be modified in
3290 memory_modified
= false;
3291 note_stores (as_a
<const rtx_insn
*> (insn
), memory_modified_1
,
3292 CONST_CAST_RTX(mem
));
3293 return memory_modified
;
3296 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3300 init_alias_analysis (void)
3302 const bool frame_pointer_eliminated
3304 && !frame_pointer_needed
3305 && targetm
.can_eliminate (FRAME_POINTER_REGNUM
, STACK_POINTER_REGNUM
);
3306 unsigned int maxreg
= max_reg_num ();
3315 timevar_push (TV_ALIAS_ANALYSIS
);
3317 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
, true);
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);
3362 /* Assume nothing will change this iteration of the loop. */
3365 /* We want to assign the same IDs each iteration of this loop, so
3366 start counting from one each iteration of the loop. */
3369 /* We're at the start of the function each iteration through the
3370 loop, so we're copying arguments. */
3371 copying_arguments
= true;
3373 /* Wipe the potential alias information clean for this pass. */
3374 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
3376 /* Wipe the reg_seen array clean. */
3377 bitmap_clear (reg_seen
);
3379 /* Initialize the alias information for this pass. */
3380 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3381 if (static_reg_base_value
[i
]
3382 /* Don't treat the hard frame pointer as special if we
3383 eliminated the frame pointer to the stack pointer. */
3384 && !(i
== HARD_FRAME_POINTER_REGNUM
&& frame_pointer_eliminated
))
3386 new_reg_base_value
[i
] = static_reg_base_value
[i
];
3387 bitmap_set_bit (reg_seen
, i
);
3390 /* Walk the insns adding values to the new_reg_base_value array. */
3391 for (i
= 0; i
< rpo_cnt
; i
++)
3393 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, rpo
[i
]);
3394 FOR_BB_INSNS (bb
, insn
)
3396 if (NONDEBUG_INSN_P (insn
))
3400 /* Treat the hard frame pointer as special unless we
3401 eliminated the frame pointer to the stack pointer. */
3402 if (!frame_pointer_eliminated
3403 && modified_in_p (hard_frame_pointer_rtx
, insn
))
3406 /* If this insn has a noalias note, process it, Otherwise,
3407 scan for sets. A simple set will have no side effects
3408 which could change the base value of any other register. */
3409 if (GET_CODE (PATTERN (insn
)) == SET
3410 && REG_NOTES (insn
) != 0
3411 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
3412 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
3414 note_stores (insn
, record_set
, NULL
);
3416 set
= single_set (insn
);
3419 && REG_P (SET_DEST (set
))
3420 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
3422 unsigned int regno
= REGNO (SET_DEST (set
));
3423 rtx src
= SET_SRC (set
);
3426 note
= find_reg_equal_equiv_note (insn
);
3427 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
3428 && DF_REG_DEF_COUNT (regno
) != 1)
3432 if (note
!= NULL_RTX
3433 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
3434 && ! rtx_varies_p (XEXP (note
, 0), 1)
3435 && ! reg_overlap_mentioned_p (SET_DEST (set
),
3438 set_reg_known_value (regno
, XEXP (note
, 0));
3439 set_reg_known_equiv_p (regno
,
3440 REG_NOTE_KIND (note
) == REG_EQUIV
);
3442 else if (DF_REG_DEF_COUNT (regno
) == 1
3443 && GET_CODE (src
) == PLUS
3444 && REG_P (XEXP (src
, 0))
3445 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
3446 && poly_int_rtx_p (XEXP (src
, 1), &offset
))
3448 t
= plus_constant (GET_MODE (src
), t
, offset
);
3449 set_reg_known_value (regno
, t
);
3450 set_reg_known_equiv_p (regno
, false);
3452 else if (DF_REG_DEF_COUNT (regno
) == 1
3453 && ! rtx_varies_p (src
, 1))
3455 set_reg_known_value (regno
, src
);
3456 set_reg_known_equiv_p (regno
, false);
3460 else if (NOTE_P (insn
)
3461 && NOTE_KIND (insn
) == NOTE_INSN_FUNCTION_BEG
)
3462 copying_arguments
= false;
3466 /* Now propagate values from new_reg_base_value to reg_base_value. */
3467 gcc_assert (maxreg
== (unsigned int) max_reg_num ());
3469 for (ui
= 0; ui
< maxreg
; ui
++)
3471 if (new_reg_base_value
[ui
]
3472 && new_reg_base_value
[ui
] != (*reg_base_value
)[ui
]
3473 && ! rtx_equal_p (new_reg_base_value
[ui
], (*reg_base_value
)[ui
]))
3475 (*reg_base_value
)[ui
] = new_reg_base_value
[ui
];
3480 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
3483 /* Fill in the remaining entries. */
3484 FOR_EACH_VEC_ELT (*reg_known_value
, i
, val
)
3486 int regno
= i
+ FIRST_PSEUDO_REGISTER
;
3488 set_reg_known_value (regno
, regno_reg_rtx
[regno
]);
3492 free (new_reg_base_value
);
3493 new_reg_base_value
= 0;
3494 sbitmap_free (reg_seen
);
3496 timevar_pop (TV_ALIAS_ANALYSIS
);
3499 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3500 Special API for var-tracking pass purposes. */
3503 vt_equate_reg_base_value (const_rtx reg1
, const_rtx reg2
)
3505 (*reg_base_value
)[REGNO (reg1
)] = REG_BASE_VALUE (reg2
);
3509 end_alias_analysis (void)
3511 old_reg_base_value
= reg_base_value
;
3512 vec_free (reg_known_value
);
3513 sbitmap_free (reg_known_equiv_p
);
3517 dump_alias_stats_in_alias_c (FILE *s
)
3519 fprintf (s
, " TBAA oracle: %llu disambiguations %llu queries\n"
3520 " %llu are in alias set 0\n"
3521 " %llu queries asked about the same object\n"
3522 " %llu queries asked about the same alias set\n"
3523 " %llu access volatile\n"
3524 " %llu are dependent in the DAG\n"
3525 " %llu are aritificially in conflict with void *\n",
3526 alias_stats
.num_disambiguated
,
3527 alias_stats
.num_alias_zero
+ alias_stats
.num_same_alias_set
3528 + alias_stats
.num_same_objects
+ alias_stats
.num_volatile
3529 + alias_stats
.num_dag
+ alias_stats
.num_disambiguated
3530 + alias_stats
.num_universal
,
3531 alias_stats
.num_alias_zero
, alias_stats
.num_same_alias_set
,
3532 alias_stats
.num_same_objects
, alias_stats
.num_volatile
,
3533 alias_stats
.num_dag
, alias_stats
.num_universal
);
3535 #include "gt-alias.h"