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