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