gcc/alias.c

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