1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999 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 #include "splay-tree.h"
33 /* The alias sets assigned to MEMs assist the back-end in determining
34 which MEMs can alias which other MEMs. In general, two MEMs in
35 different alias sets to not alias each other. There is one
36 exception, however. Consider something like:
38 struct S {int i; double d; };
40 a store to an `S' can alias something of either type `int' or type
41 `double'. (However, a store to an `int' cannot alias a `double'
42 and vice versa.) We indicate this via a tree structure that looks
50 (The arrows are directed and point downwards.) If, when comparing
51 two alias sets, we can hold one set fixed, and trace the other set
52 downwards, and at some point find the first set, the two MEMs can
53 alias one another. In this situation we say the alias set for
54 `struct S' is the `superset' and that those for `int' and `double'
57 Alias set zero is implicitly a superset of all other alias sets.
58 However, this is no actual entry for alias set zero. It is an
59 error to attempt to explicitly construct a subset of zero. */
61 typedef struct alias_set_entry {
62 /* The alias set number, as stored in MEM_ALIAS_SET. */
65 /* The children of the alias set. These are not just the immediate
66 children, but, in fact, all children. So, if we have:
68 struct T { struct S s; float f; }
70 continuing our example above, the children here will be all of
71 `int', `double', `float', and `struct S'. */
75 static rtx canon_rtx PROTO((rtx));
76 static int rtx_equal_for_memref_p PROTO((rtx, rtx));
77 static rtx find_symbolic_term PROTO((rtx));
78 static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
80 static void record_set PROTO((rtx, rtx));
81 static rtx find_base_term PROTO((rtx));
82 static int base_alias_check PROTO((rtx, rtx, enum machine_mode,
84 static rtx find_base_value PROTO((rtx));
85 static int mems_in_disjoint_alias_sets_p PROTO((rtx, rtx));
86 static int alias_set_compare PROTO((splay_tree_key,
88 static int insert_subset_children PROTO((splay_tree_node,
90 static alias_set_entry get_alias_set_entry PROTO((int));
92 /* Set up all info needed to perform alias analysis on memory references. */
94 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
96 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
97 different alias sets. We ignore alias sets in functions making use
98 of variable arguments because the va_arg macros on some systems are
100 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
101 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
103 /* Cap the number of passes we make over the insns propagating alias
104 information through set chains.
106 10 is a completely arbitrary choice. */
107 #define MAX_ALIAS_LOOP_PASSES 10
109 /* reg_base_value[N] gives an address to which register N is related.
110 If all sets after the first add or subtract to the current value
111 or otherwise modify it so it does not point to a different top level
112 object, reg_base_value[N] is equal to the address part of the source
115 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
116 expressions represent certain special values: function arguments and
117 the stack, frame, and argument pointers. The contents of an address
118 expression are not used (but they are descriptive for debugging);
119 only the address and mode matter. Pointer equality, not rtx_equal_p,
120 determines whether two ADDRESS expressions refer to the same base
121 address. The mode determines whether it is a function argument or
122 other special value. */
125 rtx *new_reg_base_value;
126 unsigned int reg_base_value_size; /* size of reg_base_value array */
127 #define REG_BASE_VALUE(X) \
128 ((unsigned) REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
130 /* Vector of known invariant relationships between registers. Set in
131 loop unrolling. Indexed by register number, if nonzero the value
132 is an expression describing this register in terms of another.
134 The length of this array is REG_BASE_VALUE_SIZE.
136 Because this array contains only pseudo registers it has no effect
138 static rtx *alias_invariant;
140 /* Vector indexed by N giving the initial (unchanging) value known
141 for pseudo-register N. */
142 rtx *reg_known_value;
144 /* Indicates number of valid entries in reg_known_value. */
145 static int reg_known_value_size;
147 /* Vector recording for each reg_known_value whether it is due to a
148 REG_EQUIV note. Future passes (viz., reload) may replace the
149 pseudo with the equivalent expression and so we account for the
150 dependences that would be introduced if that happens. */
151 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
152 assign_parms mention the arg pointer, and there are explicit insns in the
153 RTL that modify the arg pointer. Thus we must ensure that such insns don't
154 get scheduled across each other because that would invalidate the REG_EQUIV
155 notes. One could argue that the REG_EQUIV notes are wrong, but solving
156 the problem in the scheduler will likely give better code, so we do it
158 char *reg_known_equiv_p;
160 /* True when scanning insns from the start of the rtl to the
161 NOTE_INSN_FUNCTION_BEG note. */
163 static int copying_arguments;
165 /* The splay-tree used to store the various alias set entries. */
167 static splay_tree alias_sets;
169 /* Returns -1, 0, 1 according to whether SET1 is less than, equal to,
170 or greater than SET2. */
173 alias_set_compare (set1, set2)
188 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
189 such an entry, or NULL otherwise. */
191 static alias_set_entry
192 get_alias_set_entry (alias_set)
196 splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
198 return sn ? ((alias_set_entry) sn->value) : ((alias_set_entry) 0);
201 /* Returns nonzero value if the alias sets for MEM1 and MEM2 are such
202 that the two MEMs cannot alias each other. */
205 mems_in_disjoint_alias_sets_p (mem1, mem2)
211 #ifdef ENABLE_CHECKING
212 /* Perform a basic sanity check. Namely, that there are no alias sets
213 if we're not using strict aliasing. This helps to catch bugs
214 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
215 where a MEM is allocated in some way other than by the use of
216 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
217 use alias sets to indicate that spilled registers cannot alias each
218 other, we might need to remove this check. */
219 if (!flag_strict_aliasing &&
220 (MEM_ALIAS_SET (mem1) || MEM_ALIAS_SET (mem2)))
224 /* The code used in varargs macros are often not conforming ANSI C,
225 which can trick the compiler into making incorrect aliasing
226 assumptions in these functions. So, we don't use alias sets in
227 such a function. FIXME: This should be moved into the front-end;
228 it is a language-dependent notion, and there's no reason not to
229 still use these checks to handle globals. */
230 if (current_function_stdarg || current_function_varargs)
233 if (!MEM_ALIAS_SET (mem1) || !MEM_ALIAS_SET (mem2))
234 /* We have no alias set information for one of the MEMs, so we
235 have to assume it can alias anything. */
238 if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2))
239 /* The two alias sets are the same, so they may alias. */
242 /* Iterate through each of the children of the first alias set,
243 comparing it with the second alias set. */
244 ase = get_alias_set_entry (MEM_ALIAS_SET (mem1));
245 if (ase && splay_tree_lookup (ase->children,
246 (splay_tree_key) MEM_ALIAS_SET (mem2)))
249 /* Now do the same, but with the alias sets reversed. */
250 ase = get_alias_set_entry (MEM_ALIAS_SET (mem2));
251 if (ase && splay_tree_lookup (ase->children,
252 (splay_tree_key) MEM_ALIAS_SET (mem1)))
255 /* The two MEMs are in distinct alias sets, and neither one is the
256 child of the other. Therefore, they cannot alias. */
260 /* Insert the NODE into the splay tree given by DATA. Used by
261 record_alias_subset via splay_tree_foreach. */
264 insert_subset_children (node, data)
265 splay_tree_node node;
268 splay_tree_insert ((splay_tree) data,
275 /* Indicate that things in SUBSET can alias things in SUPERSET, but
276 not vice versa. For example, in C, a store to an `int' can alias a
277 structure containing an `int', but not vice versa. Here, the
278 structure would be the SUPERSET and `int' the SUBSET. This
279 function should be called only once per SUPERSET/SUBSET pair. At
280 present any given alias set may only be a subset of one superset.
282 It is illegal for SUPERSET to be zero; everything is implicitly a
283 subset of alias set zero. */
286 record_alias_subset (superset, subset)
290 alias_set_entry superset_entry;
291 alias_set_entry subset_entry;
296 superset_entry = get_alias_set_entry (superset);
299 /* Create an entry for the SUPERSET, so that we have a place to
300 attach the SUBSET. */
302 (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
303 superset_entry->alias_set = superset;
304 superset_entry->children
305 = splay_tree_new (alias_set_compare, 0, 0);
306 splay_tree_insert (alias_sets,
307 (splay_tree_key) superset,
308 (splay_tree_value) superset_entry);
312 subset_entry = get_alias_set_entry (subset);
314 /* There is an entry for the subset. Enter all of its children
315 (if they are not already present) as children of the SUPERSET. */
316 splay_tree_foreach (subset_entry->children,
317 insert_subset_children,
318 superset_entry->children);
320 /* Enter the SUBSET itself as a child of the SUPERSET. */
321 splay_tree_insert (superset_entry->children,
322 (splay_tree_key) subset,
326 /* Inside SRC, the source of a SET, find a base address. */
329 find_base_value (src)
332 switch (GET_CODE (src))
339 /* At the start of a function argument registers have known base
340 values which may be lost later. Returning an ADDRESS
341 expression here allows optimization based on argument values
342 even when the argument registers are used for other purposes. */
343 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
344 return new_reg_base_value[REGNO (src)];
346 /* If a pseudo has a known base value, return it. Do not do this
347 for hard regs since it can result in a circular dependency
348 chain for registers which have values at function entry.
350 The test above is not sufficient because the scheduler may move
351 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
352 if (REGNO (src) >= FIRST_PSEUDO_REGISTER
353 && (unsigned) REGNO (src) < reg_base_value_size
354 && reg_base_value[REGNO (src)])
355 return reg_base_value[REGNO (src)];
360 /* Check for an argument passed in memory. Only record in the
361 copying-arguments block; it is too hard to track changes
363 if (copying_arguments
364 && (XEXP (src, 0) == arg_pointer_rtx
365 || (GET_CODE (XEXP (src, 0)) == PLUS
366 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
367 return gen_rtx_ADDRESS (VOIDmode, src);
372 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
379 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
381 /* If either operand is a REG, then see if we already have
382 a known value for it. */
383 if (GET_CODE (src_0) == REG)
385 temp = find_base_value (src_0);
390 if (GET_CODE (src_1) == REG)
392 temp = find_base_value (src_1);
397 /* Guess which operand is the base address.
399 If either operand is a symbol, then it is the base. If
400 either operand is a CONST_INT, then the other is the base. */
402 if (GET_CODE (src_1) == CONST_INT
403 || GET_CODE (src_0) == SYMBOL_REF
404 || GET_CODE (src_0) == LABEL_REF
405 || GET_CODE (src_0) == CONST)
406 return find_base_value (src_0);
408 if (GET_CODE (src_0) == CONST_INT
409 || GET_CODE (src_1) == SYMBOL_REF
410 || GET_CODE (src_1) == LABEL_REF
411 || GET_CODE (src_1) == CONST)
412 return find_base_value (src_1);
414 /* This might not be necessary anymore.
416 If either operand is a REG that is a known pointer, then it
418 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
419 return find_base_value (src_0);
421 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
422 return find_base_value (src_1);
428 /* The standard form is (lo_sum reg sym) so look only at the
430 return find_base_value (XEXP (src, 1));
433 /* If the second operand is constant set the base
434 address to the first operand. */
435 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
436 return find_base_value (XEXP (src, 0));
440 case SIGN_EXTEND: /* used for NT/Alpha pointers */
442 return find_base_value (XEXP (src, 0));
451 /* Called from init_alias_analysis indirectly through note_stores. */
453 /* while scanning insns to find base values, reg_seen[N] is nonzero if
454 register N has been set in this function. */
455 static char *reg_seen;
457 /* Addresses which are known not to alias anything else are identified
458 by a unique integer. */
459 static int unique_id;
462 record_set (dest, set)
468 if (GET_CODE (dest) != REG)
471 regno = REGNO (dest);
475 /* A CLOBBER wipes out any old value but does not prevent a previously
476 unset register from acquiring a base address (i.e. reg_seen is not
478 if (GET_CODE (set) == CLOBBER)
480 new_reg_base_value[regno] = 0;
489 new_reg_base_value[regno] = 0;
493 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
494 GEN_INT (unique_id++));
498 /* This is not the first set. If the new value is not related to the
499 old value, forget the base value. Note that the following code is
501 extern int x, y; int *p = &x; p += (&y-&x);
502 ANSI C does not allow computing the difference of addresses
503 of distinct top level objects. */
504 if (new_reg_base_value[regno])
505 switch (GET_CODE (src))
510 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
511 new_reg_base_value[regno] = 0;
514 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
515 new_reg_base_value[regno] = 0;
518 new_reg_base_value[regno] = 0;
521 /* If this is the first set of a register, record the value. */
522 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
523 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
524 new_reg_base_value[regno] = find_base_value (src);
529 /* Called from loop optimization when a new pseudo-register is created. */
531 record_base_value (regno, val, invariant)
536 if ((unsigned) regno >= reg_base_value_size)
539 /* If INVARIANT is true then this value also describes an invariant
540 relationship which can be used to deduce that two registers with
541 unknown values are different. */
542 if (invariant && alias_invariant)
543 alias_invariant[regno] = val;
545 if (GET_CODE (val) == REG)
547 if ((unsigned) REGNO (val) < reg_base_value_size)
549 reg_base_value[regno] = reg_base_value[REGNO (val)];
553 reg_base_value[regno] = find_base_value (val);
560 /* Recursively look for equivalences. */
561 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
562 && REGNO (x) < reg_known_value_size)
563 return reg_known_value[REGNO (x)] == x
564 ? x : canon_rtx (reg_known_value[REGNO (x)]);
565 else if (GET_CODE (x) == PLUS)
567 rtx x0 = canon_rtx (XEXP (x, 0));
568 rtx x1 = canon_rtx (XEXP (x, 1));
570 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
572 /* We can tolerate LO_SUMs being offset here; these
573 rtl are used for nothing other than comparisons. */
574 if (GET_CODE (x0) == CONST_INT)
575 return plus_constant_for_output (x1, INTVAL (x0));
576 else if (GET_CODE (x1) == CONST_INT)
577 return plus_constant_for_output (x0, INTVAL (x1));
578 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
581 /* This gives us much better alias analysis when called from
582 the loop optimizer. Note we want to leave the original
583 MEM alone, but need to return the canonicalized MEM with
584 all the flags with their original values. */
585 else if (GET_CODE (x) == MEM)
587 rtx addr = canon_rtx (XEXP (x, 0));
588 if (addr != XEXP (x, 0))
590 rtx new = gen_rtx_MEM (GET_MODE (x), addr);
591 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
592 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
593 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
594 MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
601 /* Return 1 if X and Y are identical-looking rtx's.
603 We use the data in reg_known_value above to see if two registers with
604 different numbers are, in fact, equivalent. */
607 rtx_equal_for_memref_p (x, y)
612 register enum rtx_code code;
615 if (x == 0 && y == 0)
617 if (x == 0 || y == 0)
626 /* Rtx's of different codes cannot be equal. */
627 if (code != GET_CODE (y))
630 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
631 (REG:SI x) and (REG:HI x) are NOT equivalent. */
633 if (GET_MODE (x) != GET_MODE (y))
636 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
639 return REGNO (x) == REGNO (y);
640 if (code == LABEL_REF)
641 return XEXP (x, 0) == XEXP (y, 0);
642 if (code == SYMBOL_REF)
643 return XSTR (x, 0) == XSTR (y, 0);
644 if (code == CONST_INT)
645 return INTVAL (x) == INTVAL (y);
646 if (code == ADDRESSOF)
647 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1);
649 /* For commutative operations, the RTX match if the operand match in any
650 order. Also handle the simple binary and unary cases without a loop. */
651 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
652 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
653 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
654 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
655 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
656 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
657 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
658 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
659 else if (GET_RTX_CLASS (code) == '1')
660 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
662 /* Compare the elements. If any pair of corresponding elements
663 fail to match, return 0 for the whole things.
665 Limit cases to types which actually appear in addresses. */
667 fmt = GET_RTX_FORMAT (code);
668 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
673 if (XINT (x, i) != XINT (y, i))
678 /* Two vectors must have the same length. */
679 if (XVECLEN (x, i) != XVECLEN (y, i))
682 /* And the corresponding elements must match. */
683 for (j = 0; j < XVECLEN (x, i); j++)
684 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
689 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
693 /* This can happen for an asm which clobbers memory. */
697 /* It is believed that rtx's at this level will never
698 contain anything but integers and other rtx's,
699 except for within LABEL_REFs and SYMBOL_REFs. */
707 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
708 X and return it, or return 0 if none found. */
711 find_symbolic_term (x)
715 register enum rtx_code code;
719 if (code == SYMBOL_REF || code == LABEL_REF)
721 if (GET_RTX_CLASS (code) == 'o')
724 fmt = GET_RTX_FORMAT (code);
725 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
731 t = find_symbolic_term (XEXP (x, i));
735 else if (fmt[i] == 'E')
745 switch (GET_CODE (x))
748 return REG_BASE_VALUE (x);
751 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
757 return find_base_term (XEXP (x, 0));
761 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
768 rtx tmp = find_base_term (XEXP (x, 0));
771 return find_base_term (XEXP (x, 1));
775 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
776 return REG_BASE_VALUE (XEXP (x, 0));
788 /* Return 0 if the addresses X and Y are known to point to different
789 objects, 1 if they might be pointers to the same object. */
792 base_alias_check (x, y, x_mode, y_mode)
794 enum machine_mode x_mode, y_mode;
796 rtx x_base = find_base_term (x);
797 rtx y_base = find_base_term (y);
799 /* If the address itself has no known base see if a known equivalent
800 value has one. If either address still has no known base, nothing
801 is known about aliasing. */
805 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
807 x_base = find_base_term (x_c);
815 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
817 y_base = find_base_term (y_c);
822 /* If the base addresses are equal nothing is known about aliasing. */
823 if (rtx_equal_p (x_base, y_base))
826 /* The base addresses of the read and write are different expressions.
827 If they are both symbols and they are not accessed via AND, there is
828 no conflict. We can bring knowledge of object alignment into play
829 here. For example, on alpha, "char a, b;" can alias one another,
830 though "char a; long b;" cannot. */
831 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
833 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
835 if (GET_CODE (x) == AND
836 && (GET_CODE (XEXP (x, 1)) != CONST_INT
837 || GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
839 if (GET_CODE (y) == AND
840 && (GET_CODE (XEXP (y, 1)) != CONST_INT
841 || GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
843 /* Differing symbols never alias. */
847 /* If one address is a stack reference there can be no alias:
848 stack references using different base registers do not alias,
849 a stack reference can not alias a parameter, and a stack reference
850 can not alias a global. */
851 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
852 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
855 if (! flag_argument_noalias)
858 if (flag_argument_noalias > 1)
861 /* Weak noalias assertion (arguments are distinct, but may match globals). */
862 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
865 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
866 where SIZE is the size in bytes of the memory reference. If ADDR
867 is not modified by the memory reference then ADDR is returned. */
870 addr_side_effect_eval (addr, size, n_refs)
877 switch (GET_CODE (addr))
880 offset = (n_refs + 1) * size;
883 offset = -(n_refs + 1) * size;
886 offset = n_refs * size;
889 offset = -n_refs * size;
897 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset));
899 addr = XEXP (addr, 0);
904 /* Return nonzero if X and Y (memory addresses) could reference the
905 same location in memory. C is an offset accumulator. When
906 C is nonzero, we are testing aliases between X and Y + C.
907 XSIZE is the size in bytes of the X reference,
908 similarly YSIZE is the size in bytes for Y.
910 If XSIZE or YSIZE is zero, we do not know the amount of memory being
911 referenced (the reference was BLKmode), so make the most pessimistic
914 If XSIZE or YSIZE is negative, we may access memory outside the object
915 being referenced as a side effect. This can happen when using AND to
916 align memory references, as is done on the Alpha.
918 Nice to notice that varying addresses cannot conflict with fp if no
919 local variables had their addresses taken, but that's too hard now. */
923 memrefs_conflict_p (xsize, x, ysize, y, c)
928 if (GET_CODE (x) == HIGH)
930 else if (GET_CODE (x) == LO_SUM)
933 x = canon_rtx (addr_side_effect_eval (x, xsize, 0));
934 if (GET_CODE (y) == HIGH)
936 else if (GET_CODE (y) == LO_SUM)
939 y = canon_rtx (addr_side_effect_eval (y, ysize, 0));
941 if (rtx_equal_for_memref_p (x, y))
943 if (xsize <= 0 || ysize <= 0)
945 if (c >= 0 && xsize > c)
947 if (c < 0 && ysize+c > 0)
952 /* This code used to check for conflicts involving stack references and
953 globals but the base address alias code now handles these cases. */
955 if (GET_CODE (x) == PLUS)
957 /* The fact that X is canonicalized means that this
958 PLUS rtx is canonicalized. */
959 rtx x0 = XEXP (x, 0);
960 rtx x1 = XEXP (x, 1);
962 if (GET_CODE (y) == PLUS)
964 /* The fact that Y is canonicalized means that this
965 PLUS rtx is canonicalized. */
966 rtx y0 = XEXP (y, 0);
967 rtx y1 = XEXP (y, 1);
969 if (rtx_equal_for_memref_p (x1, y1))
970 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
971 if (rtx_equal_for_memref_p (x0, y0))
972 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
973 if (GET_CODE (x1) == CONST_INT)
975 if (GET_CODE (y1) == CONST_INT)
976 return memrefs_conflict_p (xsize, x0, ysize, y0,
977 c - INTVAL (x1) + INTVAL (y1));
979 return memrefs_conflict_p (xsize, x0, ysize, y,
982 else if (GET_CODE (y1) == CONST_INT)
983 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
987 else if (GET_CODE (x1) == CONST_INT)
988 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
990 else if (GET_CODE (y) == PLUS)
992 /* The fact that Y is canonicalized means that this
993 PLUS rtx is canonicalized. */
994 rtx y0 = XEXP (y, 0);
995 rtx y1 = XEXP (y, 1);
997 if (GET_CODE (y1) == CONST_INT)
998 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1003 if (GET_CODE (x) == GET_CODE (y))
1004 switch (GET_CODE (x))
1008 /* Handle cases where we expect the second operands to be the
1009 same, and check only whether the first operand would conflict
1012 rtx x1 = canon_rtx (XEXP (x, 1));
1013 rtx y1 = canon_rtx (XEXP (y, 1));
1014 if (! rtx_equal_for_memref_p (x1, y1))
1016 x0 = canon_rtx (XEXP (x, 0));
1017 y0 = canon_rtx (XEXP (y, 0));
1018 if (rtx_equal_for_memref_p (x0, y0))
1019 return (xsize == 0 || ysize == 0
1020 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1022 /* Can't properly adjust our sizes. */
1023 if (GET_CODE (x1) != CONST_INT)
1025 xsize /= INTVAL (x1);
1026 ysize /= INTVAL (x1);
1028 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1032 /* Are these registers known not to be equal? */
1033 if (alias_invariant)
1035 unsigned int r_x = REGNO (x), r_y = REGNO (y);
1036 rtx i_x, i_y; /* invariant relationships of X and Y */
1038 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
1039 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
1041 if (i_x == 0 && i_y == 0)
1044 if (! memrefs_conflict_p (xsize, i_x ? i_x : x,
1045 ysize, i_y ? i_y : y, c))
1054 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1055 as an access with indeterminate size. Assume that references
1056 besides AND are aligned, so if the size of the other reference is
1057 at least as large as the alignment, assume no other overlap. */
1058 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1060 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1062 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c);
1064 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1066 /* ??? If we are indexing far enough into the array/structure, we
1067 may yet be able to determine that we can not overlap. But we
1068 also need to that we are far enough from the end not to overlap
1069 a following reference, so we do nothing with that for now. */
1070 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1072 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c);
1077 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1079 c += (INTVAL (y) - INTVAL (x));
1080 return (xsize <= 0 || ysize <= 0
1081 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1084 if (GET_CODE (x) == CONST)
1086 if (GET_CODE (y) == CONST)
1087 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1088 ysize, canon_rtx (XEXP (y, 0)), c);
1090 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1093 if (GET_CODE (y) == CONST)
1094 return memrefs_conflict_p (xsize, x, ysize,
1095 canon_rtx (XEXP (y, 0)), c);
1098 return (xsize < 0 || ysize < 0
1099 || (rtx_equal_for_memref_p (x, y)
1100 && (xsize == 0 || ysize == 0
1101 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1108 /* Functions to compute memory dependencies.
1110 Since we process the insns in execution order, we can build tables
1111 to keep track of what registers are fixed (and not aliased), what registers
1112 are varying in known ways, and what registers are varying in unknown
1115 If both memory references are volatile, then there must always be a
1116 dependence between the two references, since their order can not be
1117 changed. A volatile and non-volatile reference can be interchanged
1120 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
1121 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
1122 allow QImode aliasing because the ANSI C standard allows character
1123 pointers to alias anything. We are assuming that characters are
1124 always QImode here. We also must allow AND addresses, because they may
1125 generate accesses outside the object being referenced. This is used to
1126 generate aligned addresses from unaligned addresses, for instance, the
1127 alpha storeqi_unaligned pattern. */
1129 /* Read dependence: X is read after read in MEM takes place. There can
1130 only be a dependence here if both reads are volatile. */
1133 read_dependence (mem, x)
1137 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1140 /* True dependence: X is read after store in MEM takes place. */
1143 true_dependence (mem, mem_mode, x, varies)
1145 enum machine_mode mem_mode;
1147 int (*varies) PROTO((rtx));
1149 register rtx x_addr, mem_addr;
1151 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1154 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1157 /* If X is an unchanging read, then it can't possibly conflict with any
1158 non-unchanging store. It may conflict with an unchanging write though,
1159 because there may be a single store to this address to initialize it.
1160 Just fall through to the code below to resolve the case where we have
1161 both an unchanging read and an unchanging write. This won't handle all
1162 cases optimally, but the possible performance loss should be
1164 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
1167 if (mem_mode == VOIDmode)
1168 mem_mode = GET_MODE (mem);
1170 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), mem_mode))
1173 x_addr = canon_rtx (XEXP (x, 0));
1174 mem_addr = canon_rtx (XEXP (mem, 0));
1176 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
1177 SIZE_FOR_MODE (x), x_addr, 0))
1180 /* If both references are struct references, or both are not, nothing
1181 is known about aliasing.
1183 If either reference is QImode or BLKmode, ANSI C permits aliasing.
1185 If both addresses are constant, or both are not, nothing is known
1187 if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
1188 || mem_mode == QImode || mem_mode == BLKmode
1189 || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
1190 || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
1191 || varies (x_addr) == varies (mem_addr))
1194 /* One memory reference is to a constant address, one is not.
1195 One is to a structure, the other is not.
1197 If either memory reference is a variable structure the other is a
1198 fixed scalar and there is no aliasing. */
1199 if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
1200 || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
1206 /* Anti dependence: X is written after read in MEM takes place. */
1209 anti_dependence (mem, x)
1213 rtx x_addr, mem_addr;
1215 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1218 /* If MEM is an unchanging read, then it can't possibly conflict with
1219 the store to X, because there is at most one store to MEM, and it must
1220 have occurred somewhere before MEM. */
1221 if (RTX_UNCHANGING_P (mem))
1224 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x),
1229 mem = canon_rtx (mem);
1231 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1234 x_addr = XEXP (x, 0);
1235 mem_addr = XEXP (mem, 0);
1237 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
1238 SIZE_FOR_MODE (x), x_addr, 0)
1239 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
1240 && GET_MODE (mem) != QImode
1241 && GET_CODE (mem_addr) != AND
1242 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
1243 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
1244 && GET_MODE (x) != QImode
1245 && GET_CODE (x_addr) != AND
1246 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
1249 /* Output dependence: X is written after store in MEM takes place. */
1252 output_dependence (mem, x)
1256 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
1259 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x),
1264 mem = canon_rtx (mem);
1266 if (DIFFERENT_ALIAS_SETS_P (x, mem))
1269 return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
1270 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
1271 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
1272 && GET_MODE (mem) != QImode
1273 && GET_CODE (XEXP (mem, 0)) != AND
1274 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
1275 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
1276 && GET_MODE (x) != QImode
1277 && GET_CODE (XEXP (x, 0)) != AND
1278 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
1282 static HARD_REG_SET argument_registers;
1289 #ifndef OUTGOING_REGNO
1290 #define OUTGOING_REGNO(N) N
1292 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1293 /* Check whether this register can hold an incoming pointer
1294 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1295 numbers, so translate if necessary due to register windows. */
1296 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
1297 && HARD_REGNO_MODE_OK (i, Pmode))
1298 SET_HARD_REG_BIT (argument_registers, i);
1300 alias_sets = splay_tree_new (alias_set_compare, 0, 0);
1304 init_alias_analysis ()
1306 int maxreg = max_reg_num ();
1309 register unsigned int ui;
1312 reg_known_value_size = maxreg;
1315 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
1316 - FIRST_PSEUDO_REGISTER;
1318 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
1319 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
1320 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
1321 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
1322 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
1324 /* Overallocate reg_base_value to allow some growth during loop
1325 optimization. Loop unrolling can create a large number of
1327 reg_base_value_size = maxreg * 2;
1328 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1329 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1330 reg_seen = (char *)alloca (reg_base_value_size);
1331 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1332 if (! reload_completed && flag_unroll_loops)
1334 alias_invariant = (rtx *)xrealloc (alias_invariant,
1335 reg_base_value_size * sizeof (rtx));
1336 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx));
1340 /* The basic idea is that each pass through this loop will use the
1341 "constant" information from the previous pass to propagate alias
1342 information through another level of assignments.
1344 This could get expensive if the assignment chains are long. Maybe
1345 we should throttle the number of iterations, possibly based on
1346 the optimization level or flag_expensive_optimizations.
1348 We could propagate more information in the first pass by making use
1349 of REG_N_SETS to determine immediately that the alias information
1350 for a pseudo is "constant".
1352 A program with an uninitialized variable can cause an infinite loop
1353 here. Instead of doing a full dataflow analysis to detect such problems
1354 we just cap the number of iterations for the loop.
1356 The state of the arrays for the set chain in question does not matter
1357 since the program has undefined behavior. */
1362 /* Assume nothing will change this iteration of the loop. */
1365 /* We want to assign the same IDs each iteration of this loop, so
1366 start counting from zero each iteration of the loop. */
1369 /* We're at the start of the funtion each iteration through the
1370 loop, so we're copying arguments. */
1371 copying_arguments = 1;
1373 /* Wipe the potential alias information clean for this pass. */
1374 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1376 /* Wipe the reg_seen array clean. */
1377 bzero ((char *) reg_seen, reg_base_value_size);
1379 /* Mark all hard registers which may contain an address.
1380 The stack, frame and argument pointers may contain an address.
1381 An argument register which can hold a Pmode value may contain
1382 an address even if it is not in BASE_REGS.
1384 The address expression is VOIDmode for an argument and
1385 Pmode for other registers. */
1387 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1388 if (TEST_HARD_REG_BIT (argument_registers, i))
1389 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1390 gen_rtx_REG (Pmode, i));
1392 new_reg_base_value[STACK_POINTER_REGNUM]
1393 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1394 new_reg_base_value[ARG_POINTER_REGNUM]
1395 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1396 new_reg_base_value[FRAME_POINTER_REGNUM]
1397 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1398 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1399 new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1400 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1402 if (struct_value_incoming_rtx
1403 && GET_CODE (struct_value_incoming_rtx) == REG)
1404 new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1405 = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1407 if (static_chain_rtx
1408 && GET_CODE (static_chain_rtx) == REG)
1409 new_reg_base_value[REGNO (static_chain_rtx)]
1410 = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1412 /* Walk the insns adding values to the new_reg_base_value array. */
1413 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1415 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1418 /* If this insn has a noalias note, process it, Otherwise,
1419 scan for sets. A simple set will have no side effects
1420 which could change the base value of any other register. */
1422 if (GET_CODE (PATTERN (insn)) == SET
1423 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1424 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1426 note_stores (PATTERN (insn), record_set);
1428 set = single_set (insn);
1431 && GET_CODE (SET_DEST (set)) == REG
1432 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1433 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1434 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1435 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1436 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1438 int regno = REGNO (SET_DEST (set));
1439 reg_known_value[regno] = XEXP (note, 0);
1440 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1443 else if (GET_CODE (insn) == NOTE
1444 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1445 copying_arguments = 0;
1448 /* Now propagate values from new_reg_base_value to reg_base_value. */
1449 for (ui = 0; ui < reg_base_value_size; ui++)
1451 if (new_reg_base_value[ui]
1452 && new_reg_base_value[ui] != reg_base_value[ui]
1453 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
1455 reg_base_value[ui] = new_reg_base_value[ui];
1460 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1462 /* Fill in the remaining entries. */
1463 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1464 if (reg_known_value[i] == 0)
1465 reg_known_value[i] = regno_reg_rtx[i];
1467 /* Simplify the reg_base_value array so that no register refers to
1468 another register, except to special registers indirectly through
1469 ADDRESS expressions.
1471 In theory this loop can take as long as O(registers^2), but unless
1472 there are very long dependency chains it will run in close to linear
1475 This loop may not be needed any longer now that the main loop does
1476 a better job at propagating alias information. */
1482 for (ui = 0; ui < reg_base_value_size; ui++)
1484 rtx base = reg_base_value[ui];
1485 if (base && GET_CODE (base) == REG)
1487 unsigned int base_regno = REGNO (base);
1488 if (base_regno == ui) /* register set from itself */
1489 reg_base_value[ui] = 0;
1491 reg_base_value[ui] = reg_base_value[base_regno];
1496 while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1498 new_reg_base_value = 0;
1503 end_alias_analysis ()
1505 reg_known_value = 0;
1507 reg_base_value_size = 0;
1508 if (alias_invariant)
1510 free ((char *)alias_invariant);
1511 alias_invariant = 0;