OSDN Git Service

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