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"
30 static rtx canon_rtx PROTO((rtx));
31 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
32 static rtx find_symbolic_term PROTO((rtx));
33 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
35 static void record_set PROTO((rtx, rtx));
36 static rtx find_base_term PROTO((rtx));
37 static int base_alias_check PROTO((rtx, rtx));
38 static rtx find_base_value PROTO((rtx));
40 /* Set up all info needed to perform alias analysis on memory references. */
42 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
44 /* Cap the number of passes we make over the insns propagating alias
45 information through set chains.
47 10 is a completely arbitrary choice. */
48 #define MAX_ALIAS_LOOP_PASSES 10
50 /* reg_base_value[N] gives an address to which register N is related.
51 If all sets after the first add or subtract to the current value
52 or otherwise modify it so it does not point to a different top level
53 object, reg_base_value[N] is equal to the address part of the source
56 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
57 expressions represent certain special values: function arguments and
58 the stack, frame, and argument pointers. The contents of an address
59 expression are not used (but they are descriptive for debugging);
60 only the address and mode matter. Pointer equality, not rtx_equal_p,
61 determines whether two ADDRESS expressions refer to the same base
62 address. The mode determines whether it is a function argument or
63 other special value. */
66 rtx *new_reg_base_value;
67 unsigned int reg_base_value_size; /* size of reg_base_value array */
68 #define REG_BASE_VALUE(X) \
69 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
71 /* Vector of known invariant relationships between registers. Set in
72 loop unrolling. Indexed by register number, if nonzero the value
73 is an expression describing this register in terms of another.
75 The length of this array is REG_BASE_VALUE_SIZE.
77 Because this array contains only pseudo registers it has no effect
79 static rtx *alias_invariant;
81 /* Vector indexed by N giving the initial (unchanging) value known
82 for pseudo-register N. */
85 /* Indicates number of valid entries in reg_known_value. */
86 static int reg_known_value_size;
88 /* Vector recording for each reg_known_value whether it is due to a
89 REG_EQUIV note. Future passes (viz., reload) may replace the
90 pseudo with the equivalent expression and so we account for the
91 dependences that would be introduced if that happens. */
92 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
93 assign_parms mention the arg pointer, and there are explicit insns in the
94 RTL that modify the arg pointer. Thus we must ensure that such insns don't
95 get scheduled across each other because that would invalidate the REG_EQUIV
96 notes. One could argue that the REG_EQUIV notes are wrong, but solving
97 the problem in the scheduler will likely give better code, so we do it
99 char *reg_known_equiv_p;
101 /* True when scanning insns from the start of the rtl to the
102 NOTE_INSN_FUNCTION_BEG note. */
104 static int copying_arguments;
106 /* Inside SRC, the source of a SET, find a base address. */
109 find_base_value (src)
112 switch (GET_CODE (src))
119 /* At the start of a function argument registers have known base
120 values which may be lost later. Returning an ADDRESS
121 expression here allows optimization based on argument values
122 even when the argument registers are used for other purposes. */
123 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
124 return new_reg_base_value[REGNO (src)];
126 /* If a pseudo has a known base value, return it. Do not do this
127 for hard regs since it can result in a circular dependency
128 chain for registers which have values at function entry.
130 The test above is not sufficient because the scheduler may move
131 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
132 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
133 && REGNO (src) < reg_base_value_size
134 && reg_base_value[REGNO (src)])
135 return reg_base_value[REGNO (src)];
140 /* Check for an argument passed in memory. Only record in the
141 copying-arguments block; it is too hard to track changes
143 if (copying_arguments
144 && (XEXP (src, 0) == arg_pointer_rtx
145 || (GET_CODE (XEXP (src, 0)) == PLUS
146 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
147 return gen_rtx_ADDRESS (VOIDmode, src);
152 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
159 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
161 /* If either operand is a REG, then see if we already have
162 a known value for it. */
163 if (GET_CODE (src_0) == REG)
165 temp = find_base_value (src_0);
170 if (GET_CODE (src_1) == REG)
172 temp = find_base_value (src_1);
177 /* Guess which operand is the base address.
179 If either operand is a symbol, then it is the base. If
180 either operand is a CONST_INT, then the other is the base. */
182 if (GET_CODE (src_1) == CONST_INT
183 || GET_CODE (src_0) == SYMBOL_REF
184 || GET_CODE (src_0) == LABEL_REF
185 || GET_CODE (src_0) == CONST)
186 return find_base_value (src_0);
188 if (GET_CODE (src_0) == CONST_INT
189 || GET_CODE (src_1) == SYMBOL_REF
190 || GET_CODE (src_1) == LABEL_REF
191 || GET_CODE (src_1) == CONST)
192 return find_base_value (src_1);
194 /* This might not be necessary anymore.
196 If either operand is a REG that is a known pointer, then it
198 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
199 return find_base_value (src_0);
201 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
202 return find_base_value (src_1);
208 /* The standard form is (lo_sum reg sym) so look only at the
210 return find_base_value (XEXP (src, 1));
213 /* If the second operand is constant set the base
214 address to the first operand. */
215 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
216 return find_base_value (XEXP (src, 0));
220 case SIGN_EXTEND: /* used for NT/Alpha pointers */
222 return find_base_value (XEXP (src, 0));
231 /* Called from init_alias_analysis indirectly through note_stores. */
233 /* while scanning insns to find base values, reg_seen[N] is nonzero if
234 register N has been set in this function. */
235 static char *reg_seen;
237 /* Addresses which are known not to alias anything else are identified
238 by a unique integer. */
239 static int unique_id;
242 record_set (dest, set)
248 if (GET_CODE (dest) != REG)
251 regno = REGNO (dest);
255 /* A CLOBBER wipes out any old value but does not prevent a previously
256 unset register from acquiring a base address (i.e. reg_seen is not
258 if (GET_CODE (set) == CLOBBER)
260 new_reg_base_value[regno] = 0;
269 new_reg_base_value[regno] = 0;
273 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
274 GEN_INT (unique_id++));
278 /* This is not the first set. If the new value is not related to the
279 old value, forget the base value. Note that the following code is
281 extern int x, y; int *p = &x; p += (&y-&x);
282 ANSI C does not allow computing the difference of addresses
283 of distinct top level objects. */
284 if (new_reg_base_value[regno])
285 switch (GET_CODE (src))
290 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
291 new_reg_base_value[regno] = 0;
294 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
295 new_reg_base_value[regno] = 0;
298 new_reg_base_value[regno] = 0;
301 /* If this is the first set of a register, record the value. */
302 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
303 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
304 new_reg_base_value[regno] = find_base_value (src);
309 /* Called from loop optimization when a new pseudo-register is created. */
311 record_base_value (regno, val, invariant)
316 if (regno >= reg_base_value_size)
319 /* If INVARIANT is true then this value also describes an invariant
320 relationship which can be used to deduce that two registers with
321 unknown values are different. */
322 if (invariant && alias_invariant)
323 alias_invariant[regno] = val;
325 if (GET_CODE (val) == REG)
327 if (REGNO (val) < reg_base_value_size)
329 reg_base_value[regno] = reg_base_value[REGNO (val)];
333 reg_base_value[regno] = find_base_value (val);
340 /* Recursively look for equivalences. */
341 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
342 && REGNO (x) < reg_known_value_size)
343 return reg_known_value[REGNO (x)] == x
344 ? x : canon_rtx (reg_known_value[REGNO (x)]);
345 else if (GET_CODE (x) == PLUS)
347 rtx x0 = canon_rtx (XEXP (x, 0));
348 rtx x1 = canon_rtx (XEXP (x, 1));
350 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
352 /* We can tolerate LO_SUMs being offset here; these
353 rtl are used for nothing other than comparisons. */
354 if (GET_CODE (x0) == CONST_INT)
355 return plus_constant_for_output (x1, INTVAL (x0));
356 else if (GET_CODE (x1) == CONST_INT)
357 return plus_constant_for_output (x0, INTVAL (x1));
358 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
361 /* This gives us much better alias analysis when called from
362 the loop optimizer. Note we want to leave the original
363 MEM alone, but need to return the canonicalized MEM with
364 all the flags with their original values. */
365 else if (GET_CODE (x) == MEM)
367 rtx addr = canon_rtx (XEXP (x, 0));
368 if (addr != XEXP (x, 0))
370 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
371 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
372 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
373 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
380 /* Return 1 if X and Y are identical-looking rtx's.
382 We use the data in reg_known_value above to see if two registers with
383 different numbers are, in fact, equivalent. */
386 rtx_equal_for_memref_p (x, y)
391 register enum rtx_code code;
394 if (x == 0 && y == 0)
396 if (x == 0 || y == 0)
405 /* Rtx's of different codes cannot be equal. */
406 if (code != GET_CODE (y))
409 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
410 (REG:SI x) and (REG:HI x) are NOT equivalent. */
412 if (GET_MODE (x) != GET_MODE (y))
415 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
418 return REGNO (x) == REGNO (y);
419 if (code == LABEL_REF)
420 return XEXP (x, 0) == XEXP (y, 0);
421 if (code == SYMBOL_REF)
422 return XSTR (x, 0) == XSTR (y, 0);
423 if (code == CONST_INT)
424 return INTVAL (x) == INTVAL (y);
425 if (code == ADDRESSOF)
426 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
428 /* For commutative operations, the RTX match if the operand match in any
429 order. Also handle the simple binary and unary cases without a loop. */
430 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
431 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
432 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
433 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
434 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
435 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
436 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
437 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
438 else if (GET_RTX_CLASS (code) == '1')
439 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
441 /* Compare the elements. If any pair of corresponding elements
442 fail to match, return 0 for the whole things.
444 Limit cases to types which actually appear in addresses. */
446 fmt = GET_RTX_FORMAT (code);
447 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
452 if (XINT (x, i) != XINT (y, i))
457 /* Two vectors must have the same length. */
458 if (XVECLEN (x, i) != XVECLEN (y, i))
461 /* And the corresponding elements must match. */
462 for (j = 0; j < XVECLEN (x, i); j++)
463 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
468 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
472 /* This can happen for an asm which clobbers memory. */
476 /* It is believed that rtx's at this level will never
477 contain anything but integers and other rtx's,
478 except for within LABEL_REFs and SYMBOL_REFs. */
486 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
487 X and return it, or return 0 if none found. */
490 find_symbolic_term (x)
494 register enum rtx_code code;
498 if (code == SYMBOL_REF || code == LABEL_REF)
500 if (GET_RTX_CLASS (code) == 'o')
503 fmt = GET_RTX_FORMAT (code);
504 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
510 t = find_symbolic_term (XEXP (x, i));
514 else if (fmt[i] == 'E')
524 switch (GET_CODE (x))
527 return REG_BASE_VALUE (x);
530 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
536 return find_base_term (XEXP (x, 0));
540 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
547 rtx tmp = find_base_term (XEXP (x, 0));
550 return find_base_term (XEXP (x, 1));
554 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
555 return REG_BASE_VALUE (XEXP (x, 0));
567 /* Return 0 if the addresses X and Y are known to point to different
568 objects, 1 if they might be pointers to the same object. */
571 base_alias_check (x, y)
574 rtx x_base = find_base_term (x);
575 rtx y_base = find_base_term (y);
577 /* If the address itself has no known base see if a known equivalent
578 value has one. If either address still has no known base, nothing
579 is known about aliasing. */
583 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
585 x_base = find_base_term (x_c);
593 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
595 y_base = find_base_term (y_c);
600 /* If the base addresses are equal nothing is known about aliasing. */
601 if (rtx_equal_p (x_base, y_base))
604 /* The base addresses of the read and write are different
605 expressions. If they are both symbols and they are not accessed
606 via AND, there is no conflict. */
607 /* XXX: We can bring knowledge of object alignment and offset into
608 play here. For example, on alpha, "char a, b;" can alias one
609 another, though "char a; long b;" cannot. Similarly, offsets
610 into strutures may be brought into play. Given "char a, b[40];",
611 a and b[1] may overlap, but a and b[20] do not. */
612 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
614 return GET_CODE (x) == AND || GET_CODE (y) == AND;
617 /* If one address is a stack reference there can be no alias:
618 stack references using different base registers do not alias,
619 a stack reference can not alias a parameter, and a stack reference
620 can not alias a global. */
621 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
622 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
625 if (! flag_argument_noalias)
628 if (flag_argument_noalias > 1)
631 /* Weak noalias assertion (arguments are distinct, but may match globals). */
632 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
635 /* Return nonzero if X and Y (memory addresses) could reference the
636 same location in memory. C is an offset accumulator. When
637 C is nonzero, we are testing aliases between X and Y + C.
638 XSIZE is the size in bytes of the X reference,
639 similarly YSIZE is the size in bytes for Y.
641 If XSIZE or YSIZE is zero, we do not know the amount of memory being
642 referenced (the reference was BLKmode), so make the most pessimistic
645 If XSIZE or YSIZE is negative, we may access memory outside the object
646 being referenced as a side effect. This can happen when using AND to
647 align memory references, as is done on the Alpha.
649 Nice to notice that varying addresses cannot conflict with fp if no
650 local variables had their addresses taken, but that's too hard now. */
654 memrefs_conflict_p (xsize, x, ysize, y, c)
659 if (GET_CODE (x) == HIGH)
661 else if (GET_CODE (x) == LO_SUM)
665 if (GET_CODE (y) == HIGH)
667 else if (GET_CODE (y) == LO_SUM)
672 if (rtx_equal_for_memref_p (x, y))
674 if (xsize <= 0 || ysize <= 0)
676 if (c >= 0 && xsize > c)
678 if (c < 0 && ysize+c > 0)
683 /* This code used to check for conflicts involving stack references and
684 globals but the base address alias code now handles these cases. */
686 if (GET_CODE (x) == PLUS)
688 /* The fact that X is canonicalized means that this
689 PLUS rtx is canonicalized. */
690 rtx x0 = XEXP (x, 0);
691 rtx x1 = XEXP (x, 1);
693 if (GET_CODE (y) == PLUS)
695 /* The fact that Y is canonicalized means that this
696 PLUS rtx is canonicalized. */
697 rtx y0 = XEXP (y, 0);
698 rtx y1 = XEXP (y, 1);
700 if (rtx_equal_for_memref_p (x1, y1))
701 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
702 if (rtx_equal_for_memref_p (x0, y0))
703 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
704 if (GET_CODE (x1) == CONST_INT)
705 if (GET_CODE (y1) == CONST_INT)
706 return memrefs_conflict_p (xsize, x0, ysize, y0,
707 c - INTVAL (x1) + INTVAL (y1));
709 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
710 else if (GET_CODE (y1) == CONST_INT)
711 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
715 else if (GET_CODE (x1) == CONST_INT)
716 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
718 else if (GET_CODE (y) == PLUS)
720 /* The fact that Y is canonicalized means that this
721 PLUS rtx is canonicalized. */
722 rtx y0 = XEXP (y, 0);
723 rtx y1 = XEXP (y, 1);
725 if (GET_CODE (y1) == CONST_INT)
726 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
731 if (GET_CODE (x) == GET_CODE (y))
732 switch (GET_CODE (x))
736 /* Handle cases where we expect the second operands to be the
737 same, and check only whether the first operand would conflict
740 rtx x1 = canon_rtx (XEXP (x, 1));
741 rtx y1 = canon_rtx (XEXP (y, 1));
742 if (! rtx_equal_for_memref_p (x1, y1))
744 x0 = canon_rtx (XEXP (x, 0));
745 y0 = canon_rtx (XEXP (y, 0));
746 if (rtx_equal_for_memref_p (x0, y0))
747 return (xsize == 0 || ysize == 0
748 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
750 /* Can't properly adjust our sizes. */
751 if (GET_CODE (x1) != CONST_INT)
753 xsize /= INTVAL (x1);
754 ysize /= INTVAL (x1);
756 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
760 /* Are these registers known not to be equal? */
763 int r_x = REGNO (x), r_y = REGNO (y);
764 rtx i_x, i_y; /* invariant relationships of X and Y */
766 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
767 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
769 if (i_x == 0 && i_y == 0)
772 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
773 ysize, i_y ? i_y : y, c))
782 /* Treat an access through an AND (e.g. a subword access on an Alpha)
783 as an access with indeterminate size.
784 ??? Could instead convert an n byte reference at (and x y) to an
785 n-y byte reference at (plus x y). */
786 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
787 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
788 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
790 /* XXX: If we are indexing far enough into the array/structure, we
791 may yet be able to determine that we can not overlap. But we
792 also need to that we are far enough from the end not to overlap
793 a following reference, so we do nothing for now. */
794 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
799 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
801 c += (INTVAL (y) - INTVAL (x));
802 return (xsize <= 0 || ysize <= 0
803 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
806 if (GET_CODE (x) == CONST)
808 if (GET_CODE (y) == CONST)
809 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
810 ysize, canon_rtx (XEXP (y, 0)), c);
812 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
815 if (GET_CODE (y) == CONST)
816 return memrefs_conflict_p (xsize, x, ysize,
817 canon_rtx (XEXP (y, 0)), c);
820 return (xsize < 0 || ysize < 0
821 || (rtx_equal_for_memref_p (x, y)
822 && (xsize == 0 || ysize == 0
823 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
830 /* Functions to compute memory dependencies.
832 Since we process the insns in execution order, we can build tables
833 to keep track of what registers are fixed (and not aliased), what registers
834 are varying in known ways, and what registers are varying in unknown
837 If both memory references are volatile, then there must always be a
838 dependence between the two references, since their order can not be
839 changed. A volatile and non-volatile reference can be interchanged
842 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
843 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
844 allow QImode aliasing because the ANSI C standard allows character
845 pointers to alias anything. We are assuming that characters are
846 always QImode here. We also must allow AND addresses, because they may
847 generate accesses outside the object being referenced. This is used to
848 generate aligned addresses from unaligned addresses, for instance, the
849 alpha storeqi_unaligned pattern. */
851 /* Read dependence: X is read after read in MEM takes place. There can
852 only be a dependence here if both reads are volatile. */
855 read_dependence (mem, x)
859 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
862 /* True dependence: X is read after store in MEM takes place. */
865 true_dependence (mem, mem_mode, x, varies)
867 enum machine_mode mem_mode;
869 int (*varies) PROTO((rtx));
871 register rtx x_addr, mem_addr;
873 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
876 /* If X is an unchanging read, then it can't possibly conflict with any
877 non-unchanging store. It may conflict with an unchanging write though,
878 because there may be a single store to this address to initialize it.
879 Just fall through to the code below to resolve the case where we have
880 both an unchanging read and an unchanging write. This won't handle all
881 cases optimally, but the possible performance loss should be
883 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
886 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
889 x_addr = canon_rtx (XEXP (x, 0));
890 mem_addr = canon_rtx (XEXP (mem, 0));
892 if (mem_mode == VOIDmode)
893 mem_mode = GET_MODE (mem);
895 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
896 SIZE_FOR_MODE (x), x_addr, 0))
899 /* If both references are struct references, or both are not, nothing
900 is known about aliasing.
902 If either reference is QImode or BLKmode, ANSI C permits aliasing.
904 If both addresses are constant, or both are not, nothing is known
906 if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
907 || mem_mode == QImode || mem_mode == BLKmode
908 || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
909 || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
910 || varies (x_addr) == varies (mem_addr))
913 /* One memory reference is to a constant address, one is not.
914 One is to a structure, the other is not.
916 If either memory reference is a variable structure the other is a
917 fixed scalar and there is no aliasing. */
918 if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
919 || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
925 /* Anti dependence: X is written after read in MEM takes place. */
928 anti_dependence (mem, x)
932 rtx x_addr, mem_addr;
934 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
937 /* If MEM is an unchanging read, then it can't possibly conflict with
938 the store to X, because there is at most one store to MEM, and it must
939 have occurred somewhere before MEM. */
940 if (RTX_UNCHANGING_P (mem))
943 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
947 mem = canon_rtx (mem);
949 x_addr = XEXP (x, 0);
950 mem_addr = XEXP (mem, 0);
952 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
953 SIZE_FOR_MODE (x), x_addr, 0)
954 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
955 && GET_MODE (mem) != QImode
956 && GET_CODE (mem_addr) != AND
957 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
958 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
959 && GET_MODE (x) != QImode
960 && GET_CODE (x_addr) != AND
961 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
964 /* Output dependence: X is written after store in MEM takes place. */
967 output_dependence (mem, x)
971 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
974 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
978 mem = canon_rtx (mem);
980 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
981 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
982 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
983 && GET_MODE (mem) != QImode
984 && GET_CODE (XEXP (mem, 0)) != AND
985 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
986 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
987 && GET_MODE (x) != QImode
988 && GET_CODE (XEXP (x, 0)) != AND
989 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
993 static HARD_REG_SET argument_registers;
1000 #ifndef OUTGOING_REGNO
1001 #define OUTGOING_REGNO(N) N
1003 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1004 /* Check whether this register can hold an incoming pointer
1005 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1006 numbers, so translate if necessary due to register windows. */
1007 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1008 && HARD_REGNO_MODE_OK (i, Pmode))
1009 SET_HARD_REG_BIT (argument_registers, i);
1013 init_alias_analysis ()
1015 int maxreg = max_reg_num ();
1020 reg_known_value_size = maxreg;
1023 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1024 - FIRST_PSEUDO_REGISTER;
1026 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1027 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1028 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1029 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1030 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1032 /* Overallocate reg_base_value to allow some growth during loop
1033 optimization. Loop unrolling can create a large number of
1035 reg_base_value_size = maxreg * 2;
1036 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1037 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1038 reg_seen = (char *)alloca (reg_base_value_size);
1039 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1040 if (! reload_completed && flag_unroll_loops)
1042 alias_invariant = (rtx *)xrealloc (alias_invariant,
1043 reg_base_value_size * sizeof (rtx));
1044 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1048 /* The basic idea is that each pass through this loop will use the
1049 "constant" information from the previous pass to propagate alias
1050 information through another level of assignments.
1052 This could get expensive if the assignment chains are long. Maybe
1053 we should throttle the number of iterations, possibly based on
1054 the optimization level or flag_expensive_optimizations.
1056 We could propagate more information in the first pass by making use
1057 of REG_N_SETS to determine immediately that the alias information
1058 for a pseudo is "constant".
1060 A program with an uninitialized variable can cause an infinite loop
1061 here. Instead of doing a full dataflow analysis to detect such problems
1062 we just cap the number of iterations for the loop.
1064 The state of the arrays for the set chain in question does not matter
1065 since the program has undefined behavior. */
1070 /* Assume nothing will change this iteration of the loop. */
1073 /* We want to assign the same IDs each iteration of this loop, so
1074 start counting from zero each iteration of the loop. */
1077 /* We're at the start of the funtion each iteration through the
1078 loop, so we're copying arguments. */
1079 copying_arguments = 1;
1081 /* Wipe the potential alias information clean for this pass. */
1082 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1084 /* Wipe the reg_seen array clean. */
1085 bzero ((char *) reg_seen, reg_base_value_size);
1087 /* Mark all hard registers which may contain an address.
1088 The stack, frame and argument pointers may contain an address.
1089 An argument register which can hold a Pmode value may contain
1090 an address even if it is not in BASE_REGS.
1092 The address expression is VOIDmode for an argument and
1093 Pmode for other registers. */
1095 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1096 if (TEST_HARD_REG_BIT (argument_registers, i))
1097 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1098 gen_rtx_REG (Pmode, i));
1100 new_reg_base_value[STACK_POINTER_REGNUM]
1101 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1102 new_reg_base_value[ARG_POINTER_REGNUM]
1103 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1104 new_reg_base_value[FRAME_POINTER_REGNUM]
1105 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1106 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1107 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1108 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1110 if (struct_value_incoming_rtx
1111 && GET_CODE (struct_value_incoming_rtx) == REG)
1112 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1113 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1115 if (static_chain_rtx
1116 && GET_CODE (static_chain_rtx) == REG)
1117 new_reg_base_value[REGNO (static_chain_rtx)]
1118 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1120 /* Walk the insns adding values to the new_reg_base_value array. */
1121 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1123 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1126 /* If this insn has a noalias note, process it, Otherwise,
1127 scan for sets. A simple set will have no side effects
1128 which could change the base value of any other register. */
1130 if (GET_CODE (PATTERN (insn)) == SET
1131 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1132 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1134 note_stores (PATTERN (insn), record_set);
1136 set = single_set (insn);
1139 && GET_CODE (SET_DEST (set)) == REG
1140 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1141 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1142 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1143 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1144 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1146 int regno = REGNO (SET_DEST (set));
1147 reg_known_value[regno] = XEXP (note, 0);
1148 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1151 else if (GET_CODE (insn) == NOTE
1152 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1153 copying_arguments = 0;
1156 /* Now propagate values from new_reg_base_value to reg_base_value. */
1157 for (i = 0; i < reg_base_value_size; i++)
1159 if (new_reg_base_value[i]
1160 && new_reg_base_value[i] != reg_base_value[i]
1161 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1163 reg_base_value[i] = new_reg_base_value[i];
1168 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1170 /* Fill in the remaining entries. */
1171 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1172 if (reg_known_value[i] == 0)
1173 reg_known_value[i] = regno_reg_rtx[i];
1175 /* Simplify the reg_base_value array so that no register refers to
1176 another register, except to special registers indirectly through
1177 ADDRESS expressions.
1179 In theory this loop can take as long as O(registers^2), but unless
1180 there are very long dependency chains it will run in close to linear
1183 This loop may not be needed any longer now that the main loop does
1184 a better job at propagating alias information. */
1190 for (i = 0; i < reg_base_value_size; i++)
1192 rtx base = reg_base_value[i];
1193 if (base && GET_CODE (base) == REG)
1195 int base_regno = REGNO (base);
1196 if (base_regno == i) /* register set from itself */
1197 reg_base_value[i] = 0;
1199 reg_base_value[i] = reg_base_value[base_regno];
1204 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1206 new_reg_base_value = 0;
1211 end_alias_analysis ()
1213 reg_known_value = 0;
1215 reg_base_value_size = 0;
1216 if (alias_invariant)
1218 free ((char *)alias_invariant);
1219 alias_invariant = 0;