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