1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998 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 static rtx canon_rtx PROTO((rtx));
32 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
33 static rtx find_symbolic_term PROTO((rtx));
34 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
36 static void record_set PROTO((rtx, rtx));
37 static rtx find_base_term PROTO((rtx));
38 static int base_alias_check PROTO((rtx, rtx));
39 static rtx find_base_value PROTO((rtx));
41 /* Set up all info needed to perform alias analysis on memory references. */
43 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
45 /* Perform a basic sanity check. Namely, that there are
46 no alias sets if we're not doing strict aliasing. This helps
47 to catch bugs whereby someone uses PUT_CODE, but doesn't clear
48 MEM_ALIAS_SET, or where a MEM is allocated in some way other
49 than by the use of gen_rtx_MEM, and the MEM_ALIAS_SET is not
51 #ifdef ENABLE_CHECKING
52 #define CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2) \
53 (!flag_strict_aliasing \
54 && (MEM_ALIAS_SET (MEM1) || MEM_ALIAS_SET (MEM2)) \
57 #define CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2) ((void)0)
60 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
61 different alias sets. */
62 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
63 (CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2), \
64 MEM_ALIAS_SET (MEM1) && MEM_ALIAS_SET (MEM2) \
65 && MEM_ALIAS_SET (MEM1) != MEM_ALIAS_SET (MEM2))
67 /* Cap the number of passes we make over the insns propagating alias
68 information through set chains.
70 10 is a completely arbitrary choice. */
71 #define MAX_ALIAS_LOOP_PASSES 10
73 /* reg_base_value[N] gives an address to which register N is related.
74 If all sets after the first add or subtract to the current value
75 or otherwise modify it so it does not point to a different top level
76 object, reg_base_value[N] is equal to the address part of the source
79 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
80 expressions represent certain special values: function arguments and
81 the stack, frame, and argument pointers. The contents of an address
82 expression are not used (but they are descriptive for debugging);
83 only the address and mode matter. Pointer equality, not rtx_equal_p,
84 determines whether two ADDRESS expressions refer to the same base
85 address. The mode determines whether it is a function argument or
86 other special value. */
89 rtx *new_reg_base_value;
90 unsigned int reg_base_value_size; /* size of reg_base_value array */
91 #define REG_BASE_VALUE(X) \
92 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
94 /* Vector of known invariant relationships between registers. Set in
95 loop unrolling. Indexed by register number, if nonzero the value
96 is an expression describing this register in terms of another.
98 The length of this array is REG_BASE_VALUE_SIZE.
100 Because this array contains only pseudo registers it has no effect
102 static rtx *alias_invariant;
104 /* Vector indexed by N giving the initial (unchanging) value known
105 for pseudo-register N. */
106 rtx *reg_known_value;
108 /* Indicates number of valid entries in reg_known_value. */
109 static int reg_known_value_size;
111 /* Vector recording for each reg_known_value whether it is due to a
112 REG_EQUIV note. Future passes (viz., reload) may replace the
113 pseudo with the equivalent expression and so we account for the
114 dependences that would be introduced if that happens. */
115 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
116 assign_parms mention the arg pointer, and there are explicit insns in the
117 RTL that modify the arg pointer. Thus we must ensure that such insns don't
118 get scheduled across each other because that would invalidate the REG_EQUIV
119 notes. One could argue that the REG_EQUIV notes are wrong, but solving
120 the problem in the scheduler will likely give better code, so we do it
122 char *reg_known_equiv_p;
124 /* True when scanning insns from the start of the rtl to the
125 NOTE_INSN_FUNCTION_BEG note. */
127 static int copying_arguments;
129 /* Inside SRC, the source of a SET, find a base address. */
132 find_base_value (src)
135 switch (GET_CODE (src))
142 /* At the start of a function argument registers have known base
143 values which may be lost later. Returning an ADDRESS
144 expression here allows optimization based on argument values
145 even when the argument registers are used for other purposes. */
146 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
147 return new_reg_base_value[REGNO (src)];
149 /* If a pseudo has a known base value, return it. Do not do this
150 for hard regs since it can result in a circular dependency
151 chain for registers which have values at function entry.
153 The test above is not sufficient because the scheduler may move
154 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
155 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
156 && REGNO (src) < reg_base_value_size
157 && reg_base_value[REGNO (src)])
158 return reg_base_value[REGNO (src)];
163 /* Check for an argument passed in memory. Only record in the
164 copying-arguments block; it is too hard to track changes
166 if (copying_arguments
167 && (XEXP (src, 0) == arg_pointer_rtx
168 || (GET_CODE (XEXP (src, 0)) == PLUS
169 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
170 return gen_rtx_ADDRESS (VOIDmode, src);
175 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
182 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
184 /* If either operand is a REG, then see if we already have
185 a known value for it. */
186 if (GET_CODE (src_0) == REG)
188 temp = find_base_value (src_0);
193 if (GET_CODE (src_1) == REG)
195 temp = find_base_value (src_1);
200 /* Guess which operand is the base address.
202 If either operand is a symbol, then it is the base. If
203 either operand is a CONST_INT, then the other is the base. */
205 if (GET_CODE (src_1) == CONST_INT
206 || GET_CODE (src_0) == SYMBOL_REF
207 || GET_CODE (src_0) == LABEL_REF
208 || GET_CODE (src_0) == CONST)
209 return find_base_value (src_0);
211 if (GET_CODE (src_0) == CONST_INT
212 || GET_CODE (src_1) == SYMBOL_REF
213 || GET_CODE (src_1) == LABEL_REF
214 || GET_CODE (src_1) == CONST)
215 return find_base_value (src_1);
217 /* This might not be necessary anymore.
219 If either operand is a REG that is a known pointer, then it
221 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
222 return find_base_value (src_0);
224 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
225 return find_base_value (src_1);
231 /* The standard form is (lo_sum reg sym) so look only at the
233 return find_base_value (XEXP (src, 1));
236 /* If the second operand is constant set the base
237 address to the first operand. */
238 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
239 return find_base_value (XEXP (src, 0));
243 case SIGN_EXTEND: /* used for NT/Alpha pointers */
245 return find_base_value (XEXP (src, 0));
254 /* Called from init_alias_analysis indirectly through note_stores. */
256 /* while scanning insns to find base values, reg_seen[N] is nonzero if
257 register N has been set in this function. */
258 static char *reg_seen;
260 /* Addresses which are known not to alias anything else are identified
261 by a unique integer. */
262 static int unique_id;
265 record_set (dest, set)
271 if (GET_CODE (dest) != REG)
274 regno = REGNO (dest);
278 /* A CLOBBER wipes out any old value but does not prevent a previously
279 unset register from acquiring a base address (i.e. reg_seen is not
281 if (GET_CODE (set) == CLOBBER)
283 new_reg_base_value[regno] = 0;
292 new_reg_base_value[regno] = 0;
296 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
297 GEN_INT (unique_id++));
301 /* This is not the first set. If the new value is not related to the
302 old value, forget the base value. Note that the following code is
304 extern int x, y; int *p = &x; p += (&y-&x);
305 ANSI C does not allow computing the difference of addresses
306 of distinct top level objects. */
307 if (new_reg_base_value[regno])
308 switch (GET_CODE (src))
313 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
314 new_reg_base_value[regno] = 0;
317 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
318 new_reg_base_value[regno] = 0;
321 new_reg_base_value[regno] = 0;
324 /* If this is the first set of a register, record the value. */
325 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
326 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
327 new_reg_base_value[regno] = find_base_value (src);
332 /* Called from loop optimization when a new pseudo-register is created. */
334 record_base_value (regno, val, invariant)
339 if (regno >= reg_base_value_size)
342 /* If INVARIANT is true then this value also describes an invariant
343 relationship which can be used to deduce that two registers with
344 unknown values are different. */
345 if (invariant && alias_invariant)
346 alias_invariant[regno] = val;
348 if (GET_CODE (val) == REG)
350 if (REGNO (val) < reg_base_value_size)
352 reg_base_value[regno] = reg_base_value[REGNO (val)];
356 reg_base_value[regno] = find_base_value (val);
363 /* Recursively look for equivalences. */
364 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
365 && REGNO (x) < reg_known_value_size)
366 return reg_known_value[REGNO (x)] == x
367 ? x : canon_rtx (reg_known_value[REGNO (x)]);
368 else if (GET_CODE (x) == PLUS)
370 rtx x0 = canon_rtx (XEXP (x, 0));
371 rtx x1 = canon_rtx (XEXP (x, 1));
373 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
375 /* We can tolerate LO_SUMs being offset here; these
376 rtl are used for nothing other than comparisons. */
377 if (GET_CODE (x0) == CONST_INT)
378 return plus_constant_for_output (x1, INTVAL (x0));
379 else if (GET_CODE (x1) == CONST_INT)
380 return plus_constant_for_output (x0, INTVAL (x1));
381 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
384 /* This gives us much better alias analysis when called from
385 the loop optimizer. Note we want to leave the original
386 MEM alone, but need to return the canonicalized MEM with
387 all the flags with their original values. */
388 else if (GET_CODE (x) == MEM)
390 rtx addr = canon_rtx (XEXP (x, 0));
391 if (addr != XEXP (x, 0))
393 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
394 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
395 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
396 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
397 MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
404 /* Return 1 if X and Y are identical-looking rtx's.
406 We use the data in reg_known_value above to see if two registers with
407 different numbers are, in fact, equivalent. */
410 rtx_equal_for_memref_p (x, y)
415 register enum rtx_code code;
418 if (x == 0 && y == 0)
420 if (x == 0 || y == 0)
429 /* Rtx's of different codes cannot be equal. */
430 if (code != GET_CODE (y))
433 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
434 (REG:SI x) and (REG:HI x) are NOT equivalent. */
436 if (GET_MODE (x) != GET_MODE (y))
439 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
442 return REGNO (x) == REGNO (y);
443 if (code == LABEL_REF)
444 return XEXP (x, 0) == XEXP (y, 0);
445 if (code == SYMBOL_REF)
446 return XSTR (x, 0) == XSTR (y, 0);
447 if (code == CONST_INT)
448 return INTVAL (x) == INTVAL (y);
449 if (code == ADDRESSOF)
450 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
452 /* For commutative operations, the RTX match if the operand match in any
453 order. Also handle the simple binary and unary cases without a loop. */
454 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
455 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
456 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
457 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
458 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
459 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
460 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
461 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
462 else if (GET_RTX_CLASS (code) == '1')
463 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
465 /* Compare the elements. If any pair of corresponding elements
466 fail to match, return 0 for the whole things.
468 Limit cases to types which actually appear in addresses. */
470 fmt = GET_RTX_FORMAT (code);
471 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
476 if (XINT (x, i) != XINT (y, i))
481 /* Two vectors must have the same length. */
482 if (XVECLEN (x, i) != XVECLEN (y, i))
485 /* And the corresponding elements must match. */
486 for (j = 0; j < XVECLEN (x, i); j++)
487 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
492 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
496 /* This can happen for an asm which clobbers memory. */
500 /* It is believed that rtx's at this level will never
501 contain anything but integers and other rtx's,
502 except for within LABEL_REFs and SYMBOL_REFs. */
510 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
511 X and return it, or return 0 if none found. */
514 find_symbolic_term (x)
518 register enum rtx_code code;
522 if (code == SYMBOL_REF || code == LABEL_REF)
524 if (GET_RTX_CLASS (code) == 'o')
527 fmt = GET_RTX_FORMAT (code);
528 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
534 t = find_symbolic_term (XEXP (x, i));
538 else if (fmt[i] == 'E')
548 switch (GET_CODE (x))
551 return REG_BASE_VALUE (x);
554 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
560 return find_base_term (XEXP (x, 0));
564 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
571 rtx tmp = find_base_term (XEXP (x, 0));
574 return find_base_term (XEXP (x, 1));
578 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
579 return REG_BASE_VALUE (XEXP (x, 0));
591 /* Return 0 if the addresses X and Y are known to point to different
592 objects, 1 if they might be pointers to the same object. */
595 base_alias_check (x, y)
598 rtx x_base = find_base_term (x);
599 rtx y_base = find_base_term (y);
601 /* If the address itself has no known base see if a known equivalent
602 value has one. If either address still has no known base, nothing
603 is known about aliasing. */
607 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
609 x_base = find_base_term (x_c);
617 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
619 y_base = find_base_term (y_c);
624 /* If the base addresses are equal nothing is known about aliasing. */
625 if (rtx_equal_p (x_base, y_base))
628 /* The base addresses of the read and write are different
629 expressions. If they are both symbols and they are not accessed
630 via AND, there is no conflict. */
631 /* XXX: We can bring knowledge of object alignment and offset into
632 play here. For example, on alpha, "char a, b;" can alias one
633 another, though "char a; long b;" cannot. Similarly, offsets
634 into strutures may be brought into play. Given "char a, b[40];",
635 a and b[1] may overlap, but a and b[20] do not. */
636 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
638 return GET_CODE (x) == AND || GET_CODE (y) == AND;
641 /* If one address is a stack reference there can be no alias:
642 stack references using different base registers do not alias,
643 a stack reference can not alias a parameter, and a stack reference
644 can not alias a global. */
645 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
646 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
649 if (! flag_argument_noalias)
652 if (flag_argument_noalias > 1)
655 /* Weak noalias assertion (arguments are distinct, but may match globals). */
656 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
659 /* Return nonzero if X and Y (memory addresses) could reference the
660 same location in memory. C is an offset accumulator. When
661 C is nonzero, we are testing aliases between X and Y + C.
662 XSIZE is the size in bytes of the X reference,
663 similarly YSIZE is the size in bytes for Y.
665 If XSIZE or YSIZE is zero, we do not know the amount of memory being
666 referenced (the reference was BLKmode), so make the most pessimistic
669 If XSIZE or YSIZE is negative, we may access memory outside the object
670 being referenced as a side effect. This can happen when using AND to
671 align memory references, as is done on the Alpha.
673 Nice to notice that varying addresses cannot conflict with fp if no
674 local variables had their addresses taken, but that's too hard now. */
678 memrefs_conflict_p (xsize, x, ysize, y, c)
683 if (GET_CODE (x) == HIGH)
685 else if (GET_CODE (x) == LO_SUM)
689 if (GET_CODE (y) == HIGH)
691 else if (GET_CODE (y) == LO_SUM)
696 if (rtx_equal_for_memref_p (x, y))
698 if (xsize <= 0 || ysize <= 0)
700 if (c >= 0 && xsize > c)
702 if (c < 0 && ysize+c > 0)
707 /* This code used to check for conflicts involving stack references and
708 globals but the base address alias code now handles these cases. */
710 if (GET_CODE (x) == PLUS)
712 /* The fact that X is canonicalized means that this
713 PLUS rtx is canonicalized. */
714 rtx x0 = XEXP (x, 0);
715 rtx x1 = XEXP (x, 1);
717 if (GET_CODE (y) == PLUS)
719 /* The fact that Y is canonicalized means that this
720 PLUS rtx is canonicalized. */
721 rtx y0 = XEXP (y, 0);
722 rtx y1 = XEXP (y, 1);
724 if (rtx_equal_for_memref_p (x1, y1))
725 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
726 if (rtx_equal_for_memref_p (x0, y0))
727 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
728 if (GET_CODE (x1) == CONST_INT)
730 if (GET_CODE (y1) == CONST_INT)
731 return memrefs_conflict_p (xsize, x0, ysize, y0,
732 c - INTVAL (x1) + INTVAL (y1));
734 return memrefs_conflict_p (xsize, x0, ysize, y,
737 else if (GET_CODE (y1) == CONST_INT)
738 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
742 else if (GET_CODE (x1) == CONST_INT)
743 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
745 else if (GET_CODE (y) == PLUS)
747 /* The fact that Y is canonicalized means that this
748 PLUS rtx is canonicalized. */
749 rtx y0 = XEXP (y, 0);
750 rtx y1 = XEXP (y, 1);
752 if (GET_CODE (y1) == CONST_INT)
753 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
758 if (GET_CODE (x) == GET_CODE (y))
759 switch (GET_CODE (x))
763 /* Handle cases where we expect the second operands to be the
764 same, and check only whether the first operand would conflict
767 rtx x1 = canon_rtx (XEXP (x, 1));
768 rtx y1 = canon_rtx (XEXP (y, 1));
769 if (! rtx_equal_for_memref_p (x1, y1))
771 x0 = canon_rtx (XEXP (x, 0));
772 y0 = canon_rtx (XEXP (y, 0));
773 if (rtx_equal_for_memref_p (x0, y0))
774 return (xsize == 0 || ysize == 0
775 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
777 /* Can't properly adjust our sizes. */
778 if (GET_CODE (x1) != CONST_INT)
780 xsize /= INTVAL (x1);
781 ysize /= INTVAL (x1);
783 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
787 /* Are these registers known not to be equal? */
790 int r_x = REGNO (x), r_y = REGNO (y);
791 rtx i_x, i_y; /* invariant relationships of X and Y */
793 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
794 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
796 if (i_x == 0 && i_y == 0)
799 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
800 ysize, i_y ? i_y : y, c))
809 /* Treat an access through an AND (e.g. a subword access on an Alpha)
810 as an access with indeterminate size.
811 ??? Could instead convert an n byte reference at (and x y) to an
812 n-y byte reference at (plus x y). */
813 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
814 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
815 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
817 /* XXX: If we are indexing far enough into the array/structure, we
818 may yet be able to determine that we can not overlap. But we
819 also need to that we are far enough from the end not to overlap
820 a following reference, so we do nothing for now. */
821 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
826 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
828 c += (INTVAL (y) - INTVAL (x));
829 return (xsize <= 0 || ysize <= 0
830 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
833 if (GET_CODE (x) == CONST)
835 if (GET_CODE (y) == CONST)
836 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
837 ysize, canon_rtx (XEXP (y, 0)), c);
839 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
842 if (GET_CODE (y) == CONST)
843 return memrefs_conflict_p (xsize, x, ysize,
844 canon_rtx (XEXP (y, 0)), c);
847 return (xsize < 0 || ysize < 0
848 || (rtx_equal_for_memref_p (x, y)
849 && (xsize == 0 || ysize == 0
850 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
857 /* Functions to compute memory dependencies.
859 Since we process the insns in execution order, we can build tables
860 to keep track of what registers are fixed (and not aliased), what registers
861 are varying in known ways, and what registers are varying in unknown
864 If both memory references are volatile, then there must always be a
865 dependence between the two references, since their order can not be
866 changed. A volatile and non-volatile reference can be interchanged
869 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
870 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
871 allow QImode aliasing because the ANSI C standard allows character
872 pointers to alias anything. We are assuming that characters are
873 always QImode here. We also must allow AND addresses, because they may
874 generate accesses outside the object being referenced. This is used to
875 generate aligned addresses from unaligned addresses, for instance, the
876 alpha storeqi_unaligned pattern. */
878 /* Read dependence: X is read after read in MEM takes place. There can
879 only be a dependence here if both reads are volatile. */
882 read_dependence (mem, x)
886 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
889 /* True dependence: X is read after store in MEM takes place. */
892 true_dependence (mem, mem_mode, x, varies)
894 enum machine_mode mem_mode;
896 int (*varies) PROTO((rtx));
898 register rtx x_addr, mem_addr;
900 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
903 if (DIFFERENT_ALIAS_SETS_P (x, mem))
906 /* If X is an unchanging read, then it can't possibly conflict with any
907 non-unchanging store. It may conflict with an unchanging write though,
908 because there may be a single store to this address to initialize it.
909 Just fall through to the code below to resolve the case where we have
910 both an unchanging read and an unchanging write. This won't handle all
911 cases optimally, but the possible performance loss should be
913 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
916 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
919 x_addr = canon_rtx (XEXP (x, 0));
920 mem_addr = canon_rtx (XEXP (mem, 0));
922 if (mem_mode == VOIDmode)
923 mem_mode = GET_MODE (mem);
925 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
926 SIZE_FOR_MODE (x), x_addr, 0))
929 /* If both references are struct references, or both are not, nothing
930 is known about aliasing.
932 If either reference is QImode or BLKmode, ANSI C permits aliasing.
934 If both addresses are constant, or both are not, nothing is known
936 if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
937 || mem_mode == QImode || mem_mode == BLKmode
938 || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
939 || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
940 || varies (x_addr) == varies (mem_addr))
943 /* One memory reference is to a constant address, one is not.
944 One is to a structure, the other is not.
946 If either memory reference is a variable structure the other is a
947 fixed scalar and there is no aliasing. */
948 if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
949 || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
955 /* Anti dependence: X is written after read in MEM takes place. */
958 anti_dependence (mem, x)
962 rtx x_addr, mem_addr;
964 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
967 /* If MEM is an unchanging read, then it can't possibly conflict with
968 the store to X, because there is at most one store to MEM, and it must
969 have occurred somewhere before MEM. */
970 if (RTX_UNCHANGING_P (mem))
973 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
977 mem = canon_rtx (mem);
979 if (DIFFERENT_ALIAS_SETS_P (x, mem))
982 x_addr = XEXP (x, 0);
983 mem_addr = XEXP (mem, 0);
985 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
986 SIZE_FOR_MODE (x), x_addr, 0)
987 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
988 && GET_MODE (mem) != QImode
989 && GET_CODE (mem_addr) != AND
990 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
991 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
992 && GET_MODE (x) != QImode
993 && GET_CODE (x_addr) != AND
994 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
997 /* Output dependence: X is written after store in MEM takes place. */
1000 output_dependence (mem, x)
1004 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1007 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
1011 mem = canon_rtx (mem);
1013 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1016 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
1017 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
1018 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
1019 && GET_MODE (mem) != QImode
1020 && GET_CODE (XEXP (mem, 0)) != AND
1021 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
1022 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
1023 && GET_MODE (x) != QImode
1024 && GET_CODE (XEXP (x, 0)) != AND
1025 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
1029 static HARD_REG_SET argument_registers;
1036 #ifndef OUTGOING_REGNO
1037 #define OUTGOING_REGNO(N) N
1039 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1040 /* Check whether this register can hold an incoming pointer
1041 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1042 numbers, so translate if necessary due to register windows. */
1043 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1044 && HARD_REGNO_MODE_OK (i, Pmode))
1045 SET_HARD_REG_BIT (argument_registers, i);
1049 init_alias_analysis ()
1051 int maxreg = max_reg_num ();
1056 reg_known_value_size = maxreg;
1059 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1060 - FIRST_PSEUDO_REGISTER;
1062 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1063 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1064 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1065 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1066 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1068 /* Overallocate reg_base_value to allow some growth during loop
1069 optimization. Loop unrolling can create a large number of
1071 reg_base_value_size = maxreg * 2;
1072 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1073 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1074 reg_seen = (char *)alloca (reg_base_value_size);
1075 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1076 if (! reload_completed && flag_unroll_loops)
1078 alias_invariant = (rtx *)xrealloc (alias_invariant,
1079 reg_base_value_size * sizeof (rtx));
1080 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1084 /* The basic idea is that each pass through this loop will use the
1085 "constant" information from the previous pass to propagate alias
1086 information through another level of assignments.
1088 This could get expensive if the assignment chains are long. Maybe
1089 we should throttle the number of iterations, possibly based on
1090 the optimization level or flag_expensive_optimizations.
1092 We could propagate more information in the first pass by making use
1093 of REG_N_SETS to determine immediately that the alias information
1094 for a pseudo is "constant".
1096 A program with an uninitialized variable can cause an infinite loop
1097 here. Instead of doing a full dataflow analysis to detect such problems
1098 we just cap the number of iterations for the loop.
1100 The state of the arrays for the set chain in question does not matter
1101 since the program has undefined behavior. */
1106 /* Assume nothing will change this iteration of the loop. */
1109 /* We want to assign the same IDs each iteration of this loop, so
1110 start counting from zero each iteration of the loop. */
1113 /* We're at the start of the funtion each iteration through the
1114 loop, so we're copying arguments. */
1115 copying_arguments = 1;
1117 /* Wipe the potential alias information clean for this pass. */
1118 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1120 /* Wipe the reg_seen array clean. */
1121 bzero ((char *) reg_seen, reg_base_value_size);
1123 /* Mark all hard registers which may contain an address.
1124 The stack, frame and argument pointers may contain an address.
1125 An argument register which can hold a Pmode value may contain
1126 an address even if it is not in BASE_REGS.
1128 The address expression is VOIDmode for an argument and
1129 Pmode for other registers. */
1131 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1132 if (TEST_HARD_REG_BIT (argument_registers, i))
1133 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1134 gen_rtx_REG (Pmode, i));
1136 new_reg_base_value[STACK_POINTER_REGNUM]
1137 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1138 new_reg_base_value[ARG_POINTER_REGNUM]
1139 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1140 new_reg_base_value[FRAME_POINTER_REGNUM]
1141 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1142 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1143 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1144 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1146 if (struct_value_incoming_rtx
1147 && GET_CODE (struct_value_incoming_rtx) == REG)
1148 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1149 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1151 if (static_chain_rtx
1152 && GET_CODE (static_chain_rtx) == REG)
1153 new_reg_base_value[REGNO (static_chain_rtx)]
1154 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1156 /* Walk the insns adding values to the new_reg_base_value array. */
1157 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1159 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1162 /* If this insn has a noalias note, process it, Otherwise,
1163 scan for sets. A simple set will have no side effects
1164 which could change the base value of any other register. */
1166 if (GET_CODE (PATTERN (insn)) == SET
1167 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1168 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1170 note_stores (PATTERN (insn), record_set);
1172 set = single_set (insn);
1175 && GET_CODE (SET_DEST (set)) == REG
1176 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1177 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1178 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1179 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1180 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1182 int regno = REGNO (SET_DEST (set));
1183 reg_known_value[regno] = XEXP (note, 0);
1184 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1187 else if (GET_CODE (insn) == NOTE
1188 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1189 copying_arguments = 0;
1192 /* Now propagate values from new_reg_base_value to reg_base_value. */
1193 for (i = 0; i < reg_base_value_size; i++)
1195 if (new_reg_base_value[i]
1196 && new_reg_base_value[i] != reg_base_value[i]
1197 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1199 reg_base_value[i] = new_reg_base_value[i];
1204 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1206 /* Fill in the remaining entries. */
1207 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1208 if (reg_known_value[i] == 0)
1209 reg_known_value[i] = regno_reg_rtx[i];
1211 /* Simplify the reg_base_value array so that no register refers to
1212 another register, except to special registers indirectly through
1213 ADDRESS expressions.
1215 In theory this loop can take as long as O(registers^2), but unless
1216 there are very long dependency chains it will run in close to linear
1219 This loop may not be needed any longer now that the main loop does
1220 a better job at propagating alias information. */
1226 for (i = 0; i < reg_base_value_size; i++)
1228 rtx base = reg_base_value[i];
1229 if (base && GET_CODE (base) == REG)
1231 int base_regno = REGNO (base);
1232 if (base_regno == i) /* register set from itself */
1233 reg_base_value[i] = 0;
1235 reg_base_value[i] = reg_base_value[base_regno];
1240 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1242 new_reg_base_value = 0;
1247 end_alias_analysis ()
1249 reg_known_value = 0;
1251 reg_base_value_size = 0;
1252 if (alias_invariant)
1254 free ((char *)alias_invariant);
1255 alias_invariant = 0;