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