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