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