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"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
39 #include "splay-tree.h"
41 #include "langhooks.h"
47 /* The alias sets assigned to MEMs assist the back-end in determining
48 which MEMs can alias which other MEMs. In general, two MEMs in
49 different alias sets cannot alias each other, with one important
50 exception. Consider something like:
52 struct S { int i; double d; };
54 a store to an `S' can alias something of either type `int' or type
55 `double'. (However, a store to an `int' cannot alias a `double'
56 and vice versa.) We indicate this via a tree structure that looks
64 (The arrows are directed and point downwards.)
65 In this situation we say the alias set for `struct S' is the
66 `superset' and that those for `int' and `double' are `subsets'.
68 To see whether two alias sets can point to the same memory, we must
69 see if either alias set is a subset of the other. We need not trace
70 past immediate descendants, however, since we propagate all
71 grandchildren up one level.
73 Alias set zero is implicitly a superset of all other alias sets.
74 However, this is no actual entry for alias set zero. It is an
75 error to attempt to explicitly construct a subset of zero. */
77 struct alias_set_entry GTY(())
79 /* The alias set number, as stored in MEM_ALIAS_SET. */
80 HOST_WIDE_INT alias_set;
82 /* The children of the alias set. These are not just the immediate
83 children, but, in fact, all descendants. So, if we have:
85 struct T { struct S s; float f; }
87 continuing our example above, the children here will be all of
88 `int', `double', `float', and `struct S'. */
89 splay_tree GTY((param1_is (int), param2_is (int))) children;
91 /* Nonzero if would have a child of zero: this effectively makes this
92 alias set the same as alias set zero. */
95 typedef struct alias_set_entry *alias_set_entry;
97 static int rtx_equal_for_memref_p (rtx, rtx);
98 static rtx find_symbolic_term (rtx);
99 static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
100 static void record_set (rtx, rtx, void *);
101 static int base_alias_check (rtx, rtx, enum machine_mode,
103 static rtx find_base_value (rtx);
104 static int mems_in_disjoint_alias_sets_p (rtx, rtx);
105 static int insert_subset_children (splay_tree_node, void*);
106 static tree find_base_decl (tree);
107 static alias_set_entry get_alias_set_entry (HOST_WIDE_INT);
108 static rtx fixed_scalar_and_varying_struct_p (rtx, rtx, rtx, rtx,
110 static int aliases_everything_p (rtx);
111 static bool nonoverlapping_component_refs_p (tree, tree);
112 static tree decl_for_component_ref (tree);
113 static rtx adjust_offset_for_component_ref (tree, rtx);
114 static int nonoverlapping_memrefs_p (rtx, rtx);
115 static int write_dependence_p (rtx, rtx, int, int);
117 static int nonlocal_mentioned_p_1 (rtx *, void *);
118 static int nonlocal_mentioned_p (rtx);
119 static int nonlocal_referenced_p_1 (rtx *, void *);
120 static int nonlocal_referenced_p (rtx);
121 static int nonlocal_set_p_1 (rtx *, void *);
122 static int nonlocal_set_p (rtx);
123 static void memory_modified_1 (rtx, rtx, void *);
125 /* Set up all info needed to perform alias analysis on memory references. */
127 /* Returns the size in bytes of the mode of X. */
128 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
130 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
131 different alias sets. We ignore alias sets in functions making use
132 of variable arguments because the va_arg macros on some systems are
134 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
135 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
137 /* Cap the number of passes we make over the insns propagating alias
138 information through set chains. 10 is a completely arbitrary choice. */
139 #define MAX_ALIAS_LOOP_PASSES 10
141 /* reg_base_value[N] gives an address to which register N is related.
142 If all sets after the first add or subtract to the current value
143 or otherwise modify it so it does not point to a different top level
144 object, reg_base_value[N] is equal to the address part of the source
147 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
148 expressions represent certain special values: function arguments and
149 the stack, frame, and argument pointers.
151 The contents of an ADDRESS is not normally used, the mode of the
152 ADDRESS determines whether the ADDRESS is a function argument or some
153 other special value. Pointer equality, not rtx_equal_p, determines whether
154 two ADDRESS expressions refer to the same base address.
156 The only use of the contents of an ADDRESS is for determining if the
157 current function performs nonlocal memory memory references for the
158 purposes of marking the function as a constant function. */
160 static GTY(()) varray_type reg_base_value;
161 static rtx *new_reg_base_value;
163 /* We preserve the copy of old array around to avoid amount of garbage
164 produced. About 8% of garbage produced were attributed to this
166 static GTY((deletable (""))) varray_type old_reg_base_value;
168 /* Static hunks of RTL used by the aliasing code; these are initialized
169 once per function to avoid unnecessary RTL allocations. */
170 static GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER];
172 #define REG_BASE_VALUE(X) \
173 (reg_base_value && REGNO (X) < VARRAY_SIZE (reg_base_value) \
174 ? VARRAY_RTX (reg_base_value, REGNO (X)) : 0)
176 /* Vector of known invariant relationships between registers. Set in
177 loop unrolling. Indexed by register number, if nonzero the value
178 is an expression describing this register in terms of another.
180 The length of this array is REG_BASE_VALUE_SIZE.
182 Because this array contains only pseudo registers it has no effect
184 static GTY((length("alias_invariant_size"))) rtx *alias_invariant;
185 unsigned GTY(()) int alias_invariant_size;
187 /* Vector indexed by N giving the initial (unchanging) value known for
188 pseudo-register N. This array is initialized in init_alias_analysis,
189 and does not change until end_alias_analysis is called. */
190 static GTY((length("reg_known_value_size"))) rtx *reg_known_value;
192 /* Indicates number of valid entries in reg_known_value. */
193 static GTY(()) unsigned int reg_known_value_size;
195 /* Vector recording for each reg_known_value whether it is due to a
196 REG_EQUIV note. Future passes (viz., reload) may replace the
197 pseudo with the equivalent expression and so we account for the
198 dependences that would be introduced if that happens.
200 The REG_EQUIV notes created in assign_parms may mention the arg
201 pointer, and there are explicit insns in the RTL that modify the
202 arg pointer. Thus we must ensure that such insns don't get
203 scheduled across each other because that would invalidate the
204 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
205 wrong, but solving the problem in the scheduler will likely give
206 better code, so we do it here. */
207 static bool *reg_known_equiv_p;
209 /* True when scanning insns from the start of the rtl to the
210 NOTE_INSN_FUNCTION_BEG note. */
211 static bool copying_arguments;
213 /* The splay-tree used to store the various alias set entries. */
214 static GTY ((param_is (struct alias_set_entry))) varray_type alias_sets;
216 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
217 such an entry, or NULL otherwise. */
219 static inline alias_set_entry
220 get_alias_set_entry (HOST_WIDE_INT alias_set)
222 return (alias_set_entry)VARRAY_GENERIC_PTR (alias_sets, alias_set);
225 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
226 the two MEMs cannot alias each other. */
229 mems_in_disjoint_alias_sets_p (rtx mem1, rtx mem2)
231 #ifdef ENABLE_CHECKING
232 /* Perform a basic sanity check. Namely, that there are no alias sets
233 if we're not using strict aliasing. This helps to catch bugs
234 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
235 where a MEM is allocated in some way other than by the use of
236 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
237 use alias sets to indicate that spilled registers cannot alias each
238 other, we might need to remove this check. */
239 if (! flag_strict_aliasing
240 && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0))
244 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
247 /* Insert the NODE into the splay tree given by DATA. Used by
248 record_alias_subset via splay_tree_foreach. */
251 insert_subset_children (splay_tree_node node, void *data)
253 splay_tree_insert ((splay_tree) data, node->key, node->value);
258 /* Return 1 if the two specified alias sets may conflict. */
261 alias_sets_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2)
265 /* If have no alias set information for one of the operands, we have
266 to assume it can alias anything. */
267 if (set1 == 0 || set2 == 0
268 /* If the two alias sets are the same, they may alias. */
272 /* See if the first alias set is a subset of the second. */
273 ase = get_alias_set_entry (set1);
275 && (ase->has_zero_child
276 || splay_tree_lookup (ase->children,
277 (splay_tree_key) set2)))
280 /* Now do the same, but with the alias sets reversed. */
281 ase = get_alias_set_entry (set2);
283 && (ase->has_zero_child
284 || splay_tree_lookup (ase->children,
285 (splay_tree_key) set1)))
288 /* The two alias sets are distinct and neither one is the
289 child of the other. Therefore, they cannot alias. */
293 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
294 has any readonly fields. If any of the fields have types that
295 contain readonly fields, return true as well. */
298 readonly_fields_p (tree type)
302 if (TREE_CODE (type) != RECORD_TYPE && TREE_CODE (type) != UNION_TYPE
303 && TREE_CODE (type) != QUAL_UNION_TYPE)
306 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
307 if (TREE_CODE (field) == FIELD_DECL
308 && (TREE_READONLY (field)
309 || readonly_fields_p (TREE_TYPE (field))))
315 /* Return 1 if any MEM object of type T1 will always conflict (using the
316 dependency routines in this file) with any MEM object of type T2.
317 This is used when allocating temporary storage. If T1 and/or T2 are
318 NULL_TREE, it means we know nothing about the storage. */
321 objects_must_conflict_p (tree t1, tree t2)
323 HOST_WIDE_INT set1, set2;
325 /* If neither has a type specified, we don't know if they'll conflict
326 because we may be using them to store objects of various types, for
327 example the argument and local variables areas of inlined functions. */
328 if (t1 == 0 && t2 == 0)
331 /* If one or the other has readonly fields or is readonly,
332 then they may not conflict. */
333 if ((t1 != 0 && readonly_fields_p (t1))
334 || (t2 != 0 && readonly_fields_p (t2))
335 || (t1 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t1))
336 || (t2 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t2)))
339 /* If they are the same type, they must conflict. */
341 /* Likewise if both are volatile. */
342 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
345 set1 = t1 ? get_alias_set (t1) : 0;
346 set2 = t2 ? get_alias_set (t2) : 0;
348 /* Otherwise they conflict if they have no alias set or the same. We
349 can't simply use alias_sets_conflict_p here, because we must make
350 sure that every subtype of t1 will conflict with every subtype of
351 t2 for which a pair of subobjects of these respective subtypes
352 overlaps on the stack. */
353 return set1 == 0 || set2 == 0 || set1 == set2;
356 /* T is an expression with pointer type. Find the DECL on which this
357 expression is based. (For example, in `a[i]' this would be `a'.)
358 If there is no such DECL, or a unique decl cannot be determined,
359 NULL_TREE is returned. */
362 find_base_decl (tree t)
366 if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
369 /* If this is a declaration, return it. */
370 if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd')
373 /* Handle general expressions. It would be nice to deal with
374 COMPONENT_REFs here. If we could tell that `a' and `b' were the
375 same, then `a->f' and `b->f' are also the same. */
376 switch (TREE_CODE_CLASS (TREE_CODE (t)))
379 return find_base_decl (TREE_OPERAND (t, 0));
382 /* Return 0 if found in neither or both are the same. */
383 d0 = find_base_decl (TREE_OPERAND (t, 0));
384 d1 = find_base_decl (TREE_OPERAND (t, 1));
395 d0 = find_base_decl (TREE_OPERAND (t, 0));
396 d1 = find_base_decl (TREE_OPERAND (t, 1));
397 d2 = find_base_decl (TREE_OPERAND (t, 2));
399 /* Set any nonzero values from the last, then from the first. */
400 if (d1 == 0) d1 = d2;
401 if (d0 == 0) d0 = d1;
402 if (d1 == 0) d1 = d0;
403 if (d2 == 0) d2 = d1;
405 /* At this point all are nonzero or all are zero. If all three are the
406 same, return it. Otherwise, return zero. */
407 return (d0 == d1 && d1 == d2) ? d0 : 0;
414 /* Return 1 if all the nested component references handled by
415 get_inner_reference in T are such that we can address the object in T. */
418 can_address_p (tree t)
420 /* If we're at the end, it is vacuously addressable. */
421 if (! handled_component_p (t))
424 /* Bitfields are never addressable. */
425 else if (TREE_CODE (t) == BIT_FIELD_REF)
428 /* Fields are addressable unless they are marked as nonaddressable or
429 the containing type has alias set 0. */
430 else if (TREE_CODE (t) == COMPONENT_REF
431 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))
432 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
433 && can_address_p (TREE_OPERAND (t, 0)))
436 /* Likewise for arrays. */
437 else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
438 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))
439 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
440 && can_address_p (TREE_OPERAND (t, 0)))
446 /* Return the alias set for T, which may be either a type or an
447 expression. Call language-specific routine for help, if needed. */
450 get_alias_set (tree t)
454 /* If we're not doing any alias analysis, just assume everything
455 aliases everything else. Also return 0 if this or its type is
457 if (! flag_strict_aliasing || t == error_mark_node
459 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
462 /* We can be passed either an expression or a type. This and the
463 language-specific routine may make mutually-recursive calls to each other
464 to figure out what to do. At each juncture, we see if this is a tree
465 that the language may need to handle specially. First handle things that
470 tree placeholder_ptr = 0;
472 /* Remove any nops, then give the language a chance to do
473 something with this tree before we look at it. */
475 set = (*lang_hooks.get_alias_set) (t);
479 /* First see if the actual object referenced is an INDIRECT_REF from a
480 restrict-qualified pointer or a "void *". Replace
481 PLACEHOLDER_EXPRs. */
482 while (TREE_CODE (inner) == PLACEHOLDER_EXPR
483 || handled_component_p (inner))
485 if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
486 inner = find_placeholder (inner, &placeholder_ptr);
488 inner = TREE_OPERAND (inner, 0);
493 /* Check for accesses through restrict-qualified pointers. */
494 if (TREE_CODE (inner) == INDIRECT_REF)
496 tree decl = find_base_decl (TREE_OPERAND (inner, 0));
498 if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
500 /* If we haven't computed the actual alias set, do it now. */
501 if (DECL_POINTER_ALIAS_SET (decl) == -2)
503 /* No two restricted pointers can point at the same thing.
504 However, a restricted pointer can point at the same thing
505 as an unrestricted pointer, if that unrestricted pointer
506 is based on the restricted pointer. So, we make the
507 alias set for the restricted pointer a subset of the
508 alias set for the type pointed to by the type of the
510 HOST_WIDE_INT pointed_to_alias_set
511 = get_alias_set (TREE_TYPE (TREE_TYPE (decl)));
513 if (pointed_to_alias_set == 0)
514 /* It's not legal to make a subset of alias set zero. */
515 DECL_POINTER_ALIAS_SET (decl) = 0;
518 DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
519 record_alias_subset (pointed_to_alias_set,
520 DECL_POINTER_ALIAS_SET (decl));
524 /* We use the alias set indicated in the declaration. */
525 return DECL_POINTER_ALIAS_SET (decl);
528 /* If we have an INDIRECT_REF via a void pointer, we don't
529 know anything about what that might alias. */
530 else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE)
534 /* Otherwise, pick up the outermost object that we could have a pointer
535 to, processing conversion and PLACEHOLDER_EXPR as above. */
537 while (TREE_CODE (t) == PLACEHOLDER_EXPR
538 || (handled_component_p (t) && ! can_address_p (t)))
540 if (TREE_CODE (t) == PLACEHOLDER_EXPR)
541 t = find_placeholder (t, &placeholder_ptr);
543 t = TREE_OPERAND (t, 0);
548 /* If we've already determined the alias set for a decl, just return
549 it. This is necessary for C++ anonymous unions, whose component
550 variables don't look like union members (boo!). */
551 if (TREE_CODE (t) == VAR_DECL
552 && DECL_RTL_SET_P (t) && GET_CODE (DECL_RTL (t)) == MEM)
553 return MEM_ALIAS_SET (DECL_RTL (t));
555 /* Now all we care about is the type. */
559 /* Variant qualifiers don't affect the alias set, so get the main
560 variant. If this is a type with a known alias set, return it. */
561 t = TYPE_MAIN_VARIANT (t);
562 if (TYPE_ALIAS_SET_KNOWN_P (t))
563 return TYPE_ALIAS_SET (t);
565 /* See if the language has special handling for this type. */
566 set = (*lang_hooks.get_alias_set) (t);
570 /* There are no objects of FUNCTION_TYPE, so there's no point in
571 using up an alias set for them. (There are, of course, pointers
572 and references to functions, but that's different.) */
573 else if (TREE_CODE (t) == FUNCTION_TYPE)
576 /* Unless the language specifies otherwise, let vector types alias
577 their components. This avoids some nasty type punning issues in
578 normal usage. And indeed lets vectors be treated more like an
580 else if (TREE_CODE (t) == VECTOR_TYPE)
581 set = get_alias_set (TREE_TYPE (t));
584 /* Otherwise make a new alias set for this type. */
585 set = new_alias_set ();
587 TYPE_ALIAS_SET (t) = set;
589 /* If this is an aggregate type, we must record any component aliasing
591 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
592 record_component_aliases (t);
597 /* Return a brand-new alias set. */
599 static GTY(()) HOST_WIDE_INT last_alias_set;
604 if (flag_strict_aliasing)
607 VARRAY_GENERIC_PTR_INIT (alias_sets, 10, "alias sets");
609 VARRAY_GROW (alias_sets, last_alias_set + 2);
610 return ++last_alias_set;
616 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
617 not everything that aliases SUPERSET also aliases SUBSET. For example,
618 in C, a store to an `int' can alias a load of a structure containing an
619 `int', and vice versa. But it can't alias a load of a 'double' member
620 of the same structure. Here, the structure would be the SUPERSET and
621 `int' the SUBSET. This relationship is also described in the comment at
622 the beginning of this file.
624 This function should be called only once per SUPERSET/SUBSET pair.
626 It is illegal for SUPERSET to be zero; everything is implicitly a
627 subset of alias set zero. */
630 record_alias_subset (HOST_WIDE_INT superset, HOST_WIDE_INT subset)
632 alias_set_entry superset_entry;
633 alias_set_entry subset_entry;
635 /* It is possible in complex type situations for both sets to be the same,
636 in which case we can ignore this operation. */
637 if (superset == subset)
643 superset_entry = get_alias_set_entry (superset);
644 if (superset_entry == 0)
646 /* Create an entry for the SUPERSET, so that we have a place to
647 attach the SUBSET. */
648 superset_entry = ggc_alloc (sizeof (struct alias_set_entry));
649 superset_entry->alias_set = superset;
650 superset_entry->children
651 = splay_tree_new_ggc (splay_tree_compare_ints);
652 superset_entry->has_zero_child = 0;
653 VARRAY_GENERIC_PTR (alias_sets, superset) = superset_entry;
657 superset_entry->has_zero_child = 1;
660 subset_entry = get_alias_set_entry (subset);
661 /* If there is an entry for the subset, enter all of its children
662 (if they are not already present) as children of the SUPERSET. */
665 if (subset_entry->has_zero_child)
666 superset_entry->has_zero_child = 1;
668 splay_tree_foreach (subset_entry->children, insert_subset_children,
669 superset_entry->children);
672 /* Enter the SUBSET itself as a child of the SUPERSET. */
673 splay_tree_insert (superset_entry->children,
674 (splay_tree_key) subset, 0);
678 /* Record that component types of TYPE, if any, are part of that type for
679 aliasing purposes. For record types, we only record component types
680 for fields that are marked addressable. For array types, we always
681 record the component types, so the front end should not call this
682 function if the individual component aren't addressable. */
685 record_component_aliases (tree type)
687 HOST_WIDE_INT superset = get_alias_set (type);
693 switch (TREE_CODE (type))
696 if (! TYPE_NONALIASED_COMPONENT (type))
697 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
702 case QUAL_UNION_TYPE:
703 /* Recursively record aliases for the base classes, if there are any. */
704 if (TYPE_BINFO (type) != NULL && TYPE_BINFO_BASETYPES (type) != NULL)
707 for (i = 0; i < TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type)); i++)
709 tree binfo = TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type), i);
710 record_alias_subset (superset,
711 get_alias_set (BINFO_TYPE (binfo)));
714 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
715 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
716 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
720 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
728 /* Allocate an alias set for use in storing and reading from the varargs
731 static GTY(()) HOST_WIDE_INT varargs_set = -1;
734 get_varargs_alias_set (void)
736 if (varargs_set == -1)
737 varargs_set = new_alias_set ();
742 /* Likewise, but used for the fixed portions of the frame, e.g., register
745 static GTY(()) HOST_WIDE_INT frame_set = -1;
748 get_frame_alias_set (void)
751 frame_set = new_alias_set ();
756 /* Inside SRC, the source of a SET, find a base address. */
759 find_base_value (rtx src)
763 switch (GET_CODE (src))
771 /* At the start of a function, argument registers have known base
772 values which may be lost later. Returning an ADDRESS
773 expression here allows optimization based on argument values
774 even when the argument registers are used for other purposes. */
775 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
776 return new_reg_base_value[regno];
778 /* If a pseudo has a known base value, return it. Do not do this
779 for non-fixed hard regs since it can result in a circular
780 dependency chain for registers which have values at function entry.
782 The test above is not sufficient because the scheduler may move
783 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
784 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
785 && regno < VARRAY_SIZE (reg_base_value))
787 /* If we're inside init_alias_analysis, use new_reg_base_value
788 to reduce the number of relaxation iterations. */
789 if (new_reg_base_value && new_reg_base_value[regno]
790 && REG_N_SETS (regno) == 1)
791 return new_reg_base_value[regno];
793 if (VARRAY_RTX (reg_base_value, regno))
794 return VARRAY_RTX (reg_base_value, regno);
800 /* Check for an argument passed in memory. Only record in the
801 copying-arguments block; it is too hard to track changes
803 if (copying_arguments
804 && (XEXP (src, 0) == arg_pointer_rtx
805 || (GET_CODE (XEXP (src, 0)) == PLUS
806 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
807 return gen_rtx_ADDRESS (VOIDmode, src);
812 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
815 /* ... fall through ... */
820 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
822 /* If either operand is a REG that is a known pointer, then it
824 if (REG_P (src_0) && REG_POINTER (src_0))
825 return find_base_value (src_0);
826 if (REG_P (src_1) && REG_POINTER (src_1))
827 return find_base_value (src_1);
829 /* If either operand is a REG, then see if we already have
830 a known value for it. */
833 temp = find_base_value (src_0);
840 temp = find_base_value (src_1);
845 /* If either base is named object or a special address
846 (like an argument or stack reference), then use it for the
849 && (GET_CODE (src_0) == SYMBOL_REF
850 || GET_CODE (src_0) == LABEL_REF
851 || (GET_CODE (src_0) == ADDRESS
852 && GET_MODE (src_0) != VOIDmode)))
856 && (GET_CODE (src_1) == SYMBOL_REF
857 || GET_CODE (src_1) == LABEL_REF
858 || (GET_CODE (src_1) == ADDRESS
859 && GET_MODE (src_1) != VOIDmode)))
862 /* Guess which operand is the base address:
863 If either operand is a symbol, then it is the base. If
864 either operand is a CONST_INT, then the other is the base. */
865 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
866 return find_base_value (src_0);
867 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
868 return find_base_value (src_1);
874 /* The standard form is (lo_sum reg sym) so look only at the
876 return find_base_value (XEXP (src, 1));
879 /* If the second operand is constant set the base
880 address to the first operand. */
881 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
882 return find_base_value (XEXP (src, 0));
886 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
896 return find_base_value (XEXP (src, 0));
899 case SIGN_EXTEND: /* used for NT/Alpha pointers */
901 rtx temp = find_base_value (XEXP (src, 0));
903 if (temp != 0 && CONSTANT_P (temp))
904 temp = convert_memory_address (Pmode, temp);
916 /* Called from init_alias_analysis indirectly through note_stores. */
918 /* While scanning insns to find base values, reg_seen[N] is nonzero if
919 register N has been set in this function. */
920 static char *reg_seen;
922 /* Addresses which are known not to alias anything else are identified
923 by a unique integer. */
924 static int unique_id;
927 record_set (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED)
933 if (GET_CODE (dest) != REG)
936 regno = REGNO (dest);
938 if (regno >= VARRAY_SIZE (reg_base_value))
941 /* If this spans multiple hard registers, then we must indicate that every
942 register has an unusable value. */
943 if (regno < FIRST_PSEUDO_REGISTER)
944 n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
951 reg_seen[regno + n] = 1;
952 new_reg_base_value[regno + n] = 0;
959 /* A CLOBBER wipes out any old value but does not prevent a previously
960 unset register from acquiring a base address (i.e. reg_seen is not
962 if (GET_CODE (set) == CLOBBER)
964 new_reg_base_value[regno] = 0;
973 new_reg_base_value[regno] = 0;
977 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
978 GEN_INT (unique_id++));
982 /* This is not the first set. If the new value is not related to the
983 old value, forget the base value. Note that the following code is
985 extern int x, y; int *p = &x; p += (&y-&x);
986 ANSI C does not allow computing the difference of addresses
987 of distinct top level objects. */
988 if (new_reg_base_value[regno])
989 switch (GET_CODE (src))
993 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
994 new_reg_base_value[regno] = 0;
997 /* If the value we add in the PLUS is also a valid base value,
998 this might be the actual base value, and the original value
1001 rtx other = NULL_RTX;
1003 if (XEXP (src, 0) == dest)
1004 other = XEXP (src, 1);
1005 else if (XEXP (src, 1) == dest)
1006 other = XEXP (src, 0);
1008 if (! other || find_base_value (other))
1009 new_reg_base_value[regno] = 0;
1013 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
1014 new_reg_base_value[regno] = 0;
1017 new_reg_base_value[regno] = 0;
1020 /* If this is the first set of a register, record the value. */
1021 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1022 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1023 new_reg_base_value[regno] = find_base_value (src);
1025 reg_seen[regno] = 1;
1028 /* Called from loop optimization when a new pseudo-register is
1029 created. It indicates that REGNO is being set to VAL. f INVARIANT
1030 is true then this value also describes an invariant relationship
1031 which can be used to deduce that two registers with unknown values
1035 record_base_value (unsigned int regno, rtx val, int invariant)
1037 if (invariant && alias_invariant && regno < alias_invariant_size)
1038 alias_invariant[regno] = val;
1040 if (regno >= VARRAY_SIZE (reg_base_value))
1041 VARRAY_GROW (reg_base_value, max_reg_num ());
1043 if (GET_CODE (val) == REG)
1045 VARRAY_RTX (reg_base_value, regno)
1046 = REG_BASE_VALUE (val);
1049 VARRAY_RTX (reg_base_value, regno)
1050 = find_base_value (val);
1053 /* Clear alias info for a register. This is used if an RTL transformation
1054 changes the value of a register. This is used in flow by AUTO_INC_DEC
1055 optimizations. We don't need to clear reg_base_value, since flow only
1056 changes the offset. */
1059 clear_reg_alias_info (rtx reg)
1061 unsigned int regno = REGNO (reg);
1063 if (regno >= FIRST_PSEUDO_REGISTER)
1065 regno -= FIRST_PSEUDO_REGISTER;
1066 if (regno < reg_known_value_size)
1068 reg_known_value[regno] = reg;
1069 reg_known_equiv_p[regno] = false;
1074 /* If a value is known for REGNO, return it. */
1077 get_reg_known_value (unsigned int regno)
1079 if (regno >= FIRST_PSEUDO_REGISTER)
1081 regno -= FIRST_PSEUDO_REGISTER;
1082 if (regno < reg_known_value_size)
1083 return reg_known_value[regno];
1091 set_reg_known_value (unsigned int regno, rtx val)
1093 if (regno >= FIRST_PSEUDO_REGISTER)
1095 regno -= FIRST_PSEUDO_REGISTER;
1096 if (regno < reg_known_value_size)
1097 reg_known_value[regno] = val;
1101 /* Similarly for reg_known_equiv_p. */
1104 get_reg_known_equiv_p (unsigned int regno)
1106 if (regno >= FIRST_PSEUDO_REGISTER)
1108 regno -= FIRST_PSEUDO_REGISTER;
1109 if (regno < reg_known_value_size)
1110 return reg_known_equiv_p[regno];
1116 set_reg_known_equiv_p (unsigned int regno, bool val)
1118 if (regno >= FIRST_PSEUDO_REGISTER)
1120 regno -= FIRST_PSEUDO_REGISTER;
1121 if (regno < reg_known_value_size)
1122 reg_known_equiv_p[regno] = val;
1127 /* Returns a canonical version of X, from the point of view alias
1128 analysis. (For example, if X is a MEM whose address is a register,
1129 and the register has a known value (say a SYMBOL_REF), then a MEM
1130 whose address is the SYMBOL_REF is returned.) */
1135 /* Recursively look for equivalences. */
1136 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1138 rtx t = get_reg_known_value (REGNO (x));
1142 return canon_rtx (t);
1145 if (GET_CODE (x) == PLUS)
1147 rtx x0 = canon_rtx (XEXP (x, 0));
1148 rtx x1 = canon_rtx (XEXP (x, 1));
1150 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1152 if (GET_CODE (x0) == CONST_INT)
1153 return plus_constant (x1, INTVAL (x0));
1154 else if (GET_CODE (x1) == CONST_INT)
1155 return plus_constant (x0, INTVAL (x1));
1156 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1160 /* This gives us much better alias analysis when called from
1161 the loop optimizer. Note we want to leave the original
1162 MEM alone, but need to return the canonicalized MEM with
1163 all the flags with their original values. */
1164 else if (GET_CODE (x) == MEM)
1165 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1170 /* Return 1 if X and Y are identical-looking rtx's.
1171 Expect that X and Y has been already canonicalized.
1173 We use the data in reg_known_value above to see if two registers with
1174 different numbers are, in fact, equivalent. */
1177 rtx_equal_for_memref_p (rtx x, rtx y)
1184 if (x == 0 && y == 0)
1186 if (x == 0 || y == 0)
1192 code = GET_CODE (x);
1193 /* Rtx's of different codes cannot be equal. */
1194 if (code != GET_CODE (y))
1197 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1198 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1200 if (GET_MODE (x) != GET_MODE (y))
1203 /* Some RTL can be compared without a recursive examination. */
1207 return REGNO (x) == REGNO (y);
1210 return XEXP (x, 0) == XEXP (y, 0);
1213 return XSTR (x, 0) == XSTR (y, 0);
1218 /* There's no need to compare the contents of CONST_DOUBLEs or
1219 CONST_INTs because pointer equality is a good enough
1220 comparison for these nodes. */
1224 return (XINT (x, 1) == XINT (y, 1)
1225 && rtx_equal_for_memref_p (XEXP (x, 0),
1232 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1234 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1235 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1236 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1237 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1238 /* For commutative operations, the RTX match if the operand match in any
1239 order. Also handle the simple binary and unary cases without a loop. */
1240 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
1242 rtx xop0 = canon_rtx (XEXP (x, 0));
1243 rtx yop0 = canon_rtx (XEXP (y, 0));
1244 rtx yop1 = canon_rtx (XEXP (y, 1));
1246 return ((rtx_equal_for_memref_p (xop0, yop0)
1247 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1248 || (rtx_equal_for_memref_p (xop0, yop1)
1249 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1251 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
1253 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1254 canon_rtx (XEXP (y, 0)))
1255 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1256 canon_rtx (XEXP (y, 1))));
1258 else if (GET_RTX_CLASS (code) == '1')
1259 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1260 canon_rtx (XEXP (y, 0)));
1262 /* Compare the elements. If any pair of corresponding elements
1263 fail to match, return 0 for the whole things.
1265 Limit cases to types which actually appear in addresses. */
1267 fmt = GET_RTX_FORMAT (code);
1268 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1273 if (XINT (x, i) != XINT (y, i))
1278 /* Two vectors must have the same length. */
1279 if (XVECLEN (x, i) != XVECLEN (y, i))
1282 /* And the corresponding elements must match. */
1283 for (j = 0; j < XVECLEN (x, i); j++)
1284 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1285 canon_rtx (XVECEXP (y, i, j))) == 0)
1290 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1291 canon_rtx (XEXP (y, i))) == 0)
1295 /* This can happen for asm operands. */
1297 if (strcmp (XSTR (x, i), XSTR (y, i)))
1301 /* This can happen for an asm which clobbers memory. */
1305 /* It is believed that rtx's at this level will never
1306 contain anything but integers and other rtx's,
1307 except for within LABEL_REFs and SYMBOL_REFs. */
1315 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1316 X and return it, or return 0 if none found. */
1319 find_symbolic_term (rtx x)
1325 code = GET_CODE (x);
1326 if (code == SYMBOL_REF || code == LABEL_REF)
1328 if (GET_RTX_CLASS (code) == 'o')
1331 fmt = GET_RTX_FORMAT (code);
1332 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1338 t = find_symbolic_term (XEXP (x, i));
1342 else if (fmt[i] == 'E')
1349 find_base_term (rtx x)
1352 struct elt_loc_list *l;
1354 #if defined (FIND_BASE_TERM)
1355 /* Try machine-dependent ways to find the base term. */
1356 x = FIND_BASE_TERM (x);
1359 switch (GET_CODE (x))
1362 return REG_BASE_VALUE (x);
1365 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1375 return find_base_term (XEXP (x, 0));
1378 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1380 rtx temp = find_base_term (XEXP (x, 0));
1382 if (temp != 0 && CONSTANT_P (temp))
1383 temp = convert_memory_address (Pmode, temp);
1389 val = CSELIB_VAL_PTR (x);
1392 for (l = val->locs; l; l = l->next)
1393 if ((x = find_base_term (l->loc)) != 0)
1399 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1406 rtx tmp1 = XEXP (x, 0);
1407 rtx tmp2 = XEXP (x, 1);
1409 /* This is a little bit tricky since we have to determine which of
1410 the two operands represents the real base address. Otherwise this
1411 routine may return the index register instead of the base register.
1413 That may cause us to believe no aliasing was possible, when in
1414 fact aliasing is possible.
1416 We use a few simple tests to guess the base register. Additional
1417 tests can certainly be added. For example, if one of the operands
1418 is a shift or multiply, then it must be the index register and the
1419 other operand is the base register. */
1421 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1422 return find_base_term (tmp2);
1424 /* If either operand is known to be a pointer, then use it
1425 to determine the base term. */
1426 if (REG_P (tmp1) && REG_POINTER (tmp1))
1427 return find_base_term (tmp1);
1429 if (REG_P (tmp2) && REG_POINTER (tmp2))
1430 return find_base_term (tmp2);
1432 /* Neither operand was known to be a pointer. Go ahead and find the
1433 base term for both operands. */
1434 tmp1 = find_base_term (tmp1);
1435 tmp2 = find_base_term (tmp2);
1437 /* If either base term is named object or a special address
1438 (like an argument or stack reference), then use it for the
1441 && (GET_CODE (tmp1) == SYMBOL_REF
1442 || GET_CODE (tmp1) == LABEL_REF
1443 || (GET_CODE (tmp1) == ADDRESS
1444 && GET_MODE (tmp1) != VOIDmode)))
1448 && (GET_CODE (tmp2) == SYMBOL_REF
1449 || GET_CODE (tmp2) == LABEL_REF
1450 || (GET_CODE (tmp2) == ADDRESS
1451 && GET_MODE (tmp2) != VOIDmode)))
1454 /* We could not determine which of the two operands was the
1455 base register and which was the index. So we can determine
1456 nothing from the base alias check. */
1461 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0)
1462 return find_base_term (XEXP (x, 0));
1470 return REG_BASE_VALUE (frame_pointer_rtx);
1477 /* Return 0 if the addresses X and Y are known to point to different
1478 objects, 1 if they might be pointers to the same object. */
1481 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1482 enum machine_mode y_mode)
1484 rtx x_base = find_base_term (x);
1485 rtx y_base = find_base_term (y);
1487 /* If the address itself has no known base see if a known equivalent
1488 value has one. If either address still has no known base, nothing
1489 is known about aliasing. */
1494 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1497 x_base = find_base_term (x_c);
1505 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1508 y_base = find_base_term (y_c);
1513 /* If the base addresses are equal nothing is known about aliasing. */
1514 if (rtx_equal_p (x_base, y_base))
1517 /* The base addresses of the read and write are different expressions.
1518 If they are both symbols and they are not accessed via AND, there is
1519 no conflict. We can bring knowledge of object alignment into play
1520 here. For example, on alpha, "char a, b;" can alias one another,
1521 though "char a; long b;" cannot. */
1522 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1524 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1526 if (GET_CODE (x) == AND
1527 && (GET_CODE (XEXP (x, 1)) != CONST_INT
1528 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1530 if (GET_CODE (y) == AND
1531 && (GET_CODE (XEXP (y, 1)) != CONST_INT
1532 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1534 /* Differing symbols never alias. */
1538 /* If one address is a stack reference there can be no alias:
1539 stack references using different base registers do not alias,
1540 a stack reference can not alias a parameter, and a stack reference
1541 can not alias a global. */
1542 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1543 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1546 if (! flag_argument_noalias)
1549 if (flag_argument_noalias > 1)
1552 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1553 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1556 /* Convert the address X into something we can use. This is done by returning
1557 it unchanged unless it is a value; in the latter case we call cselib to get
1558 a more useful rtx. */
1564 struct elt_loc_list *l;
1566 if (GET_CODE (x) != VALUE)
1568 v = CSELIB_VAL_PTR (x);
1571 for (l = v->locs; l; l = l->next)
1572 if (CONSTANT_P (l->loc))
1574 for (l = v->locs; l; l = l->next)
1575 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
1578 return v->locs->loc;
1583 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1584 where SIZE is the size in bytes of the memory reference. If ADDR
1585 is not modified by the memory reference then ADDR is returned. */
1588 addr_side_effect_eval (rtx addr, int size, int n_refs)
1592 switch (GET_CODE (addr))
1595 offset = (n_refs + 1) * size;
1598 offset = -(n_refs + 1) * size;
1601 offset = n_refs * size;
1604 offset = -n_refs * size;
1612 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1615 addr = XEXP (addr, 0);
1616 addr = canon_rtx (addr);
1621 /* Return nonzero if X and Y (memory addresses) could reference the
1622 same location in memory. C is an offset accumulator. When
1623 C is nonzero, we are testing aliases between X and Y + C.
1624 XSIZE is the size in bytes of the X reference,
1625 similarly YSIZE is the size in bytes for Y.
1626 Expect that canon_rtx has been already called for X and Y.
1628 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1629 referenced (the reference was BLKmode), so make the most pessimistic
1632 If XSIZE or YSIZE is negative, we may access memory outside the object
1633 being referenced as a side effect. This can happen when using AND to
1634 align memory references, as is done on the Alpha.
1636 Nice to notice that varying addresses cannot conflict with fp if no
1637 local variables had their addresses taken, but that's too hard now. */
1640 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1642 if (GET_CODE (x) == VALUE)
1644 if (GET_CODE (y) == VALUE)
1646 if (GET_CODE (x) == HIGH)
1648 else if (GET_CODE (x) == LO_SUM)
1651 x = addr_side_effect_eval (x, xsize, 0);
1652 if (GET_CODE (y) == HIGH)
1654 else if (GET_CODE (y) == LO_SUM)
1657 y = addr_side_effect_eval (y, ysize, 0);
1659 if (rtx_equal_for_memref_p (x, y))
1661 if (xsize <= 0 || ysize <= 0)
1663 if (c >= 0 && xsize > c)
1665 if (c < 0 && ysize+c > 0)
1670 /* This code used to check for conflicts involving stack references and
1671 globals but the base address alias code now handles these cases. */
1673 if (GET_CODE (x) == PLUS)
1675 /* The fact that X is canonicalized means that this
1676 PLUS rtx is canonicalized. */
1677 rtx x0 = XEXP (x, 0);
1678 rtx x1 = XEXP (x, 1);
1680 if (GET_CODE (y) == PLUS)
1682 /* The fact that Y is canonicalized means that this
1683 PLUS rtx is canonicalized. */
1684 rtx y0 = XEXP (y, 0);
1685 rtx y1 = XEXP (y, 1);
1687 if (rtx_equal_for_memref_p (x1, y1))
1688 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1689 if (rtx_equal_for_memref_p (x0, y0))
1690 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1691 if (GET_CODE (x1) == CONST_INT)
1693 if (GET_CODE (y1) == CONST_INT)
1694 return memrefs_conflict_p (xsize, x0, ysize, y0,
1695 c - INTVAL (x1) + INTVAL (y1));
1697 return memrefs_conflict_p (xsize, x0, ysize, y,
1700 else if (GET_CODE (y1) == CONST_INT)
1701 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1705 else if (GET_CODE (x1) == CONST_INT)
1706 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1708 else if (GET_CODE (y) == PLUS)
1710 /* The fact that Y is canonicalized means that this
1711 PLUS rtx is canonicalized. */
1712 rtx y0 = XEXP (y, 0);
1713 rtx y1 = XEXP (y, 1);
1715 if (GET_CODE (y1) == CONST_INT)
1716 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1721 if (GET_CODE (x) == GET_CODE (y))
1722 switch (GET_CODE (x))
1726 /* Handle cases where we expect the second operands to be the
1727 same, and check only whether the first operand would conflict
1730 rtx x1 = canon_rtx (XEXP (x, 1));
1731 rtx y1 = canon_rtx (XEXP (y, 1));
1732 if (! rtx_equal_for_memref_p (x1, y1))
1734 x0 = canon_rtx (XEXP (x, 0));
1735 y0 = canon_rtx (XEXP (y, 0));
1736 if (rtx_equal_for_memref_p (x0, y0))
1737 return (xsize == 0 || ysize == 0
1738 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1740 /* Can't properly adjust our sizes. */
1741 if (GET_CODE (x1) != CONST_INT)
1743 xsize /= INTVAL (x1);
1744 ysize /= INTVAL (x1);
1746 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1750 /* Are these registers known not to be equal? */
1751 if (alias_invariant)
1753 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1754 rtx i_x, i_y; /* invariant relationships of X and Y */
1756 i_x = r_x >= alias_invariant_size ? 0 : alias_invariant[r_x];
1757 i_y = r_y >= alias_invariant_size ? 0 : alias_invariant[r_y];
1759 if (i_x == 0 && i_y == 0)
1762 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1763 ysize, i_y ? i_y : y, c))
1772 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1773 as an access with indeterminate size. Assume that references
1774 besides AND are aligned, so if the size of the other reference is
1775 at least as large as the alignment, assume no other overlap. */
1776 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1778 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1780 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1782 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1784 /* ??? If we are indexing far enough into the array/structure, we
1785 may yet be able to determine that we can not overlap. But we
1786 also need to that we are far enough from the end not to overlap
1787 a following reference, so we do nothing with that for now. */
1788 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1790 return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1793 if (GET_CODE (x) == ADDRESSOF)
1795 if (y == frame_pointer_rtx
1796 || GET_CODE (y) == ADDRESSOF)
1797 return xsize <= 0 || ysize <= 0;
1799 if (GET_CODE (y) == ADDRESSOF)
1801 if (x == frame_pointer_rtx)
1802 return xsize <= 0 || ysize <= 0;
1807 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1809 c += (INTVAL (y) - INTVAL (x));
1810 return (xsize <= 0 || ysize <= 0
1811 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1814 if (GET_CODE (x) == CONST)
1816 if (GET_CODE (y) == CONST)
1817 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1818 ysize, canon_rtx (XEXP (y, 0)), c);
1820 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1823 if (GET_CODE (y) == CONST)
1824 return memrefs_conflict_p (xsize, x, ysize,
1825 canon_rtx (XEXP (y, 0)), c);
1828 return (xsize <= 0 || ysize <= 0
1829 || (rtx_equal_for_memref_p (x, y)
1830 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1837 /* Functions to compute memory dependencies.
1839 Since we process the insns in execution order, we can build tables
1840 to keep track of what registers are fixed (and not aliased), what registers
1841 are varying in known ways, and what registers are varying in unknown
1844 If both memory references are volatile, then there must always be a
1845 dependence between the two references, since their order can not be
1846 changed. A volatile and non-volatile reference can be interchanged
1849 A MEM_IN_STRUCT reference at a non-AND varying address can never
1850 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1851 also must allow AND addresses, because they may generate accesses
1852 outside the object being referenced. This is used to generate
1853 aligned addresses from unaligned addresses, for instance, the alpha
1854 storeqi_unaligned pattern. */
1856 /* Read dependence: X is read after read in MEM takes place. There can
1857 only be a dependence here if both reads are volatile. */
1860 read_dependence (rtx mem, rtx x)
1862 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1865 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1866 MEM2 is a reference to a structure at a varying address, or returns
1867 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1868 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1869 to decide whether or not an address may vary; it should return
1870 nonzero whenever variation is possible.
1871 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1874 fixed_scalar_and_varying_struct_p (rtx mem1, rtx mem2, rtx mem1_addr,
1876 int (*varies_p) (rtx, int))
1878 if (! flag_strict_aliasing)
1881 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1882 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1883 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1887 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1888 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1889 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1896 /* Returns nonzero if something about the mode or address format MEM1
1897 indicates that it might well alias *anything*. */
1900 aliases_everything_p (rtx mem)
1902 if (GET_CODE (XEXP (mem, 0)) == AND)
1903 /* If the address is an AND, its very hard to know at what it is
1904 actually pointing. */
1910 /* Return true if we can determine that the fields referenced cannot
1911 overlap for any pair of objects. */
1914 nonoverlapping_component_refs_p (tree x, tree y)
1916 tree fieldx, fieldy, typex, typey, orig_y;
1920 /* The comparison has to be done at a common type, since we don't
1921 know how the inheritance hierarchy works. */
1925 fieldx = TREE_OPERAND (x, 1);
1926 typex = DECL_FIELD_CONTEXT (fieldx);
1931 fieldy = TREE_OPERAND (y, 1);
1932 typey = DECL_FIELD_CONTEXT (fieldy);
1937 y = TREE_OPERAND (y, 0);
1939 while (y && TREE_CODE (y) == COMPONENT_REF);
1941 x = TREE_OPERAND (x, 0);
1943 while (x && TREE_CODE (x) == COMPONENT_REF);
1945 /* Never found a common type. */
1949 /* If we're left with accessing different fields of a structure,
1951 if (TREE_CODE (typex) == RECORD_TYPE
1952 && fieldx != fieldy)
1955 /* The comparison on the current field failed. If we're accessing
1956 a very nested structure, look at the next outer level. */
1957 x = TREE_OPERAND (x, 0);
1958 y = TREE_OPERAND (y, 0);
1961 && TREE_CODE (x) == COMPONENT_REF
1962 && TREE_CODE (y) == COMPONENT_REF);
1967 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1970 decl_for_component_ref (tree x)
1974 x = TREE_OPERAND (x, 0);
1976 while (x && TREE_CODE (x) == COMPONENT_REF);
1978 return x && DECL_P (x) ? x : NULL_TREE;
1981 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1982 offset of the field reference. */
1985 adjust_offset_for_component_ref (tree x, rtx offset)
1987 HOST_WIDE_INT ioffset;
1992 ioffset = INTVAL (offset);
1995 tree field = TREE_OPERAND (x, 1);
1997 if (! host_integerp (DECL_FIELD_OFFSET (field), 1))
1999 ioffset += (tree_low_cst (DECL_FIELD_OFFSET (field), 1)
2000 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2003 x = TREE_OPERAND (x, 0);
2005 while (x && TREE_CODE (x) == COMPONENT_REF);
2007 return GEN_INT (ioffset);
2010 /* Return nonzero if we can determine the exprs corresponding to memrefs
2011 X and Y and they do not overlap. */
2014 nonoverlapping_memrefs_p (rtx x, rtx y)
2016 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2019 rtx moffsetx, moffsety;
2020 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
2022 /* Unless both have exprs, we can't tell anything. */
2023 if (exprx == 0 || expry == 0)
2026 /* If both are field references, we may be able to determine something. */
2027 if (TREE_CODE (exprx) == COMPONENT_REF
2028 && TREE_CODE (expry) == COMPONENT_REF
2029 && nonoverlapping_component_refs_p (exprx, expry))
2032 /* If the field reference test failed, look at the DECLs involved. */
2033 moffsetx = MEM_OFFSET (x);
2034 if (TREE_CODE (exprx) == COMPONENT_REF)
2036 tree t = decl_for_component_ref (exprx);
2039 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
2042 else if (TREE_CODE (exprx) == INDIRECT_REF)
2044 exprx = TREE_OPERAND (exprx, 0);
2045 if (flag_argument_noalias < 2
2046 || TREE_CODE (exprx) != PARM_DECL)
2050 moffsety = MEM_OFFSET (y);
2051 if (TREE_CODE (expry) == COMPONENT_REF)
2053 tree t = decl_for_component_ref (expry);
2056 moffsety = adjust_offset_for_component_ref (expry, moffsety);
2059 else if (TREE_CODE (expry) == INDIRECT_REF)
2061 expry = TREE_OPERAND (expry, 0);
2062 if (flag_argument_noalias < 2
2063 || TREE_CODE (expry) != PARM_DECL)
2067 if (! DECL_P (exprx) || ! DECL_P (expry))
2070 rtlx = DECL_RTL (exprx);
2071 rtly = DECL_RTL (expry);
2073 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2074 can't overlap unless they are the same because we never reuse that part
2075 of the stack frame used for locals for spilled pseudos. */
2076 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM)
2077 && ! rtx_equal_p (rtlx, rtly))
2080 /* Get the base and offsets of both decls. If either is a register, we
2081 know both are and are the same, so use that as the base. The only
2082 we can avoid overlap is if we can deduce that they are nonoverlapping
2083 pieces of that decl, which is very rare. */
2084 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx;
2085 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT)
2086 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2088 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly;
2089 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT)
2090 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2092 /* If the bases are different, we know they do not overlap if both
2093 are constants or if one is a constant and the other a pointer into the
2094 stack frame. Otherwise a different base means we can't tell if they
2096 if (! rtx_equal_p (basex, basey))
2097 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2098 || (CONSTANT_P (basex) && REG_P (basey)
2099 && REGNO_PTR_FRAME_P (REGNO (basey)))
2100 || (CONSTANT_P (basey) && REG_P (basex)
2101 && REGNO_PTR_FRAME_P (REGNO (basex))));
2103 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2104 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2106 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2107 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2110 /* If we have an offset for either memref, it can update the values computed
2113 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2115 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2117 /* If a memref has both a size and an offset, we can use the smaller size.
2118 We can't do this if the offset isn't known because we must view this
2119 memref as being anywhere inside the DECL's MEM. */
2120 if (MEM_SIZE (x) && moffsetx)
2121 sizex = INTVAL (MEM_SIZE (x));
2122 if (MEM_SIZE (y) && moffsety)
2123 sizey = INTVAL (MEM_SIZE (y));
2125 /* Put the values of the memref with the lower offset in X's values. */
2126 if (offsetx > offsety)
2128 tem = offsetx, offsetx = offsety, offsety = tem;
2129 tem = sizex, sizex = sizey, sizey = tem;
2132 /* If we don't know the size of the lower-offset value, we can't tell
2133 if they conflict. Otherwise, we do the test. */
2134 return sizex >= 0 && offsety >= offsetx + sizex;
2137 /* True dependence: X is read after store in MEM takes place. */
2140 true_dependence (rtx mem, enum machine_mode mem_mode, rtx x,
2141 int (*varies) (rtx, int))
2143 rtx x_addr, mem_addr;
2146 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2149 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2150 This is used in epilogue deallocation functions. */
2151 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2153 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2156 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2159 /* Unchanging memory can't conflict with non-unchanging memory.
2160 A non-unchanging read can conflict with a non-unchanging write.
2161 An unchanging read can conflict with an unchanging write since
2162 there may be a single store to this address to initialize it.
2163 Note that an unchanging store can conflict with a non-unchanging read
2164 since we have to make conservative assumptions when we have a
2165 record with readonly fields and we are copying the whole thing.
2166 Just fall through to the code below to resolve potential conflicts.
2167 This won't handle all cases optimally, but the possible performance
2168 loss should be negligible. */
2169 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2172 if (nonoverlapping_memrefs_p (mem, x))
2175 if (mem_mode == VOIDmode)
2176 mem_mode = GET_MODE (mem);
2178 x_addr = get_addr (XEXP (x, 0));
2179 mem_addr = get_addr (XEXP (mem, 0));
2181 base = find_base_term (x_addr);
2182 if (base && (GET_CODE (base) == LABEL_REF
2183 || (GET_CODE (base) == SYMBOL_REF
2184 && CONSTANT_POOL_ADDRESS_P (base))))
2187 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2190 x_addr = canon_rtx (x_addr);
2191 mem_addr = canon_rtx (mem_addr);
2193 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2194 SIZE_FOR_MODE (x), x_addr, 0))
2197 if (aliases_everything_p (x))
2200 /* We cannot use aliases_everything_p to test MEM, since we must look
2201 at MEM_MODE, rather than GET_MODE (MEM). */
2202 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2205 /* In true_dependence we also allow BLKmode to alias anything. Why
2206 don't we do this in anti_dependence and output_dependence? */
2207 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2210 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2214 /* Canonical true dependence: X is read after store in MEM takes place.
2215 Variant of true_dependence which assumes MEM has already been
2216 canonicalized (hence we no longer do that here).
2217 The mem_addr argument has been added, since true_dependence computed
2218 this value prior to canonicalizing. */
2221 canon_true_dependence (rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2222 rtx x, int (*varies) (rtx, int))
2226 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2229 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2230 This is used in epilogue deallocation functions. */
2231 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2233 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2236 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2239 /* If X is an unchanging read, then it can't possibly conflict with any
2240 non-unchanging store. It may conflict with an unchanging write though,
2241 because there may be a single store to this address to initialize it.
2242 Just fall through to the code below to resolve the case where we have
2243 both an unchanging read and an unchanging write. This won't handle all
2244 cases optimally, but the possible performance loss should be
2246 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2249 if (nonoverlapping_memrefs_p (x, mem))
2252 x_addr = get_addr (XEXP (x, 0));
2254 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2257 x_addr = canon_rtx (x_addr);
2258 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2259 SIZE_FOR_MODE (x), x_addr, 0))
2262 if (aliases_everything_p (x))
2265 /* We cannot use aliases_everything_p to test MEM, since we must look
2266 at MEM_MODE, rather than GET_MODE (MEM). */
2267 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2270 /* In true_dependence we also allow BLKmode to alias anything. Why
2271 don't we do this in anti_dependence and output_dependence? */
2272 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2275 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2279 /* Returns nonzero if a write to X might alias a previous read from
2280 (or, if WRITEP is nonzero, a write to) MEM. If CONSTP is nonzero,
2281 honor the RTX_UNCHANGING_P flags on X and MEM. */
2284 write_dependence_p (rtx mem, rtx x, int writep, int constp)
2286 rtx x_addr, mem_addr;
2290 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2293 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2294 This is used in epilogue deallocation functions. */
2295 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2297 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2300 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2305 /* Unchanging memory can't conflict with non-unchanging memory. */
2306 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem))
2309 /* If MEM is an unchanging read, then it can't possibly conflict with
2310 the store to X, because there is at most one store to MEM, and it
2311 must have occurred somewhere before MEM. */
2312 if (! writep && RTX_UNCHANGING_P (mem))
2316 if (nonoverlapping_memrefs_p (x, mem))
2319 x_addr = get_addr (XEXP (x, 0));
2320 mem_addr = get_addr (XEXP (mem, 0));
2324 base = find_base_term (mem_addr);
2325 if (base && (GET_CODE (base) == LABEL_REF
2326 || (GET_CODE (base) == SYMBOL_REF
2327 && CONSTANT_POOL_ADDRESS_P (base))))
2331 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2335 x_addr = canon_rtx (x_addr);
2336 mem_addr = canon_rtx (mem_addr);
2338 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2339 SIZE_FOR_MODE (x), x_addr, 0))
2343 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2346 return (!(fixed_scalar == mem && !aliases_everything_p (x))
2347 && !(fixed_scalar == x && !aliases_everything_p (mem)));
2350 /* Anti dependence: X is written after read in MEM takes place. */
2353 anti_dependence (rtx mem, rtx x)
2355 return write_dependence_p (mem, x, /*writep=*/0, /*constp*/1);
2358 /* Output dependence: X is written after store in MEM takes place. */
2361 output_dependence (rtx mem, rtx x)
2363 return write_dependence_p (mem, x, /*writep=*/1, /*constp*/1);
2366 /* Unchanging anti dependence: Like anti_dependence but ignores
2367 the UNCHANGING_RTX_P property on const variable references. */
2370 unchanging_anti_dependence (rtx mem, rtx x)
2372 return write_dependence_p (mem, x, /*writep=*/0, /*constp*/0);
2375 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2376 something which is not local to the function and is not constant. */
2379 nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2388 switch (GET_CODE (x))
2391 if (GET_CODE (SUBREG_REG (x)) == REG)
2393 /* Global registers are not local. */
2394 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
2395 && global_regs[subreg_regno (x)])
2403 /* Global registers are not local. */
2404 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2419 /* Constants in the function's constants pool are constant. */
2420 if (CONSTANT_POOL_ADDRESS_P (x))
2425 /* Non-constant calls and recursion are not local. */
2429 /* Be overly conservative and consider any volatile memory
2430 reference as not local. */
2431 if (MEM_VOLATILE_P (x))
2433 base = find_base_term (XEXP (x, 0));
2436 /* A Pmode ADDRESS could be a reference via the structure value
2437 address or static chain. Such memory references are nonlocal.
2439 Thus, we have to examine the contents of the ADDRESS to find
2440 out if this is a local reference or not. */
2441 if (GET_CODE (base) == ADDRESS
2442 && GET_MODE (base) == Pmode
2443 && (XEXP (base, 0) == stack_pointer_rtx
2444 || XEXP (base, 0) == arg_pointer_rtx
2445 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2446 || XEXP (base, 0) == hard_frame_pointer_rtx
2448 || XEXP (base, 0) == frame_pointer_rtx))
2450 /* Constants in the function's constant pool are constant. */
2451 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
2456 case UNSPEC_VOLATILE:
2461 if (MEM_VOLATILE_P (x))
2473 /* Returns nonzero if X might mention something which is not
2474 local to the function and is not constant. */
2477 nonlocal_mentioned_p (rtx x)
2481 if (GET_CODE (x) == CALL_INSN)
2483 if (! CONST_OR_PURE_CALL_P (x))
2485 x = CALL_INSN_FUNCTION_USAGE (x);
2493 return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL);
2496 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2497 something which is not local to the function and is not constant. */
2500 nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2507 switch (GET_CODE (x))
2513 return nonlocal_mentioned_p (x);
2516 /* Non-constant calls and recursion are not local. */
2520 if (nonlocal_mentioned_p (SET_SRC (x)))
2523 if (GET_CODE (SET_DEST (x)) == MEM)
2524 return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0));
2526 /* If the destination is anything other than a CC0, PC,
2527 MEM, REG, or a SUBREG of a REG that occupies all of
2528 the REG, then X references nonlocal memory if it is
2529 mentioned in the destination. */
2530 if (GET_CODE (SET_DEST (x)) != CC0
2531 && GET_CODE (SET_DEST (x)) != PC
2532 && GET_CODE (SET_DEST (x)) != REG
2533 && ! (GET_CODE (SET_DEST (x)) == SUBREG
2534 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
2535 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
2536 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
2537 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
2538 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
2539 return nonlocal_mentioned_p (SET_DEST (x));
2543 if (GET_CODE (XEXP (x, 0)) == MEM)
2544 return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0));
2548 return nonlocal_mentioned_p (XEXP (x, 0));
2551 case UNSPEC_VOLATILE:
2555 if (MEM_VOLATILE_P (x))
2567 /* Returns nonzero if X might reference something which is not
2568 local to the function and is not constant. */
2571 nonlocal_referenced_p (rtx x)
2575 if (GET_CODE (x) == CALL_INSN)
2577 if (! CONST_OR_PURE_CALL_P (x))
2579 x = CALL_INSN_FUNCTION_USAGE (x);
2587 return for_each_rtx (&x, nonlocal_referenced_p_1, NULL);
2590 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2591 something which is not local to the function and is not constant. */
2594 nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2601 switch (GET_CODE (x))
2604 /* Non-constant calls and recursion are not local. */
2613 return nonlocal_mentioned_p (XEXP (x, 0));
2616 if (nonlocal_mentioned_p (SET_DEST (x)))
2618 return nonlocal_set_p (SET_SRC (x));
2621 return nonlocal_mentioned_p (XEXP (x, 0));
2627 case UNSPEC_VOLATILE:
2631 if (MEM_VOLATILE_P (x))
2643 /* Returns nonzero if X might set something which is not
2644 local to the function and is not constant. */
2647 nonlocal_set_p (rtx x)
2651 if (GET_CODE (x) == CALL_INSN)
2653 if (! CONST_OR_PURE_CALL_P (x))
2655 x = CALL_INSN_FUNCTION_USAGE (x);
2663 return for_each_rtx (&x, nonlocal_set_p_1, NULL);
2666 /* Mark the function if it is pure or constant. */
2669 mark_constant_function (void)
2672 int nonlocal_memory_referenced;
2674 if (TREE_READONLY (current_function_decl)
2675 || DECL_IS_PURE (current_function_decl)
2676 || TREE_THIS_VOLATILE (current_function_decl)
2677 || current_function_has_nonlocal_goto
2678 || !(*targetm.binds_local_p) (current_function_decl))
2681 /* A loop might not return which counts as a side effect. */
2682 if (mark_dfs_back_edges ())
2685 nonlocal_memory_referenced = 0;
2687 init_alias_analysis ();
2689 /* Determine if this is a constant or pure function. */
2691 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2693 if (! INSN_P (insn))
2696 if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn)
2697 || volatile_refs_p (PATTERN (insn)))
2700 if (! nonlocal_memory_referenced)
2701 nonlocal_memory_referenced = nonlocal_referenced_p (insn);
2704 end_alias_analysis ();
2706 /* Mark the function. */
2710 else if (nonlocal_memory_referenced)
2712 cgraph_rtl_info (current_function_decl)->pure_function = 1;
2713 DECL_IS_PURE (current_function_decl) = 1;
2717 cgraph_rtl_info (current_function_decl)->const_function = 1;
2718 TREE_READONLY (current_function_decl) = 1;
2724 init_alias_once (void)
2728 #ifndef OUTGOING_REGNO
2729 #define OUTGOING_REGNO(N) N
2731 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2732 /* Check whether this register can hold an incoming pointer
2733 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2734 numbers, so translate if necessary due to register windows. */
2735 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2736 && HARD_REGNO_MODE_OK (i, Pmode))
2737 static_reg_base_value[i]
2738 = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2740 static_reg_base_value[STACK_POINTER_REGNUM]
2741 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2742 static_reg_base_value[ARG_POINTER_REGNUM]
2743 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2744 static_reg_base_value[FRAME_POINTER_REGNUM]
2745 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2746 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2747 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2748 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2752 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2753 to be memory reference. */
2754 static bool memory_modified;
2756 memory_modified_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
2758 if (GET_CODE (x) == MEM)
2760 if (anti_dependence (x, (rtx)data) || output_dependence (x, (rtx)data))
2761 memory_modified = true;
2766 /* Return true when INSN possibly modify memory contents of MEM
2767 (ie address can be modified). */
2769 memory_modified_in_insn_p (rtx mem, rtx insn)
2773 memory_modified = false;
2774 note_stores (PATTERN (insn), memory_modified_1, mem);
2775 return memory_modified;
2778 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2782 init_alias_analysis (void)
2784 unsigned int maxreg = max_reg_num ();
2790 timevar_push (TV_ALIAS_ANALYSIS);
2792 reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER;
2793 reg_known_value = ggc_calloc (reg_known_value_size, sizeof (rtx));
2794 reg_known_equiv_p = xcalloc (reg_known_value_size, sizeof (bool));
2796 /* Overallocate reg_base_value to allow some growth during loop
2797 optimization. Loop unrolling can create a large number of
2799 if (old_reg_base_value)
2801 reg_base_value = old_reg_base_value;
2802 /* If varray gets large zeroing cost may get important. */
2803 if (VARRAY_SIZE (reg_base_value) > 256
2804 && VARRAY_SIZE (reg_base_value) > 4 * maxreg)
2805 VARRAY_GROW (reg_base_value, maxreg);
2806 VARRAY_CLEAR (reg_base_value);
2807 if (VARRAY_SIZE (reg_base_value) < maxreg)
2808 VARRAY_GROW (reg_base_value, maxreg);
2812 VARRAY_RTX_INIT (reg_base_value, maxreg, "reg_base_value");
2815 new_reg_base_value = xmalloc (maxreg * sizeof (rtx));
2816 reg_seen = xmalloc (maxreg);
2817 if (! reload_completed && flag_old_unroll_loops)
2819 alias_invariant = ggc_calloc (maxreg, sizeof (rtx));
2820 alias_invariant_size = maxreg;
2823 /* The basic idea is that each pass through this loop will use the
2824 "constant" information from the previous pass to propagate alias
2825 information through another level of assignments.
2827 This could get expensive if the assignment chains are long. Maybe
2828 we should throttle the number of iterations, possibly based on
2829 the optimization level or flag_expensive_optimizations.
2831 We could propagate more information in the first pass by making use
2832 of REG_N_SETS to determine immediately that the alias information
2833 for a pseudo is "constant".
2835 A program with an uninitialized variable can cause an infinite loop
2836 here. Instead of doing a full dataflow analysis to detect such problems
2837 we just cap the number of iterations for the loop.
2839 The state of the arrays for the set chain in question does not matter
2840 since the program has undefined behavior. */
2845 /* Assume nothing will change this iteration of the loop. */
2848 /* We want to assign the same IDs each iteration of this loop, so
2849 start counting from zero each iteration of the loop. */
2852 /* We're at the start of the function each iteration through the
2853 loop, so we're copying arguments. */
2854 copying_arguments = true;
2856 /* Wipe the potential alias information clean for this pass. */
2857 memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2859 /* Wipe the reg_seen array clean. */
2860 memset (reg_seen, 0, maxreg);
2862 /* Mark all hard registers which may contain an address.
2863 The stack, frame and argument pointers may contain an address.
2864 An argument register which can hold a Pmode value may contain
2865 an address even if it is not in BASE_REGS.
2867 The address expression is VOIDmode for an argument and
2868 Pmode for other registers. */
2870 memcpy (new_reg_base_value, static_reg_base_value,
2871 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2873 /* Walk the insns adding values to the new_reg_base_value array. */
2874 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2880 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2881 /* The prologue/epilogue insns are not threaded onto the
2882 insn chain until after reload has completed. Thus,
2883 there is no sense wasting time checking if INSN is in
2884 the prologue/epilogue until after reload has completed. */
2885 if (reload_completed
2886 && prologue_epilogue_contains (insn))
2890 /* If this insn has a noalias note, process it, Otherwise,
2891 scan for sets. A simple set will have no side effects
2892 which could change the base value of any other register. */
2894 if (GET_CODE (PATTERN (insn)) == SET
2895 && REG_NOTES (insn) != 0
2896 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2897 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2899 note_stores (PATTERN (insn), record_set, NULL);
2901 set = single_set (insn);
2904 && GET_CODE (SET_DEST (set)) == REG
2905 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2907 unsigned int regno = REGNO (SET_DEST (set));
2908 rtx src = SET_SRC (set);
2911 if (REG_NOTES (insn) != 0
2912 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2913 && REG_N_SETS (regno) == 1)
2914 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
2915 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2916 && ! rtx_varies_p (XEXP (note, 0), 1)
2917 && ! reg_overlap_mentioned_p (SET_DEST (set),
2920 set_reg_known_value (regno, XEXP (note, 0));
2921 set_reg_known_equiv_p (regno,
2922 REG_NOTE_KIND (note) == REG_EQUIV);
2924 else if (REG_N_SETS (regno) == 1
2925 && GET_CODE (src) == PLUS
2926 && GET_CODE (XEXP (src, 0)) == REG
2927 && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2928 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2930 t = plus_constant (t, INTVAL (XEXP (src, 1)));
2931 set_reg_known_value (regno, t);
2932 set_reg_known_equiv_p (regno, 0);
2934 else if (REG_N_SETS (regno) == 1
2935 && ! rtx_varies_p (src, 1))
2937 set_reg_known_value (regno, src);
2938 set_reg_known_equiv_p (regno, 0);
2942 else if (GET_CODE (insn) == NOTE
2943 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
2944 copying_arguments = false;
2947 /* Now propagate values from new_reg_base_value to reg_base_value. */
2948 if (maxreg != (unsigned int) max_reg_num())
2950 for (ui = 0; ui < maxreg; ui++)
2952 if (new_reg_base_value[ui]
2953 && new_reg_base_value[ui] != VARRAY_RTX (reg_base_value, ui)
2954 && ! rtx_equal_p (new_reg_base_value[ui],
2955 VARRAY_RTX (reg_base_value, ui)))
2957 VARRAY_RTX (reg_base_value, ui) = new_reg_base_value[ui];
2962 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2964 /* Fill in the remaining entries. */
2965 for (i = 0; i < (int)reg_known_value_size; i++)
2966 if (reg_known_value[i] == 0)
2967 reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER];
2969 /* Simplify the reg_base_value array so that no register refers to
2970 another register, except to special registers indirectly through
2971 ADDRESS expressions.
2973 In theory this loop can take as long as O(registers^2), but unless
2974 there are very long dependency chains it will run in close to linear
2977 This loop may not be needed any longer now that the main loop does
2978 a better job at propagating alias information. */
2984 for (ui = 0; ui < maxreg; ui++)
2986 rtx base = VARRAY_RTX (reg_base_value, ui);
2987 if (base && GET_CODE (base) == REG)
2989 unsigned int base_regno = REGNO (base);
2990 if (base_regno == ui) /* register set from itself */
2991 VARRAY_RTX (reg_base_value, ui) = 0;
2993 VARRAY_RTX (reg_base_value, ui)
2994 = VARRAY_RTX (reg_base_value, base_regno);
2999 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
3002 free (new_reg_base_value);
3003 new_reg_base_value = 0;
3006 timevar_pop (TV_ALIAS_ANALYSIS);
3010 end_alias_analysis (void)
3012 old_reg_base_value = reg_base_value;
3013 reg_known_value = 0;
3014 reg_known_value_size = 0;
3015 free (reg_known_equiv_p);
3016 reg_known_equiv_p = 0;
3017 if (alias_invariant)
3019 alias_invariant = 0;
3020 alias_invariant_size = 0;
3024 #include "gt-alias.h"