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