gcc/alias.c

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