OSDN Git Service

37c3fa062cf4b44285b54597e872dcf4bd9bb0f5
[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, 2008, 2009, 2010 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 "diagnostic-core.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 "tree-pass.h"
46 #include "df.h"
47 #include "tree-ssa-alias.h"
48 #include "pointer-set.h"
49 #include "tree-flow.h"
50
51 /* The aliasing API provided here solves related but different problems:
52
53    Say there exists (in c)
54
55    struct X {
56      struct Y y1;
57      struct Z z2;
58    } x1, *px1,  *px2;
59
60    struct Y y2, *py;
61    struct Z z2, *pz;
62
63
64    py = &px1.y1;
65    px2 = &x1;
66
67    Consider the four questions:
68
69    Can a store to x1 interfere with px2->y1?
70    Can a store to x1 interfere with px2->z2?
71    (*px2).z2
72    Can a store to x1 change the value pointed to by with py?
73    Can a store to x1 change the value pointed to by with pz?
74
75    The answer to these questions can be yes, yes, yes, and maybe.
76
77    The first two questions can be answered with a simple examination
78    of the type system.  If structure X contains a field of type Y then
79    a store thru a pointer to an X can overwrite any field that is
80    contained (recursively) in an X (unless we know that px1 != px2).
81
82    The last two of the questions can be solved in the same way as the
83    first two questions but this is too conservative.  The observation
84    is that in some cases analysis we can know if which (if any) fields
85    are addressed and if those addresses are used in bad ways.  This
86    analysis may be language specific.  In C, arbitrary operations may
87    be applied to pointers.  However, there is some indication that
88    this may be too conservative for some C++ types.
89
90    The pass ipa-type-escape does this analysis for the types whose
91    instances do not escape across the compilation boundary.
92
93    Historically in GCC, these two problems were combined and a single
94    data structure was used to represent the solution to these
95    problems.  We now have two similar but different data structures,
96    The data structure to solve the last two question is similar to the
97    first, but does not contain have the fields in it whose address are
98    never taken.  For types that do escape the compilation unit, the
99    data structures will have identical information.
100 */
101
102 /* The alias sets assigned to MEMs assist the back-end in determining
103    which MEMs can alias which other MEMs.  In general, two MEMs in
104    different alias sets cannot alias each other, with one important
105    exception.  Consider something like:
106
107      struct S { int i; double d; };
108
109    a store to an `S' can alias something of either type `int' or type
110    `double'.  (However, a store to an `int' cannot alias a `double'
111    and vice versa.)  We indicate this via a tree structure that looks
112    like:
113            struct S
114             /   \
115            /     \
116          |/_     _\|
117          int    double
118
119    (The arrows are directed and point downwards.)
120     In this situation we say the alias set for `struct S' is the
121    `superset' and that those for `int' and `double' are `subsets'.
122
123    To see whether two alias sets can point to the same memory, we must
124    see if either alias set is a subset of the other. We need not trace
125    past immediate descendants, however, since we propagate all
126    grandchildren up one level.
127
128    Alias set zero is implicitly a superset of all other alias sets.
129    However, this is no actual entry for alias set zero.  It is an
130    error to attempt to explicitly construct a subset of zero.  */
131
132 struct GTY(()) alias_set_entry_d {
133   /* The alias set number, as stored in MEM_ALIAS_SET.  */
134   alias_set_type alias_set;
135
136   /* Nonzero if would have a child of zero: this effectively makes this
137      alias set the same as alias set zero.  */
138   int has_zero_child;
139
140   /* The children of the alias set.  These are not just the immediate
141      children, but, in fact, all descendants.  So, if we have:
142
143        struct T { struct S s; float f; }
144
145      continuing our example above, the children here will be all of
146      `int', `double', `float', and `struct S'.  */
147   splay_tree GTY((param1_is (int), param2_is (int))) children;
148 };
149 typedef struct alias_set_entry_d *alias_set_entry;
150
151 static int rtx_equal_for_memref_p (const_rtx, const_rtx);
152 static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
153 static void record_set (rtx, const_rtx, void *);
154 static int base_alias_check (rtx, rtx, enum machine_mode,
155                              enum machine_mode);
156 static rtx find_base_value (rtx);
157 static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
158 static int insert_subset_children (splay_tree_node, void*);
159 static alias_set_entry get_alias_set_entry (alias_set_type);
160 static const_rtx fixed_scalar_and_varying_struct_p (const_rtx, const_rtx, rtx, rtx,
161                                                     bool (*) (const_rtx, bool));
162 static int aliases_everything_p (const_rtx);
163 static bool nonoverlapping_component_refs_p (const_tree, const_tree);
164 static tree decl_for_component_ref (tree);
165 static int write_dependence_p (const_rtx, const_rtx, int);
166
167 static void memory_modified_1 (rtx, const_rtx, void *);
168
169 /* Set up all info needed to perform alias analysis on memory references.  */
170
171 /* Returns the size in bytes of the mode of X.  */
172 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
173
174 /* Returns nonzero if MEM1 and MEM2 do not alias because they are in
175    different alias sets.  We ignore alias sets in functions making use
176    of variable arguments because the va_arg macros on some systems are
177    not legal ANSI C.  */
178 #define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2)                      \
179   mems_in_disjoint_alias_sets_p (MEM1, MEM2)
180
181 /* Cap the number of passes we make over the insns propagating alias
182    information through set chains.   10 is a completely arbitrary choice.  */
183 #define MAX_ALIAS_LOOP_PASSES 10
184
185 /* reg_base_value[N] gives an address to which register N is related.
186    If all sets after the first add or subtract to the current value
187    or otherwise modify it so it does not point to a different top level
188    object, reg_base_value[N] is equal to the address part of the source
189    of the first set.
190
191    A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF.  ADDRESS
192    expressions represent certain special values: function arguments and
193    the stack, frame, and argument pointers.
194
195    The contents of an ADDRESS is not normally used, the mode of the
196    ADDRESS determines whether the ADDRESS is a function argument or some
197    other special value.  Pointer equality, not rtx_equal_p, determines whether
198    two ADDRESS expressions refer to the same base address.
199
200    The only use of the contents of an ADDRESS is for determining if the
201    current function performs nonlocal memory memory references for the
202    purposes of marking the function as a constant function.  */
203
204 static GTY(()) VEC(rtx,gc) *reg_base_value;
205 static rtx *new_reg_base_value;
206
207 /* We preserve the copy of old array around to avoid amount of garbage
208    produced.  About 8% of garbage produced were attributed to this
209    array.  */
210 static GTY((deletable)) VEC(rtx,gc) *old_reg_base_value;
211
212 #define static_reg_base_value \
213   (this_target_rtl->x_static_reg_base_value)
214
215 #define REG_BASE_VALUE(X)                               \
216   (REGNO (X) < VEC_length (rtx, reg_base_value)         \
217    ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
218
219 /* Vector indexed by N giving the initial (unchanging) value known for
220    pseudo-register N.  This array is initialized in init_alias_analysis,
221    and does not change until end_alias_analysis is called.  */
222 static GTY((length("reg_known_value_size"))) rtx *reg_known_value;
223
224 /* Indicates number of valid entries in reg_known_value.  */
225 static GTY(()) unsigned int reg_known_value_size;
226
227 /* Vector recording for each reg_known_value whether it is due to a
228    REG_EQUIV note.  Future passes (viz., reload) may replace the
229    pseudo with the equivalent expression and so we account for the
230    dependences that would be introduced if that happens.
231
232    The REG_EQUIV notes created in assign_parms may mention the arg
233    pointer, and there are explicit insns in the RTL that modify the
234    arg pointer.  Thus we must ensure that such insns don't get
235    scheduled across each other because that would invalidate the
236    REG_EQUIV notes.  One could argue that the REG_EQUIV notes are
237    wrong, but solving the problem in the scheduler will likely give
238    better code, so we do it here.  */
239 static bool *reg_known_equiv_p;
240
241 /* True when scanning insns from the start of the rtl to the
242    NOTE_INSN_FUNCTION_BEG note.  */
243 static bool copying_arguments;
244
245 DEF_VEC_P(alias_set_entry);
246 DEF_VEC_ALLOC_P(alias_set_entry,gc);
247
248 /* The splay-tree used to store the various alias set entries.  */
249 static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
250 \f
251 /* Build a decomposed reference object for querying the alias-oracle
252    from the MEM rtx and store it in *REF.
253    Returns false if MEM is not suitable for the alias-oracle.  */
254
255 static bool
256 ao_ref_from_mem (ao_ref *ref, const_rtx mem)
257 {
258   tree expr = MEM_EXPR (mem);
259   tree base;
260
261   if (!expr)
262     return false;
263
264   ao_ref_init (ref, expr);
265
266   /* Get the base of the reference and see if we have to reject or
267      adjust it.  */
268   base = ao_ref_base (ref);
269   if (base == NULL_TREE)
270     return false;
271
272   /* The tree oracle doesn't like to have these.  */
273   if (TREE_CODE (base) == FUNCTION_DECL
274       || TREE_CODE (base) == LABEL_DECL)
275     return false;
276
277   /* If this is a pointer dereference of a non-SSA_NAME punt.
278      ???  We could replace it with a pointer to anything.  */
279   if ((INDIRECT_REF_P (base)
280        || TREE_CODE (base) == MEM_REF)
281       && TREE_CODE (TREE_OPERAND (base, 0)) != SSA_NAME)
282     return false;
283   if (TREE_CODE (base) == TARGET_MEM_REF
284       && TMR_BASE (base)
285       && TREE_CODE (TMR_BASE (base)) != SSA_NAME)
286     return false;
287
288   /* If this is a reference based on a partitioned decl replace the
289      base with an INDIRECT_REF of the pointer representative we
290      created during stack slot partitioning.  */
291   if (TREE_CODE (base) == VAR_DECL
292       && ! TREE_STATIC (base)
293       && cfun->gimple_df->decls_to_pointers != NULL)
294     {
295       void *namep;
296       namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers, base);
297       if (namep)
298         ref->base = build_simple_mem_ref (*(tree *)namep);
299     }
300   else if (TREE_CODE (base) == TARGET_MEM_REF
301            && TREE_CODE (TMR_BASE (base)) == ADDR_EXPR
302            && TREE_CODE (TREE_OPERAND (TMR_BASE (base), 0)) == VAR_DECL
303            && ! TREE_STATIC (TREE_OPERAND (TMR_BASE (base), 0))
304            && cfun->gimple_df->decls_to_pointers != NULL)
305     {
306       void *namep;
307       namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers,
308                                     TREE_OPERAND (TMR_BASE (base), 0));
309       if (namep)
310         ref->base = build_simple_mem_ref (*(tree *)namep);
311     }
312
313   ref->ref_alias_set = MEM_ALIAS_SET (mem);
314
315   /* If MEM_OFFSET or MEM_SIZE are unknown we have to punt.
316      Keep points-to related information though.  */
317   if (!MEM_OFFSET_KNOWN_P (mem)
318       || !MEM_SIZE_KNOWN_P (mem))
319     {
320       ref->ref = NULL_TREE;
321       ref->offset = 0;
322       ref->size = -1;
323       ref->max_size = -1;
324       return true;
325     }
326
327   /* If the base decl is a parameter we can have negative MEM_OFFSET in
328      case of promoted subregs on bigendian targets.  Trust the MEM_EXPR
329      here.  */
330   if (MEM_OFFSET (mem) < 0
331       && (MEM_SIZE (mem) + MEM_OFFSET (mem)) * BITS_PER_UNIT == ref->size)
332     return true;
333
334   ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
335   ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
336
337   /* The MEM may extend into adjacent fields, so adjust max_size if
338      necessary.  */
339   if (ref->max_size != -1
340       && ref->size > ref->max_size)
341     ref->max_size = ref->size;
342
343   /* If MEM_OFFSET and MEM_SIZE get us outside of the base object of
344      the MEM_EXPR punt.  This happens for STRICT_ALIGNMENT targets a lot.  */
345   if (MEM_EXPR (mem) != get_spill_slot_decl (false)
346       && (ref->offset < 0
347           || (DECL_P (ref->base)
348               && (!host_integerp (DECL_SIZE (ref->base), 1)
349                   || (TREE_INT_CST_LOW (DECL_SIZE ((ref->base)))
350                       < (unsigned HOST_WIDE_INT)(ref->offset + ref->size))))))
351     return false;
352
353   return true;
354 }
355
356 /* Query the alias-oracle on whether the two memory rtx X and MEM may
357    alias.  If TBAA_P is set also apply TBAA.  Returns true if the
358    two rtxen may alias, false otherwise.  */
359
360 static bool
361 rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
362 {
363   ao_ref ref1, ref2;
364
365   if (!ao_ref_from_mem (&ref1, x)
366       || !ao_ref_from_mem (&ref2, mem))
367     return true;
368
369   return refs_may_alias_p_1 (&ref1, &ref2,
370                              tbaa_p
371                              && MEM_ALIAS_SET (x) != 0
372                              && MEM_ALIAS_SET (mem) != 0);
373 }
374
375 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
376    such an entry, or NULL otherwise.  */
377
378 static inline alias_set_entry
379 get_alias_set_entry (alias_set_type alias_set)
380 {
381   return VEC_index (alias_set_entry, alias_sets, alias_set);
382 }
383
384 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
385    the two MEMs cannot alias each other.  */
386
387 static inline int
388 mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
389 {
390 /* Perform a basic sanity check.  Namely, that there are no alias sets
391    if we're not using strict aliasing.  This helps to catch bugs
392    whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
393    where a MEM is allocated in some way other than by the use of
394    gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared.  If we begin to
395    use alias sets to indicate that spilled registers cannot alias each
396    other, we might need to remove this check.  */
397   gcc_assert (flag_strict_aliasing
398               || (!MEM_ALIAS_SET (mem1) && !MEM_ALIAS_SET (mem2)));
399
400   return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
401 }
402
403 /* Insert the NODE into the splay tree given by DATA.  Used by
404    record_alias_subset via splay_tree_foreach.  */
405
406 static int
407 insert_subset_children (splay_tree_node node, void *data)
408 {
409   splay_tree_insert ((splay_tree) data, node->key, node->value);
410
411   return 0;
412 }
413
414 /* Return true if the first alias set is a subset of the second.  */
415
416 bool
417 alias_set_subset_of (alias_set_type set1, alias_set_type set2)
418 {
419   alias_set_entry ase;
420
421   /* Everything is a subset of the "aliases everything" set.  */
422   if (set2 == 0)
423     return true;
424
425   /* Otherwise, check if set1 is a subset of set2.  */
426   ase = get_alias_set_entry (set2);
427   if (ase != 0
428       && (ase->has_zero_child
429           || splay_tree_lookup (ase->children,
430                                 (splay_tree_key) set1)))
431     return true;
432   return false;
433 }
434
435 /* Return 1 if the two specified alias sets may conflict.  */
436
437 int
438 alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
439 {
440   alias_set_entry ase;
441
442   /* The easy case.  */
443   if (alias_sets_must_conflict_p (set1, set2))
444     return 1;
445
446   /* See if the first alias set is a subset of the second.  */
447   ase = get_alias_set_entry (set1);
448   if (ase != 0
449       && (ase->has_zero_child
450           || splay_tree_lookup (ase->children,
451                                 (splay_tree_key) set2)))
452     return 1;
453
454   /* Now do the same, but with the alias sets reversed.  */
455   ase = get_alias_set_entry (set2);
456   if (ase != 0
457       && (ase->has_zero_child
458           || splay_tree_lookup (ase->children,
459                                 (splay_tree_key) set1)))
460     return 1;
461
462   /* The two alias sets are distinct and neither one is the
463      child of the other.  Therefore, they cannot conflict.  */
464   return 0;
465 }
466
467 /* Return 1 if the two specified alias sets will always conflict.  */
468
469 int
470 alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
471 {
472   if (set1 == 0 || set2 == 0 || set1 == set2)
473     return 1;
474
475   return 0;
476 }
477
478 /* Return 1 if any MEM object of type T1 will always conflict (using the
479    dependency routines in this file) with any MEM object of type T2.
480    This is used when allocating temporary storage.  If T1 and/or T2 are
481    NULL_TREE, it means we know nothing about the storage.  */
482
483 int
484 objects_must_conflict_p (tree t1, tree t2)
485 {
486   alias_set_type set1, set2;
487
488   /* If neither has a type specified, we don't know if they'll conflict
489      because we may be using them to store objects of various types, for
490      example the argument and local variables areas of inlined functions.  */
491   if (t1 == 0 && t2 == 0)
492     return 0;
493
494   /* If they are the same type, they must conflict.  */
495   if (t1 == t2
496       /* Likewise if both are volatile.  */
497       || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
498     return 1;
499
500   set1 = t1 ? get_alias_set (t1) : 0;
501   set2 = t2 ? get_alias_set (t2) : 0;
502
503   /* We can't use alias_sets_conflict_p because we must make sure
504      that every subtype of t1 will conflict with every subtype of
505      t2 for which a pair of subobjects of these respective subtypes
506      overlaps on the stack.  */
507   return alias_sets_must_conflict_p (set1, set2);
508 }
509 \f
510 /* Return true if all nested component references handled by
511    get_inner_reference in T are such that we should use the alias set
512    provided by the object at the heart of T.
513
514    This is true for non-addressable components (which don't have their
515    own alias set), as well as components of objects in alias set zero.
516    This later point is a special case wherein we wish to override the
517    alias set used by the component, but we don't have per-FIELD_DECL
518    assignable alias sets.  */
519
520 bool
521 component_uses_parent_alias_set (const_tree t)
522 {
523   while (1)
524     {
525       /* If we're at the end, it vacuously uses its own alias set.  */
526       if (!handled_component_p (t))
527         return false;
528
529       switch (TREE_CODE (t))
530         {
531         case COMPONENT_REF:
532           if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
533             return true;
534           break;
535
536         case ARRAY_REF:
537         case ARRAY_RANGE_REF:
538           if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
539             return true;
540           break;
541
542         case REALPART_EXPR:
543         case IMAGPART_EXPR:
544           break;
545
546         default:
547           /* Bitfields and casts are never addressable.  */
548           return true;
549         }
550
551       t = TREE_OPERAND (t, 0);
552       if (get_alias_set (TREE_TYPE (t)) == 0)
553         return true;
554     }
555 }
556
557 /* Return the alias set for the memory pointed to by T, which may be
558    either a type or an expression.  Return -1 if there is nothing
559    special about dereferencing T.  */
560
561 static alias_set_type
562 get_deref_alias_set_1 (tree t)
563 {
564   /* If we're not doing any alias analysis, just assume everything
565      aliases everything else.  */
566   if (!flag_strict_aliasing)
567     return 0;
568
569   /* All we care about is the type.  */
570   if (! TYPE_P (t))
571     t = TREE_TYPE (t);
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   if (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE
577       || TYPE_REF_CAN_ALIAS_ALL (t))
578     return 0;
579
580   return -1;
581 }
582
583 /* Return the alias set for the memory pointed to by T, which may be
584    either a type or an expression.  */
585
586 alias_set_type
587 get_deref_alias_set (tree t)
588 {
589   alias_set_type set = get_deref_alias_set_1 (t);
590
591   /* Fall back to the alias-set of the pointed-to type.  */
592   if (set == -1)
593     {
594       if (! TYPE_P (t))
595         t = TREE_TYPE (t);
596       set = get_alias_set (TREE_TYPE (t));
597     }
598
599   return set;
600 }
601
602 /* Return the alias set for T, which may be either a type or an
603    expression.  Call language-specific routine for help, if needed.  */
604
605 alias_set_type
606 get_alias_set (tree t)
607 {
608   alias_set_type set;
609
610   /* If we're not doing any alias analysis, just assume everything
611      aliases everything else.  Also return 0 if this or its type is
612      an error.  */
613   if (! flag_strict_aliasing || t == error_mark_node
614       || (! TYPE_P (t)
615           && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
616     return 0;
617
618   /* We can be passed either an expression or a type.  This and the
619      language-specific routine may make mutually-recursive calls to each other
620      to figure out what to do.  At each juncture, we see if this is a tree
621      that the language may need to handle specially.  First handle things that
622      aren't types.  */
623   if (! TYPE_P (t))
624     {
625       tree inner;
626
627       /* Give the language a chance to do something with this tree
628          before we look at it.  */
629       STRIP_NOPS (t);
630       set = lang_hooks.get_alias_set (t);
631       if (set != -1)
632         return set;
633
634       /* Get the base object of the reference.  */
635       inner = t;
636       while (handled_component_p (inner))
637         {
638           /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
639              the type of any component references that wrap it to
640              determine the alias-set.  */
641           if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
642             t = TREE_OPERAND (inner, 0);
643           inner = TREE_OPERAND (inner, 0);
644         }
645
646       /* Handle pointer dereferences here, they can override the
647          alias-set.  */
648       if (INDIRECT_REF_P (inner))
649         {
650           set = get_deref_alias_set_1 (TREE_OPERAND (inner, 0));
651           if (set != -1)
652             return set;
653         }
654       else if (TREE_CODE (inner) == TARGET_MEM_REF)
655         return get_deref_alias_set (TMR_OFFSET (inner));
656       else if (TREE_CODE (inner) == MEM_REF)
657         {
658           set = get_deref_alias_set_1 (TREE_OPERAND (inner, 1));
659           if (set != -1)
660             return set;
661         }
662
663       /* If the innermost reference is a MEM_REF that has a
664          conversion embedded treat it like a VIEW_CONVERT_EXPR above,
665          using the memory access type for determining the alias-set.  */
666      if (TREE_CODE (inner) == MEM_REF
667          && TYPE_MAIN_VARIANT (TREE_TYPE (inner))
668             != TYPE_MAIN_VARIANT
669                (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1)))))
670        return get_deref_alias_set (TREE_OPERAND (inner, 1));
671
672       /* Otherwise, pick up the outermost object that we could have a pointer
673          to, processing conversions as above.  */
674       while (component_uses_parent_alias_set (t))
675         {
676           t = TREE_OPERAND (t, 0);
677           STRIP_NOPS (t);
678         }
679
680       /* If we've already determined the alias set for a decl, just return
681          it.  This is necessary for C++ anonymous unions, whose component
682          variables don't look like union members (boo!).  */
683       if (TREE_CODE (t) == VAR_DECL
684           && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
685         return MEM_ALIAS_SET (DECL_RTL (t));
686
687       /* Now all we care about is the type.  */
688       t = TREE_TYPE (t);
689     }
690
691   /* Variant qualifiers don't affect the alias set, so get the main
692      variant.  */
693   t = TYPE_MAIN_VARIANT (t);
694
695   /* Always use the canonical type as well.  If this is a type that
696      requires structural comparisons to identify compatible types
697      use alias set zero.  */
698   if (TYPE_STRUCTURAL_EQUALITY_P (t))
699     {
700       /* Allow the language to specify another alias set for this
701          type.  */
702       set = lang_hooks.get_alias_set (t);
703       if (set != -1)
704         return set;
705       return 0;
706     }
707
708   t = TYPE_CANONICAL (t);
709
710   /* The canonical type should not require structural equality checks.  */
711   gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
712
713   /* If this is a type with a known alias set, return it.  */
714   if (TYPE_ALIAS_SET_KNOWN_P (t))
715     return TYPE_ALIAS_SET (t);
716
717   /* We don't want to set TYPE_ALIAS_SET for incomplete types.  */
718   if (!COMPLETE_TYPE_P (t))
719     {
720       /* For arrays with unknown size the conservative answer is the
721          alias set of the element type.  */
722       if (TREE_CODE (t) == ARRAY_TYPE)
723         return get_alias_set (TREE_TYPE (t));
724
725       /* But return zero as a conservative answer for incomplete types.  */
726       return 0;
727     }
728
729   /* See if the language has special handling for this type.  */
730   set = lang_hooks.get_alias_set (t);
731   if (set != -1)
732     return set;
733
734   /* There are no objects of FUNCTION_TYPE, so there's no point in
735      using up an alias set for them.  (There are, of course, pointers
736      and references to functions, but that's different.)  */
737   else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
738     set = 0;
739
740   /* Unless the language specifies otherwise, let vector types alias
741      their components.  This avoids some nasty type punning issues in
742      normal usage.  And indeed lets vectors be treated more like an
743      array slice.  */
744   else if (TREE_CODE (t) == VECTOR_TYPE)
745     set = get_alias_set (TREE_TYPE (t));
746
747   /* Unless the language specifies otherwise, treat array types the
748      same as their components.  This avoids the asymmetry we get
749      through recording the components.  Consider accessing a
750      character(kind=1) through a reference to a character(kind=1)[1:1].
751      Or consider if we want to assign integer(kind=4)[0:D.1387] and
752      integer(kind=4)[4] the same alias set or not.
753      Just be pragmatic here and make sure the array and its element
754      type get the same alias set assigned.  */
755   else if (TREE_CODE (t) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (t))
756     set = get_alias_set (TREE_TYPE (t));
757
758   /* From the former common C and C++ langhook implementation:
759
760      Unfortunately, there is no canonical form of a pointer type.
761      In particular, if we have `typedef int I', then `int *', and
762      `I *' are different types.  So, we have to pick a canonical
763      representative.  We do this below.
764
765      Technically, this approach is actually more conservative that
766      it needs to be.  In particular, `const int *' and `int *'
767      should be in different alias sets, according to the C and C++
768      standard, since their types are not the same, and so,
769      technically, an `int **' and `const int **' cannot point at
770      the same thing.
771
772      But, the standard is wrong.  In particular, this code is
773      legal C++:
774
775      int *ip;
776      int **ipp = &ip;
777      const int* const* cipp = ipp;
778      And, it doesn't make sense for that to be legal unless you
779      can dereference IPP and CIPP.  So, we ignore cv-qualifiers on
780      the pointed-to types.  This issue has been reported to the
781      C++ committee.
782
783      In addition to the above canonicalization issue, with LTO
784      we should also canonicalize `T (*)[]' to `T *' avoiding
785      alias issues with pointer-to element types and pointer-to
786      array types.
787
788      Likewise we need to deal with the situation of incomplete
789      pointed-to types and make `*(struct X **)&a' and
790      `*(struct X {} **)&a' alias.  Otherwise we will have to
791      guarantee that all pointer-to incomplete type variants
792      will be replaced by pointer-to complete type variants if
793      they are available.
794
795      With LTO the convenient situation of using `void *' to
796      access and store any pointer type will also become
797      more apparent (and `void *' is just another pointer-to
798      incomplete type).  Assigning alias-set zero to `void *'
799      and all pointer-to incomplete types is a not appealing
800      solution.  Assigning an effective alias-set zero only
801      affecting pointers might be - by recording proper subset
802      relationships of all pointer alias-sets.
803
804      Pointer-to function types are another grey area which
805      needs caution.  Globbing them all into one alias-set
806      or the above effective zero set would work.
807
808      For now just assign the same alias-set to all pointers.
809      That's simple and avoids all the above problems.  */
810   else if (POINTER_TYPE_P (t)
811            && t != ptr_type_node)
812     set = get_alias_set (ptr_type_node);
813
814   /* Otherwise make a new alias set for this type.  */
815   else
816     {
817       /* Each canonical type gets its own alias set, so canonical types
818          shouldn't form a tree.  It doesn't really matter for types
819          we handle specially above, so only check it where it possibly
820          would result in a bogus alias set.  */
821       gcc_checking_assert (TYPE_CANONICAL (t) == t);
822
823       set = new_alias_set ();
824     }
825
826   TYPE_ALIAS_SET (t) = set;
827
828   /* If this is an aggregate type or a complex type, we must record any
829      component aliasing information.  */
830   if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
831     record_component_aliases (t);
832
833   return set;
834 }
835
836 /* Return a brand-new alias set.  */
837
838 alias_set_type
839 new_alias_set (void)
840 {
841   if (flag_strict_aliasing)
842     {
843       if (alias_sets == 0)
844         VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
845       VEC_safe_push (alias_set_entry, gc, alias_sets, 0);
846       return VEC_length (alias_set_entry, alias_sets) - 1;
847     }
848   else
849     return 0;
850 }
851
852 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
853    not everything that aliases SUPERSET also aliases SUBSET.  For example,
854    in C, a store to an `int' can alias a load of a structure containing an
855    `int', and vice versa.  But it can't alias a load of a 'double' member
856    of the same structure.  Here, the structure would be the SUPERSET and
857    `int' the SUBSET.  This relationship is also described in the comment at
858    the beginning of this file.
859
860    This function should be called only once per SUPERSET/SUBSET pair.
861
862    It is illegal for SUPERSET to be zero; everything is implicitly a
863    subset of alias set zero.  */
864
865 void
866 record_alias_subset (alias_set_type superset, alias_set_type subset)
867 {
868   alias_set_entry superset_entry;
869   alias_set_entry subset_entry;
870
871   /* It is possible in complex type situations for both sets to be the same,
872      in which case we can ignore this operation.  */
873   if (superset == subset)
874     return;
875
876   gcc_assert (superset);
877
878   superset_entry = get_alias_set_entry (superset);
879   if (superset_entry == 0)
880     {
881       /* Create an entry for the SUPERSET, so that we have a place to
882          attach the SUBSET.  */
883       superset_entry = ggc_alloc_cleared_alias_set_entry_d ();
884       superset_entry->alias_set = superset;
885       superset_entry->children
886         = splay_tree_new_ggc (splay_tree_compare_ints,
887                               ggc_alloc_splay_tree_scalar_scalar_splay_tree_s,
888                               ggc_alloc_splay_tree_scalar_scalar_splay_tree_node_s);
889       superset_entry->has_zero_child = 0;
890       VEC_replace (alias_set_entry, alias_sets, superset, superset_entry);
891     }
892
893   if (subset == 0)
894     superset_entry->has_zero_child = 1;
895   else
896     {
897       subset_entry = get_alias_set_entry (subset);
898       /* If there is an entry for the subset, enter all of its children
899          (if they are not already present) as children of the SUPERSET.  */
900       if (subset_entry)
901         {
902           if (subset_entry->has_zero_child)
903             superset_entry->has_zero_child = 1;
904
905           splay_tree_foreach (subset_entry->children, insert_subset_children,
906                               superset_entry->children);
907         }
908
909       /* Enter the SUBSET itself as a child of the SUPERSET.  */
910       splay_tree_insert (superset_entry->children,
911                          (splay_tree_key) subset, 0);
912     }
913 }
914
915 /* Record that component types of TYPE, if any, are part of that type for
916    aliasing purposes.  For record types, we only record component types
917    for fields that are not marked non-addressable.  For array types, we
918    only record the component type if it is not marked non-aliased.  */
919
920 void
921 record_component_aliases (tree type)
922 {
923   alias_set_type superset = get_alias_set (type);
924   tree field;
925
926   if (superset == 0)
927     return;
928
929   switch (TREE_CODE (type))
930     {
931     case RECORD_TYPE:
932     case UNION_TYPE:
933     case QUAL_UNION_TYPE:
934       /* Recursively record aliases for the base classes, if there are any.  */
935       if (TYPE_BINFO (type))
936         {
937           int i;
938           tree binfo, base_binfo;
939
940           for (binfo = TYPE_BINFO (type), i = 0;
941                BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
942             record_alias_subset (superset,
943                                  get_alias_set (BINFO_TYPE (base_binfo)));
944         }
945       for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
946         if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
947           record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
948       break;
949
950     case COMPLEX_TYPE:
951       record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
952       break;
953
954     /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
955        element type.  */
956
957     default:
958       break;
959     }
960 }
961
962 /* Allocate an alias set for use in storing and reading from the varargs
963    spill area.  */
964
965 static GTY(()) alias_set_type varargs_set = -1;
966
967 alias_set_type
968 get_varargs_alias_set (void)
969 {
970 #if 1
971   /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
972      varargs alias set to an INDIRECT_REF (FIXME!), so we can't
973      consistently use the varargs alias set for loads from the varargs
974      area.  So don't use it anywhere.  */
975   return 0;
976 #else
977   if (varargs_set == -1)
978     varargs_set = new_alias_set ();
979
980   return varargs_set;
981 #endif
982 }
983
984 /* Likewise, but used for the fixed portions of the frame, e.g., register
985    save areas.  */
986
987 static GTY(()) alias_set_type frame_set = -1;
988
989 alias_set_type
990 get_frame_alias_set (void)
991 {
992   if (frame_set == -1)
993     frame_set = new_alias_set ();
994
995   return frame_set;
996 }
997
998 /* Inside SRC, the source of a SET, find a base address.  */
999
1000 static rtx
1001 find_base_value (rtx src)
1002 {
1003   unsigned int regno;
1004
1005 #if defined (FIND_BASE_TERM)
1006   /* Try machine-dependent ways to find the base term.  */
1007   src = FIND_BASE_TERM (src);
1008 #endif
1009
1010   switch (GET_CODE (src))
1011     {
1012     case SYMBOL_REF:
1013     case LABEL_REF:
1014       return src;
1015
1016     case REG:
1017       regno = REGNO (src);
1018       /* At the start of a function, argument registers have known base
1019          values which may be lost later.  Returning an ADDRESS
1020          expression here allows optimization based on argument values
1021          even when the argument registers are used for other purposes.  */
1022       if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1023         return new_reg_base_value[regno];
1024
1025       /* If a pseudo has a known base value, return it.  Do not do this
1026          for non-fixed hard regs since it can result in a circular
1027          dependency chain for registers which have values at function entry.
1028
1029          The test above is not sufficient because the scheduler may move
1030          a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN.  */
1031       if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1032           && regno < VEC_length (rtx, reg_base_value))
1033         {
1034           /* If we're inside init_alias_analysis, use new_reg_base_value
1035              to reduce the number of relaxation iterations.  */
1036           if (new_reg_base_value && new_reg_base_value[regno]
1037               && DF_REG_DEF_COUNT (regno) == 1)
1038             return new_reg_base_value[regno];
1039
1040           if (VEC_index (rtx, reg_base_value, regno))
1041             return VEC_index (rtx, reg_base_value, regno);
1042         }
1043
1044       return 0;
1045
1046     case MEM:
1047       /* Check for an argument passed in memory.  Only record in the
1048          copying-arguments block; it is too hard to track changes
1049          otherwise.  */
1050       if (copying_arguments
1051           && (XEXP (src, 0) == arg_pointer_rtx
1052               || (GET_CODE (XEXP (src, 0)) == PLUS
1053                   && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1054         return gen_rtx_ADDRESS (VOIDmode, src);
1055       return 0;
1056
1057     case CONST:
1058       src = XEXP (src, 0);
1059       if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1060         break;
1061
1062       /* ... fall through ...  */
1063
1064     case PLUS:
1065     case MINUS:
1066       {
1067         rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1068
1069         /* If either operand is a REG that is a known pointer, then it
1070            is the base.  */
1071         if (REG_P (src_0) && REG_POINTER (src_0))
1072           return find_base_value (src_0);
1073         if (REG_P (src_1) && REG_POINTER (src_1))
1074           return find_base_value (src_1);
1075
1076         /* If either operand is a REG, then see if we already have
1077            a known value for it.  */
1078         if (REG_P (src_0))
1079           {
1080             temp = find_base_value (src_0);
1081             if (temp != 0)
1082               src_0 = temp;
1083           }
1084
1085         if (REG_P (src_1))
1086           {
1087             temp = find_base_value (src_1);
1088             if (temp!= 0)
1089               src_1 = temp;
1090           }
1091
1092         /* If either base is named object or a special address
1093            (like an argument or stack reference), then use it for the
1094            base term.  */
1095         if (src_0 != 0
1096             && (GET_CODE (src_0) == SYMBOL_REF
1097                 || GET_CODE (src_0) == LABEL_REF
1098                 || (GET_CODE (src_0) == ADDRESS
1099                     && GET_MODE (src_0) != VOIDmode)))
1100           return src_0;
1101
1102         if (src_1 != 0
1103             && (GET_CODE (src_1) == SYMBOL_REF
1104                 || GET_CODE (src_1) == LABEL_REF
1105                 || (GET_CODE (src_1) == ADDRESS
1106                     && GET_MODE (src_1) != VOIDmode)))
1107           return src_1;
1108
1109         /* Guess which operand is the base address:
1110            If either operand is a symbol, then it is the base.  If
1111            either operand is a CONST_INT, then the other is the base.  */
1112         if (CONST_INT_P (src_1) || CONSTANT_P (src_0))
1113           return find_base_value (src_0);
1114         else if (CONST_INT_P (src_0) || CONSTANT_P (src_1))
1115           return find_base_value (src_1);
1116
1117         return 0;
1118       }
1119
1120     case LO_SUM:
1121       /* The standard form is (lo_sum reg sym) so look only at the
1122          second operand.  */
1123       return find_base_value (XEXP (src, 1));
1124
1125     case AND:
1126       /* If the second operand is constant set the base
1127          address to the first operand.  */
1128       if (CONST_INT_P (XEXP (src, 1)) && INTVAL (XEXP (src, 1)) != 0)
1129         return find_base_value (XEXP (src, 0));
1130       return 0;
1131
1132     case TRUNCATE:
1133       /* As we do not know which address space the pointer is refering to, we can
1134          handle this only if the target does not support different pointer or
1135          address modes depending on the address space.  */
1136       if (!target_default_pointer_address_modes_p ())
1137         break;
1138       if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode))
1139         break;
1140       /* Fall through.  */
1141     case HIGH:
1142     case PRE_INC:
1143     case PRE_DEC:
1144     case POST_INC:
1145     case POST_DEC:
1146     case PRE_MODIFY:
1147     case POST_MODIFY:
1148       return find_base_value (XEXP (src, 0));
1149
1150     case ZERO_EXTEND:
1151     case SIGN_EXTEND:   /* used for NT/Alpha pointers */
1152       /* As we do not know which address space the pointer is refering to, we can
1153          handle this only if the target does not support different pointer or
1154          address modes depending on the address space.  */
1155       if (!target_default_pointer_address_modes_p ())
1156         break;
1157
1158       {
1159         rtx temp = find_base_value (XEXP (src, 0));
1160
1161         if (temp != 0 && CONSTANT_P (temp))
1162           temp = convert_memory_address (Pmode, temp);
1163
1164         return temp;
1165       }
1166
1167     default:
1168       break;
1169     }
1170
1171   return 0;
1172 }
1173
1174 /* Called from init_alias_analysis indirectly through note_stores.  */
1175
1176 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1177    register N has been set in this function.  */
1178 static char *reg_seen;
1179
1180 /* Addresses which are known not to alias anything else are identified
1181    by a unique integer.  */
1182 static int unique_id;
1183
1184 static void
1185 record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1186 {
1187   unsigned regno;
1188   rtx src;
1189   int n;
1190
1191   if (!REG_P (dest))
1192     return;
1193
1194   regno = REGNO (dest);
1195
1196   gcc_checking_assert (regno < VEC_length (rtx, reg_base_value));
1197
1198   /* If this spans multiple hard registers, then we must indicate that every
1199      register has an unusable value.  */
1200   if (regno < FIRST_PSEUDO_REGISTER)
1201     n = hard_regno_nregs[regno][GET_MODE (dest)];
1202   else
1203     n = 1;
1204   if (n != 1)
1205     {
1206       while (--n >= 0)
1207         {
1208           reg_seen[regno + n] = 1;
1209           new_reg_base_value[regno + n] = 0;
1210         }
1211       return;
1212     }
1213
1214   if (set)
1215     {
1216       /* A CLOBBER wipes out any old value but does not prevent a previously
1217          unset register from acquiring a base address (i.e. reg_seen is not
1218          set).  */
1219       if (GET_CODE (set) == CLOBBER)
1220         {
1221           new_reg_base_value[regno] = 0;
1222           return;
1223         }
1224       src = SET_SRC (set);
1225     }
1226   else
1227     {
1228       if (reg_seen[regno])
1229         {
1230           new_reg_base_value[regno] = 0;
1231           return;
1232         }
1233       reg_seen[regno] = 1;
1234       new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
1235                                                    GEN_INT (unique_id++));
1236       return;
1237     }
1238
1239   /* If this is not the first set of REGNO, see whether the new value
1240      is related to the old one.  There are two cases of interest:
1241
1242         (1) The register might be assigned an entirely new value
1243             that has the same base term as the original set.
1244
1245         (2) The set might be a simple self-modification that
1246             cannot change REGNO's base value.
1247
1248      If neither case holds, reject the original base value as invalid.
1249      Note that the following situation is not detected:
1250
1251          extern int x, y;  int *p = &x; p += (&y-&x);
1252
1253      ANSI C does not allow computing the difference of addresses
1254      of distinct top level objects.  */
1255   if (new_reg_base_value[regno] != 0
1256       && find_base_value (src) != new_reg_base_value[regno])
1257     switch (GET_CODE (src))
1258       {
1259       case LO_SUM:
1260       case MINUS:
1261         if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1262           new_reg_base_value[regno] = 0;
1263         break;
1264       case PLUS:
1265         /* If the value we add in the PLUS is also a valid base value,
1266            this might be the actual base value, and the original value
1267            an index.  */
1268         {
1269           rtx other = NULL_RTX;
1270
1271           if (XEXP (src, 0) == dest)
1272             other = XEXP (src, 1);
1273           else if (XEXP (src, 1) == dest)
1274             other = XEXP (src, 0);
1275
1276           if (! other || find_base_value (other))
1277             new_reg_base_value[regno] = 0;
1278           break;
1279         }
1280       case AND:
1281         if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1282           new_reg_base_value[regno] = 0;
1283         break;
1284       default:
1285         new_reg_base_value[regno] = 0;
1286         break;
1287       }
1288   /* If this is the first set of a register, record the value.  */
1289   else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1290            && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
1291     new_reg_base_value[regno] = find_base_value (src);
1292
1293   reg_seen[regno] = 1;
1294 }
1295
1296 /* Return REG_BASE_VALUE for REGNO.  Selective scheduler uses this to avoid
1297    using hard registers with non-null REG_BASE_VALUE for renaming.  */
1298 rtx
1299 get_reg_base_value (unsigned int regno)
1300 {
1301   return VEC_index (rtx, reg_base_value, regno);
1302 }
1303
1304 /* If a value is known for REGNO, return it.  */
1305
1306 rtx
1307 get_reg_known_value (unsigned int regno)
1308 {
1309   if (regno >= FIRST_PSEUDO_REGISTER)
1310     {
1311       regno -= FIRST_PSEUDO_REGISTER;
1312       if (regno < reg_known_value_size)
1313         return reg_known_value[regno];
1314     }
1315   return NULL;
1316 }
1317
1318 /* Set it.  */
1319
1320 static void
1321 set_reg_known_value (unsigned int regno, rtx val)
1322 {
1323   if (regno >= FIRST_PSEUDO_REGISTER)
1324     {
1325       regno -= FIRST_PSEUDO_REGISTER;
1326       if (regno < reg_known_value_size)
1327         reg_known_value[regno] = val;
1328     }
1329 }
1330
1331 /* Similarly for reg_known_equiv_p.  */
1332
1333 bool
1334 get_reg_known_equiv_p (unsigned int regno)
1335 {
1336   if (regno >= FIRST_PSEUDO_REGISTER)
1337     {
1338       regno -= FIRST_PSEUDO_REGISTER;
1339       if (regno < reg_known_value_size)
1340         return reg_known_equiv_p[regno];
1341     }
1342   return false;
1343 }
1344
1345 static void
1346 set_reg_known_equiv_p (unsigned int regno, bool val)
1347 {
1348   if (regno >= FIRST_PSEUDO_REGISTER)
1349     {
1350       regno -= FIRST_PSEUDO_REGISTER;
1351       if (regno < reg_known_value_size)
1352         reg_known_equiv_p[regno] = val;
1353     }
1354 }
1355
1356
1357 /* Returns a canonical version of X, from the point of view alias
1358    analysis.  (For example, if X is a MEM whose address is a register,
1359    and the register has a known value (say a SYMBOL_REF), then a MEM
1360    whose address is the SYMBOL_REF is returned.)  */
1361
1362 rtx
1363 canon_rtx (rtx x)
1364 {
1365   /* Recursively look for equivalences.  */
1366   if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1367     {
1368       rtx t = get_reg_known_value (REGNO (x));
1369       if (t == x)
1370         return x;
1371       if (t)
1372         return canon_rtx (t);
1373     }
1374
1375   if (GET_CODE (x) == PLUS)
1376     {
1377       rtx x0 = canon_rtx (XEXP (x, 0));
1378       rtx x1 = canon_rtx (XEXP (x, 1));
1379
1380       if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1381         {
1382           if (CONST_INT_P (x0))
1383             return plus_constant (x1, INTVAL (x0));
1384           else if (CONST_INT_P (x1))
1385             return plus_constant (x0, INTVAL (x1));
1386           return gen_rtx_PLUS (GET_MODE (x), x0, x1);
1387         }
1388     }
1389
1390   /* This gives us much better alias analysis when called from
1391      the loop optimizer.   Note we want to leave the original
1392      MEM alone, but need to return the canonicalized MEM with
1393      all the flags with their original values.  */
1394   else if (MEM_P (x))
1395     x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1396
1397   return x;
1398 }
1399
1400 /* Return 1 if X and Y are identical-looking rtx's.
1401    Expect that X and Y has been already canonicalized.
1402
1403    We use the data in reg_known_value above to see if two registers with
1404    different numbers are, in fact, equivalent.  */
1405
1406 static int
1407 rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1408 {
1409   int i;
1410   int j;
1411   enum rtx_code code;
1412   const char *fmt;
1413
1414   if (x == 0 && y == 0)
1415     return 1;
1416   if (x == 0 || y == 0)
1417     return 0;
1418
1419   if (x == y)
1420     return 1;
1421
1422   code = GET_CODE (x);
1423   /* Rtx's of different codes cannot be equal.  */
1424   if (code != GET_CODE (y))
1425     return 0;
1426
1427   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1428      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
1429
1430   if (GET_MODE (x) != GET_MODE (y))
1431     return 0;
1432
1433   /* Some RTL can be compared without a recursive examination.  */
1434   switch (code)
1435     {
1436     case REG:
1437       return REGNO (x) == REGNO (y);
1438
1439     case LABEL_REF:
1440       return XEXP (x, 0) == XEXP (y, 0);
1441
1442     case SYMBOL_REF:
1443       return XSTR (x, 0) == XSTR (y, 0);
1444
1445     case VALUE:
1446     case CONST_INT:
1447     case CONST_DOUBLE:
1448     case CONST_FIXED:
1449       /* There's no need to compare the contents of CONST_DOUBLEs or
1450          CONST_INTs because pointer equality is a good enough
1451          comparison for these nodes.  */
1452       return 0;
1453
1454     default:
1455       break;
1456     }
1457
1458   /* canon_rtx knows how to handle plus.  No need to canonicalize.  */
1459   if (code == PLUS)
1460     return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1461              && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1462             || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1463                 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1464   /* For commutative operations, the RTX match if the operand match in any
1465      order.  Also handle the simple binary and unary cases without a loop.  */
1466   if (COMMUTATIVE_P (x))
1467     {
1468       rtx xop0 = canon_rtx (XEXP (x, 0));
1469       rtx yop0 = canon_rtx (XEXP (y, 0));
1470       rtx yop1 = canon_rtx (XEXP (y, 1));
1471
1472       return ((rtx_equal_for_memref_p (xop0, yop0)
1473                && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1474               || (rtx_equal_for_memref_p (xop0, yop1)
1475                   && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1476     }
1477   else if (NON_COMMUTATIVE_P (x))
1478     {
1479       return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1480                                       canon_rtx (XEXP (y, 0)))
1481               && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1482                                          canon_rtx (XEXP (y, 1))));
1483     }
1484   else if (UNARY_P (x))
1485     return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1486                                    canon_rtx (XEXP (y, 0)));
1487
1488   /* Compare the elements.  If any pair of corresponding elements
1489      fail to match, return 0 for the whole things.
1490
1491      Limit cases to types which actually appear in addresses.  */
1492
1493   fmt = GET_RTX_FORMAT (code);
1494   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1495     {
1496       switch (fmt[i])
1497         {
1498         case 'i':
1499           if (XINT (x, i) != XINT (y, i))
1500             return 0;
1501           break;
1502
1503         case 'E':
1504           /* Two vectors must have the same length.  */
1505           if (XVECLEN (x, i) != XVECLEN (y, i))
1506             return 0;
1507
1508           /* And the corresponding elements must match.  */
1509           for (j = 0; j < XVECLEN (x, i); j++)
1510             if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1511                                         canon_rtx (XVECEXP (y, i, j))) == 0)
1512               return 0;
1513           break;
1514
1515         case 'e':
1516           if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1517                                       canon_rtx (XEXP (y, i))) == 0)
1518             return 0;
1519           break;
1520
1521           /* This can happen for asm operands.  */
1522         case 's':
1523           if (strcmp (XSTR (x, i), XSTR (y, i)))
1524             return 0;
1525           break;
1526
1527         /* This can happen for an asm which clobbers memory.  */
1528         case '0':
1529           break;
1530
1531           /* It is believed that rtx's at this level will never
1532              contain anything but integers and other rtx's,
1533              except for within LABEL_REFs and SYMBOL_REFs.  */
1534         default:
1535           gcc_unreachable ();
1536         }
1537     }
1538   return 1;
1539 }
1540
1541 rtx
1542 find_base_term (rtx x)
1543 {
1544   cselib_val *val;
1545   struct elt_loc_list *l, *f;
1546   rtx ret;
1547
1548 #if defined (FIND_BASE_TERM)
1549   /* Try machine-dependent ways to find the base term.  */
1550   x = FIND_BASE_TERM (x);
1551 #endif
1552
1553   switch (GET_CODE (x))
1554     {
1555     case REG:
1556       return REG_BASE_VALUE (x);
1557
1558     case TRUNCATE:
1559       /* As we do not know which address space the pointer is refering to, we can
1560          handle this only if the target does not support different pointer or
1561          address modes depending on the address space.  */
1562       if (!target_default_pointer_address_modes_p ())
1563         return 0;
1564       if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode))
1565         return 0;
1566       /* Fall through.  */
1567     case HIGH:
1568     case PRE_INC:
1569     case PRE_DEC:
1570     case POST_INC:
1571     case POST_DEC:
1572     case PRE_MODIFY:
1573     case POST_MODIFY:
1574       return find_base_term (XEXP (x, 0));
1575
1576     case ZERO_EXTEND:
1577     case SIGN_EXTEND:   /* Used for Alpha/NT pointers */
1578       /* As we do not know which address space the pointer is refering to, we can
1579          handle this only if the target does not support different pointer or
1580          address modes depending on the address space.  */
1581       if (!target_default_pointer_address_modes_p ())
1582         return 0;
1583
1584       {
1585         rtx temp = find_base_term (XEXP (x, 0));
1586
1587         if (temp != 0 && CONSTANT_P (temp))
1588           temp = convert_memory_address (Pmode, temp);
1589
1590         return temp;
1591       }
1592
1593     case VALUE:
1594       val = CSELIB_VAL_PTR (x);
1595       ret = NULL_RTX;
1596
1597       if (!val)
1598         return ret;
1599
1600       f = val->locs;
1601       /* Temporarily reset val->locs to avoid infinite recursion.  */
1602       val->locs = NULL;
1603
1604       for (l = f; l; l = l->next)
1605         if (GET_CODE (l->loc) == VALUE
1606             && CSELIB_VAL_PTR (l->loc)->locs
1607             && !CSELIB_VAL_PTR (l->loc)->locs->next
1608             && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1609           continue;
1610         else if ((ret = find_base_term (l->loc)) != 0)
1611           break;
1612
1613       val->locs = f;
1614       return ret;
1615
1616     case LO_SUM:
1617       /* The standard form is (lo_sum reg sym) so look only at the
1618          second operand.  */
1619       return find_base_term (XEXP (x, 1));
1620
1621     case CONST:
1622       x = XEXP (x, 0);
1623       if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
1624         return 0;
1625       /* Fall through.  */
1626     case PLUS:
1627     case MINUS:
1628       {
1629         rtx tmp1 = XEXP (x, 0);
1630         rtx tmp2 = XEXP (x, 1);
1631
1632         /* This is a little bit tricky since we have to determine which of
1633            the two operands represents the real base address.  Otherwise this
1634            routine may return the index register instead of the base register.
1635
1636            That may cause us to believe no aliasing was possible, when in
1637            fact aliasing is possible.
1638
1639            We use a few simple tests to guess the base register.  Additional
1640            tests can certainly be added.  For example, if one of the operands
1641            is a shift or multiply, then it must be the index register and the
1642            other operand is the base register.  */
1643
1644         if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
1645           return find_base_term (tmp2);
1646
1647         /* If either operand is known to be a pointer, then use it
1648            to determine the base term.  */
1649         if (REG_P (tmp1) && REG_POINTER (tmp1))
1650           {
1651             rtx base = find_base_term (tmp1);
1652             if (base)
1653               return base;
1654           }
1655
1656         if (REG_P (tmp2) && REG_POINTER (tmp2))
1657           {
1658             rtx base = find_base_term (tmp2);
1659             if (base)
1660               return base;
1661           }
1662
1663         /* Neither operand was known to be a pointer.  Go ahead and find the
1664            base term for both operands.  */
1665         tmp1 = find_base_term (tmp1);
1666         tmp2 = find_base_term (tmp2);
1667
1668         /* If either base term is named object or a special address
1669            (like an argument or stack reference), then use it for the
1670            base term.  */
1671         if (tmp1 != 0
1672             && (GET_CODE (tmp1) == SYMBOL_REF
1673                 || GET_CODE (tmp1) == LABEL_REF
1674                 || (GET_CODE (tmp1) == ADDRESS
1675                     && GET_MODE (tmp1) != VOIDmode)))
1676           return tmp1;
1677
1678         if (tmp2 != 0
1679             && (GET_CODE (tmp2) == SYMBOL_REF
1680                 || GET_CODE (tmp2) == LABEL_REF
1681                 || (GET_CODE (tmp2) == ADDRESS
1682                     && GET_MODE (tmp2) != VOIDmode)))
1683           return tmp2;
1684
1685         /* We could not determine which of the two operands was the
1686            base register and which was the index.  So we can determine
1687            nothing from the base alias check.  */
1688         return 0;
1689       }
1690
1691     case AND:
1692       if (CONST_INT_P (XEXP (x, 1)) && INTVAL (XEXP (x, 1)) != 0)
1693         return find_base_term (XEXP (x, 0));
1694       return 0;
1695
1696     case SYMBOL_REF:
1697     case LABEL_REF:
1698       return x;
1699
1700     default:
1701       return 0;
1702     }
1703 }
1704
1705 /* Return 0 if the addresses X and Y are known to point to different
1706    objects, 1 if they might be pointers to the same object.  */
1707
1708 static int
1709 base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
1710                   enum machine_mode y_mode)
1711 {
1712   rtx x_base = find_base_term (x);
1713   rtx y_base = find_base_term (y);
1714
1715   /* If the address itself has no known base see if a known equivalent
1716      value has one.  If either address still has no known base, nothing
1717      is known about aliasing.  */
1718   if (x_base == 0)
1719     {
1720       rtx x_c;
1721
1722       if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
1723         return 1;
1724
1725       x_base = find_base_term (x_c);
1726       if (x_base == 0)
1727         return 1;
1728     }
1729
1730   if (y_base == 0)
1731     {
1732       rtx y_c;
1733       if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
1734         return 1;
1735
1736       y_base = find_base_term (y_c);
1737       if (y_base == 0)
1738         return 1;
1739     }
1740
1741   /* If the base addresses are equal nothing is known about aliasing.  */
1742   if (rtx_equal_p (x_base, y_base))
1743     return 1;
1744
1745   /* The base addresses are different expressions.  If they are not accessed
1746      via AND, there is no conflict.  We can bring knowledge of object
1747      alignment into play here.  For example, on alpha, "char a, b;" can
1748      alias one another, though "char a; long b;" cannot.  AND addesses may
1749      implicitly alias surrounding objects; i.e. unaligned access in DImode
1750      via AND address can alias all surrounding object types except those
1751      with aligment 8 or higher.  */
1752   if (GET_CODE (x) == AND && GET_CODE (y) == AND)
1753     return 1;
1754   if (GET_CODE (x) == AND
1755       && (!CONST_INT_P (XEXP (x, 1))
1756           || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
1757     return 1;
1758   if (GET_CODE (y) == AND
1759       && (!CONST_INT_P (XEXP (y, 1))
1760           || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
1761     return 1;
1762
1763   /* Differing symbols not accessed via AND never alias.  */
1764   if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
1765     return 0;
1766
1767   /* If one address is a stack reference there can be no alias:
1768      stack references using different base registers do not alias,
1769      a stack reference can not alias a parameter, and a stack reference
1770      can not alias a global.  */
1771   if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
1772       || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
1773     return 0;
1774
1775   return 1;
1776 }
1777
1778 /* Convert the address X into something we can use.  This is done by returning
1779    it unchanged unless it is a value; in the latter case we call cselib to get
1780    a more useful rtx.  */
1781
1782 rtx
1783 get_addr (rtx x)
1784 {
1785   cselib_val *v;
1786   struct elt_loc_list *l;
1787
1788   if (GET_CODE (x) != VALUE)
1789     return x;
1790   v = CSELIB_VAL_PTR (x);
1791   if (v)
1792     {
1793       for (l = v->locs; l; l = l->next)
1794         if (CONSTANT_P (l->loc))
1795           return l->loc;
1796       for (l = v->locs; l; l = l->next)
1797         if (!REG_P (l->loc) && !MEM_P (l->loc))
1798           return l->loc;
1799       if (v->locs)
1800         return v->locs->loc;
1801     }
1802   return x;
1803 }
1804
1805 /*  Return the address of the (N_REFS + 1)th memory reference to ADDR
1806     where SIZE is the size in bytes of the memory reference.  If ADDR
1807     is not modified by the memory reference then ADDR is returned.  */
1808
1809 static rtx
1810 addr_side_effect_eval (rtx addr, int size, int n_refs)
1811 {
1812   int offset = 0;
1813
1814   switch (GET_CODE (addr))
1815     {
1816     case PRE_INC:
1817       offset = (n_refs + 1) * size;
1818       break;
1819     case PRE_DEC:
1820       offset = -(n_refs + 1) * size;
1821       break;
1822     case POST_INC:
1823       offset = n_refs * size;
1824       break;
1825     case POST_DEC:
1826       offset = -n_refs * size;
1827       break;
1828
1829     default:
1830       return addr;
1831     }
1832
1833   if (offset)
1834     addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
1835                          GEN_INT (offset));
1836   else
1837     addr = XEXP (addr, 0);
1838   addr = canon_rtx (addr);
1839
1840   return addr;
1841 }
1842
1843 /* Return one if X and Y (memory addresses) reference the
1844    same location in memory or if the references overlap.
1845    Return zero if they do not overlap, else return
1846    minus one in which case they still might reference the same location.
1847
1848    C is an offset accumulator.  When
1849    C is nonzero, we are testing aliases between X and Y + C.
1850    XSIZE is the size in bytes of the X reference,
1851    similarly YSIZE is the size in bytes for Y.
1852    Expect that canon_rtx has been already called for X and Y.
1853
1854    If XSIZE or YSIZE is zero, we do not know the amount of memory being
1855    referenced (the reference was BLKmode), so make the most pessimistic
1856    assumptions.
1857
1858    If XSIZE or YSIZE is negative, we may access memory outside the object
1859    being referenced as a side effect.  This can happen when using AND to
1860    align memory references, as is done on the Alpha.
1861
1862    Nice to notice that varying addresses cannot conflict with fp if no
1863    local variables had their addresses taken, but that's too hard now.
1864
1865    ???  Contrary to the tree alias oracle this does not return
1866    one for X + non-constant and Y + non-constant when X and Y are equal.
1867    If that is fixed the TBAA hack for union type-punning can be removed.  */
1868
1869 static int
1870 memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
1871 {
1872   if (GET_CODE (x) == VALUE)
1873     {
1874       if (REG_P (y))
1875         {
1876           struct elt_loc_list *l = NULL;
1877           if (CSELIB_VAL_PTR (x))
1878             for (l = CSELIB_VAL_PTR (x)->locs; l; l = l->next)
1879               if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
1880                 break;
1881           if (l)
1882             x = y;
1883           else
1884             x = get_addr (x);
1885         }
1886       /* Don't call get_addr if y is the same VALUE.  */
1887       else if (x != y)
1888         x = get_addr (x);
1889     }
1890   if (GET_CODE (y) == VALUE)
1891     {
1892       if (REG_P (x))
1893         {
1894           struct elt_loc_list *l = NULL;
1895           if (CSELIB_VAL_PTR (y))
1896             for (l = CSELIB_VAL_PTR (y)->locs; l; l = l->next)
1897               if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
1898                 break;
1899           if (l)
1900             y = x;
1901           else
1902             y = get_addr (y);
1903         }
1904       /* Don't call get_addr if x is the same VALUE.  */
1905       else if (y != x)
1906         y = get_addr (y);
1907     }
1908   if (GET_CODE (x) == HIGH)
1909     x = XEXP (x, 0);
1910   else if (GET_CODE (x) == LO_SUM)
1911     x = XEXP (x, 1);
1912   else
1913     x = addr_side_effect_eval (x, xsize, 0);
1914   if (GET_CODE (y) == HIGH)
1915     y = XEXP (y, 0);
1916   else if (GET_CODE (y) == LO_SUM)
1917     y = XEXP (y, 1);
1918   else
1919     y = addr_side_effect_eval (y, ysize, 0);
1920
1921   if (rtx_equal_for_memref_p (x, y))
1922     {
1923       if (xsize <= 0 || ysize <= 0)
1924         return 1;
1925       if (c >= 0 && xsize > c)
1926         return 1;
1927       if (c < 0 && ysize+c > 0)
1928         return 1;
1929       return 0;
1930     }
1931
1932   /* This code used to check for conflicts involving stack references and
1933      globals but the base address alias code now handles these cases.  */
1934
1935   if (GET_CODE (x) == PLUS)
1936     {
1937       /* The fact that X is canonicalized means that this
1938          PLUS rtx is canonicalized.  */
1939       rtx x0 = XEXP (x, 0);
1940       rtx x1 = XEXP (x, 1);
1941
1942       if (GET_CODE (y) == PLUS)
1943         {
1944           /* The fact that Y is canonicalized means that this
1945              PLUS rtx is canonicalized.  */
1946           rtx y0 = XEXP (y, 0);
1947           rtx y1 = XEXP (y, 1);
1948
1949           if (rtx_equal_for_memref_p (x1, y1))
1950             return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1951           if (rtx_equal_for_memref_p (x0, y0))
1952             return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1953           if (CONST_INT_P (x1))
1954             {
1955               if (CONST_INT_P (y1))
1956                 return memrefs_conflict_p (xsize, x0, ysize, y0,
1957                                            c - INTVAL (x1) + INTVAL (y1));
1958               else
1959                 return memrefs_conflict_p (xsize, x0, ysize, y,
1960                                            c - INTVAL (x1));
1961             }
1962           else if (CONST_INT_P (y1))
1963             return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1964
1965           return -1;
1966         }
1967       else if (CONST_INT_P (x1))
1968         return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1969     }
1970   else if (GET_CODE (y) == PLUS)
1971     {
1972       /* The fact that Y is canonicalized means that this
1973          PLUS rtx is canonicalized.  */
1974       rtx y0 = XEXP (y, 0);
1975       rtx y1 = XEXP (y, 1);
1976
1977       if (CONST_INT_P (y1))
1978         return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1979       else
1980         return -1;
1981     }
1982
1983   if (GET_CODE (x) == GET_CODE (y))
1984     switch (GET_CODE (x))
1985       {
1986       case MULT:
1987         {
1988           /* Handle cases where we expect the second operands to be the
1989              same, and check only whether the first operand would conflict
1990              or not.  */
1991           rtx x0, y0;
1992           rtx x1 = canon_rtx (XEXP (x, 1));
1993           rtx y1 = canon_rtx (XEXP (y, 1));
1994           if (! rtx_equal_for_memref_p (x1, y1))
1995             return -1;
1996           x0 = canon_rtx (XEXP (x, 0));
1997           y0 = canon_rtx (XEXP (y, 0));
1998           if (rtx_equal_for_memref_p (x0, y0))
1999             return (xsize == 0 || ysize == 0
2000                     || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
2001
2002           /* Can't properly adjust our sizes.  */
2003           if (!CONST_INT_P (x1))
2004             return -1;
2005           xsize /= INTVAL (x1);
2006           ysize /= INTVAL (x1);
2007           c /= INTVAL (x1);
2008           return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2009         }
2010
2011       default:
2012         break;
2013       }
2014
2015   /* Treat an access through an AND (e.g. a subword access on an Alpha)
2016      as an access with indeterminate size.  Assume that references
2017      besides AND are aligned, so if the size of the other reference is
2018      at least as large as the alignment, assume no other overlap.  */
2019   if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2020     {
2021       if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
2022         xsize = -1;
2023       return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
2024     }
2025   if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2026     {
2027       /* ??? If we are indexing far enough into the array/structure, we
2028          may yet be able to determine that we can not overlap.  But we
2029          also need to that we are far enough from the end not to overlap
2030          a following reference, so we do nothing with that for now.  */
2031       if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
2032         ysize = -1;
2033       return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
2034     }
2035
2036   if (CONSTANT_P (x))
2037     {
2038       if (CONST_INT_P (x) && CONST_INT_P (y))
2039         {
2040           c += (INTVAL (y) - INTVAL (x));
2041           return (xsize <= 0 || ysize <= 0
2042                   || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
2043         }
2044
2045       if (GET_CODE (x) == CONST)
2046         {
2047           if (GET_CODE (y) == CONST)
2048             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2049                                        ysize, canon_rtx (XEXP (y, 0)), c);
2050           else
2051             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2052                                        ysize, y, c);
2053         }
2054       if (GET_CODE (y) == CONST)
2055         return memrefs_conflict_p (xsize, x, ysize,
2056                                    canon_rtx (XEXP (y, 0)), c);
2057
2058       if (CONSTANT_P (y))
2059         return (xsize <= 0 || ysize <= 0
2060                 || (rtx_equal_for_memref_p (x, y)
2061                     && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
2062
2063       return -1;
2064     }
2065
2066   return -1;
2067 }
2068
2069 /* Functions to compute memory dependencies.
2070
2071    Since we process the insns in execution order, we can build tables
2072    to keep track of what registers are fixed (and not aliased), what registers
2073    are varying in known ways, and what registers are varying in unknown
2074    ways.
2075
2076    If both memory references are volatile, then there must always be a
2077    dependence between the two references, since their order can not be
2078    changed.  A volatile and non-volatile reference can be interchanged
2079    though.
2080
2081    A MEM_IN_STRUCT reference at a non-AND varying address can never
2082    conflict with a non-MEM_IN_STRUCT reference at a fixed address.  We
2083    also must allow AND addresses, because they may generate accesses
2084    outside the object being referenced.  This is used to generate
2085    aligned addresses from unaligned addresses, for instance, the alpha
2086    storeqi_unaligned pattern.  */
2087
2088 /* Read dependence: X is read after read in MEM takes place.  There can
2089    only be a dependence here if both reads are volatile.  */
2090
2091 int
2092 read_dependence (const_rtx mem, const_rtx x)
2093 {
2094   return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
2095 }
2096
2097 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
2098    MEM2 is a reference to a structure at a varying address, or returns
2099    MEM2 if vice versa.  Otherwise, returns NULL_RTX.  If a non-NULL
2100    value is returned MEM1 and MEM2 can never alias.  VARIES_P is used
2101    to decide whether or not an address may vary; it should return
2102    nonzero whenever variation is possible.
2103    MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2.  */
2104
2105 static const_rtx
2106 fixed_scalar_and_varying_struct_p (const_rtx mem1, const_rtx mem2, rtx mem1_addr,
2107                                    rtx mem2_addr,
2108                                    bool (*varies_p) (const_rtx, bool))
2109 {
2110   if (! flag_strict_aliasing)
2111     return NULL_RTX;
2112
2113   if (MEM_ALIAS_SET (mem2)
2114       && MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
2115       && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
2116     /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
2117        varying address.  */
2118     return mem1;
2119
2120   if (MEM_ALIAS_SET (mem1)
2121       && MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
2122       && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
2123     /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
2124        varying address.  */
2125     return mem2;
2126
2127   return NULL_RTX;
2128 }
2129
2130 /* Returns nonzero if something about the mode or address format MEM1
2131    indicates that it might well alias *anything*.  */
2132
2133 static int
2134 aliases_everything_p (const_rtx mem)
2135 {
2136   if (GET_CODE (XEXP (mem, 0)) == AND)
2137     /* If the address is an AND, it's very hard to know at what it is
2138        actually pointing.  */
2139     return 1;
2140
2141   return 0;
2142 }
2143
2144 /* Return true if we can determine that the fields referenced cannot
2145    overlap for any pair of objects.  */
2146
2147 static bool
2148 nonoverlapping_component_refs_p (const_tree x, const_tree y)
2149 {
2150   const_tree fieldx, fieldy, typex, typey, orig_y;
2151
2152   if (!flag_strict_aliasing)
2153     return false;
2154
2155   do
2156     {
2157       /* The comparison has to be done at a common type, since we don't
2158          know how the inheritance hierarchy works.  */
2159       orig_y = y;
2160       do
2161         {
2162           fieldx = TREE_OPERAND (x, 1);
2163           typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
2164
2165           y = orig_y;
2166           do
2167             {
2168               fieldy = TREE_OPERAND (y, 1);
2169               typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
2170
2171               if (typex == typey)
2172                 goto found;
2173
2174               y = TREE_OPERAND (y, 0);
2175             }
2176           while (y && TREE_CODE (y) == COMPONENT_REF);
2177
2178           x = TREE_OPERAND (x, 0);
2179         }
2180       while (x && TREE_CODE (x) == COMPONENT_REF);
2181       /* Never found a common type.  */
2182       return false;
2183
2184     found:
2185       /* If we're left with accessing different fields of a structure,
2186          then no overlap.  */
2187       if (TREE_CODE (typex) == RECORD_TYPE
2188           && fieldx != fieldy)
2189         return true;
2190
2191       /* The comparison on the current field failed.  If we're accessing
2192          a very nested structure, look at the next outer level.  */
2193       x = TREE_OPERAND (x, 0);
2194       y = TREE_OPERAND (y, 0);
2195     }
2196   while (x && y
2197          && TREE_CODE (x) == COMPONENT_REF
2198          && TREE_CODE (y) == COMPONENT_REF);
2199
2200   return false;
2201 }
2202
2203 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it.  */
2204
2205 static tree
2206 decl_for_component_ref (tree x)
2207 {
2208   do
2209     {
2210       x = TREE_OPERAND (x, 0);
2211     }
2212   while (x && TREE_CODE (x) == COMPONENT_REF);
2213
2214   return x && DECL_P (x) ? x : NULL_TREE;
2215 }
2216
2217 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2218    for the offset of the field reference.  *KNOWN_P says whether the
2219    offset is known.  */
2220
2221 static void
2222 adjust_offset_for_component_ref (tree x, bool *known_p,
2223                                  HOST_WIDE_INT *offset)
2224 {
2225   if (!*known_p)
2226     return;
2227   do
2228     {
2229       tree xoffset = component_ref_field_offset (x);
2230       tree field = TREE_OPERAND (x, 1);
2231
2232       if (! host_integerp (xoffset, 1))
2233         {
2234           *known_p = false;
2235           return;
2236         }
2237       *offset += (tree_low_cst (xoffset, 1)
2238                   + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2239                      / BITS_PER_UNIT));
2240
2241       x = TREE_OPERAND (x, 0);
2242     }
2243   while (x && TREE_CODE (x) == COMPONENT_REF);
2244 }
2245
2246 /* Return nonzero if we can determine the exprs corresponding to memrefs
2247    X and Y and they do not overlap. 
2248    If LOOP_VARIANT is set, skip offset-based disambiguation */
2249
2250 int
2251 nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2252 {
2253   tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2254   rtx rtlx, rtly;
2255   rtx basex, basey;
2256   bool moffsetx_known_p, moffsety_known_p;
2257   HOST_WIDE_INT moffsetx = 0, moffsety = 0;
2258   HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
2259
2260   /* Unless both have exprs, we can't tell anything.  */
2261   if (exprx == 0 || expry == 0)
2262     return 0;
2263
2264   /* For spill-slot accesses make sure we have valid offsets.  */
2265   if ((exprx == get_spill_slot_decl (false)
2266        && ! MEM_OFFSET_KNOWN_P (x))
2267       || (expry == get_spill_slot_decl (false)
2268           && ! MEM_OFFSET_KNOWN_P (y)))
2269     return 0;
2270
2271   /* If both are field references, we may be able to determine something.  */
2272   if (TREE_CODE (exprx) == COMPONENT_REF
2273       && TREE_CODE (expry) == COMPONENT_REF
2274       && nonoverlapping_component_refs_p (exprx, expry))
2275     return 1;
2276
2277
2278   /* If the field reference test failed, look at the DECLs involved.  */
2279   moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2280   if (moffsetx_known_p)
2281     moffsetx = MEM_OFFSET (x);
2282   if (TREE_CODE (exprx) == COMPONENT_REF)
2283     {
2284       tree t = decl_for_component_ref (exprx);
2285       if (! t)
2286         return 0;
2287       adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2288       exprx = t;
2289     }
2290
2291   moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2292   if (moffsety_known_p)
2293     moffsety = MEM_OFFSET (y);
2294   if (TREE_CODE (expry) == COMPONENT_REF)
2295     {
2296       tree t = decl_for_component_ref (expry);
2297       if (! t)
2298         return 0;
2299       adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2300       expry = t;
2301     }
2302
2303   if (! DECL_P (exprx) || ! DECL_P (expry))
2304     return 0;
2305
2306   /* With invalid code we can end up storing into the constant pool.
2307      Bail out to avoid ICEing when creating RTL for this.
2308      See gfortran.dg/lto/20091028-2_0.f90.  */
2309   if (TREE_CODE (exprx) == CONST_DECL
2310       || TREE_CODE (expry) == CONST_DECL)
2311     return 1;
2312
2313   rtlx = DECL_RTL (exprx);
2314   rtly = DECL_RTL (expry);
2315
2316   /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2317      can't overlap unless they are the same because we never reuse that part
2318      of the stack frame used for locals for spilled pseudos.  */
2319   if ((!MEM_P (rtlx) || !MEM_P (rtly))
2320       && ! rtx_equal_p (rtlx, rtly))
2321     return 1;
2322
2323   /* If we have MEMs refering to different address spaces (which can
2324      potentially overlap), we cannot easily tell from the addresses
2325      whether the references overlap.  */
2326   if (MEM_P (rtlx) && MEM_P (rtly)
2327       && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2328     return 0;
2329
2330   /* Get the base and offsets of both decls.  If either is a register, we
2331      know both are and are the same, so use that as the base.  The only
2332      we can avoid overlap is if we can deduce that they are nonoverlapping
2333      pieces of that decl, which is very rare.  */
2334   basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2335   if (GET_CODE (basex) == PLUS && CONST_INT_P (XEXP (basex, 1)))
2336     offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2337
2338   basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2339   if (GET_CODE (basey) == PLUS && CONST_INT_P (XEXP (basey, 1)))
2340     offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2341
2342   /* If the bases are different, we know they do not overlap if both
2343      are constants or if one is a constant and the other a pointer into the
2344      stack frame.  Otherwise a different base means we can't tell if they
2345      overlap or not.  */
2346   if (! rtx_equal_p (basex, basey))
2347     return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2348             || (CONSTANT_P (basex) && REG_P (basey)
2349                 && REGNO_PTR_FRAME_P (REGNO (basey)))
2350             || (CONSTANT_P (basey) && REG_P (basex)
2351                 && REGNO_PTR_FRAME_P (REGNO (basex))));
2352
2353   /* Offset based disambiguation not appropriate for loop invariant */
2354   if (loop_invariant)
2355     return 0;              
2356
2357   sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2358            : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2359            : -1);
2360   sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2361            : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2362            : -1);
2363
2364   /* If we have an offset for either memref, it can update the values computed
2365      above.  */
2366   if (moffsetx_known_p)
2367     offsetx += moffsetx, sizex -= moffsetx;
2368   if (moffsety_known_p)
2369     offsety += moffsety, sizey -= moffsety;
2370
2371   /* If a memref has both a size and an offset, we can use the smaller size.
2372      We can't do this if the offset isn't known because we must view this
2373      memref as being anywhere inside the DECL's MEM.  */
2374   if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2375     sizex = MEM_SIZE (x);
2376   if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2377     sizey = MEM_SIZE (y);
2378
2379   /* Put the values of the memref with the lower offset in X's values.  */
2380   if (offsetx > offsety)
2381     {
2382       tem = offsetx, offsetx = offsety, offsety = tem;
2383       tem = sizex, sizex = sizey, sizey = tem;
2384     }
2385
2386   /* If we don't know the size of the lower-offset value, we can't tell
2387      if they conflict.  Otherwise, we do the test.  */
2388   return sizex >= 0 && offsety >= offsetx + sizex;
2389 }
2390
2391 /* Helper for true_dependence and canon_true_dependence.
2392    Checks for true dependence: X is read after store in MEM takes place.
2393
2394    VARIES is the function that should be used as rtx_varies function.
2395
2396    If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2397    NULL_RTX, and the canonical addresses of MEM and X are both computed
2398    here.  If MEM_CANONICALIZED, then MEM must be already canonicalized.
2399
2400    If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2401
2402    Returns 1 if there is a true dependence, 0 otherwise.  */
2403
2404 static int
2405 true_dependence_1 (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2406                    const_rtx x, rtx x_addr, bool (*varies) (const_rtx, bool),
2407                    bool mem_canonicalized)
2408 {
2409   rtx base;
2410   int ret;
2411
2412   gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2413                        : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2414
2415   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2416     return 1;
2417
2418   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2419      This is used in epilogue deallocation functions, and in cselib.  */
2420   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2421     return 1;
2422   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2423     return 1;
2424   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2425       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2426     return 1;
2427
2428   /* Read-only memory is by definition never modified, and therefore can't
2429      conflict with anything.  We don't expect to find read-only set on MEM,
2430      but stupid user tricks can produce them, so don't die.  */
2431   if (MEM_READONLY_P (x))
2432     return 0;
2433
2434   /* If we have MEMs refering to different address spaces (which can
2435      potentially overlap), we cannot easily tell from the addresses
2436      whether the references overlap.  */
2437   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2438     return 1;
2439
2440   if (! mem_addr)
2441     {
2442       mem_addr = XEXP (mem, 0);
2443       if (mem_mode == VOIDmode)
2444         mem_mode = GET_MODE (mem);
2445     }
2446
2447   if (! x_addr)
2448     {
2449       x_addr = XEXP (x, 0);
2450       if (!((GET_CODE (x_addr) == VALUE
2451              && GET_CODE (mem_addr) != VALUE
2452              && reg_mentioned_p (x_addr, mem_addr))
2453             || (GET_CODE (x_addr) != VALUE
2454                 && GET_CODE (mem_addr) == VALUE
2455                 && reg_mentioned_p (mem_addr, x_addr))))
2456         {
2457           x_addr = get_addr (x_addr);
2458           if (! mem_canonicalized)
2459             mem_addr = get_addr (mem_addr);
2460         }
2461     }
2462
2463   base = find_base_term (x_addr);
2464   if (base && (GET_CODE (base) == LABEL_REF
2465                || (GET_CODE (base) == SYMBOL_REF
2466                    && CONSTANT_POOL_ADDRESS_P (base))))
2467     return 0;
2468
2469   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2470     return 0;
2471
2472   x_addr = canon_rtx (x_addr);
2473   if (!mem_canonicalized)
2474     mem_addr = canon_rtx (mem_addr);
2475
2476   if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2477                                  SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2478     return ret;
2479
2480   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2481     return 0;
2482
2483   if (nonoverlapping_memrefs_p (mem, x, false))
2484     return 0;
2485
2486   if (aliases_everything_p (x))
2487     return 1;
2488
2489   /* We cannot use aliases_everything_p to test MEM, since we must look
2490      at MEM_ADDR, rather than XEXP (mem, 0).  */
2491   if (GET_CODE (mem_addr) == AND)
2492     return 1;
2493
2494   /* ??? In true_dependence we also allow BLKmode to alias anything.  Why
2495      don't we do this in anti_dependence and output_dependence?  */
2496   if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2497     return 1;
2498
2499   if (fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, varies))
2500     return 0;
2501
2502   return rtx_refs_may_alias_p (x, mem, true);
2503 }
2504
2505 /* True dependence: X is read after store in MEM takes place.  */
2506
2507 int
2508 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x,
2509                  bool (*varies) (const_rtx, bool))
2510 {
2511   return true_dependence_1 (mem, mem_mode, NULL_RTX,
2512                             x, NULL_RTX, varies,
2513                             /*mem_canonicalized=*/false);
2514 }
2515
2516 /* Canonical true dependence: X is read after store in MEM takes place.
2517    Variant of true_dependence which assumes MEM has already been
2518    canonicalized (hence we no longer do that here).
2519    The mem_addr argument has been added, since true_dependence_1 computed
2520    this value prior to canonicalizing.  */
2521
2522 int
2523 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2524                        const_rtx x, rtx x_addr, bool (*varies) (const_rtx, bool))
2525 {
2526   return true_dependence_1 (mem, mem_mode, mem_addr,
2527                             x, x_addr, varies,
2528                             /*mem_canonicalized=*/true);
2529 }
2530
2531 /* Returns nonzero if a write to X might alias a previous read from
2532    (or, if WRITEP is nonzero, a write to) MEM.  */
2533
2534 static int
2535 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2536 {
2537   rtx x_addr, mem_addr;
2538   const_rtx fixed_scalar;
2539   rtx base;
2540   int ret;
2541
2542   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2543     return 1;
2544
2545   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2546      This is used in epilogue deallocation functions.  */
2547   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2548     return 1;
2549   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2550     return 1;
2551   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2552       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2553     return 1;
2554
2555   /* A read from read-only memory can't conflict with read-write memory.  */
2556   if (!writep && MEM_READONLY_P (mem))
2557     return 0;
2558
2559   /* If we have MEMs refering to different address spaces (which can
2560      potentially overlap), we cannot easily tell from the addresses
2561      whether the references overlap.  */
2562   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2563     return 1;
2564
2565   x_addr = XEXP (x, 0);
2566   mem_addr = XEXP (mem, 0);
2567   if (!((GET_CODE (x_addr) == VALUE
2568          && GET_CODE (mem_addr) != VALUE
2569          && reg_mentioned_p (x_addr, mem_addr))
2570         || (GET_CODE (x_addr) != VALUE
2571             && GET_CODE (mem_addr) == VALUE
2572             && reg_mentioned_p (mem_addr, x_addr))))
2573     {
2574       x_addr = get_addr (x_addr);
2575       mem_addr = get_addr (mem_addr);
2576     }
2577
2578   if (! writep)
2579     {
2580       base = find_base_term (mem_addr);
2581       if (base && (GET_CODE (base) == LABEL_REF
2582                    || (GET_CODE (base) == SYMBOL_REF
2583                        && CONSTANT_POOL_ADDRESS_P (base))))
2584         return 0;
2585     }
2586
2587   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2588                           GET_MODE (mem)))
2589     return 0;
2590
2591   x_addr = canon_rtx (x_addr);
2592   mem_addr = canon_rtx (mem_addr);
2593
2594   if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2595                                  SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2596     return ret;
2597
2598   if (nonoverlapping_memrefs_p (x, mem, false))
2599     return 0;
2600
2601   fixed_scalar
2602     = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2603                                          rtx_addr_varies_p);
2604
2605   if ((fixed_scalar == mem && !aliases_everything_p (x))
2606       || (fixed_scalar == x && !aliases_everything_p (mem)))
2607     return 0;
2608
2609   return rtx_refs_may_alias_p (x, mem, false);
2610 }
2611
2612 /* Anti dependence: X is written after read in MEM takes place.  */
2613
2614 int
2615 anti_dependence (const_rtx mem, const_rtx x)
2616 {
2617   return write_dependence_p (mem, x, /*writep=*/0);
2618 }
2619
2620 /* Output dependence: X is written after store in MEM takes place.  */
2621
2622 int
2623 output_dependence (const_rtx mem, const_rtx x)
2624 {
2625   return write_dependence_p (mem, x, /*writep=*/1);
2626 }
2627 \f
2628
2629
2630 /* Check whether X may be aliased with MEM.  Don't do offset-based
2631   memory disambiguation & TBAA.  */
2632 int
2633 may_alias_p (const_rtx mem, const_rtx x)
2634 {
2635   rtx x_addr, mem_addr;
2636
2637   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2638     return 1;
2639
2640   /* ??? In true_dependence we also allow BLKmode to alias anything. */
2641   if (GET_MODE (mem) == BLKmode || GET_MODE (x) == BLKmode)
2642     return 1;
2643     
2644   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2645       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2646     return 1;
2647
2648   /* Read-only memory is by definition never modified, and therefore can't
2649      conflict with anything.  We don't expect to find read-only set on MEM,
2650      but stupid user tricks can produce them, so don't die.  */
2651   if (MEM_READONLY_P (x))
2652     return 0;
2653
2654   /* If we have MEMs refering to different address spaces (which can
2655      potentially overlap), we cannot easily tell from the addresses
2656      whether the references overlap.  */
2657   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2658     return 1;
2659
2660   x_addr = XEXP (x, 0);
2661   mem_addr = XEXP (mem, 0);
2662   if (!((GET_CODE (x_addr) == VALUE
2663          && GET_CODE (mem_addr) != VALUE
2664          && reg_mentioned_p (x_addr, mem_addr))
2665         || (GET_CODE (x_addr) != VALUE
2666             && GET_CODE (mem_addr) == VALUE
2667             && reg_mentioned_p (mem_addr, x_addr))))
2668     {
2669       x_addr = get_addr (x_addr);
2670       mem_addr = get_addr (mem_addr);
2671     }
2672
2673   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), GET_MODE (mem_addr)))
2674     return 0;
2675
2676   x_addr = canon_rtx (x_addr);
2677   mem_addr = canon_rtx (mem_addr);
2678
2679   if (nonoverlapping_memrefs_p (mem, x, true))
2680     return 0;
2681
2682   if (aliases_everything_p (x))
2683     return 1;
2684
2685   /* We cannot use aliases_everything_p to test MEM, since we must look
2686      at MEM_ADDR, rather than XEXP (mem, 0).  */
2687   if (GET_CODE (mem_addr) == AND)
2688     return 1;
2689
2690   if (fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2691                                          rtx_addr_varies_p))
2692     return 0;
2693
2694   /* TBAA not valid for loop_invarint */
2695   return rtx_refs_may_alias_p (x, mem, false);
2696 }
2697
2698 void
2699 init_alias_target (void)
2700 {
2701   int i;
2702
2703   memset (static_reg_base_value, 0, sizeof static_reg_base_value);
2704
2705   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2706     /* Check whether this register can hold an incoming pointer
2707        argument.  FUNCTION_ARG_REGNO_P tests outgoing register
2708        numbers, so translate if necessary due to register windows.  */
2709     if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2710         && HARD_REGNO_MODE_OK (i, Pmode))
2711       static_reg_base_value[i]
2712         = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2713
2714   static_reg_base_value[STACK_POINTER_REGNUM]
2715     = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2716   static_reg_base_value[ARG_POINTER_REGNUM]
2717     = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2718   static_reg_base_value[FRAME_POINTER_REGNUM]
2719     = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2720 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2721   static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2722     = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2723 #endif
2724 }
2725
2726 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2727    to be memory reference.  */
2728 static bool memory_modified;
2729 static void
2730 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2731 {
2732   if (MEM_P (x))
2733     {
2734       if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
2735         memory_modified = true;
2736     }
2737 }
2738
2739
2740 /* Return true when INSN possibly modify memory contents of MEM
2741    (i.e. address can be modified).  */
2742 bool
2743 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
2744 {
2745   if (!INSN_P (insn))
2746     return false;
2747   memory_modified = false;
2748   note_stores (PATTERN (insn), memory_modified_1, CONST_CAST_RTX(mem));
2749   return memory_modified;
2750 }
2751
2752 /* Initialize the aliasing machinery.  Initialize the REG_KNOWN_VALUE
2753    array.  */
2754
2755 void
2756 init_alias_analysis (void)
2757 {
2758   unsigned int maxreg = max_reg_num ();
2759   int changed, pass;
2760   int i;
2761   unsigned int ui;
2762   rtx insn;
2763
2764   timevar_push (TV_ALIAS_ANALYSIS);
2765
2766   reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER;
2767   reg_known_value = ggc_alloc_cleared_vec_rtx (reg_known_value_size);
2768   reg_known_equiv_p = XCNEWVEC (bool, reg_known_value_size);
2769
2770   /* If we have memory allocated from the previous run, use it.  */
2771   if (old_reg_base_value)
2772     reg_base_value = old_reg_base_value;
2773
2774   if (reg_base_value)
2775     VEC_truncate (rtx, reg_base_value, 0);
2776
2777   VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2778
2779   new_reg_base_value = XNEWVEC (rtx, maxreg);
2780   reg_seen = XNEWVEC (char, maxreg);
2781
2782   /* The basic idea is that each pass through this loop will use the
2783      "constant" information from the previous pass to propagate alias
2784      information through another level of assignments.
2785
2786      This could get expensive if the assignment chains are long.  Maybe
2787      we should throttle the number of iterations, possibly based on
2788      the optimization level or flag_expensive_optimizations.
2789
2790      We could propagate more information in the first pass by making use
2791      of DF_REG_DEF_COUNT to determine immediately that the alias information
2792      for a pseudo is "constant".
2793
2794      A program with an uninitialized variable can cause an infinite loop
2795      here.  Instead of doing a full dataflow analysis to detect such problems
2796      we just cap the number of iterations for the loop.
2797
2798      The state of the arrays for the set chain in question does not matter
2799      since the program has undefined behavior.  */
2800
2801   pass = 0;
2802   do
2803     {
2804       /* Assume nothing will change this iteration of the loop.  */
2805       changed = 0;
2806
2807       /* We want to assign the same IDs each iteration of this loop, so
2808          start counting from zero each iteration of the loop.  */
2809       unique_id = 0;
2810
2811       /* We're at the start of the function each iteration through the
2812          loop, so we're copying arguments.  */
2813       copying_arguments = true;
2814
2815       /* Wipe the potential alias information clean for this pass.  */
2816       memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2817
2818       /* Wipe the reg_seen array clean.  */
2819       memset (reg_seen, 0, maxreg);
2820
2821       /* Mark all hard registers which may contain an address.
2822          The stack, frame and argument pointers may contain an address.
2823          An argument register which can hold a Pmode value may contain
2824          an address even if it is not in BASE_REGS.
2825
2826          The address expression is VOIDmode for an argument and
2827          Pmode for other registers.  */
2828
2829       memcpy (new_reg_base_value, static_reg_base_value,
2830               FIRST_PSEUDO_REGISTER * sizeof (rtx));
2831
2832       /* Walk the insns adding values to the new_reg_base_value array.  */
2833       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2834         {
2835           if (INSN_P (insn))
2836             {
2837               rtx note, set;
2838
2839 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2840               /* The prologue/epilogue insns are not threaded onto the
2841                  insn chain until after reload has completed.  Thus,
2842                  there is no sense wasting time checking if INSN is in
2843                  the prologue/epilogue until after reload has completed.  */
2844               if (reload_completed
2845                   && prologue_epilogue_contains (insn))
2846                 continue;
2847 #endif
2848
2849               /* If this insn has a noalias note, process it,  Otherwise,
2850                  scan for sets.  A simple set will have no side effects
2851                  which could change the base value of any other register.  */
2852
2853               if (GET_CODE (PATTERN (insn)) == SET
2854                   && REG_NOTES (insn) != 0
2855                   && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2856                 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2857               else
2858                 note_stores (PATTERN (insn), record_set, NULL);
2859
2860               set = single_set (insn);
2861
2862               if (set != 0
2863                   && REG_P (SET_DEST (set))
2864                   && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2865                 {
2866                   unsigned int regno = REGNO (SET_DEST (set));
2867                   rtx src = SET_SRC (set);
2868                   rtx t;
2869
2870                   note = find_reg_equal_equiv_note (insn);
2871                   if (note && REG_NOTE_KIND (note) == REG_EQUAL
2872                       && DF_REG_DEF_COUNT (regno) != 1)
2873                     note = NULL_RTX;
2874
2875                   if (note != NULL_RTX
2876                       && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2877                       && ! rtx_varies_p (XEXP (note, 0), 1)
2878                       && ! reg_overlap_mentioned_p (SET_DEST (set),
2879                                                     XEXP (note, 0)))
2880                     {
2881                       set_reg_known_value (regno, XEXP (note, 0));
2882                       set_reg_known_equiv_p (regno,
2883                         REG_NOTE_KIND (note) == REG_EQUIV);
2884                     }
2885                   else if (DF_REG_DEF_COUNT (regno) == 1
2886                            && GET_CODE (src) == PLUS
2887                            && REG_P (XEXP (src, 0))
2888                            && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2889                            && CONST_INT_P (XEXP (src, 1)))
2890                     {
2891                       t = plus_constant (t, INTVAL (XEXP (src, 1)));
2892                       set_reg_known_value (regno, t);
2893                       set_reg_known_equiv_p (regno, 0);
2894                     }
2895                   else if (DF_REG_DEF_COUNT (regno) == 1
2896                            && ! rtx_varies_p (src, 1))
2897                     {
2898                       set_reg_known_value (regno, src);
2899                       set_reg_known_equiv_p (regno, 0);
2900                     }
2901                 }
2902             }
2903           else if (NOTE_P (insn)
2904                    && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2905             copying_arguments = false;
2906         }
2907
2908       /* Now propagate values from new_reg_base_value to reg_base_value.  */
2909       gcc_assert (maxreg == (unsigned int) max_reg_num ());
2910
2911       for (ui = 0; ui < maxreg; ui++)
2912         {
2913           if (new_reg_base_value[ui]
2914               && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2915               && ! rtx_equal_p (new_reg_base_value[ui],
2916                                 VEC_index (rtx, reg_base_value, ui)))
2917             {
2918               VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2919               changed = 1;
2920             }
2921         }
2922     }
2923   while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2924
2925   /* Fill in the remaining entries.  */
2926   for (i = 0; i < (int)reg_known_value_size; i++)
2927     if (reg_known_value[i] == 0)
2928       reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER];
2929
2930   /* Clean up.  */
2931   free (new_reg_base_value);
2932   new_reg_base_value = 0;
2933   free (reg_seen);
2934   reg_seen = 0;
2935   timevar_pop (TV_ALIAS_ANALYSIS);
2936 }
2937
2938 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
2939    Special API for var-tracking pass purposes.  */
2940
2941 void
2942 vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
2943 {
2944   VEC_replace (rtx, reg_base_value, REGNO (reg1), REG_BASE_VALUE (reg2));
2945 }
2946
2947 void
2948 end_alias_analysis (void)
2949 {
2950   old_reg_base_value = reg_base_value;
2951   ggc_free (reg_known_value);
2952   reg_known_value = 0;
2953   reg_known_value_size = 0;
2954   free (reg_known_equiv_p);
2955   reg_known_equiv_p = 0;
2956 }
2957
2958 #include "gt-alias.h"