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