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 indexed by N giving the initial (unchanging) value known
72 for pseudo-register N. */
75 /* Indicates number of valid entries in reg_known_value. */
76 static int reg_known_value_size;
78 /* Vector recording for each reg_known_value whether it is due to a
79 REG_EQUIV note. Future passes (viz., reload) may replace the
80 pseudo with the equivalent expression and so we account for the
81 dependences that would be introduced if that happens. */
82 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
83 assign_parms mention the arg pointer, and there are explicit insns in the
84 RTL that modify the arg pointer. Thus we must ensure that such insns don't
85 get scheduled across each other because that would invalidate the REG_EQUIV
86 notes. One could argue that the REG_EQUIV notes are wrong, but solving
87 the problem in the scheduler will likely give better code, so we do it
89 char *reg_known_equiv_p;
91 /* True when scanning insns from the start of the rtl to the
92 NOTE_INSN_FUNCTION_BEG note. */
94 static int copying_arguments;
96 /* Inside SRC, the source of a SET, find a base address. */
102 switch (GET_CODE (src))
109 /* At the start of a function argument registers have known base
110 values which may be lost later. Returning an ADDRESS
111 expression here allows optimization based on argument values
112 even when the argument registers are used for other purposes. */
113 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
114 return new_reg_base_value[REGNO (src)];
116 /* If a pseudo has a known base value, return it. Do not do this
117 for hard regs since it can result in a circular dependency
118 chain for registers which have values at function entry.
120 The test above is not sufficient because the scheduler may move
121 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
122 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
123 && reg_base_value[REGNO (src)])
124 return reg_base_value[REGNO (src)];
129 /* Check for an argument passed in memory. Only record in the
130 copying-arguments block; it is too hard to track changes
132 if (copying_arguments
133 && (XEXP (src, 0) == arg_pointer_rtx
134 || (GET_CODE (XEXP (src, 0)) == PLUS
135 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
136 return gen_rtx_ADDRESS (VOIDmode, src);
141 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
148 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
150 /* If either operand is a REG, then see if we already have
151 a known value for it. */
152 if (GET_CODE (src_0) == REG)
154 temp = find_base_value (src_0);
159 if (GET_CODE (src_1) == REG)
161 temp = find_base_value (src_1);
166 /* Guess which operand is the base address.
168 If either operand is a symbol, then it is the base. If
169 either operand is a CONST_INT, then the other is the base. */
171 if (GET_CODE (src_1) == CONST_INT
172 || GET_CODE (src_0) == SYMBOL_REF
173 || GET_CODE (src_0) == LABEL_REF
174 || GET_CODE (src_0) == CONST)
175 return find_base_value (src_0);
177 if (GET_CODE (src_0) == CONST_INT
178 || GET_CODE (src_1) == SYMBOL_REF
179 || GET_CODE (src_1) == LABEL_REF
180 || GET_CODE (src_1) == CONST)
181 return find_base_value (src_1);
183 /* This might not be necessary anymore.
185 If either operand is a REG that is a known pointer, then it
187 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
188 return find_base_value (src_0);
190 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
191 return find_base_value (src_1);
197 /* The standard form is (lo_sum reg sym) so look only at the
199 return find_base_value (XEXP (src, 1));
202 /* If the second operand is constant set the base
203 address to the first operand. */
204 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
205 return find_base_value (XEXP (src, 0));
209 return find_base_value (XEXP (src, 0));
218 /* Called from init_alias_analysis indirectly through note_stores. */
220 /* while scanning insns to find base values, reg_seen[N] is nonzero if
221 register N has been set in this function. */
222 static char *reg_seen;
224 /* Addresses which are known not to alias anything else are identified
225 by a unique integer. */
226 static int unique_id;
229 record_set (dest, set)
235 if (GET_CODE (dest) != REG)
238 regno = REGNO (dest);
242 /* A CLOBBER wipes out any old value but does not prevent a previously
243 unset register from acquiring a base address (i.e. reg_seen is not
245 if (GET_CODE (set) == CLOBBER)
247 new_reg_base_value[regno] = 0;
256 new_reg_base_value[regno] = 0;
260 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
261 GEN_INT (unique_id++));
265 /* This is not the first set. If the new value is not related to the
266 old value, forget the base value. Note that the following code is
268 extern int x, y; int *p = &x; p += (&y-&x);
269 ANSI C does not allow computing the difference of addresses
270 of distinct top level objects. */
271 if (new_reg_base_value[regno])
272 switch (GET_CODE (src))
277 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
278 new_reg_base_value[regno] = 0;
281 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
282 new_reg_base_value[regno] = 0;
285 new_reg_base_value[regno] = 0;
288 /* If this is the first set of a register, record the value. */
289 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
290 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
291 new_reg_base_value[regno] = find_base_value (src);
296 /* Called from loop optimization when a new pseudo-register is created. */
298 record_base_value (regno, val)
302 if (regno >= reg_base_value_size)
304 if (GET_CODE (val) == REG)
306 if (REGNO (val) < reg_base_value_size)
307 reg_base_value[regno] = reg_base_value[REGNO (val)];
310 reg_base_value[regno] = find_base_value (val);
317 /* Recursively look for equivalences. */
318 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
319 && REGNO (x) < reg_known_value_size)
320 return reg_known_value[REGNO (x)] == x
321 ? x : canon_rtx (reg_known_value[REGNO (x)]);
322 else if (GET_CODE (x) == PLUS)
324 rtx x0 = canon_rtx (XEXP (x, 0));
325 rtx x1 = canon_rtx (XEXP (x, 1));
327 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
329 /* We can tolerate LO_SUMs being offset here; these
330 rtl are used for nothing other than comparisons. */
331 if (GET_CODE (x0) == CONST_INT)
332 return plus_constant_for_output (x1, INTVAL (x0));
333 else if (GET_CODE (x1) == CONST_INT)
334 return plus_constant_for_output (x0, INTVAL (x1));
335 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
338 /* This gives us much better alias analysis when called from
339 the loop optimizer. Note we want to leave the original
340 MEM alone, but need to return the canonicalized MEM with
341 all the flags with their original values. */
342 else if (GET_CODE (x) == MEM)
344 rtx addr = canon_rtx (XEXP (x, 0));
345 if (addr != XEXP (x, 0))
347 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
348 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
349 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
350 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
357 /* Return 1 if X and Y are identical-looking rtx's.
359 We use the data in reg_known_value above to see if two registers with
360 different numbers are, in fact, equivalent. */
363 rtx_equal_for_memref_p (x, y)
368 register enum rtx_code code;
371 if (x == 0 && y == 0)
373 if (x == 0 || y == 0)
382 /* Rtx's of different codes cannot be equal. */
383 if (code != GET_CODE (y))
386 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
387 (REG:SI x) and (REG:HI x) are NOT equivalent. */
389 if (GET_MODE (x) != GET_MODE (y))
392 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
395 return REGNO (x) == REGNO (y);
396 if (code == LABEL_REF)
397 return XEXP (x, 0) == XEXP (y, 0);
398 if (code == SYMBOL_REF)
399 return XSTR (x, 0) == XSTR (y, 0);
401 /* For commutative operations, the RTX match if the operand match in any
402 order. Also handle the simple binary and unary cases without a loop. */
403 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
404 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
405 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
406 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
407 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
408 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
409 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
410 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
411 else if (GET_RTX_CLASS (code) == '1')
412 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
414 /* Compare the elements. If any pair of corresponding elements
415 fail to match, return 0 for the whole things. */
417 fmt = GET_RTX_FORMAT (code);
418 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
423 if (XWINT (x, i) != XWINT (y, i))
429 if (XINT (x, i) != XINT (y, i))
435 /* Two vectors must have the same length. */
436 if (XVECLEN (x, i) != XVECLEN (y, i))
439 /* And the corresponding elements must match. */
440 for (j = 0; j < XVECLEN (x, i); j++)
441 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
446 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
452 if (strcmp (XSTR (x, i), XSTR (y, i)))
457 /* These are just backpointers, so they don't matter. */
463 /* It is believed that rtx's at this level will never
464 contain anything but integers and other rtx's,
465 except for within LABEL_REFs and SYMBOL_REFs. */
473 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
474 X and return it, or return 0 if none found. */
477 find_symbolic_term (x)
481 register enum rtx_code code;
485 if (code == SYMBOL_REF || code == LABEL_REF)
487 if (GET_RTX_CLASS (code) == 'o')
490 fmt = GET_RTX_FORMAT (code);
491 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
497 t = find_symbolic_term (XEXP (x, i));
501 else if (fmt[i] == 'E')
511 switch (GET_CODE (x))
514 return REG_BASE_VALUE (x);
517 return find_base_term (XEXP (x, 0));
523 return find_base_term (XEXP (x, 0));
527 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
534 rtx tmp = find_base_term (XEXP (x, 0));
537 return find_base_term (XEXP (x, 1));
541 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
542 return REG_BASE_VALUE (XEXP (x, 0));
554 /* Return 0 if the addresses X and Y are known to point to different
555 objects, 1 if they might be pointers to the same object. */
558 base_alias_check (x, y)
561 rtx x_base = find_base_term (x);
562 rtx y_base = find_base_term (y);
564 /* If the address itself has no known base see if a known equivalent
565 value has one. If either address still has no known base, nothing
566 is known about aliasing. */
570 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
572 x_base = find_base_term (x_c);
580 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
582 y_base = find_base_term (y_c);
587 /* If the base addresses are equal nothing is known about aliasing. */
588 if (rtx_equal_p (x_base, y_base))
591 /* The base addresses of the read and write are different
592 expressions. If they are both symbols and they are not accessed
593 via AND, there is no conflict. */
594 /* XXX: We can bring knowledge of object alignment and offset into
595 play here. For example, on alpha, "char a, b;" can alias one
596 another, though "char a; long b;" cannot. Similarly, offsets
597 into strutures may be brought into play. Given "char a, b[40];",
598 a and b[1] may overlap, but a and b[20] do not. */
599 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
601 return GET_CODE (x) == AND || GET_CODE (y) == AND;
604 /* If one address is a stack reference there can be no alias:
605 stack references using different base registers do not alias,
606 a stack reference can not alias a parameter, and a stack reference
607 can not alias a global. */
608 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
609 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
612 if (! flag_argument_noalias)
615 if (flag_argument_noalias > 1)
618 /* Weak noalias assertion (arguments are distinct, but may match globals). */
619 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
622 /* Return nonzero if X and Y (memory addresses) could reference the
623 same location in memory. C is an offset accumulator. When
624 C is nonzero, we are testing aliases between X and Y + C.
625 XSIZE is the size in bytes of the X reference,
626 similarly YSIZE is the size in bytes for Y.
628 If XSIZE or YSIZE is zero, we do not know the amount of memory being
629 referenced (the reference was BLKmode), so make the most pessimistic
632 If XSIZE or YSIZE is negative, we may access memory outside the object
633 being referenced as a side effect. This can happen when using AND to
634 align memory references, as is done on the Alpha.
636 Nice to notice that varying addresses cannot conflict with fp if no
637 local variables had their addresses taken, but that's too hard now.
639 TODO: (symbol_ref foo) can not alias (plus REG N) if N is a positive
640 integer because REG would have to point outside of the object, which
641 is not allowed in C or C++. */
645 memrefs_conflict_p (xsize, x, ysize, y, c)
650 if (GET_CODE (x) == HIGH)
652 else if (GET_CODE (x) == LO_SUM)
656 if (GET_CODE (y) == HIGH)
658 else if (GET_CODE (y) == LO_SUM)
663 if (rtx_equal_for_memref_p (x, y))
665 if (xsize <= 0 || ysize <= 0)
667 if (c >= 0 && xsize > c)
669 if (c < 0 && ysize+c > 0)
674 /* This code used to check for conflicts involving stack references and
675 globals but the base address alias code now handles these cases. */
677 if (GET_CODE (x) == PLUS)
679 /* The fact that X is canonicalized means that this
680 PLUS rtx is canonicalized. */
681 rtx x0 = XEXP (x, 0);
682 rtx x1 = XEXP (x, 1);
684 if (GET_CODE (y) == PLUS)
686 /* The fact that Y is canonicalized means that this
687 PLUS rtx is canonicalized. */
688 rtx y0 = XEXP (y, 0);
689 rtx y1 = XEXP (y, 1);
691 if (rtx_equal_for_memref_p (x1, y1))
692 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
693 if (rtx_equal_for_memref_p (x0, y0))
694 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
695 if (GET_CODE (x1) == CONST_INT)
696 if (GET_CODE (y1) == CONST_INT)
697 return memrefs_conflict_p (xsize, x0, ysize, y0,
698 c - INTVAL (x1) + INTVAL (y1));
700 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
701 else if (GET_CODE (y1) == CONST_INT)
702 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
706 else if (GET_CODE (x1) == CONST_INT)
707 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
709 else if (GET_CODE (y) == PLUS)
711 /* The fact that Y is canonicalized means that this
712 PLUS rtx is canonicalized. */
713 rtx y0 = XEXP (y, 0);
714 rtx y1 = XEXP (y, 1);
716 if (GET_CODE (y1) == CONST_INT)
717 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
722 if (GET_CODE (x) == GET_CODE (y))
723 switch (GET_CODE (x))
727 /* Handle cases where we expect the second operands to be the
728 same, and check only whether the first operand would conflict
731 rtx x1 = canon_rtx (XEXP (x, 1));
732 rtx y1 = canon_rtx (XEXP (y, 1));
733 if (! rtx_equal_for_memref_p (x1, y1))
735 x0 = canon_rtx (XEXP (x, 0));
736 y0 = canon_rtx (XEXP (y, 0));
737 if (rtx_equal_for_memref_p (x0, y0))
738 return (xsize == 0 || ysize == 0
739 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
741 /* Can't properly adjust our sizes. */
742 if (GET_CODE (x1) != CONST_INT)
744 xsize /= INTVAL (x1);
745 ysize /= INTVAL (x1);
747 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
754 /* Treat an access through an AND (e.g. a subword access on an Alpha)
755 as an access with indeterminate size.
756 ??? Could instead convert an n byte reference at (and x y) to an
757 n-y byte reference at (plus x y). */
758 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
759 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
760 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
762 /* XXX: If we are indexing far enough into the array/structure, we
763 may yet be able to determine that we can not overlap. But we
764 also need to that we are far enough from the end not to overlap
765 a following reference, so we do nothing for now. */
766 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
771 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
773 c += (INTVAL (y) - INTVAL (x));
774 return (xsize <= 0 || ysize <= 0
775 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
778 if (GET_CODE (x) == CONST)
780 if (GET_CODE (y) == CONST)
781 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
782 ysize, canon_rtx (XEXP (y, 0)), c);
784 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
787 if (GET_CODE (y) == CONST)
788 return memrefs_conflict_p (xsize, x, ysize,
789 canon_rtx (XEXP (y, 0)), c);
792 return (xsize < 0 || ysize < 0
793 || (rtx_equal_for_memref_p (x, y)
794 && (xsize == 0 || ysize == 0
795 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
802 /* Functions to compute memory dependencies.
804 Since we process the insns in execution order, we can build tables
805 to keep track of what registers are fixed (and not aliased), what registers
806 are varying in known ways, and what registers are varying in unknown
809 If both memory references are volatile, then there must always be a
810 dependence between the two references, since their order can not be
811 changed. A volatile and non-volatile reference can be interchanged
814 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
815 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
816 allow QImode aliasing because the ANSI C standard allows character
817 pointers to alias anything. We are assuming that characters are
818 always QImode here. We also must allow AND addresses, because they may
819 generate accesses outside the object being referenced. This is used to
820 generate aligned addresses from unaligned addresses, for instance, the
821 alpha storeqi_unaligned pattern. */
824 /* This subroutine implements the type and struct/varying part of the
827 Return 0 if the memory references can never alias.
828 Return 1 if the values of the addresses should be checked. */
831 mode_alias_check (x, y, varies)
833 int (*varies) PROTO ((rtx));
835 enum machine_mode x_mode = GET_MODE (x), y_mode = GET_MODE (y);
836 rtx x_addr = XEXP (x, 0), y_addr = XEXP (y, 0);
837 int x_varies, y_varies, x_struct, y_struct;
839 /* If either address is an AND then neither the mode check nor the
840 struct/varying check is valid. */
841 if (GET_CODE (x_addr) == AND || GET_CODE (y_addr) == AND)
844 x_struct = MEM_IN_STRUCT_P (x);
845 y_struct = MEM_IN_STRUCT_P (y);
847 /* QImode and BLKmode references can alias anything. */
848 if (x_mode == QImode || x_mode == BLKmode
849 || y_mode == QImode || y_mode == BLKmode)
852 /* Otherwise, different modes can only alias if they are structure
853 references. gcc bitfield operations can access an entire word,
854 but that word may also contain integers accessed directly.
856 ??? It appears that bitfield accesses can not be larger than
858 ??? Can complex modes alias their components? */
859 if (x_mode != y_mode && ! (x_struct && y_struct))
862 /* Modes are the same or may alias. */
864 /* No alias if one reference is a struct at a varying address and the
865 other is a scalar at a fixed address.
867 If either reference is a varying scalar or a fixed struct nothing
868 is known about aliasing. */
869 x_varies = varies (x_addr);
870 if (x_struct != x_varies)
872 y_varies = varies (y_addr);
873 if (y_struct != y_varies)
876 /* Both are varying structs or fixed scalars. Check that they are not
878 return (x_struct == y_struct);
881 /* Read dependence: X is read after read in MEM takes place. There can
882 only be a dependence here if both reads are volatile. */
885 read_dependence (mem, x)
889 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
892 /* True dependence: X is read after store in MEM takes place. */
895 true_dependence (mem, mem_mode, x, varies)
897 enum machine_mode mem_mode;
901 register rtx x_addr, mem_addr;
903 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (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 if (! mode_alias_check (x, mem, varies))
922 x_addr = canon_rtx (XEXP (x, 0));
923 mem_addr = canon_rtx (XEXP (mem, 0));
925 if (mem_mode == VOIDmode)
926 mem_mode = GET_MODE (mem);
928 return memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
929 SIZE_FOR_MODE (x), x_addr, 0);
932 /* Anti dependence: X is written after read in MEM takes place. */
935 anti_dependence (mem, x)
939 rtx x_addr, mem_addr;
941 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
944 /* If MEM is an unchanging read, then it can't possibly conflict with
945 the store to X, because there is at most one store to MEM, and it must
946 have occurred somewhere before MEM. */
947 if (RTX_UNCHANGING_P (mem))
950 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
954 mem = canon_rtx (mem);
956 x_addr = XEXP (x, 0);
957 mem_addr = XEXP (mem, 0);
959 if (! mode_alias_check (x, mem, rtx_varies_p))
962 return memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
963 SIZE_FOR_MODE (x), x_addr, 0);
966 /* Output dependence: X is written after store in MEM takes place. */
969 output_dependence (mem, x)
973 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
976 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
980 mem = canon_rtx (mem);
982 if (! mode_alias_check (x, mem, rtx_varies_p))
985 return memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
986 SIZE_FOR_MODE (x), XEXP (x, 0), 0);
990 static HARD_REG_SET argument_registers;
997 #ifndef OUTGOING_REGNO
998 #define OUTGOING_REGNO(N) N
1000 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1001 /* Check whether this register can hold an incoming pointer
1002 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1003 numbers, so translate if necessary due to register windows. */
1004 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1005 && HARD_REGNO_MODE_OK (i, Pmode))
1006 SET_HARD_REG_BIT (argument_registers, i);
1010 init_alias_analysis ()
1012 int maxreg = max_reg_num ();
1017 reg_known_value_size = maxreg;
1020 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1021 - FIRST_PSEUDO_REGISTER;
1023 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1024 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1025 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1026 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1027 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1029 /* Overallocate reg_base_value to allow some growth during loop
1030 optimization. Loop unrolling can create a large number of
1032 reg_base_value_size = maxreg * 2;
1033 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1034 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1035 reg_seen = (char *)alloca (reg_base_value_size);
1036 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1038 /* The basic idea is that each pass through this loop will use the
1039 "constant" information from the previous pass to propagate alias
1040 information through another level of assignments.
1042 This could get expensive if the assignment chains are long. Maybe
1043 we should throttle the number of iterations, possibly based on
1044 the optimization level or flag_expensive_optimizations.
1046 We could propagate more information in the first pass by making use
1047 of REG_N_SETS to determine immediately that the alias information
1048 for a pseudo is "constant".
1050 A program with an uninitialized variable can cause an infinite loop
1051 here. Instead of doing a full dataflow analysis to detect such problems
1052 we just cap the number of iterations for the loop.
1054 The state of the arrays for the set chain in question does not matter
1055 since the program has undefined behavior. */
1060 /* Assume nothing will change this iteration of the loop. */
1063 /* We want to assign the same IDs each iteration of this loop, so
1064 start counting from zero each iteration of the loop. */
1067 /* We're at the start of the funtion each iteration through the
1068 loop, so we're copying arguments. */
1069 copying_arguments = 1;
1071 /* Wipe the potential alias information clean for this pass. */
1072 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1074 /* Wipe the reg_seen array clean. */
1075 bzero ((char *) reg_seen, reg_base_value_size);
1077 /* Mark all hard registers which may contain an address.
1078 The stack, frame and argument pointers may contain an address.
1079 An argument register which can hold a Pmode value may contain
1080 an address even if it is not in BASE_REGS.
1082 The address expression is VOIDmode for an argument and
1083 Pmode for other registers. */
1085 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1086 if (TEST_HARD_REG_BIT (argument_registers, i))
1087 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1088 gen_rtx_REG (Pmode, i));
1090 new_reg_base_value[STACK_POINTER_REGNUM]
1091 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1092 new_reg_base_value[ARG_POINTER_REGNUM]
1093 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1094 new_reg_base_value[FRAME_POINTER_REGNUM]
1095 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1096 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1097 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1098 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1100 if (struct_value_incoming_rtx
1101 && GET_CODE (struct_value_incoming_rtx) == REG)
1102 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1103 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1105 if (static_chain_rtx
1106 && GET_CODE (static_chain_rtx) == REG)
1107 new_reg_base_value[REGNO (static_chain_rtx)]
1108 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1110 /* Walk the insns adding values to the new_reg_base_value array. */
1111 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1113 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1116 /* If this insn has a noalias note, process it, Otherwise,
1117 scan for sets. A simple set will have no side effects
1118 which could change the base value of any other register. */
1120 if (GET_CODE (PATTERN (insn)) == SET
1121 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1122 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1124 note_stores (PATTERN (insn), record_set);
1126 set = single_set (insn);
1129 && GET_CODE (SET_DEST (set)) == REG
1130 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1131 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1132 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1133 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1134 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1136 int regno = REGNO (SET_DEST (set));
1137 reg_known_value[regno] = XEXP (note, 0);
1138 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1141 else if (GET_CODE (insn) == NOTE
1142 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1143 copying_arguments = 0;
1146 /* Now propagate values from new_reg_base_value to reg_base_value. */
1147 for (i = 0; i < reg_base_value_size; i++)
1149 if (new_reg_base_value[i]
1150 && new_reg_base_value[i] != reg_base_value[i]
1151 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1153 reg_base_value[i] = new_reg_base_value[i];
1158 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1160 /* Fill in the remaining entries. */
1161 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1162 if (reg_known_value[i] == 0)
1163 reg_known_value[i] = regno_reg_rtx[i];
1165 /* Simplify the reg_base_value array so that no register refers to
1166 another register, except to special registers indirectly through
1167 ADDRESS expressions.
1169 In theory this loop can take as long as O(registers^2), but unless
1170 there are very long dependency chains it will run in close to linear
1173 This loop may not be needed any longer now that the main loop does
1174 a better job at propagating alias information. */
1180 for (i = 0; i < reg_base_value_size; i++)
1182 rtx base = reg_base_value[i];
1183 if (base && GET_CODE (base) == REG)
1185 int base_regno = REGNO (base);
1186 if (base_regno == i) /* register set from itself */
1187 reg_base_value[i] = 0;
1189 reg_base_value[i] = reg_base_value[base_regno];
1194 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1196 new_reg_base_value = 0;
1201 end_alias_analysis ()
1203 reg_known_value = 0;
1205 reg_base_value_size = 0;