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       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2095     return 0;
2096
2097   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2098      We don't care about side effects in that case because the SAVE_EXPR
2099      takes care of that for us. In all other cases, two expressions are
2100      equal if they have no side effects.  If we have two identical
2101      expressions with side effects that should be treated the same due
2102      to the only side effects being identical SAVE_EXPR's, that will
2103      be detected in the recursive calls below.  */
2104   if (arg0 == arg1 && ! only_const
2105       && (TREE_CODE (arg0) == SAVE_EXPR
2106           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2107     return 1;
2108
2109   /* Next handle constant cases, those for which we can return 1 even
2110      if ONLY_CONST is set.  */
2111   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2112     switch (TREE_CODE (arg0))
2113       {
2114       case INTEGER_CST:
2115         return (! TREE_CONSTANT_OVERFLOW (arg0)
2116                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2117                 && TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
2118                 && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1));
2119
2120       case REAL_CST:
2121         return (! TREE_CONSTANT_OVERFLOW (arg0)
2122                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2123                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2124                                           TREE_REAL_CST (arg1)));
2125
2126       case COMPLEX_CST:
2127         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2128                                  only_const)
2129                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2130                                     only_const));
2131
2132       case STRING_CST:
2133         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2134                 && ! strncmp (TREE_STRING_POINTER (arg0),
2135                               TREE_STRING_POINTER (arg1),
2136                               TREE_STRING_LENGTH (arg0)));
2137
2138       case ADDR_EXPR:
2139         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2140                                 0);
2141       default:
2142         break;
2143       }
2144
2145   if (only_const)
2146     return 0;
2147
2148   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2149     {
2150     case '1':
2151       /* Two conversions are equal only if signedness and modes match.  */
2152       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
2153           && (TREE_UNSIGNED (TREE_TYPE (arg0))
2154               != TREE_UNSIGNED (TREE_TYPE (arg1))))
2155         return 0;
2156
2157       return operand_equal_p (TREE_OPERAND (arg0, 0),
2158                               TREE_OPERAND (arg1, 0), 0);
2159
2160     case '<':
2161     case '2':
2162       if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
2163           && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
2164                               0))
2165         return 1;
2166
2167       /* For commutative ops, allow the other order.  */
2168       return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
2169                || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
2170                || TREE_CODE (arg0) == BIT_IOR_EXPR
2171                || TREE_CODE (arg0) == BIT_XOR_EXPR
2172                || TREE_CODE (arg0) == BIT_AND_EXPR
2173                || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
2174               && operand_equal_p (TREE_OPERAND (arg0, 0),
2175                                   TREE_OPERAND (arg1, 1), 0)
2176               && operand_equal_p (TREE_OPERAND (arg0, 1),
2177                                   TREE_OPERAND (arg1, 0), 0));
2178
2179     case 'r':
2180       switch (TREE_CODE (arg0))
2181         {
2182         case INDIRECT_REF:
2183           return operand_equal_p (TREE_OPERAND (arg0, 0),
2184                                   TREE_OPERAND (arg1, 0), 0);
2185
2186         case COMPONENT_REF:
2187         case ARRAY_REF:
2188           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2189                                    TREE_OPERAND (arg1, 0), 0)
2190                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2191                                       TREE_OPERAND (arg1, 1), 0));
2192
2193         case BIT_FIELD_REF:
2194           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2195                                    TREE_OPERAND (arg1, 0), 0)
2196                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2197                                       TREE_OPERAND (arg1, 1), 0)
2198                   && operand_equal_p (TREE_OPERAND (arg0, 2),
2199                                       TREE_OPERAND (arg1, 2), 0));
2200         default:
2201           return 0;
2202         }
2203
2204     case 'e':
2205       if (TREE_CODE (arg0) == RTL_EXPR)
2206         return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
2207       return 0;
2208
2209     default:
2210       return 0;
2211     }
2212 }
2213 \f
2214 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2215    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2216
2217    When in doubt, return 0.  */
2218
2219 static int
2220 operand_equal_for_comparison_p (arg0, arg1, other)
2221      tree arg0, arg1;
2222      tree other;
2223 {
2224   int unsignedp1, unsignedpo;
2225   tree primarg0, primarg1, primother;
2226   unsigned correct_width;
2227
2228   if (operand_equal_p (arg0, arg1, 0))
2229     return 1;
2230
2231   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2232       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2233     return 0;
2234
2235   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2236      and see if the inner values are the same.  This removes any
2237      signedness comparison, which doesn't matter here.  */
2238   primarg0 = arg0, primarg1 = arg1;
2239   STRIP_NOPS (primarg0);  STRIP_NOPS (primarg1);
2240   if (operand_equal_p (primarg0, primarg1, 0))
2241     return 1;
2242
2243   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2244      actual comparison operand, ARG0.
2245
2246      First throw away any conversions to wider types
2247      already present in the operands.  */
2248
2249   primarg1 = get_narrower (arg1, &unsignedp1);
2250   primother = get_narrower (other, &unsignedpo);
2251
2252   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2253   if (unsignedp1 == unsignedpo
2254       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2255       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2256     {
2257       tree type = TREE_TYPE (arg0);
2258
2259       /* Make sure shorter operand is extended the right way
2260          to match the longer operand.  */
2261       primarg1 = convert (signed_or_unsigned_type (unsignedp1,
2262                                                   TREE_TYPE (primarg1)),
2263                          primarg1);
2264
2265       if (operand_equal_p (arg0, convert (type, primarg1), 0))
2266         return 1;
2267     }
2268
2269   return 0;
2270 }
2271 \f
2272 /* See if ARG is an expression that is either a comparison or is performing
2273    arithmetic on comparisons.  The comparisons must only be comparing
2274    two different values, which will be stored in *CVAL1 and *CVAL2; if
2275    they are non-zero it means that some operands have already been found.
2276    No variables may be used anywhere else in the expression except in the
2277    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2278    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2279
2280    If this is true, return 1.  Otherwise, return zero.  */
2281
2282 static int
2283 twoval_comparison_p (arg, cval1, cval2, save_p)
2284      tree arg;
2285      tree *cval1, *cval2;
2286      int *save_p;
2287 {
2288   enum tree_code code = TREE_CODE (arg);
2289   char class = TREE_CODE_CLASS (code);
2290
2291   /* We can handle some of the 'e' cases here.  */
2292   if (class == 'e' && code == TRUTH_NOT_EXPR)
2293     class = '1';
2294   else if (class == 'e'
2295            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2296                || code == COMPOUND_EXPR))
2297     class = '2';
2298
2299   /* ??? Disable this since the SAVE_EXPR might already be in use outside
2300      the expression.  There may be no way to make this work, but it needs
2301      to be looked at again for 2.6.  */
2302 #if 0
2303   else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0)
2304     {
2305       /* If we've already found a CVAL1 or CVAL2, this expression is
2306          two complex to handle.  */
2307       if (*cval1 || *cval2)
2308         return 0;
2309
2310       class = '1';
2311       *save_p = 1;
2312     }
2313 #endif
2314
2315   switch (class)
2316     {
2317     case '1':
2318       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2319
2320     case '2':
2321       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2322               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2323                                       cval1, cval2, save_p));
2324
2325     case 'c':
2326       return 1;
2327
2328     case 'e':
2329       if (code == COND_EXPR)
2330         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2331                                      cval1, cval2, save_p)
2332                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2333                                         cval1, cval2, save_p)
2334                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2335                                         cval1, cval2, save_p));
2336       return 0;
2337
2338     case '<':
2339       /* First see if we can handle the first operand, then the second.  For
2340          the second operand, we know *CVAL1 can't be zero.  It must be that
2341          one side of the comparison is each of the values; test for the
2342          case where this isn't true by failing if the two operands
2343          are the same.  */
2344
2345       if (operand_equal_p (TREE_OPERAND (arg, 0),
2346                            TREE_OPERAND (arg, 1), 0))
2347         return 0;
2348
2349       if (*cval1 == 0)
2350         *cval1 = TREE_OPERAND (arg, 0);
2351       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2352         ;
2353       else if (*cval2 == 0)
2354         *cval2 = TREE_OPERAND (arg, 0);
2355       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2356         ;
2357       else
2358         return 0;
2359
2360       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2361         ;
2362       else if (*cval2 == 0)
2363         *cval2 = TREE_OPERAND (arg, 1);
2364       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2365         ;
2366       else
2367         return 0;
2368
2369       return 1;
2370
2371     default:
2372       return 0;
2373     }
2374 }
2375 \f
2376 /* ARG is a tree that is known to contain just arithmetic operations and
2377    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2378    any occurrence of OLD0 as an operand of a comparison and likewise for
2379    NEW1 and OLD1.  */
2380
2381 static tree
2382 eval_subst (arg, old0, new0, old1, new1)
2383      tree arg;
2384      tree old0, new0, old1, new1;
2385 {
2386   tree type = TREE_TYPE (arg);
2387   enum tree_code code = TREE_CODE (arg);
2388   char class = TREE_CODE_CLASS (code);
2389
2390   /* We can handle some of the 'e' cases here.  */
2391   if (class == 'e' && code == TRUTH_NOT_EXPR)
2392     class = '1';
2393   else if (class == 'e'
2394            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2395     class = '2';
2396
2397   switch (class)
2398     {
2399     case '1':
2400       return fold (build1 (code, type,
2401                            eval_subst (TREE_OPERAND (arg, 0),
2402                                        old0, new0, old1, new1)));
2403
2404     case '2':
2405       return fold (build (code, type,
2406                           eval_subst (TREE_OPERAND (arg, 0),
2407                                       old0, new0, old1, new1),
2408                           eval_subst (TREE_OPERAND (arg, 1),
2409                                       old0, new0, old1, new1)));
2410
2411     case 'e':
2412       switch (code)
2413         {
2414         case SAVE_EXPR:
2415           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2416
2417         case COMPOUND_EXPR:
2418           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2419
2420         case COND_EXPR:
2421           return fold (build (code, type,
2422                               eval_subst (TREE_OPERAND (arg, 0),
2423                                           old0, new0, old1, new1),
2424                               eval_subst (TREE_OPERAND (arg, 1),
2425                                           old0, new0, old1, new1),
2426                               eval_subst (TREE_OPERAND (arg, 2),
2427                                           old0, new0, old1, new1)));
2428         default:
2429           break;
2430         }
2431       /* fall through - ??? */
2432
2433     case '<':
2434       {
2435         tree arg0 = TREE_OPERAND (arg, 0);
2436         tree arg1 = TREE_OPERAND (arg, 1);
2437
2438         /* We need to check both for exact equality and tree equality.  The
2439            former will be true if the operand has a side-effect.  In that
2440            case, we know the operand occurred exactly once.  */
2441
2442         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2443           arg0 = new0;
2444         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2445           arg0 = new1;
2446
2447         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2448           arg1 = new0;
2449         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2450           arg1 = new1;
2451
2452         return fold (build (code, type, arg0, arg1));
2453       }
2454
2455     default:
2456       return arg;
2457     }
2458 }
2459 \f
2460 /* Return a tree for the case when the result of an expression is RESULT
2461    converted to TYPE and OMITTED was previously an operand of the expression
2462    but is now not needed (e.g., we folded OMITTED * 0).
2463
2464    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2465    the conversion of RESULT to TYPE.  */
2466
2467 static tree
2468 omit_one_operand (type, result, omitted)
2469      tree type, result, omitted;
2470 {
2471   tree t = convert (type, result);
2472
2473   if (TREE_SIDE_EFFECTS (omitted))
2474     return build (COMPOUND_EXPR, type, omitted, t);
2475
2476   return non_lvalue (t);
2477 }
2478
2479 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2480
2481 static tree
2482 pedantic_omit_one_operand (type, result, omitted)
2483      tree type, result, omitted;
2484 {
2485   tree t = convert (type, result);
2486
2487   if (TREE_SIDE_EFFECTS (omitted))
2488     return build (COMPOUND_EXPR, type, omitted, t);
2489
2490   return pedantic_non_lvalue (t);
2491 }
2492
2493
2494 \f
2495 /* Return a simplified tree node for the truth-negation of ARG.  This
2496    never alters ARG itself.  We assume that ARG is an operation that
2497    returns a truth value (0 or 1).  */
2498
2499 tree
2500 invert_truthvalue (arg)
2501      tree arg;
2502 {
2503   tree type = TREE_TYPE (arg);
2504   enum tree_code code = TREE_CODE (arg);
2505
2506   if (code == ERROR_MARK)
2507     return arg;
2508
2509   /* If this is a comparison, we can simply invert it, except for
2510      floating-point non-equality comparisons, in which case we just
2511      enclose a TRUTH_NOT_EXPR around what we have.  */
2512
2513   if (TREE_CODE_CLASS (code) == '<')
2514     {
2515       if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2516           && !flag_fast_math && code != NE_EXPR && code != EQ_EXPR)
2517         return build1 (TRUTH_NOT_EXPR, type, arg);
2518       else
2519         return build (invert_tree_comparison (code), type,
2520                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2521     }
2522
2523   switch (code)
2524     {
2525     case INTEGER_CST:
2526       return convert (type, build_int_2 (TREE_INT_CST_LOW (arg) == 0
2527                                          && TREE_INT_CST_HIGH (arg) == 0, 0));
2528
2529     case TRUTH_AND_EXPR:
2530       return build (TRUTH_OR_EXPR, type,
2531                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2532                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2533
2534     case TRUTH_OR_EXPR:
2535       return build (TRUTH_AND_EXPR, type,
2536                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2537                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2538
2539     case TRUTH_XOR_EXPR:
2540       /* Here we can invert either operand.  We invert the first operand
2541          unless the second operand is a TRUTH_NOT_EXPR in which case our
2542          result is the XOR of the first operand with the inside of the
2543          negation of the second operand.  */
2544
2545       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2546         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2547                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2548       else
2549         return build (TRUTH_XOR_EXPR, type,
2550                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2551                       TREE_OPERAND (arg, 1));
2552
2553     case TRUTH_ANDIF_EXPR:
2554       return build (TRUTH_ORIF_EXPR, type,
2555                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2556                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2557
2558     case TRUTH_ORIF_EXPR:
2559       return build (TRUTH_ANDIF_EXPR, type,
2560                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2561                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2562
2563     case TRUTH_NOT_EXPR:
2564       return TREE_OPERAND (arg, 0);
2565
2566     case COND_EXPR:
2567       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2568                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2569                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2570
2571     case COMPOUND_EXPR:
2572       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2573                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2574
2575     case NON_LVALUE_EXPR:
2576       return invert_truthvalue (TREE_OPERAND (arg, 0));
2577
2578     case NOP_EXPR:
2579     case CONVERT_EXPR:
2580     case FLOAT_EXPR:
2581       return build1 (TREE_CODE (arg), type,
2582                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2583
2584     case BIT_AND_EXPR:
2585       if (!integer_onep (TREE_OPERAND (arg, 1)))
2586         break;
2587       return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2588
2589     case SAVE_EXPR:
2590       return build1 (TRUTH_NOT_EXPR, type, arg);
2591
2592     case CLEANUP_POINT_EXPR:
2593       return build1 (CLEANUP_POINT_EXPR, type,
2594                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2595
2596     default:
2597       break;
2598     }
2599   if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2600     abort ();
2601   return build1 (TRUTH_NOT_EXPR, type, arg);
2602 }
2603
2604 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2605    operands are another bit-wise operation with a common input.  If so,
2606    distribute the bit operations to save an operation and possibly two if
2607    constants are involved.  For example, convert
2608         (A | B) & (A | C) into A | (B & C)
2609    Further simplification will occur if B and C are constants.
2610
2611    If this optimization cannot be done, 0 will be returned.  */
2612
2613 static tree
2614 distribute_bit_expr (code, type, arg0, arg1)
2615      enum tree_code code;
2616      tree type;
2617      tree arg0, arg1;
2618 {
2619   tree common;
2620   tree left, right;
2621
2622   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2623       || TREE_CODE (arg0) == code
2624       || (TREE_CODE (arg0) != BIT_AND_EXPR
2625           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2626     return 0;
2627
2628   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2629     {
2630       common = TREE_OPERAND (arg0, 0);
2631       left = TREE_OPERAND (arg0, 1);
2632       right = TREE_OPERAND (arg1, 1);
2633     }
2634   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2635     {
2636       common = TREE_OPERAND (arg0, 0);
2637       left = TREE_OPERAND (arg0, 1);
2638       right = TREE_OPERAND (arg1, 0);
2639     }
2640   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2641     {
2642       common = TREE_OPERAND (arg0, 1);
2643       left = TREE_OPERAND (arg0, 0);
2644       right = TREE_OPERAND (arg1, 1);
2645     }
2646   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2647     {
2648       common = TREE_OPERAND (arg0, 1);
2649       left = TREE_OPERAND (arg0, 0);
2650       right = TREE_OPERAND (arg1, 0);
2651     }
2652   else
2653     return 0;
2654
2655   return fold (build (TREE_CODE (arg0), type, common,
2656                       fold (build (code, type, left, right))));
2657 }
2658 \f
2659 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2660    starting at BITPOS.  The field is unsigned if UNSIGNEDP is non-zero.  */
2661
2662 static tree
2663 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2664      tree inner;
2665      tree type;
2666      int bitsize, bitpos;
2667      int unsignedp;
2668 {
2669   tree result = build (BIT_FIELD_REF, type, inner,
2670                        size_int (bitsize), bitsize_int (bitpos, 0L));
2671
2672   TREE_UNSIGNED (result) = unsignedp;
2673
2674   return result;
2675 }
2676
2677 /* Optimize a bit-field compare.
2678
2679    There are two cases:  First is a compare against a constant and the
2680    second is a comparison of two items where the fields are at the same
2681    bit position relative to the start of a chunk (byte, halfword, word)
2682    large enough to contain it.  In these cases we can avoid the shift
2683    implicit in bitfield extractions.
2684
2685    For constants, we emit a compare of the shifted constant with the
2686    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2687    compared.  For two fields at the same position, we do the ANDs with the
2688    similar mask and compare the result of the ANDs.
2689
2690    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2691    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2692    are the left and right operands of the comparison, respectively.
2693
2694    If the optimization described above can be done, we return the resulting
2695    tree.  Otherwise we return zero.  */
2696
2697 static tree
2698 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2699      enum tree_code code;
2700      tree compare_type;
2701      tree lhs, rhs;
2702 {
2703   int lbitpos, lbitsize, rbitpos, rbitsize;
2704   int lnbitpos, lnbitsize, rnbitpos = 0, rnbitsize = 0;
2705   tree type = TREE_TYPE (lhs);
2706   tree signed_type, unsigned_type;
2707   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2708   enum machine_mode lmode, rmode, lnmode, rnmode = VOIDmode;
2709   int lunsignedp, runsignedp;
2710   int lvolatilep = 0, rvolatilep = 0;
2711   int alignment;
2712   tree linner, rinner = NULL_TREE;
2713   tree mask;
2714   tree offset;
2715
2716   /* Get all the information about the extractions being done.  If the bit size
2717      if the same as the size of the underlying object, we aren't doing an
2718      extraction at all and so can do nothing.  */
2719   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2720                                 &lunsignedp, &lvolatilep, &alignment);
2721   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2722       || offset != 0)
2723     return 0;
2724
2725  if (!const_p)
2726    {
2727      /* If this is not a constant, we can only do something if bit positions,
2728         sizes, and signedness are the same.   */
2729      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2730                                    &runsignedp, &rvolatilep, &alignment);
2731
2732      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2733          || lunsignedp != runsignedp || offset != 0)
2734        return 0;
2735    }
2736
2737   /* See if we can find a mode to refer to this field.  We should be able to,
2738      but fail if we can't.  */
2739   lnmode = get_best_mode (lbitsize, lbitpos,
2740                           TYPE_ALIGN (TREE_TYPE (linner)), word_mode,
2741                           lvolatilep);
2742   if (lnmode == VOIDmode)
2743     return 0;
2744
2745   /* Set signed and unsigned types of the precision of this mode for the
2746      shifts below.  */
2747   signed_type = type_for_mode (lnmode, 0);
2748   unsigned_type = type_for_mode (lnmode, 1);
2749
2750   if (! const_p)
2751     {
2752       rnmode = get_best_mode (rbitsize, rbitpos,
2753                               TYPE_ALIGN (TREE_TYPE (rinner)), word_mode,
2754                               rvolatilep);
2755       if (rnmode == VOIDmode)
2756         return 0;
2757     }
2758
2759   /* Compute the bit position and size for the new reference and our offset
2760      within it. If the new reference is the same size as the original, we
2761      won't optimize anything, so return zero.  */
2762   lnbitsize = GET_MODE_BITSIZE (lnmode);
2763   lnbitpos = lbitpos & ~ (lnbitsize - 1);
2764   lbitpos -= lnbitpos;
2765   if (lnbitsize == lbitsize)
2766     return 0;
2767
2768   if (! const_p)
2769     {
2770       rnbitsize = GET_MODE_BITSIZE (rnmode);
2771       rnbitpos = rbitpos & ~ (rnbitsize - 1);
2772       rbitpos -= rnbitpos;
2773       if (rnbitsize == rbitsize)
2774         return 0;
2775     }
2776
2777   if (BYTES_BIG_ENDIAN)
2778     lbitpos = lnbitsize - lbitsize - lbitpos;
2779
2780   /* Make the mask to be used against the extracted field.  */
2781   mask = build_int_2 (~0, ~0);
2782   TREE_TYPE (mask) = unsigned_type;
2783   force_fit_type (mask, 0);
2784   mask = convert (unsigned_type, mask);
2785   mask = const_binop (LSHIFT_EXPR, mask, size_int (lnbitsize - lbitsize), 0);
2786   mask = const_binop (RSHIFT_EXPR, mask,
2787                       size_int (lnbitsize - lbitsize - lbitpos), 0);
2788
2789   if (! const_p)
2790     /* If not comparing with constant, just rework the comparison
2791        and return.  */
2792     return build (code, compare_type,
2793                   build (BIT_AND_EXPR, unsigned_type,
2794                          make_bit_field_ref (linner, unsigned_type,
2795                                              lnbitsize, lnbitpos, 1),
2796                          mask),
2797                   build (BIT_AND_EXPR, unsigned_type,
2798                          make_bit_field_ref (rinner, unsigned_type,
2799                                              rnbitsize, rnbitpos, 1),
2800                          mask));
2801
2802   /* Otherwise, we are handling the constant case. See if the constant is too
2803      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2804      this not only for its own sake, but to avoid having to test for this
2805      error case below.  If we didn't, we might generate wrong code.
2806
2807      For unsigned fields, the constant shifted right by the field length should
2808      be all zero.  For signed fields, the high-order bits should agree with
2809      the sign bit.  */
2810
2811   if (lunsignedp)
2812     {
2813       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2814                                         convert (unsigned_type, rhs),
2815                                         size_int (lbitsize), 0)))
2816         {
2817           warning ("comparison is always %d due to width of bitfield",
2818                    code == NE_EXPR);
2819           return convert (compare_type,
2820                           (code == NE_EXPR
2821                            ? integer_one_node : integer_zero_node));
2822         }
2823     }
2824   else
2825     {
2826       tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2827                               size_int (lbitsize - 1), 0);
2828       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2829         {
2830           warning ("comparison is always %d due to width of bitfield",
2831                    code == NE_EXPR);
2832           return convert (compare_type,
2833                           (code == NE_EXPR
2834                            ? integer_one_node : integer_zero_node));
2835         }
2836     }
2837
2838   /* Single-bit compares should always be against zero.  */
2839   if (lbitsize == 1 && ! integer_zerop (rhs))
2840     {
2841       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2842       rhs = convert (type, integer_zero_node);
2843     }
2844
2845   /* Make a new bitfield reference, shift the constant over the
2846      appropriate number of bits and mask it with the computed mask
2847      (in case this was a signed field).  If we changed it, make a new one.  */
2848   lhs = make_bit_field_ref (linner, unsigned_type, lnbitsize, lnbitpos, 1);
2849   if (lvolatilep)
2850     {
2851       TREE_SIDE_EFFECTS (lhs) = 1;
2852       TREE_THIS_VOLATILE (lhs) = 1;
2853     }
2854
2855   rhs = fold (const_binop (BIT_AND_EXPR,
2856                            const_binop (LSHIFT_EXPR,
2857                                         convert (unsigned_type, rhs),
2858                                         size_int (lbitpos), 0),
2859                            mask, 0));
2860
2861   return build (code, compare_type,
2862                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2863                 rhs);
2864 }
2865 \f
2866 /* Subroutine for fold_truthop: decode a field reference.
2867
2868    If EXP is a comparison reference, we return the innermost reference.
2869
2870    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2871    set to the starting bit number.
2872
2873    If the innermost field can be completely contained in a mode-sized
2874    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
2875
2876    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2877    otherwise it is not changed.
2878
2879    *PUNSIGNEDP is set to the signedness of the field.
2880
2881    *PMASK is set to the mask used.  This is either contained in a
2882    BIT_AND_EXPR or derived from the width of the field.
2883
2884    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2885
2886    Return 0 if this is not a component reference or is one that we can't
2887    do anything with.  */
2888
2889 static tree
2890 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2891                         pvolatilep, pmask, pand_mask)
2892      tree exp;
2893      int *pbitsize, *pbitpos;
2894      enum machine_mode *pmode;
2895      int *punsignedp, *pvolatilep;
2896      tree *pmask;
2897      tree *pand_mask;
2898 {
2899   tree and_mask = 0;
2900   tree mask, inner, offset;
2901   tree unsigned_type;
2902   int precision;
2903   int alignment;
2904
2905   /* All the optimizations using this function assume integer fields.
2906      There are problems with FP fields since the type_for_size call
2907      below can fail for, e.g., XFmode.  */
2908   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2909     return 0;
2910
2911   STRIP_NOPS (exp);
2912
2913   if (TREE_CODE (exp) == BIT_AND_EXPR)
2914     {
2915       and_mask = TREE_OPERAND (exp, 1);
2916       exp = TREE_OPERAND (exp, 0);
2917       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2918       if (TREE_CODE (and_mask) != INTEGER_CST)
2919         return 0;
2920     }
2921
2922
2923   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2924                                punsignedp, pvolatilep, &alignment);
2925   if ((inner == exp && and_mask == 0)
2926       || *pbitsize < 0 || offset != 0)
2927     return 0;
2928
2929   /* Compute the mask to access the bitfield.  */
2930   unsigned_type = type_for_size (*pbitsize, 1);
2931   precision = TYPE_PRECISION (unsigned_type);
2932
2933   mask = build_int_2 (~0, ~0);
2934   TREE_TYPE (mask) = unsigned_type;
2935   force_fit_type (mask, 0);
2936   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2937   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2938
2939   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
2940   if (and_mask != 0)
2941     mask = fold (build (BIT_AND_EXPR, unsigned_type,
2942                         convert (unsigned_type, and_mask), mask));
2943
2944   *pmask = mask;
2945   *pand_mask = and_mask;
2946   return inner;
2947 }
2948
2949 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2950    bit positions.  */
2951
2952 static int
2953 all_ones_mask_p (mask, size)
2954      tree mask;
2955      int size;
2956 {
2957   tree type = TREE_TYPE (mask);
2958   int precision = TYPE_PRECISION (type);
2959   tree tmask;
2960
2961   tmask = build_int_2 (~0, ~0);
2962   TREE_TYPE (tmask) = signed_type (type);
2963   force_fit_type (tmask, 0);
2964   return
2965     tree_int_cst_equal (mask,
2966                         const_binop (RSHIFT_EXPR,
2967                                      const_binop (LSHIFT_EXPR, tmask,
2968                                                   size_int (precision - size),
2969                                                   0),
2970                                      size_int (precision - size), 0));
2971 }
2972
2973 /* Subroutine for fold_truthop: determine if an operand is simple enough
2974    to be evaluated unconditionally.  */
2975
2976 static int
2977 simple_operand_p (exp)
2978      tree exp;
2979 {
2980   /* Strip any conversions that don't change the machine mode.  */
2981   while ((TREE_CODE (exp) == NOP_EXPR
2982           || TREE_CODE (exp) == CONVERT_EXPR)
2983          && (TYPE_MODE (TREE_TYPE (exp))
2984              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2985     exp = TREE_OPERAND (exp, 0);
2986
2987   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2988           || (TREE_CODE_CLASS (TREE_CODE (exp)) == 'd'
2989               && ! TREE_ADDRESSABLE (exp)
2990               && ! TREE_THIS_VOLATILE (exp)
2991               && ! DECL_NONLOCAL (exp)
2992               /* Don't regard global variables as simple.  They may be
2993                  allocated in ways unknown to the compiler (shared memory,
2994                  #pragma weak, etc).  */
2995               && ! TREE_PUBLIC (exp)
2996               && ! DECL_EXTERNAL (exp)
2997               /* Loading a static variable is unduly expensive, but global
2998                  registers aren't expensive.  */
2999               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3000 }
3001 \f
3002 /* The following functions are subroutines to fold_range_test and allow it to
3003    try to change a logical combination of comparisons into a range test.
3004
3005    For example, both
3006         X == 2 && X == 3 && X == 4 && X == 5
3007    and
3008         X >= 2 && X <= 5
3009    are converted to
3010         (unsigned) (X - 2) <= 3
3011
3012    We describe each set of comparisons as being either inside or outside
3013    a range, using a variable named like IN_P, and then describe the
3014    range with a lower and upper bound.  If one of the bounds is omitted,
3015    it represents either the highest or lowest value of the type.
3016
3017    In the comments below, we represent a range by two numbers in brackets
3018    preceded by a "+" to designate being inside that range, or a "-" to
3019    designate being outside that range, so the condition can be inverted by
3020    flipping the prefix.  An omitted bound is represented by a "-".  For
3021    example, "- [-, 10]" means being outside the range starting at the lowest
3022    possible value and ending at 10, in other words, being greater than 10.
3023    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3024    always false.
3025
3026    We set up things so that the missing bounds are handled in a consistent
3027    manner so neither a missing bound nor "true" and "false" need to be
3028    handled using a special case.  */
3029
3030 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3031    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3032    and UPPER1_P are nonzero if the respective argument is an upper bound
3033    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3034    must be specified for a comparison.  ARG1 will be converted to ARG0's
3035    type if both are specified.  */
3036
3037 static tree
3038 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
3039      enum tree_code code;
3040      tree type;
3041      tree arg0, arg1;
3042      int upper0_p, upper1_p;
3043 {
3044   tree tem;
3045   int result;
3046   int sgn0, sgn1;
3047
3048   /* If neither arg represents infinity, do the normal operation.
3049      Else, if not a comparison, return infinity.  Else handle the special
3050      comparison rules. Note that most of the cases below won't occur, but
3051      are handled for consistency.  */
3052
3053   if (arg0 != 0 && arg1 != 0)
3054     {
3055       tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
3056                          arg0, convert (TREE_TYPE (arg0), arg1)));
3057       STRIP_NOPS (tem);
3058       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3059     }
3060
3061   if (TREE_CODE_CLASS (code) != '<')
3062     return 0;
3063
3064   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3065      for neither.  In real maths, we cannot assume open ended ranges are
3066      the same. But, this is computer arithmetic, where numbers are finite.
3067      We can therefore make the transformation of any unbounded range with
3068      the value Z, Z being greater than any representable number. This permits
3069      us to treat unbounded ranges as equal. */
3070   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3071   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3072   switch (code)
3073     {
3074     case EQ_EXPR:
3075       result = sgn0 == sgn1;
3076       break;
3077     case NE_EXPR:
3078       result = sgn0 != sgn1;
3079       break;
3080     case LT_EXPR:
3081       result = sgn0 < sgn1;
3082       break;
3083     case LE_EXPR:
3084       result = sgn0 <= sgn1;
3085       break;
3086     case GT_EXPR:
3087       result = sgn0 > sgn1;
3088       break;
3089     case GE_EXPR:
3090       result = sgn0 >= sgn1;
3091       break;
3092     default:
3093       abort ();
3094     }
3095
3096   return convert (type, result ? integer_one_node : integer_zero_node);
3097 }
3098 \f
3099 /* Given EXP, a logical expression, set the range it is testing into
3100    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3101    actually being tested.  *PLOW and *PHIGH will have be made the same type
3102    as the returned expression.  If EXP is not a comparison, we will most
3103    likely not be returning a useful value and range.  */
3104
3105 static tree
3106 make_range (exp, pin_p, plow, phigh)
3107      tree exp;
3108      int *pin_p;
3109      tree *plow, *phigh;
3110 {
3111   enum tree_code code;
3112   tree arg0, arg1, type = NULL_TREE;
3113   tree orig_type = NULL_TREE;
3114   int in_p, n_in_p;
3115   tree low, high, n_low, n_high;
3116
3117   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3118      and see if we can refine the range.  Some of the cases below may not
3119      happen, but it doesn't seem worth worrying about this.  We "continue"
3120      the outer loop when we've changed something; otherwise we "break"
3121      the switch, which will "break" the while.  */
3122
3123   in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
3124
3125   while (1)
3126     {
3127       code = TREE_CODE (exp);
3128
3129       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3130         {
3131           arg0 = TREE_OPERAND (exp, 0);
3132           if (TREE_CODE_CLASS (code) == '<'
3133               || TREE_CODE_CLASS (code) == '1'
3134               || TREE_CODE_CLASS (code) == '2')
3135             type = TREE_TYPE (arg0);
3136           if (TREE_CODE_CLASS (code) == '2'
3137               || TREE_CODE_CLASS (code) == '<'
3138               || (TREE_CODE_CLASS (code) == 'e'
3139                   && tree_code_length[(int) code] > 1))
3140             arg1 = TREE_OPERAND (exp, 1);
3141         }
3142
3143       /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
3144          lose a cast by accident.  */
3145       if (type != NULL_TREE && orig_type == NULL_TREE)
3146         orig_type = type;
3147
3148       switch (code)
3149         {
3150         case TRUTH_NOT_EXPR:
3151           in_p = ! in_p, exp = arg0;
3152           continue;
3153
3154         case EQ_EXPR: case NE_EXPR:
3155         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3156           /* We can only do something if the range is testing for zero
3157              and if the second operand is an integer constant.  Note that
3158              saying something is "in" the range we make is done by
3159              complementing IN_P since it will set in the initial case of
3160              being not equal to zero; "out" is leaving it alone.  */
3161           if (low == 0 || high == 0
3162               || ! integer_zerop (low) || ! integer_zerop (high)
3163               || TREE_CODE (arg1) != INTEGER_CST)
3164             break;
3165
3166           switch (code)
3167             {
3168             case NE_EXPR:  /* - [c, c]  */
3169               low = high = arg1;
3170               break;
3171             case EQ_EXPR:  /* + [c, c]  */
3172               in_p = ! in_p, low = high = arg1;
3173               break;
3174             case GT_EXPR:  /* - [-, c] */
3175               low = 0, high = arg1;
3176               break;
3177             case GE_EXPR:  /* + [c, -] */
3178               in_p = ! in_p, low = arg1, high = 0;
3179               break;
3180             case LT_EXPR:  /* - [c, -] */
3181               low = arg1, high = 0;
3182               break;
3183             case LE_EXPR:  /* + [-, c] */
3184               in_p = ! in_p, low = 0, high = arg1;
3185               break;
3186             default:
3187               abort ();
3188             }
3189
3190           exp = arg0;
3191
3192           /* If this is an unsigned comparison, we also know that EXP is
3193              greater than or equal to zero.  We base the range tests we make
3194              on that fact, so we record it here so we can parse existing
3195              range tests.  */
3196           if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
3197             {
3198               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
3199                                   1, convert (type, integer_zero_node),
3200                                   NULL_TREE))
3201                 break;
3202
3203               in_p = n_in_p, low = n_low, high = n_high;
3204
3205               /* If the high bound is missing, reverse the range so it
3206                  goes from zero to the low bound minus 1.  */
3207               if (high == 0)
3208                 {
3209                   in_p = ! in_p;
3210                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3211                                       integer_one_node, 0);
3212                   low = convert (type, integer_zero_node);
3213                 }
3214             }
3215           continue;
3216
3217         case NEGATE_EXPR:
3218           /* (-x) IN [a,b] -> x in [-b, -a]  */
3219           n_low = range_binop (MINUS_EXPR, type,
3220                                convert (type, integer_zero_node), 0, high, 1);
3221           n_high = range_binop (MINUS_EXPR, type,
3222                                 convert (type, integer_zero_node), 0, low, 0);
3223           low = n_low, high = n_high;
3224           exp = arg0;
3225           continue;
3226
3227         case BIT_NOT_EXPR:
3228           /* ~ X -> -X - 1  */
3229           exp = build (MINUS_EXPR, type, build1 (NEGATE_EXPR, type, arg0),
3230                        convert (type, integer_one_node));
3231           continue;
3232
3233         case PLUS_EXPR:  case MINUS_EXPR:
3234           if (TREE_CODE (arg1) != INTEGER_CST)
3235             break;
3236
3237           /* If EXP is signed, any overflow in the computation is undefined,
3238              so we don't worry about it so long as our computations on
3239              the bounds don't overflow.  For unsigned, overflow is defined
3240              and this is exactly the right thing.  */
3241           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3242                                type, low, 0, arg1, 0);
3243           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3244                                 type, high, 1, arg1, 0);
3245           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3246               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3247             break;
3248
3249           /* Check for an unsigned range which has wrapped around the maximum
3250              value thus making n_high < n_low, and normalize it.  */
3251           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3252             {
3253               low = range_binop (PLUS_EXPR, type, n_high, 0,
3254                                  integer_one_node, 0);
3255               high = range_binop (MINUS_EXPR, type, n_low, 0,
3256                                  integer_one_node, 0);
3257               in_p = ! in_p;
3258             }
3259           else
3260             low = n_low, high = n_high;
3261
3262           exp = arg0;
3263           continue;
3264
3265         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3266           if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3267             break;
3268
3269           if (! INTEGRAL_TYPE_P (type)
3270               || (low != 0 && ! int_fits_type_p (low, type))
3271               || (high != 0 && ! int_fits_type_p (high, type)))
3272             break;
3273
3274           n_low = low, n_high = high;
3275
3276           if (n_low != 0)
3277             n_low = convert (type, n_low);
3278
3279           if (n_high != 0)
3280             n_high = convert (type, n_high);
3281
3282           /* If we're converting from an unsigned to a signed type,
3283              we will be doing the comparison as unsigned.  The tests above
3284              have already verified that LOW and HIGH are both positive.
3285
3286              So we have to make sure that the original unsigned value will
3287              be interpreted as positive.  */
3288           if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3289             {
3290               tree equiv_type = type_for_mode (TYPE_MODE (type), 1);
3291               tree high_positive;
3292
3293               /* A range without an upper bound is, naturally, unbounded.
3294                  Since convert would have cropped a very large value, use
3295                   the max value for the destination type.  */
3296
3297               high_positive = TYPE_MAX_VALUE (equiv_type);
3298               if (!high_positive)
3299                 {
3300                   high_positive = TYPE_MAX_VALUE (type);
3301                   if (!high_positive)
3302                     abort();
3303                 }
3304               high_positive = fold (build (RSHIFT_EXPR, type,
3305                                            convert (type, high_positive),
3306                                            convert (type, integer_one_node)));
3307
3308               /* If the low bound is specified, "and" the range with the
3309                  range for which the original unsigned value will be
3310                  positive.  */
3311               if (low != 0)
3312                 {
3313                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3314                                       1, n_low, n_high,
3315                                       1, convert (type, integer_zero_node),
3316                                       high_positive))
3317                     break;
3318
3319                   in_p = (n_in_p == in_p);
3320                 }
3321               else
3322                 {
3323                   /* Otherwise, "or" the range with the range of the input
3324                      that will be interpreted as negative.  */
3325                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3326                                       0, n_low, n_high,
3327                                       1, convert (type, integer_zero_node),
3328                                       high_positive))
3329                     break;
3330
3331                   in_p = (in_p != n_in_p);
3332                 }
3333             }
3334
3335           exp = arg0;
3336           low = n_low, high = n_high;
3337           continue;
3338
3339         default:
3340           break;
3341         }
3342
3343       break;
3344     }
3345
3346   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3347   if (TREE_CODE (exp) == INTEGER_CST)
3348     {
3349       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3350                                                  exp, 0, low, 0))
3351                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3352                                                     exp, 1, high, 1)));
3353       low = high = 0;
3354       exp = 0;
3355     }
3356
3357   *pin_p = in_p, *plow = low, *phigh = high;
3358   return exp;
3359 }
3360 \f
3361 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3362    type, TYPE, return an expression to test if EXP is in (or out of, depending
3363    on IN_P) the range.  */
3364
3365 static tree
3366 build_range_check (type, exp, in_p, low, high)
3367      tree type;
3368      tree exp;
3369      int in_p;
3370      tree low, high;
3371 {
3372   tree etype = TREE_TYPE (exp);
3373   tree utype, value;
3374
3375   if (! in_p
3376       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3377     return invert_truthvalue (value);
3378
3379   else if (low == 0 && high == 0)
3380     return convert (type, integer_one_node);
3381
3382   else if (low == 0)
3383     return fold (build (LE_EXPR, type, exp, high));
3384
3385   else if (high == 0)
3386     return fold (build (GE_EXPR, type, exp, low));
3387
3388   else if (operand_equal_p (low, high, 0))
3389     return fold (build (EQ_EXPR, type, exp, low));
3390
3391   else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3392     return build_range_check (type, exp, 1, 0, high);
3393
3394   else if (integer_zerop (low))
3395     {
3396       utype = unsigned_type (etype);
3397       return build_range_check (type, convert (utype, exp), 1, 0,
3398                                 convert (utype, high));
3399     }
3400
3401   else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3402            && ! TREE_OVERFLOW (value))
3403     return build_range_check (type,
3404                               fold (build (MINUS_EXPR, etype, exp, low)),
3405                               1, convert (etype, integer_zero_node), value);
3406   else
3407     return 0;
3408 }
3409 \f
3410 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3411    can, 0 if we can't.  Set the output range into the specified parameters.  */
3412
3413 static int
3414 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3415      int *pin_p;
3416      tree *plow, *phigh;
3417      int in0_p, in1_p;
3418      tree low0, high0, low1, high1;
3419 {
3420   int no_overlap;
3421   int subset;
3422   int temp;
3423   tree tem;
3424   int in_p;
3425   tree low, high;
3426   int lowequal = ((low0 == 0 && low1 == 0)
3427                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3428                                                 low0, 0, low1, 0)));
3429   int highequal = ((high0 == 0 && high1 == 0)
3430                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3431                                                  high0, 1, high1, 1)));
3432
3433   /* Make range 0 be the range that starts first, or ends last if they
3434      start at the same value.  Swap them if it isn't.  */
3435   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3436                                  low0, 0, low1, 0))
3437       || (lowequal
3438           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3439                                         high1, 1, high0, 1))))
3440     {
3441       temp = in0_p, in0_p = in1_p, in1_p = temp;
3442       tem = low0, low0 = low1, low1 = tem;
3443       tem = high0, high0 = high1, high1 = tem;
3444     }
3445
3446   /* Now flag two cases, whether the ranges are disjoint or whether the
3447      second range is totally subsumed in the first.  Note that the tests
3448      below are simplified by the ones above.  */
3449   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3450                                           high0, 1, low1, 0));
3451   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3452                                       high1, 1, high0, 1));
3453
3454   /* We now have four cases, depending on whether we are including or
3455      excluding the two ranges.  */
3456   if (in0_p && in1_p)
3457     {
3458       /* If they don't overlap, the result is false.  If the second range
3459          is a subset it is the result.  Otherwise, the range is from the start
3460          of the second to the end of the first.  */
3461       if (no_overlap)
3462         in_p = 0, low = high = 0;
3463       else if (subset)
3464         in_p = 1, low = low1, high = high1;
3465       else
3466         in_p = 1, low = low1, high = high0;
3467     }
3468
3469   else if (in0_p && ! in1_p)
3470     {
3471       /* If they don't overlap, the result is the first range.  If they are
3472          equal, the result is false.  If the second range is a subset of the
3473          first, and the ranges begin at the same place, we go from just after
3474          the end of the first range to the end of the second.  If the second
3475          range is not a subset of the first, or if it is a subset and both
3476          ranges end at the same place, the range starts at the start of the
3477          first range and ends just before the second range.
3478          Otherwise, we can't describe this as a single range.  */
3479       if (no_overlap)
3480         in_p = 1, low = low0, high = high0;
3481       else if (lowequal && highequal)
3482         in_p = 0, low = high = 0;
3483       else if (subset && lowequal)
3484         {
3485           in_p = 1, high = high0;
3486           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3487                              integer_one_node, 0);
3488         }
3489       else if (! subset || highequal)
3490         {
3491           in_p = 1, low = low0;
3492           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3493                               integer_one_node, 0);
3494         }
3495       else
3496         return 0;
3497     }
3498
3499   else if (! in0_p && in1_p)
3500     {
3501       /* If they don't overlap, the result is the second range.  If the second
3502          is a subset of the first, the result is false.  Otherwise,
3503          the range starts just after the first range and ends at the
3504          end of the second.  */
3505       if (no_overlap)
3506         in_p = 1, low = low1, high = high1;
3507       else if (subset)
3508         in_p = 0, low = high = 0;
3509       else
3510         {
3511           in_p = 1, high = high1;
3512           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3513                              integer_one_node, 0);
3514         }
3515     }
3516
3517   else
3518     {
3519       /* The case where we are excluding both ranges.  Here the complex case
3520          is if they don't overlap.  In that case, the only time we have a
3521          range is if they are adjacent.  If the second is a subset of the
3522          first, the result is the first.  Otherwise, the range to exclude
3523          starts at the beginning of the first range and ends at the end of the
3524          second.  */
3525       if (no_overlap)
3526         {
3527           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3528                                          range_binop (PLUS_EXPR, NULL_TREE,
3529                                                       high0, 1,
3530                                                       integer_one_node, 1),
3531                                          1, low1, 0)))
3532             in_p = 0, low = low0, high = high1;
3533           else
3534             return 0;
3535         }
3536       else if (subset)
3537         in_p = 0, low = low0, high = high0;
3538       else
3539         in_p = 0, low = low0, high = high1;
3540     }
3541
3542   *pin_p = in_p, *plow = low, *phigh = high;
3543   return 1;
3544 }
3545 \f
3546 /* EXP is some logical combination of boolean tests.  See if we can
3547    merge it into some range test.  Return the new tree if so.  */
3548
3549 static tree
3550 fold_range_test (exp)
3551      tree exp;
3552 {
3553   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3554                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3555   int in0_p, in1_p, in_p;
3556   tree low0, low1, low, high0, high1, high;
3557   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3558   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3559   tree tem;
3560
3561   /* If this is an OR operation, invert both sides; we will invert
3562      again at the end.  */
3563   if (or_op)
3564     in0_p = ! in0_p, in1_p = ! in1_p;
3565
3566   /* If both expressions are the same, if we can merge the ranges, and we
3567      can build the range test, return it or it inverted.  If one of the
3568      ranges is always true or always false, consider it to be the same
3569      expression as the other.  */
3570   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3571       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3572                        in1_p, low1, high1)
3573       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3574                                          lhs != 0 ? lhs
3575                                          : rhs != 0 ? rhs : integer_zero_node,
3576                                          in_p, low, high))))
3577     return or_op ? invert_truthvalue (tem) : tem;
3578
3579   /* On machines where the branch cost is expensive, if this is a
3580      short-circuited branch and the underlying object on both sides
3581      is the same, make a non-short-circuit operation.  */
3582   else if (BRANCH_COST >= 2
3583            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3584                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3585            && operand_equal_p (lhs, rhs, 0))
3586     {
3587       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3588          unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3589          which cases we can't do this.  */
3590       if (simple_operand_p (lhs))
3591         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3592                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3593                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3594                       TREE_OPERAND (exp, 1));
3595
3596       else if (current_function_decl != 0
3597                && ! contains_placeholder_p (lhs))
3598         {
3599           tree common = save_expr (lhs);
3600
3601           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3602                                              or_op ? ! in0_p : in0_p,
3603                                              low0, high0))
3604               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3605                                                  or_op ? ! in1_p : in1_p,
3606                                                  low1, high1))))
3607             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3608                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3609                           TREE_TYPE (exp), lhs, rhs);
3610         }
3611     }
3612
3613   return 0;
3614 }
3615 \f
3616 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3617    bit value.  Arrange things so the extra bits will be set to zero if and
3618    only if C is signed-extended to its full width.  If MASK is nonzero,
3619    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3620
3621 static tree
3622 unextend (c, p, unsignedp, mask)
3623      tree c;
3624      int p;
3625      int unsignedp;
3626      tree mask;
3627 {
3628   tree type = TREE_TYPE (c);
3629   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3630   tree temp;
3631
3632   if (p == modesize || unsignedp)
3633     return c;
3634
3635   /* We work by getting just the sign bit into the low-order bit, then
3636      into the high-order bit, then sign-extend.  We then XOR that value
3637      with C.  */
3638   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3639   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3640
3641   /* We must use a signed type in order to get an arithmetic right shift.
3642      However, we must also avoid introducing accidental overflows, so that
3643      a subsequent call to integer_zerop will work.  Hence we must
3644      do the type conversion here.  At this point, the constant is either
3645      zero or one, and the conversion to a signed type can never overflow.
3646      We could get an overflow if this conversion is done anywhere else.  */
3647   if (TREE_UNSIGNED (type))
3648     temp = convert (signed_type (type), temp);
3649
3650   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3651   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3652   if (mask != 0)
3653     temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3654   /* If necessary, convert the type back to match the type of C.  */
3655   if (TREE_UNSIGNED (type))
3656     temp = convert (type, temp);
3657
3658   return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3659 }
3660 \f
3661 /* Find ways of folding logical expressions of LHS and RHS:
3662    Try to merge two comparisons to the same innermost item.
3663    Look for range tests like "ch >= '0' && ch <= '9'".
3664    Look for combinations of simple terms on machines with expensive branches
3665    and evaluate the RHS unconditionally.
3666
3667    For example, if we have p->a == 2 && p->b == 4 and we can make an
3668    object large enough to span both A and B, we can do this with a comparison
3669    against the object ANDed with the a mask.
3670
3671    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3672    operations to do this with one comparison.
3673
3674    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3675    function and the one above.
3676
3677    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3678    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3679
3680    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3681    two operands.
3682
3683    We return the simplified tree or 0 if no optimization is possible.  */
3684
3685 static tree
3686 fold_truthop (code, truth_type, lhs, rhs)
3687      enum tree_code code;
3688      tree truth_type, lhs, rhs;
3689 {
3690   /* If this is the "or" of two comparisons, we can do something if we
3691      the comparisons are NE_EXPR.  If this is the "and", we can do something
3692      if the comparisons are EQ_EXPR.  I.e.,
3693         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3694
3695      WANTED_CODE is this operation code.  For single bit fields, we can
3696      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3697      comparison for one-bit fields.  */
3698
3699   enum tree_code wanted_code;
3700   enum tree_code lcode, rcode;
3701   tree ll_arg, lr_arg, rl_arg, rr_arg;
3702   tree ll_inner, lr_inner, rl_inner, rr_inner;
3703   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3704   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3705   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3706   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3707   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3708   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3709   enum machine_mode lnmode, rnmode;
3710   tree ll_mask, lr_mask, rl_mask, rr_mask;
3711   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3712   tree l_const, r_const;
3713   tree type, result;
3714   int first_bit, end_bit;
3715   int volatilep;
3716
3717   /* Start by getting the comparison codes.  Fail if anything is volatile.
3718      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3719      it were surrounded with a NE_EXPR.  */
3720
3721   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3722     return 0;
3723
3724   lcode = TREE_CODE (lhs);
3725   rcode = TREE_CODE (rhs);
3726
3727   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3728     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3729
3730   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3731     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3732
3733   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3734     return 0;
3735
3736   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3737           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3738
3739   ll_arg = TREE_OPERAND (lhs, 0);
3740   lr_arg = TREE_OPERAND (lhs, 1);
3741   rl_arg = TREE_OPERAND (rhs, 0);
3742   rr_arg = TREE_OPERAND (rhs, 1);
3743
3744   /* If the RHS can be evaluated unconditionally and its operands are
3745      simple, it wins to evaluate the RHS unconditionally on machines
3746      with expensive branches.  In this case, this isn't a comparison
3747      that can be merged.  */
3748
3749   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
3750      are with zero (tmw).  */
3751
3752   if (BRANCH_COST >= 2
3753       && INTEGRAL_TYPE_P (TREE_TYPE (rhs))
3754       && simple_operand_p (rl_arg)
3755       && simple_operand_p (rr_arg))
3756     return build (code, truth_type, lhs, rhs);
3757
3758   /* See if the comparisons can be merged.  Then get all the parameters for
3759      each side.  */
3760
3761   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3762       || (rcode != EQ_EXPR && rcode != NE_EXPR))
3763     return 0;
3764
3765   volatilep = 0;
3766   ll_inner = decode_field_reference (ll_arg,
3767                                      &ll_bitsize, &ll_bitpos, &ll_mode,
3768                                      &ll_unsignedp, &volatilep, &ll_mask,
3769                                      &ll_and_mask);
3770   lr_inner = decode_field_reference (lr_arg,
3771                                      &lr_bitsize, &lr_bitpos, &lr_mode,
3772                                      &lr_unsignedp, &volatilep, &lr_mask,
3773                                      &lr_and_mask);
3774   rl_inner = decode_field_reference (rl_arg,
3775                                      &rl_bitsize, &rl_bitpos, &rl_mode,
3776                                      &rl_unsignedp, &volatilep, &rl_mask,
3777                                      &rl_and_mask);
3778   rr_inner = decode_field_reference (rr_arg,
3779                                      &rr_bitsize, &rr_bitpos, &rr_mode,
3780                                      &rr_unsignedp, &volatilep, &rr_mask,
3781                                      &rr_and_mask);
3782
3783   /* It must be true that the inner operation on the lhs of each
3784      comparison must be the same if we are to be able to do anything.
3785      Then see if we have constants.  If not, the same must be true for
3786      the rhs's.  */
3787   if (volatilep || ll_inner == 0 || rl_inner == 0
3788       || ! operand_equal_p (ll_inner, rl_inner, 0))
3789     return 0;
3790
3791   if (TREE_CODE (lr_arg) == INTEGER_CST
3792       && TREE_CODE (rr_arg) == INTEGER_CST)
3793     l_const = lr_arg, r_const = rr_arg;
3794   else if (lr_inner == 0 || rr_inner == 0
3795            || ! operand_equal_p (lr_inner, rr_inner, 0))
3796     return 0;
3797   else
3798     l_const = r_const = 0;
3799
3800   /* If either comparison code is not correct for our logical operation,
3801      fail.  However, we can convert a one-bit comparison against zero into
3802      the opposite comparison against that bit being set in the field.  */
3803
3804   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3805   if (lcode != wanted_code)
3806     {
3807       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3808         {
3809           if (ll_unsignedp || tree_log2 (ll_mask) + 1 < ll_bitsize)
3810             l_const = ll_mask;
3811         else
3812           /* Since ll_arg is a single bit bit mask, we can sign extend
3813              it appropriately with a NEGATE_EXPR.
3814              l_const is made a signed value here, but since for l_const != NULL
3815              lr_unsignedp is not used, we don't need to clear the latter.  */
3816           l_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (ll_arg),
3817                                   convert (TREE_TYPE (ll_arg), ll_mask)));
3818         }
3819       else
3820         return 0;
3821     }
3822
3823   if (rcode != wanted_code)
3824     {
3825       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3826         {
3827           if (rl_unsignedp || tree_log2 (rl_mask) + 1 < rl_bitsize)
3828             r_const = rl_mask;
3829         else
3830           /* This is analogous to the code for l_const above.  */
3831           r_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (rl_arg),
3832                                   convert (TREE_TYPE (rl_arg), rl_mask)));
3833         }
3834       else
3835         return 0;
3836     }
3837
3838   /* See if we can find a mode that contains both fields being compared on
3839      the left.  If we can't, fail.  Otherwise, update all constants and masks
3840      to be relative to a field of that size.  */
3841   first_bit = MIN (ll_bitpos, rl_bitpos);
3842   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3843   lnmode = get_best_mode (end_bit - first_bit, first_bit,
3844                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3845                           volatilep);
3846   if (lnmode == VOIDmode)
3847     return 0;
3848
3849   lnbitsize = GET_MODE_BITSIZE (lnmode);
3850   lnbitpos = first_bit & ~ (lnbitsize - 1);
3851   type = type_for_size (lnbitsize, 1);
3852   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3853
3854   if (BYTES_BIG_ENDIAN)
3855     {
3856       xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3857       xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3858     }
3859
3860   ll_mask = const_binop (LSHIFT_EXPR, convert (type, ll_mask),
3861                          size_int (xll_bitpos), 0);
3862   rl_mask = const_binop (LSHIFT_EXPR, convert (type, rl_mask),
3863                          size_int (xrl_bitpos), 0);
3864
3865   if (l_const)
3866     {
3867       l_const = convert (type, l_const);
3868       l_const = unextend (l_const,  ll_bitsize, ll_unsignedp, ll_and_mask);
3869       l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3870       if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3871                                         fold (build1 (BIT_NOT_EXPR,
3872                                                       type, ll_mask)),
3873                                         0)))
3874         {
3875           warning ("comparison is always %d", wanted_code == NE_EXPR);
3876
3877           return convert (truth_type,
3878                           wanted_code == NE_EXPR
3879                           ? integer_one_node : integer_zero_node);
3880         }
3881     }
3882   if (r_const)
3883     {
3884       r_const = convert (type, r_const);
3885       r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3886       r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3887       if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3888                                         fold (build1 (BIT_NOT_EXPR,
3889                                                       type, rl_mask)),
3890                                         0)))
3891         {
3892           warning ("comparison is always %d", wanted_code == NE_EXPR);
3893
3894           return convert (truth_type,
3895                           wanted_code == NE_EXPR
3896                           ? integer_one_node : integer_zero_node);
3897         }
3898     }
3899
3900   /* If the right sides are not constant, do the same for it.  Also,
3901      disallow this optimization if a size or signedness mismatch occurs
3902      between the left and right sides.  */
3903   if (l_const == 0)
3904     {
3905       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3906           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3907           /* Make sure the two fields on the right
3908              correspond to the left without being swapped.  */
3909           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3910         return 0;
3911
3912       first_bit = MIN (lr_bitpos, rr_bitpos);
3913       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3914       rnmode = get_best_mode (end_bit - first_bit, first_bit,
3915                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3916                               volatilep);
3917       if (rnmode == VOIDmode)
3918         return 0;
3919
3920       rnbitsize = GET_MODE_BITSIZE (rnmode);
3921       rnbitpos = first_bit & ~ (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 (type, lr_mask),
3931                              size_int (xlr_bitpos), 0);
3932       rr_mask = const_binop (LSHIFT_EXPR, convert (type, 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 masks agree,
3937          and the bits being compared are in the same position, then
3938          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 (operand_equal_p (ll_mask, lr_mask, 0)
3943           && lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3944         {
3945           lhs = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
3946                                     ll_unsignedp || rl_unsignedp);
3947           rhs = make_bit_field_ref (lr_inner, type, rnbitsize, rnbitpos,
3948                                     lr_unsignedp || rr_unsignedp);
3949           if (! all_ones_mask_p (ll_mask, lnbitsize))
3950             {
3951               lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3952               rhs = build (BIT_AND_EXPR, type, rhs, ll_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       if ((ll_bitsize + ll_bitpos == rl_bitpos
3961            && lr_bitsize + lr_bitpos == rr_bitpos)
3962           || (ll_bitpos == rl_bitpos + rl_bitsize
3963               && lr_bitpos == rr_bitpos + rr_bitsize))
3964         return build (wanted_code, truth_type,
3965                       make_bit_field_ref (ll_inner, type,
3966                                           ll_bitsize + rl_bitsize,
3967                                           MIN (ll_bitpos, rl_bitpos),
3968                                           ll_unsignedp),
3969                       make_bit_field_ref (lr_inner, type,
3970                                           lr_bitsize + rr_bitsize,
3971                                           MIN (lr_bitpos, rr_bitpos),
3972                                           lr_unsignedp));
3973
3974       return 0;
3975     }
3976
3977   /* Handle the case of comparisons with constants.  If there is something in
3978      common between the masks, those bits of the constants must be the same.
3979      If not, the condition is always false.  Test for this to avoid generating
3980      incorrect code below.  */
3981   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3982   if (! integer_zerop (result)
3983       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3984                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3985     {
3986       if (wanted_code == NE_EXPR)
3987         {
3988           warning ("`or' of unmatched not-equal tests is always 1");
3989           return convert (truth_type, integer_one_node);
3990         }
3991       else
3992         {
3993           warning ("`and' of mutually exclusive equal-tests is always 0");
3994           return convert (truth_type, integer_zero_node);
3995         }
3996     }
3997
3998   /* Construct the expression we will return.  First get the component
3999      reference we will make.  Unless the mask is all ones the width of
4000      that field, perform the mask operation.  Then compare with the
4001      merged constant.  */
4002   result = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
4003                                ll_unsignedp || rl_unsignedp);
4004
4005   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
4006   if (! all_ones_mask_p (ll_mask, lnbitsize))
4007     result = build (BIT_AND_EXPR, type, result, ll_mask);
4008
4009   return build (wanted_code, truth_type, result,
4010                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
4011 }
4012 \f
4013 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4014    S, a SAVE_EXPR, return the expression actually being evaluated.   Note
4015    that we may sometimes modify the tree.  */
4016
4017 static tree
4018 strip_compound_expr (t, s)
4019      tree t;
4020      tree s;
4021 {
4022   enum tree_code code = TREE_CODE (t);
4023
4024   /* See if this is the COMPOUND_EXPR we want to eliminate.  */
4025   if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4026       && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4027     return TREE_OPERAND (t, 1);
4028
4029   /* See if this is a COND_EXPR or a simple arithmetic operator.   We
4030      don't bother handling any other types.  */
4031   else if (code == COND_EXPR)
4032     {
4033       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4034       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4035       TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4036     }
4037   else if (TREE_CODE_CLASS (code) == '1')
4038     TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4039   else if (TREE_CODE_CLASS (code) == '<'
4040            || TREE_CODE_CLASS (code) == '2')
4041     {
4042       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4043       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4044     }
4045
4046   return t;
4047 }
4048 \f
4049 /* Return a node which has the indicated constant VALUE (either 0 or
4050    1), and is of the indicated TYPE.  */
4051
4052 static tree
4053 constant_boolean_node (value, type)
4054      int value;
4055      tree type;
4056 {
4057   if (type == integer_type_node)
4058     return value ? integer_one_node : integer_zero_node;
4059   else if (TREE_CODE (type) == BOOLEAN_TYPE)
4060     return truthvalue_conversion (value ? integer_one_node :
4061                                   integer_zero_node);
4062   else
4063     {
4064       tree t = build_int_2 (value, 0);
4065       TREE_TYPE (t) = type;
4066       return t;
4067     }
4068 }
4069
4070 /* Utility function for the following routine, to see how complex a nesting of
4071    COND_EXPRs can be.  EXPR is the expression and LIMIT is a count beyond which
4072    we don't care (to avoid spending too much time on complex expressions.).  */
4073
4074 static int
4075 count_cond (expr, lim)
4076      tree expr;
4077      int lim;
4078 {
4079   int true, false;
4080
4081   if (TREE_CODE (expr) != COND_EXPR)
4082     return 0;
4083   else if (lim <= 0)
4084     return 0;
4085
4086   true = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4087   false = count_cond (TREE_OPERAND (expr, 2), lim - 1 - true);
4088   return MIN (lim, 1 + true + false);
4089 }
4090 \f
4091 /* Perform constant folding and related simplification of EXPR.
4092    The related simplifications include x*1 => x, x*0 => 0, etc.,
4093    and application of the associative law.
4094    NOP_EXPR conversions may be removed freely (as long as we
4095    are careful not to change the C type of the overall expression)
4096    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4097    but we can constant-fold them if they have constant operands.  */
4098
4099 tree
4100 fold (expr)
4101      tree expr;
4102 {
4103   register tree t = expr;
4104   tree t1 = NULL_TREE;
4105   tree tem;
4106   tree type = TREE_TYPE (expr);
4107   register tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4108   register enum tree_code code = TREE_CODE (t);
4109   register int kind;
4110   int invert;
4111
4112   /* WINS will be nonzero when the switch is done
4113      if all operands are constant.  */
4114
4115   int wins = 1;
4116
4117   /* Don't try to process an RTL_EXPR since its operands aren't trees.
4118      Likewise for a SAVE_EXPR that's already been evaluated.  */
4119   if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t)) != 0)
4120     return t;
4121
4122   /* Return right away if already constant.  */
4123   if (TREE_CONSTANT (t))
4124     {
4125       if (code == CONST_DECL)
4126         return DECL_INITIAL (t);
4127       return t;
4128     }
4129
4130 #ifdef MAX_INTEGER_COMPUTATION_MODE
4131   check_max_integer_computation_mode (expr);
4132 #endif
4133
4134   kind = TREE_CODE_CLASS (code);
4135   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4136     {
4137       tree subop;
4138
4139       /* Special case for conversion ops that can have fixed point args.  */
4140       arg0 = TREE_OPERAND (t, 0);
4141
4142       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
4143       if (arg0 != 0)
4144         STRIP_TYPE_NOPS (arg0);
4145
4146       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4147         subop = TREE_REALPART (arg0);
4148       else
4149         subop = arg0;
4150
4151       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4152 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4153           && TREE_CODE (subop) != REAL_CST
4154 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4155           )
4156         /* Note that TREE_CONSTANT isn't enough:
4157            static var addresses are constant but we can't
4158            do arithmetic on them.  */
4159         wins = 0;
4160     }
4161   else if (kind == 'e' || kind == '<'
4162            || kind == '1' || kind == '2' || kind == 'r')
4163     {
4164       register int len = tree_code_length[(int) code];
4165       register int i;
4166       for (i = 0; i < len; i++)
4167         {
4168           tree op = TREE_OPERAND (t, i);
4169           tree subop;
4170
4171           if (op == 0)
4172             continue;           /* Valid for CALL_EXPR, at least.  */
4173
4174           if (kind == '<' || code == RSHIFT_EXPR)
4175             {
4176               /* Signedness matters here.  Perhaps we can refine this
4177                  later.  */
4178               STRIP_TYPE_NOPS (op);
4179             }
4180           else
4181             {
4182               /* Strip any conversions that don't change the mode.  */
4183               STRIP_NOPS (op);
4184             }
4185
4186           if (TREE_CODE (op) == COMPLEX_CST)
4187             subop = TREE_REALPART (op);
4188           else
4189             subop = op;
4190
4191           if (TREE_CODE (subop) != INTEGER_CST
4192 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4193               && TREE_CODE (subop) != REAL_CST
4194 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4195               )
4196             /* Note that TREE_CONSTANT isn't enough:
4197                static var addresses are constant but we can't
4198                do arithmetic on them.  */
4199             wins = 0;
4200
4201           if (i == 0)
4202             arg0 = op;
4203           else if (i == 1)
4204             arg1 = op;
4205         }
4206     }
4207
4208   /* If this is a commutative operation, and ARG0 is a constant, move it
4209      to ARG1 to reduce the number of tests below.  */
4210   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4211        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4212        || code == BIT_AND_EXPR)
4213       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4214     {
4215       tem = arg0; arg0 = arg1; arg1 = tem;
4216
4217       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4218       TREE_OPERAND (t, 1) = tem;
4219     }
4220
4221   /* Now WINS is set as described above,
4222      ARG0 is the first operand of EXPR,
4223      and ARG1 is the second operand (if it has more than one operand).
4224
4225      First check for cases where an arithmetic operation is applied to a
4226      compound, conditional, or comparison operation.  Push the arithmetic
4227      operation inside the compound or conditional to see if any folding
4228      can then be done.  Convert comparison to conditional for this purpose.
4229      The also optimizes non-constant cases that used to be done in
4230      expand_expr.
4231
4232      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
4233      one of the operands is a comparison and the other is a comparison, a
4234      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
4235      code below would make the expression more complex.  Change it to a
4236      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
4237      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
4238
4239   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4240        || code == EQ_EXPR || code == NE_EXPR)
4241       && ((truth_value_p (TREE_CODE (arg0))
4242            && (truth_value_p (TREE_CODE (arg1))
4243                || (TREE_CODE (arg1) == BIT_AND_EXPR
4244                    && integer_onep (TREE_OPERAND (arg1, 1)))))
4245           || (truth_value_p (TREE_CODE (arg1))
4246               && (truth_value_p (TREE_CODE (arg0))
4247                   || (TREE_CODE (arg0) == BIT_AND_EXPR
4248                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
4249     {
4250       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4251                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4252                        : TRUTH_XOR_EXPR,
4253                        type, arg0, arg1));
4254
4255       if (code == EQ_EXPR)
4256         t = invert_truthvalue (t);
4257
4258       return t;
4259     }
4260
4261   if (TREE_CODE_CLASS (code) == '1')
4262     {
4263       if (TREE_CODE (arg0) == COMPOUND_EXPR)
4264         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4265                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4266       else if (TREE_CODE (arg0) == COND_EXPR)
4267         {
4268           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4269                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4270                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4271
4272           /* If this was a conversion, and all we did was to move into
4273              inside the COND_EXPR, bring it back out.  But leave it if
4274              it is a conversion from integer to integer and the
4275              result precision is no wider than a word since such a
4276              conversion is cheap and may be optimized away by combine,
4277              while it couldn't if it were outside the COND_EXPR.  Then return
4278              so we don't get into an infinite recursion loop taking the
4279              conversion out and then back in.  */
4280
4281           if ((code == NOP_EXPR || code == CONVERT_EXPR
4282                || code == NON_LVALUE_EXPR)
4283               && TREE_CODE (t) == COND_EXPR
4284               && TREE_CODE (TREE_OPERAND (t, 1)) == code
4285               && TREE_CODE (TREE_OPERAND (t, 2)) == code
4286               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4287                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4288               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4289                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
4290                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4291             t = build1 (code, type,
4292                         build (COND_EXPR,
4293                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
4294                                TREE_OPERAND (t, 0),
4295                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4296                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4297           return t;
4298         }
4299       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4300         return fold (build (COND_EXPR, type, arg0,
4301                             fold (build1 (code, type, integer_one_node)),
4302                             fold (build1 (code, type, integer_zero_node))));
4303    }
4304   else if (TREE_CODE_CLASS (code) == '2'
4305            || TREE_CODE_CLASS (code) == '<')
4306     {
4307       if (TREE_CODE (arg1) == COMPOUND_EXPR)
4308         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4309                       fold (build (code, type,
4310                                    arg0, TREE_OPERAND (arg1, 1))));
4311       else if ((TREE_CODE (arg1) == COND_EXPR
4312                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4313                     && TREE_CODE_CLASS (code) != '<'))
4314                && (TREE_CODE (arg0) != COND_EXPR
4315                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4316                && (! TREE_SIDE_EFFECTS (arg0)
4317                    || (current_function_decl != 0
4318                        && ! contains_placeholder_p (arg0))))
4319         {
4320           tree test, true_value, false_value;
4321           tree lhs = 0, rhs = 0;
4322
4323           if (TREE_CODE (arg1) == COND_EXPR)
4324             {
4325               test = TREE_OPERAND (arg1, 0);
4326               true_value = TREE_OPERAND (arg1, 1);
4327               false_value = TREE_OPERAND (arg1, 2);
4328             }
4329           else
4330             {
4331               tree testtype = TREE_TYPE (arg1);
4332               test = arg1;
4333               true_value = convert (testtype, integer_one_node);
4334               false_value = convert (testtype, integer_zero_node);
4335             }
4336
4337           /* If ARG0 is complex we want to make sure we only evaluate
4338              it once.  Though this is only required if it is volatile, it
4339              might be more efficient even if it is not.  However, if we
4340              succeed in folding one part to a constant, we do not need
4341              to make this SAVE_EXPR.  Since we do this optimization
4342              primarily to see if we do end up with constant and this
4343              SAVE_EXPR interferes with later optimizations, suppressing
4344              it when we can is important.
4345
4346              If we are not in a function, we can't make a SAVE_EXPR, so don't
4347              try to do so.  Don't try to see if the result is a constant
4348              if an arm is a COND_EXPR since we get exponential behavior
4349              in that case.  */
4350
4351           if (TREE_CODE (arg0) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4352               && current_function_decl != 0
4353               && ((TREE_CODE (arg0) != VAR_DECL
4354                    && TREE_CODE (arg0) != PARM_DECL)
4355                   || TREE_SIDE_EFFECTS (arg0)))
4356             {
4357               if (TREE_CODE (true_value) != COND_EXPR)
4358                 lhs = fold (build (code, type, arg0, true_value));
4359
4360               if (TREE_CODE (false_value) != COND_EXPR)
4361                 rhs = fold (build (code, type, arg0, false_value));
4362
4363               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4364                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4365                 arg0 = save_expr (arg0), lhs = rhs = 0;
4366             }
4367
4368           if (lhs == 0)
4369             lhs = fold (build (code, type, arg0, true_value));
4370           if (rhs == 0)
4371             rhs = fold (build (code, type, arg0, false_value));
4372
4373           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4374
4375           if (TREE_CODE (arg0) == SAVE_EXPR)
4376             return build (COMPOUND_EXPR, type,
4377                           convert (void_type_node, arg0),
4378                           strip_compound_expr (test, arg0));
4379           else
4380             return convert (type, test);
4381         }
4382
4383       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4384         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4385                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4386       else if ((TREE_CODE (arg0) == COND_EXPR
4387                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4388                     && TREE_CODE_CLASS (code) != '<'))
4389                && (TREE_CODE (arg1) != COND_EXPR
4390                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4391                && (! TREE_SIDE_EFFECTS (arg1)
4392                    || (current_function_decl != 0
4393                        && ! contains_placeholder_p (arg1))))
4394         {
4395           tree test, true_value, false_value;
4396           tree lhs = 0, rhs = 0;
4397
4398           if (TREE_CODE (arg0) == COND_EXPR)
4399             {
4400               test = TREE_OPERAND (arg0, 0);
4401               true_value = TREE_OPERAND (arg0, 1);
4402               false_value = TREE_OPERAND (arg0, 2);
4403             }
4404           else
4405             {
4406               tree testtype = TREE_TYPE (arg0);
4407               test = arg0;
4408               true_value = convert (testtype, integer_one_node);
4409               false_value = convert (testtype, integer_zero_node);
4410             }
4411
4412           if (TREE_CODE (arg1) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4413               && current_function_decl != 0
4414               && ((TREE_CODE (arg1) != VAR_DECL
4415                    && TREE_CODE (arg1) != PARM_DECL)
4416                   || TREE_SIDE_EFFECTS (arg1)))
4417             {
4418               if (TREE_CODE (true_value) != COND_EXPR)
4419                 lhs = fold (build (code, type, true_value, arg1));
4420
4421               if (TREE_CODE (false_value) != COND_EXPR)
4422                 rhs = fold (build (code, type, false_value, arg1));
4423
4424               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4425                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4426                 arg1 = save_expr (arg1), lhs = rhs = 0;
4427             }
4428
4429           if (lhs == 0)
4430             lhs = fold (build (code, type, true_value, arg1));
4431
4432           if (rhs == 0)
4433             rhs = fold (build (code, type, false_value, arg1));
4434
4435           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4436           if (TREE_CODE (arg1) == SAVE_EXPR)
4437             return build (COMPOUND_EXPR, type,
4438                           convert (void_type_node, arg1),
4439                           strip_compound_expr (test, arg1));
4440           else
4441             return convert (type, test);
4442         }
4443     }
4444   else if (TREE_CODE_CLASS (code) == '<'
4445            && TREE_CODE (arg0) == COMPOUND_EXPR)
4446     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4447                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4448   else if (TREE_CODE_CLASS (code) == '<'
4449            && TREE_CODE (arg1) == COMPOUND_EXPR)
4450     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4451                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4452
4453   switch (code)
4454     {
4455     case INTEGER_CST:
4456     case REAL_CST:
4457     case STRING_CST:
4458     case COMPLEX_CST:
4459     case CONSTRUCTOR:
4460       return t;
4461
4462     case CONST_DECL:
4463       return fold (DECL_INITIAL (t));
4464
4465     case NOP_EXPR:
4466     case FLOAT_EXPR:
4467     case CONVERT_EXPR:
4468     case FIX_TRUNC_EXPR:
4469       /* Other kinds of FIX are not handled properly by fold_convert.  */
4470
4471       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4472         return TREE_OPERAND (t, 0);
4473
4474       /* Handle cases of two conversions in a row.  */
4475       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4476           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4477         {
4478           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4479           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4480           tree final_type = TREE_TYPE (t);
4481           int inside_int = INTEGRAL_TYPE_P (inside_type);
4482           int inside_ptr = POINTER_TYPE_P (inside_type);
4483           int inside_float = FLOAT_TYPE_P (inside_type);
4484           int inside_prec = TYPE_PRECISION (inside_type);
4485           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4486           int inter_int = INTEGRAL_TYPE_P (inter_type);
4487           int inter_ptr = POINTER_TYPE_P (inter_type);
4488           int inter_float = FLOAT_TYPE_P (inter_type);
4489           int inter_prec = TYPE_PRECISION (inter_type);
4490           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4491           int final_int = INTEGRAL_TYPE_P (final_type);
4492           int final_ptr = POINTER_TYPE_P (final_type);
4493           int final_float = FLOAT_TYPE_P (final_type);
4494           int final_prec = TYPE_PRECISION (final_type);
4495           int final_unsignedp = TREE_UNSIGNED (final_type);
4496
4497           /* In addition to the cases of two conversions in a row
4498              handled below, if we are converting something to its own
4499              type via an object of identical or wider precision, neither
4500              conversion is needed.  */
4501           if (inside_type == final_type
4502               && ((inter_int && final_int) || (inter_float && final_float))
4503               && inter_prec >= final_prec)
4504             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4505
4506           /* Likewise, if the intermediate and final types are either both
4507              float or both integer, we don't need the middle conversion if
4508              it is wider than the final type and doesn't change the signedness
4509              (for integers).  Avoid this if the final type is a pointer
4510              since then we sometimes need the inner conversion.  Likewise if
4511              the outer has a precision not equal to the size of its mode.  */
4512           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4513                || (inter_float && inside_float))
4514               && inter_prec >= inside_prec
4515               && (inter_float || inter_unsignedp == inside_unsignedp)
4516               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4517                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4518               && ! final_ptr)
4519             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4520
4521           /* If we have a sign-extension of a zero-extended value, we can
4522              replace that by a single zero-extension.  */
4523           if (inside_int && inter_int && final_int
4524               && inside_prec < inter_prec && inter_prec < final_prec
4525               && inside_unsignedp && !inter_unsignedp)
4526             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4527
4528           /* Two conversions in a row are not needed unless:
4529              - some conversion is floating-point (overstrict for now), or
4530              - the intermediate type is narrower than both initial and
4531                final, or
4532              - the intermediate type and innermost type differ in signedness,
4533                and the outermost type is wider than the intermediate, or
4534              - the initial type is a pointer type and the precisions of the
4535                intermediate and final types differ, or
4536              - the final type is a pointer type and the precisions of the
4537                initial and intermediate types differ.  */
4538           if (! inside_float && ! inter_float && ! final_float
4539               && (inter_prec > inside_prec || inter_prec > final_prec)
4540               && ! (inside_int && inter_int
4541                     && inter_unsignedp != inside_unsignedp
4542                     && inter_prec < final_prec)
4543               && ((inter_unsignedp && inter_prec > inside_prec)
4544                   == (final_unsignedp && final_prec > inter_prec))
4545               && ! (inside_ptr && inter_prec != final_prec)
4546               && ! (final_ptr && inside_prec != inter_prec)
4547               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4548                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4549               && ! final_ptr)
4550             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4551         }
4552
4553       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4554           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4555           /* Detect assigning a bitfield.  */
4556           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4557                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4558         {
4559           /* Don't leave an assignment inside a conversion
4560              unless assigning a bitfield.  */
4561           tree prev = TREE_OPERAND (t, 0);
4562           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4563           /* First do the assignment, then return converted constant.  */
4564           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4565           TREE_USED (t) = 1;
4566           return t;
4567         }
4568       if (!wins)
4569         {
4570           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4571           return t;
4572         }
4573       return fold_convert (t, arg0);
4574
4575 #if 0  /* This loses on &"foo"[0].  */
4576     case ARRAY_REF:
4577         {
4578           int i;
4579
4580           /* Fold an expression like: "foo"[2] */
4581           if (TREE_CODE (arg0) == STRING_CST
4582               && TREE_CODE (arg1) == INTEGER_CST
4583               && !TREE_INT_CST_HIGH (arg1)
4584               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4585             {
4586               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4587               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4588               force_fit_type (t, 0);
4589             }
4590         }
4591       return t;
4592 #endif /* 0 */
4593
4594     case COMPONENT_REF:
4595       if (TREE_CODE (arg0) == CONSTRUCTOR)
4596         {
4597           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4598           if (m)
4599             t = TREE_VALUE (m);
4600         }
4601       return t;
4602
4603     case RANGE_EXPR:
4604       TREE_CONSTANT (t) = wins;
4605       return t;
4606
4607     case NEGATE_EXPR:
4608       if (wins)
4609         {
4610           if (TREE_CODE (arg0) == INTEGER_CST)
4611             {
4612               HOST_WIDE_INT low, high;
4613               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4614                                          TREE_INT_CST_HIGH (arg0),
4615                                          &low, &high);
4616               t = build_int_2 (low, high);
4617               TREE_TYPE (t) = type;
4618               TREE_OVERFLOW (t)
4619                 = (TREE_OVERFLOW (arg0)
4620                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4621               TREE_CONSTANT_OVERFLOW (t)
4622                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4623             }
4624           else if (TREE_CODE (arg0) == REAL_CST)
4625             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4626         }
4627       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4628         return TREE_OPERAND (arg0, 0);
4629
4630       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4631       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4632         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4633                       TREE_OPERAND (arg0, 0));
4634
4635       return t;
4636
4637     case ABS_EXPR:
4638       if (wins)
4639         {
4640           if (TREE_CODE (arg0) == INTEGER_CST)
4641             {
4642               if (! TREE_UNSIGNED (type)
4643                   && TREE_INT_CST_HIGH (arg0) < 0)
4644                 {
4645                   HOST_WIDE_INT low, high;
4646                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4647                                              TREE_INT_CST_HIGH (arg0),
4648                                              &low, &high);
4649                   t = build_int_2 (low, high);
4650                   TREE_TYPE (t) = type;
4651                   TREE_OVERFLOW (t)
4652                     = (TREE_OVERFLOW (arg0)
4653                        | force_fit_type (t, overflow));
4654                   TREE_CONSTANT_OVERFLOW (t)
4655                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4656                 }
4657             }
4658           else if (TREE_CODE (arg0) == REAL_CST)
4659             {
4660               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4661                 t = build_real (type,
4662                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4663             }
4664         }
4665       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4666         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4667       return t;
4668
4669     case CONJ_EXPR:
4670       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4671         return arg0;
4672       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4673         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4674                       TREE_OPERAND (arg0, 0),
4675                       fold (build1 (NEGATE_EXPR,
4676                                     TREE_TYPE (TREE_TYPE (arg0)),
4677                                     TREE_OPERAND (arg0, 1))));
4678       else if (TREE_CODE (arg0) == COMPLEX_CST)
4679         return build_complex (type, TREE_OPERAND (arg0, 0),
4680                               fold (build1 (NEGATE_EXPR,
4681                                             TREE_TYPE (TREE_TYPE (arg0)),
4682                                             TREE_OPERAND (arg0, 1))));
4683       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4684         return fold (build (TREE_CODE (arg0), type,
4685                             fold (build1 (CONJ_EXPR, type,
4686                                           TREE_OPERAND (arg0, 0))),
4687                             fold (build1 (CONJ_EXPR,
4688                                           type, TREE_OPERAND (arg0, 1)))));
4689       else if (TREE_CODE (arg0) == CONJ_EXPR)
4690         return TREE_OPERAND (arg0, 0);
4691       return t;
4692
4693     case BIT_NOT_EXPR:
4694       if (wins)
4695         {
4696           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4697                            ~ TREE_INT_CST_HIGH (arg0));
4698           TREE_TYPE (t) = type;
4699           force_fit_type (t, 0);
4700           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4701           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4702         }
4703       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4704         return TREE_OPERAND (arg0, 0);
4705       return t;
4706
4707     case PLUS_EXPR:
4708       /* A + (-B) -> A - B */
4709       if (TREE_CODE (arg1) == NEGATE_EXPR)
4710         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4711       else if (! FLOAT_TYPE_P (type))
4712         {
4713           if (integer_zerop (arg1))
4714             return non_lvalue (convert (type, arg0));
4715
4716           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4717              with a constant, and the two constants have no bits in common,
4718              we should treat this as a BIT_IOR_EXPR since this may produce more
4719              simplifications.  */
4720           if (TREE_CODE (arg0) == BIT_AND_EXPR
4721               && TREE_CODE (arg1) == BIT_AND_EXPR
4722               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4723               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4724               && integer_zerop (const_binop (BIT_AND_EXPR,
4725                                              TREE_OPERAND (arg0, 1),
4726                                              TREE_OPERAND (arg1, 1), 0)))
4727             {
4728               code = BIT_IOR_EXPR;
4729               goto bit_ior;
4730             }
4731
4732           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4733             {
4734               tree arg00, arg01, arg10, arg11;
4735               tree alt0, alt1, same;
4736
4737               /* (A * C) + (B * C) -> (A+B) * C.
4738                  We are most concerned about the case where C is a constant,
4739                  but other combinations show up during loop reduction.  Since
4740                  it is not difficult, try all four possibilities.  */
4741
4742               arg00 = TREE_OPERAND (arg0, 0);
4743               arg01 = TREE_OPERAND (arg0, 1);
4744               arg10 = TREE_OPERAND (arg1, 0);
4745               arg11 = TREE_OPERAND (arg1, 1);
4746               same = NULL_TREE;
4747
4748               if (operand_equal_p (arg01, arg11, 0))
4749                 same = arg01, alt0 = arg00, alt1 = arg10;
4750               else if (operand_equal_p (arg00, arg10, 0))
4751                 same = arg00, alt0 = arg01, alt1 = arg11;
4752               else if (operand_equal_p (arg00, arg11, 0))
4753                 same = arg00, alt0 = arg01, alt1 = arg10;
4754               else if (operand_equal_p (arg01, arg10, 0))
4755                 same = arg01, alt0 = arg00, alt1 = arg11;
4756
4757               if (same)
4758                 return fold (build (MULT_EXPR, type,
4759                                     fold (build (PLUS_EXPR, type, alt0, alt1)),
4760                                     same));
4761             }
4762         }
4763       /* In IEEE floating point, x+0 may not equal x.  */
4764       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4765                 || flag_fast_math)
4766                && real_zerop (arg1))
4767         return non_lvalue (convert (type, arg0));
4768     associate:
4769       /* In most languages, can't associate operations on floats
4770          through parentheses.  Rather than remember where the parentheses
4771          were, we don't associate floats at all.  It shouldn't matter much.
4772          However, associating multiplications is only very slightly
4773          inaccurate, so do that if -ffast-math is specified.  */
4774       if (FLOAT_TYPE_P (type)
4775           && ! (flag_fast_math && code == MULT_EXPR))
4776         goto binary;
4777
4778       /* The varsign == -1 cases happen only for addition and subtraction.
4779          It says that the arg that was split was really CON minus VAR.
4780          The rest of the code applies to all associative operations.  */
4781       if (!wins)
4782         {
4783           tree var, con;
4784           int varsign;
4785
4786           if (split_tree (arg0, code, &var, &con, &varsign))
4787             {
4788               if (varsign == -1)
4789                 {
4790                   /* EXPR is (CON-VAR) +- ARG1.  */
4791                   /* If it is + and VAR==ARG1, return just CONST.  */
4792                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4793                     return convert (TREE_TYPE (t), con);
4794
4795                   /* If ARG0 is a constant, don't change things around;
4796                      instead keep all the constant computations together.  */
4797
4798                   if (TREE_CONSTANT (arg0))
4799                     return t;
4800
4801                   /* Otherwise return (CON +- ARG1) - VAR.  */
4802                   t = build (MINUS_EXPR, type,
4803                              fold (build (code, type, con, arg1)), var);
4804                 }
4805               else
4806                 {
4807                   /* EXPR is (VAR+CON) +- ARG1.  */
4808                   /* If it is - and VAR==ARG1, return just CONST.  */
4809                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4810                     return convert (TREE_TYPE (t), con);
4811
4812                   /* If ARG0 is a constant, don't change things around;
4813                      instead keep all the constant computations together.  */
4814
4815                   if (TREE_CONSTANT (arg0))
4816                     return t;
4817
4818                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4819                   tem = fold (build (code, type, arg1, con));
4820                   t = build (code, type, var, tem);
4821
4822                   if (integer_zerop (tem)
4823                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4824                     return convert (type, var);
4825                   /* If we have x +/- (c - d) [c an explicit integer]
4826                      change it to x -/+ (d - c) since if d is relocatable
4827                      then the latter can be a single immediate insn
4828                      and the former cannot.  */
4829                   if (TREE_CODE (tem) == MINUS_EXPR
4830                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4831                     {
4832                       tree tem1 = TREE_OPERAND (tem, 1);
4833                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4834                       TREE_OPERAND (tem, 0) = tem1;
4835                       TREE_SET_CODE (t,
4836                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4837                     }
4838                 }
4839               return t;
4840             }
4841
4842           if (split_tree (arg1, code, &var, &con, &varsign))
4843             {
4844               if (TREE_CONSTANT (arg1))
4845                 return t;
4846
4847               if (varsign == -1)
4848                 TREE_SET_CODE (t,
4849                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4850
4851               /* EXPR is ARG0 +- (CON +- VAR).  */
4852               if (TREE_CODE (t) == MINUS_EXPR
4853                   && operand_equal_p (var, arg0, 0))
4854                 {
4855                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4856                   if (code == PLUS_EXPR)
4857                     return convert (TREE_TYPE (t), con);
4858                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4859                                        convert (TREE_TYPE (t), con)));
4860                 }
4861
4862               t = build (TREE_CODE (t), type,
4863                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4864
4865               if (integer_zerop (TREE_OPERAND (t, 0))
4866                   && TREE_CODE (t) == PLUS_EXPR)
4867                 return convert (TREE_TYPE (t), var);
4868               return t;
4869             }
4870         }
4871     binary:
4872 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4873       if (TREE_CODE (arg1) == REAL_CST)
4874         return t;
4875 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4876       if (wins)
4877         t1 = const_binop (code, arg0, arg1, 0);
4878       if (t1 != NULL_TREE)
4879         {
4880           /* The return value should always have
4881              the same type as the original expression.  */
4882           if (TREE_TYPE (t1) != TREE_TYPE (t))
4883             t1 = convert (TREE_TYPE (t), t1);
4884
4885           return t1;
4886         }
4887       return t;
4888
4889     case MINUS_EXPR:
4890       if (! FLOAT_TYPE_P (type))
4891         {
4892           if (! wins && integer_zerop (arg0))
4893             return build1 (NEGATE_EXPR, type, arg1);
4894           if (integer_zerop (arg1))
4895             return non_lvalue (convert (type, arg0));
4896
4897           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
4898              about the case where C is a constant, just try one of the
4899              four possibilities.  */
4900
4901           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4902               && operand_equal_p (TREE_OPERAND (arg0, 1),
4903                                   TREE_OPERAND (arg1, 1), 0))
4904             return fold (build (MULT_EXPR, type,
4905                                 fold (build (MINUS_EXPR, type,
4906                                              TREE_OPERAND (arg0, 0),
4907                                              TREE_OPERAND (arg1, 0))),
4908                                 TREE_OPERAND (arg0, 1)));
4909         }
4910       /* Convert A - (-B) to A + B.  */
4911       else if (TREE_CODE (arg1) == NEGATE_EXPR)
4912         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4913
4914       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4915                || flag_fast_math)
4916         {
4917           /* Except with IEEE floating point, 0-x equals -x.  */
4918           if (! wins && real_zerop (arg0))
4919             return build1 (NEGATE_EXPR, type, arg1);
4920           /* Except with IEEE floating point, x-0 equals x.  */
4921           if (real_zerop (arg1))
4922             return non_lvalue (convert (type, arg0));
4923         }
4924
4925       /* Fold &x - &x.  This can happen from &x.foo - &x.
4926          This is unsafe for certain floats even in non-IEEE formats.
4927          In IEEE, it is unsafe because it does wrong for NaNs.
4928          Also note that operand_equal_p is always false if an operand
4929          is volatile.  */
4930
4931       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
4932           && operand_equal_p (arg0, arg1, 0))
4933         return convert (type, integer_zero_node);
4934
4935       goto associate;
4936
4937     case MULT_EXPR:
4938       if (! FLOAT_TYPE_P (type))
4939         {
4940           if (integer_zerop (arg1))
4941             return omit_one_operand (type, arg1, arg0);
4942           if (integer_onep (arg1))
4943             return non_lvalue (convert (type, arg0));
4944
4945           /* ((A / C) * C) is A if the division is an
4946              EXACT_DIV_EXPR.   Since C is normally a constant,
4947              just check for one of the four possibilities.  */
4948
4949           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
4950               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
4951             return TREE_OPERAND (arg0, 0);
4952
4953           /* (a * (1 << b)) is (a << b)  */
4954           if (TREE_CODE (arg1) == LSHIFT_EXPR
4955               && integer_onep (TREE_OPERAND (arg1, 0)))
4956             return fold (build (LSHIFT_EXPR, type, arg0,
4957                                 TREE_OPERAND (arg1, 1)));
4958           if (TREE_CODE (arg0) == LSHIFT_EXPR
4959               && integer_onep (TREE_OPERAND (arg0, 0)))
4960             return fold (build (LSHIFT_EXPR, type, arg1,
4961                                 TREE_OPERAND (arg0, 1)));
4962         }
4963       else
4964         {
4965           /* x*0 is 0, except for IEEE floating point.  */
4966           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4967                || flag_fast_math)
4968               && real_zerop (arg1))
4969             return omit_one_operand (type, arg1, arg0);
4970           /* In IEEE floating point, x*1 is not equivalent to x for snans.
4971              However, ANSI says we can drop signals,
4972              so we can do this anyway.  */
4973           if (real_onep (arg1))
4974             return non_lvalue (convert (type, arg0));
4975           /* x*2 is x+x */
4976           if (! wins && real_twop (arg1) && current_function_decl != 0
4977               && ! contains_placeholder_p (arg0))
4978             {
4979               tree arg = save_expr (arg0);
4980               return build (PLUS_EXPR, type, arg, arg);
4981             }
4982         }
4983       goto associate;
4984
4985     case BIT_IOR_EXPR:
4986     bit_ior:
4987       {
4988       register enum tree_code code0, code1;
4989
4990       if (integer_all_onesp (arg1))
4991         return omit_one_operand (type, arg1, arg0);
4992       if (integer_zerop (arg1))
4993         return non_lvalue (convert (type, arg0));
4994       t1 = distribute_bit_expr (code, type, arg0, arg1);
4995       if (t1 != NULL_TREE)
4996         return t1;
4997
4998       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
4999          is a rotate of A by C1 bits.  */
5000       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
5001          is a rotate of A by B bits.  */
5002
5003       code0 = TREE_CODE (arg0);
5004       code1 = TREE_CODE (arg1);
5005       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5006           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5007           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
5008           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5009         {
5010           register tree tree01, tree11;
5011           register enum tree_code code01, code11;
5012
5013           tree01 = TREE_OPERAND (arg0, 1);
5014           tree11 = TREE_OPERAND (arg1, 1);
5015           STRIP_NOPS (tree01);
5016           STRIP_NOPS (tree11);
5017           code01 = TREE_CODE (tree01);
5018           code11 = TREE_CODE (tree11);
5019           if (code01 == INTEGER_CST
5020             && code11 == INTEGER_CST
5021             && TREE_INT_CST_HIGH (tree01) == 0
5022             && TREE_INT_CST_HIGH (tree11) == 0
5023             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5024               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5025             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5026                       code0 == LSHIFT_EXPR ? tree01 : tree11);
5027           else if (code11 == MINUS_EXPR)
5028             {
5029               tree tree110, tree111;
5030               tree110 = TREE_OPERAND (tree11, 0);
5031               tree111 = TREE_OPERAND (tree11, 1);
5032               STRIP_NOPS (tree110);
5033               STRIP_NOPS (tree111);
5034               if (TREE_CODE (tree110) == INTEGER_CST
5035                   && TREE_INT_CST_HIGH (tree110) == 0
5036                   && (TREE_INT_CST_LOW (tree110)
5037                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5038                   && operand_equal_p (tree01, tree111, 0))
5039                 return build ((code0 == LSHIFT_EXPR
5040                                ? LROTATE_EXPR
5041                                : RROTATE_EXPR),
5042                               type, TREE_OPERAND (arg0, 0), tree01);
5043             }
5044           else if (code01 == MINUS_EXPR)
5045             {
5046               tree tree010, tree011;
5047               tree010 = TREE_OPERAND (tree01, 0);
5048               tree011 = TREE_OPERAND (tree01, 1);
5049               STRIP_NOPS (tree010);
5050               STRIP_NOPS (tree011);
5051               if (TREE_CODE (tree010) == INTEGER_CST
5052                   && TREE_INT_CST_HIGH (tree010) == 0
5053                   && (TREE_INT_CST_LOW (tree010)
5054                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5055                   && operand_equal_p (tree11, tree011, 0))
5056                 return build ((code0 != LSHIFT_EXPR
5057                                ? LROTATE_EXPR
5058                                : RROTATE_EXPR),
5059                                type, TREE_OPERAND (arg0, 0), tree11);
5060             }
5061         }
5062
5063       goto associate;
5064       }
5065
5066     case BIT_XOR_EXPR:
5067       if (integer_zerop (arg1))
5068         return non_lvalue (convert (type, arg0));
5069       if (integer_all_onesp (arg1))
5070         return fold (build1 (BIT_NOT_EXPR, type, arg0));
5071       goto associate;
5072
5073     case BIT_AND_EXPR:
5074     bit_and:
5075       if (integer_all_onesp (arg1))
5076         return non_lvalue (convert (type, arg0));
5077       if (integer_zerop (arg1))
5078         return omit_one_operand (type, arg1, arg0);
5079       t1 = distribute_bit_expr (code, type, arg0, arg1);
5080       if (t1 != NULL_TREE)
5081         return t1;
5082       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
5083       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5084           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5085         {
5086           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5087           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5088               && (~TREE_INT_CST_LOW (arg0)
5089                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5090             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5091         }
5092       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5093           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5094         {
5095           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5096           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5097               && (~TREE_INT_CST_LOW (arg1)
5098                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5099             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5100         }
5101       goto associate;
5102
5103     case BIT_ANDTC_EXPR:
5104       if (integer_all_onesp (arg0))
5105         return non_lvalue (convert (type, arg1));
5106       if (integer_zerop (arg0))
5107         return omit_one_operand (type, arg0, arg1);
5108       if (TREE_CODE (arg1) == INTEGER_CST)
5109         {
5110           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5111           code = BIT_AND_EXPR;
5112           goto bit_and;
5113         }
5114       goto binary;
5115
5116     case RDIV_EXPR:
5117       /* In most cases, do nothing with a divide by zero.  */
5118 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
5119 #ifndef REAL_INFINITY
5120       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
5121         return t;
5122 #endif
5123 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
5124
5125       /* In IEEE floating point, x/1 is not equivalent to x for snans.
5126          However, ANSI says we can drop signals, so we can do this anyway.  */
5127       if (real_onep (arg1))
5128         return non_lvalue (convert (type, arg0));
5129
5130       /* If ARG1 is a constant, we can convert this to a multiply by the
5131          reciprocal.  This does not have the same rounding properties,
5132          so only do this if -ffast-math.  We can actually always safely
5133          do it if ARG1 is a power of two, but it's hard to tell if it is
5134          or not in a portable manner.  */
5135       if (TREE_CODE (arg1) == REAL_CST)
5136         {
5137           if (flag_fast_math
5138               && 0 != (tem = const_binop (code, build_real (type, dconst1),
5139                                           arg1, 0)))
5140             return fold (build (MULT_EXPR, type, arg0, tem));
5141           /* Find the reciprocal if optimizing and the result is exact. */
5142           else if (optimize)
5143             {
5144               REAL_VALUE_TYPE r;
5145               r = TREE_REAL_CST (arg1);
5146               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5147                   {
5148                     tem = build_real (type, r);
5149                     return fold (build (MULT_EXPR, type, arg0, tem));
5150                   }
5151             }
5152         }
5153       goto binary;
5154
5155     case TRUNC_DIV_EXPR:
5156     case ROUND_DIV_EXPR:
5157     case FLOOR_DIV_EXPR:
5158     case CEIL_DIV_EXPR:
5159     case EXACT_DIV_EXPR:
5160       if (integer_onep (arg1))
5161         return non_lvalue (convert (type, arg0));
5162       if (integer_zerop (arg1))
5163         return t;
5164
5165       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5166          operation, EXACT_DIV_EXPR.
5167
5168          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5169          At one time others generated faster code, it's not clear if they do
5170          after the last round to changes to the DIV code in expmed.c.  */
5171       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5172           && multiple_of_p (type, arg0, arg1))
5173         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5174
5175       /* If we have ((a / C1) / C2) where both division are the same type, try
5176          to simplify.  First see if C1 * C2 overflows or not.  */
5177       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
5178           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5179         {
5180           tree new_divisor;
5181
5182           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
5183           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
5184
5185           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
5186               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
5187             {
5188               /* If no overflow, divide by C1*C2.  */
5189               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
5190             }
5191         }
5192
5193       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
5194          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
5195          expressions, which often appear in the offsets or sizes of
5196          objects with a varying size.  Only deal with positive divisors
5197          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
5198
5199          Look for NOPs and SAVE_EXPRs inside.  */
5200
5201       if (TREE_CODE (arg1) == INTEGER_CST
5202           && tree_int_cst_sgn (arg1) >= 0)
5203         {
5204           int have_save_expr = 0;
5205           tree c2 = integer_zero_node;
5206           tree xarg0 = arg0;
5207
5208           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5209             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5210
5211           STRIP_NOPS (xarg0);
5212
5213           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
5214              if possible.  */
5215           if (TREE_CODE (xarg0) == MULT_EXPR
5216               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
5217             {
5218               tree t;
5219
5220               t = fold (build (MULT_EXPR, type,
5221                                fold (build (EXACT_DIV_EXPR, type,
5222                                             TREE_OPERAND (xarg0, 0), arg1)),
5223                                TREE_OPERAND (xarg0, 1)));
5224               if (have_save_expr)
5225                 t = save_expr (t);
5226               return t;
5227
5228             }
5229
5230           if (TREE_CODE (xarg0) == MULT_EXPR
5231               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
5232             {
5233               tree t;
5234
5235               t = fold (build (MULT_EXPR, type,
5236                                fold (build (EXACT_DIV_EXPR, type,
5237                                             TREE_OPERAND (xarg0, 1), arg1)),
5238                                TREE_OPERAND (xarg0, 0)));
5239               if (have_save_expr)
5240                 t = save_expr (t);
5241               return t;
5242             }
5243
5244           if (TREE_CODE (xarg0) == PLUS_EXPR
5245               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5246             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5247           else if (TREE_CODE (xarg0) == MINUS_EXPR
5248                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5249                    /* If we are doing this computation unsigned, the negate
5250                       is incorrect.  */
5251                    && ! TREE_UNSIGNED (type))
5252             {
5253               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5254               xarg0 = TREE_OPERAND (xarg0, 0);
5255             }
5256
5257           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5258             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5259
5260           STRIP_NOPS (xarg0);
5261
5262           if (TREE_CODE (xarg0) == MULT_EXPR
5263               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5264               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
5265               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
5266                                               TREE_OPERAND (xarg0, 1), arg1, 1))
5267                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
5268                                                  TREE_OPERAND (xarg0, 1), 1)))
5269               && (tree_int_cst_sgn (c2) >= 0
5270                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
5271                                                  arg1, 1))))
5272             {
5273               tree outer_div = integer_one_node;
5274               tree c1 = TREE_OPERAND (xarg0, 1);
5275               tree c3 = arg1;
5276
5277               /* If C3 > C1, set them equal and do a divide by
5278                  C3/C1 at the end of the operation.  */
5279               if (tree_int_cst_lt (c1, c3))
5280                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
5281
5282               /* The result is A * (C1/C3) + (C2/C3).  */
5283               t = fold (build (PLUS_EXPR, type,
5284                                fold (build (MULT_EXPR, type,
5285                                             TREE_OPERAND (xarg0, 0),
5286                                             const_binop (code, c1, c3, 1))),
5287                                const_binop (code, c2, c3, 1)));
5288
5289               if (! integer_onep (outer_div))
5290                 t = fold (build (code, type, t, convert (type, outer_div)));
5291
5292               if (have_save_expr)
5293                 t = save_expr (t);
5294
5295               return t;
5296             }
5297         }
5298
5299       goto binary;
5300
5301     case CEIL_MOD_EXPR:
5302     case FLOOR_MOD_EXPR:
5303     case ROUND_MOD_EXPR:
5304     case TRUNC_MOD_EXPR:
5305       if (integer_onep (arg1))
5306         return omit_one_operand (type, integer_zero_node, arg0);
5307       if (integer_zerop (arg1))
5308         return t;
5309
5310       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
5311          where C1 % C3 == 0.  Handle similarly to the division case,
5312          but don't bother with SAVE_EXPRs.  */
5313
5314       if (TREE_CODE (arg1) == INTEGER_CST
5315           && ! integer_zerop (arg1))
5316         {
5317           tree c2 = integer_zero_node;
5318           tree xarg0 = arg0;
5319
5320           if (TREE_CODE (xarg0) == PLUS_EXPR
5321               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5322             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5323           else if (TREE_CODE (xarg0) == MINUS_EXPR
5324                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5325                    && ! TREE_UNSIGNED (type))
5326             {
5327               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5328               xarg0 = TREE_OPERAND (xarg0, 0);
5329             }
5330
5331           STRIP_NOPS (xarg0);
5332
5333           if (TREE_CODE (xarg0) == MULT_EXPR
5334               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5335               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
5336                                              TREE_OPERAND (xarg0, 1),
5337                                              arg1, 1))
5338               && tree_int_cst_sgn (c2) >= 0)
5339             /* The result is (C2%C3).  */
5340             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
5341                                      TREE_OPERAND (xarg0, 0));
5342         }
5343
5344       goto binary;
5345
5346     case LSHIFT_EXPR:
5347     case RSHIFT_EXPR:
5348     case LROTATE_EXPR:
5349     case RROTATE_EXPR:
5350       if (integer_zerop (arg1))
5351         return non_lvalue (convert (type, arg0));
5352       /* Since negative shift count is not well-defined,
5353          don't try to compute it in the compiler.  */
5354       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5355         return t;
5356       /* Rewrite an LROTATE_EXPR by a constant into an
5357          RROTATE_EXPR by a new constant.  */
5358       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5359         {
5360           TREE_SET_CODE (t, RROTATE_EXPR);
5361           code = RROTATE_EXPR;
5362           TREE_OPERAND (t, 1) = arg1
5363             = const_binop
5364               (MINUS_EXPR,
5365                convert (TREE_TYPE (arg1),
5366                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5367                arg1, 0);
5368           if (tree_int_cst_sgn (arg1) < 0)
5369             return t;
5370         }
5371
5372       /* If we have a rotate of a bit operation with the rotate count and
5373          the second operand of the bit operation both constant,
5374          permute the two operations.  */
5375       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5376           && (TREE_CODE (arg0) == BIT_AND_EXPR
5377               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5378               || TREE_CODE (arg0) == BIT_IOR_EXPR
5379               || TREE_CODE (arg0) == BIT_XOR_EXPR)
5380           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5381         return fold (build (TREE_CODE (arg0), type,
5382                             fold (build (code, type,
5383                                          TREE_OPERAND (arg0, 0), arg1)),
5384                             fold (build (code, type,
5385                                          TREE_OPERAND (arg0, 1), arg1))));
5386
5387       /* Two consecutive rotates adding up to the width of the mode can
5388          be ignored.  */
5389       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5390           && TREE_CODE (arg0) == RROTATE_EXPR
5391           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5392           && TREE_INT_CST_HIGH (arg1) == 0
5393           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5394           && ((TREE_INT_CST_LOW (arg1)
5395                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5396               == GET_MODE_BITSIZE (TYPE_MODE (type))))
5397         return TREE_OPERAND (arg0, 0);
5398
5399       goto binary;
5400
5401     case MIN_EXPR:
5402       if (operand_equal_p (arg0, arg1, 0))
5403         return arg0;
5404       if (INTEGRAL_TYPE_P (type)
5405           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5406         return omit_one_operand (type, arg1, arg0);
5407       goto associate;
5408
5409     case MAX_EXPR:
5410       if (operand_equal_p (arg0, arg1, 0))
5411         return arg0;
5412       if (INTEGRAL_TYPE_P (type)
5413           && TYPE_MAX_VALUE (type)
5414           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5415         return omit_one_operand (type, arg1, arg0);
5416       goto associate;
5417
5418     case TRUTH_NOT_EXPR:
5419       /* Note that the operand of this must be an int
5420          and its values must be 0 or 1.
5421          ("true" is a fixed value perhaps depending on the language,
5422          but we don't handle values other than 1 correctly yet.)  */
5423       tem = invert_truthvalue (arg0);
5424       /* Avoid infinite recursion.  */
5425       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5426         return t;
5427       return convert (type, tem);
5428
5429     case TRUTH_ANDIF_EXPR:
5430       /* Note that the operands of this must be ints
5431          and their values must be 0 or 1.
5432          ("true" is a fixed value perhaps depending on the language.)  */
5433       /* If first arg is constant zero, return it.  */
5434       if (integer_zerop (arg0))
5435         return arg0;
5436     case TRUTH_AND_EXPR:
5437       /* If either arg is constant true, drop it.  */
5438       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5439         return non_lvalue (arg1);
5440       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5441         return non_lvalue (arg0);
5442       /* If second arg is constant zero, result is zero, but first arg
5443          must be evaluated.  */
5444       if (integer_zerop (arg1))
5445         return omit_one_operand (type, arg1, arg0);
5446       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5447          case will be handled here.  */
5448       if (integer_zerop (arg0))
5449         return omit_one_operand (type, arg0, arg1);
5450
5451     truth_andor:
5452       /* We only do these simplifications if we are optimizing.  */
5453       if (!optimize)
5454         return t;
5455
5456       /* Check for things like (A || B) && (A || C).  We can convert this
5457          to A || (B && C).  Note that either operator can be any of the four
5458          truth and/or operations and the transformation will still be
5459          valid.   Also note that we only care about order for the
5460          ANDIF and ORIF operators.  If B contains side effects, this
5461          might change the truth-value of A. */
5462       if (TREE_CODE (arg0) == TREE_CODE (arg1)
5463           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5464               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5465               || TREE_CODE (arg0) == TRUTH_AND_EXPR
5466               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5467           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5468         {
5469           tree a00 = TREE_OPERAND (arg0, 0);
5470           tree a01 = TREE_OPERAND (arg0, 1);
5471           tree a10 = TREE_OPERAND (arg1, 0);
5472           tree a11 = TREE_OPERAND (arg1, 1);
5473           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5474                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5475                              && (code == TRUTH_AND_EXPR
5476                                  || code == TRUTH_OR_EXPR));
5477
5478           if (operand_equal_p (a00, a10, 0))
5479             return fold (build (TREE_CODE (arg0), type, a00,
5480                                 fold (build (code, type, a01, a11))));
5481           else if (commutative && operand_equal_p (a00, a11, 0))
5482             return fold (build (TREE_CODE (arg0), type, a00,
5483                                 fold (build (code, type, a01, a10))));
5484           else if (commutative && operand_equal_p (a01, a10, 0))
5485             return fold (build (TREE_CODE (arg0), type, a01,
5486                                 fold (build (code, type, a00, a11))));
5487
5488           /* This case if tricky because we must either have commutative
5489              operators or else A10 must not have side-effects.  */
5490
5491           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5492                    && operand_equal_p (a01, a11, 0))
5493             return fold (build (TREE_CODE (arg0), type,
5494                                 fold (build (code, type, a00, a10)),
5495                                 a01));
5496         }
5497
5498       /* See if we can build a range comparison.  */
5499       if (0 != (tem = fold_range_test (t)))
5500         return tem;
5501
5502       /* Check for the possibility of merging component references.  If our
5503          lhs is another similar operation, try to merge its rhs with our
5504          rhs.  Then try to merge our lhs and rhs.  */
5505       if (TREE_CODE (arg0) == code
5506           && 0 != (tem = fold_truthop (code, type,
5507                                        TREE_OPERAND (arg0, 1), arg1)))
5508         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5509
5510       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5511         return tem;
5512
5513       return t;
5514
5515     case TRUTH_ORIF_EXPR:
5516       /* Note that the operands of this must be ints
5517          and their values must be 0 or true.
5518          ("true" is a fixed value perhaps depending on the language.)  */
5519       /* If first arg is constant true, return it.  */
5520       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5521         return arg0;
5522     case TRUTH_OR_EXPR:
5523       /* If either arg is constant zero, drop it.  */
5524       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5525         return non_lvalue (arg1);
5526       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5527         return non_lvalue (arg0);
5528       /* If second arg is constant true, result is true, but we must
5529          evaluate first arg.  */
5530       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5531         return omit_one_operand (type, arg1, arg0);
5532       /* Likewise for first arg, but note this only occurs here for
5533          TRUTH_OR_EXPR.  */
5534       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5535         return omit_one_operand (type, arg0, arg1);
5536       goto truth_andor;
5537
5538     case TRUTH_XOR_EXPR:
5539       /* If either arg is constant zero, drop it.  */
5540       if (integer_zerop (arg0))
5541         return non_lvalue (arg1);
5542       if (integer_zerop (arg1))
5543         return non_lvalue (arg0);
5544       /* If either arg is constant true, this is a logical inversion.  */
5545       if (integer_onep (arg0))
5546         return non_lvalue (invert_truthvalue (arg1));
5547       if (integer_onep (arg1))
5548         return non_lvalue (invert_truthvalue (arg0));
5549       return t;
5550
5551     case EQ_EXPR:
5552     case NE_EXPR:
5553     case LT_EXPR:
5554     case GT_EXPR:
5555     case LE_EXPR:
5556     case GE_EXPR:
5557       /* If one arg is a constant integer, put it last.  */
5558       if (TREE_CODE (arg0) == INTEGER_CST
5559           && TREE_CODE (arg1) != INTEGER_CST)
5560         {
5561           TREE_OPERAND (t, 0) = arg1;
5562           TREE_OPERAND (t, 1) = arg0;
5563           arg0 = TREE_OPERAND (t, 0);
5564           arg1 = TREE_OPERAND (t, 1);
5565           code = swap_tree_comparison (code);
5566           TREE_SET_CODE (t, code);
5567         }
5568
5569       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5570          First, see if one arg is constant; find the constant arg
5571          and the other one.  */
5572       {
5573         tree constop = 0, varop = NULL_TREE;
5574         int constopnum = -1;
5575
5576         if (TREE_CONSTANT (arg1))
5577           constopnum = 1, constop = arg1, varop = arg0;
5578         if (TREE_CONSTANT (arg0))
5579           constopnum = 0, constop = arg0, varop = arg1;
5580
5581         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5582           {
5583             /* This optimization is invalid for ordered comparisons
5584                if CONST+INCR overflows or if foo+incr might overflow.
5585                This optimization is invalid for floating point due to rounding.
5586                For pointer types we assume overflow doesn't happen.  */
5587             if (POINTER_TYPE_P (TREE_TYPE (varop))
5588                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5589                     && (code == EQ_EXPR || code == NE_EXPR)))
5590               {
5591                 tree newconst
5592                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5593                                  constop, TREE_OPERAND (varop, 1)));
5594                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5595
5596                 /* If VAROP is a reference to a bitfield, we must mask
5597                    the constant by the width of the field.  */
5598                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5599                     && DECL_BIT_FIELD(TREE_OPERAND
5600                                       (TREE_OPERAND (varop, 0), 1)))
5601                   {
5602                     int size
5603                       = TREE_INT_CST_LOW (DECL_SIZE
5604                                           (TREE_OPERAND
5605                                            (TREE_OPERAND (varop, 0), 1)));
5606                     tree mask, unsigned_type;
5607                     int precision;
5608                     tree folded_compare;
5609
5610                     /* First check whether the comparison would come out
5611                        always the same.  If we don't do that we would
5612                        change the meaning with the masking.  */
5613                     if (constopnum == 0)
5614                       folded_compare = fold (build (code, type, constop,
5615                                                     TREE_OPERAND (varop, 0)));
5616                     else
5617                       folded_compare = fold (build (code, type,
5618                                                     TREE_OPERAND (varop, 0),
5619                                                     constop));
5620                     if (integer_zerop (folded_compare)
5621                         || integer_onep (folded_compare))
5622                       return omit_one_operand (type, folded_compare, varop);
5623
5624                     unsigned_type = type_for_size (size, 1);
5625                     precision = TYPE_PRECISION (unsigned_type);
5626                     mask = build_int_2 (~0, ~0);
5627                     TREE_TYPE (mask) = unsigned_type;
5628                     force_fit_type (mask, 0);
5629                     mask = const_binop (RSHIFT_EXPR, mask,
5630                                         size_int (precision - size), 0);
5631                     newconst = fold (build (BIT_AND_EXPR,
5632                                             TREE_TYPE (varop), newconst,
5633                                             convert (TREE_TYPE (varop),
5634                                                      mask)));
5635                   }
5636
5637
5638                 t = build (code, type, TREE_OPERAND (t, 0),
5639                            TREE_OPERAND (t, 1));
5640                 TREE_OPERAND (t, constopnum) = newconst;
5641                 return t;
5642               }
5643           }
5644         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5645           {
5646             if (POINTER_TYPE_P (TREE_TYPE (varop))
5647                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5648                     && (code == EQ_EXPR || code == NE_EXPR)))
5649               {
5650                 tree newconst
5651                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5652                                  constop, TREE_OPERAND (varop, 1)));
5653                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5654
5655                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5656                     && DECL_BIT_FIELD(TREE_OPERAND
5657                                       (TREE_OPERAND (varop, 0), 1)))
5658                   {
5659                     int size
5660                       = TREE_INT_CST_LOW (DECL_SIZE
5661                                           (TREE_OPERAND
5662                                            (TREE_OPERAND (varop, 0), 1)));
5663                     tree mask, unsigned_type;
5664                     int precision;
5665                     tree folded_compare;
5666
5667                     if (constopnum == 0)
5668                       folded_compare = fold (build (code, type, constop,
5669                                                     TREE_OPERAND (varop, 0)));
5670                     else
5671                       folded_compare = fold (build (code, type,
5672                                                     TREE_OPERAND (varop, 0),
5673                                                     constop));
5674                     if (integer_zerop (folded_compare)
5675                         || integer_onep (folded_compare))
5676                       return omit_one_operand (type, folded_compare, varop);
5677
5678                     unsigned_type = type_for_size (size, 1);
5679                     precision = TYPE_PRECISION (unsigned_type);
5680                     mask = build_int_2 (~0, ~0);
5681                     TREE_TYPE (mask) = TREE_TYPE (varop);
5682                     force_fit_type (mask, 0);
5683                     mask = const_binop (RSHIFT_EXPR, mask,
5684                                         size_int (precision - size), 0);
5685                     newconst = fold (build (BIT_AND_EXPR,
5686                                             TREE_TYPE (varop), newconst,
5687                                             convert (TREE_TYPE (varop),
5688                                                      mask)));
5689                   }
5690
5691
5692                 t = build (code, type, TREE_OPERAND (t, 0),
5693                            TREE_OPERAND (t, 1));
5694                 TREE_OPERAND (t, constopnum) = newconst;
5695                 return t;
5696               }
5697           }
5698       }
5699
5700       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5701       if (TREE_CODE (arg1) == INTEGER_CST
5702           && TREE_CODE (arg0) != INTEGER_CST
5703           && tree_int_cst_sgn (arg1) > 0)
5704         {
5705           switch (TREE_CODE (t))
5706             {
5707             case GE_EXPR:
5708               code = GT_EXPR;
5709               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5710               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5711               break;
5712
5713             case LT_EXPR:
5714               code = LE_EXPR;
5715               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5716               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5717               break;
5718
5719             default:
5720               break;
5721             }
5722         }
5723
5724       /* If this is an EQ or NE comparison with zero and ARG0 is
5725          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5726          two operations, but the latter can be done in one less insn
5727          on machines that have only two-operand insns or on which a
5728          constant cannot be the first operand.  */
5729       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5730           && TREE_CODE (arg0) == BIT_AND_EXPR)
5731         {
5732           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5733               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5734             return
5735               fold (build (code, type,
5736                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5737                                   build (RSHIFT_EXPR,
5738                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5739                                          TREE_OPERAND (arg0, 1),
5740                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5741                                   convert (TREE_TYPE (arg0),
5742                                            integer_one_node)),
5743                            arg1));
5744           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5745                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5746             return
5747               fold (build (code, type,
5748                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5749                                   build (RSHIFT_EXPR,
5750                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5751                                          TREE_OPERAND (arg0, 0),
5752                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5753                                   convert (TREE_TYPE (arg0),
5754                                            integer_one_node)),
5755                            arg1));
5756         }
5757
5758       /* If this is an NE or EQ comparison of zero against the result of a
5759          signed MOD operation whose second operand is a power of 2, make
5760          the MOD operation unsigned since it is simpler and equivalent.  */
5761       if ((code == NE_EXPR || code == EQ_EXPR)
5762           && integer_zerop (arg1)
5763           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5764           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5765               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5766               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5767               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5768           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5769         {
5770           tree newtype = unsigned_type (TREE_TYPE (arg0));
5771           tree newmod = build (TREE_CODE (arg0), newtype,
5772                                convert (newtype, TREE_OPERAND (arg0, 0)),
5773                                convert (newtype, TREE_OPERAND (arg0, 1)));
5774
5775           return build (code, type, newmod, convert (newtype, arg1));
5776         }
5777
5778       /* If this is an NE comparison of zero with an AND of one, remove the
5779          comparison since the AND will give the correct value.  */
5780       if (code == NE_EXPR && integer_zerop (arg1)
5781           && TREE_CODE (arg0) == BIT_AND_EXPR
5782           && integer_onep (TREE_OPERAND (arg0, 1)))
5783         return convert (type, arg0);
5784
5785       /* If we have (A & C) == C where C is a power of 2, convert this into
5786          (A & C) != 0.  Similarly for NE_EXPR.  */
5787       if ((code == EQ_EXPR || code == NE_EXPR)
5788           && TREE_CODE (arg0) == BIT_AND_EXPR
5789           && integer_pow2p (TREE_OPERAND (arg0, 1))
5790           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5791         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5792                       arg0, integer_zero_node);
5793
5794       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5795          and similarly for >= into !=.  */
5796       if ((code == LT_EXPR || code == GE_EXPR)
5797           && TREE_UNSIGNED (TREE_TYPE (arg0))
5798           && TREE_CODE (arg1) == LSHIFT_EXPR
5799           && integer_onep (TREE_OPERAND (arg1, 0)))
5800         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5801                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5802                              TREE_OPERAND (arg1, 1)),
5803                       convert (TREE_TYPE (arg0), integer_zero_node));
5804
5805       else if ((code == LT_EXPR || code == GE_EXPR)
5806                && TREE_UNSIGNED (TREE_TYPE (arg0))
5807                && (TREE_CODE (arg1) == NOP_EXPR
5808                    || TREE_CODE (arg1) == CONVERT_EXPR)
5809                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5810                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5811         return
5812           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5813                  convert (TREE_TYPE (arg0),
5814                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5815                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5816                  convert (TREE_TYPE (arg0), integer_zero_node));
5817
5818       /* Simplify comparison of something with itself.  (For IEEE
5819          floating-point, we can only do some of these simplifications.)  */
5820       if (operand_equal_p (arg0, arg1, 0))
5821         {
5822           switch (code)
5823             {
5824             case EQ_EXPR:
5825             case GE_EXPR:
5826             case LE_EXPR:
5827               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5828                 return constant_boolean_node (1, type);
5829               code = EQ_EXPR;
5830               TREE_SET_CODE (t, code);
5831               break;
5832
5833             case NE_EXPR:
5834               /* For NE, we can only do this simplification if integer.  */
5835               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5836                 break;
5837               /* ... fall through ...  */
5838             case GT_EXPR:
5839             case LT_EXPR:
5840               return constant_boolean_node (0, type);
5841             default:
5842               abort ();
5843             }
5844         }
5845
5846       /* An unsigned comparison against 0 can be simplified.  */
5847       if (integer_zerop (arg1)
5848           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5849               || POINTER_TYPE_P (TREE_TYPE (arg1)))
5850           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5851         {
5852           switch (TREE_CODE (t))
5853             {
5854             case GT_EXPR:
5855               code = NE_EXPR;
5856               TREE_SET_CODE (t, NE_EXPR);
5857               break;
5858             case LE_EXPR:
5859               code = EQ_EXPR;
5860               TREE_SET_CODE (t, EQ_EXPR);
5861               break;
5862             case GE_EXPR:
5863               return omit_one_operand (type,
5864                                        convert (type, integer_one_node),
5865                                        arg0);
5866             case LT_EXPR:
5867               return omit_one_operand (type,
5868                                        convert (type, integer_zero_node),
5869                                        arg0);
5870             default:
5871               break;
5872             }
5873         }
5874
5875       /* An unsigned <= 0x7fffffff can be simplified.  */
5876       {
5877         int width = TYPE_PRECISION (TREE_TYPE (arg1));
5878         if (TREE_CODE (arg1) == INTEGER_CST
5879             && ! TREE_CONSTANT_OVERFLOW (arg1)
5880             && width <= HOST_BITS_PER_WIDE_INT
5881             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
5882             && TREE_INT_CST_HIGH (arg1) == 0
5883             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5884                 || POINTER_TYPE_P (TREE_TYPE (arg1)))
5885             && TREE_UNSIGNED (TREE_TYPE (arg1)))
5886           {
5887             switch (TREE_CODE (t))
5888               {
5889               case LE_EXPR:
5890                 return fold (build (GE_EXPR, type,
5891                                     convert (signed_type (TREE_TYPE (arg0)),
5892                                              arg0),
5893                                     convert (signed_type (TREE_TYPE (arg1)),
5894                                              integer_zero_node)));
5895               case GT_EXPR:
5896                 return fold (build (LT_EXPR, type,
5897                                     convert (signed_type (TREE_TYPE (arg0)),
5898                                              arg0),
5899                                     convert (signed_type (TREE_TYPE (arg1)),
5900                                              integer_zero_node)));
5901               default:
5902                 break;
5903               }
5904           }
5905       }
5906
5907       /* If we are comparing an expression that just has comparisons
5908          of two integer values, arithmetic expressions of those comparisons,
5909          and constants, we can simplify it.  There are only three cases
5910          to check: the two values can either be equal, the first can be
5911          greater, or the second can be greater.  Fold the expression for
5912          those three values.  Since each value must be 0 or 1, we have
5913          eight possibilities, each of which corresponds to the constant 0
5914          or 1 or one of the six possible comparisons.
5915
5916          This handles common cases like (a > b) == 0 but also handles
5917          expressions like  ((x > y) - (y > x)) > 0, which supposedly
5918          occur in macroized code.  */
5919
5920       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
5921         {
5922           tree cval1 = 0, cval2 = 0;
5923           int save_p = 0;
5924
5925           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
5926               /* Don't handle degenerate cases here; they should already
5927                  have been handled anyway.  */
5928               && cval1 != 0 && cval2 != 0
5929               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
5930               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
5931               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
5932               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
5933               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
5934               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
5935                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
5936             {
5937               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
5938               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
5939
5940               /* We can't just pass T to eval_subst in case cval1 or cval2
5941                  was the same as ARG1.  */
5942
5943               tree high_result
5944                 = fold (build (code, type,
5945                                eval_subst (arg0, cval1, maxval, cval2, minval),
5946                                arg1));
5947               tree equal_result
5948                 = fold (build (code, type,
5949                                eval_subst (arg0, cval1, maxval, cval2, maxval),
5950                                arg1));
5951               tree low_result
5952                 = fold (build (code, type,
5953                                eval_subst (arg0, cval1, minval, cval2, maxval),
5954                                arg1));
5955
5956               /* All three of these results should be 0 or 1.  Confirm they
5957                  are.  Then use those values to select the proper code
5958                  to use.  */
5959
5960               if ((integer_zerop (high_result)
5961                    || integer_onep (high_result))
5962                   && (integer_zerop (equal_result)
5963                       || integer_onep (equal_result))
5964                   && (integer_zerop (low_result)
5965                       || integer_onep (low_result)))
5966                 {
5967                   /* Make a 3-bit mask with the high-order bit being the
5968                      value for `>', the next for '=', and the low for '<'.  */
5969                   switch ((integer_onep (high_result) * 4)
5970                           + (integer_onep (equal_result) * 2)
5971                           + integer_onep (low_result))
5972                     {
5973                     case 0:
5974                       /* Always false.  */
5975                       return omit_one_operand (type, integer_zero_node, arg0);
5976                     case 1:
5977                       code = LT_EXPR;
5978                       break;
5979                     case 2:
5980                       code = EQ_EXPR;
5981                       break;
5982                     case 3:
5983                       code = LE_EXPR;
5984                       break;
5985                     case 4:
5986                       code = GT_EXPR;
5987                       break;
5988                     case 5:
5989                       code = NE_EXPR;
5990                       break;
5991                     case 6:
5992                       code = GE_EXPR;
5993                       break;
5994                     case 7:
5995                       /* Always true.  */
5996                       return omit_one_operand (type, integer_one_node, arg0);
5997                     }
5998
5999                   t = build (code, type, cval1, cval2);
6000                   if (save_p)
6001                     return save_expr (t);
6002                   else
6003                     return fold (t);
6004                 }
6005             }
6006         }
6007
6008       /* If this is a comparison of a field, we may be able to simplify it.  */
6009       if ((TREE_CODE (arg0) == COMPONENT_REF
6010            || TREE_CODE (arg0) == BIT_FIELD_REF)
6011           && (code == EQ_EXPR || code == NE_EXPR)
6012           /* Handle the constant case even without -O
6013              to make sure the warnings are given.  */
6014           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6015         {
6016           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6017           return t1 ? t1 : t;
6018         }
6019
6020       /* If this is a comparison of complex values and either or both sides
6021          are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6022          comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6023          This may prevent needless evaluations.  */
6024       if ((code == EQ_EXPR || code == NE_EXPR)
6025           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6026           && (TREE_CODE (arg0) == COMPLEX_EXPR
6027               || TREE_CODE (arg1) == COMPLEX_EXPR
6028               || TREE_CODE (arg0) == COMPLEX_CST
6029               || TREE_CODE (arg1) == COMPLEX_CST))
6030         {
6031           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6032           tree real0, imag0, real1, imag1;
6033
6034           arg0 = save_expr (arg0);
6035           arg1 = save_expr (arg1);
6036           real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6037           imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6038           real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6039           imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6040
6041           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6042                                : TRUTH_ORIF_EXPR),
6043                               type,
6044                               fold (build (code, type, real0, real1)),
6045                               fold (build (code, type, imag0, imag1))));
6046         }
6047
6048       /* From here on, the only cases we handle are when the result is
6049          known to be a constant.
6050
6051          To compute GT, swap the arguments and do LT.
6052          To compute GE, do LT and invert the result.
6053          To compute LE, swap the arguments, do LT and invert the result.
6054          To compute NE, do EQ and invert the result.
6055
6056          Therefore, the code below must handle only EQ and LT.  */
6057
6058       if (code == LE_EXPR || code == GT_EXPR)
6059         {
6060           tem = arg0, arg0 = arg1, arg1 = tem;
6061           code = swap_tree_comparison (code);
6062         }
6063
6064       /* Note that it is safe to invert for real values here because we
6065          will check below in the one case that it matters.  */
6066
6067       invert = 0;
6068       if (code == NE_EXPR || code == GE_EXPR)
6069         {
6070           invert = 1;
6071           code = invert_tree_comparison (code);
6072         }
6073
6074       /* Compute a result for LT or EQ if args permit;
6075          otherwise return T.  */
6076       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6077         {
6078           if (code == EQ_EXPR)
6079             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
6080                                == TREE_INT_CST_LOW (arg1))
6081                               && (TREE_INT_CST_HIGH (arg0)
6082                                   == TREE_INT_CST_HIGH (arg1)),
6083                               0);
6084           else
6085             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6086                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
6087                                : INT_CST_LT (arg0, arg1)),
6088                               0);
6089         }
6090
6091 #if 0 /* This is no longer useful, but breaks some real code.  */
6092       /* Assume a nonexplicit constant cannot equal an explicit one,
6093          since such code would be undefined anyway.
6094          Exception: on sysvr4, using #pragma weak,
6095          a label can come out as 0.  */
6096       else if (TREE_CODE (arg1) == INTEGER_CST
6097                && !integer_zerop (arg1)
6098                && TREE_CONSTANT (arg0)
6099                && TREE_CODE (arg0) == ADDR_EXPR
6100                && code == EQ_EXPR)
6101         t1 = build_int_2 (0, 0);
6102 #endif
6103       /* Two real constants can be compared explicitly.  */
6104       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6105         {
6106           /* If either operand is a NaN, the result is false with two
6107              exceptions: First, an NE_EXPR is true on NaNs, but that case
6108              is already handled correctly since we will be inverting the
6109              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
6110              or a GE_EXPR into a LT_EXPR, we must return true so that it
6111              will be inverted into false.  */
6112
6113           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6114               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6115             t1 = build_int_2 (invert && code == LT_EXPR, 0);
6116
6117           else if (code == EQ_EXPR)
6118             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6119                                                  TREE_REAL_CST (arg1)),
6120                               0);
6121           else
6122             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6123                                                 TREE_REAL_CST (arg1)),
6124                               0);
6125         }
6126
6127       if (t1 == NULL_TREE)
6128         return t;
6129
6130       if (invert)
6131         TREE_INT_CST_LOW (t1) ^= 1;
6132
6133       TREE_TYPE (t1) = type;
6134       if (TREE_CODE (type) == BOOLEAN_TYPE)
6135         return truthvalue_conversion (t1);
6136       return t1;
6137
6138     case COND_EXPR:
6139       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6140          so all simple results must be passed through pedantic_non_lvalue.  */
6141       if (TREE_CODE (arg0) == INTEGER_CST)
6142         return pedantic_non_lvalue
6143           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6144       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6145         return pedantic_omit_one_operand (type, arg1, arg0);
6146
6147       /* If the second operand is zero, invert the comparison and swap
6148          the second and third operands.  Likewise if the second operand
6149          is constant and the third is not or if the third operand is
6150          equivalent to the first operand of the comparison.  */
6151
6152       if (integer_zerop (arg1)
6153           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6154           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6155               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6156                                                  TREE_OPERAND (t, 2),
6157                                                  TREE_OPERAND (arg0, 1))))
6158         {
6159           /* See if this can be inverted.  If it can't, possibly because
6160              it was a floating-point inequality comparison, don't do
6161              anything.  */
6162           tem = invert_truthvalue (arg0);
6163
6164           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6165             {
6166               t = build (code, type, tem,
6167                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6168               arg0 = tem;
6169               /* arg1 should be the first argument of the new T.  */
6170               arg1 = TREE_OPERAND (t, 1);
6171               STRIP_NOPS (arg1);
6172             }
6173         }
6174
6175       /* If we have A op B ? A : C, we may be able to convert this to a
6176          simpler expression, depending on the operation and the values
6177          of B and C.  IEEE floating point prevents this though,
6178          because A or B might be -0.0 or a NaN.  */
6179
6180       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6181           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
6182               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
6183               || flag_fast_math)
6184           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6185                                              arg1, TREE_OPERAND (arg0, 1)))
6186         {
6187           tree arg2 = TREE_OPERAND (t, 2);
6188           enum tree_code comp_code = TREE_CODE (arg0);
6189
6190           STRIP_NOPS (arg2);
6191
6192           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
6193              depending on the comparison operation.  */
6194           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6195                ? real_zerop (TREE_OPERAND (arg0, 1))
6196                : integer_zerop (TREE_OPERAND (arg0, 1)))
6197               && TREE_CODE (arg2) == NEGATE_EXPR
6198               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6199             switch (comp_code)
6200               {
6201               case EQ_EXPR:
6202                 return pedantic_non_lvalue
6203                   (fold (build1 (NEGATE_EXPR, type, arg1)));
6204               case NE_EXPR:
6205                 return pedantic_non_lvalue (convert (type, arg1));
6206               case GE_EXPR:
6207               case GT_EXPR:
6208                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6209                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6210                 return pedantic_non_lvalue
6211                   (convert (type, fold (build1 (ABS_EXPR,
6212                                                 TREE_TYPE (arg1), arg1))));
6213               case LE_EXPR:
6214               case LT_EXPR:
6215                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6216                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6217                 return pedantic_non_lvalue
6218                   (fold (build1 (NEGATE_EXPR, type,
6219                                  convert (type,
6220                                           fold (build1 (ABS_EXPR,
6221                                                         TREE_TYPE (arg1),
6222                                                         arg1))))));
6223               default:
6224                 abort ();
6225               }
6226
6227           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
6228              always zero.  */
6229
6230           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6231             {
6232               if (comp_code == NE_EXPR)
6233                 return pedantic_non_lvalue (convert (type, arg1));
6234               else if (comp_code == EQ_EXPR)
6235                 return pedantic_non_lvalue (convert (type, integer_zero_node));
6236             }
6237
6238           /* If this is A op B ? A : B, this is either A, B, min (A, B),
6239              or max (A, B), depending on the operation.  */
6240
6241           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6242                                               arg2, TREE_OPERAND (arg0, 0)))
6243             {
6244               tree comp_op0 = TREE_OPERAND (arg0, 0);
6245               tree comp_op1 = TREE_OPERAND (arg0, 1);
6246               tree comp_type = TREE_TYPE (comp_op0);
6247
6248               switch (comp_code)
6249                 {
6250                 case EQ_EXPR:
6251                   return pedantic_non_lvalue (convert (type, arg2));
6252                 case NE_EXPR:
6253                   return pedantic_non_lvalue (convert (type, arg1));
6254                 case LE_EXPR:
6255                 case LT_EXPR:
6256                   /* In C++ a ?: expression can be an lvalue, so put the
6257                      operand which will be used if they are equal first
6258                      so that we can convert this back to the
6259                      corresponding COND_EXPR.  */
6260                   return pedantic_non_lvalue
6261                     (convert (type, (fold (build (MIN_EXPR, comp_type,
6262                                                   (comp_code == LE_EXPR
6263                                                    ? comp_op0 : comp_op1),
6264                                                   (comp_code == LE_EXPR
6265                                                    ? comp_op1 : comp_op0))))));
6266                   break;
6267                 case GE_EXPR:
6268                 case GT_EXPR:
6269                   return pedantic_non_lvalue
6270                     (convert (type, fold (build (MAX_EXPR, comp_type,
6271                                                  (comp_code == GE_EXPR
6272                                                   ? comp_op0 : comp_op1),
6273                                                  (comp_code == GE_EXPR
6274                                                   ? comp_op1 : comp_op0)))));
6275                   break;
6276                 default:
6277                   abort ();
6278                 }
6279             }
6280
6281           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6282              we might still be able to simplify this.  For example,
6283              if C1 is one less or one more than C2, this might have started
6284              out as a MIN or MAX and been transformed by this function.
6285              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
6286
6287           if (INTEGRAL_TYPE_P (type)
6288               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6289               && TREE_CODE (arg2) == INTEGER_CST)
6290             switch (comp_code)
6291               {
6292               case EQ_EXPR:
6293                 /* We can replace A with C1 in this case.  */
6294                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6295                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6296                            TREE_OPERAND (t, 2));
6297                 break;
6298
6299               case LT_EXPR:
6300                 /* If C1 is C2 + 1, this is min(A, C2).  */
6301                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6302                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6303                                         const_binop (PLUS_EXPR, arg2,
6304                                                      integer_one_node, 0), 1))
6305                   return pedantic_non_lvalue
6306                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6307                 break;
6308
6309               case LE_EXPR:
6310                 /* If C1 is C2 - 1, this is min(A, C2).  */
6311                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6312                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6313                                         const_binop (MINUS_EXPR, arg2,
6314                                                      integer_one_node, 0), 1))
6315                   return pedantic_non_lvalue
6316                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6317                 break;
6318
6319               case GT_EXPR:
6320                 /* If C1 is C2 - 1, this is max(A, C2).  */
6321                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6322                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6323                                         const_binop (MINUS_EXPR, arg2,
6324                                                      integer_one_node, 0), 1))
6325                   return pedantic_non_lvalue
6326                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6327                 break;
6328
6329               case GE_EXPR:
6330                 /* If C1 is C2 + 1, this is max(A, C2).  */
6331                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6332                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6333                                         const_binop (PLUS_EXPR, arg2,
6334                                                      integer_one_node, 0), 1))
6335                   return pedantic_non_lvalue
6336                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6337                 break;
6338               case NE_EXPR:
6339                 break;
6340               default:
6341                 abort ();
6342               }
6343         }
6344
6345       /* If the second operand is simpler than the third, swap them
6346          since that produces better jump optimization results.  */
6347       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
6348            || TREE_CODE (arg1) == SAVE_EXPR)
6349           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6350                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
6351                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6352         {
6353           /* See if this can be inverted.  If it can't, possibly because
6354              it was a floating-point inequality comparison, don't do
6355              anything.  */
6356           tem = invert_truthvalue (arg0);
6357
6358           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6359             {
6360               t = build (code, type, tem,
6361                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6362               arg0 = tem;
6363               /* arg1 should be the first argument of the new T.  */
6364               arg1 = TREE_OPERAND (t, 1);
6365               STRIP_NOPS (arg1);
6366             }
6367         }
6368
6369       /* Convert A ? 1 : 0 to simply A.  */
6370       if (integer_onep (TREE_OPERAND (t, 1))
6371           && integer_zerop (TREE_OPERAND (t, 2))
6372           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6373              call to fold will try to move the conversion inside
6374              a COND, which will recurse.  In that case, the COND_EXPR
6375              is probably the best choice, so leave it alone.  */
6376           && type == TREE_TYPE (arg0))
6377         return pedantic_non_lvalue (arg0);
6378
6379       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
6380          operation is simply A & 2.  */
6381
6382       if (integer_zerop (TREE_OPERAND (t, 2))
6383           && TREE_CODE (arg0) == NE_EXPR
6384           && integer_zerop (TREE_OPERAND (arg0, 1))
6385           && integer_pow2p (arg1)
6386           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6387           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6388                               arg1, 1))
6389         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6390
6391       return t;
6392
6393     case COMPOUND_EXPR:
6394       /* When pedantic, a compound expression can be neither an lvalue
6395          nor an integer constant expression.  */
6396       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6397         return t;
6398       /* Don't let (0, 0) be null pointer constant.  */
6399       if (integer_zerop (arg1))
6400         return build1 (NOP_EXPR, TREE_TYPE (arg1), arg1);
6401       return arg1;
6402
6403     case COMPLEX_EXPR:
6404       if (wins)
6405         return build_complex (type, arg0, arg1);
6406       return t;
6407
6408     case REALPART_EXPR:
6409       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6410         return t;
6411       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6412         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6413                                  TREE_OPERAND (arg0, 1));
6414       else if (TREE_CODE (arg0) == COMPLEX_CST)
6415         return TREE_REALPART (arg0);
6416       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6417         return fold (build (TREE_CODE (arg0), type,
6418                             fold (build1 (REALPART_EXPR, type,
6419                                           TREE_OPERAND (arg0, 0))),
6420                             fold (build1 (REALPART_EXPR,
6421                                           type, TREE_OPERAND (arg0, 1)))));
6422       return t;
6423
6424     case IMAGPART_EXPR:
6425       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6426         return convert (type, integer_zero_node);
6427       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6428         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6429                                  TREE_OPERAND (arg0, 0));
6430       else if (TREE_CODE (arg0) == COMPLEX_CST)
6431         return TREE_IMAGPART (arg0);
6432       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6433         return fold (build (TREE_CODE (arg0), type,
6434                             fold (build1 (IMAGPART_EXPR, type,
6435                                           TREE_OPERAND (arg0, 0))),
6436                             fold (build1 (IMAGPART_EXPR, type,
6437                                           TREE_OPERAND (arg0, 1)))));
6438       return t;
6439
6440       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6441          appropriate.  */
6442     case CLEANUP_POINT_EXPR:
6443       if (! has_cleanups (arg0))
6444         return TREE_OPERAND (t, 0);
6445
6446       {
6447         enum tree_code code0 = TREE_CODE (arg0);
6448         int kind0 = TREE_CODE_CLASS (code0);
6449         tree arg00 = TREE_OPERAND (arg0, 0);
6450         tree arg01;
6451
6452         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6453           return fold (build1 (code0, type,
6454                                fold (build1 (CLEANUP_POINT_EXPR,
6455                                              TREE_TYPE (arg00), arg00))));
6456
6457         if (kind0 == '<' || kind0 == '2'
6458             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6459             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
6460             || code0 == TRUTH_XOR_EXPR)
6461           {
6462             arg01 = TREE_OPERAND (arg0, 1);
6463
6464             if (TREE_CONSTANT (arg00)
6465                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6466                     && ! has_cleanups (arg00)))
6467               return fold (build (code0, type, arg00,
6468                                   fold (build1 (CLEANUP_POINT_EXPR,
6469                                                 TREE_TYPE (arg01), arg01))));
6470
6471             if (TREE_CONSTANT (arg01))
6472               return fold (build (code0, type,
6473                                   fold (build1 (CLEANUP_POINT_EXPR,
6474                                                 TREE_TYPE (arg00), arg00)),
6475                                   arg01));
6476           }
6477
6478         return t;
6479       }
6480
6481     default:
6482       return t;
6483     } /* switch (code) */
6484 }
6485
6486 /* Determine if first argument is a multiple of second argument.
6487    Return 0 if it is not, or is not easily determined to so be.
6488
6489    An example of the sort of thing we care about (at this point --
6490    this routine could surely be made more general, and expanded
6491    to do what the *_DIV_EXPR's fold() cases do now) is discovering
6492    that
6493
6494      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6495
6496    is a multiple of
6497
6498      SAVE_EXPR (J * 8)
6499
6500    when we know that the two `SAVE_EXPR (J * 8)' nodes are the
6501    same node (which means they will have the same value at run
6502    time, even though we don't know when they'll be assigned).
6503
6504    This code also handles discovering that
6505
6506      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6507
6508    is a multiple of
6509
6510      8
6511
6512    (of course) so we don't have to worry about dealing with a
6513    possible remainder.
6514
6515    Note that we _look_ inside a SAVE_EXPR only to determine
6516    how it was calculated; it is not safe for fold() to do much
6517    of anything else with the internals of a SAVE_EXPR, since
6518    fold() cannot know when it will be evaluated at run time.
6519    For example, the latter example above _cannot_ be implemented
6520    as
6521
6522      SAVE_EXPR (I) * J
6523
6524    or any variant thereof, since the value of J at evaluation time
6525    of the original SAVE_EXPR is not necessarily the same at the time
6526    the new expression is evaluated.  The only optimization of this
6527    sort that would be valid is changing
6528
6529      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6530    divided by
6531      8
6532
6533    to
6534
6535      SAVE_EXPR (I) * SAVE_EXPR (J)
6536
6537    (where the same SAVE_EXPR (J) is used in the original and the
6538    transformed version).  */
6539
6540 static int
6541 multiple_of_p (type, top, bottom)
6542      tree type;
6543      tree top;
6544      tree bottom;
6545 {
6546   if (operand_equal_p (top, bottom, 0))
6547     return 1;
6548
6549   if (TREE_CODE (type) != INTEGER_TYPE)
6550     return 0;
6551
6552   switch (TREE_CODE (top))
6553     {
6554     case MULT_EXPR:
6555       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6556               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6557
6558     case PLUS_EXPR:
6559     case MINUS_EXPR:
6560       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6561               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6562
6563     case NOP_EXPR:
6564       /* Punt if conversion from non-integral or wider integral type.  */
6565       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6566           || (TYPE_PRECISION (type)
6567               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6568         return 0;
6569       /* Fall through. */
6570     case SAVE_EXPR:
6571       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6572
6573     case INTEGER_CST:
6574       if ((TREE_CODE (bottom) != INTEGER_CST)
6575           || (tree_int_cst_sgn (top) < 0)
6576           || (tree_int_cst_sgn (bottom) < 0))
6577         return 0;
6578       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6579                                          top, bottom, 0));
6580
6581     default:
6582       return 0;
6583     }
6584 }
6585 \f