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       return rtx_addr_can_trap_p (XEXP (x, 0));
2466
2467       /* Division by a non-constant might trap.  */
2468     case DIV:
2469     case MOD:
2470     case UDIV:
2471     case UMOD:
2472       if (HONOR_SNANS (GET_MODE (x)))
2473         return 1;
2474       if (! CONSTANT_P (XEXP (x, 1))
2475           || (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
2476               && flag_trapping_math))
2477         return 1;
2478       /* This was const0_rtx, but by not using that,
2479          we can link this file into other programs.  */
2480       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
2481         return 1;
2482       break;
2483
2484     case EXPR_LIST:
2485       /* An EXPR_LIST is used to represent a function call.  This
2486          certainly may trap.  */
2487       return 1;
2488
2489     case GE:
2490     case GT:
2491     case LE:
2492     case LT:
2493     case COMPARE:
2494       /* Some floating point comparisons may trap.  */
2495       if (!flag_trapping_math)
2496         break;
2497       /* ??? There is no machine independent way to check for tests that trap
2498          when COMPARE is used, though many targets do make this distinction.
2499          For instance, sparc uses CCFPE for compares which generate exceptions
2500          and CCFP for compares which do not generate exceptions.  */
2501       if (HONOR_NANS (GET_MODE (x)))
2502         return 1;
2503       /* But often the compare has some CC mode, so check operand
2504          modes as well.  */
2505       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2506           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2507         return 1;
2508       break;
2509
2510     case EQ:
2511     case NE:
2512       if (HONOR_SNANS (GET_MODE (x)))
2513         return 1;
2514       /* Often comparison is CC mode, so check operand modes.  */
2515       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2516           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2517         return 1;
2518       break;
2519
2520     case FIX:
2521       /* Conversion of floating point might trap.  */
2522       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2523         return 1;
2524       break;
2525
2526     case NEG:
2527     case ABS:
2528       /* These operations don't trap even with floating point.  */
2529       break;
2530
2531     default:
2532       /* Any floating arithmetic may trap.  */
2533       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
2534           && flag_trapping_math)
2535         return 1;
2536     }
2537
2538   fmt = GET_RTX_FORMAT (code);
2539   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2540     {
2541       if (fmt[i] == 'e')
2542         {
2543           if (may_trap_p (XEXP (x, i)))
2544             return 1;
2545         }
2546       else if (fmt[i] == 'E')
2547         {
2548           int j;
2549           for (j = 0; j < XVECLEN (x, i); j++)
2550             if (may_trap_p (XVECEXP (x, i, j)))
2551               return 1;
2552         }
2553     }
2554   return 0;
2555 }
2556 \f
2557 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2558    i.e., an inequality.  */
2559
2560 int
2561 inequality_comparisons_p (x)
2562      rtx x;
2563 {
2564   const char *fmt;
2565   int len, i;
2566   enum rtx_code code = GET_CODE (x);
2567
2568   switch (code)
2569     {
2570     case REG:
2571     case SCRATCH:
2572     case PC:
2573     case CC0:
2574     case CONST_INT:
2575     case CONST_DOUBLE:
2576     case CONST_VECTOR:
2577     case CONST:
2578     case LABEL_REF:
2579     case SYMBOL_REF:
2580       return 0;
2581
2582     case LT:
2583     case LTU:
2584     case GT:
2585     case GTU:
2586     case LE:
2587     case LEU:
2588     case GE:
2589     case GEU:
2590       return 1;
2591
2592     default:
2593       break;
2594     }
2595
2596   len = GET_RTX_LENGTH (code);
2597   fmt = GET_RTX_FORMAT (code);
2598
2599   for (i = 0; i < len; i++)
2600     {
2601       if (fmt[i] == 'e')
2602         {
2603           if (inequality_comparisons_p (XEXP (x, i)))
2604             return 1;
2605         }
2606       else if (fmt[i] == 'E')
2607         {
2608           int j;
2609           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2610             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2611               return 1;
2612         }
2613     }
2614
2615   return 0;
2616 }
2617 \f
2618 /* Replace any occurrence of FROM in X with TO.  The function does
2619    not enter into CONST_DOUBLE for the replace.
2620
2621    Note that copying is not done so X must not be shared unless all copies
2622    are to be modified.  */
2623
2624 rtx
2625 replace_rtx (x, from, to)
2626      rtx x, from, to;
2627 {
2628   int i, j;
2629   const char *fmt;
2630
2631   /* The following prevents loops occurrence when we change MEM in
2632      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2633   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2634     return x;
2635
2636   if (x == from)
2637     return to;
2638
2639   /* Allow this function to make replacements in EXPR_LISTs.  */
2640   if (x == 0)
2641     return 0;
2642
2643   if (GET_CODE (x) == SUBREG)
2644     {
2645       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2646
2647       if (GET_CODE (new) == CONST_INT)
2648         {
2649           x = simplify_subreg (GET_MODE (x), new,
2650                                GET_MODE (SUBREG_REG (x)),
2651                                SUBREG_BYTE (x));
2652           if (! x)
2653             abort ();
2654         }
2655       else
2656         SUBREG_REG (x) = new;
2657
2658       return x;
2659     }
2660   else if (GET_CODE (x) == ZERO_EXTEND)
2661     {
2662       rtx new = replace_rtx (XEXP (x, 0), from, to);
2663
2664       if (GET_CODE (new) == CONST_INT)
2665         {
2666           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2667                                         new, GET_MODE (XEXP (x, 0)));
2668           if (! x)
2669             abort ();
2670         }
2671       else
2672         XEXP (x, 0) = new;
2673
2674       return x;
2675     }
2676
2677   fmt = GET_RTX_FORMAT (GET_CODE (x));
2678   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2679     {
2680       if (fmt[i] == 'e')
2681         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2682       else if (fmt[i] == 'E')
2683         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2684           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2685     }
2686
2687   return x;
2688 }
2689 \f
2690 /* Throughout the rtx X, replace many registers according to REG_MAP.
2691    Return the replacement for X (which may be X with altered contents).
2692    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2693    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2694
2695    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2696    should not be mapped to pseudos or vice versa since validate_change
2697    is not called.
2698
2699    If REPLACE_DEST is 1, replacements are also done in destinations;
2700    otherwise, only sources are replaced.  */
2701
2702 rtx
2703 replace_regs (x, reg_map, nregs, replace_dest)
2704      rtx x;
2705      rtx *reg_map;
2706      unsigned int nregs;
2707      int replace_dest;
2708 {
2709   enum rtx_code code;
2710   int i;
2711   const char *fmt;
2712
2713   if (x == 0)
2714     return x;
2715
2716   code = GET_CODE (x);
2717   switch (code)
2718     {
2719     case SCRATCH:
2720     case PC:
2721     case CC0:
2722     case CONST_INT:
2723     case CONST_DOUBLE:
2724     case CONST_VECTOR:
2725     case CONST:
2726     case SYMBOL_REF:
2727     case LABEL_REF:
2728       return x;
2729
2730     case REG:
2731       /* Verify that the register has an entry before trying to access it.  */
2732       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2733         {
2734           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2735              this replacement occurs more than once then each instance will
2736              get distinct rtx.  */
2737           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2738             return copy_rtx (reg_map[REGNO (x)]);
2739           return reg_map[REGNO (x)];
2740         }
2741       return x;
2742
2743     case SUBREG:
2744       /* Prevent making nested SUBREGs.  */
2745       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
2746           && reg_map[REGNO (SUBREG_REG (x))] != 0
2747           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2748         {
2749           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2750           return simplify_gen_subreg (GET_MODE (x), map_val,
2751                                       GET_MODE (SUBREG_REG (x)),
2752                                       SUBREG_BYTE (x));
2753         }
2754       break;
2755
2756     case SET:
2757       if (replace_dest)
2758         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2759
2760       else if (GET_CODE (SET_DEST (x)) == MEM
2761                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2762         /* Even if we are not to replace destinations, replace register if it
2763            is CONTAINED in destination (destination is memory or
2764            STRICT_LOW_PART).  */
2765         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2766                                                reg_map, nregs, 0);
2767       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2768         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2769         break;
2770
2771       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2772       return x;
2773
2774     default:
2775       break;
2776     }
2777
2778   fmt = GET_RTX_FORMAT (code);
2779   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2780     {
2781       if (fmt[i] == 'e')
2782         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2783       else if (fmt[i] == 'E')
2784         {
2785           int j;
2786           for (j = 0; j < XVECLEN (x, i); j++)
2787             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2788                                               nregs, replace_dest);
2789         }
2790     }
2791   return x;
2792 }
2793
2794 /* Replace occurrences of the old label in *X with the new one.
2795    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2796
2797 int
2798 replace_label (x, data)
2799      rtx *x;
2800      void *data;
2801 {
2802   rtx l = *x;
2803   rtx tmp;
2804   rtx old_label = ((replace_label_data *) data)->r1;
2805   rtx new_label = ((replace_label_data *) data)->r2;
2806   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2807
2808   if (l == NULL_RTX)
2809     return 0;
2810
2811   if (GET_CODE (l) == MEM
2812       && (tmp = XEXP (l, 0)) != NULL_RTX
2813       && GET_CODE (tmp) == SYMBOL_REF
2814       && CONSTANT_POOL_ADDRESS_P (tmp))
2815     {
2816       rtx c = get_pool_constant (tmp);
2817       if (rtx_referenced_p (old_label, c))
2818         {
2819           rtx new_c, new_l;
2820           replace_label_data *d = (replace_label_data *) data;
2821
2822           /* Create a copy of constant C; replace the label inside
2823              but do not update LABEL_NUSES because uses in constant pool
2824              are not counted.  */
2825           new_c = copy_rtx (c);
2826           d->update_label_nuses = false;
2827           for_each_rtx (&new_c, replace_label, data);
2828           d->update_label_nuses = update_label_nuses;
2829
2830           /* Add the new constant NEW_C to constant pool and replace
2831              the old reference to constant by new reference.  */
2832           new_l = force_const_mem (get_pool_mode (tmp), new_c);
2833           *x = replace_rtx (l, l, new_l);
2834         }
2835       return 0;
2836     }
2837
2838   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2839      field.  This is not handled by for_each_rtx because it doesn't
2840      handle unprinted ('0') fields.  */
2841   if (GET_CODE (l) == JUMP_INSN && JUMP_LABEL (l) == old_label)
2842     JUMP_LABEL (l) = new_label;
2843
2844   if ((GET_CODE (l) == LABEL_REF
2845        || GET_CODE (l) == INSN_LIST)
2846       && XEXP (l, 0) == old_label)
2847     {
2848       XEXP (l, 0) = new_label;
2849       if (update_label_nuses)
2850         {
2851           ++LABEL_NUSES (new_label);
2852           --LABEL_NUSES (old_label);
2853         }
2854       return 0;
2855     }
2856
2857   return 0;
2858 }
2859
2860 /* When *BODY is equal to X or X is directly referenced by *BODY
2861    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2862    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2863
2864 static int
2865 rtx_referenced_p_1 (body, x)
2866      rtx *body;
2867      void *x;
2868 {
2869   rtx y = (rtx) x;
2870
2871   if (*body == NULL_RTX)
2872     return y == NULL_RTX;
2873
2874   /* Return true if a label_ref *BODY refers to label Y.  */
2875   if (GET_CODE (*body) == LABEL_REF && GET_CODE (y) == CODE_LABEL)
2876     return XEXP (*body, 0) == y;
2877
2878   /* If *BODY is a reference to pool constant traverse the constant.  */
2879   if (GET_CODE (*body) == SYMBOL_REF
2880       && CONSTANT_POOL_ADDRESS_P (*body))
2881     return rtx_referenced_p (y, get_pool_constant (*body));
2882
2883   /* By default, compare the RTL expressions.  */
2884   return rtx_equal_p (*body, y);
2885 }
2886
2887 /* Return true if X is referenced in BODY.  */
2888
2889 int
2890 rtx_referenced_p (x, body)
2891      rtx x;
2892      rtx body;
2893 {
2894   return for_each_rtx (&body, rtx_referenced_p_1, x);
2895 }
2896
2897 /* If INSN is a jump to jumptable insn rturn true and store the label (which
2898    INSN jumps to) to *LABEL and the tablejump insn to *TABLE.
2899    LABEL and TABLE may be NULL.  */
2900
2901 bool
2902 tablejump_p (insn, label, table)
2903      rtx insn;
2904      rtx *label;
2905      rtx *table;
2906 {
2907   rtx l, t;
2908
2909   if (onlyjump_p (insn)
2910       && (l = JUMP_LABEL (insn)) != NULL_RTX
2911       && (t = NEXT_INSN (l)) != NULL_RTX
2912       && GET_CODE (t) == JUMP_INSN
2913       && (GET_CODE (PATTERN (t)) == ADDR_VEC
2914           || GET_CODE (PATTERN (t)) == ADDR_DIFF_VEC))
2915     {
2916       if (label)
2917         *label = l;
2918       if (table)
2919         *table = t;
2920       return true;
2921     }
2922   return false;
2923 }
2924
2925 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2926    constant that is not in the constant pool and not in the condition
2927    of an IF_THEN_ELSE.  */
2928
2929 static int
2930 computed_jump_p_1 (x)
2931      rtx x;
2932 {
2933   enum rtx_code code = GET_CODE (x);
2934   int i, j;
2935   const char *fmt;
2936
2937   switch (code)
2938     {
2939     case LABEL_REF:
2940     case PC:
2941       return 0;
2942
2943     case CONST:
2944     case CONST_INT:
2945     case CONST_DOUBLE:
2946     case CONST_VECTOR:
2947     case SYMBOL_REF:
2948     case REG:
2949       return 1;
2950
2951     case MEM:
2952       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2953                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2954
2955     case IF_THEN_ELSE:
2956       return (computed_jump_p_1 (XEXP (x, 1))
2957               || computed_jump_p_1 (XEXP (x, 2)));
2958
2959     default:
2960       break;
2961     }
2962
2963   fmt = GET_RTX_FORMAT (code);
2964   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2965     {
2966       if (fmt[i] == 'e'
2967           && computed_jump_p_1 (XEXP (x, i)))
2968         return 1;
2969
2970       else if (fmt[i] == 'E')
2971         for (j = 0; j < XVECLEN (x, i); j++)
2972           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2973             return 1;
2974     }
2975
2976   return 0;
2977 }
2978
2979 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2980
2981    Tablejumps and casesi insns are not considered indirect jumps;
2982    we can recognize them by a (use (label_ref)).  */
2983
2984 int
2985 computed_jump_p (insn)
2986      rtx insn;
2987 {
2988   int i;
2989   if (GET_CODE (insn) == JUMP_INSN)
2990     {
2991       rtx pat = PATTERN (insn);
2992
2993       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2994         return 0;
2995       else if (GET_CODE (pat) == PARALLEL)
2996         {
2997           int len = XVECLEN (pat, 0);
2998           int has_use_labelref = 0;
2999
3000           for (i = len - 1; i >= 0; i--)
3001             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
3002                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
3003                     == LABEL_REF))
3004               has_use_labelref = 1;
3005
3006           if (! has_use_labelref)
3007             for (i = len - 1; i >= 0; i--)
3008               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
3009                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
3010                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
3011                 return 1;
3012         }
3013       else if (GET_CODE (pat) == SET
3014                && SET_DEST (pat) == pc_rtx
3015                && computed_jump_p_1 (SET_SRC (pat)))
3016         return 1;
3017     }
3018   return 0;
3019 }
3020
3021 /* Traverse X via depth-first search, calling F for each
3022    sub-expression (including X itself).  F is also passed the DATA.
3023    If F returns -1, do not traverse sub-expressions, but continue
3024    traversing the rest of the tree.  If F ever returns any other
3025    nonzero value, stop the traversal, and return the value returned
3026    by F.  Otherwise, return 0.  This function does not traverse inside
3027    tree structure that contains RTX_EXPRs, or into sub-expressions
3028    whose format code is `0' since it is not known whether or not those
3029    codes are actually RTL.
3030
3031    This routine is very general, and could (should?) be used to
3032    implement many of the other routines in this file.  */
3033
3034 int
3035 for_each_rtx (x, f, data)
3036      rtx *x;
3037      rtx_function f;
3038      void *data;
3039 {
3040   int result;
3041   int length;
3042   const char *format;
3043   int i;
3044
3045   /* Call F on X.  */
3046   result = (*f) (x, data);
3047   if (result == -1)
3048     /* Do not traverse sub-expressions.  */
3049     return 0;
3050   else if (result != 0)
3051     /* Stop the traversal.  */
3052     return result;
3053
3054   if (*x == NULL_RTX)
3055     /* There are no sub-expressions.  */
3056     return 0;
3057
3058   length = GET_RTX_LENGTH (GET_CODE (*x));
3059   format = GET_RTX_FORMAT (GET_CODE (*x));
3060
3061   for (i = 0; i < length; ++i)
3062     {
3063       switch (format[i])
3064         {
3065         case 'e':
3066           result = for_each_rtx (&XEXP (*x, i), f, data);
3067           if (result != 0)
3068             return result;
3069           break;
3070
3071         case 'V':
3072         case 'E':
3073           if (XVEC (*x, i) != 0)
3074             {
3075               int j;
3076               for (j = 0; j < XVECLEN (*x, i); ++j)
3077                 {
3078                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
3079                   if (result != 0)
3080                     return result;
3081                 }
3082             }
3083           break;
3084
3085         default:
3086           /* Nothing to do.  */
3087           break;
3088         }
3089
3090     }
3091
3092   return 0;
3093 }
3094
3095 /* Searches X for any reference to REGNO, returning the rtx of the
3096    reference found if any.  Otherwise, returns NULL_RTX.  */
3097
3098 rtx
3099 regno_use_in (regno, x)
3100      unsigned int regno;
3101      rtx x;
3102 {
3103   const char *fmt;
3104   int i, j;
3105   rtx tem;
3106
3107   if (GET_CODE (x) == REG && REGNO (x) == regno)
3108     return x;
3109
3110   fmt = GET_RTX_FORMAT (GET_CODE (x));
3111   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3112     {
3113       if (fmt[i] == 'e')
3114         {
3115           if ((tem = regno_use_in (regno, XEXP (x, i))))
3116             return tem;
3117         }
3118       else if (fmt[i] == 'E')
3119         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3120           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
3121             return tem;
3122     }
3123
3124   return NULL_RTX;
3125 }
3126
3127 /* Return a value indicating whether OP, an operand of a commutative
3128    operation, is preferred as the first or second operand.  The higher
3129    the value, the stronger the preference for being the first operand.
3130    We use negative values to indicate a preference for the first operand
3131    and positive values for the second operand.  */
3132
3133 int
3134 commutative_operand_precedence (op)
3135      rtx op;
3136 {
3137   /* Constants always come the second operand.  Prefer "nice" constants.  */
3138   if (GET_CODE (op) == CONST_INT)
3139     return -5;
3140   if (GET_CODE (op) == CONST_DOUBLE)
3141     return -4;
3142   if (CONSTANT_P (op))
3143     return -3;
3144
3145   /* SUBREGs of objects should come second.  */
3146   if (GET_CODE (op) == SUBREG
3147       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
3148     return -2;
3149
3150   /* If only one operand is a `neg', `not',
3151     `mult', `plus', or `minus' expression, it will be the first
3152     operand.  */
3153   if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
3154       || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
3155       || GET_CODE (op) == MINUS)
3156     return 2;
3157
3158   /* Complex expressions should be the first, so decrease priority
3159      of objects.  */
3160   if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
3161     return -1;
3162   return 0;
3163 }
3164
3165 /* Return 1 iff it is necessary to swap operands of commutative operation
3166    in order to canonicalize expression.  */
3167
3168 int
3169 swap_commutative_operands_p (x, y)
3170      rtx x, y;
3171 {
3172   return (commutative_operand_precedence (x)
3173           < commutative_operand_precedence (y));
3174 }
3175
3176 /* Return 1 if X is an autoincrement side effect and the register is
3177    not the stack pointer.  */
3178 int
3179 auto_inc_p (x)
3180      rtx x;
3181 {
3182   switch (GET_CODE (x))
3183     {
3184     case PRE_INC:
3185     case POST_INC:
3186     case PRE_DEC:
3187     case POST_DEC:
3188     case PRE_MODIFY:
3189     case POST_MODIFY:
3190       /* There are no REG_INC notes for SP.  */
3191       if (XEXP (x, 0) != stack_pointer_rtx)
3192         return 1;
3193     default:
3194       break;
3195     }
3196   return 0;
3197 }
3198
3199 /* Return 1 if the sequence of instructions beginning with FROM and up
3200    to and including TO is safe to move.  If NEW_TO is non-NULL, and
3201    the sequence is not already safe to move, but can be easily
3202    extended to a sequence which is safe, then NEW_TO will point to the
3203    end of the extended sequence.
3204
3205    For now, this function only checks that the region contains whole
3206    exception regions, but it could be extended to check additional
3207    conditions as well.  */
3208
3209 int
3210 insns_safe_to_move_p (from, to, new_to)
3211      rtx from;
3212      rtx to;
3213      rtx *new_to;
3214 {
3215   int eh_region_count = 0;
3216   int past_to_p = 0;
3217   rtx r = from;
3218
3219   /* By default, assume the end of the region will be what was
3220      suggested.  */
3221   if (new_to)
3222     *new_to = to;
3223
3224   while (r)
3225     {
3226       if (GET_CODE (r) == NOTE)
3227         {
3228           switch (NOTE_LINE_NUMBER (r))
3229             {
3230             case NOTE_INSN_EH_REGION_BEG:
3231               ++eh_region_count;
3232               break;
3233
3234             case NOTE_INSN_EH_REGION_END:
3235               if (eh_region_count == 0)
3236                 /* This sequence of instructions contains the end of
3237                    an exception region, but not he beginning.  Moving
3238                    it will cause chaos.  */
3239                 return 0;
3240
3241               --eh_region_count;
3242               break;
3243
3244             default:
3245               break;
3246             }
3247         }
3248       else if (past_to_p)
3249         /* If we've passed TO, and we see a non-note instruction, we
3250            can't extend the sequence to a movable sequence.  */
3251         return 0;
3252
3253       if (r == to)
3254         {
3255           if (!new_to)
3256             /* It's OK to move the sequence if there were matched sets of
3257                exception region notes.  */
3258             return eh_region_count == 0;
3259
3260           past_to_p = 1;
3261         }
3262
3263       /* It's OK to move the sequence if there were matched sets of
3264          exception region notes.  */
3265       if (past_to_p && eh_region_count == 0)
3266         {
3267           *new_to = r;
3268           return 1;
3269         }
3270
3271       /* Go to the next instruction.  */
3272       r = NEXT_INSN (r);
3273     }
3274
3275   return 0;
3276 }
3277
3278 /* Return nonzero if IN contains a piece of rtl that has the address LOC */
3279 int
3280 loc_mentioned_in_p (loc, in)
3281      rtx *loc, in;
3282 {
3283   enum rtx_code code = GET_CODE (in);
3284   const char *fmt = GET_RTX_FORMAT (code);
3285   int i, j;
3286
3287   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3288     {
3289       if (loc == &in->fld[i].rtx)
3290         return 1;
3291       if (fmt[i] == 'e')
3292         {
3293           if (loc_mentioned_in_p (loc, XEXP (in, i)))
3294             return 1;
3295         }
3296       else if (fmt[i] == 'E')
3297         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
3298           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3299             return 1;
3300     }
3301   return 0;
3302 }
3303
3304 /* Given a subreg X, return the bit offset where the subreg begins
3305    (counting from the least significant bit of the reg).  */
3306
3307 unsigned int
3308 subreg_lsb (x)
3309      rtx x;
3310 {
3311   enum machine_mode inner_mode = GET_MODE (SUBREG_REG (x));
3312   enum machine_mode mode = GET_MODE (x);
3313   unsigned int bitpos;
3314   unsigned int byte;
3315   unsigned int word;
3316
3317   /* A paradoxical subreg begins at bit position 0.  */
3318   if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (inner_mode))
3319     return 0;
3320
3321   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3322     /* If the subreg crosses a word boundary ensure that
3323        it also begins and ends on a word boundary.  */
3324     if ((SUBREG_BYTE (x) % UNITS_PER_WORD
3325          + GET_MODE_SIZE (mode)) > UNITS_PER_WORD
3326         && (SUBREG_BYTE (x) % UNITS_PER_WORD
3327             || GET_MODE_SIZE (mode) % UNITS_PER_WORD))
3328         abort ();
3329
3330   if (WORDS_BIG_ENDIAN)
3331     word = (GET_MODE_SIZE (inner_mode)
3332             - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) / UNITS_PER_WORD;
3333   else
3334     word = SUBREG_BYTE (x) / UNITS_PER_WORD;
3335   bitpos = word * BITS_PER_WORD;
3336
3337   if (BYTES_BIG_ENDIAN)
3338     byte = (GET_MODE_SIZE (inner_mode)
3339             - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) % UNITS_PER_WORD;
3340   else
3341     byte = SUBREG_BYTE (x) % UNITS_PER_WORD;
3342   bitpos += byte * BITS_PER_UNIT;
3343
3344   return bitpos;
3345 }
3346
3347 /* This function returns the regno offset of a subreg expression.
3348    xregno - A regno of an inner hard subreg_reg (or what will become one).
3349    xmode  - The mode of xregno.
3350    offset - The byte offset.
3351    ymode  - The mode of a top level SUBREG (or what may become one).
3352    RETURN - The regno offset which would be used.  */
3353 unsigned int
3354 subreg_regno_offset (xregno, xmode, offset, ymode)
3355      unsigned int xregno;
3356      enum machine_mode xmode;
3357      unsigned int offset;
3358      enum machine_mode ymode;
3359 {
3360   int nregs_xmode, nregs_ymode;
3361   int mode_multiple, nregs_multiple;
3362   int y_offset;
3363
3364   if (xregno >= FIRST_PSEUDO_REGISTER)
3365     abort ();
3366
3367   nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
3368   nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
3369
3370   /* If this is a big endian paradoxical subreg, which uses more actual
3371      hard registers than the original register, we must return a negative
3372      offset so that we find the proper highpart of the register.  */
3373   if (offset == 0
3374       && nregs_ymode > nregs_xmode
3375       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3376           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3377     return nregs_xmode - nregs_ymode;
3378
3379   if (offset == 0 || nregs_xmode == nregs_ymode)
3380     return 0;
3381
3382   /* size of ymode must not be greater than the size of xmode.  */
3383   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3384   if (mode_multiple == 0)
3385     abort ();
3386
3387   y_offset = offset / GET_MODE_SIZE (ymode);
3388   nregs_multiple =  nregs_xmode / nregs_ymode;
3389   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3390 }
3391
3392 /* This function returns true when the offset is representable via
3393    subreg_offset in the given regno.
3394    xregno - A regno of an inner hard subreg_reg (or what will become one).
3395    xmode  - The mode of xregno.
3396    offset - The byte offset.
3397    ymode  - The mode of a top level SUBREG (or what may become one).
3398    RETURN - The regno offset which would be used.  */
3399 bool
3400 subreg_offset_representable_p (xregno, xmode, offset, ymode)
3401      unsigned int xregno;
3402      enum machine_mode xmode;
3403      unsigned int offset;
3404      enum machine_mode ymode;
3405 {
3406   int nregs_xmode, nregs_ymode;
3407   int mode_multiple, nregs_multiple;
3408   int y_offset;
3409
3410   if (xregno >= FIRST_PSEUDO_REGISTER)
3411     abort ();
3412
3413   nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
3414   nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
3415
3416   /* paradoxical subregs are always valid.  */
3417   if (offset == 0
3418       && nregs_ymode > nregs_xmode
3419       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3420           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3421     return true;
3422
3423   /* Lowpart subregs are always valid.  */
3424   if (offset == subreg_lowpart_offset (ymode, xmode))
3425     return true;
3426
3427 #ifdef ENABLE_CHECKING
3428   /* This should always pass, otherwise we don't know how to verify the
3429      constraint.
3430
3431      These conditions may be relaxed but subreg_offset would need to be
3432      redesigned.  */
3433   if (GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)
3434       || GET_MODE_SIZE (ymode) % nregs_ymode
3435       || (GET_MODE_BITSIZE (mode_for_size (GET_MODE_BITSIZE (xmode)
3436                                            / nregs_xmode,
3437                                            MODE_INT, 0))
3438           != GET_MODE_BITSIZE (xmode) / nregs_xmode)
3439       || nregs_xmode % nregs_ymode)
3440     abort ();
3441 #endif
3442
3443   /* The XMODE value can be seen as an vector of NREGS_XMODE
3444      values.  The subreg must represent an lowpart of given field.
3445      Compute what field it is.  */
3446   offset -= subreg_lowpart_offset (ymode,
3447                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3448                                                   / nregs_xmode,
3449                                                   MODE_INT, 0));
3450
3451   /* size of ymode must not be greater than the size of xmode.  */
3452   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3453   if (mode_multiple == 0)
3454     abort ();
3455
3456   y_offset = offset / GET_MODE_SIZE (ymode);
3457   nregs_multiple =  nregs_xmode / nregs_ymode;
3458 #ifdef ENABLE_CHECKING
3459   if (offset % GET_MODE_SIZE (ymode)
3460       || mode_multiple % nregs_multiple)
3461     abort ();
3462 #endif
3463   return (!(y_offset % (mode_multiple / nregs_multiple)));
3464 }
3465
3466 /* Return the final regno that a subreg expression refers to.  */
3467 unsigned int
3468 subreg_regno (x)
3469      rtx x;
3470 {
3471   unsigned int ret;
3472   rtx subreg = SUBREG_REG (x);
3473   int regno = REGNO (subreg);
3474
3475   ret = regno + subreg_regno_offset (regno,
3476                                      GET_MODE (subreg),
3477                                      SUBREG_BYTE (x),
3478                                      GET_MODE (x));
3479   return ret;
3480
3481 }
3482 struct parms_set_data
3483 {
3484   int nregs;
3485   HARD_REG_SET regs;
3486 };
3487
3488 /* Helper function for noticing stores to parameter registers.  */
3489 static void
3490 parms_set (x, pat, data)
3491         rtx x, pat ATTRIBUTE_UNUSED;
3492         void *data;
3493 {
3494   struct parms_set_data *d = data;
3495   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3496       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3497     {
3498       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3499       d->nregs--;
3500     }
3501 }
3502
3503 /* Look backward for first parameter to be loaded.
3504    Do not skip BOUNDARY.  */
3505 rtx
3506 find_first_parameter_load (call_insn, boundary)
3507      rtx call_insn, boundary;
3508 {
3509   struct parms_set_data parm;
3510   rtx p, before;
3511
3512   /* Since different machines initialize their parameter registers
3513      in different orders, assume nothing.  Collect the set of all
3514      parameter registers.  */
3515   CLEAR_HARD_REG_SET (parm.regs);
3516   parm.nregs = 0;
3517   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3518     if (GET_CODE (XEXP (p, 0)) == USE
3519         && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
3520       {
3521         if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
3522           abort ();
3523
3524         /* We only care about registers which can hold function
3525            arguments.  */
3526         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3527           continue;
3528
3529         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3530         parm.nregs++;
3531       }
3532   before = call_insn;
3533
3534   /* Search backward for the first set of a register in this set.  */
3535   while (parm.nregs && before != boundary)
3536     {
3537       before = PREV_INSN (before);
3538
3539       /* It is possible that some loads got CSEed from one call to
3540          another.  Stop in that case.  */
3541       if (GET_CODE (before) == CALL_INSN)
3542         break;
3543
3544       /* Our caller needs either ensure that we will find all sets
3545          (in case code has not been optimized yet), or take care
3546          for possible labels in a way by setting boundary to preceding
3547          CODE_LABEL.  */
3548       if (GET_CODE (before) == CODE_LABEL)
3549         {
3550           if (before != boundary)
3551             abort ();
3552           break;
3553         }
3554
3555       if (INSN_P (before))
3556         note_stores (PATTERN (before), parms_set, &parm);
3557     }
3558   return before;
3559 }
3560
3561 /* Return true if we should avoid inserting code between INSN and preceding
3562    call instruction.  */
3563
3564 bool
3565 keep_with_call_p (insn)
3566      rtx insn;
3567 {
3568   rtx set;
3569
3570   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3571     {
3572       if (GET_CODE (SET_DEST (set)) == REG
3573           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3574           && fixed_regs[REGNO (SET_DEST (set))]
3575           && general_operand (SET_SRC (set), VOIDmode))
3576         return true;
3577       if (GET_CODE (SET_SRC (set)) == REG
3578           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3579           && GET_CODE (SET_DEST (set)) == REG
3580           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3581         return true;
3582       /* There may be a stack pop just after the call and before the store
3583          of the return register.  Search for the actual store when deciding
3584          if we can break or not.  */
3585       if (SET_DEST (set) == stack_pointer_rtx)
3586         {
3587           rtx i2 = next_nonnote_insn (insn);
3588           if (i2 && keep_with_call_p (i2))
3589             return true;
3590         }
3591     }
3592   return false;
3593 }
3594
3595 /* Return true when store to register X can be hoisted to the place
3596    with LIVE registers (can be NULL).  Value VAL contains destination
3597    whose value will be used.  */
3598
3599 static bool
3600 hoist_test_store (x, val, live)
3601      rtx x, val;
3602      regset live;
3603 {
3604   if (GET_CODE (x) == SCRATCH)
3605     return true;
3606
3607   if (rtx_equal_p (x, val))
3608     return true;
3609
3610   /* Allow subreg of X in case it is not writting just part of multireg pseudo.
3611      Then we would need to update all users to care hoisting the store too.
3612      Caller may represent that by specifying whole subreg as val.  */
3613
3614   if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val))
3615     {
3616       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
3617           && GET_MODE_BITSIZE (GET_MODE (x)) <
3618           GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
3619         return false;
3620       return true;
3621     }
3622   if (GET_CODE (x) == SUBREG)
3623     x = SUBREG_REG (x);
3624
3625   /* Anything except register store is not hoistable.  This includes the
3626      partial stores to registers.  */
3627
3628   if (!REG_P (x))
3629     return false;
3630
3631   /* Pseudo registers can be allways replaced by another pseudo to avoid
3632      the side effect, for hard register we must ensure that they are dead.
3633      Eventually we may want to add code to try turn pseudos to hards, but it
3634      is unlikely useful.  */
3635
3636   if (REGNO (x) < FIRST_PSEUDO_REGISTER)
3637     {
3638       int regno = REGNO (x);
3639       int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
3640
3641       if (!live)
3642         return false;
3643       if (REGNO_REG_SET_P (live, regno))
3644         return false;
3645       while (--n > 0)
3646         if (REGNO_REG_SET_P (live, regno + n))
3647           return false;
3648     }
3649   return true;
3650 }
3651
3652
3653 /* Return true if INSN can be hoisted to place with LIVE hard registers
3654    (LIVE can be NULL when unknown).  VAL is expected to be stored by the insn
3655    and used by the hoisting pass.  */
3656
3657 bool
3658 can_hoist_insn_p (insn, val, live)
3659      rtx insn, val;
3660      regset live;
3661 {
3662   rtx pat = PATTERN (insn);
3663   int i;
3664
3665   /* It probably does not worth the complexity to handle multiple
3666      set stores.  */
3667   if (!single_set (insn))
3668     return false;
3669   /* We can move CALL_INSN, but we need to check that all caller clobbered
3670      regs are dead.  */
3671   if (GET_CODE (insn) == CALL_INSN)
3672     return false;
3673   /* In future we will handle hoisting of libcall sequences, but
3674      give up for now.  */
3675   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
3676     return false;
3677   switch (GET_CODE (pat))
3678     {
3679     case SET:
3680       if (!hoist_test_store (SET_DEST (pat), val, live))
3681         return false;
3682       break;
3683     case USE:
3684       /* USES do have sick semantics, so do not move them.  */
3685       return false;
3686       break;
3687     case CLOBBER:
3688       if (!hoist_test_store (XEXP (pat, 0), val, live))
3689         return false;
3690       break;
3691     case PARALLEL:
3692       for (i = 0; i < XVECLEN (pat, 0); i++)
3693         {
3694           rtx x = XVECEXP (pat, 0, i);
3695           switch (GET_CODE (x))
3696             {
3697             case SET:
3698               if (!hoist_test_store (SET_DEST (x), val, live))
3699                 return false;
3700               break;
3701             case USE:
3702               /* We need to fix callers to really ensure availability
3703                  of all values inisn uses, but for now it is safe to prohibit
3704                  hoisting of any insn having such a hidden uses.  */
3705               return false;
3706               break;
3707             case CLOBBER:
3708               if (!hoist_test_store (SET_DEST (x), val, live))
3709                 return false;
3710               break;
3711             default:
3712               break;
3713             }
3714         }
3715       break;
3716     default:
3717       abort ();
3718     }
3719   return true;
3720 }
3721
3722 /* Update store after hoisting - replace all stores to pseudo registers
3723    by new ones to avoid clobbering of values except for store to VAL that will
3724    be updated to NEW.  */
3725
3726 static void
3727 hoist_update_store (insn, xp, val, new)
3728      rtx insn, *xp, val, new;
3729 {
3730   rtx x = *xp;
3731
3732   if (GET_CODE (x) == SCRATCH)
3733     return;
3734
3735   if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val)
3736     validate_change (insn, xp,
3737                      simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new),
3738                                           SUBREG_BYTE (x)), 1);
3739   if (rtx_equal_p (x, val))
3740     {
3741       validate_change (insn, xp, new, 1);
3742       return;
3743     }
3744   if (GET_CODE (x) == SUBREG)
3745     {
3746       xp = &SUBREG_REG (x);
3747       x = *xp;
3748     }
3749
3750   if (!REG_P (x))
3751     abort ();
3752
3753   /* We've verified that hard registers are dead, so we may keep the side
3754      effect.  Otherwise replace it by new pseudo.  */
3755   if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
3756     validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1);
3757   REG_NOTES (insn)
3758     = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn));
3759 }
3760
3761 /* Create a copy of INSN after AFTER replacing store of VAL to NEW
3762    and each other side effect to pseudo register by new pseudo register.  */
3763
3764 rtx
3765 hoist_insn_after (insn, after, val, new)
3766      rtx insn, after, val, new;
3767 {
3768   rtx pat;
3769   int i;
3770   rtx note;
3771
3772   insn = emit_copy_of_insn_after (insn, after);
3773   pat = PATTERN (insn);
3774
3775   /* Remove REG_UNUSED notes as we will re-emit them.  */
3776   while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX)))
3777     remove_note (insn, note);
3778
3779   /* To get this working callers must ensure to move everything referenced
3780      by REG_EQUAL/REG_EQUIV notes too.  Lets remove them, it is probably
3781      easier.  */
3782   while ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX)))
3783     remove_note (insn, note);
3784   while ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)))
3785     remove_note (insn, note);
3786
3787   /* Remove REG_DEAD notes as they might not be valid anymore in case
3788      we create redundancy.  */
3789   while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX)))
3790     remove_note (insn, note);
3791   switch (GET_CODE (pat))
3792     {
3793     case SET:
3794       hoist_update_store (insn, &SET_DEST (pat), val, new);
3795       break;
3796     case USE:
3797       break;
3798     case CLOBBER:
3799       hoist_update_store (insn, &XEXP (pat, 0), val, new);
3800       break;
3801     case PARALLEL:
3802       for (i = 0; i < XVECLEN (pat, 0); i++)
3803         {
3804           rtx x = XVECEXP (pat, 0, i);
3805           switch (GET_CODE (x))
3806             {
3807             case SET:
3808               hoist_update_store (insn, &SET_DEST (x), val, new);
3809               break;
3810             case USE:
3811               break;
3812             case CLOBBER:
3813               hoist_update_store (insn, &SET_DEST (x), val, new);
3814               break;
3815             default:
3816               break;
3817             }
3818         }
3819       break;
3820     default:
3821       abort ();
3822     }
3823   if (!apply_change_group ())
3824     abort ();
3825
3826   return insn;
3827 }
3828
3829 rtx
3830 hoist_insn_to_edge (insn, e, val, new)
3831      rtx insn, val, new;
3832      edge e;
3833 {
3834   rtx new_insn;
3835
3836   /* We cannot insert instructions on an abnormal critical edge.
3837      It will be easier to find the culprit if we die now.  */
3838   if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
3839     abort ();
3840
3841   /* Do not use emit_insn_on_edge as we want to preserve notes and similar
3842      stuff.  We also emit CALL_INSNS and firends.  */
3843   if (e->insns == NULL_RTX)
3844     {
3845       start_sequence ();
3846       emit_note (NULL, NOTE_INSN_DELETED);
3847     }
3848   else
3849     push_to_sequence (e->insns);
3850
3851   new_insn = hoist_insn_after (insn, get_last_insn (), val, new);
3852
3853   e->insns = get_insns ();
3854   end_sequence ();
3855   return new_insn;
3856 }