gcc/fold-const.c

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