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 int mode_alias_check PROTO((rtx, rtx, int (*)(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 && reg_base_value[REGNO (src)])
134 return reg_base_value[REGNO (src)];
139 /* Check for an argument passed in memory. Only record in the
140 copying-arguments block; it is too hard to track changes
142 if (copying_arguments
143 && (XEXP (src, 0) == arg_pointer_rtx
144 || (GET_CODE (XEXP (src, 0)) == PLUS
145 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
146 return gen_rtx_ADDRESS (VOIDmode, src);
151 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
158 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
160 /* If either operand is a REG, then see if we already have
161 a known value for it. */
162 if (GET_CODE (src_0) == REG)
164 temp = find_base_value (src_0);
169 if (GET_CODE (src_1) == REG)
171 temp = find_base_value (src_1);
176 /* Guess which operand is the base address.
178 If either operand is a symbol, then it is the base. If
179 either operand is a CONST_INT, then the other is the base. */
181 if (GET_CODE (src_1) == CONST_INT
182 || GET_CODE (src_0) == SYMBOL_REF
183 || GET_CODE (src_0) == LABEL_REF
184 || GET_CODE (src_0) == CONST)
185 return find_base_value (src_0);
187 if (GET_CODE (src_0) == CONST_INT
188 || GET_CODE (src_1) == SYMBOL_REF
189 || GET_CODE (src_1) == LABEL_REF
190 || GET_CODE (src_1) == CONST)
191 return find_base_value (src_1);
193 /* This might not be necessary anymore.
195 If either operand is a REG that is a known pointer, then it
197 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
198 return find_base_value (src_0);
200 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
201 return find_base_value (src_1);
207 /* The standard form is (lo_sum reg sym) so look only at the
209 return find_base_value (XEXP (src, 1));
212 /* If the second operand is constant set the base
213 address to the first operand. */
214 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
215 return find_base_value (XEXP (src, 0));
219 case SIGN_EXTEND: /* used for NT/Alpha pointers */
221 return find_base_value (XEXP (src, 0));
230 /* Called from init_alias_analysis indirectly through note_stores. */
232 /* while scanning insns to find base values, reg_seen[N] is nonzero if
233 register N has been set in this function. */
234 static char *reg_seen;
236 /* Addresses which are known not to alias anything else are identified
237 by a unique integer. */
238 static int unique_id;
241 record_set (dest, set)
247 if (GET_CODE (dest) != REG)
250 regno = REGNO (dest);
254 /* A CLOBBER wipes out any old value but does not prevent a previously
255 unset register from acquiring a base address (i.e. reg_seen is not
257 if (GET_CODE (set) == CLOBBER)
259 new_reg_base_value[regno] = 0;
268 new_reg_base_value[regno] = 0;
272 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
273 GEN_INT (unique_id++));
277 /* This is not the first set. If the new value is not related to the
278 old value, forget the base value. Note that the following code is
280 extern int x, y; int *p = &x; p += (&y-&x);
281 ANSI C does not allow computing the difference of addresses
282 of distinct top level objects. */
283 if (new_reg_base_value[regno])
284 switch (GET_CODE (src))
289 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
290 new_reg_base_value[regno] = 0;
293 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
294 new_reg_base_value[regno] = 0;
297 new_reg_base_value[regno] = 0;
300 /* If this is the first set of a register, record the value. */
301 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
302 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
303 new_reg_base_value[regno] = find_base_value (src);
308 /* Called from loop optimization when a new pseudo-register is created. */
310 record_base_value (regno, val, invariant)
315 if (regno >= reg_base_value_size)
318 /* If INVARIANT is true then this value also describes an invariant
319 relationship which can be used to deduce that two registers with
320 unknown values are different. */
321 if (invariant && alias_invariant)
322 alias_invariant[regno] = val;
324 if (GET_CODE (val) == REG)
326 if (REGNO (val) < reg_base_value_size)
328 reg_base_value[regno] = reg_base_value[REGNO (val)];
332 reg_base_value[regno] = find_base_value (val);
339 /* Recursively look for equivalences. */
340 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
341 && REGNO (x) < reg_known_value_size)
342 return reg_known_value[REGNO (x)] == x
343 ? x : canon_rtx (reg_known_value[REGNO (x)]);
344 else if (GET_CODE (x) == PLUS)
346 rtx x0 = canon_rtx (XEXP (x, 0));
347 rtx x1 = canon_rtx (XEXP (x, 1));
349 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
351 /* We can tolerate LO_SUMs being offset here; these
352 rtl are used for nothing other than comparisons. */
353 if (GET_CODE (x0) == CONST_INT)
354 return plus_constant_for_output (x1, INTVAL (x0));
355 else if (GET_CODE (x1) == CONST_INT)
356 return plus_constant_for_output (x0, INTVAL (x1));
357 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
360 /* This gives us much better alias analysis when called from
361 the loop optimizer. Note we want to leave the original
362 MEM alone, but need to return the canonicalized MEM with
363 all the flags with their original values. */
364 else if (GET_CODE (x) == MEM)
366 rtx addr = canon_rtx (XEXP (x, 0));
367 if (addr != XEXP (x, 0))
369 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
370 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
371 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
372 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
379 /* Return 1 if X and Y are identical-looking rtx's.
381 We use the data in reg_known_value above to see if two registers with
382 different numbers are, in fact, equivalent. */
385 rtx_equal_for_memref_p (x, y)
390 register enum rtx_code code;
393 if (x == 0 && y == 0)
395 if (x == 0 || y == 0)
404 /* Rtx's of different codes cannot be equal. */
405 if (code != GET_CODE (y))
408 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
409 (REG:SI x) and (REG:HI x) are NOT equivalent. */
411 if (GET_MODE (x) != GET_MODE (y))
414 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
417 return REGNO (x) == REGNO (y);
418 if (code == LABEL_REF)
419 return XEXP (x, 0) == XEXP (y, 0);
420 if (code == SYMBOL_REF)
421 return XSTR (x, 0) == XSTR (y, 0);
422 if (code == CONST_INT)
423 return INTVAL (x) == INTVAL (y);
424 if (code == ADDRESSOF)
425 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
427 /* For commutative operations, the RTX match if the operand match in any
428 order. Also handle the simple binary and unary cases without a loop. */
429 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
430 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
431 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
432 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
433 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
434 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
435 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
436 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
437 else if (GET_RTX_CLASS (code) == '1')
438 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
440 /* Compare the elements. If any pair of corresponding elements
441 fail to match, return 0 for the whole things.
443 Limit cases to types which actually appear in addresses. */
445 fmt = GET_RTX_FORMAT (code);
446 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
451 if (XINT (x, i) != XINT (y, i))
456 /* Two vectors must have the same length. */
457 if (XVECLEN (x, i) != XVECLEN (y, i))
460 /* And the corresponding elements must match. */
461 for (j = 0; j < XVECLEN (x, i); j++)
462 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
467 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
471 /* It is believed that rtx's at this level will never
472 contain anything but integers and other rtx's,
473 except for within LABEL_REFs and SYMBOL_REFs. */
481 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
482 X and return it, or return 0 if none found. */
485 find_symbolic_term (x)
489 register enum rtx_code code;
493 if (code == SYMBOL_REF || code == LABEL_REF)
495 if (GET_RTX_CLASS (code) == 'o')
498 fmt = GET_RTX_FORMAT (code);
499 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
505 t = find_symbolic_term (XEXP (x, i));
509 else if (fmt[i] == 'E')
519 switch (GET_CODE (x))
522 return REG_BASE_VALUE (x);
525 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
531 return find_base_term (XEXP (x, 0));
535 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
542 rtx tmp = find_base_term (XEXP (x, 0));
545 return find_base_term (XEXP (x, 1));
549 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
550 return REG_BASE_VALUE (XEXP (x, 0));
562 /* Return 0 if the addresses X and Y are known to point to different
563 objects, 1 if they might be pointers to the same object. */
566 base_alias_check (x, y)
569 rtx x_base = find_base_term (x);
570 rtx y_base = find_base_term (y);
572 /* If the address itself has no known base see if a known equivalent
573 value has one. If either address still has no known base, nothing
574 is known about aliasing. */
578 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
580 x_base = find_base_term (x_c);
588 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
590 y_base = find_base_term (y_c);
595 /* If the base addresses are equal nothing is known about aliasing. */
596 if (rtx_equal_p (x_base, y_base))
599 /* The base addresses of the read and write are different
600 expressions. If they are both symbols and they are not accessed
601 via AND, there is no conflict. */
602 /* XXX: We can bring knowledge of object alignment and offset into
603 play here. For example, on alpha, "char a, b;" can alias one
604 another, though "char a; long b;" cannot. Similarly, offsets
605 into strutures may be brought into play. Given "char a, b[40];",
606 a and b[1] may overlap, but a and b[20] do not. */
607 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
609 return GET_CODE (x) == AND || GET_CODE (y) == AND;
612 /* If one address is a stack reference there can be no alias:
613 stack references using different base registers do not alias,
614 a stack reference can not alias a parameter, and a stack reference
615 can not alias a global. */
616 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
617 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
620 if (! flag_argument_noalias)
623 if (flag_argument_noalias > 1)
626 /* Weak noalias assertion (arguments are distinct, but may match globals). */
627 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
630 /* Return nonzero if X and Y (memory addresses) could reference the
631 same location in memory. C is an offset accumulator. When
632 C is nonzero, we are testing aliases between X and Y + C.
633 XSIZE is the size in bytes of the X reference,
634 similarly YSIZE is the size in bytes for Y.
636 If XSIZE or YSIZE is zero, we do not know the amount of memory being
637 referenced (the reference was BLKmode), so make the most pessimistic
640 If XSIZE or YSIZE is negative, we may access memory outside the object
641 being referenced as a side effect. This can happen when using AND to
642 align memory references, as is done on the Alpha.
644 Nice to notice that varying addresses cannot conflict with fp if no
645 local variables had their addresses taken, but that's too hard now.
647 TODO: (symbol_ref foo) can not alias (plus REG N) if N is a positive
648 integer because REG would have to point outside of the object, which
649 is not allowed in C or C++. */
653 memrefs_conflict_p (xsize, x, ysize, y, c)
658 if (GET_CODE (x) == HIGH)
660 else if (GET_CODE (x) == LO_SUM)
664 if (GET_CODE (y) == HIGH)
666 else if (GET_CODE (y) == LO_SUM)
671 if (rtx_equal_for_memref_p (x, y))
673 if (xsize <= 0 || ysize <= 0)
675 if (c >= 0 && xsize > c)
677 if (c < 0 && ysize+c > 0)
682 /* This code used to check for conflicts involving stack references and
683 globals but the base address alias code now handles these cases. */
685 if (GET_CODE (x) == PLUS)
687 /* The fact that X is canonicalized means that this
688 PLUS rtx is canonicalized. */
689 rtx x0 = XEXP (x, 0);
690 rtx x1 = XEXP (x, 1);
692 if (GET_CODE (y) == PLUS)
694 /* The fact that Y is canonicalized means that this
695 PLUS rtx is canonicalized. */
696 rtx y0 = XEXP (y, 0);
697 rtx y1 = XEXP (y, 1);
699 if (rtx_equal_for_memref_p (x1, y1))
700 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
701 if (rtx_equal_for_memref_p (x0, y0))
702 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
703 if (GET_CODE (x1) == CONST_INT)
704 if (GET_CODE (y1) == CONST_INT)
705 return memrefs_conflict_p (xsize, x0, ysize, y0,
706 c - INTVAL (x1) + INTVAL (y1));
708 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
709 else if (GET_CODE (y1) == CONST_INT)
710 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
714 else if (GET_CODE (x1) == CONST_INT)
715 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
717 else 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 (GET_CODE (y1) == CONST_INT)
725 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
730 if (GET_CODE (x) == GET_CODE (y))
731 switch (GET_CODE (x))
735 /* Handle cases where we expect the second operands to be the
736 same, and check only whether the first operand would conflict
739 rtx x1 = canon_rtx (XEXP (x, 1));
740 rtx y1 = canon_rtx (XEXP (y, 1));
741 if (! rtx_equal_for_memref_p (x1, y1))
743 x0 = canon_rtx (XEXP (x, 0));
744 y0 = canon_rtx (XEXP (y, 0));
745 if (rtx_equal_for_memref_p (x0, y0))
746 return (xsize == 0 || ysize == 0
747 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
749 /* Can't properly adjust our sizes. */
750 if (GET_CODE (x1) != CONST_INT)
752 xsize /= INTVAL (x1);
753 ysize /= INTVAL (x1);
755 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
759 /* Are these registers known not to be equal? */
762 int r_x = REGNO (x), r_y = REGNO (y);
763 rtx i_x, i_y; /* invariant relationships of X and Y */
765 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
766 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
768 if (i_x == 0 && i_y == 0)
771 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
772 ysize, i_y ? i_y : y, c))
781 /* Treat an access through an AND (e.g. a subword access on an Alpha)
782 as an access with indeterminate size.
783 ??? Could instead convert an n byte reference at (and x y) to an
784 n-y byte reference at (plus x y). */
785 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
786 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
787 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
789 /* XXX: If we are indexing far enough into the array/structure, we
790 may yet be able to determine that we can not overlap. But we
791 also need to that we are far enough from the end not to overlap
792 a following reference, so we do nothing for now. */
793 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
798 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
800 c += (INTVAL (y) - INTVAL (x));
801 return (xsize <= 0 || ysize <= 0
802 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
805 if (GET_CODE (x) == CONST)
807 if (GET_CODE (y) == CONST)
808 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
809 ysize, canon_rtx (XEXP (y, 0)), c);
811 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
814 if (GET_CODE (y) == CONST)
815 return memrefs_conflict_p (xsize, x, ysize,
816 canon_rtx (XEXP (y, 0)), c);
819 return (xsize < 0 || ysize < 0
820 || (rtx_equal_for_memref_p (x, y)
821 && (xsize == 0 || ysize == 0
822 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
829 /* Functions to compute memory dependencies.
831 Since we process the insns in execution order, we can build tables
832 to keep track of what registers are fixed (and not aliased), what registers
833 are varying in known ways, and what registers are varying in unknown
836 If both memory references are volatile, then there must always be a
837 dependence between the two references, since their order can not be
838 changed. A volatile and non-volatile reference can be interchanged
841 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
842 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
843 allow QImode aliasing because the ANSI C standard allows character
844 pointers to alias anything. We are assuming that characters are
845 always QImode here. We also must allow AND addresses, because they may
846 generate accesses outside the object being referenced. This is used to
847 generate aligned addresses from unaligned addresses, for instance, the
848 alpha storeqi_unaligned pattern. */
851 /* This subroutine implements the type and struct/varying part of the
854 Return 0 if the memory references can never alias.
855 Return 1 if the values of the addresses should be checked. */
858 mode_alias_check (x, y, varies)
860 int (*varies) PROTO ((rtx));
863 /* gcc rules: all type aliasing allowed */
866 /* ANSI C rules: different types do not alias. */
867 enum machine_mode x_mode = GET_MODE (x), y_mode = GET_MODE (y);
868 rtx x_addr = XEXP (x, 0), y_addr = XEXP (y, 0);
869 int x_varies, y_varies, x_struct, y_struct;
871 /* If either address is an AND then neither the mode check nor the
872 struct/varying check is valid. */
873 if (GET_CODE (x_addr) == AND || GET_CODE (y_addr) == AND)
876 x_struct = MEM_IN_STRUCT_P (x);
877 y_struct = MEM_IN_STRUCT_P (y);
879 /* QImode and BLKmode references can alias anything. */
880 if (x_mode == QImode || x_mode == BLKmode
881 || y_mode == QImode || y_mode == BLKmode)
884 /* Otherwise, different modes can only alias if they are structure
885 references. gcc bitfield operations can access an entire word,
886 but that word may also contain integers accessed directly.
888 ??? It appears that bitfield accesses can not be larger than
890 ??? Can complex modes alias their components? */
891 if (x_mode != y_mode && ! (x_struct && y_struct))
894 /* Modes are the same or may alias. */
896 /* No alias if one reference is a struct at a varying address and the
897 other is a scalar at a fixed address.
899 If either reference is a varying scalar or a fixed struct nothing
900 is known about aliasing. */
901 x_varies = varies (x_addr);
902 if (x_struct != x_varies)
904 y_varies = varies (y_addr);
905 if (y_struct != y_varies)
908 /* Both are varying structs or fixed scalars. Check that they are not
910 return (x_struct == y_struct);
914 /* Read dependence: X is read after read in MEM takes place. There can
915 only be a dependence here if both reads are volatile. */
918 read_dependence (mem, x)
922 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
925 /* True dependence: X is read after store in MEM takes place. */
928 true_dependence (mem, mem_mode, x, varies)
930 enum machine_mode mem_mode;
934 register rtx x_addr, mem_addr;
936 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
939 /* If X is an unchanging read, then it can't possibly conflict with any
940 non-unchanging store. It may conflict with an unchanging write though,
941 because there may be a single store to this address to initialize it.
942 Just fall through to the code below to resolve the case where we have
943 both an unchanging read and an unchanging write. This won't handle all
944 cases optimally, but the possible performance loss should be
946 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
949 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
952 if (! mode_alias_check (x, mem, varies))
955 x_addr = canon_rtx (XEXP (x, 0));
956 mem_addr = canon_rtx (XEXP (mem, 0));
958 if (mem_mode == VOIDmode)
959 mem_mode = GET_MODE (mem);
961 return memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
962 SIZE_FOR_MODE (x), x_addr, 0);
965 /* Anti dependence: X is written after read in MEM takes place. */
968 anti_dependence (mem, x)
972 rtx x_addr, mem_addr;
974 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
977 /* If MEM is an unchanging read, then it can't possibly conflict with
978 the store to X, because there is at most one store to MEM, and it must
979 have occurred somewhere before MEM. */
980 if (RTX_UNCHANGING_P (mem))
983 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
987 mem = canon_rtx (mem);
989 x_addr = XEXP (x, 0);
990 mem_addr = XEXP (mem, 0);
992 if (! mode_alias_check (x, mem, rtx_varies_p))
995 return memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
996 SIZE_FOR_MODE (x), x_addr, 0);
999 /* Output dependence: X is written after store in MEM takes place. */
1002 output_dependence (mem, x)
1006 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1009 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
1013 mem = canon_rtx (mem);
1015 if (! mode_alias_check (x, mem, rtx_varies_p))
1018 return memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
1019 SIZE_FOR_MODE (x), XEXP (x, 0), 0);
1023 static HARD_REG_SET argument_registers;
1030 #ifndef OUTGOING_REGNO
1031 #define OUTGOING_REGNO(N) N
1033 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1034 /* Check whether this register can hold an incoming pointer
1035 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1036 numbers, so translate if necessary due to register windows. */
1037 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1038 && HARD_REGNO_MODE_OK (i, Pmode))
1039 SET_HARD_REG_BIT (argument_registers, i);
1043 init_alias_analysis ()
1045 int maxreg = max_reg_num ();
1050 reg_known_value_size = maxreg;
1053 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1054 - FIRST_PSEUDO_REGISTER;
1056 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1057 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1058 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1059 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1060 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1062 /* Overallocate reg_base_value to allow some growth during loop
1063 optimization. Loop unrolling can create a large number of
1065 reg_base_value_size = maxreg * 2;
1066 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1067 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1068 reg_seen = (char *)alloca (reg_base_value_size);
1069 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1070 if (! reload_completed && flag_unroll_loops)
1072 alias_invariant = (rtx *)xrealloc (alias_invariant,
1073 reg_base_value_size * sizeof (rtx));
1074 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1078 /* The basic idea is that each pass through this loop will use the
1079 "constant" information from the previous pass to propagate alias
1080 information through another level of assignments.
1082 This could get expensive if the assignment chains are long. Maybe
1083 we should throttle the number of iterations, possibly based on
1084 the optimization level or flag_expensive_optimizations.
1086 We could propagate more information in the first pass by making use
1087 of REG_N_SETS to determine immediately that the alias information
1088 for a pseudo is "constant".
1090 A program with an uninitialized variable can cause an infinite loop
1091 here. Instead of doing a full dataflow analysis to detect such problems
1092 we just cap the number of iterations for the loop.
1094 The state of the arrays for the set chain in question does not matter
1095 since the program has undefined behavior. */
1100 /* Assume nothing will change this iteration of the loop. */
1103 /* We want to assign the same IDs each iteration of this loop, so
1104 start counting from zero each iteration of the loop. */
1107 /* We're at the start of the funtion each iteration through the
1108 loop, so we're copying arguments. */
1109 copying_arguments = 1;
1111 /* Wipe the potential alias information clean for this pass. */
1112 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1114 /* Wipe the reg_seen array clean. */
1115 bzero ((char *) reg_seen, reg_base_value_size);
1117 /* Mark all hard registers which may contain an address.
1118 The stack, frame and argument pointers may contain an address.
1119 An argument register which can hold a Pmode value may contain
1120 an address even if it is not in BASE_REGS.
1122 The address expression is VOIDmode for an argument and
1123 Pmode for other registers. */
1125 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1126 if (TEST_HARD_REG_BIT (argument_registers, i))
1127 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1128 gen_rtx_REG (Pmode, i));
1130 new_reg_base_value[STACK_POINTER_REGNUM]
1131 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1132 new_reg_base_value[ARG_POINTER_REGNUM]
1133 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1134 new_reg_base_value[FRAME_POINTER_REGNUM]
1135 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1136 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1137 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1138 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1140 if (struct_value_incoming_rtx
1141 && GET_CODE (struct_value_incoming_rtx) == REG)
1142 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1143 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1145 if (static_chain_rtx
1146 && GET_CODE (static_chain_rtx) == REG)
1147 new_reg_base_value[REGNO (static_chain_rtx)]
1148 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1150 /* Walk the insns adding values to the new_reg_base_value array. */
1151 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1153 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1156 /* If this insn has a noalias note, process it, Otherwise,
1157 scan for sets. A simple set will have no side effects
1158 which could change the base value of any other register. */
1160 if (GET_CODE (PATTERN (insn)) == SET
1161 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1162 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1164 note_stores (PATTERN (insn), record_set);
1166 set = single_set (insn);
1169 && GET_CODE (SET_DEST (set)) == REG
1170 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1171 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1172 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1173 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1174 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1176 int regno = REGNO (SET_DEST (set));
1177 reg_known_value[regno] = XEXP (note, 0);
1178 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1181 else if (GET_CODE (insn) == NOTE
1182 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1183 copying_arguments = 0;
1186 /* Now propagate values from new_reg_base_value to reg_base_value. */
1187 for (i = 0; i < reg_base_value_size; i++)
1189 if (new_reg_base_value[i]
1190 && new_reg_base_value[i] != reg_base_value[i]
1191 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1193 reg_base_value[i] = new_reg_base_value[i];
1198 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1200 /* Fill in the remaining entries. */
1201 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1202 if (reg_known_value[i] == 0)
1203 reg_known_value[i] = regno_reg_rtx[i];
1205 /* Simplify the reg_base_value array so that no register refers to
1206 another register, except to special registers indirectly through
1207 ADDRESS expressions.
1209 In theory this loop can take as long as O(registers^2), but unless
1210 there are very long dependency chains it will run in close to linear
1213 This loop may not be needed any longer now that the main loop does
1214 a better job at propagating alias information. */
1220 for (i = 0; i < reg_base_value_size; i++)
1222 rtx base = reg_base_value[i];
1223 if (base && GET_CODE (base) == REG)
1225 int base_regno = REGNO (base);
1226 if (base_regno == i) /* register set from itself */
1227 reg_base_value[i] = 0;
1229 reg_base_value[i] = reg_base_value[base_regno];
1234 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1236 new_reg_base_value = 0;
1241 end_alias_analysis ()
1243 reg_known_value = 0;
1245 reg_base_value_size = 0;
1246 if (alias_invariant)
1248 free ((char *)alias_invariant);
1249 alias_invariant = 0;