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