gcc/rtlanal.c

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