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 /* Throughout the rtx X, replace many registers according to REG_MAP.
2375    Return the replacement for X (which may be X with altered contents).
2376    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2377    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2378
2379    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2380    should not be mapped to pseudos or vice versa since validate_change
2381    is not called.
2382
2383    If REPLACE_DEST is 1, replacements are also done in destinations;
2384    otherwise, only sources are replaced.  */
2385
2386 rtx
2387 replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest)
2388 {
2389   enum rtx_code code;
2390   int i;
2391   const char *fmt;
2392
2393   if (x == 0)
2394     return x;
2395
2396   code = GET_CODE (x);
2397   switch (code)
2398     {
2399     case SCRATCH:
2400     case PC:
2401     case CC0:
2402     case CONST_INT:
2403     case CONST_DOUBLE:
2404     case CONST_VECTOR:
2405     case CONST:
2406     case SYMBOL_REF:
2407     case LABEL_REF:
2408       return x;
2409
2410     case REG:
2411       /* Verify that the register has an entry before trying to access it.  */
2412       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2413         {
2414           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2415              this replacement occurs more than once then each instance will
2416              get distinct rtx.  */
2417           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2418             return copy_rtx (reg_map[REGNO (x)]);
2419           return reg_map[REGNO (x)];
2420         }
2421       return x;
2422
2423     case SUBREG:
2424       /* Prevent making nested SUBREGs.  */
2425       if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs
2426           && reg_map[REGNO (SUBREG_REG (x))] != 0
2427           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2428         {
2429           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2430           return simplify_gen_subreg (GET_MODE (x), map_val,
2431                                       GET_MODE (SUBREG_REG (x)),
2432                                       SUBREG_BYTE (x));
2433         }
2434       break;
2435
2436     case SET:
2437       if (replace_dest)
2438         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2439
2440       else if (MEM_P (SET_DEST (x))
2441                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2442         /* Even if we are not to replace destinations, replace register if it
2443            is CONTAINED in destination (destination is memory or
2444            STRICT_LOW_PART).  */
2445         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2446                                                reg_map, nregs, 0);
2447       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2448         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2449         break;
2450
2451       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2452       return x;
2453
2454     default:
2455       break;
2456     }
2457
2458   fmt = GET_RTX_FORMAT (code);
2459   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2460     {
2461       if (fmt[i] == 'e')
2462         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2463       else if (fmt[i] == 'E')
2464         {
2465           int j;
2466           for (j = 0; j < XVECLEN (x, i); j++)
2467             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2468                                               nregs, replace_dest);
2469         }
2470     }
2471   return x;
2472 }
2473
2474 /* Replace occurrences of the old label in *X with the new one.
2475    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2476
2477 int
2478 replace_label (rtx *x, void *data)
2479 {
2480   rtx l = *x;
2481   rtx old_label = ((replace_label_data *) data)->r1;
2482   rtx new_label = ((replace_label_data *) data)->r2;
2483   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2484
2485   if (l == NULL_RTX)
2486     return 0;
2487
2488   if (GET_CODE (l) == SYMBOL_REF
2489       && CONSTANT_POOL_ADDRESS_P (l))
2490     {
2491       rtx c = get_pool_constant (l);
2492       if (rtx_referenced_p (old_label, c))
2493         {
2494           rtx new_c, new_l;
2495           replace_label_data *d = (replace_label_data *) data;
2496
2497           /* Create a copy of constant C; replace the label inside
2498              but do not update LABEL_NUSES because uses in constant pool
2499              are not counted.  */
2500           new_c = copy_rtx (c);
2501           d->update_label_nuses = false;
2502           for_each_rtx (&new_c, replace_label, data);
2503           d->update_label_nuses = update_label_nuses;
2504
2505           /* Add the new constant NEW_C to constant pool and replace
2506              the old reference to constant by new reference.  */
2507           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2508           *x = replace_rtx (l, l, new_l);
2509         }
2510       return 0;
2511     }
2512
2513   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2514      field.  This is not handled by for_each_rtx because it doesn't
2515      handle unprinted ('0') fields.  */
2516   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2517     JUMP_LABEL (l) = new_label;
2518
2519   if ((GET_CODE (l) == LABEL_REF
2520        || GET_CODE (l) == INSN_LIST)
2521       && XEXP (l, 0) == old_label)
2522     {
2523       XEXP (l, 0) = new_label;
2524       if (update_label_nuses)
2525         {
2526           ++LABEL_NUSES (new_label);
2527           --LABEL_NUSES (old_label);
2528         }
2529       return 0;
2530     }
2531
2532   return 0;
2533 }
2534
2535 /* When *BODY is equal to X or X is directly referenced by *BODY
2536    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2537    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2538
2539 static int
2540 rtx_referenced_p_1 (rtx *body, void *x)
2541 {
2542   rtx y = (rtx) x;
2543
2544   if (*body == NULL_RTX)
2545     return y == NULL_RTX;
2546
2547   /* Return true if a label_ref *BODY refers to label Y.  */
2548   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2549     return XEXP (*body, 0) == y;
2550
2551   /* If *BODY is a reference to pool constant traverse the constant.  */
2552   if (GET_CODE (*body) == SYMBOL_REF
2553       && CONSTANT_POOL_ADDRESS_P (*body))
2554     return rtx_referenced_p (y, get_pool_constant (*body));
2555
2556   /* By default, compare the RTL expressions.  */
2557   return rtx_equal_p (*body, y);
2558 }
2559
2560 /* Return true if X is referenced in BODY.  */
2561
2562 int
2563 rtx_referenced_p (rtx x, rtx body)
2564 {
2565   return for_each_rtx (&body, rtx_referenced_p_1, x);
2566 }
2567
2568 /* If INSN is a tablejump return true and store the label (before jump table) to
2569    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2570
2571 bool
2572 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2573 {
2574   rtx label, table;
2575
2576   if (JUMP_P (insn)
2577       && (label = JUMP_LABEL (insn)) != NULL_RTX
2578       && (table = next_active_insn (label)) != NULL_RTX
2579       && JUMP_P (table)
2580       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2581           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2582     {
2583       if (labelp)
2584         *labelp = label;
2585       if (tablep)
2586         *tablep = table;
2587       return true;
2588     }
2589   return false;
2590 }
2591
2592 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2593    constant that is not in the constant pool and not in the condition
2594    of an IF_THEN_ELSE.  */
2595
2596 static int
2597 computed_jump_p_1 (rtx x)
2598 {
2599   enum rtx_code code = GET_CODE (x);
2600   int i, j;
2601   const char *fmt;
2602
2603   switch (code)
2604     {
2605     case LABEL_REF:
2606     case PC:
2607       return 0;
2608
2609     case CONST:
2610     case CONST_INT:
2611     case CONST_DOUBLE:
2612     case CONST_VECTOR:
2613     case SYMBOL_REF:
2614     case REG:
2615       return 1;
2616
2617     case MEM:
2618       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2619                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2620
2621     case IF_THEN_ELSE:
2622       return (computed_jump_p_1 (XEXP (x, 1))
2623               || computed_jump_p_1 (XEXP (x, 2)));
2624
2625     default:
2626       break;
2627     }
2628
2629   fmt = GET_RTX_FORMAT (code);
2630   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2631     {
2632       if (fmt[i] == 'e'
2633           && computed_jump_p_1 (XEXP (x, i)))
2634         return 1;
2635
2636       else if (fmt[i] == 'E')
2637         for (j = 0; j < XVECLEN (x, i); j++)
2638           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2639             return 1;
2640     }
2641
2642   return 0;
2643 }
2644
2645 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2646
2647    Tablejumps and casesi insns are not considered indirect jumps;
2648    we can recognize them by a (use (label_ref)).  */
2649
2650 int
2651 computed_jump_p (rtx insn)
2652 {
2653   int i;
2654   if (JUMP_P (insn))
2655     {
2656       rtx pat = PATTERN (insn);
2657
2658       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2659         return 0;
2660       else if (GET_CODE (pat) == PARALLEL)
2661         {
2662           int len = XVECLEN (pat, 0);
2663           int has_use_labelref = 0;
2664
2665           for (i = len - 1; i >= 0; i--)
2666             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2667                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2668                     == LABEL_REF))
2669               has_use_labelref = 1;
2670
2671           if (! has_use_labelref)
2672             for (i = len - 1; i >= 0; i--)
2673               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2674                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2675                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2676                 return 1;
2677         }
2678       else if (GET_CODE (pat) == SET
2679                && SET_DEST (pat) == pc_rtx
2680                && computed_jump_p_1 (SET_SRC (pat)))
2681         return 1;
2682     }
2683   return 0;
2684 }
2685
2686 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2687    calls.  Processes the subexpressions of EXP and passes them to F.  */
2688 static int
2689 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2690 {
2691   int result, i, j;
2692   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2693   rtx *x;
2694
2695   for (; format[n] != '\0'; n++)
2696     {
2697       switch (format[n])
2698         {
2699         case 'e':
2700           /* Call F on X.  */
2701           x = &XEXP (exp, n);
2702           result = (*f) (x, data);
2703           if (result == -1)
2704             /* Do not traverse sub-expressions.  */
2705             continue;
2706           else if (result != 0)
2707             /* Stop the traversal.  */
2708             return result;
2709
2710           if (*x == NULL_RTX)
2711             /* There are no sub-expressions.  */
2712             continue;
2713
2714           i = non_rtx_starting_operands[GET_CODE (*x)];
2715           if (i >= 0)
2716             {
2717               result = for_each_rtx_1 (*x, i, f, data);
2718               if (result != 0)
2719                 return result;
2720             }
2721           break;
2722
2723         case 'V':
2724         case 'E':
2725           if (XVEC (exp, n) == 0)
2726             continue;
2727           for (j = 0; j < XVECLEN (exp, n); ++j)
2728             {
2729               /* Call F on X.  */
2730               x = &XVECEXP (exp, n, j);
2731               result = (*f) (x, data);
2732               if (result == -1)
2733                 /* Do not traverse sub-expressions.  */
2734                 continue;
2735               else if (result != 0)
2736                 /* Stop the traversal.  */
2737                 return result;
2738
2739               if (*x == NULL_RTX)
2740                 /* There are no sub-expressions.  */
2741                 continue;
2742
2743               i = non_rtx_starting_operands[GET_CODE (*x)];
2744               if (i >= 0)
2745                 {
2746                   result = for_each_rtx_1 (*x, i, f, data);
2747                   if (result != 0)
2748                     return result;
2749                 }
2750             }
2751           break;
2752
2753         default:
2754           /* Nothing to do.  */
2755           break;
2756         }
2757     }
2758
2759   return 0;
2760 }
2761
2762 /* Traverse X via depth-first search, calling F for each
2763    sub-expression (including X itself).  F is also passed the DATA.
2764    If F returns -1, do not traverse sub-expressions, but continue
2765    traversing the rest of the tree.  If F ever returns any other
2766    nonzero value, stop the traversal, and return the value returned
2767    by F.  Otherwise, return 0.  This function does not traverse inside
2768    tree structure that contains RTX_EXPRs, or into sub-expressions
2769    whose format code is `0' since it is not known whether or not those
2770    codes are actually RTL.
2771
2772    This routine is very general, and could (should?) be used to
2773    implement many of the other routines in this file.  */
2774
2775 int
2776 for_each_rtx (rtx *x, rtx_function f, void *data)
2777 {
2778   int result;
2779   int i;
2780
2781   /* Call F on X.  */
2782   result = (*f) (x, data);
2783   if (result == -1)
2784     /* Do not traverse sub-expressions.  */
2785     return 0;
2786   else if (result != 0)
2787     /* Stop the traversal.  */
2788     return result;
2789
2790   if (*x == NULL_RTX)
2791     /* There are no sub-expressions.  */
2792     return 0;
2793
2794   i = non_rtx_starting_operands[GET_CODE (*x)];
2795   if (i < 0)
2796     return 0;
2797
2798   return for_each_rtx_1 (*x, i, f, data);
2799 }
2800
2801
2802 /* Searches X for any reference to REGNO, returning the rtx of the
2803    reference found if any.  Otherwise, returns NULL_RTX.  */
2804
2805 rtx
2806 regno_use_in (unsigned int regno, rtx x)
2807 {
2808   const char *fmt;
2809   int i, j;
2810   rtx tem;
2811
2812   if (REG_P (x) && REGNO (x) == regno)
2813     return x;
2814
2815   fmt = GET_RTX_FORMAT (GET_CODE (x));
2816   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2817     {
2818       if (fmt[i] == 'e')
2819         {
2820           if ((tem = regno_use_in (regno, XEXP (x, i))))
2821             return tem;
2822         }
2823       else if (fmt[i] == 'E')
2824         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2825           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2826             return tem;
2827     }
2828
2829   return NULL_RTX;
2830 }
2831
2832 /* Return a value indicating whether OP, an operand of a commutative
2833    operation, is preferred as the first or second operand.  The higher
2834    the value, the stronger the preference for being the first operand.
2835    We use negative values to indicate a preference for the first operand
2836    and positive values for the second operand.  */
2837
2838 int
2839 commutative_operand_precedence (rtx op)
2840 {
2841   enum rtx_code code = GET_CODE (op);
2842
2843   /* Constants always come the second operand.  Prefer "nice" constants.  */
2844   if (code == CONST_INT)
2845     return -7;
2846   if (code == CONST_DOUBLE)
2847     return -6;
2848   op = avoid_constant_pool_reference (op);
2849   code = GET_CODE (op);
2850
2851   switch (GET_RTX_CLASS (code))
2852     {
2853     case RTX_CONST_OBJ:
2854       if (code == CONST_INT)
2855         return -5;
2856       if (code == CONST_DOUBLE)
2857         return -4;
2858       return -3;
2859
2860     case RTX_EXTRA:
2861       /* SUBREGs of objects should come second.  */
2862       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2863         return -2;
2864
2865       if (!CONSTANT_P (op))
2866         return 0;
2867       else
2868         /* As for RTX_CONST_OBJ.  */
2869         return -3;
2870
2871     case RTX_OBJ:
2872       /* Complex expressions should be the first, so decrease priority
2873          of objects.  */
2874       return -1;
2875
2876     case RTX_COMM_ARITH:
2877       /* Prefer operands that are themselves commutative to be first.
2878          This helps to make things linear.  In particular,
2879          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2880       return 4;
2881
2882     case RTX_BIN_ARITH:
2883       /* If only one operand is a binary expression, it will be the first
2884          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2885          is canonical, although it will usually be further simplified.  */
2886       return 2;
2887
2888     case RTX_UNARY:
2889       /* Then prefer NEG and NOT.  */
2890       if (code == NEG || code == NOT)
2891         return 1;
2892
2893     default:
2894       return 0;
2895     }
2896 }
2897
2898 /* Return 1 iff it is necessary to swap operands of commutative operation
2899    in order to canonicalize expression.  */
2900
2901 int
2902 swap_commutative_operands_p (rtx x, rtx y)
2903 {
2904   return (commutative_operand_precedence (x)
2905           < commutative_operand_precedence (y));
2906 }
2907
2908 /* Return 1 if X is an autoincrement side effect and the register is
2909    not the stack pointer.  */
2910 int
2911 auto_inc_p (rtx x)
2912 {
2913   switch (GET_CODE (x))
2914     {
2915     case PRE_INC:
2916     case POST_INC:
2917     case PRE_DEC:
2918     case POST_DEC:
2919     case PRE_MODIFY:
2920     case POST_MODIFY:
2921       /* There are no REG_INC notes for SP.  */
2922       if (XEXP (x, 0) != stack_pointer_rtx)
2923         return 1;
2924     default:
2925       break;
2926     }
2927   return 0;
2928 }
2929
2930 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2931 int
2932 loc_mentioned_in_p (rtx *loc, rtx in)
2933 {
2934   enum rtx_code code = GET_CODE (in);
2935   const char *fmt = GET_RTX_FORMAT (code);
2936   int i, j;
2937
2938   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2939     {
2940       if (loc == &in->u.fld[i].rt_rtx)
2941         return 1;
2942       if (fmt[i] == 'e')
2943         {
2944           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2945             return 1;
2946         }
2947       else if (fmt[i] == 'E')
2948         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2949           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2950             return 1;
2951     }
2952   return 0;
2953 }
2954
2955 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
2956    and SUBREG_BYTE, return the bit offset where the subreg begins
2957    (counting from the least significant bit of the operand).  */
2958
2959 unsigned int
2960 subreg_lsb_1 (enum machine_mode outer_mode,
2961               enum machine_mode inner_mode,
2962               unsigned int subreg_byte)
2963 {
2964   unsigned int bitpos;
2965   unsigned int byte;
2966   unsigned int word;
2967
2968   /* A paradoxical subreg begins at bit position 0.  */
2969   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
2970     return 0;
2971
2972   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2973     /* If the subreg crosses a word boundary ensure that
2974        it also begins and ends on a word boundary.  */
2975     gcc_assert (!((subreg_byte % UNITS_PER_WORD
2976                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
2977                   && (subreg_byte % UNITS_PER_WORD
2978                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
2979
2980   if (WORDS_BIG_ENDIAN)
2981     word = (GET_MODE_SIZE (inner_mode)
2982             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
2983   else
2984     word = subreg_byte / UNITS_PER_WORD;
2985   bitpos = word * BITS_PER_WORD;
2986
2987   if (BYTES_BIG_ENDIAN)
2988     byte = (GET_MODE_SIZE (inner_mode)
2989             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
2990   else
2991     byte = subreg_byte % UNITS_PER_WORD;
2992   bitpos += byte * BITS_PER_UNIT;
2993
2994   return bitpos;
2995 }
2996
2997 /* Given a subreg X, return the bit offset where the subreg begins
2998    (counting from the least significant bit of the reg).  */
2999
3000 unsigned int
3001 subreg_lsb (rtx x)
3002 {
3003   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3004                        SUBREG_BYTE (x));
3005 }
3006
3007 /* This function returns the regno offset of a subreg expression.
3008    xregno - A regno of an inner hard subreg_reg (or what will become one).
3009    xmode  - The mode of xregno.
3010    offset - The byte offset.
3011    ymode  - The mode of a top level SUBREG (or what may become one).
3012    RETURN - The regno offset which would be used.  */
3013 unsigned int
3014 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3015                      unsigned int offset, enum machine_mode ymode)
3016 {
3017   int nregs_xmode, nregs_ymode, nregs_xmode_unit_int;
3018   int mode_multiple, nregs_multiple;
3019   int y_offset;
3020   enum machine_mode xmode_unit, xmode_unit_int;
3021
3022   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3023
3024   if (GET_MODE_INNER (xmode) == VOIDmode)
3025     xmode_unit = xmode;
3026   else
3027     xmode_unit = GET_MODE_INNER (xmode);
3028
3029   if (FLOAT_MODE_P (xmode_unit))
3030     {
3031       xmode_unit_int = int_mode_for_mode (xmode_unit);
3032       if (xmode_unit_int == BLKmode)
3033         /* It's probably bad to be here; a port should have an integer mode
3034            that's the same size as anything of which it takes a SUBREG.  */
3035         xmode_unit_int = xmode_unit;
3036     }
3037   else
3038     xmode_unit_int = xmode_unit;
3039
3040   nregs_xmode_unit_int = hard_regno_nregs[xregno][xmode_unit_int];
3041
3042   /* Adjust nregs_xmode to allow for 'holes'.  */
3043   if (nregs_xmode_unit_int != hard_regno_nregs[xregno][xmode_unit])
3044     nregs_xmode = nregs_xmode_unit_int * GET_MODE_NUNITS (xmode);
3045   else
3046     nregs_xmode = hard_regno_nregs[xregno][xmode];
3047
3048   nregs_ymode = hard_regno_nregs[xregno][ymode];
3049
3050   /* If this is a big endian paradoxical subreg, which uses more actual
3051      hard registers than the original register, we must return a negative
3052      offset so that we find the proper highpart of the register.  */
3053   if (offset == 0
3054       && nregs_ymode > nregs_xmode
3055       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3056           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3057     return nregs_xmode - nregs_ymode;
3058
3059   if (offset == 0 || nregs_xmode == nregs_ymode)
3060     return 0;
3061
3062   /* Size of ymode must not be greater than the size of xmode.  */
3063   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3064   gcc_assert (mode_multiple != 0);
3065
3066   y_offset = offset / GET_MODE_SIZE (ymode);
3067   nregs_multiple =  nregs_xmode / nregs_ymode;
3068   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3069 }
3070
3071 /* This function returns true when the offset is representable via
3072    subreg_offset in the given regno.
3073    xregno - A regno of an inner hard subreg_reg (or what will become one).
3074    xmode  - The mode of xregno.
3075    offset - The byte offset.
3076    ymode  - The mode of a top level SUBREG (or what may become one).
3077    RETURN - Whether the offset is representable.  */
3078 bool
3079 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3080                                unsigned int offset, enum machine_mode ymode)
3081 {
3082   int nregs_xmode, nregs_ymode, nregs_xmode_unit, nregs_xmode_unit_int;
3083   int mode_multiple, nregs_multiple;
3084   int y_offset;
3085   enum machine_mode xmode_unit, xmode_unit_int;
3086
3087   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3088
3089   if (GET_MODE_INNER (xmode) == VOIDmode)
3090     xmode_unit = xmode;
3091   else
3092     xmode_unit = GET_MODE_INNER (xmode);
3093
3094   if (FLOAT_MODE_P (xmode_unit))
3095     {
3096       xmode_unit_int = int_mode_for_mode (xmode_unit);
3097       if (xmode_unit_int == BLKmode)
3098         /* It's probably bad to be here; a port should have an integer mode
3099            that's the same size as anything of which it takes a SUBREG.  */
3100         xmode_unit_int = xmode_unit;
3101     }
3102   else
3103     xmode_unit_int = xmode_unit;
3104
3105   nregs_xmode_unit = hard_regno_nregs[xregno][xmode_unit];
3106   nregs_xmode_unit_int = hard_regno_nregs[xregno][xmode_unit_int];
3107
3108   /* If there are holes in a non-scalar mode in registers, we expect
3109      that it is made up of its units concatenated together.  */
3110   if (nregs_xmode_unit != nregs_xmode_unit_int)
3111     {
3112       gcc_assert (nregs_xmode_unit * GET_MODE_NUNITS (xmode)
3113                   == hard_regno_nregs[xregno][xmode]);
3114
3115       /* You can only ask for a SUBREG of a value with holes in the middle
3116          if you don't cross the holes.  (Such a SUBREG should be done by
3117          picking a different register class, or doing it in memory if
3118          necessary.)  An example of a value with holes is XCmode on 32-bit
3119          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
3120          3 for each part, but in memory it's two 128-bit parts.
3121          Padding is assumed to be at the end (not necessarily the 'high part')
3122          of each unit.  */
3123       if (nregs_xmode_unit != nregs_xmode_unit_int
3124           && (offset / GET_MODE_SIZE (xmode_unit_int) + 1
3125               < GET_MODE_NUNITS (xmode))
3126           && (offset / GET_MODE_SIZE (xmode_unit_int)
3127               != ((offset + GET_MODE_SIZE (ymode) - 1)
3128                   / GET_MODE_SIZE (xmode_unit_int))))
3129         return false;
3130
3131       nregs_xmode = nregs_xmode_unit_int * GET_MODE_NUNITS (xmode);
3132     }
3133   else
3134     nregs_xmode = hard_regno_nregs[xregno][xmode];
3135
3136   nregs_ymode = hard_regno_nregs[xregno][ymode];
3137
3138   /* Paradoxical subregs are otherwise valid.  */
3139   if (offset == 0
3140       && nregs_ymode > nregs_xmode
3141       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3142           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3143     return true;
3144
3145   /* Lowpart subregs are otherwise valid.  */
3146   if (offset == subreg_lowpart_offset (ymode, xmode))
3147     return true;
3148
3149   /* This should always pass, otherwise we don't know how to verify
3150      the constraint.  These conditions may be relaxed but
3151      subreg_regno_offset would need to be redesigned.  */
3152   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3153   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3154
3155   /* The XMODE value can be seen as a vector of NREGS_XMODE
3156      values.  The subreg must represent a lowpart of given field.
3157      Compute what field it is.  */
3158   offset -= subreg_lowpart_offset (ymode,
3159                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3160                                                   / nregs_xmode,
3161                                                   MODE_INT, 0));
3162
3163   /* Size of ymode must not be greater than the size of xmode.  */
3164   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3165   gcc_assert (mode_multiple != 0);
3166
3167   y_offset = offset / GET_MODE_SIZE (ymode);
3168   nregs_multiple =  nregs_xmode / nregs_ymode;
3169
3170   gcc_assert ((offset % GET_MODE_SIZE (ymode)) == 0);
3171   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3172
3173   return (!(y_offset % (mode_multiple / nregs_multiple)));
3174 }
3175
3176 /* Return the final regno that a subreg expression refers to.  */
3177 unsigned int
3178 subreg_regno (rtx x)
3179 {
3180   unsigned int ret;
3181   rtx subreg = SUBREG_REG (x);
3182   int regno = REGNO (subreg);
3183
3184   ret = regno + subreg_regno_offset (regno,
3185                                      GET_MODE (subreg),
3186                                      SUBREG_BYTE (x),
3187                                      GET_MODE (x));
3188   return ret;
3189
3190 }
3191 struct parms_set_data
3192 {
3193   int nregs;
3194   HARD_REG_SET regs;
3195 };
3196
3197 /* Helper function for noticing stores to parameter registers.  */
3198 static void
3199 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3200 {
3201   struct parms_set_data *d = data;
3202   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3203       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3204     {
3205       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3206       d->nregs--;
3207     }
3208 }
3209
3210 /* Look backward for first parameter to be loaded.
3211    Note that loads of all parameters will not necessarily be
3212    found if CSE has eliminated some of them (e.g., an argument
3213    to the outer function is passed down as a parameter).
3214    Do not skip BOUNDARY.  */
3215 rtx
3216 find_first_parameter_load (rtx call_insn, rtx boundary)
3217 {
3218   struct parms_set_data parm;
3219   rtx p, before, first_set;
3220
3221   /* Since different machines initialize their parameter registers
3222      in different orders, assume nothing.  Collect the set of all
3223      parameter registers.  */
3224   CLEAR_HARD_REG_SET (parm.regs);
3225   parm.nregs = 0;
3226   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3227     if (GET_CODE (XEXP (p, 0)) == USE
3228         && REG_P (XEXP (XEXP (p, 0), 0)))
3229       {
3230         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3231
3232         /* We only care about registers which can hold function
3233            arguments.  */
3234         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3235           continue;
3236
3237         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3238         parm.nregs++;
3239       }
3240   before = call_insn;
3241   first_set = call_insn;
3242
3243   /* Search backward for the first set of a register in this set.  */
3244   while (parm.nregs && before != boundary)
3245     {
3246       before = PREV_INSN (before);
3247
3248       /* It is possible that some loads got CSEed from one call to
3249          another.  Stop in that case.  */
3250       if (CALL_P (before))
3251         break;
3252
3253       /* Our caller needs either ensure that we will find all sets
3254          (in case code has not been optimized yet), or take care
3255          for possible labels in a way by setting boundary to preceding
3256          CODE_LABEL.  */
3257       if (LABEL_P (before))
3258         {
3259           gcc_assert (before == boundary);
3260           break;
3261         }
3262
3263       if (INSN_P (before))
3264         {
3265           int nregs_old = parm.nregs;
3266           note_stores (PATTERN (before), parms_set, &parm);
3267           /* If we found something that did not set a parameter reg,
3268              we're done.  Do not keep going, as that might result
3269              in hoisting an insn before the setting of a pseudo
3270              that is used by the hoisted insn. */
3271           if (nregs_old != parm.nregs)
3272             first_set = before;
3273           else
3274             break;
3275         }
3276     }
3277   return first_set;
3278 }
3279
3280 /* Return true if we should avoid inserting code between INSN and preceding
3281    call instruction.  */
3282
3283 bool
3284 keep_with_call_p (rtx insn)
3285 {
3286   rtx set;
3287
3288   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3289     {
3290       if (REG_P (SET_DEST (set))
3291           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3292           && fixed_regs[REGNO (SET_DEST (set))]
3293           && general_operand (SET_SRC (set), VOIDmode))
3294         return true;
3295       if (REG_P (SET_SRC (set))
3296           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3297           && REG_P (SET_DEST (set))
3298           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3299         return true;
3300       /* There may be a stack pop just after the call and before the store
3301          of the return register.  Search for the actual store when deciding
3302          if we can break or not.  */
3303       if (SET_DEST (set) == stack_pointer_rtx)
3304         {
3305           rtx i2 = next_nonnote_insn (insn);
3306           if (i2 && keep_with_call_p (i2))
3307             return true;
3308         }
3309     }
3310   return false;
3311 }
3312
3313 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3314    to non-complex jumps.  That is, direct unconditional, conditional,
3315    and tablejumps, but not computed jumps or returns.  It also does
3316    not apply to the fallthru case of a conditional jump.  */
3317
3318 bool
3319 label_is_jump_target_p (rtx label, rtx jump_insn)
3320 {
3321   rtx tmp = JUMP_LABEL (jump_insn);
3322
3323   if (label == tmp)
3324     return true;
3325
3326   if (tablejump_p (jump_insn, NULL, &tmp))
3327     {
3328       rtvec vec = XVEC (PATTERN (tmp),
3329                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3330       int i, veclen = GET_NUM_ELEM (vec);
3331
3332       for (i = 0; i < veclen; ++i)
3333         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3334           return true;
3335     }
3336
3337   return false;
3338 }
3339
3340 \f
3341 /* Return an estimate of the cost of computing rtx X.
3342    One use is in cse, to decide which expression to keep in the hash table.
3343    Another is in rtl generation, to pick the cheapest way to multiply.
3344    Other uses like the latter are expected in the future.  */
3345
3346 int
3347 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3348 {
3349   int i, j;
3350   enum rtx_code code;
3351   const char *fmt;
3352   int total;
3353
3354   if (x == 0)
3355     return 0;
3356
3357   /* Compute the default costs of certain things.
3358      Note that targetm.rtx_costs can override the defaults.  */
3359
3360   code = GET_CODE (x);
3361   switch (code)
3362     {
3363     case MULT:
3364       total = COSTS_N_INSNS (5);
3365       break;
3366     case DIV:
3367     case UDIV:
3368     case MOD:
3369     case UMOD:
3370       total = COSTS_N_INSNS (7);
3371       break;
3372     case USE:
3373       /* Used in loop.c and combine.c as a marker.  */
3374       total = 0;
3375       break;
3376     default:
3377       total = COSTS_N_INSNS (1);
3378     }
3379
3380   switch (code)
3381     {
3382     case REG:
3383       return 0;
3384
3385     case SUBREG:
3386       total = 0;
3387       /* If we can't tie these modes, make this expensive.  The larger
3388          the mode, the more expensive it is.  */
3389       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3390         return COSTS_N_INSNS (2
3391                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3392       break;
3393
3394     default:
3395       if (targetm.rtx_costs (x, code, outer_code, &total))
3396         return total;
3397       break;
3398     }
3399
3400   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3401      which is already in total.  */
3402
3403   fmt = GET_RTX_FORMAT (code);
3404   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3405     if (fmt[i] == 'e')
3406       total += rtx_cost (XEXP (x, i), code);
3407     else if (fmt[i] == 'E')
3408       for (j = 0; j < XVECLEN (x, i); j++)
3409         total += rtx_cost (XVECEXP (x, i, j), code);
3410
3411   return total;
3412 }
3413 \f
3414 /* Return cost of address expression X.
3415    Expect that X is properly formed address reference.  */
3416
3417 int
3418 address_cost (rtx x, enum machine_mode mode)
3419 {
3420   /* We may be asked for cost of various unusual addresses, such as operands
3421      of push instruction.  It is not worthwhile to complicate writing
3422      of the target hook by such cases.  */
3423
3424   if (!memory_address_p (mode, x))
3425     return 1000;
3426
3427   return targetm.address_cost (x);
3428 }
3429
3430 /* If the target doesn't override, compute the cost as with arithmetic.  */
3431
3432 int
3433 default_address_cost (rtx x)
3434 {
3435   return rtx_cost (x, MEM);
3436 }
3437 \f
3438
3439 unsigned HOST_WIDE_INT
3440 nonzero_bits (rtx x, enum machine_mode mode)
3441 {
3442   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3443 }
3444
3445 unsigned int
3446 num_sign_bit_copies (rtx x, enum machine_mode mode)
3447 {
3448   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3449 }
3450
3451 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3452    It avoids exponential behavior in nonzero_bits1 when X has
3453    identical subexpressions on the first or the second level.  */
3454
3455 static unsigned HOST_WIDE_INT
3456 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3457                      enum machine_mode known_mode,
3458                      unsigned HOST_WIDE_INT known_ret)
3459 {
3460   if (x == known_x && mode == known_mode)
3461     return known_ret;
3462
3463   /* Try to find identical subexpressions.  If found call
3464      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3465      precomputed value for the subexpression as KNOWN_RET.  */
3466
3467   if (ARITHMETIC_P (x))
3468     {
3469       rtx x0 = XEXP (x, 0);
3470       rtx x1 = XEXP (x, 1);
3471
3472       /* Check the first level.  */
3473       if (x0 == x1)
3474         return nonzero_bits1 (x, mode, x0, mode,
3475                               cached_nonzero_bits (x0, mode, known_x,
3476                                                    known_mode, known_ret));
3477
3478       /* Check the second level.  */
3479       if (ARITHMETIC_P (x0)
3480           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3481         return nonzero_bits1 (x, mode, x1, mode,
3482                               cached_nonzero_bits (x1, mode, known_x,
3483                                                    known_mode, known_ret));
3484
3485       if (ARITHMETIC_P (x1)
3486           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3487         return nonzero_bits1 (x, mode, x0, mode,
3488                               cached_nonzero_bits (x0, mode, known_x,
3489                                                    known_mode, known_ret));
3490     }
3491
3492   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3493 }
3494
3495 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3496    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3497    is less useful.  We can't allow both, because that results in exponential
3498    run time recursion.  There is a nullstone testcase that triggered
3499    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3500 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3501
3502 /* Given an expression, X, compute which bits in X can be nonzero.
3503    We don't care about bits outside of those defined in MODE.
3504
3505    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3506    an arithmetic operation, we can do better.  */
3507
3508 static unsigned HOST_WIDE_INT
3509 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3510                enum machine_mode known_mode,
3511                unsigned HOST_WIDE_INT known_ret)
3512 {
3513   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3514   unsigned HOST_WIDE_INT inner_nz;
3515   enum rtx_code code;
3516   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3517
3518   /* For floating-point values, assume all bits are needed.  */
3519   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3520     return nonzero;
3521
3522   /* If X is wider than MODE, use its mode instead.  */
3523   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3524     {
3525       mode = GET_MODE (x);
3526       nonzero = GET_MODE_MASK (mode);
3527       mode_width = GET_MODE_BITSIZE (mode);
3528     }
3529
3530   if (mode_width > HOST_BITS_PER_WIDE_INT)
3531     /* Our only callers in this case look for single bit values.  So
3532        just return the mode mask.  Those tests will then be false.  */
3533     return nonzero;
3534
3535 #ifndef WORD_REGISTER_OPERATIONS
3536   /* If MODE is wider than X, but both are a single word for both the host
3537      and target machines, we can compute this from which bits of the
3538      object might be nonzero in its own mode, taking into account the fact
3539      that on many CISC machines, accessing an object in a wider mode
3540      causes the high-order bits to become undefined.  So they are
3541      not known to be zero.  */
3542
3543   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3544       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3545       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3546       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3547     {
3548       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3549                                       known_x, known_mode, known_ret);
3550       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3551       return nonzero;
3552     }
3553 #endif
3554
3555   code = GET_CODE (x);
3556   switch (code)
3557     {
3558     case REG:
3559 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3560       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3561          all the bits above ptr_mode are known to be zero.  */
3562       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3563           && REG_POINTER (x))
3564         nonzero &= GET_MODE_MASK (ptr_mode);
3565 #endif
3566
3567       /* Include declared information about alignment of pointers.  */
3568       /* ??? We don't properly preserve REG_POINTER changes across
3569          pointer-to-integer casts, so we can't trust it except for
3570          things that we know must be pointers.  See execute/960116-1.c.  */
3571       if ((x == stack_pointer_rtx
3572            || x == frame_pointer_rtx
3573            || x == arg_pointer_rtx)
3574           && REGNO_POINTER_ALIGN (REGNO (x)))
3575         {
3576           unsigned HOST_WIDE_INT alignment
3577             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3578
3579 #ifdef PUSH_ROUNDING
3580           /* If PUSH_ROUNDING is defined, it is possible for the
3581              stack to be momentarily aligned only to that amount,
3582              so we pick the least alignment.  */
3583           if (x == stack_pointer_rtx && PUSH_ARGS)
3584             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3585                              alignment);
3586 #endif
3587
3588           nonzero &= ~(alignment - 1);
3589         }
3590
3591       {
3592         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3593         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3594                                               known_mode, known_ret,
3595                                               &nonzero_for_hook);
3596
3597         if (new)
3598           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3599                                                    known_mode, known_ret);
3600
3601         return nonzero_for_hook;
3602       }
3603
3604     case CONST_INT:
3605 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3606       /* If X is negative in MODE, sign-extend the value.  */
3607       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3608           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3609         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3610 #endif
3611
3612       return INTVAL (x);
3613
3614     case MEM:
3615 #ifdef LOAD_EXTEND_OP
3616       /* In many, if not most, RISC machines, reading a byte from memory
3617          zeros the rest of the register.  Noticing that fact saves a lot
3618          of extra zero-extends.  */
3619       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3620         nonzero &= GET_MODE_MASK (GET_MODE (x));
3621 #endif
3622       break;
3623
3624     case EQ:  case NE:
3625     case UNEQ:  case LTGT:
3626     case GT:  case GTU:  case UNGT:
3627     case LT:  case LTU:  case UNLT:
3628     case GE:  case GEU:  case UNGE:
3629     case LE:  case LEU:  case UNLE:
3630     case UNORDERED: case ORDERED:
3631       /* If this produces an integer result, we know which bits are set.
3632          Code here used to clear bits outside the mode of X, but that is
3633          now done above.  */
3634       /* Mind that MODE is the mode the caller wants to look at this
3635          operation in, and not the actual operation mode.  We can wind
3636          up with (subreg:DI (gt:V4HI x y)), and we don't have anything
3637          that describes the results of a vector compare.  */
3638       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
3639           && mode_width <= HOST_BITS_PER_WIDE_INT)
3640         nonzero = STORE_FLAG_VALUE;
3641       break;
3642
3643     case NEG:
3644 #if 0
3645       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3646          and num_sign_bit_copies.  */
3647       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3648           == GET_MODE_BITSIZE (GET_MODE (x)))
3649         nonzero = 1;
3650 #endif
3651
3652       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3653         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3654       break;
3655
3656     case ABS:
3657 #if 0
3658       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3659          and num_sign_bit_copies.  */
3660       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3661           == GET_MODE_BITSIZE (GET_MODE (x)))
3662         nonzero = 1;
3663 #endif
3664       break;
3665
3666     case TRUNCATE:
3667       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
3668                                        known_x, known_mode, known_ret)
3669                   & GET_MODE_MASK (mode));
3670       break;
3671
3672     case ZERO_EXTEND:
3673       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3674                                       known_x, known_mode, known_ret);
3675       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3676         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3677       break;
3678
3679     case SIGN_EXTEND:
3680       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
3681          Otherwise, show all the bits in the outer mode but not the inner
3682          may be nonzero.  */
3683       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
3684                                       known_x, known_mode, known_ret);
3685       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3686         {
3687           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3688           if (inner_nz
3689               & (((HOST_WIDE_INT) 1
3690                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
3691             inner_nz |= (GET_MODE_MASK (mode)
3692                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
3693         }
3694
3695       nonzero &= inner_nz;
3696       break;
3697
3698     case AND:
3699       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3700                                        known_x, known_mode, known_ret)
3701                  & cached_nonzero_bits (XEXP (x, 1), mode,
3702                                         known_x, known_mode, known_ret);
3703       break;
3704
3705     case XOR:   case IOR:
3706     case UMIN:  case UMAX:  case SMIN:  case SMAX:
3707       {
3708         unsigned HOST_WIDE_INT nonzero0 =
3709           cached_nonzero_bits (XEXP (x, 0), mode,
3710                                known_x, known_mode, known_ret);
3711
3712         /* Don't call nonzero_bits for the second time if it cannot change
3713            anything.  */
3714         if ((nonzero & nonzero0) != nonzero)
3715           nonzero &= nonzero0
3716                      | cached_nonzero_bits (XEXP (x, 1), mode,
3717                                             known_x, known_mode, known_ret);
3718       }
3719       break;
3720
3721     case PLUS:  case MINUS:
3722     case MULT:
3723     case DIV:   case UDIV:
3724     case MOD:   case UMOD:
3725       /* We can apply the rules of arithmetic to compute the number of
3726          high- and low-order zero bits of these operations.  We start by
3727          computing the width (position of the highest-order nonzero bit)
3728          and the number of low-order zero bits for each value.  */
3729       {
3730         unsigned HOST_WIDE_INT nz0 =
3731           cached_nonzero_bits (XEXP (x, 0), mode,
3732                                known_x, known_mode, known_ret);
3733         unsigned HOST_WIDE_INT nz1 =
3734           cached_nonzero_bits (XEXP (x, 1), mode,
3735                                known_x, known_mode, known_ret);
3736         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
3737         int width0 = floor_log2 (nz0) + 1;
3738         int width1 = floor_log2 (nz1) + 1;
3739         int low0 = floor_log2 (nz0 & -nz0);
3740         int low1 = floor_log2 (nz1 & -nz1);
3741         HOST_WIDE_INT op0_maybe_minusp
3742           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
3743         HOST_WIDE_INT op1_maybe_minusp
3744           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
3745         unsigned int result_width = mode_width;
3746         int result_low = 0;
3747
3748         switch (code)
3749           {
3750           case PLUS:
3751             result_width = MAX (width0, width1) + 1;
3752             result_low = MIN (low0, low1);
3753             break;
3754           case MINUS:
3755             result_low = MIN (low0, low1);
3756             break;
3757           case MULT:
3758             result_width = width0 + width1;
3759             result_low = low0 + low1;
3760             break;
3761           case DIV:
3762             if (width1 == 0)
3763               break;
3764             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3765               result_width = width0;
3766             break;
3767           case UDIV:
3768             if (width1 == 0)
3769               break;
3770             result_width = width0;
3771             break;
3772           case MOD:
3773             if (width1 == 0)
3774               break;
3775             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3776               result_width = MIN (width0, width1);
3777             result_low = MIN (low0, low1);
3778             break;
3779           case UMOD:
3780             if (width1 == 0)
3781               break;
3782             result_width = MIN (width0, width1);
3783             result_low = MIN (low0, low1);
3784             break;
3785           default:
3786             gcc_unreachable ();
3787           }
3788
3789         if (result_width < mode_width)
3790           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
3791
3792         if (result_low > 0)
3793           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
3794
3795 #ifdef POINTERS_EXTEND_UNSIGNED
3796         /* If pointers extend unsigned and this is an addition or subtraction
3797            to a pointer in Pmode, all the bits above ptr_mode are known to be
3798            zero.  */
3799         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
3800             && (code == PLUS || code == MINUS)
3801             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
3802           nonzero &= GET_MODE_MASK (ptr_mode);
3803 #endif
3804       }
3805       break;
3806
3807     case ZERO_EXTRACT:
3808       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3809           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3810         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
3811       break;
3812
3813     case SUBREG:
3814       /* If this is a SUBREG formed for a promoted variable that has
3815          been zero-extended, we know that at least the high-order bits
3816          are zero, though others might be too.  */
3817
3818       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
3819         nonzero = GET_MODE_MASK (GET_MODE (x))
3820                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
3821                                          known_x, known_mode, known_ret);
3822
3823       /* If the inner mode is a single word for both the host and target
3824          machines, we can compute this from which bits of the inner
3825          object might be nonzero.  */
3826       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
3827           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
3828               <= HOST_BITS_PER_WIDE_INT))
3829         {
3830           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
3831                                           known_x, known_mode, known_ret);
3832
3833 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
3834           /* If this is a typical RISC machine, we only have to worry
3835              about the way loads are extended.  */
3836           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
3837                ? (((nonzero
3838                     & (((unsigned HOST_WIDE_INT) 1
3839                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
3840                    != 0))
3841                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
3842               || !MEM_P (SUBREG_REG (x)))
3843 #endif
3844             {
3845               /* On many CISC machines, accessing an object in a wider mode
3846                  causes the high-order bits to become undefined.  So they are
3847                  not known to be zero.  */
3848               if (GET_MODE_SIZE (GET_MODE (x))
3849                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3850                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
3851                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
3852             }
3853         }
3854       break;
3855
3856     case ASHIFTRT:
3857     case LSHIFTRT:
3858     case ASHIFT:
3859     case ROTATE:
3860       /* The nonzero bits are in two classes: any bits within MODE
3861          that aren't in GET_MODE (x) are always significant.  The rest of the
3862          nonzero bits are those that are significant in the operand of
3863          the shift when shifted the appropriate number of bits.  This
3864          shows that high-order bits are cleared by the right shift and
3865          low-order bits by left shifts.  */
3866       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3867           && INTVAL (XEXP (x, 1)) >= 0
3868           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3869         {
3870           enum machine_mode inner_mode = GET_MODE (x);
3871           unsigned int width = GET_MODE_BITSIZE (inner_mode);
3872           int count = INTVAL (XEXP (x, 1));
3873           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
3874           unsigned HOST_WIDE_INT op_nonzero =
3875             cached_nonzero_bits (XEXP (x, 0), mode,
3876                                  known_x, known_mode, known_ret);
3877           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
3878           unsigned HOST_WIDE_INT outer = 0;
3879
3880           if (mode_width > width)
3881             outer = (op_nonzero & nonzero & ~mode_mask);
3882
3883           if (code == LSHIFTRT)
3884             inner >>= count;
3885           else if (code == ASHIFTRT)
3886             {
3887               inner >>= count;
3888
3889               /* If the sign bit may have been nonzero before the shift, we
3890                  need to mark all the places it could have been copied to
3891                  by the shift as possibly nonzero.  */
3892               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
3893                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
3894             }
3895           else if (code == ASHIFT)
3896             inner <<= count;
3897           else
3898             inner = ((inner << (count % width)
3899                       | (inner >> (width - (count % width)))) & mode_mask);
3900
3901           nonzero &= (outer | inner);
3902         }
3903       break;
3904
3905     case FFS:
3906     case POPCOUNT:
3907       /* This is at most the number of bits in the mode.  */
3908       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
3909       break;
3910
3911     case CLZ:
3912       /* If CLZ has a known value at zero, then the nonzero bits are
3913          that value, plus the number of bits in the mode minus one.  */
3914       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3915         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3916       else
3917         nonzero = -1;
3918       break;
3919
3920     case CTZ:
3921       /* If CTZ has a known value at zero, then the nonzero bits are
3922          that value, plus the number of bits in the mode minus one.  */
3923       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3924         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3925       else
3926         nonzero = -1;
3927       break;
3928
3929     case PARITY:
3930       nonzero = 1;
3931       break;
3932
3933     case IF_THEN_ELSE:
3934       {
3935         unsigned HOST_WIDE_INT nonzero_true =
3936           cached_nonzero_bits (XEXP (x, 1), mode,
3937                                known_x, known_mode, known_ret);
3938
3939         /* Don't call nonzero_bits for the second time if it cannot change
3940            anything.  */
3941         if ((nonzero & nonzero_true) != nonzero)
3942           nonzero &= nonzero_true
3943                      | cached_nonzero_bits (XEXP (x, 2), mode,
3944                                             known_x, known_mode, known_ret);
3945       }
3946       break;
3947
3948     default:
3949       break;
3950     }
3951
3952   return nonzero;
3953 }
3954
3955 /* See the macro definition above.  */
3956 #undef cached_num_sign_bit_copies
3957
3958 \f
3959 /* The function cached_num_sign_bit_copies is a wrapper around
3960    num_sign_bit_copies1.  It avoids exponential behavior in
3961    num_sign_bit_copies1 when X has identical subexpressions on the
3962    first or the second level.  */
3963
3964 static unsigned int
3965 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
3966                             enum machine_mode known_mode,
3967                             unsigned int known_ret)
3968 {
3969   if (x == known_x && mode == known_mode)
3970     return known_ret;
3971
3972   /* Try to find identical subexpressions.  If found call
3973      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
3974      the precomputed value for the subexpression as KNOWN_RET.  */
3975
3976   if (ARITHMETIC_P (x))
3977     {
3978       rtx x0 = XEXP (x, 0);
3979       rtx x1 = XEXP (x, 1);
3980
3981       /* Check the first level.  */
3982       if (x0 == x1)
3983         return
3984           num_sign_bit_copies1 (x, mode, x0, mode,
3985                                 cached_num_sign_bit_copies (x0, mode, known_x,
3986                                                             known_mode,
3987                                                             known_ret));
3988
3989       /* Check the second level.  */
3990       if (ARITHMETIC_P (x0)
3991           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3992         return
3993           num_sign_bit_copies1 (x, mode, x1, mode,
3994                                 cached_num_sign_bit_copies (x1, mode, known_x,
3995                                                             known_mode,
3996                                                             known_ret));
3997
3998       if (ARITHMETIC_P (x1)
3999           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
4000         return
4001           num_sign_bit_copies1 (x, mode, x0, mode,
4002                                 cached_num_sign_bit_copies (x0, mode, known_x,
4003                                                             known_mode,
4004                                                             known_ret));
4005     }
4006
4007   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
4008 }
4009
4010 /* Return the number of bits at the high-order end of X that are known to
4011    be equal to the sign bit.  X will be used in mode MODE; if MODE is
4012    VOIDmode, X will be used in its own mode.  The returned value  will always
4013    be between 1 and the number of bits in MODE.  */
4014
4015 static unsigned int
4016 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
4017                       enum machine_mode known_mode,
4018                       unsigned int known_ret)
4019 {
4020   enum rtx_code code = GET_CODE (x);
4021   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
4022   int num0, num1, result;
4023   unsigned HOST_WIDE_INT nonzero;
4024
4025   /* If we weren't given a mode, use the mode of X.  If the mode is still
4026      VOIDmode, we don't know anything.  Likewise if one of the modes is
4027      floating-point.  */
4028
4029   if (mode == VOIDmode)
4030     mode = GET_MODE (x);
4031
4032   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
4033     return 1;
4034
4035   /* For a smaller object, just ignore the high bits.  */
4036   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
4037     {
4038       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
4039                                          known_x, known_mode, known_ret);
4040       return MAX (1,
4041                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
4042     }
4043
4044   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
4045     {
4046 #ifndef WORD_REGISTER_OPERATIONS
4047   /* If this machine does not do all register operations on the entire
4048      register and MODE is wider than the mode of X, we can say nothing
4049      at all about the high-order bits.  */
4050       return 1;
4051 #else
4052       /* Likewise on machines that do, if the mode of the object is smaller
4053          than a word and loads of that size don't sign extend, we can say
4054          nothing about the high order bits.  */
4055       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4056 #ifdef LOAD_EXTEND_OP
4057           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4058 #endif
4059           )
4060         return 1;
4061 #endif
4062     }
4063
4064   switch (code)
4065     {
4066     case REG:
4067
4068 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4069       /* If pointers extend signed and this is a pointer in Pmode, say that
4070          all the bits above ptr_mode are known to be sign bit copies.  */
4071       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4072           && REG_POINTER (x))
4073         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4074 #endif
4075
4076       {
4077         unsigned int copies_for_hook = 1, copies = 1;
4078         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4079                                                      known_mode, known_ret,
4080                                                      &copies_for_hook);
4081
4082         if (new)
4083           copies = cached_num_sign_bit_copies (new, mode, known_x,
4084                                                known_mode, known_ret);
4085
4086         if (copies > 1 || copies_for_hook > 1)
4087           return MAX (copies, copies_for_hook);
4088
4089         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4090       }
4091       break;
4092
4093     case MEM:
4094 #ifdef LOAD_EXTEND_OP
4095       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4096       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4097         return MAX (1, ((int) bitwidth
4098                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4099 #endif
4100       break;
4101
4102     case CONST_INT:
4103       /* If the constant is negative, take its 1's complement and remask.
4104          Then see how many zero bits we have.  */
4105       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4106       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4107           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4108         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4109
4110       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4111
4112     case SUBREG:
4113       /* If this is a SUBREG for a promoted object that is sign-extended
4114          and we are looking at it in a wider mode, we know that at least the
4115          high-order bits are known to be sign bit copies.  */
4116
4117       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4118         {
4119           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4120                                              known_x, known_mode, known_ret);
4121           return MAX ((int) bitwidth
4122                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4123                       num0);
4124         }
4125
4126       /* For a smaller object, just ignore the high bits.  */
4127       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4128         {
4129           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4130                                              known_x, known_mode, known_ret);
4131           return MAX (1, (num0
4132                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4133                                    - bitwidth)));
4134         }
4135
4136 #ifdef WORD_REGISTER_OPERATIONS
4137 #ifdef LOAD_EXTEND_OP
4138       /* For paradoxical SUBREGs on machines where all register operations
4139          affect the entire register, just look inside.  Note that we are
4140          passing MODE to the recursive call, so the number of sign bit copies
4141          will remain relative to that mode, not the inner mode.  */
4142
4143       /* This works only if loads sign extend.  Otherwise, if we get a
4144          reload for the inner part, it may be loaded from the stack, and
4145          then we lose all sign bit copies that existed before the store
4146          to the stack.  */
4147
4148       if ((GET_MODE_SIZE (GET_MODE (x))
4149            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4150           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4151           && MEM_P (SUBREG_REG (x)))
4152         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4153                                            known_x, known_mode, known_ret);
4154 #endif
4155 #endif
4156       break;
4157
4158     case SIGN_EXTRACT:
4159       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4160         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4161       break;
4162
4163     case SIGN_EXTEND:
4164       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4165               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4166                                             known_x, known_mode, known_ret));
4167
4168     case TRUNCATE:
4169       /* For a smaller object, just ignore the high bits.  */
4170       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4171                                          known_x, known_mode, known_ret);
4172       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4173                                     - bitwidth)));
4174
4175     case NOT:
4176       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4177                                          known_x, known_mode, known_ret);
4178
4179     case ROTATE:       case ROTATERT:
4180       /* If we are rotating left by a number of bits less than the number
4181          of sign bit copies, we can just subtract that amount from the
4182          number.  */
4183       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4184           && INTVAL (XEXP (x, 1)) >= 0
4185           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4186         {
4187           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4188                                              known_x, known_mode, known_ret);
4189           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4190                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4191         }
4192       break;
4193
4194     case NEG:
4195       /* In general, this subtracts one sign bit copy.  But if the value
4196          is known to be positive, the number of sign bit copies is the
4197          same as that of the input.  Finally, if the input has just one bit
4198          that might be nonzero, all the bits are copies of the sign bit.  */
4199       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4200                                          known_x, known_mode, known_ret);
4201       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4202         return num0 > 1 ? num0 - 1 : 1;
4203
4204       nonzero = nonzero_bits (XEXP (x, 0), mode);
4205       if (nonzero == 1)
4206         return bitwidth;
4207
4208       if (num0 > 1
4209           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4210         num0--;
4211
4212       return num0;
4213
4214     case IOR:   case AND:   case XOR:
4215     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4216       /* Logical operations will preserve the number of sign-bit copies.
4217          MIN and MAX operations always return one of the operands.  */
4218       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4219                                          known_x, known_mode, known_ret);
4220       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4221                                          known_x, known_mode, known_ret);
4222       return MIN (num0, num1);
4223
4224     case PLUS:  case MINUS:
4225       /* For addition and subtraction, we can have a 1-bit carry.  However,
4226          if we are subtracting 1 from a positive number, there will not
4227          be such a carry.  Furthermore, if the positive number is known to
4228          be 0 or 1, we know the result is either -1 or 0.  */
4229
4230       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4231           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4232         {
4233           nonzero = nonzero_bits (XEXP (x, 0), mode);
4234           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4235             return (nonzero == 1 || nonzero == 0 ? bitwidth
4236                     : bitwidth - floor_log2 (nonzero) - 1);
4237         }
4238
4239       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4240                                          known_x, known_mode, known_ret);
4241       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4242                                          known_x, known_mode, known_ret);
4243       result = MAX (1, MIN (num0, num1) - 1);
4244
4245 #ifdef POINTERS_EXTEND_UNSIGNED
4246       /* If pointers extend signed and this is an addition or subtraction
4247          to a pointer in Pmode, all the bits above ptr_mode are known to be
4248          sign bit copies.  */
4249       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4250           && (code == PLUS || code == MINUS)
4251           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4252         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4253                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4254                       result);
4255 #endif
4256       return result;
4257
4258     case MULT:
4259       /* The number of bits of the product is the sum of the number of
4260          bits of both terms.  However, unless one of the terms if known
4261          to be positive, we must allow for an additional bit since negating
4262          a negative number can remove one sign bit copy.  */
4263
4264       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4265                                          known_x, known_mode, known_ret);
4266       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4267                                          known_x, known_mode, known_ret);
4268
4269       result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
4270       if (result > 0
4271           && (bitwidth > HOST_BITS_PER_WIDE_INT
4272               || (((nonzero_bits (XEXP (x, 0), mode)
4273                     & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4274                   && ((nonzero_bits (XEXP (x, 1), mode)
4275                        & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
4276         result--;
4277
4278       return MAX (1, result);
4279
4280     case UDIV:
4281       /* The result must be <= the first operand.  If the first operand
4282          has the high bit set, we know nothing about the number of sign
4283          bit copies.  */
4284       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4285         return 1;
4286       else if ((nonzero_bits (XEXP (x, 0), mode)
4287                 & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4288         return 1;
4289       else
4290         return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4291                                            known_x, known_mode, known_ret);
4292
4293     case UMOD:
4294       /* The result must be <= the second operand.  */
4295       return cached_num_sign_bit_copies (XEXP (x, 1), mode,
4296                                            known_x, known_mode, known_ret);
4297
4298     case DIV:
4299       /* Similar to unsigned division, except that we have to worry about
4300          the case where the divisor is negative, in which case we have
4301          to add 1.  */
4302       result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4303                                            known_x, known_mode, known_ret);
4304       if (result > 1
4305           && (bitwidth > HOST_BITS_PER_WIDE_INT
4306               || (nonzero_bits (XEXP (x, 1), mode)
4307                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4308         result--;
4309
4310       return result;
4311
4312     case MOD:
4313       result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4314                                            known_x, known_mode, known_ret);
4315       if (result > 1
4316           && (bitwidth > HOST_BITS_PER_WIDE_INT
4317               || (nonzero_bits (XEXP (x, 1), mode)
4318                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4319         result--;
4320
4321       return result;
4322
4323     case ASHIFTRT:
4324       /* Shifts by a constant add to the number of bits equal to the
4325          sign bit.  */
4326       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4327                                          known_x, known_mode, known_ret);
4328       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4329           && INTVAL (XEXP (x, 1)) > 0)
4330         num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
4331
4332       return num0;
4333
4334     case ASHIFT:
4335       /* Left shifts destroy copies.  */
4336       if (GET_CODE (XEXP (x, 1)) != CONST_INT
4337           || INTVAL (XEXP (x, 1)) < 0
4338           || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
4339         return 1;
4340
4341       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4342                                          known_x, known_mode, known_ret);
4343       return MAX (1, num0 - INTVAL (XEXP (x, 1)));
4344
4345     case IF_THEN_ELSE:
4346       num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4347                                          known_x, known_mode, known_ret);
4348       num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
4349                                          known_x, known_mode, known_ret);
4350       return MIN (num0, num1);
4351
4352     case EQ:  case NE:  case GE:  case GT:  case LE:  case LT:
4353     case UNEQ:  case LTGT:  case UNGE:  case UNGT:  case UNLE:  case UNLT:
4354     case GEU: case GTU: case LEU: case LTU:
4355     case UNORDERED: case ORDERED:
4356       /* If the constant is negative, take its 1's complement and remask.
4357          Then see how many zero bits we have.  */
4358       nonzero = STORE_FLAG_VALUE;
4359       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4360           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4361         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4362
4363       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4364
4365     default:
4366       break;
4367     }
4368
4369   /* If we haven't been able to figure it out by one of the above rules,
4370      see if some of the high-order bits are known to be zero.  If so,
4371      count those bits and return one less than that amount.  If we can't
4372      safely compute the mask for this mode, always return BITWIDTH.  */
4373
4374   bitwidth = GET_MODE_BITSIZE (mode);
4375   if (bitwidth > HOST_BITS_PER_WIDE_INT)
4376     return 1;
4377
4378   nonzero = nonzero_bits (x, mode);
4379   return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
4380          ? 1 : bitwidth - floor_log2 (nonzero) - 1;
4381 }
4382
4383 /* Calculate the rtx_cost of a single instruction.  A return value of
4384    zero indicates an instruction pattern without a known cost.  */
4385
4386 int
4387 insn_rtx_cost (rtx pat)
4388 {
4389   int i, cost;
4390   rtx set;
4391
4392   /* Extract the single set rtx from the instruction pattern.
4393      We can't use single_set since we only have the pattern.  */
4394   if (GET_CODE (pat) == SET)
4395     set = pat;
4396   else if (GET_CODE (pat) == PARALLEL)
4397     {
4398       set = NULL_RTX;
4399       for (i = 0; i < XVECLEN (pat, 0); i++)
4400         {
4401           rtx x = XVECEXP (pat, 0, i);
4402           if (GET_CODE (x) == SET)
4403             {
4404               if (set)
4405                 return 0;
4406               set = x;
4407             }
4408         }
4409       if (!set)
4410         return 0;
4411     }
4412   else
4413     return 0;
4414
4415   cost = rtx_cost (SET_SRC (set), SET);
4416   return cost > 0 ? cost : COSTS_N_INSNS (1);
4417 }
4418
4419 /* Given an insn INSN and condition COND, return the condition in a
4420    canonical form to simplify testing by callers.  Specifically:
4421
4422    (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
4423    (2) Both operands will be machine operands; (cc0) will have been replaced.
4424    (3) If an operand is a constant, it will be the second operand.
4425    (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
4426        for GE, GEU, and LEU.
4427
4428    If the condition cannot be understood, or is an inequality floating-point
4429    comparison which needs to be reversed, 0 will be returned.
4430
4431    If REVERSE is nonzero, then reverse the condition prior to canonizing it.
4432
4433    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4434    insn used in locating the condition was found.  If a replacement test
4435    of the condition is desired, it should be placed in front of that
4436    insn and we will be sure that the inputs are still valid.
4437
4438    If WANT_REG is nonzero, we wish the condition to be relative to that
4439    register, if possible.  Therefore, do not canonicalize the condition
4440    further.  If ALLOW_CC_MODE is nonzero, allow the condition returned
4441    to be a compare to a CC mode register.
4442
4443    If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST
4444    and at INSN.  */
4445
4446 rtx
4447 canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest,
4448                         rtx want_reg, int allow_cc_mode, int valid_at_insn_p)
4449 {
4450   enum rtx_code code;
4451   rtx prev = insn;
4452   rtx set;
4453   rtx tem;
4454   rtx op0, op1;
4455   int reverse_code = 0;
4456   enum machine_mode mode;
4457   basic_block bb = BLOCK_FOR_INSN (insn);
4458
4459   code = GET_CODE (cond);
4460   mode = GET_MODE (cond);
4461   op0 = XEXP (cond, 0);
4462   op1 = XEXP (cond, 1);
4463
4464   if (reverse)
4465     code = reversed_comparison_code (cond, insn);
4466   if (code == UNKNOWN)
4467     return 0;
4468
4469   if (earliest)
4470     *earliest = insn;
4471
4472   /* If we are comparing a register with zero, see if the register is set
4473      in the previous insn to a COMPARE or a comparison operation.  Perform
4474      the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
4475      in cse.c  */
4476
4477   while ((GET_RTX_CLASS (code) == RTX_COMPARE
4478           || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
4479          && op1 == CONST0_RTX (GET_MODE (op0))
4480          && op0 != want_reg)
4481     {
4482       /* Set nonzero when we find something of interest.  */
4483       rtx x = 0;
4484
4485 #ifdef HAVE_cc0
4486       /* If comparison with cc0, import actual comparison from compare
4487          insn.  */
4488       if (op0 == cc0_rtx)
4489         {
4490           if ((prev = prev_nonnote_insn (prev)) == 0
4491               || !NONJUMP_INSN_P (prev)
4492               || (set = single_set (prev)) == 0
4493               || SET_DEST (set) != cc0_rtx)
4494             return 0;
4495
4496           op0 = SET_SRC (set);
4497           op1 = CONST0_RTX (GET_MODE (op0));
4498           if (earliest)
4499             *earliest = prev;
4500         }
4501 #endif
4502
4503       /* If this is a COMPARE, pick up the two things being compared.  */
4504       if (GET_CODE (op0) == COMPARE)
4505         {
4506           op1 = XEXP (op0, 1);
4507           op0 = XEXP (op0, 0);
4508           continue;
4509         }
4510       else if (!REG_P (op0))
4511         break;
4512
4513       /* Go back to the previous insn.  Stop if it is not an INSN.  We also
4514          stop if it isn't a single set or if it has a REG_INC note because
4515          we don't want to bother dealing with it.  */
4516
4517       if ((prev = prev_nonnote_insn (prev)) == 0
4518           || !NONJUMP_INSN_P (prev)
4519           || FIND_REG_INC_NOTE (prev, NULL_RTX)
4520           /* In cfglayout mode, there do not have to be labels at the
4521              beginning of a block, or jumps at the end, so the previous
4522              conditions would not stop us when we reach bb boundary.  */
4523           || BLOCK_FOR_INSN (prev) != bb)
4524         break;
4525
4526       set = set_of (op0, prev);
4527
4528       if (set
4529           && (GET_CODE (set) != SET
4530               || !rtx_equal_p (SET_DEST (set), op0)))
4531         break;
4532
4533       /* If this is setting OP0, get what it sets it to if it looks
4534          relevant.  */
4535       if (set)
4536         {
4537           enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
4538 #ifdef FLOAT_STORE_FLAG_VALUE
4539           REAL_VALUE_TYPE fsfv;
4540 #endif
4541
4542           /* ??? We may not combine comparisons done in a CCmode with
4543              comparisons not done in a CCmode.  This is to aid targets
4544              like Alpha that have an IEEE compliant EQ instruction, and
4545              a non-IEEE compliant BEQ instruction.  The use of CCmode is
4546              actually artificial, simply to prevent the combination, but
4547              should not affect other platforms.
4548
4549              However, we must allow VOIDmode comparisons to match either
4550              CCmode or non-CCmode comparison, because some ports have
4551              modeless comparisons inside branch patterns.
4552
4553              ??? This mode check should perhaps look more like the mode check
4554              in simplify_comparison in combine.  */
4555
4556           if ((GET_CODE (SET_SRC (set)) == COMPARE
4557                || (((code == NE
4558                      || (code == LT
4559                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4560                          && (GET_MODE_BITSIZE (inner_mode)
4561                              <= HOST_BITS_PER_WIDE_INT)
4562                          && (STORE_FLAG_VALUE
4563                              & ((HOST_WIDE_INT) 1
4564                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4565 #ifdef FLOAT_STORE_FLAG_VALUE
4566                      || (code == LT
4567                          && SCALAR_FLOAT_MODE_P (inner_mode)
4568                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4569                              REAL_VALUE_NEGATIVE (fsfv)))
4570 #endif
4571                      ))
4572                    && COMPARISON_P (SET_SRC (set))))
4573               && (((GET_MODE_CLASS (mode) == MODE_CC)
4574                    == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4575                   || mode == VOIDmode || inner_mode == VOIDmode))
4576             x = SET_SRC (set);
4577           else if (((code == EQ
4578                      || (code == GE
4579                          && (GET_MODE_BITSIZE (inner_mode)
4580                              <= HOST_BITS_PER_WIDE_INT)
4581                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4582                          && (STORE_FLAG_VALUE
4583                              & ((HOST_WIDE_INT) 1
4584                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4585 #ifdef FLOAT_STORE_FLAG_VALUE
4586                      || (code == GE
4587                          && SCALAR_FLOAT_MODE_P (inner_mode)
4588                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4589                              REAL_VALUE_NEGATIVE (fsfv)))
4590 #endif
4591                      ))
4592                    && COMPARISON_P (SET_SRC (set))
4593                    && (((GET_MODE_CLASS (mode) == MODE_CC)
4594                         == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4595                        || mode == VOIDmode || inner_mode == VOIDmode))
4596
4597             {
4598               reverse_code = 1;
4599               x = SET_SRC (set);
4600             }
4601           else
4602             break;
4603         }
4604
4605       else if (reg_set_p (op0, prev))
4606         /* If this sets OP0, but not directly, we have to give up.  */
4607         break;
4608
4609       if (x)
4610         {
4611           /* If the caller is expecting the condition to be valid at INSN,
4612              make sure X doesn't change before INSN.  */
4613           if (valid_at_insn_p)
4614             if (modified_in_p (x, prev) || modified_between_p (x, prev, insn))
4615               break;
4616           if (COMPARISON_P (x))
4617             code = GET_CODE (x);
4618           if (reverse_code)
4619             {
4620               code = reversed_comparison_code (x, prev);
4621               if (code == UNKNOWN)
4622                 return 0;
4623               reverse_code = 0;
4624             }
4625
4626           op0 = XEXP (x, 0), op1 = XEXP (x, 1);
4627           if (earliest)
4628             *earliest = prev;
4629         }
4630     }
4631
4632   /* If constant is first, put it last.  */
4633   if (CONSTANT_P (op0))
4634     code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
4635
4636   /* If OP0 is the result of a comparison, we weren't able to find what
4637      was really being compared, so fail.  */
4638   if (!allow_cc_mode
4639       && GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
4640     return 0;
4641
4642   /* Canonicalize any ordered comparison with integers involving equality
4643      if we can do computations in the relevant mode and we do not
4644      overflow.  */
4645
4646   if (GET_MODE_CLASS (GET_MODE (op0)) != MODE_CC
4647       && GET_CODE (op1) == CONST_INT
4648       && GET_MODE (op0) != VOIDmode
4649       && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
4650     {
4651       HOST_WIDE_INT const_val = INTVAL (op1);
4652       unsigned HOST_WIDE_INT uconst_val = const_val;
4653       unsigned HOST_WIDE_INT max_val
4654         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
4655
4656       switch (code)
4657         {
4658         case LE:
4659           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
4660             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
4661           break;
4662
4663         /* When cross-compiling, const_val might be sign-extended from
4664            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
4665         case GE:
4666           if ((HOST_WIDE_INT) (const_val & max_val)
4667               != (((HOST_WIDE_INT) 1
4668                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
4669             code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0));
4670           break;
4671
4672         case LEU:
4673           if (uconst_val < max_val)
4674             code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
4675           break;
4676
4677         case GEU:
4678           if (uconst_val != 0)
4679             code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
4680           break;
4681
4682         default:
4683           break;
4684         }
4685     }
4686
4687   /* Never return CC0; return zero instead.  */
4688   if (CC0_P (op0))
4689     return 0;
4690
4691   return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
4692 }
4693
4694 /* Given a jump insn JUMP, return the condition that will cause it to branch
4695    to its JUMP_LABEL.  If the condition cannot be understood, or is an
4696    inequality floating-point comparison which needs to be reversed, 0 will
4697    be returned.
4698
4699    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4700    insn used in locating the condition was found.  If a replacement test
4701    of the condition is desired, it should be placed in front of that
4702    insn and we will be sure that the inputs are still valid.  If EARLIEST
4703    is null, the returned condition will be valid at INSN.
4704
4705    If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
4706    compare CC mode register.
4707
4708    VALID_AT_INSN_P is the same as for canonicalize_condition.  */
4709
4710 rtx
4711 get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p)
4712 {
4713   rtx cond;
4714   int reverse;
4715   rtx set;
4716
4717   /* If this is not a standard conditional jump, we can't parse it.  */
4718   if (!JUMP_P (jump)
4719       || ! any_condjump_p (jump))
4720     return 0;
4721   set = pc_set (jump);
4722
4723   cond = XEXP (SET_SRC (set), 0);
4724
4725   /* If this branches to JUMP_LABEL when the condition is false, reverse
4726      the condition.  */
4727   reverse
4728     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
4729       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
4730
4731   return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
4732                                  allow_cc_mode, valid_at_insn_p);
4733 }
4734
4735 /* Suppose that truncation from the machine mode of X to MODE is not a
4736    no-op.  See if there is anything special about X so that we can
4737    assume it already contains a truncated value of MODE.  */
4738
4739 bool
4740 truncated_to_mode (enum machine_mode mode, rtx x)
4741 {
4742   return REG_P (x) && rtl_hooks.reg_truncated_to_mode (mode, x);
4743 }
4744
4745 \f
4746 /* Initialize non_rtx_starting_operands, which is used to speed up
4747    for_each_rtx.  */
4748 void
4749 init_rtlanal (void)
4750 {
4751   int i;
4752   for (i = 0; i < NUM_RTX_CODE; i++)
4753     {
4754       const char *format = GET_RTX_FORMAT (i);
4755       const char *first = strpbrk (format, "eEV");
4756       non_rtx_starting_operands[i] = first ? first - format : -1;
4757     }
4758 }
4759 \f
4760 /* Check whether this is a constant pool constant.  */
4761 bool
4762 constant_pool_constant_p (rtx x)
4763 {
4764   x = avoid_constant_pool_reference (x);
4765   return GET_CODE (x) == CONST_DOUBLE;
4766 }
4767