1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
27 #include "hard-reg-set.h"
31 #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))))
845 /* If one address is a stack reference there can be no alias:
846 stack references using different base registers do not alias,
847 a stack reference can not alias a parameter, and a stack reference
848 can not alias a global. */
849 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
850 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
853 if (! flag_argument_noalias
)
856 if (flag_argument_noalias
> 1)
859 /* Weak noalias assertion (arguments are distinct, but may match globals). */
860 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
863 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
864 where SIZE is the size in bytes of the memory reference. If ADDR
865 is not modified by the memory reference then ADDR is returned. */
868 addr_side_effect_eval (addr
, size
, n_refs
)
875 switch (GET_CODE (addr
))
878 offset
= (n_refs
+ 1) * size
;
881 offset
= -(n_refs
+ 1) * size
;
884 offset
= n_refs
* size
;
887 offset
= -n_refs
* size
;
895 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0), GEN_INT (offset
));
897 addr
= XEXP (addr
, 0);
902 /* Return nonzero if X and Y (memory addresses) could reference the
903 same location in memory. C is an offset accumulator. When
904 C is nonzero, we are testing aliases between X and Y + C.
905 XSIZE is the size in bytes of the X reference,
906 similarly YSIZE is the size in bytes for Y.
908 If XSIZE or YSIZE is zero, we do not know the amount of memory being
909 referenced (the reference was BLKmode), so make the most pessimistic
912 If XSIZE or YSIZE is negative, we may access memory outside the object
913 being referenced as a side effect. This can happen when using AND to
914 align memory references, as is done on the Alpha.
916 Nice to notice that varying addresses cannot conflict with fp if no
917 local variables had their addresses taken, but that's too hard now. */
921 memrefs_conflict_p (xsize
, x
, ysize
, y
, c
)
926 if (GET_CODE (x
) == HIGH
)
928 else if (GET_CODE (x
) == LO_SUM
)
931 x
= canon_rtx (addr_side_effect_eval (x
, xsize
, 0));
932 if (GET_CODE (y
) == HIGH
)
934 else if (GET_CODE (y
) == LO_SUM
)
937 y
= canon_rtx (addr_side_effect_eval (y
, ysize
, 0));
939 if (rtx_equal_for_memref_p (x
, y
))
941 if (xsize
<= 0 || ysize
<= 0)
943 if (c
>= 0 && xsize
> c
)
945 if (c
< 0 && ysize
+c
> 0)
950 /* This code used to check for conflicts involving stack references and
951 globals but the base address alias code now handles these cases. */
953 if (GET_CODE (x
) == PLUS
)
955 /* The fact that X is canonicalized means that this
956 PLUS rtx is canonicalized. */
957 rtx x0
= XEXP (x
, 0);
958 rtx x1
= XEXP (x
, 1);
960 if (GET_CODE (y
) == PLUS
)
962 /* The fact that Y is canonicalized means that this
963 PLUS rtx is canonicalized. */
964 rtx y0
= XEXP (y
, 0);
965 rtx y1
= XEXP (y
, 1);
967 if (rtx_equal_for_memref_p (x1
, y1
))
968 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
969 if (rtx_equal_for_memref_p (x0
, y0
))
970 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
971 if (GET_CODE (x1
) == CONST_INT
)
973 if (GET_CODE (y1
) == CONST_INT
)
974 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
975 c
- INTVAL (x1
) + INTVAL (y1
));
977 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
980 else if (GET_CODE (y1
) == CONST_INT
)
981 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
985 else if (GET_CODE (x1
) == CONST_INT
)
986 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
988 else if (GET_CODE (y
) == PLUS
)
990 /* The fact that Y is canonicalized means that this
991 PLUS rtx is canonicalized. */
992 rtx y0
= XEXP (y
, 0);
993 rtx y1
= XEXP (y
, 1);
995 if (GET_CODE (y1
) == CONST_INT
)
996 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1001 if (GET_CODE (x
) == GET_CODE (y
))
1002 switch (GET_CODE (x
))
1006 /* Handle cases where we expect the second operands to be the
1007 same, and check only whether the first operand would conflict
1010 rtx x1
= canon_rtx (XEXP (x
, 1));
1011 rtx y1
= canon_rtx (XEXP (y
, 1));
1012 if (! rtx_equal_for_memref_p (x1
, y1
))
1014 x0
= canon_rtx (XEXP (x
, 0));
1015 y0
= canon_rtx (XEXP (y
, 0));
1016 if (rtx_equal_for_memref_p (x0
, y0
))
1017 return (xsize
== 0 || ysize
== 0
1018 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1020 /* Can't properly adjust our sizes. */
1021 if (GET_CODE (x1
) != CONST_INT
)
1023 xsize
/= INTVAL (x1
);
1024 ysize
/= INTVAL (x1
);
1026 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1030 /* Are these registers known not to be equal? */
1031 if (alias_invariant
)
1033 unsigned int r_x
= REGNO (x
), r_y
= REGNO (y
);
1034 rtx i_x
, i_y
; /* invariant relationships of X and Y */
1036 i_x
= r_x
>= reg_base_value_size
? 0 : alias_invariant
[r_x
];
1037 i_y
= r_y
>= reg_base_value_size
? 0 : alias_invariant
[r_y
];
1039 if (i_x
== 0 && i_y
== 0)
1042 if (! memrefs_conflict_p (xsize
, i_x
? i_x
: x
,
1043 ysize
, i_y
? i_y
: y
, c
))
1052 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1053 as an access with indeterminate size. Assume that references
1054 besides AND are aligned, so if the size of the other reference is
1055 at least as large as the alignment, assume no other overlap. */
1056 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1058 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1060 return memrefs_conflict_p (xsize
, XEXP (x
, 0), ysize
, y
, c
);
1062 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1064 /* ??? If we are indexing far enough into the array/structure, we
1065 may yet be able to determine that we can not overlap. But we
1066 also need to that we are far enough from the end not to overlap
1067 a following reference, so we do nothing with that for now. */
1068 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1070 return memrefs_conflict_p (xsize
, x
, ysize
, XEXP (y
, 0), c
);
1075 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1077 c
+= (INTVAL (y
) - INTVAL (x
));
1078 return (xsize
<= 0 || ysize
<= 0
1079 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1082 if (GET_CODE (x
) == CONST
)
1084 if (GET_CODE (y
) == CONST
)
1085 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1086 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1088 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1091 if (GET_CODE (y
) == CONST
)
1092 return memrefs_conflict_p (xsize
, x
, ysize
,
1093 canon_rtx (XEXP (y
, 0)), c
);
1096 return (xsize
< 0 || ysize
< 0
1097 || (rtx_equal_for_memref_p (x
, y
)
1098 && (xsize
== 0 || ysize
== 0
1099 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1106 /* Functions to compute memory dependencies.
1108 Since we process the insns in execution order, we can build tables
1109 to keep track of what registers are fixed (and not aliased), what registers
1110 are varying in known ways, and what registers are varying in unknown
1113 If both memory references are volatile, then there must always be a
1114 dependence between the two references, since their order can not be
1115 changed. A volatile and non-volatile reference can be interchanged
1118 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
1119 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
1120 allow QImode aliasing because the ANSI C standard allows character
1121 pointers to alias anything. We are assuming that characters are
1122 always QImode here. We also must allow AND addresses, because they may
1123 generate accesses outside the object being referenced. This is used to
1124 generate aligned addresses from unaligned addresses, for instance, the
1125 alpha storeqi_unaligned pattern. */
1127 /* Read dependence: X is read after read in MEM takes place. There can
1128 only be a dependence here if both reads are volatile. */
1131 read_dependence (mem
, x
)
1135 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1138 /* True dependence: X is read after store in MEM takes place. */
1141 true_dependence (mem
, mem_mode
, x
, varies
)
1143 enum machine_mode mem_mode
;
1145 int (*varies
) PROTO((rtx
));
1147 register rtx x_addr
, mem_addr
;
1149 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
1152 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
1155 /* If X is an unchanging read, then it can't possibly conflict with any
1156 non-unchanging store. It may conflict with an unchanging write though,
1157 because there may be a single store to this address to initialize it.
1158 Just fall through to the code below to resolve the case where we have
1159 both an unchanging read and an unchanging write. This won't handle all
1160 cases optimally, but the possible performance loss should be
1162 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
1165 if (mem_mode
== VOIDmode
)
1166 mem_mode
= GET_MODE (mem
);
1168 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0), GET_MODE (x
), mem_mode
))
1171 x_addr
= canon_rtx (XEXP (x
, 0));
1172 mem_addr
= canon_rtx (XEXP (mem
, 0));
1174 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
1175 SIZE_FOR_MODE (x
), x_addr
, 0))
1178 /* If both references are struct references, or both are not, nothing
1179 is known about aliasing.
1181 If either reference is QImode or BLKmode, ANSI C permits aliasing.
1183 If both addresses are constant, or both are not, nothing is known
1185 if (MEM_IN_STRUCT_P (x
) == MEM_IN_STRUCT_P (mem
)
1186 || mem_mode
== QImode
|| mem_mode
== BLKmode
1187 || GET_MODE (x
) == QImode
|| GET_MODE (x
) == BLKmode
1188 || GET_CODE (x_addr
) == AND
|| GET_CODE (mem_addr
) == AND
1189 || varies (x_addr
) == varies (mem_addr
))
1192 /* One memory reference is to a constant address, one is not.
1193 One is to a structure, the other is not.
1195 If either memory reference is a variable structure the other is a
1196 fixed scalar and there is no aliasing. */
1197 if ((MEM_IN_STRUCT_P (mem
) && varies (mem_addr
))
1198 || (MEM_IN_STRUCT_P (x
) && varies (x_addr
)))
1204 /* Anti dependence: X is written after read in MEM takes place. */
1207 anti_dependence (mem
, x
)
1211 rtx x_addr
, mem_addr
;
1213 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
1216 /* If MEM is an unchanging read, then it can't possibly conflict with
1217 the store to X, because there is at most one store to MEM, and it must
1218 have occurred somewhere before MEM. */
1219 if (RTX_UNCHANGING_P (mem
))
1222 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0), GET_MODE (x
),
1227 mem
= canon_rtx (mem
);
1229 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
1232 x_addr
= XEXP (x
, 0);
1233 mem_addr
= XEXP (mem
, 0);
1235 return (memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
1236 SIZE_FOR_MODE (x
), x_addr
, 0)
1237 && ! (MEM_IN_STRUCT_P (mem
) && rtx_addr_varies_p (mem
)
1238 && GET_MODE (mem
) != QImode
1239 && GET_CODE (mem_addr
) != AND
1240 && ! MEM_IN_STRUCT_P (x
) && ! rtx_addr_varies_p (x
))
1241 && ! (MEM_IN_STRUCT_P (x
) && rtx_addr_varies_p (x
)
1242 && GET_MODE (x
) != QImode
1243 && GET_CODE (x_addr
) != AND
1244 && ! MEM_IN_STRUCT_P (mem
) && ! rtx_addr_varies_p (mem
)));
1247 /* Output dependence: X is written after store in MEM takes place. */
1250 output_dependence (mem
, x
)
1254 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
1257 if (! base_alias_check (XEXP (x
, 0), XEXP (mem
, 0), GET_MODE (x
),
1262 mem
= canon_rtx (mem
);
1264 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
1267 return (memrefs_conflict_p (SIZE_FOR_MODE (mem
), XEXP (mem
, 0),
1268 SIZE_FOR_MODE (x
), XEXP (x
, 0), 0)
1269 && ! (MEM_IN_STRUCT_P (mem
) && rtx_addr_varies_p (mem
)
1270 && GET_MODE (mem
) != QImode
1271 && GET_CODE (XEXP (mem
, 0)) != AND
1272 && ! MEM_IN_STRUCT_P (x
) && ! rtx_addr_varies_p (x
))
1273 && ! (MEM_IN_STRUCT_P (x
) && rtx_addr_varies_p (x
)
1274 && GET_MODE (x
) != QImode
1275 && GET_CODE (XEXP (x
, 0)) != AND
1276 && ! MEM_IN_STRUCT_P (mem
) && ! rtx_addr_varies_p (mem
)));
1280 static HARD_REG_SET argument_registers
;
1287 #ifndef OUTGOING_REGNO
1288 #define OUTGOING_REGNO(N) N
1290 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1291 /* Check whether this register can hold an incoming pointer
1292 argument. FUNCTION_ARG_REGNO_P tests outgoing register
1293 numbers, so translate if necessary due to register windows. */
1294 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
1295 && HARD_REGNO_MODE_OK (i
, Pmode
))
1296 SET_HARD_REG_BIT (argument_registers
, i
);
1298 alias_sets
= splay_tree_new (alias_set_compare
, 0, 0);
1302 init_alias_analysis ()
1304 int maxreg
= max_reg_num ();
1307 register unsigned int ui
;
1310 reg_known_value_size
= maxreg
;
1313 = (rtx
*) oballoc ((maxreg
- FIRST_PSEUDO_REGISTER
) * sizeof (rtx
))
1314 - FIRST_PSEUDO_REGISTER
;
1316 oballoc (maxreg
- FIRST_PSEUDO_REGISTER
) - FIRST_PSEUDO_REGISTER
;
1317 bzero ((char *) (reg_known_value
+ FIRST_PSEUDO_REGISTER
),
1318 (maxreg
-FIRST_PSEUDO_REGISTER
) * sizeof (rtx
));
1319 bzero (reg_known_equiv_p
+ FIRST_PSEUDO_REGISTER
,
1320 (maxreg
- FIRST_PSEUDO_REGISTER
) * sizeof (char));
1322 /* Overallocate reg_base_value to allow some growth during loop
1323 optimization. Loop unrolling can create a large number of
1325 reg_base_value_size
= maxreg
* 2;
1326 reg_base_value
= (rtx
*)oballoc (reg_base_value_size
* sizeof (rtx
));
1327 new_reg_base_value
= (rtx
*)alloca (reg_base_value_size
* sizeof (rtx
));
1328 reg_seen
= (char *)alloca (reg_base_value_size
);
1329 bzero ((char *) reg_base_value
, reg_base_value_size
* sizeof (rtx
));
1330 if (! reload_completed
&& flag_unroll_loops
)
1332 alias_invariant
= (rtx
*)xrealloc (alias_invariant
,
1333 reg_base_value_size
* sizeof (rtx
));
1334 bzero ((char *)alias_invariant
, reg_base_value_size
* sizeof (rtx
));
1338 /* The basic idea is that each pass through this loop will use the
1339 "constant" information from the previous pass to propagate alias
1340 information through another level of assignments.
1342 This could get expensive if the assignment chains are long. Maybe
1343 we should throttle the number of iterations, possibly based on
1344 the optimization level or flag_expensive_optimizations.
1346 We could propagate more information in the first pass by making use
1347 of REG_N_SETS to determine immediately that the alias information
1348 for a pseudo is "constant".
1350 A program with an uninitialized variable can cause an infinite loop
1351 here. Instead of doing a full dataflow analysis to detect such problems
1352 we just cap the number of iterations for the loop.
1354 The state of the arrays for the set chain in question does not matter
1355 since the program has undefined behavior. */
1360 /* Assume nothing will change this iteration of the loop. */
1363 /* We want to assign the same IDs each iteration of this loop, so
1364 start counting from zero each iteration of the loop. */
1367 /* We're at the start of the funtion each iteration through the
1368 loop, so we're copying arguments. */
1369 copying_arguments
= 1;
1371 /* Wipe the potential alias information clean for this pass. */
1372 bzero ((char *) new_reg_base_value
, reg_base_value_size
* sizeof (rtx
));
1374 /* Wipe the reg_seen array clean. */
1375 bzero ((char *) reg_seen
, reg_base_value_size
);
1377 /* Mark all hard registers which may contain an address.
1378 The stack, frame and argument pointers may contain an address.
1379 An argument register which can hold a Pmode value may contain
1380 an address even if it is not in BASE_REGS.
1382 The address expression is VOIDmode for an argument and
1383 Pmode for other registers. */
1385 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1386 if (TEST_HARD_REG_BIT (argument_registers
, i
))
1387 new_reg_base_value
[i
] = gen_rtx_ADDRESS (VOIDmode
,
1388 gen_rtx_REG (Pmode
, i
));
1390 new_reg_base_value
[STACK_POINTER_REGNUM
]
1391 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
1392 new_reg_base_value
[ARG_POINTER_REGNUM
]
1393 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
1394 new_reg_base_value
[FRAME_POINTER_REGNUM
]
1395 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
1396 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1397 new_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
1398 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
1400 if (struct_value_incoming_rtx
1401 && GET_CODE (struct_value_incoming_rtx
) == REG
)
1402 new_reg_base_value
[REGNO (struct_value_incoming_rtx
)]
1403 = gen_rtx_ADDRESS (Pmode
, struct_value_incoming_rtx
);
1405 if (static_chain_rtx
1406 && GET_CODE (static_chain_rtx
) == REG
)
1407 new_reg_base_value
[REGNO (static_chain_rtx
)]
1408 = gen_rtx_ADDRESS (Pmode
, static_chain_rtx
);
1410 /* Walk the insns adding values to the new_reg_base_value array. */
1411 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1413 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1416 /* If this insn has a noalias note, process it, Otherwise,
1417 scan for sets. A simple set will have no side effects
1418 which could change the base value of any other register. */
1420 if (GET_CODE (PATTERN (insn
)) == SET
1421 && (find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
)))
1422 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
);
1424 note_stores (PATTERN (insn
), record_set
);
1426 set
= single_set (insn
);
1429 && GET_CODE (SET_DEST (set
)) == REG
1430 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
1431 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
1432 && REG_N_SETS (REGNO (SET_DEST (set
))) == 1)
1433 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
1434 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
)
1436 int regno
= REGNO (SET_DEST (set
));
1437 reg_known_value
[regno
] = XEXP (note
, 0);
1438 reg_known_equiv_p
[regno
] = REG_NOTE_KIND (note
) == REG_EQUIV
;
1441 else if (GET_CODE (insn
) == NOTE
1442 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
1443 copying_arguments
= 0;
1446 /* Now propagate values from new_reg_base_value to reg_base_value. */
1447 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
1449 if (new_reg_base_value
[ui
]
1450 && new_reg_base_value
[ui
] != reg_base_value
[ui
]
1451 && ! rtx_equal_p (new_reg_base_value
[ui
], reg_base_value
[ui
]))
1453 reg_base_value
[ui
] = new_reg_base_value
[ui
];
1458 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
1460 /* Fill in the remaining entries. */
1461 for (i
= FIRST_PSEUDO_REGISTER
; i
< maxreg
; i
++)
1462 if (reg_known_value
[i
] == 0)
1463 reg_known_value
[i
] = regno_reg_rtx
[i
];
1465 /* Simplify the reg_base_value array so that no register refers to
1466 another register, except to special registers indirectly through
1467 ADDRESS expressions.
1469 In theory this loop can take as long as O(registers^2), but unless
1470 there are very long dependency chains it will run in close to linear
1473 This loop may not be needed any longer now that the main loop does
1474 a better job at propagating alias information. */
1480 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
1482 rtx base
= reg_base_value
[ui
];
1483 if (base
&& GET_CODE (base
) == REG
)
1485 unsigned int base_regno
= REGNO (base
);
1486 if (base_regno
== ui
) /* register set from itself */
1487 reg_base_value
[ui
] = 0;
1489 reg_base_value
[ui
] = reg_base_value
[base_regno
];
1494 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
1496 new_reg_base_value
= 0;
1501 end_alias_analysis ()
1503 reg_known_value
= 0;
1505 reg_base_value_size
= 0;
1506 if (alias_invariant
)
1508 free ((char *)alias_invariant
);
1509 alias_invariant
= 0;