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