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