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