gcc/fold-const.c

   1 /* Fold a constant sub-tree into a single node for C-compiler
   2    Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /*@@ This file should be rewritten to use an arbitrary precision
  22   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  23   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  24   @@ The routines that translate from the ap rep should
  25   @@ warn if precision et. al. is lost.
  26   @@ This would also make life easier when this technology is used
  27   @@ for cross-compilers.  */
  28
  29
  30 /* The entry points in this file are fold, size_int_wide, size_binop
  31    and force_fit_type.
  32
  33    fold takes a tree as argument and returns a simplified tree.
  34
  35    size_binop takes a tree code for an arithmetic operation
  36    and two operands that are trees, and produces a tree for the
  37    result, assuming the type comes from `sizetype'.
  38
  39    size_int takes an integer value, and creates a tree constant
  40    with type from `sizetype'.
  41
  42    force_fit_type takes a constant and prior overflow indicator, and
  43    forces the value to fit the type.  It returns an overflow indicator.  */
  44
  45 #include "config.h"
  46 #include "system.h"
  47 #include <setjmp.h>
  48 #include "flags.h"
  49 #include "tree.h"
  50 #include "rtl.h"
  51 #include "tm_p.h"
  52 #include "toplev.h"
  53 #include "ggc.h"
  54
  55 static void encode              PROTO((HOST_WIDE_INT *,
  56                                        HOST_WIDE_INT, HOST_WIDE_INT));
  57 static void decode              PROTO((HOST_WIDE_INT *,
  58                                        HOST_WIDE_INT *, HOST_WIDE_INT *));
  59 int div_and_round_double        PROTO((enum tree_code, int, HOST_WIDE_INT,
  60                                        HOST_WIDE_INT, HOST_WIDE_INT,
  61                                        HOST_WIDE_INT, HOST_WIDE_INT *,
  62                                        HOST_WIDE_INT *, HOST_WIDE_INT *,
  63                                        HOST_WIDE_INT *));
  64 static int split_tree           PROTO((tree, enum tree_code, tree *,
  65                                        tree *, int *));
  66 static tree int_const_binop     PROTO((enum tree_code, tree, tree, int, int));
  67 static tree const_binop         PROTO((enum tree_code, tree, tree, int));
  68 static tree fold_convert        PROTO((tree, tree));
  69 static enum tree_code invert_tree_comparison PROTO((enum tree_code));
  70 static enum tree_code swap_tree_comparison PROTO((enum tree_code));
  71 static int truth_value_p        PROTO((enum tree_code));
  72 static int operand_equal_for_comparison_p PROTO((tree, tree, tree));
  73 static int twoval_comparison_p  PROTO((tree, tree *, tree *, int *));
  74 static tree eval_subst          PROTO((tree, tree, tree, tree, tree));
  75 static tree omit_one_operand    PROTO((tree, tree, tree));
  76 static tree pedantic_omit_one_operand PROTO((tree, tree, tree));
  77 static tree distribute_bit_expr PROTO((enum tree_code, tree, tree, tree));
  78 static tree make_bit_field_ref  PROTO((tree, tree, int, int, int));
  79 static tree optimize_bit_field_compare PROTO((enum tree_code, tree,
  80                                               tree, tree));
  81 static tree decode_field_reference PROTO((tree, int *, int *,
  82                                           enum machine_mode *, int *,
  83                                           int *, tree *, tree *));
  84 static int all_ones_mask_p      PROTO((tree, int));
  85 static int simple_operand_p     PROTO((tree));
  86 static tree range_binop         PROTO((enum tree_code, tree, tree, int,
  87                                        tree, int));
  88 static tree make_range          PROTO((tree, int *, tree *, tree *));
  89 static tree build_range_check   PROTO((tree, tree, int, tree, tree));
  90 static int merge_ranges         PROTO((int *, tree *, tree *, int, tree, tree,
  91                                        int, tree, tree));
  92 static tree fold_range_test     PROTO((tree));
  93 static tree unextend            PROTO((tree, int, int, tree));
  94 static tree fold_truthop        PROTO((enum tree_code, tree, tree, tree));
  95 static tree strip_compound_expr PROTO((tree, tree));
  96 static int multiple_of_p        PROTO((tree, tree, tree));
  97 static tree constant_boolean_node PROTO((int, tree));
  98 static int count_cond           PROTO((tree, int));
  99 static void const_binop_1       PROTO((PTR));
 100 static void fold_convert_1      PROTO((PTR));
 101
 102 #ifndef BRANCH_COST
 103 #define BRANCH_COST 1
 104 #endif
 105
 106 /* Suppose A1 + B1 = SUM1, using 2's complement arithmetic ignoring overflow.
 107    Suppose A, B and SUM have the same respective signs as A1, B1, and SUM1.
 108    Then this yields nonzero if overflow occurred during the addition.
 109    Overflow occurs if A and B have the same sign, but A and SUM differ in sign.
 110    Use `^' to test whether signs differ, and `< 0' to isolate the sign.  */
 111 #define overflow_sum_sign(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
 112 \f
 113 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
 114    We do that by representing the two-word integer in 4 words, with only
 115    HOST_BITS_PER_WIDE_INT/2 bits stored in each word, as a positive number.  */
 116
 117 #define LOWPART(x) \
 118   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT/2)) - 1))
 119 #define HIGHPART(x) \
 120   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT/2)
 121 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT/2)
 122
 123 /* Unpack a two-word integer into 4 words.
 124    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
 125    WORDS points to the array of HOST_WIDE_INTs.  */
 126
 127 static void
 128 encode (words, low, hi)
 129      HOST_WIDE_INT *words;
 130      HOST_WIDE_INT low, hi;
 131 {
 132   words[0] = LOWPART (low);
 133   words[1] = HIGHPART (low);
 134   words[2] = LOWPART (hi);
 135   words[3] = HIGHPART (hi);
 136 }
 137
 138 /* Pack an array of 4 words into a two-word integer.
 139    WORDS points to the array of words.
 140    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
 141
 142 static void
 143 decode (words, low, hi)
 144      HOST_WIDE_INT *words;
 145      HOST_WIDE_INT *low, *hi;
 146 {
 147   *low = words[0] | words[1] * BASE;
 148   *hi = words[2] | words[3] * BASE;
 149 }
 150 \f
 151 /* Make the integer constant T valid for its type
 152    by setting to 0 or 1 all the bits in the constant
 153    that don't belong in the type.
 154    Yield 1 if a signed overflow occurs, 0 otherwise.
 155    If OVERFLOW is nonzero, a signed overflow has already occurred
 156    in calculating T, so propagate it.
 157
 158    Make the real constant T valid for its type by calling CHECK_FLOAT_VALUE,
 159    if it exists.  */
 160
 161 int
 162 force_fit_type (t, overflow)
 163      tree t;
 164      int overflow;
 165 {
 166   HOST_WIDE_INT low, high;
 167   register int prec;
 168
 169   if (TREE_CODE (t) == REAL_CST)
 170     {
 171 #ifdef CHECK_FLOAT_VALUE
 172       CHECK_FLOAT_VALUE (TYPE_MODE (TREE_TYPE (t)), TREE_REAL_CST (t),
 173                          overflow);
 174 #endif
 175       return overflow;
 176     }
 177
 178   else if (TREE_CODE (t) != INTEGER_CST)
 179     return overflow;
 180
 181   low = TREE_INT_CST_LOW (t);
 182   high = TREE_INT_CST_HIGH (t);
 183
 184   if (POINTER_TYPE_P (TREE_TYPE (t)))
 185     prec = POINTER_SIZE;
 186   else
 187     prec = TYPE_PRECISION (TREE_TYPE (t));
 188
 189   /* First clear all bits that are beyond the type's precision.  */
 190
 191   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 192     ;
 193   else if (prec > HOST_BITS_PER_WIDE_INT)
 194     {
 195       TREE_INT_CST_HIGH (t)
 196         &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 197     }
 198   else
 199     {
 200       TREE_INT_CST_HIGH (t) = 0;
 201       if (prec < HOST_BITS_PER_WIDE_INT)
 202         TREE_INT_CST_LOW (t) &= ~((HOST_WIDE_INT) (-1) << prec);
 203     }
 204
 205   /* Unsigned types do not suffer sign extension or overflow.  */
 206   if (TREE_UNSIGNED (TREE_TYPE (t)))
 207     return overflow;
 208
 209   /* If the value's sign bit is set, extend the sign.  */
 210   if (prec != 2 * HOST_BITS_PER_WIDE_INT
 211       && (prec > HOST_BITS_PER_WIDE_INT
 212           ? (TREE_INT_CST_HIGH (t)
 213              & ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
 214           : TREE_INT_CST_LOW (t) & ((HOST_WIDE_INT) 1 << (prec - 1))))
 215     {
 216       /* Value is negative:
 217          set to 1 all the bits that are outside this type's precision.  */
 218       if (prec > HOST_BITS_PER_WIDE_INT)
 219         {
 220           TREE_INT_CST_HIGH (t)
 221             |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 222         }
 223       else
 224         {
 225           TREE_INT_CST_HIGH (t) = -1;
 226           if (prec < HOST_BITS_PER_WIDE_INT)
 227             TREE_INT_CST_LOW (t) |= ((HOST_WIDE_INT) (-1) << prec);
 228         }
 229     }
 230
 231   /* Yield nonzero if signed overflow occurred.  */
 232   return
 233     ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
 234      != 0);
 235 }
 236 \f
 237 /* Add two doubleword integers with doubleword result.
 238    Each argument is given as two `HOST_WIDE_INT' pieces.
 239    One argument is L1 and H1; the other, L2 and H2.
 240    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 241
 242 int
 243 add_double (l1, h1, l2, h2, lv, hv)
 244      HOST_WIDE_INT l1, h1, l2, h2;
 245      HOST_WIDE_INT *lv, *hv;
 246 {
 247   HOST_WIDE_INT l, h;
 248
 249   l = l1 + l2;
 250   h = h1 + h2 + ((unsigned HOST_WIDE_INT) l < l1);
 251
 252   *lv = l;
 253   *hv = h;
 254   return overflow_sum_sign (h1, h2, h);
 255 }
 256
 257 /* Negate a doubleword integer with doubleword result.
 258    Return nonzero if the operation overflows, assuming it's signed.
 259    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 260    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 261
 262 int
 263 neg_double (l1, h1, lv, hv)
 264      HOST_WIDE_INT l1, h1;
 265      HOST_WIDE_INT *lv, *hv;
 266 {
 267   if (l1 == 0)
 268     {
 269       *lv = 0;
 270       *hv = - h1;
 271       return (*hv & h1) < 0;
 272     }
 273   else
 274     {
 275       *lv = - l1;
 276       *hv = ~ h1;
 277       return 0;
 278     }
 279 }
 280 \f
 281 /* Multiply two doubleword integers with doubleword result.
 282    Return nonzero if the operation overflows, assuming it's signed.
 283    Each argument is given as two `HOST_WIDE_INT' pieces.
 284    One argument is L1 and H1; the other, L2 and H2.
 285    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 286
 287 int
 288 mul_double (l1, h1, l2, h2, lv, hv)
 289      HOST_WIDE_INT l1, h1, l2, h2;
 290      HOST_WIDE_INT *lv, *hv;
 291 {
 292   HOST_WIDE_INT arg1[4];
 293   HOST_WIDE_INT arg2[4];
 294   HOST_WIDE_INT prod[4 * 2];
 295   register unsigned HOST_WIDE_INT carry;
 296   register int i, j, k;
 297   HOST_WIDE_INT toplow, tophigh, neglow, neghigh;
 298
 299   encode (arg1, l1, h1);
 300   encode (arg2, l2, h2);
 301
 302   bzero ((char *) prod, sizeof prod);
 303
 304   for (i = 0; i < 4; i++)
 305     {
 306       carry = 0;
 307       for (j = 0; j < 4; j++)
 308         {
 309           k = i + j;
 310           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 311           carry += arg1[i] * arg2[j];
 312           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 313           carry += prod[k];
 314           prod[k] = LOWPART (carry);
 315           carry = HIGHPART (carry);
 316         }
 317       prod[i + 4] = carry;
 318     }
 319
 320   decode (prod, lv, hv);        /* This ignores prod[4] through prod[4*2-1] */
 321
 322   /* Check for overflow by calculating the top half of the answer in full;
 323      it should agree with the low half's sign bit.  */
 324   decode (prod+4, &toplow, &tophigh);
 325   if (h1 < 0)
 326     {
 327       neg_double (l2, h2, &neglow, &neghigh);
 328       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 329     }
 330   if (h2 < 0)
 331     {
 332       neg_double (l1, h1, &neglow, &neghigh);
 333       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 334     }
 335   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 336 }
 337 \f
 338 /* Shift the doubleword integer in L1, H1 left by COUNT places
 339    keeping only PREC bits of result.
 340    Shift right if COUNT is negative.
 341    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 342    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 343
 344 void
 345 lshift_double (l1, h1, count, prec, lv, hv, arith)
 346      HOST_WIDE_INT l1, h1, count;
 347      int prec;
 348      HOST_WIDE_INT *lv, *hv;
 349      int arith;
 350 {
 351   if (count < 0)
 352     {
 353       rshift_double (l1, h1, - count, prec, lv, hv, arith);
 354       return;
 355     }
 356
 357 #ifdef SHIFT_COUNT_TRUNCATED
 358   if (SHIFT_COUNT_TRUNCATED)
 359     count %= prec;
 360 #endif
 361
 362   if (count >= HOST_BITS_PER_WIDE_INT)
 363     {
 364       *hv = (unsigned HOST_WIDE_INT) l1 << (count - HOST_BITS_PER_WIDE_INT);
 365       *lv = 0;
 366     }
 367   else
 368     {
 369       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 370              | ((unsigned HOST_WIDE_INT) l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 371       *lv = (unsigned HOST_WIDE_INT) l1 << count;
 372     }
 373 }
 374
 375 /* Shift the doubleword integer in L1, H1 right by COUNT places
 376    keeping only PREC bits of result.  COUNT must be positive.
 377    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 378    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 379
 380 void
 381 rshift_double (l1, h1, count, prec, lv, hv, arith)
 382      HOST_WIDE_INT l1, h1, count;
 383      int prec ATTRIBUTE_UNUSED;
 384      HOST_WIDE_INT *lv, *hv;
 385      int arith;
 386 {
 387   unsigned HOST_WIDE_INT signmask;
 388   signmask = (arith
 389               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 390               : 0);
 391
 392 #ifdef SHIFT_COUNT_TRUNCATED
 393   if (SHIFT_COUNT_TRUNCATED)
 394     count %= prec;
 395 #endif
 396
 397   if (count >= HOST_BITS_PER_WIDE_INT)
 398     {
 399       *hv = signmask;
 400       *lv = ((signmask << (2 * HOST_BITS_PER_WIDE_INT - count - 1) << 1)
 401              | ((unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT)));
 402     }
 403   else
 404     {
 405       *lv = (((unsigned HOST_WIDE_INT) l1 >> count)
 406              | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 407       *hv = ((signmask << (HOST_BITS_PER_WIDE_INT - count))
 408              | ((unsigned HOST_WIDE_INT) h1 >> count));
 409     }
 410 }
 411 \f
 412 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 413    keeping only PREC bits of result.
 414    Rotate right if COUNT is negative.
 415    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 416
 417 void
 418 lrotate_double (l1, h1, count, prec, lv, hv)
 419      HOST_WIDE_INT l1, h1, count;
 420      int prec;
 421      HOST_WIDE_INT *lv, *hv;
 422 {
 423   HOST_WIDE_INT s1l, s1h, s2l, s2h;
 424
 425   count %= prec;
 426   if (count < 0)
 427     count += prec;
 428
 429   lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 430   rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 431   *lv = s1l | s2l;
 432   *hv = s1h | s2h;
 433 }
 434
 435 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 436    keeping only PREC bits of result.  COUNT must be positive.
 437    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 438
 439 void
 440 rrotate_double (l1, h1, count, prec, lv, hv)
 441      HOST_WIDE_INT l1, h1, count;
 442      int prec;
 443      HOST_WIDE_INT *lv, *hv;
 444 {
 445   HOST_WIDE_INT s1l, s1h, s2l, s2h;
 446
 447   count %= prec;
 448   if (count < 0)
 449     count += prec;
 450
 451   rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 452   lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 453   *lv = s1l | s2l;
 454   *hv = s1h | s2h;
 455 }
 456 \f
 457 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 458    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 459    CODE is a tree code for a kind of division, one of
 460    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 461    or EXACT_DIV_EXPR
 462    It controls how the quotient is rounded to a integer.
 463    Return nonzero if the operation overflows.
 464    UNS nonzero says do unsigned division.  */
 465
 466 int
 467 div_and_round_double (code, uns,
 468                       lnum_orig, hnum_orig, lden_orig, hden_orig,
 469                       lquo, hquo, lrem, hrem)
 470      enum tree_code code;
 471      int uns;
 472      HOST_WIDE_INT lnum_orig, hnum_orig; /* num == numerator == dividend */
 473      HOST_WIDE_INT lden_orig, hden_orig; /* den == denominator == divisor */
 474      HOST_WIDE_INT *lquo, *hquo, *lrem, *hrem;
 475 {
 476   int quo_neg = 0;
 477   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 478   HOST_WIDE_INT den[4], quo[4];
 479   register int i, j;
 480   unsigned HOST_WIDE_INT work;
 481   register unsigned HOST_WIDE_INT carry = 0;
 482   HOST_WIDE_INT lnum = lnum_orig;
 483   HOST_WIDE_INT hnum = hnum_orig;
 484   HOST_WIDE_INT lden = lden_orig;
 485   HOST_WIDE_INT hden = hden_orig;
 486   int overflow = 0;
 487
 488   if ((hden == 0) && (lden == 0))
 489     overflow = 1, lden = 1;
 490
 491   /* calculate quotient sign and convert operands to unsigned.  */
 492   if (!uns)
 493     {
 494       if (hnum < 0)
 495         {
 496           quo_neg = ~ quo_neg;
 497           /* (minimum integer) / (-1) is the only overflow case.  */
 498           if (neg_double (lnum, hnum, &lnum, &hnum) && (lden & hden) == -1)
 499             overflow = 1;
 500         }
 501       if (hden < 0)
 502         {
 503           quo_neg = ~ quo_neg;
 504           neg_double (lden, hden, &lden, &hden);
 505         }
 506     }
 507
 508   if (hnum == 0 && hden == 0)
 509     {                           /* single precision */
 510       *hquo = *hrem = 0;
 511       /* This unsigned division rounds toward zero.  */
 512       *lquo = lnum / (unsigned HOST_WIDE_INT) lden;
 513       goto finish_up;
 514     }
 515
 516   if (hnum == 0)
 517     {                           /* trivial case: dividend < divisor */
 518       /* hden != 0 already checked.  */
 519       *hquo = *lquo = 0;
 520       *hrem = hnum;
 521       *lrem = lnum;
 522       goto finish_up;
 523     }
 524
 525   bzero ((char *) quo, sizeof quo);
 526
 527   bzero ((char *) num, sizeof num);     /* to zero 9th element */
 528   bzero ((char *) den, sizeof den);
 529
 530   encode (num, lnum, hnum);
 531   encode (den, lden, hden);
 532
 533   /* Special code for when the divisor < BASE.  */
 534   if (hden == 0 && lden < (HOST_WIDE_INT) BASE)
 535     {
 536       /* hnum != 0 already checked.  */
 537       for (i = 4 - 1; i >= 0; i--)
 538         {
 539           work = num[i] + carry * BASE;
 540           quo[i] = work / (unsigned HOST_WIDE_INT) lden;
 541           carry = work % (unsigned HOST_WIDE_INT) lden;
 542         }
 543     }
 544   else
 545     {
 546       /* Full double precision division,
 547          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 548     int num_hi_sig, den_hi_sig;
 549     unsigned HOST_WIDE_INT quo_est, scale;
 550
 551     /* Find the highest non-zero divisor digit.  */
 552     for (i = 4 - 1; ; i--)
 553       if (den[i] != 0) {
 554         den_hi_sig = i;
 555         break;
 556       }
 557
 558     /* Insure that the first digit of the divisor is at least BASE/2.
 559        This is required by the quotient digit estimation algorithm.  */
 560
 561     scale = BASE / (den[den_hi_sig] + 1);
 562     if (scale > 1) {            /* scale divisor and dividend */
 563       carry = 0;
 564       for (i = 0; i <= 4 - 1; i++) {
 565         work = (num[i] * scale) + carry;
 566         num[i] = LOWPART (work);
 567         carry = HIGHPART (work);
 568       } num[4] = carry;
 569       carry = 0;
 570       for (i = 0; i <= 4 - 1; i++) {
 571         work = (den[i] * scale) + carry;
 572         den[i] = LOWPART (work);
 573         carry = HIGHPART (work);
 574         if (den[i] != 0) den_hi_sig = i;
 575       }
 576     }
 577
 578     num_hi_sig = 4;
 579
 580     /* Main loop */
 581     for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--) {
 582       /* guess the next quotient digit, quo_est, by dividing the first
 583          two remaining dividend digits by the high order quotient digit.
 584          quo_est is never low and is at most 2 high.  */
 585       unsigned HOST_WIDE_INT tmp;
 586
 587       num_hi_sig = i + den_hi_sig + 1;
 588       work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 589       if (num[num_hi_sig] != den[den_hi_sig])
 590         quo_est = work / den[den_hi_sig];
 591       else
 592         quo_est = BASE - 1;
 593
 594       /* refine quo_est so it's usually correct, and at most one high.   */
 595       tmp = work - quo_est * den[den_hi_sig];
 596       if (tmp < BASE
 597           && den[den_hi_sig - 1] * quo_est > (tmp * BASE + num[num_hi_sig - 2]))
 598         quo_est--;
 599
 600       /* Try QUO_EST as the quotient digit, by multiplying the
 601          divisor by QUO_EST and subtracting from the remaining dividend.
 602          Keep in mind that QUO_EST is the I - 1st digit.  */
 603
 604       carry = 0;
 605       for (j = 0; j <= den_hi_sig; j++)
 606         {
 607           work = quo_est * den[j] + carry;
 608           carry = HIGHPART (work);
 609           work = num[i + j] - LOWPART (work);
 610           num[i + j] = LOWPART (work);
 611           carry += HIGHPART (work) != 0;
 612         }
 613
 614       /* if quo_est was high by one, then num[i] went negative and
 615          we need to correct things.  */
 616
 617       if (num[num_hi_sig] < carry)
 618         {
 619           quo_est--;
 620           carry = 0;            /* add divisor back in */
 621           for (j = 0; j <= den_hi_sig; j++)
 622             {
 623               work = num[i + j] + den[j] + carry;
 624               carry = HIGHPART (work);
 625               num[i + j] = LOWPART (work);
 626             }
 627           num [num_hi_sig] += carry;
 628         }
 629
 630       /* store the quotient digit.  */
 631       quo[i] = quo_est;
 632     }
 633   }
 634
 635   decode (quo, lquo, hquo);
 636
 637  finish_up:
 638   /* if result is negative, make it so.  */
 639   if (quo_neg)
 640     neg_double (*lquo, *hquo, lquo, hquo);
 641
 642   /* compute trial remainder:  rem = num - (quo * den)  */
 643   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 644   neg_double (*lrem, *hrem, lrem, hrem);
 645   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 646
 647   switch (code)
 648     {
 649     case TRUNC_DIV_EXPR:
 650     case TRUNC_MOD_EXPR:        /* round toward zero */
 651     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 652       return overflow;
 653
 654     case FLOOR_DIV_EXPR:
 655     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 656       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 657         {
 658           /* quo = quo - 1;  */
 659           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 660                       lquo, hquo);
 661         }
 662       else return overflow;
 663       break;
 664
 665     case CEIL_DIV_EXPR:
 666     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 667       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 668         {
 669           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 670                       lquo, hquo);
 671         }
 672       else return overflow;
 673       break;
 674
 675     case ROUND_DIV_EXPR:
 676     case ROUND_MOD_EXPR:        /* round to closest integer */
 677       {
 678         HOST_WIDE_INT labs_rem = *lrem, habs_rem = *hrem;
 679         HOST_WIDE_INT labs_den = lden, habs_den = hden, ltwice, htwice;
 680
 681         /* get absolute values */
 682         if (*hrem < 0) neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 683         if (hden < 0) neg_double (lden, hden, &labs_den, &habs_den);
 684
 685         /* if (2 * abs (lrem) >= abs (lden)) */
 686         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 687                     labs_rem, habs_rem, &ltwice, &htwice);
 688         if (((unsigned HOST_WIDE_INT) habs_den
 689              < (unsigned HOST_WIDE_INT) htwice)
 690             || (((unsigned HOST_WIDE_INT) habs_den
 691                  == (unsigned HOST_WIDE_INT) htwice)
 692                 && ((HOST_WIDE_INT unsigned) labs_den
 693                     < (unsigned HOST_WIDE_INT) ltwice)))
 694           {
 695             if (*hquo < 0)
 696               /* quo = quo - 1;  */
 697               add_double (*lquo, *hquo,
 698                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 699             else
 700               /* quo = quo + 1; */
 701               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 702                           lquo, hquo);
 703           }
 704         else return overflow;
 705       }
 706       break;
 707
 708     default:
 709       abort ();
 710     }
 711
 712   /* compute true remainder:  rem = num - (quo * den)  */
 713   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 714   neg_double (*lrem, *hrem, lrem, hrem);
 715   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 716   return overflow;
 717 }
 718 \f
 719 #ifndef REAL_ARITHMETIC
 720 /* Effectively truncate a real value to represent the nearest possible value
 721    in a narrower mode.  The result is actually represented in the same data
 722    type as the argument, but its value is usually different.
 723
 724    A trap may occur during the FP operations and it is the responsibility
 725    of the calling function to have a handler established.  */
 726
 727 REAL_VALUE_TYPE
 728 real_value_truncate (mode, arg)
 729      enum machine_mode mode;
 730      REAL_VALUE_TYPE arg;
 731 {
 732   return REAL_VALUE_TRUNCATE (mode, arg);
 733 }
 734
 735 #if TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
 736
 737 /* Check for infinity in an IEEE double precision number.  */
 738
 739 int
 740 target_isinf (x)
 741      REAL_VALUE_TYPE x;
 742 {
 743   /* The IEEE 64-bit double format.  */
 744   union {
 745     REAL_VALUE_TYPE d;
 746     struct {
 747       unsigned sign      :  1;
 748       unsigned exponent  : 11;
 749       unsigned mantissa1 : 20;
 750       unsigned mantissa2;
 751     } little_endian;
 752     struct {
 753       unsigned mantissa2;
 754       unsigned mantissa1 : 20;
 755       unsigned exponent  : 11;
 756       unsigned sign      :  1;
 757     } big_endian;
 758   } u;
 759
 760   u.d = dconstm1;
 761   if (u.big_endian.sign == 1)
 762     {
 763       u.d = x;
 764       return (u.big_endian.exponent == 2047
 765               && u.big_endian.mantissa1 == 0
 766               && u.big_endian.mantissa2 == 0);
 767     }
 768   else
 769     {
 770       u.d = x;
 771       return (u.little_endian.exponent == 2047
 772               && u.little_endian.mantissa1 == 0
 773               && u.little_endian.mantissa2 == 0);
 774     }
 775 }
 776
 777 /* Check whether an IEEE double precision number is a NaN.  */
 778
 779 int
 780 target_isnan (x)
 781      REAL_VALUE_TYPE x;
 782 {
 783   /* The IEEE 64-bit double format.  */
 784   union {
 785     REAL_VALUE_TYPE d;
 786     struct {
 787       unsigned sign      :  1;
 788       unsigned exponent  : 11;
 789       unsigned mantissa1 : 20;
 790       unsigned mantissa2;
 791     } little_endian;
 792     struct {
 793       unsigned mantissa2;
 794       unsigned mantissa1 : 20;
 795       unsigned exponent  : 11;
 796       unsigned sign      :  1;
 797     } big_endian;
 798   } u;
 799
 800   u.d = dconstm1;
 801   if (u.big_endian.sign == 1)
 802     {
 803       u.d = x;
 804       return (u.big_endian.exponent == 2047
 805               && (u.big_endian.mantissa1 != 0
 806                   || u.big_endian.mantissa2 != 0));
 807     }
 808   else
 809     {
 810       u.d = x;
 811       return (u.little_endian.exponent == 2047
 812               && (u.little_endian.mantissa1 != 0
 813                   || u.little_endian.mantissa2 != 0));
 814     }
 815 }
 816
 817 /* Check for a negative IEEE double precision number.  */
 818
 819 int
 820 target_negative (x)
 821      REAL_VALUE_TYPE x;
 822 {
 823   /* The IEEE 64-bit double format.  */
 824   union {
 825     REAL_VALUE_TYPE d;
 826     struct {
 827       unsigned sign      :  1;
 828       unsigned exponent  : 11;
 829       unsigned mantissa1 : 20;
 830       unsigned mantissa2;
 831     } little_endian;
 832     struct {
 833       unsigned mantissa2;
 834       unsigned mantissa1 : 20;
 835       unsigned exponent  : 11;
 836       unsigned sign      :  1;
 837     } big_endian;
 838   } u;
 839
 840   u.d = dconstm1;
 841   if (u.big_endian.sign == 1)
 842     {
 843       u.d = x;
 844       return u.big_endian.sign;
 845     }
 846   else
 847     {
 848       u.d = x;
 849       return u.little_endian.sign;
 850     }
 851 }
 852 #else /* Target not IEEE */
 853
 854 /* Let's assume other float formats don't have infinity.
 855    (This can be overridden by redefining REAL_VALUE_ISINF.)  */
 856
 857 target_isinf (x)
 858      REAL_VALUE_TYPE x;
 859 {
 860   return 0;
 861 }
 862
 863 /* Let's assume other float formats don't have NaNs.
 864    (This can be overridden by redefining REAL_VALUE_ISNAN.)  */
 865
 866 target_isnan (x)
 867      REAL_VALUE_TYPE x;
 868 {
 869   return 0;
 870 }
 871
 872 /* Let's assume other float formats don't have minus zero.
 873    (This can be overridden by redefining REAL_VALUE_NEGATIVE.)  */
 874
 875 target_negative (x)
 876      REAL_VALUE_TYPE x;
 877 {
 878   return x < 0;
 879 }
 880 #endif /* Target not IEEE */
 881
 882 /* Try to change R into its exact multiplicative inverse in machine mode
 883    MODE.  Return nonzero function value if successful.  */
 884
 885 int
 886 exact_real_inverse (mode, r)
 887      enum machine_mode mode;
 888      REAL_VALUE_TYPE *r;
 889 {
 890   jmp_buf float_error;
 891   union
 892     {
 893       double d;
 894       unsigned short i[4];
 895     }x, t, y;
 896   int i;
 897
 898   /* Usually disable if bounds checks are not reliable.  */
 899   if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT) && !flag_pretend_float)
 900     return 0;
 901
 902   /* Set array index to the less significant bits in the unions, depending
 903      on the endian-ness of the host doubles.
 904      Disable if insufficient information on the data structure.  */
 905 #if HOST_FLOAT_FORMAT == UNKNOWN_FLOAT_FORMAT
 906   return 0;
 907 #else
 908 #if HOST_FLOAT_FORMAT == VAX_FLOAT_FORMAT
 909 #define K 2
 910 #else
 911 #if HOST_FLOAT_FORMAT == IBM_FLOAT_FORMAT
 912 #define K 2
 913 #else
 914 #define K (2 * HOST_FLOAT_WORDS_BIG_ENDIAN)
 915 #endif
 916 #endif
 917 #endif
 918
 919   if (setjmp (float_error))
 920     {
 921       /* Don't do the optimization if there was an arithmetic error.  */
 922 fail:
 923       set_float_handler (NULL_PTR);
 924       return 0;
 925     }
 926   set_float_handler (float_error);
 927
 928   /* Domain check the argument.  */
 929   x.d = *r;
 930   if (x.d == 0.0)
 931     goto fail;
 932
 933 #ifdef REAL_INFINITY
 934   if (REAL_VALUE_ISINF (x.d) || REAL_VALUE_ISNAN (x.d))
 935     goto fail;
 936 #endif
 937
 938   /* Compute the reciprocal and check for numerical exactness.
 939      It is unnecessary to check all the significand bits to determine
 940      whether X is a power of 2.  If X is not, then it is impossible for
 941      the bottom half significand of both X and 1/X to be all zero bits.
 942      Hence we ignore the data structure of the top half and examine only
 943      the low order bits of the two significands.  */
 944   t.d = 1.0 / x.d;
 945   if (x.i[K] != 0 || x.i[K + 1] != 0 || t.i[K] != 0 || t.i[K + 1] != 0)
 946     goto fail;
 947
 948   /* Truncate to the required mode and range-check the result.  */
 949   y.d = REAL_VALUE_TRUNCATE (mode, t.d);
 950 #ifdef CHECK_FLOAT_VALUE
 951   i = 0;
 952   if (CHECK_FLOAT_VALUE (mode, y.d, i))
 953     goto fail;
 954 #endif
 955
 956   /* Fail if truncation changed the value.  */
 957   if (y.d != t.d || y.d == 0.0)
 958     goto fail;
 959
 960 #ifdef REAL_INFINITY
 961   if (REAL_VALUE_ISINF (y.d) || REAL_VALUE_ISNAN (y.d))
 962     goto fail;
 963 #endif
 964
 965   /* Output the reciprocal and return success flag.  */
 966   set_float_handler (NULL_PTR);
 967   *r = y.d;
 968   return 1;
 969 }
 970
 971
 972 /* Convert C9X hexadecimal floating point string constant S.  Return
 973    real value type in mode MODE.  This function uses the host computer's
 974    fp arithmetic when there is no REAL_ARITHMETIC.  */
 975
 976 REAL_VALUE_TYPE
 977 real_hex_to_f (s, mode)
 978    char *s;
 979    enum machine_mode mode;
 980 {
 981    REAL_VALUE_TYPE ip;
 982    char *p = s;
 983    unsigned HOST_WIDE_INT low, high;
 984    int frexpon, expon, shcount, nrmcount, k;
 985    int sign, expsign, decpt, isfloat, isldouble, gotp, lost;
 986    char c;
 987
 988    isldouble = 0;
 989    isfloat = 0;
 990    frexpon = 0;
 991    expon = 0;
 992    expsign = 1;
 993    ip = 0.0;
 994
 995    while (*p == ' ' || *p == '\t')
 996      ++p;
 997
 998    /* Sign, if any, comes first.  */
 999    sign = 1;
1000    if (*p == '-')
1001      {
1002        sign = -1;
1003        ++p;
1004      }
1005
1006    /* The string is supposed to start with 0x or 0X .  */
1007    if (*p == '0')
1008      {
1009        ++p;
1010        if (*p == 'x' || *p == 'X')
1011          ++p;
1012        else
1013          abort ();
1014      }
1015    else
1016      abort ();
1017
1018    while (*p == '0')
1019      ++p;
1020
1021    high = 0;
1022    low = 0;
1023    lost = 0; /* Nonzero low order bits shifted out and discarded.  */
1024    frexpon = 0;  /* Bits after the decimal point.  */
1025    expon = 0;  /* Value of exponent.  */
1026    decpt = 0;  /* How many decimal points.  */
1027    gotp = 0;  /* How many P's.  */
1028    shcount = 0;
1029    while ((c = *p) != '\0')
1030      {
1031        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F')
1032            || (c >= 'a' && c <= 'f'))
1033          {
1034            k = c & 0x7f;
1035            if (k >= 'a')
1036              k = k - 'a' + 10;
1037            else if (k >= 'A')
1038              k = k - 'A' + 10;
1039            else
1040              k = k - '0';
1041
1042            if ((high & 0xf0000000) == 0)
1043              {
1044                high = (high << 4) + ((low >> 28) & 15);
1045                low = (low << 4) + k;
1046                shcount += 4;
1047                if (decpt)
1048                  frexpon += 4;
1049              }
1050            else
1051              {
1052                /* Record nonzero lost bits.  */
1053                lost |= k;
1054                if (!decpt)
1055                  frexpon -= 4;
1056              }
1057            ++p;
1058          }
1059        else if ( c == '.')
1060          {
1061            ++decpt;
1062            ++p;
1063          }
1064        else if (c == 'p' || c == 'P')
1065          {
1066            ++gotp;
1067            ++p;
1068            /* Sign of exponent.  */
1069            if (*p == '-')
1070              {
1071                expsign = -1;
1072                ++p;
1073              }
1074            /* Value of exponent.
1075               The exponent field is a decimal integer.  */
1076            while (ISDIGIT(*p))
1077              {
1078                k = (*p++ & 0x7f) - '0';
1079                expon = 10 * expon + k;
1080              }
1081            expon *= expsign;
1082            /* F suffix is ambiguous in the significand part
1083               so it must appear after the decimal exponent field.  */
1084            if (*p == 'f' || *p == 'F')
1085              {
1086                isfloat = 1;
1087                ++p;
1088                break;
1089              }
1090          }
1091        else if (c == 'l' || c == 'L')
1092          {
1093            isldouble = 1;
1094            ++p;
1095            break;
1096          }
1097        else
1098          break;
1099      }
1100    /* Abort if last character read was not legitimate.  */
1101    c = *p;
1102    if ((c != '\0' && c != ' ' && c != '\n' && c != '\r') || (decpt > 1))
1103      abort ();
1104    /* There must be either one decimal point or one p.  */
1105    if (decpt == 0 && gotp == 0)
1106      abort ();
1107    shcount -= 4;
1108    if ((high == 0) && (low == 0))
1109      {
1110        return dconst0;
1111      }
1112
1113    /* Normalize.  */
1114    nrmcount = 0;
1115    if (high == 0)
1116      {
1117        high = low;
1118        low = 0;
1119        nrmcount += 32;
1120      }
1121    /* Leave a high guard bit for carry-out.  */
1122    if ((high & 0x80000000) != 0)
1123      {
1124        lost |= low & 1;
1125        low = (low >> 1) | (high << 31);
1126        high = high >> 1;
1127        nrmcount -= 1;
1128      }
1129    if ((high & 0xffff8000) == 0)
1130      {
1131        high = (high << 16) + ((low >> 16) & 0xffff);
1132        low = low << 16;
1133        nrmcount += 16;
1134      }
1135    while ((high & 0xc0000000) == 0)
1136      {
1137        high = (high << 1) + ((low >> 31) & 1);
1138        low = low << 1;
1139        nrmcount += 1;
1140      }
1141    if (isfloat || GET_MODE_SIZE(mode) == UNITS_PER_WORD)
1142      {
1143        /* Keep 24 bits precision, bits 0x7fffff80.
1144           Rounding bit is 0x40.  */
1145        lost = lost | low | (high & 0x3f);
1146        low = 0;
1147        if (high & 0x40)
1148          {
1149            if ((high & 0x80) || lost)
1150              high += 0x40;
1151          }
1152        high &= 0xffffff80;
1153      }
1154    else
1155      {
1156        /* We need real.c to do long double formats, so here default
1157           to double precision.  */
1158 #if HOST_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
1159        /* IEEE double.
1160           Keep 53 bits precision, bits 0x7fffffff fffffc00.
1161           Rounding bit is low word 0x200.  */
1162        lost = lost | (low & 0x1ff);
1163        if (low & 0x200)
1164          {
1165            if ((low & 0x400) || lost)
1166              {
1167                low = (low + 0x200) & 0xfffffc00;
1168                if (low == 0)
1169                  high += 1;
1170              }
1171          }
1172        low &= 0xfffffc00;
1173 #else
1174        /* Assume it's a VAX with 56-bit significand,
1175           bits 0x7fffffff ffffff80.  */
1176        lost = lost | (low & 0x7f);
1177        if (low & 0x40)
1178          {
1179            if ((low & 0x80) || lost)
1180              {
1181                low = (low + 0x40) & 0xffffff80;
1182                if (low == 0)
1183                  high += 1;
1184              }
1185          }
1186        low &= 0xffffff80;
1187 #endif
1188      }
1189    ip = (double) high;
1190    ip =  REAL_VALUE_LDEXP (ip, 32) + (double) low;
1191    /* Apply shifts and exponent value as power of 2.  */
1192    ip = REAL_VALUE_LDEXP (ip, expon - (nrmcount + frexpon));
1193
1194    if (sign < 0)
1195      ip = -ip;
1196    return ip;
1197 }
1198
1199 #endif /* no REAL_ARITHMETIC */
1200 \f
1201 /* Split a tree IN into a constant and a variable part
1202    that could be combined with CODE to make IN.
1203    CODE must be a commutative arithmetic operation.
1204    Store the constant part into *CONP and the variable in &VARP.
1205    Return 1 if this was done; zero means the tree IN did not decompose
1206    this way.
1207
1208    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.
1209    Therefore, we must tell the caller whether the variable part
1210    was subtracted.  We do this by storing 1 or -1 into *VARSIGNP.
1211    The value stored is the coefficient for the variable term.
1212    The constant term we return should always be added;
1213    we negate it if necessary.  */
1214
1215 static int
1216 split_tree (in, code, varp, conp, varsignp)
1217      tree in;
1218      enum tree_code code;
1219      tree *varp, *conp;
1220      int *varsignp;
1221 {
1222   register tree outtype = TREE_TYPE (in);
1223   *varp = 0;
1224   *conp = 0;
1225
1226   /* Strip any conversions that don't change the machine mode.  */
1227   while ((TREE_CODE (in) == NOP_EXPR
1228           || TREE_CODE (in) == CONVERT_EXPR)
1229          && (TYPE_MODE (TREE_TYPE (in))
1230              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (in, 0)))))
1231     in = TREE_OPERAND (in, 0);
1232
1233   if (TREE_CODE (in) == code
1234       || (! FLOAT_TYPE_P (TREE_TYPE (in))
1235           /* We can associate addition and subtraction together
1236              (even though the C standard doesn't say so)
1237              for integers because the value is not affected.
1238              For reals, the value might be affected, so we can't.  */
1239           && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
1240               || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
1241     {
1242       enum tree_code code = TREE_CODE (TREE_OPERAND (in, 0));
1243       if (code == INTEGER_CST)
1244         {
1245           *conp = TREE_OPERAND (in, 0);
1246           *varp = TREE_OPERAND (in, 1);
1247           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1248               && TREE_TYPE (*varp) != outtype)
1249             *varp = convert (outtype, *varp);
1250           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1251           return 1;
1252         }
1253       if (TREE_CONSTANT (TREE_OPERAND (in, 1)))
1254         {
1255           *conp = TREE_OPERAND (in, 1);
1256           *varp = TREE_OPERAND (in, 0);
1257           *varsignp = 1;
1258           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1259               && TREE_TYPE (*varp) != outtype)
1260             *varp = convert (outtype, *varp);
1261           if (TREE_CODE (in) == MINUS_EXPR)
1262             {
1263               /* If operation is subtraction and constant is second,
1264                  must negate it to get an additive constant.
1265                  And this cannot be done unless it is a manifest constant.
1266                  It could also be the address of a static variable.
1267                  We cannot negate that, so give up.  */
1268               if (TREE_CODE (*conp) == INTEGER_CST)
1269                 /* Subtracting from integer_zero_node loses for long long.  */
1270                 *conp = fold (build1 (NEGATE_EXPR, TREE_TYPE (*conp), *conp));
1271               else
1272                 return 0;
1273             }
1274           return 1;
1275         }
1276       if (TREE_CONSTANT (TREE_OPERAND (in, 0)))
1277         {
1278           *conp = TREE_OPERAND (in, 0);
1279           *varp = TREE_OPERAND (in, 1);
1280           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1281               && TREE_TYPE (*varp) != outtype)
1282             *varp = convert (outtype, *varp);
1283           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1284           return 1;
1285         }
1286     }
1287   return 0;
1288 }
1289 \f
1290 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1291    to produce a new constant.
1292
1293    If NOTRUNC is nonzero, do not truncate the result to fit the data type.
1294    If FORSIZE is nonzero, compute overflow for unsigned types.  */
1295
1296 static tree
1297 int_const_binop (code, arg1, arg2, notrunc, forsize)
1298      enum tree_code code;
1299      register tree arg1, arg2;
1300      int notrunc, forsize;
1301 {
1302   HOST_WIDE_INT int1l, int1h, int2l, int2h;
1303   HOST_WIDE_INT low, hi;
1304   HOST_WIDE_INT garbagel, garbageh;
1305   register tree t;
1306   int uns = TREE_UNSIGNED (TREE_TYPE (arg1));
1307   int overflow = 0;
1308   int no_overflow = 0;
1309
1310   int1l = TREE_INT_CST_LOW (arg1);
1311   int1h = TREE_INT_CST_HIGH (arg1);
1312   int2l = TREE_INT_CST_LOW (arg2);
1313   int2h = TREE_INT_CST_HIGH (arg2);
1314
1315   switch (code)
1316     {
1317     case BIT_IOR_EXPR:
1318       low = int1l | int2l, hi = int1h | int2h;
1319       break;
1320
1321     case BIT_XOR_EXPR:
1322       low = int1l ^ int2l, hi = int1h ^ int2h;
1323       break;
1324
1325     case BIT_AND_EXPR:
1326       low = int1l & int2l, hi = int1h & int2h;
1327       break;
1328
1329     case BIT_ANDTC_EXPR:
1330       low = int1l & ~int2l, hi = int1h & ~int2h;
1331       break;
1332
1333     case RSHIFT_EXPR:
1334       int2l = - int2l;
1335     case LSHIFT_EXPR:
1336       /* It's unclear from the C standard whether shifts can overflow.
1337          The following code ignores overflow; perhaps a C standard
1338          interpretation ruling is needed.  */
1339       lshift_double (int1l, int1h, int2l,
1340                      TYPE_PRECISION (TREE_TYPE (arg1)),
1341                      &low, &hi,
1342                      !uns);
1343       no_overflow = 1;
1344       break;
1345
1346     case RROTATE_EXPR:
1347       int2l = - int2l;
1348     case LROTATE_EXPR:
1349       lrotate_double (int1l, int1h, int2l,
1350                       TYPE_PRECISION (TREE_TYPE (arg1)),
1351                       &low, &hi);
1352       break;
1353
1354     case PLUS_EXPR:
1355       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1356       break;
1357
1358     case MINUS_EXPR:
1359       neg_double (int2l, int2h, &low, &hi);
1360       add_double (int1l, int1h, low, hi, &low, &hi);
1361       overflow = overflow_sum_sign (hi, int2h, int1h);
1362       break;
1363
1364     case MULT_EXPR:
1365       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1366       break;
1367
1368     case TRUNC_DIV_EXPR:
1369     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1370     case EXACT_DIV_EXPR:
1371       /* This is a shortcut for a common special case.  */
1372       if (int2h == 0 && int2l > 0
1373           && ! TREE_CONSTANT_OVERFLOW (arg1)
1374           && ! TREE_CONSTANT_OVERFLOW (arg2)
1375           && int1h == 0 && int1l >= 0)
1376         {
1377           if (code == CEIL_DIV_EXPR)
1378             int1l += int2l - 1;
1379           low = int1l / int2l, hi = 0;
1380           break;
1381         }
1382
1383       /* ... fall through ... */
1384
1385     case ROUND_DIV_EXPR:
1386       if (int2h == 0 && int2l == 1)
1387         {
1388           low = int1l, hi = int1h;
1389           break;
1390         }
1391       if (int1l == int2l && int1h == int2h
1392           && ! (int1l == 0 && int1h == 0))
1393         {
1394           low = 1, hi = 0;
1395           break;
1396         }
1397       overflow = div_and_round_double (code, uns,
1398                                        int1l, int1h, int2l, int2h,
1399                                        &low, &hi, &garbagel, &garbageh);
1400       break;
1401
1402     case TRUNC_MOD_EXPR:
1403     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1404       /* This is a shortcut for a common special case.  */
1405       if (int2h == 0 && int2l > 0
1406           && ! TREE_CONSTANT_OVERFLOW (arg1)
1407           && ! TREE_CONSTANT_OVERFLOW (arg2)
1408           && int1h == 0 && int1l >= 0)
1409         {
1410           if (code == CEIL_MOD_EXPR)
1411             int1l += int2l - 1;
1412           low = int1l % int2l, hi = 0;
1413           break;
1414         }
1415
1416       /* ... fall through ... */
1417
1418     case ROUND_MOD_EXPR:
1419       overflow = div_and_round_double (code, uns,
1420                                        int1l, int1h, int2l, int2h,
1421                                        &garbagel, &garbageh, &low, &hi);
1422       break;
1423
1424     case MIN_EXPR:
1425     case MAX_EXPR:
1426       if (uns)
1427         {
1428           low = (((unsigned HOST_WIDE_INT) int1h
1429                   < (unsigned HOST_WIDE_INT) int2h)
1430                  || (((unsigned HOST_WIDE_INT) int1h
1431                       == (unsigned HOST_WIDE_INT) int2h)
1432                      && ((unsigned HOST_WIDE_INT) int1l
1433                          < (unsigned HOST_WIDE_INT) int2l)));
1434         }
1435       else
1436         {
1437           low = ((int1h < int2h)
1438                  || ((int1h == int2h)
1439                      && ((unsigned HOST_WIDE_INT) int1l
1440                          < (unsigned HOST_WIDE_INT) int2l)));
1441         }
1442       if (low == (code == MIN_EXPR))
1443         low = int1l, hi = int1h;
1444       else
1445         low = int2l, hi = int2h;
1446       break;
1447
1448     default:
1449       abort ();
1450     }
1451
1452   if (TREE_TYPE (arg1) == sizetype && hi == 0
1453       && low >= 0
1454       && (TYPE_MAX_VALUE (sizetype) == NULL
1455           || low <= TREE_INT_CST_LOW (TYPE_MAX_VALUE (sizetype)))
1456       && ! overflow
1457       && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1458     t = size_int (low);
1459   else
1460     {
1461       t = build_int_2 (low, hi);
1462       TREE_TYPE (t) = TREE_TYPE (arg1);
1463     }
1464
1465   TREE_OVERFLOW (t)
1466     = ((notrunc ? (!uns || forsize) && overflow
1467         : force_fit_type (t, (!uns || forsize) && overflow) && ! no_overflow)
1468        | TREE_OVERFLOW (arg1)
1469        | TREE_OVERFLOW (arg2));
1470   /* If we're doing a size calculation, unsigned arithmetic does overflow.
1471      So check if force_fit_type truncated the value.  */
1472   if (forsize
1473       && ! TREE_OVERFLOW (t)
1474       && (TREE_INT_CST_HIGH (t) != hi
1475           || TREE_INT_CST_LOW (t) != low))
1476     TREE_OVERFLOW (t) = 1;
1477   TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1478                                 | TREE_CONSTANT_OVERFLOW (arg1)
1479                                 | TREE_CONSTANT_OVERFLOW (arg2));
1480   return t;
1481 }
1482
1483 struct cb_args
1484 {
1485   /* Input */
1486   tree arg1;
1487   REAL_VALUE_TYPE d1, d2;
1488   enum tree_code code;
1489   /* Output */
1490   tree t;
1491 };
1492
1493 static void
1494 const_binop_1 (data)
1495   PTR data;
1496 {
1497   struct cb_args * args = (struct cb_args *) data;
1498   REAL_VALUE_TYPE value;
1499
1500 #ifdef REAL_ARITHMETIC
1501   REAL_ARITHMETIC (value, args->code, args->d1, args->d2);
1502 #else
1503   switch (args->code)
1504     {
1505     case PLUS_EXPR:
1506       value = args->d1 + args->d2;
1507       break;
1508
1509     case MINUS_EXPR:
1510       value = args->d1 - args->d2;
1511       break;
1512
1513     case MULT_EXPR:
1514       value = args->d1 * args->d2;
1515       break;
1516
1517     case RDIV_EXPR:
1518 #ifndef REAL_INFINITY
1519       if (args->d2 == 0)
1520         abort ();
1521 #endif
1522
1523       value = args->d1 / args->d2;
1524       break;
1525
1526     case MIN_EXPR:
1527       value = MIN (args->d1, args->d2);
1528       break;
1529
1530     case MAX_EXPR:
1531       value = MAX (args->d1, args->d2);
1532       break;
1533
1534     default:
1535       abort ();
1536     }
1537 #endif /* no REAL_ARITHMETIC */
1538   args->t =
1539     build_real (TREE_TYPE (args->arg1),
1540                 real_value_truncate (TYPE_MODE (TREE_TYPE (args->arg1)),
1541                                      value));
1542 }
1543
1544 /* Combine two constants ARG1 and ARG2 under operation CODE
1545    to produce a new constant.
1546    We assume ARG1 and ARG2 have the same data type,
1547    or at least are the same kind of constant and the same machine mode.
1548
1549    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1550
1551 static tree
1552 const_binop (code, arg1, arg2, notrunc)
1553      enum tree_code code;
1554      register tree arg1, arg2;
1555      int notrunc;
1556 {
1557   STRIP_NOPS (arg1); STRIP_NOPS (arg2);
1558
1559   if (TREE_CODE (arg1) == INTEGER_CST)
1560     return int_const_binop (code, arg1, arg2, notrunc, 0);
1561
1562 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1563   if (TREE_CODE (arg1) == REAL_CST)
1564     {
1565       REAL_VALUE_TYPE d1;
1566       REAL_VALUE_TYPE d2;
1567       int overflow = 0;
1568       tree t;
1569       struct cb_args args;
1570
1571       d1 = TREE_REAL_CST (arg1);
1572       d2 = TREE_REAL_CST (arg2);
1573
1574       /* If either operand is a NaN, just return it.  Otherwise, set up
1575          for floating-point trap; we return an overflow.  */
1576       if (REAL_VALUE_ISNAN (d1))
1577         return arg1;
1578       else if (REAL_VALUE_ISNAN (d2))
1579         return arg2;
1580
1581       /* Setup input for const_binop_1() */
1582       args.arg1 = arg1;
1583       args.d1 = d1;
1584       args.d2 = d2;
1585       args.code = code;
1586
1587       if (do_float_handler (const_binop_1, (PTR) &args))
1588         {
1589           /* Receive output from const_binop_1() */
1590           t = args.t;
1591         }
1592       else
1593         {
1594           /* We got an exception from const_binop_1() */
1595           t = copy_node (arg1);
1596           overflow = 1;
1597         }
1598
1599       TREE_OVERFLOW (t)
1600         = (force_fit_type (t, overflow)
1601            | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1602       TREE_CONSTANT_OVERFLOW (t)
1603         = TREE_OVERFLOW (t)
1604           | TREE_CONSTANT_OVERFLOW (arg1)
1605           | TREE_CONSTANT_OVERFLOW (arg2);
1606       return t;
1607     }
1608 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1609   if (TREE_CODE (arg1) == COMPLEX_CST)
1610     {
1611       register tree type = TREE_TYPE (arg1);
1612       register tree r1 = TREE_REALPART (arg1);
1613       register tree i1 = TREE_IMAGPART (arg1);
1614       register tree r2 = TREE_REALPART (arg2);
1615       register tree i2 = TREE_IMAGPART (arg2);
1616       register tree t;
1617
1618       switch (code)
1619         {
1620         case PLUS_EXPR:
1621           t = build_complex (type,
1622                              const_binop (PLUS_EXPR, r1, r2, notrunc),
1623                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1624           break;
1625
1626         case MINUS_EXPR:
1627           t = build_complex (type,
1628                              const_binop (MINUS_EXPR, r1, r2, notrunc),
1629                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1630           break;
1631
1632         case MULT_EXPR:
1633           t = build_complex (type,
1634                              const_binop (MINUS_EXPR,
1635                                           const_binop (MULT_EXPR,
1636                                                        r1, r2, notrunc),
1637                                           const_binop (MULT_EXPR,
1638                                                        i1, i2, notrunc),
1639                                           notrunc),
1640                              const_binop (PLUS_EXPR,
1641                                           const_binop (MULT_EXPR,
1642                                                        r1, i2, notrunc),
1643                                           const_binop (MULT_EXPR,
1644                                                        i1, r2, notrunc),
1645                                           notrunc));
1646           break;
1647
1648         case RDIV_EXPR:
1649           {
1650             register tree magsquared
1651               = const_binop (PLUS_EXPR,
1652                              const_binop (MULT_EXPR, r2, r2, notrunc),
1653                              const_binop (MULT_EXPR, i2, i2, notrunc),
1654                              notrunc);
1655
1656             t = build_complex (type,
1657                                const_binop
1658                                (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1659                                 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1660                                 const_binop (PLUS_EXPR,
1661                                              const_binop (MULT_EXPR, r1, r2,
1662                                                           notrunc),
1663                                              const_binop (MULT_EXPR, i1, i2,
1664                                                           notrunc),
1665                                              notrunc),
1666                                 magsquared, notrunc),
1667                                const_binop
1668                                (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1669                                 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1670                                 const_binop (MINUS_EXPR,
1671                                              const_binop (MULT_EXPR, i1, r2,
1672                                                           notrunc),
1673                                              const_binop (MULT_EXPR, r1, i2,
1674                                                           notrunc),
1675                                              notrunc),
1676                                 magsquared, notrunc));
1677           }
1678           break;
1679
1680         default:
1681           abort ();
1682         }
1683       return t;
1684     }
1685   return 0;
1686 }
1687 \f
1688 /* Return an INTEGER_CST with value V .  The type is determined by bit_p:
1689    if it is zero, the type is taken from sizetype; if it is one, the type
1690    is taken from bitsizetype.  */
1691
1692 tree
1693 size_int_wide (number, high, bit_p)
1694      unsigned HOST_WIDE_INT number, high;
1695      int bit_p;
1696 {
1697   tree t;
1698
1699   if (!ggc_p)
1700     {
1701       /* Type-size nodes already made for small sizes.  */
1702       static tree size_table[2*HOST_BITS_PER_WIDE_INT + 1][2];
1703
1704       if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high
1705           && size_table[number][bit_p] != 0)
1706         return size_table[number][bit_p];
1707       if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high)
1708         {
1709           push_obstacks_nochange ();
1710           /* Make this a permanent node.  */
1711           end_temporary_allocation ();
1712           t = build_int_2 (number, 0);
1713           TREE_TYPE (t) = bit_p ? bitsizetype : sizetype;
1714           size_table[number][bit_p] = t;
1715           pop_obstacks ();
1716           return t;
1717         }
1718     }
1719
1720   t = build_int_2 (number, high);
1721   TREE_TYPE (t) = bit_p ? bitsizetype : sizetype;
1722   TREE_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (t) = force_fit_type (t, 0);
1723   return t;
1724 }
1725
1726 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1727    CODE is a tree code.  Data type is taken from `sizetype',
1728    If the operands are constant, so is the result.  */
1729
1730 tree
1731 size_binop (code, arg0, arg1)
1732      enum tree_code code;
1733      tree arg0, arg1;
1734 {
1735   /* Handle the special case of two integer constants faster.  */
1736   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1737     {
1738       /* And some specific cases even faster than that.  */
1739       if (code == PLUS_EXPR && integer_zerop (arg0))
1740         return arg1;
1741       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1742                && integer_zerop (arg1))
1743         return arg0;
1744       else if (code == MULT_EXPR && integer_onep (arg0))
1745         return arg1;
1746
1747       /* Handle general case of two integer constants.  */
1748       return int_const_binop (code, arg0, arg1, 0, 1);
1749     }
1750
1751   if (arg0 == error_mark_node || arg1 == error_mark_node)
1752     return error_mark_node;
1753
1754   return fold (build (code, sizetype, arg0, arg1));
1755 }
1756
1757 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1758    CODE is a tree code.  Data type is taken from `ssizetype',
1759    If the operands are constant, so is the result.  */
1760
1761 tree
1762 ssize_binop (code, arg0, arg1)
1763      enum tree_code code;
1764      tree arg0, arg1;
1765 {
1766   /* Handle the special case of two integer constants faster.  */
1767   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1768     {
1769       /* And some specific cases even faster than that.  */
1770       if (code == PLUS_EXPR && integer_zerop (arg0))
1771         return arg1;
1772       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1773                && integer_zerop (arg1))
1774         return arg0;
1775       else if (code == MULT_EXPR && integer_onep (arg0))
1776         return arg1;
1777
1778       /* Handle general case of two integer constants.  We convert
1779          arg0 to ssizetype because int_const_binop uses its type for the
1780          return value.  */
1781       arg0 = convert (ssizetype, arg0);
1782       return int_const_binop (code, arg0, arg1, 0, 0);
1783     }
1784
1785   if (arg0 == error_mark_node || arg1 == error_mark_node)
1786     return error_mark_node;
1787
1788   return fold (build (code, ssizetype, arg0, arg1));
1789 }
1790 \f
1791 struct fc_args
1792 {
1793   /* Input */
1794   tree arg1, type;
1795   /* Output */
1796   tree t;
1797 };
1798
1799 static void
1800 fold_convert_1 (data)
1801   PTR data;
1802 {
1803   struct fc_args * args = (struct fc_args *) data;
1804
1805   args->t = build_real (args->type,
1806                         real_value_truncate (TYPE_MODE (args->type),
1807                                              TREE_REAL_CST (args->arg1)));
1808 }
1809
1810 /* Given T, a tree representing type conversion of ARG1, a constant,
1811    return a constant tree representing the result of conversion.  */
1812
1813 static tree
1814 fold_convert (t, arg1)
1815      register tree t;
1816      register tree arg1;
1817 {
1818   register tree type = TREE_TYPE (t);
1819   int overflow = 0;
1820
1821   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1822     {
1823       if (TREE_CODE (arg1) == INTEGER_CST)
1824         {
1825           /* If we would build a constant wider than GCC supports,
1826              leave the conversion unfolded.  */
1827           if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1828             return t;
1829
1830           /* Given an integer constant, make new constant with new type,
1831              appropriately sign-extended or truncated.  */
1832           t = build_int_2 (TREE_INT_CST_LOW (arg1),
1833                            TREE_INT_CST_HIGH (arg1));
1834           TREE_TYPE (t) = type;
1835           /* Indicate an overflow if (1) ARG1 already overflowed,
1836              or (2) force_fit_type indicates an overflow.
1837              Tell force_fit_type that an overflow has already occurred
1838              if ARG1 is a too-large unsigned value and T is signed.
1839              But don't indicate an overflow if converting a pointer.  */
1840           TREE_OVERFLOW (t)
1841             = ((force_fit_type (t,
1842                                 (TREE_INT_CST_HIGH (arg1) < 0
1843                                  && (TREE_UNSIGNED (type)
1844                                     < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1845                 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1846                || TREE_OVERFLOW (arg1));
1847           TREE_CONSTANT_OVERFLOW (t)
1848             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1849         }
1850 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1851       else if (TREE_CODE (arg1) == REAL_CST)
1852         {
1853           /* Don't initialize these, use assignments.
1854              Initialized local aggregates don't work on old compilers.  */
1855           REAL_VALUE_TYPE x;
1856           REAL_VALUE_TYPE l;
1857           REAL_VALUE_TYPE u;
1858           tree type1 = TREE_TYPE (arg1);
1859           int no_upper_bound;
1860
1861           x = TREE_REAL_CST (arg1);
1862           l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1863
1864           no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1865           if (!no_upper_bound)
1866             u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1867
1868           /* See if X will be in range after truncation towards 0.
1869              To compensate for truncation, move the bounds away from 0,
1870              but reject if X exactly equals the adjusted bounds.  */
1871 #ifdef REAL_ARITHMETIC
1872           REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1873           if (!no_upper_bound)
1874             REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1875 #else
1876           l--;
1877           if (!no_upper_bound)
1878             u++;
1879 #endif
1880           /* If X is a NaN, use zero instead and show we have an overflow.
1881              Otherwise, range check.  */
1882           if (REAL_VALUE_ISNAN (x))
1883             overflow = 1, x = dconst0;
1884           else if (! (REAL_VALUES_LESS (l, x)
1885                       && !no_upper_bound
1886                       && REAL_VALUES_LESS (x, u)))
1887             overflow = 1;
1888
1889 #ifndef REAL_ARITHMETIC
1890           {
1891             HOST_WIDE_INT low, high;
1892             HOST_WIDE_INT half_word
1893               = (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2);
1894
1895             if (x < 0)
1896               x = -x;
1897
1898             high = (HOST_WIDE_INT) (x / half_word / half_word);
1899             x -= (REAL_VALUE_TYPE) high * half_word * half_word;
1900             if (x >= (REAL_VALUE_TYPE) half_word * half_word / 2)
1901               {
1902                 low = x - (REAL_VALUE_TYPE) half_word * half_word / 2;
1903                 low |= (HOST_WIDE_INT) -1 << (HOST_BITS_PER_WIDE_INT - 1);
1904               }
1905             else
1906               low = (HOST_WIDE_INT) x;
1907             if (TREE_REAL_CST (arg1) < 0)
1908               neg_double (low, high, &low, &high);
1909             t = build_int_2 (low, high);
1910           }
1911 #else
1912           {
1913             HOST_WIDE_INT low, high;
1914             REAL_VALUE_TO_INT (&low, &high, x);
1915             t = build_int_2 (low, high);
1916           }
1917 #endif
1918           TREE_TYPE (t) = type;
1919           TREE_OVERFLOW (t)
1920             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1921           TREE_CONSTANT_OVERFLOW (t)
1922             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1923         }
1924 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1925       TREE_TYPE (t) = type;
1926     }
1927   else if (TREE_CODE (type) == REAL_TYPE)
1928     {
1929 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1930       if (TREE_CODE (arg1) == INTEGER_CST)
1931         return build_real_from_int_cst (type, arg1);
1932 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1933       if (TREE_CODE (arg1) == REAL_CST)
1934         {
1935           struct fc_args args;
1936
1937           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1938             {
1939               t = arg1;
1940               TREE_TYPE (arg1) = type;
1941               return t;
1942             }
1943
1944           /* Setup input for fold_convert_1() */
1945           args.arg1 = arg1;
1946           args.type = type;
1947
1948           if (do_float_handler (fold_convert_1, (PTR) &args))
1949             {
1950               /* Receive output from fold_convert_1() */
1951               t = args.t;
1952             }
1953           else
1954             {
1955               /* We got an exception from fold_convert_1() */
1956               overflow = 1;
1957               t = copy_node (arg1);
1958             }
1959
1960           TREE_OVERFLOW (t)
1961             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1962           TREE_CONSTANT_OVERFLOW (t)
1963             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1964           return t;
1965         }
1966     }
1967   TREE_CONSTANT (t) = 1;
1968   return t;
1969 }
1970 \f
1971 /* Return an expr equal to X but certainly not valid as an lvalue.  */
1972
1973 tree
1974 non_lvalue (x)
1975      tree x;
1976 {
1977   tree result;
1978
1979   /* These things are certainly not lvalues.  */
1980   if (TREE_CODE (x) == NON_LVALUE_EXPR
1981       || TREE_CODE (x) == INTEGER_CST
1982       || TREE_CODE (x) == REAL_CST
1983       || TREE_CODE (x) == STRING_CST
1984       || TREE_CODE (x) == ADDR_EXPR)
1985     return x;
1986
1987   result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1988   TREE_CONSTANT (result) = TREE_CONSTANT (x);
1989   return result;
1990 }
1991
1992 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1993    Zero means allow extended lvalues.  */
1994
1995 int pedantic_lvalues;
1996
1997 /* When pedantic, return an expr equal to X but certainly not valid as a
1998    pedantic lvalue.  Otherwise, return X.  */
1999
2000 tree
2001 pedantic_non_lvalue (x)
2002      tree x;
2003 {
2004   if (pedantic_lvalues)
2005     return non_lvalue (x);
2006   else
2007     return x;
2008 }
2009 \f
2010 /* Given a tree comparison code, return the code that is the logical inverse
2011    of the given code.  It is not safe to do this for floating-point
2012    comparisons, except for NE_EXPR and EQ_EXPR.  */
2013
2014 static enum tree_code
2015 invert_tree_comparison (code)
2016      enum tree_code code;
2017 {
2018   switch (code)
2019     {
2020     case EQ_EXPR:
2021       return NE_EXPR;
2022     case NE_EXPR:
2023       return EQ_EXPR;
2024     case GT_EXPR:
2025       return LE_EXPR;
2026     case GE_EXPR:
2027       return LT_EXPR;
2028     case LT_EXPR:
2029       return GE_EXPR;
2030     case LE_EXPR:
2031       return GT_EXPR;
2032     default:
2033       abort ();
2034     }
2035 }
2036
2037 /* Similar, but return the comparison that results if the operands are
2038    swapped.  This is safe for floating-point.  */
2039
2040 static enum tree_code
2041 swap_tree_comparison (code)
2042      enum tree_code code;
2043 {
2044   switch (code)
2045     {
2046     case EQ_EXPR:
2047     case NE_EXPR:
2048       return code;
2049     case GT_EXPR:
2050       return LT_EXPR;
2051     case GE_EXPR:
2052       return LE_EXPR;
2053     case LT_EXPR:
2054       return GT_EXPR;
2055     case LE_EXPR:
2056       return GE_EXPR;
2057     default:
2058       abort ();
2059     }
2060 }
2061
2062 /* Return nonzero if CODE is a tree code that represents a truth value.  */
2063
2064 static int
2065 truth_value_p (code)
2066      enum tree_code code;
2067 {
2068   return (TREE_CODE_CLASS (code) == '<'
2069           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
2070           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
2071           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
2072 }
2073 \f
2074 /* Return nonzero if two operands are necessarily equal.
2075    If ONLY_CONST is non-zero, only return non-zero for constants.
2076    This function tests whether the operands are indistinguishable;
2077    it does not test whether they are equal using C's == operation.
2078    The distinction is important for IEEE floating point, because
2079    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2080    (2) two NaNs may be indistinguishable, but NaN!=NaN.  */
2081
2082 int
2083 operand_equal_p (arg0, arg1, only_const)
2084      tree arg0, arg1;
2085      int only_const;
2086 {
2087   /* If both types don't have the same signedness, then we can't consider
2088      them equal.  We must check this before the STRIP_NOPS calls
2089      because they may change the signedness of the arguments.  */
2090   if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
2091     return 0;
2092
2093   STRIP_NOPS (arg0);
2094   STRIP_NOPS (arg1);
2095
2096   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2097       /* This is needed for conversions and for COMPONENT_REF.
2098          Might as well play it safe and always test this.  */
2099       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2100       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2101       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2102     return 0;
2103
2104   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2105      We don't care about side effects in that case because the SAVE_EXPR
2106      takes care of that for us. In all other cases, two expressions are
2107      equal if they have no side effects.  If we have two identical
2108      expressions with side effects that should be treated the same due
2109      to the only side effects being identical SAVE_EXPR's, that will
2110      be detected in the recursive calls below.  */
2111   if (arg0 == arg1 && ! only_const
2112       && (TREE_CODE (arg0) == SAVE_EXPR
2113           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2114     return 1;
2115
2116   /* Next handle constant cases, those for which we can return 1 even
2117      if ONLY_CONST is set.  */
2118   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2119     switch (TREE_CODE (arg0))
2120       {
2121       case INTEGER_CST:
2122         return (! TREE_CONSTANT_OVERFLOW (arg0)
2123                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2124                 && TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
2125                 && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1));
2126
2127       case REAL_CST:
2128         return (! TREE_CONSTANT_OVERFLOW (arg0)
2129                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2130                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2131                                           TREE_REAL_CST (arg1)));
2132
2133       case COMPLEX_CST:
2134         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2135                                  only_const)
2136                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2137                                     only_const));
2138
2139       case STRING_CST:
2140         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2141                 && ! strncmp (TREE_STRING_POINTER (arg0),
2142                               TREE_STRING_POINTER (arg1),
2143                               TREE_STRING_LENGTH (arg0)));
2144
2145       case ADDR_EXPR:
2146         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2147                                 0);
2148       default:
2149         break;
2150       }
2151
2152   if (only_const)
2153     return 0;
2154
2155   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2156     {
2157     case '1':
2158       /* Two conversions are equal only if signedness and modes match.  */
2159       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
2160           && (TREE_UNSIGNED (TREE_TYPE (arg0))
2161               != TREE_UNSIGNED (TREE_TYPE (arg1))))
2162         return 0;
2163
2164       return operand_equal_p (TREE_OPERAND (arg0, 0),
2165                               TREE_OPERAND (arg1, 0), 0);
2166
2167     case '<':
2168     case '2':
2169       if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
2170           && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
2171                               0))
2172         return 1;
2173
2174       /* For commutative ops, allow the other order.  */
2175       return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
2176                || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
2177                || TREE_CODE (arg0) == BIT_IOR_EXPR
2178                || TREE_CODE (arg0) == BIT_XOR_EXPR
2179                || TREE_CODE (arg0) == BIT_AND_EXPR
2180                || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
2181               && operand_equal_p (TREE_OPERAND (arg0, 0),
2182                                   TREE_OPERAND (arg1, 1), 0)
2183               && operand_equal_p (TREE_OPERAND (arg0, 1),
2184                                   TREE_OPERAND (arg1, 0), 0));
2185
2186     case 'r':
2187       /* If either of the pointer (or reference) expressions we are dereferencing
2188          contain a side effect, these cannot be equal. */
2189       if (TREE_SIDE_EFFECTS (arg0)
2190           || TREE_SIDE_EFFECTS (arg1))
2191         return 0;
2192
2193       switch (TREE_CODE (arg0))
2194         {
2195         case INDIRECT_REF:
2196           return operand_equal_p (TREE_OPERAND (arg0, 0),
2197                                   TREE_OPERAND (arg1, 0), 0);
2198
2199         case COMPONENT_REF:
2200         case ARRAY_REF:
2201           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2202                                    TREE_OPERAND (arg1, 0), 0)
2203                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2204                                       TREE_OPERAND (arg1, 1), 0));
2205
2206         case BIT_FIELD_REF:
2207           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2208                                    TREE_OPERAND (arg1, 0), 0)
2209                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2210                                       TREE_OPERAND (arg1, 1), 0)
2211                   && operand_equal_p (TREE_OPERAND (arg0, 2),
2212                                       TREE_OPERAND (arg1, 2), 0));
2213         default:
2214           return 0;
2215         }
2216
2217     case 'e':
2218       if (TREE_CODE (arg0) == RTL_EXPR)
2219         return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
2220       return 0;
2221
2222     default:
2223       return 0;
2224     }
2225 }
2226 \f
2227 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2228    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2229
2230    When in doubt, return 0.  */
2231
2232 static int
2233 operand_equal_for_comparison_p (arg0, arg1, other)
2234      tree arg0, arg1;
2235      tree other;
2236 {
2237   int unsignedp1, unsignedpo;
2238   tree primarg0, primarg1, primother;
2239   unsigned correct_width;
2240
2241   if (operand_equal_p (arg0, arg1, 0))
2242     return 1;
2243
2244   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2245       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2246     return 0;
2247
2248   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2249      and see if the inner values are the same.  This removes any
2250      signedness comparison, which doesn't matter here.  */
2251   primarg0 = arg0, primarg1 = arg1;
2252   STRIP_NOPS (primarg0);  STRIP_NOPS (primarg1);
2253   if (operand_equal_p (primarg0, primarg1, 0))
2254     return 1;
2255
2256   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2257      actual comparison operand, ARG0.
2258
2259      First throw away any conversions to wider types
2260      already present in the operands.  */
2261
2262   primarg1 = get_narrower (arg1, &unsignedp1);
2263   primother = get_narrower (other, &unsignedpo);
2264
2265   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2266   if (unsignedp1 == unsignedpo
2267       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2268       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2269     {
2270       tree type = TREE_TYPE (arg0);
2271
2272       /* Make sure shorter operand is extended the right way
2273          to match the longer operand.  */
2274       primarg1 = convert (signed_or_unsigned_type (unsignedp1,
2275                                                   TREE_TYPE (primarg1)),
2276                          primarg1);
2277
2278       if (operand_equal_p (arg0, convert (type, primarg1), 0))
2279         return 1;
2280     }
2281
2282   return 0;
2283 }
2284 \f
2285 /* See if ARG is an expression that is either a comparison or is performing
2286    arithmetic on comparisons.  The comparisons must only be comparing
2287    two different values, which will be stored in *CVAL1 and *CVAL2; if
2288    they are non-zero it means that some operands have already been found.
2289    No variables may be used anywhere else in the expression except in the
2290    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2291    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2292
2293    If this is true, return 1.  Otherwise, return zero.  */
2294
2295 static int
2296 twoval_comparison_p (arg, cval1, cval2, save_p)
2297      tree arg;
2298      tree *cval1, *cval2;
2299      int *save_p;
2300 {
2301   enum tree_code code = TREE_CODE (arg);
2302   char class = TREE_CODE_CLASS (code);
2303
2304   /* We can handle some of the 'e' cases here.  */
2305   if (class == 'e' && code == TRUTH_NOT_EXPR)
2306     class = '1';
2307   else if (class == 'e'
2308            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2309                || code == COMPOUND_EXPR))
2310     class = '2';
2311
2312   /* ??? Disable this since the SAVE_EXPR might already be in use outside
2313      the expression.  There may be no way to make this work, but it needs
2314      to be looked at again for 2.6.  */
2315 #if 0
2316   else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0)
2317     {
2318       /* If we've already found a CVAL1 or CVAL2, this expression is
2319          two complex to handle.  */
2320       if (*cval1 || *cval2)
2321         return 0;
2322
2323       class = '1';
2324       *save_p = 1;
2325     }
2326 #endif
2327
2328   switch (class)
2329     {
2330     case '1':
2331       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2332
2333     case '2':
2334       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2335               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2336                                       cval1, cval2, save_p));
2337
2338     case 'c':
2339       return 1;
2340
2341     case 'e':
2342       if (code == COND_EXPR)
2343         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2344                                      cval1, cval2, save_p)
2345                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2346                                         cval1, cval2, save_p)
2347                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2348                                         cval1, cval2, save_p));
2349       return 0;
2350
2351     case '<':
2352       /* First see if we can handle the first operand, then the second.  For
2353          the second operand, we know *CVAL1 can't be zero.  It must be that
2354          one side of the comparison is each of the values; test for the
2355          case where this isn't true by failing if the two operands
2356          are the same.  */
2357
2358       if (operand_equal_p (TREE_OPERAND (arg, 0),
2359                            TREE_OPERAND (arg, 1), 0))
2360         return 0;
2361
2362       if (*cval1 == 0)
2363         *cval1 = TREE_OPERAND (arg, 0);
2364       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2365         ;
2366       else if (*cval2 == 0)
2367         *cval2 = TREE_OPERAND (arg, 0);
2368       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2369         ;
2370       else
2371         return 0;
2372
2373       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2374         ;
2375       else if (*cval2 == 0)
2376         *cval2 = TREE_OPERAND (arg, 1);
2377       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2378         ;
2379       else
2380         return 0;
2381
2382       return 1;
2383
2384     default:
2385       return 0;
2386     }
2387 }
2388 \f
2389 /* ARG is a tree that is known to contain just arithmetic operations and
2390    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2391    any occurrence of OLD0 as an operand of a comparison and likewise for
2392    NEW1 and OLD1.  */
2393
2394 static tree
2395 eval_subst (arg, old0, new0, old1, new1)
2396      tree arg;
2397      tree old0, new0, old1, new1;
2398 {
2399   tree type = TREE_TYPE (arg);
2400   enum tree_code code = TREE_CODE (arg);
2401   char class = TREE_CODE_CLASS (code);
2402
2403   /* We can handle some of the 'e' cases here.  */
2404   if (class == 'e' && code == TRUTH_NOT_EXPR)
2405     class = '1';
2406   else if (class == 'e'
2407            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2408     class = '2';
2409
2410   switch (class)
2411     {
2412     case '1':
2413       return fold (build1 (code, type,
2414                            eval_subst (TREE_OPERAND (arg, 0),
2415                                        old0, new0, old1, new1)));
2416
2417     case '2':
2418       return fold (build (code, type,
2419                           eval_subst (TREE_OPERAND (arg, 0),
2420                                       old0, new0, old1, new1),
2421                           eval_subst (TREE_OPERAND (arg, 1),
2422                                       old0, new0, old1, new1)));
2423
2424     case 'e':
2425       switch (code)
2426         {
2427         case SAVE_EXPR:
2428           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2429
2430         case COMPOUND_EXPR:
2431           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2432
2433         case COND_EXPR:
2434           return fold (build (code, type,
2435                               eval_subst (TREE_OPERAND (arg, 0),
2436                                           old0, new0, old1, new1),
2437                               eval_subst (TREE_OPERAND (arg, 1),
2438                                           old0, new0, old1, new1),
2439                               eval_subst (TREE_OPERAND (arg, 2),
2440                                           old0, new0, old1, new1)));
2441         default:
2442           break;
2443         }
2444       /* fall through - ??? */
2445
2446     case '<':
2447       {
2448         tree arg0 = TREE_OPERAND (arg, 0);
2449         tree arg1 = TREE_OPERAND (arg, 1);
2450
2451         /* We need to check both for exact equality and tree equality.  The
2452            former will be true if the operand has a side-effect.  In that
2453            case, we know the operand occurred exactly once.  */
2454
2455         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2456           arg0 = new0;
2457         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2458           arg0 = new1;
2459
2460         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2461           arg1 = new0;
2462         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2463           arg1 = new1;
2464
2465         return fold (build (code, type, arg0, arg1));
2466       }
2467
2468     default:
2469       return arg;
2470     }
2471 }
2472 \f
2473 /* Return a tree for the case when the result of an expression is RESULT
2474    converted to TYPE and OMITTED was previously an operand of the expression
2475    but is now not needed (e.g., we folded OMITTED * 0).
2476
2477    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2478    the conversion of RESULT to TYPE.  */
2479
2480 static tree
2481 omit_one_operand (type, result, omitted)
2482      tree type, result, omitted;
2483 {
2484   tree t = convert (type, result);
2485
2486   if (TREE_SIDE_EFFECTS (omitted))
2487     return build (COMPOUND_EXPR, type, omitted, t);
2488
2489   return non_lvalue (t);
2490 }
2491
2492 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2493
2494 static tree
2495 pedantic_omit_one_operand (type, result, omitted)
2496      tree type, result, omitted;
2497 {
2498   tree t = convert (type, result);
2499
2500   if (TREE_SIDE_EFFECTS (omitted))
2501     return build (COMPOUND_EXPR, type, omitted, t);
2502
2503   return pedantic_non_lvalue (t);
2504 }
2505
2506
2507 \f
2508 /* Return a simplified tree node for the truth-negation of ARG.  This
2509    never alters ARG itself.  We assume that ARG is an operation that
2510    returns a truth value (0 or 1).  */
2511
2512 tree
2513 invert_truthvalue (arg)
2514      tree arg;
2515 {
2516   tree type = TREE_TYPE (arg);
2517   enum tree_code code = TREE_CODE (arg);
2518
2519   if (code == ERROR_MARK)
2520     return arg;
2521
2522   /* If this is a comparison, we can simply invert it, except for
2523      floating-point non-equality comparisons, in which case we just
2524      enclose a TRUTH_NOT_EXPR around what we have.  */
2525
2526   if (TREE_CODE_CLASS (code) == '<')
2527     {
2528       if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2529           && !flag_fast_math && code != NE_EXPR && code != EQ_EXPR)
2530         return build1 (TRUTH_NOT_EXPR, type, arg);
2531       else
2532         return build (invert_tree_comparison (code), type,
2533                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2534     }
2535
2536   switch (code)
2537     {
2538     case INTEGER_CST:
2539       return convert (type, build_int_2 (TREE_INT_CST_LOW (arg) == 0
2540                                          && TREE_INT_CST_HIGH (arg) == 0, 0));
2541
2542     case TRUTH_AND_EXPR:
2543       return build (TRUTH_OR_EXPR, type,
2544                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2545                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2546
2547     case TRUTH_OR_EXPR:
2548       return build (TRUTH_AND_EXPR, type,
2549                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2550                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2551
2552     case TRUTH_XOR_EXPR:
2553       /* Here we can invert either operand.  We invert the first operand
2554          unless the second operand is a TRUTH_NOT_EXPR in which case our
2555          result is the XOR of the first operand with the inside of the
2556          negation of the second operand.  */
2557
2558       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2559         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2560                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2561       else
2562         return build (TRUTH_XOR_EXPR, type,
2563                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2564                       TREE_OPERAND (arg, 1));
2565
2566     case TRUTH_ANDIF_EXPR:
2567       return build (TRUTH_ORIF_EXPR, type,
2568                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2569                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2570
2571     case TRUTH_ORIF_EXPR:
2572       return build (TRUTH_ANDIF_EXPR, type,
2573                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2574                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2575
2576     case TRUTH_NOT_EXPR:
2577       return TREE_OPERAND (arg, 0);
2578
2579     case COND_EXPR:
2580       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2581                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2582                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2583
2584     case COMPOUND_EXPR:
2585       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2586                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2587
2588     case NON_LVALUE_EXPR:
2589       return invert_truthvalue (TREE_OPERAND (arg, 0));
2590
2591     case NOP_EXPR:
2592     case CONVERT_EXPR:
2593     case FLOAT_EXPR:
2594       return build1 (TREE_CODE (arg), type,
2595                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2596
2597     case BIT_AND_EXPR:
2598       if (!integer_onep (TREE_OPERAND (arg, 1)))
2599         break;
2600       return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2601
2602     case SAVE_EXPR:
2603       return build1 (TRUTH_NOT_EXPR, type, arg);
2604
2605     case CLEANUP_POINT_EXPR:
2606       return build1 (CLEANUP_POINT_EXPR, type,
2607                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2608
2609     default:
2610       break;
2611     }
2612   if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2613     abort ();
2614   return build1 (TRUTH_NOT_EXPR, type, arg);
2615 }
2616
2617 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2618    operands are another bit-wise operation with a common input.  If so,
2619    distribute the bit operations to save an operation and possibly two if
2620    constants are involved.  For example, convert
2621         (A | B) & (A | C) into A | (B & C)
2622    Further simplification will occur if B and C are constants.
2623
2624    If this optimization cannot be done, 0 will be returned.  */
2625
2626 static tree
2627 distribute_bit_expr (code, type, arg0, arg1)
2628      enum tree_code code;
2629      tree type;
2630      tree arg0, arg1;
2631 {
2632   tree common;
2633   tree left, right;
2634
2635   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2636       || TREE_CODE (arg0) == code
2637       || (TREE_CODE (arg0) != BIT_AND_EXPR
2638           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2639     return 0;
2640
2641   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2642     {
2643       common = TREE_OPERAND (arg0, 0);
2644       left = TREE_OPERAND (arg0, 1);
2645       right = TREE_OPERAND (arg1, 1);
2646     }
2647   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2648     {
2649       common = TREE_OPERAND (arg0, 0);
2650       left = TREE_OPERAND (arg0, 1);
2651       right = TREE_OPERAND (arg1, 0);
2652     }
2653   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2654     {
2655       common = TREE_OPERAND (arg0, 1);
2656       left = TREE_OPERAND (arg0, 0);
2657       right = TREE_OPERAND (arg1, 1);
2658     }
2659   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2660     {
2661       common = TREE_OPERAND (arg0, 1);
2662       left = TREE_OPERAND (arg0, 0);
2663       right = TREE_OPERAND (arg1, 0);
2664     }
2665   else
2666     return 0;
2667
2668   return fold (build (TREE_CODE (arg0), type, common,
2669                       fold (build (code, type, left, right))));
2670 }
2671 \f
2672 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2673    starting at BITPOS.  The field is unsigned if UNSIGNEDP is non-zero.  */
2674
2675 static tree
2676 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2677      tree inner;
2678      tree type;
2679      int bitsize, bitpos;
2680      int unsignedp;
2681 {
2682   tree result = build (BIT_FIELD_REF, type, inner,
2683                        size_int (bitsize), bitsize_int (bitpos, 0L));
2684
2685   TREE_UNSIGNED (result) = unsignedp;
2686
2687   return result;
2688 }
2689
2690 /* Optimize a bit-field compare.
2691
2692    There are two cases:  First is a compare against a constant and the
2693    second is a comparison of two items where the fields are at the same
2694    bit position relative to the start of a chunk (byte, halfword, word)
2695    large enough to contain it.  In these cases we can avoid the shift
2696    implicit in bitfield extractions.
2697
2698    For constants, we emit a compare of the shifted constant with the
2699    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2700    compared.  For two fields at the same position, we do the ANDs with the
2701    similar mask and compare the result of the ANDs.
2702
2703    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2704    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2705    are the left and right operands of the comparison, respectively.
2706
2707    If the optimization described above can be done, we return the resulting
2708    tree.  Otherwise we return zero.  */
2709
2710 static tree
2711 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2712      enum tree_code code;
2713      tree compare_type;
2714      tree lhs, rhs;
2715 {
2716   int lbitpos, lbitsize, rbitpos, rbitsize;
2717   int lnbitpos, lnbitsize, rnbitpos = 0, rnbitsize = 0;
2718   tree type = TREE_TYPE (lhs);
2719   tree signed_type, unsigned_type;
2720   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2721   enum machine_mode lmode, rmode, lnmode, rnmode = VOIDmode;
2722   int lunsignedp, runsignedp;
2723   int lvolatilep = 0, rvolatilep = 0;
2724   int alignment;
2725   tree linner, rinner = NULL_TREE;
2726   tree mask;
2727   tree offset;
2728
2729   /* Get all the information about the extractions being done.  If the bit size
2730      if the same as the size of the underlying object, we aren't doing an
2731      extraction at all and so can do nothing.  */
2732   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2733                                 &lunsignedp, &lvolatilep, &alignment);
2734   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2735       || offset != 0)
2736     return 0;
2737
2738  if (!const_p)
2739    {
2740      /* If this is not a constant, we can only do something if bit positions,
2741         sizes, and signedness are the same.   */
2742      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2743                                    &runsignedp, &rvolatilep, &alignment);
2744
2745      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2746          || lunsignedp != runsignedp || offset != 0)
2747        return 0;
2748    }
2749
2750   /* See if we can find a mode to refer to this field.  We should be able to,
2751      but fail if we can't.  */
2752   lnmode = get_best_mode (lbitsize, lbitpos,
2753                           TYPE_ALIGN (TREE_TYPE (linner)), word_mode,
2754                           lvolatilep);
2755   if (lnmode == VOIDmode)
2756     return 0;
2757
2758   /* Set signed and unsigned types of the precision of this mode for the
2759      shifts below.  */
2760   signed_type = type_for_mode (lnmode, 0);
2761   unsigned_type = type_for_mode (lnmode, 1);
2762
2763   if (! const_p)
2764     {
2765       rnmode = get_best_mode (rbitsize, rbitpos,
2766                               TYPE_ALIGN (TREE_TYPE (rinner)), word_mode,
2767                               rvolatilep);
2768       if (rnmode == VOIDmode)
2769         return 0;
2770     }
2771
2772   /* Compute the bit position and size for the new reference and our offset
2773      within it. If the new reference is the same size as the original, we
2774      won't optimize anything, so return zero.  */
2775   lnbitsize = GET_MODE_BITSIZE (lnmode);
2776   lnbitpos = lbitpos & ~ (lnbitsize - 1);
2777   lbitpos -= lnbitpos;
2778   if (lnbitsize == lbitsize)
2779     return 0;
2780
2781   if (! const_p)
2782     {
2783       rnbitsize = GET_MODE_BITSIZE (rnmode);
2784       rnbitpos = rbitpos & ~ (rnbitsize - 1);
2785       rbitpos -= rnbitpos;
2786       if (rnbitsize == rbitsize)
2787         return 0;
2788     }
2789
2790   if (BYTES_BIG_ENDIAN)
2791     lbitpos = lnbitsize - lbitsize - lbitpos;
2792
2793   /* Make the mask to be used against the extracted field.  */
2794   mask = build_int_2 (~0, ~0);
2795   TREE_TYPE (mask) = unsigned_type;
2796   force_fit_type (mask, 0);
2797   mask = convert (unsigned_type, mask);
2798   mask = const_binop (LSHIFT_EXPR, mask, size_int (lnbitsize - lbitsize), 0);
2799   mask = const_binop (RSHIFT_EXPR, mask,
2800                       size_int (lnbitsize - lbitsize - lbitpos), 0);
2801
2802   if (! const_p)
2803     /* If not comparing with constant, just rework the comparison
2804        and return.  */
2805     return build (code, compare_type,
2806                   build (BIT_AND_EXPR, unsigned_type,
2807                          make_bit_field_ref (linner, unsigned_type,
2808                                              lnbitsize, lnbitpos, 1),
2809                          mask),
2810                   build (BIT_AND_EXPR, unsigned_type,
2811                          make_bit_field_ref (rinner, unsigned_type,
2812                                              rnbitsize, rnbitpos, 1),
2813                          mask));
2814
2815   /* Otherwise, we are handling the constant case. See if the constant is too
2816      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2817      this not only for its own sake, but to avoid having to test for this
2818      error case below.  If we didn't, we might generate wrong code.
2819
2820      For unsigned fields, the constant shifted right by the field length should
2821      be all zero.  For signed fields, the high-order bits should agree with
2822      the sign bit.  */
2823
2824   if (lunsignedp)
2825     {
2826       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2827                                         convert (unsigned_type, rhs),
2828                                         size_int (lbitsize), 0)))
2829         {
2830           warning ("comparison is always %d due to width of bitfield",
2831                    code == NE_EXPR);
2832           return convert (compare_type,
2833                           (code == NE_EXPR
2834                            ? integer_one_node : integer_zero_node));
2835         }
2836     }
2837   else
2838     {
2839       tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2840                               size_int (lbitsize - 1), 0);
2841       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2842         {
2843           warning ("comparison is always %d due to width of bitfield",
2844                    code == NE_EXPR);
2845           return convert (compare_type,
2846                           (code == NE_EXPR
2847                            ? integer_one_node : integer_zero_node));
2848         }
2849     }
2850
2851   /* Single-bit compares should always be against zero.  */
2852   if (lbitsize == 1 && ! integer_zerop (rhs))
2853     {
2854       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2855       rhs = convert (type, integer_zero_node);
2856     }
2857
2858   /* Make a new bitfield reference, shift the constant over the
2859      appropriate number of bits and mask it with the computed mask
2860      (in case this was a signed field).  If we changed it, make a new one.  */
2861   lhs = make_bit_field_ref (linner, unsigned_type, lnbitsize, lnbitpos, 1);
2862   if (lvolatilep)
2863     {
2864       TREE_SIDE_EFFECTS (lhs) = 1;
2865       TREE_THIS_VOLATILE (lhs) = 1;
2866     }
2867
2868   rhs = fold (const_binop (BIT_AND_EXPR,
2869                            const_binop (LSHIFT_EXPR,
2870                                         convert (unsigned_type, rhs),
2871                                         size_int (lbitpos), 0),
2872                            mask, 0));
2873
2874   return build (code, compare_type,
2875                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2876                 rhs);
2877 }
2878 \f
2879 /* Subroutine for fold_truthop: decode a field reference.
2880
2881    If EXP is a comparison reference, we return the innermost reference.
2882
2883    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2884    set to the starting bit number.
2885
2886    If the innermost field can be completely contained in a mode-sized
2887    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
2888
2889    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2890    otherwise it is not changed.
2891
2892    *PUNSIGNEDP is set to the signedness of the field.
2893
2894    *PMASK is set to the mask used.  This is either contained in a
2895    BIT_AND_EXPR or derived from the width of the field.
2896
2897    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2898
2899    Return 0 if this is not a component reference or is one that we can't
2900    do anything with.  */
2901
2902 static tree
2903 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2904                         pvolatilep, pmask, pand_mask)
2905      tree exp;
2906      int *pbitsize, *pbitpos;
2907      enum machine_mode *pmode;
2908      int *punsignedp, *pvolatilep;
2909      tree *pmask;
2910      tree *pand_mask;
2911 {
2912   tree and_mask = 0;
2913   tree mask, inner, offset;
2914   tree unsigned_type;
2915   int precision;
2916   int alignment;
2917
2918   /* All the optimizations using this function assume integer fields.
2919      There are problems with FP fields since the type_for_size call
2920      below can fail for, e.g., XFmode.  */
2921   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2922     return 0;
2923
2924   STRIP_NOPS (exp);
2925
2926   if (TREE_CODE (exp) == BIT_AND_EXPR)
2927     {
2928       and_mask = TREE_OPERAND (exp, 1);
2929       exp = TREE_OPERAND (exp, 0);
2930       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2931       if (TREE_CODE (and_mask) != INTEGER_CST)
2932         return 0;
2933     }
2934
2935
2936   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2937                                punsignedp, pvolatilep, &alignment);
2938   if ((inner == exp && and_mask == 0)
2939       || *pbitsize < 0 || offset != 0)
2940     return 0;
2941
2942   /* Compute the mask to access the bitfield.  */
2943   unsigned_type = type_for_size (*pbitsize, 1);
2944   precision = TYPE_PRECISION (unsigned_type);
2945
2946   mask = build_int_2 (~0, ~0);
2947   TREE_TYPE (mask) = unsigned_type;
2948   force_fit_type (mask, 0);
2949   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2950   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2951
2952   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
2953   if (and_mask != 0)
2954     mask = fold (build (BIT_AND_EXPR, unsigned_type,
2955                         convert (unsigned_type, and_mask), mask));
2956
2957   *pmask = mask;
2958   *pand_mask = and_mask;
2959   return inner;
2960 }
2961
2962 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2963    bit positions.  */
2964
2965 static int
2966 all_ones_mask_p (mask, size)
2967      tree mask;
2968      int size;
2969 {
2970   tree type = TREE_TYPE (mask);
2971   int precision = TYPE_PRECISION (type);
2972   tree tmask;
2973
2974   tmask = build_int_2 (~0, ~0);
2975   TREE_TYPE (tmask) = signed_type (type);
2976   force_fit_type (tmask, 0);
2977   return
2978     tree_int_cst_equal (mask,
2979                         const_binop (RSHIFT_EXPR,
2980                                      const_binop (LSHIFT_EXPR, tmask,
2981                                                   size_int (precision - size),
2982                                                   0),
2983                                      size_int (precision - size), 0));
2984 }
2985
2986 /* Subroutine for fold_truthop: determine if an operand is simple enough
2987    to be evaluated unconditionally.  */
2988
2989 static int
2990 simple_operand_p (exp)
2991      tree exp;
2992 {
2993   /* Strip any conversions that don't change the machine mode.  */
2994   while ((TREE_CODE (exp) == NOP_EXPR
2995           || TREE_CODE (exp) == CONVERT_EXPR)
2996          && (TYPE_MODE (TREE_TYPE (exp))
2997              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2998     exp = TREE_OPERAND (exp, 0);
2999
3000   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
3001           || (TREE_CODE_CLASS (TREE_CODE (exp)) == 'd'
3002               && ! TREE_ADDRESSABLE (exp)
3003               && ! TREE_THIS_VOLATILE (exp)
3004               && ! DECL_NONLOCAL (exp)
3005               /* Don't regard global variables as simple.  They may be
3006                  allocated in ways unknown to the compiler (shared memory,
3007                  #pragma weak, etc).  */
3008               && ! TREE_PUBLIC (exp)
3009               && ! DECL_EXTERNAL (exp)
3010               /* Loading a static variable is unduly expensive, but global
3011                  registers aren't expensive.  */
3012               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3013 }
3014 \f
3015 /* The following functions are subroutines to fold_range_test and allow it to
3016    try to change a logical combination of comparisons into a range test.
3017
3018    For example, both
3019         X == 2 && X == 3 && X == 4 && X == 5
3020    and
3021         X >= 2 && X <= 5
3022    are converted to
3023         (unsigned) (X - 2) <= 3
3024
3025    We describe each set of comparisons as being either inside or outside
3026    a range, using a variable named like IN_P, and then describe the
3027    range with a lower and upper bound.  If one of the bounds is omitted,
3028    it represents either the highest or lowest value of the type.
3029
3030    In the comments below, we represent a range by two numbers in brackets
3031    preceded by a "+" to designate being inside that range, or a "-" to
3032    designate being outside that range, so the condition can be inverted by
3033    flipping the prefix.  An omitted bound is represented by a "-".  For
3034    example, "- [-, 10]" means being outside the range starting at the lowest
3035    possible value and ending at 10, in other words, being greater than 10.
3036    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3037    always false.
3038
3039    We set up things so that the missing bounds are handled in a consistent
3040    manner so neither a missing bound nor "true" and "false" need to be
3041    handled using a special case.  */
3042
3043 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3044    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3045    and UPPER1_P are nonzero if the respective argument is an upper bound
3046    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3047    must be specified for a comparison.  ARG1 will be converted to ARG0's
3048    type if both are specified.  */
3049
3050 static tree
3051 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
3052      enum tree_code code;
3053      tree type;
3054      tree arg0, arg1;
3055      int upper0_p, upper1_p;
3056 {
3057   tree tem;
3058   int result;
3059   int sgn0, sgn1;
3060
3061   /* If neither arg represents infinity, do the normal operation.
3062      Else, if not a comparison, return infinity.  Else handle the special
3063      comparison rules. Note that most of the cases below won't occur, but
3064      are handled for consistency.  */
3065
3066   if (arg0 != 0 && arg1 != 0)
3067     {
3068       tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
3069                          arg0, convert (TREE_TYPE (arg0), arg1)));
3070       STRIP_NOPS (tem);
3071       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3072     }
3073
3074   if (TREE_CODE_CLASS (code) != '<')
3075     return 0;
3076
3077   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3078      for neither.  In real maths, we cannot assume open ended ranges are
3079      the same. But, this is computer arithmetic, where numbers are finite.
3080      We can therefore make the transformation of any unbounded range with
3081      the value Z, Z being greater than any representable number. This permits
3082      us to treat unbounded ranges as equal. */
3083   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3084   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3085   switch (code)
3086     {
3087     case EQ_EXPR:
3088       result = sgn0 == sgn1;
3089       break;
3090     case NE_EXPR:
3091       result = sgn0 != sgn1;
3092       break;
3093     case LT_EXPR:
3094       result = sgn0 < sgn1;
3095       break;
3096     case LE_EXPR:
3097       result = sgn0 <= sgn1;
3098       break;
3099     case GT_EXPR:
3100       result = sgn0 > sgn1;
3101       break;
3102     case GE_EXPR:
3103       result = sgn0 >= sgn1;
3104       break;
3105     default:
3106       abort ();
3107     }
3108
3109   return convert (type, result ? integer_one_node : integer_zero_node);
3110 }
3111 \f
3112 /* Given EXP, a logical expression, set the range it is testing into
3113    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3114    actually being tested.  *PLOW and *PHIGH will have be made the same type
3115    as the returned expression.  If EXP is not a comparison, we will most
3116    likely not be returning a useful value and range.  */
3117
3118 static tree
3119 make_range (exp, pin_p, plow, phigh)
3120      tree exp;
3121      int *pin_p;
3122      tree *plow, *phigh;
3123 {
3124   enum tree_code code;
3125   tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
3126   tree orig_type = NULL_TREE;
3127   int in_p, n_in_p;
3128   tree low, high, n_low, n_high;
3129
3130   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3131      and see if we can refine the range.  Some of the cases below may not
3132      happen, but it doesn't seem worth worrying about this.  We "continue"
3133      the outer loop when we've changed something; otherwise we "break"
3134      the switch, which will "break" the while.  */
3135
3136   in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
3137
3138   while (1)
3139     {
3140       code = TREE_CODE (exp);
3141
3142       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3143         {
3144           arg0 = TREE_OPERAND (exp, 0);
3145           if (TREE_CODE_CLASS (code) == '<'
3146               || TREE_CODE_CLASS (code) == '1'
3147               || TREE_CODE_CLASS (code) == '2')
3148             type = TREE_TYPE (arg0);
3149           if (TREE_CODE_CLASS (code) == '2'
3150               || TREE_CODE_CLASS (code) == '<'
3151               || (TREE_CODE_CLASS (code) == 'e'
3152                   && tree_code_length[(int) code] > 1))
3153             arg1 = TREE_OPERAND (exp, 1);
3154         }
3155
3156       /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
3157          lose a cast by accident.  */
3158       if (type != NULL_TREE && orig_type == NULL_TREE)
3159         orig_type = type;
3160
3161       switch (code)
3162         {
3163         case TRUTH_NOT_EXPR:
3164           in_p = ! in_p, exp = arg0;
3165           continue;
3166
3167         case EQ_EXPR: case NE_EXPR:
3168         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3169           /* We can only do something if the range is testing for zero
3170              and if the second operand is an integer constant.  Note that
3171              saying something is "in" the range we make is done by
3172              complementing IN_P since it will set in the initial case of
3173              being not equal to zero; "out" is leaving it alone.  */
3174           if (low == 0 || high == 0
3175               || ! integer_zerop (low) || ! integer_zerop (high)
3176               || TREE_CODE (arg1) != INTEGER_CST)
3177             break;
3178
3179           switch (code)
3180             {
3181             case NE_EXPR:  /* - [c, c]  */
3182               low = high = arg1;
3183               break;
3184             case EQ_EXPR:  /* + [c, c]  */
3185               in_p = ! in_p, low = high = arg1;
3186               break;
3187             case GT_EXPR:  /* - [-, c] */
3188               low = 0, high = arg1;
3189               break;
3190             case GE_EXPR:  /* + [c, -] */
3191               in_p = ! in_p, low = arg1, high = 0;
3192               break;
3193             case LT_EXPR:  /* - [c, -] */
3194               low = arg1, high = 0;
3195               break;
3196             case LE_EXPR:  /* + [-, c] */
3197               in_p = ! in_p, low = 0, high = arg1;
3198               break;
3199             default:
3200               abort ();
3201             }
3202
3203           exp = arg0;
3204
3205           /* If this is an unsigned comparison, we also know that EXP is
3206              greater than or equal to zero.  We base the range tests we make
3207              on that fact, so we record it here so we can parse existing
3208              range tests.  */
3209           if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
3210             {
3211               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
3212                                   1, convert (type, integer_zero_node),
3213                                   NULL_TREE))
3214                 break;
3215
3216               in_p = n_in_p, low = n_low, high = n_high;
3217
3218               /* If the high bound is missing, reverse the range so it
3219                  goes from zero to the low bound minus 1.  */
3220               if (high == 0)
3221                 {
3222                   in_p = ! in_p;
3223                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3224                                       integer_one_node, 0);
3225                   low = convert (type, integer_zero_node);
3226                 }
3227             }
3228           continue;
3229
3230         case NEGATE_EXPR:
3231           /* (-x) IN [a,b] -> x in [-b, -a]  */
3232           n_low = range_binop (MINUS_EXPR, type,
3233                                convert (type, integer_zero_node), 0, high, 1);
3234           n_high = range_binop (MINUS_EXPR, type,
3235                                 convert (type, integer_zero_node), 0, low, 0);
3236           low = n_low, high = n_high;
3237           exp = arg0;
3238           continue;
3239
3240         case BIT_NOT_EXPR:
3241           /* ~ X -> -X - 1  */
3242           exp = build (MINUS_EXPR, type, build1 (NEGATE_EXPR, type, arg0),
3243                        convert (type, integer_one_node));
3244           continue;
3245
3246         case PLUS_EXPR:  case MINUS_EXPR:
3247           if (TREE_CODE (arg1) != INTEGER_CST)
3248             break;
3249
3250           /* If EXP is signed, any overflow in the computation is undefined,
3251              so we don't worry about it so long as our computations on
3252              the bounds don't overflow.  For unsigned, overflow is defined
3253              and this is exactly the right thing.  */
3254           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3255                                type, low, 0, arg1, 0);
3256           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3257                                 type, high, 1, arg1, 0);
3258           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3259               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3260             break;
3261
3262           /* Check for an unsigned range which has wrapped around the maximum
3263              value thus making n_high < n_low, and normalize it.  */
3264           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3265             {
3266               low = range_binop (PLUS_EXPR, type, n_high, 0,
3267                                  integer_one_node, 0);
3268               high = range_binop (MINUS_EXPR, type, n_low, 0,
3269                                  integer_one_node, 0);
3270               in_p = ! in_p;
3271             }
3272           else
3273             low = n_low, high = n_high;
3274
3275           exp = arg0;
3276           continue;
3277
3278         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3279           if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3280             break;
3281
3282           if (! INTEGRAL_TYPE_P (type)
3283               || (low != 0 && ! int_fits_type_p (low, type))
3284               || (high != 0 && ! int_fits_type_p (high, type)))
3285             break;
3286
3287           n_low = low, n_high = high;
3288
3289           if (n_low != 0)
3290             n_low = convert (type, n_low);
3291
3292           if (n_high != 0)
3293             n_high = convert (type, n_high);
3294
3295           /* If we're converting from an unsigned to a signed type,
3296              we will be doing the comparison as unsigned.  The tests above
3297              have already verified that LOW and HIGH are both positive.
3298
3299              So we have to make sure that the original unsigned value will
3300              be interpreted as positive.  */
3301           if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3302             {
3303               tree equiv_type = type_for_mode (TYPE_MODE (type), 1);
3304               tree high_positive;
3305
3306               /* A range without an upper bound is, naturally, unbounded.
3307                  Since convert would have cropped a very large value, use
3308                   the max value for the destination type.  */
3309
3310               high_positive = TYPE_MAX_VALUE (equiv_type);
3311               if (!high_positive)
3312                 {
3313                   high_positive = TYPE_MAX_VALUE (type);
3314                   if (!high_positive)
3315                     abort();
3316                 }
3317               high_positive = fold (build (RSHIFT_EXPR, type,
3318                                            convert (type, high_positive),
3319                                            convert (type, integer_one_node)));
3320
3321               /* If the low bound is specified, "and" the range with the
3322                  range for which the original unsigned value will be
3323                  positive.  */
3324               if (low != 0)
3325                 {
3326                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3327                                       1, n_low, n_high,
3328                                       1, convert (type, integer_zero_node),
3329                                       high_positive))
3330                     break;
3331
3332                   in_p = (n_in_p == in_p);
3333                 }
3334               else
3335                 {
3336                   /* Otherwise, "or" the range with the range of the input
3337                      that will be interpreted as negative.  */
3338                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3339                                       0, n_low, n_high,
3340                                       1, convert (type, integer_zero_node),
3341                                       high_positive))
3342                     break;
3343
3344                   in_p = (in_p != n_in_p);
3345                 }
3346             }
3347
3348           exp = arg0;
3349           low = n_low, high = n_high;
3350           continue;
3351
3352         default:
3353           break;
3354         }
3355
3356       break;
3357     }
3358
3359   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3360   if (TREE_CODE (exp) == INTEGER_CST)
3361     {
3362       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3363                                                  exp, 0, low, 0))
3364                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3365                                                     exp, 1, high, 1)));
3366       low = high = 0;
3367       exp = 0;
3368     }
3369
3370   *pin_p = in_p, *plow = low, *phigh = high;
3371   return exp;
3372 }
3373 \f
3374 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3375    type, TYPE, return an expression to test if EXP is in (or out of, depending
3376    on IN_P) the range.  */
3377
3378 static tree
3379 build_range_check (type, exp, in_p, low, high)
3380      tree type;
3381      tree exp;
3382      int in_p;
3383      tree low, high;
3384 {
3385   tree etype = TREE_TYPE (exp);
3386   tree utype, value;
3387
3388   if (! in_p
3389       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3390     return invert_truthvalue (value);
3391
3392   else if (low == 0 && high == 0)
3393     return convert (type, integer_one_node);
3394
3395   else if (low == 0)
3396     return fold (build (LE_EXPR, type, exp, high));
3397
3398   else if (high == 0)
3399     return fold (build (GE_EXPR, type, exp, low));
3400
3401   else if (operand_equal_p (low, high, 0))
3402     return fold (build (EQ_EXPR, type, exp, low));
3403
3404   else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3405     return build_range_check (type, exp, 1, 0, high);
3406
3407   else if (integer_zerop (low))
3408     {
3409       utype = unsigned_type (etype);
3410       return build_range_check (type, convert (utype, exp), 1, 0,
3411                                 convert (utype, high));
3412     }
3413
3414   else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3415            && ! TREE_OVERFLOW (value))
3416     return build_range_check (type,
3417                               fold (build (MINUS_EXPR, etype, exp, low)),
3418                               1, convert (etype, integer_zero_node), value);
3419   else
3420     return 0;
3421 }
3422 \f
3423 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3424    can, 0 if we can't.  Set the output range into the specified parameters.  */
3425
3426 static int
3427 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3428      int *pin_p;
3429      tree *plow, *phigh;
3430      int in0_p, in1_p;
3431      tree low0, high0, low1, high1;
3432 {
3433   int no_overlap;
3434   int subset;
3435   int temp;
3436   tree tem;
3437   int in_p;
3438   tree low, high;
3439   int lowequal = ((low0 == 0 && low1 == 0)
3440                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3441                                                 low0, 0, low1, 0)));
3442   int highequal = ((high0 == 0 && high1 == 0)
3443                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3444                                                  high0, 1, high1, 1)));
3445
3446   /* Make range 0 be the range that starts first, or ends last if they
3447      start at the same value.  Swap them if it isn't.  */
3448   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3449                                  low0, 0, low1, 0))
3450       || (lowequal
3451           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3452                                         high1, 1, high0, 1))))
3453     {
3454       temp = in0_p, in0_p = in1_p, in1_p = temp;
3455       tem = low0, low0 = low1, low1 = tem;
3456       tem = high0, high0 = high1, high1 = tem;
3457     }
3458
3459   /* Now flag two cases, whether the ranges are disjoint or whether the
3460      second range is totally subsumed in the first.  Note that the tests
3461      below are simplified by the ones above.  */
3462   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3463                                           high0, 1, low1, 0));
3464   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3465                                       high1, 1, high0, 1));
3466
3467   /* We now have four cases, depending on whether we are including or
3468      excluding the two ranges.  */
3469   if (in0_p && in1_p)
3470     {
3471       /* If they don't overlap, the result is false.  If the second range
3472          is a subset it is the result.  Otherwise, the range is from the start
3473          of the second to the end of the first.  */
3474       if (no_overlap)
3475         in_p = 0, low = high = 0;
3476       else if (subset)
3477         in_p = 1, low = low1, high = high1;
3478       else
3479         in_p = 1, low = low1, high = high0;
3480     }
3481
3482   else if (in0_p && ! in1_p)
3483     {
3484       /* If they don't overlap, the result is the first range.  If they are
3485          equal, the result is false.  If the second range is a subset of the
3486          first, and the ranges begin at the same place, we go from just after
3487          the end of the first range to the end of the second.  If the second
3488          range is not a subset of the first, or if it is a subset and both
3489          ranges end at the same place, the range starts at the start of the
3490          first range and ends just before the second range.
3491          Otherwise, we can't describe this as a single range.  */
3492       if (no_overlap)
3493         in_p = 1, low = low0, high = high0;
3494       else if (lowequal && highequal)
3495         in_p = 0, low = high = 0;
3496       else if (subset && lowequal)
3497         {
3498           in_p = 1, high = high0;
3499           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3500                              integer_one_node, 0);
3501         }
3502       else if (! subset || highequal)
3503         {
3504           in_p = 1, low = low0;
3505           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3506                               integer_one_node, 0);
3507         }
3508       else
3509         return 0;
3510     }
3511
3512   else if (! in0_p && in1_p)
3513     {
3514       /* If they don't overlap, the result is the second range.  If the second
3515          is a subset of the first, the result is false.  Otherwise,
3516          the range starts just after the first range and ends at the
3517          end of the second.  */
3518       if (no_overlap)
3519         in_p = 1, low = low1, high = high1;
3520       else if (subset)
3521         in_p = 0, low = high = 0;
3522       else
3523         {
3524           in_p = 1, high = high1;
3525           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3526                              integer_one_node, 0);
3527         }
3528     }
3529
3530   else
3531     {
3532       /* The case where we are excluding both ranges.  Here the complex case
3533          is if they don't overlap.  In that case, the only time we have a
3534          range is if they are adjacent.  If the second is a subset of the
3535          first, the result is the first.  Otherwise, the range to exclude
3536          starts at the beginning of the first range and ends at the end of the
3537          second.  */
3538       if (no_overlap)
3539         {
3540           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3541                                          range_binop (PLUS_EXPR, NULL_TREE,
3542                                                       high0, 1,
3543                                                       integer_one_node, 1),
3544                                          1, low1, 0)))
3545             in_p = 0, low = low0, high = high1;
3546           else
3547             return 0;
3548         }
3549       else if (subset)
3550         in_p = 0, low = low0, high = high0;
3551       else
3552         in_p = 0, low = low0, high = high1;
3553     }
3554
3555   *pin_p = in_p, *plow = low, *phigh = high;
3556   return 1;
3557 }
3558 \f
3559 /* EXP is some logical combination of boolean tests.  See if we can
3560    merge it into some range test.  Return the new tree if so.  */
3561
3562 static tree
3563 fold_range_test (exp)
3564      tree exp;
3565 {
3566   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3567                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3568   int in0_p, in1_p, in_p;
3569   tree low0, low1, low, high0, high1, high;
3570   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3571   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3572   tree tem;
3573
3574   /* If this is an OR operation, invert both sides; we will invert
3575      again at the end.  */
3576   if (or_op)
3577     in0_p = ! in0_p, in1_p = ! in1_p;
3578
3579   /* If both expressions are the same, if we can merge the ranges, and we
3580      can build the range test, return it or it inverted.  If one of the
3581      ranges is always true or always false, consider it to be the same
3582      expression as the other.  */
3583   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3584       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3585                        in1_p, low1, high1)
3586       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3587                                          lhs != 0 ? lhs
3588                                          : rhs != 0 ? rhs : integer_zero_node,
3589                                          in_p, low, high))))
3590     return or_op ? invert_truthvalue (tem) : tem;
3591
3592   /* On machines where the branch cost is expensive, if this is a
3593      short-circuited branch and the underlying object on both sides
3594      is the same, make a non-short-circuit operation.  */
3595   else if (BRANCH_COST >= 2
3596            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3597                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3598            && operand_equal_p (lhs, rhs, 0))
3599     {
3600       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3601          unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3602          which cases we can't do this.  */
3603       if (simple_operand_p (lhs))
3604         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3605                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3606                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3607                       TREE_OPERAND (exp, 1));
3608
3609       else if (global_bindings_p () == 0
3610                && ! contains_placeholder_p (lhs))
3611         {
3612           tree common = save_expr (lhs);
3613
3614           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3615                                              or_op ? ! in0_p : in0_p,
3616                                              low0, high0))
3617               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3618                                                  or_op ? ! in1_p : in1_p,
3619                                                  low1, high1))))
3620             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3621                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3622                           TREE_TYPE (exp), lhs, rhs);
3623         }
3624     }
3625
3626   return 0;
3627 }
3628 \f
3629 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3630    bit value.  Arrange things so the extra bits will be set to zero if and
3631    only if C is signed-extended to its full width.  If MASK is nonzero,
3632    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3633
3634 static tree
3635 unextend (c, p, unsignedp, mask)
3636      tree c;
3637      int p;
3638      int unsignedp;
3639      tree mask;
3640 {
3641   tree type = TREE_TYPE (c);
3642   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3643   tree temp;
3644
3645   if (p == modesize || unsignedp)
3646     return c;
3647
3648   /* We work by getting just the sign bit into the low-order bit, then
3649      into the high-order bit, then sign-extend.  We then XOR that value
3650      with C.  */
3651   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3652   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3653
3654   /* We must use a signed type in order to get an arithmetic right shift.
3655      However, we must also avoid introducing accidental overflows, so that
3656      a subsequent call to integer_zerop will work.  Hence we must
3657      do the type conversion here.  At this point, the constant is either
3658      zero or one, and the conversion to a signed type can never overflow.
3659      We could get an overflow if this conversion is done anywhere else.  */
3660   if (TREE_UNSIGNED (type))
3661     temp = convert (signed_type (type), temp);
3662
3663   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3664   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3665   if (mask != 0)
3666     temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3667   /* If necessary, convert the type back to match the type of C.  */
3668   if (TREE_UNSIGNED (type))
3669     temp = convert (type, temp);
3670
3671   return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3672 }
3673 \f
3674 /* Find ways of folding logical expressions of LHS and RHS:
3675    Try to merge two comparisons to the same innermost item.
3676    Look for range tests like "ch >= '0' && ch <= '9'".
3677    Look for combinations of simple terms on machines with expensive branches
3678    and evaluate the RHS unconditionally.
3679
3680    For example, if we have p->a == 2 && p->b == 4 and we can make an
3681    object large enough to span both A and B, we can do this with a comparison
3682    against the object ANDed with the a mask.
3683
3684    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3685    operations to do this with one comparison.
3686
3687    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3688    function and the one above.
3689
3690    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3691    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3692
3693    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3694    two operands.
3695
3696    We return the simplified tree or 0 if no optimization is possible.  */
3697
3698 static tree
3699 fold_truthop (code, truth_type, lhs, rhs)
3700      enum tree_code code;
3701      tree truth_type, lhs, rhs;
3702 {
3703   /* If this is the "or" of two comparisons, we can do something if we
3704      the comparisons are NE_EXPR.  If this is the "and", we can do something
3705      if the comparisons are EQ_EXPR.  I.e.,
3706         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3707
3708      WANTED_CODE is this operation code.  For single bit fields, we can
3709      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3710      comparison for one-bit fields.  */
3711
3712   enum tree_code wanted_code;
3713   enum tree_code lcode, rcode;
3714   tree ll_arg, lr_arg, rl_arg, rr_arg;
3715   tree ll_inner, lr_inner, rl_inner, rr_inner;
3716   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3717   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3718   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3719   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3720   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3721   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3722   enum machine_mode lnmode, rnmode;
3723   tree ll_mask, lr_mask, rl_mask, rr_mask;
3724   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3725   tree l_const, r_const;
3726   tree lntype, rntype, result;
3727   int first_bit, end_bit;
3728   int volatilep;
3729
3730   /* Start by getting the comparison codes.  Fail if anything is volatile.
3731      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3732      it were surrounded with a NE_EXPR.  */
3733
3734   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3735     return 0;
3736
3737   lcode = TREE_CODE (lhs);
3738   rcode = TREE_CODE (rhs);
3739
3740   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3741     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3742
3743   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3744     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3745
3746   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3747     return 0;
3748
3749   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3750           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3751
3752   ll_arg = TREE_OPERAND (lhs, 0);
3753   lr_arg = TREE_OPERAND (lhs, 1);
3754   rl_arg = TREE_OPERAND (rhs, 0);
3755   rr_arg = TREE_OPERAND (rhs, 1);
3756
3757   /* If the RHS can be evaluated unconditionally and its operands are
3758      simple, it wins to evaluate the RHS unconditionally on machines
3759      with expensive branches.  In this case, this isn't a comparison
3760      that can be merged.  */
3761
3762   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
3763      are with zero (tmw).  */
3764
3765   if (BRANCH_COST >= 2
3766       && INTEGRAL_TYPE_P (TREE_TYPE (rhs))
3767       && simple_operand_p (rl_arg)
3768       && simple_operand_p (rr_arg))
3769     return build (code, truth_type, lhs, rhs);
3770
3771   /* See if the comparisons can be merged.  Then get all the parameters for
3772      each side.  */
3773
3774   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3775       || (rcode != EQ_EXPR && rcode != NE_EXPR))
3776     return 0;
3777
3778   volatilep = 0;
3779   ll_inner = decode_field_reference (ll_arg,
3780                                      &ll_bitsize, &ll_bitpos, &ll_mode,
3781                                      &ll_unsignedp, &volatilep, &ll_mask,
3782                                      &ll_and_mask);
3783   lr_inner = decode_field_reference (lr_arg,
3784                                      &lr_bitsize, &lr_bitpos, &lr_mode,
3785                                      &lr_unsignedp, &volatilep, &lr_mask,
3786                                      &lr_and_mask);
3787   rl_inner = decode_field_reference (rl_arg,
3788                                      &rl_bitsize, &rl_bitpos, &rl_mode,
3789                                      &rl_unsignedp, &volatilep, &rl_mask,
3790                                      &rl_and_mask);
3791   rr_inner = decode_field_reference (rr_arg,
3792                                      &rr_bitsize, &rr_bitpos, &rr_mode,
3793                                      &rr_unsignedp, &volatilep, &rr_mask,
3794                                      &rr_and_mask);
3795
3796   /* It must be true that the inner operation on the lhs of each
3797      comparison must be the same if we are to be able to do anything.
3798      Then see if we have constants.  If not, the same must be true for
3799      the rhs's.  */
3800   if (volatilep || ll_inner == 0 || rl_inner == 0
3801       || ! operand_equal_p (ll_inner, rl_inner, 0))
3802     return 0;
3803
3804   if (TREE_CODE (lr_arg) == INTEGER_CST
3805       && TREE_CODE (rr_arg) == INTEGER_CST)
3806     l_const = lr_arg, r_const = rr_arg;
3807   else if (lr_inner == 0 || rr_inner == 0
3808            || ! operand_equal_p (lr_inner, rr_inner, 0))
3809     return 0;
3810   else
3811     l_const = r_const = 0;
3812
3813   /* If either comparison code is not correct for our logical operation,
3814      fail.  However, we can convert a one-bit comparison against zero into
3815      the opposite comparison against that bit being set in the field.  */
3816
3817   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3818   if (lcode != wanted_code)
3819     {
3820       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3821         {
3822           /* Make the left operand unsigned, since we are only interested
3823              in the value of one bit.  Otherwise we are doing the wrong
3824              thing below.  */
3825           ll_unsignedp = 1;
3826           l_const = ll_mask;
3827         }
3828       else
3829         return 0;
3830     }
3831
3832   /* This is analogous to the code for l_const above.  */
3833   if (rcode != wanted_code)
3834     {
3835       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3836         {
3837           rl_unsignedp = 1;
3838           r_const = rl_mask;
3839         }
3840       else
3841         return 0;
3842     }
3843
3844   /* See if we can find a mode that contains both fields being compared on
3845      the left.  If we can't, fail.  Otherwise, update all constants and masks
3846      to be relative to a field of that size.  */
3847   first_bit = MIN (ll_bitpos, rl_bitpos);
3848   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3849   lnmode = get_best_mode (end_bit - first_bit, first_bit,
3850                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3851                           volatilep);
3852   if (lnmode == VOIDmode)
3853     return 0;
3854
3855   lnbitsize = GET_MODE_BITSIZE (lnmode);
3856   lnbitpos = first_bit & ~ (lnbitsize - 1);
3857   lntype = type_for_size (lnbitsize, 1);
3858   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3859
3860   if (BYTES_BIG_ENDIAN)
3861     {
3862       xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3863       xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3864     }
3865
3866   ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3867                          size_int (xll_bitpos), 0);
3868   rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3869                          size_int (xrl_bitpos), 0);
3870
3871   if (l_const)
3872     {
3873       l_const = convert (lntype, l_const);
3874       l_const = unextend (l_const,  ll_bitsize, ll_unsignedp, ll_and_mask);
3875       l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3876       if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3877                                         fold (build1 (BIT_NOT_EXPR,
3878                                                       lntype, ll_mask)),
3879                                         0)))
3880         {
3881           warning ("comparison is always %d", wanted_code == NE_EXPR);
3882
3883           return convert (truth_type,
3884                           wanted_code == NE_EXPR
3885                           ? integer_one_node : integer_zero_node);
3886         }
3887     }
3888   if (r_const)
3889     {
3890       r_const = convert (lntype, r_const);
3891       r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3892       r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3893       if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3894                                         fold (build1 (BIT_NOT_EXPR,
3895                                                       lntype, rl_mask)),
3896                                         0)))
3897         {
3898           warning ("comparison is always %d", wanted_code == NE_EXPR);
3899
3900           return convert (truth_type,
3901                           wanted_code == NE_EXPR
3902                           ? integer_one_node : integer_zero_node);
3903         }
3904     }
3905
3906   /* If the right sides are not constant, do the same for it.  Also,
3907      disallow this optimization if a size or signedness mismatch occurs
3908      between the left and right sides.  */
3909   if (l_const == 0)
3910     {
3911       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3912           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3913           /* Make sure the two fields on the right
3914              correspond to the left without being swapped.  */
3915           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3916         return 0;
3917
3918       first_bit = MIN (lr_bitpos, rr_bitpos);
3919       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3920       rnmode = get_best_mode (end_bit - first_bit, first_bit,
3921                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3922                               volatilep);
3923       if (rnmode == VOIDmode)
3924         return 0;
3925
3926       rnbitsize = GET_MODE_BITSIZE (rnmode);
3927       rnbitpos = first_bit & ~ (rnbitsize - 1);
3928       rntype = type_for_size (rnbitsize, 1);
3929       xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3930
3931       if (BYTES_BIG_ENDIAN)
3932         {
3933           xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3934           xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3935         }
3936
3937       lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3938                              size_int (xlr_bitpos), 0);
3939       rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3940                              size_int (xrr_bitpos), 0);
3941
3942       /* Make a mask that corresponds to both fields being compared.
3943          Do this for both items being compared.  If the operands are the
3944          same size and the bits being compared are in the same position
3945          then we can do this by masking both and comparing the masked
3946          results.  */
3947       ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3948       lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3949       if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3950         {
3951           lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3952                                     ll_unsignedp || rl_unsignedp);
3953           if (! all_ones_mask_p (ll_mask, lnbitsize))
3954             lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3955
3956           rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3957                                     lr_unsignedp || rr_unsignedp);
3958           if (! all_ones_mask_p (lr_mask, rnbitsize))
3959             rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3960
3961           return build (wanted_code, truth_type, lhs, rhs);
3962         }
3963
3964       /* There is still another way we can do something:  If both pairs of
3965          fields being compared are adjacent, we may be able to make a wider
3966          field containing them both.
3967
3968          Note that we still must mask the lhs/rhs expressions.  Furthermore,
3969          the mask must be shifted to account for the shift done by
3970          make_bit_field_ref.  */
3971       if ((ll_bitsize + ll_bitpos == rl_bitpos
3972            && lr_bitsize + lr_bitpos == rr_bitpos)
3973           || (ll_bitpos == rl_bitpos + rl_bitsize
3974               && lr_bitpos == rr_bitpos + rr_bitsize))
3975         {
3976           tree type;
3977
3978           lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3979                                     MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3980           rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3981                                     MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3982
3983           ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3984                                  size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3985           lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3986                                  size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3987
3988           /* Convert to the smaller type before masking out unwanted bits.  */
3989           type = lntype;
3990           if (lntype != rntype)
3991             {
3992               if (lnbitsize > rnbitsize)
3993                 {
3994                   lhs = convert (rntype, lhs);
3995                   ll_mask = convert (rntype, ll_mask);
3996                   type = rntype;
3997                 }
3998               else if (lnbitsize < rnbitsize)
3999                 {
4000                   rhs = convert (lntype, rhs);
4001                   lr_mask = convert (lntype, lr_mask);
4002                   type = lntype;
4003                 }
4004             }
4005
4006           if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
4007             lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
4008
4009           if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
4010             rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
4011
4012           return build (wanted_code, truth_type, lhs, rhs);
4013         }
4014
4015       return 0;
4016     }
4017
4018   /* Handle the case of comparisons with constants.  If there is something in
4019      common between the masks, those bits of the constants must be the same.
4020      If not, the condition is always false.  Test for this to avoid generating
4021      incorrect code below.  */
4022   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
4023   if (! integer_zerop (result)
4024       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
4025                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
4026     {
4027       if (wanted_code == NE_EXPR)
4028         {
4029           warning ("`or' of unmatched not-equal tests is always 1");
4030           return convert (truth_type, integer_one_node);
4031         }
4032       else
4033         {
4034           warning ("`and' of mutually exclusive equal-tests is always 0");
4035           return convert (truth_type, integer_zero_node);
4036         }
4037     }
4038
4039   /* Construct the expression we will return.  First get the component
4040      reference we will make.  Unless the mask is all ones the width of
4041      that field, perform the mask operation.  Then compare with the
4042      merged constant.  */
4043   result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
4044                                ll_unsignedp || rl_unsignedp);
4045
4046   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
4047   if (! all_ones_mask_p (ll_mask, lnbitsize))
4048     result = build (BIT_AND_EXPR, lntype, result, ll_mask);
4049
4050   return build (wanted_code, truth_type, result,
4051                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
4052 }
4053 \f
4054 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4055    S, a SAVE_EXPR, return the expression actually being evaluated.   Note
4056    that we may sometimes modify the tree.  */
4057
4058 static tree
4059 strip_compound_expr (t, s)
4060      tree t;
4061      tree s;
4062 {
4063   enum tree_code code = TREE_CODE (t);
4064
4065   /* See if this is the COMPOUND_EXPR we want to eliminate.  */
4066   if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4067       && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4068     return TREE_OPERAND (t, 1);
4069
4070   /* See if this is a COND_EXPR or a simple arithmetic operator.   We
4071      don't bother handling any other types.  */
4072   else if (code == COND_EXPR)
4073     {
4074       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4075       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4076       TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4077     }
4078   else if (TREE_CODE_CLASS (code) == '1')
4079     TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4080   else if (TREE_CODE_CLASS (code) == '<'
4081            || TREE_CODE_CLASS (code) == '2')
4082     {
4083       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4084       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4085     }
4086
4087   return t;
4088 }
4089 \f
4090 /* Return a node which has the indicated constant VALUE (either 0 or
4091    1), and is of the indicated TYPE.  */
4092
4093 static tree
4094 constant_boolean_node (value, type)
4095      int value;
4096      tree type;
4097 {
4098   if (type == integer_type_node)
4099     return value ? integer_one_node : integer_zero_node;
4100   else if (TREE_CODE (type) == BOOLEAN_TYPE)
4101     return truthvalue_conversion (value ? integer_one_node :
4102                                   integer_zero_node);
4103   else
4104     {
4105       tree t = build_int_2 (value, 0);
4106       TREE_TYPE (t) = type;
4107       return t;
4108     }
4109 }
4110
4111 /* Utility function for the following routine, to see how complex a nesting of
4112    COND_EXPRs can be.  EXPR is the expression and LIMIT is a count beyond which
4113    we don't care (to avoid spending too much time on complex expressions.).  */
4114
4115 static int
4116 count_cond (expr, lim)
4117      tree expr;
4118      int lim;
4119 {
4120   int true, false;
4121
4122   if (TREE_CODE (expr) != COND_EXPR)
4123     return 0;
4124   else if (lim <= 0)
4125     return 0;
4126
4127   true = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4128   false = count_cond (TREE_OPERAND (expr, 2), lim - 1 - true);
4129   return MIN (lim, 1 + true + false);
4130 }
4131 \f
4132 /* Perform constant folding and related simplification of EXPR.
4133    The related simplifications include x*1 => x, x*0 => 0, etc.,
4134    and application of the associative law.
4135    NOP_EXPR conversions may be removed freely (as long as we
4136    are careful not to change the C type of the overall expression)
4137    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4138    but we can constant-fold them if they have constant operands.  */
4139
4140 tree
4141 fold (expr)
4142      tree expr;
4143 {
4144   register tree t = expr;
4145   tree t1 = NULL_TREE;
4146   tree tem;
4147   tree type = TREE_TYPE (expr);
4148   register tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4149   register enum tree_code code = TREE_CODE (t);
4150   register int kind;
4151   int invert;
4152
4153   /* WINS will be nonzero when the switch is done
4154      if all operands are constant.  */
4155
4156   int wins = 1;
4157
4158   /* Don't try to process an RTL_EXPR since its operands aren't trees.
4159      Likewise for a SAVE_EXPR that's already been evaluated.  */
4160   if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t)) != 0)
4161     return t;
4162
4163   /* Return right away if already constant.  */
4164   if (TREE_CONSTANT (t))
4165     {
4166       if (code == CONST_DECL)
4167         return DECL_INITIAL (t);
4168       return t;
4169     }
4170
4171 #ifdef MAX_INTEGER_COMPUTATION_MODE
4172   check_max_integer_computation_mode (expr);
4173 #endif
4174
4175   kind = TREE_CODE_CLASS (code);
4176   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4177     {
4178       tree subop;
4179
4180       /* Special case for conversion ops that can have fixed point args.  */
4181       arg0 = TREE_OPERAND (t, 0);
4182
4183       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
4184       if (arg0 != 0)
4185         STRIP_TYPE_NOPS (arg0);
4186
4187       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4188         subop = TREE_REALPART (arg0);
4189       else
4190         subop = arg0;
4191
4192       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4193 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4194           && TREE_CODE (subop) != REAL_CST
4195 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4196           )
4197         /* Note that TREE_CONSTANT isn't enough:
4198            static var addresses are constant but we can't
4199            do arithmetic on them.  */
4200         wins = 0;
4201     }
4202   else if (kind == 'e' || kind == '<'
4203            || kind == '1' || kind == '2' || kind == 'r')
4204     {
4205       register int len = tree_code_length[(int) code];
4206       register int i;
4207       for (i = 0; i < len; i++)
4208         {
4209           tree op = TREE_OPERAND (t, i);
4210           tree subop;
4211
4212           if (op == 0)
4213             continue;           /* Valid for CALL_EXPR, at least.  */
4214
4215           if (kind == '<' || code == RSHIFT_EXPR)
4216             {
4217               /* Signedness matters here.  Perhaps we can refine this
4218                  later.  */
4219               STRIP_TYPE_NOPS (op);
4220             }
4221           else
4222             {
4223               /* Strip any conversions that don't change the mode.  */
4224               STRIP_NOPS (op);
4225             }
4226
4227           if (TREE_CODE (op) == COMPLEX_CST)
4228             subop = TREE_REALPART (op);
4229           else
4230             subop = op;
4231
4232           if (TREE_CODE (subop) != INTEGER_CST
4233 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4234               && TREE_CODE (subop) != REAL_CST
4235 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4236               )
4237             /* Note that TREE_CONSTANT isn't enough:
4238                static var addresses are constant but we can't
4239                do arithmetic on them.  */
4240             wins = 0;
4241
4242           if (i == 0)
4243             arg0 = op;
4244           else if (i == 1)
4245             arg1 = op;
4246         }
4247     }
4248
4249   /* If this is a commutative operation, and ARG0 is a constant, move it
4250      to ARG1 to reduce the number of tests below.  */
4251   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4252        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4253        || code == BIT_AND_EXPR)
4254       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4255     {
4256       tem = arg0; arg0 = arg1; arg1 = tem;
4257
4258       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4259       TREE_OPERAND (t, 1) = tem;
4260     }
4261
4262   /* Now WINS is set as described above,
4263      ARG0 is the first operand of EXPR,
4264      and ARG1 is the second operand (if it has more than one operand).
4265
4266      First check for cases where an arithmetic operation is applied to a
4267      compound, conditional, or comparison operation.  Push the arithmetic
4268      operation inside the compound or conditional to see if any folding
4269      can then be done.  Convert comparison to conditional for this purpose.
4270      The also optimizes non-constant cases that used to be done in
4271      expand_expr.
4272
4273      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
4274      one of the operands is a comparison and the other is a comparison, a
4275      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
4276      code below would make the expression more complex.  Change it to a
4277      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
4278      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
4279
4280   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4281        || code == EQ_EXPR || code == NE_EXPR)
4282       && ((truth_value_p (TREE_CODE (arg0))
4283            && (truth_value_p (TREE_CODE (arg1))
4284                || (TREE_CODE (arg1) == BIT_AND_EXPR
4285                    && integer_onep (TREE_OPERAND (arg1, 1)))))
4286           || (truth_value_p (TREE_CODE (arg1))
4287               && (truth_value_p (TREE_CODE (arg0))
4288                   || (TREE_CODE (arg0) == BIT_AND_EXPR
4289                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
4290     {
4291       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4292                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4293                        : TRUTH_XOR_EXPR,
4294                        type, arg0, arg1));
4295
4296       if (code == EQ_EXPR)
4297         t = invert_truthvalue (t);
4298
4299       return t;
4300     }
4301
4302   if (TREE_CODE_CLASS (code) == '1')
4303     {
4304       if (TREE_CODE (arg0) == COMPOUND_EXPR)
4305         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4306                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4307       else if (TREE_CODE (arg0) == COND_EXPR)
4308         {
4309           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4310                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4311                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4312
4313           /* If this was a conversion, and all we did was to move into
4314              inside the COND_EXPR, bring it back out.  But leave it if
4315              it is a conversion from integer to integer and the
4316              result precision is no wider than a word since such a
4317              conversion is cheap and may be optimized away by combine,
4318              while it couldn't if it were outside the COND_EXPR.  Then return
4319              so we don't get into an infinite recursion loop taking the
4320              conversion out and then back in.  */
4321
4322           if ((code == NOP_EXPR || code == CONVERT_EXPR
4323                || code == NON_LVALUE_EXPR)
4324               && TREE_CODE (t) == COND_EXPR
4325               && TREE_CODE (TREE_OPERAND (t, 1)) == code
4326               && TREE_CODE (TREE_OPERAND (t, 2)) == code
4327               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4328                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4329               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4330                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
4331                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4332             t = build1 (code, type,
4333                         build (COND_EXPR,
4334                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
4335                                TREE_OPERAND (t, 0),
4336                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4337                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4338           return t;
4339         }
4340       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4341         return fold (build (COND_EXPR, type, arg0,
4342                             fold (build1 (code, type, integer_one_node)),
4343                             fold (build1 (code, type, integer_zero_node))));
4344    }
4345   else if (TREE_CODE_CLASS (code) == '2'
4346            || TREE_CODE_CLASS (code) == '<')
4347     {
4348       if (TREE_CODE (arg1) == COMPOUND_EXPR)
4349         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4350                       fold (build (code, type,
4351                                    arg0, TREE_OPERAND (arg1, 1))));
4352       else if ((TREE_CODE (arg1) == COND_EXPR
4353                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4354                     && TREE_CODE_CLASS (code) != '<'))
4355                && (TREE_CODE (arg0) != COND_EXPR
4356                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4357                && (! TREE_SIDE_EFFECTS (arg0)
4358                    || (global_bindings_p () == 0
4359                        && ! contains_placeholder_p (arg0))))
4360         {
4361           tree test, true_value, false_value;
4362           tree lhs = 0, rhs = 0;
4363
4364           if (TREE_CODE (arg1) == COND_EXPR)
4365             {
4366               test = TREE_OPERAND (arg1, 0);
4367               true_value = TREE_OPERAND (arg1, 1);
4368               false_value = TREE_OPERAND (arg1, 2);
4369             }
4370           else
4371             {
4372               tree testtype = TREE_TYPE (arg1);
4373               test = arg1;
4374               true_value = convert (testtype, integer_one_node);
4375               false_value = convert (testtype, integer_zero_node);
4376             }
4377
4378           /* If ARG0 is complex we want to make sure we only evaluate
4379              it once.  Though this is only required if it is volatile, it
4380              might be more efficient even if it is not.  However, if we
4381              succeed in folding one part to a constant, we do not need
4382              to make this SAVE_EXPR.  Since we do this optimization
4383              primarily to see if we do end up with constant and this
4384              SAVE_EXPR interferes with later optimizations, suppressing
4385              it when we can is important.
4386
4387              If we are not in a function, we can't make a SAVE_EXPR, so don't
4388              try to do so.  Don't try to see if the result is a constant
4389              if an arm is a COND_EXPR since we get exponential behavior
4390              in that case.  */
4391
4392           if (TREE_CODE (arg0) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4393               && global_bindings_p () == 0
4394               && ((TREE_CODE (arg0) != VAR_DECL
4395                    && TREE_CODE (arg0) != PARM_DECL)
4396                   || TREE_SIDE_EFFECTS (arg0)))
4397             {
4398               if (TREE_CODE (true_value) != COND_EXPR)
4399                 lhs = fold (build (code, type, arg0, true_value));
4400
4401               if (TREE_CODE (false_value) != COND_EXPR)
4402                 rhs = fold (build (code, type, arg0, false_value));
4403
4404               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4405                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4406                 arg0 = save_expr (arg0), lhs = rhs = 0;
4407             }
4408
4409           if (lhs == 0)
4410             lhs = fold (build (code, type, arg0, true_value));
4411           if (rhs == 0)
4412             rhs = fold (build (code, type, arg0, false_value));
4413
4414           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4415
4416           if (TREE_CODE (arg0) == SAVE_EXPR)
4417             return build (COMPOUND_EXPR, type,
4418                           convert (void_type_node, arg0),
4419                           strip_compound_expr (test, arg0));
4420           else
4421             return convert (type, test);
4422         }
4423
4424       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4425         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4426                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4427       else if ((TREE_CODE (arg0) == COND_EXPR
4428                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4429                     && TREE_CODE_CLASS (code) != '<'))
4430                && (TREE_CODE (arg1) != COND_EXPR
4431                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4432                && (! TREE_SIDE_EFFECTS (arg1)
4433                    || (global_bindings_p () == 0
4434                        && ! contains_placeholder_p (arg1))))
4435         {
4436           tree test, true_value, false_value;
4437           tree lhs = 0, rhs = 0;
4438
4439           if (TREE_CODE (arg0) == COND_EXPR)
4440             {
4441               test = TREE_OPERAND (arg0, 0);
4442               true_value = TREE_OPERAND (arg0, 1);
4443               false_value = TREE_OPERAND (arg0, 2);
4444             }
4445           else
4446             {
4447               tree testtype = TREE_TYPE (arg0);
4448               test = arg0;
4449               true_value = convert (testtype, integer_one_node);
4450               false_value = convert (testtype, integer_zero_node);
4451             }
4452
4453           if (TREE_CODE (arg1) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4454               && global_bindings_p () == 0
4455               && ((TREE_CODE (arg1) != VAR_DECL
4456                    && TREE_CODE (arg1) != PARM_DECL)
4457                   || TREE_SIDE_EFFECTS (arg1)))
4458             {
4459               if (TREE_CODE (true_value) != COND_EXPR)
4460                 lhs = fold (build (code, type, true_value, arg1));
4461
4462               if (TREE_CODE (false_value) != COND_EXPR)
4463                 rhs = fold (build (code, type, false_value, arg1));
4464
4465               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4466                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4467                 arg1 = save_expr (arg1), lhs = rhs = 0;
4468             }
4469
4470           if (lhs == 0)
4471             lhs = fold (build (code, type, true_value, arg1));
4472
4473           if (rhs == 0)
4474             rhs = fold (build (code, type, false_value, arg1));
4475
4476           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4477           if (TREE_CODE (arg1) == SAVE_EXPR)
4478             return build (COMPOUND_EXPR, type,
4479                           convert (void_type_node, arg1),
4480                           strip_compound_expr (test, arg1));
4481           else
4482             return convert (type, test);
4483         }
4484     }
4485   else if (TREE_CODE_CLASS (code) == '<'
4486            && TREE_CODE (arg0) == COMPOUND_EXPR)
4487     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4488                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4489   else if (TREE_CODE_CLASS (code) == '<'
4490            && TREE_CODE (arg1) == COMPOUND_EXPR)
4491     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4492                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4493
4494   switch (code)
4495     {
4496     case INTEGER_CST:
4497     case REAL_CST:
4498     case STRING_CST:
4499     case COMPLEX_CST:
4500     case CONSTRUCTOR:
4501       return t;
4502
4503     case CONST_DECL:
4504       return fold (DECL_INITIAL (t));
4505
4506     case NOP_EXPR:
4507     case FLOAT_EXPR:
4508     case CONVERT_EXPR:
4509     case FIX_TRUNC_EXPR:
4510       /* Other kinds of FIX are not handled properly by fold_convert.  */
4511
4512       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4513         return TREE_OPERAND (t, 0);
4514
4515       /* Handle cases of two conversions in a row.  */
4516       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4517           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4518         {
4519           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4520           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4521           tree final_type = TREE_TYPE (t);
4522           int inside_int = INTEGRAL_TYPE_P (inside_type);
4523           int inside_ptr = POINTER_TYPE_P (inside_type);
4524           int inside_float = FLOAT_TYPE_P (inside_type);
4525           int inside_prec = TYPE_PRECISION (inside_type);
4526           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4527           int inter_int = INTEGRAL_TYPE_P (inter_type);
4528           int inter_ptr = POINTER_TYPE_P (inter_type);
4529           int inter_float = FLOAT_TYPE_P (inter_type);
4530           int inter_prec = TYPE_PRECISION (inter_type);
4531           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4532           int final_int = INTEGRAL_TYPE_P (final_type);
4533           int final_ptr = POINTER_TYPE_P (final_type);
4534           int final_float = FLOAT_TYPE_P (final_type);
4535           int final_prec = TYPE_PRECISION (final_type);
4536           int final_unsignedp = TREE_UNSIGNED (final_type);
4537
4538           /* In addition to the cases of two conversions in a row
4539              handled below, if we are converting something to its own
4540              type via an object of identical or wider precision, neither
4541              conversion is needed.  */
4542           if (inside_type == final_type
4543               && ((inter_int && final_int) || (inter_float && final_float))
4544               && inter_prec >= final_prec)
4545             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4546
4547           /* Likewise, if the intermediate and final types are either both
4548              float or both integer, we don't need the middle conversion if
4549              it is wider than the final type and doesn't change the signedness
4550              (for integers).  Avoid this if the final type is a pointer
4551              since then we sometimes need the inner conversion.  Likewise if
4552              the outer has a precision not equal to the size of its mode.  */
4553           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4554                || (inter_float && inside_float))
4555               && inter_prec >= inside_prec
4556               && (inter_float || inter_unsignedp == inside_unsignedp)
4557               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4558                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4559               && ! final_ptr)
4560             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4561
4562           /* If we have a sign-extension of a zero-extended value, we can
4563              replace that by a single zero-extension.  */
4564           if (inside_int && inter_int && final_int
4565               && inside_prec < inter_prec && inter_prec < final_prec
4566               && inside_unsignedp && !inter_unsignedp)
4567             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4568
4569           /* Two conversions in a row are not needed unless:
4570              - some conversion is floating-point (overstrict for now), or
4571              - the intermediate type is narrower than both initial and
4572                final, or
4573              - the intermediate type and innermost type differ in signedness,
4574                and the outermost type is wider than the intermediate, or
4575              - the initial type is a pointer type and the precisions of the
4576                intermediate and final types differ, or
4577              - the final type is a pointer type and the precisions of the
4578                initial and intermediate types differ.  */
4579           if (! inside_float && ! inter_float && ! final_float
4580               && (inter_prec > inside_prec || inter_prec > final_prec)
4581               && ! (inside_int && inter_int
4582                     && inter_unsignedp != inside_unsignedp
4583                     && inter_prec < final_prec)
4584               && ((inter_unsignedp && inter_prec > inside_prec)
4585                   == (final_unsignedp && final_prec > inter_prec))
4586               && ! (inside_ptr && inter_prec != final_prec)
4587               && ! (final_ptr && inside_prec != inter_prec)
4588               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4589                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4590               && ! final_ptr)
4591             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4592         }
4593
4594       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4595           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4596           /* Detect assigning a bitfield.  */
4597           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4598                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4599         {
4600           /* Don't leave an assignment inside a conversion
4601              unless assigning a bitfield.  */
4602           tree prev = TREE_OPERAND (t, 0);
4603           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4604           /* First do the assignment, then return converted constant.  */
4605           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4606           TREE_USED (t) = 1;
4607           return t;
4608         }
4609       if (!wins)
4610         {
4611           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4612           return t;
4613         }
4614       return fold_convert (t, arg0);
4615
4616 #if 0  /* This loses on &"foo"[0].  */
4617     case ARRAY_REF:
4618         {
4619           int i;
4620
4621           /* Fold an expression like: "foo"[2] */
4622           if (TREE_CODE (arg0) == STRING_CST
4623               && TREE_CODE (arg1) == INTEGER_CST
4624               && !TREE_INT_CST_HIGH (arg1)
4625               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4626             {
4627               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4628               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4629               force_fit_type (t, 0);
4630             }
4631         }
4632       return t;
4633 #endif /* 0 */
4634
4635     case COMPONENT_REF:
4636       if (TREE_CODE (arg0) == CONSTRUCTOR)
4637         {
4638           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4639           if (m)
4640             t = TREE_VALUE (m);
4641         }
4642       return t;
4643
4644     case RANGE_EXPR:
4645       TREE_CONSTANT (t) = wins;
4646       return t;
4647
4648     case NEGATE_EXPR:
4649       if (wins)
4650         {
4651           if (TREE_CODE (arg0) == INTEGER_CST)
4652             {
4653               HOST_WIDE_INT low, high;
4654               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4655                                          TREE_INT_CST_HIGH (arg0),
4656                                          &low, &high);
4657               t = build_int_2 (low, high);
4658               TREE_TYPE (t) = type;
4659               TREE_OVERFLOW (t)
4660                 = (TREE_OVERFLOW (arg0)
4661                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4662               TREE_CONSTANT_OVERFLOW (t)
4663                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4664             }
4665           else if (TREE_CODE (arg0) == REAL_CST)
4666             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4667         }
4668       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4669         return TREE_OPERAND (arg0, 0);
4670
4671       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4672       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4673         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4674                       TREE_OPERAND (arg0, 0));
4675
4676       return t;
4677
4678     case ABS_EXPR:
4679       if (wins)
4680         {
4681           if (TREE_CODE (arg0) == INTEGER_CST)
4682             {
4683               if (! TREE_UNSIGNED (type)
4684                   && TREE_INT_CST_HIGH (arg0) < 0)
4685                 {
4686                   HOST_WIDE_INT low, high;
4687                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4688                                              TREE_INT_CST_HIGH (arg0),
4689                                              &low, &high);
4690                   t = build_int_2 (low, high);
4691                   TREE_TYPE (t) = type;
4692                   TREE_OVERFLOW (t)
4693                     = (TREE_OVERFLOW (arg0)
4694                        | force_fit_type (t, overflow));
4695                   TREE_CONSTANT_OVERFLOW (t)
4696                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4697                 }
4698             }
4699           else if (TREE_CODE (arg0) == REAL_CST)
4700             {
4701               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4702                 t = build_real (type,
4703                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4704             }
4705         }
4706       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4707         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4708       return t;
4709
4710     case CONJ_EXPR:
4711       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4712         return arg0;
4713       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4714         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4715                       TREE_OPERAND (arg0, 0),
4716                       fold (build1 (NEGATE_EXPR,
4717                                     TREE_TYPE (TREE_TYPE (arg0)),
4718                                     TREE_OPERAND (arg0, 1))));
4719       else if (TREE_CODE (arg0) == COMPLEX_CST)
4720         return build_complex (type, TREE_OPERAND (arg0, 0),
4721                               fold (build1 (NEGATE_EXPR,
4722                                             TREE_TYPE (TREE_TYPE (arg0)),
4723                                             TREE_OPERAND (arg0, 1))));
4724       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4725         return fold (build (TREE_CODE (arg0), type,
4726                             fold (build1 (CONJ_EXPR, type,
4727                                           TREE_OPERAND (arg0, 0))),
4728                             fold (build1 (CONJ_EXPR,
4729                                           type, TREE_OPERAND (arg0, 1)))));
4730       else if (TREE_CODE (arg0) == CONJ_EXPR)
4731         return TREE_OPERAND (arg0, 0);
4732       return t;
4733
4734     case BIT_NOT_EXPR:
4735       if (wins)
4736         {
4737           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4738                            ~ TREE_INT_CST_HIGH (arg0));
4739           TREE_TYPE (t) = type;
4740           force_fit_type (t, 0);
4741           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4742           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4743         }
4744       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4745         return TREE_OPERAND (arg0, 0);
4746       return t;
4747
4748     case PLUS_EXPR:
4749       /* A + (-B) -> A - B */
4750       if (TREE_CODE (arg1) == NEGATE_EXPR)
4751         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4752       /* (-A) + B -> B - A */
4753       if (TREE_CODE (arg0) == NEGATE_EXPR)
4754         return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
4755       else if (! FLOAT_TYPE_P (type))
4756         {
4757           if (integer_zerop (arg1))
4758             return non_lvalue (convert (type, arg0));
4759
4760           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4761              with a constant, and the two constants have no bits in common,
4762              we should treat this as a BIT_IOR_EXPR since this may produce more
4763              simplifications.  */
4764           if (TREE_CODE (arg0) == BIT_AND_EXPR
4765               && TREE_CODE (arg1) == BIT_AND_EXPR
4766               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4767               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4768               && integer_zerop (const_binop (BIT_AND_EXPR,
4769                                              TREE_OPERAND (arg0, 1),
4770                                              TREE_OPERAND (arg1, 1), 0)))
4771             {
4772               code = BIT_IOR_EXPR;
4773               goto bit_ior;
4774             }
4775
4776           /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4777              (plus (plus (mult) (mult)) (foo)) so that we can
4778              take advantage of the factoring cases below.  */
4779           if ((TREE_CODE (arg0) == PLUS_EXPR
4780                && TREE_CODE (arg1) == MULT_EXPR)
4781               || (TREE_CODE (arg1) == PLUS_EXPR
4782                   && TREE_CODE (arg0) == MULT_EXPR))
4783             {
4784               tree parg0, parg1, parg, marg;
4785
4786               if (TREE_CODE (arg0) == PLUS_EXPR)
4787                 parg = arg0, marg = arg1;
4788               else
4789                 parg = arg1, marg = arg0;
4790               parg0 = TREE_OPERAND (parg, 0);
4791               parg1 = TREE_OPERAND (parg, 1);
4792               STRIP_NOPS (parg0);
4793               STRIP_NOPS (parg1);
4794
4795               if (TREE_CODE (parg0) == MULT_EXPR
4796                   && TREE_CODE (parg1) != MULT_EXPR)
4797                 return fold (build (PLUS_EXPR, type,
4798                                     fold (build (PLUS_EXPR, type, parg0, marg)),
4799                                     parg1));
4800               if (TREE_CODE (parg0) != MULT_EXPR
4801                   && TREE_CODE (parg1) == MULT_EXPR)
4802                 return fold (build (PLUS_EXPR, type,
4803                                     fold (build (PLUS_EXPR, type, parg1, marg)),
4804                                     parg0));
4805             }
4806
4807           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4808             {
4809               tree arg00, arg01, arg10, arg11;
4810               tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
4811
4812               /* (A * C) + (B * C) -> (A+B) * C.
4813                  We are most concerned about the case where C is a constant,
4814                  but other combinations show up during loop reduction.  Since
4815                  it is not difficult, try all four possibilities.  */
4816
4817               arg00 = TREE_OPERAND (arg0, 0);
4818               arg01 = TREE_OPERAND (arg0, 1);
4819               arg10 = TREE_OPERAND (arg1, 0);
4820               arg11 = TREE_OPERAND (arg1, 1);
4821               same = NULL_TREE;
4822
4823               if (operand_equal_p (arg01, arg11, 0))
4824                 same = arg01, alt0 = arg00, alt1 = arg10;
4825               else if (operand_equal_p (arg00, arg10, 0))
4826                 same = arg00, alt0 = arg01, alt1 = arg11;
4827               else if (operand_equal_p (arg00, arg11, 0))
4828                 same = arg00, alt0 = arg01, alt1 = arg10;
4829               else if (operand_equal_p (arg01, arg10, 0))
4830                 same = arg01, alt0 = arg00, alt1 = arg11;
4831
4832               /* No identical multiplicands; see if we can find a common
4833                  power-of-two factor in non-power-of-two multiplies.  This
4834                  can help in multi-dimensional array access.  */
4835               else if (TREE_CODE (arg01) == INTEGER_CST
4836                        && TREE_CODE (arg11) == INTEGER_CST
4837                        && TREE_INT_CST_HIGH (arg01) == 0
4838                        && TREE_INT_CST_HIGH (arg11) == 0)
4839                 {
4840                   HOST_WIDE_INT int01, int11, tmp;
4841                   int01 = TREE_INT_CST_LOW (arg01);
4842                   int11 = TREE_INT_CST_LOW (arg11);
4843
4844                   /* Move min of absolute values to int11.  */
4845                   if ((int01 >= 0 ? int01 : -int01)
4846                       < (int11 >= 0 ? int11 : -int11))
4847                     {
4848                       tmp = int01, int01 = int11, int11 = tmp;
4849                       alt0 = arg00, arg00 = arg10, arg10 = alt0;
4850                       alt0 = arg01, arg01 = arg11, arg11 = alt0;
4851                     }
4852
4853                   if (exact_log2 (int11) > 0 && int01 % int11 == 0)
4854                     {
4855                       alt0 = fold (build (MULT_EXPR, type, arg00,
4856                                           build_int_2 (int01 / int11, 0)));
4857                       alt1 = arg10;
4858                       same = arg11;
4859                     }
4860                 }
4861
4862               if (same)
4863                 return fold (build (MULT_EXPR, type,
4864                                     fold (build (PLUS_EXPR, type, alt0, alt1)),
4865                                     same));
4866             }
4867         }
4868       /* In IEEE floating point, x+0 may not equal x.  */
4869       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4870                 || flag_fast_math)
4871                && real_zerop (arg1))
4872         return non_lvalue (convert (type, arg0));
4873       /* x+(-0) equals x, even for IEEE.  */
4874       else if (TREE_CODE (arg1) == REAL_CST
4875                && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
4876         return non_lvalue (convert (type, arg0));
4877
4878      bit_rotate:
4879       /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
4880          is a rotate of A by C1 bits.  */
4881       /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
4882          is a rotate of A by B bits.  */
4883       {
4884         register enum tree_code code0, code1;
4885         code0 = TREE_CODE (arg0);
4886         code1 = TREE_CODE (arg1);
4887         if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4888             || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4889             && operand_equal_p (TREE_OPERAND (arg0, 0),
4890                                 TREE_OPERAND (arg1,0), 0)
4891             && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4892           {
4893             register tree tree01, tree11;
4894             register enum tree_code code01, code11;
4895
4896             tree01 = TREE_OPERAND (arg0, 1);
4897             tree11 = TREE_OPERAND (arg1, 1);
4898             STRIP_NOPS (tree01);
4899             STRIP_NOPS (tree11);
4900             code01 = TREE_CODE (tree01);
4901             code11 = TREE_CODE (tree11);
4902             if (code01 == INTEGER_CST
4903               && code11 == INTEGER_CST
4904               && TREE_INT_CST_HIGH (tree01) == 0
4905               && TREE_INT_CST_HIGH (tree11) == 0
4906               && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4907                 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4908               return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4909                         code0 == LSHIFT_EXPR ? tree01 : tree11);
4910             else if (code11 == MINUS_EXPR)
4911               {
4912                 tree tree110, tree111;
4913                 tree110 = TREE_OPERAND (tree11, 0);
4914                 tree111 = TREE_OPERAND (tree11, 1);
4915                 STRIP_NOPS (tree110);
4916                 STRIP_NOPS (tree111);
4917                 if (TREE_CODE (tree110) == INTEGER_CST
4918                     && TREE_INT_CST_HIGH (tree110) == 0
4919                     && (TREE_INT_CST_LOW (tree110)
4920                         == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4921                     && operand_equal_p (tree01, tree111, 0))
4922                   return build ((code0 == LSHIFT_EXPR
4923                                  ? LROTATE_EXPR
4924                                  : RROTATE_EXPR),
4925                                 type, TREE_OPERAND (arg0, 0), tree01);
4926               }
4927             else if (code01 == MINUS_EXPR)
4928               {
4929                 tree tree010, tree011;
4930                 tree010 = TREE_OPERAND (tree01, 0);
4931                 tree011 = TREE_OPERAND (tree01, 1);
4932                 STRIP_NOPS (tree010);
4933                 STRIP_NOPS (tree011);
4934                 if (TREE_CODE (tree010) == INTEGER_CST
4935                     && TREE_INT_CST_HIGH (tree010) == 0
4936                     && (TREE_INT_CST_LOW (tree010)
4937                         == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4938                     && operand_equal_p (tree11, tree011, 0))
4939                   return build ((code0 != LSHIFT_EXPR
4940                                  ? LROTATE_EXPR
4941                                  : RROTATE_EXPR),
4942                                  type, TREE_OPERAND (arg0, 0), tree11);
4943               }
4944           }
4945       }
4946
4947     associate:
4948       /* In most languages, can't associate operations on floats
4949          through parentheses.  Rather than remember where the parentheses
4950          were, we don't associate floats at all.  It shouldn't matter much.
4951          However, associating multiplications is only very slightly
4952          inaccurate, so do that if -ffast-math is specified.  */
4953       if (FLOAT_TYPE_P (type)
4954           && ! (flag_fast_math && code == MULT_EXPR))
4955         goto binary;
4956
4957       /* The varsign == -1 cases happen only for addition and subtraction.
4958          It says that the arg that was split was really CON minus VAR.
4959          The rest of the code applies to all associative operations.  */
4960       if (!wins)
4961         {
4962           tree var, con;
4963           int varsign;
4964
4965           if (split_tree (arg0, code, &var, &con, &varsign))
4966             {
4967               if (varsign == -1)
4968                 {
4969                   /* EXPR is (CON-VAR) +- ARG1.  */
4970                   /* If it is + and VAR==ARG1, return just CONST.  */
4971                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4972                     return convert (TREE_TYPE (t), con);
4973
4974                   /* If ARG0 is a constant, don't change things around;
4975                      instead keep all the constant computations together.  */
4976
4977                   if (TREE_CONSTANT (arg0))
4978                     return t;
4979
4980                   /* Otherwise return (CON +- ARG1) - VAR.  */
4981                   t = build (MINUS_EXPR, type,
4982                              fold (build (code, type, con, arg1)), var);
4983                 }
4984               else
4985                 {
4986                   /* EXPR is (VAR+CON) +- ARG1.  */
4987                   /* If it is - and VAR==ARG1, return just CONST.  */
4988                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4989                     return convert (TREE_TYPE (t), con);
4990
4991                   /* If ARG0 is a constant, don't change things around;
4992                      instead keep all the constant computations together.  */
4993
4994                   if (TREE_CONSTANT (arg0))
4995                     return t;
4996
4997                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4998                   tem = fold (build (code, type, arg1, con));
4999                   t = build (code, type, var, tem);
5000
5001                   if (integer_zerop (tem)
5002                       && (code == PLUS_EXPR || code == MINUS_EXPR))
5003                     return convert (type, var);
5004                   /* If we have x +/- (c - d) [c an explicit integer]
5005                      change it to x -/+ (d - c) since if d is relocatable
5006                      then the latter can be a single immediate insn
5007                      and the former cannot.  */
5008                   if (TREE_CODE (tem) == MINUS_EXPR
5009                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
5010                     {
5011                       tree tem1 = TREE_OPERAND (tem, 1);
5012                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
5013                       TREE_OPERAND (tem, 0) = tem1;
5014                       TREE_SET_CODE (t,
5015                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
5016                     }
5017                 }
5018               return t;
5019             }
5020
5021           if (split_tree (arg1, code, &var, &con, &varsign))
5022             {
5023               if (TREE_CONSTANT (arg1))
5024                 return t;
5025
5026               if (varsign == -1)
5027                 TREE_SET_CODE (t,
5028                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
5029
5030               /* EXPR is ARG0 +- (CON +- VAR).  */
5031               if (TREE_CODE (t) == MINUS_EXPR
5032                   && operand_equal_p (var, arg0, 0))
5033                 {
5034                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
5035                   if (code == PLUS_EXPR)
5036                     return convert (TREE_TYPE (t), con);
5037                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
5038                                        convert (TREE_TYPE (t), con)));
5039                 }
5040
5041               t = build (TREE_CODE (t), type,
5042                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
5043
5044               if (integer_zerop (TREE_OPERAND (t, 0))
5045                   && TREE_CODE (t) == PLUS_EXPR)
5046                 return convert (TREE_TYPE (t), var);
5047               return t;
5048             }
5049         }
5050     binary:
5051 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
5052       if (TREE_CODE (arg1) == REAL_CST)
5053         return t;
5054 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
5055       if (wins)
5056         t1 = const_binop (code, arg0, arg1, 0);
5057       if (t1 != NULL_TREE)
5058         {
5059           /* The return value should always have
5060              the same type as the original expression.  */
5061           if (TREE_TYPE (t1) != TREE_TYPE (t))
5062             t1 = convert (TREE_TYPE (t), t1);
5063
5064           return t1;
5065         }
5066       return t;
5067
5068     case MINUS_EXPR:
5069       /* A - (-B) -> A + B */
5070       if (TREE_CODE (arg1) == NEGATE_EXPR)
5071         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5072       /* (-A) - CST -> (-CST) - A   for floating point (what about ints ?)  */
5073       if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5074         return
5075           fold (build (MINUS_EXPR, type,
5076                        build_real (TREE_TYPE (arg1),
5077                                    REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5078                        TREE_OPERAND (arg0, 0)));
5079
5080       if (! FLOAT_TYPE_P (type))
5081         {
5082           if (! wins && integer_zerop (arg0))
5083             return build1 (NEGATE_EXPR, type, arg1);
5084           if (integer_zerop (arg1))
5085             return non_lvalue (convert (type, arg0));
5086
5087           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
5088              about the case where C is a constant, just try one of the
5089              four possibilities.  */
5090
5091           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5092               && operand_equal_p (TREE_OPERAND (arg0, 1),
5093                                   TREE_OPERAND (arg1, 1), 0))
5094             return fold (build (MULT_EXPR, type,
5095                                 fold (build (MINUS_EXPR, type,
5096                                              TREE_OPERAND (arg0, 0),
5097                                              TREE_OPERAND (arg1, 0))),
5098                                 TREE_OPERAND (arg0, 1)));
5099         }
5100
5101       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5102                || flag_fast_math)
5103         {
5104           /* Except with IEEE floating point, 0-x equals -x.  */
5105           if (! wins && real_zerop (arg0))
5106             return build1 (NEGATE_EXPR, type, arg1);
5107           /* Except with IEEE floating point, x-0 equals x.  */
5108           if (real_zerop (arg1))
5109             return non_lvalue (convert (type, arg0));
5110         }
5111
5112       /* Fold &x - &x.  This can happen from &x.foo - &x.
5113          This is unsafe for certain floats even in non-IEEE formats.
5114          In IEEE, it is unsafe because it does wrong for NaNs.
5115          Also note that operand_equal_p is always false if an operand
5116          is volatile.  */
5117
5118       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
5119           && operand_equal_p (arg0, arg1, 0))
5120         return convert (type, integer_zero_node);
5121
5122       goto associate;
5123
5124     case MULT_EXPR:
5125       /* (-A) * (-B) -> A * B  */
5126       if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5127         return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5128                             TREE_OPERAND (arg1, 0)));
5129
5130       if (! FLOAT_TYPE_P (type))
5131         {
5132           if (integer_zerop (arg1))
5133             return omit_one_operand (type, arg1, arg0);
5134           if (integer_onep (arg1))
5135             return non_lvalue (convert (type, arg0));
5136
5137           /* ((A / C) * C) is A if the division is an
5138              EXACT_DIV_EXPR.   Since C is normally a constant,
5139              just check for one of the four possibilities.  */
5140
5141           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
5142               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5143             return TREE_OPERAND (arg0, 0);
5144
5145           /* (a * (1 << b)) is (a << b)  */
5146           if (TREE_CODE (arg1) == LSHIFT_EXPR
5147               && integer_onep (TREE_OPERAND (arg1, 0)))
5148             return fold (build (LSHIFT_EXPR, type, arg0,
5149                                 TREE_OPERAND (arg1, 1)));
5150           if (TREE_CODE (arg0) == LSHIFT_EXPR
5151               && integer_onep (TREE_OPERAND (arg0, 0)))
5152             return fold (build (LSHIFT_EXPR, type, arg1,
5153                                 TREE_OPERAND (arg0, 1)));
5154         }
5155       else
5156         {
5157           /* x*0 is 0, except for IEEE floating point.  */
5158           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5159                || flag_fast_math)
5160               && real_zerop (arg1))
5161             return omit_one_operand (type, arg1, arg0);
5162           /* In IEEE floating point, x*1 is not equivalent to x for snans.
5163              However, ANSI says we can drop signals,
5164              so we can do this anyway.  */
5165           if (real_onep (arg1))
5166             return non_lvalue (convert (type, arg0));
5167           /* x*2 is x+x */
5168           if (! wins && real_twop (arg1) && global_bindings_p () == 0
5169               && ! contains_placeholder_p (arg0))
5170             {
5171               tree arg = save_expr (arg0);
5172               return build (PLUS_EXPR, type, arg, arg);
5173             }
5174         }
5175       goto associate;
5176
5177     case BIT_IOR_EXPR:
5178     bit_ior:
5179       if (integer_all_onesp (arg1))
5180         return omit_one_operand (type, arg1, arg0);
5181       if (integer_zerop (arg1))
5182         return non_lvalue (convert (type, arg0));
5183       t1 = distribute_bit_expr (code, type, arg0, arg1);
5184       if (t1 != NULL_TREE)
5185         return t1;
5186
5187       /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5188
5189          This results in more efficient code for machines without a NAND
5190          instruction.  Combine will canonicalize to the first form
5191          which will allow use of NAND instructions provided by the
5192          backend if they exist.  */
5193       if (TREE_CODE (arg0) == BIT_NOT_EXPR
5194           && TREE_CODE (arg1) == BIT_NOT_EXPR)
5195         {
5196           return fold (build1 (BIT_NOT_EXPR, type,
5197                                build (BIT_AND_EXPR, type,
5198                                       TREE_OPERAND (arg0, 0),
5199                                       TREE_OPERAND (arg1, 0))));
5200         }
5201
5202       /* See if this can be simplified into a rotate first.  If that
5203          is unsuccessful continue in the association code.  */
5204       goto bit_rotate;
5205
5206     case BIT_XOR_EXPR:
5207       if (integer_zerop (arg1))
5208         return non_lvalue (convert (type, arg0));
5209       if (integer_all_onesp (arg1))
5210         return fold (build1 (BIT_NOT_EXPR, type, arg0));
5211
5212       /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5213          with a constant, and the two constants have no bits in common,
5214          we should treat this as a BIT_IOR_EXPR since this may produce more
5215          simplifications.  */
5216       if (TREE_CODE (arg0) == BIT_AND_EXPR
5217           && TREE_CODE (arg1) == BIT_AND_EXPR
5218           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5219           && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5220           && integer_zerop (const_binop (BIT_AND_EXPR,
5221                                          TREE_OPERAND (arg0, 1),
5222                                          TREE_OPERAND (arg1, 1), 0)))
5223         {
5224            code = BIT_IOR_EXPR;
5225            goto bit_ior;
5226         }
5227
5228       /* See if this can be simplified into a rotate first.  If that
5229          is unsuccessful continue in the association code.  */
5230       goto bit_rotate;
5231
5232     case BIT_AND_EXPR:
5233     bit_and:
5234       if (integer_all_onesp (arg1))
5235         return non_lvalue (convert (type, arg0));
5236       if (integer_zerop (arg1))
5237         return omit_one_operand (type, arg1, arg0);
5238       t1 = distribute_bit_expr (code, type, arg0, arg1);
5239       if (t1 != NULL_TREE)
5240         return t1;
5241       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
5242       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5243           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5244         {
5245           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5246           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5247               && (~TREE_INT_CST_LOW (arg0)
5248                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5249             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5250         }
5251       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5252           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5253         {
5254           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5255           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5256               && (~TREE_INT_CST_LOW (arg1)
5257                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5258             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5259         }
5260
5261       /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5262
5263          This results in more efficient code for machines without a NOR
5264          instruction.  Combine will canonicalize to the first form
5265          which will allow use of NOR instructions provided by the
5266          backend if they exist.  */
5267       if (TREE_CODE (arg0) == BIT_NOT_EXPR
5268           && TREE_CODE (arg1) == BIT_NOT_EXPR)
5269         {
5270           return fold (build1 (BIT_NOT_EXPR, type,
5271                                build (BIT_IOR_EXPR, type,
5272                                       TREE_OPERAND (arg0, 0),
5273                                       TREE_OPERAND (arg1, 0))));
5274         }
5275
5276       goto associate;
5277
5278     case BIT_ANDTC_EXPR:
5279       if (integer_all_onesp (arg0))
5280         return non_lvalue (convert (type, arg1));
5281       if (integer_zerop (arg0))
5282         return omit_one_operand (type, arg0, arg1);
5283       if (TREE_CODE (arg1) == INTEGER_CST)
5284         {
5285           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5286           code = BIT_AND_EXPR;
5287           goto bit_and;
5288         }
5289       goto binary;
5290
5291     case RDIV_EXPR:
5292       /* In most cases, do nothing with a divide by zero.  */
5293 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
5294 #ifndef REAL_INFINITY
5295       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
5296         return t;
5297 #endif
5298 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
5299
5300       /* (-A) / (-B) -> A / B  */
5301       if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5302         return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5303                             TREE_OPERAND (arg1, 0)));
5304
5305       /* In IEEE floating point, x/1 is not equivalent to x for snans.
5306          However, ANSI says we can drop signals, so we can do this anyway.  */
5307       if (real_onep (arg1))
5308         return non_lvalue (convert (type, arg0));
5309
5310       /* If ARG1 is a constant, we can convert this to a multiply by the
5311          reciprocal.  This does not have the same rounding properties,
5312          so only do this if -ffast-math.  We can actually always safely
5313          do it if ARG1 is a power of two, but it's hard to tell if it is
5314          or not in a portable manner.  */
5315       if (TREE_CODE (arg1) == REAL_CST)
5316         {
5317           if (flag_fast_math
5318               && 0 != (tem = const_binop (code, build_real (type, dconst1),
5319                                           arg1, 0)))
5320             return fold (build (MULT_EXPR, type, arg0, tem));
5321           /* Find the reciprocal if optimizing and the result is exact. */
5322           else if (optimize)
5323             {
5324               REAL_VALUE_TYPE r;
5325               r = TREE_REAL_CST (arg1);
5326               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5327                   {
5328                     tem = build_real (type, r);
5329                     return fold (build (MULT_EXPR, type, arg0, tem));
5330                   }
5331             }
5332         }
5333       goto binary;
5334
5335     case TRUNC_DIV_EXPR:
5336     case ROUND_DIV_EXPR:
5337     case FLOOR_DIV_EXPR:
5338     case CEIL_DIV_EXPR:
5339     case EXACT_DIV_EXPR:
5340       if (integer_onep (arg1))
5341         return non_lvalue (convert (type, arg0));
5342       if (integer_zerop (arg1))
5343         return t;
5344
5345       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5346          operation, EXACT_DIV_EXPR.
5347
5348          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5349          At one time others generated faster code, it's not clear if they do
5350          after the last round to changes to the DIV code in expmed.c.  */
5351       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5352           && multiple_of_p (type, arg0, arg1))
5353         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5354
5355       /* If we have ((a / C1) / C2) where both division are the same type, try
5356          to simplify.  First see if C1 * C2 overflows or not.  */
5357       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
5358           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5359         {
5360           tree new_divisor;
5361
5362           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
5363           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
5364
5365           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
5366               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
5367             {
5368               /* If no overflow, divide by C1*C2.  */
5369               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
5370             }
5371         }
5372
5373       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
5374          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
5375          expressions, which often appear in the offsets or sizes of
5376          objects with a varying size.  Only deal with positive divisors
5377          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
5378
5379          Look for NOPs and SAVE_EXPRs inside.  */
5380
5381       if (TREE_CODE (arg1) == INTEGER_CST
5382           && tree_int_cst_sgn (arg1) >= 0)
5383         {
5384           int have_save_expr = 0;
5385           tree c2 = integer_zero_node;
5386           tree xarg0 = arg0;
5387
5388           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5389             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5390
5391           STRIP_NOPS (xarg0);
5392
5393           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
5394              if possible.  */
5395           if (TREE_CODE (xarg0) == MULT_EXPR
5396               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
5397             {
5398               tree t;
5399
5400               t = fold (build (MULT_EXPR, type,
5401                                fold (build (EXACT_DIV_EXPR, type,
5402                                             TREE_OPERAND (xarg0, 0), arg1)),
5403                                TREE_OPERAND (xarg0, 1)));
5404               if (have_save_expr)
5405                 t = save_expr (t);
5406               return t;
5407
5408             }
5409
5410           if (TREE_CODE (xarg0) == MULT_EXPR
5411               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
5412             {
5413               tree t;
5414
5415               t = fold (build (MULT_EXPR, type,
5416                                fold (build (EXACT_DIV_EXPR, type,
5417                                             TREE_OPERAND (xarg0, 1), arg1)),
5418                                TREE_OPERAND (xarg0, 0)));
5419               if (have_save_expr)
5420                 t = save_expr (t);
5421               return t;
5422             }
5423
5424           if (TREE_CODE (xarg0) == PLUS_EXPR
5425               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5426             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5427           else if (TREE_CODE (xarg0) == MINUS_EXPR
5428                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5429                    /* If we are doing this computation unsigned, the negate
5430                       is incorrect.  */
5431                    && ! TREE_UNSIGNED (type))
5432             {
5433               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5434               xarg0 = TREE_OPERAND (xarg0, 0);
5435             }
5436
5437           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5438             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5439
5440           STRIP_NOPS (xarg0);
5441
5442           if (TREE_CODE (xarg0) == MULT_EXPR
5443               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5444               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
5445               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
5446                                               TREE_OPERAND (xarg0, 1), arg1, 1))
5447                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
5448                                                  TREE_OPERAND (xarg0, 1), 1)))
5449               && (tree_int_cst_sgn (c2) >= 0
5450                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
5451                                                  arg1, 1))))
5452             {
5453               tree outer_div = integer_one_node;
5454               tree c1 = TREE_OPERAND (xarg0, 1);
5455               tree c3 = arg1;
5456
5457               /* If C3 > C1, set them equal and do a divide by
5458                  C3/C1 at the end of the operation.  */
5459               if (tree_int_cst_lt (c1, c3))
5460                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
5461
5462               /* The result is A * (C1/C3) + (C2/C3).  */
5463               t = fold (build (PLUS_EXPR, type,
5464                                fold (build (MULT_EXPR, type,
5465                                             TREE_OPERAND (xarg0, 0),
5466                                             const_binop (code, c1, c3, 1))),
5467                                const_binop (code, c2, c3, 1)));
5468
5469               if (! integer_onep (outer_div))
5470                 t = fold (build (code, type, t, convert (type, outer_div)));
5471
5472               if (have_save_expr)
5473                 t = save_expr (t);
5474
5475               return t;
5476             }
5477         }
5478
5479       goto binary;
5480
5481     case CEIL_MOD_EXPR:
5482     case FLOOR_MOD_EXPR:
5483     case ROUND_MOD_EXPR:
5484     case TRUNC_MOD_EXPR:
5485       if (integer_onep (arg1))
5486         return omit_one_operand (type, integer_zero_node, arg0);
5487       if (integer_zerop (arg1))
5488         return t;
5489
5490       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
5491          where C1 % C3 == 0.  Handle similarly to the division case,
5492          but don't bother with SAVE_EXPRs.  */
5493
5494       if (TREE_CODE (arg1) == INTEGER_CST
5495           && ! integer_zerop (arg1))
5496         {
5497           tree c2 = integer_zero_node;
5498           tree xarg0 = arg0;
5499
5500           if (TREE_CODE (xarg0) == PLUS_EXPR
5501               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5502             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5503           else if (TREE_CODE (xarg0) == MINUS_EXPR
5504                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5505                    && ! TREE_UNSIGNED (type))
5506             {
5507               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5508               xarg0 = TREE_OPERAND (xarg0, 0);
5509             }
5510
5511           STRIP_NOPS (xarg0);
5512
5513           if (TREE_CODE (xarg0) == MULT_EXPR
5514               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5515               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
5516                                              TREE_OPERAND (xarg0, 1),
5517                                              arg1, 1))
5518               && tree_int_cst_sgn (c2) >= 0)
5519             /* The result is (C2%C3).  */
5520             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
5521                                      TREE_OPERAND (xarg0, 0));
5522         }
5523
5524       goto binary;
5525
5526     case LSHIFT_EXPR:
5527     case RSHIFT_EXPR:
5528     case LROTATE_EXPR:
5529     case RROTATE_EXPR:
5530       if (integer_zerop (arg1))
5531         return non_lvalue (convert (type, arg0));
5532       /* Since negative shift count is not well-defined,
5533          don't try to compute it in the compiler.  */
5534       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5535         return t;
5536       /* Rewrite an LROTATE_EXPR by a constant into an
5537          RROTATE_EXPR by a new constant.  */
5538       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5539         {
5540           TREE_SET_CODE (t, RROTATE_EXPR);
5541           code = RROTATE_EXPR;
5542           TREE_OPERAND (t, 1) = arg1
5543             = const_binop
5544               (MINUS_EXPR,
5545                convert (TREE_TYPE (arg1),
5546                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5547                arg1, 0);
5548           if (tree_int_cst_sgn (arg1) < 0)
5549             return t;
5550         }
5551
5552       /* If we have a rotate of a bit operation with the rotate count and
5553          the second operand of the bit operation both constant,
5554          permute the two operations.  */
5555       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5556           && (TREE_CODE (arg0) == BIT_AND_EXPR
5557               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5558               || TREE_CODE (arg0) == BIT_IOR_EXPR
5559               || TREE_CODE (arg0) == BIT_XOR_EXPR)
5560           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5561         return fold (build (TREE_CODE (arg0), type,
5562                             fold (build (code, type,
5563                                          TREE_OPERAND (arg0, 0), arg1)),
5564                             fold (build (code, type,
5565                                          TREE_OPERAND (arg0, 1), arg1))));
5566
5567       /* Two consecutive rotates adding up to the width of the mode can
5568          be ignored.  */
5569       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5570           && TREE_CODE (arg0) == RROTATE_EXPR
5571           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5572           && TREE_INT_CST_HIGH (arg1) == 0
5573           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5574           && ((TREE_INT_CST_LOW (arg1)
5575                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5576               == GET_MODE_BITSIZE (TYPE_MODE (type))))
5577         return TREE_OPERAND (arg0, 0);
5578
5579       goto binary;
5580
5581     case MIN_EXPR:
5582       if (operand_equal_p (arg0, arg1, 0))
5583         return arg0;
5584       if (INTEGRAL_TYPE_P (type)
5585           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5586         return omit_one_operand (type, arg1, arg0);
5587       goto associate;
5588
5589     case MAX_EXPR:
5590       if (operand_equal_p (arg0, arg1, 0))
5591         return arg0;
5592       if (INTEGRAL_TYPE_P (type)
5593           && TYPE_MAX_VALUE (type)
5594           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5595         return omit_one_operand (type, arg1, arg0);
5596       goto associate;
5597
5598     case TRUTH_NOT_EXPR:
5599       /* Note that the operand of this must be an int
5600          and its values must be 0 or 1.
5601          ("true" is a fixed value perhaps depending on the language,
5602          but we don't handle values other than 1 correctly yet.)  */
5603       tem = invert_truthvalue (arg0);
5604       /* Avoid infinite recursion.  */
5605       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5606         return t;
5607       return convert (type, tem);
5608
5609     case TRUTH_ANDIF_EXPR:
5610       /* Note that the operands of this must be ints
5611          and their values must be 0 or 1.
5612          ("true" is a fixed value perhaps depending on the language.)  */
5613       /* If first arg is constant zero, return it.  */
5614       if (integer_zerop (arg0))
5615         return arg0;
5616     case TRUTH_AND_EXPR:
5617       /* If either arg is constant true, drop it.  */
5618       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5619         return non_lvalue (arg1);
5620       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5621         return non_lvalue (arg0);
5622       /* If second arg is constant zero, result is zero, but first arg
5623          must be evaluated.  */
5624       if (integer_zerop (arg1))
5625         return omit_one_operand (type, arg1, arg0);
5626       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5627          case will be handled here.  */
5628       if (integer_zerop (arg0))
5629         return omit_one_operand (type, arg0, arg1);
5630
5631     truth_andor:
5632       /* We only do these simplifications if we are optimizing.  */
5633       if (!optimize)
5634         return t;
5635
5636       /* Check for things like (A || B) && (A || C).  We can convert this
5637          to A || (B && C).  Note that either operator can be any of the four
5638          truth and/or operations and the transformation will still be
5639          valid.   Also note that we only care about order for the
5640          ANDIF and ORIF operators.  If B contains side effects, this
5641          might change the truth-value of A. */
5642       if (TREE_CODE (arg0) == TREE_CODE (arg1)
5643           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5644               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5645               || TREE_CODE (arg0) == TRUTH_AND_EXPR
5646               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5647           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5648         {
5649           tree a00 = TREE_OPERAND (arg0, 0);
5650           tree a01 = TREE_OPERAND (arg0, 1);
5651           tree a10 = TREE_OPERAND (arg1, 0);
5652           tree a11 = TREE_OPERAND (arg1, 1);
5653           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5654                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5655                              && (code == TRUTH_AND_EXPR
5656                                  || code == TRUTH_OR_EXPR));
5657
5658           if (operand_equal_p (a00, a10, 0))
5659             return fold (build (TREE_CODE (arg0), type, a00,
5660                                 fold (build (code, type, a01, a11))));
5661           else if (commutative && operand_equal_p (a00, a11, 0))
5662             return fold (build (TREE_CODE (arg0), type, a00,
5663                                 fold (build (code, type, a01, a10))));
5664           else if (commutative && operand_equal_p (a01, a10, 0))
5665             return fold (build (TREE_CODE (arg0), type, a01,
5666                                 fold (build (code, type, a00, a11))));
5667
5668           /* This case if tricky because we must either have commutative
5669              operators or else A10 must not have side-effects.  */
5670
5671           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5672                    && operand_equal_p (a01, a11, 0))
5673             return fold (build (TREE_CODE (arg0), type,
5674                                 fold (build (code, type, a00, a10)),
5675                                 a01));
5676         }
5677
5678       /* See if we can build a range comparison.  */
5679       if (0 != (tem = fold_range_test (t)))
5680         return tem;
5681
5682       /* Check for the possibility of merging component references.  If our
5683          lhs is another similar operation, try to merge its rhs with our
5684          rhs.  Then try to merge our lhs and rhs.  */
5685       if (TREE_CODE (arg0) == code
5686           && 0 != (tem = fold_truthop (code, type,
5687                                        TREE_OPERAND (arg0, 1), arg1)))
5688         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5689
5690       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5691         return tem;
5692
5693       return t;
5694
5695     case TRUTH_ORIF_EXPR:
5696       /* Note that the operands of this must be ints
5697          and their values must be 0 or true.
5698          ("true" is a fixed value perhaps depending on the language.)  */
5699       /* If first arg is constant true, return it.  */
5700       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5701         return arg0;
5702     case TRUTH_OR_EXPR:
5703       /* If either arg is constant zero, drop it.  */
5704       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5705         return non_lvalue (arg1);
5706       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5707         return non_lvalue (arg0);
5708       /* If second arg is constant true, result is true, but we must
5709          evaluate first arg.  */
5710       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5711         return omit_one_operand (type, arg1, arg0);
5712       /* Likewise for first arg, but note this only occurs here for
5713          TRUTH_OR_EXPR.  */
5714       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5715         return omit_one_operand (type, arg0, arg1);
5716       goto truth_andor;
5717
5718     case TRUTH_XOR_EXPR:
5719       /* If either arg is constant zero, drop it.  */
5720       if (integer_zerop (arg0))
5721         return non_lvalue (arg1);
5722       if (integer_zerop (arg1))
5723         return non_lvalue (arg0);
5724       /* If either arg is constant true, this is a logical inversion.  */
5725       if (integer_onep (arg0))
5726         return non_lvalue (invert_truthvalue (arg1));
5727       if (integer_onep (arg1))
5728         return non_lvalue (invert_truthvalue (arg0));
5729       return t;
5730
5731     case EQ_EXPR:
5732     case NE_EXPR:
5733     case LT_EXPR:
5734     case GT_EXPR:
5735     case LE_EXPR:
5736     case GE_EXPR:
5737       if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5738         {
5739           /* (-a) CMP (-b) -> b CMP a  */
5740           if (TREE_CODE (arg0) == NEGATE_EXPR
5741               && TREE_CODE (arg1) == NEGATE_EXPR)
5742             return fold (build (code, type, TREE_OPERAND (arg1, 0),
5743                                 TREE_OPERAND (arg0, 0)));
5744           /* (-a) CMP CST -> a swap(CMP) (-CST)  */
5745           if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5746             return
5747               fold (build
5748                      (swap_tree_comparison (code), type,
5749                       TREE_OPERAND (arg0, 0),
5750                       build_real (TREE_TYPE (arg1),
5751                                   REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5752           /* IEEE doesn't distinguish +0 and -0 in comparisons.  */
5753           /* a CMP (-0) -> a CMP 0  */
5754           if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5755             return fold (build (code, type, arg0,
5756                                 build_real (TREE_TYPE (arg1), dconst0)));
5757         }
5758
5759
5760       /* If one arg is a constant integer, put it last.  */
5761       if (TREE_CODE (arg0) == INTEGER_CST
5762           && TREE_CODE (arg1) != INTEGER_CST)
5763         {
5764           TREE_OPERAND (t, 0) = arg1;
5765           TREE_OPERAND (t, 1) = arg0;
5766           arg0 = TREE_OPERAND (t, 0);
5767           arg1 = TREE_OPERAND (t, 1);
5768           code = swap_tree_comparison (code);
5769           TREE_SET_CODE (t, code);
5770         }
5771
5772       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5773          First, see if one arg is constant; find the constant arg
5774          and the other one.  */
5775       {
5776         tree constop = 0, varop = NULL_TREE;
5777         int constopnum = -1;
5778
5779         if (TREE_CONSTANT (arg1))
5780           constopnum = 1, constop = arg1, varop = arg0;
5781         if (TREE_CONSTANT (arg0))
5782           constopnum = 0, constop = arg0, varop = arg1;
5783
5784         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5785           {
5786             /* This optimization is invalid for ordered comparisons
5787                if CONST+INCR overflows or if foo+incr might overflow.
5788                This optimization is invalid for floating point due to rounding.
5789                For pointer types we assume overflow doesn't happen.  */
5790             if (POINTER_TYPE_P (TREE_TYPE (varop))
5791                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5792                     && (code == EQ_EXPR || code == NE_EXPR)))
5793               {
5794                 tree newconst
5795                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5796                                  constop, TREE_OPERAND (varop, 1)));
5797                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5798
5799                 /* If VAROP is a reference to a bitfield, we must mask
5800                    the constant by the width of the field.  */
5801                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5802                     && DECL_BIT_FIELD(TREE_OPERAND
5803                                       (TREE_OPERAND (varop, 0), 1)))
5804                   {
5805                     int size
5806                       = TREE_INT_CST_LOW (DECL_SIZE
5807                                           (TREE_OPERAND
5808                                            (TREE_OPERAND (varop, 0), 1)));
5809                     tree mask, unsigned_type;
5810                     int precision;
5811                     tree folded_compare;
5812
5813                     /* First check whether the comparison would come out
5814                        always the same.  If we don't do that we would
5815                        change the meaning with the masking.  */
5816                     if (constopnum == 0)
5817                       folded_compare = fold (build (code, type, constop,
5818                                                     TREE_OPERAND (varop, 0)));
5819                     else
5820                       folded_compare = fold (build (code, type,
5821                                                     TREE_OPERAND (varop, 0),
5822                                                     constop));
5823                     if (integer_zerop (folded_compare)
5824                         || integer_onep (folded_compare))
5825                       return omit_one_operand (type, folded_compare, varop);
5826
5827                     unsigned_type = type_for_size (size, 1);
5828                     precision = TYPE_PRECISION (unsigned_type);
5829                     mask = build_int_2 (~0, ~0);
5830                     TREE_TYPE (mask) = unsigned_type;
5831                     force_fit_type (mask, 0);
5832                     mask = const_binop (RSHIFT_EXPR, mask,
5833                                         size_int (precision - size), 0);
5834                     newconst = fold (build (BIT_AND_EXPR,
5835                                             TREE_TYPE (varop), newconst,
5836                                             convert (TREE_TYPE (varop),
5837                                                      mask)));
5838                   }
5839
5840
5841                 t = build (code, type, TREE_OPERAND (t, 0),
5842                            TREE_OPERAND (t, 1));
5843                 TREE_OPERAND (t, constopnum) = newconst;
5844                 return t;
5845               }
5846           }
5847         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5848           {
5849             if (POINTER_TYPE_P (TREE_TYPE (varop))
5850                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5851                     && (code == EQ_EXPR || code == NE_EXPR)))
5852               {
5853                 tree newconst
5854                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5855                                  constop, TREE_OPERAND (varop, 1)));
5856                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5857
5858                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5859                     && DECL_BIT_FIELD(TREE_OPERAND
5860                                       (TREE_OPERAND (varop, 0), 1)))
5861                   {
5862                     int size
5863                       = TREE_INT_CST_LOW (DECL_SIZE
5864                                           (TREE_OPERAND
5865                                            (TREE_OPERAND (varop, 0), 1)));
5866                     tree mask, unsigned_type;
5867                     int precision;
5868                     tree folded_compare;
5869
5870                     if (constopnum == 0)
5871                       folded_compare = fold (build (code, type, constop,
5872                                                     TREE_OPERAND (varop, 0)));
5873                     else
5874                       folded_compare = fold (build (code, type,
5875                                                     TREE_OPERAND (varop, 0),
5876                                                     constop));
5877                     if (integer_zerop (folded_compare)
5878                         || integer_onep (folded_compare))
5879                       return omit_one_operand (type, folded_compare, varop);
5880
5881                     unsigned_type = type_for_size (size, 1);
5882                     precision = TYPE_PRECISION (unsigned_type);
5883                     mask = build_int_2 (~0, ~0);
5884                     TREE_TYPE (mask) = TREE_TYPE (varop);
5885                     force_fit_type (mask, 0);
5886                     mask = const_binop (RSHIFT_EXPR, mask,
5887                                         size_int (precision - size), 0);
5888                     newconst = fold (build (BIT_AND_EXPR,
5889                                             TREE_TYPE (varop), newconst,
5890                                             convert (TREE_TYPE (varop),
5891                                                      mask)));
5892                   }
5893
5894
5895                 t = build (code, type, TREE_OPERAND (t, 0),
5896                            TREE_OPERAND (t, 1));
5897                 TREE_OPERAND (t, constopnum) = newconst;
5898                 return t;
5899               }
5900           }
5901       }
5902
5903       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5904       if (TREE_CODE (arg1) == INTEGER_CST
5905           && TREE_CODE (arg0) != INTEGER_CST
5906           && tree_int_cst_sgn (arg1) > 0)
5907         {
5908           switch (TREE_CODE (t))
5909             {
5910             case GE_EXPR:
5911               code = GT_EXPR;
5912               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5913               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5914               break;
5915
5916             case LT_EXPR:
5917               code = LE_EXPR;
5918               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5919               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5920               break;
5921
5922             default:
5923               break;
5924             }
5925         }
5926
5927       /* If this is an EQ or NE comparison with zero and ARG0 is
5928          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5929          two operations, but the latter can be done in one less insn
5930          on machines that have only two-operand insns or on which a
5931          constant cannot be the first operand.  */
5932       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5933           && TREE_CODE (arg0) == BIT_AND_EXPR)
5934         {
5935           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5936               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5937             return
5938               fold (build (code, type,
5939                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5940                                   build (RSHIFT_EXPR,
5941                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5942                                          TREE_OPERAND (arg0, 1),
5943                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5944                                   convert (TREE_TYPE (arg0),
5945                                            integer_one_node)),
5946                            arg1));
5947           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5948                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5949             return
5950               fold (build (code, type,
5951                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5952                                   build (RSHIFT_EXPR,
5953                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5954                                          TREE_OPERAND (arg0, 0),
5955                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5956                                   convert (TREE_TYPE (arg0),
5957                                            integer_one_node)),
5958                            arg1));
5959         }
5960
5961       /* If this is an NE or EQ comparison of zero against the result of a
5962          signed MOD operation whose second operand is a power of 2, make
5963          the MOD operation unsigned since it is simpler and equivalent.  */
5964       if ((code == NE_EXPR || code == EQ_EXPR)
5965           && integer_zerop (arg1)
5966           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5967           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5968               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5969               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5970               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5971           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5972         {
5973           tree newtype = unsigned_type (TREE_TYPE (arg0));
5974           tree newmod = build (TREE_CODE (arg0), newtype,
5975                                convert (newtype, TREE_OPERAND (arg0, 0)),
5976                                convert (newtype, TREE_OPERAND (arg0, 1)));
5977
5978           return build (code, type, newmod, convert (newtype, arg1));
5979         }
5980
5981       /* If this is an NE comparison of zero with an AND of one, remove the
5982          comparison since the AND will give the correct value.  */
5983       if (code == NE_EXPR && integer_zerop (arg1)
5984           && TREE_CODE (arg0) == BIT_AND_EXPR
5985           && integer_onep (TREE_OPERAND (arg0, 1)))
5986         return convert (type, arg0);
5987
5988       /* If we have (A & C) == C where C is a power of 2, convert this into
5989          (A & C) != 0.  Similarly for NE_EXPR.  */
5990       if ((code == EQ_EXPR || code == NE_EXPR)
5991           && TREE_CODE (arg0) == BIT_AND_EXPR
5992           && integer_pow2p (TREE_OPERAND (arg0, 1))
5993           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5994         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5995                       arg0, integer_zero_node);
5996
5997       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5998          and similarly for >= into !=.  */
5999       if ((code == LT_EXPR || code == GE_EXPR)
6000           && TREE_UNSIGNED (TREE_TYPE (arg0))
6001           && TREE_CODE (arg1) == LSHIFT_EXPR
6002           && integer_onep (TREE_OPERAND (arg1, 0)))
6003         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6004                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6005                              TREE_OPERAND (arg1, 1)),
6006                       convert (TREE_TYPE (arg0), integer_zero_node));
6007
6008       else if ((code == LT_EXPR || code == GE_EXPR)
6009                && TREE_UNSIGNED (TREE_TYPE (arg0))
6010                && (TREE_CODE (arg1) == NOP_EXPR
6011                    || TREE_CODE (arg1) == CONVERT_EXPR)
6012                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
6013                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
6014         return
6015           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6016                  convert (TREE_TYPE (arg0),
6017                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6018                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
6019                  convert (TREE_TYPE (arg0), integer_zero_node));
6020
6021       /* Simplify comparison of something with itself.  (For IEEE
6022          floating-point, we can only do some of these simplifications.)  */
6023       if (operand_equal_p (arg0, arg1, 0))
6024         {
6025           switch (code)
6026             {
6027             case EQ_EXPR:
6028             case GE_EXPR:
6029             case LE_EXPR:
6030               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
6031                 return constant_boolean_node (1, type);
6032               code = EQ_EXPR;
6033               TREE_SET_CODE (t, code);
6034               break;
6035
6036             case NE_EXPR:
6037               /* For NE, we can only do this simplification if integer.  */
6038               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
6039                 break;
6040               /* ... fall through ...  */
6041             case GT_EXPR:
6042             case LT_EXPR:
6043               return constant_boolean_node (0, type);
6044             default:
6045               abort ();
6046             }
6047         }
6048
6049       /* An unsigned comparison against 0 can be simplified.  */
6050       if (integer_zerop (arg1)
6051           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6052               || POINTER_TYPE_P (TREE_TYPE (arg1)))
6053           && TREE_UNSIGNED (TREE_TYPE (arg1)))
6054         {
6055           switch (TREE_CODE (t))
6056             {
6057             case GT_EXPR:
6058               code = NE_EXPR;
6059               TREE_SET_CODE (t, NE_EXPR);
6060               break;
6061             case LE_EXPR:
6062               code = EQ_EXPR;
6063               TREE_SET_CODE (t, EQ_EXPR);
6064               break;
6065             case GE_EXPR:
6066               return omit_one_operand (type,
6067                                        convert (type, integer_one_node),
6068                                        arg0);
6069             case LT_EXPR:
6070               return omit_one_operand (type,
6071                                        convert (type, integer_zero_node),
6072                                        arg0);
6073             default:
6074               break;
6075             }
6076         }
6077
6078       /* An unsigned <= 0x7fffffff can be simplified.  */
6079       {
6080         int width = TYPE_PRECISION (TREE_TYPE (arg1));
6081         if (TREE_CODE (arg1) == INTEGER_CST
6082             && ! TREE_CONSTANT_OVERFLOW (arg1)
6083             && width <= HOST_BITS_PER_WIDE_INT
6084             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
6085             && TREE_INT_CST_HIGH (arg1) == 0
6086             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6087                 || POINTER_TYPE_P (TREE_TYPE (arg1)))
6088             && TREE_UNSIGNED (TREE_TYPE (arg1)))
6089           {
6090             switch (TREE_CODE (t))
6091               {
6092               case LE_EXPR:
6093                 return fold (build (GE_EXPR, type,
6094                                     convert (signed_type (TREE_TYPE (arg0)),
6095                                              arg0),
6096                                     convert (signed_type (TREE_TYPE (arg1)),
6097                                              integer_zero_node)));
6098               case GT_EXPR:
6099                 return fold (build (LT_EXPR, type,
6100                                     convert (signed_type (TREE_TYPE (arg0)),
6101                                              arg0),
6102                                     convert (signed_type (TREE_TYPE (arg1)),
6103                                              integer_zero_node)));
6104               default:
6105                 break;
6106               }
6107           }
6108       }
6109
6110       /* If we are comparing an expression that just has comparisons
6111          of two integer values, arithmetic expressions of those comparisons,
6112          and constants, we can simplify it.  There are only three cases
6113          to check: the two values can either be equal, the first can be
6114          greater, or the second can be greater.  Fold the expression for
6115          those three values.  Since each value must be 0 or 1, we have
6116          eight possibilities, each of which corresponds to the constant 0
6117          or 1 or one of the six possible comparisons.
6118
6119          This handles common cases like (a > b) == 0 but also handles
6120          expressions like  ((x > y) - (y > x)) > 0, which supposedly
6121          occur in macroized code.  */
6122
6123       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6124         {
6125           tree cval1 = 0, cval2 = 0;
6126           int save_p = 0;
6127
6128           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6129               /* Don't handle degenerate cases here; they should already
6130                  have been handled anyway.  */
6131               && cval1 != 0 && cval2 != 0
6132               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6133               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6134               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6135               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6136               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6137               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6138                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6139             {
6140               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6141               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6142
6143               /* We can't just pass T to eval_subst in case cval1 or cval2
6144                  was the same as ARG1.  */
6145
6146               tree high_result
6147                 = fold (build (code, type,
6148                                eval_subst (arg0, cval1, maxval, cval2, minval),
6149                                arg1));
6150               tree equal_result
6151                 = fold (build (code, type,
6152                                eval_subst (arg0, cval1, maxval, cval2, maxval),
6153                                arg1));
6154               tree low_result
6155                 = fold (build (code, type,
6156                                eval_subst (arg0, cval1, minval, cval2, maxval),
6157                                arg1));
6158
6159               /* All three of these results should be 0 or 1.  Confirm they
6160                  are.  Then use those values to select the proper code
6161                  to use.  */
6162
6163               if ((integer_zerop (high_result)
6164                    || integer_onep (high_result))
6165                   && (integer_zerop (equal_result)
6166                       || integer_onep (equal_result))
6167                   && (integer_zerop (low_result)
6168                       || integer_onep (low_result)))
6169                 {
6170                   /* Make a 3-bit mask with the high-order bit being the
6171                      value for `>', the next for '=', and the low for '<'.  */
6172                   switch ((integer_onep (high_result) * 4)
6173                           + (integer_onep (equal_result) * 2)
6174                           + integer_onep (low_result))
6175                     {
6176                     case 0:
6177                       /* Always false.  */
6178                       return omit_one_operand (type, integer_zero_node, arg0);
6179                     case 1:
6180                       code = LT_EXPR;
6181                       break;
6182                     case 2:
6183                       code = EQ_EXPR;
6184                       break;
6185                     case 3:
6186                       code = LE_EXPR;
6187                       break;
6188                     case 4:
6189                       code = GT_EXPR;
6190                       break;
6191                     case 5:
6192                       code = NE_EXPR;
6193                       break;
6194                     case 6:
6195                       code = GE_EXPR;
6196                       break;
6197                     case 7:
6198                       /* Always true.  */
6199                       return omit_one_operand (type, integer_one_node, arg0);
6200                     }
6201
6202                   t = build (code, type, cval1, cval2);
6203                   if (save_p)
6204                     return save_expr (t);
6205                   else
6206                     return fold (t);
6207                 }
6208             }
6209         }
6210
6211       /* If this is a comparison of a field, we may be able to simplify it.  */
6212       if ((TREE_CODE (arg0) == COMPONENT_REF
6213            || TREE_CODE (arg0) == BIT_FIELD_REF)
6214           && (code == EQ_EXPR || code == NE_EXPR)
6215           /* Handle the constant case even without -O
6216              to make sure the warnings are given.  */
6217           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6218         {
6219           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6220           return t1 ? t1 : t;
6221         }
6222
6223       /* If this is a comparison of complex values and either or both sides
6224          are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6225          comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6226          This may prevent needless evaluations.  */
6227       if ((code == EQ_EXPR || code == NE_EXPR)
6228           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6229           && (TREE_CODE (arg0) == COMPLEX_EXPR
6230               || TREE_CODE (arg1) == COMPLEX_EXPR
6231               || TREE_CODE (arg0) == COMPLEX_CST
6232               || TREE_CODE (arg1) == COMPLEX_CST))
6233         {
6234           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6235           tree real0, imag0, real1, imag1;
6236
6237           arg0 = save_expr (arg0);
6238           arg1 = save_expr (arg1);
6239           real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6240           imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6241           real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6242           imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6243
6244           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6245                                : TRUTH_ORIF_EXPR),
6246                               type,
6247                               fold (build (code, type, real0, real1)),
6248                               fold (build (code, type, imag0, imag1))));
6249         }
6250
6251       /* From here on, the only cases we handle are when the result is
6252          known to be a constant.
6253
6254          To compute GT, swap the arguments and do LT.
6255          To compute GE, do LT and invert the result.
6256          To compute LE, swap the arguments, do LT and invert the result.
6257          To compute NE, do EQ and invert the result.
6258
6259          Therefore, the code below must handle only EQ and LT.  */
6260
6261       if (code == LE_EXPR || code == GT_EXPR)
6262         {
6263           tem = arg0, arg0 = arg1, arg1 = tem;
6264           code = swap_tree_comparison (code);
6265         }
6266
6267       /* Note that it is safe to invert for real values here because we
6268          will check below in the one case that it matters.  */
6269
6270       invert = 0;
6271       if (code == NE_EXPR || code == GE_EXPR)
6272         {
6273           invert = 1;
6274           code = invert_tree_comparison (code);
6275         }
6276
6277       /* Compute a result for LT or EQ if args permit;
6278          otherwise return T.  */
6279       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6280         {
6281           if (code == EQ_EXPR)
6282             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
6283                                == TREE_INT_CST_LOW (arg1))
6284                               && (TREE_INT_CST_HIGH (arg0)
6285                                   == TREE_INT_CST_HIGH (arg1)),
6286                               0);
6287           else
6288             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6289                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
6290                                : INT_CST_LT (arg0, arg1)),
6291                               0);
6292         }
6293
6294 #if 0 /* This is no longer useful, but breaks some real code.  */
6295       /* Assume a nonexplicit constant cannot equal an explicit one,
6296          since such code would be undefined anyway.
6297          Exception: on sysvr4, using #pragma weak,
6298          a label can come out as 0.  */
6299       else if (TREE_CODE (arg1) == INTEGER_CST
6300                && !integer_zerop (arg1)
6301                && TREE_CONSTANT (arg0)
6302                && TREE_CODE (arg0) == ADDR_EXPR
6303                && code == EQ_EXPR)
6304         t1 = build_int_2 (0, 0);
6305 #endif
6306       /* Two real constants can be compared explicitly.  */
6307       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6308         {
6309           /* If either operand is a NaN, the result is false with two
6310              exceptions: First, an NE_EXPR is true on NaNs, but that case
6311              is already handled correctly since we will be inverting the
6312              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
6313              or a GE_EXPR into a LT_EXPR, we must return true so that it
6314              will be inverted into false.  */
6315
6316           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6317               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6318             t1 = build_int_2 (invert && code == LT_EXPR, 0);
6319
6320           else if (code == EQ_EXPR)
6321             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6322                                                  TREE_REAL_CST (arg1)),
6323                               0);
6324           else
6325             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6326                                                 TREE_REAL_CST (arg1)),
6327                               0);
6328         }
6329
6330       if (t1 == NULL_TREE)
6331         return t;
6332
6333       if (invert)
6334         TREE_INT_CST_LOW (t1) ^= 1;
6335
6336       TREE_TYPE (t1) = type;
6337       if (TREE_CODE (type) == BOOLEAN_TYPE)
6338         return truthvalue_conversion (t1);
6339       return t1;
6340
6341     case COND_EXPR:
6342       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6343          so all simple results must be passed through pedantic_non_lvalue.  */
6344       if (TREE_CODE (arg0) == INTEGER_CST)
6345         return pedantic_non_lvalue
6346           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6347       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6348         return pedantic_omit_one_operand (type, arg1, arg0);
6349
6350       /* If the second operand is zero, invert the comparison and swap
6351          the second and third operands.  Likewise if the second operand
6352          is constant and the third is not or if the third operand is
6353          equivalent to the first operand of the comparison.  */
6354
6355       if (integer_zerop (arg1)
6356           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6357           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6358               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6359                                                  TREE_OPERAND (t, 2),
6360                                                  TREE_OPERAND (arg0, 1))))
6361         {
6362           /* See if this can be inverted.  If it can't, possibly because
6363              it was a floating-point inequality comparison, don't do
6364              anything.  */
6365           tem = invert_truthvalue (arg0);
6366
6367           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6368             {
6369               t = build (code, type, tem,
6370                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6371               arg0 = tem;
6372               /* arg1 should be the first argument of the new T.  */
6373               arg1 = TREE_OPERAND (t, 1);
6374               STRIP_NOPS (arg1);
6375             }
6376         }
6377
6378       /* If we have A op B ? A : C, we may be able to convert this to a
6379          simpler expression, depending on the operation and the values
6380          of B and C.  IEEE floating point prevents this though,
6381          because A or B might be -0.0 or a NaN.  */
6382
6383       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6384           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
6385               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
6386               || flag_fast_math)
6387           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6388                                              arg1, TREE_OPERAND (arg0, 1)))
6389         {
6390           tree arg2 = TREE_OPERAND (t, 2);
6391           enum tree_code comp_code = TREE_CODE (arg0);
6392
6393           STRIP_NOPS (arg2);
6394
6395           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
6396              depending on the comparison operation.  */
6397           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6398                ? real_zerop (TREE_OPERAND (arg0, 1))
6399                : integer_zerop (TREE_OPERAND (arg0, 1)))
6400               && TREE_CODE (arg2) == NEGATE_EXPR
6401               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6402             switch (comp_code)
6403               {
6404               case EQ_EXPR:
6405                 return pedantic_non_lvalue
6406                   (fold (build1 (NEGATE_EXPR, type, arg1)));
6407               case NE_EXPR:
6408                 return pedantic_non_lvalue (convert (type, arg1));
6409               case GE_EXPR:
6410               case GT_EXPR:
6411                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6412                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6413                 return pedantic_non_lvalue
6414                   (convert (type, fold (build1 (ABS_EXPR,
6415                                                 TREE_TYPE (arg1), arg1))));
6416               case LE_EXPR:
6417               case LT_EXPR:
6418                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6419                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6420                 return pedantic_non_lvalue
6421                   (fold (build1 (NEGATE_EXPR, type,
6422                                  convert (type,
6423                                           fold (build1 (ABS_EXPR,
6424                                                         TREE_TYPE (arg1),
6425                                                         arg1))))));
6426               default:
6427                 abort ();
6428               }
6429
6430           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
6431              always zero.  */
6432
6433           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6434             {
6435               if (comp_code == NE_EXPR)
6436                 return pedantic_non_lvalue (convert (type, arg1));
6437               else if (comp_code == EQ_EXPR)
6438                 return pedantic_non_lvalue (convert (type, integer_zero_node));
6439             }
6440
6441           /* If this is A op B ? A : B, this is either A, B, min (A, B),
6442              or max (A, B), depending on the operation.  */
6443
6444           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6445                                               arg2, TREE_OPERAND (arg0, 0)))
6446             {
6447               tree comp_op0 = TREE_OPERAND (arg0, 0);
6448               tree comp_op1 = TREE_OPERAND (arg0, 1);
6449               tree comp_type = TREE_TYPE (comp_op0);
6450
6451               switch (comp_code)
6452                 {
6453                 case EQ_EXPR:
6454                   return pedantic_non_lvalue (convert (type, arg2));
6455                 case NE_EXPR:
6456                   return pedantic_non_lvalue (convert (type, arg1));
6457                 case LE_EXPR:
6458                 case LT_EXPR:
6459                   /* In C++ a ?: expression can be an lvalue, so put the
6460                      operand which will be used if they are equal first
6461                      so that we can convert this back to the
6462                      corresponding COND_EXPR.  */
6463                   return pedantic_non_lvalue
6464                     (convert (type, (fold (build (MIN_EXPR, comp_type,
6465                                                   (comp_code == LE_EXPR
6466                                                    ? comp_op0 : comp_op1),
6467                                                   (comp_code == LE_EXPR
6468                                                    ? comp_op1 : comp_op0))))));
6469                   break;
6470                 case GE_EXPR:
6471                 case GT_EXPR:
6472                   return pedantic_non_lvalue
6473                     (convert (type, fold (build (MAX_EXPR, comp_type,
6474                                                  (comp_code == GE_EXPR
6475                                                   ? comp_op0 : comp_op1),
6476                                                  (comp_code == GE_EXPR
6477                                                   ? comp_op1 : comp_op0)))));
6478                   break;
6479                 default:
6480                   abort ();
6481                 }
6482             }
6483
6484           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6485              we might still be able to simplify this.  For example,
6486              if C1 is one less or one more than C2, this might have started
6487              out as a MIN or MAX and been transformed by this function.
6488              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
6489
6490           if (INTEGRAL_TYPE_P (type)
6491               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6492               && TREE_CODE (arg2) == INTEGER_CST)
6493             switch (comp_code)
6494               {
6495               case EQ_EXPR:
6496                 /* We can replace A with C1 in this case.  */
6497                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6498                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6499                            TREE_OPERAND (t, 2));
6500                 break;
6501
6502               case LT_EXPR:
6503                 /* If C1 is C2 + 1, this is min(A, C2).  */
6504                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6505                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6506                                         const_binop (PLUS_EXPR, arg2,
6507                                                      integer_one_node, 0), 1))
6508                   return pedantic_non_lvalue
6509                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6510                 break;
6511
6512               case LE_EXPR:
6513                 /* If C1 is C2 - 1, this is min(A, C2).  */
6514                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6515                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6516                                         const_binop (MINUS_EXPR, arg2,
6517                                                      integer_one_node, 0), 1))
6518                   return pedantic_non_lvalue
6519                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6520                 break;
6521
6522               case GT_EXPR:
6523                 /* If C1 is C2 - 1, this is max(A, C2).  */
6524                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6525                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6526                                         const_binop (MINUS_EXPR, arg2,
6527                                                      integer_one_node, 0), 1))
6528                   return pedantic_non_lvalue
6529                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6530                 break;
6531
6532               case GE_EXPR:
6533                 /* If C1 is C2 + 1, this is max(A, C2).  */
6534                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6535                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6536                                         const_binop (PLUS_EXPR, arg2,
6537                                                      integer_one_node, 0), 1))
6538                   return pedantic_non_lvalue
6539                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6540                 break;
6541               case NE_EXPR:
6542                 break;
6543               default:
6544                 abort ();
6545               }
6546         }
6547
6548       /* If the second operand is simpler than the third, swap them
6549          since that produces better jump optimization results.  */
6550       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
6551            || TREE_CODE (arg1) == SAVE_EXPR)
6552           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6553                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
6554                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6555         {
6556           /* See if this can be inverted.  If it can't, possibly because
6557              it was a floating-point inequality comparison, don't do
6558              anything.  */
6559           tem = invert_truthvalue (arg0);
6560
6561           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6562             {
6563               t = build (code, type, tem,
6564                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6565               arg0 = tem;
6566               /* arg1 should be the first argument of the new T.  */
6567               arg1 = TREE_OPERAND (t, 1);
6568               STRIP_NOPS (arg1);
6569             }
6570         }
6571
6572       /* Convert A ? 1 : 0 to simply A.  */
6573       if (integer_onep (TREE_OPERAND (t, 1))
6574           && integer_zerop (TREE_OPERAND (t, 2))
6575           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6576              call to fold will try to move the conversion inside
6577              a COND, which will recurse.  In that case, the COND_EXPR
6578              is probably the best choice, so leave it alone.  */
6579           && type == TREE_TYPE (arg0))
6580         return pedantic_non_lvalue (arg0);
6581
6582       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
6583          operation is simply A & 2.  */
6584
6585       if (integer_zerop (TREE_OPERAND (t, 2))
6586           && TREE_CODE (arg0) == NE_EXPR
6587           && integer_zerop (TREE_OPERAND (arg0, 1))
6588           && integer_pow2p (arg1)
6589           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6590           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6591                               arg1, 1))
6592         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6593
6594       return t;
6595
6596     case COMPOUND_EXPR:
6597       /* When pedantic, a compound expression can be neither an lvalue
6598          nor an integer constant expression.  */
6599       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6600         return t;
6601       /* Don't let (0, 0) be null pointer constant.  */
6602       if (integer_zerop (arg1))
6603         return build1 (NOP_EXPR, TREE_TYPE (arg1), arg1);
6604       return arg1;
6605
6606     case COMPLEX_EXPR:
6607       if (wins)
6608         return build_complex (type, arg0, arg1);
6609       return t;
6610
6611     case REALPART_EXPR:
6612       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6613         return t;
6614       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6615         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6616                                  TREE_OPERAND (arg0, 1));
6617       else if (TREE_CODE (arg0) == COMPLEX_CST)
6618         return TREE_REALPART (arg0);
6619       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6620         return fold (build (TREE_CODE (arg0), type,
6621                             fold (build1 (REALPART_EXPR, type,
6622                                           TREE_OPERAND (arg0, 0))),
6623                             fold (build1 (REALPART_EXPR,
6624                                           type, TREE_OPERAND (arg0, 1)))));
6625       return t;
6626
6627     case IMAGPART_EXPR:
6628       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6629         return convert (type, integer_zero_node);
6630       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6631         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6632                                  TREE_OPERAND (arg0, 0));
6633       else if (TREE_CODE (arg0) == COMPLEX_CST)
6634         return TREE_IMAGPART (arg0);
6635       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6636         return fold (build (TREE_CODE (arg0), type,
6637                             fold (build1 (IMAGPART_EXPR, type,
6638                                           TREE_OPERAND (arg0, 0))),
6639                             fold (build1 (IMAGPART_EXPR, type,
6640                                           TREE_OPERAND (arg0, 1)))));
6641       return t;
6642
6643       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6644          appropriate.  */
6645     case CLEANUP_POINT_EXPR:
6646       if (! has_cleanups (arg0))
6647         return TREE_OPERAND (t, 0);
6648
6649       {
6650         enum tree_code code0 = TREE_CODE (arg0);
6651         int kind0 = TREE_CODE_CLASS (code0);
6652         tree arg00 = TREE_OPERAND (arg0, 0);
6653         tree arg01;
6654
6655         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6656           return fold (build1 (code0, type,
6657                                fold (build1 (CLEANUP_POINT_EXPR,
6658                                              TREE_TYPE (arg00), arg00))));
6659
6660         if (kind0 == '<' || kind0 == '2'
6661             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6662             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
6663             || code0 == TRUTH_XOR_EXPR)
6664           {
6665             arg01 = TREE_OPERAND (arg0, 1);
6666
6667             if (TREE_CONSTANT (arg00)
6668                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6669                     && ! has_cleanups (arg00)))
6670               return fold (build (code0, type, arg00,
6671                                   fold (build1 (CLEANUP_POINT_EXPR,
6672                                                 TREE_TYPE (arg01), arg01))));
6673
6674             if (TREE_CONSTANT (arg01))
6675               return fold (build (code0, type,
6676                                   fold (build1 (CLEANUP_POINT_EXPR,
6677                                                 TREE_TYPE (arg00), arg00)),
6678                                   arg01));
6679           }
6680
6681         return t;
6682       }
6683
6684     default:
6685       return t;
6686     } /* switch (code) */
6687 }
6688
6689 /* Determine if first argument is a multiple of second argument.  Return 0 if
6690    it is not, or we cannot easily determined it to be.
6691
6692    An example of the sort of thing we care about (at this point; this routine
6693    could surely be made more general, and expanded to do what the *_DIV_EXPR's
6694    fold cases do now) is discovering that
6695
6696      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6697
6698    is a multiple of
6699
6700      SAVE_EXPR (J * 8)
6701
6702    when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
6703
6704    This code also handles discovering that
6705
6706      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6707
6708    is a multiple of 8 so we don't have to worry about dealing with a
6709    possible remainder.
6710
6711    Note that we *look* inside a SAVE_EXPR only to determine how it was
6712    calculated; it is not safe for fold to do much of anything else with the
6713    internals of a SAVE_EXPR, since it cannot know when it will be evaluated
6714    at run time.  For example, the latter example above *cannot* be implemented
6715    as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
6716    evaluation time of the original SAVE_EXPR is not necessarily the same at
6717    the time the new expression is evaluated.  The only optimization of this
6718    sort that would be valid is changing
6719
6720      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6721
6722    divided by 8 to
6723
6724      SAVE_EXPR (I) * SAVE_EXPR (J)
6725
6726    (where the same SAVE_EXPR (J) is used in the original and the
6727    transformed version).  */
6728
6729 static int
6730 multiple_of_p (type, top, bottom)
6731      tree type;
6732      tree top;
6733      tree bottom;
6734 {
6735   if (operand_equal_p (top, bottom, 0))
6736     return 1;
6737
6738   if (TREE_CODE (type) != INTEGER_TYPE)
6739     return 0;
6740
6741   switch (TREE_CODE (top))
6742     {
6743     case MULT_EXPR:
6744       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6745               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6746
6747     case PLUS_EXPR:
6748     case MINUS_EXPR:
6749       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6750               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6751
6752     case NOP_EXPR:
6753       /* Can't handle conversions from non-integral or wider integral type.  */
6754       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6755           || (TYPE_PRECISION (type)
6756               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6757         return 0;
6758
6759       /* .. fall through ... */
6760
6761     case SAVE_EXPR:
6762       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6763
6764     case INTEGER_CST:
6765       if ((TREE_CODE (bottom) != INTEGER_CST)
6766           || (tree_int_cst_sgn (top) < 0)
6767           || (tree_int_cst_sgn (bottom) < 0))
6768         return 0;
6769       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6770                                          top, bottom, 0));
6771
6772     default:
6773       return 0;
6774     }
6775 }