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