gcc/rtlanal.c

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