1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
3 Free Software Foundation, Inc.
4 Contributed by John Carr (jfc@mit.edu).
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
39 #include "splay-tree.h"
41 #include "langhooks.h"
47 /* The alias sets assigned to MEMs assist the back-end in determining
48 which MEMs can alias which other MEMs. In general, two MEMs in
49 different alias sets cannot alias each other, with one important
50 exception. Consider something like:
52 struct S { int i; double d; };
54 a store to an `S' can alias something of either type `int' or type
55 `double'. (However, a store to an `int' cannot alias a `double'
56 and vice versa.) We indicate this via a tree structure that looks
64 (The arrows are directed and point downwards.)
65 In this situation we say the alias set for `struct S' is the
66 `superset' and that those for `int' and `double' are `subsets'.
68 To see whether two alias sets can point to the same memory, we must
69 see if either alias set is a subset of the other. We need not trace
70 past immediate descendants, however, since we propagate all
71 grandchildren up one level.
73 Alias set zero is implicitly a superset of all other alias sets.
74 However, this is no actual entry for alias set zero. It is an
75 error to attempt to explicitly construct a subset of zero. */
77 struct alias_set_entry
GTY(())
79 /* The alias set number, as stored in MEM_ALIAS_SET. */
80 HOST_WIDE_INT alias_set
;
82 /* The children of the alias set. These are not just the immediate
83 children, but, in fact, all descendants. So, if we have:
85 struct T { struct S s; float f; }
87 continuing our example above, the children here will be all of
88 `int', `double', `float', and `struct S'. */
89 splay_tree
GTY((param1_is (int), param2_is (int))) children
;
91 /* Nonzero if would have a child of zero: this effectively makes this
92 alias set the same as alias set zero. */
95 typedef struct alias_set_entry
*alias_set_entry
;
97 static int rtx_equal_for_memref_p (rtx
, rtx
);
98 static rtx
find_symbolic_term (rtx
);
99 static int memrefs_conflict_p (int, rtx
, int, rtx
, HOST_WIDE_INT
);
100 static void record_set (rtx
, rtx
, void *);
101 static int base_alias_check (rtx
, rtx
, enum machine_mode
,
103 static rtx
find_base_value (rtx
);
104 static int mems_in_disjoint_alias_sets_p (rtx
, rtx
);
105 static int insert_subset_children (splay_tree_node
, void*);
106 static tree
find_base_decl (tree
);
107 static alias_set_entry
get_alias_set_entry (HOST_WIDE_INT
);
108 static rtx
fixed_scalar_and_varying_struct_p (rtx
, rtx
, rtx
, rtx
,
110 static int aliases_everything_p (rtx
);
111 static bool nonoverlapping_component_refs_p (tree
, tree
);
112 static tree
decl_for_component_ref (tree
);
113 static rtx
adjust_offset_for_component_ref (tree
, rtx
);
114 static int nonoverlapping_memrefs_p (rtx
, rtx
);
115 static int write_dependence_p (rtx
, rtx
, int, int);
117 static int nonlocal_mentioned_p_1 (rtx
*, void *);
118 static int nonlocal_mentioned_p (rtx
);
119 static int nonlocal_referenced_p_1 (rtx
*, void *);
120 static int nonlocal_referenced_p (rtx
);
121 static int nonlocal_set_p_1 (rtx
*, void *);
122 static int nonlocal_set_p (rtx
);
123 static void memory_modified_1 (rtx
, rtx
, void *);
125 /* Set up all info needed to perform alias analysis on memory references. */
127 /* Returns the size in bytes of the mode of X. */
128 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
130 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
131 different alias sets. We ignore alias sets in functions making use
132 of variable arguments because the va_arg macros on some systems are
134 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
135 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
137 /* Cap the number of passes we make over the insns propagating alias
138 information through set chains. 10 is a completely arbitrary choice. */
139 #define MAX_ALIAS_LOOP_PASSES 10
141 /* reg_base_value[N] gives an address to which register N is related.
142 If all sets after the first add or subtract to the current value
143 or otherwise modify it so it does not point to a different top level
144 object, reg_base_value[N] is equal to the address part of the source
147 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
148 expressions represent certain special values: function arguments and
149 the stack, frame, and argument pointers.
151 The contents of an ADDRESS is not normally used, the mode of the
152 ADDRESS determines whether the ADDRESS is a function argument or some
153 other special value. Pointer equality, not rtx_equal_p, determines whether
154 two ADDRESS expressions refer to the same base address.
156 The only use of the contents of an ADDRESS is for determining if the
157 current function performs nonlocal memory memory references for the
158 purposes of marking the function as a constant function. */
160 static GTY((length ("reg_base_value_size"))) rtx
*reg_base_value
;
161 static rtx
*new_reg_base_value
;
162 static unsigned int reg_base_value_size
; /* size of reg_base_value array */
164 /* Static hunks of RTL used by the aliasing code; these are initialized
165 once per function to avoid unnecessary RTL allocations. */
166 static GTY (()) rtx static_reg_base_value
[FIRST_PSEUDO_REGISTER
];
168 #define REG_BASE_VALUE(X) \
169 (REGNO (X) < reg_base_value_size \
170 ? reg_base_value[REGNO (X)] : 0)
172 /* Vector of known invariant relationships between registers. Set in
173 loop unrolling. Indexed by register number, if nonzero the value
174 is an expression describing this register in terms of another.
176 The length of this array is REG_BASE_VALUE_SIZE.
178 Because this array contains only pseudo registers it has no effect
180 static rtx
*alias_invariant
;
182 /* Vector indexed by N giving the initial (unchanging) value known for
183 pseudo-register N. This array is initialized in
184 init_alias_analysis, and does not change until end_alias_analysis
186 rtx
*reg_known_value
;
188 /* Indicates number of valid entries in reg_known_value. */
189 static unsigned int reg_known_value_size
;
191 /* Vector recording for each reg_known_value whether it is due to a
192 REG_EQUIV note. Future passes (viz., reload) may replace the
193 pseudo with the equivalent expression and so we account for the
194 dependences that would be introduced if that happens.
196 The REG_EQUIV notes created in assign_parms may mention the arg
197 pointer, and there are explicit insns in the RTL that modify the
198 arg pointer. Thus we must ensure that such insns don't get
199 scheduled across each other because that would invalidate the
200 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
201 wrong, but solving the problem in the scheduler will likely give
202 better code, so we do it here. */
203 char *reg_known_equiv_p
;
205 /* True when scanning insns from the start of the rtl to the
206 NOTE_INSN_FUNCTION_BEG note. */
207 static bool copying_arguments
;
209 /* The splay-tree used to store the various alias set entries. */
210 static GTY ((param_is (struct alias_set_entry
))) varray_type alias_sets
;
212 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
213 such an entry, or NULL otherwise. */
215 static inline alias_set_entry
216 get_alias_set_entry (HOST_WIDE_INT alias_set
)
218 return (alias_set_entry
)VARRAY_GENERIC_PTR (alias_sets
, alias_set
);
221 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
222 the two MEMs cannot alias each other. */
225 mems_in_disjoint_alias_sets_p (rtx mem1
, rtx mem2
)
227 #ifdef ENABLE_CHECKING
228 /* Perform a basic sanity check. Namely, that there are no alias sets
229 if we're not using strict aliasing. This helps to catch bugs
230 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
231 where a MEM is allocated in some way other than by the use of
232 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
233 use alias sets to indicate that spilled registers cannot alias each
234 other, we might need to remove this check. */
235 if (! flag_strict_aliasing
236 && (MEM_ALIAS_SET (mem1
) != 0 || MEM_ALIAS_SET (mem2
) != 0))
240 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
243 /* Insert the NODE into the splay tree given by DATA. Used by
244 record_alias_subset via splay_tree_foreach. */
247 insert_subset_children (splay_tree_node node
, void *data
)
249 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
254 /* Return 1 if the two specified alias sets may conflict. */
257 alias_sets_conflict_p (HOST_WIDE_INT set1
, HOST_WIDE_INT set2
)
261 /* If have no alias set information for one of the operands, we have
262 to assume it can alias anything. */
263 if (set1
== 0 || set2
== 0
264 /* If the two alias sets are the same, they may alias. */
268 /* See if the first alias set is a subset of the second. */
269 ase
= get_alias_set_entry (set1
);
271 && (ase
->has_zero_child
272 || splay_tree_lookup (ase
->children
,
273 (splay_tree_key
) set2
)))
276 /* Now do the same, but with the alias sets reversed. */
277 ase
= get_alias_set_entry (set2
);
279 && (ase
->has_zero_child
280 || splay_tree_lookup (ase
->children
,
281 (splay_tree_key
) set1
)))
284 /* The two alias sets are distinct and neither one is the
285 child of the other. Therefore, they cannot alias. */
289 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
290 has any readonly fields. If any of the fields have types that
291 contain readonly fields, return true as well. */
294 readonly_fields_p (tree type
)
298 if (TREE_CODE (type
) != RECORD_TYPE
&& TREE_CODE (type
) != UNION_TYPE
299 && TREE_CODE (type
) != QUAL_UNION_TYPE
)
302 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
303 if (TREE_CODE (field
) == FIELD_DECL
304 && (TREE_READONLY (field
)
305 || readonly_fields_p (TREE_TYPE (field
))))
311 /* Return 1 if any MEM object of type T1 will always conflict (using the
312 dependency routines in this file) with any MEM object of type T2.
313 This is used when allocating temporary storage. If T1 and/or T2 are
314 NULL_TREE, it means we know nothing about the storage. */
317 objects_must_conflict_p (tree t1
, tree t2
)
319 HOST_WIDE_INT set1
, set2
;
321 /* If neither has a type specified, we don't know if they'll conflict
322 because we may be using them to store objects of various types, for
323 example the argument and local variables areas of inlined functions. */
324 if (t1
== 0 && t2
== 0)
327 /* If one or the other has readonly fields or is readonly,
328 then they may not conflict. */
329 if ((t1
!= 0 && readonly_fields_p (t1
))
330 || (t2
!= 0 && readonly_fields_p (t2
))
331 || (t1
!= 0 && lang_hooks
.honor_readonly
&& TYPE_READONLY (t1
))
332 || (t2
!= 0 && lang_hooks
.honor_readonly
&& TYPE_READONLY (t2
)))
335 /* If they are the same type, they must conflict. */
337 /* Likewise if both are volatile. */
338 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
341 set1
= t1
? get_alias_set (t1
) : 0;
342 set2
= t2
? get_alias_set (t2
) : 0;
344 /* Otherwise they conflict if they have no alias set or the same. We
345 can't simply use alias_sets_conflict_p here, because we must make
346 sure that every subtype of t1 will conflict with every subtype of
347 t2 for which a pair of subobjects of these respective subtypes
348 overlaps on the stack. */
349 return set1
== 0 || set2
== 0 || set1
== set2
;
352 /* T is an expression with pointer type. Find the DECL on which this
353 expression is based. (For example, in `a[i]' this would be `a'.)
354 If there is no such DECL, or a unique decl cannot be determined,
355 NULL_TREE is returned. */
358 find_base_decl (tree t
)
362 if (t
== 0 || t
== error_mark_node
|| ! POINTER_TYPE_P (TREE_TYPE (t
)))
365 /* If this is a declaration, return it. */
366 if (TREE_CODE_CLASS (TREE_CODE (t
)) == 'd')
369 /* Handle general expressions. It would be nice to deal with
370 COMPONENT_REFs here. If we could tell that `a' and `b' were the
371 same, then `a->f' and `b->f' are also the same. */
372 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
375 return find_base_decl (TREE_OPERAND (t
, 0));
378 /* Return 0 if found in neither or both are the same. */
379 d0
= find_base_decl (TREE_OPERAND (t
, 0));
380 d1
= find_base_decl (TREE_OPERAND (t
, 1));
391 d0
= find_base_decl (TREE_OPERAND (t
, 0));
392 d1
= find_base_decl (TREE_OPERAND (t
, 1));
393 d2
= find_base_decl (TREE_OPERAND (t
, 2));
395 /* Set any nonzero values from the last, then from the first. */
396 if (d1
== 0) d1
= d2
;
397 if (d0
== 0) d0
= d1
;
398 if (d1
== 0) d1
= d0
;
399 if (d2
== 0) d2
= d1
;
401 /* At this point all are nonzero or all are zero. If all three are the
402 same, return it. Otherwise, return zero. */
403 return (d0
== d1
&& d1
== d2
) ? d0
: 0;
410 /* Return 1 if all the nested component references handled by
411 get_inner_reference in T are such that we can address the object in T. */
414 can_address_p (tree t
)
416 /* If we're at the end, it is vacuously addressable. */
417 if (! handled_component_p (t
))
420 /* Bitfields are never addressable. */
421 else if (TREE_CODE (t
) == BIT_FIELD_REF
)
424 /* Fields are addressable unless they are marked as nonaddressable or
425 the containing type has alias set 0. */
426 else if (TREE_CODE (t
) == COMPONENT_REF
427 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1))
428 && get_alias_set (TREE_TYPE (TREE_OPERAND (t
, 0))) != 0
429 && can_address_p (TREE_OPERAND (t
, 0)))
432 /* Likewise for arrays. */
433 else if ((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
434 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0)))
435 && get_alias_set (TREE_TYPE (TREE_OPERAND (t
, 0))) != 0
436 && can_address_p (TREE_OPERAND (t
, 0)))
442 /* Return the alias set for T, which may be either a type or an
443 expression. Call language-specific routine for help, if needed. */
446 get_alias_set (tree t
)
450 /* If we're not doing any alias analysis, just assume everything
451 aliases everything else. Also return 0 if this or its type is
453 if (! flag_strict_aliasing
|| t
== error_mark_node
455 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
458 /* We can be passed either an expression or a type. This and the
459 language-specific routine may make mutually-recursive calls to each other
460 to figure out what to do. At each juncture, we see if this is a tree
461 that the language may need to handle specially. First handle things that
466 tree placeholder_ptr
= 0;
468 /* Remove any nops, then give the language a chance to do
469 something with this tree before we look at it. */
471 set
= (*lang_hooks
.get_alias_set
) (t
);
475 /* First see if the actual object referenced is an INDIRECT_REF from a
476 restrict-qualified pointer or a "void *". Replace
477 PLACEHOLDER_EXPRs. */
478 while (TREE_CODE (inner
) == PLACEHOLDER_EXPR
479 || handled_component_p (inner
))
481 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
)
482 inner
= find_placeholder (inner
, &placeholder_ptr
);
484 inner
= TREE_OPERAND (inner
, 0);
489 /* Check for accesses through restrict-qualified pointers. */
490 if (TREE_CODE (inner
) == INDIRECT_REF
)
492 tree decl
= find_base_decl (TREE_OPERAND (inner
, 0));
494 if (decl
&& DECL_POINTER_ALIAS_SET_KNOWN_P (decl
))
496 /* If we haven't computed the actual alias set, do it now. */
497 if (DECL_POINTER_ALIAS_SET (decl
) == -2)
499 /* No two restricted pointers can point at the same thing.
500 However, a restricted pointer can point at the same thing
501 as an unrestricted pointer, if that unrestricted pointer
502 is based on the restricted pointer. So, we make the
503 alias set for the restricted pointer a subset of the
504 alias set for the type pointed to by the type of the
506 HOST_WIDE_INT pointed_to_alias_set
507 = get_alias_set (TREE_TYPE (TREE_TYPE (decl
)));
509 if (pointed_to_alias_set
== 0)
510 /* It's not legal to make a subset of alias set zero. */
511 DECL_POINTER_ALIAS_SET (decl
) = 0;
514 DECL_POINTER_ALIAS_SET (decl
) = new_alias_set ();
515 record_alias_subset (pointed_to_alias_set
,
516 DECL_POINTER_ALIAS_SET (decl
));
520 /* We use the alias set indicated in the declaration. */
521 return DECL_POINTER_ALIAS_SET (decl
);
524 /* If we have an INDIRECT_REF via a void pointer, we don't
525 know anything about what that might alias. */
526 else if (TREE_CODE (TREE_TYPE (inner
)) == VOID_TYPE
)
530 /* Otherwise, pick up the outermost object that we could have a pointer
531 to, processing conversion and PLACEHOLDER_EXPR as above. */
533 while (TREE_CODE (t
) == PLACEHOLDER_EXPR
534 || (handled_component_p (t
) && ! can_address_p (t
)))
536 if (TREE_CODE (t
) == PLACEHOLDER_EXPR
)
537 t
= find_placeholder (t
, &placeholder_ptr
);
539 t
= TREE_OPERAND (t
, 0);
544 /* If we've already determined the alias set for a decl, just return
545 it. This is necessary for C++ anonymous unions, whose component
546 variables don't look like union members (boo!). */
547 if (TREE_CODE (t
) == VAR_DECL
548 && DECL_RTL_SET_P (t
) && GET_CODE (DECL_RTL (t
)) == MEM
)
549 return MEM_ALIAS_SET (DECL_RTL (t
));
551 /* Now all we care about is the type. */
555 /* Variant qualifiers don't affect the alias set, so get the main
556 variant. If this is a type with a known alias set, return it. */
557 t
= TYPE_MAIN_VARIANT (t
);
558 if (TYPE_ALIAS_SET_KNOWN_P (t
))
559 return TYPE_ALIAS_SET (t
);
561 /* See if the language has special handling for this type. */
562 set
= (*lang_hooks
.get_alias_set
) (t
);
566 /* There are no objects of FUNCTION_TYPE, so there's no point in
567 using up an alias set for them. (There are, of course, pointers
568 and references to functions, but that's different.) */
569 else if (TREE_CODE (t
) == FUNCTION_TYPE
)
572 /* Unless the language specifies otherwise, let vector types alias
573 their components. This avoids some nasty type punning issues in
574 normal usage. And indeed lets vectors be treated more like an
576 else if (TREE_CODE (t
) == VECTOR_TYPE
)
577 set
= get_alias_set (TREE_TYPE (t
));
580 /* Otherwise make a new alias set for this type. */
581 set
= new_alias_set ();
583 TYPE_ALIAS_SET (t
) = set
;
585 /* If this is an aggregate type, we must record any component aliasing
587 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
588 record_component_aliases (t
);
593 /* Return a brand-new alias set. */
595 static GTY(()) HOST_WIDE_INT last_alias_set
;
600 if (flag_strict_aliasing
)
603 VARRAY_GENERIC_PTR_INIT (alias_sets
, 10, "alias sets");
605 VARRAY_GROW (alias_sets
, last_alias_set
+ 2);
606 return ++last_alias_set
;
612 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
613 not everything that aliases SUPERSET also aliases SUBSET. For example,
614 in C, a store to an `int' can alias a load of a structure containing an
615 `int', and vice versa. But it can't alias a load of a 'double' member
616 of the same structure. Here, the structure would be the SUPERSET and
617 `int' the SUBSET. This relationship is also described in the comment at
618 the beginning of this file.
620 This function should be called only once per SUPERSET/SUBSET pair.
622 It is illegal for SUPERSET to be zero; everything is implicitly a
623 subset of alias set zero. */
626 record_alias_subset (HOST_WIDE_INT superset
, HOST_WIDE_INT subset
)
628 alias_set_entry superset_entry
;
629 alias_set_entry subset_entry
;
631 /* It is possible in complex type situations for both sets to be the same,
632 in which case we can ignore this operation. */
633 if (superset
== subset
)
639 superset_entry
= get_alias_set_entry (superset
);
640 if (superset_entry
== 0)
642 /* Create an entry for the SUPERSET, so that we have a place to
643 attach the SUBSET. */
644 superset_entry
= ggc_alloc (sizeof (struct alias_set_entry
));
645 superset_entry
->alias_set
= superset
;
646 superset_entry
->children
647 = splay_tree_new_ggc (splay_tree_compare_ints
);
648 superset_entry
->has_zero_child
= 0;
649 VARRAY_GENERIC_PTR (alias_sets
, superset
) = superset_entry
;
653 superset_entry
->has_zero_child
= 1;
656 subset_entry
= get_alias_set_entry (subset
);
657 /* If there is an entry for the subset, enter all of its children
658 (if they are not already present) as children of the SUPERSET. */
661 if (subset_entry
->has_zero_child
)
662 superset_entry
->has_zero_child
= 1;
664 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
665 superset_entry
->children
);
668 /* Enter the SUBSET itself as a child of the SUPERSET. */
669 splay_tree_insert (superset_entry
->children
,
670 (splay_tree_key
) subset
, 0);
674 /* Record that component types of TYPE, if any, are part of that type for
675 aliasing purposes. For record types, we only record component types
676 for fields that are marked addressable. For array types, we always
677 record the component types, so the front end should not call this
678 function if the individual component aren't addressable. */
681 record_component_aliases (tree type
)
683 HOST_WIDE_INT superset
= get_alias_set (type
);
689 switch (TREE_CODE (type
))
692 if (! TYPE_NONALIASED_COMPONENT (type
))
693 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
698 case QUAL_UNION_TYPE
:
699 /* Recursively record aliases for the base classes, if there are any. */
700 if (TYPE_BINFO (type
) != NULL
&& TYPE_BINFO_BASETYPES (type
) != NULL
)
703 for (i
= 0; i
< TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type
)); i
++)
705 tree binfo
= TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type
), i
);
706 record_alias_subset (superset
,
707 get_alias_set (BINFO_TYPE (binfo
)));
710 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
711 if (TREE_CODE (field
) == FIELD_DECL
&& ! DECL_NONADDRESSABLE_P (field
))
712 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
716 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
724 /* Allocate an alias set for use in storing and reading from the varargs
727 static GTY(()) HOST_WIDE_INT varargs_set
= -1;
730 get_varargs_alias_set (void)
732 if (varargs_set
== -1)
733 varargs_set
= new_alias_set ();
738 /* Likewise, but used for the fixed portions of the frame, e.g., register
741 static GTY(()) HOST_WIDE_INT frame_set
= -1;
744 get_frame_alias_set (void)
747 frame_set
= new_alias_set ();
752 /* Inside SRC, the source of a SET, find a base address. */
755 find_base_value (rtx src
)
759 switch (GET_CODE (src
))
767 /* At the start of a function, argument registers have known base
768 values which may be lost later. Returning an ADDRESS
769 expression here allows optimization based on argument values
770 even when the argument registers are used for other purposes. */
771 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
772 return new_reg_base_value
[regno
];
774 /* If a pseudo has a known base value, return it. Do not do this
775 for non-fixed hard regs since it can result in a circular
776 dependency chain for registers which have values at function entry.
778 The test above is not sufficient because the scheduler may move
779 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
780 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
781 && regno
< reg_base_value_size
)
783 /* If we're inside init_alias_analysis, use new_reg_base_value
784 to reduce the number of relaxation iterations. */
785 if (new_reg_base_value
&& new_reg_base_value
[regno
]
786 && REG_N_SETS (regno
) == 1)
787 return new_reg_base_value
[regno
];
789 if (reg_base_value
[regno
])
790 return reg_base_value
[regno
];
796 /* Check for an argument passed in memory. Only record in the
797 copying-arguments block; it is too hard to track changes
799 if (copying_arguments
800 && (XEXP (src
, 0) == arg_pointer_rtx
801 || (GET_CODE (XEXP (src
, 0)) == PLUS
802 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
803 return gen_rtx_ADDRESS (VOIDmode
, src
);
808 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
811 /* ... fall through ... */
816 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
818 /* If either operand is a REG that is a known pointer, then it
820 if (REG_P (src_0
) && REG_POINTER (src_0
))
821 return find_base_value (src_0
);
822 if (REG_P (src_1
) && REG_POINTER (src_1
))
823 return find_base_value (src_1
);
825 /* If either operand is a REG, then see if we already have
826 a known value for it. */
829 temp
= find_base_value (src_0
);
836 temp
= find_base_value (src_1
);
841 /* If either base is named object or a special address
842 (like an argument or stack reference), then use it for the
845 && (GET_CODE (src_0
) == SYMBOL_REF
846 || GET_CODE (src_0
) == LABEL_REF
847 || (GET_CODE (src_0
) == ADDRESS
848 && GET_MODE (src_0
) != VOIDmode
)))
852 && (GET_CODE (src_1
) == SYMBOL_REF
853 || GET_CODE (src_1
) == LABEL_REF
854 || (GET_CODE (src_1
) == ADDRESS
855 && GET_MODE (src_1
) != VOIDmode
)))
858 /* Guess which operand is the base address:
859 If either operand is a symbol, then it is the base. If
860 either operand is a CONST_INT, then the other is the base. */
861 if (GET_CODE (src_1
) == CONST_INT
|| CONSTANT_P (src_0
))
862 return find_base_value (src_0
);
863 else if (GET_CODE (src_0
) == CONST_INT
|| CONSTANT_P (src_1
))
864 return find_base_value (src_1
);
870 /* The standard form is (lo_sum reg sym) so look only at the
872 return find_base_value (XEXP (src
, 1));
875 /* If the second operand is constant set the base
876 address to the first operand. */
877 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
878 return find_base_value (XEXP (src
, 0));
882 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
892 return find_base_value (XEXP (src
, 0));
895 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
897 rtx temp
= find_base_value (XEXP (src
, 0));
899 if (temp
!= 0 && CONSTANT_P (temp
))
900 temp
= convert_memory_address (Pmode
, temp
);
912 /* Called from init_alias_analysis indirectly through note_stores. */
914 /* While scanning insns to find base values, reg_seen[N] is nonzero if
915 register N has been set in this function. */
916 static char *reg_seen
;
918 /* Addresses which are known not to alias anything else are identified
919 by a unique integer. */
920 static int unique_id
;
923 record_set (rtx dest
, rtx set
, void *data ATTRIBUTE_UNUSED
)
929 if (GET_CODE (dest
) != REG
)
932 regno
= REGNO (dest
);
934 if (regno
>= reg_base_value_size
)
937 /* If this spans multiple hard registers, then we must indicate that every
938 register has an unusable value. */
939 if (regno
< FIRST_PSEUDO_REGISTER
)
940 n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
947 reg_seen
[regno
+ n
] = 1;
948 new_reg_base_value
[regno
+ n
] = 0;
955 /* A CLOBBER wipes out any old value but does not prevent a previously
956 unset register from acquiring a base address (i.e. reg_seen is not
958 if (GET_CODE (set
) == CLOBBER
)
960 new_reg_base_value
[regno
] = 0;
969 new_reg_base_value
[regno
] = 0;
973 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
974 GEN_INT (unique_id
++));
978 /* This is not the first set. If the new value is not related to the
979 old value, forget the base value. Note that the following code is
981 extern int x, y; int *p = &x; p += (&y-&x);
982 ANSI C does not allow computing the difference of addresses
983 of distinct top level objects. */
984 if (new_reg_base_value
[regno
])
985 switch (GET_CODE (src
))
989 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
990 new_reg_base_value
[regno
] = 0;
993 /* If the value we add in the PLUS is also a valid base value,
994 this might be the actual base value, and the original value
997 rtx other
= NULL_RTX
;
999 if (XEXP (src
, 0) == dest
)
1000 other
= XEXP (src
, 1);
1001 else if (XEXP (src
, 1) == dest
)
1002 other
= XEXP (src
, 0);
1004 if (! other
|| find_base_value (other
))
1005 new_reg_base_value
[regno
] = 0;
1009 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
1010 new_reg_base_value
[regno
] = 0;
1013 new_reg_base_value
[regno
] = 0;
1016 /* If this is the first set of a register, record the value. */
1017 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1018 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
1019 new_reg_base_value
[regno
] = find_base_value (src
);
1021 reg_seen
[regno
] = 1;
1024 /* Called from loop optimization when a new pseudo-register is
1025 created. It indicates that REGNO is being set to VAL. f INVARIANT
1026 is true then this value also describes an invariant relationship
1027 which can be used to deduce that two registers with unknown values
1031 record_base_value (unsigned int regno
, rtx val
, int invariant
)
1033 if (regno
>= reg_base_value_size
)
1036 if (invariant
&& alias_invariant
)
1037 alias_invariant
[regno
] = val
;
1039 if (GET_CODE (val
) == REG
)
1041 if (REGNO (val
) < reg_base_value_size
)
1042 reg_base_value
[regno
] = reg_base_value
[REGNO (val
)];
1047 reg_base_value
[regno
] = find_base_value (val
);
1050 /* Clear alias info for a register. This is used if an RTL transformation
1051 changes the value of a register. This is used in flow by AUTO_INC_DEC
1052 optimizations. We don't need to clear reg_base_value, since flow only
1053 changes the offset. */
1056 clear_reg_alias_info (rtx reg
)
1058 unsigned int regno
= REGNO (reg
);
1060 if (regno
< reg_known_value_size
&& regno
>= FIRST_PSEUDO_REGISTER
)
1061 reg_known_value
[regno
] = reg
;
1064 /* Returns a canonical version of X, from the point of view alias
1065 analysis. (For example, if X is a MEM whose address is a register,
1066 and the register has a known value (say a SYMBOL_REF), then a MEM
1067 whose address is the SYMBOL_REF is returned.) */
1072 /* Recursively look for equivalences. */
1073 if (GET_CODE (x
) == REG
&& REGNO (x
) >= FIRST_PSEUDO_REGISTER
1074 && REGNO (x
) < reg_known_value_size
)
1075 return reg_known_value
[REGNO (x
)] == x
1076 ? x
: canon_rtx (reg_known_value
[REGNO (x
)]);
1077 else if (GET_CODE (x
) == PLUS
)
1079 rtx x0
= canon_rtx (XEXP (x
, 0));
1080 rtx x1
= canon_rtx (XEXP (x
, 1));
1082 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1084 if (GET_CODE (x0
) == CONST_INT
)
1085 return plus_constant (x1
, INTVAL (x0
));
1086 else if (GET_CODE (x1
) == CONST_INT
)
1087 return plus_constant (x0
, INTVAL (x1
));
1088 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1092 /* This gives us much better alias analysis when called from
1093 the loop optimizer. Note we want to leave the original
1094 MEM alone, but need to return the canonicalized MEM with
1095 all the flags with their original values. */
1096 else if (GET_CODE (x
) == MEM
)
1097 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1102 /* Return 1 if X and Y are identical-looking rtx's.
1103 Expect that X and Y has been already canonicalized.
1105 We use the data in reg_known_value above to see if two registers with
1106 different numbers are, in fact, equivalent. */
1109 rtx_equal_for_memref_p (rtx x
, rtx y
)
1116 if (x
== 0 && y
== 0)
1118 if (x
== 0 || y
== 0)
1124 code
= GET_CODE (x
);
1125 /* Rtx's of different codes cannot be equal. */
1126 if (code
!= GET_CODE (y
))
1129 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1130 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1132 if (GET_MODE (x
) != GET_MODE (y
))
1135 /* Some RTL can be compared without a recursive examination. */
1139 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
1142 return REGNO (x
) == REGNO (y
);
1145 return XEXP (x
, 0) == XEXP (y
, 0);
1148 return XSTR (x
, 0) == XSTR (y
, 0);
1152 /* There's no need to compare the contents of CONST_DOUBLEs or
1153 CONST_INTs because pointer equality is a good enough
1154 comparison for these nodes. */
1158 return (XINT (x
, 1) == XINT (y
, 1)
1159 && rtx_equal_for_memref_p (XEXP (x
, 0),
1166 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1168 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1169 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1170 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1171 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1172 /* For commutative operations, the RTX match if the operand match in any
1173 order. Also handle the simple binary and unary cases without a loop. */
1174 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
1176 rtx xop0
= canon_rtx (XEXP (x
, 0));
1177 rtx yop0
= canon_rtx (XEXP (y
, 0));
1178 rtx yop1
= canon_rtx (XEXP (y
, 1));
1180 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1181 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1182 || (rtx_equal_for_memref_p (xop0
, yop1
)
1183 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1185 else if (GET_RTX_CLASS (code
) == '<' || GET_RTX_CLASS (code
) == '2')
1187 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1188 canon_rtx (XEXP (y
, 0)))
1189 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1190 canon_rtx (XEXP (y
, 1))));
1192 else if (GET_RTX_CLASS (code
) == '1')
1193 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1194 canon_rtx (XEXP (y
, 0)));
1196 /* Compare the elements. If any pair of corresponding elements
1197 fail to match, return 0 for the whole things.
1199 Limit cases to types which actually appear in addresses. */
1201 fmt
= GET_RTX_FORMAT (code
);
1202 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1207 if (XINT (x
, i
) != XINT (y
, i
))
1212 /* Two vectors must have the same length. */
1213 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1216 /* And the corresponding elements must match. */
1217 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1218 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1219 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1224 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1225 canon_rtx (XEXP (y
, i
))) == 0)
1229 /* This can happen for asm operands. */
1231 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1235 /* This can happen for an asm which clobbers memory. */
1239 /* It is believed that rtx's at this level will never
1240 contain anything but integers and other rtx's,
1241 except for within LABEL_REFs and SYMBOL_REFs. */
1249 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1250 X and return it, or return 0 if none found. */
1253 find_symbolic_term (rtx x
)
1259 code
= GET_CODE (x
);
1260 if (code
== SYMBOL_REF
|| code
== LABEL_REF
)
1262 if (GET_RTX_CLASS (code
) == 'o')
1265 fmt
= GET_RTX_FORMAT (code
);
1266 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1272 t
= find_symbolic_term (XEXP (x
, i
));
1276 else if (fmt
[i
] == 'E')
1283 find_base_term (rtx x
)
1286 struct elt_loc_list
*l
;
1288 #if defined (FIND_BASE_TERM)
1289 /* Try machine-dependent ways to find the base term. */
1290 x
= FIND_BASE_TERM (x
);
1293 switch (GET_CODE (x
))
1296 return REG_BASE_VALUE (x
);
1299 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1309 return find_base_term (XEXP (x
, 0));
1312 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1314 rtx temp
= find_base_term (XEXP (x
, 0));
1316 if (temp
!= 0 && CONSTANT_P (temp
))
1317 temp
= convert_memory_address (Pmode
, temp
);
1323 val
= CSELIB_VAL_PTR (x
);
1324 for (l
= val
->locs
; l
; l
= l
->next
)
1325 if ((x
= find_base_term (l
->loc
)) != 0)
1331 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1338 rtx tmp1
= XEXP (x
, 0);
1339 rtx tmp2
= XEXP (x
, 1);
1341 /* This is a little bit tricky since we have to determine which of
1342 the two operands represents the real base address. Otherwise this
1343 routine may return the index register instead of the base register.
1345 That may cause us to believe no aliasing was possible, when in
1346 fact aliasing is possible.
1348 We use a few simple tests to guess the base register. Additional
1349 tests can certainly be added. For example, if one of the operands
1350 is a shift or multiply, then it must be the index register and the
1351 other operand is the base register. */
1353 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1354 return find_base_term (tmp2
);
1356 /* If either operand is known to be a pointer, then use it
1357 to determine the base term. */
1358 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1359 return find_base_term (tmp1
);
1361 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1362 return find_base_term (tmp2
);
1364 /* Neither operand was known to be a pointer. Go ahead and find the
1365 base term for both operands. */
1366 tmp1
= find_base_term (tmp1
);
1367 tmp2
= find_base_term (tmp2
);
1369 /* If either base term is named object or a special address
1370 (like an argument or stack reference), then use it for the
1373 && (GET_CODE (tmp1
) == SYMBOL_REF
1374 || GET_CODE (tmp1
) == LABEL_REF
1375 || (GET_CODE (tmp1
) == ADDRESS
1376 && GET_MODE (tmp1
) != VOIDmode
)))
1380 && (GET_CODE (tmp2
) == SYMBOL_REF
1381 || GET_CODE (tmp2
) == LABEL_REF
1382 || (GET_CODE (tmp2
) == ADDRESS
1383 && GET_MODE (tmp2
) != VOIDmode
)))
1386 /* We could not determine which of the two operands was the
1387 base register and which was the index. So we can determine
1388 nothing from the base alias check. */
1393 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
&& INTVAL (XEXP (x
, 1)) != 0)
1394 return find_base_term (XEXP (x
, 0));
1402 return REG_BASE_VALUE (frame_pointer_rtx
);
1409 /* Return 0 if the addresses X and Y are known to point to different
1410 objects, 1 if they might be pointers to the same object. */
1413 base_alias_check (rtx x
, rtx y
, enum machine_mode x_mode
,
1414 enum machine_mode y_mode
)
1416 rtx x_base
= find_base_term (x
);
1417 rtx y_base
= find_base_term (y
);
1419 /* If the address itself has no known base see if a known equivalent
1420 value has one. If either address still has no known base, nothing
1421 is known about aliasing. */
1426 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1429 x_base
= find_base_term (x_c
);
1437 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1440 y_base
= find_base_term (y_c
);
1445 /* If the base addresses are equal nothing is known about aliasing. */
1446 if (rtx_equal_p (x_base
, y_base
))
1449 /* The base addresses of the read and write are different expressions.
1450 If they are both symbols and they are not accessed via AND, there is
1451 no conflict. We can bring knowledge of object alignment into play
1452 here. For example, on alpha, "char a, b;" can alias one another,
1453 though "char a; long b;" cannot. */
1454 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1456 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1458 if (GET_CODE (x
) == AND
1459 && (GET_CODE (XEXP (x
, 1)) != CONST_INT
1460 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1462 if (GET_CODE (y
) == AND
1463 && (GET_CODE (XEXP (y
, 1)) != CONST_INT
1464 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1466 /* Differing symbols never alias. */
1470 /* If one address is a stack reference there can be no alias:
1471 stack references using different base registers do not alias,
1472 a stack reference can not alias a parameter, and a stack reference
1473 can not alias a global. */
1474 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
1475 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
1478 if (! flag_argument_noalias
)
1481 if (flag_argument_noalias
> 1)
1484 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1485 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
1488 /* Convert the address X into something we can use. This is done by returning
1489 it unchanged unless it is a value; in the latter case we call cselib to get
1490 a more useful rtx. */
1496 struct elt_loc_list
*l
;
1498 if (GET_CODE (x
) != VALUE
)
1500 v
= CSELIB_VAL_PTR (x
);
1501 for (l
= v
->locs
; l
; l
= l
->next
)
1502 if (CONSTANT_P (l
->loc
))
1504 for (l
= v
->locs
; l
; l
= l
->next
)
1505 if (GET_CODE (l
->loc
) != REG
&& GET_CODE (l
->loc
) != MEM
)
1508 return v
->locs
->loc
;
1512 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1513 where SIZE is the size in bytes of the memory reference. If ADDR
1514 is not modified by the memory reference then ADDR is returned. */
1517 addr_side_effect_eval (rtx addr
, int size
, int n_refs
)
1521 switch (GET_CODE (addr
))
1524 offset
= (n_refs
+ 1) * size
;
1527 offset
= -(n_refs
+ 1) * size
;
1530 offset
= n_refs
* size
;
1533 offset
= -n_refs
* size
;
1541 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0),
1544 addr
= XEXP (addr
, 0);
1545 addr
= canon_rtx (addr
);
1550 /* Return nonzero if X and Y (memory addresses) could reference the
1551 same location in memory. C is an offset accumulator. When
1552 C is nonzero, we are testing aliases between X and Y + C.
1553 XSIZE is the size in bytes of the X reference,
1554 similarly YSIZE is the size in bytes for Y.
1555 Expect that canon_rtx has been already called for X and Y.
1557 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1558 referenced (the reference was BLKmode), so make the most pessimistic
1561 If XSIZE or YSIZE is negative, we may access memory outside the object
1562 being referenced as a side effect. This can happen when using AND to
1563 align memory references, as is done on the Alpha.
1565 Nice to notice that varying addresses cannot conflict with fp if no
1566 local variables had their addresses taken, but that's too hard now. */
1569 memrefs_conflict_p (int xsize
, rtx x
, int ysize
, rtx y
, HOST_WIDE_INT c
)
1571 if (GET_CODE (x
) == VALUE
)
1573 if (GET_CODE (y
) == VALUE
)
1575 if (GET_CODE (x
) == HIGH
)
1577 else if (GET_CODE (x
) == LO_SUM
)
1580 x
= addr_side_effect_eval (x
, xsize
, 0);
1581 if (GET_CODE (y
) == HIGH
)
1583 else if (GET_CODE (y
) == LO_SUM
)
1586 y
= addr_side_effect_eval (y
, ysize
, 0);
1588 if (rtx_equal_for_memref_p (x
, y
))
1590 if (xsize
<= 0 || ysize
<= 0)
1592 if (c
>= 0 && xsize
> c
)
1594 if (c
< 0 && ysize
+c
> 0)
1599 /* This code used to check for conflicts involving stack references and
1600 globals but the base address alias code now handles these cases. */
1602 if (GET_CODE (x
) == PLUS
)
1604 /* The fact that X is canonicalized means that this
1605 PLUS rtx is canonicalized. */
1606 rtx x0
= XEXP (x
, 0);
1607 rtx x1
= XEXP (x
, 1);
1609 if (GET_CODE (y
) == PLUS
)
1611 /* The fact that Y is canonicalized means that this
1612 PLUS rtx is canonicalized. */
1613 rtx y0
= XEXP (y
, 0);
1614 rtx y1
= XEXP (y
, 1);
1616 if (rtx_equal_for_memref_p (x1
, y1
))
1617 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1618 if (rtx_equal_for_memref_p (x0
, y0
))
1619 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
1620 if (GET_CODE (x1
) == CONST_INT
)
1622 if (GET_CODE (y1
) == CONST_INT
)
1623 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
1624 c
- INTVAL (x1
) + INTVAL (y1
));
1626 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
1629 else if (GET_CODE (y1
) == CONST_INT
)
1630 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1634 else if (GET_CODE (x1
) == CONST_INT
)
1635 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
1637 else if (GET_CODE (y
) == PLUS
)
1639 /* The fact that Y is canonicalized means that this
1640 PLUS rtx is canonicalized. */
1641 rtx y0
= XEXP (y
, 0);
1642 rtx y1
= XEXP (y
, 1);
1644 if (GET_CODE (y1
) == CONST_INT
)
1645 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1650 if (GET_CODE (x
) == GET_CODE (y
))
1651 switch (GET_CODE (x
))
1655 /* Handle cases where we expect the second operands to be the
1656 same, and check only whether the first operand would conflict
1659 rtx x1
= canon_rtx (XEXP (x
, 1));
1660 rtx y1
= canon_rtx (XEXP (y
, 1));
1661 if (! rtx_equal_for_memref_p (x1
, y1
))
1663 x0
= canon_rtx (XEXP (x
, 0));
1664 y0
= canon_rtx (XEXP (y
, 0));
1665 if (rtx_equal_for_memref_p (x0
, y0
))
1666 return (xsize
== 0 || ysize
== 0
1667 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1669 /* Can't properly adjust our sizes. */
1670 if (GET_CODE (x1
) != CONST_INT
)
1672 xsize
/= INTVAL (x1
);
1673 ysize
/= INTVAL (x1
);
1675 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1679 /* Are these registers known not to be equal? */
1680 if (alias_invariant
)
1682 unsigned int r_x
= REGNO (x
), r_y
= REGNO (y
);
1683 rtx i_x
, i_y
; /* invariant relationships of X and Y */
1685 i_x
= r_x
>= reg_base_value_size
? 0 : alias_invariant
[r_x
];
1686 i_y
= r_y
>= reg_base_value_size
? 0 : alias_invariant
[r_y
];
1688 if (i_x
== 0 && i_y
== 0)
1691 if (! memrefs_conflict_p (xsize
, i_x
? i_x
: x
,
1692 ysize
, i_y
? i_y
: y
, c
))
1701 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1702 as an access with indeterminate size. Assume that references
1703 besides AND are aligned, so if the size of the other reference is
1704 at least as large as the alignment, assume no other overlap. */
1705 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1707 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1709 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)), ysize
, y
, c
);
1711 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1713 /* ??? If we are indexing far enough into the array/structure, we
1714 may yet be able to determine that we can not overlap. But we
1715 also need to that we are far enough from the end not to overlap
1716 a following reference, so we do nothing with that for now. */
1717 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1719 return memrefs_conflict_p (xsize
, x
, ysize
, canon_rtx (XEXP (y
, 0)), c
);
1722 if (GET_CODE (x
) == ADDRESSOF
)
1724 if (y
== frame_pointer_rtx
1725 || GET_CODE (y
) == ADDRESSOF
)
1726 return xsize
<= 0 || ysize
<= 0;
1728 if (GET_CODE (y
) == ADDRESSOF
)
1730 if (x
== frame_pointer_rtx
)
1731 return xsize
<= 0 || ysize
<= 0;
1736 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1738 c
+= (INTVAL (y
) - INTVAL (x
));
1739 return (xsize
<= 0 || ysize
<= 0
1740 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1743 if (GET_CODE (x
) == CONST
)
1745 if (GET_CODE (y
) == CONST
)
1746 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1747 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1749 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1752 if (GET_CODE (y
) == CONST
)
1753 return memrefs_conflict_p (xsize
, x
, ysize
,
1754 canon_rtx (XEXP (y
, 0)), c
);
1757 return (xsize
<= 0 || ysize
<= 0
1758 || (rtx_equal_for_memref_p (x
, y
)
1759 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1766 /* Functions to compute memory dependencies.
1768 Since we process the insns in execution order, we can build tables
1769 to keep track of what registers are fixed (and not aliased), what registers
1770 are varying in known ways, and what registers are varying in unknown
1773 If both memory references are volatile, then there must always be a
1774 dependence between the two references, since their order can not be
1775 changed. A volatile and non-volatile reference can be interchanged
1778 A MEM_IN_STRUCT reference at a non-AND varying address can never
1779 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1780 also must allow AND addresses, because they may generate accesses
1781 outside the object being referenced. This is used to generate
1782 aligned addresses from unaligned addresses, for instance, the alpha
1783 storeqi_unaligned pattern. */
1785 /* Read dependence: X is read after read in MEM takes place. There can
1786 only be a dependence here if both reads are volatile. */
1789 read_dependence (rtx mem
, rtx x
)
1791 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1794 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1795 MEM2 is a reference to a structure at a varying address, or returns
1796 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1797 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1798 to decide whether or not an address may vary; it should return
1799 nonzero whenever variation is possible.
1800 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1803 fixed_scalar_and_varying_struct_p (rtx mem1
, rtx mem2
, rtx mem1_addr
,
1805 int (*varies_p
) (rtx
, int))
1807 if (! flag_strict_aliasing
)
1810 if (MEM_SCALAR_P (mem1
) && MEM_IN_STRUCT_P (mem2
)
1811 && !varies_p (mem1_addr
, 1) && varies_p (mem2_addr
, 1))
1812 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1816 if (MEM_IN_STRUCT_P (mem1
) && MEM_SCALAR_P (mem2
)
1817 && varies_p (mem1_addr
, 1) && !varies_p (mem2_addr
, 1))
1818 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1825 /* Returns nonzero if something about the mode or address format MEM1
1826 indicates that it might well alias *anything*. */
1829 aliases_everything_p (rtx mem
)
1831 if (GET_CODE (XEXP (mem
, 0)) == AND
)
1832 /* If the address is an AND, its very hard to know at what it is
1833 actually pointing. */
1839 /* Return true if we can determine that the fields referenced cannot
1840 overlap for any pair of objects. */
1843 nonoverlapping_component_refs_p (tree x
, tree y
)
1845 tree fieldx
, fieldy
, typex
, typey
, orig_y
;
1849 /* The comparison has to be done at a common type, since we don't
1850 know how the inheritance hierarchy works. */
1854 fieldx
= TREE_OPERAND (x
, 1);
1855 typex
= DECL_FIELD_CONTEXT (fieldx
);
1860 fieldy
= TREE_OPERAND (y
, 1);
1861 typey
= DECL_FIELD_CONTEXT (fieldy
);
1866 y
= TREE_OPERAND (y
, 0);
1868 while (y
&& TREE_CODE (y
) == COMPONENT_REF
);
1870 x
= TREE_OPERAND (x
, 0);
1872 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1874 /* Never found a common type. */
1878 /* If we're left with accessing different fields of a structure,
1880 if (TREE_CODE (typex
) == RECORD_TYPE
1881 && fieldx
!= fieldy
)
1884 /* The comparison on the current field failed. If we're accessing
1885 a very nested structure, look at the next outer level. */
1886 x
= TREE_OPERAND (x
, 0);
1887 y
= TREE_OPERAND (y
, 0);
1890 && TREE_CODE (x
) == COMPONENT_REF
1891 && TREE_CODE (y
) == COMPONENT_REF
);
1896 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1899 decl_for_component_ref (tree x
)
1903 x
= TREE_OPERAND (x
, 0);
1905 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1907 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
1910 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1911 offset of the field reference. */
1914 adjust_offset_for_component_ref (tree x
, rtx offset
)
1916 HOST_WIDE_INT ioffset
;
1921 ioffset
= INTVAL (offset
);
1924 tree field
= TREE_OPERAND (x
, 1);
1926 if (! host_integerp (DECL_FIELD_OFFSET (field
), 1))
1928 ioffset
+= (tree_low_cst (DECL_FIELD_OFFSET (field
), 1)
1929 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 1)
1932 x
= TREE_OPERAND (x
, 0);
1934 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1936 return GEN_INT (ioffset
);
1939 /* Return nonzero if we can determine the exprs corresponding to memrefs
1940 X and Y and they do not overlap. */
1943 nonoverlapping_memrefs_p (rtx x
, rtx y
)
1945 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
1948 rtx moffsetx
, moffsety
;
1949 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
1951 /* Unless both have exprs, we can't tell anything. */
1952 if (exprx
== 0 || expry
== 0)
1955 /* If both are field references, we may be able to determine something. */
1956 if (TREE_CODE (exprx
) == COMPONENT_REF
1957 && TREE_CODE (expry
) == COMPONENT_REF
1958 && nonoverlapping_component_refs_p (exprx
, expry
))
1961 /* If the field reference test failed, look at the DECLs involved. */
1962 moffsetx
= MEM_OFFSET (x
);
1963 if (TREE_CODE (exprx
) == COMPONENT_REF
)
1965 tree t
= decl_for_component_ref (exprx
);
1968 moffsetx
= adjust_offset_for_component_ref (exprx
, moffsetx
);
1971 else if (TREE_CODE (exprx
) == INDIRECT_REF
)
1973 exprx
= TREE_OPERAND (exprx
, 0);
1974 if (flag_argument_noalias
< 2
1975 || TREE_CODE (exprx
) != PARM_DECL
)
1979 moffsety
= MEM_OFFSET (y
);
1980 if (TREE_CODE (expry
) == COMPONENT_REF
)
1982 tree t
= decl_for_component_ref (expry
);
1985 moffsety
= adjust_offset_for_component_ref (expry
, moffsety
);
1988 else if (TREE_CODE (expry
) == INDIRECT_REF
)
1990 expry
= TREE_OPERAND (expry
, 0);
1991 if (flag_argument_noalias
< 2
1992 || TREE_CODE (expry
) != PARM_DECL
)
1996 if (! DECL_P (exprx
) || ! DECL_P (expry
))
1999 rtlx
= DECL_RTL (exprx
);
2000 rtly
= DECL_RTL (expry
);
2002 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2003 can't overlap unless they are the same because we never reuse that part
2004 of the stack frame used for locals for spilled pseudos. */
2005 if ((GET_CODE (rtlx
) != MEM
|| GET_CODE (rtly
) != MEM
)
2006 && ! rtx_equal_p (rtlx
, rtly
))
2009 /* Get the base and offsets of both decls. If either is a register, we
2010 know both are and are the same, so use that as the base. The only
2011 we can avoid overlap is if we can deduce that they are nonoverlapping
2012 pieces of that decl, which is very rare. */
2013 basex
= GET_CODE (rtlx
) == MEM
? XEXP (rtlx
, 0) : rtlx
;
2014 if (GET_CODE (basex
) == PLUS
&& GET_CODE (XEXP (basex
, 1)) == CONST_INT
)
2015 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2017 basey
= GET_CODE (rtly
) == MEM
? XEXP (rtly
, 0) : rtly
;
2018 if (GET_CODE (basey
) == PLUS
&& GET_CODE (XEXP (basey
, 1)) == CONST_INT
)
2019 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2021 /* If the bases are different, we know they do not overlap if both
2022 are constants or if one is a constant and the other a pointer into the
2023 stack frame. Otherwise a different base means we can't tell if they
2025 if (! rtx_equal_p (basex
, basey
))
2026 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2027 || (CONSTANT_P (basex
) && REG_P (basey
)
2028 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2029 || (CONSTANT_P (basey
) && REG_P (basex
)
2030 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2032 sizex
= (GET_CODE (rtlx
) != MEM
? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2033 : MEM_SIZE (rtlx
) ? INTVAL (MEM_SIZE (rtlx
))
2035 sizey
= (GET_CODE (rtly
) != MEM
? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2036 : MEM_SIZE (rtly
) ? INTVAL (MEM_SIZE (rtly
)) :
2039 /* If we have an offset for either memref, it can update the values computed
2042 offsetx
+= INTVAL (moffsetx
), sizex
-= INTVAL (moffsetx
);
2044 offsety
+= INTVAL (moffsety
), sizey
-= INTVAL (moffsety
);
2046 /* If a memref has both a size and an offset, we can use the smaller size.
2047 We can't do this if the offset isn't known because we must view this
2048 memref as being anywhere inside the DECL's MEM. */
2049 if (MEM_SIZE (x
) && moffsetx
)
2050 sizex
= INTVAL (MEM_SIZE (x
));
2051 if (MEM_SIZE (y
) && moffsety
)
2052 sizey
= INTVAL (MEM_SIZE (y
));
2054 /* Put the values of the memref with the lower offset in X's values. */
2055 if (offsetx
> offsety
)
2057 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2058 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2061 /* If we don't know the size of the lower-offset value, we can't tell
2062 if they conflict. Otherwise, we do the test. */
2063 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2066 /* True dependence: X is read after store in MEM takes place. */
2069 true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx x
,
2070 int (*varies
) (rtx
, int))
2072 rtx x_addr
, mem_addr
;
2075 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2078 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2079 This is used in epilogue deallocation functions. */
2080 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2082 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2085 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2088 /* Unchanging memory can't conflict with non-unchanging memory.
2089 A non-unchanging read can conflict with a non-unchanging write.
2090 An unchanging read can conflict with an unchanging write since
2091 there may be a single store to this address to initialize it.
2092 Note that an unchanging store can conflict with a non-unchanging read
2093 since we have to make conservative assumptions when we have a
2094 record with readonly fields and we are copying the whole thing.
2095 Just fall through to the code below to resolve potential conflicts.
2096 This won't handle all cases optimally, but the possible performance
2097 loss should be negligible. */
2098 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
2101 if (nonoverlapping_memrefs_p (mem
, x
))
2104 if (mem_mode
== VOIDmode
)
2105 mem_mode
= GET_MODE (mem
);
2107 x_addr
= get_addr (XEXP (x
, 0));
2108 mem_addr
= get_addr (XEXP (mem
, 0));
2110 base
= find_base_term (x_addr
);
2111 if (base
&& (GET_CODE (base
) == LABEL_REF
2112 || (GET_CODE (base
) == SYMBOL_REF
2113 && CONSTANT_POOL_ADDRESS_P (base
))))
2116 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2119 x_addr
= canon_rtx (x_addr
);
2120 mem_addr
= canon_rtx (mem_addr
);
2122 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2123 SIZE_FOR_MODE (x
), x_addr
, 0))
2126 if (aliases_everything_p (x
))
2129 /* We cannot use aliases_everything_p to test MEM, since we must look
2130 at MEM_MODE, rather than GET_MODE (MEM). */
2131 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2134 /* In true_dependence we also allow BLKmode to alias anything. Why
2135 don't we do this in anti_dependence and output_dependence? */
2136 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2139 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2143 /* Canonical true dependence: X is read after store in MEM takes place.
2144 Variant of true_dependence which assumes MEM has already been
2145 canonicalized (hence we no longer do that here).
2146 The mem_addr argument has been added, since true_dependence computed
2147 this value prior to canonicalizing. */
2150 canon_true_dependence (rtx mem
, enum machine_mode mem_mode
, rtx mem_addr
,
2151 rtx x
, int (*varies
) (rtx
, int))
2155 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2158 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2159 This is used in epilogue deallocation functions. */
2160 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2162 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2165 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2168 /* If X is an unchanging read, then it can't possibly conflict with any
2169 non-unchanging store. It may conflict with an unchanging write though,
2170 because there may be a single store to this address to initialize it.
2171 Just fall through to the code below to resolve the case where we have
2172 both an unchanging read and an unchanging write. This won't handle all
2173 cases optimally, but the possible performance loss should be
2175 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
2178 if (nonoverlapping_memrefs_p (x
, mem
))
2181 x_addr
= get_addr (XEXP (x
, 0));
2183 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2186 x_addr
= canon_rtx (x_addr
);
2187 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2188 SIZE_FOR_MODE (x
), x_addr
, 0))
2191 if (aliases_everything_p (x
))
2194 /* We cannot use aliases_everything_p to test MEM, since we must look
2195 at MEM_MODE, rather than GET_MODE (MEM). */
2196 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2199 /* In true_dependence we also allow BLKmode to alias anything. Why
2200 don't we do this in anti_dependence and output_dependence? */
2201 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2204 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2208 /* Returns nonzero if a write to X might alias a previous read from
2209 (or, if WRITEP is nonzero, a write to) MEM. If CONSTP is nonzero,
2210 honor the RTX_UNCHANGING_P flags on X and MEM. */
2213 write_dependence_p (rtx mem
, rtx x
, int writep
, int constp
)
2215 rtx x_addr
, mem_addr
;
2219 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2222 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2223 This is used in epilogue deallocation functions. */
2224 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2226 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2229 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2234 /* Unchanging memory can't conflict with non-unchanging memory. */
2235 if (RTX_UNCHANGING_P (x
) != RTX_UNCHANGING_P (mem
))
2238 /* If MEM is an unchanging read, then it can't possibly conflict with
2239 the store to X, because there is at most one store to MEM, and it
2240 must have occurred somewhere before MEM. */
2241 if (! writep
&& RTX_UNCHANGING_P (mem
))
2245 if (nonoverlapping_memrefs_p (x
, mem
))
2248 x_addr
= get_addr (XEXP (x
, 0));
2249 mem_addr
= get_addr (XEXP (mem
, 0));
2253 base
= find_base_term (mem_addr
);
2254 if (base
&& (GET_CODE (base
) == LABEL_REF
2255 || (GET_CODE (base
) == SYMBOL_REF
2256 && CONSTANT_POOL_ADDRESS_P (base
))))
2260 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
2264 x_addr
= canon_rtx (x_addr
);
2265 mem_addr
= canon_rtx (mem_addr
);
2267 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2268 SIZE_FOR_MODE (x
), x_addr
, 0))
2272 = fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2275 return (!(fixed_scalar
== mem
&& !aliases_everything_p (x
))
2276 && !(fixed_scalar
== x
&& !aliases_everything_p (mem
)));
2279 /* Anti dependence: X is written after read in MEM takes place. */
2282 anti_dependence (rtx mem
, rtx x
)
2284 return write_dependence_p (mem
, x
, /*writep=*/0, /*constp*/1);
2287 /* Output dependence: X is written after store in MEM takes place. */
2290 output_dependence (rtx mem
, rtx x
)
2292 return write_dependence_p (mem
, x
, /*writep=*/1, /*constp*/1);
2295 /* Unchanging anti dependence: Like anti_dependence but ignores
2296 the UNCHANGING_RTX_P property on const variable references. */
2299 unchanging_anti_dependence (rtx mem
, rtx x
)
2301 return write_dependence_p (mem
, x
, /*writep=*/0, /*constp*/0);
2304 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2305 something which is not local to the function and is not constant. */
2308 nonlocal_mentioned_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2317 switch (GET_CODE (x
))
2320 if (GET_CODE (SUBREG_REG (x
)) == REG
)
2322 /* Global registers are not local. */
2323 if (REGNO (SUBREG_REG (x
)) < FIRST_PSEUDO_REGISTER
2324 && global_regs
[subreg_regno (x
)])
2332 /* Global registers are not local. */
2333 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2348 /* Constants in the function's constants pool are constant. */
2349 if (CONSTANT_POOL_ADDRESS_P (x
))
2354 /* Non-constant calls and recursion are not local. */
2358 /* Be overly conservative and consider any volatile memory
2359 reference as not local. */
2360 if (MEM_VOLATILE_P (x
))
2362 base
= find_base_term (XEXP (x
, 0));
2365 /* A Pmode ADDRESS could be a reference via the structure value
2366 address or static chain. Such memory references are nonlocal.
2368 Thus, we have to examine the contents of the ADDRESS to find
2369 out if this is a local reference or not. */
2370 if (GET_CODE (base
) == ADDRESS
2371 && GET_MODE (base
) == Pmode
2372 && (XEXP (base
, 0) == stack_pointer_rtx
2373 || XEXP (base
, 0) == arg_pointer_rtx
2374 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2375 || XEXP (base
, 0) == hard_frame_pointer_rtx
2377 || XEXP (base
, 0) == frame_pointer_rtx
))
2379 /* Constants in the function's constant pool are constant. */
2380 if (GET_CODE (base
) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (base
))
2385 case UNSPEC_VOLATILE
:
2390 if (MEM_VOLATILE_P (x
))
2402 /* Returns nonzero if X might mention something which is not
2403 local to the function and is not constant. */
2406 nonlocal_mentioned_p (rtx x
)
2410 if (GET_CODE (x
) == CALL_INSN
)
2412 if (! CONST_OR_PURE_CALL_P (x
))
2414 x
= CALL_INSN_FUNCTION_USAGE (x
);
2422 return for_each_rtx (&x
, nonlocal_mentioned_p_1
, NULL
);
2425 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2426 something which is not local to the function and is not constant. */
2429 nonlocal_referenced_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2436 switch (GET_CODE (x
))
2442 return nonlocal_mentioned_p (x
);
2445 /* Non-constant calls and recursion are not local. */
2449 if (nonlocal_mentioned_p (SET_SRC (x
)))
2452 if (GET_CODE (SET_DEST (x
)) == MEM
)
2453 return nonlocal_mentioned_p (XEXP (SET_DEST (x
), 0));
2455 /* If the destination is anything other than a CC0, PC,
2456 MEM, REG, or a SUBREG of a REG that occupies all of
2457 the REG, then X references nonlocal memory if it is
2458 mentioned in the destination. */
2459 if (GET_CODE (SET_DEST (x
)) != CC0
2460 && GET_CODE (SET_DEST (x
)) != PC
2461 && GET_CODE (SET_DEST (x
)) != REG
2462 && ! (GET_CODE (SET_DEST (x
)) == SUBREG
2463 && GET_CODE (SUBREG_REG (SET_DEST (x
))) == REG
2464 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x
))))
2465 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
)
2466 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x
)))
2467 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
))))
2468 return nonlocal_mentioned_p (SET_DEST (x
));
2472 if (GET_CODE (XEXP (x
, 0)) == MEM
)
2473 return nonlocal_mentioned_p (XEXP (XEXP (x
, 0), 0));
2477 return nonlocal_mentioned_p (XEXP (x
, 0));
2480 case UNSPEC_VOLATILE
:
2484 if (MEM_VOLATILE_P (x
))
2496 /* Returns nonzero if X might reference something which is not
2497 local to the function and is not constant. */
2500 nonlocal_referenced_p (rtx x
)
2504 if (GET_CODE (x
) == CALL_INSN
)
2506 if (! CONST_OR_PURE_CALL_P (x
))
2508 x
= CALL_INSN_FUNCTION_USAGE (x
);
2516 return for_each_rtx (&x
, nonlocal_referenced_p_1
, NULL
);
2519 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2520 something which is not local to the function and is not constant. */
2523 nonlocal_set_p_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2530 switch (GET_CODE (x
))
2533 /* Non-constant calls and recursion are not local. */
2542 return nonlocal_mentioned_p (XEXP (x
, 0));
2545 if (nonlocal_mentioned_p (SET_DEST (x
)))
2547 return nonlocal_set_p (SET_SRC (x
));
2550 return nonlocal_mentioned_p (XEXP (x
, 0));
2556 case UNSPEC_VOLATILE
:
2560 if (MEM_VOLATILE_P (x
))
2572 /* Returns nonzero if X might set something which is not
2573 local to the function and is not constant. */
2576 nonlocal_set_p (rtx x
)
2580 if (GET_CODE (x
) == CALL_INSN
)
2582 if (! CONST_OR_PURE_CALL_P (x
))
2584 x
= CALL_INSN_FUNCTION_USAGE (x
);
2592 return for_each_rtx (&x
, nonlocal_set_p_1
, NULL
);
2595 /* Mark the function if it is pure or constant. */
2598 mark_constant_function (void)
2601 int nonlocal_memory_referenced
;
2603 if (TREE_READONLY (current_function_decl
)
2604 || DECL_IS_PURE (current_function_decl
)
2605 || TREE_THIS_VOLATILE (current_function_decl
)
2606 || current_function_has_nonlocal_goto
2607 || !(*targetm
.binds_local_p
) (current_function_decl
))
2610 /* A loop might not return which counts as a side effect. */
2611 if (mark_dfs_back_edges ())
2614 nonlocal_memory_referenced
= 0;
2616 init_alias_analysis ();
2618 /* Determine if this is a constant or pure function. */
2620 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2622 if (! INSN_P (insn
))
2625 if (nonlocal_set_p (insn
) || global_reg_mentioned_p (insn
)
2626 || volatile_refs_p (PATTERN (insn
)))
2629 if (! nonlocal_memory_referenced
)
2630 nonlocal_memory_referenced
= nonlocal_referenced_p (insn
);
2633 end_alias_analysis ();
2635 /* Mark the function. */
2639 else if (nonlocal_memory_referenced
)
2641 cgraph_rtl_info (current_function_decl
)->pure_function
= 1;
2642 DECL_IS_PURE (current_function_decl
) = 1;
2646 cgraph_rtl_info (current_function_decl
)->const_function
= 1;
2647 TREE_READONLY (current_function_decl
) = 1;
2653 init_alias_once (void)
2657 #ifndef OUTGOING_REGNO
2658 #define OUTGOING_REGNO(N) N
2660 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2661 /* Check whether this register can hold an incoming pointer
2662 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2663 numbers, so translate if necessary due to register windows. */
2664 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2665 && HARD_REGNO_MODE_OK (i
, Pmode
))
2666 static_reg_base_value
[i
]
2667 = gen_rtx_ADDRESS (VOIDmode
, gen_rtx_REG (Pmode
, i
));
2669 static_reg_base_value
[STACK_POINTER_REGNUM
]
2670 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
2671 static_reg_base_value
[ARG_POINTER_REGNUM
]
2672 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
2673 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2674 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
2675 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2676 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2677 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
2681 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2682 to be memory reference. */
2683 static bool memory_modified
;
2685 memory_modified_1 (rtx x
, rtx pat ATTRIBUTE_UNUSED
, void *data
)
2687 if (GET_CODE (x
) == MEM
)
2689 if (anti_dependence (x
, (rtx
)data
) || output_dependence (x
, (rtx
)data
))
2690 memory_modified
= true;
2695 /* Return true when INSN possibly modify memory contents of MEM
2696 (ie address can be modified). */
2698 memory_modified_in_insn_p (rtx mem
, rtx insn
)
2702 memory_modified
= false;
2703 note_stores (PATTERN (insn
), memory_modified_1
, mem
);
2704 return memory_modified
;
2707 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2711 init_alias_analysis (void)
2713 int maxreg
= max_reg_num ();
2719 timevar_push (TV_ALIAS_ANALYSIS
);
2721 reg_known_value_size
= maxreg
;
2724 = (rtx
*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (rtx
))
2725 - FIRST_PSEUDO_REGISTER
;
2727 = (char*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (char))
2728 - FIRST_PSEUDO_REGISTER
;
2730 /* Overallocate reg_base_value to allow some growth during loop
2731 optimization. Loop unrolling can create a large number of
2733 reg_base_value_size
= maxreg
* 2;
2734 reg_base_value
= ggc_alloc_cleared (reg_base_value_size
* sizeof (rtx
));
2736 new_reg_base_value
= xmalloc (reg_base_value_size
* sizeof (rtx
));
2737 reg_seen
= xmalloc (reg_base_value_size
);
2738 if (! reload_completed
&& flag_old_unroll_loops
)
2740 /* ??? Why are we realloc'ing if we're just going to zero it? */
2741 alias_invariant
= xrealloc (alias_invariant
,
2742 reg_base_value_size
* sizeof (rtx
));
2743 memset (alias_invariant
, 0, reg_base_value_size
* sizeof (rtx
));
2746 /* The basic idea is that each pass through this loop will use the
2747 "constant" information from the previous pass to propagate alias
2748 information through another level of assignments.
2750 This could get expensive if the assignment chains are long. Maybe
2751 we should throttle the number of iterations, possibly based on
2752 the optimization level or flag_expensive_optimizations.
2754 We could propagate more information in the first pass by making use
2755 of REG_N_SETS to determine immediately that the alias information
2756 for a pseudo is "constant".
2758 A program with an uninitialized variable can cause an infinite loop
2759 here. Instead of doing a full dataflow analysis to detect such problems
2760 we just cap the number of iterations for the loop.
2762 The state of the arrays for the set chain in question does not matter
2763 since the program has undefined behavior. */
2768 /* Assume nothing will change this iteration of the loop. */
2771 /* We want to assign the same IDs each iteration of this loop, so
2772 start counting from zero each iteration of the loop. */
2775 /* We're at the start of the function each iteration through the
2776 loop, so we're copying arguments. */
2777 copying_arguments
= true;
2779 /* Wipe the potential alias information clean for this pass. */
2780 memset (new_reg_base_value
, 0, reg_base_value_size
* sizeof (rtx
));
2782 /* Wipe the reg_seen array clean. */
2783 memset (reg_seen
, 0, reg_base_value_size
);
2785 /* Mark all hard registers which may contain an address.
2786 The stack, frame and argument pointers may contain an address.
2787 An argument register which can hold a Pmode value may contain
2788 an address even if it is not in BASE_REGS.
2790 The address expression is VOIDmode for an argument and
2791 Pmode for other registers. */
2793 memcpy (new_reg_base_value
, static_reg_base_value
,
2794 FIRST_PSEUDO_REGISTER
* sizeof (rtx
));
2796 /* Walk the insns adding values to the new_reg_base_value array. */
2797 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2803 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2804 /* The prologue/epilogue insns are not threaded onto the
2805 insn chain until after reload has completed. Thus,
2806 there is no sense wasting time checking if INSN is in
2807 the prologue/epilogue until after reload has completed. */
2808 if (reload_completed
2809 && prologue_epilogue_contains (insn
))
2813 /* If this insn has a noalias note, process it, Otherwise,
2814 scan for sets. A simple set will have no side effects
2815 which could change the base value of any other register. */
2817 if (GET_CODE (PATTERN (insn
)) == SET
2818 && REG_NOTES (insn
) != 0
2819 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2820 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2822 note_stores (PATTERN (insn
), record_set
, NULL
);
2824 set
= single_set (insn
);
2827 && GET_CODE (SET_DEST (set
)) == REG
2828 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2830 unsigned int regno
= REGNO (SET_DEST (set
));
2831 rtx src
= SET_SRC (set
);
2833 if (REG_NOTES (insn
) != 0
2834 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
2835 && REG_N_SETS (regno
) == 1)
2836 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
2837 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2838 && ! rtx_varies_p (XEXP (note
, 0), 1)
2839 && ! reg_overlap_mentioned_p (SET_DEST (set
), XEXP (note
, 0)))
2841 reg_known_value
[regno
] = XEXP (note
, 0);
2842 reg_known_equiv_p
[regno
] = REG_NOTE_KIND (note
) == REG_EQUIV
;
2844 else if (REG_N_SETS (regno
) == 1
2845 && GET_CODE (src
) == PLUS
2846 && GET_CODE (XEXP (src
, 0)) == REG
2847 && REGNO (XEXP (src
, 0)) >= FIRST_PSEUDO_REGISTER
2848 && (reg_known_value
[REGNO (XEXP (src
, 0))])
2849 && GET_CODE (XEXP (src
, 1)) == CONST_INT
)
2851 rtx op0
= XEXP (src
, 0);
2852 op0
= reg_known_value
[REGNO (op0
)];
2853 reg_known_value
[regno
]
2854 = plus_constant (op0
, INTVAL (XEXP (src
, 1)));
2855 reg_known_equiv_p
[regno
] = 0;
2857 else if (REG_N_SETS (regno
) == 1
2858 && ! rtx_varies_p (src
, 1))
2860 reg_known_value
[regno
] = src
;
2861 reg_known_equiv_p
[regno
] = 0;
2865 else if (GET_CODE (insn
) == NOTE
2866 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
2867 copying_arguments
= false;
2870 /* Now propagate values from new_reg_base_value to reg_base_value. */
2871 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2873 if (new_reg_base_value
[ui
]
2874 && new_reg_base_value
[ui
] != reg_base_value
[ui
]
2875 && ! rtx_equal_p (new_reg_base_value
[ui
], reg_base_value
[ui
]))
2877 reg_base_value
[ui
] = new_reg_base_value
[ui
];
2882 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2884 /* Fill in the remaining entries. */
2885 for (i
= FIRST_PSEUDO_REGISTER
; i
< maxreg
; i
++)
2886 if (reg_known_value
[i
] == 0)
2887 reg_known_value
[i
] = regno_reg_rtx
[i
];
2889 /* Simplify the reg_base_value array so that no register refers to
2890 another register, except to special registers indirectly through
2891 ADDRESS expressions.
2893 In theory this loop can take as long as O(registers^2), but unless
2894 there are very long dependency chains it will run in close to linear
2897 This loop may not be needed any longer now that the main loop does
2898 a better job at propagating alias information. */
2904 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2906 rtx base
= reg_base_value
[ui
];
2907 if (base
&& GET_CODE (base
) == REG
)
2909 unsigned int base_regno
= REGNO (base
);
2910 if (base_regno
== ui
) /* register set from itself */
2911 reg_base_value
[ui
] = 0;
2913 reg_base_value
[ui
] = reg_base_value
[base_regno
];
2918 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
2921 free (new_reg_base_value
);
2922 new_reg_base_value
= 0;
2925 timevar_pop (TV_ALIAS_ANALYSIS
);
2929 end_alias_analysis (void)
2931 free (reg_known_value
+ FIRST_PSEUDO_REGISTER
);
2932 reg_known_value
= 0;
2933 reg_known_value_size
= 0;
2934 free (reg_known_equiv_p
+ FIRST_PSEUDO_REGISTER
);
2935 reg_known_equiv_p
= 0;
2937 reg_base_value_size
= 0;
2938 if (alias_invariant
)
2940 free (alias_invariant
);
2941 alias_invariant
= 0;
2945 #include "gt-alias.h"