gcc/rtlanal.c

   1 /* Analyze RTL for C-Compiler
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   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
  23 #include "config.h"
  24 #include "system.h"
  25 #include "toplev.h"
  26 #include "rtl.h"
  27 #include "hard-reg-set.h"
  28
  29 /* Forward declarations */
  30 static void set_of_1            PARAMS ((rtx, rtx, void *));
  31 static void insn_dependent_p_1  PARAMS ((rtx, rtx, void *));
  32 static int computed_jump_p_1    PARAMS ((rtx));
  33 static int operand_preference   PARAMS ((rtx));
  34
  35 /* Bit flags that specify the machine subtype we are compiling for.
  36    Bits are tested using macros TARGET_... defined in the tm.h file
  37    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
  38
  39 int target_flags;
  40 \f
  41 /* Return 1 if the value of X is unstable
  42    (would be different at a different point in the program).
  43    The frame pointer, arg pointer, etc. are considered stable
  44    (within one function) and so is anything marked `unchanging'.  */
  45
  46 int
  47 rtx_unstable_p (x)
  48      rtx x;
  49 {
  50   register RTX_CODE code = GET_CODE (x);
  51   register int i;
  52   register const char *fmt;
  53
  54   switch (code)
  55     {
  56     case MEM:
  57       return ! RTX_UNCHANGING_P (x) || rtx_unstable_p (XEXP (x, 0));
  58
  59     case QUEUED:
  60       return 1;
  61
  62     case CONST:
  63     case CONST_INT:
  64     case CONST_DOUBLE:
  65     case SYMBOL_REF:
  66     case LABEL_REF:
  67       return 0;
  68
  69     case REG:
  70       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
  71       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
  72           /* The arg pointer varies if it is not a fixed register.  */
  73           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
  74           || RTX_UNCHANGING_P (x))
  75         return 0;
  76 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
  77       /* ??? When call-clobbered, the value is stable modulo the restore
  78          that must happen after a call.  This currently screws up local-alloc
  79          into believing that the restore is not needed.  */
  80       if (x == pic_offset_table_rtx)
  81         return 0;
  82 #endif
  83       return 1;
  84
  85     case ASM_OPERANDS:
  86       if (MEM_VOLATILE_P (x))
  87         return 1;
  88
  89       /* FALLTHROUGH */
  90
  91     default:
  92       break;
  93     }
  94
  95   fmt = GET_RTX_FORMAT (code);
  96   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  97     if (fmt[i] == 'e')
  98       {
  99         if (rtx_unstable_p (XEXP (x, i)))
 100           return 1;
 101       }
 102     else if (fmt[i] == 'E')
 103       {
 104         int j;
 105         for (j = 0; j < XVECLEN (x, i); j++)
 106           if (rtx_unstable_p (XVECEXP (x, i, j)))
 107             return 1;
 108       }
 109
 110   return 0;
 111 }
 112
 113 /* Return 1 if X has a value that can vary even between two
 114    executions of the program.  0 means X can be compared reliably
 115    against certain constants or near-constants.
 116    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 117    zero, we are slightly more conservative.
 118    The frame pointer and the arg pointer are considered constant.  */
 119
 120 int
 121 rtx_varies_p (x, for_alias)
 122      rtx x;
 123      int for_alias;
 124 {
 125   register RTX_CODE code = GET_CODE (x);
 126   register int i;
 127   register const char *fmt;
 128
 129   switch (code)
 130     {
 131     case MEM:
 132       return ! RTX_UNCHANGING_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
 133
 134     case QUEUED:
 135       return 1;
 136
 137     case CONST:
 138     case CONST_INT:
 139     case CONST_DOUBLE:
 140     case SYMBOL_REF:
 141     case LABEL_REF:
 142       return 0;
 143
 144     case REG:
 145       /* Note that we have to test for the actual rtx used for the frame
 146          and arg pointers and not just the register number in case we have
 147          eliminated the frame and/or arg pointer and are using it
 148          for pseudos.  */
 149       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 150           /* The arg pointer varies if it is not a fixed register.  */
 151           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 152         return 0;
 153       if (x == pic_offset_table_rtx
 154 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
 155           /* ??? When call-clobbered, the value is stable modulo the restore
 156              that must happen after a call.  This currently screws up
 157              local-alloc into believing that the restore is not needed, so we
 158              must return 0 only if we are called from alias analysis.  */
 159           && for_alias
 160 #endif
 161           )
 162         return 0;
 163       return 1;
 164
 165     case LO_SUM:
 166       /* The operand 0 of a LO_SUM is considered constant
 167          (in fact it is related specifically to operand 1)
 168          during alias analysis.  */
 169       return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
 170              || rtx_varies_p (XEXP (x, 1), for_alias);
 171
 172     case ASM_OPERANDS:
 173       if (MEM_VOLATILE_P (x))
 174         return 1;
 175
 176       /* FALLTHROUGH */
 177
 178     default:
 179       break;
 180     }
 181
 182   fmt = GET_RTX_FORMAT (code);
 183   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 184     if (fmt[i] == 'e')
 185       {
 186         if (rtx_varies_p (XEXP (x, i), for_alias))
 187           return 1;
 188       }
 189     else if (fmt[i] == 'E')
 190       {
 191         int j;
 192         for (j = 0; j < XVECLEN (x, i); j++)
 193           if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
 194             return 1;
 195       }
 196
 197   return 0;
 198 }
 199
 200 /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
 201
 202 int
 203 rtx_addr_can_trap_p (x)
 204      register rtx x;
 205 {
 206   register enum rtx_code code = GET_CODE (x);
 207
 208   switch (code)
 209     {
 210     case SYMBOL_REF:
 211       return SYMBOL_REF_WEAK (x);
 212
 213     case LABEL_REF:
 214       return 0;
 215
 216     case REG:
 217       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 218       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 219           || x == stack_pointer_rtx
 220           /* The arg pointer varies if it is not a fixed register.  */
 221           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 222         return 0;
 223       /* All of the virtual frame registers are stack references.  */
 224       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
 225           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
 226         return 0;
 227       return 1;
 228
 229     case CONST:
 230       return rtx_addr_can_trap_p (XEXP (x, 0));
 231
 232     case PLUS:
 233       /* An address is assumed not to trap if it is an address that can't
 234          trap plus a constant integer or it is the pic register plus a
 235          constant.  */
 236       return ! ((! rtx_addr_can_trap_p (XEXP (x, 0))
 237                  && GET_CODE (XEXP (x, 1)) == CONST_INT)
 238                 || (XEXP (x, 0) == pic_offset_table_rtx
 239                     && CONSTANT_P (XEXP (x, 1))));
 240
 241     case LO_SUM:
 242     case PRE_MODIFY:
 243       return rtx_addr_can_trap_p (XEXP (x, 1));
 244
 245     case PRE_DEC:
 246     case PRE_INC:
 247     case POST_DEC:
 248     case POST_INC:
 249     case POST_MODIFY:
 250       return rtx_addr_can_trap_p (XEXP (x, 0));
 251
 252     default:
 253       break;
 254     }
 255
 256   /* If it isn't one of the case above, it can cause a trap.  */
 257   return 1;
 258 }
 259
 260 /* Return 1 if X refers to a memory location whose address
 261    cannot be compared reliably with constant addresses,
 262    or if X refers to a BLKmode memory object.
 263    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 264    zero, we are slightly more conservative.  */
 265
 266 int
 267 rtx_addr_varies_p (x, for_alias)
 268      rtx x;
 269      int for_alias;
 270 {
 271   register enum rtx_code code;
 272   register int i;
 273   register const char *fmt;
 274
 275   if (x == 0)
 276     return 0;
 277
 278   code = GET_CODE (x);
 279   if (code == MEM)
 280     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
 281
 282   fmt = GET_RTX_FORMAT (code);
 283   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 284     if (fmt[i] == 'e')
 285       {
 286         if (rtx_addr_varies_p (XEXP (x, i), for_alias))
 287           return 1;
 288       }
 289     else if (fmt[i] == 'E')
 290       {
 291         int j;
 292         for (j = 0; j < XVECLEN (x, i); j++)
 293           if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
 294             return 1;
 295       }
 296   return 0;
 297 }
 298 \f
 299 /* Return the value of the integer term in X, if one is apparent;
 300    otherwise return 0.
 301    Only obvious integer terms are detected.
 302    This is used in cse.c with the `related_value' field.*/
 303
 304 HOST_WIDE_INT
 305 get_integer_term (x)
 306      rtx x;
 307 {
 308   if (GET_CODE (x) == CONST)
 309     x = XEXP (x, 0);
 310
 311   if (GET_CODE (x) == MINUS
 312       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 313     return - INTVAL (XEXP (x, 1));
 314   if (GET_CODE (x) == PLUS
 315       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 316     return INTVAL (XEXP (x, 1));
 317   return 0;
 318 }
 319
 320 /* If X is a constant, return the value sans apparent integer term;
 321    otherwise return 0.
 322    Only obvious integer terms are detected.  */
 323
 324 rtx
 325 get_related_value (x)
 326      rtx x;
 327 {
 328   if (GET_CODE (x) != CONST)
 329     return 0;
 330   x = XEXP (x, 0);
 331   if (GET_CODE (x) == PLUS
 332       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 333     return XEXP (x, 0);
 334   else if (GET_CODE (x) == MINUS
 335            && GET_CODE (XEXP (x, 1)) == CONST_INT)
 336     return XEXP (x, 0);
 337   return 0;
 338 }
 339 \f
 340 /* Return the number of places FIND appears within X.  If COUNT_DEST is
 341    zero, we do not count occurrences inside the destination of a SET.  */
 342
 343 int
 344 count_occurrences (x, find, count_dest)
 345      rtx x, find;
 346      int count_dest;
 347 {
 348   int i, j;
 349   enum rtx_code code;
 350   const char *format_ptr;
 351   int count;
 352
 353   if (x == find)
 354     return 1;
 355
 356   code = GET_CODE (x);
 357
 358   switch (code)
 359     {
 360     case REG:
 361     case CONST_INT:
 362     case CONST_DOUBLE:
 363     case SYMBOL_REF:
 364     case CODE_LABEL:
 365     case PC:
 366     case CC0:
 367       return 0;
 368
 369     case MEM:
 370       if (GET_CODE (find) == MEM && rtx_equal_p (x, find))
 371         return 1;
 372       break;
 373
 374     case SET:
 375       if (SET_DEST (x) == find && ! count_dest)
 376         return count_occurrences (SET_SRC (x), find, count_dest);
 377       break;
 378
 379     default:
 380       break;
 381     }
 382
 383   format_ptr = GET_RTX_FORMAT (code);
 384   count = 0;
 385
 386   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 387     {
 388       switch (*format_ptr++)
 389         {
 390         case 'e':
 391           count += count_occurrences (XEXP (x, i), find, count_dest);
 392           break;
 393
 394         case 'E':
 395           for (j = 0; j < XVECLEN (x, i); j++)
 396             count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
 397           break;
 398         }
 399     }
 400   return count;
 401 }
 402 \f
 403 /* Nonzero if register REG appears somewhere within IN.
 404    Also works if REG is not a register; in this case it checks
 405    for a subexpression of IN that is Lisp "equal" to REG.  */
 406
 407 int
 408 reg_mentioned_p (reg, in)
 409      register rtx reg, in;
 410 {
 411   register const char *fmt;
 412   register int i;
 413   register enum rtx_code code;
 414
 415   if (in == 0)
 416     return 0;
 417
 418   if (reg == in)
 419     return 1;
 420
 421   if (GET_CODE (in) == LABEL_REF)
 422     return reg == XEXP (in, 0);
 423
 424   code = GET_CODE (in);
 425
 426   switch (code)
 427     {
 428       /* Compare registers by number.  */
 429     case REG:
 430       return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
 431
 432       /* These codes have no constituent expressions
 433          and are unique.  */
 434     case SCRATCH:
 435     case CC0:
 436     case PC:
 437       return 0;
 438
 439     case CONST_INT:
 440       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
 441
 442     case CONST_DOUBLE:
 443       /* These are kept unique for a given value.  */
 444       return 0;
 445
 446     default:
 447       break;
 448     }
 449
 450   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
 451     return 1;
 452
 453   fmt = GET_RTX_FORMAT (code);
 454
 455   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 456     {
 457       if (fmt[i] == 'E')
 458         {
 459           register int j;
 460           for (j = XVECLEN (in, i) - 1; j >= 0; j--)
 461             if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
 462               return 1;
 463         }
 464       else if (fmt[i] == 'e'
 465                && reg_mentioned_p (reg, XEXP (in, i)))
 466         return 1;
 467     }
 468   return 0;
 469 }
 470 \f
 471 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 472    no CODE_LABEL insn.  */
 473
 474 int
 475 no_labels_between_p (beg, end)
 476      rtx beg, end;
 477 {
 478   register rtx p;
 479   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 480     if (GET_CODE (p) == CODE_LABEL)
 481       return 0;
 482   return 1;
 483 }
 484
 485 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 486    no JUMP_INSN insn.  */
 487
 488 int
 489 no_jumps_between_p (beg, end)
 490      rtx beg, end;
 491 {
 492   register rtx p;
 493   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 494     if (GET_CODE (p) == JUMP_INSN)
 495       return 0;
 496   return 1;
 497 }
 498
 499 /* Nonzero if register REG is used in an insn between
 500    FROM_INSN and TO_INSN (exclusive of those two).  */
 501
 502 int
 503 reg_used_between_p (reg, from_insn, to_insn)
 504      rtx reg, from_insn, to_insn;
 505 {
 506   register rtx insn;
 507
 508   if (from_insn == to_insn)
 509     return 0;
 510
 511   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 512     if (INSN_P (insn)
 513         && (reg_overlap_mentioned_p (reg, PATTERN (insn))
 514            || (GET_CODE (insn) == CALL_INSN
 515               && (find_reg_fusage (insn, USE, reg)
 516                   || find_reg_fusage (insn, CLOBBER, reg)))))
 517       return 1;
 518   return 0;
 519 }
 520 \f
 521 /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
 522    is entirely replaced by a new value and the only use is as a SET_DEST,
 523    we do not consider it a reference.  */
 524
 525 int
 526 reg_referenced_p (x, body)
 527      rtx x;
 528      rtx body;
 529 {
 530   int i;
 531
 532   switch (GET_CODE (body))
 533     {
 534     case SET:
 535       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
 536         return 1;
 537
 538       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
 539          of a REG that occupies all of the REG, the insn references X if
 540          it is mentioned in the destination.  */
 541       if (GET_CODE (SET_DEST (body)) != CC0
 542           && GET_CODE (SET_DEST (body)) != PC
 543           && GET_CODE (SET_DEST (body)) != REG
 544           && ! (GET_CODE (SET_DEST (body)) == SUBREG
 545                 && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG
 546                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
 547                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
 548                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
 549                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
 550           && reg_overlap_mentioned_p (x, SET_DEST (body)))
 551         return 1;
 552       return 0;
 553
 554     case ASM_OPERANDS:
 555       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
 556         if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
 557           return 1;
 558       return 0;
 559
 560     case CALL:
 561     case USE:
 562     case IF_THEN_ELSE:
 563       return reg_overlap_mentioned_p (x, body);
 564
 565     case TRAP_IF:
 566       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
 567
 568     case UNSPEC:
 569     case UNSPEC_VOLATILE:
 570       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 571         if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
 572           return 1;
 573       return 0;
 574
 575     case PARALLEL:
 576       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 577         if (reg_referenced_p (x, XVECEXP (body, 0, i)))
 578           return 1;
 579       return 0;
 580
 581     case CLOBBER:
 582       if (GET_CODE (XEXP (body, 0)) == MEM)
 583         if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
 584           return 1;
 585       return 0;
 586
 587     case COND_EXEC:
 588       if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
 589         return 1;
 590       return reg_referenced_p (x, COND_EXEC_CODE (body));
 591
 592     default:
 593       return 0;
 594     }
 595 }
 596
 597 /* Nonzero if register REG is referenced in an insn between
 598    FROM_INSN and TO_INSN (exclusive of those two).  Sets of REG do
 599    not count.  */
 600
 601 int
 602 reg_referenced_between_p (reg, from_insn, to_insn)
 603      rtx reg, from_insn, to_insn;
 604 {
 605   register rtx insn;
 606
 607   if (from_insn == to_insn)
 608     return 0;
 609
 610   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 611     if (INSN_P (insn)
 612         && (reg_referenced_p (reg, PATTERN (insn))
 613            || (GET_CODE (insn) == CALL_INSN
 614               && find_reg_fusage (insn, USE, reg))))
 615       return 1;
 616   return 0;
 617 }
 618 \f
 619 /* Nonzero if register REG is set or clobbered in an insn between
 620    FROM_INSN and TO_INSN (exclusive of those two).  */
 621
 622 int
 623 reg_set_between_p (reg, from_insn, to_insn)
 624      rtx reg, from_insn, to_insn;
 625 {
 626   register rtx insn;
 627
 628   if (from_insn == to_insn)
 629     return 0;
 630
 631   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 632     if (INSN_P (insn) && reg_set_p (reg, insn))
 633       return 1;
 634   return 0;
 635 }
 636
 637 /* Internals of reg_set_between_p.  */
 638 int
 639 reg_set_p (reg, insn)
 640      rtx reg, insn;
 641 {
 642   rtx body = insn;
 643
 644   /* We can be passed an insn or part of one.  If we are passed an insn,
 645      check if a side-effect of the insn clobbers REG.  */
 646   if (INSN_P (insn))
 647     {
 648       if (FIND_REG_INC_NOTE (insn, reg)
 649           || (GET_CODE (insn) == CALL_INSN
 650               /* We'd like to test call_used_regs here, but rtlanal.c can't
 651                  reference that variable due to its use in genattrtab.  So
 652                  we'll just be more conservative.
 653
 654                  ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE
 655                  information holds all clobbered registers.  */
 656               && ((GET_CODE (reg) == REG
 657                    && REGNO (reg) < FIRST_PSEUDO_REGISTER)
 658                   || GET_CODE (reg) == MEM
 659                   || find_reg_fusage (insn, CLOBBER, reg))))
 660         return 1;
 661
 662       body = PATTERN (insn);
 663     }
 664
 665   return set_of (reg, insn) != NULL_RTX;
 666 }
 667
 668 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 669    only if none of them are modified between START and END.  Do not
 670    consider non-registers one way or the other.  */
 671
 672 int
 673 regs_set_between_p (x, start, end)
 674      rtx x;
 675      rtx start, end;
 676 {
 677   enum rtx_code code = GET_CODE (x);
 678   const char *fmt;
 679   int i, j;
 680
 681   switch (code)
 682     {
 683     case CONST_INT:
 684     case CONST_DOUBLE:
 685     case CONST:
 686     case SYMBOL_REF:
 687     case LABEL_REF:
 688     case PC:
 689     case CC0:
 690       return 0;
 691
 692     case REG:
 693       return reg_set_between_p (x, start, end);
 694
 695     default:
 696       break;
 697     }
 698
 699   fmt = GET_RTX_FORMAT (code);
 700   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 701     {
 702       if (fmt[i] == 'e' && regs_set_between_p (XEXP (x, i), start, end))
 703         return 1;
 704
 705       else if (fmt[i] == 'E')
 706         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 707           if (regs_set_between_p (XVECEXP (x, i, j), start, end))
 708             return 1;
 709     }
 710
 711   return 0;
 712 }
 713
 714 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 715    only if none of them are modified between START and END.  Return 1 if
 716    X contains a MEM; this routine does not perform any memory aliasing.  */
 717
 718 int
 719 modified_between_p (x, start, end)
 720      rtx x;
 721      rtx start, end;
 722 {
 723   enum rtx_code code = GET_CODE (x);
 724   const char *fmt;
 725   int i, j;
 726
 727   switch (code)
 728     {
 729     case CONST_INT:
 730     case CONST_DOUBLE:
 731     case CONST:
 732     case SYMBOL_REF:
 733     case LABEL_REF:
 734       return 0;
 735
 736     case PC:
 737     case CC0:
 738       return 1;
 739
 740     case MEM:
 741       /* If the memory is not constant, assume it is modified.  If it is
 742          constant, we still have to check the address.  */
 743       if (! RTX_UNCHANGING_P (x))
 744         return 1;
 745       break;
 746
 747     case REG:
 748       return reg_set_between_p (x, start, end);
 749
 750     default:
 751       break;
 752     }
 753
 754   fmt = GET_RTX_FORMAT (code);
 755   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 756     {
 757       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
 758         return 1;
 759
 760       else if (fmt[i] == 'E')
 761         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 762           if (modified_between_p (XVECEXP (x, i, j), start, end))
 763             return 1;
 764     }
 765
 766   return 0;
 767 }
 768
 769 /* Similar to reg_set_p, but check all registers in X.  Return 0 only if none
 770    of them are modified in INSN.  Return 1 if X contains a MEM; this routine
 771    does not perform any memory aliasing.  */
 772
 773 int
 774 modified_in_p (x, insn)
 775      rtx x;
 776      rtx insn;
 777 {
 778   enum rtx_code code = GET_CODE (x);
 779   const char *fmt;
 780   int i, j;
 781
 782   switch (code)
 783     {
 784     case CONST_INT:
 785     case CONST_DOUBLE:
 786     case CONST:
 787     case SYMBOL_REF:
 788     case LABEL_REF:
 789       return 0;
 790
 791     case PC:
 792     case CC0:
 793       return 1;
 794
 795     case MEM:
 796       /* If the memory is not constant, assume it is modified.  If it is
 797          constant, we still have to check the address.  */
 798       if (! RTX_UNCHANGING_P (x))
 799         return 1;
 800       break;
 801
 802     case REG:
 803       return reg_set_p (x, insn);
 804
 805     default:
 806       break;
 807     }
 808
 809   fmt = GET_RTX_FORMAT (code);
 810   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 811     {
 812       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
 813         return 1;
 814
 815       else if (fmt[i] == 'E')
 816         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 817           if (modified_in_p (XVECEXP (x, i, j), insn))
 818             return 1;
 819     }
 820
 821   return 0;
 822 }
 823
 824 /* Return true if anything in insn X is (anti,output,true) dependent on
 825    anything in insn Y.  */
 826
 827 int
 828 insn_dependent_p (x, y)
 829      rtx x, y;
 830 {
 831   rtx tmp;
 832
 833   if (! INSN_P (x) || ! INSN_P (y))
 834     abort ();
 835
 836   tmp = PATTERN (y);
 837   note_stores (PATTERN (x), insn_dependent_p_1, &tmp);
 838   if (tmp == NULL_RTX)
 839     return 1;
 840
 841   tmp = PATTERN (x);
 842   note_stores (PATTERN (y), insn_dependent_p_1, &tmp);
 843   if (tmp == NULL_RTX)
 844     return 1;
 845
 846   return 0;
 847 }
 848
 849 /* A helper routine for insn_dependent_p called through note_stores.  */
 850
 851 static void
 852 insn_dependent_p_1 (x, pat, data)
 853      rtx x;
 854      rtx pat ATTRIBUTE_UNUSED;
 855      void *data;
 856 {
 857   rtx * pinsn = (rtx *) data;
 858
 859   if (*pinsn && reg_mentioned_p (x, *pinsn))
 860     *pinsn = NULL_RTX;
 861 }
 862 \f
 863 /* Helper function for set_of.  */
 864 struct set_of_data
 865   {
 866     rtx found;
 867     rtx pat;
 868   };
 869
 870 static void
 871 set_of_1 (x, pat, data1)
 872      rtx x;
 873      rtx pat;
 874      void *data1;
 875 {
 876    struct set_of_data *data = (struct set_of_data *) (data1);
 877    if (rtx_equal_p (x, data->pat)
 878        || (GET_CODE (x) != MEM && reg_overlap_mentioned_p (data->pat, x)))
 879      data->found = pat;
 880 }
 881
 882 /* Give an INSN, return a SET or CLOBBER expression that does modify PAT
 883    (eighter directly or via STRICT_LOW_PART and similar modifiers).  */
 884 rtx
 885 set_of (pat, insn)
 886      rtx pat, insn;
 887 {
 888   struct set_of_data data;
 889   data.found = NULL_RTX;
 890   data.pat = pat;
 891   note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
 892   return data.found;
 893 }
 894 \f
 895 /* Given an INSN, return a SET expression if this insn has only a single SET.
 896    It may also have CLOBBERs, USEs, or SET whose output
 897    will not be used, which we ignore.  */
 898
 899 rtx
 900 single_set_2 (insn, pat)
 901      rtx insn, pat;
 902 {
 903   rtx set = NULL;
 904   int set_verified = 1;
 905   int i;
 906
 907   if (GET_CODE (pat) == PARALLEL)
 908     {
 909       for (i = 0; i < XVECLEN (pat, 0); i++)
 910         {
 911           rtx sub = XVECEXP (pat, 0, i);
 912           switch (GET_CODE (sub))
 913             {
 914             case USE:
 915             case CLOBBER:
 916               break;
 917
 918             case SET:
 919               /* We can consider insns having multiple sets, where all
 920                  but one are dead as single set insns.  In common case
 921                  only single set is present in the pattern so we want
 922                  to avoid checking for REG_UNUSED notes unless neccesary.
 923
 924                  When we reach set first time, we just expect this is
 925                  the single set we are looking for and only when more
 926                  sets are found in the insn, we check them.  */
 927               if (!set_verified)
 928                 {
 929                   if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
 930                       && !side_effects_p (set))
 931                     set = NULL;
 932                   else
 933                     set_verified = 1;
 934                 }
 935               if (!set)
 936                 set = sub, set_verified = 0;
 937               else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
 938                        || side_effects_p (sub))
 939                 return NULL_RTX;
 940               break;
 941
 942             default:
 943               return NULL_RTX;
 944             }
 945         }
 946     }
 947   return set;
 948 }
 949
 950 /* Given an INSN, return nonzero if it has more than one SET, else return
 951    zero.  */
 952
 953 int
 954 multiple_sets (insn)
 955      rtx insn;
 956 {
 957   int found;
 958   int i;
 959
 960   /* INSN must be an insn.  */
 961   if (! INSN_P (insn))
 962     return 0;
 963
 964   /* Only a PARALLEL can have multiple SETs.  */
 965   if (GET_CODE (PATTERN (insn)) == PARALLEL)
 966     {
 967       for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
 968         if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
 969           {
 970             /* If we have already found a SET, then return now.  */
 971             if (found)
 972               return 1;
 973             else
 974               found = 1;
 975           }
 976     }
 977
 978   /* Either zero or one SET.  */
 979   return 0;
 980 }
 981 \f
 982 /* Return nonzero if the destination of SET equals the source
 983    and there are no side effects.  */
 984
 985 int
 986 set_noop_p (set)
 987      rtx set;
 988 {
 989   rtx src = SET_SRC (set);
 990   rtx dst = SET_DEST (set);
 991
 992   if (side_effects_p (src) || side_effects_p (dst))
 993     return 0;
 994
 995   if (GET_CODE (dst) == MEM && GET_CODE (src) == MEM)
 996     return rtx_equal_p (dst, src);
 997
 998   if (GET_CODE (dst) == SIGN_EXTRACT
 999       || GET_CODE (dst) == ZERO_EXTRACT)
1000     return rtx_equal_p (XEXP (dst, 0), src)
1001            && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx;
1002
1003   if (GET_CODE (dst) == STRICT_LOW_PART)
1004     dst = XEXP (dst, 0);
1005
1006   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1007     {
1008       if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1009         return 0;
1010       src = SUBREG_REG (src);
1011       dst = SUBREG_REG (dst);
1012     }
1013
1014   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
1015           && REGNO (src) == REGNO (dst));
1016 }
1017
1018 /* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
1019    is not NULL_RTX then verify that the object is not modified up to VALID_TO.
1020    If the object was modified, if we hit a partial assignment to X, or hit a
1021    CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
1022    point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
1023    be the src.  */
1024
1025 rtx
1026 find_last_value (x, pinsn, valid_to, allow_hwreg)
1027      rtx x;
1028      rtx *pinsn;
1029      rtx valid_to;
1030      int allow_hwreg;
1031 {
1032   rtx p;
1033
1034   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
1035        p = PREV_INSN (p))
1036     if (INSN_P (p))
1037       {
1038         rtx set = single_set (p);
1039         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
1040
1041         if (set && rtx_equal_p (x, SET_DEST (set)))
1042           {
1043             rtx src = SET_SRC (set);
1044
1045             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1046               src = XEXP (note, 0);
1047
1048             if ((valid_to == NULL_RTX
1049                  || ! modified_between_p (src, PREV_INSN (p), valid_to))
1050                 /* Reject hard registers because we don't usually want
1051                    to use them; we'd rather use a pseudo.  */
1052                 && (! (GET_CODE (src) == REG
1053                       && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
1054               {
1055                 *pinsn = p;
1056                 return src;
1057               }
1058           }
1059
1060         /* If set in non-simple way, we don't have a value.  */
1061         if (reg_set_p (x, p))
1062           break;
1063       }
1064
1065   return x;
1066 }
1067 \f
1068 /* Return nonzero if register in range [REGNO, ENDREGNO)
1069    appears either explicitly or implicitly in X
1070    other than being stored into.
1071
1072    References contained within the substructure at LOC do not count.
1073    LOC may be zero, meaning don't ignore anything.  */
1074
1075 int
1076 refers_to_regno_p (regno, endregno, x, loc)
1077      unsigned int regno, endregno;
1078      rtx x;
1079      rtx *loc;
1080 {
1081   int i;
1082   unsigned int x_regno;
1083   RTX_CODE code;
1084   const char *fmt;
1085
1086  repeat:
1087   /* The contents of a REG_NONNEG note is always zero, so we must come here
1088      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
1089   if (x == 0)
1090     return 0;
1091
1092   code = GET_CODE (x);
1093
1094   switch (code)
1095     {
1096     case REG:
1097       x_regno = REGNO (x);
1098
1099       /* If we modifying the stack, frame, or argument pointer, it will
1100          clobber a virtual register.  In fact, we could be more precise,
1101          but it isn't worth it.  */
1102       if ((x_regno == STACK_POINTER_REGNUM
1103 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1104            || x_regno == ARG_POINTER_REGNUM
1105 #endif
1106            || x_regno == FRAME_POINTER_REGNUM)
1107           && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1108         return 1;
1109
1110       return (endregno > x_regno
1111               && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
1112                                     ? HARD_REGNO_NREGS (x_regno, GET_MODE (x))
1113                               : 1));
1114
1115     case SUBREG:
1116       /* If this is a SUBREG of a hard reg, we can see exactly which
1117          registers are being modified.  Otherwise, handle normally.  */
1118       if (GET_CODE (SUBREG_REG (x)) == REG
1119           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1120         {
1121           unsigned int inner_regno = subreg_regno (x);
1122           unsigned int inner_endregno
1123             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1124                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1125
1126           return endregno > inner_regno && regno < inner_endregno;
1127         }
1128       break;
1129
1130     case CLOBBER:
1131     case SET:
1132       if (&SET_DEST (x) != loc
1133           /* Note setting a SUBREG counts as referring to the REG it is in for
1134              a pseudo but not for hard registers since we can
1135              treat each word individually.  */
1136           && ((GET_CODE (SET_DEST (x)) == SUBREG
1137                && loc != &SUBREG_REG (SET_DEST (x))
1138                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
1139                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1140                && refers_to_regno_p (regno, endregno,
1141                                      SUBREG_REG (SET_DEST (x)), loc))
1142               || (GET_CODE (SET_DEST (x)) != REG
1143                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1144         return 1;
1145
1146       if (code == CLOBBER || loc == &SET_SRC (x))
1147         return 0;
1148       x = SET_SRC (x);
1149       goto repeat;
1150
1151     default:
1152       break;
1153     }
1154
1155   /* X does not match, so try its subexpressions.  */
1156
1157   fmt = GET_RTX_FORMAT (code);
1158   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1159     {
1160       if (fmt[i] == 'e' && loc != &XEXP (x, i))
1161         {
1162           if (i == 0)
1163             {
1164               x = XEXP (x, 0);
1165               goto repeat;
1166             }
1167           else
1168             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1169               return 1;
1170         }
1171       else if (fmt[i] == 'E')
1172         {
1173           register int j;
1174           for (j = XVECLEN (x, i) - 1; j >=0; j--)
1175             if (loc != &XVECEXP (x, i, j)
1176                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1177               return 1;
1178         }
1179     }
1180   return 0;
1181 }
1182
1183 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
1184    we check if any register number in X conflicts with the relevant register
1185    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
1186    contains a MEM (we don't bother checking for memory addresses that can't
1187    conflict because we expect this to be a rare case.  */
1188
1189 int
1190 reg_overlap_mentioned_p (x, in)
1191      rtx x, in;
1192 {
1193   unsigned int regno, endregno;
1194
1195   /* Overly conservative.  */
1196   if (GET_CODE (x) == STRICT_LOW_PART)
1197     x = XEXP (x, 0);
1198
1199   /* If either argument is a constant, then modifying X can not affect IN.  */
1200   if (CONSTANT_P (x) || CONSTANT_P (in))
1201     return 0;
1202
1203   switch (GET_CODE (x))
1204     {
1205     case SUBREG:
1206       regno = REGNO (SUBREG_REG (x));
1207       if (regno < FIRST_PSEUDO_REGISTER)
1208         regno = subreg_regno (x);
1209       goto do_reg;
1210
1211     case REG:
1212       regno = REGNO (x);
1213     do_reg:
1214       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1215                           ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1216       return refers_to_regno_p (regno, endregno, in, (rtx*)0);
1217
1218     case MEM:
1219       {
1220         const char *fmt;
1221         int i;
1222
1223         if (GET_CODE (in) == MEM)
1224           return 1;
1225
1226         fmt = GET_RTX_FORMAT (GET_CODE (in));
1227         for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1228           if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
1229             return 1;
1230
1231         return 0;
1232       }
1233
1234     case SCRATCH:
1235     case PC:
1236     case CC0:
1237       return reg_mentioned_p (x, in);
1238
1239     case PARALLEL:
1240       {
1241         int i;
1242
1243         /* If any register in here refers to it we return true.  */
1244         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1245           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1246               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1247               return 1;
1248         return 0;
1249       }
1250
1251     default:
1252       break;
1253     }
1254
1255   abort ();
1256 }
1257 \f
1258 /* Return the last value to which REG was set prior to INSN.  If we can't
1259    find it easily, return 0.
1260
1261    We only return a REG, SUBREG, or constant because it is too hard to
1262    check if a MEM remains unchanged.  */
1263
1264 rtx
1265 reg_set_last (x, insn)
1266      rtx x;
1267      rtx insn;
1268 {
1269   rtx orig_insn = insn;
1270
1271   /* Scan backwards until reg_set_last_1 changed one of the above flags.
1272      Stop when we reach a label or X is a hard reg and we reach a
1273      CALL_INSN (if reg_set_last_last_regno is a hard reg).
1274
1275      If we find a set of X, ensure that its SET_SRC remains unchanged.  */
1276
1277   /* We compare with <= here, because reg_set_last_last_regno
1278      is actually the number of the first reg *not* in X.  */
1279   for (;
1280        insn && GET_CODE (insn) != CODE_LABEL
1281        && ! (GET_CODE (insn) == CALL_INSN
1282              && REGNO (x) <= FIRST_PSEUDO_REGISTER);
1283        insn = PREV_INSN (insn))
1284     if (INSN_P (insn))
1285       {
1286         rtx set = set_of (x, insn);
1287         /* OK, this function modify our register.  See if we understand it.  */
1288         if (set)
1289           {
1290             rtx last_value;
1291             if (GET_CODE (set) != SET || SET_DEST (set) != x)
1292               return 0;
1293             last_value = SET_SRC (x);
1294             if (CONSTANT_P (last_value)
1295                 || ((GET_CODE (last_value) == REG
1296                      || GET_CODE (last_value) == SUBREG)
1297                     && ! reg_set_between_p (last_value,
1298                                             insn, orig_insn)))
1299               return last_value;
1300             else
1301               return 0;
1302           }
1303       }
1304
1305   return 0;
1306 }
1307 \f
1308 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1309    (X would be the pattern of an insn).
1310    FUN receives two arguments:
1311      the REG, MEM, CC0 or PC being stored in or clobbered,
1312      the SET or CLOBBER rtx that does the store.
1313
1314   If the item being stored in or clobbered is a SUBREG of a hard register,
1315   the SUBREG will be passed.  */
1316
1317 void
1318 note_stores (x, fun, data)
1319      register rtx x;
1320      void (*fun) PARAMS ((rtx, rtx, void *));
1321      void *data;
1322 {
1323   int i;
1324
1325   if (GET_CODE (x) == COND_EXEC)
1326     x = COND_EXEC_CODE (x);
1327
1328   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1329     {
1330       register rtx dest = SET_DEST (x);
1331
1332       while ((GET_CODE (dest) == SUBREG
1333               && (GET_CODE (SUBREG_REG (dest)) != REG
1334                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1335              || GET_CODE (dest) == ZERO_EXTRACT
1336              || GET_CODE (dest) == SIGN_EXTRACT
1337              || GET_CODE (dest) == STRICT_LOW_PART)
1338         dest = XEXP (dest, 0);
1339
1340       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1341          each of whose first operand is a register.  We can't know what
1342          precisely is being set in these cases, so make up a CLOBBER to pass
1343          to the function.  */
1344       if (GET_CODE (dest) == PARALLEL)
1345         {
1346           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1347             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1348               (*fun) (XEXP (XVECEXP (dest, 0, i), 0),
1349                       gen_rtx_CLOBBER (VOIDmode,
1350                                        XEXP (XVECEXP (dest, 0, i), 0)),
1351                       data);
1352         }
1353       else
1354         (*fun) (dest, x, data);
1355     }
1356
1357   else if (GET_CODE (x) == PARALLEL)
1358     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1359       note_stores (XVECEXP (x, 0, i), fun, data);
1360 }
1361 \f
1362 /* Like notes_stores, but call FUN for each expression that is being
1363    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1364    FUN for each expression, not any interior subexpressions.  FUN receives a
1365    pointer to the expression and the DATA passed to this function.
1366
1367    Note that this is not quite the same test as that done in reg_referenced_p
1368    since that considers something as being referenced if it is being
1369    partially set, while we do not.  */
1370
1371 void
1372 note_uses (pbody, fun, data)
1373      rtx *pbody;
1374      void (*fun) PARAMS ((rtx *, void *));
1375      void *data;
1376 {
1377   rtx body = *pbody;
1378   int i;
1379
1380   switch (GET_CODE (body))
1381     {
1382     case COND_EXEC:
1383       (*fun) (&COND_EXEC_TEST (body), data);
1384       note_uses (&COND_EXEC_CODE (body), fun, data);
1385       return;
1386
1387     case PARALLEL:
1388       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1389         note_uses (&XVECEXP (body, 0, i), fun, data);
1390       return;
1391
1392     case USE:
1393       (*fun) (&XEXP (body, 0), data);
1394       return;
1395
1396     case ASM_OPERANDS:
1397       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1398         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1399       return;
1400
1401     case TRAP_IF:
1402       (*fun) (&TRAP_CONDITION (body), data);
1403       return;
1404
1405     case UNSPEC:
1406     case UNSPEC_VOLATILE:
1407       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1408         (*fun) (&XVECEXP (body, 0, i), data);
1409       return;
1410
1411     case CLOBBER:
1412       if (GET_CODE (XEXP (body, 0)) == MEM)
1413         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1414       return;
1415
1416     case SET:
1417       {
1418         rtx dest = SET_DEST (body);
1419
1420         /* For sets we replace everything in source plus registers in memory
1421            expression in store and operands of a ZERO_EXTRACT.  */
1422         (*fun) (&SET_SRC (body), data);
1423
1424         if (GET_CODE (dest) == ZERO_EXTRACT)
1425           {
1426             (*fun) (&XEXP (dest, 1), data);
1427             (*fun) (&XEXP (dest, 2), data);
1428           }
1429
1430         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1431           dest = XEXP (dest, 0);
1432
1433         if (GET_CODE (dest) == MEM)
1434           (*fun) (&XEXP (dest, 0), data);
1435       }
1436       return;
1437
1438     default:
1439       /* All the other possibilities never store.  */
1440       (*fun) (pbody, data);
1441       return;
1442     }
1443 }
1444 \f
1445 /* Return nonzero if X's old contents don't survive after INSN.
1446    This will be true if X is (cc0) or if X is a register and
1447    X dies in INSN or because INSN entirely sets X.
1448
1449    "Entirely set" means set directly and not through a SUBREG,
1450    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
1451    Likewise, REG_INC does not count.
1452
1453    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1454    but for this use that makes no difference, since regs don't overlap
1455    during their lifetimes.  Therefore, this function may be used
1456    at any time after deaths have been computed (in flow.c).
1457
1458    If REG is a hard reg that occupies multiple machine registers, this
1459    function will only return 1 if each of those registers will be replaced
1460    by INSN.  */
1461
1462 int
1463 dead_or_set_p (insn, x)
1464      rtx insn;
1465      rtx x;
1466 {
1467   unsigned int regno, last_regno;
1468   unsigned int i;
1469
1470   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1471   if (GET_CODE (x) == CC0)
1472     return 1;
1473
1474   if (GET_CODE (x) != REG)
1475     abort ();
1476
1477   regno = REGNO (x);
1478   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1479                 : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
1480
1481   for (i = regno; i <= last_regno; i++)
1482     if (! dead_or_set_regno_p (insn, i))
1483       return 0;
1484
1485   return 1;
1486 }
1487
1488 /* Utility function for dead_or_set_p to check an individual register.  Also
1489    called from flow.c.  */
1490
1491 int
1492 dead_or_set_regno_p (insn, test_regno)
1493      rtx insn;
1494      unsigned int test_regno;
1495 {
1496   unsigned int regno, endregno;
1497   rtx pattern;
1498
1499   /* See if there is a death note for something that includes TEST_REGNO.  */
1500   if (find_regno_note (insn, REG_DEAD, test_regno))
1501     return 1;
1502
1503   if (GET_CODE (insn) == CALL_INSN
1504       && find_regno_fusage (insn, CLOBBER, test_regno))
1505     return 1;
1506
1507   pattern = PATTERN (insn);
1508
1509   if (GET_CODE (pattern) == COND_EXEC)
1510     pattern = COND_EXEC_CODE (pattern);
1511
1512   if (GET_CODE (pattern) == SET)
1513     {
1514       rtx dest = SET_DEST (PATTERN (insn));
1515
1516       /* A value is totally replaced if it is the destination or the
1517          destination is a SUBREG of REGNO that does not change the number of
1518          words in it.  */
1519       if (GET_CODE (dest) == SUBREG
1520           && (((GET_MODE_SIZE (GET_MODE (dest))
1521                 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1522               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1523                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1524         dest = SUBREG_REG (dest);
1525
1526       if (GET_CODE (dest) != REG)
1527         return 0;
1528
1529       regno = REGNO (dest);
1530       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1531                   : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1532
1533       return (test_regno >= regno && test_regno < endregno);
1534     }
1535   else if (GET_CODE (pattern) == PARALLEL)
1536     {
1537       register int i;
1538
1539       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1540         {
1541           rtx body = XVECEXP (pattern, 0, i);
1542
1543           if (GET_CODE (body) == COND_EXEC)
1544             body = COND_EXEC_CODE (body);
1545
1546           if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1547             {
1548               rtx dest = SET_DEST (body);
1549
1550               if (GET_CODE (dest) == SUBREG
1551                   && (((GET_MODE_SIZE (GET_MODE (dest))
1552                         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1553                       == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1554                            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1555                 dest = SUBREG_REG (dest);
1556
1557               if (GET_CODE (dest) != REG)
1558                 continue;
1559
1560               regno = REGNO (dest);
1561               endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1562                           : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1563
1564               if (test_regno >= regno && test_regno < endregno)
1565                 return 1;
1566             }
1567         }
1568     }
1569
1570   return 0;
1571 }
1572
1573 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1574    If DATUM is nonzero, look for one whose datum is DATUM.  */
1575
1576 rtx
1577 find_reg_note (insn, kind, datum)
1578      rtx insn;
1579      enum reg_note kind;
1580      rtx datum;
1581 {
1582   register rtx link;
1583
1584   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1585   if (! INSN_P (insn))
1586     return 0;
1587
1588   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1589     if (REG_NOTE_KIND (link) == kind
1590         && (datum == 0 || datum == XEXP (link, 0)))
1591       return link;
1592   return 0;
1593 }
1594
1595 /* Return the reg-note of kind KIND in insn INSN which applies to register
1596    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1597    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1598    it might be the case that the note overlaps REGNO.  */
1599
1600 rtx
1601 find_regno_note (insn, kind, regno)
1602      rtx insn;
1603      enum reg_note kind;
1604      unsigned int regno;
1605 {
1606   register rtx link;
1607
1608   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1609   if (! INSN_P (insn))
1610     return 0;
1611
1612   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1613     if (REG_NOTE_KIND (link) == kind
1614         /* Verify that it is a register, so that scratch and MEM won't cause a
1615            problem here.  */
1616         && GET_CODE (XEXP (link, 0)) == REG
1617         && REGNO (XEXP (link, 0)) <= regno
1618         && ((REGNO (XEXP (link, 0))
1619              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1620                 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
1621                                     GET_MODE (XEXP (link, 0)))))
1622             > regno))
1623       return link;
1624   return 0;
1625 }
1626
1627 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1628    has such a note.  */
1629
1630 rtx
1631 find_reg_equal_equiv_note (insn)
1632      rtx insn;
1633 {
1634   rtx note;
1635
1636   if (single_set (insn) == 0)
1637     return 0;
1638   else if ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1639     return note;
1640   else
1641     return find_reg_note (insn, REG_EQUAL, NULL_RTX);
1642 }
1643
1644 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1645    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1646
1647 int
1648 find_reg_fusage (insn, code, datum)
1649      rtx insn;
1650      enum rtx_code code;
1651      rtx datum;
1652 {
1653   /* If it's not a CALL_INSN, it can't possibly have a
1654      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1655   if (GET_CODE (insn) != CALL_INSN)
1656     return 0;
1657
1658   if (! datum)
1659     abort();
1660
1661   if (GET_CODE (datum) != REG)
1662     {
1663       register rtx link;
1664
1665       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1666            link;
1667            link = XEXP (link, 1))
1668         if (GET_CODE (XEXP (link, 0)) == code
1669             && rtx_equal_p (datum, SET_DEST (XEXP (link, 0))))
1670           return 1;
1671     }
1672   else
1673     {
1674       unsigned int regno = REGNO (datum);
1675
1676       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1677          to pseudo registers, so don't bother checking.  */
1678
1679       if (regno < FIRST_PSEUDO_REGISTER)
1680         {
1681           unsigned int end_regno
1682             = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
1683           unsigned int i;
1684
1685           for (i = regno; i < end_regno; i++)
1686             if (find_regno_fusage (insn, code, i))
1687               return 1;
1688         }
1689     }
1690
1691   return 0;
1692 }
1693
1694 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1695    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1696
1697 int
1698 find_regno_fusage (insn, code, regno)
1699      rtx insn;
1700      enum rtx_code code;
1701      unsigned int regno;
1702 {
1703   register rtx link;
1704
1705   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1706      to pseudo registers, so don't bother checking.  */
1707
1708   if (regno >= FIRST_PSEUDO_REGISTER
1709       || GET_CODE (insn) != CALL_INSN )
1710     return 0;
1711
1712   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1713     {
1714       unsigned int regnote;
1715       rtx op, reg;
1716
1717       if (GET_CODE (op = XEXP (link, 0)) == code
1718           && GET_CODE (reg = XEXP (op, 0)) == REG
1719           && (regnote = REGNO (reg)) <= regno
1720           && regnote + HARD_REGNO_NREGS (regnote, GET_MODE (reg)) > regno)
1721         return 1;
1722     }
1723
1724   return 0;
1725 }
1726 \f
1727 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1728
1729 void
1730 remove_note (insn, note)
1731      register rtx insn;
1732      register rtx note;
1733 {
1734   register rtx link;
1735
1736   if (note == NULL_RTX)
1737     return;
1738
1739   if (REG_NOTES (insn) == note)
1740     {
1741       REG_NOTES (insn) = XEXP (note, 1);
1742       return;
1743     }
1744
1745   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1746     if (XEXP (link, 1) == note)
1747       {
1748         XEXP (link, 1) = XEXP (note, 1);
1749         return;
1750       }
1751
1752   abort ();
1753 }
1754
1755 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1756    remove that entry from the list if it is found.
1757
1758    A simple equality test is used to determine if NODE matches.  */
1759
1760 void
1761 remove_node_from_expr_list (node, listp)
1762      rtx node;
1763      rtx *listp;
1764 {
1765   rtx temp = *listp;
1766   rtx prev = NULL_RTX;
1767
1768   while (temp)
1769     {
1770       if (node == XEXP (temp, 0))
1771         {
1772           /* Splice the node out of the list.  */
1773           if (prev)
1774             XEXP (prev, 1) = XEXP (temp, 1);
1775           else
1776             *listp = XEXP (temp, 1);
1777
1778           return;
1779         }
1780
1781       prev = temp;
1782       temp = XEXP (temp, 1);
1783     }
1784 }
1785 \f
1786 /* Nonzero if X contains any volatile instructions.  These are instructions
1787    which may cause unpredictable machine state instructions, and thus no
1788    instructions should be moved or combined across them.  This includes
1789    only volatile asms and UNSPEC_VOLATILE instructions.  */
1790
1791 int
1792 volatile_insn_p (x)
1793      rtx x;
1794 {
1795   register RTX_CODE code;
1796
1797   code = GET_CODE (x);
1798   switch (code)
1799     {
1800     case LABEL_REF:
1801     case SYMBOL_REF:
1802     case CONST_INT:
1803     case CONST:
1804     case CONST_DOUBLE:
1805     case CC0:
1806     case PC:
1807     case REG:
1808     case SCRATCH:
1809     case CLOBBER:
1810     case ASM_INPUT:
1811     case ADDR_VEC:
1812     case ADDR_DIFF_VEC:
1813     case CALL:
1814     case MEM:
1815       return 0;
1816
1817     case UNSPEC_VOLATILE:
1818  /* case TRAP_IF: This isn't clear yet.  */
1819       return 1;
1820
1821     case ASM_OPERANDS:
1822       if (MEM_VOLATILE_P (x))
1823         return 1;
1824
1825     default:
1826       break;
1827     }
1828
1829   /* Recursively scan the operands of this expression.  */
1830
1831   {
1832     register const char *fmt = GET_RTX_FORMAT (code);
1833     register int i;
1834
1835     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1836       {
1837         if (fmt[i] == 'e')
1838           {
1839             if (volatile_insn_p (XEXP (x, i)))
1840               return 1;
1841           }
1842         else if (fmt[i] == 'E')
1843           {
1844             register int j;
1845             for (j = 0; j < XVECLEN (x, i); j++)
1846               if (volatile_insn_p (XVECEXP (x, i, j)))
1847                 return 1;
1848           }
1849       }
1850   }
1851   return 0;
1852 }
1853
1854 /* Nonzero if X contains any volatile memory references
1855    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1856
1857 int
1858 volatile_refs_p (x)
1859      rtx x;
1860 {
1861   register RTX_CODE code;
1862
1863   code = GET_CODE (x);
1864   switch (code)
1865     {
1866     case LABEL_REF:
1867     case SYMBOL_REF:
1868     case CONST_INT:
1869     case CONST:
1870     case CONST_DOUBLE:
1871     case CC0:
1872     case PC:
1873     case REG:
1874     case SCRATCH:
1875     case CLOBBER:
1876     case ASM_INPUT:
1877     case ADDR_VEC:
1878     case ADDR_DIFF_VEC:
1879       return 0;
1880
1881     case CALL:
1882     case UNSPEC_VOLATILE:
1883  /* case TRAP_IF: This isn't clear yet.  */
1884       return 1;
1885
1886     case MEM:
1887     case ASM_OPERANDS:
1888       if (MEM_VOLATILE_P (x))
1889         return 1;
1890
1891     default:
1892       break;
1893     }
1894
1895   /* Recursively scan the operands of this expression.  */
1896
1897   {
1898     register const char *fmt = GET_RTX_FORMAT (code);
1899     register int i;
1900
1901     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1902       {
1903         if (fmt[i] == 'e')
1904           {
1905             if (volatile_refs_p (XEXP (x, i)))
1906               return 1;
1907           }
1908         else if (fmt[i] == 'E')
1909           {
1910             register int j;
1911             for (j = 0; j < XVECLEN (x, i); j++)
1912               if (volatile_refs_p (XVECEXP (x, i, j)))
1913                 return 1;
1914           }
1915       }
1916   }
1917   return 0;
1918 }
1919
1920 /* Similar to above, except that it also rejects register pre- and post-
1921    incrementing.  */
1922
1923 int
1924 side_effects_p (x)
1925      rtx x;
1926 {
1927   register RTX_CODE code;
1928
1929   code = GET_CODE (x);
1930   switch (code)
1931     {
1932     case LABEL_REF:
1933     case SYMBOL_REF:
1934     case CONST_INT:
1935     case CONST:
1936     case CONST_DOUBLE:
1937     case CC0:
1938     case PC:
1939     case REG:
1940     case SCRATCH:
1941     case ASM_INPUT:
1942     case ADDR_VEC:
1943     case ADDR_DIFF_VEC:
1944       return 0;
1945
1946     case CLOBBER:
1947       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
1948          when some combination can't be done.  If we see one, don't think
1949          that we can simplify the expression.  */
1950       return (GET_MODE (x) != VOIDmode);
1951
1952     case PRE_INC:
1953     case PRE_DEC:
1954     case POST_INC:
1955     case POST_DEC:
1956     case PRE_MODIFY:
1957     case POST_MODIFY:
1958     case CALL:
1959     case UNSPEC_VOLATILE:
1960  /* case TRAP_IF: This isn't clear yet.  */
1961       return 1;
1962
1963     case MEM:
1964     case ASM_OPERANDS:
1965       if (MEM_VOLATILE_P (x))
1966         return 1;
1967
1968     default:
1969       break;
1970     }
1971
1972   /* Recursively scan the operands of this expression.  */
1973
1974   {
1975     register const char *fmt = GET_RTX_FORMAT (code);
1976     register int i;
1977
1978     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1979       {
1980         if (fmt[i] == 'e')
1981           {
1982             if (side_effects_p (XEXP (x, i)))
1983               return 1;
1984           }
1985         else if (fmt[i] == 'E')
1986           {
1987             register int j;
1988             for (j = 0; j < XVECLEN (x, i); j++)
1989               if (side_effects_p (XVECEXP (x, i, j)))
1990                 return 1;
1991           }
1992       }
1993   }
1994   return 0;
1995 }
1996 \f
1997 /* Return nonzero if evaluating rtx X might cause a trap.  */
1998
1999 int
2000 may_trap_p (x)
2001      rtx x;
2002 {
2003   int i;
2004   enum rtx_code code;
2005   const char *fmt;
2006
2007   if (x == 0)
2008     return 0;
2009   code = GET_CODE (x);
2010   switch (code)
2011     {
2012       /* Handle these cases quickly.  */
2013     case CONST_INT:
2014     case CONST_DOUBLE:
2015     case SYMBOL_REF:
2016     case LABEL_REF:
2017     case CONST:
2018     case PC:
2019     case CC0:
2020     case REG:
2021     case SCRATCH:
2022       return 0;
2023
2024     case ASM_INPUT:
2025     case UNSPEC_VOLATILE:
2026     case TRAP_IF:
2027       return 1;
2028
2029     case ASM_OPERANDS:
2030       return MEM_VOLATILE_P (x);
2031
2032       /* Memory ref can trap unless it's a static var or a stack slot.  */
2033     case MEM:
2034       return rtx_addr_can_trap_p (XEXP (x, 0));
2035
2036       /* Division by a non-constant might trap.  */
2037     case DIV:
2038     case MOD:
2039     case UDIV:
2040     case UMOD:
2041       if (! CONSTANT_P (XEXP (x, 1))
2042           || GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2043         return 1;
2044       /* This was const0_rtx, but by not using that,
2045          we can link this file into other programs.  */
2046       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
2047         return 1;
2048       break;
2049
2050     case EXPR_LIST:
2051       /* An EXPR_LIST is used to represent a function call.  This
2052          certainly may trap.  */
2053       return 1;
2054
2055     case GE:
2056     case GT:
2057     case LE:
2058     case LT:
2059     case COMPARE:
2060       /* Some floating point comparisons may trap.  */
2061       /* ??? There is no machine independent way to check for tests that trap
2062          when COMPARE is used, though many targets do make this distinction.
2063          For instance, sparc uses CCFPE for compares which generate exceptions
2064          and CCFP for compares which do not generate exceptions.  */
2065       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2066         return 1;
2067       /* But often the compare has some CC mode, so check operand
2068          modes as well.  */
2069       if (GET_MODE_CLASS (GET_MODE (XEXP (x, 0))) == MODE_FLOAT
2070           || GET_MODE_CLASS (GET_MODE (XEXP (x, 1))) == MODE_FLOAT)
2071         return 1;
2072       break;
2073
2074     case NEG:
2075     case ABS:
2076       /* These operations don't trap even with floating point.  */
2077       break;
2078
2079     default:
2080       /* Any floating arithmetic may trap.  */
2081       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2082         return 1;
2083     }
2084
2085   fmt = GET_RTX_FORMAT (code);
2086   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2087     {
2088       if (fmt[i] == 'e')
2089         {
2090           if (may_trap_p (XEXP (x, i)))
2091             return 1;
2092         }
2093       else if (fmt[i] == 'E')
2094         {
2095           register int j;
2096           for (j = 0; j < XVECLEN (x, i); j++)
2097             if (may_trap_p (XVECEXP (x, i, j)))
2098               return 1;
2099         }
2100     }
2101   return 0;
2102 }
2103 \f
2104 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2105    i.e., an inequality.  */
2106
2107 int
2108 inequality_comparisons_p (x)
2109      rtx x;
2110 {
2111   register const char *fmt;
2112   register int len, i;
2113   register enum rtx_code code = GET_CODE (x);
2114
2115   switch (code)
2116     {
2117     case REG:
2118     case SCRATCH:
2119     case PC:
2120     case CC0:
2121     case CONST_INT:
2122     case CONST_DOUBLE:
2123     case CONST:
2124     case LABEL_REF:
2125     case SYMBOL_REF:
2126       return 0;
2127
2128     case LT:
2129     case LTU:
2130     case GT:
2131     case GTU:
2132     case LE:
2133     case LEU:
2134     case GE:
2135     case GEU:
2136       return 1;
2137
2138     default:
2139       break;
2140     }
2141
2142   len = GET_RTX_LENGTH (code);
2143   fmt = GET_RTX_FORMAT (code);
2144
2145   for (i = 0; i < len; i++)
2146     {
2147       if (fmt[i] == 'e')
2148         {
2149           if (inequality_comparisons_p (XEXP (x, i)))
2150             return 1;
2151         }
2152       else if (fmt[i] == 'E')
2153         {
2154           register int j;
2155           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2156             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2157               return 1;
2158         }
2159     }
2160
2161   return 0;
2162 }
2163 \f
2164 /* Replace any occurrence of FROM in X with TO.  The function does
2165    not enter into CONST_DOUBLE for the replace.
2166
2167    Note that copying is not done so X must not be shared unless all copies
2168    are to be modified.  */
2169
2170 rtx
2171 replace_rtx (x, from, to)
2172      rtx x, from, to;
2173 {
2174   register int i, j;
2175   register const char *fmt;
2176
2177   /* The following prevents loops occurrence when we change MEM in
2178      CONST_DOUBLE onto the same CONST_DOUBLE. */
2179   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2180     return x;
2181
2182   if (x == from)
2183     return to;
2184
2185   /* Allow this function to make replacements in EXPR_LISTs.  */
2186   if (x == 0)
2187     return 0;
2188
2189   fmt = GET_RTX_FORMAT (GET_CODE (x));
2190   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2191     {
2192       if (fmt[i] == 'e')
2193         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2194       else if (fmt[i] == 'E')
2195         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2196           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2197     }
2198
2199   return x;
2200 }
2201 \f
2202 /* Throughout the rtx X, replace many registers according to REG_MAP.
2203    Return the replacement for X (which may be X with altered contents).
2204    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2205    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2206
2207    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2208    should not be mapped to pseudos or vice versa since validate_change
2209    is not called.
2210
2211    If REPLACE_DEST is 1, replacements are also done in destinations;
2212    otherwise, only sources are replaced.  */
2213
2214 rtx
2215 replace_regs (x, reg_map, nregs, replace_dest)
2216      rtx x;
2217      rtx *reg_map;
2218      unsigned int nregs;
2219      int replace_dest;
2220 {
2221   register enum rtx_code code;
2222   register int i;
2223   register const char *fmt;
2224
2225   if (x == 0)
2226     return x;
2227
2228   code = GET_CODE (x);
2229   switch (code)
2230     {
2231     case SCRATCH:
2232     case PC:
2233     case CC0:
2234     case CONST_INT:
2235     case CONST_DOUBLE:
2236     case CONST:
2237     case SYMBOL_REF:
2238     case LABEL_REF:
2239       return x;
2240
2241     case REG:
2242       /* Verify that the register has an entry before trying to access it.  */
2243       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2244         {
2245           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2246              this replacement occurs more than once then each instance will
2247              get distinct rtx.  */
2248           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2249             return copy_rtx (reg_map[REGNO (x)]);
2250           return reg_map[REGNO (x)];
2251         }
2252       return x;
2253
2254     case SUBREG:
2255       /* Prevent making nested SUBREGs.  */
2256       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
2257           && reg_map[REGNO (SUBREG_REG (x))] != 0
2258           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2259         {
2260           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2261           rtx map_inner = SUBREG_REG (map_val);
2262
2263           if (GET_MODE (x) == GET_MODE (map_inner))
2264             return map_inner;
2265           else
2266             {
2267               int final_offset = SUBREG_BYTE (x) + SUBREG_BYTE (map_val);
2268
2269               /* When working with REG SUBREGs the rule is that the byte
2270                  offset must be a multiple of the SUBREG's mode.  */
2271               final_offset = (final_offset / GET_MODE_SIZE (GET_MODE (x)));
2272               final_offset = (final_offset * GET_MODE_SIZE (GET_MODE (x)));
2273
2274               /* We cannot call gen_rtx here since we may be linked with
2275                  genattrtab.c.  */
2276               /* Let's try clobbering the incoming SUBREG and see
2277                  if this is really safe.  */
2278               SUBREG_REG (x) = map_inner;
2279               SUBREG_BYTE (x) = final_offset;
2280               return x;
2281 #if 0
2282               rtx new = rtx_alloc (SUBREG);
2283               int final_offset = SUBREG_BYTE (x) + SUBREG_BYTE (map_val);
2284
2285               /* When working with REG SUBREGs the rule is that the byte
2286                  offset must be a multiple of the SUBREG's mode.  */
2287               final_offset = (final_offset / GET_MODE_SIZE (GET_MODE (x)));
2288               final_offset = (final_offset * GET_MODE_SIZE (GET_MODE (x)));
2289
2290               PUT_MODE (new, GET_MODE (x));
2291               SUBREG_REG (new) = map_inner;
2292               SUBREG_BYTE (new) = final_offset;
2293 #endif
2294             }
2295         }
2296       break;
2297
2298     case SET:
2299       if (replace_dest)
2300         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2301
2302       else if (GET_CODE (SET_DEST (x)) == MEM
2303                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2304         /* Even if we are not to replace destinations, replace register if it
2305            is CONTAINED in destination (destination is memory or
2306            STRICT_LOW_PART).  */
2307         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2308                                                reg_map, nregs, 0);
2309       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2310         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2311         break;
2312
2313       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2314       return x;
2315
2316     default:
2317       break;
2318     }
2319
2320   fmt = GET_RTX_FORMAT (code);
2321   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2322     {
2323       if (fmt[i] == 'e')
2324         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2325       else if (fmt[i] == 'E')
2326         {
2327           register int j;
2328           for (j = 0; j < XVECLEN (x, i); j++)
2329             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2330                                               nregs, replace_dest);
2331         }
2332     }
2333   return x;
2334 }
2335
2336 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2337    constant that is not in the constant pool and not in the condition
2338    of an IF_THEN_ELSE.  */
2339
2340 static int
2341 computed_jump_p_1 (x)
2342      rtx x;
2343 {
2344   enum rtx_code code = GET_CODE (x);
2345   int i, j;
2346   const char *fmt;
2347
2348   switch (code)
2349     {
2350     case LABEL_REF:
2351     case PC:
2352       return 0;
2353
2354     case CONST:
2355     case CONST_INT:
2356     case CONST_DOUBLE:
2357     case SYMBOL_REF:
2358     case REG:
2359       return 1;
2360
2361     case MEM:
2362       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2363                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2364
2365     case IF_THEN_ELSE:
2366       return (computed_jump_p_1 (XEXP (x, 1))
2367               || computed_jump_p_1 (XEXP (x, 2)));
2368
2369     default:
2370       break;
2371     }
2372
2373   fmt = GET_RTX_FORMAT (code);
2374   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2375     {
2376       if (fmt[i] == 'e'
2377           && computed_jump_p_1 (XEXP (x, i)))
2378         return 1;
2379
2380       else if (fmt[i] == 'E')
2381         for (j = 0; j < XVECLEN (x, i); j++)
2382           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2383             return 1;
2384     }
2385
2386   return 0;
2387 }
2388
2389 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2390
2391    Tablejumps and casesi insns are not considered indirect jumps;
2392    we can recognize them by a (use (label_ref)).  */
2393
2394 int
2395 computed_jump_p (insn)
2396      rtx insn;
2397 {
2398   int i;
2399   if (GET_CODE (insn) == JUMP_INSN)
2400     {
2401       rtx pat = PATTERN (insn);
2402
2403       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2404         return 0;
2405       else if (GET_CODE (pat) == PARALLEL)
2406         {
2407           int len = XVECLEN (pat, 0);
2408           int has_use_labelref = 0;
2409
2410           for (i = len - 1; i >= 0; i--)
2411             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2412                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2413                     == LABEL_REF))
2414               has_use_labelref = 1;
2415
2416           if (! has_use_labelref)
2417             for (i = len - 1; i >= 0; i--)
2418               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2419                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2420                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2421                 return 1;
2422         }
2423       else if (GET_CODE (pat) == SET
2424                && SET_DEST (pat) == pc_rtx
2425                && computed_jump_p_1 (SET_SRC (pat)))
2426         return 1;
2427     }
2428   return 0;
2429 }
2430
2431 /* Traverse X via depth-first search, calling F for each
2432    sub-expression (including X itself).  F is also passed the DATA.
2433    If F returns -1, do not traverse sub-expressions, but continue
2434    traversing the rest of the tree.  If F ever returns any other
2435    non-zero value, stop the traversal, and return the value returned
2436    by F.  Otherwise, return 0.  This function does not traverse inside
2437    tree structure that contains RTX_EXPRs, or into sub-expressions
2438    whose format code is `0' since it is not known whether or not those
2439    codes are actually RTL.
2440
2441    This routine is very general, and could (should?) be used to
2442    implement many of the other routines in this file.  */
2443
2444 int
2445 for_each_rtx (x, f, data)
2446      rtx *x;
2447      rtx_function f;
2448      void *data;
2449 {
2450   int result;
2451   int length;
2452   const char* format;
2453   int i;
2454
2455   /* Call F on X.  */
2456   result = (*f)(x, data);
2457   if (result == -1)
2458     /* Do not traverse sub-expressions.  */
2459     return 0;
2460   else if (result != 0)
2461     /* Stop the traversal.  */
2462     return result;
2463
2464   if (*x == NULL_RTX)
2465     /* There are no sub-expressions.  */
2466     return 0;
2467
2468   length = GET_RTX_LENGTH (GET_CODE (*x));
2469   format = GET_RTX_FORMAT (GET_CODE (*x));
2470
2471   for (i = 0; i < length; ++i)
2472     {
2473       switch (format[i])
2474         {
2475         case 'e':
2476           result = for_each_rtx (&XEXP (*x, i), f, data);
2477           if (result != 0)
2478             return result;
2479           break;
2480
2481         case 'V':
2482         case 'E':
2483           if (XVEC (*x, i) != 0)
2484             {
2485               int j;
2486               for (j = 0; j < XVECLEN (*x, i); ++j)
2487                 {
2488                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
2489                   if (result != 0)
2490                     return result;
2491                 }
2492             }
2493           break;
2494
2495         default:
2496           /* Nothing to do.  */
2497           break;
2498         }
2499
2500     }
2501
2502   return 0;
2503 }
2504
2505 /* Searches X for any reference to REGNO, returning the rtx of the
2506    reference found if any.  Otherwise, returns NULL_RTX.  */
2507
2508 rtx
2509 regno_use_in (regno, x)
2510      unsigned int regno;
2511      rtx x;
2512 {
2513   register const char *fmt;
2514   int i, j;
2515   rtx tem;
2516
2517   if (GET_CODE (x) == REG && REGNO (x) == regno)
2518     return x;
2519
2520   fmt = GET_RTX_FORMAT (GET_CODE (x));
2521   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2522     {
2523       if (fmt[i] == 'e')
2524         {
2525           if ((tem = regno_use_in (regno, XEXP (x, i))))
2526             return tem;
2527         }
2528       else if (fmt[i] == 'E')
2529         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2530           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2531             return tem;
2532     }
2533
2534   return NULL_RTX;
2535 }
2536
2537 /* Return a value indicating whether OP, an operand of a commutative
2538    operation, is preferred as the first or second operand.  The higher
2539    the value, the stronger the preference for being the first operand.
2540    We use negative values to indicate a preference for the first operand
2541    and positive values for the second operand.  */
2542
2543 static int
2544 operand_preference (op)
2545      rtx op;
2546 {
2547   /* Constants always come the second operand.  Prefer "nice" constants.  */
2548   if (GET_CODE (op) == CONST_INT)
2549     return -4;
2550   if (GET_CODE (op) == CONST_DOUBLE)
2551     return -3;
2552   if (CONSTANT_P (op))
2553     return -2;
2554
2555   /* SUBREGs of objects should come second.  */
2556   if (GET_CODE (op) == SUBREG
2557       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
2558     return -1;
2559
2560   /* If only one operand is a `neg', `not',
2561     `mult', `plus', or `minus' expression, it will be the first
2562     operand.  */
2563   if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
2564       || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
2565       || GET_CODE (op) == MINUS)
2566     return 2;
2567
2568   /* Complex expressions should be the first.  */
2569   if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
2570     return 1;
2571   return 0;
2572 }
2573
2574 /* Return 1 iff it is neccesary to swap operands of commutative operation
2575    in order to canonicalize expression.  */
2576
2577 int
2578 swap_commutative_operands_p (x, y)
2579      rtx x, y;
2580 {
2581   return operand_preference (x) < operand_preference (y);
2582 }
2583
2584 /* Return 1 if X is an autoincrement side effect and the register is
2585    not the stack pointer.  */
2586 int
2587 auto_inc_p (x)
2588      rtx x;
2589 {
2590   switch (GET_CODE (x))
2591     {
2592     case PRE_INC:
2593     case POST_INC:
2594     case PRE_DEC:
2595     case POST_DEC:
2596     case PRE_MODIFY:
2597     case POST_MODIFY:
2598       /* There are no REG_INC notes for SP.  */
2599       if (XEXP (x, 0) != stack_pointer_rtx)
2600         return 1;
2601     default:
2602       break;
2603     }
2604   return 0;
2605 }
2606
2607 /* Return 1 if the sequence of instructions beginning with FROM and up
2608    to and including TO is safe to move.  If NEW_TO is non-NULL, and
2609    the sequence is not already safe to move, but can be easily
2610    extended to a sequence which is safe, then NEW_TO will point to the
2611    end of the extended sequence.
2612
2613    For now, this function only checks that the region contains whole
2614    exception regions, but it could be extended to check additional
2615    conditions as well.  */
2616
2617 int
2618 insns_safe_to_move_p (from, to, new_to)
2619      rtx from;
2620      rtx to;
2621      rtx *new_to;
2622 {
2623   int eh_region_count = 0;
2624   int past_to_p = 0;
2625   rtx r = from;
2626
2627   /* By default, assume the end of the region will be what was
2628      suggested.  */
2629   if (new_to)
2630     *new_to = to;
2631
2632   while (r)
2633     {
2634       if (GET_CODE (r) == NOTE)
2635         {
2636           switch (NOTE_LINE_NUMBER (r))
2637             {
2638             case NOTE_INSN_EH_REGION_BEG:
2639               ++eh_region_count;
2640               break;
2641
2642             case NOTE_INSN_EH_REGION_END:
2643               if (eh_region_count == 0)
2644                 /* This sequence of instructions contains the end of
2645                    an exception region, but not he beginning.  Moving
2646                    it will cause chaos.  */
2647                 return 0;
2648
2649               --eh_region_count;
2650               break;
2651
2652             default:
2653               break;
2654             }
2655         }
2656       else if (past_to_p)
2657         /* If we've passed TO, and we see a non-note instruction, we
2658            can't extend the sequence to a movable sequence.  */
2659         return 0;
2660
2661       if (r == to)
2662         {
2663           if (!new_to)
2664             /* It's OK to move the sequence if there were matched sets of
2665                exception region notes.  */
2666             return eh_region_count == 0;
2667
2668           past_to_p = 1;
2669         }
2670
2671       /* It's OK to move the sequence if there were matched sets of
2672          exception region notes.  */
2673       if (past_to_p && eh_region_count == 0)
2674         {
2675           *new_to = r;
2676           return 1;
2677         }
2678
2679       /* Go to the next instruction.  */
2680       r = NEXT_INSN (r);
2681     }
2682
2683   return 0;
2684 }
2685
2686 /* Return non-zero if IN contains a piece of rtl that has the address LOC */
2687 int
2688 loc_mentioned_in_p (loc, in)
2689      rtx *loc, in;
2690 {
2691   enum rtx_code code = GET_CODE (in);
2692   const char *fmt = GET_RTX_FORMAT (code);
2693   int i, j;
2694
2695   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2696     {
2697       if (loc == &in->fld[i].rtx)
2698         return 1;
2699       if (fmt[i] == 'e')
2700         {
2701           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2702             return 1;
2703         }
2704       else if (fmt[i] == 'E')
2705         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2706           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2707             return 1;
2708     }
2709   return 0;
2710 }
2711
2712 /* This function returns the regno offset of a subreg expression.
2713    xregno - A regno of an inner hard subreg_reg (or what will become one).
2714    xmode  - The mode of xregno.
2715    offset - The byte offset.
2716    ymode  - The mode of a top level SUBREG (or what may become one).
2717    RETURN - The regno offset which would be used.
2718    This function can be overridden by defining SUBREG_REGNO_OFFSET,
2719    taking the same parameters.  */
2720 unsigned int
2721 subreg_regno_offset (xregno, xmode, offset, ymode)
2722      unsigned int xregno;
2723      enum machine_mode xmode;
2724      unsigned int offset;
2725      enum machine_mode ymode;
2726 {
2727   unsigned ret;
2728   int nregs_xmode, nregs_ymode;
2729   int mode_multiple, nregs_multiple;
2730   int y_offset;
2731
2732 /* Check for an override, and use it instead.  */
2733 #ifdef SUBREG_REGNO_OFFSET
2734   ret = SUBREG_REGNO_OFFSET (xregno, xmode, offset, ymode)
2735 #else
2736   if (xregno >= FIRST_PSEUDO_REGISTER)
2737     abort ();
2738
2739   nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
2740   nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
2741   if (offset == 0 || nregs_xmode == nregs_ymode)
2742     return 0;
2743
2744   /* size of ymode must not be greater than the size of xmode.  */
2745   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
2746   if (mode_multiple == 0)
2747     abort ();
2748
2749   y_offset = offset / GET_MODE_SIZE (ymode);
2750   nregs_multiple =  nregs_xmode / nregs_ymode;
2751   ret = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
2752 #endif
2753
2754   return ret;
2755 }
2756
2757 /* Return the final regno that a subreg expression refers to. */
2758 unsigned int
2759 subreg_regno (x)
2760      rtx x;
2761 {
2762   unsigned int ret;
2763   rtx subreg = SUBREG_REG (x);
2764   int regno = REGNO (subreg);
2765
2766   ret = regno + subreg_regno_offset (regno,
2767                                      GET_MODE (subreg),
2768                                      SUBREG_BYTE (x),
2769                                      GET_MODE (x));
2770   return ret;
2771
2772 }