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