gcc/rtlanal.c

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