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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, 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' && reg_overlap_mentioned_p (x, XEXP (in, i)))
1313             return 1;
1314
1315         return 0;
1316       }
1317
1318     case SCRATCH:
1319     case PC:
1320     case CC0:
1321       return reg_mentioned_p (x, in);
1322
1323     case PARALLEL:
1324       {
1325         int i;
1326
1327         /* If any register in here refers to it we return true.  */
1328         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1329           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1330               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1331             return 1;
1332         return 0;
1333       }
1334
1335     default:
1336       gcc_assert (CONSTANT_P (x));
1337       return 0;
1338     }
1339 }
1340 \f
1341 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1342    (X would be the pattern of an insn).
1343    FUN receives two arguments:
1344      the REG, MEM, CC0 or PC being stored in or clobbered,
1345      the SET or CLOBBER rtx that does the store.
1346
1347   If the item being stored in or clobbered is a SUBREG of a hard register,
1348   the SUBREG will be passed.  */
1349
1350 void
1351 note_stores (rtx x, void (*fun) (rtx, rtx, void *), void *data)
1352 {
1353   int i;
1354
1355   if (GET_CODE (x) == COND_EXEC)
1356     x = COND_EXEC_CODE (x);
1357
1358   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1359     {
1360       rtx dest = SET_DEST (x);
1361
1362       while ((GET_CODE (dest) == SUBREG
1363               && (!REG_P (SUBREG_REG (dest))
1364                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1365              || GET_CODE (dest) == ZERO_EXTRACT
1366              || GET_CODE (dest) == STRICT_LOW_PART)
1367         dest = XEXP (dest, 0);
1368
1369       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1370          each of whose first operand is a register.  */
1371       if (GET_CODE (dest) == PARALLEL)
1372         {
1373           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1374             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1375               (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
1376         }
1377       else
1378         (*fun) (dest, x, data);
1379     }
1380
1381   else if (GET_CODE (x) == PARALLEL)
1382     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1383       note_stores (XVECEXP (x, 0, i), fun, data);
1384 }
1385 \f
1386 /* Like notes_stores, but call FUN for each expression that is being
1387    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1388    FUN for each expression, not any interior subexpressions.  FUN receives a
1389    pointer to the expression and the DATA passed to this function.
1390
1391    Note that this is not quite the same test as that done in reg_referenced_p
1392    since that considers something as being referenced if it is being
1393    partially set, while we do not.  */
1394
1395 void
1396 note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data)
1397 {
1398   rtx body = *pbody;
1399   int i;
1400
1401   switch (GET_CODE (body))
1402     {
1403     case COND_EXEC:
1404       (*fun) (&COND_EXEC_TEST (body), data);
1405       note_uses (&COND_EXEC_CODE (body), fun, data);
1406       return;
1407
1408     case PARALLEL:
1409       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1410         note_uses (&XVECEXP (body, 0, i), fun, data);
1411       return;
1412
1413     case USE:
1414       (*fun) (&XEXP (body, 0), data);
1415       return;
1416
1417     case ASM_OPERANDS:
1418       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1419         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1420       return;
1421
1422     case TRAP_IF:
1423       (*fun) (&TRAP_CONDITION (body), data);
1424       return;
1425
1426     case PREFETCH:
1427       (*fun) (&XEXP (body, 0), data);
1428       return;
1429
1430     case UNSPEC:
1431     case UNSPEC_VOLATILE:
1432       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1433         (*fun) (&XVECEXP (body, 0, i), data);
1434       return;
1435
1436     case CLOBBER:
1437       if (MEM_P (XEXP (body, 0)))
1438         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1439       return;
1440
1441     case SET:
1442       {
1443         rtx dest = SET_DEST (body);
1444
1445         /* For sets we replace everything in source plus registers in memory
1446            expression in store and operands of a ZERO_EXTRACT.  */
1447         (*fun) (&SET_SRC (body), data);
1448
1449         if (GET_CODE (dest) == ZERO_EXTRACT)
1450           {
1451             (*fun) (&XEXP (dest, 1), data);
1452             (*fun) (&XEXP (dest, 2), data);
1453           }
1454
1455         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1456           dest = XEXP (dest, 0);
1457
1458         if (MEM_P (dest))
1459           (*fun) (&XEXP (dest, 0), data);
1460       }
1461       return;
1462
1463     default:
1464       /* All the other possibilities never store.  */
1465       (*fun) (pbody, data);
1466       return;
1467     }
1468 }
1469 \f
1470 /* Return nonzero if X's old contents don't survive after INSN.
1471    This will be true if X is (cc0) or if X is a register and
1472    X dies in INSN or because INSN entirely sets X.
1473
1474    "Entirely set" means set directly and not through a SUBREG, or
1475    ZERO_EXTRACT, so no trace of the old contents remains.
1476    Likewise, REG_INC does not count.
1477
1478    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1479    but for this use that makes no difference, since regs don't overlap
1480    during their lifetimes.  Therefore, this function may be used
1481    at any time after deaths have been computed (in flow.c).
1482
1483    If REG is a hard reg that occupies multiple machine registers, this
1484    function will only return 1 if each of those registers will be replaced
1485    by INSN.  */
1486
1487 int
1488 dead_or_set_p (rtx insn, rtx x)
1489 {
1490   unsigned int regno, last_regno;
1491   unsigned int i;
1492
1493   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1494   if (GET_CODE (x) == CC0)
1495     return 1;
1496
1497   gcc_assert (REG_P (x));
1498
1499   regno = REGNO (x);
1500   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1501                 : regno + hard_regno_nregs[regno][GET_MODE (x)] - 1);
1502
1503   for (i = regno; i <= last_regno; i++)
1504     if (! dead_or_set_regno_p (insn, i))
1505       return 0;
1506
1507   return 1;
1508 }
1509
1510 /* Return TRUE iff DEST is a register or subreg of a register and
1511    doesn't change the number of words of the inner register, and any
1512    part of the register is TEST_REGNO.  */
1513
1514 static bool
1515 covers_regno_no_parallel_p (rtx dest, unsigned int test_regno)
1516 {
1517   unsigned int regno, endregno;
1518
1519   if (GET_CODE (dest) == SUBREG
1520       && (((GET_MODE_SIZE (GET_MODE (dest))
1521             + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1522           == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1523                + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1524     dest = SUBREG_REG (dest);
1525
1526   if (!REG_P (dest))
1527     return false;
1528
1529   regno = REGNO (dest);
1530   endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1531               : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
1532   return (test_regno >= regno && test_regno < endregno);
1533 }
1534
1535 /* Like covers_regno_no_parallel_p, but also handles PARALLELs where
1536    any member matches the covers_regno_no_parallel_p criteria.  */
1537
1538 static bool
1539 covers_regno_p (rtx dest, unsigned int test_regno)
1540 {
1541   if (GET_CODE (dest) == PARALLEL)
1542     {
1543       /* Some targets place small structures in registers for return
1544          values of functions, and those registers are wrapped in
1545          PARALLELs that we may see as the destination of a SET.  */
1546       int i;
1547
1548       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1549         {
1550           rtx inner = XEXP (XVECEXP (dest, 0, i), 0);
1551           if (inner != NULL_RTX
1552               && covers_regno_no_parallel_p (inner, test_regno))
1553             return true;
1554         }
1555
1556       return false;
1557     }
1558   else
1559     return covers_regno_no_parallel_p (dest, test_regno);
1560 }
1561
1562 /* Utility function for dead_or_set_p to check an individual register.  Also
1563    called from flow.c.  */
1564
1565 int
1566 dead_or_set_regno_p (rtx insn, unsigned int test_regno)
1567 {
1568   rtx pattern;
1569
1570   /* See if there is a death note for something that includes TEST_REGNO.  */
1571   if (find_regno_note (insn, REG_DEAD, test_regno))
1572     return 1;
1573
1574   if (CALL_P (insn)
1575       && find_regno_fusage (insn, CLOBBER, test_regno))
1576     return 1;
1577
1578   pattern = PATTERN (insn);
1579
1580   if (GET_CODE (pattern) == COND_EXEC)
1581     pattern = COND_EXEC_CODE (pattern);
1582
1583   if (GET_CODE (pattern) == SET)
1584     return covers_regno_p (SET_DEST (pattern), test_regno);
1585   else if (GET_CODE (pattern) == PARALLEL)
1586     {
1587       int i;
1588
1589       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1590         {
1591           rtx body = XVECEXP (pattern, 0, i);
1592
1593           if (GET_CODE (body) == COND_EXEC)
1594             body = COND_EXEC_CODE (body);
1595
1596           if ((GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1597               && covers_regno_p (SET_DEST (body), test_regno))
1598             return 1;
1599         }
1600     }
1601
1602   return 0;
1603 }
1604
1605 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1606    If DATUM is nonzero, look for one whose datum is DATUM.  */
1607
1608 rtx
1609 find_reg_note (rtx insn, enum reg_note kind, rtx datum)
1610 {
1611   rtx link;
1612
1613   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1614   if (! INSN_P (insn))
1615     return 0;
1616   if (datum == 0)
1617     {
1618       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1619         if (REG_NOTE_KIND (link) == kind)
1620           return link;
1621       return 0;
1622     }
1623
1624   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1625     if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0))
1626       return link;
1627   return 0;
1628 }
1629
1630 /* Return the reg-note of kind KIND in insn INSN which applies to register
1631    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1632    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1633    it might be the case that the note overlaps REGNO.  */
1634
1635 rtx
1636 find_regno_note (rtx insn, enum reg_note kind, unsigned int regno)
1637 {
1638   rtx link;
1639
1640   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1641   if (! INSN_P (insn))
1642     return 0;
1643
1644   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1645     if (REG_NOTE_KIND (link) == kind
1646         /* Verify that it is a register, so that scratch and MEM won't cause a
1647            problem here.  */
1648         && REG_P (XEXP (link, 0))
1649         && REGNO (XEXP (link, 0)) <= regno
1650         && ((REGNO (XEXP (link, 0))
1651              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1652                 : hard_regno_nregs[REGNO (XEXP (link, 0))]
1653                                   [GET_MODE (XEXP (link, 0))]))
1654             > regno))
1655       return link;
1656   return 0;
1657 }
1658
1659 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1660    has such a note.  */
1661
1662 rtx
1663 find_reg_equal_equiv_note (rtx insn)
1664 {
1665   rtx link;
1666
1667   if (!INSN_P (insn))
1668     return 0;
1669   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1670     if (REG_NOTE_KIND (link) == REG_EQUAL
1671         || REG_NOTE_KIND (link) == REG_EQUIV)
1672       {
1673         if (single_set (insn) == 0)
1674           return 0;
1675         return link;
1676       }
1677   return NULL;
1678 }
1679
1680 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1681    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1682
1683 int
1684 find_reg_fusage (rtx insn, enum rtx_code code, rtx datum)
1685 {
1686   /* If it's not a CALL_INSN, it can't possibly have a
1687      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1688   if (!CALL_P (insn))
1689     return 0;
1690
1691   gcc_assert (datum);
1692
1693   if (!REG_P (datum))
1694     {
1695       rtx link;
1696
1697       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1698            link;
1699            link = XEXP (link, 1))
1700         if (GET_CODE (XEXP (link, 0)) == code
1701             && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
1702           return 1;
1703     }
1704   else
1705     {
1706       unsigned int regno = REGNO (datum);
1707
1708       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1709          to pseudo registers, so don't bother checking.  */
1710
1711       if (regno < FIRST_PSEUDO_REGISTER)
1712         {
1713           unsigned int end_regno
1714             = regno + hard_regno_nregs[regno][GET_MODE (datum)];
1715           unsigned int i;
1716
1717           for (i = regno; i < end_regno; i++)
1718             if (find_regno_fusage (insn, code, i))
1719               return 1;
1720         }
1721     }
1722
1723   return 0;
1724 }
1725
1726 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1727    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1728
1729 int
1730 find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno)
1731 {
1732   rtx link;
1733
1734   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1735      to pseudo registers, so don't bother checking.  */
1736
1737   if (regno >= FIRST_PSEUDO_REGISTER
1738       || !CALL_P (insn) )
1739     return 0;
1740
1741   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1742     {
1743       unsigned int regnote;
1744       rtx op, reg;
1745
1746       if (GET_CODE (op = XEXP (link, 0)) == code
1747           && REG_P (reg = XEXP (op, 0))
1748           && (regnote = REGNO (reg)) <= regno
1749           && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno)
1750         return 1;
1751     }
1752
1753   return 0;
1754 }
1755
1756 /* Return true if INSN is a call to a pure function.  */
1757
1758 int
1759 pure_call_p (rtx insn)
1760 {
1761   rtx link;
1762
1763   if (!CALL_P (insn) || ! CONST_OR_PURE_CALL_P (insn))
1764     return 0;
1765
1766   /* Look for the note that differentiates const and pure functions.  */
1767   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1768     {
1769       rtx u, m;
1770
1771       if (GET_CODE (u = XEXP (link, 0)) == USE
1772           && MEM_P (m = XEXP (u, 0)) && GET_MODE (m) == BLKmode
1773           && GET_CODE (XEXP (m, 0)) == SCRATCH)
1774         return 1;
1775     }
1776
1777   return 0;
1778 }
1779 \f
1780 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1781
1782 void
1783 remove_note (rtx insn, rtx note)
1784 {
1785   rtx link;
1786
1787   if (note == NULL_RTX)
1788     return;
1789
1790   if (REG_NOTES (insn) == note)
1791     {
1792       REG_NOTES (insn) = XEXP (note, 1);
1793       return;
1794     }
1795
1796   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1797     if (XEXP (link, 1) == note)
1798       {
1799         XEXP (link, 1) = XEXP (note, 1);
1800         return;
1801       }
1802
1803   gcc_unreachable ();
1804 }
1805
1806 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1807    return 1 if it is found.  A simple equality test is used to determine if
1808    NODE matches.  */
1809
1810 int
1811 in_expr_list_p (rtx listp, rtx node)
1812 {
1813   rtx x;
1814
1815   for (x = listp; x; x = XEXP (x, 1))
1816     if (node == XEXP (x, 0))
1817       return 1;
1818
1819   return 0;
1820 }
1821
1822 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1823    remove that entry from the list if it is found.
1824
1825    A simple equality test is used to determine if NODE matches.  */
1826
1827 void
1828 remove_node_from_expr_list (rtx node, rtx *listp)
1829 {
1830   rtx temp = *listp;
1831   rtx prev = NULL_RTX;
1832
1833   while (temp)
1834     {
1835       if (node == XEXP (temp, 0))
1836         {
1837           /* Splice the node out of the list.  */
1838           if (prev)
1839             XEXP (prev, 1) = XEXP (temp, 1);
1840           else
1841             *listp = XEXP (temp, 1);
1842
1843           return;
1844         }
1845
1846       prev = temp;
1847       temp = XEXP (temp, 1);
1848     }
1849 }
1850 \f
1851 /* Nonzero if X contains any volatile instructions.  These are instructions
1852    which may cause unpredictable machine state instructions, and thus no
1853    instructions should be moved or combined across them.  This includes
1854    only volatile asms and UNSPEC_VOLATILE instructions.  */
1855
1856 int
1857 volatile_insn_p (rtx x)
1858 {
1859   RTX_CODE code;
1860
1861   code = GET_CODE (x);
1862   switch (code)
1863     {
1864     case LABEL_REF:
1865     case SYMBOL_REF:
1866     case CONST_INT:
1867     case CONST:
1868     case CONST_DOUBLE:
1869     case CONST_VECTOR:
1870     case CC0:
1871     case PC:
1872     case REG:
1873     case SCRATCH:
1874     case CLOBBER:
1875     case ADDR_VEC:
1876     case ADDR_DIFF_VEC:
1877     case CALL:
1878     case MEM:
1879       return 0;
1880
1881     case UNSPEC_VOLATILE:
1882  /* case TRAP_IF: This isn't clear yet.  */
1883       return 1;
1884
1885     case ASM_INPUT:
1886     case ASM_OPERANDS:
1887       if (MEM_VOLATILE_P (x))
1888         return 1;
1889
1890     default:
1891       break;
1892     }
1893
1894   /* Recursively scan the operands of this expression.  */
1895
1896   {
1897     const char *fmt = GET_RTX_FORMAT (code);
1898     int i;
1899
1900     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1901       {
1902         if (fmt[i] == 'e')
1903           {
1904             if (volatile_insn_p (XEXP (x, i)))
1905               return 1;
1906           }
1907         else if (fmt[i] == 'E')
1908           {
1909             int j;
1910             for (j = 0; j < XVECLEN (x, i); j++)
1911               if (volatile_insn_p (XVECEXP (x, i, j)))
1912                 return 1;
1913           }
1914       }
1915   }
1916   return 0;
1917 }
1918
1919 /* Nonzero if X contains any volatile memory references
1920    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1921
1922 int
1923 volatile_refs_p (rtx x)
1924 {
1925   RTX_CODE code;
1926
1927   code = GET_CODE (x);
1928   switch (code)
1929     {
1930     case LABEL_REF:
1931     case SYMBOL_REF:
1932     case CONST_INT:
1933     case CONST:
1934     case CONST_DOUBLE:
1935     case CONST_VECTOR:
1936     case CC0:
1937     case PC:
1938     case REG:
1939     case SCRATCH:
1940     case CLOBBER:
1941     case ADDR_VEC:
1942     case ADDR_DIFF_VEC:
1943       return 0;
1944
1945     case UNSPEC_VOLATILE:
1946       return 1;
1947
1948     case MEM:
1949     case ASM_INPUT:
1950     case ASM_OPERANDS:
1951       if (MEM_VOLATILE_P (x))
1952         return 1;
1953
1954     default:
1955       break;
1956     }
1957
1958   /* Recursively scan the operands of this expression.  */
1959
1960   {
1961     const char *fmt = GET_RTX_FORMAT (code);
1962     int i;
1963
1964     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1965       {
1966         if (fmt[i] == 'e')
1967           {
1968             if (volatile_refs_p (XEXP (x, i)))
1969               return 1;
1970           }
1971         else if (fmt[i] == 'E')
1972           {
1973             int j;
1974             for (j = 0; j < XVECLEN (x, i); j++)
1975               if (volatile_refs_p (XVECEXP (x, i, j)))
1976                 return 1;
1977           }
1978       }
1979   }
1980   return 0;
1981 }
1982
1983 /* Similar to above, except that it also rejects register pre- and post-
1984    incrementing.  */
1985
1986 int
1987 side_effects_p (rtx x)
1988 {
1989   RTX_CODE code;
1990
1991   code = GET_CODE (x);
1992   switch (code)
1993     {
1994     case LABEL_REF:
1995     case SYMBOL_REF:
1996     case CONST_INT:
1997     case CONST:
1998     case CONST_DOUBLE:
1999     case CONST_VECTOR:
2000     case CC0:
2001     case PC:
2002     case REG:
2003     case SCRATCH:
2004     case ADDR_VEC:
2005     case ADDR_DIFF_VEC:
2006       return 0;
2007
2008     case CLOBBER:
2009       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2010          when some combination can't be done.  If we see one, don't think
2011          that we can simplify the expression.  */
2012       return (GET_MODE (x) != VOIDmode);
2013
2014     case PRE_INC:
2015     case PRE_DEC:
2016     case POST_INC:
2017     case POST_DEC:
2018     case PRE_MODIFY:
2019     case POST_MODIFY:
2020     case CALL:
2021     case UNSPEC_VOLATILE:
2022  /* case TRAP_IF: This isn't clear yet.  */
2023       return 1;
2024
2025     case MEM:
2026     case ASM_INPUT:
2027     case ASM_OPERANDS:
2028       if (MEM_VOLATILE_P (x))
2029         return 1;
2030
2031     default:
2032       break;
2033     }
2034
2035   /* Recursively scan the operands of this expression.  */
2036
2037   {
2038     const char *fmt = GET_RTX_FORMAT (code);
2039     int i;
2040
2041     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2042       {
2043         if (fmt[i] == 'e')
2044           {
2045             if (side_effects_p (XEXP (x, i)))
2046               return 1;
2047           }
2048         else if (fmt[i] == 'E')
2049           {
2050             int j;
2051             for (j = 0; j < XVECLEN (x, i); j++)
2052               if (side_effects_p (XVECEXP (x, i, j)))
2053                 return 1;
2054           }
2055       }
2056   }
2057   return 0;
2058 }
2059 \f
2060 /* Return nonzero if evaluating rtx X might cause a trap.  */
2061
2062 int
2063 may_trap_p (rtx x)
2064 {
2065   int i;
2066   enum rtx_code code;
2067   const char *fmt;
2068
2069   if (x == 0)
2070     return 0;
2071   code = GET_CODE (x);
2072   switch (code)
2073     {
2074       /* Handle these cases quickly.  */
2075     case CONST_INT:
2076     case CONST_DOUBLE:
2077     case CONST_VECTOR:
2078     case SYMBOL_REF:
2079     case LABEL_REF:
2080     case CONST:
2081     case PC:
2082     case CC0:
2083     case REG:
2084     case SCRATCH:
2085       return 0;
2086
2087     case ASM_INPUT:
2088     case UNSPEC_VOLATILE:
2089     case TRAP_IF:
2090       return 1;
2091
2092     case ASM_OPERANDS:
2093       return MEM_VOLATILE_P (x);
2094
2095       /* Memory ref can trap unless it's a static var or a stack slot.  */
2096     case MEM:
2097       if (MEM_NOTRAP_P (x))
2098         return 0;
2099       return rtx_addr_can_trap_p (XEXP (x, 0));
2100
2101       /* Division by a non-constant might trap.  */
2102     case DIV:
2103     case MOD:
2104     case UDIV:
2105     case UMOD:
2106       if (HONOR_SNANS (GET_MODE (x)))
2107         return 1;
2108       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
2109         return flag_trapping_math;
2110       if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2111         return 1;
2112       break;
2113
2114     case EXPR_LIST:
2115       /* An EXPR_LIST is used to represent a function call.  This
2116          certainly may trap.  */
2117       return 1;
2118
2119     case GE:
2120     case GT:
2121     case LE:
2122     case LT:
2123     case LTGT:
2124     case COMPARE:
2125       /* Some floating point comparisons may trap.  */
2126       if (!flag_trapping_math)
2127         break;
2128       /* ??? There is no machine independent way to check for tests that trap
2129          when COMPARE is used, though many targets do make this distinction.
2130          For instance, sparc uses CCFPE for compares which generate exceptions
2131          and CCFP for compares which do not generate exceptions.  */
2132       if (HONOR_NANS (GET_MODE (x)))
2133         return 1;
2134       /* But often the compare has some CC mode, so check operand
2135          modes as well.  */
2136       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2137           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2138         return 1;
2139       break;
2140
2141     case EQ:
2142     case NE:
2143       if (HONOR_SNANS (GET_MODE (x)))
2144         return 1;
2145       /* Often comparison is CC mode, so check operand modes.  */
2146       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2147           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2148         return 1;
2149       break;
2150
2151     case FIX:
2152       /* Conversion of floating point might trap.  */
2153       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2154         return 1;
2155       break;
2156
2157     case NEG:
2158     case ABS:
2159       /* These operations don't trap even with floating point.  */
2160       break;
2161
2162     default:
2163       /* Any floating arithmetic may trap.  */
2164       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
2165           && flag_trapping_math)
2166         return 1;
2167     }
2168
2169   fmt = GET_RTX_FORMAT (code);
2170   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2171     {
2172       if (fmt[i] == 'e')
2173         {
2174           if (may_trap_p (XEXP (x, i)))
2175             return 1;
2176         }
2177       else if (fmt[i] == 'E')
2178         {
2179           int j;
2180           for (j = 0; j < XVECLEN (x, i); j++)
2181             if (may_trap_p (XVECEXP (x, i, j)))
2182               return 1;
2183         }
2184     }
2185   return 0;
2186 }
2187 \f
2188 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2189    i.e., an inequality.  */
2190
2191 int
2192 inequality_comparisons_p (rtx x)
2193 {
2194   const char *fmt;
2195   int len, i;
2196   enum rtx_code code = GET_CODE (x);
2197
2198   switch (code)
2199     {
2200     case REG:
2201     case SCRATCH:
2202     case PC:
2203     case CC0:
2204     case CONST_INT:
2205     case CONST_DOUBLE:
2206     case CONST_VECTOR:
2207     case CONST:
2208     case LABEL_REF:
2209     case SYMBOL_REF:
2210       return 0;
2211
2212     case LT:
2213     case LTU:
2214     case GT:
2215     case GTU:
2216     case LE:
2217     case LEU:
2218     case GE:
2219     case GEU:
2220       return 1;
2221
2222     default:
2223       break;
2224     }
2225
2226   len = GET_RTX_LENGTH (code);
2227   fmt = GET_RTX_FORMAT (code);
2228
2229   for (i = 0; i < len; i++)
2230     {
2231       if (fmt[i] == 'e')
2232         {
2233           if (inequality_comparisons_p (XEXP (x, i)))
2234             return 1;
2235         }
2236       else if (fmt[i] == 'E')
2237         {
2238           int j;
2239           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2240             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2241               return 1;
2242         }
2243     }
2244
2245   return 0;
2246 }
2247 \f
2248 /* Replace any occurrence of FROM in X with TO.  The function does
2249    not enter into CONST_DOUBLE for the replace.
2250
2251    Note that copying is not done so X must not be shared unless all copies
2252    are to be modified.  */
2253
2254 rtx
2255 replace_rtx (rtx x, rtx from, rtx to)
2256 {
2257   int i, j;
2258   const char *fmt;
2259
2260   /* The following prevents loops occurrence when we change MEM in
2261      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2262   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2263     return x;
2264
2265   if (x == from)
2266     return to;
2267
2268   /* Allow this function to make replacements in EXPR_LISTs.  */
2269   if (x == 0)
2270     return 0;
2271
2272   if (GET_CODE (x) == SUBREG)
2273     {
2274       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2275
2276       if (GET_CODE (new) == CONST_INT)
2277         {
2278           x = simplify_subreg (GET_MODE (x), new,
2279                                GET_MODE (SUBREG_REG (x)),
2280                                SUBREG_BYTE (x));
2281           gcc_assert (x);
2282         }
2283       else
2284         SUBREG_REG (x) = new;
2285
2286       return x;
2287     }
2288   else if (GET_CODE (x) == ZERO_EXTEND)
2289     {
2290       rtx new = replace_rtx (XEXP (x, 0), from, to);
2291
2292       if (GET_CODE (new) == CONST_INT)
2293         {
2294           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2295                                         new, GET_MODE (XEXP (x, 0)));
2296           gcc_assert (x);
2297         }
2298       else
2299         XEXP (x, 0) = new;
2300
2301       return x;
2302     }
2303
2304   fmt = GET_RTX_FORMAT (GET_CODE (x));
2305   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2306     {
2307       if (fmt[i] == 'e')
2308         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2309       else if (fmt[i] == 'E')
2310         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2311           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2312     }
2313
2314   return x;
2315 }
2316 \f
2317 /* Throughout the rtx X, replace many registers according to REG_MAP.
2318    Return the replacement for X (which may be X with altered contents).
2319    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
2320    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
2321
2322    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
2323    should not be mapped to pseudos or vice versa since validate_change
2324    is not called.
2325
2326    If REPLACE_DEST is 1, replacements are also done in destinations;
2327    otherwise, only sources are replaced.  */
2328
2329 rtx
2330 replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest)
2331 {
2332   enum rtx_code code;
2333   int i;
2334   const char *fmt;
2335
2336   if (x == 0)
2337     return x;
2338
2339   code = GET_CODE (x);
2340   switch (code)
2341     {
2342     case SCRATCH:
2343     case PC:
2344     case CC0:
2345     case CONST_INT:
2346     case CONST_DOUBLE:
2347     case CONST_VECTOR:
2348     case CONST:
2349     case SYMBOL_REF:
2350     case LABEL_REF:
2351       return x;
2352
2353     case REG:
2354       /* Verify that the register has an entry before trying to access it.  */
2355       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
2356         {
2357           /* SUBREGs can't be shared.  Always return a copy to ensure that if
2358              this replacement occurs more than once then each instance will
2359              get distinct rtx.  */
2360           if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
2361             return copy_rtx (reg_map[REGNO (x)]);
2362           return reg_map[REGNO (x)];
2363         }
2364       return x;
2365
2366     case SUBREG:
2367       /* Prevent making nested SUBREGs.  */
2368       if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs
2369           && reg_map[REGNO (SUBREG_REG (x))] != 0
2370           && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
2371         {
2372           rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
2373           return simplify_gen_subreg (GET_MODE (x), map_val,
2374                                       GET_MODE (SUBREG_REG (x)),
2375                                       SUBREG_BYTE (x));
2376         }
2377       break;
2378
2379     case SET:
2380       if (replace_dest)
2381         SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
2382
2383       else if (MEM_P (SET_DEST (x))
2384                || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
2385         /* Even if we are not to replace destinations, replace register if it
2386            is CONTAINED in destination (destination is memory or
2387            STRICT_LOW_PART).  */
2388         XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
2389                                                reg_map, nregs, 0);
2390       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
2391         /* Similarly, for ZERO_EXTRACT we replace all operands.  */
2392         break;
2393
2394       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
2395       return x;
2396
2397     default:
2398       break;
2399     }
2400
2401   fmt = GET_RTX_FORMAT (code);
2402   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2403     {
2404       if (fmt[i] == 'e')
2405         XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
2406       else if (fmt[i] == 'E')
2407         {
2408           int j;
2409           for (j = 0; j < XVECLEN (x, i); j++)
2410             XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
2411                                               nregs, replace_dest);
2412         }
2413     }
2414   return x;
2415 }
2416
2417 /* Replace occurrences of the old label in *X with the new one.
2418    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2419
2420 int
2421 replace_label (rtx *x, void *data)
2422 {
2423   rtx l = *x;
2424   rtx old_label = ((replace_label_data *) data)->r1;
2425   rtx new_label = ((replace_label_data *) data)->r2;
2426   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2427
2428   if (l == NULL_RTX)
2429     return 0;
2430
2431   if (GET_CODE (l) == SYMBOL_REF
2432       && CONSTANT_POOL_ADDRESS_P (l))
2433     {
2434       rtx c = get_pool_constant (l);
2435       if (rtx_referenced_p (old_label, c))
2436         {
2437           rtx new_c, new_l;
2438           replace_label_data *d = (replace_label_data *) data;
2439
2440           /* Create a copy of constant C; replace the label inside
2441              but do not update LABEL_NUSES because uses in constant pool
2442              are not counted.  */
2443           new_c = copy_rtx (c);
2444           d->update_label_nuses = false;
2445           for_each_rtx (&new_c, replace_label, data);
2446           d->update_label_nuses = update_label_nuses;
2447
2448           /* Add the new constant NEW_C to constant pool and replace
2449              the old reference to constant by new reference.  */
2450           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2451           *x = replace_rtx (l, l, new_l);
2452         }
2453       return 0;
2454     }
2455
2456   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2457      field.  This is not handled by for_each_rtx because it doesn't
2458      handle unprinted ('0') fields.  */
2459   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2460     JUMP_LABEL (l) = new_label;
2461
2462   if ((GET_CODE (l) == LABEL_REF
2463        || GET_CODE (l) == INSN_LIST)
2464       && XEXP (l, 0) == old_label)
2465     {
2466       XEXP (l, 0) = new_label;
2467       if (update_label_nuses)
2468         {
2469           ++LABEL_NUSES (new_label);
2470           --LABEL_NUSES (old_label);
2471         }
2472       return 0;
2473     }
2474
2475   return 0;
2476 }
2477
2478 /* When *BODY is equal to X or X is directly referenced by *BODY
2479    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2480    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2481
2482 static int
2483 rtx_referenced_p_1 (rtx *body, void *x)
2484 {
2485   rtx y = (rtx) x;
2486
2487   if (*body == NULL_RTX)
2488     return y == NULL_RTX;
2489
2490   /* Return true if a label_ref *BODY refers to label Y.  */
2491   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2492     return XEXP (*body, 0) == y;
2493
2494   /* If *BODY is a reference to pool constant traverse the constant.  */
2495   if (GET_CODE (*body) == SYMBOL_REF
2496       && CONSTANT_POOL_ADDRESS_P (*body))
2497     return rtx_referenced_p (y, get_pool_constant (*body));
2498
2499   /* By default, compare the RTL expressions.  */
2500   return rtx_equal_p (*body, y);
2501 }
2502
2503 /* Return true if X is referenced in BODY.  */
2504
2505 int
2506 rtx_referenced_p (rtx x, rtx body)
2507 {
2508   return for_each_rtx (&body, rtx_referenced_p_1, x);
2509 }
2510
2511 /* If INSN is a tablejump return true and store the label (before jump table) to
2512    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2513
2514 bool
2515 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2516 {
2517   rtx label, table;
2518
2519   if (JUMP_P (insn)
2520       && (label = JUMP_LABEL (insn)) != NULL_RTX
2521       && (table = next_active_insn (label)) != NULL_RTX
2522       && JUMP_P (table)
2523       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2524           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2525     {
2526       if (labelp)
2527         *labelp = label;
2528       if (tablep)
2529         *tablep = table;
2530       return true;
2531     }
2532   return false;
2533 }
2534
2535 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2536    constant that is not in the constant pool and not in the condition
2537    of an IF_THEN_ELSE.  */
2538
2539 static int
2540 computed_jump_p_1 (rtx x)
2541 {
2542   enum rtx_code code = GET_CODE (x);
2543   int i, j;
2544   const char *fmt;
2545
2546   switch (code)
2547     {
2548     case LABEL_REF:
2549     case PC:
2550       return 0;
2551
2552     case CONST:
2553     case CONST_INT:
2554     case CONST_DOUBLE:
2555     case CONST_VECTOR:
2556     case SYMBOL_REF:
2557     case REG:
2558       return 1;
2559
2560     case MEM:
2561       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2562                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2563
2564     case IF_THEN_ELSE:
2565       return (computed_jump_p_1 (XEXP (x, 1))
2566               || computed_jump_p_1 (XEXP (x, 2)));
2567
2568     default:
2569       break;
2570     }
2571
2572   fmt = GET_RTX_FORMAT (code);
2573   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2574     {
2575       if (fmt[i] == 'e'
2576           && computed_jump_p_1 (XEXP (x, i)))
2577         return 1;
2578
2579       else if (fmt[i] == 'E')
2580         for (j = 0; j < XVECLEN (x, i); j++)
2581           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2582             return 1;
2583     }
2584
2585   return 0;
2586 }
2587
2588 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2589
2590    Tablejumps and casesi insns are not considered indirect jumps;
2591    we can recognize them by a (use (label_ref)).  */
2592
2593 int
2594 computed_jump_p (rtx insn)
2595 {
2596   int i;
2597   if (JUMP_P (insn))
2598     {
2599       rtx pat = PATTERN (insn);
2600
2601       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2602         return 0;
2603       else if (GET_CODE (pat) == PARALLEL)
2604         {
2605           int len = XVECLEN (pat, 0);
2606           int has_use_labelref = 0;
2607
2608           for (i = len - 1; i >= 0; i--)
2609             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2610                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2611                     == LABEL_REF))
2612               has_use_labelref = 1;
2613
2614           if (! has_use_labelref)
2615             for (i = len - 1; i >= 0; i--)
2616               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2617                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2618                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2619                 return 1;
2620         }
2621       else if (GET_CODE (pat) == SET
2622                && SET_DEST (pat) == pc_rtx
2623                && computed_jump_p_1 (SET_SRC (pat)))
2624         return 1;
2625     }
2626   return 0;
2627 }
2628
2629 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2630    calls.  Processes the subexpressions of EXP and passes them to F.  */
2631 static int
2632 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2633 {
2634   int result, i, j;
2635   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2636   rtx *x;
2637
2638   for (; format[n] != '\0'; n++)
2639     {
2640       switch (format[n])
2641         {
2642         case 'e':
2643           /* Call F on X.  */
2644           x = &XEXP (exp, n);
2645           result = (*f) (x, data);
2646           if (result == -1)
2647             /* Do not traverse sub-expressions.  */
2648             continue;
2649           else if (result != 0)
2650             /* Stop the traversal.  */
2651             return result;
2652
2653           if (*x == NULL_RTX)
2654             /* There are no sub-expressions.  */
2655             continue;
2656
2657           i = non_rtx_starting_operands[GET_CODE (*x)];
2658           if (i >= 0)
2659             {
2660               result = for_each_rtx_1 (*x, i, f, data);
2661               if (result != 0)
2662                 return result;
2663             }
2664           break;
2665
2666         case 'V':
2667         case 'E':
2668           if (XVEC (exp, n) == 0)
2669             continue;
2670           for (j = 0; j < XVECLEN (exp, n); ++j)
2671             {
2672               /* Call F on X.  */
2673               x = &XVECEXP (exp, n, j);
2674               result = (*f) (x, data);
2675               if (result == -1)
2676                 /* Do not traverse sub-expressions.  */
2677                 continue;
2678               else if (result != 0)
2679                 /* Stop the traversal.  */
2680                 return result;
2681
2682               if (*x == NULL_RTX)
2683                 /* There are no sub-expressions.  */
2684                 continue;
2685
2686               i = non_rtx_starting_operands[GET_CODE (*x)];
2687               if (i >= 0)
2688                 {
2689                   result = for_each_rtx_1 (*x, i, f, data);
2690                   if (result != 0)
2691                     return result;
2692                 }
2693             }
2694           break;
2695
2696         default:
2697           /* Nothing to do.  */
2698           break;
2699         }
2700     }
2701
2702   return 0;
2703 }
2704
2705 /* Traverse X via depth-first search, calling F for each
2706    sub-expression (including X itself).  F is also passed the DATA.
2707    If F returns -1, do not traverse sub-expressions, but continue
2708    traversing the rest of the tree.  If F ever returns any other
2709    nonzero value, stop the traversal, and return the value returned
2710    by F.  Otherwise, return 0.  This function does not traverse inside
2711    tree structure that contains RTX_EXPRs, or into sub-expressions
2712    whose format code is `0' since it is not known whether or not those
2713    codes are actually RTL.
2714
2715    This routine is very general, and could (should?) be used to
2716    implement many of the other routines in this file.  */
2717
2718 int
2719 for_each_rtx (rtx *x, rtx_function f, void *data)
2720 {
2721   int result;
2722   int i;
2723
2724   /* Call F on X.  */
2725   result = (*f) (x, data);
2726   if (result == -1)
2727     /* Do not traverse sub-expressions.  */
2728     return 0;
2729   else if (result != 0)
2730     /* Stop the traversal.  */
2731     return result;
2732
2733   if (*x == NULL_RTX)
2734     /* There are no sub-expressions.  */
2735     return 0;
2736
2737   i = non_rtx_starting_operands[GET_CODE (*x)];
2738   if (i < 0)
2739     return 0;
2740
2741   return for_each_rtx_1 (*x, i, f, data);
2742 }
2743
2744
2745 /* Searches X for any reference to REGNO, returning the rtx of the
2746    reference found if any.  Otherwise, returns NULL_RTX.  */
2747
2748 rtx
2749 regno_use_in (unsigned int regno, rtx x)
2750 {
2751   const char *fmt;
2752   int i, j;
2753   rtx tem;
2754
2755   if (REG_P (x) && REGNO (x) == regno)
2756     return x;
2757
2758   fmt = GET_RTX_FORMAT (GET_CODE (x));
2759   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2760     {
2761       if (fmt[i] == 'e')
2762         {
2763           if ((tem = regno_use_in (regno, XEXP (x, i))))
2764             return tem;
2765         }
2766       else if (fmt[i] == 'E')
2767         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2768           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2769             return tem;
2770     }
2771
2772   return NULL_RTX;
2773 }
2774
2775 /* Return a value indicating whether OP, an operand of a commutative
2776    operation, is preferred as the first or second operand.  The higher
2777    the value, the stronger the preference for being the first operand.
2778    We use negative values to indicate a preference for the first operand
2779    and positive values for the second operand.  */
2780
2781 int
2782 commutative_operand_precedence (rtx op)
2783 {
2784   enum rtx_code code = GET_CODE (op);
2785
2786   /* Constants always come the second operand.  Prefer "nice" constants.  */
2787   if (code == CONST_INT)
2788     return -7;
2789   if (code == CONST_DOUBLE)
2790     return -6;
2791   op = avoid_constant_pool_reference (op);
2792   code = GET_CODE (op);
2793
2794   switch (GET_RTX_CLASS (code))
2795     {
2796     case RTX_CONST_OBJ:
2797       if (code == CONST_INT)
2798         return -5;
2799       if (code == CONST_DOUBLE)
2800         return -4;
2801       return -3;
2802
2803     case RTX_EXTRA:
2804       /* SUBREGs of objects should come second.  */
2805       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2806         return -2;
2807
2808       if (!CONSTANT_P (op))
2809         return 0;
2810       else
2811         /* As for RTX_CONST_OBJ.  */
2812         return -3;
2813
2814     case RTX_OBJ:
2815       /* Complex expressions should be the first, so decrease priority
2816          of objects.  */
2817       return -1;
2818
2819     case RTX_COMM_ARITH:
2820       /* Prefer operands that are themselves commutative to be first.
2821          This helps to make things linear.  In particular,
2822          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2823       return 4;
2824
2825     case RTX_BIN_ARITH:
2826       /* If only one operand is a binary expression, it will be the first
2827          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2828          is canonical, although it will usually be further simplified.  */
2829       return 2;
2830
2831     case RTX_UNARY:
2832       /* Then prefer NEG and NOT.  */
2833       if (code == NEG || code == NOT)
2834         return 1;
2835
2836     default:
2837       return 0;
2838     }
2839 }
2840
2841 /* Return 1 iff it is necessary to swap operands of commutative operation
2842    in order to canonicalize expression.  */
2843
2844 int
2845 swap_commutative_operands_p (rtx x, rtx y)
2846 {
2847   return (commutative_operand_precedence (x)
2848           < commutative_operand_precedence (y));
2849 }
2850
2851 /* Return 1 if X is an autoincrement side effect and the register is
2852    not the stack pointer.  */
2853 int
2854 auto_inc_p (rtx x)
2855 {
2856   switch (GET_CODE (x))
2857     {
2858     case PRE_INC:
2859     case POST_INC:
2860     case PRE_DEC:
2861     case POST_DEC:
2862     case PRE_MODIFY:
2863     case POST_MODIFY:
2864       /* There are no REG_INC notes for SP.  */
2865       if (XEXP (x, 0) != stack_pointer_rtx)
2866         return 1;
2867     default:
2868       break;
2869     }
2870   return 0;
2871 }
2872
2873 /* Return 1 if the sequence of instructions beginning with FROM and up
2874    to and including TO is safe to move.  If NEW_TO is non-NULL, and
2875    the sequence is not already safe to move, but can be easily
2876    extended to a sequence which is safe, then NEW_TO will point to the
2877    end of the extended sequence.
2878
2879    For now, this function only checks that the region contains whole
2880    exception regions, but it could be extended to check additional
2881    conditions as well.  */
2882
2883 int
2884 insns_safe_to_move_p (rtx from, rtx to, rtx *new_to)
2885 {
2886   int eh_region_count = 0;
2887   int past_to_p = 0;
2888   rtx r = from;
2889
2890   /* By default, assume the end of the region will be what was
2891      suggested.  */
2892   if (new_to)
2893     *new_to = to;
2894
2895   while (r)
2896     {
2897       if (NOTE_P (r))
2898         {
2899           switch (NOTE_LINE_NUMBER (r))
2900             {
2901             case NOTE_INSN_EH_REGION_BEG:
2902               ++eh_region_count;
2903               break;
2904
2905             case NOTE_INSN_EH_REGION_END:
2906               if (eh_region_count == 0)
2907                 /* This sequence of instructions contains the end of
2908                    an exception region, but not he beginning.  Moving
2909                    it will cause chaos.  */
2910                 return 0;
2911
2912               --eh_region_count;
2913               break;
2914
2915             default:
2916               break;
2917             }
2918         }
2919       else if (past_to_p)
2920         /* If we've passed TO, and we see a non-note instruction, we
2921            can't extend the sequence to a movable sequence.  */
2922         return 0;
2923
2924       if (r == to)
2925         {
2926           if (!new_to)
2927             /* It's OK to move the sequence if there were matched sets of
2928                exception region notes.  */
2929             return eh_region_count == 0;
2930
2931           past_to_p = 1;
2932         }
2933
2934       /* It's OK to move the sequence if there were matched sets of
2935          exception region notes.  */
2936       if (past_to_p && eh_region_count == 0)
2937         {
2938           *new_to = r;
2939           return 1;
2940         }
2941
2942       /* Go to the next instruction.  */
2943       r = NEXT_INSN (r);
2944     }
2945
2946   return 0;
2947 }
2948
2949 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2950 int
2951 loc_mentioned_in_p (rtx *loc, rtx in)
2952 {
2953   enum rtx_code code = GET_CODE (in);
2954   const char *fmt = GET_RTX_FORMAT (code);
2955   int i, j;
2956
2957   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2958     {
2959       if (loc == &in->u.fld[i].rt_rtx)
2960         return 1;
2961       if (fmt[i] == 'e')
2962         {
2963           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2964             return 1;
2965         }
2966       else if (fmt[i] == 'E')
2967         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2968           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2969             return 1;
2970     }
2971   return 0;
2972 }
2973
2974 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
2975    and SUBREG_BYTE, return the bit offset where the subreg begins
2976    (counting from the least significant bit of the operand).  */
2977
2978 unsigned int
2979 subreg_lsb_1 (enum machine_mode outer_mode,
2980               enum machine_mode inner_mode,
2981               unsigned int subreg_byte)
2982 {
2983   unsigned int bitpos;
2984   unsigned int byte;
2985   unsigned int word;
2986
2987   /* A paradoxical subreg begins at bit position 0.  */
2988   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
2989     return 0;
2990
2991   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2992     /* If the subreg crosses a word boundary ensure that
2993        it also begins and ends on a word boundary.  */
2994     gcc_assert (!((subreg_byte % UNITS_PER_WORD
2995                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
2996                   && (subreg_byte % UNITS_PER_WORD
2997                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
2998
2999   if (WORDS_BIG_ENDIAN)
3000     word = (GET_MODE_SIZE (inner_mode)
3001             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3002   else
3003     word = subreg_byte / UNITS_PER_WORD;
3004   bitpos = word * BITS_PER_WORD;
3005
3006   if (BYTES_BIG_ENDIAN)
3007     byte = (GET_MODE_SIZE (inner_mode)
3008             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3009   else
3010     byte = subreg_byte % UNITS_PER_WORD;
3011   bitpos += byte * BITS_PER_UNIT;
3012
3013   return bitpos;
3014 }
3015
3016 /* Given a subreg X, return the bit offset where the subreg begins
3017    (counting from the least significant bit of the reg).  */
3018
3019 unsigned int
3020 subreg_lsb (rtx x)
3021 {
3022   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3023                        SUBREG_BYTE (x));
3024 }
3025
3026 /* This function returns the regno offset of a subreg expression.
3027    xregno - A regno of an inner hard subreg_reg (or what will become one).
3028    xmode  - The mode of xregno.
3029    offset - The byte offset.
3030    ymode  - The mode of a top level SUBREG (or what may become one).
3031    RETURN - The regno offset which would be used.  */
3032 unsigned int
3033 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3034                      unsigned int offset, enum machine_mode ymode)
3035 {
3036   int nregs_xmode, nregs_ymode;
3037   int mode_multiple, nregs_multiple;
3038   int y_offset;
3039
3040   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3041
3042   nregs_xmode = hard_regno_nregs[xregno][xmode];
3043   nregs_ymode = hard_regno_nregs[xregno][ymode];
3044
3045   /* If this is a big endian paradoxical subreg, which uses more actual
3046      hard registers than the original register, we must return a negative
3047      offset so that we find the proper highpart of the register.  */
3048   if (offset == 0
3049       && nregs_ymode > nregs_xmode
3050       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3051           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3052     return nregs_xmode - nregs_ymode;
3053
3054   if (offset == 0 || nregs_xmode == nregs_ymode)
3055     return 0;
3056
3057   /* size of ymode must not be greater than the size of xmode.  */
3058   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3059   gcc_assert (mode_multiple != 0);
3060
3061   y_offset = offset / GET_MODE_SIZE (ymode);
3062   nregs_multiple =  nregs_xmode / nregs_ymode;
3063   return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3064 }
3065
3066 /* This function returns true when the offset is representable via
3067    subreg_offset in the given regno.
3068    xregno - A regno of an inner hard subreg_reg (or what will become one).
3069    xmode  - The mode of xregno.
3070    offset - The byte offset.
3071    ymode  - The mode of a top level SUBREG (or what may become one).
3072    RETURN - The regno offset which would be used.  */
3073 bool
3074 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3075                                unsigned int offset, enum machine_mode ymode)
3076 {
3077   int nregs_xmode, nregs_ymode;
3078   int mode_multiple, nregs_multiple;
3079   int y_offset;
3080
3081   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3082
3083   nregs_xmode = hard_regno_nregs[xregno][xmode];
3084   nregs_ymode = hard_regno_nregs[xregno][ymode];
3085
3086   /* Paradoxical subregs are always valid.  */
3087   if (offset == 0
3088       && nregs_ymode > nregs_xmode
3089       && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3090           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
3091     return true;
3092
3093   /* Lowpart subregs are always valid.  */
3094   if (offset == subreg_lowpart_offset (ymode, xmode))
3095     return true;
3096
3097   /* This should always pass, otherwise we don't know how to verify the
3098      constraint.  These conditions may be relaxed but subreg_offset would
3099      need to be redesigned.  */
3100   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3101   gcc_assert ((GET_MODE_SIZE (ymode) % nregs_ymode) == 0);
3102   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3103
3104   /* The XMODE value can be seen as a vector of NREGS_XMODE
3105      values.  The subreg must represent a lowpart of given field.
3106      Compute what field it is.  */
3107   offset -= subreg_lowpart_offset (ymode,
3108                                    mode_for_size (GET_MODE_BITSIZE (xmode)
3109                                                   / nregs_xmode,
3110                                                   MODE_INT, 0));
3111
3112   /* size of ymode must not be greater than the size of xmode.  */
3113   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3114   gcc_assert (mode_multiple != 0);
3115
3116   y_offset = offset / GET_MODE_SIZE (ymode);
3117   nregs_multiple =  nregs_xmode / nregs_ymode;
3118
3119   gcc_assert ((offset % GET_MODE_SIZE (ymode)) == 0);
3120   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3121
3122   return (!(y_offset % (mode_multiple / nregs_multiple)));
3123 }
3124
3125 /* Return the final regno that a subreg expression refers to.  */
3126 unsigned int
3127 subreg_regno (rtx x)
3128 {
3129   unsigned int ret;
3130   rtx subreg = SUBREG_REG (x);
3131   int regno = REGNO (subreg);
3132
3133   ret = regno + subreg_regno_offset (regno,
3134                                      GET_MODE (subreg),
3135                                      SUBREG_BYTE (x),
3136                                      GET_MODE (x));
3137   return ret;
3138
3139 }
3140 struct parms_set_data
3141 {
3142   int nregs;
3143   HARD_REG_SET regs;
3144 };
3145
3146 /* Helper function for noticing stores to parameter registers.  */
3147 static void
3148 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3149 {
3150   struct parms_set_data *d = data;
3151   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3152       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3153     {
3154       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3155       d->nregs--;
3156     }
3157 }
3158
3159 /* Look backward for first parameter to be loaded.
3160    Note that loads of all parameters will not necessarily be
3161    found if CSE has eliminated some of them (e.g., an argument
3162    to the outer function is passed down as a parameter).
3163    Do not skip BOUNDARY.  */
3164 rtx
3165 find_first_parameter_load (rtx call_insn, rtx boundary)
3166 {
3167   struct parms_set_data parm;
3168   rtx p, before, first_set;
3169
3170   /* Since different machines initialize their parameter registers
3171      in different orders, assume nothing.  Collect the set of all
3172      parameter registers.  */
3173   CLEAR_HARD_REG_SET (parm.regs);
3174   parm.nregs = 0;
3175   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3176     if (GET_CODE (XEXP (p, 0)) == USE
3177         && REG_P (XEXP (XEXP (p, 0), 0)))
3178       {
3179         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3180
3181         /* We only care about registers which can hold function
3182            arguments.  */
3183         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3184           continue;
3185
3186         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3187         parm.nregs++;
3188       }
3189   before = call_insn;
3190   first_set = call_insn;
3191
3192   /* Search backward for the first set of a register in this set.  */
3193   while (parm.nregs && before != boundary)
3194     {
3195       before = PREV_INSN (before);
3196
3197       /* It is possible that some loads got CSEed from one call to
3198          another.  Stop in that case.  */
3199       if (CALL_P (before))
3200         break;
3201
3202       /* Our caller needs either ensure that we will find all sets
3203          (in case code has not been optimized yet), or take care
3204          for possible labels in a way by setting boundary to preceding
3205          CODE_LABEL.  */
3206       if (LABEL_P (before))
3207         {
3208           gcc_assert (before == boundary);
3209           break;
3210         }
3211
3212       if (INSN_P (before))
3213         {
3214           int nregs_old = parm.nregs;
3215           note_stores (PATTERN (before), parms_set, &parm);
3216           /* If we found something that did not set a parameter reg,
3217              we're done.  Do not keep going, as that might result
3218              in hoisting an insn before the setting of a pseudo
3219              that is used by the hoisted insn. */
3220           if (nregs_old != parm.nregs)
3221             first_set = before;
3222           else
3223             break;
3224         }
3225     }
3226   return first_set;
3227 }
3228
3229 /* Return true if we should avoid inserting code between INSN and preceding
3230    call instruction.  */
3231
3232 bool
3233 keep_with_call_p (rtx insn)
3234 {
3235   rtx set;
3236
3237   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3238     {
3239       if (REG_P (SET_DEST (set))
3240           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3241           && fixed_regs[REGNO (SET_DEST (set))]
3242           && general_operand (SET_SRC (set), VOIDmode))
3243         return true;
3244       if (REG_P (SET_SRC (set))
3245           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3246           && REG_P (SET_DEST (set))
3247           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3248         return true;
3249       /* There may be a stack pop just after the call and before the store
3250          of the return register.  Search for the actual store when deciding
3251          if we can break or not.  */
3252       if (SET_DEST (set) == stack_pointer_rtx)
3253         {
3254           rtx i2 = next_nonnote_insn (insn);
3255           if (i2 && keep_with_call_p (i2))
3256             return true;
3257         }
3258     }
3259   return false;
3260 }
3261
3262 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3263    to non-complex jumps.  That is, direct unconditional, conditional,
3264    and tablejumps, but not computed jumps or returns.  It also does
3265    not apply to the fallthru case of a conditional jump.  */
3266
3267 bool
3268 label_is_jump_target_p (rtx label, rtx jump_insn)
3269 {
3270   rtx tmp = JUMP_LABEL (jump_insn);
3271
3272   if (label == tmp)
3273     return true;
3274
3275   if (tablejump_p (jump_insn, NULL, &tmp))
3276     {
3277       rtvec vec = XVEC (PATTERN (tmp),
3278                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3279       int i, veclen = GET_NUM_ELEM (vec);
3280
3281       for (i = 0; i < veclen; ++i)
3282         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3283           return true;
3284     }
3285
3286   return false;
3287 }
3288
3289 \f
3290 /* Return an estimate of the cost of computing rtx X.
3291    One use is in cse, to decide which expression to keep in the hash table.
3292    Another is in rtl generation, to pick the cheapest way to multiply.
3293    Other uses like the latter are expected in the future.  */
3294
3295 int
3296 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3297 {
3298   int i, j;
3299   enum rtx_code code;
3300   const char *fmt;
3301   int total;
3302
3303   if (x == 0)
3304     return 0;
3305
3306   /* Compute the default costs of certain things.
3307      Note that targetm.rtx_costs can override the defaults.  */
3308
3309   code = GET_CODE (x);
3310   switch (code)
3311     {
3312     case MULT:
3313       total = COSTS_N_INSNS (5);
3314       break;
3315     case DIV:
3316     case UDIV:
3317     case MOD:
3318     case UMOD:
3319       total = COSTS_N_INSNS (7);
3320       break;
3321     case USE:
3322       /* Used in loop.c and combine.c as a marker.  */
3323       total = 0;
3324       break;
3325     default:
3326       total = COSTS_N_INSNS (1);
3327     }
3328
3329   switch (code)
3330     {
3331     case REG:
3332       return 0;
3333
3334     case SUBREG:
3335       total = 0;
3336       /* If we can't tie these modes, make this expensive.  The larger
3337          the mode, the more expensive it is.  */
3338       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3339         return COSTS_N_INSNS (2
3340                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3341       break;
3342
3343     default:
3344       if (targetm.rtx_costs (x, code, outer_code, &total))
3345         return total;
3346       break;
3347     }
3348
3349   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3350      which is already in total.  */
3351
3352   fmt = GET_RTX_FORMAT (code);
3353   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3354     if (fmt[i] == 'e')
3355       total += rtx_cost (XEXP (x, i), code);
3356     else if (fmt[i] == 'E')
3357       for (j = 0; j < XVECLEN (x, i); j++)
3358         total += rtx_cost (XVECEXP (x, i, j), code);
3359
3360   return total;
3361 }
3362 \f
3363 /* Return cost of address expression X.
3364    Expect that X is properly formed address reference.  */
3365
3366 int
3367 address_cost (rtx x, enum machine_mode mode)
3368 {
3369   /* We may be asked for cost of various unusual addresses, such as operands
3370      of push instruction.  It is not worthwhile to complicate writing
3371      of the target hook by such cases.  */
3372
3373   if (!memory_address_p (mode, x))
3374     return 1000;
3375
3376   return targetm.address_cost (x);
3377 }
3378
3379 /* If the target doesn't override, compute the cost as with arithmetic.  */
3380
3381 int
3382 default_address_cost (rtx x)
3383 {
3384   return rtx_cost (x, MEM);
3385 }
3386 \f
3387
3388 unsigned HOST_WIDE_INT
3389 nonzero_bits (rtx x, enum machine_mode mode)
3390 {
3391   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3392 }
3393
3394 unsigned int
3395 num_sign_bit_copies (rtx x, enum machine_mode mode)
3396 {
3397   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3398 }
3399
3400 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3401    It avoids exponential behavior in nonzero_bits1 when X has
3402    identical subexpressions on the first or the second level.  */
3403
3404 static unsigned HOST_WIDE_INT
3405 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3406                      enum machine_mode known_mode,
3407                      unsigned HOST_WIDE_INT known_ret)
3408 {
3409   if (x == known_x && mode == known_mode)
3410     return known_ret;
3411
3412   /* Try to find identical subexpressions.  If found call
3413      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3414      precomputed value for the subexpression as KNOWN_RET.  */
3415
3416   if (ARITHMETIC_P (x))
3417     {
3418       rtx x0 = XEXP (x, 0);
3419       rtx x1 = XEXP (x, 1);
3420
3421       /* Check the first level.  */
3422       if (x0 == x1)
3423         return nonzero_bits1 (x, mode, x0, mode,
3424                               cached_nonzero_bits (x0, mode, known_x,
3425                                                    known_mode, known_ret));
3426
3427       /* Check the second level.  */
3428       if (ARITHMETIC_P (x0)
3429           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3430         return nonzero_bits1 (x, mode, x1, mode,
3431                               cached_nonzero_bits (x1, mode, known_x,
3432                                                    known_mode, known_ret));
3433
3434       if (ARITHMETIC_P (x1)
3435           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3436         return nonzero_bits1 (x, mode, x0, mode,
3437                               cached_nonzero_bits (x0, mode, known_x,
3438                                                    known_mode, known_ret));
3439     }
3440
3441   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3442 }
3443
3444 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3445    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3446    is less useful.  We can't allow both, because that results in exponential
3447    run time recursion.  There is a nullstone testcase that triggered
3448    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3449 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3450
3451 /* Given an expression, X, compute which bits in X can be nonzero.
3452    We don't care about bits outside of those defined in MODE.
3453
3454    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3455    an arithmetic operation, we can do better.  */
3456
3457 static unsigned HOST_WIDE_INT
3458 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3459                enum machine_mode known_mode,
3460                unsigned HOST_WIDE_INT known_ret)
3461 {
3462   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3463   unsigned HOST_WIDE_INT inner_nz;
3464   enum rtx_code code;
3465   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3466
3467   /* For floating-point values, assume all bits are needed.  */
3468   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3469     return nonzero;
3470
3471   /* If X is wider than MODE, use its mode instead.  */
3472   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3473     {
3474       mode = GET_MODE (x);
3475       nonzero = GET_MODE_MASK (mode);
3476       mode_width = GET_MODE_BITSIZE (mode);
3477     }
3478
3479   if (mode_width > HOST_BITS_PER_WIDE_INT)
3480     /* Our only callers in this case look for single bit values.  So
3481        just return the mode mask.  Those tests will then be false.  */
3482     return nonzero;
3483
3484 #ifndef WORD_REGISTER_OPERATIONS
3485   /* If MODE is wider than X, but both are a single word for both the host
3486      and target machines, we can compute this from which bits of the
3487      object might be nonzero in its own mode, taking into account the fact
3488      that on many CISC machines, accessing an object in a wider mode
3489      causes the high-order bits to become undefined.  So they are
3490      not known to be zero.  */
3491
3492   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3493       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3494       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3495       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3496     {
3497       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3498                                       known_x, known_mode, known_ret);
3499       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3500       return nonzero;
3501     }
3502 #endif
3503
3504   code = GET_CODE (x);
3505   switch (code)
3506     {
3507     case REG:
3508 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3509       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3510          all the bits above ptr_mode are known to be zero.  */
3511       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3512           && REG_POINTER (x))
3513         nonzero &= GET_MODE_MASK (ptr_mode);
3514 #endif
3515
3516       /* Include declared information about alignment of pointers.  */
3517       /* ??? We don't properly preserve REG_POINTER changes across
3518          pointer-to-integer casts, so we can't trust it except for
3519          things that we know must be pointers.  See execute/960116-1.c.  */
3520       if ((x == stack_pointer_rtx
3521            || x == frame_pointer_rtx
3522            || x == arg_pointer_rtx)
3523           && REGNO_POINTER_ALIGN (REGNO (x)))
3524         {
3525           unsigned HOST_WIDE_INT alignment
3526             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3527
3528 #ifdef PUSH_ROUNDING
3529           /* If PUSH_ROUNDING is defined, it is possible for the
3530              stack to be momentarily aligned only to that amount,
3531              so we pick the least alignment.  */
3532           if (x == stack_pointer_rtx && PUSH_ARGS)
3533             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3534                              alignment);
3535 #endif
3536
3537           nonzero &= ~(alignment - 1);
3538         }
3539
3540       {
3541         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3542         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3543                                               known_mode, known_ret,
3544                                               &nonzero_for_hook);
3545
3546         if (new)
3547           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3548                                                    known_mode, known_ret);
3549
3550         return nonzero_for_hook;
3551       }
3552
3553     case CONST_INT:
3554 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3555       /* If X is negative in MODE, sign-extend the value.  */
3556       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3557           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3558         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3559 #endif
3560
3561       return INTVAL (x);
3562
3563     case MEM:
3564 #ifdef LOAD_EXTEND_OP
3565       /* In many, if not most, RISC machines, reading a byte from memory
3566          zeros the rest of the register.  Noticing that fact saves a lot
3567          of extra zero-extends.  */
3568       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3569         nonzero &= GET_MODE_MASK (GET_MODE (x));
3570 #endif
3571       break;
3572
3573     case EQ:  case NE:
3574     case UNEQ:  case LTGT:
3575     case GT:  case GTU:  case UNGT:
3576     case LT:  case LTU:  case UNLT:
3577     case GE:  case GEU:  case UNGE:
3578     case LE:  case LEU:  case UNLE:
3579     case UNORDERED: case ORDERED:
3580
3581       /* If this produces an integer result, we know which bits are set.
3582          Code here used to clear bits outside the mode of X, but that is
3583          now done above.  */
3584
3585       if (GET_MODE_CLASS (mode) == MODE_INT
3586           && mode_width <= HOST_BITS_PER_WIDE_INT)
3587         nonzero = STORE_FLAG_VALUE;
3588       break;
3589
3590     case NEG:
3591 #if 0
3592       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3593          and num_sign_bit_copies.  */
3594       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3595           == GET_MODE_BITSIZE (GET_MODE (x)))
3596         nonzero = 1;
3597 #endif
3598
3599       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3600         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3601       break;
3602
3603     case ABS:
3604 #if 0
3605       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3606          and num_sign_bit_copies.  */
3607       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3608           == GET_MODE_BITSIZE (GET_MODE (x)))
3609         nonzero = 1;
3610 #endif
3611       break;
3612
3613     case TRUNCATE:
3614       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
3615                                        known_x, known_mode, known_ret)
3616                   & GET_MODE_MASK (mode));
3617       break;
3618
3619     case ZERO_EXTEND:
3620       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3621                                       known_x, known_mode, known_ret);
3622       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3623         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3624       break;
3625
3626     case SIGN_EXTEND:
3627       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
3628          Otherwise, show all the bits in the outer mode but not the inner
3629          may be nonzero.  */
3630       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
3631                                       known_x, known_mode, known_ret);
3632       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3633         {
3634           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3635           if (inner_nz
3636               & (((HOST_WIDE_INT) 1
3637                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
3638             inner_nz |= (GET_MODE_MASK (mode)
3639                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
3640         }
3641
3642       nonzero &= inner_nz;
3643       break;
3644
3645     case AND:
3646       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3647                                        known_x, known_mode, known_ret)
3648                  & cached_nonzero_bits (XEXP (x, 1), mode,
3649                                         known_x, known_mode, known_ret);
3650       break;
3651
3652     case XOR:   case IOR:
3653     case UMIN:  case UMAX:  case SMIN:  case SMAX:
3654       {
3655         unsigned HOST_WIDE_INT nonzero0 =
3656           cached_nonzero_bits (XEXP (x, 0), mode,
3657                                known_x, known_mode, known_ret);
3658
3659         /* Don't call nonzero_bits for the second time if it cannot change
3660            anything.  */
3661         if ((nonzero & nonzero0) != nonzero)
3662           nonzero &= nonzero0
3663                      | cached_nonzero_bits (XEXP (x, 1), mode,
3664                                             known_x, known_mode, known_ret);
3665       }
3666       break;
3667
3668     case PLUS:  case MINUS:
3669     case MULT:
3670     case DIV:   case UDIV:
3671     case MOD:   case UMOD:
3672       /* We can apply the rules of arithmetic to compute the number of
3673          high- and low-order zero bits of these operations.  We start by
3674          computing the width (position of the highest-order nonzero bit)
3675          and the number of low-order zero bits for each value.  */
3676       {
3677         unsigned HOST_WIDE_INT nz0 =
3678           cached_nonzero_bits (XEXP (x, 0), mode,
3679                                known_x, known_mode, known_ret);
3680         unsigned HOST_WIDE_INT nz1 =
3681           cached_nonzero_bits (XEXP (x, 1), mode,
3682                                known_x, known_mode, known_ret);
3683         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
3684         int width0 = floor_log2 (nz0) + 1;
3685         int width1 = floor_log2 (nz1) + 1;
3686         int low0 = floor_log2 (nz0 & -nz0);
3687         int low1 = floor_log2 (nz1 & -nz1);
3688         HOST_WIDE_INT op0_maybe_minusp
3689           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
3690         HOST_WIDE_INT op1_maybe_minusp
3691           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
3692         unsigned int result_width = mode_width;
3693         int result_low = 0;
3694
3695         switch (code)
3696           {
3697           case PLUS:
3698             result_width = MAX (width0, width1) + 1;
3699             result_low = MIN (low0, low1);
3700             break;
3701           case MINUS:
3702             result_low = MIN (low0, low1);
3703             break;
3704           case MULT:
3705             result_width = width0 + width1;
3706             result_low = low0 + low1;
3707             break;
3708           case DIV:
3709             if (width1 == 0)
3710               break;
3711             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3712               result_width = width0;
3713             break;
3714           case UDIV:
3715             if (width1 == 0)
3716               break;
3717             result_width = width0;
3718             break;
3719           case MOD:
3720             if (width1 == 0)
3721               break;
3722             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3723               result_width = MIN (width0, width1);
3724             result_low = MIN (low0, low1);
3725             break;
3726           case UMOD:
3727             if (width1 == 0)
3728               break;
3729             result_width = MIN (width0, width1);
3730             result_low = MIN (low0, low1);
3731             break;
3732           default:
3733             gcc_unreachable ();
3734           }
3735
3736         if (result_width < mode_width)
3737           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
3738
3739         if (result_low > 0)
3740           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
3741
3742 #ifdef POINTERS_EXTEND_UNSIGNED
3743         /* If pointers extend unsigned and this is an addition or subtraction
3744            to a pointer in Pmode, all the bits above ptr_mode are known to be
3745            zero.  */
3746         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
3747             && (code == PLUS || code == MINUS)
3748             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
3749           nonzero &= GET_MODE_MASK (ptr_mode);
3750 #endif
3751       }
3752       break;
3753
3754     case ZERO_EXTRACT:
3755       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3756           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3757         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
3758       break;
3759
3760     case SUBREG:
3761       /* If this is a SUBREG formed for a promoted variable that has
3762          been zero-extended, we know that at least the high-order bits
3763          are zero, though others might be too.  */
3764
3765       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
3766         nonzero = GET_MODE_MASK (GET_MODE (x))
3767                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
3768                                          known_x, known_mode, known_ret);
3769
3770       /* If the inner mode is a single word for both the host and target
3771          machines, we can compute this from which bits of the inner
3772          object might be nonzero.  */
3773       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
3774           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
3775               <= HOST_BITS_PER_WIDE_INT))
3776         {
3777           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
3778                                           known_x, known_mode, known_ret);
3779
3780 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
3781           /* If this is a typical RISC machine, we only have to worry
3782              about the way loads are extended.  */
3783           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
3784                ? (((nonzero
3785                     & (((unsigned HOST_WIDE_INT) 1
3786                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
3787                    != 0))
3788                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
3789               || !MEM_P (SUBREG_REG (x)))
3790 #endif
3791             {
3792               /* On many CISC machines, accessing an object in a wider mode
3793                  causes the high-order bits to become undefined.  So they are
3794                  not known to be zero.  */
3795               if (GET_MODE_SIZE (GET_MODE (x))
3796                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3797                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
3798                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
3799             }
3800         }
3801       break;
3802
3803     case ASHIFTRT:
3804     case LSHIFTRT:
3805     case ASHIFT:
3806     case ROTATE:
3807       /* The nonzero bits are in two classes: any bits within MODE
3808          that aren't in GET_MODE (x) are always significant.  The rest of the
3809          nonzero bits are those that are significant in the operand of
3810          the shift when shifted the appropriate number of bits.  This
3811          shows that high-order bits are cleared by the right shift and
3812          low-order bits by left shifts.  */
3813       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3814           && INTVAL (XEXP (x, 1)) >= 0
3815           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3816         {
3817           enum machine_mode inner_mode = GET_MODE (x);
3818           unsigned int width = GET_MODE_BITSIZE (inner_mode);
3819           int count = INTVAL (XEXP (x, 1));
3820           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
3821           unsigned HOST_WIDE_INT op_nonzero =
3822             cached_nonzero_bits (XEXP (x, 0), mode,
3823                                  known_x, known_mode, known_ret);
3824           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
3825           unsigned HOST_WIDE_INT outer = 0;
3826
3827           if (mode_width > width)
3828             outer = (op_nonzero & nonzero & ~mode_mask);
3829
3830           if (code == LSHIFTRT)
3831             inner >>= count;
3832           else if (code == ASHIFTRT)
3833             {
3834               inner >>= count;
3835
3836               /* If the sign bit may have been nonzero before the shift, we
3837                  need to mark all the places it could have been copied to
3838                  by the shift as possibly nonzero.  */
3839               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
3840                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
3841             }
3842           else if (code == ASHIFT)
3843             inner <<= count;
3844           else
3845             inner = ((inner << (count % width)
3846                       | (inner >> (width - (count % width)))) & mode_mask);
3847
3848           nonzero &= (outer | inner);
3849         }
3850       break;
3851
3852     case FFS:
3853     case POPCOUNT:
3854       /* This is at most the number of bits in the mode.  */
3855       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
3856       break;
3857
3858     case CLZ:
3859       /* If CLZ has a known value at zero, then the nonzero bits are
3860          that value, plus the number of bits in the mode minus one.  */
3861       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3862         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3863       else
3864         nonzero = -1;
3865       break;
3866
3867     case CTZ:
3868       /* If CTZ has a known value at zero, then the nonzero bits are
3869          that value, plus the number of bits in the mode minus one.  */
3870       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3871         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3872       else
3873         nonzero = -1;
3874       break;
3875
3876     case PARITY:
3877       nonzero = 1;
3878       break;
3879
3880     case IF_THEN_ELSE:
3881       {
3882         unsigned HOST_WIDE_INT nonzero_true =
3883           cached_nonzero_bits (XEXP (x, 1), mode,
3884                                known_x, known_mode, known_ret);
3885
3886         /* Don't call nonzero_bits for the second time if it cannot change
3887            anything.  */
3888         if ((nonzero & nonzero_true) != nonzero)
3889           nonzero &= nonzero_true
3890                      | cached_nonzero_bits (XEXP (x, 2), mode,
3891                                             known_x, known_mode, known_ret);
3892       }
3893       break;
3894
3895     default:
3896       break;
3897     }
3898
3899   return nonzero;
3900 }
3901
3902 /* See the macro definition above.  */
3903 #undef cached_num_sign_bit_copies
3904
3905 \f
3906 /* The function cached_num_sign_bit_copies is a wrapper around
3907    num_sign_bit_copies1.  It avoids exponential behavior in
3908    num_sign_bit_copies1 when X has identical subexpressions on the
3909    first or the second level.  */
3910
3911 static unsigned int
3912 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
3913                             enum machine_mode known_mode,
3914                             unsigned int known_ret)
3915 {
3916   if (x == known_x && mode == known_mode)
3917     return known_ret;
3918
3919   /* Try to find identical subexpressions.  If found call
3920      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
3921      the precomputed value for the subexpression as KNOWN_RET.  */
3922
3923   if (ARITHMETIC_P (x))
3924     {
3925       rtx x0 = XEXP (x, 0);
3926       rtx x1 = XEXP (x, 1);
3927
3928       /* Check the first level.  */
3929       if (x0 == x1)
3930         return
3931           num_sign_bit_copies1 (x, mode, x0, mode,
3932                                 cached_num_sign_bit_copies (x0, mode, known_x,
3933                                                             known_mode,
3934                                                             known_ret));
3935
3936       /* Check the second level.  */
3937       if (ARITHMETIC_P (x0)
3938           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3939         return
3940           num_sign_bit_copies1 (x, mode, x1, mode,
3941                                 cached_num_sign_bit_copies (x1, mode, known_x,
3942                                                             known_mode,
3943                                                             known_ret));
3944
3945       if (ARITHMETIC_P (x1)
3946           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3947         return
3948           num_sign_bit_copies1 (x, mode, x0, mode,
3949                                 cached_num_sign_bit_copies (x0, mode, known_x,
3950                                                             known_mode,
3951                                                             known_ret));
3952     }
3953
3954   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
3955 }
3956
3957 /* Return the number of bits at the high-order end of X that are known to
3958    be equal to the sign bit.  X will be used in mode MODE; if MODE is
3959    VOIDmode, X will be used in its own mode.  The returned value  will always
3960    be between 1 and the number of bits in MODE.  */
3961
3962 static unsigned int
3963 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
3964                       enum machine_mode known_mode,
3965                       unsigned int known_ret)
3966 {
3967   enum rtx_code code = GET_CODE (x);
3968   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
3969   int num0, num1, result;
3970   unsigned HOST_WIDE_INT nonzero;
3971
3972   /* If we weren't given a mode, use the mode of X.  If the mode is still
3973      VOIDmode, we don't know anything.  Likewise if one of the modes is
3974      floating-point.  */
3975
3976   if (mode == VOIDmode)
3977     mode = GET_MODE (x);
3978
3979   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
3980     return 1;
3981
3982   /* For a smaller object, just ignore the high bits.  */
3983   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
3984     {
3985       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
3986                                          known_x, known_mode, known_ret);
3987       return MAX (1,
3988                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
3989     }
3990
3991   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
3992     {
3993 #ifndef WORD_REGISTER_OPERATIONS
3994   /* If this machine does not do all register operations on the entire
3995      register and MODE is wider than the mode of X, we can say nothing
3996      at all about the high-order bits.  */
3997       return 1;
3998 #else
3999       /* Likewise on machines that do, if the mode of the object is smaller
4000          than a word and loads of that size don't sign extend, we can say
4001          nothing about the high order bits.  */
4002       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4003 #ifdef LOAD_EXTEND_OP
4004           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4005 #endif
4006           )
4007         return 1;
4008 #endif
4009     }
4010
4011   switch (code)
4012     {
4013     case REG:
4014
4015 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4016       /* If pointers extend signed and this is a pointer in Pmode, say that
4017          all the bits above ptr_mode are known to be sign bit copies.  */
4018       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4019           && REG_POINTER (x))
4020         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4021 #endif
4022
4023       {
4024         unsigned int copies_for_hook = 1, copies = 1;
4025         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4026                                                      known_mode, known_ret,
4027                                                      &copies_for_hook);
4028
4029         if (new)
4030           copies = cached_num_sign_bit_copies (new, mode, known_x,
4031                                                known_mode, known_ret);
4032
4033         if (copies > 1 || copies_for_hook > 1)
4034           return MAX (copies, copies_for_hook);
4035
4036         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4037       }
4038       break;
4039
4040     case MEM:
4041 #ifdef LOAD_EXTEND_OP
4042       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4043       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4044         return MAX (1, ((int) bitwidth
4045                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4046 #endif
4047       break;
4048
4049     case CONST_INT:
4050       /* If the constant is negative, take its 1's complement and remask.
4051          Then see how many zero bits we have.  */
4052       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4053       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4054           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4055         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4056
4057       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4058
4059     case SUBREG:
4060       /* If this is a SUBREG for a promoted object that is sign-extended
4061          and we are looking at it in a wider mode, we know that at least the
4062          high-order bits are known to be sign bit copies.  */
4063
4064       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4065         {
4066           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4067                                              known_x, known_mode, known_ret);
4068           return MAX ((int) bitwidth
4069                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4070                       num0);
4071         }
4072
4073       /* For a smaller object, just ignore the high bits.  */
4074       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4075         {
4076           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4077                                              known_x, known_mode, known_ret);
4078           return MAX (1, (num0
4079                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4080                                    - bitwidth)));
4081         }
4082
4083 #ifdef WORD_REGISTER_OPERATIONS
4084 #ifdef LOAD_EXTEND_OP
4085       /* For paradoxical SUBREGs on machines where all register operations
4086          affect the entire register, just look inside.  Note that we are
4087          passing MODE to the recursive call, so the number of sign bit copies
4088          will remain relative to that mode, not the inner mode.  */
4089
4090       /* This works only if loads sign extend.  Otherwise, if we get a
4091          reload for the inner part, it may be loaded from the stack, and
4092          then we lose all sign bit copies that existed before the store
4093          to the stack.  */
4094
4095       if ((GET_MODE_SIZE (GET_MODE (x))
4096            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4097           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4098           && MEM_P (SUBREG_REG (x)))
4099         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4100                                            known_x, known_mode, known_ret);
4101 #endif
4102 #endif
4103       break;
4104
4105     case SIGN_EXTRACT:
4106       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4107         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4108       break;
4109
4110     case SIGN_EXTEND:
4111       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4112               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4113                                             known_x, known_mode, known_ret));
4114
4115     case TRUNCATE:
4116       /* For a smaller object, just ignore the high bits.  */
4117       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4118                                          known_x, known_mode, known_ret);
4119       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4120                                     - bitwidth)));
4121
4122     case NOT:
4123       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4124                                          known_x, known_mode, known_ret);
4125
4126     case ROTATE:       case ROTATERT:
4127       /* If we are rotating left by a number of bits less than the number
4128          of sign bit copies, we can just subtract that amount from the
4129          number.  */
4130       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4131           && INTVAL (XEXP (x, 1)) >= 0
4132           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4133         {
4134           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4135                                              known_x, known_mode, known_ret);
4136           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4137                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4138         }
4139       break;
4140
4141     case NEG:
4142       /* In general, this subtracts one sign bit copy.  But if the value
4143          is known to be positive, the number of sign bit copies is the
4144          same as that of the input.  Finally, if the input has just one bit
4145          that might be nonzero, all the bits are copies of the sign bit.  */
4146       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4147                                          known_x, known_mode, known_ret);
4148       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4149         return num0 > 1 ? num0 - 1 : 1;
4150
4151       nonzero = nonzero_bits (XEXP (x, 0), mode);
4152       if (nonzero == 1)
4153         return bitwidth;
4154
4155       if (num0 > 1
4156           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4157         num0--;
4158
4159       return num0;
4160
4161     case IOR:   case AND:   case XOR:
4162     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4163       /* Logical operations will preserve the number of sign-bit copies.
4164          MIN and MAX operations always return one of the operands.  */
4165       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4166                                          known_x, known_mode, known_ret);
4167       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4168                                          known_x, known_mode, known_ret);
4169       return MIN (num0, num1);
4170
4171     case PLUS:  case MINUS:
4172       /* For addition and subtraction, we can have a 1-bit carry.  However,
4173          if we are subtracting 1 from a positive number, there will not
4174          be such a carry.  Furthermore, if the positive number is known to
4175          be 0 or 1, we know the result is either -1 or 0.  */
4176
4177       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4178           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4179         {
4180           nonzero = nonzero_bits (XEXP (x, 0), mode);
4181           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4182             return (nonzero == 1 || nonzero == 0 ? bitwidth
4183                     : bitwidth - floor_log2 (nonzero) - 1);
4184         }
4185
4186       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4187                                          known_x, known_mode, known_ret);
4188       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4189                                          known_x, known_mode, known_ret);
4190       result = MAX (1, MIN (num0, num1) - 1);
4191
4192 #ifdef POINTERS_EXTEND_UNSIGNED
4193       /* If pointers extend signed and this is an addition or subtraction
4194          to a pointer in Pmode, all the bits above ptr_mode are known to be
4195          sign bit copies.  */
4196       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4197           && (code == PLUS || code == MINUS)
4198           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4199         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4200                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4201                       result);
4202 #endif
4203       return result;
4204
4205     case MULT:
4206       /* The number of bits of the product is the sum of the number of
4207          bits of both terms.  However, unless one of the terms if known
4208          to be positive, we must allow for an additional bit since negating
4209          a negative number can remove one sign bit copy.  */
4210
4211       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4212                                          known_x, known_mode, known_ret);
4213       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4214                                          known_x, known_mode, known_ret);
4215
4216       result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
4217       if (result > 0
4218           && (bitwidth > HOST_BITS_PER_WIDE_INT
4219               || (((nonzero_bits (XEXP (x, 0), mode)
4220                     & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4221                   && ((nonzero_bits (XEXP (x, 1), mode)
4222                        & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
4223         result--;
4224
4225       return MAX (1, result);
4226
4227     case UDIV:
4228       /* The result must be <= the first operand.  If the first operand
4229          has the high bit set, we know nothing about the number of sign
4230          bit copies.  */
4231       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4232         return 1;
4233       else if ((nonzero_bits (XEXP (x, 0), mode)
4234                 & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4235         return 1;
4236       else
4237         return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4238                                            known_x, known_mode, known_ret);
4239
4240     case UMOD:
4241       /* The result must be <= the second operand.  */
4242       return cached_num_sign_bit_copies (XEXP (x, 1), mode,
4243                                            known_x, known_mode, known_ret);
4244
4245     case DIV:
4246       /* Similar to unsigned division, except that we have to worry about
4247          the case where the divisor is negative, in which case we have
4248          to add 1.  */
4249       result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4250                                            known_x, known_mode, known_ret);
4251       if (result > 1
4252           && (bitwidth > HOST_BITS_PER_WIDE_INT
4253               || (nonzero_bits (XEXP (x, 1), mode)
4254                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4255         result--;
4256
4257       return result;
4258
4259     case MOD:
4260       result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4261                                            known_x, known_mode, known_ret);
4262       if (result > 1
4263           && (bitwidth > HOST_BITS_PER_WIDE_INT
4264               || (nonzero_bits (XEXP (x, 1), mode)
4265                   & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
4266         result--;
4267
4268       return result;
4269
4270     case ASHIFTRT:
4271       /* Shifts by a constant add to the number of bits equal to the
4272          sign bit.  */
4273       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4274                                          known_x, known_mode, known_ret);
4275       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4276           && INTVAL (XEXP (x, 1)) > 0)
4277         num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
4278
4279       return num0;
4280
4281     case ASHIFT:
4282       /* Left shifts destroy copies.  */
4283       if (GET_CODE (XEXP (x, 1)) != CONST_INT
4284           || INTVAL (XEXP (x, 1)) < 0
4285           || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
4286         return 1;
4287
4288       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4289                                          known_x, known_mode, known_ret);
4290       return MAX (1, num0 - INTVAL (XEXP (x, 1)));
4291
4292     case IF_THEN_ELSE:
4293       num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4294                                          known_x, known_mode, known_ret);
4295       num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
4296                                          known_x, known_mode, known_ret);
4297       return MIN (num0, num1);
4298
4299     case EQ:  case NE:  case GE:  case GT:  case LE:  case LT:
4300     case UNEQ:  case LTGT:  case UNGE:  case UNGT:  case UNLE:  case UNLT:
4301     case GEU: case GTU: case LEU: case LTU:
4302     case UNORDERED: case ORDERED:
4303       /* If the constant is negative, take its 1's complement and remask.
4304          Then see how many zero bits we have.  */
4305       nonzero = STORE_FLAG_VALUE;
4306       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4307           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4308         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4309
4310       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4311
4312     default:
4313       break;
4314     }
4315
4316   /* If we haven't been able to figure it out by one of the above rules,
4317      see if some of the high-order bits are known to be zero.  If so,
4318      count those bits and return one less than that amount.  If we can't
4319      safely compute the mask for this mode, always return BITWIDTH.  */
4320
4321   bitwidth = GET_MODE_BITSIZE (mode);
4322   if (bitwidth > HOST_BITS_PER_WIDE_INT)
4323     return 1;
4324
4325   nonzero = nonzero_bits (x, mode);
4326   return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
4327          ? 1 : bitwidth - floor_log2 (nonzero) - 1;
4328 }
4329
4330 /* Calculate the rtx_cost of a single instruction.  A return value of
4331    zero indicates an instruction pattern without a known cost.  */
4332
4333 int
4334 insn_rtx_cost (rtx pat)
4335 {
4336   int i, cost;
4337   rtx set;
4338
4339   /* Extract the single set rtx from the instruction pattern.
4340      We can't use single_set since we only have the pattern.  */
4341   if (GET_CODE (pat) == SET)
4342     set = pat;
4343   else if (GET_CODE (pat) == PARALLEL)
4344     {
4345       set = NULL_RTX;
4346       for (i = 0; i < XVECLEN (pat, 0); i++)
4347         {
4348           rtx x = XVECEXP (pat, 0, i);
4349           if (GET_CODE (x) == SET)
4350             {
4351               if (set)
4352                 return 0;
4353               set = x;
4354             }
4355         }
4356       if (!set)
4357         return 0;
4358     }
4359   else
4360     return 0;
4361
4362   cost = rtx_cost (SET_SRC (set), SET);
4363   return cost > 0 ? cost : COSTS_N_INSNS (1);
4364 }
4365
4366 /* Given an insn INSN and condition COND, return the condition in a
4367    canonical form to simplify testing by callers.  Specifically:
4368
4369    (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
4370    (2) Both operands will be machine operands; (cc0) will have been replaced.
4371    (3) If an operand is a constant, it will be the second operand.
4372    (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
4373        for GE, GEU, and LEU.
4374
4375    If the condition cannot be understood, or is an inequality floating-point
4376    comparison which needs to be reversed, 0 will be returned.
4377
4378    If REVERSE is nonzero, then reverse the condition prior to canonizing it.
4379
4380    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4381    insn used in locating the condition was found.  If a replacement test
4382    of the condition is desired, it should be placed in front of that
4383    insn and we will be sure that the inputs are still valid.
4384
4385    If WANT_REG is nonzero, we wish the condition to be relative to that
4386    register, if possible.  Therefore, do not canonicalize the condition
4387    further.  If ALLOW_CC_MODE is nonzero, allow the condition returned
4388    to be a compare to a CC mode register.
4389
4390    If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST
4391    and at INSN.  */
4392
4393 rtx
4394 canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest,
4395                         rtx want_reg, int allow_cc_mode, int valid_at_insn_p)
4396 {
4397   enum rtx_code code;
4398   rtx prev = insn;
4399   rtx set;
4400   rtx tem;
4401   rtx op0, op1;
4402   int reverse_code = 0;
4403   enum machine_mode mode;
4404
4405   code = GET_CODE (cond);
4406   mode = GET_MODE (cond);
4407   op0 = XEXP (cond, 0);
4408   op1 = XEXP (cond, 1);
4409
4410   if (reverse)
4411     code = reversed_comparison_code (cond, insn);
4412   if (code == UNKNOWN)
4413     return 0;
4414
4415   if (earliest)
4416     *earliest = insn;
4417
4418   /* If we are comparing a register with zero, see if the register is set
4419      in the previous insn to a COMPARE or a comparison operation.  Perform
4420      the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
4421      in cse.c  */
4422
4423   while ((GET_RTX_CLASS (code) == RTX_COMPARE
4424           || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
4425          && op1 == CONST0_RTX (GET_MODE (op0))
4426          && op0 != want_reg)
4427     {
4428       /* Set nonzero when we find something of interest.  */
4429       rtx x = 0;
4430
4431 #ifdef HAVE_cc0
4432       /* If comparison with cc0, import actual comparison from compare
4433          insn.  */
4434       if (op0 == cc0_rtx)
4435         {
4436           if ((prev = prev_nonnote_insn (prev)) == 0
4437               || !NONJUMP_INSN_P (prev)
4438               || (set = single_set (prev)) == 0
4439               || SET_DEST (set) != cc0_rtx)
4440             return 0;
4441
4442           op0 = SET_SRC (set);
4443           op1 = CONST0_RTX (GET_MODE (op0));
4444           if (earliest)
4445             *earliest = prev;
4446         }
4447 #endif
4448
4449       /* If this is a COMPARE, pick up the two things being compared.  */
4450       if (GET_CODE (op0) == COMPARE)
4451         {
4452           op1 = XEXP (op0, 1);
4453           op0 = XEXP (op0, 0);
4454           continue;
4455         }
4456       else if (!REG_P (op0))
4457         break;
4458
4459       /* Go back to the previous insn.  Stop if it is not an INSN.  We also
4460          stop if it isn't a single set or if it has a REG_INC note because
4461          we don't want to bother dealing with it.  */
4462
4463       if ((prev = prev_nonnote_insn (prev)) == 0
4464           || !NONJUMP_INSN_P (prev)
4465           || FIND_REG_INC_NOTE (prev, NULL_RTX))
4466         break;
4467
4468       set = set_of (op0, prev);
4469
4470       if (set
4471           && (GET_CODE (set) != SET
4472               || !rtx_equal_p (SET_DEST (set), op0)))
4473         break;
4474
4475       /* If this is setting OP0, get what it sets it to if it looks
4476          relevant.  */
4477       if (set)
4478         {
4479           enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
4480 #ifdef FLOAT_STORE_FLAG_VALUE
4481           REAL_VALUE_TYPE fsfv;
4482 #endif
4483
4484           /* ??? We may not combine comparisons done in a CCmode with
4485              comparisons not done in a CCmode.  This is to aid targets
4486              like Alpha that have an IEEE compliant EQ instruction, and
4487              a non-IEEE compliant BEQ instruction.  The use of CCmode is
4488              actually artificial, simply to prevent the combination, but
4489              should not affect other platforms.
4490
4491              However, we must allow VOIDmode comparisons to match either
4492              CCmode or non-CCmode comparison, because some ports have
4493              modeless comparisons inside branch patterns.
4494
4495              ??? This mode check should perhaps look more like the mode check
4496              in simplify_comparison in combine.  */
4497
4498           if ((GET_CODE (SET_SRC (set)) == COMPARE
4499                || (((code == NE
4500                      || (code == LT
4501                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4502                          && (GET_MODE_BITSIZE (inner_mode)
4503                              <= HOST_BITS_PER_WIDE_INT)
4504                          && (STORE_FLAG_VALUE
4505                              & ((HOST_WIDE_INT) 1
4506                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4507 #ifdef FLOAT_STORE_FLAG_VALUE
4508                      || (code == LT
4509                          && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
4510                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4511                              REAL_VALUE_NEGATIVE (fsfv)))
4512 #endif
4513                      ))
4514                    && COMPARISON_P (SET_SRC (set))))
4515               && (((GET_MODE_CLASS (mode) == MODE_CC)
4516                    == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4517                   || mode == VOIDmode || inner_mode == VOIDmode))
4518             x = SET_SRC (set);
4519           else if (((code == EQ
4520                      || (code == GE
4521                          && (GET_MODE_BITSIZE (inner_mode)
4522                              <= HOST_BITS_PER_WIDE_INT)
4523                          && GET_MODE_CLASS (inner_mode) == MODE_INT
4524                          && (STORE_FLAG_VALUE
4525                              & ((HOST_WIDE_INT) 1
4526                                 << (GET_MODE_BITSIZE (inner_mode) - 1))))
4527 #ifdef FLOAT_STORE_FLAG_VALUE
4528                      || (code == GE
4529                          && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
4530                          && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
4531                              REAL_VALUE_NEGATIVE (fsfv)))
4532 #endif
4533                      ))
4534                    && COMPARISON_P (SET_SRC (set))
4535                    && (((GET_MODE_CLASS (mode) == MODE_CC)
4536                         == (GET_MODE_CLASS (inner_mode) == MODE_CC))
4537                        || mode == VOIDmode || inner_mode == VOIDmode))
4538
4539             {
4540               reverse_code = 1;
4541               x = SET_SRC (set);
4542             }
4543           else
4544             break;
4545         }
4546
4547       else if (reg_set_p (op0, prev))
4548         /* If this sets OP0, but not directly, we have to give up.  */
4549         break;
4550
4551       if (x)
4552         {
4553           /* If the caller is expecting the condition to be valid at INSN,
4554              make sure X doesn't change before INSN.  */
4555           if (valid_at_insn_p)
4556             if (modified_in_p (x, prev) || modified_between_p (x, prev, insn))
4557               break;
4558           if (COMPARISON_P (x))
4559             code = GET_CODE (x);
4560           if (reverse_code)
4561             {
4562               code = reversed_comparison_code (x, prev);
4563               if (code == UNKNOWN)
4564                 return 0;
4565               reverse_code = 0;
4566             }
4567
4568           op0 = XEXP (x, 0), op1 = XEXP (x, 1);
4569           if (earliest)
4570             *earliest = prev;
4571         }
4572     }
4573
4574   /* If constant is first, put it last.  */
4575   if (CONSTANT_P (op0))
4576     code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
4577
4578   /* If OP0 is the result of a comparison, we weren't able to find what
4579      was really being compared, so fail.  */
4580   if (!allow_cc_mode
4581       && GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
4582     return 0;
4583
4584   /* Canonicalize any ordered comparison with integers involving equality
4585      if we can do computations in the relevant mode and we do not
4586      overflow.  */
4587
4588   if (GET_MODE_CLASS (GET_MODE (op0)) != MODE_CC
4589       && GET_CODE (op1) == CONST_INT
4590       && GET_MODE (op0) != VOIDmode
4591       && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
4592     {
4593       HOST_WIDE_INT const_val = INTVAL (op1);
4594       unsigned HOST_WIDE_INT uconst_val = const_val;
4595       unsigned HOST_WIDE_INT max_val
4596         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
4597
4598       switch (code)
4599         {
4600         case LE:
4601           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
4602             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
4603           break;
4604
4605         /* When cross-compiling, const_val might be sign-extended from
4606            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
4607         case GE:
4608           if ((HOST_WIDE_INT) (const_val & max_val)
4609               != (((HOST_WIDE_INT) 1
4610                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
4611             code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0));
4612           break;
4613
4614         case LEU:
4615           if (uconst_val < max_val)
4616             code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
4617           break;
4618
4619         case GEU:
4620           if (uconst_val != 0)
4621             code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
4622           break;
4623
4624         default:
4625           break;
4626         }
4627     }
4628
4629   /* Never return CC0; return zero instead.  */
4630   if (CC0_P (op0))
4631     return 0;
4632
4633   return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
4634 }
4635
4636 /* Given a jump insn JUMP, return the condition that will cause it to branch
4637    to its JUMP_LABEL.  If the condition cannot be understood, or is an
4638    inequality floating-point comparison which needs to be reversed, 0 will
4639    be returned.
4640
4641    If EARLIEST is nonzero, it is a pointer to a place where the earliest
4642    insn used in locating the condition was found.  If a replacement test
4643    of the condition is desired, it should be placed in front of that
4644    insn and we will be sure that the inputs are still valid.  If EARLIEST
4645    is null, the returned condition will be valid at INSN.
4646
4647    If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
4648    compare CC mode register.
4649
4650    VALID_AT_INSN_P is the same as for canonicalize_condition.  */
4651
4652 rtx
4653 get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p)
4654 {
4655   rtx cond;
4656   int reverse;
4657   rtx set;
4658
4659   /* If this is not a standard conditional jump, we can't parse it.  */
4660   if (!JUMP_P (jump)
4661       || ! any_condjump_p (jump))
4662     return 0;
4663   set = pc_set (jump);
4664
4665   cond = XEXP (SET_SRC (set), 0);
4666
4667   /* If this branches to JUMP_LABEL when the condition is false, reverse
4668      the condition.  */
4669   reverse
4670     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
4671       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
4672
4673   return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
4674                                  allow_cc_mode, valid_at_insn_p);
4675 }
4676
4677 \f
4678 /* Initialize non_rtx_starting_operands, which is used to speed up
4679    for_each_rtx.  */
4680 void
4681 init_rtlanal (void)
4682 {
4683   int i;
4684   for (i = 0; i < NUM_RTX_CODE; i++)
4685     {
4686       const char *format = GET_RTX_FORMAT (i);
4687       const char *first = strpbrk (format, "eEV");
4688       non_rtx_starting_operands[i] = first ? first - format : -1;
4689     }
4690 }