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?
70 Can a store to x1 change the value pointed to by with py?
71 Can a store to x1 change the value pointed to by with pz?
73 The answer to these questions can be yes, yes, yes, and maybe.
75 The first two questions can be answered with a simple examination
76 of the type system. If structure X contains a field of type Y then
77 a store through a pointer to an X can overwrite any field that is
78 contained (recursively) in an X (unless we know that px1 != px2).
80 The last two questions can be solved in the same way as the first
81 two questions but this is too conservative. The observation is
82 that in some cases we can know which (if any) fields are addressed
83 and if those addresses are used in bad ways. This analysis may be
84 language specific. In C, arbitrary operations may be applied to
85 pointers. However, there is some indication that this may be too
86 conservative for some C++ types.
88 The pass ipa-type-escape does this analysis for the types whose
89 instances do not escape across the compilation boundary.
91 Historically in GCC, these two problems were combined and a single
92 data structure that was used to represent the solution to these
93 problems. We now have two similar but different data structures,
94 The data structure to solve the last two questions is similar to
95 the first, but does not contain the fields whose address are never
96 taken. For types that do escape the compilation unit, the data
97 structures will have identical information.
100 /* The alias sets assigned to MEMs assist the back-end in determining
101 which MEMs can alias which other MEMs. In general, two MEMs in
102 different alias sets cannot alias each other, with one important
103 exception. Consider something like:
105 struct S { int i; double d; };
107 a store to an `S' can alias something of either type `int' or type
108 `double'. (However, a store to an `int' cannot alias a `double'
109 and vice versa.) We indicate this via a tree structure that looks
117 (The arrows are directed and point downwards.)
118 In this situation we say the alias set for `struct S' is the
119 `superset' and that those for `int' and `double' are `subsets'.
121 To see whether two alias sets can point to the same memory, we must
122 see if either alias set is a subset of the other. We need not trace
123 past immediate descendants, however, since we propagate all
124 grandchildren up one level.
126 Alias set zero is implicitly a superset of all other alias sets.
127 However, this is no actual entry for alias set zero. It is an
128 error to attempt to explicitly construct a subset of zero. */
130 struct GTY(()) alias_set_entry_d
{
131 /* The alias set number, as stored in MEM_ALIAS_SET. */
132 alias_set_type alias_set
;
134 /* Nonzero if would have a child of zero: this effectively makes this
135 alias set the same as alias set zero. */
138 /* The children of the alias set. These are not just the immediate
139 children, but, in fact, all descendants. So, if we have:
141 struct T { struct S s; float f; }
143 continuing our example above, the children here will be all of
144 `int', `double', `float', and `struct S'. */
145 splay_tree
GTY((param1_is (int), param2_is (int))) children
;
147 typedef struct alias_set_entry_d
*alias_set_entry
;
149 static int rtx_equal_for_memref_p (const_rtx
, const_rtx
);
150 static int memrefs_conflict_p (int, rtx
, int, rtx
, HOST_WIDE_INT
);
151 static void record_set (rtx
, const_rtx
, void *);
152 static int base_alias_check (rtx
, rtx
, enum machine_mode
,
154 static rtx
find_base_value (rtx
);
155 static int mems_in_disjoint_alias_sets_p (const_rtx
, const_rtx
);
156 static int insert_subset_children (splay_tree_node
, void*);
157 static alias_set_entry
get_alias_set_entry (alias_set_type
);
158 static bool nonoverlapping_component_refs_p (const_rtx
, const_rtx
);
159 static tree
decl_for_component_ref (tree
);
160 static int write_dependence_p (const_rtx
, const_rtx
, int);
162 static void memory_modified_1 (rtx
, const_rtx
, void *);
164 /* Set up all info needed to perform alias analysis on memory references. */
166 /* Returns the size in bytes of the mode of X. */
167 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
169 /* Cap the number of passes we make over the insns propagating alias
170 information through set chains.
171 ??? 10 is a completely arbitrary choice. This should be based on the
172 maximum loop depth in the CFG, but we do not have this information
173 available (even if current_loops _is_ available). */
174 #define MAX_ALIAS_LOOP_PASSES 10
176 /* reg_base_value[N] gives an address to which register N is related.
177 If all sets after the first add or subtract to the current value
178 or otherwise modify it so it does not point to a different top level
179 object, reg_base_value[N] is equal to the address part of the source
182 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
183 expressions represent three types of base:
185 1. incoming arguments. There is just one ADDRESS to represent all
186 arguments, since we do not know at this level whether accesses
187 based on different arguments can alias. The ADDRESS has id 0.
189 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
190 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
191 Each of these rtxes has a separate ADDRESS associated with it,
192 each with a negative id.
194 GCC is (and is required to be) precise in which register it
195 chooses to access a particular region of stack. We can therefore
196 assume that accesses based on one of these rtxes do not alias
197 accesses based on another of these rtxes.
199 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
200 Each such piece of memory has a separate ADDRESS associated
201 with it, each with an id greater than 0.
203 Accesses based on one ADDRESS do not alias accesses based on other
204 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
205 alias globals either; the ADDRESSes have Pmode to indicate this.
206 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
209 static GTY(()) vec
<rtx
, va_gc
> *reg_base_value
;
210 static rtx
*new_reg_base_value
;
212 /* The single VOIDmode ADDRESS that represents all argument bases.
214 static GTY(()) rtx arg_base_value
;
216 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
217 static int unique_id
;
219 /* We preserve the copy of old array around to avoid amount of garbage
220 produced. About 8% of garbage produced were attributed to this
222 static GTY((deletable
)) vec
<rtx
, va_gc
> *old_reg_base_value
;
224 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
226 #define UNIQUE_BASE_VALUE_SP -1
227 #define UNIQUE_BASE_VALUE_ARGP -2
228 #define UNIQUE_BASE_VALUE_FP -3
229 #define UNIQUE_BASE_VALUE_HFP -4
231 #define static_reg_base_value \
232 (this_target_rtl->x_static_reg_base_value)
234 #define REG_BASE_VALUE(X) \
235 (REGNO (X) < vec_safe_length (reg_base_value) \
236 ? (*reg_base_value)[REGNO (X)] : 0)
238 /* Vector indexed by N giving the initial (unchanging) value known for
239 pseudo-register N. This vector is initialized in init_alias_analysis,
240 and does not change until end_alias_analysis is called. */
241 static GTY(()) vec
<rtx
, va_gc
> *reg_known_value
;
243 /* Vector recording for each reg_known_value whether it is due to a
244 REG_EQUIV note. Future passes (viz., reload) may replace the
245 pseudo with the equivalent expression and so we account for the
246 dependences that would be introduced if that happens.
248 The REG_EQUIV notes created in assign_parms may mention the arg
249 pointer, and there are explicit insns in the RTL that modify the
250 arg pointer. Thus we must ensure that such insns don't get
251 scheduled across each other because that would invalidate the
252 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
253 wrong, but solving the problem in the scheduler will likely give
254 better code, so we do it here. */
255 static sbitmap reg_known_equiv_p
;
257 /* True when scanning insns from the start of the rtl to the
258 NOTE_INSN_FUNCTION_BEG note. */
259 static bool copying_arguments
;
262 /* The splay-tree used to store the various alias set entries. */
263 static GTY (()) vec
<alias_set_entry
, va_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 bases that are neither decls
287 nor indirect references of SSA names. */
289 || (TREE_CODE (base
) == MEM_REF
290 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
291 || (TREE_CODE (base
) == TARGET_MEM_REF
292 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)))
295 /* If this is a reference based on a partitioned decl replace the
296 base with a MEM_REF of the pointer representative we
297 created during stack slot partitioning. */
298 if (TREE_CODE (base
) == VAR_DECL
299 && ! is_global_var (base
)
300 && cfun
->gimple_df
->decls_to_pointers
!= NULL
)
303 namep
= pointer_map_contains (cfun
->gimple_df
->decls_to_pointers
, base
);
305 ref
->base
= build_simple_mem_ref (*(tree
*)namep
);
308 ref
->ref_alias_set
= MEM_ALIAS_SET (mem
);
310 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
311 is conservative, so trust it. */
312 if (!MEM_OFFSET_KNOWN_P (mem
)
313 || !MEM_SIZE_KNOWN_P (mem
))
316 /* If the base decl is a parameter we can have negative MEM_OFFSET in
317 case of promoted subregs on bigendian targets. Trust the MEM_EXPR
319 if (MEM_OFFSET (mem
) < 0
320 && (MEM_SIZE (mem
) + MEM_OFFSET (mem
)) * BITS_PER_UNIT
== ref
->size
)
323 /* Otherwise continue and refine size and offset we got from analyzing
324 MEM_EXPR by using MEM_SIZE and MEM_OFFSET. */
326 ref
->offset
+= MEM_OFFSET (mem
) * BITS_PER_UNIT
;
327 ref
->size
= MEM_SIZE (mem
) * BITS_PER_UNIT
;
329 /* The MEM may extend into adjacent fields, so adjust max_size if
331 if (ref
->max_size
!= -1
332 && ref
->size
> ref
->max_size
)
333 ref
->max_size
= ref
->size
;
335 /* If MEM_OFFSET and MEM_SIZE get us outside of the base object of
336 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
337 if (MEM_EXPR (mem
) != get_spill_slot_decl (false)
339 || (DECL_P (ref
->base
)
340 && (!host_integerp (DECL_SIZE (ref
->base
), 1)
341 || (TREE_INT_CST_LOW (DECL_SIZE ((ref
->base
)))
342 < (unsigned HOST_WIDE_INT
)(ref
->offset
+ ref
->size
))))))
348 /* Query the alias-oracle on whether the two memory rtx X and MEM may
349 alias. If TBAA_P is set also apply TBAA. Returns true if the
350 two rtxen may alias, false otherwise. */
353 rtx_refs_may_alias_p (const_rtx x
, const_rtx mem
, bool tbaa_p
)
357 if (!ao_ref_from_mem (&ref1
, x
)
358 || !ao_ref_from_mem (&ref2
, mem
))
361 return refs_may_alias_p_1 (&ref1
, &ref2
,
363 && MEM_ALIAS_SET (x
) != 0
364 && MEM_ALIAS_SET (mem
) != 0);
367 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
368 such an entry, or NULL otherwise. */
370 static inline alias_set_entry
371 get_alias_set_entry (alias_set_type alias_set
)
373 return (*alias_sets
)[alias_set
];
376 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
377 the two MEMs cannot alias each other. */
380 mems_in_disjoint_alias_sets_p (const_rtx mem1
, const_rtx mem2
)
382 /* Perform a basic sanity check. Namely, that there are no alias sets
383 if we're not using strict aliasing. This helps to catch bugs
384 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
385 where a MEM is allocated in some way other than by the use of
386 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
387 use alias sets to indicate that spilled registers cannot alias each
388 other, we might need to remove this check. */
389 gcc_assert (flag_strict_aliasing
390 || (!MEM_ALIAS_SET (mem1
) && !MEM_ALIAS_SET (mem2
)));
392 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
395 /* Insert the NODE into the splay tree given by DATA. Used by
396 record_alias_subset via splay_tree_foreach. */
399 insert_subset_children (splay_tree_node node
, void *data
)
401 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
406 /* Return true if the first alias set is a subset of the second. */
409 alias_set_subset_of (alias_set_type set1
, alias_set_type set2
)
413 /* Everything is a subset of the "aliases everything" set. */
417 /* Otherwise, check if set1 is a subset of set2. */
418 ase
= get_alias_set_entry (set2
);
420 && (ase
->has_zero_child
421 || splay_tree_lookup (ase
->children
,
422 (splay_tree_key
) set1
)))
427 /* Return 1 if the two specified alias sets may conflict. */
430 alias_sets_conflict_p (alias_set_type set1
, alias_set_type set2
)
435 if (alias_sets_must_conflict_p (set1
, set2
))
438 /* See if the first alias set is a subset of the second. */
439 ase
= get_alias_set_entry (set1
);
441 && (ase
->has_zero_child
442 || splay_tree_lookup (ase
->children
,
443 (splay_tree_key
) set2
)))
446 /* Now do the same, but with the alias sets reversed. */
447 ase
= get_alias_set_entry (set2
);
449 && (ase
->has_zero_child
450 || splay_tree_lookup (ase
->children
,
451 (splay_tree_key
) set1
)))
454 /* The two alias sets are distinct and neither one is the
455 child of the other. Therefore, they cannot conflict. */
459 /* Return 1 if the two specified alias sets will always conflict. */
462 alias_sets_must_conflict_p (alias_set_type set1
, alias_set_type set2
)
464 if (set1
== 0 || set2
== 0 || set1
== set2
)
470 /* Return 1 if any MEM object of type T1 will always conflict (using the
471 dependency routines in this file) with any MEM object of type T2.
472 This is used when allocating temporary storage. If T1 and/or T2 are
473 NULL_TREE, it means we know nothing about the storage. */
476 objects_must_conflict_p (tree t1
, tree t2
)
478 alias_set_type set1
, set2
;
480 /* If neither has a type specified, we don't know if they'll conflict
481 because we may be using them to store objects of various types, for
482 example the argument and local variables areas of inlined functions. */
483 if (t1
== 0 && t2
== 0)
486 /* If they are the same type, they must conflict. */
488 /* Likewise if both are volatile. */
489 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
492 set1
= t1
? get_alias_set (t1
) : 0;
493 set2
= t2
? get_alias_set (t2
) : 0;
495 /* We can't use alias_sets_conflict_p because we must make sure
496 that every subtype of t1 will conflict with every subtype of
497 t2 for which a pair of subobjects of these respective subtypes
498 overlaps on the stack. */
499 return alias_sets_must_conflict_p (set1
, set2
);
502 /* Return true if all nested component references handled by
503 get_inner_reference in T are such that we should use the alias set
504 provided by the object at the heart of T.
506 This is true for non-addressable components (which don't have their
507 own alias set), as well as components of objects in alias set zero.
508 This later point is a special case wherein we wish to override the
509 alias set used by the component, but we don't have per-FIELD_DECL
510 assignable alias sets. */
513 component_uses_parent_alias_set (const_tree t
)
517 /* If we're at the end, it vacuously uses its own alias set. */
518 if (!handled_component_p (t
))
521 switch (TREE_CODE (t
))
524 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
529 case ARRAY_RANGE_REF
:
530 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
539 /* Bitfields and casts are never addressable. */
543 t
= TREE_OPERAND (t
, 0);
544 if (get_alias_set (TREE_TYPE (t
)) == 0)
549 /* Return the alias set for the memory pointed to by T, which may be
550 either a type or an expression. Return -1 if there is nothing
551 special about dereferencing T. */
553 static alias_set_type
554 get_deref_alias_set_1 (tree t
)
556 /* If we're not doing any alias analysis, just assume everything
557 aliases everything else. */
558 if (!flag_strict_aliasing
)
561 /* All we care about is the type. */
565 /* If we have an INDIRECT_REF via a void pointer, we don't
566 know anything about what that might alias. Likewise if the
567 pointer is marked that way. */
568 if (TREE_CODE (TREE_TYPE (t
)) == VOID_TYPE
569 || TYPE_REF_CAN_ALIAS_ALL (t
))
575 /* Return the alias set for the memory pointed to by T, which may be
576 either a type or an expression. */
579 get_deref_alias_set (tree t
)
581 alias_set_type set
= get_deref_alias_set_1 (t
);
583 /* Fall back to the alias-set of the pointed-to type. */
588 set
= get_alias_set (TREE_TYPE (t
));
594 /* Return the alias set for T, which may be either a type or an
595 expression. Call language-specific routine for help, if needed. */
598 get_alias_set (tree t
)
602 /* If we're not doing any alias analysis, just assume everything
603 aliases everything else. Also return 0 if this or its type is
605 if (! flag_strict_aliasing
|| t
== error_mark_node
607 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
610 /* We can be passed either an expression or a type. This and the
611 language-specific routine may make mutually-recursive calls to each other
612 to figure out what to do. At each juncture, we see if this is a tree
613 that the language may need to handle specially. First handle things that
619 /* Give the language a chance to do something with this tree
620 before we look at it. */
622 set
= lang_hooks
.get_alias_set (t
);
626 /* Get the base object of the reference. */
628 while (handled_component_p (inner
))
630 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
631 the type of any component references that wrap it to
632 determine the alias-set. */
633 if (TREE_CODE (inner
) == VIEW_CONVERT_EXPR
)
634 t
= TREE_OPERAND (inner
, 0);
635 inner
= TREE_OPERAND (inner
, 0);
638 /* Handle pointer dereferences here, they can override the
640 if (INDIRECT_REF_P (inner
))
642 set
= get_deref_alias_set_1 (TREE_OPERAND (inner
, 0));
646 else if (TREE_CODE (inner
) == TARGET_MEM_REF
)
647 return get_deref_alias_set (TMR_OFFSET (inner
));
648 else if (TREE_CODE (inner
) == MEM_REF
)
650 set
= get_deref_alias_set_1 (TREE_OPERAND (inner
, 1));
655 /* If the innermost reference is a MEM_REF that has a
656 conversion embedded treat it like a VIEW_CONVERT_EXPR above,
657 using the memory access type for determining the alias-set. */
658 if (TREE_CODE (inner
) == MEM_REF
659 && TYPE_MAIN_VARIANT (TREE_TYPE (inner
))
661 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner
, 1)))))
662 return get_deref_alias_set (TREE_OPERAND (inner
, 1));
664 /* Otherwise, pick up the outermost object that we could have a pointer
665 to, processing conversions as above. */
666 while (component_uses_parent_alias_set (t
))
668 t
= TREE_OPERAND (t
, 0);
672 /* If we've already determined the alias set for a decl, just return
673 it. This is necessary for C++ anonymous unions, whose component
674 variables don't look like union members (boo!). */
675 if (TREE_CODE (t
) == VAR_DECL
676 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
677 return MEM_ALIAS_SET (DECL_RTL (t
));
679 /* Now all we care about is the type. */
683 /* Variant qualifiers don't affect the alias set, so get the main
685 t
= TYPE_MAIN_VARIANT (t
);
687 /* Always use the canonical type as well. If this is a type that
688 requires structural comparisons to identify compatible types
689 use alias set zero. */
690 if (TYPE_STRUCTURAL_EQUALITY_P (t
))
692 /* Allow the language to specify another alias set for this
694 set
= lang_hooks
.get_alias_set (t
);
700 t
= TYPE_CANONICAL (t
);
702 /* The canonical type should not require structural equality checks. */
703 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t
));
705 /* If this is a type with a known alias set, return it. */
706 if (TYPE_ALIAS_SET_KNOWN_P (t
))
707 return TYPE_ALIAS_SET (t
);
709 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
710 if (!COMPLETE_TYPE_P (t
))
712 /* For arrays with unknown size the conservative answer is the
713 alias set of the element type. */
714 if (TREE_CODE (t
) == ARRAY_TYPE
)
715 return get_alias_set (TREE_TYPE (t
));
717 /* But return zero as a conservative answer for incomplete types. */
721 /* See if the language has special handling for this type. */
722 set
= lang_hooks
.get_alias_set (t
);
726 /* There are no objects of FUNCTION_TYPE, so there's no point in
727 using up an alias set for them. (There are, of course, pointers
728 and references to functions, but that's different.) */
729 else if (TREE_CODE (t
) == FUNCTION_TYPE
|| TREE_CODE (t
) == METHOD_TYPE
)
732 /* Unless the language specifies otherwise, let vector types alias
733 their components. This avoids some nasty type punning issues in
734 normal usage. And indeed lets vectors be treated more like an
736 else if (TREE_CODE (t
) == VECTOR_TYPE
)
737 set
= get_alias_set (TREE_TYPE (t
));
739 /* Unless the language specifies otherwise, treat array types the
740 same as their components. This avoids the asymmetry we get
741 through recording the components. Consider accessing a
742 character(kind=1) through a reference to a character(kind=1)[1:1].
743 Or consider if we want to assign integer(kind=4)[0:D.1387] and
744 integer(kind=4)[4] the same alias set or not.
745 Just be pragmatic here and make sure the array and its element
746 type get the same alias set assigned. */
747 else if (TREE_CODE (t
) == ARRAY_TYPE
&& !TYPE_NONALIASED_COMPONENT (t
))
748 set
= get_alias_set (TREE_TYPE (t
));
750 /* From the former common C and C++ langhook implementation:
752 Unfortunately, there is no canonical form of a pointer type.
753 In particular, if we have `typedef int I', then `int *', and
754 `I *' are different types. So, we have to pick a canonical
755 representative. We do this below.
757 Technically, this approach is actually more conservative that
758 it needs to be. In particular, `const int *' and `int *'
759 should be in different alias sets, according to the C and C++
760 standard, since their types are not the same, and so,
761 technically, an `int **' and `const int **' cannot point at
764 But, the standard is wrong. In particular, this code is
769 const int* const* cipp = ipp;
770 And, it doesn't make sense for that to be legal unless you
771 can dereference IPP and CIPP. So, we ignore cv-qualifiers on
772 the pointed-to types. This issue has been reported to the
775 In addition to the above canonicalization issue, with LTO
776 we should also canonicalize `T (*)[]' to `T *' avoiding
777 alias issues with pointer-to element types and pointer-to
780 Likewise we need to deal with the situation of incomplete
781 pointed-to types and make `*(struct X **)&a' and
782 `*(struct X {} **)&a' alias. Otherwise we will have to
783 guarantee that all pointer-to incomplete type variants
784 will be replaced by pointer-to complete type variants if
787 With LTO the convenient situation of using `void *' to
788 access and store any pointer type will also become
789 more apparent (and `void *' is just another pointer-to
790 incomplete type). Assigning alias-set zero to `void *'
791 and all pointer-to incomplete types is a not appealing
792 solution. Assigning an effective alias-set zero only
793 affecting pointers might be - by recording proper subset
794 relationships of all pointer alias-sets.
796 Pointer-to function types are another grey area which
797 needs caution. Globbing them all into one alias-set
798 or the above effective zero set would work.
800 For now just assign the same alias-set to all pointers.
801 That's simple and avoids all the above problems. */
802 else if (POINTER_TYPE_P (t
)
803 && t
!= ptr_type_node
)
804 set
= get_alias_set (ptr_type_node
);
806 /* Otherwise make a new alias set for this type. */
809 /* Each canonical type gets its own alias set, so canonical types
810 shouldn't form a tree. It doesn't really matter for types
811 we handle specially above, so only check it where it possibly
812 would result in a bogus alias set. */
813 gcc_checking_assert (TYPE_CANONICAL (t
) == t
);
815 set
= new_alias_set ();
818 TYPE_ALIAS_SET (t
) = set
;
820 /* If this is an aggregate type or a complex type, we must record any
821 component aliasing information. */
822 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
823 record_component_aliases (t
);
828 /* Return a brand-new alias set. */
833 if (flag_strict_aliasing
)
836 vec_safe_push (alias_sets
, (alias_set_entry
) 0);
837 vec_safe_push (alias_sets
, (alias_set_entry
) 0);
838 return alias_sets
->length () - 1;
844 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
845 not everything that aliases SUPERSET also aliases SUBSET. For example,
846 in C, a store to an `int' can alias a load of a structure containing an
847 `int', and vice versa. But it can't alias a load of a 'double' member
848 of the same structure. Here, the structure would be the SUPERSET and
849 `int' the SUBSET. This relationship is also described in the comment at
850 the beginning of this file.
852 This function should be called only once per SUPERSET/SUBSET pair.
854 It is illegal for SUPERSET to be zero; everything is implicitly a
855 subset of alias set zero. */
858 record_alias_subset (alias_set_type superset
, alias_set_type subset
)
860 alias_set_entry superset_entry
;
861 alias_set_entry subset_entry
;
863 /* It is possible in complex type situations for both sets to be the same,
864 in which case we can ignore this operation. */
865 if (superset
== subset
)
868 gcc_assert (superset
);
870 superset_entry
= get_alias_set_entry (superset
);
871 if (superset_entry
== 0)
873 /* Create an entry for the SUPERSET, so that we have a place to
874 attach the SUBSET. */
875 superset_entry
= ggc_alloc_cleared_alias_set_entry_d ();
876 superset_entry
->alias_set
= superset
;
877 superset_entry
->children
878 = splay_tree_new_ggc (splay_tree_compare_ints
,
879 ggc_alloc_splay_tree_scalar_scalar_splay_tree_s
,
880 ggc_alloc_splay_tree_scalar_scalar_splay_tree_node_s
);
881 superset_entry
->has_zero_child
= 0;
882 (*alias_sets
)[superset
] = superset_entry
;
886 superset_entry
->has_zero_child
= 1;
889 subset_entry
= get_alias_set_entry (subset
);
890 /* If there is an entry for the subset, enter all of its children
891 (if they are not already present) as children of the SUPERSET. */
894 if (subset_entry
->has_zero_child
)
895 superset_entry
->has_zero_child
= 1;
897 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
898 superset_entry
->children
);
901 /* Enter the SUBSET itself as a child of the SUPERSET. */
902 splay_tree_insert (superset_entry
->children
,
903 (splay_tree_key
) subset
, 0);
907 /* Record that component types of TYPE, if any, are part of that type for
908 aliasing purposes. For record types, we only record component types
909 for fields that are not marked non-addressable. For array types, we
910 only record the component type if it is not marked non-aliased. */
913 record_component_aliases (tree type
)
915 alias_set_type superset
= get_alias_set (type
);
921 switch (TREE_CODE (type
))
925 case QUAL_UNION_TYPE
:
926 /* Recursively record aliases for the base classes, if there are any. */
927 if (TYPE_BINFO (type
))
930 tree binfo
, base_binfo
;
932 for (binfo
= TYPE_BINFO (type
), i
= 0;
933 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
934 record_alias_subset (superset
,
935 get_alias_set (BINFO_TYPE (base_binfo
)));
937 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= DECL_CHAIN (field
))
938 if (TREE_CODE (field
) == FIELD_DECL
&& !DECL_NONADDRESSABLE_P (field
))
939 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
943 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
946 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
954 /* Allocate an alias set for use in storing and reading from the varargs
957 static GTY(()) alias_set_type varargs_set
= -1;
960 get_varargs_alias_set (void)
963 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
964 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
965 consistently use the varargs alias set for loads from the varargs
966 area. So don't use it anywhere. */
969 if (varargs_set
== -1)
970 varargs_set
= new_alias_set ();
976 /* Likewise, but used for the fixed portions of the frame, e.g., register
979 static GTY(()) alias_set_type frame_set
= -1;
982 get_frame_alias_set (void)
985 frame_set
= new_alias_set ();
990 /* Create a new, unique base with id ID. */
993 unique_base_value (HOST_WIDE_INT id
)
995 return gen_rtx_ADDRESS (Pmode
, id
);
998 /* Return true if accesses based on any other base value cannot alias
1002 unique_base_value_p (rtx x
)
1004 return GET_CODE (x
) == ADDRESS
&& GET_MODE (x
) == Pmode
;
1007 /* Return true if X is known to be a base value. */
1010 known_base_value_p (rtx x
)
1012 switch (GET_CODE (x
))
1019 /* Arguments may or may not be bases; we don't know for sure. */
1020 return GET_MODE (x
) != VOIDmode
;
1027 /* Inside SRC, the source of a SET, find a base address. */
1030 find_base_value (rtx src
)
1034 #if defined (FIND_BASE_TERM)
1035 /* Try machine-dependent ways to find the base term. */
1036 src
= FIND_BASE_TERM (src
);
1039 switch (GET_CODE (src
))
1046 regno
= REGNO (src
);
1047 /* At the start of a function, argument registers have known base
1048 values which may be lost later. Returning an ADDRESS
1049 expression here allows optimization based on argument values
1050 even when the argument registers are used for other purposes. */
1051 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
1052 return new_reg_base_value
[regno
];
1054 /* If a pseudo has a known base value, return it. Do not do this
1055 for non-fixed hard regs since it can result in a circular
1056 dependency chain for registers which have values at function entry.
1058 The test above is not sufficient because the scheduler may move
1059 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1060 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
1061 && regno
< vec_safe_length (reg_base_value
))
1063 /* If we're inside init_alias_analysis, use new_reg_base_value
1064 to reduce the number of relaxation iterations. */
1065 if (new_reg_base_value
&& new_reg_base_value
[regno
]
1066 && DF_REG_DEF_COUNT (regno
) == 1)
1067 return new_reg_base_value
[regno
];
1069 if ((*reg_base_value
)[regno
])
1070 return (*reg_base_value
)[regno
];
1076 /* Check for an argument passed in memory. Only record in the
1077 copying-arguments block; it is too hard to track changes
1079 if (copying_arguments
1080 && (XEXP (src
, 0) == arg_pointer_rtx
1081 || (GET_CODE (XEXP (src
, 0)) == PLUS
1082 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
1083 return arg_base_value
;
1087 src
= XEXP (src
, 0);
1088 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
1091 /* ... fall through ... */
1096 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
1098 /* If either operand is a REG that is a known pointer, then it
1100 if (REG_P (src_0
) && REG_POINTER (src_0
))
1101 return find_base_value (src_0
);
1102 if (REG_P (src_1
) && REG_POINTER (src_1
))
1103 return find_base_value (src_1
);
1105 /* If either operand is a REG, then see if we already have
1106 a known value for it. */
1109 temp
= find_base_value (src_0
);
1116 temp
= find_base_value (src_1
);
1121 /* If either base is named object or a special address
1122 (like an argument or stack reference), then use it for the
1124 if (src_0
!= 0 && known_base_value_p (src_0
))
1127 if (src_1
!= 0 && known_base_value_p (src_1
))
1130 /* Guess which operand is the base address:
1131 If either operand is a symbol, then it is the base. If
1132 either operand is a CONST_INT, then the other is the base. */
1133 if (CONST_INT_P (src_1
) || CONSTANT_P (src_0
))
1134 return find_base_value (src_0
);
1135 else if (CONST_INT_P (src_0
) || CONSTANT_P (src_1
))
1136 return find_base_value (src_1
);
1142 /* The standard form is (lo_sum reg sym) so look only at the
1144 return find_base_value (XEXP (src
, 1));
1147 /* If the second operand is constant set the base
1148 address to the first operand. */
1149 if (CONST_INT_P (XEXP (src
, 1)) && INTVAL (XEXP (src
, 1)) != 0)
1150 return find_base_value (XEXP (src
, 0));
1154 /* As we do not know which address space the pointer is referring to, we can
1155 handle this only if the target does not support different pointer or
1156 address modes depending on the address space. */
1157 if (!target_default_pointer_address_modes_p ())
1159 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
1169 return find_base_value (XEXP (src
, 0));
1172 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
1173 /* As we do not know which address space the pointer is referring to, we can
1174 handle this only if the target does not support different pointer or
1175 address modes depending on the address space. */
1176 if (!target_default_pointer_address_modes_p ())
1180 rtx temp
= find_base_value (XEXP (src
, 0));
1182 if (temp
!= 0 && CONSTANT_P (temp
))
1183 temp
= convert_memory_address (Pmode
, temp
);
1195 /* Called from init_alias_analysis indirectly through note_stores,
1196 or directly if DEST is a register with a REG_NOALIAS note attached.
1197 SET is null in the latter case. */
1199 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1200 register N has been set in this function. */
1201 static sbitmap reg_seen
;
1204 record_set (rtx dest
, const_rtx set
, void *data ATTRIBUTE_UNUSED
)
1213 regno
= REGNO (dest
);
1215 gcc_checking_assert (regno
< reg_base_value
->length ());
1217 /* If this spans multiple hard registers, then we must indicate that every
1218 register has an unusable value. */
1219 if (regno
< FIRST_PSEUDO_REGISTER
)
1220 n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
1227 bitmap_set_bit (reg_seen
, regno
+ n
);
1228 new_reg_base_value
[regno
+ n
] = 0;
1235 /* A CLOBBER wipes out any old value but does not prevent a previously
1236 unset register from acquiring a base address (i.e. reg_seen is not
1238 if (GET_CODE (set
) == CLOBBER
)
1240 new_reg_base_value
[regno
] = 0;
1243 src
= SET_SRC (set
);
1247 /* There's a REG_NOALIAS note against DEST. */
1248 if (bitmap_bit_p (reg_seen
, regno
))
1250 new_reg_base_value
[regno
] = 0;
1253 bitmap_set_bit (reg_seen
, regno
);
1254 new_reg_base_value
[regno
] = unique_base_value (unique_id
++);
1258 /* If this is not the first set of REGNO, see whether the new value
1259 is related to the old one. There are two cases of interest:
1261 (1) The register might be assigned an entirely new value
1262 that has the same base term as the original set.
1264 (2) The set might be a simple self-modification that
1265 cannot change REGNO's base value.
1267 If neither case holds, reject the original base value as invalid.
1268 Note that the following situation is not detected:
1270 extern int x, y; int *p = &x; p += (&y-&x);
1272 ANSI C does not allow computing the difference of addresses
1273 of distinct top level objects. */
1274 if (new_reg_base_value
[regno
] != 0
1275 && find_base_value (src
) != new_reg_base_value
[regno
])
1276 switch (GET_CODE (src
))
1280 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1281 new_reg_base_value
[regno
] = 0;
1284 /* If the value we add in the PLUS is also a valid base value,
1285 this might be the actual base value, and the original value
1288 rtx other
= NULL_RTX
;
1290 if (XEXP (src
, 0) == dest
)
1291 other
= XEXP (src
, 1);
1292 else if (XEXP (src
, 1) == dest
)
1293 other
= XEXP (src
, 0);
1295 if (! other
|| find_base_value (other
))
1296 new_reg_base_value
[regno
] = 0;
1300 if (XEXP (src
, 0) != dest
|| !CONST_INT_P (XEXP (src
, 1)))
1301 new_reg_base_value
[regno
] = 0;
1304 new_reg_base_value
[regno
] = 0;
1307 /* If this is the first set of a register, record the value. */
1308 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1309 && ! bitmap_bit_p (reg_seen
, regno
) && new_reg_base_value
[regno
] == 0)
1310 new_reg_base_value
[regno
] = find_base_value (src
);
1312 bitmap_set_bit (reg_seen
, regno
);
1315 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1316 using hard registers with non-null REG_BASE_VALUE for renaming. */
1318 get_reg_base_value (unsigned int regno
)
1320 return (*reg_base_value
)[regno
];
1323 /* If a value is known for REGNO, return it. */
1326 get_reg_known_value (unsigned int regno
)
1328 if (regno
>= FIRST_PSEUDO_REGISTER
)
1330 regno
-= FIRST_PSEUDO_REGISTER
;
1331 if (regno
< vec_safe_length (reg_known_value
))
1332 return (*reg_known_value
)[regno
];
1340 set_reg_known_value (unsigned int regno
, rtx val
)
1342 if (regno
>= FIRST_PSEUDO_REGISTER
)
1344 regno
-= FIRST_PSEUDO_REGISTER
;
1345 if (regno
< vec_safe_length (reg_known_value
))
1346 (*reg_known_value
)[regno
] = val
;
1350 /* Similarly for reg_known_equiv_p. */
1353 get_reg_known_equiv_p (unsigned int regno
)
1355 if (regno
>= FIRST_PSEUDO_REGISTER
)
1357 regno
-= FIRST_PSEUDO_REGISTER
;
1358 if (regno
< vec_safe_length (reg_known_value
))
1359 return bitmap_bit_p (reg_known_equiv_p
, regno
);
1365 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1367 if (regno
>= FIRST_PSEUDO_REGISTER
)
1369 regno
-= FIRST_PSEUDO_REGISTER
;
1370 if (regno
< vec_safe_length (reg_known_value
))
1373 bitmap_set_bit (reg_known_equiv_p
, regno
);
1375 bitmap_clear_bit (reg_known_equiv_p
, regno
);
1381 /* Returns a canonical version of X, from the point of view alias
1382 analysis. (For example, if X is a MEM whose address is a register,
1383 and the register has a known value (say a SYMBOL_REF), then a MEM
1384 whose address is the SYMBOL_REF is returned.) */
1389 /* Recursively look for equivalences. */
1390 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1392 rtx t
= get_reg_known_value (REGNO (x
));
1396 return canon_rtx (t
);
1399 if (GET_CODE (x
) == PLUS
)
1401 rtx x0
= canon_rtx (XEXP (x
, 0));
1402 rtx x1
= canon_rtx (XEXP (x
, 1));
1404 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1406 if (CONST_INT_P (x0
))
1407 return plus_constant (GET_MODE (x
), x1
, INTVAL (x0
));
1408 else if (CONST_INT_P (x1
))
1409 return plus_constant (GET_MODE (x
), x0
, INTVAL (x1
));
1410 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1414 /* This gives us much better alias analysis when called from
1415 the loop optimizer. Note we want to leave the original
1416 MEM alone, but need to return the canonicalized MEM with
1417 all the flags with their original values. */
1419 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1424 /* Return 1 if X and Y are identical-looking rtx's.
1425 Expect that X and Y has been already canonicalized.
1427 We use the data in reg_known_value above to see if two registers with
1428 different numbers are, in fact, equivalent. */
1431 rtx_equal_for_memref_p (const_rtx x
, const_rtx y
)
1438 if (x
== 0 && y
== 0)
1440 if (x
== 0 || y
== 0)
1446 code
= GET_CODE (x
);
1447 /* Rtx's of different codes cannot be equal. */
1448 if (code
!= GET_CODE (y
))
1451 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1452 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1454 if (GET_MODE (x
) != GET_MODE (y
))
1457 /* Some RTL can be compared without a recursive examination. */
1461 return REGNO (x
) == REGNO (y
);
1464 return XEXP (x
, 0) == XEXP (y
, 0);
1467 return XSTR (x
, 0) == XSTR (y
, 0);
1471 /* There's no need to compare the contents of CONST_DOUBLEs or
1472 CONST_INTs because pointer equality is a good enough
1473 comparison for these nodes. */
1480 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1482 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1483 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1484 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1485 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1486 /* For commutative operations, the RTX match if the operand match in any
1487 order. Also handle the simple binary and unary cases without a loop. */
1488 if (COMMUTATIVE_P (x
))
1490 rtx xop0
= canon_rtx (XEXP (x
, 0));
1491 rtx yop0
= canon_rtx (XEXP (y
, 0));
1492 rtx yop1
= canon_rtx (XEXP (y
, 1));
1494 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1495 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1496 || (rtx_equal_for_memref_p (xop0
, yop1
)
1497 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1499 else if (NON_COMMUTATIVE_P (x
))
1501 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1502 canon_rtx (XEXP (y
, 0)))
1503 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1504 canon_rtx (XEXP (y
, 1))));
1506 else if (UNARY_P (x
))
1507 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1508 canon_rtx (XEXP (y
, 0)));
1510 /* Compare the elements. If any pair of corresponding elements
1511 fail to match, return 0 for the whole things.
1513 Limit cases to types which actually appear in addresses. */
1515 fmt
= GET_RTX_FORMAT (code
);
1516 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1521 if (XINT (x
, i
) != XINT (y
, i
))
1526 /* Two vectors must have the same length. */
1527 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1530 /* And the corresponding elements must match. */
1531 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1532 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1533 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1538 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1539 canon_rtx (XEXP (y
, i
))) == 0)
1543 /* This can happen for asm operands. */
1545 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1549 /* This can happen for an asm which clobbers memory. */
1553 /* It is believed that rtx's at this level will never
1554 contain anything but integers and other rtx's,
1555 except for within LABEL_REFs and SYMBOL_REFs. */
1564 find_base_term (rtx x
)
1567 struct elt_loc_list
*l
, *f
;
1570 #if defined (FIND_BASE_TERM)
1571 /* Try machine-dependent ways to find the base term. */
1572 x
= FIND_BASE_TERM (x
);
1575 switch (GET_CODE (x
))
1578 return REG_BASE_VALUE (x
);
1581 /* As we do not know which address space the pointer is referring to, we can
1582 handle this only if the target does not support different pointer or
1583 address modes depending on the address space. */
1584 if (!target_default_pointer_address_modes_p ())
1586 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1596 return find_base_term (XEXP (x
, 0));
1599 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1600 /* As we do not know which address space the pointer is referring to, we can
1601 handle this only if the target does not support different pointer or
1602 address modes depending on the address space. */
1603 if (!target_default_pointer_address_modes_p ())
1607 rtx temp
= find_base_term (XEXP (x
, 0));
1609 if (temp
!= 0 && CONSTANT_P (temp
))
1610 temp
= convert_memory_address (Pmode
, temp
);
1616 val
= CSELIB_VAL_PTR (x
);
1622 if (cselib_sp_based_value_p (val
))
1623 return static_reg_base_value
[STACK_POINTER_REGNUM
];
1626 /* Temporarily reset val->locs to avoid infinite recursion. */
1629 for (l
= f
; l
; l
= l
->next
)
1630 if (GET_CODE (l
->loc
) == VALUE
1631 && CSELIB_VAL_PTR (l
->loc
)->locs
1632 && !CSELIB_VAL_PTR (l
->loc
)->locs
->next
1633 && CSELIB_VAL_PTR (l
->loc
)->locs
->loc
== x
)
1635 else if ((ret
= find_base_term (l
->loc
)) != 0)
1642 /* The standard form is (lo_sum reg sym) so look only at the
1644 return find_base_term (XEXP (x
, 1));
1648 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1654 rtx tmp1
= XEXP (x
, 0);
1655 rtx tmp2
= XEXP (x
, 1);
1657 /* This is a little bit tricky since we have to determine which of
1658 the two operands represents the real base address. Otherwise this
1659 routine may return the index register instead of the base register.
1661 That may cause us to believe no aliasing was possible, when in
1662 fact aliasing is possible.
1664 We use a few simple tests to guess the base register. Additional
1665 tests can certainly be added. For example, if one of the operands
1666 is a shift or multiply, then it must be the index register and the
1667 other operand is the base register. */
1669 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1670 return find_base_term (tmp2
);
1672 /* If either operand is known to be a pointer, then use it
1673 to determine the base term. */
1674 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1676 rtx base
= find_base_term (tmp1
);
1681 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1683 rtx base
= find_base_term (tmp2
);
1688 /* Neither operand was known to be a pointer. Go ahead and find the
1689 base term for both operands. */
1690 tmp1
= find_base_term (tmp1
);
1691 tmp2
= find_base_term (tmp2
);
1693 /* If either base term is named object or a special address
1694 (like an argument or stack reference), then use it for the
1696 if (tmp1
!= 0 && known_base_value_p (tmp1
))
1699 if (tmp2
!= 0 && known_base_value_p (tmp2
))
1702 /* We could not determine which of the two operands was the
1703 base register and which was the index. So we can determine
1704 nothing from the base alias check. */
1709 if (CONST_INT_P (XEXP (x
, 1)) && INTVAL (XEXP (x
, 1)) != 0)
1710 return find_base_term (XEXP (x
, 0));
1722 /* Return true if accesses to address X may alias accesses based
1723 on the stack pointer. */
1726 may_be_sp_based_p (rtx x
)
1728 rtx base
= find_base_term (x
);
1729 return !base
|| base
== static_reg_base_value
[STACK_POINTER_REGNUM
];
1732 /* Return 0 if the addresses X and Y are known to point to different
1733 objects, 1 if they might be pointers to the same object. */
1736 base_alias_check (rtx x
, rtx y
, enum machine_mode x_mode
,
1737 enum machine_mode y_mode
)
1739 rtx x_base
= find_base_term (x
);
1740 rtx y_base
= find_base_term (y
);
1742 /* If the address itself has no known base see if a known equivalent
1743 value has one. If either address still has no known base, nothing
1744 is known about aliasing. */
1749 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1752 x_base
= find_base_term (x_c
);
1760 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1763 y_base
= find_base_term (y_c
);
1768 /* If the base addresses are equal nothing is known about aliasing. */
1769 if (rtx_equal_p (x_base
, y_base
))
1772 /* The base addresses are different expressions. If they are not accessed
1773 via AND, there is no conflict. We can bring knowledge of object
1774 alignment into play here. For example, on alpha, "char a, b;" can
1775 alias one another, though "char a; long b;" cannot. AND addesses may
1776 implicitly alias surrounding objects; i.e. unaligned access in DImode
1777 via AND address can alias all surrounding object types except those
1778 with aligment 8 or higher. */
1779 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1781 if (GET_CODE (x
) == AND
1782 && (!CONST_INT_P (XEXP (x
, 1))
1783 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1785 if (GET_CODE (y
) == AND
1786 && (!CONST_INT_P (XEXP (y
, 1))
1787 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1790 /* Differing symbols not accessed via AND never alias. */
1791 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1794 if (unique_base_value_p (x_base
) || unique_base_value_p (y_base
))
1800 /* Callback for for_each_rtx, that returns 1 upon encountering a VALUE
1801 whose UID is greater than the int uid that D points to. */
1804 refs_newer_value_cb (rtx
*x
, void *d
)
1806 if (GET_CODE (*x
) == VALUE
&& CSELIB_VAL_PTR (*x
)->uid
> *(int *)d
)
1812 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
1816 refs_newer_value_p (rtx expr
, rtx v
)
1818 int minuid
= CSELIB_VAL_PTR (v
)->uid
;
1820 return for_each_rtx (&expr
, refs_newer_value_cb
, &minuid
);
1823 /* Convert the address X into something we can use. This is done by returning
1824 it unchanged unless it is a value; in the latter case we call cselib to get
1825 a more useful rtx. */
1831 struct elt_loc_list
*l
;
1833 if (GET_CODE (x
) != VALUE
)
1835 v
= CSELIB_VAL_PTR (x
);
1838 bool have_equivs
= cselib_have_permanent_equivalences ();
1840 v
= canonical_cselib_val (v
);
1841 for (l
= v
->locs
; l
; l
= l
->next
)
1842 if (CONSTANT_P (l
->loc
))
1844 for (l
= v
->locs
; l
; l
= l
->next
)
1845 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
)
1846 /* Avoid infinite recursion when potentially dealing with
1847 var-tracking artificial equivalences, by skipping the
1848 equivalences themselves, and not choosing expressions
1849 that refer to newer VALUEs. */
1851 || (GET_CODE (l
->loc
) != VALUE
1852 && !refs_newer_value_p (l
->loc
, x
))))
1856 for (l
= v
->locs
; l
; l
= l
->next
)
1858 || (GET_CODE (l
->loc
) != VALUE
1859 && !refs_newer_value_p (l
->loc
, x
)))
1861 /* Return the canonical value. */
1865 return v
->locs
->loc
;
1870 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1871 where SIZE is the size in bytes of the memory reference. If ADDR
1872 is not modified by the memory reference then ADDR is returned. */
1875 addr_side_effect_eval (rtx addr
, int size
, int n_refs
)
1879 switch (GET_CODE (addr
))
1882 offset
= (n_refs
+ 1) * size
;
1885 offset
= -(n_refs
+ 1) * size
;
1888 offset
= n_refs
* size
;
1891 offset
= -n_refs
* size
;
1899 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0),
1902 addr
= XEXP (addr
, 0);
1903 addr
= canon_rtx (addr
);
1908 /* Return one if X and Y (memory addresses) reference the
1909 same location in memory or if the references overlap.
1910 Return zero if they do not overlap, else return
1911 minus one in which case they still might reference the same location.
1913 C is an offset accumulator. When
1914 C is nonzero, we are testing aliases between X and Y + C.
1915 XSIZE is the size in bytes of the X reference,
1916 similarly YSIZE is the size in bytes for Y.
1917 Expect that canon_rtx has been already called for X and Y.
1919 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1920 referenced (the reference was BLKmode), so make the most pessimistic
1923 If XSIZE or YSIZE is negative, we may access memory outside the object
1924 being referenced as a side effect. This can happen when using AND to
1925 align memory references, as is done on the Alpha.
1927 Nice to notice that varying addresses cannot conflict with fp if no
1928 local variables had their addresses taken, but that's too hard now.
1930 ??? Contrary to the tree alias oracle this does not return
1931 one for X + non-constant and Y + non-constant when X and Y are equal.
1932 If that is fixed the TBAA hack for union type-punning can be removed. */
1935 memrefs_conflict_p (int xsize
, rtx x
, int ysize
, rtx y
, HOST_WIDE_INT c
)
1937 if (GET_CODE (x
) == VALUE
)
1941 struct elt_loc_list
*l
= NULL
;
1942 if (CSELIB_VAL_PTR (x
))
1943 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (x
))->locs
;
1945 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, y
))
1952 /* Don't call get_addr if y is the same VALUE. */
1956 if (GET_CODE (y
) == VALUE
)
1960 struct elt_loc_list
*l
= NULL
;
1961 if (CSELIB_VAL_PTR (y
))
1962 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (y
))->locs
;
1964 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, x
))
1971 /* Don't call get_addr if x is the same VALUE. */
1975 if (GET_CODE (x
) == HIGH
)
1977 else if (GET_CODE (x
) == LO_SUM
)
1980 x
= addr_side_effect_eval (x
, xsize
, 0);
1981 if (GET_CODE (y
) == HIGH
)
1983 else if (GET_CODE (y
) == LO_SUM
)
1986 y
= addr_side_effect_eval (y
, ysize
, 0);
1988 if (rtx_equal_for_memref_p (x
, y
))
1990 if (xsize
<= 0 || ysize
<= 0)
1992 if (c
>= 0 && xsize
> c
)
1994 if (c
< 0 && ysize
+c
> 0)
1999 /* This code used to check for conflicts involving stack references and
2000 globals but the base address alias code now handles these cases. */
2002 if (GET_CODE (x
) == PLUS
)
2004 /* The fact that X is canonicalized means that this
2005 PLUS rtx is canonicalized. */
2006 rtx x0
= XEXP (x
, 0);
2007 rtx x1
= XEXP (x
, 1);
2009 if (GET_CODE (y
) == PLUS
)
2011 /* The fact that Y is canonicalized means that this
2012 PLUS rtx is canonicalized. */
2013 rtx y0
= XEXP (y
, 0);
2014 rtx y1
= XEXP (y
, 1);
2016 if (rtx_equal_for_memref_p (x1
, y1
))
2017 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2018 if (rtx_equal_for_memref_p (x0
, y0
))
2019 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
2020 if (CONST_INT_P (x1
))
2022 if (CONST_INT_P (y1
))
2023 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
2024 c
- INTVAL (x1
) + INTVAL (y1
));
2026 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
2029 else if (CONST_INT_P (y1
))
2030 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
2034 else if (CONST_INT_P (x1
))
2035 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
2037 else if (GET_CODE (y
) == PLUS
)
2039 /* The fact that Y is canonicalized means that this
2040 PLUS rtx is canonicalized. */
2041 rtx y0
= XEXP (y
, 0);
2042 rtx y1
= XEXP (y
, 1);
2044 if (CONST_INT_P (y1
))
2045 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
2050 if (GET_CODE (x
) == GET_CODE (y
))
2051 switch (GET_CODE (x
))
2055 /* Handle cases where we expect the second operands to be the
2056 same, and check only whether the first operand would conflict
2059 rtx x1
= canon_rtx (XEXP (x
, 1));
2060 rtx y1
= canon_rtx (XEXP (y
, 1));
2061 if (! rtx_equal_for_memref_p (x1
, y1
))
2063 x0
= canon_rtx (XEXP (x
, 0));
2064 y0
= canon_rtx (XEXP (y
, 0));
2065 if (rtx_equal_for_memref_p (x0
, y0
))
2066 return (xsize
== 0 || ysize
== 0
2067 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
2069 /* Can't properly adjust our sizes. */
2070 if (!CONST_INT_P (x1
))
2072 xsize
/= INTVAL (x1
);
2073 ysize
/= INTVAL (x1
);
2075 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2082 /* Deal with alignment ANDs by adjusting offset and size so as to
2083 cover the maximum range, without taking any previously known
2084 alignment into account. */
2085 if (GET_CODE (x
) == AND
&& CONST_INT_P (XEXP (x
, 1)))
2087 HOST_WIDE_INT sc
= INTVAL (XEXP (x
, 1));
2088 unsigned HOST_WIDE_INT uc
= sc
;
2089 if (xsize
> 0 && sc
< 0 && -uc
== (uc
& -uc
))
2093 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2097 if (GET_CODE (y
) == AND
&& CONST_INT_P (XEXP (y
, 1)))
2099 HOST_WIDE_INT sc
= INTVAL (XEXP (y
, 1));
2100 unsigned HOST_WIDE_INT uc
= sc
;
2101 if (ysize
> 0 && sc
< 0 && -uc
== (uc
& -uc
))
2105 return memrefs_conflict_p (xsize
, x
,
2106 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2112 if (CONST_INT_P (x
) && CONST_INT_P (y
))
2114 c
+= (INTVAL (y
) - INTVAL (x
));
2115 return (xsize
<= 0 || ysize
<= 0
2116 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
2119 if (GET_CODE (x
) == CONST
)
2121 if (GET_CODE (y
) == CONST
)
2122 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2123 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2125 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2128 if (GET_CODE (y
) == CONST
)
2129 return memrefs_conflict_p (xsize
, x
, ysize
,
2130 canon_rtx (XEXP (y
, 0)), c
);
2133 return (xsize
<= 0 || ysize
<= 0
2134 || (rtx_equal_for_memref_p (x
, y
)
2135 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
2143 /* Functions to compute memory dependencies.
2145 Since we process the insns in execution order, we can build tables
2146 to keep track of what registers are fixed (and not aliased), what registers
2147 are varying in known ways, and what registers are varying in unknown
2150 If both memory references are volatile, then there must always be a
2151 dependence between the two references, since their order can not be
2152 changed. A volatile and non-volatile reference can be interchanged
2155 We also must allow AND addresses, because they may generate accesses
2156 outside the object being referenced. This is used to generate aligned
2157 addresses from unaligned addresses, for instance, the alpha
2158 storeqi_unaligned pattern. */
2160 /* Read dependence: X is read after read in MEM takes place. There can
2161 only be a dependence here if both reads are volatile, or if either is
2162 an explicit barrier. */
2165 read_dependence (const_rtx mem
, const_rtx x
)
2167 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2169 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2170 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2175 /* Return true if we can determine that the fields referenced cannot
2176 overlap for any pair of objects. */
2179 nonoverlapping_component_refs_p (const_rtx rtlx
, const_rtx rtly
)
2181 const_tree x
= MEM_EXPR (rtlx
), y
= MEM_EXPR (rtly
);
2182 const_tree fieldx
, fieldy
, typex
, typey
, orig_y
;
2184 if (!flag_strict_aliasing
2186 || TREE_CODE (x
) != COMPONENT_REF
2187 || TREE_CODE (y
) != COMPONENT_REF
)
2192 /* The comparison has to be done at a common type, since we don't
2193 know how the inheritance hierarchy works. */
2197 fieldx
= TREE_OPERAND (x
, 1);
2198 typex
= TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx
));
2203 fieldy
= TREE_OPERAND (y
, 1);
2204 typey
= TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy
));
2209 y
= TREE_OPERAND (y
, 0);
2211 while (y
&& TREE_CODE (y
) == COMPONENT_REF
);
2213 x
= TREE_OPERAND (x
, 0);
2215 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2216 /* Never found a common type. */
2220 /* If we're left with accessing different fields of a structure, then no
2221 possible overlap, unless they are both bitfields. */
2222 if (TREE_CODE (typex
) == RECORD_TYPE
&& fieldx
!= fieldy
)
2223 return !(DECL_BIT_FIELD (fieldx
) && DECL_BIT_FIELD (fieldy
));
2225 /* The comparison on the current field failed. If we're accessing
2226 a very nested structure, look at the next outer level. */
2227 x
= TREE_OPERAND (x
, 0);
2228 y
= TREE_OPERAND (y
, 0);
2231 && TREE_CODE (x
) == COMPONENT_REF
2232 && TREE_CODE (y
) == COMPONENT_REF
);
2237 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2240 decl_for_component_ref (tree x
)
2244 x
= TREE_OPERAND (x
, 0);
2246 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2248 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
2251 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2252 for the offset of the field reference. *KNOWN_P says whether the
2256 adjust_offset_for_component_ref (tree x
, bool *known_p
,
2257 HOST_WIDE_INT
*offset
)
2263 tree xoffset
= component_ref_field_offset (x
);
2264 tree field
= TREE_OPERAND (x
, 1);
2266 if (! host_integerp (xoffset
, 1))
2271 *offset
+= (tree_low_cst (xoffset
, 1)
2272 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 1)
2275 x
= TREE_OPERAND (x
, 0);
2277 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2280 /* Return nonzero if we can determine the exprs corresponding to memrefs
2281 X and Y and they do not overlap.
2282 If LOOP_VARIANT is set, skip offset-based disambiguation */
2285 nonoverlapping_memrefs_p (const_rtx x
, const_rtx y
, bool loop_invariant
)
2287 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
2290 bool moffsetx_known_p
, moffsety_known_p
;
2291 HOST_WIDE_INT moffsetx
= 0, moffsety
= 0;
2292 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
2294 /* Unless both have exprs, we can't tell anything. */
2295 if (exprx
== 0 || expry
== 0)
2298 /* For spill-slot accesses make sure we have valid offsets. */
2299 if ((exprx
== get_spill_slot_decl (false)
2300 && ! MEM_OFFSET_KNOWN_P (x
))
2301 || (expry
== get_spill_slot_decl (false)
2302 && ! MEM_OFFSET_KNOWN_P (y
)))
2305 /* If the field reference test failed, look at the DECLs involved. */
2306 moffsetx_known_p
= MEM_OFFSET_KNOWN_P (x
);
2307 if (moffsetx_known_p
)
2308 moffsetx
= MEM_OFFSET (x
);
2309 if (TREE_CODE (exprx
) == COMPONENT_REF
)
2311 tree t
= decl_for_component_ref (exprx
);
2314 adjust_offset_for_component_ref (exprx
, &moffsetx_known_p
, &moffsetx
);
2318 moffsety_known_p
= MEM_OFFSET_KNOWN_P (y
);
2319 if (moffsety_known_p
)
2320 moffsety
= MEM_OFFSET (y
);
2321 if (TREE_CODE (expry
) == COMPONENT_REF
)
2323 tree t
= decl_for_component_ref (expry
);
2326 adjust_offset_for_component_ref (expry
, &moffsety_known_p
, &moffsety
);
2330 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2333 /* With invalid code we can end up storing into the constant pool.
2334 Bail out to avoid ICEing when creating RTL for this.
2335 See gfortran.dg/lto/20091028-2_0.f90. */
2336 if (TREE_CODE (exprx
) == CONST_DECL
2337 || TREE_CODE (expry
) == CONST_DECL
)
2340 rtlx
= DECL_RTL (exprx
);
2341 rtly
= DECL_RTL (expry
);
2343 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2344 can't overlap unless they are the same because we never reuse that part
2345 of the stack frame used for locals for spilled pseudos. */
2346 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2347 && ! rtx_equal_p (rtlx
, rtly
))
2350 /* If we have MEMs referring to different address spaces (which can
2351 potentially overlap), we cannot easily tell from the addresses
2352 whether the references overlap. */
2353 if (MEM_P (rtlx
) && MEM_P (rtly
)
2354 && MEM_ADDR_SPACE (rtlx
) != MEM_ADDR_SPACE (rtly
))
2357 /* Get the base and offsets of both decls. If either is a register, we
2358 know both are and are the same, so use that as the base. The only
2359 we can avoid overlap is if we can deduce that they are nonoverlapping
2360 pieces of that decl, which is very rare. */
2361 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2362 if (GET_CODE (basex
) == PLUS
&& CONST_INT_P (XEXP (basex
, 1)))
2363 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2365 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2366 if (GET_CODE (basey
) == PLUS
&& CONST_INT_P (XEXP (basey
, 1)))
2367 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2369 /* If the bases are different, we know they do not overlap if both
2370 are constants or if one is a constant and the other a pointer into the
2371 stack frame. Otherwise a different base means we can't tell if they
2373 if (! rtx_equal_p (basex
, basey
))
2374 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2375 || (CONSTANT_P (basex
) && REG_P (basey
)
2376 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2377 || (CONSTANT_P (basey
) && REG_P (basex
)
2378 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2380 /* Offset based disambiguation not appropriate for loop invariant */
2384 sizex
= (!MEM_P (rtlx
) ? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2385 : MEM_SIZE_KNOWN_P (rtlx
) ? MEM_SIZE (rtlx
)
2387 sizey
= (!MEM_P (rtly
) ? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2388 : MEM_SIZE_KNOWN_P (rtly
) ? MEM_SIZE (rtly
)
2391 /* If we have an offset for either memref, it can update the values computed
2393 if (moffsetx_known_p
)
2394 offsetx
+= moffsetx
, sizex
-= moffsetx
;
2395 if (moffsety_known_p
)
2396 offsety
+= moffsety
, sizey
-= moffsety
;
2398 /* If a memref has both a size and an offset, we can use the smaller size.
2399 We can't do this if the offset isn't known because we must view this
2400 memref as being anywhere inside the DECL's MEM. */
2401 if (MEM_SIZE_KNOWN_P (x
) && moffsetx_known_p
)
2402 sizex
= MEM_SIZE (x
);
2403 if (MEM_SIZE_KNOWN_P (y
) && moffsety_known_p
)
2404 sizey
= MEM_SIZE (y
);
2406 /* Put the values of the memref with the lower offset in X's values. */
2407 if (offsetx
> offsety
)
2409 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2410 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2413 /* If we don't know the size of the lower-offset value, we can't tell
2414 if they conflict. Otherwise, we do the test. */
2415 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2418 /* Helper for true_dependence and canon_true_dependence.
2419 Checks for true dependence: X is read after store in MEM takes place.
2421 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2422 NULL_RTX, and the canonical addresses of MEM and X are both computed
2423 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2425 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2427 Returns 1 if there is a true dependence, 0 otherwise. */
2430 true_dependence_1 (const_rtx mem
, enum machine_mode mem_mode
, rtx mem_addr
,
2431 const_rtx x
, rtx x_addr
, bool mem_canonicalized
)
2436 gcc_checking_assert (mem_canonicalized
? (mem_addr
!= NULL_RTX
)
2437 : (mem_addr
== NULL_RTX
&& x_addr
== NULL_RTX
));
2439 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2442 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2443 This is used in epilogue deallocation functions, and in cselib. */
2444 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2446 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2448 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2449 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2452 /* Read-only memory is by definition never modified, and therefore can't
2453 conflict with anything. We don't expect to find read-only set on MEM,
2454 but stupid user tricks can produce them, so don't die. */
2455 if (MEM_READONLY_P (x
))
2458 /* If we have MEMs referring to different address spaces (which can
2459 potentially overlap), we cannot easily tell from the addresses
2460 whether the references overlap. */
2461 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2466 mem_addr
= XEXP (mem
, 0);
2467 if (mem_mode
== VOIDmode
)
2468 mem_mode
= GET_MODE (mem
);
2473 x_addr
= XEXP (x
, 0);
2474 if (!((GET_CODE (x_addr
) == VALUE
2475 && GET_CODE (mem_addr
) != VALUE
2476 && reg_mentioned_p (x_addr
, mem_addr
))
2477 || (GET_CODE (x_addr
) != VALUE
2478 && GET_CODE (mem_addr
) == VALUE
2479 && reg_mentioned_p (mem_addr
, x_addr
))))
2481 x_addr
= get_addr (x_addr
);
2482 if (! mem_canonicalized
)
2483 mem_addr
= get_addr (mem_addr
);
2487 base
= find_base_term (x_addr
);
2488 if (base
&& (GET_CODE (base
) == LABEL_REF
2489 || (GET_CODE (base
) == SYMBOL_REF
2490 && CONSTANT_POOL_ADDRESS_P (base
))))
2493 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2496 x_addr
= canon_rtx (x_addr
);
2497 if (!mem_canonicalized
)
2498 mem_addr
= canon_rtx (mem_addr
);
2500 if ((ret
= memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2501 SIZE_FOR_MODE (x
), x_addr
, 0)) != -1)
2504 if (mems_in_disjoint_alias_sets_p (x
, mem
))
2507 if (nonoverlapping_memrefs_p (mem
, x
, false))
2510 if (nonoverlapping_component_refs_p (mem
, x
))
2513 return rtx_refs_may_alias_p (x
, mem
, true);
2516 /* True dependence: X is read after store in MEM takes place. */
2519 true_dependence (const_rtx mem
, enum machine_mode mem_mode
, const_rtx x
)
2521 return true_dependence_1 (mem
, mem_mode
, NULL_RTX
,
2522 x
, NULL_RTX
, /*mem_canonicalized=*/false);
2525 /* Canonical true dependence: X is read after store in MEM takes place.
2526 Variant of true_dependence which assumes MEM has already been
2527 canonicalized (hence we no longer do that here).
2528 The mem_addr argument has been added, since true_dependence_1 computed
2529 this value prior to canonicalizing. */
2532 canon_true_dependence (const_rtx mem
, enum machine_mode mem_mode
, rtx mem_addr
,
2533 const_rtx x
, rtx x_addr
)
2535 return true_dependence_1 (mem
, mem_mode
, mem_addr
,
2536 x
, x_addr
, /*mem_canonicalized=*/true);
2539 /* Returns nonzero if a write to X might alias a previous read from
2540 (or, if WRITEP is nonzero, a write to) MEM. */
2543 write_dependence_p (const_rtx mem
, const_rtx x
, int writep
)
2545 rtx x_addr
, mem_addr
;
2549 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2552 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2553 This is used in epilogue deallocation functions. */
2554 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2556 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2558 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2559 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2562 /* A read from read-only memory can't conflict with read-write memory. */
2563 if (!writep
&& MEM_READONLY_P (mem
))
2566 /* If we have MEMs referring to different address spaces (which can
2567 potentially overlap), we cannot easily tell from the addresses
2568 whether the references overlap. */
2569 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2572 x_addr
= XEXP (x
, 0);
2573 mem_addr
= XEXP (mem
, 0);
2574 if (!((GET_CODE (x_addr
) == VALUE
2575 && GET_CODE (mem_addr
) != VALUE
2576 && reg_mentioned_p (x_addr
, mem_addr
))
2577 || (GET_CODE (x_addr
) != VALUE
2578 && GET_CODE (mem_addr
) == VALUE
2579 && reg_mentioned_p (mem_addr
, x_addr
))))
2581 x_addr
= get_addr (x_addr
);
2582 mem_addr
= get_addr (mem_addr
);
2587 base
= find_base_term (mem_addr
);
2588 if (base
&& (GET_CODE (base
) == LABEL_REF
2589 || (GET_CODE (base
) == SYMBOL_REF
2590 && CONSTANT_POOL_ADDRESS_P (base
))))
2594 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
2598 x_addr
= canon_rtx (x_addr
);
2599 mem_addr
= canon_rtx (mem_addr
);
2601 if ((ret
= memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2602 SIZE_FOR_MODE (x
), x_addr
, 0)) != -1)
2605 if (nonoverlapping_memrefs_p (x
, mem
, false))
2608 return rtx_refs_may_alias_p (x
, mem
, false);
2611 /* Anti dependence: X is written after read in MEM takes place. */
2614 anti_dependence (const_rtx mem
, const_rtx x
)
2616 return write_dependence_p (mem
, x
, /*writep=*/0);
2619 /* Output dependence: X is written after store in MEM takes place. */
2622 output_dependence (const_rtx mem
, const_rtx x
)
2624 return write_dependence_p (mem
, x
, /*writep=*/1);
2629 /* Check whether X may be aliased with MEM. Don't do offset-based
2630 memory disambiguation & TBAA. */
2632 may_alias_p (const_rtx mem
, const_rtx x
)
2634 rtx x_addr
, mem_addr
;
2636 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2639 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2640 This is used in epilogue deallocation functions. */
2641 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2643 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2645 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2646 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2649 /* Read-only memory is by definition never modified, and therefore can't
2650 conflict with anything. We don't expect to find read-only set on MEM,
2651 but stupid user tricks can produce them, so don't die. */
2652 if (MEM_READONLY_P (x
))
2655 /* If we have MEMs referring to different address spaces (which can
2656 potentially overlap), we cannot easily tell from the addresses
2657 whether the references overlap. */
2658 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2661 x_addr
= XEXP (x
, 0);
2662 mem_addr
= XEXP (mem
, 0);
2663 if (!((GET_CODE (x_addr
) == VALUE
2664 && GET_CODE (mem_addr
) != VALUE
2665 && reg_mentioned_p (x_addr
, mem_addr
))
2666 || (GET_CODE (x_addr
) != VALUE
2667 && GET_CODE (mem_addr
) == VALUE
2668 && reg_mentioned_p (mem_addr
, x_addr
))))
2670 x_addr
= get_addr (x_addr
);
2671 mem_addr
= get_addr (mem_addr
);
2674 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), GET_MODE (mem_addr
)))
2677 x_addr
= canon_rtx (x_addr
);
2678 mem_addr
= canon_rtx (mem_addr
);
2680 if (nonoverlapping_memrefs_p (mem
, x
, true))
2683 /* TBAA not valid for loop_invarint */
2684 return rtx_refs_may_alias_p (x
, mem
, false);
2688 init_alias_target (void)
2692 if (!arg_base_value
)
2693 arg_base_value
= gen_rtx_ADDRESS (VOIDmode
, 0);
2695 memset (static_reg_base_value
, 0, sizeof static_reg_base_value
);
2697 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2698 /* Check whether this register can hold an incoming pointer
2699 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2700 numbers, so translate if necessary due to register windows. */
2701 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2702 && HARD_REGNO_MODE_OK (i
, Pmode
))
2703 static_reg_base_value
[i
] = arg_base_value
;
2705 static_reg_base_value
[STACK_POINTER_REGNUM
]
2706 = unique_base_value (UNIQUE_BASE_VALUE_SP
);
2707 static_reg_base_value
[ARG_POINTER_REGNUM
]
2708 = unique_base_value (UNIQUE_BASE_VALUE_ARGP
);
2709 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2710 = unique_base_value (UNIQUE_BASE_VALUE_FP
);
2711 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2712 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2713 = unique_base_value (UNIQUE_BASE_VALUE_HFP
);
2717 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2718 to be memory reference. */
2719 static bool memory_modified
;
2721 memory_modified_1 (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
2725 if (anti_dependence (x
, (const_rtx
)data
) || output_dependence (x
, (const_rtx
)data
))
2726 memory_modified
= true;
2731 /* Return true when INSN possibly modify memory contents of MEM
2732 (i.e. address can be modified). */
2734 memory_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
2738 memory_modified
= false;
2739 note_stores (PATTERN (insn
), memory_modified_1
, CONST_CAST_RTX(mem
));
2740 return memory_modified
;
2743 /* Return TRUE if the destination of a set is rtx identical to
2746 set_dest_equal_p (const_rtx set
, const_rtx item
)
2748 rtx dest
= SET_DEST (set
);
2749 return rtx_equal_p (dest
, item
);
2752 /* Like memory_modified_in_insn_p, but return TRUE if INSN will
2753 *DEFINITELY* modify the memory contents of MEM. */
2755 memory_must_be_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
2759 insn
= PATTERN (insn
);
2760 if (GET_CODE (insn
) == SET
)
2761 return set_dest_equal_p (insn
, mem
);
2762 else if (GET_CODE (insn
) == PARALLEL
)
2765 for (i
= 0; i
< XVECLEN (insn
, 0); i
++)
2767 rtx sub
= XVECEXP (insn
, 0, i
);
2768 if (GET_CODE (sub
) == SET
2769 && set_dest_equal_p (sub
, mem
))
2776 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2780 init_alias_analysis (void)
2782 unsigned int maxreg
= max_reg_num ();
2790 timevar_push (TV_ALIAS_ANALYSIS
);
2792 vec_safe_grow_cleared (reg_known_value
, maxreg
- FIRST_PSEUDO_REGISTER
);
2793 reg_known_equiv_p
= sbitmap_alloc (maxreg
- FIRST_PSEUDO_REGISTER
);
2795 /* If we have memory allocated from the previous run, use it. */
2796 if (old_reg_base_value
)
2797 reg_base_value
= old_reg_base_value
;
2800 reg_base_value
->truncate (0);
2802 vec_safe_grow_cleared (reg_base_value
, maxreg
);
2804 new_reg_base_value
= XNEWVEC (rtx
, maxreg
);
2805 reg_seen
= sbitmap_alloc (maxreg
);
2807 /* The basic idea is that each pass through this loop will use the
2808 "constant" information from the previous pass to propagate alias
2809 information through another level of assignments.
2811 The propagation is done on the CFG in reverse post-order, to propagate
2812 things forward as far as possible in each iteration.
2814 This could get expensive if the assignment chains are long. Maybe
2815 we should throttle the number of iterations, possibly based on
2816 the optimization level or flag_expensive_optimizations.
2818 We could propagate more information in the first pass by making use
2819 of DF_REG_DEF_COUNT to determine immediately that the alias information
2820 for a pseudo is "constant".
2822 A program with an uninitialized variable can cause an infinite loop
2823 here. Instead of doing a full dataflow analysis to detect such problems
2824 we just cap the number of iterations for the loop.
2826 The state of the arrays for the set chain in question does not matter
2827 since the program has undefined behavior. */
2829 rpo
= XNEWVEC (int, n_basic_blocks
);
2830 rpo_cnt
= pre_and_rev_post_order_compute (NULL
, rpo
, false);
2835 /* Assume nothing will change this iteration of the loop. */
2838 /* We want to assign the same IDs each iteration of this loop, so
2839 start counting from one each iteration of the loop. */
2842 /* We're at the start of the function each iteration through the
2843 loop, so we're copying arguments. */
2844 copying_arguments
= true;
2846 /* Wipe the potential alias information clean for this pass. */
2847 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
2849 /* Wipe the reg_seen array clean. */
2850 bitmap_clear (reg_seen
);
2852 /* Mark all hard registers which may contain an address.
2853 The stack, frame and argument pointers may contain an address.
2854 An argument register which can hold a Pmode value may contain
2855 an address even if it is not in BASE_REGS.
2857 The address expression is VOIDmode for an argument and
2858 Pmode for other registers. */
2860 memcpy (new_reg_base_value
, static_reg_base_value
,
2861 FIRST_PSEUDO_REGISTER
* sizeof (rtx
));
2863 /* Walk the insns adding values to the new_reg_base_value array. */
2864 for (i
= 0; i
< rpo_cnt
; i
++)
2866 basic_block bb
= BASIC_BLOCK (rpo
[i
]);
2867 FOR_BB_INSNS (bb
, insn
)
2869 if (NONDEBUG_INSN_P (insn
))
2873 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2874 /* The prologue/epilogue insns are not threaded onto the
2875 insn chain until after reload has completed. Thus,
2876 there is no sense wasting time checking if INSN is in
2877 the prologue/epilogue until after reload has completed. */
2878 if (reload_completed
2879 && prologue_epilogue_contains (insn
))
2883 /* If this insn has a noalias note, process it, Otherwise,
2884 scan for sets. A simple set will have no side effects
2885 which could change the base value of any other register. */
2887 if (GET_CODE (PATTERN (insn
)) == SET
2888 && REG_NOTES (insn
) != 0
2889 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2890 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2892 note_stores (PATTERN (insn
), record_set
, NULL
);
2894 set
= single_set (insn
);
2897 && REG_P (SET_DEST (set
))
2898 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2900 unsigned int regno
= REGNO (SET_DEST (set
));
2901 rtx src
= SET_SRC (set
);
2904 note
= find_reg_equal_equiv_note (insn
);
2905 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
2906 && DF_REG_DEF_COUNT (regno
) != 1)
2909 if (note
!= NULL_RTX
2910 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2911 && ! rtx_varies_p (XEXP (note
, 0), 1)
2912 && ! reg_overlap_mentioned_p (SET_DEST (set
),
2915 set_reg_known_value (regno
, XEXP (note
, 0));
2916 set_reg_known_equiv_p (regno
,
2917 REG_NOTE_KIND (note
) == REG_EQUIV
);
2919 else if (DF_REG_DEF_COUNT (regno
) == 1
2920 && GET_CODE (src
) == PLUS
2921 && REG_P (XEXP (src
, 0))
2922 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
2923 && CONST_INT_P (XEXP (src
, 1)))
2925 t
= plus_constant (GET_MODE (src
), t
,
2926 INTVAL (XEXP (src
, 1)));
2927 set_reg_known_value (regno
, t
);
2928 set_reg_known_equiv_p (regno
, false);
2930 else if (DF_REG_DEF_COUNT (regno
) == 1
2931 && ! rtx_varies_p (src
, 1))
2933 set_reg_known_value (regno
, src
);
2934 set_reg_known_equiv_p (regno
, false);
2938 else if (NOTE_P (insn
)
2939 && NOTE_KIND (insn
) == NOTE_INSN_FUNCTION_BEG
)
2940 copying_arguments
= false;
2944 /* Now propagate values from new_reg_base_value to reg_base_value. */
2945 gcc_assert (maxreg
== (unsigned int) max_reg_num ());
2947 for (ui
= 0; ui
< maxreg
; ui
++)
2949 if (new_reg_base_value
[ui
]
2950 && new_reg_base_value
[ui
] != (*reg_base_value
)[ui
]
2951 && ! rtx_equal_p (new_reg_base_value
[ui
], (*reg_base_value
)[ui
]))
2953 (*reg_base_value
)[ui
] = new_reg_base_value
[ui
];
2958 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2961 /* Fill in the remaining entries. */
2962 FOR_EACH_VEC_ELT (*reg_known_value
, i
, val
)
2964 int regno
= i
+ FIRST_PSEUDO_REGISTER
;
2966 set_reg_known_value (regno
, regno_reg_rtx
[regno
]);
2970 free (new_reg_base_value
);
2971 new_reg_base_value
= 0;
2972 sbitmap_free (reg_seen
);
2974 timevar_pop (TV_ALIAS_ANALYSIS
);
2977 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
2978 Special API for var-tracking pass purposes. */
2981 vt_equate_reg_base_value (const_rtx reg1
, const_rtx reg2
)
2983 (*reg_base_value
)[REGNO (reg1
)] = REG_BASE_VALUE (reg2
);
2987 end_alias_analysis (void)
2989 old_reg_base_value
= reg_base_value
;
2990 vec_free (reg_known_value
);
2991 sbitmap_free (reg_known_equiv_p
);
2994 #include "gt-alias.h"