gcc/rtlanal.c

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