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