1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
3 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, 59 Temple Place - Suite 330, 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"
48 /* The alias sets assigned to MEMs assist the back-end in determining
49 which MEMs can alias which other MEMs. In general, two MEMs in
50 different alias sets cannot alias each other, with one important
51 exception. Consider something like:
53 struct S { int i; double d; };
55 a store to an `S' can alias something of either type `int' or type
56 `double'. (However, a store to an `int' cannot alias a `double'
57 and vice versa.) We indicate this via a tree structure that looks
65 (The arrows are directed and point downwards.)
66 In this situation we say the alias set for `struct S' is the
67 `superset' and that those for `int' and `double' are `subsets'.
69 To see whether two alias sets can point to the same memory, we must
70 see if either alias set is a subset of the other. We need not trace
71 past immediate descendants, however, since we propagate all
72 grandchildren up one level.
74 Alias set zero is implicitly a superset of all other alias sets.
75 However, this is no actual entry for alias set zero. It is an
76 error to attempt to explicitly construct a subset of zero. */
78 struct alias_set_entry
GTY(())
80 /* The alias set number, as stored in MEM_ALIAS_SET. */
81 HOST_WIDE_INT alias_set
;
83 /* The children of the alias set. These are not just the immediate
84 children, but, in fact, all descendants. So, if we have:
86 struct T { struct S s; float f; }
88 continuing our example above, the children here will be all of
89 `int', `double', `float', and `struct S'. */
90 splay_tree
GTY((param1_is (int), param2_is (int))) children
;
92 /* Nonzero if would have a child of zero: this effectively makes this
93 alias set the same as alias set zero. */
96 typedef struct alias_set_entry
*alias_set_entry
;
98 static int rtx_equal_for_memref_p (rtx
, rtx
);
99 static rtx
find_symbolic_term (rtx
);
100 static int memrefs_conflict_p (int, rtx
, int, rtx
, HOST_WIDE_INT
);
101 static void record_set (rtx
, rtx
, void *);
102 static int base_alias_check (rtx
, rtx
, enum machine_mode
,
104 static rtx
find_base_value (rtx
);
105 static int mems_in_disjoint_alias_sets_p (rtx
, rtx
);
106 static int insert_subset_children (splay_tree_node
, void*);
107 static tree
find_base_decl (tree
);
108 static alias_set_entry
get_alias_set_entry (HOST_WIDE_INT
);
109 static rtx
fixed_scalar_and_varying_struct_p (rtx
, rtx
, rtx
, rtx
,
111 static int aliases_everything_p (rtx
);
112 static bool nonoverlapping_component_refs_p (tree
, tree
);
113 static tree
decl_for_component_ref (tree
);
114 static rtx
adjust_offset_for_component_ref (tree
, rtx
);
115 static int nonoverlapping_memrefs_p (rtx
, rtx
);
116 static int write_dependence_p (rtx
, rtx
, int);
118 static int nonlocal_mentioned_p_1 (rtx
*, void *);
119 static int nonlocal_mentioned_p (rtx
);
120 static int nonlocal_referenced_p_1 (rtx
*, void *);
121 static int nonlocal_referenced_p (rtx
);
122 static int nonlocal_set_p_1 (rtx
*, void *);
123 static int nonlocal_set_p (rtx
);
124 static void memory_modified_1 (rtx
, rtx
, void *);
125 static void record_alias_subset (HOST_WIDE_INT
, HOST_WIDE_INT
);
127 /* Set up all info needed to perform alias analysis on memory references. */
129 /* Returns the size in bytes of the mode of X. */
130 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
132 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
133 different alias sets. We ignore alias sets in functions making use
134 of variable arguments because the va_arg macros on some systems are
136 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
137 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
139 /* Cap the number of passes we make over the insns propagating alias
140 information through set chains. 10 is a completely arbitrary choice. */
141 #define MAX_ALIAS_LOOP_PASSES 10
143 /* reg_base_value[N] gives an address to which register N is related.
144 If all sets after the first add or subtract to the current value
145 or otherwise modify it so it does not point to a different top level
146 object, reg_base_value[N] is equal to the address part of the source
149 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
150 expressions represent certain special values: function arguments and
151 the stack, frame, and argument pointers.
153 The contents of an ADDRESS is not normally used, the mode of the
154 ADDRESS determines whether the ADDRESS is a function argument or some
155 other special value. Pointer equality, not rtx_equal_p, determines whether
156 two ADDRESS expressions refer to the same base address.
158 The only use of the contents of an ADDRESS is for determining if the
159 current function performs nonlocal memory memory references for the
160 purposes of marking the function as a constant function. */
162 static GTY(()) varray_type reg_base_value
;
163 static rtx
*new_reg_base_value
;
165 /* We preserve the copy of old array around to avoid amount of garbage
166 produced. About 8% of garbage produced were attributed to this
168 static GTY((deletable
)) varray_type old_reg_base_value
;
170 /* Static hunks of RTL used by the aliasing code; these are initialized
171 once per function to avoid unnecessary RTL allocations. */
172 static GTY (()) rtx static_reg_base_value
[FIRST_PSEUDO_REGISTER
];
174 #define REG_BASE_VALUE(X) \
175 (reg_base_value && REGNO (X) < VARRAY_SIZE (reg_base_value) \
176 ? VARRAY_RTX (reg_base_value, REGNO (X)) : 0)
178 /* Vector of known invariant relationships between registers. Set in
179 loop unrolling. Indexed by register number, if nonzero the value
180 is an expression describing this register in terms of another.
182 The length of this array is REG_BASE_VALUE_SIZE.
184 Because this array contains only pseudo registers it has no effect
186 static GTY((length("alias_invariant_size"))) rtx
*alias_invariant
;
187 static GTY(()) unsigned int alias_invariant_size
;
189 /* Vector indexed by N giving the initial (unchanging) value known for
190 pseudo-register N. This array is initialized in init_alias_analysis,
191 and does not change until end_alias_analysis is called. */
192 static GTY((length("reg_known_value_size"))) rtx
*reg_known_value
;
194 /* Indicates number of valid entries in reg_known_value. */
195 static GTY(()) unsigned int reg_known_value_size
;
197 /* Vector recording for each reg_known_value whether it is due to a
198 REG_EQUIV note. Future passes (viz., reload) may replace the
199 pseudo with the equivalent expression and so we account for the
200 dependences that would be introduced if that happens.
202 The REG_EQUIV notes created in assign_parms may mention the arg
203 pointer, and there are explicit insns in the RTL that modify the
204 arg pointer. Thus we must ensure that such insns don't get
205 scheduled across each other because that would invalidate the
206 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
207 wrong, but solving the problem in the scheduler will likely give
208 better code, so we do it here. */
209 static bool *reg_known_equiv_p
;
211 /* True when scanning insns from the start of the rtl to the
212 NOTE_INSN_FUNCTION_BEG note. */
213 static bool copying_arguments
;
215 /* The splay-tree used to store the various alias set entries. */
216 static GTY ((param_is (struct alias_set_entry
))) varray_type alias_sets
;
218 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
219 such an entry, or NULL otherwise. */
221 static inline alias_set_entry
222 get_alias_set_entry (HOST_WIDE_INT alias_set
)
224 return (alias_set_entry
)VARRAY_GENERIC_PTR (alias_sets
, alias_set
);
227 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
228 the two MEMs cannot alias each other. */
231 mems_in_disjoint_alias_sets_p (rtx mem1
, rtx mem2
)
233 /* Perform a basic sanity check. Namely, that there are no alias sets
234 if we're not using strict aliasing. This helps to catch bugs
235 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
236 where a MEM is allocated in some way other than by the use of
237 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
238 use alias sets to indicate that spilled registers cannot alias each
239 other, we might need to remove this check. */
240 gcc_assert (flag_strict_aliasing
241 || (!MEM_ALIAS_SET (mem1
) && !MEM_ALIAS_SET (mem2
)));
243 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
246 /* Insert the NODE into the splay tree given by DATA. Used by
247 record_alias_subset via splay_tree_foreach. */
250 insert_subset_children (splay_tree_node node
, void *data
)
252 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
257 /* Return 1 if the two specified alias sets may conflict. */
260 alias_sets_conflict_p (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
264 /* If have no alias set information for one of the operands, we have
265 to assume it can alias anything. */
266 if (set1
== 0 || set2
== 0
267 /* If the two alias sets are the same, they may alias. */
271 /* See if the first alias set is a subset of the second. */
272 ase
= get_alias_set_entry (set1
);
274 && (ase
->has_zero_child
275 || splay_tree_lookup (ase
->children
,
276 (splay_tree_key
) set2
)))
279 /* Now do the same, but with the alias sets reversed. */
280 ase
= get_alias_set_entry (set2
);
282 && (ase
->has_zero_child
283 || splay_tree_lookup (ase
->children
,
284 (splay_tree_key
) set1
)))
287 /* The two alias sets are distinct and neither one is the
288 child of the other. Therefore, they cannot alias. */
292 /* Return 1 if the two specified alias sets might conflict, or if any subtype
293 of these alias sets might conflict. */
296 alias_sets_might_conflict_p (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
298 if (set1
== 0 || set2
== 0 || set1
== set2
)
305 /* Return 1 if any MEM object of type T1 will always conflict (using the
306 dependency routines in this file) with any MEM object of type T2.
307 This is used when allocating temporary storage. If T1 and/or T2 are
308 NULL_TREE, it means we know nothing about the storage. */
311 objects_must_conflict_p (tree t1
, tree t2
)
313 HOST_WIDE_INT set1
, set2
;
315 /* If neither has a type specified, we don't know if they'll conflict
316 because we may be using them to store objects of various types, for
317 example the argument and local variables areas of inlined functions. */
318 if (t1
== 0 && t2
== 0)
321 /* If they are the same type, they must conflict. */
323 /* Likewise if both are volatile. */
324 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
327 set1
= t1
? get_alias_set (t1
) : 0;
328 set2
= t2
? get_alias_set (t2
) : 0;
330 /* Otherwise they conflict if they have no alias set or the same. We
331 can't simply use alias_sets_conflict_p here, because we must make
332 sure that every subtype of t1 will conflict with every subtype of
333 t2 for which a pair of subobjects of these respective subtypes
334 overlaps on the stack. */
335 return set1
== 0 || set2
== 0 || set1
== set2
;
338 /* T is an expression with pointer type. Find the DECL on which this
339 expression is based. (For example, in `a[i]' this would be `a'.)
340 If there is no such DECL, or a unique decl cannot be determined,
341 NULL_TREE is returned. */
344 find_base_decl (tree t
)
348 if (t
== 0 || t
== error_mark_node
|| ! POINTER_TYPE_P (TREE_TYPE (t
)))
351 /* If this is a declaration, return it. */
355 /* Handle general expressions. It would be nice to deal with
356 COMPONENT_REFs here. If we could tell that `a' and `b' were the
357 same, then `a->f' and `b->f' are also the same. */
358 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
361 return find_base_decl (TREE_OPERAND (t
, 0));
364 /* Return 0 if found in neither or both are the same. */
365 d0
= find_base_decl (TREE_OPERAND (t
, 0));
366 d1
= find_base_decl (TREE_OPERAND (t
, 1));
381 /* Return 1 if all the nested component references handled by
382 get_inner_reference in T are such that we can address the object in T. */
385 can_address_p (tree t
)
389 /* If we're at the end, it is vacuously addressable. */
390 if (!handled_component_p (t
))
393 switch (TREE_CODE (t
))
396 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
401 case ARRAY_RANGE_REF
:
402 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
411 /* Bitfields and casts are never addressable. */
415 t
= TREE_OPERAND (t
, 0);
419 /* Return the alias set for T, which may be either a type or an
420 expression. Call language-specific routine for help, if needed. */
423 get_alias_set (tree t
)
427 /* If we're not doing any alias analysis, just assume everything
428 aliases everything else. Also return 0 if this or its type is
430 if (! flag_strict_aliasing
|| t
== error_mark_node
432 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
435 /* We can be passed either an expression or a type. This and the
436 language-specific routine may make mutually-recursive calls to each other
437 to figure out what to do. At each juncture, we see if this is a tree
438 that the language may need to handle specially. First handle things that
444 /* Remove any nops, then give the language a chance to do
445 something with this tree before we look at it. */
447 set
= lang_hooks
.get_alias_set (t
);
451 /* First see if the actual object referenced is an INDIRECT_REF from a
452 restrict-qualified pointer or a "void *". */
453 while (handled_component_p (inner
))
455 inner
= TREE_OPERAND (inner
, 0);
459 /* Check for accesses through restrict-qualified pointers. */
460 if (INDIRECT_REF_P (inner
))
462 tree decl
= find_base_decl (TREE_OPERAND (inner
, 0));
464 if (decl
&& DECL_POINTER_ALIAS_SET_KNOWN_P (decl
))
466 /* If we haven't computed the actual alias set, do it now. */
467 if (DECL_POINTER_ALIAS_SET (decl
) == -2)
469 tree pointed_to_type
= TREE_TYPE (TREE_TYPE (decl
));
471 /* No two restricted pointers can point at the same thing.
472 However, a restricted pointer can point at the same thing
473 as an unrestricted pointer, if that unrestricted pointer
474 is based on the restricted pointer. So, we make the
475 alias set for the restricted pointer a subset of the
476 alias set for the type pointed to by the type of the
478 HOST_WIDE_INT pointed_to_alias_set
479 = get_alias_set (pointed_to_type
);
481 if (pointed_to_alias_set
== 0)
482 /* It's not legal to make a subset of alias set zero. */
483 DECL_POINTER_ALIAS_SET (decl
) = 0;
484 else if (AGGREGATE_TYPE_P (pointed_to_type
))
485 /* For an aggregate, we must treat the restricted
486 pointer the same as an ordinary pointer. If we
487 were to make the type pointed to by the
488 restricted pointer a subset of the pointed-to
489 type, then we would believe that other subsets
490 of the pointed-to type (such as fields of that
491 type) do not conflict with the type pointed to
492 by the restricted pointer. */
493 DECL_POINTER_ALIAS_SET (decl
)
494 = pointed_to_alias_set
;
497 DECL_POINTER_ALIAS_SET (decl
) = new_alias_set ();
498 record_alias_subset (pointed_to_alias_set
,
499 DECL_POINTER_ALIAS_SET (decl
));
503 /* We use the alias set indicated in the declaration. */
504 return DECL_POINTER_ALIAS_SET (decl
);
507 /* If we have an INDIRECT_REF via a void pointer, we don't
508 know anything about what that might alias. Likewise if the
509 pointer is marked that way. */
510 else if (TREE_CODE (TREE_TYPE (inner
)) == VOID_TYPE
511 || (TYPE_REF_CAN_ALIAS_ALL
512 (TREE_TYPE (TREE_OPERAND (inner
, 0)))))
516 /* Otherwise, pick up the outermost object that we could have a pointer
517 to, processing conversions as above. */
518 while (handled_component_p (t
) && ! can_address_p (t
))
520 t
= TREE_OPERAND (t
, 0);
524 /* If we've already determined the alias set for a decl, just return
525 it. This is necessary for C++ anonymous unions, whose component
526 variables don't look like union members (boo!). */
527 if (TREE_CODE (t
) == VAR_DECL
528 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
529 return MEM_ALIAS_SET (DECL_RTL (t
));
531 /* Now all we care about is the type. */
535 /* Variant qualifiers don't affect the alias set, so get the main
536 variant. If this is a type with a known alias set, return it. */
537 t
= TYPE_MAIN_VARIANT (t
);
538 if (TYPE_ALIAS_SET_KNOWN_P (t
))
539 return TYPE_ALIAS_SET (t
);
541 /* See if the language has special handling for this type. */
542 set
= lang_hooks
.get_alias_set (t
);
546 /* There are no objects of FUNCTION_TYPE, so there's no point in
547 using up an alias set for them. (There are, of course, pointers
548 and references to functions, but that's different.) */
549 else if (TREE_CODE (t
) == FUNCTION_TYPE
)
552 /* Unless the language specifies otherwise, let vector types alias
553 their components. This avoids some nasty type punning issues in
554 normal usage. And indeed lets vectors be treated more like an
556 else if (TREE_CODE (t
) == VECTOR_TYPE
)
557 set
= get_alias_set (TREE_TYPE (t
));
560 /* Otherwise make a new alias set for this type. */
561 set
= new_alias_set ();
563 TYPE_ALIAS_SET (t
) = set
;
565 /* If this is an aggregate type, we must record any component aliasing
567 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
568 record_component_aliases (t
);
573 /* Return a brand-new alias set. */
575 static GTY(()) HOST_WIDE_INT last_alias_set
;
580 if (flag_strict_aliasing
)
583 VARRAY_GENERIC_PTR_INIT (alias_sets
, 10, "alias sets");
585 VARRAY_GROW (alias_sets
, last_alias_set
+ 2);
586 return ++last_alias_set
;
592 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
593 not everything that aliases SUPERSET also aliases SUBSET. For example,
594 in C, a store to an `int' can alias a load of a structure containing an
595 `int', and vice versa. But it can't alias a load of a 'double' member
596 of the same structure. Here, the structure would be the SUPERSET and
597 `int' the SUBSET. This relationship is also described in the comment at
598 the beginning of this file.
600 This function should be called only once per SUPERSET/SUBSET pair.
602 It is illegal for SUPERSET to be zero; everything is implicitly a
603 subset of alias set zero. */
606 record_alias_subset (HOST_WIDE_INT superset
, HOST_WIDE_INT subset
)
608 alias_set_entry superset_entry
;
609 alias_set_entry subset_entry
;
611 /* It is possible in complex type situations for both sets to be the same,
612 in which case we can ignore this operation. */
613 if (superset
== subset
)
616 gcc_assert (superset
);
618 superset_entry
= get_alias_set_entry (superset
);
619 if (superset_entry
== 0)
621 /* Create an entry for the SUPERSET, so that we have a place to
622 attach the SUBSET. */
623 superset_entry
= ggc_alloc (sizeof (struct alias_set_entry
));
624 superset_entry
->alias_set
= superset
;
625 superset_entry
->children
626 = splay_tree_new_ggc (splay_tree_compare_ints
);
627 superset_entry
->has_zero_child
= 0;
628 VARRAY_GENERIC_PTR (alias_sets
, superset
) = superset_entry
;
632 superset_entry
->has_zero_child
= 1;
635 subset_entry
= get_alias_set_entry (subset
);
636 /* If there is an entry for the subset, enter all of its children
637 (if they are not already present) as children of the SUPERSET. */
640 if (subset_entry
->has_zero_child
)
641 superset_entry
->has_zero_child
= 1;
643 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
644 superset_entry
->children
);
647 /* Enter the SUBSET itself as a child of the SUPERSET. */
648 splay_tree_insert (superset_entry
->children
,
649 (splay_tree_key
) subset
, 0);
653 /* Record that component types of TYPE, if any, are part of that type for
654 aliasing purposes. For record types, we only record component types
655 for fields that are marked addressable. For array types, we always
656 record the component types, so the front end should not call this
657 function if the individual component aren't addressable. */
660 record_component_aliases (tree type
)
662 HOST_WIDE_INT superset
= get_alias_set (type
);
668 switch (TREE_CODE (type
))
671 if (! TYPE_NONALIASED_COMPONENT (type
))
672 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
677 case QUAL_UNION_TYPE
:
678 /* Recursively record aliases for the base classes, if there are any. */
679 if (TYPE_BINFO (type
))
682 tree binfo
, base_binfo
;
684 for (binfo
= TYPE_BINFO (type
), i
= 0;
685 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
686 record_alias_subset (superset
,
687 get_alias_set (BINFO_TYPE (base_binfo
)));
689 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
690 if (TREE_CODE (field
) == FIELD_DECL
&& ! DECL_NONADDRESSABLE_P (field
))
691 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
695 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
703 /* Allocate an alias set for use in storing and reading from the varargs
706 static GTY(()) HOST_WIDE_INT varargs_set
= -1;
709 get_varargs_alias_set (void)
712 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
713 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
714 consistently use the varargs alias set for loads from the varargs
715 area. So don't use it anywhere. */
718 if (varargs_set
== -1)
719 varargs_set
= new_alias_set ();
725 /* Likewise, but used for the fixed portions of the frame, e.g., register
728 static GTY(()) HOST_WIDE_INT frame_set
= -1;
731 get_frame_alias_set (void)
734 frame_set
= new_alias_set ();
739 /* Inside SRC, the source of a SET, find a base address. */
742 find_base_value (rtx src
)
746 switch (GET_CODE (src
))
754 /* At the start of a function, argument registers have known base
755 values which may be lost later. Returning an ADDRESS
756 expression here allows optimization based on argument values
757 even when the argument registers are used for other purposes. */
758 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
759 return new_reg_base_value
[regno
];
761 /* If a pseudo has a known base value, return it. Do not do this
762 for non-fixed hard regs since it can result in a circular
763 dependency chain for registers which have values at function entry.
765 The test above is not sufficient because the scheduler may move
766 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
767 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
768 && regno
< VARRAY_SIZE (reg_base_value
))
770 /* If we're inside init_alias_analysis, use new_reg_base_value
771 to reduce the number of relaxation iterations. */
772 if (new_reg_base_value
&& new_reg_base_value
[regno
]
773 && REG_N_SETS (regno
) == 1)
774 return new_reg_base_value
[regno
];
776 if (VARRAY_RTX (reg_base_value
, regno
))
777 return VARRAY_RTX (reg_base_value
, regno
);
783 /* Check for an argument passed in memory. Only record in the
784 copying-arguments block; it is too hard to track changes
786 if (copying_arguments
787 && (XEXP (src
, 0) == arg_pointer_rtx
788 || (GET_CODE (XEXP (src
, 0)) == PLUS
789 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
790 return gen_rtx_ADDRESS (VOIDmode
, src
);
795 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
798 /* ... fall through ... */
803 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
805 /* If either operand is a REG that is a known pointer, then it
807 if (REG_P (src_0
) && REG_POINTER (src_0
))
808 return find_base_value (src_0
);
809 if (REG_P (src_1
) && REG_POINTER (src_1
))
810 return find_base_value (src_1
);
812 /* If either operand is a REG, then see if we already have
813 a known value for it. */
816 temp
= find_base_value (src_0
);
823 temp
= find_base_value (src_1
);
828 /* If either base is named object or a special address
829 (like an argument or stack reference), then use it for the
832 && (GET_CODE (src_0
) == SYMBOL_REF
833 || GET_CODE (src_0
) == LABEL_REF
834 || (GET_CODE (src_0
) == ADDRESS
835 && GET_MODE (src_0
) != VOIDmode
)))
839 && (GET_CODE (src_1
) == SYMBOL_REF
840 || GET_CODE (src_1
) == LABEL_REF
841 || (GET_CODE (src_1
) == ADDRESS
842 && GET_MODE (src_1
) != VOIDmode
)))
845 /* Guess which operand is the base address:
846 If either operand is a symbol, then it is the base. If
847 either operand is a CONST_INT, then the other is the base. */
848 if (GET_CODE (src_1
) == CONST_INT
|| CONSTANT_P (src_0
))
849 return find_base_value (src_0
);
850 else if (GET_CODE (src_0
) == CONST_INT
|| CONSTANT_P (src_1
))
851 return find_base_value (src_1
);
857 /* The standard form is (lo_sum reg sym) so look only at the
859 return find_base_value (XEXP (src
, 1));
862 /* If the second operand is constant set the base
863 address to the first operand. */
864 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
865 return find_base_value (XEXP (src
, 0));
869 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
879 return find_base_value (XEXP (src
, 0));
882 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
884 rtx temp
= find_base_value (XEXP (src
, 0));
886 if (temp
!= 0 && CONSTANT_P (temp
))
887 temp
= convert_memory_address (Pmode
, temp
);
899 /* Called from init_alias_analysis indirectly through note_stores. */
901 /* While scanning insns to find base values, reg_seen[N] is nonzero if
902 register N has been set in this function. */
903 static char *reg_seen
;
905 /* Addresses which are known not to alias anything else are identified
906 by a unique integer. */
907 static int unique_id
;
910 record_set (rtx dest
, rtx set
, void *data ATTRIBUTE_UNUSED
)
919 regno
= REGNO (dest
);
921 gcc_assert (regno
< VARRAY_SIZE (reg_base_value
));
923 /* If this spans multiple hard registers, then we must indicate that every
924 register has an unusable value. */
925 if (regno
< FIRST_PSEUDO_REGISTER
)
926 n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
933 reg_seen
[regno
+ n
] = 1;
934 new_reg_base_value
[regno
+ n
] = 0;
941 /* A CLOBBER wipes out any old value but does not prevent a previously
942 unset register from acquiring a base address (i.e. reg_seen is not
944 if (GET_CODE (set
) == CLOBBER
)
946 new_reg_base_value
[regno
] = 0;
955 new_reg_base_value
[regno
] = 0;
959 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
960 GEN_INT (unique_id
++));
964 /* If this is not the first set of REGNO, see whether the new value
965 is related to the old one. There are two cases of interest:
967 (1) The register might be assigned an entirely new value
968 that has the same base term as the original set.
970 (2) The set might be a simple self-modification that
971 cannot change REGNO's base value.
973 If neither case holds, reject the original base value as invalid.
974 Note that the following situation is not detected:
976 extern int x, y; int *p = &x; p += (&y-&x);
978 ANSI C does not allow computing the difference of addresses
979 of distinct top level objects. */
980 if (new_reg_base_value
[regno
] != 0
981 && find_base_value (src
) != new_reg_base_value
[regno
])
982 switch (GET_CODE (src
))
986 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
987 new_reg_base_value
[regno
] = 0;
990 /* If the value we add in the PLUS is also a valid base value,
991 this might be the actual base value, and the original value
994 rtx other
= NULL_RTX
;
996 if (XEXP (src
, 0) == dest
)
997 other
= XEXP (src
, 1);
998 else if (XEXP (src
, 1) == dest
)
999 other
= XEXP (src
, 0);
1001 if (! other
|| find_base_value (other
))
1002 new_reg_base_value
[regno
] = 0;
1006 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
1007 new_reg_base_value
[regno
] = 0;
1010 new_reg_base_value
[regno
] = 0;
1013 /* If this is the first set of a register, record the value. */
1014 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1015 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
1016 new_reg_base_value
[regno
] = find_base_value (src
);
1018 reg_seen
[regno
] = 1;
1021 /* Called from loop optimization when a new pseudo-register is
1022 created. It indicates that REGNO is being set to VAL. f INVARIANT
1023 is true then this value also describes an invariant relationship
1024 which can be used to deduce that two registers with unknown values
1028 record_base_value (unsigned int regno
, rtx val
, int invariant
)
1030 if (invariant
&& alias_invariant
&& regno
< alias_invariant_size
)
1031 alias_invariant
[regno
] = val
;
1033 if (regno
>= VARRAY_SIZE (reg_base_value
))
1034 VARRAY_GROW (reg_base_value
, max_reg_num ());
1038 VARRAY_RTX (reg_base_value
, regno
)
1039 = REG_BASE_VALUE (val
);
1042 VARRAY_RTX (reg_base_value
, regno
)
1043 = find_base_value (val
);
1046 /* Clear alias info for a register. This is used if an RTL transformation
1047 changes the value of a register. This is used in flow by AUTO_INC_DEC
1048 optimizations. We don't need to clear reg_base_value, since flow only
1049 changes the offset. */
1052 clear_reg_alias_info (rtx reg
)
1054 unsigned int regno
= REGNO (reg
);
1056 if (regno
>= FIRST_PSEUDO_REGISTER
)
1058 regno
-= FIRST_PSEUDO_REGISTER
;
1059 if (regno
< reg_known_value_size
)
1061 reg_known_value
[regno
] = reg
;
1062 reg_known_equiv_p
[regno
] = false;
1067 /* If a value is known for REGNO, return it. */
1070 get_reg_known_value (unsigned int regno
)
1072 if (regno
>= FIRST_PSEUDO_REGISTER
)
1074 regno
-= FIRST_PSEUDO_REGISTER
;
1075 if (regno
< reg_known_value_size
)
1076 return reg_known_value
[regno
];
1084 set_reg_known_value (unsigned int regno
, rtx val
)
1086 if (regno
>= FIRST_PSEUDO_REGISTER
)
1088 regno
-= FIRST_PSEUDO_REGISTER
;
1089 if (regno
< reg_known_value_size
)
1090 reg_known_value
[regno
] = val
;
1094 /* Similarly for reg_known_equiv_p. */
1097 get_reg_known_equiv_p (unsigned int regno
)
1099 if (regno
>= FIRST_PSEUDO_REGISTER
)
1101 regno
-= FIRST_PSEUDO_REGISTER
;
1102 if (regno
< reg_known_value_size
)
1103 return reg_known_equiv_p
[regno
];
1109 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1111 if (regno
>= FIRST_PSEUDO_REGISTER
)
1113 regno
-= FIRST_PSEUDO_REGISTER
;
1114 if (regno
< reg_known_value_size
)
1115 reg_known_equiv_p
[regno
] = val
;
1120 /* Returns a canonical version of X, from the point of view alias
1121 analysis. (For example, if X is a MEM whose address is a register,
1122 and the register has a known value (say a SYMBOL_REF), then a MEM
1123 whose address is the SYMBOL_REF is returned.) */
1128 /* Recursively look for equivalences. */
1129 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1131 rtx t
= get_reg_known_value (REGNO (x
));
1135 return canon_rtx (t
);
1138 if (GET_CODE (x
) == PLUS
)
1140 rtx x0
= canon_rtx (XEXP (x
, 0));
1141 rtx x1
= canon_rtx (XEXP (x
, 1));
1143 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1145 if (GET_CODE (x0
) == CONST_INT
)
1146 return plus_constant (x1
, INTVAL (x0
));
1147 else if (GET_CODE (x1
) == CONST_INT
)
1148 return plus_constant (x0
, INTVAL (x1
));
1149 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1153 /* This gives us much better alias analysis when called from
1154 the loop optimizer. Note we want to leave the original
1155 MEM alone, but need to return the canonicalized MEM with
1156 all the flags with their original values. */
1158 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1163 /* Return 1 if X and Y are identical-looking rtx's.
1164 Expect that X and Y has been already canonicalized.
1166 We use the data in reg_known_value above to see if two registers with
1167 different numbers are, in fact, equivalent. */
1170 rtx_equal_for_memref_p (rtx x
, rtx y
)
1177 if (x
== 0 && y
== 0)
1179 if (x
== 0 || y
== 0)
1185 code
= GET_CODE (x
);
1186 /* Rtx's of different codes cannot be equal. */
1187 if (code
!= GET_CODE (y
))
1190 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1191 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1193 if (GET_MODE (x
) != GET_MODE (y
))
1196 /* Some RTL can be compared without a recursive examination. */
1200 return REGNO (x
) == REGNO (y
);
1203 return XEXP (x
, 0) == XEXP (y
, 0);
1206 return XSTR (x
, 0) == XSTR (y
, 0);
1211 /* There's no need to compare the contents of CONST_DOUBLEs or
1212 CONST_INTs because pointer equality is a good enough
1213 comparison for these nodes. */
1220 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1222 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1223 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1224 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1225 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1226 /* For commutative operations, the RTX match if the operand match in any
1227 order. Also handle the simple binary and unary cases without a loop. */
1228 if (COMMUTATIVE_P (x
))
1230 rtx xop0
= canon_rtx (XEXP (x
, 0));
1231 rtx yop0
= canon_rtx (XEXP (y
, 0));
1232 rtx yop1
= canon_rtx (XEXP (y
, 1));
1234 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1235 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1236 || (rtx_equal_for_memref_p (xop0
, yop1
)
1237 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1239 else if (NON_COMMUTATIVE_P (x
))
1241 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1242 canon_rtx (XEXP (y
, 0)))
1243 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1244 canon_rtx (XEXP (y
, 1))));
1246 else if (UNARY_P (x
))
1247 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1248 canon_rtx (XEXP (y
, 0)));
1250 /* Compare the elements. If any pair of corresponding elements
1251 fail to match, return 0 for the whole things.
1253 Limit cases to types which actually appear in addresses. */
1255 fmt
= GET_RTX_FORMAT (code
);
1256 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1261 if (XINT (x
, i
) != XINT (y
, i
))
1266 /* Two vectors must have the same length. */
1267 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1270 /* And the corresponding elements must match. */
1271 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1272 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1273 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1278 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1279 canon_rtx (XEXP (y
, i
))) == 0)
1283 /* This can happen for asm operands. */
1285 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1289 /* This can happen for an asm which clobbers memory. */
1293 /* It is believed that rtx's at this level will never
1294 contain anything but integers and other rtx's,
1295 except for within LABEL_REFs and SYMBOL_REFs. */
1303 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1304 X and return it, or return 0 if none found. */
1307 find_symbolic_term (rtx x
)
1313 code
= GET_CODE (x
);
1314 if (code
== SYMBOL_REF
|| code
== LABEL_REF
)
1319 fmt
= GET_RTX_FORMAT (code
);
1320 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1326 t
= find_symbolic_term (XEXP (x
, i
));
1330 else if (fmt
[i
] == 'E')
1337 find_base_term (rtx x
)
1340 struct elt_loc_list
*l
;
1342 #if defined (FIND_BASE_TERM)
1343 /* Try machine-dependent ways to find the base term. */
1344 x
= FIND_BASE_TERM (x
);
1347 switch (GET_CODE (x
))
1350 return REG_BASE_VALUE (x
);
1353 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1363 return find_base_term (XEXP (x
, 0));
1366 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1368 rtx temp
= find_base_term (XEXP (x
, 0));
1370 if (temp
!= 0 && CONSTANT_P (temp
))
1371 temp
= convert_memory_address (Pmode
, temp
);
1377 val
= CSELIB_VAL_PTR (x
);
1380 for (l
= val
->locs
; l
; l
= l
->next
)
1381 if ((x
= find_base_term (l
->loc
)) != 0)
1387 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1394 rtx tmp1
= XEXP (x
, 0);
1395 rtx tmp2
= XEXP (x
, 1);
1397 /* This is a little bit tricky since we have to determine which of
1398 the two operands represents the real base address. Otherwise this
1399 routine may return the index register instead of the base register.
1401 That may cause us to believe no aliasing was possible, when in
1402 fact aliasing is possible.
1404 We use a few simple tests to guess the base register. Additional
1405 tests can certainly be added. For example, if one of the operands
1406 is a shift or multiply, then it must be the index register and the
1407 other operand is the base register. */
1409 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1410 return find_base_term (tmp2
);
1412 /* If either operand is known to be a pointer, then use it
1413 to determine the base term. */
1414 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1415 return find_base_term (tmp1
);
1417 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1418 return find_base_term (tmp2
);
1420 /* Neither operand was known to be a pointer. Go ahead and find the
1421 base term for both operands. */
1422 tmp1
= find_base_term (tmp1
);
1423 tmp2
= find_base_term (tmp2
);
1425 /* If either base term is named object or a special address
1426 (like an argument or stack reference), then use it for the
1429 && (GET_CODE (tmp1
) == SYMBOL_REF
1430 || GET_CODE (tmp1
) == LABEL_REF
1431 || (GET_CODE (tmp1
) == ADDRESS
1432 && GET_MODE (tmp1
) != VOIDmode
)))
1436 && (GET_CODE (tmp2
) == SYMBOL_REF
1437 || GET_CODE (tmp2
) == LABEL_REF
1438 || (GET_CODE (tmp2
) == ADDRESS
1439 && GET_MODE (tmp2
) != VOIDmode
)))
1442 /* We could not determine which of the two operands was the
1443 base register and which was the index. So we can determine
1444 nothing from the base alias check. */
1449 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
&& INTVAL (XEXP (x
, 1)) != 0)
1450 return find_base_term (XEXP (x
, 0));
1462 /* Return 0 if the addresses X and Y are known to point to different
1463 objects, 1 if they might be pointers to the same object. */
1466 base_alias_check (rtx x
, rtx y
, enum machine_mode x_mode
,
1467 enum machine_mode y_mode
)
1469 rtx x_base
= find_base_term (x
);
1470 rtx y_base
= find_base_term (y
);
1472 /* If the address itself has no known base see if a known equivalent
1473 value has one. If either address still has no known base, nothing
1474 is known about aliasing. */
1479 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1482 x_base
= find_base_term (x_c
);
1490 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1493 y_base
= find_base_term (y_c
);
1498 /* If the base addresses are equal nothing is known about aliasing. */
1499 if (rtx_equal_p (x_base
, y_base
))
1502 /* The base addresses of the read and write are different expressions.
1503 If they are both symbols and they are not accessed via AND, there is
1504 no conflict. We can bring knowledge of object alignment into play
1505 here. For example, on alpha, "char a, b;" can alias one another,
1506 though "char a; long b;" cannot. */
1507 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1509 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1511 if (GET_CODE (x
) == AND
1512 && (GET_CODE (XEXP (x
, 1)) != CONST_INT
1513 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1515 if (GET_CODE (y
) == AND
1516 && (GET_CODE (XEXP (y
, 1)) != CONST_INT
1517 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1519 /* Differing symbols never alias. */
1523 /* If one address is a stack reference there can be no alias:
1524 stack references using different base registers do not alias,
1525 a stack reference can not alias a parameter, and a stack reference
1526 can not alias a global. */
1527 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
1528 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
1531 if (! flag_argument_noalias
)
1534 if (flag_argument_noalias
> 1)
1537 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1538 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
1541 /* Convert the address X into something we can use. This is done by returning
1542 it unchanged unless it is a value; in the latter case we call cselib to get
1543 a more useful rtx. */
1549 struct elt_loc_list
*l
;
1551 if (GET_CODE (x
) != VALUE
)
1553 v
= CSELIB_VAL_PTR (x
);
1556 for (l
= v
->locs
; l
; l
= l
->next
)
1557 if (CONSTANT_P (l
->loc
))
1559 for (l
= v
->locs
; l
; l
= l
->next
)
1560 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
))
1563 return v
->locs
->loc
;
1568 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1569 where SIZE is the size in bytes of the memory reference. If ADDR
1570 is not modified by the memory reference then ADDR is returned. */
1573 addr_side_effect_eval (rtx addr
, int size
, int n_refs
)
1577 switch (GET_CODE (addr
))
1580 offset
= (n_refs
+ 1) * size
;
1583 offset
= -(n_refs
+ 1) * size
;
1586 offset
= n_refs
* size
;
1589 offset
= -n_refs
* size
;
1597 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0),
1600 addr
= XEXP (addr
, 0);
1601 addr
= canon_rtx (addr
);
1606 /* Return nonzero if X and Y (memory addresses) could reference the
1607 same location in memory. C is an offset accumulator. When
1608 C is nonzero, we are testing aliases between X and Y + C.
1609 XSIZE is the size in bytes of the X reference,
1610 similarly YSIZE is the size in bytes for Y.
1611 Expect that canon_rtx has been already called for X and Y.
1613 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1614 referenced (the reference was BLKmode), so make the most pessimistic
1617 If XSIZE or YSIZE is negative, we may access memory outside the object
1618 being referenced as a side effect. This can happen when using AND to
1619 align memory references, as is done on the Alpha.
1621 Nice to notice that varying addresses cannot conflict with fp if no
1622 local variables had their addresses taken, but that's too hard now. */
1625 memrefs_conflict_p (int xsize
, rtx x
, int ysize
, rtx y
, HOST_WIDE_INT c
)
1627 if (GET_CODE (x
) == VALUE
)
1629 if (GET_CODE (y
) == VALUE
)
1631 if (GET_CODE (x
) == HIGH
)
1633 else if (GET_CODE (x
) == LO_SUM
)
1636 x
= addr_side_effect_eval (x
, xsize
, 0);
1637 if (GET_CODE (y
) == HIGH
)
1639 else if (GET_CODE (y
) == LO_SUM
)
1642 y
= addr_side_effect_eval (y
, ysize
, 0);
1644 if (rtx_equal_for_memref_p (x
, y
))
1646 if (xsize
<= 0 || ysize
<= 0)
1648 if (c
>= 0 && xsize
> c
)
1650 if (c
< 0 && ysize
+c
> 0)
1655 /* This code used to check for conflicts involving stack references and
1656 globals but the base address alias code now handles these cases. */
1658 if (GET_CODE (x
) == PLUS
)
1660 /* The fact that X is canonicalized means that this
1661 PLUS rtx is canonicalized. */
1662 rtx x0
= XEXP (x
, 0);
1663 rtx x1
= XEXP (x
, 1);
1665 if (GET_CODE (y
) == PLUS
)
1667 /* The fact that Y is canonicalized means that this
1668 PLUS rtx is canonicalized. */
1669 rtx y0
= XEXP (y
, 0);
1670 rtx y1
= XEXP (y
, 1);
1672 if (rtx_equal_for_memref_p (x1
, y1
))
1673 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1674 if (rtx_equal_for_memref_p (x0
, y0
))
1675 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
1676 if (GET_CODE (x1
) == CONST_INT
)
1678 if (GET_CODE (y1
) == CONST_INT
)
1679 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
1680 c
- INTVAL (x1
) + INTVAL (y1
));
1682 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
1685 else if (GET_CODE (y1
) == CONST_INT
)
1686 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1690 else if (GET_CODE (x1
) == CONST_INT
)
1691 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
1693 else if (GET_CODE (y
) == PLUS
)
1695 /* The fact that Y is canonicalized means that this
1696 PLUS rtx is canonicalized. */
1697 rtx y0
= XEXP (y
, 0);
1698 rtx y1
= XEXP (y
, 1);
1700 if (GET_CODE (y1
) == CONST_INT
)
1701 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1706 if (GET_CODE (x
) == GET_CODE (y
))
1707 switch (GET_CODE (x
))
1711 /* Handle cases where we expect the second operands to be the
1712 same, and check only whether the first operand would conflict
1715 rtx x1
= canon_rtx (XEXP (x
, 1));
1716 rtx y1
= canon_rtx (XEXP (y
, 1));
1717 if (! rtx_equal_for_memref_p (x1
, y1
))
1719 x0
= canon_rtx (XEXP (x
, 0));
1720 y0
= canon_rtx (XEXP (y
, 0));
1721 if (rtx_equal_for_memref_p (x0
, y0
))
1722 return (xsize
== 0 || ysize
== 0
1723 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1725 /* Can't properly adjust our sizes. */
1726 if (GET_CODE (x1
) != CONST_INT
)
1728 xsize
/= INTVAL (x1
);
1729 ysize
/= INTVAL (x1
);
1731 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1735 /* Are these registers known not to be equal? */
1736 if (alias_invariant
)
1738 unsigned int r_x
= REGNO (x
), r_y
= REGNO (y
);
1739 rtx i_x
, i_y
; /* invariant relationships of X and Y */
1741 i_x
= r_x
>= alias_invariant_size
? 0 : alias_invariant
[r_x
];
1742 i_y
= r_y
>= alias_invariant_size
? 0 : alias_invariant
[r_y
];
1744 if (i_x
== 0 && i_y
== 0)
1747 if (! memrefs_conflict_p (xsize
, i_x
? i_x
: x
,
1748 ysize
, i_y
? i_y
: y
, c
))
1757 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1758 as an access with indeterminate size. Assume that references
1759 besides AND are aligned, so if the size of the other reference is
1760 at least as large as the alignment, assume no other overlap. */
1761 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1763 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1765 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)), ysize
, y
, c
);
1767 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1769 /* ??? If we are indexing far enough into the array/structure, we
1770 may yet be able to determine that we can not overlap. But we
1771 also need to that we are far enough from the end not to overlap
1772 a following reference, so we do nothing with that for now. */
1773 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1775 return memrefs_conflict_p (xsize
, x
, ysize
, canon_rtx (XEXP (y
, 0)), c
);
1780 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1782 c
+= (INTVAL (y
) - INTVAL (x
));
1783 return (xsize
<= 0 || ysize
<= 0
1784 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1787 if (GET_CODE (x
) == CONST
)
1789 if (GET_CODE (y
) == CONST
)
1790 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1791 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1793 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1796 if (GET_CODE (y
) == CONST
)
1797 return memrefs_conflict_p (xsize
, x
, ysize
,
1798 canon_rtx (XEXP (y
, 0)), c
);
1801 return (xsize
<= 0 || ysize
<= 0
1802 || (rtx_equal_for_memref_p (x
, y
)
1803 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1810 /* Functions to compute memory dependencies.
1812 Since we process the insns in execution order, we can build tables
1813 to keep track of what registers are fixed (and not aliased), what registers
1814 are varying in known ways, and what registers are varying in unknown
1817 If both memory references are volatile, then there must always be a
1818 dependence between the two references, since their order can not be
1819 changed. A volatile and non-volatile reference can be interchanged
1822 A MEM_IN_STRUCT reference at a non-AND varying address can never
1823 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1824 also must allow AND addresses, because they may generate accesses
1825 outside the object being referenced. This is used to generate
1826 aligned addresses from unaligned addresses, for instance, the alpha
1827 storeqi_unaligned pattern. */
1829 /* Read dependence: X is read after read in MEM takes place. There can
1830 only be a dependence here if both reads are volatile. */
1833 read_dependence (rtx mem
, rtx x
)
1835 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1838 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1839 MEM2 is a reference to a structure at a varying address, or returns
1840 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1841 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1842 to decide whether or not an address may vary; it should return
1843 nonzero whenever variation is possible.
1844 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1847 fixed_scalar_and_varying_struct_p (rtx mem1
, rtx mem2
, rtx mem1_addr
,
1849 int (*varies_p
) (rtx
, int))
1851 if (! flag_strict_aliasing
)
1854 if (MEM_SCALAR_P (mem1
) && MEM_IN_STRUCT_P (mem2
)
1855 && !varies_p (mem1_addr
, 1) && varies_p (mem2_addr
, 1))
1856 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1860 if (MEM_IN_STRUCT_P (mem1
) && MEM_SCALAR_P (mem2
)
1861 && varies_p (mem1_addr
, 1) && !varies_p (mem2_addr
, 1))
1862 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1869 /* Returns nonzero if something about the mode or address format MEM1
1870 indicates that it might well alias *anything*. */
1873 aliases_everything_p (rtx mem
)
1875 if (GET_CODE (XEXP (mem
, 0)) == AND
)
1876 /* If the address is an AND, its very hard to know at what it is
1877 actually pointing. */
1883 /* Return true if we can determine that the fields referenced cannot
1884 overlap for any pair of objects. */
1887 nonoverlapping_component_refs_p (tree x
, tree y
)
1889 tree fieldx
, fieldy
, typex
, typey
, orig_y
;
1893 /* The comparison has to be done at a common type, since we don't
1894 know how the inheritance hierarchy works. */
1898 fieldx
= TREE_OPERAND (x
, 1);
1899 typex
= DECL_FIELD_CONTEXT (fieldx
);
1904 fieldy
= TREE_OPERAND (y
, 1);
1905 typey
= DECL_FIELD_CONTEXT (fieldy
);
1910 y
= TREE_OPERAND (y
, 0);
1912 while (y
&& TREE_CODE (y
) == COMPONENT_REF
);
1914 x
= TREE_OPERAND (x
, 0);
1916 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1918 /* Never found a common type. */
1922 /* If we're left with accessing different fields of a structure,
1924 if (TREE_CODE (typex
) == RECORD_TYPE
1925 && fieldx
!= fieldy
)
1928 /* The comparison on the current field failed. If we're accessing
1929 a very nested structure, look at the next outer level. */
1930 x
= TREE_OPERAND (x
, 0);
1931 y
= TREE_OPERAND (y
, 0);
1934 && TREE_CODE (x
) == COMPONENT_REF
1935 && TREE_CODE (y
) == COMPONENT_REF
);
1940 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1943 decl_for_component_ref (tree x
)
1947 x
= TREE_OPERAND (x
, 0);
1949 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1951 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
1954 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1955 offset of the field reference. */
1958 adjust_offset_for_component_ref (tree x
, rtx offset
)
1960 HOST_WIDE_INT ioffset
;
1965 ioffset
= INTVAL (offset
);
1968 tree offset
= component_ref_field_offset (x
);
1969 tree field
= TREE_OPERAND (x
, 1);
1971 if (! host_integerp (offset
, 1))
1973 ioffset
+= (tree_low_cst (offset
, 1)
1974 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 1)
1977 x
= TREE_OPERAND (x
, 0);
1979 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1981 return GEN_INT (ioffset
);
1984 /* Return nonzero if we can determine the exprs corresponding to memrefs
1985 X and Y and they do not overlap. */
1988 nonoverlapping_memrefs_p (rtx x
, rtx y
)
1990 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
1993 rtx moffsetx
, moffsety
;
1994 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
1996 /* Unless both have exprs, we can't tell anything. */
1997 if (exprx
== 0 || expry
== 0)
2000 /* If both are field references, we may be able to determine something. */
2001 if (TREE_CODE (exprx
) == COMPONENT_REF
2002 && TREE_CODE (expry
) == COMPONENT_REF
2003 && nonoverlapping_component_refs_p (exprx
, expry
))
2006 /* If the field reference test failed, look at the DECLs involved. */
2007 moffsetx
= MEM_OFFSET (x
);
2008 if (TREE_CODE (exprx
) == COMPONENT_REF
)
2010 tree t
= decl_for_component_ref (exprx
);
2013 moffsetx
= adjust_offset_for_component_ref (exprx
, moffsetx
);
2016 else if (INDIRECT_REF_P (exprx
))
2018 exprx
= TREE_OPERAND (exprx
, 0);
2019 if (flag_argument_noalias
< 2
2020 || TREE_CODE (exprx
) != PARM_DECL
)
2024 moffsety
= MEM_OFFSET (y
);
2025 if (TREE_CODE (expry
) == COMPONENT_REF
)
2027 tree t
= decl_for_component_ref (expry
);
2030 moffsety
= adjust_offset_for_component_ref (expry
, moffsety
);
2033 else if (INDIRECT_REF_P (expry
))
2035 expry
= TREE_OPERAND (expry
, 0);
2036 if (flag_argument_noalias
< 2
2037 || TREE_CODE (expry
) != PARM_DECL
)
2041 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2044 rtlx
= DECL_RTL (exprx
);
2045 rtly
= DECL_RTL (expry
);
2047 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2048 can't overlap unless they are the same because we never reuse that part
2049 of the stack frame used for locals for spilled pseudos. */
2050 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2051 && ! rtx_equal_p (rtlx
, rtly
))
2054 /* Get the base and offsets of both decls. If either is a register, we
2055 know both are and are the same, so use that as the base. The only
2056 we can avoid overlap is if we can deduce that they are nonoverlapping
2057 pieces of that decl, which is very rare. */
2058 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2059 if (GET_CODE (basex
) == PLUS
&& GET_CODE (XEXP (basex
, 1)) == CONST_INT
)
2060 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2062 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2063 if (GET_CODE (basey
) == PLUS
&& GET_CODE (XEXP (basey
, 1)) == CONST_INT
)
2064 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2066 /* If the bases are different, we know they do not overlap if both
2067 are constants or if one is a constant and the other a pointer into the
2068 stack frame. Otherwise a different base means we can't tell if they
2070 if (! rtx_equal_p (basex
, basey
))
2071 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2072 || (CONSTANT_P (basex
) && REG_P (basey
)
2073 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2074 || (CONSTANT_P (basey
) && REG_P (basex
)
2075 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2077 sizex
= (!MEM_P (rtlx
) ? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2078 : MEM_SIZE (rtlx
) ? INTVAL (MEM_SIZE (rtlx
))
2080 sizey
= (!MEM_P (rtly
) ? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2081 : MEM_SIZE (rtly
) ? INTVAL (MEM_SIZE (rtly
)) :
2084 /* If we have an offset for either memref, it can update the values computed
2087 offsetx
+= INTVAL (moffsetx
), sizex
-= INTVAL (moffsetx
);
2089 offsety
+= INTVAL (moffsety
), sizey
-= INTVAL (moffsety
);
2091 /* If a memref has both a size and an offset, we can use the smaller size.
2092 We can't do this if the offset isn't known because we must view this
2093 memref as being anywhere inside the DECL's MEM. */
2094 if (MEM_SIZE (x
) && moffsetx
)
2095 sizex
= INTVAL (MEM_SIZE (x
));
2096 if (MEM_SIZE (y
) && moffsety
)
2097 sizey
= INTVAL (MEM_SIZE (y
));
2099 /* Put the values of the memref with the lower offset in X's values. */
2100 if (offsetx
> offsety
)
2102 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2103 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2106 /* If we don't know the size of the lower-offset value, we can't tell
2107 if they conflict. Otherwise, we do the test. */
2108 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2111 /* True dependence: X is read after store in MEM takes place. */
2114 true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx x
,
2115 int (*varies
) (rtx
, int))
2117 rtx x_addr
, mem_addr
;
2120 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2123 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2124 This is used in epilogue deallocation functions. */
2125 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2127 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2130 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2133 /* Read-only memory is by definition never modified, and therefore can't
2134 conflict with anything. We don't expect to find read-only set on MEM,
2135 but stupid user tricks can produce them, so don't abort. */
2136 if (MEM_READONLY_P (x
))
2139 if (nonoverlapping_memrefs_p (mem
, x
))
2142 if (mem_mode
== VOIDmode
)
2143 mem_mode
= GET_MODE (mem
);
2145 x_addr
= get_addr (XEXP (x
, 0));
2146 mem_addr
= get_addr (XEXP (mem
, 0));
2148 base
= find_base_term (x_addr
);
2149 if (base
&& (GET_CODE (base
) == LABEL_REF
2150 || (GET_CODE (base
) == SYMBOL_REF
2151 && CONSTANT_POOL_ADDRESS_P (base
))))
2154 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2157 x_addr
= canon_rtx (x_addr
);
2158 mem_addr
= canon_rtx (mem_addr
);
2160 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2161 SIZE_FOR_MODE (x
), x_addr
, 0))
2164 if (aliases_everything_p (x
))
2167 /* We cannot use aliases_everything_p to test MEM, since we must look
2168 at MEM_MODE, rather than GET_MODE (MEM). */
2169 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2172 /* In true_dependence we also allow BLKmode to alias anything. Why
2173 don't we do this in anti_dependence and output_dependence? */
2174 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2177 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2181 /* Canonical true dependence: X is read after store in MEM takes place.
2182 Variant of true_dependence which assumes MEM has already been
2183 canonicalized (hence we no longer do that here).
2184 The mem_addr argument has been added, since true_dependence computed
2185 this value prior to canonicalizing. */
2188 canon_true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx mem_addr
,
2189 rtx x
, int (*varies
) (rtx
, int))
2193 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2196 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2197 This is used in epilogue deallocation functions. */
2198 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2200 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2203 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2206 /* Read-only memory is by definition never modified, and therefore can't
2207 conflict with anything. We don't expect to find read-only set on MEM,
2208 but stupid user tricks can produce them, so don't abort. */
2209 if (MEM_READONLY_P (x
))
2212 if (nonoverlapping_memrefs_p (x
, mem
))
2215 x_addr
= get_addr (XEXP (x
, 0));
2217 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2220 x_addr
= canon_rtx (x_addr
);
2221 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2222 SIZE_FOR_MODE (x
), x_addr
, 0))
2225 if (aliases_everything_p (x
))
2228 /* We cannot use aliases_everything_p to test MEM, since we must look
2229 at MEM_MODE, rather than GET_MODE (MEM). */
2230 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2233 /* In true_dependence we also allow BLKmode to alias anything. Why
2234 don't we do this in anti_dependence and output_dependence? */
2235 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2238 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2242 /* Returns nonzero if a write to X might alias a previous read from
2243 (or, if WRITEP is nonzero, a write to) MEM. */
2246 write_dependence_p (rtx mem
, rtx x
, int writep
)
2248 rtx x_addr
, mem_addr
;
2252 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2255 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2256 This is used in epilogue deallocation functions. */
2257 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2259 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2262 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2265 /* A read from read-only memory can't conflict with read-write memory. */
2266 if (!writep
&& MEM_READONLY_P (mem
))
2269 if (nonoverlapping_memrefs_p (x
, mem
))
2272 x_addr
= get_addr (XEXP (x
, 0));
2273 mem_addr
= get_addr (XEXP (mem
, 0));
2277 base
= find_base_term (mem_addr
);
2278 if (base
&& (GET_CODE (base
) == LABEL_REF
2279 || (GET_CODE (base
) == SYMBOL_REF
2280 && CONSTANT_POOL_ADDRESS_P (base
))))
2284 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
2288 x_addr
= canon_rtx (x_addr
);
2289 mem_addr
= canon_rtx (mem_addr
);
2291 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2292 SIZE_FOR_MODE (x
), x_addr
, 0))
2296 = fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2299 return (!(fixed_scalar
== mem
&& !aliases_everything_p (x
))
2300 && !(fixed_scalar
== x
&& !aliases_everything_p (mem
)));
2303 /* Anti dependence: X is written after read in MEM takes place. */
2306 anti_dependence (rtx mem
, rtx x
)
2308 return write_dependence_p (mem
, x
, /*writep=*/0);
2311 /* Output dependence: X is written after store in MEM takes place. */
2314 output_dependence (rtx mem
, rtx x
)
2316 return write_dependence_p (mem
, x
, /*writep=*/1);
2319 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2320 something which is not local to the function and is not constant. */
2323 nonlocal_mentioned_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2332 switch (GET_CODE (x
))
2335 if (REG_P (SUBREG_REG (x
)))
2337 /* Global registers are not local. */
2338 if (REGNO (SUBREG_REG (x
)) < FIRST_PSEUDO_REGISTER
2339 && global_regs
[subreg_regno (x
)])
2347 /* Global registers are not local. */
2348 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2363 /* Constants in the function's constants pool are constant. */
2364 if (CONSTANT_POOL_ADDRESS_P (x
))
2369 /* Non-constant calls and recursion are not local. */
2373 /* Be overly conservative and consider any volatile memory
2374 reference as not local. */
2375 if (MEM_VOLATILE_P (x
))
2377 base
= find_base_term (XEXP (x
, 0));
2380 /* A Pmode ADDRESS could be a reference via the structure value
2381 address or static chain. Such memory references are nonlocal.
2383 Thus, we have to examine the contents of the ADDRESS to find
2384 out if this is a local reference or not. */
2385 if (GET_CODE (base
) == ADDRESS
2386 && GET_MODE (base
) == Pmode
2387 && (XEXP (base
, 0) == stack_pointer_rtx
2388 || XEXP (base
, 0) == arg_pointer_rtx
2389 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2390 || XEXP (base
, 0) == hard_frame_pointer_rtx
2392 || XEXP (base
, 0) == frame_pointer_rtx
))
2394 /* Constants in the function's constant pool are constant. */
2395 if (GET_CODE (base
) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (base
))
2400 case UNSPEC_VOLATILE
:
2405 if (MEM_VOLATILE_P (x
))
2417 /* Returns nonzero if X might mention something which is not
2418 local to the function and is not constant. */
2421 nonlocal_mentioned_p (rtx x
)
2427 if (! CONST_OR_PURE_CALL_P (x
))
2429 x
= CALL_INSN_FUNCTION_USAGE (x
);
2437 return for_each_rtx (&x
, nonlocal_mentioned_p_1
, NULL
);
2440 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2441 something which is not local to the function and is not constant. */
2444 nonlocal_referenced_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2451 switch (GET_CODE (x
))
2457 return nonlocal_mentioned_p (x
);
2460 /* Non-constant calls and recursion are not local. */
2464 if (nonlocal_mentioned_p (SET_SRC (x
)))
2467 if (MEM_P (SET_DEST (x
)))
2468 return nonlocal_mentioned_p (XEXP (SET_DEST (x
), 0));
2470 /* If the destination is anything other than a CC0, PC,
2471 MEM, REG, or a SUBREG of a REG that occupies all of
2472 the REG, then X references nonlocal memory if it is
2473 mentioned in the destination. */
2474 if (GET_CODE (SET_DEST (x
)) != CC0
2475 && GET_CODE (SET_DEST (x
)) != PC
2476 && !REG_P (SET_DEST (x
))
2477 && ! (GET_CODE (SET_DEST (x
)) == SUBREG
2478 && REG_P (SUBREG_REG (SET_DEST (x
)))
2479 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x
))))
2480 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
)
2481 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x
)))
2482 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
))))
2483 return nonlocal_mentioned_p (SET_DEST (x
));
2487 if (MEM_P (XEXP (x
, 0)))
2488 return nonlocal_mentioned_p (XEXP (XEXP (x
, 0), 0));
2492 return nonlocal_mentioned_p (XEXP (x
, 0));
2495 case UNSPEC_VOLATILE
:
2499 if (MEM_VOLATILE_P (x
))
2511 /* Returns nonzero if X might reference something which is not
2512 local to the function and is not constant. */
2515 nonlocal_referenced_p (rtx x
)
2521 if (! CONST_OR_PURE_CALL_P (x
))
2523 x
= CALL_INSN_FUNCTION_USAGE (x
);
2531 return for_each_rtx (&x
, nonlocal_referenced_p_1
, NULL
);
2534 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2535 something which is not local to the function and is not constant. */
2538 nonlocal_set_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2545 switch (GET_CODE (x
))
2548 /* Non-constant calls and recursion are not local. */
2557 return nonlocal_mentioned_p (XEXP (x
, 0));
2560 if (nonlocal_mentioned_p (SET_DEST (x
)))
2562 return nonlocal_set_p (SET_SRC (x
));
2565 return nonlocal_mentioned_p (XEXP (x
, 0));
2571 case UNSPEC_VOLATILE
:
2575 if (MEM_VOLATILE_P (x
))
2587 /* Returns nonzero if X might set something which is not
2588 local to the function and is not constant. */
2591 nonlocal_set_p (rtx x
)
2597 if (! CONST_OR_PURE_CALL_P (x
))
2599 x
= CALL_INSN_FUNCTION_USAGE (x
);
2607 return for_each_rtx (&x
, nonlocal_set_p_1
, NULL
);
2610 /* Mark the function if it is pure or constant. */
2613 mark_constant_function (void)
2616 int nonlocal_memory_referenced
;
2618 if (TREE_READONLY (current_function_decl
)
2619 || DECL_IS_PURE (current_function_decl
)
2620 || TREE_THIS_VOLATILE (current_function_decl
)
2621 || current_function_has_nonlocal_goto
2622 || !targetm
.binds_local_p (current_function_decl
))
2625 /* A loop might not return which counts as a side effect. */
2626 if (mark_dfs_back_edges ())
2629 nonlocal_memory_referenced
= 0;
2631 init_alias_analysis ();
2633 /* Determine if this is a constant or pure function. */
2635 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2637 if (! INSN_P (insn
))
2640 if (nonlocal_set_p (insn
) || global_reg_mentioned_p (insn
)
2641 || volatile_refs_p (PATTERN (insn
)))
2644 if (! nonlocal_memory_referenced
)
2645 nonlocal_memory_referenced
= nonlocal_referenced_p (insn
);
2648 end_alias_analysis ();
2650 /* Mark the function. */
2654 else if (nonlocal_memory_referenced
)
2656 cgraph_rtl_info (current_function_decl
)->pure_function
= 1;
2657 DECL_IS_PURE (current_function_decl
) = 1;
2661 cgraph_rtl_info (current_function_decl
)->const_function
= 1;
2662 TREE_READONLY (current_function_decl
) = 1;
2668 init_alias_once (void)
2672 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2673 /* Check whether this register can hold an incoming pointer
2674 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2675 numbers, so translate if necessary due to register windows. */
2676 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2677 && HARD_REGNO_MODE_OK (i
, Pmode
))
2678 static_reg_base_value
[i
]
2679 = gen_rtx_ADDRESS (VOIDmode
, gen_rtx_REG (Pmode
, i
));
2681 static_reg_base_value
[STACK_POINTER_REGNUM
]
2682 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
2683 static_reg_base_value
[ARG_POINTER_REGNUM
]
2684 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
2685 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2686 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
2687 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2688 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2689 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
2693 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2694 to be memory reference. */
2695 static bool memory_modified
;
2697 memory_modified_1 (rtx x
, rtx pat ATTRIBUTE_UNUSED
, void *data
)
2701 if (anti_dependence (x
, (rtx
)data
) || output_dependence (x
, (rtx
)data
))
2702 memory_modified
= true;
2707 /* Return true when INSN possibly modify memory contents of MEM
2708 (i.e. address can be modified). */
2710 memory_modified_in_insn_p (rtx mem
, rtx insn
)
2714 memory_modified
= false;
2715 note_stores (PATTERN (insn
), memory_modified_1
, mem
);
2716 return memory_modified
;
2719 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2723 init_alias_analysis (void)
2725 unsigned int maxreg
= max_reg_num ();
2731 timevar_push (TV_ALIAS_ANALYSIS
);
2733 reg_known_value_size
= maxreg
- FIRST_PSEUDO_REGISTER
;
2734 reg_known_value
= ggc_calloc (reg_known_value_size
, sizeof (rtx
));
2735 reg_known_equiv_p
= xcalloc (reg_known_value_size
, sizeof (bool));
2737 /* Overallocate reg_base_value to allow some growth during loop
2738 optimization. Loop unrolling can create a large number of
2740 if (old_reg_base_value
)
2742 reg_base_value
= old_reg_base_value
;
2743 /* If varray gets large zeroing cost may get important. */
2744 if (VARRAY_SIZE (reg_base_value
) > 256
2745 && VARRAY_SIZE (reg_base_value
) > 4 * maxreg
)
2746 VARRAY_GROW (reg_base_value
, maxreg
);
2747 VARRAY_CLEAR (reg_base_value
);
2748 if (VARRAY_SIZE (reg_base_value
) < maxreg
)
2749 VARRAY_GROW (reg_base_value
, maxreg
);
2753 VARRAY_RTX_INIT (reg_base_value
, maxreg
, "reg_base_value");
2756 new_reg_base_value
= xmalloc (maxreg
* sizeof (rtx
));
2757 reg_seen
= xmalloc (maxreg
);
2759 /* The basic idea is that each pass through this loop will use the
2760 "constant" information from the previous pass to propagate alias
2761 information through another level of assignments.
2763 This could get expensive if the assignment chains are long. Maybe
2764 we should throttle the number of iterations, possibly based on
2765 the optimization level or flag_expensive_optimizations.
2767 We could propagate more information in the first pass by making use
2768 of REG_N_SETS to determine immediately that the alias information
2769 for a pseudo is "constant".
2771 A program with an uninitialized variable can cause an infinite loop
2772 here. Instead of doing a full dataflow analysis to detect such problems
2773 we just cap the number of iterations for the loop.
2775 The state of the arrays for the set chain in question does not matter
2776 since the program has undefined behavior. */
2781 /* Assume nothing will change this iteration of the loop. */
2784 /* We want to assign the same IDs each iteration of this loop, so
2785 start counting from zero each iteration of the loop. */
2788 /* We're at the start of the function each iteration through the
2789 loop, so we're copying arguments. */
2790 copying_arguments
= true;
2792 /* Wipe the potential alias information clean for this pass. */
2793 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
2795 /* Wipe the reg_seen array clean. */
2796 memset (reg_seen
, 0, maxreg
);
2798 /* Mark all hard registers which may contain an address.
2799 The stack, frame and argument pointers may contain an address.
2800 An argument register which can hold a Pmode value may contain
2801 an address even if it is not in BASE_REGS.
2803 The address expression is VOIDmode for an argument and
2804 Pmode for other registers. */
2806 memcpy (new_reg_base_value
, static_reg_base_value
,
2807 FIRST_PSEUDO_REGISTER
* sizeof (rtx
));
2809 /* Walk the insns adding values to the new_reg_base_value array. */
2810 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2816 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2817 /* The prologue/epilogue insns are not threaded onto the
2818 insn chain until after reload has completed. Thus,
2819 there is no sense wasting time checking if INSN is in
2820 the prologue/epilogue until after reload has completed. */
2821 if (reload_completed
2822 && prologue_epilogue_contains (insn
))
2826 /* If this insn has a noalias note, process it, Otherwise,
2827 scan for sets. A simple set will have no side effects
2828 which could change the base value of any other register. */
2830 if (GET_CODE (PATTERN (insn
)) == SET
2831 && REG_NOTES (insn
) != 0
2832 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2833 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2835 note_stores (PATTERN (insn
), record_set
, NULL
);
2837 set
= single_set (insn
);
2840 && REG_P (SET_DEST (set
))
2841 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2843 unsigned int regno
= REGNO (SET_DEST (set
));
2844 rtx src
= SET_SRC (set
);
2847 if (REG_NOTES (insn
) != 0
2848 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
2849 && REG_N_SETS (regno
) == 1)
2850 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
2851 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2852 && ! rtx_varies_p (XEXP (note
, 0), 1)
2853 && ! reg_overlap_mentioned_p (SET_DEST (set
),
2856 set_reg_known_value (regno
, XEXP (note
, 0));
2857 set_reg_known_equiv_p (regno
,
2858 REG_NOTE_KIND (note
) == REG_EQUIV
);
2860 else if (REG_N_SETS (regno
) == 1
2861 && GET_CODE (src
) == PLUS
2862 && REG_P (XEXP (src
, 0))
2863 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
2864 && GET_CODE (XEXP (src
, 1)) == CONST_INT
)
2866 t
= plus_constant (t
, INTVAL (XEXP (src
, 1)));
2867 set_reg_known_value (regno
, t
);
2868 set_reg_known_equiv_p (regno
, 0);
2870 else if (REG_N_SETS (regno
) == 1
2871 && ! rtx_varies_p (src
, 1))
2873 set_reg_known_value (regno
, src
);
2874 set_reg_known_equiv_p (regno
, 0);
2878 else if (NOTE_P (insn
)
2879 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
2880 copying_arguments
= false;
2883 /* Now propagate values from new_reg_base_value to reg_base_value. */
2884 gcc_assert (maxreg
== (unsigned int) max_reg_num());
2886 for (ui
= 0; ui
< maxreg
; ui
++)
2888 if (new_reg_base_value
[ui
]
2889 && new_reg_base_value
[ui
] != VARRAY_RTX (reg_base_value
, ui
)
2890 && ! rtx_equal_p (new_reg_base_value
[ui
],
2891 VARRAY_RTX (reg_base_value
, ui
)))
2893 VARRAY_RTX (reg_base_value
, ui
) = new_reg_base_value
[ui
];
2898 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2900 /* Fill in the remaining entries. */
2901 for (i
= 0; i
< (int)reg_known_value_size
; i
++)
2902 if (reg_known_value
[i
] == 0)
2903 reg_known_value
[i
] = regno_reg_rtx
[i
+ FIRST_PSEUDO_REGISTER
];
2905 /* Simplify the reg_base_value array so that no register refers to
2906 another register, except to special registers indirectly through
2907 ADDRESS expressions.
2909 In theory this loop can take as long as O(registers^2), but unless
2910 there are very long dependency chains it will run in close to linear
2913 This loop may not be needed any longer now that the main loop does
2914 a better job at propagating alias information. */
2920 for (ui
= 0; ui
< maxreg
; ui
++)
2922 rtx base
= VARRAY_RTX (reg_base_value
, ui
);
2923 if (base
&& REG_P (base
))
2925 unsigned int base_regno
= REGNO (base
);
2926 if (base_regno
== ui
) /* register set from itself */
2927 VARRAY_RTX (reg_base_value
, ui
) = 0;
2929 VARRAY_RTX (reg_base_value
, ui
)
2930 = VARRAY_RTX (reg_base_value
, base_regno
);
2935 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
2938 free (new_reg_base_value
);
2939 new_reg_base_value
= 0;
2942 timevar_pop (TV_ALIAS_ANALYSIS
);
2946 end_alias_analysis (void)
2948 old_reg_base_value
= reg_base_value
;
2949 ggc_free (reg_known_value
);
2950 reg_known_value
= 0;
2951 reg_known_value_size
= 0;
2952 free (reg_known_equiv_p
);
2953 reg_known_equiv_p
= 0;
2954 if (alias_invariant
)
2956 ggc_free (alias_invariant
);
2957 alias_invariant
= 0;
2958 alias_invariant_size
= 0;
2962 #include "gt-alias.h"