gcc/rtlanal.c

   1 /* Analyze RTL for C-Compiler
   2    Copyright (C) 1987, 1988, 1991, 1992 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 #include "config.h"
  22 #include "rtl.h"
  23
  24 void note_stores ();
  25 int reg_set_p ();
  26
  27 /* Bit flags that specify the machine subtype we are compiling for.
  28    Bits are tested using macros TARGET_... defined in the tm.h file
  29    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
  30
  31 int target_flags;
  32 \f
  33 /* Return 1 if the value of X is unstable
  34    (would be different at a different point in the program).
  35    The frame pointer, arg pointer, etc. are considered stable
  36    (within one function) and so is anything marked `unchanging'.  */
  37
  38 int
  39 rtx_unstable_p (x)
  40      rtx x;
  41 {
  42   register RTX_CODE code = GET_CODE (x);
  43   register int i;
  44   register char *fmt;
  45
  46   if (code == MEM)
  47     return ! RTX_UNCHANGING_P (x);
  48
  49   if (code == QUEUED)
  50     return 1;
  51
  52   if (code == CONST || code == CONST_INT)
  53     return 0;
  54
  55   if (code == REG)
  56     return ! (REGNO (x) == FRAME_POINTER_REGNUM
  57               || REGNO (x) == ARG_POINTER_REGNUM
  58               || RTX_UNCHANGING_P (x));
  59
  60   fmt = GET_RTX_FORMAT (code);
  61   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  62     if (fmt[i] == 'e')
  63       if (rtx_unstable_p (XEXP (x, i)))
  64         return 1;
  65   return 0;
  66 }
  67
  68 /* Return 1 if X has a value that can vary even between two
  69    executions of the program.  0 means X can be compared reliably
  70    against certain constants or near-constants.
  71    The frame pointer and the arg pointer are considered constant.  */
  72
  73 int
  74 rtx_varies_p (x)
  75      rtx x;
  76 {
  77   register RTX_CODE code = GET_CODE (x);
  78   register int i;
  79   register char *fmt;
  80
  81   switch (code)
  82     {
  83     case MEM:
  84     case QUEUED:
  85       return 1;
  86
  87     case CONST:
  88     case CONST_INT:
  89     case CONST_DOUBLE:
  90     case SYMBOL_REF:
  91     case LABEL_REF:
  92       return 0;
  93
  94     case REG:
  95       /* Note that we have to test for the actual rtx used for the frame
  96          and arg pointers and not just the register number in case we have
  97          eliminated the frame and/or arg pointer and are using it
  98          for pseudos.  */
  99       return ! (x == frame_pointer_rtx || x == arg_pointer_rtx);
 100
 101     case LO_SUM:
 102       /* The operand 0 of a LO_SUM is considered constant
 103          (in fact is it related specifically to operand 1).  */
 104       return rtx_varies_p (XEXP (x, 1));
 105     }
 106
 107   fmt = GET_RTX_FORMAT (code);
 108   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 109     if (fmt[i] == 'e')
 110       if (rtx_varies_p (XEXP (x, i)))
 111         return 1;
 112   return 0;
 113 }
 114
 115 /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
 116
 117 int
 118 rtx_addr_can_trap_p (x)
 119      register rtx x;
 120 {
 121   register enum rtx_code code = GET_CODE (x);
 122
 123   switch (code)
 124     {
 125     case SYMBOL_REF:
 126     case LABEL_REF:
 127       /* SYMBOL_REF is problematic due to the possible presence of
 128          a #pragma weak, but to say that loads from symbols can trap is
 129          *very* costly.  It's not at all clear what's best here.  For
 130          now, we ignore the impact of #pragma weak.  */
 131       return 0;
 132
 133     case REG:
 134       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 135       return ! (x == frame_pointer_rtx || x == stack_pointer_rtx
 136                 || x == arg_pointer_rtx);
 137
 138     case CONST:
 139       return rtx_addr_can_trap_p (XEXP (x, 0));
 140
 141     case PLUS:
 142       /* An address is assumed not to trap if it is an address that can't
 143          trap plus a constant integer.  */
 144       return (rtx_addr_can_trap_p (XEXP (x, 0))
 145               || GET_CODE (XEXP (x, 1)) != CONST_INT);
 146
 147     case LO_SUM:
 148       return rtx_addr_can_trap_p (XEXP (x, 1));
 149     }
 150
 151   /* If it isn't one of the case above, it can cause a trap.  */
 152   return 1;
 153 }
 154
 155 /* Return 1 if X refers to a memory location whose address
 156    cannot be compared reliably with constant addresses,
 157    or if X refers to a BLKmode memory object.  */
 158
 159 int
 160 rtx_addr_varies_p (x)
 161      rtx x;
 162 {
 163   register enum rtx_code code;
 164   register int i;
 165   register char *fmt;
 166
 167   if (x == 0)
 168     return 0;
 169
 170   code = GET_CODE (x);
 171   if (code == MEM)
 172     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0));
 173
 174   fmt = GET_RTX_FORMAT (code);
 175   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 176     if (fmt[i] == 'e')
 177       if (rtx_addr_varies_p (XEXP (x, i)))
 178         return 1;
 179   return 0;
 180 }
 181 \f
 182 /* Return the value of the integer term in X, if one is apparent;
 183    otherwise return 0.
 184    Only obvious integer terms are detected.
 185    This is used in cse.c with the `related_value' field.*/
 186
 187 HOST_WIDE_INT
 188 get_integer_term (x)
 189      rtx x;
 190 {
 191   if (GET_CODE (x) == CONST)
 192     x = XEXP (x, 0);
 193
 194   if (GET_CODE (x) == MINUS
 195       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 196     return - INTVAL (XEXP (x, 1));
 197   if (GET_CODE (x) == PLUS
 198       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 199     return INTVAL (XEXP (x, 1));
 200   return 0;
 201 }
 202
 203 /* If X is a constant, return the value sans apparent integer term;
 204    otherwise return 0.
 205    Only obvious integer terms are detected.  */
 206
 207 rtx
 208 get_related_value (x)
 209      rtx x;
 210 {
 211   if (GET_CODE (x) != CONST)
 212     return 0;
 213   x = XEXP (x, 0);
 214   if (GET_CODE (x) == PLUS
 215       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 216     return XEXP (x, 0);
 217   else if (GET_CODE (x) == MINUS
 218            && GET_CODE (XEXP (x, 1)) == CONST_INT)
 219     return XEXP (x, 0);
 220   return 0;
 221 }
 222 \f
 223 /* Nonzero if register REG appears somewhere within IN.
 224    Also works if REG is not a register; in this case it checks
 225    for a subexpression of IN that is Lisp "equal" to REG.  */
 226
 227 int
 228 reg_mentioned_p (reg, in)
 229      register rtx reg, in;
 230 {
 231   register char *fmt;
 232   register int i;
 233   register enum rtx_code code;
 234
 235   if (in == 0)
 236     return 0;
 237
 238   if (reg == in)
 239     return 1;
 240
 241   if (GET_CODE (in) == LABEL_REF)
 242     return reg == XEXP (in, 0);
 243
 244   code = GET_CODE (in);
 245
 246   switch (code)
 247     {
 248       /* Compare registers by number.  */
 249     case REG:
 250       return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
 251
 252       /* These codes have no constituent expressions
 253          and are unique.  */
 254     case SCRATCH:
 255     case CC0:
 256     case PC:
 257       return 0;
 258
 259     case CONST_INT:
 260       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
 261
 262     case CONST_DOUBLE:
 263       /* These are kept unique for a given value.  */
 264       return 0;
 265     }
 266
 267   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
 268     return 1;
 269
 270   fmt = GET_RTX_FORMAT (code);
 271
 272   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 273     {
 274       if (fmt[i] == 'E')
 275         {
 276           register int j;
 277           for (j = XVECLEN (in, i) - 1; j >= 0; j--)
 278             if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
 279               return 1;
 280         }
 281       else if (fmt[i] == 'e'
 282                && reg_mentioned_p (reg, XEXP (in, i)))
 283         return 1;
 284     }
 285   return 0;
 286 }
 287 \f
 288 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 289    no CODE_LABEL insn.  */
 290
 291 int
 292 no_labels_between_p (beg, end)
 293      rtx beg, end;
 294 {
 295   register rtx p;
 296   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 297     if (GET_CODE (p) == CODE_LABEL)
 298       return 0;
 299   return 1;
 300 }
 301
 302 /* Nonzero if register REG is used in an insn between
 303    FROM_INSN and TO_INSN (exclusive of those two).  */
 304
 305 int
 306 reg_used_between_p (reg, from_insn, to_insn)
 307      rtx reg, from_insn, to_insn;
 308 {
 309   register rtx insn;
 310
 311   if (from_insn == to_insn)
 312     return 0;
 313
 314   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 315     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
 316         && reg_overlap_mentioned_p (reg, PATTERN (insn)))
 317       return 1;
 318   return 0;
 319 }
 320 \f
 321 /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
 322    is entirely replaced by a new value and the only use is as a SET_DEST,
 323    we do not consider it a reference.  */
 324
 325 int
 326 reg_referenced_p (x, body)
 327      rtx x;
 328      rtx body;
 329 {
 330   int i;
 331
 332   switch (GET_CODE (body))
 333     {
 334     case SET:
 335       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
 336         return 1;
 337
 338       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
 339          of a REG that occupies all of the REG, the insn references X if
 340          it is mentioned in the destination.  */
 341       if (GET_CODE (SET_DEST (body)) != CC0
 342           && GET_CODE (SET_DEST (body)) != PC
 343           && GET_CODE (SET_DEST (body)) != REG
 344           && ! (GET_CODE (SET_DEST (body)) == SUBREG
 345                 && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG
 346                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
 347                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
 348                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
 349                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
 350           && reg_overlap_mentioned_p (x, SET_DEST (body)))
 351         return 1;
 352       break;
 353
 354     case ASM_OPERANDS:
 355       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
 356         if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
 357           return 1;
 358       break;
 359
 360     case CALL:
 361     case USE:
 362       return reg_overlap_mentioned_p (x, body);
 363
 364     case TRAP_IF:
 365       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
 366
 367     case UNSPEC:
 368     case UNSPEC_VOLATILE:
 369     case PARALLEL:
 370       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 371         if (reg_referenced_p (x, XVECEXP (body, 0, i)))
 372           return 1;
 373       break;
 374     }
 375
 376   return 0;
 377 }
 378
 379 /* Nonzero if register REG is referenced in an insn between
 380    FROM_INSN and TO_INSN (exclusive of those two).  Sets of REG do
 381    not count. */
 382
 383 int
 384 reg_referenced_between_p (reg, from_insn, to_insn)
 385      rtx reg, from_insn, to_insn;
 386 {
 387   register rtx insn;
 388
 389   if (from_insn == to_insn)
 390     return 0;
 391
 392   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 393     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
 394         && reg_referenced_p (reg, PATTERN (insn)))
 395       return 1;
 396   return 0;
 397 }
 398 \f
 399 /* Nonzero if register REG is set or clobbered in an insn between
 400    FROM_INSN and TO_INSN (exclusive of those two).  */
 401
 402 int
 403 reg_set_between_p (reg, from_insn, to_insn)
 404      rtx reg, from_insn, to_insn;
 405 {
 406   register rtx insn;
 407
 408   if (from_insn == to_insn)
 409     return 0;
 410
 411   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 412     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
 413         && reg_set_p (reg, insn))
 414       return 1;
 415   return 0;
 416 }
 417
 418 /* Internals of reg_set_between_p.  */
 419
 420 static rtx reg_set_reg;
 421 static int reg_set_flag;
 422
 423 void
 424 reg_set_p_1 (x)
 425      rtx x;
 426 {
 427   /* We don't want to return 1 if X is a MEM that contains a register
 428      within REG_SET_REG.  */
 429
 430   if ((GET_CODE (x) != MEM)
 431       && reg_overlap_mentioned_p (reg_set_reg, x))
 432     reg_set_flag = 1;
 433 }
 434
 435 int
 436 reg_set_p (reg, insn)
 437      rtx reg, insn;
 438 {
 439   rtx body = insn;
 440
 441   /* We can be passed an insn or part of one.  If we are passed an insn,
 442      check if a side-effect of the insn clobbers REG.  */
 443   if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 444     {
 445       if (FIND_REG_INC_NOTE (insn, reg)
 446           || (GET_CODE (insn) == CALL_INSN
 447               /* We'd like to test call_used_regs here, but rtlanal.c can't
 448                  reference that variable due to its use in genattrtab.  So
 449                  we'll just be more conservative.  */
 450               && ((GET_CODE (reg) == REG
 451                    && REGNO (reg) < FIRST_PSEUDO_REGISTER)
 452                   || GET_CODE (reg) == MEM)))
 453         return 1;
 454
 455       body = PATTERN (insn);
 456     }
 457
 458   reg_set_reg = reg;
 459   reg_set_flag = 0;
 460   note_stores (body, reg_set_p_1);
 461   return reg_set_flag;
 462 }
 463
 464 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 465    only if none of them are modified between START and END.  Return 1 if
 466    X contains a MEM; this routine does not perform any memory aliasing.  */
 467
 468 int
 469 modified_between_p (x, start, end)
 470      rtx x;
 471      rtx start, end;
 472 {
 473   enum rtx_code code = GET_CODE (x);
 474   char *fmt;
 475   int i;
 476
 477   switch (code)
 478     {
 479     case CONST_INT:
 480     case CONST_DOUBLE:
 481     case CONST:
 482     case SYMBOL_REF:
 483     case LABEL_REF:
 484       return 0;
 485
 486     case PC:
 487     case CC0:
 488       return 1;
 489
 490     case MEM:
 491       /* If the memory is not constant, assume it is modified.  If it is
 492          constant, we still have to check the address.  */
 493       if (! RTX_UNCHANGING_P (x))
 494         return 1;
 495       break;
 496
 497     case REG:
 498       return reg_set_between_p (x, start, end);
 499     }
 500
 501   fmt = GET_RTX_FORMAT (code);
 502   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 503     if (fmt[i] == 'e'
 504         && modified_between_p (XEXP (x, i), start, end))
 505       return 1;
 506
 507   return 0;
 508 }
 509 \f
 510 /* Given an INSN, return a SET expression if this insn has only a single SET.
 511    It may also have CLOBBERs, USEs, or SET whose output
 512    will not be used, which we ignore.  */
 513
 514 rtx
 515 single_set (insn)
 516      rtx insn;
 517 {
 518   rtx set;
 519   int i;
 520
 521   if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
 522     return 0;
 523
 524   if (GET_CODE (PATTERN (insn)) == SET)
 525     return PATTERN (insn);
 526
 527   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
 528     {
 529       for (i = 0, set = 0; i < XVECLEN (PATTERN (insn), 0); i++)
 530         if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
 531             && (! find_reg_note (insn, REG_UNUSED,
 532                                  SET_DEST (XVECEXP (PATTERN (insn), 0, i)))
 533                 || side_effects_p (XVECEXP (PATTERN (insn), 0, i))))
 534           {
 535             if (set)
 536               return 0;
 537             else
 538               set = XVECEXP (PATTERN (insn), 0, i);
 539           }
 540       return set;
 541     }
 542
 543   return 0;
 544 }
 545 \f
 546 /* Return the last thing that X was assigned from before *PINSN.  Verify that
 547    the object is not modified up to VALID_TO.  If it was, if we hit
 548    a partial assignment to X, or hit a CODE_LABEL first, return X.  If we
 549    found an assignment, update *PINSN to point to it.  */
 550
 551 rtx
 552 find_last_value (x, pinsn, valid_to)
 553      rtx x;
 554      rtx *pinsn;
 555      rtx valid_to;
 556 {
 557   rtx p;
 558
 559   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
 560        p = PREV_INSN (p))
 561     if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
 562       {
 563         rtx set = single_set (p);
 564         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
 565
 566         if (set && rtx_equal_p (x, SET_DEST (set)))
 567           {
 568             rtx src = SET_SRC (set);
 569
 570             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
 571               src = XEXP (note, 0);
 572
 573             if (! modified_between_p (src, PREV_INSN (p), valid_to)
 574                 /* Reject hard registers because we don't usually want
 575                    to use them; we'd rather use a pseudo.  */
 576                 && ! (GET_CODE (src) == REG
 577                       && REGNO (src) < FIRST_PSEUDO_REGISTER))
 578               {
 579                 *pinsn = p;
 580                 return src;
 581               }
 582           }
 583
 584         /* If set in non-simple way, we don't have a value.  */
 585         if (reg_set_p (x, p))
 586           break;
 587       }
 588
 589   return x;
 590 }
 591 \f
 592 /* Return nonzero if register in range [REGNO, ENDREGNO)
 593    appears either explicitly or implicitly in X
 594    other than being stored into.
 595
 596    References contained within the substructure at LOC do not count.
 597    LOC may be zero, meaning don't ignore anything.  */
 598
 599 int
 600 refers_to_regno_p (regno, endregno, x, loc)
 601      int regno, endregno;
 602      rtx x;
 603      rtx *loc;
 604 {
 605   register int i;
 606   register RTX_CODE code;
 607   register char *fmt;
 608
 609  repeat:
 610   /* The contents of a REG_NONNEG note is always zero, so we must come here
 611      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
 612   if (x == 0)
 613     return 0;
 614
 615   code = GET_CODE (x);
 616
 617   switch (code)
 618     {
 619     case REG:
 620       i = REGNO (x);
 621       return (endregno > i
 622               && regno < i + (i < FIRST_PSEUDO_REGISTER
 623                               ? HARD_REGNO_NREGS (i, GET_MODE (x))
 624                               : 1));
 625
 626     case SUBREG:
 627       /* If this is a SUBREG of a hard reg, we can see exactly which
 628          registers are being modified.  Otherwise, handle normally.  */
 629       if (GET_CODE (SUBREG_REG (x)) == REG
 630           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
 631         {
 632           int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
 633           int inner_endregno
 634             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
 635                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
 636
 637           return endregno > inner_regno && regno < inner_endregno;
 638         }
 639       break;
 640
 641     case CLOBBER:
 642     case SET:
 643       if (&SET_DEST (x) != loc
 644           /* Note setting a SUBREG counts as referring to the REG it is in for
 645              a pseudo but not for hard registers since we can
 646              treat each word individually.  */
 647           && ((GET_CODE (SET_DEST (x)) == SUBREG
 648                && loc != &SUBREG_REG (SET_DEST (x))
 649                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
 650                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
 651                && refers_to_regno_p (regno, endregno,
 652                                      SUBREG_REG (SET_DEST (x)), loc))
 653               || (GET_CODE (SET_DEST (x)) != REG
 654                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
 655         return 1;
 656
 657       if (code == CLOBBER || loc == &SET_SRC (x))
 658         return 0;
 659       x = SET_SRC (x);
 660       goto repeat;
 661     }
 662
 663   /* X does not match, so try its subexpressions.  */
 664
 665   fmt = GET_RTX_FORMAT (code);
 666   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 667     {
 668       if (fmt[i] == 'e' && loc != &XEXP (x, i))
 669         {
 670           if (i == 0)
 671             {
 672               x = XEXP (x, 0);
 673               goto repeat;
 674             }
 675           else
 676             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
 677               return 1;
 678         }
 679       else if (fmt[i] == 'E')
 680         {
 681           register int j;
 682           for (j = XVECLEN (x, i) - 1; j >=0; j--)
 683             if (loc != &XVECEXP (x, i, j)
 684                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
 685               return 1;
 686         }
 687     }
 688   return 0;
 689 }
 690
 691 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
 692    we check if any register number in X conflicts with the relevant register
 693    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
 694    contains a MEM (we don't bother checking for memory addresses that can't
 695    conflict because we expect this to be a rare case.  */
 696
 697 int
 698 reg_overlap_mentioned_p (x, in)
 699      rtx x, in;
 700 {
 701   int regno, endregno;
 702
 703   if (GET_CODE (x) == SUBREG)
 704     {
 705       regno = REGNO (SUBREG_REG (x));
 706       if (regno < FIRST_PSEUDO_REGISTER)
 707         regno += SUBREG_WORD (x);
 708     }
 709   else if (GET_CODE (x) == REG)
 710     regno = REGNO (x);
 711   else if (CONSTANT_P (x))
 712     return 0;
 713   else if (GET_CODE (x) == MEM)
 714     {
 715       char *fmt;
 716       int i;
 717
 718       if (GET_CODE (in) == MEM)
 719         return 1;
 720
 721       fmt = GET_RTX_FORMAT (GET_CODE (in));
 722
 723       for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
 724         if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
 725           return 1;
 726
 727       return 0;
 728     }
 729   else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
 730            || GET_CODE (x) == CC0)
 731     return reg_mentioned_p (x, in);
 732   else
 733     abort ();
 734
 735   endregno = regno + (regno < FIRST_PSEUDO_REGISTER
 736                       ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
 737
 738   return refers_to_regno_p (regno, endregno, in, NULL_PTR);
 739 }
 740 \f
 741 /* Used for communications between the next few functions.  */
 742
 743 static int reg_set_last_unknown;
 744 static rtx reg_set_last_value;
 745 static int reg_set_last_first_regno, reg_set_last_last_regno;
 746
 747 /* Called via note_stores from reg_set_last.  */
 748
 749 static void
 750 reg_set_last_1 (x, pat)
 751      rtx x;
 752      rtx pat;
 753 {
 754   int first, last;
 755
 756   /* If X is not a register, or is not one in the range we care
 757      about, ignore.  */
 758   if (GET_CODE (x) != REG)
 759     return;
 760
 761   first = REGNO (x);
 762   last = first + (first < FIRST_PSEUDO_REGISTER
 763                   ? HARD_REGNO_NREGS (first, GET_MODE (x)) : 1);
 764
 765   if (first >= reg_set_last_last_regno
 766       || last <= reg_set_last_first_regno)
 767     return;
 768
 769   /* If this is a CLOBBER or is some complex LHS, or doesn't modify
 770      exactly the registers we care about, show we don't know the value.  */
 771   if (GET_CODE (pat) == CLOBBER || SET_DEST (pat) != x
 772       || first != reg_set_last_first_regno
 773       || last != reg_set_last_last_regno)
 774     reg_set_last_unknown = 1;
 775   else
 776     reg_set_last_value = SET_SRC (pat);
 777 }
 778
 779 /* Return the last value to which REG was set prior to INSN.  If we can't
 780    find it easily, return 0.
 781
 782    We only return a REG, SUBREG, or constant because it is too hard to
 783    check if a MEM remains unchanged.  */
 784
 785 rtx
 786 reg_set_last (x, insn)
 787      rtx x;
 788      rtx insn;
 789 {
 790   rtx orig_insn = insn;
 791
 792   reg_set_last_first_regno = REGNO (x);
 793
 794   reg_set_last_last_regno
 795     = reg_set_last_first_regno
 796       + (reg_set_last_first_regno < FIRST_PSEUDO_REGISTER
 797          ? HARD_REGNO_NREGS (reg_set_last_first_regno, GET_MODE (x)) : 1);
 798
 799   reg_set_last_unknown = 0;
 800   reg_set_last_value = 0;
 801
 802   /* Scan backwards until reg_set_last_1 changed one of the above flags.
 803      Stop when we reach a label or X is a hard reg and we reach a
 804      CALL_INSN (if reg_set_last_last_regno is a hard reg).
 805
 806      If we find a set of X, ensure that its SET_SRC remains unchanged.  */
 807
 808   for (;
 809        insn && GET_CODE (insn) != CODE_LABEL
 810        && ! (GET_CODE (insn) == CALL_INSN
 811              && reg_set_last_last_regno <= FIRST_PSEUDO_REGISTER);
 812        insn = PREV_INSN (insn))
 813     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 814       {
 815         note_stores (PATTERN (insn), reg_set_last_1);
 816         if (reg_set_last_unknown)
 817           return 0;
 818         else if (reg_set_last_value)
 819           {
 820             if (CONSTANT_P (reg_set_last_value)
 821                 || ((GET_CODE (reg_set_last_value) == REG
 822                      || GET_CODE (reg_set_last_value) == SUBREG)
 823                     && ! reg_set_between_p (reg_set_last_value,
 824                                             NEXT_INSN (insn), orig_insn)))
 825               return reg_set_last_value;
 826             else
 827               return 0;
 828           }
 829       }
 830
 831   return 0;
 832 }
 833 \f
 834 /* This is 1 until after reload pass.  */
 835 int rtx_equal_function_value_matters;
 836
 837 /* Return 1 if X and Y are identical-looking rtx's.
 838    This is the Lisp function EQUAL for rtx arguments.  */
 839
 840 int
 841 rtx_equal_p (x, y)
 842      rtx x, y;
 843 {
 844   register int i;
 845   register int j;
 846   register enum rtx_code code;
 847   register char *fmt;
 848
 849   if (x == y)
 850     return 1;
 851   if (x == 0 || y == 0)
 852     return 0;
 853
 854   code = GET_CODE (x);
 855   /* Rtx's of different codes cannot be equal.  */
 856   if (code != GET_CODE (y))
 857     return 0;
 858
 859   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 860      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 861
 862   if (GET_MODE (x) != GET_MODE (y))
 863     return 0;
 864
 865   /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively.  */
 866
 867   if (code == REG)
 868     /* Until rtl generation is complete, don't consider a reference to the
 869        return register of the current function the same as the return from a
 870        called function.  This eases the job of function integration.  Once the
 871        distinction is no longer needed, they can be considered equivalent.  */
 872     return (REGNO (x) == REGNO (y)
 873             && (! rtx_equal_function_value_matters
 874                 || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 875   else if (code == LABEL_REF)
 876     return XEXP (x, 0) == XEXP (y, 0);
 877   else if (code == SYMBOL_REF)
 878     return XSTR (x, 0) == XSTR (y, 0);
 879   else if (code == SCRATCH || code == CONST_DOUBLE)
 880     return 0;
 881
 882   /* Compare the elements.  If any pair of corresponding elements
 883      fail to match, return 0 for the whole things.  */
 884
 885   fmt = GET_RTX_FORMAT (code);
 886   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 887     {
 888       switch (fmt[i])
 889         {
 890         case 'w':
 891           if (XWINT (x, i) != XWINT (y, i))
 892             return 0;
 893           break;
 894
 895         case 'n':
 896         case 'i':
 897           if (XINT (x, i) != XINT (y, i))
 898             return 0;
 899           break;
 900
 901         case 'V':
 902         case 'E':
 903           /* Two vectors must have the same length.  */
 904           if (XVECLEN (x, i) != XVECLEN (y, i))
 905             return 0;
 906
 907           /* And the corresponding elements must match.  */
 908           for (j = 0; j < XVECLEN (x, i); j++)
 909             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 910               return 0;
 911           break;
 912
 913         case 'e':
 914           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 915             return 0;
 916           break;
 917
 918         case 'S':
 919         case 's':
 920           if (strcmp (XSTR (x, i), XSTR (y, i)))
 921             return 0;
 922           break;
 923
 924         case 'u':
 925           /* These are just backpointers, so they don't matter.  */
 926           break;
 927
 928         case '0':
 929           break;
 930
 931           /* It is believed that rtx's at this level will never
 932              contain anything but integers and other rtx's,
 933              except for within LABEL_REFs and SYMBOL_REFs.  */
 934         default:
 935           abort ();
 936         }
 937     }
 938   return 1;
 939 }
 940 \f
 941 /* Call FUN on each register or MEM that is stored into or clobbered by X.
 942    (X would be the pattern of an insn).
 943    FUN receives two arguments:
 944      the REG, MEM, CC0 or PC being stored in or clobbered,
 945      the SET or CLOBBER rtx that does the store.
 946
 947   If the item being stored in or clobbered is a SUBREG of a hard register,
 948   the SUBREG will be passed.  */
 949
 950 void
 951 note_stores (x, fun)
 952      register rtx x;
 953      void (*fun) ();
 954 {
 955   if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER))
 956     {
 957       register rtx dest = SET_DEST (x);
 958       while ((GET_CODE (dest) == SUBREG
 959               && (GET_CODE (SUBREG_REG (dest)) != REG
 960                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
 961              || GET_CODE (dest) == ZERO_EXTRACT
 962              || GET_CODE (dest) == SIGN_EXTRACT
 963              || GET_CODE (dest) == STRICT_LOW_PART)
 964         dest = XEXP (dest, 0);
 965       (*fun) (dest, x);
 966     }
 967   else if (GET_CODE (x) == PARALLEL)
 968     {
 969       register int i;
 970       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
 971         {
 972           register rtx y = XVECEXP (x, 0, i);
 973           if (GET_CODE (y) == SET || GET_CODE (y) == CLOBBER)
 974             {
 975               register rtx dest = SET_DEST (y);
 976               while ((GET_CODE (dest) == SUBREG
 977                       && (GET_CODE (SUBREG_REG (dest)) != REG
 978                           || (REGNO (SUBREG_REG (dest))
 979                               >= FIRST_PSEUDO_REGISTER)))
 980                      || GET_CODE (dest) == ZERO_EXTRACT
 981                      || GET_CODE (dest) == SIGN_EXTRACT
 982                      || GET_CODE (dest) == STRICT_LOW_PART)
 983                 dest = XEXP (dest, 0);
 984               (*fun) (dest, y);
 985             }
 986         }
 987     }
 988 }
 989 \f
 990 /* Return nonzero if X's old contents don't survive after INSN.
 991    This will be true if X is (cc0) or if X is a register and
 992    X dies in INSN or because INSN entirely sets X.
 993
 994    "Entirely set" means set directly and not through a SUBREG,
 995    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
 996    Likewise, REG_INC does not count.
 997
 998    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
 999    but for this use that makes no difference, since regs don't overlap
1000    during their lifetimes.  Therefore, this function may be used
1001    at any time after deaths have been computed (in flow.c).
1002
1003    If REG is a hard reg that occupies multiple machine registers, this
1004    function will only return 1 if each of those registers will be replaced
1005    by INSN.  */
1006
1007 int
1008 dead_or_set_p (insn, x)
1009      rtx insn;
1010      rtx x;
1011 {
1012   register int regno, last_regno;
1013   register int i;
1014
1015   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1016   if (GET_CODE (x) == CC0)
1017     return 1;
1018
1019   if (GET_CODE (x) != REG)
1020     abort ();
1021
1022   regno = REGNO (x);
1023   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1024                 : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
1025
1026   for (i = regno; i <= last_regno; i++)
1027     if (! dead_or_set_regno_p (insn, i))
1028       return 0;
1029
1030   return 1;
1031 }
1032
1033 /* Utility function for dead_or_set_p to check an individual register.  Also
1034    called from flow.c.  */
1035
1036 int
1037 dead_or_set_regno_p (insn, test_regno)
1038      rtx insn;
1039      int test_regno;
1040 {
1041   int regno, endregno;
1042   rtx link;
1043
1044   /* See if there is a death note for something that includes TEST_REGNO.  */
1045   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1046     {
1047       if (REG_NOTE_KIND (link) != REG_DEAD || GET_CODE (XEXP (link, 0)) != REG)
1048         continue;
1049
1050       regno = REGNO (XEXP (link, 0));
1051       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1052                   : regno + HARD_REGNO_NREGS (regno,
1053                                               GET_MODE (XEXP (link, 0))));
1054
1055       if (test_regno >= regno && test_regno < endregno)
1056         return 1;
1057     }
1058
1059   if (GET_CODE (PATTERN (insn)) == SET)
1060     {
1061       rtx dest = SET_DEST (PATTERN (insn));
1062
1063       /* A value is totally replaced if it is the destination or the
1064          destination is a SUBREG of REGNO that does not change the number of
1065          words in it.  */
1066      if (GET_CODE (dest) == SUBREG
1067           && (((GET_MODE_SIZE (GET_MODE (dest))
1068                 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1069               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1070                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1071         dest = SUBREG_REG (dest);
1072
1073       if (GET_CODE (dest) != REG)
1074         return 0;
1075
1076       regno = REGNO (dest);
1077       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1078                   : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1079
1080       return (test_regno >= regno && test_regno < endregno);
1081     }
1082   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1083     {
1084       register int i;
1085
1086       for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1087         {
1088           rtx body = XVECEXP (PATTERN (insn), 0, i);
1089
1090           if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1091             {
1092               rtx dest = SET_DEST (body);
1093
1094               if (GET_CODE (dest) == SUBREG
1095                   && (((GET_MODE_SIZE (GET_MODE (dest))
1096                         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1097                       == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1098                            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1099                 dest = SUBREG_REG (dest);
1100
1101               if (GET_CODE (dest) != REG)
1102                 continue;
1103
1104               regno = REGNO (dest);
1105               endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1106                           : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1107
1108               if (test_regno >= regno && test_regno < endregno)
1109                 return 1;
1110             }
1111         }
1112     }
1113
1114   return 0;
1115 }
1116
1117 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1118    If DATUM is nonzero, look for one whose datum is DATUM.  */
1119
1120 rtx
1121 find_reg_note (insn, kind, datum)
1122      rtx insn;
1123      enum reg_note kind;
1124      rtx datum;
1125 {
1126   register rtx link;
1127
1128   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1129     if (REG_NOTE_KIND (link) == kind
1130         && (datum == 0 || datum == XEXP (link, 0)))
1131       return link;
1132   return 0;
1133 }
1134
1135 /* Return the reg-note of kind KIND in insn INSN which applies to register
1136    number REGNO, if any.  Return 0 if there is no such reg-note.  */
1137
1138 rtx
1139 find_regno_note (insn, kind, regno)
1140      rtx insn;
1141      enum reg_note kind;
1142      int regno;
1143 {
1144   register rtx link;
1145
1146   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1147     if (REG_NOTE_KIND (link) == kind
1148         /* Verify that it is a register, so that scratch and MEM won't cause a
1149            problem here.  */
1150         && GET_CODE (XEXP (link, 0)) == REG
1151         && REGNO (XEXP (link, 0)) == regno)
1152       return link;
1153   return 0;
1154 }
1155 \f
1156 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1157
1158 void
1159 remove_note (insn, note)
1160      register rtx note;
1161      register rtx insn;
1162 {
1163   register rtx link;
1164
1165   if (REG_NOTES (insn) == note)
1166     {
1167       REG_NOTES (insn) = XEXP (note, 1);
1168       return;
1169     }
1170
1171   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1172     if (XEXP (link, 1) == note)
1173       {
1174         XEXP (link, 1) = XEXP (note, 1);
1175         return;
1176       }
1177
1178   abort ();
1179 }
1180 \f
1181 /* Nonzero if X contains any volatile memory references
1182    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1183
1184 int
1185 volatile_refs_p (x)
1186      rtx x;
1187 {
1188   register RTX_CODE code;
1189
1190   code = GET_CODE (x);
1191   switch (code)
1192     {
1193     case LABEL_REF:
1194     case SYMBOL_REF:
1195     case CONST_INT:
1196     case CONST:
1197     case CONST_DOUBLE:
1198     case CC0:
1199     case PC:
1200     case REG:
1201     case SCRATCH:
1202     case CLOBBER:
1203     case ASM_INPUT:
1204     case ADDR_VEC:
1205     case ADDR_DIFF_VEC:
1206       return 0;
1207
1208     case CALL:
1209     case UNSPEC_VOLATILE:
1210  /* case TRAP_IF: This isn't clear yet.  */
1211       return 1;
1212
1213     case MEM:
1214     case ASM_OPERANDS:
1215       if (MEM_VOLATILE_P (x))
1216         return 1;
1217     }
1218
1219   /* Recursively scan the operands of this expression.  */
1220
1221   {
1222     register char *fmt = GET_RTX_FORMAT (code);
1223     register int i;
1224
1225     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1226       {
1227         if (fmt[i] == 'e')
1228           {
1229             if (volatile_refs_p (XEXP (x, i)))
1230               return 1;
1231           }
1232         if (fmt[i] == 'E')
1233           {
1234             register int j;
1235             for (j = 0; j < XVECLEN (x, i); j++)
1236               if (volatile_refs_p (XVECEXP (x, i, j)))
1237                 return 1;
1238           }
1239       }
1240   }
1241   return 0;
1242 }
1243
1244 /* Similar to above, except that it also rejects register pre- and post-
1245    incrementing.  */
1246
1247 int
1248 side_effects_p (x)
1249      rtx x;
1250 {
1251   register RTX_CODE code;
1252
1253   code = GET_CODE (x);
1254   switch (code)
1255     {
1256     case LABEL_REF:
1257     case SYMBOL_REF:
1258     case CONST_INT:
1259     case CONST:
1260     case CONST_DOUBLE:
1261     case CC0:
1262     case PC:
1263     case REG:
1264     case SCRATCH:
1265     case ASM_INPUT:
1266     case ADDR_VEC:
1267     case ADDR_DIFF_VEC:
1268       return 0;
1269
1270     case CLOBBER:
1271       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
1272          when some combination can't be done.  If we see one, don't think
1273          that we can simplify the expression.  */
1274       return (GET_MODE (x) != VOIDmode);
1275
1276     case PRE_INC:
1277     case PRE_DEC:
1278     case POST_INC:
1279     case POST_DEC:
1280     case CALL:
1281     case UNSPEC_VOLATILE:
1282  /* case TRAP_IF: This isn't clear yet.  */
1283       return 1;
1284
1285     case MEM:
1286     case ASM_OPERANDS:
1287       if (MEM_VOLATILE_P (x))
1288         return 1;
1289     }
1290
1291   /* Recursively scan the operands of this expression.  */
1292
1293   {
1294     register char *fmt = GET_RTX_FORMAT (code);
1295     register int i;
1296
1297     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1298       {
1299         if (fmt[i] == 'e')
1300           {
1301             if (side_effects_p (XEXP (x, i)))
1302               return 1;
1303           }
1304         if (fmt[i] == 'E')
1305           {
1306             register int j;
1307             for (j = 0; j < XVECLEN (x, i); j++)
1308               if (side_effects_p (XVECEXP (x, i, j)))
1309                 return 1;
1310           }
1311       }
1312   }
1313   return 0;
1314 }
1315 \f
1316 /* Return nonzero if evaluating rtx X might cause a trap.  */
1317
1318 int
1319 may_trap_p (x)
1320      rtx x;
1321 {
1322   int i;
1323   enum rtx_code code;
1324   char *fmt;
1325
1326   if (x == 0)
1327     return 0;
1328   code = GET_CODE (x);
1329   switch (code)
1330     {
1331       /* Handle these cases quickly.  */
1332     case CONST_INT:
1333     case CONST_DOUBLE:
1334     case SYMBOL_REF:
1335     case LABEL_REF:
1336     case CONST:
1337     case PC:
1338     case CC0:
1339     case REG:
1340     case SCRATCH:
1341       return 0;
1342
1343       /* Conditional trap can trap!  */
1344     case UNSPEC_VOLATILE:
1345     case TRAP_IF:
1346       return 1;
1347
1348       /* Memory ref can trap unless it's a static var or a stack slot.  */
1349     case MEM:
1350       return rtx_addr_can_trap_p (XEXP (x, 0));
1351
1352       /* Division by a non-constant might trap.  */
1353     case DIV:
1354     case MOD:
1355     case UDIV:
1356     case UMOD:
1357       if (! CONSTANT_P (XEXP (x, 1)))
1358         return 1;
1359       /* This was const0_rtx, but by not using that,
1360          we can link this file into other programs.  */
1361       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
1362         return 1;
1363     default:
1364       /* Any floating arithmetic may trap.  */
1365       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
1366         return 1;
1367     }
1368
1369   fmt = GET_RTX_FORMAT (code);
1370   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1371     {
1372       if (fmt[i] == 'e')
1373         {
1374           if (may_trap_p (XEXP (x, i)))
1375             return 1;
1376         }
1377       else if (fmt[i] == 'E')
1378         {
1379           register int j;
1380           for (j = 0; j < XVECLEN (x, i); j++)
1381             if (may_trap_p (XVECEXP (x, i, j)))
1382               return 1;
1383         }
1384     }
1385   return 0;
1386 }
1387 \f
1388 /* Return nonzero if X contains a comparison that is not either EQ or NE,
1389    i.e., an inequality.  */
1390
1391 int
1392 inequality_comparisons_p (x)
1393      rtx x;
1394 {
1395   register char *fmt;
1396   register int len, i;
1397   register enum rtx_code code = GET_CODE (x);
1398
1399   switch (code)
1400     {
1401     case REG:
1402     case SCRATCH:
1403     case PC:
1404     case CC0:
1405     case CONST_INT:
1406     case CONST_DOUBLE:
1407     case CONST:
1408     case LABEL_REF:
1409     case SYMBOL_REF:
1410       return 0;
1411
1412     case LT:
1413     case LTU:
1414     case GT:
1415     case GTU:
1416     case LE:
1417     case LEU:
1418     case GE:
1419     case GEU:
1420       return 1;
1421     }
1422
1423   len = GET_RTX_LENGTH (code);
1424   fmt = GET_RTX_FORMAT (code);
1425
1426   for (i = 0; i < len; i++)
1427     {
1428       if (fmt[i] == 'e')
1429         {
1430           if (inequality_comparisons_p (XEXP (x, i)))
1431             return 1;
1432         }
1433       else if (fmt[i] == 'E')
1434         {
1435           register int j;
1436           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1437             if (inequality_comparisons_p (XVECEXP (x, i, j)))
1438               return 1;
1439         }
1440     }
1441
1442   return 0;
1443 }
1444 \f
1445 /* Replace any occurrence of FROM in X with TO.
1446
1447    Note that copying is not done so X must not be shared unless all copies
1448    are to be modified.  */
1449
1450 rtx
1451 replace_rtx (x, from, to)
1452      rtx x, from, to;
1453 {
1454   register int i, j;
1455   register char *fmt;
1456
1457   if (x == from)
1458     return to;
1459
1460   /* Allow this function to make replacements in EXPR_LISTs.  */
1461   if (x == 0)
1462     return 0;
1463
1464   fmt = GET_RTX_FORMAT (GET_CODE (x));
1465   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
1466     {
1467       if (fmt[i] == 'e')
1468         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
1469       else if (fmt[i] == 'E')
1470         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1471           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
1472     }
1473
1474   return x;
1475 }
1476 \f
1477 /* Throughout the rtx X, replace many registers according to REG_MAP.
1478    Return the replacement for X (which may be X with altered contents).
1479    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
1480    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
1481
1482    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
1483    should not be mapped to pseudos or vice versa since validate_change
1484    is not called.
1485
1486    If REPLACE_DEST is 1, replacements are also done in destinations;
1487    otherwise, only sources are replaced.  */
1488
1489 rtx
1490 replace_regs (x, reg_map, nregs, replace_dest)
1491      rtx x;
1492      rtx *reg_map;
1493      int nregs;
1494      int replace_dest;
1495 {
1496   register enum rtx_code code;
1497   register int i;
1498   register char *fmt;
1499
1500   if (x == 0)
1501     return x;
1502
1503   code = GET_CODE (x);
1504   switch (code)
1505     {
1506     case SCRATCH:
1507     case PC:
1508     case CC0:
1509     case CONST_INT:
1510     case CONST_DOUBLE:
1511     case CONST:
1512     case SYMBOL_REF:
1513     case LABEL_REF:
1514       return x;
1515
1516     case REG:
1517       /* Verify that the register has an entry before trying to access it.  */
1518       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
1519         return reg_map[REGNO (x)];
1520       return x;
1521
1522     case SUBREG:
1523       /* Prevent making nested SUBREGs.  */
1524       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
1525           && reg_map[REGNO (SUBREG_REG (x))] != 0
1526           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
1527         {
1528           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
1529           rtx map_inner = SUBREG_REG (map_val);
1530
1531           if (GET_MODE (x) == GET_MODE (map_inner))
1532             return map_inner;
1533           else
1534             {
1535               /* We cannot call gen_rtx here since we may be linked with
1536                  genattrtab.c.  */
1537               /* Let's try clobbering the incoming SUBREG and see
1538                  if this is really safe.  */
1539               SUBREG_REG (x) = map_inner;
1540               SUBREG_WORD (x) += SUBREG_WORD (map_val);
1541               return x;
1542 #if 0
1543               rtx new = rtx_alloc (SUBREG);
1544               PUT_MODE (new, GET_MODE (x));
1545               SUBREG_REG (new) = map_inner;
1546               SUBREG_WORD (new) = SUBREG_WORD (x) + SUBREG_WORD (map_val);
1547 #endif
1548             }
1549         }
1550       break;
1551
1552     case SET:
1553       if (replace_dest)
1554         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
1555
1556       else if (GET_CODE (SET_DEST (x)) == MEM
1557                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
1558         /* Even if we are not to replace destinations, replace register if it
1559            is CONTAINED in destination (destination is memory or
1560            STRICT_LOW_PART).  */
1561         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
1562                                                reg_map, nregs, 0);
1563       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
1564         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
1565         break;
1566
1567       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
1568       return x;
1569     }
1570
1571   fmt = GET_RTX_FORMAT (code);
1572   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1573     {
1574       if (fmt[i] == 'e')
1575         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
1576       if (fmt[i] == 'E')
1577         {
1578           register int j;
1579           for (j = 0; j < XVECLEN (x, i); j++)
1580             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
1581                                               nregs, replace_dest);
1582         }
1583     }
1584   return x;
1585 }