OSDN Git Service

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