gcc/rtlanal.c

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