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"
44 /* The alias sets assigned to MEMs assist the back-end in determining
45 which MEMs can alias which other MEMs. In general, two MEMs in
46 different alias sets cannot alias each other, with one important
47 exception. Consider something like:
49 struct S {int i; double d; };
51 a store to an `S' can alias something of either type `int' or type
52 `double'. (However, a store to an `int' cannot alias a `double'
53 and vice versa.) We indicate this via a tree structure that looks
61 (The arrows are directed and point downwards.)
62 In this situation we say the alias set for `struct S' is the
63 `superset' and that those for `int' and `double' are `subsets'.
65 To see whether two alias sets can point to the same memory, we must
66 see if either alias set is a subset of the other. We need not trace
67 past immediate descendents, however, since we propagate all
68 grandchildren up one level.
70 Alias set zero is implicitly a superset of all other alias sets.
71 However, this is no actual entry for alias set zero. It is an
72 error to attempt to explicitly construct a subset of zero. */
74 typedef struct alias_set_entry
76 /* The alias set number, as stored in MEM_ALIAS_SET. */
77 HOST_WIDE_INT alias_set
;
79 /* The children of the alias set. These are not just the immediate
80 children, but, in fact, all descendents. So, if we have:
82 struct T { struct S s; float f; }
84 continuing our example above, the children here will be all of
85 `int', `double', `float', and `struct S'. */
88 /* Nonzero if would have a child of zero: this effectively makes this
89 alias set the same as alias set zero. */
93 static int rtx_equal_for_memref_p
PARAMS ((rtx
, rtx
));
94 static rtx find_symbolic_term
PARAMS ((rtx
));
95 rtx get_addr
PARAMS ((rtx
));
96 static int memrefs_conflict_p
PARAMS ((int, rtx
, int, rtx
,
98 static void record_set
PARAMS ((rtx
, rtx
, void *));
99 static rtx find_base_term
PARAMS ((rtx
));
100 static int base_alias_check
PARAMS ((rtx
, rtx
, enum machine_mode
,
102 static rtx find_base_value
PARAMS ((rtx
));
103 static int mems_in_disjoint_alias_sets_p
PARAMS ((rtx
, rtx
));
104 static int insert_subset_children
PARAMS ((splay_tree_node
, void*));
105 static tree find_base_decl
PARAMS ((tree
));
106 static alias_set_entry get_alias_set_entry
PARAMS ((HOST_WIDE_INT
));
107 static rtx fixed_scalar_and_varying_struct_p
PARAMS ((rtx
, rtx
, rtx
, rtx
,
108 int (*) (rtx
, int)));
109 static int aliases_everything_p
PARAMS ((rtx
));
110 static bool nonoverlapping_component_refs_p
PARAMS ((tree
, tree
));
111 static tree decl_for_component_ref
PARAMS ((tree
));
112 static rtx adjust_offset_for_component_ref
PARAMS ((tree
, rtx
));
113 static int nonoverlapping_memrefs_p
PARAMS ((rtx
, rtx
));
114 static int write_dependence_p
PARAMS ((rtx
, rtx
, int));
116 static int nonlocal_mentioned_p_1
PARAMS ((rtx
*, void *));
117 static int nonlocal_mentioned_p
PARAMS ((rtx
));
118 static int nonlocal_referenced_p_1
PARAMS ((rtx
*, void *));
119 static int nonlocal_referenced_p
PARAMS ((rtx
));
120 static int nonlocal_set_p_1
PARAMS ((rtx
*, void *));
121 static int nonlocal_set_p
PARAMS ((rtx
));
123 /* Set up all info needed to perform alias analysis on memory references. */
125 /* Returns the size in bytes of the mode of X. */
126 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
128 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
129 different alias sets. We ignore alias sets in functions making use
130 of variable arguments because the va_arg macros on some systems are
132 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
133 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
135 /* Cap the number of passes we make over the insns propagating alias
136 information through set chains. 10 is a completely arbitrary choice. */
137 #define MAX_ALIAS_LOOP_PASSES 10
139 /* reg_base_value[N] gives an address to which register N is related.
140 If all sets after the first add or subtract to the current value
141 or otherwise modify it so it does not point to a different top level
142 object, reg_base_value[N] is equal to the address part of the source
145 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
146 expressions represent certain special values: function arguments and
147 the stack, frame, and argument pointers.
149 The contents of an ADDRESS is not normally used, the mode of the
150 ADDRESS determines whether the ADDRESS is a function argument or some
151 other special value. Pointer equality, not rtx_equal_p, determines whether
152 two ADDRESS expressions refer to the same base address.
154 The only use of the contents of an ADDRESS is for determining if the
155 current function performs nonlocal memory memory references for the
156 purposes of marking the function as a constant function. */
158 static GTY((length ("reg_base_value_size"))) rtx
*reg_base_value
;
159 static rtx
*new_reg_base_value
;
160 static unsigned int reg_base_value_size
; /* size of reg_base_value array */
162 /* Static hunks of RTL used by the aliasing code; these are initialized
163 once per function to avoid unnecessary RTL allocations. */
164 static GTY (()) rtx static_reg_base_value
[FIRST_PSEUDO_REGISTER
];
166 #define REG_BASE_VALUE(X) \
167 (REGNO (X) < reg_base_value_size \
168 ? reg_base_value[REGNO (X)] : 0)
170 /* Vector of known invariant relationships between registers. Set in
171 loop unrolling. Indexed by register number, if nonzero the value
172 is an expression describing this register in terms of another.
174 The length of this array is REG_BASE_VALUE_SIZE.
176 Because this array contains only pseudo registers it has no effect
178 static rtx
*alias_invariant
;
180 /* Vector indexed by N giving the initial (unchanging) value known for
181 pseudo-register N. This array is initialized in
182 init_alias_analysis, and does not change until end_alias_analysis
184 rtx
*reg_known_value
;
186 /* Indicates number of valid entries in reg_known_value. */
187 static unsigned int reg_known_value_size
;
189 /* Vector recording for each reg_known_value whether it is due to a
190 REG_EQUIV note. Future passes (viz., reload) may replace the
191 pseudo with the equivalent expression and so we account for the
192 dependences that would be introduced if that happens.
194 The REG_EQUIV notes created in assign_parms may mention the arg
195 pointer, and there are explicit insns in the RTL that modify the
196 arg pointer. Thus we must ensure that such insns don't get
197 scheduled across each other because that would invalidate the
198 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
199 wrong, but solving the problem in the scheduler will likely give
200 better code, so we do it here. */
201 char *reg_known_equiv_p
;
203 /* True when scanning insns from the start of the rtl to the
204 NOTE_INSN_FUNCTION_BEG note. */
205 static bool copying_arguments
;
207 /* The splay-tree used to store the various alias set entries. */
208 static splay_tree alias_sets
;
210 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
211 such an entry, or NULL otherwise. */
213 static alias_set_entry
214 get_alias_set_entry (alias_set
)
215 HOST_WIDE_INT alias_set
;
218 = splay_tree_lookup (alias_sets
, (splay_tree_key
) alias_set
);
220 return sn
!= 0 ? ((alias_set_entry
) sn
->value
) : 0;
223 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
224 the two MEMs cannot alias each other. */
227 mems_in_disjoint_alias_sets_p (mem1
, mem2
)
231 #ifdef ENABLE_CHECKING
232 /* Perform a basic sanity check. Namely, that there are no alias sets
233 if we're not using strict aliasing. This helps to catch bugs
234 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
235 where a MEM is allocated in some way other than by the use of
236 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
237 use alias sets to indicate that spilled registers cannot alias each
238 other, we might need to remove this check. */
239 if (! flag_strict_aliasing
240 && (MEM_ALIAS_SET (mem1
) != 0 || MEM_ALIAS_SET (mem2
) != 0))
244 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
), MEM_ALIAS_SET (mem2
));
247 /* Insert the NODE into the splay tree given by DATA. Used by
248 record_alias_subset via splay_tree_foreach. */
251 insert_subset_children (node
, data
)
252 splay_tree_node node
;
255 splay_tree_insert ((splay_tree
) data
, node
->key
, node
->value
);
260 /* Return 1 if the two specified alias sets may conflict. */
263 alias_sets_conflict_p (set1
, set2
)
264 HOST_WIDE_INT set1
, set2
;
268 /* If have no alias set information for one of the operands, we have
269 to assume it can alias anything. */
270 if (set1
== 0 || set2
== 0
271 /* If the two alias sets are the same, they may alias. */
275 /* See if the first alias set is a subset of the second. */
276 ase
= get_alias_set_entry (set1
);
278 && (ase
->has_zero_child
279 || splay_tree_lookup (ase
->children
,
280 (splay_tree_key
) set2
)))
283 /* Now do the same, but with the alias sets reversed. */
284 ase
= get_alias_set_entry (set2
);
286 && (ase
->has_zero_child
287 || splay_tree_lookup (ase
->children
,
288 (splay_tree_key
) set1
)))
291 /* The two alias sets are distinct and neither one is the
292 child of the other. Therefore, they cannot alias. */
296 /* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has
297 has any readonly fields. If any of the fields have types that
298 contain readonly fields, return true as well. */
301 readonly_fields_p (type
)
306 if (TREE_CODE (type
) != RECORD_TYPE
&& TREE_CODE (type
) != UNION_TYPE
307 && TREE_CODE (type
) != QUAL_UNION_TYPE
)
310 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
311 if (TREE_CODE (field
) == FIELD_DECL
312 && (TREE_READONLY (field
)
313 || readonly_fields_p (TREE_TYPE (field
))))
319 /* Return 1 if any MEM object of type T1 will always conflict (using the
320 dependency routines in this file) with any MEM object of type T2.
321 This is used when allocating temporary storage. If T1 and/or T2 are
322 NULL_TREE, it means we know nothing about the storage. */
325 objects_must_conflict_p (t1
, t2
)
328 /* If neither has a type specified, we don't know if they'll conflict
329 because we may be using them to store objects of various types, for
330 example the argument and local variables areas of inlined functions. */
331 if (t1
== 0 && t2
== 0)
334 /* If one or the other has readonly fields or is readonly,
335 then they may not conflict. */
336 if ((t1
!= 0 && readonly_fields_p (t1
))
337 || (t2
!= 0 && readonly_fields_p (t2
))
338 || (t1
!= 0 && lang_hooks
.honor_readonly
&& TYPE_READONLY (t1
))
339 || (t2
!= 0 && lang_hooks
.honor_readonly
&& TYPE_READONLY (t2
)))
342 /* If they are the same type, they must conflict. */
344 /* Likewise if both are volatile. */
345 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
348 /* If one is aggregate and the other is scalar then they may not
350 if ((t1
!= 0 && AGGREGATE_TYPE_P (t1
))
351 != (t2
!= 0 && AGGREGATE_TYPE_P (t2
)))
354 /* Otherwise they conflict only if the alias sets conflict. */
355 return alias_sets_conflict_p (t1
? get_alias_set (t1
) : 0,
356 t2
? get_alias_set (t2
) : 0);
359 /* T is an expression with pointer type. Find the DECL on which this
360 expression is based. (For example, in `a[i]' this would be `a'.)
361 If there is no such DECL, or a unique decl cannot be determined,
362 NULL_TREE is returned. */
370 if (t
== 0 || t
== error_mark_node
|| ! POINTER_TYPE_P (TREE_TYPE (t
)))
373 /* If this is a declaration, return it. */
374 if (TREE_CODE_CLASS (TREE_CODE (t
)) == 'd')
377 /* Handle general expressions. It would be nice to deal with
378 COMPONENT_REFs here. If we could tell that `a' and `b' were the
379 same, then `a->f' and `b->f' are also the same. */
380 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
383 return find_base_decl (TREE_OPERAND (t
, 0));
386 /* Return 0 if found in neither or both are the same. */
387 d0
= find_base_decl (TREE_OPERAND (t
, 0));
388 d1
= find_base_decl (TREE_OPERAND (t
, 1));
399 d0
= find_base_decl (TREE_OPERAND (t
, 0));
400 d1
= find_base_decl (TREE_OPERAND (t
, 1));
401 d2
= find_base_decl (TREE_OPERAND (t
, 2));
403 /* Set any nonzero values from the last, then from the first. */
404 if (d1
== 0) d1
= d2
;
405 if (d0
== 0) d0
= d1
;
406 if (d1
== 0) d1
= d0
;
407 if (d2
== 0) d2
= d1
;
409 /* At this point all are nonzero or all are zero. If all three are the
410 same, return it. Otherwise, return zero. */
411 return (d0
== d1
&& d1
== d2
) ? d0
: 0;
418 /* Return 1 if all the nested component references handled by
419 get_inner_reference in T are such that we can address the object in T. */
425 /* If we're at the end, it is vacuously addressable. */
426 if (! handled_component_p (t
))
429 /* Bitfields are never addressable. */
430 else if (TREE_CODE (t
) == BIT_FIELD_REF
)
433 /* Fields are addressable unless they are marked as nonaddressable or
434 the containing type has alias set 0. */
435 else if (TREE_CODE (t
) == COMPONENT_REF
436 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1))
437 && get_alias_set (TREE_TYPE (TREE_OPERAND (t
, 0))) != 0
438 && can_address_p (TREE_OPERAND (t
, 0)))
441 /* Likewise for arrays. */
442 else if ((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
443 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0)))
444 && get_alias_set (TREE_TYPE (TREE_OPERAND (t
, 0))) != 0
445 && can_address_p (TREE_OPERAND (t
, 0)))
451 /* Return the alias set for T, which may be either a type or an
452 expression. Call language-specific routine for help, if needed. */
460 /* If we're not doing any alias analysis, just assume everything
461 aliases everything else. Also return 0 if this or its type is
463 if (! flag_strict_aliasing
|| t
== error_mark_node
465 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
468 /* We can be passed either an expression or a type. This and the
469 language-specific routine may make mutually-recursive calls to each other
470 to figure out what to do. At each juncture, we see if this is a tree
471 that the language may need to handle specially. First handle things that
476 tree placeholder_ptr
= 0;
478 /* Remove any nops, then give the language a chance to do
479 something with this tree before we look at it. */
481 set
= (*lang_hooks
.get_alias_set
) (t
);
485 /* First see if the actual object referenced is an INDIRECT_REF from a
486 restrict-qualified pointer or a "void *". Replace
487 PLACEHOLDER_EXPRs. */
488 while (TREE_CODE (inner
) == PLACEHOLDER_EXPR
489 || handled_component_p (inner
))
491 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
)
492 inner
= find_placeholder (inner
, &placeholder_ptr
);
494 inner
= TREE_OPERAND (inner
, 0);
499 /* Check for accesses through restrict-qualified pointers. */
500 if (TREE_CODE (inner
) == INDIRECT_REF
)
502 tree decl
= find_base_decl (TREE_OPERAND (inner
, 0));
504 if (decl
&& DECL_POINTER_ALIAS_SET_KNOWN_P (decl
))
506 /* If we haven't computed the actual alias set, do it now. */
507 if (DECL_POINTER_ALIAS_SET (decl
) == -2)
509 /* No two restricted pointers can point at the same thing.
510 However, a restricted pointer can point at the same thing
511 as an unrestricted pointer, if that unrestricted pointer
512 is based on the restricted pointer. So, we make the
513 alias set for the restricted pointer a subset of the
514 alias set for the type pointed to by the type of the
516 HOST_WIDE_INT pointed_to_alias_set
517 = get_alias_set (TREE_TYPE (TREE_TYPE (decl
)));
519 if (pointed_to_alias_set
== 0)
520 /* It's not legal to make a subset of alias set zero. */
524 DECL_POINTER_ALIAS_SET (decl
) = new_alias_set ();
525 record_alias_subset (pointed_to_alias_set
,
526 DECL_POINTER_ALIAS_SET (decl
));
530 /* We use the alias set indicated in the declaration. */
531 return DECL_POINTER_ALIAS_SET (decl
);
534 /* If we have an INDIRECT_REF via a void pointer, we don't
535 know anything about what that might alias. */
536 else if (TREE_CODE (TREE_TYPE (inner
)) == VOID_TYPE
)
540 /* Otherwise, pick up the outermost object that we could have a pointer
541 to, processing conversion and PLACEHOLDER_EXPR as above. */
543 while (TREE_CODE (t
) == PLACEHOLDER_EXPR
544 || (handled_component_p (t
) && ! can_address_p (t
)))
546 if (TREE_CODE (t
) == PLACEHOLDER_EXPR
)
547 t
= find_placeholder (t
, &placeholder_ptr
);
549 t
= TREE_OPERAND (t
, 0);
554 /* If we've already determined the alias set for a decl, just return
555 it. This is necessary for C++ anonymous unions, whose component
556 variables don't look like union members (boo!). */
557 if (TREE_CODE (t
) == VAR_DECL
558 && DECL_RTL_SET_P (t
) && GET_CODE (DECL_RTL (t
)) == MEM
)
559 return MEM_ALIAS_SET (DECL_RTL (t
));
561 /* Now all we care about is the type. */
565 /* Variant qualifiers don't affect the alias set, so get the main
566 variant. If this is a type with a known alias set, return it. */
567 t
= TYPE_MAIN_VARIANT (t
);
568 if (TYPE_ALIAS_SET_KNOWN_P (t
))
569 return TYPE_ALIAS_SET (t
);
571 /* See if the language has special handling for this type. */
572 set
= (*lang_hooks
.get_alias_set
) (t
);
576 /* There are no objects of FUNCTION_TYPE, so there's no point in
577 using up an alias set for them. (There are, of course, pointers
578 and references to functions, but that's different.) */
579 else if (TREE_CODE (t
) == FUNCTION_TYPE
)
582 /* Unless the language specifies otherwise, let vector types alias
583 their components. This avoids some nasty type punning issues in
584 normal usage. And indeed lets vectors be treated more like an
586 else if (TREE_CODE (t
) == VECTOR_TYPE
)
587 set
= get_alias_set (TREE_TYPE (t
));
590 /* Otherwise make a new alias set for this type. */
591 set
= new_alias_set ();
593 TYPE_ALIAS_SET (t
) = set
;
595 /* If this is an aggregate type, we must record any component aliasing
597 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
598 record_component_aliases (t
);
603 /* Return a brand-new alias set. */
608 static HOST_WIDE_INT last_alias_set
;
610 if (flag_strict_aliasing
)
611 return ++last_alias_set
;
616 /* Indicate that things in SUBSET can alias things in SUPERSET, but
617 not vice versa. For example, in C, a store to an `int' can alias a
618 structure containing an `int', but not vice versa. Here, the
619 structure would be the SUPERSET and `int' the SUBSET. This
620 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 (superset
, subset
)
627 HOST_WIDE_INT superset
;
628 HOST_WIDE_INT subset
;
630 alias_set_entry superset_entry
;
631 alias_set_entry subset_entry
;
633 /* It is possible in complex type situations for both sets to be the same,
634 in which case we can ignore this operation. */
635 if (superset
== subset
)
641 superset_entry
= get_alias_set_entry (superset
);
642 if (superset_entry
== 0)
644 /* Create an entry for the SUPERSET, so that we have a place to
645 attach the SUBSET. */
647 = (alias_set_entry
) xmalloc (sizeof (struct alias_set_entry
));
648 superset_entry
->alias_set
= superset
;
649 superset_entry
->children
650 = splay_tree_new (splay_tree_compare_ints
, 0, 0);
651 superset_entry
->has_zero_child
= 0;
652 splay_tree_insert (alias_sets
, (splay_tree_key
) superset
,
653 (splay_tree_value
) superset_entry
);
657 superset_entry
->has_zero_child
= 1;
660 subset_entry
= get_alias_set_entry (subset
);
661 /* If there is an entry for the subset, enter all of its children
662 (if they are not already present) as children of the SUPERSET. */
665 if (subset_entry
->has_zero_child
)
666 superset_entry
->has_zero_child
= 1;
668 splay_tree_foreach (subset_entry
->children
, insert_subset_children
,
669 superset_entry
->children
);
672 /* Enter the SUBSET itself as a child of the SUPERSET. */
673 splay_tree_insert (superset_entry
->children
,
674 (splay_tree_key
) subset
, 0);
678 /* Record that component types of TYPE, if any, are part of that type for
679 aliasing purposes. For record types, we only record component types
680 for fields that are marked addressable. For array types, we always
681 record the component types, so the front end should not call this
682 function if the individual component aren't addressable. */
685 record_component_aliases (type
)
688 HOST_WIDE_INT superset
= get_alias_set (type
);
694 switch (TREE_CODE (type
))
697 if (! TYPE_NONALIASED_COMPONENT (type
))
698 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
703 case QUAL_UNION_TYPE
:
704 /* Recursively record aliases for the base classes, if there are any */
705 if (TYPE_BINFO (type
) != NULL
&& TYPE_BINFO_BASETYPES (type
) != NULL
)
708 for (i
= 0; i
< TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type
)); i
++)
710 tree binfo
= TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type
), i
);
711 record_alias_subset (superset
,
712 get_alias_set (BINFO_TYPE (binfo
)));
715 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= TREE_CHAIN (field
))
716 if (TREE_CODE (field
) == FIELD_DECL
&& ! DECL_NONADDRESSABLE_P (field
))
717 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
721 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
729 /* Allocate an alias set for use in storing and reading from the varargs
733 get_varargs_alias_set ()
735 static HOST_WIDE_INT set
= -1;
738 set
= new_alias_set ();
743 /* Likewise, but used for the fixed portions of the frame, e.g., register
747 get_frame_alias_set ()
749 static HOST_WIDE_INT set
= -1;
752 set
= new_alias_set ();
757 /* Inside SRC, the source of a SET, find a base address. */
760 find_base_value (src
)
765 switch (GET_CODE (src
))
773 /* At the start of a function, argument registers have known base
774 values which may be lost later. Returning an ADDRESS
775 expression here allows optimization based on argument values
776 even when the argument registers are used for other purposes. */
777 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
778 return new_reg_base_value
[regno
];
780 /* If a pseudo has a known base value, return it. Do not do this
781 for non-fixed hard regs since it can result in a circular
782 dependency chain for registers which have values at function entry.
784 The test above is not sufficient because the scheduler may move
785 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
786 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
787 && regno
< reg_base_value_size
)
789 /* If we're inside init_alias_analysis, use new_reg_base_value
790 to reduce the number of relaxation iterations. */
791 if (new_reg_base_value
&& new_reg_base_value
[regno
]
792 && REG_N_SETS (regno
) == 1)
793 return new_reg_base_value
[regno
];
795 if (reg_base_value
[regno
])
796 return reg_base_value
[regno
];
802 /* Check for an argument passed in memory. Only record in the
803 copying-arguments block; it is too hard to track changes
805 if (copying_arguments
806 && (XEXP (src
, 0) == arg_pointer_rtx
807 || (GET_CODE (XEXP (src
, 0)) == PLUS
808 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
809 return gen_rtx_ADDRESS (VOIDmode
, src
);
814 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
817 /* ... fall through ... */
822 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
824 /* If either operand is a REG that is a known pointer, then it
826 if (REG_P (src_0
) && REG_POINTER (src_0
))
827 return find_base_value (src_0
);
828 if (REG_P (src_1
) && REG_POINTER (src_1
))
829 return find_base_value (src_1
);
831 /* If either operand is a REG, then see if we already have
832 a known value for it. */
835 temp
= find_base_value (src_0
);
842 temp
= find_base_value (src_1
);
847 /* If either base is named object or a special address
848 (like an argument or stack reference), then use it for the
851 && (GET_CODE (src_0
) == SYMBOL_REF
852 || GET_CODE (src_0
) == LABEL_REF
853 || (GET_CODE (src_0
) == ADDRESS
854 && GET_MODE (src_0
) != VOIDmode
)))
858 && (GET_CODE (src_1
) == SYMBOL_REF
859 || GET_CODE (src_1
) == LABEL_REF
860 || (GET_CODE (src_1
) == ADDRESS
861 && GET_MODE (src_1
) != VOIDmode
)))
864 /* Guess which operand is the base address:
865 If either operand is a symbol, then it is the base. If
866 either operand is a CONST_INT, then the other is the base. */
867 if (GET_CODE (src_1
) == CONST_INT
|| CONSTANT_P (src_0
))
868 return find_base_value (src_0
);
869 else if (GET_CODE (src_0
) == CONST_INT
|| CONSTANT_P (src_1
))
870 return find_base_value (src_1
);
876 /* The standard form is (lo_sum reg sym) so look only at the
878 return find_base_value (XEXP (src
, 1));
881 /* If the second operand is constant set the base
882 address to the first operand. */
883 if (GET_CODE (XEXP (src
, 1)) == CONST_INT
&& INTVAL (XEXP (src
, 1)) != 0)
884 return find_base_value (XEXP (src
, 0));
888 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
898 return find_base_value (XEXP (src
, 0));
901 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
903 rtx temp
= find_base_value (XEXP (src
, 0));
905 #ifdef POINTERS_EXTEND_UNSIGNED
906 if (temp
!= 0 && CONSTANT_P (temp
) && GET_MODE (temp
) != Pmode
)
907 temp
= convert_memory_address (Pmode
, temp
);
920 /* Called from init_alias_analysis indirectly through note_stores. */
922 /* While scanning insns to find base values, reg_seen[N] is nonzero if
923 register N has been set in this function. */
924 static char *reg_seen
;
926 /* Addresses which are known not to alias anything else are identified
927 by a unique integer. */
928 static int unique_id
;
931 record_set (dest
, set
, data
)
933 void *data ATTRIBUTE_UNUSED
;
939 if (GET_CODE (dest
) != REG
)
942 regno
= REGNO (dest
);
944 if (regno
>= reg_base_value_size
)
947 /* If this spans multiple hard registers, then we must indicate that every
948 register has an unusable value. */
949 if (regno
< FIRST_PSEUDO_REGISTER
)
950 n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
957 reg_seen
[regno
+ n
] = 1;
958 new_reg_base_value
[regno
+ n
] = 0;
965 /* A CLOBBER wipes out any old value but does not prevent a previously
966 unset register from acquiring a base address (i.e. reg_seen is not
968 if (GET_CODE (set
) == CLOBBER
)
970 new_reg_base_value
[regno
] = 0;
979 new_reg_base_value
[regno
] = 0;
983 new_reg_base_value
[regno
] = gen_rtx_ADDRESS (Pmode
,
984 GEN_INT (unique_id
++));
988 /* This is not the first set. If the new value is not related to the
989 old value, forget the base value. Note that the following code is
991 extern int x, y; int *p = &x; p += (&y-&x);
992 ANSI C does not allow computing the difference of addresses
993 of distinct top level objects. */
994 if (new_reg_base_value
[regno
])
995 switch (GET_CODE (src
))
999 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1000 new_reg_base_value
[regno
] = 0;
1003 /* If the value we add in the PLUS is also a valid base value,
1004 this might be the actual base value, and the original value
1007 rtx other
= NULL_RTX
;
1009 if (XEXP (src
, 0) == dest
)
1010 other
= XEXP (src
, 1);
1011 else if (XEXP (src
, 1) == dest
)
1012 other
= XEXP (src
, 0);
1014 if (! other
|| find_base_value (other
))
1015 new_reg_base_value
[regno
] = 0;
1019 if (XEXP (src
, 0) != dest
|| GET_CODE (XEXP (src
, 1)) != CONST_INT
)
1020 new_reg_base_value
[regno
] = 0;
1023 new_reg_base_value
[regno
] = 0;
1026 /* If this is the first set of a register, record the value. */
1027 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1028 && ! reg_seen
[regno
] && new_reg_base_value
[regno
] == 0)
1029 new_reg_base_value
[regno
] = find_base_value (src
);
1031 reg_seen
[regno
] = 1;
1034 /* Called from loop optimization when a new pseudo-register is
1035 created. It indicates that REGNO is being set to VAL. f INVARIANT
1036 is true then this value also describes an invariant relationship
1037 which can be used to deduce that two registers with unknown values
1041 record_base_value (regno
, val
, invariant
)
1046 if (regno
>= reg_base_value_size
)
1049 if (invariant
&& alias_invariant
)
1050 alias_invariant
[regno
] = val
;
1052 if (GET_CODE (val
) == REG
)
1054 if (REGNO (val
) < reg_base_value_size
)
1055 reg_base_value
[regno
] = reg_base_value
[REGNO (val
)];
1060 reg_base_value
[regno
] = find_base_value (val
);
1063 /* Clear alias info for a register. This is used if an RTL transformation
1064 changes the value of a register. This is used in flow by AUTO_INC_DEC
1065 optimizations. We don't need to clear reg_base_value, since flow only
1066 changes the offset. */
1069 clear_reg_alias_info (reg
)
1072 unsigned int regno
= REGNO (reg
);
1074 if (regno
< reg_known_value_size
&& regno
>= FIRST_PSEUDO_REGISTER
)
1075 reg_known_value
[regno
] = reg
;
1078 /* Returns a canonical version of X, from the point of view alias
1079 analysis. (For example, if X is a MEM whose address is a register,
1080 and the register has a known value (say a SYMBOL_REF), then a MEM
1081 whose address is the SYMBOL_REF is returned.) */
1087 /* Recursively look for equivalences. */
1088 if (GET_CODE (x
) == REG
&& REGNO (x
) >= FIRST_PSEUDO_REGISTER
1089 && REGNO (x
) < reg_known_value_size
)
1090 return reg_known_value
[REGNO (x
)] == x
1091 ? x
: canon_rtx (reg_known_value
[REGNO (x
)]);
1092 else if (GET_CODE (x
) == PLUS
)
1094 rtx x0
= canon_rtx (XEXP (x
, 0));
1095 rtx x1
= canon_rtx (XEXP (x
, 1));
1097 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1099 if (GET_CODE (x0
) == CONST_INT
)
1100 return plus_constant (x1
, INTVAL (x0
));
1101 else if (GET_CODE (x1
) == CONST_INT
)
1102 return plus_constant (x0
, INTVAL (x1
));
1103 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1107 /* This gives us much better alias analysis when called from
1108 the loop optimizer. Note we want to leave the original
1109 MEM alone, but need to return the canonicalized MEM with
1110 all the flags with their original values. */
1111 else if (GET_CODE (x
) == MEM
)
1112 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1117 /* Return 1 if X and Y are identical-looking rtx's.
1119 We use the data in reg_known_value above to see if two registers with
1120 different numbers are, in fact, equivalent. */
1123 rtx_equal_for_memref_p (x
, y
)
1131 if (x
== 0 && y
== 0)
1133 if (x
== 0 || y
== 0)
1142 code
= GET_CODE (x
);
1143 /* Rtx's of different codes cannot be equal. */
1144 if (code
!= GET_CODE (y
))
1147 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1148 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1150 if (GET_MODE (x
) != GET_MODE (y
))
1153 /* Some RTL can be compared without a recursive examination. */
1157 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
1160 return REGNO (x
) == REGNO (y
);
1163 return XEXP (x
, 0) == XEXP (y
, 0);
1166 return XSTR (x
, 0) == XSTR (y
, 0);
1170 /* There's no need to compare the contents of CONST_DOUBLEs or
1171 CONST_INTs because pointer equality is a good enough
1172 comparison for these nodes. */
1176 return (XINT (x
, 1) == XINT (y
, 1)
1177 && rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0)));
1183 /* For commutative operations, the RTX match if the operand match in any
1184 order. Also handle the simple binary and unary cases without a loop. */
1185 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
1186 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1187 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1188 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1189 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1190 else if (GET_RTX_CLASS (code
) == '<' || GET_RTX_CLASS (code
) == '2')
1191 return (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1192 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)));
1193 else if (GET_RTX_CLASS (code
) == '1')
1194 return rtx_equal_for_memref_p (XEXP (x
, 0), 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 (XVECEXP (x
, i
, j
),
1219 XVECEXP (y
, i
, j
)) == 0)
1224 if (rtx_equal_for_memref_p (XEXP (x
, i
), XEXP (y
, i
)) == 0)
1228 /* This can happen for asm operands. */
1230 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1234 /* This can happen for an asm which clobbers memory. */
1238 /* It is believed that rtx's at this level will never
1239 contain anything but integers and other rtx's,
1240 except for within LABEL_REFs and SYMBOL_REFs. */
1248 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
1249 X and return it, or return 0 if none found. */
1252 find_symbolic_term (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')
1287 struct elt_loc_list
*l
;
1289 #if defined (FIND_BASE_TERM)
1290 /* Try machine-dependent ways to find the base term. */
1291 x
= FIND_BASE_TERM (x
);
1294 switch (GET_CODE (x
))
1297 return REG_BASE_VALUE (x
);
1300 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1310 return find_base_term (XEXP (x
, 0));
1313 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1315 rtx temp
= find_base_term (XEXP (x
, 0));
1317 #ifdef POINTERS_EXTEND_UNSIGNED
1318 if (temp
!= 0 && CONSTANT_P (temp
) && GET_MODE (temp
) != Pmode
)
1319 temp
= convert_memory_address (Pmode
, temp
);
1326 val
= CSELIB_VAL_PTR (x
);
1327 for (l
= val
->locs
; l
; l
= l
->next
)
1328 if ((x
= find_base_term (l
->loc
)) != 0)
1334 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1341 rtx tmp1
= XEXP (x
, 0);
1342 rtx tmp2
= XEXP (x
, 1);
1344 /* This is a little bit tricky since we have to determine which of
1345 the two operands represents the real base address. Otherwise this
1346 routine may return the index register instead of the base register.
1348 That may cause us to believe no aliasing was possible, when in
1349 fact aliasing is possible.
1351 We use a few simple tests to guess the base register. Additional
1352 tests can certainly be added. For example, if one of the operands
1353 is a shift or multiply, then it must be the index register and the
1354 other operand is the base register. */
1356 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1357 return find_base_term (tmp2
);
1359 /* If either operand is known to be a pointer, then use it
1360 to determine the base term. */
1361 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1362 return find_base_term (tmp1
);
1364 if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1365 return find_base_term (tmp2
);
1367 /* Neither operand was known to be a pointer. Go ahead and find the
1368 base term for both operands. */
1369 tmp1
= find_base_term (tmp1
);
1370 tmp2
= find_base_term (tmp2
);
1372 /* If either base term is named object or a special address
1373 (like an argument or stack reference), then use it for the
1376 && (GET_CODE (tmp1
) == SYMBOL_REF
1377 || GET_CODE (tmp1
) == LABEL_REF
1378 || (GET_CODE (tmp1
) == ADDRESS
1379 && GET_MODE (tmp1
) != VOIDmode
)))
1383 && (GET_CODE (tmp2
) == SYMBOL_REF
1384 || GET_CODE (tmp2
) == LABEL_REF
1385 || (GET_CODE (tmp2
) == ADDRESS
1386 && GET_MODE (tmp2
) != VOIDmode
)))
1389 /* We could not determine which of the two operands was the
1390 base register and which was the index. So we can determine
1391 nothing from the base alias check. */
1396 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
&& INTVAL (XEXP (x
, 1)) != 0)
1397 return find_base_term (XEXP (x
, 0));
1405 return REG_BASE_VALUE (frame_pointer_rtx
);
1412 /* Return 0 if the addresses X and Y are known to point to different
1413 objects, 1 if they might be pointers to the same object. */
1416 base_alias_check (x
, y
, x_mode
, y_mode
)
1418 enum machine_mode x_mode
, y_mode
;
1420 rtx x_base
= find_base_term (x
);
1421 rtx y_base
= find_base_term (y
);
1423 /* If the address itself has no known base see if a known equivalent
1424 value has one. If either address still has no known base, nothing
1425 is known about aliasing. */
1430 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1433 x_base
= find_base_term (x_c
);
1441 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1444 y_base
= find_base_term (y_c
);
1449 /* If the base addresses are equal nothing is known about aliasing. */
1450 if (rtx_equal_p (x_base
, y_base
))
1453 /* The base addresses of the read and write are different expressions.
1454 If they are both symbols and they are not accessed via AND, there is
1455 no conflict. We can bring knowledge of object alignment into play
1456 here. For example, on alpha, "char a, b;" can alias one another,
1457 though "char a; long b;" cannot. */
1458 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1460 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1462 if (GET_CODE (x
) == AND
1463 && (GET_CODE (XEXP (x
, 1)) != CONST_INT
1464 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1466 if (GET_CODE (y
) == AND
1467 && (GET_CODE (XEXP (y
, 1)) != CONST_INT
1468 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1470 /* Differing symbols never alias. */
1474 /* If one address is a stack reference there can be no alias:
1475 stack references using different base registers do not alias,
1476 a stack reference can not alias a parameter, and a stack reference
1477 can not alias a global. */
1478 if ((GET_CODE (x_base
) == ADDRESS
&& GET_MODE (x_base
) == Pmode
)
1479 || (GET_CODE (y_base
) == ADDRESS
&& GET_MODE (y_base
) == Pmode
))
1482 if (! flag_argument_noalias
)
1485 if (flag_argument_noalias
> 1)
1488 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1489 return ! (GET_MODE (x_base
) == VOIDmode
&& GET_MODE (y_base
) == VOIDmode
);
1492 /* Convert the address X into something we can use. This is done by returning
1493 it unchanged unless it is a value; in the latter case we call cselib to get
1494 a more useful rtx. */
1501 struct elt_loc_list
*l
;
1503 if (GET_CODE (x
) != VALUE
)
1505 v
= CSELIB_VAL_PTR (x
);
1506 for (l
= v
->locs
; l
; l
= l
->next
)
1507 if (CONSTANT_P (l
->loc
))
1509 for (l
= v
->locs
; l
; l
= l
->next
)
1510 if (GET_CODE (l
->loc
) != REG
&& GET_CODE (l
->loc
) != MEM
)
1513 return v
->locs
->loc
;
1517 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1518 where SIZE is the size in bytes of the memory reference. If ADDR
1519 is not modified by the memory reference then ADDR is returned. */
1522 addr_side_effect_eval (addr
, size
, n_refs
)
1529 switch (GET_CODE (addr
))
1532 offset
= (n_refs
+ 1) * size
;
1535 offset
= -(n_refs
+ 1) * size
;
1538 offset
= n_refs
* size
;
1541 offset
= -n_refs
* size
;
1549 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0), GEN_INT (offset
));
1551 addr
= XEXP (addr
, 0);
1556 /* Return nonzero if X and Y (memory addresses) could reference the
1557 same location in memory. C is an offset accumulator. When
1558 C is nonzero, we are testing aliases between X and Y + C.
1559 XSIZE is the size in bytes of the X reference,
1560 similarly YSIZE is the size in bytes for Y.
1562 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1563 referenced (the reference was BLKmode), so make the most pessimistic
1566 If XSIZE or YSIZE is negative, we may access memory outside the object
1567 being referenced as a side effect. This can happen when using AND to
1568 align memory references, as is done on the Alpha.
1570 Nice to notice that varying addresses cannot conflict with fp if no
1571 local variables had their addresses taken, but that's too hard now. */
1574 memrefs_conflict_p (xsize
, x
, ysize
, y
, c
)
1579 if (GET_CODE (x
) == VALUE
)
1581 if (GET_CODE (y
) == VALUE
)
1583 if (GET_CODE (x
) == HIGH
)
1585 else if (GET_CODE (x
) == LO_SUM
)
1588 x
= canon_rtx (addr_side_effect_eval (x
, xsize
, 0));
1589 if (GET_CODE (y
) == HIGH
)
1591 else if (GET_CODE (y
) == LO_SUM
)
1594 y
= canon_rtx (addr_side_effect_eval (y
, ysize
, 0));
1596 if (rtx_equal_for_memref_p (x
, y
))
1598 if (xsize
<= 0 || ysize
<= 0)
1600 if (c
>= 0 && xsize
> c
)
1602 if (c
< 0 && ysize
+c
> 0)
1607 /* This code used to check for conflicts involving stack references and
1608 globals but the base address alias code now handles these cases. */
1610 if (GET_CODE (x
) == PLUS
)
1612 /* The fact that X is canonicalized means that this
1613 PLUS rtx is canonicalized. */
1614 rtx x0
= XEXP (x
, 0);
1615 rtx x1
= XEXP (x
, 1);
1617 if (GET_CODE (y
) == PLUS
)
1619 /* The fact that Y is canonicalized means that this
1620 PLUS rtx is canonicalized. */
1621 rtx y0
= XEXP (y
, 0);
1622 rtx y1
= XEXP (y
, 1);
1624 if (rtx_equal_for_memref_p (x1
, y1
))
1625 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1626 if (rtx_equal_for_memref_p (x0
, y0
))
1627 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
1628 if (GET_CODE (x1
) == CONST_INT
)
1630 if (GET_CODE (y1
) == CONST_INT
)
1631 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
1632 c
- INTVAL (x1
) + INTVAL (y1
));
1634 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
1637 else if (GET_CODE (y1
) == CONST_INT
)
1638 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1642 else if (GET_CODE (x1
) == CONST_INT
)
1643 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
1645 else if (GET_CODE (y
) == PLUS
)
1647 /* The fact that Y is canonicalized means that this
1648 PLUS rtx is canonicalized. */
1649 rtx y0
= XEXP (y
, 0);
1650 rtx y1
= XEXP (y
, 1);
1652 if (GET_CODE (y1
) == CONST_INT
)
1653 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
1658 if (GET_CODE (x
) == GET_CODE (y
))
1659 switch (GET_CODE (x
))
1663 /* Handle cases where we expect the second operands to be the
1664 same, and check only whether the first operand would conflict
1667 rtx x1
= canon_rtx (XEXP (x
, 1));
1668 rtx y1
= canon_rtx (XEXP (y
, 1));
1669 if (! rtx_equal_for_memref_p (x1
, y1
))
1671 x0
= canon_rtx (XEXP (x
, 0));
1672 y0
= canon_rtx (XEXP (y
, 0));
1673 if (rtx_equal_for_memref_p (x0
, y0
))
1674 return (xsize
== 0 || ysize
== 0
1675 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1677 /* Can't properly adjust our sizes. */
1678 if (GET_CODE (x1
) != CONST_INT
)
1680 xsize
/= INTVAL (x1
);
1681 ysize
/= INTVAL (x1
);
1683 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
1687 /* Are these registers known not to be equal? */
1688 if (alias_invariant
)
1690 unsigned int r_x
= REGNO (x
), r_y
= REGNO (y
);
1691 rtx i_x
, i_y
; /* invariant relationships of X and Y */
1693 i_x
= r_x
>= reg_base_value_size
? 0 : alias_invariant
[r_x
];
1694 i_y
= r_y
>= reg_base_value_size
? 0 : alias_invariant
[r_y
];
1696 if (i_x
== 0 && i_y
== 0)
1699 if (! memrefs_conflict_p (xsize
, i_x
? i_x
: x
,
1700 ysize
, i_y
? i_y
: y
, c
))
1709 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1710 as an access with indeterminate size. Assume that references
1711 besides AND are aligned, so if the size of the other reference is
1712 at least as large as the alignment, assume no other overlap. */
1713 if (GET_CODE (x
) == AND
&& GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1715 if (GET_CODE (y
) == AND
|| ysize
< -INTVAL (XEXP (x
, 1)))
1717 return memrefs_conflict_p (xsize
, XEXP (x
, 0), ysize
, y
, c
);
1719 if (GET_CODE (y
) == AND
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
1721 /* ??? If we are indexing far enough into the array/structure, we
1722 may yet be able to determine that we can not overlap. But we
1723 also need to that we are far enough from the end not to overlap
1724 a following reference, so we do nothing with that for now. */
1725 if (GET_CODE (x
) == AND
|| xsize
< -INTVAL (XEXP (y
, 1)))
1727 return memrefs_conflict_p (xsize
, x
, ysize
, XEXP (y
, 0), c
);
1730 if (GET_CODE (x
) == ADDRESSOF
)
1732 if (y
== frame_pointer_rtx
1733 || GET_CODE (y
) == ADDRESSOF
)
1734 return xsize
<= 0 || ysize
<= 0;
1736 if (GET_CODE (y
) == ADDRESSOF
)
1738 if (x
== frame_pointer_rtx
)
1739 return xsize
<= 0 || ysize
<= 0;
1744 if (GET_CODE (x
) == CONST_INT
&& GET_CODE (y
) == CONST_INT
)
1746 c
+= (INTVAL (y
) - INTVAL (x
));
1747 return (xsize
<= 0 || ysize
<= 0
1748 || (c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0));
1751 if (GET_CODE (x
) == CONST
)
1753 if (GET_CODE (y
) == CONST
)
1754 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1755 ysize
, canon_rtx (XEXP (y
, 0)), c
);
1757 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
1760 if (GET_CODE (y
) == CONST
)
1761 return memrefs_conflict_p (xsize
, x
, ysize
,
1762 canon_rtx (XEXP (y
, 0)), c
);
1765 return (xsize
<= 0 || ysize
<= 0
1766 || (rtx_equal_for_memref_p (x
, y
)
1767 && ((c
>= 0 && xsize
> c
) || (c
< 0 && ysize
+c
> 0))));
1774 /* Functions to compute memory dependencies.
1776 Since we process the insns in execution order, we can build tables
1777 to keep track of what registers are fixed (and not aliased), what registers
1778 are varying in known ways, and what registers are varying in unknown
1781 If both memory references are volatile, then there must always be a
1782 dependence between the two references, since their order can not be
1783 changed. A volatile and non-volatile reference can be interchanged
1786 A MEM_IN_STRUCT reference at a non-AND varying address can never
1787 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1788 also must allow AND addresses, because they may generate accesses
1789 outside the object being referenced. This is used to generate
1790 aligned addresses from unaligned addresses, for instance, the alpha
1791 storeqi_unaligned pattern. */
1793 /* Read dependence: X is read after read in MEM takes place. There can
1794 only be a dependence here if both reads are volatile. */
1797 read_dependence (mem
, x
)
1801 return MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
);
1804 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1805 MEM2 is a reference to a structure at a varying address, or returns
1806 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1807 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1808 to decide whether or not an address may vary; it should return
1809 nonzero whenever variation is possible.
1810 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1813 fixed_scalar_and_varying_struct_p (mem1
, mem2
, mem1_addr
, mem2_addr
, varies_p
)
1815 rtx mem1_addr
, mem2_addr
;
1816 int (*varies_p
) PARAMS ((rtx
, int));
1818 if (! flag_strict_aliasing
)
1821 if (MEM_SCALAR_P (mem1
) && MEM_IN_STRUCT_P (mem2
)
1822 && !varies_p (mem1_addr
, 1) && varies_p (mem2_addr
, 1))
1823 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1827 if (MEM_IN_STRUCT_P (mem1
) && MEM_SCALAR_P (mem2
)
1828 && varies_p (mem1_addr
, 1) && !varies_p (mem2_addr
, 1))
1829 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1836 /* Returns nonzero if something about the mode or address format MEM1
1837 indicates that it might well alias *anything*. */
1840 aliases_everything_p (mem
)
1843 if (GET_CODE (XEXP (mem
, 0)) == AND
)
1844 /* If the address is an AND, its very hard to know at what it is
1845 actually pointing. */
1851 /* Return true if we can determine that the fields referenced cannot
1852 overlap for any pair of objects. */
1855 nonoverlapping_component_refs_p (x
, y
)
1858 tree fieldx
, fieldy
, typex
, typey
, orig_y
;
1862 /* The comparison has to be done at a common type, since we don't
1863 know how the inheritance hierarchy works. */
1867 fieldx
= TREE_OPERAND (x
, 1);
1868 typex
= DECL_FIELD_CONTEXT (fieldx
);
1873 fieldy
= TREE_OPERAND (y
, 1);
1874 typey
= DECL_FIELD_CONTEXT (fieldy
);
1879 y
= TREE_OPERAND (y
, 0);
1881 while (y
&& TREE_CODE (y
) == COMPONENT_REF
);
1883 x
= TREE_OPERAND (x
, 0);
1885 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1887 /* Never found a common type. */
1891 /* If we're left with accessing different fields of a structure,
1893 if (TREE_CODE (typex
) == RECORD_TYPE
1894 && fieldx
!= fieldy
)
1897 /* The comparison on the current field failed. If we're accessing
1898 a very nested structure, look at the next outer level. */
1899 x
= TREE_OPERAND (x
, 0);
1900 y
= TREE_OPERAND (y
, 0);
1903 && TREE_CODE (x
) == COMPONENT_REF
1904 && TREE_CODE (y
) == COMPONENT_REF
);
1909 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1912 decl_for_component_ref (x
)
1917 x
= TREE_OPERAND (x
, 0);
1919 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1921 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
1924 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1925 offset of the field reference. */
1928 adjust_offset_for_component_ref (x
, offset
)
1932 HOST_WIDE_INT ioffset
;
1937 ioffset
= INTVAL (offset
);
1940 tree field
= TREE_OPERAND (x
, 1);
1942 if (! host_integerp (DECL_FIELD_OFFSET (field
), 1))
1944 ioffset
+= (tree_low_cst (DECL_FIELD_OFFSET (field
), 1)
1945 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field
), 1)
1948 x
= TREE_OPERAND (x
, 0);
1950 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
1952 return GEN_INT (ioffset
);
1955 /* Return nonzero if we can deterimine the exprs corresponding to memrefs
1956 X and Y and they do not overlap. */
1959 nonoverlapping_memrefs_p (x
, y
)
1962 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
1965 rtx moffsetx
, moffsety
;
1966 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
1968 /* Unless both have exprs, we can't tell anything. */
1969 if (exprx
== 0 || expry
== 0)
1972 /* If both are field references, we may be able to determine something. */
1973 if (TREE_CODE (exprx
) == COMPONENT_REF
1974 && TREE_CODE (expry
) == COMPONENT_REF
1975 && nonoverlapping_component_refs_p (exprx
, expry
))
1978 /* If the field reference test failed, look at the DECLs involved. */
1979 moffsetx
= MEM_OFFSET (x
);
1980 if (TREE_CODE (exprx
) == COMPONENT_REF
)
1982 tree t
= decl_for_component_ref (exprx
);
1985 moffsetx
= adjust_offset_for_component_ref (exprx
, moffsetx
);
1988 else if (TREE_CODE (exprx
) == INDIRECT_REF
)
1990 exprx
= TREE_OPERAND (exprx
, 0);
1991 if (flag_argument_noalias
< 2
1992 || TREE_CODE (exprx
) != PARM_DECL
)
1996 moffsety
= MEM_OFFSET (y
);
1997 if (TREE_CODE (expry
) == COMPONENT_REF
)
1999 tree t
= decl_for_component_ref (expry
);
2002 moffsety
= adjust_offset_for_component_ref (expry
, moffsety
);
2005 else if (TREE_CODE (expry
) == INDIRECT_REF
)
2007 expry
= TREE_OPERAND (expry
, 0);
2008 if (flag_argument_noalias
< 2
2009 || TREE_CODE (expry
) != PARM_DECL
)
2013 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2016 rtlx
= DECL_RTL (exprx
);
2017 rtly
= DECL_RTL (expry
);
2019 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2020 can't overlap unless they are the same because we never reuse that part
2021 of the stack frame used for locals for spilled pseudos. */
2022 if ((GET_CODE (rtlx
) != MEM
|| GET_CODE (rtly
) != MEM
)
2023 && ! rtx_equal_p (rtlx
, rtly
))
2026 /* Get the base and offsets of both decls. If either is a register, we
2027 know both are and are the same, so use that as the base. The only
2028 we can avoid overlap is if we can deduce that they are nonoverlapping
2029 pieces of that decl, which is very rare. */
2030 basex
= GET_CODE (rtlx
) == MEM
? XEXP (rtlx
, 0) : rtlx
;
2031 if (GET_CODE (basex
) == PLUS
&& GET_CODE (XEXP (basex
, 1)) == CONST_INT
)
2032 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2034 basey
= GET_CODE (rtly
) == MEM
? XEXP (rtly
, 0) : rtly
;
2035 if (GET_CODE (basey
) == PLUS
&& GET_CODE (XEXP (basey
, 1)) == CONST_INT
)
2036 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2038 /* If the bases are different, we know they do not overlap if both
2039 are constants or if one is a constant and the other a pointer into the
2040 stack frame. Otherwise a different base means we can't tell if they
2042 if (! rtx_equal_p (basex
, basey
))
2043 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2044 || (CONSTANT_P (basex
) && REG_P (basey
)
2045 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2046 || (CONSTANT_P (basey
) && REG_P (basex
)
2047 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2049 sizex
= (GET_CODE (rtlx
) != MEM
? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2050 : MEM_SIZE (rtlx
) ? INTVAL (MEM_SIZE (rtlx
))
2052 sizey
= (GET_CODE (rtly
) != MEM
? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2053 : MEM_SIZE (rtly
) ? INTVAL (MEM_SIZE (rtly
)) :
2056 /* If we have an offset for either memref, it can update the values computed
2059 offsetx
+= INTVAL (moffsetx
), sizex
-= INTVAL (moffsetx
);
2061 offsety
+= INTVAL (moffsety
), sizey
-= INTVAL (moffsety
);
2063 /* If a memref has both a size and an offset, we can use the smaller size.
2064 We can't do this if the offset isn't known because we must view this
2065 memref as being anywhere inside the DECL's MEM. */
2066 if (MEM_SIZE (x
) && moffsetx
)
2067 sizex
= INTVAL (MEM_SIZE (x
));
2068 if (MEM_SIZE (y
) && moffsety
)
2069 sizey
= INTVAL (MEM_SIZE (y
));
2071 /* Put the values of the memref with the lower offset in X's values. */
2072 if (offsetx
> offsety
)
2074 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2075 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2078 /* If we don't know the size of the lower-offset value, we can't tell
2079 if they conflict. Otherwise, we do the test. */
2080 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2083 /* True dependence: X is read after store in MEM takes place. */
2086 true_dependence (mem
, mem_mode
, x
, varies
)
2088 enum machine_mode mem_mode
;
2090 int (*varies
) PARAMS ((rtx
, int));
2092 rtx x_addr
, mem_addr
;
2095 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2098 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2099 This is used in epilogue deallocation functions. */
2100 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2102 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2105 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2108 /* Unchanging memory can't conflict with non-unchanging memory.
2109 A non-unchanging read can conflict with a non-unchanging write.
2110 An unchanging read can conflict with an unchanging write since
2111 there may be a single store to this address to initialize it.
2112 Note that an unchanging store can conflict with a non-unchanging read
2113 since we have to make conservative assumptions when we have a
2114 record with readonly fields and we are copying the whole thing.
2115 Just fall through to the code below to resolve potential conflicts.
2116 This won't handle all cases optimally, but the possible performance
2117 loss should be negligible. */
2118 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
2121 if (nonoverlapping_memrefs_p (mem
, x
))
2124 if (mem_mode
== VOIDmode
)
2125 mem_mode
= GET_MODE (mem
);
2127 x_addr
= get_addr (XEXP (x
, 0));
2128 mem_addr
= get_addr (XEXP (mem
, 0));
2130 base
= find_base_term (x_addr
);
2131 if (base
&& (GET_CODE (base
) == LABEL_REF
2132 || (GET_CODE (base
) == SYMBOL_REF
2133 && CONSTANT_POOL_ADDRESS_P (base
))))
2136 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2139 x_addr
= canon_rtx (x_addr
);
2140 mem_addr
= canon_rtx (mem_addr
);
2142 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2143 SIZE_FOR_MODE (x
), x_addr
, 0))
2146 if (aliases_everything_p (x
))
2149 /* We cannot use aliases_everything_p to test MEM, since we must look
2150 at MEM_MODE, rather than GET_MODE (MEM). */
2151 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2154 /* In true_dependence we also allow BLKmode to alias anything. Why
2155 don't we do this in anti_dependence and output_dependence? */
2156 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2159 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2163 /* Canonical true dependence: X is read after store in MEM takes place.
2164 Variant of true_dependence which assumes MEM has already been
2165 canonicalized (hence we no longer do that here).
2166 The mem_addr argument has been added, since true_dependence computed
2167 this value prior to canonicalizing. */
2170 canon_true_dependence (mem
, mem_mode
, mem_addr
, x
, varies
)
2171 rtx mem
, mem_addr
, x
;
2172 enum machine_mode mem_mode
;
2173 int (*varies
) PARAMS ((rtx
, int));
2177 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2180 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2181 This is used in epilogue deallocation functions. */
2182 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2184 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2187 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2190 /* If X is an unchanging read, then it can't possibly conflict with any
2191 non-unchanging store. It may conflict with an unchanging write though,
2192 because there may be a single store to this address to initialize it.
2193 Just fall through to the code below to resolve the case where we have
2194 both an unchanging read and an unchanging write. This won't handle all
2195 cases optimally, but the possible performance loss should be
2197 if (RTX_UNCHANGING_P (x
) && ! RTX_UNCHANGING_P (mem
))
2200 if (nonoverlapping_memrefs_p (x
, mem
))
2203 x_addr
= get_addr (XEXP (x
, 0));
2205 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
), mem_mode
))
2208 x_addr
= canon_rtx (x_addr
);
2209 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2210 SIZE_FOR_MODE (x
), x_addr
, 0))
2213 if (aliases_everything_p (x
))
2216 /* We cannot use aliases_everything_p to test MEM, since we must look
2217 at MEM_MODE, rather than GET_MODE (MEM). */
2218 if (mem_mode
== QImode
|| GET_CODE (mem_addr
) == AND
)
2221 /* In true_dependence we also allow BLKmode to alias anything. Why
2222 don't we do this in anti_dependence and output_dependence? */
2223 if (mem_mode
== BLKmode
|| GET_MODE (x
) == BLKmode
)
2226 return ! fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2230 /* Returns nonzero if a write to X might alias a previous read from
2231 (or, if WRITEP is nonzero, a write to) MEM. */
2234 write_dependence_p (mem
, x
, writep
)
2239 rtx x_addr
, mem_addr
;
2243 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2246 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2247 This is used in epilogue deallocation functions. */
2248 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2250 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2253 if (DIFFERENT_ALIAS_SETS_P (x
, mem
))
2256 /* Unchanging memory can't conflict with non-unchanging memory. */
2257 if (RTX_UNCHANGING_P (x
) != RTX_UNCHANGING_P (mem
))
2260 /* If MEM is an unchanging read, then it can't possibly conflict with
2261 the store to X, because there is at most one store to MEM, and it must
2262 have occurred somewhere before MEM. */
2263 if (! writep
&& RTX_UNCHANGING_P (mem
))
2266 if (nonoverlapping_memrefs_p (x
, mem
))
2269 x_addr
= get_addr (XEXP (x
, 0));
2270 mem_addr
= get_addr (XEXP (mem
, 0));
2274 base
= find_base_term (mem_addr
);
2275 if (base
&& (GET_CODE (base
) == LABEL_REF
2276 || (GET_CODE (base
) == SYMBOL_REF
2277 && CONSTANT_POOL_ADDRESS_P (base
))))
2281 if (! base_alias_check (x_addr
, mem_addr
, GET_MODE (x
),
2285 x_addr
= canon_rtx (x_addr
);
2286 mem_addr
= canon_rtx (mem_addr
);
2288 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2289 SIZE_FOR_MODE (x
), x_addr
, 0))
2293 = fixed_scalar_and_varying_struct_p (mem
, x
, mem_addr
, x_addr
,
2296 return (!(fixed_scalar
== mem
&& !aliases_everything_p (x
))
2297 && !(fixed_scalar
== x
&& !aliases_everything_p (mem
)));
2300 /* Anti dependence: X is written after read in MEM takes place. */
2303 anti_dependence (mem
, x
)
2307 return write_dependence_p (mem
, x
, /*writep=*/0);
2310 /* Output dependence: X is written after store in MEM takes place. */
2313 output_dependence (mem
, x
)
2317 return write_dependence_p (mem
, x
, /*writep=*/1);
2320 /* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
2321 something which is not local to the function and is not constant. */
2324 nonlocal_mentioned_p_1 (loc
, data
)
2326 void *data ATTRIBUTE_UNUSED
;
2335 switch (GET_CODE (x
))
2338 if (GET_CODE (SUBREG_REG (x
)) == REG
)
2340 /* Global registers are not local. */
2341 if (REGNO (SUBREG_REG (x
)) < FIRST_PSEUDO_REGISTER
2342 && global_regs
[subreg_regno (x
)])
2350 /* Global registers are not local. */
2351 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2366 /* Constants in the function's constants pool are constant. */
2367 if (CONSTANT_POOL_ADDRESS_P (x
))
2372 /* Non-constant calls and recursion are not local. */
2376 /* Be overly conservative and consider any volatile memory
2377 reference as not local. */
2378 if (MEM_VOLATILE_P (x
))
2380 base
= find_base_term (XEXP (x
, 0));
2383 /* A Pmode ADDRESS could be a reference via the structure value
2384 address or static chain. Such memory references are nonlocal.
2386 Thus, we have to examine the contents of the ADDRESS to find
2387 out if this is a local reference or not. */
2388 if (GET_CODE (base
) == ADDRESS
2389 && GET_MODE (base
) == Pmode
2390 && (XEXP (base
, 0) == stack_pointer_rtx
2391 || XEXP (base
, 0) == arg_pointer_rtx
2392 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2393 || XEXP (base
, 0) == hard_frame_pointer_rtx
2395 || XEXP (base
, 0) == frame_pointer_rtx
))
2397 /* Constants in the function's constant pool are constant. */
2398 if (GET_CODE (base
) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (base
))
2403 case UNSPEC_VOLATILE
:
2408 if (MEM_VOLATILE_P (x
))
2420 /* Returns nonzero if X might mention something which is not
2421 local to the function and is not constant. */
2424 nonlocal_mentioned_p (x
)
2430 if (GET_CODE (x
) == CALL_INSN
)
2432 if (! CONST_OR_PURE_CALL_P (x
))
2434 x
= CALL_INSN_FUNCTION_USAGE (x
);
2442 return for_each_rtx (&x
, nonlocal_mentioned_p_1
, NULL
);
2445 /* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
2446 something which is not local to the function and is not constant. */
2449 nonlocal_referenced_p_1 (loc
, data
)
2451 void *data ATTRIBUTE_UNUSED
;
2458 switch (GET_CODE (x
))
2464 return nonlocal_mentioned_p (x
);
2467 /* Non-constant calls and recursion are not local. */
2471 if (nonlocal_mentioned_p (SET_SRC (x
)))
2474 if (GET_CODE (SET_DEST (x
)) == MEM
)
2475 return nonlocal_mentioned_p (XEXP (SET_DEST (x
), 0));
2477 /* If the destination is anything other than a CC0, PC,
2478 MEM, REG, or a SUBREG of a REG that occupies all of
2479 the REG, then X references nonlocal memory if it is
2480 mentioned in the destination. */
2481 if (GET_CODE (SET_DEST (x
)) != CC0
2482 && GET_CODE (SET_DEST (x
)) != PC
2483 && GET_CODE (SET_DEST (x
)) != REG
2484 && ! (GET_CODE (SET_DEST (x
)) == SUBREG
2485 && GET_CODE (SUBREG_REG (SET_DEST (x
))) == REG
2486 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x
))))
2487 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
)
2488 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x
)))
2489 + (UNITS_PER_WORD
- 1)) / UNITS_PER_WORD
))))
2490 return nonlocal_mentioned_p (SET_DEST (x
));
2494 if (GET_CODE (XEXP (x
, 0)) == MEM
)
2495 return nonlocal_mentioned_p (XEXP (XEXP (x
, 0), 0));
2499 return nonlocal_mentioned_p (XEXP (x
, 0));
2502 case UNSPEC_VOLATILE
:
2506 if (MEM_VOLATILE_P (x
))
2518 /* Returns nonzero if X might reference something which is not
2519 local to the function and is not constant. */
2522 nonlocal_referenced_p (x
)
2528 if (GET_CODE (x
) == CALL_INSN
)
2530 if (! CONST_OR_PURE_CALL_P (x
))
2532 x
= CALL_INSN_FUNCTION_USAGE (x
);
2540 return for_each_rtx (&x
, nonlocal_referenced_p_1
, NULL
);
2543 /* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
2544 something which is not local to the function and is not constant. */
2547 nonlocal_set_p_1 (loc
, data
)
2549 void *data ATTRIBUTE_UNUSED
;
2556 switch (GET_CODE (x
))
2559 /* Non-constant calls and recursion are not local. */
2568 return nonlocal_mentioned_p (XEXP (x
, 0));
2571 if (nonlocal_mentioned_p (SET_DEST (x
)))
2573 return nonlocal_set_p (SET_SRC (x
));
2576 return nonlocal_mentioned_p (XEXP (x
, 0));
2582 case UNSPEC_VOLATILE
:
2586 if (MEM_VOLATILE_P (x
))
2598 /* Returns nonzero if X might set something which is not
2599 local to the function and is not constant. */
2608 if (GET_CODE (x
) == CALL_INSN
)
2610 if (! CONST_OR_PURE_CALL_P (x
))
2612 x
= CALL_INSN_FUNCTION_USAGE (x
);
2620 return for_each_rtx (&x
, nonlocal_set_p_1
, NULL
);
2623 /* Mark the function if it is constant. */
2626 mark_constant_function ()
2629 int nonlocal_memory_referenced
;
2631 if (TREE_READONLY (current_function_decl
)
2632 || DECL_IS_PURE (current_function_decl
)
2633 || TREE_THIS_VOLATILE (current_function_decl
)
2634 || TYPE_MODE (TREE_TYPE (current_function_decl
)) == VOIDmode
2635 || current_function_has_nonlocal_goto
2636 || !(*targetm
.binds_local_p
) (current_function_decl
))
2639 /* A loop might not return which counts as a side effect. */
2640 if (mark_dfs_back_edges ())
2643 nonlocal_memory_referenced
= 0;
2645 init_alias_analysis ();
2647 /* Determine if this is a constant or pure function. */
2649 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2651 if (! INSN_P (insn
))
2654 if (nonlocal_set_p (insn
) || global_reg_mentioned_p (insn
)
2655 || volatile_refs_p (PATTERN (insn
)))
2658 if (! nonlocal_memory_referenced
)
2659 nonlocal_memory_referenced
= nonlocal_referenced_p (insn
);
2662 end_alias_analysis ();
2664 /* Mark the function. */
2668 else if (nonlocal_memory_referenced
)
2669 DECL_IS_PURE (current_function_decl
) = 1;
2671 TREE_READONLY (current_function_decl
) = 1;
2680 #ifndef OUTGOING_REGNO
2681 #define OUTGOING_REGNO(N) N
2683 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2684 /* Check whether this register can hold an incoming pointer
2685 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2686 numbers, so translate if necessary due to register windows. */
2687 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2688 && HARD_REGNO_MODE_OK (i
, Pmode
))
2689 static_reg_base_value
[i
]
2690 = gen_rtx_ADDRESS (VOIDmode
, gen_rtx_REG (Pmode
, i
));
2692 static_reg_base_value
[STACK_POINTER_REGNUM
]
2693 = gen_rtx_ADDRESS (Pmode
, stack_pointer_rtx
);
2694 static_reg_base_value
[ARG_POINTER_REGNUM
]
2695 = gen_rtx_ADDRESS (Pmode
, arg_pointer_rtx
);
2696 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2697 = gen_rtx_ADDRESS (Pmode
, frame_pointer_rtx
);
2698 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2699 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2700 = gen_rtx_ADDRESS (Pmode
, hard_frame_pointer_rtx
);
2703 alias_sets
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
2706 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2710 init_alias_analysis ()
2712 int maxreg
= max_reg_num ();
2718 reg_known_value_size
= maxreg
;
2721 = (rtx
*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (rtx
))
2722 - FIRST_PSEUDO_REGISTER
;
2724 = (char*) xcalloc ((maxreg
- FIRST_PSEUDO_REGISTER
), sizeof (char))
2725 - FIRST_PSEUDO_REGISTER
;
2727 /* Overallocate reg_base_value to allow some growth during loop
2728 optimization. Loop unrolling can create a large number of
2730 reg_base_value_size
= maxreg
* 2;
2731 reg_base_value
= (rtx
*) ggc_alloc_cleared (reg_base_value_size
2734 new_reg_base_value
= (rtx
*) xmalloc (reg_base_value_size
* sizeof (rtx
));
2735 reg_seen
= (char *) xmalloc (reg_base_value_size
);
2736 if (! reload_completed
&& flag_unroll_loops
)
2738 /* ??? Why are we realloc'ing if we're just going to zero it? */
2739 alias_invariant
= (rtx
*)xrealloc (alias_invariant
,
2740 reg_base_value_size
* sizeof (rtx
));
2741 memset ((char *)alias_invariant
, 0, reg_base_value_size
* sizeof (rtx
));
2744 /* The basic idea is that each pass through this loop will use the
2745 "constant" information from the previous pass to propagate alias
2746 information through another level of assignments.
2748 This could get expensive if the assignment chains are long. Maybe
2749 we should throttle the number of iterations, possibly based on
2750 the optimization level or flag_expensive_optimizations.
2752 We could propagate more information in the first pass by making use
2753 of REG_N_SETS to determine immediately that the alias information
2754 for a pseudo is "constant".
2756 A program with an uninitialized variable can cause an infinite loop
2757 here. Instead of doing a full dataflow analysis to detect such problems
2758 we just cap the number of iterations for the loop.
2760 The state of the arrays for the set chain in question does not matter
2761 since the program has undefined behavior. */
2766 /* Assume nothing will change this iteration of the loop. */
2769 /* We want to assign the same IDs each iteration of this loop, so
2770 start counting from zero each iteration of the loop. */
2773 /* We're at the start of the function each iteration through the
2774 loop, so we're copying arguments. */
2775 copying_arguments
= true;
2777 /* Wipe the potential alias information clean for this pass. */
2778 memset ((char *) new_reg_base_value
, 0, reg_base_value_size
* sizeof (rtx
));
2780 /* Wipe the reg_seen array clean. */
2781 memset ((char *) reg_seen
, 0, reg_base_value_size
);
2783 /* Mark all hard registers which may contain an address.
2784 The stack, frame and argument pointers may contain an address.
2785 An argument register which can hold a Pmode value may contain
2786 an address even if it is not in BASE_REGS.
2788 The address expression is VOIDmode for an argument and
2789 Pmode for other registers. */
2791 memcpy (new_reg_base_value
, static_reg_base_value
,
2792 FIRST_PSEUDO_REGISTER
* sizeof (rtx
));
2794 /* Walk the insns adding values to the new_reg_base_value array. */
2795 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2801 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2802 /* The prologue/epilogue insns are not threaded onto the
2803 insn chain until after reload has completed. Thus,
2804 there is no sense wasting time checking if INSN is in
2805 the prologue/epilogue until after reload has completed. */
2806 if (reload_completed
2807 && prologue_epilogue_contains (insn
))
2811 /* If this insn has a noalias note, process it, Otherwise,
2812 scan for sets. A simple set will have no side effects
2813 which could change the base value of any other register. */
2815 if (GET_CODE (PATTERN (insn
)) == SET
2816 && REG_NOTES (insn
) != 0
2817 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2818 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2820 note_stores (PATTERN (insn
), record_set
, NULL
);
2822 set
= single_set (insn
);
2825 && GET_CODE (SET_DEST (set
)) == REG
2826 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2828 unsigned int regno
= REGNO (SET_DEST (set
));
2829 rtx src
= SET_SRC (set
);
2831 if (REG_NOTES (insn
) != 0
2832 && (((note
= find_reg_note (insn
, REG_EQUAL
, 0)) != 0
2833 && REG_N_SETS (regno
) == 1)
2834 || (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != 0)
2835 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2836 && ! rtx_varies_p (XEXP (note
, 0), 1)
2837 && ! reg_overlap_mentioned_p (SET_DEST (set
), XEXP (note
, 0)))
2839 reg_known_value
[regno
] = XEXP (note
, 0);
2840 reg_known_equiv_p
[regno
] = REG_NOTE_KIND (note
) == REG_EQUIV
;
2842 else if (REG_N_SETS (regno
) == 1
2843 && GET_CODE (src
) == PLUS
2844 && GET_CODE (XEXP (src
, 0)) == REG
2845 && REGNO (XEXP (src
, 0)) >= FIRST_PSEUDO_REGISTER
2846 && (reg_known_value
[REGNO (XEXP (src
, 0))])
2847 && GET_CODE (XEXP (src
, 1)) == CONST_INT
)
2849 rtx op0
= XEXP (src
, 0);
2850 op0
= reg_known_value
[REGNO (op0
)];
2851 reg_known_value
[regno
]
2852 = plus_constant (op0
, INTVAL (XEXP (src
, 1)));
2853 reg_known_equiv_p
[regno
] = 0;
2855 else if (REG_N_SETS (regno
) == 1
2856 && ! rtx_varies_p (src
, 1))
2858 reg_known_value
[regno
] = src
;
2859 reg_known_equiv_p
[regno
] = 0;
2863 else if (GET_CODE (insn
) == NOTE
2864 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_FUNCTION_BEG
)
2865 copying_arguments
= false;
2868 /* Now propagate values from new_reg_base_value to reg_base_value. */
2869 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2871 if (new_reg_base_value
[ui
]
2872 && new_reg_base_value
[ui
] != reg_base_value
[ui
]
2873 && ! rtx_equal_p (new_reg_base_value
[ui
], reg_base_value
[ui
]))
2875 reg_base_value
[ui
] = new_reg_base_value
[ui
];
2880 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
2882 /* Fill in the remaining entries. */
2883 for (i
= FIRST_PSEUDO_REGISTER
; i
< maxreg
; i
++)
2884 if (reg_known_value
[i
] == 0)
2885 reg_known_value
[i
] = regno_reg_rtx
[i
];
2887 /* Simplify the reg_base_value array so that no register refers to
2888 another register, except to special registers indirectly through
2889 ADDRESS expressions.
2891 In theory this loop can take as long as O(registers^2), but unless
2892 there are very long dependency chains it will run in close to linear
2895 This loop may not be needed any longer now that the main loop does
2896 a better job at propagating alias information. */
2902 for (ui
= 0; ui
< reg_base_value_size
; ui
++)
2904 rtx base
= reg_base_value
[ui
];
2905 if (base
&& GET_CODE (base
) == REG
)
2907 unsigned int base_regno
= REGNO (base
);
2908 if (base_regno
== ui
) /* register set from itself */
2909 reg_base_value
[ui
] = 0;
2911 reg_base_value
[ui
] = reg_base_value
[base_regno
];
2916 while (changed
&& pass
< MAX_ALIAS_LOOP_PASSES
);
2919 free (new_reg_base_value
);
2920 new_reg_base_value
= 0;
2926 end_alias_analysis ()
2928 free (reg_known_value
+ FIRST_PSEUDO_REGISTER
);
2929 reg_known_value
= 0;
2930 reg_known_value_size
= 0;
2931 free (reg_known_equiv_p
+ FIRST_PSEUDO_REGISTER
);
2932 reg_known_equiv_p
= 0;
2934 reg_base_value_size
= 0;
2935 if (alias_invariant
)
2937 free (alias_invariant
);
2938 alias_invariant
= 0;
2942 #include "gt-alias.h"