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 old_label = ((replace_label_data *) data)->r1;
2719   rtx new_label = ((replace_label_data *) data)->r2;
2720   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2721
2722   if (l == NULL_RTX)
2723     return 0;
2724
2725   if (GET_CODE (l) == SYMBOL_REF
2726       && CONSTANT_POOL_ADDRESS_P (l))
2727     {
2728       rtx c = get_pool_constant (l);
2729       if (rtx_referenced_p (old_label, c))
2730         {
2731           rtx new_c, new_l;
2732           replace_label_data *d = (replace_label_data *) data;
2733
2734           /* Create a copy of constant C; replace the label inside
2735              but do not update LABEL_NUSES because uses in constant pool
2736              are not counted.  */
2737           new_c = copy_rtx (c);
2738           d->update_label_nuses = false;
2739           for_each_rtx (&new_c, replace_label, data);
2740           d->update_label_nuses = update_label_nuses;
2741
2742           /* Add the new constant NEW_C to constant pool and replace
2743              the old reference to constant by new reference.  */
2744           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2745           *x = replace_rtx (l, l, new_l);
2746         }
2747       return 0;
2748     }
2749
2750   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2751      field.  This is not handled by for_each_rtx because it doesn't
2752      handle unprinted ('0') fields.  */
2753   if (GET_CODE (l) == JUMP_INSN && JUMP_LABEL (l) == old_label)
2754     JUMP_LABEL (l) = new_label;
2755
2756   if ((GET_CODE (l) == LABEL_REF
2757        || GET_CODE (l) == INSN_LIST)
2758       && XEXP (l, 0) == old_label)
2759     {
2760       XEXP (l, 0) = new_label;
2761       if (update_label_nuses)
2762         {
2763           ++LABEL_NUSES (new_label);
2764           --LABEL_NUSES (old_label);
2765         }
2766       return 0;
2767     }
2768
2769   return 0;
2770 }
2771
2772 /* When *BODY is equal to X or X is directly referenced by *BODY
2773    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2774    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2775
2776 static int
2777 rtx_referenced_p_1 (rtx *body, void *x)
2778 {
2779   rtx y = (rtx) x;
2780
2781   if (*body == NULL_RTX)
2782     return y == NULL_RTX;
2783
2784   /* Return true if a label_ref *BODY refers to label Y.  */
2785   if (GET_CODE (*body) == LABEL_REF && GET_CODE (y) == CODE_LABEL)
2786     return XEXP (*body, 0) == y;
2787
2788   /* If *BODY is a reference to pool constant traverse the constant.  */
2789   if (GET_CODE (*body) == SYMBOL_REF
2790       && CONSTANT_POOL_ADDRESS_P (*body))
2791     return rtx_referenced_p (y, get_pool_constant (*body));
2792
2793   /* By default, compare the RTL expressions.  */
2794   return rtx_equal_p (*body, y);
2795 }
2796
2797 /* Return true if X is referenced in BODY.  */
2798
2799 int
2800 rtx_referenced_p (rtx x, rtx body)
2801 {
2802   return for_each_rtx (&body, rtx_referenced_p_1, x);
2803 }
2804
2805 /* If INSN is a tablejump return true and store the label (before jump table) to
2806    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2807
2808 bool
2809 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2810 {
2811   rtx label, table;
2812
2813   if (GET_CODE (insn) == JUMP_INSN
2814       && (label = JUMP_LABEL (insn)) != NULL_RTX
2815       && (table = next_active_insn (label)) != NULL_RTX
2816       && GET_CODE (table) == JUMP_INSN
2817       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2818           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2819     {
2820       if (labelp)
2821         *labelp = label;
2822       if (tablep)
2823         *tablep = table;
2824       return true;
2825     }
2826   return false;
2827 }
2828
2829 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2830    constant that is not in the constant pool and not in the condition
2831    of an IF_THEN_ELSE.  */
2832
2833 static int
2834 computed_jump_p_1 (rtx x)
2835 {
2836   enum rtx_code code = GET_CODE (x);
2837   int i, j;
2838   const char *fmt;
2839
2840   switch (code)
2841     {
2842     case LABEL_REF:
2843     case PC:
2844       return 0;
2845
2846     case CONST:
2847     case CONST_INT:
2848     case CONST_DOUBLE:
2849     case CONST_VECTOR:
2850     case SYMBOL_REF:
2851     case REG:
2852       return 1;
2853
2854     case MEM:
2855       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2856                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2857
2858     case IF_THEN_ELSE:
2859       return (computed_jump_p_1 (XEXP (x, 1))
2860               || computed_jump_p_1 (XEXP (x, 2)));
2861
2862     default:
2863       break;
2864     }
2865
2866   fmt = GET_RTX_FORMAT (code);
2867   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2868     {
2869       if (fmt[i] == 'e'
2870           && computed_jump_p_1 (XEXP (x, i)))
2871         return 1;
2872
2873       else if (fmt[i] == 'E')
2874         for (j = 0; j < XVECLEN (x, i); j++)
2875           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2876             return 1;
2877     }
2878
2879   return 0;
2880 }
2881
2882 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2883
2884    Tablejumps and casesi insns are not considered indirect jumps;
2885    we can recognize them by a (use (label_ref)).  */
2886
2887 int
2888 computed_jump_p (rtx insn)
2889 {
2890   int i;
2891   if (GET_CODE (insn) == JUMP_INSN)
2892     {
2893       rtx pat = PATTERN (insn);
2894
2895       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2896         return 0;
2897       else if (GET_CODE (pat) == PARALLEL)
2898         {
2899           int len = XVECLEN (pat, 0);
2900           int has_use_labelref = 0;
2901
2902           for (i = len - 1; i >= 0; i--)
2903             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2904                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2905                     == LABEL_REF))
2906               has_use_labelref = 1;
2907
2908           if (! has_use_labelref)
2909             for (i = len - 1; i >= 0; i--)
2910               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2911                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2912                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2913                 return 1;
2914         }
2915       else if (GET_CODE (pat) == SET
2916                && SET_DEST (pat) == pc_rtx
2917                && computed_jump_p_1 (SET_SRC (pat)))
2918         return 1;
2919     }
2920   return 0;
2921 }
2922
2923 /* Traverse X via depth-first search, calling F for each
2924    sub-expression (including X itself).  F is also passed the DATA.
2925    If F returns -1, do not traverse sub-expressions, but continue
2926    traversing the rest of the tree.  If F ever returns any other
2927    nonzero value, stop the traversal, and return the value returned
2928    by F.  Otherwise, return 0.  This function does not traverse inside
2929    tree structure that contains RTX_EXPRs, or into sub-expressions
2930    whose format code is `0' since it is not known whether or not those
2931    codes are actually RTL.
2932
2933    This routine is very general, and could (should?) be used to
2934    implement many of the other routines in this file.  */
2935
2936 int
2937 for_each_rtx (rtx *x, rtx_function f, void *data)
2938 {
2939   int result;
2940   int length;
2941   const char *format;
2942   int i;
2943
2944   /* Call F on X.  */
2945   result = (*f) (x, data);
2946   if (result == -1)
2947     /* Do not traverse sub-expressions.  */
2948     return 0;
2949   else if (result != 0)
2950     /* Stop the traversal.  */
2951     return result;
2952
2953   if (*x == NULL_RTX)
2954     /* There are no sub-expressions.  */
2955     return 0;
2956
2957   length = GET_RTX_LENGTH (GET_CODE (*x));
2958   format = GET_RTX_FORMAT (GET_CODE (*x));
2959
2960   for (i = 0; i < length; ++i)
2961     {
2962       switch (format[i])
2963         {
2964         case 'e':
2965           result = for_each_rtx (&XEXP (*x, i), f, data);
2966           if (result != 0)
2967             return result;
2968           break;
2969
2970         case 'V':
2971         case 'E':
2972           if (XVEC (*x, i) != 0)
2973             {
2974               int j;
2975               for (j = 0; j < XVECLEN (*x, i); ++j)
2976                 {
2977                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
2978                   if (result != 0)
2979                     return result;
2980                 }
2981             }
2982           break;
2983
2984         default:
2985           /* Nothing to do.  */
2986           break;
2987         }
2988
2989     }
2990
2991   return 0;
2992 }
2993
2994 /* Searches X for any reference to REGNO, returning the rtx of the
2995    reference found if any.  Otherwise, returns NULL_RTX.  */
2996
2997 rtx
2998 regno_use_in (unsigned int regno, rtx x)
2999 {
3000   const char *fmt;
3001   int i, j;
3002   rtx tem;
3003
3004   if (GET_CODE (x) == REG && REGNO (x) == regno)
3005     return x;
3006
3007   fmt = GET_RTX_FORMAT (GET_CODE (x));
3008   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3009     {
3010       if (fmt[i] == 'e')
3011         {
3012           if ((tem = regno_use_in (regno, XEXP (x, i))))
3013             return tem;
3014         }
3015       else if (fmt[i] == 'E')
3016         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3017           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
3018             return tem;
3019     }
3020
3021   return NULL_RTX;
3022 }
3023
3024 /* Return a value indicating whether OP, an operand of a commutative
3025    operation, is preferred as the first or second operand.  The higher
3026    the value, the stronger the preference for being the first operand.
3027    We use negative values to indicate a preference for the first operand
3028    and positive values for the second operand.  */
3029
3030 int
3031 commutative_operand_precedence (rtx op)
3032 {
3033   enum rtx_code code = GET_CODE (op);
3034   char class;
3035
3036   /* Constants always come the second operand.  Prefer "nice" constants.  */
3037   if (code == CONST_INT)
3038     return -7;
3039   if (code == CONST_DOUBLE)
3040     return -6;
3041   op = avoid_constant_pool_reference (op);
3042   if (code == CONST_INT)
3043     return -5;
3044   if (code == CONST_DOUBLE)
3045     return -4;
3046   if (CONSTANT_P (op))
3047     return -3;
3048
3049   /* SUBREGs of objects should come second.  */
3050   if (code == SUBREG
3051       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
3052     return -2;
3053
3054   class = GET_RTX_CLASS (code);
3055
3056   /* Prefer operands that are themselves commutative to be first.
3057      This helps to make things linear.  In particular,
3058      (and (and (reg) (reg)) (not (reg))) is canonical.  */
3059   if (class == 'c')
3060     return 4;
3061
3062   /* If only one operand is a binary expression, it will be the first
3063      operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
3064      is canonical, although it will usually be further simplified.  */
3065   if (class == '2')
3066     return 2;
3067
3068   /* Then prefer NEG and NOT.  */
3069   if (code == NEG || code == NOT)
3070     return 1;
3071
3072   /* Complex expressions should be the first, so decrease priority
3073      of objects.  */
3074   if (GET_RTX_CLASS (code) == 'o')
3075     return -1;
3076   return 0;
3077 }
3078
3079 /* Return 1 iff it is necessary to swap operands of commutative operation
3080    in order to canonicalize expression.  */
3081
3082 int
3083 swap_commutative_operands_p (rtx x, rtx y)
3084 {
3085   return (commutative_operand_precedence (x)
3086           < commutative_operand_precedence (y));
3087 }
3088
3089 /* Return 1 if X is an autoincrement side effect and the register is
3090    not the stack pointer.  */
3091 int
3092 auto_inc_p (rtx x)
3093 {
3094   switch (GET_CODE (x))
3095     {
3096     case PRE_INC:
3097     case POST_INC:
3098     case PRE_DEC:
3099     case POST_DEC:
3100     case PRE_MODIFY:
3101     case POST_MODIFY:
3102       /* There are no REG_INC notes for SP.  */
3103       if (XEXP (x, 0) != stack_pointer_rtx)
3104         return 1;
3105     default:
3106       break;
3107     }
3108   return 0;
3109 }
3110
3111 /* Return 1 if the sequence of instructions beginning with FROM and up
3112    to and including TO is safe to move.  If NEW_TO is non-NULL, and
3113    the sequence is not already safe to move, but can be easily
3114    extended to a sequence which is safe, then NEW_TO will point to the
3115    end of the extended sequence.
3116
3117    For now, this function only checks that the region contains whole
3118    exception regions, but it could be extended to check additional
3119    conditions as well.  */
3120
3121 int
3122 insns_safe_to_move_p (rtx from, rtx to, rtx *new_to)
3123 {
3124   int eh_region_count = 0;
3125   int past_to_p = 0;
3126   rtx r = from;
3127
3128   /* By default, assume the end of the region will be what was
3129      suggested.  */
3130   if (new_to)
3131     *new_to = to;
3132
3133   while (r)
3134     {
3135       if (GET_CODE (r) == NOTE)
3136         {
3137           switch (NOTE_LINE_NUMBER (r))
3138             {
3139             case NOTE_INSN_EH_REGION_BEG:
3140               ++eh_region_count;
3141               break;
3142
3143             case NOTE_INSN_EH_REGION_END:
3144               if (eh_region_count == 0)
3145                 /* This sequence of instructions contains the end of
3146                    an exception region, but not he beginning.  Moving
3147                    it will cause chaos.  */
3148                 return 0;
3149
3150               --eh_region_count;
3151               break;
3152
3153             default:
3154               break;
3155             }
3156         }
3157       else if (past_to_p)
3158         /* If we've passed TO, and we see a non-note instruction, we
3159            can't extend the sequence to a movable sequence.  */
3160         return 0;
3161
3162       if (r == to)
3163         {
3164           if (!new_to)
3165             /* It's OK to move the sequence if there were matched sets of
3166                exception region notes.  */
3167             return eh_region_count == 0;
3168
3169           past_to_p = 1;
3170         }
3171
3172       /* It's OK to move the sequence if there were matched sets of
3173          exception region notes.  */
3174       if (past_to_p && eh_region_count == 0)
3175         {
3176           *new_to = r;
3177           return 1;
3178         }
3179
3180       /* Go to the next instruction.  */
3181       r = NEXT_INSN (r);
3182     }
3183
3184   return 0;
3185 }
3186
3187 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
3188 int
3189 loc_mentioned_in_p (rtx *loc, rtx in)
3190 {
3191   enum rtx_code code = GET_CODE (in);
3192   const char *fmt = GET_RTX_FORMAT (code);
3193   int i, j;
3194
3195   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3196     {
3197       if (loc == &in->u.fld[i].rtx)
3198         return 1;
3199       if (fmt[i] == 'e')
3200         {
3201           if (loc_mentioned_in_p (loc, XEXP (in, i)))
3202             return 1;
3203         }
3204       else if (fmt[i] == 'E')
3205         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
3206           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3207             return 1;
3208     }
3209   return 0;
3210 }
3211
3212 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
3213    and SUBREG_BYTE, return the bit offset where the subreg begins
3214    (counting from the least significant bit of the operand).  */
3215
3216 unsigned int
3217 subreg_lsb_1 (enum machine_mode outer_mode,
3218               enum machine_mode inner_mode,
3219               unsigned int subreg_byte)
3220 {
3221   unsigned int bitpos;
3222   unsigned int byte;
3223   unsigned int word;
3224
3225   /* A paradoxical subreg begins at bit position 0.  */
3226   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
3227     return 0;
3228
3229   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3230     /* If the subreg crosses a word boundary ensure that
3231        it also begins and ends on a word boundary.  */
3232     if ((subreg_byte % UNITS_PER_WORD
3233          + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
3234         && (subreg_byte % UNITS_PER_WORD
3235             || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD))
3236         abort ();
3237
3238   if (WORDS_BIG_ENDIAN)
3239     word = (GET_MODE_SIZE (inner_mode)
3240             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3241   else
3242     word = subreg_byte / UNITS_PER_WORD;
3243   bitpos = word * BITS_PER_WORD;
3244
3245   if (BYTES_BIG_ENDIAN)
3246     byte = (GET_MODE_SIZE (inner_mode)
3247             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3248   else
3249     byte = subreg_byte % UNITS_PER_WORD;
3250   bitpos += byte * BITS_PER_UNIT;
3251
3252   return bitpos;
3253 }
3254
3255 /* Given a subreg X, return the bit offset where the subreg begins
3256    (counting from the least significant bit of the reg).  */
3257
3258 unsigned int
3259 subreg_lsb (rtx x)
3260 {
3261   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3262                        SUBREG_BYTE (x));
3263 }
3264
3265 /* This function returns the regno offset of a subreg expression.
3266    xregno - A regno of an inner hard subreg_reg (or what will become one).
3267    xmode  - The mode of xregno.
3268    offset - The byte offset.
3269    ymode  - The mode of a top level SUBREG (or what may become one).
3270    RETURN - The regno offset which would be used.  */
3271 unsigned int
3272 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3273                      unsigned int offset, enum machine_mode ymode)
3274 {
3275   int nregs_xmode, nregs_ymode;
3276   int mode_multiple, nregs_multiple;
3277   int y_offset;
3278
3279   if (xregno >= FIRST_PSEUDO_REGISTER)
3280     abort ();
3281
3282   nregs_xmode = hard_regno_nregs[xregno][xmode];
3283   nregs_ymode = hard_regno_nregs[xregno][ymode];
3284
3285   /* If this is a big endian paradoxical subreg, which uses more actual
3286      hard registers than the original register, we must return a negative
3287      offset so that we find the proper highpart of the register.  */
3288   if (offset == 0
3289       && nregs_ymode > nregs_xmode
3290       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3291           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3292     return nregs_xmode - nregs_ymode;
3293
3294   if (offset == 0 || nregs_xmode == nregs_ymode)
3295     return 0;
3296
3297   /* size of ymode must not be greater than the size of xmode.  */
3298   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3299   if (mode_multiple == 0)
3300     abort ();
3301
3302   y_offset = offset / GET_MODE_SIZE (ymode);
3303   nregs_multiple =  nregs_xmode / nregs_ymode;
3304   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3305 }
3306
3307 /* This function returns true when the offset is representable via
3308    subreg_offset in the given regno.
3309    xregno - A regno of an inner hard subreg_reg (or what will become one).
3310    xmode  - The mode of xregno.
3311    offset - The byte offset.
3312    ymode  - The mode of a top level SUBREG (or what may become one).
3313    RETURN - The regno offset which would be used.  */
3314 bool
3315 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3316                                unsigned int offset, enum machine_mode ymode)
3317 {
3318   int nregs_xmode, nregs_ymode;
3319   int mode_multiple, nregs_multiple;
3320   int y_offset;
3321
3322   if (xregno >= FIRST_PSEUDO_REGISTER)
3323     abort ();
3324
3325   nregs_xmode = hard_regno_nregs[xregno][xmode];
3326   nregs_ymode = hard_regno_nregs[xregno][ymode];
3327
3328   /* paradoxical subregs are always valid.  */
3329   if (offset == 0
3330       && nregs_ymode > nregs_xmode
3331       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3332           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3333     return true;
3334
3335   /* Lowpart subregs are always valid.  */
3336   if (offset == subreg_lowpart_offset (ymode, xmode))
3337     return true;
3338
3339 #ifdef ENABLE_CHECKING
3340   /* This should always pass, otherwise we don't know how to verify the
3341      constraint.  These conditions may be relaxed but subreg_offset would
3342      need to be redesigned.  */
3343   if (GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)
3344       || GET_MODE_SIZE (ymode) % nregs_ymode
3345       || nregs_xmode % nregs_ymode)
3346     abort ();
3347 #endif
3348
3349   /* The XMODE value can be seen as a vector of NREGS_XMODE
3350      values.  The subreg must represent a lowpart of given field.
3351      Compute what field it is.  */
3352   offset -= subreg_lowpart_offset (ymode,
3353                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3354                                                   / nregs_xmode,
3355                                                   MODE_INT, 0));
3356
3357   /* size of ymode must not be greater than the size of xmode.  */
3358   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3359   if (mode_multiple == 0)
3360     abort ();
3361
3362   y_offset = offset / GET_MODE_SIZE (ymode);
3363   nregs_multiple =  nregs_xmode / nregs_ymode;
3364 #ifdef ENABLE_CHECKING
3365   if (offset % GET_MODE_SIZE (ymode)
3366       || mode_multiple % nregs_multiple)
3367     abort ();
3368 #endif
3369   return (!(y_offset % (mode_multiple / nregs_multiple)));
3370 }
3371
3372 /* Return the final regno that a subreg expression refers to.  */
3373 unsigned int
3374 subreg_regno (rtx x)
3375 {
3376   unsigned int ret;
3377   rtx subreg = SUBREG_REG (x);
3378   int regno = REGNO (subreg);
3379
3380   ret = regno + subreg_regno_offset (regno,
3381                                      GET_MODE (subreg),
3382                                      SUBREG_BYTE (x),
3383                                      GET_MODE (x));
3384   return ret;
3385
3386 }
3387 struct parms_set_data
3388 {
3389   int nregs;
3390   HARD_REG_SET regs;
3391 };
3392
3393 /* Helper function for noticing stores to parameter registers.  */
3394 static void
3395 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3396 {
3397   struct parms_set_data *d = data;
3398   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3399       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3400     {
3401       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3402       d->nregs--;
3403     }
3404 }
3405
3406 /* Look backward for first parameter to be loaded.
3407    Do not skip BOUNDARY.  */
3408 rtx
3409 find_first_parameter_load (rtx call_insn, rtx boundary)
3410 {
3411   struct parms_set_data parm;
3412   rtx p, before;
3413
3414   /* Since different machines initialize their parameter registers
3415      in different orders, assume nothing.  Collect the set of all
3416      parameter registers.  */
3417   CLEAR_HARD_REG_SET (parm.regs);
3418   parm.nregs = 0;
3419   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3420     if (GET_CODE (XEXP (p, 0)) == USE
3421         && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
3422       {
3423         if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
3424           abort ();
3425
3426         /* We only care about registers which can hold function
3427            arguments.  */
3428         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3429           continue;
3430
3431         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3432         parm.nregs++;
3433       }
3434   before = call_insn;
3435
3436   /* Search backward for the first set of a register in this set.  */
3437   while (parm.nregs && before != boundary)
3438     {
3439       before = PREV_INSN (before);
3440
3441       /* It is possible that some loads got CSEed from one call to
3442          another.  Stop in that case.  */
3443       if (GET_CODE (before) == CALL_INSN)
3444         break;
3445
3446       /* Our caller needs either ensure that we will find all sets
3447          (in case code has not been optimized yet), or take care
3448          for possible labels in a way by setting boundary to preceding
3449          CODE_LABEL.  */
3450       if (GET_CODE (before) == CODE_LABEL)
3451         {
3452           if (before != boundary)
3453             abort ();
3454           break;
3455         }
3456
3457       if (INSN_P (before))
3458         note_stores (PATTERN (before), parms_set, &parm);
3459     }
3460   return before;
3461 }
3462
3463 /* Return true if we should avoid inserting code between INSN and preceding
3464    call instruction.  */
3465
3466 bool
3467 keep_with_call_p (rtx insn)
3468 {
3469   rtx set;
3470
3471   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3472     {
3473       if (GET_CODE (SET_DEST (set)) == REG
3474           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3475           && fixed_regs[REGNO (SET_DEST (set))]
3476           && general_operand (SET_SRC (set), VOIDmode))
3477         return true;
3478       if (GET_CODE (SET_SRC (set)) == REG
3479           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3480           && GET_CODE (SET_DEST (set)) == REG
3481           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3482         return true;
3483       /* There may be a stack pop just after the call and before the store
3484          of the return register.  Search for the actual store when deciding
3485          if we can break or not.  */
3486       if (SET_DEST (set) == stack_pointer_rtx)
3487         {
3488           rtx i2 = next_nonnote_insn (insn);
3489           if (i2 && keep_with_call_p (i2))
3490             return true;
3491         }
3492     }
3493   return false;
3494 }
3495
3496 /* Return true when store to register X can be hoisted to the place
3497    with LIVE registers (can be NULL).  Value VAL contains destination
3498    whose value will be used.  */
3499
3500 static bool
3501 hoist_test_store (rtx x, rtx val, regset live)
3502 {
3503   if (GET_CODE (x) == SCRATCH)
3504     return true;
3505
3506   if (rtx_equal_p (x, val))
3507     return true;
3508
3509   /* Allow subreg of X in case it is not writing just part of multireg pseudo.
3510      Then we would need to update all users to care hoisting the store too.
3511      Caller may represent that by specifying whole subreg as val.  */
3512
3513   if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val))
3514     {
3515       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
3516           && GET_MODE_BITSIZE (GET_MODE (x)) <
3517           GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
3518         return false;
3519       return true;
3520     }
3521   if (GET_CODE (x) == SUBREG)
3522     x = SUBREG_REG (x);
3523
3524   /* Anything except register store is not hoistable.  This includes the
3525      partial stores to registers.  */
3526
3527   if (!REG_P (x))
3528     return false;
3529
3530   /* Pseudo registers can be always replaced by another pseudo to avoid
3531      the side effect, for hard register we must ensure that they are dead.
3532      Eventually we may want to add code to try turn pseudos to hards, but it
3533      is unlikely useful.  */
3534
3535   if (REGNO (x) < FIRST_PSEUDO_REGISTER)
3536     {
3537       int regno = REGNO (x);
3538       int n = hard_regno_nregs[regno][GET_MODE (x)];
3539
3540       if (!live)
3541         return false;
3542       if (REGNO_REG_SET_P (live, regno))
3543         return false;
3544       while (--n > 0)
3545         if (REGNO_REG_SET_P (live, regno + n))
3546           return false;
3547     }
3548   return true;
3549 }
3550
3551
3552 /* Return true if INSN can be hoisted to place with LIVE hard registers
3553    (LIVE can be NULL when unknown).  VAL is expected to be stored by the insn
3554    and used by the hoisting pass.  */
3555
3556 bool
3557 can_hoist_insn_p (rtx insn, rtx val, regset live)
3558 {
3559   rtx pat = PATTERN (insn);
3560   int i;
3561
3562   /* It probably does not worth the complexity to handle multiple
3563      set stores.  */
3564   if (!single_set (insn))
3565     return false;
3566   /* We can move CALL_INSN, but we need to check that all caller clobbered
3567      regs are dead.  */
3568   if (GET_CODE (insn) == CALL_INSN)
3569     return false;
3570   /* In future we will handle hoisting of libcall sequences, but
3571      give up for now.  */
3572   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
3573     return false;
3574   switch (GET_CODE (pat))
3575     {
3576     case SET:
3577       if (!hoist_test_store (SET_DEST (pat), val, live))
3578         return false;
3579       break;
3580     case USE:
3581       /* USES do have sick semantics, so do not move them.  */
3582       return false;
3583       break;
3584     case CLOBBER:
3585       if (!hoist_test_store (XEXP (pat, 0), val, live))
3586         return false;
3587       break;
3588     case PARALLEL:
3589       for (i = 0; i < XVECLEN (pat, 0); i++)
3590         {
3591           rtx x = XVECEXP (pat, 0, i);
3592           switch (GET_CODE (x))
3593             {
3594             case SET:
3595               if (!hoist_test_store (SET_DEST (x), val, live))
3596                 return false;
3597               break;
3598             case USE:
3599               /* We need to fix callers to really ensure availability
3600                  of all values insn uses, but for now it is safe to prohibit
3601                  hoisting of any insn having such a hidden uses.  */
3602               return false;
3603               break;
3604             case CLOBBER:
3605               if (!hoist_test_store (SET_DEST (x), val, live))
3606                 return false;
3607               break;
3608             default:
3609               break;
3610             }
3611         }
3612       break;
3613     default:
3614       abort ();
3615     }
3616   return true;
3617 }
3618
3619 /* Update store after hoisting - replace all stores to pseudo registers
3620    by new ones to avoid clobbering of values except for store to VAL that will
3621    be updated to NEW.  */
3622
3623 static void
3624 hoist_update_store (rtx insn, rtx *xp, rtx val, rtx new)
3625 {
3626   rtx x = *xp;
3627
3628   if (GET_CODE (x) == SCRATCH)
3629     return;
3630
3631   if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val)
3632     validate_change (insn, xp,
3633                      simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new),
3634                                           SUBREG_BYTE (x)), 1);
3635   if (rtx_equal_p (x, val))
3636     {
3637       validate_change (insn, xp, new, 1);
3638       return;
3639     }
3640   if (GET_CODE (x) == SUBREG)
3641     {
3642       xp = &SUBREG_REG (x);
3643       x = *xp;
3644     }
3645
3646   if (!REG_P (x))
3647     abort ();
3648
3649   /* We've verified that hard registers are dead, so we may keep the side
3650      effect.  Otherwise replace it by new pseudo.  */
3651   if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
3652     validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1);
3653   REG_NOTES (insn)
3654     = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn));
3655 }
3656
3657 /* Create a copy of INSN after AFTER replacing store of VAL to NEW
3658    and each other side effect to pseudo register by new pseudo register.  */
3659
3660 rtx
3661 hoist_insn_after (rtx insn, rtx after, rtx val, rtx new)
3662 {
3663   rtx pat;
3664   int i;
3665   rtx note;
3666
3667   insn = emit_copy_of_insn_after (insn, after);
3668   pat = PATTERN (insn);
3669
3670   /* Remove REG_UNUSED notes as we will re-emit them.  */
3671   while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX)))
3672     remove_note (insn, note);
3673
3674   /* To get this working callers must ensure to move everything referenced
3675      by REG_EQUAL/REG_EQUIV notes too.  Lets remove them, it is probably
3676      easier.  */
3677   while ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX)))
3678     remove_note (insn, note);
3679   while ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)))
3680     remove_note (insn, note);
3681
3682   /* Remove REG_DEAD notes as they might not be valid anymore in case
3683      we create redundancy.  */
3684   while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX)))
3685     remove_note (insn, note);
3686   switch (GET_CODE (pat))
3687     {
3688     case SET:
3689       hoist_update_store (insn, &SET_DEST (pat), val, new);
3690       break;
3691     case USE:
3692       break;
3693     case CLOBBER:
3694       hoist_update_store (insn, &XEXP (pat, 0), val, new);
3695       break;
3696     case PARALLEL:
3697       for (i = 0; i < XVECLEN (pat, 0); i++)
3698         {
3699           rtx x = XVECEXP (pat, 0, i);
3700           switch (GET_CODE (x))
3701             {
3702             case SET:
3703               hoist_update_store (insn, &SET_DEST (x), val, new);
3704               break;
3705             case USE:
3706               break;
3707             case CLOBBER:
3708               hoist_update_store (insn, &SET_DEST (x), val, new);
3709               break;
3710             default:
3711               break;
3712             }
3713         }
3714       break;
3715     default:
3716       abort ();
3717     }
3718   if (!apply_change_group ())
3719     abort ();
3720
3721   return insn;
3722 }
3723
3724 rtx
3725 hoist_insn_to_edge (rtx insn, edge e, rtx val, rtx new)
3726 {
3727   rtx new_insn;
3728
3729   /* We cannot insert instructions on an abnormal critical edge.
3730      It will be easier to find the culprit if we die now.  */
3731   if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
3732     abort ();
3733
3734   /* Do not use emit_insn_on_edge as we want to preserve notes and similar
3735      stuff.  We also emit CALL_INSNS and friends.  */
3736   if (e->insns == NULL_RTX)
3737     {
3738       start_sequence ();
3739       emit_note (NOTE_INSN_DELETED);
3740     }
3741   else
3742     push_to_sequence (e->insns);
3743
3744   new_insn = hoist_insn_after (insn, get_last_insn (), val, new);
3745
3746   e->insns = get_insns ();
3747   end_sequence ();
3748   return new_insn;
3749 }
3750
3751 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3752    to non-complex jumps.  That is, direct unconditional, conditional,
3753    and tablejumps, but not computed jumps or returns.  It also does
3754    not apply to the fallthru case of a conditional jump.  */
3755
3756 bool
3757 label_is_jump_target_p (rtx label, rtx jump_insn)
3758 {
3759   rtx tmp = JUMP_LABEL (jump_insn);
3760
3761   if (label == tmp)
3762     return true;
3763
3764   if (tablejump_p (jump_insn, NULL, &tmp))
3765     {
3766       rtvec vec = XVEC (PATTERN (tmp),
3767                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3768       int i, veclen = GET_NUM_ELEM (vec);
3769
3770       for (i = 0; i < veclen; ++i)
3771         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3772           return true;
3773     }
3774
3775   return false;
3776 }
3777