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