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