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"
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_rtx, const_rtx);
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.
172 ??? 10 is a completely arbitrary choice. This should be based on the
173 maximum loop depth in the CFG, but we do not have this information
174 available (even if current_loops _is_ available). */
175 #define MAX_ALIAS_LOOP_PASSES 10
177 /* reg_base_value[N] gives an address to which register N is related.
178 If all sets after the first add or subtract to the current value
179 or otherwise modify it so it does not point to a different top level
180 object, reg_base_value[N] is equal to the address part of the source
183 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
184 expressions represent three types of base:
186 1. incoming arguments. There is just one ADDRESS to represent all
187 arguments, since we do not know at this level whether accesses
188 based on different arguments can alias. The ADDRESS has id 0.
190 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
191 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
192 Each of these rtxes has a separate ADDRESS associated with it,
193 each with a negative id.
195 GCC is (and is required to be) precise in which register it
196 chooses to access a particular region of stack. We can therefore
197 assume that accesses based on one of these rtxes do not alias
198 accesses based on another of these rtxes.
200 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
201 Each such piece of memory has a separate ADDRESS associated
202 with it, each with an id greater than 0.
204 Accesses based on one ADDRESS do not alias accesses based on other
205 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
206 alias globals either; the ADDRESSes have Pmode to indicate this.
207 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
210 static GTY(()) VEC(rtx,gc) *reg_base_value;
211 static rtx *new_reg_base_value;
213 /* The single VOIDmode ADDRESS that represents all argument bases.
215 static GTY(()) rtx arg_base_value;
217 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
218 static int unique_id;
220 /* We preserve the copy of old array around to avoid amount of garbage
221 produced. About 8% of garbage produced were attributed to this
223 static GTY((deletable)) VEC(rtx,gc) *old_reg_base_value;
225 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
227 #define UNIQUE_BASE_VALUE_SP -1
228 #define UNIQUE_BASE_VALUE_ARGP -2
229 #define UNIQUE_BASE_VALUE_FP -3
230 #define UNIQUE_BASE_VALUE_HFP -4
232 #define static_reg_base_value \
233 (this_target_rtl->x_static_reg_base_value)
235 #define REG_BASE_VALUE(X) \
236 (REGNO (X) < VEC_length (rtx, reg_base_value) \
237 ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
239 /* Vector indexed by N giving the initial (unchanging) value known for
240 pseudo-register N. This vector is initialized in init_alias_analysis,
241 and does not change until end_alias_analysis is called. */
242 static GTY(()) VEC(rtx,gc) *reg_known_value;
244 /* Vector recording for each reg_known_value whether it is due to a
245 REG_EQUIV note. Future passes (viz., reload) may replace the
246 pseudo with the equivalent expression and so we account for the
247 dependences that would be introduced if that happens.
249 The REG_EQUIV notes created in assign_parms may mention the arg
250 pointer, and there are explicit insns in the RTL that modify the
251 arg pointer. Thus we must ensure that such insns don't get
252 scheduled across each other because that would invalidate the
253 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
254 wrong, but solving the problem in the scheduler will likely give
255 better code, so we do it here. */
256 static sbitmap reg_known_equiv_p;
258 /* True when scanning insns from the start of the rtl to the
259 NOTE_INSN_FUNCTION_BEG note. */
260 static bool copying_arguments;
262 DEF_VEC_P(alias_set_entry);
263 DEF_VEC_ALLOC_P(alias_set_entry,gc);
265 /* The splay-tree used to store the various alias set entries. */
266 static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
268 /* Build a decomposed reference object for querying the alias-oracle
269 from the MEM rtx and store it in *REF.
270 Returns false if MEM is not suitable for the alias-oracle. */
273 ao_ref_from_mem (ao_ref *ref, const_rtx mem)
275 tree expr = MEM_EXPR (mem);
281 ao_ref_init (ref, expr);
283 /* Get the base of the reference and see if we have to reject or
285 base = ao_ref_base (ref);
286 if (base == NULL_TREE)
289 /* The tree oracle doesn't like to have these. */
290 if (TREE_CODE (base) == FUNCTION_DECL
291 || TREE_CODE (base) == LABEL_DECL)
294 /* If this is a pointer dereference of a non-SSA_NAME punt.
295 ??? We could replace it with a pointer to anything. */
296 if ((INDIRECT_REF_P (base)
297 || TREE_CODE (base) == MEM_REF)
298 && TREE_CODE (TREE_OPERAND (base, 0)) != SSA_NAME)
300 if (TREE_CODE (base) == TARGET_MEM_REF
302 && TREE_CODE (TMR_BASE (base)) != SSA_NAME)
305 /* If this is a reference based on a partitioned decl replace the
306 base with an INDIRECT_REF of the pointer representative we
307 created during stack slot partitioning. */
308 if (TREE_CODE (base) == VAR_DECL
309 && ! TREE_STATIC (base)
310 && cfun->gimple_df->decls_to_pointers != NULL)
313 namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers, base);
315 ref->base = build_simple_mem_ref (*(tree *)namep);
317 else if (TREE_CODE (base) == TARGET_MEM_REF
318 && TREE_CODE (TMR_BASE (base)) == ADDR_EXPR
319 && TREE_CODE (TREE_OPERAND (TMR_BASE (base), 0)) == VAR_DECL
320 && ! TREE_STATIC (TREE_OPERAND (TMR_BASE (base), 0))
321 && cfun->gimple_df->decls_to_pointers != NULL)
324 namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers,
325 TREE_OPERAND (TMR_BASE (base), 0));
327 ref->base = build_simple_mem_ref (*(tree *)namep);
330 ref->ref_alias_set = MEM_ALIAS_SET (mem);
332 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
333 is conservative, so trust it. */
334 if (!MEM_OFFSET_KNOWN_P (mem)
335 || !MEM_SIZE_KNOWN_P (mem))
338 /* If the base decl is a parameter we can have negative MEM_OFFSET in
339 case of promoted subregs on bigendian targets. Trust the MEM_EXPR
341 if (MEM_OFFSET (mem) < 0
342 && (MEM_SIZE (mem) + MEM_OFFSET (mem)) * BITS_PER_UNIT == ref->size)
345 /* Otherwise continue and refine size and offset we got from analyzing
346 MEM_EXPR by using MEM_SIZE and MEM_OFFSET. */
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, (alias_set_entry) 0);
859 VEC_safe_push (alias_set_entry, gc, alias_sets, (alias_set_entry) 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 /* Deal with alignment ANDs by adjusting offset and size so as to
2104 cover the maximum range, without taking any previously known
2105 alignment into account. */
2106 if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2108 HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2109 unsigned HOST_WIDE_INT uc = sc;
2110 if (xsize > 0 && sc < 0 && -uc == (uc & -uc))
2114 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2118 if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2120 HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2121 unsigned HOST_WIDE_INT uc = sc;
2122 if (ysize > 0 && sc < 0 && -uc == (uc & -uc))
2126 return memrefs_conflict_p (xsize, x,
2127 ysize, canon_rtx (XEXP (y, 0)), c);
2133 if (CONST_INT_P (x) && CONST_INT_P (y))
2135 c += (INTVAL (y) - INTVAL (x));
2136 return (xsize <= 0 || ysize <= 0
2137 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
2140 if (GET_CODE (x) == CONST)
2142 if (GET_CODE (y) == CONST)
2143 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2144 ysize, canon_rtx (XEXP (y, 0)), c);
2146 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2149 if (GET_CODE (y) == CONST)
2150 return memrefs_conflict_p (xsize, x, ysize,
2151 canon_rtx (XEXP (y, 0)), c);
2154 return (xsize <= 0 || ysize <= 0
2155 || (rtx_equal_for_memref_p (x, y)
2156 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
2164 /* Functions to compute memory dependencies.
2166 Since we process the insns in execution order, we can build tables
2167 to keep track of what registers are fixed (and not aliased), what registers
2168 are varying in known ways, and what registers are varying in unknown
2171 If both memory references are volatile, then there must always be a
2172 dependence between the two references, since their order can not be
2173 changed. A volatile and non-volatile reference can be interchanged
2176 We also must allow AND addresses, because they may generate accesses
2177 outside the object being referenced. This is used to generate aligned
2178 addresses from unaligned addresses, for instance, the alpha
2179 storeqi_unaligned pattern. */
2181 /* Read dependence: X is read after read in MEM takes place. There can
2182 only be a dependence here if both reads are volatile. */
2185 read_dependence (const_rtx mem, const_rtx x)
2187 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
2190 /* Return true if we can determine that the fields referenced cannot
2191 overlap for any pair of objects. */
2194 nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly)
2196 const_tree x = MEM_EXPR (rtlx), y = MEM_EXPR (rtly);
2197 const_tree fieldx, fieldy, typex, typey, orig_y;
2199 if (!flag_strict_aliasing
2201 || TREE_CODE (x) != COMPONENT_REF
2202 || TREE_CODE (y) != COMPONENT_REF)
2207 /* The comparison has to be done at a common type, since we don't
2208 know how the inheritance hierarchy works. */
2212 fieldx = TREE_OPERAND (x, 1);
2213 typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
2218 fieldy = TREE_OPERAND (y, 1);
2219 typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
2224 y = TREE_OPERAND (y, 0);
2226 while (y && TREE_CODE (y) == COMPONENT_REF);
2228 x = TREE_OPERAND (x, 0);
2230 while (x && TREE_CODE (x) == COMPONENT_REF);
2231 /* Never found a common type. */
2235 /* If we're left with accessing different fields of a structure,
2237 if (TREE_CODE (typex) == RECORD_TYPE
2238 && fieldx != fieldy)
2241 /* The comparison on the current field failed. If we're accessing
2242 a very nested structure, look at the next outer level. */
2243 x = TREE_OPERAND (x, 0);
2244 y = TREE_OPERAND (y, 0);
2247 && TREE_CODE (x) == COMPONENT_REF
2248 && TREE_CODE (y) == COMPONENT_REF);
2253 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2256 decl_for_component_ref (tree x)
2260 x = TREE_OPERAND (x, 0);
2262 while (x && TREE_CODE (x) == COMPONENT_REF);
2264 return x && DECL_P (x) ? x : NULL_TREE;
2267 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2268 for the offset of the field reference. *KNOWN_P says whether the
2272 adjust_offset_for_component_ref (tree x, bool *known_p,
2273 HOST_WIDE_INT *offset)
2279 tree xoffset = component_ref_field_offset (x);
2280 tree field = TREE_OPERAND (x, 1);
2282 if (! host_integerp (xoffset, 1))
2287 *offset += (tree_low_cst (xoffset, 1)
2288 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2291 x = TREE_OPERAND (x, 0);
2293 while (x && TREE_CODE (x) == COMPONENT_REF);
2296 /* Return nonzero if we can determine the exprs corresponding to memrefs
2297 X and Y and they do not overlap.
2298 If LOOP_VARIANT is set, skip offset-based disambiguation */
2301 nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2303 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2306 bool moffsetx_known_p, moffsety_known_p;
2307 HOST_WIDE_INT moffsetx = 0, moffsety = 0;
2308 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
2310 /* Unless both have exprs, we can't tell anything. */
2311 if (exprx == 0 || expry == 0)
2314 /* For spill-slot accesses make sure we have valid offsets. */
2315 if ((exprx == get_spill_slot_decl (false)
2316 && ! MEM_OFFSET_KNOWN_P (x))
2317 || (expry == get_spill_slot_decl (false)
2318 && ! MEM_OFFSET_KNOWN_P (y)))
2321 /* If the field reference test failed, look at the DECLs involved. */
2322 moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2323 if (moffsetx_known_p)
2324 moffsetx = MEM_OFFSET (x);
2325 if (TREE_CODE (exprx) == COMPONENT_REF)
2327 tree t = decl_for_component_ref (exprx);
2330 adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2334 moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2335 if (moffsety_known_p)
2336 moffsety = MEM_OFFSET (y);
2337 if (TREE_CODE (expry) == COMPONENT_REF)
2339 tree t = decl_for_component_ref (expry);
2342 adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2346 if (! DECL_P (exprx) || ! DECL_P (expry))
2349 /* With invalid code we can end up storing into the constant pool.
2350 Bail out to avoid ICEing when creating RTL for this.
2351 See gfortran.dg/lto/20091028-2_0.f90. */
2352 if (TREE_CODE (exprx) == CONST_DECL
2353 || TREE_CODE (expry) == CONST_DECL)
2356 rtlx = DECL_RTL (exprx);
2357 rtly = DECL_RTL (expry);
2359 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2360 can't overlap unless they are the same because we never reuse that part
2361 of the stack frame used for locals for spilled pseudos. */
2362 if ((!MEM_P (rtlx) || !MEM_P (rtly))
2363 && ! rtx_equal_p (rtlx, rtly))
2366 /* If we have MEMs referring to different address spaces (which can
2367 potentially overlap), we cannot easily tell from the addresses
2368 whether the references overlap. */
2369 if (MEM_P (rtlx) && MEM_P (rtly)
2370 && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2373 /* Get the base and offsets of both decls. If either is a register, we
2374 know both are and are the same, so use that as the base. The only
2375 we can avoid overlap is if we can deduce that they are nonoverlapping
2376 pieces of that decl, which is very rare. */
2377 basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2378 if (GET_CODE (basex) == PLUS && CONST_INT_P (XEXP (basex, 1)))
2379 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2381 basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2382 if (GET_CODE (basey) == PLUS && CONST_INT_P (XEXP (basey, 1)))
2383 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2385 /* If the bases are different, we know they do not overlap if both
2386 are constants or if one is a constant and the other a pointer into the
2387 stack frame. Otherwise a different base means we can't tell if they
2389 if (! rtx_equal_p (basex, basey))
2390 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2391 || (CONSTANT_P (basex) && REG_P (basey)
2392 && REGNO_PTR_FRAME_P (REGNO (basey)))
2393 || (CONSTANT_P (basey) && REG_P (basex)
2394 && REGNO_PTR_FRAME_P (REGNO (basex))));
2396 /* Offset based disambiguation not appropriate for loop invariant */
2400 sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2401 : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2403 sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2404 : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2407 /* If we have an offset for either memref, it can update the values computed
2409 if (moffsetx_known_p)
2410 offsetx += moffsetx, sizex -= moffsetx;
2411 if (moffsety_known_p)
2412 offsety += moffsety, sizey -= moffsety;
2414 /* If a memref has both a size and an offset, we can use the smaller size.
2415 We can't do this if the offset isn't known because we must view this
2416 memref as being anywhere inside the DECL's MEM. */
2417 if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2418 sizex = MEM_SIZE (x);
2419 if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2420 sizey = MEM_SIZE (y);
2422 /* Put the values of the memref with the lower offset in X's values. */
2423 if (offsetx > offsety)
2425 tem = offsetx, offsetx = offsety, offsety = tem;
2426 tem = sizex, sizex = sizey, sizey = tem;
2429 /* If we don't know the size of the lower-offset value, we can't tell
2430 if they conflict. Otherwise, we do the test. */
2431 return sizex >= 0 && offsety >= offsetx + sizex;
2434 /* Helper for true_dependence and canon_true_dependence.
2435 Checks for true dependence: X is read after store in MEM takes place.
2437 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2438 NULL_RTX, and the canonical addresses of MEM and X are both computed
2439 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2441 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2443 Returns 1 if there is a true dependence, 0 otherwise. */
2446 true_dependence_1 (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2447 const_rtx x, rtx x_addr, bool mem_canonicalized)
2452 gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2453 : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2455 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2458 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2459 This is used in epilogue deallocation functions, and in cselib. */
2460 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2462 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2464 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2465 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2468 /* Read-only memory is by definition never modified, and therefore can't
2469 conflict with anything. We don't expect to find read-only set on MEM,
2470 but stupid user tricks can produce them, so don't die. */
2471 if (MEM_READONLY_P (x))
2474 /* If we have MEMs referring to different address spaces (which can
2475 potentially overlap), we cannot easily tell from the addresses
2476 whether the references overlap. */
2477 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2482 mem_addr = XEXP (mem, 0);
2483 if (mem_mode == VOIDmode)
2484 mem_mode = GET_MODE (mem);
2489 x_addr = XEXP (x, 0);
2490 if (!((GET_CODE (x_addr) == VALUE
2491 && GET_CODE (mem_addr) != VALUE
2492 && reg_mentioned_p (x_addr, mem_addr))
2493 || (GET_CODE (x_addr) != VALUE
2494 && GET_CODE (mem_addr) == VALUE
2495 && reg_mentioned_p (mem_addr, x_addr))))
2497 x_addr = get_addr (x_addr);
2498 if (! mem_canonicalized)
2499 mem_addr = get_addr (mem_addr);
2503 base = find_base_term (x_addr);
2504 if (base && (GET_CODE (base) == LABEL_REF
2505 || (GET_CODE (base) == SYMBOL_REF
2506 && CONSTANT_POOL_ADDRESS_P (base))))
2509 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2512 x_addr = canon_rtx (x_addr);
2513 if (!mem_canonicalized)
2514 mem_addr = canon_rtx (mem_addr);
2516 if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2517 SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2520 if (mems_in_disjoint_alias_sets_p (x, mem))
2523 if (nonoverlapping_memrefs_p (mem, x, false))
2526 if (nonoverlapping_component_refs_p (mem, x))
2529 return rtx_refs_may_alias_p (x, mem, true);
2532 /* True dependence: X is read after store in MEM takes place. */
2535 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x)
2537 return true_dependence_1 (mem, mem_mode, NULL_RTX,
2538 x, NULL_RTX, /*mem_canonicalized=*/false);
2541 /* Canonical true dependence: X is read after store in MEM takes place.
2542 Variant of true_dependence which assumes MEM has already been
2543 canonicalized (hence we no longer do that here).
2544 The mem_addr argument has been added, since true_dependence_1 computed
2545 this value prior to canonicalizing. */
2548 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2549 const_rtx x, rtx x_addr)
2551 return true_dependence_1 (mem, mem_mode, mem_addr,
2552 x, x_addr, /*mem_canonicalized=*/true);
2555 /* Returns nonzero if a write to X might alias a previous read from
2556 (or, if WRITEP is nonzero, a write to) MEM. */
2559 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2561 rtx x_addr, mem_addr;
2565 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2568 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2569 This is used in epilogue deallocation functions. */
2570 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2572 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2574 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2575 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2578 /* A read from read-only memory can't conflict with read-write memory. */
2579 if (!writep && MEM_READONLY_P (mem))
2582 /* If we have MEMs referring to different address spaces (which can
2583 potentially overlap), we cannot easily tell from the addresses
2584 whether the references overlap. */
2585 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2588 x_addr = XEXP (x, 0);
2589 mem_addr = XEXP (mem, 0);
2590 if (!((GET_CODE (x_addr) == VALUE
2591 && GET_CODE (mem_addr) != VALUE
2592 && reg_mentioned_p (x_addr, mem_addr))
2593 || (GET_CODE (x_addr) != VALUE
2594 && GET_CODE (mem_addr) == VALUE
2595 && reg_mentioned_p (mem_addr, x_addr))))
2597 x_addr = get_addr (x_addr);
2598 mem_addr = get_addr (mem_addr);
2603 base = find_base_term (mem_addr);
2604 if (base && (GET_CODE (base) == LABEL_REF
2605 || (GET_CODE (base) == SYMBOL_REF
2606 && CONSTANT_POOL_ADDRESS_P (base))))
2610 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2614 x_addr = canon_rtx (x_addr);
2615 mem_addr = canon_rtx (mem_addr);
2617 if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2618 SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2621 if (nonoverlapping_memrefs_p (x, mem, false))
2624 return rtx_refs_may_alias_p (x, mem, false);
2627 /* Anti dependence: X is written after read in MEM takes place. */
2630 anti_dependence (const_rtx mem, const_rtx x)
2632 return write_dependence_p (mem, x, /*writep=*/0);
2635 /* Output dependence: X is written after store in MEM takes place. */
2638 output_dependence (const_rtx mem, const_rtx x)
2640 return write_dependence_p (mem, x, /*writep=*/1);
2645 /* Check whether X may be aliased with MEM. Don't do offset-based
2646 memory disambiguation & TBAA. */
2648 may_alias_p (const_rtx mem, const_rtx x)
2650 rtx x_addr, mem_addr;
2652 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2655 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2656 This is used in epilogue deallocation functions. */
2657 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2659 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2661 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2662 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2665 /* Read-only memory is by definition never modified, and therefore can't
2666 conflict with anything. We don't expect to find read-only set on MEM,
2667 but stupid user tricks can produce them, so don't die. */
2668 if (MEM_READONLY_P (x))
2671 /* If we have MEMs referring to different address spaces (which can
2672 potentially overlap), we cannot easily tell from the addresses
2673 whether the references overlap. */
2674 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2677 x_addr = XEXP (x, 0);
2678 mem_addr = XEXP (mem, 0);
2679 if (!((GET_CODE (x_addr) == VALUE
2680 && GET_CODE (mem_addr) != VALUE
2681 && reg_mentioned_p (x_addr, mem_addr))
2682 || (GET_CODE (x_addr) != VALUE
2683 && GET_CODE (mem_addr) == VALUE
2684 && reg_mentioned_p (mem_addr, x_addr))))
2686 x_addr = get_addr (x_addr);
2687 mem_addr = get_addr (mem_addr);
2690 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), GET_MODE (mem_addr)))
2693 x_addr = canon_rtx (x_addr);
2694 mem_addr = canon_rtx (mem_addr);
2696 if (nonoverlapping_memrefs_p (mem, x, true))
2699 /* TBAA not valid for loop_invarint */
2700 return rtx_refs_may_alias_p (x, mem, false);
2704 init_alias_target (void)
2708 if (!arg_base_value)
2709 arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
2711 memset (static_reg_base_value, 0, sizeof static_reg_base_value);
2713 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2714 /* Check whether this register can hold an incoming pointer
2715 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2716 numbers, so translate if necessary due to register windows. */
2717 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2718 && HARD_REGNO_MODE_OK (i, Pmode))
2719 static_reg_base_value[i] = arg_base_value;
2721 static_reg_base_value[STACK_POINTER_REGNUM]
2722 = unique_base_value (UNIQUE_BASE_VALUE_SP);
2723 static_reg_base_value[ARG_POINTER_REGNUM]
2724 = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
2725 static_reg_base_value[FRAME_POINTER_REGNUM]
2726 = unique_base_value (UNIQUE_BASE_VALUE_FP);
2727 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2728 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2729 = unique_base_value (UNIQUE_BASE_VALUE_HFP);
2733 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2734 to be memory reference. */
2735 static bool memory_modified;
2737 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2741 if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
2742 memory_modified = true;
2747 /* Return true when INSN possibly modify memory contents of MEM
2748 (i.e. address can be modified). */
2750 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
2754 memory_modified = false;
2755 note_stores (PATTERN (insn), memory_modified_1, CONST_CAST_RTX(mem));
2756 return memory_modified;
2759 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2763 init_alias_analysis (void)
2765 unsigned int maxreg = max_reg_num ();
2773 timevar_push (TV_ALIAS_ANALYSIS);
2775 reg_known_value = VEC_alloc (rtx, gc, maxreg - FIRST_PSEUDO_REGISTER);
2776 reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
2778 /* If we have memory allocated from the previous run, use it. */
2779 if (old_reg_base_value)
2780 reg_base_value = old_reg_base_value;
2783 VEC_truncate (rtx, reg_base_value, 0);
2785 VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2787 new_reg_base_value = XNEWVEC (rtx, maxreg);
2788 reg_seen = XNEWVEC (char, maxreg);
2790 /* The basic idea is that each pass through this loop will use the
2791 "constant" information from the previous pass to propagate alias
2792 information through another level of assignments.
2794 The propagation is done on the CFG in reverse post-order, to propagate
2795 things forward as far as possible in each iteration.
2797 This could get expensive if the assignment chains are long. Maybe
2798 we should throttle the number of iterations, possibly based on
2799 the optimization level or flag_expensive_optimizations.
2801 We could propagate more information in the first pass by making use
2802 of DF_REG_DEF_COUNT to determine immediately that the alias information
2803 for a pseudo is "constant".
2805 A program with an uninitialized variable can cause an infinite loop
2806 here. Instead of doing a full dataflow analysis to detect such problems
2807 we just cap the number of iterations for the loop.
2809 The state of the arrays for the set chain in question does not matter
2810 since the program has undefined behavior. */
2812 rpo = XNEWVEC (int, n_basic_blocks);
2813 rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
2818 /* Assume nothing will change this iteration of the loop. */
2821 /* We want to assign the same IDs each iteration of this loop, so
2822 start counting from one each iteration of the loop. */
2825 /* We're at the start of the function each iteration through the
2826 loop, so we're copying arguments. */
2827 copying_arguments = true;
2829 /* Wipe the potential alias information clean for this pass. */
2830 memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2832 /* Wipe the reg_seen array clean. */
2833 memset (reg_seen, 0, maxreg);
2835 /* Mark all hard registers which may contain an address.
2836 The stack, frame and argument pointers may contain an address.
2837 An argument register which can hold a Pmode value may contain
2838 an address even if it is not in BASE_REGS.
2840 The address expression is VOIDmode for an argument and
2841 Pmode for other registers. */
2843 memcpy (new_reg_base_value, static_reg_base_value,
2844 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2846 /* Walk the insns adding values to the new_reg_base_value array. */
2847 for (i = 0; i < rpo_cnt; i++)
2849 basic_block bb = BASIC_BLOCK (rpo[i]);
2850 FOR_BB_INSNS (bb, insn)
2852 if (NONDEBUG_INSN_P (insn))
2856 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2857 /* The prologue/epilogue insns are not threaded onto the
2858 insn chain until after reload has completed. Thus,
2859 there is no sense wasting time checking if INSN is in
2860 the prologue/epilogue until after reload has completed. */
2861 if (reload_completed
2862 && prologue_epilogue_contains (insn))
2866 /* If this insn has a noalias note, process it, Otherwise,
2867 scan for sets. A simple set will have no side effects
2868 which could change the base value of any other register. */
2870 if (GET_CODE (PATTERN (insn)) == SET
2871 && REG_NOTES (insn) != 0
2872 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2873 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2875 note_stores (PATTERN (insn), record_set, NULL);
2877 set = single_set (insn);
2880 && REG_P (SET_DEST (set))
2881 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2883 unsigned int regno = REGNO (SET_DEST (set));
2884 rtx src = SET_SRC (set);
2887 note = find_reg_equal_equiv_note (insn);
2888 if (note && REG_NOTE_KIND (note) == REG_EQUAL
2889 && DF_REG_DEF_COUNT (regno) != 1)
2892 if (note != NULL_RTX
2893 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2894 && ! rtx_varies_p (XEXP (note, 0), 1)
2895 && ! reg_overlap_mentioned_p (SET_DEST (set),
2898 set_reg_known_value (regno, XEXP (note, 0));
2899 set_reg_known_equiv_p (regno,
2900 REG_NOTE_KIND (note) == REG_EQUIV);
2902 else if (DF_REG_DEF_COUNT (regno) == 1
2903 && GET_CODE (src) == PLUS
2904 && REG_P (XEXP (src, 0))
2905 && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2906 && CONST_INT_P (XEXP (src, 1)))
2908 t = plus_constant (GET_MODE (src), t,
2909 INTVAL (XEXP (src, 1)));
2910 set_reg_known_value (regno, t);
2911 set_reg_known_equiv_p (regno, false);
2913 else if (DF_REG_DEF_COUNT (regno) == 1
2914 && ! rtx_varies_p (src, 1))
2916 set_reg_known_value (regno, src);
2917 set_reg_known_equiv_p (regno, false);
2921 else if (NOTE_P (insn)
2922 && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2923 copying_arguments = false;
2927 /* Now propagate values from new_reg_base_value to reg_base_value. */
2928 gcc_assert (maxreg == (unsigned int) max_reg_num ());
2930 for (ui = 0; ui < maxreg; ui++)
2932 if (new_reg_base_value[ui]
2933 && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2934 && ! rtx_equal_p (new_reg_base_value[ui],
2935 VEC_index (rtx, reg_base_value, ui)))
2937 VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2942 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2945 /* Fill in the remaining entries. */
2946 FOR_EACH_VEC_ELT (rtx, reg_known_value, i, val)
2948 int regno = i + FIRST_PSEUDO_REGISTER;
2950 set_reg_known_value (regno, regno_reg_rtx[regno]);
2954 free (new_reg_base_value);
2955 new_reg_base_value = 0;
2958 timevar_pop (TV_ALIAS_ANALYSIS);
2961 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
2962 Special API for var-tracking pass purposes. */
2965 vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
2967 VEC_replace (rtx, reg_base_value, REGNO (reg1), REG_BASE_VALUE (reg2));
2971 end_alias_analysis (void)
2973 old_reg_base_value = reg_base_value;
2974 VEC_free (rtx, gc, reg_known_value);
2975 sbitmap_free (reg_known_equiv_p);
2978 #include "gt-alias.h"