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