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