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