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