gcc/rtlanal.c

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