1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
3 2007 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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
25 #include "coretypes.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
40 #include "splay-tree.h"
42 #include "langhooks.h"
47 #include "tree-pass.h"
48 #include "ipa-type-escape.h"
51 /* The aliasing API provided here solves related but different problems:
53 Say there exists (in c)
67 Consider the four questions:
69 Can a store to x1 interfere with px2->y1?
70 Can a store to x1 interfere with px2->z2?
72 Can a store to x1 change the value pointed to by with py?
73 Can a store to x1 change the value pointed to by with pz?
75 The answer to these questions can be yes, yes, yes, and maybe.
77 The first two questions can be answered with a simple examination
78 of the type system. If structure X contains a field of type Y then
79 a store thru a pointer to an X can overwrite any field that is
80 contained (recursively) in an X (unless we know that px1 != px2).
82 The last two of the questions can be solved in the same way as the
83 first two questions but this is too conservative. The observation
84 is that in some cases analysis we can know if which (if any) fields
85 are addressed and if those addresses are used in bad ways. This
86 analysis may be language specific. In C, arbitrary operations may
87 be applied to pointers. However, there is some indication that
88 this may be too conservative for some C++ types.
90 The pass ipa-type-escape does this analysis for the types whose
91 instances do not escape across the compilation boundary.
93 Historically in GCC, these two problems were combined and a single
94 data structure was used to represent the solution to these
95 problems. We now have two similar but different data structures,
96 The data structure to solve the last two question is similar to the
97 first, but does not contain have the fields in it whose address are
98 never taken. For types that do escape the compilation unit, the
99 data structures will have identical information.
102 /* The alias sets assigned to MEMs assist the back-end in determining
103 which MEMs can alias which other MEMs. In general, two MEMs in
104 different alias sets cannot alias each other, with one important
105 exception. Consider something like:
107 struct S { int i; double d; };
109 a store to an `S' can alias something of either type `int' or type
110 `double'. (However, a store to an `int' cannot alias a `double'
111 and vice versa.) We indicate this via a tree structure that looks
119 (The arrows are directed and point downwards.)
120 In this situation we say the alias set for `struct S' is the
121 `superset' and that those for `int' and `double' are `subsets'.
123 To see whether two alias sets can point to the same memory, we must
124 see if either alias set is a subset of the other. We need not trace
125 past immediate descendants, however, since we propagate all
126 grandchildren up one level.
128 Alias set zero is implicitly a superset of all other alias sets.
129 However, this is no actual entry for alias set zero. It is an
130 error to attempt to explicitly construct a subset of zero. */
132 struct alias_set_entry
GTY(())
134 /* The alias set number, as stored in MEM_ALIAS_SET. */
135 HOST_WIDE_INT alias_set
;
137 /* The children of the alias set. These are not just the immediate
138 children, but, in fact, all descendants. So, if we have:
140 struct T { struct S s; float f; }
142 continuing our example above, the children here will be all of
143 `int', `double', `float', and `struct S'. */
144 splay_tree
GTY((param1_is (int), param2_is (int))) children
;
146 /* Nonzero if would have a child of zero: this effectively makes this
147 alias set the same as alias set zero. */
150 typedef struct alias_set_entry
*alias_set_entry
;
152 static int rtx_equal_for_memref_p (rtx
, rtx
);
153 static int memrefs_conflict_p (int, rtx
, int, rtx
, HOST_WIDE_INT
);
154 static void record_set (rtx
, rtx
, void *);
155 static int base_alias_check (rtx
, rtx
, enum machine_mode
,
157 static rtx
find_base_value (rtx
);
158 static int mems_in_disjoint_alias_sets_p (rtx
, rtx
);
159 static int insert_subset_children (splay_tree_node
, void*);
160 static tree
find_base_decl (tree
);
161 static alias_set_entry
get_alias_set_entry (HOST_WIDE_INT
);
162 static rtx
fixed_scalar_and_varying_struct_p (rtx
, rtx
, rtx
, rtx
,
164 static int aliases_everything_p (rtx
);
165 static bool nonoverlapping_component_refs_p (tree
, tree
);
166 static tree
decl_for_component_ref (tree
);
167 static rtx
adjust_offset_for_component_ref (tree
, rtx
);
168 static int nonoverlapping_memrefs_p (rtx
, rtx
);
169 static int write_dependence_p (rtx
, rtx
, int);
171 static void memory_modified_1 (rtx
, rtx
, void *);
172 static void record_alias_subset (HOST_WIDE_INT
, HOST_WIDE_INT
);
174 /* Set up all info needed to perform alias analysis on memory references. */
176 /* Returns the size in bytes of the mode of X. */
177 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
179 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
180 different alias sets. We ignore alias sets in functions making use
181 of variable arguments because the va_arg macros on some systems are
183 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
184 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
186 /* Cap the number of passes we make over the insns propagating alias
187 information through set chains. 10 is a completely arbitrary choice. */
188 #define MAX_ALIAS_LOOP_PASSES 10
190 /* reg_base_value[N] gives an address to which register N is related.
191 If all sets after the first add or subtract to the current value
192 or otherwise modify it so it does not point to a different top level
193 object, reg_base_value[N] is equal to the address part of the source
196 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
197 expressions represent certain special values: function arguments and
198 the stack, frame, and argument pointers.
200 The contents of an ADDRESS is not normally used, the mode of the
201 ADDRESS determines whether the ADDRESS is a function argument or some
202 other special value. Pointer equality, not rtx_equal_p, determines whether
203 two ADDRESS expressions refer to the same base address.
205 The only use of the contents of an ADDRESS is for determining if the
206 current function performs nonlocal memory memory references for the
207 purposes of marking the function as a constant function. */
209 static GTY(()) VEC(rtx
,gc
) *reg_base_value
;
210 static rtx
*new_reg_base_value
;
212 /* We preserve the copy of old array around to avoid amount of garbage
213 produced. About 8% of garbage produced were attributed to this
215 static GTY((deletable
)) VEC(rtx
,gc
) *old_reg_base_value
;
217 /* Static hunks of RTL used by the aliasing code; these are initialized
218 once per function to avoid unnecessary RTL allocations. */
219 static GTY (()) rtx static_reg_base_value
[FIRST_PSEUDO_REGISTER
];
221 #define REG_BASE_VALUE(X) \
222 (REGNO (X) < VEC_length (rtx, reg_base_value) \
223 ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
225 /* Vector indexed by N giving the initial (unchanging) value known for
226 pseudo-register N. This array is initialized in init_alias_analysis,
227 and does not change until end_alias_analysis is called. */
228 static GTY((length("reg_known_value_size"))) rtx
*reg_known_value
;
230 /* Indicates number of valid entries in reg_known_value. */
231 static GTY(()) unsigned int reg_known_value_size
;
233 /* Vector recording for each reg_known_value whether it is due to a
234 REG_EQUIV note. Future passes (viz., reload) may replace the
235 pseudo with the equivalent expression and so we account for the
236 dependences that would be introduced if that happens.
238 The REG_EQUIV notes created in assign_parms may mention the arg
239 pointer, and there are explicit insns in the RTL that modify the
240 arg pointer. Thus we must ensure that such insns don't get
241 scheduled across each other because that would invalidate the
242 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
243 wrong, but solving the problem in the scheduler will likely give
244 better code, so we do it here. */
245 static bool *reg_known_equiv_p
;
247 /* True when scanning insns from the start of the rtl to the
248 NOTE_INSN_FUNCTION_BEG note. */
249 static bool copying_arguments
;
251 DEF_VEC_P(alias_set_entry
);
252 DEF_VEC_ALLOC_P(alias_set_entry
,gc
);
254 /* The splay-tree used to store the various alias set entries. */
255 static GTY (()) VEC(alias_set_entry
,gc
) *alias_sets
;
257 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
258 such an entry, or NULL otherwise. */
260 static inline alias_set_entry
261 get_alias_set_entry (HOST_WIDE_INT alias_set
)
263 return VEC_index (alias_set_entry
, alias_sets
, alias_set
);
266 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
267 the two MEMs cannot alias each other. */
270 mems_in_disjoint_alias_sets_p (rtx mem1
, rtx mem2
)
272 /* Perform a basic sanity check. Namely, that there are no alias sets
273 if we're not using strict aliasing. This helps to catch bugs
274 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
275 where a MEM is allocated in some way other than by the use of
276 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
277 use alias sets to indicate that spilled registers cannot alias each
278 other, we might need to remove this check. */
279 gcc_assert (flag_strict_aliasing
280 || (!MEM_ALIAS_SET (mem1
) && !MEM_ALIAS_SET (mem2
)));
282 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
285 /* Insert the NODE into the splay tree given by DATA. Used by
286 record_alias_subset via splay_tree_foreach. */
289 insert_subset_children (splay_tree_node node
, void *data
)
291 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
296 /* Return true if the first alias set is a subset of the second. */
299 alias_set_subset_of (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
303 /* Everything is a subset of the "aliases everything" set. */
307 /* Otherwise, check if set1 is a subset of set2. */
308 ase
= get_alias_set_entry (set2
);
310 && (splay_tree_lookup (ase
->children
,
311 (splay_tree_key
) set1
)))
316 /* Return 1 if the two specified alias sets may conflict. */
319 alias_sets_conflict_p (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
323 /* If have no alias set information for one of the operands, we have
324 to assume it can alias anything. */
325 if (set1
== 0 || set2
== 0
326 /* If the two alias sets are the same, they may alias. */
330 /* See if the first alias set is a subset of the second. */
331 ase
= get_alias_set_entry (set1
);
333 && (ase
->has_zero_child
334 || splay_tree_lookup (ase
->children
,
335 (splay_tree_key
) set2
)))
338 /* Now do the same, but with the alias sets reversed. */
339 ase
= get_alias_set_entry (set2
);
341 && (ase
->has_zero_child
342 || splay_tree_lookup (ase
->children
,
343 (splay_tree_key
) set1
)))
346 /* The two alias sets are distinct and neither one is the
347 child of the other. Therefore, they cannot alias. */
351 /* Return 1 if the two specified alias sets might conflict, or if any subtype
352 of these alias sets might conflict. */
355 alias_sets_might_conflict_p (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
357 if (set1
== 0 || set2
== 0 || set1
== set2
)
364 /* Return 1 if any MEM object of type T1 will always conflict (using the
365 dependency routines in this file) with any MEM object of type T2.
366 This is used when allocating temporary storage. If T1 and/or T2 are
367 NULL_TREE, it means we know nothing about the storage. */
370 objects_must_conflict_p (tree t1
, tree t2
)
372 HOST_WIDE_INT set1
, set2
;
374 /* If neither has a type specified, we don't know if they'll conflict
375 because we may be using them to store objects of various types, for
376 example the argument and local variables areas of inlined functions. */
377 if (t1
== 0 && t2
== 0)
380 /* If they are the same type, they must conflict. */
382 /* Likewise if both are volatile. */
383 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
386 set1
= t1
? get_alias_set (t1
) : 0;
387 set2
= t2
? get_alias_set (t2
) : 0;
389 /* Otherwise they conflict if they have no alias set or the same. We
390 can't simply use alias_sets_conflict_p here, because we must make
391 sure that every subtype of t1 will conflict with every subtype of
392 t2 for which a pair of subobjects of these respective subtypes
393 overlaps on the stack. */
394 return set1
== 0 || set2
== 0 || set1
== set2
;
397 /* T is an expression with pointer type. Find the DECL on which this
398 expression is based. (For example, in `a[i]' this would be `a'.)
399 If there is no such DECL, or a unique decl cannot be determined,
400 NULL_TREE is returned. */
403 find_base_decl (tree t
)
407 if (t
== 0 || t
== error_mark_node
|| ! POINTER_TYPE_P (TREE_TYPE (t
)))
410 /* If this is a declaration, return it. If T is based on a restrict
411 qualified decl, return that decl. */
414 if (TREE_CODE (t
) == VAR_DECL
&& DECL_BASED_ON_RESTRICT_P (t
))
415 t
= DECL_GET_RESTRICT_BASE (t
);
419 /* Handle general expressions. It would be nice to deal with
420 COMPONENT_REFs here. If we could tell that `a' and `b' were the
421 same, then `a->f' and `b->f' are also the same. */
422 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
425 return find_base_decl (TREE_OPERAND (t
, 0));
428 /* Return 0 if found in neither or both are the same. */
429 d0
= find_base_decl (TREE_OPERAND (t
, 0));
430 d1
= find_base_decl (TREE_OPERAND (t
, 1));
445 /* Return true if all nested component references handled by
446 get_inner_reference in T are such that we should use the alias set
447 provided by the object at the heart of T.
449 This is true for non-addressable components (which don't have their
450 own alias set), as well as components of objects in alias set zero.
451 This later point is a special case wherein we wish to override the
452 alias set used by the component, but we don't have per-FIELD_DECL
453 assignable alias sets. */
456 component_uses_parent_alias_set (tree t
)
460 /* If we're at the end, it vacuously uses its own alias set. */
461 if (!handled_component_p (t
))
464 switch (TREE_CODE (t
))
467 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
472 case ARRAY_RANGE_REF
:
473 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
482 /* Bitfields and casts are never addressable. */
486 t
= TREE_OPERAND (t
, 0);
487 if (get_alias_set (TREE_TYPE (t
)) == 0)
492 /* Return the alias set for T, which may be either a type or an
493 expression. Call language-specific routine for help, if needed. */
496 get_alias_set (tree t
)
500 /* If we're not doing any alias analysis, just assume everything
501 aliases everything else. Also return 0 if this or its type is
503 if (! flag_strict_aliasing
|| t
== error_mark_node
505 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
508 /* We can be passed either an expression or a type. This and the
509 language-specific routine may make mutually-recursive calls to each other
510 to figure out what to do. At each juncture, we see if this is a tree
511 that the language may need to handle specially. First handle things that
517 /* Remove any nops, then give the language a chance to do
518 something with this tree before we look at it. */
520 set
= lang_hooks
.get_alias_set (t
);
524 /* First see if the actual object referenced is an INDIRECT_REF from a
525 restrict-qualified pointer or a "void *". */
526 while (handled_component_p (inner
))
528 inner
= TREE_OPERAND (inner
, 0);
532 /* Check for accesses through restrict-qualified pointers. */
533 if (INDIRECT_REF_P (inner
))
535 tree decl
= find_base_decl (TREE_OPERAND (inner
, 0));
537 if (decl
&& DECL_POINTER_ALIAS_SET_KNOWN_P (decl
))
539 /* If we haven't computed the actual alias set, do it now. */
540 if (DECL_POINTER_ALIAS_SET (decl
) == -2)
542 tree pointed_to_type
= TREE_TYPE (TREE_TYPE (decl
));
544 /* No two restricted pointers can point at the same thing.
545 However, a restricted pointer can point at the same thing
546 as an unrestricted pointer, if that unrestricted pointer
547 is based on the restricted pointer. So, we make the
548 alias set for the restricted pointer a subset of the
549 alias set for the type pointed to by the type of the
551 HOST_WIDE_INT pointed_to_alias_set
552 = get_alias_set (pointed_to_type
);
554 if (pointed_to_alias_set
== 0)
555 /* It's not legal to make a subset of alias set zero. */
556 DECL_POINTER_ALIAS_SET (decl
) = 0;
557 else if (AGGREGATE_TYPE_P (pointed_to_type
))
558 /* For an aggregate, we must treat the restricted
559 pointer the same as an ordinary pointer. If we
560 were to make the type pointed to by the
561 restricted pointer a subset of the pointed-to
562 type, then we would believe that other subsets
563 of the pointed-to type (such as fields of that
564 type) do not conflict with the type pointed to
565 by the restricted pointer. */
566 DECL_POINTER_ALIAS_SET (decl
)
567 = pointed_to_alias_set
;
570 DECL_POINTER_ALIAS_SET (decl
) = new_alias_set ();
571 record_alias_subset (pointed_to_alias_set
,
572 DECL_POINTER_ALIAS_SET (decl
));
576 /* We use the alias set indicated in the declaration. */
577 return DECL_POINTER_ALIAS_SET (decl
);
580 /* If we have an INDIRECT_REF via a void pointer, we don't
581 know anything about what that might alias. Likewise if the
582 pointer is marked that way. */
583 else if (TREE_CODE (TREE_TYPE (inner
)) == VOID_TYPE
584 || (TYPE_REF_CAN_ALIAS_ALL
585 (TREE_TYPE (TREE_OPERAND (inner
, 0)))))
589 /* Otherwise, pick up the outermost object that we could have a pointer
590 to, processing conversions as above. */
591 while (component_uses_parent_alias_set (t
))
593 t
= TREE_OPERAND (t
, 0);
597 /* If we've already determined the alias set for a decl, just return
598 it. This is necessary for C++ anonymous unions, whose component
599 variables don't look like union members (boo!). */
600 if (TREE_CODE (t
) == VAR_DECL
601 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
602 return MEM_ALIAS_SET (DECL_RTL (t
));
604 /* Now all we care about is the type. */
608 /* Variant qualifiers don't affect the alias set, so get the main
609 variant. If this is a type with a known alias set, return it. */
610 t
= TYPE_MAIN_VARIANT (t
);
611 if (TYPE_ALIAS_SET_KNOWN_P (t
))
612 return TYPE_ALIAS_SET (t
);
614 /* See if the language has special handling for this type. */
615 set
= lang_hooks
.get_alias_set (t
);
619 /* There are no objects of FUNCTION_TYPE, so there's no point in
620 using up an alias set for them. (There are, of course, pointers
621 and references to functions, but that's different.) */
622 else if (TREE_CODE (t
) == FUNCTION_TYPE
)
625 /* Unless the language specifies otherwise, let vector types alias
626 their components. This avoids some nasty type punning issues in
627 normal usage. And indeed lets vectors be treated more like an
629 else if (TREE_CODE (t
) == VECTOR_TYPE
)
630 set
= get_alias_set (TREE_TYPE (t
));
633 /* Otherwise make a new alias set for this type. */
634 set
= new_alias_set ();
636 TYPE_ALIAS_SET (t
) = set
;
638 /* If this is an aggregate type, we must record any component aliasing
640 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
641 record_component_aliases (t
);
646 /* Return a brand-new alias set. */
651 if (flag_strict_aliasing
)
654 VEC_safe_push (alias_set_entry
, gc
, alias_sets
, 0);
655 VEC_safe_push (alias_set_entry
, gc
, alias_sets
, 0);
656 return VEC_length (alias_set_entry
, alias_sets
) - 1;
662 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
663 not everything that aliases SUPERSET also aliases SUBSET. For example,
664 in C, a store to an `int' can alias a load of a structure containing an
665 `int', and vice versa. But it can't alias a load of a 'double' member
666 of the same structure. Here, the structure would be the SUPERSET and
667 `int' the SUBSET. This relationship is also described in the comment at
668 the beginning of this file.
670 This function should be called only once per SUPERSET/SUBSET pair.
672 It is illegal for SUPERSET to be zero; everything is implicitly a
673 subset of alias set zero. */
676 record_alias_subset (HOST_WIDE_INT superset
, HOST_WIDE_INT subset
)
678 alias_set_entry superset_entry
;
679 alias_set_entry subset_entry
;
681 /* It is possible in complex type situations for both sets to be the same,
682 in which case we can ignore this operation. */
683 if (superset
== subset
)
686 gcc_assert (superset
);
688 superset_entry
= get_alias_set_entry (superset
);
689 if (superset_entry
== 0)
691 /* Create an entry for the SUPERSET, so that we have a place to
692 attach the SUBSET. */
693 superset_entry
= ggc_alloc (sizeof (struct alias_set_entry
));
694 superset_entry
->alias_set
= superset
;
695 superset_entry
->children
696 = splay_tree_new_ggc (splay_tree_compare_ints
);
697 superset_entry
->has_zero_child
= 0;
698 VEC_replace (alias_set_entry
, alias_sets
, superset
, superset_entry
);
702 superset_entry
->has_zero_child
= 1;
705 subset_entry
= get_alias_set_entry (subset
);
706 /* If there is an entry for the subset, enter all of its children
707 (if they are not already present) as children of the SUPERSET. */
710 if (subset_entry
->has_zero_child
)
711 superset_entry
->has_zero_child
= 1;
713 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
714 superset_entry
->children
);
717 /* Enter the SUBSET itself as a child of the SUPERSET. */
718 splay_tree_insert (superset_entry
->children
,
719 (splay_tree_key
) subset
, 0);
723 /* Record that component types of TYPE, if any, are part of that type for
724 aliasing purposes. For record types, we only record component types
725 for fields that are marked addressable. For array types, we always
726 record the component types, so the front end should not call this
727 function if the individual component aren't addressable. */
730 record_component_aliases (tree type
)
732 HOST_WIDE_INT superset
= get_alias_set (type
);
738 switch (TREE_CODE (type
))
741 if (! TYPE_NONALIASED_COMPONENT (type
))
742 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
747 case QUAL_UNION_TYPE
:
748 /* Recursively record aliases for the base classes, if there are any. */
749 if (TYPE_BINFO (type
))
752 tree binfo
, base_binfo
;
754 for (binfo
= TYPE_BINFO (type
), i
= 0;
755 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
756 record_alias_subset (superset
,
757 get_alias_set (BINFO_TYPE (base_binfo
)));
759 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
760 if (TREE_CODE (field
) == FIELD_DECL
&& ! DECL_NONADDRESSABLE_P (field
))
761 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
765 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
773 /* Allocate an alias set for use in storing and reading from the varargs
776 static GTY(()) HOST_WIDE_INT varargs_set
= -1;
779 get_varargs_alias_set (void)
782 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
783 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
784 consistently use the varargs alias set for loads from the varargs
785 area. So don't use it anywhere. */
788 if (varargs_set
== -1)
789 varargs_set
= new_alias_set ();
795 /* Likewise, but used for the fixed portions of the frame, e.g., register
798 static GTY(()) HOST_WIDE_INT frame_set
= -1;
801 get_frame_alias_set (void)
804 frame_set
= new_alias_set ();
809 /* Inside SRC, the source of a SET, find a base address. */
812 find_base_value (rtx src
)
816 switch (GET_CODE (src
))
824 /* At the start of a function, argument registers have known base
825 values which may be lost later. Returning an ADDRESS
826 expression here allows optimization based on argument values
827 even when the argument registers are used for other purposes. */
828 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
829 return new_reg_base_value
[regno
];
831 /* If a pseudo has a known base value, return it. Do not do this
832 for non-fixed hard regs since it can result in a circular
833 dependency chain for registers which have values at function entry.
835 The test above is not sufficient because the scheduler may move
836 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
837 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
838 && regno
< VEC_length (rtx
, reg_base_value
))
840 /* If we're inside init_alias_analysis, use new_reg_base_value
841 to reduce the number of relaxation iterations. */
842 if (new_reg_base_value
&& new_reg_base_value
[regno
]
843 && DF_REG_DEF_COUNT (regno
) == 1)
844 return new_reg_base_value
[regno
];
846 if (VEC_index (rtx
, reg_base_value
, regno
))
847 return VEC_index (rtx
, reg_base_value
, regno
);
853 /* Check for an argument passed in memory. Only record in the
854 copying-arguments block; it is too hard to track changes
856 if (copying_arguments
857 && (XEXP (src
, 0) == arg_pointer_rtx
858 || (GET_CODE (XEXP (src
, 0)) == PLUS
859 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
860 return gen_rtx_ADDRESS (VOIDmode
, src
);
865 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
868 /* ... fall through ... */
873 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
875 /* If either operand is a REG that is a known pointer, then it
877 if (REG_P (src_0
) && REG_POINTER (src_0
))
878 return find_base_value (src_0
);
879 if (REG_P (src_1
) && REG_POINTER (src_1
))
880 return find_base_value (src_1
);
882 /* If either operand is a REG, then see if we already have
883 a known value for it. */
886 temp
= find_base_value (src_0
);
893 temp
= find_base_value (src_1
);
898 /* If either base is named object or a special address
899 (like an argument or stack reference), then use it for the
902 && (GET_CODE (src_0
) == SYMBOL_REF
903 || GET_CODE (src_0
) == LABEL_REF
904 || (GET_CODE (src_0
) == ADDRESS
905 && GET_MODE (src_0
) != VOIDmode
)))
909 && (GET_CODE (src_1
) == SYMBOL_REF
910 || GET_CODE (src_1
) == LABEL_REF
911 || (GET_CODE (src_1
) == ADDRESS
912 && GET_MODE (src_1
) != VOIDmode
)))
915 /* Guess which operand is the base address:
916 If either operand is a symbol, then it is the base. If
917 either operand is a CONST_INT, then the other is the base. */
918 if (GET_CODE (src_1
) == CONST_INT
|| CONSTANT_P (src_0
))
919 return find_base_value (src_0
);
920 else if (GET_CODE (src_0
) == CONST_INT
|| CONSTANT_P (src_1
))
921 return find_base_value (src_1
);
927 /* The standard form is (lo_sum reg sym) so look only at the
929 return find_base_value (XEXP (src
, 1));
932 /* If the second operand is constant set the base
933 address to the first operand. */
934 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
935 return find_base_value (XEXP (src
, 0));
939 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
949 return find_base_value (XEXP (src
, 0));
952 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
954 rtx temp
= find_base_value (XEXP (src
, 0));
956 if (temp
!= 0 && CONSTANT_P (temp
))
957 temp
= convert_memory_address (Pmode
, temp
);
969 /* Called from init_alias_analysis indirectly through note_stores. */
971 /* While scanning insns to find base values, reg_seen[N] is nonzero if
972 register N has been set in this function. */
973 static char *reg_seen
;
975 /* Addresses which are known not to alias anything else are identified
976 by a unique integer. */
977 static int unique_id
;
980 record_set (rtx dest
, rtx set
, void *data ATTRIBUTE_UNUSED
)
989 regno
= REGNO (dest
);
991 gcc_assert (regno
< VEC_length (rtx
, reg_base_value
));
993 /* If this spans multiple hard registers, then we must indicate that every
994 register has an unusable value. */
995 if (regno
< FIRST_PSEUDO_REGISTER
)
996 n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
1003 reg_seen
[regno
+ n
] = 1;
1004 new_reg_base_value
[regno
+ n
] = 0;
1011 /* A CLOBBER wipes out any old value but does not prevent a previously
1012 unset register from acquiring a base address (i.e. reg_seen is not
1014 if (GET_CODE (set
) == CLOBBER
)
1016 new_reg_base_value
[regno
] = 0;
1019 src
= SET_SRC (set
);
1023 if (reg_seen
[regno
])
1025 new_reg_base_value
[regno
] = 0;
1028 reg_seen
[regno
] = 1;
1029 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
1030 GEN_INT (unique_id
++));
1034 /* If this is not the first set of REGNO, see whether the new value
1035 is related to the old one. There are two cases of interest:
1037 (1) The register might be assigned an entirely new value
1038 that has the same base term as the original set.
1040 (2) The set might be a simple self-modification that
1041 cannot change REGNO's base value.
1043 If neither case holds, reject the original base value as invalid.
1044 Note that the following situation is not detected:
1046 extern int x, y; int *p = &x; p += (&y-&x);
1048 ANSI C does not allow computing the difference of addresses
1049 of distinct top level objects. */
1050 if (new_reg_base_value
[regno
] != 0
1051 && find_base_value (src
) != new_reg_base_value
[regno
])
1052 switch (GET_CODE (src
))
1056 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1057 new_reg_base_value
[regno
] = 0;
1060 /* If the value we add in the PLUS is also a valid base value,
1061 this might be the actual base value, and the original value
1064 rtx other
= NULL_RTX
;
1066 if (XEXP (src
, 0) == dest
)
1067 other
= XEXP (src
, 1);
1068 else if (XEXP (src
, 1) == dest
)
1069 other
= XEXP (src
, 0);
1071 if (! other
|| find_base_value (other
))
1072 new_reg_base_value
[regno
] = 0;
1076 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
1077 new_reg_base_value
[regno
] = 0;
1080 new_reg_base_value
[regno
] = 0;
1083 /* If this is the first set of a register, record the value. */
1084 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1085 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
1086 new_reg_base_value
[regno
] = find_base_value (src
);
1088 reg_seen
[regno
] = 1;
1091 /* If a value is known for REGNO, return it. */
1094 get_reg_known_value (unsigned int regno
)
1096 if (regno
>= FIRST_PSEUDO_REGISTER
)
1098 regno
-= FIRST_PSEUDO_REGISTER
;
1099 if (regno
< reg_known_value_size
)
1100 return reg_known_value
[regno
];
1108 set_reg_known_value (unsigned int regno
, rtx val
)
1110 if (regno
>= FIRST_PSEUDO_REGISTER
)
1112 regno
-= FIRST_PSEUDO_REGISTER
;
1113 if (regno
< reg_known_value_size
)
1114 reg_known_value
[regno
] = val
;
1118 /* Similarly for reg_known_equiv_p. */
1121 get_reg_known_equiv_p (unsigned int regno
)
1123 if (regno
>= FIRST_PSEUDO_REGISTER
)
1125 regno
-= FIRST_PSEUDO_REGISTER
;
1126 if (regno
< reg_known_value_size
)
1127 return reg_known_equiv_p
[regno
];
1133 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1135 if (regno
>= FIRST_PSEUDO_REGISTER
)
1137 regno
-= FIRST_PSEUDO_REGISTER
;
1138 if (regno
< reg_known_value_size
)
1139 reg_known_equiv_p
[regno
] = val
;
1144 /* Returns a canonical version of X, from the point of view alias
1145 analysis. (For example, if X is a MEM whose address is a register,
1146 and the register has a known value (say a SYMBOL_REF), then a MEM
1147 whose address is the SYMBOL_REF is returned.) */
1152 /* Recursively look for equivalences. */
1153 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1155 rtx t
= get_reg_known_value (REGNO (x
));
1159 return canon_rtx (t
);
1162 if (GET_CODE (x
) == PLUS
)
1164 rtx x0
= canon_rtx (XEXP (x
, 0));
1165 rtx x1
= canon_rtx (XEXP (x
, 1));
1167 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1169 if (GET_CODE (x0
) == CONST_INT
)
1170 return plus_constant (x1
, INTVAL (x0
));
1171 else if (GET_CODE (x1
) == CONST_INT
)
1172 return plus_constant (x0
, INTVAL (x1
));
1173 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1177 /* This gives us much better alias analysis when called from
1178 the loop optimizer. Note we want to leave the original
1179 MEM alone, but need to return the canonicalized MEM with
1180 all the flags with their original values. */
1182 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1187 /* Return 1 if X and Y are identical-looking rtx's.
1188 Expect that X and Y has been already canonicalized.
1190 We use the data in reg_known_value above to see if two registers with
1191 different numbers are, in fact, equivalent. */
1194 rtx_equal_for_memref_p (rtx x
, rtx y
)
1201 if (x
== 0 && y
== 0)
1203 if (x
== 0 || y
== 0)
1209 code
= GET_CODE (x
);
1210 /* Rtx's of different codes cannot be equal. */
1211 if (code
!= GET_CODE (y
))
1214 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1215 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1217 if (GET_MODE (x
) != GET_MODE (y
))
1220 /* Some RTL can be compared without a recursive examination. */
1224 return REGNO (x
) == REGNO (y
);
1227 return XEXP (x
, 0) == XEXP (y
, 0);
1230 return XSTR (x
, 0) == XSTR (y
, 0);
1235 /* There's no need to compare the contents of CONST_DOUBLEs or
1236 CONST_INTs because pointer equality is a good enough
1237 comparison for these nodes. */
1244 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1246 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1247 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1248 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1249 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1250 /* For commutative operations, the RTX match if the operand match in any
1251 order. Also handle the simple binary and unary cases without a loop. */
1252 if (COMMUTATIVE_P (x
))
1254 rtx xop0
= canon_rtx (XEXP (x
, 0));
1255 rtx yop0
= canon_rtx (XEXP (y
, 0));
1256 rtx yop1
= canon_rtx (XEXP (y
, 1));
1258 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1259 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1260 || (rtx_equal_for_memref_p (xop0
, yop1
)
1261 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1263 else if (NON_COMMUTATIVE_P (x
))
1265 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1266 canon_rtx (XEXP (y
, 0)))
1267 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1268 canon_rtx (XEXP (y
, 1))));
1270 else if (UNARY_P (x
))
1271 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1272 canon_rtx (XEXP (y
, 0)));
1274 /* Compare the elements. If any pair of corresponding elements
1275 fail to match, return 0 for the whole things.
1277 Limit cases to types which actually appear in addresses. */
1279 fmt
= GET_RTX_FORMAT (code
);
1280 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1285 if (XINT (x
, i
) != XINT (y
, i
))
1290 /* Two vectors must have the same length. */
1291 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1294 /* And the corresponding elements must match. */
1295 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1296 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1297 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1302 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1303 canon_rtx (XEXP (y
, i
))) == 0)
1307 /* This can happen for asm operands. */
1309 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1313 /* This can happen for an asm which clobbers memory. */
1317 /* It is believed that rtx's at this level will never
1318 contain anything but integers and other rtx's,
1319 except for within LABEL_REFs and SYMBOL_REFs. */
1328 find_base_term (rtx x
)
1331 struct elt_loc_list
*l
;
1333 #if defined (FIND_BASE_TERM)
1334 /* Try machine-dependent ways to find the base term. */
1335 x
= FIND_BASE_TERM (x
);
1338 switch (GET_CODE (x
))
1341 return REG_BASE_VALUE (x
);
1344 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1354 return find_base_term (XEXP (x
, 0));
1357 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1359 rtx temp
= find_base_term (XEXP (x
, 0));
1361 if (temp
!= 0 && CONSTANT_P (temp
))
1362 temp
= convert_memory_address (Pmode
, temp
);
1368 val
= CSELIB_VAL_PTR (x
);
1371 for (l
= val
->locs
; l
; l
= l
->next
)
1372 if ((x
= find_base_term (l
->loc
)) != 0)
1378 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1385 rtx tmp1
= XEXP (x
, 0);
1386 rtx tmp2
= XEXP (x
, 1);
1388 /* This is a little bit tricky since we have to determine which of
1389 the two operands represents the real base address. Otherwise this
1390 routine may return the index register instead of the base register.
1392 That may cause us to believe no aliasing was possible, when in
1393 fact aliasing is possible.
1395 We use a few simple tests to guess the base register. Additional
1396 tests can certainly be added. For example, if one of the operands
1397 is a shift or multiply, then it must be the index register and the
1398 other operand is the base register. */
1400 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1401 return find_base_term (tmp2
);
1403 /* If either operand is known to be a pointer, then use it
1404 to determine the base term. */
1405 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1406 return find_base_term (tmp1
);
1408 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1409 return find_base_term (tmp2
);
1411 /* Neither operand was known to be a pointer. Go ahead and find the
1412 base term for both operands. */
1413 tmp1
= find_base_term (tmp1
);
1414 tmp2
= find_base_term (tmp2
);
1416 /* If either base term is named object or a special address
1417 (like an argument or stack reference), then use it for the
1420 && (GET_CODE (tmp1
) == SYMBOL_REF
1421 || GET_CODE (tmp1
) == LABEL_REF
1422 || (GET_CODE (tmp1
) == ADDRESS
1423 && GET_MODE (tmp1
) != VOIDmode
)))
1427 && (GET_CODE (tmp2
) == SYMBOL_REF
1428 || GET_CODE (tmp2
) == LABEL_REF
1429 || (GET_CODE (tmp2
) == ADDRESS
1430 && GET_MODE (tmp2
) != VOIDmode
)))
1433 /* We could not determine which of the two operands was the
1434 base register and which was the index. So we can determine
1435 nothing from the base alias check. */
1440 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
&& INTVAL (XEXP (x
, 1)) != 0)
1441 return find_base_term (XEXP (x
, 0));
1453 /* Return 0 if the addresses X and Y are known to point to different
1454 objects, 1 if they might be pointers to the same object. */
1457 base_alias_check (rtx x
, rtx y
, enum machine_mode x_mode
,
1458 enum machine_mode y_mode
)
1460 rtx x_base
= find_base_term (x
);
1461 rtx y_base
= find_base_term (y
);
1463 /* If the address itself has no known base see if a known equivalent
1464 value has one. If either address still has no known base, nothing
1465 is known about aliasing. */
1470 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1473 x_base
= find_base_term (x_c
);
1481 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1484 y_base
= find_base_term (y_c
);
1489 /* If the base addresses are equal nothing is known about aliasing. */
1490 if (rtx_equal_p (x_base
, y_base
))
1493 /* The base addresses of the read and write are different expressions.
1494 If they are both symbols and they are not accessed via AND, there is
1495 no conflict. We can bring knowledge of object alignment into play
1496 here. For example, on alpha, "char a, b;" can alias one another,
1497 though "char a; long b;" cannot. */
1498 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1500 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1502 if (GET_CODE (x
) == AND
1503 && (GET_CODE (XEXP (x
, 1)) != CONST_INT
1504 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1506 if (GET_CODE (y
) == AND
1507 && (GET_CODE (XEXP (y
, 1)) != CONST_INT
1508 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1510 /* Differing symbols never alias. */
1514 /* If one address is a stack reference there can be no alias:
1515 stack references using different base registers do not alias,
1516 a stack reference can not alias a parameter, and a stack reference
1517 can not alias a global. */
1518 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
1519 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
1522 if (! flag_argument_noalias
)
1525 if (flag_argument_noalias
> 1)
1528 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1529 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
1532 /* Convert the address X into something we can use. This is done by returning
1533 it unchanged unless it is a value; in the latter case we call cselib to get
1534 a more useful rtx. */
1540 struct elt_loc_list
*l
;
1542 if (GET_CODE (x
) != VALUE
)
1544 v
= CSELIB_VAL_PTR (x
);
1547 for (l
= v
->locs
; l
; l
= l
->next
)
1548 if (CONSTANT_P (l
->loc
))
1550 for (l
= v
->locs
; l
; l
= l
->next
)
1551 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
))
1554 return v
->locs
->loc
;
1559 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1560 where SIZE is the size in bytes of the memory reference. If ADDR
1561 is not modified by the memory reference then ADDR is returned. */
1564 addr_side_effect_eval (rtx addr
, int size
, int n_refs
)
1568 switch (GET_CODE (addr
))
1571 offset
= (n_refs
+ 1) * size
;
1574 offset
= -(n_refs
+ 1) * size
;
1577 offset
= n_refs
* size
;
1580 offset
= -n_refs
* size
;
1588 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0),
1591 addr
= XEXP (addr
, 0);
1592 addr
= canon_rtx (addr
);
1597 /* Return nonzero if X and Y (memory addresses) could reference the
1598 same location in memory. C is an offset accumulator. When
1599 C is nonzero, we are testing aliases between X and Y + C.
1600 XSIZE is the size in bytes of the X reference,
1601 similarly YSIZE is the size in bytes for Y.
1602 Expect that canon_rtx has been already called for X and Y.
1604 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1605 referenced (the reference was BLKmode), so make the most pessimistic
1608 If XSIZE or YSIZE is negative, we may access memory outside the object
1609 being referenced as a side effect. This can happen when using AND to
1610 align memory references, as is done on the Alpha.
1612 Nice to notice that varying addresses cannot conflict with fp if no
1613 local variables had their addresses taken, but that's too hard now. */
1616 memrefs_conflict_p (int xsize
, rtx x
, int ysize
, rtx y
, HOST_WIDE_INT c
)
1618 if (GET_CODE (x
) == VALUE
)
1620 if (GET_CODE (y
) == VALUE
)
1622 if (GET_CODE (x
) == HIGH
)
1624 else if (GET_CODE (x
) == LO_SUM
)
1627 x
= addr_side_effect_eval (x
, xsize
, 0);
1628 if (GET_CODE (y
) == HIGH
)
1630 else if (GET_CODE (y
) == LO_SUM
)
1633 y
= addr_side_effect_eval (y
, ysize
, 0);
1635 if (rtx_equal_for_memref_p (x
, y
))
1637 if (xsize
<= 0 || ysize
<= 0)
1639 if (c
>= 0 && xsize
> c
)
1641 if (c
< 0 && ysize
+c
> 0)
1646 /* This code used to check for conflicts involving stack references and
1647 globals but the base address alias code now handles these cases. */
1649 if (GET_CODE (x
) == PLUS
)
1651 /* The fact that X is canonicalized means that this
1652 PLUS rtx is canonicalized. */
1653 rtx x0
= XEXP (x
, 0);
1654 rtx x1
= XEXP (x
, 1);
1656 if (GET_CODE (y
) == PLUS
)
1658 /* The fact that Y is canonicalized means that this
1659 PLUS rtx is canonicalized. */
1660 rtx y0
= XEXP (y
, 0);
1661 rtx y1
= XEXP (y
, 1);
1663 if (rtx_equal_for_memref_p (x1
, y1
))
1664 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1665 if (rtx_equal_for_memref_p (x0
, y0
))
1666 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
1667 if (GET_CODE (x1
) == CONST_INT
)
1669 if (GET_CODE (y1
) == CONST_INT
)
1670 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
1671 c
- INTVAL (x1
) + INTVAL (y1
));
1673 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
1676 else if (GET_CODE (y1
) == CONST_INT
)
1677 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1681 else if (GET_CODE (x1
) == CONST_INT
)
1682 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
1684 else if (GET_CODE (y
) == PLUS
)
1686 /* The fact that Y is canonicalized means that this
1687 PLUS rtx is canonicalized. */
1688 rtx y0
= XEXP (y
, 0);
1689 rtx y1
= XEXP (y
, 1);
1691 if (GET_CODE (y1
) == CONST_INT
)
1692 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1697 if (GET_CODE (x
) == GET_CODE (y
))
1698 switch (GET_CODE (x
))
1702 /* Handle cases where we expect the second operands to be the
1703 same, and check only whether the first operand would conflict
1706 rtx x1
= canon_rtx (XEXP (x
, 1));
1707 rtx y1
= canon_rtx (XEXP (y
, 1));
1708 if (! rtx_equal_for_memref_p (x1
, y1
))
1710 x0
= canon_rtx (XEXP (x
, 0));
1711 y0
= canon_rtx (XEXP (y
, 0));
1712 if (rtx_equal_for_memref_p (x0
, y0
))
1713 return (xsize
== 0 || ysize
== 0
1714 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1716 /* Can't properly adjust our sizes. */
1717 if (GET_CODE (x1
) != CONST_INT
)
1719 xsize
/= INTVAL (x1
);
1720 ysize
/= INTVAL (x1
);
1722 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1729 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1730 as an access with indeterminate size. Assume that references
1731 besides AND are aligned, so if the size of the other reference is
1732 at least as large as the alignment, assume no other overlap. */
1733 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1735 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1737 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)), ysize
, y
, c
);
1739 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1741 /* ??? If we are indexing far enough into the array/structure, we
1742 may yet be able to determine that we can not overlap. But we
1743 also need to that we are far enough from the end not to overlap
1744 a following reference, so we do nothing with that for now. */
1745 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1747 return memrefs_conflict_p (xsize
, x
, ysize
, canon_rtx (XEXP (y
, 0)), c
);
1752 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1754 c
+= (INTVAL (y
) - INTVAL (x
));
1755 return (xsize
<= 0 || ysize
<= 0
1756 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1759 if (GET_CODE (x
) == CONST
)
1761 if (GET_CODE (y
) == CONST
)
1762 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1763 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1765 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1768 if (GET_CODE (y
) == CONST
)
1769 return memrefs_conflict_p (xsize
, x
, ysize
,
1770 canon_rtx (XEXP (y
, 0)), c
);
1773 return (xsize
<= 0 || ysize
<= 0
1774 || (rtx_equal_for_memref_p (x
, y
)
1775 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1782 /* Functions to compute memory dependencies.
1784 Since we process the insns in execution order, we can build tables
1785 to keep track of what registers are fixed (and not aliased), what registers
1786 are varying in known ways, and what registers are varying in unknown
1789 If both memory references are volatile, then there must always be a
1790 dependence between the two references, since their order can not be
1791 changed. A volatile and non-volatile reference can be interchanged
1794 A MEM_IN_STRUCT reference at a non-AND varying address can never
1795 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1796 also must allow AND addresses, because they may generate accesses
1797 outside the object being referenced. This is used to generate
1798 aligned addresses from unaligned addresses, for instance, the alpha
1799 storeqi_unaligned pattern. */
1801 /* Read dependence: X is read after read in MEM takes place. There can
1802 only be a dependence here if both reads are volatile. */
1805 read_dependence (rtx mem
, rtx x
)
1807 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1810 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1811 MEM2 is a reference to a structure at a varying address, or returns
1812 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1813 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1814 to decide whether or not an address may vary; it should return
1815 nonzero whenever variation is possible.
1816 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1819 fixed_scalar_and_varying_struct_p (rtx mem1
, rtx mem2
, rtx mem1_addr
,
1821 int (*varies_p
) (rtx
, int))
1823 if (! flag_strict_aliasing
)
1826 if (MEM_ALIAS_SET (mem2
)
1827 && MEM_SCALAR_P (mem1
) && MEM_IN_STRUCT_P (mem2
)
1828 && !varies_p (mem1_addr
, 1) && varies_p (mem2_addr
, 1))
1829 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1833 if (MEM_ALIAS_SET (mem1
)
1834 && MEM_IN_STRUCT_P (mem1
) && MEM_SCALAR_P (mem2
)
1835 && varies_p (mem1_addr
, 1) && !varies_p (mem2_addr
, 1))
1836 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1843 /* Returns nonzero if something about the mode or address format MEM1
1844 indicates that it might well alias *anything*. */
1847 aliases_everything_p (rtx mem
)
1849 if (GET_CODE (XEXP (mem
, 0)) == AND
)
1850 /* If the address is an AND, it's very hard to know at what it is
1851 actually pointing. */
1857 /* Return true if we can determine that the fields referenced cannot
1858 overlap for any pair of objects. */
1861 nonoverlapping_component_refs_p (tree x
, tree y
)
1863 tree fieldx
, fieldy
, typex
, typey
, orig_y
;
1867 /* The comparison has to be done at a common type, since we don't
1868 know how the inheritance hierarchy works. */
1872 fieldx
= TREE_OPERAND (x
, 1);
1873 typex
= TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx
));
1878 fieldy
= TREE_OPERAND (y
, 1);
1879 typey
= TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy
));
1884 y
= TREE_OPERAND (y
, 0);
1886 while (y
&& TREE_CODE (y
) == COMPONENT_REF
);
1888 x
= TREE_OPERAND (x
, 0);
1890 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1891 /* Never found a common type. */
1895 /* If we're left with accessing different fields of a structure,
1897 if (TREE_CODE (typex
) == RECORD_TYPE
1898 && fieldx
!= fieldy
)
1901 /* The comparison on the current field failed. If we're accessing
1902 a very nested structure, look at the next outer level. */
1903 x
= TREE_OPERAND (x
, 0);
1904 y
= TREE_OPERAND (y
, 0);
1907 && TREE_CODE (x
) == COMPONENT_REF
1908 && TREE_CODE (y
) == COMPONENT_REF
);
1913 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1916 decl_for_component_ref (tree x
)
1920 x
= TREE_OPERAND (x
, 0);
1922 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1924 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
1927 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1928 offset of the field reference. */
1931 adjust_offset_for_component_ref (tree x
, rtx offset
)
1933 HOST_WIDE_INT ioffset
;
1938 ioffset
= INTVAL (offset
);
1941 tree offset
= component_ref_field_offset (x
);
1942 tree field
= TREE_OPERAND (x
, 1);
1944 if (! host_integerp (offset
, 1))
1946 ioffset
+= (tree_low_cst (offset
, 1)
1947 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 1)
1950 x
= TREE_OPERAND (x
, 0);
1952 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1954 return GEN_INT (ioffset
);
1957 /* Return nonzero if we can determine the exprs corresponding to memrefs
1958 X and Y and they do not overlap. */
1961 nonoverlapping_memrefs_p (rtx x
, rtx y
)
1963 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
1966 rtx moffsetx
, moffsety
;
1967 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
1969 /* Unless both have exprs, we can't tell anything. */
1970 if (exprx
== 0 || expry
== 0)
1973 /* If both are field references, we may be able to determine something. */
1974 if (TREE_CODE (exprx
) == COMPONENT_REF
1975 && TREE_CODE (expry
) == COMPONENT_REF
1976 && nonoverlapping_component_refs_p (exprx
, expry
))
1980 /* If the field reference test failed, look at the DECLs involved. */
1981 moffsetx
= MEM_OFFSET (x
);
1982 if (TREE_CODE (exprx
) == COMPONENT_REF
)
1984 if (TREE_CODE (expry
) == VAR_DECL
1985 && POINTER_TYPE_P (TREE_TYPE (expry
)))
1987 tree field
= TREE_OPERAND (exprx
, 1);
1988 tree fieldcontext
= DECL_FIELD_CONTEXT (field
);
1989 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext
,
1994 tree t
= decl_for_component_ref (exprx
);
1997 moffsetx
= adjust_offset_for_component_ref (exprx
, moffsetx
);
2001 else if (INDIRECT_REF_P (exprx
))
2003 exprx
= TREE_OPERAND (exprx
, 0);
2004 if (flag_argument_noalias
< 2
2005 || TREE_CODE (exprx
) != PARM_DECL
)
2009 moffsety
= MEM_OFFSET (y
);
2010 if (TREE_CODE (expry
) == COMPONENT_REF
)
2012 if (TREE_CODE (exprx
) == VAR_DECL
2013 && POINTER_TYPE_P (TREE_TYPE (exprx
)))
2015 tree field
= TREE_OPERAND (expry
, 1);
2016 tree fieldcontext
= DECL_FIELD_CONTEXT (field
);
2017 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext
,
2022 tree t
= decl_for_component_ref (expry
);
2025 moffsety
= adjust_offset_for_component_ref (expry
, moffsety
);
2029 else if (INDIRECT_REF_P (expry
))
2031 expry
= TREE_OPERAND (expry
, 0);
2032 if (flag_argument_noalias
< 2
2033 || TREE_CODE (expry
) != PARM_DECL
)
2037 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2040 rtlx
= DECL_RTL (exprx
);
2041 rtly
= DECL_RTL (expry
);
2043 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2044 can't overlap unless they are the same because we never reuse that part
2045 of the stack frame used for locals for spilled pseudos. */
2046 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2047 && ! rtx_equal_p (rtlx
, rtly
))
2050 /* Get the base and offsets of both decls. If either is a register, we
2051 know both are and are the same, so use that as the base. The only
2052 we can avoid overlap is if we can deduce that they are nonoverlapping
2053 pieces of that decl, which is very rare. */
2054 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2055 if (GET_CODE (basex
) == PLUS
&& GET_CODE (XEXP (basex
, 1)) == CONST_INT
)
2056 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2058 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2059 if (GET_CODE (basey
) == PLUS
&& GET_CODE (XEXP (basey
, 1)) == CONST_INT
)
2060 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2062 /* If the bases are different, we know they do not overlap if both
2063 are constants or if one is a constant and the other a pointer into the
2064 stack frame. Otherwise a different base means we can't tell if they
2066 if (! rtx_equal_p (basex
, basey
))
2067 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2068 || (CONSTANT_P (basex
) && REG_P (basey
)
2069 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2070 || (CONSTANT_P (basey
) && REG_P (basex
)
2071 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2073 sizex
= (!MEM_P (rtlx
) ? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2074 : MEM_SIZE (rtlx
) ? INTVAL (MEM_SIZE (rtlx
))
2076 sizey
= (!MEM_P (rtly
) ? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2077 : MEM_SIZE (rtly
) ? INTVAL (MEM_SIZE (rtly
)) :
2080 /* If we have an offset for either memref, it can update the values computed
2083 offsetx
+= INTVAL (moffsetx
), sizex
-= INTVAL (moffsetx
);
2085 offsety
+= INTVAL (moffsety
), sizey
-= INTVAL (moffsety
);
2087 /* If a memref has both a size and an offset, we can use the smaller size.
2088 We can't do this if the offset isn't known because we must view this
2089 memref as being anywhere inside the DECL's MEM. */
2090 if (MEM_SIZE (x
) && moffsetx
)
2091 sizex
= INTVAL (MEM_SIZE (x
));
2092 if (MEM_SIZE (y
) && moffsety
)
2093 sizey
= INTVAL (MEM_SIZE (y
));
2095 /* Put the values of the memref with the lower offset in X's values. */
2096 if (offsetx
> offsety
)
2098 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2099 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2102 /* If we don't know the size of the lower-offset value, we can't tell
2103 if they conflict. Otherwise, we do the test. */
2104 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2107 /* True dependence: X is read after store in MEM takes place. */
2110 true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx x
,
2111 int (*varies
) (rtx
, int))
2113 rtx x_addr
, mem_addr
;
2116 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2119 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2120 This is used in epilogue deallocation functions, and in cselib. */
2121 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2123 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2125 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2126 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2129 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2132 /* Read-only memory is by definition never modified, and therefore can't
2133 conflict with anything. We don't expect to find read-only set on MEM,
2134 but stupid user tricks can produce them, so don't die. */
2135 if (MEM_READONLY_P (x
))
2138 if (nonoverlapping_memrefs_p (mem
, x
))
2141 if (mem_mode
== VOIDmode
)
2142 mem_mode
= GET_MODE (mem
);
2144 x_addr
= get_addr (XEXP (x
, 0));
2145 mem_addr
= get_addr (XEXP (mem
, 0));
2147 base
= find_base_term (x_addr
);
2148 if (base
&& (GET_CODE (base
) == LABEL_REF
2149 || (GET_CODE (base
) == SYMBOL_REF
2150 && CONSTANT_POOL_ADDRESS_P (base
))))
2153 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2156 x_addr
= canon_rtx (x_addr
);
2157 mem_addr
= canon_rtx (mem_addr
);
2159 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2160 SIZE_FOR_MODE (x
), x_addr
, 0))
2163 if (aliases_everything_p (x
))
2166 /* We cannot use aliases_everything_p to test MEM, since we must look
2167 at MEM_MODE, rather than GET_MODE (MEM). */
2168 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2171 /* In true_dependence we also allow BLKmode to alias anything. Why
2172 don't we do this in anti_dependence and output_dependence? */
2173 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2176 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2180 /* Canonical true dependence: X is read after store in MEM takes place.
2181 Variant of true_dependence which assumes MEM has already been
2182 canonicalized (hence we no longer do that here).
2183 The mem_addr argument has been added, since true_dependence computed
2184 this value prior to canonicalizing. */
2187 canon_true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx mem_addr
,
2188 rtx x
, int (*varies
) (rtx
, int))
2192 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2195 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2196 This is used in epilogue deallocation functions. */
2197 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2199 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2201 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2202 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2205 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2208 /* Read-only memory is by definition never modified, and therefore can't
2209 conflict with anything. We don't expect to find read-only set on MEM,
2210 but stupid user tricks can produce them, so don't die. */
2211 if (MEM_READONLY_P (x
))
2214 if (nonoverlapping_memrefs_p (x
, mem
))
2217 x_addr
= get_addr (XEXP (x
, 0));
2219 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2222 x_addr
= canon_rtx (x_addr
);
2223 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2224 SIZE_FOR_MODE (x
), x_addr
, 0))
2227 if (aliases_everything_p (x
))
2230 /* We cannot use aliases_everything_p to test MEM, since we must look
2231 at MEM_MODE, rather than GET_MODE (MEM). */
2232 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2235 /* In true_dependence we also allow BLKmode to alias anything. Why
2236 don't we do this in anti_dependence and output_dependence? */
2237 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2240 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2244 /* Returns nonzero if a write to X might alias a previous read from
2245 (or, if WRITEP is nonzero, a write to) MEM. */
2248 write_dependence_p (rtx mem
, rtx x
, int writep
)
2250 rtx x_addr
, mem_addr
;
2254 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2257 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2258 This is used in epilogue deallocation functions. */
2259 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2261 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2263 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2264 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2267 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2270 /* A read from read-only memory can't conflict with read-write memory. */
2271 if (!writep
&& MEM_READONLY_P (mem
))
2274 if (nonoverlapping_memrefs_p (x
, mem
))
2277 x_addr
= get_addr (XEXP (x
, 0));
2278 mem_addr
= get_addr (XEXP (mem
, 0));
2282 base
= find_base_term (mem_addr
);
2283 if (base
&& (GET_CODE (base
) == LABEL_REF
2284 || (GET_CODE (base
) == SYMBOL_REF
2285 && CONSTANT_POOL_ADDRESS_P (base
))))
2289 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
2293 x_addr
= canon_rtx (x_addr
);
2294 mem_addr
= canon_rtx (mem_addr
);
2296 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2297 SIZE_FOR_MODE (x
), x_addr
, 0))
2301 = fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2304 return (!(fixed_scalar
== mem
&& !aliases_everything_p (x
))
2305 && !(fixed_scalar
== x
&& !aliases_everything_p (mem
)));
2308 /* Anti dependence: X is written after read in MEM takes place. */
2311 anti_dependence (rtx mem
, rtx x
)
2313 return write_dependence_p (mem
, x
, /*writep=*/0);
2316 /* Output dependence: X is written after store in MEM takes place. */
2319 output_dependence (rtx mem
, rtx x
)
2321 return write_dependence_p (mem
, x
, /*writep=*/1);
2326 init_alias_once (void)
2330 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2331 /* Check whether this register can hold an incoming pointer
2332 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2333 numbers, so translate if necessary due to register windows. */
2334 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2335 && HARD_REGNO_MODE_OK (i
, Pmode
))
2336 static_reg_base_value
[i
]
2337 = gen_rtx_ADDRESS (VOIDmode
, gen_rtx_REG (Pmode
, i
));
2339 static_reg_base_value
[STACK_POINTER_REGNUM
]
2340 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
2341 static_reg_base_value
[ARG_POINTER_REGNUM
]
2342 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
2343 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2344 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
2345 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2346 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2347 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
2351 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2352 to be memory reference. */
2353 static bool memory_modified
;
2355 memory_modified_1 (rtx x
, rtx pat ATTRIBUTE_UNUSED
, void *data
)
2359 if (anti_dependence (x
, (rtx
)data
) || output_dependence (x
, (rtx
)data
))
2360 memory_modified
= true;
2365 /* Return true when INSN possibly modify memory contents of MEM
2366 (i.e. address can be modified). */
2368 memory_modified_in_insn_p (rtx mem
, rtx insn
)
2372 memory_modified
= false;
2373 note_stores (PATTERN (insn
), memory_modified_1
, mem
);
2374 return memory_modified
;
2377 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2381 init_alias_analysis (void)
2383 unsigned int maxreg
= max_reg_num ();
2389 timevar_push (TV_ALIAS_ANALYSIS
);
2391 reg_known_value_size
= maxreg
- FIRST_PSEUDO_REGISTER
;
2392 reg_known_value
= ggc_calloc (reg_known_value_size
, sizeof (rtx
));
2393 reg_known_equiv_p
= xcalloc (reg_known_value_size
, sizeof (bool));
2395 /* If we have memory allocated from the previous run, use it. */
2396 if (old_reg_base_value
)
2397 reg_base_value
= old_reg_base_value
;
2400 VEC_truncate (rtx
, reg_base_value
, 0);
2402 VEC_safe_grow_cleared (rtx
, gc
, reg_base_value
, maxreg
);
2404 new_reg_base_value
= XNEWVEC (rtx
, maxreg
);
2405 reg_seen
= XNEWVEC (char, maxreg
);
2407 /* The basic idea is that each pass through this loop will use the
2408 "constant" information from the previous pass to propagate alias
2409 information through another level of assignments.
2411 This could get expensive if the assignment chains are long. Maybe
2412 we should throttle the number of iterations, possibly based on
2413 the optimization level or flag_expensive_optimizations.
2415 We could propagate more information in the first pass by making use
2416 of DF_REG_DEF_COUNT to determine immediately that the alias information
2417 for a pseudo is "constant".
2419 A program with an uninitialized variable can cause an infinite loop
2420 here. Instead of doing a full dataflow analysis to detect such problems
2421 we just cap the number of iterations for the loop.
2423 The state of the arrays for the set chain in question does not matter
2424 since the program has undefined behavior. */
2429 /* Assume nothing will change this iteration of the loop. */
2432 /* We want to assign the same IDs each iteration of this loop, so
2433 start counting from zero each iteration of the loop. */
2436 /* We're at the start of the function each iteration through the
2437 loop, so we're copying arguments. */
2438 copying_arguments
= true;
2440 /* Wipe the potential alias information clean for this pass. */
2441 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
2443 /* Wipe the reg_seen array clean. */
2444 memset (reg_seen
, 0, maxreg
);
2446 /* Mark all hard registers which may contain an address.
2447 The stack, frame and argument pointers may contain an address.
2448 An argument register which can hold a Pmode value may contain
2449 an address even if it is not in BASE_REGS.
2451 The address expression is VOIDmode for an argument and
2452 Pmode for other registers. */
2454 memcpy (new_reg_base_value
, static_reg_base_value
,
2455 FIRST_PSEUDO_REGISTER
* sizeof (rtx
));
2457 /* Walk the insns adding values to the new_reg_base_value array. */
2458 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2464 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2465 /* The prologue/epilogue insns are not threaded onto the
2466 insn chain until after reload has completed. Thus,
2467 there is no sense wasting time checking if INSN is in
2468 the prologue/epilogue until after reload has completed. */
2469 if (reload_completed
2470 && prologue_epilogue_contains (insn
))
2474 /* If this insn has a noalias note, process it, Otherwise,
2475 scan for sets. A simple set will have no side effects
2476 which could change the base value of any other register. */
2478 if (GET_CODE (PATTERN (insn
)) == SET
2479 && REG_NOTES (insn
) != 0
2480 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2481 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2483 note_stores (PATTERN (insn
), record_set
, NULL
);
2485 set
= single_set (insn
);
2488 && REG_P (SET_DEST (set
))
2489 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2491 unsigned int regno
= REGNO (SET_DEST (set
));
2492 rtx src
= SET_SRC (set
);
2495 note
= find_reg_equal_equiv_note (insn
);
2496 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
2497 && DF_REG_DEF_COUNT (regno
) != 1)
2500 if (note
!= NULL_RTX
2501 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2502 && ! rtx_varies_p (XEXP (note
, 0), 1)
2503 && ! reg_overlap_mentioned_p (SET_DEST (set
),
2506 set_reg_known_value (regno
, XEXP (note
, 0));
2507 set_reg_known_equiv_p (regno
,
2508 REG_NOTE_KIND (note
) == REG_EQUIV
);
2510 else if (DF_REG_DEF_COUNT (regno
) == 1
2511 && GET_CODE (src
) == PLUS
2512 && REG_P (XEXP (src
, 0))
2513 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
2514 && GET_CODE (XEXP (src
, 1)) == CONST_INT
)
2516 t
= plus_constant (t
, INTVAL (XEXP (src
, 1)));
2517 set_reg_known_value (regno
, t
);
2518 set_reg_known_equiv_p (regno
, 0);
2520 else if (DF_REG_DEF_COUNT (regno
) == 1
2521 && ! rtx_varies_p (src
, 1))
2523 set_reg_known_value (regno
, src
);
2524 set_reg_known_equiv_p (regno
, 0);
2528 else if (NOTE_P (insn
)
2529 && NOTE_KIND (insn
) == NOTE_INSN_FUNCTION_BEG
)
2530 copying_arguments
= false;
2533 /* Now propagate values from new_reg_base_value to reg_base_value. */
2534 gcc_assert (maxreg
== (unsigned int) max_reg_num ());
2536 for (ui
= 0; ui
< maxreg
; ui
++)
2538 if (new_reg_base_value
[ui
]
2539 && new_reg_base_value
[ui
] != VEC_index (rtx
, reg_base_value
, ui
)
2540 && ! rtx_equal_p (new_reg_base_value
[ui
],
2541 VEC_index (rtx
, reg_base_value
, ui
)))
2543 VEC_replace (rtx
, reg_base_value
, ui
, new_reg_base_value
[ui
]);
2548 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2550 /* Fill in the remaining entries. */
2551 for (i
= 0; i
< (int)reg_known_value_size
; i
++)
2552 if (reg_known_value
[i
] == 0)
2553 reg_known_value
[i
] = regno_reg_rtx
[i
+ FIRST_PSEUDO_REGISTER
];
2556 free (new_reg_base_value
);
2557 new_reg_base_value
= 0;
2560 timevar_pop (TV_ALIAS_ANALYSIS
);
2564 end_alias_analysis (void)
2566 old_reg_base_value
= reg_base_value
;
2567 ggc_free (reg_known_value
);
2568 reg_known_value
= 0;
2569 reg_known_value_size
= 0;
2570 free (reg_known_equiv_p
);
2571 reg_known_equiv_p
= 0;
2574 #include "gt-alias.h"