1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
28 #include "insn-flags.h"
31 #include "hard-reg-set.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 to not alias each other. There is one
42 exception, however. 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.) If, when comparing
57 two alias sets, we can hold one set fixed, trace the other set
58 downwards, and at some point find the first set, the two MEMs can
59 alias one another. In this situation we say the alias set for
60 `struct S' is the `superset' and that those for `int' and `double'
63 Alias set zero is implicitly a superset of all other alias sets.
64 However, this is no actual entry for alias set zero. It is an
65 error to attempt to explicitly construct a subset of zero. */
67 typedef struct alias_set_entry
69 /* The alias set number, as stored in MEM_ALIAS_SET. */
72 /* The children of the alias set. These are not just the immediate
73 children, but, in fact, all children. So, if we have:
75 struct T { struct S s; float f; }
77 continuing our example above, the children here will be all of
78 `int', `double', `float', and `struct S'. */
82 static int rtx_equal_for_memref_p PARAMS ((rtx, rtx));
83 static rtx find_symbolic_term PARAMS ((rtx));
84 static rtx get_addr PARAMS ((rtx));
85 static int memrefs_conflict_p PARAMS ((int, rtx, int, rtx,
87 static void record_set PARAMS ((rtx, rtx, void *));
88 static rtx find_base_term PARAMS ((rtx));
89 static int base_alias_check PARAMS ((rtx, rtx, enum machine_mode,
91 static rtx find_base_value PARAMS ((rtx));
92 static int mems_in_disjoint_alias_sets_p PARAMS ((rtx, rtx));
93 static int insert_subset_children PARAMS ((splay_tree_node, void*));
94 static alias_set_entry get_alias_set_entry PARAMS ((int));
95 static rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx,
97 static int aliases_everything_p PARAMS ((rtx));
98 static int write_dependence_p PARAMS ((rtx, rtx, int));
99 static int nonlocal_reference_p PARAMS ((rtx));
101 /* Set up all info needed to perform alias analysis on memory references. */
103 /* Returns the size in bytes of the mode of X. */
104 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
106 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
107 different alias sets. We ignore alias sets in functions making use
108 of variable arguments because the va_arg macros on some systems are
110 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
111 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
113 /* Cap the number of passes we make over the insns propagating alias
114 information through set chains.
116 10 is a completely arbitrary choice. */
117 #define MAX_ALIAS_LOOP_PASSES 10
119 /* reg_base_value[N] gives an address to which register N is related.
120 If all sets after the first add or subtract to the current value
121 or otherwise modify it so it does not point to a different top level
122 object, reg_base_value[N] is equal to the address part of the source
125 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
126 expressions represent certain special values: function arguments and
127 the stack, frame, and argument pointers.
129 The contents of an ADDRESS is not normally used, the mode of the
130 ADDRESS determines whether the ADDRESS is a function argument or some
131 other special value. Pointer equality, not rtx_equal_p, determines whether
132 two ADDRESS expressions refer to the same base address.
134 The only use of the contents of an ADDRESS is for determining if the
135 current function performs nonlocal memory memory references for the
136 purposes of marking the function as a constant function. */
138 static rtx *reg_base_value;
139 static rtx *new_reg_base_value;
140 static unsigned int reg_base_value_size; /* size of reg_base_value array */
142 #define REG_BASE_VALUE(X) \
143 ((unsigned) REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
145 /* Vector of known invariant relationships between registers. Set in
146 loop unrolling. Indexed by register number, if nonzero the value
147 is an expression describing this register in terms of another.
149 The length of this array is REG_BASE_VALUE_SIZE.
151 Because this array contains only pseudo registers it has no effect
153 static rtx *alias_invariant;
155 /* Vector indexed by N giving the initial (unchanging) value known for
156 pseudo-register N. This array is initialized in
157 init_alias_analysis, and does not change until end_alias_analysis
159 rtx *reg_known_value;
161 /* Indicates number of valid entries in reg_known_value. */
162 static unsigned int reg_known_value_size;
164 /* Vector recording for each reg_known_value whether it is due to a
165 REG_EQUIV note. Future passes (viz., reload) may replace the
166 pseudo with the equivalent expression and so we account for the
167 dependences that would be introduced if that happens. */
168 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
169 assign_parms mention the arg pointer, and there are explicit insns in the
170 RTL that modify the arg pointer. Thus we must ensure that such insns don't
171 get scheduled across each other because that would invalidate the REG_EQUIV
172 notes. One could argue that the REG_EQUIV notes are wrong, but solving
173 the problem in the scheduler will likely give better code, so we do it
175 char *reg_known_equiv_p;
177 /* True when scanning insns from the start of the rtl to the
178 NOTE_INSN_FUNCTION_BEG note. */
180 static int copying_arguments;
182 /* The splay-tree used to store the various alias set entries. */
184 static splay_tree alias_sets;
186 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
187 such an entry, or NULL otherwise. */
189 static alias_set_entry
190 get_alias_set_entry (alias_set)
194 = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
196 return sn != 0 ? ((alias_set_entry) sn->value) : 0;
199 /* Returns nonzero value if the alias sets for MEM1 and MEM2 are such
200 that the two MEMs cannot alias each other. */
203 mems_in_disjoint_alias_sets_p (mem1, mem2)
209 #ifdef ENABLE_CHECKING
210 /* Perform a basic sanity check. Namely, that there are no alias sets
211 if we're not using strict aliasing. This helps to catch bugs
212 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
213 where a MEM is allocated in some way other than by the use of
214 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
215 use alias sets to indicate that spilled registers cannot alias each
216 other, we might need to remove this check. */
217 if (! flag_strict_aliasing
218 && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0))
222 /* The code used in varargs macros are often not conforming ANSI C,
223 which can trick the compiler into making incorrect aliasing
224 assumptions in these functions. So, we don't use alias sets in
225 such a function. FIXME: This should be moved into the front-end;
226 it is a language-dependent notion, and there's no reason not to
227 still use these checks to handle globals. */
228 if (current_function_stdarg || current_function_varargs)
231 /* If have no alias set information for one of the MEMs, we have to assume
232 it can alias anything. */
233 if (MEM_ALIAS_SET (mem1) == 0 || MEM_ALIAS_SET (mem2) == 0)
236 /* If the two alias sets are the same, they may alias. */
237 if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2))
240 /* Iterate through each of the children of the first alias set,
241 comparing it with the second alias set. */
242 ase = get_alias_set_entry (MEM_ALIAS_SET (mem1));
243 if (ase != 0 && splay_tree_lookup (ase->children,
244 (splay_tree_key) MEM_ALIAS_SET (mem2)))
247 /* Now do the same, but with the alias sets reversed. */
248 ase = get_alias_set_entry (MEM_ALIAS_SET (mem2));
249 if (ase != 0 && splay_tree_lookup (ase->children,
250 (splay_tree_key) MEM_ALIAS_SET (mem1)))
253 /* The two MEMs are in distinct alias sets, and neither one is the
254 child of the other. Therefore, they cannot alias. */
258 /* Insert the NODE into the splay tree given by DATA. Used by
259 record_alias_subset via splay_tree_foreach. */
262 insert_subset_children (node, data)
263 splay_tree_node node;
266 splay_tree_insert ((splay_tree) data, node->key, node->value);
271 /* Indicate that things in SUBSET can alias things in SUPERSET, but
272 not vice versa. For example, in C, a store to an `int' can alias a
273 structure containing an `int', but not vice versa. Here, the
274 structure would be the SUPERSET and `int' the SUBSET. This
275 function should be called only once per SUPERSET/SUBSET pair. At
276 present any given alias set may only be a subset of one superset.
278 It is illegal for SUPERSET to be zero; everything is implicitly a
279 subset of alias set zero. */
282 record_alias_subset (superset, subset)
286 alias_set_entry superset_entry;
287 alias_set_entry subset_entry;
292 superset_entry = get_alias_set_entry (superset);
293 if (superset_entry == 0)
295 /* Create an entry for the SUPERSET, so that we have a place to
296 attach the SUBSET. */
298 = (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
299 superset_entry->alias_set = superset;
300 superset_entry->children
301 = splay_tree_new (splay_tree_compare_ints, 0, 0);
302 splay_tree_insert (alias_sets, (splay_tree_key) superset,
303 (splay_tree_value) superset_entry);
307 subset_entry = get_alias_set_entry (subset);
309 /* If there is an entry for the subset, enter all of its children
310 (if they are not already present) as children of the SUPERSET. */
312 splay_tree_foreach (subset_entry->children,
313 insert_subset_children,
314 superset_entry->children);
316 /* Enter the SUBSET itself as a child of the SUPERSET. */
317 splay_tree_insert (superset_entry->children,
318 (splay_tree_key) subset, 0);
321 /* Inside SRC, the source of a SET, find a base address. */
324 find_base_value (src)
327 switch (GET_CODE (src))
334 /* At the start of a function, argument registers have known base
335 values which may be lost later. Returning an ADDRESS
336 expression here allows optimization based on argument values
337 even when the argument registers are used for other purposes. */
338 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
339 return new_reg_base_value[REGNO (src)];
341 /* If a pseudo has a known base value, return it. Do not do this
342 for hard regs since it can result in a circular dependency
343 chain for registers which have values at function entry.
345 The test above is not sufficient because the scheduler may move
346 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
347 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
348 && (unsigned) REGNO (src) < reg_base_value_size
349 && reg_base_value[REGNO (src)])
350 return reg_base_value[REGNO (src)];
355 /* Check for an argument passed in memory. Only record in the
356 copying-arguments block; it is too hard to track changes
358 if (copying_arguments
359 && (XEXP (src, 0) == arg_pointer_rtx
360 || (GET_CODE (XEXP (src, 0)) == PLUS
361 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
362 return gen_rtx_ADDRESS (VOIDmode, src);
367 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
370 /* ... fall through ... */
375 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
377 /* If either operand is a REG, then see if we already have
378 a known value for it. */
379 if (GET_CODE (src_0) == REG)
381 temp = find_base_value (src_0);
386 if (GET_CODE (src_1) == REG)
388 temp = find_base_value (src_1);
393 /* Guess which operand is the base address:
394 If either operand is a symbol, then it is the base. If
395 either operand is a CONST_INT, then the other is the base. */
396 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
397 return find_base_value (src_0);
398 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
399 return find_base_value (src_1);
401 /* This might not be necessary anymore:
402 If either operand is a REG that is a known pointer, then it
404 else if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
405 return find_base_value (src_0);
406 else if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
407 return find_base_value (src_1);
413 /* The standard form is (lo_sum reg sym) so look only at the
415 return find_base_value (XEXP (src, 1));
418 /* If the second operand is constant set the base
419 address to the first operand. */
420 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
421 return find_base_value (XEXP (src, 0));
425 case SIGN_EXTEND: /* used for NT/Alpha pointers */
427 return find_base_value (XEXP (src, 0));
436 /* Called from init_alias_analysis indirectly through note_stores. */
438 /* While scanning insns to find base values, reg_seen[N] is nonzero if
439 register N has been set in this function. */
440 static char *reg_seen;
442 /* Addresses which are known not to alias anything else are identified
443 by a unique integer. */
444 static int unique_id;
447 record_set (dest, set, data)
449 void *data ATTRIBUTE_UNUSED;
451 register unsigned regno;
454 if (GET_CODE (dest) != REG)
457 regno = REGNO (dest);
459 if (regno >= reg_base_value_size)
464 /* A CLOBBER wipes out any old value but does not prevent a previously
465 unset register from acquiring a base address (i.e. reg_seen is not
467 if (GET_CODE (set) == CLOBBER)
469 new_reg_base_value[regno] = 0;
478 new_reg_base_value[regno] = 0;
482 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
483 GEN_INT (unique_id++));
487 /* This is not the first set. If the new value is not related to the
488 old value, forget the base value. Note that the following code is
490 extern int x, y; int *p = &x; p += (&y-&x);
491 ANSI C does not allow computing the difference of addresses
492 of distinct top level objects. */
493 if (new_reg_base_value[regno])
494 switch (GET_CODE (src))
499 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
500 new_reg_base_value[regno] = 0;
503 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
504 new_reg_base_value[regno] = 0;
507 new_reg_base_value[regno] = 0;
510 /* If this is the first set of a register, record the value. */
511 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
512 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
513 new_reg_base_value[regno] = find_base_value (src);
518 /* Called from loop optimization when a new pseudo-register is created. */
521 record_base_value (regno, val, invariant)
526 if ((unsigned) regno >= reg_base_value_size)
529 /* If INVARIANT is true then this value also describes an invariant
530 relationship which can be used to deduce that two registers with
531 unknown values are different. */
532 if (invariant && alias_invariant)
533 alias_invariant[regno] = val;
535 if (GET_CODE (val) == REG)
537 if ((unsigned) REGNO (val) < reg_base_value_size)
538 reg_base_value[regno] = reg_base_value[REGNO (val)];
543 reg_base_value[regno] = find_base_value (val);
546 /* Returns a canonical version of X, from the point of view alias
547 analysis. (For example, if X is a MEM whose address is a register,
548 and the register has a known value (say a SYMBOL_REF), then a MEM
549 whose address is the SYMBOL_REF is returned.) */
555 /* Recursively look for equivalences. */
556 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
557 && REGNO (x) < reg_known_value_size)
558 return reg_known_value[REGNO (x)] == x
559 ? x : canon_rtx (reg_known_value[REGNO (x)]);
560 else if (GET_CODE (x) == PLUS)
562 rtx x0 = canon_rtx (XEXP (x, 0));
563 rtx x1 = canon_rtx (XEXP (x, 1));
565 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
567 /* We can tolerate LO_SUMs being offset here; these
568 rtl are used for nothing other than comparisons. */
569 if (GET_CODE (x0) == CONST_INT)
570 return plus_constant_for_output (x1, INTVAL (x0));
571 else if (GET_CODE (x1) == CONST_INT)
572 return plus_constant_for_output (x0, INTVAL (x1));
573 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
577 /* This gives us much better alias analysis when called from
578 the loop optimizer. Note we want to leave the original
579 MEM alone, but need to return the canonicalized MEM with
580 all the flags with their original values. */
581 else if (GET_CODE (x) == MEM)
583 rtx addr = canon_rtx (XEXP (x, 0));
585 if (addr != XEXP (x, 0))
587 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
589 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
590 MEM_COPY_ATTRIBUTES (new, x);
591 MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
598 /* Return 1 if X and Y are identical-looking rtx's.
600 We use the data in reg_known_value above to see if two registers with
601 different numbers are, in fact, equivalent. */
604 rtx_equal_for_memref_p (x, y)
609 register enum rtx_code code;
610 register const char *fmt;
612 if (x == 0 && y == 0)
614 if (x == 0 || y == 0)
624 /* Rtx's of different codes cannot be equal. */
625 if (code != GET_CODE (y))
628 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
629 (REG:SI x) and (REG:HI x) are NOT equivalent. */
631 if (GET_MODE (x) != GET_MODE (y))
634 /* Some RTL can be compared without a recursive examination. */
638 return REGNO (x) == REGNO (y);
641 return XEXP (x, 0) == XEXP (y, 0);
644 return XSTR (x, 0) == XSTR (y, 0);
648 /* There's no need to compare the contents of CONST_DOUBLEs or
649 CONST_INTs because pointer equality is a good enough
650 comparison for these nodes. */
654 return (REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0))
655 && XINT (x, 1) == XINT (y, 1));
661 /* For commutative operations, the RTX match if the operand match in any
662 order. Also handle the simple binary and unary cases without a loop. */
663 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
664 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
665 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
666 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
667 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
668 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
669 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
670 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
671 else if (GET_RTX_CLASS (code) == '1')
672 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
674 /* Compare the elements. If any pair of corresponding elements
675 fail to match, return 0 for the whole things.
677 Limit cases to types which actually appear in addresses. */
679 fmt = GET_RTX_FORMAT (code);
680 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
685 if (XINT (x, i) != XINT (y, i))
690 /* Two vectors must have the same length. */
691 if (XVECLEN (x, i) != XVECLEN (y, i))
694 /* And the corresponding elements must match. */
695 for (j = 0; j < XVECLEN (x, i); j++)
696 if (rtx_equal_for_memref_p (XVECEXP (x, i, j),
697 XVECEXP (y, i, j)) == 0)
702 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
706 /* This can happen for an asm which clobbers memory. */
710 /* It is believed that rtx's at this level will never
711 contain anything but integers and other rtx's,
712 except for within LABEL_REFs and SYMBOL_REFs. */
720 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
721 X and return it, or return 0 if none found. */
724 find_symbolic_term (x)
728 register enum rtx_code code;
729 register const char *fmt;
732 if (code == SYMBOL_REF || code == LABEL_REF)
734 if (GET_RTX_CLASS (code) == 'o')
737 fmt = GET_RTX_FORMAT (code);
738 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
744 t = find_symbolic_term (XEXP (x, i));
748 else if (fmt[i] == 'E')
759 struct elt_loc_list *l;
761 switch (GET_CODE (x))
764 return REG_BASE_VALUE (x);
767 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
773 return find_base_term (XEXP (x, 0));
776 val = CSELIB_VAL_PTR (x);
777 for (l = val->locs; l; l = l->next)
778 if ((x = find_base_term (l->loc)) != 0)
784 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
791 rtx tmp1 = XEXP (x, 0);
792 rtx tmp2 = XEXP (x, 1);
794 /* This is a litle bit tricky since we have to determine which of
795 the two operands represents the real base address. Otherwise this
796 routine may return the index register instead of the base register.
798 That may cause us to believe no aliasing was possible, when in
799 fact aliasing is possible.
801 We use a few simple tests to guess the base register. Additional
802 tests can certainly be added. For example, if one of the operands
803 is a shift or multiply, then it must be the index register and the
804 other operand is the base register. */
806 /* If either operand is known to be a pointer, then use it
807 to determine the base term. */
808 if (REG_P (tmp1) && REGNO_POINTER_FLAG (REGNO (tmp1)))
809 return find_base_term (tmp1);
811 if (REG_P (tmp2) && REGNO_POINTER_FLAG (REGNO (tmp2)))
812 return find_base_term (tmp2);
814 /* Neither operand was known to be a pointer. Go ahead and find the
815 base term for both operands. */
816 tmp1 = find_base_term (tmp1);
817 tmp2 = find_base_term (tmp2);
819 /* If either base term is named object or a special address
820 (like an argument or stack reference), then use it for the
823 && (GET_CODE (tmp1) == SYMBOL_REF
824 || GET_CODE (tmp1) == LABEL_REF
825 || (GET_CODE (tmp1) == ADDRESS
826 && GET_MODE (tmp1) != VOIDmode)))
830 && (GET_CODE (tmp2) == SYMBOL_REF
831 || GET_CODE (tmp2) == LABEL_REF
832 || (GET_CODE (tmp2) == ADDRESS
833 && GET_MODE (tmp2) != VOIDmode)))
836 /* We could not determine which of the two operands was the
837 base register and which was the index. So we can determine
838 nothing from the base alias check. */
843 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
844 return REG_BASE_VALUE (XEXP (x, 0));
856 /* Return 0 if the addresses X and Y are known to point to different
857 objects, 1 if they might be pointers to the same object. */
860 base_alias_check (x, y, x_mode, y_mode)
862 enum machine_mode x_mode, y_mode;
864 rtx x_base = find_base_term (x);
865 rtx y_base = find_base_term (y);
867 /* If the address itself has no known base see if a known equivalent
868 value has one. If either address still has no known base, nothing
869 is known about aliasing. */
874 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
877 x_base = find_base_term (x_c);
885 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
888 y_base = find_base_term (y_c);
893 /* If the base addresses are equal nothing is known about aliasing. */
894 if (rtx_equal_p (x_base, y_base))
897 /* The base addresses of the read and write are different expressions.
898 If they are both symbols and they are not accessed via AND, there is
899 no conflict. We can bring knowledge of object alignment into play
900 here. For example, on alpha, "char a, b;" can alias one another,
901 though "char a; long b;" cannot. */
902 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
904 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
906 if (GET_CODE (x) == AND
907 && (GET_CODE (XEXP (x, 1)) != CONST_INT
908 || GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
910 if (GET_CODE (y) == AND
911 && (GET_CODE (XEXP (y, 1)) != CONST_INT
912 || GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
914 /* Differing symbols never alias. */
918 /* If one address is a stack reference there can be no alias:
919 stack references using different base registers do not alias,
920 a stack reference can not alias a parameter, and a stack reference
921 can not alias a global. */
922 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
923 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
926 if (! flag_argument_noalias)
929 if (flag_argument_noalias > 1)
932 /* Weak noalias assertion (arguments are distinct, but may match globals). */
933 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
936 /* Convert the address X into something we can use. This is done by returning
937 it unchanged unless it is a value; in the latter case we call cselib to get
938 a more useful rtx. */
944 struct elt_loc_list *l;
946 if (GET_CODE (x) != VALUE)
948 v = CSELIB_VAL_PTR (x);
949 for (l = v->locs; l; l = l->next)
950 if (CONSTANT_P (l->loc))
952 for (l = v->locs; l; l = l->next)
953 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
960 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
961 where SIZE is the size in bytes of the memory reference. If ADDR
962 is not modified by the memory reference then ADDR is returned. */
965 addr_side_effect_eval (addr, size, n_refs)
972 switch (GET_CODE (addr))
975 offset = (n_refs + 1) * size;
978 offset = -(n_refs + 1) * size;
981 offset = n_refs * size;
984 offset = -n_refs * size;
992 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset));
994 addr = XEXP (addr, 0);
999 /* Return nonzero if X and Y (memory addresses) could reference the
1000 same location in memory. C is an offset accumulator. When
1001 C is nonzero, we are testing aliases between X and Y + C.
1002 XSIZE is the size in bytes of the X reference,
1003 similarly YSIZE is the size in bytes for Y.
1005 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1006 referenced (the reference was BLKmode), so make the most pessimistic
1009 If XSIZE or YSIZE is negative, we may access memory outside the object
1010 being referenced as a side effect. This can happen when using AND to
1011 align memory references, as is done on the Alpha.
1013 Nice to notice that varying addresses cannot conflict with fp if no
1014 local variables had their addresses taken, but that's too hard now. */
1017 memrefs_conflict_p (xsize, x, ysize, y, c)
1022 if (GET_CODE (x) == VALUE)
1024 if (GET_CODE (y) == VALUE)
1026 if (GET_CODE (x) == HIGH)
1028 else if (GET_CODE (x) == LO_SUM)
1031 x = canon_rtx (addr_side_effect_eval (x, xsize, 0));
1032 if (GET_CODE (y) == HIGH)
1034 else if (GET_CODE (y) == LO_SUM)
1037 y = canon_rtx (addr_side_effect_eval (y, ysize, 0));
1039 if (rtx_equal_for_memref_p (x, y))
1041 if (xsize <= 0 || ysize <= 0)
1043 if (c >= 0 && xsize > c)
1045 if (c < 0 && ysize+c > 0)
1050 /* This code used to check for conflicts involving stack references and
1051 globals but the base address alias code now handles these cases. */
1053 if (GET_CODE (x) == PLUS)
1055 /* The fact that X is canonicalized means that this
1056 PLUS rtx is canonicalized. */
1057 rtx x0 = XEXP (x, 0);
1058 rtx x1 = XEXP (x, 1);
1060 if (GET_CODE (y) == PLUS)
1062 /* The fact that Y is canonicalized means that this
1063 PLUS rtx is canonicalized. */
1064 rtx y0 = XEXP (y, 0);
1065 rtx y1 = XEXP (y, 1);
1067 if (rtx_equal_for_memref_p (x1, y1))
1068 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1069 if (rtx_equal_for_memref_p (x0, y0))
1070 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1071 if (GET_CODE (x1) == CONST_INT)
1073 if (GET_CODE (y1) == CONST_INT)
1074 return memrefs_conflict_p (xsize, x0, ysize, y0,
1075 c - INTVAL (x1) + INTVAL (y1));
1077 return memrefs_conflict_p (xsize, x0, ysize, y,
1080 else if (GET_CODE (y1) == CONST_INT)
1081 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1085 else if (GET_CODE (x1) == CONST_INT)
1086 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1088 else if (GET_CODE (y) == PLUS)
1090 /* The fact that Y is canonicalized means that this
1091 PLUS rtx is canonicalized. */
1092 rtx y0 = XEXP (y, 0);
1093 rtx y1 = XEXP (y, 1);
1095 if (GET_CODE (y1) == CONST_INT)
1096 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1101 if (GET_CODE (x) == GET_CODE (y))
1102 switch (GET_CODE (x))
1106 /* Handle cases where we expect the second operands to be the
1107 same, and check only whether the first operand would conflict
1110 rtx x1 = canon_rtx (XEXP (x, 1));
1111 rtx y1 = canon_rtx (XEXP (y, 1));
1112 if (! rtx_equal_for_memref_p (x1, y1))
1114 x0 = canon_rtx (XEXP (x, 0));
1115 y0 = canon_rtx (XEXP (y, 0));
1116 if (rtx_equal_for_memref_p (x0, y0))
1117 return (xsize == 0 || ysize == 0
1118 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1120 /* Can't properly adjust our sizes. */
1121 if (GET_CODE (x1) != CONST_INT)
1123 xsize /= INTVAL (x1);
1124 ysize /= INTVAL (x1);
1126 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1130 /* Are these registers known not to be equal? */
1131 if (alias_invariant)
1133 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1134 rtx i_x, i_y; /* invariant relationships of X and Y */
1136 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1137 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1139 if (i_x == 0 && i_y == 0)
1142 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1143 ysize, i_y ? i_y : y, c))
1152 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1153 as an access with indeterminate size. Assume that references
1154 besides AND are aligned, so if the size of the other reference is
1155 at least as large as the alignment, assume no other overlap. */
1156 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1158 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1160 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c);
1162 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1164 /* ??? If we are indexing far enough into the array/structure, we
1165 may yet be able to determine that we can not overlap. But we
1166 also need to that we are far enough from the end not to overlap
1167 a following reference, so we do nothing with that for now. */
1168 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1170 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c);
1175 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1177 c += (INTVAL (y) - INTVAL (x));
1178 return (xsize <= 0 || ysize <= 0
1179 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1182 if (GET_CODE (x) == CONST)
1184 if (GET_CODE (y) == CONST)
1185 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1186 ysize, canon_rtx (XEXP (y, 0)), c);
1188 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1191 if (GET_CODE (y) == CONST)
1192 return memrefs_conflict_p (xsize, x, ysize,
1193 canon_rtx (XEXP (y, 0)), c);
1196 return (xsize < 0 || ysize < 0
1197 || (rtx_equal_for_memref_p (x, y)
1198 && (xsize == 0 || ysize == 0
1199 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1206 /* Functions to compute memory dependencies.
1208 Since we process the insns in execution order, we can build tables
1209 to keep track of what registers are fixed (and not aliased), what registers
1210 are varying in known ways, and what registers are varying in unknown
1213 If both memory references are volatile, then there must always be a
1214 dependence between the two references, since their order can not be
1215 changed. A volatile and non-volatile reference can be interchanged
1218 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
1219 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
1220 allow QImode aliasing because the ANSI C standard allows character
1221 pointers to alias anything. We are assuming that characters are
1222 always QImode here. We also must allow AND addresses, because they may
1223 generate accesses outside the object being referenced. This is used to
1224 generate aligned addresses from unaligned addresses, for instance, the
1225 alpha storeqi_unaligned pattern. */
1227 /* Read dependence: X is read after read in MEM takes place. There can
1228 only be a dependence here if both reads are volatile. */
1231 read_dependence (mem, x)
1235 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1238 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1239 MEM2 is a reference to a structure at a varying address, or returns
1240 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1241 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1242 to decide whether or not an address may vary; it should return
1243 nonzero whenever variation is possible.
1244 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1247 fixed_scalar_and_varying_struct_p (mem1, mem2, mem1_addr, mem2_addr, varies_p)
1249 rtx mem1_addr, mem2_addr;
1250 int (*varies_p) PARAMS ((rtx));
1252 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1253 && !varies_p (mem1_addr) && varies_p (mem2_addr))
1254 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1258 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1259 && varies_p (mem1_addr) && !varies_p (mem2_addr))
1260 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1267 /* Returns nonzero if something about the mode or address format MEM1
1268 indicates that it might well alias *anything*. */
1271 aliases_everything_p (mem)
1274 if (GET_MODE (mem) == QImode)
1275 /* ANSI C says that a `char*' can point to anything. */
1278 if (GET_CODE (XEXP (mem, 0)) == AND)
1279 /* If the address is an AND, its very hard to know at what it is
1280 actually pointing. */
1286 /* True dependence: X is read after store in MEM takes place. */
1289 true_dependence (mem, mem_mode, x, varies)
1291 enum machine_mode mem_mode;
1293 int (*varies) PARAMS ((rtx));
1295 register rtx x_addr, mem_addr;
1297 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1300 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1303 /* If X is an unchanging read, then it can't possibly conflict with any
1304 non-unchanging store. It may conflict with an unchanging write though,
1305 because there may be a single store to this address to initialize it.
1306 Just fall through to the code below to resolve the case where we have
1307 both an unchanging read and an unchanging write. This won't handle all
1308 cases optimally, but the possible performance loss should be
1310 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
1313 if (mem_mode == VOIDmode)
1314 mem_mode = GET_MODE (mem);
1316 x_addr = get_addr (XEXP (x, 0));
1317 mem_addr = get_addr (XEXP (mem, 0));
1319 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
1322 x_addr = canon_rtx (x_addr);
1323 mem_addr = canon_rtx (mem_addr);
1325 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
1326 SIZE_FOR_MODE (x), x_addr, 0))
1329 if (aliases_everything_p (x))
1332 /* We cannot use aliases_everyting_p to test MEM, since we must look
1333 at MEM_MODE, rather than GET_MODE (MEM). */
1334 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
1337 /* In true_dependence we also allow BLKmode to alias anything. Why
1338 don't we do this in anti_dependence and output_dependence? */
1339 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
1342 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
1346 /* Returns non-zero if a write to X might alias a previous read from
1347 (or, if WRITEP is non-zero, a write to) MEM. */
1350 write_dependence_p (mem, x, writep)
1355 rtx x_addr, mem_addr;
1358 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1361 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1364 /* If MEM is an unchanging read, then it can't possibly conflict with
1365 the store to X, because there is at most one store to MEM, and it must
1366 have occurred somewhere before MEM. */
1367 if (!writep && RTX_UNCHANGING_P (mem))
1370 x_addr = get_addr (XEXP (x, 0));
1371 mem_addr = get_addr (XEXP (mem, 0));
1373 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
1377 x_addr = canon_rtx (x_addr);
1378 mem_addr = canon_rtx (mem_addr);
1380 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
1381 SIZE_FOR_MODE (x), x_addr, 0))
1385 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
1388 return (!(fixed_scalar == mem && !aliases_everything_p (x))
1389 && !(fixed_scalar == x && !aliases_everything_p (mem)));
1392 /* Anti dependence: X is written after read in MEM takes place. */
1395 anti_dependence (mem, x)
1399 return write_dependence_p (mem, x, /*writep=*/0);
1402 /* Output dependence: X is written after store in MEM takes place. */
1405 output_dependence (mem, x)
1409 return write_dependence_p (mem, x, /*writep=*/1);
1412 /* Returns non-zero if X might refer to something which is not
1413 local to the function and is not constant. */
1416 nonlocal_reference_p (x)
1420 register RTX_CODE code;
1423 code = GET_CODE (x);
1425 if (GET_RTX_CLASS (code) == 'i')
1427 /* Constant functions can be constant if they don't use
1428 scratch memory used to mark function w/o side effects. */
1429 if (code == CALL_INSN && CONST_CALL_P (x))
1431 x = CALL_INSN_FUNCTION_USAGE (x);
1436 code = GET_CODE (x);
1442 if (GET_CODE (SUBREG_REG (x)) == REG)
1444 /* Global registers are not local. */
1445 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
1446 && global_regs[REGNO (SUBREG_REG (x)) + SUBREG_WORD (x)])
1454 /* Global registers are not local. */
1455 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1469 /* Constants in the function's constants pool are constant. */
1470 if (CONSTANT_POOL_ADDRESS_P (x))
1475 /* Recursion introduces no additional considerations. */
1476 if (GET_CODE (XEXP (x, 0)) == MEM
1477 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
1478 && strcmp(XSTR (XEXP (XEXP (x, 0), 0), 0),
1479 IDENTIFIER_POINTER (
1480 DECL_ASSEMBLER_NAME (current_function_decl))) == 0)
1485 /* Be overly conservative and consider any volatile memory
1486 reference as not local. */
1487 if (MEM_VOLATILE_P (x))
1489 base = find_base_term (XEXP (x, 0));
1492 /* A Pmode ADDRESS could be a reference via the structure value
1493 address or static chain. Such memory references are nonlocal.
1495 Thus, we have to examine the contents of the ADDRESS to find
1496 out if this is a local reference or not. */
1497 if (GET_CODE (base) == ADDRESS
1498 && GET_MODE (base) == Pmode
1499 && (XEXP (base, 0) == stack_pointer_rtx
1500 || XEXP (base, 0) == arg_pointer_rtx
1501 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1502 || XEXP (base, 0) == hard_frame_pointer_rtx
1504 || XEXP (base, 0) == frame_pointer_rtx))
1506 /* Constants in the function's constant pool are constant. */
1507 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
1520 /* Recursively scan the operands of this expression. */
1523 register const char *fmt = GET_RTX_FORMAT (code);
1526 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1528 if (fmt[i] == 'e' && XEXP (x, i))
1530 if (nonlocal_reference_p (XEXP (x, i)))
1533 else if (fmt[i] == 'E')
1536 for (j = 0; j < XVECLEN (x, i); j++)
1537 if (nonlocal_reference_p (XVECEXP (x, i, j)))
1546 /* Mark the function if it is constant. */
1549 mark_constant_function ()
1553 if (TREE_PUBLIC (current_function_decl)
1554 || TREE_READONLY (current_function_decl)
1555 || TREE_THIS_VOLATILE (current_function_decl)
1556 || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode)
1559 /* Determine if this is a constant function. */
1561 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1562 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
1563 && nonlocal_reference_p (insn))
1566 /* Mark the function. */
1568 TREE_READONLY (current_function_decl) = 1;
1572 static HARD_REG_SET argument_registers;
1579 #ifndef OUTGOING_REGNO
1580 #define OUTGOING_REGNO(N) N
1582 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1583 /* Check whether this register can hold an incoming pointer
1584 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1585 numbers, so translate if necessary due to register windows. */
1586 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1587 && HARD_REGNO_MODE_OK (i, Pmode))
1588 SET_HARD_REG_BIT (argument_registers, i);
1590 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
1593 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
1597 init_alias_analysis ()
1599 int maxreg = max_reg_num ();
1602 register unsigned int ui;
1605 reg_known_value_size = maxreg;
1608 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx))
1609 - FIRST_PSEUDO_REGISTER;
1611 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char))
1612 - FIRST_PSEUDO_REGISTER;
1614 /* Overallocate reg_base_value to allow some growth during loop
1615 optimization. Loop unrolling can create a large number of
1617 reg_base_value_size = maxreg * 2;
1618 reg_base_value = (rtx *) xcalloc (reg_base_value_size, sizeof (rtx));
1620 ggc_add_rtx_root (reg_base_value, reg_base_value_size);
1622 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx));
1623 reg_seen = (char *) xmalloc (reg_base_value_size);
1624 if (! reload_completed && flag_unroll_loops)
1626 /* ??? Why are we realloc'ing if we're just going to zero it? */
1627 alias_invariant = (rtx *)xrealloc (alias_invariant,
1628 reg_base_value_size * sizeof (rtx));
1629 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1633 /* The basic idea is that each pass through this loop will use the
1634 "constant" information from the previous pass to propagate alias
1635 information through another level of assignments.
1637 This could get expensive if the assignment chains are long. Maybe
1638 we should throttle the number of iterations, possibly based on
1639 the optimization level or flag_expensive_optimizations.
1641 We could propagate more information in the first pass by making use
1642 of REG_N_SETS to determine immediately that the alias information
1643 for a pseudo is "constant".
1645 A program with an uninitialized variable can cause an infinite loop
1646 here. Instead of doing a full dataflow analysis to detect such problems
1647 we just cap the number of iterations for the loop.
1649 The state of the arrays for the set chain in question does not matter
1650 since the program has undefined behavior. */
1655 /* Assume nothing will change this iteration of the loop. */
1658 /* We want to assign the same IDs each iteration of this loop, so
1659 start counting from zero each iteration of the loop. */
1662 /* We're at the start of the funtion each iteration through the
1663 loop, so we're copying arguments. */
1664 copying_arguments = 1;
1666 /* Wipe the potential alias information clean for this pass. */
1667 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1669 /* Wipe the reg_seen array clean. */
1670 bzero ((char *) reg_seen, reg_base_value_size);
1672 /* Mark all hard registers which may contain an address.
1673 The stack, frame and argument pointers may contain an address.
1674 An argument register which can hold a Pmode value may contain
1675 an address even if it is not in BASE_REGS.
1677 The address expression is VOIDmode for an argument and
1678 Pmode for other registers. */
1680 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1681 if (TEST_HARD_REG_BIT (argument_registers, i))
1682 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1683 gen_rtx_REG (Pmode, i));
1685 new_reg_base_value[STACK_POINTER_REGNUM]
1686 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1687 new_reg_base_value[ARG_POINTER_REGNUM]
1688 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1689 new_reg_base_value[FRAME_POINTER_REGNUM]
1690 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1691 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1692 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1693 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1695 if (struct_value_incoming_rtx
1696 && GET_CODE (struct_value_incoming_rtx) == REG)
1697 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1698 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1700 if (static_chain_rtx
1701 && GET_CODE (static_chain_rtx) == REG)
1702 new_reg_base_value[REGNO (static_chain_rtx)]
1703 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1705 /* Walk the insns adding values to the new_reg_base_value array. */
1706 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1708 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
1709 if (prologue_epilogue_contains (insn))
1712 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1715 /* If this insn has a noalias note, process it, Otherwise,
1716 scan for sets. A simple set will have no side effects
1717 which could change the base value of any other register. */
1719 if (GET_CODE (PATTERN (insn)) == SET
1720 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1721 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
1723 note_stores (PATTERN (insn), record_set, NULL);
1725 set = single_set (insn);
1728 && GET_CODE (SET_DEST (set)) == REG
1729 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1730 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1731 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1732 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1733 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
1734 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
1736 int regno = REGNO (SET_DEST (set));
1737 reg_known_value[regno] = XEXP (note, 0);
1738 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1741 else if (GET_CODE (insn) == NOTE
1742 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1743 copying_arguments = 0;
1746 /* Now propagate values from new_reg_base_value to reg_base_value. */
1747 for (ui = 0; ui < reg_base_value_size; ui++)
1749 if (new_reg_base_value[ui]
1750 && new_reg_base_value[ui] != reg_base_value[ui]
1751 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
1753 reg_base_value[ui] = new_reg_base_value[ui];
1758 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1760 /* Fill in the remaining entries. */
1761 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1762 if (reg_known_value[i] == 0)
1763 reg_known_value[i] = regno_reg_rtx[i];
1765 /* Simplify the reg_base_value array so that no register refers to
1766 another register, except to special registers indirectly through
1767 ADDRESS expressions.
1769 In theory this loop can take as long as O(registers^2), but unless
1770 there are very long dependency chains it will run in close to linear
1773 This loop may not be needed any longer now that the main loop does
1774 a better job at propagating alias information. */
1780 for (ui = 0; ui < reg_base_value_size; ui++)
1782 rtx base = reg_base_value[ui];
1783 if (base && GET_CODE (base) == REG)
1785 unsigned int base_regno = REGNO (base);
1786 if (base_regno == ui) /* register set from itself */
1787 reg_base_value[ui] = 0;
1789 reg_base_value[ui] = reg_base_value[base_regno];
1794 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1797 free (new_reg_base_value);
1798 new_reg_base_value = 0;
1804 end_alias_analysis ()
1806 free (reg_known_value + FIRST_PSEUDO_REGISTER);
1807 reg_known_value = 0;
1808 reg_known_value_size = 0;
1809 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER);
1810 reg_known_equiv_p = 0;
1814 ggc_del_root (reg_base_value);
1815 free (reg_base_value);
1818 reg_base_value_size = 0;
1819 if (alias_invariant)
1821 free (alias_invariant);
1822 alias_invariant = 0;