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