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