gcc/simplify-rtx.c

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