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