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 /* Return nonzero if evaluating rtx X might cause a trap.  UNALIGNED_MEMS
2037    controls whether nonzero is returned for unaligned memory accesses on
2038    strict alignment machines.  */
2039
2040 static int
2041 may_trap_p_1 (rtx x, bool unaligned_mems)
2042 {
2043   int i;
2044   enum rtx_code code;
2045   const char *fmt;
2046
2047   if (x == 0)
2048     return 0;
2049   code = GET_CODE (x);
2050   switch (code)
2051     {
2052       /* Handle these cases quickly.  */
2053     case CONST_INT:
2054     case CONST_DOUBLE:
2055     case CONST_VECTOR:
2056     case SYMBOL_REF:
2057     case LABEL_REF:
2058     case CONST:
2059     case PC:
2060     case CC0:
2061     case REG:
2062     case SCRATCH:
2063       return 0;
2064
2065     case ASM_INPUT:
2066     case UNSPEC_VOLATILE:
2067     case TRAP_IF:
2068       return 1;
2069
2070     case ASM_OPERANDS:
2071       return MEM_VOLATILE_P (x);
2072
2073       /* Memory ref can trap unless it's a static var or a stack slot.  */
2074     case MEM:
2075       if (MEM_NOTRAP_P (x)
2076           && (!STRICT_ALIGNMENT || !unaligned_mems))
2077         return 0;
2078       return
2079         rtx_addr_can_trap_p_1 (XEXP (x, 0), GET_MODE (x), unaligned_mems);
2080
2081       /* Division by a non-constant might trap.  */
2082     case DIV:
2083     case MOD:
2084     case UDIV:
2085     case UMOD:
2086       if (HONOR_SNANS (GET_MODE (x)))
2087         return 1;
2088       if (SCALAR_FLOAT_MODE_P (GET_MODE (x)))
2089         return flag_trapping_math;
2090       if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2091         return 1;
2092       break;
2093
2094     case EXPR_LIST:
2095       /* An EXPR_LIST is used to represent a function call.  This
2096          certainly may trap.  */
2097       return 1;
2098
2099     case GE:
2100     case GT:
2101     case LE:
2102     case LT:
2103     case LTGT:
2104     case COMPARE:
2105       /* Some floating point comparisons may trap.  */
2106       if (!flag_trapping_math)
2107         break;
2108       /* ??? There is no machine independent way to check for tests that trap
2109          when COMPARE is used, though many targets do make this distinction.
2110          For instance, sparc uses CCFPE for compares which generate exceptions
2111          and CCFP for compares which do not generate exceptions.  */
2112       if (HONOR_NANS (GET_MODE (x)))
2113         return 1;
2114       /* But often the compare has some CC mode, so check operand
2115          modes as well.  */
2116       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2117           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2118         return 1;
2119       break;
2120
2121     case EQ:
2122     case NE:
2123       if (HONOR_SNANS (GET_MODE (x)))
2124         return 1;
2125       /* Often comparison is CC mode, so check operand modes.  */
2126       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2127           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2128         return 1;
2129       break;
2130
2131     case FIX:
2132       /* Conversion of floating point might trap.  */
2133       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2134         return 1;
2135       break;
2136
2137     case NEG:
2138     case ABS:
2139     case SUBREG:
2140       /* These operations don't trap even with floating point.  */
2141       break;
2142
2143     default:
2144       /* Any floating arithmetic may trap.  */
2145       if (SCALAR_FLOAT_MODE_P (GET_MODE (x))
2146           && flag_trapping_math)
2147         return 1;
2148     }
2149
2150   fmt = GET_RTX_FORMAT (code);
2151   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2152     {
2153       if (fmt[i] == 'e')
2154         {
2155           if (may_trap_p_1 (XEXP (x, i), unaligned_mems))
2156             return 1;
2157         }
2158       else if (fmt[i] == 'E')
2159         {
2160           int j;
2161           for (j = 0; j < XVECLEN (x, i); j++)
2162             if (may_trap_p_1 (XVECEXP (x, i, j), unaligned_mems))
2163               return 1;
2164         }
2165     }
2166   return 0;
2167 }
2168
2169 /* Return nonzero if evaluating rtx X might cause a trap.  */
2170
2171 int
2172 may_trap_p (rtx x)
2173 {
2174   return may_trap_p_1 (x, false);
2175 }
2176
2177 /* Same as above, but additionally return non-zero if evaluating rtx X might
2178    cause a fault.  We define a fault for the purpose of this function as a
2179    erroneous execution condition that cannot be encountered during the normal
2180    execution of a valid program; the typical example is an unaligned memory
2181    access on a strict alignment machine.  The compiler guarantees that it
2182    doesn't generate code that will fault from a valid program, but this
2183    guarantee doesn't mean anything for individual instructions.  Consider
2184    the following example:
2185
2186       struct S { int d; union { char *cp; int *ip; }; };
2187
2188       int foo(struct S *s)
2189       {
2190         if (s->d == 1)
2191           return *s->ip;
2192         else
2193           return *s->cp;
2194       }
2195
2196    on a strict alignment machine.  In a valid program, foo will never be
2197    invoked on a structure for which d is equal to 1 and the underlying
2198    unique field of the union not aligned on a 4-byte boundary, but the
2199    expression *s->ip might cause a fault if considered individually.
2200
2201    At the RTL level, potentially problematic expressions will almost always
2202    verify may_trap_p; for example, the above dereference can be emitted as
2203    (mem:SI (reg:P)) and this expression is may_trap_p for a generic register.
2204    However, suppose that foo is inlined in a caller that causes s->cp to
2205    point to a local character variable and guarantees that s->d is not set
2206    to 1; foo may have been effectively translated into pseudo-RTL as:
2207
2208       if ((reg:SI) == 1)
2209         (set (reg:SI) (mem:SI (%fp - 7)))
2210       else
2211         (set (reg:QI) (mem:QI (%fp - 7)))
2212
2213    Now (mem:SI (%fp - 7)) is considered as not may_trap_p since it is a
2214    memory reference to a stack slot, but it will certainly cause a fault
2215    on a strict alignment machine.  */
2216
2217 int
2218 may_trap_or_fault_p (rtx x)
2219 {
2220   return may_trap_p_1 (x, true);
2221 }
2222 \f
2223 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2224    i.e., an inequality.  */
2225
2226 int
2227 inequality_comparisons_p (rtx x)
2228 {
2229   const char *fmt;
2230   int len, i;
2231   enum rtx_code code = GET_CODE (x);
2232
2233   switch (code)
2234     {
2235     case REG:
2236     case SCRATCH:
2237     case PC:
2238     case CC0:
2239     case CONST_INT:
2240     case CONST_DOUBLE:
2241     case CONST_VECTOR:
2242     case CONST:
2243     case LABEL_REF:
2244     case SYMBOL_REF:
2245       return 0;
2246
2247     case LT:
2248     case LTU:
2249     case GT:
2250     case GTU:
2251     case LE:
2252     case LEU:
2253     case GE:
2254     case GEU:
2255       return 1;
2256
2257     default:
2258       break;
2259     }
2260
2261   len = GET_RTX_LENGTH (code);
2262   fmt = GET_RTX_FORMAT (code);
2263
2264   for (i = 0; i < len; i++)
2265     {
2266       if (fmt[i] == 'e')
2267         {
2268           if (inequality_comparisons_p (XEXP (x, i)))
2269             return 1;
2270         }
2271       else if (fmt[i] == 'E')
2272         {
2273           int j;
2274           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2275             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2276               return 1;
2277         }
2278     }
2279
2280   return 0;
2281 }
2282 \f
2283 /* Replace any occurrence of FROM in X with TO.  The function does
2284    not enter into CONST_DOUBLE for the replace.
2285
2286    Note that copying is not done so X must not be shared unless all copies
2287    are to be modified.  */
2288
2289 rtx
2290 replace_rtx (rtx x, rtx from, rtx to)
2291 {
2292   int i, j;
2293   const char *fmt;
2294
2295   /* The following prevents loops occurrence when we change MEM in
2296      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2297   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2298     return x;
2299
2300   if (x == from)
2301     return to;
2302
2303   /* Allow this function to make replacements in EXPR_LISTs.  */
2304   if (x == 0)
2305     return 0;
2306
2307   if (GET_CODE (x) == SUBREG)
2308     {
2309       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2310
2311       if (GET_CODE (new) == CONST_INT)
2312         {
2313           x = simplify_subreg (GET_MODE (x), new,
2314                                GET_MODE (SUBREG_REG (x)),
2315                                SUBREG_BYTE (x));
2316           gcc_assert (x);
2317         }
2318       else
2319         SUBREG_REG (x) = new;
2320
2321       return x;
2322     }
2323   else if (GET_CODE (x) == ZERO_EXTEND)
2324     {
2325       rtx new = replace_rtx (XEXP (x, 0), from, to);
2326
2327       if (GET_CODE (new) == CONST_INT)
2328         {
2329           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2330                                         new, GET_MODE (XEXP (x, 0)));
2331           gcc_assert (x);
2332         }
2333       else
2334         XEXP (x, 0) = new;
2335
2336       return x;
2337     }
2338
2339   fmt = GET_RTX_FORMAT (GET_CODE (x));
2340   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2341     {
2342       if (fmt[i] == 'e')
2343         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2344       else if (fmt[i] == 'E')
2345         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2346           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2347     }
2348
2349   return x;
2350 }
2351 \f
2352 /* Throughout the rtx X, replace many registers according to REG_MAP.
2353    Return the replacement for X (which may be X with altered contents).
2354    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2355    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2356
2357    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2358    should not be mapped to pseudos or vice versa since validate_change
2359    is not called.
2360
2361    If REPLACE_DEST is 1, replacements are also done in destinations;
2362    otherwise, only sources are replaced.  */
2363
2364 rtx
2365 replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest)
2366 {
2367   enum rtx_code code;
2368   int i;
2369   const char *fmt;
2370
2371   if (x == 0)
2372     return x;
2373
2374   code = GET_CODE (x);
2375   switch (code)
2376     {
2377     case SCRATCH:
2378     case PC:
2379     case CC0:
2380     case CONST_INT:
2381     case CONST_DOUBLE:
2382     case CONST_VECTOR:
2383     case CONST:
2384     case SYMBOL_REF:
2385     case LABEL_REF:
2386       return x;
2387
2388     case REG:
2389       /* Verify that the register has an entry before trying to access it.  */
2390       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2391         {
2392           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2393              this replacement occurs more than once then each instance will
2394              get distinct rtx.  */
2395           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2396             return copy_rtx (reg_map[REGNO (x)]);
2397           return reg_map[REGNO (x)];
2398         }
2399       return x;
2400
2401     case SUBREG:
2402       /* Prevent making nested SUBREGs.  */
2403       if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs
2404           && reg_map[REGNO (SUBREG_REG (x))] != 0
2405           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2406         {
2407           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2408           return simplify_gen_subreg (GET_MODE (x), map_val,
2409                                       GET_MODE (SUBREG_REG (x)),
2410                                       SUBREG_BYTE (x));
2411         }
2412       break;
2413
2414     case SET:
2415       if (replace_dest)
2416         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2417
2418       else if (MEM_P (SET_DEST (x))
2419                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2420         /* Even if we are not to replace destinations, replace register if it
2421            is CONTAINED in destination (destination is memory or
2422            STRICT_LOW_PART).  */
2423         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2424                                                reg_map, nregs, 0);
2425       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2426         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2427         break;
2428
2429       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2430       return x;
2431
2432     default:
2433       break;
2434     }
2435
2436   fmt = GET_RTX_FORMAT (code);
2437   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2438     {
2439       if (fmt[i] == 'e')
2440         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2441       else if (fmt[i] == 'E')
2442         {
2443           int j;
2444           for (j = 0; j < XVECLEN (x, i); j++)
2445             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2446                                               nregs, replace_dest);
2447         }
2448     }
2449   return x;
2450 }
2451
2452 /* Replace occurrences of the old label in *X with the new one.
2453    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2454
2455 int
2456 replace_label (rtx *x, void *data)
2457 {
2458   rtx l = *x;
2459   rtx old_label = ((replace_label_data *) data)->r1;
2460   rtx new_label = ((replace_label_data *) data)->r2;
2461   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2462
2463   if (l == NULL_RTX)
2464     return 0;
2465
2466   if (GET_CODE (l) == SYMBOL_REF
2467       && CONSTANT_POOL_ADDRESS_P (l))
2468     {
2469       rtx c = get_pool_constant (l);
2470       if (rtx_referenced_p (old_label, c))
2471         {
2472           rtx new_c, new_l;
2473           replace_label_data *d = (replace_label_data *) data;
2474
2475           /* Create a copy of constant C; replace the label inside
2476              but do not update LABEL_NUSES because uses in constant pool
2477              are not counted.  */
2478           new_c = copy_rtx (c);
2479           d->update_label_nuses = false;
2480           for_each_rtx (&new_c, replace_label, data);
2481           d->update_label_nuses = update_label_nuses;
2482
2483           /* Add the new constant NEW_C to constant pool and replace
2484              the old reference to constant by new reference.  */
2485           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2486           *x = replace_rtx (l, l, new_l);
2487         }
2488       return 0;
2489     }
2490
2491   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2492      field.  This is not handled by for_each_rtx because it doesn't
2493      handle unprinted ('0') fields.  */
2494   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2495     JUMP_LABEL (l) = new_label;
2496
2497   if ((GET_CODE (l) == LABEL_REF
2498        || GET_CODE (l) == INSN_LIST)
2499       && XEXP (l, 0) == old_label)
2500     {
2501       XEXP (l, 0) = new_label;
2502       if (update_label_nuses)
2503         {
2504           ++LABEL_NUSES (new_label);
2505           --LABEL_NUSES (old_label);
2506         }
2507       return 0;
2508     }
2509
2510   return 0;
2511 }
2512
2513 /* When *BODY is equal to X or X is directly referenced by *BODY
2514    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2515    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2516
2517 static int
2518 rtx_referenced_p_1 (rtx *body, void *x)
2519 {
2520   rtx y = (rtx) x;
2521
2522   if (*body == NULL_RTX)
2523     return y == NULL_RTX;
2524
2525   /* Return true if a label_ref *BODY refers to label Y.  */
2526   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2527     return XEXP (*body, 0) == y;
2528
2529   /* If *BODY is a reference to pool constant traverse the constant.  */
2530   if (GET_CODE (*body) == SYMBOL_REF
2531       && CONSTANT_POOL_ADDRESS_P (*body))
2532     return rtx_referenced_p (y, get_pool_constant (*body));
2533
2534   /* By default, compare the RTL expressions.  */
2535   return rtx_equal_p (*body, y);
2536 }
2537
2538 /* Return true if X is referenced in BODY.  */
2539
2540 int
2541 rtx_referenced_p (rtx x, rtx body)
2542 {
2543   return for_each_rtx (&body, rtx_referenced_p_1, x);
2544 }
2545
2546 /* If INSN is a tablejump return true and store the label (before jump table) to
2547    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2548
2549 bool
2550 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2551 {
2552   rtx label, table;
2553
2554   if (JUMP_P (insn)
2555       && (label = JUMP_LABEL (insn)) != NULL_RTX
2556       && (table = next_active_insn (label)) != NULL_RTX
2557       && JUMP_P (table)
2558       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2559           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2560     {
2561       if (labelp)
2562         *labelp = label;
2563       if (tablep)
2564         *tablep = table;
2565       return true;
2566     }
2567   return false;
2568 }
2569
2570 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2571    constant that is not in the constant pool and not in the condition
2572    of an IF_THEN_ELSE.  */
2573
2574 static int
2575 computed_jump_p_1 (rtx x)
2576 {
2577   enum rtx_code code = GET_CODE (x);
2578   int i, j;
2579   const char *fmt;
2580
2581   switch (code)
2582     {
2583     case LABEL_REF:
2584     case PC:
2585       return 0;
2586
2587     case CONST:
2588     case CONST_INT:
2589     case CONST_DOUBLE:
2590     case CONST_VECTOR:
2591     case SYMBOL_REF:
2592     case REG:
2593       return 1;
2594
2595     case MEM:
2596       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2597                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2598
2599     case IF_THEN_ELSE:
2600       return (computed_jump_p_1 (XEXP (x, 1))
2601               || computed_jump_p_1 (XEXP (x, 2)));
2602
2603     default:
2604       break;
2605     }
2606
2607   fmt = GET_RTX_FORMAT (code);
2608   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2609     {
2610       if (fmt[i] == 'e'
2611           && computed_jump_p_1 (XEXP (x, i)))
2612         return 1;
2613
2614       else if (fmt[i] == 'E')
2615         for (j = 0; j < XVECLEN (x, i); j++)
2616           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2617             return 1;
2618     }
2619
2620   return 0;
2621 }
2622
2623 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2624
2625    Tablejumps and casesi insns are not considered indirect jumps;
2626    we can recognize them by a (use (label_ref)).  */
2627
2628 int
2629 computed_jump_p (rtx insn)
2630 {
2631   int i;
2632   if (JUMP_P (insn))
2633     {
2634       rtx pat = PATTERN (insn);
2635
2636       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2637         return 0;
2638       else if (GET_CODE (pat) == PARALLEL)
2639         {
2640           int len = XVECLEN (pat, 0);
2641           int has_use_labelref = 0;
2642
2643           for (i = len - 1; i >= 0; i--)
2644             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2645                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2646                     == LABEL_REF))
2647               has_use_labelref = 1;
2648
2649           if (! has_use_labelref)
2650             for (i = len - 1; i >= 0; i--)
2651               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2652                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2653                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2654                 return 1;
2655         }
2656       else if (GET_CODE (pat) == SET
2657                && SET_DEST (pat) == pc_rtx
2658                && computed_jump_p_1 (SET_SRC (pat)))
2659         return 1;
2660     }
2661   return 0;
2662 }
2663
2664 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2665    calls.  Processes the subexpressions of EXP and passes them to F.  */
2666 static int
2667 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2668 {
2669   int result, i, j;
2670   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2671   rtx *x;
2672
2673   for (; format[n] != '\0'; n++)
2674     {
2675       switch (format[n])
2676         {
2677         case 'e':
2678           /* Call F on X.  */
2679           x = &XEXP (exp, n);
2680           result = (*f) (x, data);
2681           if (result == -1)
2682             /* Do not traverse sub-expressions.  */
2683             continue;
2684           else if (result != 0)
2685             /* Stop the traversal.  */
2686             return result;
2687
2688           if (*x == NULL_RTX)
2689             /* There are no sub-expressions.  */
2690             continue;
2691
2692           i = non_rtx_starting_operands[GET_CODE (*x)];
2693           if (i >= 0)
2694             {
2695               result = for_each_rtx_1 (*x, i, f, data);
2696               if (result != 0)
2697                 return result;
2698             }
2699           break;
2700
2701         case 'V':
2702         case 'E':
2703           if (XVEC (exp, n) == 0)
2704             continue;
2705           for (j = 0; j < XVECLEN (exp, n); ++j)
2706             {
2707               /* Call F on X.  */
2708               x = &XVECEXP (exp, n, j);
2709               result = (*f) (x, data);
2710               if (result == -1)
2711                 /* Do not traverse sub-expressions.  */
2712                 continue;
2713               else if (result != 0)
2714                 /* Stop the traversal.  */
2715                 return result;
2716
2717               if (*x == NULL_RTX)
2718                 /* There are no sub-expressions.  */
2719                 continue;
2720
2721               i = non_rtx_starting_operands[GET_CODE (*x)];
2722               if (i >= 0)
2723                 {
2724                   result = for_each_rtx_1 (*x, i, f, data);
2725                   if (result != 0)
2726                     return result;
2727                 }
2728             }
2729           break;
2730
2731         default:
2732           /* Nothing to do.  */
2733           break;
2734         }
2735     }
2736
2737   return 0;
2738 }
2739
2740 /* Traverse X via depth-first search, calling F for each
2741    sub-expression (including X itself).  F is also passed the DATA.
2742    If F returns -1, do not traverse sub-expressions, but continue
2743    traversing the rest of the tree.  If F ever returns any other
2744    nonzero value, stop the traversal, and return the value returned
2745    by F.  Otherwise, return 0.  This function does not traverse inside
2746    tree structure that contains RTX_EXPRs, or into sub-expressions
2747    whose format code is `0' since it is not known whether or not those
2748    codes are actually RTL.
2749
2750    This routine is very general, and could (should?) be used to
2751    implement many of the other routines in this file.  */
2752
2753 int
2754 for_each_rtx (rtx *x, rtx_function f, void *data)
2755 {
2756   int result;
2757   int i;
2758
2759   /* Call F on X.  */
2760   result = (*f) (x, data);
2761   if (result == -1)
2762     /* Do not traverse sub-expressions.  */
2763     return 0;
2764   else if (result != 0)
2765     /* Stop the traversal.  */
2766     return result;
2767
2768   if (*x == NULL_RTX)
2769     /* There are no sub-expressions.  */
2770     return 0;
2771
2772   i = non_rtx_starting_operands[GET_CODE (*x)];
2773   if (i < 0)
2774     return 0;
2775
2776   return for_each_rtx_1 (*x, i, f, data);
2777 }
2778
2779
2780 /* Searches X for any reference to REGNO, returning the rtx of the
2781    reference found if any.  Otherwise, returns NULL_RTX.  */
2782
2783 rtx
2784 regno_use_in (unsigned int regno, rtx x)
2785 {
2786   const char *fmt;
2787   int i, j;
2788   rtx tem;
2789
2790   if (REG_P (x) && REGNO (x) == regno)
2791     return x;
2792
2793   fmt = GET_RTX_FORMAT (GET_CODE (x));
2794   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2795     {
2796       if (fmt[i] == 'e')
2797         {
2798           if ((tem = regno_use_in (regno, XEXP (x, i))))
2799             return tem;
2800         }
2801       else if (fmt[i] == 'E')
2802         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2803           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2804             return tem;
2805     }
2806
2807   return NULL_RTX;
2808 }
2809
2810 /* Return a value indicating whether OP, an operand of a commutative
2811    operation, is preferred as the first or second operand.  The higher
2812    the value, the stronger the preference for being the first operand.
2813    We use negative values to indicate a preference for the first operand
2814    and positive values for the second operand.  */
2815
2816 int
2817 commutative_operand_precedence (rtx op)
2818 {
2819   enum rtx_code code = GET_CODE (op);
2820
2821   /* Constants always come the second operand.  Prefer "nice" constants.  */
2822   if (code == CONST_INT)
2823     return -7;
2824   if (code == CONST_DOUBLE)
2825     return -6;
2826   op = avoid_constant_pool_reference (op);
2827   code = GET_CODE (op);
2828
2829   switch (GET_RTX_CLASS (code))
2830     {
2831     case RTX_CONST_OBJ:
2832       if (code == CONST_INT)
2833         return -5;
2834       if (code == CONST_DOUBLE)
2835         return -4;
2836       return -3;
2837
2838     case RTX_EXTRA:
2839       /* SUBREGs of objects should come second.  */
2840       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2841         return -2;
2842
2843       if (!CONSTANT_P (op))
2844         return 0;
2845       else
2846         /* As for RTX_CONST_OBJ.  */
2847         return -3;
2848
2849     case RTX_OBJ:
2850       /* Complex expressions should be the first, so decrease priority
2851          of objects.  */
2852       return -1;
2853
2854     case RTX_COMM_ARITH:
2855       /* Prefer operands that are themselves commutative to be first.
2856          This helps to make things linear.  In particular,
2857          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2858       return 4;
2859
2860     case RTX_BIN_ARITH:
2861       /* If only one operand is a binary expression, it will be the first
2862          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2863          is canonical, although it will usually be further simplified.  */
2864       return 2;
2865
2866     case RTX_UNARY:
2867       /* Then prefer NEG and NOT.  */
2868       if (code == NEG || code == NOT)
2869         return 1;
2870
2871     default:
2872       return 0;
2873     }
2874 }
2875
2876 /* Return 1 iff it is necessary to swap operands of commutative operation
2877    in order to canonicalize expression.  */
2878
2879 int
2880 swap_commutative_operands_p (rtx x, rtx y)
2881 {
2882   return (commutative_operand_precedence (x)
2883           < commutative_operand_precedence (y));
2884 }
2885
2886 /* Return 1 if X is an autoincrement side effect and the register is
2887    not the stack pointer.  */
2888 int
2889 auto_inc_p (rtx x)
2890 {
2891   switch (GET_CODE (x))
2892     {
2893     case PRE_INC:
2894     case POST_INC:
2895     case PRE_DEC:
2896     case POST_DEC:
2897     case PRE_MODIFY:
2898     case POST_MODIFY:
2899       /* There are no REG_INC notes for SP.  */
2900       if (XEXP (x, 0) != stack_pointer_rtx)
2901         return 1;
2902     default:
2903       break;
2904     }
2905   return 0;
2906 }
2907
2908 /* Return 1 if the sequence of instructions beginning with FROM and up
2909    to and including TO is safe to move.  If NEW_TO is non-NULL, and
2910    the sequence is not already safe to move, but can be easily
2911    extended to a sequence which is safe, then NEW_TO will point to the
2912    end of the extended sequence.
2913
2914    For now, this function only checks that the region contains whole
2915    exception regions, but it could be extended to check additional
2916    conditions as well.  */
2917
2918 int
2919 insns_safe_to_move_p (rtx from, rtx to, rtx *new_to)
2920 {
2921   int eh_region_count = 0;
2922   int past_to_p = 0;
2923   rtx r = from;
2924
2925   /* By default, assume the end of the region will be what was
2926      suggested.  */
2927   if (new_to)
2928     *new_to = to;
2929
2930   while (r)
2931     {
2932       if (NOTE_P (r))
2933         {
2934           switch (NOTE_LINE_NUMBER (r))
2935             {
2936             case NOTE_INSN_EH_REGION_BEG:
2937               ++eh_region_count;
2938               break;
2939
2940             case NOTE_INSN_EH_REGION_END:
2941               if (eh_region_count == 0)
2942                 /* This sequence of instructions contains the end of
2943                    an exception region, but not he beginning.  Moving
2944                    it will cause chaos.  */
2945                 return 0;
2946
2947               --eh_region_count;
2948               break;
2949
2950             default:
2951               break;
2952             }
2953         }
2954       else if (past_to_p)
2955         /* If we've passed TO, and we see a non-note instruction, we
2956            can't extend the sequence to a movable sequence.  */
2957         return 0;
2958
2959       if (r == to)
2960         {
2961           if (!new_to)
2962             /* It's OK to move the sequence if there were matched sets of
2963                exception region notes.  */
2964             return eh_region_count == 0;
2965
2966           past_to_p = 1;
2967         }
2968
2969       /* It's OK to move the sequence if there were matched sets of
2970          exception region notes.  */
2971       if (past_to_p && eh_region_count == 0)
2972         {
2973           *new_to = r;
2974           return 1;
2975         }
2976
2977       /* Go to the next instruction.  */
2978       r = NEXT_INSN (r);
2979     }
2980
2981   return 0;
2982 }
2983
2984 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2985 int
2986 loc_mentioned_in_p (rtx *loc, rtx in)
2987 {
2988   enum rtx_code code = GET_CODE (in);
2989   const char *fmt = GET_RTX_FORMAT (code);
2990   int i, j;
2991
2992   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2993     {
2994       if (loc == &in->u.fld[i].rt_rtx)
2995         return 1;
2996       if (fmt[i] == 'e')
2997         {
2998           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2999             return 1;
3000         }
3001       else if (fmt[i] == 'E')
3002         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
3003           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3004             return 1;
3005     }
3006   return 0;
3007 }
3008
3009 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
3010    and SUBREG_BYTE, return the bit offset where the subreg begins
3011    (counting from the least significant bit of the operand).  */
3012
3013 unsigned int
3014 subreg_lsb_1 (enum machine_mode outer_mode,
3015               enum machine_mode inner_mode,
3016               unsigned int subreg_byte)
3017 {
3018   unsigned int bitpos;
3019   unsigned int byte;
3020   unsigned int word;
3021
3022   /* A paradoxical subreg begins at bit position 0.  */
3023   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
3024     return 0;
3025
3026   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3027     /* If the subreg crosses a word boundary ensure that
3028        it also begins and ends on a word boundary.  */
3029     gcc_assert (!((subreg_byte % UNITS_PER_WORD
3030                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
3031                   && (subreg_byte % UNITS_PER_WORD
3032                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
3033
3034   if (WORDS_BIG_ENDIAN)
3035     word = (GET_MODE_SIZE (inner_mode)
3036             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3037   else
3038     word = subreg_byte / UNITS_PER_WORD;
3039   bitpos = word * BITS_PER_WORD;
3040
3041   if (BYTES_BIG_ENDIAN)
3042     byte = (GET_MODE_SIZE (inner_mode)
3043             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3044   else
3045     byte = subreg_byte % UNITS_PER_WORD;
3046   bitpos += byte * BITS_PER_UNIT;
3047
3048   return bitpos;
3049 }
3050
3051 /* Given a subreg X, return the bit offset where the subreg begins
3052    (counting from the least significant bit of the reg).  */
3053
3054 unsigned int
3055 subreg_lsb (rtx x)
3056 {
3057   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3058                        SUBREG_BYTE (x));
3059 }
3060
3061 /* This function returns the regno offset of a subreg expression.
3062    xregno - A regno of an inner hard subreg_reg (or what will become one).
3063    xmode  - The mode of xregno.
3064    offset - The byte offset.
3065    ymode  - The mode of a top level SUBREG (or what may become one).
3066    RETURN - The regno offset which would be used.  */
3067 unsigned int
3068 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3069                      unsigned int offset, enum machine_mode ymode)
3070 {
3071   int nregs_xmode, nregs_ymode, nregs_xmode_unit_int;
3072   int mode_multiple, nregs_multiple;
3073   int y_offset;
3074   enum machine_mode xmode_unit, xmode_unit_int;
3075
3076   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3077
3078   if (GET_MODE_INNER (xmode) == VOIDmode)
3079     xmode_unit = xmode;
3080   else
3081     xmode_unit = GET_MODE_INNER (xmode);
3082
3083   if (FLOAT_MODE_P (xmode_unit))
3084     {
3085       xmode_unit_int = int_mode_for_mode (xmode_unit);
3086       if (xmode_unit_int == BLKmode)
3087         /* It's probably bad to be here; a port should have an integer mode
3088            that's the same size as anything of which it takes a SUBREG.  */
3089         xmode_unit_int = xmode_unit;
3090     }
3091   else
3092     xmode_unit_int = xmode_unit;
3093
3094   nregs_xmode_unit_int = hard_regno_nregs[xregno][xmode_unit_int];
3095
3096   /* Adjust nregs_xmode to allow for 'holes'.  */
3097   if (nregs_xmode_unit_int != hard_regno_nregs[xregno][xmode_unit])
3098     nregs_xmode = nregs_xmode_unit_int * GET_MODE_NUNITS (xmode);
3099   else
3100     nregs_xmode = hard_regno_nregs[xregno][xmode];
3101
3102   nregs_ymode = hard_regno_nregs[xregno][ymode];
3103
3104   /* If this is a big endian paradoxical subreg, which uses more actual
3105      hard registers than the original register, we must return a negative
3106      offset so that we find the proper highpart of the register.  */
3107   if (offset == 0
3108       && nregs_ymode > nregs_xmode
3109       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3110           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3111     return nregs_xmode - nregs_ymode;
3112
3113   if (offset == 0 || nregs_xmode == nregs_ymode)
3114     return 0;
3115
3116   /* Size of ymode must not be greater than the size of xmode.  */
3117   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3118   gcc_assert (mode_multiple != 0);
3119
3120   y_offset = offset / GET_MODE_SIZE (ymode);
3121   nregs_multiple =  nregs_xmode / nregs_ymode;
3122   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3123 }
3124
3125 /* This function returns true when the offset is representable via
3126    subreg_offset in the given regno.
3127    xregno - A regno of an inner hard subreg_reg (or what will become one).
3128    xmode  - The mode of xregno.
3129    offset - The byte offset.
3130    ymode  - The mode of a top level SUBREG (or what may become one).
3131    RETURN - Whether the offset is representable.  */
3132 bool
3133 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3134                                unsigned int offset, enum machine_mode ymode)
3135 {
3136   int nregs_xmode, nregs_ymode, nregs_xmode_unit, nregs_xmode_unit_int;
3137   int mode_multiple, nregs_multiple;
3138   int y_offset;
3139   enum machine_mode xmode_unit, xmode_unit_int;
3140
3141   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3142
3143   if (GET_MODE_INNER (xmode) == VOIDmode)
3144     xmode_unit = xmode;
3145   else
3146     xmode_unit = GET_MODE_INNER (xmode);
3147
3148   if (FLOAT_MODE_P (xmode_unit))
3149     {
3150       xmode_unit_int = int_mode_for_mode (xmode_unit);
3151       if (xmode_unit_int == BLKmode)
3152         /* It's probably bad to be here; a port should have an integer mode
3153            that's the same size as anything of which it takes a SUBREG.  */
3154         xmode_unit_int = xmode_unit;
3155     }
3156   else
3157     xmode_unit_int = xmode_unit;
3158
3159   nregs_xmode_unit = hard_regno_nregs[xregno][xmode_unit];
3160   nregs_xmode_unit_int = hard_regno_nregs[xregno][xmode_unit_int];
3161
3162   /* If there are holes in a non-scalar mode in registers, we expect
3163      that it is made up of its units concatenated together.  */
3164   if (nregs_xmode_unit != nregs_xmode_unit_int)
3165     {
3166       gcc_assert (nregs_xmode_unit * GET_MODE_NUNITS (xmode)
3167                   == hard_regno_nregs[xregno][xmode]);
3168
3169       /* You can only ask for a SUBREG of a value with holes in the middle
3170          if you don't cross the holes.  (Such a SUBREG should be done by
3171          picking a different register class, or doing it in memory if
3172          necessary.)  An example of a value with holes is XCmode on 32-bit
3173          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
3174          3 for each part, but in memory it's two 128-bit parts.
3175          Padding is assumed to be at the end (not necessarily the 'high part')
3176          of each unit.  */
3177       if (nregs_xmode_unit != nregs_xmode_unit_int
3178           && (offset / GET_MODE_SIZE (xmode_unit_int) + 1
3179               < GET_MODE_NUNITS (xmode))
3180           && (offset / GET_MODE_SIZE (xmode_unit_int)
3181               != ((offset + GET_MODE_SIZE (ymode) - 1)
3182                   / GET_MODE_SIZE (xmode_unit_int))))
3183         return false;
3184
3185       nregs_xmode = nregs_xmode_unit_int * GET_MODE_NUNITS (xmode);
3186     }
3187   else
3188     nregs_xmode = hard_regno_nregs[xregno][xmode];
3189
3190   nregs_ymode = hard_regno_nregs[xregno][ymode];
3191
3192   /* Paradoxical subregs are otherwise valid.  */
3193   if (offset == 0
3194       && nregs_ymode > nregs_xmode
3195       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3196           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3197     return true;
3198
3199   /* Lowpart subregs are otherwise valid.  */
3200   if (offset == subreg_lowpart_offset (ymode, xmode))
3201     return true;
3202
3203   /* This should always pass, otherwise we don't know how to verify
3204      the constraint.  These conditions may be relaxed but
3205      subreg_regno_offset would need to be redesigned.  */
3206   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3207   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3208
3209   /* The XMODE value can be seen as a vector of NREGS_XMODE
3210      values.  The subreg must represent a lowpart of given field.
3211      Compute what field it is.  */
3212   offset -= subreg_lowpart_offset (ymode,
3213                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3214                                                   / nregs_xmode,
3215                                                   MODE_INT, 0));
3216
3217   /* Size of ymode must not be greater than the size of xmode.  */
3218   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3219   gcc_assert (mode_multiple != 0);
3220
3221   y_offset = offset / GET_MODE_SIZE (ymode);
3222   nregs_multiple =  nregs_xmode / nregs_ymode;
3223
3224   gcc_assert ((offset % GET_MODE_SIZE (ymode)) == 0);
3225   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3226
3227   return (!(y_offset % (mode_multiple / nregs_multiple)));
3228 }
3229
3230 /* Return the final regno that a subreg expression refers to.  */
3231 unsigned int
3232 subreg_regno (rtx x)
3233 {
3234   unsigned int ret;
3235   rtx subreg = SUBREG_REG (x);
3236   int regno = REGNO (subreg);
3237
3238   ret = regno + subreg_regno_offset (regno,
3239                                      GET_MODE (subreg),
3240                                      SUBREG_BYTE (x),
3241                                      GET_MODE (x));
3242   return ret;
3243
3244 }
3245 struct parms_set_data
3246 {
3247   int nregs;
3248   HARD_REG_SET regs;
3249 };
3250
3251 /* Helper function for noticing stores to parameter registers.  */
3252 static void
3253 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3254 {
3255   struct parms_set_data *d = data;
3256   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3257       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3258     {
3259       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3260       d->nregs--;
3261     }
3262 }
3263
3264 /* Look backward for first parameter to be loaded.
3265    Note that loads of all parameters will not necessarily be
3266    found if CSE has eliminated some of them (e.g., an argument
3267    to the outer function is passed down as a parameter).
3268    Do not skip BOUNDARY.  */
3269 rtx
3270 find_first_parameter_load (rtx call_insn, rtx boundary)
3271 {
3272   struct parms_set_data parm;
3273   rtx p, before, first_set;
3274
3275   /* Since different machines initialize their parameter registers
3276      in different orders, assume nothing.  Collect the set of all
3277      parameter registers.  */
3278   CLEAR_HARD_REG_SET (parm.regs);
3279   parm.nregs = 0;
3280   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3281     if (GET_CODE (XEXP (p, 0)) == USE
3282         && REG_P (XEXP (XEXP (p, 0), 0)))
3283       {
3284         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3285
3286         /* We only care about registers which can hold function
3287            arguments.  */
3288         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3289           continue;
3290
3291         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3292         parm.nregs++;
3293       }
3294   before = call_insn;
3295   first_set = call_insn;
3296
3297   /* Search backward for the first set of a register in this set.  */
3298   while (parm.nregs && before != boundary)
3299     {
3300       before = PREV_INSN (before);
3301
3302       /* It is possible that some loads got CSEed from one call to
3303          another.  Stop in that case.  */
3304       if (CALL_P (before))
3305         break;
3306
3307       /* Our caller needs either ensure that we will find all sets
3308          (in case code has not been optimized yet), or take care
3309          for possible labels in a way by setting boundary to preceding
3310          CODE_LABEL.  */
3311       if (LABEL_P (before))
3312         {
3313           gcc_assert (before == boundary);
3314           break;
3315         }
3316
3317       if (INSN_P (before))
3318         {
3319           int nregs_old = parm.nregs;
3320           note_stores (PATTERN (before), parms_set, &parm);
3321           /* If we found something that did not set a parameter reg,
3322              we're done.  Do not keep going, as that might result
3323              in hoisting an insn before the setting of a pseudo
3324              that is used by the hoisted insn. */
3325           if (nregs_old != parm.nregs)
3326             first_set = before;
3327           else
3328             break;
3329         }
3330     }
3331   return first_set;
3332 }
3333
3334 /* Return true if we should avoid inserting code between INSN and preceding
3335    call instruction.  */
3336
3337 bool
3338 keep_with_call_p (rtx insn)
3339 {
3340   rtx set;
3341
3342   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3343     {
3344       if (REG_P (SET_DEST (set))
3345           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3346           && fixed_regs[REGNO (SET_DEST (set))]
3347           && general_operand (SET_SRC (set), VOIDmode))
3348         return true;
3349       if (REG_P (SET_SRC (set))
3350           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3351           && REG_P (SET_DEST (set))
3352           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3353         return true;
3354       /* There may be a stack pop just after the call and before the store
3355          of the return register.  Search for the actual store when deciding
3356          if we can break or not.  */
3357       if (SET_DEST (set) == stack_pointer_rtx)
3358         {
3359           rtx i2 = next_nonnote_insn (insn);
3360           if (i2 && keep_with_call_p (i2))
3361             return true;
3362         }
3363     }
3364   return false;
3365 }
3366
3367 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3368    to non-complex jumps.  That is, direct unconditional, conditional,
3369    and tablejumps, but not computed jumps or returns.  It also does
3370    not apply to the fallthru case of a conditional jump.  */
3371
3372 bool
3373 label_is_jump_target_p (rtx label, rtx jump_insn)
3374 {
3375   rtx tmp = JUMP_LABEL (jump_insn);
3376
3377   if (label == tmp)
3378     return true;
3379
3380   if (tablejump_p (jump_insn, NULL, &tmp))
3381     {
3382       rtvec vec = XVEC (PATTERN (tmp),
3383                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3384       int i, veclen = GET_NUM_ELEM (vec);
3385
3386       for (i = 0; i < veclen; ++i)
3387         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3388           return true;
3389     }
3390
3391   return false;
3392 }
3393
3394 \f
3395 /* Return an estimate of the cost of computing rtx X.
3396    One use is in cse, to decide which expression to keep in the hash table.
3397    Another is in rtl generation, to pick the cheapest way to multiply.
3398    Other uses like the latter are expected in the future.  */
3399
3400 int
3401 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3402 {
3403   int i, j;
3404   enum rtx_code code;
3405   const char *fmt;
3406   int total;
3407
3408   if (x == 0)
3409     return 0;
3410
3411   /* Compute the default costs of certain things.
3412      Note that targetm.rtx_costs can override the defaults.  */
3413
3414   code = GET_CODE (x);
3415   switch (code)
3416     {
3417     case MULT:
3418       total = COSTS_N_INSNS (5);
3419       break;
3420     case DIV:
3421     case UDIV:
3422     case MOD:
3423     case UMOD:
3424       total = COSTS_N_INSNS (7);
3425       break;
3426     case USE:
3427       /* Used in loop.c and combine.c as a marker.  */
3428       total = 0;
3429       break;
3430     default:
3431       total = COSTS_N_INSNS (1);
3432     }
3433
3434   switch (code)
3435     {
3436     case REG:
3437       return 0;
3438
3439     case SUBREG:
3440       total = 0;
3441       /* If we can't tie these modes, make this expensive.  The larger
3442          the mode, the more expensive it is.  */
3443       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3444         return COSTS_N_INSNS (2
3445                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3446       break;
3447
3448     default:
3449       if (targetm.rtx_costs (x, code, outer_code, &total))
3450         return total;
3451       break;
3452     }
3453
3454   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3455      which is already in total.  */
3456
3457   fmt = GET_RTX_FORMAT (code);
3458   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3459     if (fmt[i] == 'e')
3460       total += rtx_cost (XEXP (x, i), code);
3461     else if (fmt[i] == 'E')
3462       for (j = 0; j < XVECLEN (x, i); j++)
3463         total += rtx_cost (XVECEXP (x, i, j), code);
3464
3465   return total;
3466 }
3467 \f
3468 /* Return cost of address expression X.
3469    Expect that X is properly formed address reference.  */
3470
3471 int
3472 address_cost (rtx x, enum machine_mode mode)
3473 {
3474   /* We may be asked for cost of various unusual addresses, such as operands
3475      of push instruction.  It is not worthwhile to complicate writing
3476      of the target hook by such cases.  */
3477
3478   if (!memory_address_p (mode, x))
3479     return 1000;
3480
3481   return targetm.address_cost (x);
3482 }
3483
3484 /* If the target doesn't override, compute the cost as with arithmetic.  */
3485
3486 int
3487 default_address_cost (rtx x)
3488 {
3489   return rtx_cost (x, MEM);
3490 }
3491 \f
3492
3493 unsigned HOST_WIDE_INT
3494 nonzero_bits (rtx x, enum machine_mode mode)
3495 {
3496   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3497 }
3498
3499 unsigned int
3500 num_sign_bit_copies (rtx x, enum machine_mode mode)
3501 {
3502   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3503 }
3504
3505 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3506    It avoids exponential behavior in nonzero_bits1 when X has
3507    identical subexpressions on the first or the second level.  */
3508
3509 static unsigned HOST_WIDE_INT
3510 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3511                      enum machine_mode known_mode,
3512                      unsigned HOST_WIDE_INT known_ret)
3513 {
3514   if (x == known_x && mode == known_mode)
3515     return known_ret;
3516
3517   /* Try to find identical subexpressions.  If found call
3518      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3519      precomputed value for the subexpression as KNOWN_RET.  */
3520
3521   if (ARITHMETIC_P (x))
3522     {
3523       rtx x0 = XEXP (x, 0);
3524       rtx x1 = XEXP (x, 1);
3525
3526       /* Check the first level.  */
3527       if (x0 == x1)
3528         return nonzero_bits1 (x, mode, x0, mode,
3529                               cached_nonzero_bits (x0, mode, known_x,
3530                                                    known_mode, known_ret));
3531
3532       /* Check the second level.  */
3533       if (ARITHMETIC_P (x0)
3534           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3535         return nonzero_bits1 (x, mode, x1, mode,
3536                               cached_nonzero_bits (x1, mode, known_x,
3537                                                    known_mode, known_ret));
3538
3539       if (ARITHMETIC_P (x1)
3540           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3541         return nonzero_bits1 (x, mode, x0, mode,
3542                               cached_nonzero_bits (x0, mode, known_x,
3543                                                    known_mode, known_ret));
3544     }
3545
3546   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3547 }
3548
3549 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3550    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3551    is less useful.  We can't allow both, because that results in exponential
3552    run time recursion.  There is a nullstone testcase that triggered
3553    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3554 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3555
3556 /* Given an expression, X, compute which bits in X can be nonzero.
3557    We don't care about bits outside of those defined in MODE.
3558
3559    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3560    an arithmetic operation, we can do better.  */
3561
3562 static unsigned HOST_WIDE_INT
3563 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3564                enum machine_mode known_mode,
3565                unsigned HOST_WIDE_INT known_ret)
3566 {
3567   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3568   unsigned HOST_WIDE_INT inner_nz;
3569   enum rtx_code code;
3570   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3571
3572   /* For floating-point values, assume all bits are needed.  */
3573   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3574     return nonzero;
3575
3576   /* If X is wider than MODE, use its mode instead.  */
3577   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3578     {
3579       mode = GET_MODE (x);
3580       nonzero = GET_MODE_MASK (mode);
3581       mode_width = GET_MODE_BITSIZE (mode);
3582     }
3583
3584   if (mode_width > HOST_BITS_PER_WIDE_INT)
3585     /* Our only callers in this case look for single bit values.  So
3586        just return the mode mask.  Those tests will then be false.  */
3587     return nonzero;
3588
3589 #ifndef WORD_REGISTER_OPERATIONS
3590   /* If MODE is wider than X, but both are a single word for both the host
3591      and target machines, we can compute this from which bits of the
3592      object might be nonzero in its own mode, taking into account the fact
3593      that on many CISC machines, accessing an object in a wider mode
3594      causes the high-order bits to become undefined.  So they are
3595      not known to be zero.  */
3596
3597   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3598       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3599       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3600       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3601     {
3602       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3603                                       known_x, known_mode, known_ret);
3604       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3605       return nonzero;
3606     }
3607 #endif
3608
3609   code = GET_CODE (x);
3610   switch (code)
3611     {
3612     case REG:
3613 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3614       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3615          all the bits above ptr_mode are known to be zero.  */
3616       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3617           && REG_POINTER (x))
3618         nonzero &= GET_MODE_MASK (ptr_mode);
3619 #endif
3620
3621       /* Include declared information about alignment of pointers.  */
3622       /* ??? We don't properly preserve REG_POINTER changes across
3623          pointer-to-integer casts, so we can't trust it except for
3624          things that we know must be pointers.  See execute/960116-1.c.  */
3625       if ((x == stack_pointer_rtx
3626            || x == frame_pointer_rtx
3627            || x == arg_pointer_rtx)
3628           && REGNO_POINTER_ALIGN (REGNO (x)))
3629         {
3630           unsigned HOST_WIDE_INT alignment
3631             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3632
3633 #ifdef PUSH_ROUNDING
3634           /* If PUSH_ROUNDING is defined, it is possible for the
3635              stack to be momentarily aligned only to that amount,
3636              so we pick the least alignment.  */
3637           if (x == stack_pointer_rtx && PUSH_ARGS)
3638             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3639                              alignment);
3640 #endif
3641
3642           nonzero &= ~(alignment - 1);
3643         }
3644
3645       {
3646         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3647         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3648                                               known_mode, known_ret,
3649                                               &nonzero_for_hook);
3650
3651         if (new)
3652           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3653                                                    known_mode, known_ret);
3654
3655         return nonzero_for_hook;
3656       }
3657
3658     case CONST_INT:
3659 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3660       /* If X is negative in MODE, sign-extend the value.  */
3661       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3662           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3663         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3664 #endif
3665
3666       return INTVAL (x);
3667
3668     case MEM:
3669 #ifdef LOAD_EXTEND_OP
3670       /* In many, if not most, RISC machines, reading a byte from memory
3671          zeros the rest of the register.  Noticing that fact saves a lot
3672          of extra zero-extends.  */
3673       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3674         nonzero &= GET_MODE_MASK (GET_MODE (x));
3675 #endif
3676       break;
3677
3678     case EQ:  case NE:
3679     case UNEQ:  case LTGT:
3680     case GT:  case GTU:  case UNGT:
3681     case LT:  case LTU:  case UNLT:
3682     case GE:  case GEU:  case UNGE:
3683     case LE:  case LEU:  case UNLE:
3684     case UNORDERED: case ORDERED:
3685       /* If this produces an integer result, we know which bits are set.
3686          Code here used to clear bits outside the mode of X, but that is
3687          now done above.  */
3688       /* Mind that MODE is the mode the caller wants to look at this
3689          operation in, and not the actual operation mode.  We can wind
3690          up with (subreg:DI (gt:V4HI x y)), and we don't have anything
3691          that describes the results of a vector compare.  */
3692       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
3693           && mode_width <= HOST_BITS_PER_WIDE_INT)
3694         nonzero = STORE_FLAG_VALUE;
3695       break;
3696
3697     case NEG:
3698 #if 0
3699       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3700          and num_sign_bit_copies.  */
3701       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3702           == GET_MODE_BITSIZE (GET_MODE (x)))
3703         nonzero = 1;
3704 #endif
3705
3706       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3707         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3708       break;
3709
3710     case ABS:
3711 #if 0
3712       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3713          and num_sign_bit_copies.  */
3714       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3715           == GET_MODE_BITSIZE (GET_MODE (x)))
3716         nonzero = 1;
3717 #endif
3718       break;
3719
3720     case TRUNCATE:
3721       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
3722                                        known_x, known_mode, known_ret)
3723                   & GET_MODE_MASK (mode));
3724       break;
3725
3726     case ZERO_EXTEND:
3727       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3728                                       known_x, known_mode, known_ret);
3729       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3730         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3731       break;
3732
3733     case SIGN_EXTEND:
3734       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
3735          Otherwise, show all the bits in the outer mode but not the inner
3736          may be nonzero.  */
3737       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
3738                                       known_x, known_mode, known_ret);
3739       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3740         {
3741           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3742           if (inner_nz
3743               & (((HOST_WIDE_INT) 1
3744                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
3745             inner_nz |= (GET_MODE_MASK (mode)
3746                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
3747         }
3748
3749       nonzero &= inner_nz;
3750       break;
3751
3752     case AND:
3753       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3754                                        known_x, known_mode, known_ret)
3755                  & cached_nonzero_bits (XEXP (x, 1), mode,
3756                                         known_x, known_mode, known_ret);
3757       break;
3758
3759     case XOR:   case IOR:
3760     case UMIN:  case UMAX:  case SMIN:  case SMAX:
3761       {
3762         unsigned HOST_WIDE_INT nonzero0 =
3763           cached_nonzero_bits (XEXP (x, 0), mode,
3764                                known_x, known_mode, known_ret);
3765
3766         /* Don't call nonzero_bits for the second time if it cannot change
3767            anything.  */
3768         if ((nonzero & nonzero0) != nonzero)
3769           nonzero &= nonzero0
3770                      | cached_nonzero_bits (XEXP (x, 1), mode,
3771                                             known_x, known_mode, known_ret);
3772       }
3773       break;
3774
3775     case PLUS:  case MINUS:
3776     case MULT:
3777     case DIV:   case UDIV:
3778     case MOD:   case UMOD:
3779       /* We can apply the rules of arithmetic to compute the number of
3780          high- and low-order zero bits of these operations.  We start by
3781          computing the width (position of the highest-order nonzero bit)
3782          and the number of low-order zero bits for each value.  */
3783       {
3784         unsigned HOST_WIDE_INT nz0 =
3785           cached_nonzero_bits (XEXP (x, 0), mode,
3786                                known_x, known_mode, known_ret);
3787         unsigned HOST_WIDE_INT nz1 =
3788           cached_nonzero_bits (XEXP (x, 1), mode,
3789                                known_x, known_mode, known_ret);
3790         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
3791         int width0 = floor_log2 (nz0) + 1;
3792         int width1 = floor_log2 (nz1) + 1;
3793         int low0 = floor_log2 (nz0 & -nz0);
3794         int low1 = floor_log2 (nz1 & -nz1);
3795         HOST_WIDE_INT op0_maybe_minusp
3796           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
3797         HOST_WIDE_INT op1_maybe_minusp
3798           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
3799         unsigned int result_width = mode_width;
3800         int result_low = 0;
3801
3802         switch (code)
3803           {
3804           case PLUS:
3805             result_width = MAX (width0, width1) + 1;
3806             result_low = MIN (low0, low1);
3807             break;
3808           case MINUS:
3809             result_low = MIN (low0, low1);
3810             break;
3811           case MULT:
3812             result_width = width0 + width1;
3813             result_low = low0 + low1;
3814             break;
3815           case DIV:
3816             if (width1 == 0)
3817               break;
3818             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3819               result_width = width0;
3820             break;
3821           case UDIV:
3822             if (width1 == 0)
3823               break;
3824             result_width = width0;
3825             break;
3826           case MOD:
3827             if (width1 == 0)
3828               break;
3829             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3830               result_width = MIN (width0, width1);
3831             result_low = MIN (low0, low1);
3832             break;
3833           case UMOD:
3834             if (width1 == 0)
3835               break;
3836             result_width = MIN (width0, width1);
3837             result_low = MIN (low0, low1);
3838             break;
3839           default:
3840             gcc_unreachable ();
3841           }
3842
3843         if (result_width < mode_width)
3844           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
3845
3846         if (result_low > 0)
3847           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
3848
3849 #ifdef POINTERS_EXTEND_UNSIGNED
3850         /* If pointers extend unsigned and this is an addition or subtraction
3851            to a pointer in Pmode, all the bits above ptr_mode are known to be
3852            zero.  */
3853         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
3854             && (code == PLUS || code == MINUS)
3855             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
3856           nonzero &= GET_MODE_MASK (ptr_mode);
3857 #endif
3858       }
3859       break;
3860
3861     case ZERO_EXTRACT:
3862       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3863           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3864         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
3865       break;
3866
3867     case SUBREG:
3868       /* If this is a SUBREG formed for a promoted variable that has
3869          been zero-extended, we know that at least the high-order bits
3870          are zero, though others might be too.  */
3871
3872       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
3873         nonzero = GET_MODE_MASK (GET_MODE (x))
3874                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
3875                                          known_x, known_mode, known_ret);
3876
3877       /* If the inner mode is a single word for both the host and target
3878          machines, we can compute this from which bits of the inner
3879          object might be nonzero.  */
3880       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
3881           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
3882               <= HOST_BITS_PER_WIDE_INT))
3883         {
3884           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
3885                                           known_x, known_mode, known_ret);
3886
3887 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
3888           /* If this is a typical RISC machine, we only have to worry
3889              about the way loads are extended.  */
3890           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
3891                ? (((nonzero
3892                     & (((unsigned HOST_WIDE_INT) 1
3893                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
3894                    != 0))
3895                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
3896               || !MEM_P (SUBREG_REG (x)))
3897 #endif
3898             {
3899               /* On many CISC machines, accessing an object in a wider mode
3900                  causes the high-order bits to become undefined.  So they are
3901                  not known to be zero.  */
3902               if (GET_MODE_SIZE (GET_MODE (x))
3903                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3904                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
3905                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
3906             }
3907         }
3908       break;
3909
3910     case ASHIFTRT:
3911     case LSHIFTRT:
3912     case ASHIFT:
3913     case ROTATE:
3914       /* The nonzero bits are in two classes: any bits within MODE
3915          that aren't in GET_MODE (x) are always significant.  The rest of the
3916          nonzero bits are those that are significant in the operand of
3917          the shift when shifted the appropriate number of bits.  This
3918          shows that high-order bits are cleared by the right shift and
3919          low-order bits by left shifts.  */
3920       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3921           && INTVAL (XEXP (x, 1)) >= 0
3922           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3923         {
3924           enum machine_mode inner_mode = GET_MODE (x);
3925           unsigned int width = GET_MODE_BITSIZE (inner_mode);
3926           int count = INTVAL (XEXP (x, 1));
3927           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
3928           unsigned HOST_WIDE_INT op_nonzero =
3929             cached_nonzero_bits (XEXP (x, 0), mode,
3930                                  known_x, known_mode, known_ret);
3931           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
3932           unsigned HOST_WIDE_INT outer = 0;
3933
3934           if (mode_width > width)
3935             outer = (op_nonzero & nonzero & ~mode_mask);
3936
3937           if (code == LSHIFTRT)
3938             inner >>= count;
3939           else if (code == ASHIFTRT)
3940             {
3941               inner >>= count;
3942
3943               /* If the sign bit may have been nonzero before the shift, we
3944                  need to mark all the places it could have been copied to
3945                  by the shift as possibly nonzero.  */
3946               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
3947                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
3948             }
3949           else if (code == ASHIFT)
3950             inner <<= count;
3951           else
3952             inner = ((inner << (count % width)
3953                       | (inner >> (width - (count % width)))) & mode_mask);
3954
3955           nonzero &= (outer | inner);
3956         }
3957       break;
3958
3959     case FFS:
3960     case POPCOUNT:
3961       /* This is at most the number of bits in the mode.  */
3962       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
3963       break;
3964
3965     case CLZ:
3966       /* If CLZ has a known value at zero, then the nonzero bits are
3967          that value, plus the number of bits in the mode minus one.  */
3968       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3969         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3970       else
3971         nonzero = -1;
3972       break;
3973
3974     case CTZ:
3975       /* If CTZ has a known value at zero, then the nonzero bits are
3976          that value, plus the number of bits in the mode minus one.  */
3977       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3978         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3979       else
3980         nonzero = -1;
3981       break;
3982
3983     case PARITY:
3984       nonzero = 1;
3985       break;
3986
3987     case IF_THEN_ELSE:
3988       {
3989         unsigned HOST_WIDE_INT nonzero_true =
3990           cached_nonzero_bits (XEXP (x, 1), mode,
3991                                known_x, known_mode, known_ret);
3992
3993         /* Don't call nonzero_bits for the second time if it cannot change
3994            anything.  */
3995         if ((nonzero & nonzero_true) != nonzero)
3996           nonzero &= nonzero_true
3997                      | cached_nonzero_bits (XEXP (x, 2), mode,
3998                                             known_x, known_mode, known_ret);
3999       }
4000       break;
4001
4002     default:
4003       break;
4004     }
4005
4006   return nonzero;
4007 }
4008
4009 /* See the macro definition above.  */
4010 #undef cached_num_sign_bit_copies
4011
4012 \f
4013 /* The function cached_num_sign_bit_copies is a wrapper around
4014    num_sign_bit_copies1.  It avoids exponential behavior in
4015    num_sign_bit_copies1 when X has identical subexpressions on the
4016    first or the second level.  */
4017
4018 static unsigned int
4019 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
4020                             enum machine_mode known_mode,
4021                             unsigned int known_ret)
4022 {
4023   if (x == known_x && mode == known_mode)
4024     return known_ret;
4025
4026   /* Try to find identical subexpressions.  If found call
4027      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
4028      the precomputed value for the subexpression as KNOWN_RET.  */
4029
4030   if (ARITHMETIC_P (x))
4031     {
4032       rtx x0 = XEXP (x, 0);
4033       rtx x1 = XEXP (x, 1);
4034
4035       /* Check the first level.  */
4036       if (x0 == x1)
4037         return
4038           num_sign_bit_copies1 (x, mode, x0, mode,
4039                                 cached_num_sign_bit_copies (x0, mode, known_x,
4040                                                             known_mode,
4041                                                             known_ret));
4042
4043       /* Check the second level.  */
4044       if (ARITHMETIC_P (x0)
4045           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
4046         return
4047           num_sign_bit_copies1 (x, mode, x1, mode,
4048                                 cached_num_sign_bit_copies (x1, mode, known_x,
4049                                                             known_mode,
4050                                                             known_ret));
4051
4052       if (ARITHMETIC_P (x1)
4053           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
4054         return
4055           num_sign_bit_copies1 (x, mode, x0, mode,
4056                                 cached_num_sign_bit_copies (x0, mode, known_x,
4057                                                             known_mode,
4058                                                             known_ret));
4059     }
4060
4061   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
4062 }
4063
4064 /* Return the number of bits at the high-order end of X that are known to
4065    be equal to the sign bit.  X will be used in mode MODE; if MODE is
4066    VOIDmode, X will be used in its own mode.  The returned value  will always
4067    be between 1 and the number of bits in MODE.  */
4068
4069 static unsigned int
4070 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
4071                       enum machine_mode known_mode,
4072                       unsigned int known_ret)
4073 {
4074   enum rtx_code code = GET_CODE (x);
4075   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
4076   int num0, num1, result;
4077   unsigned HOST_WIDE_INT nonzero;
4078
4079   /* If we weren't given a mode, use the mode of X.  If the mode is still
4080      VOIDmode, we don't know anything.  Likewise if one of the modes is
4081      floating-point.  */
4082
4083   if (mode == VOIDmode)
4084     mode = GET_MODE (x);
4085
4086   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
4087     return 1;
4088
4089   /* For a smaller object, just ignore the high bits.  */
4090   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
4091     {
4092       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
4093                                          known_x, known_mode, known_ret);
4094       return MAX (1,
4095                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
4096     }
4097
4098   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
4099     {
4100 #ifndef WORD_REGISTER_OPERATIONS
4101   /* If this machine does not do all register operations on the entire
4102      register and MODE is wider than the mode of X, we can say nothing
4103      at all about the high-order bits.  */
4104       return 1;
4105 #else
4106       /* Likewise on machines that do, if the mode of the object is smaller
4107          than a word and loads of that size don't sign extend, we can say
4108          nothing about the high order bits.  */
4109       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4110 #ifdef LOAD_EXTEND_OP
4111           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4112 #endif
4113           )
4114         return 1;
4115 #endif
4116     }
4117
4118   switch (code)
4119     {
4120     case REG:
4121
4122 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4123       /* If pointers extend signed and this is a pointer in Pmode, say that
4124          all the bits above ptr_mode are known to be sign bit copies.  */
4125       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4126           && REG_POINTER (x))
4127         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4128 #endif
4129
4130       {
4131         unsigned int copies_for_hook = 1, copies = 1;
4132         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4133                                                      known_mode, known_ret,
4134                                                      &copies_for_hook);
4135
4136         if (new)
4137           copies = cached_num_sign_bit_copies (new, mode, known_x,
4138                                                known_mode, known_ret);
4139
4140         if (copies > 1 || copies_for_hook > 1)
4141           return MAX (copies, copies_for_hook);
4142
4143         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4144       }
4145       break;
4146
4147     case MEM:
4148 #ifdef LOAD_EXTEND_OP
4149       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4150       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4151         return MAX (1, ((int) bitwidth
4152                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4153 #endif
4154       break;
4155
4156     case CONST_INT:
4157       /* If the constant is negative, take its 1's complement and remask.
4158          Then see how many zero bits we have.  */
4159       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4160       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4161           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4162         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4163
4164       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4165
4166     case SUBREG:
4167       /* If this is a SUBREG for a promoted object that is sign-extended
4168          and we are looking at it in a wider mode, we know that at least the
4169          high-order bits are known to be sign bit copies.  */
4170
4171       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4172         {
4173           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4174                                              known_x, known_mode, known_ret);
4175           return MAX ((int) bitwidth
4176                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4177                       num0);
4178         }
4179
4180       /* For a smaller object, just ignore the high bits.  */
4181       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4182         {
4183           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4184                                              known_x, known_mode, known_ret);
4185           return MAX (1, (num0
4186                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4187                                    - bitwidth)));
4188         }
4189
4190 #ifdef WORD_REGISTER_OPERATIONS
4191 #ifdef LOAD_EXTEND_OP
4192       /* For paradoxical SUBREGs on machines where all register operations
4193          affect the entire register, just look inside.  Note that we are
4194          passing MODE to the recursive call, so the number of sign bit copies
4195          will remain relative to that mode, not the inner mode.  */
4196
4197       /* This works only if loads sign extend.  Otherwise, if we get a
4198          reload for the inner part, it may be loaded from the stack, and
4199          then we lose all sign bit copies that existed before the store
4200          to the stack.  */
4201
4202       if ((GET_MODE_SIZE (GET_MODE (x))
4203            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4204           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4205           && MEM_P (SUBREG_REG (x)))
4206         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4207                                            known_x, known_mode, known_ret);
4208 #endif
4209 #endif
4210       break;
4211
4212     case SIGN_EXTRACT:
4213       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4214         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4215       break;
4216
4217     case SIGN_EXTEND:
4218       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4219               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4220                                             known_x, known_mode, known_ret));
4221
4222     case TRUNCATE:
4223       /* For a smaller object, just ignore the high bits.  */
4224       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4225                                          known_x, known_mode, known_ret);
4226       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4227                                     - bitwidth)));
4228
4229     case NOT:
4230       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4231                                          known_x, known_mode, known_ret);
4232
4233     case ROTATE:       case ROTATERT:
4234       /* If we are rotating left by a number of bits less than the number
4235          of sign bit copies, we can just subtract that amount from the
4236          number.  */
4237       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4238           && INTVAL (XEXP (x, 1)) >= 0
4239           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4240         {
4241           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4242                                              known_x, known_mode, known_ret);
4243           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4244                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4245         }
4246       break;
4247
4248     case NEG:
4249       /* In general, this subtracts one sign bit copy.  But if the value
4250          is known to be positive, the number of sign bit copies is the
4251          same as that of the input.  Finally, if the input has just one bit
4252          that might be nonzero, all the bits are copies of the sign bit.  */
4253       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4254                                          known_x, known_mode, known_ret);
4255       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4256         return num0 > 1 ? num0 - 1 : 1;
4257
4258       nonzero = nonzero_bits (XEXP (x, 0), mode);
4259       if (nonzero == 1)
4260         return bitwidth;
4261
4262       if (num0 > 1
4263           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4264         num0--;
4265
4266       return num0;
4267
4268     case IOR:   case AND:   case XOR:
4269     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4270       /* Logical operations will preserve the number of sign-bit copies.
4271          MIN and MAX operations always return one of the operands.  */
4272       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4273                                          known_x, known_mode, known_ret);
4274       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4275                                          known_x, known_mode, known_ret);
4276       return MIN (num0, num1);
4277
4278     case PLUS:  case MINUS:
4279       /* For addition and subtraction, we can have a 1-bit carry.  However,
4280          if we are subtracting 1 from a positive number, there will not
4281          be such a carry.  Furthermore, if the positive number is known to
4282          be 0 or 1, we know the result is either -1 or 0.  */
4283
4284       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4285           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4286         {
4287           nonzero = nonzero_bits (XEXP (x, 0), mode);
4288           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4289             return (nonzero == 1 || nonzero == 0 ? bitwidth
4290                     : bitwidth - floor_log2 (nonzero) - 1);
4291         }
4292
4293       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4294                                          known_x, known_mode, known_ret);
4295       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4296                                          known_x, known_mode, known_ret);
4297       result = MAX (1, MIN (num0, num1) - 1);
4298
4299 #ifdef POINTERS_EXTEND_UNSIGNED
4300       /* If pointers extend signed and this is an addition or subtraction
4301          to a pointer in Pmode, all the bits above ptr_mode are known to be
4302          sign bit copies.  */
4303       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4304           && (code == PLUS || code == MINUS)
4305           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4306         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4307                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4308                       result);
4309 #endif
4310       return result;
4311
4312     case MULT:
4313       /* The number of bits of the product is the sum of the number of
4314          bits of both terms.  However, unless one of the terms if known
4315          to be positive, we must allow for an additional bit since negating
4316          a negative number can remove one sign bit copy.  */
4317
4318       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4319                                          known_x, known_mode, known_ret);
4320       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4321                                          known_x, known_mode, known_ret);
4322
4323       result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
4324       if (result > 0
4325           && (bitwidth > HOST_BITS_PER_WIDE_INT
4326               || (((nonzero_bits (XEXP (x, 0), mode)
4327                     & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4328                   && ((nonzero_bits (XEXP (x, 1), mode)
4329                        & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
4330         result--;
4331
4332       return MAX (1, result);
4333
4334     case UDIV:
4335       /* The result must be <= the first operand.  If the first operand
4336          has the high bit set, we know nothing about the number of sign
4337          bit copies.  */
4338       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4339         return 1;
4340       else if ((nonzero_bits (XEXP (x, 0), mode)
4341                 & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4342         return 1;
4343       else
4344         return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4345                                            known_x, known_mode, known_ret);
4346
4347     case UMOD:
4348       /* The result must be <= the second operand.  */
4349       return cached_num_sign_bit_copies (XEXP (x, 1), mode,
4350                                            known_x, known_mode, known_ret);
4351
4352     case DIV:
4353       /* Similar to unsigned division, except that we have to worry about
4354          the case where the divisor is negative, in which case we have
4355          to add 1.  */
4356       result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4357                                            known_x, known_mode, known_ret);
4358       if (result > 1
4359           && (bitwidth > HOST_BITS_PER_WIDE_INT
4360               || (nonzero_bits (XEXP (x, 1), mode)
4361                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4362         result--;
4363
4364       return result;
4365
4366     case MOD:
4367       result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4368                                            known_x, known_mode, known_ret);
4369       if (result > 1
4370           && (bitwidth > HOST_BITS_PER_WIDE_INT
4371               || (nonzero_bits (XEXP (x, 1), mode)
4372                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4373         result--;
4374
4375       return result;
4376
4377     case ASHIFTRT:
4378       /* Shifts by a constant add to the number of bits equal to the
4379          sign bit.  */
4380       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4381                                          known_x, known_mode, known_ret);
4382       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4383           && INTVAL (XEXP (x, 1)) > 0)
4384         num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
4385
4386       return num0;
4387
4388     case ASHIFT:
4389       /* Left shifts destroy copies.  */
4390       if (GET_CODE (XEXP (x, 1)) != CONST_INT
4391           || INTVAL (XEXP (x, 1)) < 0
4392           || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
4393         return 1;
4394
4395       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4396                                          known_x, known_mode, known_ret);
4397       return MAX (1, num0 - INTVAL (XEXP (x, 1)));
4398
4399     case IF_THEN_ELSE:
4400       num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4401                                          known_x, known_mode, known_ret);
4402       num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
4403                                          known_x, known_mode, known_ret);
4404       return MIN (num0, num1);
4405
4406     case EQ:  case NE:  case GE:  case GT:  case LE:  case LT:
4407     case UNEQ:  case LTGT:  case UNGE:  case UNGT:  case UNLE:  case UNLT:
4408     case GEU: case GTU: case LEU: case LTU:
4409     case UNORDERED: case ORDERED:
4410       /* If the constant is negative, take its 1's complement and remask.
4411          Then see how many zero bits we have.  */
4412       nonzero = STORE_FLAG_VALUE;
4413       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4414           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4415         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4416
4417       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4418
4419     default:
4420       break;
4421     }
4422
4423   /* If we haven't been able to figure it out by one of the above rules,
4424      see if some of the high-order bits are known to be zero.  If so,
4425      count those bits and return one less than that amount.  If we can't
4426      safely compute the mask for this mode, always return BITWIDTH.  */
4427
4428   bitwidth = GET_MODE_BITSIZE (mode);
4429   if (bitwidth > HOST_BITS_PER_WIDE_INT)
4430     return 1;
4431
4432   nonzero = nonzero_bits (x, mode);
4433   return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
4434          ? 1 : bitwidth - floor_log2 (nonzero) - 1;
4435 }
4436
4437 /* Calculate the rtx_cost of a single instruction.  A return value of
4438    zero indicates an instruction pattern without a known cost.  */
4439
4440 int
4441 insn_rtx_cost (rtx pat)
4442 {
4443   int i, cost;
4444   rtx set;
4445
4446   /* Extract the single set rtx from the instruction pattern.
4447      We can't use single_set since we only have the pattern.  */
4448   if (GET_CODE (pat) == SET)
4449     set = pat;
4450   else if (GET_CODE (pat) == PARALLEL)
4451     {
4452       set = NULL_RTX;
4453       for (i = 0; i < XVECLEN (pat, 0); i++)
4454         {
4455           rtx x = XVECEXP (pat, 0, i);
4456           if (GET_CODE (x) == SET)
4457             {
4458               if (set)
4459                 return 0;
4460               set = x;
4461             }
4462         }
4463       if (!set)
4464         return 0;
4465     }
4466   else
4467     return 0;
4468
4469   cost = rtx_cost (SET_SRC (set), SET);
4470   return cost > 0 ? cost : COSTS_N_INSNS (1);
4471 }
4472
4473 /* Given an insn INSN and condition COND, return the condition in a
4474    canonical form to simplify testing by callers.  Specifically:
4475
4476    (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
4477    (2) Both operands will be machine operands; (cc0) will have been replaced.
4478    (3) If an operand is a constant, it will be the second operand.
4479    (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
4480        for GE, GEU, and LEU.
4481
4482    If the condition cannot be understood, or is an inequality floating-point
4483    comparison which needs to be reversed, 0 will be returned.
4484
4485    If REVERSE is nonzero, then reverse the condition prior to canonizing it.
4486
4487    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4488    insn used in locating the condition was found.  If a replacement test
4489    of the condition is desired, it should be placed in front of that
4490    insn and we will be sure that the inputs are still valid.
4491
4492    If WANT_REG is nonzero, we wish the condition to be relative to that
4493    register, if possible.  Therefore, do not canonicalize the condition
4494    further.  If ALLOW_CC_MODE is nonzero, allow the condition returned
4495    to be a compare to a CC mode register.
4496
4497    If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST
4498    and at INSN.  */
4499
4500 rtx
4501 canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest,
4502                         rtx want_reg, int allow_cc_mode, int valid_at_insn_p)
4503 {
4504   enum rtx_code code;
4505   rtx prev = insn;
4506   rtx set;
4507   rtx tem;
4508   rtx op0, op1;
4509   int reverse_code = 0;
4510   enum machine_mode mode;
4511   basic_block bb = BLOCK_FOR_INSN (insn);
4512
4513   code = GET_CODE (cond);
4514   mode = GET_MODE (cond);
4515   op0 = XEXP (cond, 0);
4516   op1 = XEXP (cond, 1);
4517
4518   if (reverse)
4519     code = reversed_comparison_code (cond, insn);
4520   if (code == UNKNOWN)
4521     return 0;
4522
4523   if (earliest)
4524     *earliest = insn;
4525
4526   /* If we are comparing a register with zero, see if the register is set
4527      in the previous insn to a COMPARE or a comparison operation.  Perform
4528      the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
4529      in cse.c  */
4530
4531   while ((GET_RTX_CLASS (code) == RTX_COMPARE
4532           || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
4533          && op1 == CONST0_RTX (GET_MODE (op0))
4534          && op0 != want_reg)
4535     {
4536       /* Set nonzero when we find something of interest.  */
4537       rtx x = 0;
4538
4539 #ifdef HAVE_cc0
4540       /* If comparison with cc0, import actual comparison from compare
4541          insn.  */
4542       if (op0 == cc0_rtx)
4543         {
4544           if ((prev = prev_nonnote_insn (prev)) == 0
4545               || !NONJUMP_INSN_P (prev)
4546               || (set = single_set (prev)) == 0
4547               || SET_DEST (set) != cc0_rtx)
4548             return 0;
4549
4550           op0 = SET_SRC (set);
4551           op1 = CONST0_RTX (GET_MODE (op0));
4552           if (earliest)
4553             *earliest = prev;
4554         }
4555 #endif
4556
4557       /* If this is a COMPARE, pick up the two things being compared.  */
4558       if (GET_CODE (op0) == COMPARE)
4559         {
4560           op1 = XEXP (op0, 1);
4561           op0 = XEXP (op0, 0);
4562           continue;
4563         }
4564       else if (!REG_P (op0))
4565         break;
4566
4567       /* Go back to the previous insn.  Stop if it is not an INSN.  We also
4568          stop if it isn't a single set or if it has a REG_INC note because
4569          we don't want to bother dealing with it.  */
4570
4571       if ((prev = prev_nonnote_insn (prev)) == 0
4572           || !NONJUMP_INSN_P (prev)
4573           || FIND_REG_INC_NOTE (prev, NULL_RTX)
4574           /* In cfglayout mode, there do not have to be labels at the
4575              beginning of a block, or jumps at the end, so the previous
4576              conditions would not stop us when we reach bb boundary.  */
4577           || BLOCK_FOR_INSN (prev) != bb)
4578         break;
4579
4580       set = set_of (op0, prev);
4581
4582       if (set
4583           && (GET_CODE (set) != SET
4584               || !rtx_equal_p (SET_DEST (set), op0)))
4585         break;
4586
4587       /* If this is setting OP0, get what it sets it to if it looks
4588          relevant.  */
4589       if (set)
4590         {
4591           enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
4592 #ifdef FLOAT_STORE_FLAG_VALUE
4593           REAL_VALUE_TYPE fsfv;
4594 #endif
4595
4596           /* ??? We may not combine comparisons done in a CCmode with
4597              comparisons not done in a CCmode.  This is to aid targets
4598              like Alpha that have an IEEE compliant EQ instruction, and
4599              a non-IEEE compliant BEQ instruction.  The use of CCmode is
4600              actually artificial, simply to prevent the combination, but
4601              should not affect other platforms.
4602
4603              However, we must allow VOIDmode comparisons to match either
4604              CCmode or non-CCmode comparison, because some ports have
4605              modeless comparisons inside branch patterns.
4606
4607              ??? This mode check should perhaps look more like the mode check
4608              in simplify_comparison in combine.  */
4609
4610           if ((GET_CODE (SET_SRC (set)) == COMPARE
4611                || (((code == NE
4612                      || (code == LT
4613                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4614                          && (GET_MODE_BITSIZE (inner_mode)
4615                              <= HOST_BITS_PER_WIDE_INT)
4616                          && (STORE_FLAG_VALUE
4617                              & ((HOST_WIDE_INT) 1
4618                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4619 #ifdef FLOAT_STORE_FLAG_VALUE
4620                      || (code == LT
4621                          && SCALAR_FLOAT_MODE_P (inner_mode)
4622                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4623                              REAL_VALUE_NEGATIVE (fsfv)))
4624 #endif
4625                      ))
4626                    && COMPARISON_P (SET_SRC (set))))
4627               && (((GET_MODE_CLASS (mode) == MODE_CC)
4628                    == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4629                   || mode == VOIDmode || inner_mode == VOIDmode))
4630             x = SET_SRC (set);
4631           else if (((code == EQ
4632                      || (code == GE
4633                          && (GET_MODE_BITSIZE (inner_mode)
4634                              <= HOST_BITS_PER_WIDE_INT)
4635                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4636                          && (STORE_FLAG_VALUE
4637                              & ((HOST_WIDE_INT) 1
4638                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4639 #ifdef FLOAT_STORE_FLAG_VALUE
4640                      || (code == GE
4641                          && SCALAR_FLOAT_MODE_P (inner_mode)
4642                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4643                              REAL_VALUE_NEGATIVE (fsfv)))
4644 #endif
4645                      ))
4646                    && COMPARISON_P (SET_SRC (set))
4647                    && (((GET_MODE_CLASS (mode) == MODE_CC)
4648                         == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4649                        || mode == VOIDmode || inner_mode == VOIDmode))
4650
4651             {
4652               reverse_code = 1;
4653               x = SET_SRC (set);
4654             }
4655           else
4656             break;
4657         }
4658
4659       else if (reg_set_p (op0, prev))
4660         /* If this sets OP0, but not directly, we have to give up.  */
4661         break;
4662
4663       if (x)
4664         {
4665           /* If the caller is expecting the condition to be valid at INSN,
4666              make sure X doesn't change before INSN.  */
4667           if (valid_at_insn_p)
4668             if (modified_in_p (x, prev) || modified_between_p (x, prev, insn))
4669               break;
4670           if (COMPARISON_P (x))
4671             code = GET_CODE (x);
4672           if (reverse_code)
4673             {
4674               code = reversed_comparison_code (x, prev);
4675               if (code == UNKNOWN)
4676                 return 0;
4677               reverse_code = 0;
4678             }
4679
4680           op0 = XEXP (x, 0), op1 = XEXP (x, 1);
4681           if (earliest)
4682             *earliest = prev;
4683         }
4684     }
4685
4686   /* If constant is first, put it last.  */
4687   if (CONSTANT_P (op0))
4688     code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
4689
4690   /* If OP0 is the result of a comparison, we weren't able to find what
4691      was really being compared, so fail.  */
4692   if (!allow_cc_mode
4693       && GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
4694     return 0;
4695
4696   /* Canonicalize any ordered comparison with integers involving equality
4697      if we can do computations in the relevant mode and we do not
4698      overflow.  */
4699
4700   if (GET_MODE_CLASS (GET_MODE (op0)) != MODE_CC
4701       && GET_CODE (op1) == CONST_INT
4702       && GET_MODE (op0) != VOIDmode
4703       && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
4704     {
4705       HOST_WIDE_INT const_val = INTVAL (op1);
4706       unsigned HOST_WIDE_INT uconst_val = const_val;
4707       unsigned HOST_WIDE_INT max_val
4708         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
4709
4710       switch (code)
4711         {
4712         case LE:
4713           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
4714             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
4715           break;
4716
4717         /* When cross-compiling, const_val might be sign-extended from
4718            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
4719         case GE:
4720           if ((HOST_WIDE_INT) (const_val & max_val)
4721               != (((HOST_WIDE_INT) 1
4722                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
4723             code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0));
4724           break;
4725
4726         case LEU:
4727           if (uconst_val < max_val)
4728             code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
4729           break;
4730
4731         case GEU:
4732           if (uconst_val != 0)
4733             code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
4734           break;
4735
4736         default:
4737           break;
4738         }
4739     }
4740
4741   /* Never return CC0; return zero instead.  */
4742   if (CC0_P (op0))
4743     return 0;
4744
4745   return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
4746 }
4747
4748 /* Given a jump insn JUMP, return the condition that will cause it to branch
4749    to its JUMP_LABEL.  If the condition cannot be understood, or is an
4750    inequality floating-point comparison which needs to be reversed, 0 will
4751    be returned.
4752
4753    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4754    insn used in locating the condition was found.  If a replacement test
4755    of the condition is desired, it should be placed in front of that
4756    insn and we will be sure that the inputs are still valid.  If EARLIEST
4757    is null, the returned condition will be valid at INSN.
4758
4759    If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
4760    compare CC mode register.
4761
4762    VALID_AT_INSN_P is the same as for canonicalize_condition.  */
4763
4764 rtx
4765 get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p)
4766 {
4767   rtx cond;
4768   int reverse;
4769   rtx set;
4770
4771   /* If this is not a standard conditional jump, we can't parse it.  */
4772   if (!JUMP_P (jump)
4773       || ! any_condjump_p (jump))
4774     return 0;
4775   set = pc_set (jump);
4776
4777   cond = XEXP (SET_SRC (set), 0);
4778
4779   /* If this branches to JUMP_LABEL when the condition is false, reverse
4780      the condition.  */
4781   reverse
4782     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
4783       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
4784
4785   return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
4786                                  allow_cc_mode, valid_at_insn_p);
4787 }
4788
4789 \f
4790 /* Initialize non_rtx_starting_operands, which is used to speed up
4791    for_each_rtx.  */
4792 void
4793 init_rtlanal (void)
4794 {
4795   int i;
4796   for (i = 0; i < NUM_RTX_CODE; i++)
4797     {
4798       const char *format = GET_RTX_FORMAT (i);
4799       const char *first = strpbrk (format, "eEV");
4800       non_rtx_starting_operands[i] = first ? first - format : -1;
4801     }
4802 }
4803 \f
4804 /* Check whether this is a constant pool constant.  */
4805 bool
4806 constant_pool_constant_p (rtx x)
4807 {
4808   x = avoid_constant_pool_reference (x);
4809   return GET_CODE (x) == CONST_DOUBLE;
4810 }
4811