gcc/rtlanal.c

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