1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000 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. */
28 #include "insn-flags.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "splay-tree.h"
40 /* The alias sets assigned to MEMs assist the back-end in determining
41 which MEMs can alias which other MEMs. In general, two MEMs in
42 different alias sets cannot alias each other, with one important
43 exception. Consider something like:
45 struct S {int i; double d; };
47 a store to an `S' can alias something of either type `int' or type
48 `double'. (However, a store to an `int' cannot alias a `double'
49 and vice versa.) We indicate this via a tree structure that looks
57 (The arrows are directed and point downwards.)
58 In this situation we say the alias set for `struct S' is the
59 `superset' and that those for `int' and `double' are `subsets'.
61 To see whether two alias sets can point to the same memory, we must
62 see if either alias set is a subset of the other. We need not trace
63 past immediate decendents, however, since we propagate all
64 grandchildren up one level.
66 Alias set zero is implicitly a superset of all other alias sets.
67 However, this is no actual entry for alias set zero. It is an
68 error to attempt to explicitly construct a subset of zero. */
70 typedef struct alias_set_entry
72 /* The alias set number, as stored in MEM_ALIAS_SET. */
73 HOST_WIDE_INT alias_set
;
75 /* The children of the alias set. These are not just the immediate
76 children, but, in fact, all decendents. So, if we have:
78 struct T { struct S s; float f; }
80 continuing our example above, the children here will be all of
81 `int', `double', `float', and `struct S'. */
84 /* Nonzero if would have a child of zero: this effectively makes this
85 alias set the same as alias set zero. */
89 static int rtx_equal_for_memref_p
PARAMS ((rtx
, rtx
));
90 static rtx find_symbolic_term
PARAMS ((rtx
));
91 static rtx get_addr
PARAMS ((rtx
));
92 static int memrefs_conflict_p
PARAMS ((int, rtx
, int, rtx
,
94 static void record_set
PARAMS ((rtx
, rtx
, void *));
95 static rtx find_base_term
PARAMS ((rtx
));
96 static int base_alias_check
PARAMS ((rtx
, rtx
, enum machine_mode
,
98 static rtx find_base_value
PARAMS ((rtx
));
99 static int mems_in_disjoint_alias_sets_p
PARAMS ((rtx
, rtx
));
100 static int insert_subset_children
PARAMS ((splay_tree_node
, void*));
101 static tree find_base_decl
PARAMS ((tree
));
102 static alias_set_entry get_alias_set_entry
PARAMS ((HOST_WIDE_INT
));
103 static rtx fixed_scalar_and_varying_struct_p
PARAMS ((rtx
, rtx
, rtx
, rtx
,
104 int (*) (rtx
, int)));
105 static int aliases_everything_p
PARAMS ((rtx
));
106 static int write_dependence_p
PARAMS ((rtx
, rtx
, int));
107 static int nonlocal_mentioned_p
PARAMS ((rtx
));
109 static int loop_p
PARAMS ((void));
111 /* Set up all info needed to perform alias analysis on memory references. */
113 /* Returns the size in bytes of the mode of X. */
114 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
116 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
117 different alias sets. We ignore alias sets in functions making use
118 of variable arguments because the va_arg macros on some systems are
120 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
121 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
123 /* Cap the number of passes we make over the insns propagating alias
124 information through set chains. 10 is a completely arbitrary choice. */
125 #define MAX_ALIAS_LOOP_PASSES 10
127 /* reg_base_value[N] gives an address to which register N is related.
128 If all sets after the first add or subtract to the current value
129 or otherwise modify it so it does not point to a different top level
130 object, reg_base_value[N] is equal to the address part of the source
133 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
134 expressions represent certain special values: function arguments and
135 the stack, frame, and argument pointers.
137 The contents of an ADDRESS is not normally used, the mode of the
138 ADDRESS determines whether the ADDRESS is a function argument or some
139 other special value. Pointer equality, not rtx_equal_p, determines whether
140 two ADDRESS expressions refer to the same base address.
142 The only use of the contents of an ADDRESS is for determining if the
143 current function performs nonlocal memory memory references for the
144 purposes of marking the function as a constant function. */
146 static rtx
*reg_base_value
;
147 static rtx
*new_reg_base_value
;
148 static unsigned int reg_base_value_size
; /* size of reg_base_value array */
150 #define REG_BASE_VALUE(X) \
151 (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
153 /* Vector of known invariant relationships between registers. Set in
154 loop unrolling. Indexed by register number, if nonzero the value
155 is an expression describing this register in terms of another.
157 The length of this array is REG_BASE_VALUE_SIZE.
159 Because this array contains only pseudo registers it has no effect
161 static rtx
*alias_invariant
;
163 /* Vector indexed by N giving the initial (unchanging) value known for
164 pseudo-register N. This array is initialized in
165 init_alias_analysis, and does not change until end_alias_analysis
167 rtx
*reg_known_value
;
169 /* Indicates number of valid entries in reg_known_value. */
170 static unsigned int reg_known_value_size
;
172 /* Vector recording for each reg_known_value whether it is due to a
173 REG_EQUIV note. Future passes (viz., reload) may replace the
174 pseudo with the equivalent expression and so we account for the
175 dependences that would be introduced if that happens.
177 The REG_EQUIV notes created in assign_parms may mention the arg
178 pointer, and there are explicit insns in the RTL that modify the
179 arg pointer. Thus we must ensure that such insns don't get
180 scheduled across each other because that would invalidate the
181 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
182 wrong, but solving the problem in the scheduler will likely give
183 better code, so we do it here. */
184 char *reg_known_equiv_p
;
186 /* True when scanning insns from the start of the rtl to the
187 NOTE_INSN_FUNCTION_BEG note. */
188 static int copying_arguments
;
190 /* The splay-tree used to store the various alias set entries. */
191 static splay_tree alias_sets
;
193 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
194 such an entry, or NULL otherwise. */
196 static alias_set_entry
197 get_alias_set_entry (alias_set
)
198 HOST_WIDE_INT alias_set
;
201 = splay_tree_lookup (alias_sets
, (splay_tree_key
) alias_set
);
203 return sn
!= 0 ? ((alias_set_entry
) sn
->value
) : 0;
206 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
207 the two MEMs cannot alias each other. */
210 mems_in_disjoint_alias_sets_p (mem1
, mem2
)
214 #ifdef ENABLE_CHECKING
215 /* Perform a basic sanity check. Namely, that there are no alias sets
216 if we're not using strict aliasing. This helps to catch bugs
217 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
218 where a MEM is allocated in some way other than by the use of
219 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
220 use alias sets to indicate that spilled registers cannot alias each
221 other, we might need to remove this check. */
222 if (! flag_strict_aliasing
223 && (MEM_ALIAS_SET (mem1
) != 0 || MEM_ALIAS_SET (mem2
) != 0))
227 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
230 /* Insert the NODE into the splay tree given by DATA. Used by
231 record_alias_subset via splay_tree_foreach. */
234 insert_subset_children (node
, data
)
235 splay_tree_node node
;
238 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
243 /* Return 1 if the two specified alias sets may conflict. */
246 alias_sets_conflict_p (set1
, set2
)
247 HOST_WIDE_INT set1
, set2
;
251 /* If have no alias set information for one of the operands, we have
252 to assume it can alias anything. */
253 if (set1
== 0 || set2
== 0
254 /* If the two alias sets are the same, they may alias. */
258 /* See if the first alias set is a subset of the second. */
259 ase
= get_alias_set_entry (set1
);
261 && (ase
->has_zero_child
262 || splay_tree_lookup (ase
->children
,
263 (splay_tree_key
) set2
)))
266 /* Now do the same, but with the alias sets reversed. */
267 ase
= get_alias_set_entry (set2
);
269 && (ase
->has_zero_child
270 || splay_tree_lookup (ase
->children
,
271 (splay_tree_key
) set1
)))
274 /* The two alias sets are distinct and neither one is the
275 child of the other. Therefore, they cannot alias. */
279 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
280 has any readonly fields. If any of the fields have types that
281 contain readonly fields, return true as well. */
284 readonly_fields_p (type
)
289 if (TREE_CODE (type
) != RECORD_TYPE
&& TREE_CODE (type
) != UNION_TYPE
290 && TREE_CODE (type
) != QUAL_UNION_TYPE
)
293 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
294 if (TREE_CODE (field
) == FIELD_DECL
295 && (TREE_READONLY (field
)
296 || readonly_fields_p (TREE_TYPE (field
))))
302 /* Return 1 if any MEM object of type T1 will always conflict (using the
303 dependency routines in this file) with any MEM object of type T2.
304 This is used when allocating temporary storage. If T1 and/or T2 are
305 NULL_TREE, it means we know nothing about the storage. */
308 objects_must_conflict_p (t1
, t2
)
311 /* If they are the same type, they must conflict. */
313 /* Likewise if both are volatile. */
314 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
317 /* We now know they are different types. If one or both has readonly fields
318 or if one is readonly and the other not, they may not conflict.
319 Likewise if one is aggregate and the other is scalar. */
320 if ((t1
!= 0 && readonly_fields_p (t1
))
321 || (t2
!= 0 && readonly_fields_p (t2
))
322 || ((t1
!= 0 && TYPE_READONLY (t1
))
323 != (t2
!= 0 && TYPE_READONLY (t2
)))
324 || ((t1
!= 0 && AGGREGATE_TYPE_P (t1
))
325 != (t2
!= 0 && AGGREGATE_TYPE_P (t2
))))
328 /* Otherwise they conflict only if the alias sets conflict. */
329 return alias_sets_conflict_p (t1
? get_alias_set (t1
) : 0,
330 t2
? get_alias_set (t2
) : 0);
333 /* T is an expression with pointer type. Find the DECL on which this
334 expression is based. (For example, in `a[i]' this would be `a'.)
335 If there is no such DECL, or a unique decl cannot be determined,
336 NULL_TREE is retured. */
344 if (t
== 0 || t
== error_mark_node
|| ! POINTER_TYPE_P (TREE_TYPE (t
)))
347 /* If this is a declaration, return it. */
348 if (TREE_CODE_CLASS (TREE_CODE (t
)) == 'd')
351 /* Handle general expressions. It would be nice to deal with
352 COMPONENT_REFs here. If we could tell that `a' and `b' were the
353 same, then `a->f' and `b->f' are also the same. */
354 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
357 return find_base_decl (TREE_OPERAND (t
, 0));
360 /* Return 0 if found in neither or both are the same. */
361 d0
= find_base_decl (TREE_OPERAND (t
, 0));
362 d1
= find_base_decl (TREE_OPERAND (t
, 1));
373 d0
= find_base_decl (TREE_OPERAND (t
, 0));
374 d1
= find_base_decl (TREE_OPERAND (t
, 1));
375 d0
= find_base_decl (TREE_OPERAND (t
, 0));
376 d2
= find_base_decl (TREE_OPERAND (t
, 2));
378 /* Set any nonzero values from the last, then from the first. */
379 if (d1
== 0) d1
= d2
;
380 if (d0
== 0) d0
= d1
;
381 if (d1
== 0) d1
= d0
;
382 if (d2
== 0) d2
= d1
;
384 /* At this point all are nonzero or all are zero. If all three are the
385 same, return it. Otherwise, return zero. */
386 return (d0
== d1
&& d1
== d2
) ? d0
: 0;
393 /* Return the alias set for T, which may be either a type or an
394 expression. Call language-specific routine for help, if needed. */
403 /* If we're not doing any alias analysis, just assume everything
404 aliases everything else. Also return 0 if this or its type is
406 if (! flag_strict_aliasing
|| t
== error_mark_node
408 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
411 /* We can be passed either an expression or a type. This and the
412 language-specific routine may make mutually-recursive calls to
413 each other to figure out what to do. At each juncture, we see if
414 this is a tree that the language may need to handle specially.
415 First handle things that aren't types and start by removing nops
416 since we care only about the actual object. */
419 while (TREE_CODE (t
) == NOP_EXPR
|| TREE_CODE (t
) == CONVERT_EXPR
420 || TREE_CODE (t
) == NON_LVALUE_EXPR
)
421 t
= TREE_OPERAND (t
, 0);
423 /* Now give the language a chance to do something but record what we
424 gave it this time. */
426 if ((set
= lang_get_alias_set (t
)) != -1)
429 /* Now loop the same way as get_inner_reference and get the alias
430 set to use. Pick up the outermost object that we could have
434 /* Unnamed bitfields are not an addressable object. */
435 if (TREE_CODE (t
) == BIT_FIELD_REF
)
437 else if (TREE_CODE (t
) == COMPONENT_REF
)
439 if (! DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
440 /* Stop at an adressable decl. */
443 else if (TREE_CODE (t
) == ARRAY_REF
)
445 if (! TYPE_NONALIASED_COMPONENT
446 (TREE_TYPE (TREE_OPERAND (t
, 0))))
447 /* Stop at an addresssable array element. */
450 else if (TREE_CODE (t
) != NON_LVALUE_EXPR
451 && ! ((TREE_CODE (t
) == NOP_EXPR
452 || TREE_CODE (t
) == CONVERT_EXPR
)
453 && (TYPE_MODE (TREE_TYPE (t
))
454 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (t
, 0))))))
455 /* Stop if not one of above and not mode-preserving conversion. */
458 t
= TREE_OPERAND (t
, 0);
461 if (TREE_CODE (t
) == INDIRECT_REF
)
463 /* Check for accesses through restrict-qualified pointers. */
464 tree decl
= find_base_decl (TREE_OPERAND (t
, 0));
466 if (decl
&& DECL_POINTER_ALIAS_SET_KNOWN_P (decl
))
467 /* We use the alias set indicated in the declaration. */
468 return DECL_POINTER_ALIAS_SET (decl
);
470 /* If we have an INDIRECT_REF via a void pointer, we don't
471 know anything about what that might alias. */
472 if (TREE_CODE (TREE_TYPE (t
)) == VOID_TYPE
)
476 /* Give the language another chance to do something special. */
478 && (set
= lang_get_alias_set (t
)) != -1)
481 /* Now all we care about is the type. */
485 /* Variant qualifiers don't affect the alias set, so get the main
486 variant. If this is a type with a known alias set, return it. */
487 t
= TYPE_MAIN_VARIANT (t
);
488 if (TYPE_P (t
) && TYPE_ALIAS_SET_KNOWN_P (t
))
489 return TYPE_ALIAS_SET (t
);
491 /* See if the language has special handling for this type. */
492 if ((set
= lang_get_alias_set (t
)) != -1)
494 /* If the alias set is now known, we are done. */
495 if (TYPE_ALIAS_SET_KNOWN_P (t
))
496 return TYPE_ALIAS_SET (t
);
499 /* There are no objects of FUNCTION_TYPE, so there's no point in
500 using up an alias set for them. (There are, of course, pointers
501 and references to functions, but that's different.) */
502 else if (TREE_CODE (t
) == FUNCTION_TYPE
)
505 /* Otherwise make a new alias set for this type. */
506 set
= new_alias_set ();
508 TYPE_ALIAS_SET (t
) = set
;
510 /* If this is an aggregate type, we must record any component aliasing
512 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
513 record_component_aliases (t
);
518 /* Return a brand-new alias set. */
523 static HOST_WIDE_INT last_alias_set
;
525 if (flag_strict_aliasing
)
526 return ++last_alias_set
;
531 /* Indicate that things in SUBSET can alias things in SUPERSET, but
532 not vice versa. For example, in C, a store to an `int' can alias a
533 structure containing an `int', but not vice versa. Here, the
534 structure would be the SUPERSET and `int' the SUBSET. This
535 function should be called only once per SUPERSET/SUBSET pair.
537 It is illegal for SUPERSET to be zero; everything is implicitly a
538 subset of alias set zero. */
541 record_alias_subset (superset
, subset
)
542 HOST_WIDE_INT superset
;
543 HOST_WIDE_INT subset
;
545 alias_set_entry superset_entry
;
546 alias_set_entry subset_entry
;
551 superset_entry
= get_alias_set_entry (superset
);
552 if (superset_entry
== 0)
554 /* Create an entry for the SUPERSET, so that we have a place to
555 attach the SUBSET. */
557 = (alias_set_entry
) xmalloc (sizeof (struct alias_set_entry
));
558 superset_entry
->alias_set
= superset
;
559 superset_entry
->children
560 = splay_tree_new (splay_tree_compare_ints
, 0, 0);
561 superset_entry
->has_zero_child
= 0;
562 splay_tree_insert (alias_sets
, (splay_tree_key
) superset
,
563 (splay_tree_value
) superset_entry
);
567 superset_entry
->has_zero_child
= 1;
570 subset_entry
= get_alias_set_entry (subset
);
571 /* If there is an entry for the subset, enter all of its children
572 (if they are not already present) as children of the SUPERSET. */
575 if (subset_entry
->has_zero_child
)
576 superset_entry
->has_zero_child
= 1;
578 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
579 superset_entry
->children
);
582 /* Enter the SUBSET itself as a child of the SUPERSET. */
583 splay_tree_insert (superset_entry
->children
,
584 (splay_tree_key
) subset
, 0);
588 /* Record that component types of TYPE, if any, are part of that type for
589 aliasing purposes. For record types, we only record component types
590 for fields that are marked addressable. For array types, we always
591 record the component types, so the front end should not call this
592 function if the individual component aren't addressable. */
595 record_component_aliases (type
)
598 HOST_WIDE_INT superset
= get_alias_set (type
);
604 switch (TREE_CODE (type
))
607 if (! TYPE_NONALIASED_COMPONENT (type
))
608 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
613 case QUAL_UNION_TYPE
:
614 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
615 if (TREE_CODE (field
) == FIELD_DECL
&& ! DECL_NONADDRESSABLE_P (field
))
616 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
620 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
628 /* Allocate an alias set for use in storing and reading from the varargs
632 get_varargs_alias_set ()
634 static HOST_WIDE_INT set
= -1;
637 set
= new_alias_set ();
642 /* Likewise, but used for the fixed portions of the frame, e.g., register
646 get_frame_alias_set ()
648 static HOST_WIDE_INT set
= -1;
651 set
= new_alias_set ();
656 /* Inside SRC, the source of a SET, find a base address. */
659 find_base_value (src
)
662 switch (GET_CODE (src
))
669 /* At the start of a function, argument registers have known base
670 values which may be lost later. Returning an ADDRESS
671 expression here allows optimization based on argument values
672 even when the argument registers are used for other purposes. */
673 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
&& copying_arguments
)
674 return new_reg_base_value
[REGNO (src
)];
676 /* If a pseudo has a known base value, return it. Do not do this
677 for hard regs since it can result in a circular dependency
678 chain for registers which have values at function entry.
680 The test above is not sufficient because the scheduler may move
681 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
682 if (REGNO (src
) >= FIRST_PSEUDO_REGISTER
683 && (unsigned) REGNO (src
) < reg_base_value_size
684 && reg_base_value
[REGNO (src
)])
685 return reg_base_value
[REGNO (src
)];
690 /* Check for an argument passed in memory. Only record in the
691 copying-arguments block; it is too hard to track changes
693 if (copying_arguments
694 && (XEXP (src
, 0) == arg_pointer_rtx
695 || (GET_CODE (XEXP (src
, 0)) == PLUS
696 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
697 return gen_rtx_ADDRESS (VOIDmode
, src
);
702 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
705 /* ... fall through ... */
710 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
712 /* If either operand is a REG, then see if we already have
713 a known value for it. */
714 if (GET_CODE (src_0
) == REG
)
716 temp
= find_base_value (src_0
);
721 if (GET_CODE (src_1
) == REG
)
723 temp
= find_base_value (src_1
);
728 /* Guess which operand is the base address:
729 If either operand is a symbol, then it is the base. If
730 either operand is a CONST_INT, then the other is the base. */
731 if (GET_CODE (src_1
) == CONST_INT
|| CONSTANT_P (src_0
))
732 return find_base_value (src_0
);
733 else if (GET_CODE (src_0
) == CONST_INT
|| CONSTANT_P (src_1
))
734 return find_base_value (src_1
);
736 /* This might not be necessary anymore:
737 If either operand is a REG that is a known pointer, then it
739 else if (GET_CODE (src_0
) == REG
&& REG_POINTER (src_0
))
740 return find_base_value (src_0
);
741 else if (GET_CODE (src_1
) == REG
&& REG_POINTER (src_1
))
742 return find_base_value (src_1
);
748 /* The standard form is (lo_sum reg sym) so look only at the
750 return find_base_value (XEXP (src
, 1));
753 /* If the second operand is constant set the base
754 address to the first operand. */
755 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
756 return find_base_value (XEXP (src
, 0));
760 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
762 return find_base_value (XEXP (src
, 0));
771 /* Called from init_alias_analysis indirectly through note_stores. */
773 /* While scanning insns to find base values, reg_seen[N] is nonzero if
774 register N has been set in this function. */
775 static char *reg_seen
;
777 /* Addresses which are known not to alias anything else are identified
778 by a unique integer. */
779 static int unique_id
;
782 record_set (dest
, set
, data
)
784 void *data ATTRIBUTE_UNUSED
;
786 register unsigned regno
;
789 if (GET_CODE (dest
) != REG
)
792 regno
= REGNO (dest
);
794 if (regno
>= reg_base_value_size
)
799 /* A CLOBBER wipes out any old value but does not prevent a previously
800 unset register from acquiring a base address (i.e. reg_seen is not
802 if (GET_CODE (set
) == CLOBBER
)
804 new_reg_base_value
[regno
] = 0;
813 new_reg_base_value
[regno
] = 0;
817 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
818 GEN_INT (unique_id
++));
822 /* This is not the first set. If the new value is not related to the
823 old value, forget the base value. Note that the following code is
825 extern int x, y; int *p = &x; p += (&y-&x);
826 ANSI C does not allow computing the difference of addresses
827 of distinct top level objects. */
828 if (new_reg_base_value
[regno
])
829 switch (GET_CODE (src
))
834 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
835 new_reg_base_value
[regno
] = 0;
838 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
839 new_reg_base_value
[regno
] = 0;
842 new_reg_base_value
[regno
] = 0;
845 /* If this is the first set of a register, record the value. */
846 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
847 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
848 new_reg_base_value
[regno
] = find_base_value (src
);
853 /* Called from loop optimization when a new pseudo-register is
854 created. It indicates that REGNO is being set to VAL. f INVARIANT
855 is true then this value also describes an invariant relationship
856 which can be used to deduce that two registers with unknown values
860 record_base_value (regno
, val
, invariant
)
865 if (regno
>= reg_base_value_size
)
868 if (invariant
&& alias_invariant
)
869 alias_invariant
[regno
] = val
;
871 if (GET_CODE (val
) == REG
)
873 if (REGNO (val
) < reg_base_value_size
)
874 reg_base_value
[regno
] = reg_base_value
[REGNO (val
)];
879 reg_base_value
[regno
] = find_base_value (val
);
882 /* Returns a canonical version of X, from the point of view alias
883 analysis. (For example, if X is a MEM whose address is a register,
884 and the register has a known value (say a SYMBOL_REF), then a MEM
885 whose address is the SYMBOL_REF is returned.) */
891 /* Recursively look for equivalences. */
892 if (GET_CODE (x
) == REG
&& REGNO (x
) >= FIRST_PSEUDO_REGISTER
893 && REGNO (x
) < reg_known_value_size
)
894 return reg_known_value
[REGNO (x
)] == x
895 ? x
: canon_rtx (reg_known_value
[REGNO (x
)]);
896 else if (GET_CODE (x
) == PLUS
)
898 rtx x0
= canon_rtx (XEXP (x
, 0));
899 rtx x1
= canon_rtx (XEXP (x
, 1));
901 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
903 /* We can tolerate LO_SUMs being offset here; these
904 rtl are used for nothing other than comparisons. */
905 if (GET_CODE (x0
) == CONST_INT
)
906 return plus_constant_for_output (x1
, INTVAL (x0
));
907 else if (GET_CODE (x1
) == CONST_INT
)
908 return plus_constant_for_output (x0
, INTVAL (x1
));
909 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
913 /* This gives us much better alias analysis when called from
914 the loop optimizer. Note we want to leave the original
915 MEM alone, but need to return the canonicalized MEM with
916 all the flags with their original values. */
917 else if (GET_CODE (x
) == MEM
)
919 rtx addr
= canon_rtx (XEXP (x
, 0));
921 if (addr
!= XEXP (x
, 0))
923 rtx
new = gen_rtx_MEM (GET_MODE (x
), addr
);
925 MEM_COPY_ATTRIBUTES (new, x
);
932 /* Return 1 if X and Y are identical-looking rtx's.
934 We use the data in reg_known_value above to see if two registers with
935 different numbers are, in fact, equivalent. */
938 rtx_equal_for_memref_p (x
, y
)
943 register enum rtx_code code
;
944 register const char *fmt
;
946 if (x
== 0 && y
== 0)
948 if (x
== 0 || y
== 0)
958 /* Rtx's of different codes cannot be equal. */
959 if (code
!= GET_CODE (y
))
962 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
963 (REG:SI x) and (REG:HI x) are NOT equivalent. */
965 if (GET_MODE (x
) != GET_MODE (y
))
968 /* Some RTL can be compared without a recursive examination. */
972 return REGNO (x
) == REGNO (y
);
975 return XEXP (x
, 0) == XEXP (y
, 0);
978 return XSTR (x
, 0) == XSTR (y
, 0);
982 /* There's no need to compare the contents of CONST_DOUBLEs or
983 CONST_INTs because pointer equality is a good enough
984 comparison for these nodes. */
988 return (REGNO (XEXP (x
, 0)) == REGNO (XEXP (y
, 0))
989 && XINT (x
, 1) == XINT (y
, 1));
995 /* For commutative operations, the RTX match if the operand match in any
996 order. Also handle the simple binary and unary cases without a loop. */
997 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
998 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
999 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1000 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1001 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1002 else if (GET_RTX_CLASS (code
) == '<' || GET_RTX_CLASS (code
) == '2')
1003 return (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1004 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)));
1005 else if (GET_RTX_CLASS (code
) == '1')
1006 return rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0));
1008 /* Compare the elements. If any pair of corresponding elements
1009 fail to match, return 0 for the whole things.
1011 Limit cases to types which actually appear in addresses. */
1013 fmt
= GET_RTX_FORMAT (code
);
1014 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1019 if (XINT (x
, i
) != XINT (y
, i
))
1024 /* Two vectors must have the same length. */
1025 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1028 /* And the corresponding elements must match. */
1029 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1030 if (rtx_equal_for_memref_p (XVECEXP (x
, i
, j
),
1031 XVECEXP (y
, i
, j
)) == 0)
1036 if (rtx_equal_for_memref_p (XEXP (x
, i
), XEXP (y
, i
)) == 0)
1040 /* This can happen for an asm which clobbers memory. */
1044 /* It is believed that rtx's at this level will never
1045 contain anything but integers and other rtx's,
1046 except for within LABEL_REFs and SYMBOL_REFs. */
1054 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1055 X and return it, or return 0 if none found. */
1058 find_symbolic_term (x
)
1062 register enum rtx_code code
;
1063 register const char *fmt
;
1065 code
= GET_CODE (x
);
1066 if (code
== SYMBOL_REF
|| code
== LABEL_REF
)
1068 if (GET_RTX_CLASS (code
) == 'o')
1071 fmt
= GET_RTX_FORMAT (code
);
1072 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1078 t
= find_symbolic_term (XEXP (x
, i
));
1082 else if (fmt
[i
] == 'E')
1093 struct elt_loc_list
*l
;
1095 #if defined (FIND_BASE_TERM)
1096 /* Try machine-dependent ways to find the base term. */
1097 x
= FIND_BASE_TERM (x
);
1100 switch (GET_CODE (x
))
1103 return REG_BASE_VALUE (x
);
1106 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1112 return find_base_term (XEXP (x
, 0));
1115 val
= CSELIB_VAL_PTR (x
);
1116 for (l
= val
->locs
; l
; l
= l
->next
)
1117 if ((x
= find_base_term (l
->loc
)) != 0)
1123 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1130 rtx tmp1
= XEXP (x
, 0);
1131 rtx tmp2
= XEXP (x
, 1);
1133 /* This is a litle bit tricky since we have to determine which of
1134 the two operands represents the real base address. Otherwise this
1135 routine may return the index register instead of the base register.
1137 That may cause us to believe no aliasing was possible, when in
1138 fact aliasing is possible.
1140 We use a few simple tests to guess the base register. Additional
1141 tests can certainly be added. For example, if one of the operands
1142 is a shift or multiply, then it must be the index register and the
1143 other operand is the base register. */
1145 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1146 return find_base_term (tmp2
);
1148 /* If either operand is known to be a pointer, then use it
1149 to determine the base term. */
1150 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1151 return find_base_term (tmp1
);
1153 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1154 return find_base_term (tmp2
);
1156 /* Neither operand was known to be a pointer. Go ahead and find the
1157 base term for both operands. */
1158 tmp1
= find_base_term (tmp1
);
1159 tmp2
= find_base_term (tmp2
);
1161 /* If either base term is named object or a special address
1162 (like an argument or stack reference), then use it for the
1165 && (GET_CODE (tmp1
) == SYMBOL_REF
1166 || GET_CODE (tmp1
) == LABEL_REF
1167 || (GET_CODE (tmp1
) == ADDRESS
1168 && GET_MODE (tmp1
) != VOIDmode
)))
1172 && (GET_CODE (tmp2
) == SYMBOL_REF
1173 || GET_CODE (tmp2
) == LABEL_REF
1174 || (GET_CODE (tmp2
) == ADDRESS
1175 && GET_MODE (tmp2
) != VOIDmode
)))
1178 /* We could not determine which of the two operands was the
1179 base register and which was the index. So we can determine
1180 nothing from the base alias check. */
1185 if (GET_CODE (XEXP (x
, 0)) == REG
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1186 return REG_BASE_VALUE (XEXP (x
, 0));
1194 return REG_BASE_VALUE (frame_pointer_rtx
);
1201 /* Return 0 if the addresses X and Y are known to point to different
1202 objects, 1 if they might be pointers to the same object. */
1205 base_alias_check (x
, y
, x_mode
, y_mode
)
1207 enum machine_mode x_mode
, y_mode
;
1209 rtx x_base
= find_base_term (x
);
1210 rtx y_base
= find_base_term (y
);
1212 /* If the address itself has no known base see if a known equivalent
1213 value has one. If either address still has no known base, nothing
1214 is known about aliasing. */
1219 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1222 x_base
= find_base_term (x_c
);
1230 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1233 y_base
= find_base_term (y_c
);
1238 /* If the base addresses are equal nothing is known about aliasing. */
1239 if (rtx_equal_p (x_base
, y_base
))
1242 /* The base addresses of the read and write are different expressions.
1243 If they are both symbols and they are not accessed via AND, there is
1244 no conflict. We can bring knowledge of object alignment into play
1245 here. For example, on alpha, "char a, b;" can alias one another,
1246 though "char a; long b;" cannot. */
1247 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1249 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1251 if (GET_CODE (x
) == AND
1252 && (GET_CODE (XEXP (x
, 1)) != CONST_INT
1253 || GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1255 if (GET_CODE (y
) == AND
1256 && (GET_CODE (XEXP (y
, 1)) != CONST_INT
1257 || GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1259 /* Differing symbols never alias. */
1263 /* If one address is a stack reference there can be no alias:
1264 stack references using different base registers do not alias,
1265 a stack reference can not alias a parameter, and a stack reference
1266 can not alias a global. */
1267 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
1268 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
1271 if (! flag_argument_noalias
)
1274 if (flag_argument_noalias
> 1)
1277 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1278 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
1281 /* Convert the address X into something we can use. This is done by returning
1282 it unchanged unless it is a value; in the latter case we call cselib to get
1283 a more useful rtx. */
1290 struct elt_loc_list
*l
;
1292 if (GET_CODE (x
) != VALUE
)
1294 v
= CSELIB_VAL_PTR (x
);
1295 for (l
= v
->locs
; l
; l
= l
->next
)
1296 if (CONSTANT_P (l
->loc
))
1298 for (l
= v
->locs
; l
; l
= l
->next
)
1299 if (GET_CODE (l
->loc
) != REG
&& GET_CODE (l
->loc
) != MEM
)
1302 return v
->locs
->loc
;
1306 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1307 where SIZE is the size in bytes of the memory reference. If ADDR
1308 is not modified by the memory reference then ADDR is returned. */
1311 addr_side_effect_eval (addr
, size
, n_refs
)
1318 switch (GET_CODE (addr
))
1321 offset
= (n_refs
+ 1) * size
;
1324 offset
= -(n_refs
+ 1) * size
;
1327 offset
= n_refs
* size
;
1330 offset
= -n_refs
* size
;
1338 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0), GEN_INT (offset
));
1340 addr
= XEXP (addr
, 0);
1345 /* Return nonzero if X and Y (memory addresses) could reference the
1346 same location in memory. C is an offset accumulator. When
1347 C is nonzero, we are testing aliases between X and Y + C.
1348 XSIZE is the size in bytes of the X reference,
1349 similarly YSIZE is the size in bytes for Y.
1351 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1352 referenced (the reference was BLKmode), so make the most pessimistic
1355 If XSIZE or YSIZE is negative, we may access memory outside the object
1356 being referenced as a side effect. This can happen when using AND to
1357 align memory references, as is done on the Alpha.
1359 Nice to notice that varying addresses cannot conflict with fp if no
1360 local variables had their addresses taken, but that's too hard now. */
1363 memrefs_conflict_p (xsize
, x
, ysize
, y
, c
)
1368 if (GET_CODE (x
) == VALUE
)
1370 if (GET_CODE (y
) == VALUE
)
1372 if (GET_CODE (x
) == HIGH
)
1374 else if (GET_CODE (x
) == LO_SUM
)
1377 x
= canon_rtx (addr_side_effect_eval (x
, xsize
, 0));
1378 if (GET_CODE (y
) == HIGH
)
1380 else if (GET_CODE (y
) == LO_SUM
)
1383 y
= canon_rtx (addr_side_effect_eval (y
, ysize
, 0));
1385 if (rtx_equal_for_memref_p (x
, y
))
1387 if (xsize
<= 0 || ysize
<= 0)
1389 if (c
>= 0 && xsize
> c
)
1391 if (c
< 0 && ysize
+c
> 0)
1396 /* This code used to check for conflicts involving stack references and
1397 globals but the base address alias code now handles these cases. */
1399 if (GET_CODE (x
) == PLUS
)
1401 /* The fact that X is canonicalized means that this
1402 PLUS rtx is canonicalized. */
1403 rtx x0
= XEXP (x
, 0);
1404 rtx x1
= XEXP (x
, 1);
1406 if (GET_CODE (y
) == PLUS
)
1408 /* The fact that Y is canonicalized means that this
1409 PLUS rtx is canonicalized. */
1410 rtx y0
= XEXP (y
, 0);
1411 rtx y1
= XEXP (y
, 1);
1413 if (rtx_equal_for_memref_p (x1
, y1
))
1414 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1415 if (rtx_equal_for_memref_p (x0
, y0
))
1416 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
1417 if (GET_CODE (x1
) == CONST_INT
)
1419 if (GET_CODE (y1
) == CONST_INT
)
1420 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
1421 c
- INTVAL (x1
) + INTVAL (y1
));
1423 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
1426 else if (GET_CODE (y1
) == CONST_INT
)
1427 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1431 else if (GET_CODE (x1
) == CONST_INT
)
1432 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
1434 else if (GET_CODE (y
) == PLUS
)
1436 /* The fact that Y is canonicalized means that this
1437 PLUS rtx is canonicalized. */
1438 rtx y0
= XEXP (y
, 0);
1439 rtx y1
= XEXP (y
, 1);
1441 if (GET_CODE (y1
) == CONST_INT
)
1442 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1447 if (GET_CODE (x
) == GET_CODE (y
))
1448 switch (GET_CODE (x
))
1452 /* Handle cases where we expect the second operands to be the
1453 same, and check only whether the first operand would conflict
1456 rtx x1
= canon_rtx (XEXP (x
, 1));
1457 rtx y1
= canon_rtx (XEXP (y
, 1));
1458 if (! rtx_equal_for_memref_p (x1
, y1
))
1460 x0
= canon_rtx (XEXP (x
, 0));
1461 y0
= canon_rtx (XEXP (y
, 0));
1462 if (rtx_equal_for_memref_p (x0
, y0
))
1463 return (xsize
== 0 || ysize
== 0
1464 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1466 /* Can't properly adjust our sizes. */
1467 if (GET_CODE (x1
) != CONST_INT
)
1469 xsize
/= INTVAL (x1
);
1470 ysize
/= INTVAL (x1
);
1472 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1476 /* Are these registers known not to be equal? */
1477 if (alias_invariant
)
1479 unsigned int r_x
= REGNO (x
), r_y
= REGNO (y
);
1480 rtx i_x
, i_y
; /* invariant relationships of X and Y */
1482 i_x
= r_x
>= reg_base_value_size
? 0 : alias_invariant
[r_x
];
1483 i_y
= r_y
>= reg_base_value_size
? 0 : alias_invariant
[r_y
];
1485 if (i_x
== 0 && i_y
== 0)
1488 if (! memrefs_conflict_p (xsize
, i_x
? i_x
: x
,
1489 ysize
, i_y
? i_y
: y
, c
))
1498 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1499 as an access with indeterminate size. Assume that references
1500 besides AND are aligned, so if the size of the other reference is
1501 at least as large as the alignment, assume no other overlap. */
1502 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1504 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1506 return memrefs_conflict_p (xsize
, XEXP (x
, 0), ysize
, y
, c
);
1508 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1510 /* ??? If we are indexing far enough into the array/structure, we
1511 may yet be able to determine that we can not overlap. But we
1512 also need to that we are far enough from the end not to overlap
1513 a following reference, so we do nothing with that for now. */
1514 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1516 return memrefs_conflict_p (xsize
, x
, ysize
, XEXP (y
, 0), c
);
1519 if (GET_CODE (x
) == ADDRESSOF
)
1521 if (y
== frame_pointer_rtx
1522 || GET_CODE (y
) == ADDRESSOF
)
1523 return xsize
<= 0 || ysize
<= 0;
1525 if (GET_CODE (y
) == ADDRESSOF
)
1527 if (x
== frame_pointer_rtx
)
1528 return xsize
<= 0 || ysize
<= 0;
1533 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1535 c
+= (INTVAL (y
) - INTVAL (x
));
1536 return (xsize
<= 0 || ysize
<= 0
1537 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1540 if (GET_CODE (x
) == CONST
)
1542 if (GET_CODE (y
) == CONST
)
1543 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1544 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1546 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1549 if (GET_CODE (y
) == CONST
)
1550 return memrefs_conflict_p (xsize
, x
, ysize
,
1551 canon_rtx (XEXP (y
, 0)), c
);
1554 return (xsize
<= 0 || ysize
<= 0
1555 || (rtx_equal_for_memref_p (x
, y
)
1556 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1563 /* Functions to compute memory dependencies.
1565 Since we process the insns in execution order, we can build tables
1566 to keep track of what registers are fixed (and not aliased), what registers
1567 are varying in known ways, and what registers are varying in unknown
1570 If both memory references are volatile, then there must always be a
1571 dependence between the two references, since their order can not be
1572 changed. A volatile and non-volatile reference can be interchanged
1575 A MEM_IN_STRUCT reference at a non-AND varying address can never
1576 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1577 also must allow AND addresses, because they may generate accesses
1578 outside the object being referenced. This is used to generate
1579 aligned addresses from unaligned addresses, for instance, the alpha
1580 storeqi_unaligned pattern. */
1582 /* Read dependence: X is read after read in MEM takes place. There can
1583 only be a dependence here if both reads are volatile. */
1586 read_dependence (mem
, x
)
1590 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1593 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1594 MEM2 is a reference to a structure at a varying address, or returns
1595 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1596 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1597 to decide whether or not an address may vary; it should return
1598 nonzero whenever variation is possible.
1599 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1602 fixed_scalar_and_varying_struct_p (mem1
, mem2
, mem1_addr
, mem2_addr
, varies_p
)
1604 rtx mem1_addr
, mem2_addr
;
1605 int (*varies_p
) PARAMS ((rtx
, int));
1607 if (! flag_strict_aliasing
)
1610 if (MEM_SCALAR_P (mem1
) && MEM_IN_STRUCT_P (mem2
)
1611 && !varies_p (mem1_addr
, 1) && varies_p (mem2_addr
, 1))
1612 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1616 if (MEM_IN_STRUCT_P (mem1
) && MEM_SCALAR_P (mem2
)
1617 && varies_p (mem1_addr
, 1) && !varies_p (mem2_addr
, 1))
1618 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1625 /* Returns nonzero if something about the mode or address format MEM1
1626 indicates that it might well alias *anything*. */
1629 aliases_everything_p (mem
)
1632 if (GET_CODE (XEXP (mem
, 0)) == AND
)
1633 /* If the address is an AND, its very hard to know at what it is
1634 actually pointing. */
1640 /* True dependence: X is read after store in MEM takes place. */
1643 true_dependence (mem
, mem_mode
, x
, varies
)
1645 enum machine_mode mem_mode
;
1647 int (*varies
) PARAMS ((rtx
, int));
1649 register rtx x_addr
, mem_addr
;
1652 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
1655 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
1658 /* Unchanging memory can't conflict with non-unchanging memory.
1659 A non-unchanging read can conflict with a non-unchanging write.
1660 An unchanging read can conflict with an unchanging write since
1661 there may be a single store to this address to initialize it.
1662 Note that an unchanging store can conflict with a non-unchanging read
1663 since we have to make conservative assumptions when we have a
1664 record with readonly fields and we are copying the whole thing.
1665 Just fall through to the code below to resolve potential conflicts.
1666 This won't handle all cases optimally, but the possible performance
1667 loss should be negligible. */
1668 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
1671 if (mem_mode
== VOIDmode
)
1672 mem_mode
= GET_MODE (mem
);
1674 x_addr
= get_addr (XEXP (x
, 0));
1675 mem_addr
= get_addr (XEXP (mem
, 0));
1677 base
= find_base_term (x_addr
);
1678 if (base
&& (GET_CODE (base
) == LABEL_REF
1679 || (GET_CODE (base
) == SYMBOL_REF
1680 && CONSTANT_POOL_ADDRESS_P (base
))))
1683 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
1686 x_addr
= canon_rtx (x_addr
);
1687 mem_addr
= canon_rtx (mem_addr
);
1689 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
1690 SIZE_FOR_MODE (x
), x_addr
, 0))
1693 if (aliases_everything_p (x
))
1696 /* We cannot use aliases_everyting_p to test MEM, since we must look
1697 at MEM_MODE, rather than GET_MODE (MEM). */
1698 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
1701 /* In true_dependence we also allow BLKmode to alias anything. Why
1702 don't we do this in anti_dependence and output_dependence? */
1703 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
1706 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
1710 /* Returns non-zero if a write to X might alias a previous read from
1711 (or, if WRITEP is non-zero, a write to) MEM. */
1714 write_dependence_p (mem
, x
, writep
)
1719 rtx x_addr
, mem_addr
;
1723 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
1726 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
1729 /* Unchanging memory can't conflict with non-unchanging memory. */
1730 if (RTX_UNCHANGING_P (x
) != RTX_UNCHANGING_P (mem
))
1733 /* If MEM is an unchanging read, then it can't possibly conflict with
1734 the store to X, because there is at most one store to MEM, and it must
1735 have occurred somewhere before MEM. */
1736 if (! writep
&& RTX_UNCHANGING_P (mem
))
1739 x_addr
= get_addr (XEXP (x
, 0));
1740 mem_addr
= get_addr (XEXP (mem
, 0));
1744 base
= find_base_term (mem_addr
);
1745 if (base
&& (GET_CODE (base
) == LABEL_REF
1746 || (GET_CODE (base
) == SYMBOL_REF
1747 && CONSTANT_POOL_ADDRESS_P (base
))))
1751 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
1755 x_addr
= canon_rtx (x_addr
);
1756 mem_addr
= canon_rtx (mem_addr
);
1758 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
1759 SIZE_FOR_MODE (x
), x_addr
, 0))
1763 = fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
1766 return (!(fixed_scalar
== mem
&& !aliases_everything_p (x
))
1767 && !(fixed_scalar
== x
&& !aliases_everything_p (mem
)));
1770 /* Anti dependence: X is written after read in MEM takes place. */
1773 anti_dependence (mem
, x
)
1777 return write_dependence_p (mem
, x
, /*writep=*/0);
1780 /* Output dependence: X is written after store in MEM takes place. */
1783 output_dependence (mem
, x
)
1787 return write_dependence_p (mem
, x
, /*writep=*/1);
1790 /* Returns non-zero if X mentions something which is not
1791 local to the function and is not constant. */
1794 nonlocal_mentioned_p (x
)
1798 register RTX_CODE code
;
1801 code
= GET_CODE (x
);
1803 if (GET_RTX_CLASS (code
) == 'i')
1805 /* Constant functions can be constant if they don't use
1806 scratch memory used to mark function w/o side effects. */
1807 if (code
== CALL_INSN
&& CONST_CALL_P (x
))
1809 x
= CALL_INSN_FUNCTION_USAGE (x
);
1815 code
= GET_CODE (x
);
1821 if (GET_CODE (SUBREG_REG (x
)) == REG
)
1823 /* Global registers are not local. */
1824 if (REGNO (SUBREG_REG (x
)) < FIRST_PSEUDO_REGISTER
1825 && global_regs
[REGNO (SUBREG_REG (x
)) + SUBREG_WORD (x
)])
1833 /* Global registers are not local. */
1834 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1848 /* Constants in the function's constants pool are constant. */
1849 if (CONSTANT_POOL_ADDRESS_P (x
))
1854 /* Non-constant calls and recursion are not local. */
1858 /* Be overly conservative and consider any volatile memory
1859 reference as not local. */
1860 if (MEM_VOLATILE_P (x
))
1862 base
= find_base_term (XEXP (x
, 0));
1865 /* A Pmode ADDRESS could be a reference via the structure value
1866 address or static chain. Such memory references are nonlocal.
1868 Thus, we have to examine the contents of the ADDRESS to find
1869 out if this is a local reference or not. */
1870 if (GET_CODE (base
) == ADDRESS
1871 && GET_MODE (base
) == Pmode
1872 && (XEXP (base
, 0) == stack_pointer_rtx
1873 || XEXP (base
, 0) == arg_pointer_rtx
1874 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1875 || XEXP (base
, 0) == hard_frame_pointer_rtx
1877 || XEXP (base
, 0) == frame_pointer_rtx
))
1879 /* Constants in the function's constant pool are constant. */
1880 if (GET_CODE (base
) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (base
))
1885 case UNSPEC_VOLATILE
:
1890 if (MEM_VOLATILE_P (x
))
1899 /* Recursively scan the operands of this expression. */
1902 register const char *fmt
= GET_RTX_FORMAT (code
);
1905 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1907 if (fmt
[i
] == 'e' && XEXP (x
, i
))
1909 if (nonlocal_mentioned_p (XEXP (x
, i
)))
1912 else if (fmt
[i
] == 'E')
1915 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1916 if (nonlocal_mentioned_p (XVECEXP (x
, i
, j
)))
1925 /* Return non-zero if a loop (natural or otherwise) is present.
1926 Inspired by Depth_First_Search_PP described in:
1928 Advanced Compiler Design and Implementation
1930 Morgan Kaufmann, 1997
1932 and heavily borrowed from flow_depth_first_order_compute. */
1945 /* Allocate the preorder and postorder number arrays. */
1946 pre
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1947 post
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1949 /* Allocate stack for back-tracking up CFG. */
1950 stack
= (edge
*) xmalloc ((n_basic_blocks
+ 1) * sizeof (edge
));
1953 /* Allocate bitmap to track nodes that have been visited. */
1954 visited
= sbitmap_alloc (n_basic_blocks
);
1956 /* None of the nodes in the CFG have been visited yet. */
1957 sbitmap_zero (visited
);
1959 /* Push the first edge on to the stack. */
1960 stack
[sp
++] = ENTRY_BLOCK_PTR
->succ
;
1968 /* Look at the edge on the top of the stack. */
1973 /* Check if the edge destination has been visited yet. */
1974 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
1976 /* Mark that we have visited the destination. */
1977 SET_BIT (visited
, dest
->index
);
1979 pre
[dest
->index
] = prenum
++;
1983 /* Since the DEST node has been visited for the first
1984 time, check its successors. */
1985 stack
[sp
++] = dest
->succ
;
1988 post
[dest
->index
] = postnum
++;
1992 if (dest
!= EXIT_BLOCK_PTR
1993 && pre
[src
->index
] >= pre
[dest
->index
]
1994 && post
[dest
->index
] == 0)
1997 if (! e
->succ_next
&& src
!= ENTRY_BLOCK_PTR
)
1998 post
[src
->index
] = postnum
++;
2001 stack
[sp
- 1] = e
->succ_next
;
2010 sbitmap_free (visited
);
2015 /* Mark the function if it is constant. */
2018 mark_constant_function ()
2021 int nonlocal_mentioned
;
2023 if (TREE_PUBLIC (current_function_decl
)
2024 || TREE_READONLY (current_function_decl
)
2025 || DECL_IS_PURE (current_function_decl
)
2026 || TREE_THIS_VOLATILE (current_function_decl
)
2027 || TYPE_MODE (TREE_TYPE (current_function_decl
)) == VOIDmode
)
2030 /* A loop might not return which counts as a side effect. */
2034 nonlocal_mentioned
= 0;
2036 init_alias_analysis ();
2038 /* Determine if this is a constant function. */
2040 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2041 if (INSN_P (insn
) && nonlocal_mentioned_p (insn
))
2043 nonlocal_mentioned
= 1;
2047 end_alias_analysis ();
2049 /* Mark the function. */
2051 if (! nonlocal_mentioned
)
2052 TREE_READONLY (current_function_decl
) = 1;
2056 static HARD_REG_SET argument_registers
;
2063 #ifndef OUTGOING_REGNO
2064 #define OUTGOING_REGNO(N) N
2066 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2067 /* Check whether this register can hold an incoming pointer
2068 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2069 numbers, so translate if necessary due to register windows. */
2070 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2071 && HARD_REGNO_MODE_OK (i
, Pmode
))
2072 SET_HARD_REG_BIT (argument_registers
, i
);
2074 alias_sets
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
2077 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2081 init_alias_analysis ()
2083 int maxreg
= max_reg_num ();
2086 register unsigned int ui
;
2089 reg_known_value_size
= maxreg
;
2092 = (rtx
*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (rtx
))
2093 - FIRST_PSEUDO_REGISTER
;
2095 = (char*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (char))
2096 - FIRST_PSEUDO_REGISTER
;
2098 /* Overallocate reg_base_value to allow some growth during loop
2099 optimization. Loop unrolling can create a large number of
2101 reg_base_value_size
= maxreg
* 2;
2102 reg_base_value
= (rtx
*) xcalloc (reg_base_value_size
, sizeof (rtx
));
2103 ggc_add_rtx_root (reg_base_value
, reg_base_value_size
);
2105 new_reg_base_value
= (rtx
*) xmalloc (reg_base_value_size
* sizeof (rtx
));
2106 reg_seen
= (char *) xmalloc (reg_base_value_size
);
2107 if (! reload_completed
&& flag_unroll_loops
)
2109 /* ??? Why are we realloc'ing if we're just going to zero it? */
2110 alias_invariant
= (rtx
*)xrealloc (alias_invariant
,
2111 reg_base_value_size
* sizeof (rtx
));
2112 memset ((char *)alias_invariant
, 0, reg_base_value_size
* sizeof (rtx
));
2116 /* The basic idea is that each pass through this loop will use the
2117 "constant" information from the previous pass to propagate alias
2118 information through another level of assignments.
2120 This could get expensive if the assignment chains are long. Maybe
2121 we should throttle the number of iterations, possibly based on
2122 the optimization level or flag_expensive_optimizations.
2124 We could propagate more information in the first pass by making use
2125 of REG_N_SETS to determine immediately that the alias information
2126 for a pseudo is "constant".
2128 A program with an uninitialized variable can cause an infinite loop
2129 here. Instead of doing a full dataflow analysis to detect such problems
2130 we just cap the number of iterations for the loop.
2132 The state of the arrays for the set chain in question does not matter
2133 since the program has undefined behavior. */
2138 /* Assume nothing will change this iteration of the loop. */
2141 /* We want to assign the same IDs each iteration of this loop, so
2142 start counting from zero each iteration of the loop. */
2145 /* We're at the start of the funtion each iteration through the
2146 loop, so we're copying arguments. */
2147 copying_arguments
= 1;
2149 /* Wipe the potential alias information clean for this pass. */
2150 memset ((char *) new_reg_base_value
, 0, reg_base_value_size
* sizeof (rtx
));
2152 /* Wipe the reg_seen array clean. */
2153 memset ((char *) reg_seen
, 0, reg_base_value_size
);
2155 /* Mark all hard registers which may contain an address.
2156 The stack, frame and argument pointers may contain an address.
2157 An argument register which can hold a Pmode value may contain
2158 an address even if it is not in BASE_REGS.
2160 The address expression is VOIDmode for an argument and
2161 Pmode for other registers. */
2163 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2164 if (TEST_HARD_REG_BIT (argument_registers
, i
))
2165 new_reg_base_value
[i
] = gen_rtx_ADDRESS (VOIDmode
,
2166 gen_rtx_REG (Pmode
, i
));
2168 new_reg_base_value
[STACK_POINTER_REGNUM
]
2169 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
2170 new_reg_base_value
[ARG_POINTER_REGNUM
]
2171 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
2172 new_reg_base_value
[FRAME_POINTER_REGNUM
]
2173 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
2174 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2175 new_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2176 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
2179 /* Walk the insns adding values to the new_reg_base_value array. */
2180 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2186 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2187 /* The prologue/epilouge insns are not threaded onto the
2188 insn chain until after reload has completed. Thus,
2189 there is no sense wasting time checking if INSN is in
2190 the prologue/epilogue until after reload has completed. */
2191 if (reload_completed
2192 && prologue_epilogue_contains (insn
))
2196 /* If this insn has a noalias note, process it, Otherwise,
2197 scan for sets. A simple set will have no side effects
2198 which could change the base value of any other register. */
2200 if (GET_CODE (PATTERN (insn
)) == SET
2201 && REG_NOTES (insn
) != 0
2202 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2203 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2205 note_stores (PATTERN (insn
), record_set
, NULL
);
2207 set
= single_set (insn
);
2210 && GET_CODE (SET_DEST (set
)) == REG
2211 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
2212 && REG_NOTES (insn
) != 0
2213 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
2214 && REG_N_SETS (REGNO (SET_DEST (set
))) == 1)
2215 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
2216 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2217 && ! reg_overlap_mentioned_p (SET_DEST (set
), XEXP (note
, 0)))
2219 int regno
= REGNO (SET_DEST (set
));
2220 reg_known_value
[regno
] = XEXP (note
, 0);
2221 reg_known_equiv_p
[regno
] = REG_NOTE_KIND (note
) == REG_EQUIV
;
2224 else if (GET_CODE (insn
) == NOTE
2225 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
2226 copying_arguments
= 0;
2229 /* Now propagate values from new_reg_base_value to reg_base_value. */
2230 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2232 if (new_reg_base_value
[ui
]
2233 && new_reg_base_value
[ui
] != reg_base_value
[ui
]
2234 && ! rtx_equal_p (new_reg_base_value
[ui
], reg_base_value
[ui
]))
2236 reg_base_value
[ui
] = new_reg_base_value
[ui
];
2241 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2243 /* Fill in the remaining entries. */
2244 for (i
= FIRST_PSEUDO_REGISTER
; i
< maxreg
; i
++)
2245 if (reg_known_value
[i
] == 0)
2246 reg_known_value
[i
] = regno_reg_rtx
[i
];
2248 /* Simplify the reg_base_value array so that no register refers to
2249 another register, except to special registers indirectly through
2250 ADDRESS expressions.
2252 In theory this loop can take as long as O(registers^2), but unless
2253 there are very long dependency chains it will run in close to linear
2256 This loop may not be needed any longer now that the main loop does
2257 a better job at propagating alias information. */
2263 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2265 rtx base
= reg_base_value
[ui
];
2266 if (base
&& GET_CODE (base
) == REG
)
2268 unsigned int base_regno
= REGNO (base
);
2269 if (base_regno
== ui
) /* register set from itself */
2270 reg_base_value
[ui
] = 0;
2272 reg_base_value
[ui
] = reg_base_value
[base_regno
];
2277 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
2280 free (new_reg_base_value
);
2281 new_reg_base_value
= 0;
2287 end_alias_analysis ()
2289 free (reg_known_value
+ FIRST_PSEUDO_REGISTER
);
2290 reg_known_value
= 0;
2291 reg_known_value_size
= 0;
2292 free (reg_known_equiv_p
+ FIRST_PSEUDO_REGISTER
);
2293 reg_known_equiv_p
= 0;
2296 ggc_del_root (reg_base_value
);
2297 free (reg_base_value
);
2300 reg_base_value_size
= 0;
2301 if (alias_invariant
)
2303 free (alias_invariant
);
2304 alias_invariant
= 0;