1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
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"
46 /* The alias sets assigned to MEMs assist the back-end in determining
47 which MEMs can alias which other MEMs. In general, two MEMs in
48 different alias sets cannot alias each other, with one important
49 exception. Consider something like:
51 struct S {int i; double d; };
53 a store to an `S' can alias something of either type `int' or type
54 `double'. (However, a store to an `int' cannot alias a `double'
55 and vice versa.) We indicate this via a tree structure that looks
63 (The arrows are directed and point downwards.)
64 In this situation we say the alias set for `struct S' is the
65 `superset' and that those for `int' and `double' are `subsets'.
67 To see whether two alias sets can point to the same memory, we must
68 see if either alias set is a subset of the other. We need not trace
69 past immediate descendants, however, since we propagate all
70 grandchildren up one level.
72 Alias set zero is implicitly a superset of all other alias sets.
73 However, this is no actual entry for alias set zero. It is an
74 error to attempt to explicitly construct a subset of zero. */
76 typedef struct alias_set_entry
78 /* The alias set number, as stored in MEM_ALIAS_SET. */
79 HOST_WIDE_INT alias_set;
81 /* The children of the alias set. These are not just the immediate
82 children, but, in fact, all descendants. So, if we have:
84 struct T { struct S s; float f; }
86 continuing our example above, the children here will be all of
87 `int', `double', `float', and `struct S'. */
90 /* Nonzero if would have a child of zero: this effectively makes this
91 alias set the same as alias set zero. */
95 static int rtx_equal_for_memref_p (rtx, rtx);
96 static rtx find_symbolic_term (rtx);
97 static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
98 static void record_set (rtx, rtx, void *);
99 static int base_alias_check (rtx, rtx, enum machine_mode,
101 static rtx find_base_value (rtx);
102 static int mems_in_disjoint_alias_sets_p (rtx, rtx);
103 static int insert_subset_children (splay_tree_node, void*);
104 static tree find_base_decl (tree);
105 static alias_set_entry get_alias_set_entry (HOST_WIDE_INT);
106 static rtx fixed_scalar_and_varying_struct_p (rtx, rtx, rtx, rtx,
108 static int aliases_everything_p (rtx);
109 static bool nonoverlapping_component_refs_p (tree, tree);
110 static tree decl_for_component_ref (tree);
111 static rtx adjust_offset_for_component_ref (tree, rtx);
112 static int nonoverlapping_memrefs_p (rtx, rtx);
113 static int write_dependence_p (rtx, rtx, int, int);
115 static int nonlocal_mentioned_p_1 (rtx *, void *);
116 static int nonlocal_mentioned_p (rtx);
117 static int nonlocal_referenced_p_1 (rtx *, void *);
118 static int nonlocal_referenced_p (rtx);
119 static int nonlocal_set_p_1 (rtx *, void *);
120 static int nonlocal_set_p (rtx);
121 static void memory_modified_1 (rtx, rtx, void *);
123 /* Set up all info needed to perform alias analysis on memory references. */
125 /* Returns the size in bytes of the mode of X. */
126 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
128 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
129 different alias sets. We ignore alias sets in functions making use
130 of variable arguments because the va_arg macros on some systems are
132 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
133 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
135 /* Cap the number of passes we make over the insns propagating alias
136 information through set chains. 10 is a completely arbitrary choice. */
137 #define MAX_ALIAS_LOOP_PASSES 10
139 /* reg_base_value[N] gives an address to which register N is related.
140 If all sets after the first add or subtract to the current value
141 or otherwise modify it so it does not point to a different top level
142 object, reg_base_value[N] is equal to the address part of the source
145 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
146 expressions represent certain special values: function arguments and
147 the stack, frame, and argument pointers.
149 The contents of an ADDRESS is not normally used, the mode of the
150 ADDRESS determines whether the ADDRESS is a function argument or some
151 other special value. Pointer equality, not rtx_equal_p, determines whether
152 two ADDRESS expressions refer to the same base address.
154 The only use of the contents of an ADDRESS is for determining if the
155 current function performs nonlocal memory memory references for the
156 purposes of marking the function as a constant function. */
158 static GTY((length ("reg_base_value_size"))) rtx *reg_base_value;
159 static rtx *new_reg_base_value;
160 static unsigned int reg_base_value_size; /* size of reg_base_value array */
162 /* Static hunks of RTL used by the aliasing code; these are initialized
163 once per function to avoid unnecessary RTL allocations. */
164 static GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER];
166 #define REG_BASE_VALUE(X) \
167 (REGNO (X) < reg_base_value_size \
168 ? reg_base_value[REGNO (X)] : 0)
170 /* Vector of known invariant relationships between registers. Set in
171 loop unrolling. Indexed by register number, if nonzero the value
172 is an expression describing this register in terms of another.
174 The length of this array is REG_BASE_VALUE_SIZE.
176 Because this array contains only pseudo registers it has no effect
178 static rtx *alias_invariant;
180 /* Vector indexed by N giving the initial (unchanging) value known for
181 pseudo-register N. This array is initialized in
182 init_alias_analysis, and does not change until end_alias_analysis
184 rtx *reg_known_value;
186 /* Indicates number of valid entries in reg_known_value. */
187 static unsigned int reg_known_value_size;
189 /* Vector recording for each reg_known_value whether it is due to a
190 REG_EQUIV note. Future passes (viz., reload) may replace the
191 pseudo with the equivalent expression and so we account for the
192 dependences that would be introduced if that happens.
194 The REG_EQUIV notes created in assign_parms may mention the arg
195 pointer, and there are explicit insns in the RTL that modify the
196 arg pointer. Thus we must ensure that such insns don't get
197 scheduled across each other because that would invalidate the
198 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
199 wrong, but solving the problem in the scheduler will likely give
200 better code, so we do it here. */
201 char *reg_known_equiv_p;
203 /* True when scanning insns from the start of the rtl to the
204 NOTE_INSN_FUNCTION_BEG note. */
205 static bool copying_arguments;
207 /* The splay-tree used to store the various alias set entries. */
208 static splay_tree alias_sets;
210 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
211 such an entry, or NULL otherwise. */
213 static alias_set_entry
214 get_alias_set_entry (HOST_WIDE_INT alias_set)
217 = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
219 return sn != 0 ? ((alias_set_entry) sn->value) : 0;
222 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
223 the two MEMs cannot alias each other. */
226 mems_in_disjoint_alias_sets_p (rtx mem1, rtx mem2)
228 #ifdef ENABLE_CHECKING
229 /* Perform a basic sanity check. Namely, that there are no alias sets
230 if we're not using strict aliasing. This helps to catch bugs
231 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
232 where a MEM is allocated in some way other than by the use of
233 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
234 use alias sets to indicate that spilled registers cannot alias each
235 other, we might need to remove this check. */
236 if (! flag_strict_aliasing
237 && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0))
241 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
244 /* Insert the NODE into the splay tree given by DATA. Used by
245 record_alias_subset via splay_tree_foreach. */
248 insert_subset_children (splay_tree_node node, void *data)
250 splay_tree_insert ((splay_tree) data, node->key, node->value);
255 /* Return 1 if the two specified alias sets may conflict. */
258 alias_sets_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2)
262 /* If have no alias set information for one of the operands, we have
263 to assume it can alias anything. */
264 if (set1 == 0 || set2 == 0
265 /* If the two alias sets are the same, they may alias. */
269 /* See if the first alias set is a subset of the second. */
270 ase = get_alias_set_entry (set1);
272 && (ase->has_zero_child
273 || splay_tree_lookup (ase->children,
274 (splay_tree_key) set2)))
277 /* Now do the same, but with the alias sets reversed. */
278 ase = get_alias_set_entry (set2);
280 && (ase->has_zero_child
281 || splay_tree_lookup (ase->children,
282 (splay_tree_key) set1)))
285 /* The two alias sets are distinct and neither one is the
286 child of the other. Therefore, they cannot alias. */
290 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
291 has any readonly fields. If any of the fields have types that
292 contain readonly fields, return true as well. */
295 readonly_fields_p (tree type)
299 if (TREE_CODE (type) != RECORD_TYPE && TREE_CODE (type) != UNION_TYPE
300 && TREE_CODE (type) != QUAL_UNION_TYPE)
303 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
304 if (TREE_CODE (field) == FIELD_DECL
305 && (TREE_READONLY (field)
306 || readonly_fields_p (TREE_TYPE (field))))
312 /* Return 1 if any MEM object of type T1 will always conflict (using the
313 dependency routines in this file) with any MEM object of type T2.
314 This is used when allocating temporary storage. If T1 and/or T2 are
315 NULL_TREE, it means we know nothing about the storage. */
318 objects_must_conflict_p (tree t1, tree t2)
320 HOST_WIDE_INT set1, set2;
322 /* If neither has a type specified, we don't know if they'll conflict
323 because we may be using them to store objects of various types, for
324 example the argument and local variables areas of inlined functions. */
325 if (t1 == 0 && t2 == 0)
328 /* If one or the other has readonly fields or is readonly,
329 then they may not conflict. */
330 if ((t1 != 0 && readonly_fields_p (t1))
331 || (t2 != 0 && readonly_fields_p (t2))
332 || (t1 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t1))
333 || (t2 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t2)))
336 /* If they are the same type, they must conflict. */
338 /* Likewise if both are volatile. */
339 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
342 set1 = t1 ? get_alias_set (t1) : 0;
343 set2 = t2 ? get_alias_set (t2) : 0;
345 /* Otherwise they conflict if they have no alias set or the same. We
346 can't simply use alias_sets_conflict_p here, because we must make
347 sure that every subtype of t1 will conflict with every subtype of
348 t2 for which a pair of subobjects of these respective subtypes
349 overlaps on the stack. */
350 return set1 == 0 || set2 == 0 || set1 == set2;
353 /* T is an expression with pointer type. Find the DECL on which this
354 expression is based. (For example, in `a[i]' this would be `a'.)
355 If there is no such DECL, or a unique decl cannot be determined,
356 NULL_TREE is returned. */
359 find_base_decl (tree t)
363 if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
366 /* If this is a declaration, return it. */
367 if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd')
370 /* Handle general expressions. It would be nice to deal with
371 COMPONENT_REFs here. If we could tell that `a' and `b' were the
372 same, then `a->f' and `b->f' are also the same. */
373 switch (TREE_CODE_CLASS (TREE_CODE (t)))
376 return find_base_decl (TREE_OPERAND (t, 0));
379 /* Return 0 if found in neither or both are the same. */
380 d0 = find_base_decl (TREE_OPERAND (t, 0));
381 d1 = find_base_decl (TREE_OPERAND (t, 1));
392 d0 = find_base_decl (TREE_OPERAND (t, 0));
393 d1 = find_base_decl (TREE_OPERAND (t, 1));
394 d2 = find_base_decl (TREE_OPERAND (t, 2));
396 /* Set any nonzero values from the last, then from the first. */
397 if (d1 == 0) d1 = d2;
398 if (d0 == 0) d0 = d1;
399 if (d1 == 0) d1 = d0;
400 if (d2 == 0) d2 = d1;
402 /* At this point all are nonzero or all are zero. If all three are the
403 same, return it. Otherwise, return zero. */
404 return (d0 == d1 && d1 == d2) ? d0 : 0;
411 /* Return 1 if all the nested component references handled by
412 get_inner_reference in T are such that we can address the object in T. */
415 can_address_p (tree t)
417 /* If we're at the end, it is vacuously addressable. */
418 if (! handled_component_p (t))
421 /* Bitfields are never addressable. */
422 else if (TREE_CODE (t) == BIT_FIELD_REF)
425 /* Fields are addressable unless they are marked as nonaddressable or
426 the containing type has alias set 0. */
427 else if (TREE_CODE (t) == COMPONENT_REF
428 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))
429 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
430 && can_address_p (TREE_OPERAND (t, 0)))
433 /* Likewise for arrays. */
434 else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
435 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))
436 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
437 && can_address_p (TREE_OPERAND (t, 0)))
443 /* Return the alias set for T, which may be either a type or an
444 expression. Call language-specific routine for help, if needed. */
447 get_alias_set (tree t)
451 /* If we're not doing any alias analysis, just assume everything
452 aliases everything else. Also return 0 if this or its type is
454 if (! flag_strict_aliasing || t == error_mark_node
456 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
459 /* We can be passed either an expression or a type. This and the
460 language-specific routine may make mutually-recursive calls to each other
461 to figure out what to do. At each juncture, we see if this is a tree
462 that the language may need to handle specially. First handle things that
467 tree placeholder_ptr = 0;
469 /* Remove any nops, then give the language a chance to do
470 something with this tree before we look at it. */
472 set = (*lang_hooks.get_alias_set) (t);
476 /* First see if the actual object referenced is an INDIRECT_REF from a
477 restrict-qualified pointer or a "void *". Replace
478 PLACEHOLDER_EXPRs. */
479 while (TREE_CODE (inner) == PLACEHOLDER_EXPR
480 || handled_component_p (inner))
482 if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
483 inner = find_placeholder (inner, &placeholder_ptr);
485 inner = TREE_OPERAND (inner, 0);
490 /* Check for accesses through restrict-qualified pointers. */
491 if (TREE_CODE (inner) == INDIRECT_REF)
493 tree decl = find_base_decl (TREE_OPERAND (inner, 0));
495 if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
497 /* If we haven't computed the actual alias set, do it now. */
498 if (DECL_POINTER_ALIAS_SET (decl) == -2)
500 /* No two restricted pointers can point at the same thing.
501 However, a restricted pointer can point at the same thing
502 as an unrestricted pointer, if that unrestricted pointer
503 is based on the restricted pointer. So, we make the
504 alias set for the restricted pointer a subset of the
505 alias set for the type pointed to by the type of the
507 HOST_WIDE_INT pointed_to_alias_set
508 = get_alias_set (TREE_TYPE (TREE_TYPE (decl)));
510 if (pointed_to_alias_set == 0)
511 /* It's not legal to make a subset of alias set zero. */
515 DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
516 record_alias_subset (pointed_to_alias_set,
517 DECL_POINTER_ALIAS_SET (decl));
521 /* We use the alias set indicated in the declaration. */
522 return DECL_POINTER_ALIAS_SET (decl);
525 /* If we have an INDIRECT_REF via a void pointer, we don't
526 know anything about what that might alias. */
527 else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE)
531 /* Otherwise, pick up the outermost object that we could have a pointer
532 to, processing conversion and PLACEHOLDER_EXPR as above. */
534 while (TREE_CODE (t) == PLACEHOLDER_EXPR
535 || (handled_component_p (t) && ! can_address_p (t)))
537 if (TREE_CODE (t) == PLACEHOLDER_EXPR)
538 t = find_placeholder (t, &placeholder_ptr);
540 t = TREE_OPERAND (t, 0);
545 /* If we've already determined the alias set for a decl, just return
546 it. This is necessary for C++ anonymous unions, whose component
547 variables don't look like union members (boo!). */
548 if (TREE_CODE (t) == VAR_DECL
549 && DECL_RTL_SET_P (t) && GET_CODE (DECL_RTL (t)) == MEM)
550 return MEM_ALIAS_SET (DECL_RTL (t));
552 /* Now all we care about is the type. */
556 /* Variant qualifiers don't affect the alias set, so get the main
557 variant. If this is a type with a known alias set, return it. */
558 t = TYPE_MAIN_VARIANT (t);
559 if (TYPE_ALIAS_SET_KNOWN_P (t))
560 return TYPE_ALIAS_SET (t);
562 /* See if the language has special handling for this type. */
563 set = (*lang_hooks.get_alias_set) (t);
567 /* There are no objects of FUNCTION_TYPE, so there's no point in
568 using up an alias set for them. (There are, of course, pointers
569 and references to functions, but that's different.) */
570 else if (TREE_CODE (t) == FUNCTION_TYPE)
573 /* Unless the language specifies otherwise, let vector types alias
574 their components. This avoids some nasty type punning issues in
575 normal usage. And indeed lets vectors be treated more like an
577 else if (TREE_CODE (t) == VECTOR_TYPE)
578 set = get_alias_set (TREE_TYPE (t));
581 /* Otherwise make a new alias set for this type. */
582 set = new_alias_set ();
584 TYPE_ALIAS_SET (t) = set;
586 /* If this is an aggregate type, we must record any component aliasing
588 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
589 record_component_aliases (t);
594 /* Return a brand-new alias set. */
599 static HOST_WIDE_INT last_alias_set;
601 if (flag_strict_aliasing)
602 return ++last_alias_set;
607 /* Indicate that things in SUBSET can alias things in SUPERSET, but
608 not vice versa. For example, in C, a store to an `int' can alias a
609 structure containing an `int', but not vice versa. Here, the
610 structure would be the SUPERSET and `int' the SUBSET. This
611 function should be called only once per SUPERSET/SUBSET pair.
613 It is illegal for SUPERSET to be zero; everything is implicitly a
614 subset of alias set zero. */
617 record_alias_subset (HOST_WIDE_INT superset, HOST_WIDE_INT subset)
619 alias_set_entry superset_entry;
620 alias_set_entry subset_entry;
622 /* It is possible in complex type situations for both sets to be the same,
623 in which case we can ignore this operation. */
624 if (superset == subset)
630 superset_entry = get_alias_set_entry (superset);
631 if (superset_entry == 0)
633 /* Create an entry for the SUPERSET, so that we have a place to
634 attach the SUBSET. */
635 superset_entry = xmalloc (sizeof (struct alias_set_entry));
636 superset_entry->alias_set = superset;
637 superset_entry->children
638 = splay_tree_new (splay_tree_compare_ints, 0, 0);
639 superset_entry->has_zero_child = 0;
640 splay_tree_insert (alias_sets, (splay_tree_key) superset,
641 (splay_tree_value) superset_entry);
645 superset_entry->has_zero_child = 1;
648 subset_entry = get_alias_set_entry (subset);
649 /* If there is an entry for the subset, enter all of its children
650 (if they are not already present) as children of the SUPERSET. */
653 if (subset_entry->has_zero_child)
654 superset_entry->has_zero_child = 1;
656 splay_tree_foreach (subset_entry->children, insert_subset_children,
657 superset_entry->children);
660 /* Enter the SUBSET itself as a child of the SUPERSET. */
661 splay_tree_insert (superset_entry->children,
662 (splay_tree_key) subset, 0);
666 /* Record that component types of TYPE, if any, are part of that type for
667 aliasing purposes. For record types, we only record component types
668 for fields that are marked addressable. For array types, we always
669 record the component types, so the front end should not call this
670 function if the individual component aren't addressable. */
673 record_component_aliases (tree type)
675 HOST_WIDE_INT superset = get_alias_set (type);
681 switch (TREE_CODE (type))
684 if (! TYPE_NONALIASED_COMPONENT (type))
685 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
690 case QUAL_UNION_TYPE:
691 /* Recursively record aliases for the base classes, if there are any */
692 if (TYPE_BINFO (type) != NULL && TYPE_BINFO_BASETYPES (type) != NULL)
695 for (i = 0; i < TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type)); i++)
697 tree binfo = TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type), i);
698 record_alias_subset (superset,
699 get_alias_set (BINFO_TYPE (binfo)));
702 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
703 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
704 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
708 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
716 /* Allocate an alias set for use in storing and reading from the varargs
720 get_varargs_alias_set (void)
722 static HOST_WIDE_INT set = -1;
725 set = new_alias_set ();
730 /* Likewise, but used for the fixed portions of the frame, e.g., register
734 get_frame_alias_set (void)
736 static HOST_WIDE_INT set = -1;
739 set = new_alias_set ();
744 /* Inside SRC, the source of a SET, find a base address. */
747 find_base_value (rtx src)
751 switch (GET_CODE (src))
759 /* At the start of a function, argument registers have known base
760 values which may be lost later. Returning an ADDRESS
761 expression here allows optimization based on argument values
762 even when the argument registers are used for other purposes. */
763 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
764 return new_reg_base_value[regno];
766 /* If a pseudo has a known base value, return it. Do not do this
767 for non-fixed hard regs since it can result in a circular
768 dependency chain for registers which have values at function entry.
770 The test above is not sufficient because the scheduler may move
771 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
772 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
773 && regno < reg_base_value_size)
775 /* If we're inside init_alias_analysis, use new_reg_base_value
776 to reduce the number of relaxation iterations. */
777 if (new_reg_base_value && new_reg_base_value[regno]
778 && REG_N_SETS (regno) == 1)
779 return new_reg_base_value[regno];
781 if (reg_base_value[regno])
782 return reg_base_value[regno];
788 /* Check for an argument passed in memory. Only record in the
789 copying-arguments block; it is too hard to track changes
791 if (copying_arguments
792 && (XEXP (src, 0) == arg_pointer_rtx
793 || (GET_CODE (XEXP (src, 0)) == PLUS
794 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
795 return gen_rtx_ADDRESS (VOIDmode, src);
800 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
803 /* ... fall through ... */
808 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
810 /* If either operand is a REG that is a known pointer, then it
812 if (REG_P (src_0) && REG_POINTER (src_0))
813 return find_base_value (src_0);
814 if (REG_P (src_1) && REG_POINTER (src_1))
815 return find_base_value (src_1);
817 /* If either operand is a REG, then see if we already have
818 a known value for it. */
821 temp = find_base_value (src_0);
828 temp = find_base_value (src_1);
833 /* If either base is named object or a special address
834 (like an argument or stack reference), then use it for the
837 && (GET_CODE (src_0) == SYMBOL_REF
838 || GET_CODE (src_0) == LABEL_REF
839 || (GET_CODE (src_0) == ADDRESS
840 && GET_MODE (src_0) != VOIDmode)))
844 && (GET_CODE (src_1) == SYMBOL_REF
845 || GET_CODE (src_1) == LABEL_REF
846 || (GET_CODE (src_1) == ADDRESS
847 && GET_MODE (src_1) != VOIDmode)))
850 /* Guess which operand is the base address:
851 If either operand is a symbol, then it is the base. If
852 either operand is a CONST_INT, then the other is the base. */
853 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
854 return find_base_value (src_0);
855 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
856 return find_base_value (src_1);
862 /* The standard form is (lo_sum reg sym) so look only at the
864 return find_base_value (XEXP (src, 1));
867 /* If the second operand is constant set the base
868 address to the first operand. */
869 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
870 return find_base_value (XEXP (src, 0));
874 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
884 return find_base_value (XEXP (src, 0));
887 case SIGN_EXTEND: /* used for NT/Alpha pointers */
889 rtx temp = find_base_value (XEXP (src, 0));
891 if (temp != 0 && CONSTANT_P (temp))
892 temp = convert_memory_address (Pmode, temp);
904 /* Called from init_alias_analysis indirectly through note_stores. */
906 /* While scanning insns to find base values, reg_seen[N] is nonzero if
907 register N has been set in this function. */
908 static char *reg_seen;
910 /* Addresses which are known not to alias anything else are identified
911 by a unique integer. */
912 static int unique_id;
915 record_set (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED)
921 if (GET_CODE (dest) != REG)
924 regno = REGNO (dest);
926 if (regno >= reg_base_value_size)
929 /* If this spans multiple hard registers, then we must indicate that every
930 register has an unusable value. */
931 if (regno < FIRST_PSEUDO_REGISTER)
932 n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
939 reg_seen[regno + n] = 1;
940 new_reg_base_value[regno + n] = 0;
947 /* A CLOBBER wipes out any old value but does not prevent a previously
948 unset register from acquiring a base address (i.e. reg_seen is not
950 if (GET_CODE (set) == CLOBBER)
952 new_reg_base_value[regno] = 0;
961 new_reg_base_value[regno] = 0;
965 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
966 GEN_INT (unique_id++));
970 /* This is not the first set. If the new value is not related to the
971 old value, forget the base value. Note that the following code is
973 extern int x, y; int *p = &x; p += (&y-&x);
974 ANSI C does not allow computing the difference of addresses
975 of distinct top level objects. */
976 if (new_reg_base_value[regno])
977 switch (GET_CODE (src))
981 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
982 new_reg_base_value[regno] = 0;
985 /* If the value we add in the PLUS is also a valid base value,
986 this might be the actual base value, and the original value
989 rtx other = NULL_RTX;
991 if (XEXP (src, 0) == dest)
992 other = XEXP (src, 1);
993 else if (XEXP (src, 1) == dest)
994 other = XEXP (src, 0);
996 if (! other || find_base_value (other))
997 new_reg_base_value[regno] = 0;
1001 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
1002 new_reg_base_value[regno] = 0;
1005 new_reg_base_value[regno] = 0;
1008 /* If this is the first set of a register, record the value. */
1009 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1010 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1011 new_reg_base_value[regno] = find_base_value (src);
1013 reg_seen[regno] = 1;
1016 /* Called from loop optimization when a new pseudo-register is
1017 created. It indicates that REGNO is being set to VAL. f INVARIANT
1018 is true then this value also describes an invariant relationship
1019 which can be used to deduce that two registers with unknown values
1023 record_base_value (unsigned int regno, rtx val, int invariant)
1025 if (regno >= reg_base_value_size)
1028 if (invariant && alias_invariant)
1029 alias_invariant[regno] = val;
1031 if (GET_CODE (val) == REG)
1033 if (REGNO (val) < reg_base_value_size)
1034 reg_base_value[regno] = reg_base_value[REGNO (val)];
1039 reg_base_value[regno] = find_base_value (val);
1042 /* Clear alias info for a register. This is used if an RTL transformation
1043 changes the value of a register. This is used in flow by AUTO_INC_DEC
1044 optimizations. We don't need to clear reg_base_value, since flow only
1045 changes the offset. */
1048 clear_reg_alias_info (rtx reg)
1050 unsigned int regno = REGNO (reg);
1052 if (regno < reg_known_value_size && regno >= FIRST_PSEUDO_REGISTER)
1053 reg_known_value[regno] = reg;
1056 /* Returns a canonical version of X, from the point of view alias
1057 analysis. (For example, if X is a MEM whose address is a register,
1058 and the register has a known value (say a SYMBOL_REF), then a MEM
1059 whose address is the SYMBOL_REF is returned.) */
1064 /* Recursively look for equivalences. */
1065 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
1066 && REGNO (x) < reg_known_value_size)
1067 return reg_known_value[REGNO (x)] == x
1068 ? x : canon_rtx (reg_known_value[REGNO (x)]);
1069 else if (GET_CODE (x) == PLUS)
1071 rtx x0 = canon_rtx (XEXP (x, 0));
1072 rtx x1 = canon_rtx (XEXP (x, 1));
1074 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1076 if (GET_CODE (x0) == CONST_INT)
1077 return plus_constant (x1, INTVAL (x0));
1078 else if (GET_CODE (x1) == CONST_INT)
1079 return plus_constant (x0, INTVAL (x1));
1080 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1084 /* This gives us much better alias analysis when called from
1085 the loop optimizer. Note we want to leave the original
1086 MEM alone, but need to return the canonicalized MEM with
1087 all the flags with their original values. */
1088 else if (GET_CODE (x) == MEM)
1089 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1094 /* Return 1 if X and Y are identical-looking rtx's.
1095 Expect that X and Y has been already canonicalized.
1097 We use the data in reg_known_value above to see if two registers with
1098 different numbers are, in fact, equivalent. */
1101 rtx_equal_for_memref_p (rtx x, rtx y)
1108 if (x == 0 && y == 0)
1110 if (x == 0 || y == 0)
1116 code = GET_CODE (x);
1117 /* Rtx's of different codes cannot be equal. */
1118 if (code != GET_CODE (y))
1121 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1122 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1124 if (GET_MODE (x) != GET_MODE (y))
1127 /* Some RTL can be compared without a recursive examination. */
1131 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
1134 return REGNO (x) == REGNO (y);
1137 return XEXP (x, 0) == XEXP (y, 0);
1140 return XSTR (x, 0) == XSTR (y, 0);
1144 /* There's no need to compare the contents of CONST_DOUBLEs or
1145 CONST_INTs because pointer equality is a good enough
1146 comparison for these nodes. */
1150 return (XINT (x, 1) == XINT (y, 1)
1151 && rtx_equal_for_memref_p (XEXP (x, 0),
1158 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1160 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1161 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1162 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1163 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1164 /* For commutative operations, the RTX match if the operand match in any
1165 order. Also handle the simple binary and unary cases without a loop. */
1166 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
1168 rtx xop0 = canon_rtx (XEXP (x, 0));
1169 rtx yop0 = canon_rtx (XEXP (y, 0));
1170 rtx yop1 = canon_rtx (XEXP (y, 1));
1172 return ((rtx_equal_for_memref_p (xop0, yop0)
1173 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1174 || (rtx_equal_for_memref_p (xop0, yop1)
1175 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1177 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
1179 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1180 canon_rtx (XEXP (y, 0)))
1181 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1182 canon_rtx (XEXP (y, 1))));
1184 else if (GET_RTX_CLASS (code) == '1')
1185 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1186 canon_rtx (XEXP (y, 0)));
1188 /* Compare the elements. If any pair of corresponding elements
1189 fail to match, return 0 for the whole things.
1191 Limit cases to types which actually appear in addresses. */
1193 fmt = GET_RTX_FORMAT (code);
1194 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1199 if (XINT (x, i) != XINT (y, i))
1204 /* Two vectors must have the same length. */
1205 if (XVECLEN (x, i) != XVECLEN (y, i))
1208 /* And the corresponding elements must match. */
1209 for (j = 0; j < XVECLEN (x, i); j++)
1210 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1211 canon_rtx (XVECEXP (y, i, j))) == 0)
1216 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1217 canon_rtx (XEXP (y, i))) == 0)
1221 /* This can happen for asm operands. */
1223 if (strcmp (XSTR (x, i), XSTR (y, i)))
1227 /* This can happen for an asm which clobbers memory. */
1231 /* It is believed that rtx's at this level will never
1232 contain anything but integers and other rtx's,
1233 except for within LABEL_REFs and SYMBOL_REFs. */
1241 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1242 X and return it, or return 0 if none found. */
1245 find_symbolic_term (rtx x)
1251 code = GET_CODE (x);
1252 if (code == SYMBOL_REF || code == LABEL_REF)
1254 if (GET_RTX_CLASS (code) == 'o')
1257 fmt = GET_RTX_FORMAT (code);
1258 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1264 t = find_symbolic_term (XEXP (x, i));
1268 else if (fmt[i] == 'E')
1275 find_base_term (rtx x)
1278 struct elt_loc_list *l;
1280 #if defined (FIND_BASE_TERM)
1281 /* Try machine-dependent ways to find the base term. */
1282 x = FIND_BASE_TERM (x);
1285 switch (GET_CODE (x))
1288 return REG_BASE_VALUE (x);
1291 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1301 return find_base_term (XEXP (x, 0));
1304 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1306 rtx temp = find_base_term (XEXP (x, 0));
1308 if (temp != 0 && CONSTANT_P (temp))
1309 temp = convert_memory_address (Pmode, temp);
1315 val = CSELIB_VAL_PTR (x);
1316 for (l = val->locs; l; l = l->next)
1317 if ((x = find_base_term (l->loc)) != 0)
1323 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1330 rtx tmp1 = XEXP (x, 0);
1331 rtx tmp2 = XEXP (x, 1);
1333 /* This is a little bit tricky since we have to determine which of
1334 the two operands represents the real base address. Otherwise this
1335 routine may return the index register instead of the base register.
1337 That may cause us to believe no aliasing was possible, when in
1338 fact aliasing is possible.
1340 We use a few simple tests to guess the base register. Additional
1341 tests can certainly be added. For example, if one of the operands
1342 is a shift or multiply, then it must be the index register and the
1343 other operand is the base register. */
1345 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1346 return find_base_term (tmp2);
1348 /* If either operand is known to be a pointer, then use it
1349 to determine the base term. */
1350 if (REG_P (tmp1) && REG_POINTER (tmp1))
1351 return find_base_term (tmp1);
1353 if (REG_P (tmp2) && REG_POINTER (tmp2))
1354 return find_base_term (tmp2);
1356 /* Neither operand was known to be a pointer. Go ahead and find the
1357 base term for both operands. */
1358 tmp1 = find_base_term (tmp1);
1359 tmp2 = find_base_term (tmp2);
1361 /* If either base term is named object or a special address
1362 (like an argument or stack reference), then use it for the
1365 && (GET_CODE (tmp1) == SYMBOL_REF
1366 || GET_CODE (tmp1) == LABEL_REF
1367 || (GET_CODE (tmp1) == ADDRESS
1368 && GET_MODE (tmp1) != VOIDmode)))
1372 && (GET_CODE (tmp2) == SYMBOL_REF
1373 || GET_CODE (tmp2) == LABEL_REF
1374 || (GET_CODE (tmp2) == ADDRESS
1375 && GET_MODE (tmp2) != VOIDmode)))
1378 /* We could not determine which of the two operands was the
1379 base register and which was the index. So we can determine
1380 nothing from the base alias check. */
1385 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0)
1386 return find_base_term (XEXP (x, 0));
1394 return REG_BASE_VALUE (frame_pointer_rtx);
1401 /* Return 0 if the addresses X and Y are known to point to different
1402 objects, 1 if they might be pointers to the same object. */
1405 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1406 enum machine_mode y_mode)
1408 rtx x_base = find_base_term (x);
1409 rtx y_base = find_base_term (y);
1411 /* If the address itself has no known base see if a known equivalent
1412 value has one. If either address still has no known base, nothing
1413 is known about aliasing. */
1418 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1421 x_base = find_base_term (x_c);
1429 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1432 y_base = find_base_term (y_c);
1437 /* If the base addresses are equal nothing is known about aliasing. */
1438 if (rtx_equal_p (x_base, y_base))
1441 /* The base addresses of the read and write are different expressions.
1442 If they are both symbols and they are not accessed via AND, there is
1443 no conflict. We can bring knowledge of object alignment into play
1444 here. For example, on alpha, "char a, b;" can alias one another,
1445 though "char a; long b;" cannot. */
1446 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1448 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1450 if (GET_CODE (x) == AND
1451 && (GET_CODE (XEXP (x, 1)) != CONST_INT
1452 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1454 if (GET_CODE (y) == AND
1455 && (GET_CODE (XEXP (y, 1)) != CONST_INT
1456 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1458 /* Differing symbols never alias. */
1462 /* If one address is a stack reference there can be no alias:
1463 stack references using different base registers do not alias,
1464 a stack reference can not alias a parameter, and a stack reference
1465 can not alias a global. */
1466 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1467 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1470 if (! flag_argument_noalias)
1473 if (flag_argument_noalias > 1)
1476 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1477 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1480 /* Convert the address X into something we can use. This is done by returning
1481 it unchanged unless it is a value; in the latter case we call cselib to get
1482 a more useful rtx. */
1488 struct elt_loc_list *l;
1490 if (GET_CODE (x) != VALUE)
1492 v = CSELIB_VAL_PTR (x);
1493 for (l = v->locs; l; l = l->next)
1494 if (CONSTANT_P (l->loc))
1496 for (l = v->locs; l; l = l->next)
1497 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
1500 return v->locs->loc;
1504 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1505 where SIZE is the size in bytes of the memory reference. If ADDR
1506 is not modified by the memory reference then ADDR is returned. */
1509 addr_side_effect_eval (rtx addr, int size, int n_refs)
1513 switch (GET_CODE (addr))
1516 offset = (n_refs + 1) * size;
1519 offset = -(n_refs + 1) * size;
1522 offset = n_refs * size;
1525 offset = -n_refs * size;
1533 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1536 addr = XEXP (addr, 0);
1537 addr = canon_rtx (addr);
1542 /* Return nonzero if X and Y (memory addresses) could reference the
1543 same location in memory. C is an offset accumulator. When
1544 C is nonzero, we are testing aliases between X and Y + C.
1545 XSIZE is the size in bytes of the X reference,
1546 similarly YSIZE is the size in bytes for Y.
1547 Expect that canon_rtx has been already called for X and Y.
1549 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1550 referenced (the reference was BLKmode), so make the most pessimistic
1553 If XSIZE or YSIZE is negative, we may access memory outside the object
1554 being referenced as a side effect. This can happen when using AND to
1555 align memory references, as is done on the Alpha.
1557 Nice to notice that varying addresses cannot conflict with fp if no
1558 local variables had their addresses taken, but that's too hard now. */
1561 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1563 if (GET_CODE (x) == VALUE)
1565 if (GET_CODE (y) == VALUE)
1567 if (GET_CODE (x) == HIGH)
1569 else if (GET_CODE (x) == LO_SUM)
1572 x = addr_side_effect_eval (x, xsize, 0);
1573 if (GET_CODE (y) == HIGH)
1575 else if (GET_CODE (y) == LO_SUM)
1578 y = addr_side_effect_eval (y, ysize, 0);
1580 if (rtx_equal_for_memref_p (x, y))
1582 if (xsize <= 0 || ysize <= 0)
1584 if (c >= 0 && xsize > c)
1586 if (c < 0 && ysize+c > 0)
1591 /* This code used to check for conflicts involving stack references and
1592 globals but the base address alias code now handles these cases. */
1594 if (GET_CODE (x) == PLUS)
1596 /* The fact that X is canonicalized means that this
1597 PLUS rtx is canonicalized. */
1598 rtx x0 = XEXP (x, 0);
1599 rtx x1 = XEXP (x, 1);
1601 if (GET_CODE (y) == PLUS)
1603 /* The fact that Y is canonicalized means that this
1604 PLUS rtx is canonicalized. */
1605 rtx y0 = XEXP (y, 0);
1606 rtx y1 = XEXP (y, 1);
1608 if (rtx_equal_for_memref_p (x1, y1))
1609 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1610 if (rtx_equal_for_memref_p (x0, y0))
1611 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1612 if (GET_CODE (x1) == CONST_INT)
1614 if (GET_CODE (y1) == CONST_INT)
1615 return memrefs_conflict_p (xsize, x0, ysize, y0,
1616 c - INTVAL (x1) + INTVAL (y1));
1618 return memrefs_conflict_p (xsize, x0, ysize, y,
1621 else if (GET_CODE (y1) == CONST_INT)
1622 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1626 else if (GET_CODE (x1) == CONST_INT)
1627 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1629 else if (GET_CODE (y) == PLUS)
1631 /* The fact that Y is canonicalized means that this
1632 PLUS rtx is canonicalized. */
1633 rtx y0 = XEXP (y, 0);
1634 rtx y1 = XEXP (y, 1);
1636 if (GET_CODE (y1) == CONST_INT)
1637 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1642 if (GET_CODE (x) == GET_CODE (y))
1643 switch (GET_CODE (x))
1647 /* Handle cases where we expect the second operands to be the
1648 same, and check only whether the first operand would conflict
1651 rtx x1 = canon_rtx (XEXP (x, 1));
1652 rtx y1 = canon_rtx (XEXP (y, 1));
1653 if (! rtx_equal_for_memref_p (x1, y1))
1655 x0 = canon_rtx (XEXP (x, 0));
1656 y0 = canon_rtx (XEXP (y, 0));
1657 if (rtx_equal_for_memref_p (x0, y0))
1658 return (xsize == 0 || ysize == 0
1659 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1661 /* Can't properly adjust our sizes. */
1662 if (GET_CODE (x1) != CONST_INT)
1664 xsize /= INTVAL (x1);
1665 ysize /= INTVAL (x1);
1667 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1671 /* Are these registers known not to be equal? */
1672 if (alias_invariant)
1674 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1675 rtx i_x, i_y; /* invariant relationships of X and Y */
1677 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1678 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1680 if (i_x == 0 && i_y == 0)
1683 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1684 ysize, i_y ? i_y : y, c))
1693 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1694 as an access with indeterminate size. Assume that references
1695 besides AND are aligned, so if the size of the other reference is
1696 at least as large as the alignment, assume no other overlap. */
1697 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1699 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1701 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1703 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1705 /* ??? If we are indexing far enough into the array/structure, we
1706 may yet be able to determine that we can not overlap. But we
1707 also need to that we are far enough from the end not to overlap
1708 a following reference, so we do nothing with that for now. */
1709 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1711 return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1714 if (GET_CODE (x) == ADDRESSOF)
1716 if (y == frame_pointer_rtx
1717 || GET_CODE (y) == ADDRESSOF)
1718 return xsize <= 0 || ysize <= 0;
1720 if (GET_CODE (y) == ADDRESSOF)
1722 if (x == frame_pointer_rtx)
1723 return xsize <= 0 || ysize <= 0;
1728 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1730 c += (INTVAL (y) - INTVAL (x));
1731 return (xsize <= 0 || ysize <= 0
1732 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1735 if (GET_CODE (x) == CONST)
1737 if (GET_CODE (y) == CONST)
1738 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1739 ysize, canon_rtx (XEXP (y, 0)), c);
1741 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1744 if (GET_CODE (y) == CONST)
1745 return memrefs_conflict_p (xsize, x, ysize,
1746 canon_rtx (XEXP (y, 0)), c);
1749 return (xsize <= 0 || ysize <= 0
1750 || (rtx_equal_for_memref_p (x, y)
1751 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1758 /* Functions to compute memory dependencies.
1760 Since we process the insns in execution order, we can build tables
1761 to keep track of what registers are fixed (and not aliased), what registers
1762 are varying in known ways, and what registers are varying in unknown
1765 If both memory references are volatile, then there must always be a
1766 dependence between the two references, since their order can not be
1767 changed. A volatile and non-volatile reference can be interchanged
1770 A MEM_IN_STRUCT reference at a non-AND varying address can never
1771 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1772 also must allow AND addresses, because they may generate accesses
1773 outside the object being referenced. This is used to generate
1774 aligned addresses from unaligned addresses, for instance, the alpha
1775 storeqi_unaligned pattern. */
1777 /* Read dependence: X is read after read in MEM takes place. There can
1778 only be a dependence here if both reads are volatile. */
1781 read_dependence (rtx mem, rtx x)
1783 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1786 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1787 MEM2 is a reference to a structure at a varying address, or returns
1788 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1789 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1790 to decide whether or not an address may vary; it should return
1791 nonzero whenever variation is possible.
1792 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1795 fixed_scalar_and_varying_struct_p (rtx mem1, rtx mem2, rtx mem1_addr,
1797 int (*varies_p) (rtx, int))
1799 if (! flag_strict_aliasing)
1802 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1803 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1804 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1808 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1809 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1810 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1817 /* Returns nonzero if something about the mode or address format MEM1
1818 indicates that it might well alias *anything*. */
1821 aliases_everything_p (rtx mem)
1823 if (GET_CODE (XEXP (mem, 0)) == AND)
1824 /* If the address is an AND, its very hard to know at what it is
1825 actually pointing. */
1831 /* Return true if we can determine that the fields referenced cannot
1832 overlap for any pair of objects. */
1835 nonoverlapping_component_refs_p (tree x, tree y)
1837 tree fieldx, fieldy, typex, typey, orig_y;
1841 /* The comparison has to be done at a common type, since we don't
1842 know how the inheritance hierarchy works. */
1846 fieldx = TREE_OPERAND (x, 1);
1847 typex = DECL_FIELD_CONTEXT (fieldx);
1852 fieldy = TREE_OPERAND (y, 1);
1853 typey = DECL_FIELD_CONTEXT (fieldy);
1858 y = TREE_OPERAND (y, 0);
1860 while (y && TREE_CODE (y) == COMPONENT_REF);
1862 x = TREE_OPERAND (x, 0);
1864 while (x && TREE_CODE (x) == COMPONENT_REF);
1866 /* Never found a common type. */
1870 /* If we're left with accessing different fields of a structure,
1872 if (TREE_CODE (typex) == RECORD_TYPE
1873 && fieldx != fieldy)
1876 /* The comparison on the current field failed. If we're accessing
1877 a very nested structure, look at the next outer level. */
1878 x = TREE_OPERAND (x, 0);
1879 y = TREE_OPERAND (y, 0);
1882 && TREE_CODE (x) == COMPONENT_REF
1883 && TREE_CODE (y) == COMPONENT_REF);
1888 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1891 decl_for_component_ref (tree x)
1895 x = TREE_OPERAND (x, 0);
1897 while (x && TREE_CODE (x) == COMPONENT_REF);
1899 return x && DECL_P (x) ? x : NULL_TREE;
1902 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1903 offset of the field reference. */
1906 adjust_offset_for_component_ref (tree x, rtx offset)
1908 HOST_WIDE_INT ioffset;
1913 ioffset = INTVAL (offset);
1916 tree field = TREE_OPERAND (x, 1);
1918 if (! host_integerp (DECL_FIELD_OFFSET (field), 1))
1920 ioffset += (tree_low_cst (DECL_FIELD_OFFSET (field), 1)
1921 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
1924 x = TREE_OPERAND (x, 0);
1926 while (x && TREE_CODE (x) == COMPONENT_REF);
1928 return GEN_INT (ioffset);
1931 /* Return nonzero if we can determine the exprs corresponding to memrefs
1932 X and Y and they do not overlap. */
1935 nonoverlapping_memrefs_p (rtx x, rtx y)
1937 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
1940 rtx moffsetx, moffsety;
1941 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
1943 /* Unless both have exprs, we can't tell anything. */
1944 if (exprx == 0 || expry == 0)
1947 /* If both are field references, we may be able to determine something. */
1948 if (TREE_CODE (exprx) == COMPONENT_REF
1949 && TREE_CODE (expry) == COMPONENT_REF
1950 && nonoverlapping_component_refs_p (exprx, expry))
1953 /* If the field reference test failed, look at the DECLs involved. */
1954 moffsetx = MEM_OFFSET (x);
1955 if (TREE_CODE (exprx) == COMPONENT_REF)
1957 tree t = decl_for_component_ref (exprx);
1960 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
1963 else if (TREE_CODE (exprx) == INDIRECT_REF)
1965 exprx = TREE_OPERAND (exprx, 0);
1966 if (flag_argument_noalias < 2
1967 || TREE_CODE (exprx) != PARM_DECL)
1971 moffsety = MEM_OFFSET (y);
1972 if (TREE_CODE (expry) == COMPONENT_REF)
1974 tree t = decl_for_component_ref (expry);
1977 moffsety = adjust_offset_for_component_ref (expry, moffsety);
1980 else if (TREE_CODE (expry) == INDIRECT_REF)
1982 expry = TREE_OPERAND (expry, 0);
1983 if (flag_argument_noalias < 2
1984 || TREE_CODE (expry) != PARM_DECL)
1988 if (! DECL_P (exprx) || ! DECL_P (expry))
1991 rtlx = DECL_RTL (exprx);
1992 rtly = DECL_RTL (expry);
1994 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
1995 can't overlap unless they are the same because we never reuse that part
1996 of the stack frame used for locals for spilled pseudos. */
1997 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM)
1998 && ! rtx_equal_p (rtlx, rtly))
2001 /* Get the base and offsets of both decls. If either is a register, we
2002 know both are and are the same, so use that as the base. The only
2003 we can avoid overlap is if we can deduce that they are nonoverlapping
2004 pieces of that decl, which is very rare. */
2005 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx;
2006 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT)
2007 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2009 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly;
2010 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT)
2011 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2013 /* If the bases are different, we know they do not overlap if both
2014 are constants or if one is a constant and the other a pointer into the
2015 stack frame. Otherwise a different base means we can't tell if they
2017 if (! rtx_equal_p (basex, basey))
2018 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2019 || (CONSTANT_P (basex) && REG_P (basey)
2020 && REGNO_PTR_FRAME_P (REGNO (basey)))
2021 || (CONSTANT_P (basey) && REG_P (basex)
2022 && REGNO_PTR_FRAME_P (REGNO (basex))));
2024 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2025 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2027 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2028 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2031 /* If we have an offset for either memref, it can update the values computed
2034 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2036 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2038 /* If a memref has both a size and an offset, we can use the smaller size.
2039 We can't do this if the offset isn't known because we must view this
2040 memref as being anywhere inside the DECL's MEM. */
2041 if (MEM_SIZE (x) && moffsetx)
2042 sizex = INTVAL (MEM_SIZE (x));
2043 if (MEM_SIZE (y) && moffsety)
2044 sizey = INTVAL (MEM_SIZE (y));
2046 /* Put the values of the memref with the lower offset in X's values. */
2047 if (offsetx > offsety)
2049 tem = offsetx, offsetx = offsety, offsety = tem;
2050 tem = sizex, sizex = sizey, sizey = tem;
2053 /* If we don't know the size of the lower-offset value, we can't tell
2054 if they conflict. Otherwise, we do the test. */
2055 return sizex >= 0 && offsety >= offsetx + sizex;
2058 /* True dependence: X is read after store in MEM takes place. */
2061 true_dependence (rtx mem, enum machine_mode mem_mode, rtx x,
2062 int (*varies) (rtx, int))
2064 rtx x_addr, mem_addr;
2067 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2070 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2071 This is used in epilogue deallocation functions. */
2072 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2074 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2077 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2080 /* Unchanging memory can't conflict with non-unchanging memory.
2081 A non-unchanging read can conflict with a non-unchanging write.
2082 An unchanging read can conflict with an unchanging write since
2083 there may be a single store to this address to initialize it.
2084 Note that an unchanging store can conflict with a non-unchanging read
2085 since we have to make conservative assumptions when we have a
2086 record with readonly fields and we are copying the whole thing.
2087 Just fall through to the code below to resolve potential conflicts.
2088 This won't handle all cases optimally, but the possible performance
2089 loss should be negligible. */
2090 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2093 if (nonoverlapping_memrefs_p (mem, x))
2096 if (mem_mode == VOIDmode)
2097 mem_mode = GET_MODE (mem);
2099 x_addr = get_addr (XEXP (x, 0));
2100 mem_addr = get_addr (XEXP (mem, 0));
2102 base = find_base_term (x_addr);
2103 if (base && (GET_CODE (base) == LABEL_REF
2104 || (GET_CODE (base) == SYMBOL_REF
2105 && CONSTANT_POOL_ADDRESS_P (base))))
2108 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2111 x_addr = canon_rtx (x_addr);
2112 mem_addr = canon_rtx (mem_addr);
2114 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2115 SIZE_FOR_MODE (x), x_addr, 0))
2118 if (aliases_everything_p (x))
2121 /* We cannot use aliases_everything_p to test MEM, since we must look
2122 at MEM_MODE, rather than GET_MODE (MEM). */
2123 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2126 /* In true_dependence we also allow BLKmode to alias anything. Why
2127 don't we do this in anti_dependence and output_dependence? */
2128 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2131 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2135 /* Canonical true dependence: X is read after store in MEM takes place.
2136 Variant of true_dependence which assumes MEM has already been
2137 canonicalized (hence we no longer do that here).
2138 The mem_addr argument has been added, since true_dependence computed
2139 this value prior to canonicalizing. */
2142 canon_true_dependence (rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2143 rtx x, int (*varies) (rtx, int))
2147 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2150 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2151 This is used in epilogue deallocation functions. */
2152 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2154 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2157 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2160 /* If X is an unchanging read, then it can't possibly conflict with any
2161 non-unchanging store. It may conflict with an unchanging write though,
2162 because there may be a single store to this address to initialize it.
2163 Just fall through to the code below to resolve the case where we have
2164 both an unchanging read and an unchanging write. This won't handle all
2165 cases optimally, but the possible performance loss should be
2167 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2170 if (nonoverlapping_memrefs_p (x, mem))
2173 x_addr = get_addr (XEXP (x, 0));
2175 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2178 x_addr = canon_rtx (x_addr);
2179 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2180 SIZE_FOR_MODE (x), x_addr, 0))
2183 if (aliases_everything_p (x))
2186 /* We cannot use aliases_everything_p to test MEM, since we must look
2187 at MEM_MODE, rather than GET_MODE (MEM). */
2188 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2191 /* In true_dependence we also allow BLKmode to alias anything. Why
2192 don't we do this in anti_dependence and output_dependence? */
2193 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2196 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2200 /* Returns nonzero if a write to X might alias a previous read from
2201 (or, if WRITEP is nonzero, a write to) MEM. If CONSTP is nonzero,
2202 honor the RTX_UNCHANGING_P flags on X and MEM. */
2205 write_dependence_p (rtx mem, rtx x, int writep, int constp)
2207 rtx x_addr, mem_addr;
2211 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2214 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2215 This is used in epilogue deallocation functions. */
2216 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2218 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2221 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2226 /* Unchanging memory can't conflict with non-unchanging memory. */
2227 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem))
2230 /* If MEM is an unchanging read, then it can't possibly conflict with
2231 the store to X, because there is at most one store to MEM, and it
2232 must have occurred somewhere before MEM. */
2233 if (! writep && RTX_UNCHANGING_P (mem))
2237 if (nonoverlapping_memrefs_p (x, mem))
2240 x_addr = get_addr (XEXP (x, 0));
2241 mem_addr = get_addr (XEXP (mem, 0));
2245 base = find_base_term (mem_addr);
2246 if (base && (GET_CODE (base) == LABEL_REF
2247 || (GET_CODE (base) == SYMBOL_REF
2248 && CONSTANT_POOL_ADDRESS_P (base))))
2252 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2256 x_addr = canon_rtx (x_addr);
2257 mem_addr = canon_rtx (mem_addr);
2259 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2260 SIZE_FOR_MODE (x), x_addr, 0))
2264 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2267 return (!(fixed_scalar == mem && !aliases_everything_p (x))
2268 && !(fixed_scalar == x && !aliases_everything_p (mem)));
2271 /* Anti dependence: X is written after read in MEM takes place. */
2274 anti_dependence (rtx mem, rtx x)
2276 return write_dependence_p (mem, x, /*writep=*/0, /*constp*/1);
2279 /* Output dependence: X is written after store in MEM takes place. */
2282 output_dependence (rtx mem, rtx x)
2284 return write_dependence_p (mem, x, /*writep=*/1, /*constp*/1);
2287 /* Unchanging anti dependence: Like anti_dependence but ignores
2288 the UNCHANGING_RTX_P property on const variable references. */
2291 unchanging_anti_dependence (rtx mem, rtx x)
2293 return write_dependence_p (mem, x, /*writep=*/0, /*constp*/0);
2296 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2297 something which is not local to the function and is not constant. */
2300 nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2309 switch (GET_CODE (x))
2312 if (GET_CODE (SUBREG_REG (x)) == REG)
2314 /* Global registers are not local. */
2315 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
2316 && global_regs[subreg_regno (x)])
2324 /* Global registers are not local. */
2325 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2340 /* Constants in the function's constants pool are constant. */
2341 if (CONSTANT_POOL_ADDRESS_P (x))
2346 /* Non-constant calls and recursion are not local. */
2350 /* Be overly conservative and consider any volatile memory
2351 reference as not local. */
2352 if (MEM_VOLATILE_P (x))
2354 base = find_base_term (XEXP (x, 0));
2357 /* A Pmode ADDRESS could be a reference via the structure value
2358 address or static chain. Such memory references are nonlocal.
2360 Thus, we have to examine the contents of the ADDRESS to find
2361 out if this is a local reference or not. */
2362 if (GET_CODE (base) == ADDRESS
2363 && GET_MODE (base) == Pmode
2364 && (XEXP (base, 0) == stack_pointer_rtx
2365 || XEXP (base, 0) == arg_pointer_rtx
2366 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2367 || XEXP (base, 0) == hard_frame_pointer_rtx
2369 || XEXP (base, 0) == frame_pointer_rtx))
2371 /* Constants in the function's constant pool are constant. */
2372 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
2377 case UNSPEC_VOLATILE:
2382 if (MEM_VOLATILE_P (x))
2394 /* Returns nonzero if X might mention something which is not
2395 local to the function and is not constant. */
2398 nonlocal_mentioned_p (rtx x)
2402 if (GET_CODE (x) == CALL_INSN)
2404 if (! CONST_OR_PURE_CALL_P (x))
2406 x = CALL_INSN_FUNCTION_USAGE (x);
2414 return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL);
2417 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2418 something which is not local to the function and is not constant. */
2421 nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2428 switch (GET_CODE (x))
2434 return nonlocal_mentioned_p (x);
2437 /* Non-constant calls and recursion are not local. */
2441 if (nonlocal_mentioned_p (SET_SRC (x)))
2444 if (GET_CODE (SET_DEST (x)) == MEM)
2445 return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0));
2447 /* If the destination is anything other than a CC0, PC,
2448 MEM, REG, or a SUBREG of a REG that occupies all of
2449 the REG, then X references nonlocal memory if it is
2450 mentioned in the destination. */
2451 if (GET_CODE (SET_DEST (x)) != CC0
2452 && GET_CODE (SET_DEST (x)) != PC
2453 && GET_CODE (SET_DEST (x)) != REG
2454 && ! (GET_CODE (SET_DEST (x)) == SUBREG
2455 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
2456 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
2457 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
2458 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
2459 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
2460 return nonlocal_mentioned_p (SET_DEST (x));
2464 if (GET_CODE (XEXP (x, 0)) == MEM)
2465 return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0));
2469 return nonlocal_mentioned_p (XEXP (x, 0));
2472 case UNSPEC_VOLATILE:
2476 if (MEM_VOLATILE_P (x))
2488 /* Returns nonzero if X might reference something which is not
2489 local to the function and is not constant. */
2492 nonlocal_referenced_p (rtx x)
2496 if (GET_CODE (x) == CALL_INSN)
2498 if (! CONST_OR_PURE_CALL_P (x))
2500 x = CALL_INSN_FUNCTION_USAGE (x);
2508 return for_each_rtx (&x, nonlocal_referenced_p_1, NULL);
2511 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2512 something which is not local to the function and is not constant. */
2515 nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2522 switch (GET_CODE (x))
2525 /* Non-constant calls and recursion are not local. */
2534 return nonlocal_mentioned_p (XEXP (x, 0));
2537 if (nonlocal_mentioned_p (SET_DEST (x)))
2539 return nonlocal_set_p (SET_SRC (x));
2542 return nonlocal_mentioned_p (XEXP (x, 0));
2548 case UNSPEC_VOLATILE:
2552 if (MEM_VOLATILE_P (x))
2564 /* Returns nonzero if X might set something which is not
2565 local to the function and is not constant. */
2568 nonlocal_set_p (rtx x)
2572 if (GET_CODE (x) == CALL_INSN)
2574 if (! CONST_OR_PURE_CALL_P (x))
2576 x = CALL_INSN_FUNCTION_USAGE (x);
2584 return for_each_rtx (&x, nonlocal_set_p_1, NULL);
2587 /* Mark the function if it is pure or constant. */
2590 mark_constant_function (void)
2593 int nonlocal_memory_referenced;
2595 if (TREE_READONLY (current_function_decl)
2596 || DECL_IS_PURE (current_function_decl)
2597 || TREE_THIS_VOLATILE (current_function_decl)
2598 || current_function_has_nonlocal_goto
2599 || !(*targetm.binds_local_p) (current_function_decl))
2602 /* A loop might not return which counts as a side effect. */
2603 if (mark_dfs_back_edges ())
2606 nonlocal_memory_referenced = 0;
2608 init_alias_analysis ();
2610 /* Determine if this is a constant or pure function. */
2612 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2614 if (! INSN_P (insn))
2617 if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn)
2618 || volatile_refs_p (PATTERN (insn)))
2621 if (! nonlocal_memory_referenced)
2622 nonlocal_memory_referenced = nonlocal_referenced_p (insn);
2625 end_alias_analysis ();
2627 /* Mark the function. */
2631 else if (nonlocal_memory_referenced)
2633 cgraph_rtl_info (current_function_decl)->pure_function = 1;
2634 DECL_IS_PURE (current_function_decl) = 1;
2638 cgraph_rtl_info (current_function_decl)->const_function = 1;
2639 TREE_READONLY (current_function_decl) = 1;
2645 init_alias_once (void)
2649 #ifndef OUTGOING_REGNO
2650 #define OUTGOING_REGNO(N) N
2652 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2653 /* Check whether this register can hold an incoming pointer
2654 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2655 numbers, so translate if necessary due to register windows. */
2656 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2657 && HARD_REGNO_MODE_OK (i, Pmode))
2658 static_reg_base_value[i]
2659 = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2661 static_reg_base_value[STACK_POINTER_REGNUM]
2662 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2663 static_reg_base_value[ARG_POINTER_REGNUM]
2664 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2665 static_reg_base_value[FRAME_POINTER_REGNUM]
2666 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2667 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2668 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2669 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2672 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
2675 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2676 to be memory reference. */
2677 static bool memory_modified;
2679 memory_modified_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
2681 if (GET_CODE (x) == MEM)
2683 if (anti_dependence (x, (rtx)data) || output_dependence (x, (rtx)data))
2684 memory_modified = true;
2689 /* Return true when INSN possibly modify memory contents of MEM
2690 (ie address can be modified). */
2692 memory_modified_in_insn_p (rtx mem, rtx insn)
2696 memory_modified = false;
2697 note_stores (PATTERN (insn), memory_modified_1, mem);
2698 return memory_modified;
2701 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2705 init_alias_analysis (void)
2707 int maxreg = max_reg_num ();
2713 timevar_push (TV_ALIAS_ANALYSIS);
2715 reg_known_value_size = maxreg;
2718 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx))
2719 - FIRST_PSEUDO_REGISTER;
2721 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char))
2722 - FIRST_PSEUDO_REGISTER;
2724 /* Overallocate reg_base_value to allow some growth during loop
2725 optimization. Loop unrolling can create a large number of
2727 reg_base_value_size = maxreg * 2;
2728 reg_base_value = ggc_alloc_cleared (reg_base_value_size * sizeof (rtx));
2730 new_reg_base_value = xmalloc (reg_base_value_size * sizeof (rtx));
2731 reg_seen = xmalloc (reg_base_value_size);
2732 if (! reload_completed && flag_old_unroll_loops)
2734 /* ??? Why are we realloc'ing if we're just going to zero it? */
2735 alias_invariant = xrealloc (alias_invariant,
2736 reg_base_value_size * sizeof (rtx));
2737 memset (alias_invariant, 0, reg_base_value_size * sizeof (rtx));
2740 /* The basic idea is that each pass through this loop will use the
2741 "constant" information from the previous pass to propagate alias
2742 information through another level of assignments.
2744 This could get expensive if the assignment chains are long. Maybe
2745 we should throttle the number of iterations, possibly based on
2746 the optimization level or flag_expensive_optimizations.
2748 We could propagate more information in the first pass by making use
2749 of REG_N_SETS to determine immediately that the alias information
2750 for a pseudo is "constant".
2752 A program with an uninitialized variable can cause an infinite loop
2753 here. Instead of doing a full dataflow analysis to detect such problems
2754 we just cap the number of iterations for the loop.
2756 The state of the arrays for the set chain in question does not matter
2757 since the program has undefined behavior. */
2762 /* Assume nothing will change this iteration of the loop. */
2765 /* We want to assign the same IDs each iteration of this loop, so
2766 start counting from zero each iteration of the loop. */
2769 /* We're at the start of the function each iteration through the
2770 loop, so we're copying arguments. */
2771 copying_arguments = true;
2773 /* Wipe the potential alias information clean for this pass. */
2774 memset (new_reg_base_value, 0, reg_base_value_size * sizeof (rtx));
2776 /* Wipe the reg_seen array clean. */
2777 memset (reg_seen, 0, reg_base_value_size);
2779 /* Mark all hard registers which may contain an address.
2780 The stack, frame and argument pointers may contain an address.
2781 An argument register which can hold a Pmode value may contain
2782 an address even if it is not in BASE_REGS.
2784 The address expression is VOIDmode for an argument and
2785 Pmode for other registers. */
2787 memcpy (new_reg_base_value, static_reg_base_value,
2788 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2790 /* Walk the insns adding values to the new_reg_base_value array. */
2791 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2797 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2798 /* The prologue/epilogue insns are not threaded onto the
2799 insn chain until after reload has completed. Thus,
2800 there is no sense wasting time checking if INSN is in
2801 the prologue/epilogue until after reload has completed. */
2802 if (reload_completed
2803 && prologue_epilogue_contains (insn))
2807 /* If this insn has a noalias note, process it, Otherwise,
2808 scan for sets. A simple set will have no side effects
2809 which could change the base value of any other register. */
2811 if (GET_CODE (PATTERN (insn)) == SET
2812 && REG_NOTES (insn) != 0
2813 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2814 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2816 note_stores (PATTERN (insn), record_set, NULL);
2818 set = single_set (insn);
2821 && GET_CODE (SET_DEST (set)) == REG
2822 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2824 unsigned int regno = REGNO (SET_DEST (set));
2825 rtx src = SET_SRC (set);
2827 if (REG_NOTES (insn) != 0
2828 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2829 && REG_N_SETS (regno) == 1)
2830 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
2831 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2832 && ! rtx_varies_p (XEXP (note, 0), 1)
2833 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
2835 reg_known_value[regno] = XEXP (note, 0);
2836 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
2838 else if (REG_N_SETS (regno) == 1
2839 && GET_CODE (src) == PLUS
2840 && GET_CODE (XEXP (src, 0)) == REG
2841 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
2842 && (reg_known_value[REGNO (XEXP (src, 0))])
2843 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2845 rtx op0 = XEXP (src, 0);
2846 op0 = reg_known_value[REGNO (op0)];
2847 reg_known_value[regno]
2848 = plus_constant (op0, INTVAL (XEXP (src, 1)));
2849 reg_known_equiv_p[regno] = 0;
2851 else if (REG_N_SETS (regno) == 1
2852 && ! rtx_varies_p (src, 1))
2854 reg_known_value[regno] = src;
2855 reg_known_equiv_p[regno] = 0;
2859 else if (GET_CODE (insn) == NOTE
2860 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
2861 copying_arguments = false;
2864 /* Now propagate values from new_reg_base_value to reg_base_value. */
2865 for (ui = 0; ui < reg_base_value_size; ui++)
2867 if (new_reg_base_value[ui]
2868 && new_reg_base_value[ui] != reg_base_value[ui]
2869 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
2871 reg_base_value[ui] = new_reg_base_value[ui];
2876 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2878 /* Fill in the remaining entries. */
2879 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
2880 if (reg_known_value[i] == 0)
2881 reg_known_value[i] = regno_reg_rtx[i];
2883 /* Simplify the reg_base_value array so that no register refers to
2884 another register, except to special registers indirectly through
2885 ADDRESS expressions.
2887 In theory this loop can take as long as O(registers^2), but unless
2888 there are very long dependency chains it will run in close to linear
2891 This loop may not be needed any longer now that the main loop does
2892 a better job at propagating alias information. */
2898 for (ui = 0; ui < reg_base_value_size; ui++)
2900 rtx base = reg_base_value[ui];
2901 if (base && GET_CODE (base) == REG)
2903 unsigned int base_regno = REGNO (base);
2904 if (base_regno == ui) /* register set from itself */
2905 reg_base_value[ui] = 0;
2907 reg_base_value[ui] = reg_base_value[base_regno];
2912 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
2915 free (new_reg_base_value);
2916 new_reg_base_value = 0;
2919 timevar_pop (TV_ALIAS_ANALYSIS);
2923 end_alias_analysis (void)
2925 free (reg_known_value + FIRST_PSEUDO_REGISTER);
2926 reg_known_value = 0;
2927 reg_known_value_size = 0;
2928 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER);
2929 reg_known_equiv_p = 0;
2931 reg_base_value_size = 0;
2932 if (alias_invariant)
2934 free (alias_invariant);
2935 alias_invariant = 0;
2939 #include "gt-alias.h"