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   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1680     if (REG_NOTE_KIND (link) == REG_EQUAL
1681         || REG_NOTE_KIND (link) == REG_EQUIV)
1682       {
1683         if (single_set (insn) == 0)
1684           return 0;
1685         return link;
1686       }
1687   return NULL;
1688 }
1689
1690 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1691    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1692
1693 int
1694 find_reg_fusage (rtx insn, enum rtx_code code, rtx datum)
1695 {
1696   /* If it's not a CALL_INSN, it can't possibly have a
1697      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1698   if (!CALL_P (insn))
1699     return 0;
1700
1701   gcc_assert (datum);
1702
1703   if (!REG_P (datum))
1704     {
1705       rtx link;
1706
1707       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1708            link;
1709            link = XEXP (link, 1))
1710         if (GET_CODE (XEXP (link, 0)) == code
1711             && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
1712           return 1;
1713     }
1714   else
1715     {
1716       unsigned int regno = REGNO (datum);
1717
1718       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1719          to pseudo registers, so don't bother checking.  */
1720
1721       if (regno < FIRST_PSEUDO_REGISTER)
1722         {
1723           unsigned int end_regno
1724             = regno + hard_regno_nregs[regno][GET_MODE (datum)];
1725           unsigned int i;
1726
1727           for (i = regno; i < end_regno; i++)
1728             if (find_regno_fusage (insn, code, i))
1729               return 1;
1730         }
1731     }
1732
1733   return 0;
1734 }
1735
1736 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1737    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1738
1739 int
1740 find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno)
1741 {
1742   rtx link;
1743
1744   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1745      to pseudo registers, so don't bother checking.  */
1746
1747   if (regno >= FIRST_PSEUDO_REGISTER
1748       || !CALL_P (insn) )
1749     return 0;
1750
1751   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1752     {
1753       unsigned int regnote;
1754       rtx op, reg;
1755
1756       if (GET_CODE (op = XEXP (link, 0)) == code
1757           && REG_P (reg = XEXP (op, 0))
1758           && (regnote = REGNO (reg)) <= regno
1759           && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno)
1760         return 1;
1761     }
1762
1763   return 0;
1764 }
1765
1766 /* Return true if INSN is a call to a pure function.  */
1767
1768 int
1769 pure_call_p (rtx insn)
1770 {
1771   rtx link;
1772
1773   if (!CALL_P (insn) || ! CONST_OR_PURE_CALL_P (insn))
1774     return 0;
1775
1776   /* Look for the note that differentiates const and pure functions.  */
1777   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1778     {
1779       rtx u, m;
1780
1781       if (GET_CODE (u = XEXP (link, 0)) == USE
1782           && MEM_P (m = XEXP (u, 0)) && GET_MODE (m) == BLKmode
1783           && GET_CODE (XEXP (m, 0)) == SCRATCH)
1784         return 1;
1785     }
1786
1787   return 0;
1788 }
1789 \f
1790 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1791
1792 void
1793 remove_note (rtx insn, rtx note)
1794 {
1795   rtx link;
1796
1797   if (note == NULL_RTX)
1798     return;
1799
1800   if (REG_NOTES (insn) == note)
1801     {
1802       REG_NOTES (insn) = XEXP (note, 1);
1803       return;
1804     }
1805
1806   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1807     if (XEXP (link, 1) == note)
1808       {
1809         XEXP (link, 1) = XEXP (note, 1);
1810         return;
1811       }
1812
1813   gcc_unreachable ();
1814 }
1815
1816 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1817    return 1 if it is found.  A simple equality test is used to determine if
1818    NODE matches.  */
1819
1820 int
1821 in_expr_list_p (rtx listp, rtx node)
1822 {
1823   rtx x;
1824
1825   for (x = listp; x; x = XEXP (x, 1))
1826     if (node == XEXP (x, 0))
1827       return 1;
1828
1829   return 0;
1830 }
1831
1832 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1833    remove that entry from the list if it is found.
1834
1835    A simple equality test is used to determine if NODE matches.  */
1836
1837 void
1838 remove_node_from_expr_list (rtx node, rtx *listp)
1839 {
1840   rtx temp = *listp;
1841   rtx prev = NULL_RTX;
1842
1843   while (temp)
1844     {
1845       if (node == XEXP (temp, 0))
1846         {
1847           /* Splice the node out of the list.  */
1848           if (prev)
1849             XEXP (prev, 1) = XEXP (temp, 1);
1850           else
1851             *listp = XEXP (temp, 1);
1852
1853           return;
1854         }
1855
1856       prev = temp;
1857       temp = XEXP (temp, 1);
1858     }
1859 }
1860 \f
1861 /* Nonzero if X contains any volatile instructions.  These are instructions
1862    which may cause unpredictable machine state instructions, and thus no
1863    instructions should be moved or combined across them.  This includes
1864    only volatile asms and UNSPEC_VOLATILE instructions.  */
1865
1866 int
1867 volatile_insn_p (rtx x)
1868 {
1869   RTX_CODE code;
1870
1871   code = GET_CODE (x);
1872   switch (code)
1873     {
1874     case LABEL_REF:
1875     case SYMBOL_REF:
1876     case CONST_INT:
1877     case CONST:
1878     case CONST_DOUBLE:
1879     case CONST_VECTOR:
1880     case CC0:
1881     case PC:
1882     case REG:
1883     case SCRATCH:
1884     case CLOBBER:
1885     case ADDR_VEC:
1886     case ADDR_DIFF_VEC:
1887     case CALL:
1888     case MEM:
1889       return 0;
1890
1891     case UNSPEC_VOLATILE:
1892  /* case TRAP_IF: This isn't clear yet.  */
1893       return 1;
1894
1895     case ASM_INPUT:
1896     case ASM_OPERANDS:
1897       if (MEM_VOLATILE_P (x))
1898         return 1;
1899
1900     default:
1901       break;
1902     }
1903
1904   /* Recursively scan the operands of this expression.  */
1905
1906   {
1907     const char *fmt = GET_RTX_FORMAT (code);
1908     int i;
1909
1910     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1911       {
1912         if (fmt[i] == 'e')
1913           {
1914             if (volatile_insn_p (XEXP (x, i)))
1915               return 1;
1916           }
1917         else if (fmt[i] == 'E')
1918           {
1919             int j;
1920             for (j = 0; j < XVECLEN (x, i); j++)
1921               if (volatile_insn_p (XVECEXP (x, i, j)))
1922                 return 1;
1923           }
1924       }
1925   }
1926   return 0;
1927 }
1928
1929 /* Nonzero if X contains any volatile memory references
1930    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1931
1932 int
1933 volatile_refs_p (rtx x)
1934 {
1935   RTX_CODE code;
1936
1937   code = GET_CODE (x);
1938   switch (code)
1939     {
1940     case LABEL_REF:
1941     case SYMBOL_REF:
1942     case CONST_INT:
1943     case CONST:
1944     case CONST_DOUBLE:
1945     case CONST_VECTOR:
1946     case CC0:
1947     case PC:
1948     case REG:
1949     case SCRATCH:
1950     case CLOBBER:
1951     case ADDR_VEC:
1952     case ADDR_DIFF_VEC:
1953       return 0;
1954
1955     case UNSPEC_VOLATILE:
1956       return 1;
1957
1958     case MEM:
1959     case ASM_INPUT:
1960     case ASM_OPERANDS:
1961       if (MEM_VOLATILE_P (x))
1962         return 1;
1963
1964     default:
1965       break;
1966     }
1967
1968   /* Recursively scan the operands of this expression.  */
1969
1970   {
1971     const char *fmt = GET_RTX_FORMAT (code);
1972     int i;
1973
1974     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1975       {
1976         if (fmt[i] == 'e')
1977           {
1978             if (volatile_refs_p (XEXP (x, i)))
1979               return 1;
1980           }
1981         else if (fmt[i] == 'E')
1982           {
1983             int j;
1984             for (j = 0; j < XVECLEN (x, i); j++)
1985               if (volatile_refs_p (XVECEXP (x, i, j)))
1986                 return 1;
1987           }
1988       }
1989   }
1990   return 0;
1991 }
1992
1993 /* Similar to above, except that it also rejects register pre- and post-
1994    incrementing.  */
1995
1996 int
1997 side_effects_p (rtx x)
1998 {
1999   RTX_CODE code;
2000
2001   code = GET_CODE (x);
2002   switch (code)
2003     {
2004     case LABEL_REF:
2005     case SYMBOL_REF:
2006     case CONST_INT:
2007     case CONST:
2008     case CONST_DOUBLE:
2009     case CONST_VECTOR:
2010     case CC0:
2011     case PC:
2012     case REG:
2013     case SCRATCH:
2014     case ADDR_VEC:
2015     case ADDR_DIFF_VEC:
2016       return 0;
2017
2018     case CLOBBER:
2019       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2020          when some combination can't be done.  If we see one, don't think
2021          that we can simplify the expression.  */
2022       return (GET_MODE (x) != VOIDmode);
2023
2024     case PRE_INC:
2025     case PRE_DEC:
2026     case POST_INC:
2027     case POST_DEC:
2028     case PRE_MODIFY:
2029     case POST_MODIFY:
2030     case CALL:
2031     case UNSPEC_VOLATILE:
2032  /* case TRAP_IF: This isn't clear yet.  */
2033       return 1;
2034
2035     case MEM:
2036     case ASM_INPUT:
2037     case ASM_OPERANDS:
2038       if (MEM_VOLATILE_P (x))
2039         return 1;
2040
2041     default:
2042       break;
2043     }
2044
2045   /* Recursively scan the operands of this expression.  */
2046
2047   {
2048     const char *fmt = GET_RTX_FORMAT (code);
2049     int i;
2050
2051     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2052       {
2053         if (fmt[i] == 'e')
2054           {
2055             if (side_effects_p (XEXP (x, i)))
2056               return 1;
2057           }
2058         else if (fmt[i] == 'E')
2059           {
2060             int j;
2061             for (j = 0; j < XVECLEN (x, i); j++)
2062               if (side_effects_p (XVECEXP (x, i, j)))
2063                 return 1;
2064           }
2065       }
2066   }
2067   return 0;
2068 }
2069 \f
2070 enum may_trap_p_flags
2071 {
2072   MTP_UNALIGNED_MEMS = 1,
2073   MTP_AFTER_MOVE = 2
2074 };
2075 /* Return nonzero if evaluating rtx X might cause a trap.
2076    (FLAGS & MTP_UNALIGNED_MEMS) controls whether nonzero is returned for
2077    unaligned memory accesses on strict alignment machines.  If
2078    (FLAGS & AFTER_MOVE) is true, returns nonzero even in case the expression
2079    cannot trap at its current location, but it might become trapping if moved
2080    elsewhere.  */
2081
2082 static int
2083 may_trap_p_1 (rtx x, unsigned flags)
2084 {
2085   int i;
2086   enum rtx_code code;
2087   const char *fmt;
2088   bool unaligned_mems = (flags & MTP_UNALIGNED_MEMS) != 0;
2089
2090   if (x == 0)
2091     return 0;
2092   code = GET_CODE (x);
2093   switch (code)
2094     {
2095       /* Handle these cases quickly.  */
2096     case CONST_INT:
2097     case CONST_DOUBLE:
2098     case CONST_VECTOR:
2099     case SYMBOL_REF:
2100     case LABEL_REF:
2101     case CONST:
2102     case PC:
2103     case CC0:
2104     case REG:
2105     case SCRATCH:
2106       return 0;
2107
2108     case ASM_INPUT:
2109     case UNSPEC_VOLATILE:
2110     case TRAP_IF:
2111       return 1;
2112
2113     case ASM_OPERANDS:
2114       return MEM_VOLATILE_P (x);
2115
2116       /* Memory ref can trap unless it's a static var or a stack slot.  */
2117     case MEM:
2118       if (/* MEM_NOTRAP_P only relates to the actual position of the memory
2119              reference; moving it out of condition might cause its address
2120              become invalid.  */
2121           !(flags & MTP_AFTER_MOVE)
2122           && MEM_NOTRAP_P (x)
2123           && (!STRICT_ALIGNMENT || !unaligned_mems))
2124         return 0;
2125       return
2126         rtx_addr_can_trap_p_1 (XEXP (x, 0), GET_MODE (x), unaligned_mems);
2127
2128       /* Division by a non-constant might trap.  */
2129     case DIV:
2130     case MOD:
2131     case UDIV:
2132     case UMOD:
2133       if (HONOR_SNANS (GET_MODE (x)))
2134         return 1;
2135       if (SCALAR_FLOAT_MODE_P (GET_MODE (x)))
2136         return flag_trapping_math;
2137       if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2138         return 1;
2139       break;
2140
2141     case EXPR_LIST:
2142       /* An EXPR_LIST is used to represent a function call.  This
2143          certainly may trap.  */
2144       return 1;
2145
2146     case GE:
2147     case GT:
2148     case LE:
2149     case LT:
2150     case LTGT:
2151     case COMPARE:
2152       /* Some floating point comparisons may trap.  */
2153       if (!flag_trapping_math)
2154         break;
2155       /* ??? There is no machine independent way to check for tests that trap
2156          when COMPARE is used, though many targets do make this distinction.
2157          For instance, sparc uses CCFPE for compares which generate exceptions
2158          and CCFP for compares which do not generate exceptions.  */
2159       if (HONOR_NANS (GET_MODE (x)))
2160         return 1;
2161       /* But often the compare has some CC mode, so check operand
2162          modes as well.  */
2163       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2164           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2165         return 1;
2166       break;
2167
2168     case EQ:
2169     case NE:
2170       if (HONOR_SNANS (GET_MODE (x)))
2171         return 1;
2172       /* Often comparison is CC mode, so check operand modes.  */
2173       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2174           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2175         return 1;
2176       break;
2177
2178     case FIX:
2179       /* Conversion of floating point might trap.  */
2180       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2181         return 1;
2182       break;
2183
2184     case NEG:
2185     case ABS:
2186     case SUBREG:
2187       /* These operations don't trap even with floating point.  */
2188       break;
2189
2190     default:
2191       /* Any floating arithmetic may trap.  */
2192       if (SCALAR_FLOAT_MODE_P (GET_MODE (x))
2193           && flag_trapping_math)
2194         return 1;
2195     }
2196
2197   fmt = GET_RTX_FORMAT (code);
2198   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2199     {
2200       if (fmt[i] == 'e')
2201         {
2202           if (may_trap_p_1 (XEXP (x, i), flags))
2203             return 1;
2204         }
2205       else if (fmt[i] == 'E')
2206         {
2207           int j;
2208           for (j = 0; j < XVECLEN (x, i); j++)
2209             if (may_trap_p_1 (XVECEXP (x, i, j), flags))
2210               return 1;
2211         }
2212     }
2213   return 0;
2214 }
2215
2216 /* Return nonzero if evaluating rtx X might cause a trap.  */
2217
2218 int
2219 may_trap_p (rtx x)
2220 {
2221   return may_trap_p_1 (x, 0);
2222 }
2223
2224 /* Return nonzero if evaluating rtx X might cause a trap, when the expression
2225    is moved from its current location by some optimization.  */
2226
2227 int
2228 may_trap_after_code_motion_p (rtx x)
2229 {
2230   return may_trap_p_1 (x, MTP_AFTER_MOVE);
2231 }
2232
2233 /* Same as above, but additionally return nonzero if evaluating rtx X might
2234    cause a fault.  We define a fault for the purpose of this function as a
2235    erroneous execution condition that cannot be encountered during the normal
2236    execution of a valid program; the typical example is an unaligned memory
2237    access on a strict alignment machine.  The compiler guarantees that it
2238    doesn't generate code that will fault from a valid program, but this
2239    guarantee doesn't mean anything for individual instructions.  Consider
2240    the following example:
2241
2242       struct S { int d; union { char *cp; int *ip; }; };
2243
2244       int foo(struct S *s)
2245       {
2246         if (s->d == 1)
2247           return *s->ip;
2248         else
2249           return *s->cp;
2250       }
2251
2252    on a strict alignment machine.  In a valid program, foo will never be
2253    invoked on a structure for which d is equal to 1 and the underlying
2254    unique field of the union not aligned on a 4-byte boundary, but the
2255    expression *s->ip might cause a fault if considered individually.
2256
2257    At the RTL level, potentially problematic expressions will almost always
2258    verify may_trap_p; for example, the above dereference can be emitted as
2259    (mem:SI (reg:P)) and this expression is may_trap_p for a generic register.
2260    However, suppose that foo is inlined in a caller that causes s->cp to
2261    point to a local character variable and guarantees that s->d is not set
2262    to 1; foo may have been effectively translated into pseudo-RTL as:
2263
2264       if ((reg:SI) == 1)
2265         (set (reg:SI) (mem:SI (%fp - 7)))
2266       else
2267         (set (reg:QI) (mem:QI (%fp - 7)))
2268
2269    Now (mem:SI (%fp - 7)) is considered as not may_trap_p since it is a
2270    memory reference to a stack slot, but it will certainly cause a fault
2271    on a strict alignment machine.  */
2272
2273 int
2274 may_trap_or_fault_p (rtx x)
2275 {
2276   return may_trap_p_1 (x, MTP_UNALIGNED_MEMS);
2277 }
2278 \f
2279 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2280    i.e., an inequality.  */
2281
2282 int
2283 inequality_comparisons_p (rtx x)
2284 {
2285   const char *fmt;
2286   int len, i;
2287   enum rtx_code code = GET_CODE (x);
2288
2289   switch (code)
2290     {
2291     case REG:
2292     case SCRATCH:
2293     case PC:
2294     case CC0:
2295     case CONST_INT:
2296     case CONST_DOUBLE:
2297     case CONST_VECTOR:
2298     case CONST:
2299     case LABEL_REF:
2300     case SYMBOL_REF:
2301       return 0;
2302
2303     case LT:
2304     case LTU:
2305     case GT:
2306     case GTU:
2307     case LE:
2308     case LEU:
2309     case GE:
2310     case GEU:
2311       return 1;
2312
2313     default:
2314       break;
2315     }
2316
2317   len = GET_RTX_LENGTH (code);
2318   fmt = GET_RTX_FORMAT (code);
2319
2320   for (i = 0; i < len; i++)
2321     {
2322       if (fmt[i] == 'e')
2323         {
2324           if (inequality_comparisons_p (XEXP (x, i)))
2325             return 1;
2326         }
2327       else if (fmt[i] == 'E')
2328         {
2329           int j;
2330           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2331             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2332               return 1;
2333         }
2334     }
2335
2336   return 0;
2337 }
2338 \f
2339 /* Replace any occurrence of FROM in X with TO.  The function does
2340    not enter into CONST_DOUBLE for the replace.
2341
2342    Note that copying is not done so X must not be shared unless all copies
2343    are to be modified.  */
2344
2345 rtx
2346 replace_rtx (rtx x, rtx from, rtx to)
2347 {
2348   int i, j;
2349   const char *fmt;
2350
2351   /* The following prevents loops occurrence when we change MEM in
2352      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2353   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2354     return x;
2355
2356   if (x == from)
2357     return to;
2358
2359   /* Allow this function to make replacements in EXPR_LISTs.  */
2360   if (x == 0)
2361     return 0;
2362
2363   if (GET_CODE (x) == SUBREG)
2364     {
2365       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2366
2367       if (GET_CODE (new) == CONST_INT)
2368         {
2369           x = simplify_subreg (GET_MODE (x), new,
2370                                GET_MODE (SUBREG_REG (x)),
2371                                SUBREG_BYTE (x));
2372           gcc_assert (x);
2373         }
2374       else
2375         SUBREG_REG (x) = new;
2376
2377       return x;
2378     }
2379   else if (GET_CODE (x) == ZERO_EXTEND)
2380     {
2381       rtx new = replace_rtx (XEXP (x, 0), from, to);
2382
2383       if (GET_CODE (new) == CONST_INT)
2384         {
2385           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2386                                         new, GET_MODE (XEXP (x, 0)));
2387           gcc_assert (x);
2388         }
2389       else
2390         XEXP (x, 0) = new;
2391
2392       return x;
2393     }
2394
2395   fmt = GET_RTX_FORMAT (GET_CODE (x));
2396   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2397     {
2398       if (fmt[i] == 'e')
2399         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2400       else if (fmt[i] == 'E')
2401         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2402           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2403     }
2404
2405   return x;
2406 }
2407 \f
2408 /* Replace occurrences of the old label in *X with the new one.
2409    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2410
2411 int
2412 replace_label (rtx *x, void *data)
2413 {
2414   rtx l = *x;
2415   rtx old_label = ((replace_label_data *) data)->r1;
2416   rtx new_label = ((replace_label_data *) data)->r2;
2417   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2418
2419   if (l == NULL_RTX)
2420     return 0;
2421
2422   if (GET_CODE (l) == SYMBOL_REF
2423       && CONSTANT_POOL_ADDRESS_P (l))
2424     {
2425       rtx c = get_pool_constant (l);
2426       if (rtx_referenced_p (old_label, c))
2427         {
2428           rtx new_c, new_l;
2429           replace_label_data *d = (replace_label_data *) data;
2430
2431           /* Create a copy of constant C; replace the label inside
2432              but do not update LABEL_NUSES because uses in constant pool
2433              are not counted.  */
2434           new_c = copy_rtx (c);
2435           d->update_label_nuses = false;
2436           for_each_rtx (&new_c, replace_label, data);
2437           d->update_label_nuses = update_label_nuses;
2438
2439           /* Add the new constant NEW_C to constant pool and replace
2440              the old reference to constant by new reference.  */
2441           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2442           *x = replace_rtx (l, l, new_l);
2443         }
2444       return 0;
2445     }
2446
2447   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2448      field.  This is not handled by for_each_rtx because it doesn't
2449      handle unprinted ('0') fields.  */
2450   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2451     JUMP_LABEL (l) = new_label;
2452
2453   if ((GET_CODE (l) == LABEL_REF
2454        || GET_CODE (l) == INSN_LIST)
2455       && XEXP (l, 0) == old_label)
2456     {
2457       XEXP (l, 0) = new_label;
2458       if (update_label_nuses)
2459         {
2460           ++LABEL_NUSES (new_label);
2461           --LABEL_NUSES (old_label);
2462         }
2463       return 0;
2464     }
2465
2466   return 0;
2467 }
2468
2469 /* When *BODY is equal to X or X is directly referenced by *BODY
2470    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2471    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2472
2473 static int
2474 rtx_referenced_p_1 (rtx *body, void *x)
2475 {
2476   rtx y = (rtx) x;
2477
2478   if (*body == NULL_RTX)
2479     return y == NULL_RTX;
2480
2481   /* Return true if a label_ref *BODY refers to label Y.  */
2482   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2483     return XEXP (*body, 0) == y;
2484
2485   /* If *BODY is a reference to pool constant traverse the constant.  */
2486   if (GET_CODE (*body) == SYMBOL_REF
2487       && CONSTANT_POOL_ADDRESS_P (*body))
2488     return rtx_referenced_p (y, get_pool_constant (*body));
2489
2490   /* By default, compare the RTL expressions.  */
2491   return rtx_equal_p (*body, y);
2492 }
2493
2494 /* Return true if X is referenced in BODY.  */
2495
2496 int
2497 rtx_referenced_p (rtx x, rtx body)
2498 {
2499   return for_each_rtx (&body, rtx_referenced_p_1, x);
2500 }
2501
2502 /* If INSN is a tablejump return true and store the label (before jump table) to
2503    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2504
2505 bool
2506 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2507 {
2508   rtx label, table;
2509
2510   if (JUMP_P (insn)
2511       && (label = JUMP_LABEL (insn)) != NULL_RTX
2512       && (table = next_active_insn (label)) != NULL_RTX
2513       && JUMP_P (table)
2514       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2515           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2516     {
2517       if (labelp)
2518         *labelp = label;
2519       if (tablep)
2520         *tablep = table;
2521       return true;
2522     }
2523   return false;
2524 }
2525
2526 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2527    constant that is not in the constant pool and not in the condition
2528    of an IF_THEN_ELSE.  */
2529
2530 static int
2531 computed_jump_p_1 (rtx x)
2532 {
2533   enum rtx_code code = GET_CODE (x);
2534   int i, j;
2535   const char *fmt;
2536
2537   switch (code)
2538     {
2539     case LABEL_REF:
2540     case PC:
2541       return 0;
2542
2543     case CONST:
2544     case CONST_INT:
2545     case CONST_DOUBLE:
2546     case CONST_VECTOR:
2547     case SYMBOL_REF:
2548     case REG:
2549       return 1;
2550
2551     case MEM:
2552       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2553                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2554
2555     case IF_THEN_ELSE:
2556       return (computed_jump_p_1 (XEXP (x, 1))
2557               || computed_jump_p_1 (XEXP (x, 2)));
2558
2559     default:
2560       break;
2561     }
2562
2563   fmt = GET_RTX_FORMAT (code);
2564   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2565     {
2566       if (fmt[i] == 'e'
2567           && computed_jump_p_1 (XEXP (x, i)))
2568         return 1;
2569
2570       else if (fmt[i] == 'E')
2571         for (j = 0; j < XVECLEN (x, i); j++)
2572           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2573             return 1;
2574     }
2575
2576   return 0;
2577 }
2578
2579 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2580
2581    Tablejumps and casesi insns are not considered indirect jumps;
2582    we can recognize them by a (use (label_ref)).  */
2583
2584 int
2585 computed_jump_p (rtx insn)
2586 {
2587   int i;
2588   if (JUMP_P (insn))
2589     {
2590       rtx pat = PATTERN (insn);
2591
2592       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2593         return 0;
2594       else if (GET_CODE (pat) == PARALLEL)
2595         {
2596           int len = XVECLEN (pat, 0);
2597           int has_use_labelref = 0;
2598
2599           for (i = len - 1; i >= 0; i--)
2600             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2601                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2602                     == LABEL_REF))
2603               has_use_labelref = 1;
2604
2605           if (! has_use_labelref)
2606             for (i = len - 1; i >= 0; i--)
2607               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2608                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2609                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2610                 return 1;
2611         }
2612       else if (GET_CODE (pat) == SET
2613                && SET_DEST (pat) == pc_rtx
2614                && computed_jump_p_1 (SET_SRC (pat)))
2615         return 1;
2616     }
2617   return 0;
2618 }
2619
2620 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2621    calls.  Processes the subexpressions of EXP and passes them to F.  */
2622 static int
2623 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2624 {
2625   int result, i, j;
2626   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2627   rtx *x;
2628
2629   for (; format[n] != '\0'; n++)
2630     {
2631       switch (format[n])
2632         {
2633         case 'e':
2634           /* Call F on X.  */
2635           x = &XEXP (exp, n);
2636           result = (*f) (x, data);
2637           if (result == -1)
2638             /* Do not traverse sub-expressions.  */
2639             continue;
2640           else if (result != 0)
2641             /* Stop the traversal.  */
2642             return result;
2643
2644           if (*x == NULL_RTX)
2645             /* There are no sub-expressions.  */
2646             continue;
2647
2648           i = non_rtx_starting_operands[GET_CODE (*x)];
2649           if (i >= 0)
2650             {
2651               result = for_each_rtx_1 (*x, i, f, data);
2652               if (result != 0)
2653                 return result;
2654             }
2655           break;
2656
2657         case 'V':
2658         case 'E':
2659           if (XVEC (exp, n) == 0)
2660             continue;
2661           for (j = 0; j < XVECLEN (exp, n); ++j)
2662             {
2663               /* Call F on X.  */
2664               x = &XVECEXP (exp, n, j);
2665               result = (*f) (x, data);
2666               if (result == -1)
2667                 /* Do not traverse sub-expressions.  */
2668                 continue;
2669               else if (result != 0)
2670                 /* Stop the traversal.  */
2671                 return result;
2672
2673               if (*x == NULL_RTX)
2674                 /* There are no sub-expressions.  */
2675                 continue;
2676
2677               i = non_rtx_starting_operands[GET_CODE (*x)];
2678               if (i >= 0)
2679                 {
2680                   result = for_each_rtx_1 (*x, i, f, data);
2681                   if (result != 0)
2682                     return result;
2683                 }
2684             }
2685           break;
2686
2687         default:
2688           /* Nothing to do.  */
2689           break;
2690         }
2691     }
2692
2693   return 0;
2694 }
2695
2696 /* Traverse X via depth-first search, calling F for each
2697    sub-expression (including X itself).  F is also passed the DATA.
2698    If F returns -1, do not traverse sub-expressions, but continue
2699    traversing the rest of the tree.  If F ever returns any other
2700    nonzero value, stop the traversal, and return the value returned
2701    by F.  Otherwise, return 0.  This function does not traverse inside
2702    tree structure that contains RTX_EXPRs, or into sub-expressions
2703    whose format code is `0' since it is not known whether or not those
2704    codes are actually RTL.
2705
2706    This routine is very general, and could (should?) be used to
2707    implement many of the other routines in this file.  */
2708
2709 int
2710 for_each_rtx (rtx *x, rtx_function f, void *data)
2711 {
2712   int result;
2713   int i;
2714
2715   /* Call F on X.  */
2716   result = (*f) (x, data);
2717   if (result == -1)
2718     /* Do not traverse sub-expressions.  */
2719     return 0;
2720   else if (result != 0)
2721     /* Stop the traversal.  */
2722     return result;
2723
2724   if (*x == NULL_RTX)
2725     /* There are no sub-expressions.  */
2726     return 0;
2727
2728   i = non_rtx_starting_operands[GET_CODE (*x)];
2729   if (i < 0)
2730     return 0;
2731
2732   return for_each_rtx_1 (*x, i, f, data);
2733 }
2734
2735
2736 /* Searches X for any reference to REGNO, returning the rtx of the
2737    reference found if any.  Otherwise, returns NULL_RTX.  */
2738
2739 rtx
2740 regno_use_in (unsigned int regno, rtx x)
2741 {
2742   const char *fmt;
2743   int i, j;
2744   rtx tem;
2745
2746   if (REG_P (x) && REGNO (x) == regno)
2747     return x;
2748
2749   fmt = GET_RTX_FORMAT (GET_CODE (x));
2750   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2751     {
2752       if (fmt[i] == 'e')
2753         {
2754           if ((tem = regno_use_in (regno, XEXP (x, i))))
2755             return tem;
2756         }
2757       else if (fmt[i] == 'E')
2758         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2759           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2760             return tem;
2761     }
2762
2763   return NULL_RTX;
2764 }
2765
2766 /* Return a value indicating whether OP, an operand of a commutative
2767    operation, is preferred as the first or second operand.  The higher
2768    the value, the stronger the preference for being the first operand.
2769    We use negative values to indicate a preference for the first operand
2770    and positive values for the second operand.  */
2771
2772 int
2773 commutative_operand_precedence (rtx op)
2774 {
2775   enum rtx_code code = GET_CODE (op);
2776
2777   /* Constants always come the second operand.  Prefer "nice" constants.  */
2778   if (code == CONST_INT)
2779     return -7;
2780   if (code == CONST_DOUBLE)
2781     return -6;
2782   op = avoid_constant_pool_reference (op);
2783   code = GET_CODE (op);
2784
2785   switch (GET_RTX_CLASS (code))
2786     {
2787     case RTX_CONST_OBJ:
2788       if (code == CONST_INT)
2789         return -5;
2790       if (code == CONST_DOUBLE)
2791         return -4;
2792       return -3;
2793
2794     case RTX_EXTRA:
2795       /* SUBREGs of objects should come second.  */
2796       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2797         return -2;
2798
2799       if (!CONSTANT_P (op))
2800         return 0;
2801       else
2802         /* As for RTX_CONST_OBJ.  */
2803         return -3;
2804
2805     case RTX_OBJ:
2806       /* Complex expressions should be the first, so decrease priority
2807          of objects.  */
2808       return -1;
2809
2810     case RTX_COMM_ARITH:
2811       /* Prefer operands that are themselves commutative to be first.
2812          This helps to make things linear.  In particular,
2813          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2814       return 4;
2815
2816     case RTX_BIN_ARITH:
2817       /* If only one operand is a binary expression, it will be the first
2818          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2819          is canonical, although it will usually be further simplified.  */
2820       return 2;
2821
2822     case RTX_UNARY:
2823       /* Then prefer NEG and NOT.  */
2824       if (code == NEG || code == NOT)
2825         return 1;
2826
2827     default:
2828       return 0;
2829     }
2830 }
2831
2832 /* Return 1 iff it is necessary to swap operands of commutative operation
2833    in order to canonicalize expression.  */
2834
2835 int
2836 swap_commutative_operands_p (rtx x, rtx y)
2837 {
2838   return (commutative_operand_precedence (x)
2839           < commutative_operand_precedence (y));
2840 }
2841
2842 /* Return 1 if X is an autoincrement side effect and the register is
2843    not the stack pointer.  */
2844 int
2845 auto_inc_p (rtx x)
2846 {
2847   switch (GET_CODE (x))
2848     {
2849     case PRE_INC:
2850     case POST_INC:
2851     case PRE_DEC:
2852     case POST_DEC:
2853     case PRE_MODIFY:
2854     case POST_MODIFY:
2855       /* There are no REG_INC notes for SP.  */
2856       if (XEXP (x, 0) != stack_pointer_rtx)
2857         return 1;
2858     default:
2859       break;
2860     }
2861   return 0;
2862 }
2863
2864 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2865 int
2866 loc_mentioned_in_p (rtx *loc, rtx in)
2867 {
2868   enum rtx_code code;
2869   const char *fmt;
2870   int i, j;
2871
2872   if (!in)
2873     return 0;
2874
2875   code = GET_CODE (in);
2876   fmt = GET_RTX_FORMAT (code);
2877   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2878     {
2879       if (loc == &in->u.fld[i].rt_rtx)
2880         return 1;
2881       if (fmt[i] == 'e')
2882         {
2883           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2884             return 1;
2885         }
2886       else if (fmt[i] == 'E')
2887         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2888           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2889             return 1;
2890     }
2891   return 0;
2892 }
2893
2894 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
2895    and SUBREG_BYTE, return the bit offset where the subreg begins
2896    (counting from the least significant bit of the operand).  */
2897
2898 unsigned int
2899 subreg_lsb_1 (enum machine_mode outer_mode,
2900               enum machine_mode inner_mode,
2901               unsigned int subreg_byte)
2902 {
2903   unsigned int bitpos;
2904   unsigned int byte;
2905   unsigned int word;
2906
2907   /* A paradoxical subreg begins at bit position 0.  */
2908   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
2909     return 0;
2910
2911   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2912     /* If the subreg crosses a word boundary ensure that
2913        it also begins and ends on a word boundary.  */
2914     gcc_assert (!((subreg_byte % UNITS_PER_WORD
2915                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
2916                   && (subreg_byte % UNITS_PER_WORD
2917                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
2918
2919   if (WORDS_BIG_ENDIAN)
2920     word = (GET_MODE_SIZE (inner_mode)
2921             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
2922   else
2923     word = subreg_byte / UNITS_PER_WORD;
2924   bitpos = word * BITS_PER_WORD;
2925
2926   if (BYTES_BIG_ENDIAN)
2927     byte = (GET_MODE_SIZE (inner_mode)
2928             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
2929   else
2930     byte = subreg_byte % UNITS_PER_WORD;
2931   bitpos += byte * BITS_PER_UNIT;
2932
2933   return bitpos;
2934 }
2935
2936 /* Given a subreg X, return the bit offset where the subreg begins
2937    (counting from the least significant bit of the reg).  */
2938
2939 unsigned int
2940 subreg_lsb (rtx x)
2941 {
2942   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
2943                        SUBREG_BYTE (x));
2944 }
2945
2946 /* Fill in information about a subreg of a hard register.
2947    xregno - A regno of an inner hard subreg_reg (or what will become one).
2948    xmode  - The mode of xregno.
2949    offset - The byte offset.
2950    ymode  - The mode of a top level SUBREG (or what may become one).
2951    info   - Pointer to structure to fill in.  */
2952 static void
2953 subreg_get_info (unsigned int xregno, enum machine_mode xmode,
2954                  unsigned int offset, enum machine_mode ymode,
2955                  struct subreg_info *info)
2956 {
2957   int nregs_xmode, nregs_ymode;
2958   int mode_multiple, nregs_multiple;
2959   int offset_adj, y_offset, y_offset_adj;
2960   int regsize_xmode, regsize_ymode;
2961   bool rknown;
2962
2963   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
2964
2965   rknown = false;
2966
2967   /* If there are holes in a non-scalar mode in registers, we expect
2968      that it is made up of its units concatenated together.  */
2969   if (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode))
2970     {
2971       enum machine_mode xmode_unit;
2972
2973       nregs_xmode = HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode);
2974       if (GET_MODE_INNER (xmode) == VOIDmode)
2975         xmode_unit = xmode;
2976       else
2977         xmode_unit = GET_MODE_INNER (xmode);
2978       gcc_assert (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode_unit));
2979       gcc_assert (nregs_xmode
2980                   == (GET_MODE_NUNITS (xmode)
2981                       * HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode_unit)));
2982       gcc_assert (hard_regno_nregs[xregno][xmode]
2983                   == (hard_regno_nregs[xregno][xmode_unit]
2984                       * GET_MODE_NUNITS (xmode)));
2985
2986       /* You can only ask for a SUBREG of a value with holes in the middle
2987          if you don't cross the holes.  (Such a SUBREG should be done by
2988          picking a different register class, or doing it in memory if
2989          necessary.)  An example of a value with holes is XCmode on 32-bit
2990          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
2991          3 for each part, but in memory it's two 128-bit parts.
2992          Padding is assumed to be at the end (not necessarily the 'high part')
2993          of each unit.  */
2994       if ((offset / GET_MODE_SIZE (xmode_unit) + 1
2995            < GET_MODE_NUNITS (xmode))
2996           && (offset / GET_MODE_SIZE (xmode_unit)
2997               != ((offset + GET_MODE_SIZE (ymode) - 1)
2998                   / GET_MODE_SIZE (xmode_unit))))
2999         {
3000           info->representable_p = false;
3001           rknown = true;
3002         }
3003     }
3004   else
3005     nregs_xmode = hard_regno_nregs[xregno][xmode];
3006
3007   nregs_ymode = hard_regno_nregs[xregno][ymode];
3008
3009   /* Paradoxical subregs are otherwise valid.  */
3010   if (!rknown
3011       && offset == 0
3012       && GET_MODE_SIZE (ymode) > GET_MODE_SIZE (xmode))
3013     {
3014       info->representable_p = true;
3015       /* If this is a big endian paradoxical subreg, which uses more
3016          actual hard registers than the original register, we must
3017          return a negative offset so that we find the proper highpart
3018          of the register.  */
3019       if (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3020           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)
3021         info->offset = nregs_xmode - nregs_ymode;
3022       else
3023         info->offset = 0;
3024       info->nregs = nregs_ymode;
3025       return;
3026     }
3027
3028   /* If registers store different numbers of bits in the different
3029      modes, we cannot generally form this subreg.  */
3030   if (!HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode)
3031       && !HARD_REGNO_NREGS_HAS_PADDING (xregno, ymode)
3032       && (GET_MODE_SIZE (xmode) % nregs_xmode) == 0
3033       && (GET_MODE_SIZE (ymode) % nregs_ymode) == 0)
3034     {
3035       regsize_xmode = GET_MODE_SIZE (xmode) / nregs_xmode;
3036       regsize_ymode = GET_MODE_SIZE (ymode) / nregs_ymode;
3037       if (!rknown && regsize_xmode > regsize_ymode && nregs_ymode > 1)
3038         {
3039           info->representable_p = false;
3040           info->nregs
3041             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3042           info->offset = offset / regsize_xmode;
3043           return;
3044         }
3045       if (!rknown && regsize_ymode > regsize_xmode && nregs_xmode > 1)
3046         {
3047           info->representable_p = false;
3048           info->nregs
3049             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3050           info->offset = offset / regsize_xmode;
3051           return;
3052         }
3053     }
3054
3055   /* Lowpart subregs are otherwise valid.  */
3056   if (!rknown && offset == subreg_lowpart_offset (ymode, xmode))
3057     {
3058       info->representable_p = true;
3059       rknown = true;
3060
3061       if (offset == 0 || nregs_xmode == nregs_ymode)
3062         {
3063           info->offset = 0;
3064           info->nregs = nregs_ymode;
3065           return;
3066         }
3067     }
3068
3069   /* This should always pass, otherwise we don't know how to verify
3070      the constraint.  These conditions may be relaxed but
3071      subreg_regno_offset would need to be redesigned.  */
3072   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3073   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3074
3075   /* The XMODE value can be seen as a vector of NREGS_XMODE
3076      values.  The subreg must represent a lowpart of given field.
3077      Compute what field it is.  */
3078   offset_adj = offset;
3079   offset_adj -= subreg_lowpart_offset (ymode,
3080                                        mode_for_size (GET_MODE_BITSIZE (xmode)
3081                                                       / nregs_xmode,
3082                                                       MODE_INT, 0));
3083
3084   /* Size of ymode must not be greater than the size of xmode.  */
3085   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3086   gcc_assert (mode_multiple != 0);
3087
3088   y_offset = offset / GET_MODE_SIZE (ymode);
3089   y_offset_adj = offset_adj / GET_MODE_SIZE (ymode);
3090   nregs_multiple = nregs_xmode / nregs_ymode;
3091
3092   gcc_assert ((offset_adj % GET_MODE_SIZE (ymode)) == 0);
3093   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3094
3095   if (!rknown)
3096     {
3097       info->representable_p = (!(y_offset_adj % (mode_multiple / nregs_multiple)));
3098       rknown = true;
3099     }
3100   info->offset = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3101   info->nregs = nregs_ymode;
3102 }
3103
3104 /* This function returns the regno offset of a subreg expression.
3105    xregno - A regno of an inner hard subreg_reg (or what will become one).
3106    xmode  - The mode of xregno.
3107    offset - The byte offset.
3108    ymode  - The mode of a top level SUBREG (or what may become one).
3109    RETURN - The regno offset which would be used.  */
3110 unsigned int
3111 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3112                      unsigned int offset, enum machine_mode ymode)
3113 {
3114   struct subreg_info info;
3115   subreg_get_info (xregno, xmode, offset, ymode, &info);
3116   return info.offset;
3117 }
3118
3119 /* This function returns true when the offset is representable via
3120    subreg_offset in the given regno.
3121    xregno - A regno of an inner hard subreg_reg (or what will become one).
3122    xmode  - The mode of xregno.
3123    offset - The byte offset.
3124    ymode  - The mode of a top level SUBREG (or what may become one).
3125    RETURN - Whether the offset is representable.  */
3126 bool
3127 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3128                                unsigned int offset, enum machine_mode ymode)
3129 {
3130   struct subreg_info info;
3131   subreg_get_info (xregno, xmode, offset, ymode, &info);
3132   return info.representable_p;
3133 }
3134
3135 /* Return the final regno that a subreg expression refers to.  */
3136 unsigned int
3137 subreg_regno (rtx x)
3138 {
3139   unsigned int ret;
3140   rtx subreg = SUBREG_REG (x);
3141   int regno = REGNO (subreg);
3142
3143   ret = regno + subreg_regno_offset (regno,
3144                                      GET_MODE (subreg),
3145                                      SUBREG_BYTE (x),
3146                                      GET_MODE (x));
3147   return ret;
3148
3149 }
3150
3151 /* Return the number of registers that a subreg expression refers
3152    to.  */
3153 unsigned int
3154 subreg_nregs (rtx x)
3155 {
3156   struct subreg_info info;
3157   rtx subreg = SUBREG_REG (x);
3158   int regno = REGNO (subreg);
3159
3160   subreg_get_info (regno, GET_MODE (subreg), SUBREG_BYTE (x), GET_MODE (x),
3161                    &info);
3162   return info.nregs;
3163 }
3164
3165 struct parms_set_data
3166 {
3167   int nregs;
3168   HARD_REG_SET regs;
3169 };
3170
3171 /* Helper function for noticing stores to parameter registers.  */
3172 static void
3173 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3174 {
3175   struct parms_set_data *d = data;
3176   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3177       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3178     {
3179       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3180       d->nregs--;
3181     }
3182 }
3183
3184 /* Look backward for first parameter to be loaded.
3185    Note that loads of all parameters will not necessarily be
3186    found if CSE has eliminated some of them (e.g., an argument
3187    to the outer function is passed down as a parameter).
3188    Do not skip BOUNDARY.  */
3189 rtx
3190 find_first_parameter_load (rtx call_insn, rtx boundary)
3191 {
3192   struct parms_set_data parm;
3193   rtx p, before, first_set;
3194
3195   /* Since different machines initialize their parameter registers
3196      in different orders, assume nothing.  Collect the set of all
3197      parameter registers.  */
3198   CLEAR_HARD_REG_SET (parm.regs);
3199   parm.nregs = 0;
3200   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3201     if (GET_CODE (XEXP (p, 0)) == USE
3202         && REG_P (XEXP (XEXP (p, 0), 0)))
3203       {
3204         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3205
3206         /* We only care about registers which can hold function
3207            arguments.  */
3208         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3209           continue;
3210
3211         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3212         parm.nregs++;
3213       }
3214   before = call_insn;
3215   first_set = call_insn;
3216
3217   /* Search backward for the first set of a register in this set.  */
3218   while (parm.nregs && before != boundary)
3219     {
3220       before = PREV_INSN (before);
3221
3222       /* It is possible that some loads got CSEed from one call to
3223          another.  Stop in that case.  */
3224       if (CALL_P (before))
3225         break;
3226
3227       /* Our caller needs either ensure that we will find all sets
3228          (in case code has not been optimized yet), or take care
3229          for possible labels in a way by setting boundary to preceding
3230          CODE_LABEL.  */
3231       if (LABEL_P (before))
3232         {
3233           gcc_assert (before == boundary);
3234           break;
3235         }
3236
3237       if (INSN_P (before))
3238         {
3239           int nregs_old = parm.nregs;
3240           note_stores (PATTERN (before), parms_set, &parm);
3241           /* If we found something that did not set a parameter reg,
3242              we're done.  Do not keep going, as that might result
3243              in hoisting an insn before the setting of a pseudo
3244              that is used by the hoisted insn. */
3245           if (nregs_old != parm.nregs)
3246             first_set = before;
3247           else
3248             break;
3249         }
3250     }
3251   return first_set;
3252 }
3253
3254 /* Return true if we should avoid inserting code between INSN and preceding
3255    call instruction.  */
3256
3257 bool
3258 keep_with_call_p (rtx insn)
3259 {
3260   rtx set;
3261
3262   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3263     {
3264       if (REG_P (SET_DEST (set))
3265           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3266           && fixed_regs[REGNO (SET_DEST (set))]
3267           && general_operand (SET_SRC (set), VOIDmode))
3268         return true;
3269       if (REG_P (SET_SRC (set))
3270           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3271           && REG_P (SET_DEST (set))
3272           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3273         return true;
3274       /* There may be a stack pop just after the call and before the store
3275          of the return register.  Search for the actual store when deciding
3276          if we can break or not.  */
3277       if (SET_DEST (set) == stack_pointer_rtx)
3278         {
3279           rtx i2 = next_nonnote_insn (insn);
3280           if (i2 && keep_with_call_p (i2))
3281             return true;
3282         }
3283     }
3284   return false;
3285 }
3286
3287 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3288    to non-complex jumps.  That is, direct unconditional, conditional,
3289    and tablejumps, but not computed jumps or returns.  It also does
3290    not apply to the fallthru case of a conditional jump.  */
3291
3292 bool
3293 label_is_jump_target_p (rtx label, rtx jump_insn)
3294 {
3295   rtx tmp = JUMP_LABEL (jump_insn);
3296
3297   if (label == tmp)
3298     return true;
3299
3300   if (tablejump_p (jump_insn, NULL, &tmp))
3301     {
3302       rtvec vec = XVEC (PATTERN (tmp),
3303                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3304       int i, veclen = GET_NUM_ELEM (vec);
3305
3306       for (i = 0; i < veclen; ++i)
3307         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3308           return true;
3309     }
3310
3311   return false;
3312 }
3313
3314 \f
3315 /* Return an estimate of the cost of computing rtx X.
3316    One use is in cse, to decide which expression to keep in the hash table.
3317    Another is in rtl generation, to pick the cheapest way to multiply.
3318    Other uses like the latter are expected in the future.  */
3319
3320 int
3321 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3322 {
3323   int i, j;
3324   enum rtx_code code;
3325   const char *fmt;
3326   int total;
3327
3328   if (x == 0)
3329     return 0;
3330
3331   /* Compute the default costs of certain things.
3332      Note that targetm.rtx_costs can override the defaults.  */
3333
3334   code = GET_CODE (x);
3335   switch (code)
3336     {
3337     case MULT:
3338       total = COSTS_N_INSNS (5);
3339       break;
3340     case DIV:
3341     case UDIV:
3342     case MOD:
3343     case UMOD:
3344       total = COSTS_N_INSNS (7);
3345       break;
3346     case USE:
3347       /* Used in combine.c as a marker.  */
3348       total = 0;
3349       break;
3350     default:
3351       total = COSTS_N_INSNS (1);
3352     }
3353
3354   switch (code)
3355     {
3356     case REG:
3357       return 0;
3358
3359     case SUBREG:
3360       total = 0;
3361       /* If we can't tie these modes, make this expensive.  The larger
3362          the mode, the more expensive it is.  */
3363       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3364         return COSTS_N_INSNS (2
3365                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3366       break;
3367
3368     default:
3369       if (targetm.rtx_costs (x, code, outer_code, &total))
3370         return total;
3371       break;
3372     }
3373
3374   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3375      which is already in total.  */
3376
3377   fmt = GET_RTX_FORMAT (code);
3378   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3379     if (fmt[i] == 'e')
3380       total += rtx_cost (XEXP (x, i), code);
3381     else if (fmt[i] == 'E')
3382       for (j = 0; j < XVECLEN (x, i); j++)
3383         total += rtx_cost (XVECEXP (x, i, j), code);
3384
3385   return total;
3386 }
3387 \f
3388 /* Return cost of address expression X.
3389    Expect that X is properly formed address reference.  */
3390
3391 int
3392 address_cost (rtx x, enum machine_mode mode)
3393 {
3394   /* We may be asked for cost of various unusual addresses, such as operands
3395      of push instruction.  It is not worthwhile to complicate writing
3396      of the target hook by such cases.  */
3397
3398   if (!memory_address_p (mode, x))
3399     return 1000;
3400
3401   return targetm.address_cost (x);
3402 }
3403
3404 /* If the target doesn't override, compute the cost as with arithmetic.  */
3405
3406 int
3407 default_address_cost (rtx x)
3408 {
3409   return rtx_cost (x, MEM);
3410 }
3411 \f
3412
3413 unsigned HOST_WIDE_INT
3414 nonzero_bits (rtx x, enum machine_mode mode)
3415 {
3416   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3417 }
3418
3419 unsigned int
3420 num_sign_bit_copies (rtx x, enum machine_mode mode)
3421 {
3422   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3423 }
3424
3425 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3426    It avoids exponential behavior in nonzero_bits1 when X has
3427    identical subexpressions on the first or the second level.  */
3428
3429 static unsigned HOST_WIDE_INT
3430 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3431                      enum machine_mode known_mode,
3432                      unsigned HOST_WIDE_INT known_ret)
3433 {
3434   if (x == known_x && mode == known_mode)
3435     return known_ret;
3436
3437   /* Try to find identical subexpressions.  If found call
3438      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3439      precomputed value for the subexpression as KNOWN_RET.  */
3440
3441   if (ARITHMETIC_P (x))
3442     {
3443       rtx x0 = XEXP (x, 0);
3444       rtx x1 = XEXP (x, 1);
3445
3446       /* Check the first level.  */
3447       if (x0 == x1)
3448         return nonzero_bits1 (x, mode, x0, mode,
3449                               cached_nonzero_bits (x0, mode, known_x,
3450                                                    known_mode, known_ret));
3451
3452       /* Check the second level.  */
3453       if (ARITHMETIC_P (x0)
3454           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3455         return nonzero_bits1 (x, mode, x1, mode,
3456                               cached_nonzero_bits (x1, mode, known_x,
3457                                                    known_mode, known_ret));
3458
3459       if (ARITHMETIC_P (x1)
3460           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3461         return nonzero_bits1 (x, mode, x0, mode,
3462                               cached_nonzero_bits (x0, mode, known_x,
3463                                                    known_mode, known_ret));
3464     }
3465
3466   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3467 }
3468
3469 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3470    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3471    is less useful.  We can't allow both, because that results in exponential
3472    run time recursion.  There is a nullstone testcase that triggered
3473    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3474 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3475
3476 /* Given an expression, X, compute which bits in X can be nonzero.
3477    We don't care about bits outside of those defined in MODE.
3478
3479    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3480    an arithmetic operation, we can do better.  */
3481
3482 static unsigned HOST_WIDE_INT
3483 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3484                enum machine_mode known_mode,
3485                unsigned HOST_WIDE_INT known_ret)
3486 {
3487   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3488   unsigned HOST_WIDE_INT inner_nz;
3489   enum rtx_code code;
3490   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3491
3492   /* For floating-point values, assume all bits are needed.  */
3493   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3494     return nonzero;
3495
3496   /* If X is wider than MODE, use its mode instead.  */
3497   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3498     {
3499       mode = GET_MODE (x);
3500       nonzero = GET_MODE_MASK (mode);
3501       mode_width = GET_MODE_BITSIZE (mode);
3502     }
3503
3504   if (mode_width > HOST_BITS_PER_WIDE_INT)
3505     /* Our only callers in this case look for single bit values.  So
3506        just return the mode mask.  Those tests will then be false.  */
3507     return nonzero;
3508
3509 #ifndef WORD_REGISTER_OPERATIONS
3510   /* If MODE is wider than X, but both are a single word for both the host
3511      and target machines, we can compute this from which bits of the
3512      object might be nonzero in its own mode, taking into account the fact
3513      that on many CISC machines, accessing an object in a wider mode
3514      causes the high-order bits to become undefined.  So they are
3515      not known to be zero.  */
3516
3517   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3518       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3519       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3520       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3521     {
3522       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3523                                       known_x, known_mode, known_ret);
3524       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3525       return nonzero;
3526     }
3527 #endif
3528
3529   code = GET_CODE (x);
3530   switch (code)
3531     {
3532     case REG:
3533 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3534       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3535          all the bits above ptr_mode are known to be zero.  */
3536       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3537           && REG_POINTER (x))
3538         nonzero &= GET_MODE_MASK (ptr_mode);
3539 #endif
3540
3541       /* Include declared information about alignment of pointers.  */
3542       /* ??? We don't properly preserve REG_POINTER changes across
3543          pointer-to-integer casts, so we can't trust it except for
3544          things that we know must be pointers.  See execute/960116-1.c.  */
3545       if ((x == stack_pointer_rtx
3546            || x == frame_pointer_rtx
3547            || x == arg_pointer_rtx)
3548           && REGNO_POINTER_ALIGN (REGNO (x)))
3549         {
3550           unsigned HOST_WIDE_INT alignment
3551             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3552
3553 #ifdef PUSH_ROUNDING
3554           /* If PUSH_ROUNDING is defined, it is possible for the
3555              stack to be momentarily aligned only to that amount,
3556              so we pick the least alignment.  */
3557           if (x == stack_pointer_rtx && PUSH_ARGS)
3558             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3559                              alignment);
3560 #endif
3561
3562           nonzero &= ~(alignment - 1);
3563         }
3564
3565       {
3566         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3567         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3568                                               known_mode, known_ret,
3569                                               &nonzero_for_hook);
3570
3571         if (new)
3572           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3573                                                    known_mode, known_ret);
3574
3575         return nonzero_for_hook;
3576       }
3577
3578     case CONST_INT:
3579 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3580       /* If X is negative in MODE, sign-extend the value.  */
3581       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3582           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3583         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3584 #endif
3585
3586       return INTVAL (x);
3587
3588     case MEM:
3589 #ifdef LOAD_EXTEND_OP
3590       /* In many, if not most, RISC machines, reading a byte from memory
3591          zeros the rest of the register.  Noticing that fact saves a lot
3592          of extra zero-extends.  */
3593       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3594         nonzero &= GET_MODE_MASK (GET_MODE (x));
3595 #endif
3596       break;
3597
3598     case EQ:  case NE:
3599     case UNEQ:  case LTGT:
3600     case GT:  case GTU:  case UNGT:
3601     case LT:  case LTU:  case UNLT:
3602     case GE:  case GEU:  case UNGE:
3603     case LE:  case LEU:  case UNLE:
3604     case UNORDERED: case ORDERED:
3605       /* If this produces an integer result, we know which bits are set.
3606          Code here used to clear bits outside the mode of X, but that is
3607          now done above.  */
3608       /* Mind that MODE is the mode the caller wants to look at this
3609          operation in, and not the actual operation mode.  We can wind
3610          up with (subreg:DI (gt:V4HI x y)), and we don't have anything
3611          that describes the results of a vector compare.  */
3612       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
3613           && mode_width <= HOST_BITS_PER_WIDE_INT)
3614         nonzero = STORE_FLAG_VALUE;
3615       break;
3616
3617     case NEG:
3618 #if 0
3619       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3620          and num_sign_bit_copies.  */
3621       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3622           == GET_MODE_BITSIZE (GET_MODE (x)))
3623         nonzero = 1;
3624 #endif
3625
3626       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3627         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3628       break;
3629
3630     case ABS:
3631 #if 0
3632       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3633          and num_sign_bit_copies.  */
3634       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3635           == GET_MODE_BITSIZE (GET_MODE (x)))
3636         nonzero = 1;
3637 #endif
3638       break;
3639
3640     case TRUNCATE:
3641       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
3642                                        known_x, known_mode, known_ret)
3643                   & GET_MODE_MASK (mode));
3644       break;
3645
3646     case ZERO_EXTEND:
3647       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3648                                       known_x, known_mode, known_ret);
3649       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3650         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3651       break;
3652
3653     case SIGN_EXTEND:
3654       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
3655          Otherwise, show all the bits in the outer mode but not the inner
3656          may be nonzero.  */
3657       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
3658                                       known_x, known_mode, known_ret);
3659       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3660         {
3661           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3662           if (inner_nz
3663               & (((HOST_WIDE_INT) 1
3664                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
3665             inner_nz |= (GET_MODE_MASK (mode)
3666                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
3667         }
3668
3669       nonzero &= inner_nz;
3670       break;
3671
3672     case AND:
3673       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3674                                        known_x, known_mode, known_ret)
3675                  & cached_nonzero_bits (XEXP (x, 1), mode,
3676                                         known_x, known_mode, known_ret);
3677       break;
3678
3679     case XOR:   case IOR:
3680     case UMIN:  case UMAX:  case SMIN:  case SMAX:
3681       {
3682         unsigned HOST_WIDE_INT nonzero0 =
3683           cached_nonzero_bits (XEXP (x, 0), mode,
3684                                known_x, known_mode, known_ret);
3685
3686         /* Don't call nonzero_bits for the second time if it cannot change
3687            anything.  */
3688         if ((nonzero & nonzero0) != nonzero)
3689           nonzero &= nonzero0
3690                      | cached_nonzero_bits (XEXP (x, 1), mode,
3691                                             known_x, known_mode, known_ret);
3692       }
3693       break;
3694
3695     case PLUS:  case MINUS:
3696     case MULT:
3697     case DIV:   case UDIV:
3698     case MOD:   case UMOD:
3699       /* We can apply the rules of arithmetic to compute the number of
3700          high- and low-order zero bits of these operations.  We start by
3701          computing the width (position of the highest-order nonzero bit)
3702          and the number of low-order zero bits for each value.  */
3703       {
3704         unsigned HOST_WIDE_INT nz0 =
3705           cached_nonzero_bits (XEXP (x, 0), mode,
3706                                known_x, known_mode, known_ret);
3707         unsigned HOST_WIDE_INT nz1 =
3708           cached_nonzero_bits (XEXP (x, 1), mode,
3709                                known_x, known_mode, known_ret);
3710         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
3711         int width0 = floor_log2 (nz0) + 1;
3712         int width1 = floor_log2 (nz1) + 1;
3713         int low0 = floor_log2 (nz0 & -nz0);
3714         int low1 = floor_log2 (nz1 & -nz1);
3715         HOST_WIDE_INT op0_maybe_minusp
3716           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
3717         HOST_WIDE_INT op1_maybe_minusp
3718           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
3719         unsigned int result_width = mode_width;
3720         int result_low = 0;
3721
3722         switch (code)
3723           {
3724           case PLUS:
3725             result_width = MAX (width0, width1) + 1;
3726             result_low = MIN (low0, low1);
3727             break;
3728           case MINUS:
3729             result_low = MIN (low0, low1);
3730             break;
3731           case MULT:
3732             result_width = width0 + width1;
3733             result_low = low0 + low1;
3734             break;
3735           case DIV:
3736             if (width1 == 0)
3737               break;
3738             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3739               result_width = width0;
3740             break;
3741           case UDIV:
3742             if (width1 == 0)
3743               break;
3744             result_width = width0;
3745             break;
3746           case MOD:
3747             if (width1 == 0)
3748               break;
3749             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3750               result_width = MIN (width0, width1);
3751             result_low = MIN (low0, low1);
3752             break;
3753           case UMOD:
3754             if (width1 == 0)
3755               break;
3756             result_width = MIN (width0, width1);
3757             result_low = MIN (low0, low1);
3758             break;
3759           default:
3760             gcc_unreachable ();
3761           }
3762
3763         if (result_width < mode_width)
3764           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
3765
3766         if (result_low > 0)
3767           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
3768
3769 #ifdef POINTERS_EXTEND_UNSIGNED
3770         /* If pointers extend unsigned and this is an addition or subtraction
3771            to a pointer in Pmode, all the bits above ptr_mode are known to be
3772            zero.  */
3773         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
3774             && (code == PLUS || code == MINUS)
3775             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
3776           nonzero &= GET_MODE_MASK (ptr_mode);
3777 #endif
3778       }
3779       break;
3780
3781     case ZERO_EXTRACT:
3782       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3783           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3784         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
3785       break;
3786
3787     case SUBREG:
3788       /* If this is a SUBREG formed for a promoted variable that has
3789          been zero-extended, we know that at least the high-order bits
3790          are zero, though others might be too.  */
3791
3792       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
3793         nonzero = GET_MODE_MASK (GET_MODE (x))
3794                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
3795                                          known_x, known_mode, known_ret);
3796
3797       /* If the inner mode is a single word for both the host and target
3798          machines, we can compute this from which bits of the inner
3799          object might be nonzero.  */
3800       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
3801           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
3802               <= HOST_BITS_PER_WIDE_INT))
3803         {
3804           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
3805                                           known_x, known_mode, known_ret);
3806
3807 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
3808           /* If this is a typical RISC machine, we only have to worry
3809              about the way loads are extended.  */
3810           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
3811                ? (((nonzero
3812                     & (((unsigned HOST_WIDE_INT) 1
3813                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
3814                    != 0))
3815                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
3816               || !MEM_P (SUBREG_REG (x)))
3817 #endif
3818             {
3819               /* On many CISC machines, accessing an object in a wider mode
3820                  causes the high-order bits to become undefined.  So they are
3821                  not known to be zero.  */
3822               if (GET_MODE_SIZE (GET_MODE (x))
3823                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3824                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
3825                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
3826             }
3827         }
3828       break;
3829
3830     case ASHIFTRT:
3831     case LSHIFTRT:
3832     case ASHIFT:
3833     case ROTATE:
3834       /* The nonzero bits are in two classes: any bits within MODE
3835          that aren't in GET_MODE (x) are always significant.  The rest of the
3836          nonzero bits are those that are significant in the operand of
3837          the shift when shifted the appropriate number of bits.  This
3838          shows that high-order bits are cleared by the right shift and
3839          low-order bits by left shifts.  */
3840       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3841           && INTVAL (XEXP (x, 1)) >= 0
3842           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3843         {
3844           enum machine_mode inner_mode = GET_MODE (x);
3845           unsigned int width = GET_MODE_BITSIZE (inner_mode);
3846           int count = INTVAL (XEXP (x, 1));
3847           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
3848           unsigned HOST_WIDE_INT op_nonzero =
3849             cached_nonzero_bits (XEXP (x, 0), mode,
3850                                  known_x, known_mode, known_ret);
3851           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
3852           unsigned HOST_WIDE_INT outer = 0;
3853
3854           if (mode_width > width)
3855             outer = (op_nonzero & nonzero & ~mode_mask);
3856
3857           if (code == LSHIFTRT)
3858             inner >>= count;
3859           else if (code == ASHIFTRT)
3860             {
3861               inner >>= count;
3862
3863               /* If the sign bit may have been nonzero before the shift, we
3864                  need to mark all the places it could have been copied to
3865                  by the shift as possibly nonzero.  */
3866               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
3867                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
3868             }
3869           else if (code == ASHIFT)
3870             inner <<= count;
3871           else
3872             inner = ((inner << (count % width)
3873                       | (inner >> (width - (count % width)))) & mode_mask);
3874
3875           nonzero &= (outer | inner);
3876         }
3877       break;
3878
3879     case FFS:
3880     case POPCOUNT:
3881       /* This is at most the number of bits in the mode.  */
3882       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
3883       break;
3884
3885     case CLZ:
3886       /* If CLZ has a known value at zero, then the nonzero bits are
3887          that value, plus the number of bits in the mode minus one.  */
3888       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3889         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3890       else
3891         nonzero = -1;
3892       break;
3893
3894     case CTZ:
3895       /* If CTZ has a known value at zero, then the nonzero bits are
3896          that value, plus the number of bits in the mode minus one.  */
3897       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3898         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3899       else
3900         nonzero = -1;
3901       break;
3902
3903     case PARITY:
3904       nonzero = 1;
3905       break;
3906
3907     case IF_THEN_ELSE:
3908       {
3909         unsigned HOST_WIDE_INT nonzero_true =
3910           cached_nonzero_bits (XEXP (x, 1), mode,
3911                                known_x, known_mode, known_ret);
3912
3913         /* Don't call nonzero_bits for the second time if it cannot change
3914            anything.  */
3915         if ((nonzero & nonzero_true) != nonzero)
3916           nonzero &= nonzero_true
3917                      | cached_nonzero_bits (XEXP (x, 2), mode,
3918                                             known_x, known_mode, known_ret);
3919       }
3920       break;
3921
3922     default:
3923       break;
3924     }
3925
3926   return nonzero;
3927 }
3928
3929 /* See the macro definition above.  */
3930 #undef cached_num_sign_bit_copies
3931
3932 \f
3933 /* The function cached_num_sign_bit_copies is a wrapper around
3934    num_sign_bit_copies1.  It avoids exponential behavior in
3935    num_sign_bit_copies1 when X has identical subexpressions on the
3936    first or the second level.  */
3937
3938 static unsigned int
3939 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
3940                             enum machine_mode known_mode,
3941                             unsigned int known_ret)
3942 {
3943   if (x == known_x && mode == known_mode)
3944     return known_ret;
3945
3946   /* Try to find identical subexpressions.  If found call
3947      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
3948      the precomputed value for the subexpression as KNOWN_RET.  */
3949
3950   if (ARITHMETIC_P (x))
3951     {
3952       rtx x0 = XEXP (x, 0);
3953       rtx x1 = XEXP (x, 1);
3954
3955       /* Check the first level.  */
3956       if (x0 == x1)
3957         return
3958           num_sign_bit_copies1 (x, mode, x0, mode,
3959                                 cached_num_sign_bit_copies (x0, mode, known_x,
3960                                                             known_mode,
3961                                                             known_ret));
3962
3963       /* Check the second level.  */
3964       if (ARITHMETIC_P (x0)
3965           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3966         return
3967           num_sign_bit_copies1 (x, mode, x1, mode,
3968                                 cached_num_sign_bit_copies (x1, mode, known_x,
3969                                                             known_mode,
3970                                                             known_ret));
3971
3972       if (ARITHMETIC_P (x1)
3973           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3974         return
3975           num_sign_bit_copies1 (x, mode, x0, mode,
3976                                 cached_num_sign_bit_copies (x0, mode, known_x,
3977                                                             known_mode,
3978                                                             known_ret));
3979     }
3980
3981   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
3982 }
3983
3984 /* Return the number of bits at the high-order end of X that are known to
3985    be equal to the sign bit.  X will be used in mode MODE; if MODE is
3986    VOIDmode, X will be used in its own mode.  The returned value  will always
3987    be between 1 and the number of bits in MODE.  */
3988
3989 static unsigned int
3990 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
3991                       enum machine_mode known_mode,
3992                       unsigned int known_ret)
3993 {
3994   enum rtx_code code = GET_CODE (x);
3995   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
3996   int num0, num1, result;
3997   unsigned HOST_WIDE_INT nonzero;
3998
3999   /* If we weren't given a mode, use the mode of X.  If the mode is still
4000      VOIDmode, we don't know anything.  Likewise if one of the modes is
4001      floating-point.  */
4002
4003   if (mode == VOIDmode)
4004     mode = GET_MODE (x);
4005
4006   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
4007     return 1;
4008
4009   /* For a smaller object, just ignore the high bits.  */
4010   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
4011     {
4012       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
4013                                          known_x, known_mode, known_ret);
4014       return MAX (1,
4015                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
4016     }
4017
4018   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
4019     {
4020 #ifndef WORD_REGISTER_OPERATIONS
4021   /* If this machine does not do all register operations on the entire
4022      register and MODE is wider than the mode of X, we can say nothing
4023      at all about the high-order bits.  */
4024       return 1;
4025 #else
4026       /* Likewise on machines that do, if the mode of the object is smaller
4027          than a word and loads of that size don't sign extend, we can say
4028          nothing about the high order bits.  */
4029       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4030 #ifdef LOAD_EXTEND_OP
4031           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4032 #endif
4033           )
4034         return 1;
4035 #endif
4036     }
4037
4038   switch (code)
4039     {
4040     case REG:
4041
4042 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4043       /* If pointers extend signed and this is a pointer in Pmode, say that
4044          all the bits above ptr_mode are known to be sign bit copies.  */
4045       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4046           && REG_POINTER (x))
4047         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4048 #endif
4049
4050       {
4051         unsigned int copies_for_hook = 1, copies = 1;
4052         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4053                                                      known_mode, known_ret,
4054                                                      &copies_for_hook);
4055
4056         if (new)
4057           copies = cached_num_sign_bit_copies (new, mode, known_x,
4058                                                known_mode, known_ret);
4059
4060         if (copies > 1 || copies_for_hook > 1)
4061           return MAX (copies, copies_for_hook);
4062
4063         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4064       }
4065       break;
4066
4067     case MEM:
4068 #ifdef LOAD_EXTEND_OP
4069       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4070       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4071         return MAX (1, ((int) bitwidth
4072                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4073 #endif
4074       break;
4075
4076     case CONST_INT:
4077       /* If the constant is negative, take its 1's complement and remask.
4078          Then see how many zero bits we have.  */
4079       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4080       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4081           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4082         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4083
4084       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4085
4086     case SUBREG:
4087       /* If this is a SUBREG for a promoted object that is sign-extended
4088          and we are looking at it in a wider mode, we know that at least the
4089          high-order bits are known to be sign bit copies.  */
4090
4091       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4092         {
4093           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4094                                              known_x, known_mode, known_ret);
4095           return MAX ((int) bitwidth
4096                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4097                       num0);
4098         }
4099
4100       /* For a smaller object, just ignore the high bits.  */
4101       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4102         {
4103           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4104                                              known_x, known_mode, known_ret);
4105           return MAX (1, (num0
4106                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4107                                    - bitwidth)));
4108         }
4109
4110 #ifdef WORD_REGISTER_OPERATIONS
4111 #ifdef LOAD_EXTEND_OP
4112       /* For paradoxical SUBREGs on machines where all register operations
4113          affect the entire register, just look inside.  Note that we are
4114          passing MODE to the recursive call, so the number of sign bit copies
4115          will remain relative to that mode, not the inner mode.  */
4116
4117       /* This works only if loads sign extend.  Otherwise, if we get a
4118          reload for the inner part, it may be loaded from the stack, and
4119          then we lose all sign bit copies that existed before the store
4120          to the stack.  */
4121
4122       if ((GET_MODE_SIZE (GET_MODE (x))
4123            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4124           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4125           && MEM_P (SUBREG_REG (x)))
4126         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4127                                            known_x, known_mode, known_ret);
4128 #endif
4129 #endif
4130       break;
4131
4132     case SIGN_EXTRACT:
4133       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4134         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4135       break;
4136
4137     case SIGN_EXTEND:
4138       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4139               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4140                                             known_x, known_mode, known_ret));
4141
4142     case TRUNCATE:
4143       /* For a smaller object, just ignore the high bits.  */
4144       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4145                                          known_x, known_mode, known_ret);
4146       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4147                                     - bitwidth)));
4148
4149     case NOT:
4150       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4151                                          known_x, known_mode, known_ret);
4152
4153     case ROTATE:       case ROTATERT:
4154       /* If we are rotating left by a number of bits less than the number
4155          of sign bit copies, we can just subtract that amount from the
4156          number.  */
4157       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4158           && INTVAL (XEXP (x, 1)) >= 0
4159           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4160         {
4161           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4162                                              known_x, known_mode, known_ret);
4163           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4164                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4165         }
4166       break;
4167
4168     case NEG:
4169       /* In general, this subtracts one sign bit copy.  But if the value
4170          is known to be positive, the number of sign bit copies is the
4171          same as that of the input.  Finally, if the input has just one bit
4172          that might be nonzero, all the bits are copies of the sign bit.  */
4173       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4174                                          known_x, known_mode, known_ret);
4175       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4176         return num0 > 1 ? num0 - 1 : 1;
4177
4178       nonzero = nonzero_bits (XEXP (x, 0), mode);
4179       if (nonzero == 1)
4180         return bitwidth;
4181
4182       if (num0 > 1
4183           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4184         num0--;
4185
4186       return num0;
4187
4188     case IOR:   case AND:   case XOR:
4189     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4190       /* Logical operations will preserve the number of sign-bit copies.
4191          MIN and MAX operations always return one of the operands.  */
4192       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4193                                          known_x, known_mode, known_ret);
4194       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4195                                          known_x, known_mode, known_ret);
4196       return MIN (num0, num1);
4197
4198     case PLUS:  case MINUS:
4199       /* For addition and subtraction, we can have a 1-bit carry.  However,
4200          if we are subtracting 1 from a positive number, there will not
4201          be such a carry.  Furthermore, if the positive number is known to
4202          be 0 or 1, we know the result is either -1 or 0.  */
4203
4204       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4205           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4206         {
4207           nonzero = nonzero_bits (XEXP (x, 0), mode);
4208           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4209             return (nonzero == 1 || nonzero == 0 ? bitwidth
4210                     : bitwidth - floor_log2 (nonzero) - 1);
4211         }
4212
4213       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4214                                          known_x, known_mode, known_ret);
4215       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4216                                          known_x, known_mode, known_ret);
4217       result = MAX (1, MIN (num0, num1) - 1);
4218
4219 #ifdef POINTERS_EXTEND_UNSIGNED
4220       /* If pointers extend signed and this is an addition or subtraction
4221          to a pointer in Pmode, all the bits above ptr_mode are known to be
4222          sign bit copies.  */
4223       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4224           && (code == PLUS || code == MINUS)
4225           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4226         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4227                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4228                       result);
4229 #endif
4230       return result;
4231
4232     case MULT:
4233       /* The number of bits of the product is the sum of the number of
4234          bits of both terms.  However, unless one of the terms if known
4235          to be positive, we must allow for an additional bit since negating
4236          a negative number can remove one sign bit copy.  */
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
4243       result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
4244       if (result > 0
4245           && (bitwidth > HOST_BITS_PER_WIDE_INT
4246               || (((nonzero_bits (XEXP (x, 0), mode)
4247                     & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4248                   && ((nonzero_bits (XEXP (x, 1), mode)
4249                        & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
4250         result--;
4251
4252       return MAX (1, result);
4253
4254     case UDIV:
4255       /* The result must be <= the first operand.  If the first operand
4256          has the high bit set, we know nothing about the number of sign
4257          bit copies.  */
4258       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4259         return 1;
4260       else if ((nonzero_bits (XEXP (x, 0), mode)
4261                 & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4262         return 1;
4263       else
4264         return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4265                                            known_x, known_mode, known_ret);
4266
4267     case UMOD:
4268       /* The result must be <= the second operand.  */
4269       return cached_num_sign_bit_copies (XEXP (x, 1), mode,
4270                                            known_x, known_mode, known_ret);
4271
4272     case DIV:
4273       /* Similar to unsigned division, except that we have to worry about
4274          the case where the divisor is negative, in which case we have
4275          to add 1.  */
4276       result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4277                                            known_x, known_mode, known_ret);
4278       if (result > 1
4279           && (bitwidth > HOST_BITS_PER_WIDE_INT
4280               || (nonzero_bits (XEXP (x, 1), mode)
4281                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4282         result--;
4283
4284       return result;
4285
4286     case MOD:
4287       result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4288                                            known_x, known_mode, known_ret);
4289       if (result > 1
4290           && (bitwidth > HOST_BITS_PER_WIDE_INT
4291               || (nonzero_bits (XEXP (x, 1), mode)
4292                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4293         result--;
4294
4295       return result;
4296
4297     case ASHIFTRT:
4298       /* Shifts by a constant add to the number of bits equal to the
4299          sign bit.  */
4300       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4301                                          known_x, known_mode, known_ret);
4302       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4303           && INTVAL (XEXP (x, 1)) > 0)
4304         num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
4305
4306       return num0;
4307
4308     case ASHIFT:
4309       /* Left shifts destroy copies.  */
4310       if (GET_CODE (XEXP (x, 1)) != CONST_INT
4311           || INTVAL (XEXP (x, 1)) < 0
4312           || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
4313         return 1;
4314
4315       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4316                                          known_x, known_mode, known_ret);
4317       return MAX (1, num0 - INTVAL (XEXP (x, 1)));
4318
4319     case IF_THEN_ELSE:
4320       num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4321                                          known_x, known_mode, known_ret);
4322       num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
4323                                          known_x, known_mode, known_ret);
4324       return MIN (num0, num1);
4325
4326     case EQ:  case NE:  case GE:  case GT:  case LE:  case LT:
4327     case UNEQ:  case LTGT:  case UNGE:  case UNGT:  case UNLE:  case UNLT:
4328     case GEU: case GTU: case LEU: case LTU:
4329     case UNORDERED: case ORDERED:
4330       /* If the constant is negative, take its 1's complement and remask.
4331          Then see how many zero bits we have.  */
4332       nonzero = STORE_FLAG_VALUE;
4333       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4334           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4335         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4336
4337       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4338
4339     default:
4340       break;
4341     }
4342
4343   /* If we haven't been able to figure it out by one of the above rules,
4344      see if some of the high-order bits are known to be zero.  If so,
4345      count those bits and return one less than that amount.  If we can't
4346      safely compute the mask for this mode, always return BITWIDTH.  */
4347
4348   bitwidth = GET_MODE_BITSIZE (mode);
4349   if (bitwidth > HOST_BITS_PER_WIDE_INT)
4350     return 1;
4351
4352   nonzero = nonzero_bits (x, mode);
4353   return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
4354          ? 1 : bitwidth - floor_log2 (nonzero) - 1;
4355 }
4356
4357 /* Calculate the rtx_cost of a single instruction.  A return value of
4358    zero indicates an instruction pattern without a known cost.  */
4359
4360 int
4361 insn_rtx_cost (rtx pat)
4362 {
4363   int i, cost;
4364   rtx set;
4365
4366   /* Extract the single set rtx from the instruction pattern.
4367      We can't use single_set since we only have the pattern.  */
4368   if (GET_CODE (pat) == SET)
4369     set = pat;
4370   else if (GET_CODE (pat) == PARALLEL)
4371     {
4372       set = NULL_RTX;
4373       for (i = 0; i < XVECLEN (pat, 0); i++)
4374         {
4375           rtx x = XVECEXP (pat, 0, i);
4376           if (GET_CODE (x) == SET)
4377             {
4378               if (set)
4379                 return 0;
4380               set = x;
4381             }
4382         }
4383       if (!set)
4384         return 0;
4385     }
4386   else
4387     return 0;
4388
4389   cost = rtx_cost (SET_SRC (set), SET);
4390   return cost > 0 ? cost : COSTS_N_INSNS (1);
4391 }
4392
4393 /* Given an insn INSN and condition COND, return the condition in a
4394    canonical form to simplify testing by callers.  Specifically:
4395
4396    (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
4397    (2) Both operands will be machine operands; (cc0) will have been replaced.
4398    (3) If an operand is a constant, it will be the second operand.
4399    (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
4400        for GE, GEU, and LEU.
4401
4402    If the condition cannot be understood, or is an inequality floating-point
4403    comparison which needs to be reversed, 0 will be returned.
4404
4405    If REVERSE is nonzero, then reverse the condition prior to canonizing it.
4406
4407    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4408    insn used in locating the condition was found.  If a replacement test
4409    of the condition is desired, it should be placed in front of that
4410    insn and we will be sure that the inputs are still valid.
4411
4412    If WANT_REG is nonzero, we wish the condition to be relative to that
4413    register, if possible.  Therefore, do not canonicalize the condition
4414    further.  If ALLOW_CC_MODE is nonzero, allow the condition returned
4415    to be a compare to a CC mode register.
4416
4417    If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST
4418    and at INSN.  */
4419
4420 rtx
4421 canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest,
4422                         rtx want_reg, int allow_cc_mode, int valid_at_insn_p)
4423 {
4424   enum rtx_code code;
4425   rtx prev = insn;
4426   rtx set;
4427   rtx tem;
4428   rtx op0, op1;
4429   int reverse_code = 0;
4430   enum machine_mode mode;
4431   basic_block bb = BLOCK_FOR_INSN (insn);
4432
4433   code = GET_CODE (cond);
4434   mode = GET_MODE (cond);
4435   op0 = XEXP (cond, 0);
4436   op1 = XEXP (cond, 1);
4437
4438   if (reverse)
4439     code = reversed_comparison_code (cond, insn);
4440   if (code == UNKNOWN)
4441     return 0;
4442
4443   if (earliest)
4444     *earliest = insn;
4445
4446   /* If we are comparing a register with zero, see if the register is set
4447      in the previous insn to a COMPARE or a comparison operation.  Perform
4448      the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
4449      in cse.c  */
4450
4451   while ((GET_RTX_CLASS (code) == RTX_COMPARE
4452           || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
4453          && op1 == CONST0_RTX (GET_MODE (op0))
4454          && op0 != want_reg)
4455     {
4456       /* Set nonzero when we find something of interest.  */
4457       rtx x = 0;
4458
4459 #ifdef HAVE_cc0
4460       /* If comparison with cc0, import actual comparison from compare
4461          insn.  */
4462       if (op0 == cc0_rtx)
4463         {
4464           if ((prev = prev_nonnote_insn (prev)) == 0
4465               || !NONJUMP_INSN_P (prev)
4466               || (set = single_set (prev)) == 0
4467               || SET_DEST (set) != cc0_rtx)
4468             return 0;
4469
4470           op0 = SET_SRC (set);
4471           op1 = CONST0_RTX (GET_MODE (op0));
4472           if (earliest)
4473             *earliest = prev;
4474         }
4475 #endif
4476
4477       /* If this is a COMPARE, pick up the two things being compared.  */
4478       if (GET_CODE (op0) == COMPARE)
4479         {
4480           op1 = XEXP (op0, 1);
4481           op0 = XEXP (op0, 0);
4482           continue;
4483         }
4484       else if (!REG_P (op0))
4485         break;
4486
4487       /* Go back to the previous insn.  Stop if it is not an INSN.  We also
4488          stop if it isn't a single set or if it has a REG_INC note because
4489          we don't want to bother dealing with it.  */
4490
4491       if ((prev = prev_nonnote_insn (prev)) == 0
4492           || !NONJUMP_INSN_P (prev)
4493           || FIND_REG_INC_NOTE (prev, NULL_RTX)
4494           /* In cfglayout mode, there do not have to be labels at the
4495              beginning of a block, or jumps at the end, so the previous
4496              conditions would not stop us when we reach bb boundary.  */
4497           || BLOCK_FOR_INSN (prev) != bb)
4498         break;
4499
4500       set = set_of (op0, prev);
4501
4502       if (set
4503           && (GET_CODE (set) != SET
4504               || !rtx_equal_p (SET_DEST (set), op0)))
4505         break;
4506
4507       /* If this is setting OP0, get what it sets it to if it looks
4508          relevant.  */
4509       if (set)
4510         {
4511           enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
4512 #ifdef FLOAT_STORE_FLAG_VALUE
4513           REAL_VALUE_TYPE fsfv;
4514 #endif
4515
4516           /* ??? We may not combine comparisons done in a CCmode with
4517              comparisons not done in a CCmode.  This is to aid targets
4518              like Alpha that have an IEEE compliant EQ instruction, and
4519              a non-IEEE compliant BEQ instruction.  The use of CCmode is
4520              actually artificial, simply to prevent the combination, but
4521              should not affect other platforms.
4522
4523              However, we must allow VOIDmode comparisons to match either
4524              CCmode or non-CCmode comparison, because some ports have
4525              modeless comparisons inside branch patterns.
4526
4527              ??? This mode check should perhaps look more like the mode check
4528              in simplify_comparison in combine.  */
4529
4530           if ((GET_CODE (SET_SRC (set)) == COMPARE
4531                || (((code == NE
4532                      || (code == LT
4533                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4534                          && (GET_MODE_BITSIZE (inner_mode)
4535                              <= HOST_BITS_PER_WIDE_INT)
4536                          && (STORE_FLAG_VALUE
4537                              & ((HOST_WIDE_INT) 1
4538                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4539 #ifdef FLOAT_STORE_FLAG_VALUE
4540                      || (code == LT
4541                          && SCALAR_FLOAT_MODE_P (inner_mode)
4542                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4543                              REAL_VALUE_NEGATIVE (fsfv)))
4544 #endif
4545                      ))
4546                    && COMPARISON_P (SET_SRC (set))))
4547               && (((GET_MODE_CLASS (mode) == MODE_CC)
4548                    == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4549                   || mode == VOIDmode || inner_mode == VOIDmode))
4550             x = SET_SRC (set);
4551           else if (((code == EQ
4552                      || (code == GE
4553                          && (GET_MODE_BITSIZE (inner_mode)
4554                              <= HOST_BITS_PER_WIDE_INT)
4555                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4556                          && (STORE_FLAG_VALUE
4557                              & ((HOST_WIDE_INT) 1
4558                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4559 #ifdef FLOAT_STORE_FLAG_VALUE
4560                      || (code == GE
4561                          && SCALAR_FLOAT_MODE_P (inner_mode)
4562                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4563                              REAL_VALUE_NEGATIVE (fsfv)))
4564 #endif
4565                      ))
4566                    && COMPARISON_P (SET_SRC (set))
4567                    && (((GET_MODE_CLASS (mode) == MODE_CC)
4568                         == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4569                        || mode == VOIDmode || inner_mode == VOIDmode))
4570
4571             {
4572               reverse_code = 1;
4573               x = SET_SRC (set);
4574             }
4575           else
4576             break;
4577         }
4578
4579       else if (reg_set_p (op0, prev))
4580         /* If this sets OP0, but not directly, we have to give up.  */
4581         break;
4582
4583       if (x)
4584         {
4585           /* If the caller is expecting the condition to be valid at INSN,
4586              make sure X doesn't change before INSN.  */
4587           if (valid_at_insn_p)
4588             if (modified_in_p (x, prev) || modified_between_p (x, prev, insn))
4589               break;
4590           if (COMPARISON_P (x))
4591             code = GET_CODE (x);
4592           if (reverse_code)
4593             {
4594               code = reversed_comparison_code (x, prev);
4595               if (code == UNKNOWN)
4596                 return 0;
4597               reverse_code = 0;
4598             }
4599
4600           op0 = XEXP (x, 0), op1 = XEXP (x, 1);
4601           if (earliest)
4602             *earliest = prev;
4603         }
4604     }
4605
4606   /* If constant is first, put it last.  */
4607   if (CONSTANT_P (op0))
4608     code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
4609
4610   /* If OP0 is the result of a comparison, we weren't able to find what
4611      was really being compared, so fail.  */
4612   if (!allow_cc_mode
4613       && GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
4614     return 0;
4615
4616   /* Canonicalize any ordered comparison with integers involving equality
4617      if we can do computations in the relevant mode and we do not
4618      overflow.  */
4619
4620   if (GET_MODE_CLASS (GET_MODE (op0)) != MODE_CC
4621       && GET_CODE (op1) == CONST_INT
4622       && GET_MODE (op0) != VOIDmode
4623       && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
4624     {
4625       HOST_WIDE_INT const_val = INTVAL (op1);
4626       unsigned HOST_WIDE_INT uconst_val = const_val;
4627       unsigned HOST_WIDE_INT max_val
4628         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
4629
4630       switch (code)
4631         {
4632         case LE:
4633           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
4634             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
4635           break;
4636
4637         /* When cross-compiling, const_val might be sign-extended from
4638            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
4639         case GE:
4640           if ((HOST_WIDE_INT) (const_val & max_val)
4641               != (((HOST_WIDE_INT) 1
4642                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
4643             code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0));
4644           break;
4645
4646         case LEU:
4647           if (uconst_val < max_val)
4648             code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
4649           break;
4650
4651         case GEU:
4652           if (uconst_val != 0)
4653             code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
4654           break;
4655
4656         default:
4657           break;
4658         }
4659     }
4660
4661   /* Never return CC0; return zero instead.  */
4662   if (CC0_P (op0))
4663     return 0;
4664
4665   return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
4666 }
4667
4668 /* Given a jump insn JUMP, return the condition that will cause it to branch
4669    to its JUMP_LABEL.  If the condition cannot be understood, or is an
4670    inequality floating-point comparison which needs to be reversed, 0 will
4671    be returned.
4672
4673    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4674    insn used in locating the condition was found.  If a replacement test
4675    of the condition is desired, it should be placed in front of that
4676    insn and we will be sure that the inputs are still valid.  If EARLIEST
4677    is null, the returned condition will be valid at INSN.
4678
4679    If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
4680    compare CC mode register.
4681
4682    VALID_AT_INSN_P is the same as for canonicalize_condition.  */
4683
4684 rtx
4685 get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p)
4686 {
4687   rtx cond;
4688   int reverse;
4689   rtx set;
4690
4691   /* If this is not a standard conditional jump, we can't parse it.  */
4692   if (!JUMP_P (jump)
4693       || ! any_condjump_p (jump))
4694     return 0;
4695   set = pc_set (jump);
4696
4697   cond = XEXP (SET_SRC (set), 0);
4698
4699   /* If this branches to JUMP_LABEL when the condition is false, reverse
4700      the condition.  */
4701   reverse
4702     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
4703       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
4704
4705   return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
4706                                  allow_cc_mode, valid_at_insn_p);
4707 }
4708
4709 /* Initialize the table NUM_SIGN_BIT_COPIES_IN_REP based on
4710    TARGET_MODE_REP_EXTENDED.
4711
4712    Note that we assume that the property of
4713    TARGET_MODE_REP_EXTENDED(B, C) is sticky to the integral modes
4714    narrower than mode B.  I.e., if A is a mode narrower than B then in
4715    order to be able to operate on it in mode B, mode A needs to
4716    satisfy the requirements set by the representation of mode B.  */
4717
4718 static void
4719 init_num_sign_bit_copies_in_rep (void)
4720 {
4721   enum machine_mode mode, in_mode;
4722
4723   for (in_mode = GET_CLASS_NARROWEST_MODE (MODE_INT); in_mode != VOIDmode;
4724        in_mode = GET_MODE_WIDER_MODE (mode))
4725     for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != in_mode;
4726          mode = GET_MODE_WIDER_MODE (mode))
4727       {
4728         enum machine_mode i;
4729
4730         /* Currently, it is assumed that TARGET_MODE_REP_EXTENDED
4731            extends to the next widest mode.  */
4732         gcc_assert (targetm.mode_rep_extended (mode, in_mode) == UNKNOWN
4733                     || GET_MODE_WIDER_MODE (mode) == in_mode);
4734
4735         /* We are in in_mode.  Count how many bits outside of mode
4736            have to be copies of the sign-bit.  */
4737         for (i = mode; i != in_mode; i = GET_MODE_WIDER_MODE (i))
4738           {
4739             enum machine_mode wider = GET_MODE_WIDER_MODE (i);
4740
4741             if (targetm.mode_rep_extended (i, wider) == SIGN_EXTEND
4742                 /* We can only check sign-bit copies starting from the
4743                    top-bit.  In order to be able to check the bits we
4744                    have already seen we pretend that subsequent bits
4745                    have to be sign-bit copies too.  */
4746                 || num_sign_bit_copies_in_rep [in_mode][mode])
4747               num_sign_bit_copies_in_rep [in_mode][mode]
4748                 += GET_MODE_BITSIZE (wider) - GET_MODE_BITSIZE (i);
4749           }
4750       }
4751 }
4752
4753 /* Suppose that truncation from the machine mode of X to MODE is not a
4754    no-op.  See if there is anything special about X so that we can
4755    assume it already contains a truncated value of MODE.  */
4756
4757 bool
4758 truncated_to_mode (enum machine_mode mode, rtx x)
4759 {
4760   /* This register has already been used in MODE without explicit
4761      truncation.  */
4762   if (REG_P (x) && rtl_hooks.reg_truncated_to_mode (mode, x))
4763     return true;
4764
4765   /* See if we already satisfy the requirements of MODE.  If yes we
4766      can just switch to MODE.  */
4767   if (num_sign_bit_copies_in_rep[GET_MODE (x)][mode]
4768       && (num_sign_bit_copies (x, GET_MODE (x))
4769           >= num_sign_bit_copies_in_rep[GET_MODE (x)][mode] + 1))
4770     return true;
4771
4772   return false;
4773 }
4774 \f
4775 /* Initialize non_rtx_starting_operands, which is used to speed up
4776    for_each_rtx.  */
4777 void
4778 init_rtlanal (void)
4779 {
4780   int i;
4781   for (i = 0; i < NUM_RTX_CODE; i++)
4782     {
4783       const char *format = GET_RTX_FORMAT (i);
4784       const char *first = strpbrk (format, "eEV");
4785       non_rtx_starting_operands[i] = first ? first - format : -1;
4786     }
4787
4788   init_num_sign_bit_copies_in_rep ();
4789 }
4790 \f
4791 /* Check whether this is a constant pool constant.  */
4792 bool
4793 constant_pool_constant_p (rtx x)
4794 {
4795   x = avoid_constant_pool_reference (x);
4796   return GET_CODE (x) == CONST_DOUBLE;
4797 }
4798