OSDN Git Service

6ec51ec2967bed6aa0709262fc6a86a7d536821e
[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;
1796           for (l = CSELIB_VAL_PTR (x)->locs; l; l = l->next)
1797             if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
1798               break;
1799           if (l)
1800             x = y;
1801           else
1802             x = get_addr (x);
1803         }
1804       /* Don't call get_addr if y is the same VALUE.  */
1805       else if (x != y)
1806         x = get_addr (x);
1807     }
1808   if (GET_CODE (y) == VALUE)
1809     {
1810       if (REG_P (x))
1811         {
1812           struct elt_loc_list *l;
1813           for (l = CSELIB_VAL_PTR (y)->locs; l; l = l->next)
1814             if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
1815               break;
1816           if (l)
1817             y = x;
1818           else
1819             y = get_addr (y);
1820         }
1821       /* Don't call get_addr if x is the same VALUE.  */
1822       else if (y != x)
1823         y = get_addr (y);
1824     }
1825   if (GET_CODE (x) == HIGH)
1826     x = XEXP (x, 0);
1827   else if (GET_CODE (x) == LO_SUM)
1828     x = XEXP (x, 1);
1829   else
1830     x = addr_side_effect_eval (x, xsize, 0);
1831   if (GET_CODE (y) == HIGH)
1832     y = XEXP (y, 0);
1833   else if (GET_CODE (y) == LO_SUM)
1834     y = XEXP (y, 1);
1835   else
1836     y = addr_side_effect_eval (y, ysize, 0);
1837
1838   if (rtx_equal_for_memref_p (x, y))
1839     {
1840       if (xsize <= 0 || ysize <= 0)
1841         return 1;
1842       if (c >= 0 && xsize > c)
1843         return 1;
1844       if (c < 0 && ysize+c > 0)
1845         return 1;
1846       return 0;
1847     }
1848
1849   /* This code used to check for conflicts involving stack references and
1850      globals but the base address alias code now handles these cases.  */
1851
1852   if (GET_CODE (x) == PLUS)
1853     {
1854       /* The fact that X is canonicalized means that this
1855          PLUS rtx is canonicalized.  */
1856       rtx x0 = XEXP (x, 0);
1857       rtx x1 = XEXP (x, 1);
1858
1859       if (GET_CODE (y) == PLUS)
1860         {
1861           /* The fact that Y is canonicalized means that this
1862              PLUS rtx is canonicalized.  */
1863           rtx y0 = XEXP (y, 0);
1864           rtx y1 = XEXP (y, 1);
1865
1866           if (rtx_equal_for_memref_p (x1, y1))
1867             return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1868           if (rtx_equal_for_memref_p (x0, y0))
1869             return memrefs_conflict_p (xsize, x1, ysize, y1, c);
1870           if (CONST_INT_P (x1))
1871             {
1872               if (CONST_INT_P (y1))
1873                 return memrefs_conflict_p (xsize, x0, ysize, y0,
1874                                            c - INTVAL (x1) + INTVAL (y1));
1875               else
1876                 return memrefs_conflict_p (xsize, x0, ysize, y,
1877                                            c - INTVAL (x1));
1878             }
1879           else if (CONST_INT_P (y1))
1880             return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1881
1882           return -1;
1883         }
1884       else if (CONST_INT_P (x1))
1885         return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
1886     }
1887   else if (GET_CODE (y) == PLUS)
1888     {
1889       /* The fact that Y is canonicalized means that this
1890          PLUS rtx is canonicalized.  */
1891       rtx y0 = XEXP (y, 0);
1892       rtx y1 = XEXP (y, 1);
1893
1894       if (CONST_INT_P (y1))
1895         return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
1896       else
1897         return -1;
1898     }
1899
1900   if (GET_CODE (x) == GET_CODE (y))
1901     switch (GET_CODE (x))
1902       {
1903       case MULT:
1904         {
1905           /* Handle cases where we expect the second operands to be the
1906              same, and check only whether the first operand would conflict
1907              or not.  */
1908           rtx x0, y0;
1909           rtx x1 = canon_rtx (XEXP (x, 1));
1910           rtx y1 = canon_rtx (XEXP (y, 1));
1911           if (! rtx_equal_for_memref_p (x1, y1))
1912             return -1;
1913           x0 = canon_rtx (XEXP (x, 0));
1914           y0 = canon_rtx (XEXP (y, 0));
1915           if (rtx_equal_for_memref_p (x0, y0))
1916             return (xsize == 0 || ysize == 0
1917                     || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1918
1919           /* Can't properly adjust our sizes.  */
1920           if (!CONST_INT_P (x1))
1921             return -1;
1922           xsize /= INTVAL (x1);
1923           ysize /= INTVAL (x1);
1924           c /= INTVAL (x1);
1925           return memrefs_conflict_p (xsize, x0, ysize, y0, c);
1926         }
1927
1928       default:
1929         break;
1930       }
1931
1932   /* Treat an access through an AND (e.g. a subword access on an Alpha)
1933      as an access with indeterminate size.  Assume that references
1934      besides AND are aligned, so if the size of the other reference is
1935      at least as large as the alignment, assume no other overlap.  */
1936   if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
1937     {
1938       if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
1939         xsize = -1;
1940       return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
1941     }
1942   if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
1943     {
1944       /* ??? If we are indexing far enough into the array/structure, we
1945          may yet be able to determine that we can not overlap.  But we
1946          also need to that we are far enough from the end not to overlap
1947          a following reference, so we do nothing with that for now.  */
1948       if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
1949         ysize = -1;
1950       return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
1951     }
1952
1953   if (CONSTANT_P (x))
1954     {
1955       if (CONST_INT_P (x) && CONST_INT_P (y))
1956         {
1957           c += (INTVAL (y) - INTVAL (x));
1958           return (xsize <= 0 || ysize <= 0
1959                   || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
1960         }
1961
1962       if (GET_CODE (x) == CONST)
1963         {
1964           if (GET_CODE (y) == CONST)
1965             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1966                                        ysize, canon_rtx (XEXP (y, 0)), c);
1967           else
1968             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
1969                                        ysize, y, c);
1970         }
1971       if (GET_CODE (y) == CONST)
1972         return memrefs_conflict_p (xsize, x, ysize,
1973                                    canon_rtx (XEXP (y, 0)), c);
1974
1975       if (CONSTANT_P (y))
1976         return (xsize <= 0 || ysize <= 0
1977                 || (rtx_equal_for_memref_p (x, y)
1978                     && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
1979
1980       return -1;
1981     }
1982
1983   return -1;
1984 }
1985
1986 /* Functions to compute memory dependencies.
1987
1988    Since we process the insns in execution order, we can build tables
1989    to keep track of what registers are fixed (and not aliased), what registers
1990    are varying in known ways, and what registers are varying in unknown
1991    ways.
1992
1993    If both memory references are volatile, then there must always be a
1994    dependence between the two references, since their order can not be
1995    changed.  A volatile and non-volatile reference can be interchanged
1996    though.
1997
1998    A MEM_IN_STRUCT reference at a non-AND varying address can never
1999    conflict with a non-MEM_IN_STRUCT reference at a fixed address.  We
2000    also must allow AND addresses, because they may generate accesses
2001    outside the object being referenced.  This is used to generate
2002    aligned addresses from unaligned addresses, for instance, the alpha
2003    storeqi_unaligned pattern.  */
2004
2005 /* Read dependence: X is read after read in MEM takes place.  There can
2006    only be a dependence here if both reads are volatile.  */
2007
2008 int
2009 read_dependence (const_rtx mem, const_rtx x)
2010 {
2011   return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
2012 }
2013
2014 /* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and
2015    MEM2 is a reference to a structure at a varying address, or returns
2016    MEM2 if vice versa.  Otherwise, returns NULL_RTX.  If a non-NULL
2017    value is returned MEM1 and MEM2 can never alias.  VARIES_P is used
2018    to decide whether or not an address may vary; it should return
2019    nonzero whenever variation is possible.
2020    MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2.  */
2021
2022 static const_rtx
2023 fixed_scalar_and_varying_struct_p (const_rtx mem1, const_rtx mem2, rtx mem1_addr,
2024                                    rtx mem2_addr,
2025                                    bool (*varies_p) (const_rtx, bool))
2026 {
2027   if (! flag_strict_aliasing)
2028     return NULL_RTX;
2029
2030   if (MEM_ALIAS_SET (mem2)
2031       && MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
2032       && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1))
2033     /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
2034        varying address.  */
2035     return mem1;
2036
2037   if (MEM_ALIAS_SET (mem1)
2038       && MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2)
2039       && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1))
2040     /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a
2041        varying address.  */
2042     return mem2;
2043
2044   return NULL_RTX;
2045 }
2046
2047 /* Returns nonzero if something about the mode or address format MEM1
2048    indicates that it might well alias *anything*.  */
2049
2050 static int
2051 aliases_everything_p (const_rtx mem)
2052 {
2053   if (GET_CODE (XEXP (mem, 0)) == AND)
2054     /* If the address is an AND, it's very hard to know at what it is
2055        actually pointing.  */
2056     return 1;
2057
2058   return 0;
2059 }
2060
2061 /* Return true if we can determine that the fields referenced cannot
2062    overlap for any pair of objects.  */
2063
2064 static bool
2065 nonoverlapping_component_refs_p (const_tree x, const_tree y)
2066 {
2067   const_tree fieldx, fieldy, typex, typey, orig_y;
2068
2069   if (!flag_strict_aliasing)
2070     return false;
2071
2072   do
2073     {
2074       /* The comparison has to be done at a common type, since we don't
2075          know how the inheritance hierarchy works.  */
2076       orig_y = y;
2077       do
2078         {
2079           fieldx = TREE_OPERAND (x, 1);
2080           typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
2081
2082           y = orig_y;
2083           do
2084             {
2085               fieldy = TREE_OPERAND (y, 1);
2086               typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
2087
2088               if (typex == typey)
2089                 goto found;
2090
2091               y = TREE_OPERAND (y, 0);
2092             }
2093           while (y && TREE_CODE (y) == COMPONENT_REF);
2094
2095           x = TREE_OPERAND (x, 0);
2096         }
2097       while (x && TREE_CODE (x) == COMPONENT_REF);
2098       /* Never found a common type.  */
2099       return false;
2100
2101     found:
2102       /* If we're left with accessing different fields of a structure,
2103          then no overlap.  */
2104       if (TREE_CODE (typex) == RECORD_TYPE
2105           && fieldx != fieldy)
2106         return true;
2107
2108       /* The comparison on the current field failed.  If we're accessing
2109          a very nested structure, look at the next outer level.  */
2110       x = TREE_OPERAND (x, 0);
2111       y = TREE_OPERAND (y, 0);
2112     }
2113   while (x && y
2114          && TREE_CODE (x) == COMPONENT_REF
2115          && TREE_CODE (y) == COMPONENT_REF);
2116
2117   return false;
2118 }
2119
2120 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it.  */
2121
2122 static tree
2123 decl_for_component_ref (tree x)
2124 {
2125   do
2126     {
2127       x = TREE_OPERAND (x, 0);
2128     }
2129   while (x && TREE_CODE (x) == COMPONENT_REF);
2130
2131   return x && DECL_P (x) ? x : NULL_TREE;
2132 }
2133
2134 /* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the
2135    offset of the field reference.  */
2136
2137 static rtx
2138 adjust_offset_for_component_ref (tree x, rtx offset)
2139 {
2140   HOST_WIDE_INT ioffset;
2141
2142   if (! offset)
2143     return NULL_RTX;
2144
2145   ioffset = INTVAL (offset);
2146   do
2147     {
2148       tree offset = component_ref_field_offset (x);
2149       tree field = TREE_OPERAND (x, 1);
2150
2151       if (! host_integerp (offset, 1))
2152         return NULL_RTX;
2153       ioffset += (tree_low_cst (offset, 1)
2154                   + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2155                      / BITS_PER_UNIT));
2156
2157       x = TREE_OPERAND (x, 0);
2158     }
2159   while (x && TREE_CODE (x) == COMPONENT_REF);
2160
2161   return GEN_INT (ioffset);
2162 }
2163
2164 /* Return nonzero if we can determine the exprs corresponding to memrefs
2165    X and Y and they do not overlap.  */
2166
2167 int
2168 nonoverlapping_memrefs_p (const_rtx x, const_rtx y)
2169 {
2170   tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2171   rtx rtlx, rtly;
2172   rtx basex, basey;
2173   rtx moffsetx, moffsety;
2174   HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem;
2175
2176   /* Unless both have exprs, we can't tell anything.  */
2177   if (exprx == 0 || expry == 0)
2178     return 0;
2179
2180   /* For spill-slot accesses make sure we have valid offsets.  */
2181   if ((exprx == get_spill_slot_decl (false)
2182        && ! MEM_OFFSET (x))
2183       || (expry == get_spill_slot_decl (false)
2184           && ! MEM_OFFSET (y)))
2185     return 0;
2186
2187   /* If both are field references, we may be able to determine something.  */
2188   if (TREE_CODE (exprx) == COMPONENT_REF
2189       && TREE_CODE (expry) == COMPONENT_REF
2190       && nonoverlapping_component_refs_p (exprx, expry))
2191     return 1;
2192
2193
2194   /* If the field reference test failed, look at the DECLs involved.  */
2195   moffsetx = MEM_OFFSET (x);
2196   if (TREE_CODE (exprx) == COMPONENT_REF)
2197     {
2198       if (TREE_CODE (expry) == VAR_DECL
2199           && POINTER_TYPE_P (TREE_TYPE (expry)))
2200         {
2201          tree field = TREE_OPERAND (exprx, 1);
2202          tree fieldcontext = DECL_FIELD_CONTEXT (field);
2203          if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
2204                                                        TREE_TYPE (field)))
2205            return 1;
2206         }
2207       {
2208         tree t = decl_for_component_ref (exprx);
2209         if (! t)
2210           return 0;
2211         moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
2212         exprx = t;
2213       }
2214     }
2215
2216   moffsety = MEM_OFFSET (y);
2217   if (TREE_CODE (expry) == COMPONENT_REF)
2218     {
2219       if (TREE_CODE (exprx) == VAR_DECL
2220           && POINTER_TYPE_P (TREE_TYPE (exprx)))
2221         {
2222          tree field = TREE_OPERAND (expry, 1);
2223          tree fieldcontext = DECL_FIELD_CONTEXT (field);
2224          if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
2225                                                        TREE_TYPE (field)))
2226            return 1;
2227         }
2228       {
2229         tree t = decl_for_component_ref (expry);
2230         if (! t)
2231           return 0;
2232         moffsety = adjust_offset_for_component_ref (expry, moffsety);
2233         expry = t;
2234       }
2235     }
2236
2237   if (! DECL_P (exprx) || ! DECL_P (expry))
2238     return 0;
2239
2240   /* With invalid code we can end up storing into the constant pool.
2241      Bail out to avoid ICEing when creating RTL for this.
2242      See gfortran.dg/lto/20091028-2_0.f90.  */
2243   if (TREE_CODE (exprx) == CONST_DECL
2244       || TREE_CODE (expry) == CONST_DECL)
2245     return 1;
2246
2247   rtlx = DECL_RTL (exprx);
2248   rtly = DECL_RTL (expry);
2249
2250   /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2251      can't overlap unless they are the same because we never reuse that part
2252      of the stack frame used for locals for spilled pseudos.  */
2253   if ((!MEM_P (rtlx) || !MEM_P (rtly))
2254       && ! rtx_equal_p (rtlx, rtly))
2255     return 1;
2256
2257   /* If we have MEMs refering to different address spaces (which can
2258      potentially overlap), we cannot easily tell from the addresses
2259      whether the references overlap.  */
2260   if (MEM_P (rtlx) && MEM_P (rtly)
2261       && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2262     return 0;
2263
2264   /* Get the base and offsets of both decls.  If either is a register, we
2265      know both are and are the same, so use that as the base.  The only
2266      we can avoid overlap is if we can deduce that they are nonoverlapping
2267      pieces of that decl, which is very rare.  */
2268   basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2269   if (GET_CODE (basex) == PLUS && CONST_INT_P (XEXP (basex, 1)))
2270     offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0);
2271
2272   basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2273   if (GET_CODE (basey) == PLUS && CONST_INT_P (XEXP (basey, 1)))
2274     offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0);
2275
2276   /* If the bases are different, we know they do not overlap if both
2277      are constants or if one is a constant and the other a pointer into the
2278      stack frame.  Otherwise a different base means we can't tell if they
2279      overlap or not.  */
2280   if (! rtx_equal_p (basex, basey))
2281     return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2282             || (CONSTANT_P (basex) && REG_P (basey)
2283                 && REGNO_PTR_FRAME_P (REGNO (basey)))
2284             || (CONSTANT_P (basey) && REG_P (basex)
2285                 && REGNO_PTR_FRAME_P (REGNO (basex))));
2286
2287   sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
2288            : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx))
2289            : -1);
2290   sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly))
2291            : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) :
2292            -1);
2293
2294   /* If we have an offset for either memref, it can update the values computed
2295      above.  */
2296   if (moffsetx)
2297     offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx);
2298   if (moffsety)
2299     offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety);
2300
2301   /* If a memref has both a size and an offset, we can use the smaller size.
2302      We can't do this if the offset isn't known because we must view this
2303      memref as being anywhere inside the DECL's MEM.  */
2304   if (MEM_SIZE (x) && moffsetx)
2305     sizex = INTVAL (MEM_SIZE (x));
2306   if (MEM_SIZE (y) && moffsety)
2307     sizey = INTVAL (MEM_SIZE (y));
2308
2309   /* Put the values of the memref with the lower offset in X's values.  */
2310   if (offsetx > offsety)
2311     {
2312       tem = offsetx, offsetx = offsety, offsety = tem;
2313       tem = sizex, sizex = sizey, sizey = tem;
2314     }
2315
2316   /* If we don't know the size of the lower-offset value, we can't tell
2317      if they conflict.  Otherwise, we do the test.  */
2318   return sizex >= 0 && offsety >= offsetx + sizex;
2319 }
2320
2321 /* True dependence: X is read after store in MEM takes place.  */
2322
2323 int
2324 true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x,
2325                  bool (*varies) (const_rtx, bool))
2326 {
2327   rtx x_addr, mem_addr;
2328   rtx base;
2329   int ret;
2330
2331   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2332     return 1;
2333
2334   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2335      This is used in epilogue deallocation functions, and in cselib.  */
2336   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2337     return 1;
2338   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2339     return 1;
2340   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2341       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2342     return 1;
2343
2344   /* Read-only memory is by definition never modified, and therefore can't
2345      conflict with anything.  We don't expect to find read-only set on MEM,
2346      but stupid user tricks can produce them, so don't die.  */
2347   if (MEM_READONLY_P (x))
2348     return 0;
2349
2350   /* If we have MEMs refering to different address spaces (which can
2351      potentially overlap), we cannot easily tell from the addresses
2352      whether the references overlap.  */
2353   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2354     return 1;
2355
2356   if (mem_mode == VOIDmode)
2357     mem_mode = GET_MODE (mem);
2358
2359   x_addr = get_addr (XEXP (x, 0));
2360   mem_addr = get_addr (XEXP (mem, 0));
2361
2362   base = find_base_term (x_addr);
2363   if (base && (GET_CODE (base) == LABEL_REF
2364                || (GET_CODE (base) == SYMBOL_REF
2365                    && CONSTANT_POOL_ADDRESS_P (base))))
2366     return 0;
2367
2368   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2369     return 0;
2370
2371   x_addr = canon_rtx (x_addr);
2372   mem_addr = canon_rtx (mem_addr);
2373
2374   if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2375                                  SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2376     return ret;
2377
2378   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2379     return 0;
2380
2381   if (nonoverlapping_memrefs_p (mem, x))
2382     return 0;
2383
2384   if (aliases_everything_p (x))
2385     return 1;
2386
2387   /* We cannot use aliases_everything_p to test MEM, since we must look
2388      at MEM_MODE, rather than GET_MODE (MEM).  */
2389   if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2390     return 1;
2391
2392   /* In true_dependence we also allow BLKmode to alias anything.  Why
2393      don't we do this in anti_dependence and output_dependence?  */
2394   if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2395     return 1;
2396
2397   if (fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, varies))
2398     return 0;
2399
2400   return rtx_refs_may_alias_p (x, mem, true);
2401 }
2402
2403 /* Canonical true dependence: X is read after store in MEM takes place.
2404    Variant of true_dependence which assumes MEM has already been
2405    canonicalized (hence we no longer do that here).
2406    The mem_addr argument has been added, since true_dependence computed
2407    this value prior to canonicalizing.
2408    If x_addr is non-NULL, it is used in preference of XEXP (x, 0).  */
2409
2410 int
2411 canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
2412                        const_rtx x, rtx x_addr, bool (*varies) (const_rtx, bool))
2413 {
2414   int ret;
2415
2416   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2417     return 1;
2418
2419   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2420      This is used in epilogue deallocation functions.  */
2421   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2422     return 1;
2423   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2424     return 1;
2425   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2426       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2427     return 1;
2428
2429   /* Read-only memory is by definition never modified, and therefore can't
2430      conflict with anything.  We don't expect to find read-only set on MEM,
2431      but stupid user tricks can produce them, so don't die.  */
2432   if (MEM_READONLY_P (x))
2433     return 0;
2434
2435   /* If we have MEMs refering to different address spaces (which can
2436      potentially overlap), we cannot easily tell from the addresses
2437      whether the references overlap.  */
2438   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2439     return 1;
2440
2441   if (! x_addr)
2442     x_addr = get_addr (XEXP (x, 0));
2443
2444   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
2445     return 0;
2446
2447   x_addr = canon_rtx (x_addr);
2448   if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
2449                                  SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2450     return ret;
2451
2452   if (DIFFERENT_ALIAS_SETS_P (x, mem))
2453     return 0;
2454
2455   if (nonoverlapping_memrefs_p (x, mem))
2456     return 0;
2457
2458   if (aliases_everything_p (x))
2459     return 1;
2460
2461   /* We cannot use aliases_everything_p to test MEM, since we must look
2462      at MEM_MODE, rather than GET_MODE (MEM).  */
2463   if (mem_mode == QImode || GET_CODE (mem_addr) == AND)
2464     return 1;
2465
2466   /* In true_dependence we also allow BLKmode to alias anything.  Why
2467      don't we do this in anti_dependence and output_dependence?  */
2468   if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
2469     return 1;
2470
2471   if (fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, varies))
2472     return 0;
2473
2474   return rtx_refs_may_alias_p (x, mem, true);
2475 }
2476
2477 /* Returns nonzero if a write to X might alias a previous read from
2478    (or, if WRITEP is nonzero, a write to) MEM.  */
2479
2480 static int
2481 write_dependence_p (const_rtx mem, const_rtx x, int writep)
2482 {
2483   rtx x_addr, mem_addr;
2484   const_rtx fixed_scalar;
2485   rtx base;
2486   int ret;
2487
2488   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2489     return 1;
2490
2491   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2492      This is used in epilogue deallocation functions.  */
2493   if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2494     return 1;
2495   if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2496     return 1;
2497   if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2498       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2499     return 1;
2500
2501   /* A read from read-only memory can't conflict with read-write memory.  */
2502   if (!writep && MEM_READONLY_P (mem))
2503     return 0;
2504
2505   /* If we have MEMs refering to different address spaces (which can
2506      potentially overlap), we cannot easily tell from the addresses
2507      whether the references overlap.  */
2508   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2509     return 1;
2510
2511   x_addr = get_addr (XEXP (x, 0));
2512   mem_addr = get_addr (XEXP (mem, 0));
2513
2514   if (! writep)
2515     {
2516       base = find_base_term (mem_addr);
2517       if (base && (GET_CODE (base) == LABEL_REF
2518                    || (GET_CODE (base) == SYMBOL_REF
2519                        && CONSTANT_POOL_ADDRESS_P (base))))
2520         return 0;
2521     }
2522
2523   if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
2524                           GET_MODE (mem)))
2525     return 0;
2526
2527   x_addr = canon_rtx (x_addr);
2528   mem_addr = canon_rtx (mem_addr);
2529
2530   if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
2531                                  SIZE_FOR_MODE (x), x_addr, 0)) != -1)
2532     return ret;
2533
2534   if (nonoverlapping_memrefs_p (x, mem))
2535     return 0;
2536
2537   fixed_scalar
2538     = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
2539                                          rtx_addr_varies_p);
2540
2541   if ((fixed_scalar == mem && !aliases_everything_p (x))
2542       || (fixed_scalar == x && !aliases_everything_p (mem)))
2543     return 0;
2544
2545   return rtx_refs_may_alias_p (x, mem, false);
2546 }
2547
2548 /* Anti dependence: X is written after read in MEM takes place.  */
2549
2550 int
2551 anti_dependence (const_rtx mem, const_rtx x)
2552 {
2553   return write_dependence_p (mem, x, /*writep=*/0);
2554 }
2555
2556 /* Output dependence: X is written after store in MEM takes place.  */
2557
2558 int
2559 output_dependence (const_rtx mem, const_rtx x)
2560 {
2561   return write_dependence_p (mem, x, /*writep=*/1);
2562 }
2563 \f
2564
2565 void
2566 init_alias_target (void)
2567 {
2568   int i;
2569
2570   memset (static_reg_base_value, 0, sizeof static_reg_base_value);
2571
2572   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2573     /* Check whether this register can hold an incoming pointer
2574        argument.  FUNCTION_ARG_REGNO_P tests outgoing register
2575        numbers, so translate if necessary due to register windows.  */
2576     if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
2577         && HARD_REGNO_MODE_OK (i, Pmode))
2578       static_reg_base_value[i]
2579         = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i));
2580
2581   static_reg_base_value[STACK_POINTER_REGNUM]
2582     = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
2583   static_reg_base_value[ARG_POINTER_REGNUM]
2584     = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
2585   static_reg_base_value[FRAME_POINTER_REGNUM]
2586     = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
2587 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2588   static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
2589     = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
2590 #endif
2591 }
2592
2593 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2594    to be memory reference.  */
2595 static bool memory_modified;
2596 static void
2597 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
2598 {
2599   if (MEM_P (x))
2600     {
2601       if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
2602         memory_modified = true;
2603     }
2604 }
2605
2606
2607 /* Return true when INSN possibly modify memory contents of MEM
2608    (i.e. address can be modified).  */
2609 bool
2610 memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
2611 {
2612   if (!INSN_P (insn))
2613     return false;
2614   memory_modified = false;
2615   note_stores (PATTERN (insn), memory_modified_1, CONST_CAST_RTX(mem));
2616   return memory_modified;
2617 }
2618
2619 /* Initialize the aliasing machinery.  Initialize the REG_KNOWN_VALUE
2620    array.  */
2621
2622 void
2623 init_alias_analysis (void)
2624 {
2625   unsigned int maxreg = max_reg_num ();
2626   int changed, pass;
2627   int i;
2628   unsigned int ui;
2629   rtx insn;
2630
2631   timevar_push (TV_ALIAS_ANALYSIS);
2632
2633   reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER;
2634   reg_known_value = GGC_CNEWVEC (rtx, reg_known_value_size);
2635   reg_known_equiv_p = XCNEWVEC (bool, reg_known_value_size);
2636
2637   /* If we have memory allocated from the previous run, use it.  */
2638   if (old_reg_base_value)
2639     reg_base_value = old_reg_base_value;
2640
2641   if (reg_base_value)
2642     VEC_truncate (rtx, reg_base_value, 0);
2643
2644   VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
2645
2646   new_reg_base_value = XNEWVEC (rtx, maxreg);
2647   reg_seen = XNEWVEC (char, maxreg);
2648
2649   /* The basic idea is that each pass through this loop will use the
2650      "constant" information from the previous pass to propagate alias
2651      information through another level of assignments.
2652
2653      This could get expensive if the assignment chains are long.  Maybe
2654      we should throttle the number of iterations, possibly based on
2655      the optimization level or flag_expensive_optimizations.
2656
2657      We could propagate more information in the first pass by making use
2658      of DF_REG_DEF_COUNT to determine immediately that the alias information
2659      for a pseudo is "constant".
2660
2661      A program with an uninitialized variable can cause an infinite loop
2662      here.  Instead of doing a full dataflow analysis to detect such problems
2663      we just cap the number of iterations for the loop.
2664
2665      The state of the arrays for the set chain in question does not matter
2666      since the program has undefined behavior.  */
2667
2668   pass = 0;
2669   do
2670     {
2671       /* Assume nothing will change this iteration of the loop.  */
2672       changed = 0;
2673
2674       /* We want to assign the same IDs each iteration of this loop, so
2675          start counting from zero each iteration of the loop.  */
2676       unique_id = 0;
2677
2678       /* We're at the start of the function each iteration through the
2679          loop, so we're copying arguments.  */
2680       copying_arguments = true;
2681
2682       /* Wipe the potential alias information clean for this pass.  */
2683       memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
2684
2685       /* Wipe the reg_seen array clean.  */
2686       memset (reg_seen, 0, maxreg);
2687
2688       /* Mark all hard registers which may contain an address.
2689          The stack, frame and argument pointers may contain an address.
2690          An argument register which can hold a Pmode value may contain
2691          an address even if it is not in BASE_REGS.
2692
2693          The address expression is VOIDmode for an argument and
2694          Pmode for other registers.  */
2695
2696       memcpy (new_reg_base_value, static_reg_base_value,
2697               FIRST_PSEUDO_REGISTER * sizeof (rtx));
2698
2699       /* Walk the insns adding values to the new_reg_base_value array.  */
2700       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2701         {
2702           if (INSN_P (insn))
2703             {
2704               rtx note, set;
2705
2706 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2707               /* The prologue/epilogue insns are not threaded onto the
2708                  insn chain until after reload has completed.  Thus,
2709                  there is no sense wasting time checking if INSN is in
2710                  the prologue/epilogue until after reload has completed.  */
2711               if (reload_completed
2712                   && prologue_epilogue_contains (insn))
2713                 continue;
2714 #endif
2715
2716               /* If this insn has a noalias note, process it,  Otherwise,
2717                  scan for sets.  A simple set will have no side effects
2718                  which could change the base value of any other register.  */
2719
2720               if (GET_CODE (PATTERN (insn)) == SET
2721                   && REG_NOTES (insn) != 0
2722                   && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
2723                 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
2724               else
2725                 note_stores (PATTERN (insn), record_set, NULL);
2726
2727               set = single_set (insn);
2728
2729               if (set != 0
2730                   && REG_P (SET_DEST (set))
2731                   && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
2732                 {
2733                   unsigned int regno = REGNO (SET_DEST (set));
2734                   rtx src = SET_SRC (set);
2735                   rtx t;
2736
2737                   note = find_reg_equal_equiv_note (insn);
2738                   if (note && REG_NOTE_KIND (note) == REG_EQUAL
2739                       && DF_REG_DEF_COUNT (regno) != 1)
2740                     note = NULL_RTX;
2741
2742                   if (note != NULL_RTX
2743                       && GET_CODE (XEXP (note, 0)) != EXPR_LIST
2744                       && ! rtx_varies_p (XEXP (note, 0), 1)
2745                       && ! reg_overlap_mentioned_p (SET_DEST (set),
2746                                                     XEXP (note, 0)))
2747                     {
2748                       set_reg_known_value (regno, XEXP (note, 0));
2749                       set_reg_known_equiv_p (regno,
2750                         REG_NOTE_KIND (note) == REG_EQUIV);
2751                     }
2752                   else if (DF_REG_DEF_COUNT (regno) == 1
2753                            && GET_CODE (src) == PLUS
2754                            && REG_P (XEXP (src, 0))
2755                            && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
2756                            && CONST_INT_P (XEXP (src, 1)))
2757                     {
2758                       t = plus_constant (t, INTVAL (XEXP (src, 1)));
2759                       set_reg_known_value (regno, t);
2760                       set_reg_known_equiv_p (regno, 0);
2761                     }
2762                   else if (DF_REG_DEF_COUNT (regno) == 1
2763                            && ! rtx_varies_p (src, 1))
2764                     {
2765                       set_reg_known_value (regno, src);
2766                       set_reg_known_equiv_p (regno, 0);
2767                     }
2768                 }
2769             }
2770           else if (NOTE_P (insn)
2771                    && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
2772             copying_arguments = false;
2773         }
2774
2775       /* Now propagate values from new_reg_base_value to reg_base_value.  */
2776       gcc_assert (maxreg == (unsigned int) max_reg_num ());
2777
2778       for (ui = 0; ui < maxreg; ui++)
2779         {
2780           if (new_reg_base_value[ui]
2781               && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
2782               && ! rtx_equal_p (new_reg_base_value[ui],
2783                                 VEC_index (rtx, reg_base_value, ui)))
2784             {
2785               VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
2786               changed = 1;
2787             }
2788         }
2789     }
2790   while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
2791
2792   /* Fill in the remaining entries.  */
2793   for (i = 0; i < (int)reg_known_value_size; i++)
2794     if (reg_known_value[i] == 0)
2795       reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER];
2796
2797   /* Clean up.  */
2798   free (new_reg_base_value);
2799   new_reg_base_value = 0;
2800   free (reg_seen);
2801   reg_seen = 0;
2802   timevar_pop (TV_ALIAS_ANALYSIS);
2803 }
2804
2805 void
2806 end_alias_analysis (void)
2807 {
2808   old_reg_base_value = reg_base_value;
2809   ggc_free (reg_known_value);
2810   reg_known_value = 0;
2811   reg_known_value_size = 0;
2812   free (reg_known_equiv_p);
2813   reg_known_equiv_p = 0;
2814 }
2815
2816 #include "gt-alias.h"