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