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