1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
3 2007, 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
4 Contributed by John Carr (jfc@mit.edu).
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
36 #include "diagnostic-core.h"
38 #include "splay-tree.h"
40 #include "langhooks.h"
44 #include "tree-pass.h"
46 #include "tree-ssa-alias.h"
47 #include "pointer-set.h"
48 #include "tree-flow.h"
50 /* The aliasing API provided here solves related but different problems:
52 Say there exists (in c)
66 Consider the four questions:
68 Can a store to x1 interfere with px2->y1?
69 Can a store to x1 interfere with px2->z2?
71 Can a store to x1 change the value pointed to by with py?
72 Can a store to x1 change the value pointed to by with pz?
74 The answer to these questions can be yes, yes, yes, and maybe.
76 The first two questions can be answered with a simple examination
77 of the type system. If structure X contains a field of type Y then
78 a store through a pointer to an X can overwrite any field that is
79 contained (recursively) in an X (unless we know that px1 != px2).
81 The last two of the questions can be solved in the same way as the
82 first two questions but this is too conservative. The observation
83 is that in some cases analysis we can know if which (if any) fields
84 are addressed and if those addresses are used in bad ways. This
85 analysis may be language specific. In C, arbitrary operations may
86 be applied to pointers. However, there is some indication that
87 this may be too conservative for some C++ types.
89 The pass ipa-type-escape does this analysis for the types whose
90 instances do not escape across the compilation boundary.
92 Historically in GCC, these two problems were combined and a single
93 data structure was used to represent the solution to these
94 problems. We now have two similar but different data structures,
95 The data structure to solve the last two question is similar to the
96 first, but does not contain have the fields in it whose address are
97 never taken. For types that do escape the compilation unit, the
98 data structures will have identical information.
101 /* The alias sets assigned to MEMs assist the back-end in determining
102 which MEMs can alias which other MEMs. In general, two MEMs in
103 different alias sets cannot alias each other, with one important
104 exception. Consider something like:
106 struct S { int i; double d; };
108 a store to an `S' can alias something of either type `int' or type
109 `double'. (However, a store to an `int' cannot alias a `double'
110 and vice versa.) We indicate this via a tree structure that looks
118 (The arrows are directed and point downwards.)
119 In this situation we say the alias set for `struct S' is the
120 `superset' and that those for `int' and `double' are `subsets'.
122 To see whether two alias sets can point to the same memory, we must
123 see if either alias set is a subset of the other. We need not trace
124 past immediate descendants, however, since we propagate all
125 grandchildren up one level.
127 Alias set zero is implicitly a superset of all other alias sets.
128 However, this is no actual entry for alias set zero. It is an
129 error to attempt to explicitly construct a subset of zero. */
131 struct GTY(()) alias_set_entry_d {
132 /* The alias set number, as stored in MEM_ALIAS_SET. */
133 alias_set_type alias_set;
135 /* Nonzero if would have a child of zero: this effectively makes this
136 alias set the same as alias set zero. */
139 /* The children of the alias set. These are not just the immediate
140 children, but, in fact, all descendants. So, if we have:
142 struct T { struct S s; float f; }
144 continuing our example above, the children here will be all of
145 `int', `double', `float', and `struct S'. */
146 splay_tree GTY((param1_is (int), param2_is (int))) children;
148 typedef struct alias_set_entry_d *alias_set_entry;
150 static int rtx_equal_for_memref_p (const_rtx, const_rtx);
151 static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
152 static void record_set (rtx, const_rtx, void *);
153 static int base_alias_check (rtx, rtx, enum machine_mode,
155 static rtx find_base_value (rtx);
156 static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
157 static int insert_subset_children (splay_tree_node, void*);
158 static alias_set_entry get_alias_set_entry (alias_set_type);
159 static bool nonoverlapping_component_refs_p (const_tree, const_tree);
160 static tree decl_for_component_ref (tree);
161 static int write_dependence_p (const_rtx, const_rtx, int);
163 static void memory_modified_1 (rtx, const_rtx, void *);
165 /* Set up all info needed to perform alias analysis on memory references. */
167 /* Returns the size in bytes of the mode of X. */
168 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
170 /* Cap the number of passes we make over the insns propagating alias
171 information through set chains. 10 is a completely arbitrary choice. */
172 #define MAX_ALIAS_LOOP_PASSES 10
174 /* reg_base_value[N] gives an address to which register N is related.
175 If all sets after the first add or subtract to the current value
176 or otherwise modify it so it does not point to a different top level
177 object, reg_base_value[N] is equal to the address part of the source
180 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
181 expressions represent three types of base:
183 1. incoming arguments. There is just one ADDRESS to represent all
184 arguments, since we do not know at this level whether accesses
185 based on different arguments can alias. The ADDRESS has id 0.
187 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
188 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
189 Each of these rtxes has a separate ADDRESS associated with it,
190 each with a negative id.
192 GCC is (and is required to be) precise in which register it
193 chooses to access a particular region of stack. We can therefore
194 assume that accesses based on one of these rtxes do not alias
195 accesses based on another of these rtxes.
197 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
198 Each such piece of memory has a separate ADDRESS associated
199 with it, each with an id greater than 0.
201 Accesses based on one ADDRESS do not alias accesses based on other
202 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
203 alias globals either; the ADDRESSes have Pmode to indicate this.
204 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
207 static GTY(()) VEC(rtx,gc) *reg_base_value;
208 static rtx *new_reg_base_value;
210 /* The single VOIDmode ADDRESS that represents all argument bases.
212 static GTY(()) rtx arg_base_value;
214 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
215 static int unique_id;
217 /* We preserve the copy of old array around to avoid amount of garbage
218 produced. About 8% of garbage produced were attributed to this
220 static GTY((deletable)) VEC(rtx,gc) *old_reg_base_value;
222 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
224 #define UNIQUE_BASE_VALUE_SP -1
225 #define UNIQUE_BASE_VALUE_ARGP -2
226 #define UNIQUE_BASE_VALUE_FP -3
227 #define UNIQUE_BASE_VALUE_HFP -4
229 #define static_reg_base_value \
230 (this_target_rtl->x_static_reg_base_value)
232 #define REG_BASE_VALUE(X) \
233 (REGNO (X) < VEC_length (rtx, reg_base_value) \
234 ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
236 /* Vector indexed by N giving the initial (unchanging) value known for
237 pseudo-register N. This vector is initialized in init_alias_analysis,
238 and does not change until end_alias_analysis is called. */
239 static GTY(()) VEC(rtx,gc) *reg_known_value;
241 /* Vector recording for each reg_known_value whether it is due to a
242 REG_EQUIV note. Future passes (viz., reload) may replace the
243 pseudo with the equivalent expression and so we account for the
244 dependences that would be introduced if that happens.
246 The REG_EQUIV notes created in assign_parms may mention the arg
247 pointer, and there are explicit insns in the RTL that modify the
248 arg pointer. Thus we must ensure that such insns don't get
249 scheduled across each other because that would invalidate the
250 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
251 wrong, but solving the problem in the scheduler will likely give
252 better code, so we do it here. */
253 static sbitmap reg_known_equiv_p;
255 /* True when scanning insns from the start of the rtl to the
256 NOTE_INSN_FUNCTION_BEG note. */
257 static bool copying_arguments;
259 DEF_VEC_P(alias_set_entry);
260 DEF_VEC_ALLOC_P(alias_set_entry,gc);
262 /* The splay-tree used to store the various alias set entries. */
263 static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
265 /* Build a decomposed reference object for querying the alias-oracle
266 from the MEM rtx and store it in *REF.
267 Returns false if MEM is not suitable for the alias-oracle. */
270 ao_ref_from_mem (ao_ref *ref, const_rtx mem)
272 tree expr = MEM_EXPR (mem);
278 ao_ref_init (ref, expr);
280 /* Get the base of the reference and see if we have to reject or
282 base = ao_ref_base (ref);
283 if (base == NULL_TREE)
286 /* The tree oracle doesn't like to have these. */
287 if (TREE_CODE (base) == FUNCTION_DECL
288 || TREE_CODE (base) == LABEL_DECL)
291 /* If this is a pointer dereference of a non-SSA_NAME punt.
292 ??? We could replace it with a pointer to anything. */
293 if ((INDIRECT_REF_P (base)
294 || TREE_CODE (base) == MEM_REF)
295 && TREE_CODE (TREE_OPERAND (base, 0)) != SSA_NAME)
297 if (TREE_CODE (base) == TARGET_MEM_REF
299 && TREE_CODE (TMR_BASE (base)) != SSA_NAME)
302 /* If this is a reference based on a partitioned decl replace the
303 base with an INDIRECT_REF of the pointer representative we
304 created during stack slot partitioning. */
305 if (TREE_CODE (base) == VAR_DECL
306 && ! TREE_STATIC (base)
307 && cfun->gimple_df->decls_to_pointers != NULL)
310 namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers, base);
312 ref->base = build_simple_mem_ref (*(tree *)namep);
314 else if (TREE_CODE (base) == TARGET_MEM_REF
315 && TREE_CODE (TMR_BASE (base)) == ADDR_EXPR
316 && TREE_CODE (TREE_OPERAND (TMR_BASE (base), 0)) == VAR_DECL
317 && ! TREE_STATIC (TREE_OPERAND (TMR_BASE (base), 0))
318 && cfun->gimple_df->decls_to_pointers != NULL)
321 namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers,
322 TREE_OPERAND (TMR_BASE (base), 0));
324 ref->base = build_simple_mem_ref (*(tree *)namep);
327 ref->ref_alias_set = MEM_ALIAS_SET (mem);
329 /* If MEM_OFFSET or MEM_SIZE are unknown we have to punt.
330 Keep points-to related information though. */
331 if (!MEM_OFFSET_KNOWN_P (mem)
332 || !MEM_SIZE_KNOWN_P (mem))
334 ref->ref = NULL_TREE;
341 /* If the base decl is a parameter we can have negative MEM_OFFSET in
342 case of promoted subregs on bigendian targets. Trust the MEM_EXPR
344 if (MEM_OFFSET (mem) < 0
345 && (MEM_SIZE (mem) + MEM_OFFSET (mem)) * BITS_PER_UNIT == ref->size)
348 ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
349 ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
351 /* The MEM may extend into adjacent fields, so adjust max_size if
353 if (ref->max_size != -1
354 && ref->size > ref->max_size)
355 ref->max_size = ref->size;
357 /* If MEM_OFFSET and MEM_SIZE get us outside of the base object of
358 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
359 if (MEM_EXPR (mem) != get_spill_slot_decl (false)
361 || (DECL_P (ref->base)
362 && (!host_integerp (DECL_SIZE (ref->base), 1)
363 || (TREE_INT_CST_LOW (DECL_SIZE ((ref->base)))
364 < (unsigned HOST_WIDE_INT)(ref->offset + ref->size))))))
370 /* Query the alias-oracle on whether the two memory rtx X and MEM may
371 alias. If TBAA_P is set also apply TBAA. Returns true if the
372 two rtxen may alias, false otherwise. */
375 rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
379 if (!ao_ref_from_mem (&ref1, x)
380 || !ao_ref_from_mem (&ref2, mem))
383 return refs_may_alias_p_1 (&ref1, &ref2,
385 && MEM_ALIAS_SET (x) != 0
386 && MEM_ALIAS_SET (mem) != 0);
389 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
390 such an entry, or NULL otherwise. */
392 static inline alias_set_entry
393 get_alias_set_entry (alias_set_type alias_set)
395 return VEC_index (alias_set_entry, alias_sets, alias_set);
398 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
399 the two MEMs cannot alias each other. */
402 mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
404 /* Perform a basic sanity check. Namely, that there are no alias sets
405 if we're not using strict aliasing. This helps to catch bugs
406 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
407 where a MEM is allocated in some way other than by the use of
408 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
409 use alias sets to indicate that spilled registers cannot alias each
410 other, we might need to remove this check. */
411 gcc_assert (flag_strict_aliasing
412 || (!MEM_ALIAS_SET (mem1) && !MEM_ALIAS_SET (mem2)));
414 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
417 /* Insert the NODE into the splay tree given by DATA. Used by
418 record_alias_subset via splay_tree_foreach. */
421 insert_subset_children (splay_tree_node node, void *data)
423 splay_tree_insert ((splay_tree) data, node->key, node->value);
428 /* Return true if the first alias set is a subset of the second. */
431 alias_set_subset_of (alias_set_type set1, alias_set_type set2)
435 /* Everything is a subset of the "aliases everything" set. */
439 /* Otherwise, check if set1 is a subset of set2. */
440 ase = get_alias_set_entry (set2);
442 && (ase->has_zero_child
443 || splay_tree_lookup (ase->children,
444 (splay_tree_key) set1)))
449 /* Return 1 if the two specified alias sets may conflict. */
452 alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
457 if (alias_sets_must_conflict_p (set1, set2))
460 /* See if the first alias set is a subset of the second. */
461 ase = get_alias_set_entry (set1);
463 && (ase->has_zero_child
464 || splay_tree_lookup (ase->children,
465 (splay_tree_key) set2)))
468 /* Now do the same, but with the alias sets reversed. */
469 ase = get_alias_set_entry (set2);
471 && (ase->has_zero_child
472 || splay_tree_lookup (ase->children,
473 (splay_tree_key) set1)))
476 /* The two alias sets are distinct and neither one is the
477 child of the other. Therefore, they cannot conflict. */
481 /* Return 1 if the two specified alias sets will always conflict. */
484 alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
486 if (set1 == 0 || set2 == 0 || set1 == set2)
492 /* Return 1 if any MEM object of type T1 will always conflict (using the
493 dependency routines in this file) with any MEM object of type T2.
494 This is used when allocating temporary storage. If T1 and/or T2 are
495 NULL_TREE, it means we know nothing about the storage. */
498 objects_must_conflict_p (tree t1, tree t2)
500 alias_set_type set1, set2;
502 /* If neither has a type specified, we don't know if they'll conflict
503 because we may be using them to store objects of various types, for
504 example the argument and local variables areas of inlined functions. */
505 if (t1 == 0 && t2 == 0)
508 /* If they are the same type, they must conflict. */
510 /* Likewise if both are volatile. */
511 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
514 set1 = t1 ? get_alias_set (t1) : 0;
515 set2 = t2 ? get_alias_set (t2) : 0;
517 /* We can't use alias_sets_conflict_p because we must make sure
518 that every subtype of t1 will conflict with every subtype of
519 t2 for which a pair of subobjects of these respective subtypes
520 overlaps on the stack. */
521 return alias_sets_must_conflict_p (set1, set2);
524 /* Return true if all nested component references handled by
525 get_inner_reference in T are such that we should use the alias set
526 provided by the object at the heart of T.
528 This is true for non-addressable components (which don't have their
529 own alias set), as well as components of objects in alias set zero.
530 This later point is a special case wherein we wish to override the
531 alias set used by the component, but we don't have per-FIELD_DECL
532 assignable alias sets. */
535 component_uses_parent_alias_set (const_tree t)
539 /* If we're at the end, it vacuously uses its own alias set. */
540 if (!handled_component_p (t))
543 switch (TREE_CODE (t))
546 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
551 case ARRAY_RANGE_REF:
552 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
561 /* Bitfields and casts are never addressable. */
565 t = TREE_OPERAND (t, 0);
566 if (get_alias_set (TREE_TYPE (t)) == 0)
571 /* Return the alias set for the memory pointed to by T, which may be
572 either a type or an expression. Return -1 if there is nothing
573 special about dereferencing T. */
575 static alias_set_type
576 get_deref_alias_set_1 (tree t)
578 /* If we're not doing any alias analysis, just assume everything
579 aliases everything else. */
580 if (!flag_strict_aliasing)
583 /* All we care about is the type. */
587 /* If we have an INDIRECT_REF via a void pointer, we don't
588 know anything about what that might alias. Likewise if the
589 pointer is marked that way. */
590 if (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE
591 || TYPE_REF_CAN_ALIAS_ALL (t))
597 /* Return the alias set for the memory pointed to by T, which may be
598 either a type or an expression. */
601 get_deref_alias_set (tree t)
603 alias_set_type set = get_deref_alias_set_1 (t);
605 /* Fall back to the alias-set of the pointed-to type. */
610 set = get_alias_set (TREE_TYPE (t));
616 /* Return the alias set for T, which may be either a type or an
617 expression. Call language-specific routine for help, if needed. */
620 get_alias_set (tree t)
624 /* If we're not doing any alias analysis, just assume everything
625 aliases everything else. Also return 0 if this or its type is
627 if (! flag_strict_aliasing || t == error_mark_node
629 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
632 /* We can be passed either an expression or a type. This and the
633 language-specific routine may make mutually-recursive calls to each other
634 to figure out what to do. At each juncture, we see if this is a tree
635 that the language may need to handle specially. First handle things that
641 /* Give the language a chance to do something with this tree
642 before we look at it. */
644 set = lang_hooks.get_alias_set (t);
648 /* Get the base object of the reference. */
650 while (handled_component_p (inner))
652 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
653 the type of any component references that wrap it to
654 determine the alias-set. */
655 if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
656 t = TREE_OPERAND (inner, 0);
657 inner = TREE_OPERAND (inner, 0);
660 /* Handle pointer dereferences here, they can override the
662 if (INDIRECT_REF_P (inner))
664 set = get_deref_alias_set_1 (TREE_OPERAND (inner, 0));
668 else if (TREE_CODE (inner) == TARGET_MEM_REF)
669 return get_deref_alias_set (TMR_OFFSET (inner));
670 else if (TREE_CODE (inner) == MEM_REF)
672 set = get_deref_alias_set_1 (TREE_OPERAND (inner, 1));
677 /* If the innermost reference is a MEM_REF that has a
678 conversion embedded treat it like a VIEW_CONVERT_EXPR above,
679 using the memory access type for determining the alias-set. */
680 if (TREE_CODE (inner) == MEM_REF
681 && TYPE_MAIN_VARIANT (TREE_TYPE (inner))
683 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1)))))
684 return get_deref_alias_set (TREE_OPERAND (inner, 1));
686 /* Otherwise, pick up the outermost object that we could have a pointer
687 to, processing conversions as above. */
688 while (component_uses_parent_alias_set (t))
690 t = TREE_OPERAND (t, 0);
694 /* If we've already determined the alias set for a decl, just return
695 it. This is necessary for C++ anonymous unions, whose component
696 variables don't look like union members (boo!). */
697 if (TREE_CODE (t) == VAR_DECL
698 && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
699 return MEM_ALIAS_SET (DECL_RTL (t));
701 /* Now all we care about is the type. */
705 /* Variant qualifiers don't affect the alias set, so get the main
707 t = TYPE_MAIN_VARIANT (t);
709 /* Always use the canonical type as well. If this is a type that
710 requires structural comparisons to identify compatible types
711 use alias set zero. */
712 if (TYPE_STRUCTURAL_EQUALITY_P (t))
714 /* Allow the language to specify another alias set for this
716 set = lang_hooks.get_alias_set (t);
722 t = TYPE_CANONICAL (t);
724 /* The canonical type should not require structural equality checks. */
725 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
727 /* If this is a type with a known alias set, return it. */
728 if (TYPE_ALIAS_SET_KNOWN_P (t))
729 return TYPE_ALIAS_SET (t);
731 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
732 if (!COMPLETE_TYPE_P (t))
734 /* For arrays with unknown size the conservative answer is the
735 alias set of the element type. */
736 if (TREE_CODE (t) == ARRAY_TYPE)
737 return get_alias_set (TREE_TYPE (t));
739 /* But return zero as a conservative answer for incomplete types. */
743 /* See if the language has special handling for this type. */
744 set = lang_hooks.get_alias_set (t);
748 /* There are no objects of FUNCTION_TYPE, so there's no point in
749 using up an alias set for them. (There are, of course, pointers
750 and references to functions, but that's different.) */
751 else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
754 /* Unless the language specifies otherwise, let vector types alias
755 their components. This avoids some nasty type punning issues in
756 normal usage. And indeed lets vectors be treated more like an
758 else if (TREE_CODE (t) == VECTOR_TYPE)
759 set = get_alias_set (TREE_TYPE (t));
761 /* Unless the language specifies otherwise, treat array types the
762 same as their components. This avoids the asymmetry we get
763 through recording the components. Consider accessing a
764 character(kind=1) through a reference to a character(kind=1)[1:1].
765 Or consider if we want to assign integer(kind=4)[0:D.1387] and
766 integer(kind=4)[4] the same alias set or not.
767 Just be pragmatic here and make sure the array and its element
768 type get the same alias set assigned. */
769 else if (TREE_CODE (t) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (t))
770 set = get_alias_set (TREE_TYPE (t));
772 /* From the former common C and C++ langhook implementation:
774 Unfortunately, there is no canonical form of a pointer type.
775 In particular, if we have `typedef int I', then `int *', and
776 `I *' are different types. So, we have to pick a canonical
777 representative. We do this below.
779 Technically, this approach is actually more conservative that
780 it needs to be. In particular, `const int *' and `int *'
781 should be in different alias sets, according to the C and C++
782 standard, since their types are not the same, and so,
783 technically, an `int **' and `const int **' cannot point at
786 But, the standard is wrong. In particular, this code is
791 const int* const* cipp = ipp;
792 And, it doesn't make sense for that to be legal unless you
793 can dereference IPP and CIPP. So, we ignore cv-qualifiers on
794 the pointed-to types. This issue has been reported to the
797 In addition to the above canonicalization issue, with LTO
798 we should also canonicalize `T (*)[]' to `T *' avoiding
799 alias issues with pointer-to element types and pointer-to
802 Likewise we need to deal with the situation of incomplete
803 pointed-to types and make `*(struct X **)&a' and
804 `*(struct X {} **)&a' alias. Otherwise we will have to
805 guarantee that all pointer-to incomplete type variants
806 will be replaced by pointer-to complete type variants if
809 With LTO the convenient situation of using `void *' to
810 access and store any pointer type will also become
811 more apparent (and `void *' is just another pointer-to
812 incomplete type). Assigning alias-set zero to `void *'
813 and all pointer-to incomplete types is a not appealing
814 solution. Assigning an effective alias-set zero only
815 affecting pointers might be - by recording proper subset
816 relationships of all pointer alias-sets.
818 Pointer-to function types are another grey area which
819 needs caution. Globbing them all into one alias-set
820 or the above effective zero set would work.
822 For now just assign the same alias-set to all pointers.
823 That's simple and avoids all the above problems. */
824 else if (POINTER_TYPE_P (t)
825 && t != ptr_type_node)
826 set = get_alias_set (ptr_type_node);
828 /* Otherwise make a new alias set for this type. */
831 /* Each canonical type gets its own alias set, so canonical types
832 shouldn't form a tree. It doesn't really matter for types
833 we handle specially above, so only check it where it possibly
834 would result in a bogus alias set. */
835 gcc_checking_assert (TYPE_CANONICAL (t) == t);
837 set = new_alias_set ();
840 TYPE_ALIAS_SET (t) = set;
842 /* If this is an aggregate type or a complex type, we must record any
843 component aliasing information. */
844 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
845 record_component_aliases (t);
850 /* Return a brand-new alias set. */
855 if (flag_strict_aliasing)
858 VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
859 VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
860 return VEC_length (alias_set_entry, alias_sets) - 1;
866 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
867 not everything that aliases SUPERSET also aliases SUBSET. For example,
868 in C, a store to an `int' can alias a load of a structure containing an
869 `int', and vice versa. But it can't alias a load of a 'double' member
870 of the same structure. Here, the structure would be the SUPERSET and
871 `int' the SUBSET. This relationship is also described in the comment at
872 the beginning of this file.
874 This function should be called only once per SUPERSET/SUBSET pair.
876 It is illegal for SUPERSET to be zero; everything is implicitly a
877 subset of alias set zero. */
880 record_alias_subset (alias_set_type superset, alias_set_type subset)
882 alias_set_entry superset_entry;
883 alias_set_entry subset_entry;
885 /* It is possible in complex type situations for both sets to be the same,
886 in which case we can ignore this operation. */
887 if (superset == subset)
890 gcc_assert (superset);
892 superset_entry = get_alias_set_entry (superset);
893 if (superset_entry == 0)
895 /* Create an entry for the SUPERSET, so that we have a place to
896 attach the SUBSET. */
897 superset_entry = ggc_alloc_cleared_alias_set_entry_d ();
898 superset_entry->alias_set = superset;
899 superset_entry->children
900 = splay_tree_new_ggc (splay_tree_compare_ints,
901 ggc_alloc_splay_tree_scalar_scalar_splay_tree_s,
902 ggc_alloc_splay_tree_scalar_scalar_splay_tree_node_s);
903 superset_entry->has_zero_child = 0;
904 VEC_replace (alias_set_entry, alias_sets, superset, superset_entry);
908 superset_entry->has_zero_child = 1;
911 subset_entry = get_alias_set_entry (subset);
912 /* If there is an entry for the subset, enter all of its children
913 (if they are not already present) as children of the SUPERSET. */
916 if (subset_entry->has_zero_child)
917 superset_entry->has_zero_child = 1;
919 splay_tree_foreach (subset_entry->children, insert_subset_children,
920 superset_entry->children);
923 /* Enter the SUBSET itself as a child of the SUPERSET. */
924 splay_tree_insert (superset_entry->children,
925 (splay_tree_key) subset, 0);
929 /* Record that component types of TYPE, if any, are part of that type for
930 aliasing purposes. For record types, we only record component types
931 for fields that are not marked non-addressable. For array types, we
932 only record the component type if it is not marked non-aliased. */
935 record_component_aliases (tree type)
937 alias_set_type superset = get_alias_set (type);
943 switch (TREE_CODE (type))
947 case QUAL_UNION_TYPE:
948 /* Recursively record aliases for the base classes, if there are any. */
949 if (TYPE_BINFO (type))
952 tree binfo, base_binfo;
954 for (binfo = TYPE_BINFO (type), i = 0;
955 BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
956 record_alias_subset (superset,
957 get_alias_set (BINFO_TYPE (base_binfo)));
959 for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
960 if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
961 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
965 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
968 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
976 /* Allocate an alias set for use in storing and reading from the varargs
979 static GTY(()) alias_set_type varargs_set = -1;
982 get_varargs_alias_set (void)
985 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
986 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
987 consistently use the varargs alias set for loads from the varargs
988 area. So don't use it anywhere. */
991 if (varargs_set == -1)
992 varargs_set = new_alias_set ();
998 /* Likewise, but used for the fixed portions of the frame, e.g., register
1001 static GTY(()) alias_set_type frame_set = -1;
1004 get_frame_alias_set (void)
1006 if (frame_set == -1)
1007 frame_set = new_alias_set ();
1012 /* Create a new, unique base with id ID. */
1015 unique_base_value (HOST_WIDE_INT id)
1017 return gen_rtx_ADDRESS (Pmode, id);
1020 /* Return true if accesses based on any other base value cannot alias
1021 those based on X. */
1024 unique_base_value_p (rtx x)
1026 return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1029 /* Return true if X is known to be a base value. */
1032 known_base_value_p (rtx x)
1034 switch (GET_CODE (x))
1041 /* Arguments may or may not be bases; we don't know for sure. */
1042 return GET_MODE (x) != VOIDmode;
1049 /* Inside SRC, the source of a SET, find a base address. */
1052 find_base_value (rtx src)
1056 #if defined (FIND_BASE_TERM)
1057 /* Try machine-dependent ways to find the base term. */
1058 src = FIND_BASE_TERM (src);
1061 switch (GET_CODE (src))
1068 regno = REGNO (src);
1069 /* At the start of a function, argument registers have known base
1070 values which may be lost later. Returning an ADDRESS
1071 expression here allows optimization based on argument values
1072 even when the argument registers are used for other purposes. */
1073 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1074 return new_reg_base_value[regno];
1076 /* If a pseudo has a known base value, return it. Do not do this
1077 for non-fixed hard regs since it can result in a circular
1078 dependency chain for registers which have values at function entry.
1080 The test above is not sufficient because the scheduler may move
1081 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1082 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1083 && regno < VEC_length (rtx, reg_base_value))
1085 /* If we're inside init_alias_analysis, use new_reg_base_value
1086 to reduce the number of relaxation iterations. */
1087 if (new_reg_base_value && new_reg_base_value[regno]
1088 && DF_REG_DEF_COUNT (regno) == 1)
1089 return new_reg_base_value[regno];
1091 if (VEC_index (rtx, reg_base_value, regno))
1092 return VEC_index (rtx, reg_base_value, regno);
1098 /* Check for an argument passed in memory. Only record in the
1099 copying-arguments block; it is too hard to track changes
1101 if (copying_arguments
1102 && (XEXP (src, 0) == arg_pointer_rtx
1103 || (GET_CODE (XEXP (src, 0)) == PLUS
1104 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1105 return arg_base_value;
1109 src = XEXP (src, 0);
1110 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1113 /* ... fall through ... */
1118 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1120 /* If either operand is a REG that is a known pointer, then it
1122 if (REG_P (src_0) && REG_POINTER (src_0))
1123 return find_base_value (src_0);
1124 if (REG_P (src_1) && REG_POINTER (src_1))
1125 return find_base_value (src_1);
1127 /* If either operand is a REG, then see if we already have
1128 a known value for it. */
1131 temp = find_base_value (src_0);
1138 temp = find_base_value (src_1);
1143 /* If either base is named object or a special address
1144 (like an argument or stack reference), then use it for the
1146 if (src_0 != 0 && known_base_value_p (src_0))
1149 if (src_1 != 0 && known_base_value_p (src_1))
1152 /* Guess which operand is the base address:
1153 If either operand is a symbol, then it is the base. If
1154 either operand is a CONST_INT, then the other is the base. */
1155 if (CONST_INT_P (src_1) || CONSTANT_P (src_0))
1156 return find_base_value (src_0);
1157 else if (CONST_INT_P (src_0) || CONSTANT_P (src_1))
1158 return find_base_value (src_1);
1164 /* The standard form is (lo_sum reg sym) so look only at the
1166 return find_base_value (XEXP (src, 1));
1169 /* If the second operand is constant set the base
1170 address to the first operand. */
1171 if (CONST_INT_P (XEXP (src, 1)) && INTVAL (XEXP (src, 1)) != 0)
1172 return find_base_value (XEXP (src, 0));
1176 /* As we do not know which address space the pointer is referring to, we can
1177 handle this only if the target does not support different pointer or
1178 address modes depending on the address space. */
1179 if (!target_default_pointer_address_modes_p ())
1181 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
1191 return find_base_value (XEXP (src, 0));
1194 case SIGN_EXTEND: /* used for NT/Alpha pointers */
1195 /* As we do not know which address space the pointer is referring to, we can
1196 handle this only if the target does not support different pointer or
1197 address modes depending on the address space. */
1198 if (!target_default_pointer_address_modes_p ())
1202 rtx temp = find_base_value (XEXP (src, 0));
1204 if (temp != 0 && CONSTANT_P (temp))
1205 temp = convert_memory_address (Pmode, temp);
1217 /* Called from init_alias_analysis indirectly through note_stores,
1218 or directly if DEST is a register with a REG_NOALIAS note attached.
1219 SET is null in the latter case. */
1221 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1222 register N has been set in this function. */
1223 static char *reg_seen;
1226 record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1235 regno = REGNO (dest);
1237 gcc_checking_assert (regno < VEC_length (rtx, reg_base_value));
1239 /* If this spans multiple hard registers, then we must indicate that every
1240 register has an unusable value. */
1241 if (regno < FIRST_PSEUDO_REGISTER)
1242 n = hard_regno_nregs[regno][GET_MODE (dest)];
1249 reg_seen[regno + n] = 1;
1250 new_reg_base_value[regno + n] = 0;
1257 /* A CLOBBER wipes out any old value but does not prevent a previously
1258 unset register from acquiring a base address (i.e. reg_seen is not
1260 if (GET_CODE (set) == CLOBBER)
1262 new_reg_base_value[regno] = 0;
1265 src = SET_SRC (set);
1269 /* There's a REG_NOALIAS note against DEST. */
1270 if (reg_seen[regno])
1272 new_reg_base_value[regno] = 0;
1275 reg_seen[regno] = 1;
1276 new_reg_base_value[regno] = unique_base_value (unique_id++);
1280 /* If this is not the first set of REGNO, see whether the new value
1281 is related to the old one. There are two cases of interest:
1283 (1) The register might be assigned an entirely new value
1284 that has the same base term as the original set.
1286 (2) The set might be a simple self-modification that
1287 cannot change REGNO's base value.
1289 If neither case holds, reject the original base value as invalid.
1290 Note that the following situation is not detected:
1292 extern int x, y; int *p = &x; p += (&y-&x);
1294 ANSI C does not allow computing the difference of addresses
1295 of distinct top level objects. */
1296 if (new_reg_base_value[regno] != 0
1297 && find_base_value (src) != new_reg_base_value[regno])
1298 switch (GET_CODE (src))
1302 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1303 new_reg_base_value[regno] = 0;
1306 /* If the value we add in the PLUS is also a valid base value,
1307 this might be the actual base value, and the original value
1310 rtx other = NULL_RTX;
1312 if (XEXP (src, 0) == dest)
1313 other = XEXP (src, 1);
1314 else if (XEXP (src, 1) == dest)
1315 other = XEXP (src, 0);
1317 if (! other || find_base_value (other))
1318 new_reg_base_value[regno] = 0;
1322 if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1323 new_reg_base_value[regno] = 0;
1326 new_reg_base_value[regno] = 0;
1329 /* If this is the first set of a register, record the value. */
1330 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1331 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1332 new_reg_base_value[regno] = find_base_value (src);
1334 reg_seen[regno] = 1;
1337 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1338 using hard registers with non-null REG_BASE_VALUE for renaming. */
1340 get_reg_base_value (unsigned int regno)
1342 return VEC_index (rtx, reg_base_value, regno);
1345 /* If a value is known for REGNO, return it. */
1348 get_reg_known_value (unsigned int regno)
1350 if (regno >= FIRST_PSEUDO_REGISTER)
1352 regno -= FIRST_PSEUDO_REGISTER;
1353 if (regno < VEC_length (rtx, reg_known_value))
1354 return VEC_index (rtx, reg_known_value, regno);
1362 set_reg_known_value (unsigned int regno, rtx val)
1364 if (regno >= FIRST_PSEUDO_REGISTER)
1366 regno -= FIRST_PSEUDO_REGISTER;
1367 if (regno < VEC_length (rtx, reg_known_value))
1368 VEC_replace (rtx, reg_known_value, regno, val);
1372 /* Similarly for reg_known_equiv_p. */
1375 get_reg_known_equiv_p (unsigned int regno)
1377 if (regno >= FIRST_PSEUDO_REGISTER)
1379 regno -= FIRST_PSEUDO_REGISTER;
1380 if (regno < VEC_length (rtx, reg_known_value))
1381 return TEST_BIT (reg_known_equiv_p, regno);
1387 set_reg_known_equiv_p (unsigned int regno, bool val)
1389 if (regno >= FIRST_PSEUDO_REGISTER)
1391 regno -= FIRST_PSEUDO_REGISTER;
1392 if (regno < VEC_length (rtx, reg_known_value))
1395 SET_BIT (reg_known_equiv_p, regno);
1397 RESET_BIT (reg_known_equiv_p, regno);
1403 /* Returns a canonical version of X, from the point of view alias
1404 analysis. (For example, if X is a MEM whose address is a register,
1405 and the register has a known value (say a SYMBOL_REF), then a MEM
1406 whose address is the SYMBOL_REF is returned.) */
1411 /* Recursively look for equivalences. */
1412 if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1414 rtx t = get_reg_known_value (REGNO (x));
1418 return canon_rtx (t);
1421 if (GET_CODE (x) == PLUS)
1423 rtx x0 = canon_rtx (XEXP (x, 0));
1424 rtx x1 = canon_rtx (XEXP (x, 1));
1426 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1428 if (CONST_INT_P (x0))
1429 return plus_constant (GET_MODE (x), x1, INTVAL (x0));
1430 else if (CONST_INT_P (x1))
1431 return plus_constant (GET_MODE (x), x0, INTVAL (x1));
1432 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1436 /* This gives us much better alias analysis when called from
1437 the loop optimizer. Note we want to leave the original
1438 MEM alone, but need to return the canonicalized MEM with
1439 all the flags with their original values. */
1441 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1446 /* Return 1 if X and Y are identical-looking rtx's.
1447 Expect that X and Y has been already canonicalized.
1449 We use the data in reg_known_value above to see if two registers with
1450 different numbers are, in fact, equivalent. */
1453 rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1460 if (x == 0 && y == 0)
1462 if (x == 0 || y == 0)
1468 code = GET_CODE (x);
1469 /* Rtx's of different codes cannot be equal. */
1470 if (code != GET_CODE (y))
1473 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1474 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1476 if (GET_MODE (x) != GET_MODE (y))
1479 /* Some RTL can be compared without a recursive examination. */
1483 return REGNO (x) == REGNO (y);
1486 return XEXP (x, 0) == XEXP (y, 0);
1489 return XSTR (x, 0) == XSTR (y, 0);
1495 /* There's no need to compare the contents of CONST_DOUBLEs or
1496 CONST_INTs because pointer equality is a good enough
1497 comparison for these nodes. */
1504 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1506 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1507 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1508 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1509 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1510 /* For commutative operations, the RTX match if the operand match in any
1511 order. Also handle the simple binary and unary cases without a loop. */
1512 if (COMMUTATIVE_P (x))
1514 rtx xop0 = canon_rtx (XEXP (x, 0));
1515 rtx yop0 = canon_rtx (XEXP (y, 0));
1516 rtx yop1 = canon_rtx (XEXP (y, 1));
1518 return ((rtx_equal_for_memref_p (xop0, yop0)
1519 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1520 || (rtx_equal_for_memref_p (xop0, yop1)
1521 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1523 else if (NON_COMMUTATIVE_P (x))
1525 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1526 canon_rtx (XEXP (y, 0)))
1527 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1528 canon_rtx (XEXP (y, 1))));
1530 else if (UNARY_P (x))
1531 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1532 canon_rtx (XEXP (y, 0)));
1534 /* Compare the elements. If any pair of corresponding elements
1535 fail to match, return 0 for the whole things.
1537 Limit cases to types which actually appear in addresses. */
1539 fmt = GET_RTX_FORMAT (code);
1540 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1545 if (XINT (x, i) != XINT (y, i))
1550 /* Two vectors must have the same length. */
1551 if (XVECLEN (x, i) != XVECLEN (y, i))
1554 /* And the corresponding elements must match. */
1555 for (j = 0; j < XVECLEN (x, i); j++)
1556 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1557 canon_rtx (XVECEXP (y, i, j))) == 0)
1562 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1563 canon_rtx (XEXP (y, i))) == 0)
1567 /* This can happen for asm operands. */
1569 if (strcmp (XSTR (x, i), XSTR (y, i)))
1573 /* This can happen for an asm which clobbers memory. */
1577 /* It is believed that rtx's at this level will never
1578 contain anything but integers and other rtx's,
1579 except for within LABEL_REFs and SYMBOL_REFs. */
1588 find_base_term (rtx x)
1591 struct elt_loc_list *l, *f;
1594 #if defined (FIND_BASE_TERM)
1595 /* Try machine-dependent ways to find the base term. */
1596 x = FIND_BASE_TERM (x);
1599 switch (GET_CODE (x))
1602 return REG_BASE_VALUE (x);
1605 /* As we do not know which address space the pointer is referring to, we can
1606 handle this only if the target does not support different pointer or
1607 address modes depending on the address space. */
1608 if (!target_default_pointer_address_modes_p ())
1610 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1620 return find_base_term (XEXP (x, 0));
1623 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1624 /* As we do not know which address space the pointer is referring to, we can
1625 handle this only if the target does not support different pointer or
1626 address modes depending on the address space. */
1627 if (!target_default_pointer_address_modes_p ())
1631 rtx temp = find_base_term (XEXP (x, 0));
1633 if (temp != 0 && CONSTANT_P (temp))
1634 temp = convert_memory_address (Pmode, temp);
1640 val = CSELIB_VAL_PTR (x);
1647 /* Temporarily reset val->locs to avoid infinite recursion. */
1650 for (l = f; l; l = l->next)
1651 if (GET_CODE (l->loc) == VALUE
1652 && CSELIB_VAL_PTR (l->loc)->locs
1653 && !CSELIB_VAL_PTR (l->loc)->locs->next
1654 && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1656 else if ((ret = find_base_term (l->loc)) != 0)
1663 /* The standard form is (lo_sum reg sym) so look only at the
1665 return find_base_term (XEXP (x, 1));
1669 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1675 rtx tmp1 = XEXP (x, 0);
1676 rtx tmp2 = XEXP (x, 1);
1678 /* This is a little bit tricky since we have to determine which of
1679 the two operands represents the real base address. Otherwise this
1680 routine may return the index register instead of the base register.
1682 That may cause us to believe no aliasing was possible, when in
1683 fact aliasing is possible.
1685 We use a few simple tests to guess the base register. Additional
1686 tests can certainly be added. For example, if one of the operands
1687 is a shift or multiply, then it must be the index register and the
1688 other operand is the base register. */
1690 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1691 return find_base_term (tmp2);
1693 /* If either operand is known to be a pointer, then use it
1694 to determine the base term. */
1695 if (REG_P (tmp1) && REG_POINTER (tmp1))
1697 rtx base = find_base_term (tmp1);
1702 if (REG_P (tmp2) && REG_POINTER (tmp2))
1704 rtx base = find_base_term (tmp2);
1709 /* Neither operand was known to be a pointer. Go ahead and find the
1710 base term for both operands. */
1711 tmp1 = find_base_term (tmp1);
1712 tmp2 = find_base_term (tmp2);
1714 /* If either base term is named object or a special address
1715 (like an argument or stack reference), then use it for the
1717 if (tmp1 != 0 && known_base_value_p (tmp1))
1720 if (tmp2 != 0 && known_base_value_p (tmp2))
1723 /* We could not determine which of the two operands was the
1724 base register and which was the index. So we can determine
1725 nothing from the base alias check. */
1730 if (CONST_INT_P (XEXP (x, 1)) && INTVAL (XEXP (x, 1)) != 0)
1731 return find_base_term (XEXP (x, 0));
1743 /* Return true if accesses to address X may alias accesses based
1744 on the stack pointer. */
1747 may_be_sp_based_p (rtx x)
1749 rtx base = find_base_term (x);
1750 return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
1753 /* Return 0 if the addresses X and Y are known to point to different
1754 objects, 1 if they might be pointers to the same object. */
1757 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1758 enum machine_mode y_mode)
1760 rtx x_base = find_base_term (x);
1761 rtx y_base = find_base_term (y);
1763 /* If the address itself has no known base see if a known equivalent
1764 value has one. If either address still has no known base, nothing
1765 is known about aliasing. */
1770 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1773 x_base = find_base_term (x_c);
1781 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1784 y_base = find_base_term (y_c);
1789 /* If the base addresses are equal nothing is known about aliasing. */
1790 if (rtx_equal_p (x_base, y_base))
1793 /* The base addresses are different expressions. If they are not accessed
1794 via AND, there is no conflict. We can bring knowledge of object
1795 alignment into play here. For example, on alpha, "char a, b;" can
1796 alias one another, though "char a; long b;" cannot. AND addesses may
1797 implicitly alias surrounding objects; i.e. unaligned access in DImode
1798 via AND address can alias all surrounding object types except those
1799 with aligment 8 or higher. */
1800 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1802 if (GET_CODE (x) == AND
1803 && (!CONST_INT_P (XEXP (x, 1))
1804 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1806 if (GET_CODE (y) == AND
1807 && (!CONST_INT_P (XEXP (y, 1))
1808 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1811 /* Differing symbols not accessed via AND never alias. */
1812 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1815 if (unique_base_value_p (x_base) || unique_base_value_p (y_base))
1821 /* Callback for for_each_rtx, that returns 1 upon encountering a VALUE
1822 whose UID is greater than the int uid that D points to. */
1825 refs_newer_value_cb (rtx *x, void *d)
1827 if (GET_CODE (*x) == VALUE && CSELIB_VAL_PTR (*x)->uid > *(int *)d)
1833 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
1837 refs_newer_value_p (rtx expr, rtx v)
1839 int minuid = CSELIB_VAL_PTR (v)->uid;
1841 return for_each_rtx (&expr, refs_newer_value_cb, &minuid);
1844 /* Convert the address X into something we can use. This is done by returning
1845 it unchanged unless it is a value; in the latter case we call cselib to get
1846 a more useful rtx. */
1852 struct elt_loc_list *l;
1854 if (GET_CODE (x) != VALUE)
1856 v = CSELIB_VAL_PTR (x);
1859 bool have_equivs = cselib_have_permanent_equivalences ();
1861 v = canonical_cselib_val (v);
1862 for (l = v->locs; l; l = l->next)
1863 if (CONSTANT_P (l->loc))
1865 for (l = v->locs; l; l = l->next)
1866 if (!REG_P (l->loc) && !MEM_P (l->loc)
1867 /* Avoid infinite recursion when potentially dealing with
1868 var-tracking artificial equivalences, by skipping the
1869 equivalences themselves, and not choosing expressions
1870 that refer to newer VALUEs. */
1872 || (GET_CODE (l->loc) != VALUE
1873 && !refs_newer_value_p (l->loc, x))))
1877 for (l = v->locs; l; l = l->next)
1879 || (GET_CODE (l->loc) != VALUE
1880 && !refs_newer_value_p (l->loc, x)))
1882 /* Return the canonical value. */
1886 return v->locs->loc;
1891 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1892 where SIZE is the size in bytes of the memory reference. If ADDR
1893 is not modified by the memory reference then ADDR is returned. */
1896 addr_side_effect_eval (rtx addr, int size, int n_refs)
1900 switch (GET_CODE (addr))
1903 offset = (n_refs + 1) * size;
1906 offset = -(n_refs + 1) * size;
1909 offset = n_refs * size;
1912 offset = -n_refs * size;
1920 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1923 addr = XEXP (addr, 0);
1924 addr = canon_rtx (addr);
1929 /* Return one if X and Y (memory addresses) reference the
1930 same location in memory or if the references overlap.
1931 Return zero if they do not overlap, else return
1932 minus one in which case they still might reference the same location.
1934 C is an offset accumulator. When
1935 C is nonzero, we are testing aliases between X and Y + C.
1936 XSIZE is the size in bytes of the X reference,
1937 similarly YSIZE is the size in bytes for Y.
1938 Expect that canon_rtx has been already called for X and Y.
1940 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1941 referenced (the reference was BLKmode), so make the most pessimistic
1944 If XSIZE or YSIZE is negative, we may access memory outside the object
1945 being referenced as a side effect. This can happen when using AND to
1946 align memory references, as is done on the Alpha.
1948 Nice to notice that varying addresses cannot conflict with fp if no
1949 local variables had their addresses taken, but that's too hard now.
1951 ??? Contrary to the tree alias oracle this does not return
1952 one for X + non-constant and Y + non-constant when X and Y are equal.
1953 If that is fixed the TBAA hack for union type-punning can be removed. */
1956 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1958 if (GET_CODE (x) == VALUE)
1962 struct elt_loc_list *l = NULL;
1963 if (CSELIB_VAL_PTR (x))
1964 for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
1966 if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
1973 /* Don't call get_addr if y is the same VALUE. */
1977 if (GET_CODE (y) == VALUE)
1981 struct elt_loc_list *l = NULL;
1982 if (CSELIB_VAL_PTR (y))
1983 for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
1985 if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
1992 /* Don't call get_addr if x is the same VALUE. */
1996 if (GET_CODE (x) == HIGH)
1998 else if (GET_CODE (x) == LO_SUM)
2001 x = addr_side_effect_eval (x, xsize, 0);
2002 if (GET_CODE (y) == HIGH)
2004 else if (GET_CODE (y) == LO_SUM)
2007 y = addr_side_effect_eval (y, ysize, 0);
2009 if (rtx_equal_for_memref_p (x, y))
2011 if (xsize <= 0 || ysize <= 0)
2013 if (c >= 0 && xsize > c)
2015 if (c < 0 && ysize+c > 0)
2020 /* This code used to check for conflicts involving stack references and
2021 globals but the base address alias code now handles these cases. */
2023 if (GET_CODE (x) == PLUS)
2025 /* The fact that X is canonicalized means that this
2026 PLUS rtx is canonicalized. */
2027 rtx x0 = XEXP (x, 0);
2028 rtx x1 = XEXP (x, 1);
2030 if (GET_CODE (y) == PLUS)
2032 /* The fact that Y is canonicalized means that this
2033 PLUS rtx is canonicalized. */
2034 rtx y0 = XEXP (y, 0);
2035 rtx y1 = XEXP (y, 1);
2037 if (rtx_equal_for_memref_p (x1, y1))
2038 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2039 if (rtx_equal_for_memref_p (x0, y0))
2040 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
2041 if (CONST_INT_P (x1))
2043 if (CONST_INT_P (y1))
2044 return memrefs_conflict_p (xsize, x0, ysize, y0,
2045 c - INTVAL (x1) + INTVAL (y1));
2047 return memrefs_conflict_p (xsize, x0, ysize, y,
2050 else if (CONST_INT_P (y1))
2051 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
2055 else if (CONST_INT_P (x1))
2056 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
2058 else if (GET_CODE (y) == PLUS)
2060 /* The fact that Y is canonicalized means that this
2061 PLUS rtx is canonicalized. */
2062 rtx y0 = XEXP (y, 0);
2063 rtx y1 = XEXP (y, 1);
2065 if (CONST_INT_P (y1))
2066 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
2071 if (GET_CODE (x) == GET_CODE (y))
2072 switch (GET_CODE (x))
2076 /* Handle cases where we expect the second operands to be the
2077 same, and check only whether the first operand would conflict
2080 rtx x1 = canon_rtx (XEXP (x, 1));
2081 rtx y1 = canon_rtx (XEXP (y, 1));
2082 if (! rtx_equal_for_memref_p (x1, y1))
2084 x0 = canon_rtx (XEXP (x, 0));
2085 y0 = canon_rtx (XEXP (y, 0));
2086 if (rtx_equal_for_memref_p (x0, y0))
2087 return (xsize == 0 || ysize == 0
2088 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
2090 /* Can't properly adjust our sizes. */
2091 if (!CONST_INT_P (x1))
2093 xsize /= INTVAL (x1);
2094 ysize /= INTVAL (x1);
2096 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2103 /* Treat an access through an AND (e.g. a subword access on an Alpha)
2104 as an access with indeterminate size. Assume that references
2105 besides AND are aligned, so if the size of the other reference is
2106 at least as large as the alignment, assume no other overlap. */
2107 if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2109 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
2111 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
2113 if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2115 /* ??? If we are indexing far enough into the array/structure, we
2116 may yet be able to determine that we can not overlap. But we
2117 also need to that we are far enough from the end not to overlap
2118 a following reference, so we do nothing with that for now. */
2119 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
2121 return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
2126 if (CONST_INT_P (x) && CONST_INT_P (y))
2128 c += (INTVAL (y) - INTVAL (x));
2129 return (xsize <= 0 || ysize <= 0
2130 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
2133 if (GET_CODE (x) == CONST)
2135 if (GET_CODE (y) == CONST)
2136 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2137 ysize, canon_rtx (XEXP (y, 0)), c);
2139 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2142 if (GET_CODE (y) == CONST)
2143 return memrefs_conflict_p (xsize, x, ysize,
2144 canon_rtx (XEXP (y, 0)), c);
2147 return (xsize <= 0 || ysize <= 0
2148 || (rtx_equal_for_memref_p (x, y)
2149 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
2157 /* Functions to compute memory dependencies.
2159 Since we process the insns in execution order, we can build tables
2160 to keep track of what registers are fixed (and not aliased), what registers
2161 are varying in known ways, and what registers are varying in unknown
2164 If both memory references are volatile, then there must always be a
2165 dependence between the two references, since their order can not be
2166 changed. A volatile and non-volatile reference can be interchanged
2169 We also must allow AND addresses, because they may generate accesses
2170 outside the object being referenced. This is used to generate aligned
2171 addresses from unaligned addresses, for instance, the alpha
2172 storeqi_unaligned pattern. */
2174 /* Read dependence: X is read after read in MEM takes place. There can
2175 only be a dependence here if both reads are volatile. */
2178 read_dependence (const_rtx mem, const_rtx x)
2180 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
2183 /* Return true if we can determine that the fields referenced cannot
2184 overlap for any pair of objects. */
2187 nonoverlapping_component_refs_p (const_tree x, const_tree y)
2189 const_tree fieldx, fieldy, typex, typey, orig_y;
2191 if (!flag_strict_aliasing)
2196 /* The comparison has to be done at a common type, since we don't
2197 know how the inheritance hierarchy works. */
2201 fieldx = TREE_OPERAND (x, 1);
2202 typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
2207 fieldy = TREE_OPERAND (y, 1);
2208 typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
2213 y = TREE_OPERAND (y, 0);
2215 while (y && TREE_CODE (y) == COMPONENT_REF);
2217 x = TREE_OPERAND (x, 0);
2219 while (x && TREE_CODE (x) == COMPONENT_REF);
2220 /* Never found a common type. */
2224 /* If we're left with accessing different fields of a structure,
2226 if (TREE_CODE (typex) == RECORD_TYPE
2227 && fieldx != fieldy)
2230 /* The comparison on the current field failed. If we're accessing
2231 a very nested structure, look at the next outer level. */
2232 x = TREE_OPERAND (x, 0);
2233 y = TREE_OPERAND (y, 0);
2236 && TREE_CODE (x) == COMPONENT_REF
2237 && TREE_CODE (y) == COMPONENT_REF);
2242 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2245 decl_for_component_ref (tree x)
2249 x = TREE_OPERAND (x, 0);
2251 while (x && TREE_CODE (x) == COMPONENT_REF);
2253 return x && DECL_P (x) ? x : NULL_TREE;
2256 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2257 for the offset of the field reference. *KNOWN_P says whether the
2261 adjust_offset_for_component_ref (tree x, bool *known_p,
2262 HOST_WIDE_INT *offset)
2268 tree xoffset = component_ref_field_offset (x);
2269 tree field = TREE_OPERAND (x, 1);
2271 if (! host_integerp (xoffset, 1))
2276 *offset += (tree_low_cst (xoffset, 1)
2277 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2280 x = TREE_OPERAND (x, 0);
2282 while (x && TREE_CODE (x) == COMPONENT_REF);
2285 /* Return nonzero if we can determine the exprs corresponding to memrefs
2286 X and Y and they do not overlap.
2287 If LOOP_VARIANT is set, skip offset-based disambiguation */
2290 nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2292 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2295 bool moffsetx_known_p, moffsety_known_p;
2296 HOST_WIDE_INT moffsetx = 0, moffsety = 0;
2297 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
2299 /* Unless both have exprs, we can't tell anything. */
2300 if (exprx == 0 || expry == 0)
2303 /* For spill-slot accesses make sure we have valid offsets. */
2304 if ((exprx == get_spill_slot_decl (false)
2305 && ! MEM_OFFSET_KNOWN_P (x))
2306 || (expry == get_spill_slot_decl (false)
2307 && ! MEM_OFFSET_KNOWN_P (y)))
2310 /* If both are field references, we may be able to determine something. */
2311 if (TREE_CODE (exprx) == COMPONENT_REF
2312 && TREE_CODE (expry) == COMPONENT_REF
2313 && nonoverlapping_component_refs_p (exprx, expry))
2317 /* If the field reference test failed, look at the DECLs involved. */
2318 moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2319 if (moffsetx_known_p)
2320 moffsetx = MEM_OFFSET (x);
2321 if (TREE_CODE (exprx) == COMPONENT_REF)
2323 tree t = decl_for_component_ref (exprx);
2326 adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2330 moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2331 if (moffsety_known_p)
2332 moffsety = MEM_OFFSET (y);
2333 if (TREE_CODE (expry) == COMPONENT_REF)
2335 tree t = decl_for_component_ref (expry);
2338 adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2342 if (! DECL_P (exprx) || ! DECL_P (expry))
2345 /* With invalid code we can end up storing into the constant pool.
2346 Bail out to avoid ICEing when creating RTL for this.
2347 See gfortran.dg/lto/20091028-2_0.f90. */
2348 if (TREE_CODE (exprx) == CONST_DECL
2349 || TREE_CODE (expry) == CONST_DECL)
2352 rtlx = DECL_RTL (exprx);
2353 rtly = DECL_RTL (expry);
2355 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2356 can't overlap unless they are the same because we never reuse that part
2357 of the stack frame used for locals for spilled pseudos. */
2358 if ((!MEM_P (rtlx) || !MEM_P (rtly))
2359 && ! rtx_equal_p (rtlx, rtly))
2362 /* If we have MEMs referring to different address spaces (which can
2363 potentially overlap), we cannot easily tell from the addresses
2364 whether the references overlap. */
2365 if (MEM_P (rtlx) && MEM_P (rtly)
2366 && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2369 /* Get the base and offsets of both decls. If either is a register, we
2370 know both are and are the same, so use that as the base. The only
2371 we can avoid overlap is if we can deduce that they are nonoverlapping
2372 pieces of that decl, which is very rare. */
2373 basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2374 if (GET_CODE (basex) == PLUS && CONST_INT_P (XEXP (basex, 1)))
2375 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2377 basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2378 if (GET_CODE (basey) == PLUS && CONST_INT_P (XEXP (basey, 1)))
2379 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2381 /* If the bases are different, we know they do not overlap if both
2382 are constants or if one is a constant and the other a pointer into the
2383 stack frame. Otherwise a different base means we can't tell if they
2385 if (! rtx_equal_p (basex, basey))
2386 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2387 || (CONSTANT_P (basex) && REG_P (basey)
2388 && REGNO_PTR_FRAME_P (REGNO (basey)))
2389 || (CONSTANT_P (basey) && REG_P (basex)
2390 && REGNO_PTR_FRAME_P (REGNO (basex))));
2392 /* Offset based disambiguation not appropriate for loop invariant */
2396 sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2397 : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2399 sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2400 : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2403 /* If we have an offset for either memref, it can update the values computed
2405 if (moffsetx_known_p)
2406 offsetx += moffsetx, sizex -= moffsetx;
2407 if (moffsety_known_p)
2408 offsety += moffsety, sizey -= moffsety;
2410 /* If a memref has both a size and an offset, we can use the smaller size.
2411 We can't do this if the offset isn't known because we must view this
2412 memref as being anywhere inside the DECL's MEM. */
2413 if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2414 sizex = MEM_SIZE (x);
2415 if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2416 sizey = MEM_SIZE (y);
2418 /* Put the values of the memref with the lower offset in X's values. */
2419 if (offsetx > offsety)
2421 tem = offsetx, offsetx = offsety, offsety = tem;
2422 tem = sizex, sizex = sizey, sizey = tem;
2425 /* If we don't know the size of the lower-offset value, we can't tell
2426 if they conflict. Otherwise, we do the test. */
2427 return sizex >= 0 && offsety >= offsetx + sizex;
2430 /* Helper for true_dependence and canon_true_dependence.
2431 Checks for true dependence: X is read after store in MEM takes place.
2433 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2434 NULL_RTX, and the canonical addresses of MEM and X are both computed
2435 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2437 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2439 Returns 1 if there is a true dependence, 0 otherwise. */
2442 true_dependence_1 (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2443 const_rtx x, rtx x_addr, bool mem_canonicalized)
2448 gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2449 : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2451 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2454 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2455 This is used in epilogue deallocation functions, and in cselib. */
2456 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2458 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2460 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2461 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2464 /* Read-only memory is by definition never modified, and therefore can't
2465 conflict with anything. We don't expect to find read-only set on MEM,
2466 but stupid user tricks can produce them, so don't die. */
2467 if (MEM_READONLY_P (x))
2470 /* If we have MEMs referring to different address spaces (which can
2471 potentially overlap), we cannot easily tell from the addresses
2472 whether the references overlap. */
2473 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2478 mem_addr = XEXP (mem, 0);
2479 if (mem_mode == VOIDmode)
2480 mem_mode = GET_MODE (mem);
2485 x_addr = XEXP (x, 0);
2486 if (!((GET_CODE (x_addr) == VALUE
2487 && GET_CODE (mem_addr) != VALUE
2488 && reg_mentioned_p (x_addr, mem_addr))
2489 || (GET_CODE (x_addr) != VALUE
2490 && GET_CODE (mem_addr) == VALUE
2491 && reg_mentioned_p (mem_addr, x_addr))))
2493 x_addr = get_addr (x_addr);
2494 if (! mem_canonicalized)
2495 mem_addr = get_addr (mem_addr);
2499 base = find_base_term (x_addr);
2500 if (base && (GET_CODE (base) == LABEL_REF
2501 || (GET_CODE (base) == SYMBOL_REF
2502 && CONSTANT_POOL_ADDRESS_P (base))))
2505 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2508 x_addr = canon_rtx (x_addr);
2509 if (!mem_canonicalized)
2510 mem_addr = canon_rtx (mem_addr);
2512 if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2513 SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2516 if (mems_in_disjoint_alias_sets_p (x, mem))
2519 if (nonoverlapping_memrefs_p (mem, x, false))
2522 return rtx_refs_may_alias_p (x, mem, true);
2525 /* True dependence: X is read after store in MEM takes place. */
2528 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x)
2530 return true_dependence_1 (mem, mem_mode, NULL_RTX,
2531 x, NULL_RTX, /*mem_canonicalized=*/false);
2534 /* Canonical true dependence: X is read after store in MEM takes place.
2535 Variant of true_dependence which assumes MEM has already been
2536 canonicalized (hence we no longer do that here).
2537 The mem_addr argument has been added, since true_dependence_1 computed
2538 this value prior to canonicalizing. */
2541 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2542 const_rtx x, rtx x_addr)
2544 return true_dependence_1 (mem, mem_mode, mem_addr,
2545 x, x_addr, /*mem_canonicalized=*/true);
2548 /* Returns nonzero if a write to X might alias a previous read from
2549 (or, if WRITEP is nonzero, a write to) MEM. */
2552 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2554 rtx x_addr, mem_addr;
2558 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2561 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2562 This is used in epilogue deallocation functions. */
2563 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2565 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2567 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2568 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2571 /* A read from read-only memory can't conflict with read-write memory. */
2572 if (!writep && MEM_READONLY_P (mem))
2575 /* If we have MEMs referring to different address spaces (which can
2576 potentially overlap), we cannot easily tell from the addresses
2577 whether the references overlap. */
2578 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2581 x_addr = XEXP (x, 0);
2582 mem_addr = XEXP (mem, 0);
2583 if (!((GET_CODE (x_addr) == VALUE
2584 && GET_CODE (mem_addr) != VALUE
2585 && reg_mentioned_p (x_addr, mem_addr))
2586 || (GET_CODE (x_addr) != VALUE
2587 && GET_CODE (mem_addr) == VALUE
2588 && reg_mentioned_p (mem_addr, x_addr))))
2590 x_addr = get_addr (x_addr);
2591 mem_addr = get_addr (mem_addr);
2596 base = find_base_term (mem_addr);
2597 if (base && (GET_CODE (base) == LABEL_REF
2598 || (GET_CODE (base) == SYMBOL_REF
2599 && CONSTANT_POOL_ADDRESS_P (base))))
2603 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2607 x_addr = canon_rtx (x_addr);
2608 mem_addr = canon_rtx (mem_addr);
2610 if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2611 SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2614 if (nonoverlapping_memrefs_p (x, mem, false))
2617 return rtx_refs_may_alias_p (x, mem, false);
2620 /* Anti dependence: X is written after read in MEM takes place. */
2623 anti_dependence (const_rtx mem, const_rtx x)
2625 return write_dependence_p (mem, x, /*writep=*/0);
2628 /* Output dependence: X is written after store in MEM takes place. */
2631 output_dependence (const_rtx mem, const_rtx x)
2633 return write_dependence_p (mem, x, /*writep=*/1);
2638 /* Check whether X may be aliased with MEM. Don't do offset-based
2639 memory disambiguation & TBAA. */
2641 may_alias_p (const_rtx mem, const_rtx x)
2643 rtx x_addr, mem_addr;
2645 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2648 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2649 This is used in epilogue deallocation functions. */
2650 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2652 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2654 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2655 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2658 /* Read-only memory is by definition never modified, and therefore can't
2659 conflict with anything. We don't expect to find read-only set on MEM,
2660 but stupid user tricks can produce them, so don't die. */
2661 if (MEM_READONLY_P (x))
2664 /* If we have MEMs referring to different address spaces (which can
2665 potentially overlap), we cannot easily tell from the addresses
2666 whether the references overlap. */
2667 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2670 x_addr = XEXP (x, 0);
2671 mem_addr = XEXP (mem, 0);
2672 if (!((GET_CODE (x_addr) == VALUE
2673 && GET_CODE (mem_addr) != VALUE
2674 && reg_mentioned_p (x_addr, mem_addr))
2675 || (GET_CODE (x_addr) != VALUE
2676 && GET_CODE (mem_addr) == VALUE
2677 && reg_mentioned_p (mem_addr, x_addr))))
2679 x_addr = get_addr (x_addr);
2680 mem_addr = get_addr (mem_addr);
2683 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), GET_MODE (mem_addr)))
2686 x_addr = canon_rtx (x_addr);
2687 mem_addr = canon_rtx (mem_addr);
2689 if (nonoverlapping_memrefs_p (mem, x, true))
2692 /* TBAA not valid for loop_invarint */
2693 return rtx_refs_may_alias_p (x, mem, false);
2697 init_alias_target (void)
2701 if (!arg_base_value)
2702 arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
2704 memset (static_reg_base_value, 0, sizeof static_reg_base_value);
2706 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2707 /* Check whether this register can hold an incoming pointer
2708 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2709 numbers, so translate if necessary due to register windows. */
2710 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2711 && HARD_REGNO_MODE_OK (i, Pmode))
2712 static_reg_base_value[i] = arg_base_value;
2714 static_reg_base_value[STACK_POINTER_REGNUM]
2715 = unique_base_value (UNIQUE_BASE_VALUE_SP);
2716 static_reg_base_value[ARG_POINTER_REGNUM]
2717 = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
2718 static_reg_base_value[FRAME_POINTER_REGNUM]
2719 = unique_base_value (UNIQUE_BASE_VALUE_FP);
2720 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2721 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2722 = unique_base_value (UNIQUE_BASE_VALUE_HFP);
2726 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2727 to be memory reference. */
2728 static bool memory_modified;
2730 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2734 if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
2735 memory_modified = true;
2740 /* Return true when INSN possibly modify memory contents of MEM
2741 (i.e. address can be modified). */
2743 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
2747 memory_modified = false;
2748 note_stores (PATTERN (insn), memory_modified_1, CONST_CAST_RTX(mem));
2749 return memory_modified;
2752 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2756 init_alias_analysis (void)
2758 unsigned int maxreg = max_reg_num ();
2764 timevar_push (TV_ALIAS_ANALYSIS);
2766 reg_known_value = VEC_alloc (rtx, gc, maxreg - FIRST_PSEUDO_REGISTER);
2767 reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
2769 /* If we have memory allocated from the previous run, use it. */
2770 if (old_reg_base_value)
2771 reg_base_value = old_reg_base_value;
2774 VEC_truncate (rtx, reg_base_value, 0);
2776 VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2778 new_reg_base_value = XNEWVEC (rtx, maxreg);
2779 reg_seen = XNEWVEC (char, maxreg);
2781 /* The basic idea is that each pass through this loop will use the
2782 "constant" information from the previous pass to propagate alias
2783 information through another level of assignments.
2785 This could get expensive if the assignment chains are long. Maybe
2786 we should throttle the number of iterations, possibly based on
2787 the optimization level or flag_expensive_optimizations.
2789 We could propagate more information in the first pass by making use
2790 of DF_REG_DEF_COUNT to determine immediately that the alias information
2791 for a pseudo is "constant".
2793 A program with an uninitialized variable can cause an infinite loop
2794 here. Instead of doing a full dataflow analysis to detect such problems
2795 we just cap the number of iterations for the loop.
2797 The state of the arrays for the set chain in question does not matter
2798 since the program has undefined behavior. */
2803 /* Assume nothing will change this iteration of the loop. */
2806 /* We want to assign the same IDs each iteration of this loop, so
2807 start counting from one each iteration of the loop. */
2810 /* We're at the start of the function each iteration through the
2811 loop, so we're copying arguments. */
2812 copying_arguments = true;
2814 /* Wipe the potential alias information clean for this pass. */
2815 memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2817 /* Wipe the reg_seen array clean. */
2818 memset (reg_seen, 0, maxreg);
2820 /* Mark all hard registers which may contain an address.
2821 The stack, frame and argument pointers may contain an address.
2822 An argument register which can hold a Pmode value may contain
2823 an address even if it is not in BASE_REGS.
2825 The address expression is VOIDmode for an argument and
2826 Pmode for other registers. */
2828 memcpy (new_reg_base_value, static_reg_base_value,
2829 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2831 /* Walk the insns adding values to the new_reg_base_value array. */
2832 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2838 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2839 /* The prologue/epilogue insns are not threaded onto the
2840 insn chain until after reload has completed. Thus,
2841 there is no sense wasting time checking if INSN is in
2842 the prologue/epilogue until after reload has completed. */
2843 if (reload_completed
2844 && prologue_epilogue_contains (insn))
2848 /* If this insn has a noalias note, process it, Otherwise,
2849 scan for sets. A simple set will have no side effects
2850 which could change the base value of any other register. */
2852 if (GET_CODE (PATTERN (insn)) == SET
2853 && REG_NOTES (insn) != 0
2854 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2855 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2857 note_stores (PATTERN (insn), record_set, NULL);
2859 set = single_set (insn);
2862 && REG_P (SET_DEST (set))
2863 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2865 unsigned int regno = REGNO (SET_DEST (set));
2866 rtx src = SET_SRC (set);
2869 note = find_reg_equal_equiv_note (insn);
2870 if (note && REG_NOTE_KIND (note) == REG_EQUAL
2871 && DF_REG_DEF_COUNT (regno) != 1)
2874 if (note != NULL_RTX
2875 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2876 && ! rtx_varies_p (XEXP (note, 0), 1)
2877 && ! reg_overlap_mentioned_p (SET_DEST (set),
2880 set_reg_known_value (regno, XEXP (note, 0));
2881 set_reg_known_equiv_p (regno,
2882 REG_NOTE_KIND (note) == REG_EQUIV);
2884 else if (DF_REG_DEF_COUNT (regno) == 1
2885 && GET_CODE (src) == PLUS
2886 && REG_P (XEXP (src, 0))
2887 && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2888 && CONST_INT_P (XEXP (src, 1)))
2890 t = plus_constant (GET_MODE (src), t,
2891 INTVAL (XEXP (src, 1)));
2892 set_reg_known_value (regno, t);
2893 set_reg_known_equiv_p (regno, false);
2895 else if (DF_REG_DEF_COUNT (regno) == 1
2896 && ! rtx_varies_p (src, 1))
2898 set_reg_known_value (regno, src);
2899 set_reg_known_equiv_p (regno, false);
2903 else if (NOTE_P (insn)
2904 && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2905 copying_arguments = false;
2908 /* Now propagate values from new_reg_base_value to reg_base_value. */
2909 gcc_assert (maxreg == (unsigned int) max_reg_num ());
2911 for (ui = 0; ui < maxreg; ui++)
2913 if (new_reg_base_value[ui]
2914 && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2915 && ! rtx_equal_p (new_reg_base_value[ui],
2916 VEC_index (rtx, reg_base_value, ui)))
2918 VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2923 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2925 /* Fill in the remaining entries. */
2926 FOR_EACH_VEC_ELT (rtx, reg_known_value, i, val)
2928 int regno = i + FIRST_PSEUDO_REGISTER;
2930 set_reg_known_value (regno, regno_reg_rtx[regno]);
2934 free (new_reg_base_value);
2935 new_reg_base_value = 0;
2938 timevar_pop (TV_ALIAS_ANALYSIS);
2941 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
2942 Special API for var-tracking pass purposes. */
2945 vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
2947 VEC_replace (rtx, reg_base_value, REGNO (reg1), REG_BASE_VALUE (reg2));
2951 end_alias_analysis (void)
2953 old_reg_base_value = reg_base_value;
2954 VEC_free (rtx, gc, reg_known_value);
2955 sbitmap_free (reg_known_equiv_p);
2958 #include "gt-alias.h"