1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999 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. */
27 #include "hard-reg-set.h"
31 #include "splay-tree.h"
33 /* The alias sets assigned to MEMs assist the back-end in determining
34 which MEMs can alias which other MEMs. In general, two MEMs in
35 different alias sets to not alias each other. There is one
36 exception, however. Consider something like:
38 struct S {int i; double d; };
40 a store to an `S' can alias something of either type `int' or type
41 `double'. (However, a store to an `int' cannot alias a `double'
42 and vice versa.) We indicate this via a tree structure that looks
50 (The arrows are directed and point downwards.) If, when comparing
51 two alias sets, we can hold one set fixed, and trace the other set
52 downwards, and at some point find the first set, the two MEMs can
53 alias one another. In this situation we say the alias set for
54 `struct S' is the `superset' and that those for `int' and `double'
57 Alias set zero is implicitly a superset of all other alias sets.
58 However, this is no actual entry for alias set zero. It is an
59 error to attempt to explicitly construct a subset of zero. */
61 typedef struct alias_set_entry {
62 /* The alias set number, as stored in MEM_ALIAS_SET. */
65 /* The children of the alias set. These are not just the immediate
66 children, but, in fact, all children. So, if we have:
68 struct T { struct S s; float f; }
70 continuing our example above, the children here will be all of
71 `int', `double', `float', and `struct S'. */
75 static rtx canon_rtx PROTO((rtx));
76 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
77 static rtx find_symbolic_term PROTO((rtx));
78 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
80 static void record_set PROTO((rtx, rtx));
81 static rtx find_base_term PROTO((rtx));
82 static int base_alias_check PROTO((rtx, rtx, enum machine_mode,
84 static rtx find_base_value PROTO((rtx));
85 static int mems_in_disjoint_alias_sets_p PROTO((rtx, rtx));
86 static int insert_subset_children PROTO((splay_tree_node,
88 static alias_set_entry get_alias_set_entry PROTO((int));
89 static rtx fixed_scalar_and_varying_struct_p PROTO((rtx, rtx, int (*)(rtx)));
90 static int aliases_everything_p PROTO((rtx));
91 static int write_dependence_p PROTO((rtx, rtx, int));
93 /* Set up all info needed to perform alias analysis on memory references. */
95 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
97 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
98 different alias sets. We ignore alias sets in functions making use
99 of variable arguments because the va_arg macros on some systems are
101 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
102 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
104 /* Cap the number of passes we make over the insns propagating alias
105 information through set chains.
107 10 is a completely arbitrary choice. */
108 #define MAX_ALIAS_LOOP_PASSES 10
110 /* reg_base_value[N] gives an address to which register N is related.
111 If all sets after the first add or subtract to the current value
112 or otherwise modify it so it does not point to a different top level
113 object, reg_base_value[N] is equal to the address part of the source
116 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
117 expressions represent certain special values: function arguments and
118 the stack, frame, and argument pointers. The contents of an address
119 expression are not used (but they are descriptive for debugging);
120 only the address and mode matter. Pointer equality, not rtx_equal_p,
121 determines whether two ADDRESS expressions refer to the same base
122 address. The mode determines whether it is a function argument or
123 other special value. */
126 rtx *new_reg_base_value;
127 unsigned int reg_base_value_size; /* size of reg_base_value array */
128 #define REG_BASE_VALUE(X) \
129 ((unsigned) REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
131 /* Vector of known invariant relationships between registers. Set in
132 loop unrolling. Indexed by register number, if nonzero the value
133 is an expression describing this register in terms of another.
135 The length of this array is REG_BASE_VALUE_SIZE.
137 Because this array contains only pseudo registers it has no effect
139 static rtx *alias_invariant;
141 /* Vector indexed by N giving the initial (unchanging) value known
142 for pseudo-register N. */
143 rtx *reg_known_value;
145 /* Indicates number of valid entries in reg_known_value. */
146 static int reg_known_value_size;
148 /* Vector recording for each reg_known_value whether it is due to a
149 REG_EQUIV note. Future passes (viz., reload) may replace the
150 pseudo with the equivalent expression and so we account for the
151 dependences that would be introduced if that happens. */
152 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
153 assign_parms mention the arg pointer, and there are explicit insns in the
154 RTL that modify the arg pointer. Thus we must ensure that such insns don't
155 get scheduled across each other because that would invalidate the REG_EQUIV
156 notes. One could argue that the REG_EQUIV notes are wrong, but solving
157 the problem in the scheduler will likely give better code, so we do it
159 char *reg_known_equiv_p;
161 /* True when scanning insns from the start of the rtl to the
162 NOTE_INSN_FUNCTION_BEG note. */
164 static int copying_arguments;
166 /* The splay-tree used to store the various alias set entries. */
168 static splay_tree alias_sets;
170 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
171 such an entry, or NULL otherwise. */
173 static alias_set_entry
174 get_alias_set_entry (alias_set)
178 splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
180 return sn ? ((alias_set_entry) sn->value) : ((alias_set_entry) 0);
183 /* Returns nonzero value if the alias sets for MEM1 and MEM2 are such
184 that the two MEMs cannot alias each other. */
187 mems_in_disjoint_alias_sets_p (mem1, mem2)
193 #ifdef ENABLE_CHECKING
194 /* Perform a basic sanity check. Namely, that there are no alias sets
195 if we're not using strict aliasing. This helps to catch bugs
196 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
197 where a MEM is allocated in some way other than by the use of
198 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
199 use alias sets to indicate that spilled registers cannot alias each
200 other, we might need to remove this check. */
201 if (!flag_strict_aliasing &&
202 (MEM_ALIAS_SET (mem1) || MEM_ALIAS_SET (mem2)))
206 /* The code used in varargs macros are often not conforming ANSI C,
207 which can trick the compiler into making incorrect aliasing
208 assumptions in these functions. So, we don't use alias sets in
209 such a function. FIXME: This should be moved into the front-end;
210 it is a language-dependent notion, and there's no reason not to
211 still use these checks to handle globals. */
212 if (current_function_stdarg || current_function_varargs)
215 if (!MEM_ALIAS_SET (mem1) || !MEM_ALIAS_SET (mem2))
216 /* We have no alias set information for one of the MEMs, so we
217 have to assume it can alias anything. */
220 if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2))
221 /* The two alias sets are the same, so they may alias. */
224 /* Iterate through each of the children of the first alias set,
225 comparing it with the second alias set. */
226 ase = get_alias_set_entry (MEM_ALIAS_SET (mem1));
227 if (ase && splay_tree_lookup (ase->children,
228 (splay_tree_key) MEM_ALIAS_SET (mem2)))
231 /* Now do the same, but with the alias sets reversed. */
232 ase = get_alias_set_entry (MEM_ALIAS_SET (mem2));
233 if (ase && splay_tree_lookup (ase->children,
234 (splay_tree_key) MEM_ALIAS_SET (mem1)))
237 /* The two MEMs are in distinct alias sets, and neither one is the
238 child of the other. Therefore, they cannot alias. */
242 /* Insert the NODE into the splay tree given by DATA. Used by
243 record_alias_subset via splay_tree_foreach. */
246 insert_subset_children (node, data)
247 splay_tree_node node;
250 splay_tree_insert ((splay_tree) data,
257 /* Indicate that things in SUBSET can alias things in SUPERSET, but
258 not vice versa. For example, in C, a store to an `int' can alias a
259 structure containing an `int', but not vice versa. Here, the
260 structure would be the SUPERSET and `int' the SUBSET. This
261 function should be called only once per SUPERSET/SUBSET pair. At
262 present any given alias set may only be a subset of one superset.
264 It is illegal for SUPERSET to be zero; everything is implicitly a
265 subset of alias set zero. */
268 record_alias_subset (superset, subset)
272 alias_set_entry superset_entry;
273 alias_set_entry subset_entry;
278 superset_entry = get_alias_set_entry (superset);
281 /* Create an entry for the SUPERSET, so that we have a place to
282 attach the SUBSET. */
284 (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
285 superset_entry->alias_set = superset;
286 superset_entry->children
287 = splay_tree_new (splay_tree_compare_ints, 0, 0);
288 splay_tree_insert (alias_sets,
289 (splay_tree_key) superset,
290 (splay_tree_value) superset_entry);
294 subset_entry = get_alias_set_entry (subset);
296 /* There is an entry for the subset. Enter all of its children
297 (if they are not already present) as children of the SUPERSET. */
298 splay_tree_foreach (subset_entry->children,
299 insert_subset_children,
300 superset_entry->children);
302 /* Enter the SUBSET itself as a child of the SUPERSET. */
303 splay_tree_insert (superset_entry->children,
304 (splay_tree_key) subset,
308 /* Inside SRC, the source of a SET, find a base address. */
311 find_base_value (src)
314 switch (GET_CODE (src))
321 /* At the start of a function argument registers have known base
322 values which may be lost later. Returning an ADDRESS
323 expression here allows optimization based on argument values
324 even when the argument registers are used for other purposes. */
325 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
326 return new_reg_base_value[REGNO (src)];
328 /* If a pseudo has a known base value, return it. Do not do this
329 for hard regs since it can result in a circular dependency
330 chain for registers which have values at function entry.
332 The test above is not sufficient because the scheduler may move
333 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
334 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
335 && (unsigned) REGNO (src) < reg_base_value_size
336 && reg_base_value[REGNO (src)])
337 return reg_base_value[REGNO (src)];
342 /* Check for an argument passed in memory. Only record in the
343 copying-arguments block; it is too hard to track changes
345 if (copying_arguments
346 && (XEXP (src, 0) == arg_pointer_rtx
347 || (GET_CODE (XEXP (src, 0)) == PLUS
348 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
349 return gen_rtx_ADDRESS (VOIDmode, src);
354 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
361 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
363 /* If either operand is a REG, then see if we already have
364 a known value for it. */
365 if (GET_CODE (src_0) == REG)
367 temp = find_base_value (src_0);
372 if (GET_CODE (src_1) == REG)
374 temp = find_base_value (src_1);
379 /* Guess which operand is the base address.
381 If either operand is a symbol, then it is the base. If
382 either operand is a CONST_INT, then the other is the base. */
384 if (GET_CODE (src_1) == CONST_INT
385 || GET_CODE (src_0) == SYMBOL_REF
386 || GET_CODE (src_0) == LABEL_REF
387 || GET_CODE (src_0) == CONST)
388 return find_base_value (src_0);
390 if (GET_CODE (src_0) == CONST_INT
391 || GET_CODE (src_1) == SYMBOL_REF
392 || GET_CODE (src_1) == LABEL_REF
393 || GET_CODE (src_1) == CONST)
394 return find_base_value (src_1);
396 /* This might not be necessary anymore.
398 If either operand is a REG that is a known pointer, then it
400 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
401 return find_base_value (src_0);
403 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
404 return find_base_value (src_1);
410 /* The standard form is (lo_sum reg sym) so look only at the
412 return find_base_value (XEXP (src, 1));
415 /* If the second operand is constant set the base
416 address to the first operand. */
417 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
418 return find_base_value (XEXP (src, 0));
422 case SIGN_EXTEND: /* used for NT/Alpha pointers */
424 return find_base_value (XEXP (src, 0));
433 /* Called from init_alias_analysis indirectly through note_stores. */
435 /* while scanning insns to find base values, reg_seen[N] is nonzero if
436 register N has been set in this function. */
437 static char *reg_seen;
439 /* Addresses which are known not to alias anything else are identified
440 by a unique integer. */
441 static int unique_id;
444 record_set (dest, set)
450 if (GET_CODE (dest) != REG)
453 regno = REGNO (dest);
457 /* A CLOBBER wipes out any old value but does not prevent a previously
458 unset register from acquiring a base address (i.e. reg_seen is not
460 if (GET_CODE (set) == CLOBBER)
462 new_reg_base_value[regno] = 0;
471 new_reg_base_value[regno] = 0;
475 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
476 GEN_INT (unique_id++));
480 /* This is not the first set. If the new value is not related to the
481 old value, forget the base value. Note that the following code is
483 extern int x, y; int *p = &x; p += (&y-&x);
484 ANSI C does not allow computing the difference of addresses
485 of distinct top level objects. */
486 if (new_reg_base_value[regno])
487 switch (GET_CODE (src))
492 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
493 new_reg_base_value[regno] = 0;
496 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
497 new_reg_base_value[regno] = 0;
500 new_reg_base_value[regno] = 0;
503 /* If this is the first set of a register, record the value. */
504 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
505 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
506 new_reg_base_value[regno] = find_base_value (src);
511 /* Called from loop optimization when a new pseudo-register is created. */
513 record_base_value (regno, val, invariant)
518 if ((unsigned) regno >= reg_base_value_size)
521 /* If INVARIANT is true then this value also describes an invariant
522 relationship which can be used to deduce that two registers with
523 unknown values are different. */
524 if (invariant && alias_invariant)
525 alias_invariant[regno] = val;
527 if (GET_CODE (val) == REG)
529 if ((unsigned) REGNO (val) < reg_base_value_size)
531 reg_base_value[regno] = reg_base_value[REGNO (val)];
535 reg_base_value[regno] = find_base_value (val);
542 /* Recursively look for equivalences. */
543 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
544 && REGNO (x) < reg_known_value_size)
545 return reg_known_value[REGNO (x)] == x
546 ? x : canon_rtx (reg_known_value[REGNO (x)]);
547 else if (GET_CODE (x) == PLUS)
549 rtx x0 = canon_rtx (XEXP (x, 0));
550 rtx x1 = canon_rtx (XEXP (x, 1));
552 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
554 /* We can tolerate LO_SUMs being offset here; these
555 rtl are used for nothing other than comparisons. */
556 if (GET_CODE (x0) == CONST_INT)
557 return plus_constant_for_output (x1, INTVAL (x0));
558 else if (GET_CODE (x1) == CONST_INT)
559 return plus_constant_for_output (x0, INTVAL (x1));
560 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
563 /* This gives us much better alias analysis when called from
564 the loop optimizer. Note we want to leave the original
565 MEM alone, but need to return the canonicalized MEM with
566 all the flags with their original values. */
567 else if (GET_CODE (x) == MEM)
569 rtx addr = canon_rtx (XEXP (x, 0));
570 if (addr != XEXP (x, 0))
572 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
573 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
574 MEM_COPY_ATTRIBUTES (new, x);
575 MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
582 /* Return 1 if X and Y are identical-looking rtx's.
584 We use the data in reg_known_value above to see if two registers with
585 different numbers are, in fact, equivalent. */
588 rtx_equal_for_memref_p (x, y)
593 register enum rtx_code code;
596 if (x == 0 && y == 0)
598 if (x == 0 || y == 0)
607 /* Rtx's of different codes cannot be equal. */
608 if (code != GET_CODE (y))
611 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
612 (REG:SI x) and (REG:HI x) are NOT equivalent. */
614 if (GET_MODE (x) != GET_MODE (y))
617 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
620 return REGNO (x) == REGNO (y);
621 if (code == LABEL_REF)
622 return XEXP (x, 0) == XEXP (y, 0);
623 if (code == SYMBOL_REF)
624 return XSTR (x, 0) == XSTR (y, 0);
625 if (code == CONST_INT)
626 return INTVAL (x) == INTVAL (y);
627 if (code == ADDRESSOF)
628 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
630 /* For commutative operations, the RTX match if the operand match in any
631 order. Also handle the simple binary and unary cases without a loop. */
632 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
633 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
634 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
635 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
636 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
637 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
638 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
639 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
640 else if (GET_RTX_CLASS (code) == '1')
641 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
643 /* Compare the elements. If any pair of corresponding elements
644 fail to match, return 0 for the whole things.
646 Limit cases to types which actually appear in addresses. */
648 fmt = GET_RTX_FORMAT (code);
649 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
654 if (XINT (x, i) != XINT (y, i))
659 /* Two vectors must have the same length. */
660 if (XVECLEN (x, i) != XVECLEN (y, i))
663 /* And the corresponding elements must match. */
664 for (j = 0; j < XVECLEN (x, i); j++)
665 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
670 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
674 /* This can happen for an asm which clobbers memory. */
678 /* It is believed that rtx's at this level will never
679 contain anything but integers and other rtx's,
680 except for within LABEL_REFs and SYMBOL_REFs. */
688 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
689 X and return it, or return 0 if none found. */
692 find_symbolic_term (x)
696 register enum rtx_code code;
700 if (code == SYMBOL_REF || code == LABEL_REF)
702 if (GET_RTX_CLASS (code) == 'o')
705 fmt = GET_RTX_FORMAT (code);
706 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
712 t = find_symbolic_term (XEXP (x, i));
716 else if (fmt[i] == 'E')
726 switch (GET_CODE (x))
729 return REG_BASE_VALUE (x);
732 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
738 return find_base_term (XEXP (x, 0));
742 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
749 rtx tmp = find_base_term (XEXP (x, 0));
752 return find_base_term (XEXP (x, 1));
756 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
757 return REG_BASE_VALUE (XEXP (x, 0));
769 /* Return 0 if the addresses X and Y are known to point to different
770 objects, 1 if they might be pointers to the same object. */
773 base_alias_check (x, y, x_mode, y_mode)
775 enum machine_mode x_mode, y_mode;
777 rtx x_base = find_base_term (x);
778 rtx y_base = find_base_term (y);
780 /* If the address itself has no known base see if a known equivalent
781 value has one. If either address still has no known base, nothing
782 is known about aliasing. */
786 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
788 x_base = find_base_term (x_c);
796 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
798 y_base = find_base_term (y_c);
803 /* If the base addresses are equal nothing is known about aliasing. */
804 if (rtx_equal_p (x_base, y_base))
807 /* The base addresses of the read and write are different expressions.
808 If they are both symbols and they are not accessed via AND, there is
809 no conflict. We can bring knowledge of object alignment into play
810 here. For example, on alpha, "char a, b;" can alias one another,
811 though "char a; long b;" cannot. */
812 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
814 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
816 if (GET_CODE (x) == AND
817 && (GET_CODE (XEXP (x, 1)) != CONST_INT
818 || GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
820 if (GET_CODE (y) == AND
821 && (GET_CODE (XEXP (y, 1)) != CONST_INT
822 || GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
824 /* Differing symbols never alias. */
828 /* If one address is a stack reference there can be no alias:
829 stack references using different base registers do not alias,
830 a stack reference can not alias a parameter, and a stack reference
831 can not alias a global. */
832 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
833 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
836 if (! flag_argument_noalias)
839 if (flag_argument_noalias > 1)
842 /* Weak noalias assertion (arguments are distinct, but may match globals). */
843 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
846 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
847 where SIZE is the size in bytes of the memory reference. If ADDR
848 is not modified by the memory reference then ADDR is returned. */
851 addr_side_effect_eval (addr, size, n_refs)
858 switch (GET_CODE (addr))
861 offset = (n_refs + 1) * size;
864 offset = -(n_refs + 1) * size;
867 offset = n_refs * size;
870 offset = -n_refs * size;
878 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset));
880 addr = XEXP (addr, 0);
885 /* Return nonzero if X and Y (memory addresses) could reference the
886 same location in memory. C is an offset accumulator. When
887 C is nonzero, we are testing aliases between X and Y + C.
888 XSIZE is the size in bytes of the X reference,
889 similarly YSIZE is the size in bytes for Y.
891 If XSIZE or YSIZE is zero, we do not know the amount of memory being
892 referenced (the reference was BLKmode), so make the most pessimistic
895 If XSIZE or YSIZE is negative, we may access memory outside the object
896 being referenced as a side effect. This can happen when using AND to
897 align memory references, as is done on the Alpha.
899 Nice to notice that varying addresses cannot conflict with fp if no
900 local variables had their addresses taken, but that's too hard now. */
904 memrefs_conflict_p (xsize, x, ysize, y, c)
909 if (GET_CODE (x) == HIGH)
911 else if (GET_CODE (x) == LO_SUM)
914 x = canon_rtx (addr_side_effect_eval (x, xsize, 0));
915 if (GET_CODE (y) == HIGH)
917 else if (GET_CODE (y) == LO_SUM)
920 y = canon_rtx (addr_side_effect_eval (y, ysize, 0));
922 if (rtx_equal_for_memref_p (x, y))
924 if (xsize <= 0 || ysize <= 0)
926 if (c >= 0 && xsize > c)
928 if (c < 0 && ysize+c > 0)
933 /* This code used to check for conflicts involving stack references and
934 globals but the base address alias code now handles these cases. */
936 if (GET_CODE (x) == PLUS)
938 /* The fact that X is canonicalized means that this
939 PLUS rtx is canonicalized. */
940 rtx x0 = XEXP (x, 0);
941 rtx x1 = XEXP (x, 1);
943 if (GET_CODE (y) == PLUS)
945 /* The fact that Y is canonicalized means that this
946 PLUS rtx is canonicalized. */
947 rtx y0 = XEXP (y, 0);
948 rtx y1 = XEXP (y, 1);
950 if (rtx_equal_for_memref_p (x1, y1))
951 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
952 if (rtx_equal_for_memref_p (x0, y0))
953 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
954 if (GET_CODE (x1) == CONST_INT)
956 if (GET_CODE (y1) == CONST_INT)
957 return memrefs_conflict_p (xsize, x0, ysize, y0,
958 c - INTVAL (x1) + INTVAL (y1));
960 return memrefs_conflict_p (xsize, x0, ysize, y,
963 else if (GET_CODE (y1) == CONST_INT)
964 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
968 else if (GET_CODE (x1) == CONST_INT)
969 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
971 else if (GET_CODE (y) == PLUS)
973 /* The fact that Y is canonicalized means that this
974 PLUS rtx is canonicalized. */
975 rtx y0 = XEXP (y, 0);
976 rtx y1 = XEXP (y, 1);
978 if (GET_CODE (y1) == CONST_INT)
979 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
984 if (GET_CODE (x) == GET_CODE (y))
985 switch (GET_CODE (x))
989 /* Handle cases where we expect the second operands to be the
990 same, and check only whether the first operand would conflict
993 rtx x1 = canon_rtx (XEXP (x, 1));
994 rtx y1 = canon_rtx (XEXP (y, 1));
995 if (! rtx_equal_for_memref_p (x1, y1))
997 x0 = canon_rtx (XEXP (x, 0));
998 y0 = canon_rtx (XEXP (y, 0));
999 if (rtx_equal_for_memref_p (x0, y0))
1000 return (xsize == 0 || ysize == 0
1001 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1003 /* Can't properly adjust our sizes. */
1004 if (GET_CODE (x1) != CONST_INT)
1006 xsize /= INTVAL (x1);
1007 ysize /= INTVAL (x1);
1009 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1013 /* Are these registers known not to be equal? */
1014 if (alias_invariant)
1016 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1017 rtx i_x, i_y; /* invariant relationships of X and Y */
1019 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1020 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1022 if (i_x == 0 && i_y == 0)
1025 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1026 ysize, i_y ? i_y : y, c))
1035 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1036 as an access with indeterminate size. Assume that references
1037 besides AND are aligned, so if the size of the other reference is
1038 at least as large as the alignment, assume no other overlap. */
1039 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1041 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1043 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c);
1045 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1047 /* ??? If we are indexing far enough into the array/structure, we
1048 may yet be able to determine that we can not overlap. But we
1049 also need to that we are far enough from the end not to overlap
1050 a following reference, so we do nothing with that for now. */
1051 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1053 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c);
1058 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1060 c += (INTVAL (y) - INTVAL (x));
1061 return (xsize <= 0 || ysize <= 0
1062 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1065 if (GET_CODE (x) == CONST)
1067 if (GET_CODE (y) == CONST)
1068 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1069 ysize, canon_rtx (XEXP (y, 0)), c);
1071 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1074 if (GET_CODE (y) == CONST)
1075 return memrefs_conflict_p (xsize, x, ysize,
1076 canon_rtx (XEXP (y, 0)), c);
1079 return (xsize < 0 || ysize < 0
1080 || (rtx_equal_for_memref_p (x, y)
1081 && (xsize == 0 || ysize == 0
1082 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1089 /* Functions to compute memory dependencies.
1091 Since we process the insns in execution order, we can build tables
1092 to keep track of what registers are fixed (and not aliased), what registers
1093 are varying in known ways, and what registers are varying in unknown
1096 If both memory references are volatile, then there must always be a
1097 dependence between the two references, since their order can not be
1098 changed. A volatile and non-volatile reference can be interchanged
1101 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
1102 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
1103 allow QImode aliasing because the ANSI C standard allows character
1104 pointers to alias anything. We are assuming that characters are
1105 always QImode here. We also must allow AND addresses, because they may
1106 generate accesses outside the object being referenced. This is used to
1107 generate aligned addresses from unaligned addresses, for instance, the
1108 alpha storeqi_unaligned pattern. */
1110 /* Read dependence: X is read after read in MEM takes place. There can
1111 only be a dependence here if both reads are volatile. */
1114 read_dependence (mem, x)
1118 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1121 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1122 MEM2 is a reference to a structure at a varying address, or returns
1123 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1124 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1125 to decide whether or not an address may vary; it should return
1126 nozero whenever variation is possible. */
1129 fixed_scalar_and_varying_struct_p (mem1, mem2, varies_p)
1132 int (*varies_p) PROTO((rtx));
1134 rtx mem1_addr = XEXP (mem1, 0);
1135 rtx mem2_addr = XEXP (mem2, 0);
1137 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1138 && !varies_p (mem1_addr) && varies_p (mem2_addr))
1139 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1143 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1144 && varies_p (mem1_addr) && !varies_p (mem2_addr))
1145 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1152 /* Returns nonzero if something about the mode or address format MEM1
1153 indicates that it might well alias *anything*. */
1156 aliases_everything_p (mem)
1159 if (GET_MODE (mem) == QImode)
1160 /* ANSI C says that a `char*' can point to anything. */
1163 if (GET_CODE (XEXP (mem, 0)) == AND)
1164 /* If the address is an AND, its very hard to know at what it is
1165 actually pointing. */
1171 /* True dependence: X is read after store in MEM takes place. */
1174 true_dependence (mem, mem_mode, x, varies)
1176 enum machine_mode mem_mode;
1178 int (*varies) PROTO((rtx));
1180 register rtx x_addr, mem_addr;
1182 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1185 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1188 /* If X is an unchanging read, then it can't possibly conflict with any
1189 non-unchanging store. It may conflict with an unchanging write though,
1190 because there may be a single store to this address to initialize it.
1191 Just fall through to the code below to resolve the case where we have
1192 both an unchanging read and an unchanging write. This won't handle all
1193 cases optimally, but the possible performance loss should be
1195 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
1198 if (mem_mode == VOIDmode)
1199 mem_mode = GET_MODE (mem);
1201 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), mem_mode))
1204 x_addr = canon_rtx (XEXP (x, 0));
1205 mem_addr = canon_rtx (XEXP (mem, 0));
1207 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
1208 SIZE_FOR_MODE (x), x_addr, 0))
1211 if (aliases_everything_p (x))
1214 /* We cannot use aliases_everyting_p to test MEM, since we must look
1215 at MEM_MODE, rather than GET_MODE (MEM). */
1216 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
1219 /* In true_dependence we also allow BLKmode to alias anything. Why
1220 don't we do this in anti_dependence and output_dependence? */
1221 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
1224 return !fixed_scalar_and_varying_struct_p (mem, x, varies);
1227 /* Returns non-zero if a write to X might alias a previous read from
1228 (or, if WRITEP is non-zero, a write to) MEM. */
1231 write_dependence_p (mem, x, writep)
1236 rtx x_addr, mem_addr;
1239 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1242 /* If MEM is an unchanging read, then it can't possibly conflict with
1243 the store to X, because there is at most one store to MEM, and it must
1244 have occurred somewhere before MEM. */
1245 if (!writep && RTX_UNCHANGING_P (mem))
1248 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x),
1253 mem = canon_rtx (mem);
1255 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1258 x_addr = XEXP (x, 0);
1259 mem_addr = XEXP (mem, 0);
1261 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
1262 SIZE_FOR_MODE (x), x_addr, 0))
1266 = fixed_scalar_and_varying_struct_p (mem, x, rtx_addr_varies_p);
1268 return (!(fixed_scalar == mem && !aliases_everything_p (x))
1269 && !(fixed_scalar == x && !aliases_everything_p (mem)));
1272 /* Anti dependence: X is written after read in MEM takes place. */
1275 anti_dependence (mem, x)
1279 return write_dependence_p (mem, x, /*writep=*/0);
1282 /* Output dependence: X is written after store in MEM takes place. */
1285 output_dependence (mem, x)
1289 return write_dependence_p (mem, x, /*writep=*/1);
1293 static HARD_REG_SET argument_registers;
1300 #ifndef OUTGOING_REGNO
1301 #define OUTGOING_REGNO(N) N
1303 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1304 /* Check whether this register can hold an incoming pointer
1305 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1306 numbers, so translate if necessary due to register windows. */
1307 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1308 && HARD_REGNO_MODE_OK (i, Pmode))
1309 SET_HARD_REG_BIT (argument_registers, i);
1311 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
1315 init_alias_analysis ()
1317 int maxreg = max_reg_num ();
1320 register unsigned int ui;
1323 reg_known_value_size = maxreg;
1326 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1327 - FIRST_PSEUDO_REGISTER;
1329 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1330 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1331 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1332 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1333 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1335 /* Overallocate reg_base_value to allow some growth during loop
1336 optimization. Loop unrolling can create a large number of
1338 reg_base_value_size = maxreg * 2;
1339 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1340 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1341 reg_seen = (char *)alloca (reg_base_value_size);
1342 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1343 if (! reload_completed && flag_unroll_loops)
1345 alias_invariant = (rtx *)xrealloc (alias_invariant,
1346 reg_base_value_size * sizeof (rtx));
1347 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1351 /* The basic idea is that each pass through this loop will use the
1352 "constant" information from the previous pass to propagate alias
1353 information through another level of assignments.
1355 This could get expensive if the assignment chains are long. Maybe
1356 we should throttle the number of iterations, possibly based on
1357 the optimization level or flag_expensive_optimizations.
1359 We could propagate more information in the first pass by making use
1360 of REG_N_SETS to determine immediately that the alias information
1361 for a pseudo is "constant".
1363 A program with an uninitialized variable can cause an infinite loop
1364 here. Instead of doing a full dataflow analysis to detect such problems
1365 we just cap the number of iterations for the loop.
1367 The state of the arrays for the set chain in question does not matter
1368 since the program has undefined behavior. */
1373 /* Assume nothing will change this iteration of the loop. */
1376 /* We want to assign the same IDs each iteration of this loop, so
1377 start counting from zero each iteration of the loop. */
1380 /* We're at the start of the funtion each iteration through the
1381 loop, so we're copying arguments. */
1382 copying_arguments = 1;
1384 /* Wipe the potential alias information clean for this pass. */
1385 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1387 /* Wipe the reg_seen array clean. */
1388 bzero ((char *) reg_seen, reg_base_value_size);
1390 /* Mark all hard registers which may contain an address.
1391 The stack, frame and argument pointers may contain an address.
1392 An argument register which can hold a Pmode value may contain
1393 an address even if it is not in BASE_REGS.
1395 The address expression is VOIDmode for an argument and
1396 Pmode for other registers. */
1398 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1399 if (TEST_HARD_REG_BIT (argument_registers, i))
1400 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1401 gen_rtx_REG (Pmode, i));
1403 new_reg_base_value[STACK_POINTER_REGNUM]
1404 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1405 new_reg_base_value[ARG_POINTER_REGNUM]
1406 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1407 new_reg_base_value[FRAME_POINTER_REGNUM]
1408 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1409 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1410 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1411 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1413 if (struct_value_incoming_rtx
1414 && GET_CODE (struct_value_incoming_rtx) == REG)
1415 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1416 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1418 if (static_chain_rtx
1419 && GET_CODE (static_chain_rtx) == REG)
1420 new_reg_base_value[REGNO (static_chain_rtx)]
1421 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1423 /* Walk the insns adding values to the new_reg_base_value array. */
1424 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1426 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1429 /* If this insn has a noalias note, process it, Otherwise,
1430 scan for sets. A simple set will have no side effects
1431 which could change the base value of any other register. */
1433 if (GET_CODE (PATTERN (insn)) == SET
1434 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1435 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1437 note_stores (PATTERN (insn), record_set);
1439 set = single_set (insn);
1442 && GET_CODE (SET_DEST (set)) == REG
1443 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1444 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1445 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1446 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1447 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
1448 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
1450 int regno = REGNO (SET_DEST (set));
1451 reg_known_value[regno] = XEXP (note, 0);
1452 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1455 else if (GET_CODE (insn) == NOTE
1456 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1457 copying_arguments = 0;
1460 /* Now propagate values from new_reg_base_value to reg_base_value. */
1461 for (ui = 0; ui < reg_base_value_size; ui++)
1463 if (new_reg_base_value[ui]
1464 && new_reg_base_value[ui] != reg_base_value[ui]
1465 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
1467 reg_base_value[ui] = new_reg_base_value[ui];
1472 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1474 /* Fill in the remaining entries. */
1475 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1476 if (reg_known_value[i] == 0)
1477 reg_known_value[i] = regno_reg_rtx[i];
1479 /* Simplify the reg_base_value array so that no register refers to
1480 another register, except to special registers indirectly through
1481 ADDRESS expressions.
1483 In theory this loop can take as long as O(registers^2), but unless
1484 there are very long dependency chains it will run in close to linear
1487 This loop may not be needed any longer now that the main loop does
1488 a better job at propagating alias information. */
1494 for (ui = 0; ui < reg_base_value_size; ui++)
1496 rtx base = reg_base_value[ui];
1497 if (base && GET_CODE (base) == REG)
1499 unsigned int base_regno = REGNO (base);
1500 if (base_regno == ui) /* register set from itself */
1501 reg_base_value[ui] = 0;
1503 reg_base_value[ui] = reg_base_value[base_regno];
1508 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1510 new_reg_base_value = 0;
1515 end_alias_analysis ()
1517 reg_known_value = 0;
1519 reg_base_value_size = 0;
1520 if (alias_invariant)
1522 free ((char *)alias_invariant);
1523 alias_invariant = 0;