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);
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. */
636 = (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
637 superset_entry->alias_set = superset;
638 superset_entry->children
639 = splay_tree_new (splay_tree_compare_ints, 0, 0);
640 superset_entry->has_zero_child = 0;
641 splay_tree_insert (alias_sets, (splay_tree_key) superset,
642 (splay_tree_value) superset_entry);
646 superset_entry->has_zero_child = 1;
649 subset_entry = get_alias_set_entry (subset);
650 /* If there is an entry for the subset, enter all of its children
651 (if they are not already present) as children of the SUPERSET. */
654 if (subset_entry->has_zero_child)
655 superset_entry->has_zero_child = 1;
657 splay_tree_foreach (subset_entry->children, insert_subset_children,
658 superset_entry->children);
661 /* Enter the SUBSET itself as a child of the SUPERSET. */
662 splay_tree_insert (superset_entry->children,
663 (splay_tree_key) subset, 0);
667 /* Record that component types of TYPE, if any, are part of that type for
668 aliasing purposes. For record types, we only record component types
669 for fields that are marked addressable. For array types, we always
670 record the component types, so the front end should not call this
671 function if the individual component aren't addressable. */
674 record_component_aliases (tree type)
676 HOST_WIDE_INT superset = get_alias_set (type);
682 switch (TREE_CODE (type))
685 if (! TYPE_NONALIASED_COMPONENT (type))
686 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
691 case QUAL_UNION_TYPE:
692 /* Recursively record aliases for the base classes, if there are any */
693 if (TYPE_BINFO (type) != NULL && TYPE_BINFO_BASETYPES (type) != NULL)
696 for (i = 0; i < TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type)); i++)
698 tree binfo = TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type), i);
699 record_alias_subset (superset,
700 get_alias_set (BINFO_TYPE (binfo)));
703 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
704 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
705 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
709 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
717 /* Allocate an alias set for use in storing and reading from the varargs
721 get_varargs_alias_set (void)
723 static HOST_WIDE_INT set = -1;
726 set = new_alias_set ();
731 /* Likewise, but used for the fixed portions of the frame, e.g., register
735 get_frame_alias_set (void)
737 static HOST_WIDE_INT set = -1;
740 set = new_alias_set ();
745 /* Inside SRC, the source of a SET, find a base address. */
748 find_base_value (rtx src)
752 switch (GET_CODE (src))
760 /* At the start of a function, argument registers have known base
761 values which may be lost later. Returning an ADDRESS
762 expression here allows optimization based on argument values
763 even when the argument registers are used for other purposes. */
764 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
765 return new_reg_base_value[regno];
767 /* If a pseudo has a known base value, return it. Do not do this
768 for non-fixed hard regs since it can result in a circular
769 dependency chain for registers which have values at function entry.
771 The test above is not sufficient because the scheduler may move
772 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
773 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
774 && regno < reg_base_value_size)
776 /* If we're inside init_alias_analysis, use new_reg_base_value
777 to reduce the number of relaxation iterations. */
778 if (new_reg_base_value && new_reg_base_value[regno]
779 && REG_N_SETS (regno) == 1)
780 return new_reg_base_value[regno];
782 if (reg_base_value[regno])
783 return reg_base_value[regno];
789 /* Check for an argument passed in memory. Only record in the
790 copying-arguments block; it is too hard to track changes
792 if (copying_arguments
793 && (XEXP (src, 0) == arg_pointer_rtx
794 || (GET_CODE (XEXP (src, 0)) == PLUS
795 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
796 return gen_rtx_ADDRESS (VOIDmode, src);
801 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
804 /* ... fall through ... */
809 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
811 /* If either operand is a REG that is a known pointer, then it
813 if (REG_P (src_0) && REG_POINTER (src_0))
814 return find_base_value (src_0);
815 if (REG_P (src_1) && REG_POINTER (src_1))
816 return find_base_value (src_1);
818 /* If either operand is a REG, then see if we already have
819 a known value for it. */
822 temp = find_base_value (src_0);
829 temp = find_base_value (src_1);
834 /* If either base is named object or a special address
835 (like an argument or stack reference), then use it for the
838 && (GET_CODE (src_0) == SYMBOL_REF
839 || GET_CODE (src_0) == LABEL_REF
840 || (GET_CODE (src_0) == ADDRESS
841 && GET_MODE (src_0) != VOIDmode)))
845 && (GET_CODE (src_1) == SYMBOL_REF
846 || GET_CODE (src_1) == LABEL_REF
847 || (GET_CODE (src_1) == ADDRESS
848 && GET_MODE (src_1) != VOIDmode)))
851 /* Guess which operand is the base address:
852 If either operand is a symbol, then it is the base. If
853 either operand is a CONST_INT, then the other is the base. */
854 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
855 return find_base_value (src_0);
856 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
857 return find_base_value (src_1);
863 /* The standard form is (lo_sum reg sym) so look only at the
865 return find_base_value (XEXP (src, 1));
868 /* If the second operand is constant set the base
869 address to the first operand. */
870 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
871 return find_base_value (XEXP (src, 0));
875 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
885 return find_base_value (XEXP (src, 0));
888 case SIGN_EXTEND: /* used for NT/Alpha pointers */
890 rtx temp = find_base_value (XEXP (src, 0));
892 #ifdef POINTERS_EXTEND_UNSIGNED
893 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode)
894 temp = convert_memory_address (Pmode, temp);
907 /* Called from init_alias_analysis indirectly through note_stores. */
909 /* While scanning insns to find base values, reg_seen[N] is nonzero if
910 register N has been set in this function. */
911 static char *reg_seen;
913 /* Addresses which are known not to alias anything else are identified
914 by a unique integer. */
915 static int unique_id;
918 record_set (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED)
924 if (GET_CODE (dest) != REG)
927 regno = REGNO (dest);
929 if (regno >= reg_base_value_size)
932 /* If this spans multiple hard registers, then we must indicate that every
933 register has an unusable value. */
934 if (regno < FIRST_PSEUDO_REGISTER)
935 n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
942 reg_seen[regno + n] = 1;
943 new_reg_base_value[regno + n] = 0;
950 /* A CLOBBER wipes out any old value but does not prevent a previously
951 unset register from acquiring a base address (i.e. reg_seen is not
953 if (GET_CODE (set) == CLOBBER)
955 new_reg_base_value[regno] = 0;
964 new_reg_base_value[regno] = 0;
968 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
969 GEN_INT (unique_id++));
973 /* This is not the first set. If the new value is not related to the
974 old value, forget the base value. Note that the following code is
976 extern int x, y; int *p = &x; p += (&y-&x);
977 ANSI C does not allow computing the difference of addresses
978 of distinct top level objects. */
979 if (new_reg_base_value[regno])
980 switch (GET_CODE (src))
984 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
985 new_reg_base_value[regno] = 0;
988 /* If the value we add in the PLUS is also a valid base value,
989 this might be the actual base value, and the original value
992 rtx other = NULL_RTX;
994 if (XEXP (src, 0) == dest)
995 other = XEXP (src, 1);
996 else if (XEXP (src, 1) == dest)
997 other = XEXP (src, 0);
999 if (! other || find_base_value (other))
1000 new_reg_base_value[regno] = 0;
1004 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
1005 new_reg_base_value[regno] = 0;
1008 new_reg_base_value[regno] = 0;
1011 /* If this is the first set of a register, record the value. */
1012 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1013 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1014 new_reg_base_value[regno] = find_base_value (src);
1016 reg_seen[regno] = 1;
1019 /* Called from loop optimization when a new pseudo-register is
1020 created. It indicates that REGNO is being set to VAL. f INVARIANT
1021 is true then this value also describes an invariant relationship
1022 which can be used to deduce that two registers with unknown values
1026 record_base_value (unsigned int regno, rtx val, int invariant)
1028 if (regno >= reg_base_value_size)
1031 if (invariant && alias_invariant)
1032 alias_invariant[regno] = val;
1034 if (GET_CODE (val) == REG)
1036 if (REGNO (val) < reg_base_value_size)
1037 reg_base_value[regno] = reg_base_value[REGNO (val)];
1042 reg_base_value[regno] = find_base_value (val);
1045 /* Clear alias info for a register. This is used if an RTL transformation
1046 changes the value of a register. This is used in flow by AUTO_INC_DEC
1047 optimizations. We don't need to clear reg_base_value, since flow only
1048 changes the offset. */
1051 clear_reg_alias_info (rtx reg)
1053 unsigned int regno = REGNO (reg);
1055 if (regno < reg_known_value_size && regno >= FIRST_PSEUDO_REGISTER)
1056 reg_known_value[regno] = reg;
1059 /* Returns a canonical version of X, from the point of view alias
1060 analysis. (For example, if X is a MEM whose address is a register,
1061 and the register has a known value (say a SYMBOL_REF), then a MEM
1062 whose address is the SYMBOL_REF is returned.) */
1067 /* Recursively look for equivalences. */
1068 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
1069 && REGNO (x) < reg_known_value_size)
1070 return reg_known_value[REGNO (x)] == x
1071 ? x : canon_rtx (reg_known_value[REGNO (x)]);
1072 else if (GET_CODE (x) == PLUS)
1074 rtx x0 = canon_rtx (XEXP (x, 0));
1075 rtx x1 = canon_rtx (XEXP (x, 1));
1077 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1079 if (GET_CODE (x0) == CONST_INT)
1080 return plus_constant (x1, INTVAL (x0));
1081 else if (GET_CODE (x1) == CONST_INT)
1082 return plus_constant (x0, INTVAL (x1));
1083 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1087 /* This gives us much better alias analysis when called from
1088 the loop optimizer. Note we want to leave the original
1089 MEM alone, but need to return the canonicalized MEM with
1090 all the flags with their original values. */
1091 else if (GET_CODE (x) == MEM)
1092 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1097 /* Return 1 if X and Y are identical-looking rtx's.
1098 Expect that X and Y has been already canonicalized.
1100 We use the data in reg_known_value above to see if two registers with
1101 different numbers are, in fact, equivalent. */
1104 rtx_equal_for_memref_p (rtx x, rtx y)
1111 if (x == 0 && y == 0)
1113 if (x == 0 || y == 0)
1119 code = GET_CODE (x);
1120 /* Rtx's of different codes cannot be equal. */
1121 if (code != GET_CODE (y))
1124 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1125 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1127 if (GET_MODE (x) != GET_MODE (y))
1130 /* Some RTL can be compared without a recursive examination. */
1134 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
1137 return REGNO (x) == REGNO (y);
1140 return XEXP (x, 0) == XEXP (y, 0);
1143 return XSTR (x, 0) == XSTR (y, 0);
1147 /* There's no need to compare the contents of CONST_DOUBLEs or
1148 CONST_INTs because pointer equality is a good enough
1149 comparison for these nodes. */
1153 return (XINT (x, 1) == XINT (y, 1)
1154 && rtx_equal_for_memref_p (XEXP (x, 0),
1161 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1163 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1164 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1165 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1166 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1167 /* For commutative operations, the RTX match if the operand match in any
1168 order. Also handle the simple binary and unary cases without a loop. */
1169 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
1171 rtx xop0 = canon_rtx (XEXP (x, 0));
1172 rtx yop0 = canon_rtx (XEXP (y, 0));
1173 rtx yop1 = canon_rtx (XEXP (y, 1));
1175 return ((rtx_equal_for_memref_p (xop0, yop0)
1176 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1177 || (rtx_equal_for_memref_p (xop0, yop1)
1178 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1180 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
1182 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1183 canon_rtx (XEXP (y, 0)))
1184 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1185 canon_rtx (XEXP (y, 1))));
1187 else if (GET_RTX_CLASS (code) == '1')
1188 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1189 canon_rtx (XEXP (y, 0)));
1191 /* Compare the elements. If any pair of corresponding elements
1192 fail to match, return 0 for the whole things.
1194 Limit cases to types which actually appear in addresses. */
1196 fmt = GET_RTX_FORMAT (code);
1197 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1202 if (XINT (x, i) != XINT (y, i))
1207 /* Two vectors must have the same length. */
1208 if (XVECLEN (x, i) != XVECLEN (y, i))
1211 /* And the corresponding elements must match. */
1212 for (j = 0; j < XVECLEN (x, i); j++)
1213 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1214 canon_rtx (XVECEXP (y, i, j))) == 0)
1219 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1220 canon_rtx (XEXP (y, i))) == 0)
1224 /* This can happen for asm operands. */
1226 if (strcmp (XSTR (x, i), XSTR (y, i)))
1230 /* This can happen for an asm which clobbers memory. */
1234 /* It is believed that rtx's at this level will never
1235 contain anything but integers and other rtx's,
1236 except for within LABEL_REFs and SYMBOL_REFs. */
1244 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1245 X and return it, or return 0 if none found. */
1248 find_symbolic_term (rtx x)
1254 code = GET_CODE (x);
1255 if (code == SYMBOL_REF || code == LABEL_REF)
1257 if (GET_RTX_CLASS (code) == 'o')
1260 fmt = GET_RTX_FORMAT (code);
1261 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1267 t = find_symbolic_term (XEXP (x, i));
1271 else if (fmt[i] == 'E')
1278 find_base_term (rtx x)
1281 struct elt_loc_list *l;
1283 #if defined (FIND_BASE_TERM)
1284 /* Try machine-dependent ways to find the base term. */
1285 x = FIND_BASE_TERM (x);
1288 switch (GET_CODE (x))
1291 return REG_BASE_VALUE (x);
1294 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1304 return find_base_term (XEXP (x, 0));
1307 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1309 rtx temp = find_base_term (XEXP (x, 0));
1311 #ifdef POINTERS_EXTEND_UNSIGNED
1312 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode)
1313 temp = convert_memory_address (Pmode, temp);
1320 val = CSELIB_VAL_PTR (x);
1321 for (l = val->locs; l; l = l->next)
1322 if ((x = find_base_term (l->loc)) != 0)
1328 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1335 rtx tmp1 = XEXP (x, 0);
1336 rtx tmp2 = XEXP (x, 1);
1338 /* This is a little bit tricky since we have to determine which of
1339 the two operands represents the real base address. Otherwise this
1340 routine may return the index register instead of the base register.
1342 That may cause us to believe no aliasing was possible, when in
1343 fact aliasing is possible.
1345 We use a few simple tests to guess the base register. Additional
1346 tests can certainly be added. For example, if one of the operands
1347 is a shift or multiply, then it must be the index register and the
1348 other operand is the base register. */
1350 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1351 return find_base_term (tmp2);
1353 /* If either operand is known to be a pointer, then use it
1354 to determine the base term. */
1355 if (REG_P (tmp1) && REG_POINTER (tmp1))
1356 return find_base_term (tmp1);
1358 if (REG_P (tmp2) && REG_POINTER (tmp2))
1359 return find_base_term (tmp2);
1361 /* Neither operand was known to be a pointer. Go ahead and find the
1362 base term for both operands. */
1363 tmp1 = find_base_term (tmp1);
1364 tmp2 = find_base_term (tmp2);
1366 /* If either base term is named object or a special address
1367 (like an argument or stack reference), then use it for the
1370 && (GET_CODE (tmp1) == SYMBOL_REF
1371 || GET_CODE (tmp1) == LABEL_REF
1372 || (GET_CODE (tmp1) == ADDRESS
1373 && GET_MODE (tmp1) != VOIDmode)))
1377 && (GET_CODE (tmp2) == SYMBOL_REF
1378 || GET_CODE (tmp2) == LABEL_REF
1379 || (GET_CODE (tmp2) == ADDRESS
1380 && GET_MODE (tmp2) != VOIDmode)))
1383 /* We could not determine which of the two operands was the
1384 base register and which was the index. So we can determine
1385 nothing from the base alias check. */
1390 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0)
1391 return find_base_term (XEXP (x, 0));
1399 return REG_BASE_VALUE (frame_pointer_rtx);
1406 /* Return 0 if the addresses X and Y are known to point to different
1407 objects, 1 if they might be pointers to the same object. */
1410 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1411 enum machine_mode y_mode)
1413 rtx x_base = find_base_term (x);
1414 rtx y_base = find_base_term (y);
1416 /* If the address itself has no known base see if a known equivalent
1417 value has one. If either address still has no known base, nothing
1418 is known about aliasing. */
1423 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1426 x_base = find_base_term (x_c);
1434 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1437 y_base = find_base_term (y_c);
1442 /* If the base addresses are equal nothing is known about aliasing. */
1443 if (rtx_equal_p (x_base, y_base))
1446 /* The base addresses of the read and write are different expressions.
1447 If they are both symbols and they are not accessed via AND, there is
1448 no conflict. We can bring knowledge of object alignment into play
1449 here. For example, on alpha, "char a, b;" can alias one another,
1450 though "char a; long b;" cannot. */
1451 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1453 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1455 if (GET_CODE (x) == AND
1456 && (GET_CODE (XEXP (x, 1)) != CONST_INT
1457 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1459 if (GET_CODE (y) == AND
1460 && (GET_CODE (XEXP (y, 1)) != CONST_INT
1461 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1463 /* Differing symbols never alias. */
1467 /* If one address is a stack reference there can be no alias:
1468 stack references using different base registers do not alias,
1469 a stack reference can not alias a parameter, and a stack reference
1470 can not alias a global. */
1471 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1472 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1475 if (! flag_argument_noalias)
1478 if (flag_argument_noalias > 1)
1481 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1482 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1485 /* Convert the address X into something we can use. This is done by returning
1486 it unchanged unless it is a value; in the latter case we call cselib to get
1487 a more useful rtx. */
1493 struct elt_loc_list *l;
1495 if (GET_CODE (x) != VALUE)
1497 v = CSELIB_VAL_PTR (x);
1498 for (l = v->locs; l; l = l->next)
1499 if (CONSTANT_P (l->loc))
1501 for (l = v->locs; l; l = l->next)
1502 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
1505 return v->locs->loc;
1509 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1510 where SIZE is the size in bytes of the memory reference. If ADDR
1511 is not modified by the memory reference then ADDR is returned. */
1514 addr_side_effect_eval (rtx addr, int size, int n_refs)
1518 switch (GET_CODE (addr))
1521 offset = (n_refs + 1) * size;
1524 offset = -(n_refs + 1) * size;
1527 offset = n_refs * size;
1530 offset = -n_refs * size;
1538 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1541 addr = XEXP (addr, 0);
1542 addr = canon_rtx (addr);
1547 /* Return nonzero if X and Y (memory addresses) could reference the
1548 same location in memory. C is an offset accumulator. When
1549 C is nonzero, we are testing aliases between X and Y + C.
1550 XSIZE is the size in bytes of the X reference,
1551 similarly YSIZE is the size in bytes for Y.
1552 Expect that canon_rtx has been already called for X and Y.
1554 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1555 referenced (the reference was BLKmode), so make the most pessimistic
1558 If XSIZE or YSIZE is negative, we may access memory outside the object
1559 being referenced as a side effect. This can happen when using AND to
1560 align memory references, as is done on the Alpha.
1562 Nice to notice that varying addresses cannot conflict with fp if no
1563 local variables had their addresses taken, but that's too hard now. */
1566 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1568 if (GET_CODE (x) == VALUE)
1570 if (GET_CODE (y) == VALUE)
1572 if (GET_CODE (x) == HIGH)
1574 else if (GET_CODE (x) == LO_SUM)
1577 x = addr_side_effect_eval (x, xsize, 0);
1578 if (GET_CODE (y) == HIGH)
1580 else if (GET_CODE (y) == LO_SUM)
1583 y = addr_side_effect_eval (y, ysize, 0);
1585 if (rtx_equal_for_memref_p (x, y))
1587 if (xsize <= 0 || ysize <= 0)
1589 if (c >= 0 && xsize > c)
1591 if (c < 0 && ysize+c > 0)
1596 /* This code used to check for conflicts involving stack references and
1597 globals but the base address alias code now handles these cases. */
1599 if (GET_CODE (x) == PLUS)
1601 /* The fact that X is canonicalized means that this
1602 PLUS rtx is canonicalized. */
1603 rtx x0 = XEXP (x, 0);
1604 rtx x1 = XEXP (x, 1);
1606 if (GET_CODE (y) == PLUS)
1608 /* The fact that Y is canonicalized means that this
1609 PLUS rtx is canonicalized. */
1610 rtx y0 = XEXP (y, 0);
1611 rtx y1 = XEXP (y, 1);
1613 if (rtx_equal_for_memref_p (x1, y1))
1614 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1615 if (rtx_equal_for_memref_p (x0, y0))
1616 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1617 if (GET_CODE (x1) == CONST_INT)
1619 if (GET_CODE (y1) == CONST_INT)
1620 return memrefs_conflict_p (xsize, x0, ysize, y0,
1621 c - INTVAL (x1) + INTVAL (y1));
1623 return memrefs_conflict_p (xsize, x0, ysize, y,
1626 else if (GET_CODE (y1) == CONST_INT)
1627 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1631 else if (GET_CODE (x1) == CONST_INT)
1632 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1634 else if (GET_CODE (y) == PLUS)
1636 /* The fact that Y is canonicalized means that this
1637 PLUS rtx is canonicalized. */
1638 rtx y0 = XEXP (y, 0);
1639 rtx y1 = XEXP (y, 1);
1641 if (GET_CODE (y1) == CONST_INT)
1642 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1647 if (GET_CODE (x) == GET_CODE (y))
1648 switch (GET_CODE (x))
1652 /* Handle cases where we expect the second operands to be the
1653 same, and check only whether the first operand would conflict
1656 rtx x1 = canon_rtx (XEXP (x, 1));
1657 rtx y1 = canon_rtx (XEXP (y, 1));
1658 if (! rtx_equal_for_memref_p (x1, y1))
1660 x0 = canon_rtx (XEXP (x, 0));
1661 y0 = canon_rtx (XEXP (y, 0));
1662 if (rtx_equal_for_memref_p (x0, y0))
1663 return (xsize == 0 || ysize == 0
1664 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1666 /* Can't properly adjust our sizes. */
1667 if (GET_CODE (x1) != CONST_INT)
1669 xsize /= INTVAL (x1);
1670 ysize /= INTVAL (x1);
1672 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1676 /* Are these registers known not to be equal? */
1677 if (alias_invariant)
1679 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1680 rtx i_x, i_y; /* invariant relationships of X and Y */
1682 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1683 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1685 if (i_x == 0 && i_y == 0)
1688 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1689 ysize, i_y ? i_y : y, c))
1698 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1699 as an access with indeterminate size. Assume that references
1700 besides AND are aligned, so if the size of the other reference is
1701 at least as large as the alignment, assume no other overlap. */
1702 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1704 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1706 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1708 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1710 /* ??? If we are indexing far enough into the array/structure, we
1711 may yet be able to determine that we can not overlap. But we
1712 also need to that we are far enough from the end not to overlap
1713 a following reference, so we do nothing with that for now. */
1714 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1716 return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1719 if (GET_CODE (x) == ADDRESSOF)
1721 if (y == frame_pointer_rtx
1722 || GET_CODE (y) == ADDRESSOF)
1723 return xsize <= 0 || ysize <= 0;
1725 if (GET_CODE (y) == ADDRESSOF)
1727 if (x == frame_pointer_rtx)
1728 return xsize <= 0 || ysize <= 0;
1733 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1735 c += (INTVAL (y) - INTVAL (x));
1736 return (xsize <= 0 || ysize <= 0
1737 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1740 if (GET_CODE (x) == CONST)
1742 if (GET_CODE (y) == CONST)
1743 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1744 ysize, canon_rtx (XEXP (y, 0)), c);
1746 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1749 if (GET_CODE (y) == CONST)
1750 return memrefs_conflict_p (xsize, x, ysize,
1751 canon_rtx (XEXP (y, 0)), c);
1754 return (xsize <= 0 || ysize <= 0
1755 || (rtx_equal_for_memref_p (x, y)
1756 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1763 /* Functions to compute memory dependencies.
1765 Since we process the insns in execution order, we can build tables
1766 to keep track of what registers are fixed (and not aliased), what registers
1767 are varying in known ways, and what registers are varying in unknown
1770 If both memory references are volatile, then there must always be a
1771 dependence between the two references, since their order can not be
1772 changed. A volatile and non-volatile reference can be interchanged
1775 A MEM_IN_STRUCT reference at a non-AND varying address can never
1776 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1777 also must allow AND addresses, because they may generate accesses
1778 outside the object being referenced. This is used to generate
1779 aligned addresses from unaligned addresses, for instance, the alpha
1780 storeqi_unaligned pattern. */
1782 /* Read dependence: X is read after read in MEM takes place. There can
1783 only be a dependence here if both reads are volatile. */
1786 read_dependence (rtx mem, rtx x)
1788 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1791 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1792 MEM2 is a reference to a structure at a varying address, or returns
1793 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1794 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1795 to decide whether or not an address may vary; it should return
1796 nonzero whenever variation is possible.
1797 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1800 fixed_scalar_and_varying_struct_p (rtx mem1, rtx mem2, rtx mem1_addr,
1802 int (*varies_p) (rtx, int))
1804 if (! flag_strict_aliasing)
1807 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1808 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1809 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1813 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1814 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1815 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1822 /* Returns nonzero if something about the mode or address format MEM1
1823 indicates that it might well alias *anything*. */
1826 aliases_everything_p (rtx mem)
1828 if (GET_CODE (XEXP (mem, 0)) == AND)
1829 /* If the address is an AND, its very hard to know at what it is
1830 actually pointing. */
1836 /* Return true if we can determine that the fields referenced cannot
1837 overlap for any pair of objects. */
1840 nonoverlapping_component_refs_p (tree x, tree y)
1842 tree fieldx, fieldy, typex, typey, orig_y;
1846 /* The comparison has to be done at a common type, since we don't
1847 know how the inheritance hierarchy works. */
1851 fieldx = TREE_OPERAND (x, 1);
1852 typex = DECL_FIELD_CONTEXT (fieldx);
1857 fieldy = TREE_OPERAND (y, 1);
1858 typey = DECL_FIELD_CONTEXT (fieldy);
1863 y = TREE_OPERAND (y, 0);
1865 while (y && TREE_CODE (y) == COMPONENT_REF);
1867 x = TREE_OPERAND (x, 0);
1869 while (x && TREE_CODE (x) == COMPONENT_REF);
1871 /* Never found a common type. */
1875 /* If we're left with accessing different fields of a structure,
1877 if (TREE_CODE (typex) == RECORD_TYPE
1878 && fieldx != fieldy)
1881 /* The comparison on the current field failed. If we're accessing
1882 a very nested structure, look at the next outer level. */
1883 x = TREE_OPERAND (x, 0);
1884 y = TREE_OPERAND (y, 0);
1887 && TREE_CODE (x) == COMPONENT_REF
1888 && TREE_CODE (y) == COMPONENT_REF);
1893 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1896 decl_for_component_ref (tree x)
1900 x = TREE_OPERAND (x, 0);
1902 while (x && TREE_CODE (x) == COMPONENT_REF);
1904 return x && DECL_P (x) ? x : NULL_TREE;
1907 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1908 offset of the field reference. */
1911 adjust_offset_for_component_ref (tree x, rtx offset)
1913 HOST_WIDE_INT ioffset;
1918 ioffset = INTVAL (offset);
1921 tree field = TREE_OPERAND (x, 1);
1923 if (! host_integerp (DECL_FIELD_OFFSET (field), 1))
1925 ioffset += (tree_low_cst (DECL_FIELD_OFFSET (field), 1)
1926 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
1929 x = TREE_OPERAND (x, 0);
1931 while (x && TREE_CODE (x) == COMPONENT_REF);
1933 return GEN_INT (ioffset);
1936 /* Return nonzero if we can determine the exprs corresponding to memrefs
1937 X and Y and they do not overlap. */
1940 nonoverlapping_memrefs_p (rtx x, rtx y)
1942 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
1945 rtx moffsetx, moffsety;
1946 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
1948 /* Unless both have exprs, we can't tell anything. */
1949 if (exprx == 0 || expry == 0)
1952 /* If both are field references, we may be able to determine something. */
1953 if (TREE_CODE (exprx) == COMPONENT_REF
1954 && TREE_CODE (expry) == COMPONENT_REF
1955 && nonoverlapping_component_refs_p (exprx, expry))
1958 /* If the field reference test failed, look at the DECLs involved. */
1959 moffsetx = MEM_OFFSET (x);
1960 if (TREE_CODE (exprx) == COMPONENT_REF)
1962 tree t = decl_for_component_ref (exprx);
1965 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
1968 else if (TREE_CODE (exprx) == INDIRECT_REF)
1970 exprx = TREE_OPERAND (exprx, 0);
1971 if (flag_argument_noalias < 2
1972 || TREE_CODE (exprx) != PARM_DECL)
1976 moffsety = MEM_OFFSET (y);
1977 if (TREE_CODE (expry) == COMPONENT_REF)
1979 tree t = decl_for_component_ref (expry);
1982 moffsety = adjust_offset_for_component_ref (expry, moffsety);
1985 else if (TREE_CODE (expry) == INDIRECT_REF)
1987 expry = TREE_OPERAND (expry, 0);
1988 if (flag_argument_noalias < 2
1989 || TREE_CODE (expry) != PARM_DECL)
1993 if (! DECL_P (exprx) || ! DECL_P (expry))
1996 rtlx = DECL_RTL (exprx);
1997 rtly = DECL_RTL (expry);
1999 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2000 can't overlap unless they are the same because we never reuse that part
2001 of the stack frame used for locals for spilled pseudos. */
2002 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM)
2003 && ! rtx_equal_p (rtlx, rtly))
2006 /* Get the base and offsets of both decls. If either is a register, we
2007 know both are and are the same, so use that as the base. The only
2008 we can avoid overlap is if we can deduce that they are nonoverlapping
2009 pieces of that decl, which is very rare. */
2010 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx;
2011 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT)
2012 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2014 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly;
2015 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT)
2016 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2018 /* If the bases are different, we know they do not overlap if both
2019 are constants or if one is a constant and the other a pointer into the
2020 stack frame. Otherwise a different base means we can't tell if they
2022 if (! rtx_equal_p (basex, basey))
2023 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2024 || (CONSTANT_P (basex) && REG_P (basey)
2025 && REGNO_PTR_FRAME_P (REGNO (basey)))
2026 || (CONSTANT_P (basey) && REG_P (basex)
2027 && REGNO_PTR_FRAME_P (REGNO (basex))));
2029 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2030 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2032 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2033 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2036 /* If we have an offset for either memref, it can update the values computed
2039 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2041 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2043 /* If a memref has both a size and an offset, we can use the smaller size.
2044 We can't do this if the offset isn't known because we must view this
2045 memref as being anywhere inside the DECL's MEM. */
2046 if (MEM_SIZE (x) && moffsetx)
2047 sizex = INTVAL (MEM_SIZE (x));
2048 if (MEM_SIZE (y) && moffsety)
2049 sizey = INTVAL (MEM_SIZE (y));
2051 /* Put the values of the memref with the lower offset in X's values. */
2052 if (offsetx > offsety)
2054 tem = offsetx, offsetx = offsety, offsety = tem;
2055 tem = sizex, sizex = sizey, sizey = tem;
2058 /* If we don't know the size of the lower-offset value, we can't tell
2059 if they conflict. Otherwise, we do the test. */
2060 return sizex >= 0 && offsety >= offsetx + sizex;
2063 /* True dependence: X is read after store in MEM takes place. */
2066 true_dependence (rtx mem, enum machine_mode mem_mode, rtx x,
2067 int (*varies) (rtx, int))
2069 rtx x_addr, mem_addr;
2072 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2075 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2076 This is used in epilogue deallocation functions. */
2077 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2079 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2082 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2085 /* Unchanging memory can't conflict with non-unchanging memory.
2086 A non-unchanging read can conflict with a non-unchanging write.
2087 An unchanging read can conflict with an unchanging write since
2088 there may be a single store to this address to initialize it.
2089 Note that an unchanging store can conflict with a non-unchanging read
2090 since we have to make conservative assumptions when we have a
2091 record with readonly fields and we are copying the whole thing.
2092 Just fall through to the code below to resolve potential conflicts.
2093 This won't handle all cases optimally, but the possible performance
2094 loss should be negligible. */
2095 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2098 if (nonoverlapping_memrefs_p (mem, x))
2101 if (mem_mode == VOIDmode)
2102 mem_mode = GET_MODE (mem);
2104 x_addr = get_addr (XEXP (x, 0));
2105 mem_addr = get_addr (XEXP (mem, 0));
2107 base = find_base_term (x_addr);
2108 if (base && (GET_CODE (base) == LABEL_REF
2109 || (GET_CODE (base) == SYMBOL_REF
2110 && CONSTANT_POOL_ADDRESS_P (base))))
2113 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2116 x_addr = canon_rtx (x_addr);
2117 mem_addr = canon_rtx (mem_addr);
2119 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2120 SIZE_FOR_MODE (x), x_addr, 0))
2123 if (aliases_everything_p (x))
2126 /* We cannot use aliases_everything_p to test MEM, since we must look
2127 at MEM_MODE, rather than GET_MODE (MEM). */
2128 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2131 /* In true_dependence we also allow BLKmode to alias anything. Why
2132 don't we do this in anti_dependence and output_dependence? */
2133 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2136 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2140 /* Canonical true dependence: X is read after store in MEM takes place.
2141 Variant of true_dependence which assumes MEM has already been
2142 canonicalized (hence we no longer do that here).
2143 The mem_addr argument has been added, since true_dependence computed
2144 this value prior to canonicalizing. */
2147 canon_true_dependence (rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2148 rtx x, int (*varies) (rtx, int))
2152 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2155 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2156 This is used in epilogue deallocation functions. */
2157 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2159 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2162 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2165 /* If X is an unchanging read, then it can't possibly conflict with any
2166 non-unchanging store. It may conflict with an unchanging write though,
2167 because there may be a single store to this address to initialize it.
2168 Just fall through to the code below to resolve the case where we have
2169 both an unchanging read and an unchanging write. This won't handle all
2170 cases optimally, but the possible performance loss should be
2172 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
2175 if (nonoverlapping_memrefs_p (x, mem))
2178 x_addr = get_addr (XEXP (x, 0));
2180 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2183 x_addr = canon_rtx (x_addr);
2184 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2185 SIZE_FOR_MODE (x), x_addr, 0))
2188 if (aliases_everything_p (x))
2191 /* We cannot use aliases_everything_p to test MEM, since we must look
2192 at MEM_MODE, rather than GET_MODE (MEM). */
2193 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2196 /* In true_dependence we also allow BLKmode to alias anything. Why
2197 don't we do this in anti_dependence and output_dependence? */
2198 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2201 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2205 /* Returns nonzero if a write to X might alias a previous read from
2206 (or, if WRITEP is nonzero, a write to) MEM. */
2209 write_dependence_p (rtx mem, rtx x, int writep)
2211 rtx x_addr, mem_addr;
2215 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2218 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2219 This is used in epilogue deallocation functions. */
2220 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2222 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2225 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2228 /* Unchanging memory can't conflict with non-unchanging memory. */
2229 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem))
2232 /* If MEM is an unchanging read, then it can't possibly conflict with
2233 the store to X, because there is at most one store to MEM, and it must
2234 have occurred somewhere before MEM. */
2235 if (! writep && RTX_UNCHANGING_P (mem))
2238 if (nonoverlapping_memrefs_p (x, mem))
2241 x_addr = get_addr (XEXP (x, 0));
2242 mem_addr = get_addr (XEXP (mem, 0));
2246 base = find_base_term (mem_addr);
2247 if (base && (GET_CODE (base) == LABEL_REF
2248 || (GET_CODE (base) == SYMBOL_REF
2249 && CONSTANT_POOL_ADDRESS_P (base))))
2253 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2257 x_addr = canon_rtx (x_addr);
2258 mem_addr = canon_rtx (mem_addr);
2260 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2261 SIZE_FOR_MODE (x), x_addr, 0))
2265 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2268 return (!(fixed_scalar == mem && !aliases_everything_p (x))
2269 && !(fixed_scalar == x && !aliases_everything_p (mem)));
2272 /* Anti dependence: X is written after read in MEM takes place. */
2275 anti_dependence (rtx mem, rtx x)
2277 return write_dependence_p (mem, x, /*writep=*/0);
2280 /* Output dependence: X is written after store in MEM takes place. */
2283 output_dependence (rtx mem, rtx x)
2285 return write_dependence_p (mem, x, /*writep=*/1);
2288 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2289 something which is not local to the function and is not constant. */
2292 nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2301 switch (GET_CODE (x))
2304 if (GET_CODE (SUBREG_REG (x)) == REG)
2306 /* Global registers are not local. */
2307 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
2308 && global_regs[subreg_regno (x)])
2316 /* Global registers are not local. */
2317 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2332 /* Constants in the function's constants pool are constant. */
2333 if (CONSTANT_POOL_ADDRESS_P (x))
2338 /* Non-constant calls and recursion are not local. */
2342 /* Be overly conservative and consider any volatile memory
2343 reference as not local. */
2344 if (MEM_VOLATILE_P (x))
2346 base = find_base_term (XEXP (x, 0));
2349 /* A Pmode ADDRESS could be a reference via the structure value
2350 address or static chain. Such memory references are nonlocal.
2352 Thus, we have to examine the contents of the ADDRESS to find
2353 out if this is a local reference or not. */
2354 if (GET_CODE (base) == ADDRESS
2355 && GET_MODE (base) == Pmode
2356 && (XEXP (base, 0) == stack_pointer_rtx
2357 || XEXP (base, 0) == arg_pointer_rtx
2358 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2359 || XEXP (base, 0) == hard_frame_pointer_rtx
2361 || XEXP (base, 0) == frame_pointer_rtx))
2363 /* Constants in the function's constant pool are constant. */
2364 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
2369 case UNSPEC_VOLATILE:
2374 if (MEM_VOLATILE_P (x))
2386 /* Returns nonzero if X might mention something which is not
2387 local to the function and is not constant. */
2390 nonlocal_mentioned_p (rtx x)
2394 if (GET_CODE (x) == CALL_INSN)
2396 if (! CONST_OR_PURE_CALL_P (x))
2398 x = CALL_INSN_FUNCTION_USAGE (x);
2406 return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL);
2409 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2410 something which is not local to the function and is not constant. */
2413 nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2420 switch (GET_CODE (x))
2426 return nonlocal_mentioned_p (x);
2429 /* Non-constant calls and recursion are not local. */
2433 if (nonlocal_mentioned_p (SET_SRC (x)))
2436 if (GET_CODE (SET_DEST (x)) == MEM)
2437 return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0));
2439 /* If the destination is anything other than a CC0, PC,
2440 MEM, REG, or a SUBREG of a REG that occupies all of
2441 the REG, then X references nonlocal memory if it is
2442 mentioned in the destination. */
2443 if (GET_CODE (SET_DEST (x)) != CC0
2444 && GET_CODE (SET_DEST (x)) != PC
2445 && GET_CODE (SET_DEST (x)) != REG
2446 && ! (GET_CODE (SET_DEST (x)) == SUBREG
2447 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
2448 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
2449 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
2450 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
2451 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
2452 return nonlocal_mentioned_p (SET_DEST (x));
2456 if (GET_CODE (XEXP (x, 0)) == MEM)
2457 return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0));
2461 return nonlocal_mentioned_p (XEXP (x, 0));
2464 case UNSPEC_VOLATILE:
2468 if (MEM_VOLATILE_P (x))
2480 /* Returns nonzero if X might reference something which is not
2481 local to the function and is not constant. */
2484 nonlocal_referenced_p (rtx x)
2488 if (GET_CODE (x) == CALL_INSN)
2490 if (! CONST_OR_PURE_CALL_P (x))
2492 x = CALL_INSN_FUNCTION_USAGE (x);
2500 return for_each_rtx (&x, nonlocal_referenced_p_1, NULL);
2503 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2504 something which is not local to the function and is not constant. */
2507 nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2514 switch (GET_CODE (x))
2517 /* Non-constant calls and recursion are not local. */
2526 return nonlocal_mentioned_p (XEXP (x, 0));
2529 if (nonlocal_mentioned_p (SET_DEST (x)))
2531 return nonlocal_set_p (SET_SRC (x));
2534 return nonlocal_mentioned_p (XEXP (x, 0));
2540 case UNSPEC_VOLATILE:
2544 if (MEM_VOLATILE_P (x))
2556 /* Returns nonzero if X might set something which is not
2557 local to the function and is not constant. */
2560 nonlocal_set_p (rtx x)
2564 if (GET_CODE (x) == CALL_INSN)
2566 if (! CONST_OR_PURE_CALL_P (x))
2568 x = CALL_INSN_FUNCTION_USAGE (x);
2576 return for_each_rtx (&x, nonlocal_set_p_1, NULL);
2579 /* Mark the function if it is pure or constant. */
2582 mark_constant_function (void)
2585 int nonlocal_memory_referenced;
2587 if (TREE_READONLY (current_function_decl)
2588 || DECL_IS_PURE (current_function_decl)
2589 || TREE_THIS_VOLATILE (current_function_decl)
2590 || current_function_has_nonlocal_goto
2591 || !(*targetm.binds_local_p) (current_function_decl))
2594 /* A loop might not return which counts as a side effect. */
2595 if (mark_dfs_back_edges ())
2598 nonlocal_memory_referenced = 0;
2600 init_alias_analysis ();
2602 /* Determine if this is a constant or pure function. */
2604 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2606 if (! INSN_P (insn))
2609 if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn)
2610 || volatile_refs_p (PATTERN (insn)))
2613 if (! nonlocal_memory_referenced)
2614 nonlocal_memory_referenced = nonlocal_referenced_p (insn);
2617 end_alias_analysis ();
2619 /* Mark the function. */
2623 else if (nonlocal_memory_referenced)
2625 cgraph_rtl_info (current_function_decl)->pure_function = 1;
2626 DECL_IS_PURE (current_function_decl) = 1;
2630 cgraph_rtl_info (current_function_decl)->const_function = 1;
2631 TREE_READONLY (current_function_decl) = 1;
2637 init_alias_once (void)
2641 #ifndef OUTGOING_REGNO
2642 #define OUTGOING_REGNO(N) N
2644 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2645 /* Check whether this register can hold an incoming pointer
2646 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2647 numbers, so translate if necessary due to register windows. */
2648 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2649 && HARD_REGNO_MODE_OK (i, Pmode))
2650 static_reg_base_value[i]
2651 = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2653 static_reg_base_value[STACK_POINTER_REGNUM]
2654 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2655 static_reg_base_value[ARG_POINTER_REGNUM]
2656 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2657 static_reg_base_value[FRAME_POINTER_REGNUM]
2658 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2659 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2660 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2661 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2664 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
2667 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2668 to be memory reference. */
2669 static bool memory_modified;
2671 memory_modified_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
2673 if (GET_CODE (x) == MEM)
2675 if (anti_dependence (x, (rtx)data) || output_dependence (x, (rtx)data))
2676 memory_modified = true;
2681 /* Return true when INSN possibly modify memory contents of MEM
2682 (ie address can be modified). */
2684 memory_modified_in_insn_p (rtx mem, rtx insn)
2688 memory_modified = false;
2689 note_stores (PATTERN (insn), memory_modified_1, mem);
2690 return memory_modified;
2693 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2697 init_alias_analysis (void)
2699 int maxreg = max_reg_num ();
2705 timevar_push (TV_ALIAS_ANALYSIS);
2707 reg_known_value_size = maxreg;
2710 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx))
2711 - FIRST_PSEUDO_REGISTER;
2713 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char))
2714 - FIRST_PSEUDO_REGISTER;
2716 /* Overallocate reg_base_value to allow some growth during loop
2717 optimization. Loop unrolling can create a large number of
2719 reg_base_value_size = maxreg * 2;
2720 reg_base_value = (rtx *) ggc_alloc_cleared (reg_base_value_size
2723 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx));
2724 reg_seen = (char *) xmalloc (reg_base_value_size);
2725 if (! reload_completed && flag_old_unroll_loops)
2727 /* ??? Why are we realloc'ing if we're just going to zero it? */
2728 alias_invariant = (rtx *)xrealloc (alias_invariant,
2729 reg_base_value_size * sizeof (rtx));
2730 memset ((char *)alias_invariant, 0, reg_base_value_size * sizeof (rtx));
2733 /* The basic idea is that each pass through this loop will use the
2734 "constant" information from the previous pass to propagate alias
2735 information through another level of assignments.
2737 This could get expensive if the assignment chains are long. Maybe
2738 we should throttle the number of iterations, possibly based on
2739 the optimization level or flag_expensive_optimizations.
2741 We could propagate more information in the first pass by making use
2742 of REG_N_SETS to determine immediately that the alias information
2743 for a pseudo is "constant".
2745 A program with an uninitialized variable can cause an infinite loop
2746 here. Instead of doing a full dataflow analysis to detect such problems
2747 we just cap the number of iterations for the loop.
2749 The state of the arrays for the set chain in question does not matter
2750 since the program has undefined behavior. */
2755 /* Assume nothing will change this iteration of the loop. */
2758 /* We want to assign the same IDs each iteration of this loop, so
2759 start counting from zero each iteration of the loop. */
2762 /* We're at the start of the function each iteration through the
2763 loop, so we're copying arguments. */
2764 copying_arguments = true;
2766 /* Wipe the potential alias information clean for this pass. */
2767 memset ((char *) new_reg_base_value, 0, reg_base_value_size * sizeof (rtx));
2769 /* Wipe the reg_seen array clean. */
2770 memset ((char *) reg_seen, 0, reg_base_value_size);
2772 /* Mark all hard registers which may contain an address.
2773 The stack, frame and argument pointers may contain an address.
2774 An argument register which can hold a Pmode value may contain
2775 an address even if it is not in BASE_REGS.
2777 The address expression is VOIDmode for an argument and
2778 Pmode for other registers. */
2780 memcpy (new_reg_base_value, static_reg_base_value,
2781 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2783 /* Walk the insns adding values to the new_reg_base_value array. */
2784 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2790 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2791 /* The prologue/epilogue insns are not threaded onto the
2792 insn chain until after reload has completed. Thus,
2793 there is no sense wasting time checking if INSN is in
2794 the prologue/epilogue until after reload has completed. */
2795 if (reload_completed
2796 && prologue_epilogue_contains (insn))
2800 /* If this insn has a noalias note, process it, Otherwise,
2801 scan for sets. A simple set will have no side effects
2802 which could change the base value of any other register. */
2804 if (GET_CODE (PATTERN (insn)) == SET
2805 && REG_NOTES (insn) != 0
2806 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2807 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2809 note_stores (PATTERN (insn), record_set, NULL);
2811 set = single_set (insn);
2814 && GET_CODE (SET_DEST (set)) == REG
2815 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2817 unsigned int regno = REGNO (SET_DEST (set));
2818 rtx src = SET_SRC (set);
2820 if (REG_NOTES (insn) != 0
2821 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2822 && REG_N_SETS (regno) == 1)
2823 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
2824 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2825 && ! rtx_varies_p (XEXP (note, 0), 1)
2826 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
2828 reg_known_value[regno] = XEXP (note, 0);
2829 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
2831 else if (REG_N_SETS (regno) == 1
2832 && GET_CODE (src) == PLUS
2833 && GET_CODE (XEXP (src, 0)) == REG
2834 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
2835 && (reg_known_value[REGNO (XEXP (src, 0))])
2836 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2838 rtx op0 = XEXP (src, 0);
2839 op0 = reg_known_value[REGNO (op0)];
2840 reg_known_value[regno]
2841 = plus_constant (op0, INTVAL (XEXP (src, 1)));
2842 reg_known_equiv_p[regno] = 0;
2844 else if (REG_N_SETS (regno) == 1
2845 && ! rtx_varies_p (src, 1))
2847 reg_known_value[regno] = src;
2848 reg_known_equiv_p[regno] = 0;
2852 else if (GET_CODE (insn) == NOTE
2853 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
2854 copying_arguments = false;
2857 /* Now propagate values from new_reg_base_value to reg_base_value. */
2858 for (ui = 0; ui < reg_base_value_size; ui++)
2860 if (new_reg_base_value[ui]
2861 && new_reg_base_value[ui] != reg_base_value[ui]
2862 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
2864 reg_base_value[ui] = new_reg_base_value[ui];
2869 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2871 /* Fill in the remaining entries. */
2872 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
2873 if (reg_known_value[i] == 0)
2874 reg_known_value[i] = regno_reg_rtx[i];
2876 /* Simplify the reg_base_value array so that no register refers to
2877 another register, except to special registers indirectly through
2878 ADDRESS expressions.
2880 In theory this loop can take as long as O(registers^2), but unless
2881 there are very long dependency chains it will run in close to linear
2884 This loop may not be needed any longer now that the main loop does
2885 a better job at propagating alias information. */
2891 for (ui = 0; ui < reg_base_value_size; ui++)
2893 rtx base = reg_base_value[ui];
2894 if (base && GET_CODE (base) == REG)
2896 unsigned int base_regno = REGNO (base);
2897 if (base_regno == ui) /* register set from itself */
2898 reg_base_value[ui] = 0;
2900 reg_base_value[ui] = reg_base_value[base_regno];
2905 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
2908 free (new_reg_base_value);
2909 new_reg_base_value = 0;
2912 timevar_pop (TV_ALIAS_ANALYSIS);
2916 end_alias_analysis (void)
2918 free (reg_known_value + FIRST_PSEUDO_REGISTER);
2919 reg_known_value = 0;
2920 reg_known_value_size = 0;
2921 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER);
2922 reg_known_equiv_p = 0;
2924 reg_base_value_size = 0;
2925 if (alias_invariant)
2927 free (alias_invariant);
2928 alias_invariant = 0;
2932 #include "gt-alias.h"