gcc/simplify-rtx.c

   1 /* RTL simplification functions for GNU compiler.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include <setjmp.h>
  26
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "regs.h"
  30 #include "hard-reg-set.h"
  31 #include "flags.h"
  32 #include "real.h"
  33 #include "insn-config.h"
  34 #include "recog.h"
  35 #include "function.h"
  36 #include "expr.h"
  37 #include "toplev.h"
  38 #include "output.h"
  39 #include "ggc.h"
  40 #include "obstack.h"
  41 #include "hashtab.h"
  42 #include "cselib.h"
  43
  44 /* Simplification and canonicalization of RTL.  */
  45
  46 /* Nonzero if X has the form (PLUS frame-pointer integer).  We check for
  47    virtual regs here because the simplify_*_operation routines are called
  48    by integrate.c, which is called before virtual register instantiation.
  49
  50    ?!? FIXED_BASE_PLUS_P and NONZERO_BASE_PLUS_P need to move into
  51    a header file so that their definitions can be shared with the
  52    simplification routines in simplify-rtx.c.  Until then, do not
  53    change these macros without also changing the copy in simplify-rtx.c.  */
  54
  55 #define FIXED_BASE_PLUS_P(X)                                    \
  56   ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx    \
  57    || ((X) == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])\
  58    || (X) == virtual_stack_vars_rtx                             \
  59    || (X) == virtual_incoming_args_rtx                          \
  60    || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
  61        && (XEXP (X, 0) == frame_pointer_rtx                     \
  62            || XEXP (X, 0) == hard_frame_pointer_rtx             \
  63            || ((X) == arg_pointer_rtx                           \
  64                && fixed_regs[ARG_POINTER_REGNUM])               \
  65            || XEXP (X, 0) == virtual_stack_vars_rtx             \
  66            || XEXP (X, 0) == virtual_incoming_args_rtx))        \
  67    || GET_CODE (X) == ADDRESSOF)
  68
  69 /* Similar, but also allows reference to the stack pointer.
  70
  71    This used to include FIXED_BASE_PLUS_P, however, we can't assume that
  72    arg_pointer_rtx by itself is nonzero, because on at least one machine,
  73    the i960, the arg pointer is zero when it is unused.  */
  74
  75 #define NONZERO_BASE_PLUS_P(X)                                  \
  76   ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx    \
  77    || (X) == virtual_stack_vars_rtx                             \
  78    || (X) == virtual_incoming_args_rtx                          \
  79    || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
  80        && (XEXP (X, 0) == frame_pointer_rtx                     \
  81            || XEXP (X, 0) == hard_frame_pointer_rtx             \
  82            || ((X) == arg_pointer_rtx                           \
  83                && fixed_regs[ARG_POINTER_REGNUM])               \
  84            || XEXP (X, 0) == virtual_stack_vars_rtx             \
  85            || XEXP (X, 0) == virtual_incoming_args_rtx))        \
  86    || (X) == stack_pointer_rtx                                  \
  87    || (X) == virtual_stack_dynamic_rtx                          \
  88    || (X) == virtual_outgoing_args_rtx                          \
  89    || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
  90        && (XEXP (X, 0) == stack_pointer_rtx                     \
  91            || XEXP (X, 0) == virtual_stack_dynamic_rtx          \
  92            || XEXP (X, 0) == virtual_outgoing_args_rtx))        \
  93    || GET_CODE (X) == ADDRESSOF)
  94
  95 /* Much code operates on (low, high) pairs; the low value is an
  96    unsigned wide int, the high value a signed wide int.  We
  97    occasionally need to sign extend from low to high as if low were a
  98    signed wide int.  */
  99 #define HWI_SIGN_EXTEND(low) \
 100  ((((HOST_WIDE_INT) low) < 0) ? ((HOST_WIDE_INT) -1) : ((HOST_WIDE_INT) 0))
 101
 102 static rtx simplify_plus_minus          PARAMS ((enum rtx_code,
 103                                                  enum machine_mode, rtx, rtx));
 104 static void check_fold_consts           PARAMS ((PTR));
 105 static int entry_and_rtx_equal_p        PARAMS ((const void *, const void *));
 106 static unsigned int get_value_hash      PARAMS ((const void *));
 107 static struct elt_list *new_elt_list    PARAMS ((struct elt_list *,
 108                                                  cselib_val *));
 109 static struct elt_loc_list *new_elt_loc_list PARAMS ((struct elt_loc_list *,
 110                                                       rtx));
 111 static void unchain_one_value           PARAMS ((cselib_val *));
 112 static void unchain_one_elt_list        PARAMS ((struct elt_list **));
 113 static void unchain_one_elt_loc_list    PARAMS ((struct elt_loc_list **));
 114 static void clear_table                 PARAMS ((void));
 115 static int discard_useless_locs         PARAMS ((void **, void *));
 116 static int discard_useless_values       PARAMS ((void **, void *));
 117 static void remove_useless_values       PARAMS ((void));
 118 static unsigned int hash_rtx            PARAMS ((rtx, enum machine_mode, int));
 119 static cselib_val *new_cselib_val       PARAMS ((unsigned int,
 120                                                  enum machine_mode));
 121 static void add_mem_for_addr            PARAMS ((cselib_val *, cselib_val *,
 122                                                  rtx));
 123 static cselib_val *cselib_lookup_mem    PARAMS ((rtx, int));
 124 static rtx cselib_subst_to_values       PARAMS ((rtx));
 125 static void cselib_invalidate_regno     PARAMS ((unsigned int,
 126                                                  enum machine_mode));
 127 static int cselib_mem_conflict_p        PARAMS ((rtx, rtx));
 128 static int cselib_invalidate_mem_1      PARAMS ((void **, void *));
 129 static void cselib_invalidate_mem       PARAMS ((rtx));
 130 static void cselib_invalidate_rtx       PARAMS ((rtx, rtx, void *));
 131 static void cselib_record_set           PARAMS ((rtx, cselib_val *,
 132                                                  cselib_val *));
 133 static void cselib_record_sets          PARAMS ((rtx));
 134
 135 /* There are three ways in which cselib can look up an rtx:
 136    - for a REG, the reg_values table (which is indexed by regno) is used
 137    - for a MEM, we recursively look up its address and then follow the
 138      addr_list of that value
 139    - for everything else, we compute a hash value and go through the hash
 140      table.  Since different rtx's can still have the same hash value,
 141      this involves walking the table entries for a given value and comparing
 142      the locations of the entries with the rtx we are looking up.  */
 143
 144 /* A table that enables us to look up elts by their value.  */
 145 static htab_t hash_table;
 146
 147 /* This is a global so we don't have to pass this through every function.
 148    It is used in new_elt_loc_list to set SETTING_INSN.  */
 149 static rtx cselib_current_insn;
 150
 151 /* Every new unknown value gets a unique number.  */
 152 static unsigned int next_unknown_value;
 153
 154 /* The number of registers we had when the varrays were last resized.  */
 155 static unsigned int cselib_nregs;
 156
 157 /* Count values without known locations.  Whenever this grows too big, we
 158    remove these useless values from the table.  */
 159 static int n_useless_values;
 160
 161 /* Number of useless values before we remove them from the hash table.  */
 162 #define MAX_USELESS_VALUES 32
 163
 164 /* This table maps from register number to values.  It does not contain
 165    pointers to cselib_val structures, but rather elt_lists.  The purpose is
 166    to be able to refer to the same register in different modes.  */
 167 static varray_type reg_values;
 168 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
 169
 170 /* We pass this to cselib_invalidate_mem to invalidate all of
 171    memory for a non-const call instruction.  */
 172 static rtx callmem;
 173
 174 /* Memory for our structures is allocated from this obstack.  */
 175 static struct obstack cselib_obstack;
 176
 177 /* Used to quickly free all memory.  */
 178 static char *cselib_startobj;
 179
 180 /* Caches for unused structures.  */
 181 static cselib_val *empty_vals;
 182 static struct elt_list *empty_elt_lists;
 183 static struct elt_loc_list *empty_elt_loc_lists;
 184
 185 /* Set by discard_useless_locs if it deleted the last location of any
 186    value.  */
 187 static int values_became_useless;
 188 \f
 189 /* Make a binary operation by properly ordering the operands and
 190    seeing if the expression folds.  */
 191
 192 rtx
 193 simplify_gen_binary (code, mode, op0, op1)
 194      enum rtx_code code;
 195      enum machine_mode mode;
 196      rtx op0, op1;
 197 {
 198   rtx tem;
 199
 200   /* Put complex operands first and constants second if commutative.  */
 201   if (GET_RTX_CLASS (code) == 'c'
 202       && ((CONSTANT_P (op0) && GET_CODE (op1) != CONST_INT)
 203           || (GET_RTX_CLASS (GET_CODE (op0)) == 'o'
 204               && GET_RTX_CLASS (GET_CODE (op1)) != 'o')
 205           || (GET_CODE (op0) == SUBREG
 206               && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op0))) == 'o'
 207               && GET_RTX_CLASS (GET_CODE (op1)) != 'o')))
 208     tem = op0, op0 = op1, op1 = tem;
 209
 210   /* If this simplifies, do it.  */
 211   tem = simplify_binary_operation (code, mode, op0, op1);
 212
 213   if (tem)
 214     return tem;
 215
 216   /* Handle addition and subtraction of CONST_INT specially.  Otherwise,
 217      just form the operation.  */
 218
 219   if (code == PLUS && GET_CODE (op1) == CONST_INT
 220       && GET_MODE (op0) != VOIDmode)
 221     return plus_constant (op0, INTVAL (op1));
 222   else if (code == MINUS && GET_CODE (op1) == CONST_INT
 223            && GET_MODE (op0) != VOIDmode)
 224     return plus_constant (op0, - INTVAL (op1));
 225   else
 226     return gen_rtx_fmt_ee (code, mode, op0, op1);
 227 }
 228 \f
 229 /* Try to simplify a unary operation CODE whose output mode is to be
 230    MODE with input operand OP whose mode was originally OP_MODE.
 231    Return zero if no simplification can be made.  */
 232
 233 rtx
 234 simplify_unary_operation (code, mode, op, op_mode)
 235      enum rtx_code code;
 236      enum machine_mode mode;
 237      rtx op;
 238      enum machine_mode op_mode;
 239 {
 240   unsigned int width = GET_MODE_BITSIZE (mode);
 241
 242   /* The order of these tests is critical so that, for example, we don't
 243      check the wrong mode (input vs. output) for a conversion operation,
 244      such as FIX.  At some point, this should be simplified.  */
 245
 246 #if !defined(REAL_IS_NOT_DOUBLE) || defined(REAL_ARITHMETIC)
 247
 248   if (code == FLOAT && GET_MODE (op) == VOIDmode
 249       && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
 250     {
 251       HOST_WIDE_INT hv, lv;
 252       REAL_VALUE_TYPE d;
 253
 254       if (GET_CODE (op) == CONST_INT)
 255         lv = INTVAL (op), hv = HWI_SIGN_EXTEND (lv);
 256       else
 257         lv = CONST_DOUBLE_LOW (op),  hv = CONST_DOUBLE_HIGH (op);
 258
 259 #ifdef REAL_ARITHMETIC
 260       REAL_VALUE_FROM_INT (d, lv, hv, mode);
 261 #else
 262       if (hv < 0)
 263         {
 264           d = (double) (~ hv);
 265           d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
 266                 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
 267           d += (double) (unsigned HOST_WIDE_INT) (~ lv);
 268           d = (- d - 1.0);
 269         }
 270       else
 271         {
 272           d = (double) hv;
 273           d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
 274                 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
 275           d += (double) (unsigned HOST_WIDE_INT) lv;
 276         }
 277 #endif  /* REAL_ARITHMETIC */
 278       d = real_value_truncate (mode, d);
 279       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
 280     }
 281   else if (code == UNSIGNED_FLOAT && GET_MODE (op) == VOIDmode
 282            && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
 283     {
 284       HOST_WIDE_INT hv, lv;
 285       REAL_VALUE_TYPE d;
 286
 287       if (GET_CODE (op) == CONST_INT)
 288         lv = INTVAL (op), hv = HWI_SIGN_EXTEND (lv);
 289       else
 290         lv = CONST_DOUBLE_LOW (op),  hv = CONST_DOUBLE_HIGH (op);
 291
 292       if (op_mode == VOIDmode)
 293         {
 294           /* We don't know how to interpret negative-looking numbers in
 295              this case, so don't try to fold those.  */
 296           if (hv < 0)
 297             return 0;
 298         }
 299       else if (GET_MODE_BITSIZE (op_mode) >= HOST_BITS_PER_WIDE_INT * 2)
 300         ;
 301       else
 302         hv = 0, lv &= GET_MODE_MASK (op_mode);
 303
 304 #ifdef REAL_ARITHMETIC
 305       REAL_VALUE_FROM_UNSIGNED_INT (d, lv, hv, mode);
 306 #else
 307
 308       d = (double) (unsigned HOST_WIDE_INT) hv;
 309       d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
 310             * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
 311       d += (double) (unsigned HOST_WIDE_INT) lv;
 312 #endif  /* REAL_ARITHMETIC */
 313       d = real_value_truncate (mode, d);
 314       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
 315     }
 316 #endif
 317
 318   if (GET_CODE (op) == CONST_INT
 319       && width <= HOST_BITS_PER_WIDE_INT && width > 0)
 320     {
 321       register HOST_WIDE_INT arg0 = INTVAL (op);
 322       register HOST_WIDE_INT val;
 323
 324       switch (code)
 325         {
 326         case NOT:
 327           val = ~ arg0;
 328           break;
 329
 330         case NEG:
 331           val = - arg0;
 332           break;
 333
 334         case ABS:
 335           val = (arg0 >= 0 ? arg0 : - arg0);
 336           break;
 337
 338         case FFS:
 339           /* Don't use ffs here.  Instead, get low order bit and then its
 340              number.  If arg0 is zero, this will return 0, as desired.  */
 341           arg0 &= GET_MODE_MASK (mode);
 342           val = exact_log2 (arg0 & (- arg0)) + 1;
 343           break;
 344
 345         case TRUNCATE:
 346           val = arg0;
 347           break;
 348
 349         case ZERO_EXTEND:
 350           if (op_mode == VOIDmode)
 351             op_mode = mode;
 352           if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
 353             {
 354               /* If we were really extending the mode,
 355                  we would have to distinguish between zero-extension
 356                  and sign-extension.  */
 357               if (width != GET_MODE_BITSIZE (op_mode))
 358                 abort ();
 359               val = arg0;
 360             }
 361           else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
 362             val = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
 363           else
 364             return 0;
 365           break;
 366
 367         case SIGN_EXTEND:
 368           if (op_mode == VOIDmode)
 369             op_mode = mode;
 370           if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
 371             {
 372               /* If we were really extending the mode,
 373                  we would have to distinguish between zero-extension
 374                  and sign-extension.  */
 375               if (width != GET_MODE_BITSIZE (op_mode))
 376                 abort ();
 377               val = arg0;
 378             }
 379           else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
 380             {
 381               val
 382                 = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
 383               if (val
 384                   & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (op_mode) - 1)))
 385                 val -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
 386             }
 387           else
 388             return 0;
 389           break;
 390
 391         case SQRT:
 392           return 0;
 393
 394         default:
 395           abort ();
 396         }
 397
 398       val = trunc_int_for_mode (val, mode);
 399
 400       return GEN_INT (val);
 401     }
 402
 403   /* We can do some operations on integer CONST_DOUBLEs.  Also allow
 404      for a DImode operation on a CONST_INT.  */
 405   else if (GET_MODE (op) == VOIDmode && width <= HOST_BITS_PER_INT * 2
 406            && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
 407     {
 408       unsigned HOST_WIDE_INT l1, lv;
 409       HOST_WIDE_INT h1, hv;
 410
 411       if (GET_CODE (op) == CONST_DOUBLE)
 412         l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op);
 413       else
 414         l1 = INTVAL (op), h1 = HWI_SIGN_EXTEND (l1);
 415
 416       switch (code)
 417         {
 418         case NOT:
 419           lv = ~ l1;
 420           hv = ~ h1;
 421           break;
 422
 423         case NEG:
 424           neg_double (l1, h1, &lv, &hv);
 425           break;
 426
 427         case ABS:
 428           if (h1 < 0)
 429             neg_double (l1, h1, &lv, &hv);
 430           else
 431             lv = l1, hv = h1;
 432           break;
 433
 434         case FFS:
 435           hv = 0;
 436           if (l1 == 0)
 437             lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & (-h1)) + 1;
 438           else
 439             lv = exact_log2 (l1 & (-l1)) + 1;
 440           break;
 441
 442         case TRUNCATE:
 443           /* This is just a change-of-mode, so do nothing.  */
 444           lv = l1, hv = h1;
 445           break;
 446
 447         case ZERO_EXTEND:
 448           if (op_mode == VOIDmode
 449               || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
 450             return 0;
 451
 452           hv = 0;
 453           lv = l1 & GET_MODE_MASK (op_mode);
 454           break;
 455
 456         case SIGN_EXTEND:
 457           if (op_mode == VOIDmode
 458               || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
 459             return 0;
 460           else
 461             {
 462               lv = l1 & GET_MODE_MASK (op_mode);
 463               if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT
 464                   && (lv & ((HOST_WIDE_INT) 1
 465                             << (GET_MODE_BITSIZE (op_mode) - 1))) != 0)
 466                 lv -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
 467
 468               hv = HWI_SIGN_EXTEND (lv);
 469             }
 470           break;
 471
 472         case SQRT:
 473           return 0;
 474
 475         default:
 476           return 0;
 477         }
 478
 479       return immed_double_const (lv, hv, mode);
 480     }
 481
 482 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
 483   else if (GET_CODE (op) == CONST_DOUBLE
 484            && GET_MODE_CLASS (mode) == MODE_FLOAT)
 485     {
 486       REAL_VALUE_TYPE d;
 487       jmp_buf handler;
 488       rtx x;
 489
 490       if (setjmp (handler))
 491         /* There used to be a warning here, but that is inadvisable.
 492            People may want to cause traps, and the natural way
 493            to do it should not get a warning.  */
 494         return 0;
 495
 496       set_float_handler (handler);
 497
 498       REAL_VALUE_FROM_CONST_DOUBLE (d, op);
 499
 500       switch (code)
 501         {
 502         case NEG:
 503           d = REAL_VALUE_NEGATE (d);
 504           break;
 505
 506         case ABS:
 507           if (REAL_VALUE_NEGATIVE (d))
 508             d = REAL_VALUE_NEGATE (d);
 509           break;
 510
 511         case FLOAT_TRUNCATE:
 512           d = real_value_truncate (mode, d);
 513           break;
 514
 515         case FLOAT_EXTEND:
 516           /* All this does is change the mode.  */
 517           break;
 518
 519         case FIX:
 520           d = REAL_VALUE_RNDZINT (d);
 521           break;
 522
 523         case UNSIGNED_FIX:
 524           d = REAL_VALUE_UNSIGNED_RNDZINT (d);
 525           break;
 526
 527         case SQRT:
 528           return 0;
 529
 530         default:
 531           abort ();
 532         }
 533
 534       x = CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
 535       set_float_handler (NULL_PTR);
 536       return x;
 537     }
 538
 539   else if (GET_CODE (op) == CONST_DOUBLE
 540            && GET_MODE_CLASS (GET_MODE (op)) == MODE_FLOAT
 541            && GET_MODE_CLASS (mode) == MODE_INT
 542            && width <= HOST_BITS_PER_WIDE_INT && width > 0)
 543     {
 544       REAL_VALUE_TYPE d;
 545       jmp_buf handler;
 546       HOST_WIDE_INT val;
 547
 548       if (setjmp (handler))
 549         return 0;
 550
 551       set_float_handler (handler);
 552
 553       REAL_VALUE_FROM_CONST_DOUBLE (d, op);
 554
 555       switch (code)
 556         {
 557         case FIX:
 558           val = REAL_VALUE_FIX (d);
 559           break;
 560
 561         case UNSIGNED_FIX:
 562           val = REAL_VALUE_UNSIGNED_FIX (d);
 563           break;
 564
 565         default:
 566           abort ();
 567         }
 568
 569       set_float_handler (NULL_PTR);
 570
 571       val = trunc_int_for_mode (val, mode);
 572
 573       return GEN_INT (val);
 574     }
 575 #endif
 576   /* This was formerly used only for non-IEEE float.
 577      eggert@twinsun.com says it is safe for IEEE also.  */
 578   else
 579     {
 580       /* There are some simplifications we can do even if the operands
 581          aren't constant.  */
 582       switch (code)
 583         {
 584         case NEG:
 585         case NOT:
 586           /* (not (not X)) == X, similarly for NEG.  */
 587           if (GET_CODE (op) == code)
 588             return XEXP (op, 0);
 589           break;
 590
 591         case SIGN_EXTEND:
 592           /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
 593              becomes just the MINUS if its mode is MODE.  This allows
 594              folding switch statements on machines using casesi (such as
 595              the Vax).  */
 596           if (GET_CODE (op) == TRUNCATE
 597               && GET_MODE (XEXP (op, 0)) == mode
 598               && GET_CODE (XEXP (op, 0)) == MINUS
 599               && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
 600               && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
 601             return XEXP (op, 0);
 602
 603 #ifdef POINTERS_EXTEND_UNSIGNED
 604           if (! POINTERS_EXTEND_UNSIGNED
 605               && mode == Pmode && GET_MODE (op) == ptr_mode
 606               && CONSTANT_P (op))
 607             return convert_memory_address (Pmode, op);
 608 #endif
 609           break;
 610
 611 #ifdef POINTERS_EXTEND_UNSIGNED
 612         case ZERO_EXTEND:
 613           if (POINTERS_EXTEND_UNSIGNED
 614               && mode == Pmode && GET_MODE (op) == ptr_mode
 615               && CONSTANT_P (op))
 616             return convert_memory_address (Pmode, op);
 617           break;
 618 #endif
 619
 620         default:
 621           break;
 622         }
 623
 624       return 0;
 625     }
 626 }
 627 \f
 628 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
 629    and OP1.  Return 0 if no simplification is possible.
 630
 631    Don't use this for relational operations such as EQ or LT.
 632    Use simplify_relational_operation instead.  */
 633
 634 rtx
 635 simplify_binary_operation (code, mode, op0, op1)
 636      enum rtx_code code;
 637      enum machine_mode mode;
 638      rtx op0, op1;
 639 {
 640   register HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
 641   HOST_WIDE_INT val;
 642   unsigned int width = GET_MODE_BITSIZE (mode);
 643   rtx tem;
 644
 645   /* Relational operations don't work here.  We must know the mode
 646      of the operands in order to do the comparison correctly.
 647      Assuming a full word can give incorrect results.
 648      Consider comparing 128 with -128 in QImode.  */
 649
 650   if (GET_RTX_CLASS (code) == '<')
 651     abort ();
 652
 653 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
 654   if (GET_MODE_CLASS (mode) == MODE_FLOAT
 655       && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
 656       && mode == GET_MODE (op0) && mode == GET_MODE (op1))
 657     {
 658       REAL_VALUE_TYPE f0, f1, value;
 659       jmp_buf handler;
 660
 661       if (setjmp (handler))
 662         return 0;
 663
 664       set_float_handler (handler);
 665
 666       REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
 667       REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
 668       f0 = real_value_truncate (mode, f0);
 669       f1 = real_value_truncate (mode, f1);
 670
 671 #ifdef REAL_ARITHMETIC
 672 #ifndef REAL_INFINITY
 673       if (code == DIV && REAL_VALUES_EQUAL (f1, dconst0))
 674         return 0;
 675 #endif
 676       REAL_ARITHMETIC (value, rtx_to_tree_code (code), f0, f1);
 677 #else
 678       switch (code)
 679         {
 680         case PLUS:
 681           value = f0 + f1;
 682           break;
 683         case MINUS:
 684           value = f0 - f1;
 685           break;
 686         case MULT:
 687           value = f0 * f1;
 688           break;
 689         case DIV:
 690 #ifndef REAL_INFINITY
 691           if (f1 == 0)
 692             return 0;
 693 #endif
 694           value = f0 / f1;
 695           break;
 696         case SMIN:
 697           value = MIN (f0, f1);
 698           break;
 699         case SMAX:
 700           value = MAX (f0, f1);
 701           break;
 702         default:
 703           abort ();
 704         }
 705 #endif
 706
 707       value = real_value_truncate (mode, value);
 708       set_float_handler (NULL_PTR);
 709       return CONST_DOUBLE_FROM_REAL_VALUE (value, mode);
 710     }
 711 #endif  /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
 712
 713   /* We can fold some multi-word operations.  */
 714   if (GET_MODE_CLASS (mode) == MODE_INT
 715       && width == HOST_BITS_PER_WIDE_INT * 2
 716       && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
 717       && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
 718     {
 719       unsigned HOST_WIDE_INT l1, l2, lv;
 720       HOST_WIDE_INT h1, h2, hv;
 721
 722       if (GET_CODE (op0) == CONST_DOUBLE)
 723         l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0);
 724       else
 725         l1 = INTVAL (op0), h1 = HWI_SIGN_EXTEND (l1);
 726
 727       if (GET_CODE (op1) == CONST_DOUBLE)
 728         l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1);
 729       else
 730         l2 = INTVAL (op1), h2 = HWI_SIGN_EXTEND (l2);
 731
 732       switch (code)
 733         {
 734         case MINUS:
 735           /* A - B == A + (-B).  */
 736           neg_double (l2, h2, &lv, &hv);
 737           l2 = lv, h2 = hv;
 738
 739           /* .. fall through ...  */
 740
 741         case PLUS:
 742           add_double (l1, h1, l2, h2, &lv, &hv);
 743           break;
 744
 745         case MULT:
 746           mul_double (l1, h1, l2, h2, &lv, &hv);
 747           break;
 748
 749         case DIV:  case MOD:   case UDIV:  case UMOD:
 750           /* We'd need to include tree.h to do this and it doesn't seem worth
 751              it.  */
 752           return 0;
 753
 754         case AND:
 755           lv = l1 & l2, hv = h1 & h2;
 756           break;
 757
 758         case IOR:
 759           lv = l1 | l2, hv = h1 | h2;
 760           break;
 761
 762         case XOR:
 763           lv = l1 ^ l2, hv = h1 ^ h2;
 764           break;
 765
 766         case SMIN:
 767           if (h1 < h2
 768               || (h1 == h2
 769                   && ((unsigned HOST_WIDE_INT) l1
 770                       < (unsigned HOST_WIDE_INT) l2)))
 771             lv = l1, hv = h1;
 772           else
 773             lv = l2, hv = h2;
 774           break;
 775
 776         case SMAX:
 777           if (h1 > h2
 778               || (h1 == h2
 779                   && ((unsigned HOST_WIDE_INT) l1
 780                       > (unsigned HOST_WIDE_INT) l2)))
 781             lv = l1, hv = h1;
 782           else
 783             lv = l2, hv = h2;
 784           break;
 785
 786         case UMIN:
 787           if ((unsigned HOST_WIDE_INT) h1 < (unsigned HOST_WIDE_INT) h2
 788               || (h1 == h2
 789                   && ((unsigned HOST_WIDE_INT) l1
 790                       < (unsigned HOST_WIDE_INT) l2)))
 791             lv = l1, hv = h1;
 792           else
 793             lv = l2, hv = h2;
 794           break;
 795
 796         case UMAX:
 797           if ((unsigned HOST_WIDE_INT) h1 > (unsigned HOST_WIDE_INT) h2
 798               || (h1 == h2
 799                   && ((unsigned HOST_WIDE_INT) l1
 800                       > (unsigned HOST_WIDE_INT) l2)))
 801             lv = l1, hv = h1;
 802           else
 803             lv = l2, hv = h2;
 804           break;
 805
 806         case LSHIFTRT:   case ASHIFTRT:
 807         case ASHIFT:
 808         case ROTATE:     case ROTATERT:
 809 #ifdef SHIFT_COUNT_TRUNCATED
 810           if (SHIFT_COUNT_TRUNCATED)
 811             l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0;
 812 #endif
 813
 814           if (h2 != 0 || l2 >= GET_MODE_BITSIZE (mode))
 815             return 0;
 816
 817           if (code == LSHIFTRT || code == ASHIFTRT)
 818             rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
 819                            code == ASHIFTRT);
 820           else if (code == ASHIFT)
 821             lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, 1);
 822           else if (code == ROTATE)
 823             lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
 824           else /* code == ROTATERT */
 825             rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
 826           break;
 827
 828         default:
 829           return 0;
 830         }
 831
 832       return immed_double_const (lv, hv, mode);
 833     }
 834
 835   if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
 836       || width > HOST_BITS_PER_WIDE_INT || width == 0)
 837     {
 838       /* Even if we can't compute a constant result,
 839          there are some cases worth simplifying.  */
 840
 841       switch (code)
 842         {
 843         case PLUS:
 844           /* In IEEE floating point, x+0 is not the same as x.  Similarly
 845              for the other optimizations below.  */
 846           if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
 847               && FLOAT_MODE_P (mode) && ! flag_fast_math)
 848             break;
 849
 850           if (op1 == CONST0_RTX (mode))
 851             return op0;
 852
 853           /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
 854           if (GET_CODE (op0) == NEG)
 855             return simplify_gen_binary (MINUS, mode, op1, XEXP (op0, 0));
 856           else if (GET_CODE (op1) == NEG)
 857             return simplify_gen_binary (MINUS, mode, op0, XEXP (op1, 0));
 858
 859           /* Handle both-operands-constant cases.  We can only add
 860              CONST_INTs to constants since the sum of relocatable symbols
 861              can't be handled by most assemblers.  Don't add CONST_INT
 862              to CONST_INT since overflow won't be computed properly if wider
 863              than HOST_BITS_PER_WIDE_INT.  */
 864
 865           if (CONSTANT_P (op0) && GET_MODE (op0) != VOIDmode
 866               && GET_CODE (op1) == CONST_INT)
 867             return plus_constant (op0, INTVAL (op1));
 868           else if (CONSTANT_P (op1) && GET_MODE (op1) != VOIDmode
 869                    && GET_CODE (op0) == CONST_INT)
 870             return plus_constant (op1, INTVAL (op0));
 871
 872           /* See if this is something like X * C - X or vice versa or
 873              if the multiplication is written as a shift.  If so, we can
 874              distribute and make a new multiply, shift, or maybe just
 875              have X (if C is 2 in the example above).  But don't make
 876              real multiply if we didn't have one before.  */
 877
 878           if (! FLOAT_MODE_P (mode))
 879             {
 880               HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
 881               rtx lhs = op0, rhs = op1;
 882               int had_mult = 0;
 883
 884               if (GET_CODE (lhs) == NEG)
 885                 coeff0 = -1, lhs = XEXP (lhs, 0);
 886               else if (GET_CODE (lhs) == MULT
 887                        && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
 888                 {
 889                   coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
 890                   had_mult = 1;
 891                 }
 892               else if (GET_CODE (lhs) == ASHIFT
 893                        && GET_CODE (XEXP (lhs, 1)) == CONST_INT
 894                        && INTVAL (XEXP (lhs, 1)) >= 0
 895                        && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
 896                 {
 897                   coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
 898                   lhs = XEXP (lhs, 0);
 899                 }
 900
 901               if (GET_CODE (rhs) == NEG)
 902                 coeff1 = -1, rhs = XEXP (rhs, 0);
 903               else if (GET_CODE (rhs) == MULT
 904                        && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
 905                 {
 906                   coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
 907                   had_mult = 1;
 908                 }
 909               else if (GET_CODE (rhs) == ASHIFT
 910                        && GET_CODE (XEXP (rhs, 1)) == CONST_INT
 911                        && INTVAL (XEXP (rhs, 1)) >= 0
 912                        && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
 913                 {
 914                   coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
 915                   rhs = XEXP (rhs, 0);
 916                 }
 917
 918               if (rtx_equal_p (lhs, rhs))
 919                 {
 920                   tem = simplify_gen_binary (MULT, mode, lhs,
 921                                         GEN_INT (coeff0 + coeff1));
 922                   return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
 923                 }
 924             }
 925
 926           /* If one of the operands is a PLUS or a MINUS, see if we can
 927              simplify this by the associative law.
 928              Don't use the associative law for floating point.
 929              The inaccuracy makes it nonassociative,
 930              and subtle programs can break if operations are associated.  */
 931
 932           if (INTEGRAL_MODE_P (mode)
 933               && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
 934                   || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
 935               && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
 936             return tem;
 937           break;
 938
 939         case COMPARE:
 940 #ifdef HAVE_cc0
 941           /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
 942              using cc0, in which case we want to leave it as a COMPARE
 943              so we can distinguish it from a register-register-copy.
 944
 945              In IEEE floating point, x-0 is not the same as x.  */
 946
 947           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
 948                || ! FLOAT_MODE_P (mode) || flag_fast_math)
 949               && op1 == CONST0_RTX (mode))
 950             return op0;
 951 #endif
 952
 953           /* Convert (compare (gt (flags) 0) (lt (flags) 0)) to (flags).  */
 954           if (((GET_CODE (op0) == GT && GET_CODE (op1) == LT)
 955                || (GET_CODE (op0) == GTU && GET_CODE (op1) == LTU))
 956               && XEXP (op0, 1) == const0_rtx && XEXP (op1, 1) == const0_rtx)
 957             {
 958               rtx xop00 = XEXP (op0, 0);
 959               rtx xop10 = XEXP (op1, 0);
 960
 961 #ifdef HAVE_cc0
 962               if (GET_CODE (xop00) == CC0 && GET_CODE (xop10) == CC0)
 963 #else
 964               if (GET_CODE (xop00) == REG && GET_CODE (xop10) == REG
 965                   && GET_MODE (xop00) == GET_MODE (xop10)
 966                   && REGNO (xop00) == REGNO (xop10)
 967                   && GET_MODE_CLASS (GET_MODE (xop00)) == MODE_CC
 968                   && GET_MODE_CLASS (GET_MODE (xop10)) == MODE_CC)
 969 #endif
 970                 return xop00;
 971             }
 972
 973           break;
 974         case MINUS:
 975           /* None of these optimizations can be done for IEEE
 976              floating point.  */
 977           if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
 978               && FLOAT_MODE_P (mode) && ! flag_fast_math)
 979             break;
 980
 981           /* We can't assume x-x is 0 even with non-IEEE floating point,
 982              but since it is zero except in very strange circumstances, we
 983              will treat it as zero with -ffast-math.  */
 984           if (rtx_equal_p (op0, op1)
 985               && ! side_effects_p (op0)
 986               && (! FLOAT_MODE_P (mode) || flag_fast_math))
 987             return CONST0_RTX (mode);
 988
 989           /* Change subtraction from zero into negation.  */
 990           if (op0 == CONST0_RTX (mode))
 991             return gen_rtx_NEG (mode, op1);
 992
 993           /* (-1 - a) is ~a.  */
 994           if (op0 == constm1_rtx)
 995             return gen_rtx_NOT (mode, op1);
 996
 997           /* Subtracting 0 has no effect.  */
 998           if (op1 == CONST0_RTX (mode))
 999             return op0;
1000
1001           /* See if this is something like X * C - X or vice versa or
1002              if the multiplication is written as a shift.  If so, we can
1003              distribute and make a new multiply, shift, or maybe just
1004              have X (if C is 2 in the example above).  But don't make
1005              real multiply if we didn't have one before.  */
1006
1007           if (! FLOAT_MODE_P (mode))
1008             {
1009               HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
1010               rtx lhs = op0, rhs = op1;
1011               int had_mult = 0;
1012
1013               if (GET_CODE (lhs) == NEG)
1014                 coeff0 = -1, lhs = XEXP (lhs, 0);
1015               else if (GET_CODE (lhs) == MULT
1016                        && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
1017                 {
1018                   coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
1019                   had_mult = 1;
1020                 }
1021               else if (GET_CODE (lhs) == ASHIFT
1022                        && GET_CODE (XEXP (lhs, 1)) == CONST_INT
1023                        && INTVAL (XEXP (lhs, 1)) >= 0
1024                        && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
1025                 {
1026                   coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
1027                   lhs = XEXP (lhs, 0);
1028                 }
1029
1030               if (GET_CODE (rhs) == NEG)
1031                 coeff1 = - 1, rhs = XEXP (rhs, 0);
1032               else if (GET_CODE (rhs) == MULT
1033                        && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
1034                 {
1035                   coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
1036                   had_mult = 1;
1037                 }
1038               else if (GET_CODE (rhs) == ASHIFT
1039                        && GET_CODE (XEXP (rhs, 1)) == CONST_INT
1040                        && INTVAL (XEXP (rhs, 1)) >= 0
1041                        && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
1042                 {
1043                   coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
1044                   rhs = XEXP (rhs, 0);
1045                 }
1046
1047               if (rtx_equal_p (lhs, rhs))
1048                 {
1049                   tem = simplify_gen_binary (MULT, mode, lhs,
1050                                              GEN_INT (coeff0 - coeff1));
1051                   return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
1052                 }
1053             }
1054
1055           /* (a - (-b)) -> (a + b).  */
1056           if (GET_CODE (op1) == NEG)
1057             return simplify_gen_binary (PLUS, mode, op0, XEXP (op1, 0));
1058
1059           /* If one of the operands is a PLUS or a MINUS, see if we can
1060              simplify this by the associative law.
1061              Don't use the associative law for floating point.
1062              The inaccuracy makes it nonassociative,
1063              and subtle programs can break if operations are associated.  */
1064
1065           if (INTEGRAL_MODE_P (mode)
1066               && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
1067                   || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
1068               && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
1069             return tem;
1070
1071           /* Don't let a relocatable value get a negative coeff.  */
1072           if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode)
1073             return plus_constant (op0, - INTVAL (op1));
1074
1075           /* (x - (x & y)) -> (x & ~y) */
1076           if (GET_CODE (op1) == AND)
1077             {
1078              if (rtx_equal_p (op0, XEXP (op1, 0)))
1079                return simplify_gen_binary (AND, mode, op0,
1080                                            gen_rtx_NOT (mode, XEXP (op1, 1)));
1081              if (rtx_equal_p (op0, XEXP (op1, 1)))
1082                return simplify_gen_binary (AND, mode, op0,
1083                                            gen_rtx_NOT (mode, XEXP (op1, 0)));
1084            }
1085           break;
1086
1087         case MULT:
1088           if (op1 == constm1_rtx)
1089             {
1090               tem = simplify_unary_operation (NEG, mode, op0, mode);
1091
1092               return tem ? tem : gen_rtx_NEG (mode, op0);
1093             }
1094
1095           /* In IEEE floating point, x*0 is not always 0.  */
1096           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1097                || ! FLOAT_MODE_P (mode) || flag_fast_math)
1098               && op1 == CONST0_RTX (mode)
1099               && ! side_effects_p (op0))
1100             return op1;
1101
1102           /* In IEEE floating point, x*1 is not equivalent to x for nans.
1103              However, ANSI says we can drop signals,
1104              so we can do this anyway.  */
1105           if (op1 == CONST1_RTX (mode))
1106             return op0;
1107
1108           /* Convert multiply by constant power of two into shift unless
1109              we are still generating RTL.  This test is a kludge.  */
1110           if (GET_CODE (op1) == CONST_INT
1111               && (val = exact_log2 (INTVAL (op1))) >= 0
1112               /* If the mode is larger than the host word size, and the
1113                  uppermost bit is set, then this isn't a power of two due
1114                  to implicit sign extension.  */
1115               && (width <= HOST_BITS_PER_WIDE_INT
1116                   || val != HOST_BITS_PER_WIDE_INT - 1)
1117               && ! rtx_equal_function_value_matters)
1118             return gen_rtx_ASHIFT (mode, op0, GEN_INT (val));
1119
1120           if (GET_CODE (op1) == CONST_DOUBLE
1121               && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
1122             {
1123               REAL_VALUE_TYPE d;
1124               jmp_buf handler;
1125               int op1is2, op1ism1;
1126
1127               if (setjmp (handler))
1128                 return 0;
1129
1130               set_float_handler (handler);
1131               REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1132               op1is2 = REAL_VALUES_EQUAL (d, dconst2);
1133               op1ism1 = REAL_VALUES_EQUAL (d, dconstm1);
1134               set_float_handler (NULL_PTR);
1135
1136               /* x*2 is x+x and x*(-1) is -x */
1137               if (op1is2 && GET_MODE (op0) == mode)
1138                 return gen_rtx_PLUS (mode, op0, copy_rtx (op0));
1139
1140               else if (op1ism1 && GET_MODE (op0) == mode)
1141                 return gen_rtx_NEG (mode, op0);
1142             }
1143           break;
1144
1145         case IOR:
1146           if (op1 == const0_rtx)
1147             return op0;
1148           if (GET_CODE (op1) == CONST_INT
1149               && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1150             return op1;
1151           if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1152             return op0;
1153           /* A | (~A) -> -1 */
1154           if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1155                || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1156               && ! side_effects_p (op0)
1157               && GET_MODE_CLASS (mode) != MODE_CC)
1158             return constm1_rtx;
1159           break;
1160
1161         case XOR:
1162           if (op1 == const0_rtx)
1163             return op0;
1164           if (GET_CODE (op1) == CONST_INT
1165               && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1166             return gen_rtx_NOT (mode, op0);
1167           if (op0 == op1 && ! side_effects_p (op0)
1168               && GET_MODE_CLASS (mode) != MODE_CC)
1169             return const0_rtx;
1170           break;
1171
1172         case AND:
1173           if (op1 == const0_rtx && ! side_effects_p (op0))
1174             return const0_rtx;
1175           if (GET_CODE (op1) == CONST_INT
1176               && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1177             return op0;
1178           if (op0 == op1 && ! side_effects_p (op0)
1179               && GET_MODE_CLASS (mode) != MODE_CC)
1180             return op0;
1181           /* A & (~A) -> 0 */
1182           if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1183                || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1184               && ! side_effects_p (op0)
1185               && GET_MODE_CLASS (mode) != MODE_CC)
1186             return const0_rtx;
1187           break;
1188
1189         case UDIV:
1190           /* Convert divide by power of two into shift (divide by 1 handled
1191              below).  */
1192           if (GET_CODE (op1) == CONST_INT
1193               && (arg1 = exact_log2 (INTVAL (op1))) > 0)
1194             return gen_rtx_LSHIFTRT (mode, op0, GEN_INT (arg1));
1195
1196           /* ... fall through ...  */
1197
1198         case DIV:
1199           if (op1 == CONST1_RTX (mode))
1200             return op0;
1201
1202           /* In IEEE floating point, 0/x is not always 0.  */
1203           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1204                || ! FLOAT_MODE_P (mode) || flag_fast_math)
1205               && op0 == CONST0_RTX (mode)
1206               && ! side_effects_p (op1))
1207             return op0;
1208
1209 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1210           /* Change division by a constant into multiplication.  Only do
1211              this with -ffast-math until an expert says it is safe in
1212              general.  */
1213           else if (GET_CODE (op1) == CONST_DOUBLE
1214                    && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
1215                    && op1 != CONST0_RTX (mode)
1216                    && flag_fast_math)
1217             {
1218               REAL_VALUE_TYPE d;
1219               REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1220
1221               if (! REAL_VALUES_EQUAL (d, dconst0))
1222                 {
1223 #if defined (REAL_ARITHMETIC)
1224                   REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d);
1225                   return gen_rtx_MULT (mode, op0,
1226                                        CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
1227 #else
1228                   return
1229                     gen_rtx_MULT (mode, op0,
1230                                   CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
1231 #endif
1232                 }
1233             }
1234 #endif
1235           break;
1236
1237         case UMOD:
1238           /* Handle modulus by power of two (mod with 1 handled below).  */
1239           if (GET_CODE (op1) == CONST_INT
1240               && exact_log2 (INTVAL (op1)) > 0)
1241             return gen_rtx_AND (mode, op0, GEN_INT (INTVAL (op1) - 1));
1242
1243           /* ... fall through ...  */
1244
1245         case MOD:
1246           if ((op0 == const0_rtx || op1 == const1_rtx)
1247               && ! side_effects_p (op0) && ! side_effects_p (op1))
1248             return const0_rtx;
1249           break;
1250
1251         case ROTATERT:
1252         case ROTATE:
1253           /* Rotating ~0 always results in ~0.  */
1254           if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT
1255               && (unsigned HOST_WIDE_INT) INTVAL (op0) == GET_MODE_MASK (mode)
1256               && ! side_effects_p (op1))
1257             return op0;
1258
1259           /* ... fall through ...  */
1260
1261         case ASHIFT:
1262         case ASHIFTRT:
1263         case LSHIFTRT:
1264           if (op1 == const0_rtx)
1265             return op0;
1266           if (op0 == const0_rtx && ! side_effects_p (op1))
1267             return op0;
1268           break;
1269
1270         case SMIN:
1271           if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1272               && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1)
1273               && ! side_effects_p (op0))
1274             return op1;
1275           else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1276             return op0;
1277           break;
1278
1279         case SMAX:
1280           if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1281               && ((unsigned HOST_WIDE_INT) INTVAL (op1)
1282                   == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1)
1283               && ! side_effects_p (op0))
1284             return op1;
1285           else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1286             return op0;
1287           break;
1288
1289         case UMIN:
1290           if (op1 == const0_rtx && ! side_effects_p (op0))
1291             return op1;
1292           else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1293             return op0;
1294           break;
1295
1296         case UMAX:
1297           if (op1 == constm1_rtx && ! side_effects_p (op0))
1298             return op1;
1299           else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1300             return op0;
1301           break;
1302
1303         default:
1304           abort ();
1305         }
1306
1307       return 0;
1308     }
1309
1310   /* Get the integer argument values in two forms:
1311      zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S.  */
1312
1313   arg0 = INTVAL (op0);
1314   arg1 = INTVAL (op1);
1315
1316   if (width < HOST_BITS_PER_WIDE_INT)
1317     {
1318       arg0 &= ((HOST_WIDE_INT) 1 << width) - 1;
1319       arg1 &= ((HOST_WIDE_INT) 1 << width) - 1;
1320
1321       arg0s = arg0;
1322       if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1323         arg0s |= ((HOST_WIDE_INT) (-1) << width);
1324
1325       arg1s = arg1;
1326       if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1327         arg1s |= ((HOST_WIDE_INT) (-1) << width);
1328     }
1329   else
1330     {
1331       arg0s = arg0;
1332       arg1s = arg1;
1333     }
1334
1335   /* Compute the value of the arithmetic.  */
1336
1337   switch (code)
1338     {
1339     case PLUS:
1340       val = arg0s + arg1s;
1341       break;
1342
1343     case MINUS:
1344       val = arg0s - arg1s;
1345       break;
1346
1347     case MULT:
1348       val = arg0s * arg1s;
1349       break;
1350
1351     case DIV:
1352       if (arg1s == 0)
1353         return 0;
1354       val = arg0s / arg1s;
1355       break;
1356
1357     case MOD:
1358       if (arg1s == 0)
1359         return 0;
1360       val = arg0s % arg1s;
1361       break;
1362
1363     case UDIV:
1364       if (arg1 == 0)
1365         return 0;
1366       val = (unsigned HOST_WIDE_INT) arg0 / arg1;
1367       break;
1368
1369     case UMOD:
1370       if (arg1 == 0)
1371         return 0;
1372       val = (unsigned HOST_WIDE_INT) arg0 % arg1;
1373       break;
1374
1375     case AND:
1376       val = arg0 & arg1;
1377       break;
1378
1379     case IOR:
1380       val = arg0 | arg1;
1381       break;
1382
1383     case XOR:
1384       val = arg0 ^ arg1;
1385       break;
1386
1387     case LSHIFTRT:
1388       /* If shift count is undefined, don't fold it; let the machine do
1389          what it wants.  But truncate it if the machine will do that.  */
1390       if (arg1 < 0)
1391         return 0;
1392
1393 #ifdef SHIFT_COUNT_TRUNCATED
1394       if (SHIFT_COUNT_TRUNCATED)
1395         arg1 %= width;
1396 #endif
1397
1398       val = ((unsigned HOST_WIDE_INT) arg0) >> arg1;
1399       break;
1400
1401     case ASHIFT:
1402       if (arg1 < 0)
1403         return 0;
1404
1405 #ifdef SHIFT_COUNT_TRUNCATED
1406       if (SHIFT_COUNT_TRUNCATED)
1407         arg1 %= width;
1408 #endif
1409
1410       val = ((unsigned HOST_WIDE_INT) arg0) << arg1;
1411       break;
1412
1413     case ASHIFTRT:
1414       if (arg1 < 0)
1415         return 0;
1416
1417 #ifdef SHIFT_COUNT_TRUNCATED
1418       if (SHIFT_COUNT_TRUNCATED)
1419         arg1 %= width;
1420 #endif
1421
1422       val = arg0s >> arg1;
1423
1424       /* Bootstrap compiler may not have sign extended the right shift.
1425          Manually extend the sign to insure bootstrap cc matches gcc.  */
1426       if (arg0s < 0 && arg1 > 0)
1427         val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1);
1428
1429       break;
1430
1431     case ROTATERT:
1432       if (arg1 < 0)
1433         return 0;
1434
1435       arg1 %= width;
1436       val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1))
1437              | (((unsigned HOST_WIDE_INT) arg0) >> arg1));
1438       break;
1439
1440     case ROTATE:
1441       if (arg1 < 0)
1442         return 0;
1443
1444       arg1 %= width;
1445       val = ((((unsigned HOST_WIDE_INT) arg0) << arg1)
1446              | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1)));
1447       break;
1448
1449     case COMPARE:
1450       /* Do nothing here.  */
1451       return 0;
1452
1453     case SMIN:
1454       val = arg0s <= arg1s ? arg0s : arg1s;
1455       break;
1456
1457     case UMIN:
1458       val = ((unsigned HOST_WIDE_INT) arg0
1459              <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1460       break;
1461
1462     case SMAX:
1463       val = arg0s > arg1s ? arg0s : arg1s;
1464       break;
1465
1466     case UMAX:
1467       val = ((unsigned HOST_WIDE_INT) arg0
1468              > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1469       break;
1470
1471     default:
1472       abort ();
1473     }
1474
1475   val = trunc_int_for_mode (val, mode);
1476
1477   return GEN_INT (val);
1478 }
1479 \f
1480 /* Simplify a PLUS or MINUS, at least one of whose operands may be another
1481    PLUS or MINUS.
1482
1483    Rather than test for specific case, we do this by a brute-force method
1484    and do all possible simplifications until no more changes occur.  Then
1485    we rebuild the operation.  */
1486
1487 static rtx
1488 simplify_plus_minus (code, mode, op0, op1)
1489      enum rtx_code code;
1490      enum machine_mode mode;
1491      rtx op0, op1;
1492 {
1493   rtx ops[8];
1494   int negs[8];
1495   rtx result, tem;
1496   int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
1497   int first = 1, negate = 0, changed;
1498   int i, j;
1499
1500   bzero ((char *) ops, sizeof ops);
1501
1502   /* Set up the two operands and then expand them until nothing has been
1503      changed.  If we run out of room in our array, give up; this should
1504      almost never happen.  */
1505
1506   ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
1507
1508   changed = 1;
1509   while (changed)
1510     {
1511       changed = 0;
1512
1513       for (i = 0; i < n_ops; i++)
1514         switch (GET_CODE (ops[i]))
1515           {
1516           case PLUS:
1517           case MINUS:
1518             if (n_ops == 7)
1519               return 0;
1520
1521             ops[n_ops] = XEXP (ops[i], 1);
1522             negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
1523             ops[i] = XEXP (ops[i], 0);
1524             input_ops++;
1525             changed = 1;
1526             break;
1527
1528           case NEG:
1529             ops[i] = XEXP (ops[i], 0);
1530             negs[i] = ! negs[i];
1531             changed = 1;
1532             break;
1533
1534           case CONST:
1535             ops[i] = XEXP (ops[i], 0);
1536             input_consts++;
1537             changed = 1;
1538             break;
1539
1540           case NOT:
1541             /* ~a -> (-a - 1) */
1542             if (n_ops != 7)
1543               {
1544                 ops[n_ops] = constm1_rtx;
1545                 negs[n_ops++] = negs[i];
1546                 ops[i] = XEXP (ops[i], 0);
1547                 negs[i] = ! negs[i];
1548                 changed = 1;
1549               }
1550             break;
1551
1552           case CONST_INT:
1553             if (negs[i])
1554               ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
1555             break;
1556
1557           default:
1558             break;
1559           }
1560     }
1561
1562   /* If we only have two operands, we can't do anything.  */
1563   if (n_ops <= 2)
1564     return 0;
1565
1566   /* Now simplify each pair of operands until nothing changes.  The first
1567      time through just simplify constants against each other.  */
1568
1569   changed = 1;
1570   while (changed)
1571     {
1572       changed = first;
1573
1574       for (i = 0; i < n_ops - 1; i++)
1575         for (j = i + 1; j < n_ops; j++)
1576           if (ops[i] != 0 && ops[j] != 0
1577               && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
1578             {
1579               rtx lhs = ops[i], rhs = ops[j];
1580               enum rtx_code ncode = PLUS;
1581
1582               if (negs[i] && ! negs[j])
1583                 lhs = ops[j], rhs = ops[i], ncode = MINUS;
1584               else if (! negs[i] && negs[j])
1585                 ncode = MINUS;
1586
1587               tem = simplify_binary_operation (ncode, mode, lhs, rhs);
1588               if (tem)
1589                 {
1590                   ops[i] = tem, ops[j] = 0;
1591                   negs[i] = negs[i] && negs[j];
1592                   if (GET_CODE (tem) == NEG)
1593                     ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
1594
1595                   if (GET_CODE (ops[i]) == CONST_INT && negs[i])
1596                     ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
1597                   changed = 1;
1598                 }
1599             }
1600
1601       first = 0;
1602     }
1603
1604   /* Pack all the operands to the lower-numbered entries and give up if
1605      we didn't reduce the number of operands we had.  Make sure we
1606      count a CONST as two operands.  If we have the same number of
1607      operands, but have made more CONSTs than we had, this is also
1608      an improvement, so accept it.  */
1609
1610   for (i = 0, j = 0; j < n_ops; j++)
1611     if (ops[j] != 0)
1612       {
1613         ops[i] = ops[j], negs[i++] = negs[j];
1614         if (GET_CODE (ops[j]) == CONST)
1615           n_consts++;
1616       }
1617
1618   if (i + n_consts > input_ops
1619       || (i + n_consts == input_ops && n_consts <= input_consts))
1620     return 0;
1621
1622   n_ops = i;
1623
1624   /* If we have a CONST_INT, put it last.  */
1625   for (i = 0; i < n_ops - 1; i++)
1626     if (GET_CODE (ops[i]) == CONST_INT)
1627       {
1628         tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
1629         j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
1630       }
1631
1632   /* Put a non-negated operand first.  If there aren't any, make all
1633      operands positive and negate the whole thing later.  */
1634   for (i = 0; i < n_ops && negs[i]; i++)
1635     ;
1636
1637   if (i == n_ops)
1638     {
1639       for (i = 0; i < n_ops; i++)
1640         negs[i] = 0;
1641       negate = 1;
1642     }
1643   else if (i != 0)
1644     {
1645       tem = ops[0], ops[0] = ops[i], ops[i] = tem;
1646       j = negs[0], negs[0] = negs[i], negs[i] = j;
1647     }
1648
1649   /* Now make the result by performing the requested operations.  */
1650   result = ops[0];
1651   for (i = 1; i < n_ops; i++)
1652     result = simplify_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
1653
1654   return negate ? gen_rtx_NEG (mode, result) : result;
1655 }
1656
1657 struct cfc_args
1658 {
1659   rtx op0, op1;                 /* Input */
1660   int equal, op0lt, op1lt;      /* Output */
1661 };
1662
1663 static void
1664 check_fold_consts (data)
1665   PTR data;
1666 {
1667   struct cfc_args *args = (struct cfc_args *) data;
1668   REAL_VALUE_TYPE d0, d1;
1669
1670   REAL_VALUE_FROM_CONST_DOUBLE (d0, args->op0);
1671   REAL_VALUE_FROM_CONST_DOUBLE (d1, args->op1);
1672   args->equal = REAL_VALUES_EQUAL (d0, d1);
1673   args->op0lt = REAL_VALUES_LESS (d0, d1);
1674   args->op1lt = REAL_VALUES_LESS (d1, d0);
1675 }
1676
1677 /* Like simplify_binary_operation except used for relational operators.
1678    MODE is the mode of the operands, not that of the result.  If MODE
1679    is VOIDmode, both operands must also be VOIDmode and we compare the
1680    operands in "infinite precision".
1681
1682    If no simplification is possible, this function returns zero.  Otherwise,
1683    it returns either const_true_rtx or const0_rtx.  */
1684
1685 rtx
1686 simplify_relational_operation (code, mode, op0, op1)
1687      enum rtx_code code;
1688      enum machine_mode mode;
1689      rtx op0, op1;
1690 {
1691   int equal, op0lt, op0ltu, op1lt, op1ltu;
1692   rtx tem;
1693
1694   if (mode == VOIDmode
1695       && (GET_MODE (op0) != VOIDmode
1696           || GET_MODE (op1) != VOIDmode))
1697     abort();
1698
1699   /* If op0 is a compare, extract the comparison arguments from it.  */
1700   if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
1701     op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
1702
1703   /* We can't simplify MODE_CC values since we don't know what the
1704      actual comparison is.  */
1705   if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC
1706 #ifdef HAVE_cc0
1707       || op0 == cc0_rtx
1708 #endif
1709       )
1710     return 0;
1711
1712   /* Make sure the constant is second.  */
1713   if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
1714       || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
1715     {
1716       tem = op0, op0 = op1, op1 = tem;
1717       code = swap_condition (code);
1718     }
1719
1720   /* For integer comparisons of A and B maybe we can simplify A - B and can
1721      then simplify a comparison of that with zero.  If A and B are both either
1722      a register or a CONST_INT, this can't help; testing for these cases will
1723      prevent infinite recursion here and speed things up.
1724
1725      If CODE is an unsigned comparison, then we can never do this optimization,
1726      because it gives an incorrect result if the subtraction wraps around zero.
1727      ANSI C defines unsigned operations such that they never overflow, and
1728      thus such cases can not be ignored.  */
1729
1730   if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx
1731       && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT)
1732             && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT))
1733       && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1))
1734       && code != GTU && code != GEU && code != LTU && code != LEU)
1735     return simplify_relational_operation (signed_condition (code),
1736                                           mode, tem, const0_rtx);
1737
1738   /* For non-IEEE floating-point, if the two operands are equal, we know the
1739      result.  */
1740   if (rtx_equal_p (op0, op1)
1741       && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1742           || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math))
1743     equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0;
1744
1745   /* If the operands are floating-point constants, see if we can fold
1746      the result.  */
1747 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1748   else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
1749            && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
1750     {
1751       struct cfc_args args;
1752
1753       /* Setup input for check_fold_consts() */
1754       args.op0 = op0;
1755       args.op1 = op1;
1756
1757       if (do_float_handler(check_fold_consts, (PTR) &args) == 0)
1758         /* We got an exception from check_fold_consts() */
1759         return 0;
1760
1761       /* Receive output from check_fold_consts() */
1762       equal = args.equal;
1763       op0lt = op0ltu = args.op0lt;
1764       op1lt = op1ltu = args.op1lt;
1765     }
1766 #endif  /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1767
1768   /* Otherwise, see if the operands are both integers.  */
1769   else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode)
1770            && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
1771            && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
1772     {
1773       int width = GET_MODE_BITSIZE (mode);
1774       HOST_WIDE_INT l0s, h0s, l1s, h1s;
1775       unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u;
1776
1777       /* Get the two words comprising each integer constant.  */
1778       if (GET_CODE (op0) == CONST_DOUBLE)
1779         {
1780           l0u = l0s = CONST_DOUBLE_LOW (op0);
1781           h0u = h0s = CONST_DOUBLE_HIGH (op0);
1782         }
1783       else
1784         {
1785           l0u = l0s = INTVAL (op0);
1786           h0u = h0s = HWI_SIGN_EXTEND (l0s);
1787         }
1788
1789       if (GET_CODE (op1) == CONST_DOUBLE)
1790         {
1791           l1u = l1s = CONST_DOUBLE_LOW (op1);
1792           h1u = h1s = CONST_DOUBLE_HIGH (op1);
1793         }
1794       else
1795         {
1796           l1u = l1s = INTVAL (op1);
1797           h1u = h1s = HWI_SIGN_EXTEND (l1s);
1798         }
1799
1800       /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT,
1801          we have to sign or zero-extend the values.  */
1802       if (width != 0 && width <= HOST_BITS_PER_WIDE_INT)
1803         h0u = h1u = 0, h0s = HWI_SIGN_EXTEND (l0s), h1s = HWI_SIGN_EXTEND (l1s);
1804
1805       if (width != 0 && width < HOST_BITS_PER_WIDE_INT)
1806         {
1807           l0u &= ((HOST_WIDE_INT) 1 << width) - 1;
1808           l1u &= ((HOST_WIDE_INT) 1 << width) - 1;
1809
1810           if (l0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1811             l0s |= ((HOST_WIDE_INT) (-1) << width);
1812
1813           if (l1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1814             l1s |= ((HOST_WIDE_INT) (-1) << width);
1815         }
1816
1817       equal = (h0u == h1u && l0u == l1u);
1818       op0lt = (h0s < h1s || (h0s == h1s && l0u < l1u));
1819       op1lt = (h1s < h0s || (h1s == h0s && l1u < l0u));
1820       op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u));
1821       op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u));
1822     }
1823
1824   /* Otherwise, there are some code-specific tests we can make.  */
1825   else
1826     {
1827       switch (code)
1828         {
1829         case EQ:
1830           /* References to the frame plus a constant or labels cannot
1831              be zero, but a SYMBOL_REF can due to #pragma weak.  */
1832           if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1833                || GET_CODE (op0) == LABEL_REF)
1834 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1835               /* On some machines, the ap reg can be 0 sometimes.  */
1836               && op0 != arg_pointer_rtx
1837 #endif
1838                 )
1839             return const0_rtx;
1840           break;
1841
1842         case NE:
1843           if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1844                || GET_CODE (op0) == LABEL_REF)
1845 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1846               && op0 != arg_pointer_rtx
1847 #endif
1848               )
1849             return const_true_rtx;
1850           break;
1851
1852         case GEU:
1853           /* Unsigned values are never negative.  */
1854           if (op1 == const0_rtx)
1855             return const_true_rtx;
1856           break;
1857
1858         case LTU:
1859           if (op1 == const0_rtx)
1860             return const0_rtx;
1861           break;
1862
1863         case LEU:
1864           /* Unsigned values are never greater than the largest
1865              unsigned value.  */
1866           if (GET_CODE (op1) == CONST_INT
1867               && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1868             && INTEGRAL_MODE_P (mode))
1869           return const_true_rtx;
1870           break;
1871
1872         case GTU:
1873           if (GET_CODE (op1) == CONST_INT
1874               && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1875               && INTEGRAL_MODE_P (mode))
1876             return const0_rtx;
1877           break;
1878
1879         default:
1880           break;
1881         }
1882
1883       return 0;
1884     }
1885
1886   /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set
1887      as appropriate.  */
1888   switch (code)
1889     {
1890     case EQ:
1891       return equal ? const_true_rtx : const0_rtx;
1892     case NE:
1893       return ! equal ? const_true_rtx : const0_rtx;
1894     case LT:
1895       return op0lt ? const_true_rtx : const0_rtx;
1896     case GT:
1897       return op1lt ? const_true_rtx : const0_rtx;
1898     case LTU:
1899       return op0ltu ? const_true_rtx : const0_rtx;
1900     case GTU:
1901       return op1ltu ? const_true_rtx : const0_rtx;
1902     case LE:
1903       return equal || op0lt ? const_true_rtx : const0_rtx;
1904     case GE:
1905       return equal || op1lt ? const_true_rtx : const0_rtx;
1906     case LEU:
1907       return equal || op0ltu ? const_true_rtx : const0_rtx;
1908     case GEU:
1909       return equal || op1ltu ? const_true_rtx : const0_rtx;
1910     default:
1911       abort ();
1912     }
1913 }
1914 \f
1915 /* Simplify CODE, an operation with result mode MODE and three operands,
1916    OP0, OP1, and OP2.  OP0_MODE was the mode of OP0 before it became
1917    a constant.  Return 0 if no simplifications is possible.  */
1918
1919 rtx
1920 simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
1921      enum rtx_code code;
1922      enum machine_mode mode, op0_mode;
1923      rtx op0, op1, op2;
1924 {
1925   unsigned int width = GET_MODE_BITSIZE (mode);
1926
1927   /* VOIDmode means "infinite" precision.  */
1928   if (width == 0)
1929     width = HOST_BITS_PER_WIDE_INT;
1930
1931   switch (code)
1932     {
1933     case SIGN_EXTRACT:
1934     case ZERO_EXTRACT:
1935       if (GET_CODE (op0) == CONST_INT
1936           && GET_CODE (op1) == CONST_INT
1937           && GET_CODE (op2) == CONST_INT
1938           && ((unsigned) INTVAL (op1) + (unsigned) INTVAL (op2) <= width)
1939           && width <= (unsigned) HOST_BITS_PER_WIDE_INT)
1940         {
1941           /* Extracting a bit-field from a constant */
1942           HOST_WIDE_INT val = INTVAL (op0);
1943
1944           if (BITS_BIG_ENDIAN)
1945             val >>= (GET_MODE_BITSIZE (op0_mode)
1946                      - INTVAL (op2) - INTVAL (op1));
1947           else
1948             val >>= INTVAL (op2);
1949
1950           if (HOST_BITS_PER_WIDE_INT != INTVAL (op1))
1951             {
1952               /* First zero-extend.  */
1953               val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1;
1954               /* If desired, propagate sign bit.  */
1955               if (code == SIGN_EXTRACT
1956                   && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1))))
1957                 val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1);
1958             }
1959
1960           /* Clear the bits that don't belong in our mode,
1961              unless they and our sign bit are all one.
1962              So we get either a reasonable negative value or a reasonable
1963              unsigned value for this mode.  */
1964           if (width < HOST_BITS_PER_WIDE_INT
1965               && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
1966                   != ((HOST_WIDE_INT) (-1) << (width - 1))))
1967             val &= ((HOST_WIDE_INT) 1 << width) - 1;
1968
1969           return GEN_INT (val);
1970         }
1971       break;
1972
1973     case IF_THEN_ELSE:
1974       if (GET_CODE (op0) == CONST_INT)
1975         return op0 != const0_rtx ? op1 : op2;
1976
1977       /* Convert a == b ? b : a to "a".  */
1978       if (GET_CODE (op0) == NE && ! side_effects_p (op0)
1979           && rtx_equal_p (XEXP (op0, 0), op1)
1980           && rtx_equal_p (XEXP (op0, 1), op2))
1981         return op1;
1982       else if (GET_CODE (op0) == EQ && ! side_effects_p (op0)
1983           && rtx_equal_p (XEXP (op0, 1), op1)
1984           && rtx_equal_p (XEXP (op0, 0), op2))
1985         return op2;
1986       else if (GET_RTX_CLASS (GET_CODE (op0)) == '<' && ! side_effects_p (op0))
1987         {
1988           enum machine_mode cmp_mode = (GET_MODE (XEXP (op0, 0)) == VOIDmode
1989                                         ? GET_MODE (XEXP (op0, 1))
1990                                         : GET_MODE (XEXP (op0, 0)));
1991           rtx temp
1992              = simplify_relational_operation (GET_CODE (op0), cmp_mode,
1993                                               XEXP (op0, 0), XEXP (op0, 1));
1994
1995           /* See if any simplifications were possible.  */
1996           if (temp == const0_rtx)
1997             return op2;
1998           else if (temp == const1_rtx)
1999             return op1;
2000           else if (temp)
2001             op0 = temp;
2002
2003           /* Look for happy constants in op1 and op2.  */
2004           if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
2005             {
2006               HOST_WIDE_INT t = INTVAL (op1);
2007               HOST_WIDE_INT f = INTVAL (op2);
2008
2009               if (t == STORE_FLAG_VALUE && f == 0)
2010                 code = GET_CODE (op0);
2011               else if (t == 0 && f == STORE_FLAG_VALUE
2012                        && can_reverse_comparison_p (op0, NULL_RTX))
2013                 code = reverse_condition (GET_CODE (op0));
2014               else
2015                 break;
2016
2017               return gen_rtx_fmt_ee (code, mode, XEXP (op0, 0), XEXP (op0, 1));
2018             }
2019         }
2020       break;
2021
2022     default:
2023       abort ();
2024     }
2025
2026   return 0;
2027 }
2028
2029 /* Simplify X, an rtx expression.
2030
2031    Return the simplified expression or NULL if no simplifications
2032    were possible.
2033
2034    This is the preferred entry point into the simplification routines;
2035    however, we still allow passes to call the more specific routines.
2036
2037    Right now GCC has three (yes, three) major bodies of RTL simplficiation
2038    code that need to be unified.
2039
2040         1. fold_rtx in cse.c.  This code uses various CSE specific
2041            information to aid in RTL simplification.
2042
2043         2. simplify_rtx in combine.c.  Similar to fold_rtx, except that
2044            it uses combine specific information to aid in RTL
2045            simplification.
2046
2047         3. The routines in this file.
2048
2049
2050    Long term we want to only have one body of simplification code; to
2051    get to that state I recommend the following steps:
2052
2053         1. Pour over fold_rtx & simplify_rtx and move any simplifications
2054            which are not pass dependent state into these routines.
2055
2056         2. As code is moved by #1, change fold_rtx & simplify_rtx to
2057            use this routine whenever possible.
2058
2059         3. Allow for pass dependent state to be provided to these
2060            routines and add simplifications based on the pass dependent
2061            state.  Remove code from cse.c & combine.c that becomes
2062            redundant/dead.
2063
2064     It will take time, but ultimately the compiler will be easier to
2065     maintain and improve.  It's totally silly that when we add a
2066     simplification that it needs to be added to 4 places (3 for RTL
2067     simplification and 1 for tree simplification.  */
2068
2069 rtx
2070 simplify_rtx (x)
2071      rtx x;
2072 {
2073   enum rtx_code code;
2074   enum machine_mode mode;
2075
2076   mode = GET_MODE (x);
2077   code = GET_CODE (x);
2078
2079   switch (GET_RTX_CLASS (code))
2080     {
2081     case '1':
2082       return simplify_unary_operation (code, mode,
2083                                        XEXP (x, 0), GET_MODE (XEXP (x, 0)));
2084     case '2':
2085     case 'c':
2086       return simplify_binary_operation (code, mode, XEXP (x, 0), XEXP (x, 1));
2087
2088     case '3':
2089     case 'b':
2090       return simplify_ternary_operation (code, mode, GET_MODE (XEXP (x, 0)),
2091                                          XEXP (x, 0), XEXP (x, 1), XEXP (x, 2));
2092
2093     case '<':
2094       return simplify_relational_operation (code, GET_MODE (XEXP (x, 0)),
2095                                             XEXP (x, 0), XEXP (x, 1));
2096     default:
2097       return NULL;
2098     }
2099 }
2100 \f
2101
2102 /* Allocate a struct elt_list and fill in its two elements with the
2103    arguments.  */
2104
2105 static struct elt_list *
2106 new_elt_list (next, elt)
2107      struct elt_list *next;
2108      cselib_val *elt;
2109 {
2110   struct elt_list *el = empty_elt_lists;
2111
2112   if (el)
2113     empty_elt_lists = el->next;
2114   else
2115     el = (struct elt_list *) obstack_alloc (&cselib_obstack,
2116                                             sizeof (struct elt_list));
2117   el->next = next;
2118   el->elt = elt;
2119   return el;
2120 }
2121
2122 /* Allocate a struct elt_loc_list and fill in its two elements with the
2123    arguments.  */
2124
2125 static struct elt_loc_list *
2126 new_elt_loc_list (next, loc)
2127      struct elt_loc_list *next;
2128      rtx loc;
2129 {
2130   struct elt_loc_list *el = empty_elt_loc_lists;
2131
2132   if (el)
2133     empty_elt_loc_lists = el->next;
2134   else
2135     el = (struct elt_loc_list *) obstack_alloc (&cselib_obstack,
2136                                                 sizeof (struct elt_loc_list));
2137   el->next = next;
2138   el->loc = loc;
2139   el->setting_insn = cselib_current_insn;
2140   return el;
2141 }
2142
2143 /* The elt_list at *PL is no longer needed.  Unchain it and free its
2144    storage.  */
2145
2146 static void
2147 unchain_one_elt_list (pl)
2148      struct elt_list **pl;
2149 {
2150   struct elt_list *l = *pl;
2151
2152   *pl = l->next;
2153   l->next = empty_elt_lists;
2154   empty_elt_lists = l;
2155 }
2156
2157 /* Likewise for elt_loc_lists.  */
2158
2159 static void
2160 unchain_one_elt_loc_list (pl)
2161      struct elt_loc_list **pl;
2162 {
2163   struct elt_loc_list *l = *pl;
2164
2165   *pl = l->next;
2166   l->next = empty_elt_loc_lists;
2167   empty_elt_loc_lists = l;
2168 }
2169
2170 /* Likewise for cselib_vals.  This also frees the addr_list associated with
2171    V.  */
2172
2173 static void
2174 unchain_one_value (v)
2175      cselib_val *v;
2176 {
2177   while (v->addr_list)
2178     unchain_one_elt_list (&v->addr_list);
2179
2180   v->u.next_free = empty_vals;
2181   empty_vals = v;
2182 }
2183
2184 /* Remove all entries from the hash table.  Also used during
2185    initialization.  */
2186
2187 static void
2188 clear_table ()
2189 {
2190   unsigned int i;
2191
2192   for (i = 0; i < cselib_nregs; i++)
2193     REG_VALUES (i) = 0;
2194
2195   htab_empty (hash_table);
2196   obstack_free (&cselib_obstack, cselib_startobj);
2197
2198   empty_vals = 0;
2199   empty_elt_lists = 0;
2200   empty_elt_loc_lists = 0;
2201   n_useless_values = 0;
2202
2203   next_unknown_value = 0;
2204 }
2205
2206 /* The equality test for our hash table.  The first argument ENTRY is a table
2207    element (i.e. a cselib_val), while the second arg X is an rtx.  */
2208
2209 static int
2210 entry_and_rtx_equal_p (entry, x_arg)
2211      const void *entry, *x_arg;
2212 {
2213   struct elt_loc_list *l;
2214   const cselib_val *v = (const cselib_val *) entry;
2215   rtx x = (rtx) x_arg;
2216
2217   /* We don't guarantee that distinct rtx's have different hash values,
2218      so we need to do a comparison.  */
2219   for (l = v->locs; l; l = l->next)
2220     if (rtx_equal_for_cselib_p (l->loc, x))
2221       return 1;
2222
2223   return 0;
2224 }
2225
2226 /* The hash function for our hash table.  The value is always computed with
2227    hash_rtx when adding an element; this function just extracts the hash
2228    value from a cselib_val structure.  */
2229
2230 static unsigned int
2231 get_value_hash (entry)
2232      const void *entry;
2233 {
2234   const cselib_val *v = (const cselib_val *) entry;
2235   return v->value;
2236 }
2237
2238 /* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
2239    only return true for values which point to a cselib_val whose value
2240    element has been set to zero, which implies the cselib_val will be
2241    removed.  */
2242
2243 int
2244 references_value_p (x, only_useless)
2245      rtx x;
2246      int only_useless;
2247 {
2248   enum rtx_code code = GET_CODE (x);
2249   const char *fmt = GET_RTX_FORMAT (code);
2250   int i, j;
2251
2252   if (GET_CODE (x) == VALUE
2253       && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
2254     return 1;
2255
2256   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2257     {
2258       if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
2259         return 1;
2260       else if (fmt[i] == 'E')
2261         for (j = 0; j < XVECLEN (x, i); j++)
2262           if (references_value_p (XVECEXP (x, i, j), only_useless))
2263             return 1;
2264     }
2265
2266   return 0;
2267 }
2268
2269 /* For all locations found in X, delete locations that reference useless
2270    values (i.e. values without any location).  Called through
2271    htab_traverse.  */
2272
2273 static int
2274 discard_useless_locs (x, info)
2275      void **x;
2276      void *info ATTRIBUTE_UNUSED;
2277 {
2278   cselib_val *v = (cselib_val *)*x;
2279   struct elt_loc_list **p = &v->locs;
2280   int had_locs = v->locs != 0;
2281
2282   while (*p)
2283     {
2284       if (references_value_p ((*p)->loc, 1))
2285         unchain_one_elt_loc_list (p);
2286       else
2287         p = &(*p)->next;
2288     }
2289
2290   if (had_locs && v->locs == 0)
2291     {
2292       n_useless_values++;
2293       values_became_useless = 1;
2294     }
2295   return 1;
2296 }
2297
2298 /* If X is a value with no locations, remove it from the hashtable.  */
2299
2300 static int
2301 discard_useless_values (x, info)
2302      void **x;
2303      void *info ATTRIBUTE_UNUSED;
2304 {
2305   cselib_val *v = (cselib_val *)*x;
2306
2307   if (v->locs == 0)
2308     {
2309       htab_clear_slot (hash_table, x);
2310       unchain_one_value (v);
2311       n_useless_values--;
2312     }
2313
2314   return 1;
2315 }
2316
2317 /* Clean out useless values (i.e. those which no longer have locations
2318    associated with them) from the hash table.  */
2319
2320 static void
2321 remove_useless_values ()
2322 {
2323   /* First pass: eliminate locations that reference the value.  That in
2324      turn can make more values useless.  */
2325   do
2326     {
2327       values_became_useless = 0;
2328       htab_traverse (hash_table, discard_useless_locs, 0);
2329     }
2330   while (values_became_useless);
2331
2332   /* Second pass: actually remove the values.  */
2333   htab_traverse (hash_table, discard_useless_values, 0);
2334
2335   if (n_useless_values != 0)
2336     abort ();
2337 }
2338
2339 /* Return nonzero if we can prove that X and Y contain the same value, taking
2340    our gathered information into account.  */
2341
2342 int
2343 rtx_equal_for_cselib_p (x, y)
2344      rtx x, y;
2345 {
2346   enum rtx_code code;
2347   const char *fmt;
2348   int i;
2349
2350   if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
2351     {
2352       cselib_val *e = cselib_lookup (x, VOIDmode, 0);
2353
2354       if (e)
2355         x = e->u.val_rtx;
2356     }
2357
2358   if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
2359     {
2360       cselib_val *e = cselib_lookup (y, VOIDmode, 0);
2361
2362       if (e)
2363         y = e->u.val_rtx;
2364     }
2365
2366   if (x == y)
2367     return 1;
2368
2369   if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
2370     return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
2371
2372   if (GET_CODE (x) == VALUE)
2373     {
2374       cselib_val *e = CSELIB_VAL_PTR (x);
2375       struct elt_loc_list *l;
2376
2377       for (l = e->locs; l; l = l->next)
2378         {
2379           rtx t = l->loc;
2380
2381           /* Avoid infinite recursion.  */
2382           if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2383             continue;
2384           else if (rtx_equal_for_cselib_p (t, y))
2385             return 1;
2386         }
2387
2388       return 0;
2389     }
2390
2391   if (GET_CODE (y) == VALUE)
2392     {
2393       cselib_val *e = CSELIB_VAL_PTR (y);
2394       struct elt_loc_list *l;
2395
2396       for (l = e->locs; l; l = l->next)
2397         {
2398           rtx t = l->loc;
2399
2400           if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2401             continue;
2402           else if (rtx_equal_for_cselib_p (x, t))
2403             return 1;
2404         }
2405
2406       return 0;
2407     }
2408
2409   if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
2410     return 0;
2411
2412   /* This won't be handled correctly by the code below.  */
2413   if (GET_CODE (x) == LABEL_REF)
2414     return XEXP (x, 0) == XEXP (y, 0);
2415
2416   code = GET_CODE (x);
2417   fmt = GET_RTX_FORMAT (code);
2418
2419   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2420     {
2421       int j;
2422
2423       switch (fmt[i])
2424         {
2425         case 'w':
2426           if (XWINT (x, i) != XWINT (y, i))
2427             return 0;
2428           break;
2429
2430         case 'n':
2431         case 'i':
2432           if (XINT (x, i) != XINT (y, i))
2433             return 0;
2434           break;
2435
2436         case 'V':
2437         case 'E':
2438           /* Two vectors must have the same length.  */
2439           if (XVECLEN (x, i) != XVECLEN (y, i))
2440             return 0;
2441
2442           /* And the corresponding elements must match.  */
2443           for (j = 0; j < XVECLEN (x, i); j++)
2444             if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
2445                                           XVECEXP (y, i, j)))
2446               return 0;
2447           break;
2448
2449         case 'e':
2450           if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
2451             return 0;
2452           break;
2453
2454         case 'S':
2455         case 's':
2456           if (strcmp (XSTR (x, i), XSTR (y, i)))
2457             return 0;
2458           break;
2459
2460         case 'u':
2461           /* These are just backpointers, so they don't matter.  */
2462           break;
2463
2464         case '0':
2465         case 't':
2466           break;
2467
2468           /* It is believed that rtx's at this level will never
2469              contain anything but integers and other rtx's,
2470              except for within LABEL_REFs and SYMBOL_REFs.  */
2471         default:
2472           abort ();
2473         }
2474     }
2475   return 1;
2476 }
2477
2478 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
2479    For registers and memory locations, we look up their cselib_val structure
2480    and return its VALUE element.
2481    Possible reasons for return 0 are: the object is volatile, or we couldn't
2482    find a register or memory location in the table and CREATE is zero.  If
2483    CREATE is nonzero, table elts are created for regs and mem.
2484    MODE is used in hashing for CONST_INTs only;
2485    otherwise the mode of X is used.  */
2486
2487 static unsigned int
2488 hash_rtx (x, mode, create)
2489      rtx x;
2490      enum machine_mode mode;
2491      int create;
2492 {
2493   cselib_val *e;
2494   int i, j;
2495   enum rtx_code code;
2496   const char *fmt;
2497   unsigned int hash = 0;
2498
2499   /* repeat is used to turn tail-recursion into iteration.  */
2500  repeat:
2501   code = GET_CODE (x);
2502   hash += (unsigned) code + (unsigned) GET_MODE (x);
2503
2504   switch (code)
2505     {
2506     case MEM:
2507     case REG:
2508       e = cselib_lookup (x, GET_MODE (x), create);
2509       if (! e)
2510         return 0;
2511
2512       hash += e->value;
2513       return hash;
2514
2515     case CONST_INT:
2516       hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
2517       return hash ? hash : CONST_INT;
2518
2519     case CONST_DOUBLE:
2520       /* This is like the general case, except that it only counts
2521          the integers representing the constant.  */
2522       hash += (unsigned) code + (unsigned) GET_MODE (x);
2523       if (GET_MODE (x) != VOIDmode)
2524         for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2525           hash += XWINT (x, i);
2526       else
2527         hash += ((unsigned) CONST_DOUBLE_LOW (x)
2528                  + (unsigned) CONST_DOUBLE_HIGH (x));
2529       return hash ? hash : CONST_DOUBLE;
2530
2531       /* Assume there is only one rtx object for any given label.  */
2532     case LABEL_REF:
2533       hash
2534         += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2535       return hash ? hash : LABEL_REF;
2536
2537     case SYMBOL_REF:
2538       hash
2539         += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2540       return hash ? hash : SYMBOL_REF;
2541
2542     case PRE_DEC:
2543     case PRE_INC:
2544     case POST_DEC:
2545     case POST_INC:
2546     case POST_MODIFY:
2547     case PRE_MODIFY:
2548     case PC:
2549     case CC0:
2550     case CALL:
2551     case UNSPEC_VOLATILE:
2552       return 0;
2553
2554     case ASM_OPERANDS:
2555       if (MEM_VOLATILE_P (x))
2556         return 0;
2557
2558       break;
2559
2560     default:
2561       break;
2562     }
2563
2564   i = GET_RTX_LENGTH (code) - 1;
2565   fmt = GET_RTX_FORMAT (code);
2566   for (; i >= 0; i--)
2567     {
2568       if (fmt[i] == 'e')
2569         {
2570           rtx tem = XEXP (x, i);
2571           unsigned int tem_hash;
2572
2573           /* If we are about to do the last recursive call
2574              needed at this level, change it into iteration.
2575              This function  is called enough to be worth it.  */
2576           if (i == 0)
2577             {
2578               x = tem;
2579               goto repeat;
2580             }
2581
2582           tem_hash = hash_rtx (tem, 0, create);
2583           if (tem_hash == 0)
2584             return 0;
2585
2586           hash += tem_hash;
2587         }
2588       else if (fmt[i] == 'E')
2589         for (j = 0; j < XVECLEN (x, i); j++)
2590           {
2591             unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
2592
2593             if (tem_hash == 0)
2594               return 0;
2595
2596             hash += tem_hash;
2597           }
2598       else if (fmt[i] == 's')
2599         {
2600           const unsigned char *p = (const unsigned char *) XSTR (x, i);
2601
2602           if (p)
2603             while (*p)
2604               hash += *p++;
2605         }
2606       else if (fmt[i] == 'i')
2607         hash += XINT (x, i);
2608       else if (fmt[i] == '0' || fmt[i] == 't')
2609         /* unused */;
2610       else
2611         abort ();
2612     }
2613
2614   return hash ? hash : 1 + GET_CODE (x);
2615 }
2616
2617 /* Create a new value structure for VALUE and initialize it.  The mode of the
2618    value is MODE.  */
2619
2620 static cselib_val *
2621 new_cselib_val (value, mode)
2622      unsigned int value;
2623      enum machine_mode mode;
2624 {
2625   cselib_val *e = empty_vals;
2626
2627   if (e)
2628     empty_vals = e->u.next_free;
2629   else
2630     e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
2631
2632   if (value == 0)
2633     abort ();
2634
2635   e->value = value;
2636   e->u.val_rtx = gen_rtx_VALUE (mode);
2637   CSELIB_VAL_PTR (e->u.val_rtx) = e;
2638   e->addr_list = 0;
2639   e->locs = 0;
2640   return e;
2641 }
2642
2643 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
2644    contains the data at this address.  X is a MEM that represents the
2645    value.  Update the two value structures to represent this situation.  */
2646
2647 static void
2648 add_mem_for_addr (addr_elt, mem_elt, x)
2649      cselib_val *addr_elt, *mem_elt;
2650      rtx x;
2651 {
2652   rtx new;
2653   struct elt_loc_list *l;
2654
2655   /* Avoid duplicates.  */
2656   for (l = mem_elt->locs; l; l = l->next)
2657     if (GET_CODE (l->loc) == MEM
2658         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
2659       return;
2660
2661   new = gen_rtx_MEM (GET_MODE (x), addr_elt->u.val_rtx);
2662   MEM_COPY_ATTRIBUTES (new, x);
2663
2664   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
2665   mem_elt->locs = new_elt_loc_list (mem_elt->locs, new);
2666 }
2667
2668 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
2669    If CREATE, make a new one if we haven't seen it before.  */
2670
2671 static cselib_val *
2672 cselib_lookup_mem (x, create)
2673      rtx x;
2674      int create;
2675 {
2676   void **slot;
2677   cselib_val *addr;
2678   cselib_val *mem_elt;
2679   struct elt_list *l;
2680
2681   if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode
2682       || (FLOAT_MODE_P (GET_MODE (x)) && flag_float_store))
2683     return 0;
2684
2685   /* Look up the value for the address.  */
2686   addr = cselib_lookup (XEXP (x, 0), GET_MODE (x), create);
2687   if (! addr)
2688     return 0;
2689
2690   /* Find a value that describes a value of our mode at that address.  */
2691   for (l = addr->addr_list; l; l = l->next)
2692     if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2693       return l->elt;
2694
2695   if (! create)
2696     return 0;
2697
2698   mem_elt = new_cselib_val (++next_unknown_value, GET_MODE (x));
2699   add_mem_for_addr (addr, mem_elt, x);
2700   slot = htab_find_slot_with_hash (hash_table, x, mem_elt->value, INSERT);
2701   *slot = mem_elt;
2702   return mem_elt;
2703 }
2704
2705 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2706    with VALUE expressions.  This way, it becomes independent of changes
2707    to registers and memory.
2708    X isn't actually modified; if modifications are needed, new rtl is
2709    allocated.  However, the return value can share rtl with X.  */
2710
2711 static rtx
2712 cselib_subst_to_values (x)
2713      rtx x;
2714 {
2715   enum rtx_code code = GET_CODE (x);
2716   const char *fmt = GET_RTX_FORMAT (code);
2717   cselib_val *e;
2718   struct elt_list *l;
2719   rtx copy = x;
2720   int i;
2721
2722   switch (code)
2723     {
2724     case REG:
2725       for (l = REG_VALUES (REGNO (x)); l; l = l->next)
2726         if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2727           return l->elt->u.val_rtx;
2728
2729       abort ();
2730
2731     case MEM:
2732       e = cselib_lookup_mem (x, 0);
2733       if (! e)
2734         abort ();
2735       return e->u.val_rtx;
2736
2737       /* CONST_DOUBLEs must be special-cased here so that we won't try to
2738          look up the CONST_DOUBLE_MEM inside.  */
2739     case CONST_DOUBLE:
2740     case CONST_INT:
2741       return x;
2742
2743     default:
2744       break;
2745     }
2746
2747   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2748     {
2749       if (fmt[i] == 'e')
2750         {
2751           rtx t = cselib_subst_to_values (XEXP (x, i));
2752
2753           if (t != XEXP (x, i) && x == copy)
2754             copy = shallow_copy_rtx (x);
2755
2756           XEXP (copy, i) = t;
2757         }
2758       else if (fmt[i] == 'E')
2759         {
2760           int j, k;
2761
2762           for (j = 0; j < XVECLEN (x, i); j++)
2763             {
2764               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
2765
2766               if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
2767                 {
2768                   if (x == copy)
2769                     copy = shallow_copy_rtx (x);
2770
2771                   XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
2772                   for (k = 0; k < j; k++)
2773                     XVECEXP (copy, i, k) = XVECEXP (x, i, k);
2774                 }
2775
2776               XVECEXP (copy, i, j) = t;
2777             }
2778         }
2779     }
2780
2781   return copy;
2782 }
2783
2784 /* Look up the rtl expression X in our tables and return the value it has.
2785    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
2786    we create a new one if possible, using mode MODE if X doesn't have a mode
2787    (i.e. because it's a constant).  */
2788
2789 cselib_val *
2790 cselib_lookup (x, mode, create)
2791      rtx x;
2792      enum machine_mode mode;
2793      int create;
2794 {
2795   void **slot;
2796   cselib_val *e;
2797   unsigned int hashval;
2798
2799   if (GET_MODE (x) != VOIDmode)
2800     mode = GET_MODE (x);
2801
2802   if (GET_CODE (x) == VALUE)
2803     return CSELIB_VAL_PTR (x);
2804
2805   if (GET_CODE (x) == REG)
2806     {
2807       struct elt_list *l;
2808       unsigned int i = REGNO (x);
2809
2810       for (l = REG_VALUES (i); l; l = l->next)
2811         if (mode == GET_MODE (l->elt->u.val_rtx))
2812           return l->elt;
2813
2814       if (! create)
2815         return 0;
2816
2817       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
2818       e->locs = new_elt_loc_list (e->locs, x);
2819       REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
2820       slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
2821       *slot = e;
2822       return e;
2823     }
2824
2825   if (GET_CODE (x) == MEM)
2826     return cselib_lookup_mem (x, create);
2827
2828   hashval = hash_rtx (x, mode, create);
2829   /* Can't even create if hashing is not possible.  */
2830   if (! hashval)
2831     return 0;
2832
2833   slot = htab_find_slot_with_hash (hash_table, x, hashval,
2834                                    create ? INSERT : NO_INSERT);
2835   if (slot == 0)
2836     return 0;
2837
2838   e = (cselib_val *) *slot;
2839   if (e)
2840     return e;
2841
2842   e = new_cselib_val (hashval, mode);
2843
2844   /* We have to fill the slot before calling cselib_subst_to_values:
2845      the hash table is inconsistent until we do so, and
2846      cselib_subst_to_values will need to do lookups.  */
2847   *slot = (void *) e;
2848   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
2849   return e;
2850 }
2851
2852 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
2853    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
2854    is used to determine how many hard registers are being changed.  If MODE
2855    is VOIDmode, then only REGNO is being changed; this is used when
2856    invalidating call clobbered registers across a call.  */
2857
2858 static void
2859 cselib_invalidate_regno (regno, mode)
2860      unsigned int regno;
2861      enum machine_mode mode;
2862 {
2863   unsigned int endregno;
2864   unsigned int i;
2865
2866   /* If we see pseudos after reload, something is _wrong_.  */
2867   if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
2868       && reg_renumber[regno] >= 0)
2869     abort ();
2870
2871   /* Determine the range of registers that must be invalidated.  For
2872      pseudos, only REGNO is affected.  For hard regs, we must take MODE
2873      into account, and we must also invalidate lower register numbers
2874      if they contain values that overlap REGNO.  */
2875   endregno = regno + 1;
2876   if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode)
2877     endregno = regno + HARD_REGNO_NREGS (regno, mode);
2878
2879   for (i = 0; i < endregno; i++)
2880     {
2881       struct elt_list **l = &REG_VALUES (i);
2882
2883       /* Go through all known values for this reg; if it overlaps the range
2884          we're invalidating, remove the value.  */
2885       while (*l)
2886         {
2887           cselib_val *v = (*l)->elt;
2888           struct elt_loc_list **p;
2889           unsigned int this_last = i;
2890
2891           if (i < FIRST_PSEUDO_REGISTER)
2892             this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
2893
2894           if (this_last < regno)
2895             {
2896               l = &(*l)->next;
2897               continue;
2898             }
2899
2900           /* We have an overlap.  */
2901           unchain_one_elt_list (l);
2902
2903           /* Now, we clear the mapping from value to reg.  It must exist, so
2904              this code will crash intentionally if it doesn't.  */
2905           for (p = &v->locs; ; p = &(*p)->next)
2906             {
2907               rtx x = (*p)->loc;
2908
2909               if (GET_CODE (x) == REG && REGNO (x) == i)
2910                 {
2911                   unchain_one_elt_loc_list (p);
2912                   break;
2913                 }
2914             }
2915           if (v->locs == 0)
2916             n_useless_values++;
2917         }
2918     }
2919 }
2920
2921 /* The memory at address MEM_BASE is being changed.
2922    Return whether this change will invalidate VAL.  */
2923
2924 static int
2925 cselib_mem_conflict_p (mem_base, val)
2926      rtx mem_base;
2927      rtx val;
2928 {
2929   enum rtx_code code;
2930   const char *fmt;
2931   int i, j;
2932
2933   code = GET_CODE (val);
2934   switch (code)
2935     {
2936       /* Get rid of a few simple cases quickly. */
2937     case REG:
2938     case PC:
2939     case CC0:
2940     case SCRATCH:
2941     case CONST:
2942     case CONST_INT:
2943     case CONST_DOUBLE:
2944     case SYMBOL_REF:
2945     case LABEL_REF:
2946       return 0;
2947
2948     case MEM:
2949       if (GET_MODE (mem_base) == BLKmode
2950           || GET_MODE (val) == BLKmode
2951           || anti_dependence (val, mem_base))
2952         return 1;
2953
2954       /* The address may contain nested MEMs.  */
2955       break;
2956
2957     default:
2958       break;
2959     }
2960
2961   fmt = GET_RTX_FORMAT (code);
2962   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2963     {
2964       if (fmt[i] == 'e')
2965         {
2966           if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
2967             return 1;
2968         }
2969       else if (fmt[i] == 'E')
2970         for (j = 0; j < XVECLEN (val, i); j++)
2971           if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
2972             return 1;
2973     }
2974
2975   return 0;
2976 }
2977
2978 /* For the value found in SLOT, walk its locations to determine if any overlap
2979    INFO (which is a MEM rtx).  */
2980
2981 static int
2982 cselib_invalidate_mem_1 (slot, info)
2983      void **slot;
2984      void *info;
2985 {
2986   cselib_val *v = (cselib_val *) *slot;
2987   rtx mem_rtx = (rtx) info;
2988   struct elt_loc_list **p = &v->locs;
2989   int had_locs = v->locs != 0;
2990
2991   while (*p)
2992     {
2993       rtx x = (*p)->loc;
2994       cselib_val *addr;
2995       struct elt_list **mem_chain;
2996
2997       /* MEMs may occur in locations only at the top level; below
2998          that every MEM or REG is substituted by its VALUE.  */
2999       if (GET_CODE (x) != MEM
3000           || ! cselib_mem_conflict_p (mem_rtx, x))
3001         {
3002           p = &(*p)->next;
3003           continue;
3004         }
3005
3006       /* This one overlaps.  */
3007       /* We must have a mapping from this MEM's address to the
3008          value (E).  Remove that, too.  */
3009       addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
3010       mem_chain = &addr->addr_list;
3011       for (;;)
3012         {
3013           if ((*mem_chain)->elt == v)
3014             {
3015               unchain_one_elt_list (mem_chain);
3016               break;
3017             }
3018
3019           mem_chain = &(*mem_chain)->next;
3020         }
3021
3022       unchain_one_elt_loc_list (p);
3023     }
3024
3025   if (had_locs && v->locs == 0)
3026     n_useless_values++;
3027
3028   return 1;
3029 }
3030
3031 /* Invalidate any locations in the table which are changed because of a
3032    store to MEM_RTX.  If this is called because of a non-const call
3033    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
3034
3035 static void
3036 cselib_invalidate_mem (mem_rtx)
3037      rtx mem_rtx;
3038 {
3039   htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
3040 }
3041
3042 /* Invalidate DEST, which is being assigned to or clobbered.  The second and
3043    the third parameter exist so that this function can be passed to
3044    note_stores; they are ignored.  */
3045
3046 static void
3047 cselib_invalidate_rtx (dest, ignore, data)
3048      rtx dest;
3049      rtx ignore ATTRIBUTE_UNUSED;
3050      void *data ATTRIBUTE_UNUSED;
3051 {
3052   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
3053          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
3054     dest = XEXP (dest, 0);
3055
3056   if (GET_CODE (dest) == REG)
3057     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
3058   else if (GET_CODE (dest) == MEM)
3059     cselib_invalidate_mem (dest);
3060
3061   /* Some machines don't define AUTO_INC_DEC, but they still use push
3062      instructions.  We need to catch that case here in order to
3063      invalidate the stack pointer correctly.  Note that invalidating
3064      the stack pointer is different from invalidating DEST.  */
3065   if (push_operand (dest, GET_MODE (dest)))
3066     cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
3067 }
3068
3069 /* Record the result of a SET instruction.  DEST is being set; the source
3070    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
3071    describes its address.  */
3072
3073 static void
3074 cselib_record_set (dest, src_elt, dest_addr_elt)
3075      rtx dest;
3076      cselib_val *src_elt, *dest_addr_elt;
3077 {
3078   int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
3079
3080   if (src_elt == 0 || side_effects_p (dest))
3081     return;
3082
3083   if (dreg >= 0)
3084     {
3085       REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
3086       if (src_elt->locs == 0)
3087         n_useless_values--;
3088       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
3089     }
3090   else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
3091     {
3092       if (src_elt->locs == 0)
3093         n_useless_values--;
3094       add_mem_for_addr (dest_addr_elt, src_elt, dest);
3095     }
3096 }
3097
3098 /* Describe a single set that is part of an insn.  */
3099 struct set
3100 {
3101   rtx src;
3102   rtx dest;
3103   cselib_val *src_elt;
3104   cselib_val *dest_addr_elt;
3105 };
3106
3107 /* There is no good way to determine how many elements there can be
3108    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
3109 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
3110
3111 /* Record the effects of any sets in INSN.  */
3112 static void
3113 cselib_record_sets (insn)
3114      rtx insn;
3115 {
3116   int n_sets = 0;
3117   int i;
3118   struct set sets[MAX_SETS];
3119   rtx body = PATTERN (insn);
3120
3121   body = PATTERN (insn);
3122   /* Find all sets.  */
3123   if (GET_CODE (body) == SET)
3124     {
3125       sets[0].src = SET_SRC (body);
3126       sets[0].dest = SET_DEST (body);
3127       n_sets = 1;
3128     }
3129   else if (GET_CODE (body) == PARALLEL)
3130     {
3131       /* Look through the PARALLEL and record the values being
3132          set, if possible.  Also handle any CLOBBERs.  */
3133       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3134         {
3135           rtx x = XVECEXP (body, 0, i);
3136
3137           if (GET_CODE (x) == SET)
3138             {
3139               sets[n_sets].src = SET_SRC (x);
3140               sets[n_sets].dest = SET_DEST (x);
3141               n_sets++;
3142             }
3143         }
3144     }
3145
3146   /* Look up the values that are read.  Do this before invalidating the
3147      locations that are written.  */
3148   for (i = 0; i < n_sets; i++)
3149     {
3150       sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (sets[i].dest),
3151                                        1);
3152       if (GET_CODE (sets[i].dest) == MEM)
3153         sets[i].dest_addr_elt = cselib_lookup (XEXP (sets[i].dest, 0), Pmode,
3154                                                1);
3155       else
3156         sets[i].dest_addr_elt = 0;
3157     }
3158
3159   /* Invalidate all locations written by this insn.  Note that the elts we
3160      looked up in the previous loop aren't affected, just some of their
3161      locations may go away.  */
3162   note_stores (body, cselib_invalidate_rtx, NULL);
3163
3164   /* Now enter the equivalences in our tables.  */
3165   for (i = 0; i < n_sets; i++)
3166     cselib_record_set (sets[i].dest, sets[i].src_elt, sets[i].dest_addr_elt);
3167 }
3168
3169 /* Record the effects of INSN.  */
3170
3171 void
3172 cselib_process_insn (insn)
3173      rtx insn;
3174 {
3175   int i;
3176   rtx x;
3177
3178   cselib_current_insn = insn;
3179
3180   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
3181   if (GET_CODE (insn) == CODE_LABEL
3182       || (GET_CODE (insn) == NOTE
3183           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3184       || (GET_CODE (insn) == INSN
3185           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
3186           && MEM_VOLATILE_P (PATTERN (insn))))
3187     {
3188       clear_table ();
3189       return;
3190     }
3191
3192   if (! INSN_P (insn))
3193     {
3194       cselib_current_insn = 0;
3195       return;
3196     }
3197
3198   /* If this is a call instruction, forget anything stored in a
3199      call clobbered register, or, if this is not a const call, in
3200      memory.  */
3201   if (GET_CODE (insn) == CALL_INSN)
3202     {
3203       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3204         if (call_used_regs[i])
3205           cselib_invalidate_regno (i, VOIDmode);
3206
3207       if (! CONST_CALL_P (insn))
3208         cselib_invalidate_mem (callmem);
3209     }
3210
3211   cselib_record_sets (insn);
3212
3213 #ifdef AUTO_INC_DEC
3214   /* Clobber any registers which appear in REG_INC notes.  We
3215      could keep track of the changes to their values, but it is
3216      unlikely to help.  */
3217   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
3218     if (REG_NOTE_KIND (x) == REG_INC)
3219       cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
3220 #endif
3221
3222   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3223      after we have processed the insn.  */
3224   if (GET_CODE (insn) == CALL_INSN)
3225     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3226       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3227         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
3228
3229   cselib_current_insn = 0;
3230
3231   if (n_useless_values > MAX_USELESS_VALUES)
3232     remove_useless_values ();
3233 }
3234
3235 /* Make sure our varrays are big enough.  Not called from any cselib routines;
3236    it must be called by the user if it allocated new registers.  */
3237
3238 void
3239 cselib_update_varray_sizes ()
3240 {
3241   unsigned int nregs = max_reg_num ();
3242
3243   if (nregs == cselib_nregs)
3244     return;
3245
3246   cselib_nregs = nregs;
3247   VARRAY_GROW (reg_values, nregs);
3248 }
3249
3250 /* Initialize cselib for one pass.  The caller must also call
3251    init_alias_analysis.  */
3252
3253 void
3254 cselib_init ()
3255 {
3256   /* These are only created once.  */
3257   if (! callmem)
3258     {
3259       extern struct obstack permanent_obstack;
3260
3261       gcc_obstack_init (&cselib_obstack);
3262       cselib_startobj = obstack_alloc (&cselib_obstack, 0);
3263
3264       push_obstacks (&permanent_obstack, &permanent_obstack);
3265       callmem = gen_rtx_MEM (BLKmode, const0_rtx);
3266       pop_obstacks ();
3267       ggc_add_rtx_root (&callmem, 1);
3268     }
3269
3270   cselib_nregs = max_reg_num ();
3271   VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
3272   hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
3273   clear_table ();
3274 }
3275
3276 /* Called when the current user is done with cselib.  */
3277
3278 void
3279 cselib_finish ()
3280 {
3281   clear_table ();
3282   htab_delete (hash_table);
3283 }