1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
27 #include "hard-reg-set.h"
31 static rtx canon_rtx PROTO((rtx));
32 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
33 static rtx find_symbolic_term PROTO((rtx));
34 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
36 static void record_set PROTO((rtx, rtx));
37 static rtx find_base_term PROTO((rtx));
38 static int base_alias_check PROTO((rtx, rtx));
39 static rtx find_base_value PROTO((rtx));
41 /* Set up all info needed to perform alias analysis on memory references. */
43 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
45 /* Cap the number of passes we make over the insns propagating alias
46 information through set chains.
48 10 is a completely arbitrary choice. */
49 #define MAX_ALIAS_LOOP_PASSES 10
51 /* reg_base_value[N] gives an address to which register N is related.
52 If all sets after the first add or subtract to the current value
53 or otherwise modify it so it does not point to a different top level
54 object, reg_base_value[N] is equal to the address part of the source
57 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
58 expressions represent certain special values: function arguments and
59 the stack, frame, and argument pointers. The contents of an address
60 expression are not used (but they are descriptive for debugging);
61 only the address and mode matter. Pointer equality, not rtx_equal_p,
62 determines whether two ADDRESS expressions refer to the same base
63 address. The mode determines whether it is a function argument or
64 other special value. */
67 rtx *new_reg_base_value;
68 unsigned int reg_base_value_size; /* size of reg_base_value array */
69 #define REG_BASE_VALUE(X) \
70 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
72 /* Vector of known invariant relationships between registers. Set in
73 loop unrolling. Indexed by register number, if nonzero the value
74 is an expression describing this register in terms of another.
76 The length of this array is REG_BASE_VALUE_SIZE.
78 Because this array contains only pseudo registers it has no effect
80 static rtx *alias_invariant;
82 /* Vector indexed by N giving the initial (unchanging) value known
83 for pseudo-register N. */
86 /* Indicates number of valid entries in reg_known_value. */
87 static int reg_known_value_size;
89 /* Vector recording for each reg_known_value whether it is due to a
90 REG_EQUIV note. Future passes (viz., reload) may replace the
91 pseudo with the equivalent expression and so we account for the
92 dependences that would be introduced if that happens. */
93 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
94 assign_parms mention the arg pointer, and there are explicit insns in the
95 RTL that modify the arg pointer. Thus we must ensure that such insns don't
96 get scheduled across each other because that would invalidate the REG_EQUIV
97 notes. One could argue that the REG_EQUIV notes are wrong, but solving
98 the problem in the scheduler will likely give better code, so we do it
100 char *reg_known_equiv_p;
102 /* True when scanning insns from the start of the rtl to the
103 NOTE_INSN_FUNCTION_BEG note. */
105 static int copying_arguments;
107 /* Inside SRC, the source of a SET, find a base address. */
110 find_base_value (src)
113 switch (GET_CODE (src))
120 /* At the start of a function argument registers have known base
121 values which may be lost later. Returning an ADDRESS
122 expression here allows optimization based on argument values
123 even when the argument registers are used for other purposes. */
124 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
125 return new_reg_base_value[REGNO (src)];
127 /* If a pseudo has a known base value, return it. Do not do this
128 for hard regs since it can result in a circular dependency
129 chain for registers which have values at function entry.
131 The test above is not sufficient because the scheduler may move
132 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
133 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
134 && REGNO (src) < reg_base_value_size
135 && reg_base_value[REGNO (src)])
136 return reg_base_value[REGNO (src)];
141 /* Check for an argument passed in memory. Only record in the
142 copying-arguments block; it is too hard to track changes
144 if (copying_arguments
145 && (XEXP (src, 0) == arg_pointer_rtx
146 || (GET_CODE (XEXP (src, 0)) == PLUS
147 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
148 return gen_rtx_ADDRESS (VOIDmode, src);
153 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
160 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
162 /* If either operand is a REG, then see if we already have
163 a known value for it. */
164 if (GET_CODE (src_0) == REG)
166 temp = find_base_value (src_0);
171 if (GET_CODE (src_1) == REG)
173 temp = find_base_value (src_1);
178 /* Guess which operand is the base address.
180 If either operand is a symbol, then it is the base. If
181 either operand is a CONST_INT, then the other is the base. */
183 if (GET_CODE (src_1) == CONST_INT
184 || GET_CODE (src_0) == SYMBOL_REF
185 || GET_CODE (src_0) == LABEL_REF
186 || GET_CODE (src_0) == CONST)
187 return find_base_value (src_0);
189 if (GET_CODE (src_0) == CONST_INT
190 || GET_CODE (src_1) == SYMBOL_REF
191 || GET_CODE (src_1) == LABEL_REF
192 || GET_CODE (src_1) == CONST)
193 return find_base_value (src_1);
195 /* This might not be necessary anymore.
197 If either operand is a REG that is a known pointer, then it
199 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
200 return find_base_value (src_0);
202 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
203 return find_base_value (src_1);
209 /* The standard form is (lo_sum reg sym) so look only at the
211 return find_base_value (XEXP (src, 1));
214 /* If the second operand is constant set the base
215 address to the first operand. */
216 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
217 return find_base_value (XEXP (src, 0));
221 case SIGN_EXTEND: /* used for NT/Alpha pointers */
223 return find_base_value (XEXP (src, 0));
232 /* Called from init_alias_analysis indirectly through note_stores. */
234 /* while scanning insns to find base values, reg_seen[N] is nonzero if
235 register N has been set in this function. */
236 static char *reg_seen;
238 /* Addresses which are known not to alias anything else are identified
239 by a unique integer. */
240 static int unique_id;
243 record_set (dest, set)
249 if (GET_CODE (dest) != REG)
252 regno = REGNO (dest);
256 /* A CLOBBER wipes out any old value but does not prevent a previously
257 unset register from acquiring a base address (i.e. reg_seen is not
259 if (GET_CODE (set) == CLOBBER)
261 new_reg_base_value[regno] = 0;
270 new_reg_base_value[regno] = 0;
274 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
275 GEN_INT (unique_id++));
279 /* This is not the first set. If the new value is not related to the
280 old value, forget the base value. Note that the following code is
282 extern int x, y; int *p = &x; p += (&y-&x);
283 ANSI C does not allow computing the difference of addresses
284 of distinct top level objects. */
285 if (new_reg_base_value[regno])
286 switch (GET_CODE (src))
291 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
292 new_reg_base_value[regno] = 0;
295 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
296 new_reg_base_value[regno] = 0;
299 new_reg_base_value[regno] = 0;
302 /* If this is the first set of a register, record the value. */
303 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
304 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
305 new_reg_base_value[regno] = find_base_value (src);
310 /* Called from loop optimization when a new pseudo-register is created. */
312 record_base_value (regno, val, invariant)
317 if (regno >= reg_base_value_size)
320 /* If INVARIANT is true then this value also describes an invariant
321 relationship which can be used to deduce that two registers with
322 unknown values are different. */
323 if (invariant && alias_invariant)
324 alias_invariant[regno] = val;
326 if (GET_CODE (val) == REG)
328 if (REGNO (val) < reg_base_value_size)
330 reg_base_value[regno] = reg_base_value[REGNO (val)];
334 reg_base_value[regno] = find_base_value (val);
341 /* Recursively look for equivalences. */
342 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
343 && REGNO (x) < reg_known_value_size)
344 return reg_known_value[REGNO (x)] == x
345 ? x : canon_rtx (reg_known_value[REGNO (x)]);
346 else if (GET_CODE (x) == PLUS)
348 rtx x0 = canon_rtx (XEXP (x, 0));
349 rtx x1 = canon_rtx (XEXP (x, 1));
351 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
353 /* We can tolerate LO_SUMs being offset here; these
354 rtl are used for nothing other than comparisons. */
355 if (GET_CODE (x0) == CONST_INT)
356 return plus_constant_for_output (x1, INTVAL (x0));
357 else if (GET_CODE (x1) == CONST_INT)
358 return plus_constant_for_output (x0, INTVAL (x1));
359 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
362 /* This gives us much better alias analysis when called from
363 the loop optimizer. Note we want to leave the original
364 MEM alone, but need to return the canonicalized MEM with
365 all the flags with their original values. */
366 else if (GET_CODE (x) == MEM)
368 rtx addr = canon_rtx (XEXP (x, 0));
369 if (addr != XEXP (x, 0))
371 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
372 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
373 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
374 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
381 /* Return 1 if X and Y are identical-looking rtx's.
383 We use the data in reg_known_value above to see if two registers with
384 different numbers are, in fact, equivalent. */
387 rtx_equal_for_memref_p (x, y)
392 register enum rtx_code code;
395 if (x == 0 && y == 0)
397 if (x == 0 || y == 0)
406 /* Rtx's of different codes cannot be equal. */
407 if (code != GET_CODE (y))
410 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
411 (REG:SI x) and (REG:HI x) are NOT equivalent. */
413 if (GET_MODE (x) != GET_MODE (y))
416 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
419 return REGNO (x) == REGNO (y);
420 if (code == LABEL_REF)
421 return XEXP (x, 0) == XEXP (y, 0);
422 if (code == SYMBOL_REF)
423 return XSTR (x, 0) == XSTR (y, 0);
424 if (code == CONST_INT)
425 return INTVAL (x) == INTVAL (y);
426 if (code == ADDRESSOF)
427 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
429 /* For commutative operations, the RTX match if the operand match in any
430 order. Also handle the simple binary and unary cases without a loop. */
431 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
432 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
433 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
434 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
435 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
436 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
437 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
438 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
439 else if (GET_RTX_CLASS (code) == '1')
440 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
442 /* Compare the elements. If any pair of corresponding elements
443 fail to match, return 0 for the whole things.
445 Limit cases to types which actually appear in addresses. */
447 fmt = GET_RTX_FORMAT (code);
448 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
453 if (XINT (x, i) != XINT (y, i))
458 /* Two vectors must have the same length. */
459 if (XVECLEN (x, i) != XVECLEN (y, i))
462 /* And the corresponding elements must match. */
463 for (j = 0; j < XVECLEN (x, i); j++)
464 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
469 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
473 /* This can happen for an asm which clobbers memory. */
477 /* It is believed that rtx's at this level will never
478 contain anything but integers and other rtx's,
479 except for within LABEL_REFs and SYMBOL_REFs. */
487 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
488 X and return it, or return 0 if none found. */
491 find_symbolic_term (x)
495 register enum rtx_code code;
499 if (code == SYMBOL_REF || code == LABEL_REF)
501 if (GET_RTX_CLASS (code) == 'o')
504 fmt = GET_RTX_FORMAT (code);
505 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
511 t = find_symbolic_term (XEXP (x, i));
515 else if (fmt[i] == 'E')
525 switch (GET_CODE (x))
528 return REG_BASE_VALUE (x);
531 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
537 return find_base_term (XEXP (x, 0));
541 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
548 rtx tmp = find_base_term (XEXP (x, 0));
551 return find_base_term (XEXP (x, 1));
555 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
556 return REG_BASE_VALUE (XEXP (x, 0));
568 /* Return 0 if the addresses X and Y are known to point to different
569 objects, 1 if they might be pointers to the same object. */
572 base_alias_check (x, y)
575 rtx x_base = find_base_term (x);
576 rtx y_base = find_base_term (y);
578 /* If the address itself has no known base see if a known equivalent
579 value has one. If either address still has no known base, nothing
580 is known about aliasing. */
584 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
586 x_base = find_base_term (x_c);
594 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
596 y_base = find_base_term (y_c);
601 /* If the base addresses are equal nothing is known about aliasing. */
602 if (rtx_equal_p (x_base, y_base))
605 /* The base addresses of the read and write are different
606 expressions. If they are both symbols and they are not accessed
607 via AND, there is no conflict. */
608 /* XXX: We can bring knowledge of object alignment and offset into
609 play here. For example, on alpha, "char a, b;" can alias one
610 another, though "char a; long b;" cannot. Similarly, offsets
611 into strutures may be brought into play. Given "char a, b[40];",
612 a and b[1] may overlap, but a and b[20] do not. */
613 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
615 return GET_CODE (x) == AND || GET_CODE (y) == AND;
618 /* If one address is a stack reference there can be no alias:
619 stack references using different base registers do not alias,
620 a stack reference can not alias a parameter, and a stack reference
621 can not alias a global. */
622 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
623 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
626 if (! flag_argument_noalias)
629 if (flag_argument_noalias > 1)
632 /* Weak noalias assertion (arguments are distinct, but may match globals). */
633 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
636 /* Return nonzero if X and Y (memory addresses) could reference the
637 same location in memory. C is an offset accumulator. When
638 C is nonzero, we are testing aliases between X and Y + C.
639 XSIZE is the size in bytes of the X reference,
640 similarly YSIZE is the size in bytes for Y.
642 If XSIZE or YSIZE is zero, we do not know the amount of memory being
643 referenced (the reference was BLKmode), so make the most pessimistic
646 If XSIZE or YSIZE is negative, we may access memory outside the object
647 being referenced as a side effect. This can happen when using AND to
648 align memory references, as is done on the Alpha.
650 Nice to notice that varying addresses cannot conflict with fp if no
651 local variables had their addresses taken, but that's too hard now. */
655 memrefs_conflict_p (xsize, x, ysize, y, c)
660 if (GET_CODE (x) == HIGH)
662 else if (GET_CODE (x) == LO_SUM)
666 if (GET_CODE (y) == HIGH)
668 else if (GET_CODE (y) == LO_SUM)
673 if (rtx_equal_for_memref_p (x, y))
675 if (xsize <= 0 || ysize <= 0)
677 if (c >= 0 && xsize > c)
679 if (c < 0 && ysize+c > 0)
684 /* This code used to check for conflicts involving stack references and
685 globals but the base address alias code now handles these cases. */
687 if (GET_CODE (x) == PLUS)
689 /* The fact that X is canonicalized means that this
690 PLUS rtx is canonicalized. */
691 rtx x0 = XEXP (x, 0);
692 rtx x1 = XEXP (x, 1);
694 if (GET_CODE (y) == PLUS)
696 /* The fact that Y is canonicalized means that this
697 PLUS rtx is canonicalized. */
698 rtx y0 = XEXP (y, 0);
699 rtx y1 = XEXP (y, 1);
701 if (rtx_equal_for_memref_p (x1, y1))
702 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
703 if (rtx_equal_for_memref_p (x0, y0))
704 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
705 if (GET_CODE (x1) == CONST_INT)
706 if (GET_CODE (y1) == CONST_INT)
707 return memrefs_conflict_p (xsize, x0, ysize, y0,
708 c - INTVAL (x1) + INTVAL (y1));
710 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
711 else if (GET_CODE (y1) == CONST_INT)
712 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
716 else if (GET_CODE (x1) == CONST_INT)
717 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
719 else if (GET_CODE (y) == PLUS)
721 /* The fact that Y is canonicalized means that this
722 PLUS rtx is canonicalized. */
723 rtx y0 = XEXP (y, 0);
724 rtx y1 = XEXP (y, 1);
726 if (GET_CODE (y1) == CONST_INT)
727 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
732 if (GET_CODE (x) == GET_CODE (y))
733 switch (GET_CODE (x))
737 /* Handle cases where we expect the second operands to be the
738 same, and check only whether the first operand would conflict
741 rtx x1 = canon_rtx (XEXP (x, 1));
742 rtx y1 = canon_rtx (XEXP (y, 1));
743 if (! rtx_equal_for_memref_p (x1, y1))
745 x0 = canon_rtx (XEXP (x, 0));
746 y0 = canon_rtx (XEXP (y, 0));
747 if (rtx_equal_for_memref_p (x0, y0))
748 return (xsize == 0 || ysize == 0
749 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
751 /* Can't properly adjust our sizes. */
752 if (GET_CODE (x1) != CONST_INT)
754 xsize /= INTVAL (x1);
755 ysize /= INTVAL (x1);
757 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
761 /* Are these registers known not to be equal? */
764 int r_x = REGNO (x), r_y = REGNO (y);
765 rtx i_x, i_y; /* invariant relationships of X and Y */
767 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
768 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
770 if (i_x == 0 && i_y == 0)
773 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
774 ysize, i_y ? i_y : y, c))
783 /* Treat an access through an AND (e.g. a subword access on an Alpha)
784 as an access with indeterminate size.
785 ??? Could instead convert an n byte reference at (and x y) to an
786 n-y byte reference at (plus x y). */
787 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
788 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
789 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
791 /* XXX: If we are indexing far enough into the array/structure, we
792 may yet be able to determine that we can not overlap. But we
793 also need to that we are far enough from the end not to overlap
794 a following reference, so we do nothing for now. */
795 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
800 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
802 c += (INTVAL (y) - INTVAL (x));
803 return (xsize <= 0 || ysize <= 0
804 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
807 if (GET_CODE (x) == CONST)
809 if (GET_CODE (y) == CONST)
810 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
811 ysize, canon_rtx (XEXP (y, 0)), c);
813 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
816 if (GET_CODE (y) == CONST)
817 return memrefs_conflict_p (xsize, x, ysize,
818 canon_rtx (XEXP (y, 0)), c);
821 return (xsize < 0 || ysize < 0
822 || (rtx_equal_for_memref_p (x, y)
823 && (xsize == 0 || ysize == 0
824 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
831 /* Functions to compute memory dependencies.
833 Since we process the insns in execution order, we can build tables
834 to keep track of what registers are fixed (and not aliased), what registers
835 are varying in known ways, and what registers are varying in unknown
838 If both memory references are volatile, then there must always be a
839 dependence between the two references, since their order can not be
840 changed. A volatile and non-volatile reference can be interchanged
843 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
844 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
845 allow QImode aliasing because the ANSI C standard allows character
846 pointers to alias anything. We are assuming that characters are
847 always QImode here. We also must allow AND addresses, because they may
848 generate accesses outside the object being referenced. This is used to
849 generate aligned addresses from unaligned addresses, for instance, the
850 alpha storeqi_unaligned pattern. */
852 /* Read dependence: X is read after read in MEM takes place. There can
853 only be a dependence here if both reads are volatile. */
856 read_dependence (mem, x)
860 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
863 /* True dependence: X is read after store in MEM takes place. */
866 true_dependence (mem, mem_mode, x, varies)
868 enum machine_mode mem_mode;
870 int (*varies) PROTO((rtx));
872 register rtx x_addr, mem_addr;
874 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
877 /* If X is an unchanging read, then it can't possibly conflict with any
878 non-unchanging store. It may conflict with an unchanging write though,
879 because there may be a single store to this address to initialize it.
880 Just fall through to the code below to resolve the case where we have
881 both an unchanging read and an unchanging write. This won't handle all
882 cases optimally, but the possible performance loss should be
884 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
887 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
890 x_addr = canon_rtx (XEXP (x, 0));
891 mem_addr = canon_rtx (XEXP (mem, 0));
893 if (mem_mode == VOIDmode)
894 mem_mode = GET_MODE (mem);
896 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
897 SIZE_FOR_MODE (x), x_addr, 0))
900 /* If both references are struct references, or both are not, nothing
901 is known about aliasing.
903 If either reference is QImode or BLKmode, ANSI C permits aliasing.
905 If both addresses are constant, or both are not, nothing is known
907 if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
908 || mem_mode == QImode || mem_mode == BLKmode
909 || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
910 || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
911 || varies (x_addr) == varies (mem_addr))
914 /* One memory reference is to a constant address, one is not.
915 One is to a structure, the other is not.
917 If either memory reference is a variable structure the other is a
918 fixed scalar and there is no aliasing. */
919 if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
920 || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
926 /* Anti dependence: X is written after read in MEM takes place. */
929 anti_dependence (mem, x)
933 rtx x_addr, mem_addr;
935 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
938 /* If MEM is an unchanging read, then it can't possibly conflict with
939 the store to X, because there is at most one store to MEM, and it must
940 have occurred somewhere before MEM. */
941 if (RTX_UNCHANGING_P (mem))
944 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
948 mem = canon_rtx (mem);
950 x_addr = XEXP (x, 0);
951 mem_addr = XEXP (mem, 0);
953 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
954 SIZE_FOR_MODE (x), x_addr, 0)
955 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
956 && GET_MODE (mem) != QImode
957 && GET_CODE (mem_addr) != AND
958 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
959 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
960 && GET_MODE (x) != QImode
961 && GET_CODE (x_addr) != AND
962 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
965 /* Output dependence: X is written after store in MEM takes place. */
968 output_dependence (mem, x)
972 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
975 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
979 mem = canon_rtx (mem);
981 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
982 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
983 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
984 && GET_MODE (mem) != QImode
985 && GET_CODE (XEXP (mem, 0)) != AND
986 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
987 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
988 && GET_MODE (x) != QImode
989 && GET_CODE (XEXP (x, 0)) != AND
990 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
994 static HARD_REG_SET argument_registers;
1001 #ifndef OUTGOING_REGNO
1002 #define OUTGOING_REGNO(N) N
1004 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1005 /* Check whether this register can hold an incoming pointer
1006 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1007 numbers, so translate if necessary due to register windows. */
1008 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1009 && HARD_REGNO_MODE_OK (i, Pmode))
1010 SET_HARD_REG_BIT (argument_registers, i);
1014 init_alias_analysis ()
1016 int maxreg = max_reg_num ();
1021 reg_known_value_size = maxreg;
1024 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1025 - FIRST_PSEUDO_REGISTER;
1027 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1028 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1029 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1030 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1031 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1033 /* Overallocate reg_base_value to allow some growth during loop
1034 optimization. Loop unrolling can create a large number of
1036 reg_base_value_size = maxreg * 2;
1037 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1038 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1039 reg_seen = (char *)alloca (reg_base_value_size);
1040 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1041 if (! reload_completed && flag_unroll_loops)
1043 alias_invariant = (rtx *)xrealloc (alias_invariant,
1044 reg_base_value_size * sizeof (rtx));
1045 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1049 /* The basic idea is that each pass through this loop will use the
1050 "constant" information from the previous pass to propagate alias
1051 information through another level of assignments.
1053 This could get expensive if the assignment chains are long. Maybe
1054 we should throttle the number of iterations, possibly based on
1055 the optimization level or flag_expensive_optimizations.
1057 We could propagate more information in the first pass by making use
1058 of REG_N_SETS to determine immediately that the alias information
1059 for a pseudo is "constant".
1061 A program with an uninitialized variable can cause an infinite loop
1062 here. Instead of doing a full dataflow analysis to detect such problems
1063 we just cap the number of iterations for the loop.
1065 The state of the arrays for the set chain in question does not matter
1066 since the program has undefined behavior. */
1071 /* Assume nothing will change this iteration of the loop. */
1074 /* We want to assign the same IDs each iteration of this loop, so
1075 start counting from zero each iteration of the loop. */
1078 /* We're at the start of the funtion each iteration through the
1079 loop, so we're copying arguments. */
1080 copying_arguments = 1;
1082 /* Wipe the potential alias information clean for this pass. */
1083 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1085 /* Wipe the reg_seen array clean. */
1086 bzero ((char *) reg_seen, reg_base_value_size);
1088 /* Mark all hard registers which may contain an address.
1089 The stack, frame and argument pointers may contain an address.
1090 An argument register which can hold a Pmode value may contain
1091 an address even if it is not in BASE_REGS.
1093 The address expression is VOIDmode for an argument and
1094 Pmode for other registers. */
1096 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1097 if (TEST_HARD_REG_BIT (argument_registers, i))
1098 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1099 gen_rtx_REG (Pmode, i));
1101 new_reg_base_value[STACK_POINTER_REGNUM]
1102 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1103 new_reg_base_value[ARG_POINTER_REGNUM]
1104 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1105 new_reg_base_value[FRAME_POINTER_REGNUM]
1106 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1107 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1108 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1109 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1111 if (struct_value_incoming_rtx
1112 && GET_CODE (struct_value_incoming_rtx) == REG)
1113 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1114 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1116 if (static_chain_rtx
1117 && GET_CODE (static_chain_rtx) == REG)
1118 new_reg_base_value[REGNO (static_chain_rtx)]
1119 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1121 /* Walk the insns adding values to the new_reg_base_value array. */
1122 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1124 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1127 /* If this insn has a noalias note, process it, Otherwise,
1128 scan for sets. A simple set will have no side effects
1129 which could change the base value of any other register. */
1131 if (GET_CODE (PATTERN (insn)) == SET
1132 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1133 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1135 note_stores (PATTERN (insn), record_set);
1137 set = single_set (insn);
1140 && GET_CODE (SET_DEST (set)) == REG
1141 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1142 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1143 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1144 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1145 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1147 int regno = REGNO (SET_DEST (set));
1148 reg_known_value[regno] = XEXP (note, 0);
1149 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1152 else if (GET_CODE (insn) == NOTE
1153 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1154 copying_arguments = 0;
1157 /* Now propagate values from new_reg_base_value to reg_base_value. */
1158 for (i = 0; i < reg_base_value_size; i++)
1160 if (new_reg_base_value[i]
1161 && new_reg_base_value[i] != reg_base_value[i]
1162 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1164 reg_base_value[i] = new_reg_base_value[i];
1169 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1171 /* Fill in the remaining entries. */
1172 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1173 if (reg_known_value[i] == 0)
1174 reg_known_value[i] = regno_reg_rtx[i];
1176 /* Simplify the reg_base_value array so that no register refers to
1177 another register, except to special registers indirectly through
1178 ADDRESS expressions.
1180 In theory this loop can take as long as O(registers^2), but unless
1181 there are very long dependency chains it will run in close to linear
1184 This loop may not be needed any longer now that the main loop does
1185 a better job at propagating alias information. */
1191 for (i = 0; i < reg_base_value_size; i++)
1193 rtx base = reg_base_value[i];
1194 if (base && GET_CODE (base) == REG)
1196 int base_regno = REGNO (base);
1197 if (base_regno == i) /* register set from itself */
1198 reg_base_value[i] = 0;
1200 reg_base_value[i] = reg_base_value[base_regno];
1205 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1207 new_reg_base_value = 0;
1212 end_alias_analysis ()
1214 reg_known_value = 0;
1216 reg_base_value_size = 0;
1217 if (alias_invariant)
1219 free ((char *)alias_invariant);
1220 alias_invariant = 0;