gcc/rtlanal.c

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