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, 2002 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "toplev.h"
  26 #include "rtl.h"
  27 #include "hard-reg-set.h"
  28 #include "insn-config.h"
  29 #include "recog.h"
  30 #include "tm_p.h"
  31
  32 /* Forward declarations */
  33 static void set_of_1            PARAMS ((rtx, rtx, void *));
  34 static void insn_dependent_p_1  PARAMS ((rtx, rtx, void *));
  35 static int computed_jump_p_1    PARAMS ((rtx));
  36 static void parms_set           PARAMS ((rtx, rtx, void *));
  37
  38 /* Bit flags that specify the machine subtype we are compiling for.
  39    Bits are tested using macros TARGET_... defined in the tm.h file
  40    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
  41
  42 int target_flags;
  43 \f
  44 /* Return 1 if the value of X is unstable
  45    (would be different at a different point in the program).
  46    The frame pointer, arg pointer, etc. are considered stable
  47    (within one function) and so is anything marked `unchanging'.  */
  48
  49 int
  50 rtx_unstable_p (x)
  51      rtx x;
  52 {
  53   RTX_CODE code = GET_CODE (x);
  54   int i;
  55   const char *fmt;
  56
  57   switch (code)
  58     {
  59     case MEM:
  60       return ! RTX_UNCHANGING_P (x) || rtx_unstable_p (XEXP (x, 0));
  61
  62     case QUEUED:
  63       return 1;
  64
  65     case ADDRESSOF:
  66     case CONST:
  67     case CONST_INT:
  68     case CONST_DOUBLE:
  69     case CONST_VECTOR:
  70     case SYMBOL_REF:
  71     case LABEL_REF:
  72       return 0;
  73
  74     case REG:
  75       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
  76       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
  77           /* The arg pointer varies if it is not a fixed register.  */
  78           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
  79           || RTX_UNCHANGING_P (x))
  80         return 0;
  81 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
  82       /* ??? When call-clobbered, the value is stable modulo the restore
  83          that must happen after a call.  This currently screws up local-alloc
  84          into believing that the restore is not needed.  */
  85       if (x == pic_offset_table_rtx)
  86         return 0;
  87 #endif
  88       return 1;
  89
  90     case ASM_OPERANDS:
  91       if (MEM_VOLATILE_P (x))
  92         return 1;
  93
  94       /* FALLTHROUGH */
  95
  96     default:
  97       break;
  98     }
  99
 100   fmt = GET_RTX_FORMAT (code);
 101   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 102     if (fmt[i] == 'e')
 103       {
 104         if (rtx_unstable_p (XEXP (x, i)))
 105           return 1;
 106       }
 107     else if (fmt[i] == 'E')
 108       {
 109         int j;
 110         for (j = 0; j < XVECLEN (x, i); j++)
 111           if (rtx_unstable_p (XVECEXP (x, i, j)))
 112             return 1;
 113       }
 114
 115   return 0;
 116 }
 117
 118 /* Return 1 if X has a value that can vary even between two
 119    executions of the program.  0 means X can be compared reliably
 120    against certain constants or near-constants.
 121    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 122    zero, we are slightly more conservative.
 123    The frame pointer and the arg pointer are considered constant.  */
 124
 125 int
 126 rtx_varies_p (x, for_alias)
 127      rtx x;
 128      int for_alias;
 129 {
 130   RTX_CODE code = GET_CODE (x);
 131   int i;
 132   const char *fmt;
 133
 134   switch (code)
 135     {
 136     case MEM:
 137       return ! RTX_UNCHANGING_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
 138
 139     case QUEUED:
 140       return 1;
 141
 142     case CONST:
 143     case CONST_INT:
 144     case CONST_DOUBLE:
 145     case CONST_VECTOR:
 146     case SYMBOL_REF:
 147     case LABEL_REF:
 148       return 0;
 149
 150     case REG:
 151       /* Note that we have to test for the actual rtx used for the frame
 152          and arg pointers and not just the register number in case we have
 153          eliminated the frame and/or arg pointer and are using it
 154          for pseudos.  */
 155       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 156           /* The arg pointer varies if it is not a fixed register.  */
 157           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 158         return 0;
 159       if (x == pic_offset_table_rtx
 160 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
 161           /* ??? When call-clobbered, the value is stable modulo the restore
 162              that must happen after a call.  This currently screws up
 163              local-alloc into believing that the restore is not needed, so we
 164              must return 0 only if we are called from alias analysis.  */
 165           && for_alias
 166 #endif
 167           )
 168         return 0;
 169       return 1;
 170
 171     case LO_SUM:
 172       /* The operand 0 of a LO_SUM is considered constant
 173          (in fact it is related specifically to operand 1)
 174          during alias analysis.  */
 175       return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
 176              || rtx_varies_p (XEXP (x, 1), for_alias);
 177
 178     case ASM_OPERANDS:
 179       if (MEM_VOLATILE_P (x))
 180         return 1;
 181
 182       /* FALLTHROUGH */
 183
 184     default:
 185       break;
 186     }
 187
 188   fmt = GET_RTX_FORMAT (code);
 189   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 190     if (fmt[i] == 'e')
 191       {
 192         if (rtx_varies_p (XEXP (x, i), for_alias))
 193           return 1;
 194       }
 195     else if (fmt[i] == 'E')
 196       {
 197         int j;
 198         for (j = 0; j < XVECLEN (x, i); j++)
 199           if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
 200             return 1;
 201       }
 202
 203   return 0;
 204 }
 205
 206 /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
 207
 208 int
 209 rtx_addr_can_trap_p (x)
 210      rtx x;
 211 {
 212   enum rtx_code code = GET_CODE (x);
 213
 214   switch (code)
 215     {
 216     case SYMBOL_REF:
 217       return SYMBOL_REF_WEAK (x);
 218
 219     case LABEL_REF:
 220       return 0;
 221
 222     case REG:
 223       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 224       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 225           || x == stack_pointer_rtx
 226           /* The arg pointer varies if it is not a fixed register.  */
 227           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 228         return 0;
 229       /* All of the virtual frame registers are stack references.  */
 230       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
 231           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
 232         return 0;
 233       return 1;
 234
 235     case CONST:
 236       return rtx_addr_can_trap_p (XEXP (x, 0));
 237
 238     case PLUS:
 239       /* An address is assumed not to trap if it is an address that can't
 240          trap plus a constant integer or it is the pic register plus a
 241          constant.  */
 242       return ! ((! rtx_addr_can_trap_p (XEXP (x, 0))
 243                  && GET_CODE (XEXP (x, 1)) == CONST_INT)
 244                 || (XEXP (x, 0) == pic_offset_table_rtx
 245                     && CONSTANT_P (XEXP (x, 1))));
 246
 247     case LO_SUM:
 248     case PRE_MODIFY:
 249       return rtx_addr_can_trap_p (XEXP (x, 1));
 250
 251     case PRE_DEC:
 252     case PRE_INC:
 253     case POST_DEC:
 254     case POST_INC:
 255     case POST_MODIFY:
 256       return rtx_addr_can_trap_p (XEXP (x, 0));
 257
 258     default:
 259       break;
 260     }
 261
 262   /* If it isn't one of the case above, it can cause a trap.  */
 263   return 1;
 264 }
 265
 266 /* Return 1 if X refers to a memory location whose address
 267    cannot be compared reliably with constant addresses,
 268    or if X refers to a BLKmode memory object.
 269    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 270    zero, we are slightly more conservative.  */
 271
 272 int
 273 rtx_addr_varies_p (x, for_alias)
 274      rtx x;
 275      int for_alias;
 276 {
 277   enum rtx_code code;
 278   int i;
 279   const char *fmt;
 280
 281   if (x == 0)
 282     return 0;
 283
 284   code = GET_CODE (x);
 285   if (code == MEM)
 286     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
 287
 288   fmt = GET_RTX_FORMAT (code);
 289   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 290     if (fmt[i] == 'e')
 291       {
 292         if (rtx_addr_varies_p (XEXP (x, i), for_alias))
 293           return 1;
 294       }
 295     else if (fmt[i] == 'E')
 296       {
 297         int j;
 298         for (j = 0; j < XVECLEN (x, i); j++)
 299           if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
 300             return 1;
 301       }
 302   return 0;
 303 }
 304 \f
 305 /* Return the value of the integer term in X, if one is apparent;
 306    otherwise return 0.
 307    Only obvious integer terms are detected.
 308    This is used in cse.c with the `related_value' field.  */
 309
 310 HOST_WIDE_INT
 311 get_integer_term (x)
 312      rtx x;
 313 {
 314   if (GET_CODE (x) == CONST)
 315     x = XEXP (x, 0);
 316
 317   if (GET_CODE (x) == MINUS
 318       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 319     return - INTVAL (XEXP (x, 1));
 320   if (GET_CODE (x) == PLUS
 321       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 322     return INTVAL (XEXP (x, 1));
 323   return 0;
 324 }
 325
 326 /* If X is a constant, return the value sans apparent integer term;
 327    otherwise return 0.
 328    Only obvious integer terms are detected.  */
 329
 330 rtx
 331 get_related_value (x)
 332      rtx x;
 333 {
 334   if (GET_CODE (x) != CONST)
 335     return 0;
 336   x = XEXP (x, 0);
 337   if (GET_CODE (x) == PLUS
 338       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 339     return XEXP (x, 0);
 340   else if (GET_CODE (x) == MINUS
 341            && GET_CODE (XEXP (x, 1)) == CONST_INT)
 342     return XEXP (x, 0);
 343   return 0;
 344 }
 345 \f
 346 /* Given a tablejump insn INSN, return the RTL expression for the offset
 347    into the jump table.  If the offset cannot be determined, then return
 348    NULL_RTX.
 349
 350    If EARLIEST is non-zero, it is a pointer to a place where the earliest
 351    insn used in locating the offset was found.  */
 352
 353 rtx
 354 get_jump_table_offset (insn, earliest)
 355      rtx insn;
 356      rtx *earliest;
 357 {
 358   rtx label;
 359   rtx table;
 360   rtx set;
 361   rtx old_insn;
 362   rtx x;
 363   rtx old_x;
 364   rtx y;
 365   rtx old_y;
 366   int i;
 367
 368   if (GET_CODE (insn) != JUMP_INSN
 369       || ! (label = JUMP_LABEL (insn))
 370       || ! (table = NEXT_INSN (label))
 371       || GET_CODE (table) != JUMP_INSN
 372       || (GET_CODE (PATTERN (table)) != ADDR_VEC
 373           && GET_CODE (PATTERN (table)) != ADDR_DIFF_VEC)
 374       || ! (set = single_set (insn)))
 375     return NULL_RTX;
 376
 377   x = SET_SRC (set);
 378
 379   /* Some targets (eg, ARM) emit a tablejump that also
 380      contains the out-of-range target.  */
 381   if (GET_CODE (x) == IF_THEN_ELSE
 382       && GET_CODE (XEXP (x, 2)) == LABEL_REF)
 383     x = XEXP (x, 1);
 384
 385   /* Search backwards and locate the expression stored in X.  */
 386   for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
 387        old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 388     ;
 389
 390   /* If X is an expression using a relative address then strip
 391      off the addition / subtraction of PC, PIC_OFFSET_TABLE_REGNUM,
 392      or the jump table label.  */
 393   if (GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC
 394       && (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS))
 395     {
 396       for (i = 0; i < 2; i++)
 397         {
 398           old_insn = insn;
 399           y = XEXP (x, i);
 400
 401           if (y == pc_rtx || y == pic_offset_table_rtx)
 402             break;
 403
 404           for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y;
 405                old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
 406             ;
 407
 408           if ((GET_CODE (y) == LABEL_REF && XEXP (y, 0) == label))
 409             break;
 410         }
 411
 412       if (i >= 2)
 413         return NULL_RTX;
 414
 415       x = XEXP (x, 1 - i);
 416
 417       for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
 418            old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 419         ;
 420     }
 421
 422   /* Strip off any sign or zero extension.  */
 423   if (GET_CODE (x) == SIGN_EXTEND || GET_CODE (x) == ZERO_EXTEND)
 424     {
 425       x = XEXP (x, 0);
 426
 427       for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
 428            old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 429         ;
 430     }
 431
 432   /* If X isn't a MEM then this isn't a tablejump we understand.  */
 433   if (GET_CODE (x) != MEM)
 434     return NULL_RTX;
 435
 436   /* Strip off the MEM.  */
 437   x = XEXP (x, 0);
 438
 439   for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
 440        old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 441     ;
 442
 443   /* If X isn't a PLUS than this isn't a tablejump we understand.  */
 444   if (GET_CODE (x) != PLUS)
 445     return NULL_RTX;
 446
 447   /* At this point we should have an expression representing the jump table
 448      plus an offset.  Examine each operand in order to determine which one
 449      represents the jump table.  Knowing that tells us that the other operand
 450      must represent the offset.  */
 451   for (i = 0; i < 2; i++)
 452     {
 453       old_insn = insn;
 454       y = XEXP (x, i);
 455
 456       for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y;
 457            old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
 458         ;
 459
 460       if ((GET_CODE (y) == CONST || GET_CODE (y) == LABEL_REF)
 461           && reg_mentioned_p (label, y))
 462         break;
 463     }
 464
 465   if (i >= 2)
 466     return NULL_RTX;
 467
 468   x = XEXP (x, 1 - i);
 469
 470   /* Strip off the addition / subtraction of PIC_OFFSET_TABLE_REGNUM.  */
 471   if (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
 472     for (i = 0; i < 2; i++)
 473       if (XEXP (x, i) == pic_offset_table_rtx)
 474         {
 475           x = XEXP (x, 1 - i);
 476           break;
 477         }
 478
 479   if (earliest)
 480     *earliest = insn;
 481
 482   /* Return the RTL expression representing the offset.  */
 483   return x;
 484 }
 485 \f
 486 /* Return the number of places FIND appears within X.  If COUNT_DEST is
 487    zero, we do not count occurrences inside the destination of a SET.  */
 488
 489 int
 490 count_occurrences (x, find, count_dest)
 491      rtx x, find;
 492      int count_dest;
 493 {
 494   int i, j;
 495   enum rtx_code code;
 496   const char *format_ptr;
 497   int count;
 498
 499   if (x == find)
 500     return 1;
 501
 502   code = GET_CODE (x);
 503
 504   switch (code)
 505     {
 506     case REG:
 507     case CONST_INT:
 508     case CONST_DOUBLE:
 509     case CONST_VECTOR:
 510     case SYMBOL_REF:
 511     case CODE_LABEL:
 512     case PC:
 513     case CC0:
 514       return 0;
 515
 516     case MEM:
 517       if (GET_CODE (find) == MEM && rtx_equal_p (x, find))
 518         return 1;
 519       break;
 520
 521     case SET:
 522       if (SET_DEST (x) == find && ! count_dest)
 523         return count_occurrences (SET_SRC (x), find, count_dest);
 524       break;
 525
 526     default:
 527       break;
 528     }
 529
 530   format_ptr = GET_RTX_FORMAT (code);
 531   count = 0;
 532
 533   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 534     {
 535       switch (*format_ptr++)
 536         {
 537         case 'e':
 538           count += count_occurrences (XEXP (x, i), find, count_dest);
 539           break;
 540
 541         case 'E':
 542           for (j = 0; j < XVECLEN (x, i); j++)
 543             count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
 544           break;
 545         }
 546     }
 547   return count;
 548 }
 549 \f
 550 /* Nonzero if register REG appears somewhere within IN.
 551    Also works if REG is not a register; in this case it checks
 552    for a subexpression of IN that is Lisp "equal" to REG.  */
 553
 554 int
 555 reg_mentioned_p (reg, in)
 556      rtx reg, in;
 557 {
 558   const char *fmt;
 559   int i;
 560   enum rtx_code code;
 561
 562   if (in == 0)
 563     return 0;
 564
 565   if (reg == in)
 566     return 1;
 567
 568   if (GET_CODE (in) == LABEL_REF)
 569     return reg == XEXP (in, 0);
 570
 571   code = GET_CODE (in);
 572
 573   switch (code)
 574     {
 575       /* Compare registers by number.  */
 576     case REG:
 577       return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
 578
 579       /* These codes have no constituent expressions
 580          and are unique.  */
 581     case SCRATCH:
 582     case CC0:
 583     case PC:
 584       return 0;
 585
 586     case CONST_INT:
 587       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
 588
 589     case CONST_VECTOR:
 590     case CONST_DOUBLE:
 591       /* These are kept unique for a given value.  */
 592       return 0;
 593
 594     default:
 595       break;
 596     }
 597
 598   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
 599     return 1;
 600
 601   fmt = GET_RTX_FORMAT (code);
 602
 603   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 604     {
 605       if (fmt[i] == 'E')
 606         {
 607           int j;
 608           for (j = XVECLEN (in, i) - 1; j >= 0; j--)
 609             if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
 610               return 1;
 611         }
 612       else if (fmt[i] == 'e'
 613                && reg_mentioned_p (reg, XEXP (in, i)))
 614         return 1;
 615     }
 616   return 0;
 617 }
 618 \f
 619 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 620    no CODE_LABEL insn.  */
 621
 622 int
 623 no_labels_between_p (beg, end)
 624      rtx beg, end;
 625 {
 626   rtx p;
 627   if (beg == end)
 628     return 0;
 629   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 630     if (GET_CODE (p) == CODE_LABEL)
 631       return 0;
 632   return 1;
 633 }
 634
 635 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 636    no JUMP_INSN insn.  */
 637
 638 int
 639 no_jumps_between_p (beg, end)
 640      rtx beg, end;
 641 {
 642   rtx p;
 643   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 644     if (GET_CODE (p) == JUMP_INSN)
 645       return 0;
 646   return 1;
 647 }
 648
 649 /* Nonzero if register REG is used in an insn between
 650    FROM_INSN and TO_INSN (exclusive of those two).  */
 651
 652 int
 653 reg_used_between_p (reg, from_insn, to_insn)
 654      rtx reg, from_insn, to_insn;
 655 {
 656   rtx insn;
 657
 658   if (from_insn == to_insn)
 659     return 0;
 660
 661   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 662     if (INSN_P (insn)
 663         && (reg_overlap_mentioned_p (reg, PATTERN (insn))
 664            || (GET_CODE (insn) == CALL_INSN
 665               && (find_reg_fusage (insn, USE, reg)
 666                   || find_reg_fusage (insn, CLOBBER, reg)))))
 667       return 1;
 668   return 0;
 669 }
 670 \f
 671 /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
 672    is entirely replaced by a new value and the only use is as a SET_DEST,
 673    we do not consider it a reference.  */
 674
 675 int
 676 reg_referenced_p (x, body)
 677      rtx x;
 678      rtx body;
 679 {
 680   int i;
 681
 682   switch (GET_CODE (body))
 683     {
 684     case SET:
 685       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
 686         return 1;
 687
 688       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
 689          of a REG that occupies all of the REG, the insn references X if
 690          it is mentioned in the destination.  */
 691       if (GET_CODE (SET_DEST (body)) != CC0
 692           && GET_CODE (SET_DEST (body)) != PC
 693           && GET_CODE (SET_DEST (body)) != REG
 694           && ! (GET_CODE (SET_DEST (body)) == SUBREG
 695                 && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG
 696                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
 697                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
 698                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
 699                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
 700           && reg_overlap_mentioned_p (x, SET_DEST (body)))
 701         return 1;
 702       return 0;
 703
 704     case ASM_OPERANDS:
 705       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
 706         if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
 707           return 1;
 708       return 0;
 709
 710     case CALL:
 711     case USE:
 712     case IF_THEN_ELSE:
 713       return reg_overlap_mentioned_p (x, body);
 714
 715     case TRAP_IF:
 716       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
 717
 718     case PREFETCH:
 719       return reg_overlap_mentioned_p (x, XEXP (body, 0));
 720
 721     case UNSPEC:
 722     case UNSPEC_VOLATILE:
 723       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 724         if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
 725           return 1;
 726       return 0;
 727
 728     case PARALLEL:
 729       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 730         if (reg_referenced_p (x, XVECEXP (body, 0, i)))
 731           return 1;
 732       return 0;
 733
 734     case CLOBBER:
 735       if (GET_CODE (XEXP (body, 0)) == MEM)
 736         if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
 737           return 1;
 738       return 0;
 739
 740     case COND_EXEC:
 741       if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
 742         return 1;
 743       return reg_referenced_p (x, COND_EXEC_CODE (body));
 744
 745     default:
 746       return 0;
 747     }
 748 }
 749
 750 /* Nonzero if register REG is referenced in an insn between
 751    FROM_INSN and TO_INSN (exclusive of those two).  Sets of REG do
 752    not count.  */
 753
 754 int
 755 reg_referenced_between_p (reg, from_insn, to_insn)
 756      rtx reg, from_insn, to_insn;
 757 {
 758   rtx insn;
 759
 760   if (from_insn == to_insn)
 761     return 0;
 762
 763   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 764     if (INSN_P (insn)
 765         && (reg_referenced_p (reg, PATTERN (insn))
 766            || (GET_CODE (insn) == CALL_INSN
 767               && find_reg_fusage (insn, USE, reg))))
 768       return 1;
 769   return 0;
 770 }
 771 \f
 772 /* Nonzero if register REG is set or clobbered in an insn between
 773    FROM_INSN and TO_INSN (exclusive of those two).  */
 774
 775 int
 776 reg_set_between_p (reg, from_insn, to_insn)
 777      rtx reg, from_insn, to_insn;
 778 {
 779   rtx insn;
 780
 781   if (from_insn == to_insn)
 782     return 0;
 783
 784   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 785     if (INSN_P (insn) && reg_set_p (reg, insn))
 786       return 1;
 787   return 0;
 788 }
 789
 790 /* Internals of reg_set_between_p.  */
 791 int
 792 reg_set_p (reg, insn)
 793      rtx reg, insn;
 794 {
 795   rtx body = insn;
 796
 797   /* We can be passed an insn or part of one.  If we are passed an insn,
 798      check if a side-effect of the insn clobbers REG.  */
 799   if (INSN_P (insn))
 800     {
 801       if (FIND_REG_INC_NOTE (insn, reg)
 802           || (GET_CODE (insn) == CALL_INSN
 803               /* We'd like to test call_used_regs here, but rtlanal.c can't
 804                  reference that variable due to its use in genattrtab.  So
 805                  we'll just be more conservative.
 806
 807                  ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE
 808                  information holds all clobbered registers.  */
 809               && ((GET_CODE (reg) == REG
 810                    && REGNO (reg) < FIRST_PSEUDO_REGISTER)
 811                   || GET_CODE (reg) == MEM
 812                   || find_reg_fusage (insn, CLOBBER, reg))))
 813         return 1;
 814
 815       body = PATTERN (insn);
 816     }
 817
 818   return set_of (reg, insn) != NULL_RTX;
 819 }
 820
 821 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 822    only if none of them are modified between START and END.  Do not
 823    consider non-registers one way or the other.  */
 824
 825 int
 826 regs_set_between_p (x, start, end)
 827      rtx x;
 828      rtx start, end;
 829 {
 830   enum rtx_code code = GET_CODE (x);
 831   const char *fmt;
 832   int i, j;
 833
 834   switch (code)
 835     {
 836     case CONST_INT:
 837     case CONST_DOUBLE:
 838     case CONST_VECTOR:
 839     case CONST:
 840     case SYMBOL_REF:
 841     case LABEL_REF:
 842     case PC:
 843     case CC0:
 844       return 0;
 845
 846     case REG:
 847       return reg_set_between_p (x, start, end);
 848
 849     default:
 850       break;
 851     }
 852
 853   fmt = GET_RTX_FORMAT (code);
 854   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 855     {
 856       if (fmt[i] == 'e' && regs_set_between_p (XEXP (x, i), start, end))
 857         return 1;
 858
 859       else if (fmt[i] == 'E')
 860         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 861           if (regs_set_between_p (XVECEXP (x, i, j), start, end))
 862             return 1;
 863     }
 864
 865   return 0;
 866 }
 867
 868 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 869    only if none of them are modified between START and END.  Return 1 if
 870    X contains a MEM; this routine does not perform any memory aliasing.  */
 871
 872 int
 873 modified_between_p (x, start, end)
 874      rtx x;
 875      rtx start, end;
 876 {
 877   enum rtx_code code = GET_CODE (x);
 878   const char *fmt;
 879   int i, j;
 880
 881   switch (code)
 882     {
 883     case CONST_INT:
 884     case CONST_DOUBLE:
 885     case CONST_VECTOR:
 886     case CONST:
 887     case SYMBOL_REF:
 888     case LABEL_REF:
 889       return 0;
 890
 891     case PC:
 892     case CC0:
 893       return 1;
 894
 895     case MEM:
 896       /* If the memory is not constant, assume it is modified.  If it is
 897          constant, we still have to check the address.  */
 898       if (! RTX_UNCHANGING_P (x))
 899         return 1;
 900       break;
 901
 902     case REG:
 903       return reg_set_between_p (x, start, end);
 904
 905     default:
 906       break;
 907     }
 908
 909   fmt = GET_RTX_FORMAT (code);
 910   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 911     {
 912       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
 913         return 1;
 914
 915       else if (fmt[i] == 'E')
 916         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 917           if (modified_between_p (XVECEXP (x, i, j), start, end))
 918             return 1;
 919     }
 920
 921   return 0;
 922 }
 923
 924 /* Similar to reg_set_p, but check all registers in X.  Return 0 only if none
 925    of them are modified in INSN.  Return 1 if X contains a MEM; this routine
 926    does not perform any memory aliasing.  */
 927
 928 int
 929 modified_in_p (x, insn)
 930      rtx x;
 931      rtx insn;
 932 {
 933   enum rtx_code code = GET_CODE (x);
 934   const char *fmt;
 935   int i, j;
 936
 937   switch (code)
 938     {
 939     case CONST_INT:
 940     case CONST_DOUBLE:
 941     case CONST_VECTOR:
 942     case CONST:
 943     case SYMBOL_REF:
 944     case LABEL_REF:
 945       return 0;
 946
 947     case PC:
 948     case CC0:
 949       return 1;
 950
 951     case MEM:
 952       /* If the memory is not constant, assume it is modified.  If it is
 953          constant, we still have to check the address.  */
 954       if (! RTX_UNCHANGING_P (x))
 955         return 1;
 956       break;
 957
 958     case REG:
 959       return reg_set_p (x, insn);
 960
 961     default:
 962       break;
 963     }
 964
 965   fmt = GET_RTX_FORMAT (code);
 966   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 967     {
 968       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
 969         return 1;
 970
 971       else if (fmt[i] == 'E')
 972         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 973           if (modified_in_p (XVECEXP (x, i, j), insn))
 974             return 1;
 975     }
 976
 977   return 0;
 978 }
 979
 980 /* Return true if anything in insn X is (anti,output,true) dependent on
 981    anything in insn Y.  */
 982
 983 int
 984 insn_dependent_p (x, y)
 985      rtx x, y;
 986 {
 987   rtx tmp;
 988
 989   if (! INSN_P (x) || ! INSN_P (y))
 990     abort ();
 991
 992   tmp = PATTERN (y);
 993   note_stores (PATTERN (x), insn_dependent_p_1, &tmp);
 994   if (tmp == NULL_RTX)
 995     return 1;
 996
 997   tmp = PATTERN (x);
 998   note_stores (PATTERN (y), insn_dependent_p_1, &tmp);
 999   if (tmp == NULL_RTX)
1000     return 1;
1001
1002   return 0;
1003 }
1004
1005 /* A helper routine for insn_dependent_p called through note_stores.  */
1006
1007 static void
1008 insn_dependent_p_1 (x, pat, data)
1009      rtx x;
1010      rtx pat ATTRIBUTE_UNUSED;
1011      void *data;
1012 {
1013   rtx * pinsn = (rtx *) data;
1014
1015   if (*pinsn && reg_mentioned_p (x, *pinsn))
1016     *pinsn = NULL_RTX;
1017 }
1018 \f
1019 /* Helper function for set_of.  */
1020 struct set_of_data
1021   {
1022     rtx found;
1023     rtx pat;
1024   };
1025
1026 static void
1027 set_of_1 (x, pat, data1)
1028      rtx x;
1029      rtx pat;
1030      void *data1;
1031 {
1032    struct set_of_data *data = (struct set_of_data *) (data1);
1033    if (rtx_equal_p (x, data->pat)
1034        || (GET_CODE (x) != MEM && reg_overlap_mentioned_p (data->pat, x)))
1035      data->found = pat;
1036 }
1037
1038 /* Give an INSN, return a SET or CLOBBER expression that does modify PAT
1039    (either directly or via STRICT_LOW_PART and similar modifiers).  */
1040 rtx
1041 set_of (pat, insn)
1042      rtx pat, insn;
1043 {
1044   struct set_of_data data;
1045   data.found = NULL_RTX;
1046   data.pat = pat;
1047   note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
1048   return data.found;
1049 }
1050 \f
1051 /* Given an INSN, return a SET expression if this insn has only a single SET.
1052    It may also have CLOBBERs, USEs, or SET whose output
1053    will not be used, which we ignore.  */
1054
1055 rtx
1056 single_set_2 (insn, pat)
1057      rtx insn, pat;
1058 {
1059   rtx set = NULL;
1060   int set_verified = 1;
1061   int i;
1062
1063   if (GET_CODE (pat) == PARALLEL)
1064     {
1065       for (i = 0; i < XVECLEN (pat, 0); i++)
1066         {
1067           rtx sub = XVECEXP (pat, 0, i);
1068           switch (GET_CODE (sub))
1069             {
1070             case USE:
1071             case CLOBBER:
1072               break;
1073
1074             case SET:
1075               /* We can consider insns having multiple sets, where all
1076                  but one are dead as single set insns.  In common case
1077                  only single set is present in the pattern so we want
1078                  to avoid checking for REG_UNUSED notes unless necessary.
1079
1080                  When we reach set first time, we just expect this is
1081                  the single set we are looking for and only when more
1082                  sets are found in the insn, we check them.  */
1083               if (!set_verified)
1084                 {
1085                   if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
1086                       && !side_effects_p (set))
1087                     set = NULL;
1088                   else
1089                     set_verified = 1;
1090                 }
1091               if (!set)
1092                 set = sub, set_verified = 0;
1093               else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
1094                        || side_effects_p (sub))
1095                 return NULL_RTX;
1096               break;
1097
1098             default:
1099               return NULL_RTX;
1100             }
1101         }
1102     }
1103   return set;
1104 }
1105
1106 /* Given an INSN, return nonzero if it has more than one SET, else return
1107    zero.  */
1108
1109 int
1110 multiple_sets (insn)
1111      rtx insn;
1112 {
1113   int found;
1114   int i;
1115
1116   /* INSN must be an insn.  */
1117   if (! INSN_P (insn))
1118     return 0;
1119
1120   /* Only a PARALLEL can have multiple SETs.  */
1121   if (GET_CODE (PATTERN (insn)) == PARALLEL)
1122     {
1123       for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1124         if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
1125           {
1126             /* If we have already found a SET, then return now.  */
1127             if (found)
1128               return 1;
1129             else
1130               found = 1;
1131           }
1132     }
1133
1134   /* Either zero or one SET.  */
1135   return 0;
1136 }
1137 \f
1138 /* Return nonzero if the destination of SET equals the source
1139    and there are no side effects.  */
1140
1141 int
1142 set_noop_p (set)
1143      rtx set;
1144 {
1145   rtx src = SET_SRC (set);
1146   rtx dst = SET_DEST (set);
1147
1148   if (side_effects_p (src) || side_effects_p (dst))
1149     return 0;
1150
1151   if (GET_CODE (dst) == MEM && GET_CODE (src) == MEM)
1152     return rtx_equal_p (dst, src);
1153
1154   if (dst == pc_rtx && src == pc_rtx)
1155     return 1;
1156
1157   if (GET_CODE (dst) == SIGN_EXTRACT
1158       || GET_CODE (dst) == ZERO_EXTRACT)
1159     return rtx_equal_p (XEXP (dst, 0), src)
1160            && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx;
1161
1162   if (GET_CODE (dst) == STRICT_LOW_PART)
1163     dst = XEXP (dst, 0);
1164
1165   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1166     {
1167       if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1168         return 0;
1169       src = SUBREG_REG (src);
1170       dst = SUBREG_REG (dst);
1171     }
1172
1173   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
1174           && REGNO (src) == REGNO (dst));
1175 }
1176 \f
1177 /* Return nonzero if an insn consists only of SETs, each of which only sets a
1178    value to itself.  */
1179
1180 int
1181 noop_move_p (insn)
1182      rtx insn;
1183 {
1184   rtx pat = PATTERN (insn);
1185
1186   if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
1187     return 1;
1188
1189   /* Insns carrying these notes are useful later on.  */
1190   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
1191     return 0;
1192
1193   /* For now treat an insn with a REG_RETVAL note as a
1194      a special insn which should not be considered a no-op.  */
1195   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
1196     return 0;
1197
1198   if (GET_CODE (pat) == SET && set_noop_p (pat))
1199     return 1;
1200
1201   if (GET_CODE (pat) == PARALLEL)
1202     {
1203       int i;
1204       /* If nothing but SETs of registers to themselves,
1205          this insn can also be deleted.  */
1206       for (i = 0; i < XVECLEN (pat, 0); i++)
1207         {
1208           rtx tem = XVECEXP (pat, 0, i);
1209
1210           if (GET_CODE (tem) == USE
1211               || GET_CODE (tem) == CLOBBER)
1212             continue;
1213
1214           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
1215             return 0;
1216         }
1217
1218       return 1;
1219     }
1220   return 0;
1221 }
1222 \f
1223
1224 /* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
1225    is not NULL_RTX then verify that the object is not modified up to VALID_TO.
1226    If the object was modified, if we hit a partial assignment to X, or hit a
1227    CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
1228    point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
1229    be the src.  */
1230
1231 rtx
1232 find_last_value (x, pinsn, valid_to, allow_hwreg)
1233      rtx x;
1234      rtx *pinsn;
1235      rtx valid_to;
1236      int allow_hwreg;
1237 {
1238   rtx p;
1239
1240   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
1241        p = PREV_INSN (p))
1242     if (INSN_P (p))
1243       {
1244         rtx set = single_set (p);
1245         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
1246
1247         if (set && rtx_equal_p (x, SET_DEST (set)))
1248           {
1249             rtx src = SET_SRC (set);
1250
1251             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1252               src = XEXP (note, 0);
1253
1254             if ((valid_to == NULL_RTX
1255                  || ! modified_between_p (src, PREV_INSN (p), valid_to))
1256                 /* Reject hard registers because we don't usually want
1257                    to use them; we'd rather use a pseudo.  */
1258                 && (! (GET_CODE (src) == REG
1259                       && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
1260               {
1261                 *pinsn = p;
1262                 return src;
1263               }
1264           }
1265
1266         /* If set in non-simple way, we don't have a value.  */
1267         if (reg_set_p (x, p))
1268           break;
1269       }
1270
1271   return x;
1272 }
1273 \f
1274 /* Return nonzero if register in range [REGNO, ENDREGNO)
1275    appears either explicitly or implicitly in X
1276    other than being stored into.
1277
1278    References contained within the substructure at LOC do not count.
1279    LOC may be zero, meaning don't ignore anything.  */
1280
1281 int
1282 refers_to_regno_p (regno, endregno, x, loc)
1283      unsigned int regno, endregno;
1284      rtx x;
1285      rtx *loc;
1286 {
1287   int i;
1288   unsigned int x_regno;
1289   RTX_CODE code;
1290   const char *fmt;
1291
1292  repeat:
1293   /* The contents of a REG_NONNEG note is always zero, so we must come here
1294      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
1295   if (x == 0)
1296     return 0;
1297
1298   code = GET_CODE (x);
1299
1300   switch (code)
1301     {
1302     case REG:
1303       x_regno = REGNO (x);
1304
1305       /* If we modifying the stack, frame, or argument pointer, it will
1306          clobber a virtual register.  In fact, we could be more precise,
1307          but it isn't worth it.  */
1308       if ((x_regno == STACK_POINTER_REGNUM
1309 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1310            || x_regno == ARG_POINTER_REGNUM
1311 #endif
1312            || x_regno == FRAME_POINTER_REGNUM)
1313           && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1314         return 1;
1315
1316       return (endregno > x_regno
1317               && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
1318                                     ? HARD_REGNO_NREGS (x_regno, GET_MODE (x))
1319                               : 1));
1320
1321     case SUBREG:
1322       /* If this is a SUBREG of a hard reg, we can see exactly which
1323          registers are being modified.  Otherwise, handle normally.  */
1324       if (GET_CODE (SUBREG_REG (x)) == REG
1325           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1326         {
1327           unsigned int inner_regno = subreg_regno (x);
1328           unsigned int inner_endregno
1329             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1330                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1331
1332           return endregno > inner_regno && regno < inner_endregno;
1333         }
1334       break;
1335
1336     case CLOBBER:
1337     case SET:
1338       if (&SET_DEST (x) != loc
1339           /* Note setting a SUBREG counts as referring to the REG it is in for
1340              a pseudo but not for hard registers since we can
1341              treat each word individually.  */
1342           && ((GET_CODE (SET_DEST (x)) == SUBREG
1343                && loc != &SUBREG_REG (SET_DEST (x))
1344                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
1345                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1346                && refers_to_regno_p (regno, endregno,
1347                                      SUBREG_REG (SET_DEST (x)), loc))
1348               || (GET_CODE (SET_DEST (x)) != REG
1349                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1350         return 1;
1351
1352       if (code == CLOBBER || loc == &SET_SRC (x))
1353         return 0;
1354       x = SET_SRC (x);
1355       goto repeat;
1356
1357     default:
1358       break;
1359     }
1360
1361   /* X does not match, so try its subexpressions.  */
1362
1363   fmt = GET_RTX_FORMAT (code);
1364   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1365     {
1366       if (fmt[i] == 'e' && loc != &XEXP (x, i))
1367         {
1368           if (i == 0)
1369             {
1370               x = XEXP (x, 0);
1371               goto repeat;
1372             }
1373           else
1374             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1375               return 1;
1376         }
1377       else if (fmt[i] == 'E')
1378         {
1379           int j;
1380           for (j = XVECLEN (x, i) - 1; j >=0; j--)
1381             if (loc != &XVECEXP (x, i, j)
1382                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1383               return 1;
1384         }
1385     }
1386   return 0;
1387 }
1388
1389 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
1390    we check if any register number in X conflicts with the relevant register
1391    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
1392    contains a MEM (we don't bother checking for memory addresses that can't
1393    conflict because we expect this to be a rare case.  */
1394
1395 int
1396 reg_overlap_mentioned_p (x, in)
1397      rtx x, in;
1398 {
1399   unsigned int regno, endregno;
1400
1401   /* Overly conservative.  */
1402   if (GET_CODE (x) == STRICT_LOW_PART)
1403     x = XEXP (x, 0);
1404
1405   /* If either argument is a constant, then modifying X can not affect IN.  */
1406   if (CONSTANT_P (x) || CONSTANT_P (in))
1407     return 0;
1408
1409   switch (GET_CODE (x))
1410     {
1411     case SUBREG:
1412       regno = REGNO (SUBREG_REG (x));
1413       if (regno < FIRST_PSEUDO_REGISTER)
1414         regno = subreg_regno (x);
1415       goto do_reg;
1416
1417     case REG:
1418       regno = REGNO (x);
1419     do_reg:
1420       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1421                           ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
1422       return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
1423
1424     case MEM:
1425       {
1426         const char *fmt;
1427         int i;
1428
1429         if (GET_CODE (in) == MEM)
1430           return 1;
1431
1432         fmt = GET_RTX_FORMAT (GET_CODE (in));
1433         for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1434           if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
1435             return 1;
1436
1437         return 0;
1438       }
1439
1440     case SCRATCH:
1441     case PC:
1442     case CC0:
1443       return reg_mentioned_p (x, in);
1444
1445     case PARALLEL:
1446       {
1447         int i;
1448
1449         /* If any register in here refers to it we return true.  */
1450         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1451           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1452               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1453               return 1;
1454         return 0;
1455       }
1456
1457     default:
1458       break;
1459     }
1460
1461   abort ();
1462 }
1463 \f
1464 /* Return the last value to which REG was set prior to INSN.  If we can't
1465    find it easily, return 0.
1466
1467    We only return a REG, SUBREG, or constant because it is too hard to
1468    check if a MEM remains unchanged.  */
1469
1470 rtx
1471 reg_set_last (x, insn)
1472      rtx x;
1473      rtx insn;
1474 {
1475   rtx orig_insn = insn;
1476
1477   /* Scan backwards until reg_set_last_1 changed one of the above flags.
1478      Stop when we reach a label or X is a hard reg and we reach a
1479      CALL_INSN (if reg_set_last_last_regno is a hard reg).
1480
1481      If we find a set of X, ensure that its SET_SRC remains unchanged.  */
1482
1483   /* We compare with <= here, because reg_set_last_last_regno
1484      is actually the number of the first reg *not* in X.  */
1485   for (;
1486        insn && GET_CODE (insn) != CODE_LABEL
1487        && ! (GET_CODE (insn) == CALL_INSN
1488              && REGNO (x) <= FIRST_PSEUDO_REGISTER);
1489        insn = PREV_INSN (insn))
1490     if (INSN_P (insn))
1491       {
1492         rtx set = set_of (x, insn);
1493         /* OK, this function modify our register.  See if we understand it.  */
1494         if (set)
1495           {
1496             rtx last_value;
1497             if (GET_CODE (set) != SET || SET_DEST (set) != x)
1498               return 0;
1499             last_value = SET_SRC (x);
1500             if (CONSTANT_P (last_value)
1501                 || ((GET_CODE (last_value) == REG
1502                      || GET_CODE (last_value) == SUBREG)
1503                     && ! reg_set_between_p (last_value,
1504                                             insn, orig_insn)))
1505               return last_value;
1506             else
1507               return 0;
1508           }
1509       }
1510
1511   return 0;
1512 }
1513 \f
1514 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1515    (X would be the pattern of an insn).
1516    FUN receives two arguments:
1517      the REG, MEM, CC0 or PC being stored in or clobbered,
1518      the SET or CLOBBER rtx that does the store.
1519
1520   If the item being stored in or clobbered is a SUBREG of a hard register,
1521   the SUBREG will be passed.  */
1522
1523 void
1524 note_stores (x, fun, data)
1525      rtx x;
1526      void (*fun) PARAMS ((rtx, rtx, void *));
1527      void *data;
1528 {
1529   int i;
1530
1531   if (GET_CODE (x) == COND_EXEC)
1532     x = COND_EXEC_CODE (x);
1533
1534   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1535     {
1536       rtx dest = SET_DEST (x);
1537
1538       while ((GET_CODE (dest) == SUBREG
1539               && (GET_CODE (SUBREG_REG (dest)) != REG
1540                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1541              || GET_CODE (dest) == ZERO_EXTRACT
1542              || GET_CODE (dest) == SIGN_EXTRACT
1543              || GET_CODE (dest) == STRICT_LOW_PART)
1544         dest = XEXP (dest, 0);
1545
1546       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1547          each of whose first operand is a register.  We can't know what
1548          precisely is being set in these cases, so make up a CLOBBER to pass
1549          to the function.  */
1550       if (GET_CODE (dest) == PARALLEL)
1551         {
1552           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1553             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1554               (*fun) (XEXP (XVECEXP (dest, 0, i), 0),
1555                       gen_rtx_CLOBBER (VOIDmode,
1556                                        XEXP (XVECEXP (dest, 0, i), 0)),
1557                       data);
1558         }
1559       else
1560         (*fun) (dest, x, data);
1561     }
1562
1563   else if (GET_CODE (x) == PARALLEL)
1564     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1565       note_stores (XVECEXP (x, 0, i), fun, data);
1566 }
1567 \f
1568 /* Like notes_stores, but call FUN for each expression that is being
1569    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1570    FUN for each expression, not any interior subexpressions.  FUN receives a
1571    pointer to the expression and the DATA passed to this function.
1572
1573    Note that this is not quite the same test as that done in reg_referenced_p
1574    since that considers something as being referenced if it is being
1575    partially set, while we do not.  */
1576
1577 void
1578 note_uses (pbody, fun, data)
1579      rtx *pbody;
1580      void (*fun) PARAMS ((rtx *, void *));
1581      void *data;
1582 {
1583   rtx body = *pbody;
1584   int i;
1585
1586   switch (GET_CODE (body))
1587     {
1588     case COND_EXEC:
1589       (*fun) (&COND_EXEC_TEST (body), data);
1590       note_uses (&COND_EXEC_CODE (body), fun, data);
1591       return;
1592
1593     case PARALLEL:
1594       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1595         note_uses (&XVECEXP (body, 0, i), fun, data);
1596       return;
1597
1598     case USE:
1599       (*fun) (&XEXP (body, 0), data);
1600       return;
1601
1602     case ASM_OPERANDS:
1603       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1604         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1605       return;
1606
1607     case TRAP_IF:
1608       (*fun) (&TRAP_CONDITION (body), data);
1609       return;
1610
1611     case PREFETCH:
1612       (*fun) (&XEXP (body, 0), data);
1613       return;
1614
1615     case UNSPEC:
1616     case UNSPEC_VOLATILE:
1617       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1618         (*fun) (&XVECEXP (body, 0, i), data);
1619       return;
1620
1621     case CLOBBER:
1622       if (GET_CODE (XEXP (body, 0)) == MEM)
1623         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1624       return;
1625
1626     case SET:
1627       {
1628         rtx dest = SET_DEST (body);
1629
1630         /* For sets we replace everything in source plus registers in memory
1631            expression in store and operands of a ZERO_EXTRACT.  */
1632         (*fun) (&SET_SRC (body), data);
1633
1634         if (GET_CODE (dest) == ZERO_EXTRACT)
1635           {
1636             (*fun) (&XEXP (dest, 1), data);
1637             (*fun) (&XEXP (dest, 2), data);
1638           }
1639
1640         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1641           dest = XEXP (dest, 0);
1642
1643         if (GET_CODE (dest) == MEM)
1644           (*fun) (&XEXP (dest, 0), data);
1645       }
1646       return;
1647
1648     default:
1649       /* All the other possibilities never store.  */
1650       (*fun) (pbody, data);
1651       return;
1652     }
1653 }
1654 \f
1655 /* Return nonzero if X's old contents don't survive after INSN.
1656    This will be true if X is (cc0) or if X is a register and
1657    X dies in INSN or because INSN entirely sets X.
1658
1659    "Entirely set" means set directly and not through a SUBREG,
1660    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
1661    Likewise, REG_INC does not count.
1662
1663    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1664    but for this use that makes no difference, since regs don't overlap
1665    during their lifetimes.  Therefore, this function may be used
1666    at any time after deaths have been computed (in flow.c).
1667
1668    If REG is a hard reg that occupies multiple machine registers, this
1669    function will only return 1 if each of those registers will be replaced
1670    by INSN.  */
1671
1672 int
1673 dead_or_set_p (insn, x)
1674      rtx insn;
1675      rtx x;
1676 {
1677   unsigned int regno, last_regno;
1678   unsigned int i;
1679
1680   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1681   if (GET_CODE (x) == CC0)
1682     return 1;
1683
1684   if (GET_CODE (x) != REG)
1685     abort ();
1686
1687   regno = REGNO (x);
1688   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1689                 : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
1690
1691   for (i = regno; i <= last_regno; i++)
1692     if (! dead_or_set_regno_p (insn, i))
1693       return 0;
1694
1695   return 1;
1696 }
1697
1698 /* Utility function for dead_or_set_p to check an individual register.  Also
1699    called from flow.c.  */
1700
1701 int
1702 dead_or_set_regno_p (insn, test_regno)
1703      rtx insn;
1704      unsigned int test_regno;
1705 {
1706   unsigned int regno, endregno;
1707   rtx pattern;
1708
1709   /* See if there is a death note for something that includes TEST_REGNO.  */
1710   if (find_regno_note (insn, REG_DEAD, test_regno))
1711     return 1;
1712
1713   if (GET_CODE (insn) == CALL_INSN
1714       && find_regno_fusage (insn, CLOBBER, test_regno))
1715     return 1;
1716
1717   pattern = PATTERN (insn);
1718
1719   if (GET_CODE (pattern) == COND_EXEC)
1720     pattern = COND_EXEC_CODE (pattern);
1721
1722   if (GET_CODE (pattern) == SET)
1723     {
1724       rtx dest = SET_DEST (PATTERN (insn));
1725
1726       /* A value is totally replaced if it is the destination or the
1727          destination is a SUBREG of REGNO that does not change the number of
1728          words in it.  */
1729       if (GET_CODE (dest) == SUBREG
1730           && (((GET_MODE_SIZE (GET_MODE (dest))
1731                 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1732               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1733                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1734         dest = SUBREG_REG (dest);
1735
1736       if (GET_CODE (dest) != REG)
1737         return 0;
1738
1739       regno = REGNO (dest);
1740       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1741                   : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1742
1743       return (test_regno >= regno && test_regno < endregno);
1744     }
1745   else if (GET_CODE (pattern) == PARALLEL)
1746     {
1747       int i;
1748
1749       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1750         {
1751           rtx body = XVECEXP (pattern, 0, i);
1752
1753           if (GET_CODE (body) == COND_EXEC)
1754             body = COND_EXEC_CODE (body);
1755
1756           if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1757             {
1758               rtx dest = SET_DEST (body);
1759
1760               if (GET_CODE (dest) == SUBREG
1761                   && (((GET_MODE_SIZE (GET_MODE (dest))
1762                         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1763                       == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1764                            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1765                 dest = SUBREG_REG (dest);
1766
1767               if (GET_CODE (dest) != REG)
1768                 continue;
1769
1770               regno = REGNO (dest);
1771               endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1772                           : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
1773
1774               if (test_regno >= regno && test_regno < endregno)
1775                 return 1;
1776             }
1777         }
1778     }
1779
1780   return 0;
1781 }
1782
1783 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1784    If DATUM is nonzero, look for one whose datum is DATUM.  */
1785
1786 rtx
1787 find_reg_note (insn, kind, datum)
1788      rtx insn;
1789      enum reg_note kind;
1790      rtx datum;
1791 {
1792   rtx link;
1793
1794   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1795   if (! INSN_P (insn))
1796     return 0;
1797
1798   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1799     if (REG_NOTE_KIND (link) == kind
1800         && (datum == 0 || datum == XEXP (link, 0)))
1801       return link;
1802   return 0;
1803 }
1804
1805 /* Return the reg-note of kind KIND in insn INSN which applies to register
1806    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1807    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1808    it might be the case that the note overlaps REGNO.  */
1809
1810 rtx
1811 find_regno_note (insn, kind, regno)
1812      rtx insn;
1813      enum reg_note kind;
1814      unsigned int regno;
1815 {
1816   rtx link;
1817
1818   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1819   if (! INSN_P (insn))
1820     return 0;
1821
1822   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1823     if (REG_NOTE_KIND (link) == kind
1824         /* Verify that it is a register, so that scratch and MEM won't cause a
1825            problem here.  */
1826         && GET_CODE (XEXP (link, 0)) == REG
1827         && REGNO (XEXP (link, 0)) <= regno
1828         && ((REGNO (XEXP (link, 0))
1829              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1830                 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
1831                                     GET_MODE (XEXP (link, 0)))))
1832             > regno))
1833       return link;
1834   return 0;
1835 }
1836
1837 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1838    has such a note.  */
1839
1840 rtx
1841 find_reg_equal_equiv_note (insn)
1842      rtx insn;
1843 {
1844   rtx note;
1845
1846   if (single_set (insn) == 0)
1847     return 0;
1848   else if ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
1849     return note;
1850   else
1851     return find_reg_note (insn, REG_EQUAL, NULL_RTX);
1852 }
1853
1854 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1855    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1856
1857 int
1858 find_reg_fusage (insn, code, datum)
1859      rtx insn;
1860      enum rtx_code code;
1861      rtx datum;
1862 {
1863   /* If it's not a CALL_INSN, it can't possibly have a
1864      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1865   if (GET_CODE (insn) != CALL_INSN)
1866     return 0;
1867
1868   if (! datum)
1869     abort ();
1870
1871   if (GET_CODE (datum) != REG)
1872     {
1873       rtx link;
1874
1875       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1876            link;
1877            link = XEXP (link, 1))
1878         if (GET_CODE (XEXP (link, 0)) == code
1879             && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
1880           return 1;
1881     }
1882   else
1883     {
1884       unsigned int regno = REGNO (datum);
1885
1886       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1887          to pseudo registers, so don't bother checking.  */
1888
1889       if (regno < FIRST_PSEUDO_REGISTER)
1890         {
1891           unsigned int end_regno
1892             = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
1893           unsigned int i;
1894
1895           for (i = regno; i < end_regno; i++)
1896             if (find_regno_fusage (insn, code, i))
1897               return 1;
1898         }
1899     }
1900
1901   return 0;
1902 }
1903
1904 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1905    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1906
1907 int
1908 find_regno_fusage (insn, code, regno)
1909      rtx insn;
1910      enum rtx_code code;
1911      unsigned int regno;
1912 {
1913   rtx link;
1914
1915   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1916      to pseudo registers, so don't bother checking.  */
1917
1918   if (regno >= FIRST_PSEUDO_REGISTER
1919       || GET_CODE (insn) != CALL_INSN )
1920     return 0;
1921
1922   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1923     {
1924       unsigned int regnote;
1925       rtx op, reg;
1926
1927       if (GET_CODE (op = XEXP (link, 0)) == code
1928           && GET_CODE (reg = XEXP (op, 0)) == REG
1929           && (regnote = REGNO (reg)) <= regno
1930           && regnote + HARD_REGNO_NREGS (regnote, GET_MODE (reg)) > regno)
1931         return 1;
1932     }
1933
1934   return 0;
1935 }
1936 \f
1937 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1938
1939 void
1940 remove_note (insn, note)
1941      rtx insn;
1942      rtx note;
1943 {
1944   rtx link;
1945
1946   if (note == NULL_RTX)
1947     return;
1948
1949   if (REG_NOTES (insn) == note)
1950     {
1951       REG_NOTES (insn) = XEXP (note, 1);
1952       return;
1953     }
1954
1955   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1956     if (XEXP (link, 1) == note)
1957       {
1958         XEXP (link, 1) = XEXP (note, 1);
1959         return;
1960       }
1961
1962   abort ();
1963 }
1964
1965 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1966    return 1 if it is found.  A simple equality test is used to determine if
1967    NODE matches.  */
1968
1969 int
1970 in_expr_list_p (listp, node)
1971      rtx listp;
1972      rtx node;
1973 {
1974   rtx x;
1975
1976   for (x = listp; x; x = XEXP (x, 1))
1977     if (node == XEXP (x, 0))
1978       return 1;
1979
1980   return 0;
1981 }
1982
1983 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1984    remove that entry from the list if it is found.
1985
1986    A simple equality test is used to determine if NODE matches.  */
1987
1988 void
1989 remove_node_from_expr_list (node, listp)
1990      rtx node;
1991      rtx *listp;
1992 {
1993   rtx temp = *listp;
1994   rtx prev = NULL_RTX;
1995
1996   while (temp)
1997     {
1998       if (node == XEXP (temp, 0))
1999         {
2000           /* Splice the node out of the list.  */
2001           if (prev)
2002             XEXP (prev, 1) = XEXP (temp, 1);
2003           else
2004             *listp = XEXP (temp, 1);
2005
2006           return;
2007         }
2008
2009       prev = temp;
2010       temp = XEXP (temp, 1);
2011     }
2012 }
2013 \f
2014 /* Nonzero if X contains any volatile instructions.  These are instructions
2015    which may cause unpredictable machine state instructions, and thus no
2016    instructions should be moved or combined across them.  This includes
2017    only volatile asms and UNSPEC_VOLATILE instructions.  */
2018
2019 int
2020 volatile_insn_p (x)
2021      rtx x;
2022 {
2023   RTX_CODE code;
2024
2025   code = GET_CODE (x);
2026   switch (code)
2027     {
2028     case LABEL_REF:
2029     case SYMBOL_REF:
2030     case CONST_INT:
2031     case CONST:
2032     case CONST_DOUBLE:
2033     case CONST_VECTOR:
2034     case CC0:
2035     case PC:
2036     case REG:
2037     case SCRATCH:
2038     case CLOBBER:
2039     case ASM_INPUT:
2040     case ADDR_VEC:
2041     case ADDR_DIFF_VEC:
2042     case CALL:
2043     case MEM:
2044       return 0;
2045
2046     case UNSPEC_VOLATILE:
2047  /* case TRAP_IF: This isn't clear yet.  */
2048       return 1;
2049
2050     case ASM_OPERANDS:
2051       if (MEM_VOLATILE_P (x))
2052         return 1;
2053
2054     default:
2055       break;
2056     }
2057
2058   /* Recursively scan the operands of this expression.  */
2059
2060   {
2061     const char *fmt = GET_RTX_FORMAT (code);
2062     int i;
2063
2064     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2065       {
2066         if (fmt[i] == 'e')
2067           {
2068             if (volatile_insn_p (XEXP (x, i)))
2069               return 1;
2070           }
2071         else if (fmt[i] == 'E')
2072           {
2073             int j;
2074             for (j = 0; j < XVECLEN (x, i); j++)
2075               if (volatile_insn_p (XVECEXP (x, i, j)))
2076                 return 1;
2077           }
2078       }
2079   }
2080   return 0;
2081 }
2082
2083 /* Nonzero if X contains any volatile memory references
2084    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
2085
2086 int
2087 volatile_refs_p (x)
2088      rtx x;
2089 {
2090   RTX_CODE code;
2091
2092   code = GET_CODE (x);
2093   switch (code)
2094     {
2095     case LABEL_REF:
2096     case SYMBOL_REF:
2097     case CONST_INT:
2098     case CONST:
2099     case CONST_DOUBLE:
2100     case CONST_VECTOR:
2101     case CC0:
2102     case PC:
2103     case REG:
2104     case SCRATCH:
2105     case CLOBBER:
2106     case ASM_INPUT:
2107     case ADDR_VEC:
2108     case ADDR_DIFF_VEC:
2109       return 0;
2110
2111     case CALL:
2112     case UNSPEC_VOLATILE:
2113  /* case TRAP_IF: This isn't clear yet.  */
2114       return 1;
2115
2116     case MEM:
2117     case ASM_OPERANDS:
2118       if (MEM_VOLATILE_P (x))
2119         return 1;
2120
2121     default:
2122       break;
2123     }
2124
2125   /* Recursively scan the operands of this expression.  */
2126
2127   {
2128     const char *fmt = GET_RTX_FORMAT (code);
2129     int i;
2130
2131     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2132       {
2133         if (fmt[i] == 'e')
2134           {
2135             if (volatile_refs_p (XEXP (x, i)))
2136               return 1;
2137           }
2138         else if (fmt[i] == 'E')
2139           {
2140             int j;
2141             for (j = 0; j < XVECLEN (x, i); j++)
2142               if (volatile_refs_p (XVECEXP (x, i, j)))
2143                 return 1;
2144           }
2145       }
2146   }
2147   return 0;
2148 }
2149
2150 /* Similar to above, except that it also rejects register pre- and post-
2151    incrementing.  */
2152
2153 int
2154 side_effects_p (x)
2155      rtx x;
2156 {
2157   RTX_CODE code;
2158
2159   code = GET_CODE (x);
2160   switch (code)
2161     {
2162     case LABEL_REF:
2163     case SYMBOL_REF:
2164     case CONST_INT:
2165     case CONST:
2166     case CONST_DOUBLE:
2167     case CONST_VECTOR:
2168     case CC0:
2169     case PC:
2170     case REG:
2171     case SCRATCH:
2172     case ASM_INPUT:
2173     case ADDR_VEC:
2174     case ADDR_DIFF_VEC:
2175       return 0;
2176
2177     case CLOBBER:
2178       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2179          when some combination can't be done.  If we see one, don't think
2180          that we can simplify the expression.  */
2181       return (GET_MODE (x) != VOIDmode);
2182
2183     case PRE_INC:
2184     case PRE_DEC:
2185     case POST_INC:
2186     case POST_DEC:
2187     case PRE_MODIFY:
2188     case POST_MODIFY:
2189     case CALL:
2190     case UNSPEC_VOLATILE:
2191  /* case TRAP_IF: This isn't clear yet.  */
2192       return 1;
2193
2194     case MEM:
2195     case ASM_OPERANDS:
2196       if (MEM_VOLATILE_P (x))
2197         return 1;
2198
2199     default:
2200       break;
2201     }
2202
2203   /* Recursively scan the operands of this expression.  */
2204
2205   {
2206     const char *fmt = GET_RTX_FORMAT (code);
2207     int i;
2208
2209     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2210       {
2211         if (fmt[i] == 'e')
2212           {
2213             if (side_effects_p (XEXP (x, i)))
2214               return 1;
2215           }
2216         else if (fmt[i] == 'E')
2217           {
2218             int j;
2219             for (j = 0; j < XVECLEN (x, i); j++)
2220               if (side_effects_p (XVECEXP (x, i, j)))
2221                 return 1;
2222           }
2223       }
2224   }
2225   return 0;
2226 }
2227 \f
2228 /* Return nonzero if evaluating rtx X might cause a trap.  */
2229
2230 int
2231 may_trap_p (x)
2232      rtx x;
2233 {
2234   int i;
2235   enum rtx_code code;
2236   const char *fmt;
2237
2238   if (x == 0)
2239     return 0;
2240   code = GET_CODE (x);
2241   switch (code)
2242     {
2243       /* Handle these cases quickly.  */
2244     case CONST_INT:
2245     case CONST_DOUBLE:
2246     case CONST_VECTOR:
2247     case SYMBOL_REF:
2248     case LABEL_REF:
2249     case CONST:
2250     case PC:
2251     case CC0:
2252     case REG:
2253     case SCRATCH:
2254       return 0;
2255
2256     case ASM_INPUT:
2257     case UNSPEC_VOLATILE:
2258     case TRAP_IF:
2259       return 1;
2260
2261     case ASM_OPERANDS:
2262       return MEM_VOLATILE_P (x);
2263
2264       /* Memory ref can trap unless it's a static var or a stack slot.  */
2265     case MEM:
2266       return rtx_addr_can_trap_p (XEXP (x, 0));
2267
2268       /* Division by a non-constant might trap.  */
2269     case DIV:
2270     case MOD:
2271     case UDIV:
2272     case UMOD:
2273       if (! CONSTANT_P (XEXP (x, 1))
2274           || GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2275         return 1;
2276       /* This was const0_rtx, but by not using that,
2277          we can link this file into other programs.  */
2278       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
2279         return 1;
2280       break;
2281
2282     case EXPR_LIST:
2283       /* An EXPR_LIST is used to represent a function call.  This
2284          certainly may trap.  */
2285       return 1;
2286
2287     case GE:
2288     case GT:
2289     case LE:
2290     case LT:
2291     case COMPARE:
2292       /* Some floating point comparisons may trap.  */
2293       /* ??? There is no machine independent way to check for tests that trap
2294          when COMPARE is used, though many targets do make this distinction.
2295          For instance, sparc uses CCFPE for compares which generate exceptions
2296          and CCFP for compares which do not generate exceptions.  */
2297       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2298         return 1;
2299       /* But often the compare has some CC mode, so check operand
2300          modes as well.  */
2301       if (GET_MODE_CLASS (GET_MODE (XEXP (x, 0))) == MODE_FLOAT
2302           || GET_MODE_CLASS (GET_MODE (XEXP (x, 1))) == MODE_FLOAT)
2303         return 1;
2304       break;
2305
2306     case NEG:
2307     case ABS:
2308       /* These operations don't trap even with floating point.  */
2309       break;
2310
2311     default:
2312       /* Any floating arithmetic may trap.  */
2313       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2314         return 1;
2315     }
2316
2317   fmt = GET_RTX_FORMAT (code);
2318   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2319     {
2320       if (fmt[i] == 'e')
2321         {
2322           if (may_trap_p (XEXP (x, i)))
2323             return 1;
2324         }
2325       else if (fmt[i] == 'E')
2326         {
2327           int j;
2328           for (j = 0; j < XVECLEN (x, i); j++)
2329             if (may_trap_p (XVECEXP (x, i, j)))
2330               return 1;
2331         }
2332     }
2333   return 0;
2334 }
2335 \f
2336 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2337    i.e., an inequality.  */
2338
2339 int
2340 inequality_comparisons_p (x)
2341      rtx x;
2342 {
2343   const char *fmt;
2344   int len, i;
2345   enum rtx_code code = GET_CODE (x);
2346
2347   switch (code)
2348     {
2349     case REG:
2350     case SCRATCH:
2351     case PC:
2352     case CC0:
2353     case CONST_INT:
2354     case CONST_DOUBLE:
2355     case CONST_VECTOR:
2356     case CONST:
2357     case LABEL_REF:
2358     case SYMBOL_REF:
2359       return 0;
2360
2361     case LT:
2362     case LTU:
2363     case GT:
2364     case GTU:
2365     case LE:
2366     case LEU:
2367     case GE:
2368     case GEU:
2369       return 1;
2370
2371     default:
2372       break;
2373     }
2374
2375   len = GET_RTX_LENGTH (code);
2376   fmt = GET_RTX_FORMAT (code);
2377
2378   for (i = 0; i < len; i++)
2379     {
2380       if (fmt[i] == 'e')
2381         {
2382           if (inequality_comparisons_p (XEXP (x, i)))
2383             return 1;
2384         }
2385       else if (fmt[i] == 'E')
2386         {
2387           int j;
2388           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2389             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2390               return 1;
2391         }
2392     }
2393
2394   return 0;
2395 }
2396 \f
2397 /* Replace any occurrence of FROM in X with TO.  The function does
2398    not enter into CONST_DOUBLE for the replace.
2399
2400    Note that copying is not done so X must not be shared unless all copies
2401    are to be modified.  */
2402
2403 rtx
2404 replace_rtx (x, from, to)
2405      rtx x, from, to;
2406 {
2407   int i, j;
2408   const char *fmt;
2409
2410   /* The following prevents loops occurrence when we change MEM in
2411      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2412   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2413     return x;
2414
2415   if (x == from)
2416     return to;
2417
2418   /* Allow this function to make replacements in EXPR_LISTs.  */
2419   if (x == 0)
2420     return 0;
2421
2422   if (GET_CODE (x) == SUBREG)
2423     {
2424       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2425
2426       if (GET_CODE (new) == CONST_INT)
2427         {
2428           x = simplify_subreg (GET_MODE (x), new,
2429                                GET_MODE (SUBREG_REG (x)),
2430                                SUBREG_BYTE (x));
2431           if (! x)
2432             abort ();
2433         }
2434       else
2435         SUBREG_REG (x) = new;
2436
2437       return x;
2438     }
2439   else if (GET_CODE (x) == ZERO_EXTEND)
2440     {
2441       rtx new = replace_rtx (XEXP (x, 0), from, to);
2442
2443       if (GET_CODE (new) == CONST_INT)
2444         {
2445           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2446                                         new, GET_MODE (XEXP (x, 0)));
2447           if (! x)
2448             abort ();
2449         }
2450       else
2451         XEXP (x, 0) = new;
2452
2453       return x;
2454     }
2455
2456   fmt = GET_RTX_FORMAT (GET_CODE (x));
2457   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2458     {
2459       if (fmt[i] == 'e')
2460         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2461       else if (fmt[i] == 'E')
2462         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2463           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2464     }
2465
2466   return x;
2467 }
2468 \f
2469 /* Throughout the rtx X, replace many registers according to REG_MAP.
2470    Return the replacement for X (which may be X with altered contents).
2471    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2472    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2473
2474    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2475    should not be mapped to pseudos or vice versa since validate_change
2476    is not called.
2477
2478    If REPLACE_DEST is 1, replacements are also done in destinations;
2479    otherwise, only sources are replaced.  */
2480
2481 rtx
2482 replace_regs (x, reg_map, nregs, replace_dest)
2483      rtx x;
2484      rtx *reg_map;
2485      unsigned int nregs;
2486      int replace_dest;
2487 {
2488   enum rtx_code code;
2489   int i;
2490   const char *fmt;
2491
2492   if (x == 0)
2493     return x;
2494
2495   code = GET_CODE (x);
2496   switch (code)
2497     {
2498     case SCRATCH:
2499     case PC:
2500     case CC0:
2501     case CONST_INT:
2502     case CONST_DOUBLE:
2503     case CONST_VECTOR:
2504     case CONST:
2505     case SYMBOL_REF:
2506     case LABEL_REF:
2507       return x;
2508
2509     case REG:
2510       /* Verify that the register has an entry before trying to access it.  */
2511       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2512         {
2513           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2514              this replacement occurs more than once then each instance will
2515              get distinct rtx.  */
2516           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2517             return copy_rtx (reg_map[REGNO (x)]);
2518           return reg_map[REGNO (x)];
2519         }
2520       return x;
2521
2522     case SUBREG:
2523       /* Prevent making nested SUBREGs.  */
2524       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
2525           && reg_map[REGNO (SUBREG_REG (x))] != 0
2526           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2527         {
2528           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2529           return simplify_gen_subreg (GET_MODE (x), map_val,
2530                                       GET_MODE (SUBREG_REG (x)),
2531                                       SUBREG_BYTE (x));
2532         }
2533       break;
2534
2535     case SET:
2536       if (replace_dest)
2537         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2538
2539       else if (GET_CODE (SET_DEST (x)) == MEM
2540                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2541         /* Even if we are not to replace destinations, replace register if it
2542            is CONTAINED in destination (destination is memory or
2543            STRICT_LOW_PART).  */
2544         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2545                                                reg_map, nregs, 0);
2546       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2547         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2548         break;
2549
2550       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2551       return x;
2552
2553     default:
2554       break;
2555     }
2556
2557   fmt = GET_RTX_FORMAT (code);
2558   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2559     {
2560       if (fmt[i] == 'e')
2561         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2562       else if (fmt[i] == 'E')
2563         {
2564           int j;
2565           for (j = 0; j < XVECLEN (x, i); j++)
2566             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2567                                               nregs, replace_dest);
2568         }
2569     }
2570   return x;
2571 }
2572
2573 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2574    constant that is not in the constant pool and not in the condition
2575    of an IF_THEN_ELSE.  */
2576
2577 static int
2578 computed_jump_p_1 (x)
2579      rtx x;
2580 {
2581   enum rtx_code code = GET_CODE (x);
2582   int i, j;
2583   const char *fmt;
2584
2585   switch (code)
2586     {
2587     case LABEL_REF:
2588     case PC:
2589       return 0;
2590
2591     case CONST:
2592     case CONST_INT:
2593     case CONST_DOUBLE:
2594     case CONST_VECTOR:
2595     case SYMBOL_REF:
2596     case REG:
2597       return 1;
2598
2599     case MEM:
2600       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2601                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2602
2603     case IF_THEN_ELSE:
2604       return (computed_jump_p_1 (XEXP (x, 1))
2605               || computed_jump_p_1 (XEXP (x, 2)));
2606
2607     default:
2608       break;
2609     }
2610
2611   fmt = GET_RTX_FORMAT (code);
2612   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2613     {
2614       if (fmt[i] == 'e'
2615           && computed_jump_p_1 (XEXP (x, i)))
2616         return 1;
2617
2618       else if (fmt[i] == 'E')
2619         for (j = 0; j < XVECLEN (x, i); j++)
2620           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2621             return 1;
2622     }
2623
2624   return 0;
2625 }
2626
2627 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2628
2629    Tablejumps and casesi insns are not considered indirect jumps;
2630    we can recognize them by a (use (label_ref)).  */
2631
2632 int
2633 computed_jump_p (insn)
2634      rtx insn;
2635 {
2636   int i;
2637   if (GET_CODE (insn) == JUMP_INSN)
2638     {
2639       rtx pat = PATTERN (insn);
2640
2641       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2642         return 0;
2643       else if (GET_CODE (pat) == PARALLEL)
2644         {
2645           int len = XVECLEN (pat, 0);
2646           int has_use_labelref = 0;
2647
2648           for (i = len - 1; i >= 0; i--)
2649             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2650                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2651                     == LABEL_REF))
2652               has_use_labelref = 1;
2653
2654           if (! has_use_labelref)
2655             for (i = len - 1; i >= 0; i--)
2656               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2657                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2658                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2659                 return 1;
2660         }
2661       else if (GET_CODE (pat) == SET
2662                && SET_DEST (pat) == pc_rtx
2663                && computed_jump_p_1 (SET_SRC (pat)))
2664         return 1;
2665     }
2666   return 0;
2667 }
2668
2669 /* Traverse X via depth-first search, calling F for each
2670    sub-expression (including X itself).  F is also passed the DATA.
2671    If F returns -1, do not traverse sub-expressions, but continue
2672    traversing the rest of the tree.  If F ever returns any other
2673    non-zero value, stop the traversal, and return the value returned
2674    by F.  Otherwise, return 0.  This function does not traverse inside
2675    tree structure that contains RTX_EXPRs, or into sub-expressions
2676    whose format code is `0' since it is not known whether or not those
2677    codes are actually RTL.
2678
2679    This routine is very general, and could (should?) be used to
2680    implement many of the other routines in this file.  */
2681
2682 int
2683 for_each_rtx (x, f, data)
2684      rtx *x;
2685      rtx_function f;
2686      void *data;
2687 {
2688   int result;
2689   int length;
2690   const char *format;
2691   int i;
2692
2693   /* Call F on X.  */
2694   result = (*f) (x, data);
2695   if (result == -1)
2696     /* Do not traverse sub-expressions.  */
2697     return 0;
2698   else if (result != 0)
2699     /* Stop the traversal.  */
2700     return result;
2701
2702   if (*x == NULL_RTX)
2703     /* There are no sub-expressions.  */
2704     return 0;
2705
2706   length = GET_RTX_LENGTH (GET_CODE (*x));
2707   format = GET_RTX_FORMAT (GET_CODE (*x));
2708
2709   for (i = 0; i < length; ++i)
2710     {
2711       switch (format[i])
2712         {
2713         case 'e':
2714           result = for_each_rtx (&XEXP (*x, i), f, data);
2715           if (result != 0)
2716             return result;
2717           break;
2718
2719         case 'V':
2720         case 'E':
2721           if (XVEC (*x, i) != 0)
2722             {
2723               int j;
2724               for (j = 0; j < XVECLEN (*x, i); ++j)
2725                 {
2726                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
2727                   if (result != 0)
2728                     return result;
2729                 }
2730             }
2731           break;
2732
2733         default:
2734           /* Nothing to do.  */
2735           break;
2736         }
2737
2738     }
2739
2740   return 0;
2741 }
2742
2743 /* Searches X for any reference to REGNO, returning the rtx of the
2744    reference found if any.  Otherwise, returns NULL_RTX.  */
2745
2746 rtx
2747 regno_use_in (regno, x)
2748      unsigned int regno;
2749      rtx x;
2750 {
2751   const char *fmt;
2752   int i, j;
2753   rtx tem;
2754
2755   if (GET_CODE (x) == REG && REGNO (x) == regno)
2756     return x;
2757
2758   fmt = GET_RTX_FORMAT (GET_CODE (x));
2759   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2760     {
2761       if (fmt[i] == 'e')
2762         {
2763           if ((tem = regno_use_in (regno, XEXP (x, i))))
2764             return tem;
2765         }
2766       else if (fmt[i] == 'E')
2767         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2768           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2769             return tem;
2770     }
2771
2772   return NULL_RTX;
2773 }
2774
2775 /* Return a value indicating whether OP, an operand of a commutative
2776    operation, is preferred as the first or second operand.  The higher
2777    the value, the stronger the preference for being the first operand.
2778    We use negative values to indicate a preference for the first operand
2779    and positive values for the second operand.  */
2780
2781 int
2782 commutative_operand_precedence (op)
2783      rtx op;
2784 {
2785   /* Constants always come the second operand.  Prefer "nice" constants.  */
2786   if (GET_CODE (op) == CONST_INT)
2787     return -5;
2788   if (GET_CODE (op) == CONST_DOUBLE)
2789     return -4;
2790   if (CONSTANT_P (op))
2791     return -3;
2792
2793   /* SUBREGs of objects should come second.  */
2794   if (GET_CODE (op) == SUBREG
2795       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
2796     return -2;
2797
2798   /* If only one operand is a `neg', `not',
2799     `mult', `plus', or `minus' expression, it will be the first
2800     operand.  */
2801   if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
2802       || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
2803       || GET_CODE (op) == MINUS)
2804     return 2;
2805
2806   /* Complex expressions should be the first, so decrease priority
2807      of objects.  */
2808   if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
2809     return -1;
2810   return 0;
2811 }
2812
2813 /* Return 1 iff it is necessary to swap operands of commutative operation
2814    in order to canonicalize expression.  */
2815
2816 int
2817 swap_commutative_operands_p (x, y)
2818      rtx x, y;
2819 {
2820   return (commutative_operand_precedence (x)
2821           < commutative_operand_precedence (y));
2822 }
2823
2824 /* Return 1 if X is an autoincrement side effect and the register is
2825    not the stack pointer.  */
2826 int
2827 auto_inc_p (x)
2828      rtx x;
2829 {
2830   switch (GET_CODE (x))
2831     {
2832     case PRE_INC:
2833     case POST_INC:
2834     case PRE_DEC:
2835     case POST_DEC:
2836     case PRE_MODIFY:
2837     case POST_MODIFY:
2838       /* There are no REG_INC notes for SP.  */
2839       if (XEXP (x, 0) != stack_pointer_rtx)
2840         return 1;
2841     default:
2842       break;
2843     }
2844   return 0;
2845 }
2846
2847 /* Return 1 if the sequence of instructions beginning with FROM and up
2848    to and including TO is safe to move.  If NEW_TO is non-NULL, and
2849    the sequence is not already safe to move, but can be easily
2850    extended to a sequence which is safe, then NEW_TO will point to the
2851    end of the extended sequence.
2852
2853    For now, this function only checks that the region contains whole
2854    exception regions, but it could be extended to check additional
2855    conditions as well.  */
2856
2857 int
2858 insns_safe_to_move_p (from, to, new_to)
2859      rtx from;
2860      rtx to;
2861      rtx *new_to;
2862 {
2863   int eh_region_count = 0;
2864   int past_to_p = 0;
2865   rtx r = from;
2866
2867   /* By default, assume the end of the region will be what was
2868      suggested.  */
2869   if (new_to)
2870     *new_to = to;
2871
2872   while (r)
2873     {
2874       if (GET_CODE (r) == NOTE)
2875         {
2876           switch (NOTE_LINE_NUMBER (r))
2877             {
2878             case NOTE_INSN_EH_REGION_BEG:
2879               ++eh_region_count;
2880               break;
2881
2882             case NOTE_INSN_EH_REGION_END:
2883               if (eh_region_count == 0)
2884                 /* This sequence of instructions contains the end of
2885                    an exception region, but not he beginning.  Moving
2886                    it will cause chaos.  */
2887                 return 0;
2888
2889               --eh_region_count;
2890               break;
2891
2892             default:
2893               break;
2894             }
2895         }
2896       else if (past_to_p)
2897         /* If we've passed TO, and we see a non-note instruction, we
2898            can't extend the sequence to a movable sequence.  */
2899         return 0;
2900
2901       if (r == to)
2902         {
2903           if (!new_to)
2904             /* It's OK to move the sequence if there were matched sets of
2905                exception region notes.  */
2906             return eh_region_count == 0;
2907
2908           past_to_p = 1;
2909         }
2910
2911       /* It's OK to move the sequence if there were matched sets of
2912          exception region notes.  */
2913       if (past_to_p && eh_region_count == 0)
2914         {
2915           *new_to = r;
2916           return 1;
2917         }
2918
2919       /* Go to the next instruction.  */
2920       r = NEXT_INSN (r);
2921     }
2922
2923   return 0;
2924 }
2925
2926 /* Return non-zero if IN contains a piece of rtl that has the address LOC */
2927 int
2928 loc_mentioned_in_p (loc, in)
2929      rtx *loc, in;
2930 {
2931   enum rtx_code code = GET_CODE (in);
2932   const char *fmt = GET_RTX_FORMAT (code);
2933   int i, j;
2934
2935   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2936     {
2937       if (loc == &in->fld[i].rtx)
2938         return 1;
2939       if (fmt[i] == 'e')
2940         {
2941           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2942             return 1;
2943         }
2944       else if (fmt[i] == 'E')
2945         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2946           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2947             return 1;
2948     }
2949   return 0;
2950 }
2951
2952 /* Given a subreg X, return the bit offset where the subreg begins
2953    (counting from the least significant bit of the reg).  */
2954
2955 unsigned int
2956 subreg_lsb (x)
2957      rtx x;
2958 {
2959   enum machine_mode inner_mode = GET_MODE (SUBREG_REG (x));
2960   enum machine_mode mode = GET_MODE (x);
2961   unsigned int bitpos;
2962   unsigned int byte;
2963   unsigned int word;
2964
2965   /* A paradoxical subreg begins at bit position 0.  */
2966   if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (inner_mode))
2967     return 0;
2968
2969   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2970     /* If the subreg crosses a word boundary ensure that
2971        it also begins and ends on a word boundary.  */
2972     if ((SUBREG_BYTE (x) % UNITS_PER_WORD
2973          + GET_MODE_SIZE (mode)) > UNITS_PER_WORD
2974         && (SUBREG_BYTE (x) % UNITS_PER_WORD
2975             || GET_MODE_SIZE (mode) % UNITS_PER_WORD))
2976         abort ();
2977
2978   if (WORDS_BIG_ENDIAN)
2979     word = (GET_MODE_SIZE (inner_mode)
2980             - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) / UNITS_PER_WORD;
2981   else
2982     word = SUBREG_BYTE (x) / UNITS_PER_WORD;
2983   bitpos = word * BITS_PER_WORD;
2984
2985   if (BYTES_BIG_ENDIAN)
2986     byte = (GET_MODE_SIZE (inner_mode)
2987             - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) % UNITS_PER_WORD;
2988   else
2989     byte = SUBREG_BYTE (x) % UNITS_PER_WORD;
2990   bitpos += byte * BITS_PER_UNIT;
2991
2992   return bitpos;
2993 }
2994
2995 /* This function returns the regno offset of a subreg expression.
2996    xregno - A regno of an inner hard subreg_reg (or what will become one).
2997    xmode  - The mode of xregno.
2998    offset - The byte offset.
2999    ymode  - The mode of a top level SUBREG (or what may become one).
3000    RETURN - The regno offset which would be used.  */
3001 unsigned int
3002 subreg_regno_offset (xregno, xmode, offset, ymode)
3003      unsigned int xregno;
3004      enum machine_mode xmode;
3005      unsigned int offset;
3006      enum machine_mode ymode;
3007 {
3008   int nregs_xmode, nregs_ymode;
3009   int mode_multiple, nregs_multiple;
3010   int y_offset;
3011
3012   if (xregno >= FIRST_PSEUDO_REGISTER)
3013     abort ();
3014
3015   nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
3016   nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
3017   if (offset == 0 || nregs_xmode == nregs_ymode)
3018     return 0;
3019
3020   /* size of ymode must not be greater than the size of xmode.  */
3021   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3022   if (mode_multiple == 0)
3023     abort ();
3024
3025   y_offset = offset / GET_MODE_SIZE (ymode);
3026   nregs_multiple =  nregs_xmode / nregs_ymode;
3027   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3028 }
3029
3030 /* Return the final regno that a subreg expression refers to.  */
3031 unsigned int
3032 subreg_regno (x)
3033      rtx x;
3034 {
3035   unsigned int ret;
3036   rtx subreg = SUBREG_REG (x);
3037   int regno = REGNO (subreg);
3038
3039   ret = regno + subreg_regno_offset (regno,
3040                                      GET_MODE (subreg),
3041                                      SUBREG_BYTE (x),
3042                                      GET_MODE (x));
3043   return ret;
3044
3045 }
3046 struct parms_set_data
3047 {
3048   int nregs;
3049   HARD_REG_SET regs;
3050 };
3051
3052 /* Helper function for noticing stores to parameter registers.  */
3053 static void
3054 parms_set (x, pat, data)
3055         rtx x, pat ATTRIBUTE_UNUSED;
3056         void *data;
3057 {
3058   struct parms_set_data *d = data;
3059   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3060       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3061     {
3062       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3063       d->nregs--;
3064     }
3065 }
3066
3067 /* Look backward for first parameter to be loaded.
3068    Do not skip BOUNDARY.  */
3069 rtx
3070 find_first_parameter_load (call_insn, boundary)
3071      rtx call_insn, boundary;
3072 {
3073   struct parms_set_data parm;
3074   rtx p, before;
3075
3076   /* Since different machines initialize their parameter registers
3077      in different orders, assume nothing.  Collect the set of all
3078      parameter registers.  */
3079   CLEAR_HARD_REG_SET (parm.regs);
3080   parm.nregs = 0;
3081   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3082     if (GET_CODE (XEXP (p, 0)) == USE
3083         && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
3084       {
3085         if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
3086           abort ();
3087
3088         /* We only care about registers which can hold function
3089            arguments.  */
3090         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3091           continue;
3092
3093         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3094         parm.nregs++;
3095       }
3096   before = call_insn;
3097
3098   /* Search backward for the first set of a register in this set.  */
3099   while (parm.nregs && before != boundary)
3100     {
3101       before = PREV_INSN (before);
3102
3103       /* It is possible that some loads got CSEed from one call to
3104          another.  Stop in that case.  */
3105       if (GET_CODE (before) == CALL_INSN)
3106         break;
3107
3108       /* Our caller needs either ensure that we will find all sets
3109          (in case code has not been optimized yet), or take care
3110          for possible labels in a way by setting boundary to preceding
3111          CODE_LABEL.  */
3112       if (GET_CODE (before) == CODE_LABEL)
3113         {
3114           if (before != boundary)
3115             abort ();
3116           break;
3117         }
3118
3119       if (INSN_P (before))
3120         note_stores (PATTERN (before), parms_set, &parm);
3121     }
3122   return before;
3123 }
3124
3125 /* Return true if we should avoid inserting code between INSN and preceeding
3126    call instruction.  */
3127
3128 bool
3129 keep_with_call_p (insn)
3130      rtx insn;
3131 {
3132   rtx set;
3133
3134   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3135     {
3136       if (GET_CODE (SET_DEST (set)) == REG
3137           && fixed_regs[REGNO (SET_DEST (set))]
3138           && general_operand (SET_SRC (set), VOIDmode))
3139         return true;
3140       if (GET_CODE (SET_SRC (set)) == REG
3141           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3142           && GET_CODE (SET_DEST (set)) == REG
3143           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3144         return true;
3145       /* There may be a stack pop just after the call and before the store
3146          of the return register.  Search for the actual store when deciding
3147          if we can break or not.  */
3148       if (SET_DEST (set) == stack_pointer_rtx)
3149         {
3150           rtx i2 = next_nonnote_insn (insn);
3151           if (i2 && keep_with_call_p (i2))
3152             return true;
3153         }
3154     }
3155   return false;
3156 }