gcc/rtlanal.c

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