gcc/rtlanal.c

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