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 (GET_CODE (dst) == SIGN_EXTRACT
1002       || GET_CODE (dst) == ZERO_EXTRACT)
1003     return rtx_equal_p (XEXP (dst, 0), src)
1004            && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx;
1005
1006   if (GET_CODE (dst) == STRICT_LOW_PART)
1007     dst = XEXP (dst, 0);
1008
1009   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1010     {
1011       if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1012         return 0;
1013       src = SUBREG_REG (src);
1014       dst = SUBREG_REG (dst);
1015     }
1016
1017   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
1018           && REGNO (src) == REGNO (dst));
1019 }
1020
1021 /* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
1022    is not NULL_RTX then verify that the object is not modified up to VALID_TO.
1023    If the object was modified, if we hit a partial assignment to X, or hit a
1024    CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
1025    point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
1026    be the src.  */
1027
1028 rtx
1029 find_last_value (x, pinsn, valid_to, allow_hwreg)
1030      rtx x;
1031      rtx *pinsn;
1032      rtx valid_to;
1033      int allow_hwreg;
1034 {
1035   rtx p;
1036
1037   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
1038        p = PREV_INSN (p))
1039     if (INSN_P (p))
1040       {
1041         rtx set = single_set (p);
1042         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
1043
1044         if (set && rtx_equal_p (x, SET_DEST (set)))
1045           {
1046             rtx src = SET_SRC (set);
1047
1048             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1049               src = XEXP (note, 0);
1050
1051             if ((valid_to == NULL_RTX
1052                  || ! modified_between_p (src, PREV_INSN (p), valid_to))
1053                 /* Reject hard registers because we don't usually want
1054                    to use them; we'd rather use a pseudo.  */
1055                 && (! (GET_CODE (src) == REG
1056                       && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
1057               {
1058                 *pinsn = p;
1059                 return src;
1060               }
1061           }
1062
1063         /* If set in non-simple way, we don't have a value.  */
1064         if (reg_set_p (x, p))
1065           break;
1066       }
1067
1068   return x;
1069 }
1070 \f
1071 /* Return nonzero if register in range [REGNO, ENDREGNO)
1072    appears either explicitly or implicitly in X
1073    other than being stored into.
1074
1075    References contained within the substructure at LOC do not count.
1076    LOC may be zero, meaning don't ignore anything.  */
1077
1078 int
1079 refers_to_regno_p (regno, endregno, x, loc)
1080      unsigned int regno, endregno;
1081      rtx x;
1082      rtx *loc;
1083 {
1084   int i;
1085   unsigned int x_regno;
1086   RTX_CODE code;
1087   const char *fmt;
1088
1089  repeat:
1090   /* The contents of a REG_NONNEG note is always zero, so we must come here
1091      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
1092   if (x == 0)
1093     return 0;
1094
1095   code = GET_CODE (x);
1096
1097   switch (code)
1098     {
1099     case REG:
1100       x_regno = REGNO (x);
1101
1102       /* If we modifying the stack, frame, or argument pointer, it will
1103          clobber a virtual register.  In fact, we could be more precise,
1104          but it isn't worth it.  */
1105       if ((x_regno == STACK_POINTER_REGNUM
1106 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1107            || x_regno == ARG_POINTER_REGNUM
1108 #endif
1109            || x_regno == FRAME_POINTER_REGNUM)
1110           && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1111         return 1;
1112
1113       return (endregno > x_regno
1114               && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
1115                                     ? HARD_REGNO_NREGS (x_regno, GET_MODE (x))
1116                               : 1));
1117
1118     case SUBREG:
1119       /* If this is a SUBREG of a hard reg, we can see exactly which
1120          registers are being modified.  Otherwise, handle normally.  */
1121       if (GET_CODE (SUBREG_REG (x)) == REG
1122           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1123         {
1124           unsigned int inner_regno = subreg_regno (x);
1125           unsigned int inner_endregno
1126             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1127                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1128
1129           return endregno > inner_regno && regno < inner_endregno;
1130         }
1131       break;
1132
1133     case CLOBBER:
1134     case SET:
1135       if (&SET_DEST (x) != loc
1136           /* Note setting a SUBREG counts as referring to the REG it is in for
1137              a pseudo but not for hard registers since we can
1138              treat each word individually.  */
1139           && ((GET_CODE (SET_DEST (x)) == SUBREG
1140                && loc != &SUBREG_REG (SET_DEST (x))
1141                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
1142                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1143                && refers_to_regno_p (regno, endregno,
1144                                      SUBREG_REG (SET_DEST (x)), loc))
1145               || (GET_CODE (SET_DEST (x)) != REG
1146                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1147         return 1;
1148
1149       if (code == CLOBBER || loc == &SET_SRC (x))
1150         return 0;
1151       x = SET_SRC (x);
1152       goto repeat;
1153
1154     default:
1155       break;
1156     }
1157
1158   /* X does not match, so try its subexpressions.  */
1159
1160   fmt = GET_RTX_FORMAT (code);
1161   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1162     {
1163       if (fmt[i] == 'e' && loc != &XEXP (x, i))
1164         {
1165           if (i == 0)
1166             {
1167               x = XEXP (x, 0);
1168               goto repeat;
1169             }
1170           else
1171             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1172               return 1;
1173         }
1174       else if (fmt[i] == 'E')
1175         {
1176           register int j;
1177           for (j = XVECLEN (x, i) - 1; j >=0; j--)
1178             if (loc != &XVECEXP (x, i, j)
1179                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1180               return 1;
1181         }
1182     }
1183   return 0;
1184 }
1185
1186 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
1187    we check if any register number in X conflicts with the relevant register
1188    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
1189    contains a MEM (we don't bother checking for memory addresses that can't
1190    conflict because we expect this to be a rare case.  */
1191
1192 int
1193 reg_overlap_mentioned_p (x, in)
1194      rtx x, in;
1195 {
1196   unsigned int regno, endregno;
1197
1198   /* Overly conservative.  */
1199   if (GET_CODE (x) == STRICT_LOW_PART)
1200     x = XEXP (x, 0);
1201
1202   /* If either argument is a constant, then modifying X can not affect IN.  */
1203   if (CONSTANT_P (x) || CONSTANT_P (in))
1204     return 0;
1205
1206   switch (GET_CODE (x))
1207     {
1208     case SUBREG:
1209       regno = REGNO (SUBREG_REG (x));
1210       if (regno < FIRST_PSEUDO_REGISTER)
1211         regno = subreg_regno (x);
1212       goto do_reg;
1213
1214     case REG:
1215       regno = REGNO (x);
1216     do_reg:
1217       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1218                           ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1219       return refers_to_regno_p (regno, endregno, in, (rtx*)0);
1220
1221     case MEM:
1222       {
1223         const char *fmt;
1224         int i;
1225
1226         if (GET_CODE (in) == MEM)
1227           return 1;
1228
1229         fmt = GET_RTX_FORMAT (GET_CODE (in));
1230         for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1231           if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
1232             return 1;
1233
1234         return 0;
1235       }
1236
1237     case SCRATCH:
1238     case PC:
1239     case CC0:
1240       return reg_mentioned_p (x, in);
1241
1242     case PARALLEL:
1243       {
1244         int i;
1245
1246         /* If any register in here refers to it we return true.  */
1247         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1248           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1249               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1250               return 1;
1251         return 0;
1252       }
1253
1254     default:
1255       break;
1256     }
1257
1258   abort ();
1259 }
1260 \f
1261 /* Return the last value to which REG was set prior to INSN.  If we can't
1262    find it easily, return 0.
1263
1264    We only return a REG, SUBREG, or constant because it is too hard to
1265    check if a MEM remains unchanged.  */
1266
1267 rtx
1268 reg_set_last (x, insn)
1269      rtx x;
1270      rtx insn;
1271 {
1272   rtx orig_insn = insn;
1273
1274   /* Scan backwards until reg_set_last_1 changed one of the above flags.
1275      Stop when we reach a label or X is a hard reg and we reach a
1276      CALL_INSN (if reg_set_last_last_regno is a hard reg).
1277
1278      If we find a set of X, ensure that its SET_SRC remains unchanged.  */
1279
1280   /* We compare with <= here, because reg_set_last_last_regno
1281      is actually the number of the first reg *not* in X.  */
1282   for (;
1283        insn && GET_CODE (insn) != CODE_LABEL
1284        && ! (GET_CODE (insn) == CALL_INSN
1285              && REGNO (x) <= FIRST_PSEUDO_REGISTER);
1286        insn = PREV_INSN (insn))
1287     if (INSN_P (insn))
1288       {
1289         rtx set = set_of (x, insn);
1290         /* OK, this function modify our register.  See if we understand it.  */
1291         if (set)
1292           {
1293             rtx last_value;
1294             if (GET_CODE (set) != SET || SET_DEST (set) != x)
1295               return 0;
1296             last_value = SET_SRC (x);
1297             if (CONSTANT_P (last_value)
1298                 || ((GET_CODE (last_value) == REG
1299                      || GET_CODE (last_value) == SUBREG)
1300                     && ! reg_set_between_p (last_value,
1301                                             insn, orig_insn)))
1302               return last_value;
1303             else
1304               return 0;
1305           }
1306       }
1307
1308   return 0;
1309 }
1310 \f
1311 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1312    (X would be the pattern of an insn).
1313    FUN receives two arguments:
1314      the REG, MEM, CC0 or PC being stored in or clobbered,
1315      the SET or CLOBBER rtx that does the store.
1316
1317   If the item being stored in or clobbered is a SUBREG of a hard register,
1318   the SUBREG will be passed.  */
1319
1320 void
1321 note_stores (x, fun, data)
1322      register rtx x;
1323      void (*fun) PARAMS ((rtx, rtx, void *));
1324      void *data;
1325 {
1326   int i;
1327
1328   if (GET_CODE (x) == COND_EXEC)
1329     x = COND_EXEC_CODE (x);
1330
1331   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1332     {
1333       register rtx dest = SET_DEST (x);
1334
1335       while ((GET_CODE (dest) == SUBREG
1336               && (GET_CODE (SUBREG_REG (dest)) != REG
1337                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1338              || GET_CODE (dest) == ZERO_EXTRACT
1339              || GET_CODE (dest) == SIGN_EXTRACT
1340              || GET_CODE (dest) == STRICT_LOW_PART)
1341         dest = XEXP (dest, 0);
1342
1343       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1344          each of whose first operand is a register.  We can't know what
1345          precisely is being set in these cases, so make up a CLOBBER to pass
1346          to the function.  */
1347       if (GET_CODE (dest) == PARALLEL)
1348         {
1349           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1350             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1351               (*fun) (XEXP (XVECEXP (dest, 0, i), 0),
1352                       gen_rtx_CLOBBER (VOIDmode,
1353                                        XEXP (XVECEXP (dest, 0, i), 0)),
1354                       data);
1355         }
1356       else
1357         (*fun) (dest, x, data);
1358     }
1359
1360   else if (GET_CODE (x) == PARALLEL)
1361     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1362       note_stores (XVECEXP (x, 0, i), fun, data);
1363 }
1364 \f
1365 /* Like notes_stores, but call FUN for each expression that is being
1366    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1367    FUN for each expression, not any interior subexpressions.  FUN receives a
1368    pointer to the expression and the DATA passed to this function.
1369
1370    Note that this is not quite the same test as that done in reg_referenced_p
1371    since that considers something as being referenced if it is being
1372    partially set, while we do not.  */
1373
1374 void
1375 note_uses (pbody, fun, data)
1376      rtx *pbody;
1377      void (*fun) PARAMS ((rtx *, void *));
1378      void *data;
1379 {
1380   rtx body = *pbody;
1381   int i;
1382
1383   switch (GET_CODE (body))
1384     {
1385     case COND_EXEC:
1386       (*fun) (&COND_EXEC_TEST (body), data);
1387       note_uses (&COND_EXEC_CODE (body), fun, data);
1388       return;
1389
1390     case PARALLEL:
1391       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1392         note_uses (&XVECEXP (body, 0, i), fun, data);
1393       return;
1394
1395     case USE:
1396       (*fun) (&XEXP (body, 0), data);
1397       return;
1398
1399     case ASM_OPERANDS:
1400       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1401         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1402       return;
1403
1404     case TRAP_IF:
1405       (*fun) (&TRAP_CONDITION (body), data);
1406       return;
1407
1408     case UNSPEC:
1409     case UNSPEC_VOLATILE:
1410       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1411         (*fun) (&XVECEXP (body, 0, i), data);
1412       return;
1413
1414     case CLOBBER:
1415       if (GET_CODE (XEXP (body, 0)) == MEM)
1416         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1417       return;
1418
1419     case SET:
1420       {
1421         rtx dest = SET_DEST (body);
1422
1423         /* For sets we replace everything in source plus registers in memory
1424            expression in store and operands of a ZERO_EXTRACT.  */
1425         (*fun) (&SET_SRC (body), data);
1426
1427         if (GET_CODE (dest) == ZERO_EXTRACT)
1428           {
1429             (*fun) (&XEXP (dest, 1), data);
1430             (*fun) (&XEXP (dest, 2), data);
1431           }
1432
1433         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1434           dest = XEXP (dest, 0);
1435
1436         if (GET_CODE (dest) == MEM)
1437           (*fun) (&XEXP (dest, 0), data);
1438       }
1439       return;
1440
1441     default:
1442       /* All the other possibilities never store.  */
1443       (*fun) (pbody, data);
1444       return;
1445     }
1446 }
1447 \f
1448 /* Return nonzero if X's old contents don't survive after INSN.
1449    This will be true if X is (cc0) or if X is a register and
1450    X dies in INSN or because INSN entirely sets X.
1451
1452    "Entirely set" means set directly and not through a SUBREG,
1453    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
1454    Likewise, REG_INC does not count.
1455
1456    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1457    but for this use that makes no difference, since regs don't overlap
1458    during their lifetimes.  Therefore, this function may be used
1459    at any time after deaths have been computed (in flow.c).
1460
1461    If REG is a hard reg that occupies multiple machine registers, this
1462    function will only return 1 if each of those registers will be replaced
1463    by INSN.  */
1464
1465 int
1466 dead_or_set_p (insn, x)
1467      rtx insn;
1468      rtx x;
1469 {
1470   unsigned int regno, last_regno;
1471   unsigned int i;
1472
1473   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1474   if (GET_CODE (x) == CC0)
1475     return 1;
1476
1477   if (GET_CODE (x) != REG)
1478     abort ();
1479
1480   regno = REGNO (x);
1481   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1482                 : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
1483
1484   for (i = regno; i <= last_regno; i++)
1485     if (! dead_or_set_regno_p (insn, i))
1486       return 0;
1487
1488   return 1;
1489 }
1490
1491 /* Utility function for dead_or_set_p to check an individual register.  Also
1492    called from flow.c.  */
1493
1494 int
1495 dead_or_set_regno_p (insn, test_regno)
1496      rtx insn;
1497      unsigned int test_regno;
1498 {
1499   unsigned int regno, endregno;
1500   rtx pattern;
1501
1502   /* See if there is a death note for something that includes TEST_REGNO.  */
1503   if (find_regno_note (insn, REG_DEAD, test_regno))
1504     return 1;
1505
1506   if (GET_CODE (insn) == CALL_INSN
1507       && find_regno_fusage (insn, CLOBBER, test_regno))
1508     return 1;
1509
1510   pattern = PATTERN (insn);
1511
1512   if (GET_CODE (pattern) == COND_EXEC)
1513     pattern = COND_EXEC_CODE (pattern);
1514
1515   if (GET_CODE (pattern) == SET)
1516     {
1517       rtx dest = SET_DEST (PATTERN (insn));
1518
1519       /* A value is totally replaced if it is the destination or the
1520          destination is a SUBREG of REGNO that does not change the number of
1521          words in it.  */
1522       if (GET_CODE (dest) == SUBREG
1523           && (((GET_MODE_SIZE (GET_MODE (dest))
1524                 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1525               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1526                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1527         dest = SUBREG_REG (dest);
1528
1529       if (GET_CODE (dest) != REG)
1530         return 0;
1531
1532       regno = REGNO (dest);
1533       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1534                   : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1535
1536       return (test_regno >= regno && test_regno < endregno);
1537     }
1538   else if (GET_CODE (pattern) == PARALLEL)
1539     {
1540       register int i;
1541
1542       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1543         {
1544           rtx body = XVECEXP (pattern, 0, i);
1545
1546           if (GET_CODE (body) == COND_EXEC)
1547             body = COND_EXEC_CODE (body);
1548
1549           if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1550             {
1551               rtx dest = SET_DEST (body);
1552
1553               if (GET_CODE (dest) == SUBREG
1554                   && (((GET_MODE_SIZE (GET_MODE (dest))
1555                         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1556                       == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1557                            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1558                 dest = SUBREG_REG (dest);
1559
1560               if (GET_CODE (dest) != REG)
1561                 continue;
1562
1563               regno = REGNO (dest);
1564               endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1565                           : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1566
1567               if (test_regno >= regno && test_regno < endregno)
1568                 return 1;
1569             }
1570         }
1571     }
1572
1573   return 0;
1574 }
1575
1576 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1577    If DATUM is nonzero, look for one whose datum is DATUM.  */
1578
1579 rtx
1580 find_reg_note (insn, kind, datum)
1581      rtx insn;
1582      enum reg_note kind;
1583      rtx datum;
1584 {
1585   register rtx link;
1586
1587   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1588   if (! INSN_P (insn))
1589     return 0;
1590
1591   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1592     if (REG_NOTE_KIND (link) == kind
1593         && (datum == 0 || datum == XEXP (link, 0)))
1594       return link;
1595   return 0;
1596 }
1597
1598 /* Return the reg-note of kind KIND in insn INSN which applies to register
1599    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1600    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1601    it might be the case that the note overlaps REGNO.  */
1602
1603 rtx
1604 find_regno_note (insn, kind, regno)
1605      rtx insn;
1606      enum reg_note kind;
1607      unsigned int regno;
1608 {
1609   register rtx link;
1610
1611   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1612   if (! INSN_P (insn))
1613     return 0;
1614
1615   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1616     if (REG_NOTE_KIND (link) == kind
1617         /* Verify that it is a register, so that scratch and MEM won't cause a
1618            problem here.  */
1619         && GET_CODE (XEXP (link, 0)) == REG
1620         && REGNO (XEXP (link, 0)) <= regno
1621         && ((REGNO (XEXP (link, 0))
1622              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1623                 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
1624                                     GET_MODE (XEXP (link, 0)))))
1625             > regno))
1626       return link;
1627   return 0;
1628 }
1629
1630 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1631    has such a note.  */
1632
1633 rtx
1634 find_reg_equal_equiv_note (insn)
1635      rtx insn;
1636 {
1637   rtx note;
1638
1639   if (single_set (insn) == 0)
1640     return 0;
1641   else if ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1642     return note;
1643   else
1644     return find_reg_note (insn, REG_EQUAL, NULL_RTX);
1645 }
1646
1647 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1648    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1649
1650 int
1651 find_reg_fusage (insn, code, datum)
1652      rtx insn;
1653      enum rtx_code code;
1654      rtx datum;
1655 {
1656   /* If it's not a CALL_INSN, it can't possibly have a
1657      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1658   if (GET_CODE (insn) != CALL_INSN)
1659     return 0;
1660
1661   if (! datum)
1662     abort();
1663
1664   if (GET_CODE (datum) != REG)
1665     {
1666       register rtx link;
1667
1668       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1669            link;
1670            link = XEXP (link, 1))
1671         if (GET_CODE (XEXP (link, 0)) == code
1672             && rtx_equal_p (datum, SET_DEST (XEXP (link, 0))))
1673           return 1;
1674     }
1675   else
1676     {
1677       unsigned int regno = REGNO (datum);
1678
1679       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1680          to pseudo registers, so don't bother checking.  */
1681
1682       if (regno < FIRST_PSEUDO_REGISTER)
1683         {
1684           unsigned int end_regno
1685             = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
1686           unsigned int i;
1687
1688           for (i = regno; i < end_regno; i++)
1689             if (find_regno_fusage (insn, code, i))
1690               return 1;
1691         }
1692     }
1693
1694   return 0;
1695 }
1696
1697 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1698    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1699
1700 int
1701 find_regno_fusage (insn, code, regno)
1702      rtx insn;
1703      enum rtx_code code;
1704      unsigned int regno;
1705 {
1706   register rtx link;
1707
1708   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1709      to pseudo registers, so don't bother checking.  */
1710
1711   if (regno >= FIRST_PSEUDO_REGISTER
1712       || GET_CODE (insn) != CALL_INSN )
1713     return 0;
1714
1715   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1716     {
1717       unsigned int regnote;
1718       rtx op, reg;
1719
1720       if (GET_CODE (op = XEXP (link, 0)) == code
1721           && GET_CODE (reg = XEXP (op, 0)) == REG
1722           && (regnote = REGNO (reg)) <= regno
1723           && regnote + HARD_REGNO_NREGS (regnote, GET_MODE (reg)) > regno)
1724         return 1;
1725     }
1726
1727   return 0;
1728 }
1729 \f
1730 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1731
1732 void
1733 remove_note (insn, note)
1734      register rtx insn;
1735      register rtx note;
1736 {
1737   register rtx link;
1738
1739   if (note == NULL_RTX)
1740     return;
1741
1742   if (REG_NOTES (insn) == note)
1743     {
1744       REG_NOTES (insn) = XEXP (note, 1);
1745       return;
1746     }
1747
1748   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1749     if (XEXP (link, 1) == note)
1750       {
1751         XEXP (link, 1) = XEXP (note, 1);
1752         return;
1753       }
1754
1755   abort ();
1756 }
1757
1758 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1759    remove that entry from the list if it is found.
1760
1761    A simple equality test is used to determine if NODE matches.  */
1762
1763 void
1764 remove_node_from_expr_list (node, listp)
1765      rtx node;
1766      rtx *listp;
1767 {
1768   rtx temp = *listp;
1769   rtx prev = NULL_RTX;
1770
1771   while (temp)
1772     {
1773       if (node == XEXP (temp, 0))
1774         {
1775           /* Splice the node out of the list.  */
1776           if (prev)
1777             XEXP (prev, 1) = XEXP (temp, 1);
1778           else
1779             *listp = XEXP (temp, 1);
1780
1781           return;
1782         }
1783
1784       prev = temp;
1785       temp = XEXP (temp, 1);
1786     }
1787 }
1788 \f
1789 /* Nonzero if X contains any volatile instructions.  These are instructions
1790    which may cause unpredictable machine state instructions, and thus no
1791    instructions should be moved or combined across them.  This includes
1792    only volatile asms and UNSPEC_VOLATILE instructions.  */
1793
1794 int
1795 volatile_insn_p (x)
1796      rtx x;
1797 {
1798   register RTX_CODE code;
1799
1800   code = GET_CODE (x);
1801   switch (code)
1802     {
1803     case LABEL_REF:
1804     case SYMBOL_REF:
1805     case CONST_INT:
1806     case CONST:
1807     case CONST_DOUBLE:
1808     case CC0:
1809     case PC:
1810     case REG:
1811     case SCRATCH:
1812     case CLOBBER:
1813     case ASM_INPUT:
1814     case ADDR_VEC:
1815     case ADDR_DIFF_VEC:
1816     case CALL:
1817     case MEM:
1818       return 0;
1819
1820     case UNSPEC_VOLATILE:
1821  /* case TRAP_IF: This isn't clear yet.  */
1822       return 1;
1823
1824     case ASM_OPERANDS:
1825       if (MEM_VOLATILE_P (x))
1826         return 1;
1827
1828     default:
1829       break;
1830     }
1831
1832   /* Recursively scan the operands of this expression.  */
1833
1834   {
1835     register const char *fmt = GET_RTX_FORMAT (code);
1836     register int i;
1837
1838     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1839       {
1840         if (fmt[i] == 'e')
1841           {
1842             if (volatile_insn_p (XEXP (x, i)))
1843               return 1;
1844           }
1845         else if (fmt[i] == 'E')
1846           {
1847             register int j;
1848             for (j = 0; j < XVECLEN (x, i); j++)
1849               if (volatile_insn_p (XVECEXP (x, i, j)))
1850                 return 1;
1851           }
1852       }
1853   }
1854   return 0;
1855 }
1856
1857 /* Nonzero if X contains any volatile memory references
1858    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1859
1860 int
1861 volatile_refs_p (x)
1862      rtx x;
1863 {
1864   register RTX_CODE code;
1865
1866   code = GET_CODE (x);
1867   switch (code)
1868     {
1869     case LABEL_REF:
1870     case SYMBOL_REF:
1871     case CONST_INT:
1872     case CONST:
1873     case CONST_DOUBLE:
1874     case CC0:
1875     case PC:
1876     case REG:
1877     case SCRATCH:
1878     case CLOBBER:
1879     case ASM_INPUT:
1880     case ADDR_VEC:
1881     case ADDR_DIFF_VEC:
1882       return 0;
1883
1884     case CALL:
1885     case UNSPEC_VOLATILE:
1886  /* case TRAP_IF: This isn't clear yet.  */
1887       return 1;
1888
1889     case MEM:
1890     case ASM_OPERANDS:
1891       if (MEM_VOLATILE_P (x))
1892         return 1;
1893
1894     default:
1895       break;
1896     }
1897
1898   /* Recursively scan the operands of this expression.  */
1899
1900   {
1901     register const char *fmt = GET_RTX_FORMAT (code);
1902     register int i;
1903
1904     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1905       {
1906         if (fmt[i] == 'e')
1907           {
1908             if (volatile_refs_p (XEXP (x, i)))
1909               return 1;
1910           }
1911         else if (fmt[i] == 'E')
1912           {
1913             register int j;
1914             for (j = 0; j < XVECLEN (x, i); j++)
1915               if (volatile_refs_p (XVECEXP (x, i, j)))
1916                 return 1;
1917           }
1918       }
1919   }
1920   return 0;
1921 }
1922
1923 /* Similar to above, except that it also rejects register pre- and post-
1924    incrementing.  */
1925
1926 int
1927 side_effects_p (x)
1928      rtx x;
1929 {
1930   register RTX_CODE code;
1931
1932   code = GET_CODE (x);
1933   switch (code)
1934     {
1935     case LABEL_REF:
1936     case SYMBOL_REF:
1937     case CONST_INT:
1938     case CONST:
1939     case CONST_DOUBLE:
1940     case CC0:
1941     case PC:
1942     case REG:
1943     case SCRATCH:
1944     case ASM_INPUT:
1945     case ADDR_VEC:
1946     case ADDR_DIFF_VEC:
1947       return 0;
1948
1949     case CLOBBER:
1950       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
1951          when some combination can't be done.  If we see one, don't think
1952          that we can simplify the expression.  */
1953       return (GET_MODE (x) != VOIDmode);
1954
1955     case PRE_INC:
1956     case PRE_DEC:
1957     case POST_INC:
1958     case POST_DEC:
1959     case PRE_MODIFY:
1960     case POST_MODIFY:
1961     case CALL:
1962     case UNSPEC_VOLATILE:
1963  /* case TRAP_IF: This isn't clear yet.  */
1964       return 1;
1965
1966     case MEM:
1967     case ASM_OPERANDS:
1968       if (MEM_VOLATILE_P (x))
1969         return 1;
1970
1971     default:
1972       break;
1973     }
1974
1975   /* Recursively scan the operands of this expression.  */
1976
1977   {
1978     register const char *fmt = GET_RTX_FORMAT (code);
1979     register int i;
1980
1981     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1982       {
1983         if (fmt[i] == 'e')
1984           {
1985             if (side_effects_p (XEXP (x, i)))
1986               return 1;
1987           }
1988         else if (fmt[i] == 'E')
1989           {
1990             register int j;
1991             for (j = 0; j < XVECLEN (x, i); j++)
1992               if (side_effects_p (XVECEXP (x, i, j)))
1993                 return 1;
1994           }
1995       }
1996   }
1997   return 0;
1998 }
1999 \f
2000 /* Return nonzero if evaluating rtx X might cause a trap.  */
2001
2002 int
2003 may_trap_p (x)
2004      rtx x;
2005 {
2006   int i;
2007   enum rtx_code code;
2008   const char *fmt;
2009
2010   if (x == 0)
2011     return 0;
2012   code = GET_CODE (x);
2013   switch (code)
2014     {
2015       /* Handle these cases quickly.  */
2016     case CONST_INT:
2017     case CONST_DOUBLE:
2018     case SYMBOL_REF:
2019     case LABEL_REF:
2020     case CONST:
2021     case PC:
2022     case CC0:
2023     case REG:
2024     case SCRATCH:
2025       return 0;
2026
2027     case ASM_INPUT:
2028     case UNSPEC_VOLATILE:
2029     case TRAP_IF:
2030       return 1;
2031
2032     case ASM_OPERANDS:
2033       return MEM_VOLATILE_P (x);
2034
2035       /* Memory ref can trap unless it's a static var or a stack slot.  */
2036     case MEM:
2037       return rtx_addr_can_trap_p (XEXP (x, 0));
2038
2039       /* Division by a non-constant might trap.  */
2040     case DIV:
2041     case MOD:
2042     case UDIV:
2043     case UMOD:
2044       if (! CONSTANT_P (XEXP (x, 1))
2045           || GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2046         return 1;
2047       /* This was const0_rtx, but by not using that,
2048          we can link this file into other programs.  */
2049       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
2050         return 1;
2051       break;
2052
2053     case EXPR_LIST:
2054       /* An EXPR_LIST is used to represent a function call.  This
2055          certainly may trap.  */
2056       return 1;
2057
2058     case GE:
2059     case GT:
2060     case LE:
2061     case LT:
2062     case COMPARE:
2063       /* Some floating point comparisons may trap.  */
2064       /* ??? There is no machine independent way to check for tests that trap
2065          when COMPARE is used, though many targets do make this distinction.
2066          For instance, sparc uses CCFPE for compares which generate exceptions
2067          and CCFP for compares which do not generate exceptions.  */
2068       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2069         return 1;
2070       /* But often the compare has some CC mode, so check operand
2071          modes as well.  */
2072       if (GET_MODE_CLASS (GET_MODE (XEXP (x, 0))) == MODE_FLOAT
2073           || GET_MODE_CLASS (GET_MODE (XEXP (x, 1))) == MODE_FLOAT)
2074         return 1;
2075       break;
2076
2077     case NEG:
2078     case ABS:
2079       /* These operations don't trap even with floating point.  */
2080       break;
2081
2082     default:
2083       /* Any floating arithmetic may trap.  */
2084       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2085         return 1;
2086     }
2087
2088   fmt = GET_RTX_FORMAT (code);
2089   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2090     {
2091       if (fmt[i] == 'e')
2092         {
2093           if (may_trap_p (XEXP (x, i)))
2094             return 1;
2095         }
2096       else if (fmt[i] == 'E')
2097         {
2098           register int j;
2099           for (j = 0; j < XVECLEN (x, i); j++)
2100             if (may_trap_p (XVECEXP (x, i, j)))
2101               return 1;
2102         }
2103     }
2104   return 0;
2105 }
2106 \f
2107 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2108    i.e., an inequality.  */
2109
2110 int
2111 inequality_comparisons_p (x)
2112      rtx x;
2113 {
2114   register const char *fmt;
2115   register int len, i;
2116   register enum rtx_code code = GET_CODE (x);
2117
2118   switch (code)
2119     {
2120     case REG:
2121     case SCRATCH:
2122     case PC:
2123     case CC0:
2124     case CONST_INT:
2125     case CONST_DOUBLE:
2126     case CONST:
2127     case LABEL_REF:
2128     case SYMBOL_REF:
2129       return 0;
2130
2131     case LT:
2132     case LTU:
2133     case GT:
2134     case GTU:
2135     case LE:
2136     case LEU:
2137     case GE:
2138     case GEU:
2139       return 1;
2140
2141     default:
2142       break;
2143     }
2144
2145   len = GET_RTX_LENGTH (code);
2146   fmt = GET_RTX_FORMAT (code);
2147
2148   for (i = 0; i < len; i++)
2149     {
2150       if (fmt[i] == 'e')
2151         {
2152           if (inequality_comparisons_p (XEXP (x, i)))
2153             return 1;
2154         }
2155       else if (fmt[i] == 'E')
2156         {
2157           register int j;
2158           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2159             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2160               return 1;
2161         }
2162     }
2163
2164   return 0;
2165 }
2166 \f
2167 /* Replace any occurrence of FROM in X with TO.  The function does
2168    not enter into CONST_DOUBLE for the replace.
2169
2170    Note that copying is not done so X must not be shared unless all copies
2171    are to be modified.  */
2172
2173 rtx
2174 replace_rtx (x, from, to)
2175      rtx x, from, to;
2176 {
2177   register int i, j;
2178   register const char *fmt;
2179
2180   /* The following prevents loops occurrence when we change MEM in
2181      CONST_DOUBLE onto the same CONST_DOUBLE. */
2182   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2183     return x;
2184
2185   if (x == from)
2186     return to;
2187
2188   /* Allow this function to make replacements in EXPR_LISTs.  */
2189   if (x == 0)
2190     return 0;
2191
2192   fmt = GET_RTX_FORMAT (GET_CODE (x));
2193   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2194     {
2195       if (fmt[i] == 'e')
2196         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2197       else if (fmt[i] == 'E')
2198         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2199           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2200     }
2201
2202   return x;
2203 }
2204 \f
2205 /* Throughout the rtx X, replace many registers according to REG_MAP.
2206    Return the replacement for X (which may be X with altered contents).
2207    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2208    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2209
2210    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2211    should not be mapped to pseudos or vice versa since validate_change
2212    is not called.
2213
2214    If REPLACE_DEST is 1, replacements are also done in destinations;
2215    otherwise, only sources are replaced.  */
2216
2217 rtx
2218 replace_regs (x, reg_map, nregs, replace_dest)
2219      rtx x;
2220      rtx *reg_map;
2221      unsigned int nregs;
2222      int replace_dest;
2223 {
2224   register enum rtx_code code;
2225   register int i;
2226   register const char *fmt;
2227
2228   if (x == 0)
2229     return x;
2230
2231   code = GET_CODE (x);
2232   switch (code)
2233     {
2234     case SCRATCH:
2235     case PC:
2236     case CC0:
2237     case CONST_INT:
2238     case CONST_DOUBLE:
2239     case CONST:
2240     case SYMBOL_REF:
2241     case LABEL_REF:
2242       return x;
2243
2244     case REG:
2245       /* Verify that the register has an entry before trying to access it.  */
2246       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2247         {
2248           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2249              this replacement occurs more than once then each instance will
2250              get distinct rtx.  */
2251           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2252             return copy_rtx (reg_map[REGNO (x)]);
2253           return reg_map[REGNO (x)];
2254         }
2255       return x;
2256
2257     case SUBREG:
2258       /* Prevent making nested SUBREGs.  */
2259       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
2260           && reg_map[REGNO (SUBREG_REG (x))] != 0
2261           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2262         {
2263           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2264           return simplify_gen_subreg (GET_MODE (x), map_val,
2265                                       GET_MODE (SUBREG_REG (x)),
2266                                       SUBREG_BYTE (x));
2267         }
2268       break;
2269
2270     case SET:
2271       if (replace_dest)
2272         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2273
2274       else if (GET_CODE (SET_DEST (x)) == MEM
2275                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2276         /* Even if we are not to replace destinations, replace register if it
2277            is CONTAINED in destination (destination is memory or
2278            STRICT_LOW_PART).  */
2279         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2280                                                reg_map, nregs, 0);
2281       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2282         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2283         break;
2284
2285       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2286       return x;
2287
2288     default:
2289       break;
2290     }
2291
2292   fmt = GET_RTX_FORMAT (code);
2293   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2294     {
2295       if (fmt[i] == 'e')
2296         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2297       else if (fmt[i] == 'E')
2298         {
2299           register int j;
2300           for (j = 0; j < XVECLEN (x, i); j++)
2301             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2302                                               nregs, replace_dest);
2303         }
2304     }
2305   return x;
2306 }
2307
2308 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2309    constant that is not in the constant pool and not in the condition
2310    of an IF_THEN_ELSE.  */
2311
2312 static int
2313 computed_jump_p_1 (x)
2314      rtx x;
2315 {
2316   enum rtx_code code = GET_CODE (x);
2317   int i, j;
2318   const char *fmt;
2319
2320   switch (code)
2321     {
2322     case LABEL_REF:
2323     case PC:
2324       return 0;
2325
2326     case CONST:
2327     case CONST_INT:
2328     case CONST_DOUBLE:
2329     case SYMBOL_REF:
2330     case REG:
2331       return 1;
2332
2333     case MEM:
2334       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2335                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2336
2337     case IF_THEN_ELSE:
2338       return (computed_jump_p_1 (XEXP (x, 1))
2339               || computed_jump_p_1 (XEXP (x, 2)));
2340
2341     default:
2342       break;
2343     }
2344
2345   fmt = GET_RTX_FORMAT (code);
2346   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2347     {
2348       if (fmt[i] == 'e'
2349           && computed_jump_p_1 (XEXP (x, i)))
2350         return 1;
2351
2352       else if (fmt[i] == 'E')
2353         for (j = 0; j < XVECLEN (x, i); j++)
2354           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2355             return 1;
2356     }
2357
2358   return 0;
2359 }
2360
2361 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2362
2363    Tablejumps and casesi insns are not considered indirect jumps;
2364    we can recognize them by a (use (label_ref)).  */
2365
2366 int
2367 computed_jump_p (insn)
2368      rtx insn;
2369 {
2370   int i;
2371   if (GET_CODE (insn) == JUMP_INSN)
2372     {
2373       rtx pat = PATTERN (insn);
2374
2375       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2376         return 0;
2377       else if (GET_CODE (pat) == PARALLEL)
2378         {
2379           int len = XVECLEN (pat, 0);
2380           int has_use_labelref = 0;
2381
2382           for (i = len - 1; i >= 0; i--)
2383             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2384                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2385                     == LABEL_REF))
2386               has_use_labelref = 1;
2387
2388           if (! has_use_labelref)
2389             for (i = len - 1; i >= 0; i--)
2390               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2391                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2392                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2393                 return 1;
2394         }
2395       else if (GET_CODE (pat) == SET
2396                && SET_DEST (pat) == pc_rtx
2397                && computed_jump_p_1 (SET_SRC (pat)))
2398         return 1;
2399     }
2400   return 0;
2401 }
2402
2403 /* Traverse X via depth-first search, calling F for each
2404    sub-expression (including X itself).  F is also passed the DATA.
2405    If F returns -1, do not traverse sub-expressions, but continue
2406    traversing the rest of the tree.  If F ever returns any other
2407    non-zero value, stop the traversal, and return the value returned
2408    by F.  Otherwise, return 0.  This function does not traverse inside
2409    tree structure that contains RTX_EXPRs, or into sub-expressions
2410    whose format code is `0' since it is not known whether or not those
2411    codes are actually RTL.
2412
2413    This routine is very general, and could (should?) be used to
2414    implement many of the other routines in this file.  */
2415
2416 int
2417 for_each_rtx (x, f, data)
2418      rtx *x;
2419      rtx_function f;
2420      void *data;
2421 {
2422   int result;
2423   int length;
2424   const char* format;
2425   int i;
2426
2427   /* Call F on X.  */
2428   result = (*f)(x, data);
2429   if (result == -1)
2430     /* Do not traverse sub-expressions.  */
2431     return 0;
2432   else if (result != 0)
2433     /* Stop the traversal.  */
2434     return result;
2435
2436   if (*x == NULL_RTX)
2437     /* There are no sub-expressions.  */
2438     return 0;
2439
2440   length = GET_RTX_LENGTH (GET_CODE (*x));
2441   format = GET_RTX_FORMAT (GET_CODE (*x));
2442
2443   for (i = 0; i < length; ++i)
2444     {
2445       switch (format[i])
2446         {
2447         case 'e':
2448           result = for_each_rtx (&XEXP (*x, i), f, data);
2449           if (result != 0)
2450             return result;
2451           break;
2452
2453         case 'V':
2454         case 'E':
2455           if (XVEC (*x, i) != 0)
2456             {
2457               int j;
2458               for (j = 0; j < XVECLEN (*x, i); ++j)
2459                 {
2460                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
2461                   if (result != 0)
2462                     return result;
2463                 }
2464             }
2465           break;
2466
2467         default:
2468           /* Nothing to do.  */
2469           break;
2470         }
2471
2472     }
2473
2474   return 0;
2475 }
2476
2477 /* Searches X for any reference to REGNO, returning the rtx of the
2478    reference found if any.  Otherwise, returns NULL_RTX.  */
2479
2480 rtx
2481 regno_use_in (regno, x)
2482      unsigned int regno;
2483      rtx x;
2484 {
2485   register const char *fmt;
2486   int i, j;
2487   rtx tem;
2488
2489   if (GET_CODE (x) == REG && REGNO (x) == regno)
2490     return x;
2491
2492   fmt = GET_RTX_FORMAT (GET_CODE (x));
2493   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2494     {
2495       if (fmt[i] == 'e')
2496         {
2497           if ((tem = regno_use_in (regno, XEXP (x, i))))
2498             return tem;
2499         }
2500       else if (fmt[i] == 'E')
2501         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2502           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2503             return tem;
2504     }
2505
2506   return NULL_RTX;
2507 }
2508
2509 /* Return a value indicating whether OP, an operand of a commutative
2510    operation, is preferred as the first or second operand.  The higher
2511    the value, the stronger the preference for being the first operand.
2512    We use negative values to indicate a preference for the first operand
2513    and positive values for the second operand.  */
2514
2515 static int
2516 operand_preference (op)
2517      rtx op;
2518 {
2519   /* Constants always come the second operand.  Prefer "nice" constants.  */
2520   if (GET_CODE (op) == CONST_INT)
2521     return -5;
2522   if (GET_CODE (op) == CONST_DOUBLE)
2523     return -4;
2524   if (CONSTANT_P (op))
2525     return -3;
2526
2527   /* SUBREGs of objects should come second.  */
2528   if (GET_CODE (op) == SUBREG
2529       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
2530     return -2;
2531
2532   /* If only one operand is a `neg', `not',
2533     `mult', `plus', or `minus' expression, it will be the first
2534     operand.  */
2535   if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
2536       || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
2537       || GET_CODE (op) == MINUS)
2538     return 2;
2539
2540   /* Complex expressions should be the first, so decrease priority
2541      of objects.  */
2542   if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
2543     return -1;
2544   return 0;
2545 }
2546
2547 /* Return 1 iff it is neccesary to swap operands of commutative operation
2548    in order to canonicalize expression.  */
2549
2550 int
2551 swap_commutative_operands_p (x, y)
2552      rtx x, y;
2553 {
2554   return operand_preference (x) < operand_preference (y);
2555 }
2556
2557 /* Return 1 if X is an autoincrement side effect and the register is
2558    not the stack pointer.  */
2559 int
2560 auto_inc_p (x)
2561      rtx x;
2562 {
2563   switch (GET_CODE (x))
2564     {
2565     case PRE_INC:
2566     case POST_INC:
2567     case PRE_DEC:
2568     case POST_DEC:
2569     case PRE_MODIFY:
2570     case POST_MODIFY:
2571       /* There are no REG_INC notes for SP.  */
2572       if (XEXP (x, 0) != stack_pointer_rtx)
2573         return 1;
2574     default:
2575       break;
2576     }
2577   return 0;
2578 }
2579
2580 /* Return 1 if the sequence of instructions beginning with FROM and up
2581    to and including TO is safe to move.  If NEW_TO is non-NULL, and
2582    the sequence is not already safe to move, but can be easily
2583    extended to a sequence which is safe, then NEW_TO will point to the
2584    end of the extended sequence.
2585
2586    For now, this function only checks that the region contains whole
2587    exception regions, but it could be extended to check additional
2588    conditions as well.  */
2589
2590 int
2591 insns_safe_to_move_p (from, to, new_to)
2592      rtx from;
2593      rtx to;
2594      rtx *new_to;
2595 {
2596   int eh_region_count = 0;
2597   int past_to_p = 0;
2598   rtx r = from;
2599
2600   /* By default, assume the end of the region will be what was
2601      suggested.  */
2602   if (new_to)
2603     *new_to = to;
2604
2605   while (r)
2606     {
2607       if (GET_CODE (r) == NOTE)
2608         {
2609           switch (NOTE_LINE_NUMBER (r))
2610             {
2611             case NOTE_INSN_EH_REGION_BEG:
2612               ++eh_region_count;
2613               break;
2614
2615             case NOTE_INSN_EH_REGION_END:
2616               if (eh_region_count == 0)
2617                 /* This sequence of instructions contains the end of
2618                    an exception region, but not he beginning.  Moving
2619                    it will cause chaos.  */
2620                 return 0;
2621
2622               --eh_region_count;
2623               break;
2624
2625             default:
2626               break;
2627             }
2628         }
2629       else if (past_to_p)
2630         /* If we've passed TO, and we see a non-note instruction, we
2631            can't extend the sequence to a movable sequence.  */
2632         return 0;
2633
2634       if (r == to)
2635         {
2636           if (!new_to)
2637             /* It's OK to move the sequence if there were matched sets of
2638                exception region notes.  */
2639             return eh_region_count == 0;
2640
2641           past_to_p = 1;
2642         }
2643
2644       /* It's OK to move the sequence if there were matched sets of
2645          exception region notes.  */
2646       if (past_to_p && eh_region_count == 0)
2647         {
2648           *new_to = r;
2649           return 1;
2650         }
2651
2652       /* Go to the next instruction.  */
2653       r = NEXT_INSN (r);
2654     }
2655
2656   return 0;
2657 }
2658
2659 /* Return non-zero if IN contains a piece of rtl that has the address LOC */
2660 int
2661 loc_mentioned_in_p (loc, in)
2662      rtx *loc, in;
2663 {
2664   enum rtx_code code = GET_CODE (in);
2665   const char *fmt = GET_RTX_FORMAT (code);
2666   int i, j;
2667
2668   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2669     {
2670       if (loc == &in->fld[i].rtx)
2671         return 1;
2672       if (fmt[i] == 'e')
2673         {
2674           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2675             return 1;
2676         }
2677       else if (fmt[i] == 'E')
2678         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2679           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2680             return 1;
2681     }
2682   return 0;
2683 }
2684
2685 /* This function returns the regno offset of a subreg expression.
2686    xregno - A regno of an inner hard subreg_reg (or what will become one).
2687    xmode  - The mode of xregno.
2688    offset - The byte offset.
2689    ymode  - The mode of a top level SUBREG (or what may become one).
2690    RETURN - The regno offset which would be used.
2691    This function can be overridden by defining SUBREG_REGNO_OFFSET,
2692    taking the same parameters.  */
2693 unsigned int
2694 subreg_regno_offset (xregno, xmode, offset, ymode)
2695      unsigned int xregno;
2696      enum machine_mode xmode;
2697      unsigned int offset;
2698      enum machine_mode ymode;
2699 {
2700   unsigned ret;
2701   int nregs_xmode, nregs_ymode;
2702   int mode_multiple, nregs_multiple;
2703   int y_offset;
2704
2705 /* Check for an override, and use it instead.  */
2706 #ifdef SUBREG_REGNO_OFFSET
2707   ret = SUBREG_REGNO_OFFSET (xregno, xmode, offset, ymode)
2708 #else
2709   if (xregno >= FIRST_PSEUDO_REGISTER)
2710     abort ();
2711
2712   nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
2713   nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
2714   if (offset == 0 || nregs_xmode == nregs_ymode)
2715     return 0;
2716
2717   /* size of ymode must not be greater than the size of xmode.  */
2718   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
2719   if (mode_multiple == 0)
2720     abort ();
2721
2722   y_offset = offset / GET_MODE_SIZE (ymode);
2723   nregs_multiple =  nregs_xmode / nregs_ymode;
2724   ret = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
2725 #endif
2726
2727   return ret;
2728 }
2729
2730 /* Return the final regno that a subreg expression refers to. */
2731 unsigned int
2732 subreg_regno (x)
2733      rtx x;
2734 {
2735   unsigned int ret;
2736   rtx subreg = SUBREG_REG (x);
2737   int regno = REGNO (subreg);
2738
2739   ret = regno + subreg_regno_offset (regno,
2740                                      GET_MODE (subreg),
2741                                      SUBREG_BYTE (x),
2742                                      GET_MODE (x));
2743   return ret;
2744
2745 }