1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
36 #include "splay-tree.h"
39 /* The alias sets assigned to MEMs assist the back-end in determining
40 which MEMs can alias which other MEMs. In general, two MEMs in
41 different alias sets cannot alias each other, with one important
42 exception. Consider something like:
44 struct S {int i; double d; };
46 a store to an `S' can alias something of either type `int' or type
47 `double'. (However, a store to an `int' cannot alias a `double'
48 and vice versa.) We indicate this via a tree structure that looks
56 (The arrows are directed and point downwards.)
57 In this situation we say the alias set for `struct S' is the
58 `superset' and that those for `int' and `double' are `subsets'.
60 To see whether two alias sets can point to the same memory, we must
61 see if either alias set is a subset of the other. We need not trace
62 past immediate descendents, however, since we propagate all
63 grandchildren up one level.
65 Alias set zero is implicitly a superset of all other alias sets.
66 However, this is no actual entry for alias set zero. It is an
67 error to attempt to explicitly construct a subset of zero. */
69 typedef struct alias_set_entry
71 /* The alias set number, as stored in MEM_ALIAS_SET. */
72 HOST_WIDE_INT alias_set;
74 /* The children of the alias set. These are not just the immediate
75 children, but, in fact, all descendents. So, if we have:
77 struct T { struct S s; float f; }
79 continuing our example above, the children here will be all of
80 `int', `double', `float', and `struct S'. */
83 /* Nonzero if would have a child of zero: this effectively makes this
84 alias set the same as alias set zero. */
88 static int rtx_equal_for_memref_p PARAMS ((rtx, rtx));
89 static rtx find_symbolic_term PARAMS ((rtx));
90 rtx get_addr PARAMS ((rtx));
91 static int memrefs_conflict_p PARAMS ((int, rtx, int, rtx,
93 static void record_set PARAMS ((rtx, rtx, void *));
94 static rtx find_base_term PARAMS ((rtx));
95 static int base_alias_check PARAMS ((rtx, rtx, enum machine_mode,
97 static int handled_component_p PARAMS ((tree));
98 static int can_address_p PARAMS ((tree));
99 static rtx find_base_value PARAMS ((rtx));
100 static int mems_in_disjoint_alias_sets_p PARAMS ((rtx, rtx));
101 static int insert_subset_children PARAMS ((splay_tree_node, void*));
102 static tree find_base_decl PARAMS ((tree));
103 static alias_set_entry get_alias_set_entry PARAMS ((HOST_WIDE_INT));
104 static rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx,
105 int (*) (rtx, int)));
106 static int aliases_everything_p PARAMS ((rtx));
107 static int write_dependence_p PARAMS ((rtx, rtx, int));
108 static int nonlocal_mentioned_p PARAMS ((rtx));
110 /* Set up all info needed to perform alias analysis on memory references. */
112 /* Returns the size in bytes of the mode of X. */
113 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
115 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
116 different alias sets. We ignore alias sets in functions making use
117 of variable arguments because the va_arg macros on some systems are
119 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
120 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
122 /* Cap the number of passes we make over the insns propagating alias
123 information through set chains. 10 is a completely arbitrary choice. */
124 #define MAX_ALIAS_LOOP_PASSES 10
126 /* reg_base_value[N] gives an address to which register N is related.
127 If all sets after the first add or subtract to the current value
128 or otherwise modify it so it does not point to a different top level
129 object, reg_base_value[N] is equal to the address part of the source
132 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
133 expressions represent certain special values: function arguments and
134 the stack, frame, and argument pointers.
136 The contents of an ADDRESS is not normally used, the mode of the
137 ADDRESS determines whether the ADDRESS is a function argument or some
138 other special value. Pointer equality, not rtx_equal_p, determines whether
139 two ADDRESS expressions refer to the same base address.
141 The only use of the contents of an ADDRESS is for determining if the
142 current function performs nonlocal memory memory references for the
143 purposes of marking the function as a constant function. */
145 static rtx *reg_base_value;
146 static rtx *new_reg_base_value;
147 static unsigned int reg_base_value_size; /* size of reg_base_value array */
149 #define REG_BASE_VALUE(X) \
150 (REGNO (X) < reg_base_value_size \
151 ? reg_base_value[REGNO (X)] : 0)
153 /* Vector of known invariant relationships between registers. Set in
154 loop unrolling. Indexed by register number, if nonzero the value
155 is an expression describing this register in terms of another.
157 The length of this array is REG_BASE_VALUE_SIZE.
159 Because this array contains only pseudo registers it has no effect
161 static rtx *alias_invariant;
163 /* Vector indexed by N giving the initial (unchanging) value known for
164 pseudo-register N. This array is initialized in
165 init_alias_analysis, and does not change until end_alias_analysis
167 rtx *reg_known_value;
169 /* Indicates number of valid entries in reg_known_value. */
170 static unsigned int reg_known_value_size;
172 /* Vector recording for each reg_known_value whether it is due to a
173 REG_EQUIV note. Future passes (viz., reload) may replace the
174 pseudo with the equivalent expression and so we account for the
175 dependences that would be introduced if that happens.
177 The REG_EQUIV notes created in assign_parms may mention the arg
178 pointer, and there are explicit insns in the RTL that modify the
179 arg pointer. Thus we must ensure that such insns don't get
180 scheduled across each other because that would invalidate the
181 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
182 wrong, but solving the problem in the scheduler will likely give
183 better code, so we do it here. */
184 char *reg_known_equiv_p;
186 /* True when scanning insns from the start of the rtl to the
187 NOTE_INSN_FUNCTION_BEG note. */
188 static int copying_arguments;
190 /* The splay-tree used to store the various alias set entries. */
191 static splay_tree alias_sets;
193 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
194 such an entry, or NULL otherwise. */
196 static alias_set_entry
197 get_alias_set_entry (alias_set)
198 HOST_WIDE_INT alias_set;
201 = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
203 return sn != 0 ? ((alias_set_entry) sn->value) : 0;
206 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
207 the two MEMs cannot alias each other. */
210 mems_in_disjoint_alias_sets_p (mem1, mem2)
214 #ifdef ENABLE_CHECKING
215 /* Perform a basic sanity check. Namely, that there are no alias sets
216 if we're not using strict aliasing. This helps to catch bugs
217 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
218 where a MEM is allocated in some way other than by the use of
219 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
220 use alias sets to indicate that spilled registers cannot alias each
221 other, we might need to remove this check. */
222 if (! flag_strict_aliasing
223 && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0))
227 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
230 /* Insert the NODE into the splay tree given by DATA. Used by
231 record_alias_subset via splay_tree_foreach. */
234 insert_subset_children (node, data)
235 splay_tree_node node;
238 splay_tree_insert ((splay_tree) data, node->key, node->value);
243 /* Return 1 if the two specified alias sets may conflict. */
246 alias_sets_conflict_p (set1, set2)
247 HOST_WIDE_INT set1, set2;
251 /* If have no alias set information for one of the operands, we have
252 to assume it can alias anything. */
253 if (set1 == 0 || set2 == 0
254 /* If the two alias sets are the same, they may alias. */
258 /* See if the first alias set is a subset of the second. */
259 ase = get_alias_set_entry (set1);
261 && (ase->has_zero_child
262 || splay_tree_lookup (ase->children,
263 (splay_tree_key) set2)))
266 /* Now do the same, but with the alias sets reversed. */
267 ase = get_alias_set_entry (set2);
269 && (ase->has_zero_child
270 || splay_tree_lookup (ase->children,
271 (splay_tree_key) set1)))
274 /* The two alias sets are distinct and neither one is the
275 child of the other. Therefore, they cannot alias. */
279 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
280 has any readonly fields. If any of the fields have types that
281 contain readonly fields, return true as well. */
284 readonly_fields_p (type)
289 if (TREE_CODE (type) != RECORD_TYPE && TREE_CODE (type) != UNION_TYPE
290 && TREE_CODE (type) != QUAL_UNION_TYPE)
293 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
294 if (TREE_CODE (field) == FIELD_DECL
295 && (TREE_READONLY (field)
296 || readonly_fields_p (TREE_TYPE (field))))
302 /* Return 1 if any MEM object of type T1 will always conflict (using the
303 dependency routines in this file) with any MEM object of type T2.
304 This is used when allocating temporary storage. If T1 and/or T2 are
305 NULL_TREE, it means we know nothing about the storage. */
308 objects_must_conflict_p (t1, t2)
311 /* If neither has a type specified, we don't know if they'll conflict
312 because we may be using them to store objects of various types, for
313 example the argument and local variables areas of inlined functions. */
314 if (t1 == 0 && t2 == 0)
317 /* If one or the other has readonly fields or is readonly,
318 then they may not conflict. */
319 if ((t1 != 0 && readonly_fields_p (t1))
320 || (t2 != 0 && readonly_fields_p (t2))
321 || (t1 != 0 && TYPE_READONLY (t1))
322 || (t2 != 0 && TYPE_READONLY (t2)))
325 /* If they are the same type, they must conflict. */
327 /* Likewise if both are volatile. */
328 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
331 /* If one is aggregate and the other is scalar then they may not
333 if ((t1 != 0 && AGGREGATE_TYPE_P (t1))
334 != (t2 != 0 && AGGREGATE_TYPE_P (t2)))
337 /* Otherwise they conflict only if the alias sets conflict. */
338 return alias_sets_conflict_p (t1 ? get_alias_set (t1) : 0,
339 t2 ? get_alias_set (t2) : 0);
342 /* T is an expression with pointer type. Find the DECL on which this
343 expression is based. (For example, in `a[i]' this would be `a'.)
344 If there is no such DECL, or a unique decl cannot be determined,
345 NULL_TREE is retured. */
353 if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
356 /* If this is a declaration, return it. */
357 if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd')
360 /* Handle general expressions. It would be nice to deal with
361 COMPONENT_REFs here. If we could tell that `a' and `b' were the
362 same, then `a->f' and `b->f' are also the same. */
363 switch (TREE_CODE_CLASS (TREE_CODE (t)))
366 return find_base_decl (TREE_OPERAND (t, 0));
369 /* Return 0 if found in neither or both are the same. */
370 d0 = find_base_decl (TREE_OPERAND (t, 0));
371 d1 = find_base_decl (TREE_OPERAND (t, 1));
382 d0 = find_base_decl (TREE_OPERAND (t, 0));
383 d1 = find_base_decl (TREE_OPERAND (t, 1));
384 d2 = find_base_decl (TREE_OPERAND (t, 2));
386 /* Set any nonzero values from the last, then from the first. */
387 if (d1 == 0) d1 = d2;
388 if (d0 == 0) d0 = d1;
389 if (d1 == 0) d1 = d0;
390 if (d2 == 0) d2 = d1;
392 /* At this point all are nonzero or all are zero. If all three are the
393 same, return it. Otherwise, return zero. */
394 return (d0 == d1 && d1 == d2) ? d0 : 0;
401 /* Return 1 if T is an expression that get_inner_reference handles. */
404 handled_component_p (t)
407 switch (TREE_CODE (t))
412 case ARRAY_RANGE_REF:
413 case NON_LVALUE_EXPR:
418 return (TYPE_MODE (TREE_TYPE (t))
419 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (t, 0))));
426 /* Return 1 if all the nested component references handled by
427 get_inner_reference in T are such that we can address the object in T. */
433 /* If we're at the end, it is vacuously addressable. */
434 if (! handled_component_p (t))
437 /* Bitfields are never addressable. */
438 else if (TREE_CODE (t) == BIT_FIELD_REF)
441 else if (TREE_CODE (t) == COMPONENT_REF
442 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))
443 && can_address_p (TREE_OPERAND (t, 0)))
446 else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
447 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))
448 && can_address_p (TREE_OPERAND (t, 0)))
454 /* Return the alias set for T, which may be either a type or an
455 expression. Call language-specific routine for help, if needed. */
464 /* If we're not doing any alias analysis, just assume everything
465 aliases everything else. Also return 0 if this or its type is
467 if (! flag_strict_aliasing || t == error_mark_node
469 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
472 /* We can be passed either an expression or a type. This and the
473 language-specific routine may make mutually-recursive calls to each other
474 to figure out what to do. At each juncture, we see if this is a tree
475 that the language may need to handle specially. First handle things that
476 aren't types and start by removing nops since we care only about the
477 actual object. Also replace PLACEHOLDER_EXPRs and pick up the outermost
478 object that we could have a pointer to. */
481 /* Remove any NOPs and see what any PLACEHOLD_EXPRs will expand to. */
482 while (((TREE_CODE (t) == NOP_EXPR || TREE_CODE (t) == CONVERT_EXPR)
483 && (TYPE_MODE (TREE_TYPE (t))
484 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (t, 0)))))
485 || TREE_CODE (t) == NON_LVALUE_EXPR
486 || TREE_CODE (t) == PLACEHOLDER_EXPR
487 || (handled_component_p (t) && ! can_address_p (t)))
489 /* Give the language a chance to do something with this tree
490 before we go inside it. */
491 if ((set = lang_get_alias_set (t)) != -1)
494 if (TREE_CODE (t) == PLACEHOLDER_EXPR)
495 t = find_placeholder (t, 0);
497 t = TREE_OPERAND (t, 0);
500 /* Now give the language a chance to do something but record what we
501 gave it this time. */
503 if ((set = lang_get_alias_set (t)) != -1)
506 /* Check for accesses through restrict-qualified pointers. */
507 if (TREE_CODE (t) == INDIRECT_REF)
509 tree decl = find_base_decl (TREE_OPERAND (t, 0));
511 if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
512 /* We use the alias set indicated in the declaration. */
513 return DECL_POINTER_ALIAS_SET (decl);
515 /* If we have an INDIRECT_REF via a void pointer, we don't
516 know anything about what that might alias. */
517 if (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE)
521 /* If we've already determined the alias set for this decl, just
522 return it. This is necessary for C++ anonymous unions, whose
523 component variables don't look like union members (boo!). */
524 if (TREE_CODE (t) == VAR_DECL
525 && DECL_RTL_SET_P (t) && GET_CODE (DECL_RTL (t)) == MEM)
526 return MEM_ALIAS_SET (DECL_RTL (t));
528 /* Give the language another chance to do something special. */
530 && (set = lang_get_alias_set (t)) != -1)
533 /* Now all we care about is the type. */
537 /* Variant qualifiers don't affect the alias set, so get the main
538 variant. If this is a type with a known alias set, return it. */
539 t = TYPE_MAIN_VARIANT (t);
540 if (TYPE_P (t) && TYPE_ALIAS_SET_KNOWN_P (t))
541 return TYPE_ALIAS_SET (t);
543 /* See if the language has special handling for this type. */
544 if ((set = lang_get_alias_set (t)) != -1)
546 /* If the alias set is now known, we are done. */
547 if (TYPE_ALIAS_SET_KNOWN_P (t))
548 return TYPE_ALIAS_SET (t);
551 /* There are no objects of FUNCTION_TYPE, so there's no point in
552 using up an alias set for them. (There are, of course, pointers
553 and references to functions, but that's different.) */
554 else if (TREE_CODE (t) == FUNCTION_TYPE)
557 /* Otherwise make a new alias set for this type. */
558 set = new_alias_set ();
560 TYPE_ALIAS_SET (t) = set;
562 /* If this is an aggregate type, we must record any component aliasing
564 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
565 record_component_aliases (t);
570 /* Return a brand-new alias set. */
575 static HOST_WIDE_INT last_alias_set;
577 if (flag_strict_aliasing)
578 return ++last_alias_set;
583 /* Indicate that things in SUBSET can alias things in SUPERSET, but
584 not vice versa. For example, in C, a store to an `int' can alias a
585 structure containing an `int', but not vice versa. Here, the
586 structure would be the SUPERSET and `int' the SUBSET. This
587 function should be called only once per SUPERSET/SUBSET pair.
589 It is illegal for SUPERSET to be zero; everything is implicitly a
590 subset of alias set zero. */
593 record_alias_subset (superset, subset)
594 HOST_WIDE_INT superset;
595 HOST_WIDE_INT subset;
597 alias_set_entry superset_entry;
598 alias_set_entry subset_entry;
600 /* It is possible in complex type situations for both sets to be the same,
601 in which case we can ignore this operation. */
602 if (superset == subset)
608 superset_entry = get_alias_set_entry (superset);
609 if (superset_entry == 0)
611 /* Create an entry for the SUPERSET, so that we have a place to
612 attach the SUBSET. */
614 = (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
615 superset_entry->alias_set = superset;
616 superset_entry->children
617 = splay_tree_new (splay_tree_compare_ints, 0, 0);
618 superset_entry->has_zero_child = 0;
619 splay_tree_insert (alias_sets, (splay_tree_key) superset,
620 (splay_tree_value) superset_entry);
624 superset_entry->has_zero_child = 1;
627 subset_entry = get_alias_set_entry (subset);
628 /* If there is an entry for the subset, enter all of its children
629 (if they are not already present) as children of the SUPERSET. */
632 if (subset_entry->has_zero_child)
633 superset_entry->has_zero_child = 1;
635 splay_tree_foreach (subset_entry->children, insert_subset_children,
636 superset_entry->children);
639 /* Enter the SUBSET itself as a child of the SUPERSET. */
640 splay_tree_insert (superset_entry->children,
641 (splay_tree_key) subset, 0);
645 /* Record that component types of TYPE, if any, are part of that type for
646 aliasing purposes. For record types, we only record component types
647 for fields that are marked addressable. For array types, we always
648 record the component types, so the front end should not call this
649 function if the individual component aren't addressable. */
652 record_component_aliases (type)
655 HOST_WIDE_INT superset = get_alias_set (type);
661 switch (TREE_CODE (type))
664 if (! TYPE_NONALIASED_COMPONENT (type))
665 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
670 case QUAL_UNION_TYPE:
671 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
672 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
673 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
677 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
685 /* Allocate an alias set for use in storing and reading from the varargs
689 get_varargs_alias_set ()
691 static HOST_WIDE_INT set = -1;
694 set = new_alias_set ();
699 /* Likewise, but used for the fixed portions of the frame, e.g., register
703 get_frame_alias_set ()
705 static HOST_WIDE_INT set = -1;
708 set = new_alias_set ();
713 /* Inside SRC, the source of a SET, find a base address. */
716 find_base_value (src)
720 switch (GET_CODE (src))
728 /* At the start of a function, argument registers have known base
729 values which may be lost later. Returning an ADDRESS
730 expression here allows optimization based on argument values
731 even when the argument registers are used for other purposes. */
732 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
733 return new_reg_base_value[regno];
735 /* If a pseudo has a known base value, return it. Do not do this
736 for hard regs since it can result in a circular dependency
737 chain for registers which have values at function entry.
739 The test above is not sufficient because the scheduler may move
740 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
741 if (regno >= FIRST_PSEUDO_REGISTER
742 && regno < reg_base_value_size
743 && reg_base_value[regno])
744 return reg_base_value[regno];
749 /* Check for an argument passed in memory. Only record in the
750 copying-arguments block; it is too hard to track changes
752 if (copying_arguments
753 && (XEXP (src, 0) == arg_pointer_rtx
754 || (GET_CODE (XEXP (src, 0)) == PLUS
755 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
756 return gen_rtx_ADDRESS (VOIDmode, src);
761 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
764 /* ... fall through ... */
769 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
771 /* If either operand is a REG, then see if we already have
772 a known value for it. */
773 if (GET_CODE (src_0) == REG)
775 temp = find_base_value (src_0);
780 if (GET_CODE (src_1) == REG)
782 temp = find_base_value (src_1);
787 /* Guess which operand is the base address:
788 If either operand is a symbol, then it is the base. If
789 either operand is a CONST_INT, then the other is the base. */
790 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
791 return find_base_value (src_0);
792 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
793 return find_base_value (src_1);
795 /* This might not be necessary anymore:
796 If either operand is a REG that is a known pointer, then it
798 else if (GET_CODE (src_0) == REG && REG_POINTER (src_0))
799 return find_base_value (src_0);
800 else if (GET_CODE (src_1) == REG && REG_POINTER (src_1))
801 return find_base_value (src_1);
807 /* The standard form is (lo_sum reg sym) so look only at the
809 return find_base_value (XEXP (src, 1));
812 /* If the second operand is constant set the base
813 address to the first operand. */
814 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
815 return find_base_value (XEXP (src, 0));
819 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
823 case SIGN_EXTEND: /* used for NT/Alpha pointers */
825 return find_base_value (XEXP (src, 0));
834 /* Called from init_alias_analysis indirectly through note_stores. */
836 /* While scanning insns to find base values, reg_seen[N] is nonzero if
837 register N has been set in this function. */
838 static char *reg_seen;
840 /* Addresses which are known not to alias anything else are identified
841 by a unique integer. */
842 static int unique_id;
845 record_set (dest, set, data)
847 void *data ATTRIBUTE_UNUSED;
852 if (GET_CODE (dest) != REG)
855 regno = REGNO (dest);
857 if (regno >= reg_base_value_size)
862 /* A CLOBBER wipes out any old value but does not prevent a previously
863 unset register from acquiring a base address (i.e. reg_seen is not
865 if (GET_CODE (set) == CLOBBER)
867 new_reg_base_value[regno] = 0;
876 new_reg_base_value[regno] = 0;
880 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
881 GEN_INT (unique_id++));
885 /* This is not the first set. If the new value is not related to the
886 old value, forget the base value. Note that the following code is
888 extern int x, y; int *p = &x; p += (&y-&x);
889 ANSI C does not allow computing the difference of addresses
890 of distinct top level objects. */
891 if (new_reg_base_value[regno])
892 switch (GET_CODE (src))
896 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
897 new_reg_base_value[regno] = 0;
900 /* If the value we add in the PLUS is also a valid base value,
901 this might be the actual base value, and the original value
904 rtx other = NULL_RTX;
906 if (XEXP (src, 0) == dest)
907 other = XEXP (src, 1);
908 else if (XEXP (src, 1) == dest)
909 other = XEXP (src, 0);
911 if (! other || find_base_value (other))
912 new_reg_base_value[regno] = 0;
916 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
917 new_reg_base_value[regno] = 0;
920 new_reg_base_value[regno] = 0;
923 /* If this is the first set of a register, record the value. */
924 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
925 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
926 new_reg_base_value[regno] = find_base_value (src);
931 /* Called from loop optimization when a new pseudo-register is
932 created. It indicates that REGNO is being set to VAL. f INVARIANT
933 is true then this value also describes an invariant relationship
934 which can be used to deduce that two registers with unknown values
938 record_base_value (regno, val, invariant)
943 if (regno >= reg_base_value_size)
946 if (invariant && alias_invariant)
947 alias_invariant[regno] = val;
949 if (GET_CODE (val) == REG)
951 if (REGNO (val) < reg_base_value_size)
952 reg_base_value[regno] = reg_base_value[REGNO (val)];
957 reg_base_value[regno] = find_base_value (val);
960 /* Clear alias info for a register. This is used if an RTL transformation
961 changes the value of a register. This is used in flow by AUTO_INC_DEC
962 optimizations. We don't need to clear reg_base_value, since flow only
963 changes the offset. */
966 clear_reg_alias_info (reg)
969 unsigned int regno = REGNO (reg);
971 if (regno < reg_known_value_size && regno >= FIRST_PSEUDO_REGISTER)
972 reg_known_value[regno] = reg;
975 /* Returns a canonical version of X, from the point of view alias
976 analysis. (For example, if X is a MEM whose address is a register,
977 and the register has a known value (say a SYMBOL_REF), then a MEM
978 whose address is the SYMBOL_REF is returned.) */
984 /* Recursively look for equivalences. */
985 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
986 && REGNO (x) < reg_known_value_size)
987 return reg_known_value[REGNO (x)] == x
988 ? x : canon_rtx (reg_known_value[REGNO (x)]);
989 else if (GET_CODE (x) == PLUS)
991 rtx x0 = canon_rtx (XEXP (x, 0));
992 rtx x1 = canon_rtx (XEXP (x, 1));
994 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
996 if (GET_CODE (x0) == CONST_INT)
997 return plus_constant (x1, INTVAL (x0));
998 else if (GET_CODE (x1) == CONST_INT)
999 return plus_constant (x0, INTVAL (x1));
1000 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1004 /* This gives us much better alias analysis when called from
1005 the loop optimizer. Note we want to leave the original
1006 MEM alone, but need to return the canonicalized MEM with
1007 all the flags with their original values. */
1008 else if (GET_CODE (x) == MEM)
1009 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1014 /* Return 1 if X and Y are identical-looking rtx's.
1016 We use the data in reg_known_value above to see if two registers with
1017 different numbers are, in fact, equivalent. */
1020 rtx_equal_for_memref_p (x, y)
1028 if (x == 0 && y == 0)
1030 if (x == 0 || y == 0)
1039 code = GET_CODE (x);
1040 /* Rtx's of different codes cannot be equal. */
1041 if (code != GET_CODE (y))
1044 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1045 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1047 if (GET_MODE (x) != GET_MODE (y))
1050 /* Some RTL can be compared without a recursive examination. */
1054 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
1057 return REGNO (x) == REGNO (y);
1060 return XEXP (x, 0) == XEXP (y, 0);
1063 return XSTR (x, 0) == XSTR (y, 0);
1067 /* There's no need to compare the contents of CONST_DOUBLEs or
1068 CONST_INTs because pointer equality is a good enough
1069 comparison for these nodes. */
1073 return (XINT (x, 1) == XINT (y, 1)
1074 && rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)));
1080 /* For commutative operations, the RTX match if the operand match in any
1081 order. Also handle the simple binary and unary cases without a loop. */
1082 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
1083 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1084 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1085 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1086 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1087 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
1088 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1089 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
1090 else if (GET_RTX_CLASS (code) == '1')
1091 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
1093 /* Compare the elements. If any pair of corresponding elements
1094 fail to match, return 0 for the whole things.
1096 Limit cases to types which actually appear in addresses. */
1098 fmt = GET_RTX_FORMAT (code);
1099 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1104 if (XINT (x, i) != XINT (y, i))
1109 /* Two vectors must have the same length. */
1110 if (XVECLEN (x, i) != XVECLEN (y, i))
1113 /* And the corresponding elements must match. */
1114 for (j = 0; j < XVECLEN (x, i); j++)
1115 if (rtx_equal_for_memref_p (XVECEXP (x, i, j),
1116 XVECEXP (y, i, j)) == 0)
1121 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
1125 /* This can happen for asm operands. */
1127 if (strcmp (XSTR (x, i), XSTR (y, i)))
1131 /* This can happen for an asm which clobbers memory. */
1135 /* It is believed that rtx's at this level will never
1136 contain anything but integers and other rtx's,
1137 except for within LABEL_REFs and SYMBOL_REFs. */
1145 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1146 X and return it, or return 0 if none found. */
1149 find_symbolic_term (x)
1156 code = GET_CODE (x);
1157 if (code == SYMBOL_REF || code == LABEL_REF)
1159 if (GET_RTX_CLASS (code) == 'o')
1162 fmt = GET_RTX_FORMAT (code);
1163 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1169 t = find_symbolic_term (XEXP (x, i));
1173 else if (fmt[i] == 'E')
1184 struct elt_loc_list *l;
1186 #if defined (FIND_BASE_TERM)
1187 /* Try machine-dependent ways to find the base term. */
1188 x = FIND_BASE_TERM (x);
1191 switch (GET_CODE (x))
1194 return REG_BASE_VALUE (x);
1197 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1203 return find_base_term (XEXP (x, 0));
1206 val = CSELIB_VAL_PTR (x);
1207 for (l = val->locs; l; l = l->next)
1208 if ((x = find_base_term (l->loc)) != 0)
1214 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1221 rtx tmp1 = XEXP (x, 0);
1222 rtx tmp2 = XEXP (x, 1);
1224 /* This is a litle bit tricky since we have to determine which of
1225 the two operands represents the real base address. Otherwise this
1226 routine may return the index register instead of the base register.
1228 That may cause us to believe no aliasing was possible, when in
1229 fact aliasing is possible.
1231 We use a few simple tests to guess the base register. Additional
1232 tests can certainly be added. For example, if one of the operands
1233 is a shift or multiply, then it must be the index register and the
1234 other operand is the base register. */
1236 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1237 return find_base_term (tmp2);
1239 /* If either operand is known to be a pointer, then use it
1240 to determine the base term. */
1241 if (REG_P (tmp1) && REG_POINTER (tmp1))
1242 return find_base_term (tmp1);
1244 if (REG_P (tmp2) && REG_POINTER (tmp2))
1245 return find_base_term (tmp2);
1247 /* Neither operand was known to be a pointer. Go ahead and find the
1248 base term for both operands. */
1249 tmp1 = find_base_term (tmp1);
1250 tmp2 = find_base_term (tmp2);
1252 /* If either base term is named object or a special address
1253 (like an argument or stack reference), then use it for the
1256 && (GET_CODE (tmp1) == SYMBOL_REF
1257 || GET_CODE (tmp1) == LABEL_REF
1258 || (GET_CODE (tmp1) == ADDRESS
1259 && GET_MODE (tmp1) != VOIDmode)))
1263 && (GET_CODE (tmp2) == SYMBOL_REF
1264 || GET_CODE (tmp2) == LABEL_REF
1265 || (GET_CODE (tmp2) == ADDRESS
1266 && GET_MODE (tmp2) != VOIDmode)))
1269 /* We could not determine which of the two operands was the
1270 base register and which was the index. So we can determine
1271 nothing from the base alias check. */
1276 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
1277 return REG_BASE_VALUE (XEXP (x, 0));
1285 return REG_BASE_VALUE (frame_pointer_rtx);
1292 /* Return 0 if the addresses X and Y are known to point to different
1293 objects, 1 if they might be pointers to the same object. */
1296 base_alias_check (x, y, x_mode, y_mode)
1298 enum machine_mode x_mode, y_mode;
1300 rtx x_base = find_base_term (x);
1301 rtx y_base = find_base_term (y);
1303 /* If the address itself has no known base see if a known equivalent
1304 value has one. If either address still has no known base, nothing
1305 is known about aliasing. */
1310 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1313 x_base = find_base_term (x_c);
1321 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1324 y_base = find_base_term (y_c);
1329 /* If the base addresses are equal nothing is known about aliasing. */
1330 if (rtx_equal_p (x_base, y_base))
1333 /* The base addresses of the read and write are different expressions.
1334 If they are both symbols and they are not accessed via AND, there is
1335 no conflict. We can bring knowledge of object alignment into play
1336 here. For example, on alpha, "char a, b;" can alias one another,
1337 though "char a; long b;" cannot. */
1338 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1340 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1342 if (GET_CODE (x) == AND
1343 && (GET_CODE (XEXP (x, 1)) != CONST_INT
1344 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1346 if (GET_CODE (y) == AND
1347 && (GET_CODE (XEXP (y, 1)) != CONST_INT
1348 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1350 /* Differing symbols never alias. */
1354 /* If one address is a stack reference there can be no alias:
1355 stack references using different base registers do not alias,
1356 a stack reference can not alias a parameter, and a stack reference
1357 can not alias a global. */
1358 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1359 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1362 if (! flag_argument_noalias)
1365 if (flag_argument_noalias > 1)
1368 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1369 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1372 /* Convert the address X into something we can use. This is done by returning
1373 it unchanged unless it is a value; in the latter case we call cselib to get
1374 a more useful rtx. */
1381 struct elt_loc_list *l;
1383 if (GET_CODE (x) != VALUE)
1385 v = CSELIB_VAL_PTR (x);
1386 for (l = v->locs; l; l = l->next)
1387 if (CONSTANT_P (l->loc))
1389 for (l = v->locs; l; l = l->next)
1390 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
1393 return v->locs->loc;
1397 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1398 where SIZE is the size in bytes of the memory reference. If ADDR
1399 is not modified by the memory reference then ADDR is returned. */
1402 addr_side_effect_eval (addr, size, n_refs)
1409 switch (GET_CODE (addr))
1412 offset = (n_refs + 1) * size;
1415 offset = -(n_refs + 1) * size;
1418 offset = n_refs * size;
1421 offset = -n_refs * size;
1429 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset));
1431 addr = XEXP (addr, 0);
1436 /* Return nonzero if X and Y (memory addresses) could reference the
1437 same location in memory. C is an offset accumulator. When
1438 C is nonzero, we are testing aliases between X and Y + C.
1439 XSIZE is the size in bytes of the X reference,
1440 similarly YSIZE is the size in bytes for Y.
1442 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1443 referenced (the reference was BLKmode), so make the most pessimistic
1446 If XSIZE or YSIZE is negative, we may access memory outside the object
1447 being referenced as a side effect. This can happen when using AND to
1448 align memory references, as is done on the Alpha.
1450 Nice to notice that varying addresses cannot conflict with fp if no
1451 local variables had their addresses taken, but that's too hard now. */
1454 memrefs_conflict_p (xsize, x, ysize, y, c)
1459 if (GET_CODE (x) == VALUE)
1461 if (GET_CODE (y) == VALUE)
1463 if (GET_CODE (x) == HIGH)
1465 else if (GET_CODE (x) == LO_SUM)
1468 x = canon_rtx (addr_side_effect_eval (x, xsize, 0));
1469 if (GET_CODE (y) == HIGH)
1471 else if (GET_CODE (y) == LO_SUM)
1474 y = canon_rtx (addr_side_effect_eval (y, ysize, 0));
1476 if (rtx_equal_for_memref_p (x, y))
1478 if (xsize <= 0 || ysize <= 0)
1480 if (c >= 0 && xsize > c)
1482 if (c < 0 && ysize+c > 0)
1487 /* This code used to check for conflicts involving stack references and
1488 globals but the base address alias code now handles these cases. */
1490 if (GET_CODE (x) == PLUS)
1492 /* The fact that X is canonicalized means that this
1493 PLUS rtx is canonicalized. */
1494 rtx x0 = XEXP (x, 0);
1495 rtx x1 = XEXP (x, 1);
1497 if (GET_CODE (y) == PLUS)
1499 /* The fact that Y is canonicalized means that this
1500 PLUS rtx is canonicalized. */
1501 rtx y0 = XEXP (y, 0);
1502 rtx y1 = XEXP (y, 1);
1504 if (rtx_equal_for_memref_p (x1, y1))
1505 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1506 if (rtx_equal_for_memref_p (x0, y0))
1507 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1508 if (GET_CODE (x1) == CONST_INT)
1510 if (GET_CODE (y1) == CONST_INT)
1511 return memrefs_conflict_p (xsize, x0, ysize, y0,
1512 c - INTVAL (x1) + INTVAL (y1));
1514 return memrefs_conflict_p (xsize, x0, ysize, y,
1517 else if (GET_CODE (y1) == CONST_INT)
1518 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1522 else if (GET_CODE (x1) == CONST_INT)
1523 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1525 else if (GET_CODE (y) == PLUS)
1527 /* The fact that Y is canonicalized means that this
1528 PLUS rtx is canonicalized. */
1529 rtx y0 = XEXP (y, 0);
1530 rtx y1 = XEXP (y, 1);
1532 if (GET_CODE (y1) == CONST_INT)
1533 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1538 if (GET_CODE (x) == GET_CODE (y))
1539 switch (GET_CODE (x))
1543 /* Handle cases where we expect the second operands to be the
1544 same, and check only whether the first operand would conflict
1547 rtx x1 = canon_rtx (XEXP (x, 1));
1548 rtx y1 = canon_rtx (XEXP (y, 1));
1549 if (! rtx_equal_for_memref_p (x1, y1))
1551 x0 = canon_rtx (XEXP (x, 0));
1552 y0 = canon_rtx (XEXP (y, 0));
1553 if (rtx_equal_for_memref_p (x0, y0))
1554 return (xsize == 0 || ysize == 0
1555 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1557 /* Can't properly adjust our sizes. */
1558 if (GET_CODE (x1) != CONST_INT)
1560 xsize /= INTVAL (x1);
1561 ysize /= INTVAL (x1);
1563 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1567 /* Are these registers known not to be equal? */
1568 if (alias_invariant)
1570 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1571 rtx i_x, i_y; /* invariant relationships of X and Y */
1573 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1574 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1576 if (i_x == 0 && i_y == 0)
1579 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1580 ysize, i_y ? i_y : y, c))
1589 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1590 as an access with indeterminate size. Assume that references
1591 besides AND are aligned, so if the size of the other reference is
1592 at least as large as the alignment, assume no other overlap. */
1593 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1595 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1597 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c);
1599 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1601 /* ??? If we are indexing far enough into the array/structure, we
1602 may yet be able to determine that we can not overlap. But we
1603 also need to that we are far enough from the end not to overlap
1604 a following reference, so we do nothing with that for now. */
1605 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1607 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c);
1610 if (GET_CODE (x) == ADDRESSOF)
1612 if (y == frame_pointer_rtx
1613 || GET_CODE (y) == ADDRESSOF)
1614 return xsize <= 0 || ysize <= 0;
1616 if (GET_CODE (y) == ADDRESSOF)
1618 if (x == frame_pointer_rtx)
1619 return xsize <= 0 || ysize <= 0;
1624 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1626 c += (INTVAL (y) - INTVAL (x));
1627 return (xsize <= 0 || ysize <= 0
1628 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1631 if (GET_CODE (x) == CONST)
1633 if (GET_CODE (y) == CONST)
1634 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1635 ysize, canon_rtx (XEXP (y, 0)), c);
1637 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1640 if (GET_CODE (y) == CONST)
1641 return memrefs_conflict_p (xsize, x, ysize,
1642 canon_rtx (XEXP (y, 0)), c);
1645 return (xsize <= 0 || ysize <= 0
1646 || (rtx_equal_for_memref_p (x, y)
1647 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1654 /* Functions to compute memory dependencies.
1656 Since we process the insns in execution order, we can build tables
1657 to keep track of what registers are fixed (and not aliased), what registers
1658 are varying in known ways, and what registers are varying in unknown
1661 If both memory references are volatile, then there must always be a
1662 dependence between the two references, since their order can not be
1663 changed. A volatile and non-volatile reference can be interchanged
1666 A MEM_IN_STRUCT reference at a non-AND varying address can never
1667 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1668 also must allow AND addresses, because they may generate accesses
1669 outside the object being referenced. This is used to generate
1670 aligned addresses from unaligned addresses, for instance, the alpha
1671 storeqi_unaligned pattern. */
1673 /* Read dependence: X is read after read in MEM takes place. There can
1674 only be a dependence here if both reads are volatile. */
1677 read_dependence (mem, x)
1681 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1684 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1685 MEM2 is a reference to a structure at a varying address, or returns
1686 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1687 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1688 to decide whether or not an address may vary; it should return
1689 nonzero whenever variation is possible.
1690 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1693 fixed_scalar_and_varying_struct_p (mem1, mem2, mem1_addr, mem2_addr, varies_p)
1695 rtx mem1_addr, mem2_addr;
1696 int (*varies_p) PARAMS ((rtx, int));
1698 if (! flag_strict_aliasing)
1701 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1702 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1703 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1707 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1708 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1709 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1716 /* Returns nonzero if something about the mode or address format MEM1
1717 indicates that it might well alias *anything*. */
1720 aliases_everything_p (mem)
1723 if (GET_CODE (XEXP (mem, 0)) == AND)
1724 /* If the address is an AND, its very hard to know at what it is
1725 actually pointing. */
1731 /* True dependence: X is read after store in MEM takes place. */
1734 true_dependence (mem, mem_mode, x, varies)
1736 enum machine_mode mem_mode;
1738 int (*varies) PARAMS ((rtx, int));
1740 rtx x_addr, mem_addr;
1743 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1746 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1749 /* Unchanging memory can't conflict with non-unchanging memory.
1750 A non-unchanging read can conflict with a non-unchanging write.
1751 An unchanging read can conflict with an unchanging write since
1752 there may be a single store to this address to initialize it.
1753 Note that an unchanging store can conflict with a non-unchanging read
1754 since we have to make conservative assumptions when we have a
1755 record with readonly fields and we are copying the whole thing.
1756 Just fall through to the code below to resolve potential conflicts.
1757 This won't handle all cases optimally, but the possible performance
1758 loss should be negligible. */
1759 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
1762 if (mem_mode == VOIDmode)
1763 mem_mode = GET_MODE (mem);
1765 x_addr = get_addr (XEXP (x, 0));
1766 mem_addr = get_addr (XEXP (mem, 0));
1768 base = find_base_term (x_addr);
1769 if (base && (GET_CODE (base) == LABEL_REF
1770 || (GET_CODE (base) == SYMBOL_REF
1771 && CONSTANT_POOL_ADDRESS_P (base))))
1774 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
1777 x_addr = canon_rtx (x_addr);
1778 mem_addr = canon_rtx (mem_addr);
1780 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
1781 SIZE_FOR_MODE (x), x_addr, 0))
1784 if (aliases_everything_p (x))
1787 /* We cannot use aliases_everyting_p to test MEM, since we must look
1788 at MEM_MODE, rather than GET_MODE (MEM). */
1789 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
1792 /* In true_dependence we also allow BLKmode to alias anything. Why
1793 don't we do this in anti_dependence and output_dependence? */
1794 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
1797 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
1801 /* Canonical true dependence: X is read after store in MEM takes place.
1802 Variant of true_dependece which assumes MEM has already been
1803 canonicalized (hence we no longer do that here).
1804 The mem_addr argument has been added, since true_dependence computed
1805 this value prior to canonicalizing. */
1808 canon_true_dependence (mem, mem_mode, mem_addr, x, varies)
1809 rtx mem, mem_addr, x;
1810 enum machine_mode mem_mode;
1811 int (*varies) PARAMS ((rtx, int));
1815 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1818 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1821 /* If X is an unchanging read, then it can't possibly conflict with any
1822 non-unchanging store. It may conflict with an unchanging write though,
1823 because there may be a single store to this address to initialize it.
1824 Just fall through to the code below to resolve the case where we have
1825 both an unchanging read and an unchanging write. This won't handle all
1826 cases optimally, but the possible performance loss should be
1828 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
1831 x_addr = get_addr (XEXP (x, 0));
1833 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
1836 x_addr = canon_rtx (x_addr);
1837 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
1838 SIZE_FOR_MODE (x), x_addr, 0))
1841 if (aliases_everything_p (x))
1844 /* We cannot use aliases_everyting_p to test MEM, since we must look
1845 at MEM_MODE, rather than GET_MODE (MEM). */
1846 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
1849 /* In true_dependence we also allow BLKmode to alias anything. Why
1850 don't we do this in anti_dependence and output_dependence? */
1851 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
1854 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
1858 /* Returns non-zero if a write to X might alias a previous read from
1859 (or, if WRITEP is non-zero, a write to) MEM. */
1862 write_dependence_p (mem, x, writep)
1867 rtx x_addr, mem_addr;
1871 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1874 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1877 /* Unchanging memory can't conflict with non-unchanging memory. */
1878 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem))
1881 /* If MEM is an unchanging read, then it can't possibly conflict with
1882 the store to X, because there is at most one store to MEM, and it must
1883 have occurred somewhere before MEM. */
1884 if (! writep && RTX_UNCHANGING_P (mem))
1887 x_addr = get_addr (XEXP (x, 0));
1888 mem_addr = get_addr (XEXP (mem, 0));
1892 base = find_base_term (mem_addr);
1893 if (base && (GET_CODE (base) == LABEL_REF
1894 || (GET_CODE (base) == SYMBOL_REF
1895 && CONSTANT_POOL_ADDRESS_P (base))))
1899 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
1903 x_addr = canon_rtx (x_addr);
1904 mem_addr = canon_rtx (mem_addr);
1906 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
1907 SIZE_FOR_MODE (x), x_addr, 0))
1911 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
1914 return (!(fixed_scalar == mem && !aliases_everything_p (x))
1915 && !(fixed_scalar == x && !aliases_everything_p (mem)));
1918 /* Anti dependence: X is written after read in MEM takes place. */
1921 anti_dependence (mem, x)
1925 return write_dependence_p (mem, x, /*writep=*/0);
1928 /* Output dependence: X is written after store in MEM takes place. */
1931 output_dependence (mem, x)
1935 return write_dependence_p (mem, x, /*writep=*/1);
1938 /* Returns non-zero if X mentions something which is not
1939 local to the function and is not constant. */
1942 nonlocal_mentioned_p (x)
1949 code = GET_CODE (x);
1951 if (GET_RTX_CLASS (code) == 'i')
1953 /* Constant functions can be constant if they don't use
1954 scratch memory used to mark function w/o side effects. */
1955 if (code == CALL_INSN && CONST_OR_PURE_CALL_P (x))
1957 x = CALL_INSN_FUNCTION_USAGE (x);
1963 code = GET_CODE (x);
1969 if (GET_CODE (SUBREG_REG (x)) == REG)
1971 /* Global registers are not local. */
1972 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
1973 && global_regs[subreg_regno (x)])
1981 /* Global registers are not local. */
1982 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1996 /* Constants in the function's constants pool are constant. */
1997 if (CONSTANT_POOL_ADDRESS_P (x))
2002 /* Non-constant calls and recursion are not local. */
2006 /* Be overly conservative and consider any volatile memory
2007 reference as not local. */
2008 if (MEM_VOLATILE_P (x))
2010 base = find_base_term (XEXP (x, 0));
2013 /* A Pmode ADDRESS could be a reference via the structure value
2014 address or static chain. Such memory references are nonlocal.
2016 Thus, we have to examine the contents of the ADDRESS to find
2017 out if this is a local reference or not. */
2018 if (GET_CODE (base) == ADDRESS
2019 && GET_MODE (base) == Pmode
2020 && (XEXP (base, 0) == stack_pointer_rtx
2021 || XEXP (base, 0) == arg_pointer_rtx
2022 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2023 || XEXP (base, 0) == hard_frame_pointer_rtx
2025 || XEXP (base, 0) == frame_pointer_rtx))
2027 /* Constants in the function's constant pool are constant. */
2028 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
2033 case UNSPEC_VOLATILE:
2038 if (MEM_VOLATILE_P (x))
2047 /* Recursively scan the operands of this expression. */
2050 const char *fmt = GET_RTX_FORMAT (code);
2053 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2055 if (fmt[i] == 'e' && XEXP (x, i))
2057 if (nonlocal_mentioned_p (XEXP (x, i)))
2060 else if (fmt[i] == 'E')
2063 for (j = 0; j < XVECLEN (x, i); j++)
2064 if (nonlocal_mentioned_p (XVECEXP (x, i, j)))
2073 /* Mark the function if it is constant. */
2076 mark_constant_function ()
2079 int nonlocal_mentioned;
2081 if (TREE_PUBLIC (current_function_decl)
2082 || TREE_READONLY (current_function_decl)
2083 || DECL_IS_PURE (current_function_decl)
2084 || TREE_THIS_VOLATILE (current_function_decl)
2085 || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode)
2088 /* A loop might not return which counts as a side effect. */
2089 if (mark_dfs_back_edges ())
2092 nonlocal_mentioned = 0;
2094 init_alias_analysis ();
2096 /* Determine if this is a constant function. */
2098 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2099 if (INSN_P (insn) && nonlocal_mentioned_p (insn))
2101 nonlocal_mentioned = 1;
2105 end_alias_analysis ();
2107 /* Mark the function. */
2109 if (! nonlocal_mentioned)
2110 TREE_READONLY (current_function_decl) = 1;
2114 static HARD_REG_SET argument_registers;
2121 #ifndef OUTGOING_REGNO
2122 #define OUTGOING_REGNO(N) N
2124 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2125 /* Check whether this register can hold an incoming pointer
2126 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2127 numbers, so translate if necessary due to register windows. */
2128 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2129 && HARD_REGNO_MODE_OK (i, Pmode))
2130 SET_HARD_REG_BIT (argument_registers, i);
2132 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
2135 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2139 init_alias_analysis ()
2141 int maxreg = max_reg_num ();
2147 reg_known_value_size = maxreg;
2150 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx))
2151 - FIRST_PSEUDO_REGISTER;
2153 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char))
2154 - FIRST_PSEUDO_REGISTER;
2156 /* Overallocate reg_base_value to allow some growth during loop
2157 optimization. Loop unrolling can create a large number of
2159 reg_base_value_size = maxreg * 2;
2160 reg_base_value = (rtx *) xcalloc (reg_base_value_size, sizeof (rtx));
2161 ggc_add_rtx_root (reg_base_value, reg_base_value_size);
2163 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx));
2164 reg_seen = (char *) xmalloc (reg_base_value_size);
2165 if (! reload_completed && flag_unroll_loops)
2167 /* ??? Why are we realloc'ing if we're just going to zero it? */
2168 alias_invariant = (rtx *)xrealloc (alias_invariant,
2169 reg_base_value_size * sizeof (rtx));
2170 memset ((char *)alias_invariant, 0, reg_base_value_size * sizeof (rtx));
2173 /* The basic idea is that each pass through this loop will use the
2174 "constant" information from the previous pass to propagate alias
2175 information through another level of assignments.
2177 This could get expensive if the assignment chains are long. Maybe
2178 we should throttle the number of iterations, possibly based on
2179 the optimization level or flag_expensive_optimizations.
2181 We could propagate more information in the first pass by making use
2182 of REG_N_SETS to determine immediately that the alias information
2183 for a pseudo is "constant".
2185 A program with an uninitialized variable can cause an infinite loop
2186 here. Instead of doing a full dataflow analysis to detect such problems
2187 we just cap the number of iterations for the loop.
2189 The state of the arrays for the set chain in question does not matter
2190 since the program has undefined behavior. */
2195 /* Assume nothing will change this iteration of the loop. */
2198 /* We want to assign the same IDs each iteration of this loop, so
2199 start counting from zero each iteration of the loop. */
2202 /* We're at the start of the funtion each iteration through the
2203 loop, so we're copying arguments. */
2204 copying_arguments = 1;
2206 /* Wipe the potential alias information clean for this pass. */
2207 memset ((char *) new_reg_base_value, 0, reg_base_value_size * sizeof (rtx));
2209 /* Wipe the reg_seen array clean. */
2210 memset ((char *) reg_seen, 0, reg_base_value_size);
2212 /* Mark all hard registers which may contain an address.
2213 The stack, frame and argument pointers may contain an address.
2214 An argument register which can hold a Pmode value may contain
2215 an address even if it is not in BASE_REGS.
2217 The address expression is VOIDmode for an argument and
2218 Pmode for other registers. */
2220 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2221 if (TEST_HARD_REG_BIT (argument_registers, i))
2222 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
2223 gen_rtx_REG (Pmode, i));
2225 new_reg_base_value[STACK_POINTER_REGNUM]
2226 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2227 new_reg_base_value[ARG_POINTER_REGNUM]
2228 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2229 new_reg_base_value[FRAME_POINTER_REGNUM]
2230 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2231 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2232 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2233 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2236 /* Walk the insns adding values to the new_reg_base_value array. */
2237 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2243 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2244 /* The prologue/epilouge insns are not threaded onto the
2245 insn chain until after reload has completed. Thus,
2246 there is no sense wasting time checking if INSN is in
2247 the prologue/epilogue until after reload has completed. */
2248 if (reload_completed
2249 && prologue_epilogue_contains (insn))
2253 /* If this insn has a noalias note, process it, Otherwise,
2254 scan for sets. A simple set will have no side effects
2255 which could change the base value of any other register. */
2257 if (GET_CODE (PATTERN (insn)) == SET
2258 && REG_NOTES (insn) != 0
2259 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2260 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2262 note_stores (PATTERN (insn), record_set, NULL);
2264 set = single_set (insn);
2267 && GET_CODE (SET_DEST (set)) == REG
2268 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2270 unsigned int regno = REGNO (SET_DEST (set));
2271 rtx src = SET_SRC (set);
2273 if (REG_NOTES (insn) != 0
2274 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2275 && REG_N_SETS (regno) == 1)
2276 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
2277 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2278 && ! rtx_varies_p (XEXP (note, 0), 1)
2279 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
2281 reg_known_value[regno] = XEXP (note, 0);
2282 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
2284 else if (REG_N_SETS (regno) == 1
2285 && GET_CODE (src) == PLUS
2286 && GET_CODE (XEXP (src, 0)) == REG
2287 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
2288 && (reg_known_value[REGNO (XEXP (src, 0))])
2289 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2291 rtx op0 = XEXP (src, 0);
2292 op0 = reg_known_value[REGNO (op0)];
2293 reg_known_value[regno]
2294 = plus_constant (op0, INTVAL (XEXP (src, 1)));
2295 reg_known_equiv_p[regno] = 0;
2297 else if (REG_N_SETS (regno) == 1
2298 && ! rtx_varies_p (src, 1))
2300 reg_known_value[regno] = src;
2301 reg_known_equiv_p[regno] = 0;
2305 else if (GET_CODE (insn) == NOTE
2306 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
2307 copying_arguments = 0;
2310 /* Now propagate values from new_reg_base_value to reg_base_value. */
2311 for (ui = 0; ui < reg_base_value_size; ui++)
2313 if (new_reg_base_value[ui]
2314 && new_reg_base_value[ui] != reg_base_value[ui]
2315 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
2317 reg_base_value[ui] = new_reg_base_value[ui];
2322 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2324 /* Fill in the remaining entries. */
2325 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
2326 if (reg_known_value[i] == 0)
2327 reg_known_value[i] = regno_reg_rtx[i];
2329 /* Simplify the reg_base_value array so that no register refers to
2330 another register, except to special registers indirectly through
2331 ADDRESS expressions.
2333 In theory this loop can take as long as O(registers^2), but unless
2334 there are very long dependency chains it will run in close to linear
2337 This loop may not be needed any longer now that the main loop does
2338 a better job at propagating alias information. */
2344 for (ui = 0; ui < reg_base_value_size; ui++)
2346 rtx base = reg_base_value[ui];
2347 if (base && GET_CODE (base) == REG)
2349 unsigned int base_regno = REGNO (base);
2350 if (base_regno == ui) /* register set from itself */
2351 reg_base_value[ui] = 0;
2353 reg_base_value[ui] = reg_base_value[base_regno];
2358 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
2361 free (new_reg_base_value);
2362 new_reg_base_value = 0;
2368 end_alias_analysis ()
2370 free (reg_known_value + FIRST_PSEUDO_REGISTER);
2371 reg_known_value = 0;
2372 reg_known_value_size = 0;
2373 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER);
2374 reg_known_equiv_p = 0;
2377 ggc_del_root (reg_base_value);
2378 free (reg_base_value);
2381 reg_base_value_size = 0;
2382 if (alias_invariant)
2384 free (alias_invariant);
2385 alias_invariant = 0;