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 "target.h"
  33 #include "output.h"
  34 #include "tm_p.h"
  35 #include "flags.h"
  36 #include "basic-block.h"
  37 #include "real.h"
  38 #include "regs.h"
  39 #include "function.h"
  40
  41 /* Forward declarations */
  42 static int global_reg_mentioned_p_1 (rtx *, void *);
  43 static void set_of_1 (rtx, rtx, void *);
  44 static void insn_dependent_p_1 (rtx, rtx, void *);
  45 static int rtx_referenced_p_1 (rtx *, void *);
  46 static int computed_jump_p_1 (rtx);
  47 static void parms_set (rtx, rtx, void *);
  48 static bool hoist_test_store (rtx, rtx, regset);
  49 static void hoist_update_store (rtx, rtx *, rtx, rtx);
  50
  51 static unsigned HOST_WIDE_INT cached_nonzero_bits (rtx, enum machine_mode,
  52                                                    rtx, enum machine_mode,
  53                                                    unsigned HOST_WIDE_INT);
  54 static unsigned HOST_WIDE_INT nonzero_bits1 (rtx, enum machine_mode, rtx,
  55                                              enum machine_mode,
  56                                              unsigned HOST_WIDE_INT);
  57 static unsigned int cached_num_sign_bit_copies (rtx, enum machine_mode, rtx,
  58                                                 enum machine_mode,
  59                                                 unsigned int);
  60 static unsigned int num_sign_bit_copies1 (rtx, enum machine_mode, rtx,
  61                                           enum machine_mode, unsigned int);
  62
  63 /* Bit flags that specify the machine subtype we are compiling for.
  64    Bits are tested using macros TARGET_... defined in the tm.h file
  65    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
  66
  67 int target_flags;
  68 \f
  69 /* Return 1 if the value of X is unstable
  70    (would be different at a different point in the program).
  71    The frame pointer, arg pointer, etc. are considered stable
  72    (within one function) and so is anything marked `unchanging'.  */
  73
  74 int
  75 rtx_unstable_p (rtx x)
  76 {
  77   RTX_CODE code = GET_CODE (x);
  78   int i;
  79   const char *fmt;
  80
  81   switch (code)
  82     {
  83     case MEM:
  84       return ! RTX_UNCHANGING_P (x) || rtx_unstable_p (XEXP (x, 0));
  85
  86     case QUEUED:
  87       return 1;
  88
  89     case ADDRESSOF:
  90     case CONST:
  91     case CONST_INT:
  92     case CONST_DOUBLE:
  93     case CONST_VECTOR:
  94     case SYMBOL_REF:
  95     case LABEL_REF:
  96       return 0;
  97
  98     case REG:
  99       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 100       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 101           /* The arg pointer varies if it is not a fixed register.  */
 102           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
 103           || RTX_UNCHANGING_P (x))
 104         return 0;
 105 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
 106       /* ??? When call-clobbered, the value is stable modulo the restore
 107          that must happen after a call.  This currently screws up local-alloc
 108          into believing that the restore is not needed.  */
 109       if (x == pic_offset_table_rtx)
 110         return 0;
 111 #endif
 112       return 1;
 113
 114     case ASM_OPERANDS:
 115       if (MEM_VOLATILE_P (x))
 116         return 1;
 117
 118       /* Fall through.  */
 119
 120     default:
 121       break;
 122     }
 123
 124   fmt = GET_RTX_FORMAT (code);
 125   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 126     if (fmt[i] == 'e')
 127       {
 128         if (rtx_unstable_p (XEXP (x, i)))
 129           return 1;
 130       }
 131     else if (fmt[i] == 'E')
 132       {
 133         int j;
 134         for (j = 0; j < XVECLEN (x, i); j++)
 135           if (rtx_unstable_p (XVECEXP (x, i, j)))
 136             return 1;
 137       }
 138
 139   return 0;
 140 }
 141
 142 /* Return 1 if X has a value that can vary even between two
 143    executions of the program.  0 means X can be compared reliably
 144    against certain constants or near-constants.
 145    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 146    zero, we are slightly more conservative.
 147    The frame pointer and the arg pointer are considered constant.  */
 148
 149 int
 150 rtx_varies_p (rtx x, int for_alias)
 151 {
 152   RTX_CODE code;
 153   int i;
 154   const char *fmt;
 155
 156   if (!x)
 157     return 0;
 158
 159   code = GET_CODE (x);
 160   switch (code)
 161     {
 162     case MEM:
 163       return ! RTX_UNCHANGING_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
 164
 165     case QUEUED:
 166       return 1;
 167
 168     case CONST:
 169     case CONST_INT:
 170     case CONST_DOUBLE:
 171     case CONST_VECTOR:
 172     case SYMBOL_REF:
 173     case LABEL_REF:
 174       return 0;
 175
 176     case ADDRESSOF:
 177       /* This will resolve to some offset from the frame pointer.  */
 178       return 0;
 179
 180     case REG:
 181       /* Note that we have to test for the actual rtx used for the frame
 182          and arg pointers and not just the register number in case we have
 183          eliminated the frame and/or arg pointer and are using it
 184          for pseudos.  */
 185       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 186           /* The arg pointer varies if it is not a fixed register.  */
 187           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 188         return 0;
 189       if (x == pic_offset_table_rtx
 190 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
 191           /* ??? When call-clobbered, the value is stable modulo the restore
 192              that must happen after a call.  This currently screws up
 193              local-alloc into believing that the restore is not needed, so we
 194              must return 0 only if we are called from alias analysis.  */
 195           && for_alias
 196 #endif
 197           )
 198         return 0;
 199       return 1;
 200
 201     case LO_SUM:
 202       /* The operand 0 of a LO_SUM is considered constant
 203          (in fact it is related specifically to operand 1)
 204          during alias analysis.  */
 205       return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
 206              || rtx_varies_p (XEXP (x, 1), for_alias);
 207
 208     case ASM_OPERANDS:
 209       if (MEM_VOLATILE_P (x))
 210         return 1;
 211
 212       /* Fall through.  */
 213
 214     default:
 215       break;
 216     }
 217
 218   fmt = GET_RTX_FORMAT (code);
 219   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 220     if (fmt[i] == 'e')
 221       {
 222         if (rtx_varies_p (XEXP (x, i), for_alias))
 223           return 1;
 224       }
 225     else if (fmt[i] == 'E')
 226       {
 227         int j;
 228         for (j = 0; j < XVECLEN (x, i); j++)
 229           if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
 230             return 1;
 231       }
 232
 233   return 0;
 234 }
 235
 236 /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
 237
 238 int
 239 rtx_addr_can_trap_p (rtx x)
 240 {
 241   enum rtx_code code = GET_CODE (x);
 242
 243   switch (code)
 244     {
 245     case SYMBOL_REF:
 246       return SYMBOL_REF_WEAK (x);
 247
 248     case LABEL_REF:
 249       return 0;
 250
 251     case ADDRESSOF:
 252       /* This will resolve to some offset from the frame pointer.  */
 253       return 0;
 254
 255     case REG:
 256       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 257       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 258           || x == stack_pointer_rtx
 259           /* The arg pointer varies if it is not a fixed register.  */
 260           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 261         return 0;
 262       /* All of the virtual frame registers are stack references.  */
 263       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
 264           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
 265         return 0;
 266       return 1;
 267
 268     case CONST:
 269       return rtx_addr_can_trap_p (XEXP (x, 0));
 270
 271     case PLUS:
 272       /* An address is assumed not to trap if it is an address that can't
 273          trap plus a constant integer or it is the pic register plus a
 274          constant.  */
 275       return ! ((! rtx_addr_can_trap_p (XEXP (x, 0))
 276                  && GET_CODE (XEXP (x, 1)) == CONST_INT)
 277                 || (XEXP (x, 0) == pic_offset_table_rtx
 278                     && CONSTANT_P (XEXP (x, 1))));
 279
 280     case LO_SUM:
 281     case PRE_MODIFY:
 282       return rtx_addr_can_trap_p (XEXP (x, 1));
 283
 284     case PRE_DEC:
 285     case PRE_INC:
 286     case POST_DEC:
 287     case POST_INC:
 288     case POST_MODIFY:
 289       return rtx_addr_can_trap_p (XEXP (x, 0));
 290
 291     default:
 292       break;
 293     }
 294
 295   /* If it isn't one of the case above, it can cause a trap.  */
 296   return 1;
 297 }
 298
 299 /* Return true if X is an address that is known to not be zero.  */
 300
 301 bool
 302 nonzero_address_p (rtx x)
 303 {
 304   enum rtx_code code = GET_CODE (x);
 305
 306   switch (code)
 307     {
 308     case SYMBOL_REF:
 309       return !SYMBOL_REF_WEAK (x);
 310
 311     case LABEL_REF:
 312       return true;
 313
 314     case ADDRESSOF:
 315       /* This will resolve to some offset from the frame pointer.  */
 316       return true;
 317
 318     case REG:
 319       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
 320       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
 321           || x == stack_pointer_rtx
 322           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
 323         return true;
 324       /* All of the virtual frame registers are stack references.  */
 325       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
 326           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
 327         return true;
 328       return false;
 329
 330     case CONST:
 331       return nonzero_address_p (XEXP (x, 0));
 332
 333     case PLUS:
 334       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
 335         {
 336           /* Pointers aren't allowed to wrap.  If we've got a register
 337              that is known to be a pointer, and a positive offset, then
 338              the composite can't be zero.  */
 339           if (INTVAL (XEXP (x, 1)) > 0
 340               && REG_P (XEXP (x, 0))
 341               && REG_POINTER (XEXP (x, 0)))
 342             return true;
 343
 344           return nonzero_address_p (XEXP (x, 0));
 345         }
 346       /* Handle PIC references.  */
 347       else if (XEXP (x, 0) == pic_offset_table_rtx
 348                && CONSTANT_P (XEXP (x, 1)))
 349         return true;
 350       return false;
 351
 352     case PRE_MODIFY:
 353       /* Similar to the above; allow positive offsets.  Further, since
 354          auto-inc is only allowed in memories, the register must be a
 355          pointer.  */
 356       if (GET_CODE (XEXP (x, 1)) == CONST_INT
 357           && INTVAL (XEXP (x, 1)) > 0)
 358         return true;
 359       return nonzero_address_p (XEXP (x, 0));
 360
 361     case PRE_INC:
 362       /* Similarly.  Further, the offset is always positive.  */
 363       return true;
 364
 365     case PRE_DEC:
 366     case POST_DEC:
 367     case POST_INC:
 368     case POST_MODIFY:
 369       return nonzero_address_p (XEXP (x, 0));
 370
 371     case LO_SUM:
 372       return nonzero_address_p (XEXP (x, 1));
 373
 374     default:
 375       break;
 376     }
 377
 378   /* If it isn't one of the case above, might be zero.  */
 379   return false;
 380 }
 381
 382 /* Return 1 if X refers to a memory location whose address
 383    cannot be compared reliably with constant addresses,
 384    or if X refers to a BLKmode memory object.
 385    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
 386    zero, we are slightly more conservative.  */
 387
 388 int
 389 rtx_addr_varies_p (rtx x, int for_alias)
 390 {
 391   enum rtx_code code;
 392   int i;
 393   const char *fmt;
 394
 395   if (x == 0)
 396     return 0;
 397
 398   code = GET_CODE (x);
 399   if (code == MEM)
 400     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
 401
 402   fmt = GET_RTX_FORMAT (code);
 403   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 404     if (fmt[i] == 'e')
 405       {
 406         if (rtx_addr_varies_p (XEXP (x, i), for_alias))
 407           return 1;
 408       }
 409     else if (fmt[i] == 'E')
 410       {
 411         int j;
 412         for (j = 0; j < XVECLEN (x, i); j++)
 413           if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
 414             return 1;
 415       }
 416   return 0;
 417 }
 418 \f
 419 /* Return the value of the integer term in X, if one is apparent;
 420    otherwise return 0.
 421    Only obvious integer terms are detected.
 422    This is used in cse.c with the `related_value' field.  */
 423
 424 HOST_WIDE_INT
 425 get_integer_term (rtx x)
 426 {
 427   if (GET_CODE (x) == CONST)
 428     x = XEXP (x, 0);
 429
 430   if (GET_CODE (x) == MINUS
 431       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 432     return - INTVAL (XEXP (x, 1));
 433   if (GET_CODE (x) == PLUS
 434       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 435     return INTVAL (XEXP (x, 1));
 436   return 0;
 437 }
 438
 439 /* If X is a constant, return the value sans apparent integer term;
 440    otherwise return 0.
 441    Only obvious integer terms are detected.  */
 442
 443 rtx
 444 get_related_value (rtx x)
 445 {
 446   if (GET_CODE (x) != CONST)
 447     return 0;
 448   x = XEXP (x, 0);
 449   if (GET_CODE (x) == PLUS
 450       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 451     return XEXP (x, 0);
 452   else if (GET_CODE (x) == MINUS
 453            && GET_CODE (XEXP (x, 1)) == CONST_INT)
 454     return XEXP (x, 0);
 455   return 0;
 456 }
 457 \f
 458 /* Given a tablejump insn INSN, return the RTL expression for the offset
 459    into the jump table.  If the offset cannot be determined, then return
 460    NULL_RTX.
 461
 462    If EARLIEST is nonzero, it is a pointer to a place where the earliest
 463    insn used in locating the offset was found.  */
 464
 465 rtx
 466 get_jump_table_offset (rtx insn, rtx *earliest)
 467 {
 468   rtx label = NULL;
 469   rtx table = NULL;
 470   rtx set;
 471   rtx old_insn;
 472   rtx x;
 473   rtx old_x;
 474   rtx y;
 475   rtx old_y;
 476   int i;
 477
 478   if (!tablejump_p (insn, &label, &table) || !(set = single_set (insn)))
 479     return NULL_RTX;
 480
 481   x = SET_SRC (set);
 482
 483   /* Some targets (eg, ARM) emit a tablejump that also
 484      contains the out-of-range target.  */
 485   if (GET_CODE (x) == IF_THEN_ELSE
 486       && GET_CODE (XEXP (x, 2)) == LABEL_REF)
 487     x = XEXP (x, 1);
 488
 489   /* Search backwards and locate the expression stored in X.  */
 490   for (old_x = NULL_RTX; REG_P (x) && x != old_x;
 491        old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 492     ;
 493
 494   /* If X is an expression using a relative address then strip
 495      off the addition / subtraction of PC, PIC_OFFSET_TABLE_REGNUM,
 496      or the jump table label.  */
 497   if (GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC
 498       && (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS))
 499     {
 500       for (i = 0; i < 2; i++)
 501         {
 502           old_insn = insn;
 503           y = XEXP (x, i);
 504
 505           if (y == pc_rtx || y == pic_offset_table_rtx)
 506             break;
 507
 508           for (old_y = NULL_RTX; REG_P (y) && y != old_y;
 509                old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
 510             ;
 511
 512           if ((GET_CODE (y) == LABEL_REF && XEXP (y, 0) == label))
 513             break;
 514         }
 515
 516       if (i >= 2)
 517         return NULL_RTX;
 518
 519       x = XEXP (x, 1 - i);
 520
 521       for (old_x = NULL_RTX; REG_P (x) && x != old_x;
 522            old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 523         ;
 524     }
 525
 526   /* Strip off any sign or zero extension.  */
 527   if (GET_CODE (x) == SIGN_EXTEND || GET_CODE (x) == ZERO_EXTEND)
 528     {
 529       x = XEXP (x, 0);
 530
 531       for (old_x = NULL_RTX; REG_P (x) && x != old_x;
 532            old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 533         ;
 534     }
 535
 536   /* If X isn't a MEM then this isn't a tablejump we understand.  */
 537   if (GET_CODE (x) != MEM)
 538     return NULL_RTX;
 539
 540   /* Strip off the MEM.  */
 541   x = XEXP (x, 0);
 542
 543   for (old_x = NULL_RTX; REG_P (x) && x != old_x;
 544        old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
 545     ;
 546
 547   /* If X isn't a PLUS than this isn't a tablejump we understand.  */
 548   if (GET_CODE (x) != PLUS)
 549     return NULL_RTX;
 550
 551   /* At this point we should have an expression representing the jump table
 552      plus an offset.  Examine each operand in order to determine which one
 553      represents the jump table.  Knowing that tells us that the other operand
 554      must represent the offset.  */
 555   for (i = 0; i < 2; i++)
 556     {
 557       old_insn = insn;
 558       y = XEXP (x, i);
 559
 560       for (old_y = NULL_RTX; REG_P (y) && y != old_y;
 561            old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
 562         ;
 563
 564       if ((GET_CODE (y) == CONST || GET_CODE (y) == LABEL_REF)
 565           && reg_mentioned_p (label, y))
 566         break;
 567     }
 568
 569   if (i >= 2)
 570     return NULL_RTX;
 571
 572   x = XEXP (x, 1 - i);
 573
 574   /* Strip off the addition / subtraction of PIC_OFFSET_TABLE_REGNUM.  */
 575   if (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
 576     for (i = 0; i < 2; i++)
 577       if (XEXP (x, i) == pic_offset_table_rtx)
 578         {
 579           x = XEXP (x, 1 - i);
 580           break;
 581         }
 582
 583   if (earliest)
 584     *earliest = insn;
 585
 586   /* Return the RTL expression representing the offset.  */
 587   return x;
 588 }
 589 \f
 590 /* A subroutine of global_reg_mentioned_p, returns 1 if *LOC mentions
 591    a global register.  */
 592
 593 static int
 594 global_reg_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
 595 {
 596   int regno;
 597   rtx x = *loc;
 598
 599   if (! x)
 600     return 0;
 601
 602   switch (GET_CODE (x))
 603     {
 604     case SUBREG:
 605       if (REG_P (SUBREG_REG (x)))
 606         {
 607           if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
 608               && global_regs[subreg_regno (x)])
 609             return 1;
 610           return 0;
 611         }
 612       break;
 613
 614     case REG:
 615       regno = REGNO (x);
 616       if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
 617         return 1;
 618       return 0;
 619
 620     case SCRATCH:
 621     case PC:
 622     case CC0:
 623     case CONST_INT:
 624     case CONST_DOUBLE:
 625     case CONST:
 626     case LABEL_REF:
 627       return 0;
 628
 629     case CALL:
 630       /* A non-constant call might use a global register.  */
 631       return 1;
 632
 633     default:
 634       break;
 635     }
 636
 637   return 0;
 638 }
 639
 640 /* Returns nonzero if X mentions a global register.  */
 641
 642 int
 643 global_reg_mentioned_p (rtx x)
 644 {
 645   if (INSN_P (x))
 646     {
 647       if (GET_CODE (x) == CALL_INSN)
 648         {
 649           if (! CONST_OR_PURE_CALL_P (x))
 650             return 1;
 651           x = CALL_INSN_FUNCTION_USAGE (x);
 652           if (x == 0)
 653             return 0;
 654         }
 655       else
 656         x = PATTERN (x);
 657     }
 658
 659   return for_each_rtx (&x, global_reg_mentioned_p_1, NULL);
 660 }
 661 \f
 662 /* Return the number of places FIND appears within X.  If COUNT_DEST is
 663    zero, we do not count occurrences inside the destination of a SET.  */
 664
 665 int
 666 count_occurrences (rtx x, rtx find, int count_dest)
 667 {
 668   int i, j;
 669   enum rtx_code code;
 670   const char *format_ptr;
 671   int count;
 672
 673   if (x == find)
 674     return 1;
 675
 676   code = GET_CODE (x);
 677
 678   switch (code)
 679     {
 680     case REG:
 681     case CONST_INT:
 682     case CONST_DOUBLE:
 683     case CONST_VECTOR:
 684     case SYMBOL_REF:
 685     case CODE_LABEL:
 686     case PC:
 687     case CC0:
 688       return 0;
 689
 690     case MEM:
 691       if (GET_CODE (find) == MEM && rtx_equal_p (x, find))
 692         return 1;
 693       break;
 694
 695     case SET:
 696       if (SET_DEST (x) == find && ! count_dest)
 697         return count_occurrences (SET_SRC (x), find, count_dest);
 698       break;
 699
 700     default:
 701       break;
 702     }
 703
 704   format_ptr = GET_RTX_FORMAT (code);
 705   count = 0;
 706
 707   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 708     {
 709       switch (*format_ptr++)
 710         {
 711         case 'e':
 712           count += count_occurrences (XEXP (x, i), find, count_dest);
 713           break;
 714
 715         case 'E':
 716           for (j = 0; j < XVECLEN (x, i); j++)
 717             count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
 718           break;
 719         }
 720     }
 721   return count;
 722 }
 723 \f
 724 /* Nonzero if register REG appears somewhere within IN.
 725    Also works if REG is not a register; in this case it checks
 726    for a subexpression of IN that is Lisp "equal" to REG.  */
 727
 728 int
 729 reg_mentioned_p (rtx reg, rtx in)
 730 {
 731   const char *fmt;
 732   int i;
 733   enum rtx_code code;
 734
 735   if (in == 0)
 736     return 0;
 737
 738   if (reg == in)
 739     return 1;
 740
 741   if (GET_CODE (in) == LABEL_REF)
 742     return reg == XEXP (in, 0);
 743
 744   code = GET_CODE (in);
 745
 746   switch (code)
 747     {
 748       /* Compare registers by number.  */
 749     case REG:
 750       return REG_P (reg) && REGNO (in) == REGNO (reg);
 751
 752       /* These codes have no constituent expressions
 753          and are unique.  */
 754     case SCRATCH:
 755     case CC0:
 756     case PC:
 757       return 0;
 758
 759     case CONST_INT:
 760     case CONST_VECTOR:
 761     case CONST_DOUBLE:
 762       /* These are kept unique for a given value.  */
 763       return 0;
 764
 765     default:
 766       break;
 767     }
 768
 769   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
 770     return 1;
 771
 772   fmt = GET_RTX_FORMAT (code);
 773
 774   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 775     {
 776       if (fmt[i] == 'E')
 777         {
 778           int j;
 779           for (j = XVECLEN (in, i) - 1; j >= 0; j--)
 780             if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
 781               return 1;
 782         }
 783       else if (fmt[i] == 'e'
 784                && reg_mentioned_p (reg, XEXP (in, i)))
 785         return 1;
 786     }
 787   return 0;
 788 }
 789 \f
 790 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 791    no CODE_LABEL insn.  */
 792
 793 int
 794 no_labels_between_p (rtx beg, rtx end)
 795 {
 796   rtx p;
 797   if (beg == end)
 798     return 0;
 799   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 800     if (GET_CODE (p) == CODE_LABEL)
 801       return 0;
 802   return 1;
 803 }
 804
 805 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
 806    no JUMP_INSN insn.  */
 807
 808 int
 809 no_jumps_between_p (rtx beg, rtx end)
 810 {
 811   rtx p;
 812   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
 813     if (GET_CODE (p) == JUMP_INSN)
 814       return 0;
 815   return 1;
 816 }
 817
 818 /* Nonzero if register REG is used in an insn between
 819    FROM_INSN and TO_INSN (exclusive of those two).  */
 820
 821 int
 822 reg_used_between_p (rtx reg, rtx from_insn, rtx to_insn)
 823 {
 824   rtx insn;
 825
 826   if (from_insn == to_insn)
 827     return 0;
 828
 829   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 830     if (INSN_P (insn)
 831         && (reg_overlap_mentioned_p (reg, PATTERN (insn))
 832            || (GET_CODE (insn) == CALL_INSN
 833               && (find_reg_fusage (insn, USE, reg)
 834                   || find_reg_fusage (insn, CLOBBER, reg)))))
 835       return 1;
 836   return 0;
 837 }
 838 \f
 839 /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
 840    is entirely replaced by a new value and the only use is as a SET_DEST,
 841    we do not consider it a reference.  */
 842
 843 int
 844 reg_referenced_p (rtx x, rtx body)
 845 {
 846   int i;
 847
 848   switch (GET_CODE (body))
 849     {
 850     case SET:
 851       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
 852         return 1;
 853
 854       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
 855          of a REG that occupies all of the REG, the insn references X if
 856          it is mentioned in the destination.  */
 857       if (GET_CODE (SET_DEST (body)) != CC0
 858           && GET_CODE (SET_DEST (body)) != PC
 859           && !REG_P (SET_DEST (body))
 860           && ! (GET_CODE (SET_DEST (body)) == SUBREG
 861                 && REG_P (SUBREG_REG (SET_DEST (body)))
 862                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
 863                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
 864                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
 865                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
 866           && reg_overlap_mentioned_p (x, SET_DEST (body)))
 867         return 1;
 868       return 0;
 869
 870     case ASM_OPERANDS:
 871       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
 872         if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
 873           return 1;
 874       return 0;
 875
 876     case CALL:
 877     case USE:
 878     case IF_THEN_ELSE:
 879       return reg_overlap_mentioned_p (x, body);
 880
 881     case TRAP_IF:
 882       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
 883
 884     case PREFETCH:
 885       return reg_overlap_mentioned_p (x, XEXP (body, 0));
 886
 887     case UNSPEC:
 888     case UNSPEC_VOLATILE:
 889       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 890         if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
 891           return 1;
 892       return 0;
 893
 894     case PARALLEL:
 895       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 896         if (reg_referenced_p (x, XVECEXP (body, 0, i)))
 897           return 1;
 898       return 0;
 899
 900     case CLOBBER:
 901       if (GET_CODE (XEXP (body, 0)) == MEM)
 902         if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
 903           return 1;
 904       return 0;
 905
 906     case COND_EXEC:
 907       if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
 908         return 1;
 909       return reg_referenced_p (x, COND_EXEC_CODE (body));
 910
 911     default:
 912       return 0;
 913     }
 914 }
 915
 916 /* Nonzero if register REG is referenced in an insn between
 917    FROM_INSN and TO_INSN (exclusive of those two).  Sets of REG do
 918    not count.  */
 919
 920 int
 921 reg_referenced_between_p (rtx reg, rtx from_insn, rtx to_insn)
 922 {
 923   rtx insn;
 924
 925   if (from_insn == to_insn)
 926     return 0;
 927
 928   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 929     if (INSN_P (insn)
 930         && (reg_referenced_p (reg, PATTERN (insn))
 931            || (GET_CODE (insn) == CALL_INSN
 932               && find_reg_fusage (insn, USE, reg))))
 933       return 1;
 934   return 0;
 935 }
 936 \f
 937 /* Nonzero if register REG is set or clobbered in an insn between
 938    FROM_INSN and TO_INSN (exclusive of those two).  */
 939
 940 int
 941 reg_set_between_p (rtx reg, rtx from_insn, rtx to_insn)
 942 {
 943   rtx insn;
 944
 945   if (from_insn == to_insn)
 946     return 0;
 947
 948   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
 949     if (INSN_P (insn) && reg_set_p (reg, insn))
 950       return 1;
 951   return 0;
 952 }
 953
 954 /* Internals of reg_set_between_p.  */
 955 int
 956 reg_set_p (rtx reg, rtx insn)
 957 {
 958   /* We can be passed an insn or part of one.  If we are passed an insn,
 959      check if a side-effect of the insn clobbers REG.  */
 960   if (INSN_P (insn)
 961       && (FIND_REG_INC_NOTE (insn, reg)
 962           || (GET_CODE (insn) == CALL_INSN
 963               /* We'd like to test call_used_regs here, but rtlanal.c can't
 964                  reference that variable due to its use in genattrtab.  So
 965                  we'll just be more conservative.
 966
 967                  ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE
 968                  information holds all clobbered registers.  */
 969               && ((REG_P (reg)
 970                    && REGNO (reg) < FIRST_PSEUDO_REGISTER)
 971                   || GET_CODE (reg) == MEM
 972                   || find_reg_fusage (insn, CLOBBER, reg)))))
 973     return 1;
 974
 975   return set_of (reg, insn) != NULL_RTX;
 976 }
 977
 978 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
 979    only if none of them are modified between START and END.  Do not
 980    consider non-registers one way or the other.  */
 981
 982 int
 983 regs_set_between_p (rtx x, rtx start, rtx end)
 984 {
 985   enum rtx_code code = GET_CODE (x);
 986   const char *fmt;
 987   int i, j;
 988
 989   switch (code)
 990     {
 991     case CONST_INT:
 992     case CONST_DOUBLE:
 993     case CONST_VECTOR:
 994     case CONST:
 995     case SYMBOL_REF:
 996     case LABEL_REF:
 997     case PC:
 998     case CC0:
 999       return 0;
1000
1001     case REG:
1002       return reg_set_between_p (x, start, end);
1003
1004     default:
1005       break;
1006     }
1007
1008   fmt = GET_RTX_FORMAT (code);
1009   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1010     {
1011       if (fmt[i] == 'e' && regs_set_between_p (XEXP (x, i), start, end))
1012         return 1;
1013
1014       else if (fmt[i] == 'E')
1015         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1016           if (regs_set_between_p (XVECEXP (x, i, j), start, end))
1017             return 1;
1018     }
1019
1020   return 0;
1021 }
1022
1023 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
1024    only if none of them are modified between START and END.  Return 1 if
1025    X contains a MEM; this routine does usememory aliasing.  */
1026
1027 int
1028 modified_between_p (rtx x, rtx start, rtx end)
1029 {
1030   enum rtx_code code = GET_CODE (x);
1031   const char *fmt;
1032   int i, j;
1033   rtx insn;
1034
1035   if (start == end)
1036     return 0;
1037
1038   switch (code)
1039     {
1040     case CONST_INT:
1041     case CONST_DOUBLE:
1042     case CONST_VECTOR:
1043     case CONST:
1044     case SYMBOL_REF:
1045     case LABEL_REF:
1046       return 0;
1047
1048     case PC:
1049     case CC0:
1050       return 1;
1051
1052     case MEM:
1053       if (RTX_UNCHANGING_P (x))
1054         return 0;
1055       if (modified_between_p (XEXP (x, 0), start, end))
1056         return 1;
1057       for (insn = NEXT_INSN (start); insn != end; insn = NEXT_INSN (insn))
1058         if (memory_modified_in_insn_p (x, insn))
1059           return 1;
1060       return 0;
1061       break;
1062
1063     case REG:
1064       return reg_set_between_p (x, start, end);
1065
1066     default:
1067       break;
1068     }
1069
1070   fmt = GET_RTX_FORMAT (code);
1071   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1072     {
1073       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
1074         return 1;
1075
1076       else if (fmt[i] == 'E')
1077         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1078           if (modified_between_p (XVECEXP (x, i, j), start, end))
1079             return 1;
1080     }
1081
1082   return 0;
1083 }
1084
1085 /* Similar to reg_set_p, but check all registers in X.  Return 0 only if none
1086    of them are modified in INSN.  Return 1 if X contains a MEM; this routine
1087    does use memory aliasing.  */
1088
1089 int
1090 modified_in_p (rtx x, rtx insn)
1091 {
1092   enum rtx_code code = GET_CODE (x);
1093   const char *fmt;
1094   int i, j;
1095
1096   switch (code)
1097     {
1098     case CONST_INT:
1099     case CONST_DOUBLE:
1100     case CONST_VECTOR:
1101     case CONST:
1102     case SYMBOL_REF:
1103     case LABEL_REF:
1104       return 0;
1105
1106     case PC:
1107     case CC0:
1108       return 1;
1109
1110     case MEM:
1111       if (RTX_UNCHANGING_P (x))
1112         return 0;
1113       if (modified_in_p (XEXP (x, 0), insn))
1114         return 1;
1115       if (memory_modified_in_insn_p (x, insn))
1116         return 1;
1117       return 0;
1118       break;
1119
1120     case REG:
1121       return reg_set_p (x, insn);
1122
1123     default:
1124       break;
1125     }
1126
1127   fmt = GET_RTX_FORMAT (code);
1128   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1129     {
1130       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
1131         return 1;
1132
1133       else if (fmt[i] == 'E')
1134         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1135           if (modified_in_p (XVECEXP (x, i, j), insn))
1136             return 1;
1137     }
1138
1139   return 0;
1140 }
1141
1142 /* Return true if anything in insn X is (anti,output,true) dependent on
1143    anything in insn Y.  */
1144
1145 int
1146 insn_dependent_p (rtx x, rtx y)
1147 {
1148   rtx tmp;
1149
1150   if (! INSN_P (x) || ! INSN_P (y))
1151     abort ();
1152
1153   tmp = PATTERN (y);
1154   note_stores (PATTERN (x), insn_dependent_p_1, &tmp);
1155   if (tmp == NULL_RTX)
1156     return 1;
1157
1158   tmp = PATTERN (x);
1159   note_stores (PATTERN (y), insn_dependent_p_1, &tmp);
1160   if (tmp == NULL_RTX)
1161     return 1;
1162
1163   return 0;
1164 }
1165
1166 /* A helper routine for insn_dependent_p called through note_stores.  */
1167
1168 static void
1169 insn_dependent_p_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
1170 {
1171   rtx * pinsn = (rtx *) data;
1172
1173   if (*pinsn && reg_mentioned_p (x, *pinsn))
1174     *pinsn = NULL_RTX;
1175 }
1176 \f
1177 /* Helper function for set_of.  */
1178 struct set_of_data
1179   {
1180     rtx found;
1181     rtx pat;
1182   };
1183
1184 static void
1185 set_of_1 (rtx x, rtx pat, void *data1)
1186 {
1187    struct set_of_data *data = (struct set_of_data *) (data1);
1188    if (rtx_equal_p (x, data->pat)
1189        || (GET_CODE (x) != MEM && reg_overlap_mentioned_p (data->pat, x)))
1190      data->found = pat;
1191 }
1192
1193 /* Give an INSN, return a SET or CLOBBER expression that does modify PAT
1194    (either directly or via STRICT_LOW_PART and similar modifiers).  */
1195 rtx
1196 set_of (rtx pat, rtx insn)
1197 {
1198   struct set_of_data data;
1199   data.found = NULL_RTX;
1200   data.pat = pat;
1201   note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
1202   return data.found;
1203 }
1204 \f
1205 /* Given an INSN, return a SET expression if this insn has only a single SET.
1206    It may also have CLOBBERs, USEs, or SET whose output
1207    will not be used, which we ignore.  */
1208
1209 rtx
1210 single_set_2 (rtx insn, rtx pat)
1211 {
1212   rtx set = NULL;
1213   int set_verified = 1;
1214   int i;
1215
1216   if (GET_CODE (pat) == PARALLEL)
1217     {
1218       for (i = 0; i < XVECLEN (pat, 0); i++)
1219         {
1220           rtx sub = XVECEXP (pat, 0, i);
1221           switch (GET_CODE (sub))
1222             {
1223             case USE:
1224             case CLOBBER:
1225               break;
1226
1227             case SET:
1228               /* We can consider insns having multiple sets, where all
1229                  but one are dead as single set insns.  In common case
1230                  only single set is present in the pattern so we want
1231                  to avoid checking for REG_UNUSED notes unless necessary.
1232
1233                  When we reach set first time, we just expect this is
1234                  the single set we are looking for and only when more
1235                  sets are found in the insn, we check them.  */
1236               if (!set_verified)
1237                 {
1238                   if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
1239                       && !side_effects_p (set))
1240                     set = NULL;
1241                   else
1242                     set_verified = 1;
1243                 }
1244               if (!set)
1245                 set = sub, set_verified = 0;
1246               else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
1247                        || side_effects_p (sub))
1248                 return NULL_RTX;
1249               break;
1250
1251             default:
1252               return NULL_RTX;
1253             }
1254         }
1255     }
1256   return set;
1257 }
1258
1259 /* Given an INSN, return nonzero if it has more than one SET, else return
1260    zero.  */
1261
1262 int
1263 multiple_sets (rtx insn)
1264 {
1265   int found;
1266   int i;
1267
1268   /* INSN must be an insn.  */
1269   if (! INSN_P (insn))
1270     return 0;
1271
1272   /* Only a PARALLEL can have multiple SETs.  */
1273   if (GET_CODE (PATTERN (insn)) == PARALLEL)
1274     {
1275       for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1276         if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
1277           {
1278             /* If we have already found a SET, then return now.  */
1279             if (found)
1280               return 1;
1281             else
1282               found = 1;
1283           }
1284     }
1285
1286   /* Either zero or one SET.  */
1287   return 0;
1288 }
1289 \f
1290 /* Return nonzero if the destination of SET equals the source
1291    and there are no side effects.  */
1292
1293 int
1294 set_noop_p (rtx set)
1295 {
1296   rtx src = SET_SRC (set);
1297   rtx dst = SET_DEST (set);
1298
1299   if (dst == pc_rtx && src == pc_rtx)
1300     return 1;
1301
1302   if (GET_CODE (dst) == MEM && GET_CODE (src) == MEM)
1303     return rtx_equal_p (dst, src) && !side_effects_p (dst);
1304
1305   if (GET_CODE (dst) == SIGN_EXTRACT
1306       || GET_CODE (dst) == ZERO_EXTRACT)
1307     return rtx_equal_p (XEXP (dst, 0), src)
1308            && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx
1309            && !side_effects_p (src);
1310
1311   if (GET_CODE (dst) == STRICT_LOW_PART)
1312     dst = XEXP (dst, 0);
1313
1314   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1315     {
1316       if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1317         return 0;
1318       src = SUBREG_REG (src);
1319       dst = SUBREG_REG (dst);
1320     }
1321
1322   return (REG_P (src) && REG_P (dst)
1323           && REGNO (src) == REGNO (dst));
1324 }
1325 \f
1326 /* Return nonzero if an insn consists only of SETs, each of which only sets a
1327    value to itself.  */
1328
1329 int
1330 noop_move_p (rtx insn)
1331 {
1332   rtx pat = PATTERN (insn);
1333
1334   if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
1335     return 1;
1336
1337   /* Insns carrying these notes are useful later on.  */
1338   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
1339     return 0;
1340
1341   /* For now treat an insn with a REG_RETVAL note as a
1342      a special insn which should not be considered a no-op.  */
1343   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
1344     return 0;
1345
1346   if (GET_CODE (pat) == SET && set_noop_p (pat))
1347     return 1;
1348
1349   if (GET_CODE (pat) == PARALLEL)
1350     {
1351       int i;
1352       /* If nothing but SETs of registers to themselves,
1353          this insn can also be deleted.  */
1354       for (i = 0; i < XVECLEN (pat, 0); i++)
1355         {
1356           rtx tem = XVECEXP (pat, 0, i);
1357
1358           if (GET_CODE (tem) == USE
1359               || GET_CODE (tem) == CLOBBER)
1360             continue;
1361
1362           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
1363             return 0;
1364         }
1365
1366       return 1;
1367     }
1368   return 0;
1369 }
1370 \f
1371
1372 /* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
1373    is not NULL_RTX then verify that the object is not modified up to VALID_TO.
1374    If the object was modified, if we hit a partial assignment to X, or hit a
1375    CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
1376    point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
1377    be the src.  */
1378
1379 rtx
1380 find_last_value (rtx x, rtx *pinsn, rtx valid_to, int allow_hwreg)
1381 {
1382   rtx p;
1383
1384   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
1385        p = PREV_INSN (p))
1386     if (INSN_P (p))
1387       {
1388         rtx set = single_set (p);
1389         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
1390
1391         if (set && rtx_equal_p (x, SET_DEST (set)))
1392           {
1393             rtx src = SET_SRC (set);
1394
1395             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1396               src = XEXP (note, 0);
1397
1398             if ((valid_to == NULL_RTX
1399                  || ! modified_between_p (src, PREV_INSN (p), valid_to))
1400                 /* Reject hard registers because we don't usually want
1401                    to use them; we'd rather use a pseudo.  */
1402                 && (! (REG_P (src)
1403                       && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
1404               {
1405                 *pinsn = p;
1406                 return src;
1407               }
1408           }
1409
1410         /* If set in non-simple way, we don't have a value.  */
1411         if (reg_set_p (x, p))
1412           break;
1413       }
1414
1415   return x;
1416 }
1417 \f
1418 /* Return nonzero if register in range [REGNO, ENDREGNO)
1419    appears either explicitly or implicitly in X
1420    other than being stored into.
1421
1422    References contained within the substructure at LOC do not count.
1423    LOC may be zero, meaning don't ignore anything.  */
1424
1425 int
1426 refers_to_regno_p (unsigned int regno, unsigned int endregno, rtx x,
1427                    rtx *loc)
1428 {
1429   int i;
1430   unsigned int x_regno;
1431   RTX_CODE code;
1432   const char *fmt;
1433
1434  repeat:
1435   /* The contents of a REG_NONNEG note is always zero, so we must come here
1436      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
1437   if (x == 0)
1438     return 0;
1439
1440   code = GET_CODE (x);
1441
1442   switch (code)
1443     {
1444     case REG:
1445       x_regno = REGNO (x);
1446
1447       /* If we modifying the stack, frame, or argument pointer, it will
1448          clobber a virtual register.  In fact, we could be more precise,
1449          but it isn't worth it.  */
1450       if ((x_regno == STACK_POINTER_REGNUM
1451 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1452            || x_regno == ARG_POINTER_REGNUM
1453 #endif
1454            || x_regno == FRAME_POINTER_REGNUM)
1455           && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1456         return 1;
1457
1458       return (endregno > x_regno
1459               && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
1460                                     ? hard_regno_nregs[x_regno][GET_MODE (x)]
1461                               : 1));
1462
1463     case SUBREG:
1464       /* If this is a SUBREG of a hard reg, we can see exactly which
1465          registers are being modified.  Otherwise, handle normally.  */
1466       if (REG_P (SUBREG_REG (x))
1467           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1468         {
1469           unsigned int inner_regno = subreg_regno (x);
1470           unsigned int inner_endregno
1471             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1472                              ? hard_regno_nregs[inner_regno][GET_MODE (x)] : 1);
1473
1474           return endregno > inner_regno && regno < inner_endregno;
1475         }
1476       break;
1477
1478     case CLOBBER:
1479     case SET:
1480       if (&SET_DEST (x) != loc
1481           /* Note setting a SUBREG counts as referring to the REG it is in for
1482              a pseudo but not for hard registers since we can
1483              treat each word individually.  */
1484           && ((GET_CODE (SET_DEST (x)) == SUBREG
1485                && loc != &SUBREG_REG (SET_DEST (x))
1486                && REG_P (SUBREG_REG (SET_DEST (x)))
1487                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1488                && refers_to_regno_p (regno, endregno,
1489                                      SUBREG_REG (SET_DEST (x)), loc))
1490               || (!REG_P (SET_DEST (x))
1491                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1492         return 1;
1493
1494       if (code == CLOBBER || loc == &SET_SRC (x))
1495         return 0;
1496       x = SET_SRC (x);
1497       goto repeat;
1498
1499     default:
1500       break;
1501     }
1502
1503   /* X does not match, so try its subexpressions.  */
1504
1505   fmt = GET_RTX_FORMAT (code);
1506   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1507     {
1508       if (fmt[i] == 'e' && loc != &XEXP (x, i))
1509         {
1510           if (i == 0)
1511             {
1512               x = XEXP (x, 0);
1513               goto repeat;
1514             }
1515           else
1516             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1517               return 1;
1518         }
1519       else if (fmt[i] == 'E')
1520         {
1521           int j;
1522           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1523             if (loc != &XVECEXP (x, i, j)
1524                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1525               return 1;
1526         }
1527     }
1528   return 0;
1529 }
1530
1531 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
1532    we check if any register number in X conflicts with the relevant register
1533    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
1534    contains a MEM (we don't bother checking for memory addresses that can't
1535    conflict because we expect this to be a rare case.  */
1536
1537 int
1538 reg_overlap_mentioned_p (rtx x, rtx in)
1539 {
1540   unsigned int regno, endregno;
1541
1542   /* If either argument is a constant, then modifying X can not
1543      affect IN.  Here we look at IN, we can profitably combine
1544      CONSTANT_P (x) with the switch statement below.  */
1545   if (CONSTANT_P (in))
1546     return 0;
1547
1548  recurse:
1549   switch (GET_CODE (x))
1550     {
1551     case STRICT_LOW_PART:
1552     case ZERO_EXTRACT:
1553     case SIGN_EXTRACT:
1554       /* Overly conservative.  */
1555       x = XEXP (x, 0);
1556       goto recurse;
1557
1558     case SUBREG:
1559       regno = REGNO (SUBREG_REG (x));
1560       if (regno < FIRST_PSEUDO_REGISTER)
1561         regno = subreg_regno (x);
1562       goto do_reg;
1563
1564     case REG:
1565       regno = REGNO (x);
1566     do_reg:
1567       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1568                           ? hard_regno_nregs[regno][GET_MODE (x)] : 1);
1569       return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
1570
1571     case MEM:
1572       {
1573         const char *fmt;
1574         int i;
1575
1576         if (GET_CODE (in) == MEM)
1577           return 1;
1578
1579         fmt = GET_RTX_FORMAT (GET_CODE (in));
1580         for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1581           if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
1582             return 1;
1583
1584         return 0;
1585       }
1586
1587     case SCRATCH:
1588     case PC:
1589     case CC0:
1590       return reg_mentioned_p (x, in);
1591
1592     case PARALLEL:
1593       {
1594         int i;
1595
1596         /* If any register in here refers to it we return true.  */
1597         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1598           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1599               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1600             return 1;
1601         return 0;
1602       }
1603
1604     default:
1605 #ifdef ENABLE_CHECKING
1606       if (!CONSTANT_P (x))
1607         abort ();
1608 #endif
1609
1610       return 0;
1611     }
1612 }
1613 \f
1614 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1615    (X would be the pattern of an insn).
1616    FUN receives two arguments:
1617      the REG, MEM, CC0 or PC being stored in or clobbered,
1618      the SET or CLOBBER rtx that does the store.
1619
1620   If the item being stored in or clobbered is a SUBREG of a hard register,
1621   the SUBREG will be passed.  */
1622
1623 void
1624 note_stores (rtx x, void (*fun) (rtx, rtx, void *), void *data)
1625 {
1626   int i;
1627
1628   if (GET_CODE (x) == COND_EXEC)
1629     x = COND_EXEC_CODE (x);
1630
1631   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1632     {
1633       rtx dest = SET_DEST (x);
1634
1635       while ((GET_CODE (dest) == SUBREG
1636               && (!REG_P (SUBREG_REG (dest))
1637                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1638              || GET_CODE (dest) == ZERO_EXTRACT
1639              || GET_CODE (dest) == SIGN_EXTRACT
1640              || GET_CODE (dest) == STRICT_LOW_PART)
1641         dest = XEXP (dest, 0);
1642
1643       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1644          each of whose first operand is a register.  */
1645       if (GET_CODE (dest) == PARALLEL)
1646         {
1647           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1648             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1649               (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
1650         }
1651       else
1652         (*fun) (dest, x, data);
1653     }
1654
1655   else if (GET_CODE (x) == PARALLEL)
1656     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1657       note_stores (XVECEXP (x, 0, i), fun, data);
1658 }
1659 \f
1660 /* Like notes_stores, but call FUN for each expression that is being
1661    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1662    FUN for each expression, not any interior subexpressions.  FUN receives a
1663    pointer to the expression and the DATA passed to this function.
1664
1665    Note that this is not quite the same test as that done in reg_referenced_p
1666    since that considers something as being referenced if it is being
1667    partially set, while we do not.  */
1668
1669 void
1670 note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data)
1671 {
1672   rtx body = *pbody;
1673   int i;
1674
1675   switch (GET_CODE (body))
1676     {
1677     case COND_EXEC:
1678       (*fun) (&COND_EXEC_TEST (body), data);
1679       note_uses (&COND_EXEC_CODE (body), fun, data);
1680       return;
1681
1682     case PARALLEL:
1683       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1684         note_uses (&XVECEXP (body, 0, i), fun, data);
1685       return;
1686
1687     case USE:
1688       (*fun) (&XEXP (body, 0), data);
1689       return;
1690
1691     case ASM_OPERANDS:
1692       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1693         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1694       return;
1695
1696     case TRAP_IF:
1697       (*fun) (&TRAP_CONDITION (body), data);
1698       return;
1699
1700     case PREFETCH:
1701       (*fun) (&XEXP (body, 0), data);
1702       return;
1703
1704     case UNSPEC:
1705     case UNSPEC_VOLATILE:
1706       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1707         (*fun) (&XVECEXP (body, 0, i), data);
1708       return;
1709
1710     case CLOBBER:
1711       if (GET_CODE (XEXP (body, 0)) == MEM)
1712         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1713       return;
1714
1715     case SET:
1716       {
1717         rtx dest = SET_DEST (body);
1718
1719         /* For sets we replace everything in source plus registers in memory
1720            expression in store and operands of a ZERO_EXTRACT.  */
1721         (*fun) (&SET_SRC (body), data);
1722
1723         if (GET_CODE (dest) == ZERO_EXTRACT)
1724           {
1725             (*fun) (&XEXP (dest, 1), data);
1726             (*fun) (&XEXP (dest, 2), data);
1727           }
1728
1729         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1730           dest = XEXP (dest, 0);
1731
1732         if (GET_CODE (dest) == MEM)
1733           (*fun) (&XEXP (dest, 0), data);
1734       }
1735       return;
1736
1737     default:
1738       /* All the other possibilities never store.  */
1739       (*fun) (pbody, data);
1740       return;
1741     }
1742 }
1743 \f
1744 /* Return nonzero if X's old contents don't survive after INSN.
1745    This will be true if X is (cc0) or if X is a register and
1746    X dies in INSN or because INSN entirely sets X.
1747
1748    "Entirely set" means set directly and not through a SUBREG,
1749    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
1750    Likewise, REG_INC does not count.
1751
1752    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1753    but for this use that makes no difference, since regs don't overlap
1754    during their lifetimes.  Therefore, this function may be used
1755    at any time after deaths have been computed (in flow.c).
1756
1757    If REG is a hard reg that occupies multiple machine registers, this
1758    function will only return 1 if each of those registers will be replaced
1759    by INSN.  */
1760
1761 int
1762 dead_or_set_p (rtx insn, rtx x)
1763 {
1764   unsigned int regno, last_regno;
1765   unsigned int i;
1766
1767   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1768   if (GET_CODE (x) == CC0)
1769     return 1;
1770
1771   if (!REG_P (x))
1772     abort ();
1773
1774   regno = REGNO (x);
1775   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1776                 : regno + hard_regno_nregs[regno][GET_MODE (x)] - 1);
1777
1778   for (i = regno; i <= last_regno; i++)
1779     if (! dead_or_set_regno_p (insn, i))
1780       return 0;
1781
1782   return 1;
1783 }
1784
1785 /* Utility function for dead_or_set_p to check an individual register.  Also
1786    called from flow.c.  */
1787
1788 int
1789 dead_or_set_regno_p (rtx insn, unsigned int test_regno)
1790 {
1791   unsigned int regno, endregno;
1792   rtx pattern;
1793
1794   /* See if there is a death note for something that includes TEST_REGNO.  */
1795   if (find_regno_note (insn, REG_DEAD, test_regno))
1796     return 1;
1797
1798   if (GET_CODE (insn) == CALL_INSN
1799       && find_regno_fusage (insn, CLOBBER, test_regno))
1800     return 1;
1801
1802   pattern = PATTERN (insn);
1803
1804   if (GET_CODE (pattern) == COND_EXEC)
1805     pattern = COND_EXEC_CODE (pattern);
1806
1807   if (GET_CODE (pattern) == SET)
1808     {
1809       rtx dest = SET_DEST (pattern);
1810
1811       /* A value is totally replaced if it is the destination or the
1812          destination is a SUBREG of REGNO that does not change the number of
1813          words in it.  */
1814       if (GET_CODE (dest) == SUBREG
1815           && (((GET_MODE_SIZE (GET_MODE (dest))
1816                 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1817               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1818                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1819         dest = SUBREG_REG (dest);
1820
1821       if (!REG_P (dest))
1822         return 0;
1823
1824       regno = REGNO (dest);
1825       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1826                   : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
1827
1828       return (test_regno >= regno && test_regno < endregno);
1829     }
1830   else if (GET_CODE (pattern) == PARALLEL)
1831     {
1832       int i;
1833
1834       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1835         {
1836           rtx body = XVECEXP (pattern, 0, i);
1837
1838           if (GET_CODE (body) == COND_EXEC)
1839             body = COND_EXEC_CODE (body);
1840
1841           if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1842             {
1843               rtx dest = SET_DEST (body);
1844
1845               if (GET_CODE (dest) == SUBREG
1846                   && (((GET_MODE_SIZE (GET_MODE (dest))
1847                         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1848                       == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1849                            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1850                 dest = SUBREG_REG (dest);
1851
1852               if (!REG_P (dest))
1853                 continue;
1854
1855               regno = REGNO (dest);
1856               endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1857                           : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
1858
1859               if (test_regno >= regno && test_regno < endregno)
1860                 return 1;
1861             }
1862         }
1863     }
1864
1865   return 0;
1866 }
1867
1868 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1869    If DATUM is nonzero, look for one whose datum is DATUM.  */
1870
1871 rtx
1872 find_reg_note (rtx insn, enum reg_note kind, rtx datum)
1873 {
1874   rtx link;
1875
1876   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1877   if (! INSN_P (insn))
1878     return 0;
1879   if (datum == 0)
1880     {
1881       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1882         if (REG_NOTE_KIND (link) == kind)
1883           return link;
1884       return 0;
1885     }
1886
1887   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1888     if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0))
1889       return link;
1890   return 0;
1891 }
1892
1893 /* Return the reg-note of kind KIND in insn INSN which applies to register
1894    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1895    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1896    it might be the case that the note overlaps REGNO.  */
1897
1898 rtx
1899 find_regno_note (rtx insn, enum reg_note kind, unsigned int regno)
1900 {
1901   rtx link;
1902
1903   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1904   if (! INSN_P (insn))
1905     return 0;
1906
1907   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1908     if (REG_NOTE_KIND (link) == kind
1909         /* Verify that it is a register, so that scratch and MEM won't cause a
1910            problem here.  */
1911         && REG_P (XEXP (link, 0))
1912         && REGNO (XEXP (link, 0)) <= regno
1913         && ((REGNO (XEXP (link, 0))
1914              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1915                 : hard_regno_nregs[REGNO (XEXP (link, 0))]
1916                                   [GET_MODE (XEXP (link, 0))]))
1917             > regno))
1918       return link;
1919   return 0;
1920 }
1921
1922 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1923    has such a note.  */
1924
1925 rtx
1926 find_reg_equal_equiv_note (rtx insn)
1927 {
1928   rtx link;
1929
1930   if (!INSN_P (insn))
1931     return 0;
1932   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1933     if (REG_NOTE_KIND (link) == REG_EQUAL
1934         || REG_NOTE_KIND (link) == REG_EQUIV)
1935       {
1936         if (single_set (insn) == 0)
1937           return 0;
1938         return link;
1939       }
1940   return NULL;
1941 }
1942
1943 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1944    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1945
1946 int
1947 find_reg_fusage (rtx insn, enum rtx_code code, rtx datum)
1948 {
1949   /* If it's not a CALL_INSN, it can't possibly have a
1950      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1951   if (GET_CODE (insn) != CALL_INSN)
1952     return 0;
1953
1954   if (! datum)
1955     abort ();
1956
1957   if (!REG_P (datum))
1958     {
1959       rtx link;
1960
1961       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1962            link;
1963            link = XEXP (link, 1))
1964         if (GET_CODE (XEXP (link, 0)) == code
1965             && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
1966           return 1;
1967     }
1968   else
1969     {
1970       unsigned int regno = REGNO (datum);
1971
1972       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1973          to pseudo registers, so don't bother checking.  */
1974
1975       if (regno < FIRST_PSEUDO_REGISTER)
1976         {
1977           unsigned int end_regno
1978             = regno + hard_regno_nregs[regno][GET_MODE (datum)];
1979           unsigned int i;
1980
1981           for (i = regno; i < end_regno; i++)
1982             if (find_regno_fusage (insn, code, i))
1983               return 1;
1984         }
1985     }
1986
1987   return 0;
1988 }
1989
1990 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1991    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1992
1993 int
1994 find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno)
1995 {
1996   rtx link;
1997
1998   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1999      to pseudo registers, so don't bother checking.  */
2000
2001   if (regno >= FIRST_PSEUDO_REGISTER
2002       || GET_CODE (insn) != CALL_INSN )
2003     return 0;
2004
2005   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2006     {
2007       unsigned int regnote;
2008       rtx op, reg;
2009
2010       if (GET_CODE (op = XEXP (link, 0)) == code
2011           && REG_P (reg = XEXP (op, 0))
2012           && (regnote = REGNO (reg)) <= regno
2013           && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno)
2014         return 1;
2015     }
2016
2017   return 0;
2018 }
2019
2020 /* Return true if INSN is a call to a pure function.  */
2021
2022 int
2023 pure_call_p (rtx insn)
2024 {
2025   rtx link;
2026
2027   if (GET_CODE (insn) != CALL_INSN || ! CONST_OR_PURE_CALL_P (insn))
2028     return 0;
2029
2030   /* Look for the note that differentiates const and pure functions.  */
2031   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2032     {
2033       rtx u, m;
2034
2035       if (GET_CODE (u = XEXP (link, 0)) == USE
2036           && GET_CODE (m = XEXP (u, 0)) == MEM && GET_MODE (m) == BLKmode
2037           && GET_CODE (XEXP (m, 0)) == SCRATCH)
2038         return 1;
2039     }
2040
2041   return 0;
2042 }
2043 \f
2044 /* Remove register note NOTE from the REG_NOTES of INSN.  */
2045
2046 void
2047 remove_note (rtx insn, rtx note)
2048 {
2049   rtx link;
2050
2051   if (note == NULL_RTX)
2052     return;
2053
2054   if (REG_NOTES (insn) == note)
2055     {
2056       REG_NOTES (insn) = XEXP (note, 1);
2057       return;
2058     }
2059
2060   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2061     if (XEXP (link, 1) == note)
2062       {
2063         XEXP (link, 1) = XEXP (note, 1);
2064         return;
2065       }
2066
2067   abort ();
2068 }
2069
2070 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
2071    return 1 if it is found.  A simple equality test is used to determine if
2072    NODE matches.  */
2073
2074 int
2075 in_expr_list_p (rtx listp, rtx node)
2076 {
2077   rtx x;
2078
2079   for (x = listp; x; x = XEXP (x, 1))
2080     if (node == XEXP (x, 0))
2081       return 1;
2082
2083   return 0;
2084 }
2085
2086 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
2087    remove that entry from the list if it is found.
2088
2089    A simple equality test is used to determine if NODE matches.  */
2090
2091 void
2092 remove_node_from_expr_list (rtx node, rtx *listp)
2093 {
2094   rtx temp = *listp;
2095   rtx prev = NULL_RTX;
2096
2097   while (temp)
2098     {
2099       if (node == XEXP (temp, 0))
2100         {
2101           /* Splice the node out of the list.  */
2102           if (prev)
2103             XEXP (prev, 1) = XEXP (temp, 1);
2104           else
2105             *listp = XEXP (temp, 1);
2106
2107           return;
2108         }
2109
2110       prev = temp;
2111       temp = XEXP (temp, 1);
2112     }
2113 }
2114 \f
2115 /* Nonzero if X contains any volatile instructions.  These are instructions
2116    which may cause unpredictable machine state instructions, and thus no
2117    instructions should be moved or combined across them.  This includes
2118    only volatile asms and UNSPEC_VOLATILE instructions.  */
2119
2120 int
2121 volatile_insn_p (rtx x)
2122 {
2123   RTX_CODE code;
2124
2125   code = GET_CODE (x);
2126   switch (code)
2127     {
2128     case LABEL_REF:
2129     case SYMBOL_REF:
2130     case CONST_INT:
2131     case CONST:
2132     case CONST_DOUBLE:
2133     case CONST_VECTOR:
2134     case CC0:
2135     case PC:
2136     case REG:
2137     case SCRATCH:
2138     case CLOBBER:
2139     case ADDR_VEC:
2140     case ADDR_DIFF_VEC:
2141     case CALL:
2142     case MEM:
2143       return 0;
2144
2145     case UNSPEC_VOLATILE:
2146  /* case TRAP_IF: This isn't clear yet.  */
2147       return 1;
2148
2149     case ASM_INPUT:
2150     case ASM_OPERANDS:
2151       if (MEM_VOLATILE_P (x))
2152         return 1;
2153
2154     default:
2155       break;
2156     }
2157
2158   /* Recursively scan the operands of this expression.  */
2159
2160   {
2161     const char *fmt = GET_RTX_FORMAT (code);
2162     int i;
2163
2164     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2165       {
2166         if (fmt[i] == 'e')
2167           {
2168             if (volatile_insn_p (XEXP (x, i)))
2169               return 1;
2170           }
2171         else if (fmt[i] == 'E')
2172           {
2173             int j;
2174             for (j = 0; j < XVECLEN (x, i); j++)
2175               if (volatile_insn_p (XVECEXP (x, i, j)))
2176                 return 1;
2177           }
2178       }
2179   }
2180   return 0;
2181 }
2182
2183 /* Nonzero if X contains any volatile memory references
2184    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
2185
2186 int
2187 volatile_refs_p (rtx x)
2188 {
2189   RTX_CODE code;
2190
2191   code = GET_CODE (x);
2192   switch (code)
2193     {
2194     case LABEL_REF:
2195     case SYMBOL_REF:
2196     case CONST_INT:
2197     case CONST:
2198     case CONST_DOUBLE:
2199     case CONST_VECTOR:
2200     case CC0:
2201     case PC:
2202     case REG:
2203     case SCRATCH:
2204     case CLOBBER:
2205     case ADDR_VEC:
2206     case ADDR_DIFF_VEC:
2207       return 0;
2208
2209     case UNSPEC_VOLATILE:
2210       return 1;
2211
2212     case MEM:
2213     case ASM_INPUT:
2214     case ASM_OPERANDS:
2215       if (MEM_VOLATILE_P (x))
2216         return 1;
2217
2218     default:
2219       break;
2220     }
2221
2222   /* Recursively scan the operands of this expression.  */
2223
2224   {
2225     const char *fmt = GET_RTX_FORMAT (code);
2226     int i;
2227
2228     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2229       {
2230         if (fmt[i] == 'e')
2231           {
2232             if (volatile_refs_p (XEXP (x, i)))
2233               return 1;
2234           }
2235         else if (fmt[i] == 'E')
2236           {
2237             int j;
2238             for (j = 0; j < XVECLEN (x, i); j++)
2239               if (volatile_refs_p (XVECEXP (x, i, j)))
2240                 return 1;
2241           }
2242       }
2243   }
2244   return 0;
2245 }
2246
2247 /* Similar to above, except that it also rejects register pre- and post-
2248    incrementing.  */
2249
2250 int
2251 side_effects_p (rtx x)
2252 {
2253   RTX_CODE code;
2254
2255   code = GET_CODE (x);
2256   switch (code)
2257     {
2258     case LABEL_REF:
2259     case SYMBOL_REF:
2260     case CONST_INT:
2261     case CONST:
2262     case CONST_DOUBLE:
2263     case CONST_VECTOR:
2264     case CC0:
2265     case PC:
2266     case REG:
2267     case SCRATCH:
2268     case ADDR_VEC:
2269     case ADDR_DIFF_VEC:
2270       return 0;
2271
2272     case CLOBBER:
2273       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2274          when some combination can't be done.  If we see one, don't think
2275          that we can simplify the expression.  */
2276       return (GET_MODE (x) != VOIDmode);
2277
2278     case PRE_INC:
2279     case PRE_DEC:
2280     case POST_INC:
2281     case POST_DEC:
2282     case PRE_MODIFY:
2283     case POST_MODIFY:
2284     case CALL:
2285     case UNSPEC_VOLATILE:
2286  /* case TRAP_IF: This isn't clear yet.  */
2287       return 1;
2288
2289     case MEM:
2290     case ASM_INPUT:
2291     case ASM_OPERANDS:
2292       if (MEM_VOLATILE_P (x))
2293         return 1;
2294
2295     default:
2296       break;
2297     }
2298
2299   /* Recursively scan the operands of this expression.  */
2300
2301   {
2302     const char *fmt = GET_RTX_FORMAT (code);
2303     int i;
2304
2305     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2306       {
2307         if (fmt[i] == 'e')
2308           {
2309             if (side_effects_p (XEXP (x, i)))
2310               return 1;
2311           }
2312         else if (fmt[i] == 'E')
2313           {
2314             int j;
2315             for (j = 0; j < XVECLEN (x, i); j++)
2316               if (side_effects_p (XVECEXP (x, i, j)))
2317                 return 1;
2318           }
2319       }
2320   }
2321   return 0;
2322 }
2323 \f
2324 /* Return nonzero if evaluating rtx X might cause a trap.  */
2325
2326 int
2327 may_trap_p (rtx x)
2328 {
2329   int i;
2330   enum rtx_code code;
2331   const char *fmt;
2332
2333   if (x == 0)
2334     return 0;
2335   code = GET_CODE (x);
2336   switch (code)
2337     {
2338       /* Handle these cases quickly.  */
2339     case CONST_INT:
2340     case CONST_DOUBLE:
2341     case CONST_VECTOR:
2342     case SYMBOL_REF:
2343     case LABEL_REF:
2344     case CONST:
2345     case PC:
2346     case CC0:
2347     case REG:
2348     case SCRATCH:
2349       return 0;
2350
2351     case ASM_INPUT:
2352     case UNSPEC_VOLATILE:
2353     case TRAP_IF:
2354       return 1;
2355
2356     case ASM_OPERANDS:
2357       return MEM_VOLATILE_P (x);
2358
2359       /* Memory ref can trap unless it's a static var or a stack slot.  */
2360     case MEM:
2361       if (MEM_NOTRAP_P (x))
2362         return 0;
2363       return rtx_addr_can_trap_p (XEXP (x, 0));
2364
2365       /* Division by a non-constant might trap.  */
2366     case DIV:
2367     case MOD:
2368     case UDIV:
2369     case UMOD:
2370       if (HONOR_SNANS (GET_MODE (x)))
2371         return 1;
2372       if (! CONSTANT_P (XEXP (x, 1))
2373           || (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
2374               && flag_trapping_math))
2375         return 1;
2376       if (XEXP (x, 1) == const0_rtx)
2377         return 1;
2378       break;
2379
2380     case EXPR_LIST:
2381       /* An EXPR_LIST is used to represent a function call.  This
2382          certainly may trap.  */
2383       return 1;
2384
2385     case GE:
2386     case GT:
2387     case LE:
2388     case LT:
2389     case COMPARE:
2390       /* Some floating point comparisons may trap.  */
2391       if (!flag_trapping_math)
2392         break;
2393       /* ??? There is no machine independent way to check for tests that trap
2394          when COMPARE is used, though many targets do make this distinction.
2395          For instance, sparc uses CCFPE for compares which generate exceptions
2396          and CCFP for compares which do not generate exceptions.  */
2397       if (HONOR_NANS (GET_MODE (x)))
2398         return 1;
2399       /* But often the compare has some CC mode, so check operand
2400          modes as well.  */
2401       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2402           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2403         return 1;
2404       break;
2405
2406     case EQ:
2407     case NE:
2408       if (HONOR_SNANS (GET_MODE (x)))
2409         return 1;
2410       /* Often comparison is CC mode, so check operand modes.  */
2411       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2412           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2413         return 1;
2414       break;
2415
2416     case FIX:
2417       /* Conversion of floating point might trap.  */
2418       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2419         return 1;
2420       break;
2421
2422     case NEG:
2423     case ABS:
2424       /* These operations don't trap even with floating point.  */
2425       break;
2426
2427     default:
2428       /* Any floating arithmetic may trap.  */
2429       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
2430           && flag_trapping_math)
2431         return 1;
2432     }
2433
2434   fmt = GET_RTX_FORMAT (code);
2435   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2436     {
2437       if (fmt[i] == 'e')
2438         {
2439           if (may_trap_p (XEXP (x, i)))
2440             return 1;
2441         }
2442       else if (fmt[i] == 'E')
2443         {
2444           int j;
2445           for (j = 0; j < XVECLEN (x, i); j++)
2446             if (may_trap_p (XVECEXP (x, i, j)))
2447               return 1;
2448         }
2449     }
2450   return 0;
2451 }
2452 \f
2453 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2454    i.e., an inequality.  */
2455
2456 int
2457 inequality_comparisons_p (rtx x)
2458 {
2459   const char *fmt;
2460   int len, i;
2461   enum rtx_code code = GET_CODE (x);
2462
2463   switch (code)
2464     {
2465     case REG:
2466     case SCRATCH:
2467     case PC:
2468     case CC0:
2469     case CONST_INT:
2470     case CONST_DOUBLE:
2471     case CONST_VECTOR:
2472     case CONST:
2473     case LABEL_REF:
2474     case SYMBOL_REF:
2475       return 0;
2476
2477     case LT:
2478     case LTU:
2479     case GT:
2480     case GTU:
2481     case LE:
2482     case LEU:
2483     case GE:
2484     case GEU:
2485       return 1;
2486
2487     default:
2488       break;
2489     }
2490
2491   len = GET_RTX_LENGTH (code);
2492   fmt = GET_RTX_FORMAT (code);
2493
2494   for (i = 0; i < len; i++)
2495     {
2496       if (fmt[i] == 'e')
2497         {
2498           if (inequality_comparisons_p (XEXP (x, i)))
2499             return 1;
2500         }
2501       else if (fmt[i] == 'E')
2502         {
2503           int j;
2504           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2505             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2506               return 1;
2507         }
2508     }
2509
2510   return 0;
2511 }
2512 \f
2513 /* Replace any occurrence of FROM in X with TO.  The function does
2514    not enter into CONST_DOUBLE for the replace.
2515
2516    Note that copying is not done so X must not be shared unless all copies
2517    are to be modified.  */
2518
2519 rtx
2520 replace_rtx (rtx x, rtx from, rtx to)
2521 {
2522   int i, j;
2523   const char *fmt;
2524
2525   /* The following prevents loops occurrence when we change MEM in
2526      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2527   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2528     return x;
2529
2530   if (x == from)
2531     return to;
2532
2533   /* Allow this function to make replacements in EXPR_LISTs.  */
2534   if (x == 0)
2535     return 0;
2536
2537   if (GET_CODE (x) == SUBREG)
2538     {
2539       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2540
2541       if (GET_CODE (new) == CONST_INT)
2542         {
2543           x = simplify_subreg (GET_MODE (x), new,
2544                                GET_MODE (SUBREG_REG (x)),
2545                                SUBREG_BYTE (x));
2546           if (! x)
2547             abort ();
2548         }
2549       else
2550         SUBREG_REG (x) = new;
2551
2552       return x;
2553     }
2554   else if (GET_CODE (x) == ZERO_EXTEND)
2555     {
2556       rtx new = replace_rtx (XEXP (x, 0), from, to);
2557
2558       if (GET_CODE (new) == CONST_INT)
2559         {
2560           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2561                                         new, GET_MODE (XEXP (x, 0)));
2562           if (! x)
2563             abort ();
2564         }
2565       else
2566         XEXP (x, 0) = new;
2567
2568       return x;
2569     }
2570
2571   fmt = GET_RTX_FORMAT (GET_CODE (x));
2572   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2573     {
2574       if (fmt[i] == 'e')
2575         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2576       else if (fmt[i] == 'E')
2577         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2578           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2579     }
2580
2581   return x;
2582 }
2583 \f
2584 /* Throughout the rtx X, replace many registers according to REG_MAP.
2585    Return the replacement for X (which may be X with altered contents).
2586    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2587    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2588
2589    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2590    should not be mapped to pseudos or vice versa since validate_change
2591    is not called.
2592
2593    If REPLACE_DEST is 1, replacements are also done in destinations;
2594    otherwise, only sources are replaced.  */
2595
2596 rtx
2597 replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest)
2598 {
2599   enum rtx_code code;
2600   int i;
2601   const char *fmt;
2602
2603   if (x == 0)
2604     return x;
2605
2606   code = GET_CODE (x);
2607   switch (code)
2608     {
2609     case SCRATCH:
2610     case PC:
2611     case CC0:
2612     case CONST_INT:
2613     case CONST_DOUBLE:
2614     case CONST_VECTOR:
2615     case CONST:
2616     case SYMBOL_REF:
2617     case LABEL_REF:
2618       return x;
2619
2620     case REG:
2621       /* Verify that the register has an entry before trying to access it.  */
2622       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2623         {
2624           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2625              this replacement occurs more than once then each instance will
2626              get distinct rtx.  */
2627           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2628             return copy_rtx (reg_map[REGNO (x)]);
2629           return reg_map[REGNO (x)];
2630         }
2631       return x;
2632
2633     case SUBREG:
2634       /* Prevent making nested SUBREGs.  */
2635       if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs
2636           && reg_map[REGNO (SUBREG_REG (x))] != 0
2637           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2638         {
2639           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2640           return simplify_gen_subreg (GET_MODE (x), map_val,
2641                                       GET_MODE (SUBREG_REG (x)),
2642                                       SUBREG_BYTE (x));
2643         }
2644       break;
2645
2646     case SET:
2647       if (replace_dest)
2648         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2649
2650       else if (GET_CODE (SET_DEST (x)) == MEM
2651                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2652         /* Even if we are not to replace destinations, replace register if it
2653            is CONTAINED in destination (destination is memory or
2654            STRICT_LOW_PART).  */
2655         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2656                                                reg_map, nregs, 0);
2657       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2658         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2659         break;
2660
2661       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2662       return x;
2663
2664     default:
2665       break;
2666     }
2667
2668   fmt = GET_RTX_FORMAT (code);
2669   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2670     {
2671       if (fmt[i] == 'e')
2672         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2673       else if (fmt[i] == 'E')
2674         {
2675           int j;
2676           for (j = 0; j < XVECLEN (x, i); j++)
2677             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2678                                               nregs, replace_dest);
2679         }
2680     }
2681   return x;
2682 }
2683
2684 /* Replace occurrences of the old label in *X with the new one.
2685    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2686
2687 int
2688 replace_label (rtx *x, void *data)
2689 {
2690   rtx l = *x;
2691   rtx old_label = ((replace_label_data *) data)->r1;
2692   rtx new_label = ((replace_label_data *) data)->r2;
2693   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2694
2695   if (l == NULL_RTX)
2696     return 0;
2697
2698   if (GET_CODE (l) == SYMBOL_REF
2699       && CONSTANT_POOL_ADDRESS_P (l))
2700     {
2701       rtx c = get_pool_constant (l);
2702       if (rtx_referenced_p (old_label, c))
2703         {
2704           rtx new_c, new_l;
2705           replace_label_data *d = (replace_label_data *) data;
2706
2707           /* Create a copy of constant C; replace the label inside
2708              but do not update LABEL_NUSES because uses in constant pool
2709              are not counted.  */
2710           new_c = copy_rtx (c);
2711           d->update_label_nuses = false;
2712           for_each_rtx (&new_c, replace_label, data);
2713           d->update_label_nuses = update_label_nuses;
2714
2715           /* Add the new constant NEW_C to constant pool and replace
2716              the old reference to constant by new reference.  */
2717           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2718           *x = replace_rtx (l, l, new_l);
2719         }
2720       return 0;
2721     }
2722
2723   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2724      field.  This is not handled by for_each_rtx because it doesn't
2725      handle unprinted ('0') fields.  */
2726   if (GET_CODE (l) == JUMP_INSN && JUMP_LABEL (l) == old_label)
2727     JUMP_LABEL (l) = new_label;
2728
2729   if ((GET_CODE (l) == LABEL_REF
2730        || GET_CODE (l) == INSN_LIST)
2731       && XEXP (l, 0) == old_label)
2732     {
2733       XEXP (l, 0) = new_label;
2734       if (update_label_nuses)
2735         {
2736           ++LABEL_NUSES (new_label);
2737           --LABEL_NUSES (old_label);
2738         }
2739       return 0;
2740     }
2741
2742   return 0;
2743 }
2744
2745 /* When *BODY is equal to X or X is directly referenced by *BODY
2746    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2747    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2748
2749 static int
2750 rtx_referenced_p_1 (rtx *body, void *x)
2751 {
2752   rtx y = (rtx) x;
2753
2754   if (*body == NULL_RTX)
2755     return y == NULL_RTX;
2756
2757   /* Return true if a label_ref *BODY refers to label Y.  */
2758   if (GET_CODE (*body) == LABEL_REF && GET_CODE (y) == CODE_LABEL)
2759     return XEXP (*body, 0) == y;
2760
2761   /* If *BODY is a reference to pool constant traverse the constant.  */
2762   if (GET_CODE (*body) == SYMBOL_REF
2763       && CONSTANT_POOL_ADDRESS_P (*body))
2764     return rtx_referenced_p (y, get_pool_constant (*body));
2765
2766   /* By default, compare the RTL expressions.  */
2767   return rtx_equal_p (*body, y);
2768 }
2769
2770 /* Return true if X is referenced in BODY.  */
2771
2772 int
2773 rtx_referenced_p (rtx x, rtx body)
2774 {
2775   return for_each_rtx (&body, rtx_referenced_p_1, x);
2776 }
2777
2778 /* If INSN is a tablejump return true and store the label (before jump table) to
2779    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2780
2781 bool
2782 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2783 {
2784   rtx label, table;
2785
2786   if (GET_CODE (insn) == JUMP_INSN
2787       && (label = JUMP_LABEL (insn)) != NULL_RTX
2788       && (table = next_active_insn (label)) != NULL_RTX
2789       && GET_CODE (table) == JUMP_INSN
2790       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2791           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2792     {
2793       if (labelp)
2794         *labelp = label;
2795       if (tablep)
2796         *tablep = table;
2797       return true;
2798     }
2799   return false;
2800 }
2801
2802 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2803    constant that is not in the constant pool and not in the condition
2804    of an IF_THEN_ELSE.  */
2805
2806 static int
2807 computed_jump_p_1 (rtx x)
2808 {
2809   enum rtx_code code = GET_CODE (x);
2810   int i, j;
2811   const char *fmt;
2812
2813   switch (code)
2814     {
2815     case LABEL_REF:
2816     case PC:
2817       return 0;
2818
2819     case CONST:
2820     case CONST_INT:
2821     case CONST_DOUBLE:
2822     case CONST_VECTOR:
2823     case SYMBOL_REF:
2824     case REG:
2825       return 1;
2826
2827     case MEM:
2828       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2829                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2830
2831     case IF_THEN_ELSE:
2832       return (computed_jump_p_1 (XEXP (x, 1))
2833               || computed_jump_p_1 (XEXP (x, 2)));
2834
2835     default:
2836       break;
2837     }
2838
2839   fmt = GET_RTX_FORMAT (code);
2840   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2841     {
2842       if (fmt[i] == 'e'
2843           && computed_jump_p_1 (XEXP (x, i)))
2844         return 1;
2845
2846       else if (fmt[i] == 'E')
2847         for (j = 0; j < XVECLEN (x, i); j++)
2848           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2849             return 1;
2850     }
2851
2852   return 0;
2853 }
2854
2855 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2856
2857    Tablejumps and casesi insns are not considered indirect jumps;
2858    we can recognize them by a (use (label_ref)).  */
2859
2860 int
2861 computed_jump_p (rtx insn)
2862 {
2863   int i;
2864   if (GET_CODE (insn) == JUMP_INSN)
2865     {
2866       rtx pat = PATTERN (insn);
2867
2868       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2869         return 0;
2870       else if (GET_CODE (pat) == PARALLEL)
2871         {
2872           int len = XVECLEN (pat, 0);
2873           int has_use_labelref = 0;
2874
2875           for (i = len - 1; i >= 0; i--)
2876             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2877                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2878                     == LABEL_REF))
2879               has_use_labelref = 1;
2880
2881           if (! has_use_labelref)
2882             for (i = len - 1; i >= 0; i--)
2883               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2884                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2885                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2886                 return 1;
2887         }
2888       else if (GET_CODE (pat) == SET
2889                && SET_DEST (pat) == pc_rtx
2890                && computed_jump_p_1 (SET_SRC (pat)))
2891         return 1;
2892     }
2893   return 0;
2894 }
2895
2896 /* Traverse X via depth-first search, calling F for each
2897    sub-expression (including X itself).  F is also passed the DATA.
2898    If F returns -1, do not traverse sub-expressions, but continue
2899    traversing the rest of the tree.  If F ever returns any other
2900    nonzero value, stop the traversal, and return the value returned
2901    by F.  Otherwise, return 0.  This function does not traverse inside
2902    tree structure that contains RTX_EXPRs, or into sub-expressions
2903    whose format code is `0' since it is not known whether or not those
2904    codes are actually RTL.
2905
2906    This routine is very general, and could (should?) be used to
2907    implement many of the other routines in this file.  */
2908
2909 int
2910 for_each_rtx (rtx *x, rtx_function f, void *data)
2911 {
2912   int result;
2913   int length;
2914   const char *format;
2915   int i;
2916
2917   /* Call F on X.  */
2918   result = (*f) (x, data);
2919   if (result == -1)
2920     /* Do not traverse sub-expressions.  */
2921     return 0;
2922   else if (result != 0)
2923     /* Stop the traversal.  */
2924     return result;
2925
2926   if (*x == NULL_RTX)
2927     /* There are no sub-expressions.  */
2928     return 0;
2929
2930   length = GET_RTX_LENGTH (GET_CODE (*x));
2931   format = GET_RTX_FORMAT (GET_CODE (*x));
2932
2933   for (i = 0; i < length; ++i)
2934     {
2935       switch (format[i])
2936         {
2937         case 'e':
2938           result = for_each_rtx (&XEXP (*x, i), f, data);
2939           if (result != 0)
2940             return result;
2941           break;
2942
2943         case 'V':
2944         case 'E':
2945           if (XVEC (*x, i) != 0)
2946             {
2947               int j;
2948               for (j = 0; j < XVECLEN (*x, i); ++j)
2949                 {
2950                   result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
2951                   if (result != 0)
2952                     return result;
2953                 }
2954             }
2955           break;
2956
2957         default:
2958           /* Nothing to do.  */
2959           break;
2960         }
2961
2962     }
2963
2964   return 0;
2965 }
2966
2967 /* Searches X for any reference to REGNO, returning the rtx of the
2968    reference found if any.  Otherwise, returns NULL_RTX.  */
2969
2970 rtx
2971 regno_use_in (unsigned int regno, rtx x)
2972 {
2973   const char *fmt;
2974   int i, j;
2975   rtx tem;
2976
2977   if (REG_P (x) && REGNO (x) == regno)
2978     return x;
2979
2980   fmt = GET_RTX_FORMAT (GET_CODE (x));
2981   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2982     {
2983       if (fmt[i] == 'e')
2984         {
2985           if ((tem = regno_use_in (regno, XEXP (x, i))))
2986             return tem;
2987         }
2988       else if (fmt[i] == 'E')
2989         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2990           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2991             return tem;
2992     }
2993
2994   return NULL_RTX;
2995 }
2996
2997 /* Return a value indicating whether OP, an operand of a commutative
2998    operation, is preferred as the first or second operand.  The higher
2999    the value, the stronger the preference for being the first operand.
3000    We use negative values to indicate a preference for the first operand
3001    and positive values for the second operand.  */
3002
3003 int
3004 commutative_operand_precedence (rtx op)
3005 {
3006   enum rtx_code code = GET_CODE (op);
3007
3008   /* Constants always come the second operand.  Prefer "nice" constants.  */
3009   if (code == CONST_INT)
3010     return -7;
3011   if (code == CONST_DOUBLE)
3012     return -6;
3013   op = avoid_constant_pool_reference (op);
3014
3015   switch (GET_RTX_CLASS (code))
3016     {
3017     case RTX_CONST_OBJ:
3018       if (code == CONST_INT)
3019         return -5;
3020       if (code == CONST_DOUBLE)
3021         return -4;
3022       return -3;
3023
3024     case RTX_EXTRA:
3025       /* SUBREGs of objects should come second.  */
3026       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
3027         return -2;
3028
3029       if (!CONSTANT_P (op))
3030         return 0;
3031       else
3032         /* As for RTX_CONST_OBJ.  */
3033         return -3;
3034
3035     case RTX_OBJ:
3036       /* Complex expressions should be the first, so decrease priority
3037          of objects.  */
3038       return -1;
3039
3040     case RTX_COMM_ARITH:
3041       /* Prefer operands that are themselves commutative to be first.
3042          This helps to make things linear.  In particular,
3043          (and (and (reg) (reg)) (not (reg))) is canonical.  */
3044       return 4;
3045
3046     case RTX_BIN_ARITH:
3047       /* If only one operand is a binary expression, it will be the first
3048          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
3049          is canonical, although it will usually be further simplified.  */
3050       return 2;
3051
3052     case RTX_UNARY:
3053       /* Then prefer NEG and NOT.  */
3054       if (code == NEG || code == NOT)
3055         return 1;
3056
3057     default:
3058       return 0;
3059     }
3060 }
3061
3062 /* Return 1 iff it is necessary to swap operands of commutative operation
3063    in order to canonicalize expression.  */
3064
3065 int
3066 swap_commutative_operands_p (rtx x, rtx y)
3067 {
3068   return (commutative_operand_precedence (x)
3069           < commutative_operand_precedence (y));
3070 }
3071
3072 /* Return 1 if X is an autoincrement side effect and the register is
3073    not the stack pointer.  */
3074 int
3075 auto_inc_p (rtx x)
3076 {
3077   switch (GET_CODE (x))
3078     {
3079     case PRE_INC:
3080     case POST_INC:
3081     case PRE_DEC:
3082     case POST_DEC:
3083     case PRE_MODIFY:
3084     case POST_MODIFY:
3085       /* There are no REG_INC notes for SP.  */
3086       if (XEXP (x, 0) != stack_pointer_rtx)
3087         return 1;
3088     default:
3089       break;
3090     }
3091   return 0;
3092 }
3093
3094 /* Return 1 if the sequence of instructions beginning with FROM and up
3095    to and including TO is safe to move.  If NEW_TO is non-NULL, and
3096    the sequence is not already safe to move, but can be easily
3097    extended to a sequence which is safe, then NEW_TO will point to the
3098    end of the extended sequence.
3099
3100    For now, this function only checks that the region contains whole
3101    exception regions, but it could be extended to check additional
3102    conditions as well.  */
3103
3104 int
3105 insns_safe_to_move_p (rtx from, rtx to, rtx *new_to)
3106 {
3107   int eh_region_count = 0;
3108   int past_to_p = 0;
3109   rtx r = from;
3110
3111   /* By default, assume the end of the region will be what was
3112      suggested.  */
3113   if (new_to)
3114     *new_to = to;
3115
3116   while (r)
3117     {
3118       if (GET_CODE (r) == NOTE)
3119         {
3120           switch (NOTE_LINE_NUMBER (r))
3121             {
3122             case NOTE_INSN_EH_REGION_BEG:
3123               ++eh_region_count;
3124               break;
3125
3126             case NOTE_INSN_EH_REGION_END:
3127               if (eh_region_count == 0)
3128                 /* This sequence of instructions contains the end of
3129                    an exception region, but not he beginning.  Moving
3130                    it will cause chaos.  */
3131                 return 0;
3132
3133               --eh_region_count;
3134               break;
3135
3136             default:
3137               break;
3138             }
3139         }
3140       else if (past_to_p)
3141         /* If we've passed TO, and we see a non-note instruction, we
3142            can't extend the sequence to a movable sequence.  */
3143         return 0;
3144
3145       if (r == to)
3146         {
3147           if (!new_to)
3148             /* It's OK to move the sequence if there were matched sets of
3149                exception region notes.  */
3150             return eh_region_count == 0;
3151
3152           past_to_p = 1;
3153         }
3154
3155       /* It's OK to move the sequence if there were matched sets of
3156          exception region notes.  */
3157       if (past_to_p && eh_region_count == 0)
3158         {
3159           *new_to = r;
3160           return 1;
3161         }
3162
3163       /* Go to the next instruction.  */
3164       r = NEXT_INSN (r);
3165     }
3166
3167   return 0;
3168 }
3169
3170 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
3171 int
3172 loc_mentioned_in_p (rtx *loc, rtx in)
3173 {
3174   enum rtx_code code = GET_CODE (in);
3175   const char *fmt = GET_RTX_FORMAT (code);
3176   int i, j;
3177
3178   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3179     {
3180       if (loc == &in->u.fld[i].rtx)
3181         return 1;
3182       if (fmt[i] == 'e')
3183         {
3184           if (loc_mentioned_in_p (loc, XEXP (in, i)))
3185             return 1;
3186         }
3187       else if (fmt[i] == 'E')
3188         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
3189           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3190             return 1;
3191     }
3192   return 0;
3193 }
3194
3195 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
3196    and SUBREG_BYTE, return the bit offset where the subreg begins
3197    (counting from the least significant bit of the operand).  */
3198
3199 unsigned int
3200 subreg_lsb_1 (enum machine_mode outer_mode,
3201               enum machine_mode inner_mode,
3202               unsigned int subreg_byte)
3203 {
3204   unsigned int bitpos;
3205   unsigned int byte;
3206   unsigned int word;
3207
3208   /* A paradoxical subreg begins at bit position 0.  */
3209   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
3210     return 0;
3211
3212   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3213     /* If the subreg crosses a word boundary ensure that
3214        it also begins and ends on a word boundary.  */
3215     if ((subreg_byte % UNITS_PER_WORD
3216          + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
3217         && (subreg_byte % UNITS_PER_WORD
3218             || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD))
3219         abort ();
3220
3221   if (WORDS_BIG_ENDIAN)
3222     word = (GET_MODE_SIZE (inner_mode)
3223             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3224   else
3225     word = subreg_byte / UNITS_PER_WORD;
3226   bitpos = word * BITS_PER_WORD;
3227
3228   if (BYTES_BIG_ENDIAN)
3229     byte = (GET_MODE_SIZE (inner_mode)
3230             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3231   else
3232     byte = subreg_byte % UNITS_PER_WORD;
3233   bitpos += byte * BITS_PER_UNIT;
3234
3235   return bitpos;
3236 }
3237
3238 /* Given a subreg X, return the bit offset where the subreg begins
3239    (counting from the least significant bit of the reg).  */
3240
3241 unsigned int
3242 subreg_lsb (rtx x)
3243 {
3244   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3245                        SUBREG_BYTE (x));
3246 }
3247
3248 /* This function returns the regno offset of a subreg expression.
3249    xregno - A regno of an inner hard subreg_reg (or what will become one).
3250    xmode  - The mode of xregno.
3251    offset - The byte offset.
3252    ymode  - The mode of a top level SUBREG (or what may become one).
3253    RETURN - The regno offset which would be used.  */
3254 unsigned int
3255 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3256                      unsigned int offset, enum machine_mode ymode)
3257 {
3258   int nregs_xmode, nregs_ymode;
3259   int mode_multiple, nregs_multiple;
3260   int y_offset;
3261
3262   if (xregno >= FIRST_PSEUDO_REGISTER)
3263     abort ();
3264
3265   nregs_xmode = hard_regno_nregs[xregno][xmode];
3266   nregs_ymode = hard_regno_nregs[xregno][ymode];
3267
3268   /* If this is a big endian paradoxical subreg, which uses more actual
3269      hard registers than the original register, we must return a negative
3270      offset so that we find the proper highpart of the register.  */
3271   if (offset == 0
3272       && nregs_ymode > nregs_xmode
3273       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3274           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3275     return nregs_xmode - nregs_ymode;
3276
3277   if (offset == 0 || nregs_xmode == nregs_ymode)
3278     return 0;
3279
3280   /* size of ymode must not be greater than the size of xmode.  */
3281   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3282   if (mode_multiple == 0)
3283     abort ();
3284
3285   y_offset = offset / GET_MODE_SIZE (ymode);
3286   nregs_multiple =  nregs_xmode / nregs_ymode;
3287   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3288 }
3289
3290 /* This function returns true when the offset is representable via
3291    subreg_offset in the given regno.
3292    xregno - A regno of an inner hard subreg_reg (or what will become one).
3293    xmode  - The mode of xregno.
3294    offset - The byte offset.
3295    ymode  - The mode of a top level SUBREG (or what may become one).
3296    RETURN - The regno offset which would be used.  */
3297 bool
3298 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3299                                unsigned int offset, enum machine_mode ymode)
3300 {
3301   int nregs_xmode, nregs_ymode;
3302   int mode_multiple, nregs_multiple;
3303   int y_offset;
3304
3305   if (xregno >= FIRST_PSEUDO_REGISTER)
3306     abort ();
3307
3308   nregs_xmode = hard_regno_nregs[xregno][xmode];
3309   nregs_ymode = hard_regno_nregs[xregno][ymode];
3310
3311   /* Paradoxical subregs are always valid.  */
3312   if (offset == 0
3313       && nregs_ymode > nregs_xmode
3314       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3315           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3316     return true;
3317
3318   /* Lowpart subregs are always valid.  */
3319   if (offset == subreg_lowpart_offset (ymode, xmode))
3320     return true;
3321
3322 #ifdef ENABLE_CHECKING
3323   /* This should always pass, otherwise we don't know how to verify the
3324      constraint.  These conditions may be relaxed but subreg_offset would
3325      need to be redesigned.  */
3326   if (GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)
3327       || GET_MODE_SIZE (ymode) % nregs_ymode
3328       || nregs_xmode % nregs_ymode)
3329     abort ();
3330 #endif
3331
3332   /* The XMODE value can be seen as a vector of NREGS_XMODE
3333      values.  The subreg must represent a lowpart of given field.
3334      Compute what field it is.  */
3335   offset -= subreg_lowpart_offset (ymode,
3336                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3337                                                   / nregs_xmode,
3338                                                   MODE_INT, 0));
3339
3340   /* size of ymode must not be greater than the size of xmode.  */
3341   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3342   if (mode_multiple == 0)
3343     abort ();
3344
3345   y_offset = offset / GET_MODE_SIZE (ymode);
3346   nregs_multiple =  nregs_xmode / nregs_ymode;
3347 #ifdef ENABLE_CHECKING
3348   if (offset % GET_MODE_SIZE (ymode)
3349       || mode_multiple % nregs_multiple)
3350     abort ();
3351 #endif
3352   return (!(y_offset % (mode_multiple / nregs_multiple)));
3353 }
3354
3355 /* Return the final regno that a subreg expression refers to.  */
3356 unsigned int
3357 subreg_regno (rtx x)
3358 {
3359   unsigned int ret;
3360   rtx subreg = SUBREG_REG (x);
3361   int regno = REGNO (subreg);
3362
3363   ret = regno + subreg_regno_offset (regno,
3364                                      GET_MODE (subreg),
3365                                      SUBREG_BYTE (x),
3366                                      GET_MODE (x));
3367   return ret;
3368
3369 }
3370 struct parms_set_data
3371 {
3372   int nregs;
3373   HARD_REG_SET regs;
3374 };
3375
3376 /* Helper function for noticing stores to parameter registers.  */
3377 static void
3378 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3379 {
3380   struct parms_set_data *d = data;
3381   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3382       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3383     {
3384       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3385       d->nregs--;
3386     }
3387 }
3388
3389 /* Look backward for first parameter to be loaded.
3390    Do not skip BOUNDARY.  */
3391 rtx
3392 find_first_parameter_load (rtx call_insn, rtx boundary)
3393 {
3394   struct parms_set_data parm;
3395   rtx p, before;
3396
3397   /* Since different machines initialize their parameter registers
3398      in different orders, assume nothing.  Collect the set of all
3399      parameter registers.  */
3400   CLEAR_HARD_REG_SET (parm.regs);
3401   parm.nregs = 0;
3402   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3403     if (GET_CODE (XEXP (p, 0)) == USE
3404         && REG_P (XEXP (XEXP (p, 0), 0)))
3405       {
3406         if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
3407           abort ();
3408
3409         /* We only care about registers which can hold function
3410            arguments.  */
3411         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3412           continue;
3413
3414         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3415         parm.nregs++;
3416       }
3417   before = call_insn;
3418
3419   /* Search backward for the first set of a register in this set.  */
3420   while (parm.nregs && before != boundary)
3421     {
3422       before = PREV_INSN (before);
3423
3424       /* It is possible that some loads got CSEed from one call to
3425          another.  Stop in that case.  */
3426       if (GET_CODE (before) == CALL_INSN)
3427         break;
3428
3429       /* Our caller needs either ensure that we will find all sets
3430          (in case code has not been optimized yet), or take care
3431          for possible labels in a way by setting boundary to preceding
3432          CODE_LABEL.  */
3433       if (GET_CODE (before) == CODE_LABEL)
3434         {
3435           if (before != boundary)
3436             abort ();
3437           break;
3438         }
3439
3440       if (INSN_P (before))
3441         note_stores (PATTERN (before), parms_set, &parm);
3442     }
3443   return before;
3444 }
3445
3446 /* Return true if we should avoid inserting code between INSN and preceding
3447    call instruction.  */
3448
3449 bool
3450 keep_with_call_p (rtx insn)
3451 {
3452   rtx set;
3453
3454   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3455     {
3456       if (REG_P (SET_DEST (set))
3457           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3458           && fixed_regs[REGNO (SET_DEST (set))]
3459           && general_operand (SET_SRC (set), VOIDmode))
3460         return true;
3461       if (REG_P (SET_SRC (set))
3462           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3463           && REG_P (SET_DEST (set))
3464           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3465         return true;
3466       /* There may be a stack pop just after the call and before the store
3467          of the return register.  Search for the actual store when deciding
3468          if we can break or not.  */
3469       if (SET_DEST (set) == stack_pointer_rtx)
3470         {
3471           rtx i2 = next_nonnote_insn (insn);
3472           if (i2 && keep_with_call_p (i2))
3473             return true;
3474         }
3475     }
3476   return false;
3477 }
3478
3479 /* Return true when store to register X can be hoisted to the place
3480    with LIVE registers (can be NULL).  Value VAL contains destination
3481    whose value will be used.  */
3482
3483 static bool
3484 hoist_test_store (rtx x, rtx val, regset live)
3485 {
3486   if (GET_CODE (x) == SCRATCH)
3487     return true;
3488
3489   if (rtx_equal_p (x, val))
3490     return true;
3491
3492   /* Allow subreg of X in case it is not writing just part of multireg pseudo.
3493      Then we would need to update all users to care hoisting the store too.
3494      Caller may represent that by specifying whole subreg as val.  */
3495
3496   if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val))
3497     {
3498       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
3499           && GET_MODE_BITSIZE (GET_MODE (x)) <
3500           GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
3501         return false;
3502       return true;
3503     }
3504   if (GET_CODE (x) == SUBREG)
3505     x = SUBREG_REG (x);
3506
3507   /* Anything except register store is not hoistable.  This includes the
3508      partial stores to registers.  */
3509
3510   if (!REG_P (x))
3511     return false;
3512
3513   /* Pseudo registers can be always replaced by another pseudo to avoid
3514      the side effect, for hard register we must ensure that they are dead.
3515      Eventually we may want to add code to try turn pseudos to hards, but it
3516      is unlikely useful.  */
3517
3518   if (REGNO (x) < FIRST_PSEUDO_REGISTER)
3519     {
3520       int regno = REGNO (x);
3521       int n = hard_regno_nregs[regno][GET_MODE (x)];
3522
3523       if (!live)
3524         return false;
3525       if (REGNO_REG_SET_P (live, regno))
3526         return false;
3527       while (--n > 0)
3528         if (REGNO_REG_SET_P (live, regno + n))
3529           return false;
3530     }
3531   return true;
3532 }
3533
3534
3535 /* Return true if INSN can be hoisted to place with LIVE hard registers
3536    (LIVE can be NULL when unknown).  VAL is expected to be stored by the insn
3537    and used by the hoisting pass.  */
3538
3539 bool
3540 can_hoist_insn_p (rtx insn, rtx val, regset live)
3541 {
3542   rtx pat = PATTERN (insn);
3543   int i;
3544
3545   /* It probably does not worth the complexity to handle multiple
3546      set stores.  */
3547   if (!single_set (insn))
3548     return false;
3549   /* We can move CALL_INSN, but we need to check that all caller clobbered
3550      regs are dead.  */
3551   if (GET_CODE (insn) == CALL_INSN)
3552     return false;
3553   /* In future we will handle hoisting of libcall sequences, but
3554      give up for now.  */
3555   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
3556     return false;
3557   switch (GET_CODE (pat))
3558     {
3559     case SET:
3560       if (!hoist_test_store (SET_DEST (pat), val, live))
3561         return false;
3562       break;
3563     case USE:
3564       /* USES do have sick semantics, so do not move them.  */
3565       return false;
3566       break;
3567     case CLOBBER:
3568       if (!hoist_test_store (XEXP (pat, 0), val, live))
3569         return false;
3570       break;
3571     case PARALLEL:
3572       for (i = 0; i < XVECLEN (pat, 0); i++)
3573         {
3574           rtx x = XVECEXP (pat, 0, i);
3575           switch (GET_CODE (x))
3576             {
3577             case SET:
3578               if (!hoist_test_store (SET_DEST (x), val, live))
3579                 return false;
3580               break;
3581             case USE:
3582               /* We need to fix callers to really ensure availability
3583                  of all values insn uses, but for now it is safe to prohibit
3584                  hoisting of any insn having such a hidden uses.  */
3585               return false;
3586               break;
3587             case CLOBBER:
3588               if (!hoist_test_store (SET_DEST (x), val, live))
3589                 return false;
3590               break;
3591             default:
3592               break;
3593             }
3594         }
3595       break;
3596     default:
3597       abort ();
3598     }
3599   return true;
3600 }
3601
3602 /* Update store after hoisting - replace all stores to pseudo registers
3603    by new ones to avoid clobbering of values except for store to VAL that will
3604    be updated to NEW.  */
3605
3606 static void
3607 hoist_update_store (rtx insn, rtx *xp, rtx val, rtx new)
3608 {
3609   rtx x = *xp;
3610
3611   if (GET_CODE (x) == SCRATCH)
3612     return;
3613
3614   if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val)
3615     validate_change (insn, xp,
3616                      simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new),
3617                                           SUBREG_BYTE (x)), 1);
3618   if (rtx_equal_p (x, val))
3619     {
3620       validate_change (insn, xp, new, 1);
3621       return;
3622     }
3623   if (GET_CODE (x) == SUBREG)
3624     {
3625       xp = &SUBREG_REG (x);
3626       x = *xp;
3627     }
3628
3629   if (!REG_P (x))
3630     abort ();
3631
3632   /* We've verified that hard registers are dead, so we may keep the side
3633      effect.  Otherwise replace it by new pseudo.  */
3634   if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
3635     validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1);
3636   REG_NOTES (insn)
3637     = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn));
3638 }
3639
3640 /* Create a copy of INSN after AFTER replacing store of VAL to NEW
3641    and each other side effect to pseudo register by new pseudo register.  */
3642
3643 rtx
3644 hoist_insn_after (rtx insn, rtx after, rtx val, rtx new)
3645 {
3646   rtx pat;
3647   int i;
3648   rtx note;
3649
3650   insn = emit_copy_of_insn_after (insn, after);
3651   pat = PATTERN (insn);
3652
3653   /* Remove REG_UNUSED notes as we will re-emit them.  */
3654   while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX)))
3655     remove_note (insn, note);
3656
3657   /* To get this working callers must ensure to move everything referenced
3658      by REG_EQUAL/REG_EQUIV notes too.  Lets remove them, it is probably
3659      easier.  */
3660   while ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX)))
3661     remove_note (insn, note);
3662   while ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)))
3663     remove_note (insn, note);
3664
3665   /* Remove REG_DEAD notes as they might not be valid anymore in case
3666      we create redundancy.  */
3667   while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX)))
3668     remove_note (insn, note);
3669   switch (GET_CODE (pat))
3670     {
3671     case SET:
3672       hoist_update_store (insn, &SET_DEST (pat), val, new);
3673       break;
3674     case USE:
3675       break;
3676     case CLOBBER:
3677       hoist_update_store (insn, &XEXP (pat, 0), val, new);
3678       break;
3679     case PARALLEL:
3680       for (i = 0; i < XVECLEN (pat, 0); i++)
3681         {
3682           rtx x = XVECEXP (pat, 0, i);
3683           switch (GET_CODE (x))
3684             {
3685             case SET:
3686               hoist_update_store (insn, &SET_DEST (x), val, new);
3687               break;
3688             case USE:
3689               break;
3690             case CLOBBER:
3691               hoist_update_store (insn, &SET_DEST (x), val, new);
3692               break;
3693             default:
3694               break;
3695             }
3696         }
3697       break;
3698     default:
3699       abort ();
3700     }
3701   if (!apply_change_group ())
3702     abort ();
3703
3704   return insn;
3705 }
3706
3707 rtx
3708 hoist_insn_to_edge (rtx insn, edge e, rtx val, rtx new)
3709 {
3710   rtx new_insn;
3711
3712   /* We cannot insert instructions on an abnormal critical edge.
3713      It will be easier to find the culprit if we die now.  */
3714   if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
3715     abort ();
3716
3717   /* Do not use emit_insn_on_edge as we want to preserve notes and similar
3718      stuff.  We also emit CALL_INSNS and firends.  */
3719   if (e->insns.r == NULL_RTX)
3720     {
3721       start_sequence ();
3722       emit_note (NOTE_INSN_DELETED);
3723     }
3724   else
3725     push_to_sequence (e->insns.r);
3726
3727   new_insn = hoist_insn_after (insn, get_last_insn (), val, new);
3728
3729   e->insns.r = get_insns ();
3730   end_sequence ();
3731   return new_insn;
3732 }
3733
3734 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3735    to non-complex jumps.  That is, direct unconditional, conditional,
3736    and tablejumps, but not computed jumps or returns.  It also does
3737    not apply to the fallthru case of a conditional jump.  */
3738
3739 bool
3740 label_is_jump_target_p (rtx label, rtx jump_insn)
3741 {
3742   rtx tmp = JUMP_LABEL (jump_insn);
3743
3744   if (label == tmp)
3745     return true;
3746
3747   if (tablejump_p (jump_insn, NULL, &tmp))
3748     {
3749       rtvec vec = XVEC (PATTERN (tmp),
3750                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3751       int i, veclen = GET_NUM_ELEM (vec);
3752
3753       for (i = 0; i < veclen; ++i)
3754         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3755           return true;
3756     }
3757
3758   return false;
3759 }
3760
3761 \f
3762 /* Return an estimate of the cost of computing rtx X.
3763    One use is in cse, to decide which expression to keep in the hash table.
3764    Another is in rtl generation, to pick the cheapest way to multiply.
3765    Other uses like the latter are expected in the future.  */
3766
3767 int
3768 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3769 {
3770   int i, j;
3771   enum rtx_code code;
3772   const char *fmt;
3773   int total;
3774
3775   if (x == 0)
3776     return 0;
3777
3778   /* Compute the default costs of certain things.
3779      Note that targetm.rtx_costs can override the defaults.  */
3780
3781   code = GET_CODE (x);
3782   switch (code)
3783     {
3784     case MULT:
3785       total = COSTS_N_INSNS (5);
3786       break;
3787     case DIV:
3788     case UDIV:
3789     case MOD:
3790     case UMOD:
3791       total = COSTS_N_INSNS (7);
3792       break;
3793     case USE:
3794       /* Used in loop.c and combine.c as a marker.  */
3795       total = 0;
3796       break;
3797     default:
3798       total = COSTS_N_INSNS (1);
3799     }
3800
3801   switch (code)
3802     {
3803     case REG:
3804       return 0;
3805
3806     case SUBREG:
3807       /* If we can't tie these modes, make this expensive.  The larger
3808          the mode, the more expensive it is.  */
3809       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3810         return COSTS_N_INSNS (2
3811                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3812       break;
3813
3814     default:
3815       if (targetm.rtx_costs (x, code, outer_code, &total))
3816         return total;
3817       break;
3818     }
3819
3820   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3821      which is already in total.  */
3822
3823   fmt = GET_RTX_FORMAT (code);
3824   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3825     if (fmt[i] == 'e')
3826       total += rtx_cost (XEXP (x, i), code);
3827     else if (fmt[i] == 'E')
3828       for (j = 0; j < XVECLEN (x, i); j++)
3829         total += rtx_cost (XVECEXP (x, i, j), code);
3830
3831   return total;
3832 }
3833 \f
3834 /* Return cost of address expression X.
3835    Expect that X is properly formed address reference.  */
3836
3837 int
3838 address_cost (rtx x, enum machine_mode mode)
3839 {
3840   /* The address_cost target hook does not deal with ADDRESSOF nodes.  But,
3841      during CSE, such nodes are present.  Using an ADDRESSOF node which
3842      refers to the address of a REG is a good thing because we can then
3843      turn (MEM (ADDRESSOF (REG))) into just plain REG.  */
3844
3845   if (GET_CODE (x) == ADDRESSOF && REG_P (XEXP ((x), 0)))
3846     return -1;
3847
3848   /* We may be asked for cost of various unusual addresses, such as operands
3849      of push instruction.  It is not worthwhile to complicate writing
3850      of the target hook by such cases.  */
3851
3852   if (!memory_address_p (mode, x))
3853     return 1000;
3854
3855   return targetm.address_cost (x);
3856 }
3857
3858 /* If the target doesn't override, compute the cost as with arithmetic.  */
3859
3860 int
3861 default_address_cost (rtx x)
3862 {
3863   return rtx_cost (x, MEM);
3864 }
3865 \f
3866
3867 unsigned HOST_WIDE_INT
3868 nonzero_bits (rtx x, enum machine_mode mode)
3869 {
3870   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3871 }
3872
3873 unsigned int
3874 num_sign_bit_copies (rtx x, enum machine_mode mode)
3875 {
3876   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3877 }
3878
3879 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3880    It avoids exponential behavior in nonzero_bits1 when X has
3881    identical subexpressions on the first or the second level.  */
3882
3883 static unsigned HOST_WIDE_INT
3884 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3885                      enum machine_mode known_mode,
3886                      unsigned HOST_WIDE_INT known_ret)
3887 {
3888   if (x == known_x && mode == known_mode)
3889     return known_ret;
3890
3891   /* Try to find identical subexpressions.  If found call
3892      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3893      precomputed value for the subexpression as KNOWN_RET.  */
3894
3895   if (ARITHMETIC_P (x))
3896     {
3897       rtx x0 = XEXP (x, 0);
3898       rtx x1 = XEXP (x, 1);
3899
3900       /* Check the first level.  */
3901       if (x0 == x1)
3902         return nonzero_bits1 (x, mode, x0, mode,
3903                               cached_nonzero_bits (x0, mode, known_x,
3904                                                    known_mode, known_ret));
3905
3906       /* Check the second level.  */
3907       if (ARITHMETIC_P (x0)
3908           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3909         return nonzero_bits1 (x, mode, x1, mode,
3910                               cached_nonzero_bits (x1, mode, known_x,
3911                                                    known_mode, known_ret));
3912
3913       if (ARITHMETIC_P (x1)
3914           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3915         return nonzero_bits1 (x, mode, x0, mode,
3916                               cached_nonzero_bits (x0, mode, known_x,
3917                                                    known_mode, known_ret));
3918     }
3919
3920   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3921 }
3922
3923 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3924    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3925    is less useful.  We can't allow both, because that results in exponential
3926    run time recursion.  There is a nullstone testcase that triggered
3927    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3928 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3929
3930 /* Given an expression, X, compute which bits in X can be nonzero.
3931    We don't care about bits outside of those defined in MODE.
3932
3933    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3934    an arithmetic operation, we can do better.  */
3935
3936 static unsigned HOST_WIDE_INT
3937 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3938                enum machine_mode known_mode,
3939                unsigned HOST_WIDE_INT known_ret)
3940 {
3941   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3942   unsigned HOST_WIDE_INT inner_nz;
3943   enum rtx_code code;
3944   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3945
3946   /* For floating-point values, assume all bits are needed.  */
3947   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3948     return nonzero;
3949
3950   /* If X is wider than MODE, use its mode instead.  */
3951   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3952     {
3953       mode = GET_MODE (x);
3954       nonzero = GET_MODE_MASK (mode);
3955       mode_width = GET_MODE_BITSIZE (mode);
3956     }
3957
3958   if (mode_width > HOST_BITS_PER_WIDE_INT)
3959     /* Our only callers in this case look for single bit values.  So
3960        just return the mode mask.  Those tests will then be false.  */
3961     return nonzero;
3962
3963 #ifndef WORD_REGISTER_OPERATIONS
3964   /* If MODE is wider than X, but both are a single word for both the host
3965      and target machines, we can compute this from which bits of the
3966      object might be nonzero in its own mode, taking into account the fact
3967      that on many CISC machines, accessing an object in a wider mode
3968      causes the high-order bits to become undefined.  So they are
3969      not known to be zero.  */
3970
3971   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3972       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3973       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3974       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3975     {
3976       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3977                                       known_x, known_mode, known_ret);
3978       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3979       return nonzero;
3980     }
3981 #endif
3982
3983   code = GET_CODE (x);
3984   switch (code)
3985     {
3986     case REG:
3987 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3988       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3989          all the bits above ptr_mode are known to be zero.  */
3990       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3991           && REG_POINTER (x))
3992         nonzero &= GET_MODE_MASK (ptr_mode);
3993 #endif
3994
3995       /* Include declared information about alignment of pointers.  */
3996       /* ??? We don't properly preserve REG_POINTER changes across
3997          pointer-to-integer casts, so we can't trust it except for
3998          things that we know must be pointers.  See execute/960116-1.c.  */
3999       if ((x == stack_pointer_rtx
4000            || x == frame_pointer_rtx
4001            || x == arg_pointer_rtx)
4002           && REGNO_POINTER_ALIGN (REGNO (x)))
4003         {
4004           unsigned HOST_WIDE_INT alignment
4005             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
4006
4007 #ifdef PUSH_ROUNDING
4008           /* If PUSH_ROUNDING is defined, it is possible for the
4009              stack to be momentarily aligned only to that amount,
4010              so we pick the least alignment.  */
4011           if (x == stack_pointer_rtx && PUSH_ARGS)
4012             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
4013                              alignment);
4014 #endif
4015
4016           nonzero &= ~(alignment - 1);
4017         }
4018
4019       {
4020         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
4021         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
4022                                               known_mode, known_ret,
4023                                               &nonzero_for_hook);
4024
4025         if (new)
4026           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
4027                                                    known_mode, known_ret);
4028
4029         return nonzero_for_hook;
4030       }
4031
4032     case CONST_INT:
4033 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
4034       /* If X is negative in MODE, sign-extend the value.  */
4035       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
4036           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
4037         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
4038 #endif
4039
4040       return INTVAL (x);
4041
4042     case MEM:
4043 #ifdef LOAD_EXTEND_OP
4044       /* In many, if not most, RISC machines, reading a byte from memory
4045          zeros the rest of the register.  Noticing that fact saves a lot
4046          of extra zero-extends.  */
4047       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
4048         nonzero &= GET_MODE_MASK (GET_MODE (x));
4049 #endif
4050       break;
4051
4052     case EQ:  case NE:
4053     case UNEQ:  case LTGT:
4054     case GT:  case GTU:  case UNGT:
4055     case LT:  case LTU:  case UNLT:
4056     case GE:  case GEU:  case UNGE:
4057     case LE:  case LEU:  case UNLE:
4058     case UNORDERED: case ORDERED:
4059
4060       /* If this produces an integer result, we know which bits are set.
4061          Code here used to clear bits outside the mode of X, but that is
4062          now done above.  */
4063
4064       if (GET_MODE_CLASS (mode) == MODE_INT
4065           && mode_width <= HOST_BITS_PER_WIDE_INT)
4066         nonzero = STORE_FLAG_VALUE;
4067       break;
4068
4069     case NEG:
4070 #if 0
4071       /* Disabled to avoid exponential mutual recursion between nonzero_bits
4072          and num_sign_bit_copies.  */
4073       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
4074           == GET_MODE_BITSIZE (GET_MODE (x)))
4075         nonzero = 1;
4076 #endif
4077
4078       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
4079         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
4080       break;
4081
4082     case ABS:
4083 #if 0
4084       /* Disabled to avoid exponential mutual recursion between nonzero_bits
4085          and num_sign_bit_copies.  */
4086       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
4087           == GET_MODE_BITSIZE (GET_MODE (x)))
4088         nonzero = 1;
4089 #endif
4090       break;
4091
4092     case TRUNCATE:
4093       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
4094                                        known_x, known_mode, known_ret)
4095                   & GET_MODE_MASK (mode));
4096       break;
4097
4098     case ZERO_EXTEND:
4099       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
4100                                       known_x, known_mode, known_ret);
4101       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
4102         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
4103       break;
4104
4105     case SIGN_EXTEND:
4106       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
4107          Otherwise, show all the bits in the outer mode but not the inner
4108          may be nonzero.  */
4109       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
4110                                       known_x, known_mode, known_ret);
4111       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
4112         {
4113           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
4114           if (inner_nz
4115               & (((HOST_WIDE_INT) 1
4116                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
4117             inner_nz |= (GET_MODE_MASK (mode)
4118                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
4119         }
4120
4121       nonzero &= inner_nz;
4122       break;
4123
4124     case AND:
4125       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
4126                                        known_x, known_mode, known_ret)
4127                  & cached_nonzero_bits (XEXP (x, 1), mode,
4128                                         known_x, known_mode, known_ret);
4129       break;
4130
4131     case XOR:   case IOR:
4132     case UMIN:  case UMAX:  case SMIN:  case SMAX:
4133       {
4134         unsigned HOST_WIDE_INT nonzero0 =
4135           cached_nonzero_bits (XEXP (x, 0), mode,
4136                                known_x, known_mode, known_ret);
4137
4138         /* Don't call nonzero_bits for the second time if it cannot change
4139            anything.  */
4140         if ((nonzero & nonzero0) != nonzero)
4141           nonzero &= nonzero0
4142                      | cached_nonzero_bits (XEXP (x, 1), mode,
4143                                             known_x, known_mode, known_ret);
4144       }
4145       break;
4146
4147     case PLUS:  case MINUS:
4148     case MULT:
4149     case DIV:   case UDIV:
4150     case MOD:   case UMOD:
4151       /* We can apply the rules of arithmetic to compute the number of
4152          high- and low-order zero bits of these operations.  We start by
4153          computing the width (position of the highest-order nonzero bit)
4154          and the number of low-order zero bits for each value.  */
4155       {
4156         unsigned HOST_WIDE_INT nz0 =
4157           cached_nonzero_bits (XEXP (x, 0), mode,
4158                                known_x, known_mode, known_ret);
4159         unsigned HOST_WIDE_INT nz1 =
4160           cached_nonzero_bits (XEXP (x, 1), mode,
4161                                known_x, known_mode, known_ret);
4162         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
4163         int width0 = floor_log2 (nz0) + 1;
4164         int width1 = floor_log2 (nz1) + 1;
4165         int low0 = floor_log2 (nz0 & -nz0);
4166         int low1 = floor_log2 (nz1 & -nz1);
4167         HOST_WIDE_INT op0_maybe_minusp
4168           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
4169         HOST_WIDE_INT op1_maybe_minusp
4170           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
4171         unsigned int result_width = mode_width;
4172         int result_low = 0;
4173
4174         switch (code)
4175           {
4176           case PLUS:
4177             result_width = MAX (width0, width1) + 1;
4178             result_low = MIN (low0, low1);
4179             break;
4180           case MINUS:
4181             result_low = MIN (low0, low1);
4182             break;
4183           case MULT:
4184             result_width = width0 + width1;
4185             result_low = low0 + low1;
4186             break;
4187           case DIV:
4188             if (width1 == 0)
4189               break;
4190             if (! op0_maybe_minusp && ! op1_maybe_minusp)
4191               result_width = width0;
4192             break;
4193           case UDIV:
4194             if (width1 == 0)
4195               break;
4196             result_width = width0;
4197             break;
4198           case MOD:
4199             if (width1 == 0)
4200               break;
4201             if (! op0_maybe_minusp && ! op1_maybe_minusp)
4202               result_width = MIN (width0, width1);
4203             result_low = MIN (low0, low1);
4204             break;
4205           case UMOD:
4206             if (width1 == 0)
4207               break;
4208             result_width = MIN (width0, width1);
4209             result_low = MIN (low0, low1);
4210             break;
4211           default:
4212             abort ();
4213           }
4214
4215         if (result_width < mode_width)
4216           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
4217
4218         if (result_low > 0)
4219           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
4220
4221 #ifdef POINTERS_EXTEND_UNSIGNED
4222         /* If pointers extend unsigned and this is an addition or subtraction
4223            to a pointer in Pmode, all the bits above ptr_mode are known to be
4224            zero.  */
4225         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
4226             && (code == PLUS || code == MINUS)
4227             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4228           nonzero &= GET_MODE_MASK (ptr_mode);
4229 #endif
4230       }
4231       break;
4232
4233     case ZERO_EXTRACT:
4234       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4235           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
4236         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
4237       break;
4238
4239     case SUBREG:
4240       /* If this is a SUBREG formed for a promoted variable that has
4241          been zero-extended, we know that at least the high-order bits
4242          are zero, though others might be too.  */
4243
4244       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
4245         nonzero = GET_MODE_MASK (GET_MODE (x))
4246                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
4247                                          known_x, known_mode, known_ret);
4248
4249       /* If the inner mode is a single word for both the host and target
4250          machines, we can compute this from which bits of the inner
4251          object might be nonzero.  */
4252       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
4253           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4254               <= HOST_BITS_PER_WIDE_INT))
4255         {
4256           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
4257                                           known_x, known_mode, known_ret);
4258
4259 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
4260           /* If this is a typical RISC machine, we only have to worry
4261              about the way loads are extended.  */
4262           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4263                ? (((nonzero
4264                     & (((unsigned HOST_WIDE_INT) 1
4265                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
4266                    != 0))
4267                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
4268               || GET_CODE (SUBREG_REG (x)) != MEM)
4269 #endif
4270             {
4271               /* On many CISC machines, accessing an object in a wider mode
4272                  causes the high-order bits to become undefined.  So they are
4273                  not known to be zero.  */
4274               if (GET_MODE_SIZE (GET_MODE (x))
4275                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4276                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
4277                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
4278             }
4279         }
4280       break;
4281
4282     case ASHIFTRT:
4283     case LSHIFTRT:
4284     case ASHIFT:
4285     case ROTATE:
4286       /* The nonzero bits are in two classes: any bits within MODE
4287          that aren't in GET_MODE (x) are always significant.  The rest of the
4288          nonzero bits are those that are significant in the operand of
4289          the shift when shifted the appropriate number of bits.  This
4290          shows that high-order bits are cleared by the right shift and
4291          low-order bits by left shifts.  */
4292       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4293           && INTVAL (XEXP (x, 1)) >= 0
4294           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
4295         {
4296           enum machine_mode inner_mode = GET_MODE (x);
4297           unsigned int width = GET_MODE_BITSIZE (inner_mode);
4298           int count = INTVAL (XEXP (x, 1));
4299           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
4300           unsigned HOST_WIDE_INT op_nonzero =
4301             cached_nonzero_bits (XEXP (x, 0), mode,
4302                                  known_x, known_mode, known_ret);
4303           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
4304           unsigned HOST_WIDE_INT outer = 0;
4305
4306           if (mode_width > width)
4307             outer = (op_nonzero & nonzero & ~mode_mask);
4308
4309           if (code == LSHIFTRT)
4310             inner >>= count;
4311           else if (code == ASHIFTRT)
4312             {
4313               inner >>= count;
4314
4315               /* If the sign bit may have been nonzero before the shift, we
4316                  need to mark all the places it could have been copied to
4317                  by the shift as possibly nonzero.  */
4318               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
4319                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
4320             }
4321           else if (code == ASHIFT)
4322             inner <<= count;
4323           else
4324             inner = ((inner << (count % width)
4325                       | (inner >> (width - (count % width)))) & mode_mask);
4326
4327           nonzero &= (outer | inner);
4328         }
4329       break;
4330
4331     case FFS:
4332     case POPCOUNT:
4333       /* This is at most the number of bits in the mode.  */
4334       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
4335       break;
4336
4337     case CLZ:
4338       /* If CLZ has a known value at zero, then the nonzero bits are
4339          that value, plus the number of bits in the mode minus one.  */
4340       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
4341         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
4342       else
4343         nonzero = -1;
4344       break;
4345
4346     case CTZ:
4347       /* If CTZ has a known value at zero, then the nonzero bits are
4348          that value, plus the number of bits in the mode minus one.  */
4349       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
4350         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
4351       else
4352         nonzero = -1;
4353       break;
4354
4355     case PARITY:
4356       nonzero = 1;
4357       break;
4358
4359     case IF_THEN_ELSE:
4360       {
4361         unsigned HOST_WIDE_INT nonzero_true =
4362           cached_nonzero_bits (XEXP (x, 1), mode,
4363                                known_x, known_mode, known_ret);
4364
4365         /* Don't call nonzero_bits for the second time if it cannot change
4366            anything.  */
4367         if ((nonzero & nonzero_true) != nonzero)
4368           nonzero &= nonzero_true
4369                      | cached_nonzero_bits (XEXP (x, 2), mode,
4370                                             known_x, known_mode, known_ret);
4371       }
4372       break;
4373
4374     default:
4375       break;
4376     }
4377
4378   return nonzero;
4379 }
4380
4381 /* See the macro definition above.  */
4382 #undef cached_num_sign_bit_copies
4383
4384 \f
4385 /* The function cached_num_sign_bit_copies is a wrapper around
4386    num_sign_bit_copies1.  It avoids exponential behavior in
4387    num_sign_bit_copies1 when X has identical subexpressions on the
4388    first or the second level.  */
4389
4390 static unsigned int
4391 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
4392                             enum machine_mode known_mode,
4393                             unsigned int known_ret)
4394 {
4395   if (x == known_x && mode == known_mode)
4396     return known_ret;
4397
4398   /* Try to find identical subexpressions.  If found call
4399      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
4400      the precomputed value for the subexpression as KNOWN_RET.  */
4401
4402   if (ARITHMETIC_P (x))
4403     {
4404       rtx x0 = XEXP (x, 0);
4405       rtx x1 = XEXP (x, 1);
4406
4407       /* Check the first level.  */
4408       if (x0 == x1)
4409         return
4410           num_sign_bit_copies1 (x, mode, x0, mode,
4411                                 cached_num_sign_bit_copies (x0, mode, known_x,
4412                                                             known_mode,
4413                                                             known_ret));
4414
4415       /* Check the second level.  */
4416       if (ARITHMETIC_P (x0)
4417           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
4418         return
4419           num_sign_bit_copies1 (x, mode, x1, mode,
4420                                 cached_num_sign_bit_copies (x1, mode, known_x,
4421                                                             known_mode,
4422                                                             known_ret));
4423
4424       if (ARITHMETIC_P (x1)
4425           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
4426         return
4427           num_sign_bit_copies1 (x, mode, x0, mode,
4428                                 cached_num_sign_bit_copies (x0, mode, known_x,
4429                                                             known_mode,
4430                                                             known_ret));
4431     }
4432
4433   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
4434 }
4435
4436 /* Return the number of bits at the high-order end of X that are known to
4437    be equal to the sign bit.  X will be used in mode MODE; if MODE is
4438    VOIDmode, X will be used in its own mode.  The returned value  will always
4439    be between 1 and the number of bits in MODE.  */
4440
4441 static unsigned int
4442 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
4443                       enum machine_mode known_mode,
4444                       unsigned int known_ret)
4445 {
4446   enum rtx_code code = GET_CODE (x);
4447   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
4448   int num0, num1, result;
4449   unsigned HOST_WIDE_INT nonzero;
4450
4451   /* If we weren't given a mode, use the mode of X.  If the mode is still
4452      VOIDmode, we don't know anything.  Likewise if one of the modes is
4453      floating-point.  */
4454
4455   if (mode == VOIDmode)
4456     mode = GET_MODE (x);
4457
4458   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
4459     return 1;
4460
4461   /* For a smaller object, just ignore the high bits.  */
4462   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
4463     {
4464       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
4465                                          known_x, known_mode, known_ret);
4466       return MAX (1,
4467                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
4468     }
4469
4470   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
4471     {
4472 #ifndef WORD_REGISTER_OPERATIONS
4473   /* If this machine does not do all register operations on the entire
4474      register and MODE is wider than the mode of X, we can say nothing
4475      at all about the high-order bits.  */
4476       return 1;
4477 #else
4478       /* Likewise on machines that do, if the mode of the object is smaller
4479          than a word and loads of that size don't sign extend, we can say
4480          nothing about the high order bits.  */
4481       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4482 #ifdef LOAD_EXTEND_OP
4483           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4484 #endif
4485           )
4486         return 1;
4487 #endif
4488     }
4489
4490   switch (code)
4491     {
4492     case REG:
4493
4494 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4495       /* If pointers extend signed and this is a pointer in Pmode, say that
4496          all the bits above ptr_mode are known to be sign bit copies.  */
4497       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4498           && REG_POINTER (x))
4499         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4500 #endif
4501
4502       {
4503         unsigned int copies_for_hook = 1, copies = 1;
4504         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4505                                                      known_mode, known_ret,
4506                                                      &copies_for_hook);
4507
4508         if (new)
4509           copies = cached_num_sign_bit_copies (new, mode, known_x,
4510                                                known_mode, known_ret);
4511
4512         if (copies > 1 || copies_for_hook > 1)
4513           return MAX (copies, copies_for_hook);
4514
4515         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4516       }
4517       break;
4518
4519     case MEM:
4520 #ifdef LOAD_EXTEND_OP
4521       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4522       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4523         return MAX (1, ((int) bitwidth
4524                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4525 #endif
4526       break;
4527
4528     case CONST_INT:
4529       /* If the constant is negative, take its 1's complement and remask.
4530          Then see how many zero bits we have.  */
4531       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4532       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4533           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4534         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4535
4536       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4537
4538     case SUBREG:
4539       /* If this is a SUBREG for a promoted object that is sign-extended
4540          and we are looking at it in a wider mode, we know that at least the
4541          high-order bits are known to be sign bit copies.  */
4542
4543       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4544         {
4545           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4546                                              known_x, known_mode, known_ret);
4547           return MAX ((int) bitwidth
4548                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4549                       num0);
4550         }
4551
4552       /* For a smaller object, just ignore the high bits.  */
4553       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4554         {
4555           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4556                                              known_x, known_mode, known_ret);
4557           return MAX (1, (num0
4558                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4559                                    - bitwidth)));
4560         }
4561
4562 #ifdef WORD_REGISTER_OPERATIONS
4563 #ifdef LOAD_EXTEND_OP
4564       /* For paradoxical SUBREGs on machines where all register operations
4565          affect the entire register, just look inside.  Note that we are
4566          passing MODE to the recursive call, so the number of sign bit copies
4567          will remain relative to that mode, not the inner mode.  */
4568
4569       /* This works only if loads sign extend.  Otherwise, if we get a
4570          reload for the inner part, it may be loaded from the stack, and
4571          then we lose all sign bit copies that existed before the store
4572          to the stack.  */
4573
4574       if ((GET_MODE_SIZE (GET_MODE (x))
4575            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4576           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4577           && GET_CODE (SUBREG_REG (x)) == MEM)
4578         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4579                                            known_x, known_mode, known_ret);
4580 #endif
4581 #endif
4582       break;
4583
4584     case SIGN_EXTRACT:
4585       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4586         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4587       break;
4588
4589     case SIGN_EXTEND:
4590       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4591               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4592                                             known_x, known_mode, known_ret));
4593
4594     case TRUNCATE:
4595       /* For a smaller object, just ignore the high bits.  */
4596       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4597                                          known_x, known_mode, known_ret);
4598       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4599                                     - bitwidth)));
4600
4601     case NOT:
4602       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4603                                          known_x, known_mode, known_ret);
4604
4605     case ROTATE:       case ROTATERT:
4606       /* If we are rotating left by a number of bits less than the number
4607          of sign bit copies, we can just subtract that amount from the
4608          number.  */
4609       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4610           && INTVAL (XEXP (x, 1)) >= 0
4611           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4612         {
4613           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4614                                              known_x, known_mode, known_ret);
4615           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4616                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4617         }
4618       break;
4619
4620     case NEG:
4621       /* In general, this subtracts one sign bit copy.  But if the value
4622          is known to be positive, the number of sign bit copies is the
4623          same as that of the input.  Finally, if the input has just one bit
4624          that might be nonzero, all the bits are copies of the sign bit.  */
4625       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4626                                          known_x, known_mode, known_ret);
4627       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4628         return num0 > 1 ? num0 - 1 : 1;
4629
4630       nonzero = nonzero_bits (XEXP (x, 0), mode);
4631       if (nonzero == 1)
4632         return bitwidth;
4633
4634       if (num0 > 1
4635           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4636         num0--;
4637
4638       return num0;
4639
4640     case IOR:   case AND:   case XOR:
4641     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4642       /* Logical operations will preserve the number of sign-bit copies.
4643          MIN and MAX operations always return one of the operands.  */
4644       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4645                                          known_x, known_mode, known_ret);
4646       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4647                                          known_x, known_mode, known_ret);
4648       return MIN (num0, num1);
4649
4650     case PLUS:  case MINUS:
4651       /* For addition and subtraction, we can have a 1-bit carry.  However,
4652          if we are subtracting 1 from a positive number, there will not
4653          be such a carry.  Furthermore, if the positive number is known to
4654          be 0 or 1, we know the result is either -1 or 0.  */
4655
4656       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4657           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4658         {
4659           nonzero = nonzero_bits (XEXP (x, 0), mode);
4660           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4661             return (nonzero == 1 || nonzero == 0 ? bitwidth
4662                     : bitwidth - floor_log2 (nonzero) - 1);
4663         }
4664
4665       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4666                                          known_x, known_mode, known_ret);
4667       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4668                                          known_x, known_mode, known_ret);
4669       result = MAX (1, MIN (num0, num1) - 1);
4670
4671 #ifdef POINTERS_EXTEND_UNSIGNED
4672       /* If pointers extend signed and this is an addition or subtraction
4673          to a pointer in Pmode, all the bits above ptr_mode are known to be
4674          sign bit copies.  */
4675       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4676           && (code == PLUS || code == MINUS)
4677           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4678         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4679                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4680                       result);
4681 #endif
4682       return result;
4683
4684     case MULT:
4685       /* The number of bits of the product is the sum of the number of
4686          bits of both terms.  However, unless one of the terms if known
4687          to be positive, we must allow for an additional bit since negating
4688          a negative number can remove one sign bit copy.  */
4689
4690       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4691                                          known_x, known_mode, known_ret);
4692       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4693                                          known_x, known_mode, known_ret);
4694
4695       result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
4696       if (result > 0
4697           && (bitwidth > HOST_BITS_PER_WIDE_INT
4698               || (((nonzero_bits (XEXP (x, 0), mode)
4699                     & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4700                   && ((nonzero_bits (XEXP (x, 1), mode)
4701                        & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
4702         result--;
4703
4704       return MAX (1, result);
4705
4706     case UDIV:
4707       /* The result must be <= the first operand.  If the first operand
4708          has the high bit set, we know nothing about the number of sign
4709          bit copies.  */
4710       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4711         return 1;
4712       else if ((nonzero_bits (XEXP (x, 0), mode)
4713                 & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4714         return 1;
4715       else
4716         return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4717                                            known_x, known_mode, known_ret);
4718
4719     case UMOD:
4720       /* The result must be <= the second operand.  */
4721       return cached_num_sign_bit_copies (XEXP (x, 1), mode,
4722                                            known_x, known_mode, known_ret);
4723
4724     case DIV:
4725       /* Similar to unsigned division, except that we have to worry about
4726          the case where the divisor is negative, in which case we have
4727          to add 1.  */
4728       result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4729                                            known_x, known_mode, known_ret);
4730       if (result > 1
4731           && (bitwidth > HOST_BITS_PER_WIDE_INT
4732               || (nonzero_bits (XEXP (x, 1), mode)
4733                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4734         result--;
4735
4736       return result;
4737
4738     case MOD:
4739       result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4740                                            known_x, known_mode, known_ret);
4741       if (result > 1
4742           && (bitwidth > HOST_BITS_PER_WIDE_INT
4743               || (nonzero_bits (XEXP (x, 1), mode)
4744                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4745         result--;
4746
4747       return result;
4748
4749     case ASHIFTRT:
4750       /* Shifts by a constant add to the number of bits equal to the
4751          sign bit.  */
4752       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4753                                          known_x, known_mode, known_ret);
4754       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4755           && INTVAL (XEXP (x, 1)) > 0)
4756         num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
4757
4758       return num0;
4759
4760     case ASHIFT:
4761       /* Left shifts destroy copies.  */
4762       if (GET_CODE (XEXP (x, 1)) != CONST_INT
4763           || INTVAL (XEXP (x, 1)) < 0
4764           || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
4765         return 1;
4766
4767       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4768                                          known_x, known_mode, known_ret);
4769       return MAX (1, num0 - INTVAL (XEXP (x, 1)));
4770
4771     case IF_THEN_ELSE:
4772       num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4773                                          known_x, known_mode, known_ret);
4774       num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
4775                                          known_x, known_mode, known_ret);
4776       return MIN (num0, num1);
4777
4778     case EQ:  case NE:  case GE:  case GT:  case LE:  case LT:
4779     case UNEQ:  case LTGT:  case UNGE:  case UNGT:  case UNLE:  case UNLT:
4780     case GEU: case GTU: case LEU: case LTU:
4781     case UNORDERED: case ORDERED:
4782       /* If the constant is negative, take its 1's complement and remask.
4783          Then see how many zero bits we have.  */
4784       nonzero = STORE_FLAG_VALUE;
4785       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4786           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4787         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4788
4789       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4790
4791     default:
4792       break;
4793     }
4794
4795   /* If we haven't been able to figure it out by one of the above rules,
4796      see if some of the high-order bits are known to be zero.  If so,
4797      count those bits and return one less than that amount.  If we can't
4798      safely compute the mask for this mode, always return BITWIDTH.  */
4799
4800   bitwidth = GET_MODE_BITSIZE (mode);
4801   if (bitwidth > HOST_BITS_PER_WIDE_INT)
4802     return 1;
4803
4804   nonzero = nonzero_bits (x, mode);
4805   return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
4806          ? 1 : bitwidth - floor_log2 (nonzero) - 1;
4807 }