OSDN Git Service

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