gcc/alias.c

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