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
,
36 /* Set up all info needed to perform alias analysis on memory references. */
38 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
40 /* Cap the number of passes we make over the insns propagating alias
41 information through set chains.
43 10 is a completely arbitrary choice. */
44 #define MAX_ALIAS_LOOP_PASSES 10
46 /* reg_base_value[N] gives an address to which register N is related.
47 If all sets after the first add or subtract to the current value
48 or otherwise modify it so it does not point to a different top level
49 object, reg_base_value[N] is equal to the address part of the source
52 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
53 expressions represent certain special values: function arguments and
54 the stack, frame, and argument pointers. The contents of an address
55 expression are not used (but they are descriptive for debugging);
56 only the address and mode matter. Pointer equality, not rtx_equal_p,
57 determines whether two ADDRESS expressions refer to the same base
58 address. The mode determines whether it is a function argument or
59 other special value. */
62 rtx
*new_reg_base_value
;
63 unsigned int reg_base_value_size
; /* size of reg_base_value array */
64 #define REG_BASE_VALUE(X) \
65 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
67 /* Vector indexed by N giving the initial (unchanging) value known
68 for pseudo-register N. */
71 /* Indicates number of valid entries in reg_known_value. */
72 static int reg_known_value_size
;
74 /* Vector recording for each reg_known_value whether it is due to a
75 REG_EQUIV note. Future passes (viz., reload) may replace the
76 pseudo with the equivalent expression and so we account for the
77 dependences that would be introduced if that happens. */
78 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
79 assign_parms mention the arg pointer, and there are explicit insns in the
80 RTL that modify the arg pointer. Thus we must ensure that such insns don't
81 get scheduled across each other because that would invalidate the REG_EQUIV
82 notes. One could argue that the REG_EQUIV notes are wrong, but solving
83 the problem in the scheduler will likely give better code, so we do it
85 char *reg_known_equiv_p
;
87 /* True when scanning insns from the start of the rtl to the
88 NOTE_INSN_FUNCTION_BEG note. */
90 static int copying_arguments
;
92 /* Inside SRC, the source of a SET, find a base address. */
98 switch (GET_CODE (src
))
105 /* At the start of a function argument registers have known base
106 values which may be lost later. Returning an ADDRESS
107 expression here allows optimization based on argument values
108 even when the argument registers are used for other purposes. */
109 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
&& copying_arguments
)
110 return new_reg_base_value
[REGNO (src
)];
112 /* If a pseudo has a known base value, return it. Do not do this
113 for hard regs since it can result in a circular dependency
114 chain for registers which have values at function entry.
116 The test above is not sufficient because the scheduler may move
117 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
118 if (REGNO (src
) >= FIRST_PSEUDO_REGISTER
119 && reg_base_value
[REGNO (src
)])
120 return reg_base_value
[REGNO (src
)];
125 /* Check for an argument passed in memory. Only record in the
126 copying-arguments block; it is too hard to track changes
128 if (copying_arguments
129 && (XEXP (src
, 0) == arg_pointer_rtx
130 || (GET_CODE (XEXP (src
, 0)) == PLUS
131 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
132 return gen_rtx_ADDRESS (VOIDmode
, src
);
137 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
144 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
146 /* If either operand is a REG, then see if we already have
147 a known value for it. */
148 if (GET_CODE (src_0
) == REG
)
150 temp
= find_base_value (src_0
);
155 if (GET_CODE (src_1
) == REG
)
157 temp
= find_base_value (src_1
);
162 /* Guess which operand is the base address.
164 If either operand is a symbol, then it is the base. If
165 either operand is a CONST_INT, then the other is the base. */
167 if (GET_CODE (src_1
) == CONST_INT
168 || GET_CODE (src_0
) == SYMBOL_REF
169 || GET_CODE (src_0
) == LABEL_REF
170 || GET_CODE (src_0
) == CONST
)
171 return find_base_value (src_0
);
173 if (GET_CODE (src_0
) == CONST_INT
174 || GET_CODE (src_1
) == SYMBOL_REF
175 || GET_CODE (src_1
) == LABEL_REF
176 || GET_CODE (src_1
) == CONST
)
177 return find_base_value (src_1
);
179 /* This might not be necessary anymore.
181 If either operand is a REG that is a known pointer, then it
183 if (GET_CODE (src_0
) == REG
&& REGNO_POINTER_FLAG (REGNO (src_0
)))
184 return find_base_value (src_0
);
186 if (GET_CODE (src_1
) == REG
&& REGNO_POINTER_FLAG (REGNO (src_1
)))
187 return find_base_value (src_1
);
193 /* The standard form is (lo_sum reg sym) so look only at the
195 return find_base_value (XEXP (src
, 1));
198 /* If the second operand is constant set the base
199 address to the first operand. */
200 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
201 return find_base_value (XEXP (src
, 0));
205 return find_base_value (XEXP (src
, 0));
214 /* Called from init_alias_analysis indirectly through note_stores. */
216 /* while scanning insns to find base values, reg_seen[N] is nonzero if
217 register N has been set in this function. */
218 static char *reg_seen
;
220 /* Addresses which are known not to alias anything else are identified
221 by a unique integer. */
222 static int unique_id
;
225 record_set (dest
, set
)
231 if (GET_CODE (dest
) != REG
)
234 regno
= REGNO (dest
);
238 /* A CLOBBER wipes out any old value but does not prevent a previously
239 unset register from acquiring a base address (i.e. reg_seen is not
241 if (GET_CODE (set
) == CLOBBER
)
243 new_reg_base_value
[regno
] = 0;
252 new_reg_base_value
[regno
] = 0;
256 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
257 GEN_INT (unique_id
++));
261 /* This is not the first set. If the new value is not related to the
262 old value, forget the base value. Note that the following code is
264 extern int x, y; int *p = &x; p += (&y-&x);
265 ANSI C does not allow computing the difference of addresses
266 of distinct top level objects. */
267 if (new_reg_base_value
[regno
])
268 switch (GET_CODE (src
))
273 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
274 new_reg_base_value
[regno
] = 0;
277 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
278 new_reg_base_value
[regno
] = 0;
281 new_reg_base_value
[regno
] = 0;
284 /* If this is the first set of a register, record the value. */
285 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
286 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
287 new_reg_base_value
[regno
] = find_base_value (src
);
292 /* Called from loop optimization when a new pseudo-register is created. */
294 record_base_value (regno
, val
)
298 if (regno
>= reg_base_value_size
)
300 if (GET_CODE (val
) == REG
)
302 if (REGNO (val
) < reg_base_value_size
)
303 reg_base_value
[regno
] = reg_base_value
[REGNO (val
)];
306 reg_base_value
[regno
] = find_base_value (val
);
313 /* Recursively look for equivalences. */
314 if (GET_CODE (x
) == REG
&& REGNO (x
) >= FIRST_PSEUDO_REGISTER
315 && REGNO (x
) < reg_known_value_size
)
316 return reg_known_value
[REGNO (x
)] == x
317 ? x
: canon_rtx (reg_known_value
[REGNO (x
)]);
318 else if (GET_CODE (x
) == PLUS
)
320 rtx x0
= canon_rtx (XEXP (x
, 0));
321 rtx x1
= canon_rtx (XEXP (x
, 1));
323 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
325 /* We can tolerate LO_SUMs being offset here; these
326 rtl are used for nothing other than comparisons. */
327 if (GET_CODE (x0
) == CONST_INT
)
328 return plus_constant_for_output (x1
, INTVAL (x0
));
329 else if (GET_CODE (x1
) == CONST_INT
)
330 return plus_constant_for_output (x0
, INTVAL (x1
));
331 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
334 /* This gives us much better alias analysis when called from
335 the loop optimizer. Note we want to leave the original
336 MEM alone, but need to return the canonicalized MEM with
337 all the flags with their original values. */
338 else if (GET_CODE (x
) == MEM
)
340 rtx addr
= canon_rtx (XEXP (x
, 0));
341 if (addr
!= XEXP (x
, 0))
343 rtx
new = gen_rtx_MEM (GET_MODE (x
), addr
);
344 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x
);
345 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x
);
346 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x
);
353 /* Return 1 if X and Y are identical-looking rtx's.
355 We use the data in reg_known_value above to see if two registers with
356 different numbers are, in fact, equivalent. */
359 rtx_equal_for_memref_p (x
, y
)
364 register enum rtx_code code
;
367 if (x
== 0 && y
== 0)
369 if (x
== 0 || y
== 0)
378 /* Rtx's of different codes cannot be equal. */
379 if (code
!= GET_CODE (y
))
382 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
383 (REG:SI x) and (REG:HI x) are NOT equivalent. */
385 if (GET_MODE (x
) != GET_MODE (y
))
388 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
391 return REGNO (x
) == REGNO (y
);
392 if (code
== LABEL_REF
)
393 return XEXP (x
, 0) == XEXP (y
, 0);
394 if (code
== SYMBOL_REF
)
395 return XSTR (x
, 0) == XSTR (y
, 0);
397 /* For commutative operations, the RTX match if the operand match in any
398 order. Also handle the simple binary and unary cases without a loop. */
399 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
400 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
401 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
402 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
403 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
404 else if (GET_RTX_CLASS (code
) == '<' || GET_RTX_CLASS (code
) == '2')
405 return (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
406 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)));
407 else if (GET_RTX_CLASS (code
) == '1')
408 return rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0));
410 /* Compare the elements. If any pair of corresponding elements
411 fail to match, return 0 for the whole things. */
413 fmt
= GET_RTX_FORMAT (code
);
414 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
419 if (XWINT (x
, i
) != XWINT (y
, i
))
425 if (XINT (x
, i
) != XINT (y
, i
))
431 /* Two vectors must have the same length. */
432 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
435 /* And the corresponding elements must match. */
436 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
437 if (rtx_equal_for_memref_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
)) == 0)
442 if (rtx_equal_for_memref_p (XEXP (x
, i
), XEXP (y
, i
)) == 0)
448 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
453 /* These are just backpointers, so they don't matter. */
459 /* It is believed that rtx's at this level will never
460 contain anything but integers and other rtx's,
461 except for within LABEL_REFs and SYMBOL_REFs. */
469 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
470 X and return it, or return 0 if none found. */
473 find_symbolic_term (x
)
477 register enum rtx_code code
;
481 if (code
== SYMBOL_REF
|| code
== LABEL_REF
)
483 if (GET_RTX_CLASS (code
) == 'o')
486 fmt
= GET_RTX_FORMAT (code
);
487 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
493 t
= find_symbolic_term (XEXP (x
, i
));
497 else if (fmt
[i
] == 'E')
507 switch (GET_CODE (x
))
510 return REG_BASE_VALUE (x
);
513 return find_base_term (XEXP (x
, 0));
519 return find_base_term (XEXP (x
, 0));
523 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
530 rtx tmp
= find_base_term (XEXP (x
, 0));
533 return find_base_term (XEXP (x
, 1));
537 if (GET_CODE (XEXP (x
, 0)) == REG
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
538 return REG_BASE_VALUE (XEXP (x
, 0));
550 /* Return 0 if the addresses X and Y are known to point to different
551 objects, 1 if they might be pointers to the same object. */
554 base_alias_check (x
, y
)
557 rtx x_base
= find_base_term (x
);
558 rtx y_base
= find_base_term (y
);
560 /* If the address itself has no known base see if a known equivalent
561 value has one. If either address still has no known base, nothing
562 is known about aliasing. */
566 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
568 x_base
= find_base_term (x_c
);
576 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
578 y_base
= find_base_term (y_c
);
583 /* If the base addresses are equal nothing is known about aliasing. */
584 if (rtx_equal_p (x_base
, y_base
))
587 /* The base addresses of the read and write are different
588 expressions. If they are both symbols and they are not accessed
589 via AND, there is no conflict. */
590 /* XXX: We can bring knowledge of object alignment and offset into
591 play here. For example, on alpha, "char a, b;" can alias one
592 another, though "char a; long b;" cannot. Similarly, offsets
593 into strutures may be brought into play. Given "char a, b[40];",
594 a and b[1] may overlap, but a and b[20] do not. */
595 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
597 return GET_CODE (x
) == AND
|| GET_CODE (y
) == AND
;
600 /* If one address is a stack reference there can be no alias:
601 stack references using different base registers do not alias,
602 a stack reference can not alias a parameter, and a stack reference
603 can not alias a global. */
604 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
605 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
608 if (! flag_argument_noalias
)
611 if (flag_argument_noalias
> 1)
614 /* Weak noalias assertion (arguments are distinct, but may match globals). */
615 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
618 /* Return nonzero if X and Y (memory addresses) could reference the
619 same location in memory. C is an offset accumulator. When
620 C is nonzero, we are testing aliases between X and Y + C.
621 XSIZE is the size in bytes of the X reference,
622 similarly YSIZE is the size in bytes for Y.
624 If XSIZE or YSIZE is zero, we do not know the amount of memory being
625 referenced (the reference was BLKmode), so make the most pessimistic
628 If XSIZE or YSIZE is negative, we may access memory outside the object
629 being referenced as a side effect. This can happen when using AND to
630 align memory references, as is done on the Alpha.
632 Nice to notice that varying addresses cannot conflict with fp if no
633 local variables had their addresses taken, but that's too hard now. */
637 memrefs_conflict_p (xsize
, x
, ysize
, y
, c
)
642 if (GET_CODE (x
) == HIGH
)
644 else if (GET_CODE (x
) == LO_SUM
)
648 if (GET_CODE (y
) == HIGH
)
650 else if (GET_CODE (y
) == LO_SUM
)
655 if (rtx_equal_for_memref_p (x
, y
))
657 if (xsize
<= 0 || ysize
<= 0)
659 if (c
>= 0 && xsize
> c
)
661 if (c
< 0 && ysize
+c
> 0)
666 /* This code used to check for conflicts involving stack references and
667 globals but the base address alias code now handles these cases. */
669 if (GET_CODE (x
) == PLUS
)
671 /* The fact that X is canonicalized means that this
672 PLUS rtx is canonicalized. */
673 rtx x0
= XEXP (x
, 0);
674 rtx x1
= XEXP (x
, 1);
676 if (GET_CODE (y
) == PLUS
)
678 /* The fact that Y is canonicalized means that this
679 PLUS rtx is canonicalized. */
680 rtx y0
= XEXP (y
, 0);
681 rtx y1
= XEXP (y
, 1);
683 if (rtx_equal_for_memref_p (x1
, y1
))
684 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
685 if (rtx_equal_for_memref_p (x0
, y0
))
686 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
687 if (GET_CODE (x1
) == CONST_INT
)
688 if (GET_CODE (y1
) == CONST_INT
)
689 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
690 c
- INTVAL (x1
) + INTVAL (y1
));
692 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
693 else if (GET_CODE (y1
) == CONST_INT
)
694 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
698 else if (GET_CODE (x1
) == CONST_INT
)
699 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
701 else if (GET_CODE (y
) == PLUS
)
703 /* The fact that Y is canonicalized means that this
704 PLUS rtx is canonicalized. */
705 rtx y0
= XEXP (y
, 0);
706 rtx y1
= XEXP (y
, 1);
708 if (GET_CODE (y1
) == CONST_INT
)
709 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
714 if (GET_CODE (x
) == GET_CODE (y
))
715 switch (GET_CODE (x
))
719 /* Handle cases where we expect the second operands to be the
720 same, and check only whether the first operand would conflict
723 rtx x1
= canon_rtx (XEXP (x
, 1));
724 rtx y1
= canon_rtx (XEXP (y
, 1));
725 if (! rtx_equal_for_memref_p (x1
, y1
))
727 x0
= canon_rtx (XEXP (x
, 0));
728 y0
= canon_rtx (XEXP (y
, 0));
729 if (rtx_equal_for_memref_p (x0
, y0
))
730 return (xsize
== 0 || ysize
== 0
731 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
733 /* Can't properly adjust our sizes. */
734 if (GET_CODE (x1
) != CONST_INT
)
736 xsize
/= INTVAL (x1
);
737 ysize
/= INTVAL (x1
);
739 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
746 /* Treat an access through an AND (e.g. a subword access on an Alpha)
747 as an access with indeterminate size.
748 ??? Could instead convert an n byte reference at (and x y) to an
749 n-y byte reference at (plus x y). */
750 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
751 return memrefs_conflict_p (-1, XEXP (x
, 0), ysize
, y
, c
);
752 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
754 /* XXX: If we are indexing far enough into the array/structure, we
755 may yet be able to determine that we can not overlap. But we
756 also need to that we are far enough from the end not to overlap
757 a following reference, so we do nothing for now. */
758 return memrefs_conflict_p (xsize
, x
, -1, XEXP (y
, 0), c
);
763 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
765 c
+= (INTVAL (y
) - INTVAL (x
));
766 return (xsize
<= 0 || ysize
<= 0
767 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
770 if (GET_CODE (x
) == CONST
)
772 if (GET_CODE (y
) == CONST
)
773 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
774 ysize
, canon_rtx (XEXP (y
, 0)), c
);
776 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
779 if (GET_CODE (y
) == CONST
)
780 return memrefs_conflict_p (xsize
, x
, ysize
,
781 canon_rtx (XEXP (y
, 0)), c
);
784 return (xsize
< 0 || ysize
< 0
785 || (rtx_equal_for_memref_p (x
, y
)
786 && (xsize
== 0 || ysize
== 0
787 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
794 /* Functions to compute memory dependencies.
796 Since we process the insns in execution order, we can build tables
797 to keep track of what registers are fixed (and not aliased), what registers
798 are varying in known ways, and what registers are varying in unknown
801 If both memory references are volatile, then there must always be a
802 dependence between the two references, since their order can not be
803 changed. A volatile and non-volatile reference can be interchanged
806 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
807 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
808 allow QImode aliasing because the ANSI C standard allows character
809 pointers to alias anything. We are assuming that characters are
810 always QImode here. We also must allow AND addresses, because they may
811 generate accesses outside the object being referenced. This is used to
812 generate aligned addresses from unaligned addresses, for instance, the
813 alpha storeqi_unaligned pattern. */
815 /* Read dependence: X is read after read in MEM takes place. There can
816 only be a dependence here if both reads are volatile. */
819 read_dependence (mem
, x
)
823 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
826 /* True dependence: X is read after store in MEM takes place. */
829 true_dependence (mem
, mem_mode
, x
, varies
)
831 enum machine_mode mem_mode
;
835 register rtx x_addr
, mem_addr
;
837 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
840 /* If X is an unchanging read, then it can't possibly conflict with any
841 non-unchanging store. It may conflict with an unchanging write though,
842 because there may be a single store to this address to initialize it.
843 Just fall through to the code below to resolve the case where we have
844 both an unchanging read and an unchanging write. This won't handle all
845 cases optimally, but the possible performance loss should be
847 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
850 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0)))
853 x_addr
= canon_rtx (XEXP (x
, 0));
854 mem_addr
= canon_rtx (XEXP (mem
, 0));
856 if (mem_mode
== VOIDmode
)
857 mem_mode
= GET_MODE (mem
);
859 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
860 SIZE_FOR_MODE (x
), x_addr
, 0))
863 /* If both references are struct references, or both are not, nothing
864 is known about aliasing.
866 If either reference is QImode or BLKmode, ANSI C permits aliasing.
868 If both addresses are constant, or both are not, nothing is known
870 if (MEM_IN_STRUCT_P (x
) == MEM_IN_STRUCT_P (mem
)
871 || mem_mode
== QImode
|| mem_mode
== BLKmode
872 || GET_MODE (x
) == QImode
|| GET_MODE (x
) == BLKmode
873 || GET_CODE (x_addr
) == AND
|| GET_CODE (mem_addr
) == AND
874 || varies (x_addr
) == varies (mem_addr
))
877 /* One memory reference is to a constant address, one is not.
878 One is to a structure, the other is not.
880 If either memory reference is a variable structure the other is a
881 fixed scalar and there is no aliasing. */
882 if ((MEM_IN_STRUCT_P (mem
) && varies (mem_addr
))
883 || (MEM_IN_STRUCT_P (x
) && varies (x_addr
)))
889 /* Anti dependence: X is written after read in MEM takes place. */
892 anti_dependence (mem
, x
)
896 rtx x_addr
, mem_addr
;
898 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
901 /* If MEM is an unchanging read, then it can't possibly conflict with
902 the store to X, because there is at most one store to MEM, and it must
903 have occurred somewhere before MEM. */
904 if (RTX_UNCHANGING_P (mem
))
907 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0)))
911 mem
= canon_rtx (mem
);
913 x_addr
= XEXP (x
, 0);
914 mem_addr
= XEXP (mem
, 0);
916 return (memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
917 SIZE_FOR_MODE (x
), x_addr
, 0)
918 && ! (MEM_IN_STRUCT_P (mem
) && rtx_addr_varies_p (mem
)
919 && GET_MODE (mem
) != QImode
920 && GET_CODE (mem_addr
) != AND
921 && ! MEM_IN_STRUCT_P (x
) && ! rtx_addr_varies_p (x
))
922 && ! (MEM_IN_STRUCT_P (x
) && rtx_addr_varies_p (x
)
923 && GET_MODE (x
) != QImode
924 && GET_CODE (x_addr
) != AND
925 && ! MEM_IN_STRUCT_P (mem
) && ! rtx_addr_varies_p (mem
)));
928 /* Output dependence: X is written after store in MEM takes place. */
931 output_dependence (mem
, x
)
935 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
938 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0)))
942 mem
= canon_rtx (mem
);
944 return (memrefs_conflict_p (SIZE_FOR_MODE (mem
), XEXP (mem
, 0),
945 SIZE_FOR_MODE (x
), XEXP (x
, 0), 0)
946 && ! (MEM_IN_STRUCT_P (mem
) && rtx_addr_varies_p (mem
)
947 && GET_MODE (mem
) != QImode
948 && GET_CODE (XEXP (mem
, 0)) != AND
949 && ! MEM_IN_STRUCT_P (x
) && ! rtx_addr_varies_p (x
))
950 && ! (MEM_IN_STRUCT_P (x
) && rtx_addr_varies_p (x
)
951 && GET_MODE (x
) != QImode
952 && GET_CODE (XEXP (x
, 0)) != AND
953 && ! MEM_IN_STRUCT_P (mem
) && ! rtx_addr_varies_p (mem
)));
957 static HARD_REG_SET argument_registers
;
964 #ifndef OUTGOING_REGNO
965 #define OUTGOING_REGNO(N) N
967 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
968 /* Check whether this register can hold an incoming pointer
969 argument. FUNCTION_ARG_REGNO_P tests outgoing register
970 numbers, so translate if necessary due to register windows. */
971 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
972 && HARD_REGNO_MODE_OK (i
, Pmode
))
973 SET_HARD_REG_BIT (argument_registers
, i
);
977 init_alias_analysis ()
979 int maxreg
= max_reg_num ();
984 reg_known_value_size
= maxreg
;
987 = (rtx
*) oballoc ((maxreg
- FIRST_PSEUDO_REGISTER
) * sizeof (rtx
))
988 - FIRST_PSEUDO_REGISTER
;
990 oballoc (maxreg
- FIRST_PSEUDO_REGISTER
) - FIRST_PSEUDO_REGISTER
;
991 bzero ((char *) (reg_known_value
+ FIRST_PSEUDO_REGISTER
),
992 (maxreg
-FIRST_PSEUDO_REGISTER
) * sizeof (rtx
));
993 bzero (reg_known_equiv_p
+ FIRST_PSEUDO_REGISTER
,
994 (maxreg
- FIRST_PSEUDO_REGISTER
) * sizeof (char));
996 /* Overallocate reg_base_value to allow some growth during loop
997 optimization. Loop unrolling can create a large number of
999 reg_base_value_size
= maxreg
* 2;
1000 reg_base_value
= (rtx
*)oballoc (reg_base_value_size
* sizeof (rtx
));
1001 new_reg_base_value
= (rtx
*)alloca (reg_base_value_size
* sizeof (rtx
));
1002 reg_seen
= (char *)alloca (reg_base_value_size
);
1003 bzero ((char *) reg_base_value
, reg_base_value_size
* sizeof (rtx
));
1005 /* The basic idea is that each pass through this loop will use the
1006 "constant" information from the previous pass to propagate alias
1007 information through another level of assignments.
1009 This could get expensive if the assignment chains are long. Maybe
1010 we should throttle the number of iterations, possibly based on
1011 the optimization level or flag_expensive_optimizations.
1013 We could propagate more information in the first pass by making use
1014 of REG_N_SETS to determine immediately that the alias information
1015 for a pseudo is "constant".
1017 A program with an uninitialized variable can cause an infinite loop
1018 here. Instead of doing a full dataflow analysis to detect such problems
1019 we just cap the number of iterations for the loop.
1021 The state of the arrays for the set chain in question does not matter
1022 since the program has undefined behavior. */
1027 /* Assume nothing will change this iteration of the loop. */
1030 /* We want to assign the same IDs each iteration of this loop, so
1031 start counting from zero each iteration of the loop. */
1034 /* We're at the start of the funtion each iteration through the
1035 loop, so we're copying arguments. */
1036 copying_arguments
= 1;
1038 /* Wipe the potential alias information clean for this pass. */
1039 bzero ((char *) new_reg_base_value
, reg_base_value_size
* sizeof (rtx
));
1041 /* Wipe the reg_seen array clean. */
1042 bzero ((char *) reg_seen
, reg_base_value_size
);
1044 /* Mark all hard registers which may contain an address.
1045 The stack, frame and argument pointers may contain an address.
1046 An argument register which can hold a Pmode value may contain
1047 an address even if it is not in BASE_REGS.
1049 The address expression is VOIDmode for an argument and
1050 Pmode for other registers. */
1052 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1053 if (TEST_HARD_REG_BIT (argument_registers
, i
))
1054 new_reg_base_value
[i
] = gen_rtx_ADDRESS (VOIDmode
,
1055 gen_rtx_REG (Pmode
, i
));
1057 new_reg_base_value
[STACK_POINTER_REGNUM
]
1058 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
1059 new_reg_base_value
[ARG_POINTER_REGNUM
]
1060 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
1061 new_reg_base_value
[FRAME_POINTER_REGNUM
]
1062 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
1063 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1064 new_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
1065 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
1067 if (struct_value_incoming_rtx
1068 && GET_CODE (struct_value_incoming_rtx
) == REG
)
1069 new_reg_base_value
[REGNO (struct_value_incoming_rtx
)]
1070 = gen_rtx_ADDRESS (Pmode
, struct_value_incoming_rtx
);
1072 if (static_chain_rtx
1073 && GET_CODE (static_chain_rtx
) == REG
)
1074 new_reg_base_value
[REGNO (static_chain_rtx
)]
1075 = gen_rtx_ADDRESS (Pmode
, static_chain_rtx
);
1077 /* Walk the insns adding values to the new_reg_base_value array. */
1078 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1080 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1083 /* If this insn has a noalias note, process it, Otherwise,
1084 scan for sets. A simple set will have no side effects
1085 which could change the base value of any other register. */
1087 if (GET_CODE (PATTERN (insn
)) == SET
1088 && (find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
)))
1089 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
);
1091 note_stores (PATTERN (insn
), record_set
);
1093 set
= single_set (insn
);
1096 && GET_CODE (SET_DEST (set
)) == REG
1097 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
1098 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
1099 && REG_N_SETS (REGNO (SET_DEST (set
))) == 1)
1100 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
1101 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
)
1103 int regno
= REGNO (SET_DEST (set
));
1104 reg_known_value
[regno
] = XEXP (note
, 0);
1105 reg_known_equiv_p
[regno
] = REG_NOTE_KIND (note
) == REG_EQUIV
;
1108 else if (GET_CODE (insn
) == NOTE
1109 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
1110 copying_arguments
= 0;
1113 /* Now propagate values from new_reg_base_value to reg_base_value. */
1114 for (i
= 0; i
< reg_base_value_size
; i
++)
1116 if (new_reg_base_value
[i
]
1117 && new_reg_base_value
[i
] != reg_base_value
[i
]
1118 && ! rtx_equal_p (new_reg_base_value
[i
], reg_base_value
[i
]))
1120 reg_base_value
[i
] = new_reg_base_value
[i
];
1125 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
1127 /* Fill in the remaining entries. */
1128 for (i
= FIRST_PSEUDO_REGISTER
; i
< maxreg
; i
++)
1129 if (reg_known_value
[i
] == 0)
1130 reg_known_value
[i
] = regno_reg_rtx
[i
];
1132 /* Simplify the reg_base_value array so that no register refers to
1133 another register, except to special registers indirectly through
1134 ADDRESS expressions.
1136 In theory this loop can take as long as O(registers^2), but unless
1137 there are very long dependency chains it will run in close to linear
1140 This loop may not be needed any longer now that the main loop does
1141 a better job at propagating alias information. */
1147 for (i
= 0; i
< reg_base_value_size
; i
++)
1149 rtx base
= reg_base_value
[i
];
1150 if (base
&& GET_CODE (base
) == REG
)
1152 int base_regno
= REGNO (base
);
1153 if (base_regno
== i
) /* register set from itself */
1154 reg_base_value
[i
] = 0;
1156 reg_base_value
[i
] = reg_base_value
[base_regno
];
1161 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
1163 new_reg_base_value
= 0;
1168 end_alias_analysis ()
1170 reg_known_value
= 0;
1172 reg_base_value_size
= 0;