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