gcc/alias.c

   1 /* Alias analysis for GNU C
   2    Copyright (C) 1997, 1998 Free Software Foundation, Inc.
   3    Contributed by John Carr (jfc@mit.edu).
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "rtl.h"
  25 #include "expr.h"
  26 #include "regs.h"
  27 #include "hard-reg-set.h"
  28 #include "flags.h"
  29
  30 static rtx canon_rtx                    PROTO((rtx));
  31 static int rtx_equal_for_memref_p       PROTO((rtx, rtx));
  32 static rtx find_symbolic_term           PROTO((rtx));
  33 static int memrefs_conflict_p           PROTO((int, rtx, int, rtx,
  34                                                HOST_WIDE_INT));
  35
  36 /* Set up all info needed to perform alias analysis on memory references.  */
  37
  38 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
  39
  40 /* Cap the number of passes we make over the insns propagating alias
  41    information through set chains.
  42
  43    10 is a completely arbitrary choice.  */
  44 #define MAX_ALIAS_LOOP_PASSES 10
  45
  46 /* reg_base_value[N] gives an address to which register N is related.
  47    If all sets after the first add or subtract to the current value
  48    or otherwise modify it so it does not point to a different top level
  49    object, reg_base_value[N] is equal to the address part of the source
  50    of the first set.
  51
  52    A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF.  ADDRESS
  53    expressions represent certain special values: function arguments and
  54    the stack, frame, and argument pointers.  The contents of an address
  55    expression are not used (but they are descriptive for debugging);
  56    only the address and mode matter.  Pointer equality, not rtx_equal_p,
  57    determines whether two ADDRESS expressions refer to the same base
  58    address.  The mode determines whether it is a function argument or
  59    other special value. */
  60
  61 rtx *reg_base_value;
  62 rtx *new_reg_base_value;
  63 unsigned int reg_base_value_size;       /* size of reg_base_value array */
  64 #define REG_BASE_VALUE(X) \
  65         (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
  66
  67 /* Vector indexed by N giving the initial (unchanging) value known
  68    for pseudo-register N.  */
  69 rtx *reg_known_value;
  70
  71 /* Indicates number of valid entries in reg_known_value.  */
  72 static int reg_known_value_size;
  73
  74 /* Vector recording for each reg_known_value whether it is due to a
  75    REG_EQUIV note.  Future passes (viz., reload) may replace the
  76    pseudo with the equivalent expression and so we account for the
  77    dependences that would be introduced if that happens. */
  78 /* ??? This is a problem only on the Convex.  The REG_EQUIV notes created in
  79    assign_parms mention the arg pointer, and there are explicit insns in the
  80    RTL that modify the arg pointer.  Thus we must ensure that such insns don't
  81    get scheduled across each other because that would invalidate the REG_EQUIV
  82    notes.  One could argue that the REG_EQUIV notes are wrong, but solving
  83    the problem in the scheduler will likely give better code, so we do it
  84    here.  */
  85 char *reg_known_equiv_p;
  86
  87 /* True when scanning insns from the start of the rtl to the
  88    NOTE_INSN_FUNCTION_BEG note.  */
  89
  90 static int copying_arguments;
  91
  92 /* Inside SRC, the source of a SET, find a base address.  */
  93
  94 static rtx
  95 find_base_value (src)
  96      register rtx src;
  97 {
  98   switch (GET_CODE (src))
  99     {
 100     case SYMBOL_REF:
 101     case LABEL_REF:
 102       return src;
 103
 104     case REG:
 105       /* At the start of a function argument registers have known base
 106          values which may be lost later.  Returning an ADDRESS
 107          expression here allows optimization based on argument values
 108          even when the argument registers are used for other purposes.  */
 109       if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
 110         return new_reg_base_value[REGNO (src)];
 111
 112       /* If a pseudo has a known base value, return it.  Do not do this
 113          for hard regs since it can result in a circular dependency
 114          chain for registers which have values at function entry.
 115
 116          The test above is not sufficient because the scheduler may move
 117          a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN.  */
 118       if (REGNO (src) >= FIRST_PSEUDO_REGISTER
 119           && reg_base_value[REGNO (src)])
 120         return reg_base_value[REGNO (src)];
 121
 122       return src;
 123
 124     case MEM:
 125       /* Check for an argument passed in memory.  Only record in the
 126          copying-arguments block; it is too hard to track changes
 127          otherwise.  */
 128       if (copying_arguments
 129           && (XEXP (src, 0) == arg_pointer_rtx
 130               || (GET_CODE (XEXP (src, 0)) == PLUS
 131                   && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
 132         return gen_rtx_ADDRESS (VOIDmode, src);
 133       return 0;
 134
 135     case CONST:
 136       src = XEXP (src, 0);
 137       if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
 138         break;
 139       /* fall through */
 140
 141     case PLUS:
 142     case MINUS:
 143       {
 144         rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
 145
 146         /* If either operand is a REG, then see if we already have
 147            a known value for it.  */
 148         if (GET_CODE (src_0) == REG)
 149           {
 150             temp = find_base_value (src_0);
 151             if (temp)
 152               src_0 = temp;
 153           }
 154
 155         if (GET_CODE (src_1) == REG)
 156           {
 157             temp = find_base_value (src_1);
 158             if (temp)
 159               src_1 = temp;
 160           }
 161
 162         /* Guess which operand is the base address.
 163
 164            If either operand is a symbol, then it is the base.  If
 165            either operand is a CONST_INT, then the other is the base.  */
 166
 167         if (GET_CODE (src_1) == CONST_INT
 168             || GET_CODE (src_0) == SYMBOL_REF
 169             || GET_CODE (src_0) == LABEL_REF
 170             || GET_CODE (src_0) == CONST)
 171           return find_base_value (src_0);
 172
 173         if (GET_CODE (src_0) == CONST_INT
 174             || GET_CODE (src_1) == SYMBOL_REF
 175             || GET_CODE (src_1) == LABEL_REF
 176             || GET_CODE (src_1) == CONST)
 177           return find_base_value (src_1);
 178
 179         /* This might not be necessary anymore.
 180
 181            If either operand is a REG that is a known pointer, then it
 182            is the base.  */
 183         if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
 184           return find_base_value (src_0);
 185
 186         if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1)))
 187           return find_base_value (src_1);
 188
 189         return 0;
 190       }
 191
 192     case LO_SUM:
 193       /* The standard form is (lo_sum reg sym) so look only at the
 194          second operand.  */
 195       return find_base_value (XEXP (src, 1));
 196
 197     case AND:
 198       /* If the second operand is constant set the base
 199          address to the first operand. */
 200       if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0)
 201         return find_base_value (XEXP (src, 0));
 202       return 0;
 203
 204     case HIGH:
 205       return find_base_value (XEXP (src, 0));
 206
 207     default:
 208       break;
 209     }
 210
 211   return 0;
 212 }
 213
 214 /* Called from init_alias_analysis indirectly through note_stores.  */
 215
 216 /* while scanning insns to find base values, reg_seen[N] is nonzero if
 217    register N has been set in this function.  */
 218 static char *reg_seen;
 219
 220 /* Addresses which are known not to alias anything else are identified
 221    by a unique integer.  */
 222 static int unique_id;
 223
 224 static void
 225 record_set (dest, set)
 226      rtx dest, set;
 227 {
 228   register int regno;
 229   rtx src;
 230
 231   if (GET_CODE (dest) != REG)
 232     return;
 233
 234   regno = REGNO (dest);
 235
 236   if (set)
 237     {
 238       /* A CLOBBER wipes out any old value but does not prevent a previously
 239          unset register from acquiring a base address (i.e. reg_seen is not
 240          set).  */
 241       if (GET_CODE (set) == CLOBBER)
 242         {
 243           new_reg_base_value[regno] = 0;
 244           return;
 245         }
 246       src = SET_SRC (set);
 247     }
 248   else
 249     {
 250       if (reg_seen[regno])
 251         {
 252           new_reg_base_value[regno] = 0;
 253           return;
 254         }
 255       reg_seen[regno] = 1;
 256       new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode,
 257                                                    GEN_INT (unique_id++));
 258       return;
 259     }
 260
 261   /* This is not the first set.  If the new value is not related to the
 262      old value, forget the base value. Note that the following code is
 263      not detected:
 264      extern int x, y;  int *p = &x; p += (&y-&x);
 265      ANSI C does not allow computing the difference of addresses
 266      of distinct top level objects.  */
 267   if (new_reg_base_value[regno])
 268     switch (GET_CODE (src))
 269       {
 270       case LO_SUM:
 271       case PLUS:
 272       case MINUS:
 273         if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
 274           new_reg_base_value[regno] = 0;
 275         break;
 276       case AND:
 277         if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
 278           new_reg_base_value[regno] = 0;
 279         break;
 280       default:
 281         new_reg_base_value[regno] = 0;
 282         break;
 283       }
 284   /* If this is the first set of a register, record the value.  */
 285   else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
 286            && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
 287     new_reg_base_value[regno] = find_base_value (src);
 288
 289   reg_seen[regno] = 1;
 290 }
 291
 292 /* Called from loop optimization when a new pseudo-register is created.  */
 293 void
 294 record_base_value (regno, val)
 295      int regno;
 296      rtx val;
 297 {
 298   if (regno >= reg_base_value_size)
 299     return;
 300   if (GET_CODE (val) == REG)
 301     {
 302       if (REGNO (val) < reg_base_value_size)
 303         reg_base_value[regno] = reg_base_value[REGNO (val)];
 304       return;
 305     }
 306   reg_base_value[regno] = find_base_value (val);
 307 }
 308
 309 static rtx
 310 canon_rtx (x)
 311      rtx x;
 312 {
 313   /* Recursively look for equivalences.  */
 314   if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
 315       && REGNO (x) < reg_known_value_size)
 316     return reg_known_value[REGNO (x)] == x
 317       ? x : canon_rtx (reg_known_value[REGNO (x)]);
 318   else if (GET_CODE (x) == PLUS)
 319     {
 320       rtx x0 = canon_rtx (XEXP (x, 0));
 321       rtx x1 = canon_rtx (XEXP (x, 1));
 322
 323       if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
 324         {
 325           /* We can tolerate LO_SUMs being offset here; these
 326              rtl are used for nothing other than comparisons.  */
 327           if (GET_CODE (x0) == CONST_INT)
 328             return plus_constant_for_output (x1, INTVAL (x0));
 329           else if (GET_CODE (x1) == CONST_INT)
 330             return plus_constant_for_output (x0, INTVAL (x1));
 331           return gen_rtx_PLUS (GET_MODE (x), x0, x1);
 332         }
 333     }
 334   /* This gives us much better alias analysis when called from
 335      the loop optimizer.   Note we want to leave the original
 336      MEM alone, but need to return the canonicalized MEM with
 337      all the flags with their original values.  */
 338   else if (GET_CODE (x) == MEM)
 339     {
 340       rtx addr = canon_rtx (XEXP (x, 0));
 341       if (addr != XEXP (x, 0))
 342         {
 343           rtx new = gen_rtx_MEM (GET_MODE (x), addr);
 344           MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
 345           RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
 346           MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
 347           x = new;
 348         }
 349     }
 350   return x;
 351 }
 352
 353 /* Return 1 if X and Y are identical-looking rtx's.
 354
 355    We use the data in reg_known_value above to see if two registers with
 356    different numbers are, in fact, equivalent.  */
 357
 358 static int
 359 rtx_equal_for_memref_p (x, y)
 360      rtx x, y;
 361 {
 362   register int i;
 363   register int j;
 364   register enum rtx_code code;
 365   register char *fmt;
 366
 367   if (x == 0 && y == 0)
 368     return 1;
 369   if (x == 0 || y == 0)
 370     return 0;
 371   x = canon_rtx (x);
 372   y = canon_rtx (y);
 373
 374   if (x == y)
 375     return 1;
 376
 377   code = GET_CODE (x);
 378   /* Rtx's of different codes cannot be equal.  */
 379   if (code != GET_CODE (y))
 380     return 0;
 381
 382   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 383      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 384
 385   if (GET_MODE (x) != GET_MODE (y))
 386     return 0;
 387
 388   /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively.  */
 389
 390   if (code == REG)
 391     return REGNO (x) == REGNO (y);
 392   if (code == LABEL_REF)
 393     return XEXP (x, 0) == XEXP (y, 0);
 394   if (code == SYMBOL_REF)
 395     return XSTR (x, 0) == XSTR (y, 0);
 396
 397   /* For commutative operations, the RTX match if the operand match in any
 398      order.  Also handle the simple binary and unary cases without a loop.  */
 399   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
 400     return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
 401              && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
 402             || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
 403                 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
 404   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
 405     return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
 406             && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
 407   else if (GET_RTX_CLASS (code) == '1')
 408     return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
 409
 410   /* Compare the elements.  If any pair of corresponding elements
 411      fail to match, return 0 for the whole things.  */
 412
 413   fmt = GET_RTX_FORMAT (code);
 414   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 415     {
 416       switch (fmt[i])
 417         {
 418         case 'w':
 419           if (XWINT (x, i) != XWINT (y, i))
 420             return 0;
 421           break;
 422
 423         case 'n':
 424         case 'i':
 425           if (XINT (x, i) != XINT (y, i))
 426             return 0;
 427           break;
 428
 429         case 'V':
 430         case 'E':
 431           /* Two vectors must have the same length.  */
 432           if (XVECLEN (x, i) != XVECLEN (y, i))
 433             return 0;
 434
 435           /* And the corresponding elements must match.  */
 436           for (j = 0; j < XVECLEN (x, i); j++)
 437             if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 438               return 0;
 439           break;
 440
 441         case 'e':
 442           if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
 443             return 0;
 444           break;
 445
 446         case 'S':
 447         case 's':
 448           if (strcmp (XSTR (x, i), XSTR (y, i)))
 449             return 0;
 450           break;
 451
 452         case 'u':
 453           /* These are just backpointers, so they don't matter.  */
 454           break;
 455
 456         case '0':
 457           break;
 458
 459           /* It is believed that rtx's at this level will never
 460              contain anything but integers and other rtx's,
 461              except for within LABEL_REFs and SYMBOL_REFs.  */
 462         default:
 463           abort ();
 464         }
 465     }
 466   return 1;
 467 }
 468
 469 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
 470    X and return it, or return 0 if none found.  */
 471
 472 static rtx
 473 find_symbolic_term (x)
 474      rtx x;
 475 {
 476   register int i;
 477   register enum rtx_code code;
 478   register char *fmt;
 479
 480   code = GET_CODE (x);
 481   if (code == SYMBOL_REF || code == LABEL_REF)
 482     return x;
 483   if (GET_RTX_CLASS (code) == 'o')
 484     return 0;
 485
 486   fmt = GET_RTX_FORMAT (code);
 487   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 488     {
 489       rtx t;
 490
 491       if (fmt[i] == 'e')
 492         {
 493           t = find_symbolic_term (XEXP (x, i));
 494           if (t != 0)
 495             return t;
 496         }
 497       else if (fmt[i] == 'E')
 498         break;
 499     }
 500   return 0;
 501 }
 502
 503 static rtx
 504 find_base_term (x)
 505      register rtx x;
 506 {
 507   switch (GET_CODE (x))
 508     {
 509     case REG:
 510       return REG_BASE_VALUE (x);
 511
 512     case HIGH:
 513       return find_base_term (XEXP (x, 0));
 514
 515     case PRE_INC:
 516     case PRE_DEC:
 517     case POST_INC:
 518     case POST_DEC:
 519       return find_base_term (XEXP (x, 0));
 520
 521     case CONST:
 522       x = XEXP (x, 0);
 523       if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
 524         return 0;
 525       /* fall through */
 526     case LO_SUM:
 527     case PLUS:
 528     case MINUS:
 529       {
 530         rtx tmp = find_base_term (XEXP (x, 0));
 531         if (tmp)
 532           return tmp;
 533         return find_base_term (XEXP (x, 1));
 534       }
 535
 536     case AND:
 537       if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT)
 538         return REG_BASE_VALUE (XEXP (x, 0));
 539       return 0;
 540
 541     case SYMBOL_REF:
 542     case LABEL_REF:
 543       return x;
 544
 545     default:
 546       return 0;
 547     }
 548 }
 549
 550 /* Return 0 if the addresses X and Y are known to point to different
 551    objects, 1 if they might be pointers to the same object.  */
 552
 553 static int
 554 base_alias_check (x, y)
 555      rtx x, y;
 556 {
 557   rtx x_base = find_base_term (x);
 558   rtx y_base = find_base_term (y);
 559
 560   /* If the address itself has no known base see if a known equivalent
 561      value has one.  If either address still has no known base, nothing
 562      is known about aliasing.  */
 563   if (x_base == 0)
 564     {
 565       rtx x_c;
 566       if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
 567         return 1;
 568       x_base = find_base_term (x_c);
 569       if (x_base == 0)
 570         return 1;
 571     }
 572
 573   if (y_base == 0)
 574     {
 575       rtx y_c;
 576       if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
 577         return 1;
 578       y_base = find_base_term (y_c);
 579       if (y_base == 0)
 580         return 1;
 581     }
 582
 583   /* If the base addresses are equal nothing is known about aliasing.  */
 584   if (rtx_equal_p (x_base, y_base))
 585     return 1;
 586
 587   /* The base addresses of the read and write are different
 588      expressions.  If they are both symbols and they are not accessed
 589      via AND, there is no conflict.  */
 590   /* XXX: We can bring knowledge of object alignment and offset into
 591      play here.  For example, on alpha, "char a, b;" can alias one
 592      another, though "char a; long b;" cannot.  Similarly, offsets
 593      into strutures may be brought into play.  Given "char a, b[40];",
 594      a and b[1] may overlap, but a and b[20] do not.  */
 595   if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
 596     {
 597       return GET_CODE (x) == AND || GET_CODE (y) == AND;
 598     }
 599
 600   /* If one address is a stack reference there can be no alias:
 601      stack references using different base registers do not alias,
 602      a stack reference can not alias a parameter, and a stack reference
 603      can not alias a global.  */
 604   if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode)
 605       || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode))
 606     return 0;
 607
 608   if (! flag_argument_noalias)
 609     return 1;
 610
 611   if (flag_argument_noalias > 1)
 612     return 0;
 613
 614   /* Weak noalias assertion (arguments are distinct, but may match globals). */
 615   return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
 616 }
 617
 618 /* Return nonzero if X and Y (memory addresses) could reference the
 619    same location in memory.  C is an offset accumulator.  When
 620    C is nonzero, we are testing aliases between X and Y + C.
 621    XSIZE is the size in bytes of the X reference,
 622    similarly YSIZE is the size in bytes for Y.
 623
 624    If XSIZE or YSIZE is zero, we do not know the amount of memory being
 625    referenced (the reference was BLKmode), so make the most pessimistic
 626    assumptions.
 627
 628    If XSIZE or YSIZE is negative, we may access memory outside the object
 629    being referenced as a side effect.  This can happen when using AND to
 630    align memory references, as is done on the Alpha.
 631
 632    Nice to notice that varying addresses cannot conflict with fp if no
 633    local variables had their addresses taken, but that's too hard now.  */
 634
 635
 636 static int
 637 memrefs_conflict_p (xsize, x, ysize, y, c)
 638      register rtx x, y;
 639      int xsize, ysize;
 640      HOST_WIDE_INT c;
 641 {
 642   if (GET_CODE (x) == HIGH)
 643     x = XEXP (x, 0);
 644   else if (GET_CODE (x) == LO_SUM)
 645     x = XEXP (x, 1);
 646   else
 647     x = canon_rtx (x);
 648   if (GET_CODE (y) == HIGH)
 649     y = XEXP (y, 0);
 650   else if (GET_CODE (y) == LO_SUM)
 651     y = XEXP (y, 1);
 652   else
 653     y = canon_rtx (y);
 654
 655   if (rtx_equal_for_memref_p (x, y))
 656     {
 657       if (xsize <= 0 || ysize <= 0)
 658         return 1;
 659       if (c >= 0 && xsize > c)
 660         return 1;
 661       if (c < 0 && ysize+c > 0)
 662         return 1;
 663       return 0;
 664     }
 665
 666   /* This code used to check for conflicts involving stack references and
 667      globals but the base address alias code now handles these cases.  */
 668
 669   if (GET_CODE (x) == PLUS)
 670     {
 671       /* The fact that X is canonicalized means that this
 672          PLUS rtx is canonicalized.  */
 673       rtx x0 = XEXP (x, 0);
 674       rtx x1 = XEXP (x, 1);
 675
 676       if (GET_CODE (y) == PLUS)
 677         {
 678           /* The fact that Y is canonicalized means that this
 679              PLUS rtx is canonicalized.  */
 680           rtx y0 = XEXP (y, 0);
 681           rtx y1 = XEXP (y, 1);
 682
 683           if (rtx_equal_for_memref_p (x1, y1))
 684             return memrefs_conflict_p (xsize, x0, ysize, y0, c);
 685           if (rtx_equal_for_memref_p (x0, y0))
 686             return memrefs_conflict_p (xsize, x1, ysize, y1, c);
 687           if (GET_CODE (x1) == CONST_INT)
 688             if (GET_CODE (y1) == CONST_INT)
 689               return memrefs_conflict_p (xsize, x0, ysize, y0,
 690                                          c - INTVAL (x1) + INTVAL (y1));
 691             else
 692               return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
 693           else if (GET_CODE (y1) == CONST_INT)
 694             return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
 695
 696           return 1;
 697         }
 698       else if (GET_CODE (x1) == CONST_INT)
 699         return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
 700     }
 701   else if (GET_CODE (y) == PLUS)
 702     {
 703       /* The fact that Y is canonicalized means that this
 704          PLUS rtx is canonicalized.  */
 705       rtx y0 = XEXP (y, 0);
 706       rtx y1 = XEXP (y, 1);
 707
 708       if (GET_CODE (y1) == CONST_INT)
 709         return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
 710       else
 711         return 1;
 712     }
 713
 714   if (GET_CODE (x) == GET_CODE (y))
 715     switch (GET_CODE (x))
 716       {
 717       case MULT:
 718         {
 719           /* Handle cases where we expect the second operands to be the
 720              same, and check only whether the first operand would conflict
 721              or not.  */
 722           rtx x0, y0;
 723           rtx x1 = canon_rtx (XEXP (x, 1));
 724           rtx y1 = canon_rtx (XEXP (y, 1));
 725           if (! rtx_equal_for_memref_p (x1, y1))
 726             return 1;
 727           x0 = canon_rtx (XEXP (x, 0));
 728           y0 = canon_rtx (XEXP (y, 0));
 729           if (rtx_equal_for_memref_p (x0, y0))
 730             return (xsize == 0 || ysize == 0
 731                     || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
 732
 733           /* Can't properly adjust our sizes.  */
 734           if (GET_CODE (x1) != CONST_INT)
 735             return 1;
 736           xsize /= INTVAL (x1);
 737           ysize /= INTVAL (x1);
 738           c /= INTVAL (x1);
 739           return memrefs_conflict_p (xsize, x0, ysize, y0, c);
 740         }
 741
 742       default:
 743         break;
 744       }
 745
 746   /* Treat an access through an AND (e.g. a subword access on an Alpha)
 747      as an access with indeterminate size.
 748      ??? Could instead convert an n byte reference at (and x y) to an
 749      n-y byte reference at (plus x y). */
 750   if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
 751     return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
 752   if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
 753     {
 754       /* XXX: If we are indexing far enough into the array/structure, we
 755          may yet be able to determine that we can not overlap.  But we
 756          also need to that we are far enough from the end not to overlap
 757          a following reference, so we do nothing for now.  */
 758       return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
 759     }
 760
 761   if (CONSTANT_P (x))
 762     {
 763       if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
 764         {
 765           c += (INTVAL (y) - INTVAL (x));
 766           return (xsize <= 0 || ysize <= 0
 767                   || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
 768         }
 769
 770       if (GET_CODE (x) == CONST)
 771         {
 772           if (GET_CODE (y) == CONST)
 773             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
 774                                        ysize, canon_rtx (XEXP (y, 0)), c);
 775           else
 776             return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
 777                                        ysize, y, c);
 778         }
 779       if (GET_CODE (y) == CONST)
 780         return memrefs_conflict_p (xsize, x, ysize,
 781                                    canon_rtx (XEXP (y, 0)), c);
 782
 783       if (CONSTANT_P (y))
 784         return (xsize < 0 || ysize < 0
 785                 || (rtx_equal_for_memref_p (x, y)
 786                     && (xsize == 0 || ysize == 0
 787                         || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
 788
 789       return 1;
 790     }
 791   return 1;
 792 }
 793
 794 /* Functions to compute memory dependencies.
 795
 796    Since we process the insns in execution order, we can build tables
 797    to keep track of what registers are fixed (and not aliased), what registers
 798    are varying in known ways, and what registers are varying in unknown
 799    ways.
 800
 801    If both memory references are volatile, then there must always be a
 802    dependence between the two references, since their order can not be
 803    changed.  A volatile and non-volatile reference can be interchanged
 804    though.
 805
 806    A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
 807    conflict with a non-MEM_IN_STRUCT reference at a fixed address.   We must
 808    allow QImode aliasing because the ANSI C standard allows character
 809    pointers to alias anything.  We are assuming that characters are
 810    always QImode here.  We also must allow AND addresses, because they may
 811    generate accesses outside the object being referenced.  This is used to
 812    generate aligned addresses from unaligned addresses, for instance, the
 813    alpha storeqi_unaligned pattern.  */
 814
 815 /* Read dependence: X is read after read in MEM takes place.  There can
 816    only be a dependence here if both reads are volatile.  */
 817
 818 int
 819 read_dependence (mem, x)
 820      rtx mem;
 821      rtx x;
 822 {
 823   return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
 824 }
 825
 826 /* True dependence: X is read after store in MEM takes place.  */
 827
 828 int
 829 true_dependence (mem, mem_mode, x, varies)
 830      rtx mem;
 831      enum machine_mode mem_mode;
 832      rtx x;
 833      int (*varies)();
 834 {
 835   register rtx x_addr, mem_addr;
 836
 837   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
 838     return 1;
 839
 840   /* If X is an unchanging read, then it can't possibly conflict with any
 841      non-unchanging store.  It may conflict with an unchanging write though,
 842      because there may be a single store to this address to initialize it.
 843      Just fall through to the code below to resolve the case where we have
 844      both an unchanging read and an unchanging write.  This won't handle all
 845      cases optimally, but the possible performance loss should be
 846      negligible.  */
 847   if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
 848     return 0;
 849
 850   if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
 851     return 0;
 852
 853   x_addr = canon_rtx (XEXP (x, 0));
 854   mem_addr = canon_rtx (XEXP (mem, 0));
 855
 856   if (mem_mode == VOIDmode)
 857     mem_mode = GET_MODE (mem);
 858
 859   if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
 860                             SIZE_FOR_MODE (x), x_addr, 0))
 861     return 0;
 862
 863   /* If both references are struct references, or both are not, nothing
 864      is known about aliasing.
 865
 866      If either reference is QImode or BLKmode, ANSI C permits aliasing.
 867
 868      If both addresses are constant, or both are not, nothing is known
 869      about aliasing.  */
 870   if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem)
 871       || mem_mode == QImode || mem_mode == BLKmode
 872       || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode
 873       || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND
 874       || varies (x_addr) == varies (mem_addr))
 875     return 1;
 876
 877   /* One memory reference is to a constant address, one is not.
 878      One is to a structure, the other is not.
 879
 880      If either memory reference is a variable structure the other is a
 881      fixed scalar and there is no aliasing.  */
 882   if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr))
 883       || (MEM_IN_STRUCT_P (x) && varies (x_addr)))
 884     return 0;
 885
 886   return 1;
 887 }
 888
 889 /* Anti dependence: X is written after read in MEM takes place.  */
 890
 891 int
 892 anti_dependence (mem, x)
 893      rtx mem;
 894      rtx x;
 895 {
 896   rtx x_addr, mem_addr;
 897
 898   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
 899     return 1;
 900
 901   /* If MEM is an unchanging read, then it can't possibly conflict with
 902      the store to X, because there is at most one store to MEM, and it must
 903      have occurred somewhere before MEM.  */
 904   if (RTX_UNCHANGING_P (mem))
 905     return 0;
 906
 907   if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
 908     return 0;
 909
 910   x = canon_rtx (x);
 911   mem = canon_rtx (mem);
 912
 913   x_addr = XEXP (x, 0);
 914   mem_addr = XEXP (mem, 0);
 915
 916   return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
 917                               SIZE_FOR_MODE (x), x_addr, 0)
 918           && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
 919                 && GET_MODE (mem) != QImode
 920                 && GET_CODE (mem_addr) != AND
 921                 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
 922           && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
 923                 && GET_MODE (x) != QImode
 924                 && GET_CODE (x_addr) != AND
 925                 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
 926 }
 927
 928 /* Output dependence: X is written after store in MEM takes place.  */
 929
 930 int
 931 output_dependence (mem, x)
 932      register rtx mem;
 933      register rtx x;
 934 {
 935   if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
 936     return 1;
 937
 938   if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
 939     return 0;
 940
 941   x = canon_rtx (x);
 942   mem = canon_rtx (mem);
 943
 944   return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
 945                               SIZE_FOR_MODE (x), XEXP (x, 0), 0)
 946           && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
 947                 && GET_MODE (mem) != QImode
 948                 && GET_CODE (XEXP (mem, 0)) != AND
 949                 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
 950           && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
 951                 && GET_MODE (x) != QImode
 952                 && GET_CODE (XEXP (x, 0)) != AND
 953                 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)));
 954 }
 955
 956
 957 static HARD_REG_SET argument_registers;
 958
 959 void
 960 init_alias_once ()
 961 {
 962   register int i;
 963
 964 #ifndef OUTGOING_REGNO
 965 #define OUTGOING_REGNO(N) N
 966 #endif
 967   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 968     /* Check whether this register can hold an incoming pointer
 969        argument.  FUNCTION_ARG_REGNO_P tests outgoing register
 970        numbers, so translate if necessary due to register windows. */
 971     if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
 972         && HARD_REGNO_MODE_OK (i, Pmode))
 973       SET_HARD_REG_BIT (argument_registers, i);
 974 }
 975
 976 void
 977 init_alias_analysis ()
 978 {
 979   int maxreg = max_reg_num ();
 980   int changed, pass;
 981   register int i;
 982   register rtx insn;
 983
 984   reg_known_value_size = maxreg;
 985
 986   reg_known_value
 987     = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx))
 988     - FIRST_PSEUDO_REGISTER;
 989   reg_known_equiv_p =
 990     oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER;
 991   bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
 992          (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
 993   bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
 994          (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
 995
 996   /* Overallocate reg_base_value to allow some growth during loop
 997      optimization.  Loop unrolling can create a large number of
 998      registers.  */
 999   reg_base_value_size = maxreg * 2;
1000   reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
1001   new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
1002   reg_seen = (char *)alloca (reg_base_value_size);
1003   bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
1004
1005   /* The basic idea is that each pass through this loop will use the
1006      "constant" information from the previous pass to propagate alias
1007      information through another level of assignments.
1008
1009      This could get expensive if the assignment chains are long.  Maybe
1010      we should throttle the number of iterations, possibly based on
1011      the optimization level or flag_expensive_optimizations.
1012
1013      We could propagate more information in the first pass by making use
1014      of REG_N_SETS to determine immediately that the alias information
1015      for a pseudo is "constant".
1016
1017      A program with an uninitialized variable can cause an infinite loop
1018      here.  Instead of doing a full dataflow analysis to detect such problems
1019      we just cap the number of iterations for the loop.
1020
1021      The state of the arrays for the set chain in question does not matter
1022      since the program has undefined behavior.  */
1023
1024   pass = 0;
1025   do
1026     {
1027       /* Assume nothing will change this iteration of the loop.  */
1028       changed = 0;
1029
1030       /* We want to assign the same IDs each iteration of this loop, so
1031          start counting from zero each iteration of the loop.  */
1032       unique_id = 0;
1033
1034       /* We're at the start of the funtion each iteration through the
1035          loop, so we're copying arguments.  */
1036       copying_arguments = 1;
1037
1038       /* Wipe the potential alias information clean for this pass.  */
1039       bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
1040
1041       /* Wipe the reg_seen array clean.  */
1042       bzero ((char *) reg_seen, reg_base_value_size);
1043
1044       /* Mark all hard registers which may contain an address.
1045          The stack, frame and argument pointers may contain an address.
1046          An argument register which can hold a Pmode value may contain
1047          an address even if it is not in BASE_REGS.
1048
1049          The address expression is VOIDmode for an argument and
1050          Pmode for other registers.  */
1051
1052       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1053         if (TEST_HARD_REG_BIT (argument_registers, i))
1054           new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode,
1055                                                    gen_rtx_REG (Pmode, i));
1056
1057       new_reg_base_value[STACK_POINTER_REGNUM]
1058         = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
1059       new_reg_base_value[ARG_POINTER_REGNUM]
1060         = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
1061       new_reg_base_value[FRAME_POINTER_REGNUM]
1062         = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
1063 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1064       new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
1065         = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
1066 #endif
1067       if (struct_value_incoming_rtx
1068           && GET_CODE (struct_value_incoming_rtx) == REG)
1069         new_reg_base_value[REGNO (struct_value_incoming_rtx)]
1070           = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx);
1071
1072       if (static_chain_rtx
1073           && GET_CODE (static_chain_rtx) == REG)
1074         new_reg_base_value[REGNO (static_chain_rtx)]
1075           = gen_rtx_ADDRESS (Pmode, static_chain_rtx);
1076
1077       /* Walk the insns adding values to the new_reg_base_value array.  */
1078       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1079         {
1080           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1081             {
1082               rtx note, set;
1083               /* If this insn has a noalias note, process it,  Otherwise,
1084                  scan for sets.  A simple set will have no side effects
1085                  which could change the base value of any other register. */
1086
1087               if (GET_CODE (PATTERN (insn)) == SET
1088                   && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
1089                 record_set (SET_DEST (PATTERN (insn)), NULL_RTX);
1090               else
1091                 note_stores (PATTERN (insn), record_set);
1092
1093               set = single_set (insn);
1094
1095               if (set != 0
1096                   && GET_CODE (SET_DEST (set)) == REG
1097                   && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
1098                   && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
1099                        && REG_N_SETS (REGNO (SET_DEST (set))) == 1)
1100                       || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1101                   && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1102                 {
1103                   int regno = REGNO (SET_DEST (set));
1104                   reg_known_value[regno] = XEXP (note, 0);
1105                   reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
1106                 }
1107             }
1108           else if (GET_CODE (insn) == NOTE
1109                    && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
1110             copying_arguments = 0;
1111         }
1112
1113       /* Now propagate values from new_reg_base_value to reg_base_value.  */
1114       for (i = 0; i < reg_base_value_size; i++)
1115         {
1116           if (new_reg_base_value[i]
1117               && new_reg_base_value[i] != reg_base_value[i]
1118               && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
1119             {
1120               reg_base_value[i] = new_reg_base_value[i];
1121               changed = 1;
1122             }
1123         }
1124     }
1125   while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
1126
1127   /* Fill in the remaining entries.  */
1128   for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
1129     if (reg_known_value[i] == 0)
1130       reg_known_value[i] = regno_reg_rtx[i];
1131
1132   /* Simplify the reg_base_value array so that no register refers to
1133      another register, except to special registers indirectly through
1134      ADDRESS expressions.
1135
1136      In theory this loop can take as long as O(registers^2), but unless
1137      there are very long dependency chains it will run in close to linear
1138      time.
1139
1140      This loop may not be needed any longer now that the main loop does
1141      a better job at propagating alias information.  */
1142   pass = 0;
1143   do
1144     {
1145       changed = 0;
1146       pass++;
1147       for (i = 0; i < reg_base_value_size; i++)
1148         {
1149           rtx base = reg_base_value[i];
1150           if (base && GET_CODE (base) == REG)
1151             {
1152               int base_regno = REGNO (base);
1153               if (base_regno == i)              /* register set from itself */
1154                 reg_base_value[i] = 0;
1155               else
1156                 reg_base_value[i] = reg_base_value[base_regno];
1157               changed = 1;
1158             }
1159         }
1160     }
1161   while (changed && pass < MAX_ALIAS_LOOP_PASSES);
1162
1163   new_reg_base_value = 0;
1164   reg_seen = 0;
1165 }
1166
1167 void
1168 end_alias_analysis ()
1169 {
1170   reg_known_value = 0;
1171   reg_base_value = 0;
1172   reg_base_value_size = 0;
1173 }