OSDN Git Service

689c944c54edffeef4d40fb247513a8b84d7c579
[pf3gnuchains/gcc-fork.git] / gcc / alias.c
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).
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>.  */
21
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"
49
50 /* The aliasing API provided here solves related but different problems:
51
52    Say there exists (in c)
53
54    struct X {
55      struct Y y1;
56      struct Z z2;
57    } x1, *px1,  *px2;
58
59    struct Y y2, *py;
60    struct Z z2, *pz;
61
62
63    py = &px1.y1;
64    px2 = &x1;
65
66    Consider the four questions:
67
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?
73
74    The answer to these questions can be yes, yes, yes, and maybe.
75
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).
80
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.
88
89    The pass ipa-type-escape does this analysis for the types whose
90    instances do not escape across the compilation boundary.
91
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.
99 */
100
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:
105
106      struct S { int i; double d; };
107
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
113             /   \
114            /     \
115          |/_     _\|
116          int    double
117
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'.
121
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.
126
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.  */
130
131 struct alias_set_entry GTY(())
132 {
133   /* The alias set number, as stored in MEM_ALIAS_SET.  */
134   HOST_WIDE_INT alias_set;
135
136   /* The children of the alias set.  These are not just the immediate
137      children, but, in fact, all descendants.  So, if we have:
138
139        struct T { struct S s; float f; }
140
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;
144
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;
148 };
149 typedef struct alias_set_entry *alias_set_entry;
150
151 static int rtx_equal_for_memref_p (rtx, 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 (HOST_WIDE_INT);
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);
169
170 static void memory_modified_1 (rtx, const_rtx, void *);
171 static void record_alias_subset (HOST_WIDE_INT, HOST_WIDE_INT);
172
173 /* Set up all info needed to perform alias analysis on memory references.  */
174
175 /* Returns the size in bytes of the mode of X.  */
176 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
177
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)
184
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
188
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.
194
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.
198
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.
203
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.  */
207
208 static GTY(()) VEC(rtx,gc) *reg_base_value;
209 static rtx *new_reg_base_value;
210
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;
215
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];
219
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)
223
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;
228
229 /* Indicates number of valid entries in reg_known_value.  */
230 static GTY(()) unsigned int reg_known_value_size;
231
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.
236
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;
245
246 /* True when scanning insns from the start of the rtl to the
247    NOTE_INSN_FUNCTION_BEG note.  */
248 static bool copying_arguments;
249
250 DEF_VEC_P(alias_set_entry);
251 DEF_VEC_ALLOC_P(alias_set_entry,gc);
252
253 /* The splay-tree used to store the various alias set entries.  */
254 static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
255 \f
256 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
257    such an entry, or NULL otherwise.  */
258
259 static inline alias_set_entry
260 get_alias_set_entry (HOST_WIDE_INT alias_set)
261 {
262   return VEC_index (alias_set_entry, alias_sets, alias_set);
263 }
264
265 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
266    the two MEMs cannot alias each other.  */
267
268 static inline int
269 mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
270 {
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)));
280
281   return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
282 }
283
284 /* Insert the NODE into the splay tree given by DATA.  Used by
285    record_alias_subset via splay_tree_foreach.  */
286
287 static int
288 insert_subset_children (splay_tree_node node, void *data)
289 {
290   splay_tree_insert ((splay_tree) data, node->key, node->value);
291
292   return 0;
293 }
294
295 /* Return true if the first alias set is a subset of the second.  */
296
297 bool
298 alias_set_subset_of (HOST_WIDE_INT set1, HOST_WIDE_INT set2)
299 {
300   alias_set_entry ase;
301
302   /* Everything is a subset of the "aliases everything" set.  */
303   if (set2 == 0)
304     return true;
305
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;
313 }
314
315 /* Return 1 if the two specified alias sets may conflict.  */
316
317 int
318 alias_sets_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2)
319 {
320   alias_set_entry ase;
321
322   /* The easy case.  */
323   if (alias_sets_must_conflict_p (set1, set2))
324     return 1;
325
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;
333
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;
341
342   /* The two alias sets are distinct and neither one is the
343      child of the other.  Therefore, they cannot conflict.  */
344   return 0;
345 }
346
347 /* Return 1 if the two specified alias sets will always conflict.  */
348
349 int
350 alias_sets_must_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2)
351 {
352   if (set1 == 0 || set2 == 0 || set1 == set2)
353     return 1;
354
355   return 0;
356 }
357
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.  */
362
363 int
364 objects_must_conflict_p (tree t1, tree t2)
365 {
366   HOST_WIDE_INT set1, set2;
367
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;
373
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;
379
380   set1 = t1 ? get_alias_set (t1) : 0;
381   set2 = t2 ? get_alias_set (t2) : 0;
382
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);
388 }
389 \f
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.  */
394
395 static tree
396 find_base_decl (tree t)
397 {
398   tree d0, d1;
399
400   if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
401     return 0;
402
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))
406     {
407       if (TREE_CODE (t) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (t))
408         t = DECL_GET_RESTRICT_BASE (t);
409       return t;
410     }
411
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)))
416     {
417     case tcc_unary:
418       return find_base_decl (TREE_OPERAND (t, 0));
419
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;
432
433     default:
434       return 0;
435     }
436 }
437
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.
441
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.  */
447
448 bool
449 component_uses_parent_alias_set (tree t)
450 {
451   while (1)
452     {
453       /* If we're at the end, it vacuously uses its own alias set.  */
454       if (!handled_component_p (t))
455         return false;
456
457       switch (TREE_CODE (t))
458         {
459         case COMPONENT_REF:
460           if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
461             return true;
462           break;
463
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;
469
470         case REALPART_EXPR:
471         case IMAGPART_EXPR:
472           break;
473
474         default:
475           /* Bitfields and casts are never addressable.  */
476           return true;
477         }
478
479       t = TREE_OPERAND (t, 0);
480       if (get_alias_set (TREE_TYPE (t)) == 0)
481         return true;
482     }
483 }
484
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.  */
487
488 HOST_WIDE_INT
489 get_alias_set (tree t)
490 {
491   HOST_WIDE_INT set;
492
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;
500
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))
507     {
508       tree inner = t;
509
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;
516
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))
520         {
521           inner = TREE_OPERAND (inner, 0);
522           STRIP_NOPS (inner);
523         }
524
525       /* Check for accesses through restrict-qualified pointers.  */
526       if (INDIRECT_REF_P (inner))
527         {
528           tree decl = find_base_decl (TREE_OPERAND (inner, 0));
529
530           if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
531             {
532               /* If we haven't computed the actual alias set, do it now.  */
533               if (DECL_POINTER_ALIAS_SET (decl) == -2)
534                 {
535                   tree pointed_to_type = TREE_TYPE (TREE_TYPE (decl));
536
537                   /* No two restricted pointers can point at the same thing.
538                      However, a restricted pointer can point at the same thing
539                      as an unrestricted pointer, if that unrestricted pointer
540                      is based on the restricted pointer.  So, we make the
541                      alias set for the restricted pointer a subset of the
542                      alias set for the type pointed to by the type of the
543                      decl.  */
544                   HOST_WIDE_INT pointed_to_alias_set
545                     = get_alias_set (pointed_to_type);
546
547                   if (pointed_to_alias_set == 0)
548                     /* It's not legal to make a subset of alias set zero.  */
549                     DECL_POINTER_ALIAS_SET (decl) = 0;
550                   else if (AGGREGATE_TYPE_P (pointed_to_type))
551                     /* For an aggregate, we must treat the restricted
552                        pointer the same as an ordinary pointer.  If we
553                        were to make the type pointed to by the
554                        restricted pointer a subset of the pointed-to
555                        type, then we would believe that other subsets
556                        of the pointed-to type (such as fields of that
557                        type) do not conflict with the type pointed to
558                        by the restricted pointer.  */
559                     DECL_POINTER_ALIAS_SET (decl)
560                       = pointed_to_alias_set;
561                   else
562                     {
563                       DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
564                       record_alias_subset (pointed_to_alias_set,
565                                            DECL_POINTER_ALIAS_SET (decl));
566                     }
567                 }
568
569               /* We use the alias set indicated in the declaration.  */
570               return DECL_POINTER_ALIAS_SET (decl);
571             }
572
573           /* If we have an INDIRECT_REF via a void pointer, we don't
574              know anything about what that might alias.  Likewise if the
575              pointer is marked that way.  */
576           else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE
577                    || (TYPE_REF_CAN_ALIAS_ALL
578                        (TREE_TYPE (TREE_OPERAND (inner, 0)))))
579             return 0;
580         }
581
582       /* For non-addressable fields we return the alias set of the
583          outermost object that could have its address taken.  If this
584          is an SFT use the precomputed value.  */
585       if (TREE_CODE (t) == STRUCT_FIELD_TAG
586           && SFT_NONADDRESSABLE_P (t))
587         return SFT_ALIAS_SET (t);
588
589       /* Otherwise, pick up the outermost object that we could have a pointer
590          to, processing conversions as above.  */
591       while (component_uses_parent_alias_set (t))
592         {
593           t = TREE_OPERAND (t, 0);
594           STRIP_NOPS (t);
595         }
596
597       /* If we've already determined the alias set for a decl, just return
598          it.  This is necessary for C++ anonymous unions, whose component
599          variables don't look like union members (boo!).  */
600       if (TREE_CODE (t) == VAR_DECL
601           && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
602         return MEM_ALIAS_SET (DECL_RTL (t));
603
604       /* Now all we care about is the type.  */
605       t = TREE_TYPE (t);
606     }
607
608   /* Variant qualifiers don't affect the alias set, so get the main
609      variant. If this is a type with a known alias set, return it.  */
610   t = TYPE_MAIN_VARIANT (t);
611   if (TYPE_ALIAS_SET_KNOWN_P (t))
612     return TYPE_ALIAS_SET (t);
613
614   /* See if the language has special handling for this type.  */
615   set = lang_hooks.get_alias_set (t);
616   if (set != -1)
617     return set;
618
619   /* There are no objects of FUNCTION_TYPE, so there's no point in
620      using up an alias set for them.  (There are, of course, pointers
621      and references to functions, but that's different.)  */
622   else if (TREE_CODE (t) == FUNCTION_TYPE
623            || TREE_CODE (t) == METHOD_TYPE)
624     set = 0;
625
626   /* Unless the language specifies otherwise, let vector types alias
627      their components.  This avoids some nasty type punning issues in
628      normal usage.  And indeed lets vectors be treated more like an
629      array slice.  */
630   else if (TREE_CODE (t) == VECTOR_TYPE)
631     set = get_alias_set (TREE_TYPE (t));
632
633   else
634     /* Otherwise make a new alias set for this type.  */
635     set = new_alias_set ();
636
637   TYPE_ALIAS_SET (t) = set;
638
639   /* If this is an aggregate type, we must record any component aliasing
640      information.  */
641   if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
642     record_component_aliases (t);
643
644   return set;
645 }
646
647 /* Return a brand-new alias set.  */
648
649 HOST_WIDE_INT
650 new_alias_set (void)
651 {
652   if (flag_strict_aliasing)
653     {
654       if (alias_sets == 0)
655         VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
656       VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
657       return VEC_length (alias_set_entry, alias_sets) - 1;
658     }
659   else
660     return 0;
661 }
662
663 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
664    not everything that aliases SUPERSET also aliases SUBSET.  For example,
665    in C, a store to an `int' can alias a load of a structure containing an
666    `int', and vice versa.  But it can't alias a load of a 'double' member
667    of the same structure.  Here, the structure would be the SUPERSET and
668    `int' the SUBSET.  This relationship is also described in the comment at
669    the beginning of this file.
670
671    This function should be called only once per SUPERSET/SUBSET pair.
672
673    It is illegal for SUPERSET to be zero; everything is implicitly a
674    subset of alias set zero.  */
675
676 static void
677 record_alias_subset (HOST_WIDE_INT superset, HOST_WIDE_INT subset)
678 {
679   alias_set_entry superset_entry;
680   alias_set_entry subset_entry;
681
682   /* It is possible in complex type situations for both sets to be the same,
683      in which case we can ignore this operation.  */
684   if (superset == subset)
685     return;
686
687   gcc_assert (superset);
688
689   superset_entry = get_alias_set_entry (superset);
690   if (superset_entry == 0)
691     {
692       /* Create an entry for the SUPERSET, so that we have a place to
693          attach the SUBSET.  */
694       superset_entry = ggc_alloc (sizeof (struct alias_set_entry));
695       superset_entry->alias_set = superset;
696       superset_entry->children
697         = splay_tree_new_ggc (splay_tree_compare_ints);
698       superset_entry->has_zero_child = 0;
699       VEC_replace (alias_set_entry, alias_sets, superset, superset_entry);
700     }
701
702   if (subset == 0)
703     superset_entry->has_zero_child = 1;
704   else
705     {
706       subset_entry = get_alias_set_entry (subset);
707       /* If there is an entry for the subset, enter all of its children
708          (if they are not already present) as children of the SUPERSET.  */
709       if (subset_entry)
710         {
711           if (subset_entry->has_zero_child)
712             superset_entry->has_zero_child = 1;
713
714           splay_tree_foreach (subset_entry->children, insert_subset_children,
715                               superset_entry->children);
716         }
717
718       /* Enter the SUBSET itself as a child of the SUPERSET.  */
719       splay_tree_insert (superset_entry->children,
720                          (splay_tree_key) subset, 0);
721     }
722 }
723
724 /* Record that component types of TYPE, if any, are part of that type for
725    aliasing purposes.  For record types, we only record component types
726    for fields that are marked addressable.  For array types, we always
727    record the component types, so the front end should not call this
728    function if the individual component aren't addressable.  */
729
730 void
731 record_component_aliases (tree type)
732 {
733   HOST_WIDE_INT superset = get_alias_set (type);
734   tree field;
735
736   if (superset == 0)
737     return;
738
739   switch (TREE_CODE (type))
740     {
741     case ARRAY_TYPE:
742       if (! TYPE_NONALIASED_COMPONENT (type))
743         record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
744       break;
745
746     case RECORD_TYPE:
747     case UNION_TYPE:
748     case QUAL_UNION_TYPE:
749       /* Recursively record aliases for the base classes, if there are any.  */
750       if (TYPE_BINFO (type))
751         {
752           int i;
753           tree binfo, base_binfo;
754
755           for (binfo = TYPE_BINFO (type), i = 0;
756                BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
757             record_alias_subset (superset,
758                                  get_alias_set (BINFO_TYPE (base_binfo)));
759         }
760       for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
761         if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
762           record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
763       break;
764
765     case COMPLEX_TYPE:
766       record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
767       break;
768
769     default:
770       break;
771     }
772 }
773
774 /* Allocate an alias set for use in storing and reading from the varargs
775    spill area.  */
776
777 static GTY(()) HOST_WIDE_INT varargs_set = -1;
778
779 HOST_WIDE_INT
780 get_varargs_alias_set (void)
781 {
782 #if 1
783   /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
784      varargs alias set to an INDIRECT_REF (FIXME!), so we can't
785      consistently use the varargs alias set for loads from the varargs
786      area.  So don't use it anywhere.  */
787   return 0;
788 #else
789   if (varargs_set == -1)
790     varargs_set = new_alias_set ();
791
792   return varargs_set;
793 #endif
794 }
795
796 /* Likewise, but used for the fixed portions of the frame, e.g., register
797    save areas.  */
798
799 static GTY(()) HOST_WIDE_INT frame_set = -1;
800
801 HOST_WIDE_INT
802 get_frame_alias_set (void)
803 {
804   if (frame_set == -1)
805     frame_set = new_alias_set ();
806
807   return frame_set;
808 }
809
810 /* Inside SRC, the source of a SET, find a base address.  */
811
812 static rtx
813 find_base_value (rtx src)
814 {
815   unsigned int regno;
816
817   switch (GET_CODE (src))
818     {
819     case SYMBOL_REF:
820     case LABEL_REF:
821       return src;
822
823     case REG:
824       regno = REGNO (src);
825       /* At the start of a function, argument registers have known base
826          values which may be lost later.  Returning an ADDRESS
827          expression here allows optimization based on argument values
828          even when the argument registers are used for other purposes.  */
829       if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
830         return new_reg_base_value[regno];
831
832       /* If a pseudo has a known base value, return it.  Do not do this
833          for non-fixed hard regs since it can result in a circular
834          dependency chain for registers which have values at function entry.
835
836          The test above is not sufficient because the scheduler may move
837          a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN.  */
838       if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
839           && regno < VEC_length (rtx, reg_base_value))
840         {
841           /* If we're inside init_alias_analysis, use new_reg_base_value
842              to reduce the number of relaxation iterations.  */
843           if (new_reg_base_value && new_reg_base_value[regno]
844               && DF_REG_DEF_COUNT (regno) == 1)
845             return new_reg_base_value[regno];
846
847           if (VEC_index (rtx, reg_base_value, regno))
848             return VEC_index (rtx, reg_base_value, regno);
849         }
850
851       return 0;
852
853     case MEM:
854       /* Check for an argument passed in memory.  Only record in the
855          copying-arguments block; it is too hard to track changes
856          otherwise.  */
857       if (copying_arguments
858           && (XEXP (src, 0) == arg_pointer_rtx
859               || (GET_CODE (XEXP (src, 0)) == PLUS
860                   && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
861         return gen_rtx_ADDRESS (VOIDmode, src);
862       return 0;
863
864     case CONST:
865       src = XEXP (src, 0);
866       if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
867         break;
868
869       /* ... fall through ...  */
870
871     case PLUS:
872     case MINUS:
873       {
874         rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
875
876         /* If either operand is a REG that is a known pointer, then it
877            is the base.  */
878         if (REG_P (src_0) && REG_POINTER (src_0))
879           return find_base_value (src_0);
880         if (REG_P (src_1) && REG_POINTER (src_1))
881           return find_base_value (src_1);
882
883         /* If either operand is a REG, then see if we already have
884            a known value for it.  */
885         if (REG_P (src_0))
886           {
887             temp = find_base_value (src_0);
888             if (temp != 0)
889               src_0 = temp;
890           }
891
892         if (REG_P (src_1))
893           {
894             temp = find_base_value (src_1);
895             if (temp!= 0)
896               src_1 = temp;
897           }
898
899         /* If either base is named object or a special address
900            (like an argument or stack reference), then use it for the
901            base term.  */
902         if (src_0 != 0
903             && (GET_CODE (src_0) == SYMBOL_REF
904                 || GET_CODE (src_0) == LABEL_REF
905                 || (GET_CODE (src_0) == ADDRESS
906                     && GET_MODE (src_0) != VOIDmode)))
907           return src_0;
908
909         if (src_1 != 0
910             && (GET_CODE (src_1) == SYMBOL_REF
911                 || GET_CODE (src_1) == LABEL_REF
912                 || (GET_CODE (src_1) == ADDRESS
913                     && GET_MODE (src_1) != VOIDmode)))
914           return src_1;
915
916         /* Guess which operand is the base address:
917            If either operand is a symbol, then it is the base.  If
918            either operand is a CONST_INT, then the other is the base.  */
919         if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0))
920           return find_base_value (src_0);
921         else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1))
922           return find_base_value (src_1);
923
924         return 0;
925       }
926
927     case LO_SUM:
928       /* The standard form is (lo_sum reg sym) so look only at the
929          second operand.  */
930       return find_base_value (XEXP (src, 1));
931
932     case AND:
933       /* If the second operand is constant set the base
934          address to the first operand.  */
935       if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
936         return find_base_value (XEXP (src, 0));
937       return 0;
938
939     case TRUNCATE:
940       if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
941         break;
942       /* Fall through.  */
943     case HIGH:
944     case PRE_INC:
945     case PRE_DEC:
946     case POST_INC:
947     case POST_DEC:
948     case PRE_MODIFY:
949     case POST_MODIFY:
950       return find_base_value (XEXP (src, 0));
951
952     case ZERO_EXTEND:
953     case SIGN_EXTEND:   /* used for NT/Alpha pointers */
954       {
955         rtx temp = find_base_value (XEXP (src, 0));
956
957         if (temp != 0 && CONSTANT_P (temp))
958           temp = convert_memory_address (Pmode, temp);
959
960         return temp;
961       }
962
963     default:
964       break;
965     }
966
967   return 0;
968 }
969
970 /* Called from init_alias_analysis indirectly through note_stores.  */
971
972 /* While scanning insns to find base values, reg_seen[N] is nonzero if
973    register N has been set in this function.  */
974 static char *reg_seen;
975
976 /* Addresses which are known not to alias anything else are identified
977    by a unique integer.  */
978 static int unique_id;
979
980 static void
981 record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
982 {
983   unsigned regno;
984   rtx src;
985   int n;
986
987   if (!REG_P (dest))
988     return;
989
990   regno = REGNO (dest);
991
992   gcc_assert (regno < VEC_length (rtx, reg_base_value));
993
994   /* If this spans multiple hard registers, then we must indicate that every
995      register has an unusable value.  */
996   if (regno < FIRST_PSEUDO_REGISTER)
997     n = hard_regno_nregs[regno][GET_MODE (dest)];
998   else
999     n = 1;
1000   if (n != 1)
1001     {
1002       while (--n >= 0)
1003         {
1004           reg_seen[regno + n] = 1;
1005           new_reg_base_value[regno + n] = 0;
1006         }
1007       return;
1008     }
1009
1010   if (set)
1011     {
1012       /* A CLOBBER wipes out any old value but does not prevent a previously
1013          unset register from acquiring a base address (i.e. reg_seen is not
1014          set).  */
1015       if (GET_CODE (set) == CLOBBER)
1016         {
1017           new_reg_base_value[regno] = 0;
1018           return;
1019         }
1020       src = SET_SRC (set);
1021     }
1022   else
1023     {
1024       if (reg_seen[regno])
1025         {
1026           new_reg_base_value[regno] = 0;
1027           return;
1028         }
1029       reg_seen[regno] = 1;
1030       new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
1031                                                    GEN_INT (unique_id++));
1032       return;
1033     }
1034
1035   /* If this is not the first set of REGNO, see whether the new value
1036      is related to the old one.  There are two cases of interest:
1037
1038         (1) The register might be assigned an entirely new value
1039             that has the same base term as the original set.
1040
1041         (2) The set might be a simple self-modification that
1042             cannot change REGNO's base value.
1043
1044      If neither case holds, reject the original base value as invalid.
1045      Note that the following situation is not detected:
1046
1047          extern int x, y;  int *p = &x; p += (&y-&x);
1048
1049      ANSI C does not allow computing the difference of addresses
1050      of distinct top level objects.  */
1051   if (new_reg_base_value[regno] != 0
1052       && find_base_value (src) != new_reg_base_value[regno])
1053     switch (GET_CODE (src))
1054       {
1055       case LO_SUM:
1056       case MINUS:
1057         if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1058           new_reg_base_value[regno] = 0;
1059         break;
1060       case PLUS:
1061         /* If the value we add in the PLUS is also a valid base value,
1062            this might be the actual base value, and the original value
1063            an index.  */
1064         {
1065           rtx other = NULL_RTX;
1066
1067           if (XEXP (src, 0) == dest)
1068             other = XEXP (src, 1);
1069           else if (XEXP (src, 1) == dest)
1070             other = XEXP (src, 0);
1071
1072           if (! other || find_base_value (other))
1073             new_reg_base_value[regno] = 0;
1074           break;
1075         }
1076       case AND:
1077         if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
1078           new_reg_base_value[regno] = 0;
1079         break;
1080       default:
1081         new_reg_base_value[regno] = 0;
1082         break;
1083       }
1084   /* If this is the first set of a register, record the value.  */
1085   else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1086            && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1087     new_reg_base_value[regno] = find_base_value (src);
1088
1089   reg_seen[regno] = 1;
1090 }
1091
1092 /* If a value is known for REGNO, return it.  */
1093
1094 rtx
1095 get_reg_known_value (unsigned int regno)
1096 {
1097   if (regno >= FIRST_PSEUDO_REGISTER)
1098     {
1099       regno -= FIRST_PSEUDO_REGISTER;
1100       if (regno < reg_known_value_size)
1101         return reg_known_value[regno];
1102     }
1103   return NULL;
1104 }
1105
1106 /* Set it.  */
1107
1108 static void
1109 set_reg_known_value (unsigned int regno, rtx val)
1110 {
1111   if (regno >= FIRST_PSEUDO_REGISTER)
1112     {
1113       regno -= FIRST_PSEUDO_REGISTER;
1114       if (regno < reg_known_value_size)
1115         reg_known_value[regno] = val;
1116     }
1117 }
1118
1119 /* Similarly for reg_known_equiv_p.  */
1120
1121 bool
1122 get_reg_known_equiv_p (unsigned int regno)
1123 {
1124   if (regno >= FIRST_PSEUDO_REGISTER)
1125     {
1126       regno -= FIRST_PSEUDO_REGISTER;
1127       if (regno < reg_known_value_size)
1128         return reg_known_equiv_p[regno];
1129     }
1130   return false;
1131 }
1132
1133 static void
1134 set_reg_known_equiv_p (unsigned int regno, bool val)
1135 {
1136   if (regno >= FIRST_PSEUDO_REGISTER)
1137     {
1138       regno -= FIRST_PSEUDO_REGISTER;
1139       if (regno < reg_known_value_size)
1140         reg_known_equiv_p[regno] = val;
1141     }
1142 }
1143
1144
1145 /* Returns a canonical version of X, from the point of view alias
1146    analysis.  (For example, if X is a MEM whose address is a register,
1147    and the register has a known value (say a SYMBOL_REF), then a MEM
1148    whose address is the SYMBOL_REF is returned.)  */
1149
1150 rtx
1151 canon_rtx (rtx x)
1152 {
1153   /* Recursively look for equivalences.  */
1154   if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1155     {
1156       rtx t = get_reg_known_value (REGNO (x));
1157       if (t == x)
1158         return x;
1159       if (t)
1160         return canon_rtx (t);
1161     }
1162
1163   if (GET_CODE (x) == PLUS)
1164     {
1165       rtx x0 = canon_rtx (XEXP (x, 0));
1166       rtx x1 = canon_rtx (XEXP (x, 1));
1167
1168       if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1169         {
1170           if (GET_CODE (x0) == CONST_INT)
1171             return plus_constant (x1, INTVAL (x0));
1172           else if (GET_CODE (x1) == CONST_INT)
1173             return plus_constant (x0, INTVAL (x1));
1174           return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1175         }
1176     }
1177
1178   /* This gives us much better alias analysis when called from
1179      the loop optimizer.   Note we want to leave the original
1180      MEM alone, but need to return the canonicalized MEM with
1181      all the flags with their original values.  */
1182   else if (MEM_P (x))
1183     x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1184
1185   return x;
1186 }
1187
1188 /* Return 1 if X and Y are identical-looking rtx's.
1189    Expect that X and Y has been already canonicalized.
1190
1191    We use the data in reg_known_value above to see if two registers with
1192    different numbers are, in fact, equivalent.  */
1193
1194 static int
1195 rtx_equal_for_memref_p (rtx x, rtx y)
1196 {
1197   int i;
1198   int j;
1199   enum rtx_code code;
1200   const char *fmt;
1201
1202   if (x == 0 && y == 0)
1203     return 1;
1204   if (x == 0 || y == 0)
1205     return 0;
1206
1207   if (x == y)
1208     return 1;
1209
1210   code = GET_CODE (x);
1211   /* Rtx's of different codes cannot be equal.  */
1212   if (code != GET_CODE (y))
1213     return 0;
1214
1215   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1216      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
1217
1218   if (GET_MODE (x) != GET_MODE (y))
1219     return 0;
1220
1221   /* Some RTL can be compared without a recursive examination.  */
1222   switch (code)
1223     {
1224     case REG:
1225       return REGNO (x) == REGNO (y);
1226
1227     case LABEL_REF:
1228       return XEXP (x, 0) == XEXP (y, 0);
1229
1230     case SYMBOL_REF:
1231       return XSTR (x, 0) == XSTR (y, 0);
1232
1233     case VALUE:
1234     case CONST_INT:
1235     case CONST_DOUBLE:
1236       /* There's no need to compare the contents of CONST_DOUBLEs or
1237          CONST_INTs because pointer equality is a good enough
1238          comparison for these nodes.  */
1239       return 0;
1240
1241     default:
1242       break;
1243     }
1244
1245   /* canon_rtx knows how to handle plus.  No need to canonicalize.  */
1246   if (code == PLUS)
1247     return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1248              && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1249             || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1250                 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1251   /* For commutative operations, the RTX match if the operand match in any
1252      order.  Also handle the simple binary and unary cases without a loop.  */
1253   if (COMMUTATIVE_P (x))
1254     {
1255       rtx xop0 = canon_rtx (XEXP (x, 0));
1256       rtx yop0 = canon_rtx (XEXP (y, 0));
1257       rtx yop1 = canon_rtx (XEXP (y, 1));
1258
1259       return ((rtx_equal_for_memref_p (xop0, yop0)
1260                && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1261               || (rtx_equal_for_memref_p (xop0, yop1)
1262                   && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1263     }
1264   else if (NON_COMMUTATIVE_P (x))
1265     {
1266       return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1267                                       canon_rtx (XEXP (y, 0)))
1268               && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1269                                          canon_rtx (XEXP (y, 1))));
1270     }
1271   else if (UNARY_P (x))
1272     return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1273                                    canon_rtx (XEXP (y, 0)));
1274
1275   /* Compare the elements.  If any pair of corresponding elements
1276      fail to match, return 0 for the whole things.
1277
1278      Limit cases to types which actually appear in addresses.  */
1279
1280   fmt = GET_RTX_FORMAT (code);
1281   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1282     {
1283       switch (fmt[i])
1284         {
1285         case 'i':
1286           if (XINT (x, i) != XINT (y, i))
1287             return 0;
1288           break;
1289
1290         case 'E':
1291           /* Two vectors must have the same length.  */
1292           if (XVECLEN (x, i) != XVECLEN (y, i))
1293             return 0;
1294
1295           /* And the corresponding elements must match.  */
1296           for (j = 0; j < XVECLEN (x, i); j++)
1297             if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1298                                         canon_rtx (XVECEXP (y, i, j))) == 0)
1299               return 0;
1300           break;
1301
1302         case 'e':
1303           if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1304                                       canon_rtx (XEXP (y, i))) == 0)
1305             return 0;
1306           break;
1307
1308           /* This can happen for asm operands.  */
1309         case 's':
1310           if (strcmp (XSTR (x, i), XSTR (y, i)))
1311             return 0;
1312           break;
1313
1314         /* This can happen for an asm which clobbers memory.  */
1315         case '0':
1316           break;
1317
1318           /* It is believed that rtx's at this level will never
1319              contain anything but integers and other rtx's,
1320              except for within LABEL_REFs and SYMBOL_REFs.  */
1321         default:
1322           gcc_unreachable ();
1323         }
1324     }
1325   return 1;
1326 }
1327
1328 rtx
1329 find_base_term (rtx x)
1330 {
1331   cselib_val *val;
1332   struct elt_loc_list *l;
1333
1334 #if defined (FIND_BASE_TERM)
1335   /* Try machine-dependent ways to find the base term.  */
1336   x = FIND_BASE_TERM (x);
1337 #endif
1338
1339   switch (GET_CODE (x))
1340     {
1341     case REG:
1342       return REG_BASE_VALUE (x);
1343
1344     case TRUNCATE:
1345       if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1346         return 0;
1347       /* Fall through.  */
1348     case HIGH:
1349     case PRE_INC:
1350     case PRE_DEC:
1351     case POST_INC:
1352     case POST_DEC:
1353     case PRE_MODIFY:
1354     case POST_MODIFY:
1355       return find_base_term (XEXP (x, 0));
1356
1357     case ZERO_EXTEND:
1358     case SIGN_EXTEND:   /* Used for Alpha/NT pointers */
1359       {
1360         rtx temp = find_base_term (XEXP (x, 0));
1361
1362         if (temp != 0 && CONSTANT_P (temp))
1363           temp = convert_memory_address (Pmode, temp);
1364
1365         return temp;
1366       }
1367
1368     case VALUE:
1369       val = CSELIB_VAL_PTR (x);
1370       if (!val)
1371         return 0;
1372       for (l = val->locs; l; l = l->next)
1373         if ((x = find_base_term (l->loc)) != 0)
1374           return x;
1375       return 0;
1376
1377     case CONST:
1378       x = XEXP (x, 0);
1379       if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1380         return 0;
1381       /* Fall through.  */
1382     case LO_SUM:
1383     case PLUS:
1384     case MINUS:
1385       {
1386         rtx tmp1 = XEXP (x, 0);
1387         rtx tmp2 = XEXP (x, 1);
1388
1389         /* This is a little bit tricky since we have to determine which of
1390            the two operands represents the real base address.  Otherwise this
1391            routine may return the index register instead of the base register.
1392
1393            That may cause us to believe no aliasing was possible, when in
1394            fact aliasing is possible.
1395
1396            We use a few simple tests to guess the base register.  Additional
1397            tests can certainly be added.  For example, if one of the operands
1398            is a shift or multiply, then it must be the index register and the
1399            other operand is the base register.  */
1400
1401         if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1402           return find_base_term (tmp2);
1403
1404         /* If either operand is known to be a pointer, then use it
1405            to determine the base term.  */
1406         if (REG_P (tmp1) && REG_POINTER (tmp1))
1407           return find_base_term (tmp1);
1408
1409         if (REG_P (tmp2) && REG_POINTER (tmp2))
1410           return find_base_term (tmp2);
1411
1412         /* Neither operand was known to be a pointer.  Go ahead and find the
1413            base term for both operands.  */
1414         tmp1 = find_base_term (tmp1);
1415         tmp2 = find_base_term (tmp2);
1416
1417         /* If either base term is named object or a special address
1418            (like an argument or stack reference), then use it for the
1419            base term.  */
1420         if (tmp1 != 0
1421             && (GET_CODE (tmp1) == SYMBOL_REF
1422                 || GET_CODE (tmp1) == LABEL_REF
1423                 || (GET_CODE (tmp1) == ADDRESS
1424                     && GET_MODE (tmp1) != VOIDmode)))
1425           return tmp1;
1426
1427         if (tmp2 != 0
1428             && (GET_CODE (tmp2) == SYMBOL_REF
1429                 || GET_CODE (tmp2) == LABEL_REF
1430                 || (GET_CODE (tmp2) == ADDRESS
1431                     && GET_MODE (tmp2) != VOIDmode)))
1432           return tmp2;
1433
1434         /* We could not determine which of the two operands was the
1435            base register and which was the index.  So we can determine
1436            nothing from the base alias check.  */
1437         return 0;
1438       }
1439
1440     case AND:
1441       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0)
1442         return find_base_term (XEXP (x, 0));
1443       return 0;
1444
1445     case SYMBOL_REF:
1446     case LABEL_REF:
1447       return x;
1448
1449     default:
1450       return 0;
1451     }
1452 }
1453
1454 /* Return 0 if the addresses X and Y are known to point to different
1455    objects, 1 if they might be pointers to the same object.  */
1456
1457 static int
1458 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1459                   enum machine_mode y_mode)
1460 {
1461   rtx x_base = find_base_term (x);
1462   rtx y_base = find_base_term (y);
1463
1464   /* If the address itself has no known base see if a known equivalent
1465      value has one.  If either address still has no known base, nothing
1466      is known about aliasing.  */
1467   if (x_base == 0)
1468     {
1469       rtx x_c;
1470
1471       if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1472         return 1;
1473
1474       x_base = find_base_term (x_c);
1475       if (x_base == 0)
1476         return 1;
1477     }
1478
1479   if (y_base == 0)
1480     {
1481       rtx y_c;
1482       if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1483         return 1;
1484
1485       y_base = find_base_term (y_c);
1486       if (y_base == 0)
1487         return 1;
1488     }
1489
1490   /* If the base addresses are equal nothing is known about aliasing.  */
1491   if (rtx_equal_p (x_base, y_base))
1492     return 1;
1493
1494   /* The base addresses of the read and write are different expressions.
1495      If they are both symbols and they are not accessed via AND, there is
1496      no conflict.  We can bring knowledge of object alignment into play
1497      here.  For example, on alpha, "char a, b;" can alias one another,
1498      though "char a; long b;" cannot.  */
1499   if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1500     {
1501       if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1502         return 1;
1503       if (GET_CODE (x) == AND
1504           && (GET_CODE (XEXP (x, 1)) != CONST_INT
1505               || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1506         return 1;
1507       if (GET_CODE (y) == AND
1508           && (GET_CODE (XEXP (y, 1)) != CONST_INT
1509               || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1510         return 1;
1511       /* Differing symbols never alias.  */
1512       return 0;
1513     }
1514
1515   /* If one address is a stack reference there can be no alias:
1516      stack references using different base registers do not alias,
1517      a stack reference can not alias a parameter, and a stack reference
1518      can not alias a global.  */
1519   if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1520       || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1521     return 0;
1522
1523   if (! flag_argument_noalias)
1524     return 1;
1525
1526   if (flag_argument_noalias > 1)
1527     return 0;
1528
1529   /* Weak noalias assertion (arguments are distinct, but may match globals).  */
1530   return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
1531 }
1532
1533 /* Convert the address X into something we can use.  This is done by returning
1534    it unchanged unless it is a value; in the latter case we call cselib to get
1535    a more useful rtx.  */
1536
1537 rtx
1538 get_addr (rtx x)
1539 {
1540   cselib_val *v;
1541   struct elt_loc_list *l;
1542
1543   if (GET_CODE (x) != VALUE)
1544     return x;
1545   v = CSELIB_VAL_PTR (x);
1546   if (v)
1547     {
1548       for (l = v->locs; l; l = l->next)
1549         if (CONSTANT_P (l->loc))
1550           return l->loc;
1551       for (l = v->locs; l; l = l->next)
1552         if (!REG_P (l->loc) && !MEM_P (l->loc))
1553           return l->loc;
1554       if (v->locs)
1555         return v->locs->loc;
1556     }
1557   return x;
1558 }
1559
1560 /*  Return the address of the (N_REFS + 1)th memory reference to ADDR
1561     where SIZE is the size in bytes of the memory reference.  If ADDR
1562     is not modified by the memory reference then ADDR is returned.  */
1563
1564 static rtx
1565 addr_side_effect_eval (rtx addr, int size, int n_refs)
1566 {
1567   int offset = 0;
1568
1569   switch (GET_CODE (addr))
1570     {
1571     case PRE_INC:
1572       offset = (n_refs + 1) * size;
1573       break;
1574     case PRE_DEC:
1575       offset = -(n_refs + 1) * size;
1576       break;
1577     case POST_INC:
1578       offset = n_refs * size;
1579       break;
1580     case POST_DEC:
1581       offset = -n_refs * size;
1582       break;
1583
1584     default:
1585       return addr;
1586     }
1587
1588   if (offset)
1589     addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1590                          GEN_INT (offset));
1591   else
1592     addr = XEXP (addr, 0);
1593   addr = canon_rtx (addr);
1594
1595   return addr;
1596 }
1597
1598 /* Return nonzero if X and Y (memory addresses) could reference the
1599    same location in memory.  C is an offset accumulator.  When
1600    C is nonzero, we are testing aliases between X and Y + C.
1601    XSIZE is the size in bytes of the X reference,
1602    similarly YSIZE is the size in bytes for Y.
1603    Expect that canon_rtx has been already called for X and Y.
1604
1605    If XSIZE or YSIZE is zero, we do not know the amount of memory being
1606    referenced (the reference was BLKmode), so make the most pessimistic
1607    assumptions.
1608
1609    If XSIZE or YSIZE is negative, we may access memory outside the object
1610    being referenced as a side effect.  This can happen when using AND to
1611    align memory references, as is done on the Alpha.
1612
1613    Nice to notice that varying addresses cannot conflict with fp if no
1614    local variables had their addresses taken, but that's too hard now.  */
1615
1616 static int
1617 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1618 {
1619   if (GET_CODE (x) == VALUE)
1620     x = get_addr (x);
1621   if (GET_CODE (y) == VALUE)
1622     y = get_addr (y);
1623   if (GET_CODE (x) == HIGH)
1624     x = XEXP (x, 0);
1625   else if (GET_CODE (x) == LO_SUM)
1626     x = XEXP (x, 1);
1627   else
1628     x = addr_side_effect_eval (x, xsize, 0);
1629   if (GET_CODE (y) == HIGH)
1630     y = XEXP (y, 0);
1631   else if (GET_CODE (y) == LO_SUM)
1632     y = XEXP (y, 1);
1633   else
1634     y = addr_side_effect_eval (y, ysize, 0);
1635
1636   if (rtx_equal_for_memref_p (x, y))
1637     {
1638       if (xsize <= 0 || ysize <= 0)
1639         return 1;
1640       if (c >= 0 && xsize > c)
1641         return 1;
1642       if (c < 0 && ysize+c > 0)
1643         return 1;
1644       return 0;
1645     }
1646
1647   /* This code used to check for conflicts involving stack references and
1648      globals but the base address alias code now handles these cases.  */
1649
1650   if (GET_CODE (x) == PLUS)
1651     {
1652       /* The fact that X is canonicalized means that this
1653          PLUS rtx is canonicalized.  */
1654       rtx x0 = XEXP (x, 0);
1655       rtx x1 = XEXP (x, 1);
1656
1657       if (GET_CODE (y) == PLUS)
1658         {
1659           /* The fact that Y is canonicalized means that this
1660              PLUS rtx is canonicalized.  */
1661           rtx y0 = XEXP (y, 0);
1662           rtx y1 = XEXP (y, 1);
1663
1664           if (rtx_equal_for_memref_p (x1, y1))
1665             return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1666           if (rtx_equal_for_memref_p (x0, y0))
1667             return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1668           if (GET_CODE (x1) == CONST_INT)
1669             {
1670               if (GET_CODE (y1) == CONST_INT)
1671                 return memrefs_conflict_p (xsize, x0, ysize, y0,
1672                                            c - INTVAL (x1) + INTVAL (y1));
1673               else
1674                 return memrefs_conflict_p (xsize, x0, ysize, y,
1675                                            c - INTVAL (x1));
1676             }
1677           else if (GET_CODE (y1) == CONST_INT)
1678             return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1679
1680           return 1;
1681         }
1682       else if (GET_CODE (x1) == CONST_INT)
1683         return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1684     }
1685   else if (GET_CODE (y) == PLUS)
1686     {
1687       /* The fact that Y is canonicalized means that this
1688          PLUS rtx is canonicalized.  */
1689       rtx y0 = XEXP (y, 0);
1690       rtx y1 = XEXP (y, 1);
1691
1692       if (GET_CODE (y1) == CONST_INT)
1693         return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1694       else
1695         return 1;
1696     }
1697
1698   if (GET_CODE (x) == GET_CODE (y))
1699     switch (GET_CODE (x))
1700       {
1701       case MULT:
1702         {
1703           /* Handle cases where we expect the second operands to be the
1704              same, and check only whether the first operand would conflict
1705              or not.  */
1706           rtx x0, y0;
1707           rtx x1 = canon_rtx (XEXP (x, 1));
1708           rtx y1 = canon_rtx (XEXP (y, 1));
1709           if (! rtx_equal_for_memref_p (x1, y1))
1710             return 1;
1711           x0 = canon_rtx (XEXP (x, 0));
1712           y0 = canon_rtx (XEXP (y, 0));
1713           if (rtx_equal_for_memref_p (x0, y0))
1714             return (xsize == 0 || ysize == 0
1715                     || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1716
1717           /* Can't properly adjust our sizes.  */
1718           if (GET_CODE (x1) != CONST_INT)
1719             return 1;
1720           xsize /= INTVAL (x1);
1721           ysize /= INTVAL (x1);
1722           c /= INTVAL (x1);
1723           return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1724         }
1725
1726       default:
1727         break;
1728       }
1729
1730   /* Treat an access through an AND (e.g. a subword access on an Alpha)
1731      as an access with indeterminate size.  Assume that references
1732      besides AND are aligned, so if the size of the other reference is
1733      at least as large as the alignment, assume no other overlap.  */
1734   if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
1735     {
1736       if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1737         xsize = -1;
1738       return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1739     }
1740   if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
1741     {
1742       /* ??? If we are indexing far enough into the array/structure, we
1743          may yet be able to determine that we can not overlap.  But we
1744          also need to that we are far enough from the end not to overlap
1745          a following reference, so we do nothing with that for now.  */
1746       if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1747         ysize = -1;
1748       return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1749     }
1750
1751   if (CONSTANT_P (x))
1752     {
1753       if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
1754         {
1755           c += (INTVAL (y) - INTVAL (x));
1756           return (xsize <= 0 || ysize <= 0
1757                   || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1758         }
1759
1760       if (GET_CODE (x) == CONST)
1761         {
1762           if (GET_CODE (y) == CONST)
1763             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1764                                        ysize, canon_rtx (XEXP (y, 0)), c);
1765           else
1766             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1767                                        ysize, y, c);
1768         }
1769       if (GET_CODE (y) == CONST)
1770         return memrefs_conflict_p (xsize, x, ysize,
1771                                    canon_rtx (XEXP (y, 0)), c);
1772
1773       if (CONSTANT_P (y))
1774         return (xsize <= 0 || ysize <= 0
1775                 || (rtx_equal_for_memref_p (x, y)
1776                     && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1777
1778       return 1;
1779     }
1780   return 1;
1781 }
1782
1783 /* Functions to compute memory dependencies.
1784
1785    Since we process the insns in execution order, we can build tables
1786    to keep track of what registers are fixed (and not aliased), what registers
1787    are varying in known ways, and what registers are varying in unknown
1788    ways.
1789
1790    If both memory references are volatile, then there must always be a
1791    dependence between the two references, since their order can not be
1792    changed.  A volatile and non-volatile reference can be interchanged
1793    though.
1794
1795    A MEM_IN_STRUCT reference at a non-AND varying address can never
1796    conflict with a non-MEM_IN_STRUCT reference at a fixed address.  We
1797    also must allow AND addresses, because they may generate accesses
1798    outside the object being referenced.  This is used to generate
1799    aligned addresses from unaligned addresses, for instance, the alpha
1800    storeqi_unaligned pattern.  */
1801
1802 /* Read dependence: X is read after read in MEM takes place.  There can
1803    only be a dependence here if both reads are volatile.  */
1804
1805 int
1806 read_dependence (const_rtx mem, const_rtx x)
1807 {
1808   return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
1809 }
1810
1811 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
1812    MEM2 is a reference to a structure at a varying address, or returns
1813    MEM2 if vice versa.  Otherwise, returns NULL_RTX.  If a non-NULL
1814    value is returned MEM1 and MEM2 can never alias.  VARIES_P is used
1815    to decide whether or not an address may vary; it should return
1816    nonzero whenever variation is possible.
1817    MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2.  */
1818
1819 static const_rtx
1820 fixed_scalar_and_varying_struct_p (const_rtx mem1, const_rtx mem2, rtx mem1_addr,
1821                                    rtx mem2_addr,
1822                                    bool (*varies_p) (const_rtx, bool))
1823 {
1824   if (! flag_strict_aliasing)
1825     return NULL_RTX;
1826
1827   if (MEM_ALIAS_SET (mem2)
1828       && MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
1829       && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
1830     /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
1831        varying address.  */
1832     return mem1;
1833
1834   if (MEM_ALIAS_SET (mem1)
1835       && MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
1836       && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
1837     /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
1838        varying address.  */
1839     return mem2;
1840
1841   return NULL_RTX;
1842 }
1843
1844 /* Returns nonzero if something about the mode or address format MEM1
1845    indicates that it might well alias *anything*.  */
1846
1847 static int
1848 aliases_everything_p (const_rtx mem)
1849 {
1850   if (GET_CODE (XEXP (mem, 0)) == AND)
1851     /* If the address is an AND, it's very hard to know at what it is
1852        actually pointing.  */
1853     return 1;
1854
1855   return 0;
1856 }
1857
1858 /* Return true if we can determine that the fields referenced cannot
1859    overlap for any pair of objects.  */
1860
1861 static bool
1862 nonoverlapping_component_refs_p (const_tree x, const_tree y)
1863 {
1864   const_tree fieldx, fieldy, typex, typey, orig_y;
1865
1866   do
1867     {
1868       /* The comparison has to be done at a common type, since we don't
1869          know how the inheritance hierarchy works.  */
1870       orig_y = y;
1871       do
1872         {
1873           fieldx = TREE_OPERAND (x, 1);
1874           typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
1875
1876           y = orig_y;
1877           do
1878             {
1879               fieldy = TREE_OPERAND (y, 1);
1880               typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
1881
1882               if (typex == typey)
1883                 goto found;
1884
1885               y = TREE_OPERAND (y, 0);
1886             }
1887           while (y && TREE_CODE (y) == COMPONENT_REF);
1888
1889           x = TREE_OPERAND (x, 0);
1890         }
1891       while (x && TREE_CODE (x) == COMPONENT_REF);
1892       /* Never found a common type.  */
1893       return false;
1894
1895     found:
1896       /* If we're left with accessing different fields of a structure,
1897          then no overlap.  */
1898       if (TREE_CODE (typex) == RECORD_TYPE
1899           && fieldx != fieldy)
1900         return true;
1901
1902       /* The comparison on the current field failed.  If we're accessing
1903          a very nested structure, look at the next outer level.  */
1904       x = TREE_OPERAND (x, 0);
1905       y = TREE_OPERAND (y, 0);
1906     }
1907   while (x && y
1908          && TREE_CODE (x) == COMPONENT_REF
1909          && TREE_CODE (y) == COMPONENT_REF);
1910
1911   return false;
1912 }
1913
1914 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it.  */
1915
1916 static tree
1917 decl_for_component_ref (tree x)
1918 {
1919   do
1920     {
1921       x = TREE_OPERAND (x, 0);
1922     }
1923   while (x && TREE_CODE (x) == COMPONENT_REF);
1924
1925   return x && DECL_P (x) ? x : NULL_TREE;
1926 }
1927
1928 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
1929    offset of the field reference.  */
1930
1931 static rtx
1932 adjust_offset_for_component_ref (tree x, rtx offset)
1933 {
1934   HOST_WIDE_INT ioffset;
1935
1936   if (! offset)
1937     return NULL_RTX;
1938
1939   ioffset = INTVAL (offset);
1940   do
1941     {
1942       tree offset = component_ref_field_offset (x);
1943       tree field = TREE_OPERAND (x, 1);
1944
1945       if (! host_integerp (offset, 1))
1946         return NULL_RTX;
1947       ioffset += (tree_low_cst (offset, 1)
1948                   + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
1949                      / BITS_PER_UNIT));
1950
1951       x = TREE_OPERAND (x, 0);
1952     }
1953   while (x && TREE_CODE (x) == COMPONENT_REF);
1954
1955   return GEN_INT (ioffset);
1956 }
1957
1958 /* Return nonzero if we can determine the exprs corresponding to memrefs
1959    X and Y and they do not overlap.  */
1960
1961 static int
1962 nonoverlapping_memrefs_p (const_rtx x, const_rtx y)
1963 {
1964   tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
1965   rtx rtlx, rtly;
1966   rtx basex, basey;
1967   rtx moffsetx, moffsety;
1968   HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
1969
1970   /* Unless both have exprs, we can't tell anything.  */
1971   if (exprx == 0 || expry == 0)
1972     return 0;
1973
1974   /* If both are field references, we may be able to determine something.  */
1975   if (TREE_CODE (exprx) == COMPONENT_REF
1976       && TREE_CODE (expry) == COMPONENT_REF
1977       && nonoverlapping_component_refs_p (exprx, expry))
1978     return 1;
1979
1980
1981   /* If the field reference test failed, look at the DECLs involved.  */
1982   moffsetx = MEM_OFFSET (x);
1983   if (TREE_CODE (exprx) == COMPONENT_REF)
1984     {
1985       if (TREE_CODE (expry) == VAR_DECL
1986           && POINTER_TYPE_P (TREE_TYPE (expry)))
1987         {
1988          tree field = TREE_OPERAND (exprx, 1);
1989          tree fieldcontext = DECL_FIELD_CONTEXT (field);
1990          if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
1991                                                        TREE_TYPE (field)))
1992            return 1;
1993         }
1994       {
1995         tree t = decl_for_component_ref (exprx);
1996         if (! t)
1997           return 0;
1998         moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
1999         exprx = t;
2000       }
2001     }
2002   else if (INDIRECT_REF_P (exprx))
2003     {
2004       exprx = TREE_OPERAND (exprx, 0);
2005       if (flag_argument_noalias < 2
2006           || TREE_CODE (exprx) != PARM_DECL)
2007         return 0;
2008     }
2009
2010   moffsety = MEM_OFFSET (y);
2011   if (TREE_CODE (expry) == COMPONENT_REF)
2012     {
2013       if (TREE_CODE (exprx) == VAR_DECL
2014           && POINTER_TYPE_P (TREE_TYPE (exprx)))
2015         {
2016          tree field = TREE_OPERAND (expry, 1);
2017          tree fieldcontext = DECL_FIELD_CONTEXT (field);
2018          if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
2019                                                        TREE_TYPE (field)))
2020            return 1;
2021         }
2022       {
2023         tree t = decl_for_component_ref (expry);
2024         if (! t)
2025           return 0;
2026         moffsety = adjust_offset_for_component_ref (expry, moffsety);
2027         expry = t;
2028       }
2029     }
2030   else if (INDIRECT_REF_P (expry))
2031     {
2032       expry = TREE_OPERAND (expry, 0);
2033       if (flag_argument_noalias < 2
2034           || TREE_CODE (expry) != PARM_DECL)
2035         return 0;
2036     }
2037
2038   if (! DECL_P (exprx) || ! DECL_P (expry))
2039     return 0;
2040
2041   rtlx = DECL_RTL (exprx);
2042   rtly = DECL_RTL (expry);
2043
2044   /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2045      can't overlap unless they are the same because we never reuse that part
2046      of the stack frame used for locals for spilled pseudos.  */
2047   if ((!MEM_P (rtlx) || !MEM_P (rtly))
2048       && ! rtx_equal_p (rtlx, rtly))
2049     return 1;
2050
2051   /* Get the base and offsets of both decls.  If either is a register, we
2052      know both are and are the same, so use that as the base.  The only
2053      we can avoid overlap is if we can deduce that they are nonoverlapping
2054      pieces of that decl, which is very rare.  */
2055   basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2056   if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT)
2057     offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2058
2059   basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2060   if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT)
2061     offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2062
2063   /* If the bases are different, we know they do not overlap if both
2064      are constants or if one is a constant and the other a pointer into the
2065      stack frame.  Otherwise a different base means we can't tell if they
2066      overlap or not.  */
2067   if (! rtx_equal_p (basex, basey))
2068     return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2069             || (CONSTANT_P (basex) && REG_P (basey)
2070                 && REGNO_PTR_FRAME_P (REGNO (basey)))
2071             || (CONSTANT_P (basey) && REG_P (basex)
2072                 && REGNO_PTR_FRAME_P (REGNO (basex))));
2073
2074   sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2075            : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2076            : -1);
2077   sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2078            : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2079            -1);
2080
2081   /* If we have an offset for either memref, it can update the values computed
2082      above.  */
2083   if (moffsetx)
2084     offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2085   if (moffsety)
2086     offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2087
2088   /* If a memref has both a size and an offset, we can use the smaller size.
2089      We can't do this if the offset isn't known because we must view this
2090      memref as being anywhere inside the DECL's MEM.  */
2091   if (MEM_SIZE (x) && moffsetx)
2092     sizex = INTVAL (MEM_SIZE (x));
2093   if (MEM_SIZE (y) && moffsety)
2094     sizey = INTVAL (MEM_SIZE (y));
2095
2096   /* Put the values of the memref with the lower offset in X's values.  */
2097   if (offsetx > offsety)
2098     {
2099       tem = offsetx, offsetx = offsety, offsety = tem;
2100       tem = sizex, sizex = sizey, sizey = tem;
2101     }
2102
2103   /* If we don't know the size of the lower-offset value, we can't tell
2104      if they conflict.  Otherwise, we do the test.  */
2105   return sizex >= 0 && offsety >= offsetx + sizex;
2106 }
2107
2108 /* True dependence: X is read after store in MEM takes place.  */
2109
2110 int
2111 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x,
2112                  bool (*varies) (const_rtx, bool))
2113 {
2114   rtx x_addr, mem_addr;
2115   rtx base;
2116
2117   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2118     return 1;
2119
2120   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2121      This is used in epilogue deallocation functions, and in cselib.  */
2122   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2123     return 1;
2124   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2125     return 1;
2126   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2127       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2128     return 1;
2129
2130   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2131     return 0;
2132
2133   /* Read-only memory is by definition never modified, and therefore can't
2134      conflict with anything.  We don't expect to find read-only set on MEM,
2135      but stupid user tricks can produce them, so don't die.  */
2136   if (MEM_READONLY_P (x))
2137     return 0;
2138
2139   if (nonoverlapping_memrefs_p (mem, x))
2140     return 0;
2141
2142   if (mem_mode == VOIDmode)
2143     mem_mode = GET_MODE (mem);
2144
2145   x_addr = get_addr (XEXP (x, 0));
2146   mem_addr = get_addr (XEXP (mem, 0));
2147
2148   base = find_base_term (x_addr);
2149   if (base && (GET_CODE (base) == LABEL_REF
2150                || (GET_CODE (base) == SYMBOL_REF
2151                    && CONSTANT_POOL_ADDRESS_P (base))))
2152     return 0;
2153
2154   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2155     return 0;
2156
2157   x_addr = canon_rtx (x_addr);
2158   mem_addr = canon_rtx (mem_addr);
2159
2160   if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2161                             SIZE_FOR_MODE (x), x_addr, 0))
2162     return 0;
2163
2164   if (aliases_everything_p (x))
2165     return 1;
2166
2167   /* We cannot use aliases_everything_p to test MEM, since we must look
2168      at MEM_MODE, rather than GET_MODE (MEM).  */
2169   if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2170     return 1;
2171
2172   /* In true_dependence we also allow BLKmode to alias anything.  Why
2173      don't we do this in anti_dependence and output_dependence?  */
2174   if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2175     return 1;
2176
2177   return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2178                                               varies);
2179 }
2180
2181 /* Canonical true dependence: X is read after store in MEM takes place.
2182    Variant of true_dependence which assumes MEM has already been
2183    canonicalized (hence we no longer do that here).
2184    The mem_addr argument has been added, since true_dependence computed
2185    this value prior to canonicalizing.  */
2186
2187 int
2188 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2189                        const_rtx x, bool (*varies) (const_rtx, bool))
2190 {
2191   rtx x_addr;
2192
2193   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2194     return 1;
2195
2196   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2197      This is used in epilogue deallocation functions.  */
2198   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2199     return 1;
2200   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2201     return 1;
2202   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2203       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2204     return 1;
2205
2206   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2207     return 0;
2208
2209   /* Read-only memory is by definition never modified, and therefore can't
2210      conflict with anything.  We don't expect to find read-only set on MEM,
2211      but stupid user tricks can produce them, so don't die.  */
2212   if (MEM_READONLY_P (x))
2213     return 0;
2214
2215   if (nonoverlapping_memrefs_p (x, mem))
2216     return 0;
2217
2218   x_addr = get_addr (XEXP (x, 0));
2219
2220   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2221     return 0;
2222
2223   x_addr = canon_rtx (x_addr);
2224   if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2225                             SIZE_FOR_MODE (x), x_addr, 0))
2226     return 0;
2227
2228   if (aliases_everything_p (x))
2229     return 1;
2230
2231   /* We cannot use aliases_everything_p to test MEM, since we must look
2232      at MEM_MODE, rather than GET_MODE (MEM).  */
2233   if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2234     return 1;
2235
2236   /* In true_dependence we also allow BLKmode to alias anything.  Why
2237      don't we do this in anti_dependence and output_dependence?  */
2238   if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2239     return 1;
2240
2241   return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2242                                               varies);
2243 }
2244
2245 /* Returns nonzero if a write to X might alias a previous read from
2246    (or, if WRITEP is nonzero, a write to) MEM.  */
2247
2248 static int
2249 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2250 {
2251   rtx x_addr, mem_addr;
2252   const_rtx fixed_scalar;
2253   rtx base;
2254
2255   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2256     return 1;
2257
2258   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2259      This is used in epilogue deallocation functions.  */
2260   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2261     return 1;
2262   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2263     return 1;
2264   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2265       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2266     return 1;
2267
2268   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2269     return 0;
2270
2271   /* A read from read-only memory can't conflict with read-write memory.  */
2272   if (!writep && MEM_READONLY_P (mem))
2273     return 0;
2274
2275   if (nonoverlapping_memrefs_p (x, mem))
2276     return 0;
2277
2278   x_addr = get_addr (XEXP (x, 0));
2279   mem_addr = get_addr (XEXP (mem, 0));
2280
2281   if (! writep)
2282     {
2283       base = find_base_term (mem_addr);
2284       if (base && (GET_CODE (base) == LABEL_REF
2285                    || (GET_CODE (base) == SYMBOL_REF
2286                        && CONSTANT_POOL_ADDRESS_P (base))))
2287         return 0;
2288     }
2289
2290   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2291                           GET_MODE (mem)))
2292     return 0;
2293
2294   x_addr = canon_rtx (x_addr);
2295   mem_addr = canon_rtx (mem_addr);
2296
2297   if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2298                            SIZE_FOR_MODE (x), x_addr, 0))
2299     return 0;
2300
2301   fixed_scalar
2302     = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2303                                          rtx_addr_varies_p);
2304
2305   return (!(fixed_scalar == mem && !aliases_everything_p (x))
2306           && !(fixed_scalar == x && !aliases_everything_p (mem)));
2307 }
2308
2309 /* Anti dependence: X is written after read in MEM takes place.  */
2310
2311 int
2312 anti_dependence (const_rtx mem, const_rtx x)
2313 {
2314   return write_dependence_p (mem, x, /*writep=*/0);
2315 }
2316
2317 /* Output dependence: X is written after store in MEM takes place.  */
2318
2319 int
2320 output_dependence (const_rtx mem, const_rtx x)
2321 {
2322   return write_dependence_p (mem, x, /*writep=*/1);
2323 }
2324 \f
2325
2326 void
2327 init_alias_once (void)
2328 {
2329   int i;
2330
2331   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2332     /* Check whether this register can hold an incoming pointer
2333        argument.  FUNCTION_ARG_REGNO_P tests outgoing register
2334        numbers, so translate if necessary due to register windows.  */
2335     if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2336         && HARD_REGNO_MODE_OK (i, Pmode))
2337       static_reg_base_value[i]
2338         = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2339
2340   static_reg_base_value[STACK_POINTER_REGNUM]
2341     = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2342   static_reg_base_value[ARG_POINTER_REGNUM]
2343     = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2344   static_reg_base_value[FRAME_POINTER_REGNUM]
2345     = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2346 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2347   static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2348     = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2349 #endif
2350 }
2351
2352 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2353    to be memory reference.  */
2354 static bool memory_modified;
2355 static void
2356 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2357 {
2358   if (MEM_P (x))
2359     {
2360       if (anti_dependence (x, (rtx)data) || output_dependence (x, (rtx)data))
2361         memory_modified = true;
2362     }
2363 }
2364
2365
2366 /* Return true when INSN possibly modify memory contents of MEM
2367    (i.e. address can be modified).  */
2368 bool
2369 memory_modified_in_insn_p (rtx mem, rtx insn)
2370 {
2371   if (!INSN_P (insn))
2372     return false;
2373   memory_modified = false;
2374   note_stores (PATTERN (insn), memory_modified_1, mem);
2375   return memory_modified;
2376 }
2377
2378 /* Initialize the aliasing machinery.  Initialize the REG_KNOWN_VALUE
2379    array.  */
2380
2381 void
2382 init_alias_analysis (void)
2383 {
2384   unsigned int maxreg = max_reg_num ();
2385   int changed, pass;
2386   int i;
2387   unsigned int ui;
2388   rtx insn;
2389
2390   timevar_push (TV_ALIAS_ANALYSIS);
2391
2392   reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER;
2393   reg_known_value = ggc_calloc (reg_known_value_size, sizeof (rtx));
2394   reg_known_equiv_p = xcalloc (reg_known_value_size, sizeof (bool));
2395
2396   /* If we have memory allocated from the previous run, use it.  */
2397   if (old_reg_base_value)
2398     reg_base_value = old_reg_base_value;
2399
2400   if (reg_base_value)
2401     VEC_truncate (rtx, reg_base_value, 0);
2402
2403   VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2404
2405   new_reg_base_value = XNEWVEC (rtx, maxreg);
2406   reg_seen = XNEWVEC (char, maxreg);
2407
2408   /* The basic idea is that each pass through this loop will use the
2409      "constant" information from the previous pass to propagate alias
2410      information through another level of assignments.
2411
2412      This could get expensive if the assignment chains are long.  Maybe
2413      we should throttle the number of iterations, possibly based on
2414      the optimization level or flag_expensive_optimizations.
2415
2416      We could propagate more information in the first pass by making use
2417      of DF_REG_DEF_COUNT to determine immediately that the alias information
2418      for a pseudo is "constant".
2419
2420      A program with an uninitialized variable can cause an infinite loop
2421      here.  Instead of doing a full dataflow analysis to detect such problems
2422      we just cap the number of iterations for the loop.
2423
2424      The state of the arrays for the set chain in question does not matter
2425      since the program has undefined behavior.  */
2426
2427   pass = 0;
2428   do
2429     {
2430       /* Assume nothing will change this iteration of the loop.  */
2431       changed = 0;
2432
2433       /* We want to assign the same IDs each iteration of this loop, so
2434          start counting from zero each iteration of the loop.  */
2435       unique_id = 0;
2436
2437       /* We're at the start of the function each iteration through the
2438          loop, so we're copying arguments.  */
2439       copying_arguments = true;
2440
2441       /* Wipe the potential alias information clean for this pass.  */
2442       memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2443
2444       /* Wipe the reg_seen array clean.  */
2445       memset (reg_seen, 0, maxreg);
2446
2447       /* Mark all hard registers which may contain an address.
2448          The stack, frame and argument pointers may contain an address.
2449          An argument register which can hold a Pmode value may contain
2450          an address even if it is not in BASE_REGS.
2451
2452          The address expression is VOIDmode for an argument and
2453          Pmode for other registers.  */
2454
2455       memcpy (new_reg_base_value, static_reg_base_value,
2456               FIRST_PSEUDO_REGISTER * sizeof (rtx));
2457
2458       /* Walk the insns adding values to the new_reg_base_value array.  */
2459       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2460         {
2461           if (INSN_P (insn))
2462             {
2463               rtx note, set;
2464
2465 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2466               /* The prologue/epilogue insns are not threaded onto the
2467                  insn chain until after reload has completed.  Thus,
2468                  there is no sense wasting time checking if INSN is in
2469                  the prologue/epilogue until after reload has completed.  */
2470               if (reload_completed
2471                   && prologue_epilogue_contains (insn))
2472                 continue;
2473 #endif
2474
2475               /* If this insn has a noalias note, process it,  Otherwise,
2476                  scan for sets.  A simple set will have no side effects
2477                  which could change the base value of any other register.  */
2478
2479               if (GET_CODE (PATTERN (insn)) == SET
2480                   && REG_NOTES (insn) != 0
2481                   && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2482                 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2483               else
2484                 note_stores (PATTERN (insn), record_set, NULL);
2485
2486               set = single_set (insn);
2487
2488               if (set != 0
2489                   && REG_P (SET_DEST (set))
2490                   && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2491                 {
2492                   unsigned int regno = REGNO (SET_DEST (set));
2493                   rtx src = SET_SRC (set);
2494                   rtx t;
2495
2496                   note = find_reg_equal_equiv_note (insn);
2497                   if (note && REG_NOTE_KIND (note) == REG_EQUAL
2498                       && DF_REG_DEF_COUNT (regno) != 1)
2499                     note = NULL_RTX;
2500
2501                   if (note != NULL_RTX
2502                       && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2503                       && ! rtx_varies_p (XEXP (note, 0), 1)
2504                       && ! reg_overlap_mentioned_p (SET_DEST (set),
2505                                                     XEXP (note, 0)))
2506                     {
2507                       set_reg_known_value (regno, XEXP (note, 0));
2508                       set_reg_known_equiv_p (regno,
2509                         REG_NOTE_KIND (note) == REG_EQUIV);
2510                     }
2511                   else if (DF_REG_DEF_COUNT (regno) == 1
2512                            && GET_CODE (src) == PLUS
2513                            && REG_P (XEXP (src, 0))
2514                            && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2515                            && GET_CODE (XEXP (src, 1)) == CONST_INT)
2516                     {
2517                       t = plus_constant (t, INTVAL (XEXP (src, 1)));
2518                       set_reg_known_value (regno, t);
2519                       set_reg_known_equiv_p (regno, 0);
2520                     }
2521                   else if (DF_REG_DEF_COUNT (regno) == 1
2522                            && ! rtx_varies_p (src, 1))
2523                     {
2524                       set_reg_known_value (regno, src);
2525                       set_reg_known_equiv_p (regno, 0);
2526                     }
2527                 }
2528             }
2529           else if (NOTE_P (insn)
2530                    && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2531             copying_arguments = false;
2532         }
2533
2534       /* Now propagate values from new_reg_base_value to reg_base_value.  */
2535       gcc_assert (maxreg == (unsigned int) max_reg_num ());
2536
2537       for (ui = 0; ui < maxreg; ui++)
2538         {
2539           if (new_reg_base_value[ui]
2540               && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2541               && ! rtx_equal_p (new_reg_base_value[ui],
2542                                 VEC_index (rtx, reg_base_value, ui)))
2543             {
2544               VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2545               changed = 1;
2546             }
2547         }
2548     }
2549   while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2550
2551   /* Fill in the remaining entries.  */
2552   for (i = 0; i < (int)reg_known_value_size; i++)
2553     if (reg_known_value[i] == 0)
2554       reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER];
2555
2556   /* Clean up.  */
2557   free (new_reg_base_value);
2558   new_reg_base_value = 0;
2559   free (reg_seen);
2560   reg_seen = 0;
2561   timevar_pop (TV_ALIAS_ANALYSIS);
2562 }
2563
2564 void
2565 end_alias_analysis (void)
2566 {
2567   old_reg_base_value = reg_base_value;
2568   ggc_free (reg_known_value);
2569   reg_known_value = 0;
2570   reg_known_value_size = 0;
2571   free (reg_known_equiv_p);
2572   reg_known_equiv_p = 0;
2573 }
2574
2575 #include "gt-alias.h"