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