gcc/rtlanal.c

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