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