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