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. */
26 #include "hard-reg-set.h"
29 static rtx canon_rtx PROTO((rtx));
30 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
31 static rtx find_symbolic_term PROTO((rtx));
32 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
35 /* Set up all info needed to perform alias analysis on memory references. */
37 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
39 /* Cap the number of passes we make over the insns propagating alias
40 information through set chains.
42 10 is a completely arbitrary choice. */
43 #define MAX_ALIAS_LOOP_PASSES 10
45 /* reg_base_value[N] gives an address to which register N is related.
46 If all sets after the first add or subtract to the current value
47 or otherwise modify it so it does not point to a different top level
48 object, reg_base_value[N] is equal to the address part of the source
51 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
52 expressions represent certain special values: function arguments and
53 the stack, frame, and argument pointers. The contents of an address
54 expression are not used (but they are descriptive for debugging);
55 only the address and mode matter. Pointer equality, not rtx_equal_p,
56 determines whether two ADDRESS expressions refer to the same base
57 address. The mode determines whether it is a function argument or
58 other special value. */
61 rtx *new_reg_base_value;
62 unsigned int reg_base_value_size; /* size of reg_base_value array */
63 #define REG_BASE_VALUE(X) \
64 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
66 /* Vector indexed by N giving the initial (unchanging) value known
67 for pseudo-register N. */
70 /* Indicates number of valid entries in reg_known_value. */
71 static int reg_known_value_size;
73 /* Vector recording for each reg_known_value whether it is due to a
74 REG_EQUIV note. Future passes (viz., reload) may replace the
75 pseudo with the equivalent expression and so we account for the
76 dependences that would be introduced if that happens. */
77 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
78 assign_parms mention the arg pointer, and there are explicit insns in the
79 RTL that modify the arg pointer. Thus we must ensure that such insns don't
80 get scheduled across each other because that would invalidate the REG_EQUIV
81 notes. One could argue that the REG_EQUIV notes are wrong, but solving
82 the problem in the scheduler will likely give better code, so we do it
84 char *reg_known_equiv_p;
86 /* True when scanning insns from the start of the rtl to the
87 NOTE_INSN_FUNCTION_BEG note. */
89 static int copying_arguments;
91 /* Inside SRC, the source of a SET, find a base address. */
97 switch (GET_CODE (src))
104 /* At the start of a function argument registers have known base
105 values which may be lost later. Returning an ADDRESS
106 expression here allows optimization based on argument values
107 even when the argument registers are used for other purposes. */
108 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
109 return new_reg_base_value[REGNO (src)];
111 /* If a pseudo has a known base value, return it. Do not do this
112 for hard regs since it can result in a circular dependency
113 chain for registers which have values at function entry.
115 The test above is not sufficient because the scheduler may move
116 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
117 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
118 && reg_base_value[REGNO (src)])
119 return reg_base_value[REGNO (src)];
124 /* Check for an argument passed in memory. Only record in the
125 copying-arguments block; it is too hard to track changes
127 if (copying_arguments
128 && (XEXP (src, 0) == arg_pointer_rtx
129 || (GET_CODE (XEXP (src, 0)) == PLUS
130 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
131 return gen_rtx_ADDRESS (VOIDmode, src);
136 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
143 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
145 /* If either operand is a REG, then see if we already have
146 a known value for it. */
147 if (GET_CODE (src_0) == REG)
149 temp = find_base_value (src_0);
154 if (GET_CODE (src_1) == REG)
156 temp = find_base_value (src_1);
161 /* Guess which operand is the base address.
163 If either operand is a symbol, then it is the base. If
164 either operand is a CONST_INT, then the other is the base. */
166 if (GET_CODE (src_1) == CONST_INT
167 || GET_CODE (src_0) == SYMBOL_REF
168 || GET_CODE (src_0) == LABEL_REF
169 || GET_CODE (src_0) == CONST)
170 return find_base_value (src_0);
172 if (GET_CODE (src_0) == CONST_INT
173 || GET_CODE (src_1) == SYMBOL_REF
174 || GET_CODE (src_1) == LABEL_REF
175 || GET_CODE (src_1) == CONST)
176 return find_base_value (src_1);
178 /* This might not be necessary anymore.
180 If either operand is a REG that is a known pointer, then it
182 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
183 return find_base_value (src_0);
185 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
186 return find_base_value (src_1);
192 /* The standard form is (lo_sum reg sym) so look only at the
194 return find_base_value (XEXP (src, 1));
197 /* If the second operand is constant set the base
198 address to the first operand. */
199 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
200 return find_base_value (XEXP (src, 0));
204 return find_base_value (XEXP (src, 0));
213 /* Called from init_alias_analysis indirectly through note_stores. */
215 /* while scanning insns to find base values, reg_seen[N] is nonzero if
216 register N has been set in this function. */
217 static char *reg_seen;
220 static int unique_id;
223 record_set (dest, set)
229 if (GET_CODE (dest) != REG)
232 regno = REGNO (dest);
236 /* A CLOBBER wipes out any old value but does not prevent a previously
237 unset register from acquiring a base address (i.e. reg_seen is not
239 if (GET_CODE (set) == CLOBBER)
241 new_reg_base_value[regno] = 0;
250 new_reg_base_value[regno] = 0;
254 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
255 GEN_INT (unique_id++));
259 /* This is not the first set. If the new value is not related to the
260 old value, forget the base value. Note that the following code is
262 extern int x, y; int *p = &x; p += (&y-&x);
263 ANSI C does not allow computing the difference of addresses
264 of distinct top level objects. */
265 if (new_reg_base_value[regno])
266 switch (GET_CODE (src))
271 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
272 new_reg_base_value[regno] = 0;
275 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
276 new_reg_base_value[regno] = 0;
279 new_reg_base_value[regno] = 0;
282 /* If this is the first set of a register, record the value. */
283 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
284 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
285 new_reg_base_value[regno] = find_base_value (src);
290 /* Called from loop optimization when a new pseudo-register is created. */
292 record_base_value (regno, val)
296 if (regno >= reg_base_value_size)
298 if (GET_CODE (val) == REG)
300 if (REGNO (val) < reg_base_value_size)
301 reg_base_value[regno] = reg_base_value[REGNO (val)];
304 reg_base_value[regno] = find_base_value (val);
311 /* Recursively look for equivalences. */
312 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
313 && REGNO (x) < reg_known_value_size)
314 return reg_known_value[REGNO (x)] == x
315 ? x : canon_rtx (reg_known_value[REGNO (x)]);
316 else if (GET_CODE (x) == PLUS)
318 rtx x0 = canon_rtx (XEXP (x, 0));
319 rtx x1 = canon_rtx (XEXP (x, 1));
321 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
323 /* We can tolerate LO_SUMs being offset here; these
324 rtl are used for nothing other than comparisons. */
325 if (GET_CODE (x0) == CONST_INT)
326 return plus_constant_for_output (x1, INTVAL (x0));
327 else if (GET_CODE (x1) == CONST_INT)
328 return plus_constant_for_output (x0, INTVAL (x1));
329 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
332 /* This gives us much better alias analysis when called from
333 the loop optimizer. Note we want to leave the original
334 MEM alone, but need to return the canonicalized MEM with
335 all the flags with their original values. */
336 else if (GET_CODE (x) == MEM)
338 rtx addr = canon_rtx (XEXP (x, 0));
339 if (addr != XEXP (x, 0))
341 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
342 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
343 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
344 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
351 /* Return 1 if X and Y are identical-looking rtx's.
353 We use the data in reg_known_value above to see if two registers with
354 different numbers are, in fact, equivalent. */
357 rtx_equal_for_memref_p (x, y)
362 register enum rtx_code code;
365 if (x == 0 && y == 0)
367 if (x == 0 || y == 0)
376 /* Rtx's of different codes cannot be equal. */
377 if (code != GET_CODE (y))
380 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
381 (REG:SI x) and (REG:HI x) are NOT equivalent. */
383 if (GET_MODE (x) != GET_MODE (y))
386 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
389 return REGNO (x) == REGNO (y);
390 if (code == LABEL_REF)
391 return XEXP (x, 0) == XEXP (y, 0);
392 if (code == SYMBOL_REF)
393 return XSTR (x, 0) == XSTR (y, 0);
395 /* For commutative operations, the RTX match if the operand match in any
396 order. Also handle the simple binary and unary cases without a loop. */
397 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
398 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
399 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
400 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
401 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
402 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
403 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
404 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
405 else if (GET_RTX_CLASS (code) == '1')
406 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
408 /* Compare the elements. If any pair of corresponding elements
409 fail to match, return 0 for the whole things. */
411 fmt = GET_RTX_FORMAT (code);
412 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
417 if (XWINT (x, i) != XWINT (y, i))
423 if (XINT (x, i) != XINT (y, i))
429 /* Two vectors must have the same length. */
430 if (XVECLEN (x, i) != XVECLEN (y, i))
433 /* And the corresponding elements must match. */
434 for (j = 0; j < XVECLEN (x, i); j++)
435 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
440 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
446 if (strcmp (XSTR (x, i), XSTR (y, i)))
451 /* These are just backpointers, so they don't matter. */
457 /* It is believed that rtx's at this level will never
458 contain anything but integers and other rtx's,
459 except for within LABEL_REFs and SYMBOL_REFs. */
467 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
468 X and return it, or return 0 if none found. */
471 find_symbolic_term (x)
475 register enum rtx_code code;
479 if (code == SYMBOL_REF || code == LABEL_REF)
481 if (GET_RTX_CLASS (code) == 'o')
484 fmt = GET_RTX_FORMAT (code);
485 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
491 t = find_symbolic_term (XEXP (x, i));
495 else if (fmt[i] == 'E')
505 switch (GET_CODE (x))
508 return REG_BASE_VALUE (x);
511 return find_base_term (XEXP (x, 0));
517 return find_base_term (XEXP (x, 0));
521 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
528 rtx tmp = find_base_term (XEXP (x, 0));
531 return find_base_term (XEXP (x, 1));
535 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
536 return REG_BASE_VALUE (XEXP (x, 0));
548 /* Return 0 if the addresses X and Y are known to point to different
549 objects, 1 if they might be pointers to the same object. */
552 base_alias_check (x, y)
555 rtx x_base = find_base_term (x);
556 rtx y_base = find_base_term (y);
558 /* If the address itself has no known base see if a known equivalent
559 value has one. If either address still has no known base, nothing
560 is known about aliasing. */
564 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
566 x_base = find_base_term (x_c);
574 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
576 y_base = find_base_term (y_c);
581 /* If the base addresses are equal nothing is known about aliasing. */
582 if (rtx_equal_p (x_base, y_base))
585 /* The base addresses of the read and write are different
586 expressions. If they are both symbols and they are not accessed
587 via AND, there is no conflict. */
588 /* XXX: We can bring knowledge of object alignment and offset into
589 play here. For example, on alpha, "char a, b;" can alias one
590 another, though "char a; long b;" cannot. Similarly, offsets
591 into strutures may be brought into play. Given "char a, b[40];",
592 a and b[1] may overlap, but a and b[20] do not. */
593 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
595 return GET_CODE (x) == AND || GET_CODE (y) == AND;
598 /* If one address is a stack reference there can be no alias:
599 stack references using different base registers do not alias,
600 a stack reference can not alias a parameter, and a stack reference
601 can not alias a global. */
602 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
603 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
606 if (! flag_argument_noalias)
609 if (flag_argument_noalias > 1)
612 /* Weak noalias assertion (arguments are distinct, but may match globals). */
613 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
616 /* Return nonzero if X and Y (memory addresses) could reference the
617 same location in memory. C is an offset accumulator. When
618 C is nonzero, we are testing aliases between X and Y + C.
619 XSIZE is the size in bytes of the X reference,
620 similarly YSIZE is the size in bytes for Y.
622 If XSIZE or YSIZE is zero, we do not know the amount of memory being
623 referenced (the reference was BLKmode), so make the most pessimistic
626 If XSIZE or YSIZE is negative, we may access memory outside the object
627 being referenced as a side effect. This can happen when using AND to
628 align memory references, as is done on the Alpha.
630 Nice to notice that varying addresses cannot conflict with fp if no
631 local variables had their addresses taken, but that's too hard now. */
635 memrefs_conflict_p (xsize, x, ysize, y, c)
640 if (GET_CODE (x) == HIGH)
642 else if (GET_CODE (x) == LO_SUM)
646 if (GET_CODE (y) == HIGH)
648 else if (GET_CODE (y) == LO_SUM)
653 if (rtx_equal_for_memref_p (x, y))
655 if (xsize <= 0 || ysize <= 0)
657 if (c >= 0 && xsize > c)
659 if (c < 0 && ysize+c > 0)
664 /* This code used to check for conflicts involving stack references and
665 globals but the base address alias code now handles these cases. */
667 if (GET_CODE (x) == PLUS)
669 /* The fact that X is canonicalized means that this
670 PLUS rtx is canonicalized. */
671 rtx x0 = XEXP (x, 0);
672 rtx x1 = XEXP (x, 1);
674 if (GET_CODE (y) == PLUS)
676 /* The fact that Y is canonicalized means that this
677 PLUS rtx is canonicalized. */
678 rtx y0 = XEXP (y, 0);
679 rtx y1 = XEXP (y, 1);
681 if (rtx_equal_for_memref_p (x1, y1))
682 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
683 if (rtx_equal_for_memref_p (x0, y0))
684 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
685 if (GET_CODE (x1) == CONST_INT)
686 if (GET_CODE (y1) == CONST_INT)
687 return memrefs_conflict_p (xsize, x0, ysize, y0,
688 c - INTVAL (x1) + INTVAL (y1));
690 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
691 else if (GET_CODE (y1) == CONST_INT)
692 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
696 else if (GET_CODE (x1) == CONST_INT)
697 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
699 else if (GET_CODE (y) == PLUS)
701 /* The fact that Y is canonicalized means that this
702 PLUS rtx is canonicalized. */
703 rtx y0 = XEXP (y, 0);
704 rtx y1 = XEXP (y, 1);
706 if (GET_CODE (y1) == CONST_INT)
707 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
712 if (GET_CODE (x) == GET_CODE (y))
713 switch (GET_CODE (x))
717 /* Handle cases where we expect the second operands to be the
718 same, and check only whether the first operand would conflict
721 rtx x1 = canon_rtx (XEXP (x, 1));
722 rtx y1 = canon_rtx (XEXP (y, 1));
723 if (! rtx_equal_for_memref_p (x1, y1))
725 x0 = canon_rtx (XEXP (x, 0));
726 y0 = canon_rtx (XEXP (y, 0));
727 if (rtx_equal_for_memref_p (x0, y0))
728 return (xsize == 0 || ysize == 0
729 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
731 /* Can't properly adjust our sizes. */
732 if (GET_CODE (x1) != CONST_INT)
734 xsize /= INTVAL (x1);
735 ysize /= INTVAL (x1);
737 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
744 /* Treat an access through an AND (e.g. a subword access on an Alpha)
745 as an access with indeterminate size.
746 ??? Could instead convert an n byte reference at (and x y) to an
747 n-y byte reference at (plus x y). */
748 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
749 return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
750 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
752 /* XXX: If we are indexing far enough into the array/structure, we
753 may yet be able to determine that we can not overlap. But we
754 also need to that we are far enough from the end not to overlap
755 a following reference, so we do nothing for now. */
756 return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
761 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
763 c += (INTVAL (y) - INTVAL (x));
764 return (xsize <= 0 || ysize <= 0
765 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
768 if (GET_CODE (x) == CONST)
770 if (GET_CODE (y) == CONST)
771 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
772 ysize, canon_rtx (XEXP (y, 0)), c);
774 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
777 if (GET_CODE (y) == CONST)
778 return memrefs_conflict_p (xsize, x, ysize,
779 canon_rtx (XEXP (y, 0)), c);
782 return (xsize < 0 || ysize < 0
783 || (rtx_equal_for_memref_p (x, y)
784 && (xsize == 0 || ysize == 0
785 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
792 /* Functions to compute memory dependencies.
794 Since we process the insns in execution order, we can build tables
795 to keep track of what registers are fixed (and not aliased), what registers
796 are varying in known ways, and what registers are varying in unknown
799 If both memory references are volatile, then there must always be a
800 dependence between the two references, since their order can not be
801 changed. A volatile and non-volatile reference can be interchanged
804 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
805 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
806 allow QImode aliasing because the ANSI C standard allows character
807 pointers to alias anything. We are assuming that characters are
808 always QImode here. We also must allow AND addresses, because they may
809 generate accesses outside the object being referenced. This is used to
810 generate aligned addresses from unaligned addresses, for instance, the
811 alpha storeqi_unaligned pattern. */
813 /* Read dependence: X is read after read in MEM takes place. There can
814 only be a dependence here if both reads are volatile. */
817 read_dependence (mem, x)
821 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
824 /* True dependence: X is read after store in MEM takes place. */
827 true_dependence (mem, mem_mode, x, varies)
829 enum machine_mode mem_mode;
833 register rtx x_addr, mem_addr;
835 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
838 /* If X is an unchanging read, then it can't possibly conflict with any
839 non-unchanging store. It may conflict with an unchanging write though,
840 because there may be a single store to this address to initialize it.
841 Just fall through to the code below to resolve the case where we have
842 both an unchanging read and an unchanging write. This won't handle all
843 cases optimally, but the possible performance loss should be
845 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
848 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
851 x_addr = canon_rtx (XEXP (x, 0));
852 mem_addr = canon_rtx (XEXP (mem, 0));
854 if (mem_mode == VOIDmode)
855 mem_mode = GET_MODE (mem);
857 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
858 SIZE_FOR_MODE (x), x_addr, 0))
861 /* If both references are struct references, or both are not, nothing
862 is known about aliasing.
864 If either reference is QImode or BLKmode, ANSI C permits aliasing.
866 If both addresses are constant, or both are not, nothing is known
868 if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
869 || mem_mode == QImode || mem_mode == BLKmode
870 || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
871 || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
872 || varies (x_addr) == varies (mem_addr))
875 /* One memory reference is to a constant address, one is not.
876 One is to a structure, the other is not.
878 If either memory reference is a variable structure the other is a
879 fixed scalar and there is no aliasing. */
880 if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
881 || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
887 /* Anti dependence: X is written after read in MEM takes place. */
890 anti_dependence (mem, x)
894 rtx x_addr, mem_addr;
896 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
899 /* If MEM is an unchanging read, then it can't possibly conflict with
900 the store to X, because there is at most one store to MEM, and it must
901 have occurred somewhere before MEM. */
902 if (RTX_UNCHANGING_P (mem))
905 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
909 mem = canon_rtx (mem);
911 x_addr = XEXP (x, 0);
912 mem_addr = XEXP (mem, 0);
914 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
915 SIZE_FOR_MODE (x), x_addr, 0)
916 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
917 && GET_MODE (mem) != QImode
918 && GET_CODE (mem_addr) != AND
919 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
920 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
921 && GET_MODE (x) != QImode
922 && GET_CODE (x_addr) != AND
923 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
926 /* Output dependence: X is written after store in MEM takes place. */
929 output_dependence (mem, x)
933 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
936 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
940 mem = canon_rtx (mem);
942 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
943 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
944 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
945 && GET_MODE (mem) != QImode
946 && GET_CODE (XEXP (mem, 0)) != AND
947 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
948 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
949 && GET_MODE (x) != QImode
950 && GET_CODE (XEXP (x, 0)) != AND
951 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
955 static HARD_REG_SET argument_registers;
962 #ifndef OUTGOING_REGNO
963 #define OUTGOING_REGNO(N) N
965 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
966 /* Check whether this register can hold an incoming pointer
967 argument. FUNCTION_ARG_REGNO_P tests outgoing register
968 numbers, so translate if necessary due to register windows. */
969 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
970 && HARD_REGNO_MODE_OK (i, Pmode))
971 SET_HARD_REG_BIT (argument_registers, i);
975 init_alias_analysis ()
977 int maxreg = max_reg_num ();
982 reg_known_value_size = maxreg;
985 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
986 - FIRST_PSEUDO_REGISTER;
988 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
989 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
990 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
991 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
992 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
994 /* Overallocate reg_base_value to allow some growth during loop
995 optimization. Loop unrolling can create a large number of
997 reg_base_value_size = maxreg * 2;
998 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
999 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1000 reg_seen = (char *)alloca (reg_base_value_size);
1001 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1003 /* The basic idea is that each pass through this loop will use the
1004 "constant" information from the previous pass to propagate alias
1005 information through another level of assignments.
1007 This could get expensive if the assignment chains are long. Maybe
1008 we should throttle the number of iterations, possibly based on
1009 the optimization level or flag_expensive_optimizations.
1011 We could propagate more information in the first pass by making use
1012 of REG_N_SETS to determine immediately that the alias information
1013 for a pseudo is "constant".
1015 A program with an uninitialized variable can cause an infinite loop
1016 here. Instead of doing a full dataflow analysis to detect such problems
1017 we just cap the number of iterations for the loop.
1019 The state of the arrays for the set chain in question does not matter
1020 since the program has undefined behavior. */
1025 /* Assume nothing will change this iteration of the loop. */
1028 /* We want to assign the same IDs each iteration of this loop, so
1029 start counting from zero each iteration of the loop. */
1032 /* We're at the start of the funtion each iteration through the
1033 loop, so we're copying arguments. */
1034 copying_arguments = 1;
1036 /* Wipe the potential alias information clean for this pass. */
1037 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1039 /* Wipe the reg_seen array clean. */
1040 bzero ((char *) reg_seen, reg_base_value_size);
1042 /* Mark all hard registers which may contain an address.
1043 The stack, frame and argument pointers may contain an address.
1044 An argument register which can hold a Pmode value may contain
1045 an address even if it is not in BASE_REGS.
1047 The address expression is VOIDmode for an argument and
1048 Pmode for other registers. */
1050 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1051 if (TEST_HARD_REG_BIT (argument_registers, i))
1052 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1053 gen_rtx_REG (Pmode, i));
1055 new_reg_base_value[STACK_POINTER_REGNUM]
1056 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1057 new_reg_base_value[ARG_POINTER_REGNUM]
1058 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1059 new_reg_base_value[FRAME_POINTER_REGNUM]
1060 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1061 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1062 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1063 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1065 if (struct_value_incoming_rtx
1066 && GET_CODE (struct_value_incoming_rtx) == REG)
1067 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1068 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1070 if (static_chain_rtx
1071 && GET_CODE (static_chain_rtx) == REG)
1072 new_reg_base_value[REGNO (static_chain_rtx)]
1073 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1075 /* Walk the insns adding values to the new_reg_base_value array. */
1076 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1078 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1081 /* If this insn has a noalias note, process it, Otherwise,
1082 scan for sets. A simple set will have no side effects
1083 which could change the base value of any other register. */
1085 if (GET_CODE (PATTERN (insn)) == SET
1086 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1087 record_set (SET_DEST (PATTERN (insn)), 0);
1089 note_stores (PATTERN (insn), record_set);
1091 set = single_set (insn);
1094 && GET_CODE (SET_DEST (set)) == REG
1095 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1096 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1097 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1098 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1099 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1101 int regno = REGNO (SET_DEST (set));
1102 reg_known_value[regno] = XEXP (note, 0);
1103 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1106 else if (GET_CODE (insn) == NOTE
1107 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1108 copying_arguments = 0;
1111 /* Now propagate values from new_reg_base_value to reg_base_value. */
1112 for (i = 0; i < reg_base_value_size; i++)
1114 if (new_reg_base_value[i]
1115 && new_reg_base_value[i] != reg_base_value[i]
1116 && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1118 reg_base_value[i] = new_reg_base_value[i];
1123 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1125 /* Fill in the remaining entries. */
1126 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1127 if (reg_known_value[i] == 0)
1128 reg_known_value[i] = regno_reg_rtx[i];
1130 /* Simplify the reg_base_value array so that no register refers to
1131 another register, except to special registers indirectly through
1132 ADDRESS expressions.
1134 In theory this loop can take as long as O(registers^2), but unless
1135 there are very long dependency chains it will run in close to linear
1138 This loop may not be needed any longer now that the main loop does
1139 a better job at propagating alias information. */
1145 for (i = 0; i < reg_base_value_size; i++)
1147 rtx base = reg_base_value[i];
1148 if (base && GET_CODE (base) == REG)
1150 int base_regno = REGNO (base);
1151 if (base_regno == i) /* register set from itself */
1152 reg_base_value[i] = 0;
1154 reg_base_value[i] = reg_base_value[base_regno];
1159 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1161 new_reg_base_value = 0;
1166 end_alias_analysis ()
1168 reg_known_value = 0;
1170 reg_base_value_size = 0;