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