Daily bump.
[official-gcc.git] / gcc / alias.c
blobbd5c277f05aa73c39658775e60d093315b820597
1 /* Alias analysis for GNU C
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
3 2007 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 3, or (at your option) any later
11 version.
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
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "tm_p.h"
29 #include "function.h"
30 #include "alias.h"
31 #include "emit-rtl.h"
32 #include "regs.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "flags.h"
36 #include "output.h"
37 #include "toplev.h"
38 #include "cselib.h"
39 #include "splay-tree.h"
40 #include "ggc.h"
41 #include "langhooks.h"
42 #include "timevar.h"
43 #include "target.h"
44 #include "cgraph.h"
45 #include "varray.h"
46 #include "tree-pass.h"
47 #include "ipa-type-escape.h"
48 #include "df.h"
50 /* The aliasing API provided here solves related but different problems:
52 Say there exists (in c)
54 struct X {
55 struct Y y1;
56 struct Z z2;
57 } x1, *px1, *px2;
59 struct Y y2, *py;
60 struct Z z2, *pz;
63 py = &px1.y1;
64 px2 = &x1;
66 Consider the four questions:
68 Can a store to x1 interfere with px2->y1?
69 Can a store to x1 interfere with px2->z2?
70 (*px2).z2
71 Can a store to x1 change the value pointed to by with py?
72 Can a store to x1 change the value pointed to by with pz?
74 The answer to these questions can be yes, yes, yes, and maybe.
76 The first two questions can be answered with a simple examination
77 of the type system. If structure X contains a field of type Y then
78 a store thru a pointer to an X can overwrite any field that is
79 contained (recursively) in an X (unless we know that px1 != px2).
81 The last two of the questions can be solved in the same way as the
82 first two questions but this is too conservative. The observation
83 is that in some cases analysis we can know if which (if any) fields
84 are addressed and if those addresses are used in bad ways. This
85 analysis may be language specific. In C, arbitrary operations may
86 be applied to pointers. However, there is some indication that
87 this may be too conservative for some C++ types.
89 The pass ipa-type-escape does this analysis for the types whose
90 instances do not escape across the compilation boundary.
92 Historically in GCC, these two problems were combined and a single
93 data structure was used to represent the solution to these
94 problems. We now have two similar but different data structures,
95 The data structure to solve the last two question is similar to the
96 first, but does not contain have the fields in it whose address are
97 never taken. For types that do escape the compilation unit, the
98 data structures will have identical information.
101 /* The alias sets assigned to MEMs assist the back-end in determining
102 which MEMs can alias which other MEMs. In general, two MEMs in
103 different alias sets cannot alias each other, with one important
104 exception. Consider something like:
106 struct S { int i; double d; };
108 a store to an `S' can alias something of either type `int' or type
109 `double'. (However, a store to an `int' cannot alias a `double'
110 and vice versa.) We indicate this via a tree structure that looks
111 like:
112 struct S
115 |/_ _\|
116 int double
118 (The arrows are directed and point downwards.)
119 In this situation we say the alias set for `struct S' is the
120 `superset' and that those for `int' and `double' are `subsets'.
122 To see whether two alias sets can point to the same memory, we must
123 see if either alias set is a subset of the other. We need not trace
124 past immediate descendants, however, since we propagate all
125 grandchildren up one level.
127 Alias set zero is implicitly a superset of all other alias sets.
128 However, this is no actual entry for alias set zero. It is an
129 error to attempt to explicitly construct a subset of zero. */
131 struct alias_set_entry GTY(())
133 /* The alias set number, as stored in MEM_ALIAS_SET. */
134 alias_set_type alias_set;
136 /* The children of the alias set. These are not just the immediate
137 children, but, in fact, all descendants. So, if we have:
139 struct T { struct S s; float f; }
141 continuing our example above, the children here will be all of
142 `int', `double', `float', and `struct S'. */
143 splay_tree GTY((param1_is (int), param2_is (int))) children;
145 /* Nonzero if would have a child of zero: this effectively makes this
146 alias set the same as alias set zero. */
147 int has_zero_child;
149 typedef struct alias_set_entry *alias_set_entry;
151 static int rtx_equal_for_memref_p (const_rtx, const_rtx);
152 static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
153 static void record_set (rtx, const_rtx, void *);
154 static int base_alias_check (rtx, rtx, enum machine_mode,
155 enum machine_mode);
156 static rtx find_base_value (rtx);
157 static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
158 static int insert_subset_children (splay_tree_node, void*);
159 static tree find_base_decl (tree);
160 static alias_set_entry get_alias_set_entry (alias_set_type);
161 static const_rtx fixed_scalar_and_varying_struct_p (const_rtx, const_rtx, rtx, rtx,
162 bool (*) (const_rtx, bool));
163 static int aliases_everything_p (const_rtx);
164 static bool nonoverlapping_component_refs_p (const_tree, const_tree);
165 static tree decl_for_component_ref (tree);
166 static rtx adjust_offset_for_component_ref (tree, rtx);
167 static int nonoverlapping_memrefs_p (const_rtx, const_rtx);
168 static int write_dependence_p (const_rtx, const_rtx, int);
170 static void memory_modified_1 (rtx, const_rtx, void *);
171 static void record_alias_subset (alias_set_type, alias_set_type);
173 /* Set up all info needed to perform alias analysis on memory references. */
175 /* Returns the size in bytes of the mode of X. */
176 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
178 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
179 different alias sets. We ignore alias sets in functions making use
180 of variable arguments because the va_arg macros on some systems are
181 not legal ANSI C. */
182 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
183 mems_in_disjoint_alias_sets_p (MEM1, MEM2)
185 /* Cap the number of passes we make over the insns propagating alias
186 information through set chains. 10 is a completely arbitrary choice. */
187 #define MAX_ALIAS_LOOP_PASSES 10
189 /* reg_base_value[N] gives an address to which register N is related.
190 If all sets after the first add or subtract to the current value
191 or otherwise modify it so it does not point to a different top level
192 object, reg_base_value[N] is equal to the address part of the source
193 of the first set.
195 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
196 expressions represent certain special values: function arguments and
197 the stack, frame, and argument pointers.
199 The contents of an ADDRESS is not normally used, the mode of the
200 ADDRESS determines whether the ADDRESS is a function argument or some
201 other special value. Pointer equality, not rtx_equal_p, determines whether
202 two ADDRESS expressions refer to the same base address.
204 The only use of the contents of an ADDRESS is for determining if the
205 current function performs nonlocal memory memory references for the
206 purposes of marking the function as a constant function. */
208 static GTY(()) VEC(rtx,gc) *reg_base_value;
209 static rtx *new_reg_base_value;
211 /* We preserve the copy of old array around to avoid amount of garbage
212 produced. About 8% of garbage produced were attributed to this
213 array. */
214 static GTY((deletable)) VEC(rtx,gc) *old_reg_base_value;
216 /* Static hunks of RTL used by the aliasing code; these are initialized
217 once per function to avoid unnecessary RTL allocations. */
218 static GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER];
220 #define REG_BASE_VALUE(X) \
221 (REGNO (X) < VEC_length (rtx, reg_base_value) \
222 ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
224 /* Vector indexed by N giving the initial (unchanging) value known for
225 pseudo-register N. This array is initialized in init_alias_analysis,
226 and does not change until end_alias_analysis is called. */
227 static GTY((length("reg_known_value_size"))) rtx *reg_known_value;
229 /* Indicates number of valid entries in reg_known_value. */
230 static GTY(()) unsigned int reg_known_value_size;
232 /* Vector recording for each reg_known_value whether it is due to a
233 REG_EQUIV note. Future passes (viz., reload) may replace the
234 pseudo with the equivalent expression and so we account for the
235 dependences that would be introduced if that happens.
237 The REG_EQUIV notes created in assign_parms may mention the arg
238 pointer, and there are explicit insns in the RTL that modify the
239 arg pointer. Thus we must ensure that such insns don't get
240 scheduled across each other because that would invalidate the
241 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
242 wrong, but solving the problem in the scheduler will likely give
243 better code, so we do it here. */
244 static bool *reg_known_equiv_p;
246 /* True when scanning insns from the start of the rtl to the
247 NOTE_INSN_FUNCTION_BEG note. */
248 static bool copying_arguments;
250 DEF_VEC_P(alias_set_entry);
251 DEF_VEC_ALLOC_P(alias_set_entry,gc);
253 /* The splay-tree used to store the various alias set entries. */
254 static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
256 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
257 such an entry, or NULL otherwise. */
259 static inline alias_set_entry
260 get_alias_set_entry (alias_set_type alias_set)
262 return VEC_index (alias_set_entry, alias_sets, alias_set);
265 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
266 the two MEMs cannot alias each other. */
268 static inline int
269 mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
271 /* Perform a basic sanity check. Namely, that there are no alias sets
272 if we're not using strict aliasing. This helps to catch bugs
273 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
274 where a MEM is allocated in some way other than by the use of
275 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
276 use alias sets to indicate that spilled registers cannot alias each
277 other, we might need to remove this check. */
278 gcc_assert (flag_strict_aliasing
279 || (!MEM_ALIAS_SET (mem1) && !MEM_ALIAS_SET (mem2)));
281 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
284 /* Insert the NODE into the splay tree given by DATA. Used by
285 record_alias_subset via splay_tree_foreach. */
287 static int
288 insert_subset_children (splay_tree_node node, void *data)
290 splay_tree_insert ((splay_tree) data, node->key, node->value);
292 return 0;
295 /* Return true if the first alias set is a subset of the second. */
297 bool
298 alias_set_subset_of (alias_set_type set1, alias_set_type set2)
300 alias_set_entry ase;
302 /* Everything is a subset of the "aliases everything" set. */
303 if (set2 == 0)
304 return true;
306 /* Otherwise, check if set1 is a subset of set2. */
307 ase = get_alias_set_entry (set2);
308 if (ase != 0
309 && (splay_tree_lookup (ase->children,
310 (splay_tree_key) set1)))
311 return true;
312 return false;
315 /* Return 1 if the two specified alias sets may conflict. */
318 alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
320 alias_set_entry ase;
322 /* The easy case. */
323 if (alias_sets_must_conflict_p (set1, set2))
324 return 1;
326 /* See if the first alias set is a subset of the second. */
327 ase = get_alias_set_entry (set1);
328 if (ase != 0
329 && (ase->has_zero_child
330 || splay_tree_lookup (ase->children,
331 (splay_tree_key) set2)))
332 return 1;
334 /* Now do the same, but with the alias sets reversed. */
335 ase = get_alias_set_entry (set2);
336 if (ase != 0
337 && (ase->has_zero_child
338 || splay_tree_lookup (ase->children,
339 (splay_tree_key) set1)))
340 return 1;
342 /* The two alias sets are distinct and neither one is the
343 child of the other. Therefore, they cannot conflict. */
344 return 0;
347 /* Return 1 if the two specified alias sets will always conflict. */
350 alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
352 if (set1 == 0 || set2 == 0 || set1 == set2)
353 return 1;
355 return 0;
358 /* Return 1 if any MEM object of type T1 will always conflict (using the
359 dependency routines in this file) with any MEM object of type T2.
360 This is used when allocating temporary storage. If T1 and/or T2 are
361 NULL_TREE, it means we know nothing about the storage. */
364 objects_must_conflict_p (tree t1, tree t2)
366 alias_set_type set1, set2;
368 /* If neither has a type specified, we don't know if they'll conflict
369 because we may be using them to store objects of various types, for
370 example the argument and local variables areas of inlined functions. */
371 if (t1 == 0 && t2 == 0)
372 return 0;
374 /* If they are the same type, they must conflict. */
375 if (t1 == t2
376 /* Likewise if both are volatile. */
377 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
378 return 1;
380 set1 = t1 ? get_alias_set (t1) : 0;
381 set2 = t2 ? get_alias_set (t2) : 0;
383 /* We can't use alias_sets_conflict_p because we must make sure
384 that every subtype of t1 will conflict with every subtype of
385 t2 for which a pair of subobjects of these respective subtypes
386 overlaps on the stack. */
387 return alias_sets_must_conflict_p (set1, set2);
390 /* T is an expression with pointer type. Find the DECL on which this
391 expression is based. (For example, in `a[i]' this would be `a'.)
392 If there is no such DECL, or a unique decl cannot be determined,
393 NULL_TREE is returned. */
395 static tree
396 find_base_decl (tree t)
398 tree d0, d1;
400 if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
401 return 0;
403 /* If this is a declaration, return it. If T is based on a restrict
404 qualified decl, return that decl. */
405 if (DECL_P (t))
407 if (TREE_CODE (t) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (t))
408 t = DECL_GET_RESTRICT_BASE (t);
409 return t;
412 /* Handle general expressions. It would be nice to deal with
413 COMPONENT_REFs here. If we could tell that `a' and `b' were the
414 same, then `a->f' and `b->f' are also the same. */
415 switch (TREE_CODE_CLASS (TREE_CODE (t)))
417 case tcc_unary:
418 return find_base_decl (TREE_OPERAND (t, 0));
420 case tcc_binary:
421 /* Return 0 if found in neither or both are the same. */
422 d0 = find_base_decl (TREE_OPERAND (t, 0));
423 d1 = find_base_decl (TREE_OPERAND (t, 1));
424 if (d0 == d1)
425 return d0;
426 else if (d0 == 0)
427 return d1;
428 else if (d1 == 0)
429 return d0;
430 else
431 return 0;
433 default:
434 return 0;
438 /* Return true if all nested component references handled by
439 get_inner_reference in T are such that we should use the alias set
440 provided by the object at the heart of T.
442 This is true for non-addressable components (which don't have their
443 own alias set), as well as components of objects in alias set zero.
444 This later point is a special case wherein we wish to override the
445 alias set used by the component, but we don't have per-FIELD_DECL
446 assignable alias sets. */
448 bool
449 component_uses_parent_alias_set (const_tree t)
451 while (1)
453 /* If we're at the end, it vacuously uses its own alias set. */
454 if (!handled_component_p (t))
455 return false;
457 switch (TREE_CODE (t))
459 case COMPONENT_REF:
460 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
461 return true;
462 break;
464 case ARRAY_REF:
465 case ARRAY_RANGE_REF:
466 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
467 return true;
468 break;
470 case REALPART_EXPR:
471 case IMAGPART_EXPR:
472 break;
474 default:
475 /* Bitfields and casts are never addressable. */
476 return true;
479 t = TREE_OPERAND (t, 0);
480 if (get_alias_set (TREE_TYPE (t)) == 0)
481 return true;
485 /* Return the alias set for T, which may be either a type or an
486 expression. Call language-specific routine for help, if needed. */
488 alias_set_type
489 get_alias_set (tree t)
491 alias_set_type set;
493 /* If we're not doing any alias analysis, just assume everything
494 aliases everything else. Also return 0 if this or its type is
495 an error. */
496 if (! flag_strict_aliasing || t == error_mark_node
497 || (! TYPE_P (t)
498 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
499 return 0;
501 /* We can be passed either an expression or a type. This and the
502 language-specific routine may make mutually-recursive calls to each other
503 to figure out what to do. At each juncture, we see if this is a tree
504 that the language may need to handle specially. First handle things that
505 aren't types. */
506 if (! TYPE_P (t))
508 tree inner = t;
510 /* Remove any nops, then give the language a chance to do
511 something with this tree before we look at it. */
512 STRIP_NOPS (t);
513 set = lang_hooks.get_alias_set (t);
514 if (set != -1)
515 return set;
517 /* First see if the actual object referenced is an INDIRECT_REF from a
518 restrict-qualified pointer or a "void *". */
519 while (handled_component_p (inner))
521 inner = TREE_OPERAND (inner, 0);
522 STRIP_NOPS (inner);
525 /* Check for accesses through restrict-qualified pointers. */
526 if (INDIRECT_REF_P (inner))
528 tree decl;
530 if (TREE_CODE (TREE_OPERAND (inner, 0)) == SSA_NAME)
531 decl = SSA_NAME_VAR (TREE_OPERAND (inner, 0));
532 else
533 decl = find_base_decl (TREE_OPERAND (inner, 0));
535 if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
537 /* If we haven't computed the actual alias set, do it now. */
538 if (DECL_POINTER_ALIAS_SET (decl) == -2)
540 tree pointed_to_type = TREE_TYPE (TREE_TYPE (decl));
542 /* No two restricted pointers can point at the same thing.
543 However, a restricted pointer can point at the same thing
544 as an unrestricted pointer, if that unrestricted pointer
545 is based on the restricted pointer. So, we make the
546 alias set for the restricted pointer a subset of the
547 alias set for the type pointed to by the type of the
548 decl. */
549 alias_set_type pointed_to_alias_set
550 = get_alias_set (pointed_to_type);
552 if (pointed_to_alias_set == 0)
553 /* It's not legal to make a subset of alias set zero. */
554 DECL_POINTER_ALIAS_SET (decl) = 0;
555 else if (AGGREGATE_TYPE_P (pointed_to_type))
556 /* For an aggregate, we must treat the restricted
557 pointer the same as an ordinary pointer. If we
558 were to make the type pointed to by the
559 restricted pointer a subset of the pointed-to
560 type, then we would believe that other subsets
561 of the pointed-to type (such as fields of that
562 type) do not conflict with the type pointed to
563 by the restricted pointer. */
564 DECL_POINTER_ALIAS_SET (decl)
565 = pointed_to_alias_set;
566 else
568 DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
569 record_alias_subset (pointed_to_alias_set,
570 DECL_POINTER_ALIAS_SET (decl));
574 /* We use the alias set indicated in the declaration. */
575 return DECL_POINTER_ALIAS_SET (decl);
578 /* If we have an INDIRECT_REF via a void pointer, we don't
579 know anything about what that might alias. Likewise if the
580 pointer is marked that way. */
581 else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE
582 || (TYPE_REF_CAN_ALIAS_ALL
583 (TREE_TYPE (TREE_OPERAND (inner, 0)))))
584 return 0;
587 /* For non-addressable fields we return the alias set of the
588 outermost object that could have its address taken. If this
589 is an SFT use the precomputed value. */
590 if (TREE_CODE (t) == STRUCT_FIELD_TAG
591 && SFT_NONADDRESSABLE_P (t))
592 return SFT_ALIAS_SET (t);
594 /* Otherwise, pick up the outermost object that we could have a pointer
595 to, processing conversions as above. */
596 while (component_uses_parent_alias_set (t))
598 t = TREE_OPERAND (t, 0);
599 STRIP_NOPS (t);
602 /* If we've already determined the alias set for a decl, just return
603 it. This is necessary for C++ anonymous unions, whose component
604 variables don't look like union members (boo!). */
605 if (TREE_CODE (t) == VAR_DECL
606 && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
607 return MEM_ALIAS_SET (DECL_RTL (t));
609 /* Now all we care about is the type. */
610 t = TREE_TYPE (t);
613 /* Variant qualifiers don't affect the alias set, so get the main
614 variant. If this is a type with a known alias set, return it. */
615 t = TYPE_MAIN_VARIANT (t);
616 if (TYPE_ALIAS_SET_KNOWN_P (t))
617 return TYPE_ALIAS_SET (t);
619 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
620 if (!COMPLETE_TYPE_P (t))
622 /* For arrays with unknown size the conservative answer is the
623 alias set of the element type. */
624 if (TREE_CODE (t) == ARRAY_TYPE)
625 return get_alias_set (TREE_TYPE (t));
627 /* But return zero as a conservative answer for incomplete types. */
628 return 0;
631 /* See if the language has special handling for this type. */
632 set = lang_hooks.get_alias_set (t);
633 if (set != -1)
634 return set;
636 /* There are no objects of FUNCTION_TYPE, so there's no point in
637 using up an alias set for them. (There are, of course, pointers
638 and references to functions, but that's different.) */
639 else if (TREE_CODE (t) == FUNCTION_TYPE
640 || TREE_CODE (t) == METHOD_TYPE)
641 set = 0;
643 /* Unless the language specifies otherwise, let vector types alias
644 their components. This avoids some nasty type punning issues in
645 normal usage. And indeed lets vectors be treated more like an
646 array slice. */
647 else if (TREE_CODE (t) == VECTOR_TYPE)
648 set = get_alias_set (TREE_TYPE (t));
650 else
651 /* Otherwise make a new alias set for this type. */
652 set = new_alias_set ();
654 TYPE_ALIAS_SET (t) = set;
656 /* If this is an aggregate type, we must record any component aliasing
657 information. */
658 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
659 record_component_aliases (t);
661 return set;
664 /* Return a brand-new alias set. */
666 alias_set_type
667 new_alias_set (void)
669 if (flag_strict_aliasing)
671 if (alias_sets == 0)
672 VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
673 VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
674 return VEC_length (alias_set_entry, alias_sets) - 1;
676 else
677 return 0;
680 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
681 not everything that aliases SUPERSET also aliases SUBSET. For example,
682 in C, a store to an `int' can alias a load of a structure containing an
683 `int', and vice versa. But it can't alias a load of a 'double' member
684 of the same structure. Here, the structure would be the SUPERSET and
685 `int' the SUBSET. This relationship is also described in the comment at
686 the beginning of this file.
688 This function should be called only once per SUPERSET/SUBSET pair.
690 It is illegal for SUPERSET to be zero; everything is implicitly a
691 subset of alias set zero. */
693 static void
694 record_alias_subset (alias_set_type superset, alias_set_type subset)
696 alias_set_entry superset_entry;
697 alias_set_entry subset_entry;
699 /* It is possible in complex type situations for both sets to be the same,
700 in which case we can ignore this operation. */
701 if (superset == subset)
702 return;
704 gcc_assert (superset);
706 superset_entry = get_alias_set_entry (superset);
707 if (superset_entry == 0)
709 /* Create an entry for the SUPERSET, so that we have a place to
710 attach the SUBSET. */
711 superset_entry = ggc_alloc (sizeof (struct alias_set_entry));
712 superset_entry->alias_set = superset;
713 superset_entry->children
714 = splay_tree_new_ggc (splay_tree_compare_ints);
715 superset_entry->has_zero_child = 0;
716 VEC_replace (alias_set_entry, alias_sets, superset, superset_entry);
719 if (subset == 0)
720 superset_entry->has_zero_child = 1;
721 else
723 subset_entry = get_alias_set_entry (subset);
724 /* If there is an entry for the subset, enter all of its children
725 (if they are not already present) as children of the SUPERSET. */
726 if (subset_entry)
728 if (subset_entry->has_zero_child)
729 superset_entry->has_zero_child = 1;
731 splay_tree_foreach (subset_entry->children, insert_subset_children,
732 superset_entry->children);
735 /* Enter the SUBSET itself as a child of the SUPERSET. */
736 splay_tree_insert (superset_entry->children,
737 (splay_tree_key) subset, 0);
741 /* Record that component types of TYPE, if any, are part of that type for
742 aliasing purposes. For record types, we only record component types
743 for fields that are marked addressable. For array types, we always
744 record the component types, so the front end should not call this
745 function if the individual component aren't addressable. */
747 void
748 record_component_aliases (tree type)
750 alias_set_type superset = get_alias_set (type);
751 tree field;
753 if (superset == 0)
754 return;
756 switch (TREE_CODE (type))
758 case ARRAY_TYPE:
759 if (! TYPE_NONALIASED_COMPONENT (type))
760 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
761 break;
763 case RECORD_TYPE:
764 case UNION_TYPE:
765 case QUAL_UNION_TYPE:
766 /* Recursively record aliases for the base classes, if there are any. */
767 if (TYPE_BINFO (type))
769 int i;
770 tree binfo, base_binfo;
772 for (binfo = TYPE_BINFO (type), i = 0;
773 BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
774 record_alias_subset (superset,
775 get_alias_set (BINFO_TYPE (base_binfo)));
777 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
778 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
779 record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
780 break;
782 case COMPLEX_TYPE:
783 record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
784 break;
786 default:
787 break;
791 /* Allocate an alias set for use in storing and reading from the varargs
792 spill area. */
794 static GTY(()) alias_set_type varargs_set = -1;
796 alias_set_type
797 get_varargs_alias_set (void)
799 #if 1
800 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
801 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
802 consistently use the varargs alias set for loads from the varargs
803 area. So don't use it anywhere. */
804 return 0;
805 #else
806 if (varargs_set == -1)
807 varargs_set = new_alias_set ();
809 return varargs_set;
810 #endif
813 /* Likewise, but used for the fixed portions of the frame, e.g., register
814 save areas. */
816 static GTY(()) alias_set_type frame_set = -1;
818 alias_set_type
819 get_frame_alias_set (void)
821 if (frame_set == -1)
822 frame_set = new_alias_set ();
824 return frame_set;
827 /* Inside SRC, the source of a SET, find a base address. */
829 static rtx
830 find_base_value (rtx src)
832 unsigned int regno;
834 switch (GET_CODE (src))
836 case SYMBOL_REF:
837 case LABEL_REF:
838 return src;
840 case REG:
841 regno = REGNO (src);
842 /* At the start of a function, argument registers have known base
843 values which may be lost later. Returning an ADDRESS
844 expression here allows optimization based on argument values
845 even when the argument registers are used for other purposes. */
846 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
847 return new_reg_base_value[regno];
849 /* If a pseudo has a known base value, return it. Do not do this
850 for non-fixed hard regs since it can result in a circular
851 dependency chain for registers which have values at function entry.
853 The test above is not sufficient because the scheduler may move
854 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
855 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
856 && regno < VEC_length (rtx, reg_base_value))
858 /* If we're inside init_alias_analysis, use new_reg_base_value
859 to reduce the number of relaxation iterations. */
860 if (new_reg_base_value && new_reg_base_value[regno]
861 && DF_REG_DEF_COUNT (regno) == 1)
862 return new_reg_base_value[regno];
864 if (VEC_index (rtx, reg_base_value, regno))
865 return VEC_index (rtx, reg_base_value, regno);
868 return 0;
870 case MEM:
871 /* Check for an argument passed in memory. Only record in the
872 copying-arguments block; it is too hard to track changes
873 otherwise. */
874 if (copying_arguments
875 && (XEXP (src, 0) == arg_pointer_rtx
876 || (GET_CODE (XEXP (src, 0)) == PLUS
877 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
878 return gen_rtx_ADDRESS (VOIDmode, src);
879 return 0;
881 case CONST:
882 src = XEXP (src, 0);
883 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
884 break;
886 /* ... fall through ... */
888 case PLUS:
889 case MINUS:
891 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
893 /* If either operand is a REG that is a known pointer, then it
894 is the base. */
895 if (REG_P (src_0) && REG_POINTER (src_0))
896 return find_base_value (src_0);
897 if (REG_P (src_1) && REG_POINTER (src_1))
898 return find_base_value (src_1);
900 /* If either operand is a REG, then see if we already have
901 a known value for it. */
902 if (REG_P (src_0))
904 temp = find_base_value (src_0);
905 if (temp != 0)
906 src_0 = temp;
909 if (REG_P (src_1))
911 temp = find_base_value (src_1);
912 if (temp!= 0)
913 src_1 = temp;
916 /* If either base is named object or a special address
917 (like an argument or stack reference), then use it for the
918 base term. */
919 if (src_0 != 0
920 && (GET_CODE (src_0) == SYMBOL_REF
921 || GET_CODE (src_0) == LABEL_REF
922 || (GET_CODE (src_0) == ADDRESS
923 && GET_MODE (src_0) != VOIDmode)))
924 return src_0;
926 if (src_1 != 0
927 && (GET_CODE (src_1) == SYMBOL_REF
928 || GET_CODE (src_1) == LABEL_REF
929 || (GET_CODE (src_1) == ADDRESS
930 && GET_MODE (src_1) != VOIDmode)))
931 return src_1;
933 /* Guess which operand is the base address:
934 If either operand is a symbol, then it is the base. If
935 either operand is a CONST_INT, then the other is the base. */
936 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
937 return find_base_value (src_0);
938 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
939 return find_base_value (src_1);
941 return 0;
944 case LO_SUM:
945 /* The standard form is (lo_sum reg sym) so look only at the
946 second operand. */
947 return find_base_value (XEXP (src, 1));
949 case AND:
950 /* If the second operand is constant set the base
951 address to the first operand. */
952 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
953 return find_base_value (XEXP (src, 0));
954 return 0;
956 case TRUNCATE:
957 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
958 break;
959 /* Fall through. */
960 case HIGH:
961 case PRE_INC:
962 case PRE_DEC:
963 case POST_INC:
964 case POST_DEC:
965 case PRE_MODIFY:
966 case POST_MODIFY:
967 return find_base_value (XEXP (src, 0));
969 case ZERO_EXTEND:
970 case SIGN_EXTEND: /* used for NT/Alpha pointers */
972 rtx temp = find_base_value (XEXP (src, 0));
974 if (temp != 0 && CONSTANT_P (temp))
975 temp = convert_memory_address (Pmode, temp);
977 return temp;
980 default:
981 break;
984 return 0;
987 /* Called from init_alias_analysis indirectly through note_stores. */
989 /* While scanning insns to find base values, reg_seen[N] is nonzero if
990 register N has been set in this function. */
991 static char *reg_seen;
993 /* Addresses which are known not to alias anything else are identified
994 by a unique integer. */
995 static int unique_id;
997 static void
998 record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1000 unsigned regno;
1001 rtx src;
1002 int n;
1004 if (!REG_P (dest))
1005 return;
1007 regno = REGNO (dest);
1009 gcc_assert (regno < VEC_length (rtx, reg_base_value));
1011 /* If this spans multiple hard registers, then we must indicate that every
1012 register has an unusable value. */
1013 if (regno < FIRST_PSEUDO_REGISTER)
1014 n = hard_regno_nregs[regno][GET_MODE (dest)];
1015 else
1016 n = 1;
1017 if (n != 1)
1019 while (--n >= 0)
1021 reg_seen[regno + n] = 1;
1022 new_reg_base_value[regno + n] = 0;
1024 return;
1027 if (set)
1029 /* A CLOBBER wipes out any old value but does not prevent a previously
1030 unset register from acquiring a base address (i.e. reg_seen is not
1031 set). */
1032 if (GET_CODE (set) == CLOBBER)
1034 new_reg_base_value[regno] = 0;
1035 return;
1037 src = SET_SRC (set);
1039 else
1041 if (reg_seen[regno])
1043 new_reg_base_value[regno] = 0;
1044 return;
1046 reg_seen[regno] = 1;
1047 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
1048 GEN_INT (unique_id++));
1049 return;
1052 /* If this is not the first set of REGNO, see whether the new value
1053 is related to the old one. There are two cases of interest:
1055 (1) The register might be assigned an entirely new value
1056 that has the same base term as the original set.
1058 (2) The set might be a simple self-modification that
1059 cannot change REGNO's base value.
1061 If neither case holds, reject the original base value as invalid.
1062 Note that the following situation is not detected:
1064 extern int x, y; int *p = &x; p += (&y-&x);
1066 ANSI C does not allow computing the difference of addresses
1067 of distinct top level objects. */
1068 if (new_reg_base_value[regno] != 0
1069 && find_base_value (src) != new_reg_base_value[regno])
1070 switch (GET_CODE (src))
1072 case LO_SUM:
1073 case MINUS:
1074 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1075 new_reg_base_value[regno] = 0;
1076 break;
1077 case PLUS:
1078 /* If the value we add in the PLUS is also a valid base value,
1079 this might be the actual base value, and the original value
1080 an index. */
1082 rtx other = NULL_RTX;
1084 if (XEXP (src, 0) == dest)
1085 other = XEXP (src, 1);
1086 else if (XEXP (src, 1) == dest)
1087 other = XEXP (src, 0);
1089 if (! other || find_base_value (other))
1090 new_reg_base_value[regno] = 0;
1091 break;
1093 case AND:
1094 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
1095 new_reg_base_value[regno] = 0;
1096 break;
1097 default:
1098 new_reg_base_value[regno] = 0;
1099 break;
1101 /* If this is the first set of a register, record the value. */
1102 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1103 && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1104 new_reg_base_value[regno] = find_base_value (src);
1106 reg_seen[regno] = 1;
1109 /* If a value is known for REGNO, return it. */
1112 get_reg_known_value (unsigned int regno)
1114 if (regno >= FIRST_PSEUDO_REGISTER)
1116 regno -= FIRST_PSEUDO_REGISTER;
1117 if (regno < reg_known_value_size)
1118 return reg_known_value[regno];
1120 return NULL;
1123 /* Set it. */
1125 static void
1126 set_reg_known_value (unsigned int regno, rtx val)
1128 if (regno >= FIRST_PSEUDO_REGISTER)
1130 regno -= FIRST_PSEUDO_REGISTER;
1131 if (regno < reg_known_value_size)
1132 reg_known_value[regno] = val;
1136 /* Similarly for reg_known_equiv_p. */
1138 bool
1139 get_reg_known_equiv_p (unsigned int regno)
1141 if (regno >= FIRST_PSEUDO_REGISTER)
1143 regno -= FIRST_PSEUDO_REGISTER;
1144 if (regno < reg_known_value_size)
1145 return reg_known_equiv_p[regno];
1147 return false;
1150 static void
1151 set_reg_known_equiv_p (unsigned int regno, bool val)
1153 if (regno >= FIRST_PSEUDO_REGISTER)
1155 regno -= FIRST_PSEUDO_REGISTER;
1156 if (regno < reg_known_value_size)
1157 reg_known_equiv_p[regno] = val;
1162 /* Returns a canonical version of X, from the point of view alias
1163 analysis. (For example, if X is a MEM whose address is a register,
1164 and the register has a known value (say a SYMBOL_REF), then a MEM
1165 whose address is the SYMBOL_REF is returned.) */
1168 canon_rtx (rtx x)
1170 /* Recursively look for equivalences. */
1171 if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1173 rtx t = get_reg_known_value (REGNO (x));
1174 if (t == x)
1175 return x;
1176 if (t)
1177 return canon_rtx (t);
1180 if (GET_CODE (x) == PLUS)
1182 rtx x0 = canon_rtx (XEXP (x, 0));
1183 rtx x1 = canon_rtx (XEXP (x, 1));
1185 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1187 if (GET_CODE (x0) == CONST_INT)
1188 return plus_constant (x1, INTVAL (x0));
1189 else if (GET_CODE (x1) == CONST_INT)
1190 return plus_constant (x0, INTVAL (x1));
1191 return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1195 /* This gives us much better alias analysis when called from
1196 the loop optimizer. Note we want to leave the original
1197 MEM alone, but need to return the canonicalized MEM with
1198 all the flags with their original values. */
1199 else if (MEM_P (x))
1200 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1202 return x;
1205 /* Return 1 if X and Y are identical-looking rtx's.
1206 Expect that X and Y has been already canonicalized.
1208 We use the data in reg_known_value above to see if two registers with
1209 different numbers are, in fact, equivalent. */
1211 static int
1212 rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1214 int i;
1215 int j;
1216 enum rtx_code code;
1217 const char *fmt;
1219 if (x == 0 && y == 0)
1220 return 1;
1221 if (x == 0 || y == 0)
1222 return 0;
1224 if (x == y)
1225 return 1;
1227 code = GET_CODE (x);
1228 /* Rtx's of different codes cannot be equal. */
1229 if (code != GET_CODE (y))
1230 return 0;
1232 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1233 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1235 if (GET_MODE (x) != GET_MODE (y))
1236 return 0;
1238 /* Some RTL can be compared without a recursive examination. */
1239 switch (code)
1241 case REG:
1242 return REGNO (x) == REGNO (y);
1244 case LABEL_REF:
1245 return XEXP (x, 0) == XEXP (y, 0);
1247 case SYMBOL_REF:
1248 return XSTR (x, 0) == XSTR (y, 0);
1250 case VALUE:
1251 case CONST_INT:
1252 case CONST_DOUBLE:
1253 case CONST_FIXED:
1254 /* There's no need to compare the contents of CONST_DOUBLEs or
1255 CONST_INTs because pointer equality is a good enough
1256 comparison for these nodes. */
1257 return 0;
1259 default:
1260 break;
1263 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1264 if (code == PLUS)
1265 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1266 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1267 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1268 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1269 /* For commutative operations, the RTX match if the operand match in any
1270 order. Also handle the simple binary and unary cases without a loop. */
1271 if (COMMUTATIVE_P (x))
1273 rtx xop0 = canon_rtx (XEXP (x, 0));
1274 rtx yop0 = canon_rtx (XEXP (y, 0));
1275 rtx yop1 = canon_rtx (XEXP (y, 1));
1277 return ((rtx_equal_for_memref_p (xop0, yop0)
1278 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1279 || (rtx_equal_for_memref_p (xop0, yop1)
1280 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1282 else if (NON_COMMUTATIVE_P (x))
1284 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1285 canon_rtx (XEXP (y, 0)))
1286 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1287 canon_rtx (XEXP (y, 1))));
1289 else if (UNARY_P (x))
1290 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1291 canon_rtx (XEXP (y, 0)));
1293 /* Compare the elements. If any pair of corresponding elements
1294 fail to match, return 0 for the whole things.
1296 Limit cases to types which actually appear in addresses. */
1298 fmt = GET_RTX_FORMAT (code);
1299 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1301 switch (fmt[i])
1303 case 'i':
1304 if (XINT (x, i) != XINT (y, i))
1305 return 0;
1306 break;
1308 case 'E':
1309 /* Two vectors must have the same length. */
1310 if (XVECLEN (x, i) != XVECLEN (y, i))
1311 return 0;
1313 /* And the corresponding elements must match. */
1314 for (j = 0; j < XVECLEN (x, i); j++)
1315 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1316 canon_rtx (XVECEXP (y, i, j))) == 0)
1317 return 0;
1318 break;
1320 case 'e':
1321 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1322 canon_rtx (XEXP (y, i))) == 0)
1323 return 0;
1324 break;
1326 /* This can happen for asm operands. */
1327 case 's':
1328 if (strcmp (XSTR (x, i), XSTR (y, i)))
1329 return 0;
1330 break;
1332 /* This can happen for an asm which clobbers memory. */
1333 case '0':
1334 break;
1336 /* It is believed that rtx's at this level will never
1337 contain anything but integers and other rtx's,
1338 except for within LABEL_REFs and SYMBOL_REFs. */
1339 default:
1340 gcc_unreachable ();
1343 return 1;
1347 find_base_term (rtx x)
1349 cselib_val *val;
1350 struct elt_loc_list *l;
1352 #if defined (FIND_BASE_TERM)
1353 /* Try machine-dependent ways to find the base term. */
1354 x = FIND_BASE_TERM (x);
1355 #endif
1357 switch (GET_CODE (x))
1359 case REG:
1360 return REG_BASE_VALUE (x);
1362 case TRUNCATE:
1363 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1364 return 0;
1365 /* Fall through. */
1366 case HIGH:
1367 case PRE_INC:
1368 case PRE_DEC:
1369 case POST_INC:
1370 case POST_DEC:
1371 case PRE_MODIFY:
1372 case POST_MODIFY:
1373 return find_base_term (XEXP (x, 0));
1375 case ZERO_EXTEND:
1376 case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1378 rtx temp = find_base_term (XEXP (x, 0));
1380 if (temp != 0 && CONSTANT_P (temp))
1381 temp = convert_memory_address (Pmode, temp);
1383 return temp;
1386 case VALUE:
1387 val = CSELIB_VAL_PTR (x);
1388 if (!val)
1389 return 0;
1390 for (l = val->locs; l; l = l->next)
1391 if ((x = find_base_term (l->loc)) != 0)
1392 return x;
1393 return 0;
1395 case CONST:
1396 x = XEXP (x, 0);
1397 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1398 return 0;
1399 /* Fall through. */
1400 case LO_SUM:
1401 case PLUS:
1402 case MINUS:
1404 rtx tmp1 = XEXP (x, 0);
1405 rtx tmp2 = XEXP (x, 1);
1407 /* This is a little bit tricky since we have to determine which of
1408 the two operands represents the real base address. Otherwise this
1409 routine may return the index register instead of the base register.
1411 That may cause us to believe no aliasing was possible, when in
1412 fact aliasing is possible.
1414 We use a few simple tests to guess the base register. Additional
1415 tests can certainly be added. For example, if one of the operands
1416 is a shift or multiply, then it must be the index register and the
1417 other operand is the base register. */
1419 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1420 return find_base_term (tmp2);
1422 /* If either operand is known to be a pointer, then use it
1423 to determine the base term. */
1424 if (REG_P (tmp1) && REG_POINTER (tmp1))
1425 return find_base_term (tmp1);
1427 if (REG_P (tmp2) && REG_POINTER (tmp2))
1428 return find_base_term (tmp2);
1430 /* Neither operand was known to be a pointer. Go ahead and find the
1431 base term for both operands. */
1432 tmp1 = find_base_term (tmp1);
1433 tmp2 = find_base_term (tmp2);
1435 /* If either base term is named object or a special address
1436 (like an argument or stack reference), then use it for the
1437 base term. */
1438 if (tmp1 != 0
1439 && (GET_CODE (tmp1) == SYMBOL_REF
1440 || GET_CODE (tmp1) == LABEL_REF
1441 || (GET_CODE (tmp1) == ADDRESS
1442 && GET_MODE (tmp1) != VOIDmode)))
1443 return tmp1;
1445 if (tmp2 != 0
1446 && (GET_CODE (tmp2) == SYMBOL_REF
1447 || GET_CODE (tmp2) == LABEL_REF
1448 || (GET_CODE (tmp2) == ADDRESS
1449 && GET_MODE (tmp2) != VOIDmode)))
1450 return tmp2;
1452 /* We could not determine which of the two operands was the
1453 base register and which was the index. So we can determine
1454 nothing from the base alias check. */
1455 return 0;
1458 case AND:
1459 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0)
1460 return find_base_term (XEXP (x, 0));
1461 return 0;
1463 case SYMBOL_REF:
1464 case LABEL_REF:
1465 return x;
1467 default:
1468 return 0;
1472 /* Return 0 if the addresses X and Y are known to point to different
1473 objects, 1 if they might be pointers to the same object. */
1475 static int
1476 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1477 enum machine_mode y_mode)
1479 rtx x_base = find_base_term (x);
1480 rtx y_base = find_base_term (y);
1482 /* If the address itself has no known base see if a known equivalent
1483 value has one. If either address still has no known base, nothing
1484 is known about aliasing. */
1485 if (x_base == 0)
1487 rtx x_c;
1489 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1490 return 1;
1492 x_base = find_base_term (x_c);
1493 if (x_base == 0)
1494 return 1;
1497 if (y_base == 0)
1499 rtx y_c;
1500 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1501 return 1;
1503 y_base = find_base_term (y_c);
1504 if (y_base == 0)
1505 return 1;
1508 /* If the base addresses are equal nothing is known about aliasing. */
1509 if (rtx_equal_p (x_base, y_base))
1510 return 1;
1512 /* The base addresses of the read and write are different expressions.
1513 If they are both symbols and they are not accessed via AND, there is
1514 no conflict. We can bring knowledge of object alignment into play
1515 here. For example, on alpha, "char a, b;" can alias one another,
1516 though "char a; long b;" cannot. */
1517 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1519 if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1520 return 1;
1521 if (GET_CODE (x) == AND
1522 && (GET_CODE (XEXP (x, 1)) != CONST_INT
1523 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1524 return 1;
1525 if (GET_CODE (y) == AND
1526 && (GET_CODE (XEXP (y, 1)) != CONST_INT
1527 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1528 return 1;
1529 /* Differing symbols never alias. */
1530 return 0;
1533 /* If one address is a stack reference there can be no alias:
1534 stack references using different base registers do not alias,
1535 a stack reference can not alias a parameter, and a stack reference
1536 can not alias a global. */
1537 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1538 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1539 return 0;
1541 if (! flag_argument_noalias)
1542 return 1;
1544 if (flag_argument_noalias > 1)
1545 return 0;
1547 /* Weak noalias assertion (arguments are distinct, but may match globals). */
1548 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1551 /* Convert the address X into something we can use. This is done by returning
1552 it unchanged unless it is a value; in the latter case we call cselib to get
1553 a more useful rtx. */
1556 get_addr (rtx x)
1558 cselib_val *v;
1559 struct elt_loc_list *l;
1561 if (GET_CODE (x) != VALUE)
1562 return x;
1563 v = CSELIB_VAL_PTR (x);
1564 if (v)
1566 for (l = v->locs; l; l = l->next)
1567 if (CONSTANT_P (l->loc))
1568 return l->loc;
1569 for (l = v->locs; l; l = l->next)
1570 if (!REG_P (l->loc) && !MEM_P (l->loc))
1571 return l->loc;
1572 if (v->locs)
1573 return v->locs->loc;
1575 return x;
1578 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1579 where SIZE is the size in bytes of the memory reference. If ADDR
1580 is not modified by the memory reference then ADDR is returned. */
1582 static rtx
1583 addr_side_effect_eval (rtx addr, int size, int n_refs)
1585 int offset = 0;
1587 switch (GET_CODE (addr))
1589 case PRE_INC:
1590 offset = (n_refs + 1) * size;
1591 break;
1592 case PRE_DEC:
1593 offset = -(n_refs + 1) * size;
1594 break;
1595 case POST_INC:
1596 offset = n_refs * size;
1597 break;
1598 case POST_DEC:
1599 offset = -n_refs * size;
1600 break;
1602 default:
1603 return addr;
1606 if (offset)
1607 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1608 GEN_INT (offset));
1609 else
1610 addr = XEXP (addr, 0);
1611 addr = canon_rtx (addr);
1613 return addr;
1616 /* Return nonzero if X and Y (memory addresses) could reference the
1617 same location in memory. C is an offset accumulator. When
1618 C is nonzero, we are testing aliases between X and Y + C.
1619 XSIZE is the size in bytes of the X reference,
1620 similarly YSIZE is the size in bytes for Y.
1621 Expect that canon_rtx has been already called for X and Y.
1623 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1624 referenced (the reference was BLKmode), so make the most pessimistic
1625 assumptions.
1627 If XSIZE or YSIZE is negative, we may access memory outside the object
1628 being referenced as a side effect. This can happen when using AND to
1629 align memory references, as is done on the Alpha.
1631 Nice to notice that varying addresses cannot conflict with fp if no
1632 local variables had their addresses taken, but that's too hard now. */
1634 static int
1635 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1637 if (GET_CODE (x) == VALUE)
1638 x = get_addr (x);
1639 if (GET_CODE (y) == VALUE)
1640 y = get_addr (y);
1641 if (GET_CODE (x) == HIGH)
1642 x = XEXP (x, 0);
1643 else if (GET_CODE (x) == LO_SUM)
1644 x = XEXP (x, 1);
1645 else
1646 x = addr_side_effect_eval (x, xsize, 0);
1647 if (GET_CODE (y) == HIGH)
1648 y = XEXP (y, 0);
1649 else if (GET_CODE (y) == LO_SUM)
1650 y = XEXP (y, 1);
1651 else
1652 y = addr_side_effect_eval (y, ysize, 0);
1654 if (rtx_equal_for_memref_p (x, y))
1656 if (xsize <= 0 || ysize <= 0)
1657 return 1;
1658 if (c >= 0 && xsize > c)
1659 return 1;
1660 if (c < 0 && ysize+c > 0)
1661 return 1;
1662 return 0;
1665 /* This code used to check for conflicts involving stack references and
1666 globals but the base address alias code now handles these cases. */
1668 if (GET_CODE (x) == PLUS)
1670 /* The fact that X is canonicalized means that this
1671 PLUS rtx is canonicalized. */
1672 rtx x0 = XEXP (x, 0);
1673 rtx x1 = XEXP (x, 1);
1675 if (GET_CODE (y) == PLUS)
1677 /* The fact that Y is canonicalized means that this
1678 PLUS rtx is canonicalized. */
1679 rtx y0 = XEXP (y, 0);
1680 rtx y1 = XEXP (y, 1);
1682 if (rtx_equal_for_memref_p (x1, y1))
1683 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1684 if (rtx_equal_for_memref_p (x0, y0))
1685 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1686 if (GET_CODE (x1) == CONST_INT)
1688 if (GET_CODE (y1) == CONST_INT)
1689 return memrefs_conflict_p (xsize, x0, ysize, y0,
1690 c - INTVAL (x1) + INTVAL (y1));
1691 else
1692 return memrefs_conflict_p (xsize, x0, ysize, y,
1693 c - INTVAL (x1));
1695 else if (GET_CODE (y1) == CONST_INT)
1696 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1698 return 1;
1700 else if (GET_CODE (x1) == CONST_INT)
1701 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1703 else if (GET_CODE (y) == PLUS)
1705 /* The fact that Y is canonicalized means that this
1706 PLUS rtx is canonicalized. */
1707 rtx y0 = XEXP (y, 0);
1708 rtx y1 = XEXP (y, 1);
1710 if (GET_CODE (y1) == CONST_INT)
1711 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1712 else
1713 return 1;
1716 if (GET_CODE (x) == GET_CODE (y))
1717 switch (GET_CODE (x))
1719 case MULT:
1721 /* Handle cases where we expect the second operands to be the
1722 same, and check only whether the first operand would conflict
1723 or not. */
1724 rtx x0, y0;
1725 rtx x1 = canon_rtx (XEXP (x, 1));
1726 rtx y1 = canon_rtx (XEXP (y, 1));
1727 if (! rtx_equal_for_memref_p (x1, y1))
1728 return 1;
1729 x0 = canon_rtx (XEXP (x, 0));
1730 y0 = canon_rtx (XEXP (y, 0));
1731 if (rtx_equal_for_memref_p (x0, y0))
1732 return (xsize == 0 || ysize == 0
1733 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1735 /* Can't properly adjust our sizes. */
1736 if (GET_CODE (x1) != CONST_INT)
1737 return 1;
1738 xsize /= INTVAL (x1);
1739 ysize /= INTVAL (x1);
1740 c /= INTVAL (x1);
1741 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1744 default:
1745 break;
1748 /* Treat an access through an AND (e.g. a subword access on an Alpha)
1749 as an access with indeterminate size. Assume that references
1750 besides AND are aligned, so if the size of the other reference is
1751 at least as large as the alignment, assume no other overlap. */
1752 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1754 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1755 xsize = -1;
1756 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1758 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1760 /* ??? If we are indexing far enough into the array/structure, we
1761 may yet be able to determine that we can not overlap. But we
1762 also need to that we are far enough from the end not to overlap
1763 a following reference, so we do nothing with that for now. */
1764 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1765 ysize = -1;
1766 return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1769 if (CONSTANT_P (x))
1771 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1773 c += (INTVAL (y) - INTVAL (x));
1774 return (xsize <= 0 || ysize <= 0
1775 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1778 if (GET_CODE (x) == CONST)
1780 if (GET_CODE (y) == CONST)
1781 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1782 ysize, canon_rtx (XEXP (y, 0)), c);
1783 else
1784 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1785 ysize, y, c);
1787 if (GET_CODE (y) == CONST)
1788 return memrefs_conflict_p (xsize, x, ysize,
1789 canon_rtx (XEXP (y, 0)), c);
1791 if (CONSTANT_P (y))
1792 return (xsize <= 0 || ysize <= 0
1793 || (rtx_equal_for_memref_p (x, y)
1794 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1796 return 1;
1798 return 1;
1801 /* Functions to compute memory dependencies.
1803 Since we process the insns in execution order, we can build tables
1804 to keep track of what registers are fixed (and not aliased), what registers
1805 are varying in known ways, and what registers are varying in unknown
1806 ways.
1808 If both memory references are volatile, then there must always be a
1809 dependence between the two references, since their order can not be
1810 changed. A volatile and non-volatile reference can be interchanged
1811 though.
1813 A MEM_IN_STRUCT reference at a non-AND varying address can never
1814 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
1815 also must allow AND addresses, because they may generate accesses
1816 outside the object being referenced. This is used to generate
1817 aligned addresses from unaligned addresses, for instance, the alpha
1818 storeqi_unaligned pattern. */
1820 /* Read dependence: X is read after read in MEM takes place. There can
1821 only be a dependence here if both reads are volatile. */
1824 read_dependence (const_rtx mem, const_rtx x)
1826 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1829 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1830 MEM2 is a reference to a structure at a varying address, or returns
1831 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
1832 value is returned MEM1 and MEM2 can never alias. VARIES_P is used
1833 to decide whether or not an address may vary; it should return
1834 nonzero whenever variation is possible.
1835 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
1837 static const_rtx
1838 fixed_scalar_and_varying_struct_p (const_rtx mem1, const_rtx mem2, rtx mem1_addr,
1839 rtx mem2_addr,
1840 bool (*varies_p) (const_rtx, bool))
1842 if (! flag_strict_aliasing)
1843 return NULL_RTX;
1845 if (MEM_ALIAS_SET (mem2)
1846 && MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1847 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1848 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1849 varying address. */
1850 return mem1;
1852 if (MEM_ALIAS_SET (mem1)
1853 && MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1854 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1855 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1856 varying address. */
1857 return mem2;
1859 return NULL_RTX;
1862 /* Returns nonzero if something about the mode or address format MEM1
1863 indicates that it might well alias *anything*. */
1865 static int
1866 aliases_everything_p (const_rtx mem)
1868 if (GET_CODE (XEXP (mem, 0)) == AND)
1869 /* If the address is an AND, it's very hard to know at what it is
1870 actually pointing. */
1871 return 1;
1873 return 0;
1876 /* Return true if we can determine that the fields referenced cannot
1877 overlap for any pair of objects. */
1879 static bool
1880 nonoverlapping_component_refs_p (const_tree x, const_tree y)
1882 const_tree fieldx, fieldy, typex, typey, orig_y;
1886 /* The comparison has to be done at a common type, since we don't
1887 know how the inheritance hierarchy works. */
1888 orig_y = y;
1891 fieldx = TREE_OPERAND (x, 1);
1892 typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
1894 y = orig_y;
1897 fieldy = TREE_OPERAND (y, 1);
1898 typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
1900 if (typex == typey)
1901 goto found;
1903 y = TREE_OPERAND (y, 0);
1905 while (y && TREE_CODE (y) == COMPONENT_REF);
1907 x = TREE_OPERAND (x, 0);
1909 while (x && TREE_CODE (x) == COMPONENT_REF);
1910 /* Never found a common type. */
1911 return false;
1913 found:
1914 /* If we're left with accessing different fields of a structure,
1915 then no overlap. */
1916 if (TREE_CODE (typex) == RECORD_TYPE
1917 && fieldx != fieldy)
1918 return true;
1920 /* The comparison on the current field failed. If we're accessing
1921 a very nested structure, look at the next outer level. */
1922 x = TREE_OPERAND (x, 0);
1923 y = TREE_OPERAND (y, 0);
1925 while (x && y
1926 && TREE_CODE (x) == COMPONENT_REF
1927 && TREE_CODE (y) == COMPONENT_REF);
1929 return false;
1932 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
1934 static tree
1935 decl_for_component_ref (tree x)
1939 x = TREE_OPERAND (x, 0);
1941 while (x && TREE_CODE (x) == COMPONENT_REF);
1943 return x && DECL_P (x) ? x : NULL_TREE;
1946 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1947 offset of the field reference. */
1949 static rtx
1950 adjust_offset_for_component_ref (tree x, rtx offset)
1952 HOST_WIDE_INT ioffset;
1954 if (! offset)
1955 return NULL_RTX;
1957 ioffset = INTVAL (offset);
1960 tree offset = component_ref_field_offset (x);
1961 tree field = TREE_OPERAND (x, 1);
1963 if (! host_integerp (offset, 1))
1964 return NULL_RTX;
1965 ioffset += (tree_low_cst (offset, 1)
1966 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
1967 / BITS_PER_UNIT));
1969 x = TREE_OPERAND (x, 0);
1971 while (x && TREE_CODE (x) == COMPONENT_REF);
1973 return GEN_INT (ioffset);
1976 /* Return nonzero if we can determine the exprs corresponding to memrefs
1977 X and Y and they do not overlap. */
1979 static int
1980 nonoverlapping_memrefs_p (const_rtx x, const_rtx y)
1982 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
1983 rtx rtlx, rtly;
1984 rtx basex, basey;
1985 rtx moffsetx, moffsety;
1986 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
1988 /* Unless both have exprs, we can't tell anything. */
1989 if (exprx == 0 || expry == 0)
1990 return 0;
1992 /* If both are field references, we may be able to determine something. */
1993 if (TREE_CODE (exprx) == COMPONENT_REF
1994 && TREE_CODE (expry) == COMPONENT_REF
1995 && nonoverlapping_component_refs_p (exprx, expry))
1996 return 1;
1999 /* If the field reference test failed, look at the DECLs involved. */
2000 moffsetx = MEM_OFFSET (x);
2001 if (TREE_CODE (exprx) == COMPONENT_REF)
2003 if (TREE_CODE (expry) == VAR_DECL
2004 && POINTER_TYPE_P (TREE_TYPE (expry)))
2006 tree field = TREE_OPERAND (exprx, 1);
2007 tree fieldcontext = DECL_FIELD_CONTEXT (field);
2008 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
2009 TREE_TYPE (field)))
2010 return 1;
2013 tree t = decl_for_component_ref (exprx);
2014 if (! t)
2015 return 0;
2016 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
2017 exprx = t;
2020 else if (INDIRECT_REF_P (exprx))
2022 exprx = TREE_OPERAND (exprx, 0);
2023 if (flag_argument_noalias < 2
2024 || TREE_CODE (exprx) != PARM_DECL)
2025 return 0;
2028 moffsety = MEM_OFFSET (y);
2029 if (TREE_CODE (expry) == COMPONENT_REF)
2031 if (TREE_CODE (exprx) == VAR_DECL
2032 && POINTER_TYPE_P (TREE_TYPE (exprx)))
2034 tree field = TREE_OPERAND (expry, 1);
2035 tree fieldcontext = DECL_FIELD_CONTEXT (field);
2036 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
2037 TREE_TYPE (field)))
2038 return 1;
2041 tree t = decl_for_component_ref (expry);
2042 if (! t)
2043 return 0;
2044 moffsety = adjust_offset_for_component_ref (expry, moffsety);
2045 expry = t;
2048 else if (INDIRECT_REF_P (expry))
2050 expry = TREE_OPERAND (expry, 0);
2051 if (flag_argument_noalias < 2
2052 || TREE_CODE (expry) != PARM_DECL)
2053 return 0;
2056 if (! DECL_P (exprx) || ! DECL_P (expry))
2057 return 0;
2059 rtlx = DECL_RTL (exprx);
2060 rtly = DECL_RTL (expry);
2062 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2063 can't overlap unless they are the same because we never reuse that part
2064 of the stack frame used for locals for spilled pseudos. */
2065 if ((!MEM_P (rtlx) || !MEM_P (rtly))
2066 && ! rtx_equal_p (rtlx, rtly))
2067 return 1;
2069 /* Get the base and offsets of both decls. If either is a register, we
2070 know both are and are the same, so use that as the base. The only
2071 we can avoid overlap is if we can deduce that they are nonoverlapping
2072 pieces of that decl, which is very rare. */
2073 basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2074 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT)
2075 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2077 basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2078 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT)
2079 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2081 /* If the bases are different, we know they do not overlap if both
2082 are constants or if one is a constant and the other a pointer into the
2083 stack frame. Otherwise a different base means we can't tell if they
2084 overlap or not. */
2085 if (! rtx_equal_p (basex, basey))
2086 return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2087 || (CONSTANT_P (basex) && REG_P (basey)
2088 && REGNO_PTR_FRAME_P (REGNO (basey)))
2089 || (CONSTANT_P (basey) && REG_P (basex)
2090 && REGNO_PTR_FRAME_P (REGNO (basex))));
2092 sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2093 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2094 : -1);
2095 sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2096 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2097 -1);
2099 /* If we have an offset for either memref, it can update the values computed
2100 above. */
2101 if (moffsetx)
2102 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2103 if (moffsety)
2104 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2106 /* If a memref has both a size and an offset, we can use the smaller size.
2107 We can't do this if the offset isn't known because we must view this
2108 memref as being anywhere inside the DECL's MEM. */
2109 if (MEM_SIZE (x) && moffsetx)
2110 sizex = INTVAL (MEM_SIZE (x));
2111 if (MEM_SIZE (y) && moffsety)
2112 sizey = INTVAL (MEM_SIZE (y));
2114 /* Put the values of the memref with the lower offset in X's values. */
2115 if (offsetx > offsety)
2117 tem = offsetx, offsetx = offsety, offsety = tem;
2118 tem = sizex, sizex = sizey, sizey = tem;
2121 /* If we don't know the size of the lower-offset value, we can't tell
2122 if they conflict. Otherwise, we do the test. */
2123 return sizex >= 0 && offsety >= offsetx + sizex;
2126 /* True dependence: X is read after store in MEM takes place. */
2129 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x,
2130 bool (*varies) (const_rtx, bool))
2132 rtx x_addr, mem_addr;
2133 rtx base;
2135 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2136 return 1;
2138 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2139 This is used in epilogue deallocation functions, and in cselib. */
2140 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2141 return 1;
2142 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2143 return 1;
2144 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2145 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2146 return 1;
2148 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2149 return 0;
2151 /* Read-only memory is by definition never modified, and therefore can't
2152 conflict with anything. We don't expect to find read-only set on MEM,
2153 but stupid user tricks can produce them, so don't die. */
2154 if (MEM_READONLY_P (x))
2155 return 0;
2157 if (nonoverlapping_memrefs_p (mem, x))
2158 return 0;
2160 if (mem_mode == VOIDmode)
2161 mem_mode = GET_MODE (mem);
2163 x_addr = get_addr (XEXP (x, 0));
2164 mem_addr = get_addr (XEXP (mem, 0));
2166 base = find_base_term (x_addr);
2167 if (base && (GET_CODE (base) == LABEL_REF
2168 || (GET_CODE (base) == SYMBOL_REF
2169 && CONSTANT_POOL_ADDRESS_P (base))))
2170 return 0;
2172 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2173 return 0;
2175 x_addr = canon_rtx (x_addr);
2176 mem_addr = canon_rtx (mem_addr);
2178 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2179 SIZE_FOR_MODE (x), x_addr, 0))
2180 return 0;
2182 if (aliases_everything_p (x))
2183 return 1;
2185 /* We cannot use aliases_everything_p to test MEM, since we must look
2186 at MEM_MODE, rather than GET_MODE (MEM). */
2187 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2188 return 1;
2190 /* In true_dependence we also allow BLKmode to alias anything. Why
2191 don't we do this in anti_dependence and output_dependence? */
2192 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2193 return 1;
2195 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2196 varies);
2199 /* Canonical true dependence: X is read after store in MEM takes place.
2200 Variant of true_dependence which assumes MEM has already been
2201 canonicalized (hence we no longer do that here).
2202 The mem_addr argument has been added, since true_dependence computed
2203 this value prior to canonicalizing. */
2206 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2207 const_rtx x, bool (*varies) (const_rtx, bool))
2209 rtx x_addr;
2211 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2212 return 1;
2214 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2215 This is used in epilogue deallocation functions. */
2216 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2217 return 1;
2218 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2219 return 1;
2220 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2221 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2222 return 1;
2224 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2225 return 0;
2227 /* Read-only memory is by definition never modified, and therefore can't
2228 conflict with anything. We don't expect to find read-only set on MEM,
2229 but stupid user tricks can produce them, so don't die. */
2230 if (MEM_READONLY_P (x))
2231 return 0;
2233 if (nonoverlapping_memrefs_p (x, mem))
2234 return 0;
2236 x_addr = get_addr (XEXP (x, 0));
2238 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2239 return 0;
2241 x_addr = canon_rtx (x_addr);
2242 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2243 SIZE_FOR_MODE (x), x_addr, 0))
2244 return 0;
2246 if (aliases_everything_p (x))
2247 return 1;
2249 /* We cannot use aliases_everything_p to test MEM, since we must look
2250 at MEM_MODE, rather than GET_MODE (MEM). */
2251 if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2252 return 1;
2254 /* In true_dependence we also allow BLKmode to alias anything. Why
2255 don't we do this in anti_dependence and output_dependence? */
2256 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2257 return 1;
2259 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2260 varies);
2263 /* Returns nonzero if a write to X might alias a previous read from
2264 (or, if WRITEP is nonzero, a write to) MEM. */
2266 static int
2267 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2269 rtx x_addr, mem_addr;
2270 const_rtx fixed_scalar;
2271 rtx base;
2273 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2274 return 1;
2276 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2277 This is used in epilogue deallocation functions. */
2278 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2279 return 1;
2280 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2281 return 1;
2282 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2283 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2284 return 1;
2286 if (DIFFERENT_ALIAS_SETS_P (x, mem))
2287 return 0;
2289 /* A read from read-only memory can't conflict with read-write memory. */
2290 if (!writep && MEM_READONLY_P (mem))
2291 return 0;
2293 if (nonoverlapping_memrefs_p (x, mem))
2294 return 0;
2296 x_addr = get_addr (XEXP (x, 0));
2297 mem_addr = get_addr (XEXP (mem, 0));
2299 if (! writep)
2301 base = find_base_term (mem_addr);
2302 if (base && (GET_CODE (base) == LABEL_REF
2303 || (GET_CODE (base) == SYMBOL_REF
2304 && CONSTANT_POOL_ADDRESS_P (base))))
2305 return 0;
2308 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2309 GET_MODE (mem)))
2310 return 0;
2312 x_addr = canon_rtx (x_addr);
2313 mem_addr = canon_rtx (mem_addr);
2315 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2316 SIZE_FOR_MODE (x), x_addr, 0))
2317 return 0;
2319 fixed_scalar
2320 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2321 rtx_addr_varies_p);
2323 return (!(fixed_scalar == mem && !aliases_everything_p (x))
2324 && !(fixed_scalar == x && !aliases_everything_p (mem)));
2327 /* Anti dependence: X is written after read in MEM takes place. */
2330 anti_dependence (const_rtx mem, const_rtx x)
2332 return write_dependence_p (mem, x, /*writep=*/0);
2335 /* Output dependence: X is written after store in MEM takes place. */
2338 output_dependence (const_rtx mem, const_rtx x)
2340 return write_dependence_p (mem, x, /*writep=*/1);
2344 void
2345 init_alias_target (void)
2347 int i;
2349 memset (static_reg_base_value, 0, sizeof static_reg_base_value);
2351 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2352 /* Check whether this register can hold an incoming pointer
2353 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2354 numbers, so translate if necessary due to register windows. */
2355 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2356 && HARD_REGNO_MODE_OK (i, Pmode))
2357 static_reg_base_value[i]
2358 = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2360 static_reg_base_value[STACK_POINTER_REGNUM]
2361 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2362 static_reg_base_value[ARG_POINTER_REGNUM]
2363 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2364 static_reg_base_value[FRAME_POINTER_REGNUM]
2365 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2366 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2367 static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2368 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2369 #endif
2372 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2373 to be memory reference. */
2374 static bool memory_modified;
2375 static void
2376 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2378 if (MEM_P (x))
2380 if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
2381 memory_modified = true;
2386 /* Return true when INSN possibly modify memory contents of MEM
2387 (i.e. address can be modified). */
2388 bool
2389 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
2391 if (!INSN_P (insn))
2392 return false;
2393 memory_modified = false;
2394 note_stores (PATTERN (insn), memory_modified_1, CONST_CAST_RTX(mem));
2395 return memory_modified;
2398 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2399 array. */
2401 void
2402 init_alias_analysis (void)
2404 unsigned int maxreg = max_reg_num ();
2405 int changed, pass;
2406 int i;
2407 unsigned int ui;
2408 rtx insn;
2410 timevar_push (TV_ALIAS_ANALYSIS);
2412 reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER;
2413 reg_known_value = ggc_calloc (reg_known_value_size, sizeof (rtx));
2414 reg_known_equiv_p = xcalloc (reg_known_value_size, sizeof (bool));
2416 /* If we have memory allocated from the previous run, use it. */
2417 if (old_reg_base_value)
2418 reg_base_value = old_reg_base_value;
2420 if (reg_base_value)
2421 VEC_truncate (rtx, reg_base_value, 0);
2423 VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2425 new_reg_base_value = XNEWVEC (rtx, maxreg);
2426 reg_seen = XNEWVEC (char, maxreg);
2428 /* The basic idea is that each pass through this loop will use the
2429 "constant" information from the previous pass to propagate alias
2430 information through another level of assignments.
2432 This could get expensive if the assignment chains are long. Maybe
2433 we should throttle the number of iterations, possibly based on
2434 the optimization level or flag_expensive_optimizations.
2436 We could propagate more information in the first pass by making use
2437 of DF_REG_DEF_COUNT to determine immediately that the alias information
2438 for a pseudo is "constant".
2440 A program with an uninitialized variable can cause an infinite loop
2441 here. Instead of doing a full dataflow analysis to detect such problems
2442 we just cap the number of iterations for the loop.
2444 The state of the arrays for the set chain in question does not matter
2445 since the program has undefined behavior. */
2447 pass = 0;
2450 /* Assume nothing will change this iteration of the loop. */
2451 changed = 0;
2453 /* We want to assign the same IDs each iteration of this loop, so
2454 start counting from zero each iteration of the loop. */
2455 unique_id = 0;
2457 /* We're at the start of the function each iteration through the
2458 loop, so we're copying arguments. */
2459 copying_arguments = true;
2461 /* Wipe the potential alias information clean for this pass. */
2462 memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2464 /* Wipe the reg_seen array clean. */
2465 memset (reg_seen, 0, maxreg);
2467 /* Mark all hard registers which may contain an address.
2468 The stack, frame and argument pointers may contain an address.
2469 An argument register which can hold a Pmode value may contain
2470 an address even if it is not in BASE_REGS.
2472 The address expression is VOIDmode for an argument and
2473 Pmode for other registers. */
2475 memcpy (new_reg_base_value, static_reg_base_value,
2476 FIRST_PSEUDO_REGISTER * sizeof (rtx));
2478 /* Walk the insns adding values to the new_reg_base_value array. */
2479 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2481 if (INSN_P (insn))
2483 rtx note, set;
2485 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2486 /* The prologue/epilogue insns are not threaded onto the
2487 insn chain until after reload has completed. Thus,
2488 there is no sense wasting time checking if INSN is in
2489 the prologue/epilogue until after reload has completed. */
2490 if (reload_completed
2491 && prologue_epilogue_contains (insn))
2492 continue;
2493 #endif
2495 /* If this insn has a noalias note, process it, Otherwise,
2496 scan for sets. A simple set will have no side effects
2497 which could change the base value of any other register. */
2499 if (GET_CODE (PATTERN (insn)) == SET
2500 && REG_NOTES (insn) != 0
2501 && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2502 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2503 else
2504 note_stores (PATTERN (insn), record_set, NULL);
2506 set = single_set (insn);
2508 if (set != 0
2509 && REG_P (SET_DEST (set))
2510 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2512 unsigned int regno = REGNO (SET_DEST (set));
2513 rtx src = SET_SRC (set);
2514 rtx t;
2516 note = find_reg_equal_equiv_note (insn);
2517 if (note && REG_NOTE_KIND (note) == REG_EQUAL
2518 && DF_REG_DEF_COUNT (regno) != 1)
2519 note = NULL_RTX;
2521 if (note != NULL_RTX
2522 && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2523 && ! rtx_varies_p (XEXP (note, 0), 1)
2524 && ! reg_overlap_mentioned_p (SET_DEST (set),
2525 XEXP (note, 0)))
2527 set_reg_known_value (regno, XEXP (note, 0));
2528 set_reg_known_equiv_p (regno,
2529 REG_NOTE_KIND (note) == REG_EQUIV);
2531 else if (DF_REG_DEF_COUNT (regno) == 1
2532 && GET_CODE (src) == PLUS
2533 && REG_P (XEXP (src, 0))
2534 && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2535 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2537 t = plus_constant (t, INTVAL (XEXP (src, 1)));
2538 set_reg_known_value (regno, t);
2539 set_reg_known_equiv_p (regno, 0);
2541 else if (DF_REG_DEF_COUNT (regno) == 1
2542 && ! rtx_varies_p (src, 1))
2544 set_reg_known_value (regno, src);
2545 set_reg_known_equiv_p (regno, 0);
2549 else if (NOTE_P (insn)
2550 && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2551 copying_arguments = false;
2554 /* Now propagate values from new_reg_base_value to reg_base_value. */
2555 gcc_assert (maxreg == (unsigned int) max_reg_num ());
2557 for (ui = 0; ui < maxreg; ui++)
2559 if (new_reg_base_value[ui]
2560 && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2561 && ! rtx_equal_p (new_reg_base_value[ui],
2562 VEC_index (rtx, reg_base_value, ui)))
2564 VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2565 changed = 1;
2569 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2571 /* Fill in the remaining entries. */
2572 for (i = 0; i < (int)reg_known_value_size; i++)
2573 if (reg_known_value[i] == 0)
2574 reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER];
2576 /* Clean up. */
2577 free (new_reg_base_value);
2578 new_reg_base_value = 0;
2579 free (reg_seen);
2580 reg_seen = 0;
2581 timevar_pop (TV_ALIAS_ANALYSIS);
2584 void
2585 end_alias_analysis (void)
2587 old_reg_base_value = reg_base_value;
2588 ggc_free (reg_known_value);
2589 reg_known_value = 0;
2590 reg_known_value_size = 0;
2591 free (reg_known_equiv_p);
2592 reg_known_equiv_p = 0;
2595 #include "gt-alias.h"